| 目次 | 索引 |
|---|---|
h2 暗号 toc-cryptography
h3 暗号の仕組み toc-cryptography-system
index 暗号 cryptography あんこう
とは、秘密の通信を行う仕組みのことです。
暗号における登場人物は、送信者、受信者、および悪意の第三者です。
送信者は受信者に対してメッセージを送ります。
このとき、何らかの方法でメッセージを変換してから送信します。
通信の途中で第三者はメッセージを盗聴しますが、
変換されたメッセージはなかなか理解できません。
一方、受信者は変換方法についての知識を持っていますので、
受信したメッセージを逆変換して内容を理解します。
変換前のメッセージを
index 平文 plaintext ひらふん
と呼び、変換後のメッセージを
index 暗号文 cryptogram あんこうふん
と呼びます。
変換方法についての知識は、
index 鍵 key かき
と呼ばれます。
暗号文に変換することを
index 暗号化 encryption あんこうか
と言い、鍵を使って元に戻すことを
index 復号 decryption ふくこう
と言います。
鍵を使わずに元に戻すことを
index 解読 cryptanalysis かいとく
と言います。
良い暗号とは、暗号化と復号が簡単で、解読が難しいものです。
h3 単純な暗号 toc-simple-cryptographies
話を簡単にするために、平文はアルファベットの大文字の列とし、
スペースは使わないことにします。
はじめに紹介するのは
index シーザー暗号 Caesar cipher しいさああんこう
です。
これは、平文の文字を、
アルファベット順の K 個後の文字に置き換えるものです。
ただし、'Z' の次は 'A' に戻るとします。
シーザー暗号では、K の値が鍵になります。
復号は、K 個前の文字に置き換えるとできます。
例えば、平文を "HIDEYONOGUCHI" とし、
K = 3 としますと、暗号文は "KLGHBRQRJXFKL" となります。
シーザー暗号はすぐに解読されます。
なぜなら、K = 1, K = 2, ..., K = 25 をすべて試し、
意味の通るものを選べばよいからです。
シーザー暗号を拡張したものに、
index ビジネル暗号 Vigenere cipher ひしねるあんこう
があります。
ビジネル暗号では、鍵はアルファベットの列です。
例として、平文を "ICHIYOHIGUCHI" とし、
鍵を "ABC" とします。
まず、平文を書き、その下に鍵を繰り返し書きます。
そして、平文の文字の直下が 'A' ならば、
アルファベット順の次の文字に置き換え、
'B' ならば次の次の文字に置き換え、'C' ならば 3 個後の文字に置き換え、
…とします。
ICHIYOHIGUCHI 平文
ABCABCABCABCA 鍵
JEKJARIKJVEKJ 暗号文
ビジネル暗号では、鍵が長ければ長いほど解読が難しくなります。
h3 公開鍵方式 toc-public-key-system
シーザー暗号でもビジネル暗号でも、
暗号解読者に鍵が盗まれますと、もうおしまいです。
したがって、鍵は通信相手に安全に配送し、厳重に管理する必要があります。
しかし、通信相手が増えますと、鍵の配送と管理が負担になってきます。
例えば、A 子は友達の B 子と秘密の通信をするために、
B 子のための鍵を作り、
それを B 子に (直接会うなどして) こっそり教えたとします。
そして、A 子は新たに C 子と友達になり、
C 子とも秘密の通信を始めるとします。
このとき、C 子に B 子のための鍵を教えるわけにはいきません。
なぜなら、B 子とのやり取りが C 子に解読されてしまうからです。
結局、友達が一人増えるたびに新しい鍵を作り、
それをこっそり教えることになります。
何度も鍵をこっそり教えることも、
たくさんの鍵を盗まれないようにすることも大変です。
この問題を解決するために、
暗号化の鍵と復号の鍵を別にする暗号方式が考え出されました。
この方式では、暗号化の鍵は広く世間に公開します。
復号の鍵は秘密にしておきます。
これが、
index 公開鍵方式 public key system こうかいかきほうしき
です。
公開する鍵を
index 公開鍵 public key こうかいかき
と呼び、秘密にする鍵を
index 秘密鍵 secret key ひみつかき
と呼びます。
公開鍵方式に対して、暗号化の鍵と復号の鍵が同じ暗号方式を、
index 共通鍵方式 common key system きようつうかきほうしき
と呼びます。
公開鍵方式では、
A 子は自分の公開鍵をホームページなどを使って公開します。
秘密鍵は自分のパソコンなどに保存し、他人には一切教えません。
A 子に対して B 子が送信を行う場合、
B 子は A 子の公開鍵を取得し、これを使って暗号化します。
暗号文を受信した A 子は、自分の秘密鍵を使って復号します。
B 子も自分の公開鍵を公開してくれれば、
A 子から B 子への通信も行えます。
また、A 子は C 子のための新しい鍵を作る必要もありません。
公開鍵方式では、秘密鍵を一度も他人に教えることはありません。
また、通信相手が増えても、
秘密鍵は自分のものを一つだけ管理すればよいのです。
公開鍵方式が成立するためには、以下の条件が必要です。
・公開鍵で暗号化して秘密鍵で復号すると、元の平文に戻る。
・公開鍵と秘密鍵は異なる。
・公開鍵から秘密鍵を求めることは、コンピュータを使っても難しい。
・暗号化も復号も、コンピュータで簡単に処理できる。
この条件を満たす暗号方式としては、
RSA アルゴリズムが有名です。
index RSA アルゴリズム RSA algorithm ＲＳＡあるこりすむ
は、数論に基づいた暗号化・復号の方法です。
これは、まず、100 桁程度の素数を 3 個ランダムに生成し、
最大のものを s とし、残りを q, r とします。
n = q * r と置きます。
n は 200 桁程度になります。
次に、条件
(p * s) % ((q - 1) * (r - 1)) = 1
を満たす 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 * s) % ((q - 1) * (r - 1)) = 1
を満たす p を探し、p = 27 を見つけます。
したがって、公開鍵は (p, n) = (27, 51) であり、
秘密鍵は (s, n) = (19, 51) です。
平文を "HIDEYONOGUCHI" とします。
下記の表にしたがって符号化しますと、
7 8 3 4 24 14 13 14 6 20 2 7 8
となります。
式 x ^ p % n によって暗号化しますと、
31 2 24 13 48 44 4 44 39 41 8 31 2
となります。
したがって、暗号文は "fCYNwsEsnpIfC" となります。
式 x ^ s % n によって復号しますと、
7 8 3 4 24 14 13 14 6 20 2 7 8
となります。
したがって、元の平文 "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. この公開鍵と秘密鍵が、
RSA アルゴリズムの条件を満たしていることを確認してください。
2. A 子の友達になったつもりで、人名など、
アルファベット 10 文字以上の平文を考え、
それを公開鍵によって暗号化してください。
x ^ p % n の計算は上記の表を利用してください。
3. A 子になったつもりで、受け取った暗号文を、
秘密鍵によって復号してください。
x ^ s % n の計算は上記の表を利用してください。
解答例 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" とする。
これを上記の表にしたがって符号化すると、
8 2 7 8 24 14 7 8 6 20 2 7 8
となる。
式 x ^ p % n によって暗号化すると、
32 26 46 32 12 23 46 32 48 11 26 46 32
となる。
したがって、暗号文は "gaugMXugwLaug" となる。
3. 暗号文は "gaugMXugwLaug" すなわち
32 26 46 32 12 23 46 32 48 11 26 46 32
である。
式 x ^ s % n によって復号すると、
8 2 7 8 24 14 7 8 6 20 2 7 8
となる。
したがって、平文は "ICHIYOHIGUCHI" となる。
h2 演習 9 toc-exercises
B 子は、RSA アルゴリズムのための素数として
q = 17, r = 3, s = 29 を選び、n = q * r = 51 とし、
(p, n) = (21, 51) を公開鍵として友達全員に公開し、
(s, n) = (29, 51) を秘密鍵として自分のパソコンに隠しておきました。
1. この公開鍵と秘密鍵が、
RSA アルゴリズムの条件を満たしていることを確認してください。
2. B 子の友達になったつもりで、人名など、
アルファベット 10 文字以上の平文を考え、
それを公開鍵によって暗号化してください。
x ^ p % n の計算は上記の表を利用してください。
3. B 子になったつもりで、受け取った暗号文を、
秘密鍵によって復号してください。
x ^ s % n の計算は上記の表を利用してください。
今日の演習9の答案をkonishi@twcu.ac.jpあてにメールで送ってください。 メールには、学生番号、氏名、科目名、授業日（11月26日）を明記してください。