JP5599728B2 - ホワイトボックス実装 - Google Patents

Description

本発明は、エンティティが冪乗の結果を計算することを可能にする方法に関する。

インターネットは、デジタルコンテンツへの利便なアクセスをユーザに提供する。インターネットを介して消費者がコンテンツを入手できるようにする際の柔軟性のために、現在の動向として、インターネットにアクセスしてレンダリング対象の媒体コンテンツを入手する機能を消費者家電(CE)製品に搭載するようになっている。そのようなCE製品には、これらに限定されないが、デジタルセットトップボックス、デジタルTV、ゲーム機、PC、および、現在増えているPDA、携帯電話等の手持ち型装置と、携帯型MP3プレーヤ等の移動型の記憶装置およびレンダリング装置が含まれる。インターネットはデジタルコンテンツを配布する唯一の媒体ではない。例えば、衛星、地上の大気、および/またはケーブルネットワークを介してデジタル映像ブロードキャスト(DVB)およびデジタル音声ブロードキャスト(DAB)を使用する等、他のデジタルコンテンツ配布経路も広く使用される。著作権で保護されたコンテンツに対してインターネットおよび他のデジタル配布媒体を使用することは、コンテンツ提供者の利益を守るという課題を生む。特に、コンテンツ提供者の著作権とビジネスモデルを保証するために利用できる技術手段があることが望まれる。CEプラットフォームは、次第に、適切なソフトウェアがロードされたプロセッサを使用して操作されるようになりつつある。そのようなソフトウェアは、音声および/または映像等のデジタルコンテンツをレンダリング(再生)する機能の主要部分を含むことができる。再生ソフトウェアのコントロールは、コンテンツを使用するための条件を含むコンテンツ所有者の利益を擁護する方法の1つである。従来多くのCEプラットフォーム(PCおよびPDAを除く)は閉じられていたが、今日では、多くのプラットフォームは少なくとも部分的にオープン化されつつあり、コンピュータプログラマがソフトウェアを調べ、ソフトウェアに変更を行えるようになっている。パーソナルコンピュータを含むそのようなオープンシステムでは、一部のユーザは、コンテンツへのアクセスを提供するハードウェアおよびソフトウェアに対する完全な制御を有すると考えられる。また、一部のユーザは、コンテンツの保護機構を攻撃し、迂回するための多量の時間と資源を有する可能性がある。その結果、コンテンツ提供者は、悪意のあるネットワークを通じて、すべてのユーザまたは装置が信頼できるとは限らないコミュニティに配信することにより、合法的なユーザにコンテンツを配信しなければならない。

通例、デジタル権利管理システムでは、鍵に従ってデータストリームを処理するブロック暗号を用いた暗号化技術を用いる。そのようなコンテンツは、同一の鍵または別の鍵を使用して受信者によって解読できる。消費者装置内でのそのような暗号の実装は、攻撃者が鍵の値を知るのをより難しくするために難読化することができる。多くの種々のアプリケーションで一般に使用される暗号の例は、DES、AES、RSA、および特許文献１に開示される方法である。

特定の非常に重要なデータが上記のようなユーザから隠されるように設計されたソフトウェアアプリケーションは、ホワイトボックス実装と呼ばれる。詳細には、ホワイトボックス実装は、そのソフトウェアアプリケーションで使用されている暗号鍵の値を攻撃者が知ることがより難しくなるような方式で設計することができる。通例、ホワイトボックス実装は、暗号鍵等のデータを、例えばデバッガを使用することによって実行環境を完全に制御できるユーザから隠すことも試みる。

鍵の扱いに関連して、メディアプレーヤは、再生のためにライセンスデータベースから解読鍵を取得しなければならない。メディアプレーヤは次いで、その解読鍵を、暗号化コンテンツの解読のためにメモリ内のどこかに記憶する。これは、攻撃者に、鍵を攻撃するための2つの選択肢を残す。第1に、ライセンスデータベースへのアクセス機能のリバースエンジニアリングにより、ブラックボックスソフトウェア(すなわち攻撃者がそのソフトウェア機能の内部機構を理解する必要がない)を得ることが可能であり、攻撃者がすべてのライセンスデータベースから価値ある鍵を取得することが可能になる。第2に、コンテンツ解読時のメモリへのアクセスを観察することにより、価値ある鍵を取得することができる。どちらの場合も、鍵は危険にさらされるものと考えられる。

非特許文献1、および非特許文献2(以下これら2つの文献をまとめて「Chow」と呼ぶ)は鍵を隠蔽することを目的とする方法を開示し、この方法は、鍵のテーブルの符号化を、個々のステップではなく合成を表すランダムな全単射と組み合わせ、暗号化の境界をその鍵を包含するアプリケーションまで広げることによって拡大することによる。

国際公開第9967918号 国際公開第2007/105126号

「White-Box Cryptography and an AES Implementation」、Stanley Chow、Philip Eisen、Harold Johnson、およびPaul C. Van Oorschot著、Selected Areas in Cryptography: 9th Annual International Workshop, SAC 2002、カナダ、ニューファンドランド州、セントジョンズ、2002年8月15〜16日 「A White-Box DES Implementation for DRM Applications」、Stanley Chow、Phil Eisen、Harold Johnson、およびPaul C. van Oorschot著、Digital Rights Management: ACM CCS-9 Workshop, DRM 2002,アメリカ合衆国、ワシントンDC、2002年11月18日

Chowに開示される技術では、ソフトウェアを完全にデバッグできる人物に暗号鍵を公開することなく、ソフトウェア内で暗号演算を行うことができる。Chowの手法では、暗号鍵は、数学操作ではなくルックアップテーブルを使用することによって隠蔽され、その結果、数学操作のオペランドがオペランドとして記憶されなくてよい。それらのテーブルは、ランダムな全単射を使用して符号化して、さらにテーブルを難読化(obfuscate)することができる。1つのテーブルの符号化は、別のテーブルの符号化によって取り消すことができ、またはプログラム中のいずれか別の場所で取り消すことができる。しかし、すべての操作がルックアップテーブルを用いて容易に表される訳ではない。

