黒澤 馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 情報セキュリティ特論（1） 黒澤　馨 （茨城大学） kurosawa@mx.ibaraki.ac.jp 2018/12/8 confidential

教科書・参考書 現代暗号への招待： 黒澤 馨 (著), サイエンス社 現代暗号の基礎数理 黒澤馨、尾形わかは（著） 　　　現代暗号への招待： 　　　　黒澤 馨 (著), 　　　　サイエンス社 現代暗号の基礎数理 　　　　黒澤馨、尾形わかは（著） 　　　　電子情報通信学会編（コロナ社） 2018/12/8 confidential

講義内容 暗号の歴史 確率 メッセージ認証コード 2018/12/8 confidential

暗号の歴史 シーザー暗号から公開鍵暗号まで 2018/12/8 confidential

暗号 従来： 　　軍事・外交 現在： 　　ビジネス、個人のプライバシ 2018/12/8 confidential

シーザー暗号（１） （平文）　　Ｈ　 Ａ 　Ｌ 　　　　　　　↓　↓　↓ （暗号文）　Ｉ Ｂ Ｍ 2018/12/8 confidential

シーザー暗号（2） アルゴリズム 　　何文字かずらすという手順 鍵 　　ずらす文字数 2018/12/8 confidential

外交と暗号 ワシントン軍縮交渉（１９２１年） 軍艦保有数の英米と日本の比率 日本の主張 １０：７ 譲歩の用意 １０：６ 　　軍艦保有数の英米と日本の比率 日本の主張　１０：７ 譲歩の用意　１０：６ 　（暗号解読で知られていた） 2018/12/8 confidential

紫暗号（旧海軍） 解読するのは至難のわざ 米の天才フリードマンらが成功 ミッドウェイ海戦に圧勝 山本五十六大将の戦死 2018/12/8 　　ミッドウェイ海戦に圧勝 　　山本五十六大将の戦死 2018/12/8 confidential

エニグマ暗号（ドイツ) 解読するのは至難のわざ 英の天才チューリングらが成功 Ｕボートの被害減少 2018/12/8 　　Ｕボートの被害減少 2018/12/8 confidential

天才チューリング チューリング賞 チューリング機械 　　計算可能とは何か 2018/12/8 confidential

世界初のコンピュータ コロッサス（英、１９４３年） エニグマ暗号の解読 戦後、処分 設計図も焼却処分 厳重な緘口令 2018/12/8 　　エニグマ暗号の解読 戦後、処分 　　設計図も焼却処分 　　厳重な緘口令 2018/12/8 confidential

栄誉はエニアックへ １９４５年 米ペンシルバニア大学の エッカートとモークリー １８，０００本の真空管 毎秒５，０００回の計算 　　米ペンシルバニア大学の 　　エッカートとモークリー １８，０００本の真空管 毎秒５，０００回の計算 2018/12/8 confidential

アメリカでは ウィーナー 砲弾を命中させるために 計算機の製作を言上 ノイマン プログラム内蔵を提唱 シャノン 情報理論 2018/12/8 　　砲弾を命中させるために 　　計算機の製作を言上 ノイマン 　　プログラム内蔵を提唱 シャノン 　　情報理論 2018/12/8 confidential

発熱しない真空管を作れ １９４７年 トランジスタ ブラッテン バーディン ショックレー １９５４年 パラメトロン 後藤英一 １９４７年　トランジスタ 　　ブラッテン 　　バーディン 　　ショックレー １９５４年　パラメトロン 　　後藤英一 2018/12/8 confidential

戦後の暗号 計算機を利用した解読 計算機を利用した製作 計算機を所有していたのは 政府機関と軍関係のみ 2018/12/8 　政府機関と軍関係のみ 2018/12/8 confidential

１９６０年代 計算機の性能向上 一般企業も所有し、 暗号を送金や商取引に 標準化の要望 2018/12/8 confidential

