高知大学 秋の公開講座
ユビキタス情報社会を支えるソフトウェアの世界
第4回
安全・確実に情報を伝える
高知大学 理学部 数理情報科学科
塩田研一
mail: [email protected]
http://lupus.is.kochi-u.ac.jp/~shiota/
2005年9月29日
1
講師の専門分野

保型形式の整数論
• フェルマー予想解決の道具となった整数論の中心分野
• 博士論文では50年間未解決だった問題を解決

計算代数
• 代数/整数計算を行うアルゴリズム・プログラムの開発

誤り訂正符号

暗号理論

組合せ論・グラフ理論

民俗学
2
Q&A
ご質問、ご意見ありましたら
3
今日のお話
1.
2.
3.
4.
5.
6.
7.
8.
9.
信号とは
通信の歴史
デジタル信号の利点
デジタル信号の誤りを自動的に訂正する技術
アナログ情報をデジタル信号に変換する方法
暗号の必要性
昔から使われてきた暗号
インターネット時代の新しい暗号:公開鍵暗号
暗号技術の色々
4
まずは通信の歴史を振り返りましょう
5
信号とは
- 音の届かない距離で情報を伝達する方法 -



のろし
… 光を利用、伝えられる情報は1つだけ
手旗信号
… 光を利用、文字を真似たパターン
モールス信号
… 電信用、トン・ツーの組合せで文字を表現
6
電信の始まりはデジタル

1835年: パルス送信に成功

1837年: 最初の電信会社設立

1844年: モールス信号による公開実験成功

1848年: テレプリンタ使用開始

1851年: 電信会社が営業開始
7
音も送りたい





解剖学的に
音 → 鼓膜が振動 → 知覚
だったら
膜を振動 → 音が再現 ?
1860年: ライスが電流から音を再生
1876年: ベル・グレイ・エジソンらが電
話を発明
1877年: エジソンが蓄音機を発明
8
無線通信の始まり

1864年: 電磁波の理論的存在証明

1888年: 電磁波存在の実証

1894年: 無線電信実験成功

1897年: 無線電信会社設立
9
アナログ無線通信へ

1906年: 鉱石検波器の発明

1906年: 無線電話の実験

1920年: 民間放送開始

1933年: FM方式の発明

1961年: FMステレオ放送開始
10
AM と FM

AM = Amplitude Modulation
(振幅変調)
… 搬送波の振幅のずれで信号を表現

FM = Frequency Modulation
(周波数変調)
… 搬送波の周波数のずれで信号を表現
11
AM
12
FM
13
Q&A
ご質問、ご意見ありましたら
14
歴史的に

通信はデジタルで始まった

技術の発達によってアナログ通信が可能に

しかし、今またデジタルの時代
… なぜ ?
15
次はデジタル信号のお話です
16
アナログの宿命 … 雑音は免れない
信号
信号と雑音は分離不可能
雑音
17
デジタル信号とは
0 または 1 を一定間隔で並べた信号
18
デジタル信号が雑音に強い理由 1
雑音
信号
0
1
0 か 1 かの判読は容易
19
デジタル信号が雑音に強い理由 2
受信した波形
中継点で
完全な0か1
に復元して次へ送信
すればOK
綺麗に復元してから送信
20
それでも誤りは起こる


0 か 1 かの判定
… 0.5 より大きいか小さいか
雑音が大きくて 0.5 以上狂えば、やは
り判定ミスが …
21
大きな雑音
信号
正確な判読は不可能
22
ここで誤り訂正技術が登場します
23
デジタル信号が雑音に強い理由 3


信号の作り方を工夫すると …
ある程度の判定ミスが自動的に訂正可能
工夫とは …
• 0,1 を幾つかまとめてブロックにする
• 各ブロックに「おまけ」を付ける
• 「おまけ」の効果で
 判定ミスを検出
 正しい信号に復元
24
簡単な例




ブロック = 1 ビット ( 0 か 1 かのひとつ分)
おまけ = 更に 2 つ !!
つまり
• 0 → 000 にして送信
• 1 → 111 にして送信
例えば、100 を受信したら誤りが起こったこと
がわかる
25
信号の訂正方法



正しいパターンは 000 と 111 だけ
100 と 000 の違い: 1 ビット
100 と 111 の違い: 2 ビット
⇒ 100 は 000 の間違い、と考えるべき
つまり 100 は 000 に訂正しよう
同じく
010, 001 は 000 に訂正しよう
011, 101, 110 は 111 に訂正しよう
26
このように
信号に「おまけ」を付けて誤りを自動訂正
する仕組みを
誤り訂正符号
と言う
27
Q&A
ご質問、ご意見ありましたら
28
さっきの例は
データ量が3倍になってしまう
もっと上手い方法はないかな?
29
日常会話に立ち返ると …

