[DASCTF Apr. X SU战队开局之战] crypto复现

感觉突然啥都不会了,后来拿到官方WP,也没整明白,这官方的WP没有代码只讲了些道理,复现一下也不容易。

1，easySign

这是个自制的签名题。

from secret import r, tfrom Crypto.Util.number import *flag = b'xxx'flag = bytes_to_long(flag)e = 0x10001def gen_keys():p = getPrime(1024)q = getPrime(1024)phi = (p-1)*(q-1)d = inverse(e,phi)n = p*qprint(f'n = {n}')WHATF = (d ** 3 + 3) % phiprint(f'WHATF= {WHATF}')return d, n, WHATFdef easy_sign(n,d):m = flag * pow(r,e**2+d**2,n) % ns = pow(m,d,n) #用d加密用e解密return sdef gift():assert t > 0gift = pow(r,t) - 1#print(t)print(isPrime(gift))d,n,WHATF = gen_keys()gift()sign = easy_sign(n,d)print(f'sign = {sign}')

gen_keys先生成RSA的d，由于e是已知的，给出d以后基本解密不是问题。并给出了

WHATF = d^3 + 3 (mod phi)

签名是用： m= flag * r^(e^2+d^2) (mod n)

这里r未知，但给出一个：gift = pow(r,t) - 1 （t>0,gift是素数）

由于素数只有2是偶数，所以如果r不是2的话一定是奇数再减1就是偶数（t>1时），当t==1时r可以是任意一个素数+1，所以r的取值只能是2或随便什么数。。。猜测是题出漏了，这里是想让r==2

这里式子里没有d^3需要作个变换： 两边乘d次幂

并且sign = m^d

所以这里就能得到flag^d 由于e已知，直接乘e次幂flag^d^e = flag

(这里猜r=2)

n = 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699WHATF = 755087240889590334046954986708873777922173504298348786788869074751070757520891722945513556361467507764131450402966671442424244121924656643178841427758718362448484535111162450064603510761422175670658115091877682811848209224186736564423395085280128648160389325902973399357241712500228460524312636668337376268880231328857279819777556379340525135395752960173737598776223022396553901859711537325809287551279993169349352247872666197605951256802978207414287101960998089985170202927856597220583173218439796589989225339276983821280382381606714573769731164854987904961308101792538780873864733317807544668319589968398141732# 1sign = 12029865785359077271888851642408932941748698222400692402967271078485911077035193062225857653592806498565936667868784327397659271889359852555292426797695393591842279629975530499882434299824406229989496470187187565025826834367095435441393901750671657454855301104151016192695436071059013094114929109806658331209302942624722867961155156665675500638029626815869590842939369327466155186891537025880396861428410389552502395963071259114101340089657190695306100646728391832337848064478382298002033457224425654731106858054291015385823564302151351406917158392454536296555530524352049490745470215338669859669599380477470525863815'''#1, sign = m^d #2, m = flag * r^(e^2 + d^2) 两边取d次幂=> m^d = flag^d * r^(d*e^2 + d^3)=> sign = flag^d * r^(e + d^3) = flag^d * r^(e + WHATF-3)#flag = (flag^d)^e #3, r=2'''from Crypto.Util.number import *fd = sign * pow(pow(2,e+WHATF-3,n),-1,n)flag = pow(fd,e,n)print(long_to_bytes(int(flag)))#DASCTF{RSA_Bl1nd_Signatur3_With_M4th}

2,ECC

这是个椭圆曲线和RSA结合的题，这种叫ECRSA

