RSA算法详解及攻击原理分析-附攻击范例

RSA算法

1、算法背景

1.1 公钥密码

​ 在公钥密码系统中，加密和解密使用的是不同的**，这两个**之间存在着相互依存关系：即用其中任一个**加密的信息只能用另一个**进行解密。这使得通信双方无需事先交换**就可进行保密通信。其中加***和算法是对外公开的，人人都可以通过这个**加密文件然后发给收信者，这个加***又称为公钥；而收信者收到加密文件后,它可以使用他的解***解密，这个**是由他自己私人掌管的，并不需要分发，因此又成称为私钥，这就解决了**分发的问题。

1.2 公钥*数学基础

​ 由于传统***出现了困难，例如2000个用户保密通信每个人需要保存1999个**（两两保密通信需要共（2000*19999）/2 = 1999000个**，每人保管1999个），在**管理分配上有困难。另外由于数字签名（身份认证）的需求增加，这么大的**管理量级使得传统***不太方便。

​ 公钥*解决了上述主要的两个问题，即每个人有一对**（公钥和私钥），将公钥公开，私钥自己保管，这样每人只要保管好自己的私钥就可以了。通信时使用收信方的公钥进行加密，收信方使用私钥进行解密。在身份认证时，签名者使用私钥签名，验证签名者使用签名者的公钥验签。当然在实际应用时还有其他的问题需要保证，例如抗抵赖，保持信息的完整性等密码学问题。在本文中先不考虑。

​ 有上述公钥*的任务中我们知道，区别于其他***算法，公钥算法需要做到的是将加***（公钥）和加密算法公开，破坏者也不能由公钥和密文破译出明文。只有使用解***（私钥）和解密算法才能解出明文。而且保证通过公钥不能推出私钥。

​ 上述内容可以通过所谓的“单向函数”来实现。（传统的***中加密算法和解密算法是互逆的。）所谓“单向函数”是指加密函数E和解密函数D。但是已知加密函数E推导其逆运算却非常困难（也就是推导私钥的过程）。所以若不知道解密函数（或私钥）不可能解出明文。

​ 单向函数的实现依赖的是大整数因子分解的难度，根据算数基本定理：任何大于1的整数都可以分解成素数乘积的形式，并且，如果不计分解式中素数的次序，该分解式是唯一的。

​ 这个定理在理论上十分漂亮，但是操作起来却非常困难下表列出了现代最快的分解算法在大型计算机上分解一个大数所用的时间。

1.3 公钥通信的流程

发送方Alice，接收者Bob

1. Bob生成**对，私钥自己来妥善保管

2. Bob将自己的公钥发送给Alice

3. Alice用Bob给的公钥加密需要发送给Bob的信息

4. Alice将加密的密文发送给Bob

5. Bob用自己私钥解密密文

其中那片攻击者在中间截获了Bob发送给Alice的公钥，也为无法通过公钥对Alice加密后的密文进行解密，从而实现安全传输。

---

2、RSA算法数学基础

​ 1977年，三位数学家Rivest、Shamir 和 Adleman 设计了一种算法，可以实现非对称加密。这种算法用他们三个人的名字命名，叫做RSA算法。从那时直到现在，RSA算法一直是最广为使用的"非对称加密算法"。RSA算法是第一个能同时用于加密和数字签名的算法，也易于理解和操作。RSA是被研究得最广泛的公钥算法，从提出到现今的几十多年里，经历了各种攻击的考验，至今仍然应用广泛。

2.1 RSA相关的数论基础

1. 一个大于1的整数p，若除1和起本身之外没有其他正整数因数（约数），称P为素数。

2. 若整数a和b最大公约数为1，则称a，b互素，记为（gcd（a，b）= 1）。

3. 设n为正整数，a和b为整数，若a和b被n除后所得余数相同，称a和b模n同余，记为a≡b（mod n）。此式被称为同余式。若n能整除a则同余式表示为a≡0（mod n）。

   两个整数模n同余的等价说法有：a和b被n除余数相同。a-b被n整除。a和b在模n的同一个剩余类中。存在整数s使得a=sn+b。

4. 同余式的一些运算性质，

   （1） 若$a≡b（mod\ n）$a≡b（mod n），$c≡d（mod\ n）$c≡d（mod n）则有$ac≡bd（mod\ n）$ac≡bd（mod n）。特别的有，$ka≡kb（mod n）$ka≡kb（modn），k为任意整数。

   （2） 若$a≡b（mod\ n）$a≡b（mod n），d是a，b，n的公因数，则$(a/d) ≡(b/d)（mod \frac{n}{d}）$(a/d)≡(b/d)（moddn​）。特别的有$a^n≡b^n（mod\ n）$an≡bn（mod n），n为正整数。

   （3） 若$ka≡kb（mod\ n）$ka≡kb（mod n），且k与n互素时，有$a≡b（mod\ n）$a≡b（mod n）。（同余式消去律）

5. 设n为正整数 ,则任何一个整数被n除 ,余数必为0,1,2,…,n-1中的某一个,把整数集中被n除余数相同的数分别归为一类,记为[0],[1],[2]…,[n-1],这样就按模是否同余把整数集分成n类,其中每一类都称为模n的一个剩余类。显然,每个整数必属于上述类中的一类,被n除余数不同的数必属于上述的不同类中。若a0,a1,a3…,an-1分别取自上述类的不同类中,称a0,a1,a3…,an-1为模n的一个完全剩余系,该剩余系中的数两两模n不同余。

6. 含有未知量的同余式称为同余方程。一次同余方程是最简单的一种,其一般形式为ax≡b（mod n）。若a，n的最大公约数d能整除b，则$ax≡b（mod n）$ax≡b（modn）有解。且恰有d个解。若a，n的最大公约数d不能能整除b，则$ax≡b（mod n）$ax≡b（modn）无解。例如同余方程$7x≡1（mod\ 5）$7x≡1（mod 5）。
   一般地 解同余方程的步骤为 ①判断解的情况 ②当同余方程的a，b，n有公因数时 ,约去公因数化简方程 ③利用同余的定义和消去律求方程的解。

7. 模运算极其性质：

基本理论:

给定一个正整数p，任意一个整数n，一定存在等式 $n = kp + r $；

其中k、r是整数，且 $0 ≤ r < p$0≤r<p，称呼k为n除以p的商，r为n除以p的余数。

对于正整数p和整数a,b，定义如下运算：

取模运算：$a \% p（或a\ mod\ p）$a%p（或a mod p），表示a除以p的余数。

模p加法：$(a + b) \% p$(a+b)%p ，其结果是a+b算术和除以p的余数，也就是说，$(a+b) = kp +r$(a+b)=kp+r，则$(a + b) \% p = r$(a+b)%p=r。

模p减法：$(a-b) \% p$(a−b)%p ，其结果是a-b算术差除以p的余数。

模p乘法：$(a * b) \% p$(a∗b)%p，其结果是 a * b算术乘法除以p的余数。

