JP5000365B2 - ハッシュ値生成装置、プログラム及びハッシュ値生成方法 - Google Patents

Description

本発明は、ハッシュ値を生成する技術に関する。

近年、携帯電話端末、非接触型ＩＣカード、商品タグ等のようにモビリティの高いデバイスを用いたサービスが急速に拡大している。

このようなモビリティの高いデバイスを用いたサービスでは、サービス提供者や被提供者を識別するために、認証技術が通常用いられる。

ここで、認証技術としては、ＭＡＣ（Message Authentication Code: メッセージ認証子）生成方法を用いたものがよく知られているが、ＭＡＣ生成方法として、暗号学的ハッシュ関数に基づいたＭＡＣ生成方法であるＨＭＡＣ構成法がある。

ハッシュ関数は任意長のメッセージを入力として、ハッシュ値を生成して出力する。一般的に、ハッシュ関数は固定長のメッセージブロックを入力するブロック暗号から構成され、入力されたメッセージに対してブロック暗号化を繰り返し行うことで、メッセージの攪拌を行い、最終的にハッシュ値として出力する。ハッシュ関数の代表例としてはＳＨＡ−１、ＳＨＡ−２５６、Ｗｈｉｒｌｐｏｏｌといったものがある（非特許文献１参照）。

「ISO/IEC 10118-3情報セキュリティ-ハッシュ関数-(ISO/IEC 10118-3, third edition, Information technology-Security techniques-Hash-functions-)」, (スイス), 第三版, 2004年3月1日, pp 13-15, pp 19-22

ハッシュ関数の代表例として知られているＳＨＡ−１、ＳＨＡ−２５６、Ｗｈｉｒｌｐｏｏｌについては、以下のような問題がある。

まず、ＳＨＡ−１については、衝突耐性という理論的安全性に問題があることが指摘されている。

次に、ＳＨＡ−２５６については、安全性の評価を厳密に行うことは困難であり、特に、現存する攻撃方法で最も脅威とされる差分攻撃法に対する耐性についての厳密な安全性評価は今のところ知られていない。

さらに、Ｗｈｉｒｌｐｏｏｌに関しては、その安全性は評価されているが、主に高速性を重点において設計されているため、携帯電話端末、非接触型ＩＣカード、商品タグ等のようにモビリティの高いデバイス等のような軽量実装向けとはいえない。

そこで、本発明は、実装規模が小さく理論的安全性と実装安全性が保証されたハッシュ関数を提供することを目的とする。

以上の課題を解決するため、本発明は、入力されたメッセージを予め定められたデータ長のメッセージブロックに分割し、メッセージブロック毎に予め定められた変換処理を繰り返し行う際に、複数回のシフトを行うシフト変換を実行し、少なくとも一つのシフトでは、奇数ビットのシフトを行い、少なくとも一つのシフトでは、偶数ビットのシフトを行う。

例えば、本発明は、入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備えるハッシュ値生成装置であって、前記制御部が行う前記変換処理には、シフト変換が含まれており、前記シフト変換は、入力された二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を予め定められた回数行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、奇数ビットのシフトを行うものであり、前記予め定められた回数の巡回シフトの内、少なくとも一つのシフトでは、偶数ビットのシフトを行うものであること、を特徴とする。

以上のように、本発明によれば、実装規模が小さく理論的安全性と実装安全性が保証されたハッシュ関数を提供することができる。

図１は、本発明の第一の実施形態であるハッシュ値生成装置１００の概略図である。

図示するように、ハッシュ値生成装置１００は、記憶部１１０と、制御部１２０と、入出力部１３０と、を備える。

記憶部１１０は、初期値記憶領域１１１と、鍵ステート記憶領域１１２と、第一の平文ステート記憶領域１１３と、第二の平文ステート記憶領域１１４と、を備える。

初期値記憶領域１１１には、ハッシュ値を生成する際の初期値を特定する情報が格納される。

本実施形態においては、ハッシュ値を生成する際の初期値として、ラウンド定数の初期値と、ラウンド鍵の初期値と、が記憶される。

ここで、ラウンド定数の初期値は、例えば、ｃ（０）＝0xcae1ac3f55054a96といった定数が記憶される。

また、ラウンド鍵の初期値は、Ｋ_０ ^（０）＝0xbc18bf6d、Ｋ_１ ^（０）＝0x369c955b、Ｋ_２ ^（０）＝0xbb271cbc、Ｋ_３ ^（０）＝0xdd66c368、Ｋ_４ ^（０）＝0x356dba5b、Ｋ_５ ^（０）＝0x33c00055、Ｋ_６ ^（０）＝0x50d2320b、Ｋ_７ ^（０）＝0x1c617e21といった定数が記憶される。

なお、ラウンド定数及びラウンド鍵の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。

鍵ステート記憶領域１１２には、メッセージブロック毎におけるラウンド毎でのラウンド鍵を特定する情報が格納される。

ここで、本実施形態においては、メッセージブロック毎におけるラウンド毎でのラウンド鍵を後述する変換部１２３で生成して、鍵ステート記憶領域１１２に記憶する。

第一の平文ステート記憶領域１１３には、ラウンド毎に算出される第一の平文を特定する情報が格納される。

ここで、本実施形態においては、ラウンド毎に第一の平文を後述する変換部１２３で算出して、第一の平文ステート記憶領域１１３に記憶する。

第二の平文ステート記憶領域１１４には、メッセージブロック毎に算出される第二の平文を特定する情報が格納される。

ここで、本実施形態においては、メッセージブロック毎に第二の平文を後述する変換部１２３で算出して、第二の平文ステート記憶領域１１４に記憶する。

制御部１２０は、メッセージブロック化部１２１と、ラウンド定数生成部１２２と、変換部１２３と、管理部１２４と、全体制御部１２５と、を備える。

メッセージブロック化部１２１は、後述する入出力部１３０を介して入力されたメッセージを予め定められたデータ長のメッセージブロックに分割する処理を行う。

ここで、本実施形態においては、メッセージブロック化部１２１は、後述する入出力部１３０を介して入力されたメッセージを、２５６ビットのメッセージブロックに分割する。

但し、メッセージ長がメッセージブロック（２５６ビット）の倍数ではない場合は、Merkle-Damgaard方式等のパディング方式を用いてメッセージブロックの倍数になるようにパディングを行う。

ラウンド定数生成部１２２は、各ラウンドにおけるラウンド定数を算出する。

本実施形態においては、初期値記憶領域１１１に記憶されているラウンド定数の初期値から各ラウンドにおけるラウンド定数を算出する。

なお、本実施形態では、ラウンド定数生成部１２２として、６４ビットの線形変換である線形フィードバックシフトレジスタＬＲを用いる。

一般に、線形フィードバックシフトレジスタは定義多項式で決定されるが、ここではＬＲを決定する定義多項式ｇ（ｘ）は、次のように定義する。

g(x) = x⁶³ + x⁶² + x⁵⁸ + x⁵⁵ + x⁵⁴ + x⁵²+ x⁵⁰ + x⁴⁹ + x⁴⁶ + x⁴³ + x⁴⁰ + x³⁸ + x³⁷ + x³⁵ + x³⁴ + x³⁰ + x²⁸ + x²⁶ + x²⁴ + x²³ + x²² + x¹⁸ + x¹⁷ + x¹² + x¹¹ + x¹⁰+ x⁷ + x³ + x² + 1
但し、ｇは有限体ＧＦ（２）において定義される多項式である。

線形フィードバックシフトレジスタＬＲは、ｃ（０）を初期値とし、第ｒ−１ラウンド定数の基礎値ｃ（ｒ−１）から、第ｒラウンドのラウンド定数の基礎値ｃ（ｒ）を生成する。次に、ラウンド定数生成部１２２はラウンド定数の基礎値ｃ（ｒ）の下位ブロックをラウンド定数Ｃ（ｒ）とする。以下、具体的に説明する。

まず、ラウンド定数生成部１２２は、第ｒ−１ラウンドのラウンド定数の基礎値ｃ（ｒ−１）を線形フィードバックシフトレジスタＬＲに入力することで出力値を算出する（出力値：y_H ^(r)||y_L ^(r) = LR(c(r -1))）。

ここで、ｙ_Lは、基礎値ｃ（ｒ−１）の下位ブロックを予め定められたビット数（本実施形態では、１ビット）だけ、左シフトしたもの。即ち、y_L ^(r) = c(r -1)_L << 1 (<< 1は1ビットによる左シフトを表現)。

また、ｙ_Hは、基礎値ｃ（ｒ−１）の上位ブロックを予め定められたビット数（本実施形態では、３１ビット）だけ、左シフトしたもの。即ち、y_H ^(r)= (c(r -1)_H << 1)|| (y_L >> 31) (>> 31は31ビットによる右シフトを表現)。

