题目如下
import math
import sympy
from Crypto.Util.number import *
e = 65537
def get_p():
x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
value_p = sympy.nextprime((math.factorial(y)) % x) # Hint：这里直接计算会溢出，请你仔细观察 x 和 y 的特征
return value_p
def get_q():
value = [getPrime(256)]
for i in range(1, 10):
value.append(sympy.nextprime(value[i - 1]))
print("value[-1] = ", value[-1])
# value[-1] = 80096058210213458444437404275177554701604739094679033012396452382975889905967
n = 1
for i in range(10):
n = n * value[i]
q = getPrime(512)
value_q = pow(q, e, n)
print("value_q = ", value_q)
# value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
return sympy.nextprime(q)
# this destroyes the rsa cryptosystem
p = get_p()
q = get_q()
m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, e, p * q)
print("c = ", c)
# c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478
分析得知，他是让我们求出q，p从而解RSA得到明文。
首先我们解q，因为p还是不会。通过调试，了解到sympy这个库可以获得某质数的下一个质数例如sympy.nextprime(value[i - 1])得到第一个素数下面的素数。查看python某一库下所有函数我们这里选用dir(sympy)找到此函数
尝试yafu分解的代码：.\yafu-x64.exe "factor(@)" -batchfile data.txt
大数分解的网站
学习如何插入公式
函数math.factorial(y)的意思是求阶乘，求y的阶乘
c ≡ m e ( m o d n ) c\equiv m^e\ {(mod \ n)} c≡me (mod n)
m = pow(c,e,n)
m
≡
c
d
(
m
o
d
n
)
m\equiv c^d\ {(mod \ n)}
m≡cd (mod n)
c = pow(m,d,n)对于超级幂取模后期可能会与gmpy2库的powmod（）函数有关
ϕ
(
n
)
=
(
p
−
1
)
∗
(
q
−
1
)
\phi(n)=(p-1)*(q-1)
ϕ(n)=(p−1)∗(q−1)
d
∗
e
≡
1
(
m
o
d
ϕ
(
n
)
)
d*e\equiv1\ (mod\ \phi(n))
d∗e≡1 (mod ϕ(n))
一般情况下求d。 d = libnum.invmod(e, (p - 1) * (q - 1))（这里是libnum库，gmpy2库也可以重点是**invmod（）**函数，这是求逆元的函数）
d
p
≡
d
(
m
o
d
(
p
−
1
)
)
dp\equiv d \ (mod \ (p-1))
dp≡d (mod (p−1))
d q ≡ d ( m o d ( q − 1 ) ) dq \equiv d\ (mod \ (q-1)) dq≡d (mod (q−1))
c ≡ m e ( m o d n ) c\equiv m^e\ {(mod \ n)} c≡me (mod n)
正常情况下m = pow(c,e,n)即可，如果遇到大数，就用m = gmpy2.powmod(c,e,m)这个快（gmpy2库）。
一般情况下这个是解不出来的，这是RSA加密的基础，知道p，q后即可解出。解体模板如下
import libnum
from Crypto.Util.number import long_to_bytes
c =
n =
#n = int("",16)
e =
#e = int("",16)
q =
p =
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n) # m 的十进制形式
string = long_to_bytes(m) # m明文
print(string) # 结果为 b‘ m ’ 的形式
求指数，离散对数攻击
from sympy.ntheory import discrete_log
n =
m =
c =
flag = discrete_log(n,c,m)
print(long_to_bytes(flag))
在RSA中一般n是公钥，一般都会给的，如果没给，我在总结上来。
这里对应求get_p,威尔逊定理。
(
p
−
1
)
!
≡
−
1
(
m
o
d
p
)
(p-1)!\equiv -1 \ (mod\ p)
(p−1)!≡−1 (mod p)
前提p为素数
这里已经检验过x，y均为素数，而且他们相互特别接近。已经成功推理过了。这里不再赘述。
实现代码
import libnum
def decrypt(A,B):#A>B
ans=1
temp=pow(-1,1,A)
for i in range(B+1,A):
ans=(ans*libnum.invmod(i,A))%A
return (ans*temp)%A
#decrypt(x,y) return的结果即为(math.factorial(y)) % x
这里对应求get_q,欧拉函数
a
ϕ
(
m
)
≡
1
(
m
o
d
m
)
a^{\phi(m)}\equiv 1 \ (mod \ m )
aϕ(m)≡1 (mod m)
ϕ ( m ) = { m − 1 , m 为素数 m ( 1 − 1 p 1 ) ( 1 − 1 p 2 ) ( 1 − 1 p 3 ) . . . m = p 1 a 1 p 2 a 2 p 3 a 3 . . . \phi(m)=\begin{cases} m-1, & {m为素数} \\ m(1- \frac{1}{p_1} )(1- \frac{1}{p_2})(1- \frac{1}{p_3})...& {m = p{_1}{^{a_1}}p{_2}{^{a_2}}p{_3}{^{a_3}}...} \end{cases} ϕ(m)={m−1,m(1−p11)(1−p21)(1−p31)...m为素数m=p1a1p2a2p3a3...
p都是素数，整理后可以是以下形式
ϕ
(
m
)
=
(
p
1
−
1
)
(
p
2
−
1
)
(
p
3
−
1
)
(
p
4
−
1
)
.
.
.
.
m
=
p
1
∗
p
2
∗
p
3
.
.
.
.
\phi(m)=(p_1-1)(p_2-1)(p_3-1)(p_4-1).... \\m=p_1*p_2*p_3....
ϕ(m)=(p1−1)(p2−1)(p3−1)(p4−1)....m=p1∗p2∗p3....
一般就是q，p（即2个），多素数分解情况下可以为以上表示。
即求解
a
x
≡
b
(
m
o
d
m
)
ax\equiv b\ (mod\ m)
ax≡b (mod m)
转换后，给出公式
x
≡
b
a
ϕ
(
m
)
−
1
(
m
o
d
m
)
x\equiv ba^{\phi(m)-1}(mod \ m)
x≡baϕ(m)−1(mod m)
import libnum
import math
import sympy
from Crypto.Util.number import *
e = 65537
def decrypt(A,B):#A>B
ans=1
temp=pow(-1,1,A)
for i in range(B+1,A):
ans=(ans*libnum.invmod(i,A))%A
return (ans*temp)%A
value=[80096058210213458444437404275177554701604739094679033012396452382975889905967]
for i in range(1, 10):
value.append(sympy.prevprime(value[i - 1]))
n=1
for i in range(10):
n = n * value[i]
fn=1
for i in range(10):
fn = fn * (value[i]-1)
value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
d = libnum.invmod(e, fn)
q = pow(value_q, d, n)
q = sympy.nextprime(q)
x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
p = decrypt(x,y)
p = sympy.nextprime(p)
n = p * q
c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478
d = libnum.invmod(e, (p - 1) * (q - 1))
m = pow(c, d, n) # m 的十进制形式
string = long_to_bytes(m) # m明文
print(string) # 结果为 b‘ m ’ 的形式
因篇幅问题不能全部显示，请点此查看更多更全内容