RSA加密算法


		算法的描述：
 
1.选取两个素数p,q
 
2.计算n=p*q,fn=(p-1)*(q-1)
 
3.选择一个整数e，使得e与fn的最大公约数为1，e将会用于对数据进行加密。
 
4.计算出一个整数d，使得d*e除fn的余数为1。d用于对密文进行解密，还原出明文。
 
5.假设明文为m,密文为c。
 
如果需要对原文进行加密，则进行如下的计算
 
c= me mod n
 
如需将密文还原成明文，进行如下计算
 
m=cd mod n
 
6.假设p=101,q=103，则n=101*103=10403,fn=100*102=10200
 
e=7。因为7与10200的最大公约数为1。
 
d=8743。因为8743*7 mod 10200=1
 
(1)假设明文为一个整数73
 
则通过RSA加密后为
 
73^7%10403=7716
 
(2)还原出7716的原文
 
7716^8743%10403=73。
 
 
下面是杭电OJ上一道关于RSA的题目，题目中给出p,q和e的值，并给出一些加密之后的密文。要求还原出原来明文。题描述可参见http://acm.hdu.edu.cn/showproblem.php?pid=1211
 
下面是对RSA算法加密的密文进行还原的C代码
 
[cpp]  
#include<stdio.h>  
  
int main(){  
    int p,q,e;  
    int l,ch,i;  
    while(scanf("%d%d%d%d",&p,&q,&e,&l)!=EOF){  
        long long n=p*q;  
        long long fn=(p-1)*(q-1);  
        int d=1;  
        //暴力计算出d的值。使得d*e%fn=1  
        while((d*e)%fn!=1){  
            d++;  
        }  
        while(l--){  
            scanf("%d",&ch);  
            int result=1;  
            //计算 m^d%n的值，即明文  
            for(i=1;i<=d;i++){  
                result=(result*ch)%n;  
            }  
            printf("%c",result);  
        }  
        printf("\n");  
    }  
    return 0;  
}  
 
 
从上面的程序中可以看出，在还原明文中最重要的是计算出d的值。RSA算法在加解密过程都需要进行幂运算，现在为了RSA算法的安全,p和q的值一般都在100以

补充：综合编程 , 安全编程 ,