RSA加密解密过程

为了这道题把好几年前学的东西重新看了一遍，累觉不爱。。。

不清楚你了不了解RSA过程，先跟说一下吧

随机产生两个大素数p和q作为密钥对。此题：p=13,q=17,n =p*q=221

随机产生一个加密密钥e,使e 和(p-1)*(q-1)互素。此题：e=83

公钥就是（n,e）。此题：（221,83）

通过e*d mod (p-1)*(q-1)=1生成解密密钥d, ,n与d也要互素。此题：（d*83）≡1mod192

私钥就是（n,d）。此题：（221,155）

之后发送者用公钥加密明文M，得到密文C=M^e mod n

接受者利用私钥解密M=C^d mod n

求解d呢，就是求逆元，de = 1 mod n这种形式就称de于模数n说互逆元，可以看成de-ny=1，此题83e-192y=1.

用扩展的欧几里得算法。其实就是辗转相除

此题：

192=2*83+26

83=3*26+5

26=5*5+1

求到余数为1了，就往回写

1=26-5*5

=26-5*（83-3*26）

=（192-2*83）-5*（83-3*（192-2*83））

=16*192-37*83

则d=-37，取正后就是155.

记住，往回写的时候数不该换的一定不要换，比如第二步中的26,一定不能换成(83-5)/3，那样就求不出来了，最终一定要是192和83相关联的表达式。还有，最好保持好的书写格式，比如第一步2*83+26时第二步最好写成3*26+5而不是26*3+5，要不步骤比较多的话容易乱

p 和 q：两个大的质数，是另一个参数N的的两个因子。

N：大整数，可以称之为模数

e 和 d：互为无反数的两个指数

c 和 m：密文和明文

(N, e)：公钥

(N, d)：私钥

pow(x, y, z)：效果等效pow(x, y)1 % z， 先计算x的y次方，如果存在另一个参数z，需要再对结果进行取模。

密钥长度：n以二进制表示的的位数，例如密钥长度为512代表n用二进制表示的长度为512bit。

对于RSA加密算法，公钥(N, e)为公钥，可以任意公开，破解RSA最直接（亦或是暴力）的方法就是分解整数N，然后计算欧拉函数φ(n)=(p-1) * (q-1),再通过d * e ≡ 1 mod φ(N)，即可计算出 d，然后就可以使用私钥(N, d)通过m = pow(c,d,N)解密明文。

直接分解模数N是最直接的攻击方法，也是最困难的方法。具体的解析同上RSA安全性分析。

如果n小于256bit，可以使用本地工具进行暴力分解，例如windwods平台的RSATool，可以在数分钟之内完成256bit的n的分解。

如果n大于768bit，可以尝试利用在线网站 http://factordb.com ， 这一类在线网站的原理是储存了部分n分解成功的的值。

题目链接： http://ctf5.shiyanbar.com/crypto/RSAROLL.txt

分解N可以通过在线网站 http://www.factordb.com/index.php

分解920139713可以得到p和q的值为18443和49891，现在已知p、q、e以及c，可以通过前三个参数求出d

安装gmpy2可以参考 https://blog.csdn.net/wanzt123/article/details/71036184

到目前为止，已经求出p,q,e,d,n,c，然后可以求出相应的明文M，

适用于：使用相同的模数 N 、不同的私钥，加密同一明文消息

假如采用两个或者两个以上的公钥(N,e)来加密同一条信息，可以得到下面的结论：

分别拿对应的私钥来加密，可以得到相同的明文m

假设攻击者已知n,e1,e2,c1,c2，即可可以得到明文m，因为e1和e2互质，所以使用欧几里得算法（用于计算两个整数a,b的最大公约数）可以找到能够满足以下条件的x，y：

假设x为负数，需再使用欧几里得算法来计算

则可以得到

如果p<n，则p可以被计算出来。

地址： https://www.ichunqiu.com/battalion?q=2451

RSA小指数e攻击

如果RSA系统的公钥e选取较小的值，可以使得加密和验证签名的速度有所提高，但是如果e的选取太小，就容易受到攻击。

有三个分别使用不同的模数n1,n2,n3，但是都选取e=3，加密同一个明文可以得到：

一般情况下，n1,n2,n3互素，否则会比较容易求出公因子，从而安全性大幅度的减低。

RSA选择密文攻击

在此种攻击模型中，攻击者需要掌握的内容包括：加密算法、截获的部分密文、自己选择的密文消息以及相应的被解密的明文。

