HITCTF2020 ezRSA - The learing or Coppersmith attack

Posted on Edited on In Word count in article: 6.3k Reading time ≈ 6 mins.

关于出去玩只能在手机上用Sage Cell Server做题那件事
也是好久没写博客了, 刚好学习一下coppersmith attack

先把题目放上来吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#! /bin/bash python2
from flag import flag
from Crypto.Util.number import *
import os


flag = flag+os.urandom(32)

p = getPrime(512)
q = getPrime(512)
n = p*q
e = 3
phi = (p-1)*(q-1)
d = inverse(e,phi)

m1 = bytes_to_long(flag)
m2 = bytes_to_long(flag+os.urandom(8))


assert pow(m1,3) > n

c1 = pow(m1,e,n)
c2 = pow(m2,e,n)

print "c1 = %d"%c1
print "c2 = %d"%c2
print  "n = %d"%n

'''
c1 = 80653989110793139102855968265870741534421660712327094406252902072101613222389965470648960909763762225046314865847982289607336162281576790259047039000290839621007818742162307587677505606906923990312494483089046762906753345262127057162580025978324312642501118741099945205580088180943278903718853065363662232083
c2 = 5400424653941721880728309040044485787870754570249463205700803061685717472238274158687499478247752712211743180931379853481727502849946080245130393042405383007613277703993980940893569303012323853427216643473698166348237252515222556282004058588218846910754415888401275689026778751805826968590155607937830708498
n = 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338861040226250478895118923994109662815448681629315227440953320952623296140315432654804940766553284237954507627610922864055435652884184926768295740697589798180602153344302964255974935777945481843144629875127
'''

