dp泄露

例题

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

攻击条件

已知e，n，dp，c，并且e不是很大

原理

先列出所有的条件：
dp=d%(p-1)
e*d≡1 mod (p-1)(q-1)

所以

k1(p-1)+dp=d
k2(p-1)(q-1)+e*d=1

从而可以得到

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

两边对p-1取余得
(e*dp)%(p-1)=1

所以e*dp=k(p-1)+1，由于e和dp都是已知的，所以只需枚举k，算出整数的p，并且这个p还要能整除n

所以

$$k=\frac{e * d p-1}{p-1}=e * \frac{d p}{p-1}-\frac{1}{p-1}$$

由dp=d%(p-1)我们可以知道dp<p-1，所以dp/(p-1)是小于1的，因此我们很容易得到k的上限要小于e

因此只需要用k遍历range(1,e) ,若p整除n,即可得到p,从而结束循环.

脚本

from gmpy2 import *
from Crypto.Util.number import *

# e+n+dp+c => m (e不是很大)

def rsa(e,n,dp,c):
    p=0
    for i in range(1,e):
        if (e*dp-1)%i==0:
            p=(e*dp-1)//i+1
            if n%p==0:
                break
    q=n//p
    d=invert(e,(p-1)*(q-1))
    print(long_to_bytes(pow(c,d,n)))


if __name__ == "__main__":
    e = 65537
    n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
    dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657
    c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

    rsa(e,n,dp,c)