(57)【要約】【課題】十分な一様性を確保しつつ、回路規模を削減する。【解決手段】線形帰還シフトレジスタ１１が、予め指定されたＭ系列に基づいて、入力レジスタ１３でビット値Ｂを保持するごとにＮビットの乱数データＲを発生させ、排他的論理和回路１２が、乱数データＲと計算結果ＡＣＣとについてビットごとに排他的論理和を演算してＮビットの演算結果Ｑを出力し、ＡＣＣレジスタ１５が、入力レジスタ１３で保持したビット値Ｂが１の場合にのみ、排他的論理和回路１２からの演算結果Ｑを新たな計算結果ＡＣＣとして保持し、最終ビットまで取得して得られた計算結果ＡＣＣをハッシュ値ＯＵＴとして出力する。【選択図】  図１
2017058501.tif 000002
【特許請求の範囲】
【請求項１】
入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置であって、
前記引数を先頭ビットから最終ビットまで１ビットずつ取得し、ビット値として順次保持する入力レジスタと、
予め指定されたＭ系列に基づいて、前記入力レジスタで前記ビット値を保持するごとにＮビットの乱数データを発生させる線形帰還シフトレジスタと、
前記入力レジスタで保持した前記ビット値までの計算過程で得られたＮビットの計算結果を保持するＡＣＣレジスタと、
前記乱数データと前記計算結果とについてビットごとに排他的論理和を演算してＮビットの演算結果を出力する排他的論理和回路とを備え、
前記ＡＣＣレジスタは、前記入力レジスタのビット値が１の場合にのみ、前記排他的論理和回路からの演算結果を新たな計算結果として保持し、前記最終ビットまで取得して得られた前記計算結果を前記ハッシュ値として出力する
ことを特徴とするハッシュ関数計算装置。
【請求項２】
請求項１に記載のハッシュ関数計算装置において、
前記入力レジスタのビット値が１の場合には前記排他的論理和回路からの演算結果を選択するとともに、当該ビット値が０の場合には前記ＡＣＣレジスタからの計算結果を選択するセレクタをさらに備え、
前記ＡＣＣレジスタは、前記入力レジスタでビット値を保持するごとに前記セレクタで選択された選択出力を新たな計算結果として保持する
ことを特徴とするハッシュ関数計算装置。
【請求項３】
入力されたＭ（Ｍは２以上の整数）ビットの引数から、Ｎ（ＮはＭより小さい整数）ビットのハッシュ値を計算して出力するハッシュ関数計算装置で用いられるハッシュ関数計算方法であって、
入力レジスタが、前記引数を先頭ビットから最終ビットまで１ビットずつ取得し、ビット値として順次保持するステップと、
線形帰還シフトレジスタが、予め指定されたＭ系列に基づいて、前記入力レジスタで前記ビット値を保持するごとにＮビットの乱数データを発生させるステップと、
ＡＣＣレジスタが、前記入力レジスタで保持した前記ビット値までの計算過程で得られたＮビットの計算結果を保持するステップと、
排他的論理和回路が、前記乱数データと前記計算結果とについてビットごとに排他的論理和を演算し、Ｎビットの演算結果を出力するステップとを備え、
前記ＡＣＣレジスタは、前記入力レジスタのビット値が１の場合にのみ、前記排他的論理和回路からの演算結果を新たな計算結果として保持し、前記最終ビットまで取得して得られた前記計算結果を前記ハッシュ値として出力するステップを有する
ことを特徴とするハッシュ関数計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハッシュ関数計算技術に関し、特に入力された引数を乱数データでマスク処理した後にリダクション処理することにより、ハッシュ関数の値であるハッシュ値を計算するハッシュ関数計算技術に関する。
【背景技術】
【０００２】
ハッシュ関数計算処理をデジタル回路で実装する場合、計算結果の一様性に加えて、計算処理の軽量性が求められる。なお、本発明では、デジタル回路での実装を考慮して、引数の変域およびハッシュ値の値域、さらにはこれらのビット桁数が一定であるハッシュ関数を前提とする。
従来より、このような実装条件におけるハッシュ関数計算手法として、線形合同法（ＬＣＧｓ：Linear Congruential Generators）が広く用いられている（非特許文献１など参照）。この線形合同法は、疑似乱数列(以下は乱数列と表記)を生成するアルゴリズムの１つであり、その一般形は次の漸化式（１）で表される。
【数１】
2017058501.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）１１、排他的論理和（ＥＸＯＲ）回路１２、入力レジスタ１３、セレクタ１４、ＡＣＣレジスタ１５、および制御部１６が設けられている。
【００２０】
線形帰還シフトレジスタ１１は、予め指定された多項式で生成される、所定周期のＭ系列に基づいて、入力レジスタ１３でビット値Ｂを保持するごとにＮビットの乱数データＲを発生させる機能を有している。ＬＦＳＲの具体例としては、例えば非特許文献２などの公知技術を用いればよい。
【００２１】
排他的論理和回路１２は、線形帰還シフトレジスタ１１からの乱数データＲと、ＡＣＣレジスタ１５からの計算結果ＡＣＣとについて、ビットごとに排他的論理和を演算し、Ｎビットの演算結果Ｑを出力する機能を有している。
【００２２】
入力レジスタ１３は、ハッシュ関数計算装置１０の外部から入力される引数ＩＮを、その先頭ビットから最終ビットまで１ビットずつ取得し、ビット値Ｂとして順に保持する機能を有している。
【００２３】
セレクタ１４は、入力レジスタ１３で保持したビット値Ｂが１の場合には演算結果Ｑを選択し選択出力Ｄとして出力する機能と、当該ビット値Ｂが０の場合には計算結果ＡＣＣを選択し選択出力Ｄとして出力する機能とを有している。
【００２４】
ＡＣＣレジスタ１５は、入力レジスタで保持したビット値Ｂまでの計算過程で得られたＮビットの計算結果ＡＣＣを保持する機能と、入力レジスタ１３で保持したビット値Ｂに基づいてセレクタ１４で選択された選択出力Ｄを、新たな計算結果ＡＣＣとして保持する機能と、入力レジスタ１３により最終ビットまで取得して得られた計算結果ＡＣＣをハッシュ値ＯＵＴとして出力する機能とを有している。
【００２５】
制御部１６は、入力レジスタ１３でのビット値Ｂの保持に応じて、ＡＣＣレジスタ１５での保持動作を制御する機能と、ＡＣＣレジスタ１５での保持動作完了後、線形帰還シフトレジスタ１１で発生させる乱数データＲを更新する機能とを有している。
【００２６】
［本実施の形態の動作］
次に、本実施の形態にかかるハッシュ関数計算装置１０の動作について説明する。
入力されたハッシュ関数の引数ＩＮは、複数のビットにより構成される２進表現において、１単位時間（以下クロック）に１ビットずつ、先頭ビットから最終ビットまで順に到来するものとする。以下では、引数ＩＮのビット数ＭがＭ＝４ビットである場合を例として説明するが、これに限定されるものではない。
【００２７】
線形帰還シフトレジスタ１１からは、入力レジスタ１３でビット値Ｂを保持するごとに、Ｍ系列に沿って１ビットずつシフトする、Ｎビットの乱数データＲが順に出力される。この乱数データＲは、図３の乱数表から読み取られる乱数データ（４ビット分）に相当している。
【００２８】
したがって、線形帰還シフトレジスタ１１から新たな乱数データＲが出力されるごとに、排他的論理和回路１２で、この乱数データＲと、ＡＣＣレジスタ１５で保持されている計算結果ＡＣＣとの排他的論理和が演算されてリダクション処理され、得られた演算結果Ｑがセレクタ１４の一方の選択入力として入力されることになる。
【００２９】
ここで、セレクタ１４は、入力レジスタ１３で保持されたビット値Ｂが１を示す場合、排他的論理和回路１２からの演算結果Ｑを選択してＡＣＣレジスタ１５に出力し、ビット値Ｂが０を示す場合、計算結果ＡＣＣ選択してＡＣＣレジスタ１５に出力する。
【００３０】
このため、引数ＩＮを構成するＭビットのうち、ビット値Ｂが１を示すビットに対応する乱数データＲと計算結果ＡＣＣとの排他的論理和である演算結果Ｑだけが、セレクタ１４により選択されてマスク処理されることになり、ＡＣＣレジスタ１５で計算結果ＡＣＣとして保持されることになる。
【００３１】
これにより、入力レジスタ１３で新たなビット値Ｂを保持するごとに、それまで選択されたすべての乱数データＲの排他的論理和が排他的論理和回路１２で演算されて、セレクタ１４で選択出力Ｄとして選択され、ＡＣＣレジスタ１５で計算結果ＡＣＣとして保持されることになる。したがって、最終ビットが保持されてセレクタ１４で選択された選択出力Ｄが、引数ＩＮに対応するハッシュ値ＯＵＴに相当することになる。
【００３２】
［ハッシュ関数計算処理］
次に、図２を参照して、本実施の形態にかかるハッシュ関数計算装置１０の動作について説明する。図２は、ハッシュ関数計算処理を示すフローチャートである。
ハッシュ関数計算装置１０は、入力された引数ＩＮのハッシュ値ＯＵＴを計算する際、図２のハッシュ関数計算処理を実行する。
【００３３】
まず、制御部１６は、先頭ビットが到来する前に、ＡＣＣレジスタ１５の計算結果ＡＣＣを初期化するとともに、線形帰還シフトレジスタ１１の乱数データＲを初期化する（ステップ１００）。例えば、計算結果ＡＣＣが「００００」に初期化されるとともに、乱数データＲが「１０００」に初期化される。この後、１クロックサイクルごとに、引数ＩＮのビット数分のＭ回だけ、以下のステップ１０１〜１０６の処理が繰り返し実行される。
【００３４】
まず、入力レジスタ１３は、引数ＩＮを構成する１ビットが到来するのを待機し（ステップ１０１：ＮＯ）、１ビットの到来に応じて（ステップ１０１：ＹＥＳ）、到来ビットの値をビット値Ｂとして保持する（ステップ１０２）。
ここで、ビット値Ｂが１である場合（ステップ１０３：ＹＥＳ）、セレクタ１４で選択された、排他的論理和回路１２から出力されている演算結果Ｑが、ＡＣＣレジスタ１５で計算結果ＡＣＣとして保持される（ステップ１０４）。
【００３５】
一方、ビット値Ｂが「０」である場合（ステップ１０３：ＮＯ）、セレクタ１４で選択された、ＡＣＣレジスタ１５の計算結果ＡＣＣが、ＡＣＣレジスタ１５で再び保持される。したがって、この場合には、計算結果ＡＣＣの値は変化せず、処理としてはなにもしていないことと同じである。
【００３６】
この後、制御部１６は、入力レジスタ１３で保持した到来ビットが引数ＩＮの最終ビットであるか確認し（ステップ１０５）、最終ビットでなければ（ステップ１０５：ＮＯ）、線形帰還シフトレジスタ１１に対して乱数データＲの更新を指示する。これにより、線形帰還シフトレジスタ１１は、予め指定された多項式で生成されるＭ系列に基づいて、乱数データＲを更新し（ステップ１０６）、ステップ１０１戻る。
【００３７】
一方、到来ビットが最終ビットである場合（ステップ１０５：ＹＥＳ）、ＡＣＣレジスタ１５は、この最終ビットの保持に応じてセレクタ１４で選択された選択出力Ｄをハッシュ値ＯＵＴとして保持出力し（ステップ１０７）、一連のハッシュ関数計算処理を終了する。
【００３８】
［本実施の形態の効果］
このように、本実施の形態は、線形帰還シフトレジスタ１１が、予め指定されたＭ系列に基づいて、入力レジスタ１３でビット値Ｂを保持するごとにＮビットの乱数データＲを発生させ、排他的論理和回路１２が、乱数データＲと計算結果ＡＣＣとについてビットごとに排他的論理和を演算してＮビットの演算結果Ｑを出力し、ＡＣＣレジスタ１５が、入力レジスタ１３で保持したビット値Ｂが１の場合にのみ、排他的論理和回路１２からの演算結果Ｑを新たな計算結果ＡＣＣとして保持し、最終ビットまで取得して得られた計算結果ＡＣＣをハッシュ値ＯＵＴとして出力するようにしたものである。
【００３９】
これにより、事前に乱数表をメモリ等に記憶しておくかわりに、ＬＦＳＲにより乱数データＲが生成され、この乱数データＲに基づいて、統計的には一様乱数表を使う場合に近いハッシュ演算を行うことができる。したがって、一様性のある乱数表を準備しておく必要がなくなるため、このような乱数表の記憶もしくは生成のための回路構成や処理が不要となる。また、より大きな引数ｉＮの変域やハッシュ値ＯＵＴの値域を持つハッシュ関数を実現する場合でも、必要となる記憶資源はほとんど増加しない。このため、十分な一様性を確保しつつ、回路規模を削減でき、装置の小型化や集積化、さらには低コスト化を実現することが可能となる。
【００４０】
また、本実施の形態において、入力レジスタ１３のビット値Ｂが１の場合には排他的論理和回路１２からの演算結果Ｑを選択するとともに、当該ビット値Ｂが０の場合にはＡＣＣレジスタ１５からの計算結果ＡＣＣを選択するセレクタ１４をさらに備え、ＡＣＣレジスタ１５が、入力レジスタ１３でビット値Ｂを保持するごとにセレクタ１４で選択された選択出力Ｄを新たな計算結果ＡＣＣとして保持するようにしてもよい。
これにより、簡素な回路構成で入力レジスタ１３のビット値Ｂに応じた計算結果ＡＣＣの更新処理を実現することができる。
【００４１】
［実施の形態の拡張］
以上、実施形態を参照して本発明を説明したが、本発明は上記実施形態に限定されるものではない。本発明の構成や詳細には、本発明のスコープ内で当業者が理解しうる様々な変更をすることができる。また、各実施形態については、矛盾しない範囲で任意に組み合わせて実施することができる。
【符号の説明】
【００４２】
１０…ハッシュ関数計算装置、１１…線形帰還シフトレジスタ、１２…排他的論理和回路、１３…入力レジスタ、１４…セレクタ、１５…ＡＣＣレジスタ、１…６制御部、ＩＮ…引数、ＯＵＴ…ハッシュ値、Ｒ…乱数データ、Ｑ…演算結果、Ｂ…ビット値、Ｄ…選択出力、ＡＣＣ…計算結果。
【図１】
2017058501.tif 000004
【図２】
2017058501.tif 000005
【図３】
2017058501.tif 000006