情報セキュリティ: 2007年5月11日

q
q
情報セキュリティ
第４回：２００７年５月１１日（金）
q
q
本日学ぶこと









使い捨てパッド
ＤＥＳ (Data Encryption Standard)
ＡＥＳ (Advanced Encryption Standard)
ブロック暗号のモード
使い捨てパッドは無条件に安全だが，非実用的
対称暗号成功の秘訣は，排他的論理和（）
DESのファイステル構造は，暗号化と復号が同じ構造
AESは，コンペ方式による標準化で選定された
対称暗号を使いたいなら，AES
2
（復習）暗号系
平文
暗号化
平文
暗号
化鍵
復号
鍵
復号
盗聴可能な
通信路
暗号文
暗号文
3
（復習）単一換字暗号
平文
平文
abc...
WYH...
暗号化
暗号
化鍵
復号
鍵
復号
WYH...
abc...
暗号文
暗号文
4
使い捨てパッド
平文
10101 暗号
化鍵
復号 10101
鍵
暗号文
復号
01001
01001
暗号化
11100
11100
平文
01001
暗号文
5
使い捨てパッドの暗号アルゴリズム



平文： M = m1m2m3…
鍵： K = k1k2k3…
暗号化： C = c1c2c3…
ただし，ci = ki  mi
q

ビット単位で，鍵と平文の排他的論理和を求める．
復号：M' = m'1m'2m'3 …
ただし， m'i = ki  ci = ki  (ki  mi) = ki  ki  mi =
(ki  ki)  mi = 0  mi = mi
q

送受信者の間で
共有しておく．
mi, ki, ci, m'iは
1ビット
ビット単位で，鍵と暗号文の排他的論理和を求める．
Vernamによって1917年に考案され，特許になった．
「バーナム暗号」とも呼ばれる．
6
排他的論理和の性質





xy=yx
xx=0
x
y
xy
1
1
0
0
1
1
1
0
1
0
0
0
排他的論理和の
真理値表
xを平文，yを鍵とみなすと，
この式は，使い捨てパッドにおける
暗号化と復号の関係を表す．
xyy=x
x=y ⇒ xz=yz
z = x  y ⇒ x = z  y, y = x  z
7
使い捨てパッドは解読不可能

暗号文のみでは，同じ長さの任意のビット列が平文の候補と
なり，そこから平文を特定できない．
q


無条件に安全であり，情報理論的に解読不可能
（比較）実用化されている暗号アルゴリズムは，計算量的に解
読不可能
既知平文攻撃や選択平文攻撃を用いれば，暗号化に使用し
たビット列を求めることができる．
q c = k  m ⇒ k = c  m
しかしこれで求めた k は，(平文,暗号文)=(m,c)という暗号化
の鍵としてしか使えない．
q
k を知っても，それ以外の秘密通信の復号・解読には役に立た
ない．
8
鍵をどのようにして共有する？

事前にビット列を共有しておき，暗号化・復号のたびに，使用
したビット列に線を引いて消す．
10110101
11110010
01101011

10110101
11110010
01101011
暗号化する側がビット列を生成し，暗号文と別のルートで秘
密に送る．
暗号化鍵
復号鍵
9
使い捨てパッドは非現実的

平文と同じ長さの鍵が必要
q

鍵の共有（配送）が難しい
q

秘密の通信路があるのなら，そこにメッセージを送れば？
鍵は「使い捨て」でなければならない
q

平文が1GBなら，鍵も1GB
再利用すると，過去の通信内容が復号できてしまう．
鍵は真の乱数であり，かつ共有しなければならない
q
計算機が生成できるのは，擬似乱数か，再現性のない（物理ノ
イズによる）乱数のいずれか．
10
使い捨てパッドから学ぶこと

排他的論理和は，「2度適用すると，元に戻る」ので，暗号化
や復号の処理に適している．
q
ストリーム暗号
暗号
化鍵
擬似乱数
平文
q
暗号文
DES，AESなどの対称暗号でも活用
11
現代の対称暗号

DES (Data Encryption Standard)
q
q
q
q

