RSA p-1光滑

Problem: [RSA2]P6

[[toc]]

思路

观察题目:发现定义函数getMyPrime,作用为不断从前10000个素数中随机选择，再与p=1相乘，再对p+1检查，是否满足为256位的素数。q同理。

这就发现p是由多个小素数相乘后加一得到
即p-1光滑。使用Pollard p-1法进行p的求解。
进而解出flag。

EXP

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

n = 53763529836257082401813045869248978487210852880716446938539970599235060144454914000042178896730979463959004404421520555831136502171902051936080825853063287829
e = 65537
c = 50368170865606429432907125510556310647510431461588875539696416879298699197677994843344925466156992948241894107250131926237473102312181031875514294014181272618

a = 2
k = 2

while True:
a = gp.powmod(a,k,n)
p = gp.gcd(a-1,n)
if p!=1 and p!=n:
break
k+=1

q = n // p
phi = (p-1) * (q-1)
d = gp.invert(e,phi)
m = gp.powmod(c,d,n)
print(long_to_bytes(m))

总结

RSA
Pollard p-1算法
p-1光滑