数 学 の か た ち 第３講 暗号を作ろう 早苗 雅史 [email protected] 数学とソフトウエア www.nikonet.or.jp/spring/sanae/ 1 指で数える２進法 １３ ２８ ？ 2 指で数える２進法 3 指で数える２進法 小 指 薬 指 中 指 人 指 親 指 (16) (8) (4) (2) (1) × × × × × 0 1 1 0 1 || || || || || 0 8 4 0 1 ＝ １３ 4 記数法で暗号を作る a b c d e f g h i j k 0 1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x l m y z 13 14 15 16 17 18 19 20 21 22 23 24 25 5 記数法で暗号を作る ｃａｐ ＝ 2，0，15 2×262＋0×26＋15 ＝2×676＋0×26＋15 ＝1367 6 記数法で暗号を作る ２６ １３６７ ・・・１５ ２６ ５２ ・・・ ０ ２ 7 記数法で暗号を作る 8 問題 ① ｂｏｘを数字に直してみよう。 ② “13223”は何という文字を表しているか。 9 暗号の重要性 インターネットや電子メールなどの普及による危険性 情報がネットワーク上に流出 コンピュータ間のデータを見ることが可能 様々な手口 電子メールを知らない人に読まれてしまう（盗聴） 情報の内容を勝手に書き換えてしまう（改ざん） 正当なユーザーになりすまして悪用（なりすまし） それらの脅威を防ぐための解決法⇒暗号化 データを第三者に解読できないようにする方法 10 シーザー暗号 文字をアルファベット順に特定の文字数だけずらす ＝換字式（かえじしき）暗号 平文 暗号文 「暗号方式（アルゴリズム） 」 「鍵」 11 多文字置換暗号 平文 I a m a b o y 鍵 7 3 2 4 7 3 2 暗号文 p d o e i r a •キーワードが繰り返し使用される •使用頻度の高い文字を元に キーワードが簡単に推測 12 いろいろな暗号 ★転置式暗号 ① 行→列 ② １列→３列→２列→４列 ★円盤式暗号 ① 内側の小さい円盤位置決め ② 外側の大きい円盤の文字 ③ 短い方の矢印が指している 小さい円盤の文字が暗号 13 問題 ① Matheを鍵“3631”で暗号化してみよう。 ② HGWWを鍵“1234”で複合化してみよう。 14 父へのメール 父さんへ キャッシュカードのパスワードを忘れたので教 えてほしい。 他人に知られると困るので次の計算で出た数 字をメールで教えてくれ。 『まずパスワードの数字を37乗する。次に出た 数値を2491で割る。そのときの余りの数字。』 15 いくつかの疑問 ① 4桁のパスワードの数字を37乗して2491で 割るなんて計算，どうやってやるのだろう。 ② 送られてきた数字から本当にパスワードが わかるのだろうか。 ③ このメールを誰かに盗聴されたら，その人 にもパスワードを知られてしまわないか。 16 《疑問①》4桁の数を37乗して2491で 割る計算はどうするのか 繰り返し2乗法 12342 12344 12348 123416 123432 ＝1522756 ＝7552 ＝20772 ＝20082 ＝16262 ≡755 ＝570025 ＝4313929 ＝4032064 ＝2643876 ≡2077 ≡2008 ≡1626 ≡925 123437 ＝123432×12344×12341 ≡925×2077×1234 ＝1921225×1234 ≡664×1234 ≡2328 ＝819376 17 《疑問②》送られてきた数字を どのように復元するのか 例：21を余りとする世界では 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 2 4 8 16 11 1 2 4 8 16 11 1 2 4 8 16 11 1 2 3 9 6 18 12 15 3 9 6 18 12 15 3 9 6 18 12 15 3 4 16 1 4 16 1 4 16 1 4 16 1 4 16 1 4 16 1 4 5 4 20 16 17 1 5 4 20 16 17 1 5 4 20 16 17 1 5 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 15 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 1 8 9 18 15 9 18 15 9 18 15 9 18 15 9 18 15 9 18 15 9 10 16 13 4 19 10 16 13 4 19 10 16 13 4 19 10 1 1 7乗，13乗，19乗，…すると元に戻る 1 18 37乗したあと97乗すると元に戻る 2 3 4 5 6 7 8 9 10 … 36 37 … 1197 … 2393 … 3589 2 4 8 16 32 64 128 256 512 1024 … 672 1344 … 2 … 2 … 2 3 9 27 81 243 729 2187 1579 2246 1756 … 788 2364 … 3 … 3 … 3 4 16 64 256 1024 1605 1438 770 589 2356 … 713 361 … 4 … 4 … 4 5 25 125 625 634 679 904 2029 181 905 … 897 1994 … 5 … 5 … 5 6 36 216 1296 303 1818 944 682 1601 2133 … 1444 1191 … 6 … 6 … 6 7 49 343 2401 1861 572 1513 627 1898 831 … 354 2478 … 7 … 7 … 7 8 64 512 1605 385 589 2221 331 157 1256 … 864 1930 … 8 … 8 … 8 9 81 729 1579 1756 858 249 2241 241 2169 … 685 1183 … 9 … 9 … 9 … … … … … … … … … … … … … … … … … 1234 755 36 … 664 2328 … 1234 … 1234 … 1234 … … 2077 2270 1296 42 37乗 2008 1818 1512 97乗 19 A君だけが知っている 37乗したあと97乗すると元に戻る 23282 23284 23288 232816 232832 232864 ＝5419584 ＝16592 ＝22172 ＝3462 ＝1482 ＝19762 ≡1659 ＝2752281 ＝4915089 ＝119716 ＝21904 ＝3904576 ≡2217 ≡346 ≡148 ≡1976 ≡1179 232897 ＝232864×232832×23281 ≡1179×1976×2328 ＝2329704×2328 ≡619×2328 ≡1234 ＝1441032 20 共通鍵暗号方式・公開鍵暗号方式 共通鍵暗号方式 共通鍵＝３ 知られると困る 平文 "apple" 暗号化 → 共通鍵 暗号文 "dssoh" 複合化 → 共通鍵 平文 "apple" 公開鍵暗号方式 公開鍵＝37（乗），2491（で割る） 知られてもOK 秘密鍵＝97 平文 “1234" 自分しか知らない 暗号化 → 公開鍵 暗号文 “2328" 複合化 → 秘密鍵 平文 “1234" 21 RSA暗号 e 乗して 平文 nで割る → 暗号文 d乗 平文 → 公開鍵 秘密鍵 n=2491 d=97 e=37 22 A君はどうやって鍵を作ったか ①2つの 素数 P=47，Q=53を選択 ②N=PQ=2491を余りとする世界を作る（公開鍵N） ③P－1=46とQ－1=52の最小公倍数L=1196を計算 ④1196で割った余りの世界で □×○≡1となる２つの素数○=97，□=37を選ぶ ⑤２つの数字の一つ□=37を父さんに送る（公開鍵E） ⑥もう一つの数字○=97で復元する まず２つの素数を選ぶことから始まった 23 《疑問③》37乗して2491が得られたこ とを知られてもパスワードは大丈夫か ２つの素数の積は簡単に計算できます 38903 × 60293 ＝ 2345578579 しかしある数を２つの素数の積に分解する のは大変 2250021941 ＝ 40253 × 55897 暗号の秘密は「素因数分解の困難性」に起因 24 鍵の作成 ① ② ③ ④ ⑤ ２つの素数を選ぶ p=3，q=5 素数の積 これが余りの世界 n=15 p－1とq－1の最小公倍数Lを計算 L=2 Lと素な数を選択 e=7 7×□=1となる数を計算 d=13 平文 7乗して 15で割る 暗号文 → 13 乗 平文 → 25 暗号を作ってみよう メッセージM=3，あまりの世界n=15，累乗e=7 37を計算する ① 3の累乗を計算 32＝9 34≡92＝81≡6 ② 37を計算 37＝34×32×3≡6×9×3＝162≡12 ③ C=12 26 暗号を復元してみよう d=13で複合化 ① 12の累乗を計算 122＝144≡8 124≡82＝ 64≡4 128≡42＝16≡1 ② 1212を計算 1212＝128×124×12 ≡1×4×12＝48≡3 ③ M=3 27
© Copyright 2024 ExpyDoc
