(57)【要約】  供給側と目的側のハッシュ処理の間の同期を実行するために、複数のハッシュ計算が平行に処理される。複数の動的ハッシュ比較処理が、受信されたデータシーケンスに関してそれぞれ特定の時期で又は遅延して、平行に動作する。１つの処理のハッシュ結果が供給側のデータシーケンスに関連付けられた所定のハッシュ値と一致する場合、ハッシュ結果を作った目的側のデータセットが、所定のハッシュ値を作った供給側のデータセットに対応することが確保される。
2005513565.tif 000002
【特許請求の範囲】
【請求項１】
データ値のシーケンスと供給側のハッシュ値とを受け取るように構成されたハッシュシステムであって、
複数のハッシュ装置であって、前記複数のハッシュ装置の各ハッシュ装置が、有効になると、前記データ値のシーケンスの受信データ値にハッシュ関数を適用するように構成された複数のハッシュ装置と、
前記複数のハッシュ装置に動作可能に結合され、各ハッシュ装置の出力と供給側のハッシュ値とを比較して、前記データ値のシーケンスの検証を促進するように構成された少なくとも１つの比較器と
を有するハッシュシステム。
【請求項２】
請求項１に記載のハッシュシステムであって、
各ハッシュ装置が連続して有効になるハッシュシステム。
【請求項３】
請求項１に記載のハッシュシステムであって、
各ハッシュ装置がK個のデータサンプルの継続時間の間に有効になり、
前記複数のハッシュ装置がK個のハッシュ装置に対応するハッシュシステム。
【請求項４】
供給側のデータ値のサブセットに対応する供給側のハッシュ値に基づいて、受信データ値のシーケンスと供給側との間の対応を判断する方法であって、
前記受信データ値のシーケンスの各データ値の発生時に、１つ以上のハッシュ要素を選択的に有効にし、
それぞれの有効なハッシュ要素で各データ値をハッシュして、前記１つ以上のハッシュ要素のそれぞれに対応する判断されたハッシュ値を作り、
それぞれの判断されたハッシュ値と前記供給側のハッシュ値とを比較して、前記受信データ値のシーケンスと前記供給側との間の対応を判断する
ことを有する方法。
【請求項５】
請求項４に記載の方法であって、
前記１つ以上のハッシュ要素を選択的に有効にすることが、前記１つ以上のハッシュ要素のそれぞれを連続して有効にすることを有する方法。
【請求項６】
請求項４に記載の方法であって、
前記１つ以上のハッシュ要素を選択的に有効にすることが、K個のデータ値に対応する継続時間の間に前記１つ以上のハッシュ要素のそれぞれを有効にすることを有し、
前記１つ以上のハッシュ要素がK個のハッシュ要素に対応する方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、セキュリティシステムの分野に関するものであり、特にコンテンツ素材の隣接セグメントのためのハッシュ値の計算を促進するシステムに関するものである。
【背景技術】
【０００２】
ハッシュは、複数のデータセグメントの一方向のコード化を作るために広く使用されている。一方向のコード化とは、特定の入力値又は一連の入力値からハッシュ値を作ることが容易であるが、そのハッシュ値から特定の入力値又は一連の入力値を決定することが極度に困難であり、又は実質的に不可能であるようなものである。ハッシュ値は、複数のデータ要素を‘結び付ける’ために広く使用される。特定の複数のデータ要素のハッシュ値は複数のものに合致し、１つ以上のデータ要素が変更すると、異なるハッシュ値が生じる。通信システムにおいて、一式の送信データ要素に対応するハッシュ値は、一式の受信データ要素の計算されたハッシュ値と比較され、受信データ要素が送信データ要素に対応することを検証する。ストレージシステムにおいて、ストレージ媒体に書き込まれたデータ要素のハッシュ値は、書き込まれたデータ要素に対応すると主張されたデータ要素の計算されたハッシュ値と比較され、データ要素がもとのストレージ媒体から、又はストレージ媒体に書き込まれたデータ要素の有効なコピーから読み取られたことを検証する。参照を容易にするため、ここでは“供給側”という語がもとのデータ要素を定義するために用いられ、そこで‘供給側’のハッシュ値が提供され、“目的側”という語が現用のデータ要素を定義するために用いられ、そこで供給側のハッシュ値と比較するために‘目的側’のハッシュ値が計算され、供給側と目的側のデータ値の対応を判断する。
【０００３】
ハッシュは、わずかなデータの変更ですら検出するように特に設計される。２つのデータのセットの間の単一のビットの違いが、区別可能な異なるハッシュ値を結果として生じる。特定のデータ値に対するハッシュ値の感度は、データ値を“丸める”ことによって、又は特定のデータ値の小さい変化に関わらずハッシュ関数に同じ入力を効果的に供給する他の技術によって削減され得る。しかし、ハッシュ関数に供給される特定のデータ値の選択に対するハッシュ値の感度は、削減され得ない。すなわち、データ要素が値について異なることを仮定すると、ハッシュ値が１０個のデータ値のセットに基づく場合、目的側でハッシュ値を計算するために使用される１番目から１０番目のデータ要素の選択は、供給側の同じデータ要素と一致しなければならない。すなわち、供給側と目的側のハッシュ関数は同期しなければならない。
【０００４】
供給側と目的側のハッシュ関数が同期していることを確保することは多くの場合困難である。例えば、ハッシュは、CD、DVD、その他の媒体の著作権素材のようなコピープロテクトされたコンテンツ素材のコード化で多くの場合に用いられる。特に低コストの製品を考慮して設計された消費者装置では、記録処理と再生処理における変化は、供給側と目的側の間の本当の同期を多くの場合に不可能にする。したがって、同期していないと仮定された供給側と目的側のシステムのハッシュ値を比較するように設計された従来のシステムは、一般的にローカライズされた同期を動的に判断するように構成される。すなわち、目的側において期待同期ポイントで一式のデータ値を用いてハッシュ値が決定される。計算された目的側のハッシュ値が供給側のハッシュ値に対応しない場合、目的側において期待同期ポイントから補正されたポイントで、他の目的側のハッシュ値が計算される。新しい目的側のハッシュ値が供給側のハッシュ値に対応しない場合、新しい補正が用いられ、新しい目的側のハッシュ値が計算される。ローカルの同期が達成されるまで（目的側ハッシュ＝供給側ハッシュ）、又は補正が期待同期ポイントについてある程度の合理的な限界を超え、その時点で供給側の要素と目的側の要素が異なるとう結論に達するまで、期待同期ポイントからの補正が期待同期ポイントについて継続的に展開される。このシナリオにおいて、“良く制御された”目的側装置は、ローカルの同期を早く達成する可能性が高く、あまり制御されていない（すなわち低コストの）目的側装置は、ローカルの同期を達成するために必要な時間に幅広い変化を示す可能性が高い。
【発明の開示】
【課題を解決するための手段】
【０００５】
複数のハッシュの比較のための効率的な方法とシステムを提供することが、本発明の目的である。供給側と目的側のシステム間の同期を実施するために必要な時間の可変性を削減することが、本発明の更なる目的である。
【０００６】
前記の目的等は、複数のハッシュ計算を平行して計算し、供給側と目的側のハッシュ処理の間の同期を実行することにより達成される。複数の動的ハッシュ計算処理は、受信されたデータシーケンスに関してそれぞれ特定の時期で、又は遅延して、平行に動作する。１つの処理のハッシュ結果が供給側のデータシーケンスに関連付けられた所定のハッシュ値と一致する場合、ハッシュ結果を生じた目的側のデータのセットは、所定のハッシュ値を生じた供給側のデータのセットに対応することが確保される。
【発明を実施するための最良の形態】
【０００７】
本発明は、一例として添付の図面を参照して更に詳細に説明される。
【０００８】
図面を通じて同じ参照番号は、類似の又は対応する特徴又は機能を示す。
【０００９】
図１は、本発明による平行ハッシュシステム100の例示的なブロック図を示したものである。以下目的側システムと呼ぶ前記システム100は、供給側システム（図示なし）からのものであることを意味するデータシーケンスDinを受け取る。前記データDinに伴うものが、ハッシュ値Hsourceである。ハッシュ値Hsourceは、供給側システムから安全に通信されたものと仮定され、供給側システムの特定のデータのセグメントのハッシュに対応する。受信データDinのハッシュがハッシュ値Hsourceと対応する場合、その対応は、受信データDinが供給側システムから生じたデータと対応することの証拠としての役割をする。
【００１０】
ハッシュ値Hsourceを作るために用いられるハッシュ関数とデータ要素の数は既知であるが、ハッシュ値Hsourceに対応する特定のデータ要素のセットDinは不明である。前述の通り、例えばCDでの曲のコード化は、コード化された曲の１つ以上のセグメントに対応する１つ以上のハッシュ値を有することがある。ハッシュ値を作るために用いられるデータ要素の数を含めて、各ハッシュ値を作る供給側で用いられるハッシュ関数は既知であるが、目的側システム100の各セグメントの始まりの判断は、いくらかの変化を受ける。例えば、CDの各曲の‘始まり’で生じた最初のk個のデータ要素であるとして供給側でセグメントが定められることがある。再生装置のような目的側では、１つのデータ要素の解決で曲の正確な‘始まり’を判断することは困難であることがある。目的側装置が、１つのデータ要素によるものであっても、供給側装置がハッシュ値Hsourceの判断を始めたデータストリームのポイントと異なるデータストリームのポイントのハッシュ値の判断を始めると、目的側のハッシュ値は一般的に供給側からのハッシュ値に対応しない。
【００１１】
図１に示されているものは、平行して動作される“n”個のハッシュ装置110であり、その各ハッシュ装置110は、データ要素のシーケンスDinを受け取るように接続される。各ハッシュ装置110は、対応する許可信号S1-Snによって制御される。対応する許可信号S1-Snによって有効になると、各ハッシュ装置110は、ハッシュ値Hsourceを作るために用いられたハッシュ関数と同じハッシュ関数を実行するように構成される。許可信号S1-Snは、ハッシュ値Hsourceを作るために用いられたものと同じ数のデータサンプルについてアサートされるが、それぞれ入力データDinに関して異なる時間又は時期で始まる。クロック信号Cdは、データ値のシーケンスのそれぞれの新しいデータサンプルDinで各ハッシュ装置110を起動し、現在のデータサンプルDinが、有効になった各ハッシュ装置110に適用される。簡単な実施例において、許可信号S1-Snは、それぞれの連続したデータ要素に対応するように構成される。例えば、S1は第１のデータ要素で始まり、S2は次のデータ要素の発生に対応し、S3はその次のデータ要素に対応する等である。その他、特定のデータの語の境界のように、各ハッシュ値が始まることを示すトリガー又は待ち行列を目的側装置100が受け取ると、各トリガーのポイントでS1-Snが始まるように構成される。
【００１２】
比較器120は、各ハッシュ装置110からの判断されたハッシュ値と、供給側システムからのハッシュ値Hsourceとを比較するように構成される。比較は、対応する許可信号S1-Snがアサート停止になるときの各ハッシュ値の判断の終わりに生じる。判断されたハッシュ値がハッシュ値Hsourceと等しい場合、受信データDinが供給側で生じたデータに対応することを示す合致結果M1-Mnがアサートされる。理解の容易さのため、個々の比較器120が図示されていないことに留意すべきである。判断されたハッシュを各ハッシュ値110から連続して選択する適切なスイッチ回路を備えた単一の比較器が用いられ得ることを、問うｇ放射は理解するであろう。
【００１３】
ハッシュの判断と比較が、時差的に平行した方法で生じるため、連続的な比較が起こり、合致についての従来の反復する検索が回避される。図１に示される通り、合致が生じるとすぐにそれが報告される。好ましい実施例において、平行回路の数nは、供給側と目的側のシステム間の同期の期待された変化量に対応するように選択される。例えば、期待された同期ポイントが時間Tであり、変化量が+/-T1である場合、好ましくは、nは2*T1+1である。この実施例において、S1はT-T1に対応し、S2は(T-T1)+1に対応し、以下同様であり、SnはT+T1に対応する。各ハッシュ値を計算するために用いられるデータ値の数kがn未満である場合、比較が終了した後に各段階を‘再利用’することにより、段階の数が削減され得る。すなわち、例えば第１の段階が時間(T-T1)+(k-1)でその比較を終了し、次のデータ入力Dinで新しいハッシュの判断と比較を始めるのに利用可能になる。従って、目的側システムは、k個のハッシュの判断と比較の段階を有するように構成されることが可能であり、許可信号S1-Skは、n個のデータサンプルを通じてラウンドロビン方式で循環するように構成される。すなわち、S1は、k個のデータサンプルについて時間T-T1で有効になり、次に時間(T-T1)+kで再度有効になり、その後(T-T1)+2*kで有効になり、合致が生じるまで、又はn個の比較が完了するまで、以下同様である。
【００１４】
ハッシュの判断と比較は、図１に示されるようなハードウェア、又はソフトウェア、若しくはその双方の組み合わせを介して実行されることがある。例えば、図１のハッシュ装置120は、ハッシュ関数を実行し、供給側のハッシュ値とのその後の比較のために対応するレジスタに結果を保存する複数のソフトウェア関数呼び出しとして具現化されることがある。ハッシュ関数自体は、ソフトウェアアルゴリズム、ハードウェア装置、又はプログラム可能ハードウェア装置のファームウェアの一連のステップとして具現化されることがある。他の実施例と組み合わせが当業者に明らかになる。
【００１５】
図２は、本発明による平行ハッシュシステムの例示的なフローチャートを示したものであり、それぞれのブロック又は一連のブロックは、ハードウェア、ソフトウェア又はその双方の組み合わせで具現化されることがある。
【００１６】
210において、ハッシュの判断の範囲の始まりに対応する時間に（すなわち図１のS1が最初に有効になる時）、ハッシュ値を含むために用いられる変数をクリアして、データのインデックスiをゼロに設定することにより、システムが初期化される。220において、それぞれの新しいデータ値が受け取られると、データのインデックスiが増す。図２の例示的なフローチャートにおいて、それぞれの新しいデータ値は、前記データ値に影響される各ハッシュ変数に適用される。230において、現在のデータサンプルに影響されるハッシュ変数の範囲が、変数LowerとUpperとして判断される。すなわち、例えば図１の例において、S1が最初に有効になる時に、他の許可信号S2-Snがまだ有効でないため、第１のデータサンプルのみが第1のハッシュ装置120に適用される。この例において、LowerとUpperの双方が１と等しくなるように設定される。同様に、S2が最初に有効になる時に、第２のデータサンプルが第１と第２のハッシュ装置120の双方に適用され、LowerとUpperの変数がそれぞれ１と２に設定される。LowerとUpperの変数が1からNのハッシュ変数に対応するように制約されることを、MinとMaxの関数が確保する。
【００１７】
ループ240-249が、LowerとUpperの範囲内で、現在のデータ値をそれぞれのハッシュ変数に適用する。245において、供給側システムのハッシュ関数に対応するハッシュ関数が、特定のハッシュ変数H(r)に適用される。ここで、rはLowerからUpperの範囲で順序付けられるインデックスである。
【００１８】
第1のハッシュ変数H(1)が供給側のハッシュ値Hsourceと比較され得る前に、少なくともK個のデータサンプルが処理されなければならない。K個未満のデータサンプルが受け取られている場合、250の判定ブロックが次のデータサンプルを受け取るために220へのループバックを実行する。その後、各ループ処理240-249の終わりに、Lowerのハッシュ値H(Lower)が完了し、260において、この完了したハッシュ値H(Lower)が供給側の値Hsourceと比較される。完了したハッシュ値H(Lower)が供給側のハッシュ値Hsourceと等しい場合、265において、“一致”の結果で処理が終了する。270において、前記完了したハッシュ値が最後のハッシュ変数（Lower=N）である場合、275において、“不一致”の結果で処理が終了する。その他の場合、次のデータサンプルを受け取るために、処理が220にループバックする。
【００１９】
前述の通り、ハッシュ変数を計算するために用いられるデータ値の数Kが検索範囲N未満である場合、より少ないハッシュ変数が使用され得る。この場合、ハッシュ変数へのインデックスは、ハッシュ変数を再利用するためのモジュロ（K）（modulo(K)）関数を使用し、270の後に、次のデータサンプルを受け取るためにループバックする前に、それぞれの完了したハッシュ変数がクリアされる。
【００２０】
前述のことは、単に本発明の原理を示したにすぎない。従って、ここで明示的に説明され又は示されていないが、本発明の原理を具現化し、それ故に特許請求の範囲内である多様な構成を当業者が考えることが可能であることがわかる。
【図面の簡単な説明】
【００２１】
【図１】本発明による平行ハッシュシステムの例示的なブロック図を示したものである。
【図２】本発明による平行ハッシュシステムの例示的なフローチャートを示したものである。
【図１】
2005513565.tif 000003
【図２】
2005513565.tif 000004
【国際調査報告】
2005513565.tif 000005
2005513565.tif 000006
2005513565.tif 000007