JP5338327B2 - 暗号処理装置 - Google Patents

Description

本発明は、暗号処理におけるＦＯ関数及びＦＬ関数の演算を行う暗号処理装置に関するものである。

セキュリティシステムの基盤技術として、様々な暗号方式が利用されている。暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵（公開鍵）を一般に公開する代わりに、暗号文を復号するための鍵（秘密鍵）を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵（秘密鍵）を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。

共通鍵方式の暗号（以下、共通鍵暗号と呼ぶ）は、公開鍵方式の暗号（以下、公開鍵暗号と呼ぶ）と比較した場合、処理速度が速くコンパクトに実装できるという利点がある。このため、携帯電話やＩＣカードなどの小型機器に暗号化機能を付加する場合には、共通鍵暗号が利用される。また、処理速度が高速であり、情報をリアルタイムで暗号化／復号化できるので、放送や通信分野における情報通信にも利用されている。

共通鍵暗号には、ストリーム暗号とブロック暗号がある。現時点では、安全性の観点から、共通鍵暗号にはブロック暗号が使用されている。ブロック暗号は、平文（暗号化の対象となる文）を一定のビット長のまとまり（これを、ブロックと呼ぶ）に分割し、ブロック単位で暗号化を行う。尚、暗号化の処理単位であるブロックのビット長は“ブロック長”と呼ばれる。

共通鍵暗号方式のブロック暗号は、ブロック長に応じて様々なアルゴリズムが知られている。代表的なものとしては、ＤＥＳ、ＡＥＳ、ＳＣ２０００、ＭＩＳＴＹ（ＭＩＳＴＹ１、ＭＩＳＴＹ２）、ＫＡＳＵＭＩ、ＣＡＭＥＬＬＩＡなどがある。これらの共通鍵暗号のアルゴリズムは、ソフトウェアもしくはハードウェアにより実装される。

ＫＡＳＵＭＩの仕様について以下に説明する。

共通鍵暗号のアルゴリズムの１つとして、ＫＡＳＵＭＩが知られている（例えば、非特許文献１）。ＫＡＳＵＭＩは、秘密鍵を１２８ｂｉｔとし、６４ｂｉｔを暗号化単位とするアルゴリズムである。すなわち６４ｂｉｔの平文から１２８ｂｉｔの秘密鍵を用いて６４ｂｉｔの暗号文を生成する。以下では、ＫＡＳＵＭＩのラウンド処理部について述べる。

図１６は、ＫＡＳＵＭＩの暗号化処理におけるラウンド処理部の構成の一例を示す回路図である。ＫＡＳＵＭＩのラウンド処理部は、ＦＯ関数とＦＬ関数から構成されるフェイステル構造を有している。ＫＡＳＵＭＩは８ラウンドのフェイステル構造から成っている。ＫＡＳＵＭＩの暗号化処理では、６４ｂｉｔの平文Ｐが入力され、フェイステル（Feistel）構造を経由することで暗号化が行われ、最終的に６４ｂｉｔの暗号文Ｃが出力される。この図中に示される、ＫＬ_i、ＫＯ_i、ＫＩ_iは１２８ｂｉｔ秘密鍵から生成される拡大鍵である。以下では、各関数の詳細について述べる。

図１７は、ＦＯ_i関数の構成の一例を示す回路図である。ここで、１≦ｉ≦８である。ＦＯ関数（ＦＯ_i関数）の入力３２ｂｉｔは、１６ｂｉｔ毎の２つのデータに分割され、排他的論理和とＦＩ関数によって変換が行われる。ＫＯ_ij（１≦ｊ≦３）とＫＩ_ij（１≦ｊ≦３）は、それぞれ拡大鍵ＫＯ_iとＫＩ_iの左からｊ番目の１６ｂｉｔデータを使用する。

図１８は、ＦＩ_ij関数の構成の一例を示す回路図である。ここで、１≦ｉ≦８、１≦ｊ≦３である。ＦＩ関数（ＦＩ_ij関数）の入力１６ｂｉｔは、左９ｂｉｔと右７ｂｉｔのデータに分割され、排他的論理和と２つの非線形関数（Ｓ９とＳ７）によって変換が行われる。図中のｚｅｒｏ−ｅｘｔｅｎｄｅｄは、７ｂｉｔデータの上位２ｂｉｔにゼロを付加して９ｂｉｔデータとする変換を意味する。ｔｒｕｎｃａｔｅｄは、９ｂｉｔデータの上位２ｂｉｔを切り捨てて７ｂｉｔデータとする変換を意味する。拡大鍵ＫＩ_ijの左７ｂｉｔデータをＫＩ_ij1とし、右９ｂｉｔデータをＫＩ_ij2とする。

図１９は、ＦＬ_i関数の構成の一例を示す回路図である。ここで、１≦ｉ≦８である。ＦＬ関数（ＦＬ_i関数）の入力３２ｂｉｔは、１６ｂｉｔ毎の２つのデータに分割され、排他的論理和と論理積、論理和によって変換が行われる。ＫＬ_ij（１≦ｉ≦８、１≦ｊ≦２）は、拡大鍵ＫＬ_iの左からｊ番目の１６ｂｉｔデータを使用する。

従来例のＫＡＳＵＭＩのラウンド処理部の小型実装について以下に説明する。

