DES の仕組み

DES の鍵 K は 64 ビットで、そのうち 8 ビットはパリティー検査ビットで、実質は残りの 56 ビットから構成されている。 DES では以下のようにして、鍵 K を用いて、64 ビットの平文 x が 64 ビットの暗号文 y に変換される。

  1. x を長さ 64 のビット列とする。最初に定められた置換 (initial parmutation) IP を x に施す。これを次のように略記する。

    x 0 = IP( x ) = ( L 0 , R 0 )    ( L 0 は左 32 ビット、 R 0 は右 32 ビット)
     
  2. ( L i , R i ) (1≦i≦16)  を次のようにして順番に定める。

    ( L i - 1 ,  R i - 1 ) ---> ( L i ,  R i ) = ( R i - 1 ,  L i - 1  XOR  f ( R i - 1 , K i ) )
     

    但し、

解読の方法

f の構成法を知らなくても、暗号化 x --->y の逆写像はすぐわかる。基本的には ( L i ,  R i ) から ( L i - 1 ,  R i - 1 ) が決定できればよいだけであるが、

　

R i - 1 = L i
L i - 1 = R i  XOR  f ( L i , K i )

となるから明らかである。(mod 2 では 1 = -1 であることに注意。)

初期置換 IP

初期置換 IP は次で与えられる置換である。

　

58    50   42    34    26   18    10    2


60    52   44    36    28   20    12    4


62    54   46    38    30   22    14    6


64    56   48    40    32   24    16    8


57    49   41    33    25   17     9    1


59    51   43    35    27   19    11    3


61    53   45    37    29   21    13    5


63    55   47    39    31   23    15    7

すなわち、IP によってもとの 58 番目のビットが 1 番目に来て、50 番目のビットが 2 番目に来て、 ... もとの最期のビットが 7 番目のビットとなるわけである。 IP - 1 は次で与えられる。

　

40     8   48    16    56   24    64   32


39     7   47    15    55   23    63   31


38     6   46    14    54   22    62   30


37     5   45    13    53   21    61   29


36     4   44    12    52   20    60   28


35     3   43    11    51   19    59   27


34     2   42    10    50   18    58   26


33     1   41     9    49   17    57   25

関数 f に関して

長さ 32 のビット列 R と長さ 48 のビット列 K に対して、 f( R, K ) の構成法を説明しよう。最初に、次の対応で R に対して長さ 48 のビット列 E(R) を生成する。

　

32    1     2    3     4     5


 4    5     6    7     8     9


 8    9    10   11    12    13


12   13    14   15    16    17


16   17    18   19    20    21


20   21    22   23    24    25


24   25    26   27    28    29


28   29    30   31    32     1

即ち、E(R) の最初の 3 ビットは R の 32 番目、1 番目、 2 番目のビットである。このあとで、E(R) と K の排他的論理和  E(R) XOR K  を考え、これを、長さ 6 の 8 個のビット列 B 1 , B 2 , ... B 8 にわける :

　


E(R)  XOR  K = B 1 B 2 ... B 8    (右辺は単に横にならべたビット列である)
 

更に長さ 6 の各ビット列 B i を長さ 4 のビット列 S i ( B i ) に変換し、これをならべたものを更に置換 P で変換したものが f ( R, K ) である :

　


f ( R, K ) = P( S 1 ( B 1 ) S 2 ( B 2 ) ... S 8 ( B 8 ) )
 

但し、置換 P は

　

16   7  20  21


29  12  28  17


 1  15  23  26


 5  18  31  10


 2   8  24  14


32  27   3   9


19  13  30   6


22  11   4  25

で与えられ、ビット列 S i ( B i ) は次のようにして決める。 S i は成分が 0 から 16 までの整数からなる (4, 16) 行列で、例えば S 1 は次によって与えられる :

　

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

i = 1 の場合を例に取って、長さ 4 のビット列 S 1 ( B 1 ) の定め方を説明する。 B 1 は長さ 6 のビット列であるから、最初と最期のビットから、 2 桁の 2 進数が構成でき 0 から 3 までの整数を表す。 B i の中央の 4 個のビットから 4 桁の 2 進数を構成でき 0 から 15 までの整数を表す。そこでこれらをそれぞれ S 1 の行番号、列番号とみなす。 (但し番号は 0 から始める。) すると S 1 の成分が定まることになり、0 から 15 までの整数、すなわち長さ 4 のビット列 S 1 (B 1 ) が定まることになるのである。例えば B 1 = 011011 であれば、行番号は 01 (=1), 列番号は 1101 (= 13) となり、 S 1 の (1,13) 成分は 5 (表の赤の文字) であるから

　


