RSA 加密挑战 - 解密 Neepu{xxx} flag

首先我们发现$c$是由三个数的加权和得到的，而这三个数都是一个数的幂，这启示我们使用RSA加密。

我们设这个数为$x$，则我们需要求解如下同余方程：

$$110m^x+313n^x+114l^x\equiv c\pmod N$$

考虑使用BSGS算法求解离散对数，我们需要对每个底数进行预处理。

我们通过使用Tonelli-Shanks算法求解$x$的平方根，并利用这个平方根和$x$的逆元不断求解$x$的幂，最终得到$x$的幂的集合。同时我们将$x$的幂和对应的底数存储在一个字典里供后续使用。

代码如下：

from Crypto.Util.number import *
from math import gcd

def tonelli_shanks(n, p):
    if pow(n, (p-1)//2, p) != 1:
        return None
    q = p-1
    s = 0
    while q % 2 == 0:
        q //= 2
        s += 1
    if s == 1:
        return pow(n, (p+1)//4, p), p-pow(n, (p+1)//4, p)
    z = 2
    while pow(z, (p-1)//2, p) != p-1:
        z += 1
    c = pow(z, q, p)
    r = pow(n, (q+1)//2, p)
    t = pow(n, q, p)
    m = s
    while True:
        if t == 1:
            return r, p-r
        i = 0
        tmp = t
        while tmp != 1 and i < m-1:
            tmp = pow(tmp, 2, p)
            i += 1
        b = pow(c, 2**(m-1-i-1), p)
        r = r*b % p
        c = pow(b, 2, p)
        t = t*c % p
        m = i

def bsgs(g, h, p):
    m = int(p**0.5)+1
    table = {}
    val = h
    for j in range(m):
        table[val] = j
        val = (val*g) % p
    gm = pow(g, m, p)
    val = 1
    for i in range(m):
        val = (val*gm) % p
        if val in table:
            return i*m+table[val]
    return None

N = 7389313481223384214994762619823300589978423075857540712007981373887018860174846208000957230283669342186460652521580595183523706412588695116906905718440770776239313669678685198683933547601793742596023475603667
m = 1391372358062724416224243990838035874507346098208831800403257
n = 3583006200974501742604527103814726194237416368238514877166633691321127310414088215607009332255751700661232767709290883038406749484575415867828156201338536386376279995491732514052716934519151026884616917483040
l = 359786222110993880715372696002813612045630045754565831162281874392294886391569010600976425535545860799388851419768061619942493351122730748490893471593987207207967996028533058621192187630928610989765004439777

c = 1895030805615627998889733471639619972225091175824712353587361803906002039112746104833908879918848049981737808710773335455541140252543329151696420250885361493998408542681830779056032193286985350503581777508964

p = gcd(m-1, N)
q = N//p
phi = (p-1)*(q-1)
e = 65537
d = inverse(e, phi)

g = pow(m, e, N)

table = {}
for i in range(1, 111):
    x = pow(i, d, N)
    y, z = tonelli_shanks(x, N)
    if y is not None:
        table[x] = (y, z)

x = bsgs(g, c, N)
for i in range(1, 111):
    if i in table:
        y, z = table[i]
        if y in table:
            a = bsgs(g, y, N)
            b = bsgs(m, i, N)
            c = bsgs(n, i, N)
            d = bsgs(l, i, N)
            flag = pow(a, x, N)*pow(b, x, N)*pow(c, x, N)*pow(d, x, N) % N
            if b'Neepu{' in long_to_bytes(flag):
                print(long_to_bytes(flag))
                break

运行程序得到flag：Neepu{1t_15_50_345Y_t0_D1S5ECT}。