図２０は、従来例のＦＩ関数の小型実装の一例を示す回路図である。この図において、左側は、ＦＯ関数を実現する回路の一例を示し、右側は、ＦＩ関数を実現する回路の一例を示す。この従来例では、ＦＩ関数を２サイクルかけて実現する。つまり、この図の右側に示すように、ＦＩ関数の上部半分のみであるＦＩ１／２モジュールを実装し、１サイクル目の中間結果を１６ｂｉｔレジスタに格納する。２サイクル目では、この中間レジスタの値をＦＩ１／２モジュールへの入力とし、合計２サイクルかけて処理することで、ＦＩ関数の機能を実現する。

ＦＩ関数は、Ｓ７、Ｓ９と呼ばれる、それぞれ７ｂｉｔ−７ｂｉｔ非線形変換、９ｂｉｔ−９ｂｉｔ非線形変換を実行する、比較的回路規模が大きい部品を含むことが知られている。ＦＩ１／２モジュールを用いることで、ＦＩ関数を１個すべて実装するよりも、回路規模が小さくなる利点がある。

また、ＦＯ関数についても同様に、１つのＦＩ関数をベースに実装する。上述したとおり、ＦＯ関数は３つのＦＩ関数から構成される。また、上述のＦＩ関数の小型実装の従来例に示すように、ＦＯ関数におけるＦＩ関数を１段分だけ実装する。ＦＯ関数のビット幅は３２ｂｉｔであるので、中間結果を３２ｂｉｔレジスタに格納し、次のサイクルでこの中間レジスタの値を入力とする処理を繰り返すことでＦＯ関数の機能を実現する。

このように複数サイクルをかけて処理することで、ＦＩ関数を複数個実装する必要がなくなり、回路規模が小さくなる利点がある。実際には、ＦＩ関数の１段分は、上述の通りＦＩ１／２モジュールを用いて２サイクルかけて処理を行う。つまり、ＦＩ関数を２サイクルで実行するので、ＦＯ関数を実行するのに必要なサイクル数は、２サイクル×３段＝６サイクルとなる。

以上より、ＫＡＳＵＭＩのラウンド処理部の小型実装の従来例では、ＦＩ関数用の中間レジスタ（ＦＩｒｅｇ）が１６ｂｉｔ、さらにＦＯ関数用の中間レジスタ（ＦＯｒｅｇ）が３２ｂｉｔ必要であり、合計４８ｂｉｔの中間レジスタが必要である。

図２１は、従来例のＫＡＳＵＭＩのラウンド処理部の構成の一例を示す回路図である。図中のＲ_H、Ｒ_L、Ｌ_H、Ｌ_Lは、暗号文の途中結果を格納するためのデータレジスタとなっており、それぞれを１６ｂｉｔレジスタとすると、合計６４ｂｉｔである。

このラウンド処理部は、制御部３１、ＦＬ関数１２、ＦＩ１／２モジュール１３、データレジスタ１４ａ，１４ｂ、中間レジスタ３５ａ，３５ｂ、ＸＯＲゲート３６ａ，３６ｂ、セレクタ３７ｂ，３７ｃ，３７ｆ，３７ｇ，３７ｈ，３７ｉ，３７ｊを有する。データレジスタ１４ａは、３２ｂｉｔであり、上位１６ｂｉｔがＲ_Hに対応し、下位１６ｂｉｔがＲ_Lに対応する。データレジスタ１４ｂは、３２ｂｉｔであり、上位１６ｂｉｔがＬ_Hに対応し、下位１６ｂｉｔがＬ_Lに対応する。中間レジスタ３５ａは、１６ｂｉｔであり、ＦＩｒｅｇに対応する。中間レジスタ３５ｂは、３２ｂｉｔであり、ＦＯｒｅｇに対応する。制御部３１は、セレクタ３７ｂ，３７ｃ，３７ｆ，３７ｇ，３７ｈ，３７ｉ，３７ｊを制御する。

"Specification of the 3GPP Confidentiality and Integrity Algorithms; Document 2: KASUMI Specification," ｈｔｔｐ：／／ｗｗｗ．３ｇｐｐ．ｏｒｇ／ｆｔｐ／Ｓｐｅｃｓ／ａｒｃｈｉｖｅ／３５＿ｓｅｒｉｅｓ／３５．２０２／３５２０２−７００．ｚｉｐ

上述した従来例のラウンド処理部は、ＦＩ関数用の１６ｂｉｔの中間レジスタとＦＯ関数用の３２ｂｉｔの中間レジスタとの合計４８ｂｉｔの中間レジスタが必要である。一般に、他の素子と比較して、レジスタの回路規模は大きくなる傾向にある。そのため、小型回路を実現する上で、４８ｂｉｔ分ものレジスタを必要とすることは、回路規模の増大を引き起こしてしまうという問題点がある。

本発明は上述した問題点を解決するためになされたものであり、ＦＯ関数及びＦＬ関数の演算において、ＦＯ関数の演算結果を格納する中間レジスタを不要にする暗号処理装置を提供することを目的とする。

上述した課題を解決するため、本発明の一態様は、暗号処理におけるＦＯ関数及びＦＬ関数の演算を行う暗号処理装置であって、２Ｎビットの入力と第１拡大鍵とに基づいてＦＬ関数の演算を行って２Ｎビットの出力を生成するＦＬ関数演算部と、Ｎビットの入力と第２拡大鍵と第３拡大鍵とに基づいてＦＩ関数の部分関数の演算を行ってＮビットの出力を生成する部分関数演算部と、部分演算部の出力を記憶するＮビットの中間レジスタと、ＦＬ関数演算部の出力に基づくデータを記憶することができる２Ｎビットの第１データレジスタと、ＦＬ関数がＦＯ関数の演算結果を用いる第１ケースにおいて、部分関数演算部に部分関数の演算を６サイクル行わせ、中間レジスタの出力をＦＬ関数演算部へ入力し、ＦＬ関数演算部の出力に基づくデータを第１データレジスタへ記憶させる制御部とを有する。

