RSA简述 - #瘫男日记

1. 概述

RSA算法常用于非对称加密，非对称加密流程如下：

乙方生成两把密钥(公钥和私钥)。公钥是公开的，任何人都可以获得，私钥则是保密的。
甲方获取乙方的公钥，然后用它对信息加密。
乙方得到加密后的信息，用私钥解密。

特点：

算法是可逆的，即用公钥加密的信息可以用私钥解密；用私钥加密的信息可以被公钥解密
不能由公钥推算出私钥（前提是所取的质数不是特别小）

2. 数论基础

2.1 素数

素数又称质数，指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。这个概念，我们在上初中，甚至小学的时候都学过了，这里就不再过多解释了。

2.2 模运算

模运算即求余运算。“模”是“Mod”的音译。和模运算紧密相关的一个概念是“同余”。数学上，当两个整数除以同一个正整数，若得相同余数，则二整数同余。

两个整数a，b，若它们除以正整数m所得的余数相等，则称a，b对于模m同余，记作: a ≡ b \ (mod m)；读作：a同余于b模m，或者，a与b关于模m同余。例如：26 ≡ 14 \ (mod 12)。

2.3 互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

关于互质关系，不难得到以下结论：

任意两个质数构成互质关系，比如13和61。
一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。
如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。
1和任意一个自然数是都是互质关系，比如1和99。
p是大于1的整数，则p和p-1构成互质关系，比如57和56。
p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

2.4 欧拉函数

请思考以下问题：

任意给定正整数n，请问在小于等于n的正整数之中，有多少个与n构成互质关系？（比如，在1到8之中，有多少个数与8构成互质关系？）

计算这个值的方法就叫做欧拉函数，以φ(n)表示。在1到8之中，与8形成互质关系的是1、3、5、7，所以 φ(8) = 4。

φ(n)的计算方法并不复杂，但是为了得到最后那个公式，需要一步步讨论。

第1种情况

如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系。

第2种情况

如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系。比如5与1、2、3、4都构成互质关系。

第3种情况

如果n是质数的某一个次方，即 n = p^k (p为质数，k为大于等于1的整数)，则

φ(p^k)=p^k-p^{k-1}

比如 φ(8) = φ(2^3) =2^3 – 2^2 = 8 -4 = 4。

这是因为只有当一个数不包含质数p，才可能与n互质。而包含质数p的数一共有p^(k-1)个，即1×p、2×p、3×p、…、p^(k-1)×p，把它们去除，剩下的就是与n互质的数。

上面的式子还可以写成下面的形式：

φ(p^k)=p^k-p^{k-1}=p^k(1-\frac 1p)

可以看出，上面的第2种情况是 k=1 时的特例。

第4种情况

如果n可以分解成两个互质的整数之积，

n = p1 × p2

则

φ(n) = φ(p1p2) = φ(p1)φ(p2)

即积的欧拉函数等于各个因子的欧拉函数之积。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。

这一条的证明要用到“中国剩余定理”，这里就不展开了，只简单说一下思路：如果a与p1互质(a < p1)，b与p2互质(b < p2)，c与p1p2互质(c < p1p2)，则c与数对 (a,b) 是一一对应关系。由于a的值有φ(p1)种可能，b的值有φ(p2)种可能，则数对 (a,b) 有φ(p1)φ(p2)种可能，而c的值有φ(p1p2)种可能，所以φ(p1p2)就等于φ(p1)φ(p2)。

第5种情况

因为任意一个大于1的正整数，都可以写成一系列质数的积。

n=p^{k1}_1p^{k2}_2p^{k3}_3...p^{kr}_r

根据第4条的结论，得到:

φ(n)=φ(p^{k1}_1)φ(p^{k2}_2)φ(p^{k3}_3)...φ(p^{kr}_r)

再根据第3条的结论，得到:

φ(n)=p^{k1}_1p^{k2}_2p^{k3}_3...p^{kr}_r(1-\frac 1p_1)(1-\frac 1p_2)(1-\frac 1p_3)(1-\frac 1p_r)

也就等于:

φ(n)=n(1-\frac 1p_1)(1-\frac 1p_2)(1-\frac 1p_3)(1-\frac 1p_r)

这就是欧拉函数的通用计算公式。比如，1323的欧拉函数，计算过程如下：

φ(1323)=φ(3^2\times7^2)=1323(1-\frac 13)(1-\frac 17)=756

2.5 欧拉定理

欧拉函数的用处，在于欧拉定理。”欧拉定理”指的是：

如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立:

a^{φ(n)}=1(mod\,n)

