(57)【要約】【課題】静的な改変では、プログラムに埋め込まれた電子透かし情報を無効化できないようにする。【解決手段】対象プログラムから定数検出部１２が検出した定数M1に基づき、有限群選択部１４が２つの素数を選択し、それら２つの積nに基づく有限群を選択する。t値算出部１８が、電子透かし情報と、２つの素数から求められるその有限群の位数とに基づきtの値を計算する。u,w計算部が、M1、n及びtの値を用いて、M1についての２つの一方向性関数によりu,wを計算する。２つの一方向性関数は、あらかじめ定めた組み合わせ方で組み合わせると、組み合わせ結果の関数が必ずM1を出力するという条件を満たす。電子透かしコード挿入部２２は、変数t,u,wから変数fを計算する演算式を対象プログラムに挿入し、対象プログラム中の定数M1をfに置換する。この演算式は、有限群の性質により、変数t,u,wの値が正しければ必ず演算結果がM1となる。【選択図】図１
2011120127.tif 000002
【特許請求の範囲】
【請求項１】
電子透かし情報と有限群の位数とを第１の関数に入力することにより変数tの値を計算する第１の計算手段と、
前記電子透かし情報の埋込対象である対象プログラム中から選択された定数Mを第１の一方向性関数に入力することにより変数uの値を計算すると共に、前記定数Mを第２の一方向性関数に入力することにより変数wの値を計算する第２の計算手段であって、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たすことを特徴とする第２の計算手段と、
変数t，u及びwに対し前記第１の計算手段が計算した変数tの値及び前記第２の計算手段が計算した変数u及びwの値を代入するプログラム要素と、前記変数t，u及びwを入力として含む第２の関数の出力を変数fに代入するプログラム要素とを、前記対象プログラム中の、前記定数Mを含むプログラム要素よりも前に挿入すると共に、前記定数Mを含むプログラム要素における定数Mを前記変数fにより置換することにより、前記対象プログラムに対して前記電子透かし情報を埋め込む埋込手段と、
を備え、
前記第２の関数は、入力される前記変数tの値が前記電子透かし情報を前記第１の関数に入力することにより得られる正しい値であり、且つ入力される前記変数u及びwの値が前記定数Mを前記第１の一方向性関数及び前記第２の一方向性関数にそれぞれ入力することにより得られる正しい値である場合に、前記定数Mを出力することを特徴とする電子透かし埋込装置。
【請求項２】
前記第２の関数は、前記変数tと当該変数tとは異なる変数b’とを入力とする第３の関数と、前記組み合わせ関数と、を組み合わせた関数であり、
前記第３の関数は、前記変数tから前記有限群の位数の倍数を計算する演算と、前記変数b’に対して前記有限群を定義する演算を前記倍数が表す回数施す演算と、を表す、
ことを特徴とする請求項１に記載の電子透かし埋込装置。
【請求項３】
前記変数b’として、前記対象プログラムに入力される入力値の変数を用いることを特徴とする請求項２に記載の電子透かし埋込装置。
【請求項４】
対象プログラムに電子透かし情報が埋め込まれた結果である透かし入りプログラムから、既知の有限群の位数に対して第１の関数により規定される関係を持つ整数を検出する検出手段と、
前記検出手段が検出した整数であって、前記透かし入りプログラムの中に含まれるあらかじめ定められた第２の関数と同値の演算式に含まれる整数と、前記第１の関数とに基づき、前記電子透かし情報を計算する透かし情報計算手段と、
を備え、
前記第１の関数は、前記電子透かし情報と前記有限群の位数とを入力すると変数tの値を出力する関数であり、
前記第２の関数は、変数t，u及びwを入力とし、前記変数tの値が前記電子透かし情報と前記有限群の位数とを前記第１の関数に入力することにより計算される正しい値であり、且つ前記変数u及びwの値が前記対象プログラム中から選択された定数Mを第１の一方向性関数及び第２の一方向性関数にそれぞれ入力することにより計算される正しい値である場合に、前記定数Mを出力する関数であり、
前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たす、
ことを特徴とする電子透かし読取装置。
【請求項５】
コンピュータを、
電子透かし情報と有限群の位数とを第１の関数に入力することにより変数tの値を計算する第１の計算手段、
前記電子透かし情報の埋込対象である対象プログラム中から選択された定数Mを第１の一方向性関数に入力することにより変数uの値を計算すると共に、前記定数Mを第２の一方向性関数に入力することにより変数wの値を計算する第２の計算手段であって、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たすことを特徴とする第２の計算手段、
変数t，u及びwに対し前記第１の計算手段が計算した変数tの値及び前記第２の計算手段が計算した変数u及びwの値を代入するプログラム要素と、前記変数t，u及びwを入力として含む第２の関数の出力を変数fに代入するプログラム要素とを、前記対象プログラム中の、前記定数Mを含むプログラム要素よりも前に挿入すると共に、前記定数Mを含むプログラム要素における定数Mを前記変数fにより置換することにより、前記対象プログラムに対して前記電子透かし情報を埋め込む埋込手段、
として機能させるためのプログラムであって、
前記第２の関数は、入力される前記変数tの値が前記電子透かし情報を前記第１の関数に入力することにより得られる正しい値であり、且つ入力される前記変数u及びwの値が前記定数Mを前記第１の一方向性関数及び前記第２の一方向性関数にそれぞれ入力することにより得られる正しい値である場合に、前記定数Mを出力することを特徴とするプログラム。
【請求項６】
コンピュータを、
対象プログラムに電子透かし情報が埋め込まれた結果である透かし入りプログラムから、既知の有限群の位数に対して第１の関数により規定される関係を持つ整数を検出する検出手段、
前記検出手段が検出した整数であって、前記透かし入りプログラムの中に含まれるあらかじめ定められた第２の関数と同値の演算式に含まれる整数と、前記第１の関数とに基づき、前記電子透かし情報を計算する透かし情報計算手段、
として機能させるためのプログラムであって、
前記第１の関数は、前記電子透かし情報と前記有限群の位数とを入力すると変数tの値を出力する関数であり、
前記第２の関数は、変数t，u及びwを入力とし、前記変数tの値が前記電子透かし情報と前記有限群の位数とを前記第１の関数に入力することにより計算される正しい値であり、且つ前記変数u及びwの値が前記対象プログラム中から選択された定数Mを第１の一方向性関数及び第２の一方向性関数にそれぞれ入力することにより計算される正しい値である場合に、前記定数Mを出力する関数であり、
前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たす、
ことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子透かし埋込装置、電子透かし読取装置、及びプログラムに関する。
【背景技術】
【０００２】
コンピュータプログラムの不正利用抑止を目的に、プログラムに対する電子透かしの埋め込み技術が提案されている（例えば特許文献１参照）。プログラムに対する電子透かし埋め込み技術は、例えば、利用料による収入が見込めるような価値の高いプログラムに、使用許諾を受けたユーザの識別情報など、不正利用防止のための情報を埋め込む際などに利用される。プログラムが不正に利用された場合には、その透かし情報から流出経路を特定することが可能となり、プログラムの不正利用の抑止と拡大防止が可能となる。
【０００３】
代表的な電子透かし埋め込み技術として、非特許文献１に示されたコード・ウォーターマーク（Code watermark）法が一般に知られている。コード・ウォーターマーク法は、プログラム中に存在する互いに依存関係を持たない基本コードブロックを複数個選定し、これらのフローグラフ上における並び順を変化させることで埋め込みたい透かし情報を表現する技術である。選定された複数の基本コードブロックは互いに独立したコード群であるため、並び替えによってもプログラムの挙動が変化することはない。プログラムの実行速度の低下、コードサイズの増加などの問題が発生しないなど、多くの長所を持つ有力な電子透かし埋め込み技術として知られている。
【０００４】
コード・ウォーターマーク法には、透かしが埋め込まれたプログラムに簡単な改変を加えるだけで透かしを無効化出来るという脆弱性があることが知られている。例えば、プログラムの実行に影響を与えないようなダミー文をランダムに複数個挿入するなど、一般的なコード難読化手法を用いることで、基本コードブロックが改変される。これにより、透かしの判別が困難になり、埋め込まれた情報の無効化が可能となってしまう。この方法は、ダミー文の埋め込みや難読化はコードに対する静的な作業であり、プログラムの実行を要する動的な攻撃法に比較するとコストが小さくて済む。その上、これらの作業は人手を介さないで、計算機によって自動的に実施することも可能である。類似の脆弱性は、コード・ウォーターマーク法以外の多くのプログラム電子透かし技術にも存在することが知られている。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００１−２６５５８７号公報
【非特許文献】
【０００６】
【非特許文献１】C. Collberg and C. Thomborson, ``Software Watermarking: Models and Dynamic Embeddings,'' Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pp.311 - 324 , 1999.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
本発明は、プログラムの静的な改変では、そのプログラムに埋め込まれた電子透かし情報を無効化できない、電子透かし埋込技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
請求項１に係る発明は、電子透かし情報と有限群の位数とを第１の関数に入力することにより変数tの値を計算する第１の計算手段と、前記電子透かし情報の埋込対象である対象プログラム中から選択された定数Mを第１の一方向性関数に入力することにより変数uの値を計算すると共に、前記定数Mを第２の一方向性関数に入力することにより変数wの値を計算する第２の計算手段であって、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たすことを特徴とする第２の計算手段と、変数t，u及びwに対し前記第１の計算手段が計算した変数tの値及び前記第２の計算手段が計算した変数u及びwの値を代入するプログラム要素と、前記変数t，u及びwを入力として含む第２の関数の出力を変数fに代入するプログラム要素とを、前記対象プログラム中の、前記定数Mを含むプログラム要素よりも前に挿入すると共に、前記定数Mを含むプログラム要素における定数Mを前記変数fにより置換することにより、前記対象プログラムに対して前記電子透かし情報を埋め込む埋込手段と、を備え、前記第２の関数は、入力される前記変数tの値が前記電子透かし情報を前記第１の関数に入力することにより得られる正しい値であり、且つ入力される前記変数u及びwの値が前記定数Mを前記第１の一方向性関数及び前記第２の一方向性関数にそれぞれ入力することにより得られる正しい値である場合に、前記定数Mを出力することを特徴とする電子透かし埋込装置である。
【０００９】
請求項２に係る発明は、前記第２の関数は、前記変数tと当該変数tとは異なる変数b’とを入力とする第３の関数と、前記組み合わせ関数と、を組み合わせた関数であり、前記第３の関数は、前記変数tから前記有限群の位数の倍数を計算する演算と、前記変数b’に対して前記有限群を定義する演算を前記倍数が表す回数施す演算と、を表す、ことを特徴とする請求項１に記載の電子透かし埋込装置である。
【００１０】
請求項３に係る発明は、前記変数b’として、前記対象プログラムに入力される入力値の変数を用いることを特徴とする請求項２に記載の電子透かし埋込装置である。
【００１１】
請求項４に係る発明は、対象プログラムに電子透かし情報が埋め込まれた結果である透かし入りプログラムから、既知の有限群の位数に対して第１の関数により規定される関係を持つ整数を検出する検出手段と、前記検出手段が検出した整数であって、前記透かし入りプログラムの中に含まれるあらかじめ定められた第２の関数と同値の演算式に含まれる整数と、前記第１の関数とに基づき、前記電子透かし情報を計算する透かし情報計算手段と、を備え、前記第１の関数は、前記電子透かし情報と前記有限群の位数とを入力すると変数tの値を出力する関数であり、前記第２の関数は、変数t，u及びwを入力とし、前記変数tの値が前記電子透かし情報と前記有限群の位数とを前記第１の関数に入力することにより計算される正しい値であり、且つ前記変数u及びwの値が前記対象プログラム中から選択された定数Mを第１の一方向性関数及び第２の一方向性関数にそれぞれ入力することにより計算される正しい値である場合に、前記定数Mを出力する関数であり、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たす、ことを特徴とする電子透かし読取装置である。
【００１２】
請求項５に係る発明は、コンピュータを、電子透かし情報と有限群の位数とを第１の関数に入力することにより変数tの値を計算する第１の計算手段、前記電子透かし情報の埋込対象である対象プログラム中から選択された定数Mを第１の一方向性関数に入力することにより変数uの値を計算すると共に、前記定数Mを第２の一方向性関数に入力することにより変数wの値を計算する第２の計算手段であって、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たすことを特徴とする第２の計算手段、変数t，u及びwに対し前記第１の計算手段が計算した変数tの値及び前記第２の計算手段が計算した変数u及びwの値を代入するプログラム要素と、前記変数t，u及びwを入力として含む第２の関数の出力を変数fに代入するプログラム要素とを、前記対象プログラム中の、前記定数Mを含むプログラム要素よりも前に挿入すると共に、前記定数Mを含むプログラム要素における定数Mを前記変数fにより置換することにより、前記対象プログラムに対して前記電子透かし情報を埋め込む埋込手段、として機能させるためのプログラムであって、前記第２の関数は、入力される前記変数tの値が前記電子透かし情報を前記第１の関数に入力することにより得られる正しい値であり、且つ入力される前記変数u及びwの値が前記定数Mを前記第１の一方向性関数及び前記第２の一方向性関数にそれぞれ入力することにより得られる正しい値である場合に、前記定数Mを出力することを特徴とするプログラムである。
【００１３】
請求項６に係る発明は、コンピュータを、対象プログラムに電子透かし情報が埋め込まれた結果である透かし入りプログラムから、既知の有限群の位数に対して第１の関数により規定される関係を持つ整数を検出する検出手段、前記検出手段が検出した整数であって、前記透かし入りプログラムの中に含まれるあらかじめ定められた第２の関数と同値の演算式に含まれる整数と、前記第１の関数とに基づき、前記電子透かし情報を計算する透かし情報計算手段、として機能させるためのプログラムであって、前記第１の関数は、前記電子透かし情報と前記有限群の位数とを入力すると変数tの値を出力する関数であり、前記第２の関数は、変数t，u及びwを入力とし、前記変数tの値が前記電子透かし情報と前記有限群の位数とを前記第１の関数に入力することにより計算される正しい値であり、且つ前記変数u及びwの値が前記対象プログラム中から選択された定数Mを第１の一方向性関数及び第２の一方向性関数にそれぞれ入力することにより計算される正しい値である場合に、前記定数Mを出力する関数であり、前記第１の一方向性関数と前記第２の一方向性関数とは、当該第１の一方向性関数と当該第２の一方向性関数とをあらかじめ定めた関係で組み合わせた組み合わせ関数の出力値が前記第１の一方向性関数及び前記第２の一方向性関数に対する入力に等しくなるという条件を満たす、ことを特徴とするプログラムである。
【発明の効果】
【００１４】
請求項１、２又は５に係る発明によれば、プログラムの静的な改変では、そのプログラムに埋め込まれた電子透かし情報を無効化できないようにすることができる。
【００１５】
請求項３に係る発明によれば、変数b’として対象プログラムに入力される入力値の変数を用いない場合よりも、電子透かし情報が埋め込まれたプログラムの解析困難性を高めることができる。
【００１６】
請求項４又は６に係る発明によれば、請求項１又は５に係る発明によりプログラムに埋め込まれた電子透かし情報を読み取ることができる。
【図面の簡単な説明】
【００１７】
【図１】電子透かし埋込装置の一例を示す機能ブロック図である。
【図２】対象プログラムのコードの例を示す図である。
【図３】実施形態の装置により電子透かし情報が埋め込まれたプログラムのコードの例を示す図である。
【図４】電子透かし読取装置の一例を示す機能ブロック図である。
【発明を実施するための形態】
【００１８】
まず、図１を参照して、実施形態の電子透かし埋込装置の一例を説明する。この電子透かし埋込装置は、対象プログラム入力部１０、定数検出部１２、有限群選択部１４、電子透かし情報入力部１６、t値計算部１８、u,w値計算部２０、及び電子透かしコード挿入部２２を備える。
【００１９】
対象プログラム入力部１０は、電子透かし情報が埋め込まれる対象である対象プログラムの入力を受け付ける。
【００２０】
定数検出部１２は、入力された対象プログラムのコード中から定数をあらかじめ定められた数だけ選択する。例えば、対象プログラムが、図２に例示するコードにより表されるものであるとする。このプログラムには、
c = 83567*a＋23286*b
という演算式が含まれ、その中に２つの整数定数「８３５６７」と「２３２８６」とが含まれている。対象プログラムから定数を１つ選択する場合、定数検出部１２は、例えば、あらかじめ定められた選択規則に従ってそれら２つの定数のうちの一方を選択する。選択規則としては、例えば、対象プログラム中でｋ番目（ｋはあらかじめ指定した自然数）に現れる定数を選択するという規則や、最も桁数の大きい定数を選択するという規則などがあるが、もちろんこれらに限定されるものではない。また、定数検出部１２が検出した定数を例えば画面に列挙して表示し、透かし埋込を管理する管理者にその中から使用するものを選択させてもよい。
【００２１】
以下では、繁雑さを避けるため、上述の演算式を次の式(1)のように表現する。
【００２２】
c=M1*a+M2*b  ...(1)
この演算式において、a,b,cは変数であり、このうちa,bはこの対象プログラムを呼び出す他のプログラムから引数として渡される。また、M1,M2は整数定数である。この例で、定数検出部１２が、定数M1を選んだとする。この場合、この電子透かし埋込装置は以下のような処理手順を実行する。
【００２３】
<A0> まず、有限群選択部１４が、M1^(1/2)<p1<p2を満たす二つの大きな素数p1,p2をランダムに選択する。ここで、演算子”^”は、べき乗を表す。指定された数より大きい素数を求めるには周知のアルゴリズムを用いればよく、これにより求めた素数から２つをp1,p2として選択すればよい。
【００２４】
<A1> 次に、有限群選択部１４が、整数n=p1p2を算出する。この処理により、整数nを法とする剰余環Z/nZ（Zは整数全体）を規定することができ、この剰余環上の乗法群又は加法群は有限群となる。この例では、有限群選択部１４が、この剰余環Z/nZ上の乗法群を選択するものとする。
【００２５】
<A2> 次に、有限群選択部１４が、gcd(n,d)=1となる正の整数dを選択する。ここでgcd(x,y)は整数xとyの最大公約数である。したがって、上述の整数dは、整数nと互いに素な整数である。指定された整数と互いに素な整数を求めるアルゴリズムは公知であり、有限群選択部１４は、そのアルゴリズムを用いて整数dを求めればよい。
【００２６】
<A3> 次に、t値計算部１８が、次式
t=NID(p1-1)(p2-1)+1
で定義される変数tの値を計算する。ここで、正の整数NIDは、電子透かし情報入力部１６から入力される電子透かし情報である。例えば、電子透かし情報として、対象プログラムの提供先である顧客の識別番号を用いる場合、整数NIDはその顧客識別番号である。なお、対象プログラムに埋め込む電子透かし情報は、顧客識別番号に限られるものではない。正の整数以外のデータ型の情報を電子透かし情報とする場合は、例えばその電子透かし情報を正の整数へと型変換した上で、NIDに代入すればよい。p1,p2の値は有限群選択部１４から与えられるので、t値計算部１８はそれらとNIDを用いてtの値を計算する。以上の説明から明らかなように、このtに電子透かし情報が埋め込まれることになる。tの値が分かっても、p1,p2の値が分からなければ、NIDを求めることはできない。なお、(p1-1)(p2-1)は、剰余環Z/nZ上の乗法群の位数である。
【００２７】
<A4> 次に、u,w値計算部２０が、以下の式により変数s,u,wの値を計算する。
【００２８】
v=t%d, s=(t-v)/d, u= M1^d mod n, w= M1^v mod n
【００２９】
ここで、”%”は剰余を求める演算子である。また、u及びwを求める演算は、整数定数のべき乗を法数nで除した剰余を求める演算であり、この演算は一方向性関数の性質を持つ。すなわち、例えばM1とdとnの値が分かればuを計算するのは簡単であるが、uとdとnの値からM1の値を計算することや、uとM1とnの値からdの値を計算することは、計算量の観点から非常に困難である。
【００３０】
<A5> 次に、電子透かしコード挿入部２２が、対象プログラム中の(1)式（すなわち定数検出部１２が選択した定数を含んでいる式）よりも前の部分に、
(a) 変数n,s,t,u,wに対して有限群選択部１４、t値計算部１８及びu,w値計算部２０により計算された値をそれぞれ代入する文、
(b) 内部変数b'に引数bの値を代入する文（すなわちb'=b）
(c) gcd(b',n)>1またはb'=0の場合にはb'を1に変更する文、および
(d) 次の演算式
f=(b'^(t-1))(u^s)w mod n  ...(2)
を挿入する。変数n,s,t,u,wの値が、有限群選択部１４、t値計算部１８及びu,w値計算部２０で計算された正しい値のままであれば、この式で計算される変数fの値は、定数M1に等しくなる（詳細は後述）。
【００３１】
<A6> そして、電子透かしコード挿入部２２は、対象プログラム中の(1)式を、
c=f*a+M2*b  ...(3)
に変更する。すなわち、定数M1を変数fに置き換える。対象プログラム中に同じ定数M1が複数現れる場合、それらすべての定数M1をfに置き換えてもよいし、それら定数M1のうちの一部のみをfに置き換えるようにしてもよい。
【００３２】
以上の処理手順により、電子透かし情報NIDが埋め込まれた電子透かし入りプログラムが生成される。
【００３３】
図３に、図２に例示した対象プログラムに対して電子透かしの埋め込みを行うことで作成されるJava(登録商標)プログラムの例を示す。図３の例では、NID=11557, p1=54581, p2=65629, d=17の設定値を用いて上記手順によって生成された電子透かしコード(a)〜(d)が埋め込まれている。図３中のコード３２の数値部分はtの値であり、この値に電子透かし情報NID=11557が内包されている。
【００３４】
また、コード群３４は、関数FuncAへの入力bの値が0の場合、あるいはgcd(b,n)>1の場合に、入力bに相当する多倍長数bB（上述の手順におけるb'に該当）を1に変更するためのものである。これは上記ステップA5に含まれている処理（(b)及び(c)に該当）であり、入力である整数bが有限群に含まれない場合に、透かし入りプログラムの挙動が元のプログラムの挙動と異なるものになることを防止するためのコードである。すなわち、gcd(b,n)>1の場合、入力である整数bは剰余環Z/nZ上の乗法群（有限群）に含まれないので、以下に説明する有限群の性質を用いることができなくなる。また、b=0の場合も同様である。そこで、そのような場合、コード群３４により、内部変数bBの値を１に変更するのである。
【００３５】
なお、p1,p2として十分に大きい素数を選んでおけば、gcd(b,n)>1となることはほとんど起こらない。したがって、実用的には、gcd(b,n)>1の場合にbBを１に置き換えるという文はなくしてもよい。
【００３６】
また、コード３６は、上記ステップA5中の式(2)を実現するためのもので、元のプログラム内で使用されていた乗数M1を算出するための演算式である。
【００３７】
次に、上記の手順A0〜A6により生成される電子透かし入りプログラムの動作結果が、元の対象プログラムの動作結果に等しいものであることを、図３の例を用いて説明する。上記手順A5中の式(2)では、法数をnとしている（すなわちmod n)ため、式(2)における計算ではZ/nZ上の乗法群における演算が実施される。この乗法群の位数は(p1-1)(p2-1)であるため、式(2)中のb'^(t-1) mod nの値はこの乗法群の単位元である1の値となる。すなわち、ここでは、有限群（この例ではZ/nZ上の乗法群）の元（上述のコード(c)によりb'はその乗法群の元となっている）に対してその有限群を規定する演算（この例では法nでの乗算）を、その有限群の位数の倍数回（t-1 = NID(p1-1)(p2-1)）だけ施した結果は、その有限群の単位元に等しくなるという定理を用いている。
【００３８】
また、同様に有限群上の任意の元に有限群の位数の倍数回演算を施した結果が単位元になることから、式(2)の後半部は、
(u^s)w = ((M1^d)^s)( M1^v) = M1^t = M1^(NID(p1-1)(p2-1)+1) = M1 mod n
となる。ここで、ステップA0におけるp1,p2の選び方から0 < M1< nであるため、M1 mod n = M1である。このように、uとwは、それら両者を(u^s)wという関数として組み合わせると、その関数はその定義から、u及びwを求める一方向性関数u= M1^d mod n及び w= M1^v mod nに対する入力M1と同じ値M1を出力するものとなる。
【００３９】
以上のことから、式(2)で計算されるfの値はM1に等しくなる。これにより、上記ステップA6における式(3)は式(1)と同値なものであることがわかる。
【００４０】
このように、この実施形態の装置により生成される電子透かし入りプログラムは、変数n,s,t,u,wの値が改ざんされなければ、元の対象プログラムと等価な処理を行うものとなる。
【００４１】
この電子透かし入りプログラムには、電子透かし情報NIDの値は明示的には含まれていない。電子透かし情報NIDはtの値の中に内包されており、tの値は電子透かし入りプログラムの中に記述されているが、tの値が分かったとしても、素数p1,p2が分からなければ、NIDの値を求めることは計算量の観点から非常に困難である。なお、電子透かし入りプログラム中には素数p1とp2の積nの値が記述されているが、nの値が分かったとしても、その素因数分解p1,p2を求めることは計算量の観点から非常に困難である。
【００４２】
また、電子透かし入りプログラムには、定数M1の値は明示的には含まれていない。定数M1の値は、u,wの値の中に内包されている（上述のステップA4参照）。それらu,wの値は電子透かし入りプログラムの中に記述されているが、一方向性関数u= M1^d mod n, w= M1^v mod nの性質から、u,w,n,v,dの値が分かったとしても、M1を求めることは計算量的に非常に困難である。更に言えば、v,dの値は電子透かし入りプログラムの中に現れないので、M1の値を求めることはより困難である。
【００４３】
次に、図４を用いて、電子透かし入りプログラムから、その中に埋め込まれている電子透かし情報を読み取る電子透かし読取装置の構成及び処理を説明する。
【００４４】
この電子透かし読取装置は、図４に示すように、電子透かし入りプログラム入力部４０、逆コンパイル部４２、有限群情報保持部４４、位数計算部４６、倍数抽出部４８、電子透かし情報演算部５０を備える。
【００４５】
この装置では、まず電子透かし入りプログラム入力部４０に、電子透かし入りプログラムが入力される。例えば、不正に流出した電子透かし入りプログラムが見つかった場合に、プログラム配布者などが、そのプログラムを当該装置の電子透かし入りプログラム入力部４０に入力する。配布されている電子透かし入りプログラムは一般に実行形式である場合が多いので、逆コンパイル部４２が、その実行形式の電子透かし入りプログラムを逆コンパイルして、そのプログラムのソースコードを作成する。
【００４６】
一方、有限群情報保持部４４は、電子透かし入りプログラムの作成に利用された有限群を特定する有限群情報として、素数p1およびp2の値を秘密情報として保持しているものとする。位数計算部４６は、その素数p1およびp2の値から、その有限群の位数(p1-1)(p2-1)を計算する。次に倍数抽出部４８が、そのソースコード内の多倍長整数のうち、1を減じた値が上記位数(p1-1)(p2-1)で割り切れるものを全て抽出する。そして、倍数抽出部４８は、抽出した倍数の中から、ソースコード上での当該倍数の近傍に式(2)と同値の演算式が存在するもの、すなわち抽出した倍数のうち式(2)と同値の演算式に含まれるもの、を選択する。ここで、選択された多倍長整数をn1とする。電子透かし情報演算部５０は、そのn1に対して、(n1-1)/((p1-1)(p2-1))を計算し、この結果を電子透かし情報とする。この計算は、上述の電子透かし埋込手順のステップA3におけるtの定義式をNIDについて解き、それにt = n1を代入したものである。n1がステップA3で求められた値と同値の整数である場合は、その計算の結果はNIDに一致する。すなわち、この場合、電子透かし情報は正しく計算される。例えば電子透かし情報NIDとして顧客の識別情報を用いている場合、上述のようにしてプログラムから電子透かし情報を読み取ることで、そのプログラムがどの顧客に配布されたものかがわかり、そのプログラムが流出したものである場合は流出経路解明の糸口となる。
【００４７】
以上に説明した電子透かし埋込装置で生成された電子透かし入りプログラムに対して、透かしの削除あるいは偽造といった不正行為は非常に困難である。例えば埋め込まれている電子透かし情報を偽造した場合、すなわち何らかの方法で変数tの値が電子透かし情報と関連していることを突き止め、そのtの値を改変した場合、 (t-1) の値（すなわち図３のコード３６のt1）は、有限群の位数(p1-1)(p2-1)の倍数ではなくなる。このため、b'^(t-1)の値は、Z/nZ上の乗法群の単位元１にはならなくなり、その結果上述の式(2)のfの値が、元の対象プログラム内で使用されていた定数M1と異なった値となってしまう。この結果、電子透かし入りプログラムの挙動が元の対象プログラムのものと一致しなくなる。このように、電子透かし入りプログラム中の電子透かし情報を内包する値ｔを仮に突き止めることができ、それを改変することができたとしても、そのような改変を行えば元の対象プログラムと同じ挙動が得られないので、対象プログラムが守られることとなる。
【００４８】
元のプログラムと同一の挙動を実現する偽造透かしを生成する方法として、有限群上で上記のtと同等の効果を発揮する整数を利用することが考えられる。この整数の算出には秘密情報であるp1およびp2の値が必要となるが、配布された電子透かし入りプログラムには秘密情報p1およびp2の値が含まれていない。一方で、電子透かし入りプログラム内の情報から秘密情報p1およびp2の値を算出するのは計算量的にほぼ不可能である。すなわち、電子透かし入りプログラムにはp1とp2の積の値に一致するnが含まれているが、p1とp2の値が十分に大きい場合にはnの素因数分解に必要となる計算量は莫大なものとなり、事実上nから秘密情報p1およびp2の値を得るのは不可能である。
【００４９】
また、偽造ではなく透かしの削除を行う方法としては、上記ステップA5で挿入したコード群を透かし入りプログラムから削除し、上記fの値に元のプログラム内で使用されていた数M1の値を代入する方法が考えられる。しかし、数M1の値は電子透かし入りプログラムには含まれていないため、本手法に対して静的な解析法ではこの値を得ることは出来ない。M1の値を知るには、電子透かし入りプログラムの構造を人間が解析してM1の値を算出している部分を特定し、更にこの部分を動的に実行した上でM1の具体的な値を算出しなければならない。このようにプログラムを動作させながらの動的な作業が必要になるため、従来の静的な解析方法に比べて透かしの除去に多大なコストが必要になる。
【００５０】
更に、この実施形態の電子透かし埋込手法では、ステップA5の(b)〜(d)に示すように（特に式(2)）、fの値が、当該プログラムに対する外部からの入力（引数）bに依存するように見える。このため、この実施形態の装置が埋め込む電子透かしコードの構成は定数M1の値を算出しようとする攻撃者の理解を妨げるものとなっている。しかし、実際には、前述のように有限群の性質により、b'^(t-1)の値はその有限群の単位元となるため、fの値は入力b には依存せず、定数M1となるようになっている。
【００５１】
以上に説明した実施形態の手法は整数の性質を用いるものであり、対象プログラムから選択する定数は整数であった。しかし、実施形態の手法は、対象プログラムから選択する定数が整数でない場合、例えば定数が文字、文字列、日付、固定小数点数、浮動小数点数などである場合、にも適用可能である。選択した定数が整数でない場合、定数を整数に変換し、実施形態の手法を適用すればよい。
【００５２】
また、以上の例において用いたt,u,w,fの定義式は、あくまで一例に過ぎない。例えば、式(2)では、fの計算において、(b'^(t-1))と(u^s)wとを乗算しているが、乗算の代わりに別の演算を行ってもよい。そのような別の演算は、fの値が必ずM1となるような演算であれば、どのようなものでもよい。また、上述の例では、uとwはそれら両者を(u^s)wという関数として組み合わせると、その関数がu及びwを求める一方向性関数u= M1^d mod n及び w= M1^v mod nに対する入力M1と同じ値M1を出力するものであった。しかし、uとwの組み合わせ方は、これに限るものではない。uとwを組み合わせた関数が、有限群の性質からかならずM1を出力するようなものであれば、どのような組み合わせ方でもよい。また、tの定義式も、電子透かし情報と有限群の位数との積を含み、tと位数の値が与えられれば電子透かし情報を計算できるようなものであれば、どのようなものでもよい。
【００５３】
また、以上の例では、対象プログラムへの入力（引数）bをfの計算式に含めたが、これは必須のことではない。bの代わりに、例えば有限群の元を用いてもよい。ただし、入力bを用いることで、上述のように解析困難性が増す。
【００５４】
また、以上の例では、有限群として環Z/nZ上の乗法群を使用したが、加法群を用いても同様の処理を行い同様の効果を得ることが出来る。例えば、Z/nZ上の加法群の単位元（つまり０）を用いることで同様の効果を得ることが可能である。また、更に、有限体上に構成される楕円曲線上の加法群も同様に用いることができる。
【００５５】
また、以上の例では、対象プログラム中の１つの定数に対して電子透かし情報を埋め込んだが、これは一例に過ぎない。この代わりに、例えば、対象プログラム中の異なる複数の定数に対して、同じ電子透かし情報を埋め込んでもよい。複数箇所に電子透かしが埋め込まれることで、削除、偽造等が困難になる。また、この場合、電子透かしを埋め込む定数ごとに、秘密の素数p1およびp2として異なる値の組を採用するようにしてもよい。このようにすれば、電子透かし情報NIDが同じ値であっても、式(2)で計算されるtの値は、埋込対象の定数ごとに異なってくる。また、対象プログラム中の異なる複数の定数に対して、上述の手法で、それぞれ異なる電子透かし情報を埋め込んでもよい。
【００５６】
以上に例示した電子透かし埋込装置及び電子透かし読取装置は、例えば、汎用のコンピュータに上述の各機能モジュールの処理を表すプログラムを実行させることにより実現される。ここで、コンピュータは、例えば、ハードウエアとして、ＣＰＵ等のマイクロプロセッサ、ランダムアクセスメモリ（ＲＡＭ）およびリードオンリメモリ（ＲＯＭ）等のメモリ（一次記憶）、ＨＤＤ（ハードディスクドライブ）を制御するＨＤＤコントローラ、各種Ｉ／Ｏ（入出力）インタフェース、ローカルエリアネットワークなどのネットワークとの接続のための制御を行うネットワークインタフェース等が、たとえばバスを介して接続された回路構成を有する。また、そのバスに対し、例えばＩ／Ｏインタフェース経由で、ＣＤやＤＶＤなどの可搬型ディスク記録媒体に対する読み取り及び／又は書き込みのためのディスクドライブ、フラッシュメモリなどの各種規格の可搬型の不揮発性記録媒体に対する読み取り及び／又は書き込みのためのメモリリーダライタ、などが接続されてもよい。上に例示した各機能モジュールの処理内容が記述されたプログラムがＣＤやＤＶＤ等の記録媒体を経由して、又はネットワーク等の通信手段経由で、ハードディスクドライブ等の固定記憶装置に保存され、コンピュータにインストールされる。固定記憶装置に記憶されたプログラムがＲＡＭに読み出されＣＰＵ等のマイクロプロセッサにより実行されることにより、上に例示した機能モジュール群が実現される。なお、それら機能モジュール群のうちの一部又は全部を、専用ＬＳＩ(Large Scale Integration)、ＡＳＩＣ（Application Specific Integrated Circuit、特定用途向け集積回路）又はＦＰＧＡ（Field Programmable Gate Array）等のハードウエア回路として構成してもよい。
【符号の説明】
【００５７】
１０  対象プログラム入力部、１２  定数検出部、１４  有限群選択部、１６  電子透かし情報入力部、１８  t値計算部、２０  u,w値計算部、２２  電子透かしコード挿入部。
【図１】
2011120127.tif 000003
【図２】
2011120127.tif 000004
【図３】
2011120127.tif 000005
【図４】
2011120127.tif 000006