RSA

约 940 字大约 3 分钟

2025-11-15

Principle

大整数分解问题：

已知 $N$ ，对于 $N=p*q$ ，求 $p$ 和 $q$

其中： $p$ 和 $q$ 是大于1的素数

e phi 不互素

Task

[?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
'''

Solution

根据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:
            continue

NSSCTF平台有道题可以这样处理：

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

原理在于：

m^e = c \mod n \\ m^e = c_p \mod p

通过AMM算法可以求出一个 $m_p$ 满足：

m_p^e = c_p \mod p

再找一个 $a = pow(r,(p-1)//e,p)$ 且 $a \neq 1$ ，此时：

(m_p*a^k)e = (m_p)^e*t^{\frac{p-1}{e}*e*k}=(m_p)^e*1 = c_p \mod p \\ m = m_p*a^k

这个 $k$ 是可以遍历出来的。

看起来非常奇妙，还感觉这个方法似乎非常普适，但是当我回头用这个方法对刚才的NSSCTF那道题使用，得不到结果，why？

注意flag的情况，NSS那个flag非常长，转换后的数字比p或者q都大得多，而本题的flag转换后比p小，从而通过 $m_p*a^k$ 就能得到正确的m，而NSS那个只能通过分别求p和q的mp与mq，再通过CRT得到m了。

也就是说，m小于p或者q，并且e和(p-1)或者(q-1)的最大公因数是e本身时，e大但也不是太大，在计算机爆破的量级内时，可以通过这个方法求出m。而m比较大的时候，就需要CRT合并结果，此时需要e*e不能太大，否则难以遍历。

Reference

https://blog.csdn.net/m0_74345946/article/details/133936371