说明：
1. 同余式：正整数a，b对p取模，它们的余数相同，记做 a ≡ b % p或者a ≡ b (mod p)。
2. n % p得到结果的正负由被除数n决定,与p无关。例如：7%4 = 3， -7%4 = -3， 7%-4 = 3， -7%-4 = -3。

​ 基本性质:

（1）若$p|(a-b)$p∣(a−b)，则$a≡b (\% p)$a≡b(%p)。例如 $11 ≡ 4 (\% 7)$11≡4(%7)， $18 ≡ 4(\% 7)$18≡4(%7)

（2）$(a \% p)=(b \% p)意味a≡b (\% p)$(a%p)=(b%p)意味a≡b(%p)

（3）对称性：$a≡b (\% p)等价于b≡a (\% p)$a≡b(%p)等价于b≡a(%p)

（4）传递性：若$a≡b (\% p)$a≡b(%p)且$b≡c (\% p)$b≡c(%p) ，则$a≡c (\% p)$a≡c(%p)

​ 运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

$(a + b) \% p = (a \% p + b \% p) \% p （1）$(a+b)%p=(a%p+b%p)%p（1）

$(a - b) \% p = (a \% p - b \% p) \% p （2）$(a−b)%p=(a%p−b%p)%p（2）

$(a * b) \% p = (a \% p * b \% p) \% p （3）$(a∗b)%p=(a%p∗b%p)%p（3）

$(a^b) \% p = ((a \% p)^b) \% p （4）$(ab)%p=((a%p)b)%p（4）

结合率： $((a+b) \% p + c) \% p = (a + (b+c) \% p) \% p （5）$((a+b)%p+c)%p=(a+(b+c)%p)%p（5）

$((a*b) \% p * c)\% p = (a * (b*c) \% p) \% p （6）$((a∗b)%p∗c)%p=(a∗(b∗c)%p)%p（6）

交换率： $(a + b)\% p = (b+a) \% p （7）$(a+b)%p=(b+a)%p（7）

​ $(a * b) \% p = (b * a) \% p （8）$(a∗b)%p=(b∗a)%p（8）

分配率： $((a +b)\% p * c) \% p = ((a * c) \% p + (b * c) \% p) \% p （9）$((a+b)%p∗c)%p=((a∗c)%p+(b∗c)%p)%p（9）

​ 重要定理

若$a≡b (\% p)$a≡b(%p)，则对于任意的c，都有$ (a + c) ≡ (b + c) (%p)；（10）$

若$a≡b (\% p)$a≡b(%p)，则对于任意的c，都有$(a * c) ≡ (b * c) (\%p)；（11）$(a∗c)≡(b∗c)(%p)；（11）

若$a≡b (\% p)，c≡d (\% p)$a≡b(%p)，c≡d(%p)，则$(a + c) ≡ (b + d) (\%p)$(a+c)≡(b+d)(%p),$(a - c) ≡ (b - d)(\%p)$(a−c)≡(b−d)(%p)，

$(a * c) ≡ (b * d) (\%p)$(a∗c)≡(b∗d)(%p)，$(\frac{a}{c}) ≡ (\frac{b}{d} )\%p； （12）$(ca​)≡(db​)%p；（12）

若a≡b (% p)，则对于任意的c，都有ac≡ bc (%p)； （13）

2.2 欧拉定理及推广

欧拉函数的作用：

1.求出小于n且与n互素的整数的数目

2.集合$Z^*_n$Zn∗​（小于n且与n互素）集合中的元素的个数。（通过计算$\phi(n)$ϕ(n)）

$\phi(n)$ϕ(n)计算方式：

(1)$\phi(1)=0$ϕ(1)=0

(2)如果p是素数，则$\phi(p)=p-1$ϕ(p)=p−1

(3)如果m和n互素，则$\phi(m\times n)=\phi(m)\times \phi(n)$ϕ(m×n)=ϕ(m)×ϕ(n)

(4)如果p是一个素数，则$\phi(p^e)=p^e-p^{e-1}$ϕ(pe)=pe−pe−1

欧拉定理：若n,a为正整数，且n,a互质，(a,n) = 1，则$a^{φ(n)} ≡ 1 (mod\ n)$aφ(n)≡1(mod n)。

证明：在1到n的数中，与n互质的一共有φ(n)个，令这φ(n)个数为集合X，即为x1,x2……xφ(n)。
又不妨令集合M中每个元素符合从集合X道M的对应关系：
m1=a∗x1
m2=a∗x2
……
mφ(n)=a∗xφ(n)

其次先证明M中任何两个数都模n都不同余：
反证法，假设先令ma-mb=n*k
则a∗xa−a∗xb=n∗k
已知a与n互质
则上式需满足：xa−xb≡0（mod n)
又xa、xb都小于n，且不相等，所以上式不成立，假设不成立
所以M中任意两个数都模n不成立

又由于算数基本定理易证：由a与n互质，xi与n互质，所以可得mi与n互质。
由此：
m1∗m2∗……∗mφ(n)≡x1∗x2∗……∗xφ(n)(mod n)
把mi替换成x的形式
a∗x1∗a∗x2∗……∗a∗xφ(n)≡x1∗x2∗……∗xφ(n)(modn)
整理合并
a^(φ(n)−1)∗(x1∗x2……∗xφ(n)≡0(modn)
得到
a^φ(n)≡1(modn)

费马小定理：设任意整数a和素数p互素，则$a^{p-1} ≡1（mod\ p）$ap−1≡1（mod p）。

证明：费马小定理的证明依据欧拉定理很容易得到
a与p互素，所以φ(p)=p-1
带入欧拉定理即可得到结论

3、 RSA算法构造及验证

3.1 RSA算法

RSA加密算法为：
(1) 取两个大素数p,q (保密)；
(2) 计算 n=pq (公开), φ(n)=(p-1)(q-1) (保密)；
(3) 随机选取整数e，满足 $ gcd(e, φ(n))=1 $ （e与φ(n)互素）(公开)；
(4) 计算 d 满足$ d*e≡1 (mod φ(n)) $(保密)； (5) ｛e，n｝为公钥，｛d，n｝为私钥，也可以用｛e，d｝表示**对 (6) 加密时$(保密)；(5)｛e，n｝为公钥，｛d，n｝为私钥，也可以用｛e，d｝表示密钥对(6)加密时c = x^e mod\ n$ ；解密时$ x = c^d mod\ n$
(7) 签名时$c = x^d mod\ n$c=xdmod n ；解密时$ x = c^e mod\ n$

3.2 RSA算法完备性证明

3.2.1 证明方法一

定理：设p，q是不同的素数，n=pq记$φ(n)=(p-1)(q-1)$φ(n)=(p−1)(q−1),如果e，d是与φ(n)互素的两个正整数（e,d<φ(n)),并满足$e^d≡1(mod\ φ(n))$ed≡1(mod φ(n)),则对于每个整数x,都有$x^{ed}≡x(mod\ n)$xed≡x(mod n)。

