虽然本人没有参加第三届祥云杯决赛，但赛后还是摸到了赛题看。
学生组
有一个师傅在学生组，第一天学生组比完CTF后找到我说，在比赛的时候解题卡在了最后一步，让我瞅瞅，想知道怎么做。
赛题一
1234567891011121314151617181920212223 |
from secret import flagfrom Crypto.Util.number import *total_bit = 512def make_para(bit_size): P = getStrongPrime(bit_size) Q = getStrongPrime(bit_size) N = P * Q magic = (N + 1) * (N + P + Q + 1) + (P - Q) ** 2 + N d = int(0.394 * bit_size) e = inverse(d, magic) k = d * e // magic return (N, e), (P, Q, k)pubkey, sec_key = make_para(2 * total_bit)flag = bytes_to_long(flag) * sec_key[2]p = getStrongPrime(total_bit)q = getStrongPrime(total_bit)n = p * qe = 65537c = pow(flag, e, n)t = ((p - getRandomNBitInteger(16)) * sec_key[0] + q) % sec_key[1]with open('output.txt', 'w') as f: f.write(str(pubkey) + '\n') f.write(str((t, c))) |
题目大致的瞅一眼，首先生成了一些参数 $N,e,(P,Q,k)$ 其中 $N,e$ 已知。然后把 flag 乘了 k，接着又生成了一份 RSA 的公钥，并加密了 $k \cdot flag$ ，然后给出了关于 $p,q$ 的额外信息 $t = ((p-random) * P + q) % Q$
那么问题很显然啊，需要先分解 $N$，把 $P,Q,k$ 整出来先。而关于 $P,Q$，在 make_para 函数中我们注意到关于 $e,d$ 的生成方式。乍一看，还以为生成了一个大小是 $N^{0.394}$ 的私钥，然后用来生成 $e$ 的模数是 magic，合并一下其实是 $(P^2+P+1)(Q^2+Q+1)$，还以为是论文题，要用一下连分数啥的。但是转念一想，不对啊，离线比赛出论文题，那不是缺了大德么。最后定睛一看，好家伙 d = int(0.394 * bit_size)，原来 $d$ 是一个已知整数。
于是我们有 $e \cdot d = k (P^2+P+1)(Q^2+Q+1)+1$，展开一下 $e\cdot d-1 = k(N^2+PN+QN+P^2+Q^2+N+P+Q+1)$
因此 $\lfloor \frac{e\cdot d-1}{N^2}\rfloor = k$，假设 $P>Q$，那么 $Q^2 \lt N \lt P^2$，于是 $\lfloor \frac{e\cdot d-1}{kN}\rfloor \approx N +P+Q+2$，实际测出来是 $\lfloor \frac{e\cdot d-1}{kN}\rfloor = N +P+Q+3$
然后解个方程我们就能获取 $P,Q,k$ 了。
12345678910111213141516171819 |
from gmpy2 import *N,e = (21136120517038375343657055317361461947217610380415290931285704769845405139443342030139838613845989765254932385503454684656325859309861269837188207923942223163348944160792729101485975484543693998035828762630825174735962679103457025646672449491007685400869138263581883506767852264244013623583813540066115060793144049256890248337903932112449333735324371400873419104520104079223733159263094092843185909770131443506433825708789563521497940390674504488024226655482568491358458107989880756229607524452273305978138461190013290440068226454238375505010225133919526068226837545142734502100757510899741312502285931571783851666429, 291542085122413541028076006933740091355832744332602513957292369860771664833892358795585946753279254101863581542678927529330607906769804928526978686071141386341893467977451552634615917127445748737712286687041822255325772392569586666055711202824870471562051621883329559663555059967665101455578668904247279540014709971958403913939101728330638301270881265277488332145439522278871554725936095617940701105161078332467466405454007283937177070102098256744642045839067405705972784471374421818844770106228499198315920181837950503279178647052157269318876892192700670366858062171759498850112906238502375693099462427930964555274451795362167393410749436026095037695100430810204847979914959732383773952788768239221142673268839750770222737928397507645337714199166919835667638401309062163501094032890215821366318775462220119081175885338966308921205861717088926659072208866126879068213582499260316364548817213314952246293713853884872460934174624844462586276340207505217646013915381902979372875919823493439285174120160656952728493383464761519634974414670811896809158801804891938928244053980210687334268664219571818927285279999791212932795196689285015367417706597781418431735001428656415752334850685705212368666855124013583549768407830008606258798409140)d = int(0.394 * 1024)k = (e*d-1)//N**2p_a_q = (e*d-1)//(k*N) - N - 3p_s_q = iroot(p_a_q**2-4*N,2)[0]p = (p_a_q+p_s_q)//2q = p_a_q - passert p*q == Nprint(p)print(q)print(k)# 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591# 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219# 263 |
显然我们是需要根据 $t = ((p-random) * P + q) % Q$ 解出 $p,q$ 来解密密文获得 flag
这里由于 $P,Q$ 是 1024 比特的，$p,q$ 是 512 比特。考虑格基规约，类似 的 ，构造如下格
12345678910111213 |
from Crypto.Util.number import *p = getPrime(510)q = getPrime(510)n = p * qt = ((p - getRandomNBitInteger(16)) * P + q) % Qshift = 2^1024m = matrix(ZZ,[[shift*P,1,0,0,0],[shift*1,0,1,0,0],[shift*Q,0,0,1,0],[shift*t,0,0,0,2^512]])m = m.LLL()assert abs(m[1][2])==q |
本地测试发现当 $p,q$ 长度为 $510$ 的时候能跑出来，但是使用原来数据时，$p,q$ 多 2 个比特就怎么也出不来。
于是想到爆破 $p,q$ 的高位，首先最高位肯定都是 1，对于第二个比特 ，猜一下，总共也就四种可能。（另外 $P,Q$ 也有可能会反，需要对调一下，总共就是 8 种可能）
1234567891011121314151617181920212223242526 |
t,c = (18872151984199200051633005759140295224788252451326410141022483203855894790958837408470348915966212063467995292461061069273539234939320647533902914083943444743748789975745514239518406829738286900177972974033143896932863898553599888597165054837513698667686277110587659188172271629973371164557353473146831275972, 47672712219012743425382676880904671136942826695249149129159924785186563239747047304204962529935078111450524236186612259355850306867579998685662967391936502046679744616903469002187225791339629835786750259999982506494377133775859573660632942293353420327987860136624649402598383416748766985203781387716072244402)k = 263P = 143078039642881652792725771784213914569207427179221450527831176525315265565238257928580110111049486656241446498753952813958174255162082586211603455849496271101246800300949146175660103176787576526962695816071099455794179935847192303931252206979980383408582225496150194196048569906497422686531669037370362490591Q = 147724420671358625656073728988251990709657136203479220456044242791542317692661747967991832853881462444146194371982730793349362452137634455888399765514368115413509137529033492152562833458082422584778299506218002962422410654802940055372919228164309566932084727942623228573408370823021433452034727423294317997219# 猜测 p,q 高位ph = 0b11<<510qh = 0b11<<510# 根据 p,q 高位， t 做相应处理tbar = (t-qh-ph*P)%Qshift = 2^1024m = matrix(ZZ,[[shift*P,1,0,0,0],[shift*1,0,1,0,0],[shift*Q,0,0,1,0],[shift*tbar,0,0,0,2^512]])m = m.LLL()if isPrime(int(abs(m[1][2])+qh)):q = abs(m[1][2])+qhe = 65537d = inverse(e,q-1)mm = pow(c,d,q)print(long_to_bytes(int(mm//k)))b'flag{6db64079-711c-4d80-86c6-baec1023d44d}' |
赛题二
然后我把第二题给问过来了，
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596 |
from Crypto.Util.number import *from Crypto.Util.strxor import strxorfrom random import randintfrom gmpy2 import invertimport osflag = b'xxx'def mypad(m): l = len(m) r = 190 - l padded_m = m + os.urandom(r) return padded_mdef myfunction(num): output = 0 j = 0 for i in range(num): output += (i+j)*6 + 1 j += i return outputdef mix(a,b): return a | b , a * bclass MySeries(): def __init__(self, num): self.num = num def Coe(self, n): i = 0 c = 1 while i < n: i += 1 c = (c * (1 / 2 - i + 1)) / i return c def Point(self, center): sum = 0 center -= 1 i = 0 while i < self.num: sum += (center ** (1 / 2 - i) * self.Coe(i)) i += 1 return sumdef All(bound): num = randint(1111, 2222) T = MySeries(num) output = 0 i = 3 while i < bound: b1 = T.Point(i) b2 = T.Point(i + 1) output += (b1 + b2) / 2 i += 1 return outputif __name__ == '__main__': flag_len = len(flag) p,q = getPrime(512),getPrime(512) while True: r = getPrime(512) R = bytes_to_long(str(r).encode()) if isPrime(R): break n = p * q * r hint1 = R * r mod = myfunction(n) hint2 = pow(3*n+1,p % (2 ** 400),mod) k = int(All(n)) xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag) pad_flag = mypad(xor_flag) m = bytes_to_long(pad_flag) c = pow(m,65537,n) print('All data:') print(f'flag_len = {flag_len}') print(f'n = {n}') print(f'c = {c}') print(f'hint1 = {hint1}') print(f'hint2 = {hint2}')'''All data:flag_len = 42n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471c = 696238728213276154324787695659767792043458798396732235983493075871691401810545168845655490352789752222363100922123671319198981013421632076090146254867823593523050502577701155837063376958530879006719716789887624440134559774538443909463537086796915613123528679984244371544503657821859556837415229166015914540860398289216765611441964228176020361651359395184571105468667815326494558761738459063914192172836518999575866452752941368767971539919141604299843463853501960hint1 = 47533994701669017942592643580845693193316601935087923279407365999451221242084261195588230994183718077379066856479267476895986608547324057765879168010176037349172136581929046771540241367625486215731295814611283581608613208990206581757576978017732022062210538697720930605552259306749633658032304554578427461842934055558865521604512892691323385156889995854702621568441768712619224249280792783364635307739215957762771386413831279443875185633720270001928747743847856394847878232194076679733830705297410959656270945532930199517880949hint2 = 1345739841248959791137389026125065605121513428784838684290299665636596562317989590469829195181078904857051392378877013458099983407103737518119999468489762053545474516182879516762580472262640794849609626308003164739287189671066241628052826558582865342176036139097546843281565147798609965645514151827840249686650855385385323417455247722134760335695053787221300451942370377598800841980049138341564555801417479362085565640973199260631136149016266661293883650801813550118778433333591258278147003619871962070136454674193198696690506092831171400435490432196636796719177624389194619648086397178720207413652618636521150924913978530986709499047969775311955879302418093270101476537853298615347062384026172441455857088955847766335746521291043747795520485020303040819568036819058385444936925860671650596681910380157657689041971132993731048618045570715513584627109356139903842365556697314631573799394266292587334468008221427502353566938518574247502783245674619641519095644135976062817840893465238031354234069073928763492529419021632732679912738674105898149050223970723297059883534089683179512881491210176114419520070007595698242827625902377045860953285447617249204919971737086366''' |
赛题二就比较缝合怪了，魔改的应该是 2022 CCTF Infinity castle
第一步是用 $hint1$ 和 $n$ 做 gcd 求出 $r$，
然后测试（或者推一下）可得 myfuction 其实就是一个计算三次方的函数，
于是，根据二项式定理，我们可以利用 $hint2$ 求出 $p %400 = \frac{hint %400}{3n}$ ，
有了 $p$ 的低 400 位，来一个 copper 就能分解 $n$ 了。
最后为了解密 flag 还得求出 $k$，这个 All 函数其实就是一个泰勒展开在求 $\sqrt{n}$ 的积分，所以 $k = \frac{2}{3}n^\frac{3}{2}$
12345678910111213141516171819202122232425262728293031323334 |
n = 1885106209951408608833065466098355578239648885277085979696889428331716535742564778501798478665957825315340421821880653818505857049636611632357321104069926874970489073929053910350131880591544986024406953378391135673202854750625745159391997973535848495128365477217006260495413869532372418221652962946340513593002422433536479789576519469228846773250447077165756739529520975715667675188738514871033908115371290569902086064227476952606366538782284487477820835988316471 r = 13064264216014600984590013161094647588688097945008015283029781423081403612570218487688473281971441574006356719607329041516297420593832435695152551495621303 # n = p * q * r # mod = myfunction(3) # print(mod==n**3) # hint2 = pow(3*n+1,p % (2 ** 400),n**3) # hint2 = pow(3*n+1,400,n**3) # print((hint2%(n**2))//n) # pbar = (hint2%(n**2))//(3*n) # # pbar = 290093818088445232385211155295987419950746202522777816778903667287369882202987169000686051435796089920601608052312746065 # R.<x> = Zmod(n)[] # f = (2^400) * x + pbar # x0 = f.monic().small_roots(X=2^112,beta=0.49)[0] # p = int(f(x0)) # q = int(n)//p # p = 10835491201779459536146517032534966141751744767433086585469873899474443209697998673019277269625767885233333299822821960132722036029334072360300733477529681 # q = 13316873218544878416280346742338579649540959399378233738197413050519025036683226049252858246940675299712559597339200613975360145818807371576573913305896497 # phi = (p-1)*(q-1)*(r-1) # d = inverse(e,phi) # m = pow(c,d,p*q*r) # m = long_to_bytes(m) # k = 2*(n*iroot(n,2)[0])//3 xor_flag = strxor(long_to_bytes(k >> (k.bit_length() - 8 * flag_len)),flag[:42]) xor_flagb'flag{84934a62-f932-968c-fa88-22f0284c0e8e}' |
社会组
同事在社会组的 SU，赛后也把题目给我瞅了瞅，于是在去陇剑杯的飞机上看了一下
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394 |
from secret import flag, genPrime, generate_gimport randomimport mathimport ossieve_base = # from Crypto.Util.number import sieve_basedef rabinMillerTest(n, rounds): tested = [] if n < 3 or (n & 1) == 0: return n == 2, tested # n might be very large so it might be beneficial to precalculate n-1 n_1 = n - 1 # determine m and b so that 2**b * m = n - 1 and b maximal b = 0 m = n_1 while (m & 1) == 0: b += 1 m >>= 1 #a smaller number might be faster... upper = 2**(max(n.bit_length() >> 5, 10)) # we need to do at most n-2 rounds. for i in range(min(rounds, n - 2)): a = random.randint(2, upper) while a in tested: a = random.randint(2, upper) tested.append(a) # do the rabin-miller test z = pow(a, m, n) # (a**m) % n if z == 1 or z == n_1: continue composite = 1 for r in range(b): z = (z * z) % n if z == 1: return 0, tested elif z == n_1: composite = 0 break if composite: return 0, tested return 1, testeddef is_prime(N, false_positive_prob=1e-6): tested = [] if N < 3 or N & 1 == 0: return N == 2, [] for p in sieve_base: if N == p: return 1, tested if N % p == 0: tested.append(p) return 0, tested rounds = int(math.ceil(-math.log(false_positive_prob)/math.log(4))) return rabinMillerTest(N, rounds)print("Welcome to my secure key exchange system\n")while True: q = int(input("q:")) if q.bit_length() < 256: print("oh! too small!!!") continue jud, tested = is_prime(q) if not jud: print(f"Bad parameters! test set {tested} not pass.") else: breakx = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big')p = genPrime(q)g = generate_g(q, p)print(f"p: {p}")print(f"g: {g}")A = pow(g, x, p)print(f"Calculate the public key in this way: pow(g, secret, p)")print(f"eg. pow(g, x, p) = {A}")print(f"I can give you a hint:)")r = int(input("r:"))if r < x and ((p - 1) % r == 0): print(pow(g, x, r))else: print("don't need hint?")for i in range(100): B = int(input("give me your public key:")) if 1 < B < p: shared = pow(B, x, p) print(f"our shared key: {shared}") x_ = int(input("x?").strip()) if x_ == x: print(flag) else: print("sorry~") |
是一个需要交互的题，把函数 genPrime, generate_g 给偷摸隐藏了起来，估计是有点问题。看一下题目流程：
- 用户端输入一个大于 256 比特的素数 $q$
- 服务端随机生成一个秘密数 $x$，并根据用户的 $q$ 生成一个素数 $p$，在根据 $p,q$ 生成一个 $g$，并给出 $A \equiv g^x \pmod p$。（由于没有源码，这里合理猜测生成的 $p-1$ 具有因子 $q$，而 $g$ 是一个在模 $p$ 阶为 $q$ 的一个元素，这是 Elgamal 参数生成的标准）
- 服务端允许用户输入一个 $r$，如果满足 $r \lt x,p-1 \equiv 0 \pmod r$，服务端就会输出 $g^x %r$
- 之后服务端让用户输入一个 $B$，并给出 $B^x \pmod p$（就是一个 ECDH），然后让用户猜 $x$，猜对了就给 $flag$，一共一百次交互机会。
乍一看给出了 rabinMillerTest 还以为让绕过素数检测，但根据后面的流程来看，估计预期应该是根据 hint 得到一些关于 $x$ 信息，再利用一百次交互，每次搞到一点额外的信息，最后恢复完整的 $x$ 叭。
但是，注意到给 hint 的部分会给出 $g^x %r$，因此，只要 $r-1$ 是光滑的，就能解出 $x$ 了。而 $r$ 得是 $p-1$ 的一个因子，如果我们对 genPrime 函数猜测的正确的话，那就直接设 $r$ 为 $q$，而 $q-1$ 是一个光滑数就行了。至于和 $x$ 的大小关系，由于 $x$ 的生成和 $q$ 的比特有关 x = int.from_bytes(os.urandom(q.bit_length() // 8), byteorder='big') ，注意这里 $x$ 并不是严格小于 $q$，所以爆！为了消去“地板除”的影响，要找比特长度刚好是 8 的倍数的 $q$，然后多跑几次等 $x$ 比 $r$ 大，我们就可以直接解 $DLP$ 得到 $x %r$，然后根据大小关系，对结果加一个 $r$ 就是 $x$ 了。
生成 $p-1$ 光滑的素数 $p$ 的脚本
1234567891011 |
from Crypto.Util.number import *import randomdef genPrime(bit_len):while True:x = 2while x < 2**bit_len:x *= random.choice(sieve_base)if isPrime(x+1) and x.bit_length() % 8 == 0:return x+1print(genPrime(256)) |
（不过由于没有赛题源码，以上想法全是基于猜测正确的前提下）
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可联系QQ 643713081，也可以邮件至 [email protected] - source:Van1sh的小屋
- 左青龙
- 微信扫一扫
-
- 右白虎
- 微信扫一扫
-
评论