(57)【要約】  メッセージレジスタ８１は、ビット数が素数であり、そのビット数が法とされた場合における最小の原始根が２である長さのメッセージを１ビットずつ逐次出力する。巡回鍵レジスタ８２は、メッセージのビット数と同じビット数の鍵を巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する。論理積演算手段８３は、逐次出力される巡回鍵ベクトルと、１ビットずつ逐次出力されるメッセージビットとに基づいて、メッセージビットが１のときに巡回鍵ベクトルを出力し、メッセージビットが０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する。累積和演算手段８４は、出力されたビット数と同数の演算結果を累積して排他的論理和を算出する。
2014013680.tif 000002
【特許請求の範囲】
【請求項１】
ビット数が素数であり、当該ビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶し、前記メッセージを１ビットずつ逐次出力するメッセージレジスタと、
前記メッセージのビット数と同じビット数の鍵を記憶し、左または右のいずれか固定された一方向へ前記鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する巡回鍵レジスタと、
前記巡回鍵レジスタから逐次出力される前記巡回鍵ベクトルと、前記メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、当該メッセージビットが１のときに巡回鍵ベクトルを出力し、当該メッセージビットが０のときに前記巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する論理積演算手段と、
前記論理積演算手段によって出力された前記ビット数と同数の演算結果を累積して排他的論理和を算出し、前記ビット数と同数の演算結果が累積されたときに、前記排他的論理和の算出結果を出力する累積和演算手段とを備えた
ことを特徴とするユニバーサルハッシュ関数演算装置。
【請求項２】
メッセージレジスタは、メッセージを１ビットずつクロックに応じて逐次出力し、
巡回鍵レジスタは、鍵を１ビットずつクロックに応じて逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルをクロックに応じて逐次出力し、
論理積演算手段は、クロックに応じて逐次出力される巡回鍵ベクトルとメッセージビットとに基づいて、巡回鍵ベクトルまたはオールゼロベクトルを出力し、
累積和演算手段は、メッセージのビット数と同じクロック数までの演算結果を累積して排他的論理和を算出し、クロック数がメッセージのビット数と同じときに、前記排他的論理和の算出結果を出力する
請求項１記載のユニバーサルハッシュ関数演算装置。
【請求項３】
ビット数が素数であり、当該ビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶するメッセージレジスタから、前記メッセージを１ビットずつ逐次出力し、
前記メッセージのビット数と同じビット数の鍵を記憶する巡回鍵レジスタから、左または右のいずれか固定された一方向へ前記鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力し、
前記巡回鍵レジスタから逐次出力される前記巡回鍵ベクトルと、前記メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、当該メッセージビットが１のときに巡回鍵ベクトルを出力し、当該メッセージビットが０のときに前記巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力し、
出力された前記ビット数と同数の演算結果を累積して排他的論理和を算出し、前記ビット数と同数の演算結果が累積されたときに、前記排他的論理和の算出結果を出力する
ことを特徴とするユニバーサルハッシュ関数演算方法。
【請求項４】
メッセージレジスタからメッセージを１ビットずつクロックに応じて逐次出力し、
巡回鍵レジスタから鍵を１ビットずつクロックに応じて逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルをクロックに応じて逐次出力し、
クロックに応じて逐次出力される巡回鍵ベクトルとメッセージビットとに基づいて、巡回鍵ベクトルまたはオールゼロベクトルを出力し、
メッセージのビット数と同じクロック数までの演算結果を累積して排他的論理和を算出し、クロック数がメッセージのビット数と同じときに、前記排他的論理和の算出結果を出力する
請求項３記載のユニバーサルハッシュ関数演算方法。
【請求項５】
コンピュータに、
ビット数が素数であり、当該ビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶するメッセージレジスタから、前記メッセージを１ビットずつ逐次出力するメッセージ出力処理、
前記メッセージのビット数と同じビット数の鍵を記憶する巡回鍵レジスタから、左または右のいずれか固定された一方向へ前記鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する巡回鍵ベクトル出力処理、
前記巡回鍵レジスタから逐次出力される前記巡回鍵ベクトルと、前記メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、当該メッセージビットが１のときに巡回鍵ベクトルを出力し、当該メッセージビットが０のときに前記巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する論理積演算処理、および、
出力された前記ビット数と同数の演算結果を累積して排他的論理和を算出し、前記ビット数と同数の演算結果が累積されたときに、前記排他的論理和の算出結果を出力する累積和演算処理
を実行させるためのユニバーサルハッシュ関数演算プログラム。
【請求項６】
コンピュータに、
メッセージ出力処理で、メッセージレジスタからメッセージを１ビットずつクロックに応じて逐次出力させ、
巡回鍵ベクトル出力処理で、巡回鍵レジスタから鍵を１ビットずつクロックに応じて逐次的に巡回置換させ、巡回置換した結果得られる巡回鍵ベクトルをクロックに応じて逐次出力させ、
論理積演算処理で、クロックに応じて逐次出力される巡回鍵ベクトルとメッセージビットとに基づいて、巡回鍵ベクトルまたはオールゼロベクトルを出力させ、
累積和演算処理で、メッセージのビット数と同じクロック数までの演算結果を累積して排他的論理和を算出させ、クロック数がメッセージのビット数と同じときに、前記排他的論理和の算出結果を出力させる
請求項５記載のユニバーサルハッシュ関数演算プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明は、鍵付きのユニバーサルハッシュ関数の演算を行うユニバーサルハッシュ関数演算装置、ユニバーサルハッシュ関数演算およびユニバーサルハッシュ関数演算プログラムに関する。
【背景技術】
【０００２】
ユニバーサルハッシュ関数とは、所定の入力空間の入力を固定長の出力へ変換する関数である。SHA-1 （Secure Hash Algorithm 1 ）やMD5 （Message Digest 5）などの暗号学的ハッシュ関数と異なり、ランダムな鍵も入力として用いられる。入力x 、鍵k を用いたユニバーサルハッシュ関数H は、形式的に、以下に示す式１で表わされる。【０００３】
y = H(k,x)   （式１）【０００４】
また、鍵の空間がD_key であるとき、関数の集合{H(k,*): k in D_key}は、ユニバーサルハッシュ関数の族（family）と呼ばれることもある。【０００５】
ユニバーサルハッシュ関数は、CarterとWegmanによりその概念が最初に提案され、以後、暗号技術の様々な分野で要素技術として利用されている。その典型的な例として、メッセージ認証（Message Authentication Code, MAC）の分野においては、暗号学的ハッシュ関数を用いたHMAC（Keyed-Hashing for Message Authentication Code ）などの方式以外に、ユニバーサルハッシュ関数とブロック暗号またはストリーム暗号を組み合わせた方法が存在する。この方法は、Carter-Wegman MAC（CW-MAC）と呼ばれている。ユニバーサルハッシュ関数の構成によっては、Carter-Wegman MACは非常に高速で演算できることが知られている。【０００６】
ユニバーサルハッシュ関数に求められる性質にはいくつかのバリエーションがある。代表的な性質は、e-almost universalという性質である。入力空間D_in、出力空間D_out 、鍵空間D_key について、以下に示す式２の関係を満たす場合、関数H:D_key x D_in -> D_out がe-almost universalの性質を満たす（e-AU）ハッシュ関数であると言われる。【０００７】
Pr_K[H(K,x) = H(K,x')] ≦ e , for all x ≠ x' , x,x' in D_in   （式２）【０００８】
すなわち、上記に示す式２は、鍵をD_key 上の一様な乱数としたとき、異なる２つの入力があった場合におけるH の出力が一致する確率が、たかだかe になることを示す。鍵付きの関数H が上記に示す式２を満たすときに、H はe-AUハッシュ関数であると言われる。【０００９】
また、D_out がn-bit 空間であり、以下に示す式３の関係を満たす場合、H はe-almost XOR universalという性質を満たす（e-AXU ）ハッシュ関数であると言われる。【００１０】
Pr_K[H(K,x) xor H(K,x') = d ] ≦ e ,
for all x ≠ x' , x,x' in D_in, for all d in D_out    （式３）【００１１】
上記に示す式３において、x xor y は、x とy のビットごとの排他的論理和（XOR ）を表す。入出力空間が同じであれば、e-AUよりe-AXU がより強い条件になる。e-AUハッシュ関数同様に、鍵付きの関数H が上記に示す式３を満たすときに、H はe-AXU ハッシュ関数であると言われる。【００１２】
なお、ここでは、ユニバーサルハッシュ関数の最も基本的な形式として、２ブロック入力１ブロック出力のe-AUハッシュ関数、または、１ブロック入出力のe-AXU 関数を中心に説明する。ブロック長は、断りのない限りn bitsとする。H(k,x)が１ブロック入出力のe-AXU ハッシュ関数であれば、以下の式４で示される２ブロック入力１ブロック出力の関数G は、必ずe-AUハッシュ関数になる。【００１３】
G(k,(x[1],x[2])) = H(k,x[1]) xor x[2]   （式４）【００１４】
さらに、２ブロック入力１ブロック出力のe-AUハッシュ関数を用いてデータを２分木状に処理することで、任意の長さのデータを処理できることが知られている（例えば、非特許文献１参照）。したがって、１ブロック入出力のe-AXU ハッシュ関数を考えれば、原則的にはあらゆる長さのユニバーサルハッシュ関数を生成することが可能になる。【００１５】
e-AUまたはe-AXUであるユニバーサルハッシュ関数の具体的な作成方法について、数多くの研究がある。最も一般的な方法の一つとして、有限体GF(2n)を用いた方法がある。これは、例えば、入力空間がGF(2n)、出力空間がGF(2n)の場合、関数H を、以下に示す式５で定義する方法である。【００１６】
H(K,x[1]) = x[1] mult K  （式５）【００１７】
式５において、K はGF(2n)上の一様な乱数を表わし、multは、GF(2n)上の乗算を表す。GF(2n)の要素は、2n個存在するため、n-bit 系列で一意に表現できる。よって、上記に示す式５のH は、n-bit 入出力の鍵付き関数であり、さらに、(1/2n)-AXUであることが知られている。この値は、n-bit 出力の場合、理論最小値である。また、式４について示した理由と同様の理由により、以下に示す式６のH が、2n-bit入力、および、n-bit 出力の鍵付き関数であり、かつ、(1/2n)-AU であることも分かる。【００１８】
H(K,(x[1],x[2])) = x[1] mult K + x[2]    （式６）【００１９】
上記に示す式６において、+ は、GF(2n)上の加算（すなわち xor ）を表す。それ以外については、式５に示す内容と同様である。【００２０】
一方、非特許文献２には、Krawczykにより提案された、Toeplitz行列を用いる方法が記載されている。n 行m 列のバイナリToeplitz行列におけるi 行j 列成分をc(i,j) in {0,1} と表したとき、c(i,j)は、以下に示す式７の関係を満たす。【００２１】
c(i,j) = c(i+1,j+1) for any 1≦i≦n-1, any 1≦j≦m-1   （式７）【００２２】
すなわち、対角線上の成分は、全て同じであり、行列は、第一列と第一行に含まれるn+m-1 個の成分を指定することで、一意に決定される。また、非特許文献２には、n 行m 列のバイナリToeplitz行列M において、上記のn+m-1 個の独立な成分がそれぞれ{0,1} の範囲からランダムに与えられたとき、行列積により、m-bit 入力およびn-bit 出力を利用して、(1/2n)-AXUハッシュ関数が構成できることが記載されている。すなわち、この関数は、以下に示す式８で定義される。【００２３】
ToplitzHash(K,x) = M・x  （式８）【００２４】
式８において、x は、m-bitを表わし、K は、(n+m-1)-bit の鍵を表わし、M は、第一列と第一行をK を用いて定められたランダムなn 行m 列のバイナリToeplitz行列を表す。また、M・xは、行列−ベクトル積を表し、その結果は、n-bit である。ビットごとの演算は、ブール変数として行われる。 具体的には、n 行n 列のバイナリ正方Toeplitz行列を用いる場合、鍵は、2n-1ビットになる。 【００２５】
さらに、非特許文献２には、m がn よりはるかに大きくなる場合を考え、第一列と第一行を、レジスタの初期値をランダムに設定した線形フィードバックレジスタ（Linear Feedback Shift Register, LFSR）の出力系列とする方法が記載されている。この方法を用いることで、鍵の長さを行列の大きさとは直接関係のない定数にすることができる。【００２６】
なお、上述のn-bit 入出力のe-AXU ハッシュ関数を応用した方法も、いくつか存在する。このハッシュ関数は、ブロック暗号との組み合わせによる暗号化や認証に応用もされている。例えば、Liskovらにより提案された、Tweakable ブロック暗号と呼ばれる拡張されたブロック暗号が知られている。【００２７】
Tweakable ブロック暗号は、鍵とメッセージ（すなわち、平文および暗号文）以外に、Tweak と呼ばれる外部パラメータをもつ。メッセージとTweak が共にn-bit であるようなTweakable ブロック暗号は、AES （Advanced Encryption Standard）など、通常のn-bit ブロック暗号E と、n-bit 入出力のe-AXU ハッシュ関数H があれば、作成可能であることが知られている（例えば、非特許文献３、非特許文献４、非特許文献５参照）。
図６は、n-bit ブロック暗号E とn-bit 入出力e-AXU ハッシュ関数H から、n-bit ブロックおよびn-bit Tweak のTweakable ブロック暗号を構成する方法の例を示す説明図である。上述するTweakable ブロック暗号は、具体的には、図６に示されるように、Tweak をH に与えた結果をE の上下でマスクとして用いることで一般的に構成可能である。【００２８】
なお、メッセージとTweak が共にn-bit であるようなTweakable ブロック暗号は、例えば、認証暗号化方式（特許文献１、非特許文献６参照。）や、ストレージ向けの暗号化方式（非特許文献７参照。）、オンライン型の暗号化（非特許文献８参照。）などに用いられる。【００２９】
他にも、n-bit 入出力のe-AXU ハッシュ関数を、ハードウェアの物理特性の個体差を利用した個別IDの生成などにも利用可能である。例えば、非特許文献９には、128-bit入出力のe-AXU ハッシュ関数が、Toeplitz行列で構成されることが記載されている。なお、非特許文献９には、e-AXU ハッシュ関数が64-bit入力128-bit 出力で、行列が128次のToeplitz 行列であることも記載されている。【００３０】
なお、非特許文献１０には、有限体の要素からなる行列のランクに関する補題が記載されている。また、非特許文献１１には、All-one-polynomialの既約性の条件について記載されている。
【先行技術文献】
【特許文献】
【００３１】
【特許文献１】米国特許第７０４６８０２号明細書
【非特許文献】
【００３２】
【非特許文献１】K. Minematsu, Y. Tsunoo Provably Secure MACs from Differentially-Uniform Permutations and AES-Based Implementations. FSE 2006, LNCS 4047, pp. 226-241.
【非特許文献２】H. Krawczyk. LFSR-based Hashing and Authentication. CRYPTO 1994, LNCS 839, Springer 1994, pp. 129-139
【非特許文献３】M. Liskov, R. L. Rivest, D. Wagner: Tweakable Block Ciphers. Advances in Cryptology - CRYPTO 2002, 22nd Annual International Cryptology Conference, Santa Barbara, California, USA, August 18-22, 2002, Proceedings. Lecture Notes in Computer Science 2442 Springer 2002, pp. 31-46.
【非特許文献４】K. Minematsu, Improved Security Analysis of XEX and LRW Modes, Selected Areas in Cryptography- SAC'06, LNCS 4356, pp.96-113, Springer, 2007.
【非特許文献５】K. Minematsu, T. Matsushima, Generalization and Extension of XEX* Mode, IEICE Transactions 92-A(2): 517-524 (2009).
【非特許文献６】Phillip Rogaway: Efficient Instantiations of Tweakable Blockciphers and Refinements to Modes OCB and PMAC. Advances in Cryptology - ASIACRYPT 2004, 10th International Conference on the Theory and Application of Cryptology and Information Security, Jeju Island, Korea, December 5-9, 2004, Proceedings. Lecture Notes in Computer Science 3329 Springer 2004, pp. 16-31
【非特許文献７】NIST Special Publication 800-38E, Recommendation for Block Cipher Modes of Operation: The XTS-AES Mode for Confidentiality on Storage Devices, Jan. 2010.
【非特許文献８】P. Rogaway, H. Zhang, Online Ciphers from Tweakable Blockciphers, Topics in Cryptology - CT-RSA 2011 - The Cryptographers' Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings. Lecture Notes in Computer Science 6558 Springer 2011, pp. 237-249.
【非特許文献９】R. Maes, P. Tuyls, I. Verbauwhede, Low-Overhead Implementation of a Soft Decision Helper Data Algorithm for SRAM PUFs, Cryptographic Hardware and Embedded Systems - CHES 2009, 11th International Workshop, Lausanne, Switzerland, September 6-9, 2009, Proceedings. Lecture Notes in Computer Science 5747 Springer 2009, pp. 332-347
【非特許文献１０】D. E. Daykin. "On the Rank of the Matrix f(A) and the Enumeration of Certain Matrices over a Finite Field." Journal London Math. Society, Vol. 35, pp. 36-42, 1960.
【非特許文献１１】P.K.S. Wah, and M. Z. Wang. "Realization and application of the Massey-Omura lock." Digital Comm., Int. Zurich Seminar, IEEE Press, 1984, pp. 175 - 182.
【発明の概要】
【発明が解決しようとする課題】
【００３３】
上記の式５および式６に示すユニバーサルハッシュ関数の演算には、GF(2n)上の乗算が必要である。例えば、ユニバーサルハッシュ関数を暗号に関係する用途に用いる場合、e が十分小さいe-AXU またはe-AUハッシュ関数を作成しようとすると、n の値は、例えば、64、128 、256 、または512 などの大きい数字になる。その場合の計算コストは、一般にかなり大きいものになってしまうという問題がある。【００３４】
また、Toeplitz行列とLFSRとを組み合わせた方式を用いる場合、AXU としてのバイアスe は低下する。例えば、LFSRの長さがn-bit のとき、上記のToeplitz行列とLFSRとを組み合わせた方式は、(n/2n)-AXUになる。さらに、上記のバイアスを達成するためには、LFSRのn-bit レジスタの初期値をランダムに与えるだけでなく、LFSRの既約なフィードバック多項式もランダムに決められている必要がある。よって、LFSRのn-bit レジスタの初期値をランダムに与える際に、n-bit の鍵が必要になる。また、LFSRの既約なフィードバック多項式をランダムに決める際、2n-bit の鍵が必要になる。【００３５】
すなわち、Toeplitz行列を用いる方式では、e-AXU におけるバイアスe を1/2nに近づけようとすると、LFSRを使う場合でも使わない場合でも、鍵長がほぼ2n-bitになってしまう。鍵長が2n-bitになるということは、鍵長がn-bit である場合に比べて、鍵を生成するコストが増大することを意味する。【００３６】
図７は、非特許文献２に記載されたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いずにハードウェア実装した例を示す説明図である。また、図８は、非特許文献２に記載されたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いてハードウェア実装した例を示す説明図である。図８に例示する実装は、LFSR（図８におけるn-bit LSFR）を用いて実装されている点において、図７に例示する実装と異なる。【００３７】
Toeplitz行列を用いる方式をハードウェアで実装する場合、レジスタを増やす必要があるため、回路が複雑になり、回路の規模が増大してしまうという問題がある。【００３８】
なお、上記の点を考慮しても、Toeplitz行列を用いたユニバーサルハッシュ関数は、一般的に、ハードウェアの実装に適した方式である。特に、Toeplitz行列とLFSRとを組み合わせた方式では、鍵が固定されている場合、非常に容易にハードウェアの実装が可能である。しかし、Toeplitz行列とLFSRとを組み合わせた方式では、鍵が固定できない場合、鍵に依存してフィードバック多項式が変わることに対応する実装を必要とするため、ハードウェアによる実装がより複雑になってしまうという問題がある。【００３９】
そこで、本発明は、n-bit 入出力のe-AXU ハッシュ関数方式を用いる場合に、鍵長がn-bit であっても、バイアスを理論最小値(1/2n)に近づけることができるユニバーサルハッシュ関数演算装置を提供することを目的とする。
【課題を解決するための手段】
【００４０】
本発明によるユニバーサルハッシュ関数演算装置は、ビット数が素数であり、そのビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶し、メッセージを１ビットずつ逐次出力するメッセージレジスタと、メッセージのビット数と同じビット数の鍵を記憶し、左または右のいずれか固定された一方向へ鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する巡回鍵レジスタと、巡回鍵レジスタから逐次出力される巡回鍵ベクトルと、メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、そのメッセージビットが１のときに巡回鍵ベクトルを出力し、そのメッセージビットが０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する論理積演算手段と、論理積演算手段によって出力されたビット数と同数の演算結果を累積して排他的論理和を算出し、ビット数と同数の演算結果が累積されたときに、排他的論理和の算出結果を出力する累積和演算手段とを備えたことを特徴とする。【００４１】
本発明によるユニバーサルハッシュ関数演算方法は、ビット数が素数であり、そのビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶するメッセージレジスタから、メッセージを１ビットずつ逐次出力し、メッセージのビット数と同じビット数の鍵を記憶する巡回鍵レジスタから、左または右のいずれか固定された一方向へ鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力し、巡回鍵レジスタから逐次出力される巡回鍵ベクトルと、メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、そのメッセージビットが１のときに巡回鍵ベクトルを出力し、そのメッセージビットが０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力し、出力されたビット数と同数の演算結果を累積して排他的論理和を算出し、ビット数と同数の演算結果が累積されたときに、排他的論理和の算出結果を出力することを特徴とする。【００４２】
本発明によるユニバーサルハッシュ関数演算プログラムは、コンピュータに、ビット数が素数であり、そのビット数が法とされた場合における最小の原始根が２である長さのメッセージを記憶するメッセージレジスタから、メッセージを１ビットずつ逐次出力するメッセージ出力処理、メッセージのビット数と同じビット数の鍵を記憶する巡回鍵レジスタから、左または右のいずれか固定された一方向へ鍵を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する巡回鍵ベクトル出力処理、巡回鍵レジスタから逐次出力される巡回鍵ベクトルと、メッセージレジスタから１ビットずつ逐次出力されるメッセージビットとに基づいて、そのメッセージビットが１のときに巡回鍵ベクトルを出力し、そのメッセージビットが０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する論理積演算処理、および、出力されたビット数と同数の演算結果を累積して排他的論理和を算出し、ビット数と同数の演算結果が累積されたときに、排他的論理和の算出結果を出力する累積和演算処理を実行させることを特徴とする。
【発明の効果】
【００４３】
本発明によれば、n-bit 入出力のe-AXU ハッシュ関数方式を用いる場合に、鍵長がn-bit であっても、バイアスを理論最小値(1/2n)に近づけることができる。
【図面の簡単な説明】
【００４４】
【図１】本発明によるユニバーサルハッシュ関数演算装置の一実施形態を示すブロック図である。
【図２】本実施形態のユニバーサルハッシュ関数演算装置の動作例を示す説明図である。
【図３】本実施形態のユニバーサルハッシュ関数演算装置の動作例を示すフローチャートである。
【図４】ユニバーサルハッシュ関数をハードウェアで実装する方法の例を示す説明図である。
【図５】本発明によるユニバーサルハッシュ関数演算装置の概要を示すブロック図である。
【図６】n-bit ブロックおよびn-bit Tweak のTweakable ブロック暗号を構成する方法の例を示す説明図である。
【図７】非特許文献２に記載されたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いずにハードウェア実装した例を示す説明図である。
【図８】非特許文献２に記載されたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いてハードウェア実装した例を示す説明図である。
【発明を実施するための形態】
【００４５】
以下、本発明の実施形態を図面を参照して説明する。以下、特に断りのない限り、+ をビットごとの排他的論理和を表すものとする。また、１ブロックの長さをn ビットとする。また、ベクトルx のi-bit 左巡回シフトをrot(i,x)と記す。
【００４６】
図１は、本発明によるユニバーサルハッシュ関数演算装置の一実施形態を示すブロック図である。本実施形態のユニバーサルハッシュ関数演算装置１０は、入力手段１００と、メッセージレジスタ手段１０１と、巡回鍵レジスタ手段１０２と、論理積演算手段１０３と、累積和演算手段１０４と、出力手段１０５とを備えている。
【００４７】
ユニバーサルハッシュ関数演算装置１０は、例えば、ＣＰＵ、メモリ、磁気ディスク等により実現される。また、ユニバーサルハッシュ関数演算装置の各手段は、例えば、磁気ディスクに格納されたプログラムをＣＰＵ上で動作させることにより実現される。
【００４８】
具体的には、メッセージレジスタ手段１０１と、巡回鍵レジスタ手段１０２と、論理積演算手段１０３と、累積和演算手段１０４は、プログラム（ユニバーサルハッシュ関数演算プログラム）に従って動作するコンピュータのＣＰＵによって実現される。
【００４９】
入力手段１００は、対象のn-bit メッセージM=(M[1],...,M[n]) およびn-bit 鍵K=(K[1],...,K[n]) を入力する。入力手段１００は、例えば、キーボードなどの文字入力装置により実現される。また、入力手段１００は、他の装置より入力されたメッセージを受信するインタフェースなどにより実現されていてもよい。なお、以下の説明では、メッセージM に含まれるビット単位の情報M[i]をメッセージビットと記すこともある。
【００５０】
また、ここで、n （すなわち、ビット数）は、素数であり、n を法とする原始根（primitive root of modulo n）は２を満たす。したがって、メッセージM は、ビット数が素数であって、そのビット数が法とされた場合における最小の原始根が２である。また、鍵K のビット数は、メッセージM のビット数と同じビット数（具体的には、n ）である。
【００５１】
入力手段１００は、入力されたメッセージM をメッセージレジスタ手段１０１に記憶させる。また、入力手段１００は、入力された鍵K を巡回鍵レジスタ手段１０２に記憶させる。
【００５２】
メッセージレジスタ手段１０１は、入力されたメッセージを記憶し、記憶されたメッセージを外部クロックに応じて1-bit ずつ逐次出力する。具体的には、クロックは、1 からn まで動くものとし、メッセージレジスタ手段１０１は、クロックがi のときM[i]を出力する。 
【００５３】
巡回鍵レジスタ手段１０２は、入力された鍵K を記録し、これを外部クロックに応じて巡回シフトさせた値を出力する。具体的には、クロックは1 からn まで動くものとし、巡回鍵レジスタ手段１０２は、クロックがi のときrot(i-1,K)を出力する。
【００５４】
なお、本実施形態では、鍵を左方向へ１ビットずつ逐次的に巡回置換する場合を例示しているが、巡回置換する方向は左方向に限定されず、右方向であってもよい。すなわち、巡回鍵レジスタ手段１０２は、左または右のいずれか固定された一方向へ１ビットずつ、クロックに応じて逐次的に巡回置換し、巡回置換した結果得られるn ビットの巡回鍵ベクトルをクロックに応じて逐次出力する。
【００５５】
論理積演算手段１０３は、メッセージレジスタ手段１０１が出力するM[i]と、巡回鍵レジスタ手段１０２が出力するrot(i-1,K)から、ベクトルとビットの論理積を算出し、算出結果を出力する。すなわち、クロックがi のときに論理積演算手段１０３が出力する結果をS(i)とすると、M[i]が1 のとき、S(i)はrot(i-1,K)になり、M[i]が0 のとき、S(i)はn-bitの全ゼロ値になる。
【００５６】
言い換えると、論理積演算手段１０３は、メッセージビットM[i]が1 のときに巡回鍵ベクトルrot(i-1,K)を出力し、メッセージビットM[i]が0 のときに巡回鍵ベクトルと同じビット数（n ビット）のオールゼロベクトルを出力する。
【００５７】
累積和演算手段１０４は、クロックが1 からn に動く間の全ての論理積演算手段１０３の出力の排他的論理和を出力する。具体的には、累積和演算手段１０４は、S(1) + S(2) + ... + S(n)を出力する。
【００５８】
すなわち、累積和演算手段１０４は、論理積演算手段１０３によって出力されたビット数と同数の演算結果（例えば、１番目のクロックに応じた演算結果からｎ番目のクロックに応じた演算結果まで）を累積して、排他的論理和（例えば、XOR ）を算出する。そして、累積和演算手段１０４は、上述するビット数と同数の演算結果が累積されたときに（例えば、ｎ番目のクロックに応じて）、排他的論理和の算出結果を出力する。なお、累積和演算手段１０４は、全てのS(i)を記録して排他的論理和を算出してもよく、全てのS(i)を記録せず、逐次的に排他的論理和を算出してもよい。
【００５９】
出力手段１０５は、累積和演算手段１０４の出力結果（すなわち、S(1) + S(2) + ... + S(n)）を、例えば、コンピュータのディスプレイ装置や、プリンタなどへ出力する。
【００６０】
次に、本実施形態のユニバーサルハッシュ関数演算装置の動作を図２および図３を用いて説明する。図２は、本実施形態のユニバーサルハッシュ関数演算装置の動作例を示す説明図である。また、図３は、本実施形態のユニバーサルハッシュ関数演算装置の動作例を示すフローチャートである。
【００６１】
まず、入力手段１００は、対象のn-bit メッセージM = (M[1], M[2], ..., M[n]) とn-bit 鍵K を入力する（図３におけるステップＧ１）。図２に示すように、入力されたメッセージM は、メッセージレジスタ手段１０１に入力され、鍵K は、巡回鍵レジスタ手段１０２に入力される。
【００６２】
次に、メッセージレジスタ手段１０１は、1 からn まで動くクロックに従って、メッセージビットM[i]（i はクロック）を出力する（ステップＧ２）。具体的には、図２に示すように、メッセージレジスタ手段１０１は、n-bit メッセージ(M[1], M[2], ..., M[n]) の各ビットM[i]をi=1 からn について、逐次出力する。以下の説明では、この出力をB と記す。
【００６３】
次に、巡回鍵レジスタ手段１０２は、1 からn まで動くクロックに従って、鍵K の(i-1)-bit 巡回シフト（i はクロック）であるrot(i-1,K)を出力する（ステップＧ３）。具体的には、巡回鍵レジスタ手段１０２は、図２に示すように、n-bit 鍵K をi=1 からn についてi-bit 巡回シフトした結果であるrot(1,K)を逐次出力する。以下の説明では、この出力をV と記す。
【００６４】
次に、論理積演算手段１０３は、B が1 か否か判断する（ステップＧ４）。B が1 の場合（ステップＧ４におけるｙ）、論理積演算手段１０３は、V をそのまま出力する。一方、B が1 ではない場合、すなわち、B が0 の場合（ステップＧ４におけるｎ）、論理積演算手段１０３は、V を全ゼロ値にして出力する（ステップＧ５）。
【００６５】
具体的には、図２に示すように、論理積演算手段１０３は、i=1 からn について、M[i]=1 の場合、rot(i,K)を出力し、M[i]=0 の場合、全ゼロベクトルを出力する。
【００６６】
累積和演算手段１０４は、直前の累積和S とV との和を算出し、S を更新する（ステップＧ６）。なおS の初期値は、ステップＧ１において、予め全てのビットがゼロに設定される。具体的には、累積和演算手段１０４は、図２に示すように、i=1 からn について、論理積演算手段１０３から入力されたベクトルを加算（すなわち、論理的排他和を算出）し、その結果を出力する。
【００６７】
その後、累積和演算手段１０４は、クロックi がn に達したか否かを判断する（ステップＧ７）、クロックi がn に達していない場合（ステップＧ７におけるｙ）、i に1 加算され（ステップＧ８）、ステップＧ２以降の処理が再度行われる。一方、クロックi がn に達していない場合、すなわち、i=n の場合（ステップＧ７におけるｎ）、累積和演算手段１０４は、累積和S を出力する（ステップＧ９）。
【００６８】
すなわち、累積和演算手段１０４は、S の更新処理をクロックi がn になるまで継続し、i がn になった場合に累積和S を出力する。
【００６９】
以上のように、本実施形態によれば、メッセージレジスタ手段１０１は、n bitsのメッセージM を１ビットずつ逐次出力する。ただし、ビット数n は、素数であり、最小のprimitive root modulo n が2 となるという条件を満たす。巡回鍵レジスタ手段１０２は、左または右のいずれか固定された一方向へ鍵K を１ビットずつ逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルを逐次出力する。論理積演算手段１０３は、巡回鍵ベクトルとメッセージビットM[i]とに基づいて、M[i]が１のときに巡回鍵ベクトルを出力し、M[i]が０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する。累積和演算手段１０４は、n 個の演算結果を累積して排他的論理和を算出し、n 個の演算結果が累積されたときに、排他的論理和の算出結果を出力する。
【００７０】
よって、n-bit 入出力のe-AXU ハッシュ関数方式を用いる場合に、鍵長がn-bit であっても、バイアスを理論最小値(1/2n)に近づけることができる。
【００７１】
すなわち、本実施形態によれば、入出力長が共にn-bit であって、バイアスe が理論最小値である1/2nに十分近いe-AXUハッシュ関数の演算を行う場合に、Toeplitz行列ベースの方式よりも、シンプルな演算が可能であり、かつ、鍵長を短くできる。以下、この理由を説明する。
【００７２】
まず、ベクトルx のi-bit 巡回シフトをrot(i,x)とする。なお、巡回シフトの方向は、左でも右でも本発明による効果は変わらないが、ここでは、左方向に統一して説明する。x がn-bit 値(x[1],x[2],...,x[n])の場合、rot(i,x) = (x[i],x[i+1],...,x[n],x[1],...,x[i-1]) になる。さらに、rot(0,x) = rot(n,x) = x である。本発明による方法おけるn-bit 入力をx=(x[1],x[2],...,x[n])、n-bit 鍵をK とすると、出力は、以下に示す式９で表わすことができる。
【００７３】
y = XOR_{i:x[i]=1} rot(i-1,K)   （式９）
【００７４】
上記の式９におけるXOR_{i:x[i]=1}は、x[i]=1を満たすi について全てXOR 演算を行うことを意味する。このとき、y は、rot(i-1,K)を第i 列（i=1,...,n）とした行列M と入力の列ベクトルxTとの行列−ベクトル積に等しい。ここで、Mは、rot(0,K)=Kを第一列としたn 次巡回行列になっている。このとき、上記の式９で表される鍵付き関数は、n が素数かつ最小のprimitive root modulo n が2 のとき、n-bit 入出力(2/2n)-AXUハッシュ関数になることがわかる。
【００７５】
このことは、非特許文献１０に記載された有限体の要素からなる行列のランクに関する補題と、非特許文献１１に記載されたAll-one-polynomialの既約性の条件とを組み合わせることにより導かれる。このとき、バイアスe の理論最小値は(1/2n)であるため、この関数は、ほぼ理論最適なバイアスを実現できるといえる。
【００７６】
次に、上述するユニバーサルハッシュ関数をハードウェアで実装する方法を説明する。図４は、ユニバーサルハッシュ関数をハードウェアで実装する場合の例を示す説明図である。
【００７７】
例えば、Toeplitz行列を用いたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いずにハードウェア実装する場合、図７に示すように、(2n-1)-bitのシフトレジスタ２１を用いて、(2n-1)-bitの初期値を鍵とし、クロックごとに、固定された位置のn-bitを取り出す処理が必要になる。このとき、バイアスe は、理論最小値の1/2nになる。
【００７８】
一方、Toeplitz行列を用いたn-bit 入出力e-AXU ハッシュ関数を、LFSRを用いてハードウェア実装する場合、図８に示すように、n-bit のLFSR２２を用いて、n-bit の初期値を鍵とし、クロックごとに、レジスタ全体（n-bit）を取り出す処理を行えばよい。しかし、この場合、LFSRのフィードバック多項式をランダムに決定するために、約n-bit の別の鍵を必要とする。そのため、この鍵の情報を保持するために、約n-bit のレジスタが必要となる。さらに、フィードバック多項式を鍵依存にするため、ハードウェア実装がより複雑になる。なお、この場合、バイアスe は、理論最小値より若干大きいn/2nになることが知られている。
【００７９】
しかし、図４に示すように、n-bit の巡回レジスタ２３を用いて、n-bit の初期値を鍵とし、クロックごとにレジスタ全体（n-bit ）を取り出す処理で本実施形態によるユニバーサルハッシュ関数演算処理を実現できる。したがって、本実施形態の演算方法は、図７および図８に示す実装方法と比較すると、レジスタを短くでき、さらに、実装方法も単純にすることができる。
【００８０】
なお、Toeplitz行列を用いた方式では、n を任意の正整数とすることができるのに対し、本発明によるユニバーサルハッシュ関数演算方法では、n が素数、かつ、最小のprimitive root modulo n が2 となるという条件が必要である。しかし、このような素数は数が多く、かつ、ある程度均一に分布して存在しているため、実用上大きな問題にならない。例えば、e=1/264 程度のバイアスを実現したい場合、条件を満たすn として、n=61やn=67を選択すればよく、また、e=1/2128程度のバイアスを実現したい場合、条件を満たすn とし、n=107 やn=131 を選択すればよい。
【００８１】
さらに、上述するように、n-bit 入出力のe-AXU ハッシュ関数を、n-bit ブロック暗号との組み合わせなどにより、様々なタイプの暗号化および認証へ応用することが可能である。
【００８２】
次に、本発明の概要を説明する。図５は、本発明によるユニバーサルハッシュ関数演算装置の概要を示すブロック図である。本発明によるユニバーサルハッシュ関数演算装置は、ビット数（例えば、n ）が素数であり、そのビット数が法とされた場合における最小の原始根が２（すなわち、最小のprimitive root modulo n が２を満たすn ）である長さのメッセージ（例えば、M = (M[1], M[2], ..., M[n]) ）を記憶し、メッセージを１ビットずつ逐次（例えば、クロックに応じて）出力するメッセージレジスタ８１（例えば、メッセージレジスタ手段１０１）と、メッセージのビット数と同じビット数（例えば、n ）の鍵（例えば、K = (K[1],...,K[n]) ）を記憶し、左または右のいずれか固定された一方向へ鍵を１ビットずつ逐次的に（例えば、クロックに応じて）巡回置換し、巡回置換した結果得られる（例えば、n ビットの）巡回鍵ベクトルを逐次（例えば、クロックに応じて）出力する巡回鍵レジスタ８２（例えば、巡回鍵レジスタ手段１０２）と、巡回鍵レジスタ８２から逐次出力される巡回鍵ベクトルと、メッセージレジスタ８１から１ビットずつ逐次出力されるメッセージビット（例えば、M[i]）とに基づいて、そのメッセージビットが１のときに巡回鍵ベクトルを出力し、そのメッセージビットが０のときに巡回鍵ベクトルと同じビット数のオールゼロベクトルを出力する論理積演算手段８３（例えば、論理積演算手段１０３）と、論理積演算手段８３によって出力されたビット数と同数の演算結果を累積して（例えば、１番目のクロックに応じた演算結果からｎ番目のクロックに応じた演算結果までを累積して）排他的論理和（例えば、XOR ）を算出し、ビット数と同数の演算結果が累積されたときに（例えば、ｎ番目のクロックに応じて）、排他的論理和の算出結果を出力する累積和演算手段８４（例えば、累積和演算手段１０４）とを備えている。
【００８３】
そのような構成により、n-bit 入出力のe-AXU ハッシュ関数方式を用いる場合に、鍵長がn-bit であっても、バイアスを理論最小値(1/2n)に近づけることができる。
【００８４】
また、メッセージレジスタ８１は、メッセージを１ビットずつクロックに応じて逐次出力し、巡回鍵レジスタ８２は、鍵を１ビットずつクロックに応じて逐次的に巡回置換し、巡回置換した結果得られる巡回鍵ベクトルをクロックに応じて逐次出力し、論理積演算手段８３は、クロックに応じて逐次出力される巡回鍵ベクトルとメッセージビットとに基づいて、巡回鍵ベクトルまたはオールゼロベクトルを出力し、累積和演算手段８４は、メッセージのビット数と同じクロック数（例えば、クロック１からｎ）までの演算結果を累積して排他的論理和を算出し、クロック数がメッセージのビット数と同じとき（クロックｎのとき）に、排他的論理和の算出結果を出力してもよい。
【００８５】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【００８６】
この出願は、２０１２年７月１８日に出願された日本特許出願２０１２−１５９５０５を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【００８７】
本発明は、鍵付きのユニバーサルハッシュ関数の演算を行うユニバーサルハッシュ関数演算装置に好適に適用される。例えば、本発明は、無線または有線を用いたデータ通信における認証や、データベースの改ざん検知、装置上のメモリの正当性検証といった用途に適用される。
【符号の説明】
【００８８】
１０  ユニバーサルハッシュ関数演算装置
２１  シフトレジスタ
２２  LFSR
２３  巡回レジスタ
１００  入力手段
１０１  メッセージレジスタ手段
１０２  巡回鍵レジスタ手段
１０３  論理積演算手段
１０４  累積和演算手段
１０５  出力手段
【図１】
2014013680.tif 000003
【図２】
2014013680.tif 000004
【図３】
2014013680.tif 000005
【図４】
2014013680.tif 000006
【図５】
2014013680.tif 000007
【図６】
2014013680.tif 000008
【図７】
2014013680.tif 000009
【図８】
2014013680.tif 000010
【国際調査報告】
2014013680.tif 000011
2014013680.tif 000012