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

q
q
情報セキュリティ
第8回:2005年6月3日(金)
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
ディジタル署名の方法1(1)

署名文復元法
教科書Fig.9-2(p.214)の,より適切な図
プライベート鍵で署名した署名文は
対応する公開鍵でのみ正しく検証できる
メッセージ
(署名文の検証)
(ディジタル署名)
(署名文の作成)
公開鍵で
復元
署名文
プライベート
鍵で署名
公開鍵
公開鍵ペア
メッセージ
プライベート
鍵
11
ディジタル署名の方法1(2)

教科書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
ディジタル署名の方法2

認証子照合法
教科書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
ディジタル署名の方法3

これも,認証子照合法
教科書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 と1対1に対応する.すなわち,N×Nの各要素を順に漏れ
なく列挙可能.
そこで,N×Nの要素(a,b)を順に漏れなく取り出し,
ビット列の系列のa番目の要素xおよびb番目の要素yに対して,
x≠y かつ h(x)=h(y)であるかを評価すればよい.
計算できる?
q
q
計算理論としては,これも帰納的可算.
実用上は,ビット列x,yをランダムに生成するほうが簡便.
19