FEALのソースを表示

{{Infobox Encryption method
| name          = FEAL
| image         = [[Image:FEAL InfoBox Diagram.png|300px|center]]
| caption       = The FEAL Feistel function
| designers     = 清水明宏、宮口庄司（[[日本電信電話|NTT]]）
| publish date  = FEAL-4：1987、FEAL-N/NX：1990
| derived from  = 
| derived to    = 
| key size      = 64 bits (FEAL), 128 bits (FEAL-NX)
| block size    = 64 bits
| structure     = [[Feistel構造]]
| rounds        = FEAL-4：4、FEAL-8：8、FEAL-N/NX：可変(32以上)
| cryptanalysis = FEAL-4：5つの[[既知平文]]を用いた[[線形解読法]]で解読可能 (Matsui and Yamagishi, 1992). FEAL-N/NX：[[差分解読法]]により、31ラウンドまで解読可能 (Biham and Shamir, 1991).
}}
'''FEAL'''（the '''Fast Data Encipherment Algorithm'''）とは、[[1987年]]に、[[日本電信電話|NTT]]にいた清水明宏と宮口庄司が提案した64bit[[ブロック暗号]]である。[[Data Encryption Standard|DES]]（Data Encryption Standard）の代替品となることを目的として開発された。

== 概要 ==
FEALは、DESと同じく[[Feistel構造]]を採用したブロック長64ビットのブロック暗号である。

1987年当初は、FEAL-4 としてラウンド数4、鍵長64ビットで、その後、1988年にFEAL-8（ラウンド数 8）を経て、1990年にFEAL-N（Nは可変、32以上が望ましい)と鍵長を128ビットに拡張した FEAL-NX に改定された。

ソフトウェアで効率的に実装できるようにビット単位の転置やテーブル参照による[[Sボックス]]は採用せずに、あみだ構造のラウンド関数と、8ビット単位の算術演算やシフト演算等、CPUで容易に実装可能な演算のみを使用している点に特徴がある。その結果、FEAL-8は8ビットCPUでのソフトウェア実装時の処理速度がDESよりも高い。

あみだ構造のラウンド関数は、設計者たちの評価によれば、DESのラウンド関数よりもデータ攪拌効果が高く、安全であると主張されていた。しかし、このアルゴリズムは発表直後から様々な[[暗号解読]]を試みられ、暗号学者たちが[[差分解読法]]や[[線形解読法]]を発見するきっかけとなった。

1994年に、ISO/IEC9979にもとづく暗号アルゴリズム登録制度に登録されている（登録番号10）。

== 構造 ==
FEAL のブロック長は64ビットで、Feistel構造を採用し、FEAL-4はラウンド段数４、FEAL-8はラウンド段数８、そしてFEAL-N/NXはラウンド段数は可変である(Nは32以上)。

鍵長は、FEAL-Nは64ビット、FEAL-NXは128ビットである。FEAL-NXで鍵128ビットうち、右64ビットをすべて0とした場合、FEAL-Nと等価になる。

最初と最後に拡大鍵との排他的論理和（XOR、whitening と呼ばれる処理）と、左32ビットと右32ビットをXORし、右32ビットを更新する処理が設けられている。<!-- このラウンド関数なし単なるXORの処理が有ることで解読に必要な計算量が増加しているとされる。;出典が行方不明 -->

[[ファイル:FEAL InfoBox Diagram.png|thumb|220px|FEALのラウンド関数]]
FEALのラウンド関数は、拡大鍵16ビットを用いて、32ビットの入力を[[スクランブル]]して32ビットを出力する。ラウンド関数の内部を右図に示す。入力32ビットを8ビット単位にわけ、8ビット単位で隣の8ビットを用いてXORやS関数による変換を順番に行う構造になっている。この構造を開発者は「[[阿弥陀籤]]」からヒントを得たと述べており、"あみだ構造" と呼ばれることもある。

S関数は、8ビットCPUで容易に実装可能なように、法256での加算とビットシフトからなり、DESのようにテーブル参照をしなくてすむ分、コードサイズを小さく出来る。

鍵スケジューラでは、メインのデータスクランブルで使用されるラウンド関数を少し変形した関数を用いて、またFeistel構造とは異なる構造で、鍵64ビットを更新し、中間データを拡大鍵として出力する。

