(57)【要約】【課題】数論変換による脆弱型の電子透かし法を用いた改ざん検出法。【解決手段】処理部は、数論変換のパラメータＰ、Ｎ、αを設定し（Ｓ１０１）、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込む（Ｓ１０３）。処理部は、ｆｉ、ｊ（ｘ、ｙ）を数論変換して数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算する（Ｓ１０５）。処理部は、署名画像の埋め込み位置（ｘ’、ｙ’）をランダム化関数に基づき決定し（Ｓ１０７）、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込む（Ｓ１０９）。処理部は、埋め込み位置のＦｉ、ｊ（ｘ’、ｙ’）とｇｉ、ｊとにより、各ブロックの埋め込み量δを求め（Ｓ１１１）、Ｆｉ、ｊ（ｘ、ｙ）に埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求める（Ｓ１１３）。処理部は、Ｈｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求め、それを記憶し、出力部等に出力する。【選択図】  図６
2004153493.tif 000002
【特許請求の範囲】
【請求項１】
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
を含む改ざん検出方法。
【請求項２】
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
を含む改ざん検出方法。
【請求項３】
署名画像を原画像に埋め込む処理及び署名画像を抽出する処理を含む改ざん検出方法であって、
前記埋め込む処理は、
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
を含み、
前記抽出処理は、
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
を含む改ざん検出方法。
【請求項４】
処理部は、出力部又はインターフェースを介して、抽出側装置に、法Ｐ及び埋め込み済み画像［ｈ］を、また、必要に応じて位数Ｎを送信するステップをさらに含む請求項１または３に記載の改ざん検出方法。
【請求項５】
処理部は、数論変換のためのパラメータである法Ｐと埋め込み済み画像［ｈ］、必要に応じてＮを送信側装置から受信するステップをさらに含む請求項２又は３に記載の改ざん検出方法。
【請求項６】
処理部は、埋め込み済み画像［ｈ］及び署名画像［ｇ］に基づいて、原画像［ｆ］を求めるステップをさらに含む請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項７】
Ｐは、素数のべき乗による任意の合成数であることを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項８】
Ｎは、署名画像の埋め込み側及び抽出側で共通にあらかじめ記憶部に記憶してあること、又は、埋め込み側から抽出側へ伝送されることを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項９】
処理部は、Ｎ｜ＧＣＤ［（ｐ１−１）、（ｐ２−１）、…、（ｐｍ−１）］  により求められた位数Ｎの候補から、予め定められた優先順位でいずれかの位数Ｎを選択することを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項１０】
処理部は、設定された法Ｐ及び位数Ｎに基づき、一意に算出される中国剰余定理等の予め定められた式により根αを計算することを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項１１】
処理部は、ｐｉを素数、ｒｉを正の整数として、Ｐ＝ｐ１ｒ１ｐ２ｒ２…ｐｍｒｍ  で表されるとしたＰを設定し、
処理部は、位数Ｎを、Ｎ｜ＧＣＤ［（ｐ１−１）、（ｐ２−１）、…、（ｐｍ−１）］  を満たす正の整数から選択し、又は、記憶部から読み取り、
処理部は、ｐｉを法とする位数Ｎの根α１、ｉを計算し、
処理部は、ｐｉｒｉを法とする位数Ｎの根α２、ｉを、α１、ｉより求め、
処理部は、中国剰余定理により、Ｐを法とする位数Ｎの根αを、α２、ｉより求める
ことを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項１２】
処理部は、Ｐ、Ｎ及びαを用いて、次式によりｘ（ｎ）とＸ（ｋ）との間の数論変換を実行することを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【数１】
2004153493.tif 000025
（ここに、Ｐ（素数のべき乗となる任意の合成数）、α、（を正の整数、ＮをαＮ＝１（ｍｏｄＰ）となる最小の正の整数）
Ｘ＝［Ｔ］ｘ
ｘ＝［Ｔ］−１Ｘ
（［Ｔ］：変換行列、［Ｔ］−１：逆変換行列）
【請求項１３】
前記ランダム化関数は、法Ｐの値、及び／又は、隣接するブロック若しくは埋め込み処理で変更されない所定ブロックの画素値をパラメータとし、位置を一意に決定する関数であることを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【請求項１４】
前記ランダム化関数は、以下の式による関数であることを特徴とする請求項１乃至３のいずれかに記載の改ざん検出方法。
【数２】
2004153493.tif 000026
【請求項１５】
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
をコンピュータに実行させるための改ざん検出プログラム。
【請求項１６】
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
をコンピュータに実行させるための改ざん検出プログラム。
【請求項１７】
署名画像を原画像に埋め込む処理及び署名画像を抽出する処理を含む改ざん検出方法であって、
前記埋め込む処理は、
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
を含み、
前記抽出処理は、
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
をコンピュータに実行させるための改ざん検出プログラム。
【請求項１８】
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
をコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体。
【請求項１９】
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
をコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体。
【請求項２０】
署名画像を原画像に埋め込む処理及び署名画像を抽出する処理を含む改ざん検出方法であって、
前記埋め込む処理は、
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
を含み、
前記抽出処理は、
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
をコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、改ざん検出方法、改ざん検出プログラム及びそのプログラムを記録した記録媒体に係り、特に、数論変換による脆弱型電子透かしを用いた画像の改ざん位置検出技術に関する。
【０００２】
【従来の技術】
一般に、証拠写真などの公文書で用いられる画像には原本性が十分に保証されたものが要求されるが、ディジタル画像は不自然さを排除した改ざんを比較的容易に行えるため、その証拠能力が不十分な場合がある。ゆえに、ディジタル画像における原本性保証や改ざん検出の技術が求められている。従来、これらの目的を実現する方法としてハッシュ関数を用いた電子署名が検討されてきた。しかし、電子署名は改ざんの位置検出をすることを意図していない。
【０００３】
そこで、従来より改ざん位置検出を行う一つの方法として電子透かしが注目されている。電子透かしはその性質に応じて耐性型と脆弱型との二種類に分類される。耐性型電子透かしは攻撃に対してロバストな性質を持ち、主に著作権保護を目的とする場合に用いられる。一方、改ざん位置検出には脆弱型電子透かしを使用する。脆弱型電子透かしは画像処理に対して非常に敏感に反応する性質を持つ。改ざん検出の過程において、何らかの変化を生じている電子透かしを同定することで改ざんの位置を特定できる。以下に参照文献リストを示す。
【特許文献１】
特開２００２−４４４２９号公報
【特許文献２】
特開２００２−２０１７０３号公報
【非特許文献１】
田森秀明、青木直史、山本強、“数論変換を用いた改ざん検出可能な電子透かし方式”  電子情報通信学会技術研究報告ＩＥ２００１−３３，ｐｐ．１０５−１１０，  Ｊｕｌ．  ２００１．
【非特許文献２】
田森秀明、青木直史、山本強、“数論変換による脆弱型電子透かしを用いた静止画像の改ざん位置検出と改ざん訂正”  電子情報通信学会技術研究報告ＩＥ２００２−４５，ｐｐ．１９−２４，  Ｊｕｌ．  ２００２．
【非特許文献３】
Ｈ．  Ｔａｍｏｒｉ，  Ｎ．  Ａｏｋｉ，  ａｎｄ  Ｔ．  Ｙａｍａｍｏｔｏ，  “Ａ  Ｆｒａｇｉｌｅ  Ｄｉｇｉｔａｌ  Ｗａｔｅｒｍａｒｋｉｎｇ  Ｔｅｃｈｎｉｑｕｅ  ｂｙ  Ｎｕｍｂｅｒ  Ｔｈｅｏｒｅｔｉｃ  Ｔｒａｎｓｆｏｒｍ，”  ＩＥＩＣＥ  Ｔｒａｎｓ．  Ｆｕｎｄａｍｅｎｔａｌｓ，  Ａｕｇ．２００２．
【０００４】
【発明が解決しようとする課題】
以上のような改ざん位置検出を目的とした脆弱型電子透かしの従来手法としては、ディジタルコンテンツから得られたハッシュ値やパリティ値をビットプレーンに埋めるといったものが主であった。しかしながらこれらの手法はアルゴリズム公開時の安全性に問題がある場合があり、例えば複数の異なる埋め込み済み画像から改ざん画像を合成するような、特定の改ざんは検出できなかった。
【０００５】
一方、耐性型電子透かしにおいては、離散フーリエ変換などの直交変換を利用した、比較的安全性の高い手法が数多く提案されている。そのような耐性型電子透かしの手法を脆弱型電子透かしに応用することで安全性の更なる向上が期待できると考えられる。そこで本発明者等は数論変換（ｎｕｍｂｅｒ  ｔｈｅｏｒｅｔｉｃ  ｔｒａｎｓｆｏｒｍ：  ＮＴＴ）と呼ばれる直交変換を用いた脆弱型電子透かし法を検討してきた。数論変換は、系列に与えられた変化がわずかでも、その変換結果が変化を与える前に比べ大きく異なるという脆弱な性質を持つ。
【０００６】
本発明は、以上の点に鑑み、直交変換を用いた耐性型電子透かし法を応用した数論変換による脆弱型の電子透かし法を用いた改ざん検出方法、改ざん検出プログラム及びそのプログラムを記録した記録媒体を提案することを目的とする。また、本発明は、改ざんの有無及びその位置を目視によって容易に確認することができる改ざん検出法等を提供することを目的とする。
【０００７】
さらに、従来の数論変換を利用した電子透かしの手法では、原画像の画像ビットを下位２ｂｉｔ程度という比較的少ない範囲で置換することにより署名情報を埋め込むものであった。これに対して、本発明では、原画像の画素ビットの全て又は所望の広範囲を利用して署名情報を埋め込むことにより安全性を一層高めることを目的とする。また、従来の数論変換を利用した手法では、署名情報の埋め込みを数論変換ドメインに掛け合わせて（畳み込んで）実現していた。これに対して、本発明では、署名情報の埋め込みを足し算により実現することで、演算速度を速くすることを目的とする。
【０００８】
【課題を解決するための手段】
本発明の第１の解決手段によると、
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
含む改ざん検出方法、これら各ステップをコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体が提供される。
【０００９】
本発明の第２の解決手段によると、
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
含む改ざん検出方法、これら各ステップをコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体が提供される。
【００１０】
本発明の第３の解決手段によると、
署名画像を原画像に埋め込む処理及び署名画像を抽出する処理を含む改ざん検出方法であって、
前記埋め込む処理は、
処理部は、数論変換のパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、記憶部から、埋め込み対象の原画像［ｆ］をブロック分割した原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込むステップと、
処理部は、設定された法Ｐ、位数Ｎ、根αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を数論変換して原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、各ブロックにおける署名画像の埋め込み位置（ｘ’、ｙ’）を、所定のランダム化関数に基づき決定するステップと、
処理部は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部から読み込むステップと、
処理部は、埋め込み位置の原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ’、ｙ’）と署名画像の画素値ｇｉ、ｊと埋め込み強度εにより、各ブロックの埋め込み量δを求めるステップと、
処理部は、原画像ブロックの数論変換ブロックＦｉ、ｊ（ｘ、ｙ）に、（ｘ、ｙ）に応じて埋め込み量δを加算又は減算して、埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、数論変換ブロックＨｉ、ｊ（ｘ、ｙ）の逆数論変換を計算して、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めるステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を求めることにより埋め込み済み画像［ｈ］を得て、それを記憶部に記憶する、及び／又は、出力部若しくはインターフェースにより出力するステップと
を含み、
前記抽出処理は、
処理部は、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を、記憶部又は入力部又はインターフェースから読み込むステップと、
処理部は、数論変換のためのパラメータである法Ｐ、位数Ｎ、根αを設定するステップと、
処理部は、埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換して埋め込み済み画像ブロックの数論変換ブロックＨｉ、ｊ（ｘ、ｙ）を計算するステップと、
処理部は、署名画像の埋め込み位置に対応する抽出位置（ｘ’、ｙ’）を所定のランダム化関数に基づいて決定するステップと、
処理部は、抽出位置の数論変換ブロックＨｉ、ｊ（ｘ’、ｙ’）の埋め込み強度εによる剰余を取ることによって、署名画像の画素値ｇｉ、ｊを抽出するステップと、
処理部は、全ての又は所望の範囲の（ｉ，ｊ）ブロックについて署名画像の画素値ｇｉ、ｊを求めることにより署名画像［ｇ］を得て、それを記憶部に記憶する、及び／又は、表示部若しくは出力部若しくはインターフェースに出力するステップと
含む改ざん検出方法、これら各ステップをコンピュータに実行させるための改ざん検出プログラムを記録した記録媒体が提供される。
【００１１】
【発明の実施の形態】
１．数論変換
１．１  概要
はじめに、数論変換について説明する。なお、数論変換については、必要であれば以下の文献を参照のこと。
−  Ｊ．  Ｈ．  ＭｃＣｌｅｌｌａｎ，  ａｎｄ  Ｃ．  Ｍ．  Ｒａｄｅｒ，  “Ｎｕｍｂｅｒ  Ｔｈｅｏｒｙ  ｉｎ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｌ  Ｐｒｏｃｅｓｓｉｎｇ，”  Ｐｒｅｎｔｉｃｅ−Ｈａｌｌ，  Ｎｅｗ  Ｊｅｒｓｅｙ，  １９７９．
−  電子情報通信学会（編）、ディジタル信号処理ハンドブック、オーム社、東京、１９９３．
−  Ｓ．Ｃ．Ｃｏｕｔｉｎｈｏ（著）、林彬（訳）、暗号の数学的基礎、シュプリンガー・フェアラーク東京株式会社、東京、２００１．
−  Ｈ．Ｊ．Ｎｕｓｓｂａｕｍｅｒ（著）、佐川雅彦、本間仁志（訳）、高速フーリエ変換のアルゴリズム、科学技術出版社、東京、１９８９．
−  谷荻隆嗣（著）、ディジタル信号処理ライブラリー４  アルゴリズムと並列処理、コロナ社、東京、２０００．
−  青木由直、波動信号処理、森北出版、東京、１９８６
【００１２】
まず、パラメータＰ、αを正の整数、ＮをαＮ＝１ｍｏｄＰとなる最小の正の整数とする。ここで、φ（Ｐ）をＥｕｌｅｒ関数とすると、Ｎ＝φ（Ｐ）となるαを位数Ｎの原始根と呼び、Ｎ＜φ（Ｐ）のαを、単に位数Ｎの根と呼ぶ。なお、φ（Ｐ）は、Ｐより小さく、かつＰに対し互いに素となる整数の個数を表す。
ここで、αを用いた次のような変換対を考える。
【００１３】
【数３】
2004153493.tif 000003
【００１４】
上式の計算は、Ｐを法とする剰余数系ですべての演算が可能なため、丸め誤差を一切生じない。電子透かしへの応用を考えたとき、Ｐを秘匿しておけば、数論変換の性質から、第三者は期待する変換結果を得ることができないため、Ｐは鍵情報として利用できる。ところで、数論変換においてはＰには、メルセンヌ数やフェルマー数を用いるのが代表的である（例えば、電子情報通信学会（編）、ディジタル信号処理ハンドブック、オーム社、東京、１９９３  等参照。）。しかしながら、これらには厳しい制限があり、選択できる数が少なく鍵情報として用いるのには不適当な場合があった。そこで、Ｐが素数のべき上による任意の合成数でも可能である手法を適用する。
ｐを素数として、
【００１５】
【数４】
2004153493.tif 000004
【００１６】
で表されるとする。まず、位数Ｎを
【００１７】
【数５】
2004153493.tif 000005
【００１８】
を満たす正の整数から選択する。ｐｍを法とする位数Ｎの根α１、ｍを計算し、次に位数Ｎの根α２、ｍを
【００１９】
【数６】
2004153493.tif 000006
【００２０】
で求める。続いて中国剰余定理によりα２、ｍからＰを法とする位数Ｎの根αを求めることができる（例えば、Ｈ．Ｊ．Ｎｕｓｓｂａｕｍｅｒ（著）、佐川雅彦、本間仁志（訳）、高速フーリエ変換のアルゴリズム、科学技術出版社、東京、１９８９  等参照。）。
【００２１】
一般に、剰余系で演算を行う場合取扱える数の範囲を広げるため、異なる法の剰余系の組を用い、演算結果は法ごとの結果の組となる場合がある。中国剰余定理（Ｃｈｉｎｅｓｅ  ｒｅｍａｉｎｄｅｒ  ｔｈｅｏｒｅｍ）は、この組からある進数で唯一に定まる数を求めるもので次のように表わせる。（青木由直「波動信号処理」、森北出版株式会社、１９８６年４月３日、参照）
［定理］  法ｍｉ（ｉ＝１、２、・・・、ｌ）を互いに素な正整数に選びＭ＝ｍ１ｍ２・・・ｍｌとすると
＜ａ＞ｍｉ＝ｒｉ  （ｉ＝１、２、・・・、ｌ）
（ここに、ｒｉは法ｍｉに関するａの剰余である。）
を満足する正整数ａ（０＜ａ≦Ｍ−１）は次式で唯一に与えられる。
ａ＝Σｄｉｄｉ−１ｒｉ  （ｍｏｄ  Ｍ）
ここで、
Σは、ｉ＝１〜ｌの和
ｄｉ＝Ｍ／ｍｉ  、
ｄｉ−１＝（＜ｄｉ＞ｍｉ）−１  （ｍｏｄ  ｍｉ）
（なお、（＜ｄｉ＞ｍｉ）−１は法ｍｉでの乗法逆元。）
【００２２】
１．２  例
例えば、Ｐ＝６１００９＝１３２×１９２による数論変換を考える。まず、ＧＣＤ［１２、１８］＝６より、ＮをＮ｜６＝［１、２、３、６］から選択する。ここではＮ＝３を採用する。次に１３と１９を法とする位数３の根を計算する。それぞれをα１、１、α１、２とすると、α１、１＝３、α１、２＝７である。よって、１３２と１９２を法とする位数３の根をα２、１、α２、２とすると、次のようになる。
【００２３】
【数７】
2004153493.tif 000007
【００２４】
続いて、よく知られた中国剰余定理により、６１００９を法とする位数３の根はα＝６５３と求まる。
図１に、素数１３のｙｘ（ｍｏｄ  １３）の説明図を示す。
例えば、１３を法とする位数３の根の見つけ方を考える。ｙが縦、ｘが横である。１が出る周期がＮである時、ｙを１３を法とした位数Ｎ（ここだと３）である。ｙ＝３、９の時、３つおきに“３”が出ているため、３、９が根である。ここでは、例えば、複数の根のうち最小のものを選択することとすると、根＝３となる。なお、数論の全般的なことについては、ｈｔｔｐ：／／ｆｏｘ．ｚｅｒｏ．ａｄ．ｊｐ／￣ｚａｔ２５９６０／ｍａｔｈ／ｎｕｍｂｅｒ／ｉｎｄｅｘ．ｈｔｍ等参照。
【００２５】
ここで、一例として、以上に基づき、Ｎ＝３の系列ｘ＝［１０、２０、３０］Ｔの数論変換を考える。式（１）、（２）は行列表示すると次のようになる。
Ｘ＝［Ｔ］ｘ
ｘ＝［Ｔ］−１Ｘ
ただし、
Ｘ＝［Ｘ（０）、Ｘ（１）、Ｘ（２）］Ｔ
ｘ＝［ｘ（０）、ｘ（１）、ｘ（２）］Ｔ
である。変換行列［Ｔ］は、
【００２６】
【数８】
2004153493.tif 000008
【００２７】
となり、逆変換行列［Ｔ］−１は
【００２８】
【数９】
2004153493.tif 000009
【００２９】
となる。ｘを数論変換すると、
【００３０】
【数１０】
2004153493.tif 000010
【００３１】
となり、［Ｔ］−１を用いて逆変換すると、
ｘ＝［Ｔ］−１Ｘ＝［１０、２０、３０］Ｔ（ｍｏｄ  ６１００９）
が得られる。
【００３２】
ここで、例えば、変換後の系列Ｘ＝［６０、５４４５９、６５２０］ＴがＸ’＝［６１、５４４５９、６５２１］Ｔに改ざんされたとする。逆変換後の出力ｘ’は、
ｘ’＝［Ｔ］−１Ｘ’＝［１１、２３８、４０４８５］Ｔ（ｍｏｄ  ６１００９）
となり、ｘとは全く異なる。この結果は、丸め誤差の生じない数論変換の性質から得られるもので、改ざん検出に有効であるといえる。
【００３３】
２．ハードウェア
図２に、システム構成の概略図を示す。このシステムでは、送信者用コンピュータ１０、受信者用コンピュータ２０、認証機関用コンピュータ３０を備える。送信者コンピュータ１０から受信者用コンピュータ２０へは署名情報が電子透かしで埋め込まれた画像情報［ｈ］が伝達される。なお、署名データ［ｇ］は送信者用コンピュータ１０から受信者用コンピュータ２０との間で予め決定されている。送信者用コンピュータ１０から認証機関用コンピュータ３０は鍵情報Ｐ、さらに、必要に応じて位数Ｎが送られる。受信者用コンピュータ２０は認証機関用コンピュータ３０からこれら鍵情報Ｐさらに、必要に応じてＮを取得する。
【００３４】
上述のシステム構成以外にも、認証機関用コンピュータ３０を省略して直接送信者用コンピュータ１０と受信者用コンピュータ２０との間で［ｈ］、Ｐ、さらに必要によりＮを送受信するようにしても良い。
【００３５】
送信者から受信者への［ｈ］、Ｐ、Ｎの伝送手段は、例えば、次のような手段がある。ここで、［ｈ］は公開してもかまわないため、受信者用コンピュータ２０は送信者用コンピュータ１０からｅ−ｍａｉｌで直接送信しても特に問題ないが、鍵情報Ｐは秘密鍵のため、送信者用コンピュータ１０から受信者用コンピュータ２０又は認証機関コンピュータ３０に送信する場合にはセキュリティの観点から、ＲＳＡなどの暗号化を施した後に送信すると良い。例えば、ディジタルカメラでの運用を考えた場合、カメラから直接認証機関に送信されることが一案である。この場合はｅ−ｍａｉｌではなく、暗号化ファイルを直接パケット交換や回線交換で送信することもできる。これら鍵情報を受信者用コンピュータ２０又は認証機関コンピュータ３０から送信者用コンピュータ１０が受信する場合も同様である。
【００３６】
図３は、改ざん位置検出装置の構成図である。
この装置は、中央処理装置（ＣＰＵ）である処理部１、入力部２、出力部３、表示部４、記憶部５、インターフェース６を有する。また、処理部１、入力部２、出力部３、表示部４及び記憶部５は、スター又はバス等の適宜の接続手段で接続されている。記憶部５は、数論変換のパラメータを記憶する鍵ファイル５１、原画像［ｆ］を記憶する原画像ファイル５２、署名画像ファイル［ｇ］を記憶する署名画像ファイル５３、埋め込み済み画像ファイル［ｈ］を記憶する埋め込み済み画像ファイル５４を含む。記憶部５は、さらに、後述するようなランダム化関数ｒｘ’、ｒｙ’、埋め込み強度εを予め記憶する。インターフェース６は、インターネット、移動体通信網等の各種ネットワークと接続され、他のコンピュータと情報の送受を無線、又は有線で行う。
【００３７】
３．改ざん位置検出
３．１  直交変換による耐性型電子透かし法
まず、参考として、離散フーリエ変換による電子透かし法の一例について説明する。
図４に、離散フーリエ変換による電子透かし法の一例についての説明図を示す。図（ａ）は、埋め込み処理について、図（ｂ）は抽出処理について、それぞれ示す。
耐性型電子透かし法では、直交変換により得られた空間周波数領域に署名情報を埋め込む手法が数多く発表されている。そのような電子透かし法の一例として、図に示すような離散フーリエ変換を用いた手法について述べる。
【００３８】
埋め込み処理では、まず、処理部１は原画像［ｆ］（ＫＮ×ＬＮ画素、８ｂｉｔ階調）をＮ×Ｎ画素のブロックに分割する。この分割した各ブロックをｆｉ、ｊ（ｘ、ｙ）と表し、ｉ、ｊは画像中でのブロックの位置を、ｘ、ｙはブロック中での画素の座標を表す（ｉ＝０、１、…、Ｋ−１；ｊ＝０、１、…、Ｌ−１；ｘ、ｙ＝０、１、…、Ｎ−１）。次に、ｆｉ、ｊ（ｘ、ｙ）の２次元フーリエ変換を行い、この変換結果をＦｉ、ｊ（ｘ、ｙ）で表す。
【００３９】
ここで、処理部１は、署名画像［ｇ］（Ｋ×Ｌ画素、１ｂｉｔ階調）を記憶部５から読み出すこと等により用意する。［ｇ］の各画素値はｇｉ、ｊ（＝０又は１）とし、ｉ、ｊは［ｇ］の中での画素の座標を表すが、ｆｉ、ｊ（ｘ、ｙ）のｉ、ｊと対応する。処理部１は、ｇｉ、ｊをＦｉ、ｊ（ｘ、ｙ）の低周波成分に加え、埋め込み済みブロックのフーリエ変換Ｈｉ、ｊ（ｘ、ｙ）を得る。つまり、εを埋め込み強度、（ｘ’、ｙ’）を埋め込む要素の座標とすると、次式となる。
【００４０】
【数１１】
2004153493.tif 000011
【００４１】
このとき、εと（ｘ’、ｙ’）は、埋め込み処理と抽出処理であらかじめ共通にユーザが一意に設定しておけば、これらは埋め込み画像を抽出するための鍵となる。つぎに、処理部１は、Ｈｉ、ｊ（ｘ、ｙ）を逆フーリエ変換し、埋め込み済みブロックｈｉ、ｊ（ｘ、ｙ）を得る。処理部１は、以上の操作をすべてのブロックに行い、埋め込み済み画像［ｈ］を得る。
一方、署名情報の抽出処理については、処理部１が、Ｈｉ、ｊ（ｘ’、ｙ’）とＦｉ、ｊ（ｘ’、ｙ’）の差分を取ることで実現する。つまり、次式によりｇｉ、ｊを求める。
【００４２】
【数１２】
2004153493.tif 000012
【００４３】
以上のような手法では署名情報が低周波成分に埋め込まれていることから、多少の画像処理などの攻撃では署名情報は破壊されにくく、ロバストな手法となっている。このような理由から、直交変換によって得られる空間周波数領域を用いた手法は、著作権保護を目的とした耐性型電子透かし法に多く用いられている。
【００４４】
３．２  数論変換による脆弱型電子透かし法
図５に、数論変換による脆弱型電子透かし法についての説明図を示す。図（ａ）は、埋め込み処理について、図（ｂ）は抽出処理について、それぞれ示す。
数論変換は離散フーリエ変換と同型の直交変換であるが、その変換領域には周波数領域のような物理的意味が無いため、上述の「３．１  直交変換による耐性型電子透かし法」をそのまま適用できない。また、上述３．１の手法では署名情報の抽出には原画像が必要なため、改ざん位置検出という目的では実用性に欠けることがある。ここでは、これらの課題を考慮した図示のような手法を提案する。
【００４５】
３．２．１．  埋め込み処理
図６及び図７に、埋め込み処理のフローチャート（１）及び（２）を示す。
埋め込み処理が開始されると、処理部１は、数論変換のパラメータである法Ｐ、及び位数Ｎ、根αを設定する（Ｓ１０１）。
【００４６】
Ｐは、例えば、あらかじめユーザが入力部２によって鍵ファイル５１に設定するか、処理部１が熱雑音等を利用してランダムな値に決定することにより、処理前にあらかじめ鍵ファイル５１に記憶しておく。処理部１は鍵ファイル５１を参照してＰを設定する。また、Ｐは、式（３）のように、素数のべき乗による任意の合成数を選択することができるが、剰余計算において画素値が取りうるすべての整数を扱うために、ここでは、処理部１は、一例として、画素値の最大値より大きな整数から選択する。
【００４７】
処理部１は、Ｐの決定後、式（４）に基づきＮを選択する。処理部１は鍵ファイル５１を参照するか、式（４）などを用いて計算することでＮを設定する。Ｎは、あらかじめ入力部２により鍵ファイル５１に記憶しておいても良いし、また、処理部１が、式（４）により、Ｐに依存した候補を求め、複数個の候補があるときはその中からいずれかを選択するようにしても良い。Ｎはブロックサイズであるので、大きすぎると正確な位置検出が出来ないことがあるので、一例としてＮ＝２、４くらいが適当だと思われるが、これらはユーザが任意に選択するか、あらかじめシステムとして適当な選択方法を決定しておくことができる。
【００４８】
Ｐ、Ｎが決定されると、処理部１は、式（５）及び中国製剰余定理等により根αを計算することで、根αは一意に算出される。Ｐ、Ｎが未知である限り、後述する抽出処理が不可能であることから、Ｐ又はＰとＮの両方が、改ざん検出における鍵となる。
【００４９】
つぎに、処理部１は、記憶部５の原画像ファイル５２から、原画像［ｆ］をブロックに分割した埋め込み対象の原画像ブロックｆｉ、ｊ（ｘ、ｙ）を読み込む（Ｓ１０３）。なお、上述と同様に原画像［ｆ］（ＫＮ×ＬＮ画素）をＮ×Ｎ画素のＫ×Ｌ個のブロックに分割し、この分割した各ブロックをｆｉ、ｊ（ｘ、ｙ）と表し、ｉ、ｊは画像中でのブロックの位置を、ｘ、ｙはブロック中での画素の座標を表す（ｉ＝０、１、…、Ｋ−１；ｊ＝０、１、…、Ｌ−１；ｘ、ｙ＝０、１、…、Ｎ−１）。
【００５０】
つぎに、処理部１は、式（１）、（２）に基づいて、ステップＳ１０１で設定したＰ、Ｎ、αを用いて、原画像ブロックｆｉ、ｊ（ｘ、ｙ）を２次元数論変換された原画像ブロックＦｉ、ｊ（ｘ、ｙ）を計算する（Ｓ１０５）。
つぎに、処理部１は、埋め込み済み画像ブロックの数論変換Ｈｉ、ｊ（ｘ、ｙ）を、次式を用いて、以下に詳細に説明するように求める。
【００５１】
【数１３】
2004153493.tif 000013
【００５２】
ただし、δは式（９）を満たす、絶対値が最小の整数とする。
【００５３】
【数１４】
2004153493.tif 000014
【００５４】
このとき、埋め込み強度εはユーザが自由に選択できるが、例えば、署名情報が１ｂｉｔである時は、２以上の整数から選択する必要がある。そして、埋め込み済み画像の劣化を考え、小さな値とすることが望ましい。また、（ｘ’、ｙ’）は、数論変換には変換領域に物理的意味がないという理由から、以下のランダム関数により決定する。
【００５５】
まず、処理部１は、ランダム化関数ｒｘ’、ｒｙ’を記憶部５から参照して、各ブロックでばらつきのある埋め込み位置（ｘ’、ｙ’）を決定する（Ｓ１０７）。ランダム化関数ｒｘ’、ｒｙ’は、埋め込み位置（ｘ’、ｙ’）を一意に決定できるような関数であり、例えば次式のように設定できる。
【００５６】
【数１５】
2004153493.tif 000015
【００５７】
なお、この例で、ランダム化関数が原画像ブロックｆｉ、ｌ（０、０）を含む関数になっているのは、安全性を高めるためであるが、詳細は「５．（７）」で後述する。なお、ｆｉ、ｌ（０、０）が左隣ブロックの（０、０）要素である。また、埋め込み処理ではこの（０、０）要素には変更がないため、抽出処理でも同じｒｘ’、ｒｙ’を設定しておけば、これらのランダム化関数からは同じ値を得ることができる。なお、左隣に限らず右隣りか所定のブロックの要素を用いても良いし、変更のない適当な要素を用いても良い。
【００５８】
また、処理部１は、埋め込むための署名画像の画素値ｇｉ、ｊを記憶部５の署名画像ファイル５３から読み込む（Ｓ１０９）。なお、ここではステップＳ１０７とステップＳ１０９を並列に処理しているが、ステップＳ１０７を処理した後に、ステップＳ１０９を処理しても良いし、ステップＳ１０９を処理した後に、ステップＳ１０７の処理を行うようにしても良い。
【００５９】
つぎに、処理部１は、求めたＦｉ、ｊ（ｘ’、ｙ’）及びｇｉ、ｊを用いて、上述の式（９）に基づいて、δを計算する（Ｓ１１１）。処理部１は、原画像ブロックの数論変換Ｆｉ、ｊ（ｘ、ｙ）及びステップＳ１１１で求められたδを用いて、式（８）に従い、埋め込み済み画像ブロックの数論変換Ｈｉ、ｊ（ｘ、ｙ）を計算する（Ｓ１１３）。さらに、処理部１は、上述の式（１）、（２）を用いて、Ｈｉ、ｊ（ｘ、ｙ）の逆数論変換である埋め込み画像ブロックｈｉ、ｊ（ｘ、ｙ）を計算する（Ｓ１１５）。
【００６０】
図８に、埋め込みによる画素値への影響についての説明図を示す。
すなわち、Ｈｉ、ｊ（ｘ、ｙ）の逆変換系列をｈｉ、ｊ（ｘ、ｙ）とすると、数論変換の性質により図のように、
【００６１】
【数１６】
2004153493.tif 000016
【００６２】
となる。Ｎが奇数の場合はこの関係は成立しないため、本実施の形態ではＮは２以上の偶数から選択する必要がある。
【００６３】
処理部１は、求めた埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を記憶部５の適宜のエリア（ワークエリア等）に記憶する（Ｓ１１７）。処理部１は、すべての（又は所望の範囲の）ブロックに対して上述の各ステップＳ１０１〜Ｓ１１７処理を行った場合はステップＳ１２１に進み、そうでない場合はステップＳ１０３に戻り処理をやり直す（Ｓ１１９）。処理部１は、以上の処理をすべての（又は所望の範囲の）ブロックについて実行し、埋め込み済み画像［ｈ］を得る。処理部１は、数論変換パラメータＰと埋め込み済み画像［ｈ］を埋め込み済み画像ファイル５４に保存する（Ｓ１２１）。処理部１は、Ｉ／Ｆ６又は出力部３を介して、受信側装置にパラメータＰと埋め込み済み画像［ｈ］を送信する（Ｓ１２３）。処理部１は、必要に応じてパラメータとしてＮを送るようにしても良い。なお、ここではステップＳ１２１とステップＳ１２３を並列して処理しているが、ステップＳ１２１を処理した後に、ステップＳ１２３を処理しても良いし、ステップＳ１２３を処理した後にステップＳ１２１の処理を行うようにしても良い。また、処理部１は、認証機関用装置（認証機関用コンピュータ３０）に、法Ｐを、また、必要に応じて位数Ｎを送信するようにしてもよい。
【００６４】
３．２．２．  抽出処理
図９に、抽出処理のフローチャートを示す。
抽出処理が開始されると、処理部１は、数論変換のパラメータＰと埋め込み済み画像［ｈ］を送信側装置から受信し、埋め込み済み画像ファイル５４に記憶する。また、処理部１は、場合によっては送信側装置から、さらにＮを受信してもよい。また、処理部１は、数論変換のためのパラメータである法Ｐ、必要に応じてＮを、認証機関装置から受信するようにしてもよい。なお、［ｈ］が予め埋め込み済み画像ファイル５４に記憶されている場合、ステップＳ２０１は省略することができる。処理部１は、埋め込み済み画像ファイル５４を参照して、埋め込み済み画像［ｈ］をブロック分割した埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を読み込む（Ｓ２０３）。
【００６５】
つぎに、処理部１は、上述のステップＳ１０１と同様に、数論変換のためのパラメータＰ、Ｎ、αを設定する（Ｓ２０４）。処理部１は、設定されたパラメータを用い、式（１）、（２）に基づいて埋め込み済み画像ブロックｈｉ、ｊ（ｘ、ｙ）を数論変換してＨｉ、ｊ（ｘ、ｙ）を計算する（Ｓ２０５）。また、処理部１は、前述した署名画像の埋め込み済み位置に対応した署名画像抽出位置（ｘ’、ｙ’）を予め記憶部５に記憶されたランダム化関数ｒｘ’、ｒｙ’を用いて決定する（Ｓ２０７）。
【００６６】
つぎに、処理部１は、抽出位置の埋め込み済み画像ブロックの数論変換Ｈｉ、ｊ（ｘ’、ｙ’）より署名画像の画素値ｇｉ、ｊを抽出する（Ｓ２０９）。すなわち、処理部１は、次式のように、Ｈｉ、ｊ（ｘ’、ｙ’）のεによる剰余を取ることによって署名画像の画素値を求める。なお、式（９）を変形すると、式（１４）となり、署名画像の画素値ｇｉ、ｊが抽出できる。
【００６７】
【数１７】
2004153493.tif 000017
【００６８】
処理部１は、署名画像の画素値ｇｉ、ｊを記憶部５の適宜のエリア（ワークエリア等）に記憶する（Ｓ２１１）。処理部１は、すべての（又は所定の範囲の）ブロックに対して処理ステップＳ２０１〜Ｓ２１１を行った場合はステップＳ２１５に進み、そうでない場合はステップＳ２０３に戻り上述の処理を繰り返す（Ｓ２１３）。処理部１は、以上の全ての（又は所定の範囲の）ブロックよりｇｉ、ｊを抽出して、署名画像［ｇ］を得る。処理部１は、署名画像［ｇ］を記憶部５の署名画像ファイル５３に保存し、表示部４に表示又は出力部３やインターフェース６から出力する（Ｓ２１５）。さらに、処理部１は、埋め込み済み画像［ｈ］及び署名画像［ｇ］に基づいて、原画像［ｆ］を求め、適宜記憶及び／又は出力・表示するようにしてもよい。
【００６９】
ここで、ＰとＮが正規の値であり、埋め込み済み画像［ｈ］に改ざんがなければ正規の署名画像が取り出せる。一方、ＰとＮが不正なものであるか、［ｈ］に改ざんがある場合、改ざんされた場合のＨｉ、ｊ（ｘ、ｙ）は数論変換の性質より正規の値と大きく異なる。ゆえに、それから抽出された署名情報は不正な値となる可能性が高い。よって、抽出された署名情報より構成された署名画像により、改ざんの有無とその位置を視認することができる。
【００７０】
４．実験結果
図１０に、実験に使用する画像の図を示す。図（ａ）は、現画像、図（ｂ）は署名画像をそれぞれ示す。図（ａ）のようなＳＩＤＢＡの標準画像であるＴｅｘｔ（２５６×２５６画素、８ｂｉｔ階調）に対して本発明を適用し、有効性について検討した。鍵となる数論変換のパラメータはＰ＝８５、１４７、６９３、Ｎ＝４を用い、署名画像は図（ｂ）（６４×６４画素、１ｂｉｔ階調）を用いた。また、埋め込み強度εは５を用いた。ランダム化関数ｒｘ’、ｒｙ’には最も簡単な例として、次式を用いた。
【００７１】
【数１８】
2004153493.tif 000018
【００７２】
図１１に、実験結果の画像の図（１）を示す。図（ａ）は、埋め込み済み画像、図（ｂ）は抽出された署名画像をそれぞれ示す。図１０（ａ）に対して埋め込み処理を行った結果が図１１（ａ）である。ＳＮＲは５６．７３ｄＢとなり、埋め込みによる劣化はほとんど目立たなかった。
【００７３】
図１２に、出力画像の画質と埋め込み強度εの関係について示す。
この図はεを２から１２まで変化させ埋め込み処理を行った場合の、埋め込み済み画像のＳＮＲとεの関係を示すグラフである。εの増加につれＳＮＲが低下するのは、埋め込み処理におけるのδ値の大きさがεに比例するからである。いずれのεでも高い値を示したことから、劣化が目立たない画像であるといえる。また、図１１（ａ）から抽出した署名画像が図１１（ｂ）であり、図１０（ｂ）と全く同じであった。
【００７４】
図１３に、実験結果の画像の図（２）を示す。図（ａ）は、改ざん例の画像、図（ｂ）は（ａ）から抽出された画像をそれぞれ示す。
この例では、図１１（ａ）に対し、図１３（ａ）のような改ざんを行った。改ざん例は、フォトレタッチソフトを使用して「０」の部分を含む矩形領域をコピーし、「８」の部分に張り付けたものである。図１３（ａ）から抽出した署名画像が図１３（ｂ）である。改ざん箇所と署名画像が破壊されている部分が一致しており、改ざん位置が視認できることがわかった。
【００７５】
５．安全性についての議論
本発明の、埋め込み済み画像に改ざんが行われた場合への安全性について以下のように議論する。ただし攻撃者は埋め込み済み画像［ｈ］とすべてのアルゴリズムが既知であり、鍵情報Ｐ、Ｎ、原画像［ｆ］、署名画像［ｇ］は未知であると仮定する。
（１）アルゴリズムから適切な改ざんを解析
ここでは簡単のため、Ｎ＝２の場合について議論する。ａ、ｂ、ｃ、ｄは正の整数として、
【００７６】
【数１９】
2004153493.tif 000019
【００７７】
とする。埋め込み処理により
【００７８】
【数２０】
2004153493.tif 000020
【００７９】
となる。抽出処理においては数論変換により
【００８０】
【数２１】
2004153493.tif 000021
【００８１】
を得て、式（１４）により、正規の署名情報を得ることができる。
ここで、ｈｉ、ｊ（ｘ、ｙ）に
【００８２】
【数２２】
2004153493.tif 000022
【００８３】
と改ざんが行われた場合を考える。ここで、μ１、μ２、μ３、μ４は整数とする。抽出処理において、ｈｉ、ｊ（ｘ、ｙ）を数論変換すると
【００８４】
【数２３】
2004153493.tif 000023
【００８５】
となる。よってλ１、λ２、λ３、λ４を任意の正の整数とすると、
【００８６】
【数２４】
2004153493.tif 000024
【００８７】
を同時に満たすようなμ１、μ２、μ３、μ４であれば、本発明では改ざんを検出できない。これは、改ざんによってν１、ν２、ν３、ν４のｅによる剰余が０になるからである。このときμ１、μ２、μ３、μ４についての連立方程式はαを含むものとなる。攻撃者はαが未知という仮定ではこの連立方程式は解析的に解くことは困難である。
【００８８】
（２）任意の部分的な改ざん
本発明において、署名情報はＨｉ、ｊ（ｘ’、ｙ’）のεによる剰余により抽出する。これは、任意に改ざんを行ったとしても一つのブロックにつきε−１の確率で正規の署名情報を得られることを意味する。一般に、画像の冗長性から一つのブロックのみを改ざんすることはほとんど意味をなさず、複数のブロックを改ざんする必要が生じる。Ｔ個のブロックを改ざんした場合、その改ざんが成功する確率はε−Ｔである。例えばＮ＝２、ε＝５である場合に、４×４ブロック（＝８×８画素）の改ざんに成功する確率は５−１６となり、この方法による改ざんは高い確率で検出できるといえる。ここで、εが大きいほど改ざんが難しくなるが、画像の劣化も大きくなるため、本発明では安全性と画像の品質はいわゆるトレードオフの関係にある。しかしながら、実験ではε＝１２においてもＳＮＲは４８．２ｄＢであり、εが比較的大きな値でも劣化の目立たない埋め込みが可能である。
【００８９】
（３）ビットプレーンへの改ざん
本発明はビットプレーンに基づいた埋め込み手法ではないため、それに注目した攻撃は意味をなさない。例えば、ＬＳＢのみへの改ざんはｈｉ、ｊ（ｘ、ｙ）に対しては小さな影響しか与えないが、数論変換の性質からＨｉ、ｊ（ｘ、ｙ）には大きな影響を与えるため、得られる署名情報は不正なものになる可能性が高い。
【００９０】
（４）鍵の全数探索
鍵であるＰの全数探索では、Ｐは素数のべき乗による任意の合成数を選択することができるため、探索範囲は計算機上で扱える整数である。一方、Ｐが正しいかどうかについての判定は、抽出された署名画像が意味のあるものかどうかを人間が視認して行うが、これには多大な時間を要すると考えられる。ゆえに、鍵の全数探索は現実的に困難である。
【００９１】
（５）拡大縮小、回転などの幾何学的な変化
本発明では解像度や形状の変化がある場合には、ｒｘ’、ｒｙ’やＮの対応がとれないために画像全体の改ざんとして検出される。
【００９２】
（６）同じ画像内の切り張り
［ｈ］をブロック分割し、それらの位置を交換したり、ブロックをコピーし任意の場所に張り付ける改ざんを考える。実験における改ざんはこれに当たる。この場合、本発明でのｒｘ’、ｒｙ’はｉ、ｊを含む関数であるため、この方法の改ざんでは位置を移動したブロックではｒｘ’、ｒｙ’の対応が正しく取れない。よって、この方法による改ざんは高い確率で検出できる。
【００９３】
（７）埋め込み処理された複数の異なる画像間で切り張り
例えば、異なる複数の埋め込み済み画像をそれぞれブロック分割し、同じ位置にあるブロックを入れ替えることで一つの画像を合成する場合を考える。ただし、これらの画像の解像度はすべて等しく、埋め込み処理におけるＰ、Ｎ、［ｇ］がすべて同じであるとする。この場合、本発明ではｒｘ’、ｒｙ’は左隣ブロックの画素値であるｆｉ、ｌ（０、０）を含む関数で生成しているため、ｒｘ’、ｒｙ’の正しい対応が取れない。よって、この方法による改ざんは高い確率で検出できる。
【００９４】
６．むすび
本発明では、従来の直交変換を用いた耐性型電子透かしの応用として、数論変換による脆弱型電子透かしによる改ざん位置検出について提案した。実験では提案法の有効性について検討し、良好な結果を得た。また、様々な攻撃に対する提案法の安全性についての考察を行った。
【００９５】
本発明の改ざん検出方法又は改ざん検出装置・システムは、その各手順をコンピュータに実行させるための改ざん検出プログラム、改ざん検出プログラムを記録したコンピュータ読み取り可能な記録媒体、改ざん検出プログラムを含みコンピュータの内部メモリにロード可能なプログラム製品、そのプログラムを含むサーバ等のコンピュータ、等により提供されることができる。
【００９６】
さらに、応用範囲として、本発明の改ざん検出方法の機能又は改ざん検出プログラムとその実行機能を、ディジタルカメラやスキャナ等の各種画像入力装置に搭載し、そのような装置から取り込んだ画像に透かし情報を埋め込むようにすることもできる。
【００９７】
【発明の効果】
本発明によると、以上のように、直交変換を用いた耐性型電子透かし法を応用した数論変換による脆弱型の電子透かし法を用いた改ざん検出方法、改ざん検出プログラム及びそのプログラムを記録した記録媒体を提案することができる。また、本発明によると、改ざんの有無及びその位置を目視によって容易に確認することができる改ざん検出法等を提供することができる。
【００９８】
さらに、従来の数論変換を利用した電子透かしの手法では、原画像の画像ビットを下位２ｂｉｔ程度という比較的少ない範囲で置換することにより署名情報を埋め込むものであった。これに対して、本発明では、原画像の画素ビットの全て又は所望の広範囲を利用して署名情報を埋め込むことにより安全性を一層高めることができる。また、従来の数論変換を利用した手法では、署名情報の埋め込みを数論変換ドメインに掛け合わせて（畳み込んで）実現していた。これに対して、本発明では、署名情報の埋め込みを足し算により実現することで、数値誤差を小さくし、演算速度を速くすることができる。
【図面の簡単な説明】
【図１】素数１３のｙｘ（ｍｏｄ  １３）の説明図。
【図２】システム構成の概略図。
【図３】改ざん位置検出装置の構成図。
【図４】離散フーリエ変換による電子透かし法についての説明図。
【図５】数論変換による脆弱型電子透かし法についての説明図。
【図６】埋め込み処理のフローチャート（１）。
【図７】埋め込み処理のフローチャート（２）。
【図８】埋め込みによる画素値への影響についての説明図。
【図９】抽出処理のフローチャート。
【図１０】実験に使用する画像の図。
【図１１】実験結果の画像の図（１）。
【図１２】出力画像の画質と埋め込み強度εの関係。
【図１３】実験結果の画像の図（２）。
【符号の説明】
１０  送信者用コンピュータ
２０  受信者用コンピュータ
３０  認証機関用コンピュータ
１  処理部
２  入力部
３  出力部
４  表示部
５  記憶部
５１  鍵ファイル
５２  原画像ファイル
５３  署名画像ファイル
５４  埋め込み済み画像ファイル
【図１】
2004153493.tif 000027
【図２】
2004153493.tif 000028
【図３】
2004153493.tif 000029
【図４】
2004153493.tif 000030
【図５】
2004153493.tif 000031
【図６】
2004153493.tif 000032
【図７】
2004153493.tif 000033
【図８】
2004153493.tif 000034
【図９】
2004153493.tif 000035
【図１０】
2004153493.tif 000036
【図１１】
2004153493.tif 000037
【図１２】
2004153493.tif 000038
【図１３】
2004153493.tif 000039