(57)【特許請求の範囲】
【請求項１】
剰余数系（ＲＮＳ）で表わされた(y1,y2,…,yk)の入力数yを基数表現で表される出力数(e0,e1,…,es-1)に変換する電子計算装置であって、該計算装置は、
前記剰余数系で表された入力数yを入力する入力インターフェースと、
前記剰余数系で表された中間数y^を反復して更新するプロセッサ回路であって、これら反復が前記基数表現の基数(b0,b1,…,bs-1)に関する該基数表現のディジット(e0,e1,…,es-1)を生成するプロセッサ回路と、
を有し、
少なくとも１つの反復が、
前記基数表現の基数btによる中間数のモジュロを計算して該基数表現のディジットetを得るステップと、
前記中間数y^を、該中間数から前記ディジットを減算し、難読化数(F;Ft)を加算し、且つ、前記基数btにより除算することにより更新するステップと、
を有し、
前記難読化数(F;Ft)が、前記基数表現の前記反復において使用される基数(b0,b1,…,bs-1)のうちの１以上の積の倍数である、計算装置。
【請求項２】
前記基数の全てが等しい、請求項１に記載の計算装置。
【請求項３】
前記基数表現の基数btによる中間数のモジュロを計算するステップが、ゼロ以上で前記基数表現の基数btの所定の倍数より小さいディジットetを生成する、請求項１又は請求項２に記載の計算装置。
【請求項４】
前記基数表現の基数btによる中間数のモジュロを計算するステップが、ゼロ以上で前記基数表現の基数btより小さいディジットetを生成する、請求項３に記載の計算装置。
【請求項５】
前記ディジットetの少なくとも１つが、ゼロ未満又は前記基数表現の基数btより大きい若しくは該基数btに等しい、請求項１又は請求項２に記載の計算装置。
【請求項６】
前記プロセッサ回路が、
前記入力数ｙと前記基数表現の基数(b0,b1,…,bs-1)に関する該基数表現のディジット(e0,e1,…,es-1)により表される数との間の差を示す補正項εs-1を計算する、
請求項１ないし５の何れか一項に記載の計算装置。
【請求項７】
前記補正項が最後のディジットes-1と基数bs-1による前記中間数y^(s-1)のモジュロとの間の差であり、前記モジュロの演算は少なくともゼロで前記基数bs-1より小さい結果を生じ、オプションとして、前記差が前記基数bs-1により除算される、請求項６に記載の計算装置。
【請求項８】
前記基数の少なくとも１つが前記剰余数系のモジュラスである、請求項１ないし７の何れか一項に記載の計算装置。
【請求項９】
前記入力数ｙ及び／若しくは前記中間数y^は、前記剰余数系において、該剰余数系のモジュラスの系列による剰余の系列のモジュロとして表され、前記系列における剰余が当該計算装置のメモリに符号化された形態で記憶され、及び／又は
前記基数表現のディジット（e0,e1,…,es-1）が当該計算装置のメモリに符号化された形態で記憶される、請求項１ないし８の何れか一項に記載の計算装置。
【請求項１０】
前記プロセッサ回路は剰余数系表現の複数の数に対し計算して結果的数を剰余数系表現で生成し、該結果的数は前記入力数として基数表現に変換され、前記難読化数(F;Ft)における前記倍数は剰余数系表現の前記複数の数の１つ以上に依存する、請求項１に記載の計算装置。
【請求項１１】
前記プロセッサ回路が、前記出力数を被乗数の１つとしてディジットベースのモンゴメリ乗算を実行する、請求項１ないし１０の何れか一項に記載の計算装置。
【請求項１２】
第１反復の開始時における前記中間数y^が前記入力数ｙである、請求項１ないし１１の何れか一項に記載の計算装置。
【請求項１３】
前記出力数は、基数b0,b1,…,bs-1及びオプションとして補正項εs-1に関するディジットe0,e1,…,es-1により表され、従って、y=e0+e1b0+…+es-1b0…bs-1-εs-1b0…bs-1となる、請求項１ないし１２の何れか一項に記載の計算装置。
【請求項１４】
前記剰余数系は少なくとも１つの冗長モジュラスm0を有する冗長剰余数系であり、該冗長モジュラスm0に関する前記中間数y^の更新が、前記冗長モジュラスに関する剰余がゼロ以上で該冗長モジュラスより小さくなるようなものとされる、請求項１ないし１３の何れか一項に記載の計算装置。
【請求項１５】
剰余数系（ＲＮＳ）で表わされた(y1,y2,…,yk)の入力数yを基数表現で表される出力数(e0,e1,…,es-1)に変換する電子計算装置の作動方法であって、
前記電子計算装置のプロセッサが、前記剰余数系で表された前記入力数yを入力するステップと、
前記プロセッサが、前記剰余数系で表された中間数y^を反復して更新するステップであって、これら反復が前記基数表現の基数(b0,b1,…,bs-1)に関する該基数表現のディジット(e0,e1,…,es-1)を生成するステップを有するステップと、を有し、
少なくとも１つの反復が、
前記プロセッサが、前記基数表現の基数btによる中間数のモジュロを計算して該基数表現のディジットetを得るステップと、
前記プロセッサが、前記中間数y^を、該中間数から前記ディジットを減算し、難読化数(F;Ft)を加算し、且つ、前記基数btにより除算することにより更新するステップと、を有し、
前記難読化数(F;Ft)が、前記基数表現の前記反復において使用される基数(b0,b1,…,bs-1)のうちの１以上の積の倍数である、電子計算装置の作動方法。
【請求項１６】
電子計算装置のプロセッサに請求項１５に記載の方法を実行させるための命令を表す一時的又は非一時的データを有する、コンピュータ読取可能な媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、電子計算装置、電子計算方法及びコンピュータ読取可能な媒体に関する。
【背景技術】
【０００２】
秘密計算（セキュア計算）、特にホワイトボックス暗号法において、数は、しばしば、剰余数系（ＲＮＳ）表現で符号化される。剰余数系（ＲＮＳ）において、モジュラスｍは互いに素な一層小さいモジュラスmiの積m=m1・・・mkであり、整数ｙ∈[0,m)は、これらの剰余のリスト(y1,…,yk)により固有に表され、ここで、yi=|y|mi∈[0,mi)は全てのｉに対してy≡yi mod miを満足する。
【０００３】
ＲＮＳ表現は、ＲＮＳ表現数に対する算術を、しばしば、ＲＮＳディジットに対して別個に実行することができる故に有利である。例えば、ＲＮＳ表現の数に加算又は乗算するためには、対応するモジュラスによる（を法とする）対応する要素のモジュロを加算又は乗算するだけで十分である。このようにして、桁上げ（キャリー）の問題は大部分消滅する。特に、ホワイトボックス暗号法においてＲＮＳ表現は有利である。ホワイトボックスにおいて、計算は符号化されたデータに対して当該計算の結果を表すテーブルを用いて実行される。ホワイトボックスにおいてさえ、キャリーを正しく考慮に入れることは可能であるが、ＲＮＳを使用することは計算を大幅に簡素化することができる。更に、キャリーの有無は隠蔽することが困難であり、ホワイトボックス装置が攻撃され得るサイドチャンネルとなり得る（例えば、ブロック暗号等の秘密キーに依存する暗号アルゴリズムのホワイトボックス装置）。
【０００４】
それにも拘わらず、数を基数表現で表すことが時には必要とされる。最も基本的なタイプの基数表現は、或る整数ｂに対してｂ進（b-ary）表現とも称される。正の整数ｂが与えられたとして、整数ｙ∈[0,bs)のｂ進表現は、全てのｉに対してｂ進（整数）ディジットdi∈[0,b)として、ｙをy=d0+d1b+…+ds-1bs-1の形で書く。例えば、整数は或る結果（例えば、計算の出力）を表すことができる。該結果は、例えば数をＲＮＳ表現で見ることに慣れていないユーザにレポートされねばならないかも知れない。該結果は、ＲＮＳ数を予期していない或るアルゴリズムにより更に処理されねばならない可能性がある。例えば、該結果は、恐らくは非安全な手順で更にレンダリングされ、又は更に処理されねばならない。例えば、モンゴメリ乗算等のディジットベースのアルゴリズムは、入力として基数表現を必要とする。
【０００５】
発明者は、ＲＮＳ表現を基数表現に変換するための既知のアルゴリズムは、セキュア計算に対し、特にホワイトボックス計算に対しては良好に変換を行わないことを認識した。ホワイトボックス計算においては、ＲＮＳ／基数変換の間においても、当該ソフトウェアは該ソフトウェアを保護するために使用される符号化についての情報を漏らしてはならない。しかしながら、以下に詳細に説明されるように、このことは当てはまらない。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
発明者は、ＲＮＳ表現数の基数表現への変換の間において中間値の幾つかは益々小さくなる傾向があることを認識した。従って、このことは当該系において小さな数が符号化される方法に関する情報を漏洩する機会を有することになる。攻撃者に符号化についての情報を得る機会を与えることは望ましくないと考えられる。このような情報は、当該系の他の部分に対する攻撃に活用され得る。
【課題を解決するための手段】
【０００７】
請求項に記載されるような、剰余数系（ＲＮＳ）で表された入力数を基数表現で表される出力数に変換するように構成された電子計算装置が提供される。中間数の更新の間に追加される難読化が、該中間数の減少に対抗する。このように、攻撃者は中間数を観察することにより小さな数についての情報を得ることはできない。
【０００８】
当該変換の可能性のあるアプリケーションは、ＲＮＳで実行された早期の計算の結果を例えばユーザにレポートすること、或る種の電子レポートにおけるもの、又は結果をレンダリングすることである。変換は、ディジットベースのアルゴリズム一部としても必要とされ得る。該アルゴリズムは完全に擬似剰余で動作することができるからである。ＲＮＳシステムは、例えばデジタル信号処理及び暗号法において広く使用されている。当該方法は、ホワイトボックスアプリケーションで使用されるのに良く適している。該方法は、小さなデータ要素でのみ動作することができ、従って全算術をテーブルのルックアップにより実行することができる。
【０００９】
本発明による方法は、コンピュータ上でコンピュータ実施化方法として、専用のハードウェアで、又は両者の組み合わせで実施化することができる。本発明による方法のための実行可能なコードは、コンピュータプログラム製品上に記憶することができる。コンピュータプログラム製品の例は、メモリ装置、光記憶装置、集積回路、サーバ、オンラインソフトウェア等を含む。好ましくは、当該コンピュータプログラム製品は、該コンピュータプログラム製品がコンピュータ上で実行された場合に本発明による方法を実行するためのコンピュータ読取可能な媒体上に記憶された非一時的プログラムコードを有する。
【００１０】
好ましい実施態様において、当該コンピュータプログラムは、該コンピュータプログラムがコンピュータ上で実行された場合に本発明による方法の全ステップを実行するように構成されたコンピュータプログラムコードを有する。好ましくは、該コンピュータプログラムはコンピュータ読取可能な記憶媒体上で具現化される。
【００１１】
本発明の他の態様は、上記コンピュータプログラムをダウンロードするために利用可能にする方法を提供する。この態様は、前記コンピュータプログラムが例えばアップルのアップルストア、グーグルのプレイストア又はマイクロソフトのウインドウズストアにアップロードされる場合、及び前記コンピュータプログラムが斯様なストアからダウンロードするために利用可能となる場合に用いられる。
【００１２】
本発明の他の詳細、態様及び実施態様は、図面を参照して例示のみとして説明されるであろう。各図における要素は、簡略化及び明瞭化のために図示され、必ずしも実寸通りには描かれていない。また、各図において、既に記載された要素に対応する要素は同一の符号を有し得る。
【図面の簡単な説明】
【００１３】
【図１】図１は、計算装置及びコンピュータ装置の実施態様の一例を概略的に示す。
【図２】図２は、計算装置の実施態様の一例を概略的に示す。
【図３】図３は、計算方法の実施態様の一例を概略的に示す。
【図４ａ】図４ａは、一実施態様によるコンピュータプログラムを有する書込可能部分を備えたコンピュータ読取可能な媒体を概略的に示す。
【図４ｂ】図４ｂは、一実施態様によるプロセッサシステムの図を概略的に示す。
【発明を実施するための形態】
【００１４】
本発明は多くの異なる形態の実施態様により影響を受け得るが、本開示は本発明の原理の例示として見なされるべきであり、本発明を図示及び記載される特定の実施態様に限定することを意図するものでないとの理解で、図面及び本明細書には１以上の特定の実施態様が図示及び記載される。
【００１５】
以下においては、理解のために、実施態様の要素は動作中において記載される。しかしながら、各要素は、これら要素により実行されると記載される機能を実行するように構成されることは明らかであろう。
【００１６】
更に、本発明は実施態様に限定されるものではなく、本発明は本明細書に記載され又は互いに異なる従属請求項に記載される各及び全ての新規なフィーチャ又はフィーチャの組み合わせに存するものである。
【００１７】
整数は、多数の異なる態様で表すことができる。この出願は、基数表現（radix representation）及び剰余数系表現（ＲＮＳ：residue number system representation）に関するものである。
【００１８】
基数表現には多数の種類がある。最も基本的なタイプの基数表現は、或る整数ｂに対してｂ進（b-ary）表現とも称される。正の整数ｂが与えられたとして、整数ｙ∈[0,bs)のｂ進表現は、全ｉに対してｂ進（整数）ディジットdi∈[0,b)として、ｙをy=d0+d1b+…+ds-1bs-1の形で書く。もっと一般的には、数b0,…,bs-1が与えられたとして、混合基数（ＭＲ）表現は、全ｉに対して整数ＭＲディジットdi∈[0,bi)として、或る整数ｑに対しｙをy=d0+d1b0+…+ds-1b0…bs-2+qb0…bs-1の形で書く。幾つかの応用例においては、補正項ｑを許容することができる。ｙが十分に小さい場合、補正項は必要とされない。
【００１９】
発明者は、混合基数表現でさえ更に一般化することができると認識した。一般化された混合基数表現（ＧＭＲ）において、数はy=e0+e1b0+…+es-1b0…bs-2-εs-1b0…bs-1=e-εs-1b0…bs-1と表される。前記混合基数表現との相違は、ディジットeiが区間[0,bi)から選択されることを要せず、biを法とする擬似残差のモジュロ、（擬似残差 mod bi）であることが許容される。整数ｐは、或る予め定められた整数φに対してｐ＝x mod m及び０≦ｐ＜φｍである場合、整数ｘ mod mの擬似残差である。整数φは、拡張限界と称され、擬似残差の成長を制限する。φ＝１なら、当該擬似残差は通常の残差である。
【００２０】
例えば、-φm＜ｐ＜φmとなることを単に要求することにより、擬似残差に対する制限を更に緩めることができる。提示の便宜上、このような緩められた仮定は行わないが、以下の説明は、より少ない制限的限界を考慮に入れるように容易に適応化することができると理解される。
【００２１】
φ＞１の場合、一般化されたＭＲ表現においてディジットには２度以上の選択が存在する。結果として、一般化されたＭＲ表現における表現は典型的に唯一ではない。発明者は、ＭＲ表現が入力として採用される多くの応用例においては、しばしば一般化されたＭＲ表現も使用することができることに想到した。このことは、一般化されたＭＲ表現を計算することは、一層効率的に且つ一層良好な難読化オプションを伴って実行することができるので有利である。例えば、ＭＲ表現がディジットベースのモンゴメリ乗算アルゴリズムのための入力として用いられる場合、一般化ＭＲ表現を用いることができる。もっとも、後の実施態様においてφ＝１と設定することにより、通常のＭＲ表現を得ることができる。後の実施態様において全てのｉに対してbi=b及びφ=1と設定することにより、ｂ進表現が得られる。
【００２２】
剰余数系（ＲＮＳ）において、モジュラスｍは互いに素な一層小さいモジュラスmiの積m=m1・・・mkであり、整数ｙ∈[0,m)は、これらの剰余のリスト(y1,…,yk)により固有に表され、ここで、yi=|y|mi∈[0,mi)は全てのｉに対してy≡yi mod miを満足する。このような剰余による表現は、ＲＮＳ表現と呼ばれる。該表現は、yi=<y>miのみが擬似残差であると仮定される場合、即ち、yi≡y mod miのみが成り立ち、必ずしも０≦yi＜miによるものでない場合、ｙを依然として固有に決定する。
【００２３】
変換は、ＲＮＳ表現の数を基数型表現に変換する処理である。セキュアな適応例においては、典型的に大きな整数のｂ進ディジット（又はＭＲディジット）及びその擬似残差の両方が、符号化された形態で（例えば、恐らくは状態による符号化により複数の表現で）与えられ、変換は、これらのディジットに関する如何なる情報も漏らさずに実行されねばならない。従来のアルゴリズムは、典型的に、ＭＲディジットを決定するためにbiを法とするモジュール式算術モジュロの形態を用いる。ホワイトボックスについての更なる情報に関しては、Chow他による文献“A White-Box DES Implementation for DRM Applications”を参照されたい。ホワイトボックスについての、特に状態を用いる符号化についての更なる情報に関しては、国際特許出願公開第2014/096117号で公開された出願“Computing device configured with a table network”を参照されたい。また、コンピュータプログラムを如何にしてホワイトボックス形態で表すかについての情報に関しては、国際特許出願公開第2014/095772号で公開された“Computing device comprising a table network”を参照されたい。
【００２４】
実施態様において、変換は、例えば擬似ＲＮＳ表現から擬似残差のみを用いてセキュアな実施化に適したやり方で計算される。実施態様は、モジュール式算術モジュロbiを用いるが、幾つかの実施態様は正確な残差は必要とせず、代わりに、擬似残差を必要とすることに注意されたい。実施態様は、従来の変換に固有の情報の漏れを防止する。更に、当該アルゴリズムは完全に擬似残差で動作することができるので、我々の変換アルゴリズムから得られる表現は、ＲＮＳで実施化される場合、ディジットベースのアルゴリズムにも使用することができる。
【００２５】
一実施態様において、当該システムはホワイトボックス暗号法を用いて実施化される。データは、恐らくは状態と一緒に、符号化された形態で表される。状態は、当該符号化が固有とならないように冗長変数である。例えば、（恐らくは非常に大きい）整数ｙは、その剰余のリスト（y1,…,yk）により符号化された形態で表すことができる。即ち、全ての剰余yiは
【数１】
0006670421.tif 000002
の形で与えられ、ここで、siは状態変数であり、Eは何らかの関数（典型的に、データ状態空間における順列）である。符号化された変数に対する演算は、典型的に、ルックアップテーブルを用いて実行される。大きな演算は、必要なら、一層小さな演算に分解される。結果として、当該計算は、複数のルックアップテーブルを有するテーブルネットワークの形をとることができる。幾つかのテーブルは、入力として、当該アルゴリズムに対する入力の一部、例えば変換される数をとる。幾つかのテーブルは、入力として、１以上の他のテーブルの出力をとる。幾つかのテーブルは、出力の一部を生成する。例えば、必要とされる算術のモジュロmiは、典型的に、少なくともmiが相対的に小さいなら、或る形態のルックアップテーブルにより実施される。
【００２６】
ホワイトボックスにおける変換の間において、整数のＭＲディジットは符号化された剰余から符号化された形態で得られねばならない。従来のＲＮＳ／ＭＲ変換アルゴリズムは、特にホワイトボックス構成の前後関係において種々の欠点を有する。
【００２７】
例えば、中国の余剰定理（ＣＲＴ）に基づく変換方法は、非常に大きな整数による直接計算を含み、従って或る形態のキャリー付加算アルゴリズムを含む。このような方法は、キャリーが符号化された形態でも恐らくは情報を漏洩する故に、ホワイトボックス用途においては余り適していない。ホワイトボックスは、相対的に小さな（符号化された）データ（即ち；大きな整数は（符号化された）ディジットのリストにより表される）により計算を実行する方法を好む。例えば、該符号化されたデータは略バイトのサイズとすることができる。
【００２８】
剰余数系（ＲＮＳ）において、整数ｙは、複数のモジュラスm1,…,mkによる剰余のリスト（y1=|y|n1,…,yk=|y|mk）のモジュロにより表される。従来、モジュラスm1,…,mkは対状素数として選択される。その場合、m=m1…mkと書けば、中国の余剰定理（ＣＲＴ）は０≦ｙ＜ｍの全ての整数ｙをモジュラススm1,…,mkによる剰余のリスト（y1,…,yk）のモジュロから固有に復元することができることを保証する。しかしながら、発明者は、このような条件は便利であるが厳密には必要とされないことを理解した。ＲＮＳは、モジュラスが全て互いに素であるように選択されなくても動作する。この場合、ｍはモジュラススm1,…,mkの最小公倍数とすることができ、依然として、０≦ｙ＜ｍの整数ｙを当該モジュラスによる剰余のモジュロから固有に復元することができる。
【００２９】
以下の説明では、更に当該モジュラスは互いに素であると仮定する（このことは、当該提示を理解するのを容易にする）。しかしながら、以下の実施態様は、例えば、これらが１より大きい共通の約数を有する少なくとも２つのモジュラスmi及びmjである場合、全てのモジュラスが互いに素ではないケースに適合させることができる。
【００３０】
m=m1…mkとし、且つ、当該モジュラスが全て対状に素であると仮定して、説明を続ける。中国の残余定理（ＣＲＴ）を用いると、０≦ｙ＜ｍの整数ｙは、その剰余のリスト（y1,…,yk）から、或る整数ｑに関して、
【数２】
0006670421.tif 000003
なる事実に基づいて固有に復元することができる。応用例においては、しばしば、ｙを剰余のリスト（y1,…,yk）から高速で復元することができることが要求される。ＭＲ変換に基づく方法は、０≦ｙ＜ｍの所与の整数ｙを混合基数形態に、０≦d1＜b1の整数値のｂ進ディジットd0,ds-1及び整数ｑに関して、
【数３】
0006670421.tif 000004
と書くよう試み、ここで、全てのｉに関してBi=b0…bi-1（及びB0=1）並びにB=Bs=b0…bs-1である。このような表現は、混合基数（ＭＲ）表現と称される。典型的な例は、b0=b1=…=bs-1=bとなるケースであり、ｂ進表現を提供する。
【００３１】
難読化数を追加するフィーチャを有さないＲＮＳにおける変換のための下記の基準方法を考察しよう。動的範囲m=m1…mkを持つモジュラスm1,…,mkに基づくＲＮＳが与えられたとして、整数ｙ∈[0,m)をＲＮＳから基数に変換するために、以下のように進行する。
１．y(0)=yと設定する。
２．t=0,…,s-1に対して、
（ａ）dt=|y(t)|bt；
（ｂ）y(t+1)=(y(t)-dt)/bt（整除）
を計算する。
【００３２】
かくして、全てのｔに対してy(t)=dt+dt+1bt+…+ds-1bt…bs-2となり、特に、ディジットdt∈[0,bt)に対しy=y(0)=d0+d1b0+…+ds-1b0…bs-2となる。y(t+1)に関するＲＮＳ表現(yt+1,1,…,yt+1,k)を、bt及びmiが互いに素なら、
【数４】
0006670421.tif 000005
であることを用いることによりy(t)のＲＮＳ表現(yt,1,…,yt,k)から計算することができ、もしそうでないなら、新たな剰余を決定するために、例えば基数拡張、例えば、混合基数変換を採用する方法（Garnerの文献The Residue Number System, Ire Transactions On Electronic Computers, June 1959, pp 140-147参照）又は冗長モジュラスを使用する方法（A.P. Shenoy及びR Kumaresanの文献Fast base extension using a redundant modulus in RNS. Computers, IEEE Transactions on, 38(2):292-297, 1989参照）を用いることができる。また、dtを決定するために、btが或るモジュラスmiに等しいなら、dt=yt,iとし、そうでないなら、dtは再び基数拡張により決定することができる。
【００３３】
上述した基準アルゴリズムの欠点は、数y(t)=dt+dt+1bt+…+ds-1bt…bs-2が益々小さくなり、このことはホワイトボックス応用例においては望ましくないことである。y(t)におけるエントロピの減少により、このことは情報を漏洩し得る。例えば、最後のy(s-1)=dtは小さいが、完全な（符号化された）ＲＮＳ系において符号化されることが分かっている。結果として、“小さい”数の符号化に関する情報は漏らされる。このように、攻撃者は符号化された小さな数のリストを構築することができる。
【００３４】
漏洩される小さい数の符号化は、攻撃者により種々のやり方で利用され得る。例えば、これらの小さな値が入力として与えられる場合の個々のモジュール式加算テーブルの出力を解析することにより、攻撃者は、小さな数の値を符号化バージョンから得ることが可能となり得る。更なる解析により、該攻撃者は全ての数の符号化を元に戻し、かくして当該プログラムが実行された場合に変数の値を得ることさえできる。更に、これらの同一の小さな数が、当該ホワイトボックス構成における他の場所で反復される可能性がある。攻撃者は、かくして、該ホワイトボックス構成における何処においても小さな数の発生を認識することができる。この情報は、当該構成の他の部分を攻撃する際に利用され得る。このことは、当該ホワイトボックス構成の異なる部分において異なる符号化を用いることにより軽減することはできるが、このことは計算を実行するために更に多くのテーブル（即ち、各符号化に対して１つ）を必要とし、該構成のハードウェアフットプリントを増加させる。当該プログラムの各部分のための別個の符号化を回避するために、このように、全ての部分における漏洩を可能な限り制限することが望ましい。
【００３５】
前述した基準アルゴリズムの他の欠点は、該アルゴリズムがｔ番目の反復においてディジットdtを正確に決定することができると仮定する故に擬似剰余では動作することができないことである。
【００３６】
以下に更に詳述されるように、対照的に、ftの適切な選択を伴う一実施態様においては、y^(t)は全範囲にわたって拡散（展開）され、かくして情報を漏洩しないことを保証することができる。また、当該アルゴリズムは、基数拡張において冗長モジュラスm0≦φ(k-1)による算術モジュラスが正確でなければならないことを除き、剰余の代わりに擬似剰余により動作することができる。上記冗長モジュラスは、該冗長モジュラスがＲＮＳの可能なサイズｋに制約を加えないように互いに素な小さなモジュラスの積とすることができることに注意されたい。幾つかの実施態様においては、難読化（例えば、ランダム）整数（例えば、、ft）を用いて、中間結果のエントロピを増加させると共に、これらの難読化整数を変化させることにより各実行に対して（ホワイトボックスのケースにおける異なる符号化に対してさえ）当該アルゴリズムの異なるバージョンを有する可能性を許容する。幾つかの実施態様において、当該アルゴリズムは、一実施態様において正確である冗長モジュラス算術の可能性のある例外を伴って、剰余の代わりに擬似剰余で動作する。冗長モジュラスに対する要件を導入することにより、実施態様は単なる剰余の代わりに擬似剰余を用いる基数拡張を使用することができる。
【００３７】
本発明による計算装置の実施態様を図１及び図２を参照して説明する。図１及び図２による実施態様の動作の更なる詳細は後に更に詳述される。
【００３８】
図１に示される計算装置１００は、剰余数（留数）系（ＲＮＳ）で表された（y1,y2,…,yk）数ｙを基数系で表された出力数（e0,e1,…es-1）に変換するように構成される。計算装置１００は、図１では、コンピュータ装置１５０内に含まれるように図示されている。コンピュータ装置１５０はセキュアなコンピュータ装置、例えば或るアルゴリズムのホワイトボックス構成とすることができる。一実施態様において、コンピュータ装置１５０は、前述したように例えばホワイトボックス構成において符号化されたデータに対して動作する。例えば、コンピュータ装置１５０は計算装置１００に或る数を基数表現に変換し、レンダリング、レポート、出力等がなされ得るように要求することができる。例えば、コンピュータ装置１００は、基数表現を入力として必要とするアルゴリズムを実行するために計算装置１００を要求することができる。
【００３９】
計算装置１００は、剰余数系で表された入力数（ｙ）を入力するように構成された入力インターフェース１１０を有している。該入力インターフェースは、種々の代替例から選択することができる。例えば、入力インターフェース１１０は、ローカルエリアネットワーク又は広域ネットワーク（例えば、インターネット）に対するネットワークインターフェース、内部又は外部データ記憶部に対する記憶部インターフェース、キーボード等とすることができる。該インターフェースは、アブレーションプログラムインターフェース（ＡＰＩ）とすることができる。コンピュータ装置１５０はプロセッサ回路及びメモリを共有することができる。コンピュータ装置１５０は、適切なコード（例えば、必要とされるテーブルを取り出し、当該変換アルゴリズムに供給する）を実行開始することにより計算装置１００を使用することができる。
【００４０】
例えば、入力インターフェース１１０は入力数ｙを符号化された整数の系列として得ることができる。斯かる符号化された整数は、ＲＮＳのモジュラスmiによる剰余のモジュロを表す。例えば、入力インターフェース１１０は上記の符号化された整数を該符号化された整数に対するポインタ等の形態で取得することができる。
【００４１】
計算装置１００は、プロセッサ回路１２０を有する。該プロセッサ回路は、単一コアとすることができるか、又は複数のコアを有することができる。該プロセッサ回路は、恐らくは物理的に分離された２つのプロセッサ回路（例えば、副回路）にわたって分散させることができる。計算装置１００はメモリ１３０を有する。該メモリは、揮発性及び不揮発性部分を有することができる。後者はオプションであり、例えば一実施態様において当該データの一定の部分（例えば、プロセッサ命令、テーブル又はデータ定数等）は、当該変換が開始される前にダウンロードすることができる。メモリの揮発性部分は、プロセッサ回路１２０が作用する入力データ、中間データ及び出力データ等の如何なるものも記憶することができる。プロセッサ回路１２０は、メモリに記憶されたプログラミング命令を実行するように構成された汎用コンピュータプロセッサとすることができる。プロセッサ回路１２０は、恐らくは部分的に、本発明による方法を実行するように構成された特化された回路とすることもできる。例えば、プロセッサ回路１２０は、ルックアップテーブルを取り込み及び／又は適用するように構成されたハードウェアを有することができる。
【００４２】
例えば、メモリ１３０は符号化データに作用するように構成されたルックアップテーブルを記憶することができる。例えば、メモリ１３０は斯かるテーブルが作用する変数（例えば、中間データ）を記憶することができる。例えば、プロセッサ回路１２０は、メモリ１３０からテーブルを取り出すと共に、該テーブルを同様にメモリ１３０から取り出される１以上のデータ項目に適用することができる。その結果は、メモリ１３０に記憶することができ、後に更に他のテーブル演算のための入力を形成するために用いることができる。メモリ１３０の一部は、例えばプログラミング命令又はテーブルを記憶するための読出専用メモリとすることができる。
【００４３】
メモリ１３０は、特に、剰余数系で表された中間数（y^）を記憶する。該中間数は、最初は、計算装置１００の入力端において入力された数ｙであり得る。該中間数は、オプションとしての追加の処理（例えば、追加の難読化、他の符号化、符号化変換等）の後の入力数から得ることもできる。後者のステップにおいて、コンピュータ装置１５０において使用される符号化は計算装置１００において使用される符号化に変化される。
【００４４】
プロセッサ回路１２０は、前記中間数y^を反復して更新するように構成される。該中間数の表現は、剰余数系に、好ましくは符号化された形態に留まる。各反復は、基数表現の基数b0,b1,…,bs-1に対する基数表現のディジットe0,e1,…,es-1のうちの１つのディジットを生成する。１つの反復は、
−  基数表現の基数(bt)による中間数のモジュロを計算して、基数表現のディジット(et=<y^>bt)を得るステップ、
−  中間数から上記ディジットを減算し、難読化数を追加し、基数（bt）により除算することにより該中間数を更新する（y^←(y^-et+F)/bt）ステップ、
を有する。
【００４５】
上記計算及び更新するステップの更なる詳細は、図２を参照して、特に以下の説明で示される。更に、そこでは、計算装置１００に適用可能な多数のオプション及び代替例も説明される。
【００４６】
図２は、計算装置２００の実施態様の一例を概略的に示す。図２に示された計算装置２００は、一実施態様の種々の部分を実行するための複数の機能ユニットを有している。図２に示される実施態様は、図１による実施態様の形態で実施化することができる。例えば、図２で使用される記憶部は、メモリ１３０の一部として実施化することができる。上記機能ユニットは、メモリ１３０に記憶されるソフトウェアユニットとして実施化し、プロセッサ回路１２０により実行することができる。該機能ユニットは、回路として又はソフトウェア及びハードウェアの組み合わせとして実施化することもできる。
【００４７】
計算装置２００は、変数記憶部２３５を有する。計算装置２００は、該計算装置２００が作用する中間データを記憶する。特に、変数記憶部２３５はＲＮＳで表現された中間数を記憶する。入力数ｙも変数記憶部に記憶することができる。例えば、前記入力インターフェースは、入力数を変数記憶部２３５に恐らくは変換処理の開始と組み合わせて記憶するように実施化することができる。
【００４８】
計算装置２００は定数記憶部２３０も有する。定数記憶部２３０は、読出専用メモリとして実施化することができる。ホワイトボックス構成の場合、定数記憶部２３０は符号化データに対して演算するためのルックアップテーブルを有する。定数記憶部２３０は、同様に又は代わりに、（符号化）データ等に対して演算するためのプログラミング命令を有することができる。定数記憶部２３０は、基数表現の基数b0,b1,…,bs-1及びＲＮＳ系のモジュラスmiを有することもできる。しかしながら、一実施態様において、これらの数は使用されるテーブルにおいて暗黙的であり、符号化された形態においてさえ明示的に掲載されることを要さない。
【００４９】
計算装置２００はディジット形成ユニット２ｌ０を有する。ディジット形成ユニット２１０は、基数表現の基数（bt）による中間数のモジュロを計算して、基数表現のディジット（et=<y^>bt）を得るように構成される。計算装置２００は更新ユニット２２０を有する。該更新ユニットは、前記中間数を該中間数から上記ディジットを減算すると共に基数（bt）により除算することにより更新する（y^←(y^-et+F)/bt）よう構成される。該更新ユニットは、難読化数（F;Ft）を追加（加算）するように構成される。前記式(y^-et+F)/btを実施することができる（例えば、(y^-et+F)/bt= (y^-et)/bt+F/bt）等の多数のやり方が存在することに注意されたい。後者のF/btは、当該除算がオンラインで実行されることを要さないように事前に計算することができる。前記難読加数を加算することは、他のタスク（例えば、etを減算する）も計算するテーブルに統合することができる。
【００５０】
計算装置２００は、ディジット形成ユニット２１０を反復動作させるように構成される。これらの反復は、基数表現の基数（b0,b1,…,bs-1）に対して基数表現のディジット（e0,e1,…,es-1）を生成する。ディジット形成ユニット２１０により生成されたディジットはディジット記憶部２４０に記憶することができる。ディジット記憶部２４０は変数記憶部２３５と組み合わせることができる。このように、ディジット記憶部２４０は計算装置２００の出力を格納することができる。ディジット記憶部２４０の内容は、更なるアルゴリズム（例えば、レンダリングのための、レポートのための等）により使用することができる。
【００５１】
以下の説明においては、擬似剰余（pseudo-residue）の表記を必要とする。モジュラスｍを法とする整数ｘのモジュロの擬似残差は、ｐ≡x mod mとなる整数ｐである。（特定されていない）擬似剰余を示すために、p=<x>mと書く。擬似剰余p=<x>mが０≦ｐ＜φｍを満たす場合、（整数）拡張率の擬似剰余と言う。擬似剰余は、区間[0,m)内に正確に位置する（即ち、０≦ｐ＜ｍ）ことが必要とされる正確な剰余より多い自由度を可能にする。一方、全ての変数が擬似剰余であることを保証することは、斯かる変数の無制限な成長を回避する。擬似剰余を使用することの斯かる更なる自由度は、当該剰余が拡張率に従わなければならないことを考慮に入れる場合においてさえ、例えばモジュール式算術のための一層効率的なアルゴリズムを可能にする。正確な剰余に対しては、p=|x|mと書き、この場合、０≦ｐ＜ｍである。
【００５２】
ここで、剰余数系（ＲＮＳ）から基数型表現への変換等の変換のためのホワイトボックスに適した新たな方法を提示する。当該アルゴリズムは、入力を擬似剰余で入力すると共に、計算の間において殆ど擬似剰余を使用するのに適している。
【００５３】
miが互いに素な正の整数として、m=m1…mkとしよう。モジュラスm1,…,mkに基づくＲＮＳにおいて、区間[0,m)における整数ｙ（即ち、０≦ｙ＜ｍの場合）は、剰余のリスト（y1,…,yk）により表され、ここで、yi=<y>miは擬似剰余又は正確な剰余とすることができる。中国の余剰定理（ＣＲＴ）によれば、区間[0,m)における全ての整数は、その擬似剰余のリストから固有に復元することができる。ｙ∈[0,m)の（擬似）剰余のリスト（y1,…,yk）による表現をｙの剰余数系（ＲＮＳ）表現と称する。ＲＮＳ型表現において要素yiに対する擬似剰余が許容されることを強調するために、擬似ＲＮＳ表現なる用語を使用する。正確な剰余は擬似剰余の特別なケースであるので、正確なＲＮＳは擬似ＲＮＳの特別なケースである。当該アルゴリズムは、拡張率φを１に設定することにより正確な剰余のみを使用するように構成することができる。
【００５４】
b0,…,bs-1を正の整数とする。（b0,…,bs-1）に対する整数ｙの混合基数（ＭＲ）表現はｙを、di∈[0,bi)である整数ディジットd0,…,ds-1及び整数ｑに対して、
【数５】
0006670421.tif 000006
と書く。アプリケーションにおいて、ｑの値は、ｙのサイズがｙを生成したアプリケーションにより既知の場合、恐らくはｑ＝０にまでさえ制限することができる。便宜上、ｑ＝０と仮定する。
【００５５】
種々のアプリケーションにおいて、ｙ∈[0,m)のＭＲ表現のディジットd0,…,ds-1を、その（擬似）剰余（y1,…,yk）から計算したい。例えば、b0=…=bs-1=bの場合、diは正にｙのｂ進ディジットであり、ｓ＝ｋ及びｑ＝０としてbi=mi+1の場合、これはモジュラスm1,…,mkに対する混合基数（ＭＲ）表現である。
【００５６】
ＲＮＳ表現（ｑは０であると仮定されることに注意）で与えられたとして、数のＭＲ表現y=d0+d1b0+…+ds-1b0…bs-2を、又はその近似を見つけるために、部分１及び２を持つ（後者は副部分２ａ及び２ｂを有する）下記のアルゴリズムを提案する：
１．y^(0)=yと設定する；
２．t=0,…,s-1に対して、
（ａ）et=<y^(t)>bt、
（ｂ）y^(t+1)=(y^(t)-et+b0…bs-1ft)/bt
を実行する。
【００５７】
ここで、f0,…,fs-1は（恐らくはデータに依存する）難読化定数であり（後に説明される特定の条件を前提として）、当該アルゴリズムの新たな各実行に対して変更することができる。b0…bs-1ftは、難読化数Ftとして参照することができる。全ての難読化数が等しい場合、反復を示す下付き文字無しでＦと称することもできる。難読化数Ft又は数ftは、事前に計算し、定数記憶部２３０に記憶することができる。
【００５８】
部分１において、中間数y^は入力数ｙに等しく設定される。反復される部分２ａ及び２ｂにおいて、ＭＲ表現のディジットが決定され（部分２ａ）、中間数y^が更新される（部分２ｂ）。明瞭にするために、中間数ｙ＾の連続する値には、これらを区別するためにインデックスｔが付されていることに注意されたい。しかしながら、一実施態様において、中間数は、新たな値（利用可能な場合）により上書きすることができる。
【００５９】
部分２ａで計算されるＭＲディジットは擬似剰余であるが、拡張率が１である場合、該ディジットは正確な剰余と同じであることにも注意されたい。拡張率が１より大きい場合、幾つかの擬似剰余は正確な剰余ではないであろう。この場合、従来の混合基数表現のディジットが得られる。しかしながら、拡張率が１より大きい場合、部分２ａで計算されるディジットは正確な剰余とは異なり得る。この場合、一般化された混合基数表現を得ることになる。拡張率は、例えば使用されるモジュール式算術を選択することにより、実施者の制御下にあることに注意されたい。一層高い拡張率は、設計者に一層多くの自由度を可能にし、しばしば好まれるが、１なる拡張率も可能である。一実施態様において、ステップ２ａで使用される擬似剰余は、正確な剰余でないもの（例えば、一実施態様において、ディジットetの少なくとも１つは基数表現の基数bt以上である）とすることができる。もっと一般的な擬似剰余が使用される場合、ディジットetの少なくとも１つが０未満であることも起こり得る。整数因子ftの幾つかはゼロとすることができるが、これらの少なくとも幾つかは正である。
【００６０】
部分２ｂにおいて、難読化数b0…bs-1ftはbt…bs-1ftにより置換することができる。このことは、ftに関して選択するために大きな範囲の選択が利用可能となるという利点を有する。例えば、一実施態様において、難読化数は、次の反復で使用される基数（b0,b1,…,bs-1）の積の倍数である（例えば、Ft=bt+1…bs-1ft）。難読化数がbtの倍数でない場合、該難読化数は除算の後に加算され得、これは余り好ましくない。
【００６１】
上記アルゴリズムにおいて、m=m1…mkによる中間数y^(t)のモジュロに関する擬似ＲＮＳ表現は維持される。ディジットetは、後に更に説明するように、基数拡張を用いて計算することができる。当該擬似剰余は整数拡張限界φを満足する。即ち、全てのｔに対して０≦δt＜φとし、δtが拡張率φにより制限される或る非負の整数変数として、et=|y^(t)|bt+δtbtを有する。整数δtは典型的にコンパイル時には未知である。
【数６】
0006670421.tif 000007
と定義する。当該アルゴリズムは以下の特性を有する。即ち、０≦ｔ≦ｓに対し、定義によりε-1=0であり、０≦εt≦θであるような整数εtが存在し、かくして、
１．y^(t)=dt+dt+1bt+…+ds-1bt…bs-2+f0bt…bs-1+f1bt…bs-1b0+…+ft-1bt…bs-1b0…bt-2-εt-1；
２．et=dt-εt-1＋εtbt
となる。
【００６２】
ステートメント１及び２は数学的帰納法により証明することができる。
【００６３】
言い換えると、整数εtは正確な剰余dtと擬似剰余etとの間の距離を示す。結果として、
１．y^(s)=f0+f1b0+…+fs-1b0…bs-2-εs-1=f-εs-1；
２．y=e0+e1b0+…+es-1b0…bs-2-εs-1b0…bs-1=e-εs-1b0…bs-1
を得る。
【００６４】
式２はｙに対する一般化された混合基数表現であることに注意されたい。驚くべきことに、この式においては、“エラー”整数εtのうち、最後のものεs-1しか発生しない。他の全ては相殺する。
【００６５】
所望ならεs-1を計算することができる幾つかの方法が存在する。一実施態様において、値ｆは式１を用いて、例えば反復の更なる部分として、計算することができる。例えば、ｆを、ｆ＝０においてｆを開始し、新たな各ftが利用可能になるやいなや式１の項を加算することにより反復的に計算することができる。次いで、εs-1を計算されたy^(s)のＲＮＳ表現及び既知のｆ（のＲＮＳ表現）から決定することができる。
【００６６】
他の例として、εs-1を、y^(s)のＲＮＳ表現を組み合わされた、小さなモジュラスm0≧θ+1（例えば、冗長モジュラス）によるｆのモジュロの一定の正確な剰余から得ることもできる。
【００６７】
εs-1が分かったなら、全てのｔに対して０≦et＜φbtを満たすディジットet及び０≦εs-1≦θの、ｙに関するＧＭＲ表現が得られる。前述したように、ＧＭＲは、ディジットベースのアルゴリズムに採用されるのに、しｂしば、十分に良好である。εs-1は補正項と称する。例えば、該補正項εs-1は、出力としてエクスポートする（例えば、ディジット記憶部２４０に記憶する）こともできる。etは対応する基数よりも大きくなり得、項εs-1b0…bs-1を減算することにより補償されることに注意されたい。
【００６８】
擬似剰余etが実際に正確な剰余であることが分かる場合（即ち、全てのｔに対してεt=0であることが分かる場合）、当該アルゴリズムはet=dtを供給し、従って実際に正確なＭＲディジットが決定される。更に、全てのｔに対してft=0である場合、当該アルゴリズムはＭＲディジットを決定するための前述した基準アルゴリズムとなる。一実施態様において、整数ftは、中間値y(t)のＲＮＳ表現を依然として可能にするために十分に小さくなるように選択される。後者は、可能な中間値y(t)の範囲が最大でｍのサイズを有する場合に達成することができる。
【００６９】
一実施態様において、前記モジュール式算術はルックアップテーブルを用いて実行される。前記btの幾つか又は全てがルックアップテーブルによるモジュール式算術の実施化を可能にするには大き過ぎる場合、所要のモジュール式算術は、例えば、モンゴメリ乗算又は同様の方法を用いて実施化することができる。複数のモジュール式算術アルゴリズム、特にはモジュール式乗算、更に特別にはモンゴメリ乗算の説明に関しては、例えば、Jean-Francois Dehmの文献“Design of an efficient public-key cryptographic library for RISC-based smart cards. PhD thesis, Universite Catholique de Louvain, 1998”を参照されたい。興味深いことに、モジュール式算術方法は、典型的に、結果を擬似剰余として供給する。正確な剰余を得るためには、余分な努力が必要とされる。一般的に、正確な剰余は、ＲＮＳ表現ドメインから離れることなしでは決定することさえできない。しかしながら、このような状況において、ここに記載される方法は、正確な剰余の代わりに擬似剰余を用いて、或る種のディジットの決定を完全にＲＮＳ領域内で可能にする。
【００７０】
例えば、Dehmにおけるモンゴメリアルゴリズム（2.2.6節）は、最後の２つのステップとして“if Un > N then U = Un − N else U = Un”を有し、この余分な縮小ステップ（reduction step）を省略することは、出力が拡張率２による擬似剰余となるモジュール式縮小アルゴリズムを提供するであろう。数百までさえ高い、大きな拡張率のモジュール式乗算アルゴリズムを、当該アルゴリズムにおいて用いることができる。
【００７１】
以下、当該変換に適したＲＮＳ構成を更に詳述する。ｙがＲＮＳモジュラスm1,…,mk及び冗長モジュラスm0に関する自身の（冗長）ＲＮＳ表現（y0,y1,…,yk）により与えられると仮定し、当該ＲＮＳの動的範囲を示すためにm=m1…mkと書く。モジュラスm0,m1,…,mkは互いに素な正の整数である。更に、m0による算術モジュロは正確であり、従って、m0による剰余のモジュロは擬似剰余ではなく真の剰余である。例えば、m0による算術モジュロはルックアップテーブルにより実施化することができる。他のモジュラスによる算術モジュロは、テーブルのルックアップにより実行することもできるが、モジュール式算術（例えば、モンゴメリ乗算等）の実施化を用いることもできる。
【００７２】
m0による剰余のモジュロは冗長モジュラスと称する。代わりに、冗長モジュラスは複数のモジュラスの積とすることもでき、この場合、計算は該複数のモジュラスに関する正確な剰余で実行される。更に、一実施態様において基数拡張を可能にするためにm0≧ｋなる通常の条件を付けるか、又は、拡張率φによる擬似剰余で動作する場合、m0≧kφとなることを要する。当該アルゴリズムの構成において、y^(t)に関してＲＮＳ表現（y^t,0,y^t,1,…,y^t,k）を維持し、ここで、y^t,i=<y(t)>miは、全てのｉ≧１に対するy^(t)モジュロmiの擬似剰余及びｉ＝０に対するy^(t)モジュロm0の正確な剰余である。
【００７３】
以下の記載において、当該アルゴリズムのＲＮＳ構成をb0=…=bs-1=b=mkの場合に関して説明するものとし、より一般的にケースにおいてどの様に進行するかが容易に理解される。該アルゴリズムの反復ステップは、この場合、以下の様に構成することができる。t=1,…,kに対してet=<y^(t)>bが得られる。mk=bと仮定するので、et=y^t,kとすることができる。次いで、ｉ≠ｋに関して、
【数７】
0006670421.tif 000008
を即座に計算することができ、ここで、
【数８】
0006670421.tif 000009
miによる逆数のモジュロである。ＲＮＳにおいて異なるモジュラスは互いに素であるので、定数
【数９】
0006670421.tif 000010
が存在し、この定数は事前に計算することができる。しかしながら、y^t+1,kに対して、これとは相違して進めなければならない。mk=bはmkによる乗法の逆数のモジュロを有さないからである。このことは、y^t+1,kを決定するために基数拡張を使用することにより解決される。一実施態様においては、下記の冗長モジュラス方法を用いる。例えば、１≦ｔ＜ｋに関して、
【数１０】
0006670421.tif 000011
を計算すると、
【数１１】
0006670421.tif 000012
が得られ、但し、y^(t+1)＜m/mk、mi（ｉ≠０，ｋとする）に基づく“縮小された”ＲＮＳの動的範囲とする。ここで、ｑの（正確な）値が、冗長剰余y^t+1,0モジュロm0から、
【数１２】
0006670421.tif 000013
と計算される。
【００７４】
ｑが決定されたなら、y^t+1,kを、
【数１３】
0006670421.tif 000014
と計算することができる。
【００７５】
これらの式における定数は、事前に計算することができ、正確な剰余であると仮定することができる。
【００７６】
y^t+1,kに関する上記式を計算するために要するモジュール式演算は、例えば後置縮小を用いたmkによる最終縮小のモジュロが続く通常の演算により実施化することができる。ここでは、擬似剰余で動作するので、ηi＜φmi（ここで、φは拡張率である）のみを有する。０≦y^(t)＜m/mkと仮定されるので、０≦ｑ＜(k-1)φが得られ、従って、前述したようにｑの値を決定することができるためには、m0≧(k-1)φとしなければならない。
【００７７】
上記アルゴリズムは、ホワイトボックス符号化システムにおいて、例えば、テーブルルックアップにより実施化されるモジュール式算術による正確な剰余のＲＮＳ、又は擬似剰余を用いるＲＮＳの何れかを用いて実施化されるのに適している。
【００７８】
前記難読化数ftは種々の方法で選択することができる。当該アルゴリズムが動的範囲m=m1…mkのモジュラスm1,…,mkによるＲＮＳの前後関係で使用される場合、オーバーフローを防止すべくy^(t)＜ｍであることを保証するために整数f0,…,fs-1は十分に小さくなければならない。例えば、bs≦ｍであるなら、０≦ft＜btであることを要求すれば十分である。これとは別に、εs-1を計算するために必要とされるｆの所望の表現を最後に計算することができるなら、ftを任意のやり方で選択することができる。ftを示されたより小さく選択することにより（例えば、ft＝０）、後のft’（t’＞t）を示されるよりも大きく選択することができる。特に有利な選択は、ft＝etとすることである。
【００７９】
一実施態様において、ftは固定された定数である。
【００８０】
一実施態様において、ftは当該アルゴリズムの新たな各適用に伴って変化し得る。例えば或る大きな計算等のアプリケーションにおいて、変換は複数回使用され得、このような各変換は、異なるが固定された難読化数を有することができる。このことは、ホワイトボックスアプリケーションにおいて特に魅力的である。
【００８１】
一実施態様において、難読化数ftは入力数ｙにのみ依存する。この構成は、異なる入力による異なる実行が異なる難読化数を使用するので、２つの異なる実行を互いに相関付けることを一層困難にさせるという利点を有する。しかしながら、同一の入力による実行において、全体の計算は、当該入力数にのみ依存するので、同一となる。このように、同一の入力により複数の実行を行うことは、当該システムを攻撃するための追加の情報を与えることはあり得ない。例えば、難読化数ftは、当該入力の恐らくは変化する（恐らくは、当該プログラムにおける他のデータに依存することにより間接的に）関数とすることができる。例えば、全てのｔに対してft＝etとする、又は当該アルゴリズムの各適用に対して変化し得る定数ctに対してft＝|et+ct|btとする。これらの選択は、当該方法の耐漏洩性を増加させる。
【００８２】
一実施態様において、当該変換は一層大きなアプリケーションの一部である。該一層大きなアプリケーションは複数の数をＲＮＳ表現で計算することができ、かくして結果としての数をＲＮＳ表現で生成する。該結果としての数は、入力数として基数表現に変換することを必要とする。該一層大きなアプリケーションが作用するデータは、前記難読化数のためのランダム源として使用することができる。例えば、複数のftは、ＲＮＳ表現の複数の数のうちの１以上に依存することができる。
【００８３】
前述したように、前記モジュラスは、全てのｔに対してy^(t)＜ｍ（動的範囲）となるように選択されねばならない。当該アルゴリズムをディジット基数m1,…,mk及びft=et（ここで、etは擬似剰余である（従って、恐らくはet≧mt））で使用する場合、確かにy^(t)＜ｍであることを保証するために、ＲＮＳに少しのモジュラスmk+1,…,mk+rを追加することができる。等価的に、数ｙをｙ＜m1…m1と仮定することにより制限し、次いで当該アルゴリズムの部分２ｂを、
【数１４】
0006670421.tif 000015
により置換することができる。
【００８４】
言い換えると、当該アルゴリズムの実行の間におけるオーバーフローを防止するために、ディジット基数b0=m1,…,br-1=mrの（従って、ｓ＝ｒ）のアルゴリズムを適用する。
【００８５】
bi=b（固定）の、且つ、全てのｔに対してft＜bのアルゴリズムを使用する場合、全てのｔに対してy^(t)＜bsとなる。典型的に、ｂは当該モジュラスの１つに等しい、即ちmk＝ｂである。この場合、モジュラスm1,…,mk-1により形成されるＲＮＳに関する基数拡張によりdt=y^t,kを決定しなければならない。この場合、動的範囲に対する条件は、bs≦m/mkということである。ｂが全てのmiに対して互いに素である場合、全ＲＮＳを用いる基数拡張によりdt=<y^(t)>bを決定しなければならず、その場合、要件はbs≦ｍということである。
【００８６】
先にy^(t+1)=(y^(t)-et+b0…bs-1ft)/btとして示された当該アルゴリズムの部分２ｂにおいて、難読化部分は一般化することができる。b0…bs-1ftを加算する代わりに、bt…bs-1ftを加算することも可能である。このことは、ftに対する一層多くの選択を提供する。除算の前にbt…bs-1ftを加算する代わりに、除算後にbt…bs-1ftを加算することもできる。
【００８７】
一実施態様において、当該アルゴリズムは、モジュラスm1,…,mk（mk=ｂとする）のＲＮＳと組み合わせて、全てのt=0,…,s-1に対するディジット基数bt=bで、定数ctに対してft=|et+ct|bとして実行され、必要な場合に前述したように“冗長モジュラス”基数拡張を適用する。
【００８８】
以下では、全てのモジュラスm1,…mkが互いに素ということではない実施態様に対して適応させる変更例が示される。= (x1,…,xk) mod (m1,…,mk)を考察する。全ての対ｉ及びｊに対してxi = xj mod gcd(mi,mj)とする。これを用いれば、一般化された中国の余剰定理（ＧＣＲＴ）は、m = lcm(m1,…,mk)である固有なx mod mが存在することを示す。この数は以下の様に復元することができる。定数c1,…,ckをc1(m/m1)+…+ck(m/mk) = 1 mod mのように決定する。
【００８９】
このような定数は常に存在し、実際に、０≦ci＜miであることを要求することさえできる。定数ciは、通常のＣＲＴにおける定数|(m/mi)^{-1}|miの役割を引き継ぐ。このことは、x1c1(m/m1)+…+xkck(m/mk) = x mod mであることを意味する。
【００９０】
この表現を用いれば、冗長モジュラスを用いる基数拡張を含む、通常のＲＮＳで行うことができる全てのことを実行することができる。実際に、後者の式から、ei=|xici|mi又はei=<xici>miが得られ、従って、通常のように０≦ｑ＜ｋとして、x=e1(m/m1)+…+ek(m/mk)-qmとなる。
【００９１】
典型的に、計算装置２００はマイクロプロセッサ（図２には別途示されていない）を有し、該マイクロプロセッサは該装置２００に記憶された適切なソフトウェアを実行する。即ち、例えば上記ソフトウェアは、例えばＲＡＭ等の揮発性メモリ又はフラッシュ等の不揮発性メモリ等（別途図示されてはいない）の対応するメモリにダウンロード及び／又は記憶されたものとすることができる。他の例として、装置２００は、全体として又は部分的に、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジック内で実施化することができる。装置２００は、全体として又は部分的に、所謂特定用途向け集積回路（ＡＳＩＣ）、即ち特定の用途のために特注化された集積回路（ＩＣ）として実施化することができる。例えば、斯かる回路は、例えばVerilog、ＶＨＤＬ等のハードウェア記述言語を用いて、ＣＭＯＳで実施化することができる。
【００９２】
一実施態様において、計算装置２００は、ディジット形成回路、更新回路、難読化回路、定数記憶部、変数記憶部及びディジット記憶部を有する。これら回路は、本明細書に記載される対応するユニットを構成する。これら回路はプロセッサ回路及び記憶回路とすることができ、プロセッサ回路は記憶回路内で電子的に表される命令を実行する。これら回路は、ＦＰＧＡ又はＡＳＩＣ等とすることもできる。
【００９３】
以下、動作中の実施態様の詳細な例を示す。ここでは、k = 3、モジュラスm1 = 13, m2 = 11, m3 = 7及び冗長モジュラスm0 = 4；ディジット基数b0 = b1 = 7、従ってs = 2；ft = et；全てのｔに対してεt < φ = 2の擬似剰余（従って、拡張率φ= 2の擬似剰余を用いる)によるＲＮＳのための本方法の一例を示す。全てのｔに対して、数y^(t)はa,b < 2・7 = 14とする形態a+7bを有し、従ってy^(t)≦13 + 13・7 = 8・13＜m1・m2であり、従ってm3 = 7による剰余のモジュロを決定するためにモジュラスm1,m2の縮小されたＲＮＳを用いた基数拡張が可能である。更に、必要に応じて、m0≧(k −1)φ= 2・2 = 4とする。
【００９４】
（既知の）剰余(1; 11,4,2) modulo (4; 13,11,7)により表されるy = 2 + 5・7 = 37 (未知と仮定される)を例にとる。本アルゴリズムを実行すると、下記が得られる。
1.y^(0) = y〜(1;11,4,2);
2. e0 = <y^(0)>7 = y^0,3 + 1・7 = 9 (擬似剰余), 従って、ε0 = 1; e0のＲＮＳは(1;9,9,2)に等しい。
y^(1) = (y^(0) + 9・(72 − 1))/7 = 67 ≡ (3; 2,1,4); 7-1〜(3; 2,8,−)なので、確かに、
(a) (y^1,0; y^1,1, y^1,2, y^1,3) ≡ ((1;11,4,2) − (1; 9,9,2)) * (3; 2,8,−) + (9・7; 9・7,9・7,9・7) ≡ (3; 2,1,−)、従って、y^1,0 = 3、及び擬似剰余y^1,1 = 2 + 1・13 = 15、及びy^1,2 = 1 + 0・11 = 1を得ることができ; 
(b) η1 = <15・|11-1|13>13 ≡ <2・6>13 ≡ 12mod13;従って、例えば、η1 = 25;
(c) η2 = <1・|13-1|11>11 ≡ 1・6 ≡ 6mod11;従って、例えば、η2 = 17; 
(d) 従って、y^(1) = 25・11 + 17・13 − q・13・11;
(e) 冗長剰余から、3 ≡ 1・3 + 1・1 − q・1・3 ≡ −3qmod4、従って、q = 3;
(f) 従って、y^1,3 = <25・|11|7 + 17・|13|7 + 3|(-13・11)|7>7 ≡ 4mod7、従って、例えば、y^1,3 = 11;
(g) 従って、ここで、y^(1)〜(3;15,1,11)を得る; 
ことが分かり；
3. e1 = y^1,3 = 11 (擬似剰余),従ってε1= 1; y = e − 1・72 （但し、e = 9 + 11・7 = 86）であるこが分かり; 
y^(2) = (y^(1) + e((72 − 1))/7 = (67 − 11)/7 + 11・7 = 85 ≡ (1;7,8,1);従って、確かに、
(a) (y^2,0;y^2,1,y^2,2,y^2,3) ≡ ((3;15,1,11) − (3;11,0,4)) * (3;2,8,−) + (11・7;11・7,11・7,11・7) ≡ (1;7,8,−)、従って、y^2,0 = 1、及び擬似剰余y^2,1 = 7 + 0・13 = 7、及びy^1,2 = 8 + 0・11 = 8を得ることができ; 
(b) η1 = <7・|11-1|13>13 ≡ <7・6>13 ≡ 3mod13;従って、例えば、η1 = 3;
(c) η2 = <8・|13-1|11>11 ≡ 8・6 ≡ 4mod11;従って、例えば、η2 = 4;
(d) 従って、y^(2) = 3・11 + 4・13 − q・13・11;
(e) 冗長剰余から、1 ≡ 3・3 + 4・1 − q・1・3 ≡ 1 − 3qmod4、従って、q = 0;
(f) 従って、y^1,3 = <3・|11|7 + 4・|13|7 + 0|(-13・11)|7>7 ≡ 1mod7、従って、例えば、y^1,3 = 8；
(g)従って、ここで、y^(2)〜(1;7,8,8)を得る;
ことが分かる。
【００９５】
f = e = 86〜(2; −, −, −)を得る一方、y^(2) = e − ε1〜(1;−,−,−)であるので、冗長剰余から、ε1 = 1と結論する。
y = e − ε172であるので、（大よその）ＧＭＲ表現：
y = 9 + 11・7 − 1・72
が分かる。
【００９６】
また、d0 = 2及びd1 = 5であるので、9 = e0 = d0 + 1・7であり、従って、ε0 = 1及び11 = e1 = 5 − 1 + 1・7であるので、確かにεl = 1となることに注意されたい。 
【００９７】
図３は、計算方法３００の実施態様の一例を概略的に示す。方法３００は剰余数系で表された（y1,y2,…,yk）入力数ｙを基数表現で表された出力数（e0,e1,…,es-1）に変換する。方法３００は、
−  剰余数系で表された入力数ｙを入力するステップ３１０と、
−  基数表現の基数btによる中間数のモジュロを計算して、基数表現のディジットet=<y^>btを得るステップであって、中間数（y^）が剰余数系で表されるステップ３２０と、
−  前記中間数を該中間数から前記ディジットを減算することにより更新する（y^←(y^-et+F)/bt）ステップ３３０と、
を有する。更新するステップ３３０は、難読化数ｆを加算するステップ３３５、及び基数btにより除算するステップを含む。
【００９８】
部分３２０及び３３０は反復され、これら反復が基数表現の基数（b0,b1,…,bs-1）に関する基数表現でのディジット（e0,e1,…,es-1）を生成するようにする。
【００９９】
当業者にとり明らかなように、本方法を実行する多数の異なる態様が可能である。例えば、上記ステップの順番は変更することができ、又は幾つかのステップは併行して実行することができる。更に、ステップの間に他の方法ステップを挿入することもできる。挿入されるステップは、本明細書に記載されるような当該方法の改良を表すことができ、又は本方法に関係しないものとすることができる。例えば、幾つかの部分は、少なくとも部分的に、並列に実行することができる。更に、所与のステップは、次のステップが開始される前に完全に完了する必要はない。
【０１００】
本発明による方法は、ソフトウェアを用いて実行することができ、該ソフトウェアはプロセッサシステムに方法３００を実行させる命令を有する。ソフトウェアは、当該システムの特定の副主体によりとられるステップのみを含むことができる。該ソフトウェアは、ハードディスク、フロッピーディスク、メモリ、光ディスク等の適切な記憶媒体に記憶することができる。該ソフトウェアは、有線又は無線に沿う信号として、又は例えばインターネット等のデータネットワークを使用して送信することができる。該ソフトウェアは、ダウンロードのために及び／又はサーバ上での遠隔使用のために利用可能にすることができる。本発明による方法は、該方法を実行するために例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ）等のプログラマブルロジックを構成するように整えられたビットストリームを用いて実行することができる。
【０１０１】
本発明は、本発明を実施するように適応化されたコンピュータプログラム、特に担体内又は上のコンピュータプログラムにも拡張するものであると理解される。該プログラムは、ソースコード、オブジェクトコード、中間ソースコード及び部分的にコンパイルされた形態等のオブジェクトコードの形態とすることができ、又は本発明による方法の実施に用いるのに適した何らかの他の形態とすることができる。コンピュータプログラム製品に関係する実施態様は、前述した方法のうちの少なくとも１つの方法の処理ステップの各々に対応するコンピュータ実行可能な命令を有する。これらの命令は、サブルーチンに分割することができ、及び／又は静的若しくは動的にリンクされ得る１以上のファイルに記憶することができる。コンピュータプログラム製品に関係する他の実施態様は、前述したシステム及び／又は製品の少なくとも１つのものの手段の各々に対応するコンピュータ実行可能な命令を有する。
【０１０２】
図４ａは、コンピュータプログラム１０２０を有する書込可能部分１０１０を備えたコンピュータ読取可能な媒体１０００を示し、コンピュータプログラム１０２０はプロセッサシステムに一実施態様による計算方法を実行させるための命令を有する。コンピュータプログラム１０２０は、コンピュータ読取可能な媒体１０００上で、物理的マークとして、又は該コンピュータ読取可能な媒体１０００の磁化により具現化することができる。しかしながら、如何なる他の好適な実施態様も同様に考えることができる。更に、ここではコンピュータ読取可能な媒体１０００が光ディスクとして図示されているが、該コンピュータ読取可能な媒体１０００は、ハードディスク、固体メモリ、フラッシュメモリ等の任意の好適なコンピュータ読取可能な媒体とすることができると共に、非記録可能又は再記録可能とすることもできることが分かる。コンピュータプログラム１０２０は、プロセッサシステムに前記計算方法を実行させるための命令を有する。
【０１０３】
図４ｂは、一実施態様によるプロセッサシステム１１４０を概略図として示す。該プロセッサシステムは１以上の集積回路１１１０を有する。該１以上の集積回路１１１０のアーキテクチャが図４ｂに概略的に示されている。回路１１１０は、一実施態様による方法を実行するための及び／又はモジュール若しくはユニットを実施化するためのコンピュータプログラム要素を実行するための処理ユニット１１２０（例えば、ＣＰＵ）を有する。回路１１１０は、プログラミングコード、データ等を記憶するためのメモリ１１２２を有する。メモリ１１２２の一部は読取専用とすることができる。回路１１１０は、例えばアンテナ、コネクタ又は両方等の通信エレメント１１２６を有することができる。回路１１１０は、本方法で定義される処理の一部又は全てを実行するための専用の集積回路１１２４を有することができる。プロセッサ１１２０、メモリ１１２２、専用のＩＣ１１２４及び通信エレメント１１２６は、相互接続部１１３０（例えば、バス）を介して互いに接続することができる。プロセッサシステム１１１０は、アンテナ及び／又はコネクタを各々用いて、非接触及び／又は接触通信を行うように構成することができる。
【０１０４】
例えば、一実施態様において、当該計算装置はプロセッサ回路及びメモリ回路を有することができ、該プロセッサ回路はメモリ回路に記憶されたソフトウェアを実行するように構成される。例えば、該プロセッサ回路は、インテルコアｉ７プロセッサ、ＡＲＭCortex-R8等とすることができる。上記メモリ回路は、ＲＯＭ回路又は例えばフラッシュメモリ等の不揮発性メモリとすることができる。該メモリ回路は、例えばＳＲＡＭメモリ等の揮発性メモリとすることができる。後者の場合、当該計算装置は、ソフトウェアを供給するように構成された、例えばハードドライブ、ネットワークインターフェース等の不揮発性ソフトウェアインターフェースを有することができる。
【０１０５】
上述した実施態様は本発明を限定するというより解説するものであり、当業者であれば多数の代替実施態様を設計することができることに注意すべきである。
【０１０６】
尚、請求項において、括弧内に示された如何なる符号も、当該請求項を限定するものと見なされてはならない。“有する”なる動詞及びその活用形の使用は、請求項に記載されたもの以外の要素又はステップの存在を排除するものではない。単数形の要素は、複数の斯様な要素の存在を排除するものではない。本発明は、幾つかの別個の要素を有するハードウェアにより、及び適切にプログラムされたコンピュータにより実施化することができる。幾つかの手段を列挙する装置の請求項において、これら手段の幾つかは１つの同一の品目のハードウェアにより具現化することができる。特定の手段が互いに異なる従属請求項に記載されているという単なる事実は、これら手段の組み合わせを有利に使用することができないということを示すものではない。
【０１０７】
請求項において、括弧内の符号は、例示的な実施態様の図面における符号又は実施態様の式を参照し、請求項の理解度を向上させるものである。これらの符号は当該請求項を限定するものと見なしてはならない。
【符号の説明】
【０１０８】
１００  計算装置
１１０  入力インターフェース
１２０  プロセッサ回路
１３０  メモリ
１５０  コンピュータ装置
２００  計算装置
２１０  ディジット形成ユニット
２２０  更新ユニット
２２５  難読化ユニット
２３０  定数記憶部
２３５  変数記憶部
２４０  ディジット記憶部
【要約】
残余数系（ＲＮＳ）で表わされた((y1,y2,…,yk))の入力数(y)を基数表現((e0,e1,…,es-1))で表される出力数に変換するよう構成された電子計算装置１００である。該計算装置は、残余数系で表された入力数(y)を入力するように構成された入力インターフェース１１０と、残余数系で表された中間数(y^)を反復して更新するよう構成されたプロセッサ回路１２０とを有する。これら反復は基数(b0,b1,…,bs-1)に関して基数表現のディジット(e0,e1,…,es-1)を生成し、少なくとも１つの反復は、基数表現の基数(bt)による中間数のモジュロを計算して基数表現のディジット(et=(y^)bt)を得るステップ、該ディジットを中間数から減算し、難読化数(F;Ft)を加え、及び基数(bt)により除算することにより中間数を更新する（y^←(y^-et+F)/bt））ステップを有する。【図１】
0006670421.tif 000016
【図２】
0006670421.tif 000017
【図３】
0006670421.tif 000018
【図４ａ】
0006670421.tif 000019
【図４ｂ】
0006670421.tif 000020