[DASCTF 2023 & 0X401七月暑期挑战赛] crypto

密码只有3道题，最后一道被卡了，赛后在师傅一点点提示下完成。

Table of Contents

ezRSA

题目很短，分两个RSA一个用小写表示一个用大写表示，小写n用大写加密，大写的给出了P和Q>>16的提示。

from Crypto.Util.number import *
from secret import secret, flag
def encrypt(m):
    return pow(m, e, n)
assert flag == b"dasctf{" + secret + b"}"
e = 11
p = getPrime(512)
q = getPrime(512)
n = p * q
P = getPrime(512)
Q = getPrime(512)
N = P * Q
gift = P ^ (Q >> 16)
print(N, gift, pow(n, e, N))
print(encrypt(bytes_to_long(secret)),
    encrypt(bytes_to_long(flag)))

原来爆破过这种，后来保存了一个外国人写的，现在看来还不如自己写的。

原理很简单：爆破+裁剪

由于xor只有4种情况，对结果0是两个0或者两个1，对1是01或10然后递归下去。

关键在于要裁剪，就是让一些情况提示返回失败，这里也是两种情况，对于已知的tp,tq

如果tp*tq>N或者(tp+(1<<k)-1)*(tq+(1<<k)-1)<N就会直接退出（提前判断一下），然后由于Q只是一部分，直接爆破到N%P==0即可

from Crypto.Util.number import *

N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377 
gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034 
C =14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
C1 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009 
C2 =46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991

ph = bin(gift)[2:][:16] + '0'*(512-16)
ph = int(ph,2)
x = bin(gift)[2:][17:]

def fac(x,tp,tq):
    if len(x) == 0:
        return
    if tp*tq>N:
        return 
    if N%(tp+1)==0:
        print(tp+1)
        return
    
    v = x[0]
    r = x[1:]
    l = len(r)
    
    if (tp+(1<<(l+1)))*(tq+(1<<(l+17)))<N:
        print(bin(tp)[:50])
        print(bin(tq)[:50])
        print(l)
        return
        
        
    if v == '0':
       fac(r, tp, tq)
       fac(r, tp+(1<<l), tq+(1<<(l+16)))
    else:
       fac(r, tp+(1<<l), tq)
       fac(r, tp, tq+(1<<(l+16)))

#q第1位为1 x[0]=='0'
tq = 1<<511
tp = ph + (1<<(512-16-1))

fac(x,tp,tq)

P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
Q = N//P 
e = 11 
#pow(n, e, N) = C 
n = pow(C,invert(e, (P-1)*(Q-1)), N)
#8410363083727227985204019150296233995423906412694890252698371563789022268553444336554986979907257458547381598181369620318848637391220240378808211998052306324620364339595355706922325759625785590466818309839146408927226283350419069859849879835884942537531811470537915106995685907400782213608736735862576031042

求出n以后是个关联信息攻击，只不过平时见到的一般与短填充攻击一起，两个差非常小，而这个非常大。

同时由于flag长度未知，小于n的话只能是5字节，显然不正确需要爆破一下。

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x*256+diff)^e - c2
    
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    
    return -gcd(g1, g2)[0]

for i in range(5,200):
    sl = i*8
    diff = bytes_to_long(b"dasctf{")*2^(sl+8) + bytes_to_long(b"}")
    #print(long_to_bytes(diff))
    v = related_message_attack(C1, C2, diff, e, n)
    v = long_to_bytes(int(v))
    if all(0x20<=k<=0x7f for k in v):
        print(v)


#C0pper_Sm1th_Mak3s_T1ng5_Bet4er
#DASCTF{C0pper_Sm1th_Mak3s_T1ng5_Bet4er}

最后这卡了很几个血，明目写的是小写壳，提示大写壳才行，而这是第1个题，谁知道壳是啥样的。

ezDHKE

这题是个DLP的题，但p是自己输入的。

