• Reference
  • 基础
    • What is modular arithmetic? (article) | Khan Academy
    • 中国剩余定理 - OI Wiki
  • 视频/会议
  • 论文
    • 1111.4877.pdf
  • 题目
    • hackergame2019-writeups/official/十次方根 at master · ustclug/hackergame2019-writeups · GitHub
    • Intended Solution to Crypto Problems in NCTF 2019 | Soreat_u's Blog
  • 进阶
    • Using the CRT with RSA
  • 代码
    • Python2 RSA/rth-root extraction at master · mad-jcbx/RSA · GitHub
  • 拓展
    • Elements of Z/nZ - Finite Rings
    • AMM 算法详解与应用
    • AMM算法简要理解（Adleman-Mander-Miller Method）
  • 工具
    • factordb
  • 讨论
    • Improved nth root for finite fields and integer_mods · Issue #7931 · sagemath/sage · GitHub
    • sage/src/sage/rings/finite_rings/integer_mod.pyx at 3dd953c3aa6b5143071b6c39208199cf128c8080 · sagemath/sage · GitHub

导言

---

在一般情况的RSA中，求出 $\phi(N)$ 就已经接近解出明文了。这个时候我们往往只需要通过 $ed\equiv1 \pmod {\phi (N)}$ 即可求出私钥 $d$，从而求出明文。但是要直接求逆元 $d$，需要满足 $gcd(e,\phi(N))=1$，也就是 $e$ 和 $\phi(N)$ 互质的情况。如果不满足，则会大大提高难度。

简单情况（ $e$ 和 $\phi(N)$ 的公约数 $t$ 比较小，且 $m^t<N$）

---

$t$ 有多小才算比较小呢，比较显然的是: 如果 $m^t \geq N$，那么 $m^t \pmod N$ 后再直接在有理数域下开根的结果就不是 $m$ 了，因为被模掉了，不过这步也能结合后面提到的有限域开根来计算 $m$，来降低后者一定计算量

假设 $gcd(e,\phi(N))=t$ ，令 $e'=e/t$

则 ${m}^{e}\equiv{m^{t}}^{e'}\equiv c \pmod N)$

又 $d=\text{invert}(e',\phi(N))$ ，换个写法 $(e')^{-1} \equiv d \pmod{\phi(N)}$

所以 ${m}^{t}\equiv {c}^{d} \pmod N$

此时 $m^t$ 可求且 $m^t<N$ 所以可据此直接开方求得 $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] # 如果m的小e次方大于N,则需要有限域下开根，继续往下看
# 当然，如果是大于N但小于2N，只需要计算二次剩余即可
print(long_to_bytes(m))

$e$ 和 $(p-1)$ 和 $(q-1)$ 互质

---

这种情况下，$e$ 和 $(p-1)$ 和 $(q-1)$ 互质，可以将 $m^e \equiv c \pmod N$ 拆解成

