RSA公钥算法详解

RSA 加密算法详解 RSA 算法是公钥加密算法的代表之一，由 Ron Rivest、Adi Shamir 和 Leonard Adleman 于 1977 年提出。该算法基于大数_factorization 问题，安全性高、应用广泛。 一、 RSA 算法的历史背景 在 1970 年左右，科学家们开始思考公钥加密系统的可能性。经过多年的研究，终于在 1977 年时，来自 MIT 的 Ron Rivest、Adi Shamir 和 Leonard Adleman 三个人合写了一篇论文，给出了至今仍然安全的公钥加密算法，即以三个人姓氏的首字母命名的 RSA 算法。 二、 RSA 算法的过程步骤 RSA 算法的过程步骤如下： 1. 找两个大质素 p 和 q 2. 设 n=p·q，算出 m=(p-1)(q-1) 3. 找出 e 和 d，使得 e·d mod m = 1（随便找出一个与 m 互质的数 e，求解方程 e·d mod m = 1） 4. 把 e，n 作为公钥，d，n 作为私钥 5. 设 X 为原始报文，Y 为密文则 Y=Xe mod n，X=Y dmod n 即某个人用公钥 e 和 n 加密后，只有拥有私钥 d 和 n 的另一个人才能进行解密。 三、 RSA 算法的数学依据 RSA 算法背后的数学依据已经存在 300 年以上，但是根据这么古老的定理创造 RSA 算法却是最近几十年的事。主要原因是随着计算机运算速度的提升以及网络的建立带来安全通讯的需求，因此开始了研究公钥算法的可行性，并终于在 1977 年时由 MIT 的三位教授发明了 RSA 公钥加密算法。 四、 RSA 算法的详解 下面我们将对 RSA 算法的步骤进行详细的解释： 1. 为什么 X=Y dmod n，而 Y=Xe mod n，也就是 X 的 e 次方除以 n 取余的值的 d 次方再除以 n 的取余又等于 X 了呢？ 因为 Xe 除以 n 的余数（Xe mod n）的 d 次方再模 n，相当于 Xe·dmod n，证明如下： (1) Y=Xe mod n 即是算 X 的 e 次方除以 n 的余， (2) 换成公式：Xe = nx + Y x 为 n 的倍数 (3) 则 Y = Xe – nx (4) Y dmod n = (Xe – nx)d mod n (5) (Xe – nx)d 是一个多项式，展开后除了第一项为 Xe·d 外，其余项都携带 n，因此其余项都能被 n 除尽，(Xe – nx)d mod n 可以简化为 Xe·dmod n 1.2 由 1.1 可知 Y dmod n = (Xe – nx)d mod n = Xe·dmod n，而为什么 Xe·dmod n = X 呢？ 1.2.1 如果某个整数 n 等于两个质数 p,q 的乘积，那么对于任意一个整数 a，写出 ai 依次除以 n 所得的余数序列，那么 p-1 和 q-1 的最小公倍数将成为该序列的一个周期，这是一个费马小定理的扩展。 1.2.2 m 就是(p-1)和（q-1）的乘积，因此该序列的周期是 m，a mod n 、a1+m mod n 、a1+2mmod n 和 a1+3m mod n 的余数都相等。 1.2.3 所以计算 e·d = 1 + m、e ·d = 1 + 2m 或 e ·d = 1 + 3m 等的任何一个值即能保证 amod n = ae·d mod n 1.2.4 计算 e·d = 1 + m 即计算 e·d mod m = 1，随便找一个与 m 互质的数 e，然后求方程e·d mod m =1。由于 e 与 m 互质，那么 e·d mod m = 1、e·d mod m = 2、e·d mod m =3 等都有解，并且在这个解的基础上加减 n 的倍数即为所有的解。 五、 RSA 算法的应用 RSA 算法广泛应用于网络安全、数据加密、数字签名等领域。该算法的安全性高、应用广泛，已经成为公钥加密算法的代表之一。 六、 结论 RSA 算法是一种基于大数_factorization 问题的公钥加密算法，安全性高、应用广泛。通过对 RSA 算法的详细解释，我们可以更好地理解该算法的原理和应用。