RSA-n由多因子高次幂得到

源码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from Crypto.Util.number import *

flag = b'NSSCTF{******}' + b'1'*100

p = getPrime(256)
q = getPrime(256)
n = (p**3) * q
e = 65537
phi = (p-1)*(q-1)

m = bytes_to_long(flag)

c = pow(m, e, n)

print(f'p = {p}')
print(f'q = {q}')
print(f'e = {e}')
print(f'c = {c}')

'''
p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041
'''

n=p3∗qn = p^3*q

对于这种多因子高次幂的情况,

n=px∗qy∗rzn = p^x * q^y * r^z

有固定公式：

ϕ=px−1(p−1)qy−1(q−1)rz−1(r−1)\phi = p^{x-1} (p-1) q^{y-1} (q-1) r^{z-1} (r-1)

简要概括， 分别降一次幂再乘以减1
此时n是题中所给的形式，不是原始的p*q

exp:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
from Crypto.Util.number import *


p = 80505091208742938705306670241621545375764148093711243653439069254008824979403
q = 67599990875658931406915486208971556223245451500927259766683936131876689508521
e = 65537
c = 7958690969908064264211283192959937430539613460471121984649054121171267262097603091410178042319139582772142226087020110084551158367679146616732446561228522673699836019156243452069036383047309578614662564794584927846163157472211089368697387945469398750955336949678910159585015004994620777231073804301249774041

n = (p**3) * q
phi = pow(p, 2) * (p-1) * (q-1)
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

# NSSCTF{more_exp}1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111