但し、ｃ（ｒ−１）の最上位ビットが「１」の場合のみ、y_H ^(r) =c(r-1)_H XOR 0xc4d6496c、y_L ^(r) =c(r-1)_L XOR 0x55c61c8d、を用いる。

次に、ラウンド定数生成部１２２は、ＬＲの出力値の上位ビットと下位ビットとを入れ替えることで、第ｒラウンドのラウンド定数の基礎値ｃ（ｒ）を算出する（c(r) = y_L ^(r)||y_H ^(r)）。

そして、ラウンド定数生成部１２２は、次のラウンドのラウンド定数の基礎値ｃ（ｒ）の下位ビットをラウンド定数Ｃ（ｒ）とする（C(r) = c(r)_L= y_H ^(r)）。

以下に、R=９６の場合におけるＣ（ｒ）の一例を掲げる。

C(0) = 0x51151113; C(1) = 0x3b4f5a2f; C(2) = 0x2b0e343a;C(3) = 0x46b151a6; C(4) = 0xac38d0e9; C(5) = 0xde130ff4;C(6) = 0x1b6f7abf; C(7) = 0xbc9a76bc; C(8) = 0xc631d3e6;C(9) = 0xf269daf1; C(10) = 0xdc1106f5; C(11) = 0xa6fd1bb3;C(12) = 0x1f1e6ba2; C(13) = 0x307857d6; C(14) = 0x7c79ae88;C(15) = 0xc1e15f59; C(16) = 0x3530f34d; C(17) = 0x68df0d12;C(18) = 0x7f4ff42f; C(19) = 0x67aa7d25; C(20) = 0x9265a0cb;C(21) = 0xf1f384e2; C(22) = 0xe21aba37; C(23) = 0x03185ae5;C(24) = 0xe73098aa; C(25) = 0xa7ed528f; C(26) = 0x58142bc4;C(27) = 0x34397327; C(28) = 0xa486e67c; C(29) = 0x7b69f586;C(30) = 0x921b99f1; C(31) = 0x29719f74; C(32) = 0xe3e25ede;C(33) = 0xa5c67dd1; C(34) = 0x4b5f3214; C(35) = 0x3c95ce5f;C(36) = 0xe9aa813c; C(37) = 0x59db0067; C(38) = 0x627c4d9d;C(39) = 0x083671eb; C(40) = 0xe6ab4602; C(41) = 0x8b55feb7;C(42) = 0x5e7b5164; C(43) = 0x86dbc3c7; C(44) = 0xbd3b0cfc;C(45) = 0xb0e33606; C(46) = 0xf4ec33f0; C(47) = 0xc38cd819;C(48) = 0x176686ad; C(49) = 0x61691012; C(50) = 0xf61623af;C(51) = 0x41720925; C(52) = 0xb702fecb; C(53) = 0x6a9254e2;C(54) = 0x7787c237; C(55) = 0x6e9f1ae5; C(56) = 0xb14578ab;C(57) = 0xd5261be2; C(58) = 0x6e99dbb7; C(59) = 0x904e26e5;C(60) = 0xd53d1eaa; C(61) = 0xeab4a28f; C(62) = 0x902233c5;C(63) = 0xc588fa4a; C(64) = 0xeb04f60f; C(65) = 0xd2f5a045;C(66) = 0xc349a84b; C(67) = 0x248cf163; C(68) = 0x627cd15a;C(69) = 0x39bffc97; C(70) = 0x4d250c04; C(71) = 0x4d73cb47;C(72) = 0xf042797d; C(73) = 0x5a955d6b; C(74) = 0xae539583;C(75) = 0x050f05da; C(76) = 0x12c26f16; C(77) = 0x143c1768;C(78) = 0x4b09bc58; C(79) = 0x50f05da1; C(80) = 0xe8f0b80d;C(81) = 0x2c9b06f3; C(82) = 0xcc989042; C(83) = 0x19e022d7;C(84) = 0xf6b40864; C(85) = 0xcc0cb247; C(86) = 0x1e0668fd;C(87) = 0x5f68b96a; C(88) = 0xd3959aef; C(89) = 0xb974acc5;C(90) = 0x210c1bca; C(91) = 0x4e5e8a0e; C(92) = 0x84306f29;C(93) = 0xfdac6154; C(94) = 0xbb4d85bf; C(95) = 0x3267cc3c:
変換部１２３は、メッセージブロック毎におけるラウンド毎に、ラウンド鍵及び第一の平文の変換を行う。ここで、変換部で行う変換には、算術加算を含まない。

ここで、本実施形態における変換部１２３は、まず、ラウンド鍵の変換を行う。

ラウンド鍵の変換は、例えば、図２（鍵ステート変換関数ｆ_ｋの概略図）に示す鍵ステート変換関数ｆ_ｋにより行う。

図示するように鍵ステート変換ｆ_ｋは、第ｒラウンドのラウンド鍵を８分割したＫ_０ ^（ｒ）、Ｋ_１ ^（ｒ）、Ｋ_２ ^（ｒ）、Ｋ_３ ^（ｒ）、Ｋ_４ ^（ｒ）、Ｋ_５ ^（ｒ）、Ｋ_６ ^（ｒ）、Ｋ_７ ^（ｒ）を、それぞれ、Ｋ_０ ^{（ｒ＋１）}、Ｋ_１ ^{（ｒ＋１）}、Ｋ_２ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}、Ｋ_４ ^{（ｒ＋１）}、Ｋ_５ ^{（ｒ＋１）}、Ｋ_６ ^{（ｒ＋１）}、Ｋ_７ ^{（ｒ＋１）}に変換し、変換したこれらの値を連結することで、第ｒ＋１ラウンドのラウンド鍵を生成する関数である。

具体的には、鍵ステート変換関数ｆ_ｋは、まず、変換部１２３が、鍵ステート記憶領域１１２に記憶されている第ｒラウンドのラウンド鍵を、Ｋ_０ ^（ｒ）、Ｋ_１ ^（ｒ）、Ｋ_２ ^（ｒ）、Ｋ_３ ^（ｒ）、Ｋ_４ ^（ｒ）、Ｋ_５ ^（ｒ）、Ｋ_６ ^（ｒ）、Ｋ_７ ^（ｒ）に８等分する。

次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ_０ ^（ｒ）、Ｋ_１ ^（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵の内のＫ_２ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}とする。

次に、変換部１２３は、ラウンド定数生成部１２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ_４ ^（ｒ）の排他的論理和と、第ｒラウンドのラウンド鍵の内のＫ_５ ^（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の上位ビットの値ｂ_Ｈを算出する（b_H = F(k₄ XOR C(r), k₅)_Ｈ）。

次に、変換部１２３は、ラウンド定数生成部１２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ_４ ^（ｒ）の排他的論理和と、第ｒラウンドのラウンド鍵の内のＫ_５ ^（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の下位ビットの値ｂ_Ｌを算出する（b_Ｌ = F(k₄ XOR C(r), k₅)_Ｌ）。

次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ_２ ^（ｒ）、Ｋ_３ ^（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵Ｋ_４ ^{（ｒ＋１）}、Ｋ_５ ^{（ｒ＋１）}とする。

次に、変換部１２３は、値ｂ_Ｈと、第ｒラウンドのラウンド鍵の内のＫ_６ ^（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドのラウンド鍵のＫ_０ ^{（ｒ＋１）}とする。

次に、変換部１２３は、値ｂ_Ｌと、第ｒラウンドのラウンド鍵の内のＫ_７ ^（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドのラウンド鍵のＫ_１ ^{（ｒ＋１）}とする。

次に、変換部１２３は、第ｒラウンドのラウンド鍵の内のＫ_４ ^（ｒ）、Ｋ_５ ^（ｒ）を、それぞれ第ｒ＋１ラウンドのラウンド鍵Ｋ_６ ^{（ｒ＋１）}、Ｋ_７ ^{（ｒ＋１）}とする。

そして、変換部１２３は、以上のようにして算出したＫ_０ ^{（ｒ＋１）}、Ｋ_１ ^{（ｒ＋１）}、Ｋ_２ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}、Ｋ_４ ^{（ｒ＋１）}、Ｋ_５ ^{（ｒ＋１）}、Ｋ_６ ^{（ｒ＋１）}、Ｋ_７ ^{（ｒ＋１）}を連結して第ｒ＋１ラウンドのラウンド鍵として、第ｒラウンドのラウンド鍵と入れ替えて鍵ステート記憶領域１１２に記憶する。