ＤＥＳ暗号 １９７６年 米国標準暗号に制定 アルゴリズムは公開 鍵のみ秘密 平文＝６４ビット 暗号文＝６４ビット 鍵長＝５６ビット 　　米国標準暗号に制定 アルゴリズムは公開 　鍵のみ秘密 　　　平文＝６４ビット 　　　暗号文＝６４ビット 　　　鍵長＝５６ビット 2018/12/8 confidential

Ｄｅｅｐ　Ｃｒａｃｋ １９９９年 　ＤＥＳ暗号を２２時間で破る 製作費用 　　わずか２５万ドル 2018/12/8 confidential

ＡＥＳ暗号 次期暗号をコンテストで募る Ｒｉｊｎｄａｅｌに決定（２００１年） 平文 １２８ビット 暗号文 １２８ビット 　平文　　１２８ビット 　暗号文　１２８ビット 　鍵長　　１２８、１９４、２５６ビット 2018/12/8 confidential

共通鍵暗号の弱点 送信者と受信者が鍵を共有 どうやって鍵を配送するか ？ スーツケースに入れて運ぶ 手間と費用が大変 2018/12/8 どうやって鍵を配送するか　？ 　スーツケースに入れて運ぶ 　手間と費用が大変 2018/12/8 confidential

公開鍵暗号の登場 暗号化鍵ｐｋを公開 ！！ 復号鍵ｓｋのみを秘密 ただし、 ｐｋからｓｋを求めることは困難 2018/12/8 暗号化鍵ｐｋを公開　！！ 復号鍵ｓｋのみを秘密 ただし、 　ｐｋからｓｋを求めることは困難 2018/12/8 confidential

ＤＨとＲＳＡ １９７６年 　　Diffie and Hellman が概念 １９７７年 ＲＳＡ暗号 2018/12/8 confidential

英のＧＣＨＱ 実は、１９７５年以前に 　公開鍵暗号 秘密厳守 特許もとらず 2018/12/8 confidential

代表的な公開鍵暗号 RSA暗号 N=pqの素因数分解の困難さを利用 ElGamal暗号 有限巡回群上の離散対数問題を利用 2018/12/8 confidential

現代暗号理論 計算機科学の一大分野に成長 デジタル署名 電子選挙 電子現金 放送型暗号系 零知識証明などなど 2018/12/8 confidential

講義内容 暗号の歴史 確率 　　教科書、２章p.8～ メッセージ認証コード 2018/12/8 confidential

確率とは さいころを考える 標本空間 ={ 1,2,・・・,6 } 確率関数 Pr(1)=Pr(2)=・・・= 確率分布 Pr(1) 　　　　　　 標本空間 ={ 1,2,・・・,6 } 　　　　　　 確率関数 Pr(1)=Pr(2)=・・・= Pr(1) Pr(2) ・・・・・・・・・ Pr(6) 確率分布 1|6 さいころ 1 2 3 4 5 6 2018/12/8 confidential

確率とは さいころを考える 標本空間 ={ 1,2,・・・,6 } 確率関数 Pr(1)=Pr(2)=・・・= 確率分布 Pr(i)≧0 　　　　　　 標本空間 ={ 1,2,・・・,6 } 　　　　　　 確率関数 Pr(1)=Pr(2)=・・・= Pr(1) Pr(2) ・・・・・・・・・ Pr(6) 確率分布 1|6 (1) i = 1,・・・,6に対し Pr(i)≧0 (2) Pr(1)+・・・+Pr(6) = 1 さいころ 1 2 3 4 5 6 2018/12/8 confidential

定義１ 以下の性質が成り立つとき、 （標本空間 U、確率関数Pr）の組を 確率分布と呼ぶ （１） 各 u∈ U に対し、 Pr(u)≧0 　　　確率分布と呼ぶ 　（１） 各 u∈ U に対し、 Pr(u)≧0 　（２） Σu Pr(u) = 1 2018/12/8 confidential

|U| = 集合Uの要素数 たとえば、 U = { 1, 2, ・・・ , 6 } のとき、|U| = 6 定義２ 各 u∈ U に対し、 　　　　　Pr(u) = が成り立つ確率分布を一様分布という 2018/12/8 confidential

