2024MOECTF Crypto Week2
第二周就开始接触一些简单的数论知识了，还有一些很有趣的题目，比如反素数，可能回过头看看觉得没什么(但深挖一下都很有内容吧，大佬手下留情了呜呜呜)，当时做得还是很累，这就是学习的常态吗
\[\]
\[\]
\[\]
大白兔
from Crypto.Util.number import *
flag = b'moectf{xxxxxxxxxx}'
m = bytes_to_long(flag)
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
def encrypt(m , e1 , e2):
p = getPrime(512)
q = getPrime(512)
N = p*q
c1 = pow((3*p + 7*q),e1,N)
c2 = pow((2*p + 5*q),e2,N)
e = 65537
c = pow(m , e , N)
return c
print(encrypt(m ,e1 , e2))
'''
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
'''
我们可以看到N是难以分解的，给出的c1和c2要我们求出p和q。
算一算吧！
\[C1≡(3*p+7*q)^{e1}(modN)$$ $$C2≡(2*p+5*q)^{e2}(modN)
\]
又知道
\[N=p*q
\]
由二项式展开可以舍掉含有$$p*q$$因式的项,则有
\[C1≡(3*p)^{e1}+(7*q)^{e1}(modN)
\]
\[C2≡(2*p)^{e2}+(5*q)^{e2}(modN)
\]
希望消掉q，不妨两边幂方再展开：
\[C1^{e2}≡(3*p)^{e1*e2}+(7*q)^{e1*e2}(modN)
\]
\[C2^{e1}≡(2*p)^{e1*e2}+(5*q)^{e1*e2}(modN)
\]
\[5^{e1*e2}*C1^{e2}≡(3*5*p)^{e1*e2}+(5*7*q)^{e1*e2}(modN)
\]
\[7^{e1*e2}*C2^{e1}≡(2*7*p)^{e1*e2}+(5*7*q)^{e1*e2}(modN)
\]
两式相减有
\[5^{e1*e2}*C1^{e2}-7^{e1*e2}*C2^{e1}≡(3*5*p)^{e1*e2}-(2*7*p)^{e1*e2}(modN)
\]
记左式为M，则有:
\[M-t*p^{\alpha}=k*p*q
\]
那么M必为p的倍数，也就是说：
\[p=gcd(M,N)
\]
利用这个公式快速得到p后，剩下就是一把梭哈
from Crypto.Util.number import *
import gmpy2
e1 = 12886657667389660800780796462970504910193928992888518978200029826975978624718627799215564700096007849924866627154987365059524315097631111242449314835868137
e2 = 12110586673991788415780355139635579057920926864887110308343229256046868242179445444897790171351302575188607117081580121488253540215781625598048021161675697
e=65537
N = 107840121617107284699019090755767399009554361670188656102287857367092313896799727185137951450003247965287300048132826912467422962758914809476564079425779097585271563973653308788065070590668934509937791637166407147571226702362485442679293305752947015356987589781998813882776841558543311396327103000285832158267
c1 = 15278844009298149463236710060119404122281203585460351155794211733716186259289419248721909282013233358914974167205731639272302971369075321450669419689268407608888816060862821686659088366316321953682936422067632021137937376646898475874811704685412676289281874194427175778134400538795937306359483779509843470045
c2 = 21094604591001258468822028459854756976693597859353651781642590543104398882448014423389799438692388258400734914492082531343013931478752601777032815369293749155925484130072691903725072096643826915317436719353858305966176758359761523170683475946913692317028587403027415142211886317152812178943344234591487108474
c = 21770231043448943684137443679409353766384859347908158264676803189707943062309013723698099073818477179441395009450511276043831958306355425252049047563947202180509717848175083113955255931885159933086221453965914552773593606054520151827862155643433544585058451821992566091775233163599161774796561236063625305050
p = GCD((pow(5,e1*e2,N)*pow(c1,e2,N) - pow(7,e1*e2,N)*pow(c2,e1,N))%N,N)
q=N//p
print(long_to_bytes(pow(c,gmpy2.invert(e,(p-1)*(q-1)),N)))
#moectf{Sh4!!0w_deeb4t0_P01arnova}
\[\]
More_secure_RSA
from Crypto.Util.number import *
flag = b'moectf{xxxxxxxxxxxxxxxxx}'
m = bytes_to_long(flag)
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e = 0x10001
c = pow(m, e, n)
print(f'c = {c}')
print(f'n = {n}')
'''
Oh,it isn't secure enough!
'''
r = getPrime(1024)
n = n * r
c = pow(m, e, n)
print(f'C = {c}')
print(f'N = {n}')
'''
c = 12992001402636687796268040906463852467529970619872166160007439409443075922491126428847990768804065656732371491774347799153093983118784555645908829567829548859716413703103209412482479508343241998746249393768508777622820076455330613128741381912099938105655018512573026861940845244466234378454245880629342180767100764598827416092526417994583641312226881576127632370028945947135323079587274787414572359073029332698851987672702157745794918609888672070493920551556186777642058518490585668611348975669471428437362746100320309846155934102756433753034162932191229328675448044938003423750406476228868496511462133634606503693079
n = 16760451201391024696418913179234861888113832949815649025201341186309388740780898642590379902259593220641452627925947802309781199156988046583854929589247527084026680464342103254634748964055033978328252761138909542146887482496813497896976832003216423447393810177016885992747522928136591835072195940398326424124029565251687167288485208146954678847038593953469848332815562187712001459140478020493313651426887636649268670397448218362549694265319848881027371779537447178555467759075683890711378208297971106626715743420508210599451447691532788685271412002723151323393995544873109062325826624960729007816102008198301645376867
C = 1227033973455439811038965425016278272592822512256148222404772464092642222302372689559402052996223110030680007093325025949747279355588869610656002059632685923872583886766517117583919384724629204452792737574445503481745695471566288752636639781636328540996436873887919128841538555313423836184797745537334236330889208413647074397092468650216303253820651869085588312638684722811238160039030594617522353067149762052873350299600889103069287265886917090425220904041840138118263873905802974197870859876987498993203027783705816687972808545961406313020500064095748870911561417904189058228917692021384088878397661756664374001122513267695267328164638124063984860445614300596622724681078873949436838102653185753255893379061574117715898417467680511056057317389854185497208849779847977169612242457941087161796645858881075586042016211743804958051233958262543770583176092221108309442538853893897999632683991081144231262128099816782478630830512
N = 1582486998399823540384313363363200260039711250093373548450892400684356890467422451159815746483347199068277830442685312502502514973605405506156013209395631708510855837597653498237290013890476973370263029834010665311042146273467094659451409034794827522542915103958741659248650774670557720668659089460310790788084368196624348469099001192897822358856214600885522908210687134137858300443670196386746010492684253036113022895437366747816728740885167967611021884779088402351311559013670949736441410139393856449468509407623330301946032314939458008738468741010360957434872591481558393042769373898724673597908686260890901656655294366875485821714239821243979564573095617073080807533166477233759321906588148907331569823186970816432053078415316559827307902239918504432915818595223579467402557885923581022810437311450172587275470923899187494633883841322542969792396699601487817033616266657366148353065324836976610554682254923012474470450197
'''
这是一道多素数RSA问题，随着质因数增加，RSA加密强度其实是降低，但可以有效减小生成密钥和解密的计算量，因此在现实中也有应用。
我们可以得到N的一个质因数r,到此我们就可以进行解密了：
\[M^e≡C(modN)
\]
即$$M^e-C=kN=kpqr$$
则
\[M^e≡C(modr)
\]
又r为素数，故有：
\[\phi(r)=r-1
\]
因此
\[M≡C^d(modr)
\]
其中d是e模r的逆元
\[e*d≡1(mod\phi(r))
\]
from Crypto.Util.number import *
import gmpy2
c = 12992001402636687796268040906463852467529970619872166160007439409443075922491126428847990768804065656732371491774347799153093983118784555645908829567829548859716413703103209412482479508343241998746249393768508777622820076455330613128741381912099938105655018512573026861940845244466234378454245880629342180767100764598827416092526417994583641312226881576127632370028945947135323079587274787414572359073029332698851987672702157745794918609888672070493920551556186777642058518490585668611348975669471428437362746100320309846155934102756433753034162932191229328675448044938003423750406476228868496511462133634606503693079
n = 16760451201391024696418913179234861888113832949815649025201341186309388740780898642590379902259593220641452627925947802309781199156988046583854929589247527084026680464342103254634748964055033978328252761138909542146887482496813497896976832003216423447393810177016885992747522928136591835072195940398326424124029565251687167288485208146954678847038593953469848332815562187712001459140478020493313651426887636649268670397448218362549694265319848881027371779537447178555467759075683890711378208297971106626715743420508210599451447691532788685271412002723151323393995544873109062325826624960729007816102008198301645376867
C = 1227033973455439811038965425016278272592822512256148222404772464092642222302372689559402052996223110030680007093325025949747279355588869610656002059632685923872583886766517117583919384724629204452792737574445503481745695471566288752636639781636328540996436873887919128841538555313423836184797745537334236330889208413647074397092468650216303253820651869085588312638684722811238160039030594617522353067149762052873350299600889103069287265886917090425220904041840138118263873905802974197870859876987498993203027783705816687972808545961406313020500064095748870911561417904189058228917692021384088878397661756664374001122513267695267328164638124063984860445614300596622724681078873949436838102653185753255893379061574117715898417467680511056057317389854185497208849779847977169612242457941087161796645858881075586042016211743804958051233958262543770583176092221108309442538853893897999632683991081144231262128099816782478630830512
N = 1582486998399823540384313363363200260039711250093373548450892400684356890467422451159815746483347199068277830442685312502502514973605405506156013209395631708510855837597653498237290013890476973370263029834010665311042146273467094659451409034794827522542915103958741659248650774670557720668659089460310790788084368196624348469099001192897822358856214600885522908210687134137858300443670196386746010492684253036113022895437366747816728740885167967611021884779088402351311559013670949736441410139393856449468509407623330301946032314939458008738468741010360957434872591481558393042769373898724673597908686260890901656655294366875485821714239821243979564573095617073080807533166477233759321906588148907331569823186970816432053078415316559827307902239918504432915818595223579467402557885923581022810437311450172587275470923899187494633883841322542969792396699601487817033616266657366148353065324836976610554682254923012474470450197
r=N//n
e=65537
d=gmpy2.invert(e,r-1)
m=pow(C,d,r)
print(long_to_bytes(m))
#moectf{th3_a1g3br4_is_s0_m@gic!}
\[\]
ezlegendre
from sympy import *
from Crypto.Util.number import *
p = getPrime(128)
a = randprime(2, p)
FLAG = b'moectf{xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx}'
def encrypt_flag(flag):
ciphertext = []
plaintext = ''.join([bin(i)[2:].zfill(8) for i in flag])
for bit in plaintext:
e = randprime(2, p)
n = pow(int(bit) + a, e , p)
ciphertext.append(n)
return ciphertext
print(encrypt_flag(FLAG))
'''
p = 303597842163255391032954159827039706827
a = 34032839867482535877794289018590990371
[278121435714344315140568219459348432240]
'''
这道题是把flag逐字转换为二进制后拼接并逐位加密，a和p已经告诉我们，问题在于随机数e是未知的，如果知道，也许可以逐位解出。
\[\]
我们会想到对每一个列表元素分别爆破e求解，但电脑表示它要爆了。
\[\]
这实际上是离散对数问题，与大数分解难题、椭圆曲线求解难题同为公钥加密的三大支柱。
\[\]
在网上可以搜到有些题通过直接求解离散对数的非预期解，但这道题似乎计算量并不允许。
\[\]
又搜到利用勒德让符号方法的预期解，结合标题ezlegendre或许这正是这道题的解法。
首先有:
\[p≡3(mod4)
\]
\[a^{(p-1)/2}≡-1(modp)
\]
因为
\[n≡(bit+a)^e(modp)
\]
如果bit为0，则
\[n≡a^e(modp)
\]
\[e={ind_a}n
\]
有解，反之bit为1，这样我们可以求出整个二进制串。
以下进行推导:
如果$$bit=0$$
两边同时幂方则有
\[n^{(p-1)/2}≡a^{e*(p-1)/2}(modp)
\]
\[n^{(p-1)/2}≡-1(modp)
\]
这是因为e是奇数
这样我们就把离散对数问题转化为了单纯容易的乘法计算了，若 n不满足上式，说明其对应的bit为1
from sympy import *
from Crypto.Util.number import *
p = 303597842163255391032954159827039706827
a = 34032839867482535877794289018590990371
ciphertext=[]
plaintext=''
for i in ciphertext:
if(pow(i,(p-1)//2,p)-p==-1):
plaintext+='0'
else:
plaintext+='1'
flag = ''
for i in range(0, len(plaintext), 8):
flag += chr(int(plaintext[i: i+8], 2))
print(flag)
#moectf{minus_one_1s_n0t_qu4dr4tic_r4sidu4_when_p_mod_f0ur_equ41_to_thr33}
当然官方wp是说a+1是p的二次剩余，那就直接判断i是否为二次剩余，如果是，则输出1。
\[\]
这里掉坑了，python取模永远是非负数，等于-1的话要手动减去p。
\[\]
new_system
from random import randint
from Crypto.Util.number import getPrime,bytes_to_long
flag = b'moectf{???????????????}'
gift = bytes_to_long(flag)
def parametergenerate():
q = getPrime(256)
gift1 = randint(1, q)
gift2 = (gift - gift1) % q
x = randint(1, q)
assert gift == (gift1 + gift2) % q
return q , x , gift1, gift2
def encrypt(m , q , x):
a = randint(1, q)
c = (a*x + m) % q
return [a , c]
q , x , gift1 , gift2 = parametergenerate()
print(encrypt(gift1 , q , x))
print(encrypt(gift2 , q , x))
print(encrypt(gift , q , x))
print(f'q = {q}')
'''
[48152794364522745851371693618734308982941622286593286738834529420565211572487, 21052760152946883017126800753094180159601684210961525956716021776156447417961]
[48649737427609115586886970515713274413023152700099032993736004585718157300141, 6060718815088072976566240336428486321776540407635735983986746493811330309844]
[30099883325957937700435284907440664781247503171217717818782838808179889651361, 85333708281128255260940125642017184300901184334842582132090488518099650581761]
q = 105482865285555225519947662900872028851795846950902311343782163147659668129411
'''
一道简单的消元解方程，不用管x是多少，直接就可以消掉了……
from random import randint
from Crypto.Util.number import getPrime,bytes_to_long,long_to_bytes
import gmpy2
a1=48152794364522745851371693618734308982941622286593286738834529420565211572487
c1=21052760152946883017126800753094180159601684210961525956716021776156447417961
a2=48649737427609115586886970515713274413023152700099032993736004585718157300141
c2=6060718815088072976566240336428486321776540407635735983986746493811330309844
a=30099883325957937700435284907440664781247503171217717818782838808179889651361
c=85333708281128255260940125642017184300901184334842582132090488518099650581761
q = 105482865285555225519947662900872028851795846950902311343782163147659668129411
t=(a*(c1+c2)-(a1+a2)*c)%q
s=(a-a1-a2)%q
d=gmpy2.invert(s,q)
g=(t*d)%q
print(long_to_bytes(g))
#b'moectf{gift_1s_present}'
\[\]
RSA_revenge
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
from secret import flag
def emirp(x):
y = 0
while x !=0:
y = y*2 + x%2
x = x//2
return y
while True:
p = getPrime(512)
q = emirp(p)
if isPrime(q):
break
n = p*q
e = 65537
m = bytes_to_long(flag)
c = pow(m,e,n)
print(f"{n = }")
print(f"{c = }")
"""
n = 141326884939079067429645084585831428717383389026212274986490638181168709713585245213459139281395768330637635670530286514361666351728405851224861268366256203851725349214834643460959210675733248662738509224865058748116797242931605149244469367508052164539306170883496415576116236739853057847265650027628600443901
c = 47886145637416465474967586561554275347396273686722042112754589742652411190694422563845157055397690806283389102421131949492150512820301748529122456307491407924640312270962219946993529007414812671985960186335307490596107298906467618684990500775058344576523751336171093010950665199612378376864378029545530793597
"""
这道题的q和p是有关系的。
\[\]
我们知道对于二进制数，乘2代表左移一位，模2代表右移一位。因此不难发现q其实是p的二进制逆序数，而且还是素数。
\[\]
其实函数名字就在提示我们了，emirp正是prime的逆序。
\[\]
既然知道p与q的关系，自然的想法是遍历p并找到对应的q，且二者乘积等于n。
怎么爆破呢？
\[\]
因为p和q相反，我们进行判定时一定需要p和q两个数，如果仅仅从低位到高位或者高位到低位爆破，二者乘积一开始只为512位，而n的大小介于1023~1024位之间，这样效率很低。
\[\]
因此我们考虑从两端同时爆破，这样p和q一开始就有512位相乘，效率应当更好。
from Crypto.Util.number import getPrime, isPrime, bytes_to_long,long_to_bytes
import gmpy2
n = 141326884939079067429645084585831428717383389026212274986490638181168709713585245213459139281395768330637635670530286514361666351728405851224861268366256203851725349214834643460959210675733248662738509224865058748116797242931605149244469367508052164539306170883496415576116236739853057847265650027628600443901
c = 47886145637416465474967586561554275347396273686722042112754589742652411190694422563845157055397690806283389102421131949492150512820301748529122456307491407924640312270962219946993529007414812671985960186335307490596107298906467618684990500775058344576523751336171093010950665199612378376864378029545530793597
def factor(a,b,k):
if k==256:
if a*b==n:
print([a,b])
return a,b
else:
for i in range(2):
for j in range(2):
a1=a+i*(2**k)+j*(2**(511-k))
b1=b+j*(2**k)+i*(2**(511-k))
if a1*b1>n:
continue
if (a1+2**(511-k))*(b1+2**(511-k))<n :
continue
if (a1*b1)%(2**(k+1))!=n%(2**(k+1)):
continue
factor(a1,b1,k+1)
factor(0,0,0)
p=12119998731259483292178496920109290754181396164390285597126378297678818779092115139911720576157973310671490865211601201831597946479039132512609504866583931
q=11660635291534613230423193509391946961264539191735481147071890944740311229658362673314192872117237108949853531941630122241060679012089130178372253390640871
phi=(p-1)*(q-1)
e=65537
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#b'moectf{WA!y0u@er***g00((d))}'