(57)【特許請求の範囲】
【請求項１】
画像の指紋を生成する方法であって、
前記画像を第１の順序を有する第１群のセルに分割するステップと、
ランダムシードを発生するステップと、
前記ランダムシードに基づいて第１群の疑似ランダム数を発生するステップと、
前記画像を前記第１群の疑似ランダム数及び前記第１群のセルに基づいて第２群のセルに分割するステップと、
第２の順序を形成する第２群の擬似ランダム数を生成するステップと、
第１の順序に対応する第1群のセルを第２の順序に対応する第2群のセルと比較して前記指紋を形成するステップと、
を具えることを特徴とする指紋生成方法。
【請求項２】
前記画像を前記第１群の疑似ランダム数及び前記第１群のセルに基づいて第２群のセルに分割するステップは、前記第１群のセルを移動させるとともにスケーリングすることを特徴とする請求項１記載の方法。
【請求項３】
前記第１群のセルは前記第１群の疑似ランダム数及び第２群の疑似ランダム数に等しい数であることを特徴とする請求項１記載の方法。
【請求項４】
前記第１の順序に対応する第1群のセルを第２の順序に対応する第2群のセルと比較して前記指紋を形成するステップは、複数の評価基準を用いて各セルを評価することを特徴とする請求項１記載の方法。
【請求項５】
前記第１の順序に対応する第1群のセルを第２の順序に対応する第2群のセルと比較して前記指紋を形成するステップは、複数の評価基準から選択した一つの評価基準を用いて各セルを評価し、前記評価基準の選択は第１群及び第２群の疑似ランダム数の少なくとも一つにより指示することを特徴とする請求項１記載の方法。
【請求項６】
伝送ディジタル画像の保全性を確かめる方法であって、
請求項１に記載された方法で画像の第１の指紋を生成するステップと、
前記第１の指紋、前記画像、及び前記ランダムシードを受信機に送信するステップと、
前記受信機により、受信した前記画像及び前記ランダムシードを用いて、第２の指紋を生成するステップと、
前記第１の指紋及び前記第２の指紋を比較するステップと、
を具えることを特徴とする伝送ディジタル画像の保全性確認方法。
【請求項７】
前記送信ステップは、
前記ランダムシードを前記受信機の公開キーで暗号化し、暗号化されたシードを生成するステップと、
前記第１の指紋及び前記暗号化されたシードを前記送信機の秘密キーで暗号化するステップと、
を含むことを特徴とする請求項6記載の方法。
【請求項８】
時間スタンプを発生するステップと、
前記時間スタンプを受信機に送信するステップと、
を更に具えることを特徴とする請求項６記載の方法。
【請求項９】
前記第２の指紋を前記第１の指紋と同一の方法で形成することを特徴とする請求項６記載の方法。
【請求項１０】
請求項１又は６記載の方法を用いるセキュリティシステム。
【請求項１１】
画像と請求項１に記載の方法に従って生成された前記画像の指紋が記憶されたコンピュータ読み取り可能記憶媒体。
【請求項１２】
時間スタンプを更に具えることを特徴とする請求項１１記載のコンピュータ読取可能記憶媒体。
【請求項１３】
コンピュータプログラムを具えるコンピュータ読取可能記憶媒体であって、前記コンピュータプログラムは画像に次のステップ：
画像を第１の順序を有する第１群のセルに分割するステップ、
ランダムシードを発生するステップ、
前記ランダムシードに基づいて第１群の疑似ランダム数を発生するステップ、
前記画像を前記第１群の疑似ランダム数及び前記第１群のセルに基づいて第２群のセルに生成するステップ、
第２の順序を形成する第２群の疑似ランダム数を発生するステップ、及び
第１の順序に対応するセルを第２の順序に対応するセルと比較して指紋を形成するステップ、
を具えることを特徴とするコンピュータ読取可能記憶媒体。
【発明の詳細な説明】
【０００１】
本発明は一般に信号暗号化の技術分野に関するものであり、特に、損失を伴って伝送されたディジタル画像が変更されておらず且つ特定のソースから送られたものであるか否かを識別する方法に関するものである。これは特殊の指紋及び「署名」の生成により達成される。
【０００２】
米国特許第５，４９９，２９４号に記載されているような改ざんを阻止するディジタル信号暗号化方法は悪意の第３者が信号を変更するのを阻止する。指紋又は「ハッシ」はディジタル画像から作られる。ハッシングアルゴリズム（即ち一方向関数）が公知であり、計算が容易であるが数学的にインバートさせるのが極めて困難である。指紋は署名のクリエータを証明又は認証するために暗号化キーを用いて暗号化されるのが代表的である。暗号化自体はソースステーションで秘密キーを用いる標準公開／秘密キー暗号化技術で達成される。得られた署名は受信ステーションによりソースの公開キーを用いて解読することができる。
【０００３】
ハッシ−キー複合署名は原画像と一緒に受信ステーションに送られ、受信ステーションが推定送信機の公開キーを用いて暗号化されたハッシを解読する。受信ステーションは受信画像に同一のハッシアルゴリズムを実行し、これを解読されたハッシと比較する。これらの２つのハッシが同一である場合には、伝送中に雑音が含まれず且つその画像は第３者により変更（改ざん）されてないことになる。画像が変更されている場合、又は誤った公開キーが使われた場合には、２つのハッシは同一にならない。
【０００４】
この技術は情報の損失を伴う伝送に一般に有効でない。一般に、ディジタル化された受信画像は損失ビット又は受信ディジタル化画像を破壊する雑音を含む。従って、受信画像が改ざんされているか否かをソース画像の受信指紋と受信ディジタル化画像に基づいて生成されるディジタル化指紋との比較に基づいて確かめるのは難しい。
【０００５】
ＪＰＥＧ伝送においてこの問題を解決する他の試みが、ISLT/SPIE Symposium on Electronic Imaging: Science and Technology、1998年1月、カリフォルニア州、サンノゼ、第77-80頁に発表されているChing-Yun Lin 及び Shin-Fu Changの論文「A Robust Image Authentication Algorithm Distinguishing JPEG Compression from Malicious Manipulations」に記載されている。この方法はＪＰＥＧ圧縮伝送の連続するフレーム内の同一のブロックを比較するものである。この比較はこれらの２つのブロック間の値の差の範囲が圧縮後でも圧縮解除後でも同一に維持されるように行われる。署名は２つのブロック間の差を閾値と比較することにより生成される。前記差が閾値以上か以下かに依存して２進値“０”又は“１”が署名に入力される。この署名が伝送画像と一緒に送られ、この方法は上述したように続けらる。
【０００６】
このLin/Changの方法は、ＪＰＥＧ圧縮の固有の構造に頼るものであり、ＪＰＥＧフォーマットに従わない他の伝送（高損失伝送を含む）に使用し得ない。更に、このLin/Changの方法は改ざんが可能である。署名は連続するフレームの閾値との比較に完全に基づくため、悪意の第３者が完全に異なるデータストリームを生成し、連続するフレーム間の差がほぼ同一である（選択した閾値の範囲内にある）限り、これを受信機に送ることができる。
【０００７】
他の既知の技術は透かし技術である。一組のビット（マーク）を伝送画像に付加する。このマークは受信機により検出することができるが画像を変質してはならないようにする必要がある。この技術は海賊行為と関連する著作権保護にしばしば使用されている。この場合には画像をコピーしていないと主張する被告はなぜ透かしマークが画像内に残っているか説明を求められる。透かしマークは起源を与える有効な方法である。しかし、改ざんが起ったとき、これを指示することはできない。
【０００８】
これがため、受信画像が変更されたか否かを確かめる改善された方法が望まれている。この方法は画像から計算することは簡単であるが所定の指紋を有する画像を生成することは難しい指紋を含む必要がある。指紋法は同一の指紋を有する２つの画像を生成することは難しい特性を有する必要がある。指紋法はディジタル化信号の伝送中に損失が生ずるときでも有効である必要がある。
【０００９】
本発明の第１の態様は伝送画像の保全性を確かめる方法であり、この方法は画像を第１の順序を有する第１群のセルに分割するステップと、ランダムシード(初期値)を発生するステップと、前記ランダムシードに基づいて第１群の疑似ランダム数を発生するステップとを含む。この方法は、更に、画像を第１群の疑似ランダム数及び第１群のセルに基づいて第２群のセルを生成するステップと、第２の順序を形成する第２群の疑似ランダム数を発生するステップとを含む。この方法は、更に、第１の順序に対応するセルを第２の順序に対応するセルと比較して第１の指紋を形成するステップと、この指紋と、画像と、ランダムシードを受信機に送信するステップとを含む。この方法は、更に、受信機により、受信した画像とランダムシードとを用いて、第２の指紋を発生させるステップと、第１及び第２の指紋を比較するステップとを含む。
【００１０】
この方法は第３者が画像の指紋を変化させることなく画像を処理することを困難にする。指紋自体はランダムシードを知っていれば容易に生成し得る。しかし、このシードは第３者に未知である。画像が損失を伴って送られる場合でも、指紋は変化せず、従って依然として画像の保全性を監視するのに使用することができる。
【００１１】
本発明の他の態様は画像の指紋を生成する方法であり、この方法は画像を第１の順序を有する第１群のセルに分割するステップと、ランダムシードを発生するステップと、前記ランダムシードに基づいて第１群の疑似ランダム数を発生するステップと、画像を第１群の疑似ランダム数及び第１群のセルに基づいて第２群のセルに分割するステップとを含む。この方法は、更に、第２の順序を形成する第２群の疑似ランダム数を発生するステップと、第１の順序に対応するセルを第２の順序に対応するセルと比較して指紋を形成するステップとを含む。この指紋は上述した指紋と同一の利点を有する。
【００１２】
本発明の更に他の態様は画像を象徴する指紋を含むコンピュータ読取可能記憶媒体であり、この記憶媒体は、各々が第１数と第２数との差と閾値との比較から得られる一連の表示を具える。前記第１数は前記画像の第１群のセルの第１セルの値に対応し、前記第２数は前記画像の第２群のセルの第２セルの値に対応しする。前記第１群のセルは、前記画像を第３群のセルに分割し、前記第３群のセルを第１群の疑似ランダム数に基づいて処理することにより形成される。前記第２群のセルは前記第１群のセルに等しい数であり、且つ前記第２群の疑似ランダム数により指示される順序を有している。
【００１３】
本発明の更に他の態様はコンピュータ読取可能記憶媒体であり、この記憶媒体は、前記符号化されたデータは、画像を第１の順序を有する第１群のセルに分割し、ランダムシードを発生し、前記ランダムシードに基づいて第１群の疑似ランダム数を発生する符号化データを有する。この記憶媒体は、更に、前記画像を前記第１群の疑似ランダム数及び前記第１群のセルに基づいて第２群のセルに生成し、第２の順序を形成する第２群の疑似ランダム数を生成し、第１の順序に対応するセルを第２の順序に対応するセルと比較して指紋を形成する符号化データを有する。
【００１４】
本発明の目的は、損失を伴なって伝送される画像のソース及び保全性を検証する方法を提供することにある。
【００１５】
本発明の他の目的は、ユニークであり、容易に生成でき且つ損失を伴って伝送された後でも他の署名と比較することができるディジタル画像の署名を提供することにある。
【００１６】
これらの目的及び他の目的は図面を参照して以下に記載する本発明の説明から明らかになる。
【００１７】
図１及び図４につき説明すると、ステップ２００において、ｎ×ｎグリッド１００をソースディジタル画像１０３に適用して、ｎ２のセルを生成する。ｎの値は処理能力及び所望の確率精度に依存する。ｎ２のセルには任意所望の番号方式に従って番号を付ける（Ｃ１、Ｃ２、Ｃ３．．．Ｃｎ２）。ステップ２０２において、ランダムシード(初期値)“ｒ”を発生させる。このランダムシードは自然のソース、例えば電気的雑音、放射性崩壊、又は太陽からの宇宙線、から得るのが最良の方法である。容易に変更し得ない予測不可能なものが最適なソースを形成する。ステップ２０４において、ｒを初期値として用いて、ｎ２の疑似ランダム数(prn)を発生させる。これらの数により生ずる変位(後にもっと詳しく説明する)のために、疑似ランダム数値に境界を設ける必要がある。これらの数はランダムシードｒに適用される数学的アルゴリズムを用いて計算する。任意のアルゴリズムを使用することができる。使用アルゴリズムはいつかは突き止められるが、ランダムシードｒは容易にはつきとめられない。
【００１８】
図２につき説明すると、ステップ２０６において、各セル（Ｃ１、Ｃ２、Ｃ３．．．Ｃｎ２）をそれぞれの疑似ランダム数prnの結果として処理する(即ち変位させるとともにスケーリングする)。例えば、各セルをその原位置からprnだけ変位させるとともにその幅及び高さを変位と同量だけ(又は多数のprnにより発生される異なる量だけ)変化させる。変位によりセルが原画像の境界を越える場合には、このセルは図２に示すように反対側に巻き付ける。図から明らかなように、多数のセルが重なる。これらの新しいセル（Ｃ１’、Ｃ２’、Ｃ３’．．．Ｃｎ２’）の位置及びサイズは第３者には未知である。
【００１９】
従来の指紋は各セルに対する評価基準を発生し、対応する値を生成する。この基準を見つけるために多くの技術を使用することができる。例えば、その尺度は各セルの特定の色の量、画素の値の和、又は離散コサイン変換（ＤＣＴ）とすることができる。これらの従来の指紋では、上述したように、第３者が同一の指紋を有する異なる画像を容易に生成することができる。グリーンが変量であれば、第３者は同量のグリーンを有するセルを発生させる必要があるだけである。しかし、第３者が本発明の指紋を有する画像を生成しようとする場合、彼は多数の重なり合うセルを妨害することになる。
【００２０】
ステップ２０８において、これらの新たに生成されたセルの各々に対し、評価基準を画像の各結果エリアごとに求める。使用する実際の手段は重要でなく、従来の任意の技術で実現することができる。実験の結果、ＤＣＴを使用する場合には、ＤＣ値が必要とされるのみであり、ＡＣ値は計算にあまり寄与しないことが確かめられた。種々の技術が使用可能であり、ユーザが選択することができ、また上述した疑似ランダム数を用いてランダムに選択することができる。この種々の技術を組み合わせて一つの大きな署名を形成することもできる。目標は、第３者が同一の署名を有する異なる画像を生成することを困難にするような署名を形成することにある。
【００２１】
ステップ２１０において、第２群のｎ２の疑似ランダム数を生成させる。これらの数は新たに生成されたセルに供給すべき順序を表わす。この順序内の第１の数はセル１と比較するセル番号であり、第２の数はセル２と比較するセル番号であり、第ｎ２の数はセルｎ２と比較するセル番号である。例えば、第２組の疑似ランダム数が１４、２３、５、．．．で始まる場合には、セル１４がセル１と、セル２３がセル２と比較され、以下同様である。比較は上で決定された基準値の関係である。
【００２２】
ステップ２１２において、ペア間の関係を閾値と比較することにより指紋を生成する。ペア間の差が閾値以上である場合には、“１”が指紋に入力される。他の場合には、“０”が入力される。指紋の例を図３に示す。指紋は任意の記憶媒体に記憶することができ、また直ちに伝送することもできる。
【００２３】
送信機Ａから受信機Ｂへの伝送のために、ステップ２１４において、ランダムシードｒを受信機の公開キーＥpub(b)(r)で符号化する。次に指紋をＥpub(b)(r)に添付する。最後に、ステップ２１６及び２１８において、Ｅpub(b)(r)と指紋の組合せを送信機の秘密キーで暗号化し、Ｅpri(a)[Ｅpub(b)(r) and 指紋]を送出する。Ｅpub(b)(r)はＡの秘密キーで暗号化する必要はないこと明かである。しかし、もしそうでないとしても、少なくとも指紋はＡの秘密キーを必要とし、Ａの起源を検証することができる。
【００２４】
指紋と画像の両方を送る。画像はこれまでと同一の方法で送る。指紋に関しては、アナログ伝送をディジタルデータに割り当て、ディジタルデータを若干の損失で送ることもできる。例えば、ＮＴＳＣ標準を使用する場合には、ディジタルデータを垂直帰線期間（ＶＢＩ）中に送ることができる。ＮＴＳＣでは、画素が行ごとに水平に付勢される。最後の画素が付勢され、スクリーンの始点に戻るとき、有限の時間が必要とされる。この時間（垂直帰線期間ＶＢＩという）中に、ディジタルデータを受信することができる。他の標準方式においても同様の期間が存在する。
【００２５】
図５につき説明すると、受信側Ｂでは、画像及び指紋をＡの秘密キーを用いて解読する。その結果は、Ａ以外の他の任意のソースがメッセージを送る場合には、無意味なものとなる。誤った公開キーを使用する場合（例えば第３者Ｃの場合）む、その結果は無意味なものとる。受信機は署名及びＥ(r)を受信し、その固有の秘密キーを用いてｒを得る。受信機Ｂは受信した画像にＡが先に実行したステップと同一のステップを実行する。これらのステップは、画像をｎ×ｎグリッドに分割するステップ、疑似ランダム数を発生するステップ等である。これは受信画像の指紋を生成する。受信局がこの生成した指紋を受信した指紋と比較する。これらの２つの指紋は同一でなければならない。比較はリアルタイムで実行することができ、また指紋を記憶しておき、後で比較することもできる。伝送中に損失があっても、指紋はあまり大きな影響を受けず、指紋に有意の変化を生ずることはない。
【００２６】
署名の若干の差は伝送中の雑音を補償するために許容することができる。例えば、両指紋を比較し、両者の差（合致しない０と１の数）が閾値(ハミング距離)以下であれば許容することができる。指紋内のいくつかのビットが相違してもシステムのセキュリティに影響はない。その理由は改ざんは指紋内の多数のビットを反転するためである。雑音は僅かな変化を生ずるのみである。
【００２７】
上述のすべての変数はアルゴリズムの固有の性質に影響を与えることなく変更することができる。例えば、生成するセルの数ｎをユーザにより望まれるセキュリティの程度に依存して増減することができる。
【００２８】
以上、伝送信号の保全性及び認証を確かめる改良方法を開示した。本発明はシステムの動作を最適にする少なくとも４つの認識し得る結果を発生する。（１）各セルのサイズは第3者に未知である。これは未知のランダムシードにより発生される疑似ランダム数prnにより保護される。実際のサイジング及びスケーリングも秘密にすることができる。（２）第３者にはどのセルが比較されたかわからない。これも未知のランダム変数の関数である。（３）セルの位置は、これも発生されるランダム変数の関数であるから、未知である。（４）各セルを評価するために使用するアルゴリズム又は評価基準は未知である。上述したように、使用する評価基準もprnの関数とすることができる。
【００２９】
セキュリティの追加の要素として、時間スタンプを伝送信号に付加することができる。悪意の第３者が画像にアクセスし、遅延した画像を受信機に送り、許容し得る画像及び指紋を送信することができる惧れがある。時間スタンプは伝送に時間を付加するためこの問題を防止する。このスタンプは暗号化し、ｒ、計算された指紋及び画像と一緒に受信機に送ることができる。
【００３０】
上述したステップの正確な順序は順序どおりにする必要はない。例えば、全ての疑似ランダム数をｎ×ｎグリッドが与えられる前でも同時に発生させることができる。
【００３１】
容易に認識し得るように、本発明によれば、特殊の指紋の生成により、伝送画像が変更されていないかについての評価を、伝送中に損失があっても行うことができる。
【００３２】
好適実施例について説明したが、当業者であれば種々の変更を本発明の範囲内において行うことができること明らかである。
【図面の簡単な説明】
【図１】  本発明に従って伝送すべき画像のセルの分割及び順序付けを示す図である。
【図２】  本発明に従って新たに生成されるセルを示す図である。
【図３】  本発明による代表的な指紋を示す図である。
【図４】  画像及び図３の指紋を表わす伝送すべき信号を発生させる方法のフローチャートである。
【図５】  伝送画像及び図３の指紋を受信し、画像の保全性を確かめる方法のフローチャートである。
【図１】
0004037614.tif 000002
【図２】
0004037614.tif 000003
【図３】
0004037614.tif 000004
【図４】
0004037614.tif 000005
【図５】
0004037614.tif 000006