(57)【要約】【課題】ハッシュ値生成のスループットを向上可能とする技術を提供する。【解決手段】ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置において、ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段，ρ処理手段，π処理手段，χ処理手段，ι処理手段を備えており、θ処理手段及びι処理手段は、ｓｈｅｅｔ単位でデータを処理するよう構成されており、θ処理手段は、ι処理手段から１個のｓｔａｔｅを構成する全てのｓｈｅｅｔが入力される前にθの処理を開始するよう構成されている。【選択図】図１８
2014092575.tif 000002
【特許請求の範囲】
【請求項１】
ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置であって、
前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段，ρ処理手段，π処理手段，χ処理手段，ι処理手段を備えており、
前記θ処理手段及び前記ι処理手段は、ｓｈｅｅｔ単位でデータを処理するよう構成されており、
前記θ処理手段は、前記ι処理手段から、１個のｓｔａｔｅを構成する全てのｓｈｅｅｔが入力される前に前記θの処理を開始するよう構成されている
ことを特徴とするハッシュ値生成装置。
【請求項２】
前記ι処理手段の出力と前記θ処理手段の入力とは、ラッチ回路を含まない組み合わせ回路のみで接続されていることを特徴とする請求項１に記載のハッシュ値生成装置。
【請求項３】
１個のｓｔａｔｅからｓｈｅｅｔ単位のデータを生成し、前記θ処理手段にｓｈｅｅｔ単位でデータを入力する入力手段を更に備えることを特徴とする請求項１又は２に記載のハッシュ値生成装置。
【請求項４】
前記θ処理手段と前記ρ処理手段とは、前記θ及び前記ρの処理をまとめて処理するθ＆ρ処理手段として構成され、
前記χ処理手段と前記ι処理手段とは、前記χ及び前記ιの処理をまとめて処理するχ＆ι処理手段として構成され、
は、前記θ＆ρ処理手段と前記χ＆ι処理手段とはパイプライン処理されるよう構成されている
ことを特徴とする請求項１乃至３の何れか１項に記載のハッシュ値生成装置。
【請求項５】
ｓｔａｔｅは、ｘ軸方向にｍビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットの直方体構造として表され、
ｓｈｅｅｔは、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットの平面構造として表される
ことを特徴とする請求項１乃至４の何れか１項に記載のハッシュ値生成装置。
【請求項６】
前記θの処理は、各ビットに対して近傍の２つのｃｏｌｕｍｎの和を加える処理であり、
前記ρの処理は、各ビットの値をｚ軸方向にシフトする処理であり、
前記πの処理は、ｘ−ｙ平面内で各ビットの値を入れ替える処理であり、
前記χの処理は、ｘ軸方向のビット列内での変換を行う処理であり、
前記ιの処理は、各ビットにラウンド定数を加える処理である
ことを特徴とする請求項１乃至５の何れか１項に記載のハッシュ値生成装置。
【請求項７】
前記ｓｔａｔｅは、５個のｓｈｅｅｔから構成されており、
前記θ処理手段は、前記ι処理手段から、３個のｓｈｅｅｔが入力されたとき前記θの処理を開始する
ことを特徴とする請求項１乃至６の何れか１項に記載のハッシュ値生成装置。
【請求項８】
ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成方法であって、
前記ＫＥＣＣＡＫアルゴリズムのラウンド処理は、θ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理工程，ρ処理工程，π処理工程，χ処理工程，ι処理工程を含んでおり、
前記θ処理工程及び前記ι処理工程は、ｓｈｅｅｔ単位でデータを処理するよう構成されており、
前記θ処理工程は、１個のｓｔａｔｅを構成する全てのｓｈｅｅｔが入力される前に前記θの処理を開始する
ことを特徴とするハッシュ値生成方法。
【請求項９】
コンピュータを請求項１乃至７の何れか１項に記載のハッシュ値生成装置の各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関するものである。
【背景技術】
【０００２】
データの改ざんがないかを検証するために、暗号学的ハッシュアルゴリズムを用いて算出されるハッシュ値が利用されている。暗号学的ハッシュアルゴリズムであるＳＨＡ−１は安全性が確保できないことが既に証明されており、ＳＨＡ−２ファミリー（ＳＨＡ−２２４，ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２）も安全性が崩れる可能性が指摘されている。そこで、アメリカ国立標準技術研究所（ＮＩＳＴ）は、次世代の暗号学的ハッシュアルゴリズム（ＳＨＡ−３）を策定すべく新しいアルゴリズムを公募した。そして、２０１２年１０月に、ＫＥＣＣＡＫアルゴリズム（非特許文献１）がＳＨＡ−３のアルゴリズムとして選定された。
【０００３】
ＳＨＡ−３では、出力する暗号学的ハッシュ値の長さ（サイズ）は４種類（２２４ビット、２５６ビット、３８４ビット、５１２ビット）が規定されており、任意の長さの入力メッセージ（データ）に対して固定長の暗号学的ハッシュ値を出力する。ＫＥＣＣＡＫアルゴリズムにおいては、５つのステップ（θ、ρ、π、χ、ι）を順に適用するラウンド処理を２４回繰り返す置換関数（permutation function）が用いられている。また、ラウンド処理は、”ｓｔａｔｅ”と呼ばれる１６００ビット長のデータに対して実行される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】"The KECCAK reference", Version 3.0, January 14, 2011, （http://keccak.noekeon.org/Keccak-reference-3.0.pdf）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、上述のＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるステップπにおいては、ｓｈｅｅｔと呼ばれるデータ構造や、ｐｌａｎｅと呼ばれるデータ構造を単位として並列化することができない。そこで、ハッシュ値の生成を高速化するために、ｌａｎｅと呼ばれるデータ構造を単位としてパイプライン処理することが考えられる。具体的には、ステップπを除く、ステップθ及びステップρ（以下、θ＆ρ）及びステップχ及びステップι（以下、χ＆ι）の２つのパイプライン構成とすることが考えられる。
【０００６】
しかしながら、ｌａｎｅを単位としてハッシュ値の生成を行う場合、θ＆ρ及びχ＆ιの２つのパイプラインを並列動作させることはできず、高速化が困難であるという問題がある。また、ｌａｎｅを単位としてハッシュ値の生成を行う場合、先行するラウンドの結果の全て（”ｓｔａｔｅ”全体）が一旦メモリに書き戻されるまで、後続のラウンドを開始することが出来ない。そのため、連続する２つのラウンド間においても２つのパイプラインを並列動作させることができず、高速化が困難であるという問題がある。
【０００７】
本発明は、上述の問題点に鑑みなされたものであり、ハッシュ値生成のスループットを向上可能とする技術を提供することを目的としている。
【課題を解決するための手段】
【０００８】
上述の問題点を解決するため、本発明のハッシュ値生成装置は以下の構成を備える。すなわち、ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置において、前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段，ρ処理手段，π処理手段，χ処理手段，ι処理手段を備えており、前記θ処理手段及び前記ι処理手段は、ｓｈｅｅｔ単位でデータを処理するよう構成されており、前記θ処理手段は、前記ι処理手段から、１個のｓｔａｔｅを構成する全てのｓｈｅｅｔが入力される前に前記θの処理を開始するよう構成されている。
【発明の効果】
【０００９】
本発明によれば、ハッシュ値生成のスループットを向上可能とする技術を提供することができる。
【図面の簡単な説明】
【００１０】
【図１】ＫＥＣＣＡＫアルゴリズムの全体の概要を示す図である。
【図２】置換関数であるＫＥＣＣＡＫ−ｆ１０５の概要を説明する図である。
【図３】ラウンド処理Ｒ２０１の概要を説明する図である。
【図４】ラウンド処理Ｒ２０１の入出力時のデータ構造である”ｓｔａｔｅ”を説明する図である。
【図５】データ構造”ｐｌａｎｅ”を説明する図である。
【図６】データ構造”ｓｈｅｅｔ”を説明する図である。
【図７】データ構造”ｌａｎｅ”を説明する図である。
【図８】データ構造”ｃｏｌｕｍｎ”を説明する図である。
【図９】”ｓｔａｔｅ”を構成する”ｌａｎｅ”の順番を表す図である。
【図１０】ステップθの処理を説明する図である。
【図１１】ステップθの処理を説明する図である（ｘ＝０のビットを求める場合）。
【図１２】ステップρの処理を説明する図である。
【図１３】ステップπの処理を説明する図である。
【図１４】ステップχの処理を説明する図である。
【図１５】ステップιの処理を説明する図である。
【図１６】ステップιにおけるラウンド定数を示す図である。
【図１７】第１実施形態に係るＫＥＣＣＡＫアルゴリズムの実装例の概略構成を示す図である。
【図１８】図１７の構成をより詳細に示した図である。
【図１９】θ＆ρの処理回路の実装例を示す図である。
【図２０】χ＆ιの処理回路の実装例を示す図である。
【図２１】第１実施形態に係る実装例における各モジュールの動作タイミングチャートである。
【図２２】ＫＥＣＣＡＫアルゴリズムをｌａｎｅを単位として処理する場合の実装例の概略構成を示す図である。
【図２３】ｌａｎｅを単位として処理する場合の各モジュールの動作タイミングチャートである。
【発明を実施するための形態】
【００１１】
以下に、図面を参照して、この発明の好適な実施の形態を詳しく説明する。なお、以下の実施の形態はあくまで例示であり、本発明の範囲を限定する趣旨のものではない。
【００１２】
（第１実施形態）
本発明に係るハッシュ値生成装置の第１実施形態として、ＳＨＡ−３（ＫＥＣＣＡＫアルゴリズム）のハッシュ値を生成する装置を例に挙げて以下に説明する。なお、以下の説明において、具体的なデータ長やビット値が示されている場合があるが、本発明はこれらの具体的な値に限定されるものでは無い。
【００１３】
＜前提技術＞
まず、前提技術となるＫＥＣＣＡＫアルゴリズムについて説明する。なお、より詳細な仕様については、背景技術で示した非特許文献１に記載されている。
【００１４】
図１は、ＫＥＣＣＡＫアルゴリズムの全体の概要を示す図である。１０１は、メッセージブロック（ｍ1〜ｍt）を表している。メッセージブロック（ｍ1〜ｍt）は、ハッシュ値生成の対象となる入力メッセージを１０２４ビット毎に分割することにより生成される。
【００１５】
１０２と１０３は初期値を表しており、ここでは初期値は全ビットが０である。ここでは、初期値の全ビットが０である例で説明するが、これに限定されない。また、初期値１０２の長さは、上述のメッセージブロックの長さと同じ１０２４ビットであり、初期値１０２と初期値１０３の長さの合計は１６００ビットである。１０４は、ビット単位の排他的論理和（ＸＯＲ）演算部を表している。つまり、ＸＯＲ演算部１０４は、２つの１０２４ビットの入力データに対し、各ビットで排他的論理和を計算した結果を１０２４ビットのデータとして出力する。
【００１６】
１０５は、置換関数（permutation function）であるＫＥＣＣＡＫ−ｆを表しており、２つの入力データを受け取り、２つのデータを出力する。１０５の詳細については図２を参照して後述する。１０６は、切り取り部を表しており、１０２４ビットの入力データから、必要なサイズだけ切り出して、出力する。１０７は、このアルゴリズムの計算結果である暗号学的ハッシュ値（すなわち、ハッシュ値）を表している。
【００１７】
図２は、置換関数であるＫＥＣＣＡＫ−ｆ１０５の概要を説明する図である。２０１はラウンド処理Ｒを表しており、２４回実行される。ラウンド処理Ｒの詳細は後述する。２０２と２０３は、入力データを表している。入力データ２０２の長さは、１０２４ビットである。また、入力データ２０２と入力データ２０３の長さの合計は、１６００ビットである。入力データ２０２及び入力データ２０３の２つが結合されて、ラウンド処理Ｒ２０１に入力される。２０４と２０５は、出力データを表している。出力データ２０４の長さは、１０２４ビットである。また、出力データ２０４と出力データ２０５の長さの合計は、１６００ビットである。
【００１８】
図３は、ラウンド処理Ｒ２０１の概要を説明する図である。上述したように、ラウンド処理Ｒ２０１においては、入力データと出力データの長さは共に１６００ビットである。ラウンド処理Ｒ２０１で、入力データに対し、後述する５つのステップの処理（θ処理，ρ処理，π処理，χ処理，ι処理）を順に適用して出力データを生成する。
【００１９】
以下では、ＫＥＣＣＡＫアルゴリズムのラウンド処理で用いられるデータ構造及び上述の５つのステップの詳細について説明する。
【００２０】
図４は、ラウンド処理Ｒ２０１の入出力時のデータ構造である”ｓｔａｔｅ”を説明する図である。上述したように入力データと出力データはともに１６００ビットである。そして、当該１６００ビットのデータは、３次元配列において、幅（ｘ軸方向）５ビット、高さ（ｙ軸方向）５ビット、奥行き（ｚ軸方向）６４ビットの直方体として表される。この直方体のデータ構造を”ｓｔａｔｅ”と呼ぶ。なお、詳細は、図９を参照して後述するが、直方体として表されるｓｔａｔｅ構造に対して、１６００ビットのデータは、ｚ軸方向、ｘ軸方向、ｙ軸方向の順に割り当てられる。
【００２１】
図５は、データ構造”ｐｌａｎｅ”を説明する図である。ｐｌａｎｅ構造は、ｘ−ｚ平面に平行な、幅５ビット、高さ１ビット、奥行き６４ビットの平面構造として表される。つまり、上述のｓｔａｔｅ構造は、ｐｌａｎｅ構造をｙ軸方向に５個重ねたものとして考えることができる。
【００２２】
図６は、データ構造”ｓｈｅｅｔ”を説明する図である。ｓｈｅｅｔ構造は、ｙ−ｚ平面に平行な、幅１ビット、高さ５ビット、奥行き６４ビットの平面構造として表される。つまり、上述のｓｔａｔｅ構造は、ｓｈｅｅｔ構造をｘ軸方向に５個横に並べたものとして考えることができる。
【００２３】
図７は、データ構造”ｌａｎｅ”を説明する図である。ｌａｎｅ構造は、ｚ軸に平行な、幅１ビット、高さ１ビット、奥行き６４ビットの直線構造として表される。つまり、上述のｓｔａｔｅ構造は、ｌａｎｅ構造をｘ−ｙ平面に沿って２５個寄せ集めたものとして考えることができる。図９は、１個のｓｔａｔｅ構造を構成する２５個のｌａｎｅの順番を表す図である。
【００２４】
図８は、データ構造”ｃｏｌｕｍｎ”を説明する図である。ｃｏｌｕｍｎ構造は、ｙ軸に平行な、幅１ビット、高さ５ビット、奥行き１ビットの直線構造として表される。つまり、上述のｓｈｅｅｔ構造は、ｃｏｌｕｍｎ構造をｚ軸方向に６４個並べたものとして考えることができる。
【００２５】
なお、第１実施形態では、入力データが１６００ビットである場合について説明するが、本発明はこれに限定されるものでは無い。また、ｓｔａｔｅ構造のデータを、幅（ｘ軸方向）５ビット、高さ（ｙ軸方向）５ビット、奥行き（ｚ軸方向）６４ビットの直方体のデータ構造として扱う例について説明するが、これに限定されない。例えば、入力データが８００ビットであり、ｓｔａｔｅ構造のデータを、幅５ビット、高さ５ビット、奥行き３２ビットの直方体のデータ構造として扱ってもよい。
【００２６】
また、ｐｌａｎｅ構造、ｓｈｅｅｔ構造、ｌａｎｅ構造、ｃｏｌｕｍｎ構造は、ｓｔａｔｅ構造の幅（ｘ軸方向）、高さ（ｙ軸方向）、奥行き（ｚ軸方向）の各ビット数に応じて変更される。すなわち、ｓｔａｔｅ構造のデータが、ｘ軸方向にｍビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットである場合、ｐｌａｎｅ構造は、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットである平面構造である。ｓｈｅｅｔ構造は、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットである平面構造である。ｌａｎｅ構造は、ｘ軸方向に１ビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットの直線構造である。ｃｏｌｕｍｎ構造は、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向に１ビットの直線構造である。
【００２７】
次に、ＫＥＣＣＡＫ−ｆ１０５に入力される入力データ２０２及び入力データ２０３から、１回目のラウンド処理Ｒ２０１の入力データを作成する方法について説明する。まず、入力データ２０２及び入力データ２０３を順に連結して、１６００ビットのデータブロックを生成する。次に、１６００ビットのデータを、６４ビット毎に分割し、２５個のｌａｎｅを生成する。最後に、２５個のｌａｎｅを、図９に示す番号順にｘ−ｙ平面に沿って配列し１個のｓｔａｔｅとして組み上げる。このようにして、生成したｓｔａｔｅ構造がラウンド処理Ｒ２０１に入力されることになる。なお、２４回目のラウンド処理Ｒ２０１の出力データから、出力データ２０４及び出力データ２０５を生成する方法についても同様であるため説明は省略する。
【００２８】
次に、ラウンド処理Ｒ２０１を構成する５つのステップ（ステップθ、ステップρ、ステップπ、ステップχ、ステップι）について説明する。なお、各ステップにおいて、入力データと出力データのデータ構造は、ｓｔａｔｅ構造である。
【００２９】
図１０は、ステップθの処理を説明する図である。ステップθは、各ビットに対して近傍の２つのｃｏｌｕｍｎの和を加える処理である。より具体的には、出力ｓｔａｔｅの各ビットは、入力ｓｔａｔｅのうち、”同じ場所にあるビットの値”と、”ｘ軸方向で−１の場所にあるｃｏｌｕｍｎのビットの和”と、”ｘ軸方向で＋１かつｚ軸方向で−１の場所にあるｃｏｌｕｍｎのビットの和”との３つ値の和として計算される。ここで、和とは、ＧＦ（２）上での和のことであり、排他的論理和の演算と同一の結果になる。式で書くと、次のようになる。
【００３０】
【数１】
2014092575.tif 000003
ここで、ｘは０〜４、ｙは０〜４、ｚは０〜６３である。
【００３１】
図１１は、端の部分（例えばｘ＝０）のビットを求める場合におけるステップθの処理を説明する図である。ｘ＝０のビットを求めたい場合、”ｘ軸方向で−１の場所にあるｃｏｌｕｍｎ”は、ｓｔａｔｅの反対側、つまり”ｘ＝４の場所にあるｃｏｌｕｍｎ”に相当する。このように、ｓｔａｔｅからはみ出す座標については、ｓｔａｔｅの反対側の位置になる。つまり、座標値は同一ｓｔａｔｅ内で循環シフトする。このルールは、ｘ座標、ｙ座標、ｚ座標の何れも同じであり、また、他の４つのステップでも同様である。
【００３２】
図１２は、ステップρの処理を説明する図である。ステップρは、ｚ軸方向に各ビットの値をシフトする処理である。より具体的には、ｓｔａｔｅの各ｌａｎｅ内の値を、指定されたビットだけｚ方向に循環シフトし出力する。各ｌａｎｅにおいてシフトするビット数は、予め定められており、図１２の下段に示している数字の通りである。
【００３３】
図１３は、ステップπの処理を説明する図である。ステップπは、ｘ−ｙ平面（”ｓｌｉｃｅ”とも呼ばれる）内での各ビットの値の入れ替えを行う処理、つまり、同一ｓｔａｔｅ内の２５個のｌａｎｅを入れ替える処理を行う。より具体的には、入力ｓｔａｔｅの各ｌａｎｅに対し図１３の上段に示すように番号をふった場合、出力ｓｔａｔｅは下段に示すようになる。
【００３４】
図１４は、ステップχの処理を説明する図である。ステップχは、ｘ軸方向（”ｒｏｗ”とも呼ばれる）のビット列内での変換を行う処理であり、出力ｒｏｗの各ビットの値は、同一の入力ｒｏｗの３つのビットに基づき導出される。より具体的には、出力ｒｏｗの各ビットの値は、入力ｒｏｗの各ビットに対し、ｘ軸方向で＋１の場所にあるビットが０、かつ、ｘ軸方向で＋２の場所にあるビットが１の場合にビットの値が反転するように設定される。
【００３５】
図１５は、ステップιの処理を説明する図である。ステップιは、各ビットにラウンド定数を加える処理である。また、図１６は、ステップιにおけるラウンド定数を示す図である。ステップιは、ｘ＝ｙ＝０のｌａｎｅのビット列に対して、ラウンド毎に予め定められたラウンド定数（６４ビット値）との排他的論理和（ＸＯＲ）を適用する。具体的には、ｘ＝ｙ＝０のｌａｎｅの６４ビット値（ｚ＝６３のビットをＭＳＢ、ｚ＝０のビットをＬＳＢとする）と、図１６に示されるラウンド定数とのビット毎の排他的論理和を計算する。そして、その結果を、出力ｓｔａｔｅにおけるｘ＝ｙ＝０のｌａｎｅのビット列として設定する。
【００３６】
上述した、各ステップ（ステップθ，ステップρ，ステップπ，ステップχ，ステップι）の処理内容から、各ステップの処理を開始するにあたり以下の制約があることが分かる。
【００３７】
・ステップθは、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｘ軸方向に関して−１のｓｈｅｅｔと＋１のｓｈｅｅｔのデータを使用する。つまり、３つのｓｈｅｅｔのデータがそろった時点で、ステップθの処理を開始することができる。
【００３８】
・ステップρは、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップθ）の計算結果が１個のｌａｎｅ分出力された時点で、ステップρの処理を開始することができる。
【００３９】
・ステップπは、ｓｔａｔｅ内の各ｌａｎｅを入れ替える。そのため、前段（ステップρ）の計算結果が１個のｓｔａｔｅ全体が出力された時点で、ステップπの処理を開始することができる。
【００４０】
・ステップχは、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｘ軸方向で＋１のｌａｎｅ及びｘ軸方向で＋２のｌａｎｅを使用する。そのため、３つのｓｈｅｅｔのデータがそろった時点で、ステップχの処理を開始することできる。
【００４１】
・ステップιは、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップχ）の計算結果が１個のｌａｎｅ分出力された時点で、ステップιの処理を開始することができる。
【００４２】
すなわち、ステップθ及びステップχにおいては、前段のステップから少なくとも３つのｓｈｅｅｔ分のデータが出力され受け取った段階で、処理を開始することができることが分かる。
【００４３】
つまり、ｓｈｅｅｔ単位で処理を行うことにより、先行するラウンドの最終段（ステップι）から３つのｓｈｅｅｔのデータを出力した時点で、後続するラウンドの最前段（ステップθ）の実行を開始することが可能であることが理解できる。そこで、以下では、ラウンド処理をｓｈｅｅｔ単位で行う構成について説明する。
【００４４】
＜装置構成および動作＞
図１７は、第１実施形態に係るＫＥＣＣＡＫアルゴリズムの実装例の概略構成を示す図である。１９０１は、入力データを表している。１９０７は、入力データ１９０１である、１個のｓｔａｔｅ分のデータを保持し、ｓｈｅｅｔ構造を単位として、データを並び替える処理ブロックである。具体的には、１６００ビットのデータを、６４ビット毎に分割し、２５個のｌａｎｅを生成する。次に、２５個のｌａｎｅを、図９に示す番号順にｘ−ｙ平面に沿って配列し、１個のｓｈｅｅｔを生成する。つまり、入力データ順に、ｙ−ｚ平面に沿って、ｓｈｅｅｔ構造のデータを作るのではなく、入力データを並び替える。尚、少なくとも、１つ目のｓｈｅｅｔ構造のデータが生成できるデータが保持されれば、１つ目のｓｈｅｅｔ構造のデータを出力するようにしてよい。１９０６は、出力データを表しており、計算が完了したときに、ｓｈｅｅｔ構造を単位として出力する処理ブロックである。
【００４５】
１９０２は、排他的論理和（ＸＯＲ）演算部を表しており、ラウンド処理を２４回実行するたびに、メッセージブロックと内部データの排他的論理和を計算する。１９０３は、ステップθ及びステップρをまとめて行う処理ブロックである。１９０４は、内部データ全体を保持するレジスタと、ステップπを行う演算部を含む処理ブロックである。１８０５は、ステップχとステップιをまとめて行う処理ブロックである。
【００４６】
図１８は、図１７の構成をより詳細に示した図である。２００１は、入力データを表している。２００９は、入力データ２００１を、ｓｈｅｅｔ構造を単位として、並び替える。２００９は、１９０７と同じブロックなので、説明は省略する。また、２００９は、１クロック毎に１個のｓｈｅｅｔ構造を単位として出力する。ここでは、ｘ座標の小さいｓｈｅｅｔから順に出力する。２００２は、マルチプレクサを表しており、入力データと内部ｓｔａｔｅとの間で排他的論理和の計算をするときは入力データをそのまま出力し、それ以外のときは０を出力する。
【００４７】
２００４は、ステップθ及びステップρを計算するための回路（以下、θ＆ρ回路と呼ぶ）である。上述のように、回路２００４には、ｘ座標の小さい順にｓｈｅｅｔ構造のデータが入力される（ｘ＝０，１，２，３，４の順番）。ただし、出力されるｓｈｅｅｔの順番は、ｘ座標が、ｘ＝１，２，３，４，０の順番である。２００５は、１段で１個のｓｈｅｅｔの情報を記憶する５段構成のレジスタを表しており、１クロック毎に、記憶したデータを後段に伝える。
【００４８】
２００６は、ステップπを処理するための回路を表している。レジスタ２００５は、通常は上流から入力されるデータを保持するが、ステップπを実行するときは、ステップπ２００６の出力データを保持するよう構成される。
【００４９】
２００７は、ステップχとステップιを処理するための回路（以下、χ＆ι回路と呼ぶ）であり、１個のｓｈｅｅｔ構造を単位として結果を出力する。２００８はマルチプレクサを表しており、ハッシュ値の計算開始時には初期化のため０を出力し、それ以外の時は計算途中のデータをそのまま出力する。
【００５０】
図１９は、θ＆ρの処理回路の実装例を示す図である。θ＆ρ回路２００４は、注目ｓｈｅｅｔと当該注目ｓｈｅｅｔに対してｘ軸方向に−１と＋１にある２個のｓｈｅｅｔを使用して、出力データを算出する。
【００５１】
２１０１は、入力データを表している。上述したように、入力データとしては、１クロック毎に１個のｓｈｅｅｔが入力される。２１０２は、組み合わせ回路を表しており、上述したステップθとステップρの演算を実際に行う論理回路である。
【００５２】
２１０３は、１段で１個のｓｈｅｅｔの情報を記憶する２段構成のレジスタを表している。２１０４は、１段で１個のｓｈｅｅｔの情報を記憶する２段構成のレジスタを表しており、ここでは、ｘ＝０とｘ＝１のｓｈｅｅｔの情報を記憶している。
【００５３】
２１０５は、マルチプレクサを表しており、処理開始からの最初の５クロックでは入力データ２１０１をそのまま出力し、引き続く２クロックは２１０４からのデータを出力する。２１０６は、出力データを表しており、１個のｓｈｅｅｔを単位として出力される。なお、図１９に示す構成においては、ｓｈｅｅｔの出力順序は、ｘ座標で１，２，３，４，０の順番である。すなわち、入力データ２１０１から受け取るｓｈｅｅｔの順番がｘ座標でｘ＝０，１，２，３，４の順番であるため、最初に出力可能となるｓｈｅｅｔはｘ＝１のｓｈｅｅｔだからである。
【００５４】
図２０は、χ＆ιの処理回路の実装例を示す図である。χ＆ι回路２００７は、注目ｓｈｅｅｔと当該注目ｓｈｅｅｔに対してｘ軸方向に＋１と＋２にある２個のｓｈｅｅｔを使用して、出力データを算出する。
【００５５】
２２０１は、入力データを表している。上述したように、入力データとしては、１クロック毎に、前段のレジスタから３ｓｈｅｅｔ分入力される。２２０２は、組み合わせ回路を表しており、上述したステップχとステップιの演算を実際に行う論理回路である。２２０３は、１段で１個のｓｈｅｅｔの情報を記憶する２段構成のレジスタを表しており、ｘ座標で０と１のｓｈｅｅｔを記憶する。２２０４は、マルチプレクサを表しており、処理開始からの最初の４クロックは入力データ２２０１をそのまま出力し、引き続く１クロックは、レジスタ２２０３の値を出力する。２２０５は、マルチプレクサを表しており、処理開始からの最初の３クロックは入力データ２２０１をそのまま出力し、引き続く２クロックは、レジスタ２２０３の値を出力する。２２０６は、出力データを表しており、１個のｓｈｅｅｔを単位として出力される。
【００５６】
上述したように、第１実施形態の実装例の特徴として、χ＆ι回路２００７の出力からθ＆ρ回路２００４の入力までの経路は、組み合わせ回路のみ接続されていることが挙げられる。すなわち、ラッチ回路を含まない構成であるため、１クロック内でデータを通過させることが可能な構成となっている。
【００５７】
図２１は、第１実施形態に係る実装例における各モジュールの動作タイミングチャートである。なお、θ＆ρ回路２００４及びχ＆ι回路２００７はパイプライン処理されるよう構成されている。この図より、χ＆ι回路２００７が１個のｓｈｅｅｔを出力してから２クロック後に、θ＆ρ回路２００４が１個のｓｈｅｅｔ出力できることがわかる。つまり、θ＆ρ回路２００４は、３個のｓｈｅｅｔが入力されたとき処理を開始でき、θ＆ρ回路２００４とχ＆ι回路２００７との並列動作が実現されていることがわかる。また、１回のラウンド処理にかかる時間が、平均８クロックであることもわかる。
【００５８】
＜ｌａｎｅ単位で処理を行った場合の例＞
以下では、上述の第１実施形態の実装例に対する比較対象として、ｌａｎｅを単位として処理する実装例について説明する。
【００５９】
図２２は、ＫＥＣＣＡＫアルゴリズムをｌａｎｅを単位として処理する場合の実装例の概略構成を示す図である。なお、５つのステップ（θ，ρ，π，χ，ι）の処理は上述したものと同じであるため説明は省略する。
【００６０】
１８０１は、入力データを表している。入力データ１８０１から、１クロック毎に１個のｌａｎｅ（６４ビット長のデータ）を受信する。なお、ｌａｎｅは、１個のｓｔａｔｅの中から図９に示される順に受信される。
【００６１】
１８０２は、排他的論理和の処理を表しており、ラウンド処理を２４回実行するたびに、メッセージブロックと内部データの排他的論理和を計算する演算部である。
【００６２】
１８０３は、内部データ全体を保持するレジスタと、ステップπを実行する処理ブロックである。ただし、上述したように、ステップπの処理は、ステップρの処理を完了した後でのみ実行可能となる。１８０４は、ステップθとステップρを実行する処理ブロックである。
【００６３】
１８０５は、ステップχとステップιを実行する処理ブロックである。１８０６は、マルチプレクサであり、ラウンド処理の前半は１８０４からのデータを出力し、後半は１８０５からのデータを出力する。１８０７は、出力データを表しており、計算が完了したときに、１個のｌａｎｅを単位として出力される。
【００６４】
図２３は、ｌａｎｅを単位として処理する場合の各モジュールの動作タイミングチャートである。この図より、θ＆ρ回路１８０４とχ＆ι回路１８０５とのは別々の期間に動作し、同時には動作していないことがわかる。また、１回のラウンド処理にかかる時間が、５１クロックであることもわかる。
【００６５】
＜比較＞
図２１と図２３とを比較すると分かるように、第１実施形態の実装例の構成を用いることにより処理スループットが向上することがわかる。
【００６６】
すなわち、
・θ＆ρ回路及びχ＆ι回路の２つの処理回路の並列動作により回路利用効率が向上可能となる。
・より少ないクロック数（時間）で１回のラウンド処理を実行することが可能となる。
ことが分かる。その結果、処理スループットを向上させることが可能となっている。
【００６７】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行する処理である。
【図１】
2014092575.tif 000004
【図２】
2014092575.tif 000005
【図３】
2014092575.tif 000006
【図４】
2014092575.tif 000007
【図５】
2014092575.tif 000008
【図６】
2014092575.tif 000009
【図７】
2014092575.tif 000010
【図８】
2014092575.tif 000011
【図９】
2014092575.tif 000012
【図１０】
2014092575.tif 000013
【図１１】
2014092575.tif 000014
【図１２】
2014092575.tif 000015
【図１３】
2014092575.tif 000016
【図１４】
2014092575.tif 000017
【図１５】
2014092575.tif 000018
【図１６】
2014092575.tif 000019
【図１７】
2014092575.tif 000020
【図１８】
2014092575.tif 000021
【図１９】
2014092575.tif 000022
【図２０】
2014092575.tif 000023
【図２１】
2014092575.tif 000024
【図２２】
2014092575.tif 000025
【図２３】
2014092575.tif 000026