== 性能 ==
FEAL-32Xは、Z80(5MHz)で6169ステート(51.8kbps）で実行できる。
Pentium III(650MHz)では、117.8Mbps。

== 安全性 ==
FEAL-4は、[[線形解読法]]により、5つの[[既知平文]]で解読可能 (Matsui and Yamagishi, 1992)。

FEAL-NXは、[[差分解読法]]により、31ラウンドまで解読可能 (Biham and Shamir, 1991)。線形解読法では、25ラウンドまで解読可能。これはFEAL-32Xは<math>2^{99}</math>の計算量で解読可能であることを意味する。また、[[CRYPTREC]]の報告書では、FEAL-32X は学術的に解読可能であり、長期の使用を考えた場合、推薦できない。とされている．

<!--
== 歴史 ==
-->
<!-- InfoBoxは削除したいです
{{Infobox block cipher
| name          = FEAL
| image         = [[画像:FEAL InfoBox Diagram.png|300px|center]]
| caption       = FEAL Feistel 関数
| designers     = 清水明宏、宮口庄司 (NTT)
| publish date  = [[1987年]] (FEAL-4)、[[1990年]] (FEAL-N/NX)
| derived from  = 
| derived to    = 
| key size      = 64 ビット (FEAL), 128 ビット (FEAL-NX)
| block size    = 64 ビット
| structure     = [[Feistel構造]]
| rounds        = オリジナル版 4回、その後 8回を経て、可変長（32ラウンド以上が望ましい)
| cryptanalysis = 5つの[[既知平文]]を用いた[[線形暗号解読]]によりFEAL-4を解読可能 (Matsui and Yamagishi, 1992)。[[差分暗号解読]]により31ラウンド未満のFEAL-N/NXを解読可能 (Biham and Shamir, 1991)。
}}
-->

== 参考文献 ==
* Eli Biham, Adi Shamir: Differential Cryptanalysis of Feal and N-Hash. EUROCRYPT 1991: 1–16
* Bert den Boer, Cryptanalysis of F.E.A.L., EUROCRYPT 1988: 293–299
* Henri Gilbert, Guy Chassé: A Statistical Attack of the FEAL-8 Cryptosystem. CRYPTO 1990: 22–33.
* Shoji Miyaguchi: The FEAL Cipher Family. CRYPTO 1990: 627–638
* Shoji Miyaguchi: The FEAL-8 Cryptosystem and a Call for Attack. CRYPTO 1989: 624–627
* Mitsuru Matsui, Atsuhiro Yamagishi: A New Method for Known Plaintext Attack of FEAL Cipher. EUROCRYPT 1992: 81–91
* Sean Murphy, The Cryptanalysis of FEAL-4 with 20 Chosen Plaintexts. ''J. Cryptology'' '''2'''(3): 145–154 (1990)
* A. Shimizu and S. Miyaguchi, Fast data encipherment algorithm FEAL, Advances in Cryptology — Eurocrypt '87, Springer-Verlag (1988), 267–280.
* Anne Tardy-Corfdir, Henri Gilbert: A Known Plaintext Attack of FEAL-4 and FEAL-6. CRYPTO 1991: 172–181
* 清水明宏, 宮口庄司：高速データ暗号アルゴリズムFEAL. 電子情報通信学会論文誌, Vol. J70-D, No. 7, pp. 1413-1423, July 1987.

== 関連項目 ==
* [[ブロック暗号]]
* [[共通鍵暗号]]
* [[Feistel構造]]
* [[Camellia]]
* [[信頼性の低い暗号アルゴリズム]]

== 外部リンク ==
* [https://web.archive.org/web/20051211085725/http://info.isl.ntt.co.jp:80/crypt/archive/index.html The FEAL home page（アーカイブ）]
* [https://groups.google.com/g/sci.crypt/c/tPMalL9_Ufk/m/tGxOJOnrtVUJ A sci.crypt article by Peter Gutmann describing FEAL]
* [http://patft.uspto.gov/netacgi/nph-Parser?TERM1=4850019&u=/netahtml/srchnum.htm&Sect1=PTO1&Sect2=HITOFF&p=1&r=0&l=50&f=S&d=PALL US patent 4850019]

{{cryptography navbox|block}}