JP2000511649A - 公開鍵暗号方法 - Google Patents

Abstract

(57)【要約】 本発明は、値Ｇ^k（ｍｏｄ）ｐを算出する離散対数に基づく公開鍵暗号方法に関するものである。本発明により、乗算回数を減らすために２つの方法が提案され、一方は、値１の少ないビット数であるがシステム全体としてのセキュリティを維持するには十分な長さの「中空の」指数ｋを生成するものであり、他方は、特定の指数について同一の内積が繰り返されることがないように指数を互いに維持しつつｇ乗する並列計算を行うものである。本発明は、デジタル署名の生成、認証および暗号化に適用される。

Description

【発明の詳細な説明】 公開鍵暗号方法 本発明は、p法値の計算を行う離散対数に基づいたいわゆる公開鍵のといわれ る暗号方法を目的とするものである。 本発明は、メッセージのデジタルサインの生成，２つの単位（実体）間での認 証あるいはデータの暗号化に用途がある。 このような方法において安全性は、特定の関係、とりわけ離散対数を逆にする という、そこに認められる極端な困難性に基づいている。 この問題点は、以下ｙ=ｇ^xｍｏｄｐ（ここで、ｙはｇｘをｐで除した余りであ ると定義できる）と記述する数学的関係ｙ＝ｇ^xｐ法から考えて、ｐ、ｇおよび ｙが既知である場合に、ｘを再認識することにある。この問題は、ｐのサイズが ５１２ビットであるかまたはそれを越えると、かつｘのサイズが1２８ビットで あるかまたはそれを越えると、現在の知識では解決することは不可能である。 このようなシステムでは、一般に、モジュールを構成している大きなサイズの 番号ｐを提供する認証機関が存在する。この認証機関は、ｇによって得られる全 体、すなわち数字ｇ^xｍｏｄｐの形成された全体のような、ベースとよばれる整 数ｇも選択するが、この時ｘは間隔［０，ｐ−１］に属す、すなわち少なくとも ２¹²⁸の最大サイズの部分集合である。 パラメータｐおよびｇはいわゆる「公開」であって、すなわち、これらは認証 機関のユーザー全てに対して認証機関によって提供されるものである。 特定の変形例によれば、これらのパラメータは各ユーザーによって個別に選択 され、この場合、公開鍵の完全な一部をなすものである。 暗号システムを用いる場合における主な欠点は、実行されている複雑な計算の ために、比較的多くの計算および記憶手段が必要となるということにある。 事実、値ｇ^kｍｏｄｐの計算とは、乗算モジュールを実現することであるが、 これは計 算時間およびメモリ容量においても費用がかかる。標準的なマイクロプロセッサ しかを用いていない簡単な電子装置では、この種のオペレーションはほとんど実 現できない。 この種の計算専用のプロセッサを有する電子装置に関しては、それでもなお、 中間値を得るのに必要な計算時間およびメモリ容量には制限するのが望ましい。 事実、値ｇｋｍｏｄｐの計算は、一般に、英語の略語ＳＱＭ（平方累乗）とし て知られる従来の「累乗」方法によって比較的費用のかかるものであるが、なぜ ならそれが平均３／２Log₂（ｐ）乗算と等しい為である。 この方法によれば、ｋがｎビット長である時ｇのすべてのべき、すなわちすべ ての平方：ｇ⁰、ｇ¹、ｇ²…ｇⁿを計算し、次に、これらのべきの間で必要な乗算 を行う。（例えば、ｇ¹⁷＝ｇ¹・ｇ¹⁶）。 単純な「平方累乗」方法によれば、単純なｇ^kにもｎ／２乗算およびｎ平方が 必要である。 Ｎ個の署名を一度に送信しなければならない場合には、Ｎｇ^kを生成し、した がって並列計算を行う。 並列「平方累乗」方法では、Ｎ×ｎ／２乗算およびｎ平方が必要である。 Ｅ．ＢＲＩＣＫＥＬＬらによって提案された、略語でＢＧＫＷと呼ばれる方法 では、累乗方法を用いる場合に乗算回数を減らすことができるが、予め算出され た多数の定数の記憶装置が必要があり、したがって、極めて不利益をもたらすよ うな記憶装置のメモリー容量を備える必要がある。 この方法にＮ値の並列計算を導入することは、中間値を保持するために多数の レジスタを用いることを示している。 したがって、この方法は、極めて短い時間に多数の署名を生成することが問題 となる状況にある場合には、さらに制約を生じさせるものになる。なぜならこの 場合、並列計算が導入されるからである。 本発明の目的は、これらのすべての欠点を改善することにある。本発明は、す べての暗号システム、特にマイクロプロセッサのチップカードタイプの携帯式装 置による、暗 号的アルゴリズムの実行のために、計算時間とメモリ容量について柔軟で費用の かからない解決策をもたらすものである。 本発明の第１の目的によれば、提案されている暗号方法は、利用されている暗 号スキーム（シュノールまたはＥ１ギャマル）に従えば計算時間において１５〜 ４０％あるいはそれ以上のゲインが得られるように、乗算モジュールの回数を減 らすことを可能とする。 本発明によれば、乗算回数を減らすために２つの解決策が提案される。一つは 、わずかな１ビットとともにであるが、システムのセキュリティを保護するのに 十分な「中空の」指数ｋを生成することであり、他方は与えられた指数について 「べき」の計算を行わないように、指数同士を組み合わせることによってべきｇ の並列計算を行うことである。 本発明は、特に、値ｇ^kｍｏｄｐの計算を導く離散対数に基づく公開鍵暗号方 法を目的としている。ここで、ｐはモジュールと呼ばれる素数であり、ｋは通常 ｎビット長のランダム値であり、ｇはベースと呼ばれる整数であり、エンティテ ィＥが認証および／または署名および／または暗号化のオペレーションを実現し 、この値が介入する別のエンティティとの間での署名の交換を含むものであり、 かかる暗号方法は、 −Ｎがｎ＋ｂビットに等しいＮビット長のランダム指数ｋを生成するステップと 、 −この指数のハミング重みＣを計算し、この値を予め定められた値ｈと比較する ステップと、 −ランダム指数値ｋがＣ≧ｈの条件を満たすか否かを確認するステップと、 −ハミング値がｈより小さい場合にランダム値ｋを除去し、この条件を満たすよ うな指数が得られるまで新たな指数を生成することを再び開始するステップと、 −あるいは、逆の場合にはこの値を保持するステップと、 −保持した値から式ｇ^kｍｏｄｐを算出するステップと、 −他のエンティティとの間で電子署名を取り交わす際にかかる式を用いるステッ プと、 を含む。 また、本発明は、以下のような値ｇ^kｍｏｄの計算を導く離散対数に基づく公 開鍵暗号方法にも関するものである。ここで、ｐはモジュールと呼ばれる素数で あり、ｋは通常ｎビット長のランダム値であり、ｇはベースと呼ばれる整数であ り、エンティティＥが認証および／または署名および／または暗号化のオペレー ションを実現し、このタイプの複数の値が介入する別のエンティティとの間での 署名の交換を含み、かかる暗号方法は、 以下の式 ｋ_j＝Σａ_i２ⁱ で表される重みａ_iのｎビットのランダム指数ｋ_jの全体を生成するステップと、 −ある指数についてすでに算出されたべきｇが、それが介入する別の指数に役立 つように、指数を組み合わせて、ｇ２ⁱの「べき」を並列計算するステップと、 −与えられた各ｋ_jについて、まだ計算されていないべきｇを計算し、これらの すべての「べき」を再度グループ分けして所望の式ｇ^kjｍｏｄｐを得るステップ と、 −他のエンティティとの間で電子署名を取り交わす際にかかる式を用いるステッ プと、を含む。 本発明の一実施態様によれば、並列計算および再グループ分けのステップは以 下のオペレーション、 −２つごとに指数を組み合わせ、その共通部分を反映する指数ｋｃを得て、得ら れた組み合わせの結果について組み合わせを繰り返すステップと、 −各ｋｃ値について、 Ｇ_kc＝ｇ^kcｍｏｄｐ になるように値Ｇ_kcを計算するステップと、 −共通の部分をなくし、異なる部分のみを保持するようにこの指数が組み合わせ によって得られた指数ｋ_cを指数ｋ_jと組み合わせるステップと、 −与えられた指数ｋ_jと与えられた指数ｋ_cとの間の異なる部分を反映している指 数ｋ’_jを定義し、 −値Ｇ_k'ｊを Ｇ_k'j＝ｇ^k'jｍｏｄｐ になるように算出し、 −各繰り返し時に得られた値Ｇｋ_cの間で乗算を行うことにより式Ｇ_kjｍｏｄｐ を求めるステップを含む。 本発明の第２の実施態様によれば、並列計算および再グループ分けのステップ は以下のオペレーション、 −共通の部分を有する指数の可能な組み合わせの部分集合を形成するように指数 を組み合わせるステップと、 −与えられた重みのヌルではないビットが、考慮対象となる組み合わせの同じ重 みのヌルではないビットに対応しているような組み合わせの各部分集合について 共通部分を反映している指数ｋ_cを定義し、 −各ｋｃ値についてＧ_kc＝ｇ^kcｍｏｄｐになるように値Ｇ_kcを算出し、 −各指数ｋ_jと、これに対してこの指数ｋ_jが共通部分をなくして異なる部分のみ を保持するように属する組み合わせの各部分集合について、各々得られた指数ｋ_c 全てを組み合わせるステップと、 −与えられた指数ｋ_jおよび与えられた指数ｋ_cの間の異なる部分を反映している 指数ｋ’_jを定義し、 −Ｇ_k'j＝ｇ^k'jｍｏｄｐになるように値Ｇ_k'jを算出し、 -各ｋ_jについて値Ｇ’_kjとＧ_kcとの間で乗算を行うことによって式ｇ^kjｍｏｄｐ を求めるステップを含む。 本発明の他の目的によれば、指数間での共通の部分を得られるようにする組み 合わせは、論理和「ＡＮＤ」によって実現される。 本発明の他の目的によれば、異なる部分を得られるようにする組み合わせは、 「排他 的論理和」論理関数によって達成される。 本発明の他の特徴および利点は、添付の図面を参照して説明する例示的かつ非 限定的な実施例による説明を読むことで明らかになろう。 −図１は、本発明を実施するのに適したシステムを示す基本図である。 −図２は、第１の実施例における方法の主なステップを示す機能図である。 −図３は、本発明の第１の実施態様による第２の実施例における方法の主なステ ップを示す機能図である。 −図４は、本発明の第２の実施態様による第２の実施例における方法の主なステ ップを示す機能図である。 図１に、本発明の目的である暗号方法の実施システムの基本図を示す。 このシステムは、少なくとも１つの他のエンティティＥ２と電子信号を交換し たいと考えているエンティティＥ１からなる。各エンティティには、中央処理装 置（ＣＰＵ）１１、３０と、通信インタフェースと、揮発性メモリ（ＲＡＭ）１ ３、３２および／または書き込み不可メモリ（ＲＯＭ）１４、３４および／また は書き込み可能なまたは再書き込み可能な不揮発性メモリ（ＥＰＲＯＭまたはＥ ＥＰＲＯＭ）１５、３３と、アドレスバス、データバスおよび制御バス１６、３ ５を備えている。 処理装置および／またはＲＯＭは、本発明の目的たる方法において、すなわち 、認証セッションの時、電子署名生成時、あるいは他のエンティティに送られる 電子信号の暗号化時に行われる計算ステップの実施に対応するプログラムまたは 計算リソースを有している。 処理装置またはＲＯＭは、モジュールの乗算、加算および減算の実施に必要な リソースを有している。 処理装置および／またはＲＯＭは、各暗号化アルゴリズム専用に用いられる暗 号機能とおよびパラメータｇおよびｐを含んでいる指数ｋ_jは、認証機関によっ て再書き込み可能メモリに予め記憶させることができ、あるいは、乱数発生器ま たは秘密乱数ソースｋ_oから順次生成することもできる。さらにエンティティＥ １は秘密鍵ｘを有している。 本発明は、口座上で行われるトランザクションにおいて厳格なセキュリティが 必要と される銀行分野で実施される暗号システムに特に利用される。また、他のエンテ ィティから電子信号形式として送信されるメッセージの送信を認証したい場合に も同様である。さらに、他のエンティティとの信号の交換時にメッセージに署名 する必要がある場合も同様である。 実際、トランザクションを行いたいと思っているエンティティは、例えばチッ プカードなどの集積カードであり、この場合は目的地となるエンティティは銀行 端末などである。 説明の後半は、本発明が離散アルゴリズムに基づく任意の暗号システムに適用 できるという理解できるのでデジタルメッセージへの署名にこの方法を適用する ことについて述べるものである。 本発明による方法は、特にメモリ容量が少ない環境に適している、乗算回数を 大幅に減らす第１の解決策を提案するものである。 この場合、原則は、指数のランダムな性質を当然維持したままで、選択される ハミング重みが可能な限り最も軽いという意味で「中空の」指数ｋ_jを生成する ということである。 この目的のために、本発明による方法は、必要に応じて順次指数ｋ_jを生成す るか、あるいは交換がなされる前に予め指数ｋ_jを生成することにある。この場 合、当然これらの指数は記憶される。生成された指数はｎビットの長さではなく ｎ＋ｂビットを超える長さであり、以下において定義する条件を満たす。 ｎ＋ｂの指数ｋが生成されると、本方法は次にかかる指数のハミング重みＣ を算出し、続いてこれを予め定めた値ｈと比較する。 比較結果がＣ≧ｈである場合には、指数は保持されエンティティによって利用 されるが、このエンティティは、式ｇ^kｍｏｄｐを算出し、式を例えば署名とし て利用する様なデジタル信号を送信する際にこの式を利用する。 パラメータＣが必要な条件を満たさない場合には、対応する指数ｋは除外さ れ、新たな指数が生成され、この条件を満たす指数ｋが得られるまで、条件につ いての確認ス テップが再度実行される。 このように、この解決方法では、より小さな指数を用いた場合と全く同じセキ ュリティレベルを保持したままより少ない乗算を行うことを可能にするものであ る。 乗算回数を最大限に減らすことができる特別な実施例においては、ｃ＝ｈが選 択される。 事実、ハミングの重みがｈであるn+bビット長（ｎ=log₂pの場合）の指数の場 合、つまりこの指数がｎビットの場合と同じ結合数を有する場合、次の関係が立 証されなければならない。 2ⁿ≦^ch _n+bと、 （Ｎ+ｂ）／２+ｈ≦ｎ （実行する計算数を削減することが出来ることを条件とする。） つまり、2ｎ≦（ｎ+ｂ）！／（ｎ+ｂ-ｈ）！ｈ！ および ｂ+2ｈ≦ｎ 決定するｂとｈの数は与えられた1個のｎ（たとえばｎ＝160）のこの二重条件 付不等式を解いて求められる。 例証として、本発明による方法の結果と既知の方法とを比較してみた。 ｎ＝160ビットのシュノールのアルゴリズムの場合と、ｎ＝512ビットのＥ１ギ ャマル アルゴリズムの場合。これらの結果を下表に示す。 ｎビットの指数によって覆われた署名空間にかかる応力を、得ることを希望す るセキュリティーのレベルによりα関数によって減少させることが出来る。 よって、パラメータｎ、ｈ、ｂは条件（１）を満たす必要がある。 （１）2^n-a≦（ｎ＋ｂ）！／（ｎ＋ｂ−ｈ）！ｈ！ この場合、（ｎ＋ｂ）ビット長の異なる確率変数から同一の署名を発生させる 可能性を有する。 事実、2⁸⁰は可能な様々なアタックを妨げるのに十分であり、したがってn-α ＝100は許容出来る値である。 この実行変数は、平方のコスト（計算時）がモジュール乗算のコストよりも少 ないためますます注目に値する。 一般には次のようになる。 計算する平方の数ｓがｓ/2≦ｍ≦ｓで、ｍが乗算の数である場合、この極端な 二つケースは、ｍ＝ｓとｍ＝2ｓとなる。 この二つの極端なケースを比較した結果を下表に表す。 シュノールとEIギャマルの図表にこの手順を適用した場合に求められたゲインは 、単純に乗算した乗法と比較した場合も、１次数のコストが乗算コストと同じと 考えられる場合にも、極めて大きい。 別の実施方法によると、この手順はメモリ空間に関し、特に特別な応力のないシ ステムに適用される。 この実施方法においては、次数の計算を一回に限るためにｇの異なるべきの並 列計算を行い、同一計算を数回にわたり実行しないように、指数を結合する。 本発明をよりわかりやすくするために、２つのべきの計算方式を説明する。 k_j＝Σa_i2ⁱこの場合のk_jは乱数として求められた。（つまり、乱数発生器に基づ き生成された）または、 k_k=k_j＝Σb_i2ⁱ 本手順に従って、k_c＝Σa_ib_i2ⁱがk_jとk_kの間の共通部分を反映し、係数a_iが１ か０となるように、指数k_cを規定するように指数k_jとk_kを結合する。 指数k_cはｋ_jとk_kの共有部分に該当する。つまり、 k_j=1×2¹⁰+...＋0＋1×2⁰と、 k_k=1×2¹⁰+0+0..．＋1×2⁰ k_c＝1×2¹⁰+0+...＋1×2⁰ 本手順に従って、論理関数ETによって指数kをk_cとする。 次に、指数k_jと指数k_c間の確実な部分を決定する2番目の組み合わせを行う。 同様に、指数k_kとk_c間の確実な部分も算出する。 次の次数を並列計算する。 g^kjmodpとG^kkmodpを求めるには、次の演算を実行する。 1）G_kj×Gk_cmodp 2）Gkk×Gk_cmodp 2つの累乗を与えた上記の例と同様、n乗算ではなく平均して約3n/4の乗算を実 行する。ゲインは25％となる。 本発明による手順は、最大数の指数の組み合わせで広げることが出来る。この ような拡大は、図3と4に示すフローチャートで説明する2つの実行方法に従い導 入することが出来る。 この場合、本発明は特に大量の署名を発生させる必要のある場合に特に適用さ れる。 第一の実行方法により、下表により表される木構造のように2つずつ指数の組 み合わせを行う。 k_j a1 a2 a3 a4 k_c b1=a1・a2 b2=a3・a4 c1=b1・b2 この組み合わせにより、上記の例と同様、指数k_cをk_j ⁰間の共通部分に反映さ せることが出来る。 簡単に記述するためには、指数k_jをa₁、a₂、a₃、a₄とする。 指数k_cをツリーの-1レベルでb₁とb₂とし、ツリーの-2レベルでc₁とする。 a₁・a₂、a₃・a₄の組み合わせを論理関数ANDにより実行する。 このように構成されているツリーの各レベルで組み合わせを反復する。ビット の単純な統計分布によりツリー内に進むにつれ乗算回数が減少する。n/3乗算に より実行する計算の成果が減じられる。 上述のように、各レベルでG_kcの値が決定される。 この結果、次の式が得られる。 実際、g^a1modpはG_a1×G_b1modpの関により求められる。またg^a2modp G_a2×G_b1 ×G_c1modpの関により求められる。 第二の方法によれば、指数を可能なあらゆる組み合わせの部分集合をなすよう に組み合わせるが、すなわち、例えば、指数kj:a,b,cでは、ab,ac,bc,abcの組み 合わせを作る。 つまり論理関数ANDをaとb、aとc,bとc,bとcとa,b,cの間に行うことにより、こ れらの部分集合について共通部分を定められるような組み合わせをつくる。この ようにして累乗指数k_cを、各部分集合について定める。 すべてのG_kc=g^kcmodp値の並列計算ができ、それらのK^cは初めのＫに対してわず かに１ビットを有し、従って、それらについてのモジュラー変換も早い。 次に、一つの指数と、上述の組み合わせとの間で共通部分をとりのぞくことか らなるまた別の組み合わせをつくる。 これらの組み合わせは論理関数で行う。このようにして次が得られる。 ka=a xor abc xor ac xor ab kb=b xor abc xor ab xor bc kc=C xor abc xor ac xor bc 次にG_kj=g^xjmodpを求めることができ、このk,_jはさらにイニシャルk_cよりも１ ビットが少なく、そのモジュラー変更速度はさらに早い。 最後にg^kjmodpの式がk_jによって得られる。 この第二の実施態様で得られた署名発生Ｎの場合、演算は、次のように示され る。 n/N二乗+n(2^N-1)/N2^N+(2^N-1-1)乗算 次の表は、掛け算二乗、平行乗算二乗、および本発明のような周知の方法と比 較した場合の結果を示している。 署名Nの発生に適用される場合における与えられた第一の実施態様（木構造分 類）はメモリー容量ではコストが安い。 指数４の二分木については計算に、log₂(p)ビットの８つのレジスタが必要と なるの であろう。 与えられた第二の実施態様（N分類）が、計算時間において費用が非常に安い のは、乗算の回数において最適なためである。 ３つの指数の場合、計算のためにlog₂(p)ビットの８つのレジスタが必要であ ろう。

