Sボックス

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

概要[編集]

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

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

1970年代に設計されたDESでは6ビット入力 4ビット出力の S-box を8種類使用しているが、2000年代に設計されたAESCamelliaでは8ビット入出力のS-boxを1種類使用している(Camelliaでは4種の S-box を持つが、三つのS-boxは一つのS-boxの単純な変換となっている)。これはソフトウェアやハードウェアでの実装時に、スピード優先だけではなく、サイズ縮小を優先させた実装も考慮したためである。

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

1990年代前半に差分解読法線形解読法が見つかり、これらの解読法に耐性を持つことが安全なS-boxの必要条件と認識された。(証明されていないが)nビット入出力のS-boxの場合、2の拡大体 GF(2m)での逆変換が差分・線形解読に対して最も強いテーブルと考えられている。このとき、差分確率及び線形確率は、 n が奇数の場合 2-n+1 、偶数の場合 2-n+2 となる。AESやCamelliaではそれを線形変換したものが採用されており、差分確率及び線形確率は、 2-6 である。

近年では、実装サイズの縮小を目的に小さいS-Boxを複数組み合わせて大きなS-Boxを構成する方法がとられることがある。この場合上記のような最善の最大差分(あるいは線形)確率を持たないが、暗号全体で十分な最大特性差分(あるいは線形)確率を持つように設計される。

DESのS-box[編集]

具体例としてDESの 6ビット入力 4ビット出力の S-box の一つ S5 を示す:

S5 入力の中間4ビット
0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111
MSBLSB 00 0010 1100 0100 0001 0111 1010 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

関連項目[編集]

外部リンク[編集]