from Crypto.Util.number import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import randbytes, getrandbits
from flag import flag

def diffie_hellman(g, p, flag):
    alice = getrandbits(1024)
    bob = getrandbits(1024)
    alice_c = pow(g, alice, p)
    bob_c = pow(g, bob, p)
    print(alice_c , bob_c)
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
    iv = b"dasctfdasctfdasc"
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(flag)
    print(enc)

def getp():
    p = int(input("P = "))
    assert isPrime(p)
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
    g = 2
    diffie_hellman(g, p, flag)

getp()

很显然，如果DLP很容易求，他必需是p-1光滑的，所以这里需要生成一个足够光滑的数。爆破一个很小的a, 使 p = a*2^1024 + 1 这样只有a,2两个小因子，直接用discrete_log可以秒求解。

#生成一个光滑的p
for i in range(10000):
    p = (i<<1024)+1
    if isPrime(p):
        print(p)
        break

连接远程输入p得到密文，然后解下即可。这里远程网站又卡了，结果也卡了血。差2分钟

p = 148489452939627293978440608759173442996844898460634522907853247036287190215343795547617202268308624753445214064773770913426160349040708130179091977708205626736036279968938890838225633390629273742668246518422214765060312463614874340097452229306723297896927521825468282346196425145184245667794004328269609137340417
c1 = 32337671148820469354884721878680627943087776320018520617248389988275433963346215288654074154198472771676495991637403129147421171101497963354018354844096794273060545906296157018896783237260047022230620638083846759318811484695846540926994367124430184947526698677779285538625565624947156247074152951743312756558898 
c2 = 100125377377199556015423607730194729002807695386170530175120140662846677601605544195835925836583392720949191562828593827957478195014427163311908981264349443449690605379501404173514406737162058680920587740024984401964656738087302957612945597870706561007252803178937861059214670505223561011281963364209043930283381
enc = b'\x1f\x88\x14\xbc\x8d\x9f\x17\xaa\xac\xa8.\x12\xe5\x1a\xa3-\xe2\x9e]\xd7\xe5F\xcd\x8eu\x8b\x08;\xffi\x15D\x0b\xb6\x83\x80\x01\xed\xbe:\x90E\xd2\xb5\xfa\xbb\xef\xc7'
g = 2
#c1->a
a = discrete_log(c1, mod(2,p))
#a = 20158983366301027231385462171522791692008630121065157717747164036452149107892009689050403369525086905480409091499801236352082118579647633366956409366429848496352342806455041880945139325908254573120825350254007004403366796160711297141324506946321528029629467774779553416023783739410698608276420938661398423969
key = sha256(long_to_bytes(pow(c2, a, p))).digest()

iv = b"dasctfdasctfdasc"
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)
#DASCTF{64897937-3972-4190-997e-9440153b94b5}

ezAlgebra

这个题才是真卡了，赛完才在师傅提示下完成。其实只差这么一点点点点点点点点点点点点点点点。

代码我改了下变量名，好看了一点。

from Crypto.Util.number import getPrime, bytes_to_long

def YiJiuJiuQiNian(m, cnt, pad, Le, n):
    Qi = 1997
    padm = m+pad if Le==1 else m*pad
    while(cnt):
        Qi += (pow(padm, cnt, n)) % n
        cnt -= 1
    return Qi
    
