RSA(以三个发明者的首位字母命名)的方法,该方法基于下面的两个事实:
1) 已有确定一个数是不是质数的快速算法;
2) 尚未找到确定一个合数的质因子的快速算法。
RSA方法的工作原理如下:
1) 任意选取两个不同的大质数p和q,计算乘积r=p*q;
2) 任意选取一个大整数e,e与(p-1)*(q-1)互质,整数e用做加密密钥。注意:e的选取是很容易的,例如,所有大 于p和q的质数都可用。
3) 确定解密密钥d: d * e = 1 modulo(p - 1)*(q - 1) 根据e、p和q可以容易地计算出d。
4) 公开整数r和e,但是不公开d;
5) 将明文P (假设P是一个小于r的整数)加密为密文C,计算方法为: C = P^e modulo r
6) 将密文C解密为明文P,计算方法为: P = C^d modulo r 然而只根据r和e(不是p和q)要计算出d是不可能的。因此,任何人都可对明文进行加密,但只有授权用户(知道d) 才可对密文解密。
下面举一简单的例子对上述过程进行说明,显然我们只能选取很小的数字。
例:选取p=3, q=5,则r=15,(p-1)*(q-1)=8。选取e=11(大于p和q的质数),通过d * 11 = 1 modulo 8, 计算出d =3。
假定明文为整数13。则密文C为 C = P^e modulo r = 13^11 modulo 15 = 1,792,160,394,037 modulo 15 = 7
复原明文P为: P = C^d modulo r = 7^3 modulo 15 = 343 modulo 15 = 13