coppersmith 定理的几种攻击情况的学习
Coppersmith 可以用于求多项式的小根，经常用于 RSA 攻击中“已知某些二进制位，求剩余位”这一类问题
给定：
- 模数 N（通常很大，如 RSA 模数）
- 模 N 的多项式 f(x)（通常为单变量）
- 边界 X
寻找所有满足 f(x0) ≡ 0 (mod N)且 ∣x0∣ < X 的整数根 x0
成立的条件：
$$
|x_0|\ <\ N^{1/deg(f)}\\
$$
deg(f)为多项式最高项次数
1.basic boradcast attack 广播攻击
攻击原理
1
|
Broadcast attack 是 Håstad attack，不是 Coppersmith，只是经常一起出现
|
使用同一个指数 e 加密同一个密文 m，产生 e 个明文，形如：
$$
c_1 \equiv m^e \pmod{n_1} \\
c_2 \equiv m^e \pmod{n_2} \\
\vdots \\
c_e \equiv m^e \pmod{n_e}
$$
n1, n2…互素，
是 m ≤ min(n₁, n₂, …, nₑ)，即明文 m 必须小于等于所有模数中的最小值
然后解中国剩余定理
根据中国剩余定理（CRT），可以求解：
mᵉ ≡ C (mod N)
其中 N = n₁ × n₂ × … × nₑ
因为 m ≤ min(n₁, n₂, …, nₑ)，m^e^ < n₁ × n₂ × … × nₑ
mᵉ < N，则可以直接对 C 开 e 次方根得到明文 m：m = ᵉ√C
RSA 高位攻击
内容参考：
RSA_高位攻击学习记录_rsa 已知高位攻击-CSDN 博客
RSA 中 coppersmith 定理的应用条件-CSDN 博客
Coppersmith 攻击
知道部分二进制位，求剩余二进制位，只有未知的 bit 位满足 unknown_bits / p_bits <= 0.44（即 coppersmith 定理）时，才能通过 small_roots()方法求出未知的 bit 位，进而求解 flag
small_roots(X = , beta = )的使用方法：
1
2
3
|
R.<x> = PolynomialRing(Zmod(N)) # 定义模N的多项式环
f = (x + a)^e - c # 定义多项式
roots = f.small_roots(X=,beta=)
|
看不懂，让 ai 细说了一下
边界因素 X：
- 已知根的比特 k 的情况下，X = 2^k^
- 已知根的大致范围 [0,1000]，X = 1000
- 理论边界：根据 coppersmith: X < N^1/e^，所以 X = floor(N^1/e^)
- 因子的部分比特攻击，知道了 p 的高位，p = p_high+x，所以 X = 2^unknown_bits^
beta 参数（β）：当 p, q 二进制位数相同时一般只能取 0.4
-
在模 N 上寻找根，如果根满足 f(x) ≡ 0 (mod N)，beta = 1
-
在模 p 上寻找根，且 p 约等于 N^0.5^（RSA 情况），p 是 N 的一个因子，p ≈ √N ≈ N^0.5，beta = 0.5，因为 p ≈ N^0.5，所以 β = 0.5
-
在模 p 上寻找根，但 p 的大小不同：
如果 p ≈ N^0.3^：beta = 0.3
如果 p ≈ N^0.25：beta = 0.25
-
寻找模 N 的小根：beta = 1.0
| 攻击目标 |
模数 |
β |
| 模 N 求根 |
N |
1.0 |
| 模 p（RSA） |
p ≈ N^0.5 |
0.5 |
| 模 p ≈ N^0.3 |
p |
0.3 |
已知 p 高位
知道 p 的前 k 位，记低位为 x，所以 p = p_high * 2^k^ + x，算出 p 的低位 x 后直接用 small_roots
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from Crypto.Util.number import*
p = getPrime(1024)
q = getPrime(1024)
n= p * q
print(p)
p_high = p >> 300#已知高位1024-300bits
pbits = 1024
kbits = pbits - p_high.bit_length()#低位300bits
p_high = p_high << kbits#移动回去把低位空出来
PR.<x> = PolynomialRing(Zmod(n))#多项式环
f = x + p_high
p0=f.small_roots(2**kbits,0.4)[0]
print(p0+p_high)
|
已知 p 高位，q 低位
已知的 p 高位不满足 unknown_bits / p_bits <= 0.44，且知道 q 的低位，低位数 x
解题方法省个流就是：
$$
p_{\text{low}} = p \bmod 2^{x} = \left( n \cdot q_{\text{low}}^{-1} \right) \bmod 2^{x}
$$
然后用 small_roots 算出中间的未知数然后加起来就可以了
1
2
3
4
5
6
7
8
9
10
11
12
13
|
from Crypto.Util.number import getPrime, bytes_to_long
from secret import flag
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 65537
hint1 = p >> 724
hint2 = q % (2 ** 265)
c = pow(bytes_to_long(flag), e, n)
print(hint1)
print(hint2)
print(n)
print(c)
|
q 的低位 q_low
$$
q \bmod 2^{265} = q_{\text{low}}
$$
所以：
$$
q = k \cdot 2^{265} + q_{\text{low}}
$$
两边同时乘 q 可以得到：
$$
n = p \cdot \left( k \cdot 2^{265} + q_{\text{low}} \right) = k \cdot 2^{265} \cdot p + q_{\text{low}} \cdot p
$$
同时除以 q_low：
$$
n \cdot q_{\text{low}}^{-1} = k \cdot 2^{265} \cdot p \cdot q_{\text{low}}^{-1} + p
$$
同时取模 2^265^得到：
$$
p_{\text{low}} = p \bmod 2^{265} = \left( n \cdot q_{\text{low}}^{-1} \right) \bmod 2^{265}
$$
1
2
3
4
5
6
7
8
|
from Crypto.Util.number import*
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
p_low=(n//q_low)%(2**256)
print(p_low)
|
现在有低位 256 和高位 300，所以目前未知位为 459，最多未知位为 1024 * 0.44 = 454，所以要暴力枚举五位
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
from Crypto.Util.number import*
p_high = 1514296530850131082973956029074258536069144071110652176122006763622293335057110441067910479
q_low = 40812438243894343296354573724131194431453023461572200856406939246297219541329623
n = 21815431662065695412834116602474344081782093119269423403335882867255834302242945742413692949886248581138784199165404321893594820375775454774521554409598568793217997859258282700084148322905405227238617443766062207618899209593375881728671746850745598576485323702483634599597393910908142659231071532803602701147251570567032402848145462183405098097523810358199597631612616833723150146418889589492395974359466777040500971885443881359700735149623177757865032984744576285054725506299888069904106805731600019058631951255795316571242969336763938805465676269140733371287244624066632153110685509892188900004952700111937292221969
c = 19073695285772829730103928222962723784199491145730661021332365516942301513989932980896145664842527253998170902799883262567366661277268801440634319694884564820420852947935710798269700777126717746701065483129644585829522353341718916661536894041337878440111845645200627940640539279744348235772441988748977191513786620459922039153862250137904894008551515928486867493608757307981955335488977402307933930592035163126858060189156114410872337004784951228340994743202032248681976932591575016798640429231399974090325134545852080425047146251781339862753527319093938929691759486362536986249207187765947926921267520150073408188188
e = 65537
q_low_inv=pow(q_low,-1,2**265)
p_low = (n*q_low_inv)%(2**265)
print(p_low)
PR.<x> = PolynomialRing(Zmod(n))
p_high=p_high << 724
for i in range(32):
f = p_high + p_low + (x * 32 + i) * (2**265)
f = f.monic()
p = f.small_roots(2**454,0.4)
if p:
x0=int(p[0])
p=(x0*32 + i) * (2**265) + p_high + p_low
break
print(p)
q=n//p
phi=(p-1)*(q-1)
d=pow(e,-1,phi)
print(long_to_bytes(pow(c,d,n)))
|
md 还能有这种报错的，夸张哦 😓
已知密文 m 高位
怎么感觉像照着抄啊我干
m 和 c 的关系是
$$
c = m^e \mod n
$$
又因为：
$$
m = m_{\text{high}} + x \quad (\text{$x$ 是低位未知})
$$
所以把 c 移过来可以变成：
$$
f(x) = (m_{\text{high}} + x)^e - c \equiv 0 \mod n
$$
然后直接套公式秒了
已知 d 的低位求 pq
已知了 d 的低位 d_low 和低位 bits 数 x 还有 e
因为：
$$
ed \equiv 1 \pmod{(p-1)(q-1)}
$$
所以：ed = 1 + k * (p-1) * (q-1)
然后对两边取模 2^x^，所以:
$$
ed_{\text{low}} \equiv 1 + k(p-1)(q-1) \pmod{2^x}
$$
把 q 换成 n/p，这个式子就为
$$
p \cdot ed_{low} \equiv p + k(n \cdot p - p^{2} - n + p) \pmod{2^{x}}
$$
然后 solve_mod 解模方程（sagemath 太好用了家人们）
Franklin-Reiter 相关消息攻击 & Coppersmith’s Short Pad Attack 短填充攻击
攻击原理
由于 m1 和 m2 存在线性关系并且在相同 N 下进行的 RSA 加密，
假设
$$
m_1 = k\ * \ m_2 \ +\ b
$$
且
$$
m_1\ \equiv \ a\ mod \ N\\
m_2\ \equiv \ a\ mod \ N
$$
这样就可以列出两个和 m2 相关的方程
$$
f(x)\ =\ x\ -\ a\\f(x)= k\ * \ x \ +\ b\ -\ a
$$
这样这两个式子取 x = m2 时都会等于 0，在数学意义下有个 (x-m2) 的因式，所以直接取这两个方程的公因数就可以找到 m2
顺便学习一下 sagemath
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
R.<X> = Zmod(n)[]#定义多项式环
.coefficients()#以列表形式返回多项式的常数项（从低项到高项的升序排列，即7x^5+3x^4+4返回[4,3,7]）
.monic()#除以最高项的系数
'''
4x^3+2x^2+x
返回：
x^3+1/2x^2+1/4x
'''
#多项式求公因数用欧几里得算法递归
def gcd(a, b):
if(b == 0):
return a.monic()
else:
return gcd(b, a % b)
|
做下例题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
from Crypto.Util.number import *
from secret import flag
from Crypto.Util.number import *
m1 = bytes_to_long(flag)
N = getPrime(512)*getPrime(512)
e = 17
c1 = pow(m1, e, N)
a = getRandomNBitInteger(512)
b = getRandomNBitInteger(512)
m2 = a * m1 + b
c2 = pow(m2, e, N)
print(f'N={N}', f'a={a}', f'b={b}', f'c1={c1}', f'c2={c2}', sep="\n")
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
N=123659932061175480826793608011321410436349950741155126876095701055301878519455031361569954900678263326118459719432097093055918891948664714258046001339215600541946755989049122600427628642622036472692779340339300158628581419220590868242848311473965406365501747491282544140645468809520929307937285660479491241363
a=12795184347649957548397347648657609712242281197428253341891395348966629724842748696386579533843100833039565312645558384706282291396553602742473087674306336
b=12652561268961103936837420866306660440380907636430718507525953046969196471975210807471094652190751376751348655252244311630569860771118936181419956587387282
c1=51991948160397341594095534046308905334052328129886214140433481879034095448631790463996064234310860642758645828216350970768732856439017324754993220774971081882007838091737307185049230846102962234452369235186705221800322142645874117556212685451861172069436515378795560228077509937484022552758984136308761496373
c2=102367269426206577837660468860715696190840895268468904172938303357188227693435122799965957675733814903345970317009686706066325312156008609593926539768689081990544088825413585508055156925413722623286655819700429518477974133941543843635128782119973290018886257977205103150970429699110833604623614038282346303825
e=17
from Crypto.Util.number import*
def s(N,e,c1,c2,a,b):
R.<X> = Zmod(N)[]
f1 = X^e - c1
f2 = (X*a+ b)^e - c2
return Integer(-(gcd(f1,f2)).coefficients()[0])
def gcd(a, b):
if(b == 0):
return a.monic()
else:
return gcd(b, a % b)
m=s(N,e,c1,c2,a,b)
print(long_to_bytes(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
43
44
45
46
47
48
49
50
51
52
53
54
|
from Crypto.Util.number import *
from secret import flag
num1 = getPrime(512)
num2 = getPrime(512)
while num1<num2 :
num2 = getPrime(512)
ring = RealField(1050)
num3 = ring(num1) /ring(num2)
print("num3=",num3)
p = getPrime(512)
q = getPrime(512)
n=p*q
e=65537
m = bytes_to_long(flag)
c=pow(m,e,n)
print("n=",n)
print("c=",c)
n2 = getPrime(512) * getPrime(512)
e1 = randint(1000,2000)
e2 = randint(1000,2000)
c1 = pow(p+num1,e1,n2)
c2 = pow(p+num2,e2,n2)
q1 = getPrime(512)
leak1 = pow(q+q1,2024,n)
leak2 = pow(q1+2024,q,n)
print("n2=",n2)
print("e1=",e1)
print("e2=",e2)
print("c1=",c1)
print("c2=",c2)
print("leak1=",leak1)
print("leak2=",leak2)
"""
num3= 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n= 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c= 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2= 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1= 1630
e2= 1866
c1= 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2= 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1= 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2= 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192
"""
|
DASTF 的题，先连分数逼近来解开 num1 和 num2，然后用相关消息攻击，情报有误，这是短填充攻击
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
|
num3= 1.36557212221826657073387899060669771982679822943621690677450888408226656788387273887547841291114809989272635809810564202247340711087479554863446719786359395466961253205133910506682801159622545780721946115442033391600881399634390008053822158098121985270501317972263356522400827768601773721146954464269212959784543085
n= 85105083975491693151454182116844944807066048677068373328227644321539783064315677834754866742549592569194223084173286381150626593510265361114796714226058887906219454795525438819082646860141163940340082006344850825956811992304447978369108606993344902286569100146695092703383844402883938506877787042873586279543
c= 8090472119640930864901421058741085326954308673260202542020919764880488559370287585797498390920330336595858609617432370825503480936376306766495089200286004922821787548265246289552343468177624634434613746605553770994437785042510225956023382347023663125411103947669109085411939772215657220674436476279268458980
n2= 101642316595332652021348165259853423287787139517550249986161819826180514401858258316466101056877182367161299111697465439636861942636526396547011727147471566130633614685728563576613692851860684686033186826342178072882901576159305747639645374751566751967096281105148714033096611618024355982220235949274576036321
e1= 1630
e2= 1866
e=65537
c1= 8857135083997055103287497833179378469532619748945804429057682575070405217145941944821968708809563240261403711644389684947851643865895254406194464015430673347359589677809515117412321862622147634752091324365628790687343748145339949310696116239361890881096088375070083053010564890401663562726144984405628773323
c2= 44531030636557714647477473185500183066851251320453194953972504422367649302810396344051696851757189817391648356459225688318373454949578822468293099948132700460437006478679492801335689493431764882835346904225119630026545592437198370606462285405519745361570058335573353886454277790277663038008240372746639859253
leak1= 82301473255013183706458389946960254392188270550712533886416705365418418731488346328643954589202172816597173052792573628245245948345810581701878535280775967863966009605872386693838526935762655380705962833467046779524956212498594045378770790026387120339093736625186401934354434702063802537686761251873173518029
leak2= 43580171648136008789232340619597144591536098696024883687397347933098380327258730482377138309020375265135558484586783368757872008322883985094403855691297725907800406097129735499961231236473313141257901326737291586051506797429883866846199683028143924054925109557329949641367848264351523500925115860458645738192
t=continued_fraction(num3)
for i in range(1000):
num1=t.numerator(i)
if is_prime(num1) and num1.nbits()==512:
num2=t.denominator(i)
print(num1)
print(num2)
break
from Crypto.Util.number import*
def s(n,e1,e2,c1,c2):
R.<X> = Zmod(n)[]
f1 = (X+num1)**e1 - c1
f2 = (X+num2)**e2 - c2
return Integer(-(gcd(f1,f2)).coefficients()[0])
def gcd(a, b):
if(b == 0):
return a.monic()
else:
return gcd(b, a % b)
p=s(n2,e1,e2,c1,c2)
print(p)
q=n//p
d=pow(e,-1,(p-1)*(q-1))
m=pow(c,d,n)
print(long_to_bytes(m))
|
