Lucifer (暗号)

Luciferは、ホルスト・ファイステルらがIBMにて開発したいくつかの初期の民間用ブロック暗号の総称である。DESの基になった。Luciferのうちの1つは DTD-1 という名称で1970年代に銀行で使われていた。
概要.
《アメリカ合衆国特許番号 3,798,359; 1971年7月》の版では、48ビットの鍵を使い、48ビットのブロックを操作する。SPN構造で2つの4ビットSボックスを使用する。鍵によってどちらのSボックスを使うかを決める。特許には、24ビットを一度に操作する方式と8ビットずつ順次操作する方式が記されている。
もうひとつの《アメリカ合衆国特許番号 3,796,830; 1971年11月》の版では、64ビットの鍵を使い、32ビットのブロックを操作する。加算と4を法とする合同式演算、ひとつの4ビットSボックスを使う。4ビットずつ処理する方式になっている。ブロック暗号の実装としては非常に小さい。
より強力な版として《Feistel, 1973》 があり、128ビットの鍵を使い、128ビットブロックを操作する。SPN構造で2つの4ビットSボックスを使う。鍵によってどちらのSボックスを使うかを決める。
その後、16ラウンドのFeistel構造で、128ビットのブロックと128ビットの鍵を採用したLuciferが《Sorkin, 1984》 に記されている。この版は差分解読法に弱い。236の選択平文で236の時間計算量で鍵の半分を破ることができる(Ben-Aroya and Biham, 1996)。
IBMはFeistel構造版のLuciferをDESの候補として提出した。設計の手直しを経て（鍵を56ビット、ブロック長を64ビットに縮め、差分解読法への耐性を強化した）、1977年に Data Encryption Standard とした。
"Lucifer"（魔王）という名前は "Demon"（悪魔）から発想した駄洒落である。そしてDemonは、ファイステルが開発していたプライバシーシステムの名称 "Demonstration" を短縮したものである。これは、開発に使っていたオペレーティングシステムが長い名前を扱えなかったためだという。
Sorkin版の詳細.
(Sorkin, 1984)で記述されている版は、DESと同様に16ラウンドのFeistel構造だが、最初と最後の並べ替えがない。鍵長とブロック長は共に128ビットである。Feistel関数はブロックの半分である64ビットを鍵の半分である64ビットの部分鍵と8ビットの交換制御ビット (interchange control bits、ICBs) で操作する。ICBsはビットの入れ替え操作を制御する。64ビットのデータブロックを8個の8ビットのかたまり（バイト）の並びとみなし、特定のバイトに対応するICBがゼロなら、4ビットずつ（ニブル）の左右を入れ替える。対応するICBが1なら、そのバイトはそのままにしておく。各バイトは次に2つの4×4ビットのSボックスで操作される。それらの出力を連結した上で、部分鍵とXOR演算を行う。これを "key interruption" と呼ぶ。その後、2段階の並べ替えを行う。1回目はバイト単位に固定の並べ替えを行う。2回目はバイト間でビットの入れ替えを行う。
鍵スケジュールのアルゴリズムは比較的単純である。まず128ビットの鍵をシフトレジスタにロードする。ラウンドごとにそのレジスタの左半分の64ビットが部分鍵に使われ、右端の8ビットがICBビットとなる。ラウンドごとにレジスタを左に56ビットローテートさせる。