（公開鍵と秘密鍵）[パワーポイント文書]

共通鍵と公開鍵
暗号のしくみ
情報、数学ハイブリッド版
暗号
◆インターネットで用いられる暗号
SSL（セキュアソケットレイヤー）
・・・インターネットで情報を暗号化して
送受信するプロトコル（通信規約）
URLにおいて、
ｈｔｔｐがｈｔｔｐｓ（Hypertext Transfer Protocol Security）に
なっている
ｈｔｔｐｓ：//ｗｗｗ．・・・
◆暗号の種類
・共通鍵方式
・公開鍵方式
など
共通鍵方式
インターネット
カード
番号
暗号化
暗号
共通鍵ｋ
復号
共通鍵ｋ
同じ鍵⇒どのようにして渡すのか？
•知られたらすぐに暗号が解かれる
•文字や単語の出現頻度から暗号が解かれてしまう。
•代表的なものシーザー暗号など
カード
番号
シーザー暗号
例１アルファベット表を3文字ずらす
→ ずらす文字数を「鍵」とする
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
↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓ ↓
D
E
F
（例）
G
H
I
J
K
L
M
N
O
P
Q
R
S
T
U
V
W X
TOP SECRET → WRS VHFUHW
問１先の表を用いて次の暗号を解読せよ。
DQJRXBDGH
（答え）
ANGOUYADE
練習１先の表を用いて、好きな言葉を暗号化せよ。
Y
Z
A
B
C
公開鍵方式１
インターネット
カード
番号
暗号化
公開鍵
ｎ、e
みんなが知っている
暗号
復号
カード
番号
秘密鍵
ｄ
秘密鍵ｄがないと
膨大な時間がかかる
⇒暗号解読を諦める
公開鍵方式－ RSA暗号

ＲＳＡ暗号
大きな整数の素因数分解が非常に難しいということを
用いた暗号方式。
RSAは、考案者であるマサチューセッツ工科大学(MIT)の
研究者3名、Rivest（リベスト）,Shamir（シャミア）,Adleman
（エイドルマン）の頭文字（1977年頃）
桁数の多い素因数分解が非常に困難
↓
人間の寿命ほどの時間がかかる（２００桁）
↓
暗号を解読するのを諦める
↓
セキュリティー

暗号の解きにくさを「強度」と呼ぶ
素因数分解をしてみよう
実習１次の数を素因数分解せよ。
①、②は自分でする。
③は、奇数出席番号の人
出席番号＋４０× ｎで割る。（ｎ＝０、１、２、・・・）
（例：出席番号３番 ⇒ ３、４３、８３、・・・で割る）
④は、偶数出席番号の人
（偶数出席番号-１）＋４０× ｎで割る。（ｎ＝０、１、２、・・・）
（例：出席番号４番 ⇒ ３、４３、８３、・・・で割る）
※出席番号４１番以上の人は、先生の指示した数字で割る。
①
15
（答え）
3 5
②
713
（答え）
23 31
③
7739
（答え） 71109
④
95677
（答え） 241 397
公開鍵と秘密鍵を作ろう①
① ２つ素数
例：
②
p
、
q
を選ぶ。
p  5 、 q  11：非公開
n  pq
をつくる
n  511
 55
n  55
：公開鍵
公開鍵と秘密鍵を作ろう②
③
  ( p  1) (q  1)
をつくる
  (5  1) (11  1)
 410
 40
  40
：非公開
公開鍵と秘密鍵を作ろう③
④

と互いに素な数 e を選ぶ（ 1  e
（１以外の共通の約数をもたないもの）
40と互いに素 → 3
⇒
e3
：公開鍵
n
）
公開鍵と秘密鍵を作ろう④
③
ed
を
 で割って１余るような整数 d
を求める
（ 0
d 
すなわち
3d  40 □1
40 m  1
d 探す
の形の 41、81、・・・と探していく
81＝3×27で適合する
→
となる整数
d  27 ：秘密鍵
）
暗号化して送る

