crypto|2021.09.19长城杯 Crypto 复现 crypto|python

baby_rsa
题目代码：

#!/usr/bin/env python3from Crypto.Util.number import * from secret import flag, v1, v2, m1, m2def enc_1(val): p, q = pow(v1, (m1+1))-pow((v1+1), m1), pow(v2, (m2+1))-pow((v2+1), m2) assert isPrime(p) and isPrime(q) and (p*q).bit_length() == 2048 and q < p < q << 3 return pow(val, 0x10001, p*q)def enc_2(val): assert val.bit_length() < 512 while True: fac = [getPrime(512) for i in range(3)] if isPrime(((fac[0]+fac[1]+fac[2]) << 1) - 1): n = fac[0]*fac[1]*fac[2]*(((fac[0]+fac[1]+fac[2]) << 1) - 1) break c = pow(val, 0x10001, n) return (c, n, ((fac[0]+fac[1]+fac[2]) << 1) - 1)if __name__ == "__main__": assert flag[:5] == b'flag{' plain1 = bytes_to_long(flag[:21]) plain2 = bytes_to_long(flag[21:]) print(enc_1(plain1)) print(enc_2(plain2))''' 15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311 (40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083, 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269, 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739) '''

比赛时思路：
【crypto|2021.09.19长城杯 Crypto 复现】由于enc_1已经被队长解完了，剩下的enc_2就留给我们写。故这里只写我当时解enc_2的思路。
从代码中可以看出n是由三个未知素数构成的，解密的话我们只需要求出φ(n)就可了。
令fac[0] = f0 , fac[1] = f1 , fac[2] = f2 , f3 = 2 * (f0 + f1 + f2) - 1 ，
则n = f0 * f1 * f2 * f3，φ(n) = (f0 - 1) * (f1 - 1) * (f2 - 1) * (f3 - 1) (f0,f1,f2,f3均为素数)
根据给出的数据，我们可以求出a = f0 * f1 * f2 , b = f0 + f1 + f2 (奇怪的是n = f0 * f1 * f2 * f3，但却不能被f3整除，当时也确实有疑惑，但就姑且这么算吧)
之后就不断尝试将φ(n)化为只含a,b的式子。
然后，然后就被队友写出来了，然后我就躺好了，队友带飞。
正确的解题思路：

enc_1

参考：[ONE LINE CRYPTO](CryptoCTF 2020 | CryptoHack Blog)
有以下式子和条件：
{ p = v 1 m 1 + 1 ? ( v 1 + 1 ) m 1 q = v 2 m 2 + 1 ? ( v 2 + 1 ) m 2 { p i s p r i m e q i s p r i m e b i t _ l e n g t h ( p ? q ) = 2048 q < p < 8 ? q \begin{cases} p = v_1^{m_1+1} - (v_1 + 1)^{m_1} \\q = v_2^{m_2+1} - (v_2 + 1)^{m_2} \end{cases} \quad \begin{cases} p\quad is\quad prime\\q\quad is\quad prime\\bit\_length(p*q) = 2048\\q < p < 8*q\end{cases} { p=v1m1?+1??(v1?+1)m1?q=v2m2?+1??(v2?+1)m2????????????pisprimeqisprimebit_length(p?q)=2048q p，q的比特长度均小于2048（应该更小）。我们可以通过这个条件来枚举v和m，求出该范围内的所有素数，然后再从中选取任意两个素数，求n，长度若为2048bits，则尝试解密。

import gmpy2 from Crypto.Util.number import * #enc_1 c1 = 15808773921165746378224649554032774095198531782455904169552223303513940968292896814159288417499220739875833754573943607047855256739976161598599903932981169979509871591999964856806929597805904134099901826858367778386342376768508031554802249075072366710038889306268806744179086648684738023073458982906066972340414398928411147970593935244077925448732772473619783079328351522269170879807064111318871074291073581343039389561175391039766936376267875184581643335916049461784753341115227515163545709454746272514827000601853735356551495685229995637483506735448900656885365353434308639412035003119516693303377081576975540948311 e1 = 65537primes = [] for x in range(500): for y in range(500): num = pow(x, (y+1))-pow((x+1), y) if len(bin(num)[2:]) < 2048: if isPrime(num): primes.append(num)for p in primes: for q in primes: n1 = p*q if len(bin(n1)[2:]) == 2048: try: d1 = gmpy2.invert(e1,(p-1)*(q-1)) flag = long_to_bytes(pow(c1,d1,n1)) if b'flag' in flag or b'ctf' in flag: print(flag) except: pass #b'flag{8102c552-3d78-4a'

enc_2
看了队友的wp之后恍然大悟！！！
令a = f0 * f1 * f2 , b = 2 * (f0 + f1 + f2) - 1，n = a * b
c ≡ m e ( m o dn ) = = > c ≡ m e ( m o db ) \quad \quad c ≡ m^e\quad (mod\ n)\\ ==>c≡m^e\quad (mod\ b) c≡me(mod n)==>c≡me(mod b)
b已知，就可以求出模b下的m，然而这个值转换成字节码后就是flag的后半部分，不需要求模n下的m。

#enc_2 c2 = 40625981017250262945230548450738951725566520252163410124565622126754739693681271649127104109038164852787767296403697462475459670540845822150397639923013223102912674748402427501588018866490878394678482061561521253365550029075565507988232729032055298992792712574569704846075514624824654127691743944112075703814043622599530496100713378696761879982542679917631570451072107893348792817321652593471794974227183476732980623835483991067080345184978482191342430627490398516912714451984152960348899589532751919272583098764118161056078536781341750142553197082925070730178092561314400518151019955104989790911460357848366016263083 n2 = 43001726046955078981344016981790445980199072066019323382068244142888931539602812318023095256474939697257802646150348546779647545152288158607555239302887689137645748628421247685225463346118081238718049701320726295435376733215681415774255258419418661466010403928591242961434178730846537471236142683517399109466429776377360118355173431016107543977241358064093102741819626163467139833352454094472229349598479358367203452452606833796483111892076343745958394932132199442718048720633556310467019222434693785423996656306612262714609076119634814783438111843773649519101169326072793596027594057988365133037041133566146897868269 #n = 191*193*627383*1859355639056989338847729886215084320013550560439241610057371464443668166453664500865174247660203446208131621966684387189121472932263450155428982061395111044679950753816414282942636019897750209949937717881413823952091423640659878296010412658344713439244770180457400325541493186854703180053691731596197238201363111053528501245160357253774375411526857827842825019859291800622538200724857835739888753732012856112635184060331441747542167843105976327845423935402822864894596846745465781342565264427930954562609611327939077769568270876754335269640277726607195276868129620895284648898858733965899439317638568413061 e2 = 65537 b = 39796272592331896400626784951713239526857273168732133046667572399622660330587881579319314094557011554851873068389016629085963086136116425352535902598378739 #pd = 191*193*627383*1720754738477317127758682285465031939891059835873975157555031327070111123628789833299433549669619325160679719355338187877758311485785197492710491 #a = n2/b#不是整数！ x1 = 191 x2 = 193 x3 = 627383 x4 = 1720754738477317127758682285465031939891059835873975157555031327070111123628789833299433549669619325160679719355338187877758311485785197492710491 phi2 = (x1-1)*(x2-1)*(x3-1)*(x4-1) d2 = gmpy2.invert(e2,phi2) m2 = pow(c2,d2,b) print(long_to_bytes(m2)) #b'42-b659-0c96ef827f05}'