マスク生成関数演算装置、そのプログラム及び記録媒体
【課題】 少ない演算量で高速に演算可能とする。
【解決手段】 乱数の種Ｃと所望出力長ＴＬｅｎが入力され（Ｓ１）、［ＴＬｅｎ／ＤＬｅｎ］によりハッシュ演算回数Ｎを、［ＣＬｅｎ＋４＋１＋８／ＢＬｅｎ］により各ハッシュ演算におけるブロック（要素）ハッシュ演算の繰返回数Ｍを求める。ＣＬｅｎ：Ｃの長さ、４：符号化部Ｉ２ＯＳＰ（ｎ，４）の長さ、１：パディング長、８：Ｃを符号化した長さ、［Ａ］はＡ以上の最少整数。ｎをＮ−１に初期化し、次回ｎ−１の演算で利用できる、つまり入出力が同一となる共通演算部分を計算し（Ｓ４）、その部分の各演算を実行し、その演算結果を演算中間値として記憶部に保存し（Ｓ６）、非共通演算部分の各演算は演算中間値をも入力して演算し、各ハッシュ演算の結果ｈ（ｎ）を保存し（Ｓ７）、ｎを−１して同様のことを繰返し、ｎ＝０で全てのｈ（ｎ）を連結して出力する。
【解決手段】 乱数の種Ｃと所望出力長ＴＬｅｎが入力され（Ｓ１）、［ＴＬｅｎ／ＤＬｅｎ］によりハッシュ演算回数Ｎを、［ＣＬｅｎ＋４＋１＋８／ＢＬｅｎ］により各ハッシュ演算におけるブロック（要素）ハッシュ演算の繰返回数Ｍを求める。ＣＬｅｎ：Ｃの長さ、４：符号化部Ｉ２ＯＳＰ（ｎ，４）の長さ、１：パディング長、８：Ｃを符号化した長さ、［Ａ］はＡ以上の最少整数。ｎをＮ−１に初期化し、次回ｎ−１の演算で利用できる、つまり入出力が同一となる共通演算部分を計算し（Ｓ４）、その部分の各演算を実行し、その演算結果を演算中間値として記憶部に保存し（Ｓ６）、非共通演算部分の各演算は演算中間値をも入力して演算し、各ハッシュ演算の結果ｈ（ｎ）を保存し（Ｓ７）、ｎを−１して同様のことを繰返し、ｎ＝０で全てのｈ（ｎ）を連結して出力する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、例えば情報セキュリティ技術に利用されハッシュ関数を用いて、乱数を生成するマスク生成関数の演算装置、そのプログラム及びその記録媒体に関する。
【背景技術】
【０００２】
情報セキュリティ技術で用いる乱数生成法は、順に生成される乱数値間の相関が低くなることが求められている。このような乱数を生成する方法として、マスク生成関数という演算方法がＩＥＥＥやＰＫＣＳで標準化されている。このマスク生成関数は、任意長の乱数の種から、ハッシュ関数演算を繰り返し行うことで、任意長の乱数を生成する。具体的な演算内容は、下記の数式で表され、この式中の先頭からＴＬｅｎオクテットをマスク生成関数とする。
Ｔ（Ｃ，ＴＬｅｎ）＝
Ｈ（Ｃ‖Ｉ２ＯＳＰ（０，４））‖Ｈ（Ｃ‖Ｉ２ＯＳＰ（１，４））‖
…‖Ｈ（Ｃ‖Ｉ２ＯＳＰ（Ｎ−１，４）） ……（１）
ここで、Ｃは乱数の種となる任意長の入力データ（以下乱数の種Ｃという）、ＴＬｅｎは所望の出力オクテット長である。１オクテットは８ビットを表わす単位である。また、Ｈ（Ｘ）はＸのハッシュ関数演算を、Ｉ２ＯＳＰ（ａ，４）（符号化部という）はオクテット長４である整数ａの符号化した表現を、Ａ‖ＢはＡとＢの連結を表す。Ｎは、所望するマスク生成関数の出力オクテット長ＴＬｅｎと、ハッシュ関数出力の固定オクテット長Ｄから計算され、下記の数式で表される。
【０００３】
Ｎ＝［ＴＬｅｎ／Ｄ］ （［Ｇ］はＧ以上の最小整数を表す。）
上述したハッシュ関数演算Ｈ（Ｘ）は、任意のハッシュ関数を使用できるが、従来はＦＩＰＳ１８０−２で規定されているＳＨＡ−１，ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２などのＳＨＡ系のアルゴリズムが使用される。ＳＨＡ系のそれぞれのアルゴリズムは、パラメータのサイズ等が異なるが、演算の構造はほぼ同じなので、代表して以下にＳＨＡ−１のアルゴリズムを説明する。
ＳＨＡ−１の演算は、メッセージと呼ばれる２６１オクテット以下の任意長の入力データ、この例ではＣ‖Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ−１）から、ダイジェストと呼ばれる２０オクテットの長さを出力する演算である。入力データはブロックと呼ばれる６４オクテット単位に演算されるため、下記手順で入力データを６４オクテットの整数倍に拡張する。すなわち、入力データの終端にビット“１”を結合し、（ブロック長６４オクテットの整数倍−８）オクテットまでビット“０”を結合し、最後に入力データ長を符号化した８オクテットデータを結合する処理が行われる。この処理をパディングという。
【０００４】
各ブロックに対する要素ハッシュ演算は以下のように演算される。即ち、入力された６４オクテットのブロックをそのまま４オクテット単位に分割してワードＷ０〜Ｗ１５とする。更にこれらＷ０〜Ｗ１５からＷｔ＝（Ｗｔ−16（＋）Ｗｔ−14（＋）Ｗｔ−８（＋）Ｗｔ−３）<<<１，…，ｔ＝１６，…，７６，Ｗ<<<１はＷを１ビット左巡環シフトすることを表わし、Ａ（＋）ＢはＡとＢのビット単位の排他的論理和を表わす。これら求めたワードＷ０〜Ｗ７９を、ダイジェストと同じ長さの中間バッファの内容に、順に混ぜ込みながら同様な演算を８０ステップ行う。中間バッファの初期値は、最初のブロックの要素ハッシュ演算の場合には、イニシャルベクタと呼ばれる予め定められた一定値であり、２番目以降のブロックの要素ハッシュ演算の場合には、前のブロックの要素ハッシュ演算の出力とする。前記中間バッファの内容に対する混ぜ込み演算は周知であるから説明を省略する（例えば……を参照）。全てのワードについて混ぜ込み演算を行った後、最終処理として、中間バッファの初期値を再度加算し、そのときのバッファ値を要素ハッシュ演算の出力とする。
【０００５】
なお、ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２などの他のＳＨＡ系アルゴリズムにおいては、上述したＳＨＡ−１アルゴリズムにおける混ぜ込み演算式や、ブロックやワードやダイジェストの長さが異なるだけで、演算の構造はほとんど同じである。
ここで、前述した通り、マスク生成関数演算処理は、ハッシュ演算の連結であるため、その演算処理量は、所望する出力オクテット長ＴＬｅｎにほぼ比例して大きくなる。また、一般的なハッシュ関数の演算処理は逐次的であるため、その演算処理量は入力オクテット長にほぼ比例する。よって、乱数の種と所望する出力オクテット長が増大すると、それに応じて演算処理量が増大する。
【０００６】
なお、特許文献１において、マスク生成関数演算処理と同様の演算を、入力された乱数部と結合する符号化部をそれぞれ別に演算することで、高速に演算する方法が示されている。つまり乱数の種Ｃを分割し、その各分割データごとに順次ハッシュ関数演算を行い、その演算結果と、各Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ）（符号化部）とについてハッシュ関数演算を行い、その演算結果を連結して出力する。
【特許文献１】特開２００２−３０４１２１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前記特許文献１に示す方法は、演算の内部処理がハッシュ関数の入力ブロックサイズ単位でしか処理できないため効率が悪いという問題があった。また、符号化部を含むデータは必ず繰り返し演算するため、実際には値が変わらない場合でも繰り返し演算するため、効率が悪いという問題があった。
この発明の目的は、値が変わらない繰り返し演算を行うことなく、入力である乱数の種のオクテット長と、所望する出力のオクテット長が大きいときに、演算処理量が増大するという課題を解決するマスク生成関数演算装置、そのプログラム及びその記録媒体を提供することにある。
【課題を解決するための手段】
【０００８】
この発明によるマスク生成関数演算装置においては、演算に先立ち、入力データから共通に行われる共通演算部分を判定し、その共通演算部分の演算結果を保存し、その共通演算部の演算結果を、非共通演算部分の演算に利用する。即ち、入力データと所望する出力長とが入力され、これらとハッシュアルゴリズムに基づくパラメータとからマスク生成関数演算の繰り返し内容が計算され、繰り返し演算の中途で入出力が同一となる共通演算部分が入力データ及び上記パラメータから計算され、共通演算部分について演算された演算中間値が記憶部に保存され、その記憶部に保存した共通演算部分の演算結果も、非共通演算部分の演算の入力として演算が行われる。
【発明の効果】
【０００９】
この発明によれば、演算の中途で入出力が同一となる共通演算部分が計算され、共通演算部分の演算結果をそれ以外の演算に適宜使用するため、少ない計算量で高速に演算が可能となる。
【発明を実施するための最良の形態】
【００１０】
（第１の実施形態）
以下、図面を参照してこの発明装置の第１の実施の形態を説明する。その機能構成の主要部を示し、この装置は、乱数の種（入力データ）Ｃと、所望の出力オクテット長ＴＬｅｎが入力され乱数Ｔ（Ｃ）を出力する。
このマスク生成関数演算装置は、各部の動作を適切に制御することで、マスク生成関数演算装置の動作を制御する制御部１０と、入力から演算内容および演算動作内容を判定する判定部２０と、ブロック（要素）ＳＨＡ−１演算の途中の中間バッファ値、ステップ数、および演算結果であるダイジェストを出力できる要素ＳＨＡ−１演算部３０と、要素ＳＨＡ−１演算部３０の出力であるダイジェストを記憶するダイジェスト記憶部４０と、要素ＳＨＡ−１演算部３０の出力である中間バッファ値およびステップ数を記憶するバッファ記憶部５０と、ブロック（要素）ＳＨＡ−１演算を繰り返し行って得られるマスク値を記憶しておく出力記憶部６０を有する。この装置の処理手順の例を図２に示す。１８９オクテットの乱数の種Ｃと、所望の出力オクテット長ＴＬｅｎ＝６４００オクテットが入力したときを例として処理内容を説明する。
【００１１】
本実施例におけるマスク生成関数演算装置に、入力として乱数の種Ｃと、所望の出力オクテット長ＴＬｅｎ＝６４００が入力される（ステップＳ１）。
次に、判定部２０において演算内容の判定を行う（ステップＳ２）。異なる符号化部（ＣＩ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ−１）のＳＨＡ−１演算の回数ＮはＮ＝［ＴＬｅｎ／ＤＬｅｎ］を計算することで得られ、この数値例ではＮ＝［６４００／２０］＝３２０回と判定される。Ｎを符号化部数という。また、各ｎ（ｎ＝０，…，Ｎ−１）の値に対するブロック（要素）ＳＨＡ−１演算の回数ＭはＭ＝［（ＣＬｅｎ＋４＋１＋８）／ＢＬｅｎ］を計算することで得られる。ここでＳＨＡ−１演算に対する入力メッセージはＣ‖Ｉ２ＯＳＰ（ｎ，４）であり、分子はＳＨＡ−１演算処理に使用されるデータのオクテット数で、ＣＬｅｎは乱数の種Ｃのオクテット長であり、４はＩ２ＯＳＰ（ｎ，４）のオクテット長であり、１はメッセージがブロック長ＢＬｅｎ整数後でも必ず１ビットの“１”が付加されるから１オクテット分は長くなるからであり、８はメッセージの長さを表わす８オクテット長である。分母のＢＬｅｎはＳＨＡ−１の入力ブロックのオクテット長を表している。この数値例ではＣＬｅｎは１８９オクテットであるからｍはｍ＝［（１８９＋４＋１＋８）／６４］＝４と判定される。
【００１２】
以上により、この数値では図３に示すような演算を行うと判定部２０により判定されることになる。１８９オクテット長の乱数の種Ｃと各符号化部（Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，３１９）との結合およびパディングとメッセージ長に対するブロック（要素）ＳＨＡ−１演算は４回の繰返演算Ｃｎ，ｍ（ｍ＝０，１，…，３）を行うことになる。その結果、各２０オクテット長の演算結果ｈ（ｎ）が得られる。なおＳＨＡ−１演算の数Ｎ、つまり異なる符号化部との組み合せＳＨＡ−１演算回数（符号化部数という）Ｎと各ＳＨＡ−１演算におけるブロック（要素）ＳＨＡ−１演算の繰り返し回数（繰返回数という）Ｍは、判定部２０内の演算内容計算部２１に、ＴＬｅｎ，ＣＬｅｎ（乱数の種Ｃより得られる）と、パラメータレジスタ２４よりのＤＬｅｎ，ＢＬｅｎが入力されて演算される。
【００１３】
次に、ステップＳ２で判定したＮを用いて、判定部２０の内部に有するｎカウンタをＮ−１である３１９に初期化する（ステップＳ３）。その後、ｎカウンタをカウント値ｎが３１９から０になるまで減算しながら、ブロック（要素）ＳＨＡ−１演算を繰り返して演算を進める（ステップＳ４〜Ｓ８）。
ここで、ｎを降順に演算する理由について説明する。即ち、乱数の種Ｃはｎによらずすべて一定値であるため、入力データＣ‖Ｉ２ＯＳＰ（ｎ，４）の先頭からＣＬｅｎオクテットは全てのｎに対して同じデータ値である。また、Ｉ２ＯＳＰ（ｎ，４）は、オクテット長４であり、かつ整数ｎを符号化したものを表わすため、先頭から（４−［（ｎ＋１）ｍｏｄ２５６］）オクテットは、全ビット“０”である。Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテット長は、ｎが大きくなるほど短くなる。よって、あるｎのＳＨＡ−１演算の入力データのうち、Ｃと、Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテットまでの入力データ（メッセージ）は、ｎ−１におけるＳＨＡ−１演算の入力データＣ‖Ｉ２ＯＳＰ（ｎ−１，４）でも同一となる。よってＳＨＡ−１演算を逐次処理する際にはｎの最大値Ｎ−１から降順に演算しながら、前の演算の中間値を利用することが効率的である。よってこの実施形態ではｎ＝３１９から降順に演算を行う。
【００１４】
次に、初回（ｎ＝３１９）におけるブロック（要素）ＳＨＡ−１演算について説明する。
はじめに、演算のどの時点での中間値を次回（ｎ＝３１８）のＳＨＡ−１演算で利用できるかを判定部２０内の保存位置計算部２０ｃで判定する（ステップＳ４）。判定される中間値はブロック（要素）ＳＨＡ−１演算のダイジェスト出力か、ブロック（要素）ＳＨＡ−１演算のブロックＷ０〜Ｗ１５のいずれかまでの演算の中間値である。これは、ＳＨＡ−１演算の場合、Ｗ０〜Ｗ１５については、６４オクテットの入力を先頭から順番に４オクテット単位で割り付けたものである。したがって、イニシャルベクタもしくは前ブロックの要素ＳＨＡ−１演算の結果が等しく、入力ブロックの内容が途中から異なる場合には、４オクテット単位で割り付けたＷ０〜Ｗ１５のうち、先頭からのデータが等しくなるところまでの演算内容は同じであり、そこまで演算したときの中間バッファ値は同じとなる。つまり、中間バッファの初期値と、共通演算部分だけ混ぜ込んだバッファを記憶しておき、それらを入力として異なる入力ブロックの割付部分から演算を行うことで、ＳＨＡ−１演算を中途から演算できる。
【００１５】
初回（ｎ＝３１９）のＳＨＡ−１演算の入力データのうち、次回（ｎ＝３１８）の演算の入力データでも同一になるオクテット長ＺＬｅｎはＺＬｅｎ＝ＣＬｅｎ＋４−［ｎ ｍｏｄ２５６］で計算される。ここで、第２項以降は、Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテット長の計算である。数値例では同一データ長ＺＬｅｎ＝１８９＋４−［３１９ｍｏｄ２５６］＝１９１となる。この同一データ長ＺＬｅｎから、演算のどの時点での中間値を次回（ｎ＝３１８）のＳＨＡ−１演算で利用できるかを判定する。これは同一データ長ＺＬｅｎをブロック長ＢＬｅｎで割ったときの商Ｒと余りＳから判定する。ＺＬｅｎをＢＬｅｎで割ると、数値例では商Ｒが２で余りＳが６３となる。次回（ｎ＝３１８）の演算では、２回の繰り返しブロック（要素）ＳＨＡ−１演算と、そのあとの６３オクテット分のブロック（要素）ＳＨＡ−１演算入力までは、今回のブロック（要素）ＳＨＡ−１演算と同一の入力データとなる。なお６３オクテット分が何個分のワードに相当するかは、余りＳをワード長をＷＬｅｎで割った商から１を減算し値Ｕ＝［Ｓ／ＷＬｅｎ］−１で計算され、この数値例の場合は［６３／４］−１＝１５ワード分に相当する。以上より、初回（ｎ＝３１９）の演算において、２回の繰り返しブロック（要素）ＳＨＡ−１演算の後、１５ワード分の演算を行った時点における演算結果を中間値バッファに保存することを判定できる。
【００１６】
次に、ＳＨＡ−１演算を行う入力データを生成する（ステップＳ５）。初回（ｎ＝３１９）の入力データはＣ‖Ｉ２ＯＳＰ（３１９，４）である。
次に、ステップＳ５で生成されたデータに対して、要素ＳＨＡ−１演算部３０で繰り返し演算を行う（ステップＳ６）。ここで、ステップＳ４での判定に従い、２回の繰り返しブロック（要素）ＳＨＡ−１演算の後のダイジェスト出力Ｄをダイジェスト記憶部４０に、その後１５ワード分の演算を行った時点における演算中間値ｂをバッファ記憶部５０に記憶する。その後ｎ＝３１９に対するＳＨＡ−１演算における残りの全ての演算を行う。
【００１７】
次に、ステップＳ６で演算したＳＨＡ−１演算結果ｈ（３１９）を、出力記憶部６０に保存し、初回（ｎ＝３１９）の演算を終了する（ステップＳ７）。
次にステップＳ８でｎ＝０か否かの判定を行い、その判定結果が０でなければステップＳ８ａでｎを−１してステップＳ４に戻る。
以下に２回目（ｎ＝３１８）以降の演算ＳＨＡ−１を説明する。
２回目（ｎ＝３１８）の演算ＳＨＡ−１演算の前に、初回（ｎ＝３１９）の演算と同様に、次回（ｎ＝３１７）の演算で利用できる中間値の判定を行う（ステップＳ４）。その判定の結果、２回の繰り返しブロック（要素）ＳＨＡ−１演算のダイジェスト出力と、その後１５ワード分のブロック（要素）ＳＨＡ−１演算を行った時点におけるバッファ値の両方を保存すると判定されるが、これは初回（ｎ＝３１９）における判定結果と同じであるため、保存すべきダイジェスト出力Ｄおよび演算中間値は初回保存されたものと同一である。よって、ダイジェスト出力Ｄおよび演算中間値ｂの保存（更新）を省略することができる。
【００１８】
２回目（ｎ＝３１８）の入力データの生成では、Ｃ‖Ｉ２ＯＳＰ（３１８，４）から先頭の２ブロックＣ３１８，０、Ｃ３１８，１を除いたデータを生成する（ステップＳ５）。これは、次ステップで、要素ＳＨＡ−１演算部に、初回（ｎ＝３１９）に保存したダイジェスト出力Ｄおよび演算中間値ｂを入力することで、途中から演算を開始することで、先頭の２ブロック分の演算を代用するためである。
次に、ステップＳ５で生成されたデータと、ダイジェスト出力Ｄおよび演算中間値ｂを用いて、要素ＳＨＡ−１演算部で繰り返し演算を途中から行う（ステップＳ６）。なお、ステップ４で、ダイジェスト出力Ｄおよび演算中間値ｂの保存（更新）が省略可能であると判定されたため、中間結果の保存は行わない。ＳＨＡ−１演算結果ｈ（３１８）を、出力記憶部６０に保存して、２回目（ｎ＝３１８）の演算を終了する。
【００１９】
このようにして、前回の演算で判定保存されたダイジェスト出力Ｄおよび演算中間値ｂの保存を利用して、ＳＨＡ−１演算を途中から行いながら、次回の演算で利用できるダイジェスト出力Ｄおよび演算中間値ｂを更新し、最終結果ｈ（ｎ）を蓄積保存していく。
なお、このように演算を進めていくと、ｎ＝２５６の演算におけるダイジェストＤおよび演算中間値ｂの判定では、ＺＬｅｎ＝１８９−４［２５６ｍｏｄ２５６］＝１９２をＢＬｅｎ＝６４で割ると、商が３で余りが０となる。よって、ｎ＝２５６における３回の繰り返しブロック（要素）ＳＨＡ−１演算のダイジェスト出力Ｄを保存しておき、次回のＳＨＡ−１演算でこれを入力とすることで、３回の繰り返し演算を省略することができる。このように、余りの０になるなど、０ワード目に相当する余りの場合、その次回のＳＨＡ−１演算では演算中間値ｂは使用されないため、演算中間値ｂの保存は省略される。
【００２０】
このような演算を全てのｎに対して行った後、出力記憶部６０に保存されているｈ（０）からｈ（３１９）をｈ（０）‖ｈ（１）‖…‖ｈ（３１９）のように連結し（ステップＳ９）、これをその先頭からＴＬｅｎの長さだけ出力とする。
図２中のステップＳ２における演算内容Ｎ，Ｍの計算は判定部２０における演算内容計算部２１で行われる。図４中に示すように演算内容計算部２１内の符号化数計算部２１ａにＴＬｅｎとＤＬｅｎが入力されＮ＝［ＴＬｅｎ／ＤＬｅｎ］が計算される。また演算内容計算部２１内の繰返回数計算部２１ｂにＣ，ＢＬｅｎが入力されＭ＝［（ＣＬｅｎ＋４＋１＋８）／ＢＬｅｎ］が計算される。図２中のステップＳ３での初期化は判定部２０内のｎカウンタ（演算要素カウンタ）２１ｃに計数値ｎとしてＮ−１を設定することにより行われる。ｎカウンタ２１ｃは１回のＳＨＡ−１演算が終了するごとに制御部１０からの指示により１減算される。また判定部２０内のパラメータレジスタ２５にＳＨＡ−１演算出力長ＤＬｅｎ、ブロック長ＢＬｅｎ、ワード長ＷＬｅｎ、乱数の種長ＣＬｅｎなどが格納されている。ＣＬｅｎは前処理として予め求められているものとする。
【００２１】
上述した保存位置Ｒ，Ｓ，Ｕの計算、ダイジェストＤ、演算中間値ｂの保存、再利用処理などのための機能構成例および処理手順の例を図４および図５を参照して説明する。
ステップＳ１１でバッファ記憶部５０内の中間値バッファ（以下Ｂバッファという）５０ａの内容ＢをＳＨＡ−１で規定されるイニシャルベクタ値ＩＶに初期化し、ダイジェスト記憶部４０内のダイジェストバッファ（以下Ｄバッファという）の内容Ｄ，ＳＨＡ−１演算の中間値（２０オクテット）ｂ、ＳＨＡ−１演算の入力値で最終処理に使用する初期データｄをそれぞれ０に初期化し、判定部２０内のｍカウンタ２１ｄの計数値ｍを０に、要素ＳＨＡ−１演算部３０内の演算ステップ数０〜７９を計数するｗカウンタ３０ａの計数値ｗを０に初期化する。
【００２２】
ステップＳ１２で入力データにおいて、次のＳＨＡ−１演算においても同一となる同一長ＺＬｅｎ＝ＣＬｅｎ＋４−［ｎ ｍｏｄ２５６］の計算が行われる。この計算は判定部２０における保存位置計算部２２内の同一長計算部２２ａにＣとｎが入力されて行われる。その後、ステップＳ１３で位置計算部２２ｂでＺＬｅｎとＢＬｅｎが入力されてその商Ｒと余りＳとが計算され、更にステップ計算部２２ｃでＵ＝［Ｓ／ＷＬｅｎ］−１が計算される。これらが図２中のステップＳ４と対応する。商Ｒは共通演算部分のブロック数であるから位置計算部２２ｂは共通ブロック数計算部ともいえる。
【００２３】
ステップＳ１４で演算開始時の各種データ、つまりＢバッファ５０ａの内容がＳＨＡ−１演算の中間値ｂとして、Ｄバッファ４０ａの内容がブロック（要素）ＳＨＡ−１演算の入力値で最終処理に使用するデータｄとして、またｍバッファ４０ｂの内容ｍ、ｗバッファ５０ｂの内容ｗがそれぞれ取り出される。
ステップＳ１５でｎカウンタ２１ｃ及びｍカウンタ２１ｄの各カウント値ｎ，ｍからブロック（要素）ＳＨＡ−１演算に対する入力データＣｎ，ｍが、判定部２０におけるデータ生成部２３内のｎ，ｍブロック生成部２３ａで生成される。ステップＳ１６でその入力データＣｎ，ｍに対する演算はそのブロック（入力データ）の先頭、つまりｗ＝０回目から開始するか否かが、判定部２０内の先頭判定部２４ａにより判定される。
【００２４】
ｗ＝０と判定されるとステップＳ１７で演算中間値ｂ（最初（Ｎ−１，０）では０）が最終処理用入力値ｄとしてステップＳ１８に移り、第ｎ，ｍブロック（要素）のデータＣｎ，ｍのステップｗのブロック（要素）ＳＨＡ−１演算が要素ＳＨＡ−１演算部３０で行われる。ステップＳ１６でｗ＝０でないと判定されると直ちにステップＳ１８での演算が行われる。
次にステップＳ１９は演算中間値を保存すべき位置、つまりｍ＝Ｒかつｗ＝Ｕであるか否かの判定を中間値保存判定部２４ｂで行う。この判定保存位置でなければ、ステップＳ２０はブロックＳＨＡ−１演算が終了したか、つまりｗ＝７９か否かの判定をブロック演算終了判定部２４ｃで行い、ｗ＝７９ではなく、つまり終了でなければステップＳ２１でステップ数ｗを＋１して、ステップＳ１８に戻る。
【００２５】
ステップＳ１９の判定が保存位置であれば、ステップＳ２２でステップＳ１８で得られたＳＨＡ−１演算の中間値ｂをＢバッファ５０ａに格納保存すると共に、その時のステップ数ｗをｗバッファ５０ｂに格納保存してステップＳ２０へ移る。
ステップＳ２０でそのブロック（要素）ＳＨＡ−１演算が終了と判定すると、ステップＳ２３はブロック（要素）ＳＨＡ−１演算の最終処理、つまり、ＳＨＡ−１演算の最終（ステップｗ＝７９）の演算結果ｂとその要素ＳＨＡ−１演算の初期入力値ｄを要素ＳＨＡ−１演算部３０内の加算部３０ｂで加算し、その加算結果を演算中間値ｂとする。
【００２６】
次にステップＳ２４はダイジェスト保存位置か否か、つまりｍ＝Ｒ−１か否かの判定をダイジェスト保存判定部２４ｂで行う。この判定が保存位置でなければステップＳ２５はそのｎにおけるＳＨＡ−１演算が終了したか、つまりｍ＝Ｍ−１となったか否かの判定を要素演算終了判定部２４ｅで行う。ステップＳ２４でダイジェスト保存位置である、つまり共通演算部分におけるブロック単位の演算が終了したと判定されると、ステップＳ２６はＢバッファ５０ａにステップＳ２３で求めた演算中間値ｂを、またその時のステップ数ｗをｗバッファ５０ｂにそれぞれ格納保存してステップＳ２５に移る。
【００２７】
ダイジェスト保存判定部２４ｄは（共通演算部分のブロック単位演算）終了判定部ともいえる。
ステップＳ２５の判定がそのｎにおけるＳＨＡ−１の演算が終了していなければ、ステップＳ２７はｍカウンタ２１ｄを＋１し、かつｗカウンタ３０ａを０にリセットしてステップＳ１５に戻る。ステップＳ２５の判定が終了していればステップＳ２８はその時のステップＳ２３の最終処理結果（演算中間値）ｂをその第ｎＳＨＡ−１演算結果ｈ（ｎ）として出力記憶部６０に格納保存する。次のステップＳ２９は全ての演算が終了したか、つまりｎ＝０であるか否かを最終判定部２４ｆで判定し、その判定が終了でなければステップＳ３０でｎカウンタ２１ｃを１減算してステップＳ１２に戻る。ステップＳ２８，Ｓ２９，Ｓ３０は図２中のステップＳ７，Ｓ８，Ｓ８ａとそれぞれ対応する。ステップＳ２９の判定が終了であれば、その後の処理は図２に示した処理と同様である。
【００２８】
上述した処理において、各種パラメータの取り出し、各種判定結果に基づく、カウンタの歩進制御、各種データの保存処理、次の処理へ歩進、各部に対する動作指令などは制御部１０が行う。なおステップＳ１１の初期化処理は、図２中のステップＳ３の初期化処理で行ってもよい。ステップＳ１８〜Ｓ２７が図２中のステップＳ６と対応する。上述から理解されるように保存位置計算部２２で計算されたＲ，Ｓ，Ｔに基づいて、その時の演算中間値ｂを保存し、次のｎのＳＨＡ−１演算の前回と同一データでない部分の入力データ、つまりデータ生成部２３ａで生成されたデータであり、そのＳＨＡ−１演算としては途中からの演算となるが、それまでの演算結果として、前記保存した中間値ｂが再利用される。この点で保存位置計算部２２は共通演算計算部ともいえ、また前記途中からの演算は非共通部分の演算であり、データ生成部２３ａは非共通演算データ生成部といえる。
【００２９】
以上のように演算したときの、演算対象データを図６に示す。図中実線部分がＳＨＡ−１演算に利用されたデータを示し、破線部分は中間値ｂおよびダイジェストｄを利用することで省略されたデータを示す。最初のｎ＝Ｎ−１のＳＨＡ−１演算はすべてのブロックＣ３１９，０、Ｃ３１９，１、Ｃ３１９，２、Ｃ３１９，３に対し行われ、つまりすべてが非共通演算部分であるが、ｎ＝Ｎ−２のＳＨＡ−１演算は前記商Ｒと対応する最初の２つのブロックＣ３１８，０とＣ３１８，１はＣ３１９，０とＣ３１９，１と同一入力データとなり、またブロックＣ３１８，２中の最初の前記余りＳのワード数Ｕと対応する１５ワードはＣ３１９，２の対応ワードの入力データと同一であるから、これら同一データに対する演算中間値ｄ，ｂと、前回と異なる入力データ（非共通演算部分）Ｃ３１８，２の残りのワードデータ及びＣ３１８，３とが入力されて演算されることになる。ｎ＝２５５になるとその入力データは、その前のｎ＝２５６に対する入力データと最初から３つのブロックが同一となるため、非共通演算部分はＣ２５６，３のみとなり、これと前回演算中間値ｄ，ｂが演算に利用されることになる。
【００３０】
このように、入力である乱数の種のオクテット長と、所望する出力のオクテット長が大きいときにも、演算に先立ち、入力データから共通に行われる共通演算部分を判定し、その共通演算部分を繰り返し演算しないよう適切に演算を行うことで、演算処理量を削減することができる。
なお、この実施例では、すべてのｎに対するＳＨＡ−１演算結果ｈ（ｎ）を保存しておき、全ての演算が終了したときに、それらを連結して出力したが、各ｎにおけるＳＨＡ−１演算が終了次第、それらを順次出力しても良い。また、演算の効率を鑑みるとｎが大きいほうから降順でＳＨＡ−１演算するのが好適であるが、ｎを小さいほうから昇順で演算しても良い。
（第２の実施形態）
第２の実施形態はＩＳＯ／ＩＥＣ１８０３３−２で規定されているＰＳＥＣ−ＫＥＭの暗復号化システムにおいてそのマスク生成関数演算にこの発明によるマスク生成関数演算装置を適用したものである。以下では体が１６３ビットのＰＳＥＣ−ＫＥＭの暗号演算手順における、マスク生成関数演算装置の動作について説明する。
【００３１】
ＰＳＥＣ−ＫＥＭの暗号化演算での過程で、ＫＤＦ（Ｉ０‖Ｃ，［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ）の演算を行う。ここで、Ｉ０はＩ２ＯＳＰ（０，４）であり、μおよびＫｅｙＬｅｎはＰＳＥＣ−ＫＥＭで使用するパラメータである。また、ＫＤＦ（Ｘ，Ｐ）は、ＫＤＦ（Ｘ，Ｐ）＝Ｈ（Ｘ‖Ｉ２ＯＳＰ（０，４））‖Ｈ（Ｘ‖Ｉ２ＯＳＰ（１，４））…‖Ｈ（Ｘ‖Ｉ２ＯＳＰ（Ｎ−１，４））の演算を表している。ただしＨ（Ｘ）はＸのハッシュ演算を表しＰ＝［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ＝ＴＬｅｎ、Ｎ＝［ＴＬｅｎ／ＤＬｅｎ］，ＴＬｅｎは出力オクテット長、ＤＬｅｎはハッシュ関数演算結果長をそれぞれ表わしている。この演算をこの発明によるマスク生成関数演算装置によって行う。この暗号化演算装置の機能構成例を図７に示す。ＰＳＥＣ−ＫＥＭ演算部１００から乱数の種Ｃ（ｓｅｅｄ）、出力オクテット長ＴＬｅｎおよび使用ハッシュ関数を表わす関数符号ＨＡがこの発明によるマスク生成関数演算装置２００に入力され、マスク生成関数演算装置２００から、生成乱数Ｔ（ｓｅｅｄ）がＰＳＥＣ−ＫＥＭ演算部１００に入力される。
【００３２】
この実施例では、［Ｌｏｇ２５６μ］＝２１オクテット、ＫｅｙＬｅｎ＝６４オクテット、Ｃは１２８オクテットの乱数の種ｓｅｅｄを使用する。したがって、マスク生成関数演算装置２００の２つの入力である乱数の種Ｃと所望の出力長ＴＬｅｎは、それぞれ、１３２オクテットのＩ０‖ｓｅｅｄと、１０１オクテット（２１＋１６＋６４）であり、その出力は、ＫＤＦ（Ｉ０‖ｓｅｅｄ，［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ）の演算結果である。
マスク生成関数演算装置２００の機能構成例は図７に示すように、制御部２１０と、判定部２２０と、複数の要素ハッシュ関数演算部としての要素ＳＨＡ−１演算部２３０、要素ＳＨＡ−２５６演算部２４０、要素ＳＨＡ−３８４演算部２５０、要素ＳＨＡ−５１２演算部２６０と、中間データ記憶部２７０と、出力記憶部２８０とを備える。
【００３３】
この第２の実施形態におけるマスク生成関数演算装置２００による処理を、図８に示すフローチャートを基に説明する。また判定部２２０の具体的機能構成例を図９に示す。
ＰＳＥＣ−ＫＥＭ演算部１００において生成されたｓｅｅｄ（Ｃ）、所望の出力長ＴＬｅｎ、例えば１０１オクテット、および、ＫＤＦに使用するハッシュ演算アルゴリズムを表わす関数符号ＨＡ、例えば０が、マスク生成関数演算装置２００に入力される（ステップＳ１）。
次に、判定部２２０において演算内容の計算を演算内容計算部２２１で行う（ステップＳ２）。
【００３４】
演算で使用するＫＤＦのアルゴリズムは、ステップＳ１で入力されたＨＡから、判定部２２０に設定したアルゴリズムテーブル２２２を参照することで判定する。例えばＨＡ＝０であって、ＫＤＦのアルゴリズムはＳＨＡ−１を選択する。
ＳＨＡ−１演算の繰り返し回数、つまり符号化部数ＮはＮ＝［ＴＬｅｎ／ＤＬｅｎ］を符号化部数計算部２２１ａで計算することで得られ、この数値例ではＮ＝［１０１／２０］＝６回と計算される。また、各ｎ（ｎ＝０，１，…，Ｎ−１）の値に対するブロック（要素）ＳＨＡ−１演算の回数ＭはＭ＝［（ＣＬｅｎ＋４＋８）／ＢＬｅｎ］を繰返回数計算部２２１ｂで計算することで得られる。この数値例ではＭ＝［（１２８＋４＋１＋８）／６４］＝３回と計算される。
【００３５】
以上によりこのマスク生成関数演算は図１０に示すようにＩ０‖ＣとＩ２ＯＳＰ（０，４）及びパディング〜Ｉ０‖ＣとＩ２ＯＳＰ（５，４）及びパディングの６回のＳＨＡ−１演算を行い、各ＳＨＡ−１演算では３回のブロック（要素）ＳＨＡ−１演算を繰り返し行うことになる。
次に、判定部２２０において、共通演算部分の共通演算部分および個別演算部分の判定を行う（ステップＳ３）。共通演算部分は、全てのｎに対して、先頭から同一となるブロック数ｋを判定することで行う。共通演算数計算部２２３にＣ，Ｎ、ブロック長ＢＬｅｎが入力されてｋ＝［（ＣＬｅｎ＋４−［ｌｏｇ２５６（Ｎ＋１）］）／ＢＬｅｎ］−１が計算される。この数値例ではｋ＝［（１２８＋４−［ｌｏｇ２５６（６＋１）］）／６４］−１＝２と演算される。つまり、全てのｎに対して共通演算部分は先頭から２ブロック（１２８オクテット）であり、３ブロック目は個別演算部分であると判定される。以降は、この判定結果に従って制御部２１０の制御によって演算を進めていく。
【００３６】
次に、共通演算部分のＳＨＡ−１演算を行う。共通演算部分である、Ｉ０‖ｓｅｅｄの先頭２ブロックに対して、ＳＨＡ−１演算を行う。まずステップＳ４でｎカウンタ２２１ｃ、ｍカウンタ２２１ｄの各計数値ｎ，ｍをそれぞれ０に初期化し、ステップＳ５で入力データ生成部２２４ａにて、ｍが入力されてデータ（Ｉ０‖Ｃ，Ｉ２ＯＳＰ（ｎ，４）に対する第０ブロック目のデータＣ０，０が生成され、ステップＳ６でそのデータＣ０，０に対し要素ＳＨＡ−１演算部２３０によるＳＨＡ−１演算を行い、ステップＳ７でその演算結果であるダイジェストＤを中間データ記憶部２７０に保存する。
【００３７】
ステップＳ８で共通演算部分のブロックでないか、つまりｍ＝ｋ−１であるか否かを共通部判定部２２５で判定し、その判定が否であればステップＳ９でｍカウンタ２２１ｄを１歩進してステップＳ５に移る。これらステップＳ４〜Ｓ９の処理は共通演算部分の第０回目（ｎ＝０）における入力データを（Ｉ０‖Ｃ）とイニシャルベクタ又は記憶部２７０中のダイジェストＤを入力とするＳＨＡ−１演算である。機能構成的にはこの演算が共通部計算部を構成することになる。
ステップＳ８での判定がｍ＝ｋ−１、この例ではｍ＝１つまり共通演算部分に対する計算の終了であればステップＳ１０でｍカウンタ２２１ｄを１歩進し、ステップＳ１１で第ｎ回目のＳＨＡ−１演算ＳＨＡ−１のデータ（Ｉ０‖Ｃ，Ｉ２ＯＳＰ（Ｎ−１，４）における第ｍ回目のブロックデータＣ０，ｍ、この例ではＣ０，２がデータ生成部２２４ｂで生成される。なおこの時共通部判定部２２５の判定出力が否定であってデータ生成部２２４ａではなくデータ生成部２２４ｂが動作するステップＳ１２ではステップＳ７で保存したダイジェストＤに対してこのデータＣ０，２を用いて要素ＳＨＡ−１演算部２３０でＳＨＡ−１演算を行い、ステップＳ１３ではｍカウンタ２２１ｄの計数値ｍが繰返回数と等しいか、つまりｍ＝Ｍ−１か否かを繰返終了判定部２２６で判定する。この判定結果が終了でなければステップＳ１４でその演算結果であるダイジェストＤを中間データ記憶部２７０に保存してステップＳ１０に戻る。ステップＳ１３の判定が終了であればステップＳ１５でステップＳ１２の演算結果ｈ（ｎ）を出力記憶部２８０に保存し、ステップＳ１６ではｎカウンタ２２１ｃの計数値ｎがｎ＝Ｎ−１か、つまりＳＨＡ−１の演算が終了したか否かの判定が最終判定部２２７で行う。この判定が終了でなければステップＳ１７ではｎカウンタ２２１ｃを１歩進させ、更にステップＳ１８ではｍカウンタ２２１ｄをｋ−１に初期化してステップＳ１０に戻る。この数値例ではｋ＝２，Ｍ＝３であるから、ステップＳ１３，Ｓ１４，Ｓ１８を省略し、破線で示すようにステップＳ１２より直ちにステップＳ１５に移り、ステップＳ１７よりステップＳ１１に直ちに移ることになる。なおこの第２の実施形態の説明を簡略にするため中間データ記憶部２７０に保存したデータと、これより取り出して要素ＳＨＡ−1演算部２３０で使用するデータとして同一表記とした。
【００３８】
これらステップＳ１０〜Ｓ１７は非共通部の演算であり、機能構成的には個別計算部を構成することになる。
ステップＳ１６での判定が終了であれば、ステップＳ１９では出力記憶部に保存されているｈ（０）からｈ（５）をｈ（０）‖ｈ（１）‖…‖ｈ（５）のように連結し、その先頭からＴＬｅｎオクテット長だけＰＳＥＣ−ＫＥＭ演算部１００への出力とする。ＰＳＥＣ−ＫＥＭ演算部１００は、マスク生成関数演算装置２００の出力を基に、ＰＳＥＣ−ＫＥＭの暗号演算を行う。
【００３９】
制御部２１０は各部の初期化、判定部２２０の各判定結果に基づく次の処理をその機能構成部に行わせるが、各演算結果の記憶部に対する保存、取り出し、処理の進行などを行う。ｐカウンタ２２１ｃ、ｍカウンタ２２１ｄなどは制御部２１０に設けるなどの変形をしてもよい、このことは第１の実施形態でも同様である。
以上のように演算したときの、演算対象データを図１１に示す。図中実線部分がＳＨＡ−１演算に利用されたデータを示し、破線部分はダイジェストＤを利用することで省略されたデータを示す。つまり第１回目のＳＨＡ−１演算はその全ブロックデータＣ０，０、Ｃ０，１、Ｃ０，２に対し行い、第２回目以後は入力データが共通とならないブロックデータＣ１，２，…，Ｃ５，２に対してのみ行う。このように計算することによって、少ない計算量でマスク生成関数演算が実行でき、これによりＰＳＥＣ−ＫＥＭの演算時間の短縮が出来る。
【００４０】
上述した各マスク生成関数演算装置はコンピュータにより機能させることもできる。例えば図１及び図４に示した機能構成による図２及び図５に示した処理を行う装置としてコンピュータを機能させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体からコンピュータにインストールし、又は通信回線を介してダウンロードし、そのプログラムを実行させればよい。第２の実施形態についても同様にコンピュータにより機能させることもできる。
【図面の簡単な説明】
【００４１】
【図１】この発明における装置の一実施形態における機能ブロック図。
【図２】この発明における装置の一実施形態における処理手順の例を示す流れ図。
【図３】第１の実施形態のマスク生成関数演算における各処理段階の各データを示した図。
【図４】図１中の判定部２０内の具体的機能構成例を示すブロック図。
【図５】図２中のステップＳ６における処理を中心とした具体例を示す流れ図。
【図６】第１の実施形態における実際に演算される各ブロックデータを示す図。
【図７】この発明における装置の他の実施形態における機能ブロック図。
【図８】この発明における装置の他の実施形態における処理手順の例を示す流れ図。
【図９】図７中の判定部２２０内の具体的機能構成例を示すブロック図。
【図１０】第２の実施形態のマスク生成関数演算における各処理段階の各データを示す図。
【図１１】第２の実施形態における実際に演算されるブロックデータを示す図。
【技術分野】
【０００１】
この発明は、例えば情報セキュリティ技術に利用されハッシュ関数を用いて、乱数を生成するマスク生成関数の演算装置、そのプログラム及びその記録媒体に関する。
【背景技術】
【０００２】
情報セキュリティ技術で用いる乱数生成法は、順に生成される乱数値間の相関が低くなることが求められている。このような乱数を生成する方法として、マスク生成関数という演算方法がＩＥＥＥやＰＫＣＳで標準化されている。このマスク生成関数は、任意長の乱数の種から、ハッシュ関数演算を繰り返し行うことで、任意長の乱数を生成する。具体的な演算内容は、下記の数式で表され、この式中の先頭からＴＬｅｎオクテットをマスク生成関数とする。
Ｔ（Ｃ，ＴＬｅｎ）＝
Ｈ（Ｃ‖Ｉ２ＯＳＰ（０，４））‖Ｈ（Ｃ‖Ｉ２ＯＳＰ（１，４））‖
…‖Ｈ（Ｃ‖Ｉ２ＯＳＰ（Ｎ−１，４）） ……（１）
ここで、Ｃは乱数の種となる任意長の入力データ（以下乱数の種Ｃという）、ＴＬｅｎは所望の出力オクテット長である。１オクテットは８ビットを表わす単位である。また、Ｈ（Ｘ）はＸのハッシュ関数演算を、Ｉ２ＯＳＰ（ａ，４）（符号化部という）はオクテット長４である整数ａの符号化した表現を、Ａ‖ＢはＡとＢの連結を表す。Ｎは、所望するマスク生成関数の出力オクテット長ＴＬｅｎと、ハッシュ関数出力の固定オクテット長Ｄから計算され、下記の数式で表される。
【０００３】
Ｎ＝［ＴＬｅｎ／Ｄ］ （［Ｇ］はＧ以上の最小整数を表す。）
上述したハッシュ関数演算Ｈ（Ｘ）は、任意のハッシュ関数を使用できるが、従来はＦＩＰＳ１８０−２で規定されているＳＨＡ−１，ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２などのＳＨＡ系のアルゴリズムが使用される。ＳＨＡ系のそれぞれのアルゴリズムは、パラメータのサイズ等が異なるが、演算の構造はほぼ同じなので、代表して以下にＳＨＡ−１のアルゴリズムを説明する。
ＳＨＡ−１の演算は、メッセージと呼ばれる２６１オクテット以下の任意長の入力データ、この例ではＣ‖Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ−１）から、ダイジェストと呼ばれる２０オクテットの長さを出力する演算である。入力データはブロックと呼ばれる６４オクテット単位に演算されるため、下記手順で入力データを６４オクテットの整数倍に拡張する。すなわち、入力データの終端にビット“１”を結合し、（ブロック長６４オクテットの整数倍−８）オクテットまでビット“０”を結合し、最後に入力データ長を符号化した８オクテットデータを結合する処理が行われる。この処理をパディングという。
【０００４】
各ブロックに対する要素ハッシュ演算は以下のように演算される。即ち、入力された６４オクテットのブロックをそのまま４オクテット単位に分割してワードＷ０〜Ｗ１５とする。更にこれらＷ０〜Ｗ１５からＷｔ＝（Ｗｔ−16（＋）Ｗｔ−14（＋）Ｗｔ−８（＋）Ｗｔ−３）<<<１，…，ｔ＝１６，…，７６，Ｗ<<<１はＷを１ビット左巡環シフトすることを表わし、Ａ（＋）ＢはＡとＢのビット単位の排他的論理和を表わす。これら求めたワードＷ０〜Ｗ７９を、ダイジェストと同じ長さの中間バッファの内容に、順に混ぜ込みながら同様な演算を８０ステップ行う。中間バッファの初期値は、最初のブロックの要素ハッシュ演算の場合には、イニシャルベクタと呼ばれる予め定められた一定値であり、２番目以降のブロックの要素ハッシュ演算の場合には、前のブロックの要素ハッシュ演算の出力とする。前記中間バッファの内容に対する混ぜ込み演算は周知であるから説明を省略する（例えば……を参照）。全てのワードについて混ぜ込み演算を行った後、最終処理として、中間バッファの初期値を再度加算し、そのときのバッファ値を要素ハッシュ演算の出力とする。
【０００５】
なお、ＳＨＡ−２５６，ＳＨＡ−３８４，ＳＨＡ−５１２などの他のＳＨＡ系アルゴリズムにおいては、上述したＳＨＡ−１アルゴリズムにおける混ぜ込み演算式や、ブロックやワードやダイジェストの長さが異なるだけで、演算の構造はほとんど同じである。
ここで、前述した通り、マスク生成関数演算処理は、ハッシュ演算の連結であるため、その演算処理量は、所望する出力オクテット長ＴＬｅｎにほぼ比例して大きくなる。また、一般的なハッシュ関数の演算処理は逐次的であるため、その演算処理量は入力オクテット長にほぼ比例する。よって、乱数の種と所望する出力オクテット長が増大すると、それに応じて演算処理量が増大する。
【０００６】
なお、特許文献１において、マスク生成関数演算処理と同様の演算を、入力された乱数部と結合する符号化部をそれぞれ別に演算することで、高速に演算する方法が示されている。つまり乱数の種Ｃを分割し、その各分割データごとに順次ハッシュ関数演算を行い、その演算結果と、各Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ）（符号化部）とについてハッシュ関数演算を行い、その演算結果を連結して出力する。
【特許文献１】特開２００２−３０４１２１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
前記特許文献１に示す方法は、演算の内部処理がハッシュ関数の入力ブロックサイズ単位でしか処理できないため効率が悪いという問題があった。また、符号化部を含むデータは必ず繰り返し演算するため、実際には値が変わらない場合でも繰り返し演算するため、効率が悪いという問題があった。
この発明の目的は、値が変わらない繰り返し演算を行うことなく、入力である乱数の種のオクテット長と、所望する出力のオクテット長が大きいときに、演算処理量が増大するという課題を解決するマスク生成関数演算装置、そのプログラム及びその記録媒体を提供することにある。
【課題を解決するための手段】
【０００８】
この発明によるマスク生成関数演算装置においては、演算に先立ち、入力データから共通に行われる共通演算部分を判定し、その共通演算部分の演算結果を保存し、その共通演算部の演算結果を、非共通演算部分の演算に利用する。即ち、入力データと所望する出力長とが入力され、これらとハッシュアルゴリズムに基づくパラメータとからマスク生成関数演算の繰り返し内容が計算され、繰り返し演算の中途で入出力が同一となる共通演算部分が入力データ及び上記パラメータから計算され、共通演算部分について演算された演算中間値が記憶部に保存され、その記憶部に保存した共通演算部分の演算結果も、非共通演算部分の演算の入力として演算が行われる。
【発明の効果】
【０００９】
この発明によれば、演算の中途で入出力が同一となる共通演算部分が計算され、共通演算部分の演算結果をそれ以外の演算に適宜使用するため、少ない計算量で高速に演算が可能となる。
【発明を実施するための最良の形態】
【００１０】
（第１の実施形態）
以下、図面を参照してこの発明装置の第１の実施の形態を説明する。その機能構成の主要部を示し、この装置は、乱数の種（入力データ）Ｃと、所望の出力オクテット長ＴＬｅｎが入力され乱数Ｔ（Ｃ）を出力する。
このマスク生成関数演算装置は、各部の動作を適切に制御することで、マスク生成関数演算装置の動作を制御する制御部１０と、入力から演算内容および演算動作内容を判定する判定部２０と、ブロック（要素）ＳＨＡ−１演算の途中の中間バッファ値、ステップ数、および演算結果であるダイジェストを出力できる要素ＳＨＡ−１演算部３０と、要素ＳＨＡ−１演算部３０の出力であるダイジェストを記憶するダイジェスト記憶部４０と、要素ＳＨＡ−１演算部３０の出力である中間バッファ値およびステップ数を記憶するバッファ記憶部５０と、ブロック（要素）ＳＨＡ−１演算を繰り返し行って得られるマスク値を記憶しておく出力記憶部６０を有する。この装置の処理手順の例を図２に示す。１８９オクテットの乱数の種Ｃと、所望の出力オクテット長ＴＬｅｎ＝６４００オクテットが入力したときを例として処理内容を説明する。
【００１１】
本実施例におけるマスク生成関数演算装置に、入力として乱数の種Ｃと、所望の出力オクテット長ＴＬｅｎ＝６４００が入力される（ステップＳ１）。
次に、判定部２０において演算内容の判定を行う（ステップＳ２）。異なる符号化部（ＣＩ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，Ｎ−１）のＳＨＡ−１演算の回数ＮはＮ＝［ＴＬｅｎ／ＤＬｅｎ］を計算することで得られ、この数値例ではＮ＝［６４００／２０］＝３２０回と判定される。Ｎを符号化部数という。また、各ｎ（ｎ＝０，…，Ｎ−１）の値に対するブロック（要素）ＳＨＡ−１演算の回数ＭはＭ＝［（ＣＬｅｎ＋４＋１＋８）／ＢＬｅｎ］を計算することで得られる。ここでＳＨＡ−１演算に対する入力メッセージはＣ‖Ｉ２ＯＳＰ（ｎ，４）であり、分子はＳＨＡ−１演算処理に使用されるデータのオクテット数で、ＣＬｅｎは乱数の種Ｃのオクテット長であり、４はＩ２ＯＳＰ（ｎ，４）のオクテット長であり、１はメッセージがブロック長ＢＬｅｎ整数後でも必ず１ビットの“１”が付加されるから１オクテット分は長くなるからであり、８はメッセージの長さを表わす８オクテット長である。分母のＢＬｅｎはＳＨＡ−１の入力ブロックのオクテット長を表している。この数値例ではＣＬｅｎは１８９オクテットであるからｍはｍ＝［（１８９＋４＋１＋８）／６４］＝４と判定される。
【００１２】
以上により、この数値では図３に示すような演算を行うと判定部２０により判定されることになる。１８９オクテット長の乱数の種Ｃと各符号化部（Ｉ２ＯＳＰ（ｎ，４）（ｎ＝０，１，…，３１９）との結合およびパディングとメッセージ長に対するブロック（要素）ＳＨＡ−１演算は４回の繰返演算Ｃｎ，ｍ（ｍ＝０，１，…，３）を行うことになる。その結果、各２０オクテット長の演算結果ｈ（ｎ）が得られる。なおＳＨＡ−１演算の数Ｎ、つまり異なる符号化部との組み合せＳＨＡ−１演算回数（符号化部数という）Ｎと各ＳＨＡ−１演算におけるブロック（要素）ＳＨＡ−１演算の繰り返し回数（繰返回数という）Ｍは、判定部２０内の演算内容計算部２１に、ＴＬｅｎ，ＣＬｅｎ（乱数の種Ｃより得られる）と、パラメータレジスタ２４よりのＤＬｅｎ，ＢＬｅｎが入力されて演算される。
【００１３】
次に、ステップＳ２で判定したＮを用いて、判定部２０の内部に有するｎカウンタをＮ−１である３１９に初期化する（ステップＳ３）。その後、ｎカウンタをカウント値ｎが３１９から０になるまで減算しながら、ブロック（要素）ＳＨＡ−１演算を繰り返して演算を進める（ステップＳ４〜Ｓ８）。
ここで、ｎを降順に演算する理由について説明する。即ち、乱数の種Ｃはｎによらずすべて一定値であるため、入力データＣ‖Ｉ２ＯＳＰ（ｎ，４）の先頭からＣＬｅｎオクテットは全てのｎに対して同じデータ値である。また、Ｉ２ＯＳＰ（ｎ，４）は、オクテット長４であり、かつ整数ｎを符号化したものを表わすため、先頭から（４−［（ｎ＋１）ｍｏｄ２５６］）オクテットは、全ビット“０”である。Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテット長は、ｎが大きくなるほど短くなる。よって、あるｎのＳＨＡ−１演算の入力データのうち、Ｃと、Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテットまでの入力データ（メッセージ）は、ｎ−１におけるＳＨＡ−１演算の入力データＣ‖Ｉ２ＯＳＰ（ｎ−１，４）でも同一となる。よってＳＨＡ−１演算を逐次処理する際にはｎの最大値Ｎ−１から降順に演算しながら、前の演算の中間値を利用することが効率的である。よってこの実施形態ではｎ＝３１９から降順に演算を行う。
【００１４】
次に、初回（ｎ＝３１９）におけるブロック（要素）ＳＨＡ−１演算について説明する。
はじめに、演算のどの時点での中間値を次回（ｎ＝３１８）のＳＨＡ−１演算で利用できるかを判定部２０内の保存位置計算部２０ｃで判定する（ステップＳ４）。判定される中間値はブロック（要素）ＳＨＡ−１演算のダイジェスト出力か、ブロック（要素）ＳＨＡ−１演算のブロックＷ０〜Ｗ１５のいずれかまでの演算の中間値である。これは、ＳＨＡ−１演算の場合、Ｗ０〜Ｗ１５については、６４オクテットの入力を先頭から順番に４オクテット単位で割り付けたものである。したがって、イニシャルベクタもしくは前ブロックの要素ＳＨＡ−１演算の結果が等しく、入力ブロックの内容が途中から異なる場合には、４オクテット単位で割り付けたＷ０〜Ｗ１５のうち、先頭からのデータが等しくなるところまでの演算内容は同じであり、そこまで演算したときの中間バッファ値は同じとなる。つまり、中間バッファの初期値と、共通演算部分だけ混ぜ込んだバッファを記憶しておき、それらを入力として異なる入力ブロックの割付部分から演算を行うことで、ＳＨＡ−１演算を中途から演算できる。
【００１５】
初回（ｎ＝３１９）のＳＨＡ−１演算の入力データのうち、次回（ｎ＝３１８）の演算の入力データでも同一になるオクテット長ＺＬｅｎはＺＬｅｎ＝ＣＬｅｎ＋４−［ｎ ｍｏｄ２５６］で計算される。ここで、第２項以降は、Ｉ２ＯＳＰ（ｎ，４）の先頭部分にある全ビット“０”となるオクテット長の計算である。数値例では同一データ長ＺＬｅｎ＝１８９＋４−［３１９ｍｏｄ２５６］＝１９１となる。この同一データ長ＺＬｅｎから、演算のどの時点での中間値を次回（ｎ＝３１８）のＳＨＡ−１演算で利用できるかを判定する。これは同一データ長ＺＬｅｎをブロック長ＢＬｅｎで割ったときの商Ｒと余りＳから判定する。ＺＬｅｎをＢＬｅｎで割ると、数値例では商Ｒが２で余りＳが６３となる。次回（ｎ＝３１８）の演算では、２回の繰り返しブロック（要素）ＳＨＡ−１演算と、そのあとの６３オクテット分のブロック（要素）ＳＨＡ−１演算入力までは、今回のブロック（要素）ＳＨＡ−１演算と同一の入力データとなる。なお６３オクテット分が何個分のワードに相当するかは、余りＳをワード長をＷＬｅｎで割った商から１を減算し値Ｕ＝［Ｓ／ＷＬｅｎ］−１で計算され、この数値例の場合は［６３／４］−１＝１５ワード分に相当する。以上より、初回（ｎ＝３１９）の演算において、２回の繰り返しブロック（要素）ＳＨＡ−１演算の後、１５ワード分の演算を行った時点における演算結果を中間値バッファに保存することを判定できる。
【００１６】
次に、ＳＨＡ−１演算を行う入力データを生成する（ステップＳ５）。初回（ｎ＝３１９）の入力データはＣ‖Ｉ２ＯＳＰ（３１９，４）である。
次に、ステップＳ５で生成されたデータに対して、要素ＳＨＡ−１演算部３０で繰り返し演算を行う（ステップＳ６）。ここで、ステップＳ４での判定に従い、２回の繰り返しブロック（要素）ＳＨＡ−１演算の後のダイジェスト出力Ｄをダイジェスト記憶部４０に、その後１５ワード分の演算を行った時点における演算中間値ｂをバッファ記憶部５０に記憶する。その後ｎ＝３１９に対するＳＨＡ−１演算における残りの全ての演算を行う。
【００１７】
次に、ステップＳ６で演算したＳＨＡ−１演算結果ｈ（３１９）を、出力記憶部６０に保存し、初回（ｎ＝３１９）の演算を終了する（ステップＳ７）。
次にステップＳ８でｎ＝０か否かの判定を行い、その判定結果が０でなければステップＳ８ａでｎを−１してステップＳ４に戻る。
以下に２回目（ｎ＝３１８）以降の演算ＳＨＡ−１を説明する。
２回目（ｎ＝３１８）の演算ＳＨＡ−１演算の前に、初回（ｎ＝３１９）の演算と同様に、次回（ｎ＝３１７）の演算で利用できる中間値の判定を行う（ステップＳ４）。その判定の結果、２回の繰り返しブロック（要素）ＳＨＡ−１演算のダイジェスト出力と、その後１５ワード分のブロック（要素）ＳＨＡ−１演算を行った時点におけるバッファ値の両方を保存すると判定されるが、これは初回（ｎ＝３１９）における判定結果と同じであるため、保存すべきダイジェスト出力Ｄおよび演算中間値は初回保存されたものと同一である。よって、ダイジェスト出力Ｄおよび演算中間値ｂの保存（更新）を省略することができる。
【００１８】
２回目（ｎ＝３１８）の入力データの生成では、Ｃ‖Ｉ２ＯＳＰ（３１８，４）から先頭の２ブロックＣ３１８，０、Ｃ３１８，１を除いたデータを生成する（ステップＳ５）。これは、次ステップで、要素ＳＨＡ−１演算部に、初回（ｎ＝３１９）に保存したダイジェスト出力Ｄおよび演算中間値ｂを入力することで、途中から演算を開始することで、先頭の２ブロック分の演算を代用するためである。
次に、ステップＳ５で生成されたデータと、ダイジェスト出力Ｄおよび演算中間値ｂを用いて、要素ＳＨＡ−１演算部で繰り返し演算を途中から行う（ステップＳ６）。なお、ステップ４で、ダイジェスト出力Ｄおよび演算中間値ｂの保存（更新）が省略可能であると判定されたため、中間結果の保存は行わない。ＳＨＡ−１演算結果ｈ（３１８）を、出力記憶部６０に保存して、２回目（ｎ＝３１８）の演算を終了する。
【００１９】
このようにして、前回の演算で判定保存されたダイジェスト出力Ｄおよび演算中間値ｂの保存を利用して、ＳＨＡ−１演算を途中から行いながら、次回の演算で利用できるダイジェスト出力Ｄおよび演算中間値ｂを更新し、最終結果ｈ（ｎ）を蓄積保存していく。
なお、このように演算を進めていくと、ｎ＝２５６の演算におけるダイジェストＤおよび演算中間値ｂの判定では、ＺＬｅｎ＝１８９−４［２５６ｍｏｄ２５６］＝１９２をＢＬｅｎ＝６４で割ると、商が３で余りが０となる。よって、ｎ＝２５６における３回の繰り返しブロック（要素）ＳＨＡ−１演算のダイジェスト出力Ｄを保存しておき、次回のＳＨＡ−１演算でこれを入力とすることで、３回の繰り返し演算を省略することができる。このように、余りの０になるなど、０ワード目に相当する余りの場合、その次回のＳＨＡ−１演算では演算中間値ｂは使用されないため、演算中間値ｂの保存は省略される。
【００２０】
このような演算を全てのｎに対して行った後、出力記憶部６０に保存されているｈ（０）からｈ（３１９）をｈ（０）‖ｈ（１）‖…‖ｈ（３１９）のように連結し（ステップＳ９）、これをその先頭からＴＬｅｎの長さだけ出力とする。
図２中のステップＳ２における演算内容Ｎ，Ｍの計算は判定部２０における演算内容計算部２１で行われる。図４中に示すように演算内容計算部２１内の符号化数計算部２１ａにＴＬｅｎとＤＬｅｎが入力されＮ＝［ＴＬｅｎ／ＤＬｅｎ］が計算される。また演算内容計算部２１内の繰返回数計算部２１ｂにＣ，ＢＬｅｎが入力されＭ＝［（ＣＬｅｎ＋４＋１＋８）／ＢＬｅｎ］が計算される。図２中のステップＳ３での初期化は判定部２０内のｎカウンタ（演算要素カウンタ）２１ｃに計数値ｎとしてＮ−１を設定することにより行われる。ｎカウンタ２１ｃは１回のＳＨＡ−１演算が終了するごとに制御部１０からの指示により１減算される。また判定部２０内のパラメータレジスタ２５にＳＨＡ−１演算出力長ＤＬｅｎ、ブロック長ＢＬｅｎ、ワード長ＷＬｅｎ、乱数の種長ＣＬｅｎなどが格納されている。ＣＬｅｎは前処理として予め求められているものとする。
【００２１】
上述した保存位置Ｒ，Ｓ，Ｕの計算、ダイジェストＤ、演算中間値ｂの保存、再利用処理などのための機能構成例および処理手順の例を図４および図５を参照して説明する。
ステップＳ１１でバッファ記憶部５０内の中間値バッファ（以下Ｂバッファという）５０ａの内容ＢをＳＨＡ−１で規定されるイニシャルベクタ値ＩＶに初期化し、ダイジェスト記憶部４０内のダイジェストバッファ（以下Ｄバッファという）の内容Ｄ，ＳＨＡ−１演算の中間値（２０オクテット）ｂ、ＳＨＡ−１演算の入力値で最終処理に使用する初期データｄをそれぞれ０に初期化し、判定部２０内のｍカウンタ２１ｄの計数値ｍを０に、要素ＳＨＡ−１演算部３０内の演算ステップ数０〜７９を計数するｗカウンタ３０ａの計数値ｗを０に初期化する。
【００２２】
ステップＳ１２で入力データにおいて、次のＳＨＡ−１演算においても同一となる同一長ＺＬｅｎ＝ＣＬｅｎ＋４−［ｎ ｍｏｄ２５６］の計算が行われる。この計算は判定部２０における保存位置計算部２２内の同一長計算部２２ａにＣとｎが入力されて行われる。その後、ステップＳ１３で位置計算部２２ｂでＺＬｅｎとＢＬｅｎが入力されてその商Ｒと余りＳとが計算され、更にステップ計算部２２ｃでＵ＝［Ｓ／ＷＬｅｎ］−１が計算される。これらが図２中のステップＳ４と対応する。商Ｒは共通演算部分のブロック数であるから位置計算部２２ｂは共通ブロック数計算部ともいえる。
【００２３】
ステップＳ１４で演算開始時の各種データ、つまりＢバッファ５０ａの内容がＳＨＡ−１演算の中間値ｂとして、Ｄバッファ４０ａの内容がブロック（要素）ＳＨＡ−１演算の入力値で最終処理に使用するデータｄとして、またｍバッファ４０ｂの内容ｍ、ｗバッファ５０ｂの内容ｗがそれぞれ取り出される。
ステップＳ１５でｎカウンタ２１ｃ及びｍカウンタ２１ｄの各カウント値ｎ，ｍからブロック（要素）ＳＨＡ−１演算に対する入力データＣｎ，ｍが、判定部２０におけるデータ生成部２３内のｎ，ｍブロック生成部２３ａで生成される。ステップＳ１６でその入力データＣｎ，ｍに対する演算はそのブロック（入力データ）の先頭、つまりｗ＝０回目から開始するか否かが、判定部２０内の先頭判定部２４ａにより判定される。
【００２４】
ｗ＝０と判定されるとステップＳ１７で演算中間値ｂ（最初（Ｎ−１，０）では０）が最終処理用入力値ｄとしてステップＳ１８に移り、第ｎ，ｍブロック（要素）のデータＣｎ，ｍのステップｗのブロック（要素）ＳＨＡ−１演算が要素ＳＨＡ−１演算部３０で行われる。ステップＳ１６でｗ＝０でないと判定されると直ちにステップＳ１８での演算が行われる。
次にステップＳ１９は演算中間値を保存すべき位置、つまりｍ＝Ｒかつｗ＝Ｕであるか否かの判定を中間値保存判定部２４ｂで行う。この判定保存位置でなければ、ステップＳ２０はブロックＳＨＡ−１演算が終了したか、つまりｗ＝７９か否かの判定をブロック演算終了判定部２４ｃで行い、ｗ＝７９ではなく、つまり終了でなければステップＳ２１でステップ数ｗを＋１して、ステップＳ１８に戻る。
【００２５】
ステップＳ１９の判定が保存位置であれば、ステップＳ２２でステップＳ１８で得られたＳＨＡ−１演算の中間値ｂをＢバッファ５０ａに格納保存すると共に、その時のステップ数ｗをｗバッファ５０ｂに格納保存してステップＳ２０へ移る。
ステップＳ２０でそのブロック（要素）ＳＨＡ−１演算が終了と判定すると、ステップＳ２３はブロック（要素）ＳＨＡ−１演算の最終処理、つまり、ＳＨＡ−１演算の最終（ステップｗ＝７９）の演算結果ｂとその要素ＳＨＡ−１演算の初期入力値ｄを要素ＳＨＡ−１演算部３０内の加算部３０ｂで加算し、その加算結果を演算中間値ｂとする。
【００２６】
次にステップＳ２４はダイジェスト保存位置か否か、つまりｍ＝Ｒ−１か否かの判定をダイジェスト保存判定部２４ｂで行う。この判定が保存位置でなければステップＳ２５はそのｎにおけるＳＨＡ−１演算が終了したか、つまりｍ＝Ｍ−１となったか否かの判定を要素演算終了判定部２４ｅで行う。ステップＳ２４でダイジェスト保存位置である、つまり共通演算部分におけるブロック単位の演算が終了したと判定されると、ステップＳ２６はＢバッファ５０ａにステップＳ２３で求めた演算中間値ｂを、またその時のステップ数ｗをｗバッファ５０ｂにそれぞれ格納保存してステップＳ２５に移る。
【００２７】
ダイジェスト保存判定部２４ｄは（共通演算部分のブロック単位演算）終了判定部ともいえる。
ステップＳ２５の判定がそのｎにおけるＳＨＡ−１の演算が終了していなければ、ステップＳ２７はｍカウンタ２１ｄを＋１し、かつｗカウンタ３０ａを０にリセットしてステップＳ１５に戻る。ステップＳ２５の判定が終了していればステップＳ２８はその時のステップＳ２３の最終処理結果（演算中間値）ｂをその第ｎＳＨＡ−１演算結果ｈ（ｎ）として出力記憶部６０に格納保存する。次のステップＳ２９は全ての演算が終了したか、つまりｎ＝０であるか否かを最終判定部２４ｆで判定し、その判定が終了でなければステップＳ３０でｎカウンタ２１ｃを１減算してステップＳ１２に戻る。ステップＳ２８，Ｓ２９，Ｓ３０は図２中のステップＳ７，Ｓ８，Ｓ８ａとそれぞれ対応する。ステップＳ２９の判定が終了であれば、その後の処理は図２に示した処理と同様である。
【００２８】
上述した処理において、各種パラメータの取り出し、各種判定結果に基づく、カウンタの歩進制御、各種データの保存処理、次の処理へ歩進、各部に対する動作指令などは制御部１０が行う。なおステップＳ１１の初期化処理は、図２中のステップＳ３の初期化処理で行ってもよい。ステップＳ１８〜Ｓ２７が図２中のステップＳ６と対応する。上述から理解されるように保存位置計算部２２で計算されたＲ，Ｓ，Ｔに基づいて、その時の演算中間値ｂを保存し、次のｎのＳＨＡ−１演算の前回と同一データでない部分の入力データ、つまりデータ生成部２３ａで生成されたデータであり、そのＳＨＡ−１演算としては途中からの演算となるが、それまでの演算結果として、前記保存した中間値ｂが再利用される。この点で保存位置計算部２２は共通演算計算部ともいえ、また前記途中からの演算は非共通部分の演算であり、データ生成部２３ａは非共通演算データ生成部といえる。
【００２９】
以上のように演算したときの、演算対象データを図６に示す。図中実線部分がＳＨＡ−１演算に利用されたデータを示し、破線部分は中間値ｂおよびダイジェストｄを利用することで省略されたデータを示す。最初のｎ＝Ｎ−１のＳＨＡ−１演算はすべてのブロックＣ３１９，０、Ｃ３１９，１、Ｃ３１９，２、Ｃ３１９，３に対し行われ、つまりすべてが非共通演算部分であるが、ｎ＝Ｎ−２のＳＨＡ−１演算は前記商Ｒと対応する最初の２つのブロックＣ３１８，０とＣ３１８，１はＣ３１９，０とＣ３１９，１と同一入力データとなり、またブロックＣ３１８，２中の最初の前記余りＳのワード数Ｕと対応する１５ワードはＣ３１９，２の対応ワードの入力データと同一であるから、これら同一データに対する演算中間値ｄ，ｂと、前回と異なる入力データ（非共通演算部分）Ｃ３１８，２の残りのワードデータ及びＣ３１８，３とが入力されて演算されることになる。ｎ＝２５５になるとその入力データは、その前のｎ＝２５６に対する入力データと最初から３つのブロックが同一となるため、非共通演算部分はＣ２５６，３のみとなり、これと前回演算中間値ｄ，ｂが演算に利用されることになる。
【００３０】
このように、入力である乱数の種のオクテット長と、所望する出力のオクテット長が大きいときにも、演算に先立ち、入力データから共通に行われる共通演算部分を判定し、その共通演算部分を繰り返し演算しないよう適切に演算を行うことで、演算処理量を削減することができる。
なお、この実施例では、すべてのｎに対するＳＨＡ−１演算結果ｈ（ｎ）を保存しておき、全ての演算が終了したときに、それらを連結して出力したが、各ｎにおけるＳＨＡ−１演算が終了次第、それらを順次出力しても良い。また、演算の効率を鑑みるとｎが大きいほうから降順でＳＨＡ−１演算するのが好適であるが、ｎを小さいほうから昇順で演算しても良い。
（第２の実施形態）
第２の実施形態はＩＳＯ／ＩＥＣ１８０３３−２で規定されているＰＳＥＣ−ＫＥＭの暗復号化システムにおいてそのマスク生成関数演算にこの発明によるマスク生成関数演算装置を適用したものである。以下では体が１６３ビットのＰＳＥＣ−ＫＥＭの暗号演算手順における、マスク生成関数演算装置の動作について説明する。
【００３１】
ＰＳＥＣ−ＫＥＭの暗号化演算での過程で、ＫＤＦ（Ｉ０‖Ｃ，［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ）の演算を行う。ここで、Ｉ０はＩ２ＯＳＰ（０，４）であり、μおよびＫｅｙＬｅｎはＰＳＥＣ−ＫＥＭで使用するパラメータである。また、ＫＤＦ（Ｘ，Ｐ）は、ＫＤＦ（Ｘ，Ｐ）＝Ｈ（Ｘ‖Ｉ２ＯＳＰ（０，４））‖Ｈ（Ｘ‖Ｉ２ＯＳＰ（１，４））…‖Ｈ（Ｘ‖Ｉ２ＯＳＰ（Ｎ−１，４））の演算を表している。ただしＨ（Ｘ）はＸのハッシュ演算を表しＰ＝［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ＝ＴＬｅｎ、Ｎ＝［ＴＬｅｎ／ＤＬｅｎ］，ＴＬｅｎは出力オクテット長、ＤＬｅｎはハッシュ関数演算結果長をそれぞれ表わしている。この演算をこの発明によるマスク生成関数演算装置によって行う。この暗号化演算装置の機能構成例を図７に示す。ＰＳＥＣ−ＫＥＭ演算部１００から乱数の種Ｃ（ｓｅｅｄ）、出力オクテット長ＴＬｅｎおよび使用ハッシュ関数を表わす関数符号ＨＡがこの発明によるマスク生成関数演算装置２００に入力され、マスク生成関数演算装置２００から、生成乱数Ｔ（ｓｅｅｄ）がＰＳＥＣ−ＫＥＭ演算部１００に入力される。
【００３２】
この実施例では、［Ｌｏｇ２５６μ］＝２１オクテット、ＫｅｙＬｅｎ＝６４オクテット、Ｃは１２８オクテットの乱数の種ｓｅｅｄを使用する。したがって、マスク生成関数演算装置２００の２つの入力である乱数の種Ｃと所望の出力長ＴＬｅｎは、それぞれ、１３２オクテットのＩ０‖ｓｅｅｄと、１０１オクテット（２１＋１６＋６４）であり、その出力は、ＫＤＦ（Ｉ０‖ｓｅｅｄ，［Ｌｏｇ２５６μ］＋１６＋ＫｅｙＬｅｎ）の演算結果である。
マスク生成関数演算装置２００の機能構成例は図７に示すように、制御部２１０と、判定部２２０と、複数の要素ハッシュ関数演算部としての要素ＳＨＡ−１演算部２３０、要素ＳＨＡ−２５６演算部２４０、要素ＳＨＡ−３８４演算部２５０、要素ＳＨＡ−５１２演算部２６０と、中間データ記憶部２７０と、出力記憶部２８０とを備える。
【００３３】
この第２の実施形態におけるマスク生成関数演算装置２００による処理を、図８に示すフローチャートを基に説明する。また判定部２２０の具体的機能構成例を図９に示す。
ＰＳＥＣ−ＫＥＭ演算部１００において生成されたｓｅｅｄ（Ｃ）、所望の出力長ＴＬｅｎ、例えば１０１オクテット、および、ＫＤＦに使用するハッシュ演算アルゴリズムを表わす関数符号ＨＡ、例えば０が、マスク生成関数演算装置２００に入力される（ステップＳ１）。
次に、判定部２２０において演算内容の計算を演算内容計算部２２１で行う（ステップＳ２）。
【００３４】
演算で使用するＫＤＦのアルゴリズムは、ステップＳ１で入力されたＨＡから、判定部２２０に設定したアルゴリズムテーブル２２２を参照することで判定する。例えばＨＡ＝０であって、ＫＤＦのアルゴリズムはＳＨＡ−１を選択する。
ＳＨＡ−１演算の繰り返し回数、つまり符号化部数ＮはＮ＝［ＴＬｅｎ／ＤＬｅｎ］を符号化部数計算部２２１ａで計算することで得られ、この数値例ではＮ＝［１０１／２０］＝６回と計算される。また、各ｎ（ｎ＝０，１，…，Ｎ−１）の値に対するブロック（要素）ＳＨＡ−１演算の回数ＭはＭ＝［（ＣＬｅｎ＋４＋８）／ＢＬｅｎ］を繰返回数計算部２２１ｂで計算することで得られる。この数値例ではＭ＝［（１２８＋４＋１＋８）／６４］＝３回と計算される。
【００３５】
以上によりこのマスク生成関数演算は図１０に示すようにＩ０‖ＣとＩ２ＯＳＰ（０，４）及びパディング〜Ｉ０‖ＣとＩ２ＯＳＰ（５，４）及びパディングの６回のＳＨＡ−１演算を行い、各ＳＨＡ−１演算では３回のブロック（要素）ＳＨＡ−１演算を繰り返し行うことになる。
次に、判定部２２０において、共通演算部分の共通演算部分および個別演算部分の判定を行う（ステップＳ３）。共通演算部分は、全てのｎに対して、先頭から同一となるブロック数ｋを判定することで行う。共通演算数計算部２２３にＣ，Ｎ、ブロック長ＢＬｅｎが入力されてｋ＝［（ＣＬｅｎ＋４−［ｌｏｇ２５６（Ｎ＋１）］）／ＢＬｅｎ］−１が計算される。この数値例ではｋ＝［（１２８＋４−［ｌｏｇ２５６（６＋１）］）／６４］−１＝２と演算される。つまり、全てのｎに対して共通演算部分は先頭から２ブロック（１２８オクテット）であり、３ブロック目は個別演算部分であると判定される。以降は、この判定結果に従って制御部２１０の制御によって演算を進めていく。
【００３６】
次に、共通演算部分のＳＨＡ−１演算を行う。共通演算部分である、Ｉ０‖ｓｅｅｄの先頭２ブロックに対して、ＳＨＡ−１演算を行う。まずステップＳ４でｎカウンタ２２１ｃ、ｍカウンタ２２１ｄの各計数値ｎ，ｍをそれぞれ０に初期化し、ステップＳ５で入力データ生成部２２４ａにて、ｍが入力されてデータ（Ｉ０‖Ｃ，Ｉ２ＯＳＰ（ｎ，４）に対する第０ブロック目のデータＣ０，０が生成され、ステップＳ６でそのデータＣ０，０に対し要素ＳＨＡ−１演算部２３０によるＳＨＡ−１演算を行い、ステップＳ７でその演算結果であるダイジェストＤを中間データ記憶部２７０に保存する。
【００３７】
ステップＳ８で共通演算部分のブロックでないか、つまりｍ＝ｋ−１であるか否かを共通部判定部２２５で判定し、その判定が否であればステップＳ９でｍカウンタ２２１ｄを１歩進してステップＳ５に移る。これらステップＳ４〜Ｓ９の処理は共通演算部分の第０回目（ｎ＝０）における入力データを（Ｉ０‖Ｃ）とイニシャルベクタ又は記憶部２７０中のダイジェストＤを入力とするＳＨＡ−１演算である。機能構成的にはこの演算が共通部計算部を構成することになる。
ステップＳ８での判定がｍ＝ｋ−１、この例ではｍ＝１つまり共通演算部分に対する計算の終了であればステップＳ１０でｍカウンタ２２１ｄを１歩進し、ステップＳ１１で第ｎ回目のＳＨＡ−１演算ＳＨＡ−１のデータ（Ｉ０‖Ｃ，Ｉ２ＯＳＰ（Ｎ−１，４）における第ｍ回目のブロックデータＣ０，ｍ、この例ではＣ０，２がデータ生成部２２４ｂで生成される。なおこの時共通部判定部２２５の判定出力が否定であってデータ生成部２２４ａではなくデータ生成部２２４ｂが動作するステップＳ１２ではステップＳ７で保存したダイジェストＤに対してこのデータＣ０，２を用いて要素ＳＨＡ−１演算部２３０でＳＨＡ−１演算を行い、ステップＳ１３ではｍカウンタ２２１ｄの計数値ｍが繰返回数と等しいか、つまりｍ＝Ｍ−１か否かを繰返終了判定部２２６で判定する。この判定結果が終了でなければステップＳ１４でその演算結果であるダイジェストＤを中間データ記憶部２７０に保存してステップＳ１０に戻る。ステップＳ１３の判定が終了であればステップＳ１５でステップＳ１２の演算結果ｈ（ｎ）を出力記憶部２８０に保存し、ステップＳ１６ではｎカウンタ２２１ｃの計数値ｎがｎ＝Ｎ−１か、つまりＳＨＡ−１の演算が終了したか否かの判定が最終判定部２２７で行う。この判定が終了でなければステップＳ１７ではｎカウンタ２２１ｃを１歩進させ、更にステップＳ１８ではｍカウンタ２２１ｄをｋ−１に初期化してステップＳ１０に戻る。この数値例ではｋ＝２，Ｍ＝３であるから、ステップＳ１３，Ｓ１４，Ｓ１８を省略し、破線で示すようにステップＳ１２より直ちにステップＳ１５に移り、ステップＳ１７よりステップＳ１１に直ちに移ることになる。なおこの第２の実施形態の説明を簡略にするため中間データ記憶部２７０に保存したデータと、これより取り出して要素ＳＨＡ−1演算部２３０で使用するデータとして同一表記とした。
【００３８】
これらステップＳ１０〜Ｓ１７は非共通部の演算であり、機能構成的には個別計算部を構成することになる。
ステップＳ１６での判定が終了であれば、ステップＳ１９では出力記憶部に保存されているｈ（０）からｈ（５）をｈ（０）‖ｈ（１）‖…‖ｈ（５）のように連結し、その先頭からＴＬｅｎオクテット長だけＰＳＥＣ−ＫＥＭ演算部１００への出力とする。ＰＳＥＣ−ＫＥＭ演算部１００は、マスク生成関数演算装置２００の出力を基に、ＰＳＥＣ−ＫＥＭの暗号演算を行う。
【００３９】
制御部２１０は各部の初期化、判定部２２０の各判定結果に基づく次の処理をその機能構成部に行わせるが、各演算結果の記憶部に対する保存、取り出し、処理の進行などを行う。ｐカウンタ２２１ｃ、ｍカウンタ２２１ｄなどは制御部２１０に設けるなどの変形をしてもよい、このことは第１の実施形態でも同様である。
以上のように演算したときの、演算対象データを図１１に示す。図中実線部分がＳＨＡ−１演算に利用されたデータを示し、破線部分はダイジェストＤを利用することで省略されたデータを示す。つまり第１回目のＳＨＡ−１演算はその全ブロックデータＣ０，０、Ｃ０，１、Ｃ０，２に対し行い、第２回目以後は入力データが共通とならないブロックデータＣ１，２，…，Ｃ５，２に対してのみ行う。このように計算することによって、少ない計算量でマスク生成関数演算が実行でき、これによりＰＳＥＣ−ＫＥＭの演算時間の短縮が出来る。
【００４０】
上述した各マスク生成関数演算装置はコンピュータにより機能させることもできる。例えば図１及び図４に示した機能構成による図２及び図５に示した処理を行う装置としてコンピュータを機能させるためのプログラムを、ＣＤ−ＲＯＭ、磁気ディスク、半導体記憶装置などの記録媒体からコンピュータにインストールし、又は通信回線を介してダウンロードし、そのプログラムを実行させればよい。第２の実施形態についても同様にコンピュータにより機能させることもできる。
【図面の簡単な説明】
【００４１】
【図１】この発明における装置の一実施形態における機能ブロック図。
【図２】この発明における装置の一実施形態における処理手順の例を示す流れ図。
【図３】第１の実施形態のマスク生成関数演算における各処理段階の各データを示した図。
【図４】図１中の判定部２０内の具体的機能構成例を示すブロック図。
【図５】図２中のステップＳ６における処理を中心とした具体例を示す流れ図。
【図６】第１の実施形態における実際に演算される各ブロックデータを示す図。
【図７】この発明における装置の他の実施形態における機能ブロック図。
【図８】この発明における装置の他の実施形態における処理手順の例を示す流れ図。
【図９】図７中の判定部２２０内の具体的機能構成例を示すブロック図。
【図１０】第２の実施形態のマスク生成関数演算における各処理段階の各データを示す図。
【図１１】第２の実施形態における実際に演算されるブロックデータを示す図。
【特許請求の範囲】
【請求項１】
入力データと所望する出力長が入力され、入力データに符号化した数値（以下符号化部という）を結合させたもののハッシュ演算を、上記符号化部の上記数値を変更しながら繰り返し行い、それらを結合することで上記所望する出力長の乱数を生成するマスク生成関数演算装置において、
予め設定されたハッシュアルゴリズムに基づくハッシュ演算を行うハッシュ演算部と、
上記入力データ及び所望出力長とハッシュアルゴリズムにより決るパラメータとからマスク生成関数演算の繰り返し内容を計算する演算内容計算部と、
繰り返し演算の中途で入出力が同一となる共通演算部分を、上記入力データ及び上記パラメータから計算する共通演算数計算部と、
マスク生成関数演算の演算中間値を記憶する記憶部とを備え、
上記ハッシュ演算部は上記計算した繰り返し内容に基づき、上記記憶部に保存した共通演算部分の演算中間値を、上記共通部分でない演算の入力としての演算をも行う演算部であることを特徴とするマスク生成関数演算装置。
【請求項２】
請求項１の装置において、上記演算内容計算部は上記出力長と上記ハッシュ演算の演算結果長とからハッシュ演算数（符号化部数という）を計算する符号化部数計算部と、
上記入力データの長さと上記ハッシュ演算の単位であるブロック長とから各ブロックハッシュ演算の繰り返し演算回数を計算する繰返回数計算部とよりなり、
上記共通演算数計算部は少くとも上記入力データ長と上記符号化部長との和を上記ブロック長で割算して計算する計算部であることを特徴とするマスク生成関数演算装置。
【請求項３】
請求項２の装置において、上記ハッシュ演算部の演算が上記共通演算部分の最後のブロック単位の演算であるか否かを上記割算結果により判定し、最後のものであればその演算結果をダイジェストとして上記記憶部に記憶する終了判定部を備えることを特徴とするマスク生成関数演算装置。
【請求項４】
請求項３の装置において、
上記演算結果の余りを、上記ブロック演算の単位であるワード長で割算するステップ計算部を上記共通演算数計算部は含み、
上記ハッシュ演算部の演算が、上記共通演算部分の最後のワード単位の演算であるか否かを上記割算結果と上記ステップ計算部の計算結果とより判定し、最後のものであればその演算結果を演算中間値として上記記憶部に保存する中間値保存判定部を備えることを特徴とするマスク生成関数演算装置。
【請求項５】
請求項２の装置において、上記割算結果と、上記符号化部数と、上記繰返回数が入力され、上記符号化部数及び繰返回数の組みに対し、共通演算部分か否かを判定する共通部判定部と、
上記共通部判定部が共通演算部分であると判定すると、上記入力データ及び上記繰返回数の中の何回目かを示す数より共通演算部分のデータを生成して上記ハッシュ演算部に演算されるべき入力データとして入力する第１データ生成部と、
上記共通部判定部が共通演算部分でないと判定すると、上記入力データ、上記符号化部数の中の何回目かを示す数及び上記繰返回数の中の何回目かを示す数より非共通演算部分のデータを生成して上記ハッシュ演算部に演算されるべき入力データとして入力する第２データ生成部とを備えることを特徴とするマスク生成関数演算装置。
【請求項６】
請求項１〜４のいずれかの装置において、上記符号化部ごとのハッシュ演算の終了ごとに、上記繰り返し内容における上記符号化した数値の最大値から順次１減算される演算要素カウンタが設けられ、
上記演算要素カウンタの計数値に基づき、上記ハッシュ演算部の演算が上記符号化した数値が大きいものから降順に行われることを特徴とするマスク生成関数演算装置。
【請求項７】
請求項１〜５のいずれかの装置において、ハッシュ関数の種類を示す関数符号も入力され、上記ハッシュ演算部は複数種類のハッシュ演算を有し、
上記入力された関数符号に応じた種類のハッシュ演算を上記ハッシュ演算部に実行させる手段を備えることを特徴とするマスク生成関数演算装置。
【請求項８】
請求項１〜７のいずれかに記載したマスク生成関数演算装置としてコンピュータを機能させるためのマスク生成関数演算プログラム。
【請求項９】
請求項８に記載したマスク生成関数演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【請求項１】
入力データと所望する出力長が入力され、入力データに符号化した数値（以下符号化部という）を結合させたもののハッシュ演算を、上記符号化部の上記数値を変更しながら繰り返し行い、それらを結合することで上記所望する出力長の乱数を生成するマスク生成関数演算装置において、
予め設定されたハッシュアルゴリズムに基づくハッシュ演算を行うハッシュ演算部と、
上記入力データ及び所望出力長とハッシュアルゴリズムにより決るパラメータとからマスク生成関数演算の繰り返し内容を計算する演算内容計算部と、
繰り返し演算の中途で入出力が同一となる共通演算部分を、上記入力データ及び上記パラメータから計算する共通演算数計算部と、
マスク生成関数演算の演算中間値を記憶する記憶部とを備え、
上記ハッシュ演算部は上記計算した繰り返し内容に基づき、上記記憶部に保存した共通演算部分の演算中間値を、上記共通部分でない演算の入力としての演算をも行う演算部であることを特徴とするマスク生成関数演算装置。
【請求項２】
請求項１の装置において、上記演算内容計算部は上記出力長と上記ハッシュ演算の演算結果長とからハッシュ演算数（符号化部数という）を計算する符号化部数計算部と、
上記入力データの長さと上記ハッシュ演算の単位であるブロック長とから各ブロックハッシュ演算の繰り返し演算回数を計算する繰返回数計算部とよりなり、
上記共通演算数計算部は少くとも上記入力データ長と上記符号化部長との和を上記ブロック長で割算して計算する計算部であることを特徴とするマスク生成関数演算装置。
【請求項３】
請求項２の装置において、上記ハッシュ演算部の演算が上記共通演算部分の最後のブロック単位の演算であるか否かを上記割算結果により判定し、最後のものであればその演算結果をダイジェストとして上記記憶部に記憶する終了判定部を備えることを特徴とするマスク生成関数演算装置。
【請求項４】
請求項３の装置において、
上記演算結果の余りを、上記ブロック演算の単位であるワード長で割算するステップ計算部を上記共通演算数計算部は含み、
上記ハッシュ演算部の演算が、上記共通演算部分の最後のワード単位の演算であるか否かを上記割算結果と上記ステップ計算部の計算結果とより判定し、最後のものであればその演算結果を演算中間値として上記記憶部に保存する中間値保存判定部を備えることを特徴とするマスク生成関数演算装置。
【請求項５】
請求項２の装置において、上記割算結果と、上記符号化部数と、上記繰返回数が入力され、上記符号化部数及び繰返回数の組みに対し、共通演算部分か否かを判定する共通部判定部と、
上記共通部判定部が共通演算部分であると判定すると、上記入力データ及び上記繰返回数の中の何回目かを示す数より共通演算部分のデータを生成して上記ハッシュ演算部に演算されるべき入力データとして入力する第１データ生成部と、
上記共通部判定部が共通演算部分でないと判定すると、上記入力データ、上記符号化部数の中の何回目かを示す数及び上記繰返回数の中の何回目かを示す数より非共通演算部分のデータを生成して上記ハッシュ演算部に演算されるべき入力データとして入力する第２データ生成部とを備えることを特徴とするマスク生成関数演算装置。
【請求項６】
請求項１〜４のいずれかの装置において、上記符号化部ごとのハッシュ演算の終了ごとに、上記繰り返し内容における上記符号化した数値の最大値から順次１減算される演算要素カウンタが設けられ、
上記演算要素カウンタの計数値に基づき、上記ハッシュ演算部の演算が上記符号化した数値が大きいものから降順に行われることを特徴とするマスク生成関数演算装置。
【請求項７】
請求項１〜５のいずれかの装置において、ハッシュ関数の種類を示す関数符号も入力され、上記ハッシュ演算部は複数種類のハッシュ演算を有し、
上記入力された関数符号に応じた種類のハッシュ演算を上記ハッシュ演算部に実行させる手段を備えることを特徴とするマスク生成関数演算装置。
【請求項８】
請求項１〜７のいずれかに記載したマスク生成関数演算装置としてコンピュータを機能させるためのマスク生成関数演算プログラム。
【請求項９】
請求項８に記載したマスク生成関数演算プログラムを記録したコンピュータ読み取り可能な記録媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【公開番号】特開２００６−３３７４２９（Ｐ２００６−３３７４２９Ａ）
【公開日】平成１８年１２月１４日（２００６．１２．１４）
【国際特許分類】
【出願番号】特願２００５−１５８５４４（Ｐ２００５−１５８５４４）
【出願日】平成１７年５月３１日（２００５．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
【公開日】平成１８年１２月１４日（２００６．１２．１４）
【国際特許分類】
【出願日】平成１７年５月３１日（２００５．５．３１）
【出願人】（０００００４２２６）日本電信電話株式会社 (13,992)
【Ｆターム（参考）】
[ Back to top ]