情報理論

前回の練習問題
F29 = {1, 2,…, 28}において，g = 11 が生成元であることを確か
め，F29 の元とその離散対数との関係を図示せよ．
x
11
12
13
14
15
16
17
18
19
20
gx
10
23
21
28
18
24
3
4
15
20
x
21
22
23
24
25
26
27
28
gx
17
13
27
7
19
6
8
1
20
gx
11
5
26
25
14
9
12
16
2
22
10
x
1
2
3
4
5
6
7
8
9
10
log a
x = 1, ..., 28 に対し，gx mod 29 を計算すればよい
0
5
10
15
20
25
a
1
前回紹介したRSA暗号の実現例
暗号化操作：
平文を3乗して，493で割った余りを暗号文とする
復号操作：
暗号文を299乗して，493で割った余りを復号結果とする
当然沸いてくる疑問：
本当に，いつも正しく復号できるの？
3や493と299との関係は？
大きな数字の計算はどうするの？
2
RSA暗号
Rivest, Shamir, Adelmanにより1977年に提案
「世界初」の公開鍵暗号で，広く実用化
以下のスライドで概要を説明する
鍵の（具体的な）構成法
暗号化・復号の（具体的な）手順
鍵構成，暗号化・復号操作の実現法について
逆元計算，べき乗計算の方法
動作原理の数学的考察
安全性について
3
RSA暗号の鍵構成
RSA暗号の暗号化鍵，復号鍵をつくるには．．．
1. 大きな素数を２個選ぶ．仮にこれを p, q とする
2. 合成数 n = pq を計算する
3. (p – 1) (q – 1) と互いに素な正整数 e を選ぶ
4.
ed ≡ 1 mod (p – 1)(q – 1) となる正整数 d を求める
5. 暗号化鍵として，e と n を公開する．
6.
d は，復号鍵として厳重に保管する
a mod x: a を x で割った余り
a ≡ b mod x: (a を x で割った余り) = (b を x で割った余り)
4
RSA暗号の暗号化と復号
e, n は暗号化鍵として公開：
暗号化操作は「平文を e 乗して n で割った余りを求める」
平文 m の暗号文は，me mod n
d は復号鍵として秘密保存：
復号操作は「暗号文を d 乗して n で割った余りを求める」
暗号文 c に対応する平文は，cd mod n
平文の集合は 1 以上 n – 1以下の正整数
5
前例の鍵生成について
前回の例の鍵：e = 3, n = 493, d = 299 はどのように求めたか
1.
2.
3.
4.
5.
6.
p = 29, q = 17 とする
n = pq = 29・ 17 = 493 とする
e = 3 とする．この値は (p – 1)(q – 1) = 28・ 16 = 448 とは
互いに素となっている
計算により d = 299 となる．ed = 3・299 = 897 = 2・448 + 1，
したがって ed を (p – 1)(q – 1) で割った余りは 1 になる
暗号化鍵として e = 3 と n = 493 を公開
d = 299 は復号鍵として保管
6
復号鍵の計算について
RSA暗号では，
ed ≡ 1 mod (p – 1)(q – 1)
となる正整数 d を求める必要がある
e と (p – 1)(q – 1) が互いに素ならば
ed ≡ 1 mod (p – 1)(q – 1) となる d は必ず存在する
d はユークリッド互除法を応用して計算可能
7
ユークリッドの互除法と d の計算
ユークリッド互除法：
２つの整数の最大公約数を計算するアルゴリズム
2整数をA, Bとする(A > B)
a0 = A
b0 = B
ai+1 = bi, bi+1 = ai mod bi と
して再帰的計算を行う
ai
ai+1 = bi
bi
bi+1 = ai mod bi
bj = 0 となったときの aj が
A と B の最大公約数
aj
bj = 0
a0 = A, b0 = B とする
8
ユークリッド互除法の計算例（１）
252 と 135 の最大公約数は．．．
252
135
135
117
← 252を135で割ると，余りは117
117
18
← 135を117で割ると，余りは18
18
9
← 117を18で割ると，余りは9
9
0
← 18を9で割ると，余りは0
252と135の最大公約数は9
9
ユークリッド互除法の計算例（２）
130 と 59 の最大公約数は．．．
130
59
59
12
← 130を59で割ると，余りは12
12
11
← 59を12で割ると，余りは11
11
1
← 12を11で割ると，余りは1
1
0
← 11を1で割ると，余りは0
最大公約数は1．．．130と59 は互いに素
2整数が互いに素ならば，どこかで bi = 1 となる
10
ユークリッド互除法と逆元計算
A, B を互いに素な正整数とし，A > B とする．
ユークリッド互除法を応用することで，
CB ≡ 1 mod A
となる C を計算可能（C は B の乗法逆元）
計算法：
各 bi を (A の倍数) + (B の倍数) として表現
どこかで bi = 1 = xA + yB となるはず
yB = – xA + 1 より，yB を A で割ると 1 余る
yB ≡ 1 mod A なので，C = y としても良いが...
CB ≡ 1 mod A となる C は無数に存在
（後の計算のため）y と同値な最小正整数をC とする
11
逆元計算の例
130 と 59 は互いに素．．．
130
59
59
12
= 130 – 2 x 59
12
11
= 59 – 4 x 12 = – 4 x 130 + 9 x 59
11
1
= 12 – 11 = 5 x 130 – 11 x 59
1 = 5・130 – 11・59 となる．これより．．．
– 11・59 = – 5・130 + 1
– 11・59 ≡ 1 mod 130
– 11 と等価な整数は，すべて 59 の逆元となる
– 11 と等価な – 11 + 130 = 119 を逆元の代表値とする
12
d の計算
ed ≡ 1 mod (p – 1)(q – 1)となる正整数 d を求める
⇒(p – 1)(q – 1) と e に対してユークリッド互除法を利用
p = 29, q = 17, n = pq = 493, e = 3 に対応する d を求める：
(p – 1)(q – 1) = 448 と e = 3 に対してユークリッド法を適用
448
3
3
1 = 448 – 149・3
3 の逆元は –149 ≡ – 149 + 448 = 299 mod 448
d = 299
これで鍵を作れるようになった
13
RSA の鍵を作ってみる
p = 79, q = 97 とすると，n = pq = 7663
(p – 1)(q – 1) = 7488 と互いに素な値 e = 5 を選択
7488 と 5 との間でユークリッド互除法を実行
7488
5
5
3 = 7488 – 1497・5
3
2 = 5 – 3 = –7488 + 1498・5
2
1 = 3 – 2 = 2・7488 – 2995・5
e の逆元は d = – 2995 ≡– 2995 + 7488 = 4493 mod 7488
14
べき乗計算について
前スライドのRSA暗号：
暗号化は，平文を 5 乗して 7663 で割る
復号は，暗号文を 4493 乗して 7663 で割る
安直に計算すると大変
べき乗を効率的に計算するために，「計算の分割」を行う
x2 mod n: そのまま計算する
x4 mod n: (x2 mod n)2 mod n として計算を行う
x8 mod n: (x4 mod n)2 mod n として計算を行う
x10 mod n: (x8 mod n) (x2 mod n) mod n として計算を行う
：
15
べき乗計算の例
1219 mod 35 を計算する
122 mod 35 = 144 mod 35 = 4
12４ mod 35 = 42 mod 35 = 16
128 mod 35 = 162 mod 35 = 256 mod 35 = 11
1216 mod 35 = 112 mod 35 = 121 mod 35 = 16
1219 mod 35 = 1216+2+1 mod 35
= 16・ 4・12 mod 35
= 768 mod 35
= 33
これで暗号化・復号が行えるようになった
16
RSA暗号の簡単な使用例（１）
ユーザＡの鍵生成：
p = 5, q = 11 とする．n = 55 となる
e = 3 とする． (p – 1)(q – 1) = 40 なので，e と互いに素
ユークリッド互除法で d を求める
40
3
3
1 = 40 – 13 x 3
d = – 13 ≡40 – 13 = 27 mod 40
d の計算は， (p – 1)(q – 1) の剰余系で行う．
n の剰余系でないことに注意！
暗号化鍵として e = 3, n = 55 を公開
復号鍵として d = 27 を秘密保持
17
RSA暗号の簡単な使用例（２）
ユーザBがユーザＡにm = 7 を暗号化して送る：
B は公開されている暗号化鍵 e = 3, n = 55 を取得
暗号文は 73 mod 55 = 343 mod 55 = 13
ユーザAによる暗号文 13 の復号操作：
ユーザAは，秘密の復号鍵 d = 27 を知っている
1327 mod 55 を計算する
132≡4, 134≡16 , 138≡36 , 1316≡31
1327 ≡ 31 x 36 x 4 x 13 = 58032≡7 mod 55
復号結果は7
暗号化，復号は n の剰余系で行う．
(p – 1)(q – 1) の剰余系でないことに注意！
18
なぜRSA暗号はうまく動くのか？
「正しい鍵を使えば正しく復号できる」ことが必須
RSA暗号の場合，
(me mod n)d mod n = med mod n = m
任意の m に対し，この式が成立することを証明する必要がある
Eular（オイラー）の定理（の特殊な場合）：
m が n = pq と互いに素ならば，m(p – 1)(q – 1) ≡ 1 mod n.
19
Eularの定理の直感的意味付け
Eular（オイラー）の定理（の特殊な場合）：
m が n = pq と互いに素ならば，m(p – 1)(q – 1) ≡ 1 mod n.
べき乗値は，[1, n – 1]に属する有限の値をとる
べき乗値の系列を考えると，どこかで無限ループに陥る
オイラーの定理の意味：mがnと互いに素であれば...
無限ループの中に 1 が存在
少なくとも，(p – 1)(q – 1) 乗したときは 1 になる
n = 2・7 = 14 の場合，(p – 1)(q – 1) = 1・6 = 6
56
55
5
54
52
53
1 2 3 4 5 6 7 8 9 10 11 12 13
20
数値例
n = 2・7 = 14 の場合，(p – 1)(q – 1) = 1・6 = 6
m
m2 m3 m4 m5 m6 m7… m13…m19
3
9
13
11
5
1
3… 3… 3
5
11
13
9
3
1
5… 5 … 5
9
11
1
9
11
1
9… 9 … 9
11
9
1
11
9
1
11 … 11 … 11
13
1
13
1
13
1
13 … 13 … 13
1になった次の次数では，再び m が出現する
mとnが互いに素であれば，任意の整数kに対し，
mk(p – 1)(q – 1)+1 = (m(p – 1)(q – 1))km ≡ m mod n
べき乗演算により，一時的にmの値が「隠蔽される」
さらにべき乗することで，周期的にmが出現する
21
RSAの正当性証明
定理： med mod n = m
証明：ed ≡ 1 mod (p – 1)(q – 1)より，整数 k が存在して
ed = k(p – 1)(q – 1) + 1
m が n と互いに素であるとき
前ページの式より med ≡mk(p – 1)(q – 1)+1 ≡ m mod n.
m が n = pq とは互いに素でないとき
m は p または q の倍数．仮に m = api とする (a < q)
a は n と互いに素 ... med ≡aedpied ≡a(ped)i mod n
ped ≡ p mod n を証明できれば良い
ped ≡ 0 mod p
ped ≡ p mod q (フェルマーの小定理)
22
ped ≡p mod nの証明
中国人の剰余定理(Chinese Reminder Theorem):
n = p1・p2 ・・・pj とする．
1以上n – 1以下の整数で，以下のj個の合同式
x≡a1 mod p1
x≡a2 mod p2
：
x≡aj mod pj
を同時に満足する整数 x は（n を法として）唯一に定まる．
□
ped ≡0 mod p, ped ≡p mod q を満足するのは，
ped≡p mod nの場合のみ ⇒ 前ページの証明完了
23
公開鍵暗号の安全性について
暗号が安全：解読が困難であること
さらに強い意味での安全性が必要になる場合も...
（本講義では扱わない）
暗号の解読：
復号のための鍵を使わずに，暗号文に隠された
平文を特定，推測すること
RSAの場合：me mod nから mの値を推測すること
24
RSA暗号の解読について
RSA暗号の解読は困難か？
結果から言うと「安全であると思われている」
安全でないことの証明は簡単
攻撃に成功する方法を一個だけ提示すれば良い
安全であることの証明は困難
何をやっても成功しないことを示す必要がある
RSAには，計算理論的な意味で安全性の保証はない
「RSAの解読はNP完全問題である」等の証明は
これまで与えられていない
25
RSAの解読法（１）
攻撃者の立場から，どのような解読法が考えられるか
「c = me mod nから mの値を推測したい」ときにどうするか
総当り攻撃
公開鍵暗号では，誰でも暗号化が可能
考えられる平文を一個ずつ暗号化する
暗号文が c になる平文が m に相当する
⇒平文空間を大きく(n の値を大きく）すれば問題なし
26
RSAの解読法（２）
方程式攻撃
c = me mod nから方程式を立てて m を計算
n の剰余系でなければ，単なる数値計算問題
⇒n の剰余系では，有効な解法が知られていない
復号鍵の推測攻撃
d は，(p – 1)(q – 1)の剰余系での e の乗法逆元
暗号化鍵 e と n = pq から，復号鍵 d を推定したい
もし(p – 1)(q – 1)がわかれば，d の計算は容易
n = pq から(p – 1)(q – 1)が計算できるか？
27
素因数分解とRSA暗号
n = pq から(p – 1)(q – 1)が計算できるか？
できるかもしれないし，できないかもしれない
もし n を素因数分解できれば．．．
p, q を特定可能
(p – 1)(q – 1)を計算可能
素因数分解はできるのか？
決定的な解法は知られていない
p, qを十分大きな素数にすれば，
実用上問題ないのではないかと考えられている
28
素因数分解と解読問題の難しさ
RSA暗号の場合，
素因数分解ができれば，RSAは解読可能
逆は示されていない
「RSAの解読は，素因数分解よりも難しくない」
RSAの解読
素因数分解
易
難
Rabin, 逆数暗号の解読
Rabin 暗号，逆数暗号等の公開鍵暗号方式
素因数分解ができれば，解読可能
暗号の解読ができれば，素因数分解もできる
「これらの方式の解読は，素因数分解と等価な難しさ」
29
RSA暗号のまとめ
RSA暗号の鍵構成法
暗号化，復号の方法
具体的な計算の実現方法
正当性の証明
安全性の議論
安全性は素因数分解の困難さに依拠する
鍵のサイズをできるだけ大きく取ることが望ましい
現在では，最低でも n を1024ビット程度にはすべき
30
暗号関連技術について
本講義では，暗号方式の基礎の基礎だけを紹介
今回紹介した基礎の上に，さまざまな技術が展開
さらに進んだ暗号方式
電子署名，PKI
暗号を用いたプロトコル
ゼロ知識証明 etc.
31
講義全体のまとめ
情報の記録や伝達を，効率よく，確実に行うための技術
第一部：情報の量を計る
第二部：情報をコンパクトに表現する
第三部：情報を正確に伝える
第四部：情報を不正者から隠す
あくまでも情報を扱うための「道具」
情報を取り扱う際に，これら道具を最大限活用してほしい
32
試験について
6/3（木）１限試験（L1講義室）
本，資料，パソコン等の持ち込みOK（通信機能の使用は不可）
電卓はあったほうが良いかも...
test day: June 3 (Thu.), L1 (this room)
You can bring any books, documents and your PC (no WiFi)
An calculator may help you, maybe....
English translation of test questions will be provided.
33

Download Report