RSA考点之coppersmith

发表于 更新于 分类于 阅读次数：

Coppersmith攻击

一、引言

近期参加的各类CTF比赛中，常见到coppersmith攻击的考点，于是在此做一个简单的学习与总结，后续若还有新的coppersmith的考点，会在文章中作出补充。

二、Coppersmith攻击原理

真正能够用好一个方法，一定要搞清楚这个方法背后的本质原理，于是我在网上搜集资料，找到了Coppersmith攻击的原理。

对于

,要找到这个多项式在意义下的根，在不限制的条件下这是一个很困难的问题。

因为可以特别大只需要是的倍数就可以

这一步带来很多困难.

首先考虑一个特殊情况如果就等于0那么可以用牛顿迭代法求出来但是牛顿迭代法遇到就失灵了.

怎么办呢？没有条件就创造条件！

大概的思路是如果足够小使得|那么

这时候就满足了使用牛顿迭代法的条件

那么现在问题集中在怎么证明|.答案是：无法证明！因为没有限制的大小

Coppersmith想出了一个办法：能不能找一个系数的多项式当时

也就是说希望找到一个系数的多项式系数小到能够满足牛顿迭代法的要求那么问题就解决了，就差把x求出来。

Coppersmith利用如下操作先得到一系列：

再将一系列的经过线性组合得到

为了让的系数尽量小就要用到LLL格基规约算法（关于LLL格基规约算法将在下一个博客中给出学习介绍）

三、Coppersmith攻击在CTF比赛中的运用

在CTF比赛中，使用Coppersmith攻击的主要原理是根据以下公式完成的：

这里只需要将t看成上述的x，即可把这个公式转换为求解一个有关t的多项式的根，其中，t要求不能太大，否则无法使用Coppersmith攻击原理解决

具体来说，我们一般会在sagemath中利用函数来解决

small_roots()是SageMath中一个运用了coppersmith定理的函数。它只能解有限域内的方程。

small_roots(X = ,beta = ) 有两个参数

X代表所需要求解根的上限；虽然是根的上限，并不是说上限越高越好，当上限超过某个值的时候就会计算失效，即使已知二进制位数满足条件，也无法用此函数求得结果；所以一般来说X取在给定情况下的最大求解上限

那么下面，我们给出几个题目来理解一下Coppersmith攻击的运用吧

1、极客：highlow

先看题目：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from Crypto.Util.number import *
e = 65537
p = getPrime(1024)
q = getPrime(1024)
n = p * q
pxor = p ^ (bytes_to_long(flag)<<400)
assert len(flag)== 44
m = bytes_to_long(flag)
c = pow(m, e, n)

print('c =',c)
print('n =',n)
print('pxor =',pxor)


'''
c = 11017336122691034053241992293963114590816319844384287448629663672049205892828600396465505710922907685545939978376321927394655458727494361852952898280905220963163625482295222856129164172619564344634365520328815972232825639292605311741655988427166811406091329613627961070231457035303298793651546412496975662225857123805867756651901374507447803198638466304862480202099076813471571495380132563252630789218173007275890600746758285415274434393381125742526014986039652677605642226576741424053749512280825231217420239089105794080707322357602941046822659335487420672699022969372037662958497832065752272061853723653365171768556
n = 14091206320622523674847720139761543154822190879035380245424481267482550932229611965964424965958386255076593911062804299275581742665134207390532802109700225140999812698020838683697375891035625255222001884477214361835101442288725383073334392995186053867261497679234362794914108033574681292656522807928680812726462195077833184018122369579002715900477290345396065912536529290811962117814900448319776590712946259540382461632468634827959957286905806432005632864663985014872365672653476822833921870071851313424903481282350342304819149894610089804321405589433980650340610521659031234826823369114800150883988613877877881069579
pxor = 124229245244085791439650934438639686782423445183921252684721764061493908790073948877623812930339081158169421854801552819088679937157357924845248082716160727839419054107753000815066526032809275137495740454967765165248115412626716101315676902716808647904092798908601183908297141420793614426863816161203796966951
'''


所以高已知

已知672位，1024-672=352 末知