from Crypto.Util.number import *from secret import flag, p, q, a, b, e1, e2, e3assert isPrime(p) and isPrime(q)assert flag.startswith("DASCTF{") and flag.endswith("}")class ECC():def __init__(self, a, b, p, q, e):self.p, self.q = p, qself.a, self.b = a, bself.N = p * qself.e = eself.Kbits= 8self.Ep = EllipticCurve(IntegerModRing(p), [a, b])self.Eq = EllipticCurve(IntegerModRing(q), [a, b])N1 = self.Ep.order()N2 = 2 * p + 2 - N1N3 = self.Eq.order()N4 = 2 * q + 2 - N3self.d = {( 1, 1): inverse_mod(e, lcm(N1, N3)),( 1, -1): inverse_mod(e, lcm(N1, N4)),(-1, 1): inverse_mod(e, lcm(N2, N3)),(-1, -1): inverse_mod(e, lcm(N2, N4))}self.E = EllipticCurve(IntegerModRing(self.N), [a, b])def enc(self, plaintext):msg_point = self.msg_to_point(plaintext, True)mp = self.Ep(msg_point)mq = self.Eq(msg_point)cp = (self.e * mp).xy()cq = (self.e * mq).xy()cp = (int(cp[0]), int(cp[1]))cq = (int(cq[0]), int(cq[1]))c = (int(crt([cp[0], cq[0]], [self.p, self.q])), \int(crt([cp[1], cq[1]], [self.p, self.q])))c = self.E(c)return c.xy()def dec(self, ciphertext):x = ciphertextw = x^3 + self.a*x + self.b % self.NP.<Yp> = PolynomialRing(Zmod(self.p))fp = x^3 + self.a*x + self.b -Yp^2yp = fp.roots()[0][0]P.<Yq> = PolynomialRing(Zmod(self.q))fq = x^3 + self.a*x + self.b -Yq^2yq = fq.roots()[0][0]y = crt([int(yp), int(yq)], [self.p, self.q])cp, cq = self.Ep((x, y)), self.Eq((x, y))legendre_symbol_p = legendre_symbol(w, self.p)legendre_symbol_q = legendre_symbol(w, self.q)mp = (self.d[(legendre_symbol_p, legendre_symbol_q)] * cp).xy()mq = (self.d[(legendre_symbol_p, legendre_symbol_q)] * cq).xy()return crt([int(mp[0]), int(mq[0])], [self.p, self.q]) >> self.Kbitsdef msg_to_point(self, x, shift=False):if shift:x <<= self.Kbitsres_point = Nonefor _ in range(2 << self.Kbits):P.<Yp> = PolynomialRing(Zmod(self.p))fp = x^3 + self.a*x + self.b - Yp^2P.<Yq> = PolynomialRing(Zmod(self.q))fq = x^3 + self.a*x + self.b - Yq^2try:yp, yq = int(fp.roots()[0][0]), int(fq.roots()[0][0])y = crt([yp, yq], [self.p, self.q])E = EllipticCurve(IntegerModRing(self.p*self.q), [self.a, self.b])res_point = E.point((x, y))return res_pointexcept:x += 1return res_pointecc1 = ECC(a, b, p, q, e1)ecc2 = ECC(a, b, p, q, e2)ecc3 = ECC(a, b ,p, q, e3)gift = p * q * getPrime(1000)secret = bytes_to_long(flag[7:-1].encode())ciphertext1 = ecc1.enc(secret)ciphertext2 = ecc2.enc(secret)ciphertext3 = ecc3.enc(secret)with open("output.txt", "w") as f:f.write(f"e1 = {e1}\n")f.write(f"e2 = {e2}\n")f.write(f"e3 = {e3}\n")f.write(f"gift = {gift}\n")f.write(f"C1 = {ciphertext1}\n")f.write(f"C2 = {ciphertext2}\n")f.write(f"C3 = {ciphertext3}\n")

给了3个e和3个椭圆曲线上的点，我一个gift(则p,q,和一个大因子组成，本来n就分解不了，再加一个因子完全没有意义)

1，椭圆曲线的参数：n,a,b都没有给出。

2，加密是用明文作为点G的x值，C[i]＝e[i]*G

所以第一步是获取参数，原来有个模板：

e1 = 516257683822598401e2 = 391427904712695553e3 = 431785901506020973gift = 10954621221812651197619957228527372749810730943802288293715079353550311138677754821746522832935330138708418986232770630995550582619687239759917418738050269898943719822278514605075330569827210725314869039623167495140328454254640051293396463956732280673238182897228775094614386379902845973838934549168736103799539422716766688822243954145073458283746306858717624769112552867126607212724068484647333634548047278790589999183913C1 = (1206929895217993244310816423179846824808172528120308055773133254871707902120929022352908110998765937447485028662679732041, 652060368795242052052268674691241294013033011634464089331399905627588366001436638328894634036437584845563026979258880828)C2 = (1819289899794579183151870678118089723240127083264590266958711858768481876209114055565064148870164568925012329554392844153, 111024553500529556828399421730507293034887258293545217706113144587284245857391199348874614436072516430081437373324551)C3 = (111217546308077435362856254728870697557150701232647066591711887333673887365379249391867408691423887642725415133046354, 1820636035485820691083758790204536675748006232767111209985774382700260408550258280489088658228739971137550264759084468620)from gmpy2 import *#3个c都是曲线上的点x1,y1 = C1x2,y2 = C2 x3,y3 = C3#求nn = (y1^2 - y2^2 - x1^3 + x2^3) * (x2 - x3) - (y2^2 - y3^2 - x2^3 + x3^3 ) * (x1 - x2)n = gcd(n, gift)#1858284081017011776897142483530706248351014197676168270132930318711536519639284920939350511528325590655669305434894548271#求a,bdef ecc(a, b, x, y):return y ^ 2 - (x ^ 3 + a * x + b)def solve_lin(f):return ZZ(-f[0] / f[1])P.<a, b> = Zmod(n)[]f = ecc(a, b, x1,y1)g = ecc(a, b, x2,y2)h1 = f.sylvester_matrix(g, b).det().univariate_polynomial()h2 = f.sylvester_matrix(g, a).det().univariate_polynomial()a = solve_lin(h1)b = solve_lin(h2)print(a,b)

