(57)【要約】【課題】  二つのデータを結合した結合データを構成する各データの独立性を維持して結合データを高速に加算処理する。【解決手段】  判定部801は、二つのデータを結合した第一の結合データX、および、二つのデータを結合した第二の結合データYを入力する。分割部702は、第一の結合データXを上位ビットデータA641と下位ビットデータA642に分割し、第二の結合データを上位ビットデータB641と下位ビットデータB642に分割する。加算処理部704は、上位ビットデータA641と上位ビットデータB641を加算処理する。加算処理部705は、下位ビットデータA642と下位ビットデータB642を加算処理する。結合部708は、加算処理によって得られる上位ビットデータ641と下位ビットデータ642を結合した第三の結合データM'を出力する。【選択図】  図12
2012252281.tif 000002
【特許請求の範囲】
【請求項１】
二つのデータを結合した第一の結合データ、および、二つのデータを結合した第二の結合データを入力する入力手段と、
前記第一の結合データを上位ビットデータと下位ビットデータに分割し、前記第二の結合データを上位ビットデータと下位ビットデータに分割する分割手段と、
前記第一の結合データから分割した上位ビットデータと前記第二の結合データから分割した上位ビットデータ、および、前記第一の結合データから分割した下位ビットデータと前記第二の結合データから分割した下位ビットデータをそれぞれ加算処理する加算手段と、
前記加算処理によって得られる上位ビットデータと前記加算処理によって得られる下位ビットデータを結合した第三の結合データを出力する出力手段とを有することを特徴とする演算処理装置。
【請求項２】
前記加算手段は、前記上位ビットデータおよび前記下位ビットデータの最上位ビットの加算における桁上がりを無視することを特徴とする請求項1に記載された演算処理装置。
【請求項３】
前記分割手段は、ハッシュ関数の種類を示す情報を入力し、前記情報に基づき前記上位ビットデータまたは前記下位ビットデータのビット長を決定することを特徴とする請求項1または請求項2に記載された演算処理装置。
【請求項４】
前記二つのデータのビット長が同一であることを特徴とする請求項1から請求項3の何れか一項に記載された演算処理装置。
【請求項５】
前記二つのデータのビット長が異なることを特徴とする請求項1から請求項3の何れか一項に記載された演算処理装置。
【請求項６】
メッセージを入力する入力手段と、
請求項1から請求項5の何れか一項に記載された演算装置を用いて前記メッセージのハッシュ値を演算する演算手段とを有することを特徴とする情報処理装置。
【請求項７】
入力手段、分割手段、加算手段、出力手段を有する演算処理装置の演算方法であって、
前記入力手段が、二つのデータを結合した第一の結合データ、および、二つのデータを結合した第二の結合データを入力し、
前記分割手段が、前記第一の結合データを上位ビットデータと下位ビットデータに分割し、前記第二の結合データを上位ビットデータと下位ビットデータに分割し、
前記加算手段が、前記第一の結合データから分割した上位ビットデータと前記第二の結合データから分割した上位ビットデータ、および、前記第一の結合データから分割した下位ビットデータと前記第二の結合データから分割した下位ビットデータをそれぞれ加算処理し、
前記出力手段が、前記加算処理によって得られる上位ビットデータと前記加算処理によって得られる下位ビットデータを結合した第三の結合データを出力することを特徴とする演算方法。
【請求項８】
コンピュータを請求項1から請求項5の何れか一項に記載された演算処理装置の各手段として機能させることを特徴とするプログラム。
【請求項９】
コンピュータを請求項6に記載された情報処理装置の各手段として機能させることを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、二つのデータを結合した結合データを加算する演算処理に関する。
【背景技術】
【０００２】
特許文献1は、二つの入力メッセージに対して、同じハッシュ関数を並列に適用し、二つのハッシュ値を同時に出力する発明を開示する。
【０００３】
特許文献1の発明は、ハッシュ関数を構成するメインルーチン処理部において、互いに関連しない二つのデータを結合した結合データを処理することで並列処理を実現する。メインルーチンは、構成要素としての論理演算や加算演算などの四則演算を、結合データに対して繰り返し適用する。
【０００４】
しかし、メインルーチンを構成する加算処理において、結合データの下位桁で桁上がりが発生すると桁上がりが上位桁に反映され、結合データの独立性が保てなくなる。これを回避するには、桁上がりを打ち消す例えばマスク処理など複数の演算を組む必要があり、その結果、結合データの加算処理に必要な処理時間が増大する。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第4004805号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明は、
【０００７】
このように、二つのデータを結合した結合データを構成する各データの独立性を維持して結合データを高速に加算処理することを目的とする。
【課題を解決するための手段】
【０００８】
本発明は、前記の目的を達成する一手段として、以下の構成を備える。
【０００９】
二つのデータを結合した第一の結合データ、および、二つのデータを結合した第二の結合データを入力し、前記第一の結合データを上位ビットデータと下位ビットデータに分割し、前記第二の結合データを上位ビットデータと下位ビットデータに分割し、前記第一の結合データから分割した上位ビットデータと前記第二の結合データから分割した上位ビットデータ、および、前記第一の結合データから分割した下位ビットデータと前記第二の結合データから分割した下位ビットデータをそれぞれ加算処理し、前記加算処理によって得られる上位ビットデータと前記加算処理によって得られる下位ビットデータを結合した第三の結合データを出力することを特徴とする。
【発明の効果】
【００１０】
本発明によれば、二つのデータを結合した結合データを構成する各データの独立性を維持して結合データを高速に加算処理することができる。
【図面の簡単な説明】
【００１１】
【図１】実施例の情報処理装置の構成例を説明するブロック図。
【図２】情報処理装置の演算処理を説明するフローチャート。
【図３】メインルーチン処理部の構成例を説明するブロック図。
【図４】メインルーチン処理を説明するフローチャート。
【図５】ラウンド処理部のMD5ラウンド処理を説明するブロック図。
【図６】MD5ラウンド処理を説明するフローチャート。
【図７】ステップ回数kに対するデータMk、データtk、左巡回シフトのビット数s、並べ替えの規則の関係を示す図。
【図８】ラウンド処理部のSHA-1ラウンド処理を説明するブロック図。
【図９】SHA-1ラウンド処理を説明するフローチャート。
【図１０】ラウンド処理部のSHA-2ラウンド処理を説明するブロック図。
【図１１】SHA-2ラウンド処理を説明するフローチャート。
【図１２】結合データの加算処理を説明するブロック図。
【図１３】結合データの加算処理を説明する図。
【図１４】三つ以上のデータを結合した結合データの加算処理を説明する図。
【図１５】実施例2の結合データの加算処理を説明するブロック図。
【図１６】実施例2の結合データの加算処理を説明するフローチャート。
【発明を実施するための形態】
【００１２】
以下、本発明にかかる実施例の演算処理を図面を参照して詳細に説明する。
【実施例１】
【００１３】
［装置の構成］
図1のブロック図により実施例の情報処理装置の構成例を説明する。
【００１４】
分割部12は、入力されるメッセージM1とM2を分割して、メッセージM1に対してx個のメッセージブロックMB1を、メッセージM2に対してy個のメッセージブロックMB2を出力する。なお、本実施例は一種類のハッシュ関数に限定されず、様々なハッシュ関数に対応する。
【００１５】
ハッシュ関数には例えばMD5 (message digest algorithm 5)、SHA (secure hash algorithm)のSHA-1、SHA-224、SHA-256、SHA-384、SHA-512などがある。なお、SHA-224、SHA-256、SHA-384、SHA-512の四つのハッシュ関数はまとめて「SHA-2」と呼ばれることがある。MD5、SHA-1、SHA-224、SHA-256の場合、メッセージは512ビット単位に分割され、先頭の512ビットから順に分割ブロックとして出力される。同様に、SHA-384、SHA-512の場合、メッセージは1024ビット単位に分割され、先頭の1024ビットから順にメッセージブロックとして出力される。
【００１６】
初期値保持部13は、ハッシュ生成に伴うイニシャル値を保持し、メインルーチン処理部15の要求に応じて保持するイニシャル値を出力する。なお、イニシャル値は、ハッシュ値の初期値であり固定値である。
【００１７】
本実施例の初期値保持部13は、ハッシュ関数が利用するイニシャル値IVを二つ結合した値IV|IVの状態で保持する。例えば、メインルーチン処理部15が同じハッシュ関数SHA-1を適用する場合、SHA-1のイニシャル値「67452301」（32ビット16進数）を二つ結合した値である。つまり、初期値保持部13は、イニシャル値IV|IVとして「6745230167452301」（64ビット16進数）を出力する。
【００１８】
レジスタ14は、初期値保持部13が出力するイニシャル値IV|IV、または、出力スイッチ17から詳細は後述する二次中間データEX|EX'を入力し、入力値をR|R'として保持する。なお、レジスタ14は、初回のみイニシャル値IV|IVを入力し、以降は二次中間データEX|EX'を入力する。
【００１９】
メインルーチン処理部15は、分割部12からメッセージブロックMB1とMB2を入力し、レジスタ14からR|R'を入力して、処理を行い、一次中間データD|D'を出力する。なお、一次中間データD|D'は、後述する結合部316から出力されるデータである。
【００２０】
排他的論理和部16は、メインルーチン処理部15が出力する一次中間データD|D'、または、レジスタ14が保持する値R|R'を入力して排他的論理和演算を行い、演算結果を二次中間データEX|EX'として出力する。
【００２１】
スイッチ17は、排他的論理和部16が出力する二次中間データEX|EX'をレジスタ14または分割部18に出力する。スイッチ17は、分割部12によって分割されたメッセージブロックMB1およびMB2のすべてが処理されたと判定した場合は二次中間データEX|EX'を分割部18へ出力し、そうでなければ二次中間データEX|EX'をレジスタ14に出力する。
【００２２】
分割部18は、出力スイッチ17から入力される二次中間データEX|EX'をEXとEX'に分割し、EXをメッセージM1のハッシュ値H1として、EX'をメッセージM2のハッシュ値H2として出力する。
【００２３】
［演算処理］
図2のフローチャートにより情報処理装置の演算処理を説明する。
【００２４】
分割部12は、例えばユーザが入力するハッシュ値の元である任意長のメッセージM1とM2を入力し(S21)、入力したメッセージM1とM2を分割して、x個のメッセージブロックMB1と、y個のメッセージブロックMB2を生成する(S22)。
【００２５】
次に、初期値保持部13は、保持するイニシャル値IV|IVをレジスタ14に設定し(S23)、レジスタ14のメッセージカウンタiに0を初期設定する(S24)。なお、メッセージカウンタiは、何番目までのメッセージブロックMB1とMB2がメインルーチン処理部15に入力されたかをカウントするカウンタである。
【００２６】
次に、分割部12は、メッセージカウンタiのカウント値iに対応するメッセージブロックMB1iとMB2iをメインルーチン処理部15に入力する(S25)。メインルーチン処理部15は、入力されたメッセージメッセージMB1とMB2、および、レジスタ14が保持するR|R'を用いて、詳細を後述するメインルーチン処理を行い、一次中間データD|D'を排他的論理和部16に出力する(S26)。
【００２７】
次に、排他的論理和部16は、一次中間データD|D'とレジスタ14が保持するR|R'の排他的論理和を演算し、演算結果の二次中間データEX|EX'をスイッチ17に出力する(S27)。スイッチ17は、メッセージカウンタiを参照して、メッセージブロックMB1とMB2のすべてが処理されたか否かを判定する(S28)。
【００２８】
スイッチ17は、メッセージブロックのすべてが処理された場合は処理をステップS31へ進め、未処理のメッセージブロックがある場合は処理をステップS29へ進める。なお、MB1の総数xとMB2の総数yが異なる場合は、何れか数が多い方のメッセージブロックについてステップS28の判定を行う。言い換えれば、x-1≦iかつy-1≦iがループ処理の終了条件である。
【００２９】
未処理のメッセージブロックがある場合、スイッチ17は、二次中間データEX|EX'をレジスタ14に設定し(S29)、メッセージカウンタiをインクリメントし(S30)、処理をステップS25に戻す。また、メッセージブロックのすべてが処理された場合、スイッチ17は二次中間データEX|EX'を分割部18に出力し、分割部18は二次中間データEX|EX'をハッシュ値H1とH2に分割して出力する(S31)。
【００３０】
［メインルーチン処理部］
図3のブロック図によりメインルーチン処理部15の構成例を説明する。
【００３１】
●分割部
分割部31は、レジスタ14から入力したR|R'を順に所定ビット長の複数のビット系列A-Hに分割する。アルゴリズムと分割の関係は次のようになる。
──────┬─────────┬───────┬────────
アルゴリズム│    入力 R|R'     │使用ビット系列│未使用ビット系列
──────┼─────────┼───────┼────────
MD5       │  64ビット長、四つ│      A-D     │      E-H
SHA-1     │  64ビット長、五つ│      A-E     │      F-H
SHA-224   │  64ビット長、八つ│      A-H     │      −
SHA-256   │  64ビット長、八つ│      A-H     │      −
SHA-384   │ 128ビット長、八つ│      A-H     │      −
SHA-512   │ 128ビット長、八つ│      A-H     │      −
──────┴─────────┴───────┴────────
【００３２】
●ワード設定部
ワード設定部32と33は、メッセージブロックMB1とMB2を入力する。そして、アルゴリズムごとに決められた下記の演算により、メッセージブロックMB1とMB2を処理して、処理結果のメッセージブロックMX1とMX2を出力するワード設定処理を行う。
if (MD5) {
MX1 = MB1；
MX2 = MB2；
}                        …(1)
if (SHA-1) {
if (0 ≦ t ≦ 15)
MXnt = MBnt；
if (16 ≦ t ≦ 79)
MXnt = ROTL1(MXnt-3^MXnt-8^MXnt-14^MXnt-16)；
}                        …(2)
ここで、「^」は排他的論理和演算子、
ROTL1は1ビット左巡回シフト演算を表す、
MBnは512ビット長のMB1またはMB2、
MBntはMBnを16分割した32ビット長のデータのt番目のデータ、
MXnはワード設定処理の処理結果MX1またはMX2、
MXntは80個のブロックで構成されるMXnのt番目のデータ。
【００３３】
左巡回シフト演算ROTLは、最左端からシフトアウトしたビットを最右端から挿入するシフト処理である。SHA-1の場合は、32ビットの範囲で左巡回シフトを行い、33ビット目以降にシフトされたビットを1ビット目から順に挿入することになる。
if (SHA-224 || SHA-256) {
if (0 ≦ t ≦ 15)
MXnt = MBnt；
if (16 ≦ t ≦ 63)
MXnt = F1(MXnt-2) + MXnt-7 + F0(MXnt-15) + MXnt-16；
}                        …(3)
ここで、MBnは512ビット長のMB1またはMB2、
MXntは64個のブロックで構成されるMXnのt番目のデータ。
【００３４】
式(3)における関数F0とF1は下式で示される。
F0(x) = ROTR7(x)^ROTR18(x)^SHR3(x)
F1(x) = ROTR17(x)^ROTR19(x)^SHR10(x)      …(4)
ここで、ROTRmはmビット右巡回シフト演算を表す、
SHRmはmビット右シフト演算を表す。
【００３５】
右巡回シフト演算ROTRは、最右端からシフトアウトしたビットを最左端から挿入するシフト処理である。SHA-224とSHA-256の場合は、32ビットの範囲で右巡回シフトを行い、1ビット目から右にシフトされたビットを32ビット目から順に挿入することになる。
if (SHA-384 || SHA-512) {
if (0 ≦ t ≦ 15)
MXnt = MBnt；
if (16 ≦ t ≦ 79)
MXnt = F3(MXnt-2) + MXnt-7 + F2(MXnt-15) + MXnt-16；
}                        …(5)
ここで、MBnは1024ビット長のMB1またはMB2、
MXntは80個のブロックで構成されるMXnのt番目のデータ。
【００３６】
式(5)における関数F2とF3は下式で示される。
F2(x) = ROTR1(x)^ROTR8(x)^SHR7(x)
F3(x) = ROTR19(x)^ROTR61(x)^SHR6(x)      …(6)
【００３７】
なお、SHA-384とSHA-512の場合は、64ビットの範囲で右巡回シフトを行い、1ビット目から右にシフトされたビットを64ビット目から順に挿入することになる。
【００３８】
●連結部
連結部40は、メッセージブロックMX1とMX2を入力し、それらを連結した結合データMX1|MX2を出力する。
【００３９】
MD5、SHA-1、SHA-224、SHA-256の場合、メッセージブロックMX1とMX2はそれぞれ32ビットであり、出力される結合データMX1|MX2は64ビットである。SHA-384、SHA-512の場合、メッセージブロックMX1とMX2はそれぞれ64ビットであり、出力される結合データMX1|MX2は128ビットである。
【００４０】
ワード設定部32と33、連結部40は、後段のラウンド処理部34-37の何れかが処理を実行する度に、ワード設定処理と連結処理を実行し、結合データMX1|MX2を出力する。その結果、ラウンド処理34-37それぞれに対して異なる結合データMX1|MX2が出力される。
【００４１】
●ラウンド処理部
ラウンド処理部34-37は、ビット系列A-H、結合データMX1|MX2、初期値保持部41-44が保持する初期値を入力し、アルゴリズムによって定義された所定のラウンド処理をビット系列に施した処理結果のビット系列を出力する。詳細は後述するが、一段目のラウンド処理部34はビット系列A-Hを入力し、二段目以降のラウンド処理部35-37はそれぞれ前段のラウンド処理部が出力するビット系列を入力する。
【００４２】
●加算部
詳細は後述するが、加算部45-52はそれぞれ、分割部31が出力するビット系列と、ラウンド処理部37が出力するビット系列を入力し、それらビット系列を加算した加算結果を出力する。なお、MD5の場合は、使用ビット系列がA-Dであり、加算部49-52の処理は実行されない。また、SHA-1の場合は、使用ビット系列がA-Eであり、加算部50-52の処理は実行されない。
【００４３】
●初期値保持部
初期値保持部41-44はそれぞれ、アルゴリズムごとに定義された初期値t1-t4を保持する。例えば、初期値保持部41は、保持する初期値t1を二つ連結した初期値t1|t1をラウンド処理部34に出力する。他の初期値保持部42-44も同様に保持する初期値を二つ連結した初期値を出力する。
【００４４】
アルゴリズムと初期値の関係は、MD5の場合は後述するMD5によるラウンド処理のtjが初期値であり、SHA-1、SHA-2の場合は後述するSHA-1、SHA-2によるラウンド処理のKjが初期値である。
【００４５】
●結合部
結合部320は、加算部45-52から加算結果のビット系列を入力し、加算結果のビット系列を結合して、メインルーチン処理部15の出力として一次中間データD|D'を出力する。
【００４６】
●メインルーチン処理
図4のフローチャートによりメインルーチン処理を説明する。なお、図4は、本実施例に適応可能な結合データの加算処理を示す。
【００４７】
ワード設定部32、33は、分割部12からメッセージブロックMB1、MB2を入力してワード設定処理を行う(S41)。連結部40は、MX1、MX2を連結する(S42)。
【００４８】
次に、分割部31は、レジスタ14からR|R'を入力して、R|R'を順に所定ビット長の複数のビット系列A-Hに分割する(S43)。そして、ラウンド処理の段数をカウントするカウンタjの値を「1」に設定する(S44)。
【００４９】
次に、カウント値jに応じてラウンド処理部34-37の処理が繰り返される。例えばカウント値j=1の場合は、ラウンド処理部34が初期値保持部41が保持する初期値t1|t1、結合データMX1|MX2、ビット系列を入力して(S45)、一段目のラウンド処理を実行する(S46)。ラウンド処理が終了するとカウンタjはインクリメントされる(S47)。
【００５０】
次に、カウント値jが判定され(S48)、j＜5であれば処理はステップS45に戻り、カウント値jに対応するラウンド処理部の処理が実行される。
【００５１】
カウント値j=5になるとラウンド処理が終了し、加算部45-52は、分割部31が分割したビット系列と、ラウンド処理部37が出力するビット系列を加算処理する(S48)。そして、結合部38は、加算結果のビット系列を結合して一次中間データD|D'を出力する(S49)。
【００５２】
［ラウンド処理］
●MD5におけるラウンド処理
図5のブロック図によりラウンド処理部のMD5ラウンド処理を説明する。
【００５３】
入力スイッチ501は、初期の入力データ（ビット系列）A-Dまたは出力スイッチ509から渡されるデータA'-D'を入力する。そして、データAまたはA'を加算処理部503に出力し、データB-DまたはB'-D'を非線形処理部502と並べ替え部508に出力する。なお、初期の入力データA-Dは、分割部31または一つ前のラウンド処理部が出力するビット系列A-Dに相当する。
【００５４】
非線形処理部502は、データB-D（またはB'-D'）に非線形処理を施し、処理結果rを加算処理部503に出力する。なお、非線形処理の内容は後述するラウンド（ステップ回数kの範囲）ごとに異なる。
if (0 ≦ k ＜ 16)
r = (B && C)||(!B && D)；非線形処理関数F    …(7)
if (16 ≦ k ＜ 32)
r = (B && D)!(C(!D))；非線形処理関数G      …(8)
if (32 ≦ k ＜ 48)
r = B^C^D；非線形処理関数H              …(9)
if (48 ≦ k ＜ 64)
r = C^(B ||!D)；非線形処理関数I          …(10)
ここで、&&は論理積演算子、
||は論理和演算子、
!は否定演算子、
＾は排他的論理和演算子。
【００５５】
加算処理部503は、データrとデータA（またはA'）を加算した結果r1を加算処理部504に渡す。加算処理部504は、データr1とデータMkを加算した結果r2を加算処理部505に渡す。なお、データMkはステップ回数kごとに異なるデータである。加算処理部505は、データr2とデータtkを加算した結果r3を左巡回処理部506に渡す。なお、データtkはステップ回数kごとに異なる入力データである。
【００５６】
左巡回処理部506は、データr3を左巡回シフトした結果r4を加算処理部507に渡す。上述したように、MD5の場合、32ビットの範囲の左巡回シフトを行い、33ビット目以降にシフトされたビットを1ビット目から順に挿入する。加算処理部507は、データr4とデータBを加算した結果r5を並べ替え部508に渡す。並べ替え部508は、詳細は後述するが、データr5（更新されたデータA）、データB、C、DをデータA'-D'に並べ替えた結果を出力スイッチ509に渡す。
【００５７】
出力スイッチ509は、ラウンド処理の終了を判定し、終了の場合は、並べ替え部509が出力するデータA'-D'を出力データA-Dとして出力する。また、終了ではない場合は、並べ替え部509が出力するデータA'-D'として入力スイッチ501に渡す。
【００５８】
図6のフローチャートによりMD5ラウンド処理を説明する。
【００５９】
ラウンド処理部は、カウンタkを0に初期化し(S601)、カウンタkのカウント値（ステップ回数k）により処理を分岐する(S602)。k=0-15の場合は非線形処理関数Fによる非線形処理をデータA（またはA'）に施す(S603)。また、k=16-31の場合は非線形処理関数Gによる非線形処理をデータA（またはA'）に施す(S604)。k=32-47の場合は非線形処理関数Hによる非線形処理をデータA（またはA'）に施す(S605)。k=48-63の場合は非線形処理関数Iによる非線形処理をデータA（またはA'）に施す(S606)。
【００６０】
次に、ラウンド処理部は、非線形処理結果のデータrとデータA（またはA'）を加算し(S607)、データr1(=r+A)とデータMkを加算する(S608)。さらに、データr2(=r1+Mk)とデータtkを加算し(S609)、データr3(=r2+tk)をsビット左巡回シフトし(S610)、データr4(=r3＜＜＜s)にデータBを加算する(S611)。次に、ラウンド処理部は、データr5(=r4+B)、B、C、Dを並べ替える(S612)。
【００６１】
図7によりステップ回数kに対するデータMk、データtk、左巡回シフトのビット数s、並べ替えの規則の関係を示す。
【００６２】
例えば、ステップk=0において、更新されたデータA（r5）、B、C、Dは、A→D'、B→A'、C→B'、D→C'に並べ替える。そして、ステップ数kをインクリメントし(S613)、ステップ数kが規定の回数（この場合は63）を超えたか否かを判定する(S614)。つまりk＜64の場合は処理をステップS602に戻して、並べ替え後のデータA'-D'によってステップS602からS612の処理を繰り返す。また、k=64の場合は、並べ替え後のデータA'-D'をデータA、B、C、Dとして出力し(S615)、ラウンド処理を終了する。
【００６３】
●SHA-1におけるラウンド処理
図8のブロック図によりラウンド処理部のSHA-1ラウンド処理を説明する。
【００６４】
入力スイッチ601は、初期の入力データ（ビット系列）A-Eまたは出力スイッチ610から渡されるデータA'-E'を入力する。そして、データAまたはA'を左巡回処理部602と並べ替え部609に出力する。さらに、データBまたはB'を非線形処理部603と左巡回処理部605に、データC、DまたはC'、D'を非線形処理部603と並べ替え部609に、データEまたはE'を加算処理部604にそれぞれ出力する。なお、初期の入力データA-Eは、分割部31または一つ前のラウンド処理部が出力するビット系列A-Eに相当する。
【００６５】
左巡回処理部602は、データA（またはA'）を左巡回シフトした結果r'を加算処理部606に渡す。左巡回処理部605は、データB（またはB'）を左巡回シフトした結果r"を並べ替え部609に渡す。上述したように、SHA-1の場合、32ビットの範囲の左巡回シフトを行い、33ビット目以降にシフトされたビットを1ビット目から順に挿入する。
【００６６】
非線形処理部603は、データB-D（またはB'-D'）に非線形処理を施し、処理結果rを加算処理部604に出力する。なお、非線形処理の内容はラウンドごとに異なる。
if (0 ≦ k ＜ 20)
r = (B && C)^(!B && D)；非線形処理関数F            …(11)
if ((20 ≦ k ＜ 40) || (60 ≦ k ＜ 80))
r = B ^ C ^；非線形処理関数G                    …(12)
if (40 ≦ k ＜ 60)
r = (B && C)^(C && D)^(D && B)；非線形処理関数H    …(13)
【００６７】
加算処理部604は、データrとデータE（またはE'）を加算した結果r1を加算処理部606に渡す。加算処理部606は、データr1とデータr"を加算した結果r2を加算処理部607に渡す。加算処理部607は、データr2とデータWkを加算した結果r3を加算処理部608に渡す。加算処理部608は、データr3とデータKkを加算した結果r4を並べ替え部609に渡す。なお、データWkはステップ回数kごとに異なるデータである。また、データKkの値（16進数）を下に示す。
if (0 ≦ k ＜ 20)
Kk = 5a827999；
if (20 ≦ k ＜ 40)
Kk = 6ed9eba1；
if (40 ≦ k ＜ 60)
Kk = 8f1bbcdc；
if (60 ≦ k ＜ 80)
Kk = ca62c1d6；      …(14)
【００６８】
並べ替え部609は、更新後のデータr"とr4、および、データA、C、Dを並べ替えた結果を出力スイッチ610に渡す。出力スイッチ610は、ラウンド処理の終了を判定し、終了の場合は、並べ替え部609が出力するデータを出力データA-Eとして出力する。また、終了ではない場合は、並べ替え部509が出力するデータをデータA'-E'として入力スイッチ601に渡す。
【００６９】
図9のフローチャートによりSHA-1ラウンド処理を説明する。
【００７０】
ラウンド処理部は、カウンタkを0に初期化し(S621)、カウンタkのカウント値（ステップ回数k）により処理を分岐する(S622)。k=0-19の場合は非線形処理関数Fによる非線形処理をデータB（またはB'）に施す(S623)。また、k=20-39の場合は非線形処理関数Gによる非線形処理をデータB（またはB'）に施す(S624)。k=40-59の場合は非線形処理関数Hによる非線形処理をデータB（またはB'）に施す(S625)。k=60-79の場合は非線形処理関数Gによる非線形処理をデータB（またはB'）に施す(S626)。
【００７１】
次に、ラウンド処理部は、データA（またはA'）を5ビット左巡回シフトし(S627)、データB（またはB'）を30ビット左巡回シフトする(S628)。さらに、非線形処理結果のデータrとデータE（またはE'）を加算し(S629)、データr1(=r+E)とデータr'を加算する(S630)。さらに、データr2(=r1+r')とデータWkを加算し(S631)、データr3(=r2+Wk)とデータKkを加算する(S632)。
【００７２】
次に、ラウンド処理部は、データA'=r4(=r3+Kk)、B'=A、C'=r"、D'=C、E'=Dに並べ替える(S633)。そして、ステップ数kをインクリメントし(S634)、ステップ数kが規定の回数（この場合は79）を超えたか否かを判定する(S635)。つまりk＜80の場合は処理をステップS622に戻して、並べ替え後のデータA'-E'によってステップS622からS633の処理を繰り返す。また、k=80の場合は、並べ替え後のデータA'-E'をデータA-Eとして出力し(S636)、ラウンド処理を終了する。
【００７３】
●SHA-2におけるラウンド処理
図10のブロック図によりラウンド処理部のSHA-2（SHA-224、SHA-256、SHA-384、SHA-512）ラウンド処理を説明する。
【００７４】
入力スイッチ701は、初期の入力データ（ビット系列）A-Hまたは出力スイッチ714から渡されるデータA'-H'を入力する。データAまたはA'を非線形処理部702、非線形処理部703および並べ替え部713に出力する。データB、CまたはB'、C'を非線形処理部703と並べ替え部713に出力する。データDまたはD'を加算処理部711に出力する。データEまたはE'を非線形処理部704、非線形処理部705および並べ替え部713に出力する。データF、GまたはF'、G'を非線形処理部704と並べ替え部713に出力する。データHまたはH'を加算処理部706に出力する。なお、初期の入力データA-Hは、分割部31または一つ前のラウンド処理部が出力するビット系列A-Hに相当する。
【００７５】
非線形処理部702は、データA（またはA'）に下式に示す非線形処理を施し、処理結果r1を加算処理部710に渡す。
if (SHA-224 || SHA-256)
(X, Y, Z) = (2, 3, 12)；
if (SHA-384 || SHA-512)
(X, Y, Z) = (28, 34, 39)；
r1 = ROTRX(A)^ROTRY(A)^ROTRZ(A)；      …(15)
【００７６】
非線形処理部703は、データA-C（またはA'-C'）に下式に示す非線形処理を施し、処理結果r2を加算処理部710に渡す。なお、SHA-224、SHA-256の場合、下式は32ビット単位で実行される。また、SHA-384、SHA-512の場合、下式は64ビット単位で実行される。
r2 = (A && B)^(B && C)^(C && A)      …(16)
【００７７】
非線形処理部704は、データE-G（またはE'-G'）に下式に示す非線形処理を施し、処理結果r'1を加算処理部706に渡す。
r1' = (E && F)^(!E && G)      …(17)
【００７８】
非線形処理部705は、データE（またはE'）に下式に示す非線形処理を施し、処理結果r'2を加算処理部707に渡す。なお、SHA-224、SHA-256の場合、32ビットの範囲で右巡回シフトである。また、SHA-384、SHA-512の場合、64ビットの範囲での右巡回シフトである。
if (SHA-224 || SHA-256)
(X, Y, Z) = 6、11、25；
if (SHA-384 ||SHA-512)
(X, Y, Z) = 14、18、41；
r2' = ROTRX(E)^ROTRY(E)^ROTRZ(E)；      …(18)
【００７９】
以下で説明する加算処理は、SHA-224、SHA-256の場合は32ビット単位で、SHA-384、SHA-512の場合は64ビット単位で行われる。
【００８０】
加算処理部710は、データr1とデータr2を加算処理し、処理結果r3を加算処理部712に渡す。加算処理部706は、データH（またはH'）とデータr'1を加算処理し、処理結果r'3を加算処理部707に渡す。加算処理部707は、データr'2とデータr'3を加算処理し、処理結果r'4を加算処理部708に渡す。加算処理部708は、データr4'とデータWkを加算処理し、処理結果r'5を加算処理部709に渡す。加算処理部709は、データr'5とデータKkを加算処理し、処理結果r'6を加算処理部711と712に渡す。なお、データWk、Kkはステップ回数kごとに異なるデータである。データKkはSHA-224、SHA-256の場合は32ビットの64個の固定値であり、SHA-224、SHA-256の場合は64ビットの80個の固定値である。
【００８１】
加算処理部711は、データr3とデータr'6を加算処理し、処理結果r4を並べ替え部713に渡す。加算処理部712は、データD（またはD'）とデータr'6を加算処理し、処理結果r5を並べ替え部713に渡す。
【００８２】
並べ替え部713は、A、B、C、更新後のデータr4、r5、データE、F、GをデータA'-H'に並べ替えた結果を出力スイッチ714に渡す。出力スイッチ714は、ラウンド処理の終了を判定し、終了の場合は、並べ替え部713が出力するデータA'-H'を出力データA-Hとして出力する。また、終了ではない場合は、並べ替え部713が出力するデータA'-H'を入力スイッチ701に渡す。
【００８３】
図11のフローチャートによりSHA-2ラウンド処理を説明する。
【００８４】
ラウンド処理部は、カウンタkを0に初期化し(S641)、式(15)によりデータA（またはA'）に非線形処理を施す(S642)。さらに、式(16)によりデータA-C（またはA'-C'）に非線形処理を施し(S643)、式(17)によりデータE-G（またはE'-G'）に非線形処理を施し(S644)、式(18)によりデータE（またはE'）に非線形処理を施す(S645)。
【００８５】
次に、ラウンド処理部は、式(15)の非線形処理の結果r1と式(16)の非線形処理の結果r2を加算する(S646)。また、データH（またはH'）と式(17)の非線形処理の結果r'1を加算し(S647)、データr'3(=H+r'1)と式(18)の非線形処理の結果r'2を加算する(S648)。そして、データr'4(=r'2+r'3)とデータWkを加算し(S649)、データr'5(=r'4+Wk)とデータKkを加算する(S649)。さらに、データD（またはD'）とデータr'6(=r'5+Kk)を加算し(S650)、データr3(=r1+r2)とデータr'6を加算する(S651)。
【００８６】
次に、ラウンド処理部は、データA'=r4(=r3+r'6)、B'=A、C'=B、D'=C、E'=r5(=D+r'6)、F'=E、G'=F、H'=Gに並べ替える(S652)。そして、ステップ数kをインクリメントし(S653)、ステップ数kが規定の回数を超えたか否かを判定する(S654)。つまり、SHA224、SHA256の場合はk＜64であれば処理をステップS642に戻す。また、SHA384、SHA512の場合はk＜80であれば処理をステップS642に戻し、並べ替え後のデータA'-H'によってステップS642からS653の処理を繰り返す。また、ステップ数kが規定の回数を超えた場合は、並べ替え後のデータA'-H'をデータA-Hとして出力し(S656)、ラウンド処理を終了する。
【００８７】
［加算処理］
図12のブロック図により結合データの加算処理を説明する。
【００８８】
判定部801は、結合データX（第一の結合データ）および結合データY（第二の結合データ）、並びに、アルゴリズムIDを入力し、アルゴリズムIDに従い結合データXとYを64ビット分割部802または32ビット分割部803に出力する。結合データXとYは、32ビットまたは64ビット長の独立したデータ二つを結合したデータである。例えば、図3に示すラウンド処理部37の出力Aや分割部31の出力Aが結合データXとYである。また、アルゴリズムIDは、ハッシュ関数の種類を特定するための情報であり、結合データを分割する際の分割データのビット長の決定に利用される。
【００８９】
判定部801は、アルゴリズムIDがSHA-512またはSHA-384を示す場合、結合データXとYをそれぞれA128、B128として64ビット分割部802へ出力する。一方、アルゴリズムIDがSHA-512、SHA-384以外を示す場合は、結合データXとYをそれぞれA64、B64として32ビット分割部803へ出力する。
【００９０】
64ビット分割部802は、入力される結合データA128、B128をそれぞれを分割する。そして、結合データA128から上位64ビットを分割した上位ビットデータA641と、結合データB128から上位64ビットを分割した上位ビットデータB641を加算処理部804へ出力する。また、結合データA128から下位64ビットを分割した下位ビットデータA642と、結合データB128から下位64ビットを分割した下位ビットデータB642を加算処理部805へ出力する。
【００９１】
32ビット分割部803は、入力される結合データA64、B64をそれぞれを分割する。そして、結合データA64から上位32ビットを分割した上位ビットデータA321と、結合データB64から上位32ビットを分割した上位ビットデータB311を加算処理部806へ出力する。また、結合データA64から下位32ビットを分割した下位ビットデータA322と、結合データB64から下位32ビットを分割した下位ビットデータB322を加算処理部807へ出力する。
【００９２】
加算処理部804は、上位ビットデータA641とB641を加算した上位ビットデータ641を出力する。同様に、加算処理部805は、下位ビットデータA642とB642を加算した下位ビットデータ642を出力する。その際、加算処理部804と805は、最上位ビットの加算で桁上がりが発生した場合も、発生した桁上がりを無視した64ビットの加算結果を出力する。
【００９３】
加算処理部806は、上位ビットデータA321とB321を加算した上位ビットデータ321を出力する。同様に、加算処理部807は、下位ビットデータA322とB322を加算した下位ビットデータ322を出力する。その際、加算処理部806と807は、最上位ビットの加算で桁上がりが発生した場合も、発生した桁上がりを無視した32ビットの加算結果を出力する。
【００９４】
128ビット結合部808は、上位ビットデータ641と下位ビットデータ642を入力して、それらデータを結合した128ビット長のデータM'を出力する。同様に、64ビット結合部709は、上位ビットデータデータ321と下位ビットデータ322を入力し、それらデータを結合した64ビット長のデータM'（第三の結合データ）を出力する。
【００９５】
図13により結合データの加算処理を説明する。図13(a)に示すように、結合データ901と904はそれぞれ上位ビットデータと下位ビットデータに分割され、分割データ902、903、905、906が生成される。そして、上位ビットデータである分割データ902と905が加算処理907され、下位ビットデータである分割データ903と906が加算処理908される。そして、加算処理結果であるデータ909と910を結合して再結合データ911にする。
【００９６】
図13(b)は結合データを分割せずに加算処理を行う例を示す。この場合、下位ビットデータ903と906の加算処理（演算914）において最上位ビットで桁上がりが発生すると、再結合データ915の上位ビットデータ916の最下位ビットに桁上がりが反映される問題が生じる。これを抑制するには、桁上がりをマスク処理する必要があり、処理速度が低下する。
【００９７】
例えば4ビットの結合データの加算を例に説明する。結合データXを‘1010’（二進数）、結合データYを‘0011’とする。結合データXとYの下位ビットデータ‘10’と‘11’を加算すると‘101’になり桁上がりが発生し、再結合データは‘1101’になる。つまり、下位2ビットデータの最上位ビットの桁上がりが上位2ビットデータの最下位ビットに影響する。
【００９８】
本実施例においては、桁上がりを無視するため、結合データXとYの下位ビットデータ‘10’と‘11’の加算結果は‘01’であり、再結合データは‘1001’になり、桁上がりによる上位ビットデータへの影響を回避することができる。
【００９９】
［変形例］
図12には二つの結合データX、Yの加算処理を示したが、三つ以上のデータを結合した結合データの加算処理に本実施例を適用することができる。図14により三つ以上のデータを結合した結合データの加算処理を説明する。
【０１００】
図14(b)に示すアルゴリズム表から分割データのサイズを取得し(S141)、取得した分割データのサイズ単位に、三つ以上の結合データそれぞれを上位ビット（または下位ビット）から順次分割し、複数個の分割データを生成する(S142)。そして、分割データのサイズ長のレジスタに分割データを格納し(S143)、レジスタ同士の加算を行い(S144)、加算結果を結合する(S144)。
【０１０１】
加算するレジスタの組み合わせは、分割位置が対応する分割データを格納するレジスタ同士である。例えば、6ビットの結合データA‘100100’と結合データB‘001001’を2ビットに分割して加算する場合、加算の組み合わせは上位ビットから順に‘10’と‘00’、‘01’と‘10’、‘00’と‘01’である。勿論、桁上がりは無視する。
【０１０２】
このように、二つのデータを結合した結合データを構成する各データの独立性を維持して結合データを高速に加算処理することができる。つまり、結合データを処理する並列処理における結合データの加算処理は、結合データから分割した上位ビットデータと下位ビットデータそれぞれを加算処理し、二つの加算結果を結合することで、結合データを高速に加算処理することができる。
【実施例２】
【０１０３】
以下、本発明にかかる実施例2の演算処理を説明する。なお、実施例2において、実施例1と略同様の構成については、同一符号を付して、その詳細説明を省略する。
【０１０４】
実施例1では、二つのメッセージに対してメインルーチンで適用するハッシュアルゴリズムのアルゴリズム処理単位の長さが同一の場合を説明した。実施例2では、アルゴリズム処理単位の長さが異なる場合を説明する。なお、実施例2におけるシステム構成と処理、メインルーチン処理部、および、各ハッシュアルゴリズムに対するラウンド処理は実施例1と同一であり、その詳細説明を割愛する。
【０１０５】
［加算処理］
図15のブロック図により実施例2の結合データの加算処理を説明する。
【０１０６】
判定部811は、結合データXとY、および、アルゴリズムIDおよびアルゴリズムIDに関連付けられた処理対象のビットを示す情報を入力し、アルゴリズムIDに従い結合データXとYを64ビット分割部812または32ビット分割部813に出力する。
【０１０７】
結合データXとYは、32ビット長または64ビット長の独立したデータX1およびX2、Y1およびY2を結合したデータである。なお、結合データXとYを構成するデータのビット長は異なり、例えば結合データXは64ビット長のデータX1と32ビット長のデータX2を結合したデータである。
【０１０８】
アルゴリズムIDは、ハッシュ関数の種類を特定するための情報である。また、処理対象のビットを示す情報（以下、対象ビット情報）は、結合データを構成するデータのうちの何れかを指示し、例えば「上位64ビット」と指定されている。
【０１０９】
判定部811は、アルゴリズムIDがSHA-512またはSHA-384を示すと判定した場合は、結合データXとY、および、対象ビット情報819を64ビット分割部812に出力する。一方、アルゴリズムIDがSHA-512、SHA-384以外を示すと判定した場合は、結合データXとY、および、対象ビット情報820を32ビット分割部813に出力する。
【０１１０】
64ビット分割部812は、対象ビット情報819に従い、結合データXとYをそれぞれを分割する。例えば、対象ビット情報819が「上位64ビット」を示す場合、結合データXの上位64ビットを分割した上位ビットデータA641と、結合データYの上位64ビットを分割した上位ビットデータB641を加算処理部804へ出力する。つまり、対象ビット情報819が「上位64ビット」を示す場合は、判定部811から入力される96(=64+32)ビット長の結合データXとYの上位64ビットを分割する。また、対象ビット情報819が「下位64ビット」を示す場合は、96(=32+64)ビット長の結合データXとYの下位64ビットを分割する。
【０１１１】
32ビット分割部813は、対象ビット情報820に従い、結合データXとYをそれぞれ分割する。例えば、対象ビット情報820が「下位32ビット」を示す場合、結合データXの下位32ビットを分割した下位ビットデータA322と、結合データYの下位32ビットを分割した下位ビットデータY322を加算処理部807へ出力する。つまり、対象ビット情報820が「下位32ビット」を示す場合は、判定部811から入力される96(=64+32)ビット長の結合データXとYの下位32ビットを分割する。また、対象ビット情報820が上位32ビットを示す場合は、96(=32+64)ビット長の結合データXとYの上位32ビットを分割する。
【０１１２】
加算処理部804-807は、図12に示した実施例1と同様の処理を行うので、その詳細説明を割愛する。
【０１１３】
結合部818は、上位ビットデータ641と下位ビットデータ322、あるいは、上位ビットデータ321と下位ビットデータ642を入力し、それらデータを結合した96ビット長の結合データM'を出力する。
【０１１４】
図16のフローチャートにより実施例2の結合データの加算処理を説明する。
【０１１５】
加算処理部は、入力したアルゴリズムIDと対象ビット情報から使用するレジスタ長と処理対象のビットを判定する(S1601)。
【０１１６】
アルゴリズムIDと対象ビット情報が「SHA-512（またはSHA-384）」「上位64ビット」を示す場合は96ビット長の結合データXとYをそれぞれ分割する。そして、上位64ビットの分割データA641とB641を64ビット長のレジスタに格納する(S1602)。そして、分割データA641とB641を加算する(S1603)。
【０１１７】
アルゴリズムIDと対象ビット情報が「SHA-512（またはSHA-384）」「下位64ビット」を示す場合は96ビット長の結合データXとYをそれぞれ分割する。そして、下位64ビットの分割データA642、B642を64ビット長のレジスタに格納する(S1604)。そして、分割データA642とB642を加算する(S1605)。
【０１１８】
アルゴリズムIDと対象ビット情報が「SHA-512、SHA-384以外」「上位32ビット」を示す場合は96ビット長の結合データXとYをそれぞれ分割する。そして、上位32ビットの分割データA321、B321を32ビット長のレジスタに格納する(S1606)。そして、分割データA321とB321を加算する(S1607)。
【０１１９】
アルゴリズムIDと対象ビット情報が「SHA-512、SHA-384以外」「下位32ビット」を示す場合、96ビット長の結合データXとYをそれぞれ分割する。そして、下位32ビットの分割データA322、B322を32ビット長のレジスタに格納する(S1608)。そして、分割データA322とB322を加算する(S1609)。
【０１２０】
加算処理部は、実施例1で説明したように、上記の加算処理において最上位ビットの桁上がりを無視する。そして、ステップS1603またはS1607の加算結果を上位ビットデータとして、ステップS1605またS1609の加算結果を下位ビットデータとして、それらデータを結合して96ビット長の結合データにする(S1610)。
【０１２１】
［変形例］
上記の実施例においては、MD5、SHA-1、SHA-2アルゴリズムを例に説明を行ったが、本発明の適用はこれらの演算処理に限定されない。例えば、アルゴリズム処理として加算処理を有するもの、また、入力データを格納するために上記の実施例で定義した長さのメモリ領域を有する演算装置や演算処理であれば、本発明を適用することができる。
【０１２２】
［その他の実施例］
また、本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア（プログラム）を、ネットワーク又は各種記憶媒体を介してシステム或いは装置に供給し、そのシステムあるいは装置のコンピュータ（又はCPUやMPU等）がプログラムを読み出して実行する処理である。
【図１】
2012252281.tif 000003
【図２】
2012252281.tif 000004
【図３】
2012252281.tif 000005
【図４】
2012252281.tif 000006
【図５】
2012252281.tif 000007
【図６】
2012252281.tif 000008
【図８】
2012252281.tif 000009
【図９】
2012252281.tif 000010
【図１０】
2012252281.tif 000011
【図１１】
2012252281.tif 000012
【図１２】
2012252281.tif 000013
【図１３】
2012252281.tif 000014
【図１４】
2012252281.tif 000015
【図１５】
2012252281.tif 000016
【図１６】
2012252281.tif 000017
【図７】
2012252281.tif 000018