暗号 （ cryptography ） とは、秘密の通信を行う仕組みのことです。
暗号における登場人物は、送信者、受信者、および悪意の第三者です。 送信者は受信者に対してメッセージを送ります。 このとき、何らかの方法でメッセージを変換してから送信します。 通信の途中で第三者はメッセージを盗聴しますが、変換されたメッセージはなかなか理解できません。 一方、受信者は変換方法についての知識を持っていますので、受信したメッセージを逆変換して内容を理解します。
変換前のメッセージを 平文 （ plaintext ） と呼び、変換後のメッセージを 暗号文 （ cryptogram ） と呼びます。 変換方法についての知識は、 鍵 （ key ） と呼ばれます。 暗号文に変換することを 暗号化 （ encryption ） と言い、鍵を使って元に戻すことを 復号 （ decryption ） と言います。 鍵を使わずに元に戻すことを 解読 （ cryptanalysis ） と言います。
良い暗号とは、暗号化と復号が簡単で、解読が難しいものです。
話を簡単にするために、平文はアルファベットの大文字の列とし、スペースは使わないことにします。
はじめに紹介するのは シーザー暗号 （ Caesar cipher ） です。 これは、平文の文字を、アルファベット順の K 個後の文字に置き換えるものです。 ただし、"Z"の次は"A"に戻るとします。 シーザー暗号では、 K の値が鍵になります。 復号は、 K 個前の文字に置き換えるとできます。
例えば、平文を"HIDEYONOGUCHI"とし、 K = 3 としますと、暗号文は"KLGHBRQRJXFKL"となります。
シーザー暗号はすぐに解読されます。 なぜなら、 K = 1, K = 2, ..., K = 25 をすべて試し、意味の通るものを選べばよいからです。
シーザー暗号を拡張したものに、 ビジネル暗号 （ Vigenere cipher ） があります。 ビジネル暗号では、鍵はアルファベットの列です。
例として、平文を"ICHIYOHIGUCHI"とし、鍵を"ABC"とします。 まず、平文を書き、その下に鍵を繰り返し書きます。 そして、平文の文字の直下が"A"ならば、アルファベット順の次の文字に置き換え、"B"ならば次の次の文字に置き換え、"C"ならば3個後の文字に置き換え、…とします。
| 平文 | I | C | H | I | Y | O | H | I | G | U | C | H | I |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 鍵 | A | B | C | A | B | C | A | B | C | A | B | C | A |
| 暗号文 | J | E | K | J | A | R | I | K | J | V | E | K | J |
ビジネル暗号では、鍵が長ければ長いほど解読が難しくなります。
シーザー暗号でもビジネル暗号でも、暗号解読者に鍵が盗まれますと、もうおしまいです。 したがって、鍵は通信相手に安全に配送し、厳重に管理する必要があります。 しかし、通信相手が増えますと、鍵の配送と管理が負担になってきます。
例えば、A子は友達のB子と秘密の通信をするために、B子のための鍵を作り、それをB子に（直接会うなどして）こっそり教えたとします。 そして、A子は新たにC子と友達になり、C子とも秘密の通信を始めるとします。 このとき、C子にB子のための鍵を教えるわけにはいきません。 なぜなら、B子とのやり取りがC子に解読されてしまうからです。 結局、友達が一人増えるたびに新しい鍵を作り、それをこっそり教えることになります。 何度も鍵をこっそり教えることも、たくさんの鍵を盗まれないようにすることも大変です。
この問題を解決するために、暗号化の鍵と復号の鍵を別にする暗号方式が考え出されました。 この方式では、暗号化の鍵は広く世間に公開します。 復号の鍵は秘密にしておきます。 これが、 公開鍵方式 （ public key system ） です。 公開する鍵を 公開鍵 （ public key ） と呼び、秘密にする鍵を 秘密鍵 （ secret key ） と呼びます。
公開鍵方式に対して、暗号化の鍵と復号の鍵が同じ暗号方式を、 共通鍵方式 （ common key system ） と呼びます。
公開鍵方式では、A子は自分の公開鍵をホームページなどを使って公開します。 秘密鍵は自分のパソコンなどに保存し、他人には一切教えません。 A子に対してB子が送信を行う場合、B子はA子の公開鍵を取得し、これを使って暗号化します。 暗号文を受信したA子は、自分の秘密鍵を使って復号します。 B子も自分の公開鍵を公開してくれれば、A子からB子への通信も行えます。 また、A子はC子のための新しい鍵を作る必要もありません。
公開鍵方式では、秘密鍵を一度も他人に教えることはありません。 また、通信相手が増えても、秘密鍵は自分のものを一つだけ管理すればよいのです。
公開鍵方式が成立するためには、以下の条件が必要です。
この条件を満たす暗号方式としては、RSAアルゴリズムが有名です。 RSAアルゴリズム （ RSA algorithm ） は、数論に基づいた暗号化・復号の方法です。
RSAアルゴリズムでは、まず、100桁程度の素数を3個ランダムに生成し、最大のものを s とし、残りを q , r とします。 n = q * r と置きます。 n は200桁程度になります。 次に、条件
を満たす p （≠ s ）を探します。 ここで、"%"は割った余りを求めるという剰余演算です。 このとき、公開鍵は ( p , n ) であり、整数 x （0 ≦ x ＜ n ）の暗号化は式 x ^ p % n によって行われます。 ここで、 x ^ p は x を p 回掛けるという、べき乗演算です。 秘密鍵は ( s , n ) であり、整数 x （0 ≦ x ＜ n ）の復号は式 x ^ s % n によって行われます。
数学的な性質により、この暗号化を行ってからこの復号を行うと元に戻ります。 暗号化と復号の式のべき乗演算と剰余演算は、少し工夫しますと、コンピュータで簡単に計算できます。 重要なのは、公開鍵 ( p , n ) から秘密鍵 ( s , n ) がなかなか導けないことです。 s を知るためには、どうしても q と r が必要です。 これは、 n を因数分解するしかありません。 しかし、200桁もの整数を因数分解するのは、コンピュータで何万年もかかる難問であると考えられています。
ここで、RSAアルゴリズムの具体例を示します。 ただし、本来の100桁程度の計算は理解の妨げになりますので、1〜2桁の計算で済むようにします。 また、本来の n は200桁程度になりますので、平文のビット列を700ビット程度（10 ^ 200 ≒ 2 ^ 700）のブロックに分割してから暗号化しますが、ここでの n は小さな数ですので、平文を1文字ごとに暗号化します。
まず、3個の素数19, 17, 3を選び、 q = 17, r = 3, s = 19 とします。 n = q * r = 51 です。 上記の条件
を満たす p を探し、 p = 27 を見つけます。 したがって、公開鍵は ( p , n ) = (27, 51) であり、秘密鍵は ( s , n ) = (19, 51) です。 平文を"HIDEYONOGUCHI"とします。 下記の表にしたがって符号化しますと、
となります。 式 x ^ p % n によって暗号化しますと、
となります。 したがって、暗号文は"fCYNwsEsnpIfC"となります。 式 x ^ s % n によって復号しますと、
となります。 したがって、元の平文"HIDEYONOGUCHI"に戻ります。
| 文字 | 符号 | べき乗 | |||||
|---|---|---|---|---|---|---|---|
| 7 | 19 | 21 | 23 | 27 | 29 | ||
| A | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| B | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| C | 2 | 26 | 8 | 32 | 26 | 8 | 32 |
| D | 3 | 45 | 27 | 39 | 45 | 24 | 12 |
| E | 4 | 13 | 13 | 4 | 13 | 13 | 4 |
| F | 5 | 44 | 23 | 14 | 44 | 11 | 20 |
| G | 6 | 48 | 12 | 24 | 48 | 39 | 27 |
| H | 7 | 46 | 37 | 28 | 46 | 31 | 40 |
| I | 8 | 32 | 2 | 26 | 32 | 2 | 26 |
| J | 9 | 36 | 15 | 42 | 36 | 15 | 42 |
| K | 10 | 22 | 31 | 40 | 22 | 37 | 28 |
| L | 11 | 20 | 5 | 44 | 20 | 29 | 41 |
| M | 12 | 24 | 45 | 3 | 24 | 6 | 48 |
| N | 13 | 4 | 4 | 13 | 4 | 4 | 13 |
| O | 14 | 23 | 41 | 29 | 23 | 44 | 5 |
| P | 15 | 42 | 9 | 36 | 42 | 9 | 36 |
| Q | 16 | 16 | 16 | 16 | 16 | 16 | 16 |
| R | 17 | 17 | 17 | 17 | 17 | 17 | 17 |
| S | 18 | 18 | 18 | 18 | 18 | 18 | 18 |
| T | 19 | 43 | 25 | 49 | 43 | 25 | 49 |
| U | 20 | 11 | 44 | 5 | 11 | 41 | 29 |
| V | 21 | 30 | 30 | 21 | 30 | 30 | 21 |
| W | 22 | 10 | 40 | 31 | 10 | 28 | 37 |
| X | 23 | 14 | 29 | 41 | 14 | 5 | 44 |
| Y | 24 | 12 | 3 | 45 | 12 | 48 | 6 |
| Z | 25 | 49 | 19 | 43 | 49 | 19 | 43 |
| a | 26 | 2 | 32 | 8 | 2 | 32 | 8 |
| b | 27 | 39 | 48 | 6 | 39 | 3 | 45 |
| c | 28 | 37 | 22 | 10 | 37 | 46 | 7 |
| d | 29 | 41 | 11 | 20 | 41 | 23 | 14 |
| e | 30 | 21 | 21 | 30 | 21 | 21 | 30 |
| f | 31 | 40 | 7 | 46 | 40 | 10 | 22 |
| g | 32 | 8 | 26 | 2 | 8 | 26 | 2 |
| h | 33 | 33 | 33 | 33 | 33 | 33 | 33 |
| i | 34 | 34 | 34 | 34 | 34 | 34 | 34 |
| j | 35 | 35 | 35 | 35 | 35 | 35 | 35 |
| k | 36 | 9 | 42 | 15 | 9 | 42 | 15 |
| l | 37 | 28 | 10 | 22 | 28 | 7 | 46 |
| m | 38 | 47 | 47 | 38 | 47 | 47 | 38 |
| n | 39 | 27 | 6 | 48 | 27 | 45 | 3 |
| o | 40 | 31 | 46 | 7 | 31 | 22 | 10 |
| p | 41 | 29 | 20 | 11 | 29 | 14 | 23 |
| q | 42 | 15 | 36 | 9 | 15 | 36 | 9 |
| r | 43 | 19 | 49 | 25 | 19 | 49 | 25 |
| s | 44 | 5 | 14 | 23 | 5 | 20 | 11 |
| t | 45 | 3 | 39 | 27 | 3 | 12 | 24 |
| u | 46 | 7 | 28 | 37 | 7 | 40 | 31 |
| v | 47 | 38 | 38 | 47 | 38 | 38 | 47 |
| w | 48 | 6 | 24 | 12 | 6 | 27 | 39 |
| x | 49 | 25 | 43 | 19 | 25 | 43 | 19 |
| y | 50 | 50 | 50 | 50 | 50 | 50 | 50 |
例題1. A子は、RSAアルゴリズムのための素数として q = 17, r = 3, s = 23 を選び、 n = q * r = 51 とし、( p , n ) = (7, 51) を公開鍵として友達全員に公開し、( s , n ) = (23, 51) を秘密鍵として自分のパソコンに隠しておきました。
解答例1.
1. p * s = 161, ( q - 1) * ( r - 1) = 16 * 2 = 32 であり、161 / 32 = 5.03... なので、
| (p * s) % ((q - 1) * (r - 1)) | = | 161 % 32 |
| = | 161 - (5 * 32) | |
| = | 161 - 160 | |
| = | 1 |
となる。
2. 平文を"ICHIYOHIGUCHI"とする。 これを上記の表にしたがって符号化すると、
となる。 式 x ^ p % n によって暗号化すると、
となる。 したがって、暗号文は"gaugMXugwLaug"となる。
3. 暗号文は"gaugMXugwLaug"すなわち
である。 式 x ^ s % n によって復号すると、
となる。 したがって、平文は"ICHIYOHIGUCHI"となる。
B子は、RSAアルゴリズムのための素数として q = 17, r = 3, s = 29 を選び、 n = q * r = 51 とし、( p , n ) = (21, 51) を公開鍵として友達全員に公開し、( s , n ) = (29, 51) を秘密鍵として自分のパソコンに隠しておきました。
今日の演習9の答案をメールで提出してください。 メールの差出人は学内のアドレス（b04a001@twcu.ac.jpなど）とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日（12月2日）を明記してください。