getprime(512)CTF中的RSA基本方法

CTF中的RSA前言 getprime(512)

本文对RSA中常用的模逆运算、欧几里得、拓展欧几里得、中国剩余定理等算法不展开作详细介绍，仅对遇到的CTF题的攻击方式，以及使用到的这些算法的python实现进行介绍。目的是让大家能轻松解决RSA在CTF中的套路题目。

RSA介绍 getprime(512)

首先，我这边就不放冗长的百度百科的东西了，我概括一下我自己对RSA的看法。
RSA是一种算法，并且广泛应用于现代，用于保密通信。
RSA算法涉及三个参数,n,e,d，其中分为私钥和公钥，私钥是n,d，公钥是n,e
n是两个素数的乘积，一般这两个素数在RSA中用字母p,q表示
e是一个素数
d是e模 varphi(n) 的逆元，CTF的角度看就是，d是由e,p,q可以求解出的
一般CTF就是把我们想要获得的flag作为明文，RSA中表示为m。然后通过RSA加密，得到密文，RSA中表示为C。
加密过程
c=m^e mod n

c=pow(m,e,n)

• 1

解密过程
m=c^d mod n

m=pow(c,d,n)

• 1

求解私钥d

d = gmpy2.invert(e, (p-1)*(q-1))

• 1

一般来说&#x