より広い範囲のアルゴリズムにホワイトボックス実装を作成することができると有利であろう。この問題によりよく対処するために、本発明の第1の態様では、底Cおよび指数xを有する冪乗C^xの結果を装置が計算することを可能にする方法が提示され、この方法は、冪乗の底Cおよび冪乗の指数xを設定する(102)ステップと、i=1,2,...,rで、複数の値λ_iを設定するステップ(104)であって、rは整数であり、r≧2であるステップと、i=1,2,...,rで、
を満たす複数の値ω_iを設定する(106)ステップと、
i=1,2,...,rで、
を満たす複数の値φ_iを設定する(108)ステップと、
複数の値ω_iを示す情報を装置に提供する(110)ステップと、
複数の値φ_iを示す情報を装置に提供する(112)ステップと、
装置により
を計算する(114)ステップとを含む。

P=C^xなので、この方法では、装置が冪乗の底Cおよび/または冪乗の指数xの知識を得られるようにすることなく、装置が冪乗C^xの結果を計算することが可能になる。これにより、エンティティを完全に調査またはデバッグする能力を有する攻撃者に底または指数を公開することなく、信頼されないエンティティ(装置)上で冪乗を行うことが可能になる。底および指数は、決して平文の形式でエンティティに提供されないので、攻撃者に対して公開されない。エンティティに提供される情報は冪乗の結果を計算するのに十分であるが、その情報から底および/または指数を計算することは困難または不可能である。エンティティには値ω_iとφ_iのみが提供されればよい。これらの値は、冪乗の結果を計算するのに十分である。しかし、これらの値からCの値を知ることは難しい。それはCを知るためには、ω_iおよびλ_iの値を知る必要があるためである。また、xを知るためにはφ_iおよびλ_iの値を知る必要があるので、xの値を知ることも難しい。結果として、複数の値λ_iが秘密に保たれれば、Cまたはxを知ることが難しい。たとえCが攻撃者に知られた場合でも、xについて知ることはなお難しい。それは、xについて知るためには、攻撃者は、i=1,2,...,rについてx=^ClogPまたはλ_i=^Clogω_iを計算する必要があるためであり、これらのパラメータと代数構造がどのように選択されるかに応じて、これらの対数は計算が難しいと考えられる。例えば、^ClogPは、Cが高次の巡回群の生成元である場合に計算するのが難しいと考えられる。この冪乗は、例えば、暗号/解読アルゴリズムを含む暗号アルゴリズム、デジタル署名の作成および/または検証で使用できる。

一実施形態では、複数の値λ_iを設定するステップは、
となるように、指数xとして使用される値の集合Vを設定し、値の複数の集合W₁、W₂、...,W_rを設定するステップを含む。複数の値φ_iを設定するステップは、i=1,2,...,rの場合にφ_i∈W_iとなるように値φ_iを選択するステップを含む。この方法は、複数の値φ_iを設定するステップと、複数の値φ_iを示す情報を装置に提供するステップと、
を装置により計算するステップとを、複数の異なる値x∈Vに関して行うステップを含む。

この実施形態では、同じ底値Cで、効率的な方式で、xの異なる値を効率的に使用することが可能になる。この実施形態で値λ_iが選択される方式により、λ_iを変えることなく集合Vにある任意の指数xを使用することが可能になる。結果として、ω_iの値は変化せず、ω_iの値を再計算する必要がない。これは計算資源を節減する。

特に効率的な実施形態では、i=1,2,...,rの場合にW_i={0,1}である。このような2値表現により、効率的で容易な実装が可能になる。φ_i∈W_iの値を効率的に求めることが可能になる。

本発明の他の有利な態様は、添付の特許請求の範囲の独立請求項に定義される。同様に従属請求項は、有利な実施形態をさらに定義する。

本発明の上記および他の態様が図面を参照してさらに解説および説明される。

装置が冪乗を計算することを可能にする方法の処理ステップを示すフローチャートである。 データの流れ、およびそのデータに作用する処理手段を示す図である。 鍵の生成方法を説明するフローチャートである。 メッセージの暗号化方法を説明するフローチャートである。 暗号文の解読方法を説明するフローチャートである。 冪α^(k₂)をホワイトボックス化する方法を説明するフローチャートである。 冪乗α^(-k₂)をホワイトボックス化する方法を説明するフローチャートである。 暗号アルゴリズムのホワイトボックス実装を得る方法を説明するフローチャートである。 解読アルゴリズムのホワイトボックス実装を得る方法を説明するフローチャートである。 一実施形態を示す図である。

ホワイトボックス暗号は、暗号アルゴリズムのホワイトボックス実装、すなわち、使用されている暗号鍵を攻撃者が抽出することが難しいソフトウェア実装に適したブロック暗号である。そのようなホワイトボックス実装は、AESや3DESなどの対称ブロック暗号のために存在することが知られている。しかし、RSAやElGamal等の非対称暗号をホワイトボックス化することも関心を引く。非対称暗号における典型的な演算は、yとxの両方が可変にも一定にもなることができる冪乗y^xである。一部のブロック暗号では、底yが概ね一定であるのに対して、指数xはより頻繁に変化する。そのようなブロック暗号(より一般的にはアルゴリズム)をホワイトボックス化する場合は、指数xを効率的に変えられると有利である。また、xの値を隠すことが可能なy^xの実装が提供されると有利であろう。本テキストでは、これらの利点を有する、ブロック暗号(より一般的にはアルゴリズム)をホワイトボックス化する手法が提示される。

本明細書に提示されるホワイトボックス実装は、冪乗の標準的な実装よりも大きくすることができる。さらに、攻撃者が実装を小さくすることが難しい。この特性は、ソフトウェア実装の無許可のコピーや配布を防止する際に有利である可能性がある。

特許文献2は、AESやDES等の対称ブロック暗号のホワイトボックス実装に所与の2進列を含める方法およびシステムを開示する。この2進列の包含を使用して、実装をプラットフォームにバインドする、または実装にフォレンジックに(forensically)透かしを入れることができる。本発明に記載されるホワイトボックス実装は、冪乗演算の実装に所与の2進列を含めることを可能にする。