​ 分析：为了证明$x^{ed}≡x(mod\ n)$xed≡x(mod n)，又因为n=pq，而p，q都是素数,故只要证明φ(n)是$x^{ed}-x$xed−x的因数即可。

$x^{ed}≡x(mod\ p) （1）$xed≡x(mod p)（1）

$x^{ed}≡x(mod\ q) （2）$xed≡x(mod q)（2）

证明：证明式1，若p是x的因数则式1必然成立
若p不是x的因数，则由$ed≡1(mod\ φ(n))$ed≡1(mod φ(n))得$ed-1=k(p-1)(q-1)$ed−1=k(p−1)(q−1),k为任意整数。则$x^{ed}=x^{k(p-1)(q-1)+1} = x*（x^{p-1}）^{k(q-1)}$xed=xk(p−1)(q−1)+1=x∗（xp−1）k(q−1)

根据费马小定理因为x与p互素所以$x^{p-1}≡1（mod p）$xp−1≡1（modp）
所以$x^{ed}≡x*（1）^{k(q-1)} ≡x（mod\ p）$xed≡x∗（1）k(q−1)≡x（mod p）
同理可证$x^{ed}≡x(mod\ q)$xed≡x(mod q)

3.2.2 证明方法二

从另一个角度解释为什么RSA加密和解密过程是互逆的：
将问题改为证明：$A^e mod\ n = B^{e*d}mod\ n$Aemod n=Be∗dmod n
即$B^{(e*d)}mod\ n = B$B(e∗d)mod n=B
其中A为密文，B为明文。
证明：因为$ed+1=（p-1）（q-1）$ed+1=（p−1）（q−1）所以$B^{e*d}=B^{k(p-1)(q-1)+1}$Be∗d=Bk(p−1)(q−1)+1,
当B与n互素时，根据欧拉定理有:
$B^{k(p-1)(q-1)+1} mod\ n$Bk(p−1)(q−1)+1mod n
$= B*B^{k(p-1)(q-1)} mod\ n$=B∗Bk(p−1)(q−1)mod n
$= (B mod\ n )*((B^{(p-1)(q-1)})^k mod\ n)$=(Bmod n)∗((B(p−1)(q−1))kmod n)
$= (B mod\ n ) * (((B^{(p-1)(q-1)} mod\ n) ^ k ) mod n)$=(Bmod n)∗(((B(p−1)(q−1)mod n)k)modn)
$= B * (1^k mod\ n)$=B∗(1kmod n)
$=B$=B
当B与n不互素时，由于n=pq，B必然能被p或者q整除，假设B=kp ,则B与q互素。再运用费马定理有：
$B^{q-1} = 1 mod\ q$Bq−1=1mod q，
则$（B^{q-1}）^{p-1}K = 1^{p-1}K mod q = 1 mod\ q$（Bq−1）p−1K=1p−1Kmodq=1mod q,
即$B^{k(p-1)(q-1)} mod\ q =1$Bk(p−1)(q−1)mod q=1。
两边同时乘以B，得到
$B^{k(p-1)(q-1)+1} mod\ q = B$Bk(p−1)(q−1)+1mod q=B
也就是$B^{e*d}mod\ n = B$Be∗dmod n=B

4、安全分析

---

​ RSA遭受攻击的很多情况是因为算法实现的一些细节上的漏洞所导致的,所以在使用RSA算法构造密码系统时，为保证安全，在生成大素数的基础上，还必须认真仔细选择参数，防止漏洞的形成。根据RSA加解密过程，其主要参数有三个:模数N，加***e，解***d。现在我们针对这三个参数进行分析，确定如果需要一个安全的RSA加密过程，我们的参数应该如何选择？以下给出RSA加解密中的安全性汾西以及参数选取原则。

4.1 模数N的选取原则

​ 一般认为RSA系统的安全性等同于大整数分解问题，即若能分解因子N，则可以攻破RSA密码系统。所以参数N的选择对于RSA系统的安全性具有十分重要的意义，在RSA中模数N的值由大素数p和q相乘所得，即$n=p\times q$n=p×q，如果可以攻击者可以分解N得到p和q那么就可以计算出$\varphi(N)=(p-1)*(q-1)$φ(N)=(p−1)∗(q−1)从而可以通过公开的e通过$ed\equiv 1(mod\varphi(N))$ed≡1(modφ(N))解***d。所以RSA系统中参数模数N的选择确定对RSA的安全性密切相关。一般，模数N的确定可以遵循以下原则：

​ (1)p和q之差要大

​ 当p和q相差很小的时候，在已知N的情况下，可以假定二者的平均值计算公式为
$\frac{p+q}{2}=\sqrt{a}$2p+q​=a​
​ 然后利用下式：
${(\frac{p+q}{2})}^2 - N={(\frac{p-q}{2})}^2$(2p+q​)2−N=(2p−q​)2
​ 在$(\frac{p+q}{2})^2$(2p+q​)2可开放的情况下可以解出$\frac{p+q}{2}$2p+q​和$\frac{p-q}{2}$2p−q​,即我们达到了使N被分解的效果。

​ (2)p-1和q-1的最大公因子应很小。

​ 当$gcd((p-1),(q-1))$gcd((p−1),(q−1))很大的时候，可以采用迭代方法，对密文$c=m^{e}mod n$c=memodn反复进行e次幂的运算:$c^{e},c^{ee}......$ce,cee......直到出现c的et次幂使之模n为c为止，则c的$e^{t-1}$et−1次幂模n为m。

​ 当t不是很大的时候这种攻击是有效的，由Eluer定理：
$e^{t}=1mod\varphi(n)$et=1modφ(n)
​ 可以推导t的最小值有：
$t=\varphi(\varphi(n))=\varphi((p-1)(q-1))$t=φ(φ(n))=φ((p−1)(q−1))
所以，如果$gcd((p-1),(q-1))$gcd((p−1),(q−1))小的时候，$\varphi(\varphi(n))$φ(φ(n))会很大，所以t就会很大，使得迭代方法攻击RSA加密的效果就会很差，从而保证了加密的安全性。

​ (3)p和q必须是强素数

​ 对于一个素数而言如果其满足：

​ 条件一：存在两个大素数$p_1,p_2$p1​,p2​,使得$p_1|p-1$p1​∣p−1且$p_2|p+1$p2​∣p+1。

​ 条件二：存在四个大素数$r_1,r_2,s_1,s_2$r1​,r2​,s1​,s2​使得$r_1|p_1-1,s_1|p_1+1,r_2|p_2-1,s_2|p_2+1$r1​∣p1​−1,s1​∣p1​+1,r2​∣p2​−1,s2​∣p2​+1。

则此素数称为强素数，其中$r_1,r_2,s_1,s_2$r1​,r2​,s1​,s2​称为三级的素数，$p_1,p_2$p1​,p2​称为二级的素数，$p$p则称为一级的素数。只有两个强素数的积所构成的N，其因子分解是困难数学问题。而如果其不是强素数，那么分解n相对容易，证明如下：

