Posted on Edited on In Word count in article: 9.3k Reading time ≈ 8 mins.

算是很久没打比赛后的第一场认真看题的比赛，就只做出一题比较白给的题，剩下的题要么卡在了错误的方向上，要么就是方法对了实际做的时候不会调参数这些（吃了不理解Coppersmith的大亏，就当是复健的第一次复盘了。

有些题看着论文感觉可行，但没有办法把论文中提到的方法给复现出来……

d3factor

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
from Crypto.Util.number import bytes_to_long, getPrime
from secret import msg
from sympy import nextprime
from gmpy2 import invert
from hashlib import md5

flag = 'd3ctf{'+md5(msg).hexdigest()+'}'
p = getPrime(256)
q = getPrime(256)
assert p > q
n = p * q
e = 0x10001
m = bytes_to_long(msg)
c = pow(m, e, n)

N = pow(p, 7) * q
phi = pow(p, 6) * (p - 1) * (q - 1)
d1 = getPrime(2000)
d2 = nextprime(d1 + getPrime(1000))
e1 = invert(d1, phi)
e2 = invert(d2, phi)

print(f'c = {c}')
print(f'N = {N}')
print(f'e1 = {e1}')
print(f'e2 = {e2}')
'''
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
'''

这道题是最先做的一道题，也是做了最久的一道题，一直以来我都对能使用Coppersmith method的equation不太敏感，这次就是这个问题导致简单的题没有整出结果来。

这题在做的时候其实查到了一篇用格来解决的文章New attacks on RSA with Moduli （查到这篇文章的时候贼兴奋，以为这题就要被我斩于马下了！其实里面采用的构造格的方法就是类似Coppersmith method里的方法！！！但我根本没反应过来，按着文章里的格基一直在调都没有什么好的结果，于是这题就被放在一边了。

赛后看神仙爷爷们轻车熟路的Coppersmith我才反应过来我一直想要复现出来的东西，就是Copper…..

题目里给的两个的生成过程可以看出

并且，对于给出的两个，我们其实是可以很快写出这个equation的（当时做的时候也写出来看了

然后就是关键的点了，关键的地方在于这个，这个是的一个很大的factor了，到这里其实就应该反应过来要用copper求了

求出自然就能求出了，剩下的就是gcd和正常的解密了

一点都不难的题，我就是没有意识到Coppersmith

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from gmpy2 import iroot
from Crypto.Util.number import long_to_bytes
N =  1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
PR.<x> = PolynomialRing(Zmod(N))

f = (e1 * e2) * x - (e2 - e1)
f = f.monic()
delta = int(f.small_roots(X=2^1000,beta=0.5)[0])
p6 = gcd((e1 * e2) * delta - (e2 - e1),N)
p = int(iroot(p6,6)[0])
q = N // p6 // p 
n = p * q
phi = (p-1) * (q-1)
c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
d = inverse_mod(0x10001,phi)
long_to_bytes(pow(c,d,n))
# b"MM is still working on Valentine's Day.You can't be like him."

有个奇怪的问题就是，如果用sage带的small_roots跑上面那个文章给的数据是跑不出答案的。
会不会文章中所使用的方法比small_roots解决这类问题好的多？（可能性不大，因为这个问题本质还是finding small roots？

Orz….

d3qcg

……挺无语的，这题因为没有注意调参数而没做出来，也就是因为对二元copper的模板不够熟悉吧。

使用bivariate polynomials的copper一般可以用https://github.com/defund/coppersmith里的coppersmith.sage

其实univariate的也可以用它，但是在定义PolynomialRing的时候要注意定义成Mutivariate的

1
2
PR.<x> = PolynomailRing(Zmod(N),1)
# difference from PR.<x> = PolynomialRing(Zmod(N))

刚好再学习学习一下Coppersmith的界，具体Coppersmith’s method到底是怎样进行操作的可以看原论文或者V神的这篇文章https://www.anquanke.com/post/id/211028，他的文章一共有三部分真的很详细很有帮助。

这里就复习一下界吧

对于Univariate Polynomials

Given a monic polynomial of degree , modulo an integer of unknown factorization, one can find in time polynomial in all integers such that and .

对于Bivariate Polynomials

Let be an irreducible polynomial in two variables over , of maximum degree in each variable separately. Let and be upper bounds on the desired integer solution , and let . If , then in time polynomial in, one can find all integer pairs such that , and .

这道题的背景是QCG（Quadratic Congruential Generator），具体的定义是这样的

这道题里面没有一次项系数，也就是说这道题的式子是这样的

题目给了以及的高位，让我们求。在这里可以先定义

我们可以将式子，写成

这里其实就能看出是二元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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
from Crypto.Util.number import long_to_bytes
import itertools

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.coefficient_matrix()
    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 []

p = 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347
a = 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101
b = 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833

w0 = 67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833 * 2 ^ 146
w1 = 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422* 2 ^ 146

Fp = GF(p)
b,w0,w1 = map(Fp, [b,w0,w1])
P.<k0, k1> = PolynomialRing(Fp)

f =  a * (w0 + k0) ^ 2 -  w1 + b - k1
roots = small_roots(f, [2^146, 2^146],m=3,d=6)
k0, k1 = roots[0]
# (50712831100361370819145886978385347931029768,9089234402520025586415667640120652372860183)