RSA算法解析

基本步骤

1. 随机选择两个大素数p和q,保密.
2. 计算欧拉函数&n=(p-1)*(q-1)
3. 计算n=p*q (n是公钥的一部分)
4. 随机选择正整数e,且1<e<&n , e不能被n整除. (e是公钥的一部分)
5. 私钥d = ( 2*&n+1 ) / e
6. 公钥加密数据:密文C = 明文的e次方 mod n
7. 私钥解密数据: 明文 = 密文C的d次方 mod n

举例

1. p = 53, q = 59 (保密)
2. &n = 52 * 58 = 3016
3. n = 53 * 59 = 3127 (公钥的一部分)
4. e = 3 (公钥的一部分)
5. 私钥 d = (2 * 3016 + 1) / 3 = 2011
6. 假如明文是89. 密文C = 89的3次方 mod 3127 = 1394
7. 私钥解密数据: 明文 = 1394的2011次方 mod 3127 = 89

要应用rsa密码,应当采用足够大的整数n. 一般加密密钥和认证密钥选n为1024位,而平台根密钥和存储根密钥则选n为2048位.

e 的二进制表示中应该尽量含有少的1.
e=3是不安全的,因为e太小,对于小的明文M,则有C=M的e次方<n,加密运算未取模.直接对密文C开e次方,即可求出明文M.

现在普遍使用e=2的16次方+1 = 65537 , 二进制表示中只有两个1,且安全.