Go 言語で学ぶ『暗号技術入門』Part 1 -DES, Triple DES-

最近結城浩さんの『暗号技術入門』を読みました。現代の暗号技術について非常にわかりやすく書かれており、とってもおすすめの書籍です。

そこで『暗号技術入門』を参考に、 Go 言語のライブラリを使い、各種暗号技術の実装や使い方について学んでみたいと思います。以下の Go のソースコードのバージョンはすべて 1.5.2 です。

まずは第3章「対称暗号（共通鍵暗号）」です。対称暗号は、「共通の鍵で暗号化と復号をおこなう暗号アルゴリズム」です。

DES (Data Encryption Standard)

DES とは

DES (Data Encryption Standard) は、1977年にアメリカ合衆国の連邦情報処理標準規格 (FIPS) に採用された対称暗号です。しかし現在ではブルートフォースアタックにより短時間で解読されてしまうため、暗号化に用いるべきではありません。

ただ後述する Triple DES は DES による処理を3回おこなう方式であり、これは TLS にも使われている未だ現役な暗号方式であるため、その基礎となる DES の処理を知っておくことは有益です。

DES は 64 ビットの平文を、 64 ビット(実際は 56 ビット) の鍵を使って 64 ビットの暗号文に暗号化するアルゴリズムです。あるまとまり単位で暗号化をおこなうアルゴリズムを「ブロック暗号」と呼び、 DES はブロック暗号の一種です。

Go におけるブロック暗号

Go ではブロック暗号はすべて crypto/cipher パッケージに定義されている cipher.Block という統一のインターフェースを介して利用するようになっています。 Encrypt() で暗号化、 Decrypt() で復号をおこないます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package cipher

type Block interface {
        // BlockSize returns the cipher's block size.
        BlockSize() int

        // Encrypt encrypts the first block in src into dst.
        // Dst and src may point at the same memory.
        Encrypt(dst, src []byte)

        // Decrypt decrypts the first block in src into dst.
        // Dst and src may point at the same memory.
        Decrypt(dst, src []byte)
}

このインターフェースにより、ライブラリを使う側は具体的なブロック暗号アルゴリズムの違いを意識する必要なく、統一的に扱えるようになっています。

DES を使ってみる

ではまず実際に DES で暗号化/復号をおこなってみます。 DES 用のオブジェクトは crypto/des パッケージの NewCipher() で生成します。戻り値は cipher.Block インターフェースで、この Encrypt()/Decrypt() メソッドはそれぞれ DES による暗号化と復号の処理を実装しています。

http://play.golang.org/p/F7QBes1BFK

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package main

import (
	"crypto/des"
	"fmt"
)

func main() {
	// 鍵の長さは 8 バイト (64 ビット) にしないとエラー
	key := []byte("priv-key")
	// cipher.Block を実装している DES 暗号化オブジェクトを生成する
	c, err := des.NewCipher(key)
	if err != nil {
		panic(err)
	}

	// 平文も暗号化されるのは 8 バイト (64 ビット)
	plainText := []byte("plaintxt")
	// 暗号化されたバイト列を格納するスライスを用意する
	encrypted := make([]byte, des.BlockSize)
	// DES で暗号化をおこなう
	c.Encrypt(encrypted, plainText)
	// 結果は暗号化されている
	fmt.Println(string(encrypted)) //=> ����A�

	// 復号する
	decrypted := make([]byte, des.BlockSize)
	c.Decrypt(decrypted, encrypted)
	// 結果は元の平文が得られる
	fmt.Println(string(decrypted)) //=> plaintxt
}

DES のアルゴリズム

DES のアルゴリズムの概略は以下の図のように表せます。まず 64 ビット (実質使われるのはそのうちの 56 ビット) の鍵から、16 個の「サブ鍵」という鍵を生成します。そしてそのサブ鍵を使い、 64 ビットの平文を「ラウンド」という処理に 16 回かけます。

https://techwith2.files.wordpress.com/2010/07/desa.jpg

各ラウンドでは以下の図のようなことをおこないます。まず暗号化対象の 64 ビットデータを 左右 32 ビットずつに分割します。続いて、サブ鍵と右の 32 ビットをラウンド関数 $f$ にかけたものと左の 32 ビットの XOR を取ります。最後にその左右を交換します。ラウンド関数 $f$ には任意の関数を用いることが可能です。

