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