0x01 原理分析

在RSA密钥对生成中，dp和dq是两个与私钥相关的参数。

dp是$d \bmod (p-1)$的值，dq是$d \bmod (q-1)$的值。这些值用于进行私钥操作，如解密和签名。

即：
$$
\begin{cases}
dp\equiv d \pmod {(p-1)}\\
dq\equiv d \pmod {(q-1)}
\end{cases}
$$

在网络安全的Crypto题目中，关于dp和dq一般有如下几种情况：

    1. 已知$n、e、dp、c$，求m；
    • 1.1 已知 $p、e、dp、c、b$，其中$n=p^bq$，求m；
    • 1.2 已知 $n、e、dp_0、c、k$，其中$dp_0$为$dp$的高$(n\text{bits}-k)$位，即$dp_0=dp>>k$，求m；
    • 1.3 已知 $n、e、dp、c$，其中$dp$很小，e很大，求m；
    • 1.4 已知 $n、e、c$，其中$dp$过小，求m；
    1. 已知$p、q、dp、dq、c$，求m。

0x0101 已知n、e、dp、c，求m

此类题目一般来说给的n比较大，需要通过dp来分解n。

显然我们有以下两个公式：
$$
\begin{align*}
dp &\equiv d \pmod {(p-1)}\\
d \times e &\equiv 1 \pmod {\phi(n)}
\end{align*}
$$
其中$\phi{(n)=(p-1)\times(q-1)}$，可以得：
$$
\begin{align*}
dp \times e & \equiv d\times e \pmod {(p-1)}\\
\Rightarrow d \times e & \equiv 1 \pmod {(p-1)}\\
\Rightarrow d \times e & =k \times (p-1)+1 \text{ \\注意这里是等号}\\
\Rightarrow d \times e & =k \times (p-1)+dp \times e \text{ \\注意这里是等号}
\end{align*}
$$
又由$d \times e \equiv 1 \pmod {\phi(n)}$和上面所得等式，可得：
$$
\begin{align*}
d \times e & =1 \pmod{(p-1)\times(q-1)}\\
k \times (p-1)+dp \times e & =k_1 \times (p-1)\times(q-1)+1\\
dp \times e & = k_1 \times (p-1)\times(q-1)+1-k \times (p-1) \\
dp \times e & = [k_1 \times (q-1)-k]\times (p-1)+1
\end{align*}
$$
设$x = k_1 \times (q-1)-k$，则有：
$$
dp \times e = x \times (p-1)+1
$$
又因为：
$$
dp < p - 1
$$
所以，可以得出要使$dp \times e = x \times (p-1)+1$等式成立，则有$x < e$，显然$x>0$，所以：
$$
x \in (0,e)
$$
即：
$$
[k_1 \times (q-1)-k ]\in(0,e)
$$
只需要遍历$(0,e)$中的整数，当以下两个等式成立时：
$$
\begin{align*}
(dp \times e-1) \bmod x &=0,\\
n \bmod{[(dp \times e -1 ) \div x +1]} & = 0
\end{align*}
$$
n就成功被分解出来了，然后就是常规rsa解法。

python3解密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def decrypt(e,n,c,dp):
    for x in range(1, e):
        if(e*dp%x==1):
            p=(e*dp-1)//x+1
            if(n%p!=0):
                continue
            q=n//p
            phin=(p-1)*(q-1)
            d=gp.invert(e, phin)
            m=gp.powmod(c, d, n)
            if(len(hex(m)[2:])%2==1):
                continue
            print(bytes.fromhex(hex(m)[2:]))

0x0102 已知 p、e、dp、c、b，其中$n=p^bq$，求m；

（推导略）

python3解密代码：

1
2
3
4
5
6
7
8
def decrypt(e,c,b,p,dp):
    mp1 = pow(c, dp, p)
    mp = pow(c, dp - 1, p)
    for i in range(1, b - 2):
        x = pow(c - pow(mp1, e), 1, p**(i + 1))
        y = pow(x * mp * (gmpy2.invert(e, p)), 1, p**(i + 1))
        mp1 = mp1 + y
    print(long_to_bytes(mp1))

0x0103 已知 n、e、dp_0、c、k$，其中dp_0为dp的高$(n\text{bits}-k)位，即dp_0=dp>>k，求m；

sage解密代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
F.<x> = PolynomialRing(Zmod(n))
d = inverse_mod(e, n)
for k in range(1, e):
	f = (secret << 200) + x + (k - 1) * d
	x0 = f.small_roots(X=2 ** (200 + 1), beta=0.44, epsilon=1/32)
	if len(x0) != 0:
		dp = x0[0] + (secret << 200)
		for i in range(2, e):
			p = (e * Integer(dp) - 1 + i) // i
			if n % p == 0:
				break
		if p < 0:
			continue
		else:
			print('k = ',k)
			print('p = ',p)
			print('dp = ',dp)
			break

0x0104 已知 n、e、dp、c，其中dp很小，e很大，求m；

未完待续。。

0x0105 已知 n、e、c，其中dp过小，求m；

未完待续。。

0x0106 已知p、q、dp、dq、c，求m。

python3解题代码：

1
2
3
4
5
6
7
8
9
def decrypt(p,q,dp,dq,c):
    n = p*q
    phin = (p-1)*(q-1)
    dd = gp.gcd(p-1, q-1)
    d=(dp-dq)//dd * gp.invert((q-1)//dd, (p-1)//dd) * (q-1) +dq
    print(d)

    m = gp.powmod(c, d, n)
    print(bytes.fromhex(hex(m)[2:]))