发表于 更新于

题目:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from secret import flag
from Crypto.Util.number import*
from gmpy2 import*

flag = b'D0g3xGC{****************}'

def gen_key(p, q):
    public_key = p*p*q
    e = public_key
    n = p*q
    phi_n = (p-1)*(q-1)
    private_key = inverse(e,phi_n)
    return public_key,private_key,e

p = getPrime(512)
q = getPrime(512)

N,d,e = gen_key(p,q)

c = gmpy2.powmod(bytes_to_long(flag),e,N)

print(N)
print(d)
print(c)

payload:

1
2
3
4
5
6
7
8
9
10
11
12
13
import gmpy2
import libnum
import math

from Crypto.Util.number import long_to_bytes

n = 539403894871945779827202174061302970341082455928364137444962844359039924160163196863639732747261316352083923762760392277536591121706270680734175544093484423564223679628430671167864783270170316881238613070741410367403388936640139281272357761773388084534717028640788227350254140821128908338938211038299089224967666902522698905762169859839320277939509727532793553875254243396522340305880944219886874086251872580220405893975158782585205038779055706441633392356197489
d = 58169755386408729394668831947856757060407423126014928705447058468355548861569452522734305188388017764321018770435192767746145932739423507387500606563617116764196418533748380893094448060562081543927295828007016873588530479985728135015510171217414380395169021607415979109815455365309760152218352878885075237009
c = 82363935080688828403687816407414245190197520763274791336321809938555352729292372511750720874636733170318783864904860402219217916275532026726988967173244517058861515301795651235356589935260088896862597321759820481288634232602161279508285376396160040216717452399727353343286840178630019331762024227868572613111538565515895048015318352044475799556833174329418774012639769680007774968870455333386419199820213165698948819857171366903857477182306178673924861370469175

pq = gmpy2.gcd(pow(2,d*n,n)-2,n)
m = pow(c,d,pq)
print(long_to_bytes(m))

推导 ：

e=N=p2∗qe = N = p^2*q
e∗d=1+k(p−1)(q−1)e*d=1+k(p-1)(q-1)
ap2∗q∗d−1=1mod(n)a^{p^2*q*d-1}=1 mod (n)
ap2∗q∗d−a=k∗na^{p^2*q*d}-a=k*n
显然2不为n的倍数，故令a=2a=2
2N∗d−2=k∗n2^{N*d}-2=k*n
n=gcd(2N∗d−2,N)n=gcd(2^{N*d}-2,N)

libnum.n2s出不来flag
但如果用

1
2
3
4
5
6
7
8
from gmpy2 import*
from libnum import*
n=...
d=...
c=...
pq=gcd(...)
m = pow(...)
print(n2s.(m))

就能出