説明

データ変換装置、およびデータ変換方法、並びにプログラム

【課題】圧縮関数実行部の改善された構成を実現する。
【解決手段】メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力してデータ圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。

【発明の詳細な説明】
【技術分野】
【0001】
本発明は、データ変換装置、およびデータ変換方法、並びにプログラムに関する。さらに詳細には、例えば入力メッセージデータに対するハッシュ値生成処理を行うデータ変換装置、およびデータ変換方法、並びにプログラムに関する。
【背景技術】
【0002】
暗号処理などのデータ変換処理においては、入力データに対するハッシュ処理を実行するハッシュ関数が用いられる場合が多い。ハッシュ関数は与えられたメッセージに対して固定長の長さの圧縮値(ダイジェスト)を計算するための関数である。すでに知られているハッシュ関数としては128ビットの出力値を持つMD5や、160ビットの出力値を持つSHA−1、さらに256ビットの出力値を持つSHA−256などがある。
【0003】
例えば解析困難性を高める要請等に基づいて、ハッシュ関数には以下のような耐性が求められる。
原像計算困難性(Preimage Resistance)
第二原像計算困難性(2nd Preimage Resistance)
衝突計算困難性(Collision Resistance)
【0004】
これらの耐性について簡単に説明する。
入力をx、ハッシュ関数をhとしてy=h(x)を出力とするハッシュ関数において、
原像計算困難性は、出力yについてh(x)=yとなる入力xを計算する困難性に相当する。
第二原像計算困難性は、1つの入力値xが既知のとき、h(x')=h(x)を満たす異なる入力値x'を見つけることの困難性に相当する。
衝突計算困難性は、h(x')=h(x)を満たす2つの異なる入力値x、x'を見つけることの困難性に相当する。
これらの困難性が高いほど、安全性の高いハッシュ関数であると言える。
【0005】
従来から、利用されてきたハッシュ関数は、近年の解析方法の発展により、上記の耐性についての脆弱性が明らかになってきている。例えば、これまでハッシュ関数として多く利用されてきたMD5やSHA−1などは衝突計算困難性(Collision Resistance)が多くのシステム要求レベルを満足していないことが明らかになってきている。また、既存のハッシュ関数として比較的長い出力長を持つSHA−256などがあるが、このSHA256もSHA−1の設計方針を踏襲していることから安全性上の不安が残り、別の設計方針に基づく、安全性の高いハッシュ関数の登場が望まれている。
【発明の開示】
【発明が解決しようとする課題】
【0006】
本発明は、上記問題点に鑑みてなされたものであり、安全性が高く処理効率の高いハッシュ関数を実現するデータ変換装置、およびデータ変換方法、並びにプログラムを提供することを目的とする。
【課題を解決するための手段】
【0007】
本発明の第1の側面は、
メッセージデータを入力してハッシュ値を生成するデータ変換部を有し、
前記データ変換部は、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行する構成であり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う構成であり、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成であるデータ変換装置にある。
【0008】
さらに、本発明のデータ変換装置の一実施態様において、前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一のメッセージスケジュール部を複数の圧縮関数実行部で共有した共有メッセージスケジュール部を有し、前記共有メッセージスケジュール部は、前記メッセージデータの分割データを入力してメッセージスケジュール処理により生成した出力データを複数の連鎖値処理部に出力する構成であり、前記複数の連鎖値処理部は、前記共有メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する処理を並列に実行する構成である。
【0009】
さらに、本発明のデータ変換装置の一実施態様において、前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一の連鎖値処理部を複数の圧縮関数実行部で共有した共有連鎖値処理部を有し、並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データを前記共有連鎖値処理部に出力する構成であり、前記共有連鎖値処理部は、前記複数のメッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する構成である。
【0010】
さらに、本発明のデータ変換装置の一実施態様において、前記並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データの排他的論理和演算結果を前記共有連鎖値処理部に出力する構成である。
【0011】
さらに、本発明のデータ変換装置の一実施態様において、前記メッセージスケジュール部は、置換処理を繰り返し実行し、各置換処理結果を中間値として出力する構成を持つ中間出力付き置換関数実行部によって構成され、前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力を付加入力として、置換処理を繰り返し実行する付加入力付き置換関数実行部を有する構成である。
【0012】
さらに、本発明のデータ変換装置の一実施態様において、前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力と前段の置換処理結果との排他的論理和結果を次の置換処理の入力データとして設定する構成である。
【0013】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々は、入力データの少なくとも一部データに対する非線形変換処理と、データ入れ替え処理としてのスワップ処理とを含む構成である。
【0014】
さらに、本発明のデータ変換装置の一実施態様において、前記非線形変換処理は、コンスタント(定数)を適用した排他的論理和演算と、非線形変換処理と、線形変換行列を適用した線形変換処理を含む処理である。
【0015】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々において行われる線形変換処理は、複数の異なる行列を適用するDSM(Diffusion Switching Mechanism)に従った処理として実行する構成である。
【0016】
さらに、本発明のデータ変換装置の一実施態様において、前記置換関数実行部の実行する複数の置換処理の各々は、それぞれ異なるコンスタント(定数)集合を入力したデータ処理を行う構成であり、1つの置換処理に適用するコンスタント集合を基本集合として、該基本集合に対するデータ変換により生成した異なるコンスタント集合を各置換処理に適用する構成である。
【0017】
さらに、本発明のデータ変換装置の一実施態様において、前記基本集合となるコンスタント集合は、異なる複数の初期値S,Tに対して予め設定した変換ルールを適用して生成した複数のコンスタントから構成され、前記変換ルールは、前記初期値に対して、
S←S・x、T←T・x
ただしa≠b
とする更新処理を含む構成である。
【0018】
さらに、本発明のデータ変換装置の一実施態様において、前記基本集合に対するデータ変換処理は、前記基本集合を構成するコンスタントの構成ビットのローテーション処理、または、予め規定したマスクデータとの演算処理である。
【0019】
さらに、本発明のデータ変換装置の一実施態様において、前記データ変換部は、最終的に出力するハッシュ値のビット数削減処理として切り詰め処理を行う構成を有し、前記データ変換部の出力部を構成する複数のデータ出力系列各々の出力ビットに対するビット削減数を、予め規定した算出式に従って算出し、算出結果に従った切り詰め処理を実行する構成である。
【0020】
さらに、本発明のデータ変換装置の一実施態様において、前記データ変換部は、さらに、入力データに対するデータ攪拌処理を実行する攪拌処理部を有し、前記複数の圧縮関数実行部は、前記メッセージデータの分割データのすべてを入力可能とした複数段の圧縮関数実行部として構成され、前記複数段の圧縮関数実行部の一部は、前記攪拌処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、前記複数段の圧縮関数実行部の一部は、前段の圧縮処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、前記複数段の圧縮関数実行部の最終段の圧縮処理部は、前記メッセージデータのハッシュ値を出力する構成である。
【0021】
さらに、本発明の第2側面は、
データ変換装置において実行するデータ変換処理方法であり、
データ変換部が、メッセージデータを入力してハッシュ値を生成するデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行するステップであり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行ない、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行うデータ変換方法にある。
【0022】
さらに、本発明の第3の側面は、
データ変換装置においてデータ変換処理を実行させるプログラムであり、
データ変換部に、メッセージデータを入力してハッシュ値を生成させるデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行させるステップであり、
前記プログラムは、前記複数の圧縮関数実行部の各々に、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を実行させ、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部に、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有させて、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行わせるプログラムにある。
【0023】
なお、本発明のプログラムは、例えば、様々なプログラム・コードを実行可能な汎用システムに対して、コンピュータ可読な形式で提供する記憶媒体、通信媒体によって提供可能なプログラムである。このようなプログラムをコンピュータ可読な形式で提供することにより、コンピュータ・システム上でプログラムに応じた処理が実現される。
【0024】
本発明のさらに他の目的、特徴や利点は、後述する本発明の実施例や添付する図面に基づくより詳細な説明によって明らかになるであろう。なお、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【発明の効果】
【0025】
本発明の一実施例においては、メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する構成を有する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力し入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成とした。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【発明を実施するための最良の形態】
【0026】
以下、図面を参照しながら本発明のデータ変換装置、およびデータ変換方法、並びにプログラムの詳細について説明する。
【0027】
説明は、以下の項目順に行う。
1.定義域拡張法
2.出力サイズを拡大する新しい定義域拡張法
3.新しい定義域拡張法の処理効率向上法
4.攪拌関数Fの実現方法
5.定義域拡大法の一般化
6.攪拌関数Fの構成の一般化
7.異なる圧縮関数の利用について
8.圧縮関数の内部処理の効率的な実現法
9.入力メッセージ長の拡張法
10.CV処理部とMS部に繰り返し型置換を利用したハッシュ関数実現法
11.MS部のサイズ拡大法
12.CV処理部のサイズ拡大法
13.CV処理部とMS部のサイズ拡大法
14.定義域拡大法用の攪拌関数Fの構成法
15.拡散性能の高い置換処理実現方法
16.独立性の高い出力をもつ置換関数の生成法
17.置換関数に適用するコンスタントの生成処理
18.複数の全体置換に対するコンスタントの生成法
19.ハッシュ関数の出力値の切り詰め手法
20.データ変換装置の構成例
【0028】
[1.定義域拡張法]
先に説明したように、ハッシュ関数実行部は上述した各種の耐性、すなわち、
原像計算困難性(Preimage Resistance)
第二原像計算困難性(2nd Preimage Resistance)
衝突計算困難性(Collision Resistance)
これらの耐性を備えたものであることが要請される。
【0029】
なお、本発明のデータ変換装置は、以下において説明するハッシュ関数実行部や、圧縮関数実行部等、各種の関数実行部を有する。以下の説明において、単に[〜関数]として表記としているものは、本発明のデータ変換装置においては、各関数を実行する関数実行部において実行される。なお、関数実行部は、ハードウェアまたはソフトウェア、あるいは両者を用いて実現される。
【0030】
ハッシュ関数は、与えられたメッセージに対して固定長の長さの圧縮値(ダイジェスト)を計算する圧縮関数(Compression Function)を利用している。ハッシュ関数を実行するハードウェアやソフトウェアからなるハッシュ処理部を構築する際には、上述した各種の耐性を考慮した構成とすることが要求される。ハッシュ処理部の構成は大きく2つの階層に分けることができる。
(1)第1階層は、定義域拡張(Domain Extension)」部分、
(2)第2階層は、圧縮関数の内部構成、
これらの2つの階層である。
【0031】
定義域とは、ハッシュ関数の入力値として許容可能なビットサイズ(入力サイズ)である。1つの圧縮関数実行部は固定長の入力値を固定長の出力値に変換する処理を行うが、一般的に1つの圧縮関数実行部では、許容可能な入力ビットサイズが小さく、ビッサイズの大きな入力値は処理できない、従って、複数の圧縮関数を接続して任意長のメッセージ入力を取り扱うように拡張することが行われる。このような処理により、ビット長の長い入力データのハッシュ処理が可能となる。定義域拡張(Domain Extension)」処理とはこのような処理である。
【0032】
この第1階層としての定義域拡張構成や、第2階層としての圧縮関数の内部構成が上述した耐性のレベルを左右することになる。
【0033】
はじめに、ここでは前者の定義域拡張処理についての新しい方式について説明する。圧縮関数は、入力値のビット列を、入力ビット長より短い長さのビット列に変換する関数である。図1は圧縮処理部としての圧縮関数(f)を図で表したものである。
【0034】
図1に示す圧縮関数10は、入力値としてのX:aビットと、初期値Y:bビットの計a+bビットを入力して、bビット値の出力Zを出力する関数である。圧縮関数の入力値として許容可能なビットサイズは定義域(入力サイズ)と呼ばれる。1つの圧縮関数10単独では長い入力メッセージを取り扱うことができないので、圧縮関数同士を適切に接続することで定義域(入力サイズ)の拡張を行い入力メッセージサイズの拡大を図ることができる。すなわち長いビット長を持つデータを入力することが可能となる。
【0035】
図2は代表的な定義域拡張法であるメッセージパディング付きのMD構成(Merkle−Damgard Construction)を表したものである。なお、この構成については、例えば、[参考文献:R.Merkle,"One way hash functions and des."in Proceedings of Crypto'89(G.Brassard,ed.),no.435 in LNCS,pp.428−446,Springer−Verlag,1989.
I.Damgard,"A design principle for hash functions."in Proceedings of Crypto'89(G. Brassard,ed.),no.435 in LNCS,pp.417−427,Springer−Verlag,1989.)]
【0036】
MD構成は図2のように圧縮関数(f)を直列に並べて、入力サイズを拡大することを可能とした構成である。入力メッセージは、ビット長調整のためのビットデータ付与処理として行われるパディング(Padding)処理により圧縮関数のメッセージ入力部サイズであるaビットの整数倍の値になるように補正される。パディング処理後の入力メッセージをaビット単位に分割したものをM,M,M,・・・,Mn−2,Mn−1|Paddingとする。[Mn−1|Padding]は、入力メッセージの末尾データ[Mn−1]に付加ビットとしてパディングデータを付加して入力ビットサイズをaビットにしているデータである。
【0037】
メッセージに対するダイジェストを作るためには、あらかじめ決められたbビットの初期値IV(Initial Value)と第一の分割メッセージMとを、圧縮関数11に入力して圧縮してbビットの値を中間値として出力し、その中間値出力との続くメッセージとを圧縮関数12に入力して圧縮するという動作を、複数の圧縮関数を用いて繰り返すことで最終的にハッシュ値(H)を得る構成である。このときの中間値は、連鎖値(Chaining Variable)と呼ばれる。
【0038】
この構成は、個々の圧縮関数自体にCollision Resistance(衝突耐性)が存在していれば、ハッシュ関数全体の衝突耐性があることを示すことができることが知られており、実際のハッシュ関数によく用いられている構成である。この構成を利用した代表的なハッシュ関数としてMD5やSHA−1がある。
【0039】
[2.出力サイズを拡大する新しい定義域拡張法]
上記構成ではbビットの出力の場合について説明したが、次に、長いビット長の2bビットのハッシュ値を生成するハッシュ関数の構成について考える。
【0040】
上記のMD構成をそのまま利用する場合には2bビットの出力をもつ圧縮関数を準備する必要がある。しかし一般的には大きいサイズの出力をもつ安全性の高い圧縮関数を新たに生成することは難しい。新たな圧縮関数を設計して安全性を評価する必要があり、この設計や評価は、サイズが大きくなればその困難性が増加する。従って、すでに評価がなされているbビット出力の圧縮関数を使って2bビット出力のハッシュ関数を構成できることが望ましい。
【0041】
出力ビットサイズが小さい圧縮関数を利用して出力ビットサイズの大きいハッシュ値を実現する従来技術としては、カスケードハッシュ(cascading hash)構成が知られている。カスケードハッシュ構成について図3を参照して説明する。
【0042】
カスケードハッシュ構成は2つの圧縮関数を並列に用いて出力サイズの大きなハッシュ値を出力可能とした構成である。図3に示すように、カスケードハッシュは単純に2つの圧縮関数f,fを並列に並べたものである。この構成により、2bビットの出力を持つハッシュ関数を構成することが可能となる。
【0043】
しかしながら、このようなbビット出力の圧縮関数を2つ並べて2bビット出力を実行させるハッシュ関数の安全性は2bビットの出力サイズを持つハッシュ関数に求められるレベルを達成していない。あくまで、bビット分の出力サイズをもつハッシュ関数と同程度の安全性しかないことが知られている。このことは、例えば、以下の文献に記載されている。[A.Joux,"Multicollisions in iterated hash functions.application to cascaded constructions." in Proceedings of Crypto'04(M.Franklin,ed.),no.3152 in LNCS, p.306−316,Springer−Verlag,2004.]
【0044】
次に、本発明の一実施例に係る安全性を高めた圧縮処理部(圧縮関数)の構成について図4を参照して説明する。図4には、aビット入力、2bビット出力の圧縮処理部である圧縮関数ユニット50を示している。図4に示す圧縮関数ユニット50は、a+bビット入力、bビット出力の独立した2つのデータ圧縮処理部としての圧縮関数f1,f2と、2bビット入出力のデータ攪拌処理部としての攪拌関数Fを有する。すなわち1つの攪拌関数Fと2系列の圧縮関数f1,f2を持つ。
【0045】
圧縮関数ユニット50は、入力としてaビットの[X]、2bビットの[Y]の計2b+aビットの入力を受け取る。入力のうち2bビット分のデータ[Y]は2bビット入出力を持つ攪拌関数Fを通過して攪拌される。続いて攪拌関数Fの2bビット出力はbビットずつに分割され、片方のbビットデータと圧縮関数ユニット50の残りの入力のaビットデータXとがユニット内部の圧縮関数f1により処理される。もう片方のbビットデータとaビットデータXがユニット内部の圧縮関数f2により並列処理される。最終的にf1とf2の出力を結合した2bビットが圧縮関数50の出力となる。なお、攪拌関数Fは入力された2bビットのデータを攪拌して出力する関数であり、2つの圧縮関数f1とf2は異なる圧縮関数である。
【0046】
長い入力ビットを処理可能とする定義域拡張のために、図4に示す圧縮関数ユニット50をMD構成として接続したハッシュ関数構成例を図5に示す。図5に示すデータ変換装置は、MD構成からなるデータ変換部を有する。図5に示す構成は、図4を参照して説明した圧縮関数ユニット50をn段持つデータ変換部からなる構成である。すなわち、2bビット入出力の1つの攪拌関数Fと、a+bビット入力bビット出力の2系列の圧縮関数f1,f2を有する圧縮関数ユニット50をn段構成としたハッシュ関数実行部としてのデータ変換装置である。
【0047】
図5に示すハッシュ関数は、圧縮関数ユニット50−0〜(n−1)をn段構成として繰り返し適用して最終段の圧縮関数ユニット50−(n−1)から2bビットのハッシュ値(H|H)を出力する。
【0048】
第1段の圧縮関数ユニット50−0は、入力ビットM〜Mn−1の最初のaビットMと、2つのbビット初期値IVとIVを入力し、各圧縮関数f1,f2がそれぞれbビット、計2bビットを出力する。その後は、前段の圧縮関数ユニットの内部の圧縮関数f1,f2の出力する2bビットと、M〜Mn−1の構成ビットであるaビットを入力して2bビットを出力する。以下、同様の処理を繰り返し実行し、最終段では、前段の出力2bビットと、Mn−1とパディングデータからなるaビットを入力して、bビットの出力H,Hの計2bビットのハッシュ値(H|H)を出力する。
【0049】
この構成は、圧縮関数ユニット50を構成する内部の圧縮関数f1,f2と、攪拌関数Fがランダムオラクルと呼ばれる性質を満たしていれば十分な安全性があることが示される。ランダムオラクルとは入力が与えられると内部で乱数を発生しその乱数を出力し、すでに与えられたことのある入力が再度与えられた場合には過去に出した乱数を再度出力する関数である。実際にはランダムオラクルのようなふるまいを近似する乱数生成の不要な決定的な手続きで出力を演算する関数を設計して置き換えることにより実現する。この構成により圧縮関数内部において安全性の評価がしやすく処理の軽い部品を利用できるため、設計がしやすく効率的の高いハッシュ関数が実現可能である。
【0050】
本実施例によれば、複数ラウンドからなる圧縮処理ラウンドの少なくとも一定タイミング毎に攪拌処理を実行させる構成としたので、解析困難性を高めた安全性の高いハッシュ値生成を行うデータ変換装置が実現される。
【0051】
また、図5で示した構成の変形例として、図6に示すように圧縮関数内部で攪拌関数Fと圧縮関数f1およびf2の順序を入れ替えた圧縮関数ユニット55を利用した場合も同じ効果のあるハッシュ関数として利用することが可能である。
【0052】
さらに、図5、図6で示した構成の変形例として、図7に示すように図6に示す構成における最終部分の攪拌関数Fを削除した構成でも安全性上は同じ効果のあるハッシュ関数として利用することが可能である。図5に示す構成において最初の攪拌関数Fの出力をIV,IVとして定義しなおすことでこの構成を得られることからも同様のことが導かれる。
【0053】
このように2bビット出力の専用の圧縮関数を作ることなく、より小さなbビット出力の圧縮関数と攪拌関数Fにより、安全性の高い2bビット出力のハッシュ関数が構成できる。
【0054】
また図5、図6、図7に示した構成では、圧縮関数ユニット内の内部の圧縮関数f1とf2の出力ビット数が両者ともbビットであり、中間値、すなわち連鎖値(Chaining Variable)が、内部圧縮関数f1とf2とで一致する構成とした。
【0055】
しかし、これらの内部圧縮関数f1,f2の連鎖値(CV)のビットサイズが一致している必要はない。例えば内部圧縮関数f1はbビットの連鎖値(CV)を出力し、内部圧縮関数f2はcビットの連鎖値(CV)を出力する設定として、全体としての連鎖値(CV)をb+cビットとする構成にしてもよい。このような構成でも、圧縮関数ユニットは、より小さい関数の構成により実現できるため、安全性の確認されている小さいビットサイズ対応の圧縮関数を内部圧縮関数として適用することができる。
【0056】
[3.新しい定義域拡張法の処理効率向上法]
続いて、図5,図6を参照して説明した定義域拡張法の処理効率を向上させたハッシュ関数の構成例について、図8を参照して説明する。図8は攪拌関数Fを挿入する間隔を圧縮関数の2回分の処理ごとに設定したハッシュ関数構成例である。
【0057】
圧縮関数ユニット60は、攪拌関数Fと、2段の内部圧縮関数f1、f3、2段の内部圧縮関数f2、f4によって構成される。なお圧縮関数ユニット60に含まれる4つの内部圧縮関数は、それぞれが異なる独立した圧縮関数である。すなわち、2つの攪拌関数Fに挟まれた領域内に含まれる4つの圧縮関数は独立した圧縮関数である。
【0058】
第1段の圧縮関数ユニット60は、2つのbビット初期値IVとIVを入力し、攪拌関数Fは入力された2bビットのデータを攪拌してbビットずつ各圧縮関数f1,f2に出力する。各圧縮関数f1,f2は、入力ビットM〜Mn−1の最初のaビットMと、攪拌関数Fからの出力bビットをそれぞれ入力して、bビット出力を生成して、後段の圧縮関数f3,f4に出力する。
【0059】
圧縮関数f3,f4は、入力ビットM〜Mn−1のaビットMと、前段の圧縮関数f1,f2からの出力bビットをそれぞれ入力して、bビット出力を生成して、後段の圧縮関数ユニットの攪拌関数Fに出力する。
【0060】
その後は、前段の圧縮関数ユニットの内部の圧縮関数出力する2bビットと、M〜Mn−1の構成ビットである2aビットを入力して2bビットを出力する。以下、同様の処理を繰り返し実行し、最終段では、前段の出力2bビットと、aビットのMn−2と、Mn−1とパディングデータからなるaビットを入力して、bビットの出力H,Hの計2bビットのハッシュ値(H|H)を出力する。
【0061】
この構成では図5に示す構成に比較して同じ長さのメッセージを処理する際の攪拌関数Fの呼び出し回数が削減されているため処理効率が向上する。具体的には図5に示す構成では、2つ分のaビットメッセージを処理する間に必要とされる処理は攪拌関数Fを2回と圧縮関数4回であるのに対し、図8に示す方式では攪拌関数Fを1回と圧縮関数4回の処理で行えるため、1回分のFの処理を削減可能となり、処理の効率化が実現される。
【0062】
図8に示す構成は、攪拌関数Fと2段階の圧縮関数を繰り返し実行する設定としている。攪拌関数の処理回数をさらに削減し、3段階以上の圧縮関数ごとに攪拌関数Fを設定するといった構成も可能である。攪拌関数Fの挿入間隔を圧縮関数k回ごとに設定した一般化したハッシュ関数実行部の構成例を図9に示す。図9に示す構成において、圧縮関数ユニット70は、2bビット入出力の1つの攪拌関数Fと、a+bビット入力、bビット出力のk段の圧縮関数を2系列とした構成を持つ。
【0063】
第1段の圧縮関数ユニット70は、2つのbビット初期値IVとIVを入力し、攪拌関数Fは入力された2bビットのデータを攪拌して2系列構成とされた各圧縮関数f1,f2にbビットずつ出力する。各圧縮関数f1,f2は、入力ビットM〜Mn−1の最初のaビットMと、攪拌関数Fからの出力bビットをそれぞれ入力して、bビット出力を生成して、後段の圧縮関数f3,f4に出力する。
【0064】
圧縮関数f3,f4は、入力ビットM〜Mn−1のaビットMと、前段の圧縮関数f1,f2からの出力bビットをそれぞれ入力してbビット出力を生成して、次の圧縮関数に出力する。以下、前段の圧縮関数の出力と、入力ビットM〜Mn−1を構成するaビットが後段の圧縮関数の入力となり、それぞれbビットを出力するこれをk回繰り返し、k回目の2系列の圧縮関数の出力が次の圧縮関数ユニット71の攪拌関数Fの入力とされる。
【0065】
圧縮関数ユニット71の処理は圧縮関数ユニット70の処理と同様である。ただし入力ビットM〜Mn−1の後半のビットデータとパディングデータが入力される。最終的に、圧縮関数ユニット71の際集団の2系列の圧縮関数からそれぞれbビットの出力H,Hの計2bビットのハッシュ値(H|H)が出力される。
【0066】
なお攪拌関数Fの挿入間隔はハッシュ値としての出力長2bに応じて安全性を落とさない範囲で決められる値である。例えばb=256の時にk=8とする構成があげられる。kが大きければ大きいほど処理効率が向上する。
【0067】
図9に示す構成は、図5に示す構成と同様、攪拌関数Fが初期値を入力して、攪拌関数Fの後段に2系列の圧縮関数を設定した構成であるが、先に図6等を参照して説明した2系列の圧縮関数が初期値を入力して、複数段の2系列の圧縮関数を実行させた後、攪拌関数Fを最終的に実行させる設定とした圧縮関数ユニットを利用する構成も可能である。
【0068】
[4.攪拌関数Fの実現方法]
攪拌関数Fは、入力ビットを攪拌して入力ビットと同一のビット数のデータを出力する関数である。具体的な攪拌関数の実現構成について図10を参照して説明する。図10は、攪拌関数Fを2つの圧縮関数を用いて実現した構成である。
【0069】
図10(1)に示す攪拌関数F80は、2bビット入出力の攪拌関数F80をbビット入力aビット出力の2つの変換部81,82と2つのa+bビット入力bビット出力の圧縮関数83,84により実現した例である。攪拌関数F80に入力される分割された2つのbビットデータはそれぞれ圧縮関数83,84の入力のbビット分として供給される。
【0070】
また同時に、それぞれのbビットデータは変換部81,82に入力されてaビットデータに変換され、圧縮関数83,84のaビット分の入力データとしてそれぞれ供給される。変換部81,82はビット長を調整するための単純な処理でよく例えばビットの複製による拡張、XORなどの単純な演算処理構成により実現可能である。
【0071】
変換部81,82は以下の条件を満足する設定とすることが好ましい。すなわち、それぞれの圧縮関数83,84の入力a+bビットに攪拌関数F80の入力2bビットのすべてのビットが影響を及ぼす設定とすることである。図10に示す構成によって攪拌関数Fは構成可能であり、結果として2つの圧縮関数にかかる処理程度で攪拌関数Fを実現することが可能である。
【0072】
図10(2)に示す攪拌関数F85は、変換部86,87の入力を2bビットとした例である。変換部86,87は、たとえばa>bである場合に2つのbビットデータを連結したのちに切り詰め、XORなどの単純な操作によりaビットを作り出す関数によって構成される。変換部86,87も以下の条件を満足する設定とすることが好ましい。すなわち、それぞれの圧縮関数88,89の入力a+bビットには攪拌関数F85の入力2bビットのすべてのビットが影響を及ぼす設定とすることである。この構成でも、2つの圧縮関数にかかる処理程度で攪拌関数Fを実現することが可能である。
【0073】
この図10に示す攪拌関数Fの構成は、図5〜図9を参照したハッシュ関数の構成における攪拌関数Fとして利用できる。このような構成を利用することで、図5〜図9に示す圧縮関数ユニットに元々設定されている圧縮関数を再利用して攪拌関数Fを実現することが可能である。このような部品の共有化によりハードウェア実装時のゲート規模の削減効果が発揮され、装置の小型化、コストダウンが可能となる。
【0074】
[5.定義域拡大法の一般化]
図5〜図9を参照して説明したMD構成を持つハッシュ関数は、1つの攪拌関数Fの出力を2系列の圧縮関数に対して入力する構成、あるいは2系列の圧縮関数の出力を1つの攪拌関数Fに出力する設定であった。すなわち、圧縮関数は2つの系列を用いた設定である。
【0075】
圧縮関数の系列数は、2に限るものではなく、3以上の系列を用いる構成としてもよい。系列数=m、ただしmは2以上の整数としたハッシュ関数の一般化構成例を図11に示す。
【0076】
図11の構成は、図9に示す構成をベースとして、圧縮関数の系列数を2からmに変更した構成である。圧縮関数ユニット90は、mbビット入出力の攪拌関数Fと、m系列構成とされた圧縮関数を複数段有する。最初の段のm個の圧縮関数f1〜fmは、F関数からmbビットのビットデータからのbビットと、入力ビットM〜Mn−1の最初のaビットMとを入力して、それぞれbビットを出力し後段の圧縮関数に入力する。k段のm系列圧縮関数は、それぞれ前段の圧縮関数からの出力と入力ビットM〜Mn−1のaビットとを入力してbビットを出力する。k段の圧縮関数の処理の後、圧縮関数ユニット90の最終段の圧縮関数の出力mbビットは、次の圧縮関数ユニットの攪拌関数Fに入力される。
【0077】
最終段の圧縮関数ユニット91の最終段のm個の圧縮関数の各々の出力bビットの出力H〜Hの計2mbビットがハッシュ値(H|H|・・・|H)として出力される。得られるハッシュ値H,H,...,Hは最大でmbビットである。この手法によりより長いサイズの出力を持つハッシュ関数の実現が容易となる。
【0078】
[6.攪拌関数Fの構成の一般化]
次に、攪拌関数Fの一般化された構成について説明する。攪拌関数Fの具体的構成については、先に図10を参照して説明した。図10を参照して説明した攪拌関数Fは、2系列の圧縮関数を適用した構成であった。
【0079】
これを一般化したmbビット入出力の攪拌関数Fの構成例を図12に示す。図12に示す攪拌関数F100は、m系列のcビット入力bビット出力の圧縮関数f1〜fmと、その前段のm個の変換部によって構成される。
【0080】
図12に示す例ではm種類の異なる独立な各圧縮関数f1〜fmの入力サイズはそれぞれcビットとしている。各圧縮関数f1〜fmへはすべての入力ビットの影響が及ぼされるようにmbビットの入力がすべていったん変換部に入力され、圧縮関数の入力サイズに合うように切り詰められる。変換部では例えば排他的論理和(XOR)や、ビットサイズ拡大処理などによりmbビット入力からcビット出力を生成する。
【0081】
変換部に求められる条件は、cビットの出力のいずれかのビットに、攪拌関数F100に対する入力ビットであるmbビットのすべてのビットが影響を与えているようにすることである。これは簡単な操作により実現可能である。例えば、c=mbであった場合には、変換部は入力をそのまま連結して出力すれば良い。
【0082】
[7.異なる圧縮関数の利用について]
以上の説明において、複数系列の多段構成とした圧縮関数f1,f2,...,fmを持つ圧縮関数ユニットにおいて、圧縮関数ユニット内の圧縮関数f1〜fmは、それぞれ異なる構成であるものとして説明した。もっとも安全性が高いことを客観的に示すことができるのがこの構成であり、たとえ単一の圧縮関数を用いた場合に即座に安全性が損なわれているわけではない。単一の圧縮関数を繰り返し使った方が実装上のメリットがある場合もあるため、別の実施の形態としてすべての圧縮関数を同じものにする構成も可能である。また単一にしなくとも、より少ない種類の圧縮関数を繰り返し用いる構成も同様に可能である。
【0083】
[8.圧縮関数の内部処理の効率的な実現法]
次に上記の説明において示した圧縮関数ユニット内に設定する圧縮関数fiの具体的な構成例について説明する。圧縮関数fの内部構成例を図13に示す。図13は、図5〜図12を参照して説明した圧縮関数ユニット内に設定する圧縮関数fi、さらに、攪拌関数Fの構成要素として利用可能な圧縮関数fiの構成例である。
【0084】
図13に示すように圧縮関数120は、メッセージスケジュール部(MS部)121と、連鎖値(CV:Chaining Variable)処理部122を有する。圧縮関数120に対する入力であるa+bビット中、[X]aビットはメッセージスケジュール部(MS部)121に入力され、残りの[Y]bビットが連鎖値(CV)処理部122に入力される。
【0085】
メッセージスケジュール部(MS部)121は、aビット入力に基づくメッセージスケジュール処理により、cビット出力を生成して連鎖値(CV)処理部122に入力する。連鎖値(CV)処理部122は、圧縮関数120に対する入力bビットと、メッセージスケジュール部(MS部)121からの入力cビットのb+cビットを入力して、圧縮関数120の出力としてbビット出力[Z]を生成する。
【0086】
この図13に示す圧縮関数、すなわち、メッセージスケジュール部(MS部)と連鎖値(CV)処理部とによって構成される圧縮関数を、先に図5を参照して説明したMD構成を持つハッシュ関数に設定した構成例を図14に示す。
【0087】
図14に示す圧縮関数ユニット130は、先に図5を参照して説明したと同様、攪拌関数Fと、2系列の圧縮関数f1,f2によって構成される。この圧縮関数f1,f2の各々が、図13を参照して説明した構成を持つ。すなわち、メッセージスケジュール部(MS部)と連鎖値(CV)処理部とによって構成される圧縮関数である。
【0088】
図14に示す例では2種類の圧縮関数f1,f2内のメッセージスケジュール部(MS部)をMS1、MS2とし、連鎖値(CV)処理部をCV1,CV2として示している。この構成によってハッシュ関数を実現することができる。以下では、さらなる処理効率の向上を実現する構成について説明する。
【0089】
図14に示す圧縮関数ユニット130−0〜130−(n−1)の各々には、メッセージMiが2つの圧縮関数内のメッセージスケジュール部MS1およびMS2に同時に入力されている。従って上下に並ぶ2系列の圧縮関数においてメッセージスケジュール部の共有化を行うことで処理の削減を行うことができる。
【0090】
図15はメッセージスケジュール部の共有を行ったハッシュ関数の構成例を示したものである。図14において、各圧縮関数ユニット130−0〜130−(n−1)に含まれていた上下2つの圧縮関数のメッセージスケジュール部を共有化して1つのメッセージスケジュール部(MS部)141とした圧縮関数142を設定している。この1つのメッセージスケジュール部(MS部)141を持つ圧縮関数142の構成を適用すれば、1つの圧縮関数ユニット140において実行するメッセージスケジュール部(MS部)の演算処理が1回の処理で済むことになり、必要な演算処理を少なくすることが可能である。例えば、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【0091】
図15を参照して説明した複数の圧縮関数におけるメッセージスケジュール部の共有化構成は、前述の複数のハッシュ構成において適用できる。すなわち、図5〜図12を参照して説明した複数系列の圧縮関数を持つ圧縮関数ユニットや攪拌関数F内の圧縮関数においても適用できる。
【0092】
[9.入力メッセージ長の拡張法]
次に、圧縮関数内の入力メッセージサイズを拡張する方法について検討する。図16に示す圧縮関数150は、図13を参照して説明した圧縮関数120と同様、メッセージスケジュール部(MS部)151と連鎖値(CV)処理部152から構成される。先に説明した図13に示す圧縮関数120はメッセージスケジュール部(MS部)121に対するメッセージ入力としてaビット入力構成であった。これに対して、図16に示す圧縮関数150は、2aビット入力に対応したメッセージスケジュール部151を有する。
【0093】
一般的にはaビット入力に対応した関数と2aビット入力に対応した関数は別物であり、異なる安全性評価基準に基づいて評価しなくてはいけない。よって、できる限り、すでに安全性や性能の評価ができているaビット入力に対応した関数を組み合わせて、2aビットに対応したメッセージスケジュール部を構成できる方が望ましい。また、そうすることによってほかに存在するaビット入力に対応した関数を再利用することも可能となる。具体的な関数の構成例は後段で説明するものとし、ここではaビット入力に対応した関数を利用して2aビット入力やそれ以上の入力に対応した圧縮関数を構成する方法について述べる。
【0094】
図17に、メッセージスケジュール部を2つの部分に分割した構成を持つ圧縮関数160の構成例を示す。圧縮関数160に対するメッセージ入力2aビットデータは2つのaビットデータに分割されたのち、各々がメッセージスケジュール部161,162においてcビット出力を生成する処理が行われる。2つのメッセージスケジュール部161,162の出力cビットはいずれも1つの連鎖値(CV)処理部163に供給される。
【0095】
連鎖値(CV)処理部163は、2つのメッセージスケジュール部161,162の出力cビットと、圧縮関数160に対する入力bビットを入力として、圧縮関数の出力であるbビット出力[Z]を生成して出力する。この構成のメリットとしては2aビットより短いaビット入力に対応した関数(メッセージスケジュール部)を利用して2aビットのメッセージ入力を実現する圧縮関数を構成可能となる点である。
【0096】
図18に示す圧縮関数170は、図17に示す圧縮関数160と同様、メッセージスケジュール部を2つの部分に分割した構成を持つ圧縮関数170の構成例である。この圧縮関数170は排他的論理和演算(XOR)部174を有する。
【0097】
圧縮関数170に対するメッセージ入力2aビットデータは2つのaビットデータに分割されたのち、各々がメッセージスケジュール部171,172においてcビット出力を生成する処理が行われる。2つのメッセージスケジュール部171,172の出力cビットは、排他的論理和演算(XOR)部174において排他的論理和演算がなされた後、1つの連鎖値(CV)処理部173に供給される。
【0098】
2つのメッセージスケジュール部同士の出力が一旦、排他的論理和演算部174で処理されたのちに連鎖値(CV)処理部173に供給される構成である。この構成のメリットとしては連鎖値(CV)処理部173が受け取るメッセージサイズは増加しないことにより連鎖値(CV)処理部173の内部が簡素化できる点である。なお排他的論理和部分をモジュロ加算処理に置き換えてもよい。
【0099】
図19は、図17に示す圧縮関数160の構成を一般化してnaビットの入力に対応するように設定した圧縮関数210の構成例を示している。圧縮関数210に入力されたnaビットのメッセージはn個のaビットメッセージに分割されそれぞれが独立にaビット入力に対応したメッセージスケジュール部(MS部)211−1〜nによって処理されて、各メッセージスケジュール部(MS部)211−1〜nがcビット出力を生成する。
【0100】
各メッセージスケジュール部(MS部)211−1〜nのcビット出力は連鎖値(CV)処理部212に供給される。連鎖値(CV)処理部212は、n個のメッセージスケジュール部(MS部)211−1〜nの出力ncビットと、圧縮関数210に対する入力bビットを入力として、圧縮関数の出力であるbビット出力[Z]を生成して出力する。
【0101】
この構成も、先に図17を参照して説明したと同様のメリットを有する。すなわち、naビットより短いaビット入力に対応した関数(メッセージスケジュール部)を利用してnaビットのメッセージ入力を実現する圧縮関数が構成可能となる。
【0102】
図20は、図18に示す圧縮関数170の構成を一般化してnaビットの入力に対応するように設定した圧縮関数220の構成例を示している。圧縮関数220に入力されたnaビットのメッセージはn個のaビットメッセージに分割されそれぞれが独立にaビット入力に対応したメッセージスケジュール部(MS部)221−1〜nによって処理されて、各メッセージスケジュール部(MS部)221−1〜nがcビット出力を生成する。
【0103】
各メッセージスケジュール部(MS部)221−1〜nのcビット出力は、排他的論理和演算部(XOR)223−1〜nにおいて排他的論理和演算がなされた後、1つの連鎖値(CV)処理部222に供給される。連鎖値(CV)処理部222は、排他的論理和演算部(XOR)223−nの出力cビットと、圧縮関数220に対する入力bビットを入力として、圧縮関数の出力であるbビット出力[Z]を生成して出力する。この構成も、naビットより短いaビット入力に対応した関数(メッセージスケジュール部)を利用してnaビットのメッセージ入力を実現する圧縮関数が構成可能となる。なお、排他的論理和演算部をモジュロ加算処理部とする構成も可能である。
【0104】
このように本発明の一実施例に係るデータ変換装置は、メッセージデータの分割データを並列に入力する複数の処理系列を有し、複数の圧縮関数実行部(f)を適用したデータ変換処理を実行する構成を有する。
【0105】
複数の圧縮関数実行部(f)の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部(MS部)を適用した処理と、メッセージスケジュール部(MS部)の出力と、前段処理部からの出力である中間値(連鎖値)を入力し、入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値(CV)処理部を適用した処理を行う構成である。
【0106】
複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部(MS部)、または連鎖値(CV)処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行う。このような構成により、例えば、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【0107】
[10.CV処理部とMS部に繰り返し型置換を利用したハッシュ関数実現法]
上述したように、圧縮関数は、メッセージスケジュール部(MS部)と連鎖値(CV)処理部を構成用素として実現可能である。このメッセージスケジュール部(MS部)と連鎖値(CV)処理部の具体的な構成例について説明する。
【0108】
メッセージスケジュール部(MS部)や、連鎖値(CV)処理部は置換関数をベースとしているものが一般的に知られている。例えば、ハッシュ関数として知られるSHA−1,Whirlpoolなどが置換関数をベースとした構成を持つ。
【0109】
メッセージスケジュール部(MS部)や、連鎖値(CV)処理部に適用する置換関数は、攪拌性能の高い置換関数が好ましい。
【0110】
比較的単純な置換関数を繰り返し適用して攪拌性能を高めた置換関数の構成例について説明する。以下の説明において、置換関数内において繰り返される比較的単純な置換を「内部置換」とよび、その結果できる置換を「全体置換」と呼ぶものとする。
【0111】
なお、置換関数は、入出力サイズが同一であり、かつ、それぞれの入出力値が一対一で対応するように入力値に基づいて出力値を生成する関数である。なお、置換関数は、この性質により逆関数が存在する。
【0112】
全体置換の内部では、2つの内部置換処理同士の間の中間データに対して外部からデータの加算を行ったり、その中間データを関数外部へ出力したりすることが可能である。圧縮関数では、この中間データを利用して全体置換の本来の入出力以外の位置に対するデータ入力や、追加データの出力を行う場合がある。そのように本来の入力以外に与えられるデータを付加入力と呼び、中間データを本来の出力以外に出力とするときにはそのデータを中間出力と呼ぶ。
【0113】
図21に示す置換関数(置換処理部)310は、付加入力311のある置換関数の例である。また、図22に示す置換関数(置換処理部)320は、中間出力321のある置換関数の例である。
【0114】
図21、図22に示す置換関数は、ともにaビット入出力に対応した全体置換をベースとしている。内部では内部置換1から内部置換kまでが繰り返し適用される構成である。図21に示す置換関数310は、付加入力311が内部置換の出力値である中間データに排他的論理和され、後段の内部置換処理部に出力、あるいは外部出力する構成を持つ。図22に示す置換関数320は内部置換の出力値である中間データが中間出力321として外部に出力される。以降ではこのようなタイプの全体置換と通常の全体置換を区別するために、それぞれ、図21に示すタイプの置換関数を付加入力付き置換関数、図22に示すタイプの置換関数を中間出力付き置換関数と呼ぶものとする。
【0115】
なお、付加入力つき置換関数では、
*付加入力が固定されたときは入力,出力が1対1対応する
という置換本来の性質を継承している。
また、中間出力付き置換関数では、
*入力とそれぞれの中間出力は1対1対応
という置換関数由来の性質をもつという特徴がある。
【0116】
ハッシュ関数を構成する圧縮関数は、先に図13〜図20を参照して説明したように、メッセージスケジュール部(MS部)と連鎖値(CV)処理部とによって構成される。
連鎖値(CV)処理部に付加入力付き置換関数を用い、
メッセージスケジュール部(MS部)に中間出力付きの置換関数を用いて互いに接続して圧縮関数を構成することについてはすでに知られていた(Whirlpool)。
【0117】
図23に、この既存の置換関数を用いた圧縮関数330の構成例を示す。図23に示す圧縮関数330は、メッセージスケジュール部(MS部)331を、中間出力付きaビット置換関数として設定し、この中間出力を連鎖値(CV)処理部332に用いた付加入力付きのaビット置換関数の付加入力に接続した構成を持つ。
【0118】
図23に示す構成では、説明を容易にするためにメッセージスケジュール部(MS部)331と、連鎖値(CV)処理部332をともにaビット置換関数としているが、必ずしもメッセージスケジュール部(MS部)331と、連鎖値(CV)処理部332の置換のサイズが一致しなくてもよい。長さが異なる場合には適切に拡張・切り詰め操作を行い調整することも可能である。また必ずしも図23に示すようにすべての中間出力を、メッセージスケジュール部(MS部)331と、連鎖値(CV)処理部332との間で接続する必要もなく、安全性や処理効率を考慮して適切に間引くなどの処理を実行し、メッセージスケジュール部(MS部)331と、連鎖値(CV)処理部332との間を接続する中間データは取捨選択してもよい。
【0119】
[11.MS部のサイズ拡大法]
圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例を図24に示す。図24に示す圧縮関数340は、入力ビットが3aビットに拡大された圧縮関数である。この図24に示す圧縮関数340は、先に、図18を参照して説明した構成と同様の構成であり、2つのメッセージスケジュール部(MS部)341,342と、2つのメッセージスケジュール部(MS部)341,342の出力の排他的論理和演算(XOR)結果を入力する1つの連鎖値(CV)処理部343を有する。
【0120】
2つのメッセージスケジュール部(MS部)341,342は、いずれも中間出力付き置換関数によって構成される。1つの連鎖値(CV)処理部343は、付加入力付き置換関数によって構成される。
【0121】
図24に示す置換関数340は、2aビットの入力Xがaビットずつに分割されそれぞれが2つのメッセージスケジュール部(MS部)341,342に入力され、これらの2つのメッセージスケジュール部(MS部)341,342の中間出力が1つの連鎖値(CV)処理部343に供給される構成である。このように付加入力付き置換関数、中間出力付き置換関数を用いれば容易に入力長の増大が可能となる。
【0122】
またこの図24に示す置換関数340の構成は、メッセージスケジュール部(MS部)として利用される2つの置換関数は同一のものであってはならない、同一である場合にはそれぞれの置換に対して同じaビットデータが入力された場合には対応する中間出力同士が一致してしまい排他的論理和演算(XOR)した結果がキャンセルされるためである。このためこの2者間には必ず異なる置換関数を準備する必要がある。これは内部置換の構成を異なるものにすることで実現可能である。
【0123】
この図24に示す圧縮関数の構成を一般化して入力Xを3aビット以上に拡大することも可能である。例えば、メッセージスケジュール部(MS部)の追加によって実現できる。
【0124】
図24に示す構成において処理量を減らし高速化を図る方法を示す。ハッシュ関数を構成する多段構成の圧縮関数において、例えば図4、図5等を参照して説明したように、圧縮関数が入力する値は、データ[X]としてメッセージ、データYとして中間値、すなわち連鎖値(CV)である。
【0125】
この際、メッセージ処理用の置換の繰り返し回数と連鎖値(CV)の系列用置換の繰り返し回数は必ずしも一致させる必要があるわけではない。例えば安全性を損なわない範囲でメッセージ処理用の置換の繰り返し回数を半分にする場合を考える。
【0126】
図25は、図24と同様、入力ビットが3aビットに拡大された圧縮関数350である。圧縮関数350に対する2aビットの入力Xがaビットずつに分割されそれぞれが2つのメッセージスケジュール部(MS部)351,352に入力され、これらの2つのメッセージスケジュール部(MS部)351,352の中間出力が1つの連鎖値(CV)処理部353に入力される。
【0127】
図25に示す2つのメッセージスケジュール部(MS部)351,352の内部置換の繰り返し回数は、連鎖値(CV)処理部353の内部置換の繰り返し回数の半分として設定されている。
【0128】
メッセージスケジュール部(MS部)351は偶数番目の置換を取り除き、メッセージスケジュール部(MS部)352は奇数番目の置換を取り除いて、2つのメッセージスケジュール部(MS部)351,352の内部置換の繰り返し回数を半分としている。この構成により、メッセージ処理に必要とされる演算が半減できる。
【0129】
この図25に示す圧縮関数350は、図24に示す圧縮関数340の構成に比べて処理が削減されることになりソフトウェア処理の向上が期待できる。メッセージスケジュール部(MS部)351,352で互い違いに関数を削除することで、ハードウェア実装時に同時に処理をすることが可能な置換を2つに設定でき、小さな回路規模で処理を実現することが可能というハードウェアの小型化を実現できるメリットがある。
【0130】
さらに図26に示す圧縮関数360は、図25と同様、入力ビットが3aビットに拡大された圧縮関数360である。圧縮関数360に対する2aビットの入力Xがaビットずつに分割されそれぞれが2つのメッセージスケジュール部(MS部)361,362に入力され、これらの2つのメッセージスケジュール部(MS部)361,362の中間出力が1つの連鎖値(CV)処理部363に入力される。
【0131】
図26に示す圧縮関数360における連鎖値(CV)処理部363は、図25に示す圧縮関数350における連鎖値(CV)処理部353の最前段に内部置換部364を1つ追加した構成であり、内部置換の繰り返し数を一つ追加した構成である。
【0132】
図26に示す圧縮関数360では、連鎖値(CV)処理部363用の全体置換のはじめに内部置換が一つ分追加されている。この変更に伴い、上側のメッセージスケジュール部(MS部)361の入力値が連鎖値(CV)処理部363の入力値に排他的論理和される構成になっている。
【0133】
本構成の特徴は、片方のメッセージスケジュール部(MS部)に着目した時に、連鎖値(CV)処理部363に供給される中間データが必ず連鎖値(CV)処理部363の2つの置換関数ごとになっている点である。この構成により上下のメッセージスケジュール部(MS部)361,362からの影響が均等に連鎖値(CV)処理部363の系列に作用しバランスのとれた攪拌が可能となる。この結果、安全性評価が容易になるというメリットがある。
【0134】
[12.CV処理部のサイズ拡大法]
図27に示す圧縮関数370は、先に図15を参照して説明した2系列の圧縮関数のメッセージスケジュール部の共有を行った構成を示したものである。図15で提示した定義域拡大法のb=aとした場合に適用することで、連鎖値(CV)処理部のサイズを拡大している。
【0135】
図27に示す圧縮関数370は、メッセージ[X]の構成ビットであるaビットをメッセージスケジュール部(MS部)371に入力し、中間値としての2つの連鎖値(CV)であるaビットをそれぞれ連鎖値(CV)処理部372,373に入力する。
【0136】
メッセージスケジュール部(MS部)371は、中間出力付き置換関数によって構成される。2つの連鎖値(CV)処理部372,373は、付加入力付き置換関数によって構成される。メッセージスケジュール部(MS部)371の中間出力は、2つの連鎖値(CV)処理部372,373の付加入力として設定される。メッセージスケジュール部(MS部)371の中間出力は、2つの連鎖値(CV)処理部372,373各々において、入力または中間値と排他的論理和演算されて内部置換部に入力される。あるいは出力値の生成に利用する。
【0137】
[13.CV処理部とMS部のサイズ拡大法]
図28に示す圧縮関数380は、図27に示す圧縮関数370の変形例であり、先に、図24を参照して説明した圧縮関数340と同様の手法で、圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例である。図28に示す圧縮関数380は、入力ビットが3aビットに拡大された圧縮関数である。この図28に示す圧縮関数380は、2つのメッセージスケジュール部(MS部)381,382と、2つのメッセージスケジュール部(MS部)381,382の出力の排他的論理和演算(XOR)結果を入力する1つの連鎖値(CV)処理部383,384を有する。
【0138】
2つのメッセージスケジュール部(MS部)381,382は、中間出力付き置換関数によって構成される。2つの連鎖値(CV)処理部383,384は、付加入力付き置換関数によって構成される。メッセージスケジュール部(MS部)381の中間出力は、連鎖値(CV)処理部383の付加入力として設定される。メッセージスケジュール部(MS部)382の中間出力は、連鎖値(CV)処理部384の付加入力として設定される。2つの連鎖値(CV)処理部383,384は、付加入力を入力または中間値と排他的論理和演算して内部置換部に入力、あるいは出力値の生成に利用する。
【0139】
[14.定義域拡大法用の攪拌関数Fの構成法]
中間出力付き置換関数と、付加入力付き置換関数の組み合わせによって攪拌関数Fを構成することも可能である。図29は、2つの中間出力付き置換関数と、2つの付加入力付き置換関数の組み合わせによって構成した攪拌関数F390の構成例である。
【0140】
攪拌関数F390は、2つのメッセージスケジュール部(MS部)391,392と、2つのメッセージスケジュール部(MS部)391,392の出力の排他的論理和演算(XOR)結果を入力する1つの連鎖値(CV)処理部393,394を有する。
【0141】
2つのメッセージスケジュール部(MS部)391,392は、中間出力付き置換関数によって構成される。2つの連鎖値(CV)処理部393,394は、付加入力付き置換関数によって構成される。
【0142】
メッセージスケジュール部(MS部)391の中間出力は、連鎖値(CV)処理部393の付加入力として設定される。メッセージスケジュール部(MS部)392の中間出力は、連鎖値(CV)処理部394の付加入力として設定される。2つの連鎖値(CV)処理部393,394は、付加入力を入力または中間値と排他的論理和演算して内部置換部に入力、あるいは出力値の生成に利用する。
【0143】
攪拌関数F390は、入力[Y]として2aビットを入力し、2aビットの出力[Z]を生成して出力する。なお、本発明のデータ変換装置内部置換については、先に説明した図25、図26の構成と同様、一部を削減した構成としてもよい。
【0144】
[15.拡散性能の高い置換処理実現方法]
メッセージスケジュール部(MS部)や、連鎖値(CV)処理部に適用する置換関数は、上述したように、比較的単純な置換関数としての内部置換を繰り返し適用して実現できる。このような比較的単純な置換関数を繰り返し適用することで攪拌性能を高めた置換関数が構成できる。
【0145】
内部置換として利用できる置換関数の具体的構成例について、図30を参照して説明する。図30は、攪拌性能の高い繰り返し型置換関数を構成するため、全体置換を実行する置換関数の内部で利用される内部置換としての置換関数の構成例である。この内部置換が繰り返し連結されて適用されることで全体置換が構成される。図30の内部置換処理部(置換関数)410は、256ビット入出力の置換を行う構成を示している。
【0146】
内部置換処理部(置換関数)410に入力する256ビットのデータは32バイトのデータとして表わされる。各バイトは、図に示す一本の入力データ線に対応する。
【0147】
まず左から4バイト(32ビット)単位でデータを区切り、8つのグループ(G1〜G8)に分けて考える。初めに左から奇数番目にあるグループ(G1,G3,G5,G7)に含まれる4バイトデータに対して、それぞれ対応する非線形変換部411において非線形変換処理を行う。
【0148】
これら4つのグループ(G1,G3,G5,G7)の各4バイト(32ビット)データは、非線形変換部411から出力されると、排他的論理和(XOR)演算部412において、それぞれ右隣にあるグループのバイト単位データとの排他的論理和演算を実行して、偶数番目の4つのグループ(G2,G4,G6,G8)の各4バイト(32ビット)データを更新する。
【0149】
すなわち、
グループ(G1)の4バイトデータの非線形変換結果データと、グループ(G2)の入力データとの排他的論理和演算を実行する。
グループ(G3)の4バイトデータの非線形変換結果データと、グループ(G4)の入力データとの排他的論理和演算を実行する。
グループ(G5)の4バイトデータの非線形変換結果データと、グループ(G6)の入力データとの排他的論理和演算を実行する。
グループ(G7)の4バイトデータの非線形変換結果データと、グループ(G8)の入力データとの排他的論理和演算を実行する。
これらの処理により、偶数番目の4つのグループ(G2,G4,G6,G8)の各4バイト(32ビット)データを更新する。
【0150】
次に、スワップ処理部413において、1バイト単位の各データのスワップ処理を行う。
非線形変換部411から出力されたデータからなる4つのグループ(G1,G3,G5,G7)のデータは、各グループ単位で左端のグループは右端のグループの位置に、それ以外のグループは一つ左のグループのあった位置に移動する。
すなわち、
グループ(G1)は出力グループ(Gout8)の位置に出力、
グループ(G3)は出力グループ(Gout2)の位置に出力、
グループ(G5)は出力グループ(Gout4)の位置に出力、
グループ(G7)は出力グループ(Gout6)の位置に出力、
このような対応でスワップ処理を実行して出力する。
【0151】
一方、排他的論理和(XOR)演算部412において、排他的論理和演算を実行して更新された偶数番目の4つのグループ(G2,G4,G6,G8)の各4バイト(32ビット)データは、バイト単位で分割されてそれぞれが異なるグループに移動するスワップ処理を行う。
【0152】
グループ(G2)の4バイトデータに対しては以下のようなスワップ処理が行われる。
グループ(G2)の4バイトデータを1バイト単位で先頭からABCDとする。
グループ(G2)の1番目の1バイトデータAは、出力グループ(Gout1)の1番目の1バイトデータとして出力、
グループ(G2)の2番目の1バイトデータBは、出力グループ(Gout3)の2番目の1バイトデータとして出力、
グループ(G2)の3番目の1バイトデータCは、出力グループ(Gout5)の3番目の1バイトデータとして出力、
グループ(G2)の4番目の1バイトデータDは、出力グループ(Gout7)の4番目の1バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【0153】
グループ(G4)の4バイトデータに対しては以下のようなスワップ処理が行われる。
グループ(G4)の4バイトデータを1バイト単位で先頭からEFGHとする。
グループ(G4)の1番目の1バイトデータEは、出力グループ(Gout3)の1番目の1バイトデータとして出力、
グループ(G4)の2番目の1バイトデータFは、出力グループ(Gout5)の2番目の1バイトデータとして出力、
グループ(G4)の3番目の1バイトデータGは、出力グループ(Gout7)の3番目の1バイトデータとして出力、
グループ(G4)の4番目の1バイトデータHは、出力グループ(Gout1)の4番目の1バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【0154】
グループ(G6)の4バイトデータに対しては以下のようなスワップ処理が行われる。
グループ(G6)の4バイトデータを1バイト単位で先頭からIJKLとする。
グループ(G6)の1番目の1バイトデータIは、出力グループ(Gout5)の1番目の1バイトデータとして出力、
グループ(G6)の2番目の1バイトデータJは、出力グループ(Gout7)の2番目の1バイトデータとして出力、
グループ(G6)の3番目の1バイトデータKは、出力グループ(Gout1)の3番目の1バイトデータとして出力、
グループ(G6)の4番目の1バイトデータLは、出力グループ(Gout3)の4番目の1バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【0155】
グループ(G8)の4バイトデータに対しては以下のようなスワップ処理が行われる。
グループ(G8)の4バイトデータを1バイト単位で先頭からMNOPとする。
グループ(G8)の1番目の1バイトデータMは、出力グループ(Gout7)の1番目の1バイトデータとして出力、
グループ(G8)の2番目の1バイトデータNは、出力グループ(Gout1)の2番目の1バイトデータとして出力、
グループ(G8)の3番目の1バイトデータOは、出力グループ(Gout3)の3番目の1バイトデータとして出力、
グループ(G8)の4番目の1バイトデータPは、出力グループ(Gout5)の4番目の1バイトデータとして出力、
このような対応でスワップ処理を実行して出力する。
【0156】
なお、次のラウンドの内部置換処理部(置換関数)においては、出力グループ(Gout1,Gout3,Gout5,Gout7)が非線形変換に入力される。
【0157】
このように、入出力を入れ替えるスワップ処理を実行することで各バイト単位データのが各ラウンドにおいて異なる種類の変換処理が実行されることになることが保証される。
【0158】
図30に示す内部置換処理部(置換関数)410の出力部に記載したように、32バイトの出力をx1〜x32とする。例えば、図22に示す中間出力付き置換関数における中間出力は、これらの出力に相当する。すなわち、図23〜図27を参照して説明した圧縮関数または攪拌関数Fの各構成におけるメッセージスケジュール部(MS部)は、中間出力付き置換関数によって構成されるが、これらのメッセージスケジュール部(MS部)の出力する中間出力に相当する。
【0159】
この中間出力は、図21に示す付加入力付き置換関数における付加入力として入力される。例えば、図23〜図27を参照して説明した圧縮関数または攪拌関数Fの各構成における連鎖値(CV)処理部は、付加入力付き置換関数によって構成されるが、これらの連鎖値(CV)処理部の付加入力として、図30に示す内部置換処理部(置換関数)410の出力部の32バイト出力:x1〜x32が入力される。
【0160】
なお、図30に示す内部置換処理部(置換関数)410の構成は、図23〜図27を参照して説明したように、圧縮関数や攪拌関数Fの内部に多数設定されることになる。この内部置換処理部(置換関数)の生成する中間データのすべての出力値x1〜x32を利用する設定としてもよいし、一部のみを利用する設定としてもよい。
【0161】
例えば、図30に示す内部置換処理部(置換関数)410の構造に着目して非線形変換部411の出力側x5〜x8、x13〜x16、x21〜x24、x29〜x32のみを中間出力として利用する構成としてもよい。あるいは、逆に次の置換関数で非線形変換部に入力されるx1〜x4、x9〜x12、x17〜x20、x25〜x28のみを中間値として利用する構成としてもよい。
【0162】
次に図30を参照して説明した内部置換処理部(置換関数)410内に構成される非線形変換部411の内部構成の一例について図31を参照して説明する。非線形変換部411は4バイトのデータを受け取り、4バイトのデータを出力する置換関数として構成可能である。
【0163】
図31に示す非線形変換部411は4バイトデータを入力する。図31に示す1本のラインが1バイトデータに相当する。入力されたデータは、排他的論理和(XOR)演算部421において、非線形変換部411ごとにあらかじめ定められた4つのコンスタント値(定数)C1,C2,C3,C4とそれぞれ排他的論理和される。なお、図30を参照して説明した内部置換処理部(置換関数)410内に構成される非線形変換部411は4つあるが、これらの4つの非線形変換部にはそれぞれ異なるコンスタント値(定数)が設定される。このコンスタント値(定数)設定処理については後述する。
【0164】
排他的論理和(XOR)演算部421において、非線形変換部411ごとにあらかじめ定められた4つのコンスタント値(定数)C1,C2,C3,C4とそれぞれ排他的論理和されたデータは、次に小非線形変換部422において、1バイト入出力の非線形変換処理が実行される。
【0165】
小非線形変換部422の出力は、線形変換部423に入力されて、線形変換が施されて出力される。なおここで説明した小非線形変換部422は、S−boxと呼ばれることがあり、256個の1バイトデータの変換テーブルとして表現することが可能である。また線形変換部423は、入力データに対する線形変換行列(M)を適用した変換処理によって出力データを算出する処理として実行される。線形変換行列(M)は、拡散行列とも呼ばれGF(2)の要素を持つ4x4の行列として表現されることがある。
【0166】
なお、置換関数はあるデータがなるべく多くのデータに影響すると同時に、入出力に含まれる非ゼロ要素の総和ができるだけ低い水準にならないことも求められている。これは、解析困難性を高め、脆弱性を排除するために有効である。具体的には差分攻撃や線形攻撃に対しての対策となる。
【0167】
図30に示す内部置換処理部(置換関数)410の構成は、図23〜図27を参照して説明したように、圧縮関数や攪拌関数Fの内部に多数設定されることになる。すなわち、図30に示す内部置換処理部(置換関数)410を複数ラウンド繰り返した処理が行われることになる。
【0168】
暗号アルゴリズムにおいても、同一の置換処理構成を複数ラウンド繰り返すラウンド演算を実行する構成としたものが多いが、全てのラウンドにおいて適用する線形変換行列[M]を1つの固定行列とするのではなく複数の異なる行列、例えば2つの行列[M1],[M2]を利用する、いわゆるDSM(Diffusion Switching Mechanism)を適用することが脆弱性に対する対策として有効であることが知られている。なお、DSMを適用した暗号アルゴリズムについては、例えば本出願人と同一の特許出願である特開2007−199156などに記載されている。
【0169】
このDSMによる脆弱性の改善効果は、ハッシュ関数においても効果があると考えられる。すなわち、全てのラウンドにおいて適用する線形変換行列[M]を1つの固定行列とするのではなく複数の異なる行列を利用することでランダム関数との区別を出来にくくすることが可能となり、様々な解析処理に対する困難性を高めることが可能となる。
【0170】
圧縮関数や攪拌関数Fの内部に多数設定される図30に示す内部置換処理部(置換関数)410の非線形変換部411において利用する線形変換行列[M]に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を図32に示す。
【0171】
図32は圧縮関数や攪拌関数Fの内部に多数設定される図30に示す内部置換処理部(置換関数)を2ラウンド分の結合構成を簡略化して表した図である。内部置換処理部(置換関数)440は、図30に示す内部置換処理部(置換関数)410と同様の構成である。内部置換処理部(置換関数)450は次の内部置換を実行するラウンドを示している。入力の各ラインは4バイトデータに相当する。
【0172】
内部置換処理部(置換関数)440は、図30に示す内部置換処理部(置換関数)410と同様、非線形変換部441、排他的論理和演算(XOR)部442、スワップ処理部443を有する。非線形変換部441は、図31を参照して説明した構成を有する。
【0173】
非線形変換部441は、図31を参照して説明したように、排他的論理和演算部と、小非線形変換部と線形変換部を有する。線形変換部は、線形変換行列Mを適用した線形変換処理を実行する。
【0174】
図32では、非線形変換部441として設定される4バイトデータ単位の非線形変換処理部を4つ示しているが、これらは、それぞれ図31を参照して説明した構成を有する。この4つの非線形変換部内の線形変換部において適用する線形変換行列Mを、図32では、左からそれぞれM1,M2,M3,M4として示している。線形変換行列M1,M2,M3,M4はそれぞれ異なる線形変換行列である。
【0175】
各ラウンドの、内部置換処理部(置換関数)440,450は同じ構成を有している。すなわち、内部置換処理部(置換関数)440,450のいずれも、4つの非線形変換部内の線形変換部において適用する線形変換行列Mは、左からそれぞれM1,M2,M3,M4である。このように内部置換では同じ行列が同じ位置で用いられている。
【0176】
図32に示すラウンド間を接続するライン(太線)から理解されるように、上段のラウンドの内部置換処理部(置換関数)440内の非線形変換の出力は下段のラウンドの内部置換処理部(置換関数)450の1つの非線形変換の出力と排他的論理和されている。
【0177】
例えば上段のラウンドの内部置換処理部(置換関数)440内の非線形変換部441の左端の線形変換行列M1を持つ非線形変換部441aの出力(図中の出力A)は、下段のラウンドの内部置換処理部(置換関数)450内の非線形変換部451の右端の線形変換行列M4を持つ非線形変換部451dの出力(図中の出力B)と、排他的論理和演算部452において、排他的論理和されている。この結果の出力が図に示す出力Cである。
【0178】
上段のラウンドの内部置換処理部(置換関数)440内の非線形変換部441の4つの非線形変換部の出力は、いずれも、下段のラウンドの内部置換処理部(置換関数)450内の非線形変換部451の4つの非線形変換部の出力のいずれかと排他的論理和演算がなされている。
【0179】
上下の各ラウンドの排他的論理和演算のなされる非線形変換部441の出力と、非線形変換部451の出力との組み合わせを各非線形変換部内の線形変換行列[M]の組み合わせとして示すと以下のようになる。
(1)M1とM4(非線形変換部441aと451d)
(2)M2とM1(非線形変換部441bと451a)
(3)M3とM2(非線形変換部441cと451b)
(4)M4とM3(非線形変換部441dと451c)
【0180】
この様に、異なる線形変換行列を適用した線形変換処理の実行結果を相互作用させる構成とすることで、上述のDSM(Diffusion Switching Mechanism)の適用構成を実現でき、解析困難性を高めることができる。
【0181】
なお、2つの行列の連結を記号|を利用して表すとして、上述の(1)〜(4)の行列ペアM1|M4、M2|M1、M3|M2、M4|M3これらの連結行列の分岐数が高くなる(例えば3以上)となる設定とした行列を選択して利用する構成とすれば、さらに解析困難性を高めることが可能である。またはそれぞれの逆行列を転置して得られる行列を並べて得られる行列M1−1M4−1M2−1M1−1M3−1M2−1M4−1M3−1の分岐数を3以上とする構成である。
【0182】
このように分岐数を高くする構成にすることで差分攻撃や線形攻撃に対する耐性を向上させることが可能である。
【0183】
このように、繰り返しラウンド演算として実行する内部置換処理部(置換関数)内の非線形変換部に設定される線形変換行列は、DSM構成を採用して異なる行列を利用した構成とすることが好ましい。また、利用する行列は、相互に影響しあう行列のペアの連結行列の分岐数が高くなるような行列に設定する構成とすることが好ましい。
【0184】
なお、図32を参照した説明では、4つの行列を用いて説明を行ったが、同じ分岐数の条件を満たすためには2つの行列でも実現可能である。例えば、M1|M2の分岐数が3以上、また逆行列を転置して得られる行列を並べて得られる行列M1−1M2−1の分岐数が3以上として図33に示す構成のように行列配置を行なう構成としてもよい。
【0185】
図33に示す構成において、上下の各ラウンドの排他的論理和演算のなされる非線形変換部441の出力と、非線形変換部451の出力との組み合わせを各非線形変換部内の線形変換行列[M]の組み合わせとして示すと以下のようになる。
(1)M1とM2(非線形変換部461aと471d)
(2)M2とM1(非線形変換部461bと471a)
(3)M1とM2(非線形変換部461cと471b)
(4)M2とM1(非線形変換部461dと471c)
【0186】
この図33に示す構成は、実装上の観点からは行列に必要なハードウェア回路やメモリ上のテーブルサイズを削減できることからさらに望ましい構成であると言える。
【0187】
この様に、異なる線形変換行列を適用した線形変換処理の実行結果を相互作用させる構成とすることで、上述のDSM(Diffusion Switching Mechanism)の適用構成を実現でき、解析困難性を高めることができる。
【0188】
以上、攪拌性能を高めた全体関数を実現するための内部置換の構成例について説明した。なお、上述の処理例は256ビット入力の例として説明したが、これは、一例であり、データサイズは様々な設定が可能であり、データサイズに応じた構成とすることは可能である。その場合小非線形変換部の入出力サイズ、線形変換部もサイズに対応した処理を行う設定とする。
【0189】
[16.独立性の高い出力をもつ置換関数の生成法]
上述した処理例では、圧縮関数や攪拌関数Fの内部に多数設定される内部置換処理構成は、例えば、図30に示す内部置換処理構成を用い、この同一構成を複数回繰り返す設定とした処理例として説明した。この内部置換処理の非線形変換部内の線形変換処理行列を上記のように構成することなどによって解析困難性を高めることができる。
【0190】
さらに複数の全体置換関数を必要とする構成においては、置換同士が独立にふるまうような複数の全体置換を利用することで解析困難性を高める場合がある。その場合、それら全体置換に含まれる内部置換を異なるものとすることにより実現する方法がある。その構成例を説明する。
【0191】
複数の異なる全体置換処理を実現するためには、それぞれの全体置換内の内部置換に含まれる部品を変化させる手法が有効である。しかしながら実装効率や、安全性評価処理の容易性の観点から、異なる部品を多数利用することは必ずしも望ましいことではない。できる限り利用部品を少なくして多様な処理を実現することが好ましい。
【0192】
全体置換ごとに異なる内部置換処理とするための構成としては、例えば以下のような構成が考えられる。
*全体置換ごとに利用されるコンスタント値(図31の排他的論理和演算部421で利用)を別のものに置き換える変更をする。
*全体置換に含まれる内部置換処理の部品である非線形変換部としてのS−box(図31の小非線形変換部422)や線形変換行列(図31の線形変換部423)を異なるものしそれを繰り返し利用して全体置換とする。
【0193】
なお、コンスタント値は、図30、図31を参照して説明した内部置換処理部410の非線形変換部411の排他的論理和(XOR)演算部421において入力する定数である。
【0194】
しかし、全体置換ごとのコンスタント値の全面的な変更や、S−boxや行列などの変更を行うためには、これらの異なるデータの供給や部品構成が必要となり、回路やメモリ容量を増大させることか必要となる。このような回路やメモリ容量を増大させることは実装上のデメリットであり、また安全性の再評価コストが高くなってしまう。という問題がある。
【0195】
そこで、本発明では、以下のような構成により、全体置換ごとの内部置換処理構成を異なる設定とする。
(a)複数の異なる小非線形演算(S−box)(図31の小非線形変換部422)が利用されている場合は、内部置換の小非線形演算(S−box)を全体置換ごとに入れ替える
(b)線形変換部(図31の線形変換部423)として利用される行列を、1つの行列から生成する複数の異なる行列に設定して、内部置換の行列を全体置換ごと異なる行列を設定する。例えば、行の入れ替えや列の入れ替えを行うことで1つの行列から複数の異なる行列を生成する。
(c)線形変換部(図31の線形変換部423)として利用される行列に複数種類の行列が利用されている場合は、内部置換の行列を全体置換ごとに入れ替える。(前述のDSMを利用した場合などはDSMの条件を崩さない範囲で変更する)
(d)上記の(a)〜(c)のいずれかの組み合わせ
【0196】
上記の(a)〜(d)のような設定として繰り返し実行される内部置換処理における置換処理構成を効率的に変更することができる。すなわち、回路規模やメモリ容量を大きく増大させることなく、異なる置換処理を実行させることが可能となる。
【0197】
特に、上記の(c)と(b)の組み合わせとすれば効率的に異なる全体置換を実現させることができる。すなわち、上述したDSM構成を適用して2種類以上の線形変換行列がメモリに格納されている場合、これらの行列の行や列を入れ替えて新たな行列を生成して、線形変換行列として利用する構成とする。このような設定とすれば、少ないデータに基づいて効率的に異なる線形変換処理を行うことができる。
【0198】
なお、DSMを利用し、複数の異なる線形変換行列を備えた構成において、行列の行や列の入れ替え処理を行った場合の安全性の評価が問題になるが、行列として所定の規則を持つ行列、例えば、circulant matrixやHadamard−matrixを使用すれば、行や列の入れ替えによって生成される行列を適用しても安全性評価に影響を与えないことが分かっている。従って、安全性評価は容易であり、簡便な変更で異なる置換関数を作り出す有効な手段であると言える。
【0199】
[17.置換関数に適用するコンスタントの生成処理]
先に説明したように、各ラウンドの置換処理構成を異なる設定とする1つの手法として、各ラウンド単位または複数ラウンド単位でコンスタント(図31の排他的論理和演算部421で利用する[C])を別のものに置き換える変更をする手法が有効であることは先に説明した。
【0200】
しかし、多数のラウンド数に対応するコンスタントを保持するためには大きなメモリ容量が必要となる。以下では、少ない数のコンスタントから、多数の異なるコンスタントを効率的に生成して、置換関数で使用可能とした構成例について説明する。
【0201】
はじめに置換関数に必要とされるコンスタントを定義する。ここでは4バイトをまとめて1ワードと呼ぶこととする。例えば図30示す内部置換処理部(置換関数)410には4つの非線形変換部があり、各非線形変換部の構成は、図31に示す構成を有する。図31に示すように、1つの非線形変換部411には4つのコンスタントを利用する。各コンスタントは、1バイト入力データとの排他的論理和演算に使用されるので、1つのコンスタントCnは1バイトデータである。1つの非線形変換部411には4つのコンスタントを利用するので、1つの非線形変換当たり1ワードのコンスタントが必要となる。
【0202】
図30示す内部置換処理部(置換関数)410には4つの非線形変換部があるので、1つの内部置換処理のために、4ワードのコンスタントが必要となる。この基本置換をk回繰り返して全体置換を構成する場合には合計4kワードのコンスタントが必要となる。
【0203】
ここでk個の内部置換のうち、入力側から数えてi番目の内部置換に含まれるj番目のコンスタント値をCi,jで表す。すると、1つの全体置換で必要とされるコンスタントは以下のように書き表すことができる。
(一つの全体置換で必要とされるコンスタントの集合の例)
1番目の内部置換:C1,1,C1,2,C1,3,C1,4
2番目の内部置換:C2,1,C2,2,C2,3,C2,4
3番目の内部置換:C3,1,C3,2,C3,3,C3,4
4番目の内部置換:C4,1,C4,2,C4,3,C4,4

k−1番目の内部置換:Ck−1,1,Ck−1,2,Ck−1,3,Ck−1,4
k番目の内部置換:Ck,1,Ck,2,Ck,3,Ck,4
【0204】
コンスタントの生成手法を開示した従来技術としては、例えば特開2008−58827に開示された技術がある。この従来技術は、64ビットのコンスタントを生成するために、8ビットの変数に格納された値を8回利用して作り出し、さらに次のコンスタントを生成するためには変数内の値をGF(2)上の要素とみなしてx倍またはx−1倍の演算を施すことで順次データの種類を増やしながら生成するという方法である。なおここで用いるxとは利用する有限体GF(2)を定義する既約多項式を多項式f(x)で表現した際の変数xである。
【0205】
以下、コンスタント生成処理構成として、一部のコンスタントをコンスタント生成用データに対するx倍の演算によって得られる系列に基いて生成し、残りはx−1倍の演算によって得られる系列に基づいて生成する方法について説明する。この方法により生成の手間を上げずにコンスタント値同士のシンプルな関係を局所的に崩すことが可能となる。その結果、コンスタントの乱雑性を上げることができる。本例では2つのワードに相当する64ビット分を1つの16ビット値から作り出す例を用いて説明する。
【0206】
本発明に従ったコンスタント生成処理について、上記の従来技術(特開2008−58827)に開示されたコンスタント生成処理について対比しながら説明する。
【0207】
まず、従来のコンスタント生成手順について説明する。従来のコンスタント生成手順は以下の通りである。
[1]16ビットの変数Sにそれぞれ初期値を格納する
[2]i=1...kに対して以下の処理を行う
(2.1)Ci,1=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
i,2=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
i,3=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
i,4=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
[2.2]S←S・x
【0208】
なお、Mask,Rotは別途定められた定数である。なお、ここで記号|はビットの連結を示している。(A xor B)はAとBの排他的論理和演算(XOR)処理を示している。
【0209】
このように生成された4つのコンスタント(Ci,1〜Ci,4)は一見乱数のように見える場合があるが、マスク演算とローテーションシフト演算のみで変化させているだけであるのでSがどんな値であろうともコンスタントの間には常にある特定の線形演算で表現される関係が維持される特徴がある。ブロック暗号の例からもわかるように線形変換のみでは乱雑性を上げることが不十分な場合が多く、できるだけ非線形な性質があった方が望ましい。
【0210】
次に、実装コストをあげず、パフォーマンスを低下させることなくコンスタント間に非線形な関係を導入して本発明に従ったコンスタント生成手法について以下説明する。
[1]16ビットの変数S,Tにそれぞれ初期値を格納する
[2]i=1...kに対して以下の処理を行う
(2.1)Ci,1=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
i,2=(S xor Mask)<<<Rot|(S xor Mask)<<<Rot
i,3=(T xor Mask)<<<Rot|(T xor Mask)<<<Rot
i,4=(T xor Mask)<<<Rot|(T xor Mask)<<<Rot
[2.2]S←S・x, T←T・x−1
【0211】
上記の処理に従って、16ビットの変数S,Tを適用して4つのコンスタント(Ci,1〜Ci,4)を生成することで、各内部置換に含まれる4つのコンスタントのうち半分はx倍の系列となり残り半分はx−1倍の系列に属することになる。
【0212】
このように構成すれば、Sから生成されるコンスタントとTから構成されるコンスタントの間には一定の線形関係が維持されることがなくなり、独立性が向上するという効果が得られる。
【0213】
上記のコンスタント生成処理を一般化して説明すると、x,xというように異なる指数を持つ値を用いて、初期値SとTの更新を行う処理であると説明できる。このような変数S,Tを適用して複数のコンスタントを生成することで、生成されるコンスタントのうち半分はx倍の系列となり残り半分はx倍の系列に属することになる。
【0214】
なお、さらにS,Tの2つの系列だけではなく、初期値が増えることが許容できれば3つ以上の系列を用いてコンスタントを生成する構成も可能である。
【0215】
[18.複数の全体置換に対するコンスタントの生成法]
圧縮関数においては複数の全体置換が存在しており、各全体置換それぞれに対して複数のコンスタントからなるコンスタント値の集合を準備する必要がある。仮に、全体置換の数がm個あるとしてそれらをP1,P2,...,Pmで表すとする。前述のコンスタント生成手法を適用すれば、これらの全体置換数mに応じて、m組の初期値を全体置換ごとに変更して、全体置換内の内部置換において適用するコンスタント値をそれぞれ生成する方法が適用できる。しかし、このような手法を行うとコンスタント値の生成の手間がm倍になり、効率的ではない。
【0216】
複数の全体置換に適用するためのコンスタント集合の生成処理を簡素化する手法について以下説明する。例えば圧縮関数内にm個の全体置換がある場合、1つ目の全体置換に必要なコンスタントは前述の複数の初期値S,Tを利用した方法により作り出し、2つ目以降の全体置換に適用するコンスタントは、1つ目の全体置換用に生成したコンスタントに対して簡単な演算を施して生成する。
【0217】
1つのデータ変換処理構成、例えば圧縮関数内にm個の全体置換が設定された構成において、x番目の全体置換の入力側から数えてi番目の内部置換に含まれるj番目のコンスタント値(ワード)をCi,j(x)で表す。1番目の全体置換用のコンスタントCi,j(1)は、上述の複数の初期値S,Tを利用した方法により生成されているものとする。
【0218】
このとき2番目以降の全体置換用のコンスタントCij(2),Cij(3),..,Cij(m)を生成する。図34を参照して、2番目以降の全体置換用のコンスタントCij(2),Cij(3),..,Cij(m)を生成する手法について説明する。
【0219】
図34には、m個の全体置換に必要とされるコンスタント集合として、上述の複数の初期値S,Tを利用した方法により生成される第1番目のコンスタント集合480と、第1番目のコンスタント集合480の変換処理によって生成する第2のコンスタント集合481、第3のコンスタント集合482、第mのコンスタント集合483を示している。
【0220】
m個の全体置換のすべてにおいて、全体置換1つにk個の内部置換が含まれ、内部置換1つに4つのコンスタントのワードが必要とされる設定とした例である。
【0221】
第2〜第mのコンスタント集合は、第1のコンスタント集合480に対する変換処理によって生成する。変換処理の具体例について説明する。
【0222】
変換処理としては、以下の3種類の変換処理のいずれかを適用することができる。
(変換処理例1)
全体置換ごとに定められた異なるローテーション量をRxとし、Ci,j(x)=Ci,j(1)<<<Rxとしてコンスタントを生成する。
i,j(1)は上述の複数の初期値S,Tを利用した方法により生成される第1番目のコンスタント集合480の要素としてのコンスタントである。
xは、コンスタント集合の識別番号であり、2〜mの値をとる。
【0223】
(変換処理例2)
全体置換ごとに定められた異なるマスク値(ワード)をMxとし、Ci,j(x)=Ci,j(1) xor Mxとしてコンスタントを生成する。
i,j(1)は上述の複数の初期値S,Tを利用した方法により生成される第1番目のコンスタント集合480の要素としてのコンスタントである。
xは、コンスタント集合の識別番号であり、2〜mの値をとる。
【0224】
(変換処理例3)
上記の変換処理例1,2を組み合わせた方法
i,j(x)=(Ci,j(1)<<<Rx)xor MxまたはCi,j(x)=(Ci,j(1) xor Mx)<<<Rxとしてコンスタントを生成する。
i,j(1)は上述の複数の初期値S,Tを利用した方法により生成される第1番目のコンスタント集合480の要素としてのコンスタントである。
xは、コンスタント集合の識別番号であり、2〜mの値をとる。
【0225】
上記変換処理例1〜3のいずれかを適用して、1つのコンスタント集合から複数の異なるコンスタント集合を生成することが可能であり、これらを各全体置換に適用するコンスタントとして設定する。
【0226】
なお、上記の変換処理例1の場合にはCi,j(0)が特殊なビットパターンを持たない限り任意のx,yに対してCi,j(x)とCi,j(y)を排他的論理和した演算結果が0にならないことが保証できるので、異なる全体置換を構成可能となる。また上記の変換処理例2の場合にも排他的論理和した結果が0にはならないことが保証できるため、この処理例でも異なる全体置換を生み出すのに適している。
【0227】
なお、上記の変換処理例において示したローテーション量およびマスク値は全体置換ごとに定められた値を用いる構成としたが、一つの全体置換に必要な複数のコンスタント値をつくるために複数の値を設定して利用する構成でも同様の効果が期待できる。
【0228】
これらの方式の採用により、一番目の置換関数用のコンスタント値の集合があれば、軽い処理コストで別の置換関数用のコンスタント値の集合を作成することができるため、処理の高速化が期待できる。
【0229】
とくにデータ変換装置に、プログラム実行機能、すなわちソフトウェアを実装した場合には、すべての全体置換に対するコンスタント値の集合をいったんメモリ上に展開することなく必要に応じて動的に作り出す形のプログラミング形態が可能となるためメモリ利用効率の向上が期待できる。
【0230】
なお、上記の例ではローテーション操作対象をワード単位での例を挙げて説明したが、2ワード分やそれ以上のワードを結合した単位でローテーションを施す形に変形してもよく、上記で説明した同様な効果が期待できる。
【0231】
[19.ハッシュ関数の出力値の切り詰め手法]
次に、ハッシュ値の生成処理構成において、nビットのハッシュ値を出力する関数を準備し、kビット分の出力を切り詰めてn−kビットのハッシュ値を出力可能としたデータ変換装置の構成例について説明する。
【0232】
例えば256ビット出力を持つハッシュ関数を準備しておき、その出力の32ビット分を切り詰めて224ビットハッシュ関数とする構成である。
【0233】
図35は、図30に示した内部置換処理部(置換関数)410と同様の構成であり、全体置換の最終段の内部置換処理構成を示している。出力y〜yは全体置換の出力であり、ハッシュ関数の出力としてのハッシュ値を示している。なお、図35では1ワード(4バイト)のデータ線を一本のデータ線として簡略化して示している。出力y〜y全体で、4×8=32バイト=256ビット出力となる。
【0234】
なお、説明を容易にするために出力の直前では排他的論理和後のデータを入れ替える処理は行わないものとする。さらに出力直前にデータ系列に対して排他的論理和されるデータXiはこの圧縮関数に入力されている中間地としての連鎖値(CV:Chaining Variable)やメッセージなどにより構成されるフィードフォワードされたデータを表しているものとする。
【0235】
ここで出力のnビットのデータのうちkビットのデータを切り詰めデータとして削除して出力データの切り詰めを行う方法を考える。図の出力系列:y〜yまでのうちの、どのデータ系列に含まれるビットを切り詰めるかを決定する必要がある。ひとつの方法として左から順にkビット分を切り詰める方式がある。その場合には次のような問題が考えられる。もしもkビットが左から2本分のデータ線のサイズの和を超えている場合には、切り詰めた結果の出力データを見たときに左端の非線形変換の処理結果が残された出力のどのビットにも影響を及ぼさないことになる。これはこの部分の計算に無駄であったことがわかる。
【0236】
このような無駄を避けるための特定のデータ系列に偏らない切り詰め手法について、以下2つの処理手法を説明する。
【0237】
(データ切り詰め手法1)
出力データ系列数をm,切り詰めるビット数(削除ビット数)をkとする。
kビットをできるだけ均等にm個に分けるために、以下の数式に従ってパラメータa,bを算出する。
【0238】
【数1】

【0239】
上記式によって、a,bを算出する。
なお、a+b=mである。
出力として得られるm個の系列y1からymのうちのa個の出力系列の出力データの各々から、f(k/m)ビット分ずつ切り詰める。さらに、残りのb個の出力系列の出力データの各々から、f(k/m)+1ビット分ずつ切り詰める。すなわち、図36に示すように、各出力系列に対するデータ切り詰め処理を実行する。
【0240】
置換を利用した場合には連続したビット列を切り捨てるよりも、飛び飛びに切り捨てることによりすべての非線形変換の結果がいずれかの出力に影響するように保証できるため、出力値の生成処理に無駄が発生しない。
【0241】
上記の出力ビット切り詰め処理では、すべての出力データ系列をデータ切り詰め対象として処理を行ったが、一部の出力系列のみを選択してデータ切り詰め処理を実行する構成としてもよい。
【0242】
例えば、図33に示す内部置換処理構成では、左から2本ずつの出力データには同じ非線形変換の出力が影響しているため、たとえば左から奇数番目(あるいは偶数番目)のデータ系列のみを切り詰めの対象として選択する構成としてもよい。このような処理を行っても、処理の無駄が発生しないという上記同様の効果は期待でき、さらに切り詰める個所が少なくなることで処理の手間が削減できる。なお、この系列選択構成は、出力系列数=nとしたとき、切り詰めるビット長がn/2を超えない場合に適用可能である。
【0243】
(データ切り詰め手法2)
出力データ系列数をm,切り詰めるビット数(削除ビット数)をkとする。
kビットをできるだけ均等にm個に分けるために、以下の数式に従ってパラメータa,bを算出する。
【0244】
【数2】

【0245】
上記式によって、a,bを算出する。
なお、a+b=m/2である。
出力として得られるm個の系列yからyのうちのm/2個の奇数番目の出力y,y,y,...,y2m−1のうちのa個の出力系列の出力データの各々から、f(2k/m)ビット分ずつ切り詰める。さらに、m/2個の奇数番目の出力の残りのb個の出力系列の出力データの各々から、f(2k/m)+1ビット分ずつ切り詰める。
【0246】
このように一部の出力系列のみを選択してデータ切り詰め処理を実行する構成としてもよい。この処理例では、切り詰める個所が少なくなることで処理の手間が削減できる。
【0247】
[20.データ変換装置の構成例]
最後に、上述した実施例に従った処理を実行する装置としてのICモジュール700の構成例を図37に示す。上述の処理は、例えばPC、ICカード、リーダライタ、その他、様々な情報処理装置において実行可能である。また、各処理は、論理回路を構成したハード回路やプログラム、あるいはその双方を適用して実行可能である。処理を実行する一例として例えば、図37に示すICモジュール700があり、このようなICモジュール700は様々な機器に搭載することが可能である。
【0248】
図37に示すCPU(Central processing Unit)701は、暗号処理やハッシュ処理等のデータ変換処理の開始や、終了、データの送受信の制御、各構成部間のデータ転送制御、その他の各種プログラムを実行するプロセッサである。メモリ702は、CPU701が実行するプログラム、あるいは演算パラメータなどの固定データを格納するROM(Read-Only-Memory)、CPU701の処理において実行されるプログラム、およびプログラム処理において適宜変化するパラメータの格納エリア、ワーク領域として使用されるRAM(Random Access Memory)等からなる。また、メモリ702は暗号処理やハッシュ処理等のデータ変換処理に必要な鍵データや、データ変換処理において適用する変換テーブル(置換表)や変換行列に適用するデータ等の格納領域として使用可能である。なおデータ格納領域は、耐タンパ構造を持つメモリとして構成されることが好ましい。
【0249】
データ変換部703は、例えば上述した各種の処理、すなわちハッシュ関数、圧縮関数、置換関数、攪拌関数などの各関数に対応するデータ変換処理、コンスタント算出、出力データ切り詰め処理などの各種処理を実行する。なお、これらの各関数の実行においては、各関数の実行において規定されている線形変換や、非線形変換や、排他的論理和演算などを、予め設定されたシーケンスに従って実行することになる。これらの処理は、ハードウェア、またはソフトウェア、またはその組み合わせ構成によって実現される。
【0250】
なお、ここでは、データ変換部を個別モジュールとした例を示したが、このような独立したモジュールを設けず、例えば暗号処理やハッシュ処理プログラムをROMに格納し、CPU701がROM格納プログラムを読み出して実行するように構成してもよい。各関数の実行、コンスタント算出、出力データ切り詰め処理などの各種処理をCPU701がプログラムに従って実行する構成としてもよい。
【0251】
乱数発生器704は、暗号処理やハッシュ処理に必要となる鍵やパラメータの生成などにおいて必要となる乱数の発生処理を実行する。
【0252】
送受信部705は、外部とのデータ通信を実行するデータ通信処理部であり、例えばリーダライタ等、ICモジュールとのデータ通信を実行し、ICモジュール内で生成した暗号文の出力、あるいは外部のリーダライタ等の機器からのデータ入力などを実行する。
【0253】
以上、特定の実施例を参照しながら、本発明について詳解してきた。しかしながら、本発明の要旨を逸脱しない範囲で当業者が実施例の修正や代用を成し得ることは自明である。すなわち、例示という形態で本発明を開示してきたのであり、限定的に解釈されるべきではない。本発明の要旨を判断するためには、特許請求の範囲の欄を参酌すべきである。
【0254】
また、明細書中において説明した一連の処理はハードウェア、またはソフトウェア、あるいは両者の複合構成によって実行することが可能である。ソフトウェアによる処理を実行する場合は、処理シーケンスを記録したプログラムを、専用のハードウェアに組み込まれたコンピュータ内のメモリにインストールして実行させるか、あるいは、各種処理が実行可能な汎用コンピュータにプログラムをインストールして実行させることが可能である。例えば、プログラムは記録媒体に予め記録しておくことができる。記録媒体からコンピュータにインストールする他、LAN(Local Area Network)、インターネットといったネットワークを介してプログラムを受信し、内蔵するハードディスク等の記録媒体にインストールすることができる。
【0255】
なお、明細書に記載された各種の処理は、記載に従って時系列に実行されるのみならず、処理を実行する装置の処理能力あるいは必要に応じて並列的にあるいは個別に実行されてもよい。また、本明細書においてシステムとは、複数の装置の論理的集合構成であり、各構成の装置が同一筐体内にあるものには限らない。
【産業上の利用可能性】
【0256】
上述したように、本発明の一実施例の構成によれば、メッセージデータの分割データを並列に入力する複数の処理系列の複数の圧縮関数実行部を適用したデータ変換処理を実行する構成を有する。複数の圧縮関数実行部の各々は、メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、このメッセージスケジュール部の出力と前段処理部からの出力である中間値を入力し入力データの圧縮により中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う。複数の処理系列において並列処理を行う複数の圧縮関数実行部は、メッセージスケジュール部または連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成とした。本構成により、ハードウェア構成の小型化、処理ステップの簡略化が実現される。
【図面の簡単な説明】
【0257】
【図1】データ圧縮処理部としての圧縮関数(f)について説明する図である。
【図2】代表的な定義域拡張法であるメッセージパディング付きのMD構成(Merkle−Damgard Construction)について説明する図である。
【図3】出力ビットサイズが小さい圧縮関数を利用して出力ビットサイズの大きいハッシュ値を実現するカスケードハッシュ構成について説明する図である。
【図4】安全性を高めた圧縮処理部(圧縮関数)の構成について説明する図である。
【図5】図4に示す圧縮関数ユニット50をMD構成として接続したハッシュ関数構成例について説明する図である。
【図6】図5で示した構成の変形例であり圧縮関数内部で攪拌関数Fと圧縮関数f1およびf2の順序を入れ替えた圧縮関数ユニット55を利用したハッシュ関数構成例について説明する図である。
【図7】図6に示す構成における最終部分の攪拌関数Fを削除した構成例について説明する図である。
【図8】攪拌関数Fを挿入する間隔を圧縮関数の2回分の処理ごとに設定した構成例について説明する図である。
【図9】攪拌関数Fの挿入間隔を圧縮関数k回ごとに設定した一般化したハッシュ関数実行部の構成例について説明する図である。
【図10】攪拌関数Fを2つの圧縮関数を用いて実現した構成例について説明する図である。
【図11】系列数=m、ただしmは2以上の整数としたハッシュ関数の一般化構成例について説明する図である。
【図12】mbビット入出力の攪拌関数Fの構成例について説明する図である。
【図13】圧縮関数fの内部構成例について説明する図である。
【図14】メッセージスケジュール部(MS部)と連鎖値(CV)処理部とによって構成される圧縮関数を、MD構成を持つハッシュ関数に設定した構成例について説明する図である。
【図15】メッセージスケジュール部の共有を行ったハッシュ関数の構成例について説明する図である。
【図16】圧縮関数内の入力メッセージサイズを拡張する圧縮関数の構成例について説明する図である。
【図17】メッセージスケジュール部を2つの部分に分割した構成を持つ圧縮関数の構成例について説明する図である。
【図18】メッセージスケジュール部を2つの部分に分割した構成を持ち、排他的論理和演算部(XOR)を有する圧縮関数の構成例について説明する図である。
【図19】図17に示す圧縮関数の構成を一般化してnaビットの入力に対応するように設定した圧縮関数の構成例について説明する図である。
【図20】図18に示す圧縮関数の構成を一般化してnaビットの入力に対応するように設定した圧縮関数の構成例について説明する図である。
【図21】付加入力のある置換関数の例について説明する図である。
【図22】中間出力のある置換関数の例について説明する図である。
【図23】既存の置換関数を用いた圧縮関数の構成例について説明する図である。
【図24】圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例について説明する図である。
【図25】入力ビットが3aビットに拡大された圧縮関数の構成例について説明する図である。
【図26】入力ビットが3aビットに拡大された圧縮関数の構成例について説明する図である。
【図27】2系列の圧縮関数のメッセージスケジュール部の共有を行った構成例について説明する図である。
【図28】圧縮関数に入力されるデータサイズを拡大した圧縮関数の構成例について説明する図である。
【図29】2つの中間出力付き置換関数と、2つの付加入力付き置換関数の組み合わせによって構成した攪拌関数Fの構成例について説明する図である。
【図30】内部置換として利用できる置換関数の具体的構成例について説明する図である。
【図31】内部置換処理部(置換関数)内に構成される非線形変換部の内部構成の一例について説明する図である。
【図32】内部置換処理部(置換関数)の非線形変換部において利用する線形変換行列[M]に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を説明する図である。
【図33】線形変換行列[M]に複数の異なる行列を利用した設定とした内部置換処理部の繰り返しラウンドの構成例を説明する図である。
【図34】全体置換用のコンスタントCij(2),Cij(3),..,Cij(m)を生成する手法について説明する図である。
【図35】ハッシュ関数の出力ビットの切り詰め手法の一例について説明する図である。
【図36】ハッシュ関数の出力ビットの切り詰め手法の一例について説明する図である。
【図37】本発明に係る処理を実行するデータ変換装置としてのICモジュールの構成例を示す図である。
【符号の説明】
【0258】
10 圧縮関数
50 圧縮関数ユニット
55 圧縮関数ユニット
60 圧縮関数ユニット
70,71 圧縮関数ユニット
80,85 攪拌関数F
81,82,86,87 変換部
83,84,88,89 圧縮関数
90,91 圧縮関数ユニット
100 攪拌関数F
120 圧縮関数
121 メッセージスケジュール部(MS部)
122 連鎖値(CV)処理部
130 圧縮関数ユニット
140 圧縮関数ユニット
141 メッセージスケジュール部(MS部)
142 圧縮関数
150 圧縮関数
151 メッセージスケジュール部(MS部)
152 連鎖値(CV)処理部
160 圧縮関数
161,162 メッセージスケジュール部(MS部)
163 連鎖値(CV)処理部
170 圧縮関数
171,172 メッセージスケジュール部(MS部)
173 連鎖値(CV)処理部
174 排他的論理和演算(XOR)部
210 圧縮関数
211 メッセージスケジュール部(MS部)
212 連鎖値(CV)処理部
220 圧縮関数
221 メッセージスケジュール部(MS部)
222 連鎖値(CV)処理部
223 排他的論理和演算(XOR)部
310 置換関数(置換処理部)
311 付加入力
320 置換関数(置換処理部)
321 中間出力
330 圧縮関数
331 メッセージスケジュール部(MS部)
332 連鎖値(CV)処理部
340 圧縮関数
341,342 メッセージスケジュール部(MS部)
343 連鎖値(CV)処理部
350 圧縮関数
351,352 メッセージスケジュール部(MS部)
353 連鎖値(CV)処理部
360 圧縮関数
361,362 メッセージスケジュール部(MS部)
363 連鎖値(CV)処理部
370 圧縮関数
371 メッセージスケジュール部(MS部)
372,373 連鎖値(CV)処理部
380 圧縮関数
381,382 メッセージスケジュール部(MS部)
383,384 連鎖値(CV)処理部
390 攪拌関数F
391,392 メッセージスケジュール部(MS部)
393,394 連鎖値(CV)処理部
410 内部置換処理部(置換関数)
411 非線形変換部
412 排他的論理和(XOR)演算部
413 スワップ処理部
421 排他的論理和(XOR)演算部
422 小非線形変換部
423 線形変換部
440 内部置換処理部(置換関数)
441 非線形変換部
442 排他的論理和演算(XOR)部
443 スワップ処理部
451 非線形変換部
452 排他的論理和演算(XOR)部
460 内部置換処理部(置換関数)
461 非線形変換部
470 内部置換処理部(置換関数)
471 非線形変換部
480〜484 コンスタント集合
700 ICモジュール
701 CPU(Central processing Unit)
702 メモリ
703 データ変換部
704 乱数発生器
705 送受信部

【特許請求の範囲】
【請求項1】
メッセージデータを入力してハッシュ値を生成するデータ変換部を有し、
前記データ変換部は、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行する構成であり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行う構成であり、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用する構成であるデータ変換装置。
【請求項2】
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一のメッセージスケジュール部を複数の圧縮関数実行部で共有した共有メッセージスケジュール部を有し、
前記共有メッセージスケジュール部は、前記メッセージデータの分割データを入力してメッセージスケジュール処理により生成した出力データを複数の連鎖値処理部に出力する構成であり、
前記複数の連鎖値処理部は、前記共有メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する処理を並列に実行する構成である請求項1に記載のデータ変換装置。
【請求項3】
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、単一の連鎖値処理部を複数の圧縮関数実行部で共有した共有連鎖値処理部を有し、
並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データを前記共有連鎖値処理部に出力する構成であり、
前記共有連鎖値処理部は、前記複数のメッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力して入力データの圧縮により前記中間値と同一ビット数の出力データを生成する構成である請求項1に記載のデータ変換装置。
【請求項4】
前記並列処理を実行する複数の圧縮関数実行部各々の複数のメッセージスケジュール部は、前記メッセージデータの同一の分割データを入力してメッセージスケジュール処理によって生成した出力データの排他的論理和演算結果を前記共有連鎖値処理部に出力する構成である請求項3に記載のデータ変換装置。
【請求項5】
前記メッセージスケジュール部は、置換処理を繰り返し実行し、各置換処理結果を中間値として出力する構成を持つ中間出力付き置換関数実行部によって構成され、
前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力を付加入力として、置換処理を繰り返し実行する付加入力付き置換関数実行部を有する構成である請求項1に記載のデータ変換装置。
【請求項6】
前記連鎖値処理部は、前記中間出力付き置換関数実行部から出力される中間出力と前段の置換処理結果との排他的論理和結果を次の置換処理の入力データとして設定する構成である請求項5に記載のデータ変換装置。
【請求項7】
前記置換関数実行部の実行する複数の置換処理の各々は、
入力データの少なくとも一部データに対する非線形変換処理と、データ入れ替え処理としてのスワップ処理とを含む構成である請求項5に記載のデータ変換装置。
【請求項8】
前記非線形変換処理は、コンスタント(定数)を適用した排他的論理和演算と、非線形変換処理と、線形変換行列を適用した線形変換処理を含む処理である請求項7に記載のデータ変換装置。
【請求項9】
前記置換関数実行部の実行する複数の置換処理の各々において行われる線形変換処理は、複数の異なる行列を適用するDSM(Diffusion Switching Mechanism)に従った処理として実行する構成である請求項7に記載のデータ変換装置。
【請求項10】
前記置換関数実行部の実行する複数の置換処理の各々は、それぞれ異なるコンスタント(定数)集合を入力したデータ処理を行う構成であり、
1つの置換処理に適用するコンスタント集合を基本集合として、該基本集合に対するデータ変換により生成した異なるコンスタント集合を各置換処理に適用する構成である請求項5に記載のデータ変換装置。
【請求項11】
前記基本集合となるコンスタント集合は、
異なる複数の初期値S,Tに対して予め設定した変換ルールを適用して生成した複数のコンスタントから構成され、
前記変換ルールは、前記初期値に対して、
S←S・x、T←T・x
ただしa≠b
とする更新処理を含む構成である請求項10に記載のデータ変換装置。
【請求項12】
前記基本集合に対するデータ変換処理は、
前記基本集合を構成するコンスタントの構成ビットのローテーション処理、または、予め規定したマスクデータとの演算処理である請求項10に記載のデータ変換装置。
【請求項13】
前記データ変換部は、
最終的に出力するハッシュ値のビット数削減処理として切り詰め処理を行う構成を有し、
前記データ変換部の出力部を構成する複数のデータ出力系列各々の出力ビットに対するビット削減数を、予め規定した算出式に従って算出し、算出結果に従った切り詰め処理を実行する構成である請求項1に記載のデータ変換装置。
【請求項14】
前記データ変換部は、さらに、
入力データに対するデータ攪拌処理を実行する攪拌処理部を有し、
前記複数の圧縮関数実行部は、前記メッセージデータの分割データのすべてを入力可能とした複数段の圧縮関数実行部として構成され、
前記複数段の圧縮関数実行部の一部は、前記攪拌処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、
前記複数段の圧縮関数実行部の一部は、前段の圧縮処理部の出力と、メッセージデータの分割データの双方を入力してデータ圧縮処理を実行する構成を有し、
前記複数段の圧縮関数実行部の最終段の圧縮処理部は、前記メッセージデータのハッシュ値を出力する構成である請求項1に記載のデータ変換装置。
【請求項15】
データ変換装置において実行するデータ変換処理方法であり、
データ変換部が、メッセージデータを入力してハッシュ値を生成するデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行するステップであり、
前記複数の圧縮関数実行部の各々は、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を行ない、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部は、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有し、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行うデータ変換方法。
【請求項16】
データ変換装置においてデータ変換処理を実行させるプログラムであり、
データ変換部に、メッセージデータを入力してハッシュ値を生成させるデータ変換ステップを有し、
前記データ変換ステップは、
前記メッセージデータの分割データを並列に入力する複数の処理系列において、複数の圧縮関数実行部を適用したデータ変換処理を実行させるステップであり、
前記プログラムは、前記複数の圧縮関数実行部の各々に、
メッセージデータの分割データを入力してメッセージスケジュール処理を行うメッセージスケジュール部を適用した処理と、
前記メッセージスケジュール部の出力と、前段処理部からの出力である中間値を入力し、入力データの圧縮により前記中間値と同一ビット数の出力データを生成する連鎖値処理部を適用した処理を実行させ、
前記複数の処理系列において並列処理を行う複数の圧縮関数実行部に、前記メッセージスケジュール部、または前記連鎖値処理部の少なくともいずれかを共有させて、単一のメッセージスケジュール部、または単一の連鎖値処理部を利用した処理を行わせるプログラム。

【図1】
image rotate

【図2】
image rotate

【図3】
image rotate

【図4】
image rotate

【図5】
image rotate

【図6】
image rotate

【図7】
image rotate

【図8】
image rotate

【図9】
image rotate

【図10】
image rotate

【図11】
image rotate

【図12】
image rotate

【図13】
image rotate

【図14】
image rotate

【図15】
image rotate

【図16】
image rotate

【図17】
image rotate

【図18】
image rotate

【図19】
image rotate

【図20】
image rotate

【図21】
image rotate

【図22】
image rotate

【図23】
image rotate

【図24】
image rotate

【図25】
image rotate

【図26】
image rotate

【図27】
image rotate

【図28】
image rotate

【図29】
image rotate

【図30】
image rotate

【図31】
image rotate

【図32】
image rotate

【図33】
image rotate

【図34】
image rotate

【図35】
image rotate

【図36】
image rotate

【図37】
image rotate