2022 uuctf--- crypto Impossible_RSA

题目

import libnum
from Crypto.Util.number import getPrime
from flag import flag, e

p = getPrime(1024)
q = getPrime(1024)
n = p * q
assert e <= 500000
c = pow(libnum.s2n(flag), e, n)
leak1 = c % q
leak2 = c % p
leak3 = p + q
print("n =", n)
print("leak1 =", leak1)
print("leak2 =", leak2)
print("leak3 =", leak3)
n = 21256406304024147327122699985764737895162788854942201173538004689536569610046157311527715126074775927977409773971656249943602454790380966869525211733301201659688694473703188427037879868522859419364680904585572399937639393418586498509580133474303442722716959873727260844993296681950092753897902540593927952622713860163782763263944291810729056735965535138964485886748344167499818148134252327820007439830749462775149754781930983094046362696040641091039506998835624218220892441813224657845627120344960554424765109502415773475619490661527184126374299883610442465428985757004551740482644952396990065188807827114495184096249
leak1 = 8842431959638543756327530752221031675897458993985909403335303147413741167900365489182674478419510549838159493192002672500346433589707076289344572454304647803237654059883974235710442126617587691632375039292283285577033977676131772115877520248352227419433136507412485140428972344000541898060766721412300525883
leak2 = 127414092867622693231378230621806169422569654246682818498761930473755998913688181327473434110121174292309611256339271412324673262030535400937563769685033472683498585742711576446343086462569783541192470920638935990937187809422965809986860709074542257475025562691683977493260026623616012846939417988284096473040
leak3 = 293130152177150437492580785085598394773458388719469800871702200331766258900690595210759869625006484354799804558552583572062231998451041105464048317708732987121458633718573774164071597186461239762511364549980544029915308083867329707804739776241438307060614946195675715671343671137725809499387682363101164970886
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

过程分析

已知n=p*q,leak3=p+q,由此可以组成方程组，从而得到p和q。又leak1 = c % q、leak2 = c % p，使用中国剩余定理CRT组合一下可以计算出c。已知此时p,q,n,c，又e <= 500000,所以我们只需要爆破出一个合适的e即可获得flag。

解题代码

#sage
import gmpy2
import libnum

n = 21256406304024147327122699985764737895162788854942201173538004689536569610046157311527715126074775927977409773971656249943602454790380966869525211733301201659688694473703188427037879868522859419364680904585572399937639393418586498509580133474303442722716959873727260844993296681950092753897902540593927952622713860163782763263944291810729056735965535138964485886748344167499818148134252327820007439830749462775149754781930983094046362696040641091039506998835624218220892441813224657845627120344960554424765109502415773475619490661527184126374299883610442465428985757004551740482644952396990065188807827114495184096249
leak1 = 8842431959638543756327530752221031675897458993985909403335303147413741167900365489182674478419510549838159493192002672500346433589707076289344572454304647803237654059883974235710442126617587691632375039292283285577033977676131772115877520248352227419433136507412485140428972344000541898060766721412300525883
leak2 = 127414092867622693231378230621806169422569654246682818498761930473755998913688181327473434110121174292309611256339271412324673262030535400937563769685033472683498585742711576446343086462569783541192470920638935990937187809422965809986860709074542257475025562691683977493260026623616012846939417988284096473040
leak3 = 293130152177150437492580785085598394773458388719469800871702200331766258900690595210759869625006484354799804558552583572062231998451041105464048317708732987121458633718573774164071597186461239762511364549980544029915308083867329707804739776241438307060614946195675715671343671137725809499387682363101164970886
var('p q')
eq = [p*q-n,p+q-leak3]
result = solve(eq,p,q)[0]
print(result)
p = 161562249983202700035527081166558786031731223261198195999535987465827171883730733359944156020947215855022510635343983292897557354440470230745496731228302894376018866016596714241754815953745113727125200716224341010140868299262202025976056483744622119807303134689795661748036502596285135565503272596613700276343
q = 131567902193947737457053703919039608741727165458271604872166212865939087016959861850815713604059268499777293923208600279164674644010570874718551586480430092745439767701977059922316781232716126035386163833756203019774439784605127681828683292496816187253311811505880053923307168541440673933884409766487464694543
phi = n - leak3 + 1
c_list = [leak2,leak1]
p_q_list = [p,q]
c = CRT_list(c_list,p_q_list)
print(f'c={c}')
for e in range(1,5000001):
    try:
        d = gmpy2.invert(e,phi)
        m = pow(c,d,n)
        flag = libnum.n2s(int(m))
        if b'flag' in flag:
            print(flag)
            break
        else:
            continue
    except:
        continue

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

flag:

flag{c59d5fc3-610c-41ca-baef-b26f9a88648d}
1

【一位好姑娘不喜欢你，一定是你不够好，等到你哪天觉得自己足够好了，姑娘兴许也嫁了人了，某次在路上碰见了你，那时也别伤心，是缘分错了，不是你喜欢错了人，记住，在那位姑娘嫁人之后就别纠缠不清了，把那份喜欢藏好，都放在酒里。每次喝酒的时候，念着点她把未来日子过得好，别想着她什么日子过不好，回心转意来找你，那才是一个男人，真正的喜欢一个姑娘】