(57)【要約】秘密の情報を用いてビットストリングに暗号計算を実行する方法と装置である。暗号鍵を処理して修正暗号鍵を生成する。修正暗号鍵に対応し、複数の標識ビットを含む標識語を生成する。ビットストリングと修正暗号鍵との関数として第１の積を非安全なプロセッサで計算する。ビットストリングと標識との関数として第２の積を安全なプロセッサで計算する。第１の積と第２の積との関数として最終積を計算する。
2004512570.tif 000002
【特許請求の範囲】
【請求項１】
秘密の暗号鍵を用いてビットストリングに計算を実行する方法であって、
前記暗号鍵を修正して修正暗号鍵を生成し、
前記修正暗号鍵に対応し、複数の標識ビットを有する標識を生成し、
前記ビットストリングと前記修正暗号鍵との関数として第１の積を非安全なプロセッサ内で計算し、
前記ビットストリングと前記標識との関数として第２の積を安全なプロセッサ内で計算し、
前記第１の積と第２の積との関数として最終積を前記安全なプロセッサ内で計算する、
ことを含む、方法。
【請求項２】
前記暗号鍵を修正して修正暗号鍵を生成することは、前記暗号鍵のランダムに選択されたビットを変更して前記修正暗号鍵を生成することを含む、請求項１記載の計算を実行する方法。
【請求項３】
前記修正暗号鍵に対応する標識を生成することは、前記修正暗号鍵に加算すると前記暗号鍵を作る前記修正暗号鍵の加法補数を計算すること含む、請求項２記載の計算を実行する方法。
【請求項４】
前記ビットストリングと前記修正暗号鍵との関数として前記第１の積を前記非安全なプロセッサ内で計算することは、前記修正暗号鍵を指数として用いて前記ビットストリングのモジュロ累乗を実行することを含む、請求項１記載の計算を実行する方法。
【請求項５】
前記ビットストリングと前記標識との関数として前記第２の積を前記安全なプロセッサ内で計算することは、前記標識に基づいて前記ビットストリングの１つ以上の逐次平方を選択することを含み、前記第２の積は前記選択された逐次平方の積を含む、請求項４記載の計算を実行する方法。
【請求項６】
前記第１の積と第２の積との関数として前記最終積を前記安全なプロセッサ内で計算することは、前記第１の積と第２の積とを掛けることを含む、請求項５記載の計算を実行する方法。
【請求項７】
前記ビットストリングと前記修正暗号鍵との関数として前記第１の積を前記非安全なプロセッサ内で計算することは、前記安全なプロセッサで計算された第３の積と、第４の積との関数として前記第１の積を計算すること含み、前記第３の積は前記ビットストリングと前記暗号鍵の短い部分との関数であり、また前記第４の積は前記ビットストリングと前記暗号鍵の修正された長い部分との関数である、請求項１記載の計算を実行する方法。
【請求項８】
秘密のビットストリングと暗号鍵とを用いて非安全なプロセッサで計算を実行する方法であって、
前記暗号鍵を第１の部分と第２の部分に分割し、
前記ビットストリングと前記暗号鍵の前記第１の部分との関数として第３の積を安全なプロセッサ内で計算し、
前記第３の積を前記非安全なプロセッサに出力し、
前記暗号鍵の前記第２の部分を前記安全なプロセッサで修正して前記暗号鍵の修正された第２の部分を作り、
前記暗号鍵の前記修正された第２の部分に対応する標識を生成し、
前記第３の積と前記暗号鍵の前記修正された第２の部分との関数として第１の積を前記非安全なプロセッサで計算し、
前記ビットストリームと前記標識との関数として第２の積を前記安全なプロセッサで計算し、
前記第１の積と前記第２の積との関数として最終積を前記安全なプロセッサで計算する、
方法。
【請求項９】
前記暗号鍵を第１の部分と第２の部分に分割することは、前記暗号鍵を最下位部分と最上位部分とに分割することを含む、請求項８記載の計算を実行する方法。
【請求項１０】
前記ビットストリングと前記暗号鍵の前記第１の部分との関数として前記第３の積を計算することは、前記ビットストリングと前記暗号鍵の前記最下位部分との関数として前記第３の積を計算することを含む、請求項９記載の計算を実行する方法。
【請求項１１】
前記暗号鍵の前記第２の部分を前記安全なプロセッサで修正して前記暗号鍵の前記修正された第２の部分を作ることは、前記暗号鍵の前記最上位部分を修正することを含む、請求項１０記載の計算を実行する方法。
【請求項１２】
前記第３の積と前記暗号鍵の前記修正された第２の部分との関数として前記第１の積を前記非安全なプロセッサで計算することは、前記暗号鍵の前記修正された第２の部分に基づいて前記ビットストリングの逐次平方を選択し、前記第３の積に前記選択された逐次平方を掛けることを含む、請求項１１記載の計算を実行する方法。
【請求項１３】
前記ビットストリームと前記標識との関数として前記第２の積を前記安全なプロセッサで計算することは、前記標識に基づいて前記ビットストリングの１つ以上の逐次平方を選択することを含み、前記第２の積は前記選択された逐次平方の積を含む、請求項１１記載の計算を実行する方法。
【請求項１４】
ビットストリングを秘密の指数で累乗する、安全なプロセッサと非安全なプロセッサとを含む計算装置であって、前記安全なプロセッサは、
前記秘密の指数を少なくとも第１の部分値と第２の部分値とを含む複数の部分値に分割して、前記複数の部分値の和が前記指数に等しくなるようにし、
前記第１の部分値を非安全なプロセッサに出力し、
前記ビットストリングと前記第１の部分値との関数として計算された第１の積を前記非安全なプロセッサから受け、
前記第２の部分値と前記ビットストリングとの関数として第２の積を計算し、
前記第１の積と第２の積との関数として最終積を計算する、
ようにプログラムされる、計算装置。
【請求項１５】
前記非安全なプロセッサで計算した前記第１の積は前記第１の部分値で累乗した前記ビットストリングを含む、請求項１４記載の計算装置。
【請求項１６】
前記安全なプロセッサで計算した前記第２の積は前記第２の部分値で累乗した前記ビットストリングを含む、請求項１５記載の計算装置。
【請求項１７】
前記最終積は前記第１の積と第２の積の積を含む、請求項１６記載の計算装置。
【請求項１８】
前記非安全なプロセッサで計算した前記第１の積を第３の積の関数として更に計算する、請求項１４記載の計算装置。
【請求項１９】
前記第３の積を第３の部分値と前記ビットストリングとの関数として前記安全なプロセッサで計算する、請求項１８記載の計算装置。
【請求項２０】
前記第３の積は前記第３の部分値で累乗した前記ビットストリングを含む、請求項１９記載の計算装置。
【請求項２１】
前記第１の積は前記第３の積に第４の積を掛けることを含む、請求項２０記載の計算装置。
【請求項２２】
前記第４の積は前記第１の部分値で累乗した前記ビットストリングを含む、請求項２１記載の計算装置。
【発明の詳細な説明】
【０００１】
（発明の分野）
本発明は暗号法に関するもので、より詳しくは、安全なプロセッサと非安全なプロセッサとを用いて、秘密のデータを保護すると同時に暗号計算を行う方法と装置に関する。
【０００２】
インターネットは、主として情報交換用の網（ネットワーク）からビジネスおよび商取引用の通信媒体に発展した。このようにインターネットはビジネスおよび商取引用の通信媒体に発展したので、公共網による通信を安全にする必要が生じた。暗号化技術は、インターネットなどの非安全な（ｉｎｓｅｃｕｒｅ）網において安全な（ｓｅｃｕｒｅ）通信を維持するのに一般に用いられている。また、電子商取引が発展したので、遠隔でのログインと文書の確認のための新しい認証方法が必要になった。
【０００３】
公開鍵暗号化法は機密保持と認証の両方の機能を提供する。公開鍵暗号方式では、各ユーザは秘密鍵と公開鍵という適合した鍵の対を保持する。秘密鍵と公開鍵は特有の適合した対を形成する。秘密鍵で暗号化された文書または通信は適合する公開鍵を用いることによってだけ解読することができる。またその逆も正しい。公開鍵は公開してよく、誰でもこれを用いて公開鍵の所有者向けの通信を暗号化することができる。秘密鍵は秘密に保持される。したがって、公開鍵で暗号化された通信は適合する秘密鍵の所有者だけが解読することができる。
【０００４】
公開鍵暗号化法を用いれば、電子文書と通信のためのデジタル署名を作ることもできる。このデジタル署名は文書を確認するのに用いてよい。人は文書または通信を自分の秘密鍵で暗号化することにより電子文書または通信に署名することができる。署名された文書は、適合する公開鍵でこれを解読することにより確認または認証することができる。適合する公開鍵を用いて文書または通信が解読できた場合は、メッセージを送ったのは秘密鍵の所有者だけのはずである。
【０００５】
商取引の完全性を確保しかつ不正を防ぐには、ユーザは自分の秘密鍵を秘密にする必要がある。或るユーザの秘密鍵を入手できた者は、全く匿名でそのユーザになりすますことができる。したがって、電子商取引やその他のアプリケーションでデジタル署名を広く用いるためには、秘密鍵を安全に保管する技術が必要である。
【０００６】
脱着可能なスマート・カードなどの変造不可能なハードウエア装置内に秘密鍵を記憶する方法が知られている。ユーザの秘密鍵と公開鍵の証明はスマート・カードのメモリ内に書き込まれる。スマート・カードを使うには、ユーザはホスト装置に接続するカード読取り器にスマート・カードを挿入し、ＩＤ／パスワードを入力してスマート・カードを活動化する。正しいＩＤ／パスワードを入力すると、カード上のプロセッサは秘密鍵を開放してホスト装置が使えるようにする。正しくないＩＤ／パスワードを所定の回数連続して入力すると、スマート・カードに永久に錠がかかる。知的スマート・カード（暗号カードと呼ぶことが多い）の中には、暗号操作が可能なので、変造できない環境から秘密鍵を出力する必要がないものもある。処理すべきバイトをホスト装置からスマート・カードに入力し、スマート・カードはこれを処理する。スマート・カードからホスト装置にはその結果だけが出力される。
【０００７】
（発明の概要）
本発明は、秘密の情報を開示することなく、メッセージの暗号化や解読などの暗号計算を行うための、安全な装置と非安全な装置を用いる方法と装置に関する。秘密の情報の少なくとも一部は安全な装置内に保持される。どんな実際的な手段でも、秘密の情報の開示された部分から秘密の情報を見つけることはできない。
【０００８】
１つの実施の形態は、秘密の暗号鍵を用いてビットストリングに計算を行う方法と装置を含む。暗号鍵は、ここで修正暗号鍵と標識（ｉｎｄｉｃａｔｏｒ）と呼ぶ２つの部分値に分割される。修正暗号鍵は外部プロセッサに出力される。修正暗号鍵は、暗号鍵の選択されたビットをランダムに変えることにより生成してよい。また修正暗号鍵に対応する標識が生成され、複数の標識ビットを含む。標識はビットストリングであって、これを修正暗号鍵に加算すると元の暗号鍵になる。第１の積（ｐｒｏｄｕｃｔ）は非安全なプロセッサで計算されるもので、ビットストリングと修正暗号鍵との関数である。第２の積は安全なプロセッサ内で計算されるもので、ビットストリングと標識との関数である。最終積は、第１の積と第２の積とを結合して安全なプロセッサ内で計算されるものである。
【０００９】
本発明の第２の実施の形態では暗号鍵を３つの部分値に分割する。ここではこの３つの部分値を、短い部分と、修正された長い部分と、標識と呼ぶ。非安全なプロセッサで第１の積を計算し、これと、安全なプロセッサで計算された第２の積とを結合する。第１の積は、安全なプロセッサで計算された第３の積と、第４の積との関数である。安全なプロセッサはまず第３の積を計算してその結果を非安全なプロセッサに出力する。第３の積は、ビットストリングと暗号鍵の短い部分との関数である。第４の積はビットストリングと暗号鍵の修正された長い部分との関数である。非安全なプロセッサは第３の積と第４の積とを掛けて第１の積を生成する。第１の積を安全なプロセッサに入力する。安全なプロセッサは第２の積を計算し、第２の積と第１の積とを結合して最終積を生成する。第２の積はビットストリームと標識との関数である。
【００１０】
（発明の詳細な説明）
図面を参照すると、図１は非安全な通信チャネル１４により暗号化メッセージを送信および受信する通信端末１０を示す。ここで用いる「通信端末」という用語は、通信チャンネル１４により情報を送信および／または受信する任意の装置を指す。通信チャンネル１４は有線チャンネルまたは無線チャンネルでよい。通信端末１０は、例えばセルラ無線電話や、個人通信システム（ＰＣＳ）端末（データ処理機能、ファクシミリ機能、データ通信機能とセルラ無線電話とを結合する）や、携帯情報端末（ＰＤＡ）（無線電話、ページャ、インターネット／イントラネット・アクセス、ウエブ・ブラウザ、オーガナイザ、カレンダ、全地球測位システム（ＧＰＳ）受信機を含む）で構成してよい。通信端末１０という用語は、他の装置と通信するための通信インターフェースを含む計算装置（例えば、パーソナル・コンピュータ、ラップトップ・コンピュータ、パームトップ・コンピュータなど）も含む。
【００１１】
通信端末１０は通信インターフェース１６と、プロセッサ１８と、セキュリティ・モジュール２０と、ここで加速器１００と呼ぶ非安全なプロセッサを含む。プロセッサ１８は通信端末１０の動作を制御し、動作中に用いる制御プログラムとデータを記憶するための内部または外部メモリを含んでよい。また通信セッションの暗号化と解読のステップ中に、プロセッサ１８を用いて計算機能を行ってよい。しかしプロセッサ１８は安全な装置ではなく、中に記憶されているデータは外部の関係者から見られる可能性がある。
【００１２】
通信インターフェース１６は通信端末１０と通信チャンネル１４とをインターフェースする手段を提供する。インターフェース１６は、無線周波数トランシーバーや、イーサネット（登録商標）・インターフェースや、モデムなどの種々の実施の形態を有してよい。
【００１３】
セキュリティ・モジュール２０は、暗号化や解読などの暗号計算や、その他の機密保護機能を実行するのに用いられる。セキュリティ・モジュール２０は例えば上部金属層でカバーされた脱着可能なスマート・カードでよく、秘密鍵などの記憶されている秘密情報を不正に取り出そうとして内部ノードが探されるのを防ぐ。セキュリティ・モジュール２０内で計算され記憶されるデータには外部からアクセスすることができないので、暗号プロセスの機密は保護される。セキュリティ・モジュール２０は、データを暗号化および解読するための暗号化アルゴリズムに用いられる暗号化変数（ユーザの公開鍵や秘密鍵など）を記憶する。図１には別個の装置として示しているが、実際には、セキュリティ・モジュール２０はプロセッサ１８の安全な部分に組み込んでもよい。
【００１４】
加速器１００は、セキュリティ・モジュール２０が実行する暗号計算を加速するのに用いられる双対プロセッサ（ｃｏ−ｐｒｏｃｅｓｓｏｒ）である。加速器１００はセキュリティ・モジュール２０の外部に置かれ、安全なプロセッサである必要はない。加速器１００の機能はプロセッサ１８が行ってもよいしプロセッサ１８に組み込んでもよい。本発明により、加速器１００は秘密情報を外部から見られずに暗号計算を行うことができる。加速器１００の詳細については後で説明する。
【００１５】
図２はセキュリティ・モジュール２０の詳細を示す。セキュリティ・モジュール２０は、安全なプロセッサ３０と、Ｉ／Ｏインターフェース３２と、読取り専用メモリ（ＲＯＭ）３４と、消去可能プログラム可能な読取り専用メモリ（ＥＰＲＯＭ）３８と、ランダム・アクセス・メモリ４０と、オプションの乱数発生器４２とを含む。Ｉ／Ｏインターフェース３２はセキュリティ・モジュール２０と通信端末１０の主プロセッサ１８とをインターフェースする。安全なプロセッサ３０はＲＯＭ３４内に記憶されているプログラムを実行し、Ｉ／Ｏインターフェース３２を介して安全なプロセッサ３０に与えられる命令に応答する。命令は、記憶されている鍵または外部から供給される鍵を用いてデータを暗号化または解読する要求や、結果を出力ビットとしてＩ／Ｏインターフェース３２に返す要求を含んでよい。
【００１６】
ＲＯＭ３４は、暗号化や解読やその他の機密保護機能に用いられるプログラムを記憶する。変造を防ぐためにプログラムは変更可能でなければならない。ユーザ特有の他のデータ（例えば、公開鍵、秘密鍵、係数（ｍｏｄｕｌｕｓ）、識別証明など）は現場でプログラム可能であり、ＥＰＲＯＭ３８に記憶される。秘密鍵ＫＰＲＩＶは外部からアクセスできない方法で記憶しなければならない。本出願と同時出願の関連米国特許出願「ＰＩＮコードを用いる暗号情報の安全な記憶（Ｓｅｃｕｒｅ Ｓｔｏｒａｇｅ ｏｆ Ｃｉｐｈｅｒｉｎｇ Ｉｎｆｏｒｍａｔｉｏｎ Ｕｓｉｎｇ ａ ＰＩＮ Ｃｏｄｅ）」は、正しいユーザ提供のパスワードを入力しなければ使用できないようにする不規則なまたは不完全な方法で秘密鍵を記憶する１つの方法を記述している。この出願をここに援用する。ＲＡＭ４０はデータ変数を一時的に記憶するための作業メモリである。
【００１７】
またセキュリティ・モジュール２０は、乱数を生成するのに用いられる乱数発生器４２を含む。乱数は、例えば鍵を計算するため、または鍵交換アルゴリズム用のランダム・ビットストリングを生成するため、またはこの技術で公知の他の目的のために用いられる。
【００１８】
通信端末１０が発信および受信するデータは、第三者に見られるのを防ぐために暗号化される。暗号化と解読は公開鍵アルゴリズムを用いて行ってよい。よく用いられる公開鍵アルゴリズムはＲＳＡアルゴリズムである。ＲＳＡアルゴリズムや他の公開鍵アルゴリズムは、暗号化のための第１の鍵（公開鍵と呼ぶ）と、解読のための対応する第２の鍵（秘密鍵と呼ぶ）を用いる。公開鍵と秘密鍵は適合する対を形成する。公開鍵で暗号化されたメッセージを解読することができるのはこれと適合する秘密鍵を用いる場合だけである。したがって、安全な通信を行うため、送信者は受信者の公開鍵を用いてメッセージを暗号化する。宛先の受信者だけが、対応する秘密鍵を用いてメッセージを解読することができる。ＲＳＡアルゴリズムは、米国特許第４，４０５，８２９号に開示されており、これを援用する。
【００１９】
ＲＳＡアルゴリズムでは、情報シーケンスすなわちメッセージは複数のメッセージ・ブロックに分割される。各メッセージ・ブロックは１と０の値を有するビットのシーケンスを含む。これは２進数Ｘと見なしてよい。暗号化を行うには、公開鍵ＫＰＵＢまたは秘密鍵ＫＰＲＩＶを指数として用いて２進数Ｘ（すなわち、メッセージ・ブロックの２進値）を累乗し、その結果を、関連する暗号化係数Ｎを法として減少させる。一般に、秘密にしたいメッセージを暗号化する場合は受信者の公開鍵ＫＰＵＢを用い、暗号化されたメッセージを解読する場合は受信者の秘密鍵ＫＰＲＩＶを用いる。場合によっては、実際上メッセージに署名するのに、メッセージ・ブロックを送信者の秘密鍵ＫＰＲＩＶで暗号化してよい。この場合、平文を回復するにはこの署名されたメッセージを送信者の公開鍵ＫＰＵＢで解読する。
【００２０】
ＲＳＡアルゴリズムでは、秘密鍵ＫＰＲＩＶの長さは一般に約２，０４８ビットである。メッセージ・ブロックと暗号化係数Ｎの語長は一般に同程度である。したがって、秘密鍵ＫＰＲＩＶで暗号化または解読を行うには２，０４８ビットのメッセージ・ブロックを２，０４８ビットの指数で累乗し、その結果を、別の２，０４８ビット数を法として減少させる。これらの計算を行うには大きな計算能力を必要とする。
【００２１】
大きな２進値を有する鍵でメッセージ・ブロックを暗号化し解読する際の複雑さを減らす方法として２つのアルゴリズムが用いられている。１つは逐次平方アルゴリズム（Ｓｕｃｃｅｓｓｉｖｅ Ｓｑｕａｒｅｓ Ａｌｇｏｒｉｔｈｍ）と呼ばれるもので、第１の大きな数を第２の大きな数で累乗するのに用いられる。もう１つのアルゴリズムはモジュロ減少若しくは還元アルゴリズム（Ｍｏｄｕｌｏ Ｒｅｄｕｃｔｉｏｎ Ａｌｇｏｒｉｔｈｍ）と呼ばれるもので、第２の大きな数を法として第１の大きな数を減少させるのに用いられる。本発明ではこれらの両アルゴリズムを修正した形で用いる。
【００２２】
逐次平方アルゴリズムはビットストリングＸを大きな数Ｙで累乗するのに用いられる。解読の場合は、ビットストリングＸは暗号化されたメッセージであり、累乗Ｙは解読鍵である。暗号化の場合は、ビットストリングＸは平文（ｐｌａｉｎｔｅｘｔ）メッセージ・ブロックであり、累乗Ｙは暗号化鍵である。ビットストリングＸの逐次平方を計算し、累乗Ｙ内の対応するビットの値に従って、これを累算値Ｚに掛ける。逐次平方をここではＸ１＝Ｘ１，Ｘ２＝Ｘ２，Ｘ３＝Ｘ４，．．．，
2004512570.tif 000003
で示す。逐次平方アルゴリズムでは、累乗Ｙの最下位ビット（Ｂ１で示す）はＸの１乗に対応し、第２ビットＢ２はＸの２乗に対応し、第３ビットＢ３はＸの４乗に対応し、以下同様にして最終ビットＢＬに到達する。累乗Ｙ内の対応するビットＢｎの値に従って、各逐次平方Ｘ１，Ｘ２，Ｘ３，．．．，Ｘｎを累算値Ｚに掛ける。詳しく述べると、累乗Ｙ内の対応するビットＢｎが１のときは、累算値Ｚに逐次平方を掛ける。累乗Ｙ内の対応するビットが０のときは、累算値Ｚに逐次平方を掛けない。逐次平方アルゴリズムを用いると、掛ける必要のある値の数は２２，０４８から２，０４８程度に減少する。ただし、ＸとＹの長さは２，０４８ビットである。
【００２３】
各掛け算または平方演算を行った後の累算値Ｚの語長は４，０９６ビット程度である。暗号化および解読においては、この累算値Ｚをモジュロ減少により２，０４８ビット長程度の値に減少させる。詳しく述べると、各平方演算の結果を、２，０４８の語長の暗号化係数Ｎを法として減少させる。これには累算値ＺがＮより小さくなるまで多数のＮの倍数を引く必要がある。引き算するＮの倍数の数は２２，０４８すなわち１０６００程度になり、これでは逐次引き算を行うことはできない。
【００２４】
モジュロ減少アルゴリズムは第２の大きな数を法として第１の大きな数を減少させるのに用いられる。モジュロ減少アルゴリズムでは、Ｎの逆数の近似値を、２進小数点の後の頭のゼロを除いて２，０４８有効ビットまで計算する。Ｎを法として４，０９６ビットのＺ値を減少させるたびに、ＮをＺから引く回数の近似値Ｔは式
2004512570.tif 000004
を用いて計算される。これはＺとＮの逆数の近似値との１回の長い掛け算である。次に積ＴｘＮを累算値Ｚから引くと、Ｚは必要な結果のＮ倍または２Ｎ倍以内に減少する。累算値Ｚから暗号化係数Ｎを更に１回または２回引いて残りがＮより小さいが負でない値になると、減少は完了する。モジュロ減少アルゴリズムに必要なのは、逐次引き算が１０６００回ではなく、長い掛け算が２回と引き算が２回である。
【００２５】
本発明では、非安全なプロセッサすなわち加速器１００を用いて、途中で秘密の情報を外部に漏らさずに大量の暗号計算を行う。本発明の或る実施の形態は、例えば或る値を秘密の指数で累乗するのに用いられる。したがって第１の実施の形態は、例えば、秘密鍵ＫＰＲＩＶまたはメッセージの平文を外部に漏らさずに、暗号化メッセージを解読するのに用いてよい。また本発明のこの実施の形態は、やはり秘密鍵ＫＰＲＩＶを外部に漏らさずに、秘密でないメッセージに秘密鍵ＫＰＲＩＶで署名するのに用いてよい。別の実施の形態は、秘密の値を秘密の指数で累乗するのに用いてよい。この実施の形態は、例えば秘密の情報または鍵を外部に漏らさずに、公開鍵ＫＰＵＢまたは秘密鍵ＫＰＲＩＶを用いて秘密の情報を暗号化するのに用いてよい。
【００２６】
本発明の第１の実施の形態では、秘密鍵ＫＰＲＩＶを秘密にしたまま暗号計算を行う。暗号計算は秘密鍵ＫＰＲＩＶでメッセージを暗号化または解読することを含む。秘密鍵ＫＰＲＩＶを保護しながら暗号化／解読に必要な処理の大部分をセキュリティ・モジュール２０の外部で行うため、秘密鍵を２つ以上の部分（ここでは部分値と呼ぶ）に分割する。第１の例示の実施の形態では、秘密鍵ＫＰＲＩＶを修正して修正秘密鍵ＫＰＲＩＶＭ（第１の部分値）と標識ＩＮＤＩＣ（第２の部分値）とを生成する。セキュリティ・モジュール２０は修正秘密鍵ＫＰＲＩＶＭとビットストリングＸとをセキュリティ・モジュール２０の外部の非安全なプロセッサ（加速器１００など）に与える。
【００２７】
加速器１００はＫＰＲＩＶＭに基づいて必要な計算の大部分を行い、生成された値（ここでは第１の積Ｐ１と呼ぶ）をセキュリティ・モジュール２０に送る。また、加速器１００はセキュリティ・モジュール２０が計算を完了するのに必要な他の値をセキュリティ・モジュール２０に送る。次に、セキュリティ・モジュール２０は標識ＩＮＤＩＣとビットストリングＸに基づいていくつかの追加計算を行い、第２の値（ここでは第２の積Ｐ２と呼ぶ）を作る。セキュリティ・モジュール２０は第１の積Ｐ１と第２の積Ｐ２とを適当な方法で結合して最終積ＰＦを作る。解読の場合は、最終積ＰＦはオリジナル平文である。暗号化の場合は、最終積ＰＦは生成された暗号文である。
【００２８】
図３は、或る実施の形態で加速器１００と安全なプロセッサ３０が行う処理を示す機能ブロック図である。加速器１００は、平方数発生器１０２と、累算器１０４と、遅延回路１０６とを備える。平方数発生器１０２は供給されるビットストリングＸを入力として受ける。ビットストリングＸは秘密鍵ＫＰＲＩＶで解読する暗号文か、または秘密鍵ＫＰＲＩＶで暗号化する平文を含んでよい。平方数発生器１０２は供給されたビットストリングＸを繰り返し平方して、各逐次平方を、暗号化係数Ｎを法として減少させる。逐次平方をＸ１，Ｘ２，．．．，Ｘｎで示す。暗号化係数Ｎは供給された秘密鍵ＫＰＲＩＶに関連する係数である。平方数発生器１０２の出力は各繰返し中に累算器１０４に与えられる。また平方数発生器１０２の出力は各繰返し中に安全なプロセッサ３０に返される。
【００２９】
乗法累算器１０４は開始値１に初期化される。上に述べたように、乗法累算器１０４は平方数発生器１０２から出力される逐次平方Ｘ１，Ｘ２，Ｘ３，Ｘ４，．．．，Ｘｎを受ける。また乗法累算器１０４は、遅延回路１０６により１サイクル遅延した累算値Ｚを第２の入力に受ける。乗法累算器１０４は、修正秘密鍵ＫＰＲＩＶＭの対応するビットＢｎの値に従って、前の累算値Ｚに平方数発生器１０２の出力を掛ける。このようにして、修正秘密鍵ＫＰＲＩＶＭのビットは乗法累算器１０４の動作を制御する。
【００３０】
修正鍵の対応するビットＢｎが０のときは、累算値Ｚに１を掛ける、すなわち、掛け算を行う必要はない。修正秘密鍵ＫＰＲＩＶＭの対応するビットＢｎが１のときは、乗法累算器１０４は平方数発生器１０２から出力される対応する逐次平方Ｘｎを前の値Ｚに掛けてＺの新しい値を計算する。各掛け算の後、生成されたＺ値を、暗号化係数Ｎを法として減少させる。このプロセスを修正鍵ＫＰＲＩＶＭのビット毎に、最下位ビットから始めて最上位ビットまで繰り返す。Ｚの最終値は第１の積Ｐ１であり、これをセキュリティ・モジュール２０に入力して暗号化計算を完了する。
【００３１】
また図３はセキュリティ・モジュール２０内の安全なプロセッサ３０が実行するプロセスを示す。これは加速器１００が開始した計算を完了する。プロセッサ３０は選択乗算器４４と積ノード４６を備える。選択乗算器４４は、平方数発生器１０２から出力される逐次平方Ｘ１，Ｘ２，．．．，Ｘｎを受ける。また選択乗算器４４は後で説明する標識ＩＮＤＩＣを受ける。選択乗算器４４の動作は標識ＩＮＤＩＣにより制御される。ＩＮＤＩＣ内のビットと逐次平方Ｘｎの数との間には１対１の対応がある。詳しく述べると、選択乗算器４４は、標識ＩＮＤＩＣ内のビット値１に対応する逐次平方Ｘｎは選択し、ビット値０に対応する逐次平方は捨てる。選択された逐次平方ＸｎはＲＡＭ４０内に保存する。このようにして、標識ＩＮＤＩＣは平方数発生器１０２から出力される逐次平方Ｘｎを選択し、残りを捨てる。
【００３２】
選択乗算器４４は選択された逐次平方Ｘｎの積を計算し、ここで第２の積Ｐ２と呼ぶ値を作って積ノード４６に送る。積ノード４６は第２の積Ｐ２と、加速器１００が生成した第１の積Ｐ１とを掛けて最終積ＰＦを生成する。最終積ＰＦは、暗号化操作から生成された平文（解読）または暗号化文（暗号化）を含む。または、加速器１００から出力された第１の積Ｐ１に選択された逐次平方Ｘｎを一度に１つずつ掛けて最終積ＰＦを計算してよい。このアプリケーションでは、第１の積Ｐ１と第２の積Ｐ２との掛け算は、第１の積Ｐ１と第２の積Ｐ２を含む要素との掛け算を含む。また、ここで用いる第２の積Ｐ２の決定または計算は第２の積Ｐ２を含む要素の決定または計算を含む。
【００３３】
図４は、秘密にする受信者の秘密鍵ＫＰＲＩＶを用いて、暗号化されたメッセージを解読するステップを示す。ステップ４００で、セキュリティ・モジュール２０は秘密鍵ＫＰＲＩＶを決定する。秘密鍵ＫＰＲＩＶを外部に漏らさずに外部の加速器１００を用いるため、元の秘密鍵ＫＰＲＩＶの選択されたビットを変えることにより秘密鍵ＫＰＲＩＶを修正して、修正秘密鍵ＫＰＲＩＶＭを生成する（ステップ４０２）。次に、秘密鍵ＫＰＲＩＶを変更したことを示す標識ＩＮＤＩＣを形成する（ステップ４０２）。標識ＩＮＤＩＣは秘密鍵ＫＰＲＩＶと同じビット数を含む。
【００３４】
修正秘密鍵ＫＰＲＩＶＭと標識ＩＮＤＩＣを計算するのに種々の方法を用いることができる。例えば、２０４８ビット長を有する秘密鍵ＫＰＲＩＶの平均１０２４ビット位置は値「１」を有する。この中の２０ビット位置を「１」から「０」に変更してＫＰＲＩＶＭを形成する。この場合の標識ＩＮＤＩＣは秘密鍵ＫＰＲＩＶと同じ長さのビットストリングを含み、秘密鍵ＫＰＲＩＶ内の変更されたビットに対応する各ビット位置は「１」で、その他の位置はゼロ０である。
【００３５】
いくつかの１をゼロで置き換え、またはいくつかのゼロを１で置き換えるなど、他の方法を用いてＫＰＲＩＶと標識ＩＮＤＩＣを生成してよい。１つの方法は、まずＩＮＤＩＣ内の少数のビットが２進数の１を含むようにランダムに選択して標識ＩＮＤＩＣを構築し、次にボロー繰上げ伝搬（ｂｏｒｒｏｗ ｐｒｏｐａｇａｔｉｏｎ）で秘密鍵ＫＰＲＩＶからＩＮＤＩＣを引いて修正秘密鍵ＫＰＲＩＶＭを生成する。同様にして、ＫＰＲＩＶ内のビットをランダムに選択し、「１」から「０」にまたは「０」から「１」に変換して、ＫＰＲＩＶより小さい値を持つ修正秘密鍵ＫＰＲＩＶＭを生成する。次に、修正秘密鍵ＫＰＲＩＶＭを元の秘密鍵ＫＰＲＩＶから引いて標識ＩＮＤＩＣを生成する。一般に、修正秘密鍵ＫＰＲＩＶＭと標識ＩＮＤＩＣは、修正秘密鍵ＫＰＲＩＶＭと標識ＩＮＤＩＣとの和が秘密鍵ＫＰＲＩＶの値に等しくなるように選択する。
【００３６】
解読では、Ｘで示す暗号化されたビットストリングを、修正秘密鍵ＫＰＲＩＶＭおよび係数Ｎと共に加速器１００に送る（ブロック４０４）。加速器１００は、逐次平方アルゴリズムとモジュロ減少アルゴリズムとを用いて、修正秘密鍵ＫＰＲＩＶＭとビットストリングＸの関数として第１の積Ｐ１を計算する。乗法累算器１０４の値Ｚを開始値「１」に設定して乗法累算器１０４を初期化する（ブロック４０６）。次に、修正秘密鍵ＫＰＲＩＶＭを用いてＸのモジュロ累乗により第１の積Ｐ１を計算する（ブロック４０８）。修正秘密鍵ＫＰＲＩＶＭ内のビットＢｎ毎に、ＫＰＲＩＶＭ内の現在のビットＢｎの値に従って、暗号化されたビットストリングＸの対応する逐次平方Ｘｎを値Ｚに掛ける。
【００３７】
ビットＢｎの値が「１」の場合は、累算器１０４は式
2004512570.tif 000005
に従ってＺを増分する。ただし、Ｘは供給されるビットストリングの値、ｎはビット位置、
2004512570.tif 000006
はＫＰＲＩＶＭのビットＢｎに対応するＸの逐次平方である。Ｂｎが「０」の場合は、累算値Ｚは変わらない。修正秘密鍵ＫＰＲＩＶＭ内のビットＢｎ毎に累算プロセスを続ける。ＫＰＲＩＶＭ内の最後のビットＢＬを処理した後、Ｚの最終値を第１の積Ｐ１としてセキュリティ・モジュール２０に送る（ブロック４１０）。
【００３８】
各逐次平方Ｘｎ（例えばＸ１，Ｘ２，．．．，Ｘｎ）は外部の加速器１００からセキュリティ・モジュール２０に返される。変造防止チップ２０は、逐次平方Ｘｎのどれを保存してどれを捨てたかが外部に分からないようにして、標識ＩＮＤＩＣ内の「１」に対応する逐次平方Ｘｎを保存して残りを捨てる。次に、安全なプロセッサ３０は保存された逐次平方Ｘｎを互いに掛けて、第２の積Ｐ２を生成する（ブロック４１２）。
【００３９】
外部の加速器１００から出力された第１の積Ｐ１に第２の積Ｐ２を掛けて最終積ＰＦを生成する（ステップ４１４）。この最終ステップは安全なプロセッサ３０が実行する。同等であるが、第１の積Ｐ１に、保存された逐次平方Ｘｎをそれぞれ独立に掛けても、最終積ＰＦを生成することができる。この場合は、第２の積Ｐ２を別に計算する必要がない。
【００４０】
外部の計算を観察する関係者には修正秘密鍵ＫＰＲＩＶＭ内のどの「０」が元は「１」だったかが分からない。２０個の「１」を「０」に変える方法の数は１０４２程度もあるので、試行錯誤で正しく決定することはできない。それにもかかわらず、必要な掛け算の９８％以上を外部の加速器１００で行ってよい。
【００４１】
図５は、５ビットのＫＰＲＩＶと５ビットのビットストリングＸとを用いた、本発明に係る暗号計算（モジュロ減少なし）の例を示す。図５の例に示すように、ＫＰＲＩＶ＝１０１１１＝２３である。修正秘密鍵ＫＰＲＩＶＭは位置２と３のビットを「１」から「０」に変えることにより生成される。ただし、ビット位置１が最下位ビットに対応する。したがって、修正秘密鍵ＫＰＲＩＶＭ＝１０００１＝１７である。指標ＩＮＤＩＣの値１はビット位置２と３にあり、その他は０である。したがって、ＩＮＤＩＣ＝６である。
【００４２】
ＫＰＲＩＶＭの最下位ビットの値は「１」である。したがって、乗法累算器１０４はＺの開始値（すなわち、１）にＸを掛ける。したがって、最初の繰返しの後のＺの終値はＸである。ＫＰＲＩＶＭの第２ビットは０である。したがって、第２の繰返しの間は累算値Ｚに掛けない。同様に、ＫＰＲＩＶＭのビット３と４はゼロなので、これらの各繰返しの間はＺの値は一定である。位置５のビットは「１」なので、累算値Ｚは式
2004512570.tif 000007
に従って増分されて、最終値５．８ｘ１０２３が生成される。これは最終ビットなので、加速器１００はＺを第１の積Ｐ１としてセキュリティ・モジュール２０に送る。
【００４３】
セキュリティ・モジュール２０は、平方数発生器１０２から返された逐次平方Ｘｎの中の、指標ＩＮＤＩＣ内の値「１」を含む各ビット位置に対応するものを決定する。この例では、逐次平方Ｘ２＝Ｘ２とＸ３＝Ｘ４がＩＮＤＩＣから選択される。したがって、第２の積Ｐ２はＸ２＊Ｘ３であって、これは２．４４ｘ１０８に等しい。最終積ＰＦは第１の積Ｐ１に第２の積Ｐ２を掛けて決定し、ＰＦの最終値は１．４２ｘ１０３２に等しい。
【００４４】
本発明の第２の実施の形態は、秘密の平文を外部に漏らさずに、公開鍵または秘密鍵で秘密の平文を暗号化するのに用いてよい。ＲＳＡアルゴリズムを用いて平文を暗号化するには、秘密の平文を公開鍵または秘密鍵で表される値で累乗しなければならない。本発明では、これはこの累乗を実行する非安全なプロセッサに秘密の平文を示さずに行われる。第２の実施の形態では、第１の積Ｐ１は加速器１００が計算し、第２の積Ｐ２はセキュリティ・モジュール２０内で計算する。セキュリティ・モジュール２０は第１の積Ｐ１と第２の積Ｐ２とを結合して最終積ＰＦを生成する。第２の実施の形態における第１の積Ｐ１は、セキュリティ・モジュール２０内で計算された第３の積Ｐ３と、第４の積Ｐ４との関数である。第３の積は累算器１０４を初期化するのに用いられる。
【００４５】
第２実施の形態では、秘密鍵ＫＰＲＩＶをまず２つの部分値（ここでは短い部分ＰＳＨＯＲＴと長い部分ＫＬＯＮＧと呼ぶ）に分ける。短い部分ＰＳＨＯＲＴは、例えば秘密鍵ＫＰＲＩＶの最下位の数ビットで構成する。長い部分ＫＬＯＮＧは、この場合はＫＰＲＩＶの最上位の数ビットで構成するセグメントである。例として、秘密鍵ＫＰＲＩＶが２，０４８ビットを含む場合は、１６個の最下位ビットで短い部分ＫＳＨＯＲＴを構成し、２，０３２個の最上位ビットで長い部分ＫＬＯＮＧを構成してよい。次に長い部分ＫＬＯＮＧを上に述べたように修正して、修正された長い部分ＫＬＯＮＧＭと標識ＩＮＤＩＣとを生成する。したがって、秘密鍵ＫＰＲＩＶはＫＳＨＯＲＴとＫＬＯＮＧＭとＩＮＤＩＣの３つの部分値に分割され、その和はＫＰＲＩＶに等しい。
【００４６】
最初に短い部分ＫＳＨＯＲＴを用いて秘密の平文Ｘをセキュリティ・モジュール２０内で暗号化して第３の積Ｐ３を生成する。この第３の積Ｐ３を用いて乗法累算器１０４を初期化する。これをここでは開始値と呼ぶ。これは、秘密鍵ＫＰＲＩＶの短い部分ＫＳＨＯＲＴを用いて秘密の平文Ｘの累乗を法とする（モジュロ累乗する）ことにより行う。モジュロ累乗は、前に説明した逐次平方アルゴリズムとモジュロ減少アルゴリズムとを用いて行ってよい。必然的にこのプロセスでは、安全なプロセッサ３０はＸの最初の１６の逐次平方を計算する必要がある。計算された１６の逐次平方の最後（Ｘ１６で示す）は、平文を３２，７６８乗し、暗号化係数Ｎを法として減少させたものである。
【００４７】
値Ｘ１６を加速器１００に与えると、加速器１００はＸ１６を用いて平方数発生器１０２を初期化する。平方数発生器１０２はＸ１６を逐次平方することにより、残り２，０３２個のＸの逐次平方を計算する。第３の積Ｐ３の値に初期化された乗法累算器１０４は、前に説明した逐次平方アルゴリズムとモジュロ減少アルゴリズムとを用いて、第３の積Ｐ３と秘密鍵ＫＰＲＩＶの修正された長い部分ＫＬＯＮＧＭとの関数として第１の積Ｐ１を計算する。したがって本発明では、秘密の平文Ｘを外部に開放するのではなく、Ｘ１６だけを開放する。Ｘ１６に基づいてＸを計算するには１／３２，７６８の根演算が必要であり、これはモジュロ算術では実際的に不可能である。したがって、Ｘ１６とＰ３を外部に開放してもＸを開放したことにはならない。
【００４８】
図６は、本発明の第２の実施の形態に係る暗号化の方法を示す。秘密鍵ＫＰＲＩＶの値を決定してセキュリティ・モジュール２０内に記憶する（ブロック６００）。次に、秘密鍵ＫＰＲＩＶを２つの部分に分割することにより、更に２つの値、ＫＳＨＯＲＴとＫＬＯＮＧとを決定する（ブロック６０２）。ＫＳＨＯＲＴは１６個の最下位ビットを含み、ＫＬＯＮＧは２，０３２個の最上位ビットを含む。次に、前に説明した方法で値ＫＬＯＮＧを修正して、ＫＬＯＮＧＭと標識ＩＮＤＩＣとを生成する（ブロック６０４）。
【００４９】
値ＫＳＨＯＲＴをセキュリティ・モジュール２０内に保持し、これを用いて秘密の平文（Ｘで示す）を累乗して第３の積Ｐ３を生成する。プロセッサ３０は、逐次平方アルゴリズムとモジュロ減少アルゴリズムとを用いて、プロセッサ３０によりセキュリティ・モジュール２０内で値ＸをＫＳＨＯＲＴ乗して、第３の積Ｐ３と値Ｘ１６＝Ｘ６５５３６を生成する（ブロック６０６）。第３の積はＸをＫＳＨＯＲＴ乗し、Ｎを法として減少させたものである（例えば、Ｐ１＝ＸＫＳＨＯＲＴｍｏｄ　Ｎ）。値ＫＬＯＮＧＭとＰ３とＸ１６を加速器１００に出力する（ブロック６１０）。乗法累算器１０４を値Ｐ３に初期化する（ブロック６１２）。ここから、プロセスは上に説明した図４と同様にして続く。平方数発生器１０２は、Ｘ１７から始めてＸ２０４８までＸの逐次平方Ｘｎを計算する。各逐次平方Ｘｎは前の値を平方することにより計算する。したがって、Ｘ１７はＸ１６を平方し、Ｘ１８はＸ１７を平方し、というようにしてＸ２０４８まで行う。各逐次平方、例えば、Ｘ１７，Ｘ１８，．．．，Ｘｎはセキュリティ・モジュール２０に返され、セキュリティ・モジュール２０は指標ＩＮＤＩＣ内の１に対応するこれらの逐次平方Ｘｎを保存して第２の積Ｐ２を計算する。
【００５０】
逐次平方Ｘｎは累算器１０４にも入力される。前に説明したように、ＫＬＯＮＧＭ内の対応するビットＢｎが１のときは累算器１０４は累算値Ｚに逐次平方Ｘｎを掛ける。実際には、乗法累算器１０４は第３の積Ｐ３に第４の積Ｐ４を掛ける。その結果はビットストリングＸのＫＬＯＮＧＭ乗である。累算器１０４の最終値（第１の積Ｐ１で示す）はセキュリティ・モジュール２０に返される。セキュリティ・モジュール２０は第２の積Ｐ２を計算する。これはビットストリングＸを標識ＩＮＤＩＣで累乗したものである。最終積ＰＦは第１の積Ｐ１に第２の積Ｐ２を掛けて生成する。
【００５１】
理解されるように、ビットストリングＫＬＯＮＧＭとＫＳＨＯＲＴは第１の実施の形態における修正暗号鍵に等しい。すなわち、ＫＬＯＮＧＭ＋ＫＳＨＯＲＴ＝第１の実施の形態のＫＰＲＩＶＭである。したがって、第２の実施の形態における第１の積Ｐ１はＫＬＯＮＧＭとＫＳＨＯＲＴの関数として表すこともできる。より特定して述べると、第１の積Ｐ１はＫＬＯＮＧＭとＫＳＨＯＲＴに式
2004512570.tif 000008
のように関係する。
ただし、
2004512570.tif 000009
は第３の積Ｐ３、
2004512570.tif 000010
は第４の積Ｐ４である。
【００５２】
上のプロトコルは、秘密鍵ＫＰＲＩＶを用いて秘密の平文の暗号化するときも、秘密鍵ＫＰＲＩＶを用いて暗号文を普通に解読するときも安全である。通信端末１０を暗号化と解読の両方に用いる場合は、両方の演算に同じ修正秘密鍵ＫＰＲＩＶＭを用いなければならない。
【００５３】
図７は、５ビットの秘密鍵ＫＰＲＩＶと５ビット値のＸを用いる、第２の実施の形態に係るモジュロ減少なしの暗号計算の例である。図７の例に示すように、ＫＰＲＩＶは１０１１１＝２３である。ＫＬＯＮＧＭは１００００＝１６である。ＫＳＨＯＲＴは０００１１＝３である。標識ＩＮＤＩＣは００１００＝４である。
【００５４】
累算器１０４の開始値は、セキュリティ・モジュール２０がビットストリングＸの値をＫＳＨＯＲＴ乗して計算する。これは１５，６２５に等しく、また第３の積Ｐ３である。この例のＫＳＨＯＲＴは、最初の２ビットはＫＰＲＩＶと同じで残りのビットは０に設定される。セキュリティ・モジュール２０はＸの最初の２つの逐次平方、すなわち、Ｘ１＝ＸとＸ２＝Ｘ２も計算する。最後の逐次平方Ｘ２を用いて平方数発生器１０２を初期化する。次に加速器１００は第１の積Ｐ１を、第３の積Ｐ３と秘密鍵ＫＰＲＩＶの修正された長い部分ＫＬＯＮＧＭとの関数として計算する。この例では、ＫＬＯＮＧＭの最初の４ビットは０である。したがって、Ｘの最初の４つの逐次平方は累算値Ｘに掛けない。ＫＬＯＮＧＭの最終ビットはＸ１６に対応し、値１を有する。したがって、累算値Ｚに第４の積Ｐ４である２．３２ｘ１０２２を掛けて、第１の積Ｐ１として３．６４ｘ１０２６が得られる。
【００５５】
第１の積Ｐ１はセキュリティ・モジュール２０に入力される。セキュリティ・モジュール２０は第２の積Ｐ２を計算する。これはこの例では３９０，６２５である。第１の積Ｐ１と第２の積Ｐ２を掛けて最終積ＰＦを生成する。これは１．４２ｘ１０３２に等しい。
【００５６】
第２の実施の形態では、秘密鍵ＫＰＲＩＶは実質的に、短いすなわち最下位部分ＫＳＨＯＲＴと、修正された最上位部分ＫＬＯＮＧＭと、標識ＩＮＤＩＣの３つの部分に分割される。最下位部分ＫＳＨＯＲＴを用いる累乗はセキュリティ・モジュール２０内で行い、修正された最上位部分ＫＬＯＮＧＭによる累乗（大量の掛け算を含む）は加速器１００で行う。当業者が理解するように、秘密鍵を分割する他の方法を用いても同じ目的を達成することができる。
【００５７】
一例として、上に説明したプロセスを次の秘密鍵に適用する例を示す。
ＫＰＲＩＶ 　　　１１０１１００１０１１１０１
ＫＬＯＮＧ 　　　１１０１１００１０１００００
ＫＳＨＯＲＴ　　　００００００００００１１０１
ＫＬＯＮＧＭ　　　１１０００００００１００００
ＩＮＤＩＣ ０００１１００１００００００
【００５８】
この場合、秘密鍵ＫＰＲＩＶは１６（ＫＬＯＮＧＭ　ＯＲ　ＩＮＤＩＣ）＋ＫＳＨＯＲＴで表すことができる。しかし、次のように秘密鍵ＫＰＲＩＶを別の方法で分割することができる。
ＫＰＲＩＶ 　　　１１０１１００１０１１１０１
ＫＬＯＮＧ 　　　１１０１１００１０１００００
ＫＳＨＯＲＴ　　　００００００００００１１０１
ＫＬＯＮＧＭ　　　１１０１０１１００１００００
ＩＮＤＩＣ ００００００１１００００００
この場合は、秘密鍵ＫＰＲＩＶは１６（ＫＬＯＮＧＭ＋ＩＮＤＩＣ）＋ＫＳＨＯＲＴで表すことができる。
【００５９】
後者の式は前者を含むが、ＫＬＯＮＧを修正する別の方法が可能である。すなわち、第１の例では、ＫＬＯＮＧで変更できるのは、２進「１」から２進「０」へ、だけである。第２の例では、順繰下げ伝搬（ｆｏｒｗａｒｄ ｂｏｒｒｏｗ ｐｒｏｐａｇａｔｉｏｎ）でその位置から２進「１」を引くことにより、ＫＬＯＮＧ内の「０」を「１」に置き換えることができる。同様に、ＫＬＯＮＧ内では、順桁上げ伝搬（ｆｏｒｗａｒｄ ｃａｒｒｙ ｐｒｏｐａｇａｔｉｏｎ）でその位置に「１」を加えることにより「１」を「０」に変換することができる。ＫＬＯＮＧに対して行ったこと（桁上げ／繰下げ伝搬でビット位置を増分または減分する）の全ての逆を標識ＩＮＤＩＣに対して行うので、ＫＬＯＮＧＭとＩＮＤＩＣとの和は非修正の長い部分ＫＬＯＮＧに常に等しい。したがって、「１」を「０」に変えるには、桁上げ／繰下げ伝搬を行わずにＫＬＯＮＧ内で減分しかつＩＮＤＩＣ内の対応する位置を増分するか、またはＫＬＯＮＧ内で桁上げ伝搬で増分しかつＩＮＤＩＣ内の対応する位置を繰下げ伝搬で減分するかでよい。逆に、ＫＬＯＮＧ内の「０」を「１」に変換するには、ＫＬＯＮＧ内のその位置を増分し、ＩＮＤＩＣ内の対応するビット位置を減分する（繰下げ伝搬で）か、またはＫＬＯＮＧ内のその位置を減分し（桁上げ伝搬で）しかつＩＮＤＩＣ内の対応するビット位置を増分してよい。
【００６０】
公開鍵ＫＰＵＢが関わる演算に非安全なプロセスを１００を用いる必要はない。なぜなら、公開鍵は一般に秘密鍵よりはるかに短い（１６ビットより少ない）からである。しかし本発明は、秘密の平文を公開鍵ＫＰＵＢの最下位部分で累乗を行い、公開鍵ＫＰＵＢの最上位部分で累乗を完了することにより、公開鍵ＫＰＵＢで平文を暗号化するのに用いてよい。次に、非安全なプロセッサ１００から返した結果とセキュリティ・モジュール２０内で計算した値とを結合してよい。公開鍵ＫＰＵＢで平文を暗号化する場合は、上に述べたように公開鍵ＫＰＵＢのビットを修正する必要はない。なぜなら、公開鍵ＫＰＵＢはすでに公開されているからである。したがって、本発明の第３の実施の形態における平文の暗号化は、暗号化鍵を２つの部分に分解し、安全なプロセッサ内で暗号化演算の第１の部分を行い、非安全なプロセッサ内で暗号化演算の第２の部分を行い、その結果を安全なプロセスが内で結合することにより行う。
【００６１】
本発明の重要な特徴から逸れることなく、ここに説明した方法以外の特定の方法で本発明を実行することができる。したがって、本発明はあらゆる点において例と見なすべきであって制限するものではなく、特許請求の範囲の意味と同等の範囲内の全ての変更はここに含まれるものとする。
【図面の簡単な説明】
【図１】
非安全な通信チャネルにより通信する、本発明に係る通信端末を示す略図である。
【図２】
図１の通信端末内で用いられるセキュリティ・モジュールの略図である。
【図３】
非安全なプロセッサと安全なプロセッサにより行われる処理を示す機能的ブロック図である。
【図４】
本発明の１つの実施の形態に係る、暗号計算を実行する方法を示す流れ図である。
【図５】
本発明に係る例示の計算を示す図である。
【図６】
本発明の第２の実施の形態に係る、暗号計算を実行する別の方法を示す流れ図である。
【図７】
第２の実施の形態に係る例示の計算を示す図である。
【図１】
2004512570.tif 000011
【図２】
2004512570.tif 000012
【図３】
2004512570.tif 000013
【図４】
2004512570.tif 000014
【図５】
2004512570.tif 000015
【図６】
2004512570.tif 000016
【図７】
2004512570.tif 000017
【国際公開パンフレット】
2004512570.tif 000018
2004512570.tif 000019
2004512570.tif 000020
2004512570.tif 000021
2004512570.tif 000022
2004512570.tif 000023
2004512570.tif 000024
2004512570.tif 000025
2004512570.tif 000026
2004512570.tif 000027
2004512570.tif 000028
2004512570.tif 000029
2004512570.tif 000030
2004512570.tif 000031
2004512570.tif 000032
2004512570.tif 000033
2004512570.tif 000034
2004512570.tif 000035
2004512570.tif 000036
2004512570.tif 000037
2004512570.tif 000038
2004512570.tif 000039
2004512570.tif 000040
2004512570.tif 000041
2004512570.tif 000042
2004512570.tif 000043
2004512570.tif 000044
2004512570.tif 000045
2004512570.tif 000046
2004512570.tif 000047
2004512570.tif 000048
2004512570.tif 000049
2004512570.tif 000050
2004512570.tif 000051
2004512570.tif 000052
2004512570.tif 000053
2004512570.tif 000054
2004512570.tif 000055
2004512570.tif 000056
【国際公開パンフレット（コレクトバージョン）】
2004512570.tif 000057
2004512570.tif 000058
【国際調査報告】
2004512570.tif 000059
2004512570.tif 000060