(57)【特許請求の範囲】
【請求項１】
秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行う暗号装置であって、
乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成する演算手段を具えることを特徴とする、
暗号装置。
【請求項２】
秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行う暗号装置であって、
乱数に従って、前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成する演算手段を具えることを特徴とする、
暗号装置。
【請求項３】
前記一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置と前記他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、前記ｕビット・シーケンスにおけるｈ個のビット位置に対応付けられるものである、請求項１または２に記載の暗号装置。
【請求項４】
情報処理装置において使用するための、秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行うプログラムであって、
乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成するステップを実行させるよう動作可能なプログラム。
【請求項５】
情報処理装置において使用するための、秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行うプログラムであって、
乱数に従って、前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成するステップを実行させるよう動作可能なプログラム。
【請求項６】
ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行う方法であって、
前記ウィンドウ・シーケンス生成手段を用いて、乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを含み、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記演算手段を用いて、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成するステップを含む、方法。
【請求項７】
ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行う方法であって、
前記ウィンドウ・シーケンス生成手段を用いて、乱数に従って、前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを含み、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
さらに、前記演算手段を用いて、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成するステップを含む、方法。
【請求項８】
秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行う暗号装置であって、
前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成する演算手段を具える、暗号装置。
【請求項９】
秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行う暗号装置であって、
前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成する演算手段を具える、暗号装置。
【請求項１０】
さらに、前記ウィンドウ・シーケンスのビット数から前記同じ値のビット数を減算したビット数を有する取り得るシーケンスをインデックスとして有し、前記インデックスに対応付けられる前記ウィンドウ・シーケンスの取り得るシーケンスに従って計算されたエントリ値を有するルックアップ・テーブルを生成する手段を具える、請求項８または９に記載の暗号装置。
【請求項１１】
前記演算手段は、前記導出されたウィンドウ・シーケンスの前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いて、テーブルをルックアップすることによって、前記演算を行うものである、請求項８または９に記載の暗号装置。
【請求項１２】
前記導出する手段は、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける対応する所定の位置に配置された前記ウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ウィンドウ・シーケンスを導出するものである、請求項８または９に記載の暗号装置。
【請求項１３】
情報処理装置において使用するための、秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行うプログラムであって、
前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成するステップを実行させるよう動作可能なプログラム。
【請求項１４】
情報処理装置において使用するための、秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行うプログラムであって、
前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成するステップを実行させるよう動作可能なプログラム。
【請求項１５】
ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて指数剰余演算による公開鍵暗号処理を行う方法であって、
前記ウィンドウ・シーケンス生成手段を用いて、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記演算手段を用いて、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或る値ａに対して乗算と２乗算とを実行する演算を行って、処理済みデータｖ＝ａｄ（ｍｏｄ  ｎ）（ｎは正の整数）を生成するステップを含む、方法。
【請求項１６】
ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて点のスカラー倍算による公開鍵暗号処理を行う方法であって、
前記ウィンドウ・シーケンス生成手段を用いて、前記公開鍵暗号のための或るスカラー値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に対応付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記演算手段を用いて、前記導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って別の或るベクトル値Ａに対して加算、減算および２倍算とを実行する演算を行って、処理済みデータＶ＝ｄＡを生成するステップを含む、方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号処理の分野に関し、特に、ＲＳＡおよび楕円曲線暗号のような公開鍵暗号のためのプロセッサにおけるＳＰＡおよびＤＰＡのような電力解析攻撃を防止する耐タンパ（tamper-proof）暗号化／復号に関する。
【０００２】
【発明の背景】
暗号方式には一般的に公開鍵暗号方式と共通鍵暗号方式が含まれる。公開鍵暗号方式は、暗号化と復号に異なる鍵（キー）を用いる。典型的には、公開鍵を用いて平文（plaintext）が暗号化され、秘密鍵を用いて暗号文（ciphertext）が復号され、それによって暗号文が安全に送信できる。または、秘密鍵を用いて平文が暗号化され、公開鍵を用いて暗号文が復号され、それによって平文を暗号化したユーザが識別される。図１は、スマートカードのような暗号デバイスにおける秘密鍵を用いた暗号化／復号の構成の例を示している。図１において、暗号デバイスは、その内部の暗号化／復号ユニットにおいて周知の形態で秘密鍵を用いて入力平文／暗号文メッセージを処理して出力暗号文／平文メッセージを供給する。
【０００３】
公開鍵暗号の１つのタイプであるＲＳＡ暗号のためのプロセッサにおいては、指数剰余演算（modular exponentiation）が行われる。指数剰余演算は、指数ｄ、平文／暗号文ａおよび公開鍵ｎに対して、ｖ＝ａｄ（ｍｏｄ  ｎ）を満たす暗号文／平文ｖを生成する。例えば、ＲＳＡ暗号による署名生成において、暗号文ｖ＝ad （ｍｏｄ  ｎ）が秘密鍵ｄを用いて指数剰余演算で生成される。
【０００４】
バイナリ・メソッド（２進方法）を用いた指数剰余演算は、２進値ｄについて、ＭＳＢ（最上位ビット）からＬＳＢ（最下位ビット）まで順に２乗とａの乗算を実行することによって、ｖを求める。例えば、ｄ＝２１＝２４＋２２＋２０＝（１０１０１）２についてｖを求めるとき、最初のＭＳＢ“１”に対して初期値ｖ＝１にａの乗算を実行してｖ＝ａを生成し、次のＭＳＢ“０”に対してそのｖに２乗（２で累乗）を実行してｖ＝ａ２を生成し、次のビット“１”に対してそのｖに２乗とａの乗算を実行してｖ＝（ａ２）２×ａを生成し、次のＭＳＢ“０”に対してそのｖに２乗を実行してｖ＝（（ａ２）２×ａ）２を生成し、ＬＳＢ“１”に対してそのｖに２乗とａの乗算を実行して、ｖ＝（（（ａ２）２×ａ）２）２×ａ＝ａ（２∧４）＋（２∧２）＋（２∧０）を生成する。ここで、２∧ｋ＝２ｋである。
【０００５】
公開鍵暗号の別のタイプである楕円曲線暗号のためのプロセッサにおいては、スカラー倍算が行われる。点のスカラー倍算は、スカラー値ｄ、および楕円曲線上の点Ａに対して、Ｖ＝ｄＡを満たす点Ｒを求める。例えば、楕円曲線暗号におけるDiffe-Hellman（ディッフィー・ヘルマン）鍵配送において、Ｖ＝ｄＡで表される点Ｒが秘密鍵ｄを用いてスカラー倍算で生成される。
【０００６】
ＲＳＡ暗号における乗算剰余ｃ＝ａ×ｂ（ｍｏｄ  ｎ）、２乗剰余ｃ＝ａ２および指数剰余ｃ＝ａｘ（ｍｏｄ  ｎ）は、楕円曲線暗号における点の加算Ｃ＝Ａ＋Ｂ、点の２倍算Ｃ＝２Ａおよび点のスカラー倍算Ｃ＝ｘＡにそれぞれ対応する。
【０００７】
バイナリ・メソッドを用いた点のスカラー倍算は、２進値ｄについて、ＭＳＢからＬＳＢまで順に点の２倍算と点の加算を実行することによって、Ｖを求める。例えばｄ＝２１＝２４＋２２＋２０＝（１０１０１）２についてＶを求めるとき、最初のＭＳＢ“１”に対して初期値Ｖ＝Ｏ（無限遠点）にＡの加算を実行してＶ＝Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝Ａ×２を生成し、次のビット“１”に対してそのＶに２倍算とＡの加算を実行してＶ＝（Ａ×２）×２＋Ａを生成し、次のビット“０”に対してそのＶに２倍算を実行してＶ＝（（Ａ×２）×２＋Ａ）×２を生成し、ＬＳＢ“１”に対してそのＶに２倍算とＡの加算を実行して、Ｖ＝（（（Ａ×２）×２＋Ａ）×２）×２＋Ａ＝（２４＋２２＋２０）Ａを生成する。
【０００８】
効率的な指数剰余演算のためのウィンドウ法（window method）が知られている。ウィンドウ法は、Alfred J. Menezes他の“HANDBOOK OF APPLIED CRYPTOGRAPHY”（CRC press）, pp. 615, Algorithm 14.82に記載されている。
【０００９】
図２は、ウィンドウ法を用いてｖ＝ａｄ（ｍｏｄ  ｎ）を求めるための指数剰余演算のアルゴリズムを示している。ここで、指数ｄは２進表現でｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２と表記される。そのアルゴリズムはＣ言語で記述されている。
【００１０】
ウィンドウ法は、ＲＳＡ暗号以外に、楕円曲線暗号における点のスカラー倍算にも用いられる。図３は、ウィンドウ法を用いた点のスカラー倍算Ｖ＝ｄＡのアルゴリズムを示している。
【００１１】
図２のアルゴリズムを説明する。図４は、図２のアルゴリズムによる演算の手順を説明するのに役立つ。まず、０＜ｘ＜２ｋである全ての整数ｘに対して、ｗ［ｘ］＝ａｘ（ｍｏｄ  ｎ）を満たす値ｗのテーブルｗを作成する。テーブルｗの作成後、ｕビットの値ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２（ここで、ｄｕ−１，．．．ｄ０は１ビット値）をｋビット・シーケンスまたはストリングに分割し、ｍ個のｋビット・シーケンスｂｉ＝（ｄｉｋ＋ｋ−１，ｄｉｋ＋ｋ−２，．．．ｄｉｋ）２（ここで、ｄｉｋ＋ｋ−１，．．．ｄｉｋは１ビット値、ｉ＝０，１，２，．．．）を生成する。ここで、ｍ＝ｃｅｉｌｉｎｇ（ｕ／ｋ）であり、関数ｃｅｉｌｉｎｇ（ｘ）は変数ｘ以上の最小の整数を表す。この各ｂｉに対する値ｗ［ｂｉ］（＝ａｂｉ）をテーブルｗでルックアップすることによる乗算ｖ＝ｖ×ｗ［ｂｉ］と、ｖ＝ｖ２∧ｋ（mod n）で表される２ｋ乗すなわち累乗とを、上位シーケンスｂｍ−１から下位シーケンスｂ０へ順に実行することによって、ｖ＝ａd（mod n）を求める。
【００１２】
図３のアルゴリズムを説明する。まず、０＜ｘ＜２ｋの全ての整数ｘに対して、Ｗ［ｘ］＝ｘＡを満たす値ＷのテーブルＷを作成する。テーブルＷの作成後、ｕビットの値ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２を分割してｍ個のｋビット・シーケンスｂｉ＝（ｄｉｋ＋ｋ−１，．．．ｄｉｋ）２（ｉ＝０，１，２，．．．）を生成する。ここで、ｍ＝ｃｅｉｌｉｎｇ（ｕ／ｋ）。そのｂｉに対する値Ｗ［ｂｉ］（＝ｂｉＡ）をテーブルＷでルックアップすることによる加算Ｖ＝Ｖ＋Ｗ［ｂｉ］と、Ｖ＝２ｋＶで表される２ｋ倍算とを、上位シーケンスｂｍ−１から下位シーケンスｂ０へ順に実行することによって、Ｖ＝ｄＡを求める。
【００１３】
以下、ウィンドウ法においてテーブル・ルックアップのインデックスとなるビット・シーケンスｂｉをウィンドウまたはウィンドウ・シーケンスといい、指数剰余演算と点のスカラー倍算の双方を公開鍵演算という。
【００１４】
暗号解読（分析）またはタンパ（tamper）は、暗号文のような入手可能な情報から秘密鍵を含めた秘密情報を推定する。暗号解読の１つである電力解析攻撃が、１９９８年にPaul Ｋocher（ポール  コーチャ）によって考案された。この電力解析攻撃は、スマートカードのような暗号デバイスに含まれる暗号プロセッサに相異なる入力データを与え、例えば図１に示されているようにオシロスコープ等を用いてその処理中における時間に対する消費電力の変化を測定し、統計的に充分な数の消費電力変化の曲線を収集しそれを解析し、それによって暗号プロセッサ内部の鍵情報を推定する。これは、前述の公開鍵暗号と共通鍵暗号の双方に適用できる。
【００１５】
電力解析攻撃には、単純電力解析（以下、ＳＰＡという）（Simple Power Analysis）および電力差分攻撃（以下、ＤＰＡという）（Differential Power Analysis）が含まれる。ＳＰＡは暗号プロセッサにおける１つの消費電力変化曲線の特徴から秘密鍵の推定を行う。ＤＰＡは相異なる多数の消費電力変化曲線の差分（以下、電力差分曲線という）を用いて解析することによって秘密鍵の推定を行う。一般的にはＤＰＡの方が強力である。
【００１６】
例えばＤＥＳ（Data Encryption Standard）およびＡＥＳ（Advanced Encryption Standard）等の共通鍵暗号に対するＳＰＡおよびＤＰＡが、Paul Ｋocher, Joshua Jaffe, and Benjamin Jun，“Differential Power Analysis”in proceedings of Advances in Cryptology-CRYPTO’９９，Lecture Notes in Computer Science, vol. １６６６, Springer-Verlag, １９９９, pp．３８８−３９７に記載されている。
【００１７】
例えばＲＳＡ暗号および楕円曲線暗号等の公開鍵暗号に対するＳＰＡおよびＤＰＡが、例えば、Thomas S. Messerges, Ezzy A. Dabbish and Robert H. Sloan“Power Analysis Attacks of Modular Exponentiation in Smartcards”Cryptographic Hardware and Embedded Systems （CHES’９９），Lecture Notes in Computer Science Vol. １７１７，Springer-Verlag，pp．１４４−１５７（以下、Messerges９９という）、およびJean-Sebastein Coron“Resistance against Differential Power Analysis for Elliptic Curve Crytosystems”Cryptographic Hardware and Embedded Systems（CHES’９９），Lecture Notes in Computer Science Vol．１７１７，Springer-Verlag，pp．２９２−３０２，１９９９（以下、Coron９９という）に記載されている。
【００１８】
図２および図３に示すウィンドウ法を用いた暗号プロセッサにおいて、前述のMesserges９９およびCoron９９に記載されているＤＰＡによって、秘密鍵ｄが推定される。
【００１９】
ＤＰＡを用いて、ウィンドウ法を用いた暗号プロセッサ内の秘密鍵ｄを推定する方法を、図５Ａ〜５Ｃを参照して説明する。図５Ａは時間に対する消費電力の曲線を示している。図５Ｂは、スパイクを有する、時間に対する電力差分曲線を示している。図５Ｃは、平坦な、時間に対する電力差分曲線を示している。
【００２０】
例えば、ｋ＝２および６ビット鍵ｄ＝（ｄ５ｄ４ｄ３ｄ２ｄ１ｄ０）２の場合、ウンドウb２ ＝（ｄ５ｄ４）２， b１＝（ｄ３ｄ２）２および b０＝（ｄ１ｄ０）２が生成される。図２の計算による指数剰余演算は、次のステップＳ１〜Ｓ５を実行してｖ＝ａｄ （ｍｏｄｎ）を生成する。
【００２１】
【数１】
0004108391.tif 000002
【００２２】
暗号プロセッサ部で上記のステップＳ１〜Ｓ５が行われていることを攻撃者が知っているとき、次のステップＳ１１〜Ｓ１４に従ったＤＰＡによって、ｂ２，ｂ２およびｂ１の値を、従ってｄの値を推定できる。
【００２３】
Ｓ１１）  暗号プロセッサにＮ個のａｉ（ｉ＝１，２，．．．Ｎ）を供給し、演算ａｉｄ（ｍｏｄ  ｎ）を実行させる。その実行中、全てのｉについて、プロセッサの消費電力量Ｐ（ａｉ，ｔｉｍｅ）を測定し、図５Ａに例示された時間に対する消費電力の曲線を得る。
【００２４】
Ｓ１２）  ２ビット値ｂ２＝ｂ２’であると仮定する。ｂ２＝ｂ２’が正しいと判定されてｂ２の推定に成功するまで、次のステップＳ１２１およびＳ１２２を繰り返す。
【００２５】
Ｓ１２１）  ステップＳ１の中間データｖに対して、仮定したｂ２’に従ってＰ（ａｉ，ｔｉｍｅ）（ｉ＝１，２，．．．Ｎ）を次の２つの集合Ｇ１およびＧ０に分ける。
【数２】
0004108391.tif 000003
【００２６】
Ｓ１２２）  Ｇ１およびＧ０から、Δ＝（Ｇ１の平均電力）−（Ｇ０の平均電力） で表される電力差分曲線Δを作成する。その曲線が図５Ｂのようなスパイクを有するとき、仮定ｂ２＝ｂ２’が正しいと判定する。その曲線が図５Ｃのような比較的平坦なときｂ２≠ｂ２’と判定する。
【００２７】
Ｓ１３）  次の２ビット値ｂ１＝ｂ１’であると仮定する。ｂ１＝ｂ１’が正しいと判定されてｂ１の推定に成功するまで、次のステップＳ１３１およびＳ１３２を繰り返す。
【００２８】
Ｓ１３１）  ステップＳ３の中間データｖに対して、確定したｂ２と仮定したｂ１’とに従ってＰ（ａｉ，ｔｉｍｅ）（ｉ＝１，２，．．．Ｎ）を次の２つの集合Ｇ１およびＧ０に分ける。
【数３】
0004108391.tif 000004
【００２９】
Ｓ１３２）  Ｇ１およびＧ０から、Δ＝（Ｇ１の平均電力）−（Ｇ０の平均電力） で表される電力差分曲線Δを作成する。その曲線が図５Ｂのようなスパイクを有するとき、仮定ｂ１＝ｂ１’が正しいと判定する。その曲線が図５Ｃのような比較的平坦なときｂ１≠ｂ１’と判定する。
【００３０】
Ｓ１４）  次の２ビット値ｂ０＝ｂ０’であると仮定する。ｂ０＝ｂ０’が正しいと判定されてｂ０の推定に成功するまで、次のステップＳ１４１およびＳ１４２を繰り返す。
【００３１】
Ｓ１４１）  ステップＳ５の中間データｖに対して、確定したｂ２およびｂ１と仮定したｂ０’とからＰ（ａｉ，ｔｉｍｅ）（ｉ＝１，２，．．．Ｎ）を次の２つの集合Ｇ１およびＧ０に分ける。
【数４】
0004108391.tif 000005
【００３２】
Ｓ１３２）  Ｇ１およびＧ０から、Δ＝（Ｇ１の平均電力）−（Ｇ０の平均電力） で表される電力差分曲線Δを作成する。その曲線が図５Ｂのようなスパイクを有するとき、仮定ｂ０＝ｂ０’が正しいと判定する。その曲線が図５Ｃのような比較的平坦なときｂ０≠ｂ０’と判定する。
【００３３】
同様の方法が、図３のウィンドウ法による暗号プロセッサに対しても適用できる。図２および３に示されているようなウィンドウ法による暗号処理は、一般的にＳＰＡによる秘密鍵の推定に対して安全であることが知られている。
【００３４】
秘密鍵に対するＳＰＡおよびＤＰＡを防止するために、乱数を用いて指数剰余演算および点のスカラー倍算を行うことが知られている。それによって、攻撃者がプロセッサ内の手順を知っていても、プロセッサ内で発生した乱数により中間データが隠蔽されるので、秘密鍵に対するＤＰＡを防止することができる。乱数を用いることによって、ウィンドウ法以外の方法による暗号処理においても、秘密鍵に対するＳＰＡを防止することができることが知られている。
【００３５】
乱数を用いた耐ＤＰＡ公開鍵演算には、次の（１）〜（５）の方法が知られている。ここで、φは、ＲＳＡ暗号ではｎ＝ｐ×ｑ（ｐおよびｑ＝素数）に対してφ＝ｌｃｍ（ｐ−１，ｑ−１）によって与えられ、楕円曲線暗号ではベースポイントの位数によって与えられる。但し、このφの値は、暗号プロセッサのインタフェースによって与えられるとは限らず、プロセッサ内で計算できるとも限らないので、φを必要とする方法は制約を受ける。例えば、ＲＳＡ暗号プロセッサに対しｎのみが与えられ、ｐおよびｑが与えられないときは、nからφ＝ｌｃｍ（ｐ−１，ｑ−１）を得るためには、１０２４ビット程度のｎの素因数分解という、事実上実行不可能な計算を行う必要があるので、φの値を用いた方法を利用することはできない。
【００３６】
（１）  ＲＳＡと楕円曲線暗号の双方について、ｄに対して公開鍵演算を行う代わりに、乱数ｒおよびφから計算したｄ＋ｒφに対して公開鍵演算を行う方法。
【００３７】
（２）  楕円曲線暗号について、ｄＡを計算する前処理として、乱数ｒを用いて２次元座標の点Ａを３次元座標の点Ａ’に変換する方法。例えば、Jacobian座標を用いて３次元座標への変換を行うとき、Ａ＝（ｘ，ｙ）に対して、乱数ｒを用いてＡ’＝（ｘ×ｒ２，ｙ×ｒ３，ｚ×ｒ）に従って変換する。
【００３８】
（３）  ＲＳＡと楕円曲線暗号の双方について、乱数を用いてｄ＝ｄ１＋ｄ２＋．．．＋ｄＭを満たすｄｉ（１≦ｉ≦Ｍ）を生成した後、それぞれのｄｉに対して、
【数５】
0004108391.tif 000006
またはＶｉ＝ｄｉＡを計算し、ｖ＝ｖ１×ｖ２×．．．×ｖＭ（ｍｏｄ  ｎ）またはＶ＝Ｖ１＋Ｖ２＋．．．＋ＶMを生成する方法。
【００３９】
（４）  ＲＳＡと楕円曲線暗号の双方について、ｄ＝ｄ１×ｄ２ （ｍｏｄ  φ）を満たす乱数ｄ１およびｄ２を生成した後、
【数６】
0004108391.tif 000007
またはＶ＝d２（ｄ１Ａ）を生成する方法。
【００４０】
（５）  ＲＳＡ暗号について、ａおよび乱数ｒからａ’＝ａ×ｒ（ｍｏｄ  ｎ），ｖ’＝ａ’ｄ（ｍｏｄ  ｎ）を計算した後、ｖ＝（ｖ’）ｒ−ｄ（ｍｏｄ  ｎ）＝ａｄ（ｍｏｄ  ｎ）を生成する方法。
【００４１】
表１は方法（１）〜（５）の比較を示している。
【表１】
0004108391.tif 000008
【００４２】
耐ＤＰＡ演算には次のような文献がある。
方法（１）：
−  Messerges９９
−  Coron９９
−  国際公開番号ＷＯ００/５９１５７（Jean-Sebastein Coron）
【００４３】
方法（２）：
−  Coron９９
−  Marc Joye and Christophe Tymen “Protections against differential analysis for elliptic curve cryptography -An algebraic approach-”， Cryptographic Hardware and Embedded Systems（CHES’２００１）（以下、Joye２００１という）
−  ＰＣＴ国際公開第ＷＯ００／５９１５６号（Jean-Sebastein Coron）
−  欧州特許公開第ＥＰ１０１４６１７号Ａ２（Kurumatani, Hiroyuki）
−  ＰＣＴ国際公開第ＷＯ０１２４４３９号（Miyazaki Kunihiko）
【００４４】
方法（３）：
−  ＰＣＴ国際公開第ＷＯ９９／３５８７２号（Paul Kocher）
−  ＰＣＴ国際公開第ＷＯ０１／３１４３６号（Louis Goubin）
−  欧州特許公開第ＥＰ１０９８４７１号Ａ２（Singer Ari）
【００４５】
方法（４）：
−  ＰＣＴ国際公開第ＷＯ９９／３５８７２号（Paul Kocher）
−  米国特許第２００１／０００２４８６号Ａ１（Paul Kocher）
【００４６】
方法（５）：
−  Messerges９９
【００４７】
表１に示されているように、方法（３）は、ＲＳＡと楕円曲線暗号の双方に適用可能であり、φが与えられないときにも適用可能なので、最も汎用性が高いと考えられる。方法（３）は、Ｍ＝２とした方法が最も高速の処理を行う。ここで、Ｍ＝２における方法（３）は、最も優れた通常の方法であり、“分割指数法”と呼ぶ。図６は、分割指数法を用いたｖ＝ａｄ（ｍｏｄ  ｎ）を求めるためのアルゴリズムを示している。
【００４８】
上述のように、図２および図３のウィンドウ法は、ＳＰＡには強いがＤＰＡには弱いという欠点がある。分割指数法は、ＳＰＡおよびＤＰＡに強いが、ｖ＝ａｄ（ｍｏｄ  ｎ）を求めるために、図６に示されているように、
【数７】
0004108391.tif 000009
という２回の指数剰余演算を実行する必要があるので、処理速度が遅いという欠点がある。
【００４９】
本発明の１つの目的は、秘密鍵の推定を困難にし、暗号処理の安全性を高めることである。
【００５０】
本発明のさらに別の目的は、効率的な耐タンパ性の指数剰余演算および点のスカラー倍算を実現することである。
【００５１】
【発明の概要】
本発明の特徴によれば、秘密鍵を用いて公開鍵暗号処理を行う暗号装置は、乱数に従って、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具えている。そのｍ個のウィンドウ・シーケンスのビット総数はそのｕビット・シーケンスのビット数ｕより多い。各ウィンドウ・シーケンスのビット数はｕ以下である。そのｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、そのｕビット・シーケンスにおける同じビット位置に対応付けられる。暗号装置は、さらに、その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成する演算手段を具えている。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００５２】
その一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置とその他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、そのｕビット・シーケンスにおけるｈ個のビット位置に対応付けられる。
【００５３】
本発明の別の特徴によれば、情報処理装置において使用するための、秘密鍵を用いて公開鍵暗号処理を行うプログラム（これは記憶媒体に格納されていてもよい）は、乱数に従って、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップと；その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップと、を実行させるよう動作可能である。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００５４】
本発明のさらに別の特徴によれば、ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて公開鍵暗号処理を行う方法は、そのウィンドウ・シーケンス生成手段を用いて、乱数に従って、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップと、その演算手段を用いて、その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップとを含んでいる。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００５５】
本発明のさらに別の特徴によれば、秘密鍵を用いて公開鍵暗号処理を行う暗号装置は、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具えている。そのｍ個のウィンドウ・シーケンスのビット総数はそのｕビット・シーケンスのビット数ｕより多い。各ウィンドウ・シーケンスのビット数はｕ以下である。そのｍ個のウィンドウ・シーケンスの中の２つのうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、そのｕビット・シーケンスにおける同じビット位置に対応付けられる。そのｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有する。暗号装置は、さらに、その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成する演算手段を具えている。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００５６】
その暗号装置は、さらに、そのウィンドウ・シーケンスのビット数からその同じ値のビット数を減算したビット数を有する取り得るシーケンスをインデックスとして有し、そのインデックスに対応付けられるそのウィンドウ・シーケンスの取り得るシーケンスに従って計算されたエントリ値を有するルックアップ・テーブルを生成する手段を具える。
【００５７】
その演算手段は、その導出されたウィンドウ・シーケンスのその同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いて、テーブルをルックアップすることによって、その演算を行う。
【００５８】
その導出する手段は、そのｕビット・シーケンスから、そのｕビット・シーケンスにおける対応する所定の位置に配置されたそのウィンドウ・シーケンスのその同じ値を減算して別のシーケンスを生成し、その別のシーケンスからそのウィンドウ・シーケンスを導出する。
【００５９】
本発明のさらに別の特徴によれば、情報処理装置において使用するための、秘密鍵を用いて公開鍵暗号処理を行うプログラム（これは記憶媒体に格納されていてもよい）は、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップと、その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップと、を実行させるよう動作可能である。そのｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有する。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００６０】
本発明のさらに別の特徴によれば、ウィンドウ・シーケンス生成手段および演算手段を具える情報処理装置において秘密鍵を用いて公開鍵暗号処理を行う方法は、そのウィンドウ・シーケンス生成手段を用いて、その公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップと、その演算手段を用いて、その導出されたｍ個のウィンドウ・シーケンスとその公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップとを含んでいる。そのｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有する。その公開鍵暗号処理は指数剰余演算であり、その別の値をａとし、ｎを正の整数としたとき、その処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、乗算と２乗算とを実行する。代替構成として、その公開鍵暗号処理は点のスカラー倍算であり、その処理済みデータはベクトルＶであり、その値ｄはスカラーであり、その別の値はベクトルＡであり、その処理済みデータＶはＶ＝ｄＡで与えられ、その演算手段は、その導出されたｍ個のウィンドウ・シーケンスｂｉの各々に従って、加算、減算および２倍算とを実行するものである。
【００６１】
本発明によれば、秘密鍵の推定を困難にし、暗号処理の安全性を高めることができ、効率的な耐タンパ性の指数剰余演算および点のスカラー倍算を実現できる。
【００６２】
図面において、同じ参照番号は同じ要素を示す。
【００６３】
【００６４】
【発明の好ましい実施形態】
図７は、本発明による暗号処理装置６０の概略的構成を示している。暗号処理装置６０は、値ａ、ｄおよびｎまたは値Ａおよびｄを入力して供給する入力部７２と、乱数発生器７４と、乱数発生器７４からの乱数に従って値ｄからオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０および重なり長（オーバラップ長）ｈｍ−２，ｈｍ−３，．．．ｈ０を生成するウィンドウおよび重なり長生成部７５と、生成部７５からのウィンドウおよび重なり長を格納するメモリ７８と、入力部７２からの値ａおよびｎまたは値Ａからｋビットのウィンドウｂｉに対するテーブルｗまたはＷを生成するテーブル生成部８０と、テーブル・メモリ８２と、メモリ７８からのウィンドウおよび重なり長に従ってテーブル・メモリ８２中のテーブルｗまたはＷをルックアップ（探索）して等式ｖ＝ａｄ（ｍｏｄｎ）またはＶ＝ｄＡを演算するウィンドウ法演算部８４と、値ｖまたはＶを出力する出力部８６とを含んでいる。
【００６５】
暗号化装置６０は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従ってこれらの要素７２〜８６を制御する。代替構成として、プロセッサ６２は、要素７２〜８６に対応する機能を実現するメモリ６４中のプログラムを実行することによって要素７２〜８６を実現してもよい。この場合、図７はフロー図として見ることができる。
【００６６】
図８は、本発明のオーバラップ・ウィンドウ法によるオーバラップ・ウィンドウｂｉの生成の仕方を示している。生成部７５は、乱数発生器７４からの乱数に従って値ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からｍ個のｋビット・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出して、メモリ７８に格納する。図８では、図４と違って、隣接する２つのｋビット・ウィンドウｂｉ＋１およびｂｉについて、ｂｉ＋１の右のｈビット位置とｂｉの左のｈビット位置がｄにおける対応するビット位置において重複することを許されている。或る値ｄに対してウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０の複数の可能な組（セット）が存在するので、その中の１つの組を乱数に従って選択することによって、ＤＰＡによる秘密鍵のタンパに耐性を有する公開鍵演算を実現できる。
【００６７】
図８には、オーバラップ・ウィンドウ法の指数剰余演算への適用の例が示されているが、オーバラップ・ウィンドウは点のスカラー倍算にも同様に適用できる。演算部８４は、メモリ７８からのウィンドウｂｉに従って、メモリ８２中のテーブルｗまたはＷをルックアップして、ｖにｗを乗算しそれを２ｋ−ｈ乗することを繰り返してｖ＝ａｄ（ｍｏｄ  ｎ）を求め、または、ＶにＷを加算し２ｋ−ｈ倍算を行うことを繰り返してＶ＝ｄＡを求める。
【００６８】
オーバラップ・ウィンドウｂｉ＋１およびｂｉにおけるそれぞれのｈ個の重なりビットのストリングの値は乱数に従って決定される。ウィンドウｂｉ＋１およびｂｉは、乱数ｒに従って、ウィンドウｂｉ＋１におけるｈ個の重なりビットのストリングの値とｂｉにおけるｈ個の重なりビットのストリングの値の和が、入力値ｄにおける対応するｈビットのストリングの値になるように、生成される。代替構成として、ウィンドウｂｉ＋１およびｂｉは、乱数ｒに従ってｂｉにおけるｈ個の重なりビットのストリングの値を発生し、ウィンドウｂｉ＋１におけるｈ個の重なりビットのストリングの値が、入力値ｄにおける対応するｈビットのストリングの値からｂｉにおけるｈ個の重なりビットのストリングの値を減じた値になるように（ｂｉ＋１における上位ビット位置からのボローが生じてもよい）、生成されてもよい。
【００６９】
図９は、本発明による、乱数に従ったオーバラップ・ウィンドウｂｉにおけるｈ個の重なりビットのストリングの値の決定の簡単な例を示している。図９において、ウィンドウｂｉ＋１およびｂｉのそれぞれのｈ個の重なりビットαｊおよびβｊ（ｊ＝ｈ−１，．．．０）を、即ちｂｉ＋１中のビット・ストリング（αｈ−１．．．α１α０）およびｂｉ中のビット・ストリング（βｈ−１．．．β１β０）を、入力値ｄにおける対応するビットｄｑ（ｑ＝ｘ＋ｋ−１，．．．ｘ＋ｋ−ｈ）の値に応じて次のように決定する。ｄｑ＝１の場合、乱数ｒ＝１または０を生成して、ビットｄｑに対応するウィンドウｂｉ＋ｒ中のビットαｊまたはβｊに１をセットし、ウィンドウｂｉ＋（１−ｒ）中の対応するビットβｊまたはαｊに０をセットする。ｄｑ＝０の場合、ウィンドウｂｉ＋ｒとｂｉ＋（１−ｒ）の双方の対応するビットαｊおよびβｊに０をセットする。
【００７０】
図１０は、本発明による、隣接するウィンドウｂｉ＋１とｂｉに固定された重なりビット長ｈを有するオーバラップ・ウィンドウ法を用いた指数剰余演算のフロー図を示している。図１１は、本発明による、隣接するウィンドウｂｉ＋１とｂｉに可変な重なりビット長ｈｉを有するオーバラップ・ウィンドウ法を用いた指数剰余演算のフロー図を示している。図１０および１１では、生成されるウィンドウｂｉは０≦ｂｉ＜２ｋの範囲の値を有する。
【００７１】
図１０のフロー図を説明する。最初に、入力部７２は値ａ、ｄおよびｎを入力して生成部７５に供給する。ステップ１０２において、生成部７５は、乱数発生器７４からの乱数に従って、値ｄからウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出してメモリ７８に格納する。ステップ１０４において、テーブル生成部８０は、テーブルｗ（ｗ［ｘ］＝ａｘ）（０＜ｘ＜２ｋ）を生成してメモリ８２に格納する。ステップ１０６において、演算部８４はｖ＝１およびｉ＝ｍをセットする。
【００７２】
ステップ１０８〜１１４において、演算部８４は、ｉ＝ｍ−１，ｍ−２，．．．０について順次、ｂｉに従って、メモリ８２のテーブルｗのルックアップによるｗ［ｂｉ］の乗算と累乗とを、ｖに対して実行する。ステップ１０８において、演算部８４はｉ＝ｉ−１をセットする。ステップ１１０において、演算部８４は、ｂｉ＞０の場合にｖにｗ［ｂｉ］を乗算する。ステップ１１２において、演算部８４はｉの値と値０とを比較してｉ＝０かどうかを判定する。ｉ＝０でないと判断された場合には、ステップ１１４において演算部８４は、（ｋ−ｈ）回の２乗によってｖの２（ｋ−ｈ）乗を生成する。ステップ１１２においてｉ＝０であると判断された場合には、出力部８６はｖ＝ａｄ（ｍｏｄ  ｎ）を出力する。
【００７３】
図１１のフロー図を説明する。ステップ２０２において、生成部７５は、乱数発生器７４からの乱数に従って、ｄからウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出しビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を生成してメモリ７８に格納する。ステップ２０４において、テーブル生成部８０は、テーブルｗを生成してメモリ８２に格納する。ステップ２０６〜２１２は、図１０のステップ１０６〜１１２に対応する。ステップ２０８〜２１４において、演算部８４は、ｉ＝ｍ−１，．．．０について順次、ｂｉに従って、メモリ８２のテーブルｗのルックアップによるｗ［ｂｉ］での乗算（ステップ２１０）と（ｋ−ｈｉ−１）回の２乗による累乗（ステップ２１４）を、ｖに対して実行して、ｖ＝ａｄ（ｍｏｄｎ）を生成する。
【００７４】
図１２は、本発明による、隣接するウィンドウｂｉ＋１とｂｉに固定された重なりビット長ｈを有するオーバラップ・ウィンドウ法を用いたスカラー倍算のフロー図を示している。図１３は、本発明による、隣接するウィンドウｂｉ＋１とｂｉに可変な重なりビット長ｈｉを有するオーバラップ・ウィンドウ法を用いたスカラー倍算のフロー図を示している。図１２および１３では、ウィンドウｂｉは−２ｋ＜ｂｉ＜２ｋの範囲の値を有する。
【００７５】
図１２のフロー図を説明する。最初に、入力部７２は値Ａおよびｄを入力して生成部７５に供給する。ステップ３０２において、生成部７５は、乱数発生器７４からの乱数に従って、ｄからウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を生成してメモリ７８に格納する。ステップ３０４において、テーブル生成部８０は、テーブルＷ（Ｗ［ｘ］＝ｘＡ）（０＜ｘ＜２ｋ）を生成してメモリ８２に格納する。ステップ３０６において、演算部８４はＶ＝Ｏ（無限遠点）およびｉ＝ｍをセットする。
【００７６】
ステップ３０８〜３１４において、演算部８４は、ｉ＝ｍ−１，ｍ−２，．．．０について順次、ｂｉに従って、メモリ８２のテーブルＷのルックアップによるＷ［ｂｉ］の加算およびＷ［−ｂｉ］の減算と、乗算とを、Ｖに対して実行する。ステップ３０８において、演算部８４はｉ＝ｉ−１をセットする。ステップ３１０において、演算部８４は、ｂｉ＞０の場合にＶにＷ［ｂｉ］を加算し、ｂｉ＜０の場合にＶからＷ［−ｂｉ］を減算する。ステップ３１２において、演算部８４はｉの値と値０とを比較してｉ＝０かどうかを判定する。ｉ＝０でないと判断された場合には、ステップ３１４において演算部８４は、（ｋ−ｈ）回の２倍算によってＶの２（ｋ−ｈ）倍を生成する。ステップ３１２においてｉ＝０であると判断された場合には、出力部８６はＶ＝ｄＡを出力する。
【００７７】
図１３のフロー図を説明する。ステップ４０２において、生成部７５は、乱数発生器７４からの乱数に従って、ｄからウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出しビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を生成してメモリ７８に格納する。ステップ４０４において、テーブル生成部８０は、テーブルＷを生成してメモリ８２に格納する。ステップ４０６〜４１２は、図１２のステップ３０６〜３１２に対応する。ステップ４０８〜４１４において、演算部８４は、ｉ＝ｍ−１，．．．０について順次、ｂｉに従って、メモリ８２のテーブルＷのルックアップによるＷ［ｂｉ］の加算またはＷ［−ｂｉ］の減算（ステップ４１０）と（ｋ−ｈｉ−１）回の２倍算による乗算（ステップ４１４）を、Ｖに対して実行して、Ｖ＝ｄＡを生成する。
【００７８】
後で実施形態において説明するように、図１０、１１、１２および１３において、ウィンドウｂｉの計算法が複数存在する。
【００７９】
図１４は、本発明の第１の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順序で生成するためのフロー図を示している。図１５は、図１４に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ＜２ｋの範囲の値を有する。従って、この実施形態は、重なりビットの長さｈが固定値のとき、図１０のＲＳＡ暗号処理と図１２の楕円曲線暗号処理の双方に適用できる。
【００８０】
重なりビットの長さｈが固定値のときに、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２を表すｕビット・シーケンス（ｄｕ−１，ｄｕ−２，．．．ｄ０）からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出する方法を、図１４および１５を参照して説明する。ここで、ｈはｂｉ＋１とｂｉの重なりビットの長さであり、０＜ｈ＜ｋであり、ｋはｂｉのビットの長さである。
【００８１】
ステップ５０１において、生成部７５は、ウィンドウｂｉの数ｍ＝ｃｅｉｌｉｎｇ（（ｕ−ｈ）／（ｋ−ｈ））を決定する。ステップ５０２において、生成部７５はｉ＝ｍにセットする。ステップ５０３において、生成部７５は最初の中間ウィンドウｗｔｍ−１＝（ｄｕ−１，．．．ｄ（ｍ−１）（ｋ−ｈ））２を供給する（図１５参照）。ここで、ｗｔｍ−１は、ｄのｋ’個のＭＳＢ（ｋ’＝ｕ−（ｍ−１）（ｋ−ｈ），ｋ’≦ｋ）を取り出したものである。
【００８２】
ステップ５０４において、生成部７５はｉ＝ｉ−１にセットする。ステップ５０５において、生成部７５はｉ＝０かどうかを判定する。ｉ≠０と判定された場合に、生成部７５は、ステップ５０６において、乱数発生器７４からのｋビットの乱数ｒに従って、ｍａｘ（０，ｗｔｍ−１−２ｈ＋１）≦ｂｍ−１≦ｗｔｍ−１を満たすようなオーバラップ・ウィンドウｂｍ−１を生成する（図１５参照）。ここで、ｍａｘ（ｘ，ｙ）は値ｘおよびｙのうちの大きいものを表す。ウィンドウｂｍ−１は、乱数ｒそのものの値であっても、または乱数ｒに従って所定の数のｂｉの値の中から選択されてもよい。ｂｍ−１がこの範囲の値なので、（ｗｔｍ−１−ｂｍ−１）は０≦（ｗｔｍ−１−ｂｍ−１）＜２ｈを満たす。
【００８３】
ｗｔｍ−１とｂｍ−１を決定した後、ステップ５０７において、生成部７５は次の中間ウィンドウｗｔｍ−２＝（（ｗｔｍ−１−ｂｍ−１）２（ｋ−ｈ）＋（ｄ（ｍ−１）（ｋ−ｈ）−１，．．．ｄ（ｍ−２）（ｋ−ｈ））２を供給する（図１５参照）。ｗｔｍ−２は、ｋ−ｈビットの左シフトおよび加算：ｗｔｍ−２＝（（ｗｔｍ−１−ｂｍ−１）＜＜（ｋ−ｈ））＋（ｄ（ｍ−１）（ｋ−ｈ）−１，．．．ｄ（ｍ−２）（ｋ−ｈ））２を実行することによって、求めてもよい。
【００８４】
その後、生成部７５は、ｉ＝ｍ−２，ｍ−３，．．．１についてステップ５０４〜５０７を繰り返す。生成部７５は、ステップ５０６において乱数ｒに従ってｍａｘ（０，ｗｔｉ−１−２ｈ＋１）≦ｂｉ≦ｗｔｉを満たすｂｉを生成し、ステップ５０７において次の中間ウィンドウｗｔｉ−１＝（ｗｔｉ−ｂｉ）２（ｋ−ｈ）＋（ｄｉ（ｋ−ｈ）−１，．．．ｄ（ｉ−１）（ｋ−ｈ））２を求める（図１５参照）。換言すれば、次の中間シーケンスｗｔｉ−１は、中間シーケンスｗｔｉからウィンドウｂｉを減算することによって導出された値をＭＳＢとして含み、ｕビット・シーケンスの中の次のｋ−ｈ個のＭＳＢをＬＳＢとして含んでいる。このようにして、ステップ５０５においてｉ＝０と判定された場合に、生成部７５は、ステップ５０８においてｂ０＝ｗｔ０とセットし、オーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を出力する。
【００８５】
図１６は、第１の実施形態の変形である本発明の第２の実施形態による、生成部７５において、可変な重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順序で生成するためのフローチャートを示している。この実施形態では、隣接するｂｉ＋１とｂｉの重なりビットの長さｈｉが可変である。図１７は、図１６に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ＜２ｋの範囲の値を有する。従って、この実施形態は、図１１のＲＳＡ暗号処理と図１３の楕円曲線暗号処理の双方に適用できる。
【００８６】
次に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出し重なりビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を生成する方法を、図１６および１７を参照して説明する。ここで、ｕはｄのビットの長さ、ｂｉ＋１とｂｉの重なりビットの長さｈｉは０≦ｈｉ≦ｋの範囲の値、ｋはｂｉのビットの長さである。
【００８７】
ステップ６０１において、生成部７５は、０≦ｈｉ≦ｋかつｕ＝ｍｋ−（ｈｍ−２＋ｈｍ−３＋．．．＋ｈ０）を満たすように、乱数ｒ（＝ｈｉ）に従って、ウィンドウｂｉの数ｍおよび重なりビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を決定する。ステップ６０２において、生成部７５はｉ＝ｍおよびｊ＝ｕ−ｋにセットする。ステップ６０３において、生成部７５は最初の中間ウィンドウｗｔｍ−１＝（ｄｕ−１，．．．ｄｊ）２を供給する。
【００８８】
ステップ６０４において、生成部７５はｉ＝ｉ−１にセットする。ステップ６０５において、生成部７５はｉ＝０かどうかを判定する。ｉ≠０と判定された場合に、生成部７５は、ステップ６０６において、図１４と同様に、乱数発生器７４からのｋビットの乱数ｒに従って、ｍａｘ（０，ｗｔｉ−２ｈｉ＋１）≦ｂｉ≦ｗｔｉを満たすようなオーバラップ・ウィンドウｂｉを生成する（図１７参照）。ウィンドウｂｉは、乱数ｒそのものの値であっても、または乱数ｒに従って所定の数のｂｉの値の中から選択されてもよい。
【００８９】
ｗｔｍ−１とｂｍ−１を決定した後、ステップ６０７において、生成部７５は次の中間ウィンドウｗｔｉ−１＝（（ｗｔｉ−ｂｉ）２（ｋ−ｈｉ−１）＋（ｄｊ−１，．．．ｄｊ−（ｋ−ｈｉ−１））２を供給する（図１７参照）。ステップ６０８において、生成部７５はｊ＝ｊ−（ｋ−ｈｉ−１）にセットする。
【００９０】
生成部７５は、ｉ＝ｍ−２，ｍ−３，．．．１についてステップ５０４〜５０７を繰り返す。このようにして、ステップ６０５においてｉ＝０と判定された場合に、生成部７５は、ステップ６０８においてｂ０＝ｗｔ０とセットし、オーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０および重なりビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を出力する。
【００９１】
図１８は、本発明の第３の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順で生成するためのフローチャートを示している。図１９は、図１８に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ＜２ｋの範囲の値を有する。従って、この実施形態は、重なりビットの長さｈが固定値のとき、図１０のＲＳＡ暗号処理と図１２の楕円曲線暗号処理の双方に適用できる。
【００９２】
重なりビットの長さｈが固定値のときに、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂ０，ｂ１，．．．ｂｍ−１を導出する方法を、図１８および１９を参照して説明する。ここで、ｂｉ＋１とｂｉの重なりビットの長さｈは０＜ｈ＜ｋの範囲の値である。ウィンドウｂｉ中のｈ個のＭＳＢをｗｌｉ、ウィンドウｂｉ中の（ｋ−ｈ）個のＬＳＢをｗｒｉと表す。ｂｉ＋１とｂｉは、ｂｉ＋１中のｈ個のＬＳＢ位置とｂｉのｈ個のＭＳＢ位置が重なる。
【００９３】
ステップ７０１において、生成部７５は、ウィンドウｂｉの数ｍ＝ｃｅｉｌｉｎｇ（（ｕ−ｈ）／（ｋ−ｈ））を決定する。ステップ７０２において、生成部７５はｉ＝０にセットする。ステップ７０３において、生成部７５は最初の中間シーケンスｄｔ０＝ｄｔ＝（ｄｕ−１，．．．ｄ０）２を供給する。
【００９４】
ステップ７０４において、生成部７５はｉ＝ｍ−１かどうかを判定する。ｉ≠ｍ−１と判定された場合に、生成部７５は、ステップ７０５において、ｗｒ０＝（ｄｔ０中の（ｋ−ｈ）個のＬＳＢ）と、乱数発生器７４からの乱数ｒに従ってｗｌ０＝（ｈビットの乱数ｒ）とを生成し、ステップ７０６においてｂ０＝ｗｌ０２（ｋ−ｈ）＋ｗｒ０を生成する（図１９参照）。それによって、（ｄｔ０−ｂ０）における（ｋ−ｈ）個のＬＳＢは全て０となる。ステップ７０７において、次の中間シーケンスｄｔ１＝（ｄｔ０−ｂ０）／２（ｋ−ｈ）を求める（図１９参照）。ステップ７０８において、ｉ＝ｉ＋１にセットする。
【００９５】
その後、生成部７５はｉ＝１，２，．．．ｍ−２についてステップ７０５〜７０８を繰り返す。生成部７５は、ステップ７０５においてｗｒｉ＝（ｄｔｉ中の（ｋ−ｈ）個のＬＳＢ）と、ｗｌｉ＝（ｈビットの乱数ｒ）とを生成し、ステップ７０６においてｂｉ＝ｗｌｉ２（ｋ−ｈ）＋ｗｒｉを生成し、ステップ７０７において次の中間シーケンスｄｔｉ＋１＝（ｄｔｉ−ｂｉ）／２（ｋ−ｈ）を生成する（図１９参照）。換言すれば、ウィンドウｂｉは、乱数に従って生成されたｈ個のＭＳＢを含み、中間シーケンスｄｔｉの（ｋ−ｈ）個のＬＳＢをＬＳＢとして含んでいる。次の中間シーケンスｄｔｉ＋１は、ｄｔｉからウィンドウｂｉを減算し、（ｋ−ｈ）個のＬＳＢを切り捨てることによって導出される。ｂｉ＝ｗｌｉ２（ｋ−ｈ）＋ｗｒｉおよびｄｔｉ＋１＝（ｄｔｉ−ｂｉ）／２（ｋ−ｈ）は、それぞれ（ｋ−ｈ）ビットの左シフトおよび右シフトを実行することによって、求めてもよい。
【００９６】
このようにして、ステップ７０４においてｉ＝ｍ−１と判定された場合に、生成部７５は、ステップ７０９においてｂｍ−１＝ｄｔｍ−１とセットし、オーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１を出力する。
【００９７】
図２０は、第３の実施形態の変形である本発明の第４の実施形態による、生成部７５において、可変な重なりビット長を有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順で生成するためのフローチャートを示している。この実施形態ではｂｉ＋１とｂｉの重なりビットの長さｈｉが可変である。図２１は、図２０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ≦２ｋの範囲の値を有する。従って、この実施形態は、図１１のＲＳＡ暗号処理と図１３の楕円曲線暗号処理の双方に適用できる。
【００９８】
次に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂ０，ｂ１，．．．ｂｍ−１を導出し重なりビット長ｈ０，ｈ１，．．．ｈｍ−２を生成する方法を、図２０および２１を参照して説明する。ｂｉ＋１とｂｉの重なりビットの長さｈｉは０≦ｈｉ≦ｋの範囲の値である。
【００９９】
ステップ８０１において、生成部７５は、０≦ｈｉ≦ｋかつｕ＝ｍｋ−（ｈ０＋ｈ１＋．．．＋ｈｍ−２）を満たすように、乱数ｒ（＝ｈｉ）に従って、ウィンドウｂｉの数ｍおよび重なりビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を決定する。ステップ８０２において、生成部７５はｉ＝０にセットする。ステップ８０３において、生成部７５は最初の中間ウィンドウｄｔ０＝（ｄｕ−１，．．．ｄｊ）２を供給する。
【０１００】
ステップ８０４において、生成部７５はｉ＝ｍ−１かどうかを判定する。ｉ≠ｍ−１と判定された場合に、生成部７５は、図１６と同様に、ステップ８０５において、乱数に従ってｗｌｉ＝（ｈｉビットの乱数）とｗｒｉ＝（ｄｔｉ中の（ｋ−ｈｉ）個のＬＳＢ）とを生成し、ステップ８０６においてｂｉ＝ｗｌｉ２（ｋ−ｈｉ）＋ｗｒｉを生成し、ステップ８０７においてｄｔｉ＝（ｄｔｉ−１−ｂｉ−１）／２（ｋ−ｈｉ）を生成する（図２１参照）。ステップ８０８において、生成部７５は、ｉ＝ｉ＋１にセットする。
【０１０１】
生成部７５は、ｉ＝０，１，．．ｍ−２についてステップ８０４〜８０８を繰り返す。このようにして、ステップ８０４においてｉ＝ｍ−１と判定された場合、生成部７５は、ステップ８０９においてｂｍ−１＝ｄｔｍ−１とセットし、オーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１および重なりビット長ｈ０，ｈ０，．．．ｈｍ−２を出力する。
【０１０２】
図２２は、本発明の第５の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順で生成するためのフローチャートを示している。図２３は、図２２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態は、図１４および１５に示された第１の実施形態におけるｂｉの値の範囲を−２ｋ＜ｂｉ＜２ｋに拡張したもので、図１２の楕円曲線暗号処理にのみ適用できる。この実施形態では、ｂｉがより多くの取り得る値を有するので、ＳＰＡおよびＤＰＡを用いた秘密鍵の推定に対する安全性をより高くすることができる。
【０１０３】
重なりビットの長さｈが固定値の場合に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出する方法を、図２２および２３を参照して説明する。ここで、ｂｉ＋１とｂｉの重なりビットの長さｈは０＜ｈ＜ｋの範囲の値である。
【０１０４】
ステップ９０１〜９０５およびステップ９０７〜９０８は図１４のステップ５０１〜５０５およびステップ５０７〜５０８に対応し、再び説明することはしない。
【０１０５】
生成部７５は、ステップ９０６において、乱数発生器７４からのｋビットの乱数ｒに従って、ｗｔｉ−１−２ｈ＜ｂｉ＜ｍｉｎ（２ｋ，ｗｔｉ＋２ｈ）を満たすようなオーバラップ・ウィンドウｂｉを生成する（図２３参照）。ここで、ｍｉｎ（ｘ，ｙ）は値ｘおよびｙのうちの小さいものを表す。図２３に示されているように、ｂｉ＝（ｄｉｋ＋ｋ−１，ｄｉｋ＋ｋ−２，．．．ｄｉｋ）２におけるｄｉｋ＋ｋ−１，．．．ｄｉｋの各々の値は−１，０または１である。ウィンドウｂｉは、乱数ｒそのものの値であっても、または乱数ｒに従って所定の数のｂｉの値の中から選択されてもよい。図１４のステップ５０６において生成されるｂｉは０以上の値であるのに対し、この実施形態において、生成されるウィンドウｂｉは、−２ｋ＋２ｈ≦ｂｉ＜２ｋの範囲の値を有し、負の値を含んでいる。
【０１０６】
図２４は、第５の実施形態の変形である本発明の第６の実施形態による、生成部７５において、可変な重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順で生成するためのフローチャートを示している。この実施形態ではｂｉ＋１とｂｉの重なりビットの長さｈｉが可変である。図２５は、図２４に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態は、図１６および１７に示された第２の実施形態におけるｂｉの値の範囲を−２ｋ＜ｂｉ＜２ｋに拡張したもので、図１３の楕円曲線暗号処理にのみ適用できる。
【０１０７】
次に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出しｈｍ−２，ｈｕ−２，．．．ｈ０を生成する方法を、図２４および２５を参照して説明する。ここで、ｂｉ＋１とｂｉの重なりビットの長さｈｉは０≦ｈｉ≦ｋの範囲の値である。
【０１０８】
ステップ１００１〜１００５およびステップ１００７〜１００８は図１６のステップ６０１〜６０５およびステップ６０７〜６０８に対応し、再び説明することはしない。
【０１０９】
生成部７５は、ステップ１００６において、乱数発生器７４からのｋビットの乱数ｒに従って、ｗｔｉ−１−２ｈｉ＜ｂｉ＜ｍｉｎ（２ｋ，ｗｔｉ＋２ｈｉ）を満たすようなオーバラップ・ウィンドウｂｉを生成する（図２５参照）。図２５に示されているように、ｂｉにおける各ビットの値は−１，０または１である。図１６のステップ６０６で生成されるｂｉは０以上の値であるのに対し、この実施形態において、生成されるウィンドウｂｉは、−２ｋ＜ｂｉ＜２ｋの範囲の値を有し、負の値を含んでいる。
【０１１０】
図２６は、本発明の第７の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順で生成するためのフローチャートを示している。図２７は、図２６に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態は、図１８および１９に示された第３の実施形態のｂｉの値の範囲を−２ｋ＜ｂｉ＜２ｋに拡張したもので、図１２の楕円曲線暗号処理にのみ適用できる。この実施形態では、ｂｉがより多くの取り得る値を有するので、ＳＰＡおよびＤＰＡを用いた秘密鍵の推定に対する安全性をより高くすることができる。この実施形態では、第３の実施形態の図１８のステップ７０７における演算をなくしたので、高速処理が可能である。
【０１１１】
重なりビットの長さｈが固定値の場合に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂ０，ｂ１，．．．ｂｍ−１を導出する方法を、図２６および２７を参照して説明する。ここで、ｂｉ＋１とｂｉの重なりビットの長さｈは０＜ｈ＜ｋの範囲の値である。
【０１１２】
ステップ１１０１〜１１０２は図１８のステップ７０１〜７０２に対応する。ステップ１１０３において、生成部７５は、最初の中間ウィンドウｗｔ０＝（ｄｋ−１，ｄｋ−２，．．．ｄ０）２を供給する。ここで、ｗｔ０は、ｄのｋ個のＬＳＢを取り出したものである。
【０１１３】
生成部７５は、ｉ＝０，１，．．．ｍ−２について、ステップ１１０４〜１１１０を実行して、ｂ０，ｂ１，．．．ｂｍ−２を生成する。ステップ１１０４において、生成部７５はｉ＝ｍ−１かどうかを判定する。ステップ１１０４、１１１０および１１１１は、図１８のステップ７０４、７０８および７０９にそれぞれ対応する。
【０１１４】
ステップ１１０５において、生成部７５は、ｗｔｒｉ＝ｗｔｉ（ｍｏｄ  ２（ｋ−ｈ））を求める。このモジュロ演算は、中間ウィンドウｗｔｉが負の場合を含んでいる。この演算は次のように実行される。
【数８】
0004108391.tif 000010
【０１１５】
ステップ１１０６において、生成部７５は、ｗｔｌｉ＝（ｗｔｉ−ｗｔｒｉ）／２（ｋ−ｈ）を決定する。ステップ１１０７において、生成部７５は、乱数発生器７４からのｋビットの乱数ｒに従ってｗｔｌｉ−２h＜ ｗｌｉ＜２hを満たすようなｗｌｉと、ｗｒｉ＝ｗｔｒｉとを生成する。ｗｌｉは、乱数ｒそのものの値であっても、または乱数ｒに従って所定の数のｗｌｉの値の中から選択されてもよい。ステップ１１０８において、生成部７５は、ｂｉ＝ｗｌｉ２ｈ＋ｗｒｉを求める（図２７参照）。換言すれば、ウィンドウｂｉは、乱数に従って生成されたｈ個のＭＳＢを含み、中間シーケンスｗｔｉ（ｍｏｄ  ２（ｋ−ｈ））の値を（ｋ−ｈ）個のＬＳＢｓとして含んでいる。図２７に示されているように、ｂｉにおける各ビットの値は−１，０または１である。
【０１１６】
ステップ１１０９において、生成部７５は、次の中間ウィンドウｗｔｉ+１＝（ｄｋ−（ｋ−ｈ）（ｉ＋１）−１，．．．ｄｋ−（ｋ−ｈ）ｉ）２２ｈ＋（ｗｔｌｉ−ｗｌｉ）を求める。換言すれば、次の中間シーケンスｗｔｉ＋１は、ｈ個のＭＳＢの値ｗｌｉを中間シーケンスｗｔｉの中のｈ個のＭＳＢの値から減算することによって導出された値をＬＳＢｓとして含み、ｕビット・シーケンスの中の他のｋ−ｈ個のビットをＭＳＢｓとして含んでいる。ステップ１１１０において、生成部７５は、生成部７５は、ｉ＝ｉ＋１にセットする。
【０１１７】
このようにして、ステップ１１０４においてｉ＝ｍ−１であると判定された場合、生成部７５はステップ１１１１においてｂｍ−１＝ｄｔｍ−１とセットして、オーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１を出力する。
【０１１８】
第３の実施形態と比較すると、この実施形態では、ｗｌｉおよびｗｒｉが負であってもよいので、図１８のステップ７０７で行う数ビット〜数百ビットの値からの減算が不要であり、処理が速い。
【０１１９】
図２８は、第７の実施形態の変形である本発明の第８の実施形態による、生成部７５において、可変な重なりビット長を有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順で生成するためのフローチャートを示している。この実施形態ではｂｉ＋１とｂｉの重なりビットの長さｈｉが可変である。図２９は、図２８に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態は、図２０および２１に示された第４の実施形態におけるｂｉの値を−２ｋ＜ｂｉ＜２ｋに拡張したもので、図１３の楕円曲線暗号処理にのみ適用できる。
【０１２０】
次に、秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂ０，ｂ１，．．．ｂｍ−１を導出し重なりビット長ｈ０，ｈ１，．．．ｈｍ−２を生成する方法を、図２８および２９を参照して説明する。ここで、ｂｉ＋１とｂｉの重なりビットの長さｈｉは０≦ｈｉ≦ｋの範囲の値である。
【０１２１】
この実施形態における処理は、ｈｉが可変であること以外は、図２６および２７と同様に処理が行われる。図２８におけるステップ１２０１は図２０のステップ８０１に対応する。ステップ１２０２において、生成部７５はｉ＝０およびｊ＝ｋにセットする。ステップ１２０４〜１２０９および１２１１は、図２６におけるステップ１１０４〜１１１０にそれぞれ対応する。
【０１２２】
ステップ１２０５において、生成部７５は、ｗｔｒｉ＝ｗｔｉ（ｍｏｄ  ２（ｋ−ｈｉ））を求める。ステップ１２０６において、生成部７５は、ｗｔｌｉ＝（ｗｔｉ−ｗｔｒｉ）／２（ｋ−ｈｉ）を求める。ステップ１２０７において、生成部７５は、乱数発生器７４からのｋビットの乱数ｒに従ってｗｔｌｉ−２hｉ＜ ｗｌｉ＜２hｉを満たすようなｗｌｉと、ｗｒｉ＝ｗｔｒｉとを生成する。ステップ１２０８において、生成部７５は、bｉ＝ｗｌｉ２（ｋ−ｈｉ）＋ｗｒｉを求める（図２９参照）。図２９に示されているように、ｂｉにおける各ビットの値は−１，０または１である。ステップ１２０９において、生成部７５は、次の中間ウィンドウｗｔｉ+１＝（ｄｊ＋ｋ−ｈｉ−１，．．．ｄｊ）２２ｈｉ＋（ｗｔｌｉ−ｗｌｉ）を求める。ステップ１２１０において、生成部７５は、ｊ＝ｊ＋（ｋ−ｈｉ）にセットする。
【０１２３】
このようにして、ステップ１２０４においてｉ＝ｍ−１であると判定された場合、生成部７５はステップ１２１２において、ｂｍ−１＝ｄｔｍ−１とセットして、オーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１および重なりビット長ｈｍ−２，ｈｍ−３，．．．ｈ０を出力する。
【０１２４】
図３０は、本発明の第９の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を順に生成するためのフローチャートを示している。図３１は、図３０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ＜２ｋの範囲の値を有し、従って、この実施形態は、図１０のＲＳＡ暗号処理と図１２の楕円曲線暗号処理の双方に適用できる。
【０１２５】
秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出する方法を、図３０および３１を参照して説明する。この実施形態では、複数のｍ−１ビットの乱数ビット・シーケンスを加算することによってウィンドウｂｉが生成される。ｂｉ＋１とｂｉの重なりビットの長さｈは０＜ｈ＜ｋの範囲の固定値である。
【０１２６】
ステップ１３０１において、生成部７５は、ウィンドウｂｉの数ｍ＝ｃｅｉｌｉｎｇ（ｕ／ｋ）を決定する。生成部７５は、ステップ１３０２において乱数発生器７４からの乱数に従って、ｄｆｊ≧０かつｄｆ１＋．．．＋ｄｆｇ−１≦ｄを満たすように入力ｄからｄｆ１，．．．ｄｆｇ−１を生成し、ステップ１３０３においてｄｆ０＝ｄ−（ｄｆ１＋．．．＋ｄｆｇ−１）（≧０）を生成する。このようにしてｄ＝ｄｆ０＋ｄｆ１＋．．．＋ｄｆｇ−１を満たすｇ個のｄｆｊ＝（ｄｆｊ，ｕ−１，ｄｆｊ，ｕ−２，．．．ｄｆｊ，０）２が生成される。ここで、ｇはｃｅｉｌｉｎｇ（２（ｋ-１）／（２（ｋ−ｈ）−１））≦ｇ≦ｆｌｏｏｒ（（２ｋ−１）／（２（ｋ−ｈ）−１））の範囲の定数である。関数ｆｌｏｏｒ（ｘ）は変数ｘ以下の最大の整数を表す。ｇは、最大ｋビットのｂｉ（２ｋ−１≦ｂｉ＜２ｋ）を与える。
【０１２７】
ステップ１３０４において、生成部７５は、ｉ＝ｉ−１にセットする。生成部７５は、ｂｉを生成するために、ステップ１３０５〜１３０８をｉ＝ｍ−１，ｍ−２，．．．０について順に実行する。ステップ１３０４〜１３０８では、ｉ＝０，１，．．．ｍ−１の順に、またはその他の順にｂｉが生成されてもよい。
【０１２８】
ステップ１３０５において、生成部７５は、ｊ＝０，１，．．．（ｇ−１）について、（ｋ−ｈ）ビットの値ｓｊ＝（ｄｆｊ，（ｉ＋１）（ｋ−ｈ）−１，．．．ｄｆｊ，ｉ（ｋ−ｈ））２をセットする。ステップ１３０６において、オーバラップ・ウィンドウｂｉ ＝ｓ０＋ｓ１＋．．．＋ｓｇ−１を求める。このようにして生成された隣接するウィンドウｂｉ＋１とｂｉは、ｂｉ＋１のｈ個のＬＳＢ位置とｂｉのｈ個のＭＳＢ位置とが、ｕビット・シーケンスにおける同じｈ個のビット（ｄｉｈ＋ｈ−１，．．．ｄｉｈ）の位置に関係付けられる。ステップ１３０７において生成部７５はｉ＝０かどうかを判定する。ｉ≠０と判定された場合に、生成部７５はステップ１３０８においてｉ＝ｉ−１にセットし、次いで、手順はステップ１３０５に進む。ｉ＝０と判定された場合は、生成部７５はオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を出力する。
【０１２９】
図３２は、第９の実施形態の変形である本発明の第１０の実施形態による、生成部７５において、重なりビット長を有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順で生成するためのフローチャートを示している。この実施形態は、第９の実施形態を変形したもので、モジュロφを用いてウィンドウｂｉを生成する。図３３は、図３２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態においてｂｉは０≦ｂｉ＜２ｋの範囲の値を有し、従って、この実施形態は、図１１のＲＳＡ暗号処理と図１３の楕円曲線暗号処理の双方に適用できる。
【０１３０】
秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２からウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を導出する方法を、図３２および３３を参照して説明する。ｂｉ＋１とｂｉの重なりビットの長さｈは０＜ｈ＜ｋの範囲の固定値である。
【０１３１】
この実施形態では、第９の実施形態と異なる条件でｄｆ０，ｄｆ１，．．．ｄｆｇ−１を生成する。この実施形態では、ｄに対してｂｉがより多くの取りうる値を有するので、ＳＰＡおよびＤＰＡを用いた秘密鍵の推定に対する安全性をより高くすることができる。
【０１３２】
ステップ１４０１において、生成部７５は、乱数発生器７４からの乱数に従って、ｄｆｊ≧０を満たすように入力ｄからｄｆ１，．．．ｄｆｇ−１を生成する。第９の実施形態とは異なり、ｄｆｊはｄｆ１＋．．．＋ｄｆｇ−１≦ｄを満たす必要がない。生成部７５は、ステップ１４０２において、ｄｆ０＝ｄ−（ｄｆ１＋．．．＋ｄｆｇ−１）（ｍｏｄ  φ）（≧０）を生成する。このようにしてｄ＝ｄｆ０＋ｄｆ１＋．．．＋ｄｆｇ−１（ｍｏｄ  φ）を満たすｇ個のｄｆｊ＝（ｄｆｊ，ｕ−１，ｄｆｊ，ｕ−２，．．．ｄｆｊ，０）２が生成される。ｄｆ０は、０≦ｄｆ０＜φを満たさなくてもよい。この実施形態では、第９の実施形態とは異なり、ｄｆ１，．．．ｄｆｇ−１は０以上のｕビットの任意の乱数なので、ｄｆ０，ｄｆ１，．．．ｄｆｇ−１がより多くの取りうる値を有し、従ってｂｉもより多くの取りうる値を有する。
【０１３３】
生成部７５は、ステップ１４０３においてｄｆ０＋ｄｆ１＋．．．＋ｄｆｇ−１のビット長ｕ’を求め、ステップ１４０４においてウィンドウｂｉの数ｍ＝ｃｅｉｌｉｎｇ（ｕ’／（ｋ−ｈ））を求める。ステップ１４０５において、生成部７５はｉ＝ｍ−１にセットする。
【０１３４】
ステップ１４０６において、生成部７５は、ｊ＝０，１，．．．（ｇ−１）について、（ｋ−ｈ）ビットのストリングの値ｓｊ＝（ｄｆｊ，（ｉ＋１）（ｋ−ｈ）−１，．．．ｄｆｊ，ｉ（ｋ−ｈ））２をセットする。ステップ１４０７において、生成部７５は、オーバラップ・ウィンドウｂｉ＝ｓ０＋ｓ１＋．．．＋ｓｇ−１を求める。ステップ１４０８〜１４０９は図３０のステップ１３０７〜１３０８に対応する。このようにして、生成部７５はオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を出力する。
【０１３５】
本発明によれば、公開鍵演算がウィンドウ法に基づいているのでＳＰＡによる秘密鍵の推定が防止される。入力値ｄに対して複数のウィンドウｂｉが乱数に従って選択されるのでＤＰＡによる秘密鍵の推定も防止される。本発明によれば、通常の分割指数法のように公開鍵演算を２回実行する必要がなく、公開鍵演算を１回だけ実行すればよいので、処理速度が速い。
【０１３６】
表２は、従来の分割指数法と本発明の処理速度の比較を示している。表２において、ｕは秘密鍵のビット長を、Ｍは乗算または点の加算／減算の計算量を、Ｓは２乗または点の２倍算の計算量を表す。ｈが可変長ｈｉの場合は、ｈは平均の長さを表す。
【０１３７】
【表２】
0004108391.tif 000011
【０１３８】
従来の分割指数法の処理速度は、図６に示す２つの公開鍵演算ｖ１＝ａｄ１（ｍｏｄｎ）とｖ２＝ａｄ２（ｍｏｄ  ｎ）の計算の方法によって異なるが、どのような方法を用いても最低２ｕＳの計算量を必要とする。一方、本発明では１回のみの公開鍵演算を必要とし、平均（Ｓ＋Ｍ／（ｋ−ｈ））ｕの計算量が必要である。一般的にＳ≒Ｍなので、従来の分割指数法の計算量は２ｕＭであり、一方、本発明の計算量は（１＋１／（ｋ−ｈ））ｕＭである。本発明においては、ｈ＜ｋであり（１＋１／（ｋ−ｈ））ｕＭ≦２ｕＭなので、本発明の公開鍵演算は従来の分割指数法より速い。例えば、ｋ＝４およびｈ＝２の場合、分割指数法は最低でも２ｕＭの計算量を必要とするが、本発明は平均１．５ｕＭの計算量しか必要としない。
【０１３９】
以上説明した実施形態では、所与の１つの秘密鍵ｄに対するオーバラップ・ウィンドウの取り得る（可能な）パターンの数は、オーバラップ・ウィンドウ法における各ウィンドウ生成においてそれぞれに使用される乱数の取り得るパターンの数にのみ依存する。ＤＰＡに対するオーバラップ・ウィンドウ法の安全性はオーバラップ・ウィンドウｂｉの取り得るパターンの数に依存する。乱数のパターンの数は、隣接のオーバラップ・ウィンドウｂｉ＋１とｂｉの重なりビット長ｈによって決まり、この数を大きくするためにはウィンドウの長さｋを大きくする必要がある。しかし、ウィンドウの長さｋを大きくすると、生成されるテーブルｗまたはＷのサイズが増加し、ウィンドウの生成、テーブルの生成およびテーブル・ルックアップの効率が低下する。
【０１４０】
以下、本発明による、所与の１つの秘密鍵ｄに対する複数のウィンドウｂｉのそれぞれの一部に、所定の同じ値または乱数に従って生成された同じ値Ｓを用いるオーバラップ・ウィンドウ法を説明する。ここでは、この方法を指数乗剰余演算に関して説明するが、点のスカラー倍算に関しても同様に実現できる。この方法は、生成されるテーブルのサイズを大きくすることなくウィンドウｂｉの取り得るパターンの数を増やすことができ、効率よく安全性が高められる。
【０１４１】
図３４Ａおよび３４Ｂは、本発明による、所与の１つの値ｄに対する複数のウィンドウのそれぞれの一部について所定の同じ値または乱数に従って生成された同じ値を用いるオーバラップ・ウィンドウ法の原理を説明するのに役立つ。
【０１４２】
図３４Ａを参照して説明すると、安全性を高めるために、オーバラップ・ウィンドウｂｉのビット長ｋをより長くする。さらに、ウィンドウｂｍ−１、ｂｍ−２、．．．ｂ０（ここで、ｍはウィンドウの数を表す）の各ウィンドウｂｉ中の所定位置におけるｈビットの重なりビット・ストリングの値を、乱数ｒに従って発生された同じ値Ｓに設定する。
【０１４３】
図３４Ｂを参照して説明すると、オーバラップ・ウィンドウ法の安全性はオーバラップ・ウィンドウｂｉのビット長ｋに応じて決まる。生成されるテーブルｗのサイズは、その同じ値Ｓを有するｈビット以外のｋ−ｈビットに応じて決まる。その理由は、ｈビットに対する同じ値Ｓを考慮すると、ｋビットのオーバラップ・ウィンドウｂｍ−１、ｂｍ−２、．．．ｂ０に対するｗ［ｂｉ］＝ａｘ（ｍｏｄ  ｎ）を満たす取り得る値ｗ［ｂｉ］の数は２ｋ−ｈだからである。従って、テーブルｗのエントリとして２ｋ−ｈ個の値ｗが計算され生成されてテーブルｗに格納される。テーブルｗをルックアップするとき、ウィンドウｂｉにおける下線のｋ−ｈビット部分のみをインデックスとして用いればよい。このようにして、テーブル・サイズを増加させることなく、およびテーブル・ルックアップに使用するインデックス値ｉｎｄの長さを増加させることなく、ウィンドウｂｉの長さを大きくすることができる。
【０１４４】
図３５は、後で説明する改良手法１および２において用いられる、複数のウィンドウのそれぞれの一部に同じ値Ｓを用いるオーバラップ・ウィンドウ法による暗号処理装置１６０の概略的構成を示している。暗号処理装置１６０は、値ａ、ｄおよびｎまたは値Ａおよびｄを入力して供給する入力部７２と、乱数発生器７４と、乱数発生器７４からの乱数に従って値ｄからオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を生成し同じ値Ｓおよび必要な場合は重なり長ｈを供給するウィンドウ値生成部７６と、生成部７６からのウィンドウを格納するメモリ７８と、入力部７２からの値ａおよびｎまたは値Ａと生成部７６からの値Ｓとからｋビットのウィンドウｂｉに対するテーブルｗまたはＷを生成するテーブル生成部８０と、テーブル・メモリ８２と、メモリ７８からのウィンドウおよび必要な場合は重なり長ｈに従ってテーブル・メモリ８２中のテーブルｗまたはＷをルックアップ（探索）して等式ｖ＝ａｄ（ｍｏｄ  ｎ）またはＶ＝ｄＡを演算するウィンドウ法演算部８４と、値ｖまたはＶを出力する出力部８６とを含んでいる。
【０１４５】
図３６は、後で説明する改良手法１および２において用いられる、複数のウィンドウのそれぞれの一部に同じ値Ｓを用いるオーバラップ・ウィンドウ法による逐次または反復処理型の暗号処理装置１６２の概略的構成を示している。暗号処理装置１６２は、乱数発生器７４からの乱数に従って値ｄからオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を順次生成し同じ値Ｓおよび必要な場合は重なり長ｈを供給するウィンドウ値生成部７６と、ウィンドウ値生成部７６からのウィンドウおよび必要な場合は重なり長ｈに従ってテーブル・メモリ８２中のテーブルｗまたはＷをルックアップして等式ｖ＝ａｄ（ｍｏｄ  ｎ）またはＶ＝ｄＡを演算するウィンドウ法演算部８４と、を含んでいる。暗号処理装置１６２は、さらに、図３５の暗号処理装置１６０と同様に、入力部７２と、乱数発生器７４と、テーブル生成部８０と、テーブル・メモリ８２と、出力部８６とを含んでいる。
【０１４６】
図３５および３６の暗号化装置１６０および１６２は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従ってこれらの要素７２〜８６を制御する。代替構成として、プロセッサ６２は、要素７２〜８６に対応する機能を実現するメモリ６４中のプログラムを実行することによって要素７２〜８６を実現してもよい。この場合、図３５および３６はフロー図として見ることができる。
【０１４７】
改良手法１  オーバラップ・ウィンドウの中央位置に同じ値Ｓを用いる手法
図３７は、本発明による、オーバラップ・ウィンドウｂｉの中央位置に同じ値Ｓを設定する手法を説明するのに役立つ。図３７を参照すると、この手法では、上述の図１０のオーバラップ・ウィンドウ法と同様に、隣接するウィンドウｂｉ＋１とｂｉが重なりビット長ｈを有する。ウィンドウｂｉは、ｋビットのシーケンスであり、ｋ−ｈ個のＭＳＢと、ｋ−ｈ個のＬＳＢと、残りのｓ個の中央のビット（ｓ＝ｋ−２（ｋ−ｈ）＝２ｈ−ｋ）とを含んでいる。この図において、ｋ−ｈ個のＭＳＢの値をｘ１とし、ｋ−ｈ個のＬＳＢの値をｘ２としている。ウィンドウｂｉのｋ−ｈ個のＬＳＢは乱数ｒｉに従って生成される。全てのオーバラップ・ウィンドウｂｍ−１、ｂｍ−２、．．．ｂ０の各々の中央位置のｓビット・ストリングの値が同じ値Ｓに設定される。値Ｓは、各値ｄごとに乱数ｒｄに従って発生してもよく、または固定値、例えば０でもよい。ウィンドウｂｉは、図１４および１５に示された第１の実施形態のウィンドウｂｉの中央のｓビットを値Ｓとしたものに相当する。
【０１４８】
ｖ＝ａｄ（ｍｏｄ  ｎ）は、オーバラップ・ウィンドウｂｉのｋ−ｈ個のＭＳＢおよびｋ−ｈ個のＬＳＢを有するインデックスｉｎｄｉを用いたテーブルｗのルックアップによるｗ［ｉｎｄｉ］の乗算と、累乗とによって求められる。Ｖ＝ｄＡは、そのようなインデックスｉｎｄｉを用いたテーブルｗのルックアップによるＷ［ｉｎｄｉ］の加算およびＷ［−ｉｎｄｉ］の減算と、乗算とによって求められる。
【０１４９】
図３８は、本発明による、オーバラップ・ウィンドウｂｉの中央位置に同じ値Ｓを用いる手法を用いた指数剰余演算の概略的なフロー図を示している。図３８のフロー図は、図１０のフロー図の変形である。この手法は、図１０のＲＳＡ暗号処理と図１２の楕円曲線暗号処理の双方に適用できる。
【０１５０】
次に、図３５および３６をも参照して、図３８のフロー図を説明する。ステップ１５０１において、入力部７２は値ａ、ｄおよびｎを入力して、ｄを生成部７６に供給し、ａおよびｎまたはＡを生成部８０に供給する。ステップ１５０２において、生成部７６は、乱数発生器７４からの乱数ｒｉに従って、値ｄからウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０の代わりにインデックスｉｎｄｍ−１，ｉｎｄｍ−２，．．．ｉｎｄ０を導出してメモリ７８に格納する。インデックスｉｎｄｉは、ウィンドウｂｉの中央のｓビットを取り除いたシーケンスで、０≦ｉｎｄｉ＜２ｘ１＜＜（ｋ−ｈ）＋ｘ２（０≦ｘ１＜２ｋ−ｈ，０≦ｘ２＜２ｋ−ｈ）の範囲の値である。ここで、ｘ１はウィンドウｂｉのｋ−ｈ個のＭＳＢを表し、ｘ２はウィンドウｂｉのｋ−ｈ個のＬＳＢを表す。インデックスｉｎｄｉは、ウィンドウｂｉを圧縮したものと見ることもできる。ステップ１５０４において、テーブル生成部８０は、２（ｋ−ｈ）個の値ｗ［０］，．．．ｗ［２２×（ｋ−ｈ）−１］を含むテーブルｗ（ｗ［ｘ１＜＜（ｋ−ｈ）＋ｘ２］＝ａ（ｘ１＜＜ｈ）＋（Ｓ＜＜（ｋ−ｈ））＋ｘ２（ｍｏｄ  ｎ））を生成してメモリ８２に格納する。ステップ１５０２とステップ１５０４は順序が逆であってもよい。
【０１５１】
ウィンドウ法演算のためのステップ１５０６〜１５１６において、演算部８４は、ｉ＝ｍ−１，ｍ−２，．．．０について順次、ｉｎｄｉに従って、メモリ８２のテーブルｗのルックアップによるｗ［ｉｎｄｉ］の乗算と累乗とを、ｖに対して実行する。ステップ１５０６において、演算部８４はｖ＝１およびｉ＝ｍをセットする。ステップ１５０８において、演算部８４はｉ＝ｉ−１をセットする。ステップ１５１０において、演算部８４は、後で詳しく説明するようにインデックスｉｎｄ＝（ｂｉ，（ｋ−１），ｂｉ，（ｋ−２），．．．ｂｉ，ｈ）｜｜（ｂｉ，（ｋ−ｈ−１），ｂｉ，（ｋ−ｈ−２），．．．ｂｉ，０）を用いてテーブルｗをルックアップして、ｖにｗ［ｉｎｄｉ］を乗算する。ここで、ａ｜｜ｂは、複数ビット値ａをＭＳＢとし複数ビット値ｂをＬＳＢとするシーケンス値を生成する結合演算であり、αビット・ストリングａ＝（ａα−１，ａα−２，．．．ａ０）およびβビット・ストリングｂ＝（ｂβ−１，ｂβ−２，．．．ｂ０）に対して、α＋βビット・ストリングａ｜｜ｂ＝ａα−１，ａα−２，．．．ａ０，ｂβ−１，ｂβ−２，．．．ｂ０）となる。ステップ１５１２において、演算部８４はｉの値と値０とを比較してｉ＝０かどうかを判定する。ｉ＝０でないと判定された場合には、ステップ１５１４において、演算部８４は、（ｋ−ｈ）回の２乗によってｖの２（ｋ−ｈ）乗を生成する。ステップ１５１２においてｉ＝０であると判断された場合には、ステップ１５１６において演算部８４は、一連のオーバラップ・ウィンドウの演算結果が従来のウィンドウ法の演算結果と整合するようにするための補正演算または補償演算を行う。ステップ１５１８において、出力部８６はｖ＝ａｄ（ｍｏｄ  ｎ）を出力する。ステップ１５０２、１５０４およびステップ１５０６〜１５１４は同時に（並行して）または反復的に実行されてもよい。
【０１５２】
このように、ｓビットの同じ値Ｓの使用により、インデックスｉｎｄの必要な長さは、ｋビットのウィンドウに対して、ｋ−ｈ個のＭＳＢとｋ−ｈ個のＬＳＢに対する２×（ｋ−ｈ）ビットとなり、テーブル・サイズは２２×（ｋ−ｈ）個のｗの値となる。この手法において、最初のウィンドウ以外のウィンドウｂｉの値は、ビットの長さｓ（数）に応じて１つ乃至数個前までの複数のウィンドウに依存する。図１０の指数剰余演算ではウィンドウｂｉの値は１つ前のウィンドウにおける乱数値にのみ依存するので、この手法の方が中間データの量が増え、安全性が高くなる。なお、Ｓ以外の部分について、簡単化のために、ｋ−ｈ個のＭＳＢおよびｋ−ｈ個のＬＳＢについて説明するが、これらのＭＳＢの長さとＬＳＢの長さとは等しくなくてもよい。
【０１５３】
図３９は、改良手法１による最初の３つのウィンドウの生成の例を示している。最初のウィンドウｂｍ−１において、ｋ−ｈ個のＭＳＢは値ｄの中のｋ−ｈ個のＭＳＢに一意的に決定され、次の中央の２ｈ−ｋ個のＭＳＢは値Ｓに一意的に決定され、ｋ−ｈ個のＬＳＢの値は乱数ｒｍ−１に従って決定される。中間データの取り得るパターンの数は２（ｋ−ｈ）である。次のウィンドウｂｍ−２において、ｋ−ｈ個のＭＳＢは値ｄの中の後続のｋ−ｈ個のＭＳＢと、ウィンドウｂｍ−１における値Ｓとから一意的に決定され、次の２ｈ−ｋ個のＭＳＢは値Ｓに決定され、ｋ−ｈ個のＬＳＢのストリングの値は乱数ｒｍ−２に従って決定される。中間データの取り得るパターンの数は２２（ｋ−ｈ）である。次のウィンドウｂｍ−３において、ｋ−ｈ個のＭＳＢは、値ｄの中の後続のｋ−ｈ個のＭＳＢと、ウィンドウｂｍ−１におけるｋ−ｈ個のＬＳＢと、ウィンドウｂｍ−２における値Ｓとから一意的に決定され、次の２ｈ−ｋ個のＭＳＢは値Ｓに決定され、ｋ−ｈ個のＬＳＢは乱数ｒｍ−３に従って決定される。ウィンドウｂｉにおけるｋ−ｈ個のＬＳＢと、次のウィンドウｂｉ−１における値Ｓと、次のウィンドウｂｉ−２におけるｋ−ｈ個のＭＳＢとの総和が値ｄにおけるｍ−（ｉ−２）番目のｋ−ｈ個のＭＳＢの値になるように、ウィンドウｂｉ−２におけるｋ−ｈ個のＭＳＢが設定される。Ｓ＝０、ｋ＝６、ｈ＝４の場合、中間データの可能なパターンの数は２２（ｋ−ｈ）＝２４である。３番目以降のウィンドウも同様に生成される。
【０１５４】
図４０は、改良手法１による本発明の第１１の実施形態による、ウィンドウ生成部７６において、重なりビット長ｈを有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順序で生成するためのフローチャートの一部を示している。図４１は、図４０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態は、図１８および１９に関連して説明した第３の実施形態の変形と見ることができる。この実施形態は、第３の実施形態において乱数ｗｌｉを、乱数に従って生成されたｋ−ｈ個のＭＳＢと同じ値Ｓを有するｓ個のＬＳＢとで構成したものに相当する。
【０１５５】
ｕビットの秘密鍵ｄ＝（ｄｕ−１，ｄｕ−２，．．．ｄ０）２から重なりビット長ｈを有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１を生成するための手順を、図４０および４１を参照して説明する。ｓビットの同じ値を固定値Ｓ＝０とし、ウィンドウの重なり幅をhビットとし、ｓ＝ｋ−２（ｋ−ｈ）＝２ｋ−ｈとする。但し、Ｓは０以外の値であってもよい。この場合、簡単化のためにｍ＝（ｕ−ｈ）／（ｋ−ｈ）は正の整数とする。
【０１５６】
図３８におけるステップ１５０１の後の図４０のステップ１６０２において、生成部７６は中間ウィンドウｄ’＝ｄ（初期値）、ｉ＝０、ｕ＝ｄ’のビット数とセットする。ステップ１６０４において、生成部７６は値ｕが基準値ｋより小さいかどうかを判定する。それが基準値より小さいと判定された場合は、生成部７６はステップ１６１８においてｍ＝ｉとセットして、手順は図３８のステップ１５０４に進む。それが基準値より小さくはないと判定された場合は、手順はステップ１６０６に進む。
【０１５７】
ステップ１６０６において、生成部７６は、値ｕが基準値ｋ＋ｈより大きいかどうかを判定する。それが基準値より大きいと判定された場合は、手順はステップ１６０８に進む。それが基準値より大きくない判定された場合は、手順はステップ１６１２に進む。
【０１５８】
生成部７６は、ステップ１６０８において、ｋ−ｈビットの乱数ｒｉ＝（ｒｋ−ｈ−１，ｒｋ−ｈ−２，．．．ｒ０）を生成し、ステップ１６１０において、インデックスｉｎｄｉ＝ｒｉ｜｜（ｄ’のｋ−ｈ個のＬＳＢ）＝（ｒｋ−ｈ−１，ｒｋ−ｈ−２，．．．ｒ０，ｄ’ｋ−ｈ−１，ｄ’ｋ−ｈ−２，．．．ｄ’０）を生成する。
【０１５９】
ステップ１６１４において、生成部７６は、中間ウィンドウｄ’から中央にＳ値の２ｈ−ｋ個のビットを含むウィンドウｂｉ＝（ｂｉ，ｋ−１，．．．ｂｉ，０）を減算し、即ちインデックスｉｎｄ（ｉ）のｋ−ｈ個のＭＳＢとｋ−ｈ個のＬＳＢの間にＳ値のｓ個のビット・ストリングを挿入したウィンドウｂｉの値を減算して、その減算値のｋ−ｈ個のＬＳＢを切り捨てたものを新しい中間ウィンドウｄ’とする。ステップ１６１６において、生成部７６は、ｕをその中間ウィンドウｄ’のビット数にセットし、ｉ＝ｉ＋１とセットする。次いで、手順はステップ１６０４に戻る。
【０１６０】
生成部７６は、ステップ１６１２において、インデックスｉｎｄｉ＝（ｄ’のｈビット上位のｋ−ｈ個のＬＳＢ）｜｜（ｄ’のｋ−ｈ個のＬＳＢ）＝（ｄ’ｋ−１，ｄ’ｋ−２，．．．ｄ’ｈ，ｄ’ｋ−ｈ−１，ｄ’ｋ−ｈ−２，．．．ｄ’０）を生成する。これによって、ウィンドウｂ０，ｂ１，．．．ｂｍ−１の累積和（ｂｍ−１＜＜（ｕ−ｋ））＋（ｂｍ−２＜＜（ｕ−２ｋ＋ｈ））＋．．．＋ｂ０＝ｄとなる。
【０１６１】
図４２は、改良手法１による本発明の第１２の実施形態による、生成部７６において、重なりビット長ｈを有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０を生成するためのフローチャートの一部を示している。図４３は、図４２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。この実施形態では、各ウィンドウの異なる複数の乱数をまとめて生成し、補正用の差を予め求めるものである。
【０１６２】
図３８におけるステップ１５０１の後の図４２におけるステップ１７０２において、生成部７６はｓビットの同じ値Ｓを決定する。ここでは同じ値を固定値Ｓ＝０とする。ステップ１７０４において、生成部７６は、値ｄのビット数に従って、全てのウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０におけるＳをＭＳＢ位置からｋ−ｈビットごとに配置して加算した乱数シーケンスＲ＝（Ｓ＜＜（ｕ−ｈ））＋ （Ｓ＜＜（ｕ−（ｈ＋ｋ−ｈ）））＋（Ｓ＜＜（ｕ−（ｈ＋２（ｋ−ｈ））））．．．＋（Ｓ＜＜（ｋ−ｈ））を生成する。ここで、ｍ＝（ｕ−ｈ）／（ｋ−ｈ）は正の整数とする。ステップ１７０６において、生成部７６はｄ’＝ｄ−Ｒを求める。
【０１６３】
ステップ１７０８において、生成部７６は、ｄ’からｈ個のＭＳＢおよびｈ個のＬＳＢを取り除いてｕ−２ｈビット値ｄｍ＝（ｄ’ｕ−ｈ−１，ｄ’ｕ−ｈ−２，．．．ｄ’ｈ）とする。ステップ１７０８において、生成部７６は、ｄｍ＝ｄｍ１＋ｄｍ２であるような２つのシーケンスｄｍ１およびｄｍ２を乱数に従って生成する。ステップ１７１２において、生成部７６は、次のような２つのシーケンスｄｈおよびｄｌを生成する。
【数９】
0004108391.tif 000012
【０１６４】
ステップ１７１４において、生成部７６は、２つのシーケンスｄｈおよびｄｌから次のようなインデックスｉｎｄｍ−１，ｉｎｄｍ−２，．．．ｉｎｄ０を生成する。その後、手順は図３８のステップ１５０４へ進む。
【数１０】
0004108391.tif 000013
【０１６５】
また、他の実施形態として、値ｄのＭＳＢの位置からインデックスを順次生成してもよく、各ウィンドウのビットに負の値を用いてもよく、上述のｄｈおよびｄｌを用いずに例えばウィンドウ法およびバイナリ・メソッドのような様々な方法で補正演算を行うことができる。
【０１６６】
改良手法２  オーバラップ・ウィンドウのＬＳＢｓまたはＭＳＢｓに同じ値Ｓを用いる手法
図４４は、本発明による、オーバラップ・ウィンドウｂｉのＬＳＢまたはＭＳＢとしてｓビットの同じ値Ｓを用いる手法を説明するのに役立つ。図４４を参照すると、この手法では、上述の図１０のオーバラップ・ウィンドウ法と同様に、隣接するウィンドウｂｉ＋１とｂｉが重なりビット長ｓを有する。ウィンドウｂｉは、ｋ＋ｓビットのシーケンスであり、ｋ個のＭＳＢと、値Ｓのｓ個のＬＳＢとを含んでいる。ここで、この手法におけるウィンドウｂｉの長さはｓビットを除外したビット数ｋで定義されるものとする。全てのオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０の各々のｓ個のＬＳＢのストリングの値は、値ｄに対して乱数ｒｄに従って発生された同じ値Ｓである。この図ではＳ＝（００１１）２である。ウィンドウｂｉは、図１４および１５に示された第１の実施形態のウィンドウｂｉのｈ個のＬＳＢを（ｈ＝ｓ）値Ｓとしたものである。
【０１６７】
ｖ＝ａｄ（ｍｏｄ  ｎ）は、オーバラップ・ウィンドウｂｉのｋ個のＭＳＢを有するインデックスｉｎｄｉを用いたテーブルｗのルックアップによるｗ［ｉｎｄｉ］の乗算と、累乗とによって求められる。Ｖ＝ｄＡは、そのようなインデックスｉｎｄｉを用いたテーブルｗのルックアップによるＷ［ｉｎｄｉ］の加算およびＷ［−ｉｎｄｉ］の減算と、乗算とによって求められる。
【０１６８】
図４５は、本発明による、オーバラップ・ウィンドウｂｉのＬＳＢまたはＭＳＢのストリングに同じ値Ｓを用いる手法を用いた指数剰余演算の概略的なフロー図を示している。図４５の処理フローは、図１０の処理フローの変形である。この手法は、図１０のＲＳＡ暗号処理と図１２の楕円曲線暗号処理の双方に適用できる。
【０１６９】
次に、図３５および３６をも参照して、図４５のフロー図を説明する。ステップ１６０１において、入力部７２は値ａ、ｄおよびｎを入力して、ｄを生成部７６に供給し、ａおよびｎまたはＡを生成部８０に供給する。次いで、生成部７６は乱数ｒｄに従って同じ値Ｓを生成する。ステップ１８０２において、テーブル生成部８０は、ＬＳＢに同じ値Ｓが用いられるときはテーブルｗ（ｗ［ｘ］＝ａｘ＜＜ｓ＋Ｓ（ｍｏｄ  ｎ））（０≦ｘ＜２ｋ，０≦Ｓ＜２ｓ）を生成し、ＭＳＢに同じ値Ｓが用いられるときはテーブルｗ（ｗ［ｘ］＝ａＳ＜＜ｋ＋ｘ（ｍｏｄ  ｎ））（０≦ｘ＜２ｋ，０≦Ｓ＜２ｓ）を生成してメモリ８２に格納する。ステップ１８０４において、生成部７６は、乱数発生器７４からの乱数ｒｉに従って、値ｄからインデックスｉｎｄｍ−１，ｉｎｄｍ−２，．．．ｉｎｄ０を導出してメモリ７８に格納する。ここで、ｍ＝ｆｌｏｏｒ（（ｕ−ｓ）／ｋ）である。ステップ１８０２とステップ１８０４は順序が逆であってもよい。
【０１７０】
ステップ１８０６〜１８１４において、演算部８４は、ｉ＝ｍ−１，ｍ−２，．．．０について順次、ｂｉに従って、メモリ８２のテーブルｗのルックアップによるｗ［ｂｉ］の乗算と累乗とを、ｖに対して実行する。ステップ１８０６において、演算部８４はｖ＝１およびｉ＝ｍをセットする。ステップ１８０８において、演算部８４はｉ＝ｉ−１をセットする。ステップ１８１０において、演算部８４は、後で詳しく説明するようにウィンドウｂｉのｋ個のＭＳＢをインデックスｉｎｄとしてテーブルｗをルックアップして、ｖにｗ［ｉｎｄｉ］を乗算する。ステップ１８１２において、演算部８４はｉの値と値０とを比較してｉ＝０かどうかを判定する。ｉ＝０でないと判断された場合には、ステップ１８１４において、演算部８４は、ｋ回の２乗（または後で説明するｋ−ｈ’回の２乗）によってｖの２ｋ乗（または２ｋ−ｈ’）を生成する。ステップ１８１２においてｉ＝０であると判断された場合には、ステップ１８１６において、出力部８６はｖ＝ａｄ（ｍｏｄ  ｎ）を供給する。ステップ１８０２、１８０４およびステップ１８０６〜１５１４は同時に（並行して）または反復的に実行されてもよい。
【０１７１】
図４６は、改良手法２による、ＬＳＢにＳを用いた場合の最初の３つのウィンドウの生成を示している。最初のウィンドウｂｍ−１において、ｋ個のＭＳＢは値ｄ中のｋ個のＭＳＢに一意的に決定され、ｓ個のＬＳＢは値Ｓに決定される。中間データの取り得るパターンの数は２ｓである。次のウィンドウｂｍ−２において、ｋ個のＭＳＢは値ｄの中の後続のｋ個のＭＳＢとウィンドウｂｍ−１における値Ｓとから一意的に決定され、ｓ個のＬＳＢは値Ｓに決定される。中間データの取り得るパターンの数は２ｓである。次のウィンドウｂｍ−３において、ｋ個のＭＳＢは値ｄの中の後続のｋ個のＭＳＢとウィンドウｂｍ−２における値Ｓとから一意的に決定され、ｓ個のＬＳＢは値Ｓに決定される。中間データの取り得るパターンの数は２ｓである。３番目以降のウィンドウも同様に生成される。ｄにおける最後に残ったＬＳＢのシーケンスは補正演算で用いられる。
【０１７２】
ｓビットの同じ値Ｓの使用により、インデックスｉｎｄの必要な長さは、ｋ＋ｓビットのウィンドウに対してｋビットとなり、テーブル・サイズは２ｋ個のｗの値となる。その処理速度は、ｋビットの通常の非オーバラップ・ウィンドウ法の従来のウィンドウ法とほぼ同程度であり、非常に高速である。この手法では、同じ値Ｓは乱数等によって生成される。この手法における中間データの取り得るパターンの数はｓビット値Ｓの可能なパターンの数に依存する。従って、ｓの長さを充分大きくすれば安全性がより高くなる。Ｓを長くしてもテーブル・サイズは増加せず、処理速度も低下しない。テーブルの作成は適当な方法で行えばよく、補正演算はウィンドウ法やバイナリ・メソッド等の適当な方法で行えばよい。
【０１７３】
図４７は、改良手法２による本発明の第１３の実施形態による、ウィンドウ生成部７６において、重なりビット長ｓを有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順序で生成するためのフローチャートの一部を示している。図４８は、図４７に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【０１７４】
図４５におけるステップ１８０２の後の図４７のステップ１９０４において、生成部７６は、初期値としてのｓ個の０ビットをＭＳＢとして含み値ｄ中のｋ個のＭＳＢをＬＳＢとして含む中間ウィンドウｄ’を生成する。ステップ１９０６において、生成部７６は、初期値としてｖ＝１、ｊ＝ｕ−ｓとセットする。
【０１７５】
ステップ１９０８において、生成部７６は、前の中間ウィンドウｄ’のｓ個のＬＳＢをＭＳＢとして含み、値ｄ中の後続のｋ個のＭＳＢをＬＳＢとして含む新しい中間ウィンドウｄ’＝（ｄ’ｓ−１，．．．ｄ’０，ｄｊ−１，．．．ｄｊ−ｋ）を生成する。
【０１７６】
ステップ１９１０において、演算部８４は、ｋ回の２乗によってｖの２ｋ乗を生成する。ステップ１９１２において、演算部８４は、中間ウィンドウｄ’のｋ個のＭＳＢの値が０に等しいかどうかを判定する。それが０に等しいと判定された場合は、手順はステップ１９２０に進む。それが０に等しくないと判定された場合は、手順はステップ１９１４に進む。
【０１７７】
ステップ１９１４において、生成部７６は、中間ウィンドウｄ’から同じ値Ｓを減算して新しい中間ウィンドウｄ’とする。減算前のｄ’のｋ個のＭＳＢは１以上の値なので、減算において繰り下がりが生じても、中間ウィンドウｄ’の値は正の値となる。ステップ１９１６において、生成部７６は、中間ウィンドウｄ’のｋ個のＭＳＢをインデックスｉｎｄとしてセットする。ステップ１９１８において、演算部８４は、ｖにｗ［ｉｎｄ］を乗算する。
【０１７８】
ステップ１９１２は、k個のＭＳＢが1以上になるまで、手順がステップ１９１４〜１９１８をスキップするようにする。換言すれば、ｋ個のＭＳＢが０より大きくない場合は、ｄ’中のｋ個のＭＳＢが０より大きくなるまで順次ｄ中の後続のｋ個のＭＳＢをサーチする。
【０１７９】
ステップ１９２０において、生成部７６はｊをｊ−ｋとセットする。ステップ１９２２において、生成部７６は、ｊがｋ＋ｓ以上かどうかを判定する。ｊがｋ＋ｓ以上であると判定された場合は、手順はステップ１９０８に戻る。ｊがｋ＋ｓ以上でないと判定された場合は、手順は図４５のステップ１８１６に進む。ステップ１８１６において、演算部８４は補正演算を行う。即ち、ウィンドウがもはや生成できなくなったときには、ｄの残りのビットに対して補正演算を行う。
【０１８０】
図４９は、改良手法２による本発明の第１４の実施形態による、ウィンドウ生成部７６において、重なりビット長ｓを有するオーバラップ・ウィンドウｂ０，ｂ１，．．．ｂｍ−１をこの順序で生成するためのフローチャートの一部を示している。図５０は、図４９に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【０１８１】
図４５におけるステップ１８０２の後の図４９のステップ２００４において、生成部７６は、最初に中間ウィンドウｄ’＝ｄ、中間インデックス・シーケンスｄ’’＝０、ｊ＝０、ｉ＝ｕとセットする。
【０１８２】
ステップ２００６において、生成部７６は、中間ウィンドウｄ’＝ｄ’−Ｓを計算し、この中間ウィンドウｄ’のｋ個のＬＳＢを追加的なＭＳＢとして有するシーケンスｄ’’＝（ｄ’ｋ−１，ｄ’ｋ−２，．．．ｄ’０，ｄ’’ｊ−１，ｄ’’ｊ−２，．．．ｄ’’０）を生成する。その追加的なｋビット・ストリング（ｄ’ｋ−１，ｄ’ｋ−２，．．．ｄ’０）はインデックスｉｎｄｉである。最初のｓ個のＬＳＢのシーケンスｓｅｑｃは補正用のシーケンスである。ステップ２００８において、生成部７６は、中間ウィンドウｄ’を２ｋで除算し、即ちｋ個のＬＳＢを切り捨て、ｊ＝ｊ＋ｋおよびｉ＝ｉ−ｋとセットする。
【０１８３】
ステップ２０１０において、生成部７６は、ｉがｋ＋ｓより大きいかどうかを判定する。ｉがｋ＋ｓより大きいと判定された場合は、手順はステップ２００６に戻る。ｉがｋ＋ｓより大きくないと判定された場合は、手順はステップ２０１２に進む。ステップ２０１２において、生成部７６は、中間ウィンドウｄ’のｓ個のＬＳＢを切り捨てた値が０に等しいかどうかを判定する。その値が０に等しいと判定された場合は、生成部７６は、ステップ２０１６においてｊ＝ｊ＋ｓとセットしてステップ２０２２に進む。その値が０に等しくないと判定された場合は、生成部７６は、ステップ２０１８においてｊ＝ｊ＋ｓ＋ｋとセットしてステップ２０２０に進み、そこでステップ２００６における場合のようにｄ’＝ｄ’−Ｓを計算し、シーケンスｄ’’＝（ｄ’ｋ−１，ｄ’ｋ−２，．．．ｄ’０，ｄ’’ｊ−１，ｄ’’ｊ−２，．．．ｄ’’０）を生成する。その後、手順はステップ２０２２に進む。
【０１８４】
ステップ２０２２において、ｄ’の残りのビットをＭＳＢとして含むシーケンスｄ’’＝ｄ’｜｜（ｄ’’ｊ−１，ｄ’’ｊ−２，．．．ｄ’’０）を生成する。ステップ２０２４において、生成部７６は、シーケンスｄ’’から、最初のｓ個のＬＳＢを除外して、ｋ個のＬＳＢをインデックスｉｎｄｉとして順次取り出して、ｍ個のインデックスｉｎｄ０，ｉｎｄ１，．．．ｉｎｄｍ−１を生成する。最初のｓ個のＬＳＢのシーケンスｓｅｑｃは補正演算において用いられる。次いで、手順は図４５のステップ１８０６へ進む。
【０１８５】
図５１は、改良手法２による本発明の第１５の実施形態による、ウィンドウ生成部７６において、重なりビット長ｓを有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順序で生成するためのフローチャートの一部を示している。図５２は、図５１に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【０１８６】
ステップ２１０６において、生成部７６は、ｍ個のＳ値のｓビット・ストリングをＭＳＢ位置からｋビットごとに配置して加算した乱数シーケンスＲ＝（Ｓ＜＜（ｕ−（ｋ＋ｓ）））＋（Ｓ＜＜（ｕ−（２ｋ＋ｓ）））＋．．．（Ｓ＜＜ｋ）＋Ｓを生成する。ここで、ｍ＝ｆｌｏｏｒ（（ｕ−ｓ）／ｋ）とする。
【０１８７】
ステップ２１０８において、生成部７６は、中間ウィンドウｄ’＝ｄ−Ｒを計算する。ステップ２１１０において、生成部７６は、インデックスｉｎｄｊ＝（ｄ’ｕ−ｉ×ｋ−１，ｄ’ｕ−ｉ×ｋ−２，．．．ｄ’ｕ−ｉ×ｋ−ｋ）をｉ＝０，１，．．．ｍ−１（ｊ＝ｍ−１−ｉ）の順序で生成する。中間ウィンドウｄ’の長さがｕビット未満のときはＭＳＢ位置に０ビットを埋めてｕビットにする。次いで、手順は図４５のステップ１８０６に進む。
【０１８８】
図５３は、改良手法２による本発明の第１６の実施形態による、ウィンドウ生成部７６において、重なりビット長ｈ’＋ｓを有するオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０をこの順序で生成するためのフローチャートの一部を示している。この実施形態は、第１の実施形態と第１５の実施形態とを組み合わせたものである。図５４は、図５３に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【０１８９】
図４５におけるステップ１８０２の後の図５３のステップ２２０６において、生成部７６は、ｍ個のＳ値のｓビット・ストリングをＭＳＢ位置からｋ−ｈ’ビットごとに配置して加算した乱数シーケンスＲ＝（Ｓ＜＜（ｕ−（ｋ＋ｓ）））＋（Ｓ＜＜（ｕ−（ｋ＋ｓ）−（ｋ−ｈ’）））＋（Ｓ＜＜（ｕ−（ｋ＋ｓ）−２（ｋ−ｈ’）））＋．．．（Ｓ＜＜（ｋ−ｈ’））＋Ｓを生成する。ここで、ｍ＝ｆｌｏｏｒ（（ｕ−ｓ−ｈ’）／（ｋ−ｈ’））とする。図５４において、ｈ’＝１である。
【０１９０】
ステップ２２０８において、生成部７６は、中間ウィンドウｄ’＝ｄ−Ｒを計算する。最初の乱数値ｒｍ−１＝ｒｆｌｏｏｒ（（ｕ−ｓ−ｈ’）／（ｋ−ｈ’））−１を初期値０にセットする。ステップ２２１０において、生成部７６は、ｉ＝ｆｌｏｏｒ（（ｕ−ｓ−ｈ’）／（ｋ−ｈ’））とセットする。ステップ２２１２において、生成部７６はｉ＝ｉ−１とセットする。
【０１９１】
ステップ２２１４において、生成部７６は、乱数に従ってｋビットのインデックスｉｎｄｉ＝（ｉｎｄｉ，ｋ−１，ｉｎｄｉ，ｋ−２，．．．ｉｎｄｉ，０）を生成する。インデックスｉｎｄｉ中のｈ’個のＬＳＢを乱数ｒｉに従って生成し、そのｈ’個のＭＳＢとインデックスｉｎｄｉ＋１のｈ’個のＬＳＢの和がｄ’中の対応するｈ’個のビット・ストリングの値になるように、そのｈ’個のＭＳＢを決定し、中央のｋ−２ｈ’ビットはｄ’中の対応するビットを取り出してコピーする。
【０１９２】
ステップ２２１６において、生成部７６は、ｉ＝０かどうかを判定する。ｉ＝０と判定された場合には手順はステップ２２１８に進む。ｉ＝０と判定されなかった場合には手順はステップ２２１２に戻る。
【０１９３】
ステップ２２１８において、演算部８４は、ｖ＝１、ｉ＝ｆｌｏｏｒ（（ｕ−ｓ）／（ｋ−ｈ’））とセットする。ステップ２２２０〜２２２６は図４５のステップ１８０６〜１８１４と同様である。ステップ２２２６において、演算部８４は、ｋ−ｈ’回の２乗によってｖのまたは２ｋ−ｈ’を生成する。その後、手順は図４５のステップ１５１６へ進む。
【０１９４】
図５５は、次に説明する改良手法３において用いられる、複数のウィンドウのそれぞれの複数の部分に同じ値Ｓを用いるオーバラップ・ウィンドウ法による暗号処理装置１６４の概略的構成を示している。暗号処理装置１６４は、図７の暗号処理装置６０と同様に、値ａ、ｄおよびｎまたは値Ａおよびｄを入力して供給する入力部７２と、乱数発生器７４と、乱数発生器７４からの乱数に従って値ｄからオーバラップ・ウィンドウｂｍ−１，ｂｍ−２，．．．ｂ０および重なり長ｈｍ−１  （ｍｏｄ  ｓ＋１），ｈｍ−２  （ｍｏｄ  ｓ＋１），．．．ｈｍ−（ｓ＋１）  （ｍｏｄ  ｓ＋１）を生成するウィンドウおよび重なり長生成部７７と、生成部７７からのウィンドウおよび重なり長を格納するメモリ７８と、入力部７２からの値ａおよびｎまたは値Ａからｋビットのウィンドウｂｉに対するテーブルｗまたはＷを生成するテーブル生成部８０と、テーブル・メモリ８２と、メモリ７８からのウィンドウおよび重なり長に従ってテーブル・メモリ８２中のテーブルｗまたはＷをルックアップして等式ｖ＝ａｄ（ｍｏｄ  ｎ）またはＶ＝ｄＡを演算するウィンドウ法演算部８４と、値ｖまたはＶを出力する出力部８６とを含んでいる。
【０１９５】
図５６は、後で説明する改良手法３において用いられる、複数のウィンドウのそれぞれの複数の部分に同じ値Ｓを用いるオーバラップ・ウィンドウ法による逐次または反復処理型の暗号処理装置１６６の概略的構成を示している。暗号処理装置１６６は、乱数発生器７４からの乱数に従って値ｄからオーバラップ・ウィンドウｂｉおよび重なり長ｈｉ  （ｍｏｄ  ｓ＋１）を順次生成するウィンドウおよび重なり長生成部７７と、生成部７７からのウィンドウおよび重なり長に従ってテーブル・メモリ８２中のテーブルｗまたはＷをルックアップして等式ｖ＝ａｄ（ｍｏｄ  ｎ）またはＶ＝ｄＡを演算するウィンドウ法演算部８４と、を含んでいる。暗号処理装置１６６は、さらに、図５４の暗号処理装置６０と同様に、入力部７２と、乱数発生器７４と、テーブル生成部８０と、テーブル・メモリ８２と、出力部８６とを含んでいる。
【０１９６】
図５５および５６の暗号化装置１６４および１６６は、さらに、プロセッサ６２と、ＲＯＭのようなプログラム・メモリ６４とを含んでいる。プロセッサ６２は、メモリ６４に格納されているプログラムに従ってこれらの要素７２〜８６を制御する。代替構成として、プロセッサ６２は、要素７２〜８６に対応する機能を実現するメモリ６４中のプログラムを実行することによって要素７２〜８６を実現してもよい。この場合、図５５および５６はフロー図として見ることができる。
【０１９７】
改良手法３  オーバラップ・ウィンドウにおいて値ｄからの複数のｔビット値の間に同じｓ×ｔビット値Ｓを配置する手法
図５７、５８および５９は、本発明による、オーバラップ・ウィンドウｂｉにおいて値ｄから取り出されたｃ個の位置のｔビット値の間にｓ×ｔビットの長さの同じ値Ｓを配置する手法を説明するのに役立つ。図５７、５８および５９を参照すると、この手法では、オーバラップ・ウィンドウｂｉの長さｋはｋ＝ｃ×ｔ＋ｓ×（ｃ−１）×ｔ＝ｓ×ｃ×ｔ−ｓ×ｔ＋ｃ×ｔビットである（ｃ、ｓおよびｔは正の整数）。図５７においてｔ＝１およびｓ＝１であり、図５８においてｔ＝１およびｓ＝２であり、図５９においてｔ＝２およびｓ＝２である。
【０１９８】
値ｄに対する、最初のｓ＋１個のウィンドウｂｍ−１，．．．ｂｍ−（ｓ＋１）のそれぞれの先頭位置は、値ｄにおける対応する１番目．．．ｓ＋１番目のＭＳＢを基準として、値ｄに対して、対応するｃ個の乱数ｒ０，．．．ｒｓ（０≦ｒｊ≦ｃ−１）に従って決定された値Ｈｊ＝（ｃ−ｒｊ−１）×ｔビット分だけ上位のビット位置に位置する。最初のウィンドウｂｍ−１は、そのウィンドウの先頭ビット位置が、ｄにおける基準位置としてのＭＳＢ（＝ｄｕ−１）より乱数ｒ０（０≦ｒ０≦ｃ−１）に従うＨ０＝（ｃ−ｒ０−１）×ｔビット分だけ上位のビット位置に配置される。次のウィンドウｂｍ−２は、そのウィンドウの先頭ビット位置が、ｄにおける基準位置としての次のＭＳＢ（＝ｄｕ−２）より乱数ｒ１（０≦ｒ１≦ｃ−１）に従うＨ１＝（ｃ−ｒ１−１）×ｔビット分だけ上位のビット位置に配置される。ｓ＝２以上の場合、さらに次のウィンドウｂｍ−３は、そのウィンドウの先頭ビット位置が、ｄにおける基準位置としての次のＭＳＢ（＝ｄｕ−３）より乱数ｒ２（０≦ｒ２≦ｃ−１）に従うＨ２＝（ｃ−ｒ２−１）×ｔビット分だけ上位のビット位置に配置される。
【０１９９】
ウィンドウｂｉは、ｓ×ｔビットおきのそのＭＳＢおよびＬＳＢを含むｃ個のｔビット位置に（陰影が付けられたビット位置に）、値ｄ中のｋビット・シーケンスにおける対応するビット位置におけるｔビット値を含むようになっている。ウィンドウｂｉは、ｃ個のｔビット値の間のそれぞれの連続するｔビット幅のｓ個の位置に（陰影のないビット位置）、同じｔビット値Ｓを挿入される。この値Ｓは、好ましくは０であり、即ちｃ個のビットの間の全てのｔビット幅のｓ個の位置にビット値０が挿入される。
【０２００】
後続のウィンドウｂｉ−１は、前のウィンドウｂｉのｃ個のｔビット値で捕捉されなかったその間にある連続するｓ×ｔビットの位置における他のｔビット値を捕捉するように決定される。さらに後続のウィンドウｂｉ−２は、前のウィンドウｂｉおよびｂｉ−１のそれぞれのｃ個のｔビット値で捕捉されなかったその間にある連続するｓ×ｔビットの位置における他のｔビット値を捕捉するように決定される。
【０２０１】
このようにして、最初のウィンドウｂｍ−１とｓ＋１個毎（ｓ個おき）の後続のウィンドウｂｍ−１，ｂｍ−１−（ｓ＋１），ｂｍ−１−２（ｓ＋１），．．．とは系列０のウィンドウのグループを形成する。最初のウィンドウｂｍ−１とｓ＋１個毎（ｓ個おき）の後続のウィンドウｂｍ−１，ｂｍ−１−（ｓ＋１），ｂｍ−１−２（ｓ＋１），．．．とは系列０のウィンドウのグループを形成する。２番目のウィンドウｂｍ−２とｓ＋１個毎（ｓ個おき）の後続のウィンドウｂｍ−２，ｂｍ−２−（ｓ＋１），ｂｍ−２−２（ｓ＋１），．．．とは系列１のウィンドウのグループを形成する。ｓ＝２以上の場合、３番目のウィンドウｂｍ−３とｓ＋１個毎（ｓ個おき）の後続のウィンドウｂｍ−３，ｂｍ−３−（ｓ＋１），ｂｍ−３−２（ｓ＋１），．．．とは系列２のウィンドウのグループを形成する。このようにして、互いにずれて配置されるｓ＋１系列のウィンドウが形成される。いずれのウィンドウにも捕捉されなかった残りのビットのシーケンスｓｅｑｃは、補正演算において用いられる。テーブル・ルックアップの開始位置は、ｓ＋１個の系列ごとに乱数ｒ０，．．．ｒｓによって決定する。
【０２０２】
隣接するウィンドウｂｉ＋１とｂｉの重なり長ｈｉは、ｈｉ＝ｋ−｜Ｈ（ｍ−１）−ｉ  （ｍｏｄ  ｓ＋１）−Ｈ（ｍ−１）−（ｉ＋１）  （ｍｏｄ  ｓ＋１）＋ｔ｜で表される。ｃ個のｔビット値＝（ｘ１，ｘ２，．．．ｘｃ）（ｘｉ＝ｔビット値（ｉ＝１，２，．．．ｃ）、０≦ｘｉ＜２ｔ）とすると、インデックスｉｎｄ＝（ｘ１＜＜（ｃ−１）×ｔ）＋（ｘ２＜＜（ｃ−２）×ｔ）＋．．．＋ｘｃであり、値ｗ［ｉｎｄ］＝ａｘ１＜＜（（ｃ−１）×ｔ＋ｓ×ｔ×（ｃ−１））＋ｘ２＜＜（（ｃ−２）×ｔ＋ｓ×ｔ＋ｓ×ｔ×（ｃ−２）＋．．．＋ｘｃ（ｍｏｄ  ｎ）となる。ａｄ（ｍｏｄ  ｎ）は、次のように表される。
【数１１】
0004108391.tif 000014
【０２０３】
図６０は、本発明による、オーバラップ・ウィンドウｂｉの値ｄからの複数のｔビット値の間に同じｓ×ｔビット値Ｓを配置する手法を用いた指数剰余演算の概略的なフロー図を示している。この手法は、ＲＳＡ暗号処理と楕円曲線暗号処理の双方に適用できる。
【０２０４】
次に、図６０のフロー図を説明する。ステップ２３０１において、入力部７２は値ａ、ｄおよびｎを入力して、ｄをウィンドウ生成部７７に供給し、ａおよびｎまたはＡをテーブル生成部８０に供給する。ステップ２３０２において、生成部８０は、値ｗ［ｉｎｄ］＝ｗ［ｘ１＜＜（ｃ−１）×ｔ＋ｘ２＜＜（ｃ−２）×ｔ＋．．．＋ｘｃ］＝ａｘ１＜＜（（ｃ−１）×ｔ＋ｓ×ｔ×（ｃ−１））＋ｘ２＜＜（（ｃ−２）×ｔ＋ｓ×ｔ＋ｓ×ｔ×（ｃ−２）＋．．．＋ｘｃ（ｍｏｄ  ｎ）を計算してテーブルを生成する。ステップ２３０４において、生成部７７は、インデックスｉｎｄｍ−１，ｉｎｄｍ−２，．．．ｉｎｄ０を生成する。ステップ２３０６において、演算部８４は、値ｄに対応するＭＳＢの位置から順次、一連のウィンドウに対して、現在のウィンドウにおける隣接のウィンドウの前までのビット数分だけテーブルをルックアップしてウィンドウ法演算ｖ＝ｖ×ｗ［ｉｎｄｉ］（ｍｏｄ  ｎ）およびｖの２ｔ乗を順次行う。ステップ２３０８において、ｖ＝ａｄ（ｍｏｄ  ｎ）を出力する。
【０２０５】
必要なインデックスｉｎｄｉの長さは、ｋビット・ウィンドウｂｉに対してｃ×ｔ＝ｋ−（ｃ−１）×ｓ×ｔビットである。テーブルｗにおける値ｗ［ｉｎｄｉ］の数は２ｃ×ｔ＝２ｋ−（ｃ−１）×ｓ×ｔ個となる。値Ｓは、固定値、好ましくは０であるが、各値ｄごとに乱数ｒｄに従って発生してもよい。値Ｓが乱数ｒｄに従う値であるときは、値ｄのビット・シーケンスから全てのウィンドウの対応する位置に配置された値Ｓ（即ち乱数シーケンスＲ）を減算した値ｄ’を値ｄの代わりに用いる。その処理速度は、非オーバラップ・ウィンド法の従来のウィンドウ法とほぼ同程度であり、非常に高速である。
【０２０６】
図６１は、所与の値ｄに対する、各系列に対する各ウィンドウの取り得るパターンの数を示している。この手法において、乱数によってウィンドウの位置がいったん決定すれば、各ウィンドウの値は一意的に決定される。従って、所与の値ｄに対して、各ウィンドウの取り得るパターンの数は、乱数ｒｊ（０≦ｒｊ≦ｃ−１）による取り得る位置のパターンの数ｃによって決定される。各系列の全てのウィンドウに対する中間データの取り得るパターンの数はｃである。同じ系列の２巡目以降のウィンドウの位置は、１巡目で決定されたウィンドウの位置で一意的に決定される。一般的には、中間データの取り得るパターンの数はｃｓ＋１である。例えば、図６１に示された値ｄ（１１１１０．．．１１）２、ｔ＝１、ｓ＝１、ｃ＝３に対して、系列０のウィンドウの取り得る位置の数はｃ＝３であり、系列０の最初のウィンドウｂｍ−１の取り得る値は（００００１）、（００１０１）および（１０１００）であり、系列１のウィンドウの取り得る位置の数はｃ＝３であり、系列１の最初のウィンドウｂｍ−２の取り得る値は（００００１）、（００１００）および（１０００１）である。この場合、２つの系列のウィンドウに対する中間データの取り得るパターンの数はｃ２＝３２＝９である。３つの系列のウィンドウに対する中間データの取り得るパターンの数はｃ３である。  改良手法３の中間データの取り得るパターンの数は、各系列のテーブル・ルックアップ開始位置の取り得る各ウィンドウの取り得るパターンの数ｃを増大させてもテーブル・サイズは増加せず、処理速度も低下しない。従って、効率よく安全性を高めることができる。
【０２０７】
図６２は、改良手法３による本発明の第１７の実施形態による、ウィンドウ生成部７７および演算部８４において、オーバラップ・ウィンドウのインデックスｉｎｄｍ−１，ｉｎｄｍ−２，．．．ｉｎｄ０をこの順序で生成するためのフローチャートの一部を示している。図５７、５８および５９は、図６２に従ったオーバラップ・ウィンドウの生成のための演算を例示してもいる。
【０２０８】
図６０のステップ２３０２の後の図６２のステップ２４０４において、生成部７７は、乱数発生器７４に、０≦ｒｊ≦ｃ−１（ｊ＝０，１，．．．ｓ）を満たすｓ＋１個の乱数ｒｊを生成させる。
【０２０９】
ステップ２４０６において、演算部８４はｖ＝１をセットする。ステップ２４０８〜２４２８において、値ｄのｕビット・シーケンスをｔ個のＭＳＢずつ順次チェックして、生成部は７７および演算部８４は、それが或るウィンドウｂｉのｔ個のＬＳＢの位置に対応するときは値ｄから取り出されたそのウィンドウのｃ個のｔビット値を含むインデックスｉｎｄを生成して、そのインデックスを用いたテーブル・ルックアップによるｗ［ｉｎｄｉ］の乗算と累乗とを行って、ｖ＝ａｄ（ｍｏｄ  ｎ）を求める。
【０２１０】
ステップ２４０８において、演算部８４はｊ＝０をセットする。ステップ２４１０において、演算部８４はｖ＝ｖ２∧ｔ（ｍｏｄ  ｎ）を計算する。ステップ２４１２において、演算部８４はｕ＝ｕ−ｔとセットし、値ｄのｕビット・シーケンスにおける処理位置をｔ個のＭＳＢずつシフトする。それによって、後続のステップ２４１４〜２４２８において値ｄのｕビット・シーケンスがｔ個のＭＳＢずつ順次処理される。ステップ２４１４において、演算部８４はｒｊ＝０かどうかを判定する。ｒｊ＝０と判定された場合は、値ｄにおけるビットｄｕをＬＳＢとする現在のｔビット値が系列ｊのウィンドウに対するインデックスｉｎｄを生成する位置であることを示しており、手順はステップ２４１６に進む。ｒｊ＝０でないと判定された場合は、ステップ２４２０において、ｒｊ＝ｒｊ−１（ｍｏｄ  ｃ）をセットする。
【０２１１】
ステップ２４１６において、生成部７７は、ウィンドウｂｉで捕捉されるｓ×ｔビットおきの値ｄのｃ個のｔビット値を含むインデックスｉｎｄｉ＝（ｘ１＜＜（ｃ−１）×ｔ＋ｘ２＜＜（ｃ−２）×ｔ＋．．．＋ｘｃ）＝（ｄｕ＋（ｃ−１）×（ｓ＋１）×ｔ＋（ｔ−１），ｄｕ＋（ｃ−１）×（ｓ＋１）×ｔ＋（ｔ−２），．．．ｄｕ＋（ｃ−１）×（ｓ＋１）×ｔ，ｄｕ＋（ｃ−２）×（ｓ＋１）×ｔ＋（ｔ−１），．．．ｄｕ）を生成する。ステップ２４１８において、演算部８４はｖ＝ｖ×ｗ［ｉｎｄｉ］（ｍｏｄ  ｎ）を計算する。ステップ２４２０において、ｒｊ＝ｒｊ−１（ｍｏｄ  ｃ）をセットする。
【０２１２】
ステップ２４２２において、演算部８４はｕ≦ｓ＋１であるかどうかを判定する。ｕ≦ｓ＋１であると判定された場合は、ステップ２４２８において演算部８４は補正演算を行う。ｕ≦ｓ＋１ではないと判定された場合は、ステップ２４２４において、演算部８４はｊ＝ｊ＋１をセットして、次の系列に対する処理の用意をする。ステップ２４２６において、演算部８４はｊ＝ｓ＋１になったかどうかを判定する。ステップ２４２６においてｊ＝ｓ＋１と判定された場合は、ステップ２４０８においてｊ＝０とセットして系列０に戻る。ｊ＝ｓ＋１でない判定された場合は、手順はステップ２４１０に進んで、次の系列についてステップ２４１０〜２４２４を継続する。ステップ２４２８の後、手順は図６０のステップ２３０８に進む。
【０２１３】
表１は、テーブル・サイズが等しいときの各ウィンドウ法の安全性と処理速度の比較を示している。ウィンドウの長さをｋビット、ウィンドウの重なりビット長をｈビット、秘密鍵をｄ、同じ値Ｓのビットの長さをｓ、改良手法３のｄに関連するビット数をｃとする。
【０２１４】
【表３】
0004108391.tif 000015
【０２１５】
従来のウィンドウ法は、乱数を全く使用せず、所与の値ｄに対して中間データの取り得るパターンの数は１であり、従ってＤＰＡに対して弱い。一方、実施形態１〜１０のオーバラップ・ウィンドウ法では、乱数を使用して中間データのパターンの数を増加させているのでＤＰＡに対して安全である。しかし、その中間データのパターンの数は重なりビット長さｈに依存するので、長さｈを大きくするためにはウィンドウの長さｋを大きくする必要があり、それによってテーブル・サイズが増加する。
【０２１６】
改良手法１では、中間データの取り得るパターンの数は重なりビット長さｈおよび同じ値Ｓのビットの長さｓに依存している。従って、ｓを大きくすれば安全性が向上する。Ｓの幅ｓを大きくしてもテーブル・サイズは増加せず、処理速度も低下しない。従って、効率よく安全性を高めることができる。
【０２１７】
改良手法２では、中間データの取り得るパターンの数はＳの長さｓのみに依存している。ｓを大きくすれば安全性が高くなる。ｓを大きくしてもテーブル・サイズは増加せず、処理速度も低下しないので、効率よく安全性を高めることができる。第１３〜第１５の実施形態では、一般的なウィンドウ法とほぼ同等の処理速度で処理できる。第１５の実施形態では、速度が幾分低下するが、第１〜第１０の実施形態のオーバラップ・ウィンドウ法よりは高速である。
【０２１８】
改良手法３では、中間データの取り得るパターン数はｓとｃのみに依存している。従って、この値ｓとｃを大きくすれば安全性が高くなる。ｓを大きくしてもテーブル・サイズは増加せず、処理速度も低下しないので、効率よく安全性を高めることができる。
【０２１９】
以上説明した実施形態は典型例として挙げたに過ぎず、その変形およびバリエーションは当業者にとって明らかであり、当業者であれば本発明の原理および請求の範囲に記載した発明の範囲を逸脱することなく上述の実施形態の種々の変形を行えることは明らかである。
【０２２０】
（付記１）  秘密鍵を用いて公開鍵暗号処理を行う暗号装置であって、
乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成する演算手段を具える、暗号装置。
（付記２）  前記公開鍵暗号処理は指数剰余演算であり、前記別の値をａとし、ｎを正の整数としたとき、前記処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、
前記演算手段は、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々に従って、乗算と２乗算とを実行するものである、
付記１に記載の暗号装置。
（付記３）  前記公開鍵暗号処理は点のスカラー倍算であり、前記処理済みデータはベクトルＶであり、前記値ｄはスカラーであり、前記別の値はベクトルＡであり、前記処理済みデータＶはＶ＝ｄＡで与えられ、
前記演算手段は、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々に従って、加算、減算および２倍算とを実行するものである、
付記１に記載の暗号装置。
（付記４）  前記ｍ個のウィンドウ・シーケンスｂｉ’ｓの各々は０≦ｂｉ＜２ｋ（ｋは正の整数）の範囲の値を有するものである、付記１に記載の暗号装置。
（付記５）  前記ｍ個のウィンドウ・シーケンスｂｉ’ｓの各々は−２ｋ＜ｂｉ＜２ｋ（ｋは正の整数）の範囲の値を有するものである、付記１に記載の暗号装置。
（付記６）  前記一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置と前記他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、前記ｕビット・シーケンスにおけるｈ個のビット位置に関係付けられるものである、付記１に記載の暗号装置。
（付記７）  前記導出手段は、少なくとも前記ｕビット・シーケンスから前記ｈ個のＬＳＢｓまたはＭＳＢｓを導出するものである、付記６に記載の暗号装置。
（付記８）  前記ｈの値は可変であり、前記導出手段は乱数に従って前記ｈの値を生成するものである、付記６に記載の暗号装置。
（付記９）  前記導出手段は、
乱数に従ってウィンドウ・シーケンスｂｉを生成し、
中間シーケンスｗｔｉから前記ウィンドウ・シーケンスｂｉを減算することによって導出された値をＭＳＢｓとして含み、かつ前記ｕビット・シーケンスの中のｋ−ｈビットをＬＳＢｓとして含む次の中間シーケンスｗｔｉ−１を生成するものである、
付記１に記載の暗号装置。
（付記１０）  前記ウィンドウ・シーケンスｂｉがｍａｘ（０，ｗｔｉ−２ｈ＋１）≦ｂｉ≦ｗｔｉを満たす、付記９に記載の暗号装置。
（付記１１）  前記ウィンドウ・シーケンスｂｉがｗｔｉ−２ｈ＜ｂｉ＜ｍｉｎ（２ｋ，ｗｔｉ＋２ｈ）（ｋは正の整数）を満たす、付記９に記載の暗号装置。
（付記１２）  前記導出手段は、
乱数に従って生成された整数ｈ個のＭＳＢｓを含み、かつ中間シーケンスｄｔｉの（ｋ−ｈ）個のＬＳＢｓをＬＳＢｓとして含むｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を生成し、
前記中間シーケンスｄｔｉから前記ウィンドウ・シーケンスｂｉを減算しおよび（ｋ−ｈ）個のＬＳＢｓを切り捨てることによって導出される次の中間シーケンスｄｔｉ＋１を生成するものである、
付記１に記載の暗号装置。
（付記１３）  前記導出手段は、
乱数に従って生成された整数ｈ個のＭＳＢｓを含み、かつ中間シーケンスｗｔｉモジュロ２（ｋ−ｈ）の値を（ｋ−ｈ）個のＬＳＢｓとして含むｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を生成し、
前記ｈ個のＭＳＢｓの値ｗｌｉを前記中間シーケンスｗｔｉの中のｈ個のＭＳＢｓの値から減算することによって導出された値をＬＳＢｓとして含み、かつ前記ｕビット・シーケンスの中のｋ−ｈビットをＭＳＢｓとして含む次の中間シーケンスｗｔｉ＋１を生成するものである、
付記１に記載の暗号装置。
（付記１４）  前記導出手段は、
乱数に従って複数ｇ個のｕビット・シーケンスｆｉを生成し、ここで前記ｇ個のｕビット・シーケンスの値の総和は前記値ｄを表し、
前記ｇ個のｕビット・シーケンスの中のそれぞれ対応する位置にある（ｋ−ｈ）個のビットの値の総和を表すｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を、生成するものである、
付記１に記載の暗号装置。
（付記１５）  前記導出手段は、
乱数に従って複数ｇ個のｕビット・シーケンスｆｉを生成し、ここで、前記ｇ個のｕビット・シーケンスの値の総和は前記値ｄモジュロφ（φを法とするｄ）を表し、φは整数であり、
前記ｇ個のｕビット・シーケンスの中のそれぞれ対応する位置にある（ｋ−ｈ）個のビットの値の総和を表すｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を、生成するものである、
付記１に記載の暗号装置。
（付記１６）  前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものである、付記１に記載の暗号装置。
（付記１７）  情報処理装置において使用するための、秘密鍵を用いて公開鍵暗号処理を行う記憶媒体に格納されたプログラムであって
乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップを実行させるよう動作可能なプログラム。
（付記１８）  前記公開鍵暗号処理は指数剰余演算であり、前記別の値をａとし、ｎを正の整数としたとき、前記処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、
前記演算を行うステップは、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々に従って、乗算と２乗算とを実行することを含むものである、
付記１７に記載のプログラム。
（付記１９）  前記公開鍵暗号処理は点のスカラー倍算であり、前記処理済みデータはベクトルＶであり、前記値ｄはスカラーであり、前記別の値はベクトルＡであり、前記処理済みデータＶはＶ＝ｄＡで与えられ、
前記演算を行うステップは、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々に従って、加算、減算および２倍算とを実行することを含むものである、
付記１７に記載のプログラム。
（付記２０）  前記一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置と前記他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、前記ｕビット・シーケンスにおけるｈ個のビット位置に関係付けられるものであり、
前記導出するステップは、少なくとも前記ｕビット・シーケンスから前記ｈ個のＬＳＢｓまたはＭＳＢｓを導出することを含むものである、
付記１７に記載のプログラム。
（付記２１）  前記一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置と前記他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、前記ｕビット・シーケンスにおけるｈ個のビット位置に関係付けられるものであり、前記ｈの値は変数であり、
前記導出するステップは、乱数に従って前記ｈの値を生成することを含むものである、
付記１７に記載のプログラム。
（付記２２）  前記導出するステップは、
乱数に従ってウィンドウ・シーケンスｂｉを生成するステップと、
中間シーケンスｗｔｉから前記ウィンドウ・シーケンスｂｉを減算することによって導出された値をＭＳＢｓとして含み、かつ前記ｕビット・シーケンスの中のｋ−ｈビットをＬＳＢｓとして含む次の中間シーケンスｗｔｉ−１を生成するステップと、を含むものである、
付記１７に記載のプログラム。
（付記２３）  前記導出するステップは、
乱数に従って生成された整数ｈ個のＭＳＢｓを含み、かつ中間シーケンスｄｔｉの（ｋ−ｈ）個のＬＳＢｓをＬＳＢｓとして含むｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を生成するステップと、
前記中間シーケンスｄｔｉから前記ウィンドウ・シーケンスｂｉを減算し、（ｋ−ｈ）個のＬＳＢｓを切り捨てることによって導出される次の中間シーケンスｄｔｉ＋１を生成するステップと、を含むものである、
付記１７に記載のプログラム。
（付記２４）  前記導出するステップは、
乱数に従って生成された整数ｈ個のＭＳＢｓを含み、かつ中間シーケンスｗｔｉモジュロ２（ｋ−ｈ）の値を（ｋ−ｈ）個のＬＳＢｓとして含むｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を生成するステップと、
前記ｈ個のＭＳＢｓの値ｗｌｉを前記中間シーケンスｗｔｉの中のｈ個のＭＳＢｓの値から減算することによって導出された値をＬＳＢｓとして含み、かつ前記ｕビット・シーケンスの中のｋ−ｈビットをＭＳＢｓとして含む次の中間シーケンスｗｔｉ＋１を生成するステップと、を含むものである、
付記１７に記載のプログラム。
（付記２５）  前記導出するステップは、
乱数に従って複数ｇ個のｕビット・シーケンスｆｉを生成ステップと、ここで前記ｇ個のｕビット・シーケンスの値の総和は前記値ｄを表し、
前記ｇ個のｕビット・シーケンスの中のそれぞれ対応する位置にある（ｋ−ｈ）個のビットの値の総和を表すｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を、生成するステップと、を含むものである、
付記１７に記載のプログラム。
（付記２６）  前記導出するステップは、
乱数に従って複数ｇ個のｕビット・シーケンスｆｉを生成するステップと、ここで、前記ｇ個のｕビット・シーケンスの値の総和は前記値ｄのモジュロφを表し、φは整数であり、
前記ｇ個のｕビット・シーケンスの中のそれぞれ対応する位置にある（ｋ−ｈ）個のビットの値の総和を表すｋビットのウィンドウ・シーケンスｂｉ（ｋは正の整数）を、生成するステップと、を含むものである、
付記１７に記載のプログラム。
（付記２７）  前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものである、付記１７に記載のプログラム。
（付記２８）  情報処理装置において秘密鍵を用いて公開鍵暗号処理を行う方法であって、
乱数に従って、前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを含み、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数より多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップを含む、方法。
（付記２９）  前記一方のウィンドウ・シーケンスにおける整数ｈ個のＬＳＢ位置（ｈは整数）と前記他方のウィンドウ・シーケンスにおけるｈ個のＭＳＢ位置とが、前記ｕビット・シーケンスにおけるｈ個のビット位置に関係付けられるものであり、
前記導出するステップは、少なくとも前記ｕビット・シーケンスから前記ｈ個のＬＳＢｓまたはＭＳＢｓを導出することを含むものである、
付記２８に記載の方法。
（付記３０）  前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものである、付記２８に記載のプログラム。
（付記３１）  秘密鍵を用いて公開鍵暗号処理を行う暗号装置であって、
前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出する手段を具え、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成する演算手段を具える、暗号装置。
（付記３２）  さらに、前記ウィンドウ・シーケンスのビット数から前記同じ値のビット数を減算したビット数を有する取り得るシーケンスをインデックスとして有し、前記インデックスに対応付けられる前記ウィンドウ・シーケンスの取り得るシーケンスに従って計算されたエントリ値を有するルックアップ・テーブルを生成する手段を具える、付記３１に記載の暗号装置。
（付記３３）  前記演算手段は、前記導出されたウィンドウ・シーケンスの前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いて、テーブルをルックアップすることによって、前記演算を行うものである、付記３１に記載の暗号装置。
（付記３４）  前記公開鍵暗号処理は指数剰余演算であり、前記別の値をａとし、ｎを正の整数としたとき、前記処理済みデータｖはｖ＝ａｄ（ｍｏｄ  ｎ）で与えられ、
前記演算手段は、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々の前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いてテーブルをルックアップすることによって、乗算と２乗算とを実行するものである、
付記３１に記載の暗号装置。
（付記３５）  前記公開鍵暗号処理は点のスカラー倍算であり、前記処理済みデータはベクトルＶであり、前記値ｄはスカラーであり、前記別の値はベクトルＡであり、前記処理済みデータＶはＶ＝ｄＡで与えられ、
前記演算手段は、前記導出されたｍ個のウィンドウ・シーケンスｂｉ’ｓの各々の前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いてテーブルをルックアップすることによって、加算、減算および２倍算とを実行するものである、
付記３１に記載の暗号装置。
（付記３６）  前記導出されたｍ個のウィンドウ・シーケンスはそれぞれの対応する所定のＭＳＢ位置に同じ値を有するものである、付記３１に記載の暗号装置。
（付記３７）  前記導出されたｍ個のウィンドウ・シーケンスはそれぞれの対応する所定のＬＳＢ位置に同じ値を有するものである、付記３１に記載の暗号装置。
（付記３８）  前記導出されたｍ個のウィンドウ・シーケンスは、それぞれのＭＳＢおよびＬＳＢを除くそれぞれの対応する所定の中間のビット位置に同じ値を有するものである、付記３１に記載の暗号装置。
（付記３９）  前記ｍ個のウィンドウ・シーケンスの中のｓ＋１個のウィンドウ・シーケンスの各々はｃ×ｔ＋ｓ×（ｃ−１）×ｔビットのシーケンスであり（ｃ、ｓおよびｔは正の整数）、ｓ×ｔビットの間隔でｃ個の位置に前記ｕビット・シーケンスからのｔビット値を有し、各ｓ×ｔビットのストリングはｓ個のｔビットの同じ値を連結したものである、付記３１に記載の暗号装置。
（付記４０）  前記ｕビット・シーケンスに対する前記ｍ個のウィンドウ・シーケンスは複数のグループのウィンドウ・シーケンスを含み、各グループのウィンドウ・シーケンスの相対的位置が１つの乱数に従って決定され、前記ｍ個のウィンドウ・シーケンスにおけるそれぞれの対応する所定のビット位置が前記ｕビット・シーケンスの相異なるビット位置に関係付けられものである、付記３１に記載の暗号装置。
（付記４１）  前記同じ値が前記或る値ｄに関係なく固定値である、付記３１に記載の暗号装置。
（付記４２）  前記同じ値が前記或る値ｄに対して１つの乱数に従って生成されるものである、付記３１に記載の暗号装置。
（付記４３）  前記導出する手段は、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける関係付けられた所定のビット位置に配置される前記ウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ウィンドウ・シーケンスを導出するものである、付記３１に記載の暗号装置。
（付記４４）  前記導出する手段は、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける関係付けられる所定の位置に配置される前記ｍ個のウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ｍ個のウィンドウ・シーケンスを導出するものである、付記３１に記載の暗号装置。
（付記４５）  前記導出する手段は、前記ｍ個のウィンドウ・シーケンスにおける前記同じ値の前記所定のビット位置以外の位置のビットの値を乱数に従って順次生成するものである、付記３１に記載の暗号装置。
（付記４６）  前記導出する手段は、前記ｍ個のウィンドウ・シーケンスにおける前記同じ値の前記所定のビット位置以外の位置のビットの値を複数の乱数に従って一度に生成するものである、付記３１に記載の暗号装置。
（付記４７）  前記演算手段は補正演算を行うものである、付記３１に記載の暗号装置。
（付記４８）  情報処理装置において使用するための、秘密鍵を用いて公開鍵暗号処理を行う記憶媒体に格納されたプログラムであって、
前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップを実行させるよう動作可能なプログラム。
（付記４９）  さらに、前記ウィンドウ・シーケンスのビット数から前記同じ値のビット数を減算したビット数を有する取り得るシーケンスをインデックスとして有し、前記インデックスに対応付けられる前記ウィンドウ・シーケンスの取り得るシーケンスに従って計算されたエントリ値を有するルックアップ・テーブルを生成するステップを実行させるよう動作可能な付記４８に記載のプログラム。
（付記５０）  前記演算を行うステップは、前記導出されたウィンドウ・シーケンスの前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いて、テーブルをルックアップすることによって、前記演算を行うことを含むものである、付記４８に記載のプログラム。
（付記５１）  前記導出するステップは、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける対応する所定の位置に配置された前記ウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ウィンドウ・シーケンスを導出することを含むものである、付記４８に記載のプログラム。
（付記５２）  前記導出するステップは、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける対応する所定の位置に配置された前記ｍ個のウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ｍ個のウィンドウ・シーケンスを導出することを含むものである、付記４８に記載のプログラム。
（付記５３）  前記導出するステップは、前記ｍ個のウィンドウ・シーケンスにおける前記同じ値のビット以外のビットの値を乱数に従って順次生成することを含むものである、付記４８に記載のプログラム。
（付記５４）  前記導出するステップは、前記ｍ個のウィンドウ・シーケンスにおける前記同じ値のビット以外の或る同じ位置のビットの値を複数の乱数に従って一度に生成することを含むものである、付記４８に記載のプログラム。
（付記５５）  情報処理装置において秘密鍵を用いて公開鍵暗号処理を行う方法であって、
前記公開鍵暗号のための或る値ｄを表す複数ｕビット・シーケンスから複数ｍ個のウィンドウ・シーケンスを導出するステップを実行させ、
前記ｍ個のウィンドウ・シーケンスのビット総数は前記ｕビット・シーケンスのビット数ｕより多く、各ウィンドウ・シーケンスのビット数はｕより少なく、前記ｍ個のウィンドウ・シーケンスの中の２つうちの一方のウィンドウ・シーケンスにおける或るビット位置と他方のウィンドウ・シーケンスにおける或るビット位置とが、前記ｕビット・シーケンスにおける同じビット位置に関係付けられるものであり、
前記ｍ個のウィンドウ・シーケンスの中の１つのウィンドウ・シーケンスにおける所定の位置のビットは、他のウィンドウ・シーケンスの対応する所定の位置のビットと同じ値を有するものであり、
さらに、前記導出されたｍ個のウィンドウ・シーケンスと前記公開鍵暗号のための別の或る値とに従って演算を行って、処理済みデータを生成するステップを含む、方法。
（付記５６）  さらに、前記ウィンドウ・シーケンスのビット数から前記同じ値のビット数を減算したビット数を有する取り得るシーケンスをインデックスとして有し、前記インデックスに対応付けられる前記ウィンドウ・シーケンスの取り得るシーケンスに従って計算されたエントリ値を有するルックアップ・テーブルを生成するステップを含む、付記５５に記載の方法。
（付記５７）  前記演算を行うステップは、前記導出されたウィンドウ・シーケンスの前記同じ値の所定のビット以外のビットのシーケンスをインデックスとして用いて、テーブルをルックアップすることによって、前記演算を行うことを含むものである、付記５５に記載の方法。
（付記５８）  前記導出するステップは、前記ｕビット・シーケンスから、前記ｕビット・シーケンスにおける対応する所定の位置に配置された前記ウィンドウ・シーケンスの前記同じ値を減算して別のシーケンスを生成し、前記別のシーケンスから前記ウィンドウ・シーケンスを導出するステップを含むものである、付記５５に記載の方法。
（付記５９）  前記導出するステップは、前記ｍ個のウィンドウ・シーケンスにおける前記同じ値のビット以外のビットの値を乱数に従って順次生成することを含むものである、付記５５に記載の方法。
【０２２１】
【発明の効果】
本発明は、上述の特徴によって、秘密鍵の推定を困難にし、暗号処理の安全性を高めることができ、効率的な耐タンパ性の指数剰余演算および点のスカラー倍算を実現できる、という効果を奏する。
【図面の簡単な説明】
【図１】図１は、暗号デバイスにおける秘密鍵を用いた暗号処理を例示している。
【図２】図２は、ウィンドウ法を用いてｖ＝ａｄ（ｍｏｄ  ｎ）を求める指数剰余演算のアルゴリズムを示している。
【図３】図３は、ウィンドウ法を用いた点のスカラー倍算Ｖ＝ｄＡのアルゴリズムを示している。
【図４】図４は、図２のアルゴリズムによる演算の手順を説明するのに役立つ。
【図５】図５Ａは時間に対する消費電力の曲線を示している。図５Ｂは、スパイクを有する、時間に対する電力差分の曲線を示している。図５Ｃは、時間に対する電力差分の平坦な曲線を示している。
【図６】図６は、分割指数法を用いたｖ＝ａｄ（ｍｏｄ  ｎ）を求めるためのアルゴリズムを示している。
【図７】図７は、本発明による暗号処理装置の概略的構成を示している。
【図８】図８は、本発明によるオーバラップ・ウィンドウの生成の仕方を示している。
【図９】図９は、本発明による、乱数に従ったオーバラップ・ウィンドウにおける重なりビットの値の決定の仕方を示している。
【図１０】図１０は、本発明による、隣接するウィンドウに固定された重なりビット長を有するオーバラップ・ウィンドウ法を用いた指数剰余演算のフロー図を示している。
【図１１】図１１は、本発明による、隣接するウィンドウに可変な重なりビット長を有するオーバラップ・ウィンドウ法を用いた指数剰余演算のフロー図を示している。
【図１２】図１２は、本発明による、隣接するウィンドウに固定された重なりビット長を有するオーバラップ・ウィンドウ法を用いたスカラー倍算のフロー図を示している。
【図１３】図１３は、本発明による、隣接するウィンドウに可変な重なりビット長を有するオーバラップ・ウィンドウ法を用いたスカラー倍算のフロー図を示している。
【図１４】図１４は、本発明の第１の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを重み（上位から下位）の順に生成するためのフローチャートを示している。
【図１５】図１５は、図１４に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図１６】図１６は、本発明の第２の実施形態による、可変な重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートを示している。
【図１７】図１７は、図１６に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図１８】図１８は、本発明の第３の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートを示している。
【図１９】図１９は、図１８に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図２０】図２０は、本発明の第４の実施形態による、可変な重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートを示している。
【図２１】図２１は、図２０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図２２】図２２は、本発明の第５の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートを示している。
【図２３】図２３は、図２２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図２４】図２４は、本発明の第６の実施形態による、可変な重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートを示している。
【図２５】図２５は、図２４に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図２６】図２６は、本発明の第７の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートを示している。
【図２７】図２６は、図２５に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図２８】図２８は、本発明の第８の実施形態による、可変な重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートを示している。
【図２９】図２９は、図２８に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図３０】図３０は、本発明の第９の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを順に生成するためのフローチャートを示している。
【図３１】図３１は、図３０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図３２】図３２は、本発明の第１０の実施形態による、重なりビット長を有するオーバラップ・ウィンドウを順に生成するためのフローチャートを示している。
【図３３】図３３は、図３２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図３４】図３４Ａおよび３４Ｂは、本発明による、複数のウィンドウのそれぞれの一部について所定の同じ値または乱数に従って生成された同じ値を用いるオーバラップ・ウィンドウ法の原理を説明するのに役立つ。
【図３５】図３５は、改良手法１および２において用いられる、複数のウィンドウのそれぞれの一部に同じ値を用いるオーバラップ・ウィンドウ法による暗号処理装置の概略的構成を示している。
【図３６】図３６は、改良手法１および２において用いられる、複数のウィンドウのそれぞれの一部に同じ値を用いるオーバラップ・ウィンドウ法による逐次または反復処理型の暗号処理装置の概略的構成を示している。
【図３７】図３７は、本発明による、オーバラップ・ウィンドウの中央位置に同じ値を設定する手法を説明するのに役立つ。
【図３８】図３８は、本発明による、オーバラップ・ウィンドウの中央位置に同じ値を用いる手法を用いた指数剰余演算の概略的なフロー図を示している。
【図３９】図３９は、改良手法１による最初の３つのウィンドウの生成の例を示している。
【図４０】図４０は、改良手法１による本発明の第１１の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートの一部を示している。
【図４１】図４１は、図４０に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図４２】図４２は、改良手法１による本発明の第１２の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートの一部を示している。
【図４３】図４３は、図４２に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図４４】図４４は、本発明による、オーバラップ・ウィンドウのＬＳＢまたはＭＳＢとして同じ値を用いる手法を説明するのに役立つ。
【図４５】図４５は、本発明による、オーバラップ・ウィンドウのＬＳＢまたはＭＳＢのストリングに同じ値を用いる手法を用いた指数剰余演算の概略的なフロー図を示している。
【図４６】図４６は、改良手法２による最初の３つのウィンドウの生成を示している。
【図４７】図４７は、改良手法２による本発明の第１３の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートの一部を示している。
【図４８】図４８は、図４７に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図４９】図４９は、改良手法２による本発明の第１４の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートの一部を示している。
【図５０】図５０は、図４９に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図５１】図５１は、改良手法２による本発明の第１５の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの逆の順に生成するためのフローチャートの一部を示している。
【図５２】図５２は、図５１に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図５３】図５３は、改良手法２による本発明の第１６の実施形態による、ウィンドウ生成部において、重なりビット長を有するオーバラップ・ウィンドウを重みの順に生成するためのフローチャートの一部を示している。
【図５４】図５４は、図５３に従ったオーバラップ・ウィンドウの生成のための演算を例示している。
【図５５】図５５は、改良手法３において用いられる、複数のウィンドウのそれぞれの複数の部分に同じ値を用いるオーバラップ・ウィンドウ法による暗号処理装置の概略的構成を示している。
【図５６】図５６は、改良手法３において用いられる、複数のウィンドウのそれぞれの複数の部分に同じ値を用いるオーバラップ・ウィンドウ法による逐次または反復処理型の暗号処理装置の概略的構成を示している。
【図５７】図５７、５８および５９は、本発明による、オーバラップ・ウィンドウにおいて複数の位置の値の間に同じ値を配置する手法を説明するのに役立つ。
【図５８】図５７、５８および５９は、本発明による、オーバラップ・ウィンドウにおいて複数の位置の値の間に同じ値を配置する手法を説明するのに役立つ。
【図５９】図５７、５８および５９は、本発明による、オーバラップ・ウィンドウにおいて複数の位置の値の間に同じ値を配置する手法を説明するのに役立つ。
【図６０】図６０は、本発明による、オーバラップ・ウィンドウの値ｄからの複数の値の間に同じ値を配置する手法を用いた指数剰余演算の概略的なフロー図を示している。
【図６１】図６１は、各系列に対する各ウィンドウの取り得るパターンの数を示している。
【図６２】図６２は、改良手法３による本発明の第１７の実施形態による、ウィンドウ生成部および演算部において、オーバラップ・ウィンドウのインデックスを重みの順に生成するためのフローチャートの一部を示している。
【符号の説明】
６０  暗号処理装置
７２  入力部
７４  乱数発生器
７５  ウィンドウおよび重なり長生成部
７８  メモリ
８０  テーブル生成部
８２  テーブル・メモリ
８４  ウィンドウ法演算部
８６  出力部
【図１】
0004108391.tif 000016
【図２】
0004108391.tif 000017
【図３】
0004108391.tif 000018
【図４】
0004108391.tif 000019
【図５】
0004108391.tif 000020
【図６】
0004108391.tif 000021
【図７】
0004108391.tif 000022
【図８】
0004108391.tif 000023
【図９】
0004108391.tif 000024
【図１０】
0004108391.tif 000025
【図１１】
0004108391.tif 000026
【図１２】
0004108391.tif 000027
【図１３】
0004108391.tif 000028
【図１４】
0004108391.tif 000029
【図１５】
0004108391.tif 000030
【図１６】
0004108391.tif 000031
【図１７】
0004108391.tif 000032
【図１８】
0004108391.tif 000033
【図１９】
0004108391.tif 000034
【図２０】
0004108391.tif 000035
【図２１】
0004108391.tif 000036
【図２２】
0004108391.tif 000037
【図２３】
0004108391.tif 000038
【図２４】
0004108391.tif 000039
【図２５】
0004108391.tif 000040
【図２６】
0004108391.tif 000041
【図２７】
0004108391.tif 000042
【図２８】
0004108391.tif 000043
【図２９】
0004108391.tif 000044
【図３０】
0004108391.tif 000045
【図３１】
0004108391.tif 000046
【図３２】
0004108391.tif 000047
【図３３】
0004108391.tif 000048
【図３４】
0004108391.tif 000049
【図３５】
0004108391.tif 000050
【図３６】
0004108391.tif 000051
【図３７】
0004108391.tif 000052
【図３８】
0004108391.tif 000053
【図３９】
0004108391.tif 000054
【図４０】
0004108391.tif 000055
【図４１】
0004108391.tif 000056
【図４２】
0004108391.tif 000057
【図４３】
0004108391.tif 000058
【図４４】
0004108391.tif 000059
【図４５】
0004108391.tif 000060
【図４６】
0004108391.tif 000061
【図４７】
0004108391.tif 000062
【図４８】
0004108391.tif 000063
【図４９】
0004108391.tif 000064
【図５０】
0004108391.tif 000065
【図５１】
0004108391.tif 000066
【図５２】
0004108391.tif 000067
【図５３】
0004108391.tif 000068
【図５４】
0004108391.tif 000069
【図５５】
0004108391.tif 000070
【図５６】
0004108391.tif 000071
【図５７】
0004108391.tif 000072
【図５８】
0004108391.tif 000073
【図５９】
0004108391.tif 000074
【図６０】
0004108391.tif 000075
【図６１】
0004108391.tif 000076
【図６２】
0004108391.tif 000077