coppersmith学习

发表于 更新于 阅读次数： 本文字数： 10k 阅读时长 ≈ 19 分钟

好久好久没有更新博客了😭最近确实懈怠了一点，还有就是在了解一些web方向的内容所以密码看的比较少了。还是进入今天的正题吧，如标题所见是对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
39
40
41
42
43
44
45
# 已知 N 和 p 的高位 p_high，缺失 kbits 位
N = ...
p_high = ...  # 高位部分（左对齐）
kbits = ...   # 缺失的位数

R.<x> = PolynomialRing(Zmod(N))
f = p_high + x  # 高位已知
roots = f.monic().small_roots(X=2^(kbits+1), beta=0.4,epsilon=0.03)
if roots:
    p = int(p_high + roots[0])
    print("p =", p)
    print("q =", N // p)




# 已知 N 和 p ≡ p_low mod 2^k
N = ...
p_low = ...
k = ...  # 低位位数

R.<x> = PolynomialRing(Zmod(N))
f = p_low + x * 2^k  # 低位已知
roots = f.monic().small_roots(X=2^(k+1), beta=0.4,epsilon=0.03)
if roots:
    p = int(p_low + roots[0] * 2^k)
    print("p =", p)
    print("q =", N // p)





N = ...
e = ...
c = ...
m0 = ...  # 已知部分，例如 m0 = bytes_to_long(b"flag{")
k = ...   # 未知位数

R.<x> = PolynomialRing(Zmod(N))
f = (m0 + x)^e - c
roots = f.small_roots(X=2^k, beta=1/e)
if roots:
    m = int(m0 + roots[0])
    print(long_to_bytes(m))

示例1—math_problem

这里以2025-L3HCTF的math_problem为例

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
import gmpy2
from gmpy2 import *
from Crypto.Util.number import *
from random import randint
from gmpy2 import invert
from scret import flag

def myfunction(num):
    output = 0
    output=num**3
    return output

if __name__ == '__main__':
    flag_len = len(flag)
    p, q = getPrime(512), getPrime(512)

    while True:
        r = getPrime(512)
        R = bytes_to_long(str(r).encode())
        if isPrime(R):
            break

    n = p * q * r
    hint1 = R * r
    mod = myfunction(n)
    hint2 = pow(3*n+1, p % (2 ** 400), mod)
    m = bytes_to_long(flag)
    c = pow(m, 65537, n)

    print('All data:')
    print(f'n = {n}')
    print(f'c = {c}')
    print(f'hint1 = {hint1}')
    print(f'hint2 = {hint2}')


'''
All data:
n = 1031361339208727791691298627543660626410606240120564103678654539403400080866317968868129842196968695881908504164493307869679126969820723174066217814377008485456923379924853652121682069359767219423414060835725846413022799109637665041081215491777412523849107017649039242068964400703052356256244423474207673552341406331476528847104738461329766566162770505123490007005634713729116037657261941371410447717090137275138353217951485412890440960756321099770208574858093921
c = 102236458296005878146044806702966879940747405722298512433320216536239393890381990624291341014929382445849345903174490221598574856359809965659167404530660264493014761156245994411400111564065685663103513911577275735398329066710295262831185375333970116921093419001584290401132157702732101670324984662104398372071827999099732380917953008348751083912048254277463410132465011554297806390512318512896160903564287060978724650580695287391837481366347198300815022619675984
hint1 = 41699797470148528118065605288197366862071963783170462567646805693192170424753713903885385414542846725515351517470807154959539734665451498128021839987009088359453952505767502787767811244460427708303466073939179073677508236152266192609771866449943129677399293427414429298810647511172104050713783858789512441818844085646242722591714271359623474775510189704720357600842458800685062043578453094042903696357669390327924676743287819794284636630926065882392099206000580093201362555407712118431477329843371699667742798025599077898845333
hint2 = 10565371682545827068628214330168936678432017129758459192768614958768416450293677581352009816968059122180962364167183380897064080110800683719854438826424680653506645748730410281261164772551926020079613841220031841169753076600288062149920421974462095373140575810644453412962829711044354434460214948130078789634468559296648856777594230611436313326135647906667484971720387096683685835063221395189609633921668472719627163647225857737284122295085955645299384331967103814148801560724293703790396208078532008033853743619829338796313296528242521122038216263850878753284443416054923259279068894310509509537975210875344702115518307484576582043341455081343814378133782821979252975223992920160189207341869819491668768770230707076868854748648405256689895041414944466320313193195829115278252603228975429163616907186455903997049788262936239949070310119041141829846270634673190618136793047062531806082102640644325030011059428082270352824026797462398349982925951981419189268790800571889709446027925165953065407940787203142846496246938799390975110032101769845148364390897424165932568423505644878118670783346937251004620653142783361686327652304482423795489977844150385264586056799848907
'''

思路：首先由hint1和n取最大公因数可以解出r（虽然这个时候把r当成n来用，$\phi(n)=r-1$,用rsa就直接可以解出来了，算是非预期吧）预期做法就是对hint2转换可以得到p的低400位然后coppersmith解出p从而解题。

令$k=p \mod 2^{400}$,$hint2=(1+3n)^k \mod n^3$,由二项式展开再消去带有$n^3$的因子的项化解完就是这样

$hint2 \equiv 1 + 3kn + \frac{9}{2}k(k-1)n^2 \pmod{n^3}$，$(hint2-1)//n\equiv 3k+\frac{9}{2}k(k-1)n \pmod{n^2}$,让$(hint2-1)//n=h$,然后再模n，$h \equiv3k \mod n$左右乘3的逆元就可以得到k即p的低四百位。

exp:

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 math import gcd
from Crypto.Util.number import *
import gmpy2
n = 1031361339208727791691298627543660626410606240120564103678654539403400080866317968868129842196968695881908504164493307869679126969820723174066217814377008485456923379924853652121682069359767219423414060835725846413022799109637665041081215491777412523849107017649039242068964400703052356256244423474207673552341406331476528847104738461329766566162770505123490007005634713729116037657261941371410447717090137275138353217951485412890440960756321099770208574858093921
c = 102236458296005878146044806702966879940747405722298512433320216536239393890381990624291341014929382445849345903174490221598574856359809965659167404530660264493014761156245994411400111564065685663103513911577275735398329066710295262831185375333970116921093419001584290401132157702732101670324984662104398372071827999099732380917953008348751083912048254277463410132465011554297806390512318512896160903564287060978724650580695287391837481366347198300815022619675984
hint1 = 41699797470148528118065605288197366862071963783170462567646805693192170424753713903885385414542846725515351517470807154959539734665451498128021839987009088359453952505767502787767811244460427708303466073939179073677508236152266192609771866449943129677399293427414429298810647511172104050713783858789512441818844085646242722591714271359623474775510189704720357600842458800685062043578453094042903696357669390327924676743287819794284636630926065882392099206000580093201362555407712118431477329843371699667742798025599077898845333
hint2 = 10565371682545827068628214330168936678432017129758459192768614958768416450293677581352009816968059122180962364167183380897064080110800683719854438826424680653506645748730410281261164772551926020079613841220031841169753076600288062149920421974462095373140575810644453412962829711044354434460214948130078789634468559296648856777594230611436313326135647906667484971720387096683685835063221395189609633921668472719627163647225857737284122295085955645299384331967103814148801560724293703790396208078532008033853743619829338796313296528242521122038216263850878753284443416054923259279068894310509509537975210875344702115518307484576582043341455081343814378133782821979252975223992920160189207341869819491668768770230707076868854748648405256689895041414944466320313193195829115278252603228975429163616907186455903997049788262936239949070310119041141829846270634673190618136793047062531806082102640644325030011059428082270352824026797462398349982925951981419189268790800571889709446027925165953065407940787203142846496246938799390975110032101769845148364390897424165932568423505644878118670783346937251004620653142783361686327652304482423795489977844150385264586056799848907

r = gcd(n, hint1)
h=(hint2-1)//n
p_low=(h*inverse(3,n))%n

kbits = 512-400 
R.<x> = PolynomialRing(Zmod(n))
f = x*2^400 + p_low
roots = f.monic().small_roots(X=2^kbits, beta=0.2, epsilon=0.03)
x0 = roots[0]
p = int(p_low + x0*2^400)
q=n//p//r
e=65537
d = inverse(e,(p-1)*(q-1)*(r-1))
m = pow(c,d,n)
print(long_to_bytes(m))
#L3HCTF{1s_4h1s_r3a11y_m4th?}

示例2—SCTF2024—-signin

参考https://tangcuxiaojikuai.xyz/post/146254b2.html

其中Φ的构造是一模一样的，所以直接套用脚本就解出了，后来看好像还可以通过连分数的方式解题。

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
from Crypto.Util.number import *
from gmpy2 import *
import itertools
from hashlib import md5
def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()
    R = f.base_ring()
    N = R.cardinality()
    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)
    G = Sequence([], f.parent())
    for i in range(m + 1):
        base = N ^ (m - i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = base * prod(map(power, f.variables(), shifts))
            G.append(g)
    B, monomials = G.coefficients_monomials()
    monomials = vector(monomials)
    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)
    B = B.dense_matrix().LLL()
    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1 / factor)
    H = Sequence([], f.parent().change_ring(QQ))
    for h in filter(None, B * monomials):
        H.append(h)
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            roots = []
            for root in I.variety(ring=ZZ):
                root = tuple(R(root[var]) for var in f.variables())
                roots.append(root)
            return roots
    return []
