[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

コンピュータIIL(情報科学入門)第9回

目次
9.1 暗号
9.1.1 暗号の基本
9.1.2 単純な暗号
9.1.3 公開鍵方式
9.2 演習9
9.3 レポート課題
9.4 参考文献
索引
RSAアルゴリズム   暗号   暗号化   暗号文   解読     共通鍵方式   公開鍵   公開鍵方式   シーザー暗号   ビジネル暗号   秘密鍵   平文   復号  

9.1 暗号

9.1.1 暗号の基本

暗号cryptography ) とは、秘密の通信を行う仕組みのことです。

暗号における登場人物は、送信者、受信者、および悪意の第三者です。 送信者は受信者に対してメッセージを送ります。 このとき、何らかの方法でメッセージを変換してから送信します。 通信の途中で第三者はメッセージを盗聴しますが、変換されたメッセージはなかなか理解できません。 一方、受信者は変換方法についての知識を持っていますので、受信したメッセージを逆変換して内容を理解します。

変換前のメッセージを 平文plaintext ) と呼び、変換後のメッセージを 暗号文cryptogram ) と呼びます。 変換方法についての知識は、 key ) と呼ばれます。 暗号文に変換することを 暗号化encryption ) と言い、鍵を使って元に戻すことを 復号decryption ) と言います。 鍵を使わずに元に戻すことを 解読cryptanalysis ) と言います。

良い暗号とは、暗号化と復号が簡単で、解読が難しいものです。

9.1.2 単純な暗号

話を簡単にするために、平文はアルファベットの大文字の列とし、スペースは使わないことにします。

はじめに紹介するのは シーザー暗号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

ビジネル暗号では、鍵が長ければ長いほど解読が難しくなります。

9.1.3 公開鍵方式

シーザー暗号でもビジネル暗号でも、暗号解読者に鍵が盗まれますと、もうおしまいです。 したがって、鍵は通信相手に安全に配送し、厳重に管理する必要があります。 しかし、通信相手が増えますと、鍵の配送と管理が負担になってきます。

例えば、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 ) % (( q - 1) * ( r - 1)) = 1

を満たす p (≠ s )を探します。 ここで、"%"は割った余りを求めるという剰余演算です。 このとき、公開鍵は ( p , n ) であり、整数 x (0 ≦ xn )の暗号化は式 x ^ p % n によって行われます。 ここで、 x ^ pxp 回掛けるという、べき乗演算です。 秘密鍵は ( s , n ) であり、整数 x (0 ≦ xn )の復号は式 x ^ s % n によって行われます。

数学的な性質により、この暗号化を行ってからこの復号を行うと元に戻ります。 暗号化と復号の式のべき乗演算と剰余演算は、少し工夫しますと、コンピュータで簡単に計算できます。 重要なのは、公開鍵 ( p , n ) から秘密鍵 ( s , n ) がなかなか導けないことです。 s を知るためには、どうしても qr が必要です。 これは、 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"に戻ります。

表 9.1  文字の符号とべき乗の値
文字 符号 べき乗
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"となる。


9.2 演習9

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.3 レポート課題

今日の演習9の答案をメールで提出してください。 メールの差出人は学内のアドレス(b04a001@twcu.ac.jpなど)とし、メールの宛先はkonishi@twcu.ac.jpとします。 メールの本文には、学生番号、氏名、科目名、授業日(12月2日)を明記してください。


9.4 参考文献


[小西ホームページ]   [目次・索引]   [前の授業]   [次の授業]

2005年12月2日更新
小西 善二郎 <konishi@twcu.ac.jp>
Copyright (C) 2005 Zenjiro Konishi. All rights reserved.