简介

RSA算法是一种非对称算法，即公钥和密钥不相同，本质是利用2个大素数的乘积难以做因素分解。

算法

RSA算法的密钥由3个数构成N，d，e

N由2个互不相同的素数的乘积构成 $$ N=pq $$
根据欧拉函数，求得r，即小于N且与N互质的数的个数。 $$ {\displaystyle r=\varphi (N)=(p-1)(q-1)} $$
选择其中的一个质数为e，找到一个数 d。 $$ ed \bmod r=1 $$

现在N，d，e都已经拿到了，公钥是(N, e)，私钥是(N, d)。那么N和e就是公开的，而d是保密的。

测试

然后就能使用公钥加密数据，然后私钥解密数据了。

首先我们先选2个素数来算出N，我这里选择了3和5，那么N = 3 x 5 = 15
那么r = (3 - 1) x (5 - 1) = 8，即15以内有8个数与它互质，他们分别是1，2，4，7，8，11，13，14。其中质数有2，7，11，13。

这里选择11为e，根据(d x 11) % 8 = 1，求出d = 3

d = 0
e = 11
r = 8
while(1):
    if ((d * e) % r == 1):
        print(d)	//3
        break
    d = d + 1

那么现在N = 15，e = 11，d = 3，公钥为(15, 11)，私钥为(15, 3)。

既然有了密钥，那么现在开始对数据进行加密。(加密的数字必须小于N)

加密公式 $$ 明文^{e} \bmod N = 密文 $$
解密公式 $$ 密文^{d} \bmod N = 明文 $$

尝试加解密

N = 15
e = 11
d = 3

plaintext = 12
print("明文为：",plaintext)
ciphertext = pow(plaintext, e, N)   #加密
print("密文为：", ciphertext)
test_plaintext = pow(ciphertext, d, N)  #尝试解密
print("解密出来的明文为：", test_plaintext)
"""
(venv) dayu@dayudeMacBook-Air test % python main.py
明文为： 12
密文为： 3
解密出来的明文为： 12
"""

攻击

现在来分析rsa算法为什么难以攻击。

我们来用python编写一个攻击上面密文的程序。作为中间人，已知：N = 15，e = 11，密文 = 3。

首先想要解密我们得拿到d才能解密密文，先来梳理一下rsa流程：

我们通过随机2个素数p = 3，q = 5，算出了N = pq = 15
然后通过欧拉公式得到r = (p - 1)(q - 1) = 8
然后随机从中挑选了一个质数e = 11，然后通过模逆元得到了d = 3。

反推流程：

上面第3步在得知r的情况下，e和d是可以互推的，其中e是已知的。
如何来得到r？r是N欧拉公式的结果，涉及到了pq分别减1的乘积，其中N是公开的，由于算术基本定理，pq是唯一的素数因数。这里可以通过彩虹表的形式来得到pq，从而反解出r，再反解出d，拿到私钥。

代码如下：

def get_primes(maxnum):
    primes_list = []
    for x in range(2, maxnum):
        i = 2
        for i in range(2, x):
            if (x % i == 0):
                break
        else:
            primes_list.append(x)
    return primes_list

def crack_primes(maxnum, N):
    primes_list = get_primes(maxnum)
    for p in primes_list:
        for q in primes_list:
            if p * q == N:
                return p,q

N = 15
e = 11
ciphertext = 3

p, q = crack_primes(100,N)

r = (p - 1) * (q - 1)

for d in range(r):
    if ((d * e) % r == 1):
        break

test_plaintext = pow(ciphertext, d, N)

print("p:", p, ", q:", q, ", d:", d, ", 密文:", test_plaintext)
"""
(venv) dayu@dayudeMacBook-Air test % python main.py
p: 3 , q: 5 , d: 3 , 密文: 12
"""

Success

对极大整数做因数分解的难度决定了 RSA 算法的可靠性，上面用的pq才1位，现在可靠的RSA加密是2048位。

一些思考和解答

算术基本定理：https://www.zhihu.com/question/490412529

N的彩虹表：https://www.zhihu.com/question/537849302

简介#

算法#

测试#

攻击#

一些思考和解答#

简介

算法

测试

攻击

一些思考和解答