また、本実施形態における変換部１２３は、第一の平文の変換を行う。

第一の平文の変換は、例えば、図３（平文ステート変換関数ｆ_Ｒの概略図）に示す平文ステート変換関数ｆ_Ｒにより行う。

図示するように平文ステート変換ｆ_Ｒは、第ｒラウンドの第一の平文を８分割したワードＸ_０ ^（ｒ）、Ｘ_１ ^（ｒ）、Ｘ_２ ^（ｒ）、Ｘ_３ ^（ｒ）、Ｘ_４ ^（ｒ）、Ｘ_５ ^（ｒ）、Ｘ_６ ^（ｒ）、Ｘ_７ ^（ｒ）を、それぞれ、Ｘ_０ ^{（ｒ＋１）}、Ｘ_１ ^{（ｒ＋１）}、Ｘ_２ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}、Ｘ_４ ^{（ｒ＋１）}、Ｘ_５ ^{（ｒ＋１）}、Ｘ_６ ^{（ｒ＋１）}、Ｘ_７ ^{（ｒ＋１）}に変換し、変換したこれらのワードの値を連結することで、第ｒ＋１ラウンドの第一の平文を生成する関数である。

具体的には、平文ステート変換ｆ_Ｒは、まず、変換部１２３が、平文ステート変換関数ｆ_Ｒを用いて、第一の平文ステート記憶領域１１３に記憶されている第ｒラウンドの第一の平文を、ワードＸ_０ ^（ｒ）、Ｘ_１ ^（ｒ）、Ｘ_２ ^（ｒ）、Ｘ_３ ^（ｒ）、Ｘ_４ ^（ｒ）、Ｘ_５ ^（ｒ）、Ｘ_６ ^（ｒ）、Ｘ_７ ^（ｒ）に８分割する。

次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ_０ ^（ｒ）、Ｘ_１ ^（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ_２ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}とする。

次に、変換部１２３は、鍵ステート記憶領域１１２に記憶されているラウンド鍵Ｋ（ｒ）及び第ｒラウンドの第一の平文のワードＸ_４ ^（ｒ）の排他的論理和と、第ｒラウンドの第一の平文のワードＸ_５ ^（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の上位ビットの値ｂ_Ｈを算出する（b_H = F(X₄ XOR K(r), X₅)_Ｈ）。

次に、変換部１２３は、鍵ステート記憶領域１１２に記憶されているラウンド鍵Ｋ（ｒ）及び第ｒラウンドの第一の平文のワードＸ_４ ^（ｒ）の排他的論理和と、第ｒラウンドの第一の平文のワードＸ_５ ^（ｒ）の値を非線形変換関数Ｆに入力した出力値の内の下位ビットの値ｂ_Lを算出する（b_L = F(X₄ XOR K(r), X₅)_L）。

次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ_２ ^（ｒ）、Ｘ_３ ^（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ_４ ^{（ｒ＋１）}、Ｘ_５ ^{（ｒ＋１）}とする。

次に、変換部１２３は、値ｂ_Ｈと、第ｒラウンドの第一の平文のワードＸ_６ ^（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドの第一の平文のワードＸ_０ ^{（ｒ＋１）}とする。

次に、変換部１２３は、値ｂ_Ｌと、第ｒラウンドの第一の平文のワードＸ_７ ^（ｒ）と、の排他的論理和を算出し、算出した値を第ｒ＋１ラウンドの第一の平文のワードＸ_１ ^{（ｒ＋１）}とする。

次に、変換部１２３は、第ｒラウンドの第一の平文のワードＸ_４ ^（ｒ）、Ｘ_５ ^（ｒ）を、それぞれ第ｒ＋１ラウンドの第一の平文のワードＸ_６ ^{（ｒ＋１）}、Ｘ_７ ^{（ｒ＋１）}とする。

そして、変換部１２３は、以上のようにして算出したワードＸ_０ ^{（ｒ＋１）}、Ｘ_１ ^{（ｒ＋１）}、Ｘ_２ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}、Ｘ_４ ^{（ｒ＋１）}、Ｘ_５ ^{（ｒ＋１）}、Ｘ_６ ^{（ｒ＋１）}、Ｘ_７ ^{（ｒ＋１）}を連結して第ｒ＋１ラウンドの第一の平文として、第ｒラウンドの第一の平文に入れ替えて第一の平文ステート記憶領域１１３に記憶する。

次に、図２及び図３における非線形変換関数Ｆについて図４を用いて説明する。

図４は、非線形変換関数Ｆの概略図である。

図示するように、非線形変換関数Ｆは、非線形変換関数ＮＬと、線形変換関数Ｌと、の合成変換を行う関数である。これらの非線形変換関数ＮＬ及び線形変換関数Ｌは、２ブロック入力かつ２ブロック出力の変換であり、非線形変換関数Ｆは、これらの二つの変換関数の合成として、Ｆ＝Ｌ（ＮＬ）のように定義される。

まず、非線形変換関数ＮＬについて説明する。

ここで、非線形変換関数ＮＬへの二つの入力ブロックをａ_Ｈ、ａ_Ｌとする。

非線形変換関数ＮＬに入力されるそれぞれのブロックは４ビット毎に区切られ、４ビット毎に対応する値を特定した置換テーブルＳを用いて非線形変換される（a_H,i+16||a_{H, i} ||a_{L, i+16}||a_L,i ← S[a_H,i+16||a_H,i||a_{L, i+16}||a_L,i ], 0≦ i ＜ 16）。ここで，a_{H, i} (a_{H, i})は a_H (a_L)_,の下位から数えてi番目のビットをそれぞれ表し，記号S[x]は置換表Sの参照を表す。

なお、例えば、置換テーブルＳは、Ｓ[２５６]＝｛４，１４，１５，１，１３，９，１０，０，１１，２，７，１２，３，６，８，５｝として定義される。

また、このような置換テーブルＳではなく、例えば、有限体における逆元演算とアフィン変換の合成変換を用いてもよい。

次に、線形変換関数Ｌについて説明する。

ここで、線形変換関数Ｌへの二つの入力ブロックをｄ_Ｈ、ｄ_Ｌとする。

線形変換関数Ｌは、巡回シフト関数と排他的論理和で構成されており、以下のように巡回シフト関数を６回適用する変換を行い、ｄ_Ｈ、ｄ_Ｌの値を更新する。ここで巡回シフト関数ＣＳＨ（ｑ、ｘ）は、ブロック幅におけるｘのｑビットでの左巡回シフトを表す。

まず、変換部１２３は、入力ブロックｄ_Ｈの値をｑ_１ビットだけ左巡回シフトしたものに、入力ブロックｄ_Ｌの値を排他的論理和演算することで、値ｔ_１を算出する（t₁ = d_L XOR CSH(q₁, d_H)）。

次に、変換部１２３は、値ｔ_１をｑ_２ビットだけ左巡回シフトしたものに、入力ブロックｄ_Ｈの値を排他的論理和演算することで、値ｕ_１を算出する（u₁ = d_H XOR CSH(q₂, t₁)）。

次に、変換部１２３は、値ｕ_１をｑ_３ビットだけ左巡回シフトしたものに、値ｔ_１を排他的論理和演算することで、値ｔ_２を算出する（t₂ = t₁ XOR CSH(q₃, u₁)）。

次に、変換部１２３は、値ｔ_２をｑ_４ビットだけ左巡回シフトしたものに、値ｕ_１を排他的論理和演算することで、値ｕ_２を算出する（u₂ = u₁ XOR CSH(q₄, t₂)）。

次に、変換部１２３は、値ｕ_２をｑ_５ビットだけ左巡回シフトしたものに、値ｔ_２を排他的論理和演算することで、値ｔ_３を算出する（t₃ = t₂ XOR CSH(q₅, u₂)）。

次に、変換部１２３は、値ｔ_３をｑ_６ビットだけ左巡回シフトしたものに、値ｕ_２を排他的論理和演算することで、値ｕ_３を算出する（u₃ = u₂ XOR CSH (q6, t₃)）。

このようにして算出された値ｕ_３と値ｔ_３とを連結することで、変換部１２３は、出力値ｂを算出する。

ここで、左巡回シフトするｑ_１、ｑ_２、ｑ_３、ｑ_４、ｑ_５、ｑ_６の値は、少なくとも一つは奇数であり、かつ、少なくとも一つは偶数であるような値の組み合わせを用いる。

そして、このような組み合わせの内、１３個の値ｑ_１＋ｑ_２、ｑ_１＋ｑ_４、ｑ_３＋ｑ_４、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４、ｑ_１＋ｑ_６、ｑ_３＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_６、ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにすることが望ましい。

