C H A N N G

写作的意义,是分享给未来的自己

超详细的RSA

RSA

网上有很多RSA讲解,但是看了我这篇,你一定能完全弄明白RSA

RSA是一种非对称加密算法,要加密一段数据,首先我们要拿到公钥和私钥。

首选取两个互质数 p q
那么p * q 得到 N
这时我要计算出φ(N)
φ函数φ(N)是小于或等于N的正整数中与N互质的数的数目。

根据欧拉公式,我知道

φ(N) = (p-1)*(q-1)

当然前提p q都是质数

现在我们举例子
首先我选择两个互质数 p=11 q=13
所以N = pq = 1113 = 143
根据公式得到φ(N) = 120
这时候我们随机选择一个整数e,条件是1< e < φ(n),且e与φ(n) 互质。
现在我们选择e =7
接着我们计算eφ(n)的模逆元

根据欧拉定理得到的公式

e*d ≡ 1 (mod φ(n))

这个公式简单的说就是 e*d除以φ(N)得到的余数为1

这个公式可以转换成

e*d - 1 = kφ(n)

所以,已知 e = 7 φ(n) = 120

7d + 120*k = 1

辗转相除法计算d

120 = 7 * 17 + 1
17 = 17 * 1

1 = 120 * 1 + 7 * (-17)

1 = 120 * 1 + 7 *(-17)
最终得出,d = -17 k = 1

虽然我们得到了 d=-17但 在rsa中 d必须是一个正整数,在工程中,RSA的pq会无穷大过公钥质数e ,所以根本不会出现这种状况。但是如果出现负数,我们会将它翻转

if(d<0)
	d=d+φ(n)

所以得到 eφ(n)的模逆元 为 120 + (-17)也就是103

RSA中 公钥就是 N,e 而 私钥就是N,d

我们上面的例子 公钥 (143,7) 私钥(143, 103)

加密

m^e ≡ c (mod n)

要加密的m = 13

13^7 = 117 (mod 143)

解密

c^d ≡ m (mod n)

要解密的是c = 117

117^103 = 13 (mod 143)

上面可以用快速幂取余来计算出余数

#include <stdio.h>
long PowerMod (int a, int b, int c) {
    int  ans = 1;
    a = a % c;
    while(b>0) {
        if(b % 2 == 1)
            ans = (ans * a) % c;
        b = b/2;       //   b>>=1;
        a = (a * a) % c;
    }
    return ans;
}

rsa 为什么安全。

  (1)ed≡1 (mod φ(n))。只有知道e和φ(n),才能算出d。

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

  (3n=pq。只有将n因数分解,才能算出p和q。

这段转自阮一峰大大的博客

道理很简单,只要能将N进行因式分解,那么RSA的就不再安全。

所以然你可因式分解143 = 13* 11
但是你不可能分解

18728736598172301274983275897298461982739812703985619727398173
*
13824985149871927398172398479818203801740957019283098109283757

最后附上一个扩展欧几里得算法,也就是扩展辗转相除法的c实现

int gcdEx(int a, int b, int *x, int *y) 
{
    if(b==0)
    {
        *x = 1,*y = 0;
        return a;
    }
    else
    {
        int r = gcdEx(b, a%b, x, y); /* r = GCD(a, b) = GCD(b, a%b) */
        int t = *x;
        *x = *y;
        *y = t - a/b * *y;
        return r;
    }
}

当然,最后还是再换个其他的数来计算一遍扩展辗转相除法

53 102 互质

102 = 53 *1 +49
53 = 49 *1 + 4
49 = 12 * 4 + 1

//余数放到前面
49 = 102*1 + 53*(-1)
4 = 53*1 +49 *(-1)
1 = 49 * 1 + 4 *(-12)

//放回去
1 = 49 * 1 + 4 *(-12)
1 = 49 * 1 + [53*1 +49 *(-1)] *(-121 = 49*(13)+53*(-12)
1 = [102*1 + 53*(-1)]*13 + 53*(-12)
1 = 102 * 13 + 53* (-25)

最后在 用

102 + (-25) 得出 53 对102 的逆元 为77

京ICP备18015771号