RSA加密解密原理

引言：         CTF密码学类题目中，RSA加密可谓是很重要且常见的加密类型，今天就总结下 RSA加密的原理及解密方法。

RSA加密算法是一种 非对称加密 算法，RSA算法相比别的算法思路非常清晰，但是想要破解的难度非常大。

RSA算法基于一个非常简单的数论事实：两个素数相乘得到一个大数很容易，但是由一个大数分解为两个素数相乘却非常难。

非对称加密算法实现机密信息交换的基本过程：

图解：

了解了非对称加密算法的原理，我们再来说说 RSA 加密算法的基本流程。

如图：

先来了解一下什么是 互质数：

随机找两个质数 p 和 q ，p 与 q 越大，越安全。

假设 p = 65 ，q = 71。计算他们的乘积 n = p * q = 4615 ，转化为二进制为 1001000000111，即该加密算法即为 13 位。位数越长，算法则越难被破解。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。

φ(n) 表示：在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。

例：

在 1 到 8 之中，与 8 形成互质关系的是1、3、5、7，所以 φ(n) = 4。

计算公式（即欧拉函数）为：

前提：P 与 Q 均为质数

设：

P = 65 ，Q = 71

即有4480 个数与 n（4615）互质。