RSA加密算法简记

λ posted @ 2011年9月05日 13:40 in Algorithm with tags arithmetic , 2786 阅读

基於大素數分解的困難性,解密算法用歐拉定理得證。

初始化工作

1. 取兩個大素數:$p,\ q,\ (p \ne q)$

2. $n = pq,\ \Phi (n) = (p-1)(q-1)$

3. 取正整數 $w$ ,$\mathrm{gcd}(w,\ \Phi (n)) = 1$

3. 求 $w$ 的模 $\Phi (n)$ 逆 $d$ ,即有 $dw \equiv 1 (\mathrm{mod}\ \Phi (n))$

4. 將明文數字化,並分成多段,每段的值 $m$ 小於 $n$ 。

加密

$c = E(m) = m^w\ \mathrm{mod}\ n$

解密

$m = D(c) = c^d\ \mathrm{mod}\ n$

 

公鑰:$w,\ n$

私鑰:$p,\ q,\ \Phi (n),\ d$

 


附快速模冪運算方法

$a^b\ \mathrm{mod}\ n$

設 $b$ 的二進製表示為 $b_{r-1}\ldots b_{1}b_{0}$,即有

$b = b_{0} + b_{1}\times 2 + \cdots + b_{r-1}\times 2^{r-1}$

於是

$a^b \equiv a^{b_0} \times (a^2)^{b_1} \times \cdots \times (a^{2^{r-1}})^{b_{r-1}} (\mathrm{mod}\ n)$

令 $A_0 = a,\ A_i \equiv A_{i-1}^2 (\mathrm{mod}\ n),\ i = 1, 2, \cdots , r-1$ ,則有

$a^b \equiv A_0^{b_0} \times A_1^{b_1} \times \cdots \times A_{r-1}^{b_{r-1}} (\mathrm{mod}\ n)$

上面,$A_i^{b_i} = \begin{cases}A_i,\ 若\ b_i = 1\\1,\ 若\ b_i = 0\end{cases}\quad i = 0, 1, \cdots , r-1$

 


本網站無註明「轉載」的著作均由Jak Wings製作 CC BY-NC-SA 2.5
Creative Commons 保持署名-相同方式分享 2.5

  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter