共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版

暗号 ｈｔｔｐｓ：//ｗｗｗ．・・・ ◆インターネットで用いられる暗号 SSL（セキュアソケットレイヤー） 　　　　　　　　　　・・・インターネットで情報を暗号化して 　　　　　　　　　　　　　送受信するプロトコル（通信規約） 　　URLにおいて、 　　　ｈｔｔｐがｈｔｔｐｓ（Hypertext Transfer Protocol Security）に 　　　なっている ◆暗号の種類 　　　　・共通鍵方式 　　　　・公開鍵方式 　　　　　　　　　　　　　など ｈｔｔｐｓ：//ｗｗｗ．・・・

共通鍵方式 インターネット 暗号化 復号 カード 番号 カード 番号 暗号 共通鍵ｋ 共通鍵ｋ 同じ鍵⇒どのようにして渡すのか？ 知られたらすぐに暗号が解かれる 文字や単語の出現頻度から暗号が解かれてしまう。 代表的なもの　シーザー暗号など

シーザー暗号 例１ アルファベット表を3文字ずらす → ずらす文字数を「鍵」とする （例） TOP SECRET → WRS VHFUHW 例１　アルファベット表を3文字ずらす 　　　　→　ずらす文字数を「鍵」とする 　　　（例）　　TOP　SECRET　→　WRS　VHFUHW 問１　先の表を用いて次の暗号を解読せよ。 　　DQJRXBDGH 　　　　　　　　（答え）　　　　ANGOUYADE 練習１　先の表を用いて、好きな言葉を暗号化せよ。 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z ↓

公開鍵方式 １ インターネット 復号 暗号化 暗号解読 みんなが知っている 秘密鍵ｄがないと 膨大な時間がかかる ⇒暗号解読を諦める カード 公開鍵方式　１ インターネット カード 番号 カード 番号 暗号 復号 暗号化 公開鍵 ｎ、e 秘密鍵 ｄ 暗号解読 みんなが知っている 秘密鍵ｄがないと 膨大な時間がかかる ⇒暗号解読を諦める

公開鍵方式 － RSA暗号 ＲＳＡ暗号 大きな整数の素因数分解が非常に難しいということを 用いた暗号方式。 　　　　大きな整数の素因数分解が非常に難しいということを 　　　　用いた暗号方式。 　　RSAは、考案者であるマサチューセッツ工科大学(MIT)の 　　研究者3名、Rivest（リベスト）,Shamir（シャミア）,Adleman（エイドルマン）の頭文字　 （1977年頃） 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 　　　　桁数の多い素因数分解が非常に困難 　　　　　　　　　　　↓ 　　　　人間の寿命ほどの時間がかかる（２００桁） 　　　　暗号を解読するのを諦める 　　　　　　　　セキュリティー 暗号の解きにくさを「強度」と呼ぶ

素因数分解をしてみよう 実習１ 次の数を素因数分解せよ。 ① （答え） ② （答え） ③ （答え） ④ （答え） ①、②は自分でする。 　実習１　次の数を素因数分解せよ。 　　　①、②は自分でする。 　　　③は、奇数出席番号の人 　　　　　　　　　　出席番号＋４０× ｎで割る。（ｎ＝０、１、２、・・・） 　　　　　　　　　　（例：出席番号３番　⇒　３、４３、８３、・・・で割る） 　　　④は、偶数出席番号の人 　　　　　　　　　　（偶数出席番号-１）＋４０× ｎで割る。（ｎ＝０、１、２、・・・） 　　　　　　　　　　（例：出席番号４番　⇒　３、４３、８３、・・・で割る） 　　　　　　　　　　※出席番号４１番以上の人は、先生の指示した数字で割る。 　　　①　　　　　　　　 （答え） 　　　②　　　　　　　　 （答え） 　　　③　　　　　　　　 （答え） 　　　④　　　　　　　　 （答え）

公開鍵と秘密鍵を作ろう① ① ２つ素数　　　、　　　を選ぶ。 　　　例：　　　　　　、　　　　　　：非公開 ②　　　　　　　　　　　をつくる 　 　　　　　　　　　　　　　　：公開鍵

公開鍵と秘密鍵を作ろう② ③　　　　　　　　　　　　　　　　　　　をつくる 　　　　　　　　　　　　　　　　　　　：非公開

公開鍵と秘密鍵を作ろう③ ④　　　と互いに素な数　　を選ぶ　（　　　　　　　　　　） 　　 　　　　（１以外の共通の約数をもたないもの） 　　　　　　40と互いに素　→　3　　　　　　 　　　　　　⇒　　　　　　　　　　：公開鍵

公開鍵と秘密鍵を作ろう④ ③ を で割って１余るような整数 を求める （ ） すなわち となる整数 探す ③ 　　　を　　で割って１余るような整数　　　を求める　　 　　　　　　　　　　　　　　　　　　　　　　　　　　　　（　　　　　　　　　　　） 　　　すなわち 　　　　　　　　　　　　　　　　　　　　　となる整数　　探す 　　　　　　　　　　　　　　の形の　41、81、・・・と探していく　　　　　　 　　　　81＝3×27で適合する 　　→　　　　　　　　：秘密鍵

暗号化して送る 平文（ひらぶん）を暗号に変換 　　平文　　　⇒　暗号 　　平文　　　　　　　　とする（　　　　　　　　　） 　　公開鍵　　　　　　、 　　⇒ 　　　　　　　　　　　　　　　　商　　 余り 　　⇒　暗号　　　　　　　　　　

復号（暗号を元の平文に戻す） 暗号　 公開鍵 秘密鍵　 ・　　　　　　　　　　の余り　⇒　平文 　　　　　↓ 大変な計算！⇒　あまりの理論を使う

仕組み 平文 暗号 平文 公開鍵 秘密鍵 送信者 鍵生成者、受信者 2つの素数 ｐ＝５ ｑ＝１１ n=55 e=3 d=27 n=55

あまりの理論 2,6,10,14,… あまりの記号 modulo（モデュロー）の略、「モッド」と読む 例２ は、 0,4,8,12, … あまりの記号　　　　　 　　modulo（モデュロー）の略、「モッド」と読む 　例２　　　　　　　　　　　　　　　　は、　　　　 　　　　　　　　　　　　　　　　　　　　とかく。 　練習２　　　　　　　　　　　　　　　を、 　　　　　　　　　　　　　　　　　　　　の形にせよ。 　 0,4,8,12, … 1,5, 9,13，… 3,7,11,15, … mod　4 2,6,10,14,…

合同式　１ 　　と　　を正の整数　　で割ったときのあまりが等しいときに、 　　と　　は　　を法として合同であるといい、 とかく。 例３ 　　　　　よって

合同式 ２ 練習３ 次の式は正しいか、誤りか。 （１） ○ 28=4×6+4 34=5×6+4 （２） （３） 合同式　２ 練習３　次の式は正しいか、誤りか。 　　（１） 　　（２） 　　（３） 　　（４） 　　（５） ○　28=4×6+4 　　 34=5×6+4 ○　17=3×5+2 　　　 2=0×5+2 ×　123=11×11+2 　　 456=41×11+5 ×　　8=1×5+3 　　 64=12×5+4 ○　　64=21×3+1　　　　　　　　　 　　 343=114×3+1

modの演算法則１ 　　　　　　　　　　　　　　　　、　　　　　　　　　　　　　　　　ならば、 （１） （２）　　 （３） 　　　　　　　　　　ただし、　　は自然数 説明 数値で確認 証明 証明 証明

演算の意味 、 のとき 例 6 ≡10 (mod 4) （←6,10は4で割るとあまり2で同じ） 　　　　　　　　　　　　　　　、　　　　　　　　　　　　　　　のとき 例 　　6 ≡10 (mod 4)　　　（←6,10は4で割るとあまり2で同じ） 　　9 ≡13 (mod 4)　　　（←9,13は４で割るとあまり1で同じ） 　　このとき 　　　　6+9 ≡10+13 (mod 4) 　　　　　15 ≡23 (mod 4) 　 　　　→　15、23は、4で割ると、あまり3なので成り立つ

