暗号アルゴリズム「FEAL-NX」
詳細評価（ＨＷ実装評価）レポート

２００１年１月１９日

1目次
１．アルゴリズム概要

３２．アルゴリズムFEAL‑NXの説明

３２．１

データランダマイズ部

３２．２

鍵スケジュール部

７３．評価方針

１０３．１

回路規模・性能の見積方法

１０３．２

設計上の留意点

１１

３．３

Synthesis（論理合成）条件

１１

４．各プリミティブの見積り

１３４．１

データランダマイズ部

１３４．２

鍵スケジュール部

１４５．ハードウェア評価結果

１５６．まとめ１７2

１．アルゴリズム概要
FEAL‑NXは、1988年にNTTより提案された秘密鍵暗号FEAL（the Fast Data EnciphermentAlgorithm）の１つのバージョンであり、ブロック長64ビットの暗号アルゴリズムである。
FEALはオプションとして、鍵の長さ、段数，鍵パリティの3つがある。鍵の長さは、6４ビットか、128ビットであり，段数Nは，データランダマイズ部の段数を指定し，鍵パリティ
オプションは，鍵ブロックにおけるパリティビットを使うか、使わないかを選択する。
FEAL‑NXは、FEALの鍵パリティビットなし、鍵サイズ128ビット、N回転限定版と位置付けられている。本報告では､FEALが差分解読法に対して、31段まで解読可能であることから､段数を32段として､FEAL‑NXの評価を行う。
２．アルゴリズムFEAL‑NXの説明
２．１ データランダマイズ部
図 1 は、FEAL‑NX のデータランダマイズ部を表している。一般的な Feistel 構造であり、暗号化と復号化は同一の構造によって処理可能である。
暗号化処理は、図 1 のように、入力 64 ビットを 64 ビットの拡大鍵と排他的論理和し、その結果を上位 32 ビットと下位 32 ビットに分割する。分割された上位 32 ビットと下位 32ビットの排他的論理和したものを、下位 32 ビットとする。これまでの処理が前処理と呼ばれる部分である。
次に、下位 32 ビットを段関数である F 関数で処理行ったものを上位 32 ビットと排他的論理和を行い、上位 32 ビットと下位 32 ビットをスワップさせる。この処理が 1 段の処理であり､32 段の FEAL‑NX の場合には､32 回繰り返し実行する。この部分の処理が反復計算と呼ばれる部分である。
最後に 32 段目の場合のみ、上位 32 ビットと下位 32 ビットのスワップを実行せずに、上位 32 ビットと下位 32 ビットを排他的論理和して下位 32 ビットとする。上位と下位を連接した 64 ビットに 64 ビットの拡大鍵と排他的論理和した結果を 64 ビットの出力データとする。この部分の処理が後処理と呼ばれる部分である。
図 2 は、反復計算の F 関数を表しており､32 ビット入力 32 ビット出力の関数である。また、段毎に異なる 16 ビットの拡大鍵が入力される。
F 関数の処理は､まず、入力された 32 ビットを 8 ビット毎４つに分割し、α0、α1、α2、α3 とする。α1 とα2 にそれぞれ 8 ビットの拡大鍵とα0 とα3 の 2 回の排他的論理和を行う。
その結果をα1 とする。
その排他的論理和されたα1 とα2 を入力とした S1 関数で処理を行い、次に、その処理されたα1 とα2 を入力とした S0 関数で処理を行い、その結果をα2 とする。

3

その次に、α0 とα1 を S0 関数で処理してα0、α2 とα3 を S1 関数で処理してα3 とする。この 8 ビット毎の処理結果α0、α1、α2、α3 を連接し 32 ビットとして、F 関数の出力データとする。この F 関数処理で用いられる S0 関数、S1 関数は、図 2 に示された式のように、256を法とした加算とローテーションシフトにより実現されている。
復号化処理に関しても、暗号化処理と同様の処理を実行することで実現可能である。ただし、各段において処理される F 関数に入力される拡大鍵の順番、前処理と後処理で処理される拡大鍵が逆になっていることに注意する必要がある。