１９７７年に連邦情報処理標準規格に採用された対称暗号
鍵長64bit，ブロック長64bit
ファイステル構造により安全性を高める
「兵器」とみなされ，かつて輸出規制があった
AES (Advanced Encryption Standard)
q
q
q
q
q
Rijndaelともいう
NISTが公募して２０００年に選定された対称暗号
鍵長128/192/256 bit，ブロック長128bit
SPN構造により安全性と処理効率を実現
特許などの制限がなく無料で利用可能
12
ＤＥＳとＡＥＳに関わる組織と考案者
NSA
NBS
選定
修正
Lucifer
応募
IBM
（Feistel他）



改組
DES
NIST
米国
当局
選定
Rijndael
AES
暗号
方式
応募
Daemen &
Rijmen
考案者
ＮＳＡ：米国安全保障局，National Security Agency
ＮＢＳ：米国商務省標準局，National Bureau of Standards
ＮＩＳＴ：米国国立標準技術研究所
13
DESの概要

暗号化
平文

鍵
転置
復号
暗号文
転置
ラウンド１
サブ鍵１
ラウンド２
サブ鍵２
ラウンド１６
サブ鍵１６
ラウンド１６
ラウンド２
ラウンド１
転置
転置
暗号文
平文
14
ファイステル構造（暗号化１）
Li-1
ki
Ri-1
f
Li

Ri
i 番目のラウンド（DESでは1≦i＜16）
q
q
Li = Ri-1
Ri = Li-1  f (ki , Ri-1)
15
ファイステル構造（暗号化２）
Li-1
ki
Ri-1
f
Li

Ri
最終ラウンド（DESではi=16）
q
q
Li = Li-1  f (ki , Ri-1)
Ri = Ri-1
16
ファイステル構造（復号１）
Li
Ri
ki
f
Li-1

Ri-1
i 番目のラウンド（DESでは1≦i＜16）
q
q
Ri-1 = Li
Li-1 = Ri  f (ki , Li ) = Ri  f (ki , Ri-1)
17
DESとAESの安全性は？

DES
q
q
q
q

70～80年代は安全な対称暗号として使用されていた．
1993年，線形解読法が提案される．
1999年には22時間で解読（鍵発見）．
現在では使用は推奨されない．
AES
q
q
q
コンペ方式による標準化（専門家らによる十分な期間の検証）
により安全性が認められた．
数学的構造を持つ（数式で記述できる）ことが安全性を脅かす
かもしれない（ただし現時点で具体的な攻撃方法はない）．
ラウンド数が少ない場合の解読の試みがなされている．
18
トリプルDES (3DES)

DES-EDE3
q
q

暗号アルゴリズムは，「鍵1でDES暗号化」して，「鍵2でDES復
号」して，「鍵3でDES暗号化」
鍵長は56×3=168bit（鍵空間は2168），ブロック長は64bit
DES-EDE2
q
q
長さは3倍だが，空間は3倍
よりもうんと大きい
暗号アルゴリズムは，「鍵1でDES暗号化」して，「鍵2でDES復
号」して，「鍵1でDES暗号化」
鍵長は56×2=112bit，ブロック長は64bit
19
暗号アルゴリズム設計者の苦悩


暗号化や復号が高速にできると，解読も高速にできてしまう
かもしれない．
処理速度が，暗号化＜復号というアルゴリズムは？
q
q
圧縮ソフトウェアでは圧縮＜伸張のことが多い．
暗号化＜復号のアルゴリズムを考案すると，構造が複雑になり，
思わぬところから欠陥が見つかるかもしれない．
20
ブロック暗号のモード

平文・暗号文のブロック化
q
q

ブロック長のサイズで分割して，暗号アルゴリズムを適用する
ブロック長に満たなければ，詰め物を加える（パディング）
複数ブロックの暗号化の方法
q
q
ECB (Electric CodeBook)モード…安全でない
 Ci = E(K, Mi)
CBC (Cipher Block Chaining)モード…安全
 Ci = E(K, (Ci-1 Mi))
C0は初期ベクトル（盗聴されてもよい）
CTR (CounTeR)モード…安全
 Ci = E(K, CTR + i)  Mi
 CTRは乱数（盗聴されてもよい）

q
Ci, Mi, CTRは
1ブロック
21
ECBモードはなぜ安全でないか


ECBモードのブロック暗号を盗聴していて，過去とまったく
同じ（暗号化された）ブロックがくれば，この二つのブロック
の平文は同じだと分かる．
１パスワード＝１ブロックで暗号化して管理しているとき，
暗号化ブロックを置き換えることで，他人のパスワードを改
ざんし，成りすまして認証を受けることができてしまう．
22

Download Report