(57)【要約】【課題】消費電力を低減するＳＨＡ演算方法等を得る。【解決手段】Initializeプロセスにおいて、ａ＝Ｈ０（ｉ−１）、ｂ＝Ｈ１（ｉ−１）、ｃ＝ROTR３０（Ｈ２（ｉ−１））、ｄ＝ROTR３０（Ｈ３（ｉ−１））、ｅ＝ROTR３０（Ｈ４（ｉ−１））となる。次に、ｔ＝０〜７９の各プロセスにおいて、ａ〜ｅのうちのいずれか１つは、TEMPを保持し、残りの４つは、１つ前のプロセスでの値をそのまま保持する。そして、computeプロセスにおいて、Ｈ０（ｉ）＝Ｈ０（ｉ−１）＋ａ、Ｈ１（ｉ）＝Ｈ１（ｉ−１）＋ｂ、Ｈ２（ｉ）＝Ｈ２（ｉ−１）＋ROTL３０（ｃ）、Ｈ３（ｉ）＝Ｈ３（ｉ−１）＋ROTL３０（ｄ）、Ｈ４（ｉ）＝Ｈ４（ｉ−１）＋ROTL３０（ｅ）となる。【選択図】図６
2008116856.tif 000002
【特許請求の範囲】
【請求項１】
ＳＨＡ−１アルゴリズムに基づくハッシュ演算に用いられる第１ないし第５の変数をそれぞれ、第１ないし第５の記憶部に格納するステップと、
前記格納した第１ないし第５の変数をそれぞれ、第１ないし第５の中間値に読み替えるステップと、
前記読み替えた第１ないし第５の中間値を用いて、ＳＨＡ−１アルゴリズムに基づく一時変数を演算するステップと、
前記演算した一時変数を格納する記憶部を前記第１ないし第５の記憶部の中から選択するステップと、
クロックサイクルに基づくタイミングで順次、前記選択した記憶部の変数に前記演算した一時変数を保持するとともに、他の１つの記憶部の変数に保持されていた値をローテートして当該他の１つの記憶部の変数に保持し、かつ残りの記憶部の変数に保持されていた値をそれぞれ、そのまま当該残りの各記憶部の変数に保持するステップと、
前記保持した各記憶部の変数を用いてハッシュ値を演算するステップと、
を含むＳＨＡ演算方法。
【請求項２】
前記読み替えた第１ないし第５の中間値のうちの一部の中間値が、対応する変数をローテートして読み替えられた場合、
前記演算するステップでは、前記ローテートして読み替えた中間値を用いて前記一時変数を演算し、
前記保持するステップでは、クロックサイクルに基づくタイミングで順次、前記ローテートして読み替えた中間値を用いて演算した一時変数を前記選択した記憶部の変数に保持するとともに、前記他の１つの記憶部の変数に保持する値をローテートすることなく、残りのすべての記憶部の変数に保持されていた値をそれぞれ、そのまま当該残りの各記憶部の変数に保持する、
請求項１に記載のＳＨＡ演算方法。
【請求項３】
ＳＨＡ−２アルゴリズムに基づくハッシュ値の演算に用いられる、第１ないし第８の変数をそれぞれ、第１ないし第８の記憶部に格納するステップと、
前記格納した第１ないし第８の変数をそれぞれ、第１ないし第８の中間値に読み替えるステップと、
前記読み替えた第１ないし第８の中間値を用いて、ＳＨＡ−２アルゴリズムに基づく、第１および第２の一時変数を演算するステップと、
前記演算した第１および第２の一時変数を格納する記憶部をそれぞれ、前記第１ないし第８の記憶部の中から選択するステップと、
クロックサイクルに基づくタイミングで順次、前記選択した記憶部の変数にそれぞれ、第１および第２の一時変数を保持し、かつ残りの記憶部の変数に保持されていた値をそれぞれ、そのまま当該残りの各記憶部の変数に保持するステップと、
前記保持した各記憶部の変数を用いてハッシュ値を演算するステップと、
を含むＳＨＡ演算方法。
【請求項４】
前記ＳＨＡ−２アルゴリズムは、ＳＨＡ−２２４、ＳＨＡ−２５６、ＳＨＡ−３８４またはＳＨＡ−５１２のアルゴリズムである、
請求項３に記載のＳＨＡ演算方法。
【請求項５】
ＳＨＡ−１アルゴリズムに基づくハッシュ演算に用いられ、かつ第１ないし第５の記憶部に格納される第１ないし第５の変数をそれぞれ、第１ないし第５の中間値に読み替える読替部と、
前記読み替えられた第１ないし第５の中間値を用いて、ＳＨＡ−１アルゴリズムに基づく一時変数を演算する演算部と、
前記第１ないし第５の記憶部の中から、前記演算された一時変数を格納する記憶部を選択する選択部と、
クロックサイクルに基づくタイミングで順次、前記選択に従って前記演算された一時変数を１つの前記変数に保持するとともに、他の１つの変数に保持されていた値をローテートして当該他の１つの変数に保持し、かつ残りの変数に保持されていた値をそれぞれ、そのまま当該残りの各変数に保持する前記第１ないし第５の記憶部と、
前記保持された第１ないし第５の記憶部の変数を用いてハッシュ値を演算して保持するハッシュ保持部と、
を含むＳＨＡ演算回路。
【請求項６】
前記読替部が、前記第１ないし第５の変数のうちの一部の変数をローテートして前記中間値を読み替えた場合、
前記演算部は、前記ローテートして読み替えられた中間値を用いて前記一時変数を演算し、
前記第１ないし第５の記憶部のうちの前記選択された記憶部は、前記クロックサイクルに基づくタイミングで順次、前記ローテートして読み替えた中間値を用いて演算された一時変数を当該変数に保持し、残りの記憶部は、いずれもローテートすることなく、当該変数に保持されていた値をそれぞれ、そのまま各変数に保持する、
請求項５に記載のＳＨＡ演算回路。
【請求項７】
ＳＨＡ−２アルゴリズムに基づくハッシュ演算に用いられ、かつ第１ないし第８の記憶部に格納される第１ないし第８の変数をそれぞれ、第１ないし第８の中間値に読み替える読替部と、
前記読み替えられた第１ないし第８の中間値を用いて、ＳＨＡ−２アルゴリズムに基づく、第１および第２の一時変数を演算する演算部と、
前記第１ないし第８の記憶部の中から、前記演算された第１および第２の一時変数をそれぞれ格納する記憶部を選択する選択部と、
クロックサイクルに基づくタイミングで順次、前記選択に従って前記演算した第１および第２の一時変数をそれぞれ、対応する前記変数に保持し、かつ残りの記憶部の変数に保持されていた値をそれぞれ、そのまま当該残りの各変数に保持する前記第１ないし第８の記憶部と、
前記保持された第１ないし第８の記憶部の変数を用いてハッシュ値を演算して保持するハッシュ保持部と、
を含むＳＨＡ演算回路。
【請求項８】
前記ＳＨＡ−２アルゴリズムは、ＳＨＡ−２２４、ＳＨＡ−２５６、ＳＨＡ−３８４またはＳＨＡ−５１２のアルゴリズムである、
請求項７に記載のＳＨＡ演算回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データからハッシュ値を演算するＳＨＡ(Secure Hash Algorithm）演算方法およびＳＨＡ演算装置に関するものである。
【背景技術】
【０００２】
近年、セキュリティアルゴリズムをハードウェア化し、セキュリティ処理を高速化する傾向にある。このため、ハッシュ（SHA: Secure Hash Algorithm）においても、ハッシュアルゴリズムがデジタル演算回路で構成されることが多い。ＳＨＡは、認証やデジタル署名、データの改ざん検出などに用いられ、ＳＨＡ−１、ＳＨＡ−２２４、ＳＨＡ−２５６、ＳＨＡ−３８４およびＳＨＡ−５１２が規定されている。
このような状況下において、従来のＳＨＡ演算の高速演算回路においては、パイプライン化によりハッシュ演算を高速に行う（例えば、特許文献１参照）。
【０００３】
【特許文献１】特開２００２−２８７６３５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、上述の従来例では、ハッシュ演算を高速化することができるものの、ハッシュ演算に用いるハードウェア回路そのものの消費電力を低減させることができなかった。このため、ＳＨＡ演算に用いるハードウェア回路の消費電力を低減させることが望まれている。
【課題を解決するための手段】
【０００５】
この発明のハッシュ演算方法は、前述の課題を解決するために、ＳＨＡ−１アルゴリズムに基づくハッシュ演算に用いられる第１ないし第５の変数をそれぞれ第１ないし第５の記憶部に格納するステップと、格納した第１ないし第５の変数をそれぞれ、第１ないし第５の中間値に読み替えるステップとを含む。さらに、読み替えた第１ないし第５の中間値を用いて、ＳＨＡ−１アルゴリズムに基づく一時変数を演算するステップと、演算した一時変数を格納する記憶部を第１ないし第５の記憶部の中から選択するステップとを含む。そして、クロックサイクルに基づくタイミングで順次、選択した記憶部の変数に演算した一時変数を保持するとともに、他の１つの記憶部の変数に保持されていた値をローテートして当該他の１つの記憶部の変数に保持し、かつ残りの記憶部の変数に保持されていた値をそれぞれ、そのまま当該残りの各記憶部の変数に保持するステップと、保持した各記憶部の変数を用いてハッシュ値を演算するステップとを含む。
この発明のハッシュ演算方法は、複数の記憶部間の値が移動することなく、ハッシュ値を演算する。
【０００６】
また、この発明のハッシュ演算回路は、ＳＨＡ−１アルゴリズムに基づくハッシュ演算に用いられ、かつ第１ないし第５の記憶部に格納される第１ないし第５の変数をそれぞれ、第１ないし第５の中間値に読み替える読替部と、読み替えられた第１ないし第５の中間値を用いて、ＳＨＡ−１アルゴリズムに基づく一時変数を演算する演算部と、第１ないし第５の記憶部の中から、演算された一時変数を格納する記憶部を選択する選択部とを含む。さらに、このハッシュ回路は、クロックサイクルに基づくタイミングで順次、選択に従って前記演算された一時変数を１つの前記変数に保持するとともに、他の１つの変数に保持されていた値をローテートして当該他の１つの変数に保持し、かつ残りの変数に保持されていた値をそれぞれ、そのまま当該残りの各変数に保持する第１ないし第５の記憶部を含む。そして、このハッシュ演算回路は、保持された第１ないし第５の記憶部の変数を用いてハッシュ値を演算して保持するハッシュ保持部を含む。
【発明の効果】
【０００７】
この発明によれば、ＳＨＡ演算に用いる記憶部を含むハードウェア回路の消費電力を低減させることができる。
【発明を実施するための最良の形態】
【０００８】
（実施の形態１）
実施の形態１においては、ＳＨＡ−１のハッシュ演算処理について説明する。なお、以下において、同一の部分は、同一の符号（用語を含む）を付して、適宜、重複説明を省略する。
まず、一般的なＳＨＡ−１のハッシュ演算処理について説明する。
最初に、ビット長が２６４bit未満のメッセージ（ハッシュ演算の対象データ）を５１２ｂｉｔずつ分割する。そして、分割したメッセージを、それぞれ、ブロックＭ（１）、Ｍ（２）、・・・、Ｍ（Ｎ）（Ｎは正数）とする。
【０００９】
次に、ブロックＭ（１）、Ｍ（２）、・・・、Ｍ（Ｎ）の順に、次のステップ１および２の処理を繰り返す。
ステップ１においては、ブロックＭ（ｉ）（ｉ＝１〜Ｎ）を３２ｂｉｔずつ分割し、１６個のワードＷ０、Ｗ１、・・・、Ｗ１５（Ｗｔ：ｔ＝０〜１５）とする。次に、ステップ２においては、３２ｂｉｔ長の変数ａ、ｂ、ｃ、ｄ、ｅを用いて、ブロックＭ（ｉ）（ｉ＝１〜Ｎ）の中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）（ｉ＝１〜Ｎ）を求める。
【００１０】
ここで、ステップ２の処理を図１を参照して説明する。
図１は一般的なＳＨＡ−１のプロセス処理を示す説明図である。
図１（ａ）によると、まず、Initialize（初期化）プロセスにおいて、ａ〜ｅは、あらかじめ規定されているハッシュ初期値Ｈ０（０）〜Ｈ４（０）が与えられる（ｉ＝１）。
次に、ｔ＝０〜７９の各プロセス（クロックサイクルに基づくタイミングで処理）において、ａ〜ｅは、数１で与えられる。
【００１１】
【数１】
2008116856.tif 000003
【００１２】
なお、数１のROTL３０（ｂ）は、ｂを３０ビット左にローテートすることを表す。また、TEMPは、数２で与えられる一時変数を表す。
【００１３】
【数２】
2008116856.tif 000004
【００１４】
なお、数２のROTL５（ａ）は、ａを５ビット左にローテートすることを表し、ｆｔ(b，c，d)は、３２bit長の３つの引数をもつ数式を表す。Ｋｔは固有値を表す。Ｗｔ（ｔ＝１６〜７９）は、Ｗｔ（ｔ＝０〜１５）に基づいて順次算出される。
【００１５】
そして、中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）は、図１（ｂ）のcomputeプロセスに示すように、数３で与えられる（ただし、ｉ＝１〜Ｎ）。
【００１６】
【数３】
2008116856.tif 000005
【００１７】
このようにして、最終的には数４のメッセージダイジェストを得る。なお、｜｜は、ビット連結を表す。
【００１８】
【数４】
2008116856.tif 000006
【００１９】
その他、公知のＳＨＡ−１のハッシュ演算方法については、米国国立標準技術研究所(National Institute of Standards and Technology)が発行するFIPS PUB(Federal Information Processing Standards Publication) 180-2の「SECURE HASH STANDARD」に規定されている。
【００２０】
次に、上記一般的なＳＨＡ−１のハッシュ演算処理を行うＳＨＡ演算回路の構成について図２を参照して説明する。
図２は一般的なＳＨＡ−１のＳＨＡ演算回路の構成例を示す図である。
図２において、ＳＨＡ演算回路１００は、ハッシュ保持部１１および５つ（第１ないし第５）の記憶部１２Ａ、１２Ｂ、１２Ｃ、１２Ｄ、１２Ｅを含んでいる。さらに、ＳＨＡ演算回路１００は、演算部１３、第１の定数設定部（Ｗｔ設定部）１４および第２の定数設定部（Ｋｔ設定部）１５を含んでいる。
【００２１】
ハッシュ保持部１１は、５つの記憶部１２Ａ〜１２Ｅのそれぞれに対応するハッシュ値Ｈ０、Ｈ１、Ｈ２、Ｈ３、Ｈ４を保持する。具体的には、ハッシュ保持部１１は、ハッシュ初期値Ｈ０（０）〜Ｈ４（０）をあらかじめ保持する。さらに、ハッシュ保持部１１は、ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）を保持する。
【００２２】
各記憶部１２Ａ〜１２Ｅは、例えばフリップフロップで構成され、図１（ａ）のａ〜ｅ（数１参照）を格納する。
演算部１３は、各記憶部１２Ａ〜１２Ｅに格納されたａ〜ｅを取り出し、それらの値に基づいて、数２のTEMPを演算する。
第１の定数設定部１４は、Ｗｔを設定し、第２の定数設定部１５は、Ｋｔを設定する。
【００２３】
以上は、ＳＨＡ−１の一般的なプロセス処理およびＳＨＡ演算回路の説明であるが、以下、本発明の実施の形態１のＳＨＡ−１のプロセス処理およびＳＨＡ演算回路について説明する。
【００２４】
図３は本発明の実施の形態１に係るＳＨＡ−１のプロセス処理を示す説明図である。
図３の実施の形態１のプロセス処理は、後述する３２ビットの中間値（１次中間値）ｖ〜ｚを用いてTEMPを求める点に特徴がある。これにより、図１のプロセス処理の場合に比べて、ａ〜ｅの値の変化回数を減少させることが可能となる。そこで、以下では、図１のプロセス処理と異なる点を中心に説明する。
図３（ａ）によると、Initializeプロセスにおいて、ａ〜ｅは、あらかじめ規定されているハッシュ初期値Ｈ０（０）〜Ｈ４（０）が与えられる（ｉ＝１）。
【００２５】
次に、ｔ＝０〜７９の各プロセスにおいて、ａ〜ｅのうちのいずれか１つは、TEMPを保持し、他の１つは、ROTL３０の演算値を保持する。そして、残りの３つは、１つ前のプロセスの値をそのまま保持する。
【００２６】
例えば、ｔ＝１の場合、ｄがTEMPを保持し、ａがROTL３０（ａ）の演算値を保持する。そして、各ｂ、ｃ、ｅは、１つ前のプロセスｔ＝０の値（ｂ、ｃ、ｅ）をそのまま保持する。このようにすることによって、図３（ａ）のａ〜ｅは、図１（ａ）のプロセス処理の場合に比べて、値の変化回数が減少することがわかる。
【００２７】
図３（ａ）のTEMPは、第１ないし第５の中間値ｖ〜ｚを用いて、数５で与えられる。
【００２８】
【数５】
2008116856.tif 000007
【００２９】
数５のROTL５（ｖ）は、ｖを５ビット左にローテートすることを表す。ここで、中間値ｖ〜ｚは、ａ〜ｅのいずれかの値を読み替えた値である。
【００３０】
例えば、ｔ＝０の場合、数５のｖ〜ｚには、Initializeプロセスのａ〜ｅが読み替えられて、ｖ＝ａ、ｗ＝ｂ、ｘ＝ｃ、ｙ＝ｄ、ｚ＝ｅとなる。また、例えば、ｔ＝１の場合、数５のｖ〜ｚには、ｔ＝０のプロセスのａ〜ｅが読み替えられて、ｖ＝ｅ、ｗ＝ａ、ｘ＝ｂ、ｙ＝ｃ、ｚ＝ｄとなる（図３（ａ）参照）。
【００３１】
そして、ｔ＝０〜７９のプロセス後、図３（ｂ）のcomputeプロセスにおいて、図１（ｂ）と等価な中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）を得る。図３（ｂ）は、図１（ｂ）に示した数３と同様の演算式で表される。
これは、例えばｔ＝０、５、・・・、７０、７５のとき、ｖ＝ａ、ｗ＝ｂ、ｘ＝ｃ、ｙ＝ｄ、ｚ＝ｅ（図３（ａ）参照）であり、中間値ｖ〜ｚへの読み替えが同じになる。すなわち、ｖ〜ｚへの読み替えは５プロセスごとに循環しており、８０プロセス（ｔ＝０〜７９）は５の倍数であるため、computeプロセスでの読み替えが必要ないからである。
【００３２】
以上のように、図３（ａ）のプロセス処理によると、ａ〜ｅのうちのいずれか１つはTEMPを保持し、他の１つはROTL３０の演算値を保持することになるものの、そのうちの３つは、１つ前のプロセスでの値をそのまま保持する。このため、図１（ａ）の場合に比べて、全プロセスにおけるａ〜ｅの値の変化回数が減少する。
【００３３】
次に、上記図３のＳＨＡ−１のハッシュ演算処理を行うＳＨＡ演算回路（ＳＨＡ演算装置）の構成について図４を参照して説明する。
図４は本発明の実施の形態１に係るＳＨＡ演算回路１０の構成例を示すブロック図である。
図４において、ＳＨＡ演算回路１０は、ハッシュ保持部１１、第１ないし第５の記憶部１２１Ａ〜１２１Ｅ、演算部１３１、第１の定数設定部１４および第２の定数設定部１５を含んでいる。さらに、ハッシュ演算回路１０は、選択部１６および読替部１７をさらに含んでいる。なお、ハッシュ保持部１１、第１の定数設定部１４および第２の定数設定部１５の構成は、図２の場合と同様である。
【００３４】
選択部１６は、図３（ａ）のプロセスに従って、TEMPを格納する記憶部を１つ選択する。同時に、選択部１６は、ROTL３０の演算値を格納する記憶部を１つ選択する。この選択に際して、選択部１６は、所定の選択信号ＥＮａ〜ＥＮｅを生成し、その選択信号を、選択する記憶部へ出力する。例えば、図３（ａ）のｔ＝０の場合、選択部１６は、記憶部１２１Ｅへ選択信号ＥＮｅを出力し、記憶部１２１ＥはTEMPを格納する。他方、選択部１６は、記憶部１２１Ｂに選択信号ＥＮｂを出力し、記憶部１２１ＢはROTL３０演算結果、すなわちROTL３０（ｂ）を格納する。
【００３５】
読替部１７は、例えば、複数個の５to１セレクタで構成され、図３（ａ）のプロセスに従って、各記憶部１２１Ａ〜１２１Ｅから取得したａ〜ｅを中間値ｖ〜ｚに読み替える。例えば、図３（ａ）のｔ＝０の場合、読替部１７は、各記憶部１２１Ａ〜１２１Ｅから取得したａ〜ｅをそのまま、ｖ〜ｚに読み替える。
【００３６】
演算部１３１は、図３（ａ）のプロセスに従って、読替部１７から取得した中間値ｖ〜ｚ、第１の定数設定部１４に設定されたＷｔ、および第２の定数設定部１５に設定されたＫｔに基づいて、TEMPを演算する。このときの演算式は、数５のとおりである。
【００３７】
各記憶部１２１Ａ〜１２１Ｅは、例えばフリップフロップで構成され、選択部１６からの選択信号に基づいて、所定の値（ａ〜ｅ、TEMP、ROTL３０）を格納する。そして、各記憶部１２１Ａ〜１２１Ｅは、ｔ＝７９のプロセス後、ａ〜ｅをハッシュ保持部１１へ出力する。この出力を受けて、ハッシュ保持部１１は、図３（ｂ）のcomputeプロセスを実行し、出力されたａ〜ｅおよび前回のハッシュ値Ｈ０（ｉ−１）〜Ｈ４（ｉ−１）に基づいて中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）を得る。
【００３８】
例えば、ｔ＝１の場合、記憶部１２１Ｄがｄ＝TEMPを保持し、記憶部１２１Ａがａ＝ROTL３０（ａ）の演算値を保持する。そして、３つの記憶部１２１Ｂ、１２１Ｃ、１２１Ｅが、１つ前のプロセスでの値（ｂ、ｃ、ｅ）をそのまま保持する。これにより、図４の各記憶部１２１Ａ〜１２１Ｅは、各記憶部間で値を移動（シフト動作）する図２の各記憶部１２Ａ〜１２Ｅの場合と異なり、各記憶部１２１Ａ〜１２１Ｅ間の値の移動がなくなる。よって、各記憶部１２１Ａ〜１２１Ｅのハードウェアの駆動率が減少し、ＳＨＡ演算回路１０の消費電力が低減する。
【００３９】
ここで、第１の記憶部１２１Ａの構成例について図５を参照して説明する。なお、他の各記憶部１２１Ｂ〜１２１Ｅの構成は、記憶部１２１Ａと同様である。
図５において、第１の記憶部１２１Ａは、セレクタ１２１と、フリップフロップ１２２（３２ビットのフリップフロップ）と、ROTL演算部１２３とを含んで構成されている。
セレクタ１２１は、選択信号ＥＮａがTEMP保持を指示している場合（例えば、図３（ａ）のｔ＝４、９、・・・、７９の場合）、演算部１３１からのTEMPを、フリップフロップ１２２へ出力させる。選択信号ＥＮａがROTL演算を指示している場合（例えば、図３（ａ）のｔ＝１、６、・・・、７１、７６の場合）、ROTL演算部１２３において演算されたROTL３０（ａ）をフリップフロップ１２２へ出力させる。他方、選択信号ＥＮａが前値保持を指示している場合（例えば、図３（ａ）のｔ＝０、２、３、・・・、７５、７７、７８の場合）は、セレクタ１２１は、フリップフロップ１２２の出力をそのまま保持させる。
【００４０】
以上のように、図４のＳＨＡ演算回路１０は、所定のａ〜ｅを中間値ｖ〜ｚに読み替える読替部１７と、ｖ〜ｚを用いてTEMPを演算する演算部１３１と、TEMPを保持する記憶部およびROTL演算値を保持する記憶部を選択する選択部１６とを含む。このため、第１ないし第５の記憶部１２１Ａ〜１２１Ｅのうちのいずれか１つは、TEMPを保持し、他の１つは、ROTL３０の演算値を保持することになるものの、そのうちの３つは、１つ前のプロセスでの値をそのまま保持する。このため、図２の場合と異なり、各記憶部間の値の移動（シフト動作）が不要となる。よって、各記憶部１２１Ａ〜１２１Ｅのハードウェアの駆動率が減少し、ＳＨＡ演算回路１０の消費電力が低減する。
【００４１】
特に、携帯電話や携帯機器、高度道路交通システム（Intelligent Transport Systems）などにおいては、バッテリー駆動の回路を多く含むため、これらに、ＳＨＡ演算回路１０（図３のＳＨＡ演算方法）を適用することは有益である。
【００４２】
さらに、各記憶部１２１Ａ〜１２１Ｅにおいて、例えば、ゲーテッド・クロックを適用し、前プロセスの値をそのまま保持し続ける記憶部へのクロック供給を停止するようにしてもよい。この場合、消費電力がさらに低減する。
【００４３】
［ＳＨＡ−１のプロセス処理の変形］
次に、ＳＨＡ−１のプロセス処理の変形について説明する。
図６は実施の形態１のＳＨＡ−１のプロセス処理の変形を示す説明図である。
図６では、図３のプロセス処理の場合と異なり、さらに、３２ビットの中間値（２次中間値）ｘtemp、ｙtemp、ｚtempを導入して、TEMPを求める点に特徴がある。これにより、全プロセスにおいて、すべてのａ〜ｅが、ROTL３０の演算値を保持しなくなり、ａ〜ｅの値の変化回数をさらに減少させることが可能となる。そこで、以下では、図３のプロセス処理と異なる点を中心に説明する。
【００４４】
図６（ａ）によると、Initializeプロセスにおいて、２つのａ、ｂは、図３（ａ）の場合と同様、それぞれ、あらかじめ規定されているハッシュ初期値Ｈ０（０）、Ｈ１（０）が与えられる（ｉ＝１）。これに対して、残りの３つのｃ〜ｅは、図３（ａ）の場合と異なり、ROTR３０（Ｈ２（０））〜ROTR３０（Ｈ４（０））が与えられる（ｉ＝１）。ここで、ROTR３０は３０ビット右にローテートすることを表す。
【００４５】
次に、ｔ＝０〜７９の各プロセスにおいて、ａ〜ｅのうちのいずれか１つは、TEMPを保持し、残りの４つは、１つ前のプロセスでの値をそのまま保持する。
【００４６】
例えば、ｔ＝１の場合、ｄがTEMPを保持し、残りのａ〜ｃ、ｅは、ｔ＝０の値（ａ〜ｃ、ｅ）をそのまま保持する。このようにすることによって、図６（ａ）のａ〜ｅは、図３のプロセス処理の場合に比べて、値の変化回数がさらに減少することがわかる。
【００４７】
この場合、図６（ａ）のTEMPは、中間値ｖ、ｗおよびｘtemp〜ｚtempを用いて、数６で与えられる。ここで、中間値ｖ、ｗ、ｘtemp、ｙtemp、ｚtempは、ａ〜ｅのいずれかの値を読み替えた値である。
【００４８】
【数６】
2008116856.tif 000008
【００４９】
例えば、ｔ＝０の場合、数６のｖ、ｗ、ｘtemp、ｙtemp、ｚtempには、Initializeプロセスのａ〜ｅが読み替えられて、ｖ＝ａ、ｗ＝ｂ、ｘtemp＝ｃ、ｙtemp＝ｄ、ｚtemp＝ｅとなる。また、例えば、ｔ＝１の場合には、ｔ＝０のプロセスのａ〜ｅが読み替えられて、ｖ＝ｅ、ｗ＝ａ、ｘtemp＝ｂ、ｙtemp＝ｃ、ｚtemp＝ｄとなる（図６（ａ）参照）。
【００５０】
そして、図６（ｂ）のcomputeプロセスにおいて、２つの中間ハッシュ値Ｈ０（ｉ）、Ｈ１（ｉ）は、図３（ｂ）の場合と同様の演算式で与えられる。これに対して、残りの３つの中間ハッシュ値Ｈ２（ｉ）〜Ｈ４（ｉ）は、図３（ｂ）の場合と異なり、ROTL３０（ｃ）〜ROTL３０（ｅ）が加算される。これにより、図６（ｂ）の中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）が、図３（ｂ）の中間ハッシュ値Ｈ０（ｉ）〜Ｈ４（ｉ）と等価の値をもつことになる。
【００５１】
なお、残りの３つの中間ハッシュ値Ｈ２（ｉ）〜Ｈ４（ｉ）にROTL３０の演算値が加算されるのは、次のような理由に基づく。すなわち、図６（ａ）のｔ＝７７〜７９において（太枠部分）、本来、ROTL３０演算が必要であるにもかかわらず、ROTL３０演算がされないため、computeプロセスでROTL３０演算を一括して行うためである。
また、Initializeプロセスにおいて、３つのｃ〜ｅには、図３（ａ）の場合と異なり、ROTR３０（Ｈ２（ｉ−１））〜ROTR３０（Ｈ４（ｉ−１））が与えられるのは、次のような理由に基づく。すなわち、図６（ａ）のｔ＝０〜２において（太枠部分）、本来、ROTR３０演算が不要であるにもかかわらず、ROTL３０演算がされているためである。これは、３０ビット右ローテートした値を３０ビット左ローテートすると、元の値に戻ることに基づく。
【００５２】
以上のように、図６（ａ）のプロセス処理によると、新たに３つの中間値ｘtemp〜ｚtempを導入してTEMPを求めることにより、ａ〜ｅのうちの４つが、１つ前のプロセスの値をそのまま保持する。このため、ａ〜ｅのうちの１つが、ROTL３０の演算値を保持する図３（ａ）の場合に比べて、全プロセスにおけるａ〜ｅの値の変化回数をさらに減少させることができる。
【００５３】
次に、上記図６のＳＨＡ−１のハッシュ演算処理を行うＳＨＡ演算回路の構成について図４を参照して説明する。
この場合、読替部１７は、図６（ａ）のプロセスに従って、各記憶部１２１Ａ〜１２１Ｅから、ａ〜ｅのいずれかを取得して、xtemp、ytemp、ztempに読み替える。さらに、読替部１７は、図６（ａ）のプロセス処理に従って、各記憶部１２１Ａ〜１２１Ｅから、ａ〜ｅのいずれかを取得して、各中間値ｖ、ｗに読み替える。
例えば、ｔ＝０の場合、読替部１７は、各記憶部１２１Ｃ〜１２１Ｅから、Initializeプロセスのｃ〜ｅを取得して、それぞれをｘtemp〜ｚtempに読み替える。これにより、ｘtemp＝ｃ、ｙtemp＝ｄ、ｚtemp＝ｅとなる。さらに、読替部１７は、各記憶部１２１Ａ、１２１Ｂから、Initializeプロセスのａ、ｂを取得して、それぞれ各中間値ｖ、ｗに読み替える。
【００５４】
また、読替部１７は、図６（ａ）のプロセスに従って、ｘtemp〜ｚtempを用いて、ROTL３０演算を行う。この演算式は、数６のとおりである。
【００５５】
演算部１３１は、図６（ａ）のプロセスに従って、読替部１７から取得した中間値ｖ〜ｚ、第１の定数設定部１４に設定されたＷｔ、および第２の定数設定部１５に設定されたＫｔに基づいて、TEMPを演算する。このときの演算式は、数６のとおりである。
【００５６】
各記憶部１２１Ａ〜１２１Ｅは、選択部１６からの選択信号に基づいて、所定の値（ａ〜ｅ、TEMP）を格納する。
例えば、図６（ａ）のｔ＝１の場合、記憶部１２１Ｄがｄ＝TEMPを保持し、残りの４つの記憶部１２１Ａ〜１２１Ｃ、１２１Ｅが、１つ前のプロセスの値（ａ〜ｃ、ｅ）をそのまま保持する。これにより、各記憶部１２１Ａ〜１２１Ｅは、図３（ａ）の場合と異なり、ROTL３０の演算値を保持しないこととなる（図５のROTL演算部１２３は不要）。よって、各記憶部１２１Ａ〜１２１Ｅのハードウェアの駆動率がさらに減少し、ＳＨＡ演算回路１０の消費電力がより一層低減する。
しかもこの場合、ＳＨＡ演算回路１０の規模を拡大することなく、より一層の消費電力の低減を期待できるので、有用である。
【００５７】
ここで、0.15μmの半導体プロセスにおいて、図６の場合の電力検証シミュレーションを行ったので、以下、説明する。なお、このシミュレーションでは、上記ゲーテッド・クロックを適用した。
例えば、第１の条件下（電源電圧1.65ｖ、周囲温度−４０℃）では、ＳＨＡ演算回路１００（図１、２参照）においては、消費電力が7.1ｍＷとなったのに対し、ハッシュ演算回路１０（図４、６参照）においては、5.5ｍＷとなった。これから、約２３％の削減効果を得ることがわかった。
さらに、第２の条件下（電源電圧1.35ｖ、周囲温度１２５℃）では、ハッシュ演算回路１００（図１、２参照）においては、消費電力が5.3ｍＷとなったのに対し、ハッシュ演算回路１０（図４、６参照）においては、3.6ｍＷとなった。これから、約３２％の削減効果を得ることがわかった。
【００５８】
（実施の形態２）
実施の形態２においては、ＳＨＡ−２（ＳＨＡ−２２４、２５６、３８４、５１２）のハッシュ演算処理について、便宜上簡略して説明する。
まず、一般的なＳＨＡ−２のハッシュ演算処理について説明する。
最初に、メッセージ（ハッシュ演算の対象データ）を分割する。例えば、ＳＨＡ−２２４、２５６の場合、５１２ビットずつ分割し、ＳＨＡ−３８４、５１２の場合、１０２４ビットずつ分割する。
そして、分割したメッセージを、それぞれ、ブロックＭ（１）、Ｍ（２）、・・・、Ｍ（Ｎ）（Ｎは正数）とする。
【００５９】
次に、ブロックＭ（１）、Ｍ（２）、・・・、Ｍ（Ｎ）の順に、次のステップ１および２の処理を繰り返す。
ステップ１においては、ブロックＭ（ｉ）（ｉ＝１〜Ｎ）を所定のビット長ずつ分割し、１６個のワードＷ０、Ｗ１、・・・、Ｗ１５（Ｗｔ：ｔ＝０〜１５）とする。例えば、ＳＨＡ−２２４、２５６の場合、３２ビットずつ分割され、ＳＨＡ−３８４、５１２の場合、６４ビットずつ分割される。
次に、ステップ２においては、所定のビット長の変数ａ、ｂ、ｃ、ｄ、ｅ、ｆ、ｇ、ｈを用いて、ブロックＭ（ｉ）（ｉ＝１〜Ｎ）の中間ハッシュ値Ｈ０（ｉ）〜Ｈ７（ｉ）（ｉ＝１〜Ｎ）を求める。ａ〜ｈのビット長は、ＳＨＡ−２２４、２５６の場合、３２ビット長であり、ＳＨＡ−３８４、５１２の場合、６４ビット長である。
【００６０】
ここで、ステップ２の処理を図７を参照して説明する。
図７は一般的なＳＨＡ−２のプロセス処理を示す説明図である。
図７（ａ）によると、まず、Initializeプロセスにおいて、ａ〜ｈは、あらかじめ規定されているハッシュ初期値Ｈ０（０）〜Ｈ７（０）が与えられる（ｉ＝１）。
次に、ｔ＝０〜７９の各プロセスにおいて、ａ〜ｈは、数７で与えられる。なお、図７（ａ）のプロセスは、ｔ＝０〜７９の８０プロセスの場合について記載されているが、例えば、ＳＨＡ−２２４、２５６の場合、ｔ＝０〜６３の６４プロセスとなる。
【００６１】
【数７】
2008116856.tif 000009
【００６２】
なお、数７のＴ１、Ｔ２は、数８で与えられる。Ｔ３は、便宜上Ｔ３＝Ｔ１＋ｄとする。
【００６３】
【数８】
2008116856.tif 000010
【００６４】
なお、数８のΣ０、Σ１、Ｃｈ、Ｍａｊ、Ｋｔ、Ｗｔは、上記「SECURE HASH STANDARD」の規定に基づくものである。
【００６５】
そして、中間ハッシュ値Ｈ０（ｉ）〜Ｈ７（ｉ）は、図７（ｂ）のcomputeプロセスに示すように、数９で与えられる（ただし、ｉ＝１〜Ｎ）。
【００６６】
【数９】
2008116856.tif 000011
【００６７】
このようにして、最終的には数１０のメッセージダイジェストを得る。なお、｜｜は、ビット連結を表す。
【００６８】
【数１０】
2008116856.tif 000012
【００６９】
その他、公知のＳＨＡ−２のハッシュ演算方法については、上記FIPS PUB(Federal Information Processing Standards Publication) 180-2(＋Change Notice to include SHA-224)の「SECURE HASH STANDARD」に規定されている。
【００７０】
以上は、ＳＨＡ−２の一般的なプロセス処理の説明であるが、以下、本発明の実施の形態２のＳＨＡ−２のプロセス処理およびＳＨＡ演算回路について説明する。
【００７１】
図８は本発明の実施の形態２に係るＳＨＡ−２のプロセス処理を示す説明図である。ここでは、ＳＨＡ−３８４、５１２の場合を想定しているので、ｔ＝０〜７９の８０プロセスとして説明するが、例えば、ＳＨＡ−２２４、２５６の場合、ｔ＝０〜６３の６４プロセスとなる。
【００７２】
図８の実施の形態２のプロセス処理は、後述する中間値（３次中間値）ｗ０〜ｚ０、ｗ１〜ｚ１を用いて、Ｔ１、Ｔ２、Ｔ３を求める点に特徴がある。これにより、図７のプロセス処理の場合に比べて、ａ〜ｈの値の変化回数を減少させることが可能となる。そこで、以下では、図７のプロセス処理と異なる点を中心に説明する。
図８（ａ）によると、Initializeプロセスにおいて、ａ〜ｈは、あらかじめ規定されているハッシュ初期値Ｈ０（０）〜Ｈ７（０）が与えられる（ｉ＝１）。
【００７３】
次に、ｔ＝０〜７９の各プロセスにおいて、ａ〜ｈのうちのいずれか１つは、Ｔ１＋Ｔ２を保持し、他の１つはＴ３を保持する。そして、残りの６つは、１つ前のプロセスでの値をそのまま保持する。
【００７４】
例えば、ｔ＝１の場合、ｃがＴ１＋Ｔ２を保持し、ｇがＴ３を保持する。そして、６つの各ａ、ｂ、ｄ、ｅ、ｆ、ｈは、１つ前のプロセスｔ＝０の値（ａ、ｂ、ｄ、ｅ、ｆ、ｈ）をそのまま保持する。このようにすることによって、図８（ａ）のａ〜ｈは、図７のプロセス処理の場合に比べて、値の変化回数が減ることがわかる。
【００７５】
図８（ａ）のＴ１〜Ｔ３は、第１ないし第８の中間値ｗ０〜ｚ０、ｗ１〜ｚ１を用いて、数１１で与えられる。
【００７６】
【数１１】
2008116856.tif 000013
【００７７】
ここで、中間値ｗ０〜ｚ０は、ａ〜ｄのいずれかの値が読み替えられた値であり、中間値ｗ１〜ｚ１は、ｅ〜ｈのいずれかの値が読み替えられた値である。例えば、ｔ＝０の場合、数１１のｗ０〜ｚ０、ｗ１〜ｚ１は、Initializeプロセスのａ〜ｈが読み替えられ、ｗ０＝ａ、ｘ０＝ｂ、ｙ０＝ｃ、ｚ０＝ｄ、ｗ１＝ｅ、ｘ１＝ｆ、ｙ１＝ｇ、ｚ１＝ｈとなる。また、例えば、ｔ＝１の場合、数１１のｗ０〜ｚ０、ｗ１〜ｚ１は、ｔ＝０のプロセスのａ〜ｈが読み替えられ、ｗ０＝ｄ、ｘ０＝ａ、ｙ０＝ｂ、ｚ０＝ｃ、ｗ１＝ｈ、ｘ１＝ｅ、ｙ１＝ｆ、ｚ１＝ｇとなる。
【００７８】
そして、ｔ＝０〜７９のプロセス後、図８（ｂ）のcomputeプロセスにおいて、図７（ｂ）と等価な中間ハッシュ値Ｈ０（ｉ）〜Ｈ７（ｉ）を得る。図８（ｂ）は、図７（ｂ）に示した数９と同様の演算式で表される。
これは、例えばｔ＝０、４、・・・、７６のとき、ｗ０＝ａ、ｘ０＝ｂ、ｙ０＝ｃ、ｚ０＝ｄ、ｗ１＝ｅ、ｘ１＝ｆ、ｙ１＝ｇ、ｚ１＝ｈ（図８（ａ）参照）であり、中間値ｗ０〜ｚ０、ｗ１〜ｚ１への読み替えが同じになる。すなわち、ｗ０〜ｚ０、ｗ１〜ｚ１への読み替えは４プロセスごとに循環しており、８０プロセス（ｔ＝０〜７９）は４の倍数であるため、computeプロセスでの読み替えが必要ないからである。
【００７９】
なお、このことは、ｔ＝０〜６３の６４プロセスとなるＳＨＡ−２２４、２５６の場合にも同じことがいえる。なぜなら、６４プロセスも、４の倍数のプロセスで終了するからである。そして、最終的には数１０のメッセージダイジェストを得る。
【００８０】
以上のように、図８（ａ）のプロセス処理によると、中間値ｗ０〜ｚ０、ｗ１〜ｚ１を用いてＴ１、Ｔ２、Ｔ３を求めることにより、ａ〜ｈは、それぞれ、４プロセスごとに、Ｔ１＋Ｔ２あるいはＴ３を保持する。そして、それ以外のプロセスでは、ａ〜ｈは、前の値をそのまま保持する。このため、図７（ａ）の場合に比べて、全プロセスにおけるａ〜ｈの値の変化回数が減少する。
【００８１】
次に、上記図８のＳＨＡ−２のハッシュ演算処理を行うＳＨＡ演算回路（ＳＨＡ演算装置）の構成について図９を参照して説明する。
図９は本発明の実施の形態２に係るＳＨＡ演算回路２０の構成例を示すブロック図である。
図９において、ＳＨＡ演算回路２０は、ハッシュ保持部２１、第１ないし第８の記憶部２２Ａ〜２２Ｈ、演算部２３、第１の定数設定部（Ｗｔ設定部）２４および第２の定数設定部（Ｋｔ設定部）２５を含んでいる。さらに、ＳＨＡ演算回路２０は、選択部２６および２つの読替部２７Ａ、２７Ｂをさらに含んでいる。なお、２つの読替部２７Ａ、２７Ｂは１つで構成するようにしてもよい。
【００８２】
選択部２６は、図８（ａ）のプロセスに従って、Ｔ１＋Ｔ２またはＴ３を格納する各記憶部を選択する。この選択に際して、選択部２６は、所定の選択信号ＥＮａ〜ＥＮｈを生成し、その選択信号を、選択する記憶部へ出力する。なお、ＥＮａ＝ＥＮｅ、ＥＮｂ＝ＥＮｆ、ＥＮｃ＝ＥＮｇ、ＥＮｄ＝ＥＮｈの関係がある。
例えば、図８（ａ）のｔ＝０の場合、選択部２６は、記憶部２２Ｄへ選択信号ＥＮｄを出力し、記憶部２２ＤにＴ１＋Ｔ２を保持させる。さらに、選択部２６は、記憶部２２Ｈへ選択信号ＥＮｈを出力し、記憶部２２ＨにＴ３を保持させる。
【００８３】
各読替部２７Ａ、２７Ｂは、例えば、複数個の４to１セレクタで構成され、図８（ａ）のプロセスに従って、各記憶部２２Ａ〜２２Ｈから取得したａ〜ｈを中間値ｗ０〜ｚ０、ｗ１〜ｚ１に読み替える。
例えば、図８（ａ）のｔ＝０の場合、読替部２７Ａは、各記憶部２２Ａ〜２２Ｄから取得したａ〜ｄをそのまま、ｗ０〜ｚ０に読み替える。そして、読替部２７Ｂは、各記憶部２２Ｅ〜２２Ｈから取得したｅ〜ｈをそのまま、ｗ１〜ｚ１に読み替える。
【００８４】
演算部２３は、図８（ａ）のプロセスに従って、読替部２７Ａから取得した中間値ｗ０〜ｚ０、読替部２７Ｂから取得した中間値ｗ１〜ｚ１、第１の定数設定部２４に設定されたＷｔ、および第２の定数設定部２５に設定されたＫｔに基づいて、Ｔ１＋Ｔ２およびＴ３を演算する。このときの演算式は、数１１のとおりである。
【００８５】
各記憶部２２Ａ〜２２Ｈ（各記憶部２２Ａ〜２２Ｄは第１のグループに属し、各記憶部２２Ｅ〜２２Ｈは第２のグループに属する）は、例えばフリップフロップで構成され、選択部２６からの選択信号に基づいて、所定の値（ａ〜ｈ、Ｔ１＋Ｔ２、Ｔ３）を格納する。そして、各記憶部２２Ａ〜２２Ｈは、ｔ＝７９（またはｔ＝６３）のプロセス後、ａ〜ｈをハッシュ保持部２１へ出力する。この出力を受けて、ハッシュ保持部２１は、図８（ｂ）のcomputeプロセスを実行し、出力されたａ〜ｈおよび前回のハッシュ値Ｈ０（ｉ−１）〜Ｈ７（ｉ−１）に基づいて中間ハッシュ値Ｈ０（ｉ）〜Ｈ７（ｉ）を得る。
【００８６】
例えば、ｔ＝１の場合、記憶部２２Ｃがｃ＝Ｔ１＋Ｔ２を保持し、記憶部２２Ｇがｇ＝Ｔ３を保持する。そして、残りの記憶部２２Ａ、２２Ｂ、２２Ｄ〜２２Ｆ、２２Ｈが、１つ前のプロセスｔ＝０の値（ａ、ｂ、ｄ〜ｆ、ｈ）をそのまま保持する。これにより、図８（ａ）のプロセス処理時の各記憶部２２Ａ〜２２Ｈは、各記憶部間で値を移動（シフト動作）することになる図７（ａ）の場合と異なり、各記憶部２２Ａ〜２２Ｈ間の値の移動がなくなる。
また、各記憶部２２Ａ〜２２Ｈは、４プロセスごとに、Ｔ１＋Ｔ２あるいはＴ３を保持することになる。
よって、各記憶部２２Ａ〜２２Ｈのハードウェアの駆動率が減少し、ＳＨＡ演算回路２０の消費電力が低減する。
【００８７】
なお、本発明は、実施の形態１、２に限られるものではなく、種々の変形が可能である。例えば、記憶部は、フリップフロップで構成した場合について説明したが、ＲＡＭ（Random Access Memory）などのメモリを用いて構成してもよい。
また、実施の形態２では、２つのグループに記憶部を分類した場合について説明したが、グループ分けをすることなく、適用してもよい。
【図面の簡単な説明】
【００８８】
【図１】一般的なＳＨＡ−１のプロセス処理を示す説明図。
【図２】一般的なＳＨＡ−１のＳＨＡ演算回路の構成例を示す図。
【図３】本発明の実施の形態１に係るＳＨＡ−１のプロセス処理を示す説明図。
【図４】本発明の実施の形態１に係るＳＨＡ−１のＳＨＡ演算回路の構成例を示す図。
【図５】図４の第１の記憶部の構成例を示す回路図。
【図６】図３のＳＨＡ−１のプロセス処理の変形を示す説明図。
【図７】一般的なＳＨＡ−２のプロセス処理を示す説明図。
【図８】本発明の実施の形態２に係るＳＨＡ−２のプロセス処理を示す説明図。
【図９】本発明の実施の形態２に係るＳＨＡ−２のＳＨＡ演算回路の構成例を示す図。
【符号の説明】
【００８９】
１０    ＳＨＡ演算回路
１１    ハッシュ保持部
１２１Ａ〜１２１Ｅ  記憶部
１３１  演算部
１４    第１の定数設定部
１５    第２の定数設定部
１６    選択部
１７    読替部
【図１】
2008116856.tif 000014
【図２】
2008116856.tif 000015
【図３】
2008116856.tif 000016
【図４】
2008116856.tif 000017
【図５】
2008116856.tif 000018
【図６】
2008116856.tif 000019
【図７】
2008116856.tif 000020
【図８】
2008116856.tif 000021
【図９】
2008116856.tif 000022