http://crunchmodo.com/wp-content/uploads/2013/03/Function-of-Rounds-in-DES.png

この処理をサブ鍵 16 個を順に使って繰り返して、最終的に出力されるバイト列が暗号化データになります。

復号処理はサブ鍵を逆順で使って同じ処理を繰り返せばよいだけになります。なぜなら XOR を 2 回かけると元に戻るという性質があるためです。

DES の鍵の長さは 64 ビット、すなわち取りうる鍵の数は高々 264 ≒ 1.8 × 1019 個なので、現代のコンピュータであればブルートフォースアタックにより短時間で解読することが可能になってしまっています（ラウンド関数は暗号解読者に知られているという前提で考えるべきなので）。

Go での実装

DES を実装した cipher.Block インターフェースの実体は以下の desCipher 構造体です。フィールドには subkeys [16]uint64 を持っています。1つの uint64 が1回のラウンドで使用する 64 ビット (8 バイト) 鍵で、 DES はそれを 16 回繰り返すため 16 個のサブ鍵が必要になります。

1
2
3
4
// desCipher is an instance of DES encryption.
type desCipher struct {
	subkeys [16]uint64
}

NewCipher() コンストラクタは以下のようになっています。鍵の長さは 8 バイト (64 ビット) でないとエラーになります。また c.generateSubkeys(key) でメインの鍵からサブ鍵の配列を生成しています。

1
2
3
4
5
6
7
8
9
10
// NewCipher creates and returns a new cipher.Block.
func NewCipher(key []byte) (cipher.Block, error) {
	if len(key) != 8 {
		return nil, KeySizeError(len(key))
	}

	c := new(desCipher)
	c.generateSubkeys(key)
	return c, nil
}

暗号化/復号をおこなう Encrypt()/Decrypt() メソッドの実装は以下のようになっています。 DES の暗号化/復号処理はサブ鍵を使う順番が違うだけなので、内部では cryptBlock() という共通の関数を用いていることがわかります。

1
2
3
4
5
6
7
8
9
10
11
12
13
func (c *desCipher) Encrypt(dst, src []byte) { encryptBlock(c.subkeys[:], dst, src) }

func (c *desCipher) Decrypt(dst, src []byte) { decryptBlock(c.subkeys[:], dst, src) }

// Encrypt one block from src into dst, using the subkeys.
func encryptBlock(subkeys []uint64, dst, src []byte) {
	cryptBlock(subkeys, dst, src, false)
}

// Decrypt one block from src into dst, using the subkeys.
func decryptBlock(subkeys []uint64, dst, src []byte) {
	cryptBlock(subkeys, dst, src, true)
}

暗号化/復号のメインの処理は以下の cryptBlock() でおこなわれます。 decrypt フラグが false であればサブ鍵が昇順で使われて暗号化され、 true であれば逆の降順で使われて復号されます。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func cryptBlock(subkeys []uint64, dst, src []byte, decrypt bool) {
	b := binary.BigEndian.Uint64(src)
	b = permuteInitialBlock(b)
	left, right := uint32(b>>32), uint32(b)

	var subkey uint64
	for i := 0; i < 16; i++ {
		if decrypt {
			subkey = subkeys[15-i]
		} else {
			subkey = subkeys[i]
		}

		left, right = right, left^feistel(right, subkey)
	}
	// switch left & right and perform final permutation
	preOutput := (uint64(right) << 32) | uint64(left)
	binary.BigEndian.PutUint64(dst, permuteFinalBlock(preOutput))
}

ラウンド関数 $f$ の実装は feistel() という関数ですが今回は割愛します。

Triple DES (3DES)

Triple DES とは

Triple DES (3DES) は、 DES よりも強力になるよう、 DES を3段重ねにした暗号アルゴリズムです。 Triple DES は TLS でも使われています。ただし、 AES (Advanced Encryption Standard) がある今、あえて Triple DES を使う必然性は薄いです。

