(57)【要約】【課題】  本発明は、ＫＥＣＣＡＫアルゴリズムによるハッシュ値生成のスループットを向上可能とする技術を提供することを目的としている。【解決手段】  ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置であって、前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段、ρ処理手段，π処理手段，χ処理手段，ι処理手段を有し、奇数回目のラウンド処理におけるπ処理手段は、ｐｌａｎｅ内でのｌａｎｅの入れ替えと、左右反転処理を行い、前記奇数回目のラウンド処理におけるχ処理手段は、ｒｏｗのビット列内での変換を行い、偶数回目のラウンド処理におけるπ処理手段は、ｓｈｅｅｔ内でのｌａｎｅの入れ替えを行う。【選択図】  図９
2015114429.tif 000002
【特許請求の範囲】
【請求項１】
ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置であって、
前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段、ρ処理手段，π処理手段，χ処理手段，ι処理手段を有し、
奇数回目のラウンド処理におけるπ処理手段は、ｐｌａｎｅ内でのｌａｎｅの入れ替えと、左右反転処理を行い、
前記奇数回目のラウンド処理におけるχ処理手段は、ｒｏｗのビット列内での変換を行い、
偶数回目のラウンド処理におけるπ処理手段は、ｓｈｅｅｔ内でのｌａｎｅの入れ替えを行うことを特徴とするハッシュ生成装置。
【請求項２】
前記偶数回目のラウンド処理におけるθ処理手段は、各ビットに対して近傍の２つのｒｏｗの和を加えることを特徴とする請求項１に記載のハッシュ生成装置。
【請求項３】
前記θ処理手段、前記ρ処理手段、前記χ処理手段、前記ι処理手段は、ｌａｎｅ単位で処理することを特徴とする請求項２に記載のハッシュ値生成装置。
【請求項４】
前記θ処理手段は、ｒｏｗ和算出処理を行うθ１処理手段と、ｒｏｗ和加算処理を行うθ２処理手段とを有し、
前記ラウンド処理において、前記π処理手段は、前記θ２処理手段と前記ρ処理手段より前に、実行され、
前記ρ処理手段は、前記π処理手段で入替処理されたｌａｎｅに対して処理を行うことを特徴とする請求項１に記載のハッシュ生成装置。
【請求項５】
前記θ１処理手段、前記θ２処理手段、前記ρ処理手段、前記χ処理手段、前記ι処理手段は、ｌａｎｅ単位で処理することを特徴とする請求項４に記載のハッシュ値生成装置。
【請求項６】
前記ｐｌａｎｅは、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向に１ビットの構造として表され、
前記ｓｈｅｅｔは、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向に１ビットの構造として表され、
前記ｌａｎｅは、ｘ軸方向に１ビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットの構造として表され、
前記ｒｏｗは、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向に１ビットの構造として表される請求項１乃至５の何れか１項に記載のハッシュ値生成装置。
【請求項７】
ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置の制御方法であって、
前記ハッシュ値生成装置は、前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段、ρ処理手段，π処理手段，χ処理手段，ι処理手段を有し、
奇数回目のラウンド処理におけるπ処理手段が、ｐｌａｎｅ内でのｌａｎｅの入れ替えと、左右反転処理を行う工程と、
前記奇数回目のラウンド処理におけるχ処理手段が、ｒｏｗのビット列内での変換を行う工程と、
偶数回目のラウンド処理におけるπ処理手段が、ｓｈｅｅｔ内でのｌａｎｅの入れ替えを行う工程を有することを特徴とするハッシュ生成装置の制御方法。
【請求項８】
前記偶数回目のラウンド処理におけるθ処理手段が、各ビットに対して近傍の２つのｒｏｗの和を加える工程を有することを特徴とする請求項７に記載のハッシュ生成装置の制御方法。
【請求項９】
前記θ処理手段は、ｒｏｗ和算出処理を行うθ１処理手段と、ｒｏｗ和加算処理を行うθ２処理手段とを有し、
前記ラウンド処理において、前記π処理手段における処理工程は、前記θ２処理手段における処理工程と前記ρ処理手段における処理工程より前に、実行され、
前記ρ処理手段における処理工程は、前記π処理手段における処理工程で入替処理されたｌａｎｅに対して処理を行うことを特徴とする請求項７に記載のハッシュ生成装置の制御方法。
【請求項１０】
前記ｐｌａｎｅは、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向に１ビットの構造として表され、
前記ｓｈｅｅｔは、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向に１ビットの構造として表され、
前記ｌａｎｅは、ｘ軸方向に１ビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットの構造として表され、
前記ｒｏｗは、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向に１ビットの構造として表される請求項７乃至９の何れか１項に記載のハッシュ値生成装置の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関するものである。
【背景技術】
【０００２】
データの改ざんがないかを検証するために、暗号学的ハッシュアルゴリズムを用いて算出されるハッシュ値が利用されている。暗号学的ハッシュアルゴリズムであるＳＨＡ−１は安全性が確保できないことが既に証明されており、ＳＨＡ−２ファミリー（ＳＨＡ−２２４，ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２）も安全性が崩れる可能性が指摘されている。そこで、アメリカ国立標準技術研究所（ＮＩＳＴ）は、次世代の暗号学的ハッシュアルゴリズム（ＳＨＡ−３）を策定すべく新しいアルゴリズムを公募した。そして、２０１２年１０月に、ＫＥＣＣＡＫアルゴリズム（非特許文献１）がＳＨＡ−３のアルゴリズムとして選定された。
【０００３】
ＳＨＡ−３では、任意の長さの入力メッセージ（データ）に対して固定長の暗号学的ハッシュ値を出力する。ＫＥＣＣＡＫアルゴリズムにおいては、５つのステップ（θ、ρ、π、χ、ι）を順に適用するラウンド処理を２４回繰り返す置換関数（ｐｅｒｍｕｔａｔｉｏｎ  ｆｕｎｃｔｉｏｎ）が用いられている。また、ラウンド処理は、”ｓｔａｔｅ”と呼ばれる１６００ビット長のデータに対して実行される。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】“Ｔｈｅ  ＫＥＣＣＡＫ  ｒｅｆｅｒｅｎｃｅ”，  Ｖｅｒｓｉｏｎ  ３．０，  Ｊａｎｕａｒｙ  １４，  ２０１１，  （ｈｔｔｐ：／／ｋｅｃｃａｋ．ｎｏｅｋｅｏｎ．ｏｒｇ／Ｋｅｃｃａｋ−ｒｅｆｅｒｅｎｃｅ−３．０．ｐｄｆ）
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ところで、上述のＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるステップπにおいては、ｌａｎｅと呼ばれるデータ構造を単位として、ｓｌｉｃｅと呼ばれる平面上でアドレス変換を実施する処理を行う。このとき、ｌａｎｅ毎にデータが入力される場合には、データハザードにより、ｓｔａｔｅデータ全体が揃わなければデータが出力できない。結果的にステップπにはｓｔａｔｅ全体を保持するバッファが必要となり、ステップπの前後で処理をパイプライン化することはできず、高速化が困難であるという問題がある。また、ｌａｎｅを単位としてハッシュ値の生成を行う場合、先行するラウンドの結果の全て（”ｓｔａｔｅ”全体）が一旦メモリに書き戻されるまで、後続のラウンドを開始することが出来ない。そのため、連続する２つのラウンド間においてもパイプライン動作させることができず、高速化が困難であるという問題がある。
【０００６】
本発明は、上述の問題点に鑑みなされたものであり、ハッシュ値生成のスループットを向上可能とする技術を提供することを目的としている。
【課題を解決するための手段】
【０００７】
本発明に係るハッシュ値生成装置は、ＫＥＣＣＡＫアルゴリズムに基づきハッシュ値を生成するハッシュ値生成装置であって、前記ＫＥＣＣＡＫアルゴリズムのラウンド処理に含まれるθ，ρ，π，χ，ιの５つの処理をそれぞれ実行するθ処理手段、ρ処理手段，π処理手段，χ処理手段，ι処理手段を有し、  奇数回目のラウンド処理におけるπ処理手段は、ｐｌａｎｅ内でのｌａｎｅの入れ替えと、左右反転処理を行い、前記奇数回目のラウンド処理におけるχ処理手段は、ｒｏｗのビット列内での変換を行い、偶数回目のラウンド処理におけるπ処理手段は、ｓｈｅｅｔ内でのｌａｎｅの入れ替えを行うことを特徴とする。
【発明の効果】
【０００８】
本発明によれば、従来のＫＥＣＣＡＫアルゴリズムをそのまま実装するのと比べ、スループット向上が可能となる。
【図面の簡単な説明】
【０００９】
【図１】ＫＥＣＣＡＫアルゴリズムを説明するための図である。
【図２】データ構造を説明する図である。
【図３】ステップθの処理を説明する図である。
【図４】ステップρの処理を説明する図である。
【図５】ステップπの処理を説明する図である。
【図６】ステップχの処理を説明する図である。
【図７】ステップιの処理を説明する図である。
【図８】ステップιにおけるラウンド定数を示す図である。
【図９】第１実施形態に係る置換関数ＫＥＣＣＡＫ−ｆ１７０３の概要を説明する図である。
【図１０】ステップπ’１７０４の処理を説明する図である。
【図１１】ステップχ’１７０５の処理を説明する図である。
【図１２】ステップθ’１７０６の処理を説明する図である。
【図１３】ステップρ’１７０７の処理を説明する図である。
【図１４】ステップπ’’１７０８の処理を説明する図である。
【図１５】第１の実施形態に係るＫＥＣＣＡＫアルゴリズムの実装例の概略構成を示す図である。
【図１６】従来例に係るＫＥＣＣＡＫアルゴリズムの実装例の概略構成を示す図である。
【図１７】動作タイミングチャートである。
【図１８】第２の実施形態に係る置換関数ＫＥＣＣＡＫ−ｆ２９０３の概要を説明する図である。
【図１９】ステップθ’３００４の処理を説明する図である。
【図２０】ステップρ’３００５の処理を説明する図である。
【図２１】ステップθ’’３００６の処理を説明する図である。
【図２２】ステップρ’’３００７の処理を説明する図である。
【図２３】第２の実施形態に係るＫＥＣＣＡＫアルゴリズムの実装例の概略構成を示す図である。
【発明を実施するための形態】
【００１０】
以下に、図面を参照して、この発明の好適な実施の形態を詳しく説明する。なお、以下の実施の形態はあくまで例示であり、本発明の範囲を限定する趣旨のものではない。
【００１１】
（第１実施形態）
本発明に係るハッシュ値生成装置の第１実施形態として、ＳＨＡ−３（ＫＥＣＣＡＫアルゴリズム）のハッシュ値を生成する装置を例に挙げて以下に説明する。なお、以下の説明において、具体的なデータ長やビット値が示されている場合があるが、本発明はこれらの具体的な値に限定されるものでは無い。
【００１２】
まず、ＫＥＣＣＡＫアルゴリズムについて説明する。なお、より詳細な仕様については、背景技術で示した非特許文献１に記載されている。
【００１３】
図１（ａ）は、ＫＥＣＣＡＫアルゴリズムの全体の概要を示す図である。１０１は、メッセージブロック（ｍ１〜ｍｔ）を表している。メッセージブロック（ｍ１〜ｍｔ）は、ハッシュ値生成の対象となる入力メッセージを１０２４ビット毎に分割することにより生成される。
【００１４】
１０２と１０３は初期値を表しており、ここでは初期値は全ビットが０である。ここでは、初期値の全ビットが０である例で説明するが、これに限定されない。また、初期値１０２の長さは、上述のメッセージブロックの長さと同じ１０２４ビットであり、初期値１０２と初期値１０３の長さの合計は１６００ビットである。１０４は、ビット単位の排他的論理和（ＸＯＲ）演算部を表している。つまり、ＸＯＲ演算部１０４は、２つの１０２４ビットの入力データに対し、各ビットで排他的論理和を計算した結果を１０２４ビットのデータとして出力する。
【００１５】
１０５は、置換関数（ｐｅｒｍｕｔａｔｉｏｎ  ｆｕｎｃｔｉｏｎ）であるＫＥＣＣＡＫ−ｆを表しており、２つの入力データを受け取り、２つのデータを出力する。１０５の詳細については図１（ｂ）を参照して後述する。１０６は、切り取り部を表しており、１０２４ビットの入力データから、必要なサイズだけ切り出して、出力する。１０７は、このアルゴリズムの計算結果である暗号学的ハッシュ値（すなわち、ハッシュ値）を表している。
【００１６】
図１（ｂ）は、置換関数であるＫＥＣＣＡＫ−ｆ１０５の概要を説明する図である。２０１はラウンド処理Ｒを表しており、２４回実行される。ラウンド処理Ｒの詳細は後述する。２０２と２０３は、入力データを表している。入力データ２０２の長さは、１０２４ビットである。また、入力データ２０２と入力データ２０３の長さの合計は、１６００ビットである。入力データ２０２及び入力データ２０３の２つが結合されて、ラウンド処理Ｒ２０１に入力される。２０４と２０５は、出力データを表している。出力データ２０４の長さは、１０２４ビットである。また、出力データ２０４と出力データ２０５の長さの合計は、１６００ビットである。
【００１７】
図１（ｃ）は、ラウンド処理Ｒ２０１の概要を説明する図である。上述したように、ラウンド処理Ｒ２０１においては、入力データと出力データの長さは共に１６００ビットである。ラウンド処理Ｒ２０１で、入力データに対し、後述する５つのステップの処理（θ処理３０１，ρ処理３０２，π処理３０３，χ処理３０４，ι処理３０５）を順に適用して出力データを生成する。
【００１８】
以下では、ＫＥＣＣＡＫアルゴリズムのラウンド処理で用いられるデータ構造及び上述の５つのステップの詳細について説明する。
【００１９】
図２（ａ）は、ラウンド処理Ｒ２０１の入出力時のデータ構造である”ｓｔａｔｅ”を説明する図である。上述したように入力データと出力データはともに１６００ビットである。そして、当該１６００ビットのデータは、３次元配列において、幅（ｘ軸方向）５ビット、高さ（ｙ軸方向）５ビット、奥行き（ｚ軸方向）６４ビットの直方体として表される。この直方体のデータ構造を”ｓｔａｔｅ”と呼ぶ。なお、詳細は、図２（ｆ）を参照して後述するが、直方体として表されるｓｔａｔｅ構造に対して、１６００ビットのデータは、ｚ軸方向、ｘ軸方向、ｙ軸方向の順に割り当てられる。
【００２０】
図２（ｂ）は、データ構造”ｐｌａｎｅ”を説明する図である。ｐｌａｎｅ構造は、ｘ−ｚ平面に平行な、幅５ビット、高さ１ビット、奥行き６４ビットの平面構造として表される。つまり、上述のｓｔａｔｅ構造は、ｐｌａｎｅ構造をｙ軸方向に５個重ねたものとして考えることができる。
【００２１】
図２（ｃ）は、データ構造”ｓｈｅｅｔ”を説明する図である。ｓｈｅｅｔ構造は、ｙ−ｚ平面に平行な、幅１ビット、高さ５ビット、奥行き６４ビットの平面構造として表される。つまり、上述のｓｔａｔｅ構造は、ｓｈｅｅｔ構造をｘ軸方向に５個横に並べたものとして考えることができる。
【００２２】
図２（ｄ）は、データ構造”ｌａｎｅ”を説明する図である。ｌａｎｅ構造は、ｚ軸に平行な、幅１ビット、高さ１ビット、奥行き６４ビットの直線構造として表される。つまり、上述のｓｔａｔｅ構造は、ｌａｎｅ構造をｘ−ｙ平面に沿って２５個寄せ集めたものとして考えることができる。図２（ｆ）は、１個のｓｔａｔｅ構造を構成する２５個のｌａｎｅの順番を表す図である。
【００２３】
図２（ｅ）は、データ構造”ｃｏｌｕｍｎ”を説明する図である。ｃｏｌｕｍｎ構造は、ｙ軸に平行な、幅１ビット、高さ５ビット、奥行き１ビットの直線構造として表される。つまり、上述のｓｈｅｅｔ構造は、ｃｏｌｕｍｎ構造をｚ軸方向に６４個並べたものとして考えることができる。
【００２４】
なお、第１実施形態では、入力データが１６００ビットである場合について説明するが、本発明はこれに限定されるものでは無い。また、ｓｔａｔｅ構造のデータを、幅（ｘ軸方向）５ビット、高さ（ｙ軸方向）５ビット、奥行き（ｚ軸方向）６４ビットの直方体のデータ構造として扱う例について説明するが、これに限定されない。例えば、入力データが８００ビットであり、ｓｔａｔｅ構造のデータを、幅５ビット、高さ５ビット、奥行き３２ビットの直方体のデータ構造として扱ってもよい。
【００２５】
また、ｐｌａｎｅ構造、ｓｈｅｅｔ構造、ｌａｎｅ構造、ｃｏｌｕｍｎ構造は、ｓｔａｔｅ構造の幅（ｘ軸方向）、高さ（ｙ軸方向）、奥行き（ｚ軸方向）の各ビット数に応じて変更される。すなわち、ｓｔａｔｅ構造のデータが、ｘ軸方向にｍビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットである場合、ｐｌａｎｅ構造は、ｘ軸方向にｍビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットである平面構造である。ｓｈｅｅｔ構造は、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向にｓビットである平面構造である。ｌａｎｅ構造は、ｘ軸方向に１ビット、ｙ軸方向に１ビット、ｚ軸方向にｓビットの直線構造である。ｃｏｌｕｍｎ構造は、ｘ軸方向に１ビット、ｙ軸方向にｎビット、ｚ軸方向に１ビットの直線構造である。
【００２６】
次に、ＫＥＣＣＡＫ−ｆ１０５に入力される入力データ２０２及び入力データ２０３から、１回目のラウンド処理Ｒ２０１の入力データを作成する方法について説明する。まず、入力データ２０２及び入力データ２０３を順に連結して、１６００ビットのデータブロックを生成する。次に、１６００ビットのデータを、６４ビット毎に分割し、２５個のｌａｎｅを生成する。最後に、２５個のｌａｎｅを、図２（ｆ）に示す番号順にｘ−ｙ平面に沿って配列し１個のｓｔａｔｅとして組み上げる。このようにして、生成したｓｔａｔｅ構造がラウンド処理Ｒ２０１に入力されることになる。なお、２４回目のラウンド処理Ｒ２０１の出力データから、出力データ２０４及び出力データ２０５を生成する方法についても同様であるため説明は省略する。
【００２７】
次に、ラウンド処理Ｒ２０１を構成する５つのステップ（ステップθ、ステップρ、ステップπ、ステップχ、ステップι）の処理について説明する。なお、各ステップにおいて、入力データと出力データのデータ構造は、ｓｔａｔｅ構造である。
【００２８】
図３（ａ）は、ステップθの処理（θ処理３０１）を説明する図である。ステップθは、各ビットに対して近傍の２つのｃｏｌｕｍｎの和を加える処理である。より具体的には、出力ｓｔａｔｅの各ビットは、次のように計算される。入力ｓｔａｔｅのうち、”同じ場所にあるビットの値”と、”ｘ軸方向で−１の場所にあるｃｏｌｕｍｎのビットの和”と、”ｘ軸方向で＋１かつｚ軸方向で−１の場所にあるｃｏｌｕｍｎのビットの和”との３つ値の和として計算される。ここで、和とは、ＧＦ（２）上での和のことであり、排他的論理和の演算と同一の結果になる。式で書くと、次のようになる。
【００２９】
【数１】
2015114429.tif 000003
【００３０】
ここで、ｘは０〜４、ｙは０〜４、ｚは０〜６３である。
【００３１】
図３（ｂ）は、端の部分（例えばｘ＝０）のビットを求める場合におけるステップθの処理を説明する図である。ｘ＝０のビットを求めたい場合、”ｘ軸方向で−１の場所にあるｃｏｌｕｍｎ”は、ｓｔａｔｅの反対側、つまり”ｘ＝４の場所にあるｃｏｌｕｍｎ”に相当する。このように、ｓｔａｔｅからはみ出す座標については、ｓｔａｔｅの反対側の位置になる。つまり、座標値は同一ｓｔａｔｅ内で循環シフトする。このルールは、ｘ座標、ｙ座標、ｚ座標の何れも同じであり、また、他の４つのステップでも同様である。
【００３２】
図４は、ステップρの処理（ρ処理３０２）を説明する図である。ステップρは、ｚ軸方向に各ビットの値をシフトする処理である。より具体的には、図４（ａ）に示すように、ｓｔａｔｅの各ｌａｎｅ内の値を、指定されたビットだけｚ方向に循環シフトし出力する。各ｌａｎｅにおいてシフトするビット数は、予め定められており、図４（ｂ）に示している数字の通りである。尚、ρ処理を実行するために、予め、保持部に、図４（ｃ）に示すような、シフト量を示すテーブルを保持しておき、保持しているテーブルを用いて、ρ処理を実行する。
【００３３】
図５は、ステップπの処理（π処理３０３）を説明する図である。ステップπは、ｘ−ｙ平面（”ｓｌｉｃｅ”とも呼ばれる）内での各ビットの値の入れ替えを行う処理、つまり、同一ｓｔａｔｅ内の２５個のｌａｎｅを入れ替える処理を行う。より具体的には、入力ｓｔａｔｅの各ｌａｎｅに対し図５（ａ）の上段に示すように番号をふった場合、出力ｓｔａｔｅは下段に示すようになる。尚、π処理を実行するために、予め、保持部に、図５（ｂ）に示すような、入替先を示すテーブルを保持しておき、保持しているテーブルを用いて、π処理を実行する。
【００３４】
図６は、ステップχの処理（χ処理３０４）を説明する図である。ステップχは、ｘ軸方向（”ｒｏｗ”とも呼ばれる）のビット列内での変換を行う処理であり、出力ｒｏｗの各ビットの値は、同一の入力ｒｏｗの３つのビットに基づき導出される。より具体的には、出力ｒｏｗの各ビットの値は、入力ｒｏｗの各ビットに対し、ｘ軸方向で＋１の場所にあるビットが０、かつ、ｘ軸方向で＋２の場所にあるビットが１の場合にビットの値が反転するように設定される。
【００３５】
図７は、ステップιの処理（ι処理３０５）を説明する図である。ステップιは、各ビットにラウンド定数を加える処理である。また、図８は、ステップιにおけるラウンド定数を示す図である。ステップιは、ｘ＝ｙ＝０のｌａｎｅのビット列に対して、ラウンド毎に予め定められたラウンド定数（６４ビット値）との排他的論理和（ＸＯＲ）を適用する。具体的には、ｘ＝ｙ＝０のｌａｎｅの６４ビット値（ｚ＝６３のビットをＭＳＢ、ｚ＝０のビットをＬＳＢとする）と、図８に示されるラウンド定数とのビット毎の排他的論理和を計算する。そして、その結果を、出力ｓｔａｔｅにおけるｘ＝ｙ＝０のｌａｎｅのビット列として設定する。
【００３６】
上述した、各ステップ（ステップθ，ステップρ，ステップπ，ステップχ，ステップι）の処理内容から、各ステップの処理を開始するにあたり以下の制約があることが分かる。
【００３７】
・ステップθは、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｘ軸方向に関して−１のｓｈｅｅｔと＋１のｓｈｅｅｔのデータを使用する。そのため、最初の３つ分のｓｈｅｅｔが完全に揃う時、つまり、２５個のｌａｎｅのうち２３個のｌａｎｅを前段の処理から受け取った時、ステップθの処理を開始することができる。
【００３８】
・ステップρは、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップθ）の計算結果が１個のｌａｎｅ分出力された時点で、ステップρの処理を開始することができる。
【００３９】
・ステップπは、ｓｔａｔｅ内の各ｌａｎｅを入れ替える。そのため、前段（ステップρ）の計算結果が１個のｓｔａｔｅ全体、すなわち２５個のｌａｎｅ分出力された時点で、ステップπの処理を開始することができる。
【００４０】
・ステップχは、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｘ軸方向で＋１のｌａｎｅ及びｘ軸方向で＋２のｌａｎｅを使用する。そのため、３個目のｌａｎｅのデータを受け取った時点で、ステップχの処理を開始することできる。
【００４１】
・ステップιは、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップχ）の計算結果が１個のｌａｎｅ分出力された時点で、ステップιの処理を開始することができる。
【００４２】
すなわち、ステップθ及びステップπ及びステップχにおいては、前段のステップの計算結果がそれぞれ２３個、２５個、３個のｌａｎｅ分出力されるまで、処理を開始することができない。このように、特にステップθ及びステップπの２処理の実行開始は、前段の処理開始から長い時間待った後でなければならない。
【００４３】
つまり、ステップθとステップπのどちらかの開始時間を早めることができれば、スループットが向上する。しかし、ＫＥＣＣＡＫアルゴリズムの仕様と同一の演算順序では早めることができない。そのため、スループットを向上するためには、演算順序をＫＥＣＣＡＫアルゴリズムとは別のものに変更する必要がある。
【００４４】
次に、関数ｆ´１７０３について説明する。関数ｆ´１７０３は、本実施形態で用いる処理であり、関数ｆ１０５と同じ結果になるように設計されているが、ＫＥＣＣＡＫアルゴリズムの仕様とは処理内容が異なる。
図９（ａ）は、関数ｆ´１７０３の概要を説明する図である。従来の奇数回目のラウンド処理をＲ’  ｏｄｄ１７０１  、偶数回目のラウンド処理をＲ’  ｅｖｅｎ１７０２  に置き換え、それらを交互に、１２回ずつ実行するアルゴリズムである。図９（ｂ）にラウンド処理Ｒ’ｏｄｄ１７０１およびラウンド処理Ｒ’ｅｖｅｎ１７０２の処理内容を示す。ただし、図中のステップπ’１７０４およびステップπ’’１７０８  は処理開始の制約を緩和したステップπである。また、ステップθ’１７０６、ステップρ’１７０７、およびステップχ’１７０５  はステップπの処理の変更に合わせて補正を施したステップθ、ステップρ、ステップχ  である。
【００４５】
まずは、奇数ラウンドＲ’ｏｄｄ１７０１の処理について説明する。奇数ラウンドＲ’ｏｄｄ１７０１は、入力データに対し、５つのステップの処理（θ処理３０１、ρ処理３０２、π´処理１７０４、χ´処理１７０５、ι処理３０５）を適用して出力データを生成する。ここで、奇数ラウンドＲ’ｏｄｄ１７０１におけるθ処理３０１、ρ処理３０２、ι処理３０５は、それぞれ、図１（ｃ）のラウンド処理Ｒ２０１におけるθ処理３０１、ρ処理３０２、ι処理３０５と、処理は同じである。  図１０は、ステップπ´の処理（π´処理１７０４）を説明する図である。図５はステップπの入力とステップπの出力を示した図であるが、この変換は図１０のように分解することができる。図１０（ａ）は、入力の状態を示した図である。図１０（ｄ）は、ステップπ処理実施後の結果である。図中の数字に小さい順にｌａｎｅ単位でデータが入力されると仮定する。このとき、ステップπは、入力されたｌａｎｅをｐｌａｎｅ内で並べ替えを行う処理と、該並べ替え済みのｐｌａｎｅを時計回りに９０度回転させる処理に分解できる。このうち入力されたｌａｎｅをｐｌａｎｅ内で並べ替えを実施した結果が図１０（ｂ）である。
【００４６】
また、同様にステップπは、入力されたｌａｎｅ単位のデータを、時計回りに９０度回転させる処理を実行し、図１０（ｃ）を得てから、該回転済みのｓｈｅｅｔ内部でｌａｎｅｎの入れ替えを行うことによっても達成できる。
【００４７】
このとき、データの入力順を考慮すると、９０度回転を実施するためには、最低でも２３ｌａｎｅ分のデータ蓄積が必要となる。一方で、図１０（ｂ）を得るだけであれば、ｐｌａｎｅ分のみのデータ蓄積でパイプライン処理が実施できる。本実施形態においては、この図１０（ａ）から図１０（ｂ）を得るための変換に、さらに左右反転処理を加えた図１０（ａ）から図１０（ｅ）に至る処理を特にステップπ’１７０４と定義する。なお、左右反転処理を加えた理由は、後述する偶数ラウンドにおけるステップπ  処理においても９０度回転処理を省略するための布石である。２度の９０度回転、すなわち１８０度回転処理は、左右反転処理と上下反転処理で代用可能である。ステップπ’  １７０４は、ｐｌａｎｅ内の各ｌａｎｅを入れ替える。そのため、前段（ステップρ）の計算結果が１個のｐｌａｎｅ、すなわち５個のｌａｎｅ分出力された時点で、ステップπ’  １７０４の処理を開始することができる。
【００４８】
図１１は、ステップχ’の処理（χ’処理１７０５）を説明するための図である。ステップχ´は、ｘ軸方向（”ｒｏｗ”とも呼ばれる）のビット列内での変換を行う処理であり、出力ｒｏｗ各ビットの値は、同一の入力ｒｏｗの３つのビットに基づき導出される。より具体的には、出力ｒｏｗの各ビットの値は、入力ｒｏｗの各ビットに対し、ｘ軸方向で＋１の場所にあるビットが０、かつ、ｘ軸方向で＋２の場所にあるビットが１の場合にビットの値が反転するように設定される。尚、ステップπ’１７０４は、ステップπが行っていた９０度回転を行っていないため、ステップχ’１７０５はデータ取り出し方向をステップχに対して９０度回転させることでステップχと同等の処理を行っている。図１１に示すとおり、ステップχ’  は、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｙ軸方向で＋１のｌａｎｅ及びｙ軸方向で＋２のｌａｎｅを使用する。そのため、２１個目のｌａｎｅのデータを受け取った時点で、ステップχ’  １７０５の処理を開始することできる。
【００４９】
奇数ラウンドＲ’ｏｄｄ１７０１におけるステップι（ι処理３０５）は、図１（ｃ）のラウンド処理Ｒ２０１におけるι処理３０５と、処理は同じである。ステップιはｘ＝０、ｙ＝０、ｚ＝０のｌａｎｅに所定の定数をＸＯＲする処理である。図１０で示した通り、ステップπ実施後（図１０の（ｄ））とステップπ’  実施後（図１０（ｅ））を比較すると当該ｌａｎｅの値は変化しないことがわかる。つまり、ステップιは、ｌａｎｅ単位で行う処理である。したがって、奇数ラウンドＲ’ｏｄｄ１７０１におけるステップιは、ラウンド処理Ｒ２０１におけるι処理３０５と同じ処理で行うことができる。
【００５０】
次に、偶数ラウンドの処理Ｒ’ｅｖｅｎ１７０２について説明する。偶数ラウンドＲ’ｅｖｅｎ１７０２は、入力データに対し、５つのステップの処理（θ´処理１７０６、ρ´処理１７０７、π´´処理１７０８、χ処理３０４、ι処理３０５）を適用して出力データを生成する。ここで、偶数ラウンドＲ’ｅｖｅｎ１７０２におけるχ処理３０４、ι処理３０５は、それぞれ、図１（ｃ）のラウンド処理Ｒ２０１におけるχ処理３０４、ι処理３０５と、処理は同じである。
【００５１】
奇数ラウンドＲ’ｏｄｄ１７０１において、本来のステップπはステップπ’１７０４に置き換えられている。そのため、本来のアルゴリズムと同等の処理結果を得るためには偶数ラウンドＲ’ｅｖｅｎ１７０２のステップθ及びステップρ及びステップπにも補正が必要となる。
【００５２】
図１２は、ステップθ’の処理（θ’処理１７０６）を説明するための図である。ステップθ´は、各ビットに対して近傍の２つのｒｏｗの和を加える処理である。尚、ｒｏｗは、ｘ軸方向に５ビット、ｙ軸方向に１ビット、ｚ軸方向に１ビットの構造として表される。ステップπ’  １７０４  はステップπにくらべて９０度回転を省略している。したがって、ステップθ’  がステップθと同等の処理結果を得るためには演算の方向を９０度逆回転させる必要がある。図３に示した通り、ステップθは近傍の２つのｃｏｌｕｍｎのＳＵＭ値をｂｉｔに足しこむ処理で合った。そこで、ステップθ’  １７０６は近傍の２つのｒｏｗの値をｂｉｔに足しこむ。具体的には、出力ｓｔａｔｅの各ビットは、入力ｓｔａｔｅのうち、次の３つ値の和として計算される。
・”同じ場所にあるビットの値”
・”ｙ軸方向で−１の場所にあるｒｏｗのビットの和”
・”ｙ軸方向で＋１かつｚ軸方向で−１の場所にあるｒｏｗのビットの和”ここで、和とは、ＧＦ（２）上での和のことであり、排他的論理和の演算と同一の結果になる。式で書くと、次のようになる。
【００５３】
【数２】
2015114429.tif 000004
【００５４】
ここで、ｘは０〜４、ｙは０〜４、ｚは０〜６３である。
【００５５】
ステップθ’  １７０６は、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｙ軸方向に関して−１のｐｌａｎｅと＋１のｐｌａｎｅのデータを使用する。そのため、最初の３つ分のｐｌａｎｅが完全に揃う時、つまり、２５個のｌａｎｅのうち１５個のｌａｎｅを前段の処理から受け取った時、ステップθ’  １７０６の処理を開始することができる。
【００５６】
図１３は、ステップρ’の処理（ρ’処理１７０７）を説明するための図である。
【００５７】
次に、ラウンド処理Ｒ’ｅｖｅｎ１７０２においてステップρに代わって用いられるステップρ’  １７０７  について説明する。ステップρは図４に示した通りｌａｎｅの各要素を所定のｂｉｔだけシフトさせる処理である。しかし、ステップπ’  １７０４では９０度回転の省略と左右反転処理を行っている。そこで、ステップρ’  １７０７  ではステップρと同等の処理結果となるよう、図１３（ｃ）に記載の数だけシフト処理を行う。ただし、図１３（ｃ）記載のシフト量は、図４（ｃ）に記載のシフト量を、９０度逆回転後に左右反転（図１０（ｄ）から図１０（ｅ）への変換に相当）して求めたものである。
【００５８】
ステップρ’  １７０７は、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップθ）から１個のｌａｎｅ分出力された時点で、ステップρ’  １７０７の処理を開始することができる。
【００５９】
図１４は、ステップπ’’の処理（π’’処理１７０８）を説明するための図である。次に、ラウンド処理Ｒ’ｅｖｅｎ１７０２においてステップπ  に代わって用いられるステップπ’’  １７０８  について説明する。ステップπ’’  １７０８は、本来のアルゴリズムで２回目のπを実行した直後と同等の結果となるよう補正する処理である。
【００６０】
ステップπ’’  １７０８の処理を具体的に説明する。図１４に本来のアルゴリズムにおいてステップπを２回実行した場合と、本実施形態のアルゴリズムにおいてステップπ’  １７０４  とステップπ’’  １７０８  を実行した場合の比較図を示す。本来のアルゴリズムでは、まず、元データ（図１４（ａ）  ）に対してステップπを実行した結果が、図１０で説明したように、図１４（ｄ）となる。さらにもう一度ステップπを実行した結果が、例えば、９０度回転とＳｈｅｅｔ内並び替え処理に相当する処理を行って、図１４（ｇ）となる。一方、本実施形態のアルゴリズムにおいては、元データ図１４（ａ）  に対してステップπ’  １７０４  を実行すると、図１０で説明したように、図１４（ｅ）となる。ステップπ’’  １７０８は、図１４（ｅ）  に対して  ｓｈｅｅｔ  内でのｌａｎｅの入れ替えを行い、図１４（ｇ）  に変換する処理である。なお、ステップπ’  １７０４  とステップπ’’  １７０８  の間には、ステップχ’  １７０５、ステップι３０５、ステップθ’  １７０６、ステップρ’  １７０７を行っている。しかし、ステップχ’  １７０５およびステップι３０５およびステップθ’  １７０６はｂｉｔの値を更新する処理、ステップρ’  １７０７はｌａｎｅ内でｂｉｔの入れ替えをする処理であるため、ステップπ’’  １７０８に影響は及ぼさない。
【００６１】
ステップπは、ｓｈｅｅｔ内の各ｌａｎｅを入れ替える。そのため、前段（ステップρ）の計算結果が２５個中２１個目のｌａｎｅ分出力された時点で、ステップπの処理を開始することができる。
【００６２】
ラウンドＲ’ｅｖｅｎ１７０２の残るステップχとステップιは、本来のアルゴリズムと同様のため説明を省略する。
【００６３】
＜装置構成および動作＞
図１５は、第１実施形態のハッシュ生成装置の回路構成である。図中の２７０１は１ｓｔａｔｅ分の入力データもしくはラウンド処理結果を保持する１ｓｔａｔｅレジスタＡである。  ２７０２は３ｐｌａｎｅ分のラウンド処理の中間値を保持する３ｐｌａｎｅレジスタＡである。  ２７０３は３ｐｌａｎｅ分のラウンド処理の中間値を保持する３ｐｌａｎｅレジスタＢである。  ２７０４は１ｓｔａｔｅ分のラウンド処理の中間値を保持する１ｓｔａｔｅレジスタＢである。
【００６４】
先に述べたとおり、各ステップを開始するための制約条件は、ステップπ’  １７０４の場合、５個のｌａｎｅのデータを前段の処理から受け取った時、ステップχ’  １７０５は２１個目のｌａｎｅのデータを前段の処理から受け取った時である。また、ステップθ’  １７０６は１５個のｌａｎｅを前段の処理から受け取った時、ステップρ’  １７０７は１個のｌａｎｅを前段の処理から受け取った時、ステップπ’’  １７０８は２１個のｌａｎｅのデータを前段の処理から受け取った時である。
【００６５】
次に従来のアルゴリズムと第１実施形態のスループットについて比較する。まずは従来のアルゴリズムについて述べる。
【００６６】
＜仕様通りのアルゴリズムでｌａｎｅ単位で処理を行った場合の例＞
図１６は、図１（ｃ）のラウンド処理Ｒ２０１を用いた場合の回路構成である。  図中の２５０１は１ｓｔａｔｅ分の入力データもしくはラウンド処理結果を保持する１ｓｔａｔｅレジスタＡである。  ２５０２は１ｓｔａｔｅ分のラウンド処理の中間値を保持する１ｓｔａｔｅレジスタＢである。
【００６７】
従来例でも述べた通り、各ステップを開始するための制約条件は、ステップθの場合２５個のｌａｎｅのうち２３個のｌａｎｅを前段の処理から受け取った時、ステップρは１個のｌａｎｅを前段の処理から受け取った時である。また、ステップπは１ｓｔａｔｅ全てを前段の処理から受け取った時、ステップχは３個目のｌａｎｅを前段の処理から受け取った時、ステップιは前段の処理から１個のｌａｎｅを受け取った時である。
【００６８】
これらの制約を踏まえ、ラウンド処理のタイミングチャートを作成すると図１７（ｂ）となる。すなわち、従来例では２Ｒｏｕｎｄ分の処理を実行するためには１００ｃｙｃｌｅの時間を要する。
【００６９】
これらの制約を踏まえ、ラウンド処理のタイミングチャートを作成すると図１７（ａ）となる。すなわち、第１実施形態では２Ｒｏｕｎｄ分の処理を実行するためには８０ｃｙｃｌｅの時間を要し、従来例に比べて２０ｃｙｃｌｅ短縮可能である。
以上が第１実施形態である。
【００７０】
本実施形態は、ｓｔａｔｅ全体に対する処理であるステップπがｐｌａｎｅ内でのｌａｎｅの置換処理とｓｈｅｅｔ内でのｌａｎｅの置換処理に分解できることに着目している。そして、奇数回目のラウンドではｐｌａｎｅ内でのｌａｎｅの置換処理、偶数回目のラウンドではｓｈｅｅｔ内でのｌａｎｅの置換処理を行うことで、データハザードを軽減することが可能となる。
【００７１】
（第２実施形態）
第２実施形態は、第１実施形態で処理性能の制約となっていたπ演算およびχ演算開始のタイミングを早めるため、θ演算に先んじてπ演算を実施することで、さらなる性能向上を実現する。  図１８（ａ）に、第２実施形態のアルゴリズムの概要図を示す。第２実施形態は第１実施形態と同様、奇数ラウンドＲ’ｏｄｄ  ２９０１  と偶数ラウンドＲ’ｅｖｅｎ２９０２  を交互に１２回実行する。
【００７２】
図１８（ｂ）に奇数回目のラウンドＲ’ｏｄｄ２９０１  と  偶数回目のラウンドＲ’ｅｖｅｎ２９０２の概要を示す。  図中の３００４はＲ’ｏｄｄにおいてステップθに代わって用いられるステップθ’  である。  ３００５はＲ’ｏｄｄにおいてステップρに代わって用いられるステップρ’  である。  ３００６はＲ’ｏｄｄにおいてステップθに代わって用いられるステップθ’’  である。３００７はＲ’ｏｄｄにおいてステップρに代わって用いられるステップρ’’  である。図１８（ｂ）に示すように、第２実施形態では、本来ラウンドの３番目に実行されるπ演算をラウンドの最初に実行するのが特徴である。
【００７３】
以下、第２実施形態の奇数ラウンドＲ’  ｏｄｄ  ２９０１、偶数ラウンドＲ’ｅｖｅｎ  ２９０２を構成する各演算について詳細に説明する。奇数ラウンドＲ’ｏｄｄ  ２９０１のステップπ’  １７０４は第１実施形態で述べた同名の演算と同一であるため、説明を省略する。
【００７４】
次にステップθ’  ３００４の処理について説明する。  先に図３で述べた通り、ステップθは隣接するｃｏｌｕｍｎの総和を各ｂｉｔに足しこむ演算である。しかし、第２実施形態では先にステップπ’  １７０４を行うため、ｐｌａｎｅ内でｌａｎｅが入れ替わってしまい、ｃｏｌｕｍｎの総和が本来の値と異なってしまう。そこで、ステップθ’    ３００４は、ステップπ’  １７０４実施前のデータからｃｏｌｕｍｎの総和を求める前半部（図１９（ａ））と、前半部の結果をステップπ’  １７０４実施後のｌａｎｅに対して加算する後半部（図１９（ｂ））の２工程で実施する。  本来のアルゴリズムのステップθでは、後半部の工程で加算される値は、同一ｃｏｌｕｍｎ内で一律である。しかし、ステップπ’  １７０４を先に実行すると図１０（ａ）から図１０（ｅ）に示すｐｌａｎｅ内のｌａｎｅ単位での置換が行われるため、ステップθ’  ３００４後半部ではこの置換を考慮して、本来のアルゴリズムと同等の結果となるよう加算を行う。
【００７５】
ステップθ’  ３００４の前半部は、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｘ軸方向に関して−１のｓｈｅｅｔと＋１のｓｈｅｅｔのデータを使用する。そのため、最初の３つ分のｓｈｅｅｔがラウンドＲ’ｏｄｄ  ２９０１の入力データとして揃った時、処理を開始することができる。つまり、ステップθ’  ３００４の前半部はラウンド処理内での開始制約は無い。
【００７６】
一方、ステップθ’  ３００４の後半部は、ｓｔａｔｅ内の各ｌａｎｅの計算において、ステップθ’  ３００４の前半部のデータを使用する。既に述べたとおり、ステップθ’  ３００４の前半部には開始制約は無いため、ステップθ’  ３００４の後半部は前段の処理ステップπ’  １７０４からｌａｎｅを受け取り次第処理を開始可能である。
【００７７】
図２０は、ステップρ’３００５の処理を説明する図である。第１実施形態で述べたとおり、ステップρはｌａｎｅ内でｂｉｔの値をｌａｎｅごとに所定の値（図４参照）だけシフトする処理である。しかし、第２の実施形態ではステップρ’  ３００５に先んじてステップπ’  １７０４を実施するため、本来のアルゴリズムと同等の結果を得るためにはｌａｎｅごとに定められたシフト量を補正する必要がある。そこで、ステップρ’  ３００５は、図４（ｃ）のシフト量にステップπ’  と同様の変換を施して求めた、図２０（ｃ）記載のシフト量で処理を行う。
【００７８】
ステップρ’    ３００５は、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップθ’  ３００４）から１個のｌａｎｅ分出力された時点で、ステップρ’  ３００４の処理を開始することができる。
【００７９】
ステップχ’  １７０５およびステップι３０５は第１の実施形態で述べた同名の演算と同一であるため、説明を省略する。奇数ラウンドＲ’ｏｄｄ  ２９０１の出力は、ステップθ’  ３００４およびステップρ’  ３００５での補正により、第１の実施形態の奇数ラウンドＲ’ｏｄｄ  １７０１と同一の結果となる。
【００８０】
続いて偶数ラウンドＲ’ｅｖｅｎ２９０２の処理について説明する。ステップπ’’  １７０８は第１の実施形態で述べた同名の演算と同一であるため、説明を省略する。
【００８１】
図２１は、ステップθ’’３００６の処理を説明する図である。図２１にステップθ’’  ３００６の処理内容を示す。ステップθ’’  ３００６は、第１実施形態におけるステップθ’  １７０６  と同じく、隣接するｒｏｗの総和を各ｂｉｔに足しこむ演算である。しかし、第２実施形態では先んじてステップπ’’  １７０８を行うため、ｒｏｗの総和が本来の値と異なってしまう。そこで、ステップθ’’  ３００６は、次の２工程で実施する。
・奇数ラウンドＲ’ｏｄｄ  ２９０１の出力データからｒｏｗの総和を求める前半部（図２１（ａ）、ｒｏｗ和算出処理）
・ステップθ’’  ３００６の前半部の結果をπ’’  演算１７０８実施後のｌａｎｅに対して加算する後半部（図２１（ｂ）、ｒｏｗ和加算処理）の
第１実施形態におけるステップθ’  １７０６では、後半部の工程で加算される値は、同一ｒｏｗ内で一律である。しかし、ステップπ’’  １７０８を先に実行すると図１３（ｃ  ）から図１３（ｇ）に示すｓｈｅｅｔ内のｌａｎｅ単位での置換が行われるため、ステップθ’’  ３００６後半部ではこの置換を考慮して、本来のアルゴリズムと同等の結果となるよう加算を行う。
【００８２】
ステップθ’’  ３００６の前半部は、ｓｔａｔｅ内の各ｌａｎｅの計算において、ｙ軸方向に関して−１のｐｌａｎｅと＋１のｐｌａｎｅのデータを使用する。そのため、最初の３つ分のｐｌａｎｅをＲ’ｏｄｄ  ２９０１から受け取った時、処理を開始することができる。つまり、ステップθ’’  ３００６の前半部はラウンド処理Ｒ’ｅｖｅｎ  ２９０２内での開始制約は無い。
【００８３】
図２２は、ステップρ’’３００７の処理を説明する図である。第１実施形態で述べたとおり、ステップρはｌａｎｅ内でｂｉｔの値をｌａｎｅごとに所定の値（図４参照）だけシフトする処理である。しかし、第２の実施形態ではステップρ’’  ３００７に先んじてステップπ’’  １７０８を実施するため、本来のアルゴリズムと同等の結果を得るためにはｌａｎｅごとに定められたシフト量を補正する必要がある。そこで、ステップρ’’  ３００７は、図１３（ｃ）のシフト量にステップπ’’  １７０８  と同様の変換を施して求めた、図２２（ｃ）記載のシフト量で処理を行う。つまり、π処理で入替処理されたｌａｎｅに対して処理を行う。ステップρ’’    ３００７は、ｌａｎｅ毎に独立した計算である。そのため、前段（ステップθ’’  ３００６）から１個のｌａｎｅ分出力された時点で、ステップρ’’  ３００７の処理を開始することができる。
【００８４】
χ  演算３０４およびι演算３０５は第１実施形態で述べた同名の演算と同一であるため、説明を省略する。以上が第２実施形態のアルゴリズムである。
【００８５】
＜装置構成および動作＞図２３は、第２実施形態のハッシュ生成装置の回路構成を示す。図中の３７０１は１ｓｔａｔｅ分の入力データおよびラウンド処理結果を保持する１ｓｔａｔｅレジスタＡである。  ３７０２は３ｐｌａｎｅ分のラウンド処理の中間値を保持する３ｐｌａｎｅレジスタＡである。  ３７０３は１ｓｔａｔｅ分のラウンド処理の中間値を保持する１ｓｔａｔｅレジスタＢである。  ３７０４は２ｐｌａｎｅ分のラウンド処理の中間値を保持する２ｐｌａｎｅレジスタＡである。
【００８６】
先に述べたとおり、各ステップを開始するための制約条件は、ステップπ’  １７０４は５個のｌａｎｅのデータを前段の処理から受け取った時、ステップθ’  ３００４は１個のｌａｎｅのデータを前段の処理から受け取った時である。また、ステップρ’  ３００５  は１個のｌａｎｅのデータを前段の処理から受け取った時、ステップχ’  １７０５は２１個目のｌａｎｅのデータを前段の処理から受け取った時である。また、ステップι３０５  は１個のｌａｎｅのデータを前段の処理から受け取った時、ステップπ’’  １７０８は２１個のｌａｎｅのデータを前段の処理から受け取った時である。また、ステップθ’’  ３００６は１個のｌａｎｅのデータを前段の処理から受け取った時、ステップρ’’  ３００７は１個のｌａｎｅのデータを前段の処理から受け取った時である。また、ステップχ３０４は３個目のｌａｎｅを前段の処理から受け取った時、ステップι３０５は１個目のｌａｎｅを前段の処理から受け取った時である。
【００８７】
これらの制約を踏まえ、ラウンド処理のタイミングチャートを作成すると図１７（ｃ）となる。すなわち、第２実施形態では２Ｒｏｕｎｄ分の処理を実行するためには６５ｃｙｃｌｅの時間を要し、従来例と比較して３５ｃｙｃｌｅの短縮が可能である。
【００８８】
以上の実施例はあくまで本発明の一例に過ぎず、本発明の効果は上記実施例に限ったことではない。
【００８９】
（その他の実施例）
また、本発明は、以下の処理を実行することによっても実現される。上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステム或いは装置のコンピュータ（またはＣＰＵやＭＰＵ等）がプログラムを読み出して実行、制御する処理である。
【図１】
2015114429.tif 000005
【図２】
2015114429.tif 000006
【図３】
2015114429.tif 000007
【図４】
2015114429.tif 000008
【図５】
2015114429.tif 000009
【図６】
2015114429.tif 000010
【図７】
2015114429.tif 000011
【図８】
2015114429.tif 000012
【図９】
2015114429.tif 000013
【図１０】
2015114429.tif 000014
【図１１】
2015114429.tif 000015
【図１２】
2015114429.tif 000016
【図１３】
2015114429.tif 000017
【図１４】
2015114429.tif 000018
【図１５】
2015114429.tif 000019
【図１６】
2015114429.tif 000020
【図１７】
2015114429.tif 000021
【図１８】
2015114429.tif 000022
【図１９】
2015114429.tif 000023
【図２０】
2015114429.tif 000024
【図２１】
2015114429.tif 000025
【図２２】
2015114429.tif 000026
【図２３】
2015114429.tif 000027