本実施形態においては、（ｑ_１、ｑ_２、ｑ_３、ｑ_４、ｑ_５、ｑ_６）＝（１、３、４、７、８、１４）を用いているが、このような態様に限定されるわけではない。

なお、以上のように、ｑ_１、ｑ_２、ｑ_３、ｑ_４、ｑ_５、ｑ_６の値を選択することで、従来より少ない処理量で、安全性を保証することができるようになる。即ち、少ないシフト回数で安全性を確保することができる。また、合成処理において算術加算を使用していないので、計算量が少なくてすみ、軽実装が可能となる。

以上に記載されたラウンド定数生成部１２２及び変換部１２３での処理については、図５（ブロック暗号を説明する概略図）に示すブロック暗号を用いたものである。

このブロック暗号ではデータ処理を３つの処理関数に分割しており、図５の左からラウンド定数生成関数、鍵スケジューリング関数、主攪拌関数と呼ぶ。

図からもわかるように、いずれも入力に対して単一関数を繰り返し（本実施形態では、ＲＯＵＮＤ ＮＵＭ回数）作用させる処理である。３つの処理関数の処理単位関数をそれぞれラウンド定数生成関数ｆ_Ｃ、ラウンド鍵生成関数ｆ_Ｋ（図２、図９の鍵ステート変換に対応）、ラウンド関数ｆ_Ｒ（図３、図１０の平文ステート変換に対応）と呼ぶ。

ラウンド定数生成関数はラウンド定数初期値ｃ（０）をラウンド定数生成関数ｆ_Ｃに入力することで、ラウンド定数生成関数ｆ_Ｃの処理毎に次々とラウンド定数Ｃ（ｒ）を生成する。

このようにして生成されたラウンド定数Ｃ（ｒ）をラウンド鍵生成関数ｆ_Ｋへの補助入力とし、ラウンド鍵の初期値をラウンド鍵生成関数ｆ_Ｋに入力することで、鍵スケジューリング関数は、ラウンド鍵生成関数ｆ_Ｋの処理毎に次々とラウンド鍵Ｋ（ｒ）を生成する。

そして、鍵スケジューリング関数で生成された生成されたラウンド鍵Ｋ（ｒ）をラウンド関数ｆ_Ｒへの補助入力とし、メッセージブロックをラウンド関数ｆ_Ｒに入力することで、主攪拌関数は、ラウンド関数ｆ_Ｒの処理を予め定められたラウンド繰り返し行うことで、暗号文を出力する。

ここで、本実施形態では、ラウンド鍵生成関数ｆ_Ｋとラウンド関数ｆ_Ｒとにおいて同じ関数を用いることで、実装規模の小さい装置においても論理安全性と実装安全性が保証されたハッシュ関数を生成することができるようになる。

管理部１２４は、メッセージブロックにおいて予め定められたラウンドの第一の平文の変更処理を終了することにより算出された第一の平文と、第ｎメッセージブロックの第二の平文と、の排他的論理和を算出することで、第ｎ＋１メッセージブロックの第二の平文を算出して、第ｎメッセージブロックの第二の平文と入れ替えて第二の平文ステート記憶領域１１４に記憶する。

また、管理部１２４は、全てのメッセージブロックについて予め定められたラウンドの第一の平文の変更処理が終了し、第二の平文を算出して第二の平文ステート記憶領域１１４に記憶した場合には、当該第二の平文ステート記憶領域１１４に記憶した第二の平文をハッシュ値として後述する入出力部１３０を介して出力する処理を行う。

全体制御部１２５は、ハッシュ値生成装置１００においてハッシュ値を生成する処理の全体を制御する。

特に、本実施形態においては、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に記憶されている情報のリセットや、メッセージブロック数やラウンド数をカウントする処理、鍵ステート記憶領域１１２にラウンド鍵の初期値又は第二の平文をセットする処理を行う。

入出力部１３０は、データの入出力を行う。

以上に記載したハッシュ値生成装置１００は、例えば、図６（コンピュータ５００の概略図）に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体５０４から情報を読み出す読取装置５０５と、キーボードやマウスなどの入力装置５０６と、ディスプレイなどの出力装置５０７と、通信ネットワークに接続するためのＮＩＣ（Network Interface Card）等の通信装置５０８と、を備えた一般的なコンピュータ５００で実現できる。

例えば、記憶部１１０は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部１２０は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入出力部１３０は、ＣＰＵ２０１が出力装置５０７及び入力装置５０６を利用することで実現可能である。

この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。

以上のように構成されるハッシュ値生成装置１００におけるハッシュ値の生成処理を図７に示すフローチャートを用いて説明する。

まず、ハッシュ値生成装置１００は、入出力部１３０を介してハッシュ値を生成する元となるメッセージを取得する（Ｓ１０）。

次に、メッセージブロック化部１２１は、入出力部１３０を介して取得したメッセージを予め定められたデータ長に分割することによりＮ個のメッセージブロックを生成する（Ｓ１１）。ここで、本実施形態においては、メッセージを２５６ビットのデータ長のメッセージブロックに分割するようにしている。

次に、全体制御部１２５は、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に記憶されている情報のリセットを行う（Ｓ１２）。具体的には、全てのビット値を「０」にする。

次に、全体制御部１２５は、メッセージブロックのカウンタであるメッセージカウンタｎの値を初期化する（Ｓ１３）。ここでは、メッセージカウンタｎの値に「１」を代入する。

次に、全体制御部１２５は、メッセージカウンタｎの値がメッセージを分割した分割数Ｎに対して、ｎ＝Ｎ＋１となっているか否かを判断する（Ｓ１４）。

ステップＳ１４で、ｎ＝Ｎ＋１となっている場合には、ステップＳ１５に進み、第二の平文ステート記憶領域１１４に記憶されている第二の平文をハッシュ値として入出力部１３０を介して出力して（Ｓ１５）、処理を終了する。

ステップＳ１４で、ｎ＝Ｎ＋１となっていない場合には、ステップＳ１６に進む。

ステップＳ１６では、全体制御部１２５は、鍵ステート記憶領域１１２、第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に所定のデータを格納（セット）し、ラウンドのカウンタであるラウンドカウンタｒに初期値を代入する。

ここで、全体制御部１２５は、ｎ＝１の場合には、初期値記憶領域１１１に記憶されているラウンド鍵の初期値を鍵ステート記憶領域１１２に格納し、メッセージカウンタｎに対応するメッセージブロックＭｎを第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に格納して、ラウンドカウンタｒに「１」を代入する。

一方、全体制御部１２５は、ｎ＞１の場合には、第二の平文ステート記憶領域１１４に記憶されている第二の平文を鍵ステート記憶領域１１２に格納し、メッセージカウンタｎに対応するメッセージブロックＭｎを第一の平文ステート記憶領域１１３及び第二の平文ステート記憶領域１１４に格納して、ラウンドカウンタｒに「１」を代入する。

次に、全体制御部１２５は、ラウンドカウンタｒの値が、予め定められたラウンド数（ＲＯＵＮＤ ＮＵＭ）に対して、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にあるか否かを判断する（Ｓ１７）。ステップＳ１７において、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にある場合には、ステップＳ２０に進み、ｒ＝（ＲＯＵＮＤ ＮＵＭ）＋１の関係にない場合には、ステップＳ１８に進む。

ステップＳ１８では、ラウンド定数生成部１２２及び変換部１２３において鍵ステート記憶領域１１２に記憶されているラウンド鍵及び第一の平文ステート記憶領域１１３に記憶されている第一の平文を更新する。

具体的には、ラウンド定数生成部１２２においてラウンドカウンタｒに対応するカウンタにおけるラウンド定数Ｃ（ｒ）を算出する。

そして、変換部１２３は、ラウンド定数生成部１２２において算出したラウンド定数Ｃ（ｒ）を補助入力として、鍵ステート記憶領域１１２に記憶されているラウンドカウンタｒ−１に対応するラウンドにおけるラウンド鍵Ｋ^{（ｒ−１）}から、ラウンドカウンタｒに対応するラウンドにおけるラウンド鍵Ｋ^（ｒ）を算出する。ここで、変換部１２３は、このようにして算出したラウンド鍵Ｋ^（ｒ）を、ラウンド鍵Ｋ^{（ｒ−１）}に代えて鍵ステート記憶領域１１２に記憶する。

そして、変換部１２３は、ラウンド定数生成部１２２において算出したラウンド鍵Ｋ^（ｒ）を補助入力として、第一の平文ステート記憶領域１１３に記憶されているラウンドカウンタｒ−１に対応するラウンドにおける第一の平文Ｘ^{（ｒ−１）}からラウンドカウンタｒに対応するラウンドにおける第一の平文Ｘ^（ｒ）を算出する。ここで、変換部１２３は、このようにして算出した第一の平文Ｘ^（ｒ）を、第一の平文Ｘ^{（ｒ−１）}に代えて第一の平文ステート記憶領域１１３に記憶する。

