(57)【特許請求の範囲】
【請求項１】
３２ビットの第１から第５のラッチと、１つまたは２つ以上の中間値ラッチと、第１の演算回路と、第２の演算回路と、演算に使われるデータを入力するデータ入力信号線と、演算に使われる定数を入力する固定信号線を備え、あるサイクルにおいて、該第１の演算回路において、少なくとも該第１のラッチのデータを左へ５ビット回転シフトした値と該中間値ラッチのデータの加算を行ない演算結果を該第１のラッチへ入力し、該第２の演算回路において、後のサイクルのための中間値を演算し、該中間値ラッチへ入力することにより、該第１のラッチへ入力するデータを求める演算を該第１の演算回路と該第２の演算回路に分け並行して動作させ、演算回路のディレイを小さくし、ＳＨＡ演算を高速に処理する特徴を持った高速演算回路。
【請求項２】
請求項１のデジタル回路であって、該第２の演算回路において、後のサイクルのための中間値を、該第１から該第３のラッチのデータによる演算結果と該第４のラッチのデータと該データ入力信号線のデータとを加算し、該中間値ラッチへ入力することと、該第１の演算回路において、該第１のラッチと該中間値と該固定信号からのデータとを加算し、該第１のラッチへ入力することを特徴とする高速演算回路。
【請求項３】
３２ビットの第１から第５のラッチと、１つまたは２つ以上の中間値ラッチと、第１の演算回路と、第２の演算回路と、第３の演算回路と、演算に使われるデータを入力するデータ入力信号線と、演算に使われる定数を入力する固定信号線を備え、あるサイクルにおいて、該第１の演算回路において、少なくとも該第１のラッチのデータを左へ５ビット回転シフトした値と該中間値ラッチのデータの加算を行ない演算結果を該第２のラッチへ入力し、該第２の演算回路において、少なくとも該第１の演算回路の演算データを用いて、後のサイクルのための中間値を演算し、該中間値ラッチへ入力し、該第３の演算回路において、該第１の演算回路の演算データと、該第１から該第３のラッチのデータによる演算結果と、該第４のラッチのデータと、該データ入力信号線のデータと、該固定信号からのデータとを加算し、該第１のラッチへ入力することにより、該第２の演算回路と該第３の演算回路を並行して動作させ、演算回路のディレイを小さくし、ＳＨＡ演算を高速に処理する特徴を持った高速演算回路。
【請求項４】
請求項３のデジタル回路であって、該第２の演算回路において、後のサイクルのための中間値を、該第１の演算回路の演算データと該第１および該第２のラッチのデータによる演算結果と、該第３のラッチのデータと、該データ入力信号線のデータとを加算し、該中間値ラッチへ入力することと、該第１の演算回路において、該第１のラッチと該中間値と該固定信号からのデータとを加算し、該第１のラッチへ入力することを特徴とする高速演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、通信データや計算機データの安全性を高めるための暗号システムで用いられる要約関数ＳＨＡ（Ｔｈｅ  Ｓｅｃｕｒｅ  Ｈａｓｈ  Ａｌｇｏｒｉｔｈｍ）を処理するデジタル回路に関する。
【０００２】
【従来の技術】
ハッシュ演算ＳＨＡのアルゴリズムについては、フェデラル  インフォメーション  プロセッシング  スタンダード  パブリケーションズ（Ｆｅｄｅｒａｌ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｐｒｏｃｅｓｓｉｎｇ  Ｓｔａｎｄａｒｄｓ  Ｐｕｂｌｉｃａｔｉｏｎ）から公開されているフィップス  パブ  １８０−１、１９９５  エイプリル  １７、セキュア  ハッシュ  スタンダード（ＦＩＰＳ  ＰＵＢ１８０−１、１９９５  Ａｐｒｉｌ  １７、ＳＥＣＵＲＥ  ＨＡＳＨ  ＳＴＡＮＤＡＲＤ、Ｕ．Ｓ．ＤＥＰＡＲＴＭＥＮＴ  ＯＦ  ＣＯＭＭＥＲＣＥ  ／  Ｎａｔｉｏｎａｌ  Ｉｎｓｔｉｔｕｔｅ  ｏｆ  Ｓｔａｎｄａｒｄｓ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ）で規定される。
【０００３】
この中では規格の内容に加え、計算アルゴリズムも紹介されており、そのアルゴリズムは、メモリ効率や処理効率に優れている。紹介されているアルゴリズムの一つを、以下に簡単に説明する。
【０００４】
まず、ＳＨＡ演算を行なうメッセージを、５１２ｂｉｔの正数倍のデータへ変換するため、定められたメッセージパディングを行なう。メッセージパディングを行なったデータを、５１２ｂｉｔ毎に分割し、Ｍ1、Ｍ2、…、Ｍnとする。メッセージパディングについては、本発明の説明をする上で、特に重要ではないので説明を省略する。
次にＨ0、Ｈ1、…、Ｈ4を以下のように初期化する。
【０００５】
【数１】
0004206205.tif 000002
【数２】
0004206205.tif 000003
【数３】
0004206205.tif 000004
【数４】
0004206205.tif 000005
【数５】
0004206205.tif 000006
Ｍ1、Ｍ2、…、Ｍnの一つ毎に、以下の処理を行なう。
（ａ）  Ｍiを３２ｂｉｔ毎に１６分割し、Ｗ0、Ｗ1、…、Ｗ15とする。
（ｂ）  Ｗ0、Ｗ1、…、Ｗ15から、Ｗ16、Ｗ17、…、Ｗ79を求めるため、ｔ＝１６からｔ＝７９まで以下の処理を繰り返す。
【０００６】
【数６】
0004206205.tif 000007
ただし、関数Ｓy（ｘ）は、ｘをｙｂｉｔ左へ回転シフトする関数を示す。
（ｃ）  以下の処理を行なう。
【０００７】
【数７】
0004206205.tif 000008
【数８】
0004206205.tif 000009
【数９】
0004206205.tif 000010
【数１０】
0004206205.tif 000011
【数１１】
0004206205.tif 000012
（ｄ）  ｔ＝０からｔ＝７９まで以下の処理を繰り返す。本発明の説明で使われるループ演算とは、この数１２から数１７の処理を指している。
【０００８】
【数１２】
0004206205.tif 000013
【数１３】
0004206205.tif 000014
【数１４】
0004206205.tif 000015
【数１５】
0004206205.tif 000016
【数１６】
0004206205.tif 000017
【数１７】
0004206205.tif 000018
ただし、関数ｆtとＫtは以下のとおりである。
【０００９】
ｔが０から１９のとき、
【００１０】
【数１８】
0004206205.tif 000019
【数１９】
0004206205.tif 000020
ｔが２０から３９のとき、
【００１１】
【数２０】
0004206205.tif 000021
【数２１】
0004206205.tif 000022
ｔが４０から５９のとき、
【００１２】
【数２２】
0004206205.tif 000023
【数２３】
0004206205.tif 000024
ｔが６０から７９のとき、
【００１３】
【数２４】
0004206205.tif 000025
【数２５】
0004206205.tif 000026
（ｅ）  以下の処理を行なう。
【００１４】
【数２６】
0004206205.tif 000027
【数２７】
0004206205.tif 000028
【数２８】
0004206205.tif 000029
【数２９】
0004206205.tif 000030
【数３０】
0004206205.tif 000031
以上の（ａ）から（ｅ）までの処理をＭnまで繰り返し、最終結果のＨ0、Ｈ1、…、Ｈ4を連結した１６０ｂｉｔが、ＳＨＡ演算の結果となる。
【００１５】
【発明が解決しようとする課題】
上記に示す従来技術は、ソフトウェアによる処理に最適化したアルゴリズムである。アルゴリズムをハードウェアで実現した場合、ソフトウェアと異なり複数の処理を並列に実行する事が可能となる。そのため、ＳＨＡ演算の並列化できる処理部分において、ある特定の処理のみが複雑であるため、演算器の性能がその処理のディレイによって決まる。
【００１６】
具体的には、数１２から数１７の処理を、ソフトウェアによる処理では逐次処理するのに対し、ハードウェアでは、ＴＥＭＰへの代入を省略して、数３１から数３５の処理を並行して行なうことができる。例えば、Ａt、…、Ｅtをｔ回目のＡ、…、Ｅの値とすると、ｔ＝ｉにおけるループ演算では、以下に示す処理を行なう。
【００１７】
【数３１】
0004206205.tif 000032
【数３２】
0004206205.tif 000033
【数３３】
0004206205.tif 000034
【数３４】
0004206205.tif 000035
【数３５】
0004206205.tif 000036
この処理をハードウェアにより実現したとき、図１のようになる。このとき数３１から数３４の処理がラッチからラッチへのデータの代入する。これらに比べ、数３５の処理は、ＴＥＭＰを演算するために、関数ｆtによる論理演算と、５つの項の加算演算を行ってから、ラッチへ代入する。このため、数３１から数３４の処理に比べ数３５の処理は複雑である。また、数３１から数３５の処理はループ演算で８０回も繰り返されるため、数３５の処理が演算性能のボトルネックとなる。
【００１８】
本発明の目的は、数３５の処理を高速化し、ＳＨＡ演算全体の性能を向上させるデジタル回路を提供することにある。
【００１９】
【課題を解決するための手段】
ＳＨＡ−１演算の一連の処理の中で、
【００２０】
【数３６】
0004206205.tif 000037
の下線部の全体または一部を、前のサイクルまでに計算して中間結果として記憶しておき、次のサイクルでＢ、…、Ｅの処理と並行して、Ａの残りの処理を行なう。また、後のサイクルのＡの処理のための中間値の計算も並行して行なう。これにより数３５は分割され、デジタル回路においては並列処理が可能となるため、性能を向上させることが出来る。
【００２１】
【発明の実施の形態】
以下、本発明を適用したデジタル回路の実施形態の一例を、図面を参照しつつ説明する。図では、制御回路とセレクタ論理への制御信号は省略している。
【００２２】
図２は、本発明によるＳＨＡ演算器のデジタル回路の構成を示す図である。図２では、制御回路とセレクタ論理への制御信号は省略している。
【００２３】
４０１から４１２は３２ｂｉｔ分のラッチを、４１３は本発明による中間結果ＭＩＤの初期値を計算する回路で、次の演算を行なう。
【００２４】
【数３７】
0004206205.tif 000038
４１４は中間結果ＭＩＤを用いてＴＥＭＰの計算を行なう回路で、次の演算を行なう。
【００２５】
【数３８】
0004206205.tif 000039
４１５は次のループ演算で用いる中間結果ＭＩＤの計算を行なう回路で、次の演算を行なう。
【００２６】
【数３９】
0004206205.tif 000040
４１６はＴＥＭＰの計算を行なう回路で、次の演算を行なう。
【００２７】
【数４０】
0004206205.tif 000041
一度に２回分のループ演算を行なう場合においても、本発明により回路パスを４１５と４１６のように、並列に設計することが出来るため、ディレイの改善やマシンサイクルにあわせた回路設計を柔軟に行なえる。４１７は２入力の加算器を、４１８、４１９は、左へ３０ｂｉｔの回転シフターを示す。ここでＶ３２４は、信号線３２４経由で転送されるデータの値すなわち４１５の出力結果である。
【００２８】
ここで本発明を適用した回路による、ＳＨＡ演算の実行手順を説明する。４０１から４１１のラッチは、それぞれ更新されない場合は、同じ値を保持し続ける。まず、３０２から３０６の入力信号から、Ｈ0からＨ4の初期値または、演算を途中から再開する場合には計算途中のＨ0からＨ4の値を、４０１から４０５のラッチへ入力する。次に、３０１の入力信号からＷ0を入力し、４１３にてＭＩＤの初期値を計算して、４１１のラッチへ入力し、３１１から３１５の信号を４０６から４１０のラッチへ入力し、３０７の固定信号を４１２のラッチへ入力する。以上が、ＴＥＭＰを計算するループ演算をする前の処理である。１回目と２回目のループ演算は、３００の信号からＷ1を、３０１の信号からＷ2を同時に入力したサイクルに行ない、４０６のラッチへ３２５の信号を、４０７のラッチへ３２４の信号を、４０８のラッチへ３２８の信号を、４０９のラッチへ３２９の信号を、４１０のラッチへ３１８の信号を、４１１のラッチへ３２６の信号を入力し、それぞれのラッチを更新して行く。３回目と４回目のループ演算は、３００の信号からＷ3を、３０１の信号からＷ4を同時に入力したサイクルに行ない、１回目と２回目のループ演算と同様に、４０６のラッチへ３２５の信号を、４０７のラッチへ３２４の信号を、４０８のラッチへ３２８の信号を、４０９のラッチへ３２９の信号を、４１０のラッチへ３１８の信号を、４１１のラッチへ３２６の信号を入力し、それぞれのラッチを更新して行く。以下、７７回目と７８回目のループ演算まで、１回目と２回目のループ演算や３回目と４回目のループ演算と同様に、３００の信号から奇数番目のＷを、３０１の信号から偶数番目Ｗを小さい順番で同時に入力したサイクルに行ない、４０６のラッチへ３２５の信号を、４０７のラッチへ３２４の信号を、４０８のラッチへ３２８の信号を、４０９のラッチへ３２９の信号を、４１０のラッチへ３１８の信号を、４１１のラッチへ３２６の信号を入力し、それぞれのラッチを更新して行く。次に３００の信号からＷ79を、３０１の信号からは、任意のデータを入力し、４０６から４１０のラッチを更新しループ演算を終了する。また、ループ演算の１８、１９回目の結果を演算するときから３０８の固定信号を、３８、３９回目の結果を演算するときから３０９の固定信号を、５８、５９回目の結果を演算するときから３１０の固定信号を、４１２のラッチへ入力する。ループ演算８０回分が終了したところで、４１８の加算器により４０１のＡと４０６のＨ0を足し、結果を４０１へ入力する。４０２から４０５と４０７から４１０も同様にして加算した結果を４０２から４０５へ入力する。以上により、新しいＨ0からＨ4を計算することが出来る。
【００２９】
図３は、図２と異なる実施形態の１つの例であり、一度に１回のループ演算を行ない、回路パスを短くすることでより高速なマシンサイクルでの動作に適した、ＳＨＡ演算器のデジタル回路の構成を示す図である。
【００３０】
図３を構成する各部品は、図２とほぼ変わらないが、図２における前半ＴＥＭＰ演算器４１５は、信号の結線の変更により６０１の回路となり、数４１の演算を行なう。図３の回路構成によれば、図２の回路に比べ回路規模が小さく、演算パスが短いため、より早いマシンサイクルに対応できる。
【００３１】
【数４１】
0004206205.tif 000042
図３におけるＳＨＡ演算の手順を説明する。４０１から４１１のラッチは、それぞれ更新されない場合は、同じ値を保持し続ける。まず、３０２から３０６の入力信号から、Ｈ0からＨ4の初期値または、演算を途中から再開する場合には計算途中のＨ0からＨ4の値を、４０１から４０５のラッチへ入力する。次に、３００の入力信号からＷ0を入力し、４１３にてＭＩＤの初期値を計算して、４１１のラッチへ入力し、３１１から３１５の信号を４０６から４１０のラッチへ入力し、３０７の固定信号を４１２のラッチへ入力する。以上が、ＴＥＭＰを計算するループ演算をする前の処理である。ループ演算は、３００の信号からＷ1、Ｗ2、…、Ｗ79を、番号の小さい順に入力して、入力する毎に４０６のラッチへ３２４の信号を、４０７のラッチへ３１６の信号を、４０８のラッチへ３２８の信号を、４０９のラッチへ３１９の信号を、４１０のラッチへ３２０の信号を、４１１のラッチへ５０１の信号を入力し、それぞれのラッチを更新して行く。ループ演算中に、４１２のラッチへ、ループ演算の１９回目の結果を演算するときから１０８の固定信号を、３９回目の結果を演算するときから３０９の固定信号を、５９回目の結果を演算するときから３１０の固定信号を入力する。ループ演算８０回分が終了したところで、４１８の加算器により４０１のＡと４０６のＨ0を足して結果を４０１へ入力する。４０２から４０５と４０７から４１０も同様にして加算した結果を４０２から４０５へ入力する。以上により、図３による回路での、新しいＨ0からＨ4を計算することが出来る。
【００３２】
【発明の効果】
本発明によれば、ハードウェアによるＳＨＡ演算の
【００３３】
【数４２】
0004206205.tif 000043
の処理において、この処理を分割することによって、演算の後半と次の演算の前半とを並列に処理することができ、演算器のディレイを改善できるという利点が得られる。
【００３４】
また、ループ演算を多重化する場合においても、実装するマシンサイクルに合わせた回路設計を柔軟に行なうことが出来る。
【図面の簡単な説明】
【図１】規格で示されたアルゴリズムの一部をデジタル回路で示した図である。
【図２】本発明によるＳＨＡ演算器の一例での回路構成を示す図である。
【図３】本発明による図２と異なる実施形態のＳＨＡ演算器の一例での回路構成を示す図である。
【符号の説明】
１００−１０８…３２ｂｉｔ信号線、２００−２０６…３２ｂｉｔラッチ、２０７…ＴＥＭＰ演算器、２０８…左３０ｂｉｔ回転３２ｂｉｔシフタ、３００−３０６…３２ｂｉｔデータ入力信号線、３０７−３１０…３２ｂｉｔ固定信号線、３１１−３２９…３２ｂｉｔ信号線、４０１−４１２…３２ｂｉｔラッチ、４１３…ＴＥＭＰ初期中間値演算器、４１４…後半ＴＥＭＰ演算器、４１５…前半ＴＥＭＰ演算器、４１６…ＴＥＭＰ演算器、４１７…２入力３２ｂｉｔ加算器、４１８、４１９…左３０ｂｉｔ回転３２ｂｉｔシフタ、３００、３０２−３０６…３２ｂｉｔデータ入力信号線、３０７−３１０…３２ｂｉｔ固定信号線、３１１−３２４、３２７、３２８…３２ｂｉｔ信号線、４０１−４１２…３２ｂｉｔラッチ、４１３…ＴＥＭＰ初期中間値演算器、４１４…後半ＴＥＭＰ演算器、４１７…２入力３２ｂｉｔ加算器、４１８…左３０ｂｉｔ回転３２ｂｉｔシフタ、５０１…３２ｂｉｔ信号線、６０１…前半ＴＥＭＰ演算器。
【図１】
0004206205.tif 000044
【図２】
0004206205.tif 000045
【図３】
0004206205.tif 000046