做这个之前, 先来看看coppersmith attack(直接翻CTF wiki

对于单变量的方程(多变量的还没接触过, 能否使用coppersmith attack 就看变量是否满足上面这部分所提到的约束.

来分析一下这些约束, 对于一般的RSA列出模N意义下的多项式方程求解根的时候, 因为N往往是两个大素数的乘积, 那么N必定会有一个因子 是满足 的, 所以一般 是取0.4~0.6的

但是有需要注意的是, 有时候求解根并不是在模N的意义下进行的, 这个时候就需要慎重的考虑一下的取值了

而对于 , 也就是多项式的阶数, 阶数越小对根的约束就越宽松, 这也就是为什么CTF wiki上会有这么一句

所以, 判断是否可以使用coppersmith attack, 就看需要解的根是否足够小(一般通过题目所给的信息来判断根的位数, 再通过e 和 N 的位数,来判断是否可以使用coppersmith attack

需要注意的是!由于LLL是启发式算法, 所以有的时候解出来的根会不满足约束, 也就是说当需要解的根近乎足够小就可以试试coppersmith了

现在回到题目, 先来分析一下题目

这题先对flag进行了一次填充flag = flag+os.urandom(32), 如果flag太小是可能直接解出来的.

然后就是对明文进行加密,再进行一次填充再加密, 写成式子就是

其实可以令M=2^64^m 和 , 就可以有

两个方程, 两个未知数, 肯定是可以解出根来的, 只不过是难不难解出来的问题了. 注意到这里的 是64位的, 而是1024位的, e=3也很小, 可以考虑试试coppersmith先解出.

事实上解用到的就是Coppersmith’s short-pad attack

Coppersmith’s short-pad attack

图片.png

wiki上说的也很清楚了, 在对明文进行填充的时候, 如果填充的位数很少,就可以算出,只需要, 就可以解出了. 在这里显然是满足的.

我们先把两个方程化成只有一个未知数的方程(代码里diff = xn ,
然后用small_root()求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
C1 = 80653989110793139102855968265870741534421660712327094406252902072101613222389965470648960909763762225046314865847982289607336162281576790259047039000290839621007818742162307587677505606906923990312494483089046762906753345262127057162580025978324312642501118741099945205580088180943278903718853065363662232083
C2 = 5400424653941721880728309040044485787870754570249463205700803061685717472238274158687499478247752712211743180931379853481727502849946080245130393042405383007613277703993980940893569303012323853427216643473698166348237252515222556282004058588218846910754415888401275689026778751805826968590155607937830708498
n = 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338861040226250478895118923994109662815448681629315227440953320952623296140315432654804940766553284237954507627610922864055435652884184926768295740697589798180602153344302964255974935777945481843144629875127
C1=(C1*2**192)%n
e = 3

n1 = n
PRxy.<x,y> = PolynomialRing(Zmod(n1))
PRx.<xn> = PolynomialRing(Zmod(n1))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n1))
 
g1 = x**e - C1
g2 = (x + y)**e - C2
 
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)

h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()

roots = h.small_roots(X=2**64, beta=0.4)
diff = roots[0]
# diff = 15325913216714639606

这里的small_root()的参数很重要, X是设置根的上界的, 这个要尽可能的接近根的大小, 这样求解出来的可能性才高. 而beta一般0.4~0.6就行了.

接下来就是算M了, 这个又是另外一个method - Franklin-Reiter related-message attack

先来看看wiki上怎么说
图片.png
图片.png
通俗一点就是, 当两个明文满足线性关系的时候,是两个方程

的一个公因式, 因此可以利用在多项式的欧几里得算法算出这个公因式, 也就是我们要算的M

1
2
3
4
5
6
7
8
9
10
11
x = PRx.gen() 
g1 = x**e - C1
g2 = (x + diff)**e - C2

# 辗转相除法求公因式
while g2:
    g1, g2 = g2, g1 % g2

g = g1.monic()
# g = xn + 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338855507056808173780823100612346393533355160251650215111996263513671265306614427524745781162849613136748611330041590288489365015322686961617690785110909682202890569108842866175345662756188830323253136519607
M = -g[0]

M算出来了别忘了除一个2^64(一开始为了方便计算所以把m放大了, 还好不影响解题, 以后做的时候要小心为了方便计算导致算不出根来, 所以最后的代码是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
C1 = 80653989110793139102855968265870741534421660712327094406252902072101613222389965470648960909763762225046314865847982289607336162281576790259047039000290839621007818742162307587677505606906923990312494483089046762906753345262127057162580025978324312642501118741099945205580088180943278903718853065363662232083
C2 = 5400424653941721880728309040044485787870754570249463205700803061685717472238274158687499478247752712211743180931379853481727502849946080245130393042405383007613277703993980940893569303012323853427216643473698166348237252515222556282004058588218846910754415888401275689026778751805826968590155607937830708498
n = 92782661709340169703868140576276816382956055756557631391697803785121887338308072309948803413610339884338861040226250478895118923994109662815448681629315227440953320952623296140315432654804940766553284237954507627610922864055435652884184926768295740697589798180602153344302964255974935777945481843144629875127
C1=(C1*2**192)%n
e = 3

n1 = n
PRxy.<x,y> = PolynomialRing(Zmod(n1))
PRx.<xn> = PolynomialRing(Zmod(n1))
PRZZ.<xz,yz> = PolynomialRing(Zmod(n1))
 
g1 = x**e - C1
g2 = (x + y)**e - C2
 
q1 = g1.change_ring(PRZZ)
q2 = g2.change_ring(PRZZ)

h = q2.resultant(q1)
h = h.univariate_polynomial()
h = h.change_ring(PRx).subs(y=xn)
h = h.monic()

roots = h.small_roots(X=2**64, beta=0.4)
diff = roots[0]

x = PRx.gen() 
g1 = x**e - C1
g2 = (x + diff)**e - C2
 
while g2:
    g1, g2 = g2, g1 % g2

g = g1.monic()

M = -g[0]
h =hex(M*inverse_mod(2**64,n))[2:]
s=""
for i in range(0,len(h),2):
    s+=chr(int(h[i:i+2],16))
print(s)

# s = HITCTF2020{dde65d8adf22b5e1a0c0c10eff23c24c}

一下子学了两个方法好爽啊, 在看到e很小的时候, 一定要想起coppersmith来.
不过这些应该都算是基础的, 特别是coppersmith的使用感觉还有很多很深奥的地方,