Reference
基础
视频/会议
论文
题目
进阶
代码
拓展
工具
讨论
导言
在一般情况的RSA中，求出 ϕ ( N ) \phi(N) ϕ ( N ) e d ≡ 1 ( m o d ϕ ( N ) ) ed\equiv1 \pmod {\phi (N)} e d ≡ 1 ( m o d ϕ ( N ) ) d d d d d d g c d ( e , ϕ ( N ) ) = 1 gcd(e,\phi(N))=1 g c d ( e , ϕ ( N ) ) = 1 e e e ϕ ( N ) \phi(N) ϕ ( N )
简单情况（ e e e ϕ ( N ) \phi(N) ϕ ( N ) t t t 比较小 ，且 m t < N m^t<N m t < N
t t t m t ≥ N m^t \geq N m t ≥ N m t ( m o d N ) m^t \pmod N m t ( m o d N ) m m m m m m
假设 g c d ( e , ϕ ( N ) ) = t gcd(e,\phi(N))=t g c d ( e , ϕ ( N ) ) = t e ′ = e / t e'=e/t e ′ = e / t
则 m e ≡ m t e ′ ≡ c ( m o d N ) ) {m}^{e}\equiv{m^{t}}^{e'}\equiv c \pmod N) m e ≡ m t e ′ ≡ c ( m o d N ) )
又 d = invert ( e ′ , ϕ ( N ) ) d=\text{invert}(e',\phi(N)) d = invert ( e ′ , ϕ ( N ) ) ( e ′ ) − 1 ≡ d ( m o d ϕ ( N ) ) (e')^{-1} \equiv d \pmod{\phi(N)} ( e ′ ) − 1 ≡ d ( m o d ϕ ( N ) )
所以 m t ≡ c d ( m o d N ) {m}^{t}\equiv {c}^{d} \pmod N m t ≡ c d ( m o d N )
此时 m t m^t m t m t < N m^t<N m t < N m m m
import gmpy2
from Crypto.Util.number import long_to_bytes
phi = (p - 1) * (q - 1)
t = gmpy2.gcd(phi, e)
d = gmpy2.invert(e // t, phi)
M = gmpy2.powmod(c, d, n)
m = gmpy2.iroot(M, e)[0]
print(long_to_bytes(m))
e e e ( p − 1 ) (p-1) ( p − 1 ) ( q − 1 ) (q-1) ( q − 1 ) 这种情况下，e e e ( p − 1 ) (p-1) ( p − 1 ) ( q − 1 ) (q-1) ( q − 1 ) m e ≡ c ( m o d N ) m^e \equiv c \pmod N m e ≡ c ( m o d N )
{ m e ≡ c ( m o d p ) m e ≡ c ( m o d q ) \left\{\begin{array}{rcl}m^{e}&\equiv c \pmod p\\m^{e} &\equiv c \pmod q \\\end{array} \right.
{ m e m e ≡ c ( m o d p ) ≡ c ( m o d q )
中国剩余定理 - OI Wiki
Using the CRT with RSA
复杂的情况： p − 1 p-1 p − 1 q − 1 q-1 q − 1 e e e
开始还是一样的操作，拆解为
{ m e ≡ c ( m o d p ) m e ≡ c ( m o d q ) \left\{\begin{array}{rcl}m^{e}\equiv c\pmod p\\m^{e}\equiv c \pmod q\\\end{array} \right.
{ m e ≡ c ( m o d p ) m e ≡ c ( m o d q )
但此时 p − 1 p-1 p − 1 q − 1 q-1 q − 1 e e e d d d
AMM 算法
先从原算法开始，
原算法中只是涉及了开平方根的方法，此时的 e = 2 e=2 e = 2 p p p
对于 x 2 ≡ r ( m o d p ) x^{2}\equiv r\pmod p x 2 ≡ r ( m o d p ) r r r p p p p − 1 = 2 s t p-1=2^{s}t p − 1 = 2 s t
r ( p − 1 ) 2 ≡ r 2 s − 1 t ≡ 1 ( m o d p ) r^{(p-1) \over 2}\equiv r^{2^{s-1}t}\equiv 1 \pmod p
r 2 ( p − 1 ) ≡ r 2 s − 1 t ≡ 1 ( m o d p )
s = 1 s=1 s = 1 如果此时的 s = 1 s=1 s = 1
r t ≡ 1 ( m o d p ) r^t\equiv1 \pmod p
r t ≡ 1 ( m o d p )
两边同时乘上 r r r
r t + 1 2 ≡ ± r ≡ ± x ( m o d p ) r^{t+1 \over 2}\equiv \pm\sqrt{r} \equiv\pm x\pmod p
r 2 t + 1 ≡ ± r ≡ ± x ( m o d p )
此时套回我们的原式，得到
± m ≡ c t + 1 2 ( m o d p ) \pm m\equiv c^{t+1 \over 2}\pmod p
± m ≡ c 2 t + 1 ( m o d p )
此时我们只需要根据 p p p t t t
s > 1 s>1 s > 1 回到原式
r 2 s − 1 t ≡ 1 ( m o d p ) r^{2^{s-1}t}\equiv 1 \pmod p
r 2 s − 1 t ≡ 1 ( m o d p )
由于此时的 s > 1 s>1 s > 1
r 2 s − 2 t ≡ 1 ( m o d p ) r^{2^{s-2}t}\equiv 1 \pmod p
r 2 s − 2 t ≡ 1 ( m o d p )
r 2 s − 2 t ≡ − 1 ( m o d p ) r^{2^{s-2}t}\equiv -1\pmod p
r 2 s − 2 t ≡ − 1 ( m o d p )
因为存在两种不同的开方结果，所以我们需要同时乘上一个二次非剩余项 n 2 s − 1 t k n^{2^{s-1}tk} n 2 s − 1 t k − 1 -1 − 1
此式 n n n p p p n ( p − 1 ) 2 ≡ − 1 ( m o d p ) n^{(p-1) \over 2}\equiv -1\pmod p n 2 ( p − 1 ) ≡ − 1 ( m o d p ) n 2 s − 1 t ≡ − 1 ( m o d p ) n^{2^{s-1}t} \equiv-1\pmod p n 2 s − 1 t ≡ − 1 ( m o d p ) k k k k = 0 k=0 k = 0 n 0 = 1 n^0=1 n 0 = 1 k = 1 k=1 k = 1 n 2 s − 1 t ≡ − 1 ( m o d p ) n^{2^{s-1}t} \equiv-1 \pmod p n 2 s − 1 t ≡ − 1 ( m o d p ) − 1 -1 − 1
得到下式
r 2 s − 2 t n 2 s − 1 t k ≡ 1 ( m o d p ) r^{2^{s-2}t}n^{2^{s-1}tk}\equiv 1 \pmod p
r 2 s − 2 t n 2 s − 1 t k ≡ 1 ( m o d p )
这样我们便可以继续开方，以此往复，直到迭代成 s = 1 s=1 s = 1
r t n t ∗ ( 2 k 1 + 2 2 k 2 + . . . + 2 s − 1 k s − 1 ) ≡ 1 ( m o d p ) r^{t}{n}^{t*(2k_1+2^{2}k_2+...+2^{s-1}k_{s-1})}\equiv 1 \pmod p
r t n t ∗ ( 2 k 1 + 2 2 k 2 + . . . + 2 s − 1 k s − 1 ) ≡ 1 ( m o d p )
然后就和 s = 1 s=1 s = 1 r r r
r t + 1 2 n t ∗ ( k 1 + 2 k 2 + . . . + 2 s − 2 k s − 1 ) ≡ ± r ≡ ± x ( m o d p ) r^{t+1 \over 2}n^{t*(k_1+2k_2+...+2^{s-2}k_{s-1})} \equiv \pm \sqrt{r} \equiv \pm x \pmod p
r 2 t + 1 n t ∗ ( k 1 + 2 k 2 + . . . + 2 s − 2 k s − 1 ) ≡ ± r ≡ ± x ( m o d p )
即
c t + 1 2 n t ∗ ( k 1 + 2 k 2 + . . . + 2 s − 2 k s − 1 ) ≡ ± m ( m o d p ) c^{t+1 \over 2}n^{t*(k_1+2k_2+...+2^{s-2}k_{s-1})}\equiv\pm m \pmod p
c 2 t + 1 n t ∗ ( k 1 + 2 k 2 + . . . + 2 s − 2 k s − 1 ) ≡ ± m ( m o d p )
这里的 k 1 , k 2 k_1,k_2 k 1 , k 2
AMM 算法 ex
在 AMM 算法基础上，有人将开平方根的方法拓展到了开 n n n
对于 x e ≡ r ( m o d p ) x^{e}\equiv r \pmod p x e ≡ r ( m o d p ) r r r p p p e e e p − 1 = e s t p-1=e^{s}t p − 1 = e s t
很明显，我们前提条件是能整除 p − 1 p- 1 p − 1
r ( p − 1 ) e ≡ r e s − 1 t ≡ 1 ( m o d p ) r^{(p-1) \over e}\equiv r^{e^{s-1}t}\equiv 1\pmod p
r e ( p − 1 ) ≡ r e s − 1 t ≡ 1 ( m o d p )
此时，我们可以找到一个数 δ \delta δ t ∣ ( e δ − 1 ) t|(e\delta -1) t ∣ ( e δ − 1 )
r e s − 1 ( e δ − 1 ) ≡ 1 ( m o d p ) r^{e^{s-1}(e\delta -1)}\equiv 1\pmod p
r e s − 1 ( e δ − 1 ) ≡ 1 ( m o d p )
s = 1 s=1 s = 1 同样的，这里的 s = 1 s=1 s = 1
r e δ − 1 ≡ 1 ( m o d p ) r^{e \delta -1} \equiv 1 \pmod p
r e δ − 1 ≡ 1 ( m o d p )
两边同时乘上 r r r e e e
r δ ≡ r e ≡ x ( m o d p ) r^{\delta} \equiv \sqrt[e]{r} \equiv x \pmod p
r δ ≡ e r ≡ x ( m o d p )
s > 1 s>1 s > 1 此时我们可以和 e = 2 e=2 e = 2 e e e
K i = ρ i ∗ p − 1 e = ρ i ∗ e s − 1 t ( i 的范围为 [ 0 , e − 1 ] ) K_i=\rho^{{i}*{p-1\over{e}}}=\rho^{i*e^{s-1}t}\ (i \text{的范围为}[0,e-1])
K i = ρ i ∗ e p − 1 = ρ i ∗ e s − 1 t ( i 的范围为 [ 0 , e − 1 ] )
K i e = ρ i ∗ e s t = ρ i ∗ ( p − 1 ) {K_{i}}^{e}=\rho^{i*e^{s}t}=\rho^{i*(p-1)}
K i e = ρ i ∗ e s t = ρ i ∗ ( p − 1 )
根据欧拉定理 ρ p − 1 ≡ 1 ( m o d p ) \rho^{p-1}\equiv1\pmod p ρ p − 1 ≡ 1 ( m o d p )
k i e ≡ 1 ( m o d p ) {k_{i}}^{e}\equiv 1 \pmod p
k i e ≡ 1 ( m o d p )
那么 K i ∗ K e − i = ρ e ∗ p − 1 e = ρ p − 1 K_i*K_{e-i}=\rho^{e*{p-1 \over e}}=\rho^{p-1} K i ∗ K e − i = ρ e ∗ e p − 1 = ρ p − 1
根据欧拉定理也得
K i ∗ K e − i ≡ 1 ( m o d p ) K_i*K_{e-i} \equiv 1\pmod p
K i ∗ K e − i ≡ 1 ( m o d p )
即 K i K_i K i K e − i K_{e-i} K e − i
回到原式
r e s − 1 ( e δ − 1 ) ≡ 1 ( m o d p ) r^{e^{s-1}(e\delta -1)}\equiv 1\pmod p
r e s − 1 ( e δ − 1 ) ≡ 1 ( m o d p )
两边同时开 e e e K K K K e − j K_{e-j} K e − j
r e s − 2 ( e δ − 1 ) ≡ K e − j ( m o d p ) r^{e^{s-2}(e\delta -1)}\equiv K_{e-j} \pmod p
r e s − 2 ( e δ − 1 ) ≡ K e − j ( m o d p )
后续也和 e = 2 e=2 e = 2 K j K_j K j e e e
r e s − 2 ( e δ − 1 ) K j ≡ K e − j K j ≡ 1 ( m o d p ) r^{e^{s-2}(e\delta -1)}K_j\equiv K_{e-j}K_j \equiv 1\pmod p
r e s − 2 ( e δ − 1 ) K j ≡ K e − j K j ≡ 1 ( m o d p )
即
r e s − 2 ( e δ − 1 ) ρ j ∗ e s − 1 t ≡ 1 ( m o d p ) r^{e^{s-2}(e\delta -1)}\rho^{j*e^{s-1}t}\equiv 1\pmod p
r e s − 2 ( e δ − 1 ) ρ j ∗ e s − 1 t ≡ 1 ( m o d p )
以此往复，最终可以迭代成
r ( e δ − 1 ) ρ t ∗ ( e j 1 + e 2 j 2 + . . . + e s − 1 j s − 1 ) ≡ 1 ( m o d p ) r^{(e\delta -1)}\rho^{t*(ej_1+e^{2}j_2+...+e^{s-1}j_{s-1})}\equiv 1\pmod p
r ( e δ − 1 ) ρ t ∗ ( e j 1 + e 2 j 2 + . . . + e s − 1 j s − 1 ) ≡ 1 ( m o d p )
再两边同时乘 r r r e e e
r δ ρ t ∗ ( j 1 + e j 2 + . . . + e s − 2 j s − 1 ) ≡ x ( m o d p ) r^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv x\pmod p
r δ ρ t ∗ ( j 1 + e j 2 + . . . + e s − 2 j s − 1 ) ≡ x ( m o d p )
相当于
c δ ρ t ∗ ( j 1 + e j 2 + . . . + e s − 2 j s − 1 ) ≡ m ( m o d p ) c^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv m \pmod p
c δ ρ t ∗ ( j 1 + e j 2 + . . . + e s − 2 j s − 1 ) ≡ m ( m o d p )
此时我们便得到了其中一个根
剩余的解可以通过不断乘上集合 K K K
K i e ≡ 1 ( m o d p ) {K_i}^{e} \equiv 1\ (mod\ p) K i e ≡ 1 ( m o d p ) ( m K i ) e ≡ c ( m o d p ) {(mK_i)}^{e}\equiv c \pmod p ( m K i ) e ≡ c ( m o d p ) m K i mK_i m K i
复杂度分析
TR;DL
O ( l o g 4 q + r l o g 3 q ) \mathcal{O(log^4 q + rlog^3 q)} O ( l o g 4 q + r l o g 3 q )
逐步分析
为了找到一个 r r r ρ \rho ρ ρ q − 1 r ≠ 1 \rho^{q-1 \over r} \neq 1 ρ r q − 1 = 1 O ( log 3 q ) \mathcal{O}(\log^3 q) O ( log 3 q ) O ( 1 ) log q \mathcal{O}(1) \log q O ( 1 ) log q ρ \rho ρ ρ \rho ρ r r r 1 − ( 1 q ) O ( 1 ) 1 - \left(\frac{1}{q}\right)^{\mathcal{O}(1)} 1 − ( q 1 ) O ( 1 ) r r r O ( log 4 q ) \mathcal{O}(\log^4 q) O ( log 4 q )
循环外的工作仅仅是少量的指数运算。因此，它需要 O ( log 3 q ) \mathcal{O}(\log^3 q) O ( log 3 q ) b r t − i − 1 b^{r^{t-i-1}} b r t − i − 1 O ( ( t − i − 1 ) log r log 2 q ) \mathcal{O}((t-i-1)\log r \log^2 q) O ( ( t − i − 1 ) log r log 2 q ) 1 + 2 + ⋯ + ( t − 1 ) 1 + 2 + \cdots + (t-1) 1 + 2 + ⋯ + ( t − 1 ) O ( t 2 log r log 2 q ) \mathcal{O}(t^2 \log r \log^2 q) O ( t 2 log r log 2 q )
要计算离散对数 log a d \log_a d log a d O ( r log 2 q ) \mathcal{O}(r \log^2 q) O ( r log 2 q ) t − 1 t-1 t − 1 O ( t r log 2 q ) \mathcal{O}(tr \log^2 q) O ( t r log 2 q ) O ( log 4 q + r log 3 q ) \mathcal{O}(\log^4 q + r \log^3 q) O ( log 4 q + r log 3 q ) 注意 ，如果 r r r
AMM 之后的操作
我们解出了两方程的多组解
{ m e ≡ c ( m o d p ) m e ≡ c ( m o d q ) \left\{\begin{array}{rcl}m^{e} &\equiv c \pmod p\\m^{e} &\equiv c \pmod q \\\end{array} \right.
{ m e m e ≡ c ( m o d p ) ≡ c ( m o d q )
将1式的解和2式的解两两做一次 CRT，就有一组可以得到正确的 flag
Exploit
import random
import time
from Crypto.Util.number import * # pip install pycryptodome
import gmpy2 # pip install gmpy2
from tqdm import tqdm # pip install tqdm
def onemod(e, q):
p = random.randint(1, q - 1)
while ((gmpy2.powmod(p, (q - 1) // e, q)) == 1):
p = random.randint(1, q)
return p
def AMM_rth(x, e, N):
assert ((N - 1) % e == 0)
p = onemod(e, N)
t = 0
s = N - 1
while (s % e == 0):
s = s // e
t += 1
k = 1
while ((s * k + 1) % e != 0):
k += 1
delta = (s * k + 1) // e
a = gmpy2.powmod(p, e ** (t - 1) * s, N)
b = gmpy2.powmod(x, e * delta - 1, N)
c = gmpy2.powmod(p, s ,N)
h = 1
for i in tqdm(range(1, t)):
d = gmpy2.powmod(b, e ** (t - 1 -i), N)
if d == 1:
j = 0
else:
j = (- math.Log(d, a)) % e
b = b * (c ** (e ** j)) % N
h = h * (c ** j) % N
c = c ** e % N
result = gmpy2.powmod(x, delta, N) * h
return result
def ALL_ROOT2(r, q):
list1 = set()
while(len(list1) < r):
p = gmpy2.powmod(random.randint(1, q - 1), (q - 1) // r, q)
list1.add(p)
return list1
def ALL_Solution(m, q, rt, cq, e):
mp = []
for pr in rt:
r = (pr * m) % q
mp.append(r)
return mp
def calc(mp, mq, e, p, q):
i = 1
j = 1
t1 = gmpy2.invert(q, p)
t2 = gmpy2.invert(p, q)
for mp1 in mp:
for mq1 in mq:
j += 1
if j % 100000 == 0:
print(j)
ans = (mp1 * t1 * q + mq1 * t2 * p) % (p * q)
if check(ans):
return
return
def check(m):
try:
a = long_to_bytes(m)
if flag_info in a:
print(a)
return True
else:
return False
except:
return False
n =
c =
p =
q =
e =
flag_info = b'flag{'
cp = c % p
cq = c % q
print("start")
mp = AMM_rth(cp, e, p)
mq = AMM_rth(cq, e, q)
rt1 = ALL_ROOT2(e, p)
rt2 = ALL_ROOT2(e, q)
amp = ALL_Solution(mp, p, rt1, cp, e)
amq = ALL_Solution(mq, q, rt2, cq, e)
calc(amp, amq, e, p, q)
print("run over")
一点点魔法
回到一个月前画的饼
强网杯 2023 线上赛 Crypto -- not only rsa
e e e ϕ ( n ) \phi(n) ϕ ( n ) n n n factordb / factor()，可分为: n = p 5 n=p^5 n = p 5 C = m e ( m o d p 5 ) C = m ^ e \pmod{p^5} C = m e ( m o d p 5 )
Sagemath
sage: import libnum
....: Zmn = Zmod(p ** 5)
....: m_list = Zmn(c).nth_root(e, all = True) # 必要
....: for i in m_list:
....: m = libnum.n2s(int(i))
....: if b'flag{' in m:
....: print(m)
得到 flag，sage 的 nth_root() 不只有有限域开根，还附带了类似 Hensel's lemma 中的 lifting_roots，不过我还并未读过 nth_root() 的源码，链接放在了文章的 Reference 部分，感兴趣的朋友可以读读看，欢迎交流
特别感谢:
N1gh7ma|2e 师傅提供文档帮助
END.