開示の暗号処理装置によれば、ＦＯ関数及びＦＩ関数の演算において、ＦＯ関数の演算結果を格納する中間レジスタを不要にすることができる。

中間レジスタのサイズが４８ｂｉｔであるラウンド処理部の処理の一例を示す図である。 中間レジスタのサイズが１６ｂｉｔであるラウンド処理部の処理の一例を示す図である。 ＦＯ−ＦＬ関数におけるＦＯ関数の構成及び演算論理内容を示す図である。 ＦＯ−ＦＬ関数におけるＦＬ関数の構成及び演算論理内容を示す図である。 ＦＯ関数用レジスタが３２ｂｉｔであり且つＦＩ関数用レジスタが１６ｂｉｔである場合のＦＯ−ＦＬ関数におけるＦＯ関数の構成の一例を示す図である。 ＦＯ関数用レジスタが３２ｂｉｔであり且つＦＩ関数用レジスタが１６ｂｉｔである場合のＦＯ−ＦＬ関数におけるＦＬ関数の構成の一例を示す図である。 ＦＯ関数の直下にＦＬ関数が無いと仮定した場合において、ＦＯ関数レジスタが無く且つＦＩ関数レジスタが１６ｂｉｔである場合の処理アルゴリズムを示す図である。 ＦＬ関数における部分関数ｆ（ａ）とｇ（ａ）の構成を示す回路図である。 ＦＬ関数全体の線形性の分析を示す回路図である。 実施例１のラウンド処理部における奇数ラウンドの処理アルゴリズムの一例を示す図である。 実施例１のラウンド処理部における偶数ラウンドの処理アルゴリズムの一例を示す図である。 実施例１のラウンド処理部の構成の一例を示す回路図である。 実施例２のラウンド処理部における偶数ラウンドの処理アルゴリズムの一例を示す図である。 実施例２のラウンド処理部の構成の一例を示す回路図である。 中間レジスタのサイズ及びラウンド処理部の回路規模を示す図である。 ＫＡＳＵＭＩの暗号化処理におけるラウンド処理部の構成の一例を示す回路図である。 ＦＯ_i関数の構成の一例を示す回路図である。 ＦＩ_ij関数の構成の一例を示す回路図である。 ＦＬ_i関数の構成の一例を示す回路図である。 従来例のＦＩ関数の小型実装の一例を示す回路図である。 従来例のＫＡＳＵＭＩのラウンド処理部の構成の一例を示す回路図である。

以下、本発明の実施の形態について図面を参照しつつ説明する。

以下の各実施の形態は、ＫＡＳＵＭＩのラウンド処理部の小型実装において、中間レジスタのサイズを１６ｂｉｔに削減する。つまり、ＦＯ関数用の中間レジスタ１６ｂｉｔとＦＩ関数用の中間レジスタ１６ｂｉｔを共用化し、全体で１６ｂｉｔの中間レジスタ１つを用いて、ＫＡＳＵＭＩのラウンド処理部を実装する。

しかし、これを実現するためには、以下で述べる課題が発生する。

ＫＡＳＵＭＩにおけるＦＬ関数は線形関数ではない。そのため、中間レジスタを１６ｂｉｔにすることで、ＫＡＳＵＭＩのラウンド処理部の偶数ラウンド、つまりＦＯ関数→ＦＬ関数という構造になっている部分において、論理の等価性を保てなくなる問題が生じる。従来例のように、中間レジスタのサイズが４８ｂｉｔの場合は問題が生じないが、１６ｂｉｔの場合には問題が生じることを以下で説明する。

図１は、中間レジスタのサイズが４８ｂｉｔであるラウンド処理部の処理の一例を示す図である。前述の通り、ＫＡＳＵＭＩのラウンド処理部の小型実装の従来例では、６サイクルかけてＦＯ関数の機能を実現する。その中間結果は４８ｂｉｔの中間データに保持される。そして、６サイクル後に中間レジスタに格納されているデータを、ＦＬ関数へとまとめて入力する。したがって、ＦＬ関数を経由するデータは１個であるので、問題なく実装できる。

図２は、中間レジスタのサイズが１６ｂｉｔであるラウンド処理部の処理の一例を示す図である。中間レジスタが１６ｂｉｔの場合、ＦＯ関数で６サイクルかけて処理する演算結果をすべて中間レジスタに格納せずに、一部はそのままＦＬ関数へとダイレクトに（ＦＯ関数から出力されるサイクルと同一のサイクルで）入力する。つまり、中間レジスタが４８ｂｉｔの場合は、ＦＯ関数の出力をまとめて１回だけＦＬ関数へと入力したが、中間レジスタが１６ｂｉｔの場合には、複数回に分けてＦＬ関数へと入力（逐一入力）することになる。

ここで、ＫＡＳＵＭＩにおけるＦＬ関数は、線形関数ではないため、次式（Ｅ−１）の性質が成立しない問題がある。

つまり、ＦＬ関数には線形性がないために、中間レジスタが１６ｂｉｔの場合には、論理の等価性が保持されないという問題が生じる。

ＦＯ−ＦＬ関数の演算処理について以下に説明する。

図３は、ＦＯ−ＦＬ関数におけるＦＯ関数の構成及び演算論理内容を示す図である。図４は、ＦＯ−ＦＬ関数におけるＦＬ関数の構成及び演算論理内容を示す図である。ここでは、ＦＯ関数処理後にＦＬ関数処理を行うラウンドにおける、論理的な演算内容を示す。

