前回の練習問題
以下に示す換字暗号の暗号文を解読せよ
（ただし，アルファベット以外の記号は換字していない）
usawlu rcunsac bsaelrsn fhs blyan emt fylthx fl wlmfh cqyvec lu
fhmywncx, uscyax wvg xscyw cqfsy fhs qlyrsy qyssnlr qvdhfsy
cun ucfvluca ascnsy eyvsn fscyw lq ilx bhsu fhs flmyucrsuf bcw
cbcynsn fl fhs elufvusuf qly fhs qvywf fvrs.
bvfh fhvyfx qvks ncxw zsqlys fhs wleesy whlbtvses oveow lqq vu
ilhcuuswzmyd, fhs fylthx fhcf fhvyfx fbl fscrw cys hltvud fl avqf
elrs imax sasksufh vw czlmf fl srzcyo lu fhs qvuca asd lq vfw
blyan flmy.
1
前回の練習問題の解答
実験用プログラム （JAVAアプレット）：
http://narayama.naist.jp/~kaji/crypto/index.html
Nelson Mandela welcomed the World Cup trophy to South Africa
on Thursday, nearly six years after the former freedom fighter and
national leader cried tears of joy when the tournament was awarded
to the continent for the first time.
With thirty five days before the soccer showpiece kicks off in
Johannesburg, the trophy that thirty two teams are hoping to lift
come July eleventh is about to embark on the final leg of its world
tour.
2
本日の講義
暗号の使用モード
暗号を，より安全に利用するための「使い方」について
鍵共有プロトコル
鍵の事前共有には，どんな解決法があるか
公開鍵暗号系の概要
鍵の事前共有が必要ない暗号方式について
今回はイントロ的内容，詳細は次回講義にて
3
暗号の使用モード
DESやAES：
単純に，暗号文から平文を推測するのは十分に困難
同じ鍵で同じ平文を暗号化すると，同じ暗号文になる
平文の統計的性質が暗号文にも出現する
原理的には，換字暗号に対する頻度攻撃と同じことが可能
暗号化装置の使い方を一工夫．．．
うまくやれば，平文の統計的性質を隠蔽できる
暗号化装置の使い方 ＝ 暗号の使用モード
4
ECBモード
ECB (Electric CodeBook) モード
もっとも単純な暗号化装置の使い方
平文 P1
P2
P3
E
E
E
暗号文 C1
C2
C3
E ：暗号化操作
（鍵は省略）
同一の平文は，常に同一の暗号文になる
5
CBCモード
CBC (Cipher Block Chaining) モード
直前に作った暗号文を，次の平文に「足す」
平文 P1
P2
P3
E
E
E
暗号文 C1
C2
C3
先頭から完全に同一の平文は，いつも同じ暗号文になる
平文中の同一パターンは，暗号文では異なるパターンに
6
CBCモードの復号
P1
P2
P3 暗号化
C1
C2
C3
E
E
E
D
D
D
C1
C2
C3
P1
P2
P3
復号
復号結果から，直前の暗号文を引けば良い
暗号文に誤りが発生すると．．．
誤り発生ブロックの復号に失敗
次のブロックの復号も失敗する
その次のブロックは無事
7
CFBモード
CFB (Cipher FeedBack) モード
直前に作った暗号文を，暗号化して次の平文に「足す」
足した結果が暗号文
平文 P1
P2
E
暗号文 C1
P3
E
C2
E
C3
先頭ブロックは「捨石」...Initial Vector (IV)とも呼ばれる
IVを変えると，同じ平文も違った暗号文に
8
CFBモードの復号
P1
P2
E
C1
暗号化
C1
E
C2
C2
E
P1
復号
E
P2
直前の暗号文を，暗号化して引く
暗号文に誤りが発生すると．．．
誤り発生ブロックの復号に失敗
次のブロックの復号も失敗する
その次のブロックは無事
9
OFBモード
OFB (Output FeedBack) モード
先頭のブロック (IV) を使って，内部的な攪拌情報を作る
攪拌情報を平文に足したものが暗号文
平文 P1
P2
E
暗号文 C1
P3
E
C2
C3
IVのブロックを変えると，同じ平文も違った暗号文に
10
OFBモードの復号
E
C1
P3
C1
E
C2
C2
E
C3
P1
C3
復号
P2
暗号化
P1
E
P2
P3
暗号化とまったく同じ手順で復号できる
暗号文に誤りが発生すると．．．
誤り発生ブロックの復号に失敗
次のブロックは無事
11
各モードの比較
ECB
CBC
CFB
OFB
非再現性
誤り耐性
並列化
頑強性
×
○
○/○
○
△
×
×/○
○
○
×
×/○
×
○
○
△/△
×
非再現性：平文の同一パターンが，暗号文で観測されないこと
誤り耐性：暗号文に誤りが発生しても，後に影響しないこと
並列化：並列に暗号化/復号が行えること
頑強性：暗号文の改変により，平文の操作ができないこと
12
鍵共有プロトコル
13
鍵共有の問題
ここまで考えてきた暗号方式：
暗号化に使う鍵と，復号に使う鍵が同じ
⇒共通鍵暗号，対称鍵暗号
(symmetric cryptography)
共通鍵暗号を使うための大前提：
暗号文の送り手と受け手が，同じ鍵を共有していること
共有している鍵は，他者には知られていないこと
どうやって鍵の共有を行うのか？
14
鍵共有の方法
どうやって鍵の共有を行うのか？
「安全な通信路」を利用して鍵を配送する
エージェント，工作員，伝書鳩，郵便 etc...
通常の通信コストよりも，かなり割高で時間もかかる
「鍵共有プロトコル」を実行する
通信プロトコルの一種
通常の通信路を使って鍵共有が可能
15
鍵共有プロトコル
鍵共有（key agreement, key sharing）プロトコルとは．．．
２人のユーザ間の通信手順
両ユーザがメッセージの交換（やりとり）を行う
メッセージ交換が終了したとき，
両ユーザは，共通の情報を共有できる
通信路を盗聴していても，共有情報はわからない
16
Diffie-Hellman鍵共有方式
Diffie と Hellman の考えた鍵共有方式
離散対数問題の難しさに依存した方式
準備：
Fq を，位数 q の有限体とする
(q が素数のとき，Fq={0, 1, ..., q – 1})
g を，Fq の生成元とする
Fq の任意の元 a (≠0) は，a = gx mod q と表現される
離散対数問題：
「与えられた Fq, a, g から，a = gx mod q となる x
(x は a の対数に相当する）を求める問題」
17
簡単な数値例
F7 = {0, 1, 2, ..., 6}
g = 3 は生成元：任意の非零元は，g のべき乗として表現可能
離散対数問題の「答え」
1 = 36 mod 7
2 = 32 mod 7
3 = 31 mod 7
4 = 34 mod 7
5 = 35 mod 7
6 = 33 mod 7
log3 1 = 6
log3 2 = 2
log3 3 = 1
log3 4 = 4
log3 5 = 5
log3 6 = 3
6
5
4
3
2
1
x
a
0 1 2 3 4 5 6
q （上例では 7） が大きいとき．．．
離散対数問題を解くことは，非常に難しいと考えられている
18
Diffie-Hellman方式の手順
ユーザA, B間で情報を共有したい
通信路の情報は，盗聴されている可能性がある
ただし，通信路上の情報の改変はないと仮定する
Diffie-Hellman (DH) 法の手順：
1. 使用する Fq, g について，A, B間で合意する（公開可）
2. A は乱数 x を選定し，mA = gx mod q を B に送る
3. B は乱数 y を選定し，mB = gy mod q を A に送る
4. Aは (mB)x ≡ gxy mod q を計算する
5. Bは (mA)y ≡ gxy mod q を計算する
19
DH法の計算手順
Fq, g を合意
x
mA = gx mod q
mB = gy mod q
gxy mod q
y
gxy mod q
盗聴者：Fq, g, gx, gy を入手可能
離散対数問題を解かない限り x, y は計算できない
⇒ gxy も計算できない
20
DH法の計算例
F197, g=3
51
71=351 mod 197
38=355 mod 197
122=3851 mod 197
55
122=7155 mod 197
21
DH法の安全性
盗聴者が離散対数問題を解けない限り，安全
通信路上の情報改変が可能な場合，安全性に問題あり
man-in-the-middle attack, 中間一致攻撃
より安全な方式はないのか ⇒ 公開鍵暗号系
22
公開鍵暗号系の概要
23
対称鍵暗号
対称鍵暗号（共通鍵―, symmetric―, secret key―, classic―）
平文の暗号化に使う鍵 ＝ 暗号文の復号に使う鍵
暗号化も復号も，鍵を知っている者だけが可能
通信に先立ち，送受信者が鍵を共有する必要あり
秘密に事前共有
A
暗号化
B
復号
24
対称鍵暗号の特徴
（公開鍵暗号に比べ）軽快な暗号である
実装にかかるコストが小さくて済む
回路面積，消費電力も小さい
高速動作が可能
多くのバリエーションが存在
鍵の秘密事前共有が必要となる
他者にバレないよう，鍵を配送・保管する仕組みが必須
（ＤＨ法も万能ではない）
25
公開鍵暗号系とは
暗号化に使う鍵と，復号に使う鍵が異なる暗号方式
暗号化鍵を見ただけでは，復号鍵が何かわからない
通常，暗号化鍵は広く公開される（誰でも暗号化ができる）
事前に配送
A
秘密にしなくて良い
暗号化
B
復号
共通鍵暗号は「金庫」
モノを入れるにも出すにも，鍵が必要
公開鍵暗号は「郵便ポスト」
誰でも投函できる
モノを出せるのは，鍵を持つ人だけ
26
公開鍵暗号の運用法
公開鍵暗号の典型的な運用方法
一人のユーザが一組の鍵（暗号化鍵，復号鍵）を生成
暗号化鍵を公開：誰でも暗号化操作が可能
復号鍵を秘密に保持：
暗号文を復号できるのは（鍵を生成した）一人だけ
ユーザＡに暗号文を送りたい場合
1. 公開されているＡの暗号化鍵を入手
2. Ａの暗号化鍵を使って平文から暗号文を構成
3. 暗号文をＡに送る
4. Ａは復号鍵を使って平文を復元
27
公開鍵暗号を使った秘密通信
ユーザA
復号鍵
skA
A
B
暗号化鍵
pkA
pkA
pkB
:
公開鍵帳
鍵のペアを生成し．．．
pkAのみ公開
skAは秘密に管理
誰でも暗号文を作ることは可能
他人が作った暗号文は復号できない
28
RSA暗号
Rivest, Shamir, Adelman が提案した公開鍵暗号
整数の掛算と割算により，暗号関連の操作を行う
素因数分解を解くことの難しさに，安全性の根拠を置く
暗号化の鍵：２つの整数 e と n
c = me mod n を暗号文とする
復号の鍵：２つの整数 d と n
m = cd mod n を復号結果とする
Shamir Rivest Adelman
十分な強度を確保するには，鍵は数百桁の大きさが必要
29
RSA暗号の一例
平文は，１から492の整数として表現する
暗号化操作：
平文を3乗して，493で割った余りを暗号文とする
平文が m = 68 の場合
683 = 314432 = 637・493 + 391，暗号文は391
平文が m = 283 の場合
2833 = 22665187 = 45974・493 + 5，暗号文は5
暗号文を解読できますか？
復号鍵は何になるでしょうか？
30
前例のRSA暗号について
暗号化操作：
平文を3乗して，493で割った余りを暗号文とする
復号操作：
暗号文を299乗して，493で割った余りを復号結果とする
当然沸いてくる疑問：
本当に，いつも正しく復号できるの？
3や493と299との関係は？
大きな数字の計算はどうするの？
...つづく
31
本日のまとめと練習問題
暗号の使用モード
鍵共有プロトコル
公開鍵暗号系の概要
練習問題
F29 = {0, 2,…, 28}において，g = 11 が生成元である
ことを確かめよ．また，p.18 の右下の図のように，
F29 の元とその離散対数との関係を図示せよ．
32
テストについて
テスト：６月３日（木）１限，Ｌ１講義室
範囲は，本講義内容全体（レポート出題以前の部分も含む）
持ち込みＯＫ（本，資料，電卓，パソコン）
ただし，通信機能の使用不可
試験日に都合の悪い人は，[email protected] まで連絡を．
木曜の講義終了後，レポートの解答例を講義ホームページに
掲載します．以降のレポート提出は受け付けません．
final exam. on June 3 (Thu) 9:20AM-, in this class room
see the note of this PPT file for the details
33
© Copyright 2024 ExpyDoc
