潜心的博客

强网杯2022-强网先锋-ASR

2022-7-31 CryptoRSACRT强网杯2022

# ASR

from Crypto.Util.number import getPrime
from secret import falg
pad = lambda s:s + bytes([(len(s)-1)%16+1]*((len(s)-1)%16+1))

n = getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2 * getPrime(128)**2
e = 3

flag = pad(flag)
print(flag)
assert(len(flag) >= 48)
m = int.from_bytes(flag,'big')
c = pow(m,e,n)

print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')

'''
n = 8250871280281573979365095715711359115372504458973444367083195431861307534563246537364248104106494598081988216584432003199198805753721448450911308558041115465900179230798939615583517756265557814710419157462721793864532239042758808298575522666358352726060578194045804198551989679722201244547561044646931280001
e = 3
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
'''
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

# writeup

记4个质数为 、 、 和 ，则 ，对 开平方后发现该数比较小，且由4个128bit的质数相乘所得，使用yafu分解 ，耗时40多分钟，得到 、 、 和

发现 的欧拉函数与 不互质，且 很小，结合CRT求解，参考：vsCTF Crypto wp_远志梦边的博客-CSDN博客 (opens new window)

将同余方程 化成

然后应用中国剩余定理求解，Sage Cell Server (sagemath.org) (opens new window)

p = 218566259296037866647273372633238739089
q = 225933944608558304529179430753170813347
r = 223213222467584072959434495118689164399
t = 260594583349478633632570848336184053653
c = 945272793717722090962030960824180726576357481511799904903841312265308706852971155205003971821843069272938250385935597609059700446530436381124650731751982419593070224310399320617914955227288662661442416421725698368791013785074809691867988444306279231013360024747585261790352627234450209996422862329513284149
e = 3

P.<m> = PolynomialRing(Zmod(p),implementation='NTL')
f = m^e - c;f
m1 = f.monic().roots()

P.<m> = PolynomialRing(Zmod(q),implementation='NTL')
f = m^e - c;f
m2 = f.monic().roots()

P.<m> = PolynomialRing(Zmod(r),implementation='NTL')
f = m^e - c;f
m3 = f.monic().roots()

P.<m> = PolynomialRing(Zmod(t),implementation='NTL')
f = m^e - c;f
m4 = f.monic().roots()

m1 = [int(i[0]) for i in m1]
m2 = [int(i[0]) for i in m2]
m3 = [int(i[0]) for i in m3]
m4 = [int(i[0]) for i in m4]

text_num = []
for pp in m1:
    for qq in m2:
        for rr in m3:
            for tt in m4:
                try:
                    text_num.append(crt([pp,qq,rr,tt],[p,q,r,t]))
                except:
                    continue

print(text_num)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
[1306173663174680354544083835098873046665147955161485267105809626183470299213147062484361435517127425037465762176491160436617371316470553010760895171531168, 2803358489265171472227210840490862843537881207776943757296126230937523911331160681955579712312498104881693839057868862438866912819678753688485739816184899, 1248984295174749683050825615411469211061247361327166117293032213981703895553936323127707213641064897178474925251326429742817744892644764737209862, 1475292321022733362914538619161388693005464952363739416469049560011153697847764341022230542196966303658527328460810763143999529259177792246387209275640333, 100044157419370198679087166259775289290892005571323188951843576772070435867939694842618860647633985719775199337911491746464610636804630306648035254654063, 169118659097037303545204467113341261751786208263501510690406051120715612616321174091805429807546092262126463462794527958708587685524984128271078841319027, 1529007847379796407634756887525822026696243818376722108701969132742428428165312563623502055174162111318912346740690335148179223775392999980945766987459837, 153759683776433243399305434624208622981670871584305881184763149503345166185487917443890373624829793380160217617791063750644305153019838041206592966473567, 222834185454100348265422735477774595442565074276484202923325623851990342933869396693076942784741899922511481742674099962888282201740191862829636553138531]
1

转为字符得到flag

import libnum

flag = [1306173663174680354544083835098873046665147955161485267105809626183470299213147062484361435517127425037465762176491160436617371316470553010760895171531168, 2803358489265171472227210840490862843537881207776943757296126230937523911331160681955579712312498104881693839057868862438866912819678753688485739816184899, 1248984295174749683050825615411469211061247361327166117293032213981703895553936323127707213641064897178474925251326429742817744892644764737209862, 1475292321022733362914538619161388693005464952363739416469049560011153697847764341022230542196966303658527328460810763143999529259177792246387209275640333, 100044157419370198679087166259775289290892005571323188951843576772070435867939694842618860647633985719775199337911491746464610636804630306648035254654063, 169118659097037303545204467113341261751786208263501510690406051120715612616321174091805429807546092262126463462794527958708587685524984128271078841319027, 1529007847379796407634756887525822026696243818376722108701969132742428428165312563623502055174162111318912346740690335148179223775392999980945766987459837, 153759683776433243399305434624208622981670871584305881184763149503345166185487917443890373624829793380160217617791063750644305153019838041206592966473567, 222834185454100348265422735477774595442565074276484202923325623851990342933869396693076942784741899922511481742674099962888282201740191862829636553138531]
for i in flag:
    if b'flag' in libnum.n2s(i):
        print(libnum.n2s(i))