３２ｂｉｔデータレジスタＲ_H｜｜Ｒ_L（ただしＲ_H、Ｒ_Lはそれぞれ１６ｂｉｔ）を入力とし、ＦＯ関数、ＦＬ関数処理を行い、演算結果を別の３２ｂｉｔデータレジスタＬ_H、Ｌ_L（ただしＬ_H、Ｌ_Lはそれぞれ１６ｂｉｔ）に対してＸＯＲ演算する。ここで、演算子“Ｘ｜｜Ｙ”は、Ｘを上位ビット列とし、Ｙを下位ビット列とする結合を示す。ここで、（Ｒ_H,1｜｜Ｒ_L,1）、（Ｒ_H,2｜｜Ｒ_L,2）、（Ｒ_H,3｜｜Ｒ_L,3）をそれぞれＦＯ関数の１段目、２段目、３段目に対する入力データ（ただしＲ_H,1、Ｒ_L,1、Ｒ_H,2、Ｒ_L,2、Ｒ_H,3、Ｒ_L,3はそれぞれ１６ｂｉｔ）と表記する。Ｒ_H、Ｒ_Lに対するＬ_H、Ｌ_Lの演算結果は、次式（Ａ−１）に示される。

上述のＦＯ−ＦＬ関数の演算処理の実装において、ＦＯ関数レジスタが３２ｂｉｔであり且つＦＩ関数レジスタが１６ｂｉｔである場合について以下に説明する。

図５は、ＦＯ関数用レジスタが３２ｂｉｔであり且つＦＩ関数用レジスタが１６ｂｉｔである場合のＦＯ−ＦＬ関数におけるＦＯ関数の構成の一例を示す図である。図６は、ＦＯ関数用レジスタが３２ｂｉｔであり且つＦＩ関数用レジスタが１６ｂｉｔである場合のＦＯ−ＦＬ関数におけるＦＬ関数の構成の一例を示す図である。ここでは、（Ａ−１）に示した演算を、ＦＯ関数用レジスタ３２ｂｉｔ（ＦＯｒｅｇ）、ＦＩ関数用レジスタ１６ｂｉｔ（ＦＩｒｅｇ）で実装する場合の処理を示す。ＦＬ関数に入力する３２ｂｉｔ値を、ＦＯｒｅｇに対してバッファリング処理を行ってから、この３２ｂｉｔのＦＯｒｅｇに対してＦＬ関数処理を最後に実行し、データレジスタＬ_H、Ｌ_Lに対するＸＯＲｉｎｇ処理を行う。この処理によるＦＯｒｅｇの演算結果は、次式（Ａ−２）のようになる。

Ｌ_H、Ｌ_Lの演算結果は、次式（Ａ−３）のようになる。

上述のＦＯ−ＦＬ関数の演算処理の実装において、ＦＯ関数レジスタが無く且つＦＩ関数レジスタが１６ｂｉｔである場合について以下に説明する。

（Ａ−１）に示した演算を、ＦＯ関数用レジスタが無く且つＦＩ関数用レジスタが１６ｂｉｔ（ＦＩｒｅｇ）である実装する場合、ＦＯ関数用レジスタが３２ｂｉｔであり且つＦＩ関数用レジスタ１６ｂｉｔである場合と異なり、３２ｂｉｔバッファリングを行うＦＯｒｅｇがない。よって、ＦＬ関数の入力となる３２ｂｉｔ値である次式（Ａ−４）の値を、部分的に計算しながら、Ｌ_H、Ｌ_LにＸＯＲｉｎｇすることとなる。

ＦＯ関数の後にＦＬ関数処理が無いと仮定した場合について説明する。この場合の演算論理内容は、次式（Ａ−５）に示される。

この場合、すなわち（Ａ−５）のような処理の場合は、（Ａ−４）の値を部分的に計算しながらＬ_H、Ｌ_LにＸＯＲｉｎｇ処理を行うことは次に示す処理アルゴリズムにより実現できる。図７は、ＦＯ関数の直下にＦＬ関数が無いと仮定した場合において、ＦＯ関数レジスタが無く且つＦＩ関数レジスタが１６ｂｉｔである場合の処理アルゴリズムを示す図である。この図は、演算論理内容（Ａ−５）の処理アルゴリズムを示す。この処理アルゴリズムは、次の関係式（Ｅ−２）を利用している。

この処理アルゴリズムは、（Ａ−４）に示されている数式を構成する部分的な演算データである、（Ｒ_L｜｜Ｒ_L）、ＦＩ（Ｒ_H,2，ＫＯ_i,2，ＫＩ_i,2）｜｜ＦＩ（Ｒ_H,2，ＫＯ_i,2，ＫＩ_i,2）、ＦＩ（Ｒ_H,1，ＫＯ_i,1，ＫＩ_i,1）｜｜ＦＩ（Ｒ_H,1，ＫＯ_i,1，ＫＩ_i,1）、０｜｜ＦＩ（Ｒ_H,3，ＫＯ_i,3，ＫＩ_i,3）を、この順番で計算しながら、部分的な演算データの計算が終了するごとに、Ｌ_H｜｜Ｌ_LにＸＯＲｉｎｇすることで、ＦＯｒｅｇを用いたバッファリングの必要がない処理を実現する。