平文（ひらぶん）を暗号に変換
平文
M⇒
平文
M  12 とする（ M  n
公開鍵
⇒
暗号
C
e  3 、 n  55
12  55  1728  55
 3123
⇒ 暗号
3
C  23
商
余り
）
復号（暗号を元の平文に戻す）

暗号
C  23

公開鍵
e3

秘密鍵
・
23  55 の余り

↓
大変な計算！⇒ あまりの理論を使う
27
n  55
d  27
⇒ 平文
M
仕組み
送信者
鍵生成者、受信者
平文
暗号
平文
M
12
C  23
2つの素数
M  12
ｐ＝５
ｑ＝１１
n=55
e=3
d=27
n=55
e=3
d=27
公開鍵
秘密鍵
あまりの理論

あまりの記号 mod
modulo（モデュロー）の略、「モッド」と読む
例２
14  4  32 は、
14  2 (mod 4) とかく。
1,5,
9,13，
…
0,4,8,12, …
mod 4
3,7,11,
15, …
2,6,10,14,…
練習２
58  9  64
x  y (mod n)
を、
の形にせよ。
合同式１
a と bを正の整数 c で割ったときのあまりが等しいときに、
a と b は c を法として合同であるといい、
a  b (mod c)
とかく。
例３
14  4  32
26  4  62
よって
14  26 (mod 4)
合同式２
練習３次の式は正しいか、誤りか。
（１）
28  34 (mod 6)
（２） 17
 2 (mod 5)
（３） 123 
456 (mod 11)
○ 28=4×6+4
34=5×6+4
○ 17=3×5+2
2=0×5+2
× 123=11×11+2
456=41×11+5
（４）
4  7 (mod 3)
×
8=1×5+3
64=12×5+4
（５）
2  4 (mod 5)
○
64=21×3+1
343=114×3+1
3
3
3
3
modの演算法則１
a  b (mod m)
（１）
、
c  d (mod m)
a  c  b  d (mod m)
a  c  b  d (mod m)
（２）
ac  bd (mod m)
（３）
a  b (mod m)
n
ならば、
説明
数値で確認
証明
証明
n
ただし、 n は自然数
証明
modの演算法則２
pと q
が互いに素で､
a  b (mod p)
かつ
a  b (mod q)
ならば、
a  b (mod pq )
数値で確認
証明
フェルマーの小定理
p ：素数
a ： p と互いに素
a
（
例
p 1
a を ( p  1)
 1 (mod p)
乗したものは、
p で割ると１余る）
1  1 (mod 5)
4
2  1 (mod 5)
1  1  0 5 1
数値で確認
2  16  3  5  1
証明
34  1 (mod 5)
34  81  16  5  1
4
4  256  51  5  1
4
4 4  1 (mod 5)
4
4
【参考】フェルマーの最終定理
参考フェルマーの大定理（最終定理）
自然数
自然数
n
3に対して
xn  yn  z n
x , y , z は存在しない。
を満たす
オイラーの定理
n
：正の整数
a
：
n と互いに素な整数
 (n) ： n
未満の n と互いに素な自然数の個数
（オイラー関数）
a
 ( n)
 1 (mod n)
オイラー関数
オイラー関数  (n) は、n 未満の n と互いに素な自然数の個数
（ⅰ）
n p
（ⅱ） n
（
p ：素数）のとき、
 ( p)  p  1
数値で確認
 pq （ p 、 q ：素数）のとき、
 ( pq)  ( p  1)( q  1)
数値で確認
《参考》
k
k
k 1
k
p

(
p
)

p

p
（ⅲ） n  p （
：素数、k ：整数）のとき、
e1
e2
e3
n

p
p
p
（ⅳ）
1
2
3  の素因数分解をとすると、
 (n)   ( p1e ) ( p2 e ) ( p3e )  ( p1e  p1e 1 )( p2 e  p2 e 1 )( p3e  p3e 1 )
