RSA加密原理及推导

一、概述

RSA算法是一种广泛使用的非对称加密算法，它的名称来源于其创始人Ron Rivest、Adi Shamir和Leonard Adleman的首字母缩写。所谓非对称，即该算法加密和解密使用不同的密钥，加密密钥用来加密、解密密钥用来解密。加密密钥可以公开，解密密钥需要保密。
基于大数分解的困难性，RSA加密算法在保护数据隐私和完整性方面具有很高的可靠性。

二、原理

对于明文M，加密过程得到密文C，可以用一个公式表达：C≡Me mod n
对于密文C，解密过程得到明文M，可以用一个公式表达：M≡Cd mod n
通俗点描述就是：获得密文是明文的e次方再取模n，获得明文是密文的d次方再取模n。

2.1 核心流程

1.生成一组密钥：一个密钥用来加密，一个密钥用来解密。用于解密的密钥只要保存好，即便公钥被知道了，也很难破解。
密钥的生成步骤：
(1)选择两个大质数 p 和 q，计算模数 n=p×q。
(2)计算欧拉函数：ϕ(n)=(p−1)(q−1)。
(3)选择公钥指数 e，需满足 gcd⁡(e,ϕ(n))=1
(4)计算私钥指数 d，使得 ed ≡1 mod ϕ(n)。即存在整数 k，使得：ed=1+kϕ(n)
(5)得到公钥(e,n)，私钥(d,n)
2.用公钥加密明文，得到密文。
3.用私钥解开密文，恢复明文。

2.2 数学原理

(1)质数和互质
一个大于1的自然数，如果只能被1和这个数字本身整除，我们称这个数为质数。
如果两个整数的最大公约数是 1，则称它们为互质。记为(m,n)=1;
(2).欧拉函数
欧拉函数φ(n)表示，那些与n互素并且小于n的数字的总数。例如小于8的数中，与8互质的有1、3、5、7，一共4个，那么φ(8)=4。
欧拉函数中有2点重要性质：
● 当n为质数时，φ(n)=n-1
● 如果整数m、n互质，则 φ(mn)=φ(m)φ(n)=(m-1)(n-1)
(3).模反运算
模运算，又称取模、求余数。用mod表示，在程序里通常表示为%。例如 17 mod 5 = 17 % 5 = 2。
如果a、b的乘积，对n取模的余数是1，即 (a * b) % n = 1，则b是整数a对同余数n的模反元素。譬如，在同余数为n=5时，整数a=3的模反元素是b=2，因为(32)%5=1
(4).欧几里得算法
对于不为0的非负整数m，n，gcd(m,n)表示m，n的最大公约数，则必然存在整数对 x，y使得 mx + ny = gcd(m,n)成立。
扩展欧几里得算法，当m，n互质，则必然存在mx + ny = 1，这里“+”号也可以写成“-”号，理解为mx比n的y倍还要多1.因此，m，n互质，则 mx = 1 (mod n)
(5).欧拉定理
若两个正整数M和n互质，则Mφ(n) ≡ 1 mod n，即M的φ(n)次方，对n取模得到余数是1.
费马小定理：由于φ(n)=n-1，所以M(n-1) = 1 mod n

2.3 推导过程

加密与解密表达式
加密过程：C≡Me mod n，其中 C=Me−xn（x 为整数）。
解密过程：M≡Cd mod n，即 M≡(Me−xn)d mod n
展开左侧的幂运算
根据二项式定理展开：(Me−xn)d=Med−(d/1)Me(d−1)(xn)+(d/2)Me(d−2)(xn)2−⋯+(−xn)d
由于 n是模数，任何含 n 的项在模 n 下均为 0。
因此(Me−xn)d mod n=Med mod n
利用RSA的密钥关系
RSA密钥满足 ed≡1modϕ(n)，
根据欧拉定理，若 M 与 n 互质，Mφ(n) ≡ 1 mod n，因此可得
Med≡M1+kϕ(n)≡M⋅(Mϕ(n))k≡M⋅1k≡M mod n
若M 与 n 不互质，需要单独分析：
● 情况1：假设 M=ap（其中 a 与 p 互质），则：
M≡0 mod p => Med≡0 mod p => Med≡M mod p，
根据费马小定理，Mq−1≡1 mod q => Mk(q−1)≡1 mod q，由于 ed≡1 mod ϕ(n)，可推导出 Med≡M mod q
● 情况2：同理可证 Med≡M mod q
根据中国剩余定理（CRT），若 Med ≡ M mod p 且 Med≡M mod q，则：
Med≡M mod n
结论：
以上，解密得证正确性。ed≡1 mod ϕ(n)是其必要条件。
而安全性方面，攻击者若想破解私钥 d，需要已知 ϕ(n)，而计算 ϕ(n)必须分解 n=pq，当 p 和 q 为大质数时，分解 nn 在计算上不可行，从而保证RSA的安全性。