この部分演算は、（Ａ−５）に示したＸＯＲｉｎｇ演算が、次の（Ａ−６）と等価な演算で実現できる、という性質を利用しており、（Ａ−６）に示したｔｍｐ１、ｔｍｐ２、ｔｍｐ３、ｔｍｐ４の計算を複数サイクルに分けて演算の上、演算しだいＬ_H｜｜Ｌ_LにＸＯＲｉｎｇする手法を用いることで、これらのデータ値をバッファリングする必要が無いため、ＦＯｒｅｇの削減が可能となる。

同様のテクニックを上述のＦＬ関数有り（ＦＯ−ＦＬ関数においてＦＯ関数用レジスタが３２ｂｉｔでＦＩ関数用レジスタが１６ｂｉｔである場合の実装の例）の処理に単純に適用することはできない。次式（Ａ−６）をＦＬ関数有りの処理に置き換える場合、次式（Ａ−７）の計算が必要となる。

しかし、（Ａ−７）で記したｔｍｐ１、ｔｍｐ２、ｔｍｐ３、ｔｍｐ４のそれぞれのデータはＦＯｒｅｇがないためバッファリングすることができないため、次式（Ｅ−３）で表記されるデータ値を保存することができない。

すなわち、ｔｍｐ１、ｔｍｐ２、ｔｍｐ３、ｔｍｐ４に記されるデータを計算したサイクルと同じサイクルで、ＦＬ関数の処理結果であるＦＬ（ｔｍｐ１）、ＦＬ（ｔｍｐ２）、ＦＬ（ｔｍｐ３）、ＦＬ（ｔｍｐ４）を計算し、Ｒ_H｜｜Ｒ_LにＸＯＲｉｎｇしなければならない。この処理は、次式（Ａ−８）で表現することができる。

ただし、（Ａ−７）の演算に対して、（Ａ−８）の演算は、論理等価性において問題がある。なぜなら、（Ａ−８）の結果が（Ａ−７）と同一となるためには、次式（Ａ−９）の性質が成り立っていなければならない。

これは一般的には線形性と呼ばれる性質であり、任意の整数Ｘ、Ｙに対して次式（Ａ−１０）がＦＬ関数について成立していなければならない。

しかし、（Ａ−９）及び（Ａ−１０）の性質は、共に、ＦＬ関数に対して成立しないことが知られているため、（Ａ−８）の演算は成立しない。

よって、ＦＬ関数について従来知られた性質のみを用いた場合、ＦＩ関数用１６ｂｉｔレジスタ、ＦＯ関数用レジスタ無し、という構成では、論理等価性を保つことができない、という問題がある。

ＦＬ関数は、（Ａ−１０）で表される完全な線形性を持たないが、分析により、次式（Ａ−１１）中の補正定数（ＫＬ_i,2＜＜＜１｜｜０）を用いることで、（Ａ−１１）で表される部分的な線形性を有することが判明した。

（Ａ−１１）の性質から、次式（Ａ−１２）のように、３変数については線形性を有する。

（Ａ−１１）、（Ａ−１２）の性質をさらに一般化すると、ＦＬ（Ｘ）に関して、ｎが奇数の場合、次式（Ｂ−１）が成立し、

ｎが偶数の場合、次式（Ｂ−２）が成立する。

ただし、ＦＬ関数への入力をＸ_k（ｋ＝１，２，．．．，ｎ）とした場合、ＦＬ関数からの出力をＦＬ（Ｘ_k）で表す。

つまり、中間レジスタからＦＬ関数へと入力する回数が偶数回の場合には、補正ビット列（（ＫＬ_i,2＜＜＜１）｜｜０）をＸＯＲするという補正操作を行うことによって、論理の等価性を保つことが可能となる。ここでの０は、１６ｂｉｔの長さを有する。これにより、ＦＯ関数からの出力を、複数サイクルにわたって分割して、ＦＬ関数に入力することが可能となり、中間レジスタのサイズを１６ｂｉｔとすることができる。

以下で、この等式が成立する根拠について詳細に述べる。

ＫＡＳＵＭＩのＦＬ関数の構造について説明する。図８は、ＦＬ関数における部分関数ｆ（ａ）とｇ（ａ）の構成を示す回路図である。ＫＡＳＵＭＩのＦＬ関数において、この図に示すように、２つの部分関数ｆ（ａ）とｇ（ａ）を定義する。ここで、ａは部分関数への入力である。ここで、演算ゲートの記号“∧”または演算子“∩”は、論理積を表し、演算ゲートの記号“∨”または演算子“∪”は、論理和を表す。演算ゲートの記号及び演算子である“＜＜＜”は、左ローテートを表す。ＦＬ関数における部分関数ｆ（ａ）とｇ（ａ）は、次式（Ｂ−３）で表される。

また、

を考慮すると、上式（Ｂ−３）は、ＡＮＤ−ＸＯＲ形式を用いて、ｆ（ａ）とｇ（ａ）は、次式（Ｂ−５）で表すことができる。

この性質を踏まえると、ｆ（），ｇ（）及び任意整数ｘ，ｙ，ｚに対して、以下が成り立つ。

Ｌｅｍｍａ１．（２変数ｘ、ｙのほか、任意の偶数個の変数で成立）

Ｌｅｍｍａ２．（３変数ｘ、ｙ、ｚのほか、任意の奇数個の変数で成立）

ｆ（）に関するＬｅｍｍａ１、Ｌｅｍｍａ２の証明を以下に示す。

よって、

が成立する。

なお、

の２変数による関係が成立する時点で、任意個数についても同様の関係が成立する。なぜなら、３変数への拡張は、

より導出でき、以下変数の同様の増加を繰り返すことができるからである。

