这类问题比较好识别，一般会给一个leak，它和p、q之间有直接关系，解题的核心就是数学推导。
常用性质和转化
同余的性质和运算
\(\begin{cases} a \pm b \equiv a\ \%\ n \pm b\ \%\ n \mod{n} \\ a \times b \equiv a\ \%\ n \times b\ \%\ n \mod{n} \\ a^b \equiv (a\ \%\ n)^b \mod{n} \end{cases}\)
当 \(\begin{cases} a \equiv b \mod{n} \\ c ≡ d \mod{n} \end{cases}\)，有 \(\begin{cases} a \pm c \equiv b \pm d \mod{n} \\ a \times c ≡ b \times d \mod{n} \end{cases}\)
当 \(\begin{cases} ak \equiv bk \mod{n} \\ \gcd(k,\ n) = 1 \end{cases}\)，有 \(a \equiv b \mod{n}\)
当 \(a \equiv b \mod{n}\)，
- 若 \(k\) 是正整数，有 \(ka \equiv kb \mod{kn}\)
- 若 \(k\) 是 \(a,b,n\) 的公因子，有 \(\frac{a}{k} \equiv \frac{b}{k} \mod{\frac{n}{k}}\)
- 若 \(p\ |\ n\)，有 \(a \equiv b \mod{p}\)
当 \(a \equiv b \mod{n_i}\ (i=1,\ 2,\ \cdots,\ k)\)，有 \(a \equiv b \mod{\operatorname{lcm}(n_1,\ n_2,\ \cdots,\ n_k)}\)
欧拉定理
当 \(\gcd(a,\ n) = 1\)，有 \(a^{\phi{n}} \equiv 1 \mod{n}\)
费马小定理
欧拉定理的一种特殊情况
当 \(\begin{cases} p是素数 \\ \gcd(a,\ p) = 1 \end{cases}\)，有 \(\begin{cases} a^{p-1} \equiv 1 \mod{p} \\ a^p \equiv a \mod{p} \end{cases}\)
e和k
设d是e模\(\phi{n}\)的逆元，有 \(d < \phi{n}\)，又因为 \(ed = 1 + k \phi{n}\)，所以 \(0 < k < e\)
有时候需要爆破k的大小
题型总结
\(leak = (p^q + q^p)\ \%\ n\)
\(leak \equiv p^q + q^p \mod{n} \\ \begin{cases} leak \equiv p^q + q^p \equiv p \mod{q} \\ leak \equiv p^q + q^p \equiv q \mod{p} \end{cases} \\ leak = p + k_{1}q = q + k_{2}p \\ (k_{1}-1)q = (k_{2}-1)p \\ 解一 \begin{cases} k_{1} = 1 \\ k_{2} = 1 \end{cases} \\ 解二 \begin{cases} k_{1} = k_{3}p+1 \\ k_{2} = k_{3}q + 1 \end{cases} \\ \because leak < n \\ \therefore 解二不成立 \\ 综上得\ leak = p + q\)
p, q = var('p q')
seq = [
leak == p + q,
n == p * q
]
print(solve(seq, p, q))\(leak = (n + p)\ \%\ (q - 1),\ 其中\ p > q\)
\(leak \equiv n + p \equiv pq + p \equiv 2p \mod{q-1} \\ leak = 2p + k(p - 1) \\ \because \begin{cases} 0 < leak < p - 1 \\ p > q \end{cases} \\ \therefore k = -2 \\ 综上得\ leak = 2(p - q + 1)\)
p, q = var('p q')
seq = [
leak == 2 * (p - q + 1),
n == p * q
]
print(solve(seq, p, q))\(leak = d + p + q\)
\(\because \begin{cases} \phi{n} = n - (p + q) + 1 \\ h = d + (p + q) \\ ed = 1 + k \phi{n} \end{cases} \\ 联立得\ \dfrac{ed - 1}{k} + h = n + d + 1 \\ ed - 1 = k(n + 1 - h) + kd \\ (e - k)d = k(n + 1 - h) + 1 \\ [k(n + 1 - h) + 1]\ \%\ (e - k) = 0 \\ 遍历\ k\ 即可\)
for k in range(1, e):
if (k * (n + 1 - leak) + 1) % (e - k) == 0:
d = (k * (n + 1 - leak) + 1) // (e - k)
m = pow(c, d, n)
print(long_to_bytes(m)) # 解不唯一更新：当 e 比较小时，\(k \approx \dfrac{e \cdot leak}{n}\)
\(leak_1 = (p + q)^e\ \%\ n,\ leak_2 = (p + e)^q\ \%\ n\)
出自：2020 巅峰极客 tryrsa
\(leak_2 \equiv (p + e)^q \equiv p + e \mod{q} \\ p \equiv leak_2 - e \mod{q} \\ leak_1 \equiv (p + q)^e \equiv p^e \equiv (leak_2 - e)^e \mod{q} \\ leak_1 - (leak_2 - e)^e = kq \\ q = \gcd(kq,\ n)\)
kq = leak1 - (leak2 - e)**e
q = gcd(kq, n)\(leak_1 = (p^e - q^e)\ \%\ n,\ leak_2 = (p - q)^e\ \%\ n\)
\(leak2 \equiv (p - q)^e \equiv p^e + \cdots + q^e \equiv p^e + q^e \mod{n} \\ \because \begin{cases} leak_1 \equiv p^e-q^e \mod{n} \\ leak_2 \equiv p^e+q^e \mod{n} \end{cases} \\ leak_1 + leak_2 \equiv 2 p^e \mod{n} \\ leak_1 + leak_2 \equiv 0 \mod{p} \\ leak_1 + leak_2 = kp \\ p = \gcd(kp,\ n)\)
kp = leak1 + leak2
p = gcd(kp, n)\(leak = (2023q + 231103)^p\ \%\ n\)
出自：2023 一带一路暨金砖（决赛） Crypto2
\(leak \equiv (2023q + 231103)^p \mod{n} \\ leak \equiv 231103^p \mod{q} \\ 两边同乘\ 231103^{p(q-1)} \\ leak \cdot 231103^{p(q-1)} \equiv 231103^{p + p(q-1)} \mod{q} \\ leak \equiv 231103^n \mod{q} \\ leak - 231103^n = kq \\ q = \gcd(kq,\ n)\)
这里还有一个知识点，就是\(231103^n\)数值太大了，直接 \(q = \gcd(leak - 231103^n,\ n)\) 是算不完的，优化方法就是 \(231103^n \Longrightarrow pow(231103,\ n,\ n)\)，证明：\(q = \gcd(leak - 231103^n\ \%\ n,\ n)\)
\(leak\ \%\ n - 231103^n\ \%\ n = kq\ \%\ n = kq + k_1 n = kq + k_1 pq = (k + k_1 p)q = k_2 q \\ \because q = \gcd(k_2 q,\ n) \\ \therefore q = \gcd(leak - 231103^n\ \%\ n,\ n)\)
kq = leak - pow(231103, n, n)
q = gcd(kq, n)\(c_1 = m^p\ \%\ n,\ c_2 = m^q\ \%\ n\)
出自：2023 NKCTF baby_RSA
\(\because \begin{cases} c_1 \equiv m^p \mod{n} \\ c_2 \equiv m^q \mod{n} \end{cases} \\ \therefore \begin{cases} c_1 \equiv m \mod{p} \\ c_2 \equiv m \mod{q} \end{cases} \\ c_1 c_2 \equiv (m + k_1 p)(m + k_2 q) \equiv m^2 + m(k_1 p + k_2 q) + 0 \equiv m^2 + m(c_1 - m + c_2 - m) \mod{n}\)
m = PolynomialRing(Zmod(n), 'm').gen()
f = c1*c2 - m**2 - m*(c1-m+c2-m)
for mbits in range(200, 500): # 爆破 m 的位数
res = f.small_roots(X=2**mbits, beta=1)
if res:
m = int(res[0])
print(long_to_bytes(m))
break\(p^{-1} = inverse(p,\ q),\ q^{-1} = inverse(q,\ p)\)
对于p和q，用扩展欧几里得可以求出整数s和t使得 \(ps + qt = \gcd(p,\ q) = 1\)，其中一正一负
假设 \(s > 0\)，\(t < 0\)，则 \(\begin{cases} p^{-1} = s \\ q^{-1} = t\ \%\ p = t + p \end{cases}\)
\(ps + qt = 1 \\ pp^{-1} + q(q^{-1} - p) = 1 \\ pp^{-1} + qq^{-1} - n = 1\)
p, q = var('p q')
seq = [
n == p * q,
p * inv_p + q * inv_q == 1 + n
]
print(solve(seq, p, q))转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 skatexu@qq.com