2023强网杯复现
not only RSA
题目描述:
这个模数好像很不安全,那你能解密出flag吗
这个模数好像很不安全,那你能解密出flag吗
今天在群里见到位师傅在复现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
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重写的:
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$下开根求解(可能是有限域为素数比较好开根?),也是跑了半天都没跑出结果来。。。
反正就是这次和师傅们唠嗑,发现了我对之前学习的一些东西掌握还是有所欠缺,也在和他们唠嗑中学到了许多新的姿势,所以我就把这事记录了下来,打算以后专门开个杂谈来放一些和师傅们唠嗑的一些有趣的东西。多和佬们唠嗑(
import os
import gmpy2
from Crypto.Util.number import *
import random
from secrets import flag
def pad(s,l):
return s + os.urandom(l - len(s))
def gen():
g = getPrime(8)
while True:
p = g * random.getrandbits(138) + 1
if isPrime(p):
break
while True:
q = g * random.getrandbits(138) + 1
if isPrime(q):
break
N = p ** 5 * q
phi = p ** 4 * (p - 1) * (q - 1)
d = random.getrandbits(256)
e = inverse(d, phi)
E = e * g
hint = gmpy2.gcd(E, phi)
return N, E, hint
flag = pad(flag,64)
m = bytes_to_long(flag)
n,e,hint = gen()
c = pow(m,e,n)
print(f'hint = {hint}')
print(f'n = {n}')
print(f'e = {e}')
print(f'c = {c}')
# hint = 251
# n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
# e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
# c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
根据gen函数,我们可以得知:
$n=p^5q,E=e*g,hint=gcd(E,\phi(n)),p=g*a1+1,q=g*a2+1$
又因为:
$$\phi(n)=p^4(p-1)(q-1)=p^4(g*a1)(g*a2)$$
所以g一定是E和$\phi(n)$的公因子,所以g|hint
但我们发现hint是个质数,所以我们可以得知g=hint=251
由于n是多素数组成的,且d仅有256位,所以d是一个小根,因此可以考虑用copper来求解d
$$ed\equiv 1\ (mod\ \phi(n))$$
得到d之后,根据$ed-1=kp^4(p-1)(q-1)$,$n=p^5q$,我们可以知道$gcd(ed-1,n)=p^4$(至少为$p^4$),所以我们依次可以求出p,q的值
exp部分:
from gmpy2 import *
E = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
g = 251
e = E // g
PR.<d> = PolynomialRing(Zmod(n))
f = e * d - 1
f = f.monic()
ans = f.small_roots(d = 2 ** 256, beta = 0.66)
print('d =', ans[0])
p4 = GCD(e * int(ans[0]) - 1, n)
p = iroot(p4, 4)[0]
print('p =', p)
q = n // (p * p4)
print('q =', q)
得到p,q之后,因为得到c的式子为:
$$c\equiv m^{E}$$
因为E和n不互质,我们无法直接求E逆元,但我们知道e的逆元d,可得到:
$$c^d\equiv m^g\ (mod\ n)$$
因为$n=p^5q$,我们可以想到上式可以拆为:
$$\left\{\begin{array}{rcl}c^d\equiv m^g\ (mod\ p)\\c^d\equiv m^g\ (mod\ q)\\\end{array} \right. $$
然后用AMM算法,我们可以将上述式子求出:
$$\left\{\begin{array}{rcl}m_p\equiv m^g\ (mod\ p)\\m_q\equiv m^g\ (mod\ q)\\\end{array} \right. $$
但是$n=p^5q$,flag被填充到了512位,若是直接用中国剩余定理去求$mod\ pq$下的根是不够的
这里我们可以用Hensel lifting将$mod\ p$下的解提升至$mod\ p^5$下的解
Hensel lifting引理 设$k\geq 2$是正整数,p为素数, $f(x)\equiv 0\ (mod\ p^{k-1})$
如果$f'(x)\not\equiv 0\ (mod\ p)$,那么存在在$mod\ p$意义下唯一的整数t,使得$f(x+tp^{k-1})\equiv 0\ (mod p^k)$由$t\equiv -f'(x)^{-1}({f(r) \over p^{k-1}})$给出
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\equiv 0\ (mod\ p^k)$,那么对任意正整数t,都有$f(x+tp^{k-1})\equiv 0\ (mod p^k)$
如果$f'(x)\equiv 0\ (mod\ p)$且$f(x)\not\equiv 0\ (mod\ p^k)$,那么对任意正整数t,都有$f(x+tp^{k-1})\not\equiv 0\ (mod p^k)$
详细介绍可以参考:Hensel lifting引理
此题正好有$f(m)=m^g-c^d\ (mod\ p)$,且我们已经用AMM算法求出m的所有可能情况,我们将之转至$\mod p^5$下,可以有$f(m)=m^g-c^d\ (mod\ p^5)$,在模$p^5$情况下得到的m已经足以满足512位的要求,所以此时我们只需要判别是否包含flag标识就可以得到明文m了
exp:
from Crypto.Util.number import *
from gmpy2 import *
import random
def onemod(e, q):
p = random.randint(1, q - 1)
while ((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 = powmod(p, e ** (t - 1) * s, N)
b = powmod(x, e * delta - 1, N)
c = powmod(p, s ,N)
h = 1
for i in range(1, t):
d = 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 = powmod(x, delta, N) * h
return result
def ALL_ROOT2(r, q):
list1 = set()
while(len(list1) < r):
p = 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
d = 39217838246811431279243531729119914044224429322696785472959081158748864949269
p = 69367143733862710652791985332025152581988181
q = 67842402383801764742069883032864699996366777
n = 108960799213330048807537253155955524262938083957673388027650083719597357215238547761557943499634403020900601643719960988288543702833581456488410418793239589934165142850195998163833962875355916819854378922306890883033496525502067124670576471251882548376530637034077
e = 3359917755894163258174451768521610910491402727660720673898848239095553816126131162471035843306464197912997253011899806560624938869918893182751614520610693643690087988363775343761651198776860913310798127832036941524620284804884136983215497742441302140070096928109039
c = 72201537621260682675988549650349973570539366370497258107694937619698999052787116039080427209958662949131892284799148484018421298241124372816425123784602508705232247879799611203283114123802597553853842227351228626180079209388772101105198454904371772564490263034162
g = 251
c1 = powmod(c, d, n)
cp = c1 % p
mp = AMM_rth(cp, g, p)
rt1 = ALL_ROOT2(g, p)
amp = ALL_Solution(mp, p, rt1, cp, g)
k = 5
for m in amp:
for i in range(1, k):
inv_fx = - invert(g * (m ** (g - 1)), p)
di = (m ** g - c1) // (p ** i)
t = inv_fx * di % p
m = m + (p ** i) * t % (p ** ( i + 1))
if b'flag' in long_to_bytes(m):
print(long_to_bytes(m))
在一般情况的RSA中,求出$\phi(N)$就已经接近解出明文了。这个时候我们往往只需要通过$ed\equiv1(mod \phi(N))$即可求出私钥d,从而求出明文。但是要直接求逆元d,需要满足$gcd(e,\phi(N))=1$,也就是e和$\phi(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)互质,可以拆解成
$$\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算法解得即可
开始还是一样的操作,拆解为
$$\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算法
先从原算法开始,
原算法中只是涉及了开平方根的方法,此时的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$则有
$$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即可
回到原式
$$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算法基础上,有人将开平方根的方法拓展到了开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$时,直接有
$$r^{e \delta -1} \equiv 1\ (mod\ p)$$
两边同时乘上r,再开e次方
$$r^{\delta} \equiv \sqrt[e]{r} \equiv x (mod p)$$
此时我们可以和$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$也为一组解)
我们解出了两方程的多组解
$$\left\{\begin{array}{rcl}m^{e}\equiv c&(mod\ p)\\m^{e}\equiv c&(mod\ q)\\\end{array} \right. $$
将1式的解和2式的解两两做一次CRT,就有一组可以得到正确的flag
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.