P12.dp泄露

出题脚本

#coding:utf-8
import random
import base64
import hashlib
import string
import libnum

def put_flag():
    # 字符串列表
    a = string.printable
    flag = ""
    for i in range(10):
        flag += a[random.randint(0, 99)]
    flag = r"flag{%s}"%(hashlib.md5(flag.encode()).hexdigest())
    print(flag)
    return flag

#生成素数
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
e=65537
n=p*q
phi_n=(p-1)*(q-1)
d=libnum.invmod(e,phi_n)
dp=d%(p-1)
m=put_flag()
m=libnum.s2n(m)
n=p*q
c=pow(m,e,n)

print("n=",n)
print("e=",e)
print("dp=",dp)
print("c=",c)

解密脚本

#coding:utf-8
import libnum
import gmpy2

n= 20591086052762884774007642208627186047740785982069905465339106113815517926005138245376424039890471346116595814990565096469487055161205492208983070664066759158320021466738870626889248859926445073065690645149662384802893003569214932187478720052507261122240086903309849212209649669687231860209185304367043990868365998317112708060029389114801978983457120555456044119368210749131216212628106714166030746209367457730301494656881326171842507368964603885018433049753989158109159264897704177466521001420986879635961230539498749382319333460275823384358292388617142535346744858436238862753394517975326105321275152062417195136487
e= 65537
dp= 117650567231513516304011449747630188369389787217757178598401487861414722594762697578263686709962979384903219013406107957537598898044022905612629709116256327804419610618227360381750844695360296505774931533979275522382118810562627585509057288685774693859111511668637640128536485929734825688725882979874153712289
c= 11882214238703654387165659956294046561271974803426268099981312451686746219445527904685768634078193803230258145834800940089716687361084767393552437220859938746433048199198403178660887457673639116251966379227242789841204694915397745327702138343494160974011134668539019661693330405169786812935866677630175241506856985283075068700171501509407518847350856175791919328062950403163853767193784729690208750698852790441958574336390898190131490970318926320913093369651228634714453458106787439297347445279781184630937957106170862280836800221040231888465070504491616197979521787557062164298550636929825159364431658963099844517487

for i in range(1,65535):
    p=(dp*e-1)//i+1
    if n%p==0:
        q=n//p
        break
print(p)
print(q)
phi_n= (p-1)*(q-1)
d=gmpy2.invert(e,phi_n)
m=pow(c,d,n)
print(m)
flag=libnum.n2s(int(m)).decode()
print(flag)

题目解析

已知公钥n,e以及dp

其中,dp = d mod (p-1)

已知：

c = m^e mod n
m = c^d mod n
ϕ(n)=(p−1)*(q−1)
d∗e ≡ 1 mod ϕ(n)
dp = d mod (p−1)

由上式可以得到

dp*e≡d*e mod (p−1)

因此可以得到

式1：d∗e=k∗(p−1)+dp∗e
式2：d∗e≡1 mod ϕ(n)

式1带入式2

=> k∗(p−1)+dp∗e ≡1 mod ϕ(n)

=> k∗(p−1)+dp∗e ≡1 mod (p−1)∗(q−1)

=> k1∗(p−1)+dp∗e = k2*(p−1)∗(q−1)+1

=> dp*e =  k2*(p−1)∗(q−1)+1-k1∗(p−1)+dp∗e

=> dp*e = (p-1)*[k2*(p-1)-k1]+1

因dp<p−1（dp是d//（p-1）的余数，dp<p−1）

所以e > k2∗(q−1)−k1

假设 x=k2∗(q−1)−k1

x的范围为 (0,e)

x∗(p−1)+1=dp∗e

求出p-1方法，遍历(0,e)的范围，其中肯定有一个p可以被n整除，那么求出p和q