ホワイトボックス実装の利点として、Chow等は、ホワイトボックス実装はプログラムの残りの部分に効果的にバインドできると述べている。より正確には、アルゴリズムの入力値および/または出力値に外部符号化を適用することにより、攻撃者がソフトウェアプログラムから完全なホワイトボックス実装を容易に理解および/または抽出できることが防止される。この説明で開示されるように、この技術は、冪乗のホワイトボックス実装にも適用することができる。

この説明では、例えば冪乗y^xの値xを隠蔽する手法が開示される。本発明では、yは一定で、xは可変であってよいが、これは限定ではない。この値xは、冪乗を行うプログラムの実装を完全に制御およびアクセスできる攻撃者に対しても隠蔽された状態を保つ。

図1は、底Cおよび/または指数xを有する冪乗C^xの結果を装置が計算することを可能にする方法による処理ステップを示すフローチャートである。図2は、データの流れと、そのデータに作用するエンティティおよび処理手段を示す図である。図1の方法について図2も参照して説明する。底Cおよび/または指数xを有する冪乗C^xの結果をエンティティ250が計算することを可能にする方法は、例えばエンティティ200の内部で実施することが可能である。エンティティ200は、インターネットなどのデジタル通信ネットワークを介して、またはケーブル、大気、および/または衛星を介したデジタル通信を使用して、エンティティ250と通信することが好ましい。あるいは、例えば、CD、DVD、フラッシュメモリUSBスティック等の取り外し可能媒体を介してデジタルメッセージが配布される。エンティティ200は、1つまたは複数のエンティティ250にサービスを提供するシステムとすることができる。そのようなシステムは、単一のサーバコンピュータからなることが可能である。ただし、エンティティ200は、各種のコンピュータおよび/または装置を備えるシステムであってもよい。エンティティ200は、ピアエンティティ250と通信するピアデバイス上に実施されてもよく、その場合、ピア同士はセキュリティが保護された方式で情報を交換することを望む。エンティティ250は、装置、または装置上で実行されるのに適したソフトウェアアプリケーションとすることができる。そのような装置は、パーソナルコンピュータ(PC)、ラップトップ、携帯情報端末(PDA)、セットトップボックス、デジタルビデオレコーダ、ゲーム機等である。適切なアプリケーションは、メディアプレーヤ、ウェブブラウザ、およびセキュリティが保護されたトランザクションを行うことが可能なソフトウェアを含む。エンティティ250は、例えば音声および/または映像コンテンツ等のマルチメディアコンテンツを処理するように構成できる。エンティティ250は、本文書に開示される冪乗を使用して音声および/または映像のコンテンツを解読する暗号ユニットを備えることができる。これに加えて、またはこの代わりに、エンティティ250は、メッセージのフィンガープリンティングや署名等の他の種類の暗号演算も行うように構成することができる。

この方法は、冪乗の底Cと冪乗の指数xを設定するステップ102を含む。これらの値Cおよびxは、この方法が適用されるコンテクストに従って得ることができる。例えば、Cおよびxは、暗号アルゴリズムの詳細および/またはそのアルゴリズムで使用される鍵に応じて決まることができる。特に非対称鍵の暗号アルゴリズムでは、冪乗は、通例、重要な役割を果たす。Cおよびxの値は、データベースから取得するか、またはデータベースに記憶されたデータから導出されることが可能であり、例えばデータベースに記憶されたユーザのための鍵がCおよび/またはxを計算するための入力を形成することができる。また、Cおよび/またはxの値は固定されてもよく、一方、他の事例では、Cおよび/またはxは可変としてもよい。Cおよび/またはxの値は、エンティティ200のメモリに記憶できる。

上記方法は、i=1,2,...,rである複数の値λ_iを設定するステップ104を含み、rは整数であり、r≧2である。これらの値λ_iは、後にこの方法でCおよびxの値を難読化するために使用される。これらの値は、所定の集合から無作為に選択されてよい。また、値rの数は無作為に選択されてよいが、より大きなrの値を選択することによってセキュリティを増大させることができる。複数の値λ_iは、少なくとも一時的にエンティティ200のメモリに記憶できる。

上記方法は、i=1,2,...,rの場合に

を満たす複数の値ω_iを設定するステップ106を含む。したがって、これらの値ω_iは、値λ_iおよびCに応じて決まる。値ω_iは、当技術分野で知られている冪乗で計算できる。そのような冪乗演算は、エンティティ200の計算ユニット202で実施されることが可能であり、計算ユニット202は、例えばコンピュータプログラム命令および/または電子回路を備えることができる。

上記方法は、i=1,2,...,rについて、

を満たす複数の値φ_iを設定するステップ108を含む。したがって、これらの値φ_iは、値λ_iおよびxに応じて決まる。値φ_iは、例えばガウス消去法または当技術分野で知られる線形方程式を解く別の方法を使用して計算できる。この方法ステップは、エンティティ200の別の計算ユニット204で実施されることが可能である。

上記方法は、複数の値ω_iを示す情報をエンティティ250に提供するステップ110を含む。方法は、複数の値φ_iを示す情報をエンティティ250に提供するステップ112を含む。ステップ110および112では、通信リンクおよび/または上記で参照した取り外し可能媒体を用いることができる。あるいは、値の一部は、エンティティ250内におけるハードコーディングによって提供されてもよい。例えば、エンティティ250が装置である場合は、製造時に、装置の読み取り専用メモリに値ω_iが記憶されることが可能である。値を時折入れ替えるべき場合には、値は、例えばファームウェアに記憶されることが可能である。値ω_iは、ソフトウェアアプリケーション中にハードコーディングされてもよい。値φ_iは、エンティティ250内に(半)恒久的に記憶されてもよいが、多くのアプリケーションでは、xは非常に頻繁に変わり(例えば送信されるメッセージに応じて)、そのような場合は、ネットワークを介して値を送信し、エンティティ250内のランダムアクセスメモリに記憶しておく方が効率的である可能性がある。

上記方法は、エンティティ250により
を計算するステップ114を含む。このステップは、エンティティ250で実施され、装置中でのC^xの計算に取って替わる。ステップ114でCおよびxは公開されないので、エンティティ250は、Cおよび/またはxの知識を得ることなく、C^xの値を計算することができる。このステップ114は、計算ユニット252で実施される。計算ユニット252は、ステップ114を行うためのソフトウェアモジュールまたは電子回路からなることができる。

