情報交換概論 第 7 回 (動画作成ソフトウェア実習) 「2 つの素数のべき」 講義ノート目次

公開暗号鍵と復号鍵を作るために、法則を発見してみる。

1. 素数の積を法とする 1 .. pq までの数に 1 .. pq 乗をかけたものを pq で割った余りを書き込む。( k ** l % pq, k と l は 1 .. pq までの整数)
2. (p-1) と (q-1) の最小公倍数に 1 を加えた数ごとに 1..pq が表れるのを確認する。

暗号地図プログラム を動かしてみる。 公開鍵で暗号化するプログラム を動かしてみる。 復号化するプログラム を動かしてみる。

p = 3, q = 7 の素数の場合で以降考える。公開鍵を s = 5, 平文を "10 9 2 18" とする。

      ^ 1 ^ 2 ^ 3 ^ 4 ^ 5 ^ 6 ^ 7 ^ 8 ^ 9 ^10 ^11 ^12 ^13 
---------------------------------------------------------
d= 1|   1   1   1   1   1   1   1   1   1   1   1   1   1
d= 2|   2   4   8  16  11   1   2   4   8  16  11   1   2
d= 3|   3   9   6  18  12  15   3   9   6  18  12  15   3
d= 4|   4  16   1   4  16   1   4  16   1   4  16   1   4
d= 5|   5   4  20  16  17   1   5   4  20  16  17   1   5
d= 6|   6  15   6  15   6  15   6  15   6  15   6  15   6
d= 7|   7   7   7   7   7   7   7   7   7   7   7   7   7
d= 8|   8   1   8   1   8   1   8   1   8   1   8   1   8
d= 9|   9  18  15   9  18  15   9  18  15   9  18  15   9
d=10|  10  16  13   4  19   1  10  16  13   4  19   1  10
d=11|  11  16   8   4   2   1  11  16   8   4   2   1  11
d=12|  12  18   6   9   3  15  12  18   6   9   3  15  12
d=13|  13   1  13   1  13   1  13   1  13   1  13   1  13
d=14|  14   7  14   7  14   7  14   7  14   7  14   7  14
d=15|  15  15  15  15  15  15  15  15  15  15  15  15  15
d=16|  16   4   1  16   4   1  16   4   1  16   4   1  16
d=17|  17  16  20   4   5   1  17  16  20   4   5   1  17
d=18|  18   9  15  18   9  15  18   9  15  18   9  15  18
d=19|  19   4  13  16  10   1  19   4  13  16  10   1  19
d=20|  20   1  20   1  20   1  20   1  20   1  20   1  20

暗号化プログラムより、 暗号化した文は "19 18 11 9" と得られた。

復号化プログラムより、復号する秘密鍵は d = 5 となり、 復号できることがわかる。