Crypto/DESとは何か?
cryptoとは、暗号という意味で、encryptoが暗号化を表します。UNIXでcryptoといえば、通常DES暗号を指します。
DES(data encryption standard)は、アメリカ商務省標準局(NBS)が1977年に定めたデータ暗号標準で、FIPS PUB 46として発行された。政府内の、機密ではないが、取り扱い注意のコンピュータデータの暗号化が目的である。しかし、一般商用にも推奨している。DESは、64ビット入力を64ビット出力に変えるブロック暗号である。鍵も64ビット長だが、そのうちの8ビットはパリティに使われているので、実質56ビットである。UNIXのパスワードを暗号化しているのも、このDESで、得られた鍵を使って、空白(0x2020202020)を暗号化することで作成される。
DESは、64ビット入力に対して、一定の初期置換IPをほどこしたあと、左右32ビットずつに分けて、同一構造の変換を16回ほどこす。第n番目の同一構造の変換のデータ系列入力を(Ln-1,Rn-1)、鍵系列入力をKnとすると、出力(Ln,Rn)は、
Ln=Rn-1
Rn=Ln-1+f(Rn-1,Kn)
で与えられる。ここで、+はビットごとの排他的論理和(XOR)をしめす。また、f(R,K)は、48ビットのKに依存して32ビットのRを変換し、32ビットを出力する非線形関数である。
16回の変換のあと、左右32ビットを入れ替え、初期置換の逆置換IP-1をほどこした結果が暗号文64ビットである。
鍵入力64ビットに対して、選択的転置PC−1でパリティ8ビットを除去してビット入れ替えをおこなったあと、左右28ビットずつのブロック(C0,D0)に分ける。これらのブロックはおのおの左巡回シフト(LS)を16回受ける。
各シフトのあとに、両ブロックを合わせた58ビット(Cn,Dn)から選択的転置PC−2により48ビットが選ばれ、かつビット入れ替えをうけて、前記関数fの入力の一つKnになる。これらが16回繰り返される。16回の左巡回シフトの合計シフト量は28となるように決められているので、(C16,D16)は最初の(C0,D0)に等しい。
選択的転置PC−1はたとえば、入力の第57番目のビットが第1番目に出力され、入力の第49番目のビットが第2番目に出力される。表の上4行がC0に、下4行がD0となる。この表に8の倍数がないのは、それらはパリティなので使われないからである。
選択的転置PC−2は入力の9,18,22,25,35,38,43,54番目の各ビットは用いられない。すなわち、入力56ビットに対して、出力は48ビットの縮約型転置である。
暗号化過程で用いられている非線形な関数f(R,K)は32ビットRと48ビットKに対して、32ビットを出力する。まず、32ビットRを、拡大型転置Eにより48ビットに拡大する。これにKの48ビットをビットごとにXORする。この結果の48ビットを6ビットずつに分けて、8個のSボックスに入力する。各Sボックスは6ビット入力に対して、4ビットを出力する。最後に全Sボックスからの32ビットに対して、転置Pでビットの入れ替えをおこなってf(R,K)をえる。選択的転置Eは、32ビット入力に対して48ビットを出力する。転置Pは32ビットを入れ替える。表の見方は今までと同じである。
Sボックスの具体的な変換は、入力6ビットに対して、第1番目と第6番目のビットを2進数とみなした数字でSボックス表の行を指定する。ただし、行番号は順次0,1,2,3とする。次に入力6ビットの残り4ビットをやはり2進数とみなした数字で今指定した行の列番号を指定する。ただし、列番号は左から順次、0,1,2,…,15とする。このようにして指定された行と列の交点の数字を2進数表現した4ビットを出力する。
DESの中で、非線形な部分はSボックスのみである。したがって、Sボックスは強度上きわめて重要である。Sボックスの決定には非線形の条件だけでなく、相関性、ブール最簡表現項数を始め、多くの条件が考慮されている。
DESの中で、鍵から鍵系列K1,K2,…,K16をつくる部分、Sボックス、転置Pは規定というよりも推奨案としての例にすぎない。FIPS PUB 46にも付録に記載されている。これらは暗号強度に対する影響が大きいため、使用者が責任をもって定めるべき、という認識に基づいている。しかし、実際には推奨案通り使っている人がほとんどである。
鍵となるSボックスの値は以下の通り。何故このような値を取っているのかは謎とされていて、噂ではアリメカ政府が簡単に解読出来るようなバックドアが仕掛けられているといわれている。
static char S[8][64] = {
{ 14, 4,13, 1, 2,15,11, 8, 3,10, 6,12, 5, 9, 0, 7,
0,15, 7, 4,14, 2,13, 1,10, 6,12,11, 9, 5, 3, 8,
4, 1,14, 8,13, 6, 2,11,15,12, 9, 7, 3,10, 5, 0,
15,12, 8, 2, 4, 9, 1, 7, 5,11, 3,14,10, 0, 6,13 },
{ 15, 1, 8,14, 6,11, 3, 4, 9, 7, 2,13,12, 0, 5,10,
3,13, 4, 7,15, 2, 8,14,12, 0, 1,10, 6, 9,11, 5,
0,14, 7,11,10, 4,13, 1, 5, 8,12, 6, 9, 3, 2,15,
13, 8,10, 1, 3,15, 4, 2,11, 6, 7,12, 0, 5,14, 9 },
{ 10, 0, 9,14, 6, 3,15, 5, 1,13,12, 7,11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6,10, 2, 8, 5,14,12,11,15, 1,
13, 6, 4, 9, 8,15, 3, 0,11, 1, 2,12, 5,10,14, 7,
1,10,13, 0, 6, 9, 8, 7, 4,15,14, 3,11, 5, 2,12 },
{ 7,13,14, 3, 0, 6, 9,10, 1, 2, 8, 5,11,12, 4,15,
13, 8,11, 5, 6,15, 0, 3, 4, 7, 2,12, 1,10,14, 9,
10, 6, 9, 0,12,11, 7,13,15, 1, 3,14, 5, 2, 8, 4,
3,15, 0, 6,10, 1,13, 8, 9, 4, 5,11,12, 7, 2,14 },
{ 2,12, 4, 1, 7,10,11, 6, 8, 5, 3,15,13, 0,14, 9,
14,11, 2,12, 4, 7,13, 1, 5, 0,15,10, 3, 9, 8, 6,
4, 2, 1,11,10,13, 7, 8,15, 9,12, 5, 6, 3, 0,14,
11, 8,12, 7, 1,14, 2,13, 6,15, 0, 9,10, 4, 5, 3 },
{ 12, 1,10,15, 9, 2, 6, 8, 0,13, 3, 4,14, 7, 5,11,
10,15, 4, 2, 7,12, 9, 5, 6, 1,13,14, 0,11, 3, 8,
9,14,15, 5, 2, 8,12, 3, 7, 0, 4,10, 1,13,11, 6,
4, 3, 2,12, 9, 5,15,10,11,14, 1, 7, 6, 0, 8,13 },
{ 4,11, 2,14,15, 0, 8,13, 3,12, 9, 7, 5,10, 6, 1,
13, 0,11, 7, 4, 9, 1,10,14, 3, 5,12, 2,15, 8, 6,
1, 4,11,13,12, 3, 7,14,10,15, 6, 8, 0, 5, 9, 2,
6,11,13, 8, 1, 4,10, 7, 9, 5, 0,15,14, 2, 3,12 },
{ 13, 2, 8, 4, 6,15,11, 1,10, 9, 3,14, 5, 0,12, 7,
1,15,13, 8,10, 3, 7, 4,12, 5, 6,11, 0,14, 9, 2,
7,11, 4, 1, 9,12,14, 2, 0, 6,10,13,15, 3, 5, 8,
2, 1,14, 7, 4,10, 8,13,15,12, 9, 0, 3, 5, 6,11 }
};