里边好几个字我都不认识，不过模板存下了就能用：三点求模。后边a,b不懂不过不用模板也能用3点求a,b。

官方WP用的另一种方法，感觉更方便也好理解。（我收藏了）

###############################################三点求参数a,b,p # 根据椭圆曲线表达式构造 groebner_basis() P.<a,b>=PolynomialRing(Zmod(gift))f1 = C1[0]^3 + a*C1[0] + b - C1[1]^2 f2 = C2[0]^3 + a*C2[0] + b - C2[1]^2f3 = C3[0]^3 + a*C3[0] + b - C3[1]^2F = [f1,f2,f3]Ideal = Ideal(F)I = Ideal.groebner_basis()print(I)# 求解参数a b nres=[x.constant_coefficient() for x in I]n = res[2]a = -res[0]%nb = -res[1]%n

后边就是根据3组e,C求G，这个就是ECRSA，比照RSA的共模攻击，求CRT，CRT也支持这样的。

E=EllipticCurve(Zmod(n),[a,b])P1=E(C1)P2=E(C2)P3=E(C3)# 三个e的ECRSA共模攻击g1,s1,t1=xgcd(e1,e2)g2,s2,t2=xgcd(g1,e3)assert g2 == 1M=s2*s1*P1 + s2*t1*P2 + t2*P3from Crypto.Util.number import *print(long_to_bytes(int(M[0])))#b'RSA_0n_ECC_1s_mor3_Ineres7ing\x00'

3,easy_hash

这个题比较难了，没有环境，而且WP上全是字，不大懂，在本地试了一下，大概还有些出入。

import socketserverimport signalfrom Crypto.Util.number import *from random import randintfrom gmpy2 import next_primefrom SECRET import flag banner = br'''_____________________________ ______ /\ __-. /\ __ \ /\ ___\ /\ ___\ /\__ _\ /\ ___\ \ \ \/\ \ \ \ __ \ \ \___ \ \ \ \____ \/_/\ \/ \ \ __\ \ \____- \ \_\ \_\ \/\_____\ \ \_____\ \ \_\ \ \_\ \/____/ \/_/\/_/ \/_____/ \/_____/\/_/ \/_/ '''n0 = 3079808251945220863025498240530054884133704746308462162479889627080155514391987610153873334549377764946092629701g = 91289086035117540959154051117940771730039965839291520308840839624996039016929class LCG():def __init__(self) -> None:self.n = next_prime(2**240)self.a = getRandomNBitInteger(85)self.seed = randint(1, self.n-1)def next(self):self.seed = (self.seed ** 3 * self.a + randint(-2**230, 2**230) + randint(1,100)) % self.nreturn self.seeddef gift():lcg = LCG()outputs = []for i in range(30):outputs.append(int(lcg.next()))return outputs, lcg.agift, a = gift()def hash(msg):key = bin(a)[2:]n = n0msg = list(map(ord,msg))for i in range(len(msg)):if key[i] == '1':n = g * (2 * n + msg[i])else:continuen = n & ((1 << 383) - 1)return (n - 0xdeedbeef114514) % (1 << 100)MENU = br'''<OPTION>'''class Task(socketserver.BaseRequestHandler):def _recvall(self):BUFF_SIZE = 2048data = b''while True:part = self.request.recv(BUFF_SIZE)data += partif len(part) < BUFF_SIZE:breakreturn data.strip()def send(self, msg, newline=True):try:if newline:msg += b'\n'self.request.sendall(msg)except:passdef recv(self, prompt=b'SERVER <INPUT>: '):self.send(prompt, newline=False)return self._recvall()def proof_of_work(self):rounds = 1000pseudo_prime = int(self.recv(prompt=b'[+] Plz Tell Me your number: '))if isPrime(pseudo_prime):self.send(b"\nNo! it's a prime, go away!")self.request.close()for i in range(rounds):if pow(randint(2, pseudo_prime), pseudo_prime - 1, pseudo_prime) != 1:self.send(b"\nYou failed in round " + str(i + 1).encode() + b', bye~~')self.request.close()self.send(b"\nCongratulations, you have passed the proof_of_work!\n")return Truedef handle(self):signal.alarm(300)step1 = self.proof_of_work()if not step1:self.request.close()self.send(banner)self.send(b"\nNew challenge now! Please give me 2 diff strings whose hashes are the same~~")self.send(b'Here is my gift for you: \n' + str(gift).encode())string1 = self.recv().decode()string2 = self.recv().decode()if string1 == string2:self.send(b"\nNo! They are the same one!")self.request.close()if hash(string1) == hash(string2):self.send(b'\nGood job~ Here you are!')self.send(flag)self.send(b"\nConnection has been closed.")self.request.close()class ThreadedServer(socketserver.ThreadingMixIn, socketserver.TCPServer):passclass ForkedServer(socketserver.ForkingMixIn, socketserver.TCPServer):passif __name__ == "__main__":HOST, PORT = '0.0.0.0', 9999print("HOST:POST " + HOST+":" + str(PORT))server = ForkedServer((HOST, PORT), Task)server.allow_reuse_address = Trueserver.serve_forever()

