1977年，三位数学家Rivest、Shamir 和Adleman 设计了一种算法，可以实现非对称加密。 这种算法用他们三个人的名字命名，叫做RSA算法。 从那时直到现在，RSA算法一直是最广为使用的”非对称加密算法”。 毫不夸张地说，只要有计算机网络的地方，就有RSA算法。

通俗点来表示

（1）乙方生成两把密钥（分为公钥和私钥），公钥为公开，私钥为保密。

（2）甲方获取到乙方的公钥，然后用公钥对信息（或者密文）进行加密。

（3）乙方得到加密后的信息（或者密文），用私钥进行解密。

一点点基础知识

1.来看看啥叫互质

互质关系是指两个或多个整数的最大公约数（GCD）为1，也称为互素或互质。两个整数如果没有除了1以外的公共因子，就被认为是互质的。

更具体地说，两个整数a和b是互质的，当且仅当它们的最大公约数（GCD）等于1，即GCD(a, b) = 1。如果有更多的整数，它们两两之间的最大公约数也都是1，那么它们被称为互质的。

例如，3和4是互质的，因为它们的最大公约数是1。相反，6和8不是互质的，因为它们的最大公约数是2。

2.再浅浅了解一下欧拉函数

欧拉函数（Euler’s totient function），也称为欧拉φ函数，用符号φ(n)表示，是一个与正整数n相关的数论函数。它表示小于或等于n的正整数中与n互质的数的个数（即与n没有共同因子的正整数的个数）。

例如，如果n是一个质数p，那么φ(p) = p – 1，因为质数与小于它的所有正整数都互质

3.模反元素

模反元素是指在模n的剩余类环中，对于某个整数a，存在整数b，使得ab≡1(modn)。

具体地说，如果 a 和 n 互质（它们的最大公约数为1），那么 b 称为 a 在模 n 意义下的模反元素。这意味着 ab 除以 n 得到的余数是1。

RSA算法步骤

1.首先我们要选取随机的两个质数p和q

2.计算一下p和q的乘积n

3.计算一下n的欧拉函数φ(n)

4.选取一个整数e，选取条件是1<e<φ(n),且e与φ(n)属于互质关系

5.计算e对于φ(n)的模反元素d

6.（e,n）为公钥 （d,n）为私钥

详细地来一遍RSA算法步骤

1，找出两个质数p和q

2.计算一下模数n ,n=p*q

3.计算一下n的欧拉函数φ(n)=（p-1）*（q-1）

4.计算公钥e 1<e<φ(n) ,(e的选取必须是整数且要和φ(n)是互质关系)

5.计算私钥d ed≡1(modφ(n))

6.加密过程 c=m^e mod n (c:密文 m：明文)

7.解密过程 m=c^d mod n

8注意：对外我们只暴露公钥（e,n）

来个很基础的例子演示一下吧

加密脚本

from Crypto.Util.number import *   #一个PY库想了解的话，百度看看吧

flag = b's3c{****************}'

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = 65537
c = pow(m,e,n)

print(f'c={c}')
print(f'q={q}')
print(f'n={n}')
print(f'p={p}')
print(f'e={e}')

# c=46030330606351313679237114285721531342330698737206129010918703498036417363454721760675334417822813724947875885929865486640329529716252321446244266071200078823149116404677646458239272424560465180337457859672108100552653744795449474797243422096682087683554195422675518709366945696571615366228054360058451341054
# q=7965227663824219708743575468258640364696652243262957308654284717055397571531875420402619622428310098741643228099521253208582008419274022052468521224569343
# n=60008666058637405918952131176677873070320281927746447186392639268538075633487600005379831632758975273175964544048523856550422863761611257579516461065425271587899339665881592025582912153375128745483282598165569624298855905060380649111435489744574433730982527224290858629704876098051961725018990469298084805711
# p=7533829363243383703326029192398256407675823363405576878158093652796081584827741540624690983087353431727274308394834209166471294116695013700935035662624177
# e=65537

解密脚本

from Crypto.Util.number import long_to_bytes, inverse

c = 46030330606351313679237114285721531342330698737206129010918703498036417363454721760675334417822813724947875885929865486640329529716252321446244266071200078823149116404677646458239272424560465180337457859672108100552653744795449474797243422096682087683554195422675518709366945696571615366228054360058451341054
q = 7965227663824219708743575468258640364696652243262957308654284717055397571531875420402619622428310098741643228099521253208582008419274022052468521224569343
n = 60008666058637405918952131176677873070320281927746447186392639268538075633487600005379831632758975273175964544048523856550422863761611257579516461065425271587899339665881592025582912153375128745483282598165569624298855905060380649111435489744574433730982527224290858629704876098051961725018990469298084805711
p = 7533829363243383703326029192398256407675823363405576878158093652796081584827741540624690983087353431727274308394834209166471294116695013700935035662624177
e = 65537

phi = (p - 1) * (q - 1)
d = inverse(e, phi)#（inverse(e, phi) 函数的目的是找到一个整数 d，使得 e⋅d≡1 (mod ϕn)这就是 d 作为 e 在模数 phi 下的模反元素。

plaintext = pow(c, d, n)
flag = long_to_bytes(plaintext)
print(flag)