1
2
3
4
5
6
b'flag{Fear_can_hold_you_prisoner_Hope_can_set_you_free}\x06\x06\x06\x06\x06\x06'
1

# 相关文章

  1. 针对CTFer的e与phi不互素的问题 - 墨天轮 (modb.pro) (opens new window)

遇到e与phi不互素的问题，首先就考虑问题的复杂程度，从e的大小和e与phi的公约数大小入手。总结出了三个板子针对不同的情况。不过遇到实际的问题还需具体情况具体分析。

  • e较小
from Crypto.Util.number import *
import gmpy2
c = 
e = 
n = 
p = 
q = 
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(e,phi)
print(t)
_e = e // t
d = gmpy2.invert(_e,phi)
_m = pow(c,d,n)
m = gmpy2.iroot(_m,t)[0]
print(long_to_bytes(m))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
  • e不算大但需结合CRT求解
from Crypto.Util.number import *
import gmpy2
p = 
q = 
c = 
n = 
e = 
phi = (p - 1) * (q - 1)

R.<x> = Zmod(p)[]
f = x ^ e - c
f = f.monic()
res1 = f.roots()
 
R.<x> = Zmod(q)[]
f = x ^e - c
f = f.monic()
res2 = f.roots()
for i in res1:
    for j in res2:
        ai = [i[0],j[0]]
        mi = [p,q]
        flag = CRT_list(ai,mi)
        flag = long_to_bytes(flag)
        if b'flag' in flag:
            print(flag)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
  • e很大，AMM算法
