例

1. \(p\) と \(q\) を決める
\(p=19, q=13\) とする
(本来は非常に大きい値にするが、説明を簡単にするためここでは小さい値にする)


2. \(n\) と \(L\) を求める
\(n=pq=247\)
\(L=lcm(18, 12)=36\)
(「\(lcm\)」は最小公倍数のこと)


3. \(e\) を決める
\(L=36\) を素因数分解すると \(2^2\times3^2\) となる。1以外の共通の約数を持たないということは、要するに「2でも3でも割り切れない」ということ。2～35の範囲の数を書きだして2か3で割り切れるものを消していけば、5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 が残る。\(e\) はこの中のどれでもよいが、ここでは \(e=23\) とする。

		2	3	4	5	6	7	8	9
10	11	12	13	14	15	16	17	18	19
20	21	22	23	24	25	26	27	28	29
30	31	32	33	34	35



4. \(d\) を求める
満たすべき関係式 \(de=kL+1\) には \(d\) と \(e\) が対称な形で入っている。つまり、\(d\) も 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35 のどれかになる。
この関係式の \(e\) と \(L\) にそれぞれ 23, 36を入れると \(23d=36k+1\) になり、1を移項して両辺を36で割れば


\((23d-1)/36=k\)

となる。つまり、候補の値それぞれについてこの左辺の値を計算し、それが整数になるどうかを調べればその \(d\) が対応するものかどうかがわかる。 順番に調べていくと
• \(d\) が \(5\) → \((23\times5-1)/36=3.1...\) (整数でないのでこれは違う)
• \(d\) が \(7\) → \((23\times7-1)/36=4.4...\) (整数でないのでこれは違う)
• \(d\) が \(11\) → \((23\times11-1)/36=7\)
なので、\(e=23\) に対応する \(d\) は \(11\) であることがわかる。


5. 送信者に \(e\) と \(n\) の値を渡す
通信路を通して \(e=23\) と \(n=247\) を送る

ステップ1と3では値を勝手に決める。
ステップ2と4で決まる値は一通りだけ。

ステップ3での「互いに素」の意味に注意。この場合は2, 3で割り切れないだけで、素数ということではない (候補のうち25, 35は素数ではない)

ステップ4で \(e\) から \(d\) を求めているので、\(e\) を通信路に通すのは危険なように見えるが、このステップには \(L\) の値も必要なので、これを通信路に通さなければ安全 (原理的には \(n\) を因数分解すれば求められるが、実際は \(n\) は非常に大きい値になるので、現実的な時間内にこれを行うのはほとんど不可能)。

例 (上で挙げた \(n=247\), \(e=23\), \(d=11\) のケース (\(m\) は\(7\) になる)

暗号化

1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
たとえば「0001101」だったときは \((0001101)_2=(13)_{10}\) が得られる


2. 変換した値を \(e\) 乗して \(n\) で割った余りを求める

\(13^{23}=1820828145547961773257038736474630733299942338773\)

で、それを247で割った余りは52になる。


3. 得られた値を \(m\) ビットの符号とする
\((52)_{10}=(0110100)_2\) なので、「0110100」とする

復号

1. 符号を \(m\) 桁ずつ区切り、2進数の値にする
受け取った「0110100」から \((0110100)_2=(52)_{10}\) が得られる


2. 変換した値を \(d\) 乗して \(n\) で割った余りを求める

\(52^{11}=140007514618240900831252\)

で、それを247で割った余りは13になる。


3. 得られた値を \(m\) ビットの符号とする
\((13)_{10}=(0001101)_2\) なので、「0001101」とする (もとの符号が得られる)

実際の暗号化・復号はプログラムで行うが、この際に「＊＊を＊＊乗して＊＊で割った余り」をまともに求めることはない (まともに求めようとすると int や long で扱える範囲を遥かに超えてしまう)。
「52の2乗」をA+B、つまりA(247で割り切れる部分) とB(余り)に分けて考えると、「52の3乗」は52A+52Bになるが、52Aは247で割り切れる。
つまり、「52の3乗」のかわりに「52B」を247で割っても余りは同じになる。
このようにしてひとつ247をかけるたびに余りを求めていけば、上の例のように巨大な数を扱わなくても最終的な余りは求められる。 例えばProcessingなら次のようになる。

int n=247; int d=11; int num0=52; int num=num0; for (int i=0; i<d; i++) { print((i+1)+"乗して"+n+"で割った余り:"); println(num); num=num*num0%n; }

1乗して247で割った余り:52 2乗して247で割った余り:234 3乗して247で割った余り:65 4乗して247で割った余り:169 5乗して247で割った余り:143 6乗して247で割った余り:26 7乗して247で割った余り:117 8乗して247で割った余り:156 9乗して247で割った余り:208 10乗して247で割った余り:195 11乗して247で割った余り:13