$设a为a_1a_2..a_n的最大值，构造B=p_1^a p_2^a..p_n^a$设a为a1​a2​..an​的最大值，构造B=p1a​p2a​..pna​

$\because p_1^{a_1} p_2^{a_2}..p_n^{a_n} |p_1^a p_2^a..p_n^a$∵p1a1​​p2a2​​..pnan​​∣p1a​p2a​..pna​

$\therefore B=k(p-1)$∴B=k(p−1)

$\because x^B=x^{p-1}$∵xB=xp−1

$若 x \not= kp,则根据费马定理$若x​=kp,则根据费马定理

$即x^B\equiv1mod p$即xB≡1modp

$即x^B=k_1p+1$即xB=k1​p+1

$令x^B\equiv y modn$令xB≡ymodn

$有k_1p+1\equiv y mod pq$有k1​p+1≡ymodpq

$\therefore k_1p \equiv y-1 mod qp$∴k1​p≡y−1modqp

$若k_1p>qp,则k_1p\equiv k_2p mod qp$若k1​p>qp,则k1​p≡k2​pmodqp

$若k_1p>qp,则k_1p\equiv k_1p mod qp$若k1​p>qp,则k1​p≡k1​pmodqp

$有k_1p\equiv kp mod qp$有k1​p≡kpmodqp

$\therefore y-1=kp$∴y−1=kp

$\therefore y=kp+1$∴y=kp+1

$\therefore p=gcd(y-1,n)$∴p=gcd(y−1,n)

$尝试设x=2、3、4...，直到y\not=1,即得到p$尝试设x=2、3、4...，直到y​=1,即得到p

​ (4)p和q因该足够大使得N的因式分解计算上不可能

RSA的安全性依赖于大数的因子分解，若能因子分解模数N，则RSA即被攻破，因此模数N必须足够大直至因子分解N在计算上不可行。因子分解问题为密码学最基本的难题之一，但是随着计算机计算能力的迅速提升，因子分解的速度已有很大的进步，为保证安全性，实际应用中所选择的素数P和q至少应该足够的大，使得计算机对其进行大数因式分解为不可行。

针对模数的攻击可以针对每种特殊的情况进行分析，如果模数不够大可以直接通过模数分解进行攻击；如果p与q的选值之差不大可以通过平均值计算公式进行攻击，还有一种很经典的攻击就是针对多组密文使用同一个模数n加密的情况——共模攻击。

4.1.1 共模攻击

适用情况：多组密文使用同一个模数n加密的情况，不同e之间两两互质

原理：通过欧几里得算法可以知道给定整数e1 与 e2, 必存在有整数 s1与 s2使得$e_1s_1 + e_2s_2 = gcd(a,b)$e1​s1​+e2​s2​=gcd(a,b)。根据扩展欧几里得算法，给定e1，e2，求解出$s_1$s1​，$s_2$s2​，然后根据推导得出的公式计算m

证明：

$贝祖公式：e_1\times s_1+e_2\times s_2=1$贝祖公式：e1​×s1​+e2​×s2​=1

$由于:c_1=m^{e_1}\%n$由于:c1​=me1​%n

$--- c_2=m^{e_2}\%n$−−−c2​=me2​%n

$所以：(c_1^{s_1}\times c_2^{s_2})\%n=((m^{e_1}\%n)^{s_1}\times (m^{e_2}\%n)^{s_2})\%n$所以：(c1s1​​×c2s2​​)%n=((me1​%n)s1​×(me2​%n)s2​)%n

$所以：(c_1^{s_1}\times c_2^{s_2})\%n =(m^{{e_1\times s_1}+{e_2\times s_2}})\%n$所以：(c1s1​​×c2s2​​)%n=(me1​×s1​+e2​×s2​)%n

$因为:e_1\times s_1+e_2\times s_2=1$因为:e1​×s1​+e2​×s2​=1

$所以：c_1^{s_1}\times c_2^{s_2}=m$所以：c1s1​​×c2s2​​=m

由此可以得到明文m。

##欧几里得算法-递归实现
def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a // b) * y)
        return x, y, q

##flag.enc1
71 B3 8B 33 CA D0 F3 BF 34 D7 26 AC AC 37 83 6E
C1 5B 15 9F B7 01 E7 A6 2B 7D 2A CE 5E 05 F3 F8
A3 C3 24 58 D6 9E E7 AB 04 C2 2B 4C AE 08 66 B9
64 C2 16 49 EB B6 B9 57 D0 AE EA FA CF 9D 6A FC
DF 8D F1 C8 64 8B F3 9E B7 52 9E 1C C0 5B E9 0E
A4 D9 BF 14 CA E8 1F 63 84 25 98 90 75 75 E4 44
EC 3F 70 EF AC C0 9F 9D 70 14 81 D9 DB 0D DE 72
2F 49 C2 95 9B 08 7F 37 01 2F ED 3F 99 39 1D B7
33 69 5E F4 E5 10 2E 72 4A 40 EA C0 DC 14 70 D9
23 B5 86 41 D1 F7 DD B1 18 6C 98 AA 15 7F 11 6B
BB 52 FD 3F 34 39 35 F2 E4 7E A5 A5 86 09 06 8C
BE 33 B1 B9 5A EC C7 45 A4 82 0C CE 67 8A 2B 36
AA 03 9A 93 25 CF 96 94 5B C6 F1 69 59 1C FF 6F
3A 54 BE C8 DF 1B 34 17 29 DA 94 89 BC 76 95 F3
DA F4 1A 48 88 C7 AB 9F AE 7A 75 3A 78 F7 89 15
22 CC 95 2B 88 0F ED 4D 1C 40 04 24 F3 12 F4 80
1C FE F4 A7 EB AF 3A BF 5E 2F B2 4B E6 9B ED 69
03 69 4C 3B A5 AA 4B 81 E0 64 00 A2 FB B2 D2 F9
53 83 25 17 6E D1 0F 17 B7 B2 F1 A3 C5 D8 53 57
12 67 81 CB 97 94 84 A9 3A CF 2C 5D 20 DA 22 05
5A 4F FC 8E 17 43 63 04 6D 91 E0 1F CB 5C 7B 4C
38 44 C1 49 4A 2D 96 4E 66 9D 59 EB 2A 6E CD 18
F7 59 14 DE 74 8C A1 82 23 3C 8D 6A 4D A7 C7 E7
61 1A 2F B5 A9 C0 BA 26 B2 8E 6F 5E AE AD DA 4B
B2 CC 5F 41 A7 16 C6 D1 04 36 62 B5 F4 53 05 EB
EC A8 53 A3 03 53 47 D6 59 61 B3 D0 83 75 2D 69
2C B6 F1 48 BF 69 EE AA 4A F5 86 A7 FD 90 90 73
37 7C 51 24 E5 1A 6D 8E 38 84 05 94 EF 5A E3 F6
49 7A 2A 9E C0 6A CC 63 E6 65 C9 6E 76 80 1E 9A
27 1C 59 7E 26 37 01 8A A3 41 EF 9F 32 1B 9B F8
1E C8 43 44 FB CB 04 0B B7 05 D4 B7 13 FE 60 07
E3 0A 88 16 EE AE 56 11 10 B9 5C DA 1C A6 41 81


