(57)【要約】      （修正有）【課題】十分な一様性を確保しつつ、回路規模を削減することができるハッシュ関数計算装置を提供する。【解決手段】乱数パターン出力部１１が、線形帰還シフトレジスタ（ＬＦＳＲ）により発生したＭ−１ビットの基準パタンＲＰＳに基づいて、ハッシュ値ＯＵＴを構成するビットｈｎ（ｎ＝０，１，２，…，Ｎ−１の整数）ごとに、Ｍビットの乱数パタンＲＰｎを発生させ、マスク処理部１２が、これら乱数パタンＲＰｎをＭビットの引数ＩＮに基づきそれぞれマスク処理することにより乱数データＱｎを抽出し、リダクション処理部１３が、これら乱数データＱｎごとに、当該Ｍビットの乱数データＱｎの各ビット値の排他的論理和をそれぞれ計算することにより、ハッシュ値ＯＵＴを構成する各ビット値ｈｎを出力する。【選択図】図１
2017058500.tif 000002
【特許請求の範囲】
【請求項１】
入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置であって、
線形帰還シフトレジスタ（ＬＦＳＲ）により基準パタンを発生させた後、この基準パタンに基づいて、前記ハッシュ値を構成するビットごとに、Ｍビットの乱数パタンを生成して出力する乱数パタン出力部と、
前記各乱数パタンを前記引数に基づきそれぞれマスク処理することにより乱数データを抽出するマスク処理部と、
前記乱数データごとに、当該乱数データに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、前記ハッシュ値を構成する各ビット値を出力するリダクション処理部と
を備えることを特徴とするハッシュ関数計算装置。
【請求項２】
請求項１に記載のハッシュ関数計算装置において、
前記乱数パタン出力部は、
前記線形帰還シフトレジスタ（ＬＦＳＲ）によりＭ−１ビットの前記基準パタンを発生させる基準パタン発生回路と、
前記基準パタンに基づいて、前記ハッシュ値を構成するビットごとに、互いに１ビットずつシフトしたＭビットの乱数パタンをそれぞれ生成する乱数パタン生成回路とを備える
ことを特徴とするハッシュ関数計算装置。
【請求項３】
請求項２に記載のハッシュ関数計算装置において、
前記乱数パタン生成回路は、前記ハッシュ値の最上位ビットに対応する乱数パタンとして、Ｍ−１ビットの前記基準パタンに対し、当該基準パタンの最上位ビットをＭビット目の最下位ビットとして追加したパタンを生成し、前記ハッシュ値の最上位以降の下位ビットに対応する乱数パタンとして、１ビット上位に対応する乱数パタンを、下位ビット方向に１ビットずつシフトさせた後、新たな最下位ビットを最上位ビットとしたパタンを生成することを特徴とするハッシュ関数計算装置。
【請求項４】
入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置で用いられるハッシュ関数計算方法であって、
乱数パタン出力部が、前記ハッシュ値を構成するビットごとに、Ｍビットの乱数パタンをそれぞれ発生させる乱数パタン発生ステップと、
マスク処理部が、前各記乱数パタンを前記引数に基づきそれぞれマスク処理するマスク処理ステップと、
リダクション処理部が、前記マスク処理された乱数パタンごとに、当該乱数パタンに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、前記ハッシュ値を構成する各ビット値を出力するリダクション処理ステップと
を備えることを特徴とするハッシュ関数計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ関数計算技術に関し、特に入力された引数を乱数パタンでマスク処理した後にリダクション処理することにより、ハッシュ関数の値であるハッシュ値を計算するハッシュ関数計算技術に関する。
【背景技術】
【０００２】
ハッシュ関数計算処理をデジタル回路で実装する場合、計算結果の一様性に加えて、計算処理の軽量性が求められる。なお、本発明では、デジタル回路での実装を考慮して、引数の変域およびハッシュ値の値域、さらにはこれらのビット桁数が一定であるハッシュ関数を前提とする。
従来より、このような実装条件におけるハッシュ関数計算手法として、線形合同法（ＬＣＧｓ：Linear Congruential Generators）が広く用いられている（非特許文献１など参照）。この線形合同法は、疑似乱数列(以下は乱数列と表記)を生成するアルゴリズムの１つであり、その一般形は次の漸化式（１）で表される。
【数１】
2017058500.tif 000003
【０００３】
この式（１）において、Ｘ0が乱数シードに相当し、Ａ、Ｂ、Ｍは定数で、Ｍ＞Ａ、Ｍ＞Ｂ、Ａ＞０、Ｂ≧０である。生成される乱数列は周期性を持ち、周期は最大でＭであり、ＢとＭが互いに素であること、Ａ−１がＭの持つ全ての素因数で割りきれること、Ｍが４の倍数である場合はＡ−１も４の倍数であることが、それぞれ満たされたときに最大周期Ｍを持つ。
【０００４】
したがって、線形合同法は、ほとんど記憶領域を必要とせず、実用的な擬似乱数アルゴリズムでは極めて簡素であり、低機能なプロセッサ上でも極めて高速に実装できる。また、乗算と除算が必要に見えるが、定数による乗算なのでシフトと加減算の組合せにでき、除算そのものが必要なのではなく剰余が得られれば良いので合同算術による式変形が可能、などの理由から効率的な式に変形できる。このため、他のハッシュ関数計算手法に比較して、デジタル回路化が容易であるとされている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】「線形合同法」、Wikipedia、https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%90%88%E5%90%8C%E6%B3%95
【非特許文献２】「線形帰還シフトレジスタ」、Wikipedia、https://ja.wikipedia.org/wiki/%E7%B7%9A%E5%BD%A2%E5%B8%B0%E9%82%84%E3%82%B7%E3%83%95%E3%83%88%E3%83%AC%E3%82%B8%E3%82%B9%E3%82%BF
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、このような線形合同法を用いた従来技術では、漸化式を効率的な式に変形可能ではあるが、加減算や剰余を計算するための回路が必要となるため、ある程度の回路規模が必要となり、計算処理のさらなる軽量化に対応できないという問題点があった。
【０００７】
計算処理の軽量性という観点からすれば、ハッシュ関数計算処理として、予め一様性のある乱数表を用意しておき、入力された引数でこの乱数表の乱数パタンをマスク処理する手法が考えられる。
【０００８】
図４は、ハッシュ関数計算処理の構成例である。ここでは、１６ビットの引数を入力として、４ビットのハッシュ値を計算する例が示されており、乱数表として、１６ビットの乱数パタンが１ビットずつずらして並べられた１６ビット×４ビットの乱数表が用いられている。
【０００９】
この構成例では、まず、乱数表のうちから、入力された引数のうちビット値が「１」である行と対応する行の乱数データ（４ビット分）をそれぞれ読み取ることにより、引数で乱数パタンをマスク処理する。この後、得られた各乱数データを、ビット桁ごとに排他的論理和（ＥＸＯＲ：EXclusive OR）を計算することにより、４ビットのハッシュ値が求められる。
【００１０】
しかしこのような簡素な構成例であっても、一様性のある乱数表を準備しておく必要があり、このような乱数表の記憶もしくは生成のための回路構成や処理が必要となる。また、より大きな引数の変域やハッシュ値の値域を持つハッシュ関数を実現するためには、必要となる記憶資源が大幅に増加するため、回路規模が増大し、装置の小型化・集積化・低コスト化の妨げとなるという問題点があった。
【００１１】
本発明はこのような課題を解決するためのものであり、十分な一様性を確保しつつ、回路規模を削減できるハッシュ関数計算技術を提供することを目的としている。
【課題を解決するための手段】
【００１２】
このような目的を達成するために、本発明にかかるハッシュ関数計算装置は、入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置であって、線形帰還シフトレジスタ（ＬＦＳＲ）により基準パタンを発生させた後、この基準パタンに基づいて、前記ハッシュ値を構成するビットごとに、Ｍビットの乱数パタンを生成して出力する乱数パタン出力部と、前記各乱数パタンを前記引数に基づきそれぞれマスク処理することにより乱数データを抽出するマスク処理部と、前記乱数データごとに、当該乱数データに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、前記ハッシュ値を構成する各ビット値を出力するリダクション処理部とを備えている。
【００１３】
また、本発明にかかる上記ハッシュ関数計算装置の一構成例は、前記乱数パタン出力部が、前記線形帰還シフトレジスタ（ＬＦＳＲ）によりＭ−１ビットの前記基準パタンを発生させる基準パタン発生回路と、前記基準パタンに基づいて、前記ハッシュ値を構成するビットごとに、互いに１ビットずつシフトしたＭビットの乱数パタンをそれぞれ生成する乱数パタン生成回路とを備えている。
【００１４】
また、本発明にかかる上記ハッシュ関数計算装置の一構成例は、前記乱数パタン生成回路が、前記ハッシュ値の最上位ビットに対応する乱数パタンとして、Ｍ−１ビットの前記基準パタンに対し、当該基準パタンの最上位ビットをＭビット目の最下位ビットとして追加したパタンを生成し、前記ハッシュ値の最上位以降の下位ビットに対応する乱数パタンとして、１ビット上位に対応する乱数パタンを、下位ビット方向に１ビットずつシフトさせた後、新たな最下位ビットを最上位ビットとしたパタンを生成するようにしたものである。
【００１５】
また、本発明にかかるハッシュ関数計算方法は、入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置で用いられるハッシュ関数計算方法であって、乱数パタン出力部が、前記ハッシュ値を構成するビットごとに、Ｍビットの乱数パタンをそれぞれ発生させる乱数パタン発生ステップと、マスク処理部が、前各記乱数パタンを前記引数に基づきそれぞれマスク処理するマスク処理ステップと、リダクション処理部が、前記マスク処理された乱数パタンごとに、当該乱数パタンに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、前記ハッシュ値を構成する各ビット値を出力するリダクション処理ステップとを備えている。
【発明の効果】
【００１６】
本発明によれば、事前に乱数表をメモリ等に記憶しておくかわりに、ＬＦＳＲにより乱数パタンＲＰｎが生成され、このＲＰｎに基づいて、統計的には一様乱数表を使う場合に近いハッシュ演算を行うことができる。したがって、一様性のある乱数表を準備しておく必要がなくなるため、このような乱数表の記憶もしくは生成のための回路構成や処理が不要となる。また、引数の変域やハッシュ値の値域が増大しても、必要となる記憶資源はほとんど増加しない。このため、十分な一様性を確保しつつ、回路規模を削減でき、装置の小型化や集積化、さらには低コスト化を実現することが可能となる。
【００１７】
また、本実施の形態によれば、ハッシュ関数計算にかかる構成を、後述のＶｅｒｉｌｏｇ  ＨＤＬにて表記したように、ＬＦＳＲによる乱数発生の内部構造において、計算原理上、乱数パタンとなるものや、同じく、計算原理上、恒等的となるビット間の関係を明示的に記す設計となっている。したがって、一般的な論理合成ツールを用いた場合にも、ツールが具備している論理最適化機能が有効に作用し、演算を実施するＦＰＧＡなどのＬＳＩ上の回路規模を小さくすることが可能となる。
【図面の簡単な説明】
【００１８】
【図１】本実施の形態にかかるハッシュ関数計算装置の構成を示すブロック図である。
【図２】乱数パタン出力部の構成例である。
【図３】ハッシュ関数計算処理を示すフローチャートである。
【図４】ハッシュ関数計算処理の構成例である。
【発明を実施するための形態】
【００１９】
次に、本発明の一実施の形態について図面を参照して説明する。
［ハッシュ関数計算装置］
まず、図１を参照して、本実施の形態にかかるハッシュ関数計算装置１０について説明する。図１は、本実施の形態にかかるハッシュ関数計算装置の構成を示すブロック図である。
【００２０】
このハッシュ関数計算装置１０は、全体としてＬＳＩなどの集積回路に実装可能なデジタル回路から構成されており、入力されたＭ（Ｍは２以上の整数）ビットの引数ＩＮから、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値ＯＵＴを計算して出力する回路装置である。
ハッシュ関数計算装置１０には、主な回路部として、乱数パタン出力部１１、マスク処理部１２、およびリダクション処理部１３が設けられている。
【００２１】
乱数パタン出力部１１は、ハッシュ値ＯＵＴを構成するビットｈｎ（ｎ＝０，１，２，…，Ｎ−１の整数）ごとに、Ｍビットの乱数パタンを発生させる機能を有している。
図２は、乱数パタン出力部の構成例である。この乱数パタン出力部１１は、Ｍ−１ビットの基準パタンＲＰＳを発生させる基準パタン回路１１Ａと、基準パタンＲＰＳに基づいて、ハッシュ値ＯＵＴを構成するビットｈｎごとに、互いに１ビットずつシフトしたＭビットの乱数パタンＲＰｎをそれぞれ生成する乱数パタン生成回路１１Ｂとから構成されている。
【００２２】
基準パタン回路１１Ａは、線形帰還シフトレジスタ（ＬＦＳＲ：Linear Feedback Shift Register）を用いることにより、Ｍ−１ビットの周期を有するＬＦＳＲ系列パタンとして、ビットａｍ（ｍ＝０，１，２，…，Ｍ−１の整数）からなるＭ−１ビットの基準パタンＲＰＳを発生させる機能を有している。基準パタンＲＰＳは、予め与えられるシード値に応じてビットパタンが変化するが、同一ハッシュ関数を用いる場合、基準パタンＲＰＳを変更する必要はない。ＬＦＳＲの具体例としては、例えば非特許文献２などの公知技術を用いればよい。
【００２３】
乱数パタン生成回路１１Ｂは、ハッシュ値ＯＵＴの最上位ビットに対応する乱数パタンＲＰＮ−１として、Ｍ−１ビットの基準パタンＲＰＳに対し、基準パタンＲＰＳの最上位ビットをＭビット目の最下位ビットとして追加したパタンを生成する機能と、ハッシュ値ＯＵＴの最上位以降の下位ビットに対応する乱数パタンＲＰｉ（ｉ＝０，１，２，…，Ｎ−２の整数）として、１ビット上位に対応する乱数パタンを、下位ビット方向に１ビットずつシフトさせた後、新たな最下位ビットを最上位ビットとしたパタンを生成する機能とを有している。
【００２４】
マスク処理部１２は、各乱数パタンＲＰｎを引数ＩＮに基づきそれぞれマスク処理することにより、ハッシュ値ＯＵＴを構成するビットｈｎごとに乱数データＱｎを抽出する機能を有している。
【００２５】
このマスク処理部１２は、ハッシュ値ＯＵＴを構成するビットｈｎごとに設けられた、論理積回路ＡＮＤ＃ｎから構成されている。論理積回路ＡＮＤ＃ｎは、Ｍビットの引数ＩＮとＭビットの乱数パタンＲＰｎとについて、ビットごとに論理積を計算し、Ｍビットの乱数データＱｎを出力する機能を有している。
【００２６】
リダクション処理部１３は、乱数データＱｎごとに、当該乱数データＱｎに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、ハッシュ値ＯＵＴを構成する各ビット値ｈｎを出力する機能を有している。
【００２７】
このリダクション処理部１３は、ハッシュ値ＯＵＴを構成するビットｈｎごとに設けられた、排他的論理和回路ＥＸＯＲ＃ｎから構成されている。排他的論理和回路ＥＸＯＲ＃ｎは、Ｍビットの乱数データＱｎに含まれる各ビット値の排他的論理和を計算して、ハッシュ値ＯＵＴを構成するビットｈｎとして出力する機能を有している。
【００２８】
［本実施の形態の動作］
次に、本実施の形態にかかるハッシュ関数計算装置１０の動作について説明する。
入力されたハッシュ関数の引数ＩＮは、複数のビットにより構成される２進表現において、１単位時間（以下クロック）に、必要とするビット数（Ｍビット）のすべてが到来するものとしている。以下では、引数ＩＮのビット数ＭがＭ＝１６ビットである場合を例として説明するが、これに限定されるものではない。
【００２９】
基準パタン回路１１Ａは、事前に用意したＬＦＳＲ系列パタンを基準パタンＲＰＳとして備える。ここで、ＬＦＳＲ系列パタンとは、非特許文献２として掲げたＬＦＳＲによるＭ系乱数発生器から発生される所定の周期を有するビット系列である。
【００３０】
図２では、具体例として、周期が１５（＝Ｍ−１）ビットのものを例として掲げている。これは、４ビットのシフトレジスタによって構成されるＬＦＳＲがM系乱数を生成している場合に相当する。また、図２では、基準パタンＲＰＳを構成する各ビットを、ビットａｊ（ｊ＝０，１，２，…，Ｍ−２の整数）により表している。
【００３１】
乱数パタン生成回路１１Ｂにおいて、基準パタンＲＰＳから図２に示す配線により構成される１６ビットの値を、乱数パタンＲＰ３，ＲＰ２，ＲＰ１，ＲＰ０とする。これにより、これら４つの乱数パタンＲＰ３，ＲＰ２，ＲＰ１，ＲＰ０の、お互いに同じビット位置を連結した４ビットの値が、ＬＦＳＲにより発生されたＭ系乱数の４ビットに相当することになる。
【００３２】
乱数パタンＲＰ３，ＲＰ２，ＲＰ１，ＲＰ０の生成例について説明する。
まず、ＲＰ３は、１５ビットのＲＰＳに対し、ＲＰＳの最上位ビットａ１４を１６ビット目の最下位ビットとして追加することにより生成される。したがって、ＲＰ３は、最上位ビットから順に、ａ１４，ａ１３，…，ａ２，ａ１，ａ０，ａ１４の１６ビットとなる。
【００３３】
次に、ＲＰ２は、１ビット上位に対応する乱数パタンであるＲＰ３の各ビットａ１４，ａ１３，…，ａ２，ａ１，ａ０，ａ１４を、下位ビット方向に１ビットずつシフトさせて最下位ビットａ１４を破棄することにより、ａ１４，ａ１３，…，ａ２，ａ１，ａ０とした後、新たな最下位ビットａ０を最上位ビットとしたパタンを生成する。したがって、ＲＰ２は、最上位ビットから順に、ａ０，ａ１４，ａ１３，…，ａ２，ａ１，ａ０の１６ビットとなる。
【００３４】
これ以降、同様にして、ＲＰ１は、ＲＰ２の各ビットａ０，ａ１４，ａ１３，…，ａ２，ａ１，ａ０を、下位ビット方向に１ビットずつシフトさせて最下位ビットａ０を破棄することにより、ａ０，ａ１４，ａ１３，…，ａ２，ａ１とした後、新たな最下位ビットａ１を最上位ビットとしたパタンを生成する。したがって、ＲＰ１は、最上位ビットから順に、ａ１，ａ０，ａ１４，ａ１３，…，ａ２，ａ１の１６ビットとなる。
【００３５】
さらにＲＰ０は、ＲＰ１の各ビットａ１，ａ０，ａ１４，ａ１３，…，ａ２，ａ１を、下位ビット方向に１ビットずつシフトさせて最下位ビットａ１を破棄することにより、ａ１，ａ０，ａ１４，ａ１３，…，ａ２とした後、新たな最下位ビットａ２を最上位ビットとしたパタンを生成する。したがって、ＲＰ０は、最上位ビットから順に、ａ２，ａ１，ａ０，ａ１４，ａ１３，…，ａ２の１６ビットとなる。
【００３６】
ここで、マスク処理回路１２は、入力された引数ＩＮの値で、乱数パタンＲＰ３，ＲＰ２，ＲＰ１，ＲＰ０をマスク処理する。すなわち、引数ＩＮと乱数パタンＲＰｎ（ｎ＝０，１，２，３）とにおいて、対応するビット位置がともに「１」ならば、そのビット位置が「１」となるよう、対応するビットごとの論理積演算を行う。
【００３７】
さらにその結果を、リダクション処理回路１３が、１６ビット中の「１」のビット数の奇遇に応じて、奇ならば「１」、遇ならば「０」を出力する。これらが４組あることによって、４つのビットｈ３，ｈ２，ｈ１，ｈ０を得て、これらを連結させることによりハッシュ値ＯＵＴとして出力する。
【００３８】
曖昧さを回避する目的で、以上のハッシュ関数計算過程を、デジタル回路設計用のハードウェア記述言語として広く利用されているｖｅｒｉｌｏｇ  ＨＤＬ言語を用いて明示的に表記すると、入力される１６ビットの引数をＩＮとし、基準パタンをＲＰＳとした場合、４ビットのハッシュ値ＯＵＴを出力するハッシュ関数計算過程は、次の式（２）で表される。
【数２】
2017058500.tif 000004
【００３９】
［ハッシュ関数計算処理］
次に、図３を参照して、本実施の形態にかかるハッシュ関数計算装置１０の動作について説明する。図３は、ハッシュ関数計算処理を示すフローチャートである。
ハッシュ関数計算装置１０は、入力された引数ＩＮのハッシュ値ＯＵＴを計算する際、図３のハッシュ関数計算処理を実行する。
【００４０】
まず、ハッシュ関数計算装置１０の外部から引数ＩＮを入力する（ステップ１００）。この際、引数ＩＮはＭビットすべてについて並列的に入力されるものとする。
【００４１】
次に、マスク処理回路１２は、引数ＩＮと乱数パタン出力部１１から出力された乱数パタンＲＰｎ（ｎ＝０，１，２，…，Ｎ−１の整数）とを、それぞれの論理積回路ＡＮＤ＃ｎでマスク処理することにより、乱数データＱｎを計算する（ステップ１０１）。
【００４２】
この際、乱数パタンＲＰｎは、乱数パタン出力部１１において予め生成されているものとする。これら乱数パタンＲＰｎは、図２に示したとおり、基準パタンＲＰＳの各ビットａ（ｊ＝０，１，２，…，Ｍ−２の整数）をビット操作することにより生成される。このビット操作は、シフトレジスタやラッチなどのデジタル回路で構成してもよいが、基準パタン回路１１Ａから出力される基準パタンＲＰＳの各ビットａｊと、マスク処理回路１２の各論理積回路ＡＮＤ＃ｎの入力端子とを接続する配線により実現してもよい。
【００４３】
この後、リダクション処理部１３は、乱数データＱｎに対応する排他的論理和回路ＥＸＯＲ＃ｎで、Ｑｎの各ビット間の排他的論理和を計算することにより、ハッシュ値ＯＵＴを構成するビットｈｎを求め（ステップ１０２）、これらビットｈｎを結合しハッシュ値ＯＵＴとして出力する（ステップ１０３）。
【００４４】
［本実施の形態の効果］
このように、本実施の形態は、乱数パタン出力部１１が、線形帰還シフトレジスタ（ＬＦＳＲ）により基準パタンＲＰＳを発生させた後、この基準パタンＲＰＳに基づいて、ハッシュ値ＯＵＴを構成するビットｈｎ（ｎ＝０，１，２，…，Ｎ−１の整数）ごとに、Ｍビットの乱数パタンＲＰｎを発生させ、マスク処理部１２が、これら乱数パタンＲＰｎを引数ＩＮに基づきそれぞれマスク処理することにより乱数データＱｎを抽出し、リダクション処理部１３が、これら乱数データＱｎごとに、当該乱数データＱｎに含まれる各ビット値の排他的論理和をそれぞれ計算することにより、ハッシュ値ＯＵＴを構成する各ビット値ｈｎを出力するようにしたものである。
【００４５】
これにより、事前に乱数表をメモリ等に記憶しておくかわりに、ＬＦＳＲにより乱数パタンＲＰｎが生成され、このＲＰｎに基づいて、統計的には一様乱数表を使う場合に近いハッシュ演算を行うことができる。したがって、一様性のある乱数表を準備しておく必要がなくなるため、このような乱数表の記憶もしくは生成のための回路構成や処理が不要となる。また、より大きな引数ＩＮの変域やハッシュ値ＯＵＴの値域を持つハッシュ関数を実現する場合でも、必要となる記憶資源はほとんど増加しない。このため、十分な一様性を確保しつつ、回路規模を削減でき、装置の小型化や集積化、さらには低コスト化を実現することが可能となる。
【００４６】
また、本実施の形態によれば、ハッシュ関数計算にかかる構成を、前述のＶｅｒｉｌｏｇ  ＨＤＬにて表記したように、ＬＦＳＲによる乱数発生の内部構造において、計算原理上、乱数パタンとなるものや、同じく、計算原理上、恒等的となるビット間の関係を明示的に記す設計となっている。したがって、一般的な論理合成ツールを用いた場合にも、ツールが具備している論理最適化機能が有効に作用し、演算を実施するＦＰＧＡなどのＬＳＩ上の回路規模を小さくすることが可能となる。
【００４７】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００４８】
１０…ハッシュ関数計算装置、１１…乱数パタン出力部、１１Ａ…基準パタン発生回路、１１Ｂ…乱数パタン生成回路、１２…マスク処理部、１３…リダクション処理部、ＩＮ…引数、ＯＵＴ…ハッシュ値、ＲＰＳ…基準パタン、ＲＰｎ，ＲＰｉ…乱数パタン、ａｍ…ビット（乱数パタン）、Ｑｎ…乱数データ、ｈｎ…ビット（ハッシュ値）。
【図１】
2017058500.tif 000005
【図２】
2017058500.tif 000006
【図３】
2017058500.tif 000007
【図４】
2017058500.tif 000008