(57)【特許請求の範囲】
【請求項１】
デジタル難読化算術演算のためのパラメータを生成する電子生成装置であって、前記パラメータは有限数の環要素を有する可換環
【数９】
0006368051.tif 000010
を定義し、これら環要素には基底要素（ｕ）が、各環要素が前記基底要素の２つの冪の間の差分として表すことができるように含まれ、当該電子生成装置は、
素数モジュラス（ｐ）を、該素数モジュラスが前記基底要素の所望の位数（ｋ）の二乗より小となる（ｋ２＞ｐ）ように発生する素数ユニットと、
基底要素ユニットと、
を有し、該基底要素ユニットは、
１より大きく前記素数モジュラス−１より小さな基底要素を可能性のある基底要素（ｕ）として選択し、
前記可能性のある基底要素の異なる冪（ｕ０，ｕ１，ｕ２，ｕ３，…，ｕｋ−１）を発生し、
前記可能性のある基底要素（ｕ）が前記所望の位数と等しい位数を有するかを判定し、もし有するなら、
前記素数モジュラスのモジュロの各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定し、
前記各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができると判定された場合に、前記素数及び前記基底要素を含むパラメータを生成する、
電子生成装置。
【請求項２】
前記素数ユニットが、素数（ｐ）を前記所望の位数（ｋ）が前記素数―１を割り切れるように発生する、請求項１に記載の電子生成装置。
【請求項３】
前記素数ユニットが、前記所望の位数の二乗より小さな全ての素数（ｐ）を発生する、請求項１又は２に記載の電子生成装置。
【請求項４】
前記各環要素が前記基底要素の２つの冪の間の差分として表すことができるかについて少なくとも肯定的に判定するまで、素数及び／又は可能性のある基底要素を反復的に発生する、請求項１又は２に記載の電子生成装置。
【請求項５】
前記各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定する動作が、
前記素数モジュラスのモジュロの整数のリスト及び関連するフラグを発生する動作、
前記可能性のある基底要素の２つの冪の間の差分を発生すると共に、該差分に関連する前記フラグを設定する動作、及び
前記整数のリストに関連する全てのフラグが設定された場合に、前記各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができると判定する動作、
を有する、請求項１ないし４の何れか一項に記載の電子生成装置。
【請求項６】
前記リストが１から前記素数モジュラス−１までの整数からなる、請求項５に記載の電子生成装置。
【請求項７】
整数ユニットを有し、該整数ユニットが、
整数モジュラス（ｎ）を、該整数モジュラスが前記基底要素の所望の位数（ｋ）の二乗より小となる（ｋ２＞ｎ）ように発生し、
前記整数モジュラスの約数に対して、該約数のモジュロの各環要素が基底要素（ｕ’）の２つの冪の間の差分として表すことができるような基底要素（ｕ’）が存在するかを判定し、もし存在するなら、
前記整数モジュラス（ｎ）のモジュロの各環要素が前記可能性のある基底要素（ｕ）の２つの冪の間の差分として表すことができるかを判定する、
請求項１ないし６の何れか一項に記載の電子生成装置。
【請求項８】
可換環
【数１０】
0006368051.tif 000011
において難読化算術演算を実行する計算装置において使用するための増加テーブルを計算し、当該電子生成装置は増加テーブルを構築するテーブル生成ユニットを有し、該テーブル生成ユニットが、
入力環要素を反復して選択し、
前記入力環要素に環加算がされた増加環要素に等しい出力環要素を決定し、
前記出力環要素を符号化する出力整数リストを決定し、
前記入力環要素を前記出力整数リストにマッピングするエントリを前記増加テーブルに追加する、
請求項１ないし７の何れか一項に記載の電子生成装置。
【請求項９】
前記素数モジュラス又は整数モジュラスを発生する前に、前記所望の位数を受信するインターフェースを有する、請求項１ないし８の何れか一項に記載の電子生成装置。
【請求項１０】
デジタル難読化算術演算のためのパラメータを生成するためのコンピュータの作動方法であって、前記パラメータは有限数の環要素を有する可換環を定義し、これら環要素には基底要素（ｕ）が、各環要素が前記基底要素の２つの冪の間の差分として表すことができるように含まれ、当該コンピュータの作動方法は、
前記コンピュータが、素数モジュラス（ｐ）を、該素数モジュラスが前記基底要素の所望の位数（ｋ）の二乗より小となる（ｋ２＞ｐ）ように発生するステップと、
前記コンピュータが、１より大きく前記素数モジュラス−１より小さな基底要素を可能性のある基底要素（ｕ）として選択するステップと、
前記コンピュータが、前記可能性のある基底要素の異なる冪（ｕ０，ｕ１，ｕ２，ｕ３，…，ｕｋ−１）を発生するステップと、
前記コンピュータが、前記可能性のある基底要素（ｕ）が前記所望の位数と等しい位数を有するかを判定するステップと、もし有するなら、
前記コンピュータが、前記素数モジュラスのモジュロの各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するステップと、
前記コンピュータが、前記各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができると判定された場合に、前記素数及び前記基底要素を含むパラメータを生成するステップと、
を有する、コンピュータの作動方法。
【請求項１１】
前記コンピュータが、整数モジュラス（ｎ）を、該整数モジュラスが前記基底要素の所望の位数（ｋ）の二乗より小となる（ｋ２＞ｎ）ように発生するステップと、
前記コンピュータが、前記整数モジュラスの約数に対して、該約数のモジュロの各環要素が基底要素（ｕ’）の２つの冪の間の差分として表すことができるような基底要素（ｕ’）が存在するかを判定するステップと、もし存在するなら、
前記コンピュータが、前記整数モジュラス（ｎ）のモジュロの各環要素が前記可能性のある基底要素（ｕ）の２つの冪の間の差分として表すことができるかを判定するステップと、
を有する、請求項１０に記載のコンピュータの作動方法。
【請求項１２】
コンピュータに、請求項１０又は１１に記載の方法の全てのステップを実行させるための、コンピュータプログラム。
【請求項１３】
コンピュータ読取可能な媒体上で具現化される、請求項１２に記載のコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子生成装置、電子生成方法、コンピュータプログラム及びコンピュータ読取可能な媒体に関する。
【背景技術】
【０００２】
ホワイトボックス暗号法、もっと一般的にはソフトウェア難読化においては、しばしば、計算は平文値の代わりに符号化値に対して実行される。難読化ソフトウェアのリバースエンジニアリングは、計算が平文値自体に対する代わりに符号化値に対して実行される場合に一層困難になる。
【０００３】
上記符号化の後、加算又は乗算等の通常の演算は、最早、コンピュータの内蔵原始関数を用いては実行することができなくなる。符号化値の直接の加算は、通常、当該値の加算の符号化とはならない。同様のことが、乗算にも当てはまる。式では、殆どのｘ及びｙに対してE(x)+E(y)≠E(x+y)であり、Ｅは符号化関数を示す。
【０００４】
この問題に対する解決策は、加算（Ａ）及び乗算（Ｍ）テーブルを導入することである。これらのテーブルは、入力として２つの符号化値をとり、加算又は乗算演算の符号化に対応する出力としての符号化を生成する。これらテーブルは、A(E(x),E(y))＝E(x;y)；M(E(x),E(y))＝E(xy)と定義することができる。これらのテーブルは、算術演算が符号化値に対して直接実行されることを可能にする。
【０００５】
テーブルを用いて難読化された加算及び乗算は、少なくとも２つの欠点を抱えている。第１に、斯かるテーブルは非常に大きくなり得る。ｘ及びｙがｌ（エル）ビットとして表される場合、各テーブルは２２ｌｌビットを必要とする。
【０００６】
第２に、このような大きなテーブルはソフトウェアで容易に見付けることができる。もっと悪いことに、テーブルは、符号化されているにも拘わらず、例えば当該符号化内に保存される斯かる関数の特性を介して、依然として加算又は乗算演算として識別され得る。例えば、乗算テーブルは、M(E(0),E(x))＝E(0)を満足する。攻撃者は、何の演算をテーブルが表しているかを推定するために、この及び同様の特性を利用することができる。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
出願人による以前の出願では、難読化算術演算を実行するための改善された方法が提示された。該以前の出願は、ヨーロッパ特許庁に対して“難読化算術演算を実行するための電子計算装置”なる名称で出願された（出願日：2014年９月４日；出願番号：14186951.1）。該以前の出願は参照により全体として、及び特に整数環に対して同質的難読化を用いる計算装置の説明に関して本明細書に組み込まれるものとする。
【課題を解決するための手段】
【０００８】
発明者は、幾つかのケースにおいて、符号化値に対する乗算及び加算は、複数の値を単一の符号化値に符号化する必要性無しに単一のテーブルを用いて実行することができることを見出した。加算及び乗算に対し同一のテーブルが使用される故に、リバースエンジニアリングの間に加算又は乗算が使用されたかを調べることは困難となる。外部から見た場合に加算及び乗算は同一の演算のように見えるので、発明者は該方法を“同質的難読化”と称した。攻撃者が使用されているテーブルを見付けることができたとしても、且つ、該攻撃者が、どうにかして、その関数を増加テーブル（increment table）として解明することができたとしても、該攻撃者には加算又は乗算が実行されたかは依然として分からないであろう。当該テーブルが整数のリストの要素に対して作用する態様は、加算及び乗算に対して相違するが、このことは、伝統的難読化法を用いて容易に隠蔽することができる。
【０００９】
加えて、使用される単一テーブルは、背景技術で述べたもの（約２２ｌｌビットが必要とされる）よりも小さい。加算のみが使用されるとしても、難読化加算のために必要とされるテーブルは、背景技術において示されたテーブルよりも小さい。
【００１０】
例えば、環の要素（元）は２つの整数（ａ，ｂ）として符号化することができる。算術演算は、符号化環要素を該符号化環要素＋増加値にマッピングする増加テーブルを用いて符号化に対し直接的に実行することができる。例えば、該テーブルはｕｃ−ｕｄ＝ｕａ−ｕｂ＋１なら、（ａ、ｂ）を（ｃ，ｄ）にマッピングすることができる。加算及び乗算の両方は、増加テーブルの反復適用により実行される。
【００１１】
各及び全ての環が整数リストとしての符号化を可能にするものではないが、難読化算術演算は多くの異なる可換環Ｒに当てはまる。可換環は、多くの異なる馴染みのある数学的構造を、例えば整数・モジュロ・数
【数１】
0006368051.tif 000002
、を含む数学的概念である。請求項による生成装置はデジタル的難読化算術演算のためのパラメータを生成するために使用することができ、前記パラメータは有限数の環要素を持つ可換環
【数２】
0006368051.tif 000003
を定義し、基底要素（ｕ；base element ｕ；基底元ｕ）は環要素内に、各環要素を基底要素の２つの冪の間の差分（ｕa1−ｕa2）として表すことができるように、含まれる。モジュラスｎが、可換環を整数・モジュロ・モジュラスｎ（モジュラスｎを法とする整数）と定義する。
【００１２】
同質的難読化を可能にする整数環の効果的生成は、異なるタイプの環が計算装置で使用されることを可能にし、かくして難読化を向上させる。
【００１３】
本発明による方法は、コンピュータで実施される方法としてコンピュータ上で、専用のハードウェアで、又は両者の組み合わせで実施することができる。本発明による方法の実行可能なコードは、コンピュータプログラム製品上に記憶することができる。コンピュータプログラム製品の例は、メモリ装置、光記憶装置、集積回路、サーバ、オンラインソフトウェア等を含む。好ましくは、コンピュータプログラム製品は、該プログラム製品がコンピュータ上で実行された場合に、本発明による方法を実行するためのコンピュータ読取可能な媒体上に記憶された非一時的プログラムコード手段を有する。
【００１４】
好ましい実施態様において、コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行された場合に、本発明による方法の全てのステップを実行するように適合化されたコンピュータプログラムコード手段を有する。好ましくは、コンピュータプログラムはコンピュータ読取可能な媒体上で具現化される。
【００１５】
本発明の上記及び他の態様は、後述する実施態様から明らかとなり、斯かる実施態様を参照して解説されるであろう。
【００１６】
尚、異なる図において同一の符号を有する項目は、同一の構造的特徴及び同一の機能を有するか、又は同一の信号である。このような項目の機能及び／又は構成が説明された場合、詳細な説明において斯かる項目の繰り返しの説明は必要ないであろう。
【図面の簡単な説明】
【００１７】
【図１ａ】図１ａは、電子生成装置の実施態様の一例を概略的に示す。
【図１ｂ】図１ｂは、電子生成装置の実施態様の一例を概略的に示す。
【図２】図２は、電子生成方法２００の実施態様の一例を概略的に示す。
【図３】各環要素が可能性のある基底要素の２つの冪の間の差分として表され得るかを検証する電子的方法３００の実施態様の一例を概略的に示す。
【図４】図４は、電子生成方法４００の実施態様の一例を概略的に示す。
【図５ａ】図５ａは、一実施態様によるコンピュータプログラムを有する書き込み可能部分を備えるコンピュータ読取可能な媒体を示す。
【図５ｂ】図５ｂは、一実施態様によるプロセッサシステムの概略図を示す。
【発明を実施するための形態】
【００１８】
本発明は多数の異なる形態の実施態様を呈し得るものであるが、図面及び本明細書には１以上の固有の実施態様が図示及び詳細に説明されており、本開示は本発明の原理の例示と見なされるべきであって、本発明を図示及び説明された固有の実施態様に限定することを意図するものではないと理解されたい。
【００１９】
以下においては、理解のために、実施態様の構成要素は動作状態で説明されている。しかしながら、各構成要素は、当該構成要素により実行されると記載されている機能を実行するように構成されていることは明らかであろう。
【００２０】
先に引用した以前の出願において、可換環において難読化算術演算を実行するための計算装置の実施態様について例示された。該計算装置は、有限可換環において難読化算術演算を実行するための電子的装置である。このような環として示された一例は、整数・モジュロ・数
【数３】
0006368051.tif 000004
である。一実施態様による生成装置は、モジュラスを、整数・モジュロ・該モジュラス
【数４】
0006368051.tif 000005
により形成される環が難読化算術演算を可能にするように、見付け出す。難読化ドメイン内及び外で環要素（例えば、整数）を符号化及び復号するために要する基底要素も生成される。
【００２１】
例えば環要素（特には、整数・モジュロ・モジュラス）を表す同質的難読化は、或る種の暗号化された算術演算である（時には、同質的暗号化とも称される）。難読化を用いて、例えばコンピュータソフトウェアコードを該コードのリバースエンジニアリングに対し保護することができる。難読化は、ここでは、算術演算を実行するコードの一部に関するものである。デジタル的難読化算術演算の一実施態様において、計算は暗号文に対して実行することができ、復号（解読）された場合に、平文に対して実行された演算の結果に合致する暗号結果を発生する。言い換えると、何らかの伝統的ソフトウェア難読化を超えて、算術演算は暗号化された値に対して実行することができる。それにも拘わらず、同質的難読化を用いた算術演算手段は、平文に対して実行される算術演算と機能的に同一であり得る。
【００２２】
当該環の要素（元）は、整数・モジュロ・モジュラスとして定義することができる。該環の要素は環要素と称される。該環要素は剰余と呼ぶこともできる。環要素はデジタル的に０とモジュラス−１との間の整数として表すことができ、０及びモジュラス−１が含まれる。環要素に対して加算及び乗算が定義され、後者は環加算及び環乗算と称される。
【００２３】
環要素は、必要ならば、任意の好適な形で表すことができる。例えば、
【数５】
0006368051.tif 000006
の要素は整数として表すことができる。しかしながら、当該計算装置において、環要素は整数リストとして表される。例えば、環要素ａは当該計算装置ではリスト（ａ１，ａ２）により表すことができる。整数リストは、環要素を、環要素と整数リストとの間の何らかのマッピングに従って符号化する。即ち、如何なる環要素が与えられても、該環要素を表す少なくとも１つの整数リストが存在し、如何なる整数リストが与えられても、該リストが表す正確に１つの環要素が存在する。実施態様において、如何なる環要素も整数リストとして表すことができる。
【００２４】
上記整数リストは少なくとも２つの要素を有する。結果として、加算及び乗算演算は、整数リストが短いほど少ないステップしか要さない。従って、一実施態様において、整数リストは常に２つの要素を有する。主な説明において、整数リストは整数対であると仮定するが、３以上の要素を有する整数リストの例が提示される。一例として、（ａ１，ａ２）は環要素（ｕａ１−ｕａ２）にマッピングすることができ、ここで、ｕは基底環要素と称される特別な環要素である。前記以前の出願においては、複数の基底要素を用いることを含め、多数の変形例が説明されている。しかしながら、主な説明においては、“例示的符号化”として、所与の整数リスト（ａ１，ａ２）が環要素（ｕａ１−ｕａ２）にマッピングすると仮定する。このように、各環要素は基底要素ｕの２つの冪の間の差分として表すことができる。
【００２５】
以下では、例えば一実施態様による生成装置により生成されたモジュラス及び基底要素を用いる難読化算術演算の複数の例が提示される。符号化、増加テーブル、環加算方法及び環乗算方法の例が示される。当該計算装置の否定、加算及び乗算ユニットは、これら実施態様の何れに対しても構成することができる。全ての例が、可換環
【数６】
0006368051.tif 000007
に当てはまる。ここで、ｎは正の整数モジュラスである。当該可換環の如何なる要素も、選択された符号化において表すことができる。全ての可換環は、全ての要素が所与の符号化において表される（例えば、所与のタイプの整数リスト表現）ことを可能にするものではない。或る可換環Ｒが与えられた場合、該環Ｒは、Ｒにおける何れの要素も所与の符号化タイプを用いて整数リストとして表すことができるなら、（完全な）同質的難読化を可能にすると言える。当業者は、或る符号化が与えられたとして所与の可換環が完全な同質的難読化を可能にするかを、全ての可能な符号化を発生すると共に、これらが共に所与の環の全ての要素を表すかを検証することにより、検証することができる。
【００２６】
以下、例示的な符号化を先ず説明する。環要素を整数のリストとして表すことができることで共通する多くのタイプの符号化が存在する。これらの整数は環要素ではない。例えば、当該環が整数環ではなく例えば多項式環であっても、要素は整数リストとして表すことができる。使用される符号化、即ち所与の整数リストが環要素にどの様にマッピングするかが、符号化と称される。典型的に、当該整数リストは常に同じ長さのものであるが、このことは必須ではない。当該符号化が一層多くのタイプの整数リスト（例えば、一層長いリスト）を許容するほど、所与の環要素を異なる態様で整数リストとして符号化することができるようになる。
【００２７】
該例示的符号化に対して可換環Ｒが与えられた場合、Ｒの如何なる要素ａも、何らかの整数ａ１及びａ２に対してｕａ１−ｕａ２と書くことができるような特別な環要素ｕが存在する。このような特別な環要素を基底環要素と称する。全ての可換環を斯様な態様で符号化することができるものではないが、これらのうちの十分に多くのものが当該符号化にとり有効である。整数ａ１及びａ２自体は環Ｒの環要素ではない。即ち、これらは、基底要素のモジュロの位数（order）に対して演算される整数である。環要素ａは基底要素ｕの冪、即ちｕａ１及びｕａ２の一次結合に等しいことに注意されたい。即ち、この場合、該一次結合は当該冪を＋１又は−１で乗算し、これらを合計することにより、更に詳細には、第１の冪を第２の冪から減算することにより得られる。当該計算装置は上述した態様で符号化された環要素に対して作用する。加算、否定及び乗算ユニットは、この符号化における環要素に対して作用する。
【００２８】
増加テーブルは、加算及び乗算演算の両方において中心的役割を果たす。増加テーブルは入力環要素をマッピングし、この場合、入力環要素は整数リストとして表すことができる。例えば、入力環要素ｋ＝ｕｋ１−ｕｋ２を表す入力整数リスト（ｋ１，ｋ２）が与えられた場合、テーブルＴは、これを出力整数リストにマッピングする。例えば、Ｔ((ｋ１，ｋ２))＝(ｌ１，ｌ２)は出力環要素ｌ＝ｕｌ１−ｕｌ２をマッピングする。該出力環要素は、入力環要素に環加算された増加環要素に等しい。この例において、増加要素は１、即ち環乗算に対する個性である環要素とすることができる。この場合、ｌ＝ｋ＋１である。テーブルは同一の符号化を用いる環要素に直接適用されるのが好都合であり、従って、整数リスト表現を持つ環要素に適用することができる。それにも拘わらず、テーブルが他の符号化における環要素に適用される実施態様も存在する。該他の符号化は、これも整数リストであるが他のタイプのものとすることができる。また、増加要素は１である必要はない。
【００２９】
以下、当該演算、即ち否定、加算及び乗算を説明する。
【００３０】
［否定］  否定入力環要素ａ＝ｕａ１−ｕａ２を表す否定入力整数リスト（ａ１，ａ２）が与えられた場合、否定出力整数リストは、上記整数リストを並び換えることにより（この場合は、順序を逆転することにより）得ることができる。否定出力整数リストは（ａ２，ａ１）となり得る。偶数位数の基底要素となり得るｕｍ＝−１のようなｍが存在すると仮定すると、他の例として、否定は定数（例えば、ｍ）を整数リストの各整数に加算することにより得ることができる。後者の場合、否定出力整数リストは（ａ１＋ｍ，ａ２＋ｍ）となり得る。これは、−ａ＝ｕａ２−ｕａ１＝ｕａ１＋ｍ−ｕａ２＋ｍ故に成り立つ。整数リストにおける算術演算は、好ましくは、基底要素の位数のモジュロで実行される。ここで、整数リストの整数は基底要素の指数に対応するので、基底要素の位数の同一のモジュロである整数が同一の環要素を符号化する。
【００３１】
［加算］  第１加算入力環要素ａ＝ｕａ１−ｕａ２を符号化する受信された第１加算入力整数リスト（ａ１，ａ２）及び第２加算入力環要素ｂ＝ｕｂ１−ｕｂ２を符号化する受信された第２加算入力整数リスト（ｂ１，ｂ２）を加算するために、先ず、中間加算環要素ｃを符号化する中間加算整数リスト((ｃ１，ｃ２))が決定される。
【００３２】
環要素ｃは、第１加算入力環要素ａ＋基底要素ｕの第２加算入力整数リストから決定される冪（特に、第２加算入力整数リストの第１整数）とすることができる。この例では、ｃ＝ｕａ１−ｕａ２＋ｕｂ１となる。後者を計算するために、ｃ＝ｕａ１−ｕａ２＋ｕｂ１＝(ｕａ１−ｂ１−ｕａ２−ｂ１＋１)ｕｂ１に注目する。括弧内の項は、当該符号化において増加テーブルを用いて書き直すことができる。環要素ｕａ１−ｂ１−ｕａ２−ｂ１に対する増加テーブルの第１の適用により、要素ｕｄ１−ｕｄ２＝ｕａ１−ｂ１−ｕａ２−ｂ１＋１が得られる。例えば、Ｔ((ａ１−ｂ１，ａ２−ｂ１))＝(ｄ１，ｄ２)によるものである。かくして、ｃ１＝ｄ１＋ｂ１及びｃ２＝ｄ２＋ｂ１、従って中間加算整数リスト((ｃ１，ｃ２))を決定することは、更に、第２加算入力整数リストから決定される整数を第１の適用から生じる整数リスト内の整数に加算することを含み得る。ｕｂ１を、整数リスト表現における環要素に（この場合は、ａに）加算することは、時には、正の約分ステップ（positive reduction step）と称される。
【００３３】
このようにして、加算ユニットは中間加算環要素ｃ＝ｕａ１−ｕａ２＋ｕｂ１＝ｕｃ１−ｕｃ２を整数リスト（ｃ１，ｃ２）として得た。このように、中間加算環要素は、１以上の基底要素の冪の線形結合であり、これら冪は第１及び第２加算入力整数リストから決定される。この場合、前記増加テーブルは、１以上の基底環要素（ｕ）の第１整数リストの第１整数（ａ１）−第２整数リストの第１整数（ｂ１）の冪−基底環要素（ｕ）の第１整数リストの第２整数（ａ２）−第２整数リストの第１整数（ｂ１）の冪により形成される環要素ｕａ１−ｂ１−ｕａ２−ｂ１に適用される。
【００３４】
本例において、加算出力整数リストは、中間加算整数リスト及び第２加算入力整数リストから決定される環要素に対する増加テーブルの第２の適用を介して決定することができる。このことは、中間加算環要素ｃと、負の基底要素の第２加算入力整数リストから決定される（例えば、第２加算入力整数リストの第２整数ｂ２の）冪との和の計算を含み得る。即ち、ｃ−ｕｂ２＝ｕｃ１−ｕｃ２−ｕｂ２である。これは、増加テーブルの第２の適用の前に、中間加算整数リストにより表される中間加算環要素を否定することにより達成することができる。ｃの否定は、前述したように実施することができる。一例として、並び換えを用いるが、同じ演算は指数に定数を加算することにより実施することもできる。否定の後、上記和は、正の（負の代わりに）基底要素の第２加算入力整数リストから決定される冪を用いることができる。即ち、−ｃ＋ｕｂ２＝ｕｃ２−ｕｃ１＋ｕｂ２である。後者の演算は前述したものと同じタイプのものであり、ｕｂ１を加算するのと同様の態様でテーブルの適用を介して実行することができる。この後、結果は再び否定される。完全な加算は、２つの否定及び同一の増加テーブルＴの２回のテーブル適用を用いることができる。
【００３５】
整数リスト表現における環要素から、この場合にはｃから−ｕｂ２を減算することは、時には、負の約分ステップと称される。負の約分ステップは、否定し、正の約分ステップを実行し、再び否定することにより実行することができる。
【００３６】
［乗算］  受信された第１乗算入力環要素ｒ＝ｕｒ１−ｕｒ２を符号化する第１乗算入力整数リスト（ｒ１，ｒ２）及び第２乗算入力環要素ｓ＝ｕｓ１−ｕｓ２を符号化する第２乗算入力整数リスト((ｓ１，ｓ２))を乗算するために、第１中間乗算整数リスト（ｔ１，ｔ２）及び第２中間乗算整数リスト（ｕ１，ｕ２）が決定される。乗算出力環要素を符号化する乗算出力整数リストは、第１及び第２中間要素から決定される。他の実施態様においては、３以上の中間整数リストが存在し得る。ｒ・ｓ＝(ｕｒ１−ｕｒ２)(ｕｓ１−ｕｓ２)＝ｕｒ１＋ｓ１−ｕｒ１＋ｓ２＋ｕｒ２＋ｓ２−ｕｒ２＋ｓ１＝(ｕｒ１＋ｓ１−ｕｒ１＋ｓ２)＋(ｕｒ２＋ｓ２−ｕｒ２＋ｓ１)＝ｔ＋ｕとなる。当該項の２つの項ｔ及びｕにわたる展開された積への分割は異なる態様で、例えば(ｕｒ１＋ｓ１−ｕｒ２＋ｓ１)(ｕｒ２＋ｓ２−ｕｒ１＋ｓ２)のように、実施することができる。
【００３７】
このように、整数リストとして表された２つの環要素を乗算するために、これらは、当該乗算に対する答を得るために加算することができる２つの新たな整数リストに変換することができる。加算は前述したように実施することができる。例えば、乗算ユニットは、前記中間整数リストを計算し、これらを乗算ユニットに送ることができる。
【００３８】
例えば、第１中間乗算整数リストの第１整数ｔ１は、第１乗算入力整数リストの第１整数ｒ１＋第２乗算入力整数リストの第１整数ｓ１を有することができ、第１中間乗算整数リストの第２整数ｔ２は、第１乗算入力整数リストの第１整数ｒ１＋第２乗算入力整数リストの第２整数ｓ２を有することができる（ｔ１＝ｒ１＋ｓ１，ｔ２＝ｒ１＋ｓ２）。第２中間乗算整数リストの第１整数ｕ１は、第１乗算入力整数リストの第２整数ｒ２＋第２乗算入力整数リストの第２整数ｓ２を有することができ、第２中間乗算整数リストの第２整数ｕ２は、第１乗算入力整数リストの第２整数ｒ２＋第２乗算入力整数リストの第１整数ｓ１を有することができる（ｕ１＝ｒ２＋ｓ２，ｕ２＝ｒ２＋ｓ１）。
【００３９】
算術演算が整数リストに対して実行される一実施態様において（今開示されている例において）、環要素は何らかの自然表現においては環要素として計算される必要はない。次に、複数の変形例を説明する。これらの変形例の多くは独立的なもので、例えば、符号化する変形例を、加算を実行する変形例と組み合わせることができる。
【００４０】
計算が（例えば、ｕａ１−ｂ１に対応する）整数リストで実行される難読化算術演算により、値はｕの位数のモジュロで約分され得る。例えば、ｕの位数が３０である場合、全ての計算はモジュロ３０で実行することができる。
【００４１】
図１ａは、電子生成装置の一実施態様１００を概略的に示す。電子生成装置１００は、デジタル難読化算術演算のためのパラメータを生成するように構成される。これらパラメータは、モジュラス及び基底要素を含むことができる。
【００４２】
モジュラスは、有限数の環要素を有する可換環
【数７】
0006368051.tif 000008
を定義する。基底要素（ｕ）は環要素に、各環要素が基底要素の２つの冪の間の差分（ｕａ１−ｕａ２）として表され得るように、含まれる。モジュラスのモジュロの（モジュラスを法とする）余剰が環要素である。例えば、環要素は０からモジュラス−１まで（自身を含む）の整数を表すことができる。
【００４３】
生成装置１００は、モジュラス及び基底要素を、該基底要素が所望の位数ｋ・モジュロ・モジュラスｎ（モジュラスｎを法とする位数ｋ）を有するように生成する。例えば、装置１００が所望の位数を受信するためのインターフェース（例えば、入力部）を有することができるか、又は所望の位数は当該生成装置内で予め決定することができる等である。位数は、所謂増加テーブルのサイズを決定し、従って、しばしば、暗号システムの設計者により事前に選定される重要なパラメータである。実施態様を用いて、設計者は所望の位数のための対応するモジュラス（複数のモジュラス）及び基底要素が存在するかを見付けることができる。例えば、上記インターフェースはＡＰＩ（アプリケーション・プログラミング・インターフェース）とすることができる。一実施態様において、所望の位数は素数モジュラスを選択する前に選択される。
【００４４】
生成装置１００は、素数モジュラスｐを生成するように構成された素数ユニット１１０を有する。素数モジュラスは、基底要素の所望の位数（ｋ；order(ｕ)＝ｋ）の二乗より小さい（ｋ２＞ｐ）。基底要素の２つの冪の、最大でｋ２の異なる整数リストが存在し得る。全ての環要素が斯様な態様で表されるべきである場合、（ｋ２＞ｐ）である必要がある。一方、素数は位数より大きくなくてはならない。
【００４５】
素数の生成は多数のやり方で実施することができる。例えば、ランダム数が発生され、素数性が判定される。素数性の判定は、複数の方法で、例えば試行除算、Agrawal-Kayal-Saxena素数判定法等により実施することができる。他の例として、複数の素数を一緒に発生するために、篩い分け法を用いることもできる。例えば、篩い分け法はｋ２より小さな全ての素数を発生するために使用することができる。篩い分け法は、エラトステネスの篩及び変形例（例えば、アトキンの篩）等を含む。篩い分け法は、区間[ｋ、ｋ２]のみにおいて素数を発生するように構成することができる。
【００４６】
一実施態様において、素数ユニットは素数（ｐ）を、所望の位数（ｋ）が素数−１を割り切るように発生するよう構成される（ｋ｜(ｐ−１)）。例えば、素数ユニットは、発生された素数を該条件に関して判定し、これが満たされない場合、該条件を満たすまで、新たな素数モジュラスを発生することができる。他の例として、素数ユニット１１０は、ｐ＝λｋ＋１の形態の整数を発生し、これらを素数性に関して判定することができる。このような素数は、上記条件を自動的に満たす。該条件は、サイズｋのものであるが、モジュロｐの乗法群の部分群であり（全て非零の要素）、且つ、ｐ−１要素を有する、基底要素により発生される乗法群を考察することにより真であると見ることができる。この条件の検証は、基底要素を検索することを要せずに、所望の基底要素が存在しない素数ｐを破棄することになる。垂直線（｜）は整除性を示す。
【００４７】
生成装置１００は基底要素ユニット１２０を有する。適切な素数ｐが見付かったなら、基底要素ユニット１２０は対応する基底要素を検索する。
【００４８】
基底要素ユニット１２０は、１より大きく、素数モジュラス−１（ｐ−１）より小さな可能性のある基底要素（ｕ）を選択するように構成される。基底要素ユニット１２０の該機能は、符号１２２で示されている。例えば、可能性のある基底要素はランダムに選択することができる。該可能性のある基底要素は、体系的に、例えば可能性のある基底要素２から始めて選択することもできる。
【００４９】
基底要素ユニット１２０は、上記可能性のある基底要素の異なる冪（ｕ０，ｕ１，ｕ２，ｕ３，…，ｕｋ−１）を生成するように構成される。基底要素ユニット１２０の該機能は、符号１２４により示されている。異なる冪の発生は、指数１で開始し、指数が所望の位数ｋに等しくなるまでの当該基底要素の全ての冪を生成することにより実施することができる。冪の生成は、素数モジュラスのモジュロのモジュロ演算を計算することを含む。例えば、冪を反復的に生成するために次の式：ｕｉ＋１＝ｕｉ＊ｕmodｐを使用することができる。
【００５０】
基底要素ユニット１２０は、上記可能性のある基底要素（ｕ）が所望の位数に等しい位数を有するかを判定するように構成される。基底要素ユニット１２０の該機能は符号１２６により示されている。例えば、基底要素ユニット１２０はｕｋ＝１modｐかを検証することができる。該判定は、機能１２４を用いて計算された、生成された冪を用いることができる。しかしながら、約log2(k)のモジュラ乗算において位数を一層速く計算することもできる。一実施態様において、ｕの位数が先ず計算される。例えば、該位数が所望の位数に等しい場合にのみ、基底要素の冪が生成される。後者には、約ｋのモジュラ乗算が掛かる。
【００５１】
基底要素ユニット１２０は、各環要素が前記可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するよう構成される。基底要素ユニット１２０の該機能は符号１２８により示されている。
【００５２】
例えば、機能１２８は以下のように実施することができる。素数モジュラスのモジュロの整数（素数モジュラスを法とする整数）のリストが発生される。各整数に関連して、フラグが関連付けられる。このフラグは、該フラグに関連する整数が当該可能性のある基底要素の冪の間の差分として示すことができるかを示す。最初に、全てのフラグはリセットされる。即ち、全てのフラグは、当該整数は上記可能性のある基底要素の冪の間の差分として示すことができないことを示す。
【００５３】
次に、上記可能性のある基底要素の２つの冪の間の差分が生成され、該生成された各差分に関して当該差分に関連するフラグが設定される。差分は素数モジュラスのモジュロで評価される。当該差分の生成は、当該可能性のある基底要素の発生された異なる冪からの全ての差分を発生することができる。例えば、当該基底要素ユニットは、全ての式ｕｉ−ｕｊ・モジュロ・素数モジュラスを評価することができる。
【００５４】
後者は最適化することができる。一実施態様において、当該リストは１から素数モジュラス−１の半分までの整数からなる。一実施態様において、該リストは、最大で、１から素数モジュラス−１までの整数の半分を有する。これは、整数ｘをｕｉ−ｕｊと表すことができる場合、−ｘもこの様に（即ち、ｕｊ−ｕｉと）表すことができる故に、実施することができる。
【００５５】
基底要素ユニット１２０が、各環要素を前記可能性のある基底要素の２つの冪の間の差分として表すことができると分かった場合、適切な環及び対応する基底要素が見付かっている。例えば、装置１００は計算装置を該モジュラス及び基底要素で構成することができる。
【００５６】
当該基底要素ユニットが１２８での判定に失敗した場合、新たな素数及び／又は可能性のある基底要素で再度試みることができる。例えば、装置１００は、素数及び／又は可能性のある基底要素を、少なくとも各環要素が基底要素の２つの冪の間の差分として表すことができることを肯定的に判断するまで反復して発生するように構成することができる。
【００５７】
例えば、装置１００は、２とｐ−１との間の整数のうちの、同一のモジュラスに対する前の可能性のある基底要素の冪として未だ発生されていなかった新たな可能性のある基底要素を選択することができる。全ての整数が、可能性のある基底要素として試みられたか、又は可能性のある基底要素の冪として発生された場合、新たなモジュラスを試みることができる。
【００５８】
好ましい実施態様において、装置１００は、難読化算術演算を可能にする、即ち素数のモジュロの全ての環要素が基底要素の冪の間の差分として書かれるのを可能にする、全ての素数及び当該素数のモジュロの位数ｋの基底要素を有する包括テーブルを発生する。
【００５９】
許容可能な素数のテーブルを有することは、非素数モジュラスの発生を大幅に高速化する。
【００６０】
図１ｂは、電子生成装置の一実施態様１０１を概略的に示す。図１ｂにより図示された実施態様は、図１ａにより図示された実施態様を、非素数モジュラスも発生することができるように拡張している。
【００６１】
装置１０１は、素数ユニット１１０及び基底要素ユニット１２０を有すると共に、加えて整数ユニット１３０を有している。装置１００と同様に、装置１０１はモジュラス及び基底要素を、該基底要素が所与の望ましい位数ｋを有するように生成する。例えば、装置１０１は所望の位数を受信するための入力部を有することができる。例えば、装置１０１は、１以上の特定の位数のために構成することができる。
【００６２】
整数ユニット１３０は整数モジュラス（ｎ）を、該整数モジュラスが基底要素の所望の位数（ｋ；order(ｕ)＝ｋ）の二乗より小となる如くに発生する。整数ユニット１３０は、整数モジュラス（ｎ）が少なくとも基底要素の所望の位数となる（ｎ≧ｋ）ように構成することもできる。この機能は図１ｂにおいて符号１３２により示されている。
【００６３】
整数ユニット１３０は、当該整数モジュラスの約数に対して、該約数のモジュロの各環要素が基底要素の２つの冪の間の差分として表すことができるような基底要素（ｕ）が存在することを判定するように構成される。例えば、一実施態様において、整数ユニット１３０は、前記基底要素ユニットを用いて、当該整数モジュラスの各素数約数に対して該素数約数のモジュロの各環要素が基底要素の２つの冪の間の差分として表すことができるような基底要素（ｕ）が存在することを判定するように構成される。この機能は、図１ｂでは符号１３４により示されている。この場合、第１整数が第２整数の約数であるなら、このことは第１整数が適切な約数であることを示す。
【００６４】
ｕがモジュラスｎに対する有効な基底要素である場合、ｕmodｐは、ｎの如何なる素数約数（ｐ｜ｎ）に対してもモジュロｐの有効な基底要素であることを証明することができる。従って、整数ユニット１３０が、モジュラスｎの何らかの素数約数に対して基底要素が存在しないと判定する場合、結果として、モジュロｎの基底要素も存在し得ない。事実、この論拠は１より大きく、モジュラスｎより小さな非素数約数に対しても成り立つ。
【００６５】
ｎの各素数約数が基底要素及び同質的難読化を可能にすることが確証されたら、モジュラスｎ自体が、整数モジュラス（ｎ）のモジュロの各環要素が可能性のある基底要素の２つの冪の間の差分として表すことができることを可能にするか検証することができる。この処理は、素数モジュラスｐの代わりに整数モジュラスｎを用いることを除き機能に関して述べたものと同一の手順を用いることができる。例えば、後者は、
−  １より大きく、整数モジュラス−１より小さな可能性のある基底要素（ｕ）を選択するステップ、
−  可能性のある基底要素の異なる冪（ｕ０，ｕ１，ｕ２，ｕ３，…，ｕｋ−１）を発生するステップ、
−  可能性のある基底要素（ｕ）が所望の位数を有するかを判定するステップ、そして、もし有しているなら、
−  当該整数モジュラスのモジュロの各環要素が当該可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するステップ、
を有することができる。可能性のある基底要素が後者の条件を満たさない場合、当該整数モジュラスの全てのモジュロが試行されてしまうか又は全てが試行され若しくは可能性のある基底要素の冪として発生されてしまうまで、新たな可能性のある基底要素を選択することができる。
【００６６】
このように、装置の一実施態様１０１においては、素数モジュラスが発生されるのみならず、非素数整数モジュラスも発生される。装置１０１は装置１００をｎの素数約数のために使用することができる。
【００６７】
装置１００又は１０１の一実施態様において、素数ユニット１１０は、所望の位数の二乗（ｋ２）より小さな素数（ｐ）を発生すると共に、基底要素ユニットを用いて各環要素が可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するように構成される。位数ｋの基底要素を用いて同質的難読化を可能にする素数が利用可能なテーブルを有することは、位数ｋの基底要素を用いて同質的難読化を可能にする整数モジュラスの検索を大幅に高速化する。
【００６８】
位数ｋの基底要素を用いて同質的難読化可能にする整数モジュラスを発生するための篩い分け方法を用いる一実施態様は、以下の通りである。
−  素数ユニット１１０及び基底要素ユニット１２０は、位数ｋの基底要素を用いて同質的難読化を可能にするｋより大きな最小の素数ｐ１を発生する。
−  整数ユニット１３０は、各々が関連するフラグを伴う、ｋ２より小さい、ｐ１以上の整数のリストを発生する。フラグは、最初は、位数ｋの基底要素を用いて同質的難読化を可能にすることができることを示すように設定される。リスト内にｐ１より大きな最小の整数に対するインデックスを設定する。
−  ｐ１より小さな素数を発生し、上記リスト上の該小さな素数の倍数である整数に関連するフラグをリセットする。
−  （Ａ）  フラグが設定されたインデックス以上のインデックスを持つ当該リスト上の最小の整数ｍを決定する。例えば、機能１３６を用いて、モジュラスとされた整数ｍが位数ｋに対して同質的難読化を可能にするかを判定する。
−  ノーの場合、ｍに関連するフラグをリセットし、ｍの倍数である当該リスト上の整数の全てのフラグをリセットする。
−  インデックスを増加させる。インデックスが依然として当該リスト内を指す場合、（Ａ）で継続する。
【００６９】
適切なモジュラス及び基底要素が見付かったなら、電子生成装置１００又は１０１は、可換環
【数８】
0006368051.tif 000009
において例えばオプションのテーブル生成ユニット１４０を用いて難読化算術演算を実行するための計算装置で使用する増加テーブルを計算することができる。
【００７０】
上記テーブル生成ユニットは増加テーブルを構築するように構成される。例えば、該テーブル生成ユニット１４０は、
入力環要素、例えば当該モジュラスのモジュロの剰余類を反復的に選択し、
入力環要素の環加算された増加環要素に等しい出力環要素を決定し、
出力環要素を符号化する出力整数リストを決定し、
入力環要素を出力整数リストにマッピングするエントリを増加テーブルに追加する、
ように構成することができる。
【００７１】
テーブル構築に関する更なる詳細は、前述した以前の出願に示されている。
【００７２】
生成装置１００又は１０１は、例えば位数ｋに対し同質的難読化を可能にする幾つかの若しくは全ての素数及び／又は全整数を与える総合テーブル等の（これは必須ではない）、テーブルを生成するように構成することができる。代わりに、生成装置１００又は１０１は、各環要素が基底要素の２つの冪の間の差分として表すことができるかについて肯定的に判定するまで、モジュラス及び／又は可能性のある基底要素を反復的に発生するように構成することもできる。
【００７３】
典型的に、装置１００及び１０１は、各々、該装置１００及び１０１に記憶された適切なソフトウェアを実行するマイクロプロセッサ（図示略）を有する。例えば、該ソフトウェアはダウンロードされ、及び／又は例えばＲＡＭ等の揮発性メモリ又はフラッシュ等の不揮発性メモリのような対応するメモリに記憶される。代わりに、装置１００及び１０１は、全体として又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジックで実施化することもできる。また、装置１００及び１０１は、全体として又は部分的に、所謂、特定用途向け集積回路（ＡＳＩＣ）、即ち特定の使用のためにカスタマイズされた集積回路（ＩＣ）として実施化することもできる。
【００７４】
機能１２２、１２４、１２６、１２８、１３２、１３４及び１３６は、対応する機能ユニットとして実施化することができる。
【００７５】
一実施態様において、当該電子生成装置は、素数回路、基底要素回路及び、オプションとして、整数回路を有する。該電子生成装置は前記機能ユニットに対応する機能回路を有することができる。これら回路はユニットの対応する機能のために構成される。これら回路はプロセッサ回路及び記憶回路とすることができ、該プロセッサ回路は該記憶回路において電子的に表される命令を実行する。これら回路は、ＦＰＧＡ又はＡＳＩＣ等とすることもできる。
【００７６】
電子生成装置はデジタル難読化算術演算のためのパラメータを生成するように構成され、これらパラメータは有限数の環要素を有する可換環を定義し、これら環要素には基底要素が、各環要素が当該基底要素の２つの冪の間の差分として表すことができるように含まれ、該電子生成装置は、前記基底要素の所望の位数の二乗より小さなモジュラスを発生し、１より大きく前記モジュラス−１より小さい可能性のある基底要素を選択し、該可能性のある基底要素の異なる冪を発生し、該可能性のある基底要素が所望の位数に等しい位数を有するかを判定し、もしそうなら、各環要素が該可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定する。
【００７７】
図２は、電子生成方法の一実施態様２００を概略的に示す。電子生成方法２００はデジタル難読化算術演算のためのパラメータを生成するように構成される。これらパラメータは、有限数の環要素を有する可換環を定義する。これら環要素には基底要素（ｕ）が、各環要素が当該基底要素の２つの冪の間の差分として表すことができるように含まれる。
【００７８】
生成方法２００は、
−  素数モジュラス（ｐ）を、該素数モジュラスが基底要素の所望の位数（ｋ；order(ｕ)＝ｋ）の二乗より小であるように発生するステップ２１０、
−  所望の位数（ｋ）が素数−１を割り切る（ｋ｜(ｐ−１)）ことを検証するステップ２２０、
−  １より大きく、モジュラス−１より小さな可能性のある基底要素（ｕ）を選択するステップ２３０、
−  可能性のある基底要素の異なる冪（ｕ０，ｕ１，ｕ２，ｕ３，…，ｕｋ−１）を発生するステップ２４０、
−  可能性のある基底要素（ｕ）が所望の位数に等しい位数を有するかを判定するステップ２５０、もしそうなら、
−  各環要素が当該可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するステップ２６０、
を有する。
【００７９】
モジュラス及び基底要素が見付かったなら、方法２００は、各環要素が当該可能性のある基底要素の２つの冪の間の差分として表すことができると判定された場合、当該素数及び基底要素を含むパラメータを発生することができる（ステップ２７０）。
【００８０】
方法２００は、少なくとも各環要素が基底要素の２つの冪の間の差分として表すことができるかについて肯定的に判定するまで、素数及び／又は可能性のある基底要素を反復的に発生する。このことは、図２では、当該フローチャートにおいて戻る方向の矢印により示されている。例えば、２２０、２５０又は２６０における判定が失敗した場合、該方法は当該発生を、例えば素数モジュラスの発生又は基底要素の選択における検索を続行することができる。
【００８１】
図３は、各環要素が可能性のある基底要素の２つの冪の間の差分として表すことができるかを検証する電子的方法の一実施態様３００を概略的に示す。該方法は、整数モジュラスのモジュロの（特には、素数モジュラスのモジュロの）環要素に対して使用することができる。
【００８２】
方法３００は、
−  整数のリスト及び関連するフラグを発生するステップ３１０、
−  当該可能性のある基底要素の２つの冪の間の差分を発生すると共に、これら差分に関連するフラグを設定するステップ３２０、及び
−  当該リストの整数に関連する全てのフラグが設定されたら、各環要素は当該可能性のある基底要素の２つの冪の間の差分として表すことができると判定するステップ３３０，
を有する。
【００８３】
図４は、電子生成方法の一実施態様４００を概略的に示す。方法４００は、
−  整数モジュラス（ｎ）を、該モジュラスが当該基底要素の所望の位数（ｋ；order(ｕ)＝ｋ）の二乗より小である（ｋ２＞ｎ）ように発生するステップ４１０、
−  前記基底要素ユニットを用いて、前記モジュラスの各素数約数に対し、当該素数約数のモジュロの各環要素が基底要素の２つの冪の間の差分として表すことができるような基底要素（ｕ）が存在することを判定するステップ４２０、及び
−  前記整数モジュラス（ｎ）のモジュロの各環要素が当該可能性のある基底要素の２つの冪の間の差分として表すことができるかを判定するステップ４３０、
を有する。
【００８４】
当業者にとり明らかなように、当該方法を実行する多数の異なる態様が可能である。例えば、上記ステップの順序は変更することができるか、又は幾つかのステップは並列に実行することができる。更に、ステップの間には他の方法のステップを挿入することができる。挿入されたステップは、本明細書に記載されたような方法の改良を表すことができるか、又は該方法とは無関係とすることができる。例えば、ステップ２４０及び２６０は少なくとも部分的に並行して実行することができる。例えば、ステップ２５０はステップ２４０より前に実行することができる。更に、所与のステップは、次のステップが開始される前に完全に完了していなくてもよい。
【００８５】
一実施態様による方法は、プロセッサシステムに方法２００、３００又は４００を実行させるための命令を含むソフトウェアを用いて実行することができる。ソフトウェアは、当該システムの特定の部分主体によりなされるステップのみを含むことができる。ソフトウェアは、ハードディスク、フロッピーディスク、メモリ等の適切な記憶媒体に記憶することができる。ソフトウェアは、有線若しくは無線を介する信号として、又は例えばインターネット等のデータネットワークを用いて伝送することができる。ソフトウェアは、ダウンロードのため、及び／又はサーバ上での遠隔使用のために利用可能とすることができる。方法は、該方法を実行するための、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジックを構成するビットストリームを用いて実行することができる。
【００８６】
一実施態様は、一実施態様を実施させるように構成されたコンピュータプログラム（特に、担体上又は内のコンピュータプログラム）にも拡張するものであることが理解されよう。該プログラムは、ソースコード、オブジェクトコード若しくは部分的にコンパイルされた形等のソース及びオブジェクトコードの中間のコードの形態、又は一実施態様による当該方法の実施に使用するのに適した何らかの他の形態とすることができる。コンピュータプログラム製品に関連する一実施態様は、前述した方法のうちの少なくとも１つにおける処理ステップの各々に対応するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに分割することができ、及び／又は静的に若しくは動的にリンクすることが可能な１以上のファイルに記憶することができる。コンピュータプログラム製品に関連する他の実施態様は、前述したシステム及び／又は製品のうちの少なくとも１つにおける手段の各々に対応するコンピュータ実行可能な命令を有する。
【００８７】
図５ａは、コンピュータプログラム１０２０を有する書き込み可能部分を備えたコンピュータ読取可能な媒体１０００を示し、該コンピュータプログラム１０２０はプロセッサシステムに一実施態様によるデジタル難読化算術演算のためのパラメータを生成する方法を実行させる命令を有している。コンピュータプログラム１０２０は、コンピュータ読取可能な媒体１０００上に、物理的マークとして又は該コンピュータ読取可能な媒体１０００の磁化により具現化することができる。しかしながら、如何なる他の好適な実施態様も同様に想定することができる。更に、ここではコンピュータ読取可能な媒体１０００は光ディスクとして示されているが、該コンピュータ読取可能な媒体１０００は、ハードディスク、固体メモリ、フラッシュメモリ等の任意の好適なコンピュータ読取可能な媒体とすることができると共に、非記録可能な又は記録可能なものとすることもできることが理解されるであろう。コンピュータプログラム１０２０は、プロセッサシステムに前記方法を実行させる命令を有する。
【００８８】
図５ｂは、一実施態様によるプロセッサシステム１１４０の概略図を示す。該プロセッサシステムは、１以上の集積回路１１１０を有する。該１以上の集積回路１１１０のアーキテクチャは図５ｂに概略的に示されている。回路１１１０は、一実施態様による方法を実施する及び／又はモジュール若しくはユニットを実施化するためのコンピュータプログラム要素を実行する処理ユニット（例えば、ＣＰＵ）１１２０を有している。回路１１１０は、プログラムコード、データ等を記憶するためのメモリ１１２２も有している。メモリ１１２２の一部は読み出し専用とすることができる。回路１１１０は、アンテナ、コネクタ又は両者等の通信エレメント１１２６を有することもできる。回路１１１０は、当該方法において定義される処理の一部又は全てを実行するための専用の集積回路１１２４も有することができる。プロセッサ１１２０、メモリ１１２２、専用のＩＣ１１２４及び通信エレメント１１２６は相互接続部（即ち、バス）１１３０を介して互いに接続することができる。該プロセッサシステム１１４０は、コネクタ及び／又はアンテナを用いて、各々、接触及び／又は非接触通信用に構成することができる。
【００８９】
尚、上述した実施態様は本発明を限定するというよりは解説するものであり、当業者であれば、多数の代替実施態様を設計することができることに注意すべきである。
【００９０】
また、請求項において、括弧内に記載された如何なる符号も、当該請求項を限定するものと見なしてはならない。“有する”なる動詞及びその活用形の使用は、請求項に記載されたもの以外の要素又はステップの存在を排除するものではない。単数形のエレメントは、複数の斯様なエレメントの存在を排除するものではない。本発明は、幾つかの個別のエレメントを有するハードウェアにより、及び適切にプログラムされたコンピュータにより実施することができる。幾つかの手段を列挙する装置の請求項において、これら手段の幾つかは１つの同一のハードウェア品目により具現化することができる。特定の手段が相互に異なる従属請求項に記載されているという単なる事実は、これら手段の組み合わせを有利に使用することができないということを示すものではない。
【００９１】
請求項において、括弧内の符号は実施態様の図面における符号又は実施態様の式を指し、請求項の理解度を増加させるものである。これらの符号は、当該請求項を限定するものと見なしてはならない。
【図１ａ】
0006368051.tif 000012
【図１ｂ】
0006368051.tif 000013
【図２】
0006368051.tif 000014
【図３】
0006368051.tif 000015
【図４】
0006368051.tif 000016
【図５ａ】
0006368051.tif 000017
【図５ｂ】
0006368051.tif 000018