可用small roots()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
from Crypto.Util.number import *
e = 65537
c = 11017336122691034053241992293963114590816319844384287448629663672049205892828600396465505710922907685545939978376321927394655458727494361852952898280905220963163625482295222856129164172619564344634365520328815972232825639292605311741655988427166811406091329613627961070231457035303298793651546412496975662225857123805867756651901374507447803198638466304862480202099076813471571495380132563252630789218173007275890600746758285415274434393381125742526014986039652677605642226576741424053749512280825231217420239089105794080707322357602941046822659335487420672699022969372037662958497832065752272061853723653365171768556
n = 14091206320622523674847720139761543154822190879035380245424481267482550932229611965964424965958386255076593911062804299275581742665134207390532802109700225140999812698020838683697375891035625255222001884477214361835101442288725383073334392995186053867261497679234362794914108033574681292656522807928680812726462195077833184018122369579002715900477290345396065912536529290811962117814900448319776590712946259540382461632468634827959957286905806432005632864663985014872365672653476822833921870071851313424903481282350342304819149894610089804321405589433980650340610521659031234826823369114800150883988613877877881069579
pxor = 124229245244085791439650934438639686782423445183921252684721764061493908790073948877623812930339081158169421854801552819088679937157357924845248082716160727839419054107753000815066526032809275137495740454967765165248115412626716101315676902716808647904092798908601183908297141420793614426863816161203796966951
phigh=(pxor>>752)<<752
plow = pxor%2**400
print(phigh)
print(plow)
R.<x>= PolynomialRing(zmod(n))
f= phigh + x*2**400 + plow
f= f.monic()
root =f.small_roots(x=2^352,beta=0.4)
print(root)
if root:
p=int(phigh + root[0]*2**400 + plow)
q = n//p
d=inverse(e,(p-1)*(q-1))
m= pow(c,d,n)
print(long_to_bytes(int(m)))
else:
print(0)

2、i春秋冬季赛 RSA1

这是一道我比较喜欢的题目🤭考察Coppersmith以及简单的数论知识。

题目代码如下：

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
from Crypto.Util.number import *
import uuid
p, q = [getPrime(512) for _ in range(2)]
N = p * q
flag = b'flag{' + str(uuid.uuid4()).encode() + b'}'
flag += bin(getPrime((1024 - bytes_to_long(flag).bit_length()) / 8)).encode()
m1 = bytes_to_long(flag)
m2 = bytes_to_long(''.join(chr((ord(i) + 3) % 128) for i in flag.decode()).encode())
e = getPrime(128)
c1 = pow(m1 * e, 2835, N)
c2 = pow(m2, 2025, N)
c3 = pow(m2, 2835, N) + e
print(f'{N = }')
print(f'{c1 = }')
print(f'{c2 = }')
print(f'{c3 = }')
'''
N =
17687156112047658916576175030063333258687770834244899450617562420363386011962151231832
11729278763896319183001842210823177413803654471977770262564053122127166306177216069180
66048995683899616059388173629437673018386590043053146712870572300799479269947118251011
967950970286626852935438101046112260915112568392601
c1 =
47280375006817082521114885578132104427687384457963920263778661542552259860890075321953
56386765823334793012150783561241727843897900670501653759635767903847117695765983415569
42843646827596758418082098123160949653935505099139848888499454210924638425466312286402
93794745005338773574343676100121000764021207044019
c2 =
17623141093397913458588607801393364949837987344485194322493501097245276989960336468615
82792691978911906437250081518121504288085503105877090086833394365901128027567671401021
36304346001599401670291938369014436170693864034099138767167055456635760196888578642643
971920733784690410395944410255241615897032471127315
c3 =
13559480788401697135681642316912816872734610240849028962388521117961957135410510239365
82492923331793464974151297851846540082997256176686556408573180639927032654071620851788
85733134590524577996093366819328960462500124201402816244104477018279673183368074374836
717994805448310223434099196774685324616523478136309
'''

根据上述题目代码，我们有：

观察2025与2835这两个数字，突然顿悟，发现他们的最大公约数为14175！

于是进行线性变化：

