introduction

Join the Nep united team, and get busy again

[NCTF2019]easyRSA

The encryption code is as follows:

from flag import flag

e = 0x1337
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
n = p * q

assert(flag.startswith('NCTF'))
m = int.from_bytes(flag.encode(), 'big')
assert(m.bit_length() > 1337)

c = pow(m, e, n)
print(c)
# 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359

Both p and q are given. Isn't that for nothing?
Then he did it happily
It turned out that the solution was a pile of random code. I looked for it directly wp (it's not easy to find that only two people solved it during the game)
e and again φ Not mutually prime, but before [De1CTF2019]babyrsa and EzRSA None of the solutions are applicable
Then look at wp and give a new idea
Congruence equation
m e ≡ c ( m o d   n ) m^e \equiv c \quad (mod\ n) me≡c(mod n)
turn
{ m e ≡ c ( m o d   p ) m e ≡ c ( m o d   q ) \begin{cases} m^e &\equiv c \quad (mod\ p)\\ m^e &\equiv c \quad (mod\ q) \end{cases} {meme​≡c(mod p)≡c(mod q)​
Then in a finite field G F ( p ) GF(p) GF(p) and G F ( q ) GF(q) GF(q) is open to two equations respectively e e e power root, then C R T CRT CRT can be obtained m m m (wonderful)
The key is how to open an arbitrary power root in a finite field
The author gave an AMM algorithm:

Here are some modifications to the code of wp:

import random
import time

def cal_k(s, r):
    R.<x> = PolynomialRing(GF(r))
    f = x * s + 1
    k = int(f.roots()[0][0])
    print(k)
    return k

# About 3 seconds to run
def AMM(o, r, q):
    start = time.time()
    print('\n----------------------------------------------------------------------------------')
    print('Start to run Adleman-Manders-Miller Root Extraction Method')
    print('Try to find one {:#x}th root of {} modulo {}'.format(r, o, q))
    g = GF(q)
    o = g(o)
    p = g(random.randint(1, q))
    while p ^ ((q-1) // r) == 1:
        p = g(random.randint(1, q))
    print('[+] Find p:{}'.format(p))
    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    print('[+] Find s:{}, t:{}'.format(s, t))
    k = cal_k(s, r)
    alp = (k * s + 1) // r
    print('[+] Find alp:{}'.format(alp))
    a = p ^ (r**(t-1) * s)
    b = o ^ (r*alp - 1)
    c = p ^ s
    h = 1
    for i in range(1, t):
        d = b ^ (r^(t-1-i))
        if d == 1:
            j = 0
        else:
            print('[+] Calculating DLP...')
            j = - dicreat_log(a, d)
            print('[+] Finish DLP...')
        b = b * (c^r)^j
        h = h * c^j
        c = c ^ r
    result = o^alp * h
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    print('Find one solution: {}'.format(result))
    return result

def findAllPRoot(p, e):
    print("Start to find all the Primitive {:#x}th root of 1 modulo {}.".format(e, p))
    start = time.time()
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return proot

def findAllSolutions(mp, proot, cp, p):
    print("Start to find all the {:#x}th root of {} modulo {}.".format(e, cp, p))
    start = time.time()
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    end = time.time()
    print("Finished in {} seconds.".format(end - start))
    return all_mp


c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
cp = c % p
cq = c % q
mp = AMM(cp, e, p)
mq = AMM(cq, e, q)
p_proot = findAllPRoot(p, e)
q_proot = findAllPRoot(q, e)
mps = findAllSolutions(mp, p_proot, cp, p)
mqs = findAllSolutions(mq, q_proot, cq, q)
print(mps, mqs)

def check(m):
    h = m.hex()
    if len(h) & 1:
        return False
    if bytes.fromhex(h).startswith(b'NCTF'):
        print(bytes.fromhex(h))
        return True
    else:
        return False


# About 16 mins to run 0x1337^2 == 24196561 times CRT
start = time.time()
result = []
print('Start CRT...')
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        if check(solution):
            print(solution)
            result.append(bytes.fromhex(solution.hex()))
    print(time.time() - start)

end = time.time()
print("Finished in {} seconds.".format(end - start))
print("result:", result)

The results obtained are as follows:

Regardless of the derivation of the algorithm and the code itself (because I don't understand it at all), is this approach beneficial to other e and φ Does the situation of non mutualism apply?
After the test, it is found that if AMM algorithm is to be applied, two conditions need to be met:
I r ∣ q − 1 r|q-1 r ∣ q − 1, II ∃ k ∈ Z ， s . t .   r ∣ k s + 1 \exist k\in \mathbb{Z}，s.t.\space r|ks+1 ∃k∈Z，s.t. r∣ks+1
The first condition needs to be met because t > 0 must be made, otherwise a = p ^ (r**(t-1) * s) will make an error
If condition 2 is not satisfied, there will be no solution in the end, or as written in the original code:

k = 1
while (k * s + 1) % r != 0:
	k += 1

It loops until the memory overflows

The author said that the inspiration came from a root ten problem of hackergame 2019, so he went to find it This problem
AMM algorithm can be applied to y in this problem, e=10
The results are as follows:

In fact, it can also be calculated directly. The time is almost the same, and the results are the same:

y_roots = []
y = 116513882455567447431772208851676203256471727099349255694179213039239989833646726805040167642952589899809273716764673737423792812107737304956679717082391151505476360762847773608327055926832394948293052633869637754201186227370594688119795413400655007893009882742908697688490841023621108562593724732469462968731
z = 88688615046438957657148589794574470139777919686383514327296565433247300792803913489977671293854830459385807133302995575774658605472491904258624914486448276269854207404533062581134557448023142028865220726281791025833570337140263511960407206818858439353134327592503945131371190285416230131136007578355799517986306208039490339159501009668785839201465041101739825050371023956782364610889969860432267781626941824596468923354157981771773589236462813563647577651117020694251283103175874783965004467136515096081442018965974870665038880840823708377340101510978112755669470752689525778937276250835072011344062132449232775717960070624563850487919381138228636278647776184490240264110748648486121139328569423969642059474027527737521891542567351630545570488901368570734520954996585774666946913854038917494322793749823245652065062604226133920469926888309742466030087045251385865707151307850662127591419171619721200858496299127088429333831383287417361021420824398501423875648199373623572614151830871182111045650469239575676312393555191890749537174702485617397506191658938798937462708198240714491454507874141432982611857838173469612147092460359775924447976521509874765598726655964369735759375793871985156532139719500175158914354647101621378769238233
e = 10
R.<b> = PolynomialRing(GF(y^3))
g = b^e - z
for yr in g.roots():
    y_roots.append(yr[0])
print(y_roots)

(however, in the case of module y, it is useless to open the root of z to the 10th power. It needs to open the root of module y^3. Although it is feasible in theory, it takes a lot of time.)

The author of this question also encountered the same problem
Then I found a question To discuss the solution of higher order surplus There is a paragraph in my blog:

For e and φ A possible solution to the non reciprocal prime problem

epilogue

e and φ The non reciprocal prime problem is still a problem to be studied. If it is encountered in the future, it will be studied again
Hope to continue to insist