符号化方法およびそのプログラム
【課題】 元のプログラムで用いられている変数の個数、ならびに当該変数間の参照・代入関係を秘匿し、かつ、秘密鍵の候補数を多くして耐性の高いプログラムの難読化を実現する。
【解決手段】 プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数に符号化するステップとを有する。
【解決手段】 プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数に符号化するステップとを有する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、プログラム中の変数を線形変換して符号化を施す、符号化方法およびそのプログラムに関する。
【背景技術】
【０００２】
ソフトウェアには、価値のあるアルゴリズムおよびコンテンツの暗号鍵など、利用者に対して秘密にすべき情報が含まれる場合がある。一方では、ソフトウェアを解析するための技術（ＲＥ：Reverse Engineering）が数多く開発されている。このため、これらの技術によりソフトウェアが解析されると、不正者が秘密情報を入手するという脅威が考えられる。この脅威に対し、ソフトウェアの仕様を保ったまま、ソフトウェアの解析を困難にする難読化という技術がある。
【０００３】
変数の符号化によるソフトウェアの難読化として、ソースコード中の変数を線形変換により符号化する方法が提案されている（例えば、非特許文献１参照）。この方法では、単一の変数ｘを線形変換により、変数Ｘ（＝ａｘ＋ｂ）に符号化することで、ソフトウェアの解析を難しくすることを意図するものである。ここでは、線形変換の際に用いる整数ａ，ｂが秘密鍵となる。この方法では、ソースコード中の変数の値や演算を隠蔽することを目的としている。
【非特許文献１】佐藤他、信学技報、Ｖｏｌ．ＩＴ‐２００２−４９，ｐｐ．１３−１８，Ｍａｒ．２００２“データの符号化と演算子の変換によるプログラムの難読化手法”
【発明の開示】
【発明が解決しようとする課題】
【０００４】
前記した非特許文献１に開示された技術によれば、ソースコード中の変数の値や演算を秘匿することはできても、難読化前のソースコードで用いられている変数の個数、ならびに変数間における参照・代入の関係を秘匿することは不可能であった。また、秘密鍵の候補数は少なく、秘密鍵の全数探索による攻撃についても脆弱であると考えられる。
【０００５】
本発明は上記事情に鑑みてなされたものであり、元のプログラムで用いられている変数の個数、ならびに当該変数間の参照・代入関係を秘匿し、かつ、秘密鍵の候補数を多くして耐性の高いプログラムの難読化を実現する、符号化方法およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記した課題を解決するために本発明は、プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化するステップと、を有することを特徴とする。
【０００７】
また、本発明は、プログラム中の変数を線形変換して符号化を施す符号化装置に用いられるプログラムであって、前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択する処理と、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成する処理と、前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化する処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、プログラム中のｎ個の変数を線形変換により同時にｍ個の整数に符号化するため、プログラム中で用いられている変数の個数を秘匿すると同時に、変数間の参照および代入関係も秘匿することができる。また、変換鍵として行列およびベクトルを用いるため鍵の候補数を多くすることができる。このことにより、耐性の高いソフトウェアの難読化を実現することができる。
【発明を実施するための最良の形態】
【０００９】
図１は、本発明実施形態に係わるの符号化方法の概略手順を示すフローチャートである。
本発明の符号化方法は、符号化を施すn個（但し、ｎは正の整数）の変数を任意に選択し、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成して変換鍵とし、ｎ個の変数を線形変換して同時にｍ個の整数に符号化することを特徴とするものであり、これを実現するために、図１に示されるように、符号化を施すｎ個の変数を選択する難読化対象選択処理（Ｓ１１）からはじまり、秘密鍵の生成（Ｓ１２）、変化式の定義（Ｓ１３）、復号式の導出（Ｓ１４）、変数の置換（Ｓ１５）、後処理（Ｓ１６）、判定（Ｓ１７）の各ステップを順次実行する。以下にステップ毎の詳細手順の説明を行う。
【００１０】
（Ｓ１１：難読化対象の選択処理）
まず、プログラムの中から、難読化の対象として符号化を施すｎ個（ｎは整数数）の変数を任意に選択する。この操作で選ばれたｎ個の変数ｘ１，ｘ２…，ｘｎ，とする。
（Ｓ１２：秘密鍵の生成処理）
ここでは、ｍ×ｎ型行列Ａ、ｍ次元ベクトルｃを任意に生成し、これらを秘密鍵とする。但し、ｍは、ｍ≧ｎなる正整数である。
【００１１】
（Ｓ１３：変換式の定義処理）
次に、生成した行列Ａおよびベクトルｃを用いて以下の変換式（１）を定義する。
【００１２】
【数１】
【００１３】
ここで、Ｘ１，Ｘ２，…，Ｘｍは、難読化後のソフトウェアで用いられる符号化されたｍ個の変数である。
【００１４】
（Ｓ１４：復号式の導出処理）
上記した変換式をｎ個の変数ｘ１，ｘ２，…，ｘｎに関するｍ本の連立方程式と見なし、それぞれの変数について解く。その結果、それぞれの変数ｘ１，ｘ２，…，ｘｎに関して以下の（２）で示す復号式が成立する。
【００１５】
【数２】
【００１６】
この復号式により、元のプログラム中のそれぞれの変数ｘ１，ｘ２，…，ｘｎの値が、復号化された変数Ｘ１，Ｘ２，…Ｘｍを用いて表すことが可能になる。
この手順では、ｍ本の連立方程式から、ｎ個の変数ｘ１，ｘ２…ｘｎの値を求める。このため、符号化された変数Ｘ１，Ｘ２，…Ｘｍの間には、ｍ‐ｎ個の自明でない以下の関係式（３）が成り立つことになる。
【００１７】
【数３】
【００１８】
この自明でない関係式を用いることにより、上記の復号式における各変数Ｘ１，Ｘ２，…，Ｘｍの係数を可変とすることができる。
【００１９】
（Ｓ１５：変数の置き換え処理）
プログラム中で用いられている変数ｘ１，ｘ２，…，ｘｎを以下の規則に従い、符号化された変数Ｘ１，Ｘ２，…Ｘｍで置き換える。
（ａ）変数ｘｉへの代入命令への置き換え
アリゴリズム中の変数ｘｉに対する代入命令ｘｉ←ｕを、以下の演算式（４）で示されるように、変数Ｘ１，Ｘ２，…ＸＭに対する代入命令に置き換える。
【００２０】
【数４】
【００２１】
この代入命令が実行されると、符号化されたｍ個全ての変換Ｘ１，Ｘ２，…Ｘｍが、同時に変更される。
（ｂ）参照されている変数ｘｊの置き換え
プログラム中で参照されている変数ｘｊを、Ｓ１４の処理で求めた復号式ｘｊ（Ｘ１，Ｘ２，…Ｘｍ）を用いて、変数Ｘ１，Ｘ２，…Ｘｍの式に置き換える。
【００２２】
（Ｓ１６：後処理）
後処理として、符号化された変数Ｘ１，Ｘ２，…，Ｘｍへの初期値を与える。また、連続する変数Ｘ１，Ｘ２，…Ｘｍへの代入命令のマージを行う。
（ａ）符号化された変数への初期値代入
上記したＳ１５（ａ）、（ｂ）の処理により、プログラム中の変数ｘ１，ｘ２，…，ｘｎは全てＸ１，Ｘ２，…，Ｘｍで置き換えられる。これらの変数の初期値は、自明でない関係式ｆ１，ｆ２，…ｆｍ‐ｎを満たす任意の整数とする。
（ｂ）連続する代入命令のマージ
Ｓ１５（ｂ）の処理により生成された、符号化された変数Ｘ１，Ｘ２，…Ｘｍへの代入命令の中で、連続するものをマージする。
【００２３】
（Ｓ１７：判定処理）
プログラムの解析が十分に困難であると判定されれば、難読化処理を終了する。さらなる難読化が必要であると判定されれば、Ｓ１１からＳ１６までの処理を繰り返す。
【００２４】
以下に、本発明の符号化方法をＣ言語で記述されたソースコードに適用した場合の具体的事例を引用して説明する。
図２は、入力された整数数ｎに対し、ｎの階乗を出力するプログラムのソースコードである。図２のプログラムの本質的な部分を取り出すと、図３に示すアルゴリズムになる。このアルゴリズムに対して本名発明を以下のように適用する。
【００２５】
（Ｓ１１：難読化対象の選択処理）
上記したアルゴリズム中では、３つの変数ｘ，ｙおよびｎが用いられている。ここでは、２つの変数ｘ，ｙを符号化するものとする。
（Ｓ１２：秘密鍵の生成処理）
ここでは、３×２型行列Ａおよび３次元ベクトルｃを秘密鍵とする。これは以下の式（５）で示される。
【００２６】
【数５】
【００２７】
（Ｓ１３：変換式の定義処理）
生成した行列Ａおよびベクトルｃを用いて以下の変換式（６）が得られる。
【００２８】
【数６】
【００２９】
ここで、Ｘ，Ｙ，Ｚは、難読化後のプログラムで用いられる符号化された変数である。
【００３０】
（Ｓ１４：復号式の導出処理）
Ｓ１３の処理で定義した変数を２つの変数ｘ，ｙに関する３本の連立方程式と見なし、それぞれの変数について解く。その結果、それぞれの変数に対する以下の復号式（７）が得られる。
【００３１】
【数７】
【００３２】
この復号式により、元のプログラムの変数ｘ，ｙの値を、符号化された変数Ｘ，Ｙ，Ｚを用いて表すことが可能になる。ここで、ｋ１，ｋ２は任意定数である。また、３本の連立方程式から２個の変数の値が求まるためには、符号化された変数Ｘ，Ｙ，Ｚの間には１つの自明でない以下の関係式５Ｘ−１３Ｙ＋１４Ｚ＋４５＝０が成り立つ必要がある。
このため、２つの復号式ｘ（Ｘ，Ｙ，Ｚ）、ｙ（Ｘ，Ｙ，Ｚ）には、それぞれ任意定数ｋ１，ｋ２が含まれているが、一意にｘおよびｙが求まる。
【００３３】
（Ｓ１５：変数の置き換え処理）
アルゴリズム中で用いられている変数ｘ，ｙを、以下の規則に従い、符号化されて変数Ｘ，Ｙ，Ｚで置き換える。
（ａ）変数ｘ，ｙに対する代入命令の置き換え
アルゴリズム中の変数ｘ，ｙに対する代入命令ｘ←ｕ，ｙ←ｕを、それぞれ以下の演算式（８）ように、変数Ｘ，Ｙ，Ｚに対する代入命令に置き換える。
【００３４】
【数８】
【００３５】
この代入命令が実行されると、符号化された全ての変数Ｘ，Ｙ，Ｚが、同時に変更される。アルゴリズム中では、図４に示すように、４個所で変数ｘ，ｙに対する代入が行われている。これらの代入命令を、上記の符号化された変数Ｘ，Ｙ，Ｚに対する代入命令で置き換えたアルゴリズムを図５に示す。
【００３６】
（ｂ）参照されている変数ｘ，ｙの置き換え
プログラム中で参照されている変数ｘ，ｙを、Ｓ１４の処理で求めた復号式ｘ＝ｘ（Ｘ，Ｙ，Ｚ）、ｙ＝ｙ（Ｘ，Ｙ，Ｚ）を用いて、符号化された変数Ｘ，Ｙ，Ｚに置き換える。この際、任意定数ｋ１，ｋ２には、具体的な任意の数値を代入しておく。
アルゴリズム中では、図６に示すように、７個所で変数ｘおよびｙが参照されている。これからの参照されている変数ｘ，ｙを、復号式を用いて変数Ｘ，Ｙ，Ｚに置き換えると、図７のようなアルゴリズムが得られる。さらに、式を整理すれば図８のようなアルゴリズムが得られる。
以上のＳ１５（ａ）、Ｓ１５（ｂ）の処理により、アルゴリズム中の変数ｘ，ｙは全てＸ，Ｙ，Ｚに置き置き換えられる。
【００３７】
（Ｓ１６：後処理）
後処理として、符号化された変数Ｘ，Ｙ，Ｚへの初期値を与える。また、連続する代入命令のマージを行う。
（ａ）変数Ｘ，Ｙ，Ｚへの初期値代入命令の追加
変数Ｘ，Ｙ，Ｚには、自明でない関係５Ｘ−１３Ｙ＋１４Ｚ＋４５＝０を満たす任意の初期値を与える。ここでは、Ｘ，Ｙ，Ｚにそれぞれ、初期値−７，４，３を与える。初期値が与えられたアルゴリズムを、図９に示す。
（ｂ）連続する代入命令のマージ
Ｓ１５（ｂ）の処理により生成された、変数Ｘ，Ｙ，Ｚに対する代入命令の中で、連続する命令をマージする。
図１０に示すように、アルゴリズム中には、連続する変数Ｘ，Ｙ，Ｚの代入命令が２個所ある。これらの命令をマージしたアルゴリズムを図１１に示す。
【００３８】
（Ｓ１７：判定処理）
そして、アルゴリズムの解析が、十分に困難になっているかどうかを判定する。ここでは、十分に困難になっているものとし、難読化処理を終了する。最終的に得られるアルゴリズムは、図１１のようになる。このアルゴリズムを実現するＣ言語のソースコードを図１２に示す。難読化後のソースコードは、図２に示される難読化前のソースコードと比較し、可読性が著しく低下している。
【００３９】
以上詳細に説明したように、本発明の符号化方法およびそのプログラムは、行列およびベクトルを秘密鍵として、複数の変数を同時に符号化することを特徴とするものであり、プログラム中のｎ個の変数を線形変換により同時にｍ個の整数に符号化するため、元のプログラムで用いられている変数の個数を秘匿すると同時に、変数間の参照および代入関係も秘匿することができる。また、変換鍵として行列およびベクトルを用いるため鍵の候補数を多くすることができる。
なお、本発明によれば、ＣやＪａｖａ（登録商標）など高級言語のソースコードから、携帯端末等で利用されているものを含む各種プロセッサの機械語まで、幅広いソフトウェアに適用可能である。
【００４０】
なお、上記した本発明実施形態は、演算装置、もしくはコンピュータにより実現されるものであり、特に、後者によれば、Ｓ１１〜Ａ１７のそれぞれで実行される手順を含むプログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行することによって本発明の符号化方法を実現するものである。ここでいうコンピュータとは、ＯＳや周辺機器等のハードウェアを含む。
また、「コンピュータ」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものであってもよい。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。更に、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００４１】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００４３】
【図１】本発明実施形態に係わる符号化方法の実行手順を示す図である。
【図２】難読化前のソースコードの一例を示す図である。
【図３】難読化前のソースコードから抜き出した本質的なアルゴリズムを示す図である。
【図４】アルゴリズム中の変数ｘ，ｙに対する代入命令を示す図である。
【図５】変数ｘ，ｙに対する代入命令を、符号化された変数Ｘ，Ｙ，Ｚに対する代入命令に置き換えたアルゴリズムを示す図である。
【図６】アルゴリズム中で参照されている変数ｘ，ｙを示す図である。
【図７】参照されている変数ｘ，ｙを符号化された変数Ｘ，Ｙ，Ｚで置き換えたアルゴリズムを示す図である。
【図８】図７を整理したアルゴリズムを示す図である。
【図９】変数Ｘ，Ｙ，Ｚへの初期値の代入命令を追加したアルゴリズムを示す図である。
【図１０】連続する変数Ｘ，Ｙ，Ｚへの代入命令を示す図である。
【図１１】最終的に得られるアルゴリズムを示す図である。
【図１２】難読化後のソースコードの一例を示す図である。
【技術分野】
【０００１】
本発明は、プログラム中の変数を線形変換して符号化を施す、符号化方法およびそのプログラムに関する。
【背景技術】
【０００２】
ソフトウェアには、価値のあるアルゴリズムおよびコンテンツの暗号鍵など、利用者に対して秘密にすべき情報が含まれる場合がある。一方では、ソフトウェアを解析するための技術（ＲＥ：Reverse Engineering）が数多く開発されている。このため、これらの技術によりソフトウェアが解析されると、不正者が秘密情報を入手するという脅威が考えられる。この脅威に対し、ソフトウェアの仕様を保ったまま、ソフトウェアの解析を困難にする難読化という技術がある。
【０００３】
変数の符号化によるソフトウェアの難読化として、ソースコード中の変数を線形変換により符号化する方法が提案されている（例えば、非特許文献１参照）。この方法では、単一の変数ｘを線形変換により、変数Ｘ（＝ａｘ＋ｂ）に符号化することで、ソフトウェアの解析を難しくすることを意図するものである。ここでは、線形変換の際に用いる整数ａ，ｂが秘密鍵となる。この方法では、ソースコード中の変数の値や演算を隠蔽することを目的としている。
【非特許文献１】佐藤他、信学技報、Ｖｏｌ．ＩＴ‐２００２−４９，ｐｐ．１３−１８，Ｍａｒ．２００２“データの符号化と演算子の変換によるプログラムの難読化手法”
【発明の開示】
【発明が解決しようとする課題】
【０００４】
前記した非特許文献１に開示された技術によれば、ソースコード中の変数の値や演算を秘匿することはできても、難読化前のソースコードで用いられている変数の個数、ならびに変数間における参照・代入の関係を秘匿することは不可能であった。また、秘密鍵の候補数は少なく、秘密鍵の全数探索による攻撃についても脆弱であると考えられる。
【０００５】
本発明は上記事情に鑑みてなされたものであり、元のプログラムで用いられている変数の個数、ならびに当該変数間の参照・代入関係を秘匿し、かつ、秘密鍵の候補数を多くして耐性の高いプログラムの難読化を実現する、符号化方法およびそのプログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
上記した課題を解決するために本発明は、プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化するステップと、を有することを特徴とする。
【０００７】
また、本発明は、プログラム中の変数を線形変換して符号化を施す符号化装置に用いられるプログラムであって、前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択する処理と、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成する処理と、前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化する処理と、をコンピュータに実行させることを特徴とする。
【発明の効果】
【０００８】
本発明によれば、プログラム中のｎ個の変数を線形変換により同時にｍ個の整数に符号化するため、プログラム中で用いられている変数の個数を秘匿すると同時に、変数間の参照および代入関係も秘匿することができる。また、変換鍵として行列およびベクトルを用いるため鍵の候補数を多くすることができる。このことにより、耐性の高いソフトウェアの難読化を実現することができる。
【発明を実施するための最良の形態】
【０００９】
図１は、本発明実施形態に係わるの符号化方法の概略手順を示すフローチャートである。
本発明の符号化方法は、符号化を施すn個（但し、ｎは正の整数）の変数を任意に選択し、ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成して変換鍵とし、ｎ個の変数を線形変換して同時にｍ個の整数に符号化することを特徴とするものであり、これを実現するために、図１に示されるように、符号化を施すｎ個の変数を選択する難読化対象選択処理（Ｓ１１）からはじまり、秘密鍵の生成（Ｓ１２）、変化式の定義（Ｓ１３）、復号式の導出（Ｓ１４）、変数の置換（Ｓ１５）、後処理（Ｓ１６）、判定（Ｓ１７）の各ステップを順次実行する。以下にステップ毎の詳細手順の説明を行う。
【００１０】
（Ｓ１１：難読化対象の選択処理）
まず、プログラムの中から、難読化の対象として符号化を施すｎ個（ｎは整数数）の変数を任意に選択する。この操作で選ばれたｎ個の変数ｘ１，ｘ２…，ｘｎ，とする。
（Ｓ１２：秘密鍵の生成処理）
ここでは、ｍ×ｎ型行列Ａ、ｍ次元ベクトルｃを任意に生成し、これらを秘密鍵とする。但し、ｍは、ｍ≧ｎなる正整数である。
【００１１】
（Ｓ１３：変換式の定義処理）
次に、生成した行列Ａおよびベクトルｃを用いて以下の変換式（１）を定義する。
【００１２】
【数１】
【００１３】
ここで、Ｘ１，Ｘ２，…，Ｘｍは、難読化後のソフトウェアで用いられる符号化されたｍ個の変数である。
【００１４】
（Ｓ１４：復号式の導出処理）
上記した変換式をｎ個の変数ｘ１，ｘ２，…，ｘｎに関するｍ本の連立方程式と見なし、それぞれの変数について解く。その結果、それぞれの変数ｘ１，ｘ２，…，ｘｎに関して以下の（２）で示す復号式が成立する。
【００１５】
【数２】
【００１６】
この復号式により、元のプログラム中のそれぞれの変数ｘ１，ｘ２，…，ｘｎの値が、復号化された変数Ｘ１，Ｘ２，…Ｘｍを用いて表すことが可能になる。
この手順では、ｍ本の連立方程式から、ｎ個の変数ｘ１，ｘ２…ｘｎの値を求める。このため、符号化された変数Ｘ１，Ｘ２，…Ｘｍの間には、ｍ‐ｎ個の自明でない以下の関係式（３）が成り立つことになる。
【００１７】
【数３】
【００１８】
この自明でない関係式を用いることにより、上記の復号式における各変数Ｘ１，Ｘ２，…，Ｘｍの係数を可変とすることができる。
【００１９】
（Ｓ１５：変数の置き換え処理）
プログラム中で用いられている変数ｘ１，ｘ２，…，ｘｎを以下の規則に従い、符号化された変数Ｘ１，Ｘ２，…Ｘｍで置き換える。
（ａ）変数ｘｉへの代入命令への置き換え
アリゴリズム中の変数ｘｉに対する代入命令ｘｉ←ｕを、以下の演算式（４）で示されるように、変数Ｘ１，Ｘ２，…ＸＭに対する代入命令に置き換える。
【００２０】
【数４】
【００２１】
この代入命令が実行されると、符号化されたｍ個全ての変換Ｘ１，Ｘ２，…Ｘｍが、同時に変更される。
（ｂ）参照されている変数ｘｊの置き換え
プログラム中で参照されている変数ｘｊを、Ｓ１４の処理で求めた復号式ｘｊ（Ｘ１，Ｘ２，…Ｘｍ）を用いて、変数Ｘ１，Ｘ２，…Ｘｍの式に置き換える。
【００２２】
（Ｓ１６：後処理）
後処理として、符号化された変数Ｘ１，Ｘ２，…，Ｘｍへの初期値を与える。また、連続する変数Ｘ１，Ｘ２，…Ｘｍへの代入命令のマージを行う。
（ａ）符号化された変数への初期値代入
上記したＳ１５（ａ）、（ｂ）の処理により、プログラム中の変数ｘ１，ｘ２，…，ｘｎは全てＸ１，Ｘ２，…，Ｘｍで置き換えられる。これらの変数の初期値は、自明でない関係式ｆ１，ｆ２，…ｆｍ‐ｎを満たす任意の整数とする。
（ｂ）連続する代入命令のマージ
Ｓ１５（ｂ）の処理により生成された、符号化された変数Ｘ１，Ｘ２，…Ｘｍへの代入命令の中で、連続するものをマージする。
【００２３】
（Ｓ１７：判定処理）
プログラムの解析が十分に困難であると判定されれば、難読化処理を終了する。さらなる難読化が必要であると判定されれば、Ｓ１１からＳ１６までの処理を繰り返す。
【００２４】
以下に、本発明の符号化方法をＣ言語で記述されたソースコードに適用した場合の具体的事例を引用して説明する。
図２は、入力された整数数ｎに対し、ｎの階乗を出力するプログラムのソースコードである。図２のプログラムの本質的な部分を取り出すと、図３に示すアルゴリズムになる。このアルゴリズムに対して本名発明を以下のように適用する。
【００２５】
（Ｓ１１：難読化対象の選択処理）
上記したアルゴリズム中では、３つの変数ｘ，ｙおよびｎが用いられている。ここでは、２つの変数ｘ，ｙを符号化するものとする。
（Ｓ１２：秘密鍵の生成処理）
ここでは、３×２型行列Ａおよび３次元ベクトルｃを秘密鍵とする。これは以下の式（５）で示される。
【００２６】
【数５】
【００２７】
（Ｓ１３：変換式の定義処理）
生成した行列Ａおよびベクトルｃを用いて以下の変換式（６）が得られる。
【００２８】
【数６】
【００２９】
ここで、Ｘ，Ｙ，Ｚは、難読化後のプログラムで用いられる符号化された変数である。
【００３０】
（Ｓ１４：復号式の導出処理）
Ｓ１３の処理で定義した変数を２つの変数ｘ，ｙに関する３本の連立方程式と見なし、それぞれの変数について解く。その結果、それぞれの変数に対する以下の復号式（７）が得られる。
【００３１】
【数７】
【００３２】
この復号式により、元のプログラムの変数ｘ，ｙの値を、符号化された変数Ｘ，Ｙ，Ｚを用いて表すことが可能になる。ここで、ｋ１，ｋ２は任意定数である。また、３本の連立方程式から２個の変数の値が求まるためには、符号化された変数Ｘ，Ｙ，Ｚの間には１つの自明でない以下の関係式５Ｘ−１３Ｙ＋１４Ｚ＋４５＝０が成り立つ必要がある。
このため、２つの復号式ｘ（Ｘ，Ｙ，Ｚ）、ｙ（Ｘ，Ｙ，Ｚ）には、それぞれ任意定数ｋ１，ｋ２が含まれているが、一意にｘおよびｙが求まる。
【００３３】
（Ｓ１５：変数の置き換え処理）
アルゴリズム中で用いられている変数ｘ，ｙを、以下の規則に従い、符号化されて変数Ｘ，Ｙ，Ｚで置き換える。
（ａ）変数ｘ，ｙに対する代入命令の置き換え
アルゴリズム中の変数ｘ，ｙに対する代入命令ｘ←ｕ，ｙ←ｕを、それぞれ以下の演算式（８）ように、変数Ｘ，Ｙ，Ｚに対する代入命令に置き換える。
【００３４】
【数８】
【００３５】
この代入命令が実行されると、符号化された全ての変数Ｘ，Ｙ，Ｚが、同時に変更される。アルゴリズム中では、図４に示すように、４個所で変数ｘ，ｙに対する代入が行われている。これらの代入命令を、上記の符号化された変数Ｘ，Ｙ，Ｚに対する代入命令で置き換えたアルゴリズムを図５に示す。
【００３６】
（ｂ）参照されている変数ｘ，ｙの置き換え
プログラム中で参照されている変数ｘ，ｙを、Ｓ１４の処理で求めた復号式ｘ＝ｘ（Ｘ，Ｙ，Ｚ）、ｙ＝ｙ（Ｘ，Ｙ，Ｚ）を用いて、符号化された変数Ｘ，Ｙ，Ｚに置き換える。この際、任意定数ｋ１，ｋ２には、具体的な任意の数値を代入しておく。
アルゴリズム中では、図６に示すように、７個所で変数ｘおよびｙが参照されている。これからの参照されている変数ｘ，ｙを、復号式を用いて変数Ｘ，Ｙ，Ｚに置き換えると、図７のようなアルゴリズムが得られる。さらに、式を整理すれば図８のようなアルゴリズムが得られる。
以上のＳ１５（ａ）、Ｓ１５（ｂ）の処理により、アルゴリズム中の変数ｘ，ｙは全てＸ，Ｙ，Ｚに置き置き換えられる。
【００３７】
（Ｓ１６：後処理）
後処理として、符号化された変数Ｘ，Ｙ，Ｚへの初期値を与える。また、連続する代入命令のマージを行う。
（ａ）変数Ｘ，Ｙ，Ｚへの初期値代入命令の追加
変数Ｘ，Ｙ，Ｚには、自明でない関係５Ｘ−１３Ｙ＋１４Ｚ＋４５＝０を満たす任意の初期値を与える。ここでは、Ｘ，Ｙ，Ｚにそれぞれ、初期値−７，４，３を与える。初期値が与えられたアルゴリズムを、図９に示す。
（ｂ）連続する代入命令のマージ
Ｓ１５（ｂ）の処理により生成された、変数Ｘ，Ｙ，Ｚに対する代入命令の中で、連続する命令をマージする。
図１０に示すように、アルゴリズム中には、連続する変数Ｘ，Ｙ，Ｚの代入命令が２個所ある。これらの命令をマージしたアルゴリズムを図１１に示す。
【００３８】
（Ｓ１７：判定処理）
そして、アルゴリズムの解析が、十分に困難になっているかどうかを判定する。ここでは、十分に困難になっているものとし、難読化処理を終了する。最終的に得られるアルゴリズムは、図１１のようになる。このアルゴリズムを実現するＣ言語のソースコードを図１２に示す。難読化後のソースコードは、図２に示される難読化前のソースコードと比較し、可読性が著しく低下している。
【００３９】
以上詳細に説明したように、本発明の符号化方法およびそのプログラムは、行列およびベクトルを秘密鍵として、複数の変数を同時に符号化することを特徴とするものであり、プログラム中のｎ個の変数を線形変換により同時にｍ個の整数に符号化するため、元のプログラムで用いられている変数の個数を秘匿すると同時に、変数間の参照および代入関係も秘匿することができる。また、変換鍵として行列およびベクトルを用いるため鍵の候補数を多くすることができる。
なお、本発明によれば、ＣやＪａｖａ（登録商標）など高級言語のソースコードから、携帯端末等で利用されているものを含む各種プロセッサの機械語まで、幅広いソフトウェアに適用可能である。
【００４０】
なお、上記した本発明実施形態は、演算装置、もしくはコンピュータにより実現されるものであり、特に、後者によれば、Ｓ１１〜Ａ１７のそれぞれで実行される手順を含むプログラムをコンピュータ読み取り可能な記録媒体に記録し、この記録媒体に記録されたプログラムをコンピュータに読み込ませ、実行することによって本発明の符号化方法を実現するものである。ここでいうコンピュータとは、ＯＳや周辺機器等のハードウェアを含む。
また、「コンピュータ」は、ＷＷＷシステムを利用している場合であれば、ホームページ提供環境（あるいは表示環境）も含むものであってもよい。また、「コンピュータ読み取り可能な記録媒体」とは、フレキシブルディスク、光磁気ディスク、ＲＯＭ、ＣＤ−ＲＯＭ等の可搬媒体、コンピュータシステムに内蔵されるハードディスク等の記憶装置のことをいう。更に、インターネット等のネットワークや電話回線等の通信回線を介してプログラムが送信された場合のシステムやクライアントとなるコンピュータシステム内部の揮発性メモリ（ＲＡＭ）のように、一定時間プログラムを保持しているものも含むものとする。
【００４１】
また、上記プログラムは、このプログラムを記憶装置等に格納したコンピュータシステムから、伝送媒体を介して、あるいは、伝送媒体中の伝送波により他のコンピュータシステムに伝送されてもよい。ここで、プログラムを伝送する「伝送媒体」は、インターネット等のネットワーク（通信網）や電話回線等の通信回線（通信線）のように情報を伝送する機能を有する媒体のことをいう。
また、上記プログラムは、前述した機能の一部を実現するためのものであっても良い。さらに、前述した機能をコンピュータシステムにすでに記録されているプログラムとの組み合わせで実現できるもの、いわゆる差分ファイル（差分プログラム）であっても良い。
【００４２】
以上、この発明の実施形態につき、図面を参照して詳述してきたが、具体的な構成はこの実施形態に限られるものではなく、この発明の要旨を逸脱しない範囲の設計等も含まれる。
【図面の簡単な説明】
【００４３】
【図１】本発明実施形態に係わる符号化方法の実行手順を示す図である。
【図２】難読化前のソースコードの一例を示す図である。
【図３】難読化前のソースコードから抜き出した本質的なアルゴリズムを示す図である。
【図４】アルゴリズム中の変数ｘ，ｙに対する代入命令を示す図である。
【図５】変数ｘ，ｙに対する代入命令を、符号化された変数Ｘ，Ｙ，Ｚに対する代入命令に置き換えたアルゴリズムを示す図である。
【図６】アルゴリズム中で参照されている変数ｘ，ｙを示す図である。
【図７】参照されている変数ｘ，ｙを符号化された変数Ｘ，Ｙ，Ｚで置き換えたアルゴリズムを示す図である。
【図８】図７を整理したアルゴリズムを示す図である。
【図９】変数Ｘ，Ｙ，Ｚへの初期値の代入命令を追加したアルゴリズムを示す図である。
【図１０】連続する変数Ｘ，Ｙ，Ｚへの代入命令を示す図である。
【図１１】最終的に得られるアルゴリズムを示す図である。
【図１２】難読化後のソースコードの一例を示す図である。
【特許請求の範囲】
【請求項１】
プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、
前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、
ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、
前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化するステップと、
を有することを特徴とする符号化方法。
【請求項２】
プログラム中の変数を線形変換して符号化を施す符号化装置に用いられるプログラムであって、
前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択する処理と、
ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成する処理と、
前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化する処理と、
をコンピュータに実行させるプログラム。
【請求項１】
プログラム中の変数を演算装置によって線形変換して符号化を施す符号化方法であって、
前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択するステップと、
ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成するステップと、
前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化するステップと、
を有することを特徴とする符号化方法。
【請求項２】
プログラム中の変数を線形変換して符号化を施す符号化装置に用いられるプログラムであって、
前記符号化を施すn個（但し、ｎは正整数）の変数を任意に選択する処理と、
ｍ×ｎの行列（但し、ｍは、ｍ≧ｎの正整数）およびｍ次元の任意のベクトルを生成する処理と、
前記生成した行列およびベクトルを変換鍵として前記ｎ個の変数を線形変換して同時にｍ個の整数を符号化する処理と、
をコンピュータに実行させるプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【公開番号】特開２００６−７９３４７（Ｐ２００６−７９３４７Ａ）
【公開日】平成１８年３月２３日（２００６．３．２３）
【国際特許分類】
【出願番号】特願２００４−２６２６７６（Ｐ２００４−２６２６７６）
【出願日】平成１６年９月９日（２００４．９．９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
【公開日】平成１８年３月２３日（２００６．３．２３）
【国際特許分類】
【出願日】平成１６年９月９日（２００４．９．９）
【出願人】（０００２０８８９１）ＫＤＤＩ株式会社 (2,700)
【Ｆターム（参考）】
[ Back to top ]