ハッシュ値生成装置、プログラム及びハッシュ値生成方法
【課題】 安全性の評価が可能なハッシュ関数を提供すること。
【解決手段】 入力されたメッセージをメッセージブロック化部１２２で、複数のメッセージブロックに分割し、ラウンド定数生成部１２３で生成されたラウンド定数を用いて、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成されたラウンド鍵を用いて、撹拌部１２６において、メッセージブロック毎にブロック暗号を用いて撹拌を行う。ブロック暗号においては、メッセージブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する。Ｆ関数においては、少なくとも非線形変換を含む変換を複数回行う。
【解決手段】 入力されたメッセージをメッセージブロック化部１２２で、複数のメッセージブロックに分割し、ラウンド定数生成部１２３で生成されたラウンド定数を用いて、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成されたラウンド鍵を用いて、撹拌部１２６において、メッセージブロック毎にブロック暗号を用いて撹拌を行う。ブロック暗号においては、メッセージブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する。Ｆ関数においては、少なくとも非線形変換を含む変換を複数回行う。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長のメッセージを入力として、特定の長さのハッシュ値を生成する関数である。
【０００３】
一般的に、ハッシュ関数は固定長のメッセージブロックを入力するブロック暗号から構成され、入力されたメッセージに対してブロック暗号化を繰り返し行うことで、メッセージの攪拌を行い、最終的にハッシュ値として出力する。ハッシュ関数の代表例としてはＳＨＡ−１、または、ＳＨＡ−２５６等のＳＨＡ−２ハッシュ族、などがある（非特許文献１参照）。
【０００４】
【非特許文献１】NIST FIPS 180-2, ”Secure Hash Standard”, 2002 August 1, pp. 9-23, http://csrc.nist.gov/publications /fips/fips180-2/fips180-2.pdf
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載のＳＨＡ−１は、ハッシュ関数が持つべき安全性である衝突耐性に問題があることが知られており、ＳＨＡ−２ハッシュ族についても、ＳＨＡ−１と類似した構造であることから、ハッシュ関数が持つべき安全性に問題を生ずる可能性がある。
【０００６】
そこで、本発明は、安全性の評価が可能なハッシュ関数を提供することを目的とする。
【課題を解決するための手段】
【０００７】
以上の課題を解決するため、本発明は、非線形変換を複数回行うＦ関数を備えるブロック暗号を用いてハッシュ値を生成する。
【０００８】
例えば、本発明は、メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置であって、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御部を備えること、を特徴とする。
【発明の効果】
【０００９】
以上のように、本発明によれば、安全性の評価が可能なハッシュ関数を提供することができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の第一の実施形態であるハッシュ値生成装置１００の概略図である。
【００１１】
ここで、本実施形態においては、５１２ビットのハッシュ値を生成するようにしている。
【００１２】
図示するように、ハッシュ値生成装置１００は、記憶部１１０と、制御部１２０と、入力部１３０と、出力部１４０と、を備える。
【００１３】
記憶部１１０は、初期値記憶領域１１１と、定数ラウンド値記憶領域１１２と、鍵ラウンド値記憶領域１１３と、平文ラウンド値記憶領域１１４と、算出値記憶領域１１５と、ハッシュ値記憶領域１１６と、を備える。
【００１４】
初期値記憶領域１１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。
【００１５】
本実施形態においては、ハッシュ値を生成する際の初期値として、定数ラウンド値の初期値と、算出値の初期値と、が記憶される。
【００１６】
ここで、定数ラウンド値の初期値は、例えば、ｃ（−１）＝0xffffffffffffffffffffffffffffffffといった定数が記憶される。
【００１７】
また、算出値の初期値は、Ｈ−１＝（Ｈ−１．０，Ｈ−１．１，・・・，Ｈ−１．７）であり、Ｈ−１．０＝0x0000000000000000、Ｈ−１．１＝0x0000000000000000、Ｈ−１．２＝0x0000000000000000、Ｈ−１．３＝0x0000000000000000、Ｈ−１．４＝0x0000000000000000、Ｈ−１．５＝0x0000000000000000、Ｈ−１．６＝0x0000000000000000、Ｈ−１．７＝0x0000000000000000、といった定数が記憶される。
【００１８】
なお、定数ラウンド値及び算出値の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【００１９】
定数ラウンド値記憶領域１１２には、各々のメッセージブロックにおけるラウンド毎の定数ラウンド値を特定する情報が格納される。
【００２０】
なお、本実施形態においては、定数ラウンド値は、後述するラウンド定数生成部１２３で生成される。
【００２１】
鍵ラウンド値記憶領域１１３には、各々のメッセージブロックにおけるラウンド毎の鍵ラウンド値を特定する情報が格納される。
【００２２】
なお、本実施形態においては、鍵ラウンド値は、後述する第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成される。
【００２３】
平文ラウンド値記憶領域１１４には、各々のメッセージブロックにおけるラウンド毎の平文ラウンド値を特定する情報が格納される。
【００２４】
なお、本実施形態においては、平文ラウンド値は、後述する撹拌部１２６で生成される。
【００２５】
算出値記憶領域１１５には、各々のメッセージブロックにおいて全てのラウンドを経て算出された算出値を特定する情報が格納される。
【００２６】
なお、本実施形態においては、算出値は、後述する全体制御部１２１で生成される。
【００２７】
ハッシュ値記憶領域には、全てのメッセージブロックにおいて全てのラウンドを経て算出されたハッシュ値を特定する情報が格納される。
【００２８】
なお、本実施形態においては、ハッシュ値は、後述する全体制御部１２１で生成される。
【００２９】
制御部１２０は、全体制御部１２１と、メッセージブロック化部１２２と、ラウンド定数生成部１２３と、第一ラウンド鍵生成部１２４と、第二ラウンド鍵生成部１２５と、撹拌部１２６と、を備える。
【００３０】
全体制御部１２１は、ハッシュ値生成装置１００における処理の全体を制御する。
【００３１】
特に、本実施形態においては、ハッシュ値を算出するメッセージをブロック化したメッセージブロックを管理する処理や、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４、第二ラウンド鍵生成部１２５及び撹拌部１２６でのラウンドを管理する処理を行う。
【００３２】
また、全体制御部１２１は、全てのラウンドを経て撹拌部１２６において算出された平文ラウンド値と、当該ラウンドでの処理の対象となったメッセージブロックと、の排他的論理和を算出することで、算出値を算出する。
【００３３】
さらに、全体制御部１２１は、全てのメッセージブロック及び全てのラウンドを経て撹拌部１２６において算出された平文ラウンド値と、最後のメッセージブロックと、の排他的論理和を算出することで、ハッシュ値を算出する。
【００３４】
メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージを予め定められたビット長のブロックに分割し、パディングを行う。
【００３５】
ここで、本実施形態では、ハッシュ値を算出する対象となるメッセージを５１２ビット毎のブロックに分割するようにしているが、このような態様に限定されるわけではない。
【００３６】
また、例えば、本実施形態におけるパディングは、以下のようにして行う。
【００３７】
まず、メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージのビット数が、５１２ビットで割り切れる場合には、当該メッセージを５１２ビット毎に分割することで各々のメッセージブロックを生成するとともに、メッセージブロックを追加して最後のメッセージブロックとする。
【００３８】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットに「１」、先頭ビットの次のビットから数えて３８３ビットまでに「０」、最後の１２８ビットにメッセージのビット長、を特定する情報を格納する。
【００３９】
次に、メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージのビット数が、５１２ビットで割り切れない場合には、当該メッセージを５１２ビット毎に分割することで各々のメッセージブロックを生成するとともに、分割した最後尾のメッセージブロックには最後のビットまで「０」を特定する情報を格納することで、５１２ビットにし、さらに、メッセージブロックを追加して最後のメッセージブロックとする。
【００４０】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットから数えて３８４ビットまでに「０」、最後の１２８ビットにメッセージのビット長、を特定する情報を格納する。
【００４１】
なお、本実施形態においては、ハッシュ値を算出するメッセージをＭとし、パディングにより、５１２ビットで割り切れるようなビット長にされたメッセージをＭ’とし、メッセージブロックの数をｋ＋１（ｋは１以上の整数）とし、各々のメッセージブロックをＭ’ｉ（ｉは、０≦ｉ≦ｋなる整数）とする。
【００４２】
ラウンド定数生成部１２３は、各ラウンドにおける定数ラウンド値及びラウンド定数を算出する。
【００４３】
本実施形態においては、ラウンド定数生成部１２３は、最初のラウンドの場合には初期値記憶領域１１１に記憶されている定数ラウンド値の初期値から、または、最初のラウンドではない場合には定数ラウンド値記憶領域１１２に記憶されている前ラウンドにおける定数ラウンド値から、線形変換関数ｆｃを用いて、各ラウンドにおける定数ラウンド値を算出する。
【００４４】
例えば、図２（線形変換関数ｆｃを示す概略図）に示すように、ラウンド定数生成部１２３は、前ラウンド（ｒ−１）の定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット（本実施形態では、上位６４ビット）と下位ビット（本実施形態では、下位６４ビット）を入れ替えることにより、今ラウンド（ｒ）の定数ラウンド値ｃ（ｒ）を算出する。
【００４５】
即ち、下記の（１）式及び（２）式に示されるようにして、前ラウンドの定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）から今ラウンドの定数ラウンド値ｃ（ｒ）を算出する。
【００４６】
【数１】
【００４７】
【数２】
【００４８】
ここで、（１）式及び（２）式において、ｔＨ及びｔＬは、それぞれ、定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット及び下位ビットである。
【００４９】
また、関数ｆＬは、線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いる。
【００５０】
一般に、ＬＦＳＲは多項式で決定されるが、ここではＬＦＳＲを決定する多項式ｇ（ｘ）を、下記の（３）式のように定義する。
【００５１】
【数３】
【００５２】
但し、ｇ（ｘ）は有限体ＧＦ（２）において定義される多項式である。
【００５３】
なお、関数ｆＬの擬似コードは、下記の（４）のように示される。
【００５４】
【数４】
【００５５】
ここで、「＜＜Ｘ」は、Ｘビットの左シフトを示し、「＞＞Ｙ」は、Ｙビットの右シフトを示し、「＾」は、ビット毎の排他的論理和を示し、「＆」は、ビット毎の論理積を示し、「｜」は、ビット毎の論理和を示す。また、ｈは、定数ラウンド値ｃ（ｒ−１）における上位ビット（上位６４ビット）、ｌは、定数ラウンド値ｃ（ｒ−１）における下位ビット（下位６４ビット）である。
【００５６】
そして、ラウンド定数生成部１２３は、算出したラウンド（ｒ）での定数ラウンド値ｃ（ｒ）の下位６４ビットを、第ｒラウンドにおけるラウンド定数Ｃ（ｒ）として、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５に出力する。
【００５７】
以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。
【００５８】
Ｃ（０）＝0x9916b42b1075d3c4、Ｃ（１）＝0xef660b4c6b97a9a1、Ｃ（２）＝0x645ad0ac41d74f11、Ｃ（３）＝0xdb7166e541d48abf、Ｃ（４）＝0x81f2b60293356a19、Ｃ（５）＝0x0b2cd041e8d806c6、Ｃ（６）＝0x71ba676d3737d203、Ｃ（７）＝0x5ac3fe60d882617f、Ｃ（８）＝0xd670690748b71e50、Ｃ（９）＝0x0de6b2578d83a9c6、Ｃ（１０）＝0x495850aeb6b42f1c、Ｃ（１１）＝0x379ac95e360ea718、Ｃ（１２）＝0x4388096e355a904b、Ｃ（１３）＝0xa81b9a1fa3d8e607、Ｃ（１４）＝0x1eb9d10b41021771、Ｃ（１５）＝0xa06e687e8f63981c、Ｃ（１６）＝0x7ae7442d04085dc5、Ｃ（１７）＝0x81b9a1fa3d8e6070、Ｃ（１８）＝0x8d745b60ffab5b2e、Ｃ（１９）＝0x7096388f8ddbfba6、Ｃ（２０）＝0x43a1d2e4854f16df、Ｃ（２１）＝0xd2c1168da307b8c4、Ｃ（２２）＝0x686e0046fab67746、Ｃ（２３）＝0x5b9dae851876b54c、Ｃ（２４）＝0xc7514acf0553f123、Ｃ（２５）＝0x7eef4ea7f5b2836d、Ｃ（２６）＝0x7bac60e8fac5e8b7、Ｃ（２７）＝0xeb24ce2c42a25be8、Ｃ（２８）＝0x8858c877049d8ee6、Ｃ（２９）＝0xbc0acc029ee139fd、Ｃ（３０）＝0x216321dc12763b99、Ｃ（３１）＝0xf02b300a7b84e7f4、Ｃ（３２）＝0x858c877049d8ee65、Ｃ（３３）＝0xa6458bfd0199b3ea、Ｃ（３４）＝0x6042a2a65c81c3f2、Ｃ（３５）＝0xef6690937d84b5cf、Ｃ（３６）＝0x91937e2ae66f5995、Ｃ（３７）＝0xdb7309991998fb06、Ｃ（３８）＝0x303d47cce25f1c32、Ｃ（３９）＝0x7d55d2d7f20bba44、Ｃ（４０）＝0xc0f51f33897c70c8、Ｃ（４１）＝0x93be008b27a4c52a、Ｃ（４２）＝0x134d887db199957d、Ｃ（４３）＝0x4ef8022c9e9314a8、Ｃ（４４）＝0x4d3621f6c66655f4、Ｃ（４５）＝0x5d09436695c67e9b、Ｃ（４６）＝0x244173688df1018c、Ｃ（４７）＝0x12cc464eb893d657、Ｃ（４８）＝0xe77572c54c267c57、Ｃ（４９）＝0x3d41a65d99ad233a、Ｃ（５０）＝0x8d4c3fa6a4f1a700、Ｃ（５１）＝0xf506997666b48ce9、Ｃ（５２）＝0x3530fe9a93c69c01、Ｃ（５３）＝0xb2f32e0d75581f9f、Ｃ（５４）＝0xa2b3450d34f80a62、Ｃ（５５）＝0xbdbc0752ae82041a、Ｃ（５６）＝0xfcbdab53a80253ee、Ｃ（５７）＝0x8080a22dc1ea6a0e、Ｃ（５８）＝0xe26f59fd346119e5、Ｃ（５９）＝0x020288b707a9a839、Ｃ（６０）＝0xef542c203e0e4baf、Ｃ（６１）＝0x7e7a9dbb6544da82、Ｃ（６２）＝0xadc944336c5178e0、Ｃ（６３）＝0x9f033d397a994632、Ｃ（６４）＝0xc155afaacaa799e6、Ｃ（６５）＝0x0a7c4b82918762ae、Ｃ（６６）＝0x15cf4a18bef631c4、Ｃ（６７）＝0x29f12e0a461d8ab8、Ｃ（６８）＝0x573d2862fbd8c710、Ｃ（６９）＝0xa7c4b82918762ae0、Ｃ（７０）＝0x3a1dea5f00e9307a、Ｃ（７１）＝0xe9625fc31a3ad1e7、Ｃ（７２）＝0x9e07161b7846bb8e、Ｃ（７３）＝0xb5108bbffc8311c1、Ｃ（７４）＝0x781c586de11aee39、Ｃ（７５）＝0xd4422efff20c4704、Ｃ（７６）＝0x86982a636be194de、Ｃ（７７）＝0x41914f4c5c594a4d、Ｃ（７８）＝0x1a60a98daf865378、Ｃ（７９）＝0x60ac76e59eef050f、Ｃ（８０）＝0x1ff21951c5fb3787、Ｃ（８１）＝0x92282f25efd44260、Ｃ（８２）＝0x7fc8654717ecde1d、Ｃ（８３）＝0x48a0bc97bf510980、Ｃ（８４）＝0x99c8dec8b039544f、Ｃ（８５）＝0x321b06ed692c705d、Ｃ（８６）＝0x67237b22c0e5513c、Ｃ（８７）＝0xc86c1bb5a4b1c174、Ｃ（８８）＝0xfa64a75fec1f68ca、Ｃ（８９）＝0x31299a6506af538d、Ｃ（９０）＝0x8f7bd6ab5ff78f13、Ｃ（９１）＝0xb2d6d6f3615f3452、Ｃ（９２）＝0x4b9fe5ca043c462a、Ｃ（９３）＝0xbd2be4aafe9eab2f、Ｃ（９４）＝0x3ee6639b84994ef5、Ｃ（９５）＝0xf4af92abfa7aacbc。
【００５９】
第一ラウンド鍵生成部１２４は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【００６０】
例えば、第一ラウンド鍵生成部１２４による鍵ラウンド値の算出は、図３（第一鍵ラウンド値変換関数ｆｋの概略図）に示す第一鍵ラウンド値変換関数ｆｋを用いて行われる。
【００６１】
図示するように、第一鍵ラウンド値変換関数ｆｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（ここでは、各々６４ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【００６２】
具体的には、第一鍵ラウンド値変換関数ｆｋでは、まず、第一ラウンド鍵生成部１２４が、鍵ラウンド値記憶領域１１３に記憶されている第ｒ−１ラウンドの鍵ラウンド値（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を、ｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）に８等分する。
【００６３】
次に、第一ラウンド鍵生成部１２４は、第ｒ−１ラウンドの鍵ラウンド値の内のｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、をそれぞれ第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、とする。
【００６４】
次に、第一ラウンド鍵生成部１２４は、ラウンド定数生成部１２３で生成されたラウンド定数Ｃ（ｒ）及び第ｒ−１ラウンドのラウンド鍵の内のｋ４（ｒ−１）の排他的論理和の値ａＨと、第ｒ−１ラウンドのラウンド鍵の内のｋ５（ｒ−１）の値ａＬと、を連結した値ａをＦ関数である関数Ｆｋに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｂＨ（ｂＨ＝Ｆｋ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｂＬ（ｂＬ＝Ｆｋ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｌ）と、を算出する。
【００６５】
そして、第一ラウンド鍵生成部１２４は、値ｂＨと、第ｒ−１ラウンドの鍵ラウンド値の内のｋ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ０（ｒ）とする。
【００６６】
また、第一ラウンド鍵生成部１２４は、値ｂＬと、第ｒ−１ラウンドの鍵ラウンド値の内のｋ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ１（ｒ）とする。
【００６７】
次に、第一ラウンド鍵生成部１２４は、第ｒ−１ラウンドの鍵ラウンド値の内のｋ４（ｒ−１）、ｋ５（ｒ−１）を、それぞれ第ｒラウンドの鍵ラウンド値ｋ６（ｒ）、ｋ７（ｒ）とする。
【００６８】
そして、第一ラウンド鍵生成部１２４は、以上のようにして算出したｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）を連結して第ｒラウンドの鍵ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて鍵ラウンド値記憶領域１１３に記憶する。
【００６９】
また、第一ラウンド鍵生成部１２４は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を、第ｒラウンドのラウンド鍵Ｋ（ｒ）として、撹拌部１２６に出力する。
【００７０】
次に、第一ラウンド鍵生成部１２４で使用するＦ関数である関数ＦＫについて説明する。
【００７１】
関数ＦＫは、下記の（５）式に示すように、非線形変換γＫと、線形変換λｋと、の合成変換を行う関数である。
【００７２】
【数５】
【００７３】
また、線形変換λｋは、バイト置換πＫと、行列変換θＫと、の合成変換である。
【００７４】
ここで、関数ＦＫへの入力をＸ、関数ＦＫからの出力をＹとして説明する。
【００７５】
本実施形態においては、Ｘ及びＹは、１２８ビットのデータである。
【００７６】
まず、非線形変換γＫでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ１５）に分割して、分割した各々のサブデータを、下記の（６）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【００７７】
【数６】
【００７８】
なお、置換テーブルＳｂｏｘは、例えば、下記の（７）で示される。
【００７９】
【数７】
【００８０】
次に、行列変換θＫでは、上記の非線形変換γＫでの変換後のサブデータ（ｓ’０，ｓ’１，・・・，ｓ’１５）を８行２列の行列にして、下記の（１０）式に示すように、変換行列Ａとの乗算を行うことで、変換を行う。ここで、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”１５とする。乗算は、有限体ＧＦ（２８）上での乗算である。有限体ＧＦ（２＾８）は、下記の（８）式及び（９）式を満たす。
【００８１】
【数８】
【００８２】
【数９】
【００８３】
【数１０】
【００８４】
ここで、変換行列Ａは、ある列を入力列とし、当該入力列に対して変換行列Ａによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、９個以上になるような変換であれば、どのような変換行列を用いてもよい。
【００８５】
次に、バイト置換πＫでは、下記の（１１）式に示すように、行列変換θＫで変換されたサブデータ（ｓ”０，ｓ”１，・・・，ｓ”１５）のうちの半分のデータの入れ替えを行う。なお、変換後のサブデータをｙ０，ｙ１，・・・，ｙ１５とする。
【００８６】
【数１１】
【００８７】
そして、以上のようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を（１２）式のように連結することで、関数ＦＫの出力Ｙとする。
【００８８】
【数１２】
【００８９】
以上の関数ＦＫでは、後述する関数ＦＲと比較して、一つの入力に対して一回の処理で出力を行うため、計算量が少なくてすみ、軽実装が可能となる。
【００９０】
図１に戻り、第二ラウンド鍵生成部１２５は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【００９１】
例えば、第二ラウンド鍵生成部１２５による鍵ラウンド値の算出は、図４（第二鍵ラウンド値変換関数ｆ’Ｋの概略図）に示す第二鍵ラウンド値変換関数ｆ’Ｋを用いて行われる。
【００９２】
図示するように、第二鍵ラウンド値変換関数ｆ’Ｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（ここでは、各々６４ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【００９３】
具体的には、第二鍵ラウンド値変換関数ｆ’Kでは、まず、第二ラウンド鍵生成部１２５が、鍵ラウンド値記憶領域１１３に記憶されている第ｒ−１ラウンドの鍵ラウンド値（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値）を、ｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）に８等分する。
【００９４】
次に、第二ラウンド鍵生成部１２５は、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、をそれぞれ第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、とする。
【００９５】
次に、第二ラウンド鍵生成部１２５は、ラウンド定数生成部１２３で生成されたラウンド定数Ｃ（ｒ）及び第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ４（ｒ−１）の排他的論理和である値ａ’Ｈと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ５（ｒ−１）の値ａ’Ｌと、を連結した値ａ’をＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｂ’Ｈ（ｂ’Ｈ＝ＦＲ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｂ’Ｌ（ｂＬ＝ＦＲ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｌ）と、を算出する。
【００９６】
そして、第二ラウンド鍵生成部１２５は、値ｂ’Ｈと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ０（ｒ）とする。
【００９７】
また、第二ラウンド鍵生成部１２５は、値ｂ’Ｌと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ１（ｒ）とする。
【００９８】
次に、第二ラウンド鍵生成部１２５は、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ４（ｒ−１）、ｋ５（ｒ−１）を、それぞれ第ｒラウンドの鍵ラウンド値ｋ６（ｒ）、ｋ７（ｒ）とする。
【００９９】
そして、第二ラウンド鍵生成部１２５は、以上のようにして算出したｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）を連結して第ｒラウンドの鍵ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて鍵ラウンド値記憶領域１１３に記憶する。
【０１００】
また、第二ラウンド鍵生成部１２５は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を、第ｒラウンドのラウンド鍵Ｋ（ｒ）として、撹拌部１２６に出力する。
【０１０１】
次に、第二ラウンド鍵生成部１２５で使用するＦ関数である関数ＦＲについて説明する。
【０１０２】
関数ＦＲは、下記の（１３）式に示すように、非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段）行う関数である。
【０１０３】
【数１３】
【０１０４】
ここで、関数ＦＲへの入力をＸ、関数ＦＲからの出力をＹとして説明する。本実施形態においては、Ｘ及びＹは、１２８ビットのデータである。
【０１０５】
まず、非線形変換γＲでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ１５）に分割して、分割した各々のサブデータを、下記の（１４）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【０１０６】
【数１４】
【０１０７】
なお、置換テーブルＳｂｏｘは、例えば、上記の（７）で示されるものを使用すればよい。
【０１０８】
次に、バイト置換πＲでは、（１５）式に示すように、非線形変換γＲで変換されたサブデータ（ｓ’０，ｓ’１，・・・，ｓ’１５）を４行４列の行列として、各々の列に含まれる各々の行のデータが各々異なる列に配置されるように、データの入れ替えを行う。なお、（１５）式は一例であって、各々の列に含まれる各々の行のデータが各々異なる列に配置されるものであれば、他の入れ替え方式を採用することも可能である。
【０１０９】
また、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”１５とする。
【０１１０】
【数１５】
【０１１１】
次に、行列変換θＲでは、下記の（１６）式に示すように、上記のバイト置換πＲでの変換後のサブデータ（ｓ”０，ｓ”１，・・・，ｓ”１５）を要素とする４行４列の行列と、変換行列Ｂと、の有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｙ０，ｙ１，・・・，ｙ１５とする。
【０１１２】
【数１６】
【０１１３】
ここで、変換行列Ｂは、ある列を入力列とし、当該入力列に対して変換行列Ｂによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、５個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０１１４】
そして、このようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を、（１７）式に示すように、サブデータ（ｓ０，ｓ１，・・・，ｓ１５）として、非線形変換γＲ、バイト置換πＲ及び行列変換θＲによる変換を３回（合計４回）行うことで、算出されるサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を（１７）式のように連結することで、関数ＦＲの出力Ｙとする。
【０１１５】
【数１７】
【０１１６】
以上の関数ＦＲでは、前述の関数ＦＫと比較して、一つの入力に対して４回の処理で出力を行うため、安全性を高めることができる。なお、この４回という回数については、適宜変更可能である。
【０１１７】
図１に戻り、撹拌部１２６は、各ラウンドにおける平文ラウンド値を算出する処理を行う。
【０１１８】
例えば、撹拌部１２６による平文ラウンド値の算出は、図５（平文ラウンド値変換関数ｆＲの概略図）に示す平文ラウンド値変換関数ｆＲを用いて行われる。
【０１１９】
図示するように、平文ラウンド値変換関数ｆＲは、第ｒ−１ラウンドの平文ラウンド値ｘ（ｒ−１）（但し、ｒ＝０の場合は、メッセージブロック化部１２２でブロック化されたメッセージブロックＭ’ｉ）を８分割（ここでは、各々６４ビット）した分割データであるｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）を、それぞれ、ｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの平文ラウンド値ｘ（ｒ）を生成する関数である。
【０１２０】
具体的には、平文ラウンド値変換関数ｆＲでは、まず、撹拌部１２６が、平文ラウンド値記憶領域１１４に記憶されている第ｒ−１ラウンドの平文ラウンド値（但し、ｒ＝０の場合は、メッセージブロック化部１２２でブロック化されたメッセージブロックＭ’ｉ）を、ｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）に８等分する。
【０１２１】
次に、撹拌部１２６は、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、をそれぞれ第ｒラウンドの平文ラウンド値の内のｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、とする。
【０１２２】
次に、撹拌部１２６は、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成されたラウンド鍵Ｋ（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨと（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｈ）、下位ビット（ここでは、下位６４ビット）の値ｑＬと（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｌ）、を算出する。
【０１２３】
そして、撹拌部１２６は、値ｑＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド鍵のｘ０（ｒ）とする。
【０１２４】
また、撹拌部１２６は、値ｑＬと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド値のｘ１（ｒ）とする。
【０１２５】
次に、撹拌部１２６は、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）、ｘ５（ｒ−１）を、それぞれ第ｒラウンドの平文ラウンド値ｘ６（ｒ）、ｘ７（ｒ）とする。
【０１２６】
そして、撹拌部１２６は、以上のようにして算出したｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）を連結して第ｒラウンドの平文ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて平文ラウンド値記憶領域１１４に記憶する。
【０１２７】
撹拌部１２６で使用するＦ関数である関数ＦＲについては、上述の（１３）式で示されているものと同様であるため、説明を省略する。
【０１２８】
入力部１３０は、情報の入力を受け付ける。
【０１２９】
出力部１４０は、情報を出力する。
【０１３０】
以上に記載したハッシュ値生成装置１００は、例えば、図６（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【０１３１】
例えば、記憶部１１０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、制御部１２０は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、入力部１３０は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、出力部１４０は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【０１３２】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【０１３３】
次に、図７（ハッシュ値の算出処理を示す概略図）を用いて、ハッシュ値生成装置１００がハッシュ値を算出する処理の概略を示す。
【０１３４】
まず、ハッシュ値生成装置１００では、入力部１３０を介して、ハッシュ値を生成するメッセージＭの入力を受け付け、ハッシュ値生成装置１００の全体制御部１２１が、メッセージブロック化部１２２にメッセージＭを入力する。
【０１３５】
そして、メッセージブロック化部１２２では、メッセージＭをパディングして、５１２ビット毎のメッセージブロック（Ｍ’０，・・・，Ｍ’ｋ；ｋは１以上の整数）に分割する。
【０１３６】
次に、全体制御部１２１は、初期値記憶領域１１１に記憶されている算出値の初期値Ｈ−１と、メッセージブロック化部１２２でブロック化されたメッセージブロックＭｉ’のうち、最初のメッセージブロックＭ’０と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ０を算出する。
【０１３７】
ここで、第一ブロック暗号ｆＥを用いた処理は、後述するように、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４及び撹拌部１２６で行われる。
【０１３８】
そして、全体制御部１２１は、算出した平文ラウンド値ｈ０と、メッセージブロックＭ’０と、の排他的論理和を算出することで、算出値を求め、求めた算出値と、次のメッセージブロックＭ’１と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ１を算出する。なお、算出された算出値については、算出値記憶領域１１５に記憶される。
【０１３９】
このような処理を、最後のメッセージブロックＭ’ｋの直前のメッセージブロックＭ’ｋ−１まで繰り返すことで、平文ラウンド値ｈｋ−１を算出する。
【０１４０】
そして、全体制御部１２１は、平文ラウンド値ｈｋ−１と、メッセージブロックＭ’ｋ−１と、の排他的論理和で算出される算出値と、最後のメッセージブロックＭ’ｋと、を第二ブロック暗号ｆ’Ｅに入力することにより、平文ラウンド値ｈｋを算出する。
【０１４１】
ここで、第二ブロック暗号ｆ’Ｅを用いた処理は、後述するように、ラウンド定数生成部１２３、第二ラウンド鍵生成部１２５及び撹拌部１２６で行われる。
【０１４２】
そして、全体制御部１２１は、平文ラウンド値ｈｋと、最後のメッセージブロックＭ’ｋと、の排他的論理和でハッシュ値Ｈｋを算出する。
【０１４３】
このようなハッシュ値Ｈｋは、ハッシュ値記憶領域１１６に記憶される。
【０１４４】
なお、本発明におけるハッシュ値の算出処理（方法）は、図７に示した処理（方法）に限定されるわけではなく、第一ブロック暗号ｆＥ又は、第二ブロック暗号ｆ’Ｅの少なくとも何れか一方を利用すれば、どのようなものであってもよく。
【０１４５】
図８は、第一ブロック暗号ｆＥでの処理を示す概略図である。
【０１４６】
まず、ラウンド定数生成部１２３は、初期値記憶領域１１１に記憶されている定数ラウンド値の初期値を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝０における定数ラウンド値ｃ（０）を算出し、定数ラウンド値ｃ（０）の下位６４ビットを、ラウンドｒ＝０におけるラウンド定数Ｃ（０）として算出する。
【０１４７】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（０）を定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（０）を第一ラウンド鍵生成部１２４に出力する。
【０１４８】
次に、第一ラウンド鍵生成部１２４は、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉがメッセージブロックＭ’０の場合には、初期値記憶領域１１１に記憶されている算出値の初期値を取得して、一方、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉがメッセージブロックＭ’０ではない場合には、算出値記憶領域１１５に記憶されている前メッセージブロックＭ’ｉにおける算出値を取得して、図３に示すような第一鍵ラウンド値変換関数ｆKを用いた処理を行うことにより、ｒ＝０における鍵ラウンド値ｋ（０）を算出し、また、鍵ラウンド値ｋ（０）の内のｋ３（０）を、ラウンドｒ＝０のラウンド鍵Ｋ（０）として算出する。
【０１４９】
そして、第一ラウンド鍵生成部１２４は、鍵ラウンド値ｋ（０）を鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（０）を撹拌部１２６に出力する。
【０１５０】
次に、撹拌部１２６は、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉを取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ｒ＝０における平文ラウンド値ｘ（０）を算出し、平文ラウンド値記憶領域１１４に記憶する。
【０１５１】
以上で、第０ラウンドの処理を終了する。
【０１５２】
次に、ラウンド定数生成部１２３は、定数ラウンド値記憶領域１１２に記憶されている定数ラウンド値ｃ（０）を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝１における定数ラウンド値ｃ（１）を算出し、定数ラウンド値ｃ（１）の下位６４ビットを、ラウンドｒ＝１におけるラウンド定数Ｃ（１）として算出する。
【０１５３】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（１）を、定数ラウンド値ｃ（０）に置き換えて（いわゆる上書きして）、定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（１）を第一ラウンド鍵生成部１２４に出力する。
【０１５４】
次に、第一ラウンド鍵生成部１２４は、鍵ラウンド値記憶領域１１３に記憶されている鍵ラウンド値ｋ（０）を取得して、図３に示すような第一鍵ラウンド値変換関数ｆKを用いた処理を行うことにより、ラウンドｒ＝１における鍵ラウンド値ｋ（１）を算出し、また、鍵ラウンド値ｋ（１）の内のｋ３（１）を、ラウンドｒ＝１のラウンド鍵Ｋ（１）として算出する。
【０１５５】
そして、第一ラウンド鍵生成部１２４は、算出した鍵ラウンド値ｋ（１）を、鍵ラウンド値ｋ（０）に置き換えて（いわゆる上書きして）、鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（１）を撹拌部１２６に出力する。
【０１５６】
次に、撹拌部１２６は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値ｘ（０）を取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ラウンドｒ＝１における平文ラウンド値ｘ（１）を算出し、算出した平文ラウンド値ｘ（１）を、平文ラウンド値ｘ（０）に置き換えて（いわゆる上書きして）、平文ラウンド値記憶領域１１４に記憶する。
【０１５７】
以上で、第１ラウンドの処理を終了する。
【０１５８】
そして、以上に記載した第１ラウンドでの処理と同様の処理を、所定のラウンド（ここでは、第３１ラウンド）まで繰り返すことで、第一ブロック暗号ｆＥでの処理を終了する。
【０１５９】
図９は、第二ブロック暗号ｆ’Ｅでの処理を示す概略図である。
【０１６０】
まず、ラウンド定数生成部１２３は、初期値記憶領域１１１に記憶されている定数ラウンド値の初期値を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝０における定数ラウンド値ｃ（０）を算出し、定数ラウンド値ｃ（０）の下位６４ビットを、ラウンドｒ＝０におけるラウンド定数Ｃ（０）として算出する。
【０１６１】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（０）を定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（０）を第二ラウンド鍵生成部１２５に出力する。
【０１６２】
次に、第二ラウンド鍵生成部１２５は、算出値記憶領域１１５に記憶されている前メッセージブロックＭ’ｋ−１における算出値を取得して、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いた処理を行うことにより、ｒ＝０における鍵ラウンド値ｋ（０）を算出し、また、鍵ラウンド値ｋ（０）の内のｋ３（０）を、ラウンドｒ＝０のラウンド鍵Ｋ（０）として算出する。
【０１６３】
そして、第二ラウンド鍵生成部１２５は、鍵ラウンド値ｋ（０）を鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（０）を撹拌部１２６に出力する。
【０１６４】
次に、撹拌部１２６は、第二ブロック暗号ｆ’Ｅに入力されたメッセージブロックＭ’ｋを取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ｒ＝０における平文ラウンド値ｘ（０）を算出し、平文ラウンド値記憶領域１１４に記憶する。
【０１６５】
以上で、第０ラウンドの処理を終了する。
【０１６６】
次に、ラウンド定数生成部１２３は、定数ラウンド値記憶領域１１２に記憶されている定数ラウンド値ｃ（０）を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝１における定数ラウンド値ｃ（１）を算出し、定数ラウンド値ｃ（１）の下位６４ビットを、ラウンドｒ＝１におけるラウンド定数Ｃ（１）として算出する。
【０１６７】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（１）を、定数ラウンド値ｃ（０）に置き換えて（いわゆる上書きして）、定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（１）を第二ラウンド鍵生成部１２５に出力する。
【０１６８】
次に、第二ラウンド鍵生成部１２５は、鍵ラウンド値記憶領域１１３に記憶されている鍵ラウンド値ｋ（０）を取得して、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いた処理を行うことにより、ラウンドｒ＝１における鍵ラウンド値ｋ（１）を算出し、また、鍵ラウンド値ｋ（１）の内のｋ３（１）を、ラウンドｒ＝１のラウンド鍵Ｋ（１）として算出する。
【０１６９】
そして、第二ラウンド鍵生成部１２５は、算出した鍵ラウンド値ｋ（１）を、鍵ラウンド値ｋ（０）に置き換えて（いわゆる上書きして）、鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（１）を撹拌部１２６に出力する。
【０１７０】
次に、撹拌部１２６は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値ｘ（０）を取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ラウンドｒ＝１における平文ラウンド値ｘ（１）を算出し、算出した平文ラウンド値ｘ（１）を、平文ラウンド値ｘ（０）に置き換えて（いわゆる上書きして）、平文ラウンド値記憶領域１１４に記憶する。
【０１７１】
以上で、第１ラウンドの処理を終了する。
【０１７２】
以上に記載した第１ラウンドでの処理と同様の処理を、所定のラウンド（ここでは、第３１ラウンド）まで繰り返すことで、第二ブロック暗号ｆ’Ｅでの処理を終了する。
【０１７３】
図１０は、ハッシュ値生成装置１００におけるハッシュ値の生成処理を示すフローチャートである。
【０１７４】
まず、ハッシュ値生成装置１００は、入力部１３０を介してハッシュ値を生成する元となるメッセージＭを取得する（Ｓ１０）。
【０１７５】
次に、メッセージブロック化部１２２は、入出部１３０を介して取得したメッセージを予め定められたデータ長に分割することによりｋ＋１個のメッセージブロックＭ’ｉを生成する（Ｓ１１）。ここで、本実施形態においては、メッセージを５１２ビットのデータ長に分割するようにしている。
【０１７６】
次に、全体制御部１２１は、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３、平文ラウンド値記憶領域１１４、算出値記憶領域１１５及びハッシュ値記憶領域１１６に記憶されている情報のリセットを行う（Ｓ１２）。具体的には、全てのビット値を「０」にする。
【０１７７】
次に、全体制御部１２１は、メッセージブロックのカウンタであるメッセージカウンタｉの値を初期化する（Ｓ１３）。ここでは、メッセージカウンタｉの値に「０」を代入する。
【０１７８】
次に、全体制御部１２１は、メッセージカウンタｉの値が、ｉ＝ｋとなっているか否かを判断する（Ｓ１４）。
【０１７９】
ステップＳ１４で、ｉ＝ｋとなっていない場合には（ステップＳ１４でＮｏ）、ステップＳ１５に進み、ｉ＝ｋとなっている場合には（ステップＳ１４でＹｅｓ）、ステップＳ２１に進む。
【０１８０】
ステップＳ１５では、全体制御部１２１は、ラウンドのカウンタであるラウンドカウンタｒに初期値「０」を代入する。
【０１８１】
次に、全体制御部１２１は、ラウンドカウンタｒの値が、予め定められた第一ラウンド数（ここでは、ＲＯＵＮＤ ＮＵＭ＝３１）に対して、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ１６）。ステップＳ１６において、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にある場合には、ステップＳ１９に進み、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にない場合には、ステップＳ１７に進む。
【０１８２】
ステップＳ１７では、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４及び撹拌部１２６において、第一ブロック暗号ｆＥを用いて、定数ラウンド値、鍵ラウンド値及び平文ラウンド値を算出し、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３及び平文ラウンド値記憶領域１１４に記憶されている情報を更新する。
【０１８３】
次に、全体制御部１２１は、ラウンドカウンタｒの値に「１」をインクリメントして、ステップＳ１６に戻って処理を繰り返す。
【０１８４】
また、ステップＳ１９では、全体制御部１２１は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値と、メッセージブロックＭ’ｉと、の排他的論理和を算出することで算出値を算出し、算出した算出値で算出値記憶領域１１５に記憶されている情報を更新する。
【０１８５】
そして、全体制御部１２１は、メッセージカウンタｉの値に「１」をインクリメントして（Ｓ２０）、ステップＳ１４に戻って処理を繰り返す。
【０１８６】
一方、ステップＳ１４において、ｉ＝ｋとなっている場合には（ステップＳ１４でＹｅｓ）、ステップＳ２１において、全体制御部１２１は、ラウンドのカウンタであるラウンドカウンタｒに初期値「０」を代入する。
【０１８７】
次に、全体制御部１２１は、ラウンドカウンタｒの値が、予め定められた第二ラウンド数（ここでは、ＲＯＵＮＤ ＮＵＭ＝３１）に対して、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ２２）。
【０１８８】
そして、ステップＳ２２において、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にある場合には（ステップＳ２２でＹｅｓ）、ステップＳ２５に進み、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にない場合には（ステップＳ２２でＮｏ）、ステップＳ２３に進む。
【０１８９】
ステップＳ２３では、ラウンド定数生成部１２３、第二ラウンド鍵生成部１２５及び撹拌部１２６において、第二ブロック暗号ｆ’Ｅを用いて、定数ラウンド値、鍵ラウンド値及び平文ラウンド値を算出し、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３及び平文ラウンド値記憶領域１１４に記憶されている情報を更新する。
【０１９０】
次に、全体制御部１２１は、ラウンドカウンタｒの値に「１」をインクリメントして（Ｓ２４）、ステップＳ２２に戻って処理を繰り返す。
【０１９１】
また、ステップＳ２５では、全体制御部１２１は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値と、メッセージブロックＭ’ｋと、の排他的論理和を算出することでハッシュ値を算出し、ハッシュ値記憶領域１１６に記憶されている情報を更新する。
【０１９２】
以上のように、本実施形態においては、５１２ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができる。
【０１９３】
図１１は、本発明の第二の実施形態であるハッシュ値生成装置２００の概略図である。
【０１９４】
ここで、本実施形態においては、２５６ビットのハッシュ値を生成するようにしている。
【０１９５】
図示するように、ハッシュ値生成装置２００は、記憶部２１０と、制御部２２０と、入力部１３０と、出力部１４０と、を備え、第一の実施形態と比較して、記憶部２１０及び制御部２２０が異なっているため、以下これらの異なっている点に関連する事項について説明する。
【０１９６】
記憶部２１０は、初期値記憶領域２１１と、定数ラウンド値記憶領域１１２と、鍵ラウンド値記憶領域１１３と、平文ラウンド値記憶領域１１４と、算出値記憶領域１１５と、ハッシュ値記憶領域１１６と、を備え、第一の実施形態と比較して、初期値記憶領域２１１に記憶されている情報が異なっているため、以下この異なっている点に関連する事項について説明する。
【０１９７】
初期値記憶領域２１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。
【０１９８】
本実施形態においては、ハッシュ値を生成する際の初期値として、定数ラウンド値の初期値と、算出値の初期値と、が記憶される。
【０１９９】
ここで、定数ラウンド値の初期値は、例えば、ｃ（−１）＝0xffffffffffffffffといった定数が記憶される。
【０２００】
また、算出値の初期値は、Ｈ−１＝（Ｈ−１．０，Ｈ−１．１，・・・，Ｈ−１．７）であり、Ｈ−１．０＝0x00000000、Ｈ−１．１＝0x00000000、Ｈ−１．２＝0x00000000、Ｈ−１．３＝0x00000000、Ｈ−１．４＝0x00000000、Ｈ−１．５＝0x00000000、Ｈ−１．６＝0x00000000、Ｈ−１．７＝0x00000000、といった定数が記憶される。
【０２０１】
なお、定数ラウンド値及び算出値の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【０２０２】
制御部２２０は、全体制御部２２１と、メッセージブロック化部２２２と、ラウンド定数生成部２２３と、第一ラウンド鍵生成部２２４と、第二ラウンド鍵生成部２２５と、撹拌部２２６と、を備える。
【０２０３】
全体制御部２２１は、ハッシュ値生成装置２００における処理の全体を制御する。
【０２０４】
特に、本実施形態においては、ハッシュ値を算出するメッセージをブロック化したメッセージブロックを管理する処理や、ラウンド定数生成部２２３、第一ラウンド鍵生成部２２４、第二ラウンド鍵生成部２２５及び撹拌部２２６でのラウンドを管理する処理を行う。
【０２０５】
また、全体制御部２２１は、全てのラウンドを経て撹拌部２２６において算出された平文ラウンド値と、当該ラウンドでの処理の対象となったメッセージブロックと、の排他的論理和を算出することで、算出値を算出する。
【０２０６】
さらに、全体制御部２２１は、全てのメッセージブロック及び全てのラウンドを経て撹拌部２２６において算出された平文ラウンド値と、最後のメッセージブロックと、の排他的論理和を算出することで、ハッシュ値を算出する。
【０２０７】
メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージを予め定められたビット長のブロックに分割し、パディングを行う。
【０２０８】
ここで、本実施形態では、ハッシュ値を算出する対象となるメッセージを２５６ビット毎のブロックに分割するようにしているが、このような態様に限定されるわけではない。
【０２０９】
また、例えば、本実施形態におけるパディングは、以下のようにして行う。
【０２１０】
まず、メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージのビット数が、２５６ビットで割り切れる場合には、当該メッセージを２５６ビット毎に分割することで各々のメッセージブロックを生成するとともに、メッセージブロックを追加して最後のメッセージブロックとする。
【０２１１】
そして、メッセージブロック化部２２２は、この最後のメッセージブロックにおいて、先頭ビットに「１」、先頭ビットの次のビットから数えて１９１ビットまでに「０」、最後の６４ビットにメッセージのビット長、を特定する情報を格納する。
【０２１２】
次に、メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージのビット数が、２５６ビットで割り切れない場合には、当該メッセージを２５６ビット毎に分割することで各々のメッセージブロックを生成するとともに、分割した最後尾のメッセージブロックには最後のビットまで「０」を特定する情報を格納することで、２５６ビットにし、さらに、メッセージブロックを追加して最後のメッセージブロックとする。
【０２１３】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットから数えて１９２ビットまでに「０」、最後の６４ビットにメッセージのビット長、を特定する情報を格納する。
【０２１４】
なお、本実施形態においては、ハッシュ値を算出するメッセージをＭとし、パディングにより、２５６ビットで割り切れるようなビット長にされたメッセージをＭ’とし、メッセージブロックの数をｋ＋１（ｋは１以上の整数）とし、各々のメッセージブロックをＭ’ｉ（ｉは、０≦ｉ≦ｋなる整数）とする。
【０２１５】
ラウンド定数生成部２２３は、各ラウンドにおける定数ラウンド値及びラウンド定数を算出する。
【０２１６】
本実施形態においても、ラウンド定数生成部２２３は、最初のラウンドの場合には、初期値記憶領域２１１に記憶されている定数ラウンド値の初期値から、または、最初のラウンドではない場合には、定数ラウンド値記憶領域２１２に記憶されている前ラウンドにおける定数ラウンド値から、線形変換関数ｆｃを用いて、各ラウンドにおける定数ラウンド値を算出する。
【０２１７】
例えば、図２に示すように、ラウンド定数生成部２２３は、前ラウンド（ｒ−１）の定数ラウンド値ｃ（ｒ−１）（ｒ＝０のときは、定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット（本実施形態では、上位３２ビット）と下位ビット（本実施形態では、下位３２ビット）を入れ替えることにより、今ラウンド（ｒ）の定数ラウンド値ｃ（ｒ）を算出する。
【０２１８】
即ち、上述の（１）式及び（２）式に示されるようにして、前ラウンドの定数ラウンド値ｃ（ｒ−１）（ｒ＝０のときは、定数ラウンド値の初期値）から今ラウンドの定数ラウンド値ｃ（ｒ）を算出する。
【０２１９】
また、関数ｆＬは、線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いる。
【０２２０】
一般に、ＬＦＳＲは多項式で決定されるが、ここではＬＦＳＲを決定する多項式ｇ（ｘ）を、下記の（１８）式のように定義する。
【０２２１】
【数１８】
【０２２２】
但し、ｇ（ｘ）は有限体ＧＦ（２）において定義される多項式である。
【０２２３】
なお、関数ｆＬの擬似コードは、下記の（１９）のように示される。
【０２２４】
【数１９】
【０２２５】
ここで、「＜＜Ｘ」は、Ｘビットの左シフトを示し、「＞＞Ｙ」は、Ｙビットの右シフトを示し、「＾」は、排他的論理和を示し、「＆」は、論理積を示し、「｜」は、論理和を示す。また、ｈは、定数ラウンド値ｃ（ｒ−１）における上位ビット（上位３２ビット）、ｌは、定数ラウンド値ｃ（ｒ−１）における下位ビット（下位３２ビット）である。
【０２２６】
そして、ラウンド定数生成部２２３は、算出したラウンド（ｒ）での定数ラウンド値ｃ（ｒ）の下位３２ビットを、第ｒラウンドにおけるラウンド定数Ｃ（ｒ）として、第一ラウンド鍵生成部２２４又は第二ラウンド鍵生成部２２５に出力する。
【０２２７】
以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。
【０２２８】
Ｃ（０）＝0x3b29b693、Ｃ（１）＝0x90a58f8a、Ｃ（２）＝0x472ae357、Ｃ（３）＝0x42963e28、Ｃ（４）＝0xd87dc430、Ｃ（５）＝0x650288d7、Ｃ（６）＝0x0ead60b6、Ｃ（７）＝0xfb50532a、Ｃ（８）＝0x9139bbc3、Ｃ（９）＝0x299705c5、Ｃ（１０）＝0xef6ad616、Ｃ（１１）＝0xa65c1715、Ｃ（１２）＝0x797d1135、Ｃ（１３）＝0x32fc654e、Ｃ（１４）＝0x21220db8、Ｃ（１５）＝0x607dac22、Ｃ（１６）＝0x848836e0、Ｃ（１７）＝0x4520f9e5、Ｃ（１８）＝0xb9ace29a、Ｃ（１９）＝0xd055aef9、Ｃ（２０）＝0x4d3fb373、Ｃ（２１）＝0x8580f288、Ｃ（２２）＝0x5ba4bdbb、Ｃ（２３）＝0xbd8ff33a、Ｃ（２４）＝0xaa44bf81、Ｃ（２５）＝0x5db3f5f3、Ｃ（２６）＝0xa912fe04、Ｃ（２７）＝0xb2199ea1、Ｃ（２８）＝0x0fc7c10b、Ｃ（２９）＝0xc8667a84、Ｃ（３０）＝0x3f1f042d、Ｃ（３１）＝0xe54fa37c、Ｃ（３２）＝0x57f029af、Ｃ（３３）＝0x51e8c49c、Ｃ（３４）＝0x309ad6ca、Ｃ（３５）＝0x28f96206、Ｃ（３６）＝0x69e76232、Ｃ（３７）＝0xa3e58818、Ｃ（３８）＝0x634bc1a5、Ｃ（３９）＝0x241a197a、Ｃ（４０）＝0x49f94ff8、Ｃ（４１）＝0x3be45cf2、Ｃ（４２）＝0xe333768c、Ｃ（４３）＝0x441d4ad3、Ｃ（４４）＝0x481b935c、Ｃ（４５）＝0x7f2f5b3a、Ｃ（４６）＝0x4f343d06、Ｃ（４７）＝0x93e71c9e、Ｃ（４８）＝0x538a846f、Ｃ（４９）＝0xe4104b62、Ｃ（５０）＝0x8afc58d1、Ｃ（５１）＝0xff1b5dff、Ｃ（５２）＝0x807d5a5f、Ｃ（５３）＝0x38bb3e91、Ｃ（５４）＝0xaa795066、Ｃ（５５）＝0xe2ecfa45、Ｃ（５６）＝0xa9e54199、Ｃ（５７）＝0x4f65a079、Ｃ（５８）＝0x0c193f7e、Ｃ（５９）＝0xf940c888、Ｃ（６０）＝0x9be8c4e3、Ｃ（６１）＝0x21d56b4d、Ｃ（６２）＝0xc42f2a96、Ｃ（６３）＝0x8755ad35、Ｃ（６４）＝0xd46ae335、Ｃ（６５）＝0xb6da8dcf、Ｃ（６６）＝0x957dc5b9、Ｃ（６７）＝0x70e60e27、Ｃ（６８）＝0x55f716e4、Ｃ（６９）＝0x074e71f0、Ｃ（７０）＝0x38862be6、Ｃ（７１）＝0xb6b5feda、Ｃ（７２）＝0xe218af99、Ｃ（７３）＝0xdad7fb69、Ｃ（７４）＝0x4cb4f709、Ｃ（７５）＝0x04059dd2、Ｃ（７６）＝0x5d89ac52、Ｃ（７７）＝0xbb9a4e52、Ｃ（７８）＝0xb2f0f825、Ｃ（７９）＝0x45e50053、Ｃ（８０）＝0xcbc3e094、Ｃ（８１）＝0xd3424821、Ｃ（８２）＝0x4055f227、Ｃ（８３）＝0x225350f2、Ｃ（８４）＝0x6e0db8ea、Ｃ（８５）＝0x22c17ad2、Ｃ（８６）＝0x7ce0aac4、Ｃ（８７）＝0x2089d252、Ｃ（８８）＝0x3754e27c、Ｃ（８９）＝0x29ab7052、Ｃ（９０）＝0xdd5389f0、Ｃ（９１）＝0xa6adc149、Ｃ（９２）＝0xb1986ead、Ｃ（９３）＝0x313b3c3f、Ｃ（９４）＝0xc661bab4、Ｃ（９５）＝0xc4ecf0fd。
【０２２９】
第一ラウンド鍵生成部２２４は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【０２３０】
例えば、第一ラウンド鍵生成部２２４による鍵ラウンド値の算出は、上述の図３に示す第一鍵ラウンド値変換関数ｆKを用いて行われる。
【０２３１】
図３に示すように、第一鍵ラウンド値変換関数ｆKは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域２１１に記憶されている算出値の初期値）を８分割（本実施形態においては、各々３２ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【０２３２】
なお、第一鍵ラウンド値変換関数ｆKを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２３３】
次に、第一ラウンド鍵生成部２２４で使用するＦ関数である関数ＦＫについて説明する。
【０２３４】
本実施形態における関数ＦＫも、上述の（５）式に示すように、非線形変換γＫと、線形変換λｋと、の合成変換を行う関数であり、線形変換λｋは、バイト置換πＫと、行列変換θＫと、からなる。
【０２３５】
ここで、関数ＦＫへの入力をＸ、関数ＦＫからの出力をＹとして説明する。
【０２３６】
本実施形態においては、Ｘ及びＹは、６４ビットのデータである。
【０２３７】
まず、非線形変換γＫでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ７）に分割して、分割した各々のサブデータを、下記の（２０）式に示すように、置換テーブルＳｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’７とする。
【０２３８】
【数２０】
【０２３９】
なお、置換テーブルＳｂｏｘは、例えば、上記の（７）で示される。
【０２４０】
次に、行列変換θＫでは、上記の非線形変換γＫでの変換後のサブデータ（ｓ’０，ｓ’１，・・・，ｓ’７）を４行２列の行列にして、下記の（２１）式に示すように、変換行列Ａとの有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”７とする。
【０２４１】
【数２１】
【０２４２】
ここで、変換行列Ａは、ある列を入力列とし、当該入力列に対して変換行列Ａによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、５個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０２４３】
次に、バイト置換πＫでは、下記の（２２）式に示すように、行列変換θＫで変換されたサブデータ（ｓ”０，ｓ”１，・・・，ｓ”７）のうちの半分のデータの入れ替えを行う。なお、変換後のサブデータをｙ０，ｙ１，・・・，ｙ７とする。
【０２４４】
【数２２】
【０２４５】
そして、以上のようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ７）を（２３）式のように連結することで、関数ＦＫの出力Ｙとする。
【０２４６】
【数２３】
【０２４７】
以上の関数ＦＫでは、後述する関数ＦＲと比較して、一つの入力に対して一回の処理で出力を行うため、計算量が少なくてすみ、軽実装が可能となる。
【０２４８】
図１１に戻り、第二ラウンド鍵生成部２２５は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【０２４９】
例えば、第二ラウンド鍵生成部２２５による鍵ラウンド値の算出は、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いて行われる。
【０２５０】
図４に示すように、第二鍵ラウンド値変換関数ｆ’Ｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（本実施形態では、各々３２ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【０２５１】
なお、第二鍵ラウンド値変換関数ｆ’Kを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２５２】
次に、第二ラウンド鍵生成部２２５で使用するＦ関数である関数ＦＲについて説明する。
【０２５３】
関数ＦＲは、上述の（１３）式に示すように、非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段分）行う関数である。
【０２５４】
ここで、関数ＦＲへの入力をＸ、関数ＦＲからの出力をＹとして説明する。
【０２５５】
本実施形態においては、Ｘ及びＹは、６４ビットのデータである。
【０２５６】
まず、非線形変換γＲでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ７）に分割して、分割した各々のサブデータを、下記の（２４）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【０２５７】
【数２４】
【０２５８】
なお、置換テーブルＳ−ｂｏｘは、例えば、上記の（７）で示されるものを使用すればよい。
【０２５９】
次に、バイト置換πＲでは、下記の（２５）式に示すように、非線形変換γＲで変換されたサブデータ（ｓ’０，ｓ’１，・・・，ｓ’７）を２行４列の行列として、各々の列に含まれる各々の行のデータが各々異なる列に配置されるように、データの入れ替えを行う。なお、（２５）式は一例であって、各々の列に含まれる各々の行のデータが各々異なる列に配置されるものであれば、他の入れ替え方式を採用することも可能である。
【０２６０】
また、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”７とする。
【０２６１】
【数２５】
【０２６２】
次に、行列変換θＲでは、下記の（２６）式に示すように、上記のバイト置換πＲでの変換後のサブデータ（ｓ”０，ｓ”１，・・・，ｓ”７）を要素とする２行４列の行列と、変換行列Ｂと、の有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｙ０，ｙ１，・・・，ｙ７とする。
【０２６３】
【数２６】
【０２６４】
ここで、変換行列Ｂは、ある列を入力列とし、当該入力列に対して変換行列Ｂによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、３個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０２６５】
そして、このようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ７）を、（２７）式に示すように、サブデータ（ｓ０，ｓ１，・・・，ｓ７）として、非線形変換γＲ、バイト置換πＲ及び行列変換θＲによる変換を３回（合計４回）行うことで、算出されるサブデータ（ｙ０，ｙ１，・・・，ｙ７）を（２７）式のように連結することで、関数ＦＲの出力Ｙとする。
【０２６６】
【数２７】
【０２６７】
以上の関数ＦＲでは、前述の関数ＦＫと比較して、一つの入力に対して４回の処理で出力を行うため、安全性を高めることができる。なお、この４回の回数に関しては、適宜変更可能である。
【０２６８】
図１１に戻り、撹拌部２２６は、各ラウンドにおける平文ラウンド値を算出する処理を行う。
【０２６９】
例えば、撹拌部２２６による平文ラウンド値の算出は、図５に示すような平文ラウンド値変換関数ｆＲを用いて行われる。
【０２７０】
図５に示すように、平文ラウンド値変換関数ｆＲは、第ｒ−１ラウンドの平文ラウンド値ｘ（ｒ−１）（但し、ｒ＝０の場合は、メッセージブロック化部２２２でブロック化されたメッセージブロックＭ’ｉ）を８分割（本実施形態では、各々３２ビット）した分割データであるｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）を、それぞれ、ｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの平文ラウンド値ｘ（ｒ）を生成する関数である。
【０２７１】
なお、平文ラウンド値変換関数ｆＲを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２７２】
また、撹拌部２２６で使用するＦ関数である関数ＦＲについては、上述の第二ラウンド鍵生成部２２５で使用するＦ関数である関数ＦＲと同様であるため、説明を省略する。
【０２７３】
本実施形態におけるハッシュ値の算出処理についても、図７と同様に行うことが可能である。
【０２７４】
まず、ハッシュ値生成装置２００では、入力部１３０を介して、ハッシュ値を生成するメッセージＭの入力を受け付け、ハッシュ値生成装置２００の全体制御部２２１が、メッセージブロック化部２２２にメッセージＭを入力する。
【０２７５】
そして、メッセージブロック化部２２２では、メッセージＭをパディングして、２５６ビット毎のメッセージブロック（Ｍ’０，・・・，Ｍ’ｋ；ｋは１以上の整数）に分割する。
【０２７６】
次に、全体制御部２２１は、初期値記憶領域２１１に記憶されている算出値の初期値Ｈ−１と、メッセージブロック化部２２２でブロック化されたメッセージブロックＭｉ’のうち、最初のメッセージブロックＭ’０と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ０を算出する。
【０２７７】
ここで、第一ブロック暗号ｆＥを用いた処理は、ラウンド定数生成部２２３、第一ラウンド鍵生成部２２４及び撹拌部２２６で行われる。
【０２７８】
そして、全体制御部２２１は、算出した平文ラウンド値ｈ０と、メッセージブロックＭ’０と、の排他的論理和を算出することで、算出値を求め、求めた算出値と、次のメッセージブロックＭ’１と、をブロック暗号ｆＥに入力することで、平文ラウンド値ｈ１を算出する。なお、算出された算出値については、算出値記憶領域１１５に記憶される。
【０２７９】
このような処理を、最後のメッセージブロックＭ’ｋの直前のメッセージブロックＭ’ｋ−１まで繰り返すことで、平文ラウンド値ｈｋ−１を算出する。
【０２８０】
そして、全体制御部２２１は、平文ラウンド値ｈｋ−１と、メッセージブロックＭ’ｋ−１と、の排他的論理和で算出される算出値と、最後のメッセージブロックＭ’ｋと、を第二ブロック暗号ｆ’Ｅに入力することにより、平文ラウンド値ｈｋを算出する。
【０２８１】
ここで、第二ブロック暗号ｆ’Ｅを用いた処理は、ラウンド定数生成部２２３、第二ラウンド鍵生成部２２５及び撹拌部２２６で行われる。
【０２８２】
そして、全体制御部２２１は、平文ラウンド値ｈｋと、最後のメッセージブロックＭ’ｋと、の排他的論理和でハッシュ値Ｈｋを算出する。
【０２８３】
このようなハッシュ値Ｈｋは、ハッシュ値記憶領域２１６に記憶される。
【０２８４】
ここで、第一ブロック暗号ｆＥでの処理及び第二ブロック暗号ｆ’Ｅでの処理については、ビット数は異なるが、図８及び図９での処理と同様であるため、説明を省略する。
【０２８５】
以上のように、本実施形態によれば、２５６ビットのハッシュ値を算出することができる。
【０２８６】
ここで、差分攻撃線形攻撃に対する耐性の指標として、最小のアクティブＳ−ｂｏｘ数を用いた下記の（２８）式が用いられる。
【０２８７】
【数２８】
【０２８８】
この点、ＡＥＳ（Advanced Encryption Standard）型のＦ関数においては、２段分のアクティブＳ−ｂｏｘ数をＢとすると、４段分のアクティブＳ−ｂｏｘ数は、Ｂ２となる。このように、Ｓ−ｂｏｘを４段重ねることで安全性を高めるこのような手法をＷＴＳ（Wide Trail Strategy）という。
【０２８９】
これに対して、例えば、図５に示されているようなＦｅｉｓｔｅｌ構造では、Ｆ関数の出力をＸ６（ｒ−１）、Ｘ７（ｒ−１）に加算する処理があるため、単にＦ関数の段数を増やすＷＴＳを採用することができない。
【０２９０】
この点、本発明では、平文ラウンド値変換関数ｆＲで使用するＦ関数である関数ＦＲにおいて、第二非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段）行うことで安全性を確保している。
【０２９１】
例えば、本発明の第一の実施形態における５１２ビットのハッシュ値を生成するハッシュ値生成装置１００では、２段分の最低アクティブＳ−ｂｏｘ数「Ｂ＝５」であるため、Ｆ関数一つ当たりの最低アクティブＳ−ｂｏｘ数「Ｂ２＝２５」となる。
【０２９２】
そして、１２段でアクティブなＦ関数は、最低５つであるため、アクティブＳ−ｂｏｘ数の最小値は、「５×２５＝１２５」となる。
【０２９３】
従って、最大の差分伝搬の確率は、「１２５×６（＝７５０）＞５１２」となるため、（２８）式を満たし、差分攻撃に対して耐性を有することがわかる。
【０２９４】
また、本発明の第二の実施形態における２５６ビットのハッシュ値を生成するハッシュ値生成装置２００では、２段分の最低アクティブＳ−ｂｏｘ数「Ｂ＝３」であるため、Ｆ関数一つ当たりの最低アクティブＳ−ｂｏｘ数「Ｂ２＝９」となる。
【０２９５】
そして、１２段でアクティブなＦ関数は、最低５つであるため、アクティブＳ−ｂｏｘ数の最小値は、「５×９＝４５」となる。
【０２９６】
従って、最大の差分伝搬の確率は、「４５×６（＝２７０）＞２５６」となるため、（２８）式を満たし、差分攻撃に対して耐性を有することがわかる。
【０２９７】
なお、ＷＴＳについては、下記の文献２に詳細に記載されている。
【０２９８】
文献２：J.Daemen and V. Rijmen, Springer, 2002, February, “The Design of Rijndael”, pp. 123-147
また、以上に記載した第一の実施形態及び第二の実施形態では、それぞれ、５１２ビット、２５６ビットのハッシュ値を算出するようにしているが、このような態様に限定されるわけではなく、ビット長を適宜変化させることで、２２４ビット、３８４ビット等の他のビット長のハッシュ値を算出することも可能である。
【０２９９】
さらに、以上に記載した実施形態においては、ハッシュ値生成装置１００、２００を図６に示すようなコンピュータ９００で実現可能としたが、このような態様に限定されず、例えば、ＣＰＵと、発揮性又は不発揮性メモリと、を備える携帯電話端末、非接触型ＩＣカード、商品タグ等の実装規模の小さなデバイスにおいても実現可能である。
【０３００】
また、上述したハッシュ値生成装置１００、２００は、コンピュータがプログラムを実行することにより実現されるものでなくてもよい。例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。
【０３０１】
以上に記載した実施形態においては、図５に示すような平文ラウンド値変換関数ｆＲを使用しているが、このような態様に限定されず、関数ＦＲをＦ関数として使用するものであれば、どのようなものであってもよい。例えば、図１２（平文ラウンド値変換関数ｆＲ変形例を示す概略図）に示すような平文ラウンド値変換関数ｆＲを使用することも可能である。
【０３０２】
図１２に示す平文ラウンド値変換関数ｆＲでは、ラウンド鍵Ｋ（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨ（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｑＬ（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｌ）と、を算出する。
【０３０３】
そして、値ｐＨ及び値ｑＨの排他的論理和と、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド鍵のｘ０（ｒ）とする。
【０３０４】
また、値ｐＬ及び値ｑＬの排他的論理和と、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド値のｘ１（ｒ）とする。
【０３０５】
図１２に示すような平文ラウンド値変換関数ｆＲを用いることで、Ｆ関数への入力を出力にフィードフォワードすることで、Ｆ関数部分の置換性をくずすことができる。
【０３０６】
さらに、図５に示すような平文ラウンド値変換関数ｆＲの替わりに、例えば、図１３（平文ラウンド値変換関数ｆＲ変形例を示す概略図）に示すような平文ラウンド値変換関数ｆＲを使用することも可能である。
【０３０７】
図１３に示す平文ラウンド値変換関数ｆＲでは、ラウンド鍵Ｋ０（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、ラウンド鍵Ｋ１（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の排他的論理和である値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨ（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ０（ｒ），ｘ５（ｒ−１） ＸＯＲ Ｋ１（ｒ））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｑＬ（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１） ＸＯＲ Ｋ１（ｒ））Ｌ）と、を算出する。
【０３０８】
ここで、ラウンド鍵Ｋ０（ｒ）は、第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）を用い、ラウンド鍵Ｋ１（ｒ）は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を用いる。
【０３０９】
図１３に示すような平文ラウンド値変換関数ｆＲを用いることで、ラウンド鍵を2倍以上の大きさにすることが可能である。
【図面の簡単な説明】
【０３１０】
【図１】第一の実施形態であるハッシュ値生成装置の概略図。
【図２】線形変換関数ｆｃを示す概略図。
【図３】第一鍵ラウンド値変換関数ｆＫの概略図。
【図４】第二鍵ラウンド値変換関数ｆ’Ｋの概略図。
【図５】平文ラウンド値変換関数ｆＲの概略図。
【図６】コンピュータの概略図。
【図７】ハッシュ値の算出処理を示す概略図。
【図８】第一ブロック暗号ｆＥでの処理を示す概略図。
【図９】第二ブロック暗号ｆ’Ｅでの処理を示す概略図。
【図１０】ハッシュ値生成装置におけるハッシュ値の生成処理を示すフローチャート。
【図１１】第二の実施形態であるハッシュ値生成装置の概略図。
【図１２】平文ラウンド値変換関数ｆＲ変形例を示す概略図。
【図１３】平文ラウンド値変換関数ｆＲ変形例を示す概略図。
【符号の説明】
【０３１１】
１００、２００ ハッシュ値生成装置
１１０、２１０ 記憶部
１１１、２１１ 初期値記憶領域
１１２ 定数ラウンド値記憶領域
１１３ 鍵ラウンド値記憶領域
１１４ 平文ラウンド値記憶領域
１１５ 算出値記憶領域
１１６ ハッシュ値記憶領域
１２０、２２０ 制御部
１２１、２２１ 全体制御部
１２２、２２２ メッセージブロック化部
１２３、２２３ ラウンド定数生成部
１２４、２２４ 第一ラウンド鍵生成部
１２５、２２５ 第二ラウンド鍵生成部
１２６、２２６ 撹拌部
【技術分野】
【０００１】
本発明は、ハッシュ値を生成する技術に関する。
【背景技術】
【０００２】
ハッシュ関数は、任意長のメッセージを入力として、特定の長さのハッシュ値を生成する関数である。
【０００３】
一般的に、ハッシュ関数は固定長のメッセージブロックを入力するブロック暗号から構成され、入力されたメッセージに対してブロック暗号化を繰り返し行うことで、メッセージの攪拌を行い、最終的にハッシュ値として出力する。ハッシュ関数の代表例としてはＳＨＡ−１、または、ＳＨＡ−２５６等のＳＨＡ−２ハッシュ族、などがある（非特許文献１参照）。
【０００４】
【非特許文献１】NIST FIPS 180-2, ”Secure Hash Standard”, 2002 August 1, pp. 9-23, http://csrc.nist.gov/publications /fips/fips180-2/fips180-2.pdf
【発明の開示】
【発明が解決しようとする課題】
【０００５】
非特許文献１に記載のＳＨＡ−１は、ハッシュ関数が持つべき安全性である衝突耐性に問題があることが知られており、ＳＨＡ−２ハッシュ族についても、ＳＨＡ−１と類似した構造であることから、ハッシュ関数が持つべき安全性に問題を生ずる可能性がある。
【０００６】
そこで、本発明は、安全性の評価が可能なハッシュ関数を提供することを目的とする。
【課題を解決するための手段】
【０００７】
以上の課題を解決するため、本発明は、非線形変換を複数回行うＦ関数を備えるブロック暗号を用いてハッシュ値を生成する。
【０００８】
例えば、本発明は、メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置であって、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御部を備えること、を特徴とする。
【発明の効果】
【０００９】
以上のように、本発明によれば、安全性の評価が可能なハッシュ関数を提供することができる。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明の第一の実施形態であるハッシュ値生成装置１００の概略図である。
【００１１】
ここで、本実施形態においては、５１２ビットのハッシュ値を生成するようにしている。
【００１２】
図示するように、ハッシュ値生成装置１００は、記憶部１１０と、制御部１２０と、入力部１３０と、出力部１４０と、を備える。
【００１３】
記憶部１１０は、初期値記憶領域１１１と、定数ラウンド値記憶領域１１２と、鍵ラウンド値記憶領域１１３と、平文ラウンド値記憶領域１１４と、算出値記憶領域１１５と、ハッシュ値記憶領域１１６と、を備える。
【００１４】
初期値記憶領域１１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。
【００１５】
本実施形態においては、ハッシュ値を生成する際の初期値として、定数ラウンド値の初期値と、算出値の初期値と、が記憶される。
【００１６】
ここで、定数ラウンド値の初期値は、例えば、ｃ（−１）＝0xffffffffffffffffffffffffffffffffといった定数が記憶される。
【００１７】
また、算出値の初期値は、Ｈ−１＝（Ｈ−１．０，Ｈ−１．１，・・・，Ｈ−１．７）であり、Ｈ−１．０＝0x0000000000000000、Ｈ−１．１＝0x0000000000000000、Ｈ−１．２＝0x0000000000000000、Ｈ−１．３＝0x0000000000000000、Ｈ−１．４＝0x0000000000000000、Ｈ−１．５＝0x0000000000000000、Ｈ−１．６＝0x0000000000000000、Ｈ−１．７＝0x0000000000000000、といった定数が記憶される。
【００１８】
なお、定数ラウンド値及び算出値の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【００１９】
定数ラウンド値記憶領域１１２には、各々のメッセージブロックにおけるラウンド毎の定数ラウンド値を特定する情報が格納される。
【００２０】
なお、本実施形態においては、定数ラウンド値は、後述するラウンド定数生成部１２３で生成される。
【００２１】
鍵ラウンド値記憶領域１１３には、各々のメッセージブロックにおけるラウンド毎の鍵ラウンド値を特定する情報が格納される。
【００２２】
なお、本実施形態においては、鍵ラウンド値は、後述する第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成される。
【００２３】
平文ラウンド値記憶領域１１４には、各々のメッセージブロックにおけるラウンド毎の平文ラウンド値を特定する情報が格納される。
【００２４】
なお、本実施形態においては、平文ラウンド値は、後述する撹拌部１２６で生成される。
【００２５】
算出値記憶領域１１５には、各々のメッセージブロックにおいて全てのラウンドを経て算出された算出値を特定する情報が格納される。
【００２６】
なお、本実施形態においては、算出値は、後述する全体制御部１２１で生成される。
【００２７】
ハッシュ値記憶領域には、全てのメッセージブロックにおいて全てのラウンドを経て算出されたハッシュ値を特定する情報が格納される。
【００２８】
なお、本実施形態においては、ハッシュ値は、後述する全体制御部１２１で生成される。
【００２９】
制御部１２０は、全体制御部１２１と、メッセージブロック化部１２２と、ラウンド定数生成部１２３と、第一ラウンド鍵生成部１２４と、第二ラウンド鍵生成部１２５と、撹拌部１２６と、を備える。
【００３０】
全体制御部１２１は、ハッシュ値生成装置１００における処理の全体を制御する。
【００３１】
特に、本実施形態においては、ハッシュ値を算出するメッセージをブロック化したメッセージブロックを管理する処理や、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４、第二ラウンド鍵生成部１２５及び撹拌部１２６でのラウンドを管理する処理を行う。
【００３２】
また、全体制御部１２１は、全てのラウンドを経て撹拌部１２６において算出された平文ラウンド値と、当該ラウンドでの処理の対象となったメッセージブロックと、の排他的論理和を算出することで、算出値を算出する。
【００３３】
さらに、全体制御部１２１は、全てのメッセージブロック及び全てのラウンドを経て撹拌部１２６において算出された平文ラウンド値と、最後のメッセージブロックと、の排他的論理和を算出することで、ハッシュ値を算出する。
【００３４】
メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージを予め定められたビット長のブロックに分割し、パディングを行う。
【００３５】
ここで、本実施形態では、ハッシュ値を算出する対象となるメッセージを５１２ビット毎のブロックに分割するようにしているが、このような態様に限定されるわけではない。
【００３６】
また、例えば、本実施形態におけるパディングは、以下のようにして行う。
【００３７】
まず、メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージのビット数が、５１２ビットで割り切れる場合には、当該メッセージを５１２ビット毎に分割することで各々のメッセージブロックを生成するとともに、メッセージブロックを追加して最後のメッセージブロックとする。
【００３８】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットに「１」、先頭ビットの次のビットから数えて３８３ビットまでに「０」、最後の１２８ビットにメッセージのビット長、を特定する情報を格納する。
【００３９】
次に、メッセージブロック化部１２２は、ハッシュ値を算出する対象となるメッセージのビット数が、５１２ビットで割り切れない場合には、当該メッセージを５１２ビット毎に分割することで各々のメッセージブロックを生成するとともに、分割した最後尾のメッセージブロックには最後のビットまで「０」を特定する情報を格納することで、５１２ビットにし、さらに、メッセージブロックを追加して最後のメッセージブロックとする。
【００４０】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットから数えて３８４ビットまでに「０」、最後の１２８ビットにメッセージのビット長、を特定する情報を格納する。
【００４１】
なお、本実施形態においては、ハッシュ値を算出するメッセージをＭとし、パディングにより、５１２ビットで割り切れるようなビット長にされたメッセージをＭ’とし、メッセージブロックの数をｋ＋１（ｋは１以上の整数）とし、各々のメッセージブロックをＭ’ｉ（ｉは、０≦ｉ≦ｋなる整数）とする。
【００４２】
ラウンド定数生成部１２３は、各ラウンドにおける定数ラウンド値及びラウンド定数を算出する。
【００４３】
本実施形態においては、ラウンド定数生成部１２３は、最初のラウンドの場合には初期値記憶領域１１１に記憶されている定数ラウンド値の初期値から、または、最初のラウンドではない場合には定数ラウンド値記憶領域１１２に記憶されている前ラウンドにおける定数ラウンド値から、線形変換関数ｆｃを用いて、各ラウンドにおける定数ラウンド値を算出する。
【００４４】
例えば、図２（線形変換関数ｆｃを示す概略図）に示すように、ラウンド定数生成部１２３は、前ラウンド（ｒ−１）の定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット（本実施形態では、上位６４ビット）と下位ビット（本実施形態では、下位６４ビット）を入れ替えることにより、今ラウンド（ｒ）の定数ラウンド値ｃ（ｒ）を算出する。
【００４５】
即ち、下記の（１）式及び（２）式に示されるようにして、前ラウンドの定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）から今ラウンドの定数ラウンド値ｃ（ｒ）を算出する。
【００４６】
【数１】
【００４７】
【数２】
【００４８】
ここで、（１）式及び（２）式において、ｔＨ及びｔＬは、それぞれ、定数ラウンド値ｃ（ｒ−１）（ｒ＝０の場合には定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット及び下位ビットである。
【００４９】
また、関数ｆＬは、線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いる。
【００５０】
一般に、ＬＦＳＲは多項式で決定されるが、ここではＬＦＳＲを決定する多項式ｇ（ｘ）を、下記の（３）式のように定義する。
【００５１】
【数３】
【００５２】
但し、ｇ（ｘ）は有限体ＧＦ（２）において定義される多項式である。
【００５３】
なお、関数ｆＬの擬似コードは、下記の（４）のように示される。
【００５４】
【数４】
【００５５】
ここで、「＜＜Ｘ」は、Ｘビットの左シフトを示し、「＞＞Ｙ」は、Ｙビットの右シフトを示し、「＾」は、ビット毎の排他的論理和を示し、「＆」は、ビット毎の論理積を示し、「｜」は、ビット毎の論理和を示す。また、ｈは、定数ラウンド値ｃ（ｒ−１）における上位ビット（上位６４ビット）、ｌは、定数ラウンド値ｃ（ｒ−１）における下位ビット（下位６４ビット）である。
【００５６】
そして、ラウンド定数生成部１２３は、算出したラウンド（ｒ）での定数ラウンド値ｃ（ｒ）の下位６４ビットを、第ｒラウンドにおけるラウンド定数Ｃ（ｒ）として、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５に出力する。
【００５７】
以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。
【００５８】
Ｃ（０）＝0x9916b42b1075d3c4、Ｃ（１）＝0xef660b4c6b97a9a1、Ｃ（２）＝0x645ad0ac41d74f11、Ｃ（３）＝0xdb7166e541d48abf、Ｃ（４）＝0x81f2b60293356a19、Ｃ（５）＝0x0b2cd041e8d806c6、Ｃ（６）＝0x71ba676d3737d203、Ｃ（７）＝0x5ac3fe60d882617f、Ｃ（８）＝0xd670690748b71e50、Ｃ（９）＝0x0de6b2578d83a9c6、Ｃ（１０）＝0x495850aeb6b42f1c、Ｃ（１１）＝0x379ac95e360ea718、Ｃ（１２）＝0x4388096e355a904b、Ｃ（１３）＝0xa81b9a1fa3d8e607、Ｃ（１４）＝0x1eb9d10b41021771、Ｃ（１５）＝0xa06e687e8f63981c、Ｃ（１６）＝0x7ae7442d04085dc5、Ｃ（１７）＝0x81b9a1fa3d8e6070、Ｃ（１８）＝0x8d745b60ffab5b2e、Ｃ（１９）＝0x7096388f8ddbfba6、Ｃ（２０）＝0x43a1d2e4854f16df、Ｃ（２１）＝0xd2c1168da307b8c4、Ｃ（２２）＝0x686e0046fab67746、Ｃ（２３）＝0x5b9dae851876b54c、Ｃ（２４）＝0xc7514acf0553f123、Ｃ（２５）＝0x7eef4ea7f5b2836d、Ｃ（２６）＝0x7bac60e8fac5e8b7、Ｃ（２７）＝0xeb24ce2c42a25be8、Ｃ（２８）＝0x8858c877049d8ee6、Ｃ（２９）＝0xbc0acc029ee139fd、Ｃ（３０）＝0x216321dc12763b99、Ｃ（３１）＝0xf02b300a7b84e7f4、Ｃ（３２）＝0x858c877049d8ee65、Ｃ（３３）＝0xa6458bfd0199b3ea、Ｃ（３４）＝0x6042a2a65c81c3f2、Ｃ（３５）＝0xef6690937d84b5cf、Ｃ（３６）＝0x91937e2ae66f5995、Ｃ（３７）＝0xdb7309991998fb06、Ｃ（３８）＝0x303d47cce25f1c32、Ｃ（３９）＝0x7d55d2d7f20bba44、Ｃ（４０）＝0xc0f51f33897c70c8、Ｃ（４１）＝0x93be008b27a4c52a、Ｃ（４２）＝0x134d887db199957d、Ｃ（４３）＝0x4ef8022c9e9314a8、Ｃ（４４）＝0x4d3621f6c66655f4、Ｃ（４５）＝0x5d09436695c67e9b、Ｃ（４６）＝0x244173688df1018c、Ｃ（４７）＝0x12cc464eb893d657、Ｃ（４８）＝0xe77572c54c267c57、Ｃ（４９）＝0x3d41a65d99ad233a、Ｃ（５０）＝0x8d4c3fa6a4f1a700、Ｃ（５１）＝0xf506997666b48ce9、Ｃ（５２）＝0x3530fe9a93c69c01、Ｃ（５３）＝0xb2f32e0d75581f9f、Ｃ（５４）＝0xa2b3450d34f80a62、Ｃ（５５）＝0xbdbc0752ae82041a、Ｃ（５６）＝0xfcbdab53a80253ee、Ｃ（５７）＝0x8080a22dc1ea6a0e、Ｃ（５８）＝0xe26f59fd346119e5、Ｃ（５９）＝0x020288b707a9a839、Ｃ（６０）＝0xef542c203e0e4baf、Ｃ（６１）＝0x7e7a9dbb6544da82、Ｃ（６２）＝0xadc944336c5178e0、Ｃ（６３）＝0x9f033d397a994632、Ｃ（６４）＝0xc155afaacaa799e6、Ｃ（６５）＝0x0a7c4b82918762ae、Ｃ（６６）＝0x15cf4a18bef631c4、Ｃ（６７）＝0x29f12e0a461d8ab8、Ｃ（６８）＝0x573d2862fbd8c710、Ｃ（６９）＝0xa7c4b82918762ae0、Ｃ（７０）＝0x3a1dea5f00e9307a、Ｃ（７１）＝0xe9625fc31a3ad1e7、Ｃ（７２）＝0x9e07161b7846bb8e、Ｃ（７３）＝0xb5108bbffc8311c1、Ｃ（７４）＝0x781c586de11aee39、Ｃ（７５）＝0xd4422efff20c4704、Ｃ（７６）＝0x86982a636be194de、Ｃ（７７）＝0x41914f4c5c594a4d、Ｃ（７８）＝0x1a60a98daf865378、Ｃ（７９）＝0x60ac76e59eef050f、Ｃ（８０）＝0x1ff21951c5fb3787、Ｃ（８１）＝0x92282f25efd44260、Ｃ（８２）＝0x7fc8654717ecde1d、Ｃ（８３）＝0x48a0bc97bf510980、Ｃ（８４）＝0x99c8dec8b039544f、Ｃ（８５）＝0x321b06ed692c705d、Ｃ（８６）＝0x67237b22c0e5513c、Ｃ（８７）＝0xc86c1bb5a4b1c174、Ｃ（８８）＝0xfa64a75fec1f68ca、Ｃ（８９）＝0x31299a6506af538d、Ｃ（９０）＝0x8f7bd6ab5ff78f13、Ｃ（９１）＝0xb2d6d6f3615f3452、Ｃ（９２）＝0x4b9fe5ca043c462a、Ｃ（９３）＝0xbd2be4aafe9eab2f、Ｃ（９４）＝0x3ee6639b84994ef5、Ｃ（９５）＝0xf4af92abfa7aacbc。
【００５９】
第一ラウンド鍵生成部１２４は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【００６０】
例えば、第一ラウンド鍵生成部１２４による鍵ラウンド値の算出は、図３（第一鍵ラウンド値変換関数ｆｋの概略図）に示す第一鍵ラウンド値変換関数ｆｋを用いて行われる。
【００６１】
図示するように、第一鍵ラウンド値変換関数ｆｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（ここでは、各々６４ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【００６２】
具体的には、第一鍵ラウンド値変換関数ｆｋでは、まず、第一ラウンド鍵生成部１２４が、鍵ラウンド値記憶領域１１３に記憶されている第ｒ−１ラウンドの鍵ラウンド値（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を、ｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）に８等分する。
【００６３】
次に、第一ラウンド鍵生成部１２４は、第ｒ−１ラウンドの鍵ラウンド値の内のｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、をそれぞれ第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、とする。
【００６４】
次に、第一ラウンド鍵生成部１２４は、ラウンド定数生成部１２３で生成されたラウンド定数Ｃ（ｒ）及び第ｒ−１ラウンドのラウンド鍵の内のｋ４（ｒ−１）の排他的論理和の値ａＨと、第ｒ−１ラウンドのラウンド鍵の内のｋ５（ｒ−１）の値ａＬと、を連結した値ａをＦ関数である関数Ｆｋに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｂＨ（ｂＨ＝Ｆｋ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｂＬ（ｂＬ＝Ｆｋ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｌ）と、を算出する。
【００６５】
そして、第一ラウンド鍵生成部１２４は、値ｂＨと、第ｒ−１ラウンドの鍵ラウンド値の内のｋ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ０（ｒ）とする。
【００６６】
また、第一ラウンド鍵生成部１２４は、値ｂＬと、第ｒ−１ラウンドの鍵ラウンド値の内のｋ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ１（ｒ）とする。
【００６７】
次に、第一ラウンド鍵生成部１２４は、第ｒ−１ラウンドの鍵ラウンド値の内のｋ４（ｒ−１）、ｋ５（ｒ−１）を、それぞれ第ｒラウンドの鍵ラウンド値ｋ６（ｒ）、ｋ７（ｒ）とする。
【００６８】
そして、第一ラウンド鍵生成部１２４は、以上のようにして算出したｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）を連結して第ｒラウンドの鍵ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて鍵ラウンド値記憶領域１１３に記憶する。
【００６９】
また、第一ラウンド鍵生成部１２４は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を、第ｒラウンドのラウンド鍵Ｋ（ｒ）として、撹拌部１２６に出力する。
【００７０】
次に、第一ラウンド鍵生成部１２４で使用するＦ関数である関数ＦＫについて説明する。
【００７１】
関数ＦＫは、下記の（５）式に示すように、非線形変換γＫと、線形変換λｋと、の合成変換を行う関数である。
【００７２】
【数５】
【００７３】
また、線形変換λｋは、バイト置換πＫと、行列変換θＫと、の合成変換である。
【００７４】
ここで、関数ＦＫへの入力をＸ、関数ＦＫからの出力をＹとして説明する。
【００７５】
本実施形態においては、Ｘ及びＹは、１２８ビットのデータである。
【００７６】
まず、非線形変換γＫでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ１５）に分割して、分割した各々のサブデータを、下記の（６）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【００７７】
【数６】
【００７８】
なお、置換テーブルＳｂｏｘは、例えば、下記の（７）で示される。
【００７９】
【数７】
【００８０】
次に、行列変換θＫでは、上記の非線形変換γＫでの変換後のサブデータ（ｓ’０，ｓ’１，・・・，ｓ’１５）を８行２列の行列にして、下記の（１０）式に示すように、変換行列Ａとの乗算を行うことで、変換を行う。ここで、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”１５とする。乗算は、有限体ＧＦ（２８）上での乗算である。有限体ＧＦ（２＾８）は、下記の（８）式及び（９）式を満たす。
【００８１】
【数８】
【００８２】
【数９】
【００８３】
【数１０】
【００８４】
ここで、変換行列Ａは、ある列を入力列とし、当該入力列に対して変換行列Ａによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、９個以上になるような変換であれば、どのような変換行列を用いてもよい。
【００８５】
次に、バイト置換πＫでは、下記の（１１）式に示すように、行列変換θＫで変換されたサブデータ（ｓ”０，ｓ”１，・・・，ｓ”１５）のうちの半分のデータの入れ替えを行う。なお、変換後のサブデータをｙ０，ｙ１，・・・，ｙ１５とする。
【００８６】
【数１１】
【００８７】
そして、以上のようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を（１２）式のように連結することで、関数ＦＫの出力Ｙとする。
【００８８】
【数１２】
【００８９】
以上の関数ＦＫでは、後述する関数ＦＲと比較して、一つの入力に対して一回の処理で出力を行うため、計算量が少なくてすみ、軽実装が可能となる。
【００９０】
図１に戻り、第二ラウンド鍵生成部１２５は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【００９１】
例えば、第二ラウンド鍵生成部１２５による鍵ラウンド値の算出は、図４（第二鍵ラウンド値変換関数ｆ’Ｋの概略図）に示す第二鍵ラウンド値変換関数ｆ’Ｋを用いて行われる。
【００９２】
図示するように、第二鍵ラウンド値変換関数ｆ’Ｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（ここでは、各々６４ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【００９３】
具体的には、第二鍵ラウンド値変換関数ｆ’Kでは、まず、第二ラウンド鍵生成部１２５が、鍵ラウンド値記憶領域１１３に記憶されている第ｒ−１ラウンドの鍵ラウンド値（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値）を、ｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）に８等分する。
【００９４】
次に、第二ラウンド鍵生成部１２５は、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、をそれぞれ第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、とする。
【００９５】
次に、第二ラウンド鍵生成部１２５は、ラウンド定数生成部１２３で生成されたラウンド定数Ｃ（ｒ）及び第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ４（ｒ−１）の排他的論理和である値ａ’Ｈと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ５（ｒ−１）の値ａ’Ｌと、を連結した値ａ’をＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｂ’Ｈ（ｂ’Ｈ＝ＦＲ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｂ’Ｌ（ｂＬ＝ＦＲ（ｋ４（ｒ−１） ＸＯＲ Ｃ（ｒ），ｋ５（ｒ−１））Ｌ）と、を算出する。
【００９６】
そして、第二ラウンド鍵生成部１２５は、値ｂ’Ｈと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ０（ｒ）とする。
【００９７】
また、第二ラウンド鍵生成部１２５は、値ｂ’Ｌと、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの鍵ラウンド値のｋ１（ｒ）とする。
【００９８】
次に、第二ラウンド鍵生成部１２５は、第ｒ−１ラウンドの鍵ラウンド値（ｒ＝０の場合には算出値）の内のｋ４（ｒ−１）、ｋ５（ｒ−１）を、それぞれ第ｒラウンドの鍵ラウンド値ｋ６（ｒ）、ｋ７（ｒ）とする。
【００９９】
そして、第二ラウンド鍵生成部１２５は、以上のようにして算出したｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）を連結して第ｒラウンドの鍵ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて鍵ラウンド値記憶領域１１３に記憶する。
【０１００】
また、第二ラウンド鍵生成部１２５は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を、第ｒラウンドのラウンド鍵Ｋ（ｒ）として、撹拌部１２６に出力する。
【０１０１】
次に、第二ラウンド鍵生成部１２５で使用するＦ関数である関数ＦＲについて説明する。
【０１０２】
関数ＦＲは、下記の（１３）式に示すように、非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段）行う関数である。
【０１０３】
【数１３】
【０１０４】
ここで、関数ＦＲへの入力をＸ、関数ＦＲからの出力をＹとして説明する。本実施形態においては、Ｘ及びＹは、１２８ビットのデータである。
【０１０５】
まず、非線形変換γＲでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ１５）に分割して、分割した各々のサブデータを、下記の（１４）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【０１０６】
【数１４】
【０１０７】
なお、置換テーブルＳｂｏｘは、例えば、上記の（７）で示されるものを使用すればよい。
【０１０８】
次に、バイト置換πＲでは、（１５）式に示すように、非線形変換γＲで変換されたサブデータ（ｓ’０，ｓ’１，・・・，ｓ’１５）を４行４列の行列として、各々の列に含まれる各々の行のデータが各々異なる列に配置されるように、データの入れ替えを行う。なお、（１５）式は一例であって、各々の列に含まれる各々の行のデータが各々異なる列に配置されるものであれば、他の入れ替え方式を採用することも可能である。
【０１０９】
また、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”１５とする。
【０１１０】
【数１５】
【０１１１】
次に、行列変換θＲでは、下記の（１６）式に示すように、上記のバイト置換πＲでの変換後のサブデータ（ｓ”０，ｓ”１，・・・，ｓ”１５）を要素とする４行４列の行列と、変換行列Ｂと、の有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｙ０，ｙ１，・・・，ｙ１５とする。
【０１１２】
【数１６】
【０１１３】
ここで、変換行列Ｂは、ある列を入力列とし、当該入力列に対して変換行列Ｂによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、５個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０１１４】
そして、このようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を、（１７）式に示すように、サブデータ（ｓ０，ｓ１，・・・，ｓ１５）として、非線形変換γＲ、バイト置換πＲ及び行列変換θＲによる変換を３回（合計４回）行うことで、算出されるサブデータ（ｙ０，ｙ１，・・・，ｙ１５）を（１７）式のように連結することで、関数ＦＲの出力Ｙとする。
【０１１５】
【数１７】
【０１１６】
以上の関数ＦＲでは、前述の関数ＦＫと比較して、一つの入力に対して４回の処理で出力を行うため、安全性を高めることができる。なお、この４回という回数については、適宜変更可能である。
【０１１７】
図１に戻り、撹拌部１２６は、各ラウンドにおける平文ラウンド値を算出する処理を行う。
【０１１８】
例えば、撹拌部１２６による平文ラウンド値の算出は、図５（平文ラウンド値変換関数ｆＲの概略図）に示す平文ラウンド値変換関数ｆＲを用いて行われる。
【０１１９】
図示するように、平文ラウンド値変換関数ｆＲは、第ｒ−１ラウンドの平文ラウンド値ｘ（ｒ−１）（但し、ｒ＝０の場合は、メッセージブロック化部１２２でブロック化されたメッセージブロックＭ’ｉ）を８分割（ここでは、各々６４ビット）した分割データであるｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）を、それぞれ、ｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの平文ラウンド値ｘ（ｒ）を生成する関数である。
【０１２０】
具体的には、平文ラウンド値変換関数ｆＲでは、まず、撹拌部１２６が、平文ラウンド値記憶領域１１４に記憶されている第ｒ−１ラウンドの平文ラウンド値（但し、ｒ＝０の場合は、メッセージブロック化部１２２でブロック化されたメッセージブロックＭ’ｉ）を、ｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）に８等分する。
【０１２１】
次に、撹拌部１２６は、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、をそれぞれ第ｒラウンドの平文ラウンド値の内のｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、とする。
【０１２２】
次に、撹拌部１２６は、第一ラウンド鍵生成部１２４又は第二ラウンド鍵生成部１２５で生成されたラウンド鍵Ｋ（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨと（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｈ）、下位ビット（ここでは、下位６４ビット）の値ｑＬと（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｌ）、を算出する。
【０１２３】
そして、撹拌部１２６は、値ｑＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド鍵のｘ０（ｒ）とする。
【０１２４】
また、撹拌部１２６は、値ｑＬと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド値のｘ１（ｒ）とする。
【０１２５】
次に、撹拌部１２６は、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）、ｘ５（ｒ−１）を、それぞれ第ｒラウンドの平文ラウンド値ｘ６（ｒ）、ｘ７（ｒ）とする。
【０１２６】
そして、撹拌部１２６は、以上のようにして算出したｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）を連結して第ｒラウンドの平文ラウンド値として、第ｒ−１ラウンドの鍵ラウンド値と入れ替えて平文ラウンド値記憶領域１１４に記憶する。
【０１２７】
撹拌部１２６で使用するＦ関数である関数ＦＲについては、上述の（１３）式で示されているものと同様であるため、説明を省略する。
【０１２８】
入力部１３０は、情報の入力を受け付ける。
【０１２９】
出力部１４０は、情報を出力する。
【０１３０】
以上に記載したハッシュ値生成装置１００は、例えば、図６（コンピュータ９００の概略図）に示すような、ＣＰＵ（Central Processing Unit）９０１と、メモリ９０２と、ＨＤＤ（Hard Disk Drive）等の外部記憶装置９０３と、ＣＤ−ＲＯＭ（Compact Disk Read Only Memory）やＤＶＤ−ＲＯＭ（Digital Versatile Disk Read Only Memory）等の可搬性を有する記憶媒体９０４に対して情報を読み書きする読書装置９０５と、キーボードやマウスなどの入力装置９０６と、ディスプレイなどの出力装置９０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置９０８と、を備えた一般的なコンピュータ９００で実現できる。
【０１３１】
例えば、記憶部１１０は、ＣＰＵ９０１がメモリ９０２又は外部記憶装置９０３を利用することにより実現可能であり、制御部１２０は、外部記憶装置９０３に記憶されている所定のプログラムをメモリ９０２にロードしてＣＰＵ９０１で実行することで実現可能であり、入力部１３０は、ＣＰＵ９０１が入力装置９０６を利用することで実現可能であり、出力部１４０は、ＣＰＵ９０１が出力装置９０７を利用することで実現可能である。
【０１３２】
この所定のプログラムは、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、外部記憶装置９０３にダウンロードされ、それから、メモリ９０２上にロードされてＣＰＵ９０１により実行されるようにしてもよい。また、読書装置９０５を介して記憶媒体９０４から、あるいは、通信装置９０８を介してネットワークから、メモリ９０２上に直接ロードされ、ＣＰＵ９０１により実行されるようにしてもよい。
【０１３３】
次に、図７（ハッシュ値の算出処理を示す概略図）を用いて、ハッシュ値生成装置１００がハッシュ値を算出する処理の概略を示す。
【０１３４】
まず、ハッシュ値生成装置１００では、入力部１３０を介して、ハッシュ値を生成するメッセージＭの入力を受け付け、ハッシュ値生成装置１００の全体制御部１２１が、メッセージブロック化部１２２にメッセージＭを入力する。
【０１３５】
そして、メッセージブロック化部１２２では、メッセージＭをパディングして、５１２ビット毎のメッセージブロック（Ｍ’０，・・・，Ｍ’ｋ；ｋは１以上の整数）に分割する。
【０１３６】
次に、全体制御部１２１は、初期値記憶領域１１１に記憶されている算出値の初期値Ｈ−１と、メッセージブロック化部１２２でブロック化されたメッセージブロックＭｉ’のうち、最初のメッセージブロックＭ’０と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ０を算出する。
【０１３７】
ここで、第一ブロック暗号ｆＥを用いた処理は、後述するように、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４及び撹拌部１２６で行われる。
【０１３８】
そして、全体制御部１２１は、算出した平文ラウンド値ｈ０と、メッセージブロックＭ’０と、の排他的論理和を算出することで、算出値を求め、求めた算出値と、次のメッセージブロックＭ’１と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ１を算出する。なお、算出された算出値については、算出値記憶領域１１５に記憶される。
【０１３９】
このような処理を、最後のメッセージブロックＭ’ｋの直前のメッセージブロックＭ’ｋ−１まで繰り返すことで、平文ラウンド値ｈｋ−１を算出する。
【０１４０】
そして、全体制御部１２１は、平文ラウンド値ｈｋ−１と、メッセージブロックＭ’ｋ−１と、の排他的論理和で算出される算出値と、最後のメッセージブロックＭ’ｋと、を第二ブロック暗号ｆ’Ｅに入力することにより、平文ラウンド値ｈｋを算出する。
【０１４１】
ここで、第二ブロック暗号ｆ’Ｅを用いた処理は、後述するように、ラウンド定数生成部１２３、第二ラウンド鍵生成部１２５及び撹拌部１２６で行われる。
【０１４２】
そして、全体制御部１２１は、平文ラウンド値ｈｋと、最後のメッセージブロックＭ’ｋと、の排他的論理和でハッシュ値Ｈｋを算出する。
【０１４３】
このようなハッシュ値Ｈｋは、ハッシュ値記憶領域１１６に記憶される。
【０１４４】
なお、本発明におけるハッシュ値の算出処理（方法）は、図７に示した処理（方法）に限定されるわけではなく、第一ブロック暗号ｆＥ又は、第二ブロック暗号ｆ’Ｅの少なくとも何れか一方を利用すれば、どのようなものであってもよく。
【０１４５】
図８は、第一ブロック暗号ｆＥでの処理を示す概略図である。
【０１４６】
まず、ラウンド定数生成部１２３は、初期値記憶領域１１１に記憶されている定数ラウンド値の初期値を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝０における定数ラウンド値ｃ（０）を算出し、定数ラウンド値ｃ（０）の下位６４ビットを、ラウンドｒ＝０におけるラウンド定数Ｃ（０）として算出する。
【０１４７】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（０）を定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（０）を第一ラウンド鍵生成部１２４に出力する。
【０１４８】
次に、第一ラウンド鍵生成部１２４は、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉがメッセージブロックＭ’０の場合には、初期値記憶領域１１１に記憶されている算出値の初期値を取得して、一方、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉがメッセージブロックＭ’０ではない場合には、算出値記憶領域１１５に記憶されている前メッセージブロックＭ’ｉにおける算出値を取得して、図３に示すような第一鍵ラウンド値変換関数ｆKを用いた処理を行うことにより、ｒ＝０における鍵ラウンド値ｋ（０）を算出し、また、鍵ラウンド値ｋ（０）の内のｋ３（０）を、ラウンドｒ＝０のラウンド鍵Ｋ（０）として算出する。
【０１４９】
そして、第一ラウンド鍵生成部１２４は、鍵ラウンド値ｋ（０）を鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（０）を撹拌部１２６に出力する。
【０１５０】
次に、撹拌部１２６は、第一ブロック暗号ｆＥに入力されたメッセージブロックＭ’ｉを取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ｒ＝０における平文ラウンド値ｘ（０）を算出し、平文ラウンド値記憶領域１１４に記憶する。
【０１５１】
以上で、第０ラウンドの処理を終了する。
【０１５２】
次に、ラウンド定数生成部１２３は、定数ラウンド値記憶領域１１２に記憶されている定数ラウンド値ｃ（０）を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝１における定数ラウンド値ｃ（１）を算出し、定数ラウンド値ｃ（１）の下位６４ビットを、ラウンドｒ＝１におけるラウンド定数Ｃ（１）として算出する。
【０１５３】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（１）を、定数ラウンド値ｃ（０）に置き換えて（いわゆる上書きして）、定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（１）を第一ラウンド鍵生成部１２４に出力する。
【０１５４】
次に、第一ラウンド鍵生成部１２４は、鍵ラウンド値記憶領域１１３に記憶されている鍵ラウンド値ｋ（０）を取得して、図３に示すような第一鍵ラウンド値変換関数ｆKを用いた処理を行うことにより、ラウンドｒ＝１における鍵ラウンド値ｋ（１）を算出し、また、鍵ラウンド値ｋ（１）の内のｋ３（１）を、ラウンドｒ＝１のラウンド鍵Ｋ（１）として算出する。
【０１５５】
そして、第一ラウンド鍵生成部１２４は、算出した鍵ラウンド値ｋ（１）を、鍵ラウンド値ｋ（０）に置き換えて（いわゆる上書きして）、鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（１）を撹拌部１２６に出力する。
【０１５６】
次に、撹拌部１２６は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値ｘ（０）を取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ラウンドｒ＝１における平文ラウンド値ｘ（１）を算出し、算出した平文ラウンド値ｘ（１）を、平文ラウンド値ｘ（０）に置き換えて（いわゆる上書きして）、平文ラウンド値記憶領域１１４に記憶する。
【０１５７】
以上で、第１ラウンドの処理を終了する。
【０１５８】
そして、以上に記載した第１ラウンドでの処理と同様の処理を、所定のラウンド（ここでは、第３１ラウンド）まで繰り返すことで、第一ブロック暗号ｆＥでの処理を終了する。
【０１５９】
図９は、第二ブロック暗号ｆ’Ｅでの処理を示す概略図である。
【０１６０】
まず、ラウンド定数生成部１２３は、初期値記憶領域１１１に記憶されている定数ラウンド値の初期値を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝０における定数ラウンド値ｃ（０）を算出し、定数ラウンド値ｃ（０）の下位６４ビットを、ラウンドｒ＝０におけるラウンド定数Ｃ（０）として算出する。
【０１６１】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（０）を定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（０）を第二ラウンド鍵生成部１２５に出力する。
【０１６２】
次に、第二ラウンド鍵生成部１２５は、算出値記憶領域１１５に記憶されている前メッセージブロックＭ’ｋ−１における算出値を取得して、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いた処理を行うことにより、ｒ＝０における鍵ラウンド値ｋ（０）を算出し、また、鍵ラウンド値ｋ（０）の内のｋ３（０）を、ラウンドｒ＝０のラウンド鍵Ｋ（０）として算出する。
【０１６３】
そして、第二ラウンド鍵生成部１２５は、鍵ラウンド値ｋ（０）を鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（０）を撹拌部１２６に出力する。
【０１６４】
次に、撹拌部１２６は、第二ブロック暗号ｆ’Ｅに入力されたメッセージブロックＭ’ｋを取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ｒ＝０における平文ラウンド値ｘ（０）を算出し、平文ラウンド値記憶領域１１４に記憶する。
【０１６５】
以上で、第０ラウンドの処理を終了する。
【０１６６】
次に、ラウンド定数生成部１２３は、定数ラウンド値記憶領域１１２に記憶されている定数ラウンド値ｃ（０）を取得して、図２に示すような線形変換関数ｆｃを用いた処理を行うことにより、ラウンドｒ＝１における定数ラウンド値ｃ（１）を算出し、定数ラウンド値ｃ（１）の下位６４ビットを、ラウンドｒ＝１におけるラウンド定数Ｃ（１）として算出する。
【０１６７】
そして、ラウンド定数生成部１２３は、算出した定数ラウンド値ｃ（１）を、定数ラウンド値ｃ（０）に置き換えて（いわゆる上書きして）、定数ラウンド値記憶領域１１２に記憶し、ラウンド定数Ｃ（１）を第二ラウンド鍵生成部１２５に出力する。
【０１６８】
次に、第二ラウンド鍵生成部１２５は、鍵ラウンド値記憶領域１１３に記憶されている鍵ラウンド値ｋ（０）を取得して、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いた処理を行うことにより、ラウンドｒ＝１における鍵ラウンド値ｋ（１）を算出し、また、鍵ラウンド値ｋ（１）の内のｋ３（１）を、ラウンドｒ＝１のラウンド鍵Ｋ（１）として算出する。
【０１６９】
そして、第二ラウンド鍵生成部１２５は、算出した鍵ラウンド値ｋ（１）を、鍵ラウンド値ｋ（０）に置き換えて（いわゆる上書きして）、鍵ラウンド値記憶領域１１３に記憶し、ラウンド鍵Ｋ（１）を撹拌部１２６に出力する。
【０１７０】
次に、撹拌部１２６は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値ｘ（０）を取得して、図５に示すような平文ラウンド値変換関数ｆＲを用いた処理を行うことにより、ラウンドｒ＝１における平文ラウンド値ｘ（１）を算出し、算出した平文ラウンド値ｘ（１）を、平文ラウンド値ｘ（０）に置き換えて（いわゆる上書きして）、平文ラウンド値記憶領域１１４に記憶する。
【０１７１】
以上で、第１ラウンドの処理を終了する。
【０１７２】
以上に記載した第１ラウンドでの処理と同様の処理を、所定のラウンド（ここでは、第３１ラウンド）まで繰り返すことで、第二ブロック暗号ｆ’Ｅでの処理を終了する。
【０１７３】
図１０は、ハッシュ値生成装置１００におけるハッシュ値の生成処理を示すフローチャートである。
【０１７４】
まず、ハッシュ値生成装置１００は、入力部１３０を介してハッシュ値を生成する元となるメッセージＭを取得する（Ｓ１０）。
【０１７５】
次に、メッセージブロック化部１２２は、入出部１３０を介して取得したメッセージを予め定められたデータ長に分割することによりｋ＋１個のメッセージブロックＭ’ｉを生成する（Ｓ１１）。ここで、本実施形態においては、メッセージを５１２ビットのデータ長に分割するようにしている。
【０１７６】
次に、全体制御部１２１は、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３、平文ラウンド値記憶領域１１４、算出値記憶領域１１５及びハッシュ値記憶領域１１６に記憶されている情報のリセットを行う（Ｓ１２）。具体的には、全てのビット値を「０」にする。
【０１７７】
次に、全体制御部１２１は、メッセージブロックのカウンタであるメッセージカウンタｉの値を初期化する（Ｓ１３）。ここでは、メッセージカウンタｉの値に「０」を代入する。
【０１７８】
次に、全体制御部１２１は、メッセージカウンタｉの値が、ｉ＝ｋとなっているか否かを判断する（Ｓ１４）。
【０１７９】
ステップＳ１４で、ｉ＝ｋとなっていない場合には（ステップＳ１４でＮｏ）、ステップＳ１５に進み、ｉ＝ｋとなっている場合には（ステップＳ１４でＹｅｓ）、ステップＳ２１に進む。
【０１８０】
ステップＳ１５では、全体制御部１２１は、ラウンドのカウンタであるラウンドカウンタｒに初期値「０」を代入する。
【０１８１】
次に、全体制御部１２１は、ラウンドカウンタｒの値が、予め定められた第一ラウンド数（ここでは、ＲＯＵＮＤ ＮＵＭ＝３１）に対して、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ１６）。ステップＳ１６において、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にある場合には、ステップＳ１９に進み、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にない場合には、ステップＳ１７に進む。
【０１８２】
ステップＳ１７では、ラウンド定数生成部１２３、第一ラウンド鍵生成部１２４及び撹拌部１２６において、第一ブロック暗号ｆＥを用いて、定数ラウンド値、鍵ラウンド値及び平文ラウンド値を算出し、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３及び平文ラウンド値記憶領域１１４に記憶されている情報を更新する。
【０１８３】
次に、全体制御部１２１は、ラウンドカウンタｒの値に「１」をインクリメントして、ステップＳ１６に戻って処理を繰り返す。
【０１８４】
また、ステップＳ１９では、全体制御部１２１は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値と、メッセージブロックＭ’ｉと、の排他的論理和を算出することで算出値を算出し、算出した算出値で算出値記憶領域１１５に記憶されている情報を更新する。
【０１８５】
そして、全体制御部１２１は、メッセージカウンタｉの値に「１」をインクリメントして（Ｓ２０）、ステップＳ１４に戻って処理を繰り返す。
【０１８６】
一方、ステップＳ１４において、ｉ＝ｋとなっている場合には（ステップＳ１４でＹｅｓ）、ステップＳ２１において、全体制御部１２１は、ラウンドのカウンタであるラウンドカウンタｒに初期値「０」を代入する。
【０１８７】
次に、全体制御部１２１は、ラウンドカウンタｒの値が、予め定められた第二ラウンド数（ここでは、ＲＯＵＮＤ ＮＵＭ＝３１）に対して、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ２２）。
【０１８８】
そして、ステップＳ２２において、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にある場合には（ステップＳ２２でＹｅｓ）、ステップＳ２５に進み、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にない場合には（ステップＳ２２でＮｏ）、ステップＳ２３に進む。
【０１８９】
ステップＳ２３では、ラウンド定数生成部１２３、第二ラウンド鍵生成部１２５及び撹拌部１２６において、第二ブロック暗号ｆ’Ｅを用いて、定数ラウンド値、鍵ラウンド値及び平文ラウンド値を算出し、定数ラウンド値記憶領域１１２、鍵ラウンド値記憶領域１１３及び平文ラウンド値記憶領域１１４に記憶されている情報を更新する。
【０１９０】
次に、全体制御部１２１は、ラウンドカウンタｒの値に「１」をインクリメントして（Ｓ２４）、ステップＳ２２に戻って処理を繰り返す。
【０１９１】
また、ステップＳ２５では、全体制御部１２１は、平文ラウンド値記憶領域１１４に記憶されている平文ラウンド値と、メッセージブロックＭ’ｋと、の排他的論理和を算出することでハッシュ値を算出し、ハッシュ値記憶領域１１６に記憶されている情報を更新する。
【０１９２】
以上のように、本実施形態においては、５１２ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができる。
【０１９３】
図１１は、本発明の第二の実施形態であるハッシュ値生成装置２００の概略図である。
【０１９４】
ここで、本実施形態においては、２５６ビットのハッシュ値を生成するようにしている。
【０１９５】
図示するように、ハッシュ値生成装置２００は、記憶部２１０と、制御部２２０と、入力部１３０と、出力部１４０と、を備え、第一の実施形態と比較して、記憶部２１０及び制御部２２０が異なっているため、以下これらの異なっている点に関連する事項について説明する。
【０１９６】
記憶部２１０は、初期値記憶領域２１１と、定数ラウンド値記憶領域１１２と、鍵ラウンド値記憶領域１１３と、平文ラウンド値記憶領域１１４と、算出値記憶領域１１５と、ハッシュ値記憶領域１１６と、を備え、第一の実施形態と比較して、初期値記憶領域２１１に記憶されている情報が異なっているため、以下この異なっている点に関連する事項について説明する。
【０１９７】
初期値記憶領域２１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。
【０１９８】
本実施形態においては、ハッシュ値を生成する際の初期値として、定数ラウンド値の初期値と、算出値の初期値と、が記憶される。
【０１９９】
ここで、定数ラウンド値の初期値は、例えば、ｃ（−１）＝0xffffffffffffffffといった定数が記憶される。
【０２００】
また、算出値の初期値は、Ｈ−１＝（Ｈ−１．０，Ｈ−１．１，・・・，Ｈ−１．７）であり、Ｈ−１．０＝0x00000000、Ｈ−１．１＝0x00000000、Ｈ−１．２＝0x00000000、Ｈ−１．３＝0x00000000、Ｈ−１．４＝0x00000000、Ｈ−１．５＝0x00000000、Ｈ−１．６＝0x00000000、Ｈ−１．７＝0x00000000、といった定数が記憶される。
【０２０１】
なお、定数ラウンド値及び算出値の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。
【０２０２】
制御部２２０は、全体制御部２２１と、メッセージブロック化部２２２と、ラウンド定数生成部２２３と、第一ラウンド鍵生成部２２４と、第二ラウンド鍵生成部２２５と、撹拌部２２６と、を備える。
【０２０３】
全体制御部２２１は、ハッシュ値生成装置２００における処理の全体を制御する。
【０２０４】
特に、本実施形態においては、ハッシュ値を算出するメッセージをブロック化したメッセージブロックを管理する処理や、ラウンド定数生成部２２３、第一ラウンド鍵生成部２２４、第二ラウンド鍵生成部２２５及び撹拌部２２６でのラウンドを管理する処理を行う。
【０２０５】
また、全体制御部２２１は、全てのラウンドを経て撹拌部２２６において算出された平文ラウンド値と、当該ラウンドでの処理の対象となったメッセージブロックと、の排他的論理和を算出することで、算出値を算出する。
【０２０６】
さらに、全体制御部２２１は、全てのメッセージブロック及び全てのラウンドを経て撹拌部２２６において算出された平文ラウンド値と、最後のメッセージブロックと、の排他的論理和を算出することで、ハッシュ値を算出する。
【０２０７】
メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージを予め定められたビット長のブロックに分割し、パディングを行う。
【０２０８】
ここで、本実施形態では、ハッシュ値を算出する対象となるメッセージを２５６ビット毎のブロックに分割するようにしているが、このような態様に限定されるわけではない。
【０２０９】
また、例えば、本実施形態におけるパディングは、以下のようにして行う。
【０２１０】
まず、メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージのビット数が、２５６ビットで割り切れる場合には、当該メッセージを２５６ビット毎に分割することで各々のメッセージブロックを生成するとともに、メッセージブロックを追加して最後のメッセージブロックとする。
【０２１１】
そして、メッセージブロック化部２２２は、この最後のメッセージブロックにおいて、先頭ビットに「１」、先頭ビットの次のビットから数えて１９１ビットまでに「０」、最後の６４ビットにメッセージのビット長、を特定する情報を格納する。
【０２１２】
次に、メッセージブロック化部２２２は、ハッシュ値を算出する対象となるメッセージのビット数が、２５６ビットで割り切れない場合には、当該メッセージを２５６ビット毎に分割することで各々のメッセージブロックを生成するとともに、分割した最後尾のメッセージブロックには最後のビットまで「０」を特定する情報を格納することで、２５６ビットにし、さらに、メッセージブロックを追加して最後のメッセージブロックとする。
【０２１３】
そして、メッセージブロック化部１２２は、この最後のメッセージブロックにおいて、先頭ビットから数えて１９２ビットまでに「０」、最後の６４ビットにメッセージのビット長、を特定する情報を格納する。
【０２１４】
なお、本実施形態においては、ハッシュ値を算出するメッセージをＭとし、パディングにより、２５６ビットで割り切れるようなビット長にされたメッセージをＭ’とし、メッセージブロックの数をｋ＋１（ｋは１以上の整数）とし、各々のメッセージブロックをＭ’ｉ（ｉは、０≦ｉ≦ｋなる整数）とする。
【０２１５】
ラウンド定数生成部２２３は、各ラウンドにおける定数ラウンド値及びラウンド定数を算出する。
【０２１６】
本実施形態においても、ラウンド定数生成部２２３は、最初のラウンドの場合には、初期値記憶領域２１１に記憶されている定数ラウンド値の初期値から、または、最初のラウンドではない場合には、定数ラウンド値記憶領域２１２に記憶されている前ラウンドにおける定数ラウンド値から、線形変換関数ｆｃを用いて、各ラウンドにおける定数ラウンド値を算出する。
【０２１７】
例えば、図２に示すように、ラウンド定数生成部２２３は、前ラウンド（ｒ−１）の定数ラウンド値ｃ（ｒ−１）（ｒ＝０のときは、定数ラウンド値の初期値）を関数ｆＬに入力して算出された値の上位ビット（本実施形態では、上位３２ビット）と下位ビット（本実施形態では、下位３２ビット）を入れ替えることにより、今ラウンド（ｒ）の定数ラウンド値ｃ（ｒ）を算出する。
【０２１８】
即ち、上述の（１）式及び（２）式に示されるようにして、前ラウンドの定数ラウンド値ｃ（ｒ−１）（ｒ＝０のときは、定数ラウンド値の初期値）から今ラウンドの定数ラウンド値ｃ（ｒ）を算出する。
【０２１９】
また、関数ｆＬは、線形フィードバックシフトレジスタ（ＬＦＳＲ）を用いる。
【０２２０】
一般に、ＬＦＳＲは多項式で決定されるが、ここではＬＦＳＲを決定する多項式ｇ（ｘ）を、下記の（１８）式のように定義する。
【０２２１】
【数１８】
【０２２２】
但し、ｇ（ｘ）は有限体ＧＦ（２）において定義される多項式である。
【０２２３】
なお、関数ｆＬの擬似コードは、下記の（１９）のように示される。
【０２２４】
【数１９】
【０２２５】
ここで、「＜＜Ｘ」は、Ｘビットの左シフトを示し、「＞＞Ｙ」は、Ｙビットの右シフトを示し、「＾」は、排他的論理和を示し、「＆」は、論理積を示し、「｜」は、論理和を示す。また、ｈは、定数ラウンド値ｃ（ｒ−１）における上位ビット（上位３２ビット）、ｌは、定数ラウンド値ｃ（ｒ−１）における下位ビット（下位３２ビット）である。
【０２２６】
そして、ラウンド定数生成部２２３は、算出したラウンド（ｒ）での定数ラウンド値ｃ（ｒ）の下位３２ビットを、第ｒラウンドにおけるラウンド定数Ｃ（ｒ）として、第一ラウンド鍵生成部２２４又は第二ラウンド鍵生成部２２５に出力する。
【０２２７】
以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。
【０２２８】
Ｃ（０）＝0x3b29b693、Ｃ（１）＝0x90a58f8a、Ｃ（２）＝0x472ae357、Ｃ（３）＝0x42963e28、Ｃ（４）＝0xd87dc430、Ｃ（５）＝0x650288d7、Ｃ（６）＝0x0ead60b6、Ｃ（７）＝0xfb50532a、Ｃ（８）＝0x9139bbc3、Ｃ（９）＝0x299705c5、Ｃ（１０）＝0xef6ad616、Ｃ（１１）＝0xa65c1715、Ｃ（１２）＝0x797d1135、Ｃ（１３）＝0x32fc654e、Ｃ（１４）＝0x21220db8、Ｃ（１５）＝0x607dac22、Ｃ（１６）＝0x848836e0、Ｃ（１７）＝0x4520f9e5、Ｃ（１８）＝0xb9ace29a、Ｃ（１９）＝0xd055aef9、Ｃ（２０）＝0x4d3fb373、Ｃ（２１）＝0x8580f288、Ｃ（２２）＝0x5ba4bdbb、Ｃ（２３）＝0xbd8ff33a、Ｃ（２４）＝0xaa44bf81、Ｃ（２５）＝0x5db3f5f3、Ｃ（２６）＝0xa912fe04、Ｃ（２７）＝0xb2199ea1、Ｃ（２８）＝0x0fc7c10b、Ｃ（２９）＝0xc8667a84、Ｃ（３０）＝0x3f1f042d、Ｃ（３１）＝0xe54fa37c、Ｃ（３２）＝0x57f029af、Ｃ（３３）＝0x51e8c49c、Ｃ（３４）＝0x309ad6ca、Ｃ（３５）＝0x28f96206、Ｃ（３６）＝0x69e76232、Ｃ（３７）＝0xa3e58818、Ｃ（３８）＝0x634bc1a5、Ｃ（３９）＝0x241a197a、Ｃ（４０）＝0x49f94ff8、Ｃ（４１）＝0x3be45cf2、Ｃ（４２）＝0xe333768c、Ｃ（４３）＝0x441d4ad3、Ｃ（４４）＝0x481b935c、Ｃ（４５）＝0x7f2f5b3a、Ｃ（４６）＝0x4f343d06、Ｃ（４７）＝0x93e71c9e、Ｃ（４８）＝0x538a846f、Ｃ（４９）＝0xe4104b62、Ｃ（５０）＝0x8afc58d1、Ｃ（５１）＝0xff1b5dff、Ｃ（５２）＝0x807d5a5f、Ｃ（５３）＝0x38bb3e91、Ｃ（５４）＝0xaa795066、Ｃ（５５）＝0xe2ecfa45、Ｃ（５６）＝0xa9e54199、Ｃ（５７）＝0x4f65a079、Ｃ（５８）＝0x0c193f7e、Ｃ（５９）＝0xf940c888、Ｃ（６０）＝0x9be8c4e3、Ｃ（６１）＝0x21d56b4d、Ｃ（６２）＝0xc42f2a96、Ｃ（６３）＝0x8755ad35、Ｃ（６４）＝0xd46ae335、Ｃ（６５）＝0xb6da8dcf、Ｃ（６６）＝0x957dc5b9、Ｃ（６７）＝0x70e60e27、Ｃ（６８）＝0x55f716e4、Ｃ（６９）＝0x074e71f0、Ｃ（７０）＝0x38862be6、Ｃ（７１）＝0xb6b5feda、Ｃ（７２）＝0xe218af99、Ｃ（７３）＝0xdad7fb69、Ｃ（７４）＝0x4cb4f709、Ｃ（７５）＝0x04059dd2、Ｃ（７６）＝0x5d89ac52、Ｃ（７７）＝0xbb9a4e52、Ｃ（７８）＝0xb2f0f825、Ｃ（７９）＝0x45e50053、Ｃ（８０）＝0xcbc3e094、Ｃ（８１）＝0xd3424821、Ｃ（８２）＝0x4055f227、Ｃ（８３）＝0x225350f2、Ｃ（８４）＝0x6e0db8ea、Ｃ（８５）＝0x22c17ad2、Ｃ（８６）＝0x7ce0aac4、Ｃ（８７）＝0x2089d252、Ｃ（８８）＝0x3754e27c、Ｃ（８９）＝0x29ab7052、Ｃ（９０）＝0xdd5389f0、Ｃ（９１）＝0xa6adc149、Ｃ（９２）＝0xb1986ead、Ｃ（９３）＝0x313b3c3f、Ｃ（９４）＝0xc661bab4、Ｃ（９５）＝0xc4ecf0fd。
【０２２９】
第一ラウンド鍵生成部２２４は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【０２３０】
例えば、第一ラウンド鍵生成部２２４による鍵ラウンド値の算出は、上述の図３に示す第一鍵ラウンド値変換関数ｆKを用いて行われる。
【０２３１】
図３に示すように、第一鍵ラウンド値変換関数ｆKは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域２１１に記憶されている算出値の初期値）を８分割（本実施形態においては、各々３２ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【０２３２】
なお、第一鍵ラウンド値変換関数ｆKを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２３３】
次に、第一ラウンド鍵生成部２２４で使用するＦ関数である関数ＦＫについて説明する。
【０２３４】
本実施形態における関数ＦＫも、上述の（５）式に示すように、非線形変換γＫと、線形変換λｋと、の合成変換を行う関数であり、線形変換λｋは、バイト置換πＫと、行列変換θＫと、からなる。
【０２３５】
ここで、関数ＦＫへの入力をＸ、関数ＦＫからの出力をＹとして説明する。
【０２３６】
本実施形態においては、Ｘ及びＹは、６４ビットのデータである。
【０２３７】
まず、非線形変換γＫでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ７）に分割して、分割した各々のサブデータを、下記の（２０）式に示すように、置換テーブルＳｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’７とする。
【０２３８】
【数２０】
【０２３９】
なお、置換テーブルＳｂｏｘは、例えば、上記の（７）で示される。
【０２４０】
次に、行列変換θＫでは、上記の非線形変換γＫでの変換後のサブデータ（ｓ’０，ｓ’１，・・・，ｓ’７）を４行２列の行列にして、下記の（２１）式に示すように、変換行列Ａとの有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”７とする。
【０２４１】
【数２１】
【０２４２】
ここで、変換行列Ａは、ある列を入力列とし、当該入力列に対して変換行列Ａによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、５個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０２４３】
次に、バイト置換πＫでは、下記の（２２）式に示すように、行列変換θＫで変換されたサブデータ（ｓ”０，ｓ”１，・・・，ｓ”７）のうちの半分のデータの入れ替えを行う。なお、変換後のサブデータをｙ０，ｙ１，・・・，ｙ７とする。
【０２４４】
【数２２】
【０２４５】
そして、以上のようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ７）を（２３）式のように連結することで、関数ＦＫの出力Ｙとする。
【０２４６】
【数２３】
【０２４７】
以上の関数ＦＫでは、後述する関数ＦＲと比較して、一つの入力に対して一回の処理で出力を行うため、計算量が少なくてすみ、軽実装が可能となる。
【０２４８】
図１１に戻り、第二ラウンド鍵生成部２２５は、各ラウンドにおける鍵ラウンド値及びラウンド鍵を算出する処理を行う。
【０２４９】
例えば、第二ラウンド鍵生成部２２５による鍵ラウンド値の算出は、図４に示すような第二鍵ラウンド値変換関数ｆ’Ｋを用いて行われる。
【０２５０】
図４に示すように、第二鍵ラウンド値変換関数ｆ’Ｋは、第ｒ−１ラウンドの鍵ラウンド値ｋ（ｒ−１）（但し、ｒ＝０の場合は、算出値記憶領域１１５に記憶されている算出値、または、初期値記憶領域１１１に記憶されている算出値の初期値）を８分割（本実施形態では、各々３２ビット）した分割データであるｋ０（ｒ−１）、ｋ１（ｒ−１）、ｋ２（ｒ−１）、ｋ３（ｒ−１）、ｋ４（ｒ−１）、ｋ５（ｒ−１）、ｋ６（ｒ−１）、ｋ７（ｒ−１）を、それぞれ、ｋ０（ｒ）、ｋ１（ｒ）、ｋ２（ｒ）、ｋ３（ｒ）、ｋ４（ｒ）、ｋ５（ｒ）、ｋ６（ｒ）、ｋ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの鍵ラウンド値ｋ（ｒ）を生成する関数である。
【０２５１】
なお、第二鍵ラウンド値変換関数ｆ’Kを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２５２】
次に、第二ラウンド鍵生成部２２５で使用するＦ関数である関数ＦＲについて説明する。
【０２５３】
関数ＦＲは、上述の（１３）式に示すように、非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段分）行う関数である。
【０２５４】
ここで、関数ＦＲへの入力をＸ、関数ＦＲからの出力をＹとして説明する。
【０２５５】
本実施形態においては、Ｘ及びＹは、６４ビットのデータである。
【０２５６】
まず、非線形変換γＲでは、値Ｘを８ビット毎のサブデータ（ｓ０，ｓ１，・・・，ｓ７）に分割して、分割した各々のサブデータを、下記の（２４）式に示すように、置換テーブルＳ−ｂｏｘを用いて非線形変換を行う。ここで、変換後のサブデータをｓ’０，ｓ’１，・・・，ｓ’１５とする。
【０２５７】
【数２４】
【０２５８】
なお、置換テーブルＳ−ｂｏｘは、例えば、上記の（７）で示されるものを使用すればよい。
【０２５９】
次に、バイト置換πＲでは、下記の（２５）式に示すように、非線形変換γＲで変換されたサブデータ（ｓ’０，ｓ’１，・・・，ｓ’７）を２行４列の行列として、各々の列に含まれる各々の行のデータが各々異なる列に配置されるように、データの入れ替えを行う。なお、（２５）式は一例であって、各々の列に含まれる各々の行のデータが各々異なる列に配置されるものであれば、他の入れ替え方式を採用することも可能である。
【０２６０】
また、変換後のサブデータをｓ”０，ｓ”１，・・・，ｓ”７とする。
【０２６１】
【数２５】
【０２６２】
次に、行列変換θＲでは、下記の（２６）式に示すように、上記のバイト置換πＲでの変換後のサブデータ（ｓ”０，ｓ”１，・・・，ｓ”７）を要素とする２行４列の行列と、変換行列Ｂと、の有限体ＧＦ（２８）上での乗算を行うことで、変換を行う。ここで、変換後のサブデータをｙ０，ｙ１，・・・，ｙ７とする。
【０２６３】
【数２６】
【０２６４】
ここで、変換行列Ｂは、ある列を入力列とし、当該入力列に対して変換行列Ｂによる変換を行った後の値の列を出力列とした場合に、入力列及び出力列に含まれる項の内、値が「０」ではない項が、３個以上になるような変換であれば、どのような変換行列を用いてもよい。
【０２６５】
そして、このようにして算出されたサブデータ（ｙ０，ｙ１，・・・，ｙ７）を、（２７）式に示すように、サブデータ（ｓ０，ｓ１，・・・，ｓ７）として、非線形変換γＲ、バイト置換πＲ及び行列変換θＲによる変換を３回（合計４回）行うことで、算出されるサブデータ（ｙ０，ｙ１，・・・，ｙ７）を（２７）式のように連結することで、関数ＦＲの出力Ｙとする。
【０２６６】
【数２７】
【０２６７】
以上の関数ＦＲでは、前述の関数ＦＫと比較して、一つの入力に対して４回の処理で出力を行うため、安全性を高めることができる。なお、この４回の回数に関しては、適宜変更可能である。
【０２６８】
図１１に戻り、撹拌部２２６は、各ラウンドにおける平文ラウンド値を算出する処理を行う。
【０２６９】
例えば、撹拌部２２６による平文ラウンド値の算出は、図５に示すような平文ラウンド値変換関数ｆＲを用いて行われる。
【０２７０】
図５に示すように、平文ラウンド値変換関数ｆＲは、第ｒ−１ラウンドの平文ラウンド値ｘ（ｒ−１）（但し、ｒ＝０の場合は、メッセージブロック化部２２２でブロック化されたメッセージブロックＭ’ｉ）を８分割（本実施形態では、各々３２ビット）した分割データであるｘ０（ｒ−１）、ｘ１（ｒ−１）、ｘ２（ｒ−１）、ｘ３（ｒ−１）、ｘ４（ｒ−１）、ｘ５（ｒ−１）、ｘ６（ｒ−１）、ｘ７（ｒ−１）を、それぞれ、ｘ０（ｒ）、ｘ１（ｒ）、ｘ２（ｒ）、ｘ３（ｒ）、ｘ４（ｒ）、ｘ５（ｒ）、ｘ６（ｒ）、ｘ７（ｒ）に変換し、変換したこれらの値を連結することで、第ｒラウンドの平文ラウンド値ｘ（ｒ）を生成する関数である。
【０２７１】
なお、平文ラウンド値変換関数ｆＲを用いた処理に関しては、ビット数が異なるだけで、第一の実施形態と同様であるため、詳細な説明は省略する。
【０２７２】
また、撹拌部２２６で使用するＦ関数である関数ＦＲについては、上述の第二ラウンド鍵生成部２２５で使用するＦ関数である関数ＦＲと同様であるため、説明を省略する。
【０２７３】
本実施形態におけるハッシュ値の算出処理についても、図７と同様に行うことが可能である。
【０２７４】
まず、ハッシュ値生成装置２００では、入力部１３０を介して、ハッシュ値を生成するメッセージＭの入力を受け付け、ハッシュ値生成装置２００の全体制御部２２１が、メッセージブロック化部２２２にメッセージＭを入力する。
【０２７５】
そして、メッセージブロック化部２２２では、メッセージＭをパディングして、２５６ビット毎のメッセージブロック（Ｍ’０，・・・，Ｍ’ｋ；ｋは１以上の整数）に分割する。
【０２７６】
次に、全体制御部２２１は、初期値記憶領域２１１に記憶されている算出値の初期値Ｈ−１と、メッセージブロック化部２２２でブロック化されたメッセージブロックＭｉ’のうち、最初のメッセージブロックＭ’０と、を第一ブロック暗号ｆＥに入力することで、平文ラウンド値ｈ０を算出する。
【０２７７】
ここで、第一ブロック暗号ｆＥを用いた処理は、ラウンド定数生成部２２３、第一ラウンド鍵生成部２２４及び撹拌部２２６で行われる。
【０２７８】
そして、全体制御部２２１は、算出した平文ラウンド値ｈ０と、メッセージブロックＭ’０と、の排他的論理和を算出することで、算出値を求め、求めた算出値と、次のメッセージブロックＭ’１と、をブロック暗号ｆＥに入力することで、平文ラウンド値ｈ１を算出する。なお、算出された算出値については、算出値記憶領域１１５に記憶される。
【０２７９】
このような処理を、最後のメッセージブロックＭ’ｋの直前のメッセージブロックＭ’ｋ−１まで繰り返すことで、平文ラウンド値ｈｋ−１を算出する。
【０２８０】
そして、全体制御部２２１は、平文ラウンド値ｈｋ−１と、メッセージブロックＭ’ｋ−１と、の排他的論理和で算出される算出値と、最後のメッセージブロックＭ’ｋと、を第二ブロック暗号ｆ’Ｅに入力することにより、平文ラウンド値ｈｋを算出する。
【０２８１】
ここで、第二ブロック暗号ｆ’Ｅを用いた処理は、ラウンド定数生成部２２３、第二ラウンド鍵生成部２２５及び撹拌部２２６で行われる。
【０２８２】
そして、全体制御部２２１は、平文ラウンド値ｈｋと、最後のメッセージブロックＭ’ｋと、の排他的論理和でハッシュ値Ｈｋを算出する。
【０２８３】
このようなハッシュ値Ｈｋは、ハッシュ値記憶領域２１６に記憶される。
【０２８４】
ここで、第一ブロック暗号ｆＥでの処理及び第二ブロック暗号ｆ’Ｅでの処理については、ビット数は異なるが、図８及び図９での処理と同様であるため、説明を省略する。
【０２８５】
以上のように、本実施形態によれば、２５６ビットのハッシュ値を算出することができる。
【０２８６】
ここで、差分攻撃線形攻撃に対する耐性の指標として、最小のアクティブＳ−ｂｏｘ数を用いた下記の（２８）式が用いられる。
【０２８７】
【数２８】
【０２８８】
この点、ＡＥＳ（Advanced Encryption Standard）型のＦ関数においては、２段分のアクティブＳ−ｂｏｘ数をＢとすると、４段分のアクティブＳ−ｂｏｘ数は、Ｂ２となる。このように、Ｓ−ｂｏｘを４段重ねることで安全性を高めるこのような手法をＷＴＳ（Wide Trail Strategy）という。
【０２８９】
これに対して、例えば、図５に示されているようなＦｅｉｓｔｅｌ構造では、Ｆ関数の出力をＸ６（ｒ−１）、Ｘ７（ｒ−１）に加算する処理があるため、単にＦ関数の段数を増やすＷＴＳを採用することができない。
【０２９０】
この点、本発明では、平文ラウンド値変換関数ｆＲで使用するＦ関数である関数ＦＲにおいて、第二非線形変換γＲと、バイト置換πＲと、行列変換θＲと、の合成変換を４回（４段）行うことで安全性を確保している。
【０２９１】
例えば、本発明の第一の実施形態における５１２ビットのハッシュ値を生成するハッシュ値生成装置１００では、２段分の最低アクティブＳ−ｂｏｘ数「Ｂ＝５」であるため、Ｆ関数一つ当たりの最低アクティブＳ−ｂｏｘ数「Ｂ２＝２５」となる。
【０２９２】
そして、１２段でアクティブなＦ関数は、最低５つであるため、アクティブＳ−ｂｏｘ数の最小値は、「５×２５＝１２５」となる。
【０２９３】
従って、最大の差分伝搬の確率は、「１２５×６（＝７５０）＞５１２」となるため、（２８）式を満たし、差分攻撃に対して耐性を有することがわかる。
【０２９４】
また、本発明の第二の実施形態における２５６ビットのハッシュ値を生成するハッシュ値生成装置２００では、２段分の最低アクティブＳ−ｂｏｘ数「Ｂ＝３」であるため、Ｆ関数一つ当たりの最低アクティブＳ−ｂｏｘ数「Ｂ２＝９」となる。
【０２９５】
そして、１２段でアクティブなＦ関数は、最低５つであるため、アクティブＳ−ｂｏｘ数の最小値は、「５×９＝４５」となる。
【０２９６】
従って、最大の差分伝搬の確率は、「４５×６（＝２７０）＞２５６」となるため、（２８）式を満たし、差分攻撃に対して耐性を有することがわかる。
【０２９７】
なお、ＷＴＳについては、下記の文献２に詳細に記載されている。
【０２９８】
文献２：J.Daemen and V. Rijmen, Springer, 2002, February, “The Design of Rijndael”, pp. 123-147
また、以上に記載した第一の実施形態及び第二の実施形態では、それぞれ、５１２ビット、２５６ビットのハッシュ値を算出するようにしているが、このような態様に限定されるわけではなく、ビット長を適宜変化させることで、２２４ビット、３８４ビット等の他のビット長のハッシュ値を算出することも可能である。
【０２９９】
さらに、以上に記載した実施形態においては、ハッシュ値生成装置１００、２００を図６に示すようなコンピュータ９００で実現可能としたが、このような態様に限定されず、例えば、ＣＰＵと、発揮性又は不発揮性メモリと、を備える携帯電話端末、非接触型ＩＣカード、商品タグ等の実装規模の小さなデバイスにおいても実現可能である。
【０３００】
また、上述したハッシュ値生成装置１００、２００は、コンピュータがプログラムを実行することにより実現されるものでなくてもよい。例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。
【０３０１】
以上に記載した実施形態においては、図５に示すような平文ラウンド値変換関数ｆＲを使用しているが、このような態様に限定されず、関数ＦＲをＦ関数として使用するものであれば、どのようなものであってもよい。例えば、図１２（平文ラウンド値変換関数ｆＲ変形例を示す概略図）に示すような平文ラウンド値変換関数ｆＲを使用することも可能である。
【０３０２】
図１２に示す平文ラウンド値変換関数ｆＲでは、ラウンド鍵Ｋ（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨ（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｑＬ（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１））Ｌ）と、を算出する。
【０３０３】
そして、値ｐＨ及び値ｑＨの排他的論理和と、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ６（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド鍵のｘ０（ｒ）とする。
【０３０４】
また、値ｐＬ及び値ｑＬの排他的論理和と、第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ７（ｒ−１）と、の排他的論理和を算出し、算出した値を第ｒラウンドの平文ラウンド値のｘ１（ｒ）とする。
【０３０５】
図１２に示すような平文ラウンド値変換関数ｆＲを用いることで、Ｆ関数への入力を出力にフィードフォワードすることで、Ｆ関数部分の置換性をくずすことができる。
【０３０６】
さらに、図５に示すような平文ラウンド値変換関数ｆＲの替わりに、例えば、図１３（平文ラウンド値変換関数ｆＲ変形例を示す概略図）に示すような平文ラウンド値変換関数ｆＲを使用することも可能である。
【０３０７】
図１３に示す平文ラウンド値変換関数ｆＲでは、ラウンド鍵Ｋ０（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ４（ｒ−１）の排他的論理和である値ｐＨと、ラウンド鍵Ｋ１（ｒ）及び第ｒ−１ラウンドの平文ラウンド値（ｒ＝０の場合は、メッセージブロックＭ’ｉ）の内のｘ５（ｒ−１）の排他的論理和である値ｐＬと、を連結した値ｐをＦ関数である関数ＦＲに入力した出力値の内の上位ビット（ここでは、上位６４ビット）の値ｑＨ（ｑＨ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ０（ｒ），ｘ５（ｒ−１） ＸＯＲ Ｋ１（ｒ））Ｈ）と、下位ビット（ここでは、下位６４ビット）の値ｑＬ（ｑＬ＝ＦＲ（ｘ４（ｒ−１） ＸＯＲ Ｋ（ｒ），ｘ５（ｒ−１） ＸＯＲ Ｋ１（ｒ））Ｌ）と、を算出する。
【０３０８】
ここで、ラウンド鍵Ｋ０（ｒ）は、第ｒラウンドの鍵ラウンド値の内のｋ２（ｒ）を用い、ラウンド鍵Ｋ１（ｒ）は、第ｒラウンドの鍵ラウンド値の内のｋ３（ｒ）を用いる。
【０３０９】
図１３に示すような平文ラウンド値変換関数ｆＲを用いることで、ラウンド鍵を2倍以上の大きさにすることが可能である。
【図面の簡単な説明】
【０３１０】
【図１】第一の実施形態であるハッシュ値生成装置の概略図。
【図２】線形変換関数ｆｃを示す概略図。
【図３】第一鍵ラウンド値変換関数ｆＫの概略図。
【図４】第二鍵ラウンド値変換関数ｆ’Ｋの概略図。
【図５】平文ラウンド値変換関数ｆＲの概略図。
【図６】コンピュータの概略図。
【図７】ハッシュ値の算出処理を示す概略図。
【図８】第一ブロック暗号ｆＥでの処理を示す概略図。
【図９】第二ブロック暗号ｆ’Ｅでの処理を示す概略図。
【図１０】ハッシュ値生成装置におけるハッシュ値の生成処理を示すフローチャート。
【図１１】第二の実施形態であるハッシュ値生成装置の概略図。
【図１２】平文ラウンド値変換関数ｆＲ変形例を示す概略図。
【図１３】平文ラウンド値変換関数ｆＲ変形例を示す概略図。
【符号の説明】
【０３１１】
１００、２００ ハッシュ値生成装置
１１０、２１０ 記憶部
１１１、２１１ 初期値記憶領域
１１２ 定数ラウンド値記憶領域
１１３ 鍵ラウンド値記憶領域
１１４ 平文ラウンド値記憶領域
１１５ 算出値記憶領域
１１６ ハッシュ値記憶領域
１２０、２２０ 制御部
１２１、２２１ 全体制御部
１２２、２２２ メッセージブロック化部
１２３、２２３ ラウンド定数生成部
１２４、２２４ 第一ラウンド鍵生成部
１２５、２２５ 第二ラウンド鍵生成部
１２６、２２６ 撹拌部
【特許請求の範囲】
【請求項１】
メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置であって、
前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御部を備えること、
を特徴とするハッシュ値生成装置。
【請求項２】
請求項１に記載のハッシュ値生成装置であって、
前記Ｆ関数は、非線形変換と、バイト置換と、行列変換と、の合成変換を複数回行うものであること、
を特徴とするハッシュ値生成装置。
【請求項３】
請求項２に記載のハッシュ値生成装置であって、
前記複数回は、４回であること、
を特徴とするハッシュ値生成装置。
【請求項４】
請求項２に記載のハッシュ値生成装置であって、
前記非線形変換は、変換前のデータに対応する変換後のデータを、予め定められた置換テーブルより抽出することで、変換を行うものであること、
を特徴とするハッシュ値生成装置。
【請求項５】
請求項２に記載のハッシュ値生成装置であって、
前記バイト置換は、変換前のデータを項目とする行列において、任意の列に含まれるそれぞれの項目を、それぞれ異なる列に配置する変換を行うものであること、
を特徴とするハッシュ値生成装置。
【請求項６】
請求項４に記載のハッシュ値生成装置であって、
前記行列変換は、変換前のデータを項目とする行列に変換行列を乗算することで、当該行列の任意の列に含まれるそれぞれの項目と、乗算後の行列における当該任意の列に対応する列に含まれるそれぞれの項目と、において０ではない項目が、予め定められた数以上となるものであること、
を特徴とするハッシュ値生成装置。
【請求項７】
請求項６に記載のハッシュ値生成装置であって、
５１２ビットのハッシュ値を生成する場合には、前記数は５であること、
を特徴とするハッシュ値生成装置。
【請求項８】
請求項６に記載のハッシュ値生成装置であって、
２５６ビットのハッシュ値を生成する場合には、前記数は３であること、
を特徴とするハッシュ値生成装置。
【請求項９】
コンピュータを、メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置として機能させるプログラムであって、
前記コンピュータを、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御手段として機能させること、
を特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
前記Ｆ関数は、非線形変換と、バイト置換と、行列変換と、の合成変換を複数回行うものであること、
を特徴とするプログラム。
【請求項１１】
請求項１０に記載のプログラムであって、
前記複数回は、４回であること、
を特徴とするプログラム。
【請求項１２】
請求項１０に記載のプログラムであって、
前記非線形変換は、変換前のデータに対応する変換後のデータを、予め定められた置換テーブルより抽出することで、変換を行うものであること、
を特徴とするプログラム。
【請求項１３】
請求項１０に記載のプログラムであって、
前記バイト置換は、変換前のデータを項目とする行列において、任意の列に含まれるそれぞれの項目を、それぞれ異なる列に配置する変換を行うものであること、
を特徴とするプログラム。
【請求項１４】
請求項１２に記載のプログラムであって、
前記行列変換は、変換前のデータを項目とする行列に変換行列を乗算することで、当該行列の任意の列に含まれるそれぞれの項目と、乗算後の行列における当該任意の列に対応する列に含まれるそれぞれの項目と、において０ではない項目が、予め定められた数以上となるものであること、
を特徴とするプログラム。
【請求項１５】
請求項１４に記載のプログラムであって、
５１２ビットのハッシュ値を生成する場合には、前記数は５であること、
を特徴とするプログラム。
【請求項１６】
請求項１４に記載のプログラムであって、
２５６ビットのハッシュ値を生成する場合には、前記数は３であること、
を特徴とするプログラム。
【請求項１７】
メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置が行うハッシュ値生成方法であって、
前記ハッシュ値生成装置の制御部が、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う過程を備えること、
を特徴とするハッシュ値生成方法。
【請求項１】
メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置であって、
前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御部を備えること、
を特徴とするハッシュ値生成装置。
【請求項２】
請求項１に記載のハッシュ値生成装置であって、
前記Ｆ関数は、非線形変換と、バイト置換と、行列変換と、の合成変換を複数回行うものであること、
を特徴とするハッシュ値生成装置。
【請求項３】
請求項２に記載のハッシュ値生成装置であって、
前記複数回は、４回であること、
を特徴とするハッシュ値生成装置。
【請求項４】
請求項２に記載のハッシュ値生成装置であって、
前記非線形変換は、変換前のデータに対応する変換後のデータを、予め定められた置換テーブルより抽出することで、変換を行うものであること、
を特徴とするハッシュ値生成装置。
【請求項５】
請求項２に記載のハッシュ値生成装置であって、
前記バイト置換は、変換前のデータを項目とする行列において、任意の列に含まれるそれぞれの項目を、それぞれ異なる列に配置する変換を行うものであること、
を特徴とするハッシュ値生成装置。
【請求項６】
請求項４に記載のハッシュ値生成装置であって、
前記行列変換は、変換前のデータを項目とする行列に変換行列を乗算することで、当該行列の任意の列に含まれるそれぞれの項目と、乗算後の行列における当該任意の列に対応する列に含まれるそれぞれの項目と、において０ではない項目が、予め定められた数以上となるものであること、
を特徴とするハッシュ値生成装置。
【請求項７】
請求項６に記載のハッシュ値生成装置であって、
５１２ビットのハッシュ値を生成する場合には、前記数は５であること、
を特徴とするハッシュ値生成装置。
【請求項８】
請求項６に記載のハッシュ値生成装置であって、
２５６ビットのハッシュ値を生成する場合には、前記数は３であること、
を特徴とするハッシュ値生成装置。
【請求項９】
コンピュータを、メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置として機能させるプログラムであって、
前記コンピュータを、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う制御手段として機能させること、
を特徴とするプログラム。
【請求項１０】
請求項９に記載のプログラムであって、
前記Ｆ関数は、非線形変換と、バイト置換と、行列変換と、の合成変換を複数回行うものであること、
を特徴とするプログラム。
【請求項１１】
請求項１０に記載のプログラムであって、
前記複数回は、４回であること、
を特徴とするプログラム。
【請求項１２】
請求項１０に記載のプログラムであって、
前記非線形変換は、変換前のデータに対応する変換後のデータを、予め定められた置換テーブルより抽出することで、変換を行うものであること、
を特徴とするプログラム。
【請求項１３】
請求項１０に記載のプログラムであって、
前記バイト置換は、変換前のデータを項目とする行列において、任意の列に含まれるそれぞれの項目を、それぞれ異なる列に配置する変換を行うものであること、
を特徴とするプログラム。
【請求項１４】
請求項１２に記載のプログラムであって、
前記行列変換は、変換前のデータを項目とする行列に変換行列を乗算することで、当該行列の任意の列に含まれるそれぞれの項目と、乗算後の行列における当該任意の列に対応する列に含まれるそれぞれの項目と、において０ではない項目が、予め定められた数以上となるものであること、
を特徴とするプログラム。
【請求項１５】
請求項１４に記載のプログラムであって、
５１２ビットのハッシュ値を生成する場合には、前記数は５であること、
を特徴とするプログラム。
【請求項１６】
請求項１４に記載のプログラムであって、
２５６ビットのハッシュ値を生成する場合には、前記数は３であること、
を特徴とするプログラム。
【請求項１７】
メッセージを予め定められたデータ長のブロックにして、当該ブロックを分割した複数の分割データのうちの特定の分割データをＦ関数により変換を行い、他の特定の分割データとの排他的論理和を算出する撹拌処理を含むブロック暗号を用いて、前記メッセージのハッシュ値を生成するハッシュ値生成装置が行うハッシュ値生成方法であって、
前記ハッシュ値生成装置の制御部が、前記Ｆ関数において、少なくとも非線形変換を含む変換を複数回行う過程を備えること、
を特徴とするハッシュ値生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１０−４４２５１（Ｐ２０１０−４４２５１Ａ）
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願番号】特願２００８−２０８６３５（Ｐ２００８−２０８６３５）
【出願日】平成２０年８月１３日（２００８．８．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２０年度 独立行政法人情報通信研究機構 「次世代ハッシュ関数の研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
【公開日】平成２２年２月２５日（２０１０．２．２５）
【国際特許分類】
【出願日】平成２０年８月１３日（２００８．８．１３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２０年度 独立行政法人情報通信研究機構 「次世代ハッシュ関数の研究開発」委託研究、産業技術力強化法第１９条の適用を受ける特許出願）
【出願人】（０００００５１０８）株式会社日立製作所 (27,607)
【Ｆターム（参考）】
[ Back to top ]