DESとTDEAの基礎

※この記事は https://kunosu.qrunch.io/entries/QhK5lynPQw0jAPb0 に移動しました。

---

# はじめに

DES(Data Encryption Standard)とTDEA(Triple Data Encryption Algorithm)について『暗号技術入門 第3版』[^1] で勉強したので、そのときのメモをQiita用に変換して投稿する。

また、すべてMarkdownで書いてみる一環として、mermaidで図を書いてみた。
本当はQiitaがmermaidに対応していればいいが、していないためここでは [Mermaid Live Editor](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiIiwibWVybWFpZCI6eyJ0aGVtZSI6ImRlZmF1bHQifX0) を用いて画像に変換。
mermaidのコードはコメントアウトにした。

# DESとは

- 1977年にアメリカ連邦政府標準の暗号方式として採用された。
- 共通鍵暗号の1つ。
	- 共通鍵暗号: 暗号化と復号に同じ鍵を用いる暗号方式
- 現在は危殆化により、使用すべきでない暗号。
	- TDEAも2023年以降は使用禁止になる。 → 今後は、共通鍵暗号方式としてAES(Advanced Encryption Standard)を使うことになる。
	- 過去の暗号文を復号する目的ならOK

## 処理の全体的なイメージ

- 鍵長: 8byte
- 平文8byteごとに暗号化を実施する。
	- この1かたまりを **ブロック(block)** という。

### 1 blockのみの暗号化の処理イメージ

フローチャートで示す。

<details><summary>凡例(折りたたみ)</summary><div>

