【题目】——This service provides you an encrypted flag. Can you decrypt it with just N & e?
【解题】远程运行服务器后得到N，e和cyphertext的值，以及RSA加密过程的python代码，如下：
def gen_key(k):"""Generates RSA key with k bits"""p,q = get_primes(k//2)N = p*qd = inverse(e, (p-1)*(q-1))return ((N,e), d)def encrypt(pubkey, m):N,e = pubkeyreturn pow(bytes_to_long(m.encode('utf-8')), e, N)def main(flag):pubkey, _privkey = gen_key(1024)encrypted = encrypt(pubkey, flag) return (pubkey[0], encrypted)if __name__ == "__main__":flag = open('flag.txt', 'r').read()flag = flag.strip()N, cypher = main(flag)print("N:", N)print("e:", e)print("cyphertext:", cypher)exit()
关于RSA的数学逻辑可以参考这篇文章，根据公式M=Cd mod n解密得到明文M（其中C是密文，e * d ≡ 1 mod Φ(n)，Φ(n)=(p-1)*(q-1)，p和q是两个质数）
现在已知C，e的值，得到p和q即可反推d的值，最终解密得到明文M，
而RSA算法保障密码不可破解的关节点就是“大数分解难题”，也就是将N分解成两个质数p和q，
所以破解的入手点就是p和q的值并非大质数，而是存在一定漏洞或规律，
因此我们多次运行上述代码，得到多组N和cyphertext数值对，
通过观察发现，所有的N值都是偶数，
因此我们选择一组数值对N和cyphertext，令p=2（当然q=2也可以），那么q=N/2，
Φ(n)=(p-1)*(q-1) 即可得，
d = inverse(e, Φ(n)) 即可得，
明文 M = pow(C, d, N) 即可得。
详细代码如下：
from Crypto.Util.number import inverse, long_to_bytes
# 给定参数（示例：第1组数值对）
C = 9109970059048183683019519086451323279844163956674438551666137208759174857870459426568972012648753854223216577134638714421248398487373332600794532623165627
N=15802304864428476390598424929570263603743509364707965536076049112745011278235752576010382135022029835275435449162451633173608468168435767399816829899840406
e = 65537q = 2
p = N // q # 计算 φ(N)
phi = (p - 1) * (q - 1)# 计算私钥 d
d = inverse(e, phi)# 解密
M = pow(C, d, N)# 转成字节 / 字符串
print("M (int) =", M)
print("M (bytes) =", long_to_bytes(M))
OVER