RSA

【基于分解大整数的困难性假定】

密钥产生

（1）选取两个大素数p,q。【大素数】

（2）计算n = p*q，φ(n) = (p-1)(q-1)【欧拉函数】

（3）选取一整数e，满足1<e<φ(n),切（φ(n),e）= 1【最大公因数】

（4）计算d，满足d*e ≡ 1 mod φ(n)【d是e在模φ(n)下的乘法逆元】

（5）{e,n}为公开钥，{d,n}为秘密钥。

加密

（1）将明文比特串分组，使得每个分组对应的十进制数小于n。

（2）加密：c ≡ m^e mod n【m为明文】

解密

（1）m ≡ c^d mod n

改进RSA

【运用中国剩余定理提高解密运算的速度，解密运算速度提高三倍以上】
（1）d_p ≡ d mod (p-1)。 d_q ≡ d mod (q-1)
（2）解：m_p ≡ c^dp ≡ c^d ≡ m mod p， m_q ≡ c^dq ≡ c^d ≡ m mod q 。得m

安全性

估计在未来一段时间，密钥长度介于1024比特至2048比特之间的RSA是安全的。