RSA攻击

本文针对已经很熟悉RSA原理的朋友。不了解RSA原理的大兄弟戳下面的链接:

RSA(Part.1)
RSA(Part.2)

0x00 Wiener's attack

  • 使用条件

    d很小(e很大)(公钥{n, e},私钥{n, d}  
  • 原理(具体原理较复杂可见参考链接,这里只说定理)

    Wiener's theorem:  
    N=qp 当q<p<2q. 如果私钥:  

    QDEL(PD[YS7TN7G6_[B_6GO.png

则攻击者可以快速算出私钥d

  • 例子

    公钥为:<N,e>=<90581, 17993>  
    分解:  

    F9U_PZBZ4[HXP05T(3QTW6.png

为啥要分解呢?

已知:

ed = 1 (mod φ(N)) .............................1

其中:

φ(N)=(p-1)(q-1).............................2

由1式可知,存在一个k使得如下等式成立:

ed = 1+ kφ(N) .............................3

则,两遍同时除以dφ(n):
~R900V1GEFPVG8_WQEZ7SJ0.png

这时,注意到一般情况下N=pq很大很大,所以φ(n)=(q-1)(p-1)很接近N,1/dφ(n)很接近0,所以就假装如下等式成立:

VGZ3[_RM%(2MD6$%RBBI2VB.png

这样子就可以使用到之前分解的式子了,假定:

8_MV{0HLG{G{7QXHP2NS3RR.png

则将式6带入式3就可以得到:

~60%KJ03B{{2EA{(GF}_40A.png

得到φ(n)有啥用呢?见下变换:

φ(N)=(p-1)(q-1)=pq-(p+q)+1 .............................8

其中,N=pq, p+q=N - φ(n) + 1

这样便得到了pq和p+q,也就自然的可以使用维达定理(不晓得这个的面壁去),

x^2 - ((N-φ(N))+1)x + N=0

x^2-618x + 90581=0

解得:N=p*q=378 x 239
想去看具体原理的戳下面的链接:
Wiener's attack
想看代码实现的戳下面链接:
code

0x01 Coppersmith's attack

  • Coppersmith's method
    只说一下Coppersmith's method的是用来干啥的,详细内容我只贴个连接。

Coppsersmith'smethod

Coppersmith's method:
有F(x):
`V}U9L4XSMMI42@V.png

上述等式右边是个度为n摩尼多项式(即度为n,最高次系数为1的多项式)
并且:
V{NZ}DABBL}H05_RP_$SNAO.png

那么,Coppersmith's method就是用来解出所有的x0。

  • 例子

或许,看了这个定理,有人觉得并没有啥用。没事儿,慢慢来:
说个Coppersmith's method最常用的例子,RSA中公钥为<N,e>,明文为m,密文为c,那么:
3LF9WK5%}[6C)1A`W@DHEBD.png

若e=3(CTF中常用这个e=3),那么:
由上面的加密公式可知:

在给定F(x)的情况下,这里使用上面的Coppersmith's method的话,就容易求出所有的x0,其中:
ER4@M0G@IO69~@EXLX~XWE4.png

若将m化成二进制,就会明白,若知道明文的高2/3位的话,那么就可以很容易恢复低1/3位的内容。
当然,这只是基于Coppersmith's method的一小种应用,Coppersmith's method可以用于不同的场景。
当注意到公钥e有问题时就可以考虑使用Coppersmith's method中的一些应用方式。
Coppersmith's attack 原理:
Coppersmith's attack
针对上述e=3,并且已知部分明文,一般使用sage脚本来进行相关操作: :
在线运行sage脚本

0x02 总结

本次说了两种针对RSA的攻击基本原理,最再后理一下,第一种是针对d较小时,第二种是针对e(注意,不一定是e较小时)。