ｇ（）に関するＬｅｍｍａ１、Ｌｅｍｍａ２の証明を以下に示す。

よって、

変数が偶数個の場合は、（ＫＬ_i,2＜＜＜１）が補正定数として必要であり、奇数の場合は不要となる。

ＦＬ関数全体の線形性の分析について以下に説明する。

図９は、ＦＬ関数全体の線形性の分析を示す回路図である。この回路の構成は、図８と同様である。ＦＬ関数をＦＬ（）と表記する。このとき、Ｘ＝（Ｘ_L｜｜Ｘ_R）、Ｏ＝（Ｏ_L｜｜Ｏ_R）を用いて、ＦＬ関数の入出力をＯ＝ＦＬ（Ｘ）と表記する。ただし、Ｘ、Ｏは３２ｂｉｔ、Ｘ_L、Ｘ_R、Ｏ_L、Ｏ_Rはそれぞれ１６ｂｉｔであるものとする。そのとき、ＯをＸの関数で表記すると、次式（Ｃ−１）のようになる。

ｆ（）の完全な線形性を考慮すると、Ｏ_Rに関して線形性が成立するのは明らかである。残りはＯ_Lであるが、ｇ（）が奇数個の変数に関して線形性を有していることを考えると、変数が奇数個に限りＦＬは線形関数である。すなわち、次式（Ｃ−２）が、ｎが奇数の場合に限って成立する。

ｎが偶数の場合は、次式（Ｃ−３）が成立する。

なぜなら、

に対して、

であるためである。（Ｑ_Rは明らかに線形であるので、省略する。）

すなわちＱ_L、つまり出力の左１６ｂｉｔのみ、定数（ＫＬ_i,2＜＜＜１）による補正を用いた線形性が成立し、Ｑ_Rは常に線形性が成立するので、ｎが偶数の場合、

が成立する。最終的に、上述の（Ｂ−１）及び（Ｂ−２）の性質を得る。

以下、ＫＡＳＵＭＩのラウンド処理部について、中間レジスタＦＩｒｅｇのサイズが１６ｂｉｔのみでハードウェア実装可能な処理アルゴリズム、及びハードウェアの実施例について述べる。

（実施例１）
図１０は、実施例１のラウンド処理部における奇数ラウンドの処理アルゴリズムの一例を示す図である。奇数ラウンド（第２ケース）の処理は、ＦＬ関数、ＦＯ関数の順番で行われる。

ＦＩｒｅｇは１６ｂｉｔ中間レジスタを表す。ＦＩ関数は２サイクルかけて処理する。ＦＩ’_i,j（）は、１サイクル目の中間結果を示す。ＦＩｓｉｇは信号線を示す。「ＦＩｒｅｇ＜＝」はＦＩｒｅｇに右辺の値が代入されるのが次サイクルであることを示している（ノンブロッキング代入）。「ＦＩｓｉｇ＝」は、そのサイクルで信号線に右辺の値が代入されることを示している（ブロッキング代入）。

１サイクル目、３サイクル目、４サイクル目では、ＦＬ関数からの出力を同一サイクルで用いている。

図１１は、実施例１のラウンド処理部における偶数ラウンドの処理アルゴリズムの一例を示す図である。偶数ラウンド（第１ケース）の処理は、ＦＯ関数、ＦＬ関数の順番で行われる。

なお、本実施例は、ＦＬ関数へと入力する回数が奇数回（３回）であるので、補正操作は行う必要が無い。ＦＬ関数への入力は、３サイクル目、５サイクル目、７サイクル目に実行される。

奇数ラウンドでは、２、４、６サイクル目でデータレジスタにＸＯＲ処理を行っていた。それに対し、偶数ラウンドでは、３、５、７サイクル目でＸＯＲ処理を行う。つまり、１サイクルだけ遅らせて処理する制御を行っている。これは、奇数ラウンドにおいて、ＦＬ関数からＦＯ関数へと同一サイクルで信号を接続していたため、偶数ラウンドではＦＯ関数からＦＬ関数へのデータパスにレジスタを挿入するためである。

このように、ＦＯ関数からＦＬ関数へのデータパスにレジスタを挿入する制御を行うことで、実装するＦＬ関数（ＦＬ１／２モジュール）の個数が１つだけですむため、回路規模が削減できる。もし、このように１サイクルだけ遅らせずに、奇数ラウンドと同様のタイミングで偶数ラウンドにおいても処理を行った場合、ＦＬ関数を２個実装する必要があり、回路規模が増大してしまう。仮にＦＬ関数を１個で実装した場合、組み合わせ回路のフィードバック構造が形成されてしまい、信頼性という面で製品化困難なハードウェアとなってしまう。

図１２は、実施例１のラウンド処理部の構成の一例を示す回路図である。このラウンド処理部は、制御部１１、ＦＬ関数１２（ＦＬ関数演算部）、ＦＩ１／２モジュール１３（部分関数演算部）、データレジスタ１４ａ，１４ｂ、中間レジスタ１５、ＸＯＲゲート１６ａ，１６ｂ、セレクタ１７ａ，１７ｂ，１７ｃ，１７ｄ，１７ｅ，１７ｆ，１７ｇを有する。データレジスタ１４ａは、３２ｂｉｔであり、上位１６ｂｉｔがＲ_Hに対応し、下位１６ｂｉｔがＲ_Lに対応する。データレジスタ１４ｂは、３２ｂｉｔであり、上位１６ｂｉｔがＬ_Hに対応し、下位１６ｂｉｔがＬ_Lに対応する。中間レジスタ１５は、１６ｂｉｔであり、ＦＩｒｅｇに対応する。制御部１１は、上述の本実施例の処理アルゴリズムに従って、セレクタ１７ａ，１７ｂ，１７ｃ，１７ｄ，１７ｅ，１７ｆ，１７ｇを制御する。“１６’ｈ００００”は、１６ｂｉｔの０を示す。

