情報セキュリティ: 2005年6月3日

q
q
情報セキュリティ
第８回：２００５年６月３日（金）
q
q
本日学ぶこと

メッセージ認証
q
q
q
q
一方向ハッシュ関数
メッセージ認証コード
ディジタル署名（デジタル署名）
いずれも，正真性・完全性に関する技術
2
機密性・正真性と暗号技術
機密性
正真性（完全性）
鍵なし
アルゴリズム秘匿
による暗号
一方向ハッシュ関数
共通鍵
対称暗号
メッセージ認証コード
非対称鍵
公開鍵暗号
ディジタル署名
3
一方向ハッシュ関数：準備

表記
q
q
q

h : ハッシュ関数
m, n, x : メッセージ（ハッシュ関数の入力）
h(m), h(n), h(x) : ハッシュ値（ハッシュ関数の出力）
メッセージとハッシュ値について
q
q
メッセージ空間は一般に無限集合
ハッシュ値空間は有限集合
 ビット長を固定とすることが多い
 SHA1なら，160ビットのビット列なので，
ハッシュ値空間の大きさは 2160
4
一方向性とは

任意のメッセージmに対してh(m)を計算するのは容易である
が，任意に与えられたh(m)から，mを求めることができない．
q
集合 Hm={x | h(x)=h(m)} を求めることは原理的に可能である
が，無限集合かもしれないし，mそのものを求めることは不可能．
Hmの要素を一つ求めることは，弱衝突耐性に関する話．
メッセージ
空間
Hm= {x | h(x)=h(m)}
m
hとh(m)によって
決まる集合
ハッシュ値
空間
h(m)
5
弱衝突耐性とは

与えられたh(m)から，h(m)=h(n)を満たすメッセージnを求め
ることができない．
q
q
m=nか否かは問わない．
原理的に求めることができるので，実用上は「計算量的に困
難」であることを示せばよい．
6
弱衝突耐性を破る攻撃（教科書pp.184-186）
Hm= {x | h(x)=h(m)}
m:百万円契約書
（アリス作成）
メッセージ
空間
一億円契約書
（マロリー作成，たくさん）
マロリーが目標とする
一億円契約書
n
ハッシュ値
空間
h(m)=h(n)
7
強衝突耐性とは

m≠nかつh(m)=h(n)を満たすメッセージm,nを求めることがで
きない．
q
hが単射でなければ，原理的に求めることができるので，実用
上は「計算量的に困難」であることを示せばよい．
 hが単射 ⇔ Hm={m}
 通常使う一方向ハッシュ関数では，メッセージ空間（の部分
集合）はハッシュ値空間よりも大きいので，単射とならない．
8
強衝突耐性を破る攻撃（教科書pp.186-188）
メッセージ
空間
百万円契約書
（マロリー作成，たくさん）
一億円契約書
（マロリー作成，たくさん）
m,n：マロリーが目標と
する契約書
ハッシュ値
空間
h(m)=h(n)
9
公開鍵暗号とディジタル署名の数式表現

RSA暗号方式
q
q

RSAディジタル署名方式
q
q

暗号化：C = Enc(pub, M) = ME mod N
復号：M = Dec(pri, C) = CD mod N
署名：S = Sign(pri, M) = MD mod N
検証：M = Ver(pub, S) = SE mod N
RSAでは，暗号化も復号も署名も検証も「メッセージをべき
乗して剰余を求める」
q
ElGamalなど，他の暗号アルゴリズムでは必ずしも成立しない．
10
ディジタル署名の方法１（１）

署名文復元法
教科書Fig.9-2（p.214）の，より適切な図
プライベート鍵で署名した署名文は
対応する公開鍵でのみ正しく検証できる
メッセージ
（署名文の検証）
（ディジタル署名）
（署名文の作成）
公開鍵で
復元
署名文
プライベート
鍵で署名
公開鍵
公開鍵ペア
メッセージ
プライベート
鍵
11
ディジタル署名の方法１（２）

