←セキュリティ論シラバスへ
←講義のツボメニューへ

５　公開鍵暗号系

【2001.11.13 】【第７回】

　1976年DiffieとHellmanによって提唱された。

〇落とし戸つき一方向性関数（one-way　trap-door　function）の概念

〇基本的な公開鍵暗号系のアイデア
 １．受信者は'秘密情報'を作成し、それを基に秘密鍵（私有鍵）（secret　key、　private　key）Ksと公開鍵（public　key）Kpを生成する。公開鍵を公表し、秘密鍵は厳重に保管しておく。
２．送信者はKpを用いてメッセージを暗号化する。
３．受信者はKsを用いてメッセージを復号する。

５．１RSA　公開鍵暗号系

暗号化鍵（公開鍵）：e,n
復号鍵　（秘密鍵）：d,n
暗号化、復号操作　：E,D
平文　M、暗号文Cとする（ただし、0≤M,C≤n -1)
C = E(M) = Me mod n
M = D(C) = Cd mod n

鍵生成

１．任意の相異なる二つの大きな素数p,qを選び、積n = pqを計算する。
２．(p-1)と(q-1)の最小公倍数L = lcm(p-1,q-1)を計算し、Lと互いに素でLより小さい任意の整数eを選ぶ。

　　　L = lcm(p-1, q-1)
(e,L) = 1, 1＜ e ＜ L
３．ed ≡ 1( mod L )となるdを拡張ユークリッドアルゴリズム（シラバスの参考書、情報学基礎B　講義資料等を参照）により求める

数値例

・p = 5, q = 11

・n = 55

・L = lcm(p - 1, q - 1) = lcm(4,10) = 20

・仮にe = 7とする。（注： (7,20) = 1)）

・このとき、dは
　　　　　7( = e )･　3 = 1･20(= L)+1
すなわち、7･3 ≡ 1 (mod 20)
従って、、d = 3

・1 ≤ M ≤ 54

・もしも M = 22 ならば、C = 227 mod 55 = 2494357888 mod 55 = 33
 (2494357888 = 45351961 * 55 + 33)

・もしもd = 3を知っていれば、M = 333 mod 55 = 35937 mod 55 = 22
(35937 = 635 * 55 + 22)

RSA暗号系とビジネス

特許：アメリカでのみ特許が成立していたが2000年9月に失効した。
輸出規制：ワッセナー協約(1998.12)による制約（鍵長512ビットまで）があった。
　　　　　　アメリカ政府商務省公布（2000年1月）により許可制に緩和された。
　　　　　　2000年7月に日本を含む特定の国については届け出性に変更され事実上撤廃。


暗号系の安全性

１．オイラー関数φ(n) = (p - 1)(q - 1)を求める。
　　pq = n, p + q = n - φ +1より、p,qが決まる。
２．離散対数(discrete logatithm)を計算する。
　　M = C d mod n から秘密鍵dを計算する。
３．nを素因数分解する。
　　鍵生成手続きに従って秘密鍵dが計算できる。

素因数分解

〇合成数の大きさと素因数分解 　・RSA Factoring Challengeにみる歴史
数年月MIPS年
RSA-10091.047
RSA-11092.0475
RSA-12093.06830
RSA-12994.045000
RSA-13096.04500
RSA-14099.02数万

・140ディジットの合成数を185台のコンピュータで分解。（RSA Factoring Challenge)(99.02)
　・512ビットの合成数を292台のコンピュータで5.2ヶ月で分解。（RSA Factoring Challenge)(99.08)
　・RSA Factoring Challenge　の新しい数2001.05.23より
　・RSA Security社の推奨鍵長：230ディジット（99.08現在）
　・open SSLのデフォルト：512ビット
　・最近の推奨鍵長：1024ビット？(PGP1.6.3i他)
〇因数分解アルゴリズム
　・二次ふるい法O(exp(c1(log n loglog n)1/2))
　・数体ふるい法O(exp(c'1(log n)1/3 loglog n)2/3))
離散対数アルゴリズムの計算量も、ほぼ同程度。

RSA暗号化・復号処理の高速化

・べき乗剰余算術z = x y mod n

１．ｙの二進数展開をyl･･･y2y1とする
２．z = 1
３．i = lから1まで、以下を繰り返す
3.1　z = z 2 mod n
3.2 もしyi =1ならばz = zx mod n

〔例〕x27の計算
y = 27(10進数)
　　　　 = 11011
= 24 + 23 + 21 + 20
= ((1 * 2 + 1) * 2) * 2 + 1) * 2 + 1
x27 = x 110011(2進数)
=x ((((1 * 2 + 1)* 2)* 2 + 1) 2 + 1
=(((x2x)2)x)2x

i初期値５　４　３　２　１
yi１　１　０　１　１
zx　x3 x6 x13 x27


ElGamal 公開鍵暗号系

　ElGamal によって1984に提案。離散対数問題の計算量的困難性に基づく。

鍵生成

１．素数pを選ぶ。
２．pの原始元aを一つ選ぶ。
３．0xpの整数xを選び、y = ａx mod pを計算する。
(1)原始元(primitive element)とは周期（xi = x となるような２つ以上の最小の）がi = P - 1となるような元ｘのこと。
公開鍵：y,p,a
秘密鍵：x
公開鍵
１．整数kを一つランダムに選ぶ。
２．送りたいメッセージをMとするとき、次のC1,C2
C1 = ak mod p
C2 = Myk mod p

復号
xを用いて以下の式を計算する。
　　　C2/C1x mod p = Myk/yk mod p = M

楕円暗号

　ある特殊な三次曲線（楕円曲線）の有理点の集合の上の加法群上.に構成される暗号。
楕円曲線：yp + c1xy + a3y = x3 + a2x2 + a4x + a6,(ai は整数）
有理点：x、y共に整数であるような解＋無限遠点
　　　　公開鍵暗号の構成には有限体上の楕円曲線が用いられる。
　　　　RSA型暗号、ElGamal型暗号が構成可能。
　　　　整数上のRSA暗号と比較して短い鍵長で同等の安全性を得られるとされる（RSAの鍵1024ビットと同等の安全性が楕円暗号では160ビットで得られるとされる）


課題　11月16日まで　
前回と今回の講義内容について意見、感想を200字以上何字でも。
オプション課題
任意のセキュリティに関する主題について、意見、感想、質問、その他、講義進め方についてなど。

←セキュリティ論シラバスへ