也就是说，a的φ(n)次方被n除的余数为1。或者说，a的φ(n)次方减去1，可以被n整除。比如，3和7互质，而7的欧拉函数φ(7)等于6，所以3的6次方（729）减去1，可以被7整除（728/7=104）。

欧拉定理的证明比较复杂，这里就省略了。我们只要记住它的结论就行了。

欧拉定理可以大大简化某些运算。比如，7和10互质，根据欧拉定理，

7^{φ(10)}=1(mod\,10)

已知 φ(10) 等于4，所以马上得到7的4倍数次方的个位数肯定是1。

7^{4k}=1(mod\,10)

因此，7的任意次方的个位数（例如7的222次方），心算就可以算出来。

欧拉定理有一个特殊情况。

假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成

a^{p-1}=1(mod\,p)

这就是著名的费马小定理。它是欧拉定理的特例。

欧拉定理是RSA算法的核心。理解了这个定理，就可以理解RSA。

2.6 模反元素

还剩下最后一个概念：

如果两个正整数a和n互质，那么一定可以找到整数b，使得ab-1被n整除，或者说ab被n除的余数是1。

ab=1(mod\,n)

这时，b就叫做a的“模反元素”。

比如，3和11互质，那么3的模反元素就是4，因为 (3 × 4)-1 可以被11整除。显然，模反元素不止一个， 4加减11的整数倍都是3的模反元素 {…,-18,-7,4,15,26,…}，即如果b是a的模反元素，则 b+kn 都是a的模反元素。

欧拉定理可以用来证明模反元素必然存在。

a^{φ(n)}=a\times a^{φ(n)-1}=1(mod\,n)

可以看到，a的 φ(n)-1 次方，就是a的模反元素。

3. RSA算法

3.1 随机选择两个不相等的质数p和q

这边我们选择61和53.（实际应用中，这两个质数越大，就越难破解。）

3.2 计算p和q的乘积n。

把61和53相乘。

n = 61×53 = 3233

n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

3.3 计算n的欧拉函数φ(n)。

n是质数，则 φ(n)=n-1
n = p1 × p2
φ(n) = φ(p1p2) = φ(p1)φ(p2)
=> φ(n) = (p-1)(q-1)

算出φ(3233)等于60×52，即3120。

3.4 随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质。

就在1到3120之间，随机选择了17。（实际应用中，常常选择65537。）

3.5 计算e对于φ(n)的模反元素d。

所谓”模反元素”就是指有一个整数d，可以使得ed被φ(n)除的余数为1。

ed ≡ 1 (mod φ(n))

这个式子等价于

ed – 1 = kφ(n)

于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。(-k = y)

ex + φ(n)y = 1

已知 e=17, φ(n)=3120，

17x + 3120y = 1

这个方程可以用“扩展欧几里得算法”(又叫辗转相除法)求解，此处省略具体过程。总之，算出一组整数解为 (x,y)=(2753,-15)，即 d=2753。

至此所有计算完成。

3.6 将n和e封装成公钥，n和d封装成私钥。

在这个例子中，n=3233，e=17，d=2753，所以公钥就是 (3233,17)，私钥就是（3233, 2753）。

OK，上面一大段都是我从网上cv下来的。原文链接🌹 写的特别好！下面的Python版RSA算法就是根据这篇文章写的（这个是我纯手撕的🌹）

4. Python实现

由于只供学习理解用，该代码有很多不足，但是能跑，还请见谅🌹

我和代码有一个能跑就行🌹

有2种模式：

自动生成质数p、q
手动输入质数p、q

4.1 完整代码

# Author：taiyang
# welcome to https://taiyang.space
 
