「電子社会の信頼性向上と情報セキュリティ」
信頼性に関する基礎的なお話し
中央大学
2003 年 11 月 17 日 北海道大学情報基盤センター 水田正弘1
信頼性の高いコンピュータへの挑戦
◎コンピュータが社会一般に普及するにつれて、その信頼性が重要な問題となっている。 例えば、ある会社に顧客がクレームを言ってきたとき、かっては、 『コンピュータだから間違わない』 と答えて問題になったことがある。最近では、 『コンピュータが間違えた』 として、人間の責任を転嫁する場合がある。コンピュータの信頼性、別の言葉で言えば、 コンピュータの事故について考察する。 計算機事故の原因 故障：ハードウェア、ソフトウェア 過失：操作ミス、使用ミス 災害：地震、火災、水害 故意：システムへの不正侵入、不正行為1.1
故障・誤り・障害
故障（ｆａｕｌｔ） 誤りを生じさせる原因。システムの構成要素がその機能を失っている状態 誤り（ｅｒｒｏｒ） 規定の内容または論理的に正しい状態と計算または計測された結果との不一致 障害（ｆａｉｌｕｒｅ） システムが規定の機能を失うこと 故障 → 誤り → 障害 コンピュータシステム 利用者1.2
信頼性に関する基礎概念
信頼度 R(t) t 時間後に動作している確率 R(0) = 1, R(∞) = 0 故障率 λ(t) t 時間後における R(t) のうち次の単位時間に故障する割合 λ(t) = − 1 R(t) dR(t) dt , R(t) = exp (− t 0 λ(t)dt)故障率λ(t) のバス・タブ曲線 故 障 率 λ(t) 初期故障期 偶発故障期 摩耗故障期 時刻 t 故障率の単位：ｆｉｔ(フィット) 1 ｆｉｔ→ 109時間当り1 回の割合で故障が生じる 【例】：固定抵抗 数10 フィット ＬＳＩ 数10∼300 フィット
平均故障寿命(ＭＴＴＦ：Mean Time to Failure)
故障するまでの平均的な時間 MTTF = ∞ 0 R(t)dt = 1/λ （故障率一定の場合） 【例題】 （１）故障率100 フィットの部品の平均故障寿命 (MTTF) を求めよ。 ただし、故障率は一定とする。 （２）100 フィットの部品を 1000 個使った製品の MTTF を求めよ。 ただし、故障率は一定とする。また、この製品は1 個の部品が 故障しても、製品が故障するものとする。 解答（１） 故障率 λ = 100 MTTF= 1/λ より、 MTTF= 10−2(109時間) = 107(時間) （約 1142 年） 解答（２） 製品の故障率 100 フィット× 1000 MTTF= 104(時間)（約 1.14 年） ◎この例題からも分かるように、個々の部品の信頼性を上げても、部品の数が多くなると 全体の信頼性は低下する。そこで、以下ではシステム全体の信頼性を向上させる方法につ いて考える。
1.3
事故に対する対策
◎事故に対する対策のレベルとしては以下のものがある。 フェール・セーフ（fail-safe） 予め安全な状態を定義することができる場合に、故障を検出したとき、システムを安全な状態にする フォールト・アボイダンス（fault-avoidance） システムの構成要素の品質を高めて故障が生じるのをできるだけ避けること フォールト・トレランス（fault-tolerance） システムの一部分が故障しても、システムの連続的な操作が可能であること 【フォールト・トレランスの例】 ａ．待機形システム コンピュータ1 (動作) コンピュータ2 (待機) 誤り検出 各コンピュータの信頼度をR、誤り検出および切り替えユニットの信頼度を 1 とすると き、システム全体の信頼度Rdは、 Rd= R2 + 2R(1 − R) = 2R − R2 となる。従って、0 ≤ R ≤ 1 より Rd ≥ R となる。 ｂ．３重化構成 コンピュータ1 多数決ユニット コンピュータ2 コンピュータ3 各コンピュータの信頼度をR、多数決ユニットの信頼度を 1 とするとき、システム全体 の信頼度 Rtは、 Rt = R3+ 3R2(1 − R) = 3R2− 2R3 となる。従って、R > 1/2 ならば Rt> R である。 (R < 1/2 ならば Rt < R となるが、これは信頼性の低いコンピュータを同時に動かして も事態は悪化することを示している。) ◎上の２つの方式で、『誤り検出および切り替えユニットの信頼度を１とする』、『多数決 ユニットの信頼度を１とする』と仮定しているが、これは実際的ではない。それぞれの信 頼度が１ではないときの、システム全体の信頼度は各自計算されたい。
1.4
ソフトウェアの信頼性モデル
ソフトウェアの品質の１つである信頼性を定量評価するためのモデルを信頼性モデルと いう。ソフトウェアの信頼性とは、ソフトウェアをある環境で利用したとき、要求出力が 許容範囲にないという欠陥が一定期間におこらない確率であると考える。この評価モデル には、 1) プログラムの検査中に観測できるデータによるもの、 2) プログラムの使用中に観測できるデータによるもの、 3) プログラムの内部特性によるもの、などがある。 1) の例には、N を時刻 t = 0 においてプログラムに残存する誤りの総数、n(t) を時刻 t ま でに発見され修正された誤りの累積数、φを比例定数として、微分方程式 dn dt = φ(N − n(t)) が成立すると考え、 n(t) = N(1 − exp (−φt)) と評価するジェリンスキー(Jelinski,Z.)-モランダ (Moranda,P.B.) のモデルなどがある。 また n(t) = N(1 − exp (−φta)) と考えるズッカート(Sulert,A.N.) のモデルもある。2) の例には、プログラムに C 個の検 査用誤り(Calibration error) をランダムに埋め込み、検査データを用いて検査し、発見で きた埋め込みの誤りc 個、真の誤り e 個から、残存誤り数 E を E = Ce/c と推定するミ ルズ(Mills,H.D.) のモデルがある。3) の例には、ハルステッド (Halstead,M.H.) のソフト ウェア科学によって、演算と演算データの種類から誤りの総数を予測するモデルがある。 （岩波「情報科学辞典」より）1.5
コンピュータウイルス
(Computer Virus)
これについては、あまりにも変化が早く、大きいので省略さ
せていただきます。
2
符号理論、暗号、そして通信
情報を扱う場合、データのやりとりを考慮しなければ、そこにある計算機の能力および 現在保有する情報の範囲に情報の処理が限定されてしまう。 そこで、計算機ネットワークなどを利用することにより、幅広い情報処理が可能にな る。 コード データ構造： 保存・処理する データ通信： 伝える データ通信の必要性 (1) 距離と時間の克服 (2) 共同利用による計算機の効率的利用 ＨＩＮＥＳ（北海道大学情報ネットワークシステム）2.1
データ通信の基礎
正常な場合 雑音のある場合 コンピュータ モデム モデム コンピュータ 0 1 0 0 0 0 0 1 ’A’ 0 1 0 0 0 0 0 1 ’A’ 伝送 コンピュータ モデム モデム コンピュータ 0 1 0 0 0 0 0 1 ’A’ 0 1 0 0 0 1 0 1 ’E’ 伝送 ノイズ ’0’ ’1’ ’0’ ’1’ 入力シンボル 出力シンボル q=0.9 q=0.9 p=0.1 p=0.1 ＊エレメント誤り率 p = 0.1 のとき ８bit を正しく送れる確率 (1 − 0.1)8 = 0.43 ＊エレメント誤り率 p = 0.01 のとき ８bit を正しく送れる確率 (1 − 0.01)8 = 0.92 ＊エレメント誤り率 p = 0.0001 のとき ８bit を正しく送れる確率 (1 − 0.0001)8 = 0.9992 ８bit を 1000 文字送る場合 (1 − 0.0001)8000 = 0.449 ◎従って、ノイズがある場合、なんらかの対策を立てる必要がある。もちろん、ノイズが 全くないという状況はほとんど考えられない。 誤り検出と誤り訂正 １）誤り検出：誤りがあったことが分かるが、必ずしも訂正できない。 ２）誤り訂正：誤りがあったことが分かり、訂正できる。 ◎つまり、単に誤りの存在を検出するだけでよい場合には、「誤り検出」だけでよい（例 えば、送信者に再送信してもらえる場合など）。しかし、宇宙のかなたにある衛星からの 画像やＣＤの音楽のような場合には、できる限り「誤り訂正」できる方法を使う。 ［簡単な例１］（パリティ） Ａ＝(０１０００００１) (０１０００００１０) パリティビット ’ １’ の合計が偶数 ノイズ(０１００１００１０) →誤り！！ ’ １’ の合計が奇数 ◎これは、「誤り検出」であり、１ビットの誤りが発生したときには、その誤りの存在を 知ることができる。しかし、どのビットが誤ったのかは分からない。さらに、２ビットの 誤りが発生した場合には、その誤りを検出することができない。 ［簡単な例２］（３回、同じ符号語を送る） ’ Ａ’ ＝ (０１０００００１) 01000001 01000001 01000001 ノイズ 01000001 01000101 01000001 ’ Ａ’ ’ Ｅ’ ’ Ａ’ 多数決→’ Ａ’ ◎これは、１ビットの誤りに対する「誤り訂正」の機能を持つ。しかし、原データの３倍 もの符号を送信しなくてはならず、無駄が多い。そこで、『符号理論』が発達した。 問題 (1) 例２の方法では、２ビットの誤りに対する「誤り訂正」の機能はもつか？ (2) 例２の方法では、２ビットの誤りに対する「誤り検出」の機能はもつか？
2.2
符号理論の基礎
コード間の距離 ’ Ａ’=(01000001) ’ Ｅ’=(01000101) ’ Ａ’ と’ Ｅ’ は 1 ビットしか異ならない → 1 ビットのエラーで ’ Ａ’ が’ Ｅ’ に変わる ハミング距離 ：異なるビットの数で定義する。 ’ Ａ’=(01000001) ’ Ｅ’=(01000101) ’ Ｚ’=(01011010) ｄ(’ Ａ’,’ Ｅ’)=1, ｄ (’ Ａ’,’ Ｚ’)=4 ◎このハミング距離を基準にすることにより、符号の「誤り検出」および「誤り訂正」の 能力を検討することができる。『なんとなく、誤りに強そうだ』をより客観的に考察しよ う。 目的 ：うまい符号化をして、各符号語間のハミング距離を大きくする。 以下、dmin をあらゆる符号語の対のハミング距離の最小値とする。 定理1 (1)dmin≥ 2 ならば、1 ビットのエラーを検出できる。 (2)dmin≥ 3 ならば、1 ビットのエラーを訂正できる。1 1 1 1 符号語 1ビットのエラー 1 1 符号語 1ビットのエラー 1 1 1 1 dmin≥ 2 ならば、1ビットのエラーを検出できる dmin ≥ 3 ならば、1ビットのエラーを訂正できる ◎この定理1 を拡張すると、定理 2 となる。 定理2 (1)dmin≥ 2t + 1 ならば、t ビット以下のエラーを訂正できる。 (2)dmin ≥ 2t + s + 1 ならば、t ビット以下のエラーを訂正でき、 (t + s) ビット以下のエラーを検出できる。 ◎その訂正または検出能力をこえるエラーが生じた場合 1) 受信した信号が他の符号語の領域に属していれば、誤って復号される。 2) 受信した信号がいずれの符号語の領域にも属していなければ、復号不可能となる。
2.3
ハミングコード
◎ここまでで扱った、誤り検出と誤り訂正を実現する実際的な符号化の方法としてハミン グコードがある。少しの線形数学の知識を使うが、以下に紹介する。 ハミングコード(ハミングの単一誤り訂正符号) 1 ビットのエラーに対して誤り訂正できる符号化の方法 ハミングコードの一例 以下、送りたいメッセージを ’0’∼’15’ とする。 ’0’=(0000) ’1’=(0001) ’2’=(0010) ’3’=(0011) ・・・ ’14’=(1110) ’15’=(1111) この’0’ から’15’ を 1 ビットのエラーによっても誤り訂正できるようにして送る。 ◎パリティビットを1 ビットから複数ビットにすることにより、「誤り訂正」の能力を上 げる。メッセージ コード単語 受信単語 復号 ’9’=(1001) 1001100 1001100 1001 ’9’ パリテイビット ノイズのないとき 記号による定義 メッセージ：u = (X1, X2, X3, X4) コード単語：v = (X1, X2, X3, X4, X5, X6, X7) ただし、 X5 = X1+ X2+ X3 X6 = X1+ X2 + X4 X7 = X1 + X3+ X4 とする。ベクトル、行列で表現してみよう。 (X1, X2, …, X5, X6, X7) = (X1, X2, X3, X4)G または v = uG G = 1000111 0100110 0010101 0001011 : 生成行列 ただし、これらのベクトル、行列の演算は下の表による。 0+0=0 0・0=0 1+0=1 1・0=0 0+1=1 0・1=0 1+1=0 1・1=1 ◎これらの演算は前期で扱った’ ＸＯＲ’ と’ ＡＮＤ’ の演算と一致している。また、別の言 い方をすると、『位数2 の有限体の演算』となる。 【例】 ’6’=(0110) ：メッセージ (0110) 1000111 0100110 0010101 0001011 = (0110011) = v ： コード単語 このコード単語v を送信する。 v = (X1, X2, …, X5, X6, X7) エラー：e = (e1, e2, …, e7) が加わる。 受信単語を r = (r1, r2, …, r7) とすると、 r = v + e
となる。ここで、 X5 = X1+ X2+ X3 X6 = X1+ X2 + X4 X7 = X1 + X3+ X4 より、 X1 +X2 +X3 +X5 = 0 X1 +X2 +X4 +X6 = 0 X1 +X3 +X4 +X7 = 0 なので、 (位数 2 の有限体では −1 = 1 に注意) vHT = 0 が成り立つ。ただし、 H = 1110100 1101010 1011001 とする(H：パリティ検査行列)。 ◎ここで、H の各列を見ると、(111), (110), (101), (011), (100), (010), (001) となり、(000) を除く全ての01 の組合せが現れていることに注意されたい。従って、 rHT = (v + e)HT = vHT + eHT = eHT となる。ここで、rHT をs とおき、r のシンドロームと呼ぶ。 e = (0000000) → s = (000) e = (0000001) → s = (001) e = (0000010) → s = (010) e = (0000100) → s = (100) e = (0001000) → s = (011) e = (0010000) → s = (101) e = (0100000) → s = (110) e = (1000000) → s = (111) 以上により、1 ビットのエラーのときは、s から e が分かる。そこで、 r = v + e から v = r − e となる。そこで、v = (X1, X2, …, X5, X6, X7) が分かり、メッセージ u = (X1, X2, X3, X4) が手に入る。 一般に、k ビットのメッセージを、1 ビットのエラーの誤り訂正が出来るような符号化 をするためには、コード単語のビット数n が次の式を満たさなくてはならない。 n ≦ 2n−k− 1 k n k n 1 3 8 12 2 5 9 13 3 6 10 14 4 7 11 15 5 9 ・・・ ・・・ 6 10 ・・・ ・・・ 7 11 2036 2047
ハミングコードのまとめ 送りたいメッセージ u = (X1, X2, X3, X4) を用意する。 これを生成行列G を使ってコード単語 v = (X1, X2, …, X6, X7) にする。 v = uG (G： 生成行列) 通信路において、エラー e = (e1, e2, …, e6, e7) が加わる。 受信単語 r = (r1, r2, …, r6, r7) = v + e を受信者が受け取る。 パリティ検査行列H を使ってシンドローム s = rHT を計算する。 s = rHT = (v + e)HT = eHT (vHT = 0) 1 ビット以内の誤りであれば、s から e が求まる。 v = r − e よりコード単語が分かる。従ってメッセージ u が得られる。 【自由課題】どのようなG,H なら上と同様にできるか？ 参考文献 1) 宮川, 岩垂, 今井：符号理論 (昭晃堂) 2) 高橋：組合せ理論とその応用 (岩波全書) 3) 嵩, 都倉, 岩垂, 稲垣：符号理論 (コロナ社)
2.4
暗号
◎暗号と言うと何かキナ臭い感じがするが、個人のプライバシー保護や通信の安全性から 有用なテーマとなっている。 暗号 ：秘密通信の手段。通信文にいろいろな操作を施し、第三者が見ても意味がわから ない形に変換する技法。 【例】野球のサイン、デパートの放送、隠語 用途 ：暗号は、軍事関係の必要性から生じたが、現在では広く大衆化されつつある。 政府等の軍事・外交上の通信 ↓ 商取引上の重要な用件 ↓ 個人的通信(プライバシー保護) 安全性 『安全な』暗号方式の評価は、かなり困難である。昔は、統計的な不確定性によって評 価されていたが、現在ではその暗号を解読するための計算量で評価しようとしている。例 えば、『世界一早い計算機でも、解読に100 万年かかる』などと表現する。しかし、ある種 の工夫をすることによって、より短時間に解読出来るかも知れないという可能性がある。 統計的な不確定性 → 解読のための計算量 「計算安全性」 方式 暗号方式を大別すると、古典的暗号と公開鍵暗号にわけることができる。 古典的暗号：公開鍵暗号以外の暗号公開鍵暗号：暗号化の方法は公開されているが、復号の方法は秘密 ◎以下で利用する記号を説明する。 暗号化 復号化 暗号文 メッセージ
M
E
C
D
M
K
1K
2 鍵 鍵 暗号化(encryption) C = Ek1(M) 復号(decryption) M = Dk2(C) ∴ M = Dk2(Ek1(M)) (一般には、M = Ek1(Dk2(M)) が成立するとは限らない 。成立する場合もある。デジタ ル署名の項を参照せよ) 2.4.1 古典的暗号 ◎古典的暗号と言っても、決して『古くさい』暗号とは限らない。特に、ＤＥＳは現在の 標準的な方式である。 シーザー暗号 アルファベットの順で3 つ分ずらす。 E3(M) = M + 3 (mod 26) (M = 0, 1, ..., 25) D3(M) = M − 3 (mod 26) (M = 0, 1, ..., 25) Ａ→Ｄ Ｂ→Ｅ Ｃ→Ｆ … Ｚ→Ｃ 【例】 ＡＮＮＧＯＵ → ＤＱＱＪＲＸ 鍵の個数 25 個→全数検査でよい 単文字換字式暗号 アルファベット26 個の任意の置換をする。 【置換例】 ABCDEFGHIJKLMNOPQRSTUVWXYZ THUVICWBNFSPODZGJXQALYMRKE 【例】MESSAAGE → OIQQTTWI 鍵の個数 26！=4.032…× 1026 ◎鍵の個数はほぼ十分あるが、英語の冗長度から比較的容易に解読できる。 ［参考］ 英語におけるＡ∼Ｚ, 空白の出現頻度space 0.1859 I 0.0575 R 0.0484 A 0.0642 J 0.0008 S 0.0514 B 0.0127 K 0.0049 T 0.0796 C 0.0218 L 0.0321 U 0.0228 D 0.0317 M 0.0198 V 0.0083 E 0.1031 N 0.0574 W 0.0175 F 0.0208 O 0.0152 X 0.0013 G 0.0152 P 0.0152 Y 0.0164 H 0.0467 Q 0.0008 Z 0.0005 乱数による暗号 メッセージに｛0，1｝乱数を加える。 【例】 Ｍ：0100110101… メッセージ ｋ：0001010111… 乱数 ↓ ＸＯＲ Ｃ：0101100010… 暗号文 ｋ：0001010111… (暗号化と同じ)乱数 ↓ ＸＯＲ Ｍ：0100110101… メッセージ 鍵の個数 自由 乱数の性質により、安全性が決まる。 安全性の評価が困難 ◎『完全な乱数』であったら、『理論的』には解読は不可能である。しかし、『完全な乱 数』は存在するか？ 転置式暗号 平文を長さn の語 (ブロック) づつに分け、各ブロックごとに並べ換える 【転置例】 n = 5 12345 43152 【例】 Ｔ1 Ｏ2 Ｐ3 4 Ｓ5 Ｅ1 Ｃ2 Ｒ3 Ｅ4 Ｔ5 1 Ｃ2 Ｏ3 Ｄ4 Ｅ5 Ｐ Ｓ Ｏ Ｔ Ｒ Ｔ Ｃ Ｅ Ｅ Ｏ Ｅ Ｃ Ｄ 鍵の個数 n！ (n 個の並び換えの場合の数) DES 1973 年に米国商務省標準局 (ＮＢＳ) がコンピュータの暗号化に用いるアルゴリズムを公
募した。ＩＢＭ社が提案した方式が1977 年にＤＥＳ (Data Encryption Standard) として
発効した。64 ビットのメッセージ (8 文字) ごとに暗号化する 鍵の個数 56 ビットの鍵 256 【暗号化の要旨】(以下、参考までに・・・) 平文のブロックにある種の初期転置を施し、その転置されたブロックに、16 回の機能 的に同一な反復からなっている鍵に従属した複雑な変換をし、最後に初期転置の逆変換を する。 ［問題点］ 1)1980 年代には 1 日で全数検査ができる機械ができるであろう。(1977 年時点での Hellman などの批判) 2) 鍵は少なくとも 64 ビット，できれば 128 ビットに増やすべきである。 3) 設計を公表すべきである。
＊鍵が56 ビットなので、鍵の個数は全部で 256(7.205…× 1016) 個ある。1 つの鍵を調べる のに1 マイクロ秒 (100 万分の 1 秒) かかるとすると、全部の鍵を検査するのに 2283 年か かる。しかし、100 万個のＬＳＩチップを使えば、1 日で検査が終了する。さらに確率的 には半分の鍵を確認すればよいので、半日ですむ。 注意: 現時点では実際的な時間で、解読が可能になった。そこで、鍵の長さを増やすこと が検討されている。 ◎ＤＥＳは、標準的な暗号方式として一応定着している。 2.4.2 公開鍵暗号 ◎暗号化の方法は公開されているが、復号の方法は秘密である暗号方式。これは、一見わ れわれの常識に反している。例えば、金庫の鍵や番号は、閉める場合も開ける場合も同じ ものを利用している。従って、閉める方法(鍵や番号) を公開すると、開ける方法がばれて しまう。しかし、巧妙な方法で「閉める鍵」から「開ける鍵」を導くことを防いでいる。 以下、EAをA 君のための鍵を使った暗号化、DAをA 君のための鍵を使った復号化と する。 暗号化 復号化 暗号文 メッセージ
M
E
C
D
M
A
君
Β
君
B B 公開 秘密 ◎このように暗号化の方法(鍵) はＡ君もＢ君も (あたかも電話帳をもっているように) 知っ ている。しかし、復号の方法は自分の分しか知らない。 公開鍵暗号の条件(1)C = EA(M) なら DA(C) = M。つまり DA(EA(M)) = M。
(2)EA からDA を計算するのは困難。
デジタル署名の条件
man crypt
CRYPT(1) USER COMMANDS CRYPT(1) NAME
crypt - encode or decode a file SYNOPSIS
crypt [ password ] DESCRIPTION
crypt encrypts and decrypts the contents of a file. crypt reads from the standard input and writes on the standard output. The password is a key that selects a particular transformation. If no password is given, crypt demands a key from the terminal and turns off printing while the key is being typed in. crypt encrypts and decrypts with the same key:
example% crypt key <clear.file >encrypted.file example% crypt key <encrypted.file | pr will print the contents of clear.file.
Files encrypted by crypt are compatible with those treated by the editors ed(1), ex(1) and vi(1) in encryption mode. The security of encrypted files depends on three factors: the fundamental method must be hard to solve; direct search of the key space must be infeasible; "sneak paths" by which keys or cleartext can become visible must be minimized. crypt implements a one-rotor machine designed along the lines of the German Enigma, but with a 256-element rotor. Methods of attack on such machines are widely known, thus crypt provides minimal security.
The transformation of a key into the internal settings of the machine is deliberately designed to be expensive, that is, to take a substantial fraction of a second to compute. However, if keys are restricted to (say) three lower-case letters, then encrypted files can be read by expending only a substantial fraction of five minutes of machine time. Since the key is an argument to the crypt command, it is potentially visible to users executing ps(1) or a derivative command. To minimize this possibility, crypt takes care to destroy any record of the key immediately upon entry. No doubt the choice of keys and key security are the most vulnerable aspect of crypt.
FILES
/dev/tty for typed key SEE ALSO
des(1), ed(1), ex(1), ps(1), vi(1), makekey(8) RESTRICTIONS
This program is not available on software shipped outside the U.S. 共立出版「蟻塔」1995/11/12 テキサス便り (3) 岡本栄司より 補足：DES の解読 三菱電機の松井先生により、DES の解読がなされた。ワークステーション 12 台を 50 日間動かして、暗号化鍵を割だした。
RSA
法
(Rivest-Shamir-Adleman
の方法
)
通信文を 0∼(n − 1) とする。 n は、素数 p, q の積：n = pq E(M) = Me (mod n) 暗号化 D(C) = Cd (mod n) 復号 ただし、 Xed = X (mod n) となるように、e と d を決めておく。 準 備フェルマーの(小) 定理 p が素数で (a, p) = 1 のとき、 ap−1 = 1 (mod p) ただし、(a, p) は a と p の最大公約数 (すなわち、ap = a (mod p) が任意の a について成り立つ) 【証明】 1, 2, 3, · · · , p − 1 (1) の全てにa を掛け、 a, 2a, 3a, · · · (2) とする。p を法として (2) には同じ数がない。(もし、存在すれば、ka = ma + np なる、p 未満の非負の整数k, m, n があり、p が素数であるのに反する)。 したがって、(1) と (2) は p を法として同じ集合となり、それらの全ての積も p を法として 等しくなる。すなわち、 ap−1(p − 1)! = (p − 1)! (mod p) (p − 1)!は p で割り切れないから、 ap−1= 1 (mod p) となる。 (証明終わり) オイラーの定理(参考) (a, r) = 1 のとき、 aφ(r)= 1 (mod r) ただし、φ(r) は、r 以下で r と互いに素な正の整数の個数。 p, q が素数のとき φ(pq) = (p − 1)(q − 1)。 e と d の作り方 (p − 1)(q − 1) と互いに素な e を任意に選ぶ。 ue + v(p − 1) = 1 xe + y(q − 1) = 1 なる、整数u, v, x, y を求める。
∴(u − x)e = −v(p − 1) + y(q − 1)
この左辺は、p − 1 と q − 1 の最大公約数 m で割り切れる。e は、(p − 1)(q − 1) と素なの で、u − x が m の倍数となる。 u − x = w(p − 1) + t(q − 1) なるw と t が存在する。 u − w(p − 1) = x + t(q − 1) をd とすればよい。このとき、 ed = eu − ew(p − 1) = 1 − (ew + v)(p − 1) = 1 (mod p − 1)
ed = ex + et(q − 1) = 1 + (et − y)(q − 1) = 1 (mod q − 1) が成立する。従って、 Xed = X (mod p) Xed = X (mod q) となり、 Xed = X (mod n) が得られる。 ◎このアルゴリズムで、n の素因数分解 (p, q を求めること) が本質的である。すなわち、 現在公表されているアルゴリズムで、50 桁の素因数分解をするには (高速な計算機でも) 数千年かかる。 素数の判定より、素因数分解が困難。 すなわち、50∼70 桁の数が素数かどうかを判定するのは、高速の計算機で 1 時間もあれ ば十分である。 61 桁の素数の例： 2200+ 235 【例】: p = 11，q = 13， 完全に秘密 n = 143 公開 e = 7 公開 d = 43 受信者のみ知っている M = 5 M ：送りたい平文 M7 = C (mod 143) C：暗文 この場合、 57 = 78125 = 47 (mod 143) より、暗文 ’47’ を送る。受信者は、本人のみが知っている 43 を使って、 4743= 79470 · · · = 5 (mod 143) を計算して、’5’ を得る。 ◎ここで、n は公開されている。p，q は (誰に対しても) 非公開。e は一般に対して公開さ れているが、d は受信者以外には非公開である。n は 100 桁程度であれば、n から p や q を 求めるのは不可能。 【質問】では、この暗号によるシステムを初めに作る人はどうするのですか？ 【答え】50 桁程度の素数 p, q を適当に捜して、n = pq を計算するのは容易です。でも、そ のあとp と q は誰に対しても秘密にしなくてはなりません。 デジタル署名 公開鍵暗号のように誰でも暗文を作れるシステムでは、送信した人の確認が不可欠です。 ☆A 君からＢ君にデジタル署名付きの通信をする方法 A 君： S = DA(M) を作り、C = EB(S) を送る。 B 君：
C から DB(C) = DB(EB(S)) = S で S を取り出す。 (S を保存する) EA(S) = EA(DA(M)) = M を取り出す ☆なぜ、署名になるのか (1)S は DAを使っているので、A 君しか作れない。 (2)C から S を取り出すのは、DBを使っているので、Ｂ君しか取り出せない。(通信の秘 密の保持) (3)S から、公開されている EAによってM が取り出せるので、署名の確認が第 3 者によっ ても可能である。 公開鍵暗号の利点 1) 鍵の種類が少なくてよい。 k 人相互の連絡の場合 ◎従来の方法 k(k − 1) ／ 2 ◎公開鍵 2k 【例】 k = 100 k(k − 1) ／ 2 = 4950 k = 1000 k(k − 1) ／ 2 = 499500 2) デジタル署名が可能 RSA による公開鍵暗号の問題点 1)DAやEAの計算量が多い。 → ハードウェア化 2)n の素因数分解の計算量の理論が完成されていない。ひょっとしたら、短期間に数 100 桁の数の素因数分解をするアルゴリズムが存在するかもしれない。