Pr(A) = + = 1|6 1 2 3 4 5 6 2018/12/8 confidential

Pr(A) = + = 1|6 1 2 3 4 5 6 事象A 2018/12/8 confidential

定義３ 標本空間Uの部分集合Aを事象と呼び、 Pr(A) = Pr(μ) と定義する。 Pr(A) = + = 1|6 1 2 3 4 5 6 事象A 定義３ 標本空間Uの部分集合Aを事象と呼び、 　　 Pr(A) = Pr(μ) と定義する。 2018/12/8 confidential

定義３ 標本空間Uの部分集合Aを事象と呼び、 Pr(A) = Pr(μ) と定義する。 事象Aの補集合Aは余事象と呼ばれ、 1|6 1 2 3 4 5 6 事象A 余事象A 定義３ 標本空間Uの部分集合Aを事象と呼び、 　　 Pr(A) = Pr(μ) と定義する。 事象Aの補集合Aは余事象と呼ばれ、 Pr(A) = 1 – Pr(A)　　　　　　 2018/12/8 confidential

２つの部分集合、A,B ⊆ に対し |A∪B| = |A| + |B| － |A∩B| A B A∩B A∪B 2018/12/8 confidential

Pr(A∪B) = Pr(A) + Pr(B) － Pr(A∩B) ≦ Pr(A) + Pr(B) |A∪B| = |A| + |B| － |A∩B| 確率においても、同様に　 　　 Pr(A∪B) = Pr(A) + Pr(B) － Pr(A∩B) ≦ Pr(A) + Pr(B) 2018/12/8 confidential

Pr(HH)=Pr(HT)=Pr(TH)=Pr(TT)=1/4 （例）　コインを2枚投げる 2枚目 H T 1枚目 H = 表 T = 裏 H H H H T T T H T T 標本空間 Pr(HH)=Pr(HT)=Pr(TH)=Pr(TT)=1/4 2018/12/8 confidential

（例） コインを2枚投げる 少なくとも一回は表が出る 事象A A = { HH,HT,TH }, Pr(A) = ¼ + ¼ + ¼ = ¾ （例）　コインを2枚投げる 少なくとも一回は表が出る 　事象A A = { HH,HT,TH }, Pr(A) = ¼ + ¼ + ¼ = ¾ 2枚目 H T 1枚目 H = 表 T = 裏 H H H H T T T H T T 標本空間 2018/12/8 confidential

（例） コインを2枚投げる 少なくとも一回は表が出る 事象A A = { HH,HT,TH } 余事象A A = { TT }, H T H （例）　コインを2枚投げる 少なくとも一回は表が出る 　事象A A = { HH,HT,TH } 余事象A A = { TT }, 2枚目 H T 1枚目 H = 表 T = 裏 H H H H T T T H T T 標本空間 2018/12/8 confidential

条件付確率 Pr(μ) Pr（μ| B） = if μ∈B ① Pr(B) Pr（μ| B） = 0 if μ B ② 事象A ⊆　　の条件付確率 　 Pr(A|B) = Pr(μ|B) = 　　③ ⇒ Pr(A∩B) = Pr(A|B) ・ Pr(B) Pr(B) Pr(A∩B) Pr(B) 2018/12/8 confidential

B1,B2,・・・,Bnに分割されていると仮定する。 すると、任意の事象Aに対し ・・・・・・・・ Bn 　　= 標本空間　　がn個の事象 　　B1,B2,・・・,Bnに分割されていると仮定する。 　　すると、任意の事象Aに対し 　　Pr（A） = Pr（A∩Bi） = Pr(A|Bi)・Pr(Bi) A 2018/12/8 confidential

Pr(B1 | A) = Pr(A∩B1) / Pr(A) 分子 = Pr(A | B1) ・Pr(B1) ・・・・・・・・ Bn 　　= A Pr(B1 | A) = Pr(A∩B1) / Pr(A) 分子 = Pr(A | B1) ・Pr(B1) 分母 = ΣPr(A | Bi)・Pr(Bi) = Pr(A | B1) ・Pr(B1) / ΣPr(A | Bi)・Pr(Bi) 2018/12/8 confidential