数値で確認 練習４　　　　　　、　　　　、　　　　　、　　　　　、　　　　　、　　 　　　　　とするとき、次の式が成り立つことを確認せよ。 　　（１） 　　（２） 　　（３） 　　（４） 　　（５） 　　（６）

modの計算法則１ （１）の証明 より ・・・① （ 、 を で割るとあまりが同じなので、 を で割るとあまりは０であるので） 同様に、 　　　　　　　　　　　　　　　　　　より　　　　　　　　　　　　　　　　・・・① 　　　　（　　、　　を　　　で割るとあまりが同じなので、　 　　　　　　　　　　を　　　で割るとあまりは０であるので） 　　同様に、 　　　　　　　　　　　　　　　　　　より　　　　　　　　　　　　　　　　・・・② 　　①、②を用いて　 　　※　　　　　　　　　　　　　　　　　　　　　の証明も同様　　　　　

modの計算法則１ （２） の証明 　　　　　　　　　　　　　　　　より　　　　　　　　　　　　　　　　　・・・① 　　　　　　　　　　　　　　　　より　　　　　　　　　　　　　　　　　・・・② 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 （①、②より） 　　　　　　　　　　　　　 よって 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　【証明終わり】

modの計算法則１ （３）の証明 数学的帰納法で証明する （ⅰ） のとき より よって、成り立つ （ⅱ） のとき、 が成り立つと仮定すると、 （ⅰ）　　　　　のとき　　　　　　 　　　　　　　　　　　　　　　　　　　より 　　　　よって、成り立つ （ⅱ）　　　　　のとき、　　　　　　　　　　　　　 が成り立つと仮定すると、 　　　このときと、　　　　　　　　　　　　　とmodの計算法則１（２）から 　　　　　よって、　　　　　　　のときにも成り立つ 　ゆえに、（ⅰ）、（ⅱ）より、　　　　　　　　　　　　　　が成り立つ 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　【証明終わり】

modの演算法則２ 　　　と　　　が互いに素で､ 　　　　　　　　　　　　　　　　かつ　　　　　　　　　　　　　　　 ならば、 数値で確認 証明

数値で確認 練習５　　　　　　　、　　　　　　、　　　　　、　　　　　　とするとき、 　　　　　次の式が成り立つことを確認せよ。 　　　（１）　　　　　　　　　　　　　かつ 　　　（２）

mod演算法則２の証明 より、ある自然数 が存在し、 ・・・① 同様に、 より、ある自然数 が存在し、 ・・・② ①－②より、 　　　　　　　　　　　　　より、ある自然数　　　　が存在し、 　　　　　　　　　　　　　　　　　　　　　・・・① 同様に、　　　　　　　　　　　　より、ある自然数　　　が存在し、 　　　　　　　　　　　　　　　　　　　　　・・・② ①－②より、 このとき、　　と　　が互いに素なので、　　　は　　　で割り切れる はずであるので、ある自然数　　　　に対し、　　　　　　　　　　　　　　　　　　 とかける。 したがって、 すなわち、　　　　　　　　　　　　　　　　　　　　　　　　【証明終わり】

フェルマーの小定理 　　　：　素数 　　　：　　　　と互いに素 　（　　を　　　　　　乗したものは、　　　で割ると１余る） 数値で確認 例 証明 【参考】　フェルマーの最終定理

フェルマーの小定理 確認 問６ 次の場合について、下の表にあまりを記入し、考察せよ。 （１）素数 とするとき、1～6の整数は、 と互いに フェルマーの小定理　確認 問６　次の場合について、下の表にあまりを記入し、考察せよ。 　　（１）素数　　　　　　とするとき、1～6の整数は、　　　と互いに 　　　　素なので、　　　　　　　　　の表を作る。 1 2 3 4 5 6 1 2 3 4 5 6 表計算で確認

フェルマーの小定理　確認 素数でない　　　　　　では 1 2 3 4 5 6 7 1 2 3 4 5 6 7

フェルマーの小定理の証明 　　　は、　　　と互いに素なので、 両辺から　　　　　　　を約して 理由

