首页 > 代码库 > RSA算法介绍与C实现算法
RSA算法介绍与C实现算法
什么是rsa：
RSA公开密钥密码体制。所谓的公开密钥密码体制就是使用不同的加密密钥与解密密钥，是一种“由已知加密密钥推导出解密密钥在计算上是不可行的”密码体制。
在在公开密钥密码体制中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，但却不能根据PK计算出SK。
rsa的算法描述：
（1）选择一对不同的、足够大的素数p，q。
（2）计算n=pq。
（3）计算f(n)=(p-1)(q-1)，同时对p, q严加保密，不让任何人知道。
（4）找一个与f(n)互质的数e，且1<e<f(n)。
（5）计算d，使得de≡1 mod f(n)。这个公式也可以表达为d ≡e-1 mod f(n)
（6）公钥KU=(e,n)，私钥KR=(d,n)。
（7）加密时，先将明文变换成0至n-1的一个整数M。若明文较长，可先分割成适当的组，然后再进行交换。设密文为C，则加密过程为：
。
（8）解密过程为：
。
#include <stdio.h>#include <math.h>#include <stdlib.h> int length = 0 ;bool JudgeP (int prime) //判断是不是素数{ int i=0; long double temp=0 ; if (prime == 0||prime == 2) return false; else { temp =sqrt((float)prime); for (i=2;i<=temp;i++) { if (prime%i == 0) return false; //输入的不是素数 } return true ; //输入的数是素数 } }long int InputP ( ) //直到输入素数{ int num; scanf_s("%d",&num); while (!JudgeP(num)) { printf("您输入的的不是素数，请重新输入!\n"); scanf_s("%d",&num); } return num ;}int gcd(int a , int b){ return b==0?a:gcd(b,a%b);}long int CheckE (long int f_n ) //判断e是否符合要求 1<e <f_n且e 与f_n互素{ long int e ; int k ; printf("please enter e(1<e<f_n) :"); scanf_s("%d",&e ); while (e > f_n || e<= 1) //确定e的范围 { printf("e is‘t fit ,enter again!(1<e<f_n)"); scanf_s("%d",&e ); } k =gcd(f_n,e) ; while (k != 1) { printf("e with f_n relatively prime，enter again!"); scanf_s("%d",&e); k =gcd(f_n,e) ; } return e ;}long int CalculateD(long int f_n ,long int e) //辗转相除{ int i , j = 1 , t1 , t2= 1 , k = 0 , m ; int arry_1[30] = {f_n,e} ,arry_2[30] ={0} ; printf(" the Calculation:\n") ; for (i=1 ; (arry_1[i] != 0 )&&( arry_1[i] != 1); i ++) { arry_1[i+1] =arry_1[i-1]%arry_1[i] ; arry_2 [i-1] = arry_1[i-1]/arry_1[i] ; printf(" %d = %d*%d+%d\n",arry_1[i-1],arry_1[i],arry_2[i-1],arry_1[i+1] ) ; } t1 = 1 ; t2 = -arry_2[i-2] ; while((i -2)!= k ) { m = t1 ; t1 = t2 ; if (j%2 != 0) t2 = (abs(m)+arry_2[i-3]*abs(t2) ); else t2 = -(abs(m)+arry_2[i-3]*abs(t2) ); i -- ; j++ ; } while(t2 < 0) { t2 = f_n + t2 ; } k = t2 ; while(t2 = t2/f_n) { k = t2%f_n ; } printf("k = %d\n",k); return k ;}int * Dec2Bin(int e ) //转换为二进制 { int i = 0 ; int str1[20] ,str2[20] ; while(e) { str1[i] = e%2 ; e = e/2 ; i++ ; } i -- ; printf("The binary is :"); for (length = 0 ; i>=0 ; length ++) { str2[length] = str1[i] ; printf("%d",str2[length]); i -- ; } return str2 ; } int Encrypt(int m , int e , int n) //平方乘法 { int c =1 , i ; int *p = Dec2Bin(e) ; for (i = 0 ; i < length;i ++) { c = c %n; c =c*c%n ; if (*(p+i) == 1) { c =c%n; c =c*m%n; } } return c ; }int main(void){ long int p,q ,n,f_n ,e ,d,m,c,l; printf("please enter p:"); //p,q输入 p = InputP(); printf("please enter q "); q = InputP(); n = p*q ; //计算n,f_n f_n =(p-1)*(q-1); e = CheckE(f_n ); //计算e d=CalculateD(f_n,e); //计算d printf("please enter m "); scanf_s("%d",&m) ; c =Encrypt(m,e,n); printf("c is %d\n",c ); l=Encrypt(c,d,n); printf("l is %d\n",l );system("pause");return 0 ;}
RSA算法介绍与C实现算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。