题目很长，大概分3部分：

1，proof_of_work

一般情况下proof就是个工作量，比如爆破个4位hash啥的，但这个不是，它是要求一个1000内无法验伪的伪素数：卡迈尔数。WP里给了伪素数生成方法的说明。这类题原来作过，用这个公式生成伪素数是极其困难的。不过这题并不需要生成，只有你知道一个就行了，这个数是一个300以下base的卡迈尔数，就是不存在300以下的因子。对于1000来说已经足够大了，1000以下全是小因子。所以输入这个数就能过。

p = 29674495668685510550154174642905332730771991799853043350995075531276838753171770199594238596428121188033664754218345562493168782883n = p *(313*(p - 1) + 1)*(353 * (p - 1) + 1)proof_of_work(n)

2，LCG

这个LCG生成30个随机数，生成公式是： f(n)= f(n-1)^3*a + e (mod p)

这是个标准的hnp问题，有个lbc_toolkit有这个函数，官方WP也给出了这个函数构造矩阵的方法，有函数了还整矩阵干啥。

不过这有个问题，不知道官方是不是作了这题，这题给出的

self.n = next_prime(2**240)

非常特殊，会造成LLL算法不出结果。经过测试，这里改成随机一个getPrime(240)数就没问题。

class LCG():def __init__(self) -> None:#self.n = next_prime(2**240)self.n = getPrime(240) #不用原来的pself.a = getRandomNBitInteger(85)self.seed = randint(1, self.n-1)print(self.n,self.a)def next(self):self.seed = (self.seed ** 3 * self.a + randint(-2**60, 2**60) + randint(1,100)) % self.n #return self.seeddef gift():lcg = LCG()outputs = []for i in range(30):outputs.append(int(lcg.next()))return outputs, lcg.aoutputs,a = gift()#－－－－－－－－－－－－－－－－p = 1113328282865438363384064798855439755994226962679762330059112876627863681B = 2^230T = [(i^3)%p for i in outputs[:-1]]A = outputs[1:]sol = hnp(p, T, A, B, verbose=True)print(sol)

说明确实那个p有问题

可以根据这一步求出a或者绕过这一步（非官方预期），所以下边也就非预期了

3，hash

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

这个hash代码比较特殊，他没有对所有位处理，只对key为1的位处理，那么当输入两位的值时，如果key='10.....'也就跟后边无关，两个值只有第1位相同，大概率hash值也相同。并且key的前两位是10的概率也非常大，大概都是50%，所以就输入AA和AB，由于环境及时关闭了，所以只能本地测

v = 0for i in range(10000):a = getRandomNBitInteger(85)if hash('AA') == hash('AB'):v+=1print(v/10000)#4961/10000

确实对于随机的a可以预期得到大概率的正确值。

这个题由于proof可以绕过，hnp可以不作，50%*50%的概率应该很容易爆破成功。