本実施例によれば、従来例のラウンド処理部におけるＦＯ関数用３２ｂｉｔ中間レジスタを不要にすることができる。

（実施例２）
本実施例のＫＡＳＵＭＩのラウンド処理部において、奇数ラウンドの処理アルゴリズムは、実施例１と同様である。

図１３は、実施例２のラウンド処理部における偶数ラウンドの処理アルゴリズムの一例を示す図である。本実施例は、ＦＬ関数へと入力する回数が偶数回（４回）であるので、補正操作を４サイクル目に行っている。ＦＬ関数への入力は、３サイクル目、５サイクル目、６サイクル目、７サイクル目に実行される。本実施例では、補正操作を４サイクル目に行っている。また、６サイクル目に、ＦＯ関数への入力Ｒ_LをＦＬ関数への入力として、データレジスタ｛Ｌ_H｜｜Ｌ_L｝にＸＯＲ処理を行っている。この２つの処理に関しては、１、２、４、６、サイクル目のいずれで実行されてもよい。つまり、データレジスタへのＸＯＲ処理が行われる３、５、７サイクル目以外であれば、いつ実行されてもよい。

図１４は、実施例２のラウンド処理部の構成の一例を示す回路図である。この図において、図１２と同一符号は図１２に示された対象と同一又は相当物を示しており、ここでの説明を省略する。実施例１と比較すると、本実施例のラウンド処理部は、制御部１１の代わりに制御部２１を有し、セレクタ１７ｃ，１７ｄ，１７ｆ，１７ｇの代わりにセレクタ２７ｃ，２７ｆ，２７ｇを有し、新たにＸＯＲゲート２６ｃ及び補正操作部２８を有する。制御部２１は、上述の本実施例の処理アルゴリズムに従って、セレクタ１７ａ，１７ｂ，２７ｃ，１７ｅ，２７ｆ，２７ｇを制御する。

従来例の回路と比較すると、本実施例の回路は、中間レジスタのサイズが１６ｂｉｔのみである。この実装が可能となっている理由は、（Ｂ−２）における補正操作に対応する補正操作部２８が加えられていることによる。

実施例の効果について以下に説明する。

図１５は、中間レジスタのサイズ及びラウンド処理部の回路規模を示す図である。この図は、従来例と実施例２について、全ての中間レジスタのサイズと、中間レジスタの回路規模とを示す。

従来例と比較すると、実施例２は、中間レジスタのサイズを４８ｂｉｔから１６ｂｉｔへ削減できる。中間レジスタの回路規模は約６７％削減されることになる。

極めて小型のＫＡＳＵＭＩハードウェア（０．１３ｕｍプロセスで約３４００ｇａｔｅ）の回路規模を考慮すると、従来例のラウンド処理部を用いたＫＡＳＵＭＩハードウェアの回路規模は、約３６５０ｇａｔｅと見積もることができる。したがって、この従来例に基づくハードウェアに実施例２を適用すると約１２％の回路規模削減効果が期待できる。

従来例のラウンド処理部を用いたＫＡＳＵＭＩハードウェアにおいて、１回の暗号化／復号に必要なサイクル数は、５６サイクルとなる。一方、実施例２のラウンド処理部を用いたＫＡＳＵＭＩハードウェアにおいて、１回の暗号化／復号に必要なサイクル数は、５２サイクルとなる。したがって、動作周波数が同じであるという前提であれば、従来例と比べて実施例２は、約７％の高速化となる。

上述の各実施の形態において、Ｎは１６である。第１拡大鍵、第２拡大鍵、第３拡大鍵は、それぞれＫＬ_i、ＫＯ_i、ＫＩ_iに対応する。

本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。そのため、前述の実施の形態は、あらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には、何ら拘束されない。更に、特許請求の範囲の均等範囲に属する全ての変形、様々な改良、代替および改質は、全て本発明の範囲内のものである。