至此，我们便可以使用Coppersmith攻击原理，求出e了！

接下来就是其他知识点的考察了，不过我们能发现，运用Coppersmith我们对这道题的进度推进了很多！

我们注意到：

(这里利用了bytes_to_long函数的原理，将每个字符转换为八位二进制的数)

我们发现是一个定值

于是我们可以对以下两个式子做相关消息攻击：

而m是大于n的，所以还需要做小范围爆破

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from Crypto.Util.number import *
import sys
def HGCD(a, b):
if 2 * b.degree() < a.degree() or a.degree() = 1:
return 1, 0, 0, 1
m = a.degree() / 2
a_top, a_bot = a.quo_rem(x^m)
b_top, b_bot = b.quo_rem(x^m)
R00, R01, R10, R11 = HGCD(a_top, b_top)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
q, e = c.quo_rem(d)
d_top, d_bot = d.quo_rem(x^(m / 2))
e_top, e_bot = e.quo_rem(x^(m / 2))
S00, S01, S10, S11 = HGCD(d_top, e_top)
RET00 = S01 * R00 + (S00 - q * S01) * R10
RET01 = S01 * R01 + (S00 - q * S01) * R11
RET10 = S11 * R00 + (S10 - q * S11) * R10
RET11 = S11 * R01 + (S10 - q * S11) * R11
return RET00, RET01, RET10, RET11
def GCD(a, b):
print(a.degree(), b.degree())
q, r = a.quo_rem(b)
if r = 0:
return b
R00, R01, R10, R11 = HGCD(a, b)
c = R00 * a + R01 * b
d = R10 * a + R11 * b
if d = 0:
return c.monic()
q, r = c.quo_rem(d)
if r = 0:
return d
return GCD(d, r)
sys.setrecursionlimit(500000)
N =
17687156112047658916576175030063333258687770834244899450617562420363386011962151231832
11729278763896319183001842210823177413803654471977770262564053122127166306177216069180
66048995683899616059388173629437673018386590043053146712870572300799479269947118251011
967950970286626852935438101046112260915112568392601
c1 =
47280375006817082521114885578132104427687384457963920263778661542552259860890075321953
56386765823334793012150783561241727843897900670501653759635767903847117695765983415569
42843646827596758418082098123160949653935505099139848888499454210924638425466312286402
93794745005338773574343676100121000764021207044019
c2 =
17623141093397913458588607801393364949837987344485194322493501097245276989960336468615
82792691978911906437250081518121504288085503105877090086833394365901128027567671401021
36304346001599401670291938369014436170693864034099138767167055456635760196888578642643
971920733784690410395944410255241615897032471127315
c3 =
13559480788401697135681642316912816872734610240849028962388521117961957135410510239365
82492923331793464974151297851846540082997256176686556408573180639927032654071620851788
85733134590524577996093366819328960462500124201402816244104477018279673183368074374836
717994805448310223434099196774685324616523478136309
R.<x> = PolynomialRing(Zmod(N))
f = (c3 - x)^5 - c2^7
res = f.monic().small_roots(X=2^128,beta=0.4,epsilon=0.02)
e = int(res[0])
print(f"e = {e}")
b =
13860425563098439450464440586299944110869145799054471005966486822062551343046248376311
97972917799925293608240198869587597177368766614530443357455736033307618174328289246889
93026332102549607397901351619425324993583087500714061523945925857368498922102768458574
857510324727265052999967460998294909713988129273348867
R.<x> = PolynomialRing(Zmod(N))
f = (e * x)^2835 - c1
g = (x + b)^2025 - c2
res = GCD(f,g)
from tqdm import *
m = int(-res.monic().coefficients()[0])
print(f"m mod N = {m}")
for k in trange(2^16):
mm = m + k*N
flag = long_to_bytes(int(mm))
if b"flag" in flag:
print(flag)
break
# flag{2404dcef-4223-417d-aee0-c236241f2320}

3、西湖论剑 matrix RSA

