D^3CTF2022

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
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}')

解析：

399.pdf (iacr.org)

即利用$e_1*e_2*(d1-d2)≡e_2-e_1\ mod\ φ(N)≈e_2-e1\ mod\ N$，求解方程$e_1*e_2*x - (e_2-e_1) = 0$ 在模N下的解。

（貌似sage中未知数x前系数得为1）

另外这里的c长度远小于N的长度，故解密时$n=p*q$。

sage

1
2
3
4
5
6
7
8
9
10
import gmpy2

N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
a = (e2-e1)*gmpy2.invert(e1*e2,N)
R.<x> = PolynomialRing(Zmod(N),implementation='NTL')
f = x-a
x0 = f.small_roots(X = 2^1000,beta = 0.4)
print(x0)

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import gmpy2
from Crypto.Util.number import *
from hashlib import md5

c = 2420624631315473673388732074340410215657378096737020976722603529598864338532404224879219059105950005655100728361198499550862405660043591919681568611707967
N = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494154077020472814706123209865769048722380888175401791873273850281384147394075054950169002165357490796510950852631287689747360436384163758289159710264469722036320819123313773301072777844457895388797742631541101152819089150281489897683508400098693808473542212963868834485233858128220055727804326451310080791
e1 = 425735006018518321920113858371691046233291394270779139216531379266829453665704656868245884309574741300746121946724344532456337490492263690989727904837374279175606623404025598533405400677329916633307585813849635071097268989906426771864410852556381279117588496262787146588414873723983855041415476840445850171457530977221981125006107741100779529209163446405585696682186452013669643507275620439492021019544922913941472624874102604249376990616323884331293660116156782891935217575308895791623826306100692059131945495084654854521834016181452508329430102813663713333608459898915361745215871305547069325129687311358338082029
e2 = 1004512650658647383814190582513307789549094672255033373245432814519573537648997991452158231923692387604945039180687417026069655569594454408690445879849410118502279459189421806132654131287284719070037134752526923855821229397612868419416851456578505341237256609343187666849045678291935806441844686439591365338539029504178066823886051731466788474438373839803448380498800384597878814991008672054436093542513518012957106825842251155935855375353004898840663429274565622024673235081082222394015174831078190299524112112571718817712276118850981261489528540025810396786605197437842655180663611669918785635193552649262904644919
e = 0x10001
x = 1476751427633071977599571983301151063258376731102955975364111147037204614220376883752032253407881568290520059515340434632858734689439268479399482315506043425541162646523388437842149125178447800616137044219916586942207838674001004007237861470176454543718752182312318068466051713087927370670177514666860822341380494148050832401609562069841131611670608508889564903156115171543356434938854665775998209034026454583918190592316542096833683522232732078346945883792128428219017665904611238598515356080299964332522186719141840239751107772675611703424971072329706974374008179321418610378586680426547416872428073384036373775613

tmp = e1*e2*x-(e2-e1)
p6 = gmpy2.gcd(tmp,N)
//print(p6)
p = gmpy2.iroot(p6,6)[0]
//print(p)
q = N//(p**7)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,phi)
m = pow(c,d,p*q)

flag = 'd3ctf{'+md5(long_to_bytes(m)).hexdigest()+'}'
print(flag)

d3qcg

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
from Crypto.Util.number import *
import random
from random import randint
from gmpy2 import *
from secret import flag
import hashlib
assert b'd3ctf' in flag
Bits = 512
UnKnownBits = 146

class QCG():
    def __init__(self,bit_length):
        p = getPrime(bit_length)
        a = randint(0,p)
        c = randint(0,p)
        self._key = {'a':a,'c':c,'p':p}
        self.secret = randint(0,p)
        self.high = []
    def Qnext(self,num):
        return ((self._key['a'])*num**2+self._key['c'])%self._key['p']
    
    def hint(self):
        num = self.secret
        for i in range(2):
            num = self.Qnext(num)
            self.high.append(num>>UnKnownBits)
    def get_key(self):
        return self._key
    def get_hint(self):
        return self.high

Q1 = QCG(Bits)
print(Q1.get_key())
#{'a': 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101, 'c': 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833, 'p': 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347}
Q1.hint()
print(Q1.get_hint())
#[67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833, 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]
enc = bytes_to_long(hashlib.sha512(b'%d'%(secret)).digest())^bytes_to_long(flag)
print(enc)
# 6176615302812247165125832378994890837952704874849571780971393318502417187945089718911116370840334873574762045429920150244413817389304969294624001945527125