以上の実施例１〜２を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
暗号処理におけるＦＯ関数及びＦＬ関数の演算を行う暗号処理装置であって、
２Ｎビットの入力と第１拡大鍵とに基づいてＦＬ関数の演算を行って２Ｎビットの出力を生成するＦＬ関数演算部と、
Ｎビットの入力と第２拡大鍵と第３拡大鍵とに基づいてＦＩ関数の部分関数の演算を行ってＮビットの出力を生成する部分関数演算部と、
前記部分演算部の出力を記憶するＮビットの中間レジスタと、
前記ＦＬ関数演算部の出力に基づくデータを記憶することができる２Ｎビットの第１データレジスタと、
ＦＬ関数がＦＯ関数の演算結果を用いる第１ケースにおいて、前記部分関数演算部に前記部分関数の演算を６サイクル行わせ、前記中間レジスタの出力を前記ＦＬ関数演算部へ入力し、前記ＦＬ関数演算部の出力に基づくデータを前記第１データレジスタへ記憶させる制御部と、
を備える暗号処理装置。
（付記２）
更に、
前記部分関数演算部の出力に基づくデータを記憶することができる２Ｎビットの第２データレジスタを備え、
前記制御部は、ＦＯ関数がＦＬ関数の演算結果を用いる第２ケースにおいて、前記ＦＬ関数演算部にＦＬ関数の演算を行わせ、前記ＦＬ関数演算部の出力を前記部分関数演算部へ入力し、前記部分関数演算部に前記部分関数の演算を６サイクル行わせ、前記部分関数演算部の出力に基づくデータを前記第２データレジスタへ記憶させる、
付記１に記載の暗号処理装置。
（付記３）
前記制御部は、前記第１ケースにおいて、前記ＦＬ関数演算部にＦＬ関数の演算を奇数回行わせる、
付記１に記載の暗号処理装置。
（付記４）
更に、
前記第１拡大鍵に基づく２Ｎビットの補正ビット列を生成する補正操作部を備え、
前記制御部は、前記第１ケースにおいて、前記ＦＬ関数演算部にＦＬ関数の演算を偶数回行わせると共に、前記補正操作部により生成された前記補正ビット列と前記ＦＬ関数演算部の出力とのＸＯＲ演算を行って前記第１データレジスタへ記憶させる、
付記１に記載の暗号処理装置。
（付記５）
前記補正操作部は、前記第１拡大鍵中のＮビットを１ビット左ローテートして前記補正ビット列の上位Ｎビットにすると共に、Ｎビットの０を前記補正ビット列の下位Ｎビットにする
付記１に記載の暗号処理装置。
（付記６）
前記第１データレジスタは、前記ＦＬ関数演算部の出力をＸＯＲ演算により累積したデータを記憶する、
付記１に記載の暗号処理装置。
（付記７）
前記第２データレジスタは、前記部分関数演算部の出力を上位Ｎビット及び下位Ｎビットの少なくともいずれかとする２ＮビットをＸＯＲ演算により累積したデータを記憶する、
付記２に記載の暗号処理装置。
（付記８）
前記制御部は、前記ＦＬ関数演算部、前記部分関数演算部、前記中間レジスタ、前記第１データレジスタ、前記第２データレジスタを用いて、ＫＡＳＵＭＩのラウンド処理を行い、
前記第１ケースは、前記ラウンド処理の偶数ラウンドであり、
前記第２ケースは、前記ラウンド処理の奇数ラウンドである、
付記２に記載の暗号処理装置。
（付記９）
前記部分関数の２サイクルの演算は、ＦＩ関数の演算である、
付記１に記載の暗号処理装置。
（付記１０）
Ｎは、１６である、
付記１に記載の暗号処理装置。

１１，２１ 制御部
１２ ＦＬ関数
１３ ＦＩ１／２モジュール
１４ａ，１４ｂ データレジスタ
１５ 中間レジスタ
１６ａ，１６ｂ，２６ｃ ＸＯＲゲート
１７ａ，１７ｂ，１７ｃ，１７ｄ，１７ｅ，１７ｆ，１７ｇ，２７ｃ，２７ｆ，２７ｇ セレクタ
２８ 補正操作部

Claims (5)

1. 暗号処理におけるＦＯ関数及びＦＬ関数の演算を行う暗号処理装置であって、
   ２Ｎビットの入力と第１拡大鍵とに基づいてＦＬ関数の演算を行って２Ｎビットの出力を生成するＦＬ関数演算部と、
   Ｎビットの入力と第２拡大鍵と第３拡大鍵とに基づいてＦＩ関数の部分関数の演算を行ってＮビットの出力を生成する部分関数演算部と、
   前記部分演算部の出力を記憶するＮビットの中間レジスタと、
   前記ＦＬ関数演算部の出力に基づくデータを記憶することができる２Ｎビットの第１データレジスタと、
   ＦＬ関数がＦＯ関数の演算結果を用いる第１ケースにおいて、前記部分関数演算部に前記部分関数の演算を６サイクル行わせ、前記中間レジスタの出力を前記ＦＬ関数演算部へ入力し、前記ＦＬ関数演算部の出力に基づくデータを前記第１データレジスタへ記憶させる処理を、複数サイクルに渡って繰り返し行わせる制御部と、
   を備える暗号処理装置。
2. 更に、
   前記部分関数演算部の出力に基づくデータを記憶することができる２Ｎビットの第２データレジスタを備え、
   前記制御部は、ＦＯ関数がＦＬ関数の演算結果を用いる第２ケースにおいて、前記ＦＬ関数演算部にＦＬ関数の演算を行わせ、前記ＦＬ関数演算部の出力を前記部分関数演算部へ入力し、前記部分関数演算部に前記部分関数の演算を６サイクル行わせ、前記部分関数演算部の出力に基づくデータを前記第２データレジスタへ記憶させる処理を、複数サイクルに渡って繰り返し行わせる、
   請求項１に記載の暗号処理装置。
3. 前記制御部は、前記第１ケースにおいて前記ＦＬ関数演算部にＦＬ関数の演算を奇数回行わせる、
   請求項１または請求項２に記載の暗号処理装置。
4. 更に、
   前記第１拡大鍵に基づく２Ｎビットの補正ビット列を生成する補正操作部を備え、
   前記制御部は、前記第１ケースにおいて前記ＦＬ関数演算部にＦＬ関数の演算を偶数回行わせると共に、前記補正操作部により生成された前記補正ビット列と前記ＦＬ関数演算部の出力とのＸＯＲ演算を行って前記第１データレジスタへ記憶させる、
   請求項１乃至請求項３のいずれかに記載の暗号処理装置。
5. 前記補正操作部は、前記第１拡大鍵中のＮビットを１ビット左ローテートして前記補正ビット列の上位Ｎビットにすると共に、Ｎビットの０を前記補正ビット列の下位Ｎビットにする
   請求項４に記載の暗号処理装置。

Images