この方法は、例えば固定されたCと可変のxと共に使用することができる。そのために、複数の値λ_iを設定するステップ104は、
となるように、指数xとして使用される値の集合Vを設定し、複数の値の集合W₁、W₂、...,W_rを設定することを含んでよい。複数の値φ_iを設定するステップ108は、i=1,2,...,rの場合にφ_i∈W_iとなるように値φ_iを選択するステップを含んでよい。x∈Vの異なる値を使用するために、以下のステップは、それらx∈Vの異なる値に関して行われる。すなわち、複数の値φ_iを設定するステップ108、複数の値φ_iを示す情報を装置に提供するステップ112、および、装置を利用してPを計算するステップ114が、x∈Vの複数の異なる値に関して行われる。

であるので、
となるように適切にφ_i∈W_iを選択することによって、任意の値x∈Vが表されることが可能である。

好ましくは、Cは、乗法群Gの要素であり、Cはq次であり、すなわちqは、C^q=1となるような最小の正の整数である。また、好ましくは、CとGは、qが十分に大きくなるように選択される。詳細には、qは、^Clogxの計算を十分に難しくする場合に十分に大きい。計算が十分に難しい度合いを決定する際には、攻撃者が利用することができる計算資源の量が考慮されるべきである。例えば、qは1024ビット数、例えばq>2¹⁰²³である。

一実施形態では、i=1,2,...,rの場合にW_i={0,1}である。これは、この方法を、例えば特に実現容易にする、かつ/またはより効率的にすることが可能な2値の解決法である。その理由は、φ_iの適切な値を見つけるのがより容易であるためである。

一実施形態では、暗号の鍵は、例えば無作為の生成により、またはデータベースから鍵を検索することによって設定され、その鍵がエンティティ250で使用されなければならない。しかし、エンティティ250に鍵の明示的な知識を与えることは望ましくない。そのため、この方法は、エンティティ200が鍵に依存して底Cを設定し、ω_iの適切な値を計算して提供することを含む。メッセージは暗号化され、メッセージ中での指数xの出現(それに対してエンティティ250はメッセージを解読するためにC^xを計算する必要がある)は、φ_iの適切な値に置き換えられる。その結果得られる暗号化されたメッセージが、エンティティ250に提供される。それにより、エンティティ250は、鍵の知識を得ることなく、詳細にはCの値を知ることなく、暗号の冪乗演算で底Cおよび指数xを使用することが可能になる。

同一の底Cおよび同一の指数xで冪乗C^xを行うべきエンティティ250が複数ある場合がある。しかし、各異なるエンティティ250はその特定のエンティティ250を対象とするデータだけを処理できることが望ましい場合がある。また、各エンティティ250が、ソフトウェアコード、および/または、エンティティ250に具備または記憶されたデータによって一意に識別できることが望ましい場合もある。そのために、この方法は、複数の異なる値λ_iおよび/または異なる値rを選択することをさらに含むことができる。そして、これらの異なる複数の値が、異なる装置に関して、しかしCおよびxの同じ値で使用できる。

エンティティ250は、複数の値ω_iの少なくとも一部を示す情報、および/または複数の値φ_iの少なくとも一部を示す情報を受け取るために、例えば通信リンクまたは取り外し可能媒体を介した入力を有する。これら複数の値の一部またはすべては、例えば製造時の1回限りの構成手順またはハードワイヤリングによってエンティティ250に記憶されることが可能である。

前もってエンティティ250に記憶されない複数の値ω_iおよびφ_iの一部は、エンティティ200から提供されることが可能である。あるいは、値ω_iおよびφ_iの一部またはすべてが、値の供給元254によって提供される。値の供給元254は、例えば装置のハードウェア識別子、生体測定値、および/またはユーザによって入力されたパスワードにアクセスする。そして、値の供給元254は、その結果得られたデータを、直接、またはデータに変換を行ってから、値ω_iおよびφ_iの一部またはすべてとして使用する。

エンティティ250は、非対称暗号に従って暗号演算を行う暗号ユニットを備えることができ、暗号演算は冪乗C^xを伴い、暗号演算を行う手段は、冪乗C^xの結果としてPを使用するように構成される。

エンティティ250は、複数の値ω_iの少なくとも一部、および/または複数の値φ_iの少なくとも一部を示す、暗号化された情報をエンティティ200から受け取るように構成された入力を有することができる。その場合、暗号化された情報を解読して、それぞれ複数の値ω_iの少なくとも一部および/または複数の値φ_iの少なくとも一部を取得する暗号ユニットが提供される。

図10は、エンティティ250として機能することが可能なハードウェアユニットのブロック図を示す。同図は、プロセッサ1002と、プロセッサ1002に本明細書に開示される方法の少なくとも1つを行わせる命令を含むコンピュータプログラム製品を記憶することが可能なメモリ1006を示す。このハードウェアユニットは、例えばボタン、タッチスクリーン、遠隔操作装置等のユーザ入力1004と、ディスプレイ1012を備え、ディスプレイ1012は、例えば、デジタル権利管理を使用して保護された映画を開始する、あるいは暗号化された電子メールメッセージおよび/またはデジタル署名が入った電子メールメッセージを作成し、送信する等、ユーザ対話に必要な機能を提供する。ディスプレイ1012は、(音声スピーカと組み合わせて)映像を再生するためにも使用できる。通信ポート1008は、上述のようにデジタルネットワークに接続し、かつ/または、取り外し可能媒体1010のリーダ/ライタが提供される。

