1. Ｂは、L=(p-1)(q-1) を計算し、L と互いに素な自然数 e を選ぶ。
   ここで、L は、任意の N 以下の自然数 m に対して m の L 乗(以下 m^L と書く) を N で割ると余りが 1 になるような数(以下、m^L mod N = 1 と書く)であることに注意。 (オイラーの定理)
2. 秘密鍵 d を、de mod L =1 となるようにとる。つまり、ある整数 k に対して、de = k･L + 1 が成り立っている。
   このような数の存在は、1.で、L と e が互いに素であることからいえる。
3. e と N を公開鍵とする。
4. Ａは、平文 W に対して、r = W^e mod N を暗号として送る。なお、W の桁数は N よりも小さくとる。
5. Ｂは、r = W^e mod N を d 乗し、N で割った余りを求めると、W = r^d mod N になる。
   なぜなら、r^d mod N = W^(de) mod N = W^{k･L + 1} mod N = W だから。
   (W^L = 1 mod N に注意せよ。)

オイラーの定理

自然数 n に対して、n 以下の、n と互いに素な数の個数を N(n) とすると、 n と互いに素である任意の自然数 a に対して a^N(n) mod n = 1 が成り立つ。

注：特に n が素数の場合がフェルマーの小定理である。
フェルマーの小定理
p が素数のとき、p 以下の任意の自然数 a に対して a^(p-1) mod p = 1 が成り立つ。


(証明)
簡単のため、フェルマーの小定理の証明のみにする。オイラーの定理の証明もほぼ同様。
1,2,…,(p-1) のおのおのに a をかけた数、 a, 2a, … , (p-1)a を考える。
ここで、a と p が互いに素であることから、 a mod p, 2a mod p, … (p-1)a mod p はすべて異なる数になることが分かる。…（＊）
( ka mod p = la mod p と仮定すると、(k-l) a mod p = 0 となり、p が素数なので、k=lとなる。)

これらをすべて乗じると、a X 2a X … X (p-1)a = 1･2･…･(p-1) X a^(p-1) となるので、これを p で割った あまりを考える。
ここで、（＊）から、a X 2a X … X (p-1)a mod p = 1･2･…･(p-1) mod p となることが分かるから、
a X 2a X … X (p-1)a mod p = 1･2･…･(p-1) X a^(p-1) mod p と連立すると、

a^(p-1) mod p = 1

を得る。(証明終)