Q q 情報セキュリティ 第6回:2005年5月26日(金) q q.

Slides:



Advertisements
Similar presentations
1 前回の練習問題 F 29 = {1, 2,…, 28} において, g = 11 が生成元であることを確 かめ, F 29 の元とその離散対数との関係を図示せよ. x = 1,..., 28 に対し, g x mod 29 を計算すればよい
Advertisements

暗号 田浦健次朗.
情報工学科 06A2055 平塚 翔太 Hiratsuka Shota
データ構造と アルゴリズム 第十二回 知能情報学部 知能情報学科 新田直也.
黒澤 馨 (茨城大学) 情報セキュリティ特論(4) 黒澤 馨 (茨城大学) 2017/3/4 confidential.
近似アルゴリズム 第10章 終了時刻最小化スケジューリング
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
Q q 情報セキュリティ 第6回:2005年5月20日(金) q q.
データ構造と アルゴリズム 理工学部 情報システム工学科 新田直也.
黒澤 馨 (茨城大学) 情報セキュリティ特論(6) 黒澤 馨 (茨城大学) 2017/3/13 confidential.
2009/10/9 良いアルゴリズムとは 第2講: 平成21年10月9日 (金) 4限 E252教室 コンピュータアルゴリズム.
データ構造と アルゴリズム 第二回 知能情報学部 新田直也.
香川大学工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学工学部 富永浩之
香川大学工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学工学部 富永浩之
共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版.
データ構造と アルゴリズム 知能情報学部 新田直也.
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
黒澤 馨 (茨城大学) 情報セキュリティ特論(7) 黒澤 馨 (茨城大学)
データ構造とアルゴリズム論 第7章 探索のアルゴリズム
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
暗号技術 ~公開鍵暗号方式の仕組み~ (3週目)
第10回 情報セキュリティ 伊藤 高廣 計算機リテラシーM 第10回 情報セキュリティ 伊藤 高廣
博士たちの愛する素数 徳山 豪 東北大学 Prime numbers that professors love
Q q 情報セキュリティ 第3回:2005年4月28日(金) q q.
Q q 情報セキュリティ 第3回:2005年4月22日(金) q q.
Q q 情報セキュリティ 第12回:2006年7月7日(金) q q.
Q q 情報セキュリティ 第5回:2005年5月13日(金) q q.
Q q 情報セキュリティ 第14回:2005年7月15日(金) q q.
Q q 情報セキュリティ 第8回:2006年6月9日(金) q q.
実用的暗号通信ソフトウェア 「まめだくん」の開発 Shiota Laboratory
情報セキュリティ  第11回 デジタル署名.
情報セキュリティ  第8回 RSA暗号.
2章 暗号技術 FM15002 友池 絲子.
Q q 情報セキュリティ 第11回:2004年6月18日(金) q q.
5.RSA暗号 素因数分解の困難性を利用した暗号.
25. Randomized Algorithms
東北大学大学院情報科学研究科 教授 西関 隆夫
Q q 情報セキュリティ 第12回:2007年7月6日(金) q q.
Q q 情報セキュリティ 第8回:2005年6月3日(金) q q.
Q q 情報セキュリティ 第7回:2006年6月2日(金) q q.
Q q 情報セキュリティ 第7回:2007年6月1日(金) q q.
Q q 情報セキュリティ 第6回:2007年5月25日(金) q q.
プログラミング基礎a 第8回 プログラムの設計 アルゴリズムとデータ構造
Q q 情報セキュリティ 第4回:2005年5月12日(金) q q.
情報処理Ⅱ 第2回:2003年10月14日(火).
11.再帰と繰り返しの回数.
生物情報ソフトウェア特論 (2)たたみ込みとハッシュに 基づくマッチング
「情報セキュリティ論」 2-4 公開鍵暗号の原理とRSA暗号
Q q 情報セキュリティ 第9回:2007年6月15日(金) q q.
香川大学創造工学部 富永浩之 情報数学1 第1-3章 素数と素因数分解 香川大学創造工学部 富永浩之
代数体上で定義された楕円曲線の 素因数分解への応用
補講:アルゴリズムと漸近的評価.
データ構造とアルゴリズム (第5回) 静岡大学工学部 安藤和敏
Diffie-Hellman 鍵共有 ElGamal 暗号 楕円曲線暗号,量子コンピュータ
データ構造とアルゴリズム論 第6章 探索のアルゴリズム
Q q 情報セキュリティ 第5回:2006年5月19日(金) q q.
計算機プログラミングI 第4回 2002年10月31日(木) 問題解決とアルゴリズム クラスメソッドと手続きの抽象化 最大公約数
香川大学創造工学部 富永浩之 情報数学1 第2-1章 合同式の性質と計算 香川大学創造工学部 富永浩之
情報処理Ⅱ 2006年11月24日(金).
黒澤 馨 (茨城大学) 情報セキュリティ特論(8) 黒澤 馨 (茨城大学)
Q q 情報セキュリティ 第8回:2004年5月28日(金) の補足 q q.
暗号技術・セキュリティ 情報工学科  04A1004 石川 真悟.
香川大学創造工学部 富永浩之 情報数学1 第2-2章 合同式の逆元と応用 香川大学創造工学部 富永浩之
情報生命科学特別講義III (3)たたみ込みとハッシュに 基づくマッチング
情報処理Ⅱ 第2回 2004年10月12日(火).
情報処理Ⅱ 2005年11月25日(金).
Q q 情報セキュリティ 第7回:2005年5月27日(金) q q.
情報処理Ⅱ 第3回 2004年10月19日(火).
情報処理Ⅱ 2006年10月20日(金).
ファーストイヤー・セミナーⅡ 第10回 if文による選択処理(2).
Presentation transcript:

q q 情報セキュリティ 第6回:2005年5月26日(金) q q

本日学ぶこと RSAのアルゴリズム RSAの安全性 Diffie-Hellman鍵交換 剰余演算,べき剰余 ユークリッドの互除法とその拡張 素数判定 RSAの安全性 素因数分解 対数の計算,離散対数問題 Diffie-Hellman鍵交換 鍵交換の方法 man-in-the-middle攻撃 前回

本日の授業で学ぶ語句 多項式時間,指数時間 素数生成,素数判定,フェルマーテスト,確定的手法,確率的手法 素因数分解問題,離散対数問題 Diffie-Hellman鍵交換,man-in-the-middle攻撃 指数時間アルゴリズムは効率が悪い. 素因数分解が効率よく行えるなら,RSAは安全でない. Diffie-Hellman鍵交換で,整数を共有することができる. 安全性は,離散対数問題に依存する. しかしman-in-the-middle攻撃には弱い.

効率の良いアルゴリズム・悪いアルゴリズム 処理時間が,入力の値のビット数 L と適当な定数 C,k を 用いて C・Lk で抑えられるならば,効率が良い. 多項式時間アルゴリズムと呼ばれる. 処理時間が,入力の値に比例するならば,効率が悪い. 例1: a % m, a2 % m, …, ab % m の順にべき剰余を求める. 例2: a*b % n = 1 を満たす整数 b を,b←1, 2, … と順に 代入して求める. 入力の値のビット数を L とすると,2L に比例するため, 指数時間アルゴリズムと呼ばれる.

素数生成 入力:ビット数N 出力:Nビットの素数 アルゴリズム Step 1. 最上位が1,間は(N-2回の1ビット乱数生成により)N-2ビットの乱数,最下位は1となるような,Nビットの整数nをランダムに生成する. Step 2. nが素数であるかどうかを判定する.素数でないと判定されたら,Step 1に戻る. Step 3. nを出力して終了する. 1 ? …

素数判定 入力:2以上の整数n,テスト回数T 出力:nが素数なら「yes」,素数でないなら「no」 アルゴリズム(フェルマーテスト) フェルマーの小定理: p が素数 ⇒ (gcd(p,a)=1 ⇒ ap-1 % p = 1 ) 入力:2以上の整数n,テスト回数T 出力:nが素数なら「yes」,素数でないなら「no」 アルゴリズム(フェルマーテスト) Step 1. i←1とする. Step 2. 2以上n未満の正整数aをランダムに生成する. Step 3. gcd(a,n)>1ならば,Step 7に進む. Step 4. an-1%n≠1ならば,Step 7に進む. Step 5. i←i+1とする.i≦Tならば,Step 2に戻る. Step 6. 「yes」と出力して終了する. Step 7. 「no」と出力して終了する. うまくいく? 素数であれば必ず「yes」と出力するが,素数でないのに誤って「yes」を出力することもある. 擬素数 n=561はカーマイケル数

○ ○ 素数判定法の分類(1) 確率的手法 乱数を使う. 素数でないと判定したら,必ず素数でないが, 素数であると判定しても,実は素数でない可能性がある. 精度と実行時間は,テスト回数次第. 事実 素数でない 素数である 判定結果 素数でない ○ 起こらない 素数である 起こり得る ○

