(57)【特許請求の範囲】
【請求項１】
楕円曲線点Ｑ（ｘ，ｙ）にスカラーｋを乗じて点ｋＱを提供する方法であって、前記方法は、暗号化プロセッサを含む計算装置によって実行され、
前記方法は、前記計算装置が、
ａ）楕円曲線上のすべての点Ｑ（ｘ，ｙ）についてψ（Ｑ）＝λＱである自己準同形写像ψが存在するように、有限体Ｆの上の次数ｎの楕円曲線を選択するステップであって、λは整数である、ステップと、
ｂ）成分ｋｉと前記整数λの組合わせとしてのｋ＝Σｋｉλｉ  ｍｏｄ  ｎの形式の前記スカラーｋの表現を確立するステップと、
ｃ）前記表現と前記点Ｑを組み合わせて、ｋＱに対応するｋ０Ｑ＋ｋ１ψ（Ｑ）＋・・・の形式の倍数の複合表現を形成するステップと、
ｄ）ｋＱの前記複合表現から前記点ｋＱに対応する値を算出するステップと
を実行することを含む、方法。
【請求項２】
前記成分ｋｉの各々が、前記スカラーｋよりも短い、請求項１に記載の方法。
【請求項３】
前記計算装置によって、前記成分ｋｉがまず選択され、その後組み合わされて前記スカラーｋが提供される、請求項１に記載の方法。
【請求項４】
前記計算装置によって、前記成分ｋｉがランダムに選択される、請求項１に記載の方法。
【請求項５】
前記表現がｋ０＋ｋ１λの形式である、請求項４に記載の方法。
【請求項６】
前記スカラーｋが所定の値を有し、前記成分ｋ０およびｋ１が前記スカラーｋの２分の１のサイズを有する、請求項１に記載の方法。
【請求項７】
前記計算装置によって、前記倍数ｋＱの前記値が、同時多重加算を使用して算出され、前記同時多重加算は、同時多重べき乗に類似しており、同時多重べき乗における乗算演算が加算演算で置き換えられたものである、請求項３に記載の方法。
【請求項８】
前記計算装置によって、前記同時多重加算において使用される一群の項Ｇｌが事前に算出される、請求項７に記載の方法。
【請求項９】
前記計算装置によって、前記体Ｆの短基底ベクトル（ｕ０，ｕｉ）を得て、ベクトルｖを（ｋ，０）として指定し、ｖを正規直交基底から（ｕ０，ｕｉ）基底に変換し、前記ベクトルｖを表す分数ｆ０およびｆ１を得て、前記分数をｋに適用しベクトルｚを得て、ｋＱの前記複合表現における効率的な等価物ｖ’を算出することによって、前記成分ｋｉが得られる、請求項６に記載の方法。
【請求項１０】
秘密鍵および公開鍵ｋＱを提供する整数ｋを有する鍵対を楕円曲線の暗号システムにおいて生成する方法であって、Ｑは前記曲線上の点であり、前記方法は、暗号化プロセッサを含む計算装置によって実行され、
前記方法は、前記計算装置が、
ａ）楕円曲線上のすべての点Ｑ（ｘ，ｙ）についてψ（Ｑ）＝λＱである自己準同形写像ψが存在するように、有限体Ｆの上の楕円曲線を選択するステップであって、λは整数である、ステップと、
ｂ）成分ｋｉと前記整数λの組合わせとしてのｋ＝Σｋｉλｉ  ｍｏｄ  ｎの形式の前記鍵ｋの表現を確立するステップであって、ｎは前記楕円曲線上の点の数である、ステップと、
ｃ）前記表現と前記点Ｑを組み合わせて前記公開鍵ｋＱに対応するｋ０Ｑ＋ｋ１ψ（Ｑ）＋・・・の形式の倍数の複合表現を形成するステップと、
ｄ）ｋＱの前記複合表現から前記公開鍵ｋＱに対応する値を算出するステップと
を実行することを含む、方法。
【請求項１１】
前記成分ｋｉの各々が、前記整数ｋよりも短い、請求項１０に記載の方法。
【請求項１２】
前記計算装置によって、前記成分ｋｉがまず選択され、その後組み合わされて前記整数ｋが提供される、請求項１１に記載の方法。
【請求項１３】
前記計算装置によって、前記成分ｋｉがランダムに選択される、請求項１２に記載の方法。
【請求項１４】
前記表現がｋ０＋ｋ１λの形式である、請求項１３に記載の方法。
【請求項１５】
前記整数ｋが所定の値を有し、前記計算装置によって、前記成分ｋ０およびｋ１が前記整数ｋの２分の１のサイズを有するように選択される、請求項１０に記載の方法。
【請求項１６】
前記計算装置によって、前記倍数ｋＱの前記値が、同時多重加算を使用して算出され、前記同時多重加算は、同時多重べき乗に類似しており、同時多重べき乗における乗算演算が加算演算で置き換えられたものである、請求項１２に記載の方法。
【請求項１７】
前記計算装置によって、前記同時多重加算において使用される一群の項Ｇｌが事前に算出される、請求項１６に記載の方法。
【請求項１８】
前記計算装置によって、前記体Ｆの短基底ベクトル（ｕ０，ｕｉ）を得て、ベクトルｖを（ｋ，０）として指定し、ｖを正規直交基底から（ｕ０，ｕｉ）基底に変換し、前記ベクトルｖを表す分数ｆ０およびｆ１を得て、前記分数をｋに適用しベクトルｚを得て、ｋＱの前記複合表現における効率的な等価物ｖ’を算出することによって、前記成分ｋｉが得られる、請求項１５に記載の方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線を利用して暗号システムで計算を実行する方法に関する。
【０００２】
【従来の技術】
公開鍵データ通信システムを使用して一対の通信者の間で情報を転送することができる。交換される情報の少なくとも一部は、送信側により所定の演算によって暗号化され、受信側は、送信側の演算に対して相補的な演算を実行してこの情報を復号することができる。
【０００３】
各通信者は、秘密鍵と、秘密鍵に数学的に関係づけられた公開鍵とを有する。この関係は、公開鍵の知識から秘密鍵を特定することができないような関係である。各鍵は、転送すべきデータを暗号化するために、あるいはデータが真正であることを検証できるように署名を添付するために、データの転送時に使用される。
【０００４】
暗号化の場合、一方の通信者は、受信側の公開鍵を使用してメッセージを暗号化し、受信側に送信する。次いで、受信側は秘密鍵を使用してメッセージを復号する。
【０００５】
一方の当事者の公開鍵を他方の当事者の秘密鍵と組み合わせることによって共通鍵を生成することもできる。このような場合には通常、各当事者の長期鍵が破られるのを回避するため、通信セッションごとに新しい秘密鍵およびこれに対応する公開鍵が生成され、これらの鍵は通常、セッション鍵または短命鍵と呼ばれる。
【０００６】
したがって、メッセージの交換および公開鍵の生成では、暗号化システムZ*pにおいて整数mod p（pは素数）の有限体を利用する際に指数演算を伴い、あるいはシステムが楕円曲線を利用する際に同様な点乗算演算を伴う相当量の計算が行われる。楕円曲線システムでは、秘密整数ｋを生成し、シード点Ｑで点乗算を実行して短命公開鍵kQを形成することによって、短命鍵対が得られる。同様に、共通短命セッション鍵を生成する場合は、公開鍵k3Q、すなわち、曲線上の点に他方の通信者の秘密整数kbを乗じる必要があり、したがって、この場合も点乗算が必要になる。
【０００７】
メッセージに署名する場合にも、送信側が自分の秘密鍵をメッセージに適用することを除いて、同様な手順が使用される。この場合、任意の受信側が、送信側の公開鍵を使用してメッセージを復元し検証することができる。
【０００８】
このような方式を実施するための様々なプロトコルが存在しており、そのうちのいくつかは広く使用されている。しかし、それぞれの場合に、送信側は転送すべき情報に署名するために計算を実行する必要があり、受信側は、署名された情報を検証するために計算を実行する必要がある。
【０００９】
典型的な実行形式において、署名成分は以下の形式を有する。
s = ae + k (mod n)
上式で、楕円曲線暗号化システムにおいて、
Ｐは、基本曲線上の、システムの定義済みパラメータである点であり、
ｋは、短期秘密鍵またはセッション鍵として選択されたランダム整数であり、
R = kPは、これに対応する短期公開鍵であり、
ａは、送信側の長期秘密鍵であり、
Q = aPは、これに対応する送信側の公開鍵であり、
ｅは、メッセージｍおよび短期公開鍵Ｒの、SHA-1ハッシュ関数などの安全ハッシュであり、および
ｎは曲線の次数である。
【００１０】
送信側は、ｍ、ｓ、およびＲを含むメッセージを受信側に送信し、署名は、Ｒに対応すべき値R1 = (sP‐eQ)を算出することによって検証される。算出された値が対応する場合、署名は検証されたことになる。
【発明が解決しようとする課題】
【００１１】
検証を実行する場合、点乗算を計算し、それぞれ計算が複雑なsPおよびeQを得る必要がある。この場合、受信側が適切な計算力を有する場合には、特に問題はないが、セキュアトークン・アプリケーションや「スマート・カード」アプリケーションのように受信側の計算力が限られている場合、このような計算によって検証プロセスに遅延が生じる。
【００１２】
したがって、キー生成プロトコルおよび署名プロトコルは、大量の計算を必要とする場合がある。暗号化が普及するにつれて、より高速であり、スマート・カードや無線装置に見られるように限られた計算力を活用する暗号化システムを実現する要求が高まっている。
【００１３】
楕円曲線暗号化（ECC）は、この計算問題を解決する。ECCでは、鍵および証明書のサイズを縮小することができ、それによって、必要なメモリが低減し、コストが著しく節約される。ECCは、コストを著しく削減することができるだけでなく、次世代アプリケーションにおけるスマート・カードの普及を促進する。また、ECCアルゴリズムによって鍵サイズを縮小することができるが、より大きな鍵を用いる他のアルゴリズムと同じレベルのセキュリティが維持される。
【００１４】
しかし、暗号化装置の低い生産コストを維持しながら情報転送速度を高めるために、依然として、鍵に対する計算をより高速に行う必要がある。
【００１５】
楕円曲線上の点の倍数を算出することは、楕円曲線暗号化で最も頻繁に実行される計算の１つである。このような計算の速度を高める１つの方法は、事前計算された点の倍数のテーブルを使用することである。この技法は、点が事前にわかっているときにさらに有用である。しかし、未知の点の倍数が必要になる場合がある（たとえば、ECDSA検証）。したがって、点乗算を容易にするシステムおよび方法が必要である。
【００１６】
【課題を解決するための手段】
一般に、本発明は、スカラーｋを、成分kiと、基本曲線で自己準同形写像から導かれる整数λとの組合わせとして表す。
【００１７】
この方法は、有限体の上に写像される複素乗算を有する楕円曲線（EC）が与えられた場合、複素乗算写像と点Ｑにλを乗じることが等しくなる二次方程式の解λが存在する、という考えに基づく方法である。λを整数とみなしてEC乗算を実行するのと比べて、複素乗算写像を介してλQを算出する方がコストが低いことが多い。実際には、他のスカラー（λ以外）による点乗算が必要になる。乗算写像を使用して点の他の倍数を算出できることも示す。
【００１８】
本発明によれば、楕円曲線点Q(x, y)にスカラーｋを乗じる速度を高める方法であって、
楕円曲線上のすべての点Q(x, y)についてψ(Q) = λ・Qである自己準同形写像ψが存在するように、有限体Ｆの上の楕円曲線を選択するステップと、
スカラーｋのより小さな表現kiと写像ψとの組合わせを使用して楕円曲線点Ｑのスカラー倍数を算出するステップとを含む方法が提供される。
【００１９】
本発明の好ましい実施形態のこれらおよび他の特徴は、添付の図面が参照される以下の詳細な説明でより明らかになろう。
【００２０】
【発明の実施の形態】
以下の説明では、同じ符号は各図面中の同じ構造物を指す。図１を参照すると、データ通信システム10は、通信チャネル16によって接続され、送信側12および受信側14として指定された一対の通信者を含む。各通信者12、14は、デジタル情報を処理し、この情報を後述のようにチャネル16を通して送信する準備をすることのできる暗号化プロセッサ18、20をそれぞれ含む。プロセッサ18、20は、プロセッサに組み込まれた集積回路で実現するか、あるいは汎用プロセッサと共に所定のプロトコルを実施するようにデータキャリア上に符号化された命令として実現することができる。図をわかりやすくするために、通信者12は、比較的限られた計算力を持つ専用プロセッサ18を有するスマート・カードの形であると仮定する。好ましくは、プロセッサ20は、チャネル16によってカードと通信する中央サーバであり、チャネル16は無線通信チャネルである。
【００２１】
暗号化プロセッサ18は、ECCの楕円曲線暗号化システムを実現し、また暗号化プロセッサ18の機能の１つは、整数であるｋと、基本楕円曲線上の点であるＱとを暗号化方式における鍵対k、kQとして使用できるように、k・Qの形の点乗算を実行することである。上記で指摘したように、楕円曲線点とスカラー値の乗算などの暗号化計算はコストがかかる。
【００２２】
楕円曲線点Q(x, y)のスカラー乗算の速度を高める方法は、図２に示されており、全体的に符号50によって示されている。本発明のアルゴリズムは、プロセッサ12がたとえば、特定の種類の楕円曲線に関してメッセージに署名しメッセージを検証する速度を高める。この方法は、Fq（qは素数べき乗）として例示された有限体上の楕円曲線Ｅに関する以下の一般的な数式が与えられ、
y2 + a1xy + a3y = x3 + a2x2 + a4x + a6    （１）
自己準同形写像ψが存在し、楕円曲線上のすべての点Q(x, y)点についてψ(Q) = λ・Qである場合、点Ｑと整数ｋとの乗算は、ｋのより小さな表現kiと写像ψとの組合わせを利用することによって速度を高めることができるという考えに基づく方法である。写像ψは、kQに関する後の計算で使用できる群要素およびそれらの組合わせを事前に算出することも可能にする。
【００２３】
次に図２を参照すると、楕円曲線上の点乗算の速度を高める一般的な実施形態のフローチャートが符号50で示されている。まずシステム・パラメータが選択される。最初のステップとして、ある特性を有する基本楕円曲線Ｅが選択される。本発明の第１の実施形態では、一般化された楕円曲線（１）を以下の形式で表すことができる。
E: y2 = x3 + b mod p（Ｐは素数）    （２）
【００２４】
まず、γ∈Fp（Fpはすべての整数mod pから成るサイズｐの体である）であり、かつγ3 ≡ 1 mod p（１の立方根）である数γが存在するように係数ｐを求めることができる。たとえば、p = 7である場合、23 mod 7 = 1であるので、γ = 2である。このようなγはすべてのｐに対して存在するわけではなく、したがって、ｐの値を選択する際にはこのことを考慮しなければならない。通常、適切な暗号強度を得るには、選択されるｐの長さが少なくとも160ビットであるべきである。
【００２５】
曲線Ｅが選択された後、写像関数ψが求められる。写像関数ψ: (x,y)→(γx,y)は、曲線上の点のある組を曲線上の点の別の組に写像するに過ぎない。楕円曲線Ｅ上の当該のすべての点Q(x, y)点についてψ(Q) = λ・Qになるような整数λが存在する。この整数λは、λ3 ≡ 1 mod nであることに留意することによって求めることができる。この場合、ｎは、Fpの上にある楕円曲線Ｅ上の点の数、すなわち、E(Fp)上の点の数である。λ3 ≡ 1のλに複数の解が存在する場合があるが、写像関数ψを満たす解は１つだけである。γ3 mod p = 1であるので、Ｑとψ(Q)の両方がＥに関する数式を満足する。したがって、長い計算を実行してλによる乗算の結果を求める代わりに、λによる乗算を非常に効率的に実行できるように写像関数の結果を使用して非常に効率的にこれを行うことができる。
【００２６】
シード点Ｑが選択され、52に示すように、製造時に、システム・パラメータＥ、ｐ、Ｑ、λ、ψ(Q)、およびγが、暗号化プロセッサ18によって使用できるようにカード12に記憶される。暗号化、鍵一致、署名などの暗号化手順を実施するには、短命秘密鍵ｋとして使用される整数ｋを選択し、対応する公開鍵kQを生成する必要がある。
【００２７】
ｋの値は次式ように表すことができる。
k = (k0 + k1λ) mod n    （３）
【００２８】
上式で、ｎはE(Fp)上の点の数であり、k0およびk1は整数である。この場合、点k・Qは次式のようになる。
k・Q = (k0Q + k1λQ) mod n    （４）
【００２９】
いくつかの暗号演算の場合、ｋの値をランダムに選択することができ、このような場合、ｋを選択するのではなく、符号ビットを含まない長さ[log2(n)]/2の、k0およびk1の値をランダムに選択し（すなわち、k1の長さとして、長さｋの少なくとも２分の１の長さが選択される）、次いで数式（３）を使用してｋの値を算出することが可能である。図２に54で示すようにk0、k1の値を選択した後、Menezesらによって「Handbook of Applied Cryptography」（HAC）に記載された「Simultaneous Multiple Exponentiation」（アルゴリズム14.88）に類似しており、56に示されているアルゴリズムを使用して数式（４）の右辺を高速に計算することができる。都合上、このアルゴリズムを以下に再現する。加群において、べき乗が加算に類似しており、したがって、このアルゴリズム内の乗算を加算で置き換えると以下の手順が得られる。
【００３０】
アルゴリズム１  同時多重加算
入力：群要素g0, g1, … gl-1および負でないｔビット整数e0, e1, … el-1。
出力：g0e0 + g1e1 + … + gl-1el-1。
ステップ１。事前計算。ｉが０から(2l‐1)に対して、
【数２】
0004662577.tif 000002
上式で、i = (il-1 . . . i0)2である。
ステップ２。A←0
ステップ３。ｉが１からｔに達するまで、以下のことを実行する。
A←A+A、A←A+Gl
ステップ４。（Ａ）を返す。この場合、A = g0e0 + g1e1 + … + gl-1el-1
【００３１】
このアルゴリズムを数式（４）に適用すると、２つの群要素g0、g1、すなわちＱおよびλQがあり、したがって、２つの整数e0、e1、すなわちk0、k1があることがわかる。このアルゴリズムでは、いくつかの値を事前に算出することができ、最初にGiが算出される。l = 2によってGiを事前に算出した結果をテーブル１（表１）に示す。
【表１】
0004662577.tif 000003
【００３２】
点加算：（Q + ψ(Q)）を実行して点を作成した後、算出済みの要素をテーブル１に記入してテーブル２（表２）を作成することが可能である。図２のステップ58に示すように、これらの要素を事前に算出しメモリに記憶することができる。
【表２】
0004662577.tif 000004
GIiを求め、したがって、60に示すようにI1からItを求めないかぎり、アルゴリズムのステップを実行することはできない。kiの２進表現を使用して概念行列または組合わせテーブルを作成することができる。たとえば、k0 = 30でありk1 = 10である場合、k0からk1の２進表現内の最大ビット数が５であるのでｔは値５を有する。k0からk1の２進表現で作成された概念行列をテーブル３に示す。Iiは、第１の行が最下位ビットを含み、第２の行が次の下位ビットを含み、以下同様であるｉ番目の列に表された数によって決定される。したがって、テーブル３（表３）から、I1 = I2 = (11) = 3、I3 = (01) = 1、I4 = 3、およびI5 = 0であることがわかる。
【表３】
0004662577.tif 000005
【００３３】
このアルゴリズムを完了するのに必要なすべての成分を得ることができ、62に示すようにステップ３の反復が行われる。
【００３４】
最初はA←Oであり、ｉは１に設定される。Ii = I1であり、これはテーブル３から１に等しい。したがって、GI1はG1であり、これはテーブル２からＱである。したがって、I = 1の場合の反復によるＡの値はO + Q = Qである。
【００３５】
i = 2である次の反復の場合、Ａの初期値はＱであり、したがって、A← Q+Q = 2Qであり、テーブル３からIi = I2 = 3である。したがって、GI2はテーブル３からG3に等しく、すなわち、Q + ψ(Q)である。
【００３６】
したがって、A + GIiは2Q + Q +ψQ = 3Q +ψQと算出される。
【００３７】
反復は、５回目の反復まで、すなわち、koq = k,λQの値、すなわちkQが算出されるまで、テーブル４（表４）に記載されたｉの値ごとに継続される。
【表４】
0004662577.tif 000006
【００３８】
各反復では、点倍加（A+A）および点加算（A+GIi）が必要である。ただし、場合によっては、GIiの値はＯであり、この場合、計算量が削減される。
【００３９】
したがって、この方法では、max{log2(ki)}に等しい数の点倍加と、ほぼ同数の点加算が必要であることがわかる。点加算の数は、ウィンドウ技法（アルゴリズム14.85 HAC）および指数再符号化技法を使用して削減することができる。ｉおよびGiの値を事前に算出することができるので、事前に算出された適切な要素Giをテーブル２から検索することによって点加算を容易に実行することができる。kPが算出された後、チャネル16を介した暗号化伝送または署名伝送において通信者12の短命公開鍵としてこのkPを使用することができる。
【００４０】
簡単に言えば、暗号化やDH署名などの暗号化演算の場合、整数ｋが必要であり、対応する公開鍵kQが算出される。それぞれ、長さｎの２分の１の長さを有する、値k0およびk1がランダムに選択され、適切なアルゴリズムを使用して項k0Q = k1λQが生成される。ｋをこのように選択すると、この方法は、ｋ自体をランダムに生成するのと同程度に安全であると思われる。もちろん、効率を向上するためにより少ないビット数のkiを選択することが可能である。
【００４１】
上記の技法において、k = k0 + k1λを書き込み、同時に組み合わせる方法によって、同時多重加算アルゴリズムの速度が高められる。k = k0 + k1λを書き込む技法は、スカラー乗算技法、すなわち、ワインディング、組合わせなどと共に使用することもでき有利である。
【００４２】
いくつかの写像ψでは、３つ以上の下位要素ｋ（sub k）を使用することも可能である。いくつかの写像ψでは、k = k0 + k1λ + k2λ2を書き込み、同時多重加算アルゴリズムを適用することによってｋの値を算出することができる。
【００４３】
本発明の第２の実施形態では、一般化された楕円曲線式（１）の異なる形式、すなわち、
y2 = (x3 ‐ ax) mod p    （５）
が使用される。この場合も、ｐは少なくとも160ビットを有する素数である。この種の曲線の場合、γに必要な特性が異なる。この場合、γ2 = ‐1 mod pになるような値を求める必要がある。γの特性を変更するには、異なる写像関数ψ’を使用する必要がある。この実施形態では、写像は形式ψ’：(x, y) → (‐x, γy)をとる。(x, y)が曲線上にある場合はψ’(x, y)も曲線上にある。この場合、λ4 ≡ 1 mod n（ｎはこの場合も、E(Fp)上の点である）、したがってλを算出することができる。写像ψ’(Q) = λ・Qは前述のように実行され、この場合も、この曲線に対してλによる乗算を非常に効率的に行うことができる。この実施形態のｋに関する数式は、第１の実施形態と同じであり、次式によって表される。
k = (k0 + k1λ) mod n    （６）
この数式は、前の実施形態と同じであり、２つの群要素のみを有する。したがって、アルゴリズム１の群要素ＱおよびQ+ψ’(Q)を使用して点k・Qを算出することができる。この計算では、max{log2(ki)}に等しい数の点倍加と、同様な数の点加算が必要である。前述のように、ウィンドウ技法および指数再符号化技法を使用して点加算の数を削減することができる。
【００４４】
この方法は、効率的に算出できる自己準同形写像ψが存在するかぎり、他の楕円曲線にも適用することができる。
【００４５】
上記の実施形態は、ｋをランダムに選択することができ、したがって、k0およびk1を選択することができるものと仮定し、ｋを求めている。ｋを選択することが可能な暗号化プロトコルの場合、まず、k = (k0 + k1λ) mod nになるようにｋの所与の値から所望の「短い」形式のk0、k1を求める必要がある。場合によっては、３つ以上のｋを使用することができ有利である。
【００４６】
上述の実施形態でわかるように、事前に点がわかっているときは、テーブルを作成して乗算の速度を高めることができる。しかし、未知の点の倍数が必要になる場合があり（たとえば、これはECDSA検証で起こる可能性がある）、その場合、与えられたｋの値をとり、次いでkiの適切な表現を決定する必要がある。
【００４７】
したがって、第３の実施形態では、システム・パラメータおよび値ｋが与えられ、点Ｑ、必要な倍数ｋ、および複素乗算倍数λが既知である。所定のｋの値から「短い」kiを求める必要がある。これを行う方法を以下に説明し、図３のフローチャートに示す。（ｋを必要としない）事前計算として、aiおよびbiがｎよりも小さな数になるような２つの関係を算出する。
a0 + b0λ = 0 mod n
a1 + b1λ = 0 mod n
aiおよびbiはできるだけ小さいことが好ましいが、本発明の方法は、aiおよびbiが最小限でないときでも有利である。aiおよびbiが共に小さな対aiおよびbiは、小さなユークリッド長を有するベクトルuiとみなすことができる。通常、後述の方法では、最初のｋのサイズの２分の１の表現を有するk0およびk1が生成される。
【００４８】
本実施形態では、事前に算出された短いベクトル表現を使用して以下の形式の数式を得ることによって、kQを効率的に算出することができる。
k0Q + λk1Q
【００４９】
これは、事前に算出されたベクトルを使用して、ｋの知識を必要としない分数f0およびf1を導くことによって行われる。ベクトルｚは、分数f0およびf1とｋを組み合わせることによって生成される。ベクトルｚを使用して、v’ = (v0’, v1’)である第２のベクトルv’が算出され、kQの値が、
【数３】
0004662577.tif 000007
として算出される。この解を得る方法を以下に詳しく説明する。
【００５０】
小さなaiおよびbiを作成する場合、L3、すなわち、短い基底ベクトルが直接得られる格子基底削減アルゴリズム（HAC、118ページ）を利用することが可能である。しかし、この好ましい実施形態では、簡単な拡張ユークリッド・アルゴリズムが対（n, λ）に対して使用される。（n, λ）に対する拡張ユークリッド・アルゴリズムにより、ｉに応じてriの表現（たとえば、ビット長）が小さくなり、ciおよびdiの表現が大きくなる線形組合わせcin + diλ = riが作成される。
【００５１】
拡張ユークリッド・アルゴリズムを使用した結果として得られた|(di, ri)|の２つの最小値が保存される。これらのベクトルのサイズが、平方ユークリッド基準|(di, ri)| = di2 + ri2を用いて測定される。これらの最小関係の項は、
0004662577.tif 000008
および
0004662577.tif 000009
として示され、通常、アルゴリズムの中央で得られる。最小関係が保持されない場合でも、この方法は、部分最適関係により、依然として点倍数の計算において有利である。
【００５２】
aiおよびbiの値は、すべて事前に算出することのできる
0004662577.tif 000010
および
0004662577.tif 000011
を定義することによって作成することができる。
【００５３】
次のタスクは、倍数ｋの小さな表現を求めることである。
【００５４】
a0、b0およびa1, b1の計算が与えられた場合、u0 = (a0, b0)でありu1 = (a1, b1)であるベクトルu0, u1を指定することが可能である。これらのベクトルはai + biλ = 0 (mod n)を満たす。群要素Ｑにベクトルv = (v0, v1)を乗じることは(v0 + v1λ)Qとして定義される。ai + biλ = 0 (mod n)であるので、任意の群要素Ｒについてu0R = u1R = 0が成立する。したがって、任意の整数z0およびz1のの場合、任意の群要素Ｒについてv’R = (v ‐ z0u0 ‐ z1u1)Rが成立する。
【００５５】
整数z0およびz1としては、ベクトルv’ = v ‐ z0u0 ‐ z1u1ができるだけ小さな成分を有するような整数が選択される。この場合も、この方法は、v’の成分が小さい場合に利点を有し、該成分が必ずしも最小限でない場合でも利点を有する。
【００５６】
適切なz0およびz1は、vの基底を正規直交基底{u0, u1}に変換することによって算出される。基底間の変換では行列乗算が行われる。ベクトルv = (v0, v1)を{u0, u1}基底から標準基底{(1, 0), (0, 1)}に変換する場合、次式が成立する。
【数４】
0004662577.tif 000012
他方の方向、すなわち、正規直交基底{(1, 0), (0, 1)}から(u0, u1)基底に変換する場合、乗算は単にＭの逆数によって行われる。
【数５】
0004662577.tif 000013
【００５７】
ベクトルv = (k, 0)がゼロ成分を有するので、逆数（Ｍ）の下の行は必要とされず、したがって、{u0, u1}に変換する場合に必要なのは次式の分数だけである。
【数６】
0004662577.tif 000014
および
【数７】
0004662577.tif 000015
【００５８】
分数f0およびf1の演算を乗算のみで行うことができるように、これらの分数を十分な精度に事前に算出しておくことができる。これらの分数をもたらす計算がｋに依存せず、したがって、楕円曲線がシステム・パラメータとして選択される際にこれらの分数を１度算出することができ、各ｋごとに再計算する必要はない。同様に、ベクトルv、u0、およびu1を事前に算出し記憶することができる。
【００５９】
ｋの値が選択されるか、あるいは求められた後、まず、ｚが(z0, z1) = (round(kf0), round(kf1))として定義されるz = (z0, z1)を計算することによってkQの値を算出することができる。ｚの近傍の他のベクトルも有用であり、したがって、丸めを床関数または天井関数、あるいは何らかの他の近似で置き換えることができる。
【００６０】
適切なｚが求められた後、v’ = (v0’, v1’) = v ‐ z0u0 ‐ z1u1によってv(k, 0)の効率的な等価物が算出される。「効率的な等価物」の句は、v’P = vPおよびv’が小さな係数を有するようなベクトルv’を意味する。この場合、値kQはv0’Q + v1’λQとして算出される。この値は、上述のように同時点加算を使用して算出することができ、上記で説明し、かつH.A.C.14.7の627ページに記載されているように非隣接形式（NAF）再符号化を使用することによってより高い効率を得ることができる。したがって、ｋが所定の値である場合でも、k0およびk1の値を算出し写像関数と共に使用してkQの値、したがって、鍵対k、kQを得ることができる。
【００６１】
ｋを３つの部分k = k0 + k1λ + k2λ2に分離する場合、L3行削減によって、次式のような小さなベクトルを得ることができる。
【数８】
0004662577.tif 000016
【００６２】
二次元の場合と同様に小ベクトル等価物（三次元行）を得ることができる。
【００６３】
これらの方法を使用してk・Qの値を求めると、暗号化プロセッサ12によって必要とされる処理能力が大幅に低減される。また、このような反復計算が行われる速度が高められ、それによって、情報を転送するための時間が短縮される。
【００６４】
当然のことながら、スカラー倍数ｋが短縮成分k = k0 + k1λ + k2λ2 + . . . km-1λm-1で表された後、同時多重加算アルゴリズムの代わりに、あるいはこのアルゴリズムと共に、効率的な楕円曲線スカラー乗算を行うための他の方法を使用することができる。このような方法には、ウィンドウ技法（固定およびスライド）、組合わせ技法、ビット再符号化技法、およびこれらの技法の組合わせが含まれる。
【００６５】
特に有益なある技法では、乗算の一成分、たとえばk0に関して作成されたテーブルを他の成分k1などに再使用することができる。これは、必要に応じて写像γを適用することにより、算出されたテーブル要素を変換することによって行われる。
【００６６】
他の例として、ｋをk = k0 + k1λ + k2λ2として再設定することができ、ｋがｍビットを有し、kiが約m/3ビットを有する実施形態について以下に説明する。
【００６７】
成分kiは、求められた後、２進表現から、より少ない非ゼロ・ビットを有する符号付き２進表現に再符号化することができる。この再符号化は、表現ki内のあらゆる１ビットまたは‐1ビットが符号付き２進文字列内で他の非ゼロに隣接しないような非隣接形式（NAF）をとることができる。
【００６８】
各kiが再符号化された後、kiλiPの計算を助けるためにテーブルを作成することができる。
【００６９】
NAFウィンドウ・テーブルは、λiPのある短ビット長倍数を事前に算出するためのテーブルである。このウィンドウの幅によってテーブルのサイズが決定される。kiが、隣接する非ゼロを有さないように再符号化されているので、奇数ウィンドウ幅が適切である。３ビット幅NAFウィンドウは以下のものを含む。
【数９】
0004662577.tif 000017
【００７０】
再符号化kiは、このようなウィンドウを連結し、必要に応じてゼロを充填することによって作成される（H.A.C.、616ページ）。
【００７１】
あらゆる非ゼロ・ビットではなく、発生するあらゆるウィンドウごとにのみEC点を加算または減算するだけでよいので、このテーブルを使用することによって必要な加算数を削減することができる。
【００７２】
したがって、まず、この技法はk0Pの計算に適用される。
【００７３】
k0Pの計算のために作成されたテーブルは、演算子γを使用してテーブル要素にψ写像が写像される場合にkiλP計算に適用することができる。同様に、k0P用に作成されたテーブルを使用するが、テーブル要素にγ2を写像することによって、k2λ2Pの速度を高めることができる。
【００７４】
スライド・ウィンドウ技法を該成分に適用する際に、実行する必要があるのは１組の倍加だけである。
【００７５】
好ましい実施形態のこの例を示すために、以下の例を使用する。
【００７６】
k = [101101011101]2 + [111010101101]2λである場合、
以下の再符号化を行う。
k = [10-100-10-100-101] + [1000-10-10-10-101]λ
= k’0 + k’1λ
【００７７】
1・P、[10-1]・P、[101]・Pを含む、Ｐに関する３ビット・ウィンドウ・テーブルが事前に算出される。この場合、２回のEC加算および２回のEC倍加が必要である。
【００７８】
この後、テーブルの要素を加算／減算することによって、kPを以下のように算出することができる。
kP = [10-100-10-100-101]P + [1000-10-10-10-101]・λP
これは、累算器Ａを使用して以下のように行うことができる。
A←0  ；初期設定
A += ψ(1・P)  ；k0’の上位ビットを消費する。
A ← 2A  ；Ａを倍加する。
A ← 2A
A ← [10-1]P  ；k0’の上位３ビットを消費する。
A ← 24A
A‐= [101]ψP  ；k1’の３ビット・ウィンドウを消費する。
A ← 2A  ；Ａを倍加する。
A‐= [101]P  ；k1’の３ビットを消費する。
A ← 24A
A‐= [101]ψP  ；k1’の３ビットを消費する。
A ← 22A
A‐= [10-1]P  ；k0’の最後のビットを消費する。
A + =ψP  ；kPを生成する。
【００７９】
簡単に言えば、前述の技法は以下のとおりである。楕円曲線Ｅおよび自己準同形写像ψが与えられた場合、すべての点Q∈EについてλQ = ψ(Q)になるような対応する整数λが存在する。整数ｍを選択し、同等な数ｍの「短基底ベクトル」b1, b2, . . . , bmを算出する。このような基底ベクトルはそれぞれ整数に対応し、そのような整数はそれぞれ、点の数n = #E(Fpm)（すなわち、点の数）で除することができる。次に、整数ｋ（0 < k < n）が与えられた場合、kiとして「短い」ベクトルが選択されるk = Σki・λiと書くことができる。これは、b1, b2, …, bmによって生成された格子内の（ｋを表す）あるベクトルと近傍のベクトルとの差を求めることによって行われる。
【００８０】
以下の実施形態では、複合体の上に画定された楕円曲線に前述の技法（自己準同形写像および基底変換および「Shamir’s trick」）を適用することについて明白に説明する。特に、ｐが奇素数である曲線E(Fpm)への適用について説明する。以下の実施形態ではこのような曲線に対する技法を例示する。
【００８１】
この技法について、写像ψがフロベニウス写像ψ(x, y) = (xp, yp)であり、A, B∈FpであるE’A,B(Fpm)が使用される場合において説明する。
【００８２】
この場合、フロベニウス写像がψ2 ‐ tψ + p = 0を満たし、t = p + 1‐#E(Fpm)であることがわかっている。
【００８３】
したがって、λ2 ‐ tλ + p = 0 mod nであり、またλ2+i ‐ tλ1+i + pλi = 0 mod nである。
【００８４】
以下のベクトルが、ベクトル空間Qn空間のｍ個の「短」基底ベクトルで構成されている。
【数１０】
0004662577.tif 000018
したがって、このような曲線に対するk・Qを計算する場合、ベクトルb1, b2, … bmおよび前述の技法を使用することができる。
【００８５】
上記の実施形態では、k, λQをψ(kQ)から得ることができ、写像が加算よりも効率的であることが理解されよう。
【図面の簡単な説明】
【図１】  通信システムの概略図である。
【図２】  本発明の第１の実施形態を実施する各ステップを示すフローチャートである。
【図３】  図２の方法を実施するために必要なパラメータを与えるステップを示すフローチャートである。
【図１】
0004662577.tif 000019
【図２】
0004662577.tif 000020
【図３】
0004662577.tif 000021