情報セキュリティ

情報セキュリティ
第２回
現代暗号の基礎数理
脅威と暗号技術
セキュリティに対する脅威
盗聴
（秘密が漏れる）
脅かされる特性
暗号技術
共通鍵暗号
機密性
公開鍵暗号
改竄
（情報が書き換えられる）
正真性
一方向ハッシュ関数
なりすまし
（正しい送信者のふりをする）
認証
メッセージ認証コード
否認
（後から私じゃないと言う）
否認不可能性
デジタル署名
共通鍵暗号系
送信者と同じ
鍵(K)で復号
鍵(K)で暗号化
平文M
送信者
暗号文C
敵
平文M
受信者
暗号アルゴリズムは知っ
ているが鍵は知らない
 共通鍵暗号
ストリーム暗号とブロック暗号
 ビット列
 {0,1}n：長さnのビット列全てから成る集合
 例： 0101は長さ4のビット列
 演算
： mod 2又は、XOR（排他的論理和）
 0 0=0, 0 1=1, 1 0=1, 1 1=0
 (a1,a2,..,an) (b1,b2,..,bn)=(a1 b1, …,an

bn )
ストリーム暗号
 ストリーム暗号
平文M＝（b1,b2,..）、鍵K=（k1,k2,..）
 暗号文＝（b1,b2,..)
(k1,k2,…)
 鍵系列K
 平文毎に鍵系列Kを変えれば安全

例 K=0101
復号
暗号化
鍵K=(k1,k2,..)
平文M=(b1,b2,..)
暗号文C=(c1,c2,..)
ci=bi
例 M=1100
鍵K=(k1,k2,..)
ki
例 C=1001
bi=ci
bi
ki
ci
ki
平文M=(b1,b2,..)
ki = bi
例 M=1100
ブロック暗号
 ブロック暗号
平文Mをブロック毎に分割し、ブロック単位で暗号化
 n：ブロック長（ビット）
 κ：鍵長（ビット）
 米国の標準暗号
長い程安全
 1977年 DES暗号 n=64, κ=56
 2001年 AES暗号 n=128, κ=128, 192, 256
 DESとAES暗号アルゴリズムは公開されている

１ブロック（nビット）
平文m
暗号文c
m=DK(c)
c=EK(m)
暗号化
E
鍵K
復号
D
κビット
１ブロック（nビット）
暗号文c
平文m
敵のモデル
 既知平文攻撃
敵はランダムに与えられ
弱い
た(m1,c1),..,(mk,ck)から
鍵Kなどを求める。
 選択平文攻撃
攻
 敵は平文m1,..,mkを自由
撃
に選び、それらに対する
の
暗号文を入手することが
強
出来る。
さ
 選択暗号文攻撃
 敵は選択平文攻撃に加
え、暗号文c1,..,ckを自由
強い
に選び、それらに対する
平文を入手することが出
来る。

ランダムな平文m1とそ
の暗号文c１の組
敵
(m1,c1),..,(mk,ck)
暗号化
EK
鍵Kなど
選択平文
平文
m1,..,mq
敵
鍵Kなど
暗号文
c1,..,cq
選択平文
平文
暗号化
EK
平文
敵
暗号文
暗号文
鍵Kなど
復号
DK
選択暗号文
疑似ランダム置換
 ランダム置換族Pn

n: ブロック長
{0,1}n（全てのnビット列の集
合）の要素を並び替える置換
πの集合をPnで表す。
 集合Pnの要素数=2n!
 擬似ランダム置換族
 長さκの鍵によって決まる置換
π（暗号化アルゴリズムEK）
の集合をENCnで表す。
 ENCn またはPnからランダム
