导言

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

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

假设$gcd(e,\phi(N))=t$，令$e'=e/t$
则${m}^{e}\equiv{m^{t}}^{e'}\equiv c(modN)$
又$d=invert(e',\phi(N))$
所以${m}^{t}\equiv {c}^{d}(modN)$
此时$m^t$可求且$m^t<N$所以可据此直接开方求得m

import gmpy2

phi = (p - 1) * (q - 1)
t = gmpy2.gcd(phi, e)
d = gmpy2.invert(e // t, phi)
M = pow(c, d, n)
m = gmpy2.iroot(M, e)[0]
print(long_to_byte(m))

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

这种情况下，e和（p-1）和（q-1）互质，可以拆解成
$$\left\{\begin{array}{rcl}m^{e}\equiv c&(mod\ p)\\m^{e}\equiv c&(mod\ q)\\\end{array} \right. $$
再有$$\left\{\begin{array}{rcl}ed_1\equiv1(mod\ \phi(p)\ )\\ed_2\equiv1(mod\ \phi(q)\ )\\\end{array}\right. $$
推得$$\left\{\begin{array}{rcl}m\equiv c^{d_1}&(mod\ p)\\m\equiv c^{d_2}&(mod\ q)\\\end{array} \right. $$
最后根据CRT算法解得即可

复杂的情况（(p-1)或(q-1)是e的倍数）

开始还是一样的操作，拆解为
$$\left\{\begin{array}{rcl}m^{e}\equiv c&(mod\ p)\\m^{e}\equiv c&(mod\ q)\\\end{array} \right. $$
但此时$p-1$或$q-1$是$e$的倍数，是倍数的话，就无法直接通过求逆元的办法求出$d$，这个时候就需要一种新的算法——AMM算法

AMM算法

先从原算法开始，
原算法中只是涉及了开平方根的方法，此时的e=2，p为奇素数
对于$x^{2}\equiv r\ (mod\ p)$，则说明r是p的一个二次剩余，令$p-1=2^{s}t$，则有
$$r^{(p-1) \over 2}\equiv r^{2^{s-1}t}\equiv 1\ (mod\ p)$$

s=1

如果此时的$s=1$则有
$$r^t\equiv1(mod\ p)$$
两边同时乘上r，再开方即可得到
$$r^{t+1 \over 2}\equiv \pm\sqrt{r} \equiv\pm x\ (mod\ p)$$
此时套回我们的原式，得到
$$\pm m\equiv c^{t+1 \over 2}\ (mod\ p)$$
此时我们只需要根据p算出t即可

s>1

回到原式
$$r^{2^{s-1}t}\equiv 1\ (mod\ p)$$
由于此时的$$s>1$$，直接开根我们可以得到两个式子

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

$$r^{2^{s-2}t}\equiv -1\ (mod\ p)$$
因为存在两种不同的开方结果，所以我们需要同时乘上一个二次非剩余项$n^{2^{s-1}tk}$，这样便消除了-1根的影响(此式$n$为$p$的一个非二次剩余，由$n^{(p-1) \over 2}\equiv -1\ (mod\ p)$到同上变换为$n^{2^{s-1}t} \equiv-1\ (mod\ p)$ ，$k$用来控制是否相乘，$k=0$时，此二次非剩余式则为$n^0=1$，不做改变；$k=1$时，此二次剩余式为$n^{2^{s-1}t} \equiv-1\ (mod\ p)$，为$-1$)
得到下式
$$r^{2^{s-2}t}n^{2^{s-1}tk}\equiv 1 \ (mod\ p)$$
这样我们便可以继续开方，以此往复，直到迭代成$$s=1$$的情况，即
$$r^{t}{n}^{t*(2k_1+2^{2}k_2+...+2^{s-1}k_{s-1})}\equiv 1 (mod\ 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 (mod p)$$
即
$$c^{t+1 \over 2}n^{t*(k_1+2k_2+...+2^{s-2}k_{s-1})}\equiv\pm m (mod p)$$
（这里的$k_1,k_2$等，只能够在一步步运算中得出）

AMM算法ex

在AMM算法基础上，有人将开平方根的方法拓展到了开n次方根
对于$x^{e}\equiv r\ (mod\ p)$，则说明r是p的一个$e-$次剩余，令$p-1=e^{s}t$，则有(很明显，我们前提条件是能整除p- 1）
$$r^{(p-1) \over e}\equiv r^{e^{s-1}t}\equiv 1\ (mod\ p)$$
此时，我们可以找到一个数$\delta$，满足$t|(e\delta -1)$，所以上式可以写为
$$r^{e^{s-1}(e\delta -1)}\equiv 1\ (mod p)$$

s=1

同样的，这里的$s=1$时，直接有
$$r^{e \delta -1} \equiv 1\ (mod\ p)$$
两边同时乘上r，再开e次方
$$r^{\delta} \equiv \sqrt[e]{r} \equiv x (mod p)$$

s>1

此时我们可以和$e=2$的情况类似，构造一个$e-$次非剩余的集合，
$$K_i=\rho^{{i}*{p-1\over{e}}}=\rho^{i*e^{s-1}t}\ (i的范围为[0,e-1])$$
$${K_{i}}^{e}=\rho^{i*e^{s}t}=\rho^{i*(p-1)}$$
根据欧拉定理$\rho^{p-1}\equiv1\ (mod\ p)$得
$${k_{i}}^{e}\equiv 1 (mod p)$$
那么$K_i*K_{e-i}=\rho^{e*{p-1 \over e}}=\rho^{p-1}$
根据欧拉定理也得
$$K_i*K_{e-i} \equiv 1\ (mod\ p)$$
即$K_i$与$K_{e-i}$互为逆元
回到原式
$$r^{e^{s-1}(e\delta -1)}\equiv 1\ (mod p)$$
两边同时开e次方得到一个集合$K$中的数设为$K_{e-j}$(根据群论性质得）
$$r^{e^{s-2}(e\delta -1)}\equiv K_{e-j}\ (mod p)$$
后续也和$e=2$的情况类似，只需要将上式不断乘上$K_j$，开e次方即可
$$r^{e^{s-2}(e\delta -1)}K_j\equiv K_{e-j}K_j \equiv 1\ (mod p)$$
即
$$r^{e^{s-2}(e\delta -1)}\rho^{j*e^{s-1}t}\equiv 1\ (mod p)$$
以此往复，最终可以迭代成
$$r^{(e\delta -1)}\rho^{t*(ej_1+e^{2}j_2+...+e^{s-1}j_{s-1})}\equiv 1\ (mod p)$$
再两边同时乘$r$，开e次方
$$r^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv x\ (mod p)$$
相当于
$$c^{\delta}\rho^{t*(j_1+ej_2+...+e^{s-2}j_{s-1})}\equiv m\ (mod p)$$
此时我们便得到了其中一个根
剩余的解可以通过不断乘上集合$K$即可（${K_i}^{e} \equiv 1\ (mod\ p)$，所以${(mK_i)}^{e}\equiv c\ (mod\ p)$，所以$mK_i$也为一组解）

AMM之后的操作

我们解出了两方程的多组解
$$\left\{\begin{array}{rcl}m^{e}\equiv c&(mod\ p)\\m^{e}\equiv c&(mod\ q)\\\end{array} \right. $$
将1式的解和2式的解两两做一次CRT，就有一组可以得到正确的flag

exp:

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

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 b'NSSCTF' in a:
            print(a)
            return True
        else:
            return False
    except:
        return False

n = 38041020633815871156456469733983765765506895617311762629687651104582466286930269704125415948922860928755218376007606985275046819516740493733602776653724917044661666016759231716059415706703608364873041098478331738686843910748962386378250780017056206432910543374411668835255040201640020726710967482627384460424737495938659004753604600674521079949545966815918391090355556787926276553281009472950401599151788863393804355849499551329
c = 2252456587771662978440183865248648532442503596913181525329434089345680311102588580009450289493044848004270703980243056178363045412903946651952904162045861994915982599488021388197891419171012611795147125799759947942753772847866647801312816514803861011346523945623870123406891646751226481676463538137263366023714001998348605629756519894600802504515051642140147685496526829541501501664072723281466792594858474882239889529245732945
p = 5220649501756432310453173296020153841505609640978826669340282938895377093244978215488158231209243571089268416199675077647719021740691293187913372884975853901554910056350739745148711689601574920977808625399309470283   
q = 7286645200183879820325990521698389973072307061827784645416472106180161656047009812712987400850001340478084529480635891468153462119149259083604029658605921695587836792877281924620444742434168448594010024363257554563
e = 1009

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

END.

N1gh7ma12e的生活日志

RSA中e与phi_N不互质的情况

导言