Pr(B1 | A) = Pr(A | B1) ・Pr(B1) / ΣPr(A | Bi)・Pr(Bi) ・・・・・・・・ Bn 　　= A ベイズの定理 Pr(B1 | A) = Pr(A | B1) ・Pr(B1) / ΣPr(A | Bi)・Pr(Bi) 2018/12/8 confidential

講義内容 暗号の歴史 確率 メッセージ認証コード 　　　教科書, p.12～ 2018/12/8 confidential

なりすまし攻撃 アリス 好き ボブ 敵 2018/12/8 confidential

改ざん攻撃 アリス きらい ボブ 好き 敵 2018/12/8 confidential

メッセージ認証 アリス 鍵 K ボブ 鍵 K （好き,Tag） 敵 平文 認証子 ・なりすまし攻撃 ・改ざん攻撃 2018/12/8 confidential

方式 p=大きな素数 鍵 K=(a,b) ← {0, 1, …, p-1} 平文 m ∈ {0, 1, …, p-1} Tag=a・m+b mod p 2018/12/8 confidential

送信者のアルゴリズム 平文 m ∈ {0, 1, …, p-1} 鍵 K=(a,b) ← {0, 1, …, p-1} アリスは、 Tag =a・m+b mod p を計算し、(m,Tag)をボブに送る。 2018/12/8 confidential

受信者のアルゴリズム 平文 m ∈ {0, 1, …, p-1} 鍵 K=(a,b) ← {0, 1, …, p-1} (m,Tag)を受け取ったボブは、 Tag=a・m+b mod p が成り立てばaccept 2018/12/8 confidential

メッセージ認証 p＝素数 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選 平文 m ∈ {0,1,2,・・・,p-1} 認証子 p＝素数 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選 平文 m ∈ {0,1,2,・・・,p-1} アリス 鍵　K ボブ 鍵　K （m,Tag） = （a,b） = （a,b） 敵 2018/12/8 confidential

メッセージ認証 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選ぶ 平文 m ∈ {0,1,2,・・・,p-1} アリス 認証子 鍵 a,b ← {0,1,2,・・・,p-1} からランダムに選ぶ 平文 m ∈ {0,1,2,・・・,p-1} アリス 鍵　K ボブ 鍵　K （m,Tag） = （a,b） = （a,b） 敵 Tag = a m + b mod p pは素数 2018/12/8 confidential

定理 本方式においては、 Pr(なりすまし成功) = 1/p Pr(改ざん成功) = 1/p 2018/12/8 confidential

なりすまし攻撃 m, Tag ボブ アリス K=(a,b) 敵 ボブ accepts if Tag=a×m+b mod p 2018/12/8 confidential

なりすまし確率 (m, Tag)=固定 アリス ボブ 敵 K=(a,b):ランダム Pr(ボブ accepts) = Pr(Tag=a×m+b mod p 　　　　　　となる鍵(a,b)を持っている) 2018/12/8 confidential

なりすまし攻撃 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ A 2 b 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ A 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Tag = a m + b mod p となる(a,b)の集合A 2018/12/8 confidential

A 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ 2 （2,0） b 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ A 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） A = ボブがだまされるという事象 　 = （Tag = a m + b mod p ） が成り立つ事象 　固定 2018/12/8 confidential

Tag=am+b mod p 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ Tag=am+b mod p 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Pr(A) = この面積 全面積 2018/12/8 confidential

Tag=am+b mod p = 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ Tag=am+b mod p 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Pr(A) = この面積 全面積 この式が成り立つ（a,b）の個数 （a,b）の総数 = 2018/12/8 confidential

Tag=am+b mod p 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ Tag=am+b mod p 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Pr(A) = この式が成り立つ（a,b）の個数 （a,b）の総数 = p2 2018/12/8 confidential