##flag.enc2
30 06 8A 18 3D 16 35 C7 B0 6C 07 DA 18 A0 A3 9A
33 29 8C 73 4E 3E DB 6C 55 A8 3D D2 3B 62 0C D0
52 AD 5D C0 19 0C 5C 99 8D 76 09 3D 36 32 10 19
8D 55 90 2F 28 5F 74 D4 B0 EE CC 6E 29 6A 86 EF
3D 4F 25 25 A5 12 8E 9C 1A 0D 07 A6 10 C6 52 75
D5 D0 5D CE BE 3A A1 98 91 1F 1E D3 33 61 18 5B
2C D7 B6 AB AA 2A CA 51 29 94 F3 4C F0 29 AF 91
BE A7 F6 4D 48 69 D4 2C 90 AD 98 3C 24 D6 78 70
E5 A4 5E D3 7F 45 FC 4D C2 46 45 75 2F 38 4E 92
86 54 12 7D 1F 1F 83 88 31 A4 2D C4 DF 76 AF 88
A8 8B AC B6 94 5B 22 C4 67 64 C0 31 D3 32 FE A2
3D 8F D9 AD BB BA 23 94 75 9E F4 FD BE FC 60 A2
77 C4 65 FC 11 90 BF D2 95 F7 56 FF 8C 09 6B 6F
35 18 B6 B7 3A 7B DC 02 A1 2B 8A 43 BB A5 89 48
D3 ED 62 81 5B F1 C5 E5 1D 51 B8 22 3F 15 32 EC
D4 26 DF C7 69 BC DB 20 73 86 FE 2D 85 15 F1 AD
B3 55 FE 0F A9 6D 06 85 69 73 C8 0B D3 C0 8C F3
77 93 91 E7 B0 7A 31 61 6D E5 30 09 E9 BD BD 67
69 3A E1 59 9F 6B 4B AE DF 37 0C 45 1F 2D 5C 7F
67 82 A9 2B F9 10 52 4A B5 44 51 20 E7 CD 71 73
31 CE 33 25 36 30 C3 DC A3 BB A9 30 8B A1 54 6B
47 7C FA B1 71 03 BA 43 50 E5 A4 0F 28 12 FD 3F
30 3B 52 18 C9 CA 25 CE 64 AA 51 E7 F2 D0 26 AC
82 78 4F 86 0E 72 37 34 93 56 C7 DC 23 A4 19 FE
0E 21 5E CF D2 4D D5 AE 5E 59 D6 B6 8C A1 71 00
78 91 F9 63 2F 3B 0D 07 58 38 FA 29 54 0A 4F 3A
E8 42 EE D7 CA 92 0F 33 63 30 95 A9 AB 48 96 10
A0 13 1A 10 13 AD 4D 2C CF 00 A8 A6 FB 19 43 A3
92 A4 89 AB 75 07 CF 65 AF FA 31 B4 DB 14 85 1A
E0 11 5F 91 19 F4 FB FC B6 58 7D E8 EE FB B8 86
DD C1 06 C9 5B F6 97 E1 D9 DF 3D AF 89 9F D6 7A
94 29 22 EE 79 AE 5C F4 1F EE 42 F5 0E 53 7E 67

##veryhardRSA.py
#!/usr/bin/env python

import random

N = 0x00b0bee5e3e9e5a7e8d00b493355c618fc8c7d7d03b82e409951c182f398dee3104580e7ba70d383ae5311475656e8a964d380cb157f48c951adfa65db0b122ca40e42fa709189b719a4f0d746e2f6069baf11cebd650f14b93c977352fd13b1eea6d6e1da775502abff89d3a8b3615fd0db49b88a976bc20568489284e181f6f11e270891c8ef80017bad238e363039a458470f1749101bc29949d3a4f4038d463938851579c7525a69984f15b5667f34209b70eb261136947fa123e549dfff00601883afd936fe411e006e4e93d1a00b0fea541bbfc8c5186cb6220503a94b2413110d640c77ea54ba3220fc8f4cc6ce77151e29b3e06578c478bd1bebe04589ef9a197f6f806db8b3ecd826cad24f5324ccdec6e8fead2c2150068602c8dcdc59402ccac9424b790048ccdd9327068095efa010b7f196c74ba8c37b128f9e1411751633f78b7b9e56f71f77a1b4daad3fc54b5e7ef935d9a72fb176759765522b4bbc02e314d5c06b64d5054b7b096c601236e6ccf45b5e611c805d335dbab0c35d226cc208d8ce4736ba39a0354426fae006c7fe52d5267dcfb9c3884f51fddfdf4a9794bcfe0e1557113749e6c8ef421dba263aff68739ce00ed80fd0022ef92d3488f76deb62bdef7bea6026f22a1d25aa2a92d124414a8021fe0c174b9803e6bb5fad75e186a946a17280770f1243f4387446ccceb2222a965cc30b3929L

def pad_even(x):
	return ('', '0')[len(x)%2] + x
e1 = 17
e2 = 65537

fi = open('flag.txt','rb')
fo1 = open('flag.enc1','wb')
fo2 = open('flag.enc2','wb')
data = fi.read()
fi.close()
while (len(data)<512-11):
	data  =  chr(random.randint(0,255))+data
data_num = int(data.encode('hex'),16)
encrypt1 = pow(data_num,e1,N)
encrypt2 = pow(data_num,e2,N)

fo1.write(pad_even(format(encrypt1,'x')).decode('hex'))
fo2.write(pad_even(format(encrypt2,'x')).decode('hex'))

fo1.close()
fo2.close()

