Download presentation
Presentation is loading. Please wait.
1
共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版
2
暗号 https://www.・・・ ◆インターネットで用いられる暗号 SSL(セキュアソケットレイヤー)
・・・インターネットで情報を暗号化して 送受信するプロトコル(通信規約) URLにおいて、 httpがhttps(Hypertext Transfer Protocol Security)に なっている ◆暗号の種類 ・共通鍵方式 ・公開鍵方式 など https://www.・・・
3
共通鍵方式 インターネット 暗号化 復号 カード 番号 カード 番号 暗号 共通鍵k 共通鍵k 同じ鍵⇒どのようにして渡すのか?
知られたらすぐに暗号が解かれる 文字や単語の出現頻度から暗号が解かれてしまう。 代表的なもの シーザー暗号など
4
シーザー暗号 例1 アルファベット表を3文字ずらす → ずらす文字数を「鍵」とする (例) TOP SECRET → WRS VHFUHW
例1 アルファベット表を3文字ずらす → ずらす文字数を「鍵」とする (例) TOP SECRET → WRS VHFUHW 問1 先の表を用いて次の暗号を解読せよ。 DQJRXBDGH (答え) ANGOUYADE 練習1 先の表を用いて、好きな言葉を暗号化せよ。 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 ↓
5
公開鍵方式 1 インターネット 復号 暗号化 暗号解読 みんなが知っている 秘密鍵dがないと 膨大な時間がかかる ⇒暗号解読を諦める カード
公開鍵方式 1 インターネット カード 番号 カード 番号 暗号 復号 暗号化 公開鍵 n、e 秘密鍵 d 暗号解読 みんなが知っている 秘密鍵dがないと 膨大な時間がかかる ⇒暗号解読を諦める
6
公開鍵方式 - RSA暗号 RSA暗号 大きな整数の素因数分解が非常に難しいということを 用いた暗号方式。
大きな整数の素因数分解が非常に難しいということを 用いた暗号方式。 RSAは、考案者であるマサチューセッツ工科大学(MIT)の 研究者3名、Rivest(リベスト),Shamir(シャミア),Adleman(エイドルマン)の頭文字 (1977年頃) 桁数の多い素因数分解が非常に困難 ↓ 人間の寿命ほどの時間がかかる(200桁) 暗号を解読するのを諦める セキュリティー 暗号の解きにくさを「強度」と呼ぶ
7
素因数分解をしてみよう 実習1 次の数を素因数分解せよ。 ① (答え) ② (答え) ③ (答え) ④ (答え) ①、②は自分でする。
実習1 次の数を素因数分解せよ。 ①、②は自分でする。 ③は、奇数出席番号の人 出席番号+40× nで割る。(n=0、1、2、・・・) (例:出席番号3番 ⇒ 3、43、83、・・・で割る) ④は、偶数出席番号の人 (偶数出席番号-1)+40× nで割る。(n=0、1、2、・・・) (例:出席番号4番 ⇒ 3、43、83、・・・で割る) ※出席番号41番以上の人は、先生の指示した数字で割る。 ① (答え) ② (答え) ③ (答え) ④ (答え)
8
公開鍵と秘密鍵を作ろう① ① 2つ素数 、 を選ぶ。 例: 、 :非公開 ② をつくる :公開鍵
9
公開鍵と秘密鍵を作ろう② ③ をつくる :非公開
10
公開鍵と秘密鍵を作ろう③ ④ と互いに素な数 を選ぶ ( ) (1以外の共通の約数をもたないもの) 40と互いに素 → 3 ⇒ :公開鍵
11
公開鍵と秘密鍵を作ろう④ ③ を で割って1余るような整数 を求める ( ) すなわち となる整数 探す
③ を で割って1余るような整数 を求める ( ) すなわち となる整数 探す の形の 41、81、・・・と探していく 81=3×27で適合する → :秘密鍵
12
暗号化して送る 平文(ひらぶん)を暗号に変換 平文 ⇒ 暗号 平文 とする( ) 公開鍵 、 ⇒ 商 余り ⇒ 暗号
13
復号(暗号を元の平文に戻す) 暗号 公開鍵 秘密鍵 ・ の余り ⇒ 平文 ↓ 大変な計算!⇒ あまりの理論を使う
14
仕組み 平文 暗号 平文 公開鍵 秘密鍵 送信者 鍵生成者、受信者 2つの素数 p=5 q=11 n=55 e=3 d=27 n=55
15
あまりの理論 2,6,10,14,… あまりの記号 modulo(モデュロー)の略、「モッド」と読む 例2 は、 0,4,8,12, …
あまりの記号 modulo(モデュロー)の略、「モッド」と読む 例2 は、 とかく。 練習2 を、 の形にせよ。 0,4,8,12, … 1,5, 9,13,… 3,7,11,15, … mod 4 2,6,10,14,…
16
合同式 1 と を正の整数 で割ったときのあまりが等しいときに、 と は を法として合同であるといい、 とかく。 例3 よって
17
合同式 2 練習3 次の式は正しいか、誤りか。 (1) ○ 28=4×6+4 34=5×6+4 (2) (3)
合同式 2 練習3 次の式は正しいか、誤りか。 (1) (2) (3) (4) (5) ○ 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
18
modの演算法則1 、 ならば、 (1) (2) (3) ただし、 は自然数 説明 数値で確認 証明 証明 証明
19
演算の意味 、 のとき 例 6 ≡10 (mod 4) (←6,10は4で割るとあまり2で同じ)
、 のとき 例 6 ≡10 (mod 4) (←6,10は4で割るとあまり2で同じ) 9 ≡13 (mod 4) (←9,13は4で割るとあまり1で同じ) このとき 6+9 ≡10+13 (mod 4) 15 ≡23 (mod 4) → 15、23は、4で割ると、あまり3なので成り立つ
20
数値で確認 練習4 、 、 、 、 、 とするとき、次の式が成り立つことを確認せよ。 (1) (2) (3) (4) (5) (6)
21
modの計算法則1 (1)の証明 より ・・・① ( 、 を で割るとあまりが同じなので、 を で割るとあまりは0であるので) 同様に、
より ・・・① ( 、 を で割るとあまりが同じなので、 を で割るとあまりは0であるので) 同様に、 より ・・・② ①、②を用いて ※ の証明も同様
22
modの計算法則1 (2) の証明 より ・・・① より ・・・② (①、②より) よって 【証明終わり】
23
modの計算法則1 (3)の証明 数学的帰納法で証明する (ⅰ) のとき より よって、成り立つ (ⅱ) のとき、 が成り立つと仮定すると、
(ⅰ) のとき より よって、成り立つ (ⅱ) のとき、 が成り立つと仮定すると、 このときと、 とmodの計算法則1(2)から よって、 のときにも成り立つ ゆえに、(ⅰ)、(ⅱ)より、 が成り立つ 【証明終わり】
24
modの演算法則2 と が互いに素で、 かつ ならば、 数値で確認 証明
25
数値で確認 練習5 、 、 、 とするとき、 次の式が成り立つことを確認せよ。 (1) かつ (2)
26
mod演算法則2の証明 より、ある自然数 が存在し、 ・・・① 同様に、 より、ある自然数 が存在し、 ・・・② ①-②より、
より、ある自然数 が存在し、 ・・・① 同様に、 より、ある自然数 が存在し、 ・・・② ①-②より、 このとき、 と が互いに素なので、 は で割り切れる はずであるので、ある自然数 に対し、 とかける。 したがって、 すなわち、 【証明終わり】
27
フェルマーの小定理 : 素数 : と互いに素 ( を 乗したものは、 で割ると1余る) 数値で確認 例 証明 【参考】 フェルマーの最終定理
28
フェルマーの小定理 確認 問6 次の場合について、下の表にあまりを記入し、考察せよ。 (1)素数 とするとき、1~6の整数は、 と互いに
フェルマーの小定理 確認 問6 次の場合について、下の表にあまりを記入し、考察せよ。 (1)素数 とするとき、1~6の整数は、 と互いに 素なので、 の表を作る。 1 2 3 4 5 6 1 2 3 4 5 6 表計算で確認
29
フェルマーの小定理 確認 素数でない では 1 2 3 4 5 6 7 1 2 3 4 5 6 7
30
フェルマーの小定理の証明 は、 と互いに素なので、 両辺から を約して 理由
31
の理由 と は で割ったあまりで、順番は異なるが同じもの ならば、 ◆背理法で証明する と仮定すると、 となり、
と は で割ったあまりで、順番は異なるが同じもの ならば、 ◆背理法で証明する と仮定すると、 となり、 が素数なので、 となり、矛盾する。 ゆえに、 ならば、 すなわち、 と はすべて、異なるあまりである。
32
参考 フェルマーの大定理(最終定理) 自然数 に対して を満たす 自然数 は存在しない。
33
オイラーの定理 :正の整数 : と互いに素な整数 : 未満の と互いに素な自然数の個数 (オイラー関数)
34
オイラー関数 オイラー関数 は、 未満の と互いに素な自然数の個数 (ⅰ) ( :素数)のとき、 (ⅱ) ( 、 :素数)のとき、 《参考》
オイラー関数 は、 未満の と互いに素な自然数の個数 (ⅰ) ( :素数)のとき、 (ⅱ) ( 、 :素数)のとき、 《参考》 (ⅲ) ( :素数、 :整数)のとき、 (ⅳ) の素因数分解をとすると、 数値で確認 数値で確認
35
オイラー関数を確認① (ⅰ)の理由 素数 と 未満の整数は、互いに素なので、 {1,2,3.,・・・, }の 個であり、
素数 と 未満の整数は、互いに素なので、 {1,2,3.,・・・, }の 個であり、 例 素数5と互いに素な5未満の整数は、 {1,2,3,4}であるので、 オイラー関数 と一致する このとき、オイラーの定理は、フェルマーの小定理と一致する。 練習 、 のとき、 と互いに素な数の 個数を実際に上げて求めたものと オイラー関数で 求めたものと比較せよ。
36
オイラー関数を確認② (ⅱ)の理由 、 のとき、 この数と互いに素な数は、{1,2,4,7,8,11,13,14}の8個。
、 のとき、 この数と互いに素な数は、{1,2,4,7,8,11,13,14}の8個。 オイラー関数で計算すると、 個となり一致する。 練習 、 のとき、 と 互いに素な数の個数を実際に上げて求めたものと オイラー関数で求めたものと比較せよ。
37
オイラーの定理(特殊な場合) 、 :素数 : 、 と互いに素な整数 :整数 証明 表計算で確認
38
オイラーの定理(特殊な場合)の証明1 、 は素数なので、フェルマーの定理より ・・・① ・・・② よって、
、 は素数なので、フェルマーの定理より ・・・① ・・・② よって、 (←①とmod演算法則1(3)より) ・・・③ 証明の続きへ
39
オイラーの定理(特殊な場合)の証明2 同様に ・・・④ ゆえに、③、④において、modの計算法則2を用いると、 [証明終]
・・・④ ゆえに、③、④において、modの計算法則2を用いると、 [証明終]
40
暗号の数学的仕組み 送信側 → 暗号を生成 暗号 を送る 受信側 → 平文を復号
41
復号ができる仕組み 1 (←指数の法則 と より) ←鍵生成の⑤で、 を で割って1あまるような整数が すなわち ( は商)
42
復号ができる仕組み 2 (←指数の法則 より) (←オイラーの定理(特殊な場合) とmodの計算法則1(2)より) →平文 になる。
復号ができる仕組み 2 (←指数の法則 より) (←オイラーの定理(特殊な場合) とmodの計算法則1(2)より) →平文 になる。 よって、 を計算すれば平文 がわかる。
43
復号1(暗号を平文に戻す) ◆繰り返し2乗法 を法とする を効率よく計算する方法 これを用いると の余りが求まり、
を法とする を効率よく計算する方法 これを用いると の余りが求まり、 暗号が復号でき、平文が求められる。 ◆ の余りを求める場合
44
復号2 ◆ 232 (mod 55) 、234 (mod 55) 、 238 (mod 55)を 用意しておく
≡34 ← より、あまり34 234 ≡342 (mod 55) ← と mod演算法則1(3)より ≡1156 (mod 55) ← ≡1 ← より、あまり1 238 ≡12 (mod 55) ← と mod演算法則1(3)より ≡1
45
復号3 2327 ≡ 232 × 234 × 234 × 238× 238 × 231 (mod 55) ≡34×1×1×1 ×1 ×23 (mod 55) ←先の計算結果とmodの演算法則1(2)より ≡782 (mod 55) ≡12 ⇒平文 M=12
46
実習 公開鍵: 暗号: 平文: (1) 鍵生成者 鍵を生成 (2)回収、再配布 (3)送信者 暗号に変換
(1) 鍵生成者 鍵を生成 (2)回収、再配布 (3)送信者 暗号に変換 (平文 として好きな数字(2桁、 )を考え、暗号 に変換) (4)回収、再配布 (5)受信者 暗号解読 (6)回収、再配布 (7)送信者 公開鍵: 暗号: 平文: 送信チェック(○、×と理由を記入) 正しく暗号解読されている 正しく暗号解読されていない できなかった理由 実習プリント 計算サイト
47
参考文献、参考URL 明星学園高校 神戸大学 教養原論(数理の世界--「現象の数理」「数理解析と社会」)の 授業用のページ(計算サイト) 高校生のための暗号論入門 ブルーバックス 素数入門 芹沢 正三 講談社
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.