[![](https://mermaid.ink/img/eyJjb2RlIjoiZ3JhcGggVERcblxuc3RhcnQoW3N0YXJ0XSktLT4gaW5wdXRfZGF0YVsvaW5wdXQgZGF0YS9dIC0tPiBcbuWHpueQhkFbZnVuYyBBXSAtLT4gaWZ7e2lmfX0gLS0gVHJ1ZSAtLT5cbm91dHB1dF9kYXRhWy9vdXRwdXQgZGF0YS9dIC0tPiBFbmQoW2VuZF0pXG5cbmlmIC0tIEZhbHNlIC0tPiDlh6bnkIZCW2Z1bmMgQl0gLS0-IG91dHB1dF9kYXRhXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9LCJ1cGRhdGVFZGl0b3IiOmZhbHNlfQ)](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiZ3JhcGggVERcblxuc3RhcnQoW3N0YXJ0XSktLT4gaW5wdXRfZGF0YVsvaW5wdXQgZGF0YS9dIC0tPiBcbuWHpueQhkFbZnVuYyBBXSAtLT4gaWZ7e2lmfX0gLS0gVHJ1ZSAtLT5cbm91dHB1dF9kYXRhWy9vdXRwdXQgZGF0YS9dIC0tPiBFbmQoW2VuZF0pXG5cbmlmIC0tIEZhbHNlIC0tPiDlh6bnkIZCW2Z1bmMgQl0gLS0-IG91dHB1dF9kYXRhXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9LCJ1cGRhdGVFZGl0b3IiOmZhbHNlfQ)

[](
```mermaid
graph TD
start([start])--> input_data[/input data/] --> 
処理A[func A] --> if{{if}} -- True -->
output_data[/output data/] --> End([end])
if -- False --> 処理B[func B] --> output_data
```
)
</details></div>

[![](https://mermaid.ink/img/eyJjb2RlIjoiZ3JhcGggVERcblxuc3R5bGUgREVTIGZpbGw6I2QzZDNkMyxzdHJva2U6IzMzM1xuXG5zdGFydChbc3RhcnRdKSBcbi0tPiBpbnB1dF9kYXRhWy9cInBsYWluIHRleHQoOGJ5dGUpXCIvXVxuLS0-IERFU1tlbmNyeXB0IGJ5IERFU11cbi0tPiBvdXRwdXRfZGF0YVsvXCJjaXBoZXJ0ZXh0KDhieXRlKVwiL11cbi0tPiBFbmQoW2VuZF0pXG5cbmtleVsvXCJrZXkoOGJ5dGUpXCIvXSAtLT4gREVTXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9LCJ1cGRhdGVFZGl0b3IiOmZhbHNlfQ)](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiZ3JhcGggVERcblxuc3R5bGUgREVTIGZpbGw6I2QzZDNkMyxzdHJva2U6IzMzM1xuXG5zdGFydChbc3RhcnRdKSBcbi0tPiBpbnB1dF9kYXRhWy9cInBsYWluIHRleHQoOGJ5dGUpXCIvXVxuLS0-IERFU1tlbmNyeXB0IGJ5IERFU11cbi0tPiBvdXRwdXRfZGF0YVsvXCJjaXBoZXJ0ZXh0KDhieXRlKVwiL11cbi0tPiBFbmQoW2VuZF0pXG5cbmtleVsvXCJrZXkoOGJ5dGUpXCIvXSAtLT4gREVTXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9LCJ1cGRhdGVFZGl0b3IiOmZhbHNlfQ)

[](
```mermaid
graph TD
style DES fill:#d3d3d3,stroke:#333
start([start]) 
--> input_data[/"plain text(8byte)"/]
--> DES[encrypt by DES]
--> output_data[/"ciphertext(8byte)"/]
--> End([end])
key[/"key(8byte)"/] --> DES
```
)

### 1 blockのみの復号の処理イメージ

[![](https://mermaid.ink/img/eyJjb2RlIjoiZ3JhcGggVERcblxuc3R5bGUgREVTIGZpbGw6I2QzZDNkMyxzdHJva2U6IzMzM1xuXG5zdGFydChbc3RhcnRdKSBcbi0tPiBpbnB1dF9kYXRhWy9cImNpcGhlcnRleHQoOGJ5dGUpXCIvXVxuLS0-IERFU1tkZWNyeXB0IGJ5IERFU11cbi0tPiBvdXRwdXRfZGF0YVsvXCJwbGFpbiB0ZXh0KDhieXRlKVwiL11cbi0tPiBFbmQoW2VuZF0pXG5cbmtleVsvXCJrZXkoOGJ5dGUpXCIvXSAtLT4gREVTXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9fQ)](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiZ3JhcGggVERcblxuc3R5bGUgREVTIGZpbGw6I2QzZDNkMyxzdHJva2U6IzMzM1xuXG5zdGFydChbc3RhcnRdKSBcbi0tPiBpbnB1dF9kYXRhWy9cImNpcGhlcnRleHQoOGJ5dGUpXCIvXVxuLS0-IERFU1tkZWNyeXB0IGJ5IERFU11cbi0tPiBvdXRwdXRfZGF0YVsvXCJwbGFpbiB0ZXh0KDhieXRlKVwiL11cbi0tPiBFbmQoW2VuZF0pXG5cbmtleVsvXCJrZXkoOGJ5dGUpXCIvXSAtLT4gREVTXG4iLCJtZXJtYWlkIjp7InRoZW1lIjoiZGVmYXVsdCJ9fQ)

[](
```mermaid
graph TD
style DES fill:#d3d3d3,stroke:#333
start([start]) 
--> input_data[/"ciphertext(8byte)"/]
--> DES[decrypt by DES]
--> output_data[/"plain text(8byte)"/]
--> End([end])
key[/"key(8byte)"/] --> DES
```
)

### 1 block より大きいサイズのデータを扱う方法

1回に8byteしか暗号化/復号できないため、暗号化/復号を繰り返す必要がある。
繰り返しの方法を **モード(mode)** という。(詳しい説明は別の記事でする予定)

## 暗号化処理部分の基本構造

DESの基本構造は ファイステルネットワーク(Feistel network) と呼ばれる。
これは **ラウンド(round)** (= 暗号化の1ステップ分)を何度も繰り返す構造である。
DESでは16回 round を繰り返す。

### 1 round 分の構造

図中の用語の意味

- subkey: 8byte の鍵値から生成される。各 round ごとに異なるsubkeyを使う。
- ラウンド関数f: 4byteのデータと subkey を引数にして、4byteのデータを出力する関数。

![mermaid-diagram-20200321164400.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316183/53f3d22f-57ad-cbe6-6e47-2e5fc6c2e477.png)

[](
```mermaid
graph TD
START([start]) --> plainData[/"plain text(8byte)"/]
plainData --> divided[左右4byteごとに分割]
divided -- 右側4byte --> plainRight[/平文の右側4byte/]
divided -- 左側4byte --> plainLeft[/平文の左側4byte/]
plainRight --> f[ラウンド関数f] --> XOR
subkey[/subkey/] --> f
plainLeft --> XOR --> encLeft[/左側4byteだけ暗号化済みのデータ/]
encLeft --> composite[左右4byteずつを合わせて8byteのデータにする]
plainRight --> composite --> outputData[/1round分の処理結果/]
--> END([end])
```
)

1回分の round で、左側4byteが暗号化される。

復号するときは、暗号化時と同じ処理をするだけでいい(XORの性質で、同じ値のXORは0になるため)。
つまり、ラウンド関数fは逆関数が計算できないような複雑なものでいい。

ではラウンド関数fは具体的に何かという話になるが、この記事では省略する。

### 2回目以降の round

![mermaid-diagram-20200321170105.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/316183/1eabaf9d-1415-3271-6614-83453bce5f1d.png)

[](```mermaid
graph TD
START([start])
--> inputData[/roundへの入力データ 8byte/] 
--> round[1 round]
--> outputData[/roundの出力データ 8byte/]
--> if{{"roundが16回未満"}} -- True --> swap[左右4byte入れ替え] --> inputData
if -- False --> END([end])
subkey[/subkey/] --> round
```
)

復号するときは、subkeyの入力順を逆にしてroundを同じ回数だけ行う。

## DESのまとめ

- 暗号化/復号が同じ構造で行える。 → 回路が組みやすい
- この暗号アルゴリズムの本質はラウンド関数fにある。

# TDEA

Triple-DESともいい、その名の通りDESを3回行うブロック暗号である。
3回演算するため、DESより処理速度が遅い。

## 処理の全体的なイメージ

- 鍵: 8byte × 3つ (= 24byte)
	- 合計の鍵長がDESより長くなるため、DESより暗号強度が高くなる。
- 平文 8byte

### 暗号化

図では key1 → key2 → key3 の順に処理を行う。

[![](https://mermaid.ink/img/eyJjb2RlIjoiZ3JhcGggVERcblxuU1RBUlQoW3N0YXJ0XSkgXG5cdC0tPiBpbnB1dERhdGFbL1wicGxhaW4gdGV4dCg4Ynl0ZSlcIi9dXG5cdC0tPiBERVMxW2VuY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTFbL1wiY2lwaGVydGV4dCBieSBrZXkxKDhieXRlKVwiL11cblxuXHQtLT4gREVTMltkZWNyeXB0IGJ5IERFU11cblx0LS0-IG91dHB1dERhdGEyWy9cImRlY3J5cHRlZCB0ZXh0IGJ5IGtleTIoOGJ5dGUpXCIvXVxuXG5cdC0tPiBERVMzW2VuY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTNbL1wiY2lwaGVydGV4dCg4Ynl0ZSlcIi9dXG4tLT4gRU5EKFtlbmRdKVxuXG5rZXkxWy9cImtleTEoOGJ5dGUpXCIvXSAtLT4gREVTMVxua2V5MlsvXCJrZXkyKDhieXRlKVwiL10gLS0-IERFUzJcbmtleTNbL1wia2V5Myg4Ynl0ZSlcIi9dIC0tPiBERVMzXG5cbmNsYXNzRGVmIERFUyBmaWxsOiNkM2QzZDMsc3Ryb2tlOiMzMzNcbmNsYXNzIERFUzEsREVTMixERVMzIERFU1xuIiwibWVybWFpZCI6eyJ0aGVtZSI6ImRlZmF1bHQifSwidXBkYXRlRWRpdG9yIjpmYWxzZX0)](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiZ3JhcGggVERcblxuU1RBUlQoW3N0YXJ0XSkgXG5cdC0tPiBpbnB1dERhdGFbL1wicGxhaW4gdGV4dCg4Ynl0ZSlcIi9dXG5cdC0tPiBERVMxW2VuY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTFbL1wiY2lwaGVydGV4dCBieSBrZXkxKDhieXRlKVwiL11cblxuXHQtLT4gREVTMltkZWNyeXB0IGJ5IERFU11cblx0LS0-IG91dHB1dERhdGEyWy9cImRlY3J5cHRlZCB0ZXh0IGJ5IGtleTIoOGJ5dGUpXCIvXVxuXG5cdC0tPiBERVMzW2VuY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTNbL1wiY2lwaGVydGV4dCg4Ynl0ZSlcIi9dXG4tLT4gRU5EKFtlbmRdKVxuXG5rZXkxWy9cImtleTEoOGJ5dGUpXCIvXSAtLT4gREVTMVxua2V5MlsvXCJrZXkyKDhieXRlKVwiL10gLS0-IERFUzJcbmtleTNbL1wia2V5Myg4Ynl0ZSlcIi9dIC0tPiBERVMzXG5cbmNsYXNzRGVmIERFUyBmaWxsOiNkM2QzZDMsc3Ryb2tlOiMzMzNcbmNsYXNzIERFUzEsREVTMixERVMzIERFU1xuIiwibWVybWFpZCI6eyJ0aGVtZSI6ImRlZmF1bHQifSwidXBkYXRlRWRpdG9yIjpmYWxzZX0)

[](
```mermaid
graph TD
START([start]) 
	--> inputData[/"plain text(8byte)"/]
	--> DES1[encrypt by DES]
	--> outputData1[/"ciphertext by key1(8byte)"/]
	--> DES2[decrypt by DES]
	--> outputData2[/"decrypted text by key2(8byte)"/]
	--> DES3[encrypt by DES]
	--> outputData3[/"ciphertext(8byte)"/]
--> END([end])
key1[/"key1(8byte)"/] --> DES1
key2[/"key2(8byte)"/] --> DES2
key3[/"key3(8byte)"/] --> DES3
classDef DES fill:#d3d3d3,stroke:#333
class DES1,DES2,DES3 DES
```
)

### 復号

暗号化と復号の順番を入れ替える。このとき、設定する鍵の順番を暗号化時と逆にする。
key1 → key2 → key3 の順で暗号化した場合、key3 → key2 → key1 の順で復号する。

[![](https://mermaid.ink/img/eyJjb2RlIjoiZ3JhcGggVERcblxuU1RBUlQoW3N0YXJ0XSkgXG5cdC0tPiBpbnB1dERhdGFbL1wiY2lwaGVydGV4dCg4Ynl0ZSlcIi9dXG5cdC0tPiBERVMzW2RlY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTNbL1wiZGVjcnlwdGVkIHRleHQgYnkga2V5Myg4Ynl0ZSlcIi9dXG5cblx0LS0-IERFUzJbZW5jcnlwdCBieSBERVNdXG5cdC0tPiBvdXRwdXREYXRhMlsvXCJjaXBoZXJ0ZXh0IGJ5IGtleTIoOGJ5dGUpXCIvXVxuXG5cdC0tPiBERVMxW2RlY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTFbL1wicGxhaW4gdGV4dCg4Ynl0ZSlcIi9dXG4tLT4gRU5EKFtlbmRdKVxuXG5rZXkxWy9cImtleTEoOGJ5dGUpXCIvXSAtLT4gREVTMVxua2V5MlsvXCJrZXkyKDhieXRlKVwiL10gLS0-IERFUzJcbmtleTNbL1wia2V5Myg4Ynl0ZSlcIi9dIC0tPiBERVMzXG5cbmNsYXNzRGVmIERFUyBmaWxsOiNkM2QzZDMsc3Ryb2tlOiMzMzNcbmNsYXNzIERFUzEsREVTMixERVMzIERFUyIsIm1lcm1haWQiOnsidGhlbWUiOiJkZWZhdWx0In0sInVwZGF0ZUVkaXRvciI6ZmFsc2V9)](https://mermaid-js.github.io/mermaid-live-editor/#/edit/eyJjb2RlIjoiZ3JhcGggVERcblxuU1RBUlQoW3N0YXJ0XSkgXG5cdC0tPiBpbnB1dERhdGFbL1wiY2lwaGVydGV4dCg4Ynl0ZSlcIi9dXG5cdC0tPiBERVMzW2RlY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTNbL1wiZGVjcnlwdGVkIHRleHQgYnkga2V5Myg4Ynl0ZSlcIi9dXG5cblx0LS0-IERFUzJbZW5jcnlwdCBieSBERVNdXG5cdC0tPiBvdXRwdXREYXRhMlsvXCJjaXBoZXJ0ZXh0IGJ5IGtleTIoOGJ5dGUpXCIvXVxuXG5cdC0tPiBERVMxW2RlY3J5cHQgYnkgREVTXVxuXHQtLT4gb3V0cHV0RGF0YTFbL1wicGxhaW4gdGV4dCg4Ynl0ZSlcIi9dXG4tLT4gRU5EKFtlbmRdKVxuXG5rZXkxWy9cImtleTEoOGJ5dGUpXCIvXSAtLT4gREVTMVxua2V5MlsvXCJrZXkyKDhieXRlKVwiL10gLS0-IERFUzJcbmtleTNbL1wia2V5Myg4Ynl0ZSlcIi9dIC0tPiBERVMzXG5cbmNsYXNzRGVmIERFUyBmaWxsOiNkM2QzZDMsc3Ryb2tlOiMzMzNcbmNsYXNzIERFUzEsREVTMixERVMzIERFUyIsIm1lcm1haWQiOnsidGhlbWUiOiJkZWZhdWx0In0sInVwZGF0ZUVkaXRvciI6ZmFsc2V9)

[](```mermaid
graph TD
START([start]) 
	--> inputData[/"ciphertext(8byte)"/]
	--> DES3[decrypt by DES]
	--> outputData3[/"decrypted text by key3(8byte)"/]
	--> DES2[encrypt by DES]
	--> outputData2[/"ciphertext by key2(8byte)"/]
	--> DES1[decrypt by DES]
	--> outputData1[/"plain text(8byte)"/]
--> END([end])
key1[/"key1(8byte)"/] --> DES1
key2[/"key2(8byte)"/] --> DES2
key3[/"key3(8byte)"/] --> DES3
classDef DES fill:#d3d3d3,stroke:#333
class DES1,DES2,DES3 DES
```
)

## 鍵の数

- 3つとも違うとき
	- **DES-EDE3** という
	- **EDE** = Encryption -> Decryption -> Encryption の流れのこと
- 2つだけ違うとき
	- **DES-EDE2** という
	- 鍵1, 3に同じ鍵を使う
- 3つとも同じ
	- 普通のDESと同じになる
		- 2回目の復号で平文に戻るため
	- TDEA の回路で通常の DES の暗号化/復号ができる

[^1]: 結城浩(2015)『暗号技術入門 第3版』