大整数分解问题:
已知,对于,求和
其中:和是大于1的素数
约 940 字大约 3 分钟
2025-11-15
大整数分解问题:
已知N,对于N=p∗q,求p和q
其中:p和q是大于1的素数
[?CTF][Crypto][Week2]Common RSA:task.py
from Crypto.Util.number import *
from secret import flag
assert flag.startswith(b'flag{') and flag.endswith(b'}')
p, q = getPrime(512), getPrime(512)
n = p * q
e = 65537
m = bytes_to_long(flag)
c = pow(m, e, n)
hint = pow(p + q, 2, n)
print(f'{n = }')
print(f'{e = }')
print(f'{c = }')
print(f'{hint = }')
'''
n = 131597024257614620869648421307952022599943625170798058722475560465555374754170467986433278540604131619940641178519954230167502146438244308999511105433219427638803460889093328223802388178143540560813587991639442439109510325931982801296494725966519902673302205827914999084293810023067168509012158443748031939483
e = 65537
c = 1968659140793648429069472000786965200510587960406184785982668854732724642287423003255222009970017202179772168410459767605874195614574533370563277818681668876342943583147204497260995173839443989636764614809399895977498001560095317260220383552929292480197409615426208803132661827666690467265686165715909909838
hint = 8041845809205494984282719083536906169105876887210623661715566866580197885950852556859414098121226785749033039450259965513505083753685569890927709072642971188655408152663342066047346862975209503093968807589977151718256296935551857116746970823854584764670720138775077146982697233376686489502015164620786724
'''根据hint求出p和q不再赘述,这里只讨论求出p和q之后,会发现GCD(e,phi)=GCD(e,p-1)=GCD(e,q-1)==e,之前也碰到过e和phi不互素的情况,比如:[TGCTF2025][Crypto]ezrsa,其中就有GCD(e,phi)=15,GCD(e,p-1)=5,GCD(e,q-1)=3的情况,可使用有限域开方求解的:
d = inverse(e//GCD(e,(p-1)*(q-1)),(p-1)*(q-1))
c = pow(c,d,n)
R.<y>=PolynomialRing(Zmod(p))
f=y^15-c
f=f.monic()
m1=f.roots()
R.<z>=PolynomialRing(Zmod(q))
f=z^15-c
f=f.monic()
m2=f.roots()
for i in m1:
for j in m2:
m=solve_crt([int(i[0]),int(j[0])],[int(p),int(q)])
if b'TGCTF' in long_to_bytes(int(m)):
print(long_to_bytes(int(m)).decode())
# TGCTF{🙇🏮🤟_🫡🫡🫡_🚩🚩🚩}😃😖😘😨😢但这一次的公因子直接等于e,并且e比较大。网上搜索相关的信息说是可以使用AMM算法处理,分别在mod p和mod q下AMM,再使用crt升到mod n上,like:
def Gen_list(c,prime,e):
m = GF(p)(c).nth_root(e)
while True:
a = pow(random.randint(2,p-1),(p-1)//e,p)
if a != 1:
break
mprime = [int(m*a^i) for i in range(e)]
return mprime
mps = Gen_list(c,p,e)
mqs = Gen_list(c,q,e)
for mp in mps:
for mq in mqs:
try:
mm , _ = crt([p,q], [mp,mq])
flag = long_to_bytes(mm)
print(flag)
if b"flag{" in flag:
print(flag)
break
except:
continueNSSCTF平台有道题可以这样处理:
from Crypto.Util.number import long_to_bytes
from sympy.ntheory.modular import crt
import random
e = 1009
n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
m = GF(p)(c).nth_root(e)
while True:
a = pow(random.randint(2,p-1),(p-1)//e,p)
if a != 1:
break
p_list = [int(m*a^i) for i in range(e)]
m = GF(q)(c).nth_root(e)
while True:
a = pow(random.randint(2,q-1),(q-1)//e,q)
if a != 1:
break
q_list = [int(m*a^i) for i in range(e)]
for mp in p_list:
for mq in q_list:
try:
mm , _ = crt([p,q], [mp,mq])
flag = long_to_bytes(mm)
if b"NSSCTF{" in flag:
print(flag)
break
except:
continue但本题不行,e太大了,最后的CRT需要大概2^32次。看官方wp,直接在p得到的内容里边找:
m = GF(p)(c).nth_root(e)
while True:
a = pow(random.randint(2,p-1),(p-1)//e,p)
if a != 1:
break
for i in range(65537):
flag = long_to_bytes(int(m))
if b'flag' in flag:
print(flag)
break
m = m*a原理在于:
me=cmodnme=cpmodp
通过AMM算法可以求出一个mp满足:
mpe=cpmodp
再找一个a=pow(r,(p−1)//e,p)且a=1,此时:
(mp∗ak)e=(mp)e∗tep−1∗e∗k=(mp)e∗1=cpmodpm=mp∗ak
这个k是可以遍历出来的。
看起来非常奇妙,还感觉这个方法似乎非常普适,但是当我回头用这个方法对刚才的NSSCTF那道题使用,得不到结果,why?
注意flag的情况,NSS那个flag非常长,转换后的数字比p或者q都大得多,而本题的flag转换后比p小,从而通过mp∗ak就能得到正确的m,而NSS那个只能通过分别求p和q的mp与mq,再通过CRT得到m了。
也就是说,m小于p或者q,并且e和(p-1)或者(q-1)的最大公因数是e本身时,e大但也不是太大,在计算机爆破的量级内时,可以通过这个方法求出m。而m比较大的时候,就需要CRT合并结果,此时需要e*e不能太大,否则难以遍历。