同様のハードウェア方式が、エンティティ200の実装にも使用されてよい。この図は、エンティティ200または250のいずれかに適したハードウェアアーキテクチャの一例に過ぎず、他のアーキテクチャが同等に適する可能性がある。エンティティ200は、複数のサーバを備えるサーバシステムとすることができ、各サーバは、図10と同様のアーキテクチャを有することができる。鍵の生成(その結果底Cが得られる)およびメッセージの暗号化(その結果指数xが得られる)が、エンティティ200のサーバシステムの異なるサーバで行われることは一般的である。鍵および/または底Cが生成されるサーバと同じサーバでω_iの値を計算するのが実用的である可能性がある。同様に、メッセージが暗号化されるサーバ、および/または、指数xが生成されるサーバと同じサーバで値φ_iを計算することが実用的である可能性がある。λ_iの値の生成は、例えば、値を更新する必要の頻度が最も低いサーバ、すなわち鍵および/または底Cを生成するサーバで行われることができる。ただし、これらの作業は、任意の方式で1つまたは複数のコンピュータに分割されてよい。

次数nの群をHとする。ただし、本発明は群に制限されない。その群にある要素をC∈Hとし、整数の部分集合Vにわたる変数をxとする。
以下の説明では、値
C^x (1)
を計算する際に、Cおよび/またはxの正確な値をどのようにホワイトボックス攻撃から隠蔽するかが示される。

整数の集まりをλ₁,λ₂,...,λ_rとし、整数の集合をW₁,W₂,...,W_rとする。さらに、これらの値が
のようにVに及ぶようにする。

さらに、Vの中の要素vについて、λ_iを乗算してvを得ることができる要素w_iとしてf_i(v)を定義し、すなわち
となる。

1≦i≦rである各iについて、
と定義する。

すると、(1)は、
と計算することができる。

C^xがこのようにして実装される場合、実装は、xの代わりに、f(x)=(f₁(x),f₂(x),...,f_r(x))を入力として使用することに留意されたい。すなわち、入力xが符号化される。換言すると、入力f(x)はxに相当するが、f(x)からxの実際の値を導出することは難しい。f(x)およびω_iをホワイトボックス実装に提供することにより、ホワイトボックス実装は、数式(2)を使用してC^xを計算することが可能になる。xを明示的に提供する必要がないので、xの値は、ホワイトボックス実装の攻撃者に対して隠された状態を保つことができる。

値λ_iが攻撃者に対して未知である場合には、攻撃者がCおよびxの値を導出するのが難しい可能性があることが示されることが可能である。さらに、値λ_iが未知であり、Cが既知である場合も、特に^ClogPの計算が難しくなるようにHおよび/またはCが選択された場合には、xを導出するのが難しい。例えば、Hが十分に大きい巡回群であり、Cがその群の生成元である場合は、対数^ClogPの計算が難しい。この対数は、Cの次数が十分に大きい場合も計算することが難しく、Cの次数は、C^q=1になる最小の正の整数qである。当業者には対数の計算が難しい他の事例が明らかであろう。また、この特性が有利に使用されて、本明細書に提示される方法により冪乗を適用することができる。

(1)でxの正確な値を隠蔽するのに加えて、ここに提案される冪乗のホワイトボックス実装は、パラメータ中に2進列を含めることを可能にするという特性も有する。例えば、値λ_iを変えることにより、値ω_iも変化する。この特性を使用して、特定の2進列(例えばハードウェア識別子やコンピュータ実行可能コードの一部から導出される)を値ω_iの少なくとも1つの中に含めることができる。それにより、例えばセキュアなサーバを介してω_iの一部のみがホワイトボックス実装に提供され、ω_iの少なくとも1つの少なくとも一部分がホワイトボックス実装によって実行環境から抽出されるホワイトボックス実装が可能になる。それにより、ターゲットの実行環境でのみ使用することができ、かつω_iが対象とする実行環境の外では無意味なω_iの集合を提供することが可能になる。

また、周辺プログラムに、何らかのλ'₁,λ'₂,...,λ'_tについての関数f'に従って変換された値f'(x)を受け取らせることにより、冪乗演算のホワイトボックス実装を、周辺プログラムにバインドすることも可能である。周辺プログラムは次いで、受け取った値f'(x)を、値λ₁、λ₂,...,λ_rに基づいて(tがrと等しい必要はない)対応する値f(x)に変換し、後者の値f(x)に基づいて冪乗演算を行う。より一般的には、ホワイトボックス実装への入力は、xの何らかの符号化バージョンg(x)からなることができ、ホワイトボックス実装は、g(x)をf(x)に変換してから冪乗を適用する。すると、攻撃者が指数xおよび/または底Cについての情報を得るためには、ホワイトボックス実装だけでなく、この変換も必要となる。ホワイトボックス実装は、1つまたは複数のω_iを何らかの秘密の値で乗算し、この演算を周辺プログラム中のどこか別の場所で取り消すことによっても、周辺プログラムにバインドされることが可能である。

以下に詳細な実施形態が開示される。この実施形態は、ElGamal公開鍵暗号の生成に基づく。ElGamal公開鍵暗号は当技術分野で知られている。簡潔には以下のように説明することができる。
鍵の生成:
生成元αにより、次数nの巡回群Gを選択する。そのような群の一例は、大きい素数pを法とする整数の乗法群である。
1≦a≦n-1であるランダムな整数aを選択し、群要素α^aを計算する。
公開鍵:α、α^a
秘密鍵:a
メッセージm∈Gの暗号化:
1≦k≦n-1であるランダムな整数kを選択し、群要素γ=α^kおよびδ=m・(α^a)^kを計算する。
暗号文は(γ,δ)によって与えられる。
暗号文(γ,δ)の解読:
γ^-aを計算する。
γ^-a・δ=(α^k)^-a・m・(α^a)^k=mなので、γ^-a・δによってメッセージが与えられる。