次に、全体制御部１２５は、ラウンドカウンタｒの値に「１」をインクリメントして、ステップＳ１７に戻って処理を繰り返す。

また、ステップＳ２０では、管理部１２４は、第二の平文ステート記憶領域１１４に記憶されている第二の平文と、第一の平文ステート記憶領域１１３に記憶されている第一の平文と、の排他的論理和を算出することにより次の第二の平文を算出し、第二の平文ステート記憶領域１１４に既に記憶されている第二の平文に代えて、算出した次の第二の平文を記憶する。

そして、全体制御部１２５は、メッセージカウンタｎの値に「１」をインクリメントして（Ｓ２１）、ステップＳ１４に戻って処理を繰り返す。

以上のように、本実施形態においては、２５６ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができるとともに、変換部でラウンド鍵と第一の平文を変換する関数として同じ関数を用いているため、実装規模を小さくすることが可能となる。

図８は、本発明の第二の実施形態であるハッシュ値生成装置２００の概略図である。

第一の実施形態においては、ハッシュ値生成装置１００で生成するハッシュ値は２５６ビットであったが、本実施形態においては、１６０ビットのハッシュ値を生成するようにしている。

図示するように、ハッシュ値生成装置２００は、記憶部２１０と、制御部２２０と、入出力部１３０と、を備える。

記憶部２１０は、初期値記憶領域２１１と、鍵ステート記憶領域２１２と、第一の平文ステート記憶領域２１３と、第二の平文ステート記憶領域２１４と、を備える。

初期値記憶領域２１１には、第一の実施形態と同様に、ハッシュ値を生成する際の初期値として、ラウンド定数の初期値と、ラウンド鍵の初期値と、が記憶される。

ここで、ラウンド定数の初期値は、例えば、ｃ（０）＝0xcae1ac3f55054a96といった定数が記憶される。

また、ラウンド鍵の初期値は、例えば、Ｋ_０ ^（０）＝0xbc18bf6d、Ｋ_１ ^（０）＝0x369c955b、Ｋ_２ ^（０）＝0xbb271cbc、Ｋ_３ ^（０）＝0xdd66c368、Ｋ_４ ^（０）＝0x356dba5bといった定数が記憶される。

なお、ラウンド定数及びラウンド鍵の初期値に使用される定数はこれらに限定されるわけではなく、例えば、疑似乱数生成器等で生成された乱数を使用することも可能である。

鍵ステート記憶領域２１２には、第一の実施形態と同様に、各メッセージブロックにおける各ラウンドでのラウンド鍵を特定する情報が格納されるが、本実施形態においては、第一の実施形態と異なり、１６０ビットのラウンド鍵が鍵ステート記憶領域２１２に記憶される。

第一の平文ステート記憶領域２１３には、第一の実施形態と同様に、ラウンド毎に算出される第一の平文を特定する情報が格納されるが、本実施形態においては、１６０ビットの第一の平文が記憶される。

第二の平文ステート記憶領域１１４には、第一の実施形態と同様に、メッセージブロック毎に算出される第二の平文を特定する情報が格納されるが、本実施形態においては、１６０ビットの第二の平文が記憶される。

制御部２２０は、メッセージブロック化部２２１と、ラウンド定数生成部２２２と、変換部２２３と、管理部２２４と、全体制御部２２５と、を備える。

メッセージブロック化部２２１は、入出力部１３０を介して入力されたメッセージを予め定められたデータ長のブロックに分割する処理を行う。

ここで、本実施形態においては、メッセージブロック化部２２１は、後述する入出力部１３０を介して入力されたメッセージを、１６０ビットのメッセージブロックに分割する。

但し、メッセージ長がメッセージブロック（１６０ビット）の倍数ではない場合は、Merkle-Damgaard方式等のパディング方式を用いてメッセージブロックの倍数になるようにパディングを行う。

ラウンド定数生成部２２２は、第一の実施形態と同様に、各ラウンドにおけるラウンド定数を算出する。

変換部２２３は、メッセージブロック毎におけるラウンド毎に、ラウンド鍵及び第一の平文の変換を行う。ここで、変換部２２３で行う変換には、算術加算を行わない。

ここで、本実施形態における変換部２２３は、まず、ラウンド鍵の変換を行う。

ラウンド鍵の変換は、例えば、図９（鍵ステート変換関数ｆ_ｋの概略図）に示す鍵ステート変換関数ｆ_ｋにより行う。

図示するように鍵ステート変換ｆ_ｋは、第ｒラウンドのラウンド鍵を５分割したＫ_０ ^（ｒ）、Ｋ_１ ^（ｒ）、Ｋ_２ ^（ｒ）、Ｋ_３ ^（ｒ）、Ｋ_４ ^（ｒ）を、それぞれ、Ｋ_０ ^{（ｒ＋１）}、Ｋ_１ ^{（ｒ＋１）}、Ｋ_２ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}、Ｋ_４ ^{（ｒ＋１）}に変換し、変換したこれらの値を連結することで、第ｒ＋１ラウンドのラウンド鍵を生成する関数である。

具体的に、鍵ステート変換ｆ_ｋでは、まず、変換部２２３が、鍵ステート記憶領域２１２に記憶されている第ｒラウンドのラウンド鍵を、Ｋ_０ ^（ｒ）、Ｋ_１ ^（ｒ）、Ｋ_２ ^（ｒ）、Ｋ_３ ^（ｒ）、Ｋ_４ ^（ｒ）に５等分する。

次に、変換部２２３は、ラウンド定数生成部２２２で生成されたラウンド定数Ｃ（ｒ）及び第ｒラウンドのラウンド鍵の内のＫ_３ ^（ｒ）の排他的論理和を非線形変換関数Ｆに入力した出力値ｂを算出する（b = F(k_３ XOR C(r))）。

次に、変換部２２３は、出力値ｂと、第ｒラウンドのラウンド鍵の内のＫ_４ ^（ｒ）と、の排他的論理和を算出して、算出した値を第ｒ＋１ラウンドのラウンド鍵の内のＫ_０ ^{（ｒ＋１）}とする。

次に、変換部２２３は、第ｒラウンドのラウンド鍵の内のＫ_３ ^（ｒ）、Ｋ_２ ^（ｒ）、Ｋ_１ ^（ｒ）、Ｋ_０ ^（ｒ）を、それぞれ、第ｒ＋１ラウンドのラウンド鍵のＫ_４ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}、Ｋ_２ ^{（ｒ＋１）}、Ｋ_１ ^{（ｒ＋１）}とする。

そして、変換部２２３は、以上のようにして算出したＫ_０ ^{（ｒ＋１）}、Ｋ_１ ^{（ｒ＋１）}、Ｋ_２ ^{（ｒ＋１）}、Ｋ_３ ^{（ｒ＋１）}、Ｋ_４ ^{（ｒ＋１）}を連結して第ｒ＋１ラウンドのラウンド鍵として、第ｒラウンドのラウンド鍵と入れ替えて鍵ステート記憶領域２１２に記憶する。

また、本実施形態における変換部２２３は、第一の平文の変換を行う。

第一の平文の変換は、例えば、図１０（平文ステート変換関数ｆ_Ｒの概略図）に示す平文ステート変換関数ｆ_Ｒにより行う。

図示するように平文ステート変換ｆ_Ｒは、第ｒラウンドの第一の平文を５分割したワードＸ_０ ^（ｒ）、Ｘ_１ ^（ｒ）、Ｘ_２ ^（ｒ）、Ｘ_３ ^（ｒ）、Ｘ_４ ^（ｒ）を、それぞれ、Ｘ_０ ^{（ｒ＋１）}、Ｘ_１ ^{（ｒ＋１）}、Ｘ_２ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}、Ｘ_４ ^{（ｒ＋１）}に変換し、変換したこれらのワードの値を連結することで、第ｒ＋１ラウンドの第一の平文を生成する関数である。

平文ステート変換関数ｆ_Ｒは、まず、変換部２２３が、第一の平文ステート記憶領域２１３に記憶されている第ｒラウンドの第一の平文を、ワードＸ_０ ^（ｒ）、Ｘ_１ ^（ｒ）、Ｘ_２ ^（ｒ）、Ｘ_３ ^（ｒ）、Ｘ_４ ^（ｒ）に５分割する。

