首页 > 代码库 > 关于RSA算法

关于RSA算法

关于RSA算法

                ——记"永恒之蓝"事件

RSA的加密解密都是在整数环$Z_n$?内完成的.

设明文$x$和密文$y$?是$Z_n$?内的元素,使用公钥进行加密可表示为:

  • 给定公钥$(n,e)$和明文$x$,则密文$y=x^e(mod n)$,其中$x,y \in Z_n$.

使用私钥进行解密可表示为:

  • 给定私钥$(n,d)$和密文$y$,则明文$x=y^d(mod n)$,其中$x,y \in Z_n$.

通常,$x$,$y$,$n$和$d$都是非常大的数字.$e$有时被称为公开指数,$d$被称为保密指数.

以下是RSA密码体制中计算公钥$(n,e)$和私钥$(n,d)$的步骤:

  1. 选择两个大整数$p$和$q$.
  2. 计算$n=p\times q$.
  3. 计算$\varphi(n)=(p-1) \times (q-1)$.
  4. 随机选择满足$(e,\varphi(n))=1$的公开指数$e \in \{1,2,...,\varphi(n)-1\}$.
  5. 计算满足$e \times d \equiv 1(mod n)$的保密指数$d$.

证明RSA方案的可行性:

条件$(e,\varphi(n))=1$保证了$Z_{\varphi(n)}$中存在$e$的逆元,即保密指数$d$必存在.

设$e \times d=k \times \varphi(n)+1$,根据加密公式和解密公式及欧拉定理,

有$x \equiv y^d \equiv (x^e)^d \equiv x^{ed} \equiv x^{k\varphi(n)+1} \equiv x^{k\varphi(n)} \times x \equiv x(mod n)$.证毕.

 

关于RSA算法