Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


Presentation on theme: "共通鍵と公開鍵 暗号のしくみ 情報、数学ハイブリッド版."— Presentation transcript:

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がないと 膨大な時間がかかる ⇒暗号解読を諦める

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 明星学園高校     神戸大学 教養原論(数理の世界--「現象の数理」「数理解析と社会」)の   授業用のページ(計算サイト)     高校生のための暗号論入門            ブルーバックス 素数入門 芹沢 正三 講談社


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

Similar presentations


Ads by Google