の理由 と は で割ったあまりで、順番は異なるが同じもの ならば、 ◆背理法で証明する と仮定すると、 となり、 　　　　　　　　　　　　　と　　　　　　　　　　　　　　　　　　　は 　　で割ったあまりで、順番は異なるが同じもの 　　　　　　ならば、 ◆背理法で証明する 　　　　　　　　　　　　　　　　と仮定すると、 　　　　　　　　　　　　　　　　　　　となり、 　　　　が素数なので、　　　　　　となり、矛盾する。 　　ゆえに、　　　　　　ならば、 　すなわち、　　　　　　　　　　　　　と 　　はすべて、異なるあまりである。

参考　フェルマーの大定理（最終定理） 　　自然数　　　　　に対して　　　　　　　　　　　を満たす 　　 自然数　　　　　　　　は存在しない。

オイラーの定理 　　　　　：正の整数 　　　　　：　　と互いに素な整数 　　　　　：　　　未満の　　と互いに素な自然数の個数 　　　　　　　　　　　　　　　　　　　　　　　（オイラー関数）

オイラー関数 オイラー関数 は、 未満の と互いに素な自然数の個数 （ⅰ） （ ：素数）のとき、 （ⅱ） （ 、 ：素数）のとき、 《参考》 オイラー関数　　　　　は、　未満の　　と互いに素な自然数の個数 （ⅰ）　　　　　　　（　　：素数）のとき、 （ⅱ）　　　　　　　（　　、　　：素数）のとき、 《参考》 （ⅲ）　　　　　（　　　：素数、　：整数）のとき、 （ⅳ）　　　　　　　　　　　　　の素因数分解をとすると、 数値で確認 数値で確認

オイラー関数を確認① （ⅰ）の理由 素数 と 未満の整数は、互いに素なので、 ｛1，2，3.，・・・， ｝の 個であり、 　　　素数　　と　　未満の整数は、互いに素なので、 　　　｛1，2，3.，・・・，　　　｝の　　　　　　個であり、 例　　素数5と互いに素な5未満の整数は、 　　　　｛1,2,3,4｝であるので、　　　　　　　 　　　　オイラー関数　　　　　　　　　　　と一致する 　　このとき、オイラーの定理は、フェルマーの小定理と一致する。 練習　　　　　　、　　　　　　のとき、　　　　　　と互いに素な数の 　　　　個数を実際に上げて求めたものと　オイラー関数で 　　　　求めたものと比較せよ。

オイラー関数を確認② （ⅱ）の理由 、 のとき、 この数と互いに素な数は、｛1,2,4,7,8,11,13,14}の８個。 　　　　　　　　　、　　　　　　のとき、 　　　この数と互いに素な数は、｛1,2,4,7,8,11,13,14}の８個。 　　　オイラー関数で計算すると、 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　個となり一致する。 練習　　　　　　　、　　　　　　のとき、　　　　　　　　　　　　と 　　　　互いに素な数の個数を実際に上げて求めたものと 　　　　オイラー関数で求めたものと比較せよ。

オイラーの定理（特殊な場合） 　　、　　：素数 ：　　、　　　と互いに素な整数 ：整数 証明 表計算で確認

オイラーの定理（特殊な場合）の証明１ 、 は素数なので、フェルマーの定理より ・・・① ・・・② よって、 　　、　　は素数なので、フェルマーの定理より 　　　　　　　　　　　　　　　　　 　・・・① 　　　　　　　　 　　　　　　　　　　・・・② よって、 　　　　　　　　　　　　　　　　　　　　　 （←①とmod演算法則１（３）より） 　　　　　　 　　　　　　　　　　　　　　　 ・・・③ 証明の続きへ

オイラーの定理（特殊な場合）の証明２ 同様に ・・・④ ゆえに、③、④において、modの計算法則２を用いると、 ［証明終］ 　　　　　　　　　　　　　　　　　　　　　　　　　・・・④ ゆえに、③、④において、modの計算法則２を用いると、 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　［証明終］

暗号の数学的仕組み 送信側　　　　　　　　　　　　　　　　　　　　→　暗号を生成 　　　　　　　　　　　　暗号　　　を送る 受信側　　　　　　　　　　　　　　　　　　　　→　平文を復号

