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}