図3〜図5に本発明の一実施形態を示す。これらの図は、非対称暗号のホワイトボックス実装を示す。より詳細には、ElGamal公開鍵暗号を一般化したもののホワイトボックス実装を示す。ただし、この実施形態は例としてのみ提供される。本発明は、ElGamalにも非対称暗号にも限定されない。指摘したように、この実施形態では、ElGamalの一般化のホワイトボックス実装が開示される。ただし、この一般化は、必ずしも暗号のブラックボックスセキュリティに影響するものではない。すなわち、暗号は、少なくとも元のElGamalブロック暗号と同程度にセキュアであると考えられる。一般化されたElGamal暗号は、以下のように定義される。
鍵の生成(図3のステップ300)
生成元αで次数nの巡回群Gを選択する(ステップ302)。
1≦a≦n-1であるランダムな整数aを選択し、群要素α^aを計算する(ステップ304)。
{0,1,2,...,n-1}に合わせて群Gから関数gを選択する(ステップ306)。強いホワイトボックス実装を可能にするために、関数gは、全単射である必要はないが、好ましくはその範囲は大きい方がよい。
公開鍵:α、α^a、g
秘密鍵:a
ステップ308で公開鍵と秘密鍵が記憶される。
メッセージm∈Gの暗号化(図4のステップ400):
1≦k₁≦n-1であるランダムな整数k₁を選択し、群要素
を計算する(ステップ402)。
k₂=g(γ)を定義する(ステップ404)。k₂=0である場合は、別のk₁を選択する(ステップ406)。
群要素
を計算する(ステップ408)。
(γ,δ)によって暗号文が与えられる(ステップ410)。
暗号文(γ,δ)の解読(図5のステップ500):
k₂=g(γ)を計算する(ステップ502)。
γ^-aおよび
を計算する(それぞれステップ504および506)。
によってメッセージが与えられる(ステップ508)。

値k₂が隠された冪乗演算
(ステップ408)および
(ステップ506)のホワイトボックス実装を導出することができる。

図6は、冪乗
(ステップ408)をホワイトボックス化する方法を示す。図7は、冪乗

(ステップ506)をホワイトボックス化する方法を示す。これらのホワイトボックス化法は、非制限的な例に過ぎない。冪乗演算
を初めに説明する。

0からn-1の間のある数の2進表現を提供するビット列の長さの推定値を
とする(ステップ604)。

k₂の範囲にある各値、すなわち1からn-1の間の各値を(w₁,w₂,...,w_r)∈W₁×W₂×...×W_rで
と書くことができるように、値λ₁、λ₂,...,λ_rおよびW₁,W_2,...,W_rを定義する。これは、例えば、m=r、W_i={0,1}、かつλ_i=b・2ⁱの場合に成立し、bは1からn-1の間で無作為に選択される整数である。これは、関数f(x)が線形関数f(x)=b^-1xと定義され、f_i(x)がf(x)のi番目のビットである場合に、任意のxについて
となることを観察することによって、理解することができる。

を定義し、
により
を計算する(ステップ608)。したがって、冪乗演算のホワイトボックス実装は、入力として(ステップ602)k₂の符号化バージョンf(k₂)=b^-1k₂を有し、
を返す(ステップ610)。

図7に、冪乗
をホワイトボックス化する方法を示す。これは、非制限的な例のみを目的とする。上述のホワイトボックス実装と区別するために、異なる表記が使用される。すなわち、λ_iの代わりにμ_iが使用され、fの代わりにgが使用される。集合W_iは、両方のホワイトボックス実装について同じ、すなわち{0,1}でよい。

1からn-1の間で無作為に選択された整数cについてμ_i=c・2ⁱを定義する(ステップ704)。さらに、線形関数g(x)=c^-1xを定義し、g(x)のi番目のビットをg_i(x)と表す(ステップ706)。これより、xの任意の関連する値は
と表される。

を定義し、
により
を計算する(ステップ708)。したがって、ホワイトボックス実装は、入力としてg(k₂)=c^-1k₂を有し(ステップ702)、
を返す(ステップ710)。

これら2つのホワイトボックス化された冪乗演算を用いて、例えば一般化されたElGamal暗号の暗号化および解読動作のホワイトボックス実装を指定することができる。

図8は、暗号化アルゴリズムのホワイトボックス実装をどのように得るかの一例を示す。

1≦k₁≦n-1であるランダムな整数k₁を選択し(ステップ802)、群要素
を標準的な方法で(すなわちホワイトボックス化せずに)計算する(ステップ804)。ただし、ホワイトボックス化された実装も使用されてよい。

γ=f(k₂)、すなわちk₂=f^-1(γ)が成立するが、これらの値は計算される必要はない。本明細書では、f ^-1は、上記のステップ404および502で使用される関数gに相当する。γ=0の場合(gは全単射かつ線形なのでk₂=0に相当)は、別のk₁を選択する(ステップ806)。

値
が、標準的な方式で(すなわちホワイトボックス化せずに)計算される(ステップ808)。ただし、ホワイトボックス化された実装が使用されてもよい。

値
が
を介して計算される(ステップ810)。γ_i=f_i(k₂)であることに留意されたい。

ステップ808の結果を使用して群要素
を計算する(ステップ812)。

(γ,δ)によって暗号文が与えられる(ステップ814)。

図9に、解読アルゴリズムのホワイトボックス実装をどのように得るかを示す。

値c^-1・bが与えられる(ステップ902)。この値が使用されて、合成関数g*f^-1(x)=c^-1・b・xを求める(ステップ904)。

この合成関数を使用してg(k₂)=g*f^-1(γ)を計算する(ステップ906)。

値γ^-aが標準的な方法で(ホワイトボックス化せずに)計算される(ステップ908)。ただし、ホワイトボックス化された実装も使用されてよい。

値
が
を介して計算される(ステップ910)。

メッセージmが
によって得られる(ステップ912)。

ホワイトボックス実装では、鍵は隠される、例えば実装中に埋め込まれることができ、鍵を交換することが容易でない可能性がある。上記でElGamalの一般化されたバージョンとの関係で説明したホワイトボックス実装は、値αと関数gおよびfが容易に交換されないように構築されることが可能である。さらに、上記でElGamalの一般化されたバージョンとの関係で説明したホワイトボックス実装を、値「α」をなお容易に変えられるような方式で構築することが容易である。そのような場合、図3に関して説明したブロック暗号の鍵生成は、次のように構成されることが好ましい。
値α、g、およびfが固定される。
公開鍵:α、α^a
秘密鍵:a

値λ_i(μ_i)を変えることにより、一般には、値ω_i(υ_i)も変化する可能性がある。したがって、m個の装置からなる集合が与えられ、提案されるこのホワイトボックス実装をそれら装置各々にバインドすることが望ましい場合は、次のようにしてこれが達成されうる。1≦i≦rであるいずれかのiについて、λ_i(μ_i)のm個の異なる値を選択し、m個の個々の関連付けられた値ω_i(υ_i)を計算し、例えば個々の装置のハードウェア識別子を個々の関連する値ω_i(υ_i)に設定する(または値ω_i(υ_i)に依存して設定する)ことによってそれらm個の個々の関連する値ω_i(υ_i)をm個の個々の装置に割り当てる。

