コンピュータと数学教育

暗号理論にみる数学
～情報と数学の接点から～
2002.6.15
札幌新川高等学校
早苗雅史
1
はじめに




インターネットの普及に伴い，ネット上にお
ける情報の機密保持，改ざん防止の方法
として公開鍵暗号方式が注目
中でも最も普及しているのがRSA暗号
この理論には基本的でかつ魅力的な数学
の整数に関する理論が用いられている
高校数学レベルでも理解できる数学をもと
に，暗号論の魅力を少しでも紹介
2
父へのメール
父さんへ
キャッシュカードのパスワードを忘れたので教
えてほしい。
他人に知られると困るので次の計算で出た数
字をメールで教えてくれ。
『まずパスワードの数字を37乗する。次に出た
数値を2491で割る。そのときの余りの数字。』
3
いくつかの疑問
① 4桁のパスワードの数字を37乗して2491で
割るなんて計算，どうやってやるのだろう。
② 送られてきた数字から本当にパスワードが
わかるのだろうか。
③ このメールを誰かに盗聴されたら，その人に
もパスワードを知られてしまわないか。
4
《疑問①》4桁の数を37乗して2491
で割る計算はどうするのか
繰り返し2乗法
12342
＝1522756
≡755
12344
＝7552
＝570025
≡2077
12348
＝20772
＝4313929
≡2008
123416 ＝20882
＝4032064
≡1626
123432 ＝16262
＝2643876
≡925
123437 ＝123432×12344×12341 ≡925×2077×1234
5
＝1921225×1234
≡664×1234
＝819376
≡2328
法
記数法
《疑問②》送られてきた数字をどのよ
うに復元するのか
例：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
6
1
1
7乗，13乗，19乗，…すると元に戻る
1
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
7
42
37乗
2008 1818 1512
97乗
暗号とは
平文・・・元のデータ
暗号文・・・第三者に解読不可能な形式に変換されたデータ
暗号化・・・平文を暗号文に変換する処理
複号化・・・暗号文を平文に変換する処理
8
暗号化の規則と鍵
“apple”をアルファベット順に3つずつずらす
→“dssoh”
「アルファベット順にずらす」が暗号化の規則（アルゴリズム）
「3」が鍵
受信者以外に鍵を知られないことで秘匿性が守られる
平文
"apple"
9
暗号化
→
暗号文
"dssoh"
複合化
→
平文
"apple"
共通鍵暗号方式・公開鍵暗号方式
共通鍵暗号方式共通鍵＝３知られると困る
平文
"apple"
暗号化
→
共通鍵
暗号文
"dssoh"
複合化
→
共通鍵
平文
"apple"
公開鍵暗号方式
公開鍵＝37（乗），2491（で割る）知られてもOK
秘密鍵＝97 自分しか知らない
平文
“1234"
10
暗号化
→
公開鍵
暗号文
“2328"
複合化
→
秘密鍵
平文
“1234"
RSA暗号
法nの元で
平文
11
e乗
暗号文
d乗
→
→
公開鍵
秘密鍵
n，e
d
平文
A君はどうやって鍵を作ったか
①2つの素数P=47，Q=53を選択
②N=PQ=2491を法とする世界を作る（公開鍵N）
③P-1=46とQ-1=52の最小公倍数L=1196を計算
④Lと素な数E=37を選んで父さんに送る（公開鍵E）
⑤L=1196を法とするE=37の逆元D=97で復元する
まず２つの素数を選ぶことから始まった
12
《疑問③》37乗して2491が得られたこ
とを知られてもパスワードは大丈夫か
２つの素数の積は簡単に計算できます
38903 × 60293 ＝ 2345578579
しかしある数を２つの素数の積に分解する
のは大変です
2250021941 ＝ 40253 × 55897
暗号の秘密は「素因数分解の困難性」に起因
13
おわりに
素数・合成数
素数の判定，素因数分解
 法，剰余の定理
法と合同，法に関する演算
逆元
 最大公約数，互いに素
ユークリッドの互除法
最小公倍数
 記数法

14
暗号理論は整数に
関する様々な内容
が盛りだくさん
易しく教材化できな
いか

Download Report