RSA简单实例

RSA是一种非对称加密算法，其安全性基于质因数分解的困难性。下面以p=3和q=5为例，详细解释RSA算法的产生过程以及加密解密过程：

一、RSA算法的产生过程

选择质数：

随机选择两个不相等的质数p和q。在这个例子中，p=3，q=5。

计算n和欧拉函数φ(n)：

计算n=p×q。在这个例子中，n=3×5=15。
计算欧拉函数φ(n)=(p-1)×(q-1)。在这个例子中，φ(n)=(3-1)×(5-1)=8。

选择公钥e：

选择一个整数e，满足1<e<φ(n)，且e与φ(n)互质。在这个例子中，可以选择e=3（也可以选择其他与8互质的数，如7）。

计算私钥d：

计算e关于φ(n)的模反元素d，即找到一个整数d，使得ed≡1(mod φ(n))。这可以通过扩展欧几里德算法来求解。
在这个例子中，需要找到一个整数d，使得3d≡1(mod 8)。通过计算，可以找到d=3（因为3×3-1=8，可以被8整除，且3小于φ(n)）。但需要注意的是，这里d的值并不唯一，例如d=11也满足条件，因为11×3-1=32，也可以被8整除。在实际应用中，通常会选择一个较小的d值。
因此，公钥为(e, n)=(3, 15)，私钥为(d, n)=(3, 15)或(11, 15)等满足条件的组合。但为了方便说明，这里我们固定私钥为(3, 15)（注：在真实场景中，应确保私钥的唯一性和安全性）。

二、RSA算法的加密解密过程

加密过程：

假设要加密的明文为m，且m必须小于n。在这个例子中，我们可以选择m=2（也可以选择其他小于15的整数）。
使用公钥(e, n)对明文m进行加密，计算密文c=m^e mod n。
在这个例子中，c=2^3 mod 15=8。也就是2的3次方模15，密文为8

解密过程：

使用私钥(d, n)对密文c进行解密，计算明文m=c^d mod n。也就是密文8的3次方模15，8^3mod15=512mod15得明文为2
综上所述，通过RSA算法，我们可以将明文2加密为密文8，然后再将密文8解密回明文2。这个过程展示了RSA算法的基本原理和操作方法。需要注意的是，在实际应用中，通常会选择更大的质数p和q来确保算法的安全性。