第一步：随机选择两个不相等的质数p和q

第二步：计算p和q的乘积n

n = p * q

第三步：计算n的欧拉函数φ(n)

　φ(n) = (p-1)(q-1)

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

在实际应用中，常常选择65537

第五步：计算e对于φ(n)的模反元素d

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

ed ≡ 1 (mod φ (n))      等价于   ed - 1 = kφ(n)

找模反元素d实际上是对下面这个二元一次方程求解

ex + φ(n)y = 1

第六步：将n和e封装成公钥，n和d封装成私钥

第七步：加密和解密

加密要用公钥(n,e)

加密信息m必须是整数(字符串可以取ASCII值或unicode值)，且m必须小于n

 m^e ≡ c (mod n)

解密要用私钥(n,d)

c^d ≡ m (mod n)

公钥(n,e)只能加密小于n的整数m，那么如果加密大于n的整数，该怎么办？

• 把长信息分割成若干段短信息，每段分别加密
• 先选择一种"对称性加密算法"(比如DES)，用这种算法的密钥加密信息，再用RSA公钥加密DES密钥

RSA算法的可靠性

密钥生成步骤中，一共出现六个数字：

p

q

n        --  n的长度(二进制长度)就是密钥长度

φ(n)   

e

d

这六个数字之中，公钥用到了两个(n和e)，其余四个数字都是不公开的。其中最关键的是d，因为n和d组成了私钥，一旦d泄露，就等于私钥泄露

 

是否可以在已知n和e的情况下，推导出d？

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

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

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

结论：如果n可以被因数分解，d就可以算出，也就意味着私钥被破解，但大整数的因素分解，是一件非常困难的事情。目前，除了暴力破解，还没有发现别的有效方法。所以，只要密钥长度足够长，用RSA加密的信息实际上是不能被破解的

案例：

参与湖北省“奇安信杯”网络安全大赛中所遇到的一道Cropto题。

题目：

p+q:

326429100407681651814978442415826213864753565034919374282004148849764531414964129530662174521568050093736341197400405816551402307458686750141836996345723514698979514133066389538988520826440776264241138888155090851605191090286605183976443204444854546781116840786281855819689375353337207819361769484061133586660

(p+1)(q+1):

26601616557971867831128918184476970808722471200861600741488181559976427915212193001812160532906370924454473038671991616741424706794741682437728013348910646937734672343325523407437596920797247711273378236903138971315823251358525257853681659038646150834388504990678755552658405772625078429891153401221091704935464031276762725209220275197422069811202440482709667987828399235771854454331605660739185369563297937712412914621262089799368586352843414856752338979163598254668715003106493342377951882955338211218066635494610164992383277776336257215001515405312235576928828485922034700150519853591032361405975195251746299510720

c:

24831377919906161196266552704492935537768087456188711284519872226691826290351027606307936414989585764319104737516021733938210516424254235349369088344349700976416957839221585194510124601438798302079231278339823353520868327987552051471031155633165987892206927171527428590536203275545528900845222038924459888879261986663709510987273937159905675940592632023428129764650249246182611973968609631056274792336171105433760493214971141615401120748113420469659787315651721605227003326305005720436114240966565179896456348773794946970503274768701856591123183247406604013805700201562056023223765073732621940021232679124486597812994

e:

65537

python代码

import libnum
a = 26601616557971867831128918184476970808722471200861600741488181559976427915212193001812160532906370924454473038671991616741424706794741682437728013348910646937734672343325523407437596920797247711273378236903138971315823251358525257853681659038646150834388504990678755552658405772625078429891153401221091704935464031276762725209220275197422069811202440482709667987828399235771854454331605660739185369563297937712412914621262089799368586352843414856752338979163598254668715003106493342377951882955338211218066635494610164992383277776336257215001515405312235576928828485922034700150519853591032361405975195251746299510720
b = 326429100407681651814978442415826213864753565034919374282004148849764531414964129530662174521568050093736341197400405816551402307458686750141836996345723514698979514133066389538988520826440776264241138888155090851605191090286605183976443204444854546781116840786281855819689375353337207819361769484061133586660
c = 24831377919906161196266552704492935537768087456188711284519872226691826290351027606307936414989585764319104737516021733938210516424254235349369088344349700976416957839221585194510124601438798302079231278339823353520868327987552051471031155633165987892206927171527428590536203275545528900845222038924459888879261986663709510987273937159905675940592632023428129764650249246182611973968609631056274792336171105433760493214971141615401120748113420469659787315651721605227003326305005720436114240966565179896456348773794946970503274768701856591123183247406604013805700201562056023223765073732621940021232679124486597812994
e = 65537

n = a - b -1
phi_n = n - b + 1
d = libnum.invmod(e,phi_n)
m = pow(c,d,n)
print(m)
print(libnum.n2s(int(m)).decode())

结果为：flag{e2df5b739abba07ae93403d3915228c9}

扩展：

libnum库常用的方法

数字型(不论是十六进制还是十进制)与字符串之间的转换

libnum.s2n(s)

libnum.n2s(n)   不用在意十六进制的位数是否为偶数

二进制与字符串之间的转换

libnum.b2s(b)

libnum.s2b(s)

数字转二进制

s2b(n2s(n))

质数&因数分解

生成质数    libnum.generate_prime(1024)

因数分解    libnum.factorize(1024)