装置上でホワイトボックス実装、より詳細にはω_iおよび/またはυ_iの表現に所与の文字列を含めるには、次のように進めることができる。実装中に32ビットのビット列sを含めたいとする。より詳細には、このビット列をω_i(υ_i)の表現として使用したいとする。すると、例えばω_i(υ_i)の最初の32ビットがsによって与えられる確率は、λ_i(μ_i)が無作為に選択された場合には、恐らく1/2³²前後になる。したがって、試行錯誤法を使用することにより、恐らくは最高で2³²回の試行の後に、ω_i(υ_i)の最初の32ビットがビット列sと一致する実装が見つかる可能性がある。このような機能は、例えば、ターゲット装置に存在する、そして好ましくは大半の装置またはすべての他の装置には存在しないことが知られている何らかのビット列を残すことにより、ω_iおよび/またはυ_iを示すデータを特定のターゲット装置にバインドするために使用できる。例えば、何らかのビット列は、MACアドレス、ハードディスクID、または他の種類のハードウェア識別子とすることができる。また、ビット列は、マシン名に基づくこともできる。ω_iおよび/またはυ_iを示すデータを特定の人物にバインドするには、何らかのビット列は、例えばユーザIDまたはパスワードまたは生体測定値に基づくことができる。上述のようにそのビット列をホワイトボックス実装に含めることにより、ホワイトボックス実装は、別の装置または別の人物によっては容易に使用することができなくなる。

本発明は、本発明を実用化するために適合された、コンピュータプログラム、特にキャリア上または内部にあるコンピュータプログラムにも適用されることが理解されよう。プログラムは、ソースコード、オブジェクトコード、部分的にコンパイルされた形態等の中間コードソースおよびオブジェクトコードの形態、または本発明による方法の実施で使用するのに適した形態であってよい。そのようなプログラムは、多くの異なるアーキテクチャ設計を有することが可能であることも理解されよう。例えば、本発明による方法またはシステムの機能を実施するプログラムコードが、1つまたは複数のサブルーチンに再分割されてよい。それらのサブルーチン間に機能を分配する種々の方式は当業者には明らかであろう。サブルーチンは、共に1つの実行ファイルに記憶されて、自己完結型プログラムを形成することができる。そのような実行ファイルは、コンピュータ実行可能命令、例えばプロセッサ命令および/またはインタープリタ命令(例えばJava(登録商標)インタープリタ命令)を含むことができる。あるいは、サブルーチンの1つまたは複数またはすべてが、少なくとも1つの外部のライブラリファイルに記憶され、静的または動的(例えば実行時)にメインプログラムにリンクされることもできる。メインプログラムは、サブルーチンの少なくとも1つへの少なくとも1回の呼び出しを含む。また、サブルーチンは、相互に対する関数呼び出しを含むことができる。コンピュータプログラム製品に関連する実施形態は、ここに述べられる方法の少なくとも1つの方法の各処理ステップに対応するコンピュータ実行可能命令を備える。それらの命令は、サブルーチンに再分割される、および/または静的または動的にリンクされることが可能な1つまたは複数のファイルに記憶できる。コンピュータプログラム製品に関連する別の実施形態は、ここに述べられるシステムおよび/または製品の少なくとも1つの各手段に対応するコンピュータ実行可能命令を備える。その命令は、サブルーチンに再分割される、および/または静的または動的にリンクされることが可能な1つまたは複数のファイルに記憶できる。

コンピュータプログラムのキャリアは、プログラムを搬送することが可能な任意のエンティティまたは装置である。例えば、キャリアは、例えばCD ROMや半導体ROMなどのROM、または例えばフロッピー(登録商標)ディスクやハードディスク等の磁気記録媒体等の記憶媒体を含むことができる。さらに、キャリアは、電気信号または光信号等の伝送可能キャリアであってもよく、電気信号または光信号は、電気ケーブルまたは光ケーブルを介して、または無線や他の手段を介して伝達されることが可能である。プログラムがそのような信号に実施される場合、キャリアは、そのようなケーブルまたは他の装置または手段によって構成されることが可能である。あるいは、キャリアは、プログラムが埋め込まれた集積回路であってもよく、集積回路は、この関連する方法を行うために、または行う際に使用するために適合される。

「乱数」の言及はいずれも、決定性アルゴリズムで生成されるものなど、擬似乱数を含むものと解釈されたい。

上記の実施形態は、本発明を制限するのではなく例示するものであり、当業者は、添付の特許請求の範囲から逸脱することなく多くの代替実施形態を設計することができることに留意されたい。クレームにおいては、括弧内に入れた参照符号は、クレームを限定するものとは解釈すべきでない。動詞「〜を備える」およびその活用形は、クレームに記載された以外の要素またはステップの存在を除外するものではない。各要素は、その要素が複数存在することを除外するものではない。本発明は、数個の別個の要素からなるハードウェア、および適切にプログラムされたコンピュータを用いて実施することができる。数個の手段を列挙する装置クレームでは、それら数個の手段は、1つの同一のハードウェアによって実施することができる。相互に異なる従属クレームに特定の手段(measure)が記載されることだけでは、それら手段の組合せが有利に使用することができないことを意味しない。

200、250 エンティティ
202、204、252 計算ユニット
254 値の供給元
1002 プロセッサ
1004 ユーザ入力
1006 メモリ
1008 通信ポート
1010 取り外し可能媒体
1012 ディスプレイ

Claims (14)

