ACTF 2023 部分WP
来自密码手的哀嚎：玩不了一点，太难了。
CRYPTO
MDH
Description
Malin’s Diffile-Hellman Key Exchange.
task.sage
from hashlib import sha256
from secret import flag
r = 128
c = 96
p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fp = GF(p)
def gen():
a1 = random_matrix(Fp, r, c)
a2 = random_matrix(Fp, r, c)
A = a1 * a2.T
return (a1, a2), A
sk_alice, pk_alice = gen()
sk_bob, pk_bob = gen()
shared = (sk_alice.T * pk_bob * sk_alice).trace()
ct = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ int.from_bytes(flag, 'big')
with open('output.txt', 'wb') as f:
f.write(str(ct).encode() + b'\n')
f.write(str(list(pk_alice)).encode() + b'\n')
f.write(str(list(pk_bob)).encode() + b'\n')output.txt
8308943029741424587523612386337754255889681699670071706719724435165094611096603769021839263
[(248911473252706126701034292146541373251616513930062195044617795903221826522, 2006663512374471656012713476848952481708164609054161957903243961884729327, 34477445744870695124522330116853976140397756578144976256418933561356297270, 134510431748375978099734325290614896206741166021565864231628975299374894934, 263052897010932566643732419798564392599203662525075356313352360336696893126, 141993015830421728697942660480086149608207938704594224742919997457007731362, 2884941569385999952542152446419918040970038754772386008722345958209977361, 251929132317823958330447233877195880589103297101688031807949769646459583779, 202402171486986340762120037260332866100215659317408872569460852300216859639, 299869910419680584431600458234987314403629236129755735947187138970557973965, 32123365781587714822724172153965985134547746672138349976513502380627017939,........分析一下：
shared = (sk_alice.T * pk_bob * sk_alice).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:
from hashlib import sha256
p = 308955606868885551120230861462612873078105583047156930179459717798715109629
Fq = GF(p)
f = open("output.txt",'r')
data = f.readlines()
ct = eval(data)
pk_alice = eval(data)
pk_bob = eval(data)
pk_alice = Matrix(Fp,pk_alice)
pk_bob = Matrix(Fq,pk_bob)
shared = (pk_alice.T * pk_bob).trace()
m = int(sha256(str(int(shared)).encode()).hexdigest(), 16) ^^ ct
flag = bytes.fromhex(hex(m))
print(flag)
# ACTF{do_you_know_f0rm2l1n_1s_4w3s0m3!}EasyRSA
Description
EasyRSA
from secret import flag
from Crypto.Util.number import *
def genKey(nbits, dbits):
bbits = (nbits // 2 - dbits) // 2
while True:
a = getRandomNBitInteger(dbits)
b = getRandomNBitInteger(bbits)
c = getRandomNBitInteger(bbits)
p1 = a * b * c + 1
if isPrime(p1):
# print("p1 =", p1)
break
while True:
d = getRandomNBitInteger(dbits)
p2 = b * c * d + 1
if isPrime(p2):
# print("p2 =", p2)
break
while True:
e = getRandomNBitInteger(bbits)
f = getRandomNBitInteger(bbits)
q1 = e * d * f + 1
p3 = a * e * f + 1
if isPrime(q1) and isPrime(p3):
# print("p3 =", p3)
# print("q1 =", q1)
break
while True:
d_ = getRandomNBitInteger(dbits)
if GCD(a * b * c * d * e * f, d_) != 1:
continue
e_ = inverse(d_, a * b * c * d * e * f)
k1 = (e_ * d_ - 1) // (a * b * c * d * e * f)
assert e_ * d_ == (a * b * c * d * e * f) * k1 + 1
q2 = k1 * e * f + 1
q3 = k1 * b * c + 1
if isPrime(q2) and isPrime(q3):
# print("q2 =", q2)
# print("q3 =", q3)
# print("e =", e_)
# print("d =", d_)
break
n1 = p1 * q1
n2 = p2 * q2
n3 = p3 * q3
assert pow(pow(0xdeadbeef, e_, n1), d_, n1) == 0xdeadbeef
assert pow(pow(0xdeadbeef, e_, n2), d_, n2) == 0xdeadbeef
assert pow(pow(0xdeadbeef, e_, n3), d_, n3) == 0xdeadbeef
return(e_, n1, n2, n3)
nbits = 0x600
dbits = 0x210
m = bytes_to_long(flag)
e, n1, n2, n3 = genKey(nbits, dbits)
c = pow(m, e, n1)
print("c =", c)
print("e =", e)
print("n1 =", n1)
print("n2 =", n2)
print("n3 =", n3)
# c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644
# e = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227
# n1 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201
# n2 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181
# n3 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421分析如下：
https://img2023.cnblogs.com/blog/3167109/202311/3167109-20231101140500348-458194193.png
于是有：
https://img2023.cnblogs.com/blog/3167109/202311/3167109-20231101140512071-363423973.png
构造格:
https://img2023.cnblogs.com/blog/3167109/202311/3167109-20231101140523087-150118411.png
调至平衡后，LLL即可得d，exp：
https://img2023.cnblogs.com/blog/3167109/202311/3167109-20231101141042260-1926619981.png
#Sage#from gmpy2 import *c = 63442255298812942222810837512019302954917822996915527697525497640413662503768308023517128481053593562877494934841788054865410798751447333551319775025362132176942795107214528962480350398519459474033659025815248579631003928932688495682277210240277909527931445899728273182691941548330126199931886748296031014210795428593631253184315074234352536885430181103986084755140024577780815130067722355861473639612699372152970688687877075365330095265612016350599320999156644e_ = 272785315258275494478303901715994595013215169713087273945370833673873860340153367010424559026764907254821416435761617347240970711252213646287464416524071944646705551816941437389777294159359383356817408302841561284559712640940354294840597133394851851877857751302209309529938795265777557840238332937938235024502686737802184255165075195042860413556866222562167425361146312096189555572705076252573222261842045286782816083933952875990572937346408235562417656218440227n1 = 327163771871802208683424470007561712270872666244394076667663345333853591836596054597471607916850284565474732679392694515656845653581599800514388800663813830528483334021178531162556250468743461443904645773493383915711571062775922446922917130005772040139744330987272549252540089872170217864935146429898458644025927741607569303966038195226388964722300472005107075179204987774627759625183739199425329481632596633992804636690274844290983438078815836605603147141262181n2 = 442893163857502334109676162774199722362644200933618691728267162172376730137502879609506615568680508257973678725536472848428042122350184530077765734033425406055810373669798840851851090476687785235612051747082232947418290952863499263547598032467577778461061567081620676910480684540883879257518083587862219344609851852177109722186714811329766477552794034774928983660538381764930765795290189612024799300768559485810526074992569676241537503405494203262336327709010421n3 = 473173031410877037287927970398347001343136400938581274026578368211539730987889738033351265663756061524526288423355193643110804217683860550767181983527932872361546531994961481442866335447011683462904976896894011884907968495626837219900141842587071512040734664898328709989285205714628355052565784162841441867556282849760230635164284802614010844226671736675222842060257156860013384955769045790763119616939897544697150710631300004180868397245728064351907334273953201assert n1
页:
[1]