##解密脚本
from Crypto.PublicKey import RSA
import gmpy2
from Crypto.Util.number import long_to_bytes
#扩展欧几里得算法
def ext_euclid(a, b):
    if b == 0:
        return 1, 0, a
    else:
        x, y, q = ext_euclid(b, a % b)
        # q = gcd(a, b) = gcd(b, a%b)
        x, y = y, (x - (a // b) * y)
        return x, y, q
n=1#n过长，贴代码超长了，使用的时候用你的N替换
e1=17
e2=65537
flag_encode= open('./flag.enc1','rb').read()
c1=int(flag_encode.hex(),16)
flag_encode= open('./flag.enc2','rb').read()
c2=int(flag_encode.hex(),16)
print("c1:",c1)
print("c2:",c2)
s1=ext_euclid(e1,e2)[0]
s2=ext_euclid(e1,e2)[1]
if s1<0:
    s1=-s1
    c1=gmpy2.invert(c1,n)
if s2<0:
    s2=-s2
    c2=gmpy2.invert(c2,n)
m=long_to_bytes(str(pow(c1,s1,n)*pow(c2,s2,n)%n))
print(m)

4.2 参数e的选取原则

​ 在RSA算法中，e和$\varphi(N)$φ(N)互质的条件比较容易满足，如果我们选择较小的e，那么加密和解密的过程中速度会更快也更容易存储，但是其却会导致安全问题，所以在e的选择上，如果需要保证其安全性，应该按照如下选取原则：

​ (1)e不能够太小

​ e如果太小了，攻击者可以通过低指数攻击很容易的对加密进行攻击**。

​ (2)e 的选择应该使其在 $mod(\varphi(N))$mod(φ(N))的阶最大。即存在i,使得 $e^i \equiv 1 mod\varphi(n),i>=\frac{\varphi(n)}{2}$ei≡1modφ(n),i>=2φ(n)​这样可以有效抵抗**。

​ 由于实际环境中，很多的加密为了保证加解密的速度和方便选择指数e=3进行加密的，这样也存在很多实际环境中存在的问题。在这举一些实际的例子分析一些对参数e进行的攻击。

4.2.1 低加密指数攻击

适用情况：e 过小，一般来说 n，c都较大。

**原理：**根据公钥加密机制，密文c=m^e mod n。如果选取的 e 过小，加密指数过低，就会引发安全问题

1. 如果 e 过小导致 m ^e < n，可以推出 c = m^e，此时直接对密文开e次方即可得出明文
2. 对于 m^e > n，根据j加密公式变形得：m^e= k*n+c(k为正整数)，由此，我们可以通过**k来获得m^e，之后再开根号即可获得明文

##flag.enc
85 C0 DE 5F 89 E8 87 20 AF D4 85 F9 1D ED 38 E9
EA ED A3 A6 1D DE E7 08 7B BD 29 92 0E E4 0B 6D
53 56 5E DD 1E 41 80 95 58 6B D4 F3 30 15 72 9D
43 3A F4 13 C6 60 E4 C0 B1 64 ED 02 5F 91 21 6D
90 45 78 F7 F2 0C 5F B1 E0 9E 71 99 21 98 D8 E8
D7 FB D9 17 59 7A EE 45 EB F4 CA 80 12 4C E9 B4
7E D1 63 F0 B9 D5 71 6A 9D 6E 1F 5B 8A E0 9B 16
CA E3 0B BD 64 A1 5E 17 CC 39 A9 0F B6 25 36 AD
94 3C DD A9 A4 AA C5 97 8E 3C 93 50 25 35 D5 35
36 38 BC 70 8C 9B 59 CC 9D C7 BC B1 D8 73 33 6C
E0 81 59 15 22 B1 D4 89 04 46 37 83 DD 68 37 B1
C4 1B 80 11 88 96 48 E0 AC DF BD 3E E2 59 F7 17
99 08 28 D1 6D B3 4E B9 82 44 62 16 DB 53 4D C0
6B 9E 7A AF 90 BC CB 54 A1 CC 77 C2 81 3B DF E9
A1 B5 C2 E9 58 C3 EA 8C A1 03 BA 1A 89 03 6B 70
14 BB C9 62 EB 7A 8C 91 0E 09 5B B8 37 91 BD 9F
EE E0 D8 F6 AF 0C 2E 03 0C CC C6 D8 72 97 43 41
9B DE E0 A1 E4 5A B5 E7 32 4A 34 47 61 C8 CC 8D
B3 09 61 A9 71 D5 66 E4 9C 45 62 92 4C 3E E0 01
ED EC E3 44 5C D2 8D BA 26 4B A8 A9 0C 5E 53 35
42 09 6C 26 AA 7D 87 49 97 A3 08 02 5A 5E 95 BF
C6 94 9E BD 16 CE A8 89 D2 42 AB 2E 2F F2 44 60
90 D0 76 66 D7 57 49 46 E3 91 D3 F1 53 D5 03 46
BC 75 DA 94 63 41 82 DF 80 F7 BA 97 B7 7A F8 92
2F 13 E4 3B 2D F7 88 90 2A 20 9B 9E 56 9D D3 C6
FA A4 DD 7B 43 89 9F 59 79 88 45 DF 64 2E DE EF
34 A1 86 94 9C BE 83 C0 99 F0 85 F8 7A 29 95 91
E7 15 CC B4 FE 74 61 2B 00 AE BE 25 C1 14 81 9C
F8 87 C2 56 12 19 15 41 6A CB CB 05 89 37 E3 D3
9E B7 EF 71 43 E1 45 13 11 19 DA 9C 3D 98 18 59
9A 0E 51 09 72 7F B5 81 BB C2 0E B3 E6 A2 50 11
B8 E9 03 45 37 C0 E5 80 A0 EE 8F 15 53 80 5B E8

##pubkey.pem
-----BEGIN PUBLIC KEY-----
MIICIDANBgkqhkiG9w0BAQEFAAOCAg0AMIICCAKCAgEAsL7l4+nlp+jQC0kzVcYY
/Ix9fQO4LkCZUcGC85je4xBFgOe6cNODrlMRR1ZW6Klk04DLFX9IyVGt+mXbCxIs
pA5C+nCRibcZpPDXRuL2BpuvEc69ZQ8UuTyXc1L9E7Huptbh2ndVAqv/idOos2Ff
0NtJuIqXa8IFaEiShOGB9vEeJwiRyO+AAXutI442MDmkWEcPF0kQG8KZSdOk9AON
Rjk4hRV5x1JaaZhPFbVmfzQgm3DrJhE2lH+hI+VJ3/8AYBiDr9k2/kEeAG5Ok9Gg
Cw/qVBu/yMUYbLYiBQOpSyQTEQ1kDHfqVLoyIPyPTMbOdxUeKbPgZXjEeL0b6+BF
ie+aGX9vgG24s+zYJsrST1MkzN7G6P6tLCFQBoYCyNzcWUAsyslCS3kASMzdkycG
gJXvoBC38ZbHS6jDexKPnhQRdRYz94t7nlb3H3ehtNqtP8VLXn75NdmnL7F2dZdl
UitLvALjFNXAa2TVBUt7CWxgEjbmzPRbXmEcgF0zXbqww10ibMII2M5HNro5oDVE
JvrgBsf+UtUmfc+5w4hPUf3f30qXlLz+DhVXETdJ5sjvQh26Jjr/aHOc4A7YD9AC
LvktNIj3betive976mAm8iodJaoqktEkQUqAIf4MF0uYA+a7X6114YapRqFygHcP
EkP0OHRGzM6yIiqWXMMLOSkCAQM=
-----END PUBLIC KEY-----

E:\enviroment\python3.7\python.exe E:/temp.py
n: 721059527572145959497866070657244746540818298735241721382435892767279354577831824618770455583435147844630635953460258329387406192598509097375098935299515255208445013180388186216473913754107215551156731413550416051385656895153798495423962750773689964815342291306243827028882267935999927349370340823239030087548468521168519725061290069094595524921012137038227208900579645041589141405674545883465785472925889948455146449614776287566375730215127615312001651111977914327170496695481547965108836595145998046638495232893568434202438172004892803105333017726958632541897741726563336871452837359564555756166187509015523771005760534037559648199915268764998183410394036820824721644946933656264441126738697663216138624571035323231711566263476403936148535644088575960271071967700560360448191493328793704136810376879662623765917690163480410089565377528947433177653458111431603202302962218312038109342064899388130688144810901340648989107010954279327738671710906115976561154622625847780945535284376248111949506936128229494332806622251145622565895781480383025403043645862516504771643210000415216199272423542871886181906457361118669629044165861299560814450960273479900717138570739601887771447529543568822851100841225147694940195217298482866496536787241
e: 3
c: 545666236924510340010249577709750283325731706774285241719627277546281629429734726717293022303311450772262647904537263500252284243393598944613964442974546950954108203106726282255676706429218187217515454665602130999856741523362906632677988245886500953095201122016935004088287862399317170828388632964668574391252399791901016522260191839164586088073933168096433230663402492577707149742261018318811473591856287943664733276898405984282679026758294364432874973387827086342720762945025346962005339728347282927842299962927871005260338747371451546554777112213044710533502191671159066680035742327279159127279685106716107705888068319962657817786581813767331740609788885735155741039564703781141646102609725965697004923161084032164730408824475517786576979990372940555488021025837456038491436690372760376483602299268887032528766383572923258228355911069631275397149328319966792315903921085816103476508992023873616148326626245855060470294978538631677232260545724075728912626994884533001056079733734460116442499311813113038763837974777469202302071221647473459505245546281400799833123812072606012604323510933244028733287443734697557314202167934768160824072400916728008549350662843995750077421616789178835625661267955774815287104291379928002318796086248

对密文、公钥处理一下获取信息发现 n,c长的过分，e=3

from Crypto.PublicKey import RSA
import base64
import gmpy2
from Crypto.Util.number import *
r=open('./pubkey.pem').read()
pub=RSA.importKey(r)
#读取pem文件，获取n，e
n=pub.n
e=pub.e
print("n:",pub.n)
print("e:",pub.e)
#读取enc文件，获取c
flag_encode= open('./flag.enc','rb').read()
print("c:",int(flag_encode.hex(),16))
c=int(flag_encode.hex(),16)
k=1
#枚举开方结果，iroot方法为求某个数的某次方，返回(开方结果(int),能否开整数次方(bool))
while 1:
    m,f=gmpy2.iroot(n*k+c,e)
    k+=1
    if f:
        print(m)
        print(long_to_bytes(str(m)))

4.2.2 低加密指数广播攻击

适用情况：e很小，给出多组 n 和 c相对应的情况

原理：根据已有信息可列方程组

c1 = m^e mod n1

c2 = m^e mod n2

c3 = m^e mod n3

通过中国剩余定理进行计算。

一般攻击方法：

设共有 i 组方程

1. 计算出M：所有n的乘积
2. 对于每一个ni计算出mi：mi=M/ni
3. 计算每一个mi对ni的模逆ti：ti*mi % ni=1 (a,ti,k=gmpy2.gcdext(mi,ni))
4. 计算每一个mitici的值，累加起来对M取模得到m^e
5. 开e次方得到明文m

例子：Hack You CTF 2014: Cryptonet

#https://www.voidsecurity.in/2014/01/hack-you-ctf-2014-crypto-400-cryptonet.html
#!/usr/bin/env python

from scapy.all import *
from sage.all import *
import zlib
import struct

PA = 24L
packets = rdpcap('packets.pcap')
client = '192.168.1.5'
size = 2 # size of e and n is packed into 2 bytes
list_n = []
list_m = []

for packet in packets:
    if packet[TCP].flags == PA:
       if packet.dst == client:
           src = packet[IP].src
           raw_data = packet[TCP].load

           size_e = struct.unpack('!H', raw_data[:size])[0] 
           e = int(zlib.decompress(raw_data[size: size + size_e]))

           size_n = struct.unpack('!H', raw_data[size + size_e: 2 * size + size_e])[0]
           n = int(zlib.decompress(raw_data[2 * size + size_e: ]))
           list_n.append(n)

        if packet[IP].src == client:
            raw_data = packet[TCP].load
            size_m = struct.unpack('!H', raw_data[:size])[0]
            m = int(zlib.decompress(raw_data[size: size + size_m]))
            list_m.append(m)

e_17 = crt(list_m, list_n)
factors = prime_factors(e_17)
enc_message = 1
for num in factors:
    enc_message *= num

print hex(enc_message).decode('hex')
# 'Secret message! CTF{336b2196a2932c399c0340bc41cd362d}\n'

4.2.3 维纳攻击

方法类似同下，理论证明、推到、攻击实现参照参数d中详解。

4.2.4 低解密指数攻击

适用情况:e很大，一般n，c也很大，难以分解

原理：与低加密指数攻击类似，由于d 是 e对 φ(n) 的模反元素，因此 e 如果过大势必会引起 d 过小，即解密所用指数过小，同样会引发安全问题。类似的体型涉及连分数展开和渐进方程计算。（维纳攻击针对低解密指数攻击部分原理见后）

##bugku例题
N : 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
e : 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619

enc : 38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192

方法一：

使用RsaCtfTool对RSA进行攻击：命令如下

python RsaCtfTool.py --createpub -n 460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597 -e 354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619 >test.pem
##(n,e)封装为公钥用于加密

python RsaCtfTool.py --publickey test.pem --private >test.key
python RsaCtfTool.py --key test.key --dumpkey

方法二：

from Crypto.Util.number import long_to_bytes
e=354611102441307572056572181827925899198345350228753730931089393275463916544456626894245415096107834465778409532373187125318554614722599301791528916212839368121066035541008808261534500586023652767712271625785204280964688004680328300124849680477105302519377370092578107827116821391826210972320377614967547827619
n=460657813884289609896372056585544172485318117026246263899744329237492701820627219556007788200590119136173895989001382151536006853823326382892363143604314518686388786002989248800814861248595075326277099645338694977097459168530898776007293695728101976069423971696524237755227187061418202849911479124793990722597
c=38230991316229399651823567590692301060044620412191737764632384680546256228451518238842965221394711848337832459443844446889468362154188214840736744657885858943810177675871991111466653158257191139605699916347308294995664530280816850482740530602254559123759121106338359220242637775919026933563326069449424391192
 
#连分数展开算法
def lf(x,y):
    arr=[]
    while y:
        arr+=[x//y]
        x,y=y,x%y
    return arr
 
def jj(k):
    x=0
    y=1
    for i in k[::-1]:
        x,y=y,x+i*y
    return (y,x)
data=lf(e,n)
for x in range(1,len(data)+1):
    data1=data[:x]
    d = jj(data1)[1]
    print(long_to_bytes(str(pow(c,d,n))))

b"Didn't you know RSA padding is really important? Now you see a non-padding message is so dangerous. And you should notice this in future.Fl4g: PCTF{Sm4ll_3xpon3nt_i5_W3ak}\n"

4.3 参数d的选取原则

​ **d的选取是参数中最为关键的，选取参数d的时候，应该要使之大于$N^{0.25}$N0.25。

​ 如果d的长度较短，虽然可以让较复杂的加密或验证能够快速的运行，但是一个最直接的问题就是安全性大幅度降低。攻击者可以利用已知明文m加密后得到$c=m^{e}mod N$c=memodN再直接猜测d，从而求出$c^d mod N$cdmodN是否等于M，如果是则猜测正确；如果不是则继续猜测，如果d的长度过小，则猜测的空间变小，猜中的可能性加大。

​ d较小的时候可以采用维纳攻击针对RSA进行有效攻击，攻击使用连续分数法能够**公开私钥d。

4.3.1 维纳攻击

维纳攻击针对私钥攻击原理：
$\lambda(N) = \operatorname{lcm}(p-1, q-1) = \frac{(p-1)(q-1)}{G} = \frac{\varphi(N)}{G}$λ(N)=lcm(p−1,q−1)=G(p−1)(q−1)​=Gφ(N)​

$因为G = \gcd (p-1, q-1) \\$因为G=gcd(p−1,q−1)

$所以 ed\equiv 1 \pmod{\lambda(N)}$所以ed≡1(modλ(N))

存在K值使得：
$ed = K \times \lambda(N)+1$ed=K×λ(N)+1

$ed = \frac {K}{G} (p-1)(q-1)+1$ed=GK​(p−1)(q−1)+1

$不妨设 k = \frac {K}{\gcd(K,G)}$不妨设k=gcd(K,G)K​
$不妨再设 g= \frac {G}{\gcd(K,G)}$不妨再设g=gcd(K,G)G​

$可得：ed = \frac {k}{g} (p-1) (q-1)+1$可得：ed=gk​(p−1)(q−1)+1
两边同除dpq:

$\frac{e}{pq} = \frac{k}{dg} (1- \delta)$pqe​=dgk​(1−δ)

$有\delta = \frac {p+q-1- \frac {g}{k}}{pq}$有δ=pqp+q−1−kg​​

$So,\frac {e}{pq} 小于 \frac {k}{dg}, 且前者完全由公共信息组成。$So,pqe​小于dgk​,且前者完全由公共信息组成。

$让 N = pq 当 q < p < 2q 让d < \frac{1}{3} N^{\frac{1}{4}}$让N=pq当q<p<2q让d<31​N41​

$给定\left \langle N,e\right \rangle 使 ed \equiv 1(\mathrm{mod}\ \lambda (N))那么攻击者就可以有效恢复**$给定⟨N,e⟩使ed≡1(mod λ(N))那么攻击者就可以有效恢复密钥

维纳算法具体流程伪代码：

(q1,…,qm;rm)←EuclideanAlgorithm(n,b)
c0←1
c1←q1
d0←0
d1←1
for j←2 to m
　　cj←qjcj−1+cj−2
　　dj←qjdj−1+dj−2
　　n′←djb−1cj
　　Comment：n′=ϕ(n)，如果cjdj是正确的收敛子。
　　if n′是一个整数
　　　　设p和q为方程x2−(n−n′+1)x+n=0的根
　　　　if p和q为小于n的整数
　　　　　　return (p,q)
return ("failure")

import gmpy2
def transform(x,y):       #使用辗转相处将分数 x/y 转为连分数的形式
    res=[]
    while y:
        res.append(x//y)
        x,y=y,x%y
    return res
    
def continued_fraction(sub_res):
    numerator,denominator=1,0
    for i in sub_res[::-1]:      #从sublist的后面往前循环
        denominator,numerator=numerator,i*numerator+denominator
    return denominator,numerator   #得到渐进分数的分母和分子，并返回

    
#求解每个渐进分数
def sub_fraction(x,y):
    res=transform(x,y)
    res=list(map(continued_fraction,(res[0:i] for i in range(1,len(res)))))  #将连分数的结果逐一截取以求渐进分数
    return res

def get_pq(a,b,c):      #由p+q和pq的值通过维达定理来求解p和q
    par=gmpy2.isqrt(b*b-4*a*c)   #由上述可得，开根号一定是整数，因为有解
    x1,x2=(-b+par)//(2*a),(-b-par)//(2*a)
    return x1,x2

def wienerAttack(e,n):
    for (d,k) in sub_fraction(e,n):  #用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
        if k==0:                     #可能会出现连分数的第一个为0的情况，排除
            continue
        if (e*d-1)%k!=0:             #ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
            continue
        
        phi=(e*d-1)//k               #这个结果就是 φ(n)
        px,qy=get_pq(1,n-phi+1,n)
        if px*qy==n:
            p,q=abs(int(px)),abs(int(qy))     #可能会得到两个负数，负负得正未尝不会出现
            d=gmpy2.invert(e,(p-1)*(q-1))     #求ed=1 (mod  φ(n))的结果，也就是e关于 φ(n)的乘法逆元d
            return d
    print("该方法不适用")
    
    
e = 14058695417015334071588010346586749790539913287499707802938898719199384604316115908373997739604466972535533733290829894940306314501336291780396644520926473
n = 33608051123287760315508423639768587307044110783252538766412788814888567164438282747809126528707329215122915093543085008547092423658991866313471837522758159
d=wienerAttack(e,n)
print("d=",d)

4.4 实验环境

运行系统：Windows10/kali
CPU：Intel(R) core(TM) [e-mail] 2.30 GHz
运行内存：24GB
编程语言：python
使用工具：RsaCtfTool  ——用于**的处理、分解
密码学相关包：
Crypto 一个非常强大的密码学库
scapy  网络编程相关数据库，用于数据包的发送、接受等
sage   开源数学软件，可以帮助实现一些数学算法，提升运行效率

5、参考资料

参考资料、文献：

https://zh.wikipedia.org/zh-hans/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95#%E6%AD%A3%E7%A1%AE%E6%80%A7%E8%AF%81%E6%98%8E

瞿白.RSA算法参数的选择[J].科技资讯,2010(28):10.童子圣,孙强.CRT-RSA的连分数算法攻击的分析[J].微计算机信息,2009,(9).doi:10.3969/j.issn.1008-0570.2009.09.028.

李勇.RSA加密算法参数的选择[J].科技信息,2008(17):67-67,67.

荀月凤.一种改进的RSA算法的实现[J].成都电子机械高等专科学校学报,2005(1):6-8.

杨中和.二次无理数的连分数[J].西安文理学院学报：自然科学版,2008(2):54-58.


教材：<<信息安全数学基础>> 、<<密码学与网络安全>>