結婚式でお父さんのスピーチ
「ふしだらな娘ですが … 」
「ふつつか」 と言いたかったのだろう

誤り訂正の原則:
一番似ている、正しいパターンを探せ
30
ということは


できるだけ似ていないパターンを
正しいパターンとして採用せよ
⇒ 「どの正しいパターンに似てるか」
を考え易い
田村早苗(たむらさなえ)さんと
田浦花江(たうらはなえ)さんが
同じクラスにいたらややこしいのと一緒
31
ブロック長 7 のハミング符号
7桁の2進数:
128パターン
うち、右の16パターン
を正しい信号に採用
(右3桁がおまけ)
正しい信号同士は
お互い3桁以上違う
0000000
0111000
1010100
1101100
1100010
1011010
0110110
0001110
1111111
1000111
0101011
0010011
0011101
0100101
1001001
1110001
32
ブロック長 8 のアダマール符号
8桁の2進数:
256パターン
00000000
01010101
00110011
うち、右の16パターンを 01100110
正しい信号に採用
00001111
(第4,6,7,8 桁がおまけ) 01011010
00111100
01101001
正しい信号同士は
お互い4桁以上違う
11111111
10101010
11001100
10011001
11110000
10100101
11000011
10010110
33
音楽CDの音声信号




ブロック長 = 24 ビット
おまけ = 8 ビット
合計 = 32 ビット
ひとつの音の情報が1箇所に固まらな
いような工夫も
34
誤り訂正符号に求められる能力






訂正能力 : 訂正できる誤りの割り合い
情報率 : 「おまけ」は少なくしたい
処理速度 (記録時、再生時)
生産コスト
機材の重量 etc.
全てを満たすのは不可能
⇒ 状況に応じて優先順位を
35
Q&A
ご質問、ご意見ありましたら
36
ところで、アナログ情報を
デジタル信号に変換する方法は ?
37
アナログ情報をデジタル信号に
変換する方法 ( CDの例 )

音波の波形を棒グラフに直す:
• 棒の幅 : 1/44100 秒
• 棒の高さ : 65536 段階で表現
65536通り = 16桁の2進数 = 16ビット
38
音楽CDの記憶容量





生データは
44100 区画 × 60 秒 × 74 分 ×16 ビット × 右左
= 約 6.27 × 109 ビット = 約 747 MB
誤り訂正のおまけを付けて 4/3 倍
更に、安定した読取りの為のおまけをつけて 17/8 倍
更に更に、タイミングを取る為のおまけもプラス
⇒ 結局、生データの 49/16 倍の情報約 2.2 GB
CD-ROM は更に強い誤り訂正が必要 → 640 MB
39
アナログ情報をデジタル信号に
変換する方法 ( 静止画の例 )





三原色 = 青, 赤, 緑
液晶画面 = 小さな点(ピクセル)の集まり
各ピクセルの色を青, 赤, 緑色成分に分離
各成分の明るさを 256 段階で表現
( 256 通り = 8 ビット )
このままでは情報量が膨大
⇒ 情報圧縮技術の出番
40
静止画の画像形式

bmp ( ビットマップ ) :
… 情報そのまま

gif ( ジフ ) , png:
… 使う色の種類を少なく

jpg ( ジェイペグ ) :
… 色の分布を三角関数で大雑把に近似
• 画質 ( = 近似誤差の許容度 ) が指定可能
41
情報圧縮のアイデア色々



出現頻度の高いものは短い名前で
… モールス信号 etc.
ディティールを犠牲に
… jpg etc.
似たもの同士は「差」だけを記録
… mpeg etc.
42
中間まとめ

デジタル信号は雑音に強い

アナログ情報は棒グラフに直してデジタルに

デジタル信号に更に「おまけ」を付けると …
「おまけ」の効果で誤りの自動訂正が可能に
43
Q&A
ご質問、ご意見ありましたら
44
後半は暗号のお話です
45
シーザー暗号


L ORYH BRX って ???
実はアルファベットを3文字ずらしたもの
正解 : I LOVE YOU
46
暗号とは


読める文章(平文)を読めない文章(暗号文)に
変換する方法
送信者 : 平文 x を暗号文 y = f(x) に変換

受信者 : 逆関数を用いて f

シーザー暗号では

f

f
-1
(y) = x を解読
: 3 文字後ろにずらすこと
-1
: 3 文字前にずらすこと
47
1970年頃までの暗号は



送信者と受信者が 「秘密の関数 f(x)」 を共有
-1
f(x) がバレれば逆関数 f (y) もバレる
古典暗号、共通鍵暗号、対称暗号などと呼ばれ
る
48
1975年 Diffie-Hellman のアイデア


-1
f(x) がバレれても逆関数 f (y) がバレない、そ
んな関数があれば …
暗号文を受け取りたい人は f(x)を公開して、
-1
自分だけ f (y)を使って読めば良い