解析：

翻译一下大概就是这样。

给出公式如下：
$$
num1 = (a*secret^2+c)%p
$$
以及
$$
num2 = (a*num1^2+c)%p
$$
现有num1>>146和num2>>146的结果[h1,h2]，求secret

需要进行二元Coppersmith。（淦！一元的都不怎么熟悉，还是别人的脚本香😅）

由于最后求的secret需要开平方。（ 由于 $p = 4k + 3$，所以$x= a^{(p+1)//4}\ mod\ p$ ）

Tonelli-Shanks algorithm - Rosetta Code(代码)

Tonelli–Shanks algorithm - HandWiki（理论）

https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm（理论）

Rabin加密算法_Dragon Liu的博客-CSDN博客_rabin算法

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#sage
import itertools
a = 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101
c = 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833
p = 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347
ans = (50712831100361370819145886978385347931029768, 9089234402520025586415667640120652372860183)
high = [67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833, 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]

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 []

R.<x1,x2> = PolynomialRing(Zmod(p))
f = a*(high[0]*(2^146)+x1)^2 + c - (high[1]*2^146+x2)
print(small_roots(f,[2^146, 2^146],m =4,d = 4))

#python
import gmpy2
from Crypto.Util.number import *
import hashlib

def Legendre(a, p):
    return pow(a, (p-1)//2, p)

def Tonelli_Shanks(a, p):
    assert Legendre(a, p) == 1
    if(p % 4 == 3):
        return pow(a, (p+1)//4, p)
    s, q = 0, p-1
    while q & 1 == 0:
        q >>= 1
        s += 1
    for z in range(2, p):
        if Legendre(z, p) == p-1:
            c = pow(z, q, p)
            break
    r, t, m = pow(a, (q+1)//2, p), pow(a, q, p), s
    temp, i = 1, 0
    while t % p != 1:
        i += 1
        temp = pow(t, 2**i, p)
        if temp % p == 1:
            b = pow(c, 2**(m-1-i), p)
            r = r * b % p
            c = b * b % p
            t = t * c % p
            m = i
            i = 0
    return r

a = 3591518680290719943596137190796366296374484536382380061852237064647969442581391967815457547858969187198898670115651116598727939742165753798804458359397101
c = 6996824752943994631802515921125382520044917095172009220000813718617441355767447428067985103926211738826304567400243131010272198095205381950589038817395833
p = 7386537185240346459857715381835501419533088465984777861268951891482072249822526223542514664598394978163933836402581547418821954407062640385756448408431347
ans = (50712831100361370819145886978385347931029768, 9089234402520025586415667640120652372860183)
high = [67523583999102391286646648674827012089888650576715333147417362919706349137337570430286202361838682309142789833, 70007105679729967877791601360700732661124470473944792680253826569739619391572400148455527621676313801799318422]
enc = 6176615302812247165125832378994890837952704874849571780971393318502417187945089718911116370840334873574762045429920150244413817389304969294624001945527125
data = (high[0]<<146) + ans[0]
secret = (data - c) * gmpy2.invert(a, p) % p
secret = Tonelli_Shanks(secret, p)
print(secret)
flag = bytes_to_long(hashlib.sha512(b'%d'%(secret)).digest())^enc
print(long_to_bytes(flag))

d3bug

xor模式下可以从输出推出message的前34位。

假设 mask = '10100100', $R=m_0m_1…m_7$

第一轮xor,得
$$
lastbit_0=\overline m_0⊕m_1⊕\overline m_2⊕m_3⊕m_4⊕\overline m_5⊕m_6⊕m_7
$$
第二轮xor，得
$$
lastbit_1=\overline m_1⊕m_2⊕\overline m_3⊕m_4⊕m_5⊕\overline m_6⊕m_7⊕lastbit_0
$$
化简 $lastbit_1$,得
$$
lastbit_1=\overline m_0⊕1=m_0\
(其中⊕1得个数等于mask中1的个数和位置而定)
$$
剩下的30位可以利用&模式下的输出构造矩阵方程求解。

参考:

AntCTF & Dˆ3CTF 2022 By W&M - W&M Team (wm-team.cn)

Crypto
#RSA #Coppersmith
D^3CTF2022
http://example.com/2022/03/18/CTF/D^3CTF 2022/
作者
gla2xy
发布于
2022年3月18日
许可协议