利用公约数

思路

如果两次加密的n1和n2具有相同的素因子，可以利用欧几里德算法直接分解n1和n2.

通过欧几里德算法计算出两个n的最大公约数p：

识别

识别此类题目，通常会发现题目给了若干个n，均不相同，并且都是2048bit，4096bit级别，无法正面硬杠，并且明文都没什么联系，e也一般取65537。

例题

直接分解成功。而欧几里得算法的时间复杂度为：O(log n)。这个时间复杂度即便是4096 bit也是秒破级别

根据欧几里德算法算出的p之后，再用n除以p即可求出q，由此可以得到的参数有p、q、n、e，再使用常规方法计算出d，即可破解密文。

Fermat方法与Pollard rho方法

针对大整数的分解有很多种算法，性能上各有优异。

在p，q的取值差异过大，或者p，q的取值过于相近的时候，Format方法与Pollard rho方法都可以很快将n分解成功。

此类分解方法有一个开源项目yafu将其自动化实现了，不论n的大小，只要p和q存在相差过大或者过近时，都可以通过yafu很快地分解成功。yafu也有linux版本，但是我这存在一些问题装不上，能解决这个问题的大佬可以私信。

识别

不能直接分解n，不能使用公约数分解n，可以尝试yafu。

低加密指数攻击

在RSA中的e被称为加密指数。由于e的选择只需要满足以下条件即可

计算欧拉函数 φ = (p-1) * (q-1)，然后选择一个e(1<e<φ)，并且e和φ互质

选择小的e可以缩短加密时间，但是选择的e不当，可能会造成严重的安全问题。

e=3的小明文攻击

当e=3，并且明文过小时，导致明文的三次方仍然小于n，通过直接对密文三次开方，即可得到明文。

原理如下

对明文m进行加密：c = pow(m, 3, N),可以得到密文c。

因为n >pow(m, 3)，所以c = pow(m, 3, N) = pow(m, 3)，故对密文三次开方，即可得到明文。

有一种特殊的情况是：pow(m, 3) >n，但是不是足够，假设存在这样的k，有下列的公式成立：

爆破k，当且仅当c - (k * n)可以开三次方，c - (k * n)开三次方结果就是明文m。

识别

当e=3时，优先使用这种方法解密。

RSA是目前使用最为广泛的公钥密码算法，公钥加密也称为非对称加密，与对称加密的最大区别在于加密与解密使用不同的密钥。

在RSA中，明文、密文和密钥都是数字，假设公钥用二元组(E,N)来表示，私钥用(D,N)来表示，其中E、D、N都是数字，那么加解密过程可表示如下：

可见，在RSA中，不论加密还是解密，都可归结为求x的y次幂对m取余问题。

生成RSA密钥可分成以下4步：

首先准备两个很大的质数p和q，那么N = p * q。

L = lcm(p-1, q-1)

由于存在恒等式gcd(a,b) * lcm(a,b) = a * b，求lcm可转换为求gcd，而求gcd可通过欧几里德算法在对数时间内算出。

E是一个比1大、比L小的数，且满足E与L互质，即有：gcd(E,L)=1, 1 <E <L。gcd(E,L)=1是为了保证后面要求的数字D一定存在。

可不断地生成[2,L-1]之间的随机数作为E的候选数，检查是否满足条件，直到找出符合要求的E为止。

至此，E和N都已求出，那么公钥(E,N)也就得到了。

数D是由数E计算得到的，D、E和L之间满足关系：E * D mod L = 1, 1 <D <L。

只要D满足上述条件，那么通过E与N加密的内容，就可通过D和N进行解密。

求D也可采用类似求E的方法，不断产生随机数去试，直到找出满足条件的D为止，这样私钥(D,N)也准备好了。

为方面说明，这里用较小的数计算。先准备两个质数，例如，p=17, q=19，那么N=17*19=323，L=lcd(16,18)=144。

满足gcd(E,L)=1的数很多，例如5,7,11,13,25等，这里取E=5。

满足E*D mod L = 1的数也很多，这里取D=29。

到这里，公私钥都有了，公钥为(5,323)，私钥为(29,323)，公钥可任意公开，私钥则保密。

明文必须是小于N的数，因为加密运算中要求mod N。假设明文是123，用公钥(5,323)对其加密：

再用私钥(29,323)对密文225进行解密：

解出的明文与原始明文一致。

---