(57)【要約】【課題】フィードバックループの無い回路によって、ＦＬ関数とＦＬ-1関数をマージした関数を実現する暗号処理装置を提供する。【解決手段】ＡＮＤゲート及びＯＲゲートのうちいずれか一方であって、第１入力ビット列と拡大鍵に基づくビット列とが入力される第１演算ゲートと、第１演算ゲートの出力と第２入力ビット列とが入力される第１ＸＯＲゲートと、第１演算ゲートと異種のゲートであって、第１ＸＯＲゲートの出力と拡大鍵に基づくビット列とが入力される第２演算ゲートと、第２演算ゲートの出力と第１入力ビット列とが入力される第２ＸＯＲゲートと、第１演算ゲートと同種のゲートであって、第２ＸＯＲゲートの出力と拡大鍵に基づくビット列とが入力される第３演算ゲートと、第３演算ゲートの出力と第１ＸＯＲゲートの出力とが入力される第３ＸＯＲゲートとを有する。【選択図】図１
2010164792.tif 000002
【特許請求の範囲】
【請求項１】
暗号処理におけるＦＬ関数及びＦＬ-1関数の演算を行うことができる暗号処理装置であって、
ＡＮＤゲート及びＯＲゲートのうちいずれか一方であって、前記暗号処理装置の入力の２Ｎビットのうち上位Ｎビットである第１入力ビット列と拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか一方に基づく第１拡大鍵ビット列とが入力される第１演算ゲートと、
前記第１演算ゲートの出力と前記暗号処理装置の入力の２Ｎビットのうち下位Ｎビットである第２入力ビット列とが入力される第１ＸＯＲゲートと、
ＡＮＤゲート及びＯＲゲートのうち前記第１演算ゲートと異種のゲートであって、前記第１ＸＯＲゲートの出力と前記拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか他方に基づく第２拡大鍵ビット列とが入力される第２演算ゲートと、
前記第２演算ゲートの出力と前記第１入力ビット列とが入力される第２ＸＯＲゲートと、
ＡＮＤゲート及びＯＲゲートのうち前記第１演算ゲートと同種のゲートであって、前記第２ＸＯＲゲートの出力と前記第１拡大鍵ビット列とが入力される第３演算ゲートと、
前記第３演算ゲートの出力と前記第１ＸＯＲゲートの出力とが入力される第３ＸＯＲゲートと、
を備える暗号処理装置。
【請求項２】
更に、
選択信号に基づいて、前記第１ＸＯＲゲートの出力と前記第２入力ビット列とのいずれかを選択して前記第２演算ゲート及び前記第３ＸＯＲゲートへ出力する第１セレクタと、
前記選択信号に基づいて、前記第３ＸＯＲゲートの出力と前記第１セレクタの出力とのいずれかを選択して出力する第２セレクタと、
を備える、
請求項１に記載の暗号処理装置。
【請求項３】
更に、
選択信号に基づいて、前記第１演算ゲートの出力と前記Ｎビットの０信号とのいずれかを選択して前記第１ＸＯＲゲートへ出力する第３セレクタと、
前記選択信号に基づいて、前記第３演算ゲートの出力と前記Ｎビットの０信号とのいずれかを選択して前記第３ＸＯＲゲートへ出力する第４セレクタと、
を備える、
請求項１に記載の暗号処理装置。
【請求項４】
更に、
前記第１演算ゲートの出力と選択信号とのＡＮＤ演算を行って前記第１ＸＯＲゲートへ出力する第１ＡＮＤゲートと、
前記第３演算ゲートの出力と前記選択信号の否定信号とのＡＮＤ演算を行って前記第３ＸＯＲゲートへ出力する第３ＡＮＤゲートと、
を備える、
請求項１に記載の暗号処理装置。
【請求項５】
更に、
前記拡大鍵の上位Ｎビットと選択信号とのＡＮＤ演算を行って前記第１演算ゲートへ出力する第３ＡＮＤゲートと、
前記拡大鍵の上位Ｎビットと前記選択信号の否定信号とのＡＮＤ演算を行って前記第３演算ゲートへ出力する第４ＡＮＤゲートと、
を備え、
前記第１演算ゲート及び前記第３演算ゲートは、ＡＮＤゲートであり、
前記第２演算ゲートは、ＯＲゲートである、
請求項１に記載の暗号処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロック暗号を処理するためのＦＬ関数及びＦＬ-1関数の少なくともいずれかの演算を行うことができる暗号処理装置に関するものである。
【背景技術】
【０００２】
セキュリティシステムの基盤技術として、様々な暗号方式が利用されている。暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵（公開鍵）を一般に公開する代わりに、暗号文を復号するための鍵（秘密鍵）を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵（秘密鍵）を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。
【０００３】
共通鍵方式の暗号（以下、共通鍵暗号と呼ぶ）は、公開鍵方式の暗号（以下、公開鍵暗号と呼ぶ）と比較した場合、処理速度が速くコンパクトに実装できるという利点がある。このため、携帯電話やＩＣカードなどの小型機器に暗号化機能を付加する場合には、共通鍵暗号が利用される。また、処理速度が高速であり、情報をリアルタイムで暗号化／復号化できるので、放送や通信分野における情報通信にも利用されている。
【０００４】
共通鍵暗号には、ストリーム暗号とブロック暗号がある。現時点では、安全性の観点から、共通鍵暗号にはブロック暗号が使用されている。ブロック暗号は、平文（暗号化の対象となる文）を一定のビット長のまとまり（これを、ブロックと呼ぶ）に分割し、ブロック単位で暗号化を行う。尚、暗号化の処理単位であるブロックのビット長は“ブロック長”と呼ばれる。
【０００５】
共通鍵暗号方式のブロック暗号は、ブロック長に応じて様々なアルゴリズムが知られている。代表的なものとしては、ＤＥＳ、ＡＥＳ、ＳＣ２０００、ＭＩＳＴＹ（ＭＩＳＴＹ１、ＭＩＳＴＹ２）、ＫＡＳＵＭＩ、ＣＡＭＥＬＬＩＡなどがある。これらの共通鍵暗号のアルゴリズムは、ソフトウェアもしくはハードウェアにより実装される。
【０００６】
共通鍵暗号のアルゴリズムの１つであるＭＩＳＴＹ１（例えば、非特許文献１）について説明する。ＭＩＳＴＹ１は、秘密鍵を１２８ｂｉｔとし、６４ｂｉｔを暗号化単位とするアルゴリズムである。すなわち６４ｂｉｔの平文から１２８ｂｉｔの秘密鍵を用いて６４ｂｉｔの暗号文を生成する。以下では、ＭＩＳＴＹ１のラウンド処理部について述べる。
【０００７】
図１０は、ＭＩＳＴＹ１ラウンド処理部の構成の一例を示す回路図である。この図において、左側は、暗号化処理のラウンド処理部を示し、右側は、復号処理のラウンド処理部を示す。
【０００８】
この図のＭＩＳＴＹ１のラウンド処理部は、段数ｎが８の場合（非特許文献１において推奨値とされている）の処理を表している。ＭＩＳＴＹ１のラウンド処理部は、ＦＯ関数（ＦＯ１，ＦＯ２，ＦＯ３，ＦＯ４，ＦＯ５，ＦＯ６，ＦＯ７，ＦＯ８）とＦＬ関数（ＦＬ１，ＦＬ２，ＦＬ３，ＦＬ４，ＦＬ５，ＦＬ６，ＦＬ７，ＦＬ８，ＦＬ９，ＦＬ１０）またはＦＬ-1関数（ＦＬ１-1，ＦＬ２-1，ＦＬ３-1，ＦＬ４-1，ＦＬ５-1，ＦＬ６-1，ＦＬ７-1，ＦＬ８-1，ＦＬ９-1，ＦＬ１０-1）から構成されるフェイステル（Feistel）構造を有している。ＭＩＳＴＹ１の暗号化処理では、６４ｂｉｔの平文Ｐが入力され、フェイステル構造を経由することで暗号化が行われ、最終的に６４ｂｉｔの暗号文Ｃが出力される。復号処理では、６４ｂｉｔの暗号文Ｃが入力され、最終的に６４ｂｉｔの平文Ｐが出力される。
【０００９】
以下では、ＦＬ関数とＦＬ-1関数について説明する。
【００１０】
図１１は、ＦＬ関数とＦＬ-1関数の構成の一例を示す回路図である。ＦＬ関数は、１段目がＡＮＤゲート１ａで２段目がＯＲゲート２ａである。ＦＬ-1関数はその逆に、１段目がＯＲゲート２ｂで２段目がＡＮＤゲート１ｂである。
【００１１】
ＦＬ関数および、ＦＬ-1関数の入力３２ｂｉｔは、１６ｂｉｔ毎の２つのデータに分割され、排他的論理和（ＸＯＲ：Exclusive OR）、論理積（ＡＮＤ）、論理和（ＯＲ）によって変換が行われる。ＫＬij（１≦ｉ≦８，１≦ｊ≦２）は、ＫＬiの左からｊ番目の１６ｂｉｔデータである。ここで、ＫＬiは拡大鍵のことであり、ＭＩＳＴＹ１では、拡大鍵処理を実行することで、１２８ｂｉｔの秘密鍵Ｋから２５６ｂｉｔの拡大鍵ＫＬiを生成する。拡大鍵の生成法の詳細は非特許文献１に記されている。
【００１２】
ＦＬ関数において、入力３２ｂｉｔの上位１６ｂｉｔのビット列と拡大鍵の上位１６ｂｉｔＫＬi1とは、ＡＮＤゲート１ａへ入力される。入力３２ｂｉｔの下位１６ｂｉｔのビット列とＡＮＤゲート１ａの出力とは、ＸＯＲゲート３ａへ入力される。ＸＯＲゲート３ａの出力と拡大鍵の下位１６ｂｉｔＫＬi2とは、ＯＲゲート２ａへ入力される。入力３２ｂｉｔの上位１６ｂｉｔのビット列とＯＲゲート２ａの出力とは、ＸＯＲゲート３ｂへ入力される。ＸＯＲゲート３ｂの出力は、ＦＬ関数の出力３２ｂｉｔの上位１６ビットとなり、ＸＯＲゲート３ａの出力は、ＦＬ関数の出力３２ｂｉｔの下位１６ビットとなる。
【００１３】
ＦＬ-1関数において、入力３２ｂｉｔの下位１６ｂｉｔのビット列と拡大鍵の下位１６ｂｉｔＫＬi2とは、ＯＲゲート２ｂへ入力される。入力３２ｂｉｔの上位１６ｂｉｔのビット列とＯＲゲート２ｂの出力とは、ＸＯＲゲート３ｃへ入力される。ＸＯＲゲート３ｃの出力と拡大鍵の上位１６ｂｉｔＫＬi1とは、ＡＮＤゲート１ｂへ入力される。入力３２ｂｉｔの下位１６ｂｉｔのビット列とＡＮＤゲート１ｂの出力とは、ＸＯＲゲート３ｄへ入力される。ＸＯＲゲート３ｃの出力は、ＦＬ-1関数の出力３２ｂｉｔの上位１６ビットとなり、ＸＯＲゲート３ｄの出力は、ＦＬ-1関数の出力３２ｂｉｔの下位１６ビットとなる。
【００１４】
ＦＬ関数とＦＬ-1関数の実装法の従来例１について以下に説明する。
【００１５】
暗号化処理と復号処理の両方に対応したハードウェアを実装する場合、ＦＬ関数とＦＬ-1関数の２つを実装する必要がある。図１２は、従来例１の実装法を示す回路図である。これは、暗号化処理と復号処理に応じて、ＦＬ関数６とＦＬ-1関数７をセレクタ５で切り替えることができるハードウェアである。
【００１６】
ＦＬ関数とＦＬ-1関数の実装法の従来例２について以下に説明する。
【００１７】
ＦＬ関数とＦＬ-1関数の実装に関して、小型化を狙った実装法がある（例えば、特許文献１）。図１３は、従来例２の実装法を示す回路図である。従来例２は、ＡＮＤゲート１ｃとＯＲゲート２ｃをそれぞれ１個ずつのみ用いて実装する。つまり、２つの関数の共通部分であるＡＮＤゲートとＯＲゲートの両方を共用化し、１つの関数にマージしている。
【００１８】
従来例２の関数において、入力３２ｂｉｔの下位１６ｂｉｔのビット列とＡＮＤゲート１ｃの出力とは、ＸＯＲゲート３ｅへ入力される。入力３２ｂｉｔの上位１６ｂｉｔのビット列とＯＲゲート２ｃの出力とは、ＸＯＲゲート３ｆへ入力される。入力３２ｂｉｔの上位１６ｂｉｔのビット列とＸＯＲゲート３ｆの出力とは、セレクタ５ａへ入力される。入力３２ｂｉｔの下位１６ｂｉｔのビット列とＸＯＲゲート３ｅの出力とは、セレクタ５ｂへ入力される。セレクタ５ａの出力と拡大鍵の上位１６ｂｉｔＫＬi1とは、ＡＮＤゲート１ｃへ入力される。セレクタ５ｂの出力と拡大鍵の下位１６ｂｉｔＫＬi2とは、ＯＲゲート２ｃへ入力される。ＸＯＲゲート３ｆの出力は、従来例２の関数の出力３２ｂｉｔの上位１６ビットとなり、ＸＯＲゲート３ｅの出力は、従来例２の関数の出力３２ｂｉｔの下位１６ビットとなる。
【００１９】
セレクタ５ａ，５ｂにおいて、２入力のうち、上部信号が選択された場合は、この関数はＦＬ関数として機能し、下段信号が選択された場合は、ＦＬ-1関数として機能する。この技術を用いると、回路規模を大きく削減することが可能である。
【先行技術文献】
【特許文献】
【００２０】
【特許文献１】特許第４１２８３９５号公報
【非特許文献】
【００２１】
【非特許文献１】ＭＩＳＴＹ１仕様書，ｈｔｔｐ：／／ｗｗｗ．ｃｒｙｐｔｒｅｃ．ｇｏ．ｊｐ／ｃｒｙｐｔｒｅｃ＿０３＿ｓｐｅｃ＿ｃｙｐｈｅｒｌｉｓｔ＿ｆｉｌｅｓ／ＰＤＦ／０５＿０２ｊｓｐｅｃ．ｐｄｆ
【非特許文献２】E. Oswald and P. Rohatgi (Eds.): CHES 2008, LNCS 5154, pp. 315-330, International Association for Cryptologic Research 2008.
【非特許文献３】"Small and High-Speed Hardware Architectures for the 3GPP Standard Cipher KASUMI," Akashi Satoh and Sumio Morioka, Information Security Conference 2002.
【発明の概要】
【発明が解決しようとする課題】
【００２２】
しかしながら、従来例２は、組み合わせ回路のフィードバックループを形成するという重大な問題点を抱えている。従来例２に示される通り、どちらの関数として機能する場合においても、経路中にレジスタが含まれない、且つ組み合わせ回路のみのループ構造を形成している。この構造が存在すると、ハードウェア記述言語から回路構造への変換作業である論理合成を行うことが非常に困難になる。仮に論理合成が可能となったとしても、変換後に生成された回路が発信回路になる危険性がある。そのため、信頼性という面において、上述のフィードバックループ構造をもつ回路は製品化不可能な実装法である。
【００２３】
このように、ＦＬ関数とＦＬ-1関数の機能を１つの関数としてマージしようとする場合、回路構成としてフィードバックループを形成せずに、回路規模の削減を実現することは容易ではない。そのため、従来のＭＩＳＴＹ１、ＫＡＳＵＭＩに関する多くの特許出願や学術論文では、従来例１のように、ＦＬ関数とＦＬ-1関数が独立に実装されている。
【００２４】
本発明は上述した問題点を解決するためになされたものであり、フィードバックループの無い回路によって、ＦＬ関数とＦＬ-1関数をマージした関数を実現する暗号処理装置を提供することを目的とする。
【課題を解決するための手段】
【００２５】
上述した課題を解決するため、本発明の一態様は、暗号処理におけるＦＬ関数及びＦＬ-1関数の少なくともいずれかの演算を行うことができる暗号処理装置であって、ＡＮＤゲート及びＯＲゲートのうちいずれか一方であって、暗号処理装置の入力の２Ｎビットのうち上位Ｎビットである第１入力ビット列と拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか一方に基づく第１拡大鍵ビット列とが入力される第１演算ゲートと、第１演算ゲートの出力と暗号処理装置の入力の２Ｎビットのうち下位Ｎビットである第２入力ビット列とが入力される第１ＸＯＲゲートと、ＡＮＤゲート及びＯＲゲートのうち第１演算ゲートと異種のゲートであって、第１ＸＯＲゲートの出力と前記拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか他方に基づく第２拡大鍵ビット列とが入力される第２演算ゲートと、第２演算ゲートの出力と第１入力ビット列とが入力される第２ＸＯＲゲートと、ＡＮＤゲート及びＯＲゲートのうち第１演算ゲートと同種のゲートであって、第２ＸＯＲゲートの出力と前記第１拡大鍵ビット列とが入力される第３演算ゲートと、第３演算ゲートの出力と第１ＸＯＲゲートの出力とが入力される第３ＸＯＲゲートとを有する。
【発明の効果】
【００２６】
開示の暗号処理装置によれば、フィードバックループの無い回路によって、ＦＬ関数とＦＬ-1関数をマージした関数を実現することができる。
【図面の簡単な説明】
【００２７】
【図１】実施例１のマージ関数の構成の一例を示す回路図である。
【図２】実施例２のマージ関数の構成の一例を示す回路図である。
【図３】実施例３のマージ関数の構成の一例を示す回路図である。
【図４】実施例４のマージ関数の構成の一例を示す回路図である。
【図５】実施例５のマージ関数の構成の一例を示す回路図である。
【図６】実施例６のマージ関数の構成の一例を示す回路図である。
【図７】実施例７のマージ関数の構成の一例を示す回路図である。
【図８】各実施例の回路規模の一例を示す表である。
【図９】各実施例の遅延時間の一例を示す表である。
【図１０】ＭＩＳＴＹ１ラウンド処理部の構成の一例を示す回路図である。
【図１１】ＦＬ関数とＦＬ-1関数の構成の一例を示す回路図である。
【図１２】従来例１の実装法を示す回路図である。
【図１３】従来例２の実装法を示す回路図である。
【発明を実施するための形態】
【００２８】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００２９】
本発明は、ＭＩＳＴＹ１、ＭＩＳＴＹ２、ＫＡＳＵＭＩ、ＣＡＭＥＬＬＩＡなど、ＦＬ関数とＦＬ-1関数を採用する共通鍵暗号方式において、ＦＬ関数とＦＬ-1関数を１つの関数として効率よくマージする新たな関数を用いることで、小型ハードウェアを実現する。本発明は、小型な共通鍵暗号ハードウェアを作る時に適用可能である。
【００３０】
以下、ＭＩＳＴＹ１において、ＦＬ関数とＦＬ-1関数を１つにマージしたマージ関数の例を示す。ＭＩＳＴＹ２やＫＡＳＵＭＩ、ＣＡＭＥＬＬＩＡなどに適用する場合も、基本的な考え方はＭＩＳＴＹ１の場合と同様である。
【００３１】
（実施例１）
図１は、実施例１のマージ関数の構成の一例を示す回路図である。上述したように、ＦＬ関数は、１段目がＡＮＤゲートで２段目がＯＲゲートである、２段構造を持つ関数である。ＦＬ-1関数はその逆に、１段目がＯＲゲートで２段目がＡＮＤゲートである、２段構造を持つ関数である。これに対して、本実施例のマージ関数は、３段構造を持つ関数である。本実施例のマージ関数は、１段目をＡＮＤゲート１１ａ（第１演算ゲート）、２段目をＯＲゲート１２（第２演算ゲート）、３段目をＡＮＤゲート１１ｂ（第３演算ゲート）とし、２つの関数の共通部分をＯＲゲート１２のみとする。
【００３２】
このマージ関数の入力３２ｂｉｔは、上位１６ｂｉｔの入力上位ビット列（第１入力ビット列）と下位１６ｂｉｔの入力下位ビット列（第２入力ビット列）に分割される。ここで、Ｎ＝１６とする。
【００３３】
入力上位ビット列と拡大鍵の上位１６ｂｉｔであるＫＬi1とがＡＮＤゲート１１ａへ入力される。入力下位ビット列とＡＮＤゲート１１ａの出力がＸＯＲゲート１３ａ（第１ＸＯＲゲート）へ入力される。ＸＯＲゲート１３ａの出力と入力下位ビット列とがセレクタ１４ａ（第１セレクタ）へ入力される。
【００３４】
セレクタ１４ａの出力と拡大鍵の下位１６ｂｉｔであるＫＬi2（第２拡大鍵ビット列）とがＯＲゲート１２へ入力される。入力上位ビット列とＯＲゲート１２の出力とがＸＯＲゲート１３ｂ（第２ＸＯＲゲート）へ入力される。
【００３５】
ＸＯＲゲート１３ｂの出力とＫＬi1とがＡＮＤゲート１１ｂへ入力される。セレクタ１４ａの出力とＡＮＤゲート１１ｂの出力とがＸＯＲゲート１３ｃ（第３ＸＯＲゲート）へ入力される。ＸＯＲゲート１３ｃの出力とセレクタ１４ａの出力とがセレクタ１４ｂ（第２セレクタ）へ入力される。
【００３６】
ＸＯＲゲート１３ｂの出力は、マージ関数の出力３２ｂｉｔの上位１６ｂｉｔとなる。セレクタ１４ｂの出力は、マージ関数の出力３２ｂｉｔの下位１６ｂｉｔとなる。
【００３７】
セレクタ１４ａ，１４ｂは、選択信号ｓｅｌにより２入力の一方を選択して出力する。マージ関数がＦＬ関数の指示を受けた場合、セレクタ１４ａがＸＯＲゲート１３ａの出力を選択し、且つセレクタ１４ｂがセレクタ１４ａの出力を選択することにより、このマージ関数は、ＦＬ関数として機能する。マージ関数がＦＬ-1関数の指示を受けた場合、セレクタ１４ａが入力下位ビット列を選択し、且つセレクタ１４ｂがＸＯＲゲート１３ｃの出力を選択することにより、このマージ関数は、ＦＬ-1関数として機能する。
【００３８】
このように、ＡＮＤゲートとＯＲゲートの２つを共通部分とするのではなく、ＯＲゲート１２のみを共通部分とすることによって、フィードバックループの形成を回避することができる。
【００３９】
１つの関数にマージしたことにより、１６ｂｉｔＡＮＤゲートと１６ｂｉｔＸＯＲゲート分の回路規模（５６ｇａｔｅ）が削減される。そのため、従来の従来例１の回路規模が０．１８ｕｍプロセスで約３３６ｇａｔｅなのに対し、実施例１の回路規模は約２８０ｇａｔｅとなる。
【００４０】
実施例１の回路規模を更に削減するために、実施例１におけるセレクタをＡＮＤゲートへと等価変換する。
【００４１】
（実施例２）
図２は、実施例２のマージ関数の構成の一例を示す回路図である。この図において、図１と同一符号は図１に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例１のセレクタ１４ａ，１４ｂをそれぞれＸＯＲゲート１３ａ，１３ｃの入力側へと移動させてセレクタ１５ａ（第３セレクタ），１５ｂ（第４セレクタ）とする。これによって、セレクタ１５ａ，１５ｂはそれぞれＡＮＤゲート１１ａ，１１ｂの出力信号、もしくは１６ｂｉｔの０信号のどちらかを選択するように変更できる。
【００４２】
マージ関数がＦＬ関数の指示を受けた場合、セレクタ１５ａがＡＮＤゲート１１ａの出力を選択し、且つセレクタ１５ｂが０信号を選択することにより、このマージ関数は、ＦＬ関数として機能する。マージ関数がＦＬ-1関数の指示を受けた場合、セレクタ１５ａが０信号を選択し、且つセレクタ１５ｂがＡＮＤゲート１１ｂの出力を選択することにより、このマージ関数は、ＦＬ-1関数として機能する。
【００４３】
（実施例３）
図３は、実施例３のマージ関数の構成の一例を示す回路図である。この図において、図２と同一符号は図２に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例２におけるセレクタ１５ａ，１５ｂをそれぞれＡＮＤゲート１６ａ（第１ＡＮＤゲート），１６ｂ（第２ＡＮＤゲート）に等価変換する。実施例２では、セレクタにおける選択信号ｓｅｌは１ｂｉｔであるが、実施例３では１６ｂｉｔに拡張した信号である。
【００４４】
ＡＮＤゲート１６ａは、ＡＮＤゲート１１ａの出力と選択信号ｓｅｌとのＡＮＤ演算を行う。ＡＮＤゲート１６ｂは、ＡＮＤゲート１１ｂの出力と選択信号ｓｅｌの否定信号とのＡＮＤ演算を行う。
【００４５】
このようにセレクタをＡＮＤゲートに変換することにより、実施例１における回路規模をさらに削減することができる。
【００４６】
（実施例４）
ＦＬ関数とＦＬ-1関数を１つの関数としてマージを行うことにより、クリティカルパスが延長され、処理速度の低下を引き起こす場合がある。
【００４７】
ここで、２−１ＮＡＮＤゲートの遅延をｄとする。ＡＮＤゲート、ＯＲゲート、ＸＯＲゲート、セレクタをＮＡＮＤゲートのみで構成する場合、各ゲートの遅延は、２ｄ、２ｄ、３ｄ、３ｄとなる。
【００４８】
従来例１のクリティカルパスは、ＦＬもしくはＦＬ-1の遅延が１０ｄ（ＦＬにおける（１段目：ＡＮＤ−ＸＯＲ）＋（２段目：ＯＲ−ＸＯＲ）、もしくはＦＬ-1における（１段目：ＯＲ−ＸＯＲ）＋（２段目：ＡＮＤ−ＸＯＲ）より（２ｄ＋３ｄ）＋（２ｄ＋３ｄ）＝１０ｄ）、ＦＬとＦＬ-1をセレクトするセレクタが３ｄのため、計１３ｄとなる。
【００４９】
一方、実施例２におけるクリティカルパスは、（１段目：ＡＮＤ−ｓｅｌ−ＸＯＲ）＋（２段目：ＯＲ−ＸＯＲ）＋（３段目：ＡＮＤ−ｓｅｌ−ＸＯＲ）＝（２ｄ＋３ｄ＋３ｄ）＋（２ｄ＋３ｄ）＋（２ｄ＋３ｄ＋３ｄ）＝２１ｄとなる。
る。この理由は、従来例１では並列だったＦＬ関数とＦＬ-1関数に対して、実施例３では縦列の構造となっているためである。これを解決するために、実施例３で等価変換したＡＮＤゲートをクリティカルパス上から移動する。
【００５０】
図４は、実施例４のマージ関数の構成の一例を示す回路図である。この図において、図３と同一符号は図３に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例３におけるＡＮＤゲート１６ａ，１６ｂをクリティカルパス上から移動してそれぞれＡＮＤゲート１７ａ（第３ＡＮＤゲート），１７ｂ（第４ＡＮＤゲート）とする。
【００５１】
ＡＮＤゲート１７ａは、選択信号ｓｅｌとＫＬi1とのＡＮＤ演算を行う。ＡＮＤゲート１７ｂは、選択信号ｓｅｌの否定信号とＫＬi1とのＡＮＤ演算を行う。
【００５２】
ＭＩＳＴＹ１では、拡大鍵であるＫＬijを生成するパスはクリティカルパスにならない。なぜなら、ＦＬ関数の処理サイクルより事前のサイクルでＫＬijを生成できる実装が多数知られており、これらの方法を用いることで、ＫＬijの生成遅延時間の影響をＦＬ関数の遅延時間に及ぼさない処理が可能であるからである。このＭＩＳＴＹ１の性質を考慮することにより、実施例３のＡＮＤゲート１６ａ，１６ｂを本実施例のＡＮＤゲート１７ａ，１７ｂへ移動することができる。これにより、クリティカルパスの遅延がＡＮＤゲート２個分短縮される。つまり、（１段目：ＡＮＤ−ＸＯＲ）＋（２段目：ＯＲ−ＸＯＲ）＋（３段目：ＡＮＤ−ＸＯＲ）＝（２ｄ＋３ｄ）＋（２ｄ＋３ｄ）＋（２ｄ＋３ｄ）＝１５ｄとなる。
【００５３】
（実施例５）
図５は、実施例５のマージ関数の構成の一例を示す回路図である。この図において、図１と同一符号は図１に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、基本的な構成と効果が実施例１と同様であるが、ＯＲゲート及びＡＮＤゲートの配置が実施例１と異なる。実施例１では、ＦＬ関数とＦＬ-1関数の共通部分をＯＲゲートとしたが、本実施例ではＡＮＤゲートを共通部分としている。つまり、本実施例のマージ関数は、１段目をＯＲゲート２１ａ（第１演算ゲート）、２段目をＡＮＤゲート２２（第２演算ゲート）、３段目をＯＲゲート２１ｂ（第３演算ゲート）とし、２つの関数の共通部分をＡＮＤゲート２２のみとする。
【００５４】
ＯＲゲート２１ａの出力にＸＯＲゲート１３ａの入力が接続される。ＡＮＤゲート２２の出力にＸＯＲゲート１３ｂの入力が接続される。ＯＲゲート２１ｂの出力にＸＯＲゲート１３ｃの入力が接続される。
【００５５】
（実施例６）
図６は、実施例６のマージ関数の構成の一例を示す回路図である。この図において、図５と同一符号は図５に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例５のセレクタ１４ａ，１４ｂをそれぞれＸＯＲゲート１３ａ，１３ｃの入力側へと移動させてセレクタ１５ａ，１５ｂとする。本実施例は、基本的な構成と効果が実施例２と同様であるが、ＯＲゲート及びＡＮＤゲートの配置が実施例２と異なる。
【００５６】
（実施例７）
図７は、実施例７のマージ関数の構成の一例を示す回路図である。この図において、図６と同一符号は図６に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例６におけるセレクタ１５ａ，１５ｂをそれぞれＡＮＤゲート１６ａ，１６ｂに等価変換する。本実施例は、基本的な構成と効果が実施例３と同様であるが、ＯＲゲート及びＡＮＤゲートの配置が実施例３と異なる。
【００５７】
上述の各実施例の効果について以下に説明する。
【００５８】
図８は、各実施例の回路規模の一例を示す表である。この表は、実施例１〜７と従来例１，２のそれぞれにおける回路規模の一例を示す。この表において、＃１−ｂｉｔ  ＭＵＸは、１−ｂｉｔ幅のセレクタの個数を示し、＃１−ｂｉｔ  ＡＮＤ／ＯＲは、１−ｂｉｔ幅のＡＮＤゲート及びＯＲゲートの個数を示し、＃１−ｂｉｔ  ＸＯＲは、１−ｂｉｔ幅のＸＯＲゲートの個数を示し、Ｇａｔｅ  Ｃｏｕｎｔは、ＦＬ関数とＦＬ-1関数に関する回路規模を示す。従来例１は、ＦＬ関数とＦＬ-1関数をそれぞれ独立に持っており、これらを切り替えるセレクタも必要とするため、回路規模が３３６ｇａｔｅと大きくなっている。従来例２は、回路規模は小さくなっているものの、フィードバックループ構造を持つために製品化不可能な実装である。実施例１、２では従来例１と比較して、回路規模は削減されるものの、その効果は小さい。この理由は、セレクタの回路規模が同一だからである。実施例３、４では、この実施例１におけるセレクタをＡＮＤゲートへと等価変換することによって、２００ｇａｔｅまで回路規模を削減している。
【００５９】
以上より、従来例１と実施例４を比較すると、本発明により、ＦＬ関数とＦＬ-1関数に関する回路規模が３３６ｇａｔｅから２００ｇａｔｅへと約４０％削減されることが見積もれた。
【００６０】
従来の小型化されたＭＩＳＴＹ１ハードウェア（０．１８ｕｍプロセスで約４０００ｇａｔｅ、例えば、非特許文献２を参照）に実施例４を適用すると、約３．５％の回路規模の削減効果が期待できる。
【００６１】
従来の小型化されたＫＡＳＵＭＩハードウェア（０．１３ｕｍプロセスで約３４００ｇａｔｅ：例えば、非特許文献３を参照）に実施例４を適用すると、最大で４％の回路規模の削減効果が期待できる。
【００６２】
図９は、各実施例の遅延時間の一例を示す表である。この表は、実施例１〜７と従来例１，２のそれぞれにおける遅延時間の一例を示す。この表において、ＡＮＤ／ＯＲは、マージ関数におけるＡＮＤゲート及びＯＲゲートの数を示し、ＸＯＲは、マージ関数におけるＸＯＲゲートの数を示し、２−１ＭＵＸは、マージ関数におけるセレクタの数を示し、遅延は、マージ関数の遅延時間を示す。従来例１では、遅延時間が１３ｄであるが、実施例１では２１ｄと大きく増加している。これは前述の通り、マージ関数が３段構造をとっており、さらに新たなセレクタがマージ関数の内部に生成されたためである。実施例３では、セレクタをＡＮＤゲートへと等価変換したことにより、２ｄだけ遅延時間が短縮されたものの、従来例１と比較すると大きい。実施例４において、クリティカルパス上からＡＮＤゲートを２つ分移動することにより、遅延時間が１５ｄとなり、従来例１の１３ｄとほぼ同等の遅延時間となる。
【００６３】
実施例１、５によれば、ＡＮＤゲートとＯＲゲートの２つを共通モジュールしてマージを行うのではなく、ＡＮＤゲート、もしくはＯＲゲートのどちらか一方のみを共通モジュールとして、マージを行うことにより、フィードバックループの形成を回避することができる。
【００６４】
実施例２、３、４、６、７によれば、回路規模の増加とクリティカルパス延長の原因となっているセレクタをＡＮＤゲートへと等価変換することによって、回路規模の削減を行い、さらにこのＡＮＤゲートをクリティカルパス以外の部分へと移動させることによって、クリティカルパスの短縮を図ることができる。
【００６５】
上述の各実施例によれば、フィードバックループを形成せずに、大幅な回路規模の削減、ならびにクリティカルパスの延長を最大限に抑制する回路構造を実現する。
【００６６】
実施例１〜４において、第１拡大鍵ビット列は、ＫＬi1に基づくＡＮＤゲートの入力に対応し、第２拡大鍵ビット列は、ＫＬi2に基づくＯＲゲートの入力に対応する。実施例５〜７において、第１拡大鍵ビット列は、ＫＬi2に基づくＯＲゲートの入力に対応し、第２拡大鍵ビット列は、ＫＬi1に基づくＡＮＤゲートの入力に対応する。
【００６７】
本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。そのため、前述の実施の形態は、あらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には、何ら拘束されない。更に、特許請求の範囲の均等範囲に属する全ての変形、様々な改良、代替および改質は、全て本発明の範囲内のものである。
【００６８】
以上の実施例１〜７を含む実施形態に関し、更に以下の付記を開示する。
（付記１）
暗号処理におけるＦＬ関数及びＦＬ-1関数の演算を行うことができる暗号処理装置であって、
ＡＮＤゲート及びＯＲゲートのうちいずれか一方であって、前記暗号処理装置の入力の２Ｎビットのうち上位Ｎビットである第１入力ビット列と拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか一方に基づく第１拡大鍵ビット列とが入力される第１演算ゲートと、
前記第１演算ゲートの出力と前記暗号処理装置の入力の２Ｎビットのうち下位Ｎビットである第２入力ビット列とが入力される第１ＸＯＲゲートと、
ＡＮＤゲート及びＯＲゲートのうち前記第１演算ゲートと異種のゲートであって、前記第１ＸＯＲゲートの出力と前記拡大鍵の上位Ｎビット及び下位Ｎビットのいずれか他方に基づく第２拡大鍵ビット列とが入力される第２演算ゲートと、
前記第２演算ゲートの出力と前記第１入力ビット列とが入力される第２ＸＯＲゲートと、
ＡＮＤゲート及びＯＲゲートのうち前記第１演算ゲートと同種のゲートであって、前記第２ＸＯＲゲートの出力と前記第１拡大鍵ビット列とが入力される第３演算ゲートと、
前記第３演算ゲートの出力と前記第１ＸＯＲゲートの出力とが入力される第３ＸＯＲゲートと、
を備える暗号処理装置。
（付記２）
更に、
選択信号に基づいて、前記第１ＸＯＲゲートの出力と前記第２入力ビット列とのいずれかを選択して前記第２演算ゲート及び前記第３ＸＯＲゲートへ出力する第１セレクタと、
前記選択信号に基づいて、前記第３ＸＯＲゲートの出力と前記第１セレクタの出力とのいずれかを選択して出力する第２セレクタと、
を備える、
付記１に記載の暗号処理装置。
（付記３）
ＦＬ関数の指示を受けた前記第１セレクタは、前記第１ＸＯＲゲートの出力を選択し、
ＦＬ関数の指示を受けた前記第２セレクタは、前記第１セレクタの出力を選択し、
ＦＬ-1関数の指示を受けた前記第１セレクタは、前記第２入力ビット列を選択し、
ＦＬ-1関数の指示を受けた前記第２セレクタは、前記第３ＸＯＲゲートの出力を選択する、
付記２に記載の暗号処理装置。
（付記４）
更に、
選択信号に基づいて、前記第１演算ゲートの出力と前記Ｎビットの０信号とのいずれかを選択して前記第１ＸＯＲゲートへ出力する第３セレクタと、
前記選択信号に基づいて、前記第３演算ゲートの出力と前記Ｎビットの０信号とのいずれかを選択して前記第３ＸＯＲゲートへ出力する第４セレクタと、
を備える、
付記１に記載の暗号処理装置。
（付記５）
ＦＬ関数の指示を受けた前記第３セレクタは、前記第１演算ゲートの出力を選択し、
ＦＬ関数の指示を受けた前記第４セレクタは、前記Ｎビットの０信号を選択し、
ＦＬ-1関数の指示を受けた前記第３セレクタは、前記Ｎビットの０信号を選択し、
ＦＬ-1関数の指示を受けた前記第４セレクタは、前記第３演算ゲートの出力を選択する、
付記４に記載の暗号処理装置。
（付記６）
更に、
前記第１演算ゲートの出力と選択信号とのＡＮＤ演算を行って前記第１ＸＯＲゲートへ出力する第１ＡＮＤゲートと、
前記第３演算ゲートの出力と前記選択信号の否定信号とのＡＮＤ演算を行って前記第３ＸＯＲゲートへ出力する第３ＡＮＤゲートと、
を備える、
付記１に記載の暗号処理装置。
（付記７）
更に、
前記拡大鍵の上位Ｎビットと選択信号とのＡＮＤ演算を行って前記第１演算ゲートへ出力する第３ＡＮＤゲートと、
前記拡大鍵の上位Ｎビットと前記選択信号の否定信号とのＡＮＤ演算を行って前記第３演算ゲートへ出力する第４ＡＮＤゲートと、
を備え、
前記第１演算ゲート及び前記第３演算ゲートは、ＡＮＤゲートであり、
前記第２演算ゲートは、ＯＲゲートである、
付記１に記載の暗号処理装置。
（付記８）
前記第１演算ゲート及び前記第３演算ゲートは、ＡＮＤゲートであり、
前記第２演算ゲートは、ＯＲゲートである、
付記１に記載の暗号処理装置。
（付記９）
前記第１演算ゲート及び前記第３演算ゲートは、ＯＲゲートであり、
前記第２演算ゲートは、ＡＮＤゲートである、
付記１に記載の暗号処理装置。
（付記１０）
前記第１演算ゲート、前記第１ＸＯＲゲート、前記第２ゲート、前記第２ＸＯＲゲート、前記演算第３ゲート、前記第３ＸＯＲゲートは、共通鍵暗号のアルゴリズムのＭＩＳＴＹ１におけるＦＬ関数及びＦＬ-1関数に設けられる、
付記１に記載の暗号処理装置。
（付記１１）
前記第１演算ゲート、前記第１ＸＯＲゲート、前記第２ゲート、前記第２ＸＯＲゲート、前記演算第３ゲート、前記第３ＸＯＲゲートは、共通鍵暗号のアルゴリズムのＭＩＳＴＹ２におけるＦＬ関数及びＦＬ-1関数に設けられる、
付記１に記載の暗号処理装置。
（付記１２）
前記第１演算ゲート、前記第１ＸＯＲゲート、前記第２ゲート、前記第２ＸＯＲゲート、前記演算第３ゲート、前記第３ＸＯＲゲートは、共通鍵暗号のアルゴリズムのＫＡＳＵＭＩにおけるＦＬ関数及びＦＬ-1関数に設けられる、
付記１に記載の暗号処理装置。
（付記１３）
前記第１演算ゲート、前記第１ＸＯＲゲート、前記第２ゲート、前記第２ＸＯＲゲート、前記演算第３ゲート、前記第３ＸＯＲゲートは、共通鍵暗号のアルゴリズムのＣＡＭＥＬＬＩＡにおけるＦＬ関数及びＦＬ-1関数に設けられる、
付記１に記載の暗号処理装置。
【符号の説明】
【００６９】
１１ａ，１１ｂ，２２，１６ａ，１６ｂ，１７ａ，１７ｂ  ＡＮＤゲート
１２，２１ａ，２１ｂ  ＯＲゲート
１３ａ，１３ｂ，１３ｃ  ＸＯＲゲート
１４ａ，１４ｂ，１５ａ，１５ｂ  セレクタ
【図１】
2010164792.tif 000003
【図２】
2010164792.tif 000004
【図３】
2010164792.tif 000005
【図４】
2010164792.tif 000006
【図５】
2010164792.tif 000007
【図６】
2010164792.tif 000008
【図７】
2010164792.tif 000009
【図８】
2010164792.tif 000010
【図９】
2010164792.tif 000011
【図１０】
2010164792.tif 000012
【図１１】
2010164792.tif 000013
【図１２】
2010164792.tif 000014
【図１３】
2010164792.tif 000015