次に、変換部２２３は、鍵ステート記憶領域２１２に記憶されているラウンド鍵Ｋ（ｒ）と、ワードＸ_３ ^（ｒ）と、の排他的論理和を非線形変換関数Ｆに入力した出力値ｂを算出する（b = F(X_３ XOR K(r))）。

次に、変換部２２３は、出力値ｂと、ワードX_４ ^（ｒ）と、の排他的論理和を算出して、算出した値をワードＸ_０ ^{（ｒ＋１）}とする。

次に、変換部２２３は、ワードＸ_３ ^（ｒ）、Ｘ_２ ^（ｒ）、Ｘ_１ ^（ｒ）、Ｘ_０ ^（ｒ）を、それぞれ、ワードＸ_４ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}、Ｘ_２ ^{（ｒ＋１）}、Ｘ_１ ^{（ｒ＋１）}とする。

そして、変換部２２３は、以上のようにして算出したＸ_０ ^{（ｒ＋１）}、Ｘ_１ ^{（ｒ＋１）}、Ｘ_２ ^{（ｒ＋１）}、Ｘ_３ ^{（ｒ＋１）}、Ｘ_４ ^{（ｒ＋１）}を連結して第ｒ＋１ラウンドの第一の平文として、第ｒラウンドの第一の平文と入れ替えて第一の平文ステート記憶領域２１３に記憶する。

次に、図９及び図１０における非線形変換関数Ｆについて図１１を用いて説明する。

図１１は、非線形変換関数Ｆの概略図である。

図示するように、非線形変換関数Ｆは、非線形変換関数ＮＬと、線形変換関数Ｌと、の合成変換を行う関数である。

本実施形態におけるこれらの非線形変換関数ＮＬ及び線形変換関数Ｌは、１ブロック入力かつ１ブロック出力の変換であり、非線形変換関数Ｆは、これらの二つの変換関数の合成として、Ｆ＝Ｌ（ＮＬ）のように定義される。

まず、非線形変換関数ＮＬについて説明する。

ここで、非線形変換関数ＮＬへの入力ブロックをａとする。

非線形変換関数ＮＬに入力されるブロックは４ビット毎に区切られ、４ビット毎に対応する値を特定した置換テーブルＳを用いて非線形変換される（d_i+24||d_i+16||d_i+8||d_i ← S[a_i+24||a_i+16||a_i+8||a_i], 0≦ i ＜ 8）。ここで，a_iはaの下位から数えてi番目のビットをそれぞれ表し，記号S[x]は置換表Sの参照を表す。

なお、例えば、置換テーブルＳは、Ｓ[２５６]＝｛４，１４，１５，１，１３，９，１０，０，１１，２，７，１２，３，６，８，５｝として定義される。

また、このような置換テーブルＳではなく、例えば、有限体における逆元演算とアフィン変換の合成変換を用いてもよい。

次に、線形変換関数Ｌについて説明する。

ここで、線形変換関数Ｌでは、入力ブロックｄを、上位ビットのブロックｄ_Ｈ、下位ビットのブロックｄ_Ｌに分割して、下記のように処理する。

線形変換関数Ｌは、巡回シフト関数と排他的論理和で構成されており、以下のような変換を行い、ｄ_Ｈ、ｄ_Ｌの値を更新する。ここで巡回シフト関数ＣＳＨ（ｑ、ｘ）はブロック幅におけるｘのｑビットでの左巡回シフトを表す。

まず、変換部２２３は、入力ブロックｄ_Ｈの値をｑ_１ビットだけ左巡回シフトしたものに、入力ブロックｄ_Ｌの値を排他的論理和演算することで、値ｔ_１を算出する（t₁ = d_L XOR CSH(q₁, d_H)）。

次に、変換部２２３は、値ｔ_１をｑ_２ビットだけ左巡回シフトしたものに、入力ブロックｄ_Ｈの値を排他的論理和演算することで、値ｕ_１を算出する（u₁ = d_H XOR CSH(q₂, t₁)）。

次に、変換部２２３は、値ｕ_１をｑ_３ビットだけ左巡回シフトしたものに、値ｔ_１を排他的論理和演算することで、値ｔ_２を算出する（t₂ = t₁ XOR CSH(q₃, u₁)）。

次に、変換部１２３は、値ｔ_２をｑ_４ビットだけ左巡回シフトしたものに、値ｕ_１を排他的論理和演算することで、値ｕ_２を算出する（u₂ = u₁ XOR CSH(q₄, t₂)）。

このようにして算出された値ｕ_２と値ｔ_２とを連結することで、変換部２２３は、出力値ｂ（=u₂||t₂）を算出する。

ここで、左巡回シフトするｑ_１、ｑ_２、ｑ_３、ｑ_４の値は、少なくとも一つは奇数であり、かつ、少なくとも一つは偶数であるような値の組み合わせを用いる。

本実施形態においては、（ｑ_１、ｑ_２、ｑ_３、ｑ_４）＝（１、３、４、７）を用いているが、このような態様に限定されるわけではない。

以上に記載されたラウンド定数生成部２２２及び変換部２２３での処理については、第一の実施形態と同様に、図５に示すブロック暗号を用いたものである。

ここで、本実施形態では、ラウンド鍵生成関数ｆ_Ｋとラウンド関数ｆ_Ｒとにおいて同じ関数を用いることで、実装規模の小さい装置においても論理安全性と実装安全性が保証されたハッシュ関数を生成することができるようになる。

管理部２２４は、予め定められた全てのラウンドにおける第一の平文の変更処理を終了することにより算出された第一の平文と、第ｎメッセージブロックの第二の平文と、の排他的論理和を算出することで、第ｎ＋１メッセージブロックの第二の平文を算出して、第ｎメッセージブロックの第二の平文と入れ替えて第二の平文ステート記憶領域２１４に記憶する。

また、管理部２２４は、全てのメッセージブロックについて予め定められた全てのラウンドの第一の平文の変更処理が終了し、第二の平文を算出して第二の平文ステート記憶領域２１４に記憶した場合には、当該第二の平文ステート記憶領域２１４に記憶した第二の平文をハッシュ値として後述する入出力部１３０を介して出力する処理を行う。

全体制御部２２５は、ハッシュ値生成装置２００においてハッシュ値を生成する処理の全体を制御する。

特に、本実施形態においては、鍵ステート記憶領域２１２、第一の平文ステート記憶領域２１３及び第二の平文ステート記憶領域２１４に記憶されている情報のリセットや、メッセージブロック数やラウンド数をカウントする処理を行う。

入出力部１３０は、データの入出力を行う。

以上に記載したハッシュ値生成装置１００は、例えば、図６に示すようなコンピュータ５００で実現可能である。

以上のように構成されるハッシュ値生成装置２００におけるハッシュ値の生成処理については、図７に示すフローチャートと同様であるため説明を省略する。

以上のように、本実施形態においては、１６０ビットにおけるブロック暗号を用いているため、理論的安全性と実装安全性が保証されたハッシュ関数を提供することができるとともに、変換部でラウンド鍵と第一の平文を変換する関数として同じ関数を用いているため、実装規模を小さくすることが可能となる。

図１２は、本発明の第三の実施形態であるメッセージ識別子生成装置３００の概略図である。

高速かつ軽量な暗号技術は、ユビキタス社会において、サーバでは高速な処理が要求されるが、クライアントでは実装資源が限られているようなアプリケーションへの応用が期待される。以下では、第一の実施形態を利用したデータの認証および配信システムについて説明する。本実施形態においては、認証技術として、ハッシュ関数に基づいたＭＡＣ生成方法であるＨＭＡＣ構成法を用いる。

図示するように、メッセージ識別子生成装置３００は、記憶部１１０と、制御部３２０と、入出力部１３０と、通信部３４０と、を備え、記憶部１１０及び入出力部１３０については第一の実施形態と同様であるため、説明を省略する。

本実施形態における制御部３２０は、メッセージブロック化部１２１と、ラウンド定数生成部１２２と、変換部１２３と、管理部１２４と、全体制御部１２５と、メッセージ識別子生成部３２６と、を備え、第一の実施形態と比較してメッセージ識別子生成部３２６が追加されているため、以下、この点に関連する事項について説明する。

メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５で生成するハッシュ値を用いて、メッセージ識別子を生成する。

具体的には、メッセージ識別子生成部３２６は、図１３（メッセージ識別子を生成する手順を示す概略図）に示されているように、入出力部１３０を介して入力されたデータMと、予め定められた鍵情報K_１を連結して、メッセージK₁||Mを生成する。

次に、メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５を用いて、メッセージK₁||Mのハッシュ値である第一のハッシュ値h(K₁||M)を生成する。