Triple DES の特徴は、暗号化を3回おこなうのではなく【暗号化 → 復号化 → 暗号化】という重ね方をするところです。これは、すべての鍵を等しくすれば単なる DES と同じように使えるように互換性が確保されているためです。

http://www.idga.org/images/article_images/small/MilioneCryptF5.jpg

3つの鍵のうち鍵1と鍵3を同じにしたものを DES-EDE2 と呼び、 3つの鍵すべてを違うものにしたものを DES-EDE3 と呼びます。 EDE は Encryption → Decryption → Encryption の略です。

DES の鍵長は 64 ビットなので、 DES-EDE2 であれば鍵の長さは 128 ビット、 DES-EDE3 なら 192 ビットになります。したがって暗号強度的には DES-EDE3 を用いるほうがよいです。

Triple DES を使ってみる

Triple DES も DES と同じ crypto/des パッケージに入っています。 Triple DES 用のオブジェクトは NewTripleDESCipher() で生成します。渡す鍵の長さは 24 バイト (192 ビット) になります。この戻り値も cipher.Block インターフェースですので、 DES の場合と使い方は同じです。

http://play.golang.org/p/UfXv32bO8e

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
package main

import (
	"crypto/des"
	"fmt"
)

func main() {
	// 鍵の長さは 24 バイトにしないとエラー
	key := []byte("this is 3des private key")

	// Triple DES 暗号化用オブジェクトを生成する
	c, err := des.NewTripleDESCipher(key)
	if err != nil {
		panic(err)
	}

	// 暗号化される平文の長さは 8 バイト
	plainText := []byte("plaintxt")
	// 暗号化された byte 列を格納する slice を用意する
	encrypted := make([]byte, des.BlockSize)
	// Triple DES で暗号化をおこなう
	c.Encrypt(encrypted, plainText)
	// 結果は暗号化されている
	fmt.Println(string(encrypted)) //=> �Y����4�

	// Triple DES で復号する
	decrypted := make([]byte, des.BlockSize)
	c.Decrypt(decrypted, encrypted)
	fmt.Println(string(decrypted)) //=> plaintxt
}

Go での実装

Triple DES を実装した cipher.Block インターフェースの実体は以下の tripleDESCipher 構造体です。フィールドには desCipher を3つ持っています。

1
2
3
4
// A tripleDESCipher is an instance of TripleDES encryption.
type tripleDESCipher struct {
	cipher1, cipher2, cipher3 desCipher
}

NewTripleDESCipher() コンストラクタは以下のようになっています。鍵の長さは 24 バイト (192 ビット) でないとエラーになります。 3 つの desCipher はそれぞれ、元の鍵の 8 バイト目まで、9 から 16 バイト目まで、 17 から 24 バイト目までを鍵にしてサブ鍵を生成します。

1
2
3
4
5
6
7
8
9
10
11
12
// NewTripleDESCipher creates and returns a new cipher.Block.
func NewTripleDESCipher(key []byte) (cipher.Block, error) {
	if len(key) != 24 {
		return nil, KeySizeError(len(key))
	}

	c := new(tripleDESCipher)
	c.cipher1.generateSubkeys(key[:8])
	c.cipher2.generateSubkeys(key[8:16])
	c.cipher3.generateSubkeys(key[16:])
	return c, nil
}

暗号化/復号をおこなう Encrypt()/Decrypt() メソッドの実装は以下のようになっています。 Triple DES のアルゴリズムそのままに、 Encrypt() では各 desCipher が順に【暗号化 → 復号化 → 暗号化】の処理をおこないます。一方 Decrypt() では逆に【復号化 → 暗号化 → 復号化】という順で処理をおこなっていますね。

1
2
3
4
5
6
7
8
9
10
11
func (c *tripleDESCipher) Encrypt(dst, src []byte) {
	c.cipher1.Encrypt(dst, src)
	c.cipher2.Decrypt(dst, dst)
	c.cipher3.Encrypt(dst, dst)
}

func (c *tripleDESCipher) Decrypt(dst, src []byte) {
	c.cipher3.Decrypt(dst, src)
	c.cipher2.Encrypt(dst, dst)
	c.cipher1.Decrypt(dst, dst)
}

次回は AES (Advanced Encryption Standard) についての記事を書く予定です。