RSA加密算法简记
基於大素數分解的困難性,解密算法用歐拉定理得證。
初始化工作
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