RSA中leak问题

1.RSA中leak=p^q%n + q^p%n问题

以ISCTF2024crypto蓝鲨的费马这道题为例子讲解自己学到的一个解决方法

import libnum
import gmpy2
from Crypto.Util.number import *
flag=b'ISCTF{********}'
m=bytes_to_long(flag)
p=libnum.generate_prime(1024)
q=libnum.generate_prime(1024)
n=p*q
e=0x10001
c=pow(m,e,n)
d=inverse(e,(p-1)*(q-1))
leak = (d+(pow(p,q,n)+pow(q,p,n)))%n
print("c=", c)
print("n=", n)
print("leak=", leak)
"""
c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
"""

$1.\text{leak} = d + p + q$ 其中 leak 简写为 L

$2. m = \text{pow}(c, d, n)，即 m = c^d \mod n.$

$3.d = L - (p + q) .$

根据欧拉函数的定义：$\phi = (p - 1)(q - 1) = pq - p - q + 1$

由于 n = pq ，因此：$\phi = n + 1 - (p + q)$

根据欧拉定理:$c^\phi \equiv1 \mod n$

代入 $\phi$的表达式：$c^{n + 1 - (p + q)} \equiv 1 \mod n$

可以进一步推导：$c^{n + 1} \equiv c^{p + q} \mod n$

因此:$c^{n + 1} \equiv c^{p + q} \mod n$

已知 d = L - (p + q) ，代入 $c^d \mod n = m$ ：

$c^{L - (p + q)} \mod n = m$

根据前面的推导：$c^{n + 1} \equiv c^{p + q} \mod n$

因此：$c^{L - (n + 1)} \mod n = m$

$m = \text{pow}(c, L - n - 1, n)$

c= 8989289659072309605793417141528767265266446236550650613514493589798432446586991233583435051268377555448062724563967695425657559568596372723980081067589103919296476501677424322525079257328042851349095575718347302884996529329066703597604694781627113384086536158793653551546025090807063130353950841148535682974762381044510423210397947080397718080033363000599995100765708244828566873128882878164321817156170983773105693537799111546309755235573342169431295776881832991533489235535981382958295960435126843833532716436804949502318851112378495533302256759494573250596802016112398817816155228378089079806308296705261876583997
n= 13424018200035368603483071894166480724482952594135293395398366121467209427078817227870501294732149372214083432516059795712917132804111155585926502759533393295089100965059106772393520277313184519450478832376508528256865861027444446718552169503579478134286009893965458507369983396982525906466073384013443851551139147777507283791250268462136554061959016630318688169168797939873600493494258467352326974238472394214986505312411729432927489878418792288365594455065912126527908319239444514857325441614280498882524432151918146061570116187524918358453036228204087993064505391742062288050068745930452767100091519798860487150247
leak= 9192002086528025412361053058922669469031188193149143635074798633855112230489479254740324032262690315813650428270911079121913869290893574897752990491429582640499542165616254566396564016734157323265631446079744216458719690853526969359930225042993006404843355356540487296896949431969541367144841985153231095140361069256753593550199420993461786814074270171257117410848796614931926182811404655619662690700351986753661502438299236428991412206196135090756862851230228396476709412020941670878645924203989895008014836619321109848938770269989596541278600166088022166386213646074764712810133558692545401032391239330088256431881
from Crypto.Util.number import long_to_bytes, inverse
m=pow(c,leak-n-1,n)
print(m)
flag=long_to_bytes(m)
print(flag)
#b'ISCTF{u_got_it}'

2.RSA中dp泄露(已知dp,e,n,c)

dp=d mod (p-1)

dq=d mod (q-1)

因为$\phi(n)=(p-1)*(q-1)$,这里也出现了（p-1）所以这几个存在一定的联系，一旦泄露可能会造成安全隐患。

题目部分数据

import gmpy2 as gp

e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751

同样先进行推导，化简成为一个可以靠程序解决的式子。

1.dp=d mod(p-1)

2.两边同乘e,$dpe \equiv de \mod(p-1)$

3.$ed =k_1*(p-1)+dpe,而ed \equiv 1 \mod \phi(n),\phi(n)=(p-1)(q-1)$

4.$k_1*(p-1)+dpe = 1+k_2(p-1)*(q-1)$

5.接下来就合并同类项解方程

6.化简得$dp*e=(k_2(q-1)-k_1)(p-1)+1$,令$k_2(q-1)-k_1=X$

7.$dp*e=X(p-1)+1$,首先dp<(p-1),所以X<e.

8.$p-1=\frac{dp*e-1}{X}$,因为X的范围已知直接遍历爆破即可求出p-1的值从而后续就变为常规RSA问题了

exp:

import gmpy2 as gp
from Crypto.Util.number import *
e = 65537
n = 248254007851526241177721526698901802985832766176221609612258877371620580060433101538328030305219918697643619814200930679612109885533801335348445023751670478437073055544724280684733298051599167660303645183146161497485358633681492129668802402065797789905550489547645118787266601929429724133167768465309665906113
dp = 905074498052346904643025132879518330691925174573054004621877253318682675055421970943552016695528560364834446303196939207056642927148093290374440210503657

c = 140423670976252696807533673586209400575664282100684119784203527124521188996403826597436883766041879067494280957410201958935737360380801845453829293997433414188838725751796261702622028587211560353362847191060306578510511380965162133472698713063592621028959167072781482562673683090590521214218071160287665180751


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=(q-1)*(p-1)            
            d=gp.invert(e,phi)         
            m=pow(c,d,n)               
                                     

print(long_to_bytes(m))  
#flag{wow_leaking_dp_breaks_rsa?_98924743502}

3.RSA中dp,dq泄露（dp,dq,c,p,q)

原谅我太懒了，懒得推导了直接脚本拿来用得了。

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

# dp+dq+p+q+c => m

def rsa(dp,dq,p,q,c):
    m1=pow(c,dp,p)
    m2=pow(c,dq,q)
    p_q=invert(p,q)
    m=m1+p_q*((m2-m1)%q)*p
    print(long_to_bytes(m))



if __name__ == "__main__":
    p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229 
    q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469 
    dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929 
    dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041 
    c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

    rsa(dp,dq,p,q,c)

#noxCTF{W31c0m3_70_Ch1n470wn}