n = 32261421478213846055712670966502489204755328170115455046538351164751104619671102517649635534043658087736634695616391757439732095084483689790126957681118278054587893972547230081514687941476504846573346232349396528794022902849402462140720882761797608629678538971832857107919821058604542569600500431547986211951
e = 334450817132213889699916301332076676907807495738301743367532551341259554597455532787632746522806063413194057583998858669641413549469205803510032623432057274574904024415310727712701532706683404590321555542304471243731711502894688623443411522742837178384157350652336133957839779184278283984964616921311020965540513988059163842300284809747927188585982778365798558959611785248767075169464495691092816641600277394649073668575637386621433598176627864284154484501969887686377152288296838258930293614942020655916701799531971307171423974651394156780269830631029915305188230547099840604668445612429756706738202411074392821840

R.<x,y>=PolynomialRing(Zmod(e))
f = 1 + x*(n^2-n+1 + (n+1)*y + y^2)
res = small_roots(f, (2^256,2^512), m=2, d=3)
pplusq = int(res[0][1])
pminusq = iroot(pplusq^2-4*n,2)[0]
p = (pplusq + pminusq) // 2
q = n // p
bp = long_to_bytes(int(p))
FLAG1 = 'SCTF{'+md5(bp).hexdigest()+'}'
print(FLAG1)
bq = long_to_bytes(int(q))
FLAG2 = 'SCTF{'+md5(bq).hexdigest()+'}'
print(FLAG2)