import random
import math
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：判断输入的p、q是不是质数
param：p、q
return：如果是返回 True
'''
 
 
def judgePandQ(p, q):
    ls = []
    ls.append(p)
    ls.append(q)
    for x in range(0, 2):
        if int(ls[x]) > 1:
            # 查看因子
            for i in range(2, int(ls[x])):
                if (int(ls[x]) % i) == 0:
                    print(int(ls[x]), "不是质数")
                    print(i, "乘于", int(ls[x]) / i, "是", int(ls[x]))
                    return False
                else:
                    return True
        # 如果输入的数字小于或等于 1，不是质数
        else:
            print(int(ls[x]), "不是质数")
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：计算出 N 和 L
param：p、q
return：N、L
'''
 
 
def getNandL(p, q):
    N = p * q
    L = (p - 1) * (q - 1)
    return N, L
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：计算出 e
param：p、q
return：一个存放所有E的列表
'''
 
 
def getE(p, q):
    N, L = getNandL(p, q)
    listOfE = []
    for i in range(2, L):
        if math.gcd(i, L) == 1:
            listOfE.append(i)
    return listOfE
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：计算出 d
param：p、q
return：一个字典；结构{e1:d1, e2:d2}   每一个e都有对应的d并且去掉重复的
'''
 
 
def getdict_EandD(p, q):
    N, L = getNandL(p, q)
    listOfE = getE(p, q)
    dict_EandD = {}
    for e in listOfE:
        for d in range(2, L):
            # 构建字典并去重
            if (e * d) % L == 1 and e != d:
                dict_EandD[e] = d
    return dict_EandD
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：计算公钥和私钥
param：p、q
return：publicKey, privateKey, N, L，E，D
'''
 
 
def getKey(p, q):
    if judgePandQ(p, q):
        N, L = getNandL(p, q)
        listOfE = getE(p, q)
        dict_EandD = getdict_EandD(p, q)
 
        # 获取E的值
        print("这是所有可用的E\n", listOfE, "\n")
        E = int(input("请选择一个喜欢的值："))
        while (True):
            if E not in listOfE:
                print("你输入的E不在给出的列表中，请重新输入！\n")
                E = int(input("请选择一个喜欢的值："))
            else:
                break
 
        # 根据E的值在dict_EandD字典中找D的值
        D = dict_EandD.get(E)
 
        # 构建公钥、私钥
        # 公钥：（N，E）
        # 私钥：（N，D）
        publicKey = (N, E)
        privateKey = (N, D)
        return publicKey, privateKey, N, L, E, D
    else:
        print("输入的p，q不是质数！请重新输入")
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：自动获得p、q
param：null
return：p、q
'''
 
 
def autoGetPandQ():
    # 考虑到性能的原因，这里只生成10——100的素数
    primeList = []
    for i in range(10, 100):
        isPrime = True
        for j in range(2, i):
            if i % j == 0:
                isPrime = False
        if isPrime:
            primeList.append(i)
 
    p = random.choice(primeList)
    q = random.choice(primeList)
 
    # 防止出现一样的情况
    while (True):
        if p == q:
            p = random.choice(primeList)
            q = random.choice(primeList)
        else:
            break
    return p, q
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：打印p、q、N、L、publicKey、privateKey、E
param：p、q、N、L、publicKey、privateKey
return：null
'''
 
 
def printParam(publicKey, privateKey, N, L, E, D, p, q):
    print()
    print("p为：", p, " q为：", q)
    print("计算出的N为：", N)
    print("计算出的L为：", L)
    print("你选择的E为：", E)
    print("该E对应的D为：", D)
    print("计算出的公钥为：", publicKey)
    print("计算出的私钥为：", privateKey)
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：对明文进行加密
param：plainText，N，E
return：加密后的密文 cipherText
'''
 
 
def rsaEncode(plainText, N, E):
    cipherText = plainText % N
    for i in range(1, E):
        cipherText = (cipherText * (plainText % N)) % N
    return cipherText
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：对密文进行解密
param：cipherText，N，
return：null
'''
 
 
def rsaDecode(cipherText, N):
    plainText = cipherText % N
    D = int(input("请输入私钥中的D："))
    for i in range(1, D):
        plainText = (plainText * (cipherText % N)) % N
    return plainText
 
 
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
description：RSA算法，进行加解密
param：p，q
return：null
'''
 
 
def rsaMain(p, q):
    publicKey, privateKey, N, L, E, D = getKey(p, q)
    printParam(publicKey, privateKey, N, L, E, D, p, q)
    plainText = int(input("\n加密\n请输入你要加密的明文："))
    cipherText = rsaEncode(plainText, N, E)
    print('你加密后的密文是：', cipherText)
 
    print("\n解密")
    plainText = rsaDecode(cipherText, N)
    print('你所解密的明文是：', plainText)
 
 
''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''
 
 
def main():
    print("*************************************")
    print("*******        RSA算法        ********")
    print("*******  自动生成质数p、q：输入1 ********")
    print("*******  手动输入质数p、q：输入2 ********")
    print("*************************************")
    option = int(input("请输入你要选择的模式："))
 
    while (True):
        if option == 1:
            p, q = autoGetPandQ()
            rsaMain(p, q)
            break
 
        elif option == 2:
            p = int(input("请输入p："))
            q = int(input("请输入q："))
            rsaMain(p, q)
            break
 
        else:
            print("输入有误！请重新输入！")
            option = int(input("请输入你要选择的模式："))
 
 
if __name__ == '__main__':
    try:
        main()
    except ValueError:
        print("输入有误！")

4.2 运行截图

自动生成质数p、q

手动输入质数p、q

5. 写在最后

这里面的代码只能用做理解RSA算法

通用的RSA算法Python版放在这里了：戳我🌹

这个也是我纯手撕的，大家凑合着用🌹

本文完

敬爱与明天🌹