RSA算法详解及手算过程

其余算法详解及实现见专栏合集~

RSA算法详解

• 算法过程

（i）密钥生成

密钥包括公钥n,e和私钥d。

首先确定两个大素数p和q，计算n，有：

确定了n后，可以计算出:

根据e和的互质，选取一个小于的e。

找到e后，根据, 可计算得d。

（ii）加密算法

约定明文为M，密文为C，公钥对{e,n}，私钥对{d,n}

加密过程：

（iii)解密算法

• 算法特点

（i）基于数论

欧几里得算法、离散对数、欧拉函数、欧拉定理、费马小定理、乘法逆元等。

（ii）大数分解的陷门函数

RSA是基于大合数的因子分解十分困难而构造的一种在数学上不可逆的加密算法。应密切关注黎曼猜想的有关证明，即大素数的分布规律。

（iii）幂运算与模运算

手算过程