4

図1．データランダマイズ部

5図2.F関数6

２．２ 鍵スケジュール部
FEAL-NXの鍵スケジュール部は、図3のような変形的ではあるがFeistel構造であり、暗号化と復号化は同一の構造によって処理可能である。
鍵スケジュール部は、図 3 のように 128 ビットの暗号化鍵 K を上位 64 ビットと下位 64ビットに分割する。下位 64 ビットを再び 32 ビット毎に分割して、KR1 と KR2 とする。また、KR1 と KR2 の排他的論理和したものを KR1＋KR2 と定義する。この KR1＋KR2 と KR1、KR2 を図 3 のように、順次 1 段目の QR、2 段目の QR、3 段目の QR、･･･のようにして、3段毎に鍵スケジュール処理に使用する。
最初に分割した上位 64 ビットは、32 ビット毎に分割し、上位 32 ビットと下位 32 ビッ
トに QR を排他的論理和したものを鍵スケジュール部用の段関数 Fk 関数に入力し処理する。
その結果を、上位 16 ビット、下位 16 ビットに分割して、拡大鍵（K0,K1）とする。Fk 関数の出力 32 ビットと下位 32 ビットをスワップし､鍵スケジュール部の 1 段の処理が完了する。
、拡大鍵（K4,K5）、･･･のように、FEAL-NX以降、1 段目の処理と同様にして､拡大鍵（K2,K3）
が 32 段の場合は､20 段の鍵スケジュール処理を実行する。
図 4 は、鍵スケジュール部の段関数 Fk 関数を表しており､64 ビット(32 ビット×2)入力32 ビット出力の関数である。
Fk 関数の処理は､まず、入力された 32 ビットαを 8 ビット毎４つに分割し、α0、α1、α、α3 とする。また、入力された 32 ビットβを 8 ビット毎４つに分割し、β0、β1、β2、2β3 とする。α0 とα1、α2 とα3 をそれぞれ排他的論理和し、α1、α2 とする。その排他的論理和されたα1 とα2 にβ0 を排他的論理和したものを入力とした S1 関数で処理を行い、その結果をα1 とする。次に、その処理されたα1 にβ1 を排他的論理和したものとα2 を入力とした S0 関数で処理を行い、その結果をα2 とする。その次に、α0 とα1 にβ2 を排他的論理和したものを S0 関数で処理してα0、α2 にβ3 を排他的論理和したものとα3 を S1 関数で処理してα3 とする。この 8 ビット毎の処理結果α0、α1、α2、α3 を連接し 32 ビットとして、Fk 関数の出力データとする。この Fk 関数処理で用いられる S0 関数、S1 関数は、データランダマイズ部で使用されている F 関数と同等の 256 を法とした加算とローテーションシフトにより実現されている。

7

図3．鍵スケジュール部

8図4．Fk関数

9３．評価方針
今回の 性 能評価 は、 SBOX、 乗 算器、 加算 器、ラ ウン ド関数 等と いった 基本 的な機 能 を 実 現 し て い る 個 々 の パ ー ツ (以 下 、 primitive)の 評 価 (回 路 規 模 、 処 理 速 度 等 )を実施することによりアルゴリズム全体の性能を見積る方法で評価を行い、また、個々の primitive においては、実際の LSI 作成に則した条件を付加して評価を行うことを前提に行った。なお、本報告で用いる評価環境は、我々が H/W 評価経 験のある三菱 0.35μm CMOS ASIC ライブラリを用い、回路記述には Verilog-HDL、Synthesis には Design Compiler を用い、回路規模(ゲート数)およびクリティカ ルパス長、処理速度等の性能見積を行った。
３.１

回路規模・ 性 能の見積 方 法