次に、メッセージ識別子生成部３２６は、第一のハッシュ値h(K₁||M)と、鍵情報K₂と、を連結し、メッセージK₂|| (K₁||M)を生成する。

そして、メッセージ識別子生成部３２６は、メッセージブロック化部１２１、ラウンド定数生成部１２２、変換部１２３、管理部１２４及び全体制御部１２５を用いて、メッセージK₂|| (K₁||M)のハッシュ値である第二のハッシュ値h(K₂||h(K₁||M))を生成する。

そして、メッセージ識別子生成部３２６は、この第二のハッシュ値をデータMのメッセージ認証子として、入出力部１３０又は通信部３４０を介して、出力する。

メッセージ識別子生成装置３００は、例えば、図６に示すような、ＣＰＵ５０１と、メモリ５０２と、ＨＤＤ等の外部記憶装置５０３と、ＣＤ−ＲＯＭやＤＶＤ−ＲＯＭ等の可搬性を有する記憶媒体５０４から情報を読み出す読取装置５０５と、キーボードやマウスなどの入力装置５０６と、ディスプレイなどの出力装置５０７と、通信ネットワークに接続するためのＮＩＣ等の通信装置５０８と、を備えた一般的なコンピュータ５００で実現できる。

例えば、記憶部１１０は、ＣＰＵ５０１がメモリ５０２又は外部記憶装置５０３を利用することにより実現可能であり、制御部３２０は、外部記憶装置５０３に記憶されている所定のプログラムをメモリ５０２にロードしてＣＰＵ５０１で実行することで実現可能であり、入出力部１３０は、ＣＰＵ２０１が出力装置５０７及び入力装置５０６を利用することで実現可能であり、通信部３４０は、ＣＰＵ２０１が通信装置５０８を利用することで実現可能である。

この所定のプログラムは、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、外部記憶装置５０３にダウンロードされ、それから、メモリ５０２上にロードされてＣＰＵ５０１により実行されるようにしてもよい。また、読取装置５０５を介して記憶媒体５０４から、あるいは、通信装置５０８を介してネットワークから、メモリ５０２上に直接ロードされ、ＣＰＵ５０１により実行されるようにしてもよい。

以上のように構成されるメッセージ識別子生成装置３００は、例えば、図１４（配信システム４００の概略図）に示すように、第一のメッセージ識別子生成装置３００Ａと、第二のメッセージ識別子生成装置Ｂと、をネットワーク１６０を介して接続することにより利用することが可能である。

このような配信システムでは、以下のようにしてデータの送受信を行う。

なお、第一のメッセージ識別子生成装置３００Ａ及び第二のメッセージ識別子生成装置Ｂは、事前に鍵情報K₁とK₂を秘密状態で共有しているものとする。

まず、第一のメッセー識別子生成装置３００Ａは、データMを上述のようにして鍵情報K₁とK₂を用いてメッセージ認証子生成部３２６において２５６ビットの第一のメッセージ認証子Vを生成する。

そして、第一のメッセージ識別子生成装置３００Ａは、通信部３４０を介して、第一のメッセージ識別子VとデータMとを連結した結果L=M||Vをネットワーク１６０を通じて第二のメッセージ識別子生成装置３００Ｂに送信する。

第二のメッセージ識別子生成装置３００Ｂは、通信部３４０を介して、受信したデータL'=M'||V'から、２５６ビットの第二のメッセージ識別子V'を切り出すことで、第二のデータM'を取得する。

そして、第二のメッセージ識別子生成装置３００Ｂは、第二のデータM'、鍵情報K₁及びK₂から、上述のように、メッセージ認証子生成部３２６において第三のメッセージ識別子V''を生成する。

そして、第二のメッセージ識別子生成装置３００Ｂの全体制御部１２５は、第三のメッセージ識別子V''が、第二のメッセージ識別子V'と等しくない場合には、第二のデータM'に改ざんがあったもの判断する。

一方、これらのメッセージ識別子が等しい場合には、第二のメッセージ識別子生成装置３００Ｂは、受信した第二のデータM'を認証済みのデータとみなす。

以上のように、本実施形態におけるメッセージ識別子生成装置３００は、送受信するデータを認証するシステムに利用することが可能となる。

また、第三の実施形態においては、第一の実施形態で説明したハッシュ値によりメッセージ識別子を生成したが、このような態様に限定されず、第二の実施形態で説明したハッシュ値によりメッセージ識別子を生成することも可能である。

また、以上に記載した実施形態においては、鍵ステート変換ｆ_Ｋと、平文ステート変換ｆ_Ｒと、を同じ関数で構成したが、実装規模の大きな装置においては、これらの関数を別々の関数にすることも可能である。このような場合には、本実施形態に記載した鍵ステート変換ｆ_Ｋ又は平文ステート変換ｆ_Ｒの少なくともいずれか一方に、任意のシフト変換や任意の線形又は非線型関数を追加することにより、より安全性の高いハッシュ値を生成することができる。

さらに、以上に記載した実施形態においては、ハッシュ値生成装置１００、２００を図６で示すようなコンピュータで実現可能としたが、このような態様に限定されず、例えば、ＣＰＵと、発揮性又は不発揮性メモリと、通信装置と、を備える携帯電話端末、非接触型ＩＣカード、商品タグ等の実装規模の小さなデバイスにおいても実現可能である。

即ち、記憶部１１０、２１０は、メモリにより実現可能で、制御部１２０、２２０は、ＣＰＵにより実現可能で、入出力部１３０は、通信装置を介して外部のデバイスからデータの入出力を受ければよい。

また、上述したハッシュ値生成装置１００、２００は、コンピュータがプログラムを実行することにより実現されるものでなくてもよい。例えば、ＡＳＩＣ（Application Specific Integrated Circuit）やＦＰＧＡ（Field Programmable Gate Array）等の集積ロジックＩＣによりハード的に実行されるものであってもよいし、あるいは、ＤＳＰ（Digital Signal Processor）等の計算機によりソフトウェア的に実行されるものであってもよい。

第一の実施形態であるハッシュ値生成装置の概略図。 鍵ステート変換関数ｆ_ｋの概略図。 平文ステート変換関数ｆ_Ｒの概略図。 非線形変換関数Ｆの概略図。 ブロック暗号を説明する概略図。 コンピュータの概略図。 ハッシュ値生成装置におけるハッシュ値の生成処理を示すフローチャート。 第二の実施形態であるハッシュ値生成装置の概略図。 鍵ステート変換関数ｆ_ｋの概略図。 平文ステート変換関数ｆ_Ｒの概略図。 非線形変換関数Ｆの概略図。 第三の実施形態であるメッセージ識別子生成装置の概略図。 メッセージ識別子を生成する手順を示す概略図。 配信システムの概略図。

符号の説明

１００、２００ ハッシュ値生成装置
３００ メッセージ識別子生成装置
１１０、２１０ 記憶部
１１１、２１１ 初期値記憶領域
１１２、２１２ 鍵ステート記憶領域
１１３、２１３ 第一の平文ステート記憶領域
１１４、２１４ 第二の平文ステート記憶領域
１２０、２２０ 制御部
１２１、２２１ メッセージブロック化部
１２２、２２２ ラウンド定数生成部
１２３、２２３ 変換部
１２４、２２４ 管理部
１２５、２２５ 全体制御部
３２６ メッセージ識別子生成部
１３０ 入出力部
３４０ 通信部

Claims (15)

1. 入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備え、
   前記制御部は、二つのデータを入力とし、前記二つのデータを非線形変換し、二つのデータを出力する非線形変換部を備え、
   前記非線形変換部は、二つのデータを入力とし、前記二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を６回行う線型変換部を備え、
   前記６回の巡回シフトでシフトするビット数は、順番にｑ_１、ｑ_２、ｑ_３、ｑ_４、ｑ_５、ｑ_６であり、
   ｑ_１＋ｑ_２、ｑ_１＋ｑ_４、ｑ_３＋ｑ_４、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４、ｑ_１＋ｑ_６、ｑ_３＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_６、ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、の１３個の値の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにしたこと、
   を特徴とするハッシュ値生成装置。
2. 請求項１に記載のハッシュ値生成装置であって、
   前記制御部が行う前記変換処理では、合成変換が行われており、
   前記合成変換は、排他的論理和を算出するものであること、
   を特徴とするハッシュ値生成装置。
3. 請求項２に記載のハッシュ値生成装置であって、
   前記合成変換には、算術加算は含まれていないこと、
   を特徴とするハッシュ値生成装置。
