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ビットローテートさせる。

脚注・出典

参考文献 
 Eli Biham, Adi Shamir (1991). "Differential Cryptanalysis of Snefru, Khafre, REDOC-II, LOKI and Lucifer". CRYPTO 1991: pp156–171
 Whitfield Diffie, Susan Landau (1998). "Privacy on the Line: The Politics of Wiretapping and Encryption".
 Steven Levy. (2001). "Crypto: Secrecy and Privacy in the New Code War" (Penguin Press Science).

外部リンク 
 John Savard's description of Lucifer

IBM