factor
factor
easy_factor1
task.py
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag
p,q,r = getPrime(256),getPrime(256),getPrime(256)
n = p*q*r
phi = (p-1)*(q-1)*(r-1)
key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))
print("n =",n)
print("hint =",getrandbits(256)*phi**3)
print("c =",c)
'''
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
'''
這題給的這個hint，關鍵怎么處理。hint=k*phi**3，我們嘗試分解hint
顯然用sagemath的factor是不能分解的，于是我用ChatGPT寫分解部分因數的腳本
exp_1
# 定義大整數
n = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
# 嘗試找到小因子
def trial_division(n, max_factor=1000000):
factors = {}
for i in range(2, max_factor + 1):
while n % i == 0:
if i in factors:
factors[i] += 1
else:
factors[i] = 1
n //= i
return factors, n # 返回因子及其次方和剩余部分
# 獲取因子及次方
known_factors, remaining = trial_division(n)
# 輸出結果
print("已知因子及其次方:")
for factor, exponent in known_factors.items():
print(f"{factor}^{exponent} ",end='')
#已知因子及其次方:
#2^11 3^6 7^3 13^6 41^3 79^3 83^3 277^3 248701^3
這些三次方的素因子，比如7，它一定是(p-1)(q-1)(r-1)中的某個的因子，于是我就假設它是p-1的素因子，然后我把hint除以7**3，剩下的也一定是
\[x(q-1)(r-1)=x*phi(qr)
\]
\]
這里的x是p-1除去7的剩余量，根據歐拉定理，于是有
\[a^{x*phi(qr)}\equiv 1\ mod\ (\ qr\ )
\]
\]
所以
\[gcd(a^{x*phi(qr)}-1,n)=qr
\]
\]
exp_2
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
n = 343127312894441264623060100705188723106648253383902349620699412384677995734576572885137280031507308915752070128528949423639735964709160841591038148069185325450544546735392923674211031016035209702254447128968565740534765322198664691
hint = 3802744632475774666777934738986183209966233570124815804333822490240409933768208822899072601181527365734196352249978937639454658680559993507805820991037544059215540360338084909833242583087617315128513337647913472696515770688338805196215328080662137260951972365100322795737835152857750114216709340410268143017180826135339564387228460663261697814425298725805568817218360964967025967384766127098203664964210047103829182895016532403825215903779806760754721373523135367007867453212189953817229696304611549977864533229540971457717668560698088917340909962348110683581294453903261530189579223087858081200349343639420534779115290433982968345085704202494045885911950427043282588446343291558819683037970053828479057449781943479407877748772895179095205885377333120540311815022381056
c = b';#\x1b\xa6R\xe2\x1d\x9dpf\x8e\xda\xe4\x14\x9a\xfb\tr\x99\x8a\xc9r\x03C\xb58Zb\x97\x0b\xc7S\x0fa\x88\xb4\xe4\x16.M\x92\x94\x94\x8b\xa9Ki\x9b\xe4\xe9d5\xa3~\x1a\x9cx\x03\xdc\x1f\x87\x14E\x90'
p = n // (GCD(pow(2,hint//7**3,n)-1,n))
q = n // GCD(pow(2,hint//277**3,n)-1,n)
r = n // p // q
key = sha256(str(p+q+r).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
flag = enc.decrypt(c)
print(flag)
#NSSCTF{Just_simply_try_t0_divid3_s0m3_f4ct0rs_0f_phi}
easy_factor2
task.py
from Crypto.Util.number import *
from random import *
from gmpy2 import *
from secret import flag
m = bytes_to_long(flag)
def gen_prime(bits,common_bits):
shift = bits - common_bits
while(True):
high = ((1<<(common_bits-1)) + getrandbits(common_bits-1)) << shift
p = high + 2*getrandbits(shift-1) + 1
q = high + 2*getrandbits(shift-1) + 1
if(isPrime(p) and isPrime(q)):
return p,q
p,q = gen_prime(1024,350)
n = p*q
leak = (pow(p,q,n) + pow(q,p,n)) & ((1 << 300) - 1)
e = 65537
c = pow(m,e,n)
print("n =",n)
print("e =",e)
print("c =",c)
print("leak =",leak)
#n = 20304817598463991883487911425007927214135740826150882692657608404060781116387976327509281041677948119173928648751205240686682904704601086882134602075008186227364732648337539221512524800875230120183740426722086488143679856177002068856911689386346260227545638754513723197073169314634515297819111746527980650406024533140966706487847121511407833611739619493873042466218612052791074001203074880497201822723381092411392045694262494838335876154820241827541930328508349759776586915947972105562652406402019214248895741297737940426853122270339018032192731304168659857343755119716209856895953244774989436447915329774815874911183
#e = 65537
#c = 7556587235137470264699910626838724733676624636871243497222431220151475350453511634500082904961419456561498962154902587302652809217390286599510524553544201322937261018961984214725167130840149912862814078259778952625651511254849935498769610746555495241583284505893054142602024818465021302307166854509140774804110453227813731851908572434719069923423995744812007854861031927076844340649660295411912697822452943265295532645300241560020169927024244415625968273457674736848596595931178772842744480816567695738191767924194206059251669256578685972003083109038051149451286043920980235629781296629849866837148736553469654985208
#leak = 1511538174156308717222440773296069138085147882345360632192251847987135518872444058511319064
我們看這個leak，其實
\[p^q+q^p\ mod\ n
\]
\]
\[p^q\equiv 0\ mod\ p
\]
\]
\[q^p\equiv p\ mod\ p
\]
\]
所以我們得到的是p+q的低300位，另外，p和q的高350位相同，所以我們暴破25位就可以得到p+q。下面我們研究怎么求p+q的高350位
\[(p+q)^2-(p-q)^2=4pq\\
(p-q)^2=(p+q)^2-4pq
\]
(p-q)^2=(p+q)^2-4pq
\]
根據費馬分解的思想，我們讓p+q從2根號n開始，通過我改變這25bit來調整p+q的大小
from Crypto.Util.number import *
import gmpy2
n=20304817598463991883487911425007927214135740826150882692657608404060781116387976327509281041677948119173928648751205240686682904704601086882134602075008186227364732648337539221512524800875230120183740426722086488143679856177002068856911689386346260227545638754513723197073169314634515297819111746527980650406024533140966706487847121511407833611739619493873042466218612052791074001203074880497201822723381092411392045694262494838335876154820241827541930328508349759776586915947972105562652406402019214248895741297737940426853122270339018032192731304168659857343755119716209856895953244774989436447915329774815874911183
e=65537
c=7556587235137470264699910626838724733676624636871243497222431220151475350453511634500082904961419456561498962154902587302652809217390286599510524553544201322937261018961984214725167130840149912862814078259778952625651511254849935498769610746555495241583284505893054142602024818465021302307166854509140774804110453227813731851908572434719069923423995744812007854861031927076844340649660295411912697822452943265295532645300241560020169927024244415625968273457674736848596595931178772842744480816567695738191767924194206059251669256578685972003083109038051149451286043920980235629781296629849866837148736553469654985208
leak=1511538174156308717222440773296069138085147882345360632192251847987135518872444058511319064
psq=2*gmpy2.iroot(n,2)[0]
psq=psq>>325<<325
for i in range(2**25):
t=psq+2**300*i+leak
if (t**2>4*n):
temp=gmpy2.iroot(t**2-4*n,2)
if (temp[1]):
p_q=temp[0]
p=(t+p_q)//2
q=n//p
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
print(long_to_bytes(pow(c,d,n)))
break
easy_factor3
task.py
from Crypto.Util.number import *
from secret import flag
def gen_noisy_sum_of_base(m,p):
sum = 0
while(m):
sum += m % p
m //= p
return sum//1000
flag = bytes_to_long(flag)
e = 65537
p = getPrime(256)
q = getPrime(256)
n = p*q
m1 = getRandomNBitInteger(2048)
m2 = getRandomNBitInteger(2048)
print("m1 =",m1)
print("m2 =",m2)
print("sum1 =",gen_noisy_sum_of_base(m1,p))
print("sum2 =",gen_noisy_sum_of_base(m2,p))
print("n =",n)
print("c =",pow(flag,e,n))
'''
m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205
'''
這里的m其實就是p進制表示。
\[m=ap^n+bp^{n-1}+...+cp+d
\]
\]
注意到sum，模1000的余數沒有了，沒關系，我們可以爆破
\[sum_0=\frac{a+b+...+c+d}{1000}
\]
\]
還原后的sum滿足
\[m-sum=a(p^n-1)+b(p^{n-1}-1)+..+c(p-1)
\]
\]
右邊都有p-1這個因子。所以
\[m\equiv sum(mod\ p-1)
\]
\]
所以
\[m_1-sum_1=k_1(p-1)\\
m_2-sum_2=k_2(p-1)
\]
m_2-sum_2=k_2(p-1)
\]
利用gcd恢復(p-1).
exp
import math
from Crypto.Util.number import long_to_bytes
import gmpy2
m1 = 23145761572719481962762273155673006162798724771853359777738044204075205506442533110957905454673168677138390288946164925146182350082798412822843805544411533748092944111577005586562560198883223125408349637392132331590745338744632420471550117436081738053152425051777196723492578868061454261995047266710226954140246577840642938899700421187651113304598644654895965391847939886431779910020514811403672972939220544348355199254228516702386597854501038639792622830084538278039854948584633614251281566284373340450838609257716124253976669362880920166668588411500606044047589369585384869618488029661584962261850614005626269748136
m2 = 21293043264185301689671141081477381397341096454508291834869907694578437286574195450398858995081655892976217341587431170279280993193619462282509529429783481444479483042173879669051228851679105028954444823160427758701176787431760859579559910604299900563680491964215291720468360933456681005593307187729279478018539532102837247060040450789168837047742882484655150731188613373706854145363872001885815654186972492841075619196485090216542847074922791386068648687399184582403554320117303153178588095463812872354300214532980928150374681897550358290689615020883772588218387143725124660254095748926982159934321361143271090861833
sum1 = 309575642078438773208947649750793560438038690144069550000470706236111082406
sum2 = 303394719183577651416751448350927044928060280972644968966068528268042222965
n = 4597063839057338886607228486569583368669829061896475991448013970518668754752831268343529061846220181652766402988715484221563478749446497476462877699249731
c = 3253873276452081483545152055347615580632252871708666807881332670645532929747667442194685757039215506084199053032613562932819745309368748317106660561209205
e=65537
for i in range(1001):
for j in range(1001):
x1=sum1*1000+i
x2=sum2*1000+j
p_1=math.gcd(m1-x1,m2-x2)
if(p_1>2**255):
p=p_1 +1
q=n//p
d=gmpy2.invert(e,(p-1)*(q-1))
m=long_to_bytes(pow(c,d,n))
if b'NSSCTF'in m:
print(m)
break
#b'NSSCTF{M@k3_U53_0F_GCD_beHinD_th3_p-Base!}'
easy_factor4
task.py
from Crypto.Util.number import *
from Crypto.Util.Padding import *
from Crypto.Cipher import AES
from hashlib import sha256
from random import *
from secret import flag
p = getPrime(256)
q = getPrime(256)
n = p*q
phi = (p-1)*(q-1)
e = 65537
d = inverse(e,phi)
key = sha256(str(p+q).encode()).digest()
enc = AES.new(key, AES.MODE_ECB)
c = enc.encrypt(pad(flag,16))
hint = getPrime(20)*d**3 + getPrime(128)*phi**2
print("n =",n)
print("c =",c)
print("hint =",hint)
'''
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
'''
\[hint=ad^3+t?(n)^2
\]
\]
瞪眼法，看到d3馬上乘以一個e3
\[e^3hint=a(ed)^3+te^3?(n)^2
\]
\]
又因為
\[ed=1+k?(n)
\]
\]
代入
\[e^3hint=a(1+k?(n))^3+te^3?(n)^2
\]
\]
簡化一下：
\[e^3hint=a+K?(n)
\]
\]
對于正確的a，有：
\[2^{e^3hint-a}=2^{K?(n)}=1\ (mod\ n)
\]
\]
用暴破求a后，再用factor1的方法去把Kphi分解求p(或q)
exp
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
e=65537
for a in range(2**20):
if isPrime(a):
if(pow(2,e**3*hint-a,n)==1):
print(a)
break
from Crypto.Util.number import isPrime, long_to_bytes
import gmpy2
import math
import hashlib
from Crypto.Cipher import AES
n = 8218998145909849489767589224752145194323996231101223014114062788439896662892324765430227087699807011312680357974547103427747626031176593986204926098978521
c = b'\x9a \x8f\x96y-\xb4\tM\x1f\xe6\xcc\xef\xd5\x19\xf26`|B\x10N\xd7\xd0u\xafH\x8d&\xe3\xdbG\x13\x8e\xea\xc0N\n\r\x91\xdc\x95\x9b\xb1Ny\xc1\xc4'
hint = 1860336365742538749239400340012599905091601221664081527583387276567734082070898348249407548568429668674672914754714801138206452116493106389151588267356258514501364109988967005351164279942136862087633991319071449095868845225164481135177941404709110974226338184970874613912364483762845606151111467768789248446875083250614540611690257121725792701375153027230580334095192816413366949340923355547691884448377941160689781707403607778943438589193122334667641037672649189861
e=65537
a=565237
def decrypt(enc):
aes = AES.new(key, AES.MODE_ECB)
return aes.decrypt(enc)
kphi=e**3*hint-a
print(kphi)
p=math.gcd(pow(2,kphi//73,n)-1,n)
q=n//p
key = hashlib.sha256(str(p+q).encode()).digest()
dec = decrypt(c)
print(dec)
b'NSSCTF{H0w_70_F4ct0R_N_7h1s_tim3?}\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e\x0e'
總結
- 上一篇： 当前安卓App加固到底该如何做到防篡改?
- 下一篇： 初窥江湖之PhotoShop抠图(一)