首页 > 代码库 > RSA算法初学

RSA算法初学

2024-07-03 23:25:14   226人阅读

RSA的算法涉及三个参数，n、e1、e2。
其中，n是两个大质数p、q的积，n的二进制表示时所占用的位数，就是所谓的密钥长度。
e1和e2是一对相关的值，e1可以任意取，但要求e1与(p-1）*(q-1）互质；再选择e2，要求（e2*e1）mod((p-1）*(q-1））=1。
（n，e1）,(n，e2）就是密钥对。其中(n，e1）为公钥，(n，e2）为私钥。[1]
RSA加解密的算法完全相同，设A为明文，B为密文，则：A=B^e2 mod n；B=A^e1 mod n；（公钥加密体制中，一般用公钥加密，私钥解密）
e1和e2可以互换使用，即：
A=B^e1 mod n；B=A^e2 mod n;
（摘自百度百科）
其中
　　p (p，q两数互质)
　　q
　　n （p*q）
　　φ(n)(欧拉函数，即(p-1)*(q-1))
　　e1
　　e2
 
 
在知道了n和e1的情况下,我们能不能破解出e2呢？

　　（1）e1*e2≡1 (mod φ(n))。只有知道e和φ(n)，才能算出d。

　　（2）φ(n)=(p-1)(q-1)。只有知道p和q，才能算出φ(n)。

　　（3）n=pq。只有将n因数分解，才能算出p和q。

分解出因数p和q就好办了（但是大数分解是非常困难的事情，目前只能破解到768位）

得到pq以后，为了算e2，根据（1）我们可以构造出m * a + n * b = 1 的二元一次方程，进而转化为求它的整数解，求解这个方程，用到“扩展欧几里得”算法，下面有C程序源代码。

 
//扩展欧几里得算法c语言
#include<stdio.h>

void EGCD(int m,int n)
{
    int a,a1,b,b1,c,d,q,r,t;
    a1=b=1,a=b1=0,c=m,d=n;
    while(1)
    {
        q=c/d,r=c%d;
        if(r==0)
        {
            printf("(%d)*%d+(%d)*%d=%d\n",a,m,b,n,d);
            return;
        }
        c=d,d=r,t=a1,a1=a,a=t-q*a,t=b1,b1=b,b=t-q*b;
    }
}

void main(){
    printf("给定两个正整数m和n,我们计算它们的最大公因子d和两个整数a和b,使得a*m+b*n=d\n");
    int m,n;
    scanf("%d%d",&m,&n);
    EGCD(m,n);
}

 


联系
我们