先上题目：

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
import random
import string
from Crypto.Util.number import *
from secret import flag
ext_len = 9*23 - len(flag)
flag += ''.join(random.choice(string.printable) for _ in range(ext_len))
def my_rsa_encrypt():
    p = getPrime(512)
    q = getPrime(512)
    n = p * q
    data = []
    for i in range(9):
        data.append(bytes_to_long(flag[23*i:23*(i+1)].encode()))
    M = Matrix(Zmod(n), [data[i:i+3] for i in range(0, len(data), 3)])
    e = 65537
    C = M**e
    print("p =", p >> 100)
    print("n =", n)
    return C
C = my_rsa_encrypt()
print("C =", C)
'''
high_p = 12305755811288164655681709252717258015229295989302934566212712319314835335461946241491177972870130171728224502716603340551353785064416812665744581355110400
p = 9707529668721508094878754383636813058761407528950189013789315732447048631740849315894253576415843631107370002912949379757275
n = 132298777672085547096511087266255066285502135020124093900452138262993155381766816424955849796168059204379325075568094431259877923353664926875986223020472585645919414821322880213299188157427622804140996898685564075484754918339670099806186873974594139182324884620018780943630196754736972805036038798946726414009
C = [130700952989014311434434028098810412089294728270156705618326733322297465714495704072159530618655340096705383710304658044991149662060657745933090473082775425812641300964472543605460360640675949447837208449794830578184968528547366608180085787382376536622136035364815331037493098283462540849880674541138443271941  71108771421281691064141020659106224750236412635914570166893031318860027728093402453305986361330527563506168063047627979831630830003190075818824767924892107148560048725155587353683119195901991465464478196049173060097561821877061015587704803006499153902855903286456023726638247758665778434728734461065079337757  67999998657112350704927993584783146575182096185020115836188544590466205688442741039622382576899587857972463337900200038021257164640987281308471100297698062626107380871262596623736773815445544153508352926374272336154553916204320257697068627063236060520725376727528604938949588845448940836430120015498687885615]
[ 23893343854815011808020457237095285782125931083991537368666368653089096539223297567339111502968295914745423286070638369517207554770793304994639155083818859208362057394004419565231389473766857235749279110546079776040193183912062870294579472815588333047561915280189529367474392709554971446978468118280633281993   9711323829269829751519177755915164402658693668631868499383945203627197171508441332211907278473276713066275283973856513580205808517918096017699122954464305556795300874005627001464297760413897074044080665941802588680926430030715299713241442313300920463145903399054123967914968894345491958980945927764454159601  44904507975955275578858125671789564568591470104141872573541481508697254621798834910263012676346204850278744732796211742615531019931085695420000582627144871996018850098958417750918177991375489106531511894991744745328626887250694950153424439172667977623425955725695498585224383607063387876414273539268016177401]
[ 67805732998935098446255672500407441801838056284635701147853683333480924477835278030145327818330916280792499177503535618310624546400536573924729837478349680007368781306805363621196573313903080315513952415535369016620873765493531188596985587834408434835281527678166509365418905214174034794683785063802543354572  13486048723056269216825615499052563411132892702727634833280269923882908676944418624902325737619945647093190397919828623788245644333036340084254490542292357044974139884304715033710988658109160936809398722070125690919829906642273377982021120160702344103998315875166038849942426382506293976662337161520494820727  95932690738697024519546289135992512776877884741458439242887603021792409575448192508456813215486904392440772808083658410285088451086298418303987628634150431725794904656250453314950126433260613949819432633322599879072805834951478466009343397728711205498602927752917834774516505262381463414617797291857077444676]

'''

我们能发现这里也有Coppersmith的踪迹！