教科書Fig.9-2（p.214）に数式を当てはめる
M'
（署名文の検証）
（ディジタル署名）
（署名文の作成）
Verify
S
Sign
pub
公開鍵ペア
M
pri
S = Sign(pri, M)
M' = Verify(pub, S) = Verify(pub, Sign(pri, M))
12
ディジタル署名をどう活用する？


復元の結果，意味のあるメッセージが得られたら，この署名
文は適切な鍵で署名されたと判断する． ⇒ 署名文復元法
復元の結果と，公開もしくは送信されたメッセージとを照合し，
同じ内容ならば，この署名文は適切な鍵で署名されたと判断
する． ⇒ 認証子照合法
q

認証子照合法では，メッセージはランダムな値でもよい．
「署名文の送信者はプライベート鍵（秘密鍵）を所有してい
る」と考えてはいけない．
q
再生攻撃の可能性あり！
13
ディジタル署名の方法２

認証子照合法
教科書Fig.9-5（p.217）に数式を当てはめる
M
pri
M
等しくなかった
ら，
Sign

S
S

pub
Verify
M'


適切なプライ
ベート鍵で署名
されていない
通信路中で改
ざんが起こった
M' = M?
S = Sign(pri, M)
M' = Verify(pub, S)
= Verify(pub, Sign(pri, M))
14
ディジタル署名の方法３

これも，認証子照合法
教科書Fig.9-6（p.219）に数式を当てはめる
M
M
h
h
等しくなかった
ら，

S
h(M)
h(M)

pri
Sign
S


pub
Verify
M'
適切なプライ
ベート鍵で署名
されていない
通信路中で改
ざんが起こった
M' = h(M)?
S = Sign(pri, h(M))
M' = Verify(pub, S)
= Verify(pub, Sign(pri, h(M)))
15
以下余談

知ってほしいこと
q
q
無限集合といっても，一般にその各要素は「有限の長さで記述
できる」こと
解を求めることが「原理的に可能」な実例
 「原理的に可能」と言うときはたいてい，「現実的には困難」と
続く．
16
ビット列が無限集合であるとは
0, 1, 00, 01, 10, 11, 100, 101, …
1ビット
2ビット
3ビット
…
とビット列を並べることで
q
q
q
重複なくビット列を列挙できる．
 この系列のx番目のビット列を求めることができる．
 ビット列mが，この系列の何番目にあるかを求めることも
できる．
この系列はいくらでも書くことができる． ⇒ 無限集合
しかしこの系列に出現するどの要素も，長さ有限のビット列
である．
17
一方向性・弱衝突耐性の破り方



入力：ハッシュ関数h，ハッシュ値M = h(m)
出力：集合 {x | h(x) = M}，またはその要素の一つ
方針
q
q

ビット列の（無限）系列の各要素を小さいものから順に取り出し
（xとする），h(x) を求め，それが M と等しいか判定する．
等しければ，その x を出力する．（一つだけでいいなら，ここで
終了）
計算できる？
q
q
計算理論では，「帰納的可算」と呼ばれる（ただし「帰納的」では
ない）．
一方向ハッシュ関数では，終了するまでの時間はハッシュ値空
間に比例するので，この空間を大きくすればよい．
18
強衝突耐性の破り方



入力：ハッシュ関数h
出力：集合 {x,y | x≠y, h(x)=h(y)}，またはその要素の一つ
方針
q
q

自然数の集合をNと書くとき，N×N = {(a,b) | a∈N, b∈N} は
N と１対１に対応する．すなわち，N×Nの各要素を順に漏れ
なく列挙可能．
そこで，N×Nの要素(a,b)を順に漏れなく取り出し，
ビット列の系列のa番目の要素xおよびb番目の要素yに対して，
x≠y かつ h(x)=h(y)であるかを評価すればよい．
計算できる？
q
q
計算理論としては，これも帰納的可算．
実用上は，ビット列x,yをランダムに生成するほうが簡便．
19

Download Report