from Crypto.Util.number import *
import gmpy2
import time
import random
from tqdm import tqdm
e = 
p = 
q = 
n = p * q
c = 

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 = 1
    while (k * s + 1) % r != 0:
        k += 1
    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 = - discrete_log(d, a)
            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 onemod(p,r): 
    t=p-2 
    while pow(t,(p-1) // r,p)==1: 
        t -= 1 
    return pow(t,(p-1) // r,p) 
 
def solution(p,root,e):  
    g = onemod(p,e) 
    may = set() 
    for i in range(e): 
        may.add(root * pow(g,i,p)%p) 
    return may

cp = c % p
cq = c % q
mp = AMM(cp,e,p)
mq = AMM(cq,e,q)
mps = solution(p,mp,e)
mqs = solution(q,mq,e)
for mpp in tqdm(mps):
    for mqq in mqs:
        ai = [int(mpp),int(mqq)]
        mi = [p,q]
        m = CRT_list(ai,mi)
        flag = long_to_bytes(m)
        if b'NCTF' in flag:
            print(flag)
            exit(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
  1. RSA笔记 | ZhouYetao (opens new window)

我们顺利的求出 、 之后，结果计算模反元素时发现 与 不互素

这种情况比较容易理解，和低加密指数分解类似：

n = p * q
c ≡ (m ** e) mod n
phi(n) = (p - 1) * (q - 1)
gcd(e,phi(n)) = t
e = e1 * t
c ≡ (m ** (e1 * t)) mod n
将m ** t看成一个整体，利用e1和phi求出模反元素，接出m ** t，再将求解出来的进行开t次方，条件是t不是很大
1
2
3
4
5
6
7
  • 在这里， 不仅与 不互素， 反而成了 的一个因数，可以利用AMM算法进行实现。AMM算法的python实现，但是需要用sagemath跑脚本
import random
from Crypto.Util.number import long_to_bytes

def AMM(o, r, 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))

    t = 0
    s = q - 1
    while s % r == 0:
        t += 1
        s = s // r
    k = 1
    while (k * s + 1) % r != 0:
        k += 1
    alp = (k * s + 1) // r
    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:
            j = - discrete_log(d, a)
        b = b * (c^r)^j
        h = h * c^j
        c = c^r
    result = o^alp * h
    return result

def findAllPRoot(p, e):
    proot = set()
    while len(proot) < e:
        proot.add(pow(random.randint(2, p-1), (p-1)//e, p))
    return proot

def findAllSolutions(mp, proot, cp, p):
    all_mp = set()
    for root in proot:
        mp2 = mp * root % p
        assert(pow(mp2, e, p) == cp)
        all_mp.add(mp2)
    return all_mp


c = 15433214846771804225704093824935372144929516863829752998270111032551363583267576397009018518790803908369965458162930857063271509296349091229352855725285388975497906340053281554202527432848881160125418406408621879995822551367228501163128699032015069585502994319524445505522625561831240862136447585120010288772692097621553249775117843166714346924868089146429002417223863834435968726551668931140147337199939823985783939085842479154589529244209712172799274024573845157268545992888944742377166586536479490962335287124809557709167220756920767331929168230518135523463578566851417486746667008938122693256033127001185017237773
p = 0xa892eb59b175bcf896be2176598f278437fe10ef032279f06e1092143acfb3c16b31811cca5286699595c2720c652ee64f8adc92c8b16a5601dd981d6f839ce9c0513db30de88c2ec6cae1a726acbd235ea946631bde633707d766287a2f075e9aace1606bd8b4f52d4f5b87dfb81f14fbc5338004575e9430257e180a169eff
q = 0xe3d47225b77e56129dc3fed716181845f89fa15b2eb35453ffdc0f05cdf57c0d90410911d209818e886b202bc4893ebe85a07ef670122f0e70092de1b7963c3b24a58c6a9ec9ed677db3473b1882d10d550e45c18fd57b85a70a5401a074d36760e85c7e6258f0ab08fa69cd433709910fad6e145f7b85f589e83d61d3baf6ad
n = p * q
e = 0x3
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=",mps)
print("mqs=",mqs)


flag = []
for mpp in mps:
    for mqq in mqs:
        solution = CRT_list([int(mpp), int(mqq)], [p, q])
        flag.append(solution)
print("flag=",flag)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

# 相关题目

NCTF2019-官方writeup | CN-SEC 中文网 (opens new window)

记5道RSA_WustHandy的博客-CSDN博客 (opens new window)

NCTF2019 Crypto easyRSA

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

是 φ 的一个因子，无法求出私钥 

from gmpy2 import *
from Crypto.Util.number import *
from tqdm import tqdm
def onemod(p,r):
    t = p-2
    while pow(t, (p-1) // r, p) == 1: t -= 1
    return pow(t, (p-1) // r, p)
def solution(p,root): 
    g = onemod(p, 0x1337)
    may = []
    for i in range(0x1337):
        if i % 100 == 0:
            print(i)
        may.append(root * pow(g,i,p) % p)
    return may
c = 10562302690541901187975815594605242014385201583329309191736952454310803387032252007244962585846519762051885640856082157060593829013572592812958261432327975138581784360302599265408134332094134880789013207382277849503344042487389850373487656200657856862096900860792273206447552132458430989534820256156021128891296387414689693952047302604774923411425863612316726417214819110981605912408620996068520823370069362751149060142640529571400977787330956486849449005402750224992048562898004309319577192693315658275912449198365737965570035264841782399978307388920681068646219895287752359564029778568376881425070363592696751183359
p = 199138677823743837339927520157607820029746574557746549094921488292877226509198315016018919385259781238148402833316033634968163276198999279327827901879426429664674358844084491830543271625147280950273934405879341438429171453002453838897458102128836690385604150324972907981960626767679153125735677417397078196059
q = 112213695905472142415221444515326532320352429478341683352811183503269676555434601229013679319423878238944956830244386653674413411658696751173844443394608246716053086226910581400528167848306119179879115809778793093611381764939789057524575349501163689452810148280625226541609383166347879832134495444706697124741
e = 0x1337
n = p * q
c_p = pow(c, (1 + 3307 * (p - 1) // e) // e, p)
C1 = solution(p, c_p)
c_q = pow(c, (1 + (2649 * (q - 1) // e)) // e, q)
C2 = solution(q, c_q)
a = invert(p, q)
b = invert(q, p)
flag=0
for i in tqdm(C1):
    for j in tqdm(C2):
        flag += 1
        if flag % 1000000 == 0:
            print(flag)
        x = (b * q * i + a * p * j) % n
        if b"NCTF{" in long_to_bytes(x):
            print(long_to_bytes(x))
            exit()
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
b'NCTF{T4k31ng_Ox1337_r00t_1s_n0t_th4t_34sy}e$71N{D]0su{ZDEKfEnY>TTQ(=qR?GBpN\\U{3@O\\/I8ZsxW.Uw)3&&s&xD-<Uf*pKXOkV0~oiWubv<VAD9roRJU9:9S?>MyZ<wMN~T||%PC*j]inkgus4f9t:g:O9!FsIas^?M*q:BU{_J*r"*6Fi94hdRUW#s0=N+][l}Js7j,c5kiLB+/f<_1*N=V3Eq%~s^!5Gh8*'
[Finished in 667.7s]
1
2