理想的と考えられる評価は、個々のアルゴリズムに対し、公平な評価指標のもとに、最大限の optimize（SBOX の小型化および最速化、および SBOX やラウンド関数のような複数回使用される回路の実装個数と繰り返し回数のトレードオフ等の検討）を試みて回路規模、性能を見積ることである。しかし、この評価方法では 、開発時間、開発資源（論理合成ツール等のソフトウェア、コンピュータ等のハードウェアおよび開発者等）が大量に必要となり、本詳細評価期間では、全てのアルゴリズムを公平な指標のもとに optimize することは困難である。そこで特定のアル ゴリズムだけを最適化することはせずに、アルゴリズムを全て実装（回路規模は大きくても構わない）し、クリティカルパス長の短縮（処理速度向上）を重視して評価を行った。
そこで今回の評価方法は、以下の通りに行った。
① 原則として、評価対象アルゴリズム全体(鍵スケジュールおよびすべての内部鍵レジスタを含む)をすべて H/W 実装することを前提とする。
② 入力鍵サイズは 128bit とし、性能評価時に、暗号化、復号部分と拡大鍵生成 部分の分離を容易にするため、拡大鍵は全てレジスタに格納する。
③ SBOX、乗算器、加算器、ラウンド関数等といった基本的な機能を実現している個々のパーツ(以下、primitive)の評価(回路規模、処理速度等)を実施する。
④ primitive の使用個数の総和を求め回路規模とする。
⑤ クリティ カ ルパス上 に 存在する primitive の 遅延値す べ ての総和 を 求めクリ ティカルパス長とする。

10

⑥ 「処理速度」を以下のように定義する。
Ｔｈｒｏｕｇｈｐｕｔ［Ｍｂｐｓ］＝ブロックサイズ（128［bit］）
暗号化（または復号）回路のクリティカルパス［ns］{}⑦ テーブル参照型 SBOX の実装は、論理合成ツール（Design Compiler）のみを用い optimize を行う。
⑧ 我々がハードウェア評価経験のあるツールを用いる。
・開発言語：Verilog-HDL
・シミュレータ：Verilog-XL
・デザインライブラリ：三菱 0.35μm CMOS ASIC ライブラリ・ 論理合成および性能評価：Design Compiler（version 1998.08）⑨ 評価するときの環境条件は、Worst ケースとする。
※注…Worst ケースとは、ハードウェアが動作する環境が劣悪、かつ、LSI 製造時のバラツキ度合いが悪い方の状態にあることを意味する。一般的に、ハードウェアの性能を議論するときには、議論の対象となっているハードウェアの動作を保証するという意味で、Worstケースで性能を論じることがほとんどである。よって、これ以降は、何も断りが無い場合は全て Worst ケースで議論を行う。
３.２

設計上の留 意 点

primitive の回路設計は、Verilog-HDL で記述し、設計する際の細かなブロック分けは、可能な限りアルゴリズム開発者のブロック分けに準じるように留意し 行った。
３.３

Synthesis（論理合成） 条 件

Synthesis(論理合成)ツールは Synopsys 社の Design Compiler(version 1998-08)を用い、すべてのアルゴリズムおよび primitive に同一の条件を付加した。こ の条
件は、速度を最大、かつ、実際の LSI 作成に則するようなものである。以下に条件を示す。
① 加算・減算・乗算回路は、Synopsys の Design Ware Basic Library 内にある最速なライブラリを用いる。
・ 32bit 加 算 器 は Synopsys の Design Ware Basic Library 内 に あ る
DW01_add(cla)[Carry look-ahead synthesis model]を用いる。
・ 32bit 減 算 器 は Synopsys の Design Ware Basic Library 内 に あ る

11

DW01_sub(cla)[Carry look-ahead synthesis model]を用いる。
・ 32bit 乗 算 器 は Synopsys の Design Ware Basic Library 内 に あ る
DW02_mult(csa)[Carry-save array synthesis model]を用いる。
② その他の条件は、基本的に default 値を用いる。ただし、fanout に関する条件は以下の理由で付加する。

