情報セキュリティ　 第１１回 デジタル署名

脅威と暗号技術 セキュリティに対する脅威 脅かされる特性 暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 セキュリティに対する脅威　　　　脅かされる特性　　　　　暗号技術 共通鍵暗号 盗聴 （秘密が漏れる） 機密性 公開鍵暗号 改竄 （情報が書き換えられる） 正真性 一方向ハッシュ関数 なりすまし （正しい送信者のふりをする） 認証 メッセージ認証コード 否認 （後から私じゃないと言う） 否認不可能性 デジタル署名

ディジタル署名 目的 モデル メッセージ認証コード(MAC)との比較: 送信者を認証する。 メッセージの改竄を検出する。 否認不可を実現する。 モデル 送信者は秘密鍵とメッセージmから署名σ作成し、(m,σ)を送信する。 受信者は受信したmと公開鍵からσが正しいか検査し、正しいならばmを受理する。 メッセージ認証コード(MAC)との比較: MACは共通鍵を利用する。 MACは否認不可を実現出来ない（第3者から見て送信者と受信者のどちらが嘘を言っているかわからない）。 秘密鍵を使用 公開鍵を使用 ディジタル署名 平文m 送信者 (m,σ) 受信者 受理 廃棄 敵 σが正しい場合だけ受理 秘密鍵がないとσを正しく作れない 共通鍵を使用 共通鍵を使用 MAC 平文m 送信者 (m,Tag) 受信者 受理 廃棄 敵 Tagが一致する場合だけ受理

ディジタル署名アルゴリズム 鍵生成アルゴリズム 署名アルゴリズム 検査アルゴリズム 公開鍵PKと秘密鍵SKを生成する。 署名σを生成する。 署名σが正しいかどうかを出力する。 ディジタル署名アルゴリズム 公開鍵PＫ 鍵生成アルゴリズムG 秘密鍵SＫ 平文m 署名アルゴリズムS 署名 σ 秘密鍵SＫ 署名文(m,σ) 受理 廃棄 検査アルゴリズムV 公開鍵PＫ

ディジタル署名の安全性 選択メッセージ攻撃 偽造 安全性 敵は、公開鍵PKと自由に選んだメッセージm1,..,mqに対する署名σ1,..,σpから、 (m,σ)を偽造する。 偽造 受信者が受理する署名文(m,σ)を作成することを偽造と呼ぶ。 安全性 敵が署名文(m,σ)の偽造に成功する確率が無視できる程小さいとき安全である。 選択メッセージ攻撃 署名オラクル 署名 σ1,..,σq メッセージ m1,..,mq 公開鍵 Pk 敵 偽造 (m,σ)

RSA署名方式 鍵生成 署名生成 検査 FDH（Full Domain Hash）署名方式 二つの素数pとqを生成する。 gcd((p-1)(q-1),e)=1を満たすeを選ぶ。 拡張ユークリッドの互除法からed≡1 (mod (p-1)(q-1))を満たすdを求める。 公開鍵Pk=(N,e)を公開し秘密鍵Sk=dを保持する。但し、N=pqである。 署名生成 ハッシュ関数Hを使って平文mをk(≦N)ビットのハッシュ値H(m)に圧縮する。 ハッシュ値H(m)をd乗して署名σを作成する： σ=H(m)d mod N 検査 受信した平文mのハッシュ値H(m)と受信した署名σのe乗（σe ） が合同、つまり、σe≡H(m) mod Nが成立すれば受理し、成立しなければ廃棄する。 FDH（Full Domain Hash）署名方式 ハッシュ値のビット数kがk=Nであること。 ハッシュ関数Hの値域はZN={0,1,.,N-1}である。 送信者 素数pとq及びeを選択し、 ed≡1を満たすdを求める PKを公開 Pk=(N,e) Sk=d 鍵生成アルゴリズムG 送信者 署名アルゴリズムS 平文 m 署名 σ σ=H(m)d mod N Sk=d 受信者 検査アルゴリズムV 受理 廃棄 署名文(m,σ) σe≡H(m) mod N ならば受理する Pk=(N,e)

ハッシュ関数を使って平文mをハッシュ値に圧縮する ＲＳＡ暗号とＲＳＡ署名の比較 平文mを復号する 公開鍵 送信者 受信者 C RSA暗号　 C = me mod N →　 m = (Cd mod N) RSA署名　σ=H(m)d mod N →　 σe ≡ H(m) (mod N) m, σ ハッシュ関数を使って平文mをハッシュ値に圧縮する 秘密鍵 合同式が成立すれば平文mを受理する

CAが公開鍵の所有者は送信者であることを保証 共通鍵の配布 受信者 送信者 平文 暗号文 暗号文 平文 共通鍵 共通鍵 暗号化した 共通鍵 暗号化した 共通鍵 公開鍵の発行元 秘密鍵 CA CAが公開鍵の所有者は送信者であることを保証 CAの デジタル署名 公開鍵 CAの デジタル署名 公開鍵

素数定理 定理A： 無限に多くの素数がある。 定理B： π(x)をx(>0)以下の素数の数とすると、次式が成立つ x=etとすれば、 定理Bからπ(x)とx/ln xは同じ速度で無限大になる。 （例） π(1010) =455052511 1010/ln 1010 =434294481 自然対数 ln x = logex

素数判定法 素数であるための必要条件（Millerの定理）を計算するため、素数であることを断定できない。素数でない場合を繰返し排除することにより、素数である確率を高くしている。 Millerの定理 素数p、奇数r、正整数sに対し、　　p－1=2srとする。この時、任意のa (1≦a≦p－1)に対して以下が成立つ。 ar≡1(mod p) 又は、 a2jr≡－1(mod p)、j=0,1,..,s－1 （証明） p－1=23r （s=3の場合）を考える。任意のa∈Z*pに対して、フェルマーの定理より、 ap-1≡1 (mod p)。従って、 0≡ ap-1－1 ≡a23r－1 ≡(a22r+1)(a22r－1) ≡(a22r+1)(a2r+1)(a2r－1) 　　 　　 ≡(a22r+1)(a2r+1)(ar+1)(ar－1) (mod p)。よって、 　　　a22r≡－1又は、 a2r≡－1又は、 ar≡－1又は、 ar≡1。 Miller-Rabinテスト （入力）奇数n≧3、繰返し回数t （出力）nは素数(prime)／合成数(composite) （アルゴリズム） n－1=2sr（rは奇数）と表し、i=0とする Y 擬素数の 確率≦(1/4)t prime i=t N i=i+1 a(1≦a≦n－1)を選択 y0=ar mod n Y j=s－1 因数分解 N Y y0=1 or n－1 j=j+1 N j=0 yj=y2j-1 mod n ar≡1 又は ar≡－1 Y yj=n－1 N 必ず合成数 composite a2jr≡－1