(57)【特許請求の範囲】
【請求項１】
有限体上で定義された楕円曲線上の点Ｐのｋ重の整数倍（k-fold multiple）ｋＰの座標（ｘ，ｙ）を、算術ロジック・ユニットと計算において用いられる値を記憶するレジスタとを有する暗号化／復号化ユニット（１６）を用いて計算する方法であって、
（ａ）前記算術ロジック・ユニットが、前記レジスタから点Ｐを取得し、ｋのバイナリ表現を取得し、Ｐだけ異なる一対の点を表すバイナリ・デジットのベクトルに対して２倍及び加算演算を連続的に実行して一対の点のｘ座標の値を取得する際にｋのそれぞれの連続的なデジットを調べるステップであって、前記一対の点の一方はｋＰに対応し、他方はｋＰからＰだけ異なる点である［ｋ−１］Ｐ又は［ｋ＋１］Ｐのいずれかに対応する、ステップと、
（ｂ）前記算術ロジック・ユニットが、前記一方の点であるｋＰのｘ座標であるｘ’を前記楕円曲線に代入し、前記楕円曲線上の点ｋＰのｙ座標である値ｙ’を決定するステップと、
（ｃ）前記算術ロジック・ユニットが、前記一方の点であるｋＰを表す座標ｘ’及びｙ’を有する点の少なくとも一方を、前記一方の点にＰを加算する又は前記一方の点からＰを減算することにより変更し、座標ｘ”及びｙ”を有する変更された点を取得するステップと、
（ｄ）前記算術ロジック・ユニットが、前記変更された点と前記他方の点［ｋ−１］Ｐ又は［ｋ＋１］Ｐとを比較し、これらの点が対応するかどうかを判断するステップと、
（ｅ）前記算術ロジック・ユニットが、前記他方の点に対応する座標を有する変更された点を提供するｙ座標の値を、前記一方の点ｋＰのｙ座標として決定するステップと、
（ｆ）前記算術ロジック・ユニットが、前記ｙ座標を選択し、前記暗号化／復号化ユニット（１６）の動作において前記点Ｐのｋ重の整数倍の座標（ｘ，ｙ）を出力するステップと、
を含むことを特徴とする方法。
【請求項２】
請求項１記載の方法において、ステップ（ａ）は、ｋの１ビットと１対の点であるｄＰ及び（ｄ＋１）Ｐとを用いて、
前記ビットが０に等しいときには、１対の点である２ｄＰ及び（２ｄ＋１）Ｐを計算するステップと、
前記ビットが１に等しいときには、１対の点である（２ｄ＋１）Ｐ及び（２ｄ＋２）Ｐを計算するステップを、
含むことを特徴とする方法。
【請求項３】
請求項２記載の方法において、
前記点２ｄＰはｄＰを２倍することによって計算され、前記点（２ｄ＋１）ＰはＰを前記点２ｄＰに加算することによって計算され、
前記点（２ｄ＋１）ＰはｄＰと（ｄ＋１）Ｐとを加算することによって計算され、前記点（２ｄ＋２）ＰはＰを（２ｄ＋１）Ｐに加算することによって計算されることを特徴とする方法。
【請求項４】
請求項１記載の方法において、前記点Ｐは前記２倍及び加算演算の間は射影座標を用いて表されることを特徴とする方法。
【請求項５】
請求項１記載の方法において、前記変更された点と前記他方の点と比較するステップは、前記変更された点と前記他方の点とのｘ座標を比較するステップを含むことを特徴とする方法。
【請求項６】
点の整数倍ｋＰから得られるｒと秘密鍵と署名されたメッセージとの組合せから得られるｓとの署名成分を有するデジタル署名を確認する方法であって、ｓＰの値とｅＱの値とを計算するステップと、ｓＰ−ｅＱを計算するステップと、ｓＰ−ｅＱ＝ｒであるかどうかをチェックするステップとを含む、デジタル署名を確認する方法であって、
請求項１ないし請求項５のいずれかの請求項に記載の方法を用いて、ｓＰ及びｅＱの少なくとも一方を計算するステップを含むことを特徴とする方法。
【請求項７】
請求項１ないし請求項５のいずれかの請求項に記載の方法を用いて前記署名において用いられる点の整数倍を計算することを特徴とする楕円曲線デジタル署名計算方法。
【請求項８】
暗号化／復号化ユニット（１６）を含み、有限体上で定義された楕円曲線上の点Ｐのｋ重の整数倍（k-fold multiple）ｋＰをｘ座標及びｙ座標を有する点を用いて決定する計算機であって、
（ａ）Ｐだけ異なる一対の点に対して２倍及び加算演算を連続的に実行して、一対の点のｘ座標の値を取得する手段であって、前記一対の点の一方はｋＰに対応し、他方はｋＰからＰだけ異なる点である［ｋ−１］Ｐ又は［ｋ＋１］Ｐのいずれかに対応する、手段と、
（ｂ）前記一方の点であるｋＰのｘ座標であるｘ’を前記楕円曲線に代入し、前記楕円曲線上の点ｋＰのｙ座標である値ｙ’を決定する手段と、
（ｃ）前記一方の点であるｋＰを表す座標ｘ’及びｙ’を有する点の少なくとも一方を、前記一方の点にＰを加算する又は前記一方の点からＰを減算することにより変更し、座標ｘ”及びｙ”を有する変更された点を取得する手段と、
（ｄ）前記変更された点と前記他方の点［ｋ−１］Ｐ又は［ｋ＋１］Ｐとを比較し、これらの点が対応するかどうかを判断する手段と、
（ｅ）前記他方の点に対応する座標を有する変更された点を提供するｙ座標の値を、前記一方の点ｋＰのｙ座標として決定する手段と、
を含むことを特徴とする計算機。
【請求項９】
請求項８記載の計算機において、前記ｘ座標の値を取得する手段は、ｋの１ビットと１対の点であるｄＰ及び（ｄ＋１）Ｐとを用いて、
前記ビットが０に等しいときには、１対の点である２ｄＰ及び（２ｄ＋１）Ｐを計算し、
前記ビットが１に等しいときには、１対の点である（２ｄ＋１）Ｐ及び（２ｄ＋２）Ｐを計算することを特徴とする計算機。
【請求項１０】
請求項９記載の計算機において、
前記点２ｄＰはｄＰを２倍することによって計算され、前記点（２ｄ＋１）ＰはＰを前記点２ｄＰに加算することによって計算され、
前記点（２ｄ＋１）ＰはｄＰと（ｄ＋１）Ｐとを加算することによって計算され、前記点（２ｄ＋２）ＰはＰを（２ｄ＋１）Ｐに加算することによって計算されることを特徴とする計算機。
【請求項１１】
請求項８記載の計算機において、前記点Ｐは射影座標を用いて表されることを特徴とする計算機。
【請求項１２】
請求項８記載の計算機において、前記計算する手段は、前記変更された点と前記他方の点とのｘ座標を比較するように動作することを特徴とする計算機。
【請求項１３】
請求項８記載の計算機において、
ｋＰのｙ座標から識別子を取得する手段と、
前記識別子とｋＰのｘ座標とを用いてｋＰを表す手段と、
を更に含むことを特徴とする計算機。
【請求項１４】
請求項１３記載の計算機において、前記識別子はｋＰのｙ座標の中の単一ビットであることを特徴とする計算機。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、有限体における演算を加速する方法に関し、更に詳しくは、暗号化システムで用いられるような体Ｆ2mにおいて実行される演算に関する。
【０００２】
【従来の技術】
Ｆ2mの中の標数（characteristics）２の有限体は、楕円曲線の算術を効果的に実現することを可能にするために、興味をもたれている。体Ｆ2mは、Ｆ2上の次数ｍのベクトル空間と見ることができる。Ｆ2上のＦ2mの基底がいったん選択されると、Ｆ2mの元は、長さがｍであり、要素がゼロ又は１であるベクトルとして表すことができる。ハードウェアでは、体の元（要素）は、長さがｍのシフト・レジスタに記憶される。体の元の加法は、ベクトル表現をビット毎にＸＯＲすることによって実行され、１クロック・サイクルを要する。
【０００３】
デジタル署名が、特定の当事者がメッセージを送ったことと、内容が伝送の間に変更されていないことを確認するために、用いられる。
【０００４】
広く用いられている署名プロトコルの組では、送り手の秘密鍵を用いてメッセージに署名するエルガマル公開鍵署名方式を用いている。この場合、受け手は、送り手の公開鍵を用いて署名を確認することができる。
【０００５】
このような方式を実現するためのプロトコルは、様々であり、広く用いられているものもある。しかし、それぞれの場合に、受け手は、署名を確認するために計算を実行することが要求される。受け手が適切な計算能力を有している場合には、これは、特に問題とはならないが、例えば、「スマート・カード」の応用例のように、受け手側の計算能力に制限が存在する場合には、計算のために、確認プロセスが遅延することになる。公開鍵方式は、離散対数問題が扱い困難であるかのように見える多数の群を用いて実現することもできるが、特に堅固な実現方法として、有限体上の楕円曲線上の点の特性を用いるものがある。個の実現方法は、例えば、Ｚ＊pにおける実現例と比較して、比較的小さな位数の体で要求されるセキュリティが得られ、従って、署名の通信に必要となる帯域幅を減少させることができるという利点がある。
【０００６】
典型的な実現例では、署名成分ｓは、ｓ＝ａｅ＋ｋ（ｍｏｄｎ）という形式を有する。ここで、Ｐは、このシステムの予め定義されたパラメータである曲線上の点である。ｋは、短期的な秘密鍵、又は、セッション鍵として選択されたランダムな整数であり、対応する短期的な公開鍵Ｒ＝ｋＰを有する。ａは、送り手の長期的な秘密鍵であり、対応する公開鍵ａＰ＝Ｑを有している。ｅは、メッセージｍと短期的な公開鍵Ｒとの、ＳＨＡハッシュ関数などの、安全ハッシュである。ｎは、曲線の位数（オーダー、次数）である。送り手は、受け手に、ｍ、ｓ、Ｒを含むメッセージを送り、署名は、Ｒに対応しなければならない値Ｒ'＝（ｓＰ−ｅＱ）を計算することによって、確認される。計算された値が同一であれば、署名は、確認される。
【０００７】
確認を実行するためには、多数の点の乗法を実行してｓＰ及びｅＱを得なければならないが、これは、それぞれが、計算的に複雑である。
【０００８】
Ｆｑが有限体であれば、Ｆｑ上の楕円曲線は、２つのクラスに分類される。すなわち、超特異（supersingular）な曲線と、非超特異（non-supersingular）な曲線とに分けられる。Ｆqが標数２である、すなわち、ｑ＝２Mである場合には、これらのクラスは、次のように定義される。
【０００９】
ｉ）方程式ｙ2＋ａｙ＝ｘ3＋ｂｘ＋ｃのすべての解の集合に、無限遠点Ｏと称される特別な点を加えたものが、Ｆq上の超特異曲線である。ここで、ａ、ｂ、ｃは、Ｆqの元であり、ａは、ゼロでない。
【００１０】
ｉｉ）方程式ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂのすべての解の集合に、無限遠点Ｏと称される特別な点を加えたものが、Ｆｑ上の非超特異曲線である。ここで、ａ、ｂは、Ｆqの元であり、ｂは、ゼロでない。
【００１１】
これらの点の上で適切な加法を定義することにより、加法的なアーベル群が得られる。ｙ2＋ａｙ＝ｘ3＋ｂｘ＋ｃで表される超特異な楕円曲線Ｅに対する２つの点Ｐ（ｘ1，ｙ1）とＱ（ｘ2，ｙ2）との加法は、次のように与えられる。
【００１２】
ＰがＥに属する場合には、Ｅに属するすべてのＥに対して、−Ｐ＝（ｘ1，ｙ1＋ａ）、Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐと定義する。
【００１３】
ＱがＥに属し、Ｑと−Ｐとが異なる場合には、Ｐ＋Ｑという和を表す点は、（ｘ3，ｙ3）と表される。ここで、ｘ3及びｙ3は、次の通りである。
【００１４】
【数１】
0004306829.tif 000002
ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂで表される非超特異な楕円曲線Ｅに対する２つの点Ｐ（ｘ1，ｙ1）とＱ（ｘ2，ｙ2）との加法は、次のように与えられる。
【００１５】
ＰがＥに属する場合には、Ｅに属するすべてのＥに対して、−Ｐ＝（ｘ1，ｙ1＋ｘ1）、Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐと定義する。
【００１６】
ＱがＥに属し、Ｑと−Ｐとが異なる場合には、Ｐ＋Ｑという和を表す点は、（ｘ3，ｙ3）と表される。ここで、ｘ3及びｙ3は、次の通りである。
【００１７】
【数２】
0004306829.tif 000003
超特異な曲線の方が好ましいが、その理由は、この曲線の方が、ＭＯＶ攻撃に対して強いからである。Ｅ上で２つの点の和を計算するには、基礎となる体Ｆ2mにおける複数回の乗算、加算、反転演算が必要となることがわかった。また、それらの演算は、それぞれが、一連の基本的なビット演算を必要とする。
【００１８】
【発明が解決しようとする課題】
エルガマル方式又はディフィ・ヘルマン方式における暗号論的な演算や、楕円曲線に関する最も暗号論的な演算を実現する際には、ｋＰ＝Ｐ＋Ｐ＋・・・＋Ｐ（Ｐをｋ回加える）を計算することが必要となる。ここで、ｋは、正の整数であり、ＰはＥに属している。このためには、（ｘ3，ｙ3）をｋ−１回計算することが要求される。ｋの値が大きい場合には、そしてこれは、暗号への応用では必要となることが多いのであるが、これは、従来は、データ通信に対して実際的ではないと考えられてきた。ｋが、例えば１０２４ビットの大きさである場合には、ｋＰは、Ｐの２1024回の加算を実行することによって、計算されることになる。
【００１９】
更に、乗法群の場合には、乗算と反転演算とは、極めて計算的に集約的である。体の反転演算は、体の乗算よりも更に費用がかかる。２つの点を加算するときに必要となる反転演算は、射影座標を用いることによって除去することができる。しかし、２つの点の加法公式は、アフィン座標を用いる場合よりも、より多くの回数の乗算を必要とすることになる。
【００２０】
Vanstone et al., "Elliptic Curve Cryptosystems and Their Implementation", The Journal of Cryptologyには、射影座標に変換し、従って、反転計算を除去することによって、２つの点を加算する方法が記載されている。しかし、反転演算を除去したことによる全体的な速度の利得は、空間的な犠牲において得られている。Ｐ及びＱを記憶するための、また更には、加算を実行する際の中間的な結果を記憶するための余分なレジスタが必要となるのである。更に、この方法は、計算において、ｙ座標を用いることが必要となる。
【００２１】
従って、本発明の目的は、上述の問題点のいくつかが解消又は克服される方法及び装置を提供することである。
【００２２】
本発明の別の目的は、有限体の元を乗算する方法を提供することであり、スマート・カードなどのように、限定的な計算能力しか有していないプロセッサ上でも比較的効率的に実現できる方法を提供することである。
【００２３】
本発明の更に別の目的は、楕円曲線暗号化システムにおいて、署名の確認（認証）が加速されるような方法及び方法を提供することである。
【００２４】
【課題を解決するための手段】
本発明によると、体Ｆ2M上で定義された楕円曲線上の点Ｐの整数倍を決定する方法が提供され、この方法は、
ａ）数ｋをバイナリ・デジットｋiのベクトルとして表すステップと、
ｂ）最大でＰだけ異なっている点Ｐ1及びＰ2の対を形成するステップと、
ｃ）前記ｋiのそれぞれを選択し、前記ｋiのそれぞれに対して、
ｋiが１であるときには、点Ｐ1及びＰ2の対を加算して新たな点Ｐ1を形成し、点ＰをＰ1に加算して新たな点Ｐ2を形成し、新たな点を用いて、点Ｐ1及びＰ2の対と交換し、
ｋiがゼロであるときには、前記点Ｐ1を２倍して新たな点Ｐ1を形成し、点Ｐを加算して新たな点Ｐ2を形成し、新たな点を用いて、点Ｐ1及びＰ2の対と交換し、それによって、積ｋＰが、Ｍはｋの桁数を表すとして、点Ｐ1から、Ｍ−１のステップで得られる、ステップと、
を含んでいる。
【００２５】
更に、本発明の発明者たちは、積ｋＰの計算が点Ｐのｙ座標を用いずに行われる方法を実現した。
【００２６】
【発明の実施の態様】
本発明の実施例を、添付の図面を参照することによって、以下で説明する。
【００２７】
図１を参照すると、データ通信システム２は、通信チャネル１４を介して接続されている１対の通話者である、送り手１０と受け手１２とを含む。通話者１０、１２のそれぞれは、デジタル情報を処理して以下で説明するようにチャネル１４を介して伝送する準備をする、暗号化／復号化ユニット１６を含む。暗号化／復号化ユニットは、他の機能に加えて、鍵交換プロトコルと暗号化／復号化アルゴリズムとを実現している。
【００２８】
モジュール１６は、その概略が図２に示されているが、鍵の交換と生成とを含む計算を実行する算術ロジック・ユニット２０を含む。秘密鍵レジスタ２２は、秘密鍵ｄを含み、この秘密鍵ｄは、例えば、１５５ビットのデータ・ストリングとして乱数生成器２４から生成され、公開鍵レジスタ２６に記憶されている公開鍵を生成するのに用いられる。ベース・ポイント・レジスタ２８は、楕円曲線内に存在し、１５５ビットのデータ・ストリングとして、それぞれの座標（ｘ，ｙ）を有するように選択されたベース・ポイントＰの座標を含む。データ・ストリングは、それぞれが、バイナリ・デジットから成るベクトルであり、それぞれのデジットは、座標の正規基底表現での有限体の元の係数である。
【００２９】
選択された楕円曲線は、一般的に、ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂという形式であり、この曲線のパラメータ、すなわち、係数ａ及びｂは、パラメータ・レジスタ３０に記憶されている。レジスタ２２、２４、２６、２８、３０の内容は、必要に応じて、ＣＰＵ３２の制御の下に、算術ユニット２０に転送される。
【００３０】
公開鍵レジスタ２６の内容もまた、適切な要求が受信されると、通信チャネル１４に対して利用可能になる。最も単純な実現例では、共通の安全ゾーンにおけるそれぞれの暗号化モジュール１６は、同じ曲線及びベース・ポイントと共に動作し、それによって、レジスタ２８及び３０の内容は、アクセス不要となる。しかし、更なる複雑さが要求される場合には、それぞれのモジュール１６は、それ自身の曲線及びベース・ポイントを選択して、この場合には、レジスタ２８及び３０の内容は、チャネル１４に対してアクセス可能となる。
【００３１】
モジュール１６はまた、暗号化と鍵の交換とに用いるために、生成器２４から整数ｋとセッション・シード（seed）とを受け取る整数レジスタ３４を含む。モジュール１６は、計算の間に必要に応じて一時記憶装置として用いられるＲＡＭ３６を有する。
【００３２】
一般的な実施例によると、送り手は、データ・ストリングを組み立てるが、これには、送り手の公開鍵Ｑ、メッセージｍ、送り手の短期的な公開鍵Ｒ、送り手の署名成分が含まれている。組み立てられると、データ・ストリングは、チャネル４上を、目的の受け手１２に向けて送られる。
【００３３】
単純のために、送り手１０の署名成分ｓは、上述のように、ｓ＝ａｅ＋ｋ（ｍｏｄｎ）の形式を有している。もちろん、これ以外の署名プロトコルを用いてもよい。署名を確認するためには、ｓＰ−ｅＱを計算し、Ｒと比較しなければならない。
【００３４】
従って、受け手の第１のステップは、ストリングからＱの値を検索することである。メッセージｍと点Ｒの座標とから、ハッシュ値ｅも計算することができる。受け手は、次に、ｓＰ及びｅＱを計算することによって、確認を行うことができる。
【００３５】
ｓＰ又はｅＱの計算を加速するためには、受け手は、次の方法を採用し、新たな点ｓＰの座標を計算することにより、基礎となる体Ｆ2mにおける複数の乗算、加算及び反転演算の実行を回避する。受け手は、図３に示されている「２倍して加算」（double and add）の方法を用いることによって、ｓＰを計算する。
【００３６】
図３を参照すると、点ｋＰを導くために楕円曲線Ｅ上の点Ｐに値ｋを乗算するための「２倍して加算」の方法を図解している本発明の１つの実施例が実現されている。まず最初に、ｋをそのバイナリ形式で表現する。次に、連続的な一連の点の対（ｍＰ，（ｍ＋１）Ｐ）が設定される。ｋのそれぞれの連続的なデジットが考察され、ｋのバイナリ表現においてゼロの値のデジットが生じると、点の対の第１のものが、２倍され、点の対の第２のものに１が加算される。すなわち、（ｍＰ，（ｍ＋１）Ｐ）から、（２ｍＰ，（２ｍ＋１）Ｐ）が計算される。ｋのバイナリ表現において１の値のデジットが生じると、対の第１が、点の先の対の和から形成され、対の第２のものが、対の第１のものに１を追加することによって、形成される。すなわち、（ｍＰ，（ｍ＋１）Ｐ）から、（（２ｍ＋１）Ｐ，（２ｍ＋２）Ｐ）を計算する。
【００３７】
これは、次の短い例によって説明することにする。ｋ＝２３とする。このｋの値は、バイナリ形式では、対（１１０１１）として表すことができる。上述の規則を点（Ｐ，２Ｐ）の対に適用すると、連続的な点のシーケンス（２Ｐ，３Ｐ）、（５Ｐ，６Ｐ）、（１１Ｐ，１２Ｐ）、・・・、（２３Ｐ，２４Ｐ）が得られる。従って、この対の第１のものが、要求される点である。
【００３８】
このように、最終的な結果２３Ｐが、体における１対の点に対して一連の「２倍して加算」の演算を実行することによって、得られる。ここで、与えられた対における点の対は、Ｐだけ異なっている。更に、「２倍して加算」演算の数は、最大で、ｋのビット数から１少ない。すなわち、（ｍ−１）回である。この「２倍して加算」の方法は、ｋの大きな値に対しては、プロセッサが実行する演算の数を減少させる点で、著しい長所を有している。これは、従来技術の説明において述べた、１つの点Ｐに対するｋ回の２倍及び加算の実行と比較して対照的である。
【００３９】
ｓＰ及びｅＱの計算に戻ると、受け手は、上述の実施例を適用して、Ｆ２ｍ上で定義されている非超特異な楕円曲線ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂに対して、ｓＰを計算する。
【００４０】
Ｐ1＝（ｘ1，ｙ1）及びＰ2＝（ｘ2，ｙ2）であり、Ｐ1（≠±Ｐ2）とＰ2とが、曲線Ｅの上の点である場合には、Ｐ1＋Ｐ2＝（ｘ3，ｙ3）と定義することができる。ここで、ｘ3は、次のように表される。
【００４１】
【数３】
ｘ3＝λ2＋λ＋ｘ1＋ｘ2＋ａ
また、曲線の勾配は、λ＝（ｙ2＋ｙ1）／（ｘ2＋ｘ1）によって与えられる。
【００４２】
同様にして、−Ｐ2＝（ｘ2，ｙ2＋ｘ2）及びＰ1−Ｐ2＝（ｘ4，ｙ4）である場合には、ｘ4は、次のように表される。
【００４３】
【数４】
ｘ4＝λ￣2＋λ￣＋ｘ1＋ｘ2＋ａ＝λ2＋ｘ／（ｘ1＋ｘ2）2＋λ＋ｘ2／（ｘ1＋ｘ2）＋ｘ1＋ｘ2＋ａ
また、λ￣＝（ｙ２＋ｘ2＋ｙ１）／（ｘ2＋ｘ1）＝ｘ2／（ｘ2＋ｘ1）＋λである。ｘ3とｘ4とを加算すると、次の式が得られる。
【００４４】
【数５】
ｘ3＋ｘ4＝ｘ／（ｘ1＋ｘ2）2＋ｘ2／（ｘ1＋ｘ2）＝ｘ1ｘ2／（ｘ1＋ｘ2）2
（Ｐ1＋Ｐ2）のｘ座標であるｘ3を計算するには、Ｐ1、Ｐ2、（Ｐ1−Ｐ2）のｘ座標だけが必要である。しかし、この計算は、反転演算を必要とするので、最適に効率的ではない。ｙ座標がこの計算において不要であることには注意すべきである。
【００４５】
図２を再び参照すると、ｋＰの値は、「２倍して加算」の方法を用いて、計算される。点の新たな対が計算されるときには、上述の数式５の加算公式が用いられ、これは、ｍ回実行される。
【００４６】
従って、我々は、ｘ1、ｘ2、ｘ4を含むｘ3の公式を有している。不運にも、この公式は、反転演算を含み、これには費用がかかる。この方程式は、次のように修正することができる。ここで、ｘ1、ｘ2、ｘ3が、ｘ1／ｚ1、ｘ2／ｚ2、ｘ3／ｚ3によって与えられるとする。ここで、ｘ1、ｘ2、ｘ3、ｚ1、ｚ2、ｚ3は、２倍して加算のアルゴリズムの間に維持される値である。次にこれらの表現を数式５に代入すると、次が成立する。
【００４７】
【数６】
0004306829.tif 000004
従って、ｘ3＝ｘ4（ｘ1ｚ2＋ｘ2ｚ1）2＋ｘ1ｘ2ｚ1ｚ2とすると、ｚ3＝（ｘ1ｚ2＋ｘ2ｚ1）2である。我々は、図３の「２倍して加算」のアルゴリズムを、この新たな表現を用いて実行し、アルゴリズムのほとんどに対して、反転の計算を回避することができる。
【００４８】
上のｘ3及びｚ3に対する式から、ｘ3は、最大でも４回の乗法演算を実行することによって計算できることがわかる。
【００４９】
点Ｐ1及びＰ2の和は、ｘ3によって表現することができ、ｚ3は、ｘ座標に関する比較的費用のかかる反転演算を実行する必要なく得られ、最大で４回の乗法演算と２回の平方演算とを用いて計算できる。残りの加法及び平方演算は、計算能力の観点から、比較的費用がかからない。（ｘ1ｚ2＋ｘ2ｚ1）2の項の計算は、括弧の中の値の正規基底の巡回シフトによって得られ、これは、汎用プロセッサが比較的容易に実行できるものである。アルゴリズムの最後には、必要であれば、元の表現に変換によって戻ることもできる。
【００５０】
再び図３を参照すると、点Ｐ（ｘ1，ｙ1）を２倍するためには、２（ｘ1，ｙ1）＝（ｘ3，ｙ3）として、楕円曲線の方程式が上述のようにＦ2m上のｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂと与えられる場合には、点２Ｐのｘ座標は、ｘ3＝ｘ12＋ｂ／ｘ12と表される。射影座標を用いてこの座標を表すと、ｘ3＝ｘ14＋ｂｚ14であり、ｚ３＝（ｘ1ｚ1）2、又は、ｘ3＝（ｘ1＋ｂ1/4ｚ１）である。
【００５１】
ｂを比較的小さくすることによって、計算的に比較的高価な演算を、ｚ3の項に対する約１回の乗算に減少させることができる。我々は、ｂ1/4を予め計算してあるので、最後の数式に従って、ｘ3を計算することができ、従って、平方の数を減らすことができる。そのようにする代わりに、先に通常の表現方法で記載したように、ｘ14及びｚ14の計算は、それぞれの値の表現を２サイクル分だけシフトすることによって得られ、一方、（ｘ1ｚ1）2は、ｘ1ｚ1を１サイクル分シフトすることによって得られる。
【００５２】
先に下線を付けた「２倍及び加算」の図３に示した方法は、Ｆ2m上に定義されたｍビットのスカラ値ｋ及びｋＰの計算に対して、高々（ｍ−１）回の２倍及び加算を必要とすることが、分かる。上記の説明から、楕円曲線上の点における２倍演算は、高々２つの乗算演算によって実行され、一方、加算演算は、高々４回の乗算演算によって実行される。このように、本発明の方法を用いてｋＰのｘ座標を計算するために、高々６回の（ｍ−１）の乗算演算を行えばよい。
【００５３】
ｘ値が計算されると、上記したように、ｙ座標も決定される。しかしながら、各ｘ座標に対して、高々２つのｙ座標が存在するだけである。例えば、点２４Ｐを得るための最終ステップにおいて、点２３Ｐと点Ｐとが既知であり、したがって、２４Ｐは、２４Ｐ＝２３Ｐ＋Ｐとして表すことができる。点Ａ＝２３ＰのＸ線座標ｘ23が既に上記したように得られていると仮定する。そして、楕円曲線の方程式Ｅにｘ23を代入して得られた２次方程式を解くことによって、２つの点Ａ（ｘ23，ｙ23(1)）及び点Ｂ＝（ｘ23，ｙ23(2)）に対応して２つのｙ値が得られる。次に、計算２４Ｐ＝Ｐ＋２３Ｐにより得られたＸ座標ｘ24を楕円曲線の方程式に代入することにより、２つの点（ｘ24，ｙ24(1)）及び（ｘ24，ｙ24（2)）が得られる。そしてこれらの２つの点は記憶される。点Ａ＋Ｂに点Ｐを加算するために、元の点加算を用いて対応する点Ａ＋Ｐ＝（ｘa，ｙa）及び点Ｂ＋Ｐ＝（ｘb，ｙb）をそれぞれ生成する。点（ｘa，ｙa）は、点（ｘ24，ｙ24(1)）及び（ｘ24，ｙ24(2)）とそれぞれ比較される。一致する点が無い場合は、点（ｘb，ｙb）は間違っている点であり、それ以外の場合は、点（ｘb、ｙb）は正しい点である。このように、点Ｐの乗算がｙ座標の値を必要としないで簡単に計算でき、さらに、ｙ座標は、必要に応じて、計算の最終段階で得ることができることは、明らかであろう。
【００５４】
したがって、例えば、楕円曲線に関するエルガマル方式がｒ＝ｋＰ＝（ｘ，ｙ）を計算する必要があることは先に説明したとおりであるが、この場合を参照すると、ｙ座標をドロップし、メッセージｍ及びｘ座標のハッシュｅ＝ｈ（ｍ／／ｘ）を生成することができる。送信側はつぎに、署名ｓ及びハッシュｅを含むメッセージを受信側に送信する。サインｓは、ｍｏｄｎのｓ＝（ｄｅ＋ｋ）の形態であり、ｄは送信側の秘密鍵であり、ｋは送信側によって生成されたランダム数である。その後、受信側は、ｓＰ−ｅＱ＝ｒを計算することによって、署名の有効性を判定する。ｓＰ及びｅＱのいずれも、本発明の「２倍及び加算」方法によって計算することができる。ｓＰ及びｅＱのｘ値はそれぞれ、２つの可能性のあるｙ値、即ち（ｘ1，ｙ1(1)）、（ｘ1，ｙ1(2)）及び（ｘ2，ｙ2(1)）、（ｘ2，ｙ2(2)）におけるｙ値を生成するが、これらは楕円曲線の方程式Ｅに代入されるときに生成される。これらの点の配列の間で点減算が実行されると、正しいｙ値が適切なマッチングｒを生成する。これらの代入のいずれによってもマッチングｒが生成されない場合は、署名は無効である。
【００５５】
図４を参照すると、この図には、図３に関連して説明した方法、及び所定の点Ｐ＝（ｘ，ｙ）、並びに（ｋ−１）Ｐのｘ座標ｘ＊（＊は反転を表す）及びｋＰのｘ座標ｘ'により導出されたｋＰのｙ座標を決定するための別の方法の概略図が、番号５０によって示されている。図３に関連して明らかなように、ｋＰのｘ座標を計算する上で（ｋ−１）Ｐのｘ座標も計算される。
【００５６】
したがって、ｙ'を得るために楕円曲線の方程式に最初に代入を行うときには、点（ｘ'，ｙ'）がこの曲線上に存在する。次に、ステップ５４において、点Ｑを（ｘ'，ｙ'）に割り当て、そして、単一の点減算５５によって、点Ｑ−Ｐを計算する。得られたｘ座標ｘ''は、ステップ５６において、（ｋ−１）のｘ座標ｘ＊と比較され、ｘ''＝ｘ＊の場合はｙ'がｋＰのｙ座標となり、そうでない場合はｙ'は−ｋＰのｙ座標となる。この方法は、０<ｋ<点Ｐの順位のときに実行できることに留意すべきである。
【００５７】
ｋＰを計算するために本発明の方法を用いることにより、ｋＰ及び（ｋ＋１）Ｐ上のｘ座標をそれぞれ得ることができるので、（ｋ＋１）Ｐを計算することも可能である。この場合、ｙ座標は、Ｑ＋Ｐ＝（ｘ''，ｙ''）を計算してｘ''を（ｋ＋１）Ｐのｘ座標と比較することによって、得ることができる。
【００５８】
図５を参照すると、本発明の実施例の、楕円曲線署名の確認への別の応用例が参照番号７０によって、示されている。第１の通話者１０が秘密鍵であるランダムな整数ｄと点Ｑ＝ｄＰの計算から導かれる対応する公開鍵Ｑとを含むと再び仮定する。メッセージＭに署名するために、ハッシュ値ｅがハッシュ関数Ｈを用いて、メッセージＭから計算される。次に、ランダムな整数ｋが、秘密セッション鍵として選択される。対応する公開セッション鍵ｋＰがランダムな整数ｋから計算される。第１の通話者は、次に、点ｋＰのｘ座標を、整数ｚとして表し、次に、第１の通話者成分ｒ＝ｚｍｏｄｎを計算する。
【００５９】
次に、第２の署名成分ｓ＝ｋ-1（ｅ＋ｄｒ）ｍｏｄｎも計算される。署名成分ｓ及びｒとメッセージＭとが、次に第２の通話者１２に送信される。第２の通話者１２がメッセージＭ上の署名（ｒ，ｓ）を確認するために、第２の通話者は、第１の通話者１０の公開鍵Ｑを参照する。メッセージＭのハッシュｅ'が、ｅ'＝Ｈ（Ｍ）となるように、ハッシュ関数を用いて、計算される。値ｃ＝ｓ-1ｍｏｄｎも計算される。次に、整数値ｕ1及びｕ2が、ｕ1＝ｅ'ｃｍｏｄｎ及びｕ2＝ｒｃｍｏｄｎとなるように計算される。署名を確認するために、値ｕ1Ｐ＋ｕ2Ｑが計算されなければならない。Ｐは知られており、システム全体のパラメータであるので、値ｕ1Ｐが、予め計算されていたＰの整数倍を用いて、迅速に計算される。例えば、これらの値は、Ｐの２倍の予め記憶されているテーブルである２Ｐ、４Ｐ、８Ｐなどから合成される。しかし、他方で、点Ｑは、現在値であり、ユーザごとに変動するので、ｕ2Ｑの値は、計算するのにいくらかの時間を要し、一般的に、予め計算しておくことはできない。
【００６０】
しかし、本発明による方法を用いることによって、署名の確認は、著しく加速される。通常は、点Ｒ＝ｕ1Ｐ＋ｕ2Ｑが計算される。点Ｒ（ｘ，ｙ）の体の元ｘは、整数ｚに変換され、値ｖ＝ｚｍｏｄｎが計算される。ｖ＝ｒであれば、署名は有効である。
【００６１】
また、ｕ２のモジュラー反転ｕ2＊＝ｕ2-1が計算される場合にｕ2Ｑを計算する「２倍して加算」を利用することができ、Ｒを、ｕ2（ｕ1ｕ2＊Ｐ＋Ｑ）として、すなわち、恒等式であるｕ2ｕ2＊＝１を用いることによって、表すことができる。ｕ1ｕ2＊の値は、整数であり、従って、容易に計算することができる。このように、点ｕ1ｕ2＊Ｐは、容易に計算できて、Ｐの整数倍に関して予め記憶されている値から作成することができる。点Ｑは、次に、点ｕ1ｕ2＊Ｐに加算されるが、これは、１回の加算であり、新たな点Ｒ'を得る。
【００６２】
このようにして、署名を確認するために、受け手は、ｕ2Ｒ'の値のｘ座標を決定すればよいだけである。この計算は、図３を参照して既に説明した「２倍して加算」の方法を用いて実行される。もしこれがｒに等しい場合には、署名は確認される。結果的な値は、点ｕ1Ｐ＋ｕ2Ｑのｘ座標である。値ｖ＝ｘｍｏｄｎが計算され、ｒに対して確認される。この方式では、ｙ座標は、署名生成や確認には用いられていないが、これは、計算が必須ではないからである。しかし、ｘ及びｙ座標の両方に対する別の方式をこの場合に用いることができ、その場合は、ｙ座標は、既に述べたように導かれ、与えられたｘ座標に対応する２つのｙ座標が計算されて、それぞれが、署名の確認のために用いられる。どちらもこの比較を満足することがなかった場合には、署名は、無効である。すなわち、確認が点Ｒ＝Ｕ1Ｐ＋Ｕ2Ｑの計算を必要としないからである。これは、次のように行われる。図３の「２倍して加算」かＥ（Ｆp）かのどちらかを用いることによって、Ｑのｘ座標だけを送信し、Ｕ2Ｑのｘ座標だけを計算する。このｘ座標に対応する両方の点を試してみて、どちらによって確認がなされるかを見る。
【００６３】
図１に戻ると、ｋＰの形式の鍵が、通話者の間で送信され帯域幅を減少させると、送り手は、ｋＰの座標の一方だけを送信し、他方の座標は受け手において計算することが可能である。例えば、体の元がＦ2155に対して、１５５ビットである場合には、他方の座標の正しい値の１ビットである識別子もまた、送信されうる。これによって、第２の座標が受け手によって計算され、識別子から正しいものが識別される可能性が生じる。
【００６４】
従って、図１を参照すると、送り手１０は、最初に、受け手１２の公開鍵ｄＰとして座標ｘ0とｙ0の座標の１ビットとを表すビット・ストリングを検索する。
【００６５】
送り手１０は、レジスタ３０に曲線のパラメータを有しているので、座標ｘ0と曲線パラメータとを用いて、算術ユニット２０から、他方の座標ｙ0の可能性のある値を得る。
【００６６】
ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂの形式の曲線と座標ｘ0との場合には、ｙ0に対して可能性のある値ｙ1及びｙ2は、方程式ｙ2＋ｘ0ｙ＝ｘ03＋ａｘ02＋ｂの根である。
【００６７】
算術ユニット２０において、ｙに関して解くことにより、２つの可能性のある値が得られ、情報の送信ビットとの比較によって、どちらの値がｙの適切な値であるかが示される。
【００６８】
第２の座標（ｙ0）の２つの可能な値は、ｘ0だけ異なっている。すなわち、ｙ1＝ｙ2＋ｘ0である。ｙ0の２つの値がｘ0だけ異なるので、ｙ1とｙ2とは、１がｘ0の表現において生じる場合には、常に異なる。従って、送信される追加的なビットは、これらの位置の１つから選択され、ｙ0の値の対応するビットの検査は、２つの根のどちらが適切な値であるかを示す。
【００６９】
受け手１０は、１５６ビットだけが検索される場合でも、このようにして、公開鍵ｄＰの座標を生成することができる。
【００７０】
セッション鍵ｋＰを受け手１２に送信する際にも同様の効率が実現できるが、この理由は、送り手１０は１つの座標ｘ0と、ｙ0の選択された識別ビットとを送るだけでよいからである。受け手１２は、次に、ｙ0の可能な値を再構成して、適切な１つを選択する。
【００７１】
体Ｆ2mにおいては、２ａ＝０であるから、二次公式を用いてｙについて解くことは不可能である。従って、他の技術を用いる必要があり、特に、算術ユニット２０をこれを効率的に実行するように適応させる。
【００７２】
一般には、ｘ0がゼロでないと仮定すると、ｙ＝ｘ0ｚである場合には、ｘ02ｚ2＋ｘ02ｚ＝ｘ03＋ａｘ02＋ｂである。これは、ｚ2＋ｚ＝ｘ0＋ａ＋ｂ１／ｘ02＝ｃとして書くことができる。すなわち、ｚ2＋ｚ＝ｃである。
【００７３】
ｍが奇数である場合には、ｚ＝ｃ＋ｃ4＋ｃ16＋・・・＋ｃ2m-1か、又は、ｚ＝１＋ｃ＋・・・＋ｃ2m-1かのどちらか一方であり、ｙ0の２つの可能性のある値を提供する。
【００７４】
ｍが偶数でありｃ2gの形式の項を用いる場合にも、類似の解が存在する。
【００７５】
これは、正規基底のＦ2mのと共に用いるのに特に適している。
【００７６】
上述のように、体の元が正規基底として表されている場合には、体Ｆ２ｍの元のｇのベキ乗を作ることは、ｇ重の巡回シフト（g fold cyclic shift）によって達成することができる。
【００７７】
従って、ｚのそれぞれの値は、得られたｙ0の値をシフト及び加算することによって、計算することができる。値の中の正しい１つは、送信された追加的なビットによって決定される。
【００７８】
従って、Ｆ2mにおいて正規基底表現を用いることによって、座標ｙ0を回復するのに用いられるプロトコルが単純化される。
【００７９】
Ｐ＝（ｘ0，ｙ0）が体Ｆ2m上で定義された楕円曲線Ｅ：ｙ2＋ｘｙ＝ｘ3＋ａｘ2＋ｂの上の点である場合には、ｘ0がゼロである場合には、ｙ0はゼロであると定義される。ｘ0がゼロではない場合には、ｙ0は、体の元ｙ0ｘ0-1の最下位ビットであると定義される。
【００８０】
Ｐのｘ0のｘ座標とビットｙ0とは、送り手１０と受け手１２との間で伝送される。ｙ座標であるｙ0は、次のようにして回復される。
【００８１】
１．ｘ0がゼロである場合には、ｙ0は、パラメータ・レジスタ３０に記憶されている体の元ｂのベクトル表現を１つの位置だけ左へ巡回的にシフトさせることによって得られる。すなわち、ｂ＝ｂm-1ｂm-2・・・ｂ1ｂ0である場合には、ｙ＝ｂm-2・・・ｂ1ｂ0ｂm-1である。
【００８２】
２．ｘ0がゼロでない場合には、次を実行する。
２．１  体Ｆ2mにおいて、元ｃ＝ｘ0＋ａ＋ｂｘ0-2を計算する。
２．２  ｃのベクトル表現をｃ＝ｃm-1ｃm-2・・・ｃ1ｃ0とする。
２．３  次の数式７のように設定することによって、体の元ｚ＝ｚm-1ｚm-2・・・ｚ1ｚ0を構成する。
【００８３】
【数７】
0004306829.tif 000005
２．４  最後に、ｙ0＝ｘ0・ｚを計算する。
【００８４】
ｘ0-2の計算は、上述したように、算術ユニット２０において容易に行うことができ、ｙ0の計算は、乗算器４８から得ることができる。
【００８５】
上述の例では、適切なｙ0の値の識別は、１ビットを送信して、得られた根の値を比較することによって得られた。しかし、他のインジケータを用いて、値のうちの適切な一方を識別することもでき、演算は、体ＧＦ（２m）における楕円曲線を用いた暗号化には限定されない。例えば、体がＺpｐ＝３（ｍｏｄ４）として選択される場合には、適切な値に関連するルジャンドル（Legendre）記号を送信して、適切な値を指定することもできる。また、Ｚｐの元の組を更に１対の部分集合に分割して、ｙが一方の部分集合に含まれる場合には、−ｙは、他方に含まれるとすることもできる。ただし、ｙはゼロではない。任意の値を次にそれぞれの部分集合に割り当てて、座標ｘ0と共に送信し、どちらの部分集合にｙ0の適切な値が位置するかを指示するようにすることもできる。従って、ｙ0の適切な値を決定することができる。部分集合を間隔として配列しｙ0の適切な値の識別を容易にするような適切な表現を与えることもできる。これらの方法のどれか１つを座標に適合させることもできる。
【００８６】
これらの技術は、楕円曲線を用いる暗号化に特に適してはいるが、任意の代数曲線と共に用いることが可能であり、曲線上の点の座標が手員層されなければならない誤り訂正コーディングなど、別の分野にも応用できる。
【００８７】
従って、有限体ＧＦ2mの中の楕円曲線を用い、また、正規基底表現を用いることにより、楕円曲線を用いた暗号化に必要な計算を効率的に実行することが可能になる。これらの演算は、ソフトウェアにおいてもハードウェアにおいても実現することができ、計算の構成を、ハードウェアにおいて実現された有限体の乗算子（multiplier）を用いて、特に効率的にすることができる。
【００８８】
本発明は、従って、暗号化方法及びシステムに関係し、特に、楕円曲線暗号化方法及びシステムに関係する。そこでは、有限体の元が、プロセッサにおいて、効率的な態様で乗算される。本発明の暗号化システムは、適切にプログラムされた汎用コンピュータなどの任意の適切なプロセッサによって構成することができる。
【図面の簡単な説明】
【図１】データ通信システムの概略図である。
【図２】暗号化／復号化システムの概略図である。
【図３】点の整数倍の計算のための流れ図である。
【図４】ｙ座標を取り除くことを示す流れ図である。
【図５】楕円曲線署名の確認への本発明の実施例の別の応用例を示している。
【図１】
0004306829.tif 000006
【図２】
0004306829.tif 000007
【図３】
0004306829.tif 000008
【図４】
0004306829.tif 000009
【図５】
0004306829.tif 000010