1. 冪乗のホワイトボックス実装により、底Cおよび指数xを有する冪乗C^xを含む暗号化処理を装置が行うことを可能にする方法であって、
   前記冪乗の底Cおよび前記冪乗の指数xを決める(102)ステップと、
   i=1,2,...,rで、複数の値λ_iを決めるステップ(104)と
   を含み、
   rは整数でありかつr≧2であるステップと、
   i=1,2,...,rで、
   
   を満たす複数の値ω_iを設定する(106)ステップと、
   i=1,2,...,rで、
   
   を満たす複数の値φ_iを設定する(108)ステップと、
   前記複数の値ω_iを示す情報を前記装置に提供する(110)ステップと、
   前記複数の値φ_iを示す情報を前記装置に提供する(112)ステップと、
   前記装置により
   
   を計算して(114)、底Cおよび指数xのうちの少なくとも１つの正確な値をホワイトボックス攻撃から隠蔽するステップであって、Pが冪乗C^xの結果であるステップと
   を含む方法。
2. 前記複数の値λ_iを設定するステップは、
   
   となるように、前記指数xとして使用される値の集合Vを設定するとともに、値の複数の集合W₁、W₂、...,W_rを設定するステップを含み、
   前記複数の値φ_iを設定するステップは、i=1,2,...,rで、φ_i∈W_iとなるように値φ_iを選択するステップを含み、
   前記方法は、前記複数の値φ_iを設定するステップと、前記複数の値φ_iを示す情報を前記装置に提供するステップと、前記装置により計算するステップとを、複数の異なる値x∈Vに関して行うステップを含む請求項１に記載の方法。
3. P=C^x であって、i=1,2,...,rで、W_i={0,1}である請求項2に記載の方法。
4. 前記方法は、暗号の鍵を設定するステップをさらに含み、
   前記鍵は、暗号演算を行う前記装置によって使用され、
   前記方法は、前記鍵に依存して前記底Cを設定するステップをさらに含む請求項1に記載の方法。
5. 異なる装置に関して使用される、複数の異なる値λ_i、および/または異なる値rを選択するステップと、
   前記異なる装置に関して、前記底Cおよび前記指数xにそれぞれ同一の値を使用するとともに、前記複数の異なる値λ_iおよび/または前記異なる値rを使用して、前記複数の値ω_iを設定するステップと、前記複数の値φ_iを設定するステップと、前記複数の値ω_iを示す情報を前記装置に提供するステップと、前記複数の値φ_iを示す情報を前記装置に提供するステップと、前記装置により
   
   を計算するステップとを行うステップと
   をさらに含む請求項1に記載の方法。
6. 底Cおよび指数xを有する冪乗C^xの結果を計算するための冪乗のホワイトボックス実装を備える装置(250)であって、
   複数の値ω_iを記憶するメモリと、
   複数の値φ_iを示す情報を受け取る入力と、
   
   を計算する計算ユニット(252)と
   を備え、
   P=C^x であって、
   暗号化処理の一部として、前記冪乗C^xの前記結果としてPには前記計算ユニットにより計算した結果を代入するように構成され、
   底Cおよび指数xのうちの少なくとも１つの正確な値は、ホワイトボックス攻撃から隠蔽される装置。
7. 前記入力は、前記複数の値ω_iの少なくとも一部を示す情報をさらに受け取るように構成される請求項6に記載の装置。
8. 前記装置のハードウェア識別子、生体測定値、およびパスワードの少なくとも1つに依存して、前記複数の値ω_iの少なくとも一部を求める手段(254)をさらに備える請求項6に記載の装置。
9. 非対称暗号に従って暗号演算を行う暗号ユニットをさらに備え、
   前記暗号演算は、前記冪乗C^xを伴い、
   前記暗号演算を行う手段は、前記冪乗C^xの結果としてPを使用するように構成される請求項6に記載の装置。
10. 前記入力において、前記複数の値φ _i を示す情報は、前記複数の値ω_iの少なくとも一部、および、前記複数の値φ_iの少なくとも一部のうちの少なくとも一方を示す暗号化された情報を前記入力が受け取るように構成され、
    前記装置は、前記暗号化された情報を解読して、それぞれ前記複数の値ω_iの少なくとも一部、および、前記複数の値φ_iの少なくとも一部のうちの少なくとも一方を得る暗号ユニットをさらに備える請求項6に記載の装置。
11. 前記装置は、コンピュータ、PDA、パーソナルビデオレコーダ、セットトップボックス、またはゲーム機を含む請求項6に記載の装置。
12. 前記暗号ユニットを使用して音声コンテンツおよび/または映像コンテンツを解読する手段をさらに備える、請求項9に記載の装置。
13. 冪乗のホワイトボックス実装により、底Cおよび指数xを有する冪乗C^xを含む暗号化処理を装置が計算することを可能にするシステム(200)であって、
    前記冪乗の底Cおよび冪乗の前記指数xを一時的に記憶するメモリと、
    i=1,2,...,rで、複数の値λ_iを記憶するメモリと
    を備え、
    rは整数でありかつr≧2であり、
    前記システムは、
    i=1,2,...,rで、
    
    を満たす複数の値ω_iを設定する計算ユニット(202)と、
    i=1,2,...,rで、
    
    を満たす複数の値φ_iを設定する計算ユニット(204)と、
    
    を計算するよう、複数の値ω_iを示す情報と前記複数の値φ_iを示す情報とを前記装置に提供し、Pが冪乗C^xの結果であって、底Cおよび指数xのうちの少なくとも１つの正確な値をホワイトボックス攻撃から隠蔽する出力と
    を備えるシステム。
14. 冪乗のホワイトボックス実装により、底Cおよび指数xを有する冪乗C^xを含む暗号化処理を装置のコンピュータが計算することを可能にするコンピュータプログラムであって、
    前記冪乗の底Cを決める(102)ステップと、
    i=1,2,...,rで、rは整数でありかつr≧2であり、複数の値λ_iを選択するステップ(104)と、
    i=1,2,...,rで、
    
    を満たす複数の値ω_iを設定する(106)ステップと、
    i=1,2,...,rで、
    
    を満たす複数の値φ_iを設定する(108)ステップと、
    
    を計算するよう、前記複数の値ω_iを示す情報と前記複数の値φ_iを示す情報を前記装置に提供し(112)、Pが冪乗C^xの結果であって、底Cおよび指数xのうちの少なくとも１つの正確な値をホワイトボックス攻撃から隠蔽するステップと
    を前記コンピュータに実行させるコンピュータプログラム。