共通鍵暗号
廣瀬勝一
廣瀬
共通鍵暗号
1 / 40
ブロック暗号とストリーム暗号
ブロック暗号 平文・暗号文の文字の集まりに作用する．
ストリーム暗号 平文・暗号文の個々の文字に作用する．
【例】
M
K
K
key stream
generator
key stream
generator
C
廣瀬
共通鍵暗号
M
2 / 40
DES (Data Encryption Standard，データ暗号化標準)
IBM，1975 年
plaintext
64
Feistel 構造
IP
64
32
32
f
K1
48
鍵長は 64 ビット
（8 ビットはパリティ）
f
K15
48
f
64
key schedule
ブロック長は 64 ビット
（平文・暗号文の長さ）
64
secret key
K16
48
IP −1 a
64
ciphertext
廣瀬
共通鍵暗号
3 / 40
IP（初期転置）
58
60
62
64
57
59
61
63
50
52
54
56
49
51
53
55
42
44
46
48
41
43
45
47
34
36
38
40
33
35
37
39
26
28
30
32
25
27
29
31
18
20
22
24
17
19
21
23
10
12
14
16
9
11
13
15
2
4
6
8
1
3
5
7
【例】32 番目の出力ビットは 8 番目の入力ビットである．
廣瀬
共通鍵暗号
4 / 40
鍵スケジュール (1/2)
LS (shift left)
64
PC-1
28
LS
C1
48
K1
28
RS
D1
1
1
9
1
2
1
10
2
3
2
11
2
4
2
12
2
5
2
13
2
6
2
14
2
7
2
15
2
8
2
16
1
5
2
13
2
6
2
14
2
7
2
15
2
8
2
16
1
PC-2
RS (shift right)
RS
LS
RS
D16
C16
48
K16
LS
1
0
9
1
2
1
10
2
3
2
11
2
4
2
12
2
PC-2
廣瀬
共通鍵暗号
5 / 40
鍵スケジュール (2/2)
P C-1 : {0, 1}64 → {0, 1}56
57
1
10
19
63
7
14
21
49
58
2
11
55
62
6
13
廣瀬
41
50
59
3
47
54
61
5
33
42
51
60
39
46
53
28
25
34
43
52
31
38
45
20
17
26
35
44
23
30
37
12
P C-2 : {0, 1}56 → {0, 1}48
9
18
27
36
15
22
29
4
共通鍵暗号
14
3
23
16
41
30
44
46
17
28
19
7
52
40
49
42
11
15
12
27
31
51
39
50
24
6
4
20
37
45
56
36
1
21
26
13
47
33
34
29
5
10
8
2
55
48
53
32
6 / 40
f 関数
4
32
S1
6
S2 a
• P は転置
S3
• Si は S ボックス
S4 a
32
• E は拡大関数
（換字ボックス）
48
48
P
32
E
S5
48
Ki
S6
S7 a
S8 a
S ボックスは DES の唯一の非線形変換である．
廣瀬
共通鍵暗号
7 / 40
拡大関数 E と転置 P
E : {0, 1}32 → {0, 1}48
32
4
8
12
16
20
24
28
廣瀬
1
5
9
13
17
21
25
29
2
6
10
14
18
22
26
30
3
7
11
15
19
23
27
31
4
8
12
16
20
24
28
32
5
9
13
17
21
25
29
1
共通鍵暗号
P : {0, 1}32 → {0, 1}32
16
29
1
5
2
32
19
22
7
12
15
18
8
27
13
11
20
28
23
31
24
3
30
4
21
17
26
10
14
9
6
25
8 / 40
S ボックス
Si (b1 , b2 , b3 , b4 , b5 , b6 ) で (b1 , b6 ) は行，(b2 , b3 , b4 , b5 ) は列を指定する．
S1
E
0
4
F
4
F
1
C
D
7
E
8
1
4
8
2
2
E
D
4
S2
F
3
0
D
1
D
E
8
8
4
7
A
E
7
B
1
6
F
A
3
廣瀬
F
2
6
9
B
2
4
F
B
D
2
1
3
8
D
4
8
1
B
7
3
A
F
5
A
6
C
B
6
C
9
3
C
B
7
E
5
9
3
A
9
5
A
0
0
3
5
6
7
8
0
D
4
E
1
2
9
C
5
B
7
0
8
6
2
1
C
7
D
A
6
C
C
6
9
0
0
9
3
5
5
B
2
E
A
5
F
9
共通鍵暗号
9 / 40
S ボックス
S3
A
D
D
1
0
7
6
A
9
0
4
D
E
9
9
0
6
3
8
6
3
4
F
9
F
6
3
8
S4
7
D
A
3
D
8
6
F
E
B
9
0
3
5
0
6
0
6
C
A
6
F
B
1
9
0
7
D
S5
2
E
4
B
C
B
2
8
4
2
1
C
1
C
B
7
7
4
A
1
A
7
D
E
B
D
7
2
廣瀬
5
A
0
7
1
2
B
4
D
8
1
F
C
5
2
E
7
E
C
3
B
C
5
B
4
B
A
5
2
F
E
2
8
1
7
C
A
3
D
8
1
4
F
9
2
7
1
4
8
2
3
5
5
C
E
B
B
1
5
C
C
A
2
7
4
E
8
2
F
9
4
E
6
1
8
D
8
5
F
6
5
0
9
F
3
F
C
0
F
A
5
9
D
3
6
A
0
9
3
4
E
8
0
5
9
6
E
3
共通鍵暗号
10 / 40
S ボックス
S6
C
A
9
4
1
F
E
3
A
4
F
2
F
2
5
C
9
7
2
9
S7
4
D
1
6
B
0
4
B
2
B
B
D
E
7
D
8
S8
D
1
7
2
2
F
B
1
8
D
4
E
4
8
1
7
廣瀬
2
C
8
5
6
9
C
F
8
5
3
A
F
4
C
1
0
9
3
4
8
1
7
A
D
A
E
7
6
A
9
4
F
3
C
A
B
7
E
8
1
4
2
D
0
6
7
B
D
1
0
E
3
D
4
1
4
E
A
7
E
0
1
6
7
B
D
0
5
3
B
8
B
8
6
D
3
E
A
9
C
3
F
5
9
5
6
0
7
C
8
F
5
2
0
E
A
F
5
2
6
8
9
3
1
6
2
C
A
C
0
F
9
5
6
C
3
6
A
9
E
B
D
0
5
0
F
3
0
E
3
5
C
9
5
6
7
2
8
B
共通鍵暗号
11 / 40
暗号解析
Kerckhoff の原理
暗号解析者はどのような暗号方式が使用されているかを知っている．
攻撃
• 暗号文単独攻撃 (ciphertext-only attack)
• 既知平文攻撃 (known-plaintext attack)
• 選択平文攻撃 (chosen-plaintext attack)
• 選択暗号文攻撃 (chosen-ciphertext attack)
目標
• 鍵の回復 (key recovery)
• 識別 (distinguishing) 無作為に選択された置換との識別
廣瀬
共通鍵暗号
12 / 40
暗号文単独攻撃と既知平文攻撃
暗号文単独攻撃
攻撃者
オラクル
C1 , C2 , . . . , Cq
Ci = EK (Pi )
既知平文攻撃
攻撃者
オラクル
(P1 , C1 ), (P2 , C2 ), . . . , (Pq , Cq )
廣瀬
共通鍵暗号
Ci = EK (Pi )
13 / 40
選択平文攻撃
攻撃者
オラクル
P1 C1
Ci−1 を受け取った後
P2 - Ci = EK (Pi )
任意に Pi を選ぶ
C2
..
.
Pq Cq
廣瀬
共通鍵暗号
14 / 40
選択暗号文攻撃
攻撃者
オラクル
x1 , t1 y1
yi−1 を受け取った後
任意に (xi , ti ) を選ぶ
x2 , t2 - yi =
y2
廣瀬
{
EK (xi ) if ti = 0
−1
EK
(xi ) if ti = 1
..
.
xq , tq yq
共通鍵暗号
15 / 40
ブロック暗号に対する二つの強力な暗号解読法
差分解読 (differential cryptanalysis) (1990, Biham & Shamir)
選択平文攻撃
線形解読 (linear cryptanalysis) (1993, Matsui)
既知平文攻撃
1994 年，線形解読法により，243 個の平文と暗号文の組を用いて，DES
が解読された（暗号化に用いられた秘密鍵が特定された）．
廣瀬
共通鍵暗号
16 / 40
鍵の全数探索
1999 年，“DES Cracker” と呼ばれる専用ハードウェアと 10 万台の計算機
を用いて，22 時間 15 分で一組の平文と暗号文の暗号化に用いられた秘密
鍵が特定された．
（1 秒当り 2450 億個の鍵が検査された）
(http://www.eff.org/descracker/)
DES を利用する場合は，3 重暗号
EK3 (DK2 (EK1 (·)))
が推奨されている．
• K1 = K3 でも良い．
• K1 = K2 のときは通常の暗号化と同じ．
廣瀬
共通鍵暗号
17 / 40
環 (Ring)
集合 R について，二つの演算 + と · が定義され，以下の条件が満たされ
るとき，R は環と呼ばれる．なお，+ は加法，· は乗法と呼ばれる．
• R は加法について可換群をなす．
• R は乗法について閉じている．
• R の乗法が結合則を満たす．
• R は乗法に関する単位元を持つ．
• 分配則が成立する．即ち，任意の a, b, c ∈ R について，
(a + b) · c = a · c + a · c
a · (b + c) = a · b + a · c
R の乗法が可換であるとき，R は可換環と呼ばれる．
廣瀬
共通鍵暗号
18 / 40
復習
• R の乗法が結合則を満たす．
• 任意の a, b, c ∈ R について，(ab)c = a(bc)．
• R が加法 + について可換群をなす．
• R が加法 + について群をなす．
• 任意の a, b ∈ R について，a + b = b + a が成立する．
廣瀬
共通鍵暗号
19 / 40
例1
Zn = {0, 1, . . . , n − 1} は，法 n の加法と乗法について環をなす．
• Zn は法 n の加法について可換群をなす．
• Zn は法 n の乗法について閉じている．
• 法 n の乗法は結合則を満たす．
• 1 は法 n の乗法についての単位元である．
• 分配則が成立する．
Zn は可換環である．
廣瀬
共通鍵暗号
20 / 40
例2
R を可換環とする．
R[x] を R の要素を係数とする多項式の集合とする．
R[x] は環をなす．
【例】Z5 [x]
f (x) = 3x2 + 4x + 1, g(x) = 2x + 4 のとき，
f (x) + g(x) = 3x2 + x
f (x) · g(x) = 6x3 + 12x2 + 8x2 + 16x + 2x + 4
= x3 + 3x + 4
係数の加法と乗法は Z5 の加法と乗法によって行われる．
廣瀬
共通鍵暗号
21 / 40
体 (Field)
集合 F について，加法 + と乗法 · が定義され，以下の条件が満たされる
とき，F は体と呼ばれる．
• F は可換環をなす．
• すべての a ∈ F \ {0} に対して，乗法についての逆元 a−1 が存在す
る．ここで，0 は加法についての F の単位元である．
体 F の別の定義
• F は加法について可換群をなす．
• F \ {0} は乗法について可換群をなす．
• 分配則が成立する．
廣瀬
共通鍵暗号
22 / 40
例
Zn は体である ⇔ n は素数である
【例】n = 15 = 3 × 5
2−1 = 8
7−1 = 13
6 の逆元は存在しない
廣瀬
共通鍵暗号
23 / 40
AES (Advanced Encryption Standard)
Rijndael (Daemen & Rijmen, 1998)
SPN 構造 (Substitution-Permutation Network)
鍵長
Nr
128
10
plaintext
128 ビット
128, 192, 256 ビット
192
12
AddRoundKey
256
14
Round
SubBytes
Nr
ShiftRows
Round
Round
MixColumns
FinalRound
AddRoundKey
FinalRound は MixColumns を省略
廣瀬
key
Key Schedule
ブロック長
鍵長
共通鍵暗号
ciphertext
24 / 40
状態
4 種類の変換 (AddRoundKey, SubBytes, ShiftRows, MixColumns) は状
態に対して適用される．
s0,0 s0,1 s0,2 s0,3
s1,0 s1,1 s1,2 s1,3
s2,0 s2,1 s2,2 s2,3
s3,0 s3,1 s3,2 s3,3
• 各バイト si,j ∈ {0, 1}8 は GF(28 ) の要素と見なされる．
• 乗法は x8 + x4 + x3 + x + 1 を法とする．
廣瀬
共通鍵暗号
25 / 40
初期状態
m0
m4
m8
m12
m1
m5
m9
m13
m2
m6
m10 m14
m3
m7
m11 m15
m = (m0 , m1 , . . . , m15 ) は平文であり，mi ∈ {0, 1}8 である．
廣瀬
共通鍵暗号
26 / 40
SubBytes
AES の唯一の非線形変換である．
S ボックス SRD : {0, 1}8 → {0, 1}8
SRD (si,j ) = f (g(si,j )),
ここで，
{
α−1
00
1
0
0
0
f (y) =
1
1
1
1
if α ̸= 00
if α = 00
g(α) =
廣瀬
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
1
1
1
1
1
1
0
0
0
0
1
1
1
1
1
0
0
共通鍵暗号
0
0
1
1
1
1
1
0
0
0
0
1
1
1
1
1
T
y ⊕
0
1
1
0
0
0
1
1
27 / 40
ShiftRows
s0,0 s0,1 s0,2 s0,3
s1,0 s1,1 s1,2 s1,3
s0,0 s0,1 s0,2 s0,3
→
s1,1 s1,2 s1,3 s1,0
s2,0 s2,1 s2,2 s2,3
s2,2 s2,3 s2,0 s2,1
s3,0 s3,1 s3,2 s3,3
s3,3 s3,0 s3,1 s3,2
第 i 行目を i 個左巡回シフトする．
廣瀬
共通鍵暗号
28 / 40
MixColumns (1/2)
a0,0 a0,1 a0,2 a0,3
a1,0 a1,1 a1,2 a1,3
→
b1,0 b1,1 b1,2 b1,3
a2,0 a2,1 a2,2 a2,3
b2,0 b2,1 b2,2 b2,3
a3,0 a3,1 a3,2 a3,3
b3,0 b3,1 b3,2 b3,3
b
3,i
02
b2,i 03
=
b 01
1,i
b0,i
01
廣瀬
b0,0 b0,1 b0,2 b0,3
01 01 03 a3,i
02 01 01
a2,i
03 02 01
a1,i
01 03 02
a0,i
共通鍵暗号
29 / 40
MixColumns (2/2)
前ページの計算では，各列が GF(28 ) 上の多項式と見なされ，次式が計算
されていることになる．
bi (x) = c(x) ai (x) mod x4 + 1
ここで
c(x) = 03 x3 + 01 x2 + 01 x + 02
であり，1 ≤ i ≤ 4 について
ai (x) = a3,i x3 + a2,i x2 + a1,i x + a0,i
bi (x) = b3,i x3 + b2,i x2 + b1,i x + b0,i
である．
廣瀬
共通鍵暗号
30 / 40
AddRoundKey
s0,0 s0,1 s0,2 s0,3
s1,0 s1,1 s1,2 s1,3
k0,0 k0,1 k0,2 k0,3
⊕
k1,0 k1,1 k1,2 k1,3
s2,0 s2,1 s2,2 s2,3
k2,0 k2,1 k2,2 k2,3
s3,0 s3,1 s3,2 s3,3
k3,0 k3,1 k3,2 k3,3
⊕ はビットごとの排他的論理和 XOR である．
廣瀬
共通鍵暗号
31 / 40
鍵スケジュール (1/2)
鍵長 128 ビットの仕様を述べる
wi,j ∈ {0, 1}8 (0 ≤ i ≤ 3, 0 ≤ j ≤ 43)
0 ≤ j ≤ 43 について (w0,j , w1,j , w2,j , w3,j ) を計算
第 r ラウンドのラウンド鍵は Kr
K0
K1
w0,0 w0,1 w0,2 w0,3 w0,4 w0,5 w0,6 w0,7
w1,0 w1,1 w1,2 w1,3 w1,4 w1,5 w1,6 w1,7
...
w2,0 w2,1 w2,2 w2,3 w2,4 w2,5 w2,6 w2,7
w3,0 w3,1 w3,2 w3,3 w3,4 w3,5 w3,6 w3,7
廣瀬
共通鍵暗号
32 / 40
鍵スケジュール (2/2)
0 ≤ j ≤ 43 について (w0,j , w1,j , w2,j , w3,j ) の計算
1
0 ≤ j ≤ 3 について，wi,j = ki,j (0 ≤ i ≤ 3)
2
j ≥ 4 について
j ≡ 0 (mod 4) のとき
{
w0,j−4 ⊕ SRD (w1,j−1 ) ⊕ RC(j/4) (i = 0)
wi,j =
wi,j−4 ⊕ SRD (wi+1 mod 4,j−1 )
(i = 1, 2, 3)
j ̸≡ 0 (mod 4) のとき
wi,j = wi,j−4 ⊕ wi,j−1
ここで，RC(l) = xl−1 mod x8 + x4 + x3 + x + 1 (1 ≤ l ≤ 10)．
廣瀬
共通鍵暗号
33 / 40
暗号利用モード
ブロック暗号を用いて任意長の平文を暗号化する方法
• Electronic codebook mode (ECB)
• Cipher block chaining mode (CBC)
• Cipher feedback mode (CFB)
• Output feedback mode (OFB)
• Counter mode (CTR)
CFB, OFB, CTR はストリーム暗号として働くモード
以降の表記法
• msbu は入力の上位 u ビットを出力する関数
• lsbu は入力の下位 u ビットを出力する関数
• x∥y は二値系列 x, y の連接
廣瀬
共通鍵暗号
34 / 40
ECB
P1
P2
EK
EK
C1
C2
Pn−1
...
EK
Cn−1
Pn
EK
Cn
単にブロックごとに暗号化
廣瀬
共通鍵暗号
35 / 40
CBC
P1
P2
EK
EK
C1
C2
Pn−1
Pn
IV
EK
Cn−1
EK
Cn
IV は初期ベクトル
廣瀬
共通鍵暗号
36 / 40
CFB
x
cmp
IV
cmp
cmp
y
EK
EK
EK
EK
msbs
msbs
msbs
msbs
P1
P2
C1
Pn−1
Pn
Cn−1
C2
Cn
• IV は初期ベクトル
• cmp(x, y) = lsbb−s (x)∥y （b は EK のブロック長）
• Pi , Ci の長さは s ビット
廣瀬
共通鍵暗号
37 / 40
OFB
IV
EK
EK
P1
P2
C1
EK
EK
Pn*
Pn−1
C2
msbu
Cn−1
Cn*
IV は初期ベクトル
廣瀬
共通鍵暗号
38 / 40
CTR
T1
T2
EK
EK
P1
P2
C1
Tn−1
...
EK
Tn
EK
msbu
Pn−1
Cn−1 Pn*
C2
Cn*
Ti はカウンタの値
【例】Ti ← Ti−1 + 1
廣瀬
共通鍵暗号
39 / 40
演習問題
1
DES の暗号化関数が置換であることを証明せよ．
2
MixColumns の行列による計算と多項式による計算が等価であるこ
とを説明せよ．
3
AES の復号アルゴリズムを説明せよ．
4
各暗号利用モードについて，復号法を説明せよ．
廣瀬
共通鍵暗号
40 / 40
© Copyright 2024 ExpyDoc
