暗号処理装置
【課題】フィードバックループの無い回路によって、FL関数とFL-1関数をマージした関数を実現する暗号処理装置を提供する。
【解決手段】ANDゲート及びORゲートのうちいずれか一方であって、第1入力ビット列と拡大鍵に基づくビット列とが入力される第1演算ゲートと、第1演算ゲートの出力と第2入力ビット列とが入力される第1XORゲートと、第1演算ゲートと異種のゲートであって、第1XORゲートの出力と拡大鍵に基づくビット列とが入力される第2演算ゲートと、第2演算ゲートの出力と第1入力ビット列とが入力される第2XORゲートと、第1演算ゲートと同種のゲートであって、第2XORゲートの出力と拡大鍵に基づくビット列とが入力される第3演算ゲートと、第3演算ゲートの出力と第1XORゲートの出力とが入力される第3XORゲートとを有する。
【解決手段】ANDゲート及びORゲートのうちいずれか一方であって、第1入力ビット列と拡大鍵に基づくビット列とが入力される第1演算ゲートと、第1演算ゲートの出力と第2入力ビット列とが入力される第1XORゲートと、第1演算ゲートと異種のゲートであって、第1XORゲートの出力と拡大鍵に基づくビット列とが入力される第2演算ゲートと、第2演算ゲートの出力と第1入力ビット列とが入力される第2XORゲートと、第1演算ゲートと同種のゲートであって、第2XORゲートの出力と拡大鍵に基づくビット列とが入力される第3演算ゲートと、第3演算ゲートの出力と第1XORゲートの出力とが入力される第3XORゲートとを有する。
【発明の詳細な説明】
【技術分野】
【0001】
本発明は、ブロック暗号を処理するためのFL関数及びFL-1関数の少なくともいずれかの演算を行うことができる暗号処理装置に関するものである。
【背景技術】
【0002】
セキュリティシステムの基盤技術として、様々な暗号方式が利用されている。暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。
【0003】
共通鍵方式の暗号(以下、共通鍵暗号と呼ぶ)は、公開鍵方式の暗号(以下、公開鍵暗号と呼ぶ)と比較した場合、処理速度が速くコンパクトに実装できるという利点がある。このため、携帯電話やICカードなどの小型機器に暗号化機能を付加する場合には、共通鍵暗号が利用される。また、処理速度が高速であり、情報をリアルタイムで暗号化/復号化できるので、放送や通信分野における情報通信にも利用されている。
【0004】
共通鍵暗号には、ストリーム暗号とブロック暗号がある。現時点では、安全性の観点から、共通鍵暗号にはブロック暗号が使用されている。ブロック暗号は、平文(暗号化の対象となる文)を一定のビット長のまとまり(これを、ブロックと呼ぶ)に分割し、ブロック単位で暗号化を行う。尚、暗号化の処理単位であるブロックのビット長は“ブロック長”と呼ばれる。
【0005】
共通鍵暗号方式のブロック暗号は、ブロック長に応じて様々なアルゴリズムが知られている。代表的なものとしては、DES、AES、SC2000、MISTY(MISTY1、MISTY2)、KASUMI、CAMELLIAなどがある。これらの共通鍵暗号のアルゴリズムは、ソフトウェアもしくはハードウェアにより実装される。
【0006】
共通鍵暗号のアルゴリズムの1つであるMISTY1(例えば、非特許文献1)について説明する。MISTY1は、秘密鍵を128bitとし、64bitを暗号化単位とするアルゴリズムである。すなわち64bitの平文から128bitの秘密鍵を用いて64bitの暗号文を生成する。以下では、MISTY1のラウンド処理部について述べる。
【0007】
図10は、MISTY1ラウンド処理部の構成の一例を示す回路図である。この図において、左側は、暗号化処理のラウンド処理部を示し、右側は、復号処理のラウンド処理部を示す。
【0008】
この図のMISTY1のラウンド処理部は、段数nが8の場合(非特許文献1において推奨値とされている)の処理を表している。MISTY1のラウンド処理部は、FO関数(FO1,FO2,FO3,FO4,FO5,FO6,FO7,FO8)とFL関数(FL1,FL2,FL3,FL4,FL5,FL6,FL7,FL8,FL9,FL10)またはFL-1関数(FL1-1,FL2-1,FL3-1,FL4-1,FL5-1,FL6-1,FL7-1,FL8-1,FL9-1,FL10-1)から構成されるフェイステル(Feistel)構造を有している。MISTY1の暗号化処理では、64bitの平文Pが入力され、フェイステル構造を経由することで暗号化が行われ、最終的に64bitの暗号文Cが出力される。復号処理では、64bitの暗号文Cが入力され、最終的に64bitの平文Pが出力される。
【0009】
以下では、FL関数とFL-1関数について説明する。
【0010】
図11は、FL関数とFL-1関数の構成の一例を示す回路図である。FL関数は、1段目がANDゲート1aで2段目がORゲート2aである。FL-1関数はその逆に、1段目がORゲート2bで2段目がANDゲート1bである。
【0011】
FL関数および、FL-1関数の入力32bitは、16bit毎の2つのデータに分割され、排他的論理和(XOR:Exclusive OR)、論理積(AND)、論理和(OR)によって変換が行われる。KLij(1≦i≦8,1≦j≦2)は、KLiの左からj番目の16bitデータである。ここで、KLiは拡大鍵のことであり、MISTY1では、拡大鍵処理を実行することで、128bitの秘密鍵Kから256bitの拡大鍵KLiを生成する。拡大鍵の生成法の詳細は非特許文献1に記されている。
【0012】
FL関数において、入力32bitの上位16bitのビット列と拡大鍵の上位16bitKLi1とは、ANDゲート1aへ入力される。入力32bitの下位16bitのビット列とANDゲート1aの出力とは、XORゲート3aへ入力される。XORゲート3aの出力と拡大鍵の下位16bitKLi2とは、ORゲート2aへ入力される。入力32bitの上位16bitのビット列とORゲート2aの出力とは、XORゲート3bへ入力される。XORゲート3bの出力は、FL関数の出力32bitの上位16ビットとなり、XORゲート3aの出力は、FL関数の出力32bitの下位16ビットとなる。
【0013】
FL-1関数において、入力32bitの下位16bitのビット列と拡大鍵の下位16bitKLi2とは、ORゲート2bへ入力される。入力32bitの上位16bitのビット列とORゲート2bの出力とは、XORゲート3cへ入力される。XORゲート3cの出力と拡大鍵の上位16bitKLi1とは、ANDゲート1bへ入力される。入力32bitの下位16bitのビット列とANDゲート1bの出力とは、XORゲート3dへ入力される。XORゲート3cの出力は、FL-1関数の出力32bitの上位16ビットとなり、XORゲート3dの出力は、FL-1関数の出力32bitの下位16ビットとなる。
【0014】
FL関数とFL-1関数の実装法の従来例1について以下に説明する。
【0015】
暗号化処理と復号処理の両方に対応したハードウェアを実装する場合、FL関数とFL-1関数の2つを実装する必要がある。図12は、従来例1の実装法を示す回路図である。これは、暗号化処理と復号処理に応じて、FL関数6とFL-1関数7をセレクタ5で切り替えることができるハードウェアである。
【0016】
FL関数とFL-1関数の実装法の従来例2について以下に説明する。
【0017】
FL関数とFL-1関数の実装に関して、小型化を狙った実装法がある(例えば、特許文献1)。図13は、従来例2の実装法を示す回路図である。従来例2は、ANDゲート1cとORゲート2cをそれぞれ1個ずつのみ用いて実装する。つまり、2つの関数の共通部分であるANDゲートとORゲートの両方を共用化し、1つの関数にマージしている。
【0018】
従来例2の関数において、入力32bitの下位16bitのビット列とANDゲート1cの出力とは、XORゲート3eへ入力される。入力32bitの上位16bitのビット列とORゲート2cの出力とは、XORゲート3fへ入力される。入力32bitの上位16bitのビット列とXORゲート3fの出力とは、セレクタ5aへ入力される。入力32bitの下位16bitのビット列とXORゲート3eの出力とは、セレクタ5bへ入力される。セレクタ5aの出力と拡大鍵の上位16bitKLi1とは、ANDゲート1cへ入力される。セレクタ5bの出力と拡大鍵の下位16bitKLi2とは、ORゲート2cへ入力される。XORゲート3fの出力は、従来例2の関数の出力32bitの上位16ビットとなり、XORゲート3eの出力は、従来例2の関数の出力32bitの下位16ビットとなる。
【0019】
セレクタ5a,5bにおいて、2入力のうち、上部信号が選択された場合は、この関数はFL関数として機能し、下段信号が選択された場合は、FL-1関数として機能する。この技術を用いると、回路規模を大きく削減することが可能である。
【先行技術文献】
【特許文献】
【0020】
【特許文献1】特許第4128395号公報
【非特許文献】
【0021】
【非特許文献1】MISTY1仕様書,http://www.cryptrec.go.jp/cryptrec_03_spec_cypherlist_files/PDF/05_02jspec.pdf
【非特許文献2】E. Oswald and P. Rohatgi (Eds.): CHES 2008, LNCS 5154, pp. 315-330, International Association for Cryptologic Research 2008.
【非特許文献3】"Small and High-Speed Hardware Architectures for the 3GPP Standard Cipher KASUMI," Akashi Satoh and Sumio Morioka, Information Security Conference 2002.
【発明の概要】
【発明が解決しようとする課題】
【0022】
しかしながら、従来例2は、組み合わせ回路のフィードバックループを形成するという重大な問題点を抱えている。従来例2に示される通り、どちらの関数として機能する場合においても、経路中にレジスタが含まれない、且つ組み合わせ回路のみのループ構造を形成している。この構造が存在すると、ハードウェア記述言語から回路構造への変換作業である論理合成を行うことが非常に困難になる。仮に論理合成が可能となったとしても、変換後に生成された回路が発信回路になる危険性がある。そのため、信頼性という面において、上述のフィードバックループ構造をもつ回路は製品化不可能な実装法である。
【0023】
このように、FL関数とFL-1関数の機能を1つの関数としてマージしようとする場合、回路構成としてフィードバックループを形成せずに、回路規模の削減を実現することは容易ではない。そのため、従来のMISTY1、KASUMIに関する多くの特許出願や学術論文では、従来例1のように、FL関数とFL-1関数が独立に実装されている。
【0024】
本発明は上述した問題点を解決するためになされたものであり、フィードバックループの無い回路によって、FL関数とFL-1関数をマージした関数を実現する暗号処理装置を提供することを目的とする。
【課題を解決するための手段】
【0025】
上述した課題を解決するため、本発明の一態様は、暗号処理におけるFL関数及びFL-1関数の少なくともいずれかの演算を行うことができる暗号処理装置であって、ANDゲート及びORゲートのうちいずれか一方であって、暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、第1演算ゲートの出力と暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、ANDゲート及びORゲートのうち第1演算ゲートと異種のゲートであって、第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、第2演算ゲートの出力と第1入力ビット列とが入力される第2XORゲートと、ANDゲート及びORゲートのうち第1演算ゲートと同種のゲートであって、第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、第3演算ゲートの出力と第1XORゲートの出力とが入力される第3XORゲートとを有する。
【発明の効果】
【0026】
開示の暗号処理装置によれば、フィードバックループの無い回路によって、FL関数とFL-1関数をマージした関数を実現することができる。
【図面の簡単な説明】
【0027】
【図1】実施例1のマージ関数の構成の一例を示す回路図である。
【図2】実施例2のマージ関数の構成の一例を示す回路図である。
【図3】実施例3のマージ関数の構成の一例を示す回路図である。
【図4】実施例4のマージ関数の構成の一例を示す回路図である。
【図5】実施例5のマージ関数の構成の一例を示す回路図である。
【図6】実施例6のマージ関数の構成の一例を示す回路図である。
【図7】実施例7のマージ関数の構成の一例を示す回路図である。
【図8】各実施例の回路規模の一例を示す表である。
【図9】各実施例の遅延時間の一例を示す表である。
【図10】MISTY1ラウンド処理部の構成の一例を示す回路図である。
【図11】FL関数とFL-1関数の構成の一例を示す回路図である。
【図12】従来例1の実装法を示す回路図である。
【図13】従来例2の実装法を示す回路図である。
【発明を実施するための形態】
【0028】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【0029】
本発明は、MISTY1、MISTY2、KASUMI、CAMELLIAなど、FL関数とFL-1関数を採用する共通鍵暗号方式において、FL関数とFL-1関数を1つの関数として効率よくマージする新たな関数を用いることで、小型ハードウェアを実現する。本発明は、小型な共通鍵暗号ハードウェアを作る時に適用可能である。
【0030】
以下、MISTY1において、FL関数とFL-1関数を1つにマージしたマージ関数の例を示す。MISTY2やKASUMI、CAMELLIAなどに適用する場合も、基本的な考え方はMISTY1の場合と同様である。
【0031】
(実施例1)
図1は、実施例1のマージ関数の構成の一例を示す回路図である。上述したように、FL関数は、1段目がANDゲートで2段目がORゲートである、2段構造を持つ関数である。FL-1関数はその逆に、1段目がORゲートで2段目がANDゲートである、2段構造を持つ関数である。これに対して、本実施例のマージ関数は、3段構造を持つ関数である。本実施例のマージ関数は、1段目をANDゲート11a(第1演算ゲート)、2段目をORゲート12(第2演算ゲート)、3段目をANDゲート11b(第3演算ゲート)とし、2つの関数の共通部分をORゲート12のみとする。
【0032】
このマージ関数の入力32bitは、上位16bitの入力上位ビット列(第1入力ビット列)と下位16bitの入力下位ビット列(第2入力ビット列)に分割される。ここで、N=16とする。
【0033】
入力上位ビット列と拡大鍵の上位16bitであるKLi1とがANDゲート11aへ入力される。入力下位ビット列とANDゲート11aの出力がXORゲート13a(第1XORゲート)へ入力される。XORゲート13aの出力と入力下位ビット列とがセレクタ14a(第1セレクタ)へ入力される。
【0034】
セレクタ14aの出力と拡大鍵の下位16bitであるKLi2(第2拡大鍵ビット列)とがORゲート12へ入力される。入力上位ビット列とORゲート12の出力とがXORゲート13b(第2XORゲート)へ入力される。
【0035】
XORゲート13bの出力とKLi1とがANDゲート11bへ入力される。セレクタ14aの出力とANDゲート11bの出力とがXORゲート13c(第3XORゲート)へ入力される。XORゲート13cの出力とセレクタ14aの出力とがセレクタ14b(第2セレクタ)へ入力される。
【0036】
XORゲート13bの出力は、マージ関数の出力32bitの上位16bitとなる。セレクタ14bの出力は、マージ関数の出力32bitの下位16bitとなる。
【0037】
セレクタ14a,14bは、選択信号selにより2入力の一方を選択して出力する。マージ関数がFL関数の指示を受けた場合、セレクタ14aがXORゲート13aの出力を選択し、且つセレクタ14bがセレクタ14aの出力を選択することにより、このマージ関数は、FL関数として機能する。マージ関数がFL-1関数の指示を受けた場合、セレクタ14aが入力下位ビット列を選択し、且つセレクタ14bがXORゲート13cの出力を選択することにより、このマージ関数は、FL-1関数として機能する。
【0038】
このように、ANDゲートとORゲートの2つを共通部分とするのではなく、ORゲート12のみを共通部分とすることによって、フィードバックループの形成を回避することができる。
【0039】
1つの関数にマージしたことにより、16bitANDゲートと16bitXORゲート分の回路規模(56gate)が削減される。そのため、従来の従来例1の回路規模が0.18umプロセスで約336gateなのに対し、実施例1の回路規模は約280gateとなる。
【0040】
実施例1の回路規模を更に削減するために、実施例1におけるセレクタをANDゲートへと等価変換する。
【0041】
(実施例2)
図2は、実施例2のマージ関数の構成の一例を示す回路図である。この図において、図1と同一符号は図1に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例1のセレクタ14a,14bをそれぞれXORゲート13a,13cの入力側へと移動させてセレクタ15a(第3セレクタ),15b(第4セレクタ)とする。これによって、セレクタ15a,15bはそれぞれANDゲート11a,11bの出力信号、もしくは16bitの0信号のどちらかを選択するように変更できる。
【0042】
マージ関数がFL関数の指示を受けた場合、セレクタ15aがANDゲート11aの出力を選択し、且つセレクタ15bが0信号を選択することにより、このマージ関数は、FL関数として機能する。マージ関数がFL-1関数の指示を受けた場合、セレクタ15aが0信号を選択し、且つセレクタ15bがANDゲート11bの出力を選択することにより、このマージ関数は、FL-1関数として機能する。
【0043】
(実施例3)
図3は、実施例3のマージ関数の構成の一例を示す回路図である。この図において、図2と同一符号は図2に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例2におけるセレクタ15a,15bをそれぞれANDゲート16a(第1ANDゲート),16b(第2ANDゲート)に等価変換する。実施例2では、セレクタにおける選択信号selは1bitであるが、実施例3では16bitに拡張した信号である。
【0044】
ANDゲート16aは、ANDゲート11aの出力と選択信号selとのAND演算を行う。ANDゲート16bは、ANDゲート11bの出力と選択信号selの否定信号とのAND演算を行う。
【0045】
このようにセレクタをANDゲートに変換することにより、実施例1における回路規模をさらに削減することができる。
【0046】
(実施例4)
FL関数とFL-1関数を1つの関数としてマージを行うことにより、クリティカルパスが延長され、処理速度の低下を引き起こす場合がある。
【0047】
ここで、2−1NANDゲートの遅延をdとする。ANDゲート、ORゲート、XORゲート、セレクタをNANDゲートのみで構成する場合、各ゲートの遅延は、2d、2d、3d、3dとなる。
【0048】
従来例1のクリティカルパスは、FLもしくはFL-1の遅延が10d(FLにおける(1段目:AND−XOR)+(2段目:OR−XOR)、もしくはFL-1における(1段目:OR−XOR)+(2段目:AND−XOR)より(2d+3d)+(2d+3d)=10d)、FLとFL-1をセレクトするセレクタが3dのため、計13dとなる。
【0049】
一方、実施例2におけるクリティカルパスは、(1段目:AND−sel−XOR)+(2段目:OR−XOR)+(3段目:AND−sel−XOR)=(2d+3d+3d)+(2d+3d)+(2d+3d+3d)=21dとなる。
る。この理由は、従来例1では並列だったFL関数とFL-1関数に対して、実施例3では縦列の構造となっているためである。これを解決するために、実施例3で等価変換したANDゲートをクリティカルパス上から移動する。
【0050】
図4は、実施例4のマージ関数の構成の一例を示す回路図である。この図において、図3と同一符号は図3に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例3におけるANDゲート16a,16bをクリティカルパス上から移動してそれぞれANDゲート17a(第3ANDゲート),17b(第4ANDゲート)とする。
【0051】
ANDゲート17aは、選択信号selとKLi1とのAND演算を行う。ANDゲート17bは、選択信号selの否定信号とKLi1とのAND演算を行う。
【0052】
MISTY1では、拡大鍵であるKLijを生成するパスはクリティカルパスにならない。なぜなら、FL関数の処理サイクルより事前のサイクルでKLijを生成できる実装が多数知られており、これらの方法を用いることで、KLijの生成遅延時間の影響をFL関数の遅延時間に及ぼさない処理が可能であるからである。このMISTY1の性質を考慮することにより、実施例3のANDゲート16a,16bを本実施例のANDゲート17a,17bへ移動することができる。これにより、クリティカルパスの遅延がANDゲート2個分短縮される。つまり、(1段目:AND−XOR)+(2段目:OR−XOR)+(3段目:AND−XOR)=(2d+3d)+(2d+3d)+(2d+3d)=15dとなる。
【0053】
(実施例5)
図5は、実施例5のマージ関数の構成の一例を示す回路図である。この図において、図1と同一符号は図1に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、基本的な構成と効果が実施例1と同様であるが、ORゲート及びANDゲートの配置が実施例1と異なる。実施例1では、FL関数とFL-1関数の共通部分をORゲートとしたが、本実施例ではANDゲートを共通部分としている。つまり、本実施例のマージ関数は、1段目をORゲート21a(第1演算ゲート)、2段目をANDゲート22(第2演算ゲート)、3段目をORゲート21b(第3演算ゲート)とし、2つの関数の共通部分をANDゲート22のみとする。
【0054】
ORゲート21aの出力にXORゲート13aの入力が接続される。ANDゲート22の出力にXORゲート13bの入力が接続される。ORゲート21bの出力にXORゲート13cの入力が接続される。
【0055】
(実施例6)
図6は、実施例6のマージ関数の構成の一例を示す回路図である。この図において、図5と同一符号は図5に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例5のセレクタ14a,14bをそれぞれXORゲート13a,13cの入力側へと移動させてセレクタ15a,15bとする。本実施例は、基本的な構成と効果が実施例2と同様であるが、ORゲート及びANDゲートの配置が実施例2と異なる。
【0056】
(実施例7)
図7は、実施例7のマージ関数の構成の一例を示す回路図である。この図において、図6と同一符号は図6に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例6におけるセレクタ15a,15bをそれぞれANDゲート16a,16bに等価変換する。本実施例は、基本的な構成と効果が実施例3と同様であるが、ORゲート及びANDゲートの配置が実施例3と異なる。
【0057】
上述の各実施例の効果について以下に説明する。
【0058】
図8は、各実施例の回路規模の一例を示す表である。この表は、実施例1〜7と従来例1,2のそれぞれにおける回路規模の一例を示す。この表において、#1−bit MUXは、1−bit幅のセレクタの個数を示し、#1−bit AND/ORは、1−bit幅のANDゲート及びORゲートの個数を示し、#1−bit XORは、1−bit幅のXORゲートの個数を示し、Gate Countは、FL関数とFL-1関数に関する回路規模を示す。従来例1は、FL関数とFL-1関数をそれぞれ独立に持っており、これらを切り替えるセレクタも必要とするため、回路規模が336gateと大きくなっている。従来例2は、回路規模は小さくなっているものの、フィードバックループ構造を持つために製品化不可能な実装である。実施例1、2では従来例1と比較して、回路規模は削減されるものの、その効果は小さい。この理由は、セレクタの回路規模が同一だからである。実施例3、4では、この実施例1におけるセレクタをANDゲートへと等価変換することによって、200gateまで回路規模を削減している。
【0059】
以上より、従来例1と実施例4を比較すると、本発明により、FL関数とFL-1関数に関する回路規模が336gateから200gateへと約40%削減されることが見積もれた。
【0060】
従来の小型化されたMISTY1ハードウェア(0.18umプロセスで約4000gate、例えば、非特許文献2を参照)に実施例4を適用すると、約3.5%の回路規模の削減効果が期待できる。
【0061】
従来の小型化されたKASUMIハードウェア(0.13umプロセスで約3400gate:例えば、非特許文献3を参照)に実施例4を適用すると、最大で4%の回路規模の削減効果が期待できる。
【0062】
図9は、各実施例の遅延時間の一例を示す表である。この表は、実施例1〜7と従来例1,2のそれぞれにおける遅延時間の一例を示す。この表において、AND/ORは、マージ関数におけるANDゲート及びORゲートの数を示し、XORは、マージ関数におけるXORゲートの数を示し、2−1MUXは、マージ関数におけるセレクタの数を示し、遅延は、マージ関数の遅延時間を示す。従来例1では、遅延時間が13dであるが、実施例1では21dと大きく増加している。これは前述の通り、マージ関数が3段構造をとっており、さらに新たなセレクタがマージ関数の内部に生成されたためである。実施例3では、セレクタをANDゲートへと等価変換したことにより、2dだけ遅延時間が短縮されたものの、従来例1と比較すると大きい。実施例4において、クリティカルパス上からANDゲートを2つ分移動することにより、遅延時間が15dとなり、従来例1の13dとほぼ同等の遅延時間となる。
【0063】
実施例1、5によれば、ANDゲートとORゲートの2つを共通モジュールしてマージを行うのではなく、ANDゲート、もしくはORゲートのどちらか一方のみを共通モジュールとして、マージを行うことにより、フィードバックループの形成を回避することができる。
【0064】
実施例2、3、4、6、7によれば、回路規模の増加とクリティカルパス延長の原因となっているセレクタをANDゲートへと等価変換することによって、回路規模の削減を行い、さらにこのANDゲートをクリティカルパス以外の部分へと移動させることによって、クリティカルパスの短縮を図ることができる。
【0065】
上述の各実施例によれば、フィードバックループを形成せずに、大幅な回路規模の削減、ならびにクリティカルパスの延長を最大限に抑制する回路構造を実現する。
【0066】
実施例1〜4において、第1拡大鍵ビット列は、KLi1に基づくANDゲートの入力に対応し、第2拡大鍵ビット列は、KLi2に基づくORゲートの入力に対応する。実施例5〜7において、第1拡大鍵ビット列は、KLi2に基づくORゲートの入力に対応し、第2拡大鍵ビット列は、KLi1に基づくANDゲートの入力に対応する。
【0067】
本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。そのため、前述の実施の形態は、あらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には、何ら拘束されない。更に、特許請求の範囲の均等範囲に属する全ての変形、様々な改良、代替および改質は、全て本発明の範囲内のものである。
【0068】
以上の実施例1〜7を含む実施形態に関し、更に以下の付記を開示する。
(付記1)
暗号処理におけるFL関数及びFL-1関数の演算を行うことができる暗号処理装置であって、
ANDゲート及びORゲートのうちいずれか一方であって、前記暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、
前記第1演算ゲートの出力と前記暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと異種のゲートであって、前記第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、
前記第2演算ゲートの出力と前記第1入力ビット列とが入力される第2XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと同種のゲートであって、前記第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、
前記第3演算ゲートの出力と前記第1XORゲートの出力とが入力される第3XORゲートと、
を備える暗号処理装置。
(付記2)
更に、
選択信号に基づいて、前記第1XORゲートの出力と前記第2入力ビット列とのいずれかを選択して前記第2演算ゲート及び前記第3XORゲートへ出力する第1セレクタと、
前記選択信号に基づいて、前記第3XORゲートの出力と前記第1セレクタの出力とのいずれかを選択して出力する第2セレクタと、
を備える、
付記1に記載の暗号処理装置。
(付記3)
FL関数の指示を受けた前記第1セレクタは、前記第1XORゲートの出力を選択し、
FL関数の指示を受けた前記第2セレクタは、前記第1セレクタの出力を選択し、
FL-1関数の指示を受けた前記第1セレクタは、前記第2入力ビット列を選択し、
FL-1関数の指示を受けた前記第2セレクタは、前記第3XORゲートの出力を選択する、
付記2に記載の暗号処理装置。
(付記4)
更に、
選択信号に基づいて、前記第1演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第1XORゲートへ出力する第3セレクタと、
前記選択信号に基づいて、前記第3演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第3XORゲートへ出力する第4セレクタと、
を備える、
付記1に記載の暗号処理装置。
(付記5)
FL関数の指示を受けた前記第3セレクタは、前記第1演算ゲートの出力を選択し、
FL関数の指示を受けた前記第4セレクタは、前記Nビットの0信号を選択し、
FL-1関数の指示を受けた前記第3セレクタは、前記Nビットの0信号を選択し、
FL-1関数の指示を受けた前記第4セレクタは、前記第3演算ゲートの出力を選択する、
付記4に記載の暗号処理装置。
(付記6)
更に、
前記第1演算ゲートの出力と選択信号とのAND演算を行って前記第1XORゲートへ出力する第1ANDゲートと、
前記第3演算ゲートの出力と前記選択信号の否定信号とのAND演算を行って前記第3XORゲートへ出力する第3ANDゲートと、
を備える、
付記1に記載の暗号処理装置。
(付記7)
更に、
前記拡大鍵の上位Nビットと選択信号とのAND演算を行って前記第1演算ゲートへ出力する第3ANDゲートと、
前記拡大鍵の上位Nビットと前記選択信号の否定信号とのAND演算を行って前記第3演算ゲートへ出力する第4ANDゲートと、
を備え、
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
付記1に記載の暗号処理装置。
(付記8)
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
付記1に記載の暗号処理装置。
(付記9)
前記第1演算ゲート及び前記第3演算ゲートは、ORゲートであり、
前記第2演算ゲートは、ANDゲートである、
付記1に記載の暗号処理装置。
(付記10)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのMISTY1におけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記11)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのMISTY2におけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記12)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのKASUMIにおけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記13)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのCAMELLIAにおけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
【符号の説明】
【0069】
11a,11b,22,16a,16b,17a,17b ANDゲート
12,21a,21b ORゲート
13a,13b,13c XORゲート
14a,14b,15a,15b セレクタ
【技術分野】
【0001】
本発明は、ブロック暗号を処理するためのFL関数及びFL-1関数の少なくともいずれかの演算を行うことができる暗号処理装置に関するものである。
【背景技術】
【0002】
セキュリティシステムの基盤技術として、様々な暗号方式が利用されている。暗号方式は、公開鍵暗号方式と共通鍵暗号方式に大別される。公開鍵暗号方式とは、暗号化と復号で異なる鍵を用いる方式であり、暗号化を行うための鍵(公開鍵)を一般に公開する代わりに、暗号文を復号するための鍵(秘密鍵)を受信者のみの秘密情報とすることで安全性を保つ方式である。これに対し、共通鍵暗号方式と呼ばれるものは、暗号化と復号で同一の鍵(秘密鍵)を用いる方式であり、この秘密鍵を送信者と受信者以外の第三者にわからない情報とすることで安全性を保つ方式である。
【0003】
共通鍵方式の暗号(以下、共通鍵暗号と呼ぶ)は、公開鍵方式の暗号(以下、公開鍵暗号と呼ぶ)と比較した場合、処理速度が速くコンパクトに実装できるという利点がある。このため、携帯電話やICカードなどの小型機器に暗号化機能を付加する場合には、共通鍵暗号が利用される。また、処理速度が高速であり、情報をリアルタイムで暗号化/復号化できるので、放送や通信分野における情報通信にも利用されている。
【0004】
共通鍵暗号には、ストリーム暗号とブロック暗号がある。現時点では、安全性の観点から、共通鍵暗号にはブロック暗号が使用されている。ブロック暗号は、平文(暗号化の対象となる文)を一定のビット長のまとまり(これを、ブロックと呼ぶ)に分割し、ブロック単位で暗号化を行う。尚、暗号化の処理単位であるブロックのビット長は“ブロック長”と呼ばれる。
【0005】
共通鍵暗号方式のブロック暗号は、ブロック長に応じて様々なアルゴリズムが知られている。代表的なものとしては、DES、AES、SC2000、MISTY(MISTY1、MISTY2)、KASUMI、CAMELLIAなどがある。これらの共通鍵暗号のアルゴリズムは、ソフトウェアもしくはハードウェアにより実装される。
【0006】
共通鍵暗号のアルゴリズムの1つであるMISTY1(例えば、非特許文献1)について説明する。MISTY1は、秘密鍵を128bitとし、64bitを暗号化単位とするアルゴリズムである。すなわち64bitの平文から128bitの秘密鍵を用いて64bitの暗号文を生成する。以下では、MISTY1のラウンド処理部について述べる。
【0007】
図10は、MISTY1ラウンド処理部の構成の一例を示す回路図である。この図において、左側は、暗号化処理のラウンド処理部を示し、右側は、復号処理のラウンド処理部を示す。
【0008】
この図のMISTY1のラウンド処理部は、段数nが8の場合(非特許文献1において推奨値とされている)の処理を表している。MISTY1のラウンド処理部は、FO関数(FO1,FO2,FO3,FO4,FO5,FO6,FO7,FO8)とFL関数(FL1,FL2,FL3,FL4,FL5,FL6,FL7,FL8,FL9,FL10)またはFL-1関数(FL1-1,FL2-1,FL3-1,FL4-1,FL5-1,FL6-1,FL7-1,FL8-1,FL9-1,FL10-1)から構成されるフェイステル(Feistel)構造を有している。MISTY1の暗号化処理では、64bitの平文Pが入力され、フェイステル構造を経由することで暗号化が行われ、最終的に64bitの暗号文Cが出力される。復号処理では、64bitの暗号文Cが入力され、最終的に64bitの平文Pが出力される。
【0009】
以下では、FL関数とFL-1関数について説明する。
【0010】
図11は、FL関数とFL-1関数の構成の一例を示す回路図である。FL関数は、1段目がANDゲート1aで2段目がORゲート2aである。FL-1関数はその逆に、1段目がORゲート2bで2段目がANDゲート1bである。
【0011】
FL関数および、FL-1関数の入力32bitは、16bit毎の2つのデータに分割され、排他的論理和(XOR:Exclusive OR)、論理積(AND)、論理和(OR)によって変換が行われる。KLij(1≦i≦8,1≦j≦2)は、KLiの左からj番目の16bitデータである。ここで、KLiは拡大鍵のことであり、MISTY1では、拡大鍵処理を実行することで、128bitの秘密鍵Kから256bitの拡大鍵KLiを生成する。拡大鍵の生成法の詳細は非特許文献1に記されている。
【0012】
FL関数において、入力32bitの上位16bitのビット列と拡大鍵の上位16bitKLi1とは、ANDゲート1aへ入力される。入力32bitの下位16bitのビット列とANDゲート1aの出力とは、XORゲート3aへ入力される。XORゲート3aの出力と拡大鍵の下位16bitKLi2とは、ORゲート2aへ入力される。入力32bitの上位16bitのビット列とORゲート2aの出力とは、XORゲート3bへ入力される。XORゲート3bの出力は、FL関数の出力32bitの上位16ビットとなり、XORゲート3aの出力は、FL関数の出力32bitの下位16ビットとなる。
【0013】
FL-1関数において、入力32bitの下位16bitのビット列と拡大鍵の下位16bitKLi2とは、ORゲート2bへ入力される。入力32bitの上位16bitのビット列とORゲート2bの出力とは、XORゲート3cへ入力される。XORゲート3cの出力と拡大鍵の上位16bitKLi1とは、ANDゲート1bへ入力される。入力32bitの下位16bitのビット列とANDゲート1bの出力とは、XORゲート3dへ入力される。XORゲート3cの出力は、FL-1関数の出力32bitの上位16ビットとなり、XORゲート3dの出力は、FL-1関数の出力32bitの下位16ビットとなる。
【0014】
FL関数とFL-1関数の実装法の従来例1について以下に説明する。
【0015】
暗号化処理と復号処理の両方に対応したハードウェアを実装する場合、FL関数とFL-1関数の2つを実装する必要がある。図12は、従来例1の実装法を示す回路図である。これは、暗号化処理と復号処理に応じて、FL関数6とFL-1関数7をセレクタ5で切り替えることができるハードウェアである。
【0016】
FL関数とFL-1関数の実装法の従来例2について以下に説明する。
【0017】
FL関数とFL-1関数の実装に関して、小型化を狙った実装法がある(例えば、特許文献1)。図13は、従来例2の実装法を示す回路図である。従来例2は、ANDゲート1cとORゲート2cをそれぞれ1個ずつのみ用いて実装する。つまり、2つの関数の共通部分であるANDゲートとORゲートの両方を共用化し、1つの関数にマージしている。
【0018】
従来例2の関数において、入力32bitの下位16bitのビット列とANDゲート1cの出力とは、XORゲート3eへ入力される。入力32bitの上位16bitのビット列とORゲート2cの出力とは、XORゲート3fへ入力される。入力32bitの上位16bitのビット列とXORゲート3fの出力とは、セレクタ5aへ入力される。入力32bitの下位16bitのビット列とXORゲート3eの出力とは、セレクタ5bへ入力される。セレクタ5aの出力と拡大鍵の上位16bitKLi1とは、ANDゲート1cへ入力される。セレクタ5bの出力と拡大鍵の下位16bitKLi2とは、ORゲート2cへ入力される。XORゲート3fの出力は、従来例2の関数の出力32bitの上位16ビットとなり、XORゲート3eの出力は、従来例2の関数の出力32bitの下位16ビットとなる。
【0019】
セレクタ5a,5bにおいて、2入力のうち、上部信号が選択された場合は、この関数はFL関数として機能し、下段信号が選択された場合は、FL-1関数として機能する。この技術を用いると、回路規模を大きく削減することが可能である。
【先行技術文献】
【特許文献】
【0020】
【特許文献1】特許第4128395号公報
【非特許文献】
【0021】
【非特許文献1】MISTY1仕様書,http://www.cryptrec.go.jp/cryptrec_03_spec_cypherlist_files/PDF/05_02jspec.pdf
【非特許文献2】E. Oswald and P. Rohatgi (Eds.): CHES 2008, LNCS 5154, pp. 315-330, International Association for Cryptologic Research 2008.
【非特許文献3】"Small and High-Speed Hardware Architectures for the 3GPP Standard Cipher KASUMI," Akashi Satoh and Sumio Morioka, Information Security Conference 2002.
【発明の概要】
【発明が解決しようとする課題】
【0022】
しかしながら、従来例2は、組み合わせ回路のフィードバックループを形成するという重大な問題点を抱えている。従来例2に示される通り、どちらの関数として機能する場合においても、経路中にレジスタが含まれない、且つ組み合わせ回路のみのループ構造を形成している。この構造が存在すると、ハードウェア記述言語から回路構造への変換作業である論理合成を行うことが非常に困難になる。仮に論理合成が可能となったとしても、変換後に生成された回路が発信回路になる危険性がある。そのため、信頼性という面において、上述のフィードバックループ構造をもつ回路は製品化不可能な実装法である。
【0023】
このように、FL関数とFL-1関数の機能を1つの関数としてマージしようとする場合、回路構成としてフィードバックループを形成せずに、回路規模の削減を実現することは容易ではない。そのため、従来のMISTY1、KASUMIに関する多くの特許出願や学術論文では、従来例1のように、FL関数とFL-1関数が独立に実装されている。
【0024】
本発明は上述した問題点を解決するためになされたものであり、フィードバックループの無い回路によって、FL関数とFL-1関数をマージした関数を実現する暗号処理装置を提供することを目的とする。
【課題を解決するための手段】
【0025】
上述した課題を解決するため、本発明の一態様は、暗号処理におけるFL関数及びFL-1関数の少なくともいずれかの演算を行うことができる暗号処理装置であって、ANDゲート及びORゲートのうちいずれか一方であって、暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、第1演算ゲートの出力と暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、ANDゲート及びORゲートのうち第1演算ゲートと異種のゲートであって、第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、第2演算ゲートの出力と第1入力ビット列とが入力される第2XORゲートと、ANDゲート及びORゲートのうち第1演算ゲートと同種のゲートであって、第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、第3演算ゲートの出力と第1XORゲートの出力とが入力される第3XORゲートとを有する。
【発明の効果】
【0026】
開示の暗号処理装置によれば、フィードバックループの無い回路によって、FL関数とFL-1関数をマージした関数を実現することができる。
【図面の簡単な説明】
【0027】
【図1】実施例1のマージ関数の構成の一例を示す回路図である。
【図2】実施例2のマージ関数の構成の一例を示す回路図である。
【図3】実施例3のマージ関数の構成の一例を示す回路図である。
【図4】実施例4のマージ関数の構成の一例を示す回路図である。
【図5】実施例5のマージ関数の構成の一例を示す回路図である。
【図6】実施例6のマージ関数の構成の一例を示す回路図である。
【図7】実施例7のマージ関数の構成の一例を示す回路図である。
【図8】各実施例の回路規模の一例を示す表である。
【図9】各実施例の遅延時間の一例を示す表である。
【図10】MISTY1ラウンド処理部の構成の一例を示す回路図である。
【図11】FL関数とFL-1関数の構成の一例を示す回路図である。
【図12】従来例1の実装法を示す回路図である。
【図13】従来例2の実装法を示す回路図である。
【発明を実施するための形態】
【0028】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【0029】
本発明は、MISTY1、MISTY2、KASUMI、CAMELLIAなど、FL関数とFL-1関数を採用する共通鍵暗号方式において、FL関数とFL-1関数を1つの関数として効率よくマージする新たな関数を用いることで、小型ハードウェアを実現する。本発明は、小型な共通鍵暗号ハードウェアを作る時に適用可能である。
【0030】
以下、MISTY1において、FL関数とFL-1関数を1つにマージしたマージ関数の例を示す。MISTY2やKASUMI、CAMELLIAなどに適用する場合も、基本的な考え方はMISTY1の場合と同様である。
【0031】
(実施例1)
図1は、実施例1のマージ関数の構成の一例を示す回路図である。上述したように、FL関数は、1段目がANDゲートで2段目がORゲートである、2段構造を持つ関数である。FL-1関数はその逆に、1段目がORゲートで2段目がANDゲートである、2段構造を持つ関数である。これに対して、本実施例のマージ関数は、3段構造を持つ関数である。本実施例のマージ関数は、1段目をANDゲート11a(第1演算ゲート)、2段目をORゲート12(第2演算ゲート)、3段目をANDゲート11b(第3演算ゲート)とし、2つの関数の共通部分をORゲート12のみとする。
【0032】
このマージ関数の入力32bitは、上位16bitの入力上位ビット列(第1入力ビット列)と下位16bitの入力下位ビット列(第2入力ビット列)に分割される。ここで、N=16とする。
【0033】
入力上位ビット列と拡大鍵の上位16bitであるKLi1とがANDゲート11aへ入力される。入力下位ビット列とANDゲート11aの出力がXORゲート13a(第1XORゲート)へ入力される。XORゲート13aの出力と入力下位ビット列とがセレクタ14a(第1セレクタ)へ入力される。
【0034】
セレクタ14aの出力と拡大鍵の下位16bitであるKLi2(第2拡大鍵ビット列)とがORゲート12へ入力される。入力上位ビット列とORゲート12の出力とがXORゲート13b(第2XORゲート)へ入力される。
【0035】
XORゲート13bの出力とKLi1とがANDゲート11bへ入力される。セレクタ14aの出力とANDゲート11bの出力とがXORゲート13c(第3XORゲート)へ入力される。XORゲート13cの出力とセレクタ14aの出力とがセレクタ14b(第2セレクタ)へ入力される。
【0036】
XORゲート13bの出力は、マージ関数の出力32bitの上位16bitとなる。セレクタ14bの出力は、マージ関数の出力32bitの下位16bitとなる。
【0037】
セレクタ14a,14bは、選択信号selにより2入力の一方を選択して出力する。マージ関数がFL関数の指示を受けた場合、セレクタ14aがXORゲート13aの出力を選択し、且つセレクタ14bがセレクタ14aの出力を選択することにより、このマージ関数は、FL関数として機能する。マージ関数がFL-1関数の指示を受けた場合、セレクタ14aが入力下位ビット列を選択し、且つセレクタ14bがXORゲート13cの出力を選択することにより、このマージ関数は、FL-1関数として機能する。
【0038】
このように、ANDゲートとORゲートの2つを共通部分とするのではなく、ORゲート12のみを共通部分とすることによって、フィードバックループの形成を回避することができる。
【0039】
1つの関数にマージしたことにより、16bitANDゲートと16bitXORゲート分の回路規模(56gate)が削減される。そのため、従来の従来例1の回路規模が0.18umプロセスで約336gateなのに対し、実施例1の回路規模は約280gateとなる。
【0040】
実施例1の回路規模を更に削減するために、実施例1におけるセレクタをANDゲートへと等価変換する。
【0041】
(実施例2)
図2は、実施例2のマージ関数の構成の一例を示す回路図である。この図において、図1と同一符号は図1に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例1のセレクタ14a,14bをそれぞれXORゲート13a,13cの入力側へと移動させてセレクタ15a(第3セレクタ),15b(第4セレクタ)とする。これによって、セレクタ15a,15bはそれぞれANDゲート11a,11bの出力信号、もしくは16bitの0信号のどちらかを選択するように変更できる。
【0042】
マージ関数がFL関数の指示を受けた場合、セレクタ15aがANDゲート11aの出力を選択し、且つセレクタ15bが0信号を選択することにより、このマージ関数は、FL関数として機能する。マージ関数がFL-1関数の指示を受けた場合、セレクタ15aが0信号を選択し、且つセレクタ15bがANDゲート11bの出力を選択することにより、このマージ関数は、FL-1関数として機能する。
【0043】
(実施例3)
図3は、実施例3のマージ関数の構成の一例を示す回路図である。この図において、図2と同一符号は図2に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例2におけるセレクタ15a,15bをそれぞれANDゲート16a(第1ANDゲート),16b(第2ANDゲート)に等価変換する。実施例2では、セレクタにおける選択信号selは1bitであるが、実施例3では16bitに拡張した信号である。
【0044】
ANDゲート16aは、ANDゲート11aの出力と選択信号selとのAND演算を行う。ANDゲート16bは、ANDゲート11bの出力と選択信号selの否定信号とのAND演算を行う。
【0045】
このようにセレクタをANDゲートに変換することにより、実施例1における回路規模をさらに削減することができる。
【0046】
(実施例4)
FL関数とFL-1関数を1つの関数としてマージを行うことにより、クリティカルパスが延長され、処理速度の低下を引き起こす場合がある。
【0047】
ここで、2−1NANDゲートの遅延をdとする。ANDゲート、ORゲート、XORゲート、セレクタをNANDゲートのみで構成する場合、各ゲートの遅延は、2d、2d、3d、3dとなる。
【0048】
従来例1のクリティカルパスは、FLもしくはFL-1の遅延が10d(FLにおける(1段目:AND−XOR)+(2段目:OR−XOR)、もしくはFL-1における(1段目:OR−XOR)+(2段目:AND−XOR)より(2d+3d)+(2d+3d)=10d)、FLとFL-1をセレクトするセレクタが3dのため、計13dとなる。
【0049】
一方、実施例2におけるクリティカルパスは、(1段目:AND−sel−XOR)+(2段目:OR−XOR)+(3段目:AND−sel−XOR)=(2d+3d+3d)+(2d+3d)+(2d+3d+3d)=21dとなる。
る。この理由は、従来例1では並列だったFL関数とFL-1関数に対して、実施例3では縦列の構造となっているためである。これを解決するために、実施例3で等価変換したANDゲートをクリティカルパス上から移動する。
【0050】
図4は、実施例4のマージ関数の構成の一例を示す回路図である。この図において、図3と同一符号は図3に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例3におけるANDゲート16a,16bをクリティカルパス上から移動してそれぞれANDゲート17a(第3ANDゲート),17b(第4ANDゲート)とする。
【0051】
ANDゲート17aは、選択信号selとKLi1とのAND演算を行う。ANDゲート17bは、選択信号selの否定信号とKLi1とのAND演算を行う。
【0052】
MISTY1では、拡大鍵であるKLijを生成するパスはクリティカルパスにならない。なぜなら、FL関数の処理サイクルより事前のサイクルでKLijを生成できる実装が多数知られており、これらの方法を用いることで、KLijの生成遅延時間の影響をFL関数の遅延時間に及ぼさない処理が可能であるからである。このMISTY1の性質を考慮することにより、実施例3のANDゲート16a,16bを本実施例のANDゲート17a,17bへ移動することができる。これにより、クリティカルパスの遅延がANDゲート2個分短縮される。つまり、(1段目:AND−XOR)+(2段目:OR−XOR)+(3段目:AND−XOR)=(2d+3d)+(2d+3d)+(2d+3d)=15dとなる。
【0053】
(実施例5)
図5は、実施例5のマージ関数の構成の一例を示す回路図である。この図において、図1と同一符号は図1に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、基本的な構成と効果が実施例1と同様であるが、ORゲート及びANDゲートの配置が実施例1と異なる。実施例1では、FL関数とFL-1関数の共通部分をORゲートとしたが、本実施例ではANDゲートを共通部分としている。つまり、本実施例のマージ関数は、1段目をORゲート21a(第1演算ゲート)、2段目をANDゲート22(第2演算ゲート)、3段目をORゲート21b(第3演算ゲート)とし、2つの関数の共通部分をANDゲート22のみとする。
【0054】
ORゲート21aの出力にXORゲート13aの入力が接続される。ANDゲート22の出力にXORゲート13bの入力が接続される。ORゲート21bの出力にXORゲート13cの入力が接続される。
【0055】
(実施例6)
図6は、実施例6のマージ関数の構成の一例を示す回路図である。この図において、図5と同一符号は図5に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例5のセレクタ14a,14bをそれぞれXORゲート13a,13cの入力側へと移動させてセレクタ15a,15bとする。本実施例は、基本的な構成と効果が実施例2と同様であるが、ORゲート及びANDゲートの配置が実施例2と異なる。
【0056】
(実施例7)
図7は、実施例7のマージ関数の構成の一例を示す回路図である。この図において、図6と同一符号は図6に示された対象と同一又は相当物を示しており、ここでの説明を省略する。本実施例は、実施例6におけるセレクタ15a,15bをそれぞれANDゲート16a,16bに等価変換する。本実施例は、基本的な構成と効果が実施例3と同様であるが、ORゲート及びANDゲートの配置が実施例3と異なる。
【0057】
上述の各実施例の効果について以下に説明する。
【0058】
図8は、各実施例の回路規模の一例を示す表である。この表は、実施例1〜7と従来例1,2のそれぞれにおける回路規模の一例を示す。この表において、#1−bit MUXは、1−bit幅のセレクタの個数を示し、#1−bit AND/ORは、1−bit幅のANDゲート及びORゲートの個数を示し、#1−bit XORは、1−bit幅のXORゲートの個数を示し、Gate Countは、FL関数とFL-1関数に関する回路規模を示す。従来例1は、FL関数とFL-1関数をそれぞれ独立に持っており、これらを切り替えるセレクタも必要とするため、回路規模が336gateと大きくなっている。従来例2は、回路規模は小さくなっているものの、フィードバックループ構造を持つために製品化不可能な実装である。実施例1、2では従来例1と比較して、回路規模は削減されるものの、その効果は小さい。この理由は、セレクタの回路規模が同一だからである。実施例3、4では、この実施例1におけるセレクタをANDゲートへと等価変換することによって、200gateまで回路規模を削減している。
【0059】
以上より、従来例1と実施例4を比較すると、本発明により、FL関数とFL-1関数に関する回路規模が336gateから200gateへと約40%削減されることが見積もれた。
【0060】
従来の小型化されたMISTY1ハードウェア(0.18umプロセスで約4000gate、例えば、非特許文献2を参照)に実施例4を適用すると、約3.5%の回路規模の削減効果が期待できる。
【0061】
従来の小型化されたKASUMIハードウェア(0.13umプロセスで約3400gate:例えば、非特許文献3を参照)に実施例4を適用すると、最大で4%の回路規模の削減効果が期待できる。
【0062】
図9は、各実施例の遅延時間の一例を示す表である。この表は、実施例1〜7と従来例1,2のそれぞれにおける遅延時間の一例を示す。この表において、AND/ORは、マージ関数におけるANDゲート及びORゲートの数を示し、XORは、マージ関数におけるXORゲートの数を示し、2−1MUXは、マージ関数におけるセレクタの数を示し、遅延は、マージ関数の遅延時間を示す。従来例1では、遅延時間が13dであるが、実施例1では21dと大きく増加している。これは前述の通り、マージ関数が3段構造をとっており、さらに新たなセレクタがマージ関数の内部に生成されたためである。実施例3では、セレクタをANDゲートへと等価変換したことにより、2dだけ遅延時間が短縮されたものの、従来例1と比較すると大きい。実施例4において、クリティカルパス上からANDゲートを2つ分移動することにより、遅延時間が15dとなり、従来例1の13dとほぼ同等の遅延時間となる。
【0063】
実施例1、5によれば、ANDゲートとORゲートの2つを共通モジュールしてマージを行うのではなく、ANDゲート、もしくはORゲートのどちらか一方のみを共通モジュールとして、マージを行うことにより、フィードバックループの形成を回避することができる。
【0064】
実施例2、3、4、6、7によれば、回路規模の増加とクリティカルパス延長の原因となっているセレクタをANDゲートへと等価変換することによって、回路規模の削減を行い、さらにこのANDゲートをクリティカルパス以外の部分へと移動させることによって、クリティカルパスの短縮を図ることができる。
【0065】
上述の各実施例によれば、フィードバックループを形成せずに、大幅な回路規模の削減、ならびにクリティカルパスの延長を最大限に抑制する回路構造を実現する。
【0066】
実施例1〜4において、第1拡大鍵ビット列は、KLi1に基づくANDゲートの入力に対応し、第2拡大鍵ビット列は、KLi2に基づくORゲートの入力に対応する。実施例5〜7において、第1拡大鍵ビット列は、KLi2に基づくORゲートの入力に対応し、第2拡大鍵ビット列は、KLi1に基づくANDゲートの入力に対応する。
【0067】
本発明は、その精神または主要な特徴から逸脱することなく、他の様々な形で実施することができる。そのため、前述の実施の形態は、あらゆる点で単なる例示に過ぎず、限定的に解釈してはならない。本発明の範囲は、特許請求の範囲によって示すものであって、明細書本文には、何ら拘束されない。更に、特許請求の範囲の均等範囲に属する全ての変形、様々な改良、代替および改質は、全て本発明の範囲内のものである。
【0068】
以上の実施例1〜7を含む実施形態に関し、更に以下の付記を開示する。
(付記1)
暗号処理におけるFL関数及びFL-1関数の演算を行うことができる暗号処理装置であって、
ANDゲート及びORゲートのうちいずれか一方であって、前記暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、
前記第1演算ゲートの出力と前記暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと異種のゲートであって、前記第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、
前記第2演算ゲートの出力と前記第1入力ビット列とが入力される第2XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと同種のゲートであって、前記第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、
前記第3演算ゲートの出力と前記第1XORゲートの出力とが入力される第3XORゲートと、
を備える暗号処理装置。
(付記2)
更に、
選択信号に基づいて、前記第1XORゲートの出力と前記第2入力ビット列とのいずれかを選択して前記第2演算ゲート及び前記第3XORゲートへ出力する第1セレクタと、
前記選択信号に基づいて、前記第3XORゲートの出力と前記第1セレクタの出力とのいずれかを選択して出力する第2セレクタと、
を備える、
付記1に記載の暗号処理装置。
(付記3)
FL関数の指示を受けた前記第1セレクタは、前記第1XORゲートの出力を選択し、
FL関数の指示を受けた前記第2セレクタは、前記第1セレクタの出力を選択し、
FL-1関数の指示を受けた前記第1セレクタは、前記第2入力ビット列を選択し、
FL-1関数の指示を受けた前記第2セレクタは、前記第3XORゲートの出力を選択する、
付記2に記載の暗号処理装置。
(付記4)
更に、
選択信号に基づいて、前記第1演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第1XORゲートへ出力する第3セレクタと、
前記選択信号に基づいて、前記第3演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第3XORゲートへ出力する第4セレクタと、
を備える、
付記1に記載の暗号処理装置。
(付記5)
FL関数の指示を受けた前記第3セレクタは、前記第1演算ゲートの出力を選択し、
FL関数の指示を受けた前記第4セレクタは、前記Nビットの0信号を選択し、
FL-1関数の指示を受けた前記第3セレクタは、前記Nビットの0信号を選択し、
FL-1関数の指示を受けた前記第4セレクタは、前記第3演算ゲートの出力を選択する、
付記4に記載の暗号処理装置。
(付記6)
更に、
前記第1演算ゲートの出力と選択信号とのAND演算を行って前記第1XORゲートへ出力する第1ANDゲートと、
前記第3演算ゲートの出力と前記選択信号の否定信号とのAND演算を行って前記第3XORゲートへ出力する第3ANDゲートと、
を備える、
付記1に記載の暗号処理装置。
(付記7)
更に、
前記拡大鍵の上位Nビットと選択信号とのAND演算を行って前記第1演算ゲートへ出力する第3ANDゲートと、
前記拡大鍵の上位Nビットと前記選択信号の否定信号とのAND演算を行って前記第3演算ゲートへ出力する第4ANDゲートと、
を備え、
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
付記1に記載の暗号処理装置。
(付記8)
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
付記1に記載の暗号処理装置。
(付記9)
前記第1演算ゲート及び前記第3演算ゲートは、ORゲートであり、
前記第2演算ゲートは、ANDゲートである、
付記1に記載の暗号処理装置。
(付記10)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのMISTY1におけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記11)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのMISTY2におけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記12)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのKASUMIにおけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
(付記13)
前記第1演算ゲート、前記第1XORゲート、前記第2ゲート、前記第2XORゲート、前記演算第3ゲート、前記第3XORゲートは、共通鍵暗号のアルゴリズムのCAMELLIAにおけるFL関数及びFL-1関数に設けられる、
付記1に記載の暗号処理装置。
【符号の説明】
【0069】
11a,11b,22,16a,16b,17a,17b ANDゲート
12,21a,21b ORゲート
13a,13b,13c XORゲート
14a,14b,15a,15b セレクタ
【特許請求の範囲】
【請求項1】
暗号処理におけるFL関数及びFL-1関数の演算を行うことができる暗号処理装置であって、
ANDゲート及びORゲートのうちいずれか一方であって、前記暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、
前記第1演算ゲートの出力と前記暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと異種のゲートであって、前記第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、
前記第2演算ゲートの出力と前記第1入力ビット列とが入力される第2XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと同種のゲートであって、前記第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、
前記第3演算ゲートの出力と前記第1XORゲートの出力とが入力される第3XORゲートと、
を備える暗号処理装置。
【請求項2】
更に、
選択信号に基づいて、前記第1XORゲートの出力と前記第2入力ビット列とのいずれかを選択して前記第2演算ゲート及び前記第3XORゲートへ出力する第1セレクタと、
前記選択信号に基づいて、前記第3XORゲートの出力と前記第1セレクタの出力とのいずれかを選択して出力する第2セレクタと、
を備える、
請求項1に記載の暗号処理装置。
【請求項3】
更に、
選択信号に基づいて、前記第1演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第1XORゲートへ出力する第3セレクタと、
前記選択信号に基づいて、前記第3演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第3XORゲートへ出力する第4セレクタと、
を備える、
請求項1に記載の暗号処理装置。
【請求項4】
更に、
前記第1演算ゲートの出力と選択信号とのAND演算を行って前記第1XORゲートへ出力する第1ANDゲートと、
前記第3演算ゲートの出力と前記選択信号の否定信号とのAND演算を行って前記第3XORゲートへ出力する第3ANDゲートと、
を備える、
請求項1に記載の暗号処理装置。
【請求項5】
更に、
前記拡大鍵の上位Nビットと選択信号とのAND演算を行って前記第1演算ゲートへ出力する第3ANDゲートと、
前記拡大鍵の上位Nビットと前記選択信号の否定信号とのAND演算を行って前記第3演算ゲートへ出力する第4ANDゲートと、
を備え、
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
請求項1に記載の暗号処理装置。
【請求項1】
暗号処理におけるFL関数及びFL-1関数の演算を行うことができる暗号処理装置であって、
ANDゲート及びORゲートのうちいずれか一方であって、前記暗号処理装置の入力の2Nビットのうち上位Nビットである第1入力ビット列と拡大鍵の上位Nビット及び下位Nビットのいずれか一方に基づく第1拡大鍵ビット列とが入力される第1演算ゲートと、
前記第1演算ゲートの出力と前記暗号処理装置の入力の2Nビットのうち下位Nビットである第2入力ビット列とが入力される第1XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと異種のゲートであって、前記第1XORゲートの出力と前記拡大鍵の上位Nビット及び下位Nビットのいずれか他方に基づく第2拡大鍵ビット列とが入力される第2演算ゲートと、
前記第2演算ゲートの出力と前記第1入力ビット列とが入力される第2XORゲートと、
ANDゲート及びORゲートのうち前記第1演算ゲートと同種のゲートであって、前記第2XORゲートの出力と前記第1拡大鍵ビット列とが入力される第3演算ゲートと、
前記第3演算ゲートの出力と前記第1XORゲートの出力とが入力される第3XORゲートと、
を備える暗号処理装置。
【請求項2】
更に、
選択信号に基づいて、前記第1XORゲートの出力と前記第2入力ビット列とのいずれかを選択して前記第2演算ゲート及び前記第3XORゲートへ出力する第1セレクタと、
前記選択信号に基づいて、前記第3XORゲートの出力と前記第1セレクタの出力とのいずれかを選択して出力する第2セレクタと、
を備える、
請求項1に記載の暗号処理装置。
【請求項3】
更に、
選択信号に基づいて、前記第1演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第1XORゲートへ出力する第3セレクタと、
前記選択信号に基づいて、前記第3演算ゲートの出力と前記Nビットの0信号とのいずれかを選択して前記第3XORゲートへ出力する第4セレクタと、
を備える、
請求項1に記載の暗号処理装置。
【請求項4】
更に、
前記第1演算ゲートの出力と選択信号とのAND演算を行って前記第1XORゲートへ出力する第1ANDゲートと、
前記第3演算ゲートの出力と前記選択信号の否定信号とのAND演算を行って前記第3XORゲートへ出力する第3ANDゲートと、
を備える、
請求項1に記載の暗号処理装置。
【請求項5】
更に、
前記拡大鍵の上位Nビットと選択信号とのAND演算を行って前記第1演算ゲートへ出力する第3ANDゲートと、
前記拡大鍵の上位Nビットと前記選択信号の否定信号とのAND演算を行って前記第3演算ゲートへ出力する第4ANDゲートと、
を備え、
前記第1演算ゲート及び前記第3演算ゲートは、ANDゲートであり、
前記第2演算ゲートは、ORゲートである、
請求項1に記載の暗号処理装置。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図12】
【図13】
【公開番号】特開2010−164792(P2010−164792A)
【公開日】平成22年7月29日(2010.7.29)
【国際特許分類】
【出願番号】特願2009−7249(P2009−7249)
【出願日】平成21年1月16日(2009.1.16)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
【公開日】平成22年7月29日(2010.7.29)
【国際特許分類】
【出願日】平成21年1月16日(2009.1.16)
【出願人】(000005223)富士通株式会社 (25,993)
【Fターム(参考)】
[ Back to top ]