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$

設 $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$