復号ができる仕組み　１ 　　　　　　　　　　　　　　　　　（←指数の法則　　　　　　 と　　　　より） 　　　　　　　　←鍵生成の⑤で、 　　　　　　　　　　　　を　　で割って１あまるような整数が 　　　　　　　　　すなわち　　　　　　　 　　　　　　（　　は商） 　　　　　

復号ができる仕組み ２ （←指数の法則 より） （←オイラーの定理（特殊な場合） とmodの計算法則１（２）より） →平文 になる。 復号ができる仕組み　２ 　　　　　　　　　　　　　　　　　　　　　（←指数の法則　　　　　　　　より） 　　　　　　　　 　　　　　　　　　　　　 （←オイラーの定理（特殊な場合） 　　　　　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　とmodの計算法則１（２）より） 　　→平文　　　になる。 　　　　よって、　　　　　　　　　を計算すれば平文　　　がわかる。

復号１（暗号を平文に戻す） ◆繰り返し2乗法 を法とする を効率よく計算する方法 これを用いると の余りが求まり、 　　　を法とする　　　を効率よく計算する方法 　　これを用いると　　　　　　　　　の余りが求まり、 　　暗号が復号でき、平文が求められる。 ◆　　　　　　　　　　の余りを求める場合

復号２ ◆ ２３２ （mod ５５） 、２３４ （mod ５５） 、 ２３８ （mod ５５）を 用意しておく 　　　≡３４　　　　　　　　←　　　　　　　　　　　　　より、あまり３４ ２３４ ≡３４２ （mod　５５）　 ← 　　　　　　　　　　　と 　　　　　　　　　　　　　　　　　　　mod演算法則１（３）より 　　　≡１１５６ （mod　５５） ←　 　　　≡１　　　　　　　　　　　 ←　　　　　　　　　　　　　より、あまり１ ２３８ ≡１２ （mod　５５）　 ← 　　　　　　　　　　　　　　と 　　　　　　　　　　　　　　　　　　　　mod演算法則１（３）より 　　 　 ≡１　

復号３ ２３２７ ≡ ２３２ × ２３４ × ２３４ × ２３８× ２３８ × ２３１ （mod　５５） 　　　　≡３４×１×１×１ ×１ ×２３ （mod　５５） 　　　　　　　　　　　　　←先の計算結果とmodの演算法則１（２）より 　　　　≡７８２ （mod　５５） 　　　 ≡１２　 　　　　⇒平文 Ｍ＝１２

実習 公開鍵： 暗号： 平文： （１） 鍵生成者 鍵を生成 （２）回収、再配布 （３）送信者 暗号に変換 （１）　鍵生成者　鍵を生成 （２）回収、再配布 （３）送信者　　暗号に変換 　　　　　　　　（平文　　　として好きな数字（２桁、　　　　　　）を考え、暗号　　　に変換） （４）回収、再配布 （５）受信者　　暗号解読 （６）回収、再配布 （７）送信者　　　　　　　　　　　　　 公開鍵： 暗号： 平文： 送信チェック（○、×と理由を記入） 正しく暗号解読されている 正しく暗号解読されていない できなかった理由 実習プリント 計算サイト

参考文献、参考URL 明星学園高校 　　　http://www.tokojoken.jp/johosyakai/rasangou.files/frame.htm 神戸大学　教養原論（数理の世界--「現象の数理」「数理解析と社会」）の 　　授業用のページ（計算サイト） 　　　http://herb.h.kobe-u.ac.jp/RSA.html 高校生のための暗号論入門 　　　http://www.nikonet.or.jp/spring/sanae/report/angou/angou.htm 　http://mathmuse.sci.ibaraki.ac.jp/crystalmind/Lesson5.htm 　http://isw3.naist.jp/~kaji/lecture/inf-theory2/Jul18.ppt 　http://www.apec.aichi-c.ed.jp/project/joho/jissyuu/PGP/pgp.xls 　ブルーバックス　素数入門　芹沢　正三　講談社