[一带一路金砖 2023 CTF]Crypto

题1

题目描述：

from Crypto.Util.number import *
from flag import flag
import gmpy2
assert(len(flag)==38)
flag = bytes_to_long(flag)p = getPrime(512)
q = getPrime(512)e = 304
enc = pow(flag,e,p*q)
print(p)
print(q)
print(enc)
#9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
#10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
#88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028

题目分析：
e和phi不互素，同时flag长度比p和q小，故可直接用p或q中其中一个进行解
不互素考点应该是很熟了，这里就不多说咯

exp:

from Crypto.Util.number import *
from gmpy2 import *
e = 304
p = 9794998439882070838464987778400633526071369507639213778760131552998185895297188941828281554258704149333679257014558677504899624597863467726403690826271979
q = 10684338300287479543408040458978465940026825189952497034380241358187629934633982402116457227553161613428839906159238238486780629366907463456434647021345729
c = 88310577537712396844221012233266891147970635383301697208951868705047581001657402229066444746440502616020663700100248617117426072580419555633169418185262898647471677640199331807653373089977785816106098591077542771088672088382667974425747852317932746201547664979549641193108900510265622890793400796486146522028
d = invert(e // 16,(q - 1))
m_16 = pow(c,d,q)
e = 16
R.<x> = Zmod(q)[]
f=x^e-m_16
mps=f.monic().roots()
for i in mps:flag=long_to_bytes(int(i[0]))if b'flag' in flag:print(flag)
# flag{947b6543117e32730a93d1b43c98bc57}

题2

题目描述：

from Crypto.Util.number import *
from flag import flagdef gen_primes(nbit, imbalance):p = 2FACTORS = [p]while p.bit_length() < nbit - 2 * imbalance:factor = getPrime(imbalance)FACTORS.append(factor)p *= factor   # 一些小素数的乘积rbit = (nbit - p.bit_length()) // 2while True:r, s = [getPrime(rbit) for _ in '01']_p = p * r * sif _p.bit_length() < nbit: rbit += 1if _p.bit_length() > nbit: rbit -= 1if isPrime(_p + 1): # 光滑FACTORS.extend((r, s))p = _p + 1breakFACTORS.sort()return (p, FACTORS)def genkey(nbit, imbalance, e):while True:p, FACTORS = gen_primes(nbit // 2, imbalance)if len(FACTORS) != len(set(FACTORS)):continueq, q_factors = gen_primes(nbit // 2, imbalance + 1)if len(q_factors) != len(set(q_factors)):continuefactors = FACTORS + q_factorsif e not in factors:breakn = p * qreturn n, (p, q)nbit = 2048
imbalance = 19
e = 0x10001m_1 = bytes_to_long(flag[:len(flag)//2])
m_2 = bytes_to_long(flag[len(flag)//2:])n, PRIMES = genkey(nbit, imbalance, e)
c_1 = pow(m_1, e, n)
c_2 = pow(e, m_2, n)
print('n =', n)
print('c_1 =', c_1)
print('c_2 =', c_2)
n = 35357873937435054001282352637015489837983629944603246522178730306982853403322122532742547568947348720656333165913123004754628275811015219202713548802943693917918541563761339716370762198583591114052428351599691659723508542841656789503328119510785085937979525249694594158534358323126435951391004918101544306531617516774746895733526101034675683422353395313765068796525289210446354001944876249728896374221851147854490650250688040658359437708219708086466006475368143815063574396167110037225787616695794333552173352376965108641554651899828690770801642222911404004972981226404611238384640428742441960433230255967882512572709
c_1 = 16634534464526067333266542688361417073505104370260567430743212030440685317214374585499981030226926044766739869847879031408549807956380355500301201488848875687853416183379064412708949479112570148317905419837975685732979495910124097985791487969870055434863407745827818697689550695419811875635482462317998019001874694405544022096737341305813428625314356741922244350713455318505335210523811539099373597334819062036544344240156834535244078408347762370087901917949527669361716338102428255611527880175371489236975227446140403028949555168795599427303842397557962531520805711901076455900612217613591150327899301858065771562916
c_2 = 28959414058046581387331073805593474819964554400846556519089342566960219426395093378840690033900219718180201586444279902099201314738785482187096282489335039754400853514399233561703766501981317579016015885985249393698030292377653287627063434792453444305041899628924704707327777803327634177387380885834429684833509758496969064593639077614464933018728667369508101718561232112365432775831642293382722453145808785853553029281098760388699782452404701217989853131800383523025244719015821981668238625535719639173942578430758429709476625832809897441275508034910613246129679480731733559701167577051633529935423253203666147846715

题目分析：
第一部分为Pollard’s p-1光滑
直接解
exp:

from Crypto.Util.number import *
from gmpy2 import *
n = 35357873937435054001282352637015489837983629944603246522178730306982853403322122532742547568947348720656333165913123004754628275811015219202713548802943693917918541563761339716370762198583591114052428351599691659723508542841656789503328119510785085937979525249694594158534358323126435951391004918101544306531617516774746895733526101034675683422353395313765068796525289210446354001944876249728896374221851147854490650250688040658359437708219708086466006475368143815063574396167110037225787616695794333552173352376965108641554651899828690770801642222911404004972981226404611238384640428742441960433230255967882512572709
c_1 = 16634534464526067333266542688361417073505104370260567430743212030440685317214374585499981030226926044766739869847879031408549807956380355500301201488848875687853416183379064412708949479112570148317905419837975685732979495910124097985791487969870055434863407745827818697689550695419811875635482462317998019001874694405544022096737341305813428625314356741922244350713455318505335210523811539099373597334819062036544344240156834535244078408347762370087901917949527669361716338102428255611527880175371489236975227446140403028949555168795599427303842397557962531520805711901076455900612217613591150327899301858065771562916
c_2 = 28959414058046581387331073805593474819964554400846556519089342566960219426395093378840690033900219718180201586444279902099201314738785482187096282489335039754400853514399233561703766501981317579016015885985249393698030292377653287627063434792453444305041899628924704707327777803327634177387380885834429684833509758496969064593639077614464933018728667369508101718561232112365432775831642293382722453145808785853553029281098760388699782452404701217989853131800383523025244719015821981668238625535719639173942578430758429709476625832809897441275508034910613246129679480731733559701167577051633529935423253203666147846715
e = 0x10001
def Pollards_p_1(N):n = 2a = 2while True:a = pow(a,n,N)res = gcd(a-1,N)print(n)if res != 1 and res != N:print('p = ',res)return resn += 1
# p = Pollards_p_1(n)
p =  246193986637546903265592815609577026241302357122314925452960382002903884663793124671589668426466042284818011792326340585156178366427487449232598147821980481083788083405892143123015262709410005719036034457206601471709604309275710937299133844390087441265560849989236470128705724138785359931092408727167182527227
q = n // p
d = inverse(e,(p - 1)*(q - 1))
print(long_to_bytes(pow(c_1,d,n))) # flag{5eec62654a551c

之后离散对数，变下域

c_2 = 28959414058046581387331073805593474819964554400846556519089342566960219426395093378840690033900219718180201586444279902099201314738785482187096282489335039754400853514399233561703766501981317579016015885985249393698030292377653287627063434792453444305041899628924704707327777803327634177387380885834429684833509758496969064593639077614464933018728667369508101718561232112365432775831642293382722453145808785853553029281098760388699782452404701217989853131800383523025244719015821981668238625535719639173942578430758429709476625832809897441275508034910613246129679480731733559701167577051633529935423253203666147846715
e = 0x10001
p =  246193986637546903265592815609577026241302357122314925452960382002903884663793124671589668426466042284818011792326340585156178366427487449232598147821980481083788083405892143123015262709410005719036034457206601471709604309275710937299133844390087441265560849989236470128705724138785359931092408727167182527227
G = Zmod(p)
print(long_to_bytes(ZZ(discrete_log(G(c_2),G(e))))) # 8cb2280fe9405f908f}

关键词:离散对数变域

唉，都是出的原题啊。不过没事，还是学到了一个没接触过的小点