Sボックス

出典: フリー百科事典『ウィキペディア（Wikipedia）』

暗号技術において、Sボックス (substitution box or S-box) とは、共通鍵暗号の基本部品の一つである関数のことである。典型的にはブロック暗号で、平文と暗号文の相関を壊すための仕組みとして使用され、暗号解読に耐性を有するように注意深く選択する必要がある部品である。

[編集] 概要

S-boxは、m ビットの入力を n ビット出力に変換する関数であり、m×n のルックアップテーブルによって実装できる。

通常は、DESのように固定テーブルとして定義されるが、暗号によっては鍵によってテーブルを動的に生成して使用するものもある。動的に生成する例として、BlowfishやTwofish がある。

1970年代に設計されたDESでは6×4-ビットのS-boxを8種類使用しているが、2000年代に設計されたAESやCamelliaでは8×8-ビットのS-boxを1種類している（Camelliaでは4種あるが中味は1つ）。これはソフトウェアやハードウェアでの実装時に、スピード優先だけではなく、サイズ縮小を優先させた実装も考慮したためである。

S-boxの設計は、DES作成時にはIBM大型コンピュータを何ヶ月か使ったほど設計は難しい、と言われている。Lucifer暗号はSボックスがとても弱いため、40個の選択平文で破れた。DESは設計時に差分解読法への耐性を持つことを設計方針にしていたことが後に公開された。

1990年代前半に差分解読法・線形解読法が見つかり、これらの解読法に耐性を持つことが安全なS-boxの必要条件と認識された。（証明されていないが）2の拡大体 GF(2^8)での逆変換が差分・線形解読に対して最も強いテーブルと考えられ、AESやCamelliaで採用されている。

[編集] DESのS-box

具体例としてDESの 6×4-ビットの S-box の一つ S₅ を示す:

S₅		入力の中間4ビット
S₅		0000	0001	0010	0011	0100	0101	0110	0111	1000	1001	1010	1011	1100	1101	1110	1111
MSBとLSB	00	0010	1100	0100	0001	0111	1100	1011	0110	1000	0101	0011	1111	1101	0000	1110	1001
	01	1110	1011	0010	1100	0100	0111	1101	0001	0101	0000	1111	1100	0011	1001	1000	0110
	10	0100	0010	0001	1011	1100	1101	0111	1000	1111	1001	1100	0101	0110	0011	0000	1110
	11	1011	1000	1100	0111	0001	1110	0010	1101	0110	1111	0000	1001	1100	0100	0101	0011

入力6ビットを中間の4ビットと、MSB,LSBの2ビットに分けて、行・列を選択して、出力4ビットを得る。例えば、入力 "011011" のとき、MSB,LSBは "01" で、中間の4ビットは "1101" である。そして出力として選択される4ビットは "1001" となる。

DESは、規格作成時に8個あるS-boxの設計方針が公開されなかったため、設計者だけが知っているバックドアが仕組まれているのではないかという点について多年に渡る研究がなされた。そして、差分解読法が(再)発見され、線形解読法によるDESの解読実験が成功した1994年になってS-boxの設計方針について公開された。それによるとS-boxは差分解読について耐性を有するように注意深く設計されていたが、線形解読法に対しては考慮されていなかった。

[編集] 参考文献

Coppersmith, Don. (1994). The data encryption standard (DES) and its strength against attacks. IBM Journal of Research and Development, 38(3), 243–250. [1]
S. Mister and C. Adams, "Practical S-Box Design," Workshop on Selected Areas in Cryptography (SAC '96) Workshop Record, Queens University, 1996, pp. 61–76
B.SCHNEIER "Applied Cryptography" p.296-298