1
2
3
1
1
2
2
3
3
オイラーの定理（特殊な場合）

p 、 q ：素数

a
：

k
：整数
p 、 q と互いに素な整数
a
k ( p 1)( q 1)
 1 (mod pq)
証明
表計算で確認
暗号の数学的仕組み
送信側
C  M (mod n)
e
暗号
受信側
C
を送る
M  C (mod n)
d
→ 暗号を生成
→ 平文を復号
復号ができる仕組み１
C d  ( M e ) d (mod n)
M
ed
(mod
s t
st
(
a
)

a
（←指数の法則
とn  pq より）
pq)
 M k ( p 1)( q 1)1 (mod pq)
←鍵生成の⑤で、
ed を  で割って１あまるような整数が d
すなわち ed    k 1 （ k は商）
ed  k  1
 k ( p  1)( q  1)  1
復号ができる仕組み２
M
k ( p 1)( q 1)
M (mod pq) （←指数の法則
 1  M (mod pq)
a s t  a s  a t より）
（←オイラーの定理（特殊な場合）
とmodの計算法則１（２）より）
 M (mod n)
→平文 M になる。
よって、C
d
(mod n) を計算すれば平文 M がわかる。
復号１（暗号を平文に戻す）
◆繰り返し2乗法
n を法とする M d を効率よく計算する方法
これを用いると 23 27  55 の余りが求まり、
暗号が復号でき、平文が求められる。
◆
23 27  55 の余りを求める場合
2  4  4  8  8 1
23  23
27
 23  23  23  23  23  23
2
4
4
8
8
1
復号２
２
、
４
、
８
◆ ２３（mod ５５）２３（mod ５５）２３（mod ５５）を
用意しておく
２
２３ ≡ ５２９（mod ５５）
≡３４
← 529  55  934 より、あまり３４
４
２
2
← 23  34 (mod 55)と
mod演算法則１（３）より
≡１１５６（mod ５５） ← 342  1156
≡１
← 1156  55  211 より、あまり１
２３ ≡３４（mod ５５）
２３
８
２
≡１（mod ５５）
≡１
← 234  342 (mod 55)  1と
mod演算法則１（３）より
復号３
２３
２７
２
４
４
８
８
１
≡ ２３ × ２３ × ２３ × ２３ × ２３ × ２３（mod ５５）
≡３４×１×１×１ ×１ ×２３（mod ５５）
←先の計算結果とmodの演算法則１（２）より
≡７８２（mod ５５）
≡１２
⇒平文Ｍ＝１２
実習
（１）鍵生成者鍵を生成
公開鍵：
n
（２）回収、再配布
（３）送信者暗号に変換
（平文 M として好きな数字（２桁、
暗号：
e
M  n ）を考え、暗号 C
に変換）
C
（４）回収、再配布
（５）受信者暗号解読
平文： M 
（６）回収、再配布
（７）送信者
送信チェック（ ○ 、 × と理由を記入）
実習プリント
正しく暗号解読されている
正しく暗号解読されていない
できなかった理由
計算サイト
参考文献、参考URL

明星学園高校
http://www.tokojoken.jp/johosyakai/rasangou.files/frame.htm

神戸大学教養原論（数理の世界--「現象の数理」「数理解析と社会」）の
授業用のページ（計算サイト）
http://herb.h.kobe-u.ac.jp/RSA.html

高校生のための暗号論入門
http://www.nikonet.or.jp/spring/sanae/report/angou/angou.htm


http://mathmuse.sci.ibaraki.ac.jp/crystalmind/Lesson5.htm
http://isw3.naist.jp/~kaji/lecture/inf-theory2/Jul18.ppt
http://www.apec.aichi-c.ed.jp/project/joho/jissyuu/PGP/pgp.xls

ブルーバックス素数入門芹沢正三講談社


Download Report