DASCTF Apr.2023

$whatF \equiv d^3+3 \mod phi \\ \downarrow\\ (whatF-3)e^3 \equiv 1 \mod phi$

知道 $kphi$ ,类似于e,d,n分解n得到pq。

$msg \equiv m\cdot r^{e^2+d^2} \pmod n \\ sign \equiv msg^d \pmod n$

根据条件 $r^t-1$ 为素数，典型的梅森素数

即 $r = 2$

from random import randint
from gmpy2 import gcd
from Crypto.Util.number import *
n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699
WHATF= 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732
e = 65537
sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815

def divide_pq(e,d,n):
    k = e**3*(WHATF-3) - 1
    while True:
        g = randint(2, n-1)
        t = k
        while True:
            if t % 2 != 0:
                break
            t //= 2
            x = pow(g, t, n)
            if x > 1 and gcd(x-1, n) > 1:
                p = gcd(x-1, n)
                return (p, n//p)



p,q = divide_pq(e,WHATF,n)
phi = (p-1)*(q-1)
d = inverse(e,phi)

msg = pow(sign,e,n)
m = msg*inverse(pow(2,e**2+d**2,n),n) %n
print(long_to_bytes(m))

ECC？

由于三次加密都是用的同一条椭圆曲线，已知三个点，构造三条同余方程

$y_1^2 \equiv x_1^3+ax_1+b \mod gift \\\\ y_2^2 \equiv x_2^3+ax_2+b \mod gift\\\\ y_3^2 \equiv x_3^3+ax_3+b \mod gift$

令 $tmp_i = y_i^2-x_i^3 (i = 1,2,3)$ ,两两作差，得到。

$nn = (tmp_2 - tmp_1)(x_2-x_1)^{-1} \equiv a \mod gift \\\\ nnn = (tmp_3 - tmp_2)(x_3-x_2)^{-1} \equiv a \mod gift$

可以得到 $gcd(nn-nnn,gift) = n$ 。

根据题目大致意思，C是M在椭圆上的倍点。类似与共模攻击，找到一对公钥满足互素。这里我们选e1，e3，那么根据扩展欧几里得可以得到 $te_1 + se_2 = 1$ ,那么就可以得到

$s\cdot C_1 +t\cdot C_2 = (se_1+te_2)M = M$

from Crypto.Util.number import *
from gmpy2 import gcdext
e1 = 516257683822598401
e2 = 391427904712695553
e3 = 431785901506020973
gift = 10954621221812651197619957228527372749810730943802288293715079353550311138677754821746522832935330138708418986232770630995550582619687239759917418738050269898943719822278514605075330569827210725314869039623167495140328454254640051293396463956732280673238182897228775094614386379902845973838934549168736103799539422716766688822243954145073458283746306858717624769112552867126607212724068484647333634548047278790589999183913
C1 = (1206929895217993244310816423179846824808172528120308055773133254871707902120929022352908110998765937447485028662679732041, 652060368795242052052268674691241294013033011634464089331399905627588366001436638328894634036437584845563026979258880828)
C2 = (1819289899794579183151870678118089723240127083264590266958711858768481876209114055565064148870164568925012329554392844153, 1110245535005295568283994217305072930348872582935452177061131445872842458573911993488746144360725164302010081437373324551)
C3 = (1112175463080774353628562547288706975571507012326470665917118873336738873653792420189391867408691423887642725415133046354, 1820636035485820691083758790204536675748006232767111209985774382700260408550258280489088658228739971137550264759084468620)

x1,y1 = C1
x2,y2 = C2
x3,y3 = C3
tmp1 = y1^2 - x1^3
tmp2 = y2^2 - x2^3
tmp3 = y3^2 - x3^3
nn = (tmp2 - tmp1)*inverse(x2-x1,gift)%gift
nnn = (tmp3-tmp2)*inverse(x3-x2,gift)%gift
n = gcd(nn-nnn,gift)
print(n)
a = (tmp2 - tmp1)*inverse(x2-x1,n)%n
b = (tmp1-a*x1)%n

assert y1**2%n == (x1**3+a*x1+b) %n and y2**2%n == (x2**3+a*x2+b) %n  and y3**2%n == (x3**3+a*x3+b) %n

print(gcd(e1,e2))
print(gcd(e1,e3))
print(gcd(e2,e3))

E = EllipticCurve(IntegerModRing(n), [a, b])
C1 = E(C1)
C3 = E(C3)
s,t =  int(gcdext(e1,e3)[1]),int(gcdext(e1,e3)[2])
M = s*C1+t*C3
print(long_to_bytes(int(M[0])))

当然可以直接sage集成好的Groebner基进行化简式子，直接求出n,a,b，没有想到，学一下😋。

from sage.all import* 
gift = 10954621221812651197619957228527372749810730943802288293715079353550311138677754821746522832935330138708418986232770630995550582619687239759917418738050269898943719822278514605075330569827210725314869039623167495140328454254640051293396463956732280673238182897228775094614386379902845973838934549168736103799539422716766688822243954145073458283746306858717624769112552867126607212724068484647333634548047278790589999183913
C1 = (1206929895217993244310816423179846824808172528120308055773133254871707902120929022352908110998765937447485028662679732041, 652060368795242052052268674691241294013033011634464089331399905627588366001436638328894634036437584845563026979258880828)
C2 = (1819289899794579183151870678118089723240127083264590266958711858768481876209114055565064148870164568925012329554392844153, 1110245535005295568283994217305072930348872582935452177061131445872842458573911993488746144360725164302010081437373324551)
C3 = (1112175463080774353628562547288706975571507012326470665917118873336738873653792420189391867408691423887642725415133046354, 1820636035485820691083758790204536675748006232767111209985774382700260408550258280489088658228739971137550264759084468620)

PR.<x> = PolynomialRing(Zmod(gift))

f1 = C1[0]^3 + a*C1[0] + b - C1[1]^2 
f2 = C2[0]^3 + a*C2[0] + b - C2[1]^2
f3 = C3[0]^3 + a*C3[0] + b - C3[1]^2
F  = [f1,f2,f3]
ideal = Ideal(F)
I = ideal.groebner_basis()
print(I)
res=[x.constant_coefficient() for x in I]
n = res[2]
a = -res[0]%n
b = -res[1]%n

babyhash

构造卡迈克尔素数通过proof，具体可以看的这篇博客

hash函数将lcg中的参数a当做秘钥，所以这里就是通过构造矩阵进行格基规约解决lcg中的hnp问题

已知30条同余方程

$s_2 \equiv as_1^3 + x0 \pmod n \\\\ s_3 \equiv as_2^3 + x1 \pmod n \\\\ \vdots\\\\ s_n \equiv as_{n-1}^3 + x_{n-1} \pmod n$

简单变换一下

$-x_1 = as_1^3 - s_2 + k_1n \\\\ -x_2 = as_2^3 - s_3 + k_2n \\\\ \vdots \\\\ -x_{n-1} = as_{n-1}^3 - s_n + k_nn$

令 $A_i = s_i^3,B_i = s_{i+1}$ 构造矩阵

$M = \begin{bmatrix} n & & & & & & \newline & n & & & & & \newline & &\ddots& & & & \newline & & & n & & & \newline A_1 & A_2& \dots & A_{n-1} & 1& & \newline B_2 & B_3& \dots & B_n& & K & \newline \end{bmatrix}$

有

$v \cdot M = \begin{bmatrix} k_1 & k_2 & \cdots & k_n & a & 1 \end{bmatrix} \begin{bmatrix} n & & & & & & \newline & n & & & & & \newline & &\ddots& & & & \newline & & & n & & & \newline A_1&A_2&\dots & A_{n-1} & 1& & \newline B_2&B_3&\dots & B_{n} & & K & \newline \end{bmatrix} = \begin{bmatrix} -x_1 & -x_2 & \cdots & -x_{n-1} & a & K \end{bmatrix} = v_k$

由于这里容器里发送的gift都是同一个列表，这里就不和环境交互了。

from gmpy2 import next_prime
from pwn import remote

re = remote('node4.buuoj.cn',26309)
re.sendline(b'464052305161')
re.recvuntil(b'Here is my gift for you: \n')
gift = eval(re.recvline().strip(b'\n').decode())
print(gift)
re.interactive()


gift  =[127888582359676118752983424994173189295729413661018222863313933491985637, 146090733881314410700324157713154229774626269454998754233361320514011950, 1353358840956653868728084636838071227218294186301428178999470983094568459, 726700391861898078130441691662813907316458172347503150569750931513604223, 752082000095840500700434986805650416251445996393711657964599508250405492, 1050273071033262842048721517673353167687235050201901753702914060635255374, 1476818794371895540406817054588840384039702965193695043112348298202492133, 1316412684753985906500461850753036451967122094995444281764947727097033743, 58976887259426255572923351490404284536619266944122199824100784046956988, 532479952217833389164514034994841245378975324523436658805370425486142076, 779590948240143869742258029596223725153215524177838409693388106825447549, 744706075985710924110067948547457202960212350958288192402068355271025102, 271188220659566363516088759365428952520526632991023485224300336947552455, 1089544165826390964327266992945613107595972660575602708036735990393106097, 226445417089192422351971965089887078012717142904837670810597279194984651, 1483816580458044527101873138142302590248227811655904930752611429292033660, 1513345809756540901946415999707800615948525105044945791962011554532676749, 638236777134329877013405839747219402488595476407998627958657715556463252, 577041759603124343853568911819754171221943102554766451338553652264503132, 1678178468428760726460866951891160159172093617822839462870988171375265003, 938997058499793363050978504974158966998658614576555797304139128607546992, 1179091856946071760948878726512069247343248268758292198913984677947170934, 1188822199515620704612499260249109243513606753864704336984722337976407368, 1562635443661276376556746887025471726648159362917474435168312345196136908, 21026790569974478215220800917821974063183437644780395662878806120738652, 1402058748928101554188338307339090940738255485004126955304763433600826432, 1198432172010120723985892271536430890375062989513505440441039432542064044, 376523467502825223619618177262889993853028785367837487137035635842828456, 790965195986552237915311613715035040953514404445184573988322166592394101, 148550381084412153135120484670762547707425349152682108852265331302181488]
n = next_prime(2**240)
K = 2^230
#len(gift) = 30
M1 = list(matrix(ZZ,31,31))
M1[-1][-1] = K
M1[-2][-2] = 1

for i in range(len(gift)-1):
    M1[i][i] = n
    M1[-1][i] = gift[i+1]
    M1[-2][i] = gift[i]^3

M1 = matrix(ZZ,M1)

res = M1.LLL()[0]
a = -res[-2]

由于这里没有长度限制,可以直接构造长度为2的🤣。

验证一下

n0 = 30798082519452208630254982405300548841337042015746308462162479889627080155514391987610153873334549377764946092629701
g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
a = 37624142806112008072206555
def hash(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)

print(hash('10'))
print(hash('11'))

#96839260258612377374047991623
#96839260258612377374047991623

babyhash_revenge

前面部分参考babyhash，这里主要复现一下通过格基规约求解哈希碰撞的问题。

def check(str1,str2):
    key = bin(a)[2:]
    test = []
    for i in range(len(key)):
        if key[i] == '0':
            test.append(str1[i] == str2[i])
    return all(test)

def hash(msg):
    key = bin(a)[2:]
    n = n0
    msg = list(map(ord,msg))
    for i in range(len(msg)):
        if key[i] == '1':
            n = g * (2 * n + msg[i])
        else:
            continue
        n = n & ((1 << 383) - 1)
    return (n - 0xdeedbeef114514) % (1 << 100)

通过hash我们得出递推式

$n_1 \equiv 2gn_0 +m_1 \mod 2^{100} \\ n_2 \equiv 2gn_1+m_2 = 4g^2n_0 +2gm_1 + m_2 \mod 2^{100}\\ n_3 \equiv 2gn_2 +m_3 = 8g^3n_0 +4g^2m_1+2gm_2+m3 \mod 2^{100}\\ \vdots\\ n_k = \sum_{i=0}^k2^{k-i}g^{k-i}m_{i}$

根据题意知道，我们要构造两个hash值一样的字符串，所以满足以下条件。生成方式同上，令msg1为s，msg2为t,两式相减得到

$\sum_{i=1}^ks_i2^{k-i}g^{k-i+1} \equiv \sum_{i=1}^kt_i2^{k-i}g^{k-i+1} \mod 2^{100}\\ \Downarrow \\ \sum_{i=1}^k(s_i-k_i)2^{k-i}g^{k-i+1} \equiv 0 \mod 2^{100} \\ \Downarrow \\ \sum_{i=1}^k(s_i-k_i)2^{k-i}g^{k-i+1} -l\cdot 2^{100} = 0$

由check函数得到，私钥a二进制串的0的对应位置字符全相同时，才能完成碰撞。

由此，我们构造矩阵

$\begin{bmatrix} 1 & 0 & 0&\cdots & 0 & g^{k}2^{k-1}\\ 0 & 1 & 0&\cdots & 0 & g^{k-1}2^{k-2} \\ 0 & 0 & 1 & 0 & 0& g^{k-i+1}2^{k-i}\\ \vdots & \vdots & \ddots &\vdots & \vdots &\vdots\\ 0 & 0 & 0 & 0 & 1& g \\ 0 & 0 & 0 & 0 & 0 & 2^{100} \end{bmatrix}$

g = 91289086035117540959154051117940771730039965839291520308840839624996039016929
key = bin(a)[2:]
n = key.count("1")
M = list(matrix(ZZ,n+1,n+1))

for i in range(n):
    M[i][i] = 1

for i in range(n):
    M[i][-1] = g^(n-i)*2^(n-i-1)
M[-1][-1] = 100

M = matrix(ZZ,M)
res2 = M.LLL()

根据题意构造字符串

s1=''
s2=''
L = res2[-1]
for i in range(len(L)):
    for j in range(40,126):
        if 40<(j+L[i])<126:
            s1+=chr(j)
            s2+=chr(j+L[i])
            break
            
#可打印的字符串

h1 = ''
h2 = ''
c1 = 0
c2 = 0

for i in range(len(key)):
    if key[i] == '1':
        h1 = h1 + s1[c1]
        h2 = h2 + s2[c1]
        c1 += 1
    else:
        h1 = h1 + '*'
        h2 = h2 + '*'
        
print(h1)
print(h2)
print(h1 == h2)
print(check(h1,h2))
print("hash(h1) = " ,hash(h1))
print("hash(h2) = " ,hash(h2))
#DASCTF{S0rry_But_this_1s_My_revenge}