に選ばれた置換πに対し、選
例えば、解読
択平文攻撃を行う敵が「現実
時間が10億年
的な時間」において、 ENCn と
は現実的な時
Pnを識別出来ないならば、
間でない
ENCn は擬似ランダム置換族。
アルゴリズムが実際に暗号化で使用
する置換πの数は2κ通りしかない。こ
れらを時間をかけずに識別する計算
方法があるならば、このアルゴリズ
ムは悪いアルゴリズムである。
鍵の長さkを増やさないでも、疑似
的にkを大きく見せることが出来る
暗号アルゴリズムを考える。
{0,1}2の場合
00
01
10
11
置換π1（暗号化）
π1
01
10
00
11
π24
置換族P2=
{π1,.., π24}
置換π24（暗号化π1の復号）
2n!通り
Pn
ENCn
平文
敵
π
暗号文
2κ通り
κ：鍵の長さ
置換πをラン
ダムに選択
π∈ENCn ?
or
π∈ Pn ?
置換πがENCnに含
まれるか否をが分
かるまでの時間が
問題
暗号アルゴリズムの置換の数は
非常に少ない： ENCn<<Pn
n=2, k=1の例
P2
π2 ,..,π11, π13 ,..,π24
ENC2
π1, π12
鍵長kのアルゴリズ
ムの置換数2κ
ブロック長nで決
まる置換数2n!
ブロック長nで決ま
n
る関数の数(2n)2
ENCn
Pn
Rn
n=2,k=1
2
24
256
n=5,k=5
25≑101.5
25! ≑1035
1048
DES暗号 n=64 k=54
254≑1016.8
264! ≑(10)10
AES暗号 n=128 k=128
2128≑1038.4
2128! ≑(10)10
スターリングの公式： n! ≑ (2πn)1/2nne-n
210=1024 ≑ 103 e7=1096.63 ≑ 103
1040/3ビットの
平文まで情報
理論的に安全
20
(264)2
64
39
(2128)2
128
観測可能な宇宙の全原子数は、
1079から1081と推定されている。
ランダム関数族
n=2の場合
 ランダム関数族Rn



集合{0,1}nから集合{0,1}nへ
の全ての関数の集合Rnを長
さｎのランダム関数族という。
選択平文攻撃を行う敵がFn
(Rnの部分集合)とRnを識別
出来ないならば、Fn は擬似
ランダム関数族と呼ばれる。
Pn は擬似ランダム関数族で
ある。
1対1対応
N対1含む
Rn
置換（暗号化）は１対１
00
01
10
11
00
01
10
11
関数はN対１を含む
00
01
10
11
４対１
00
01
10
11
Pn
ENCn
置換π1
２対１
00
01
10
11
00
01
10
11
利用モード
 利用モード
ECBモード
ブロック長ｎよりも長い平文
平文=(m1,
…
mt)
M=(m1,..,mt)を暗号化する
モード。但し、 miの長さ（|mi|）
置換
はn。
…
EK
EK
 ECBモード
 暗号化 c1=EK(m1),..,
暗号文=(c1,
…
ct)
ct=EK(mt)
 復号 m1=DK(c1),..,
並列処理
mt=DK(ct)
関数は置換よりも数が多い
が可能
 カウンタモード
カウンタモード
 暗号化
ctr
ctr+1 関数
ctr+t
c1=m1 EK(ctr+1),..,
ct=mt EK(ctr+t)
復号もEK
…
EK
EK
 復号
m1=c1 EK(ctr+1),..,
m1
mt
mt=ct EK(ctr+t)

暗号文=(ctr,
ct
EK(ctr+t)=mt
=mt
EK(ctr+t)
EK(ctr+t)
c 1,
…
c t)
利用モード
メッセージ認証コード
で使われる
 CBCモード
 暗号化
ci+1=EK(ci mi+1)
 復号
mi+1=DK(ci+1) ci
 CFBモード
 暗号化
ci+1=mi+1
 復号
mi+1=ci+1
EK(ci)
CBCモード
IV
m1
m2 …
mt
EK
EK
EK
c1 ,
c2, …
ct)
毎回初期
値を変える
暗号文=(IV,
CFBモード
IV
復号もEK
EK(ci)
関数
EK
m1
暗号文=(IV,
EK
EK
c1,
mt
m2
c2 , …
ct)
利用モード
 OFBモード
暗号化
zi+1=EK(zi),
ci+1=mi+1 zi+1
復号もEK
 復号
zi+1=EK(zi),
mi+1=ci+1 zi+1
 安全性
 ｛EK｝が擬似ランダム
置換族ならば、ECB
以外は選択平文攻
撃に安全

OFBモード
IV
暗号文=(IV,
関数
EK
EK
m1
c1,
m2
c2 , …
EK
mt
ct)

Download Report