于是先把p，q求出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
from sage.all import *
n = 132298777672085547096511087266255066285502135020124093900452138262993155381766816424955849796168059204379325075568094431259877923353664926875986223020472585645919414821322880213299188157427622804140996898685564075484754918339670099806186873974594139182324884620018780943630196754736972805036038798946726414009
p4 = 9707529668721508094878754383636813058761407528950189013789315732447048631740849315894253576415843631107370002912949379757275
e =  65537
pbits = 512
kbits = pbits - p4.nbits()
print(p4.nbits())
p4 = p4 << kbits
PR.<x> = PolynomialRing(Zmod(n))
f = x + p4
roots = f.small_roots(X=2^kbits, beta=0.4)
if roots:        
	p = p4+int(roots[0]) 
	print("n= "+str(n))
	print("p= "+str(p))
	print("q= "+str(n//p))

接下来就是一个非线性费马定理的使用了，这是以前从来没有接触过的东西捏~(￣▽￣)~*，也感谢学长的帮助，给到了文献参考！

[]: https://www.gcsu.edu/sites/files/page-assets/node-808/attachments/pangia.pdf

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import random
import string
from Crypto.Util.number import *
n= 132298777672085547096511087266255066285502135020124093900452138262993155381766816424955849796168059204379325075568094431259877923353664926875986223020472585645919414821322880213299188157427622804140996898685564075484754918339670099806186873974594139182324884620018780943630196754736972805036038798946726414009
p= 12305755811288164655681709252717258015229295989302934566212712319314835335461946241491177972870130171728224502716603340551354171940107285908105124549960063
q= 10750967246621849802090386055921679114516122704252330881722100331526757637044067492444912824266860574267360247681890637480406758188129451052986858429875143
e=65537
C =  [(130700952989014311434434028098810412089294728270156705618326733322297465714495704072159530618655340096705383710304658044991149662060657745933090473082775425812641300964472543605460360640675949447837208449794830578184968528547366608180085787382376536622136035364815331037493098283462540849880674541138443271941,71108771421281691064141020659106224750236412635914570166893031318860027728093402453305986361330527563506168063047627979831630830003190075818824767924892107148560048725155587353683119195901991465464478196049173060097561821877061015587704803006499153902855903286456023726638247758665778434728734461065079337757,67999998657112350704927993584783146575182096185020115836188544590466205688442741039622382576899587857972463337900200038021257164640987281308471100297698062626107380871262596623736773815445544153508352926374272336154553916204320257697068627063236060520725376727528604938949588845448940836430120015498687885615),(23893343854815011808020457237095285782125931083991537368666368653089096539223297567339111502968295914745423286070638369517207554770793304994639155083818859208362057394004419565231389473766857235749279110546079776040193183912062870294579472815588333047561915280189529367474392709554971446978468118280633281993, 9711323829269829751519177755915164402658693668631868499383945203627197171508441332211907278473276713066275283973856513580205808517918096017699122954464305556795300874005627001464297760413897074044080665941802588680926430030715299713241442313300920463145903399054123967914968894345491958980945927764454159601, 44904507975955275578858125671789564568591470104141872573541481508697254621798834910263012676346204850278744732796211742615531019931085695420000582627144871996018850098958417750918177991375489106531511894991744745328626887250694950153424439172667977623425955725695498585224383607063387876414273539268016177401), (67805732998935098446255672500407441801838056284635701147853683333480924477835278030145327818330916280792499177503535618310624546400536573924729837478349680007368781306805363621196573313903080315513952415535369016620873765493531188596985587834408434835281527678166509365418905214174034794683785063802543354572, 13486048723056269216825615499052563411132892702727634833280269923882908676944418624902325737619945647093190397919828623788245644333036340084254490542292357044974139884304715033710988658109160936809398722070125690919829906642273377982021120160702344103998315875166038849942426382506293976662337161520494820727, 95932690738697024519546289135992512776877884741458439242887603021792409575448192508456813215486904392440772808083658410285088451086298418303987628634150431725794904656250453314950126433260613949819432633322599879072805834951478466009343397728711205498602927752917834774516505262381463414617797291857077444676)]
C = matrix(Zmod(n), C)
phi=(p**2-1)*(q**2-1)
d = inverse(e,phi)
M = C**d
flag = b""
for i in range(3):
    for j in range(3):
        m = int(M[i,j])
        flag += long_to_bytes(m)
print(flag)

四、总结

总的来说，Coppersmith攻击的考察是十分常见的，这一般用于解决 RSA 攻击中“已知某些二进制位，求剩余位”这一类问题

当然，Coppersmith攻击很少会直接考察，一般会与其他知识点结合起来形成综合题

因此，不断深入学习其他攻击方式也是十分重要的！