数 学 の か た ち 第３講 暗号を作ろう 早苗 雅史 数学とソフトウエア

Presentation on theme: "数 学 の か た ち 第３講 暗号を作ろう 早苗 雅史 数学とソフトウエア"— Presentation transcript:

1 数 学 の か た ち 第３講 暗号を作ろう 早苗 雅史 sunny@nikonet.or.jp 数学とソフトウエア
早苗　雅史 数学とソフトウエア

2 指で数える２進法 １３ ２８ ？

3 指で数える２進法

4 指で数える２進法 小指 薬指 中指 人指 親指 (16) (8) (4) (2) (1) × 1 | | 8 4 ＝ １３

5 記数法で暗号を作る a b c d e f g h i j k l m 1 2 3 4 5 6 7 8 9 10 11 12 n o p q
1 2 3 4 5 6 7 8 9 10 11 12 n o p q r s t u v w x y z 13 14 15 16 17 18 19 20 21 22 23 24 25

6 記数法で暗号を作る ｃａｐ ＝ 2，0，15 2×262＋0×26＋15 ＝2×676＋0×26＋15 ＝1367

7 記数法で暗号を作る ２６ １３６７ ・・・１５ ２６ ５２ ・・・　０ ２

8 記数法で暗号を作る

9 問題 ①　ｂｏｘを数字に直してみよう。 ②　“13223”は何という文字を表しているか。

10 暗号の重要性 インターネットや電子メールなどの普及による危険性 情報がネットワーク上に流出 コンピュータ間のデータを見ることが可能
様々な手口 電子メールを知らない人に読まれてしまう（盗聴） 情報の内容を勝手に書き換えてしまう（改ざん） 正当なユーザーになりすまして悪用（なりすまし） それらの脅威を防ぐための解決法⇒暗号化 　 データを第三者に解読できないようにする方法

11 シーザー暗号 文字をアルファベット順に特定の文字数だけずらす ＝換字式（かえじしき）暗号 「暗号方式（アルゴリズム） 」 「鍵」 平文
文字をアルファベット順に特定の文字数だけずらす 　＝換字式（かえじしき）暗号 平文 暗号文 「暗号方式（アルゴリズム） 」 「鍵」

12 多文字置換暗号 平文 I a m b o y 鍵 7 3 2 4 暗号文 p d e i r キーワードが繰り返し使用される
使用頻度の高い文字を元に キーワードが簡単に推測

13 いろいろな暗号 ★転置式暗号 ★円盤式暗号 内側の小さい円盤位置決め 行→列 外側の大きい円盤の文字 １列→３列→２列→４列
短い方の矢印が指している 小さい円盤の文字が暗号 行→列 １列→３列→２列→４列

14 問題 ①　Matheを鍵“3631”で暗号化してみよう。 ②　HGWWを鍵“1234”で複合化してみよう。

15 父へのメール 父さんへ キャッシュカードのパスワードを忘れたので教えてほしい。
他人に知られると困るので次の計算で出た数字をメールで教えてくれ。 『まずパスワードの数字を37乗する。次に出た数値を2491で割る。そのときの余りの数字。』

16 いくつかの疑問 4桁のパスワードの数字を37乗して2491で割るなんて計算，どうやってやるのだろう。
送られてきた数字から本当にパスワードがわかるのだろうか。 このメールを誰かに盗聴されたら，その人にもパスワードを知られてしまわないか。

17 《疑問①》4桁の数を37乗して2491で 割る計算はどうするのか
《疑問①》4桁の数を37乗して2491で　　 　　　　　割る計算はどうするのか 繰り返し2乗法 12342 ＝ ≡755 12344 ＝7552 ＝570025 ≡2077 12348 ＝20772 ＝ ≡2008 123416 ＝20082 ＝ ≡1626 123432 ＝16262 ＝ ≡925 123437 ＝123432×12344×12341 ≡925×2077×1234 ＝ ×1234 ≡664×1234 ＝819376 ≡2328

18 《疑問②》送られてきた数字を どのように復元するのか
《疑問②》送られてきた数字を 　　　　　どのように復元するのか 例：21を余りとする世界では 7乗，13乗，19乗，…すると元に戻る

19 37乗したあと97乗すると元に戻る 37乗 97乗 A君だけが知っている

20 37乗したあと97乗すると元に戻る 23282 ＝ ≡1659 23284 ＝16592 ＝ ≡2217 23288 ＝22172 ＝ ≡346 232816 ＝3462 ＝119716 ≡148 232832 ＝1482 ＝21904 ≡1976 232864 ＝19762 ＝ ≡1179 232897 ＝232864×232832×23281 ≡1179×1976×2328 ＝ ×2328 ≡619×2328 ＝ ≡1234

21 共通鍵暗号方式・公開鍵暗号方式 平文 暗号化 暗号文 複合化 "apple" → "dssoh" 平文 暗号化 暗号文 複合化 “1234"
共通鍵＝３　知られると困る 平文 暗号化 暗号文 複合化 "apple" → "dssoh" 共通鍵 共通鍵 公開鍵暗号方式 公開鍵＝37（乗），2491（で割る）　知られてもOK 秘密鍵＝97　　自分しか知らない 平文 暗号化 暗号文 複合化 “1234" → “2328" 公開鍵 秘密鍵

22 RSA暗号 平文 e 乗してnで割る 暗号文 d 乗 → 秘密鍵 d=97 公開鍵 n=2491 e=37

23 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で復元する まず２つの素数を選ぶことから始まった

24 《疑問③》37乗して2491が得られたことを知られてもパスワードは大丈夫か
２つの素数の積は簡単に計算できます　 　　38903　×　60293　＝　 しかしある数を２つの素数の積に分解する　 　のは大変 　　 　＝　40253　×　55897 暗号の秘密は「素因数分解の困難性」に起因

25 鍵の作成 ２つの素数を選ぶ p=3，q=5 素数の積 これが余りの世界 n=15 p－1とq－1の最小公倍数Lを計算 L=2
Lと素な数を選択　　　　　　　　　　　　　e=7 7×□=1となる数を計算　　　　　　　　d=13 平文 7乗して 15で割る 暗号文 13 乗 →

26 暗号を作ってみよう メッセージM=3，あまりの世界n=15，累乗e=7 37を計算する 3の累乗を計算 32＝9 34≡92＝81≡6
3の累乗を計算 　　　32＝9 　　　34≡92＝81≡6 37を計算 　　　37＝34×32×3≡6×9×3＝162≡12 C=12

27 暗号を復元してみよう d=13で複合化 12の累乗を計算 122＝144≡8 124≡82＝ 64≡4 128≡42＝16≡1
12の累乗を計算 　　　122＝144≡8 　　　124≡82＝ 64≡4 　　　128≡42＝16≡1 1212を計算 　　　1212＝128×124×12 　　　 　　≡1×4×12＝48≡3 M=3