l = 512
m = bytes_to_long(flag)
p = getPrime(l)
q = getPrime(l//2)
r = getPrime(l//2)
n = p * q * r
t = getrandbits(32)
c1 = YiJiuJiuQiNian(t, 4, p, 1, n)
c2 = YiJiuJiuQiNian(m, 19, t, 0, q)
c3 = YiJiuJiuQiNian(m, 19, t, 1, q)
print(f"n = {n}")
print(f"c1 = {c1}")
print(f"c2 = {c2}")
print(f"c3 = {c3}")

这个加密是个公式，当Le==1 时

$c1 = 1997 + \sum_{e=1}^{19} {(a+b)^{e}}$ 当Le==0时是a*b

由于1式只有4次，加密了p,对原题有

c1 = 1997 + (p+t)^4 + … mod n

=> c1 = 1997 + (p+t)^4 +… mod p

=> c1 = 1997 + t^4 + t^3 + t^2 + t mod p

题目对n也成立，所以对这个式子直接用coppersmith在环n上求解

n = 119156144845956004769507478085325079414190248780654060840257869477965140304727088685316579445017214576182010373548273474121727778923582544853293534996805340795355149795694121455249972628980952137874014208209750135683003125079012121116063371902985706907482988687895813788980275896804461285403779036508897592103
c1 = 185012145382155564763088060801282407144264652101028110644849089283749320447842262397065972319766119386744305208284231153853897076876529326779092899879401876069911627013491974285327376378421323298147156687497709488102574369005495618201253946225697404932436143348932178069698091761601958275626264379615139864425
#求t
#对于环p 有 (p+t)^4 + ... + 1997 = c1 mod n => t^4 + t^3 + t^2 + t + 1997 = c1 mod p 对n也成立
P.<x> = PolynomialRing(Zmod(n))
f = x^4 + x^3 + x^2 + x + 1997 - c1
f.small_roots(X=2^32, beta=0.4, epsilon=0.01)

t = 2915836867

再拿对原式，对第2步模p的情况下得到

c1 = 1997 + K*p + t^4 + t^3 + t^2 + t 这里的K*p与n有公因子

#求p
# (p+t)^4 + ... + 1997 = c1 mod p  =>  K*p = c1-1997-t^4 -t^3-t^2-t  与n求公因子得到p
p = gcd(n, c1-1997-t^4 -t^3-t^2-t)
p = 12674045065380963936369006640913707206092165254372327547575287589116533343005456615635388048683828685030860153531390706945709086518510926980644275915726413

这一步以后由于得到p，下步求groebner基时就可以使用n//p ==q*r的环，如果用环n由于太大会解不出来。

这里边有个问题，groebner需要两个参数，而这里只有1个，只写1个的话会报错。所以把已经求出来的t又写上。

c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
qr = n//p 
qr = 9401587593485043281387085693038728331569785340080901483099201677893747028639199167409687491770551610282667335758156438520647892729094630693383021219064131
P.<m,t>=PolynomialRing(Zmod(qr))  #变量至少2个不然报错
f1 = t - 2915836867
f2 = 1997
f3 = 1997
for i in range(1,20):
    f2 += (m*t)^i 
    f3 += (m+t)^i 
f2 -= c2
f3 -= c3

F = [f1,f2,f3]
I = Ideal(F).groebner_basis()
#[m + 4558705916889325158299053017836727467132312991392588989486141942761404699250667417401143253218224052455224979673100568513463173709098904359650707695127278, t + 9401587593485043281387085693038728331569785340080901483099201677893747028639199167409687491770551610282667335758156438520647892729094630693383018303227264, 87038069032840052005520908272237788908169043580221040711149494083975743478969]
res=[x.constant_coefficient() for x in I]
q = res[2]
m = -res[0]%q
tt = -res[1]%q  #tt == t

最后是得到的m要小于真正的flag，所以需要爆破一下，一开始爆破写小了，记下来，爆破需要24位。

q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
m = 56985796272753226120469211992443340429346162287195965942430959147227534853120
for i in range(0x1000000):
    v = long_to_bytes(m+i*q)
    if all(0x20<=k<0x7f for k in v):
        print(v,i)
        break 

#b'dasctf{ShangPoXiaPoYaSiLeYiQianDuo}' 8751845

小本本记下。需要两个变量

文章出处登录后可见！

已经登录？立即刷新

[DASCTF 2023 & 0X401七月暑期挑战赛] crypto

ezRSA

ezAlgebra

相关推荐