Claims (1)

1. 【特許請求の範囲】 １． ｐはモジュールと呼ばれる素数であり、ｋはｎビットの長さにたいてい等 しい乱数であり、ｇはベースと呼ばれる整数であるｇ^k（ｍｏｄ）ｐを算出し、 エンティティＥが、かかる値を利用して別のエンティティとの間での署名を交換 することを含む認証および／または署名および／または暗号化オペレーションを 実現する離散対数に基づく公開鍵の暗号方法であって、 −Ｎビット長（Ｎはｎ＋ｂビットに等しい）の乱数指数値ｋを生成するステップ と、 −前記指数のハミング重みＣを計算し、この値を予め固定値ｈと比較するステッ プと、 −乱数値kが条件：Ｃ≧ｈを満たすか否かを確認するステップと、 −このハミング重みがｈより小さい場合に乱数値ｋを拒否し、この条件を満たす 指数が得られるように新たな乱数を生成するステップと、 −一方、逆の場合にはこの値を保持するステップと、 −保持した値によって式ｇ^k（ｍｏｄ）ｐを算出するステップと、 −他のエンティティとの間で電子署名を取り交わす際にこの式を用いるステップ と、エンティティについて含んでいることを特徴とする公開鍵暗号方法。 ２． 満たすべき条件がｃ＝ｈであることを特徴とする請求項１に記載の方法。 ３． ｐはモジュールと呼ばれる素数であり、ｋはｎビットの長さに等しい乱数 であり、ｇはベースと呼ばれる整数であるｇ^k（ｍｏｄ）ｐを算出し、エンティ ティＥが、かかる値を利用して別のエンティティとの間での署名を交換すること を含む認証および／または署名および／または暗号化オペレーションを実現する 離散対数に基づく公開鍵の暗号方法であって、 −以下の式 ｋ_j＝Σａ_i２ⁱ で表される重みａ_iのｎビットの乱数指数値ｋ_jの全体を生成するステップと、 −ある指数について算出されたｇの内積が中で機能する他の指数に対して用いら れるように指数と組み合わせて、_g２ⁱの内積を並列計算するステップと、 −与えられた各ｋ_jについて、まだ計算されていない内積ｇを算出し、これらの 内積を再度グループ分けして所望の式ｇｋ_j（ｍｏｄ）ｐを得るステップと、 −他のエンティティとの間で電子署名を取り交わす際にかかる式を用いるステッ プと、 を含むことを特徴とする公開鍵暗号方法。 ４． 並列計算および再グループ分けするステップが、以下のオペレーションす なわち、 −２ごとに指数を組み合わせ、それらの共通の部分を反映する指数ｋ_cを得て、 結果として得られた組み合わせを再度繰り返し、 −各ｋ_c値について、 Ｇ_kc＝ｇ^kc（ｍｏｄ）ｐ になるように値Ｇ_kcを計算、 −指数ｋ_jと、前記指数が属する前記組み合わせによって得られた指数ｋ_cとを組 み合わせ、共通の部分をなくして異なる部分のみを保持し、 −与えられた指数ｋ_jと与えられた指数ｋ_cとの間の異なる部分を反映している指 数ｋ，_jを定義し、 値Ｇ_k'jを Ｇ_k'j＝ｇ（ｍｏｄ）ｐ になるように算出し、 −各繰り返し時に得られた値Ｇ_kcの間の乗算によって式Ｇ_kj（ｍｏｄ）ｐを求め ることを含むことを特徴とする請求項３に記載の方法。 ５． 並列計算および再グループ分けするステップが以下のオペレーションすな わち、 −指数同士を組み合わせ、共通の部分を有する指数の考えられる組み合わせのあ らゆる部分集合を形成し、 −組み合わせの各部分集合について、重みのヌルではないビットが、考えられる 組み合 わせの同じ重みのヌルではないビットに対応している共通の部分を反映している 指数ｋ_cを定義し、 −各ｋ_c値についてＧ_kc＝ｇ^kC（ｍｏｄ）ｐになるように値Ｇ_kcを算出し、 −各指数ｋ_jと、組み合わせの部分集合について各々得られた全ての指数ｋ_cとを 組み合わせ、指数ｋ_jが属するこれは共通の部分をなくして異なる部分のみを保 持し、 −与えられた指数ｋ_jと与えられた指数ｋ_c間の異なる部分を反映している指数ｋ ’_jを定義し、 −Ｇ_k'j＝ｇ^k'j（ｍｏｄ）ｐになるように値Ｇ^k'jを算出し、 −各ｋ_jについて値Ｇ’_kjとＧ_kcとの間で乗算を行うことによって式ｇ^kj（ｍｏ ｄ）ｐを求めることを含むことを特徴とする請求項３に記載の方法。