S 1 ( B 1 ) = 0101
 

となる。S i (1≦i≦8) に関しては FIPS 46-3 に具体的な形が載っている。

キー スケジュール (key schedule)

56 ビットの K から 48 ビットの K 1 , K 2 , ..., K 16 を生成するアルゴリズムをキー スケジュールと呼ぶ。キー スケジュールにおいては最初にビット列 K に適当な置換選択 (permuted choice) PC-1 をほどこす。置換選択とは、置換と本質的に同じであるが、この場合には 64 ビットのうち 8, 16, ..., 64 の位置以外のビットを 1 から 56 の位置に動かす。(もともと 8, 16, ..., 64 のビットは各バイトが奇数パリティーになる目的で使用されていた。)

　


PC-1 : { 長さ 64 のビット列 } ---> { 長さ 56 のビット列 }
 

更に長さ 56 のビット列を上、下 28 ビットにわけてその各々に 左巡回シフトを適当にほどこしてから置換選択 PC-2 をほどこす。

　


PC-2 : { 長さ 56 のビット列 } ---> { 長さ 48 のビット列 }
 

置換選択 PC-1 の具体的な形は

　

上の表の成分に 8, 16, ..., 64 があらわれていないことに注意する。左巡回シフトの回数は

　

 1      1


 2      1


 3      2


 4      2


 5      2


 6      2


 7      2


 8      2


 9      1


10      2


11      2


12      2


13      2


14      2


15      2


16      1

この表は第 1 段、第 2 段、第 3 段、...では左巡回シフトをそれぞれ 1 回、1 回、2 回 ... することを意味し、例えば K 3 を得るためには 1 + 1 + 2 回左巡回シフトする。置換選択 PC-2 の具体的形は

　

14   17    11   24     1     5


 3   28    15    6    21    10


23   19    12    4    26     8


16    7    27   20    13     2


41   52    31   37    47    55


30   40    51   45    33    48


44   49    39   56    34    53


46   42    50   36    29    32

成分は全部で 48 個であるから、1 から 56 までの数が全部出てはいない。

3 重 DES (triple DES)

56 ビットの鍵 K に対しての DES の暗号化、解読をそれぞれ e K , d K であらわす。 3 個の 56 ビットの鍵 K 1 , K 2 , K 3 に対して

　


x ---> e K 3 ( d K 2 ( e K 1 (x) ) )   (x は長さ 64 のビット列)
 

が 3 重 DES である。この暗号化ではキーが大きくなるため、しらみつぶしにキーを探す攻撃に対しては、 DES よりはるかに安全になり、しかも K 1 = K 2 = K 3 であれば、既存の DES に一致するため、DES との互換性が保証されることになる。

DES の使用モード

長さ 64 のビット列の場合の DES の暗号化の方法を適用することによって、より長いビット列を暗号化することができるが、それには幾つかのモードがある。いずれの場合も平文を 64 ビットごとのブロック x 1 , x 2 , x 3 ... に分割し、暗号分のブロック y 1 , y 2 , y 3 ... を出力する。以下では y = e K ( x ) は 64 ビットの平文 x の鍵 K による暗号化 y を表す。

　

ECB (=electronic codebook) モード

最も簡単なモードで、鍵 K を固定して、各 y i を次で定める

y i = e K ( x i )


OFB (=output feedback) モード

64 ビットの初期ベクトル V を与え、

z 0 = V,    z i = e K (e i - 1 )   (i = 1, 2, 3, .. )

によって鍵 (あるいは鍵ストリーム) z 1 , z 2 , ... を生成し、 y i を次で定める。

y i = x i  XOR z i


CFB (=cipher feedback) モード

64 ビットの初期ベクトル V を与え、y i を次で定める。

y 0 = V,   y 1 = x 1  XOR e K ( y 0 ),   y 2 = x 2  XOR e K ( y 1 ), ...