○ ○ 素数判定法の分類(2) 確定的手法 乱数は使わない. 判定結果は正しい. 多項式時間アルゴリズムが提案されているが,計算時間は実用的ではない. 事実 素数でない 素数である 判定結果 素数でない ○ 起こらない 素数である 起こらない ○

RSAと素因数分解の関係 素因数分解が効率よく行えるなら,RSAは安全でない. 略証: NとEを既知とし,(素因数分解により)Nの素因数pが知られているときに,Dを計算できればよい. q←N/p,L←lcm(p-1,q-1) とし,aE+bL=1を満たす整数の組(a,b)を拡張ユークリッド法により求め,D←a % L とすればよい.これらの操作はいずれも効率よく行える. 「RSAが安全でないなら,素因数分解が効率よく行える」は証明されていない.

RSAにおける素因数分解の方法 Nをk=3, 5, 7, ...の順に割って割り切れる(余りが0になる)か調べる. 乱数Mを1<M<Nの範囲で生成して,gcd(N,M)を求める.これが1より大きければ,Nの素因数の一つである. これらで素因数を発見するための実行回数の期待値は, N(の素因数の小さいほうの値)に比例する.したがって, 指数時間アルゴリズムであり,効率は悪い.

整数の対数を求める方法 入力:2以上の整数a,正整数y 出力: y = az を満たす整数 z 方法1 方法2 log2 az = z log2 a を用いる. 整数値xのビット数を |x| で表すとき,|y| ≒ z×|a| である. よって z ≒ |y| / |a|. 方法2 2分探索を応用する. a, a2, a4, a8,... を求めていき,a2q≦y<a2q+1 を満たす整数qが見つかれば,2q≦z<2q+1とわかる.y'=y / a2q に対して,y'=az' を満たすz'を(再帰的に)求め,z=2q+z' とする.

RSAの解読問題(≠離散対数問題) 入力:正整数m,2以上の整数a,正整数y 出力: y = az % mを満たす整数z (ただし1≦z<m) 前記の「整数の対数を求める方法」は, いずれも適用できない.

離散対数問題 入力:2以上の素数p,生成元g, 正整数y 出力: y = gz % pを満たす整数z (ただし1≦z<p) (前ページの)RSAの解読問題が効率よく解ければ,離散対数問題も効率よく解ける. ただし,mが二つの素数の積であることを利用して,効率よく解くのであれば,その手法は離散対数問題に適用できない. 離散対数問題が効率よく解けるとしても,(前ページの)RSAの解読問題には利用できない.

生成元の補足 「gがpの生成元である」の必要十分条件 g % p,g2 % p,…,g(p-2) % p がどれも異なる. 素数かつp-1の約数(p-1の素因数)であるすべてqに対して,g(p-1)/q % p ≠ 1

Diffie-Hellman鍵交換のエッセンス 公開情報:素数P,生成元G Aliceが秘密に持つ情報:A Bobが秘密に持つ情報:B Alice→Bob:GA % P Bob→Alice:GB % P Aliceの処理:(GB % P)A % P = GAB % P Bobの処理:(GA % P)B % P = GAB % P GはPに依存する. Gは必ずしも素数ではない.

man-in-the-middle攻撃(教科書pp.136-138) カレーライス ください ハヤシライス お願いします (悪意ある) ウエイター 客 料理人 カレーライス どうぞ ハヤシライス できたよ

Diffie-Hellman鍵交換に man-in-the-middle攻撃を適用すると(1) アリスがボブに送信するが,マロリーはこれを受け取る. マロリーが,ボブになりすましてアリスに送信する. マロリーが,アリスになりすましてボブに送信する. ボブがアリスに送信するが,マロリーはこれを受け取る. 2004年度 情報セキュリティの 試験問題・解答より

Diffie-Hellman鍵交換に man-in-the-middle攻撃を適用すると(2) AliceとMalloryはGAM % Pを共有し, BobとMalloryはGBM % Pを共有する. AliceとBobの間では情報を共有していないが, Aliceは,BobとGAM % Pを共有していると思っている. Aliceが,GAM % Pを鍵として暗号文を作り,Bobに送ったら,Malloryはそれを受け取ってGAM % Pで復号し, GBM % Pで暗号化したものをBobに渡す.     AliceとBobの間で秘密にしたい通信内容が,Malloryにも知れてしまう! α E(GBM%P,α) α E(GAM%P,α) Mallory Alice Bob α