RSA-dp泄露

原理

0x00 基本数学公式

a = k * b + p

a mod b = p

0x01 RSA的基本公式

1
c ≡ m ^ e mod n
2
m ≡ c ^ d mod n
3
ϕ(n) = (p − 1) * (q − 1)
4
d * e ≡ 1 mod ϕ(n)         # 乘法逆元

0x02 dp是什么

1
dp ≡ d mod (p − 1)

0x03 推导过程

1
dp ≡ d mod (p − 1)
2
# 两边同时乘以 e
3
=> dp * e = d * e mod (p - 1)
4
=> dp * e = d * e - k * (p - 1)
5
=> d * e = dp * e + k * (p - 1)
6
# 与下面的公式结合
7
d * e ≡ 1 mod ϕ(n)

1
# 因为：
2
ϕ(n) = (p − 1) * (q − 1)
3
# 所以可以变形：
4
=> d * e = 1 mod (p − 1) * (q − 1)
5
# 变形：
6
dp * e + k * (p - 1) = 1 mod (p − 1) * (q − 1)

1
# 结合：
2
dp * e + k * (p - 1) = 1 + k * (p − 1) * (q − 1)
3
=> dp * e = 1 + k * (p − 1) * (q − 1) - k * (p - 1)
4
=> dp * e = 1 + [k * (q - 1) - k] * (p - 1)
5
# 设 i = [k * (q - 1) - k]
6
=> dp * e = 1 + i * (p - 1)

1
dp * e = 1 + i * (p - 1)
2
=> dp < p - 1
3
=> i < e
4
=> i ∈ (0, e)

0x04 求p

1
遍历 i（65537种可能），求出( p − 1 ) (p - 1) * (p − 1)，得到 p 且能被 n 整除；接下来就是常规 RSA 的解法

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

例题

[WUSTCTF2020] dp_leaking_1s_very_d@angerous

题目

1
e = 65537
2
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
3
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
4
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825

解密脚本

1
import gmpy2
2
import libnum
3
from Crypto.Util.number import long_to_bytes
4

5
e = 65537
6
n = 156808343598578774957375696815188980682166740609302831099696492068246337198792510898818496239166339015207305102101431634283168544492984586566799996471150252382144148257236707247267506165670877506370253127695314163987084076462560095456635833650720606337852199362362120808707925913897956527780930423574343287847
7
c = 108542078809057774666748066235473292495343753790443966020636060807418393737258696352569345621488958094856305865603100885838672591764072157183336139243588435583104423268921439473113244493821692560960443688048994557463526099985303667243623711454841573922233051289561865599722004107134302070301237345400354257869
8
dp = 734763139918837027274765680404546851353356952885439663987181004382601658386317353877499122276686150509151221546249750373865024485652349719427182780275825
9

10
for i in range(1, e):
11
    p = (dp * e - 1) // i + 1
12
    if n % p == 0:
13
        q = n // p
14
        phi = (p - 1) * (q - 1)
15
        d = gmpy2.invert(e, phi)
16
        m = pow(c, d, n)
17
        # print(m)
18
        print(long_to_bytes(m))
19
        # print(libnum.n2s(int(m)))
20
        break

dacj4n's

RSA-dp泄露

原理

0x00 基本数学公式

0x01 RSA的基本公式

0x02 dp是什么

0x03 推导过程

0x04 求p

例题

[WUSTCTF2020] dp_leaking_1s_very_d@angerous

题目

解密脚本