[DASCTF 2023 和amp; 0X401七月暑期挑战赛] crypto

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

ezRSA

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

1.  
   from Crypto.Util.number import *
2.  
   from secret import secret, flag
3.  
   def encrypt(m):
4.  
   return pow(m, e, n)
5.  
   assert flag == b"dasctf{" secret b"}"
6.  
   e = 11
7.  
   p = getPrime(512)
8.  
   q = getPrime(512)
9.  
   n = p * q
10.  
    P = getPrime(512)
11.  
    Q = getPrime(512)
12.  
    N = P * Q
13.  
    gift = P ^ (Q >> 16)
14.  
    print(N, gift, pow(n, e, N))
15.  
    print(encrypt(bytes_to_long(secret)),
16.  
    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即可

1.  
   from Crypto.Util.number import *
2.  
    
3.  
   N = 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377
4.  
   gift = 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034
5.  
   C =14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943
6.  
   C1 = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009
7.  
   C2 =46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991
8.  
    
9.  
   ph = bin(gift)[2:][:16] '0'*(512-16)
10.  
    ph = int(ph,2)
11.  
    x = bin(gift)[2:][17:]
12.  
     
13.  
    def fac(x,tp,tq):
14.  
    if len(x) == 0:
15.  
    return
16.  
    if tp*tq>N:
17.  
    return
18.  
    if N%(tp 1)==0:
19.  
    print(tp 1)
20.  
    return
21.  
     
22.  
    v = x[0]
23.  
    r = x[1:]
24.  
    l = len(r)
25.  
     
26.  
    if (tp (1<<(l 1)))*(tq (1<<(l 17)))<N:
27.  
    print(bin(tp)[:50])
28.  
    print(bin(tq)[:50])
29.  
    print(l)
30.  
    return
31.  
     
32.  
     
33.  
    if v == '0':
34.  
    fac(r, tp, tq)
35.  
    fac(r, tp (1<<l), tq (1<<(l 16)))
36.  
    else:
37.  
    fac(r, tp (1<<l), tq)
38.  
    fac(r, tp, tq (1<<(l 16)))
39.  
     
40.  
    #q第1位为1 x[0]=='0'
41.  
    tq = 1<<511
42.  
    tp = ph (1<<(512-16-1))
43.  
     
44.  
    fac(x,tp,tq)
45.  
     
46.  
    P = 8006847171912577069085166877758626954304824756138758266557706391662987806065132448544117840031499707938227955094109779732609035310252723066470330862622641
47.  
    Q = N//P
48.  
    e = 11
49.  
    #pow(n, e, N) = C
50.  
    n = pow(C,invert(e, (P-1)*(Q-1)), N)
51.  
    #8410363083727227985204019150296233995423906412694890252698371563789022268553444336554986979907257458547381598181369620318848637391220240378808211998052306324620364339595355706922325759625785590466818309839146408927226283350419069859849879835884942537531811470537915106995685907400782213608736735862576031042

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

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

1.  
   def related_message_attack(c1, c2, diff, e, n):
2.  
   PRx.<x> = PolynomialRing(Zmod(n))
3.  
   g1 = x^e - c1
4.  
   g2 = (x*256 diff)^e - c2
5.  
    
6.  
   def gcd(g1, g2):
7.  
   while g2:
8.  
   g1, g2 = g2, g1 % g2
9.  
   return g1.monic()
10.  
     
11.  
    return -gcd(g1, g2)[0]
12.  
     
13.  
    for i in range(5,200):
14.  
    sl = i*8
15.  
    diff = bytes_to_long(b"dasctf{")*2^(sl 8) bytes_to_long(b"}")
16.  
    #print(long_to_bytes(diff))
17.  
    v = related_message_attack(C1, C2, diff, e, n)
18.  
    v = long_to_bytes(int(v))
19.  
    if all(0x20<=k<=0x7f for k in v):
20.  
    print(v)
21.  
     
22.  
     
23.  
    #C0pper_Sm1th_Mak3s_T1ng5_Bet4er
24.  
    #DASCTF{C0pper_Sm1th_Mak3s_T1ng5_Bet4er}

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

ezDHKE

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

1.  
   from Crypto.Util.number import *
2.  
   from Crypto.Cipher import AES
3.  
   from hashlib import sha256
4.  
   from random import randbytes, getrandbits
5.  
   from flag import flag
6.  
    
7.  
   def diffie_hellman(g, p, flag):
8.  
   alice = getrandbits(1024)
9.  
   bob = getrandbits(1024)
10.  
    alice_c = pow(g, alice, p)
11.  
    bob_c = pow(g, bob, p)
12.  
    print(alice_c , bob_c)
13.  
    key = sha256(long_to_bytes(pow(bob_c, alice, p))).digest()
14.  
    iv = b"dasctfdasctfdasc"
15.  
    aes = AES.new(key, AES.MODE_CBC, iv)
16.  
    enc = aes.encrypt(flag)
17.  
    print(enc)
18.  
     
19.  
    def getp():
20.  
    p = int(input("P = "))
21.  
    assert isPrime(p)
22.  
    assert p.bit_length() >= 1024 and p.bit_length() <= 2048
23.  
    g = 2
24.  
    diffie_hellman(g, p, flag)
25.  
     
26.  
    getp()

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

1.  
   #生成一个光滑的p
2.  
   for i in range(10000):
3.  
   p = (i<<1024) 1
4.  
   if isPrime(p):
5.  
   print(p)
6.  
   break

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

1.  
   p = 148489452939627293978440608759173442996844898460634522907853247036287190215343795547617202268308624753445214064773770913426160349040708130179091977708205626736036279968938890838225633390629273742668246518422214765060312463614874340097452229306723297896927521825468282346196425145184245667794004328269609137340417
2.  
   c1 = 32337671148820469354884721878680627943087776320018520617248389988275433963346215288654074154198472771676495991637403129147421171101497963354018354844096794273060545906296157018896783237260047022230620638083846759318811484695846540926994367124430184947526698677779285538625565624947156247074152951743312756558898
3.  
   c2 = 100125377377199556015423607730194729002807695386170530175120140662846677601605544195835925836583392720949191562828593827957478195014427163311908981264349443449690605379501404173514406737162058680920587740024984401964656738087302957612945597870706561007252803178937861059214670505223561011281963364209043930283381
4.  
   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'
5.  
   g = 2
6.  
   #c1->a
7.  
   a = discrete_log(c1, mod(2,p))
8.  
   #a = 20158983366301027231385462171522791692008630121065157717747164036452149107892009689050403369525086905480409091499801236352082118579647633366956409366429848496352342806455041880945139325908254573120825350254007004403366796160711297141324506946321528029629467774779553416023783739410698608276420938661398423969
9.  
   key = sha256(long_to_bytes(pow(c2, a, p))).digest()
10.  
     
11.  
    iv = b"dasctfdasctfdasc"
12.  
    aes = AES.new(key, AES.MODE_CBC, iv)
13.  
    flag = aes.decrypt(enc)
14.  
    #DASCTF{64897937-3972-4190-997e-9440153b94b5}

ezAlgebra

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

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

1.  
   from Crypto.Util.number import getPrime, bytes_to_long
2.  
    
3.  
   def YiJiuJiuQiNian(m, cnt, pad, Le, n):
4.  
   Qi = 1997
5.  
   padm = m pad if Le==1 else m*pad
6.  
   while(cnt):
7.  
   Qi = (pow(padm, cnt, n)) % n
8.  
   cnt -= 1
9.  
   return Qi
10.  
     
11.  
    l = 512
12.  
    m = bytes_to_long(flag)
13.  
    p = getPrime(l)
14.  
    q = getPrime(l//2)
15.  
    r = getPrime(l//2)
16.  
    n = p * q * r
17.  
    t = getrandbits(32)
18.  
    c1 = YiJiuJiuQiNian(t, 4, p, 1, n)
19.  
    c2 = YiJiuJiuQiNian(m, 19, t, 0, q)
20.  
    c3 = YiJiuJiuQiNian(m, 19, t, 1, q)
21.  
    print(f"n = {n}")
22.  
    print(f"c1 = {c1}")
23.  
    print(f"c2 = {c2}")
24.  
    print(f"c3 = {c3}")
25.  
     

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

 当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上求解

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

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

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

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

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

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

1.  
   c2 = 722022978284031841958768129010024257235769706227005483829360633993196299360813
2.  
   c3 = 999691052172645326792013409327337026208773437618455136594949462410165608463231
3.  
   qr = n//p
4.  
   qr = 9401587593485043281387085693038728331569785340080901483099201677893747028639199167409687491770551610282667335758156438520647892729094630693383021219064131
5.  
   P.<m,t>=PolynomialRing(Zmod(qr)) #变量至少2个不然报错
6.  
   f1 = t - 2915836867
7.  
   f2 = 1997
8.  
   f3 = 1997
9.  
   for i in range(1,20):
10.  
    f2 = (m*t)^i
11.  
    f3 = (m t)^i
12.  
    f2 -= c2
13.  
    f3 -= c3
14.  
     
15.  
    F = [f1,f2,f3]
16.  
    I = Ideal(F).groebner_basis()
17.  
    #[m 4558705916889325158299053017836727467132312991392588989486141942761404699250667417401143253218224052455224979673100568513463173709098904359650707695127278, t 9401587593485043281387085693038728331569785340080901483099201677893747028639199167409687491770551610282667335758156438520647892729094630693383018303227264, 87038069032840052005520908272237788908169043580221040711149494083975743478969]
18.  
    res=[x.constant_coefficient() for x in I]
19.  
    q = res[2]
20.  
    m = -res[0]%q
21.  
    tt = -res[1]%q #tt == t

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

1.  
   q = 87038069032840052005520908272237788908169043580221040711149494083975743478969
2.  
   m = 56985796272753226120469211992443340429346162287195965942430959147227534853120
3.  
   for i in range(0x1000000):
4.  
   v = long_to_bytes(m i*q)
5.  
   if all(0x20<=k<0x7f for k in v):
6.  
   print(v,i)
7.  
   break
8.  
    
9.  
   #b'dasctf{ShangPoXiaPoYaSiLeYiQianDuo}' 8751845

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

这篇好文章是转载于：学新通技术网