4. 請求項１に記載のハッシュ値生成装置であって、
   ラウンド定数の初期値及びラウンド鍵の初期値を記憶する記憶部を備えており、
   前記制御部は、前記変換処理として、
   前記記憶部に記憶されている前記ラウンド定数の初期値からラウンド毎のラウンド定数を予め定められた関数で算出する処理と、
   ラウンドに対応する前記ラウンド定数と、前記記憶部に記憶されている前記ラウンド鍵の初期値から前回のラウンドで算出されたラウンド鍵と、予め定められた鍵変換関数に入力することによりラウンド毎のラウンド鍵を算出する処理と、
   ラウンドに対応する前記ラウンド鍵と、前記メッセージブロックから前回のラウンドで算出された第一平文と、を予め定められた平文変換関数に入力することによりラウンド毎の第一平文を算出する処理と、
   を行うものであること、
   を特徴とするハッシュ値生成装置。
5. 請求項４に記載のハッシュ値生成装置であって、
   前記鍵変換関数と、前記平文変換関数と、は同じ関数が用いられること、
   を特徴とするハッシュ値生成装置。
6. 請求項５に記載のハッシュ値生成装置であって、
   前記鍵変換関数と、前記平文変換関数と、は、
   入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）、Ｙ６（ｒ）、Ｙ７（ｒ）に分割し、
   Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）の値を、それぞれ、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）に変換し、
   Ｙ４（ｒ）と、ラウンドごとに定められる定数と、の排他的論理和を算出したものと、Ｙ５（ｒ）と、を予め定められた非線形関数に入力して算出された算出値の上位ビットと、Ｙ６（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
   前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
   変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）の値を連結したデータを出力データとするものであること、
   を特徴とするハッシュ値生成装置。
7. 請求項５に記載のハッシュ値生成装置であって、
   前記鍵変換関数と、前記平文変換関数と、は、
   入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）に分割し、
   Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）の値を、それぞれ、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）に変換し、
   Ｙ３（ｒ）と、ラウンドごとに定められる定数と、の排他的論理和を算出したものを予め定められた非線形関数に入力して算出された算出値と、Ｙ４（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
   前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
   変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）の値を連結したデータを出力データとするものであること、
   を特徴とするハッシュ値生成装置。
8. コンピュータを、ハッシュ値生成手段として機能させるプログラムであって、
   前記コンピュータが備える制御手段に対して、
   入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成させ、
   前記制御手段が行う前記変換処理においては、二つのデータを入力とし、前記二つのデータを非線形変換し、二つのデータを出力する非線形変換を行わせ、
   前記非線形変換においては、二つのデータを入力とし、前記二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を６回行う線型変換を行わせ、
   前記６回の巡回シフトでシフトするビット数は、順番にｑ_１、ｑ_２、ｑ_３、ｑ_４、ｑ_５、ｑ_６であり、
   ｑ_１＋ｑ_２、ｑ_１＋ｑ_４、ｑ_３＋ｑ_４、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４、ｑ_１＋ｑ_６、ｑ_３＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_６、ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、ｑ_１＋ｑ_２＋ｑ_３＋ｑ_４＋ｑ_５＋ｑ_６、の１３個の値の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにした、
   ことを特徴とするプログラム。
9. 請求項８に記載のプログラムであって、
   前記制御手段が行う前記変換処理では、合成変換が行われており、
   前記合成変換は、排他的論理和を算出するものであること、
   を特徴とするプログラム。
10. 請求項９に記載のプログラムであって、
    前記合成変換には、算術加算は含まれていないこと、
    を特徴とするプログラム。
11. 請求項８に記載のプログラムであって、
    前記コンピュータをラウンド定数の初期値及びラウンド鍵の初期値を記憶する記憶手段としても機能させ、
    前記制御手段は、前記変換処理として、
    前記記憶手段に記憶されている前記ラウンド定数の初期値からラウンド毎のラウンド定数を予め定められた関数で算出する処理と、
    ラウンドに対応する前記ラウンド定数と、前記記憶手段に記憶されている前記ラウンド鍵の初期値から前回のラウンドで算出されたラウンド鍵と、予め定められた鍵変換関数に入力することによりラウンド毎のラウンド鍵を算出する処理と、
    ラウンドに対応する前記ラウンド鍵と、前記メッセージブロックから前回のラウンドで算出された第一平文と、を予め定められた平文変換関数に入力することによりラウンド毎の第一平文を算出する処理と、
    を行うものであること、
    を特徴とするプログラム。
12. 請求項１１に記載のプログラムであって、
    前記鍵変換関数と、前記平文変換関数と、は同じ関数が用いられること、
    を特徴とするプログラム。
13. 請求項１２に記載のプログラムであって、
    前記鍵変換関数と、前記平文変換関数と、は、
    入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）、Ｙ６（ｒ）、Ｙ７（ｒ）に分割し、
    Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）、Ｙ５（ｒ）の値を、それぞれ、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）に変換し、
    Ｙ４（ｒ）と、ラウンドごとに定められる定数と、の排他的論理和を算出したものと、Ｙ５（ｒ）と、を予め定められた非線形関数に入力して算出された算出値の上位ビットと、Ｙ６（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
    前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
    変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）、Ｙ５（ｒ＋１）、Ｙ６（ｒ＋１）、Ｙ７（ｒ＋１）の値を連結したデータを出力データとするものであること、
    を特徴とするプログラム。
14. 請求項１２に記載のプログラムであって、
    前記鍵変換関数と、前記平文変換関数と、は、
    入力されたデータをＹ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）、Ｙ４（ｒ）に分割し、
    Ｙ０（ｒ）、Ｙ１（ｒ）、Ｙ２（ｒ）、Ｙ３（ｒ）の値を、それぞれ、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）に変換し、
    Ｙ３（ｒ）と、ラウンドごとに定められる定数と、の排他的論理和を算出したものを予め定められた非線形関数に入力して算出された算出値と、Ｙ４（ｒ）と、の排他的論理和を算出したものをＹ０（ｒ＋１）に変換し、
    前記算出値の下位ビットと、Ｙ７（ｒ）と、の排他的論理和を算出したものをＹ１（ｒ＋１）に変換し、
    変換したＹ０（ｒ＋１）、Ｙ１（ｒ＋１）、Ｙ２（ｒ＋１）、Ｙ３（ｒ＋１）、Ｙ４（ｒ＋１）の値を連結したデータを出力データとするものであること、
    を特徴とするプログラム。
15. ハッシュ値生成装置が行うハッシュ値生成方法であって、前記ハッシュ値生成装置は、
    入力されたメッセージを予め定められたデータ長のＮ（Ｎは自然数）個のメッセージブロックに分割し、該メッセージブロックに対して予め定められたＲ（Ｒは２以上の自然数）ラウンドの変換処理を繰り返し行い、第ｎ（ｎは自然数）メッセージブロックでのＲラウンドの変換処理で算出された値を、第ｎ＋１メッセージブロックでの鍵情報として用いるブロック暗号化をＮ回繰り返すことで、前記メッセージのハッシュ値を生成する制御部を備え、
    前記制御部が行う前記変換処理においては、二つのデータを入力とし、前記二つのデータを非線形変換し、二つのデータを出力する非線形変換の過程が行われ、
    前記非線形変換の過程においては、二つのデータを入力とし、前記二つのデータの内、一方のデータに予め定めたビットの巡回シフトを行い、他方のデータに合成する処理、を６回行う線型変換が行われ、
    前記６回の巡回シフトでシフトするビット数は、順番にｑ _１ 、ｑ _２ 、ｑ _３ 、ｑ _４ 、ｑ _５ 、ｑ _６ であり、
    ｑ _１ ＋ｑ _２ 、ｑ _１ ＋ｑ _４ 、ｑ _３ ＋ｑ _４ 、ｑ _１ ＋ｑ _２ ＋ｑ _３ ＋ｑ _４ 、ｑ _１ ＋ｑ _６ 、ｑ _３ ＋ｑ _６ 、ｑ _１ ＋ｑ _２ ＋ｑ _３ ＋ｑ _６ 、ｑ _５ ＋ｑ _６ 、ｑ _１ ＋ｑ _２ ＋ｑ _５ ＋ｑ _６ 、ｑ _１ ＋ｑ _４ ＋ｑ _５ ＋ｑ _６ 、ｑ _１ ＋ｑ _３ ＋ｑ _４ ＋ｑ _５ ＋ｑ _６ 、ｑ _２ ＋ｑ _３ ＋ｑ _４ ＋ｑ _５ ＋ｑ _６ 、ｑ _１ ＋ｑ _２ ＋ｑ _３ ＋ｑ _４ ＋ｑ _５ ＋ｑ _６ 、の１３個の値の内の任意の二つの値の差が３２の倍数になるような組の個数が３より小さくなるようにしたこと
    を特徴とするハッシュ値生成方法。

Images