RSA_dp泄露
概述
dp是什么,其实dp就是由下面公式得到的一个数值而已
引入公式:dp=d mod (p-1)
如果题目给出dp和e的值,那我们如何求d和p-1呢
公式转换:
dp≡d mod (p-1) ----> dp*e=X*(p-1)+1
可以看出dp<p-1,因为模数是p-1
所以X<e
遍历X即可得到相应的p-1,从而确定得到的p-1是否正确
公式转换原理:
已知
dp≡d mod (p-1)
两边乘e
dp*e≡ d*e mod (p-1)
变形
d*e=dp*e+k1*(p-1)
RSA中已知
d*e≡1 mod ψ(n)
代入变形
dp*e+k1*(p-1)=k2*(p-1)*(q-1)+1
移项
dp*e=(p-1)*[k2*(q-1)-k1]+1
令X=k2*(q-1)-k1
dp*e=X*(p-1)+1
脚本:
for i in range(1,e):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)//i)+1)==0:
p=((dp*e-1)//i)+1
q=n//(((dp*e-1)//i)+1)
phi = (p-1)*(q-1)
简单的dp泄露(e值较小)
来道题目练一下手
import libnum
from Crypto.Util.number import *
import gmpy2
e = 65537
n = 13851998696110232034312408768370264747862778787235362033287301947690834384177869107768578977872169953363148442670412868565346964490724532894099772144625540138618913694240688555684873934424471837897053658485573395777349902581306875149677867098014969597240339327588421766510008083189109825385296069501377605893298996953970043168244444585264894721914216744153344106498382558756181912535774309211692338879110643793628550244212618635476290699881188640645260075209594318725693972840846967120418641315829098807385382509029722923894508557890331485536938749583463709142484622852210528766911899504093351926912519458381934550361
dp = 100611735902103791101540576986246738909129436434351921338402204616138072968334504710528544150282236463859239501881283845616704984276951309172293190252510177093383836388627040387414351112878231476909883325883401542820439430154583554163420769232994455628864269732485342860663552714235811175102557578574454173473
c = 6181444980714386809771037400474840421684417066099228619603249443862056564342775884427843519992558503521271217237572084931179577274213056759651748072521423406391343404390036640425926587772914253834826777952428924120724879097154106281898045222573790203042535146780386650453819006195025203611969467741808115336980555931965932953399428393416196507391201647015490298928857521725626891994892890499900822051002774649242597456942480104711177604984775375394980504583557491508969320498603227402590571065045541654263605281038512927133012338467311855856106905424708532806690350246294477230699496179884682385040569548652234893413
for i in range(1,e):
if (dp*e-1)%i == 0:
if n%(((dp*e-1)//i)+1)==0:
p=((dp*e-1)//i)+1
q=n//(((dp*e-1)//i)+1)
phi = (p-1)*(q-1)
d = gmpy2.invert(e,int(phi))
m=pow(c,d,n)
print(m)
print(long_to_bytes(m))
# flag{dp_i5_1eak}
题目来自ctfshow,忘记哪道题了
复杂一点的dp泄露(e值较大)
这里以2024SHCTF_week2的worde很大题目为例
题目:
import gmpy2
from Crypto.Util.number import *
from enc import flag
m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p*q
e = getPrime(200)
d = gmpy2.invert(e,(p-1)*(q-1))
dp = d % (p-1)
c = pow(m,e,n)
print(f"n = {n}")
print(f"c = {c}")
print(f"e = {e}")
print(f"dp = {dp}")
'''
n = 91474109447946939698871894276271960349001966373776561670033611686437073625283283462025516928670177367294038508158406344486154584864568554210741482771082715001758535316829142684289825367252858782265696639326396850801282684889129242486172992294823142583911322170757478424031474851783181401257378331689769296481
c = 5877060584498087890130818621122055683091640450112587806234197555471108164639525013165956387751673866886085091903378995979337504368634269097720082441063356774749459882930297745838555667149490678033502959184462876431994164681181090011026014832027023591051408725623171514973450454548128626787839106255936011788
e = 1211682611107712741308968071180820292192734522707746680561367
dp = 3419452508299853890819560327170076577399361954638904673370608939542172319303163958500652275316402880274830459420046394052885512271566857571683008797661351
'''
这里e是一个200位二进制长度的素数,如果像上面一样去遍历e确定X,这基本是不可能的
那如何来做呢
其实我们只需要对上面的公式变形即可(下面公式的符号“ ^ ”代指 “指数”,不是异或)
由dp*e=X*(p-1)+1已知
dp*e≡1 mod (p-1)
得到(p-1)的倍数
dp*e-1=k*(p-1)
由欧拉定理m^(p-1)≡1 mod p
m^(dp*e-1)≡1 mod p
转化
m^(dp*e)≡m mod p
得到p的倍数
m^(dp*e)-m=k1*p
(注:上面的m只要是一个与p互素的值即可,这里m取值越小计算越简单,建议为m=2)
这里我们费尽心思得到了p的一个倍数m^(dp*e)-m
而且我们知道其中n也是p的倍数
那如果我们取m^(dp*e)-m和n的公因数,那是不是就求出了p(这里就解释了我们为什么要费劲心思要求出p的一个倍数)
有了思路,我们就可以写出脚本
m = 2
p = gmpy2.gcd(pow(m, dp*e, n) - m, n)
(注意:这里求出m^(dp*e)后先对n取模,使其小于n,然后再与n求公因数)
完整的wp如下
import gmpy2
from Crypto.Util.number import *
n = 91474109447946939698871894276271960349001966373776561670033611686437073625283283462025516928670177367294038508158406344486154584864568554210741482771082715001758535316829142684289825367252858782265696639326396850801282684889129242486172992294823142583911322170757478424031474851783181401257378331689769296481
c = 5877060584498087890130818621122055683091640450112587806234197555471108164639525013165956387751673866886085091903378995979337504368634269097720082441063356774749459882930297745838555667149490678033502959184462876431994164681181090011026014832027023591051408725623171514973450454548128626787839106255936011788
e = 1211682611107712741308968071180820292192734522707746680561367
dp = 3419452508299853890819560327170076577399361954638904673370608939542172319303163958500652275316402880274830459420046394052885512271566857571683008797661351
m = 2
p = gmpy2.gcd(pow(m, e*dp, n) - m, n)
q=n//p
d=gmpy2.invert(e,(p-1)*(q-1))
print(long_to_bytes(pow(c,d,n)))
# SHCTF{w0Rd_E_Y0u_DIAN_dA_gAcFFE}