○fanout 条件を全く付加しないことによる問題点
ある primitive の入力端子に fanout 条件が付けられていないとその入力端子は駆動能 力 が 「 ∞」 の ド ラ イバ よ り 駆 動さ れ て い るこ と に な り、 『 primitive レ ベ ルでの評価からアルゴリズム全体を試算し評価する結果』と『アルゴリズム全体のレベルでの評価する結果』でかなりの違いが出てきてしまう。
実際の LSI 設計では、各 primitive の負荷状況(fanout 等)やドライバの駆動能力
は 、 キ ャ ラ ク タ ラ イ ズ （ characterize） と い う 手 法 を 用 い 、 各 入 出 力 ピ ン の 負 荷 状
況を自動的に設定する方法、もしくは、各入出力端子に fanout 条件を付加する 方法等を用いて LSI を設計、作成している。そこで、今回は、アルゴリズム全てを実装せずに、primitive レベルから性能を見積る方法を行うため、characterize 手法は使用せず、以下のように入出力端子に fanout 設定を行う。
① primitive の入力ピンの fanin が１になるように条件をつける。
② primitive の出力から最大 40 個の primitive が並列に接続されても耐えうる よ
うに、primitive の出力ピンの fanout は 40 になるように条件をつける。

12

４．各 primitive の見積り
評価方法に従って評価を実行するために、FEAL-NX の構造を詳細にチェックし、各primitive の見積りを行った。ここでは､回路規模や速度に関しては考慮せずに、論理的にどのような構成のものがいくつあるかと言うことについて見積もりを行っている。
４．１ データランダマイズ部
表１にあるように、データランダマイズ部に関しては､F 関数が 32 個の 32 段構成となっている。その他には、最初と最後の部分の拡大鍵との 64 ビット排他的論理和（EXOR）が2 個、上位 32 ビットと下位 32 ビットの排他的論理和が 2 個、各段の F 関数からの出力と上位 32 ビットの排他的論理和が 32 個存在している。Feistel 構造であるため､復号化処理に関しても同等の構成で処理可能なため、回路規模の大幅な増加はない。
それぞれ、F 関数の内部には､8 ビットの排他的論理和が 4 個と S0 関数、S1 関数が 2 個ずつで構成されている。S0 関数は、8 ビット加算と 2 ビット左ローテートシフト、S1関数は、8 ビット加算が 2 個と 2 ビット左ローテートシフトで構成されている。
FEAL-NX のデータランダマイズ部の構成は､大半を排他的論理和と 8 ビットの加算で占めていることが判る。
表 1．データランダマイズ部の各 primitive の見積り

データランダマイズ部 Ｆ関数

F 関数

S0 関数
S1 関数

32 個 ※暗号化･復号とも同じ構成

32 ビット EXOR

34 個

64 ビット EXOR

2個

8 ビット EXOR

4個

S0 関数

2個

S1 関数

2個

8 ビット ADDR

1個

2 ビット LROT

1 個 ※2 ビット LROT：2 ビット左ローテートシフト

8 ビット ADDR

2個

2 ビット LROT

1 個 ※2 ビット LROT：2 ビット左ローテートシフト

13４．２ 鍵スケジュール部
表 2 にあるように、鍵スケジュール部に関しては､Fk 関数が 20 個の 20 段構成となっている。
その他には、32 ビット排他的論理和（EXOR）が 40 個存在している。
それぞれ、Fk 関数の内部には､8 ビットの排他的論理和が 6 個と S0 関数、S1 関数が 2 個ずつで構成されている。データランダマイズ部の F 関数と同様に、S0 関数は 8 ビット加算と 2 ビット左ローテートシフト、S1 関数は 8 ビット加算が 2 個と 2 ビット左ローテートシフトで構成されている。
FEAL-NX の鍵スケジュール部の構成は､大半を排他的論理和と 8 ビットの加算で占めていることが判る。
鍵スケジュール部の場合は､データランダマイズ部と同様に､暗号化処理と復号化処理において、共通の鍵スケジュール部を利用することが可能である。
表 2．鍵スケジュール部の各 primitive の見積り

