ACTF 2023 部分WP

来自密码手的哀嚎：
玩不了一点，太难了。
CRYPTO

MDH

Description
Malin’s Diffile-Hellman Key Exchange.

task.sage

1. from hashlib import sha256
2. from secret import flag
4. r = 128
5. c = 96
6. p = 308955606868885551120230861462612873078105583047156930179459717798715109629
7. Fp = GF(p)
9. def gen():
10.     a1 = random_matrix(Fp, r, c)
11.     a2 = random_matrix(Fp, r, c)
12.     A = a1 * a2.T
13.     return (a1, a2), A
15. sk_alice, pk_alice = gen()
16. sk_bob, pk_bob = gen()
17. shared = (sk_alice[0].T * pk_bob * sk_alice[1]).trace()
18. ct = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ int.from_bytes(flag, 'big')
20. with open('output.txt', 'wb') as f:
21.     f.write(str(ct).encode() + b'\n')
22.     f.write(str(list(pk_alice)).encode() + b'\n')
23.     f.write(str(list(pk_bob)).encode() + b'\n')

复制代码

output.txt

1. 8308943029741424587523612386337754255889681699670071706719724435165094611096603769021839263
2. [(248911473252706126701034292146541373251616513930062195044617795903221826522, 2006663512374471656012713476848952481708164609054161957903243961884729327, 34477445744870695124522330116853976140397756578144976256418933561356297270, 134510431748375978099734325290614896206741166021565864231628975299374894934, 263052897010932566643732419798564392599203662525075356313352360336696893126, 141993015830421728697942660480086149608207938704594224742919997457007731362, 2884941569385999952542152446419918040970038754772386008722345958209977361, 251929132317823958330447233877195880589103297101688031807949769646459583779, 202402171486986340762120037260332866100215659317408872569460852300216859639, 299869910419680584431600458234987314403629236129755735947187138970557973965, 32123365781587714822724172153965985134547746672138349976513502380627017939,........

复制代码

分析一下：
shared = (sk_alice[0].T * pk_bob * sk_alice[1]).trace()
也就是说shared = （（a1)T  * b1 * (b2)T * a2 ）.trace()
已知Pk_alice = a1 * (a2)T 和Pk_bob = b1 * (b2)T
线性代数学的好的我们可以根据矩阵的迹的性质：Tr(A) = Tr(AT) ,Tr(AB) = Tr(BA)
因此我们可以把shared 内容交换下顺序得到 shared = （（a1)T  * a2 * (b2)T * b1 ）.trace()
即shared = (Pk_alice.T * Pk_bob).trace()
exp:

1. from hashlib import sha256
3. p = 308955606868885551120230861462612873078105583047156930179459717798715109629
4. Fq = GF(p)
6. f = open("output.txt",'r')
7. data = f.readlines()
9. ct = eval(data[0])
10. pk_alice = eval(data[1])
11. pk_bob = eval(data[2])
13. pk_alice = Matrix(Fp,pk_alice)
14. pk_bob = Matrix(Fq,pk_bob)
16. shared = (pk_alice.T * pk_bob).trace()
18. m = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ ct
19. flag = bytes.fromhex(hex(m)[2:])
20. print(flag)
21. # ACTF{do_you_know_f0rm2l1n_1s_4w3s0m3!}

复制代码

EasyRSA

Description
EasyRSA

1. from secret import flag
2. from Crypto.Util.number import *
5. def genKey(nbits, dbits):
6.     bbits = (nbits // 2 - dbits) // 2
8.     while True:
9.         a = getRandomNBitInteger(dbits)
10.         b = getRandomNBitInteger(bbits)
11.         c = getRandomNBitInteger(bbits)
12.         p1 = a * b * c + 1
13.         if isPrime(p1):
14.             # print("p1 =", p1)
15.             break
17.     while True:
18.         d = getRandomNBitInteger(dbits)
19.         p2 = b * c * d + 1
20.         if isPrime(p2):
21.             # print("p2 =", p2)
22.             break
24.     while True:
25.         e = getRandomNBitInteger(bbits)
26.         f = getRandomNBitInteger(bbits)
27.         q1 = e * d * f + 1
28.         p3 = a * e * f + 1
29.         if isPrime(q1) and isPrime(p3):
30.             # print("p3 =", p3)
31.             # print("q1 =", q1)
32.             break
34.     while True:
35.         d_ = getRandomNBitInteger(dbits)
36.         if GCD(a * b * c * d * e * f, d_) != 1:
37.             continue
38.         e_ = inverse(d_, a * b * c * d * e * f)
39.         k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
40.         assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
41.         q2 = k1 * e * f + 1
42.         q3 = k1 * b * c + 1
43.         if isPrime(q2) and isPrime(q3):
44.             # print("q2 =", q2)
45.             # print("q3 =", q3)
46.             # print("e =", e_)
47.             # print("d =", d_)
48.             break
50.     n1 = p1 * q1
51.     n2 = p2 * q2
52.     n3 = p3 * q3
53.    
54.     assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
55.     assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
56.     assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef
58.     return(e_, n1, n2, n3)
61. nbits = 0x600
62. dbits = 0x210
64. m = bytes_to_long(flag)
65. e, n1, n2, n3 = genKey(nbits, dbits)
66. c = pow(m, e, n1)
68. print("c =", c)
69. print("e =", e)
70. print("n1 =", n1)
71. print("n2 =", n2)
72. print("n3 =", n3)
74. # c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
75. # e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
76. # n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
77. # n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
78. # n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421

复制代码

分析如下：

于是有：

构造格:

调至平衡后，LLL即可得d，exp：

[code]#Sage#from gmpy2 import *c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644e_ = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227n1 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181n2 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421n3 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201assert n1