(57)【要約】【課題】冪乗計算を実行する必要のないＲＳＡ暗号等の公開鍵暗号の依頼計算の事前計算方法を提供し、多くのクライアント装置をＰＫＩトークンとして実用に耐えられるようにする。【解決手段】ＲＳＡ暗号の依頼計算の事前計算方法を実行するクライアント装置１は、中央演算処理装置兼主記憶装置２と、記憶装置３とから構成される。記憶装置３には、従来技術の場合と同様な情報と共に、本発明により、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］が記憶される。クライアント装置１は、ステップ１０４、１０５の処理を繰り返すことにより、冪乗演算を行わず単に冪乗情報の乗算処理を行うだけで、事前計算情報ｆｐ，ｓｐを算出することができる。その後の依頼計算は、従来技術と同様にサーバ装置に行わせればよい。【選択図】      図１
2006078751.tif 000002
【特許請求の範囲】
【請求項１】
サーバ装置に公開鍵暗号の依頼計算を行わせるためにクライアント装置が事前計算を行う公開鍵暗号の依頼計算の事前計算方法において、前記クライアント装置内の記憶装置に事前計算情報の組と同様な関係が成立する冪乗情報を記憶しておき、前記クライアント装置がランダムに選んだ冪乗情報を乗算することにより事前計算情報を計算することを特徴とする公開鍵暗号の依頼計算の事前計算方法。
【請求項２】
前記公開鍵暗号がＲＳＡ暗号であることを特徴とする請求項１記載の公開鍵暗号の依頼計算の事前計算方法。
【請求項３】
前記公開鍵暗号が楕円曲線暗号であることを特徴とする請求項１記載の公開鍵暗号の依頼計算の事前計算方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、公開鍵暗号の依頼計算の事前計算方法に係り、暗号技術のうち公開鍵暗号の復号時や署名時に実行される冪乗計算の依頼計算の事前計算方法に関する。
【背景技術】
【０００２】
公開鍵暗号の依頼計算方法は、秘密鍵を記憶しているクライアント装置が、秘密鍵を記憶していないサーバ装置に対して、秘密鍵の保護を図りながら冪乗計算の処理を依頼する処理時間短縮を目的として実行する分散計算方法である。すなわち、依頼計算は、クライアント装置からサーバ装置に秘密鍵が漏洩することなく、クライアント装置で実行すべき冪乗計算の処理の一部をサーバ装置に実行させるものである。公開鍵暗号の依頼計算の事前計算方法は、復号したい暗号文または署名したいメッセージが入力される前、すなわち、公開鍵暗号の依頼計算を実行する前に、クライアント装置で実行する計算方法である。
【０００３】
公開鍵暗号の依頼計算方法に関する従来技術として、例えば、非特許文献１に記載された技術が知られている。この従来技術は、ＲＳＡ暗号の依頼計算方法に関するもので、ＲＳＡ暗号のＲＳＡ鍵情報と剰余群とを、楕円曲線暗号等の群を利用する公開鍵暗号の鍵情報と群とに変更することにより、公開鍵暗号の依頼計算方法に応用することができる。
【０００４】
図３は従来技術によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図であり、図３を参照して、従来技術による依頼計算の事前計算方法を説明する。図３において、１はクライアント装置、２は中央演算処理装置兼主記憶装置、３は記憶装置である。
【０００５】
ＲＳＡ暗号の依頼計算の事前計算方法を実行するクライアント装置１は、中央演算処理装置兼主記憶装置２と、記憶装置と３から構成される。
【０００６】
記憶装置３には、ＲＳＡ公開鍵情報ｅ，ｎと、ＲＳＡ秘密鍵情報ｄと、ＲＳＡ秘密鍵二分割情報ｆｄ，ｓｄと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，βとが記憶されている。
【０００７】
但し、φ（ｎ）はＲＳＡ公開鍵情報ｎのオイラー関数値，Ｄ［１］〜Ｄ［α］は１以上φ（ｎ）−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、ｄ＝ｆｄ×ｓｄ ｍｏｄφ（ｎ），ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄφ（ｎ），ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄφ（ｎ）が成り立つものとする。
【０００８】
次に、従来技術によるＲＳＡ暗号の依頼計算の事前計算方法の動作について、図３の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。この処理は、ＲＳＡ暗号の依頼計算方法を実行する前に、毎回実行する必要のある処理である。
【０００９】
（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、ＲＳＡ秘密鍵二分割情報ｓｄを読み込む（ステップ３０１）。
【００１０】
（２）次に、事前計算情報ｆｐに１以上ｎ−１以下のランダムな整数値を代入する（ステップ３０２）。
【００１１】
（３）次に、事前計算情報ｓｐにｆｐ＾（−ｓｄ）ｍｏｄ ｎ を代入する。但し、ｆｐ＾（−ｓｄ）は、ｆｐの（−ｓｄ）乗の値である（ステップ３０３）。
【００１２】
（４）記憶装置３に、ステップ３０２、３０３の処理で得られた事前計算情報ｆｐ，ｓｐを書き込む（ステップ３０４）。
【００１３】
以上がクライアント装置１で実行される事前計算であり、クライアント装置１は、この事前計算を行った後に、サーバ装置に対して計算の依頼を行う。
【００１４】
図４は従来技術によるＲＳＡ暗号の依頼計算方法について説明する図であり、次に、図４を参照して、従来技術による依頼計算方法を説明する。図４において、２’は中央演算処理装置兼主記憶装置、４はサーバ装置であり、他の符号は、図３の場合と同一である。
【００１５】
従来技術による依頼計算は、クライアント装置１とサーバ装置４とが接続されて実行され、ＲＳＡ暗号の依頼計算方法を実行するクライアント装置１は、中央演算処理装置兼主記憶装置２と記憶装置３から構成され、サーバ装置４は、中央演算処理装置兼主記憶装置２’から構成される。記憶装置３には、図３で説明したＲＳＡ暗号の依頼計算の事前計算方法を実行した後の情報が記憶されている。
【００１６】
なお、後述において、ｘは復号したい暗号文情報または署名したいメッセージ情報であり、ｚは復号結果情報または署名結果情報である。
【００１７】
（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータαと、事前計算情報ｆｐ，ｓｐとを読み込む（ステップ４０１）。
【００１８】
（２）次に、クライアント装置１は、サーバ装置４に、ｘ，ｎ，Ｄ［１］〜Ｄ［α］を送信する（ステップ４０２）。
【００１９】
（３）サーバ装置４は、１≦ｉ≦αについて、第一基底情報ＦＢ［ｉ］にｘ＾Ｄ［ｉ］ｍｏｄ ｎ を代入して、第一基底情報ＦＢ［１］〜ＦＢ［α］を算出する（ステップ４０３）。
【００２０】
（４）その後、サーバ装置４は、クライアント装置１にステップ４０３で算出した第一基底情報ＦＢ［１］〜ＦＢ［α］を送信する（ステップ４０４）。
【００２１】
（５）クライアント装置１は、第一基底情報ＦＢ［１］〜ＦＢ［α］を受け取ると、中間結果情報ｙにｆｐ×Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）ｍｏｄ ｎ を代入して、中間結果情報ｙを算出する（ステップ４０５）。
【００２２】
（６）クライアント装置１は、サーバ装置４にステップ４０５で算出した中間結果情報ｙを送信する（ステップ４０６）。
【００２３】
（７）サーバ装置４は、１≦ｉ≦αについて、第二基底情報ＳＢ［ｉ］にｙ＾Ｄ［ｉ］ｍｏｄ ｎを代入して、第二基底情報ＳＢ［１］〜ＳＢ［α］を算出する（ステップ４０７）。
【００２４】
（８）サーバ装置４は、クライアント装置１にステップ４０７で算出した第二基底情報ＳＢ［１］〜ＳＢ［α］を送信する（ステップ４０８）。
【００２５】
（９）クライアント装置１は、サーバ装置４から第二基底情報ＳＢ［１］〜ＳＢ［α］を受け取ると、ｚにｓｐ×Π（１≦ｉ≦α）（ＳＢ［ｉ］＾ＳＥ［ｉ］）ｍｏｄ ｎ を代入する（ステップ４０９）。
【００２６】
前述したような従来技術によるＲＳＡ暗号の依頼計算方法により、ＲＳＡ暗号の復号時や署名時に実行される冪乗計算を正しく実行することができ、このことは、次のように確認することができる。
【００２７】
ｚ＝ｓｐ×Π（１≦ｉ≦α）（ＳＢ［ｉ］＾ＳＥ［ｉ］）ｍｏｄ ｎ
＝ｓｐ×Π（１≦ｉ≦α）（ｙ＾Ｄ［ｉ］＾ＳＥ［ｉ］）ｍｏｄ ｎ
＝ｓｐ×ｙ＾｛Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）｝ｍｏｄ ｎ
＝ｓｐ×ｙ＾ｓｄ ｍｏｄ ｎ
＝ｓｐ×｛ｆｐ×Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄ ｍｏｄ ｎ
＝ｓｐ×ｆｐ＾ｓｄ×｛Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄ ｍ       ｏｄ ｎ
＝｛Π（１≦ｉ≦α）（ＦＢ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄ ｍｏｄ ｎ
＝｛Π（１≦ｉ≦α）（ｘ＾Ｄ［ｉ］＾ＦＥ［ｉ］）｝＾ｓｄ ｍｏｄ ｎ
＝ｘ＾｛Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）｝＾ｓｄ ｍｏｄ ｎ
＝ｘ＾ｆｄ＾ｓｄ ｍｏｄ ｎ
＝ｘ＾（ｆｄ×ｓｄ）ｍｏｄ ｎ
＝ｘ＾ｄ ｍｏｄ ｎ
前述したような従来技術により、ＲＳＡ暗号の依頼計算を行った場合にも、クライアント装置からサーバ装置にＲＳＡ秘密鍵情報ｄが漏洩することはない。なぜなら、セキュリティパラメータα，βの値を大きくすれば、第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］との組み合わせの数は膨大になり、サーバ装置が第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］とを取得できないからである。例えば、セキュリティパラメータαの値を１６，βの値を１６とすると、第一指数情報ＦＥ［１］〜ＦＥ［α］と第二指数情報ＳＥ［１］〜ＳＥ［α］との組み合わせの数は２＾１２８となる。
【００２８】
そして、依頼計算を行わない場合のクライアント装置の処理量は、指数部ビット長がＲＳＡ秘密鍵情報ｄのビット長の冪乗計算１回である。一方、依頼計算方を行う場合のクライアント装置の処理量は、指数部ビット長がセキュリティパラメータβのビット長の冪乗計算２α回である。指数部のビット長がＬの冪乗計算１回の処理量は、乗算１．５Ｌ回の処理量とほぼ等しい。例えば、ＲＳＡ秘密鍵情報ｄのビット長を１０２４、セキュリティパラメータβのビット長を４、セキュリティパラメータαのビット長を１６とすると、依頼計算を行わない場合のクライアント装置の処理量は、乗算１５３６回の処理量となり、依頼計算を行う場合のクライアント装置の処理量は、乗算１９２回の処理量となる。従って、前述した従来技術によるＲＳＡ暗号の依頼計算方法により、クライアント装置の処理量を大幅に削減することができる。
【非特許文献１】「情報理論とその応用シリーズ４  暗号と認証」、株式会社  培風館、１９９６年、ｐ．１１４−１１５
【発明の開示】
【発明が解決しようとする課題】
【００２９】
前述した従来技術によるＲＳＡ暗号の依頼計算の事前計算方法は、図３により説明したステップ３０３の処理で、指数部ビット長がＲＳＡ秘密鍵二分割情報ｓｄのビット長の冪乗計算を１回を実行する必要がある。ＲＳＡ秘密鍵二分割情報ｓｄのビット長は、ＲＳＡ秘密鍵情報ｄのビット長と等しいため、従来技術によるＲＳＡ暗号の依頼計算の事前計算の処理量は、依頼計算方法なしの場合のクライアント装置の処理量と等しくなる。また、この事前計算の結果は、サーバ装置に送信して依頼計算のために使用されるが、サーバ装置に毎回同一のデータを送信すると安全性を損なう可能性があるので、事前計算は、ＲＳＡ暗号の依頼計算を実行する前に、毎回実行する必要がある。
【００３０】
そのため、前述した従来技術によるＲＳＡ暗号の依頼計算の事前計算方法は、その処理量を削減しないと、クライアント装置によってはＰＫＩトークンとして実用に耐えられないという問題点を生じさせてしまう。このことは、クライアント装置が携帯電話機等の携帯可能な機器のような処理能力の小さい機器である場合に特に大きな問題となる。
【００３１】
本発明の目的は、前述したような従来技術の問題点を解決し、冪乗計算を実行する必要のないＲＳＡ暗号、楕円曲線暗号等の公開鍵暗号の依頼計算の事前計算方法を提供することにある。
【課題を解決するための手段】
【００３２】
本発明によれば前記目的は、サーバ装置に公開鍵暗号の依頼計算を行わせるためにクライアント装置が事前計算を行う公開鍵暗号の依頼計算の事前計算方法において、前記クライアント装置内の記憶装置に事前計算情報の組と同様な関係が成立する冪乗情報を記憶しておき、前記クライアント装置がランダムに選んだ冪乗情報を乗算することにより事前計算情報を計算することにより達成される。
【００３３】
公開鍵暗号がＲＳＡ暗号である場合について具体的にいえば、前記目的は、サーバ装置が、底部分が復号したい暗号文情報または署名したいメッセージ情報であり指数部分がＲＳＡ秘密鍵多分割情報である冪乗計算を実行することにより第一基底情報を計算し、クライアント装置が、底部分が第一基底情報であり指数部分が第一指数情報である冪乗計算を実行し、さらに、事前計算情報を掛け合わせることにより中間結果情報を計算し、サーバ装置が、底部分が中間結果情報であり指数部分がＲＳＡ秘密鍵多分割情報である冪乗計算を実行することにより第二基底情報を計算し、クライアント装置が、底部分が第二基底情報であり指数部分が第二指数情報である冪乗計算を実行し、さらに、事前計算情報を掛けあわせることにより復号結果情報または署名結果情報を計算するＲＳＡ暗号の依頼計算方法に対して、クライアント装置内の記憶装置に、冪乗情報の組が事前計算情報の組と同様な関係が成立する冪乗情報を記憶し、クライアント装置が、ランダムに選んだ冪乗情報を乗算することで事前計算情報を計算することにより達成される。
【発明の効果】
【００３４】
本発明によれば、公開鍵暗号の依頼計算の事前計算において、冪乗計算を実行する必要がなくなるので、依頼計算の事前計算を行うクライアント装置の処理量を削減することができると共に、安全性を維持することができる。これにより、携帯電話のような処理能力の小さい機器を含め、より多くのクライアント装置をＰＫＩトークンとして実用に耐えられるようにすることができる。
【発明を実施するための最良の形態】
【００３５】
以下、本発明による公開鍵暗号の依頼計算の事前計算方法の実施形態を図面により詳細に説明する。
【００３６】
図１は本発明の一実施形態によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図であり、図１を参照して、本発明の実施形態による依頼計算の事前計算方法を説明する。図１における符号は、図３の場合と同様である。
【００３７】
ＲＳＡ暗号の依頼計算の事前計算方法を実行するクライアント装置１は、従来技術の場合と同様に、中央演算処理装置兼主記憶装置２と、記憶装置３とから構成される。図３には、本発明の説明に必要な構成だけを示しているが、クライアント装置１は、よく知られているように、ＣＰＵ、ハードディスク装置、主記憶装置、ディスプレイ、キーボード、マウス、通信制御部等を備えて構成される携帯電話機、ＰＤＡ、ＰＣ、ワークステーション等の情報処理装置であってよい。
【００３８】
そして、記憶装置３には、ＲＳＡ公開鍵情報ｅ，ｎと、ＲＳＡ秘密鍵情報ｄと、ＲＳＡ秘密鍵二分割情報ｆｄ，ｓｄと、ＲＳＡ秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，β，γ，δと、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］が記憶されている。なお、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］は、本発明のために予め算出されている情報である。
【００３９】
但し、φ（ｎ）はＲＳＡ公開鍵情報ｎのオイラー関数値，Ｄ［１］〜Ｄ［α］は１以上φ（ｎ）−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、ｄ＝ｆｄ×ｓｄ ｍｏｄφ（ｎ） ，ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄφ（ｎ），ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄφ（ｎ），１≦ｉ≦γについてＳＰ［ｉ］＝ＦＰ［ｉ］＾（−ｓｄ）ｍｏｄ ｎ が成り立つものとする。
【００４０】
次に、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法の動作について、図１の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。
【００４１】
（１）クライアント装置１の処理装置は、まず、記憶装置３からＲＳＡ公開鍵情報ｎと、セキュリティパラメータγ，δと、冪乗情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とを読み込む（ステップ１０１）。
【００４２】
（２）次に、事前計算情報ｆｐに１を代入すると共に、事前計算情報ｓｐにも１を代入する（ステップ１０２）。
【００４３】
（３）ｉに１を代入して、ステップ１０４、１０５の処理を繰り返すことを設定する（ステップ１０３）。
【００４４】
（４）次に、Ｒ［ｉ］に１以上γ以下のランダムな整数を代入する（ステップ１０４）。
【００４５】
（５）事前計算情報ｆｐにｆｐ×ＦＰ［Ｒ［ｉ］］ｍｏｄ ｎを代入し、事前計算情報ｓｐにｓｐ×ＳＰ［Ｒ［ｉ］］ｍｏｄ ｎを代入する（ステップ１０５）。
【００４６】
（６）ｉにｉ＋１を代入して、ｉ≦δであるか否かを判定し、ｉ≦δである間、ステップ１０４からの処理に戻って処理を繰り返す（ステップ１０６）。
【００４７】
（７）前述までの処理で算出された事前計算情報ｆｐ，ｓｐを記憶装置３に書き込んで、ここでの処理を終了する（ステップ１０７）。
【００４８】
前述した事前計算の後の依頼計算は、図４により説明した従来技術の場合と同様に、サーバ装置に計算させることができる。
【００４９】
次に、前述した本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法により計算される事前計算情報ｆｐ，ｓｐが、従来技術によるＲＳＡ暗号の依頼計算の事前計算方法により計算される事前計算情報ｆｐ，ｓｐと同様なものとなることについて説明する。  ｓｐ＝Π（１≦ｉ≦δ）（ＳＰ［Ｒ［ｉ］］）ｍｏｄ ｎ
＝Π（１≦ｉ≦δ）（ＦＰ［Ｒ［ｉ］］＾（−ｓｄ））ｍｏｄ ｎ
＝｛Π（１≦ｉ≦δ）ＦＰ［Ｒ［ｉ］］｝＾（−ｓｄ）ｍｏｄ ｎ
＝ｆｐ＾（−ｓｄ）ｍｏｄ ｎ
前述した本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算２δ回である。従来技術によるＲＳＡ暗号の依頼計算の事前計算の処理量は、指数部ビット長がＲＳＡ秘密鍵二分割情報ｓｄのビット長の冪乗計算１回である。例えば、セキュリティパラメータδを２０、ＲＳＡ秘密鍵二分割情報ｓｄのビット長を１０２４とすると、本発明の実施形態でのＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算４０回の処理量であり、従来技術でのＲＳＡ暗号の依頼計算の事前計算の処理量は、乗算１５３６回の処理量である。このように、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法は、クライアント装置の処理量を削減することができる。
【００５０】
また、本発明の実施形態によるＲＳＡ暗号の依頼計算の事前計算方法を用いても、クライアント装置からサーバ装置にＲＳＡ秘密鍵情報ｄが漏洩することはない。なぜなら、セキュリティパラメータγ，δを大きくすれば、事前計算情報ｆｐ，ｓｐの組み合わせの数は膨大になり、サーバ装置が事前計算情報ｆｐ，ｓｐを取得することができないからである。例えば、セキュリティパラメータγを３２，δを２０とすると、事前計算情報ｆｐ，ｓｐの組み合わせの数は２＾１００という大きなものとなる。
【００５１】
前述したように、本発明の実施形態により、安全性を維持しつつ公開鍵暗号の依頼計算の事前計算の処理量を削減することができ、より多くのクライアント装置をＰＫＩトークンとして実用に耐えられるようにすることができる。
【００５２】
前述した本発明の実施形態は、ＲＳＡ暗号のＲＳＡ鍵情報と剰余群とを、楕円曲線暗号等の群を利用する公開鍵暗号の鍵情報と群とに変更することにより、公開鍵暗号の依頼計算の事前計算方法に応用することができ、次に、これについて説明する。
【００５３】
図２は本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法について説明する図であり、図２を参照して、本発明の他の実施形態による依頼計算の事前計算方法を説明する。図２における符号は、図３の場合と同様であり、また、楕円曲線暗号の依頼計算の事前計算方法を実行するクライアント装置１は、図１の場合と同様に、中央演算処理装置兼主記憶装置２と、記憶装置３とから構成される。
【００５４】
記憶装置３には、楕円曲線公開鍵情報Ｅ，Ｇ［１］〜Ｇ［２］と、楕円曲線秘密鍵情報ｄと、楕円曲線秘密鍵二分割情報ｆｄ，ｓｄと、楕円曲線秘密鍵多分割情報Ｄ［１］〜Ｄ［α］と、第一指数情報ＦＥ［１］〜ＦＥ［α］と、第二指数情報ＳＥ［１］〜ＳＥ［α］と、セキュリティパラメータα，β，γ，δと、スカラー倍情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とが記憶されている。
【００５５】
但し、Ｅは楕円曲線，Ｈは楕円曲線上の巡回群，｜Ｈ｜は楕円曲線上の巡回群の位数，Ｇ［１］〜Ｇ［２］及びＦＰ［１］〜ＦＰ［γ］及びＳＰ［１］〜ＳＰ［γ］は楕円曲線上の点，ｄ及びｆｄ及びｓｄ及びＤ［１］〜Ｄ［α］は１以上｜Ｈ｜−１以下の整数値，ＦＥ［１］〜ＦＥ［α］及びＳＥ［１］〜ＳＥ［α］は０以上β−１以下の整数値であり、楕円曲線Ｅ上の演算でＧ［２］＝ｄ×Ｇ［１］，ｄ＝ｆｄ×ｓｄ ｍｏｄ｜Ｈ｜，ｆｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＦＥ［ｉ］）ｍｏｄ｜Ｈ｜，ｓｄ＝Σ（１≦ｉ≦α）（Ｄ［ｉ］×ＳＥ［ｉ］）ｍｏｄ｜Ｈ｜，１≦ｉ≦γについて楕円曲線Ｅ上の演算でＳＰ［ｉ］＝ＦＰ［ｉ］×（−ｓｄ）が成り立つものとする。
【００５６】
次に、本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法の動作について、図２の中央演算処理装置兼主記憶装置２の内部に示したフローを参照して説明する。
【００５７】
（１）クライアント装置１の処理装置は、まず、記憶装置３から楕円曲線公開鍵情報Ｅと、セキュリティパラメータγ，δと、スカラー倍情報ＦＰ［１］〜ＦＰ［γ］，ＳＰ［１］〜ＳＰ［γ］とを読み込む（ステップ２０１）。
【００５８】
（２）次に、事前計算情報ｆｐに無限遠点を代入すると共に、事前計算情報ｓｐにも無限遠点を代入する（ステップ２０２）。
【００５９】
（３）ｉに１を代入して、ステップ２０４、２０５の処理を繰り返すことを設定する（ステップ２０３）。
【００６０】
（４）次に、Ｒ［ｉ］に１以上γ以下のランダムな整数を代入する（ステップ２０４）。
【００６１】
（５）事前計算情報ｆｐに楕円曲線Ｅ上の演算でｆｐ＋ＦＰ［Ｒ［ｉ］］を代入し、事前計算情報ｓｐに楕円曲線Ｅ上の演算でｓｐ＋ＳＰ［Ｒ［ｉ］］を代入する（ステップ２０５）。
【００６２】
（６）ｉにｉ＋１を代入して、ｉ≦δであるか否かを判定し、ｉ≦δである間、ステップ２０４からの処理に戻って処理を繰り返す（ステップ２０６）。
【００６３】
（７）前述までの処理で算出された事前計算情報ｆｐ，ｓｐを記憶装置３に書き込んで、ここでの処理を終了する（ステップ２０７）。
【図面の簡単な説明】
【００６４】
【図１】本発明の一実施形態によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図である。
【図２】本発明の他の実施形態による楕円曲線暗号の依頼計算の事前計算方法について説明する図である。
【図３】従来技術によるＲＳＡ暗号の依頼計算の事前計算方法について説明する図である。
【図４】従来技術によるＲＳＡ暗号の依頼計算方法について説明する図である。
【符号の説明】
【００６５】
１  クライアント装置
２、２’  中央演算処理装置兼主記憶装置
３  記憶装置
４  サーバ装置
【図１】
2006078751.tif 000003
【図２】
2006078751.tif 000004
【図３】
2006078751.tif 000005
【図４】
2006078751.tif 000006