周六一天都在看 ImaginaryCTF，被 maple 的题虐惨了都。猪脑过载的时候过来隔壁看看 DASCTF 的题，试图放松下脑汁。
ezDHKE
12345678910111213141516171819202122232425262728 |
from Crypto.Util.number import *from Crypto.Cipher import AESfrom hashlib import sha256from random import randbytes, getrandbitsfrom flag import flagdef diffie_hellman(g, p, flag): alice = getrandbits(1024) #私钥XA bob = getrandbits(1024) # 私钥XB # g作为本原根 alice_c = pow(g, alice, p) #p是共享素数 计算公钥YA bob_c = pow(g, bob, p) # 公钥YB print(alice_c , bob_c) # YB的XA次方 是Alice在计算共享密钥 digest获得摘要值 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() |
很简单的一个 DHP，甚至题目代码都还有注释，贴心到家了。
题目的点在于模数 $p$ 是由我们自己控制的，虽然需要满足比特长度在 1024 和 2048 之间，但我们找一个光滑 $p$ ，然后就能解 DLP ，继而解 DHP 了。
123456789101112131415161718192021222324252627 |
from Crypto.Util.number import *from Crypto.Cipher import AESfrom hashlib import sha256from random import choicedef myPrime(bits): while True: n = 2 while n.bit_length() < bits: n *= choice(sieve_base) if isPrime(n + 1): return n + 1A = B = # p = myPrime(1024)p = 515482686852905819026776471764664175154597541766196631808569599693945100129832449512555508593916309509882123983344422623771622319416757571580459907525933456572547127497459096961018073753946157799257464082944083244303912221051154205283779640770766245958565082104682846235618735174419474409835799563673915973399A = Mod(A,p)B = Mod(B,p)key = pow(B,int(discrete_log(A,Mod(2,p))),p)key = sha256(long_to_bytes(key)).digest()c = b''iv = b"dasctfdasctfdasc"aes = AES.new(key, AES.MODE_CBC, iv)flag = aes.decrypt(c)print(flag) |
ezRSA
12345678910111213141516171819 |
from Crypto.Util.number import *from secret import secret, flagdef encrypt(m): return pow(m, e, n)assert flag == b"dasctf{" + secret + b"}"e = 11p = getPrime(512)q = getPrime(512)n = p * qP = getPrime(512)Q = getPrime(512)N = P * Qgift = P ^ (Q >> 16)print(N, gift, pow(n, e, N))print(encrypt(bytes_to_long(secret)), encrypt(bytes_to_long(flag)))# 75000029602085996700582008490482326525611947919932949726582734167668021800854674616074297109962078048435714672088452939300776268788888016125632084529419230038436738761550906906671010312930801751000022200360857089338231002088730471277277319253053479367509575754258003761447489654232217266317081318035524086377 8006730615575401350470175601463518481685396114003290299131469001242636369747855817476589805833427855228149768949773065563676033514362512835553274555294034 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943# 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991 |
题目套了两次，我们先解第二层获取第一层的 $n$，看到 gift = P ^ (Q >> 16)，首先由于 $Q$ 右移了 16 位，所以 $P$ 的高位是泄露出来了的。我们拿着 $P$ 的高位，用 $N$ 除，是能获取 $Q$ 的高位的，本地可以测试一下先
1234567891011121314151617 |
from Crypto.Util.number import *P = getPrime(512)Q = getPrime(512)N = P * Qgift = P ^ (Q >> 16)# gift 泄露了 P 的高16比特Pbar = gift >>(512-16)print(P >>(512-16))print(Pbar)# 根据 Pbar 和 N 获取 Q 的高位Qbar = (N>>(1024-32)) // Pbarprint(Q>>(512-16))print(Qbar) |
但是注意到，我们会发现 Qbar 和 Q>>(512-16) 由于整除会有 1 - 2 的误差，所以为了尽可能减少这些判断的条件，我们索性就把低位抛弃掉，少恢复一些（我这里直接丢了 6 比特）。有了 Q 的高位，我们就能再利用 gift，和它异或，恢复 P 的高位，如此循环往复
12345678910111213141516 |
nc = secret_c = flag_c = pbar = gift >>(512-16)while True:try:qbar = (N>>(1024 - pbar.bit_length()*2))//pbar#print(qbar)qbar = qbar>>6gifts = gift^(qbar<<(512-16-qbar.bit_length()))pbar = gifts >> (512-16-qbar.bit_length())#print(pbar,pbar.bit_length())except:break |
这个粗暴的循环最后会还剩大约6个比特没有恢复，我们再附上一个暴力搜索就可以了。
1234567 |
for i in range(64):if N%((pbar<<6)+i) == 0:p = (pbar<<6)+iq = N//pprint("[+] p =",p)print("[+] q =",q)break |
拿到 P,Q 之后我们就能恢复 n 了
123456 |
e = 11nc = 14183763184495367653522884147951054630177015952745593358354098952173965560488104213517563098676028516541915855754066719475487503348914181674929072472238449853082118064823835322313680705889432313419976738694317594843046001448855575986413338142129464525633835911168202553914150009081557835620953018542067857943d = inverse(e,(p-1)*(q-1))n = pow(nc,d,N)print(n) |
注意到一个问题，就是我们算出 $n$ 之后，最好拿去 factordb 查一下，我们会发现这个直接出来的 $n$ 有一些小因子（甚至还是一个偶数），所以真正的 $n$ 应该比 $N$ 大，所以这里我们还要再 $n+N$ 一下，再拿去差就是啥也查不到了。
接下来我们需要解第一层，第一层的问题总结起来很简单，就是两个式子$$f1: flag^e \equiv c_1 \pmod n$$
$$f2:secret^e \equiv c_2 \pmod n$$
其中明文相关，flag == b"dasctf{" + secret + b"}"，可能部分选手会不知道怎么用数字表示 $flag$ 和 $secret$ 的关系，可以分开来理解，
如果 flag == secret + b"}" 那么我们知道一个字符占一个字节，表示在十进制上，就是把 $secret$ 向左移动一个字节，其实也就是 $256 \cdot secret+125$。
低位很好表示，那么高位呢？如果我们知道 secret 的长度，其实就是 "dasctf{" 向左移动 secret 的长度 + 1 个字节，也就是 $dasctf \cdot 256^{len(secret)+1} $
因此结合起来，我们就可以将两条式子表示为
12 |
f1 = (bytes_to_long(b"dasctf{" + b"\x00"*i + b"}") + 256*x)^11 - flag_c# i 表示 secret 的长度, x 表示 secretf2 = x^11 - secret_c |
然后就是明文相关攻击了，我们知道 $x=secret$ 肯定是这两个方程的解，于是这两个式子肯定有公因式 $(x-secret)$
123456789101112131415161718 |
from Crypto.Util.number import *def GCD(a, b): if(b == 0): return a.monic() else: return GCD(b, a % b)N = 83410392685813224685786027640778560521035854332627839979281105731457044069408118952629284089869335506983096270269822559619624906180108256504440296527471536363057103101146262613593336072556587341466840510200003498265457285439149541137127199088938421905041387224795918868443175561632999479925818053898100117419R.<x> = Zmod(N)[]secret_c = 69307306970629523181683439240748426263979206546157895088924929426911355406769672385984829784804673821643976780928024209092360092670457978154309402591145689825571209515868435608753923870043647892816574684663993415796465074027369407799009929334083395577490711236614662941070610575313972839165233651342137645009flag_c = 46997465834324781573963709865566777091686340553483507705539161842460528999282057880362259416654012854237739527277448599755805614622531827257136959664035098209206110290879482726083191005164961200125296999449598766201435057091624225218351537278712880859703730566080874333989361396420522357001928540408351500991for i in range(40):f1 = (bytes_to_long(b"dasctf{" + b"\x00"*i + b"}") + 256*x)^11 - flag_cf2 = x^11 - secret_cif (N-GCD(f1,f2).coefficients()[0]) != N-1:print(long_to_bytes(int(N-GCD(f1,f2).coefficients()[0])))# b'C0pper_Sm1th_Mak3s_T1ng5_Bet4er' |
EzAlgebra
123456789101112131415161718192021222324 |
from Crypto.Util.number import getPrime, bytes_to_longdef YiJiuJiuQiNian(Wo, Xue, Hui, Le, Kai): Qi = 1997 Che = Wo+Hui if Le==1 else Wo*Hui while(Xue): Qi += (pow(Che, Xue, Kai)) % Kai Xue -= 1 return Qil = 512m = bytes_to_long(flag)p = getPrime(l)q = getPrime(l//2)r = getPrime(l//2)n = p * q * rt = 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}") |
看到这个函数名字就知道是 1997年（不知道的朋友可以看一下前面 2023CCTF 的推文，或者 ctftime 上搜一下） 的队友整活了。
抛开“混淆”的过程，我们可以把题目归结为两个问题，首先第一个，
我们有 $c \equiv (t+p)^4+(t+p)^3+(t+p)^2+(t+p)+1997 \pmod n $
那么看到式子 degree 怎么低，又有 $p$，很难不去用 copper 啊
我们有 $c \equiv t^4+t^3+t^2+t+1997 \pmod p$
于是
12345678 |
N = 54743202946161502811856295720870810456365343228950644705855322505182442571262980076941089058115540911930788333918940031879968906218781504935426145280173361374496692033334841657192812883322298846746060682411659733228146767637511270445829110291022551957289461462065489646257622668554123931913354561022893455953c = 16947792380653343668183074418719189429237241437366092930083218707643531284331359041557134961815270258682795684022186373763539789618707429809410930104661863616531800497066024257733632977939092179342185663603369251482529295279126585001466395251284374970736807376806433944629258377318039254703920331585415058927ZmodN = Zmod(N)P.<x> = PolynomialRing(ZmodN)f = x^4 + x^3 + x^2 + x + 1997 - c x0 = f.small_roots(X=2^32, beta=0.4)[0]t = x0print("t: ", t) |
有了 $t$ 之后还是两个式子
$c_2 \equiv \sum_{i=1}^{19} (m+t)^{i} \pmod q$
$c_3 \equiv \sum_{i=1}^{19} (m\cdot t)^{i} \pmod q$
一个是加，一个是乘，但是和第二题的思路想法还是一样的，$x=m$ 肯定是这两个式子的根，所以给他们用一下 $GCD$
1234567891011121314151617181920 |
def GCD(a, b): if(b == 0): return a.monic() else: return GCD(b, a % b)N = 54743202946161502811856295720870810456365343228950644705855322505182442571262980076941089058115540911930788333918940031879968906218781504935426145280173361374496692033334841657192812883322298846746060682411659733228146767637511270445829110291022551957289461462065489646257622668554123931913354561022893455953c2 = 55877575842944488536738260741145576196064055314256851119903269638247167570517c3 = 24752910240512109387212015792618368998146452177596723408887013541065473659025P.<x> = PolynomialRing(Zmod(N))f1 = 1997f2 = 1997t = 4035619213for i in range(1,20): f1 += (x+t)^i f2 += (x*t)^if1 -= c3f2 -= c2GCD(f1,f2) |
然后我们会得到一个报错 ZZ_p: division by non-invertible element，为啥呢？因为式子是在模 $q$ 下的，我们是在模 $n$ 的，所以，我们在 GCD 里打印一下信息
12345678 |
def GCD(a, b): print(a.monic(),b) if(b == 0): return a.monic() else: return GCD(b, a % b)# x + 3269720129929206172290888040434844631999790813495546199598567897695383065785748573999332043932451485440224772661966886881467981258459641224093108678852609207558615214018620184887996376816876194347015843720084751398190561322698085192313884948494127864886155782163938754041371595283348119372481511820252205397 10094707220555426811770578750536360201358369370657659611252294461972567760547511972856872356006689569965863946144471753575975482915039158199762685955836393286445719933816896842332176600699750306238028403548064414478902718240280054367062726220893659556097524038957925231227120070260148988432886582427556137193 |
我们看到报错前的最后一条信息，有一个 10094707220555426811770578750536360201358369370657659611252294461972567760547511972856872356006689569965863946144471753575975482915039158199762685955836393286445719933816896842332176600699750306238028403548064414478902718240280054367062726220893659556097524038957925231227120070260148988432886582427556137193 然后对他和 n 用一下 gcd
得到 112229749912829564829770165528493741966573684175830091030568865445070552505343
于是，拿到了 $q$
再来一遍
1234567891011121314151617181920 |
def GCD(a, b): if(b == 0): return a.monic() else: return GCD(b, a % b)N = 112229749912829564829770165528493741966573684175830091030568865445070552505343c2 = 55877575842944488536738260741145576196064055314256851119903269638247167570517c3 = 24752910240512109387212015792618368998146452177596723408887013541065473659025P.<x> = PolynomialRing(Zmod(N))f1 = 1997f2 = 1997t = 4035619213for i in range(1,20): f1 += (x+t)^i f2 += (x*t)^if1 -= c3f2 -= c2print(long_to_bytes(int(N-GCD(f1,f2).coefficients()[0]))) |
发现还不行，我们得到的是 $m%q$，估计 $m$ 大于 $q$，爆破一下（希望不会大太多）
12345678910 |
q = 112229749912829564829770165528493741966573684175830091030568865445070552505343m = int(q-GCD(f1,f2).coefficients()[0])for i in range(2**25):m+=qflag = long_to_bytes(m)if b"flag" in flag:print(flag)# b'flag{ShangPo>XiaPo<YaSiLeYiQianDuo}' |
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
免责声明:文章中涉及的程序(方法)可能带有攻击性，仅供安全研究与教学之用，读者将其信息做其他用途，由读者承担全部法律及连带责任，本站不承担任何法律及连带责任；如有问题可邮件联系(建议使用企业邮箱或有效邮箱,避免邮件被拦截，联系方式见首页)，望知悉。
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论