鍵スケジュール部 Fk 関数

20 個 ※暗号化･復号とも同じ構成

32 ビット EXOR

FK 関数

S0 関数
S1 関数

40 個8 ビット EXOR

6個

S0 関数

2個

S1 関数

2個

8 ビット ADDR

1個

2 ビット LROT

1 個 ※2 ビット LROT：2 ビット左ローテートシフト

8 ビット ADDR

2個

2 ビット LROT

1 個 ※2 ビット LROT：2 ビット左ローテートシフト

14５．ハードウェア評価結果
各 primitive の見積もり結果をもとにして、評価方針通りに評価を行った。
表 3 は、データランダマイズ部の各 primitive の実装結果である。ここで、F 関数の実装に関しては､下位の primitive 毎に設計して積み上げる方式ではなく､実際に Verilog-HDLで記述し、論理合成を行った結果である。
また、F 関数の実装では､F 関数処理後に行う 32 ビット排他的論理和を含んだ構成となっている。Fk 関数の実装でも同様に、Fk 関数処理前に行う 2 回の 32 ビット排他的論理和を含んだ構成となっている。
表 3．データランダマイズ部の primitive 実装結果

回路規模[Gate]

クリティカルパス[ns]F 関数10236.94

2to1selector*32bit

2261.664 ビットレジスタ

5150.80

32bit EXOR

2671.08

表 4 は、鍵スケジュール部の各 primitive の実装結果である。ここで、Fk 関数の実装に関しては､下位の primitive 毎に設計して積み上げる方式ではなく､実際に Verilog-HDL で記述し、論理合成を行った結果である。
また、Fk 関数の実装では、Fk 関数処理前に行う 2 回の 32 ビット排他的論理和を含んだ構成となっている。
表 4．鍵スケジュール部の primitive 実装結果

回路規模[Gate]

クリティカルパス[ns]

Fk 関数

1259

7.3

2to1selector*32bit

2261.664 ビットレジスタ

5150.80

32bit EXOR

2671.0815

表 3、表 4 の primitive 実装結果をもとに、データランダマイズ部、鍵スケジュール部をアルゴリズムの構成を再現すると、表 5 のような結果となった。
表 5．データランダマイズ部、鍵スケジュール部の評価結果

回路規模[Gate]

クリティカルパス[ns]32 段 F 関数合計

32715

222.0832bit EXOR

1600

4.32

64 ビットレジスタ

5150.80

小計（演算部分）

34830

227.2020 段 Fk 関数合計

25174

146

暗／復号化鍵セレクタ

4520

1.6

64 ビットレジスタ

5147

0.80

小計（鍵生成部分）

34840

148.4

合計

69670

227.2

以上の実装結果および見積もりにより、FEAL-NX の H/W 詳細評価は、表 6 のような結果となった。なお、アルゴリズムの処理速度を見積もるため、本報告ではクリティカルパスに鍵スケジュールは含まれていないことに注意する。
表 6．FEAL-NX の H/W 詳細評価結果

回路規模[Gate] クリティカルパス[ns]69670

227.216

処理速度[Mbps]
281.69

６．まとめFEAL-NX については、5 章の評価結果のように、約 281Mbps の処置速度であることから、64 ビット暗号として Triple-DES と比較した場合、低速なアルゴリズムであると言える。これは、クリティカルパス上に並列実行のできない 8 ビット加算が大量に存在するためであると考えられる。回路規模に関しては、Triple-DES と比較した場合、約 70Kgateと小さいアルゴリズムである。実際の回路実装を考慮した場合、F 関数や Fk 関数等を全て実装することは無く、1 個実装し、ループして使用することが考えられ､その場合は、約5Kgate 前後の規模となることが予想される。従って、IC カードや携帯端末などの小型なデバイスを使用するアプリケーションにも実用可能なアルゴリズムであると考えられる。
−

17以上−