分子： Tag=am+b aを決めると、 mod p bが決まる。 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 分子： 1 （1,0） ・・・・・・ Tag=am+b mod p 2 （2,0） aを決めると、 bが決まる。 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Pr(A) = この式が成り立つ（a,b）の個数 （a,b）の総数 = p2 a = 0 → b = tag a = 1 → b = tag - m p個 ・・・ a = p-1 → b = tag - （p-1）m 2018/12/8 confidential

Tag=am+b mod p 1 2 ・・・ p-1 （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） 1 2 ・・・ p-1 a （0,0） （0,1） （0,2） ・・・ （0,p-1） 1 （1,0） ・・・・・・ Tag=am+b mod p 2 （2,0） 標本空間 ・・・ ・・・ p-1 （p-1,0） ・・・・・・・・・ （p-1,p-1） Pr(A) = この式が成り立つ（a,b）の個数 （a,b）の総数 p a = 0 → b = tag = p a = 1 → b = tag - m 2 p個 ・・・ 1 = a = p-1 → b = tag - （p-1）m p 2018/12/8 confidential

∀m, ∀Tag, Pr(なりすまし攻撃でボブが騙される) = に対し、P(x)が成り立つ ∀x ,P(x) 全てのx 　　 各x 任意のx For any x ∀x ,∀y,P(x,y) 全ての(x,y) 各(x,y) 任意の(x,y) ∀m, ∀Tag, Pr(なりすまし攻撃でボブが騙される) = に対し、P(x)が成り立つ に対し、P(x,y)が成り立つ 1 p 2018/12/8 confidential

改ざん攻撃 アリス 鍵 K ボブ 鍵 K （m,Tag） （m’,Tag’） m’ ≠ m 敵 = （a,b） （a,b） = 2018/12/8 confidential

改ざん攻撃 アリス 鍵 K ボブ 鍵 K （m,Tag） （m’,Tag’） 事象A m’ ≠ m 敵 if accept = 事象B = （a,b） 事象A m’ ≠ m = （a,b） 敵 if accept = 事象B 2018/12/8 confidential

改ざん攻撃 任意に固定 アリス 鍵 K ボブ 鍵 K （m,Tag） （m’,Tag’） 事象A 敵 if accept = 事象B = （a,b） 事象A = （a,b） 敵 if accept = 事象B 2018/12/8 confidential

事象A = {（a,b）| Tag = a・m + b mod p } 事象B = {（a,b）| Tag’ = a・m’ + b mod p } ∀m, ∀Tag, ∀m’(≠m), ∀Tag’ Pr(ボブが騙される) = Pr(B|A) = =　　　　 Pr(A∩B) Pr(A) p 1 事象A,Bが成り立つ(a,b)の数 ＝ 事象Aが成り立つ(a,b)の数 2018/12/8 confidential

方式 平文 m ∈ {0, 1, …, p-1} 鍵 (a,b) ← {0, 1, …, p-1} アリスは、 Tag=a・m+b mod p を計算し、(m,Tag)をボブに送る。 ボブは、 が成り立てばaccept 2018/12/8 confidential

定理 本方式においては、 Pr(なりすまし成功)=1/p Pr(改ざん成功)=1/p 2018/12/8 confidential

長いメッセージの場合 平文 m1, m2 ∈ {0, 1, …, p-1} 鍵 (a, b, c) ← {0, 1, …, p-1} Tag=a・m1+b・m2+c mod p 2018/12/8 confidential

演習(1) この方式においても、 Pr(なりすまし成功)=1/p Pr(改ざん成功)=1/p が成り立つことを証明せよ。 2018/12/8 　が成り立つことを証明せよ。 2018/12/8 confidential

演習(2) 以下の方式の Ｐｒ(なりすまし成功)、Pr(改ざん成功) を求めよ。 平文 m1, m2 ∈ {0, 1, …, p-1} 鍵 (a, c) ← {0, 1, …, p-1} Tag=a・m1+a2・m2+c mod p 2018/12/8 confidential