• 对于基础的RSA加密，我们只需要了解加密和解密过程，而不需要了解RSA加密这个理论是如何推导出来的（当然如果有数论基础的话可以这么干）。
  • 先对RSA加密过程进行简单的介绍，基础题型基本上就是想办法求p或q，从而把n分解出来，这样解密就可以一葫芦画瓢了。

rsa加密原理

  • 明文为m，密文为c
  1. 找两个质数p、q
  2. 计算n=p*q
  3. 计算n的欧拉函数φ（n）=（p-1）*（q-1）
  4. 公钥e，要求1＜e＜φ（n），且e为整数，还需要e、φ（n）互质
  5. 确定私钥d，d要满足e*d除以φ（n）余数为1
  • 加密
  • 解密

解密rsa关键

  • 公开传播的是：n、e、c

  • 解密要用到：n、d、c

  • 所以rsa解密的关键就是要得到私钥d

  • 要得到d，需要通过e*d除以φ（n）余数为1
  • 在求d之前就需要求φ（n）
  • 而φ（n）=（p-1）*（q-1）
  • 所以解密rsa的关键需要求p、q

  • n = p*q，可以通过分解质因素来对p、q进行爆破（当p、q比较小或者p、q比较接近的时候是可以分解的）

  • 了解RSA加密和解密的过程后，接下来就对CTF的RSA基础题（差不多已经成为模版题了）进行归纳

常用结论

  • 以下结论是在做题中比较经常用到的关于数论的一些结论。

RSA简单题型

RSA直接解密

RSA可分解n

RSA泄露p、q关系式

RSA低指数加密

RSA共享素数

RSA求phi(n)

RSA中等题型

RSA与同余

RSA中e与phi(n)不互素

RSA最小公因数和最大公倍数