前言

今天在群里见到位师傅在复现signin这道题，问$e$和$\phi(n)$不互质的情况该怎么解决，当时并没发现事情的严重性，以为只是普普通通的amm开根即可。直到师傅和我说那个${e \over t}(此处t=gcd(e,\phi(n)))$和\phi(n)不互素，我当时直接cpu被干烧了

直到另外一个师傅和我说：

甚至还贴心的给我举了个例子

好好好，我承认是我?宕机了
师傅和我说这样只需要多进行几次amm就可以了。我心想：确实，应该就是个类似高次rabin的东西吧（此时我还没看到题面）
于是我就高高兴兴的去泡了个澡，泡着的时候想着可以回去把这个题记录一下
可是，当我回去拿到题目，求出p和q后，发现这个e不太对劲，这个$e=3*2^{16}$，太大了，搓了半天死活脚本没跑出来
最后还是在题解和师傅们的帮助下，才把题目复现出来了（我承认我是菜狗/(ㄒoㄒ)/~~）
接下来就是题目的讲解：

题目源码

from Crypto.Util.number import isPrime,bytes_to_long, sieve_base
from random import choice
from secret import flag
 
m=bytes_to_long(flag)
def uniPrime(bits):
    while True:
        n = 2
        while n.bit_length() < bits:
            n *= choice(sieve_base)
        if isPrime(n + 1):
            return n + 1
 
 
p=uniPrime(512)
q=uniPrime(512)
n=p*q
e= 196608
c=pow(m,e,n)
 
print("n=",n)
print("c=",c)
 
'''
n= 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
c= 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246
'''

思考&题解

很明显，p-1和q-1都是光滑的，我们直接通过p-1光滑攻击即可求出p和q
求出之后，我们对$\phi(n)$和$e$求他的最大公约数，发现为2，用$\phi(n)$和$e/2$，求逆元发现仍然不互质。。。
于是我对e进行了质因数分解，发现$e=2^{16}*3=65536*3$
这样我们思路就很清晰了，只需要先求3在$mod\ \phi(n)$下的逆元d，就可以得到$m^{65536}\equiv c^d\ (mod\ n)$中$m^{65536}\ (mod\ n)$这个数，此时我们只需要做多次rabin即可算出m

exp：

from Crypto.Util.number import *
from gmpy2 import *

n= 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
c= 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246
e= 196608

def smooth_attack(n):
    a = 2
    m = 2
    while True:
        a = gmpy2.powmod(a, m, n)
        p = gcd(a-1, n)
        if p != 1 and p != n:
            return p
        m += 1

p = smooth_attack(n)
q = n // p
phi = (p - 1) * (q - 1)

# K = Zmod(n)
d = invert(e // 65536, phi)
m = int(powmod(c, d, n))
# print(m)

# func = K(m).nth_root(2, all=True)
# print(func)

def rabin_attack(c, n, p, q):
    c1 = powmod(c, (p + 1) // 4, p)
    c2 = powmod(c, (q + 1) // 4, q)
    cp1 = p - c1
    cp2 = q - c2

    t1 = invert(p, q)
    t2 = invert(q, p)

    m1 = (t1 * p * c2 + t2 * q * c1) % n
    m2 = (t1 * p * cp2 + t2 * q * c1) % n
    m3 = (t1 * p * c2 + t2 * q * cp1) % n
    m4 = (t1 * p * cp2 + t2 * q * cp1) % n

    return m1, m2, m3, m4

def exd_solve(c_list, t):
    for i in range(t):
        temp = []
        for c in c_list:
            m = []
            m = rabin_attack(c, n, p, q)
            for k in m:
                if k not in temp:
                    temp.append(k)
        c_list = temp
    for m in c_list:
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)
            
m_list = [m]
s = e // 3
t = 1
while s // 2 != 0:
    s = s // 2
    t += 1

exd_solve(m_list, t - 1)

我为什么没跑出来？

我最开始对多次rabin的处理，每一轮使用递归来实现的，这样大大的增加了时间复杂度。但在改回循环实现后，仍然无法求得。
再看了题解之后，发现他多了这么一部分:

for k in m:
    if k not in temp:
          temp.append(k)

这一部分相当于是对每次rabin求出的4个解做了次筛重，我们只需要将没出现过的解加进待求数组即可。
在进行了这个优化后就成功能跑出m

后续

之后那个给我举例子的师傅和我说，他是用sage中的nth_root函数把开65536次方的根直接全部求出来的（直接给了我一点小小的震撼--?好痒O.o)，于是我也用nth_root函数做了一遍，终于不负众望，还是没跑出来。。。
然后我就去观摩了下那位师傅的写法，下面是我根据他的exp重写的：

exp:

from Crypto.Util.number import *
from sympy.ntheory.modular import crt
from gmpy2 import *

n= 3326716005321175474866311915397401254111950808705576293932345690533263108414883877530294339294274914837424580618375346509555627578734883357652996005817766370804842161603027636393776079113035745495508839749006773483720698066943577445977551268093247748313691392265332970992500440422951173889419377779135952537088733
c= 2709336316075650177079376244796188132561250459751152184677022745551914544884517324887652368450635995644019212878543745475885906864265559139379903049221765159852922264140740839538366147411533242116915892792672736321879694956051586399594206293685750573633107354109784921229088063124404073840557026747056910514218246
e= 196608

def smooth_attack(n):
    a = 2
    m = 2
    while True:
        a = gmpy2.powmod(a, m, n)
        p = gcd(a-1, n)
        if p != 1 and p != n:
            return p
        m += 1

p = smooth_attack(n)
q = n // p
phi = (p - 1) * (q - 1)
d = invert(e // 65536, phi)
m = int(powmod(c, d, n))

K = Zmod(p)
funcp = K(m % p).nth_root(65536, all=True)

K = Zmod(q)
funcq = K(m % q).nth_root(65536, all=True)

for i in funcp:
    for j in funcq:
        N = [p, q]
        c = [int(i), int(j)]
        m = crt(N, c)[0]
        flag = long_to_bytes(m)
        if b'flag' in flag:
            print(flag)

他是先把n拆为p和q后，分别用nth_root开根求解，最后再每组用CRT去凑回n，看看符不符合题目需求。（好好好，这么玩是吧）

我的问题

我并没有将n分解成p和q，分别开根，而是直接用在$mod\ n$下开根求解（可能是有限域为素数比较好开根？），也是跑了半天都没跑出结果来。。。

总结

反正就是这次和师傅们唠嗑，发现了我对之前学习的一些东西掌握还是有所欠缺，也在和他们唠嗑中学到了许多新的姿势，所以我就把这事记录了下来，打算以后专门开个杂谈来放一些和师傅们唠嗑的一些有趣的东西。多和佬们唠嗑（