例えば
• 商店は f(x) を公開
• お客さんは注文書を f(x) で暗号化して送信
… 安心だよね
49
このような暗号方式を
公開鍵暗号
と言う
でもそんな都合のいい関数なんてあるの ??
f(x) がわかってれば f
-1
(y) って計算でき
るんじゃないの ???
50
1977年 最初の公開鍵暗号登場

Rivest, Shamir, Adleman の共同研究

整数関数を使って理想的な f(x) を構成

3人の頭文字を取って「RSA 暗号」と命名

その後も次々と新しい暗号方式が
ElGamal 暗号、楕円曲線暗号 etc.
51
マジックのタネ



高速にできる計算と、天文学的な時間の掛
かる計算を上手に利用
f(x) は高速な計算で
f
-1
(y) の計算には時間が掛かるように
52
例えば

問い:
p = 5025103959178413661189033433113
と
q =3815031238347521782706056223475180997
を掛けあわせなさい

答え:
n = 19170928580209458018899054265809726
563528784106572713024411968153661
… これは頑張れば手でもできる
53
ところが

問い:
n =19170928580209458018899054265809726
563528784106572713024411968153661
を2つの数に分解しなさい
… これは少々頑張っても無理
54
公開鍵暗号の使い方



ひとりひとりが自分の暗号化関数を公開
( Aさんの関数 = fA(x) )
fA(x) を集めた暗号帳を作成
( 暗号帳 : 電話帳のようなもの )
暗号通信をしたい人は暗号帳を引いて関
数を使う
55
インターネット時代では

ネット上では情報は野ざらし
悪人もつなぎ放題

暗号通信は必須

56
ネット人口は6億人を突破

6億人が古典暗号で通信しようとすると
… 18×1016 = 18京通りの関数が必要

公開鍵暗号なら6億通り

その比は3億分の1 !!!

第一、古典暗号だと変換式
で送らないと !!
f(x) 自体も暗号
57
公開鍵暗号の応用で
次のような技術が実現





電子マネー
電子投票
電子認証
通信上のコイントス
ゼロ知識証明
58
公開鍵暗号のこれから

計算の高速化

ダウンサイジング

セキュリティ向上 etc.
59
暗号のまとめ


暗号 = 情報を第3者には読めないように変換
すること
変換式を公開してしまう公開鍵暗号が誕生
• インターネット時代では必須の技術
• 電子マネー、電子認証など応用技術も多彩
60
Q&A
ご質問、ご意見ありましたら
61
時間が余ったら音楽の話でも
62
ギターのフレームは
同じ比率で並んでいる
比率 = 2 (1/12)
= 1.05946…
63
音がハモる、とは ?
1:2
sin(πx)+sin(2πx)
波長・周波数が
単純な整数比
になること
2
1.5
1
0.5
0
-0.5 0
1
2
3
4
5
6
7
8
9
10
11
12
-1
-1.5
-2
2:3
sin(2πx)+sin(3πx)
2.5
2
1.5
1
0.5
0
-0.5 0
-1
-1.5
-2
-2.5
1
2
3
4
5
6
7
8
9
10
11
12
64
3:4
sin(3πx)+sin(4πx)
2.5
2
1.5
1
0.5
0
-0.5 0
-1
-1.5
-2
-2.5
1
2
3
4
5
6
7
8
9
10
11
音を重ねても
パターンが単純
⇒ 心地よい
12
3:5
sin(3πx)+sin(5πx)
2.5
2
1.5
1
0.5
0
-0.5 0
-1
-1.5
-2
-2.5
1
2
3
4
5
6
7
8
9
10
11
12
65
ハモっていない場合
sin(11πx)+sin(17πx)
2.5
2
1.5
1
0.5
0
-0.5 0
-1
-1.5
-2
-2.5
1
2
3
4
5
6
7
8
9
10
11
12
66
1 オクターブ = 12 音 の理由

r=2
•
•
•
•
•

(1/12)
= 1.05946… とすると
r 3 = 1.189…
r 4 = 1.259…
r 5 = 1.335…
r 7 = 1.498…
r 12 = 2
≒
≒
≒
≒
6/5
5/4
4/3
3/2
ハモる比が全て r で表される
67
和音の周波数比





長調 ド:ミ:ソ = 4:5:6
単調 ラ:ド:ミ = 10:12:15
C7
= 20:25:30:36
Cmaj7
= 8:10:12:15
C6
= 12:15:18:20
68
もし宇宙人がいても

音波でコミュニケーションを取るなら

ハモる現象は同じ

地球人に心地よい音楽は、宇宙人に
とっても心地よいはず ?
69
Q&A
ご質問、ご意見ありましたら
70
ダウンロード

H17年度公開講座資料「安全・確実に情報を伝える」