$\left\{\begin{array}{rcl}m^{e}&\equiv c \pmod p\\m^{e} &\equiv c \pmod q \\\end{array} \right.$

中国剩余定理 - OI Wiki

Using the CRT with RSA

复杂的情况： $p-1$ 或 $q-1$ 是 $e$ 的倍数

---

开始还是一样的操作，拆解为

$\left\{\begin{array}{rcl}m^{e}\equiv c\pmod p\\m^{e}\equiv c \pmod q\\\end{array} \right.$

但此时 $p-1$ 或 $q-1$ 是 $e$ 的倍数，是倍数的话，就无法直接通过求逆元的办法求出 $d$，这个时候就需要一种新的算法 —— AMM 算法

AMM 算法

先从原算法开始，

原算法中只是涉及了开平方根的方法，此时的 $e=2$，$p$ 为奇素数

对于 $x^{2}\equiv r\pmod p$ ，则说明 $r$ 是 $p$ 的一个二次剩余，令 $p-1=2^{s}t$，则有

$r^{(p-1) \over 2}\equiv r^{2^{s-1}t}\equiv 1 \pmod p$

$s=1$

如果此时的 $s=1$ 则有

$r^t\equiv1 \pmod p$

两边同时乘上 $r$，再开方即可得到

$r^{t+1 \over 2}\equiv \pm\sqrt{r} \equiv\pm x\pmod p$

此时套回我们的原式，得到

$\pm m\equiv c^{t+1 \over 2}\pmod p$

此时我们只需要根据 $p$ 算出 $t$ 即可

$s>1$

回到原式

$r^{2^{s-1}t}\equiv 1 \pmod p$

由于此时的 $s>1$，直接开根我们可以得到两个式子

$r^{2^{s-2}t}\equiv 1 \pmod p$

$r^{2^{s-2}t}\equiv -1\pmod p$

因为存在两种不同的开方结果，所以我们需要同时乘上一个二次非剩余项 $n^{2^{s-1}tk}$ ，这样便消除了 $-1$ 根的影响

此式 $n$ 为 $p$ 的一个非二次剩余，由 $n^{(p-1) \over 2}\equiv -1\pmod p$ 到 同上变换为$n^{2^{s-1}t} \equiv-1\pmod p$ ，$k$ 用来控制是否相乘，$k=0$ 时，此二次非剩余式则为 $n^0=1$，不做改变；$k=1$ 时，此二次剩余式为 $n^{2^{s-1}t} \equiv-1 \pmod p$，为 $-1$

得到下式

$r^{2^{s-2}t}n^{2^{s-1}tk}\equiv 1 \pmod p$

这样我们便可以继续开方，以此往复，直到迭代成 $s=1$ 的情况，即

$r^{t}{n}^{t*(2k_1+2^{2}k_2+...+2^{s-1}k_{s-1})}\equiv 1 \pmod p$

然后就和 $s=1$ 的情况一样，两边同时乘上 $r$，再开方，得

$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$

即

$c^{t+1 \over 2}n^{t*(k_1+2k_2+...+2^{s-2}k_{s-1})}\equiv\pm m \pmod p$

这里的 $k_1,k_2$ 等，只能够在一步步运算中得出

AMM 算法 ex

在 AMM 算法基础上，有人将开平方根的方法拓展到了开 $n$ 次方根

对于 $x^{e}\equiv r \pmod p$，则说明 $r$ 是 $p$ 的一个 $e$ 次剩余，令 $p-1=e^{s}t$，则有

很明显，我们前提条件是能整除 $p- 1$

$r^{(p-1) \over e}\equiv r^{e^{s-1}t}\equiv 1\pmod p$

此时，我们可以找到一个数 $\delta$ ，满足 $t|(e\delta -1)$，所以上式可以写为

$r^{e^{s-1}(e\delta -1)}\equiv 1\pmod p$

$s=1$

同样的，这里的 $s=1$ 时，直接有

$r^{e \delta -1} \equiv 1 \pmod p$

两边同时乘上 $r$，再开 $e$ 次方

$r^{\delta} \equiv \sqrt[e]{r} \equiv x \pmod p$

$s>1$

此时我们可以和 $e=2$ 的情况类似，构造一个 $e$ 次非剩余的集合，

$K_i=\rho^{{i}*{p-1\over{e}}}=\rho^{i*e^{s-1}t}\ (i \text{的范围为}[0,e-1])$

${K_{i}}^{e}=\rho^{i*e^{s}t}=\rho^{i*(p-1)}$

根据欧拉定理 $\rho^{p-1}\equiv1\pmod p$ 得

${k_{i}}^{e}\equiv 1 \pmod p$

那么 $K_i*K_{e-i}=\rho^{e*{p-1 \over e}}=\rho^{p-1}$

根据欧拉定理也得

$K_i*K_{e-i} \equiv 1\pmod p$

即 $K_i$ 与 $K_{e-i}$ 互为逆元

回到原式

$r^{e^{s-1}(e\delta -1)}\equiv 1\pmod p$

两边同时开 $e$ 次方得到一个集合 $K$ 中的数设为 $K_{e-j}$ (根据群论性质得）

$r^{e^{s-2}(e\delta -1)}\equiv K_{e-j} \pmod p$

后续也和 $e=2$ 的情况类似，只需要将上式不断乘上 $K_j$，开 $e$ 次方即可

$r^{e^{s-2}(e\delta -1)}K_j\equiv K_{e-j}K_j \equiv 1\pmod p$

即

$r^{e^{s-2}(e\delta -1)}\rho^{j*e^{s-1}t}\equiv 1\pmod 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$ 次方

$r^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv x\pmod p$

相当于

$c^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv m \pmod p$

此时我们便得到了其中一个根

剩余的解可以通过不断乘上集合 $K$ 即可

${K_i}^{e} \equiv 1\ (mod\ p)$
所以 ${(mK_i)}^{e}\equiv c \pmod p$
所以 $mK_i$ 也为一组解

复杂度分析

TR;DL

$\mathcal{O(log^4 q + rlog^3 q)}$

逐步分析

为了找到一个 $r$ 次非剩余 $\rho$，需要检查 $\rho^{q-1 \over r} \neq 1$。这个计算需要 $\mathcal{O}(\log^3 q)$ 的时间。如果我们对超过 $\mathcal{O}(1) \log q$ 个不同的随机选择的 $\rho$ 做这个操作，那么至少有一个 $\rho$ 将给出一个 $r$ 次非剩余的概率大于 $1 - \left(\frac{1}{q}\right)^{\mathcal{O}(1)}$。因此，找到一个 $r$ 次非剩余的期望时间是 $\mathcal{O}(\log^4 q)$。

循环外的工作仅仅是少量的指数运算。因此，它需要 $\mathcal{O}(\log^3 q)$ 的时间。要计算 $b^{r^{t-i-1}}$，需要 $\mathcal{O}((t-i-1)\log r \log^2 q)$ 的时间。因为总共有 $1 + 2 + \cdots + (t-1)$ 步，所以需要 $\mathcal{O}(t^2 \log r \log^2 q)$ 的时间。

要计算离散对数 $\log_a d$，使用蛮力搜索需要 $\mathcal{O}(r \log^2 q)$ 的时间。因为最坏情况下有 $t-1$ 个离散对数，所以需要 $\mathcal{O}(tr \log^2 q)$ 的时间。因此，最终的估计是 $\mathcal{O}(\log^4 q + r \log^3 q)$。注意，如果 $r$ 足够大，算法无法在多项式时间内运行。

AMM 之后的操作

我们解出了两方程的多组解

$\left\{\begin{array}{rcl}m^{e} &\equiv c \pmod p\\m^{e} &\equiv c \pmod q \\\end{array} \right.$

将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")

---

import random
import time
from Crypto.Util.number import long_to_bytes
import gmpy2
from tqdm import tqdm


def find_non_trivial_root(e, modulus):
    """在模 modulus 下找到一个非平凡的根，该根的 e 次幂不等于 1。"""
    candidate = random.randint(1, modulus - 1)
    while gmpy2.powmod(candidate, (modulus - 1) // e, modulus) == 1:
        candidate = random.randint(1, modulus)
    return candidate


def adaptive_multiplicative_method(x, e, modulus):
    """使用自适应乘法方法计算 x 的 e 次根模 modulus。"""
    assert (modulus - 1) % e == 0
    base = find_non_trivial_root(e, modulus)
    order_e = 0
    reduced_mod = modulus - 1
    while reduced_mod % e == 0:
        reduced_mod //= e
        order_e += 1
    # 找到使 (reduced_mod * k + 1) 可以被 e 整除的 k 值
    k = 1
    while (reduced_mod * k + 1) % e != 0:
        k += 1
    delta = (reduced_mod * k + 1) // e

    a = gmpy2.powmod(base, e ** (order_e - 1) * reduced_mod, modulus)
    b = gmpy2.powmod(x, e * delta - 1, modulus)
    c = gmpy2.powmod(base, reduced_mod, modulus)
    h = 1
    for i in range(1, order_e):
        d = gmpy2.powmod(b, e ** (order_e - 1 - i), modulus)
        j = 0 if d == 1 else (-gmpy2.log(d, a) % e)
        b = (b * gmpy2.powmod(c, e ** j, modulus)) % modulus
        h = (h * gmpy2.powmod(c, j, modulus)) % modulus
        c = gmpy2.powmod(c, e, modulus)
    result = gmpy2.powmod(x, delta, modulus) * h % modulus
    return result


def find_all_roots(e, modulus):
    """找到模 modulus 下的所有 e 次根。"""
    roots = set()
    while len(roots) < e:
        roots.add(gmpy2.powmod(random.randint(
            1, modulus - 1), (modulus - 1) // e, modulus))
    return roots


def combine_solutions(messages, modulus, roots, residual, e):
    """结合来自不同根的信息解决方案。"""
    solutions = []
    for root in roots:
        modified_message = (root * messages) % modulus
        solutions.append(modified_message)
    return solutions


def find_solution(message_parts_p, message_parts_q, e, p, q):
    """通过中国剩余定理合并消息部分。"""
    inverse_q_mod_p = gmpy2.invert(q, p)
    inverse_p_mod_q = gmpy2.invert(p, q)
    for part_p in tqdm(message_parts_p, desc="Combining parts"):
        for part_q in message_parts_q:
            combined_message = (part_p * inverse_q_mod_p *
                                q + part_q * inverse_p_mod_q * p) % (p * q)
            if check_signature(combined_message):
                return combined_message
    return None


def check_signature(message):
    """检查解码的消息是否包含有效的签名。"""
    try:
        decoded_message = long_to_bytes(message)
        if flag_info in decoded_message:
            print(f"Valid signature found: {decoded_message}")
            return True
    except Exception as error:
        print(f"Error decoding message: {error}")
    return False


start_time = time.time()
# 使用示例
flag_info = b'NSSCTF{'
# 确保初始化 c, p, q, n, e
n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
e = 1009

cp = c % p
cq = c % q

print("Start processing...")
message_parts_p = adaptive_multiplicative_method(cp, e, p)
message_parts_q = adaptive_multiplicative_method(cq, e, q)

roots_p = find_all_roots(e, p)
roots_q = find_all_roots(e, q)

combined_parts_p = combine_solutions(message_parts_p, p, roots_p, cp, e)
combined_parts_q = combine_solutions(message_parts_q, q, roots_q, cq, e)

find_solution(combined_parts_p, combined_parts_q, e, p, q)
print("Processing complete.")
final_time = time.time() - start_time
print(f"Time elapsed: {final_time:.2f} seconds.")

一点点魔法

回到一个月前画的饼

强网杯 2023 线上赛 Crypto -- not only rsa

$e$, $\phi(n)$ 不互素，后面这块专门出一期来讲(当时画的饼，现在实现了)，对于本题又发现 $n$ 使用 factordb / factor()，可分为: $n=p^5$ ，结合 RSA 加密逻辑所以我们有 $C = m ^ e \pmod{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.