(57)【要約】  要素（ｇｊ）をマルチ累乗（Πｉ＝１ｄｇｉｅｉ）またはマルチスカラー乗算（Σｉ＝１ｄｅｉｇｊ）するための方法であって、それぞれの場合で少なくとも１つのべき指数またはスカラー（ｅｉ）、特に整数のべき指数またはスカラーを使用し、べき指数またはスカラーは、それぞれの場合で最大ビットレート（ｎ）またはビット長を有し、特に、要素（ｇ）を累乗（ge）またはスカラー乗算（ｅｇ）するために、少なくとも１つのべき指数またはスカラー（ｅ）、特に整数のべき指数またはスカラーを使用し、べき指数またはスカラーは、それぞれの場合で最大ビットレートｎまたはビット長を有し、要素（ｇｉ；ｇ）は、少なくとも１つの群（Ｇ）、例えばアーベル群から得られ、アーベル群は、―（マルチ）累乗の場合では、特に乗法的に表記され、―（マルチ）スカラー乗算の場合では、特に加法的に表記される方法を、再符号化されたべき指数またはスカラー（ｅｉ）のための記憶スペースに関する要件が、例えばスマートカードなどの特に極度に制限された環境であっても、可能な限り減少されるようなやり方で、さらに展開するために、全ての指数（ｇｉｃ）または全ての倍数（ｃｇｉ）を［ａ．１］計算および記憶し、または［ａ．２］少なくとも１つのメモリから検索し、ここで、ｃは許容可能な正の係数であり、［ｂ］各べき指数またはスカラー（ｅｉ）を、特定のビットレート（Ｌ）により定義されるチャンクまたは部分の幅を有する、複数のチャンクまたは複数の部分（ｅｉ，ｋ）に分割し、かつ、［ｃ］チャンクまたは部分（ｅｉ，ｋ）を個別に再符号化する、という方法ステップが提案される。【特許請求の範囲】
【請求項１】
要素（ｇｉ）をマルチ累乗（Πｉ＝１ｄｇｉｅｉ）またはマルチスカラー乗算（Σｉ＝１ｄｅｉｇｉ）するための方法であって、それぞれの場合で、少なくとも１つのべき指数またはスカラー（ｅｉ）、特に整数のべき指数またはスカラーを使用し、前記べき指数またはスカラーは、それぞれの場合で最大ビットレート（ｎ）またはビット長を有し、特に、要素（ｇ）を累乗（ｇｅ）またはスカラー乗算（ｅｇ）するために、少なくとも１つのべき指数またはスカラー（ｅ）、特に整数のべき指数またはスカラーを使用し、前記べき指数またはスカラーは、それぞれの場合で最大ビットレート（ｎ）またはビット長を有し、
前記要素（ｇｉ；ｇ）は、少なくとも１つの群（Ｇ）、例えばアーベル群から得られ、前記アーベル群は、
―（マルチ）累乗の場合では、特に乗法的に表記され、
―（マルチ）スカラー乗算の場合では、特に加法的に表記される方法において、
全ての指数（ｇｉｃ）または全ての倍数（ｃｇｉ）を、
［ａ．１］計算および記憶し、または
［ａ．２］少なくとも１つのメモリから検索し、
ここで、ｃは許容可能な正の係数であり、
［ｂ］各べき指数またはスカラー（ｅｉ）を、特定のビットレート（Ｌ）により定義されるチャンクまたは部分の幅を有する、複数のチャンクまたは複数の部分（ｅｉ、ｋ）に分割し、かつ、
［ｃ］前記チャンクまたは部分（ｅｉ、ｋ）を個別に再符号化する、
という方法ステップを備えることを特徴とする方法。
【請求項２】
前記べき指数またはスカラー（ｅｉ）は、分割された形態ｅｉ＝Σｋ＝０ｒｅｉ，ｋ２ｋＬで表され、ここで、
―ｒは、前記チャンクまたは部分（ｅｉ、ｋ）の数、特に、前記チャンクまたは部分の幅の最大ビットレート（ｎ）およびビットレート（Ｌ）の整数商として定義され、かつ、
―０≦ｅｉ，ｋ＜２Ｌである、
ことを特徴とする請求項１に記載の方法。
【請求項３】
前記チャンクまたは部分の幅（Ｌ）は、
―その上でそれぞれの前記べき指数またはスカラー（ｅｉ）のビットが読まれる窓の幅、特に幅の上限、に対応するパラメータ（ｗ）よりも著しく大きく選択され、かつ
―各べき指数またはスカラー（ｅｉ）の最大長さよりも著しく短く、特に、方法ステップ［ａ．１］および／または［ａ．２］の前に、選択される、
ことを特徴とする請求項１または請求項２に記載の方法。
【請求項４】
―前記（マルチ）累乗の場合には、前記チャンクまたは部分（ｅｉ、ｋ）を再符号化するための方法ステップ［ｃ］は、各べき指数（ｅｉ）の各個別チャンクまたは各個別部分（ｅｉ、ｋ）について：
［ｃ．１］仮変数（ｘ）を、標準化された値、特に、前記群（Ｇ）の前記要素の値１に設定し、１は、前記群（Ｇ）に割り当てられた群演算に対して中立であり、
［ｃ．２］変数（ｋ）を、値ｒ−１，ｒ−２，・・・，０に連続的に設定し、ここで、前記変数（ｋ）の各値ｋ＝ｒ−１，ｒ−２，・・・，０について：
［ｃ．２．ｉ］ｄを、特に前記要素（ｇｉ）に割り当てられたべき指数（ｅｉ）の数に応じて、前記要素（ｇｉ）の数として定義した、インデックス（ｉ）の各値ｉ＝１，２，・・・，ｄについて、
［ｃ．２．ｉ．ａ］前記チャンクまたは部分（ｅｉ、ｋ）を、それぞれの場合において整数の少なくとも１つの有限集合（Ｃ）から得られる少なくとも１つの係数（ｂｉｊ）によって荷重された、２の指数（２ｊ）の合計（Σｊ＝０Ｌｂｉ、ｊ２ｊ）として再符号化し、
［ｃ．２．ｉ．ｂ］２の最大の指数（２Ｌ）に割り当てられた係数（ｂｉ、Ｌ）が、非消滅（non-vanishing）である場合、前記仮変数（ｘ）を、仮変数（ｘ）と、前記２の最大の指数（２Ｌ）の前記係数（ｂｉ、Ｌ）に割り当てられた前記要素（ｇｉ）の指数（ｇｉｂｉ，Ｌ）との積に設定し、
［ｃ．２．ｉｉ］インデックス（ｊ）の各値ｊ＝Ｌ−１，Ｌ−２，・・・，０について、
［ｃ．２．ｉｉ．ａ］前記仮変数（ｘ）を２乗し、
［ｃ．２．ｉｉ．ｂ］前記インデックス（ｉ）の各値ｉ＝１，２，・・・，ｄについて、
前記２の指数（２ｊ）に割り当てられた前記係数（ｂｉ、Ｌ）が、非消滅である場合、前記仮変数（ｘ）を、仮変数（ｘ）と、前記２の指数（２ｊ）のそれぞれの前記係数（ｂｉ、Ｌ）に割り当てられた前記要素（ｇｉ）の指数（ｇｉｂｉｊ）との積に設定する、
というサブステップが実行される、
というサブステップに分割することができ、
―前記チャンクまたは部分（ｅｉ、ｋ）を個別に再符号化する方法ステップ［ｃ］の後に、前記仮変数（ｘ）が返される、
ことを特徴とする請求項１乃至請求項３のいずれかに記載の方法。
【請求項５】
―前記（マルチ）スカラー乗算の場合には、前記チャンクまたは部分（ｅｉ、ｋ）を再符号化するための方法ステップ［ｃ］は、各べき指数（ｅｉ）の各個別チャンクまたは各個別部分（ｅｉ、ｋ）について：
［ｃ．１］仮変数（ｘ）を、標準化された値、特に、前記群（Ｇ）の前記要素の値０に設定し、０は、前記群（Ｇ）に割り当てられた群演算に対して中立であり、
［ｃ．２］変数（ｋ）を、値ｒ−１，ｒ−２，・・・，０に連続的に設定し、ここで、前記変数（ｋ）の各値ｋ＝ｒ−１，ｒ−２，・・・，０について：
［ｃ．２．ｉ］ｄを、特に前記要素（ｇｉ）に割り当てられたスカラー（ｅｉ）の数に応じて、前記要素（ｇｉ）の数として定義した、インデックス（ｉ）の各値ｉ＝１，２，・・・，ｄについて、
［ｃ．２．ｉ．ａ］前記チャンクまたは部分（ｅｉ、ｋ）を、それぞれの場合において整数の少なくとも１つの有限集合（Ｃ）から得られる少なくとも１つの係数（ｂｉ、ｊ）によって荷重された、２の指数（２ｊ）の合計（Σｊ＝０Ｌｂｉ、ｊ２ｊ）として再符号化し、
［ｃ．２．ｉ．ｂ］２の最大の指数（２Ｌ）に割り当てられた係数（ｂｉ、Ｌ）が、非消滅（non-vanishing）である場合、前記仮変数（ｘ）を、仮変数（ｘ）と、前記２の最大の指数（２Ｌ）の前記係数（ｂｉ、Ｌ）に割り当てられた前記要素（ｇｉ）の倍数（ｂｊ、Ｌｇｉ）との合計に設定し、
［ｃ．２．ｉｉ］インデックス（ｊ）の各値ｊ＝Ｌ−１，Ｌ−２，・・・，０について、
［ｃ．２．ｉｉ．ａ］前記仮変数（ｘ）を２倍し、
［ｃ．２．ｉｉ．ｂ］前記インデックス（ｉ）の各値ｉ＝１，２，・・・，ｄについて、
前記２の指数（２ｊ）に割り当てられた前記係数（ｂｉ、ｊ）が、非消滅である場合、前記仮変数（ｘ）を、仮変数（ｘ）と、前記２の指数（２ｊ）の前記係数（ｂｉ、ｊ）に割り当てられた前記要素（ｇｉ）の倍数（ｂｊ、Ｌｇｉ）との合計に設定する、
というサブステップが実行される、
というサブステップに分割することができ、
―前記チャンクまたは部分（ｅｉ、ｋ）を個別に再符号化する方法ステップ［ｃ］の後に、前記仮変数（ｘ）が返される、
ことを特徴とする請求項１乃至請求項３のいずれかに記載の方法。
【請求項６】
―前記再符号化されたチャンクまたは前記再符号化された部分（ｅｉ、ｋ）は、一度使用され、
―前記再符号化されたチャンクまたは前記再符号化された部分（ｅｉ、ｋ）が記憶されている前記メモリユニットを用いて、続くチャンクまたは続く部分（ｅｉ、ｋ−１）が再符号化される、ことを特徴とする請求項１乃至請求項５のいずれかに記載の方法。
【請求項７】
前記方法は、特に少なくとも１つのチップカードおよび／または特に少なくとも１つのスマートカードに割り当てられた、少なくとも１つのマイクロプロセッサにおいて実施される、ことを特徴とする請求項１乃至請求項６のいずれかに記載の方法。
【請求項８】
請求項１乃至請求項７のいずれかに記載の方法に従い動作するマイクロプロセッサ。
【請求項９】
少なくとも１つの請求項８に記載のマイクロプロセッサを有する装置、特にチップカードおよび／または特にスマートカード。
【請求項１０】
請求項１乃至請求項７のいずれかに記載の方法、および／または少なくとも１つの請求項８に記載のマイクロプロセッサ、および／または、少なくとも１つの請求項９に記載の装置、特に少なくとも１つのチップカードおよび／または特に少なくとも１つのスマートカードの、
少なくとも１つのキー交換システムまたは少なくとも１つの署名システム内の、少なくとも１つの暗号システム、特に少なくとも１つの公開キー暗号システム、における使用。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、要素ｇｉをマルチ累乗Πｉ＝１ｄｇｉｅｉ  またはマルチスカラー乗算Σｉ＝１ｄｅｉｇｉするための方法であって、それぞれの場合で少なくとも１つのべき指数またはスカラーｅｉ、特に整数のべき指数またはスカラーを使用し、べき指数またはスカラーは、それぞれの場合で最大ビットレートｎまたはビット長を有し、特に、要素ｇを累乗geまたはスカラー乗算ｅ・ｇするために、少なくとも１つのべき指数またはスカラーｅ、特に整数のべき指数またはスカラーを使用し、べき指数またはスカラーは、それぞれの場合で最大ビットレートｎまたはビット長を有し、要素ｇｉ；ｇは、少なくとも１つの群Ｇ、例えばアーベル群Ｇから得られ、アーベル群Ｇは、
―（マルチ）累乗の場合では、特に乗法的に表記され、
―（マルチ）スカラー乗算の場合では、特に加法的に表記される方法に関する。
【背景技術】
【０００２】
アーベル群におけるディスクリート対数問題が解決できないことに基づく、非対称の暗号化方法または公開キー暗号システムにおいて、群要素ｇの累乗ｇｎまたはいくつかの群要素ｇ，ｈのマルチ累乗g１ｎ１ｈｋｎｋは、署名およびキー交換方法における基本的な演算の１つである。従って、この基本演算の加速が、特に重要である。
【０００３】
群要素ｇの指数を事前計算する可能性は、この場合、使用される群要素ｇが、事前に知られてなければならないという問題をもたらす。これは、例えば、ＤＳＡ（Digital Signature Algorithm）またはＥＣＤＳＡ（Elliptic Curve Digital Signature Algorithm）あるいはDiffle-Hellmanキー交換方法における署名照合の場合には、当てはまらない。加えて、例えばスマートカードで、十分に大きな数の事前計算要素を記憶する、十分な記憶スペースがないという事実がある。
【０００４】
他の可能性は、使用されるべき指数の再符号化にあり、この可能性は、群要素ｇの選択からは独立しており、従って、上述の署名およびキー交換方法の加速に対して特に魅力的である。
【０００５】
（マルチ）累乗のためのアルゴリズムで使用されるべき指数を再符号化するための技術は、整数が、通常のバイナリ表現とは異なる形態で、すなわちより低密度で、かつ少なくとも要素０および１を含む整数の有限集合Ｃにおける係数で、再度書き込まれるという、基本的な概念に基づいている。
【０００６】
計算が行なわれる特定の群において、要素の反転が、“無料（gratis）”である場合、すなわち、反転のための計算の複雑さが、他の群演算と比べて非常に低い場合、かつ、符合付き係数が使用された場合は、常に、ｃεＣが、−ｃεＣも意味するとみなすことができる。反転が、計算面で複雑である場合、集合Ｃの全ての要素は、負でない整数である。
【０００７】
そこで、ｇを群要素、ｅを整数とする、ｇｅを計算するためのいわゆる“２乗および乗算（square-and-multiply）”累乗アルゴリズムは、以下のように既知の方法で動作する。
―ｅは、Σｉ＝０ｎｅｉ２ｉと書かれ、ここで、各係数ｅｉは、Ｃ内にあり、
―要素ｇｅｎは、事前に与えられるか、または計算され、
―仮変数ｘは、ｇｅｎに設定され、
―全てのｉ＝ｎ−１，ｎ−２，ｎ−２，・・・，０、について、まずｘが２乗され、次いで、係数ｅｉが非消滅（non-vanishing）である場合、要素ｇｅｉで乗算され、
―ｉ＝０について行なわれた最後の２乗演算に続いて、かつ、適切な場合（すなわち係数ｅ０が非消滅である場合）に、要素ｇｅ０による乗算に続いて、仮変数ｘの値は、所望の結果ｇｅである。
【０００８】
群演算の数は、次いで、べき指数ｅの表現Σｉ＝０ｎｅｉ２ｉにおける非消滅の係数ｅｉの数にほぼ等しく（これらの群演算は、事前計算または所与の群要素、あるいは、群要素の反転が速い場合はその反転、のいずれかによる乗算である）、加えて、
―表現の長さｎ（対応する例えばｎの演算は、この場合、２乗演算である）、および
―ｃεＣ、およびｃはゼロに等しくないとして、要素ｇｃの表の濃度（cardinality）、または
―所与の群における反転が早く、係数ｅｉが符合付きである場合、この濃度の半分、である。
【０００９】
Ｃのサイズと表現の密度との良好な一致が、べき指数の表現における最適な性能への道である。
【００１０】
べき指数再符号化の例として、以下のものが挙げられる。
―ＮＡＦ（Non Adjacent Form）（Ｇ．Ｗ．ライトワイスナー（Reitwiesner）、“バイナリ演算（Binary arithmetic）”、コンピュータにおける進歩（Advances in Computers）１、２３１〜３０８頁、１９６０年；Ｓ．アーノ（Arno）およびＦ．Ｓ．ウィーラー、（Wheeler）、“最小ハミング重みの符合付き数字表現（Signed digit representations of minimal Hamming weight）”、ＩＥＥＥコンピュータに関する会報（IEEE Transactions on Computers）４２、１９９３年、１００７〜１０１０頁、を参照）；
―ＮＡＦ（Non Adjacent Form）に類似の同一荷重方法（Ｍ．ジョイ（Joye）およびＳ．−Ｍ．イェン（Yen）、“最適な左−右バイナリ符号付き数字の再符号化（Optimal left-to-right binary signed-digit recoding）”、コンピュータに関するＩＥＥＥ会報（IEEE Transactions on Computers）４９（７）、２０００年、７４０〜７４８頁、を参照）；
―固定窓による累乗のための再符号化（Ｊ．ボス（Bos）およびＭ．コスター（Coster）、“加法鎖ヒューリスティックス（Addition chain heuristics）”、暗号の進歩（Advances in Cryptology）−ＣＲＹＰＴＯ‘８９、ＬＮＣＳ４３５、１９９０年、４００〜４０７頁；Ａ．メネゼス（Menezes）、Ｐ．フォン  オールショット（Oorschot）およびＳ．バンストーン（Vanstone）、“応用暗号のハンドブック（Handbook of Applied Cryptography）”、ＣＲＣ出版（CRC Press）、１９９６年、を参照）；
―ＧＮＡＦ（Generalized Non Adjacent Form）（Ｗ．Ｅ．クラーク（Clark）およびＪ．Ｊ．リャン（Liang）、“整数の一般的な基数表現に対する演算重みについて（On arithmetic weight for a general radix representation of integers）”、情報論理に関するＩＥＥＥ会報（IEEE Transactions on Information Theory）ＩＴ−１９、１９７３年、８２３〜８２６頁、を参照）；
―“移動窓（sliding windows）”（Ｅ．Ｇ．サーバー（Thurber）、“加法鎖１（ｍｎ）≦１（ｎ）ｂおよびｃ（４）に対するより低いバウンドについて（On addition chains 1(mn)≦1(n)b and lower bounds for c(r)）”、デューク数学ジャーナル（Duke Mathematical Journal）４０、１９７３年、９０７〜９１３頁；Ａ．メネゼス（Menezes）、Ｐ．フォン  オールショット（Oorschot）およびＳ．バンストーン（Vanstone）、“応用暗号のハンドブック（Handbook of Applied Cryptography）”、ＣＲＣ出版（CRC Press）、１９９６年、を参照）、任意で、ＮＡＦ（Non Adjacent Form）について、または他の冗長ベース２表現について（Ｒ．アバンジ（Avanzi）、“暗号における特定のマルチ累乗技術の複雑さについて（On the complexity of certain multi-exponentiation techniques in cryptography）”、暗号のジャーナル（Journal of Cryptology）において公開；Ｋ．コヤマ（Koyama）およびＹ．ツルオカ（Tsuruoka）、“符号付きのバイナリ窓方法を用いた楕円暗号システムの加速（Speeding up elliptic cryptosystems by using a signed binary window method）”、Ｅ．ブリッケル（Brickell）（Ed.）、“暗号の進歩（Advances in Cryptology）、ＣＲＹＰＴＯ‘９２の議事録（Proceedings of Crypto ‘92）”、コンピュータ科学  ボリューム７４０におけるレクチャーノート（Lecture Notes in Computer Science Volume 740）、３４５〜３５７頁、シュプリンガーフェアラーク（Springer-Verlag）、１９９２年を参照；また、Ｋ．コヤマ（Koyama）、Ｙ．ツルオカ（Tsuruoka）、“楕円曲線上の高速計算のための符号付きバイナリ窓方法（A Signed Binary Window Method for Fast Computing over Elliptic Curves）”、ＩＥＩＣＥトランスファンダメンタルズ（Trans. Fundamentals）ボリュームＥ７６−Ａ、Ｎｏ．１、５５〜６２頁、１９９３年１月）を参照；および
―ｗＮＡＦ（window Non Adjacent Form）（Ｊ．Ａ．ソリナス（Solinas）、“楕円曲線のファミリーにおける演算のための改善されたアルゴリズム”（An improved algorithm for arithmetic on a family of elliptic curves）”、暗号の進歩（Advances in Cryptology）−ＣＲＹＰＴＯ‘９７、Ｂ．Ｓ．カリスキー（Kaliski）Ｊｒ．（Ed.）、コンピュータ科学  ボリューム１２９４におけるレクチャーノート（Lecture Notes in Computer Science Volume 1294）、３５７〜３７１頁；Ｈ．コーエン（Cohen）、“柔軟な窓の２乗アルゴリズムの分析（Analysis of the flexible window powering algorithm）”、http://www.math.u-bordeaux.fr/~cohen/において予定原稿を入手可能、を参照）。
【発明の開示】
【発明が解決しようとする課題】
【００１１】
しかしながら、べき指数の再符号化に関して、この再符号化は、多くの場合、“オンライン”、すなわち累乗それ自体の間には、行なわれ得ないことを考慮すべきである。このため、再符号化されたべき指数は、最初に記憶されなければならない。しかしながら、この記憶要件は、特に極度に制限された環境、例えばスマートカードなどでは、不利であり、それは、このような極度に制限された環境では、メモリのそれぞれのバイトが“貴重”だからである。
【００１２】
上述の不利益および欠点に基づき、また概略を述べた従来技術を参考にして、本発明の目的は、上述の種類の方法を、再符号化されたべき指数またはスカラーのための記憶スペースに関する要求が、特に例えばスマートカードなどの極度に制限された環境であっても、可能な限り削減されるようなやり方で、さらに展開することである。
【課題を解決するための手段】
【００１３】
この目的は、請求項１に記載の特徴を有する方法によって達成される。本発明の有利な実施形態および好ましい展開は、従属請求項において特徴付けられる。
【００１４】
本発明は、よって、制限された環境における、単一累乗または単一スカラー乗算のため、あるいはマルチ累乗またはマルチスカラー乗算のための、ほぼオンラインの再符号化の原理に基づいている。この点について、“ほぼオンライン”の再符号化は、べき指数またはスカラーが、個別に再符号化されるセクションに分割され、その再符号化は、（マルチ）累乗または（マルチ）スカラー乗算の部分の間の層において行なわれること、を意味する。
【００１５】
“ほぼオンライン”の再符号化の技術を用いて、再符号化されたべき指数または再符号化されたスカラーのための記憶要件を減少させることが可能である。（マルチ）累乗または（マルチ）スカラー乗算の全実行時間における、ほぼオンラインの再符号化の効果は、通常は最小である。
【００１６】
上述の好適な再符号化動作に基づき、本発明に係る方法では、マルチ累乗またはマルチスカラー乗算の場合における再符号化が、ｅｉ＝Σｊ＝０ｎｂｉｊ２ｊの形態をとる、と仮定される。マルチ累乗またはマルチスカラー乗算の特殊な場合である（単一）累乗または（単一）スカラー乗算の場合は、仮定された基準は、よってｅ＝Σｊ＝０ｎｂｊ２ｊととられ、ここでｎ＝｜ｌｏｇ２ｅ｜は、ｅのビット長であり、すなわち、このビット長ｎは、多くともバイナリ表現よりほぼ１ビット長い。換言すると、これは、ｎ＋１が、任意のべき指数またはスカラーｅｉ＝Σｊ＝０ｎｂｉｊ２ｊの最大長さとして理解されることを意味する。
【００１７】
再符号化されたアルゴリズムは、おそらく明らかではないがパラメータｗに依存するとさらに仮定され、ｗは、通常、その上でべき指数またはスカラーｅｉのビットが読まれる窓の幅、あるいはこのような幅の上限に対応する。
【００１８】
この基準において、本発明の教示によれば、乗法的に表記された群、特にアーベル群Ｇの場合、表記Πｉ＝１ｄｇｉｅｉにおいて記号で表現することができるマルチ累乗は、以下のステップで行なわれる：
まず、チャンクまたは部分の幅Ｌを選択し、チャンクまたは部分幅Ｌは、パラメータｗよりも著しく大きくてもよく、かつ任意のべき指数ｅｉの最大長さよりも著しく短くてもよく、
次いで、
全ての指数ｇｉｃを
［ａ．１］計算および記憶し、または
［ａ．２］メモリから検索し、
ここで、ｇｉは群Ｇの要素であり、
ｃは許容可能な正の係数であり、
［ｂ］各べき指数ｅｉ、特に整数のべき指数を、上で選択されたチャンクまたは部分の幅Ｌを有する、複数のチャンクまたは複数の部分ｅｉ，ｋに分割し、かつ、
［ｂ．１］べき指数ｅｉは、分割された形態ｅｉ＝Σｋ＝０ｒｅｉ，ｋ２ｋＬで書くことができ、ここで、０≦ｅｉ，ｋ＜２Ｌであり、
［ｂ．２］チャンクまたは部分ｅｉ，ｋの数ｒは、特に、チャンクまたは部分の幅の最大ビットレートｎおよびビットレートＬの整数商として定義することができ、
［ｃ］チャンクまたは部分ｅｉ，ｋを個別に再符号化し、ここで、この再符号化は、各べき指数ｅｉの各個別チャンクまたは各個別部分ｅｉ，ｋについて：
［ｃ．１］仮変数ｘを、標準化された値、特に、値１に設定し、ここで１は、群Ｇに割り当てられた群演算に対する群Ｇの中立要素を示し、
［ｃ．２］変数ｋを、値ｒ−１，ｒ−２，・・・，０に（交互に）設定し、ここで、変数ｋのこのような各値ｋ＝ｒ−１，ｒ−２，・・・，０について：
［ｃ．２．ｉ］ｄを、要素ｇｉの数として、かつ要素ｇｉに割り当てられたべき指数ｅｉのものとして定義した、インデックスｉの各値ｉ＝１，２，・・・，ｄについて、
［ｃ．２．ｉ．ａ］チャンクまたは部分ｅｉ，ｋを、それぞれの場合において整数の有限集合Ｃから得られる係数ｂｉ，ｊによって荷重された、２の指数２ｊの合計Σｊ＝０ｎｂｉ，ｊ２ｊとして再符号化し、
［ｃ．２．ｉ．ｂ］２の最大の指数２Ｌに割り当てられた係数ｂｉ，Ｌが、非消滅である場合、仮変数ｘを、ｘと、２の最大の指数２Ｌの係数ｂｉ，Ｌに割り当てられた要素ｇｉの指数ｇｉｂｉ，Ｌとの積に設定し、
［ｃ．２．ｉｉ］インデックスｊの各値ｊ＝Ｌ−１，Ｌ−２，・・・，０について、
［ｃ．２．ｉｉ．ａ］仮変数ｘを２乗し、
［ｃ．２．ｉｉ．ｂ］インデックスｉの各値ｉ＝１，２，・・・，ｄについて、
２の指数２ｊに割り当てられた係数ｂｉ，ｊが、非消滅である場合、仮変数ｘを、ｘと、２の指数２ｊの係数ｂｉ，ｊに割り当てられた要素ｇｉの指数ｇｉｂｉ，ｊとの積に設定する、
というサブステップが実行される、
というサブステップに分割することができ、
最後に、ｘが返される。
【００１９】
（単一）累乗の特別な場合が、上でｄ＝１について得られ、これはすなわち、単一の要素ｇおよび要素ｇに割り当てられた単一のべき指数ｅがある場合であり、これは事実上、インデックスｉを省略することと同等とすることができる。この場合、要素ｇは、従って、べき指数ｅ、特に、最大のビットレートｎまたはビット長を有する整数のべき指数、によって累乗されて指数ｇｅを形成し、ここで、要素ｇは、再び、乗法的に表記されたアーベル群Ｇから得られる。
【００２０】
同様のやり方で、本発明の教示によれば、加法的に表記された群、特にアーベル群Ｇの場合、表記Σｉ＝１ｄｅｉｇｉにおいて記号で表現することができるマルチスカラー乗算は、以下のステップで行なわれる：
まず、チャンクまたは部分の幅Ｌを選択し、チャンクまたは部分幅Ｌは、パラメータｗよりも著しく大きくてもよく、かつ任意のスカラーｅｉの最大長さよりも著しく短くてもよく、
次いで、
全ての倍数ｃ・ｇｉを
［ａ．１］計算および記憶し、または
［ａ．２］メモリから検索し、
ここで、ｃは許容可能な正の係数であり、
ｇｉは群Ｇの要素であり、
［ｂ］各スカラーｅｉ、特に整数のスカラーを、上で選択されたチャンクまたは部分の幅Ｌを有する、複数のチャンクまたは複数の部分ｅｉ，ｋに分割し、かつ、
［ｂ．１］スカラーｅｉは、分割された形態ｅｉ＝Σｋ＝０ｒｅｉ，ｋ２ｋＬで書くことができ、ここで、０≦ｅｉ，ｋ＜２Ｌであり、
［ｂ．２］チャンクまたは部分ｅｉ，ｋの数ｒは、特に、チャンクまたは部分の幅の最大ビットレートｎおよびビットレートＬの整数商として定義することができ、
［ｃ］チャンクまたは部分ｅｉ，ｋを個別に再符号化し、ここで、この再符号化は、各スカラーｅｉの各個別チャンクまたは各個別部分ｅｉ，ｋについて：
［ｃ．１］仮変数ｘを、標準化された値、特に、値０に設定し、ここで０は、群Ｇに割り当てられた群演算に対する群Ｇの中立要素を示し、
［ｃ．２］変数ｋを、値ｒ−１，ｒ−２，・・・，０に（交互に）設定し、ここで、変数ｋのこのような各値ｋ＝ｒ−１，ｒ−２，・・・，０について：
［ｃ．２．ｉ］ｄを、要素ｇｉの数として、かつ要素ｇｉに割り当てられたスカラーｅｉのものとして定義した、インデックスｉの各値ｉ＝１，２，・・・，ｄについて、
［ｃ．２．ｉ．ａ］チャンクまたは部分ｅｉ，ｋを、それぞれの場合において整数の有限集合Ｃから得られる係数ｂｉ，ｊによって荷重された、２の指数２ｊの合計Σｊ＝０Ｌｂｉ，ｊ２ｊとして再符号化し、
［ｃ．２．ｉ．ｂ］２の最大の指数２Ｌに割り当てられた係数ｂｉ，Ｌが、非消滅である場合、仮変数ｘを、ｘと、２の最大の指数２Ｌの係数ｂｉ，Ｌに割り当てられた要素ｇｉの倍数ｂｉ，Ｌｇｉとの合計に設定し、
［ｃ．２．ｉｉ］インデックスｊの各値ｊ＝Ｌ−１，Ｌ−２，・・・，０について、
［ｃ．２．ｉｉ．ａ］仮変数ｘを２倍し、
［ｃ．２．ｉｉ．ｂ］インデックスｉの各値ｉ＝１，２，・・・，ｄについて、
２の指数２ｊに割り当てられた係数ｂｉ，ｊが、非消滅である場合、仮変数ｘを、ｘと、２の指数２ｊの係数ｂｉ，ｊに割り当てられた要素ｇｉの倍数ｂｉ，ｊｇｉとの合計に設定する、
というサブステップが実行される、
というサブステップに分割することができ、
最後に、ｘが返される。
【００２１】
（単一）スカラー乗算の特別な場合が、上でｄ＝１について得られ、これはすなわち、単一の要素ｇおよび要素ｇに割り当てられた単一のスカラーｅがある場合であり、これは事実上、インデックスｉを省略することと同等とすることができる。この場合、要素ｇは、従って、スカラーｅ、特に、最大のビットレートｎまたはビット長を有する整数のスカラー、によって乗算されて積ｅ・ｇを提供し、ここで、要素ｇは、再び、加法的に表記されたアーベル群Ｇから得られる。
【００２２】
本発明の１つの好適なさらなる実施形態によると、
―再符号化されたチャンクまたは再符号化された部分ｅｉ，ｋは、一度使用され、
―再符号化されたチャンクまたは再符号化された部分ｅｉ，ｋが記憶されているメモリユニットを用いて、続くチャンクまたは続く部分ｅｉ，ｋ−１が再符号化され、
従って、整数の右から左への再符号化に基づく（マルチ）累乗アルゴリズムまたは（マルチ）スカラー乗算アルゴリズムの記憶要件を、大幅に減少させることができる。
【００２３】
本発明は、さらに、上述の種類の方法に従い動作するマイクロプロセッサに関する。
【００２４】
本発明は、さらに、少なくとも１つの上述の種類のマイクロプロセッサを有する装置、特にチップカードおよび／または特にスマートカードに関する。
【００２５】
本発明は、最後に、
上述の種類の方法、および／または
少なくとも１つの上述の種類のマイクロプロセッサ、および／または、
少なくとも１つの上述の種類の装置、特に少なくとも１つのチップカードおよび／または特に少なくとも１つのスマートカードの、
少なくとも１つのキー交換システムまたは少なくとも１つの署名システム内の、少なくとも１つの暗号システム、特に少なくとも１つの公開キー暗号システム、における使用に関する。
【発明を実施するための最良の形態】
【００２６】
上述したように、本発明の教示を有利に実施かつ展開する様々な可能性が存在する。この点において、一方で、請求項１に従属する請求項が参照され、他方で、本発明のさらなる実施形態、機能および利点が、５つの実施形態の例の好適な実施に基づいて、以下、より詳細に説明され、ここで、
―実施形態の第１の例は、単一累乗の方法に関し、
―実施形態の第２の例は、マルチ累乗の方法に関し、
―実施形態の第３の例は、同様に、マルチ累乗の方法に関し、
すなわち、アーベル群Ｇに対する乗法表記に基づき、
―実施形態の第４の例は、単一スカラー乗算の方法に関し、
―実施形態の第５の例は、マルチスカラー乗算の方法に関し、
すなわち、アーベル群Ｇに対する加法表記に基づく（このようなアーベル群Ｇに対する加法表記の場合は、上記“従来技術”セクションにおけるアーベル群Ｇに対する乗法表記と比べると、当然ながら変更および置換を行なう必要があり、これらの変更および置換は、請求項４［←→（マルチ）累乗：中立要素“１”；“２乗”；“積”］と請求項５［←→（マルチ）スカラー乗算：中立要素“０”；“２倍”；“合計”］の表現の違いから、明らかである。
【００２７】
以下に示す本発明に係る５つの実施形態の例は、いわゆるほぼオンラインの再符号化の形態での一般的な技術向けに用いられ、この再符号化を用いて、
―単一累乗アルゴリズム（実施形態の第１の例を参照）
―マルチ累乗アルゴリズム（実施形態の第２の例および実施形態の第３の例を参照）
―単一スカラー乗算アルゴリズム（実施形態の第４の例を参照）または
―マルチスカラー乗算アルゴリズム（実施形態の第５の例を参照）、
の記憶要件を著しく減少させることができ、これらは、右から左への整数の再符号化に基づいている。
【００２８】
ほぼオンラインの再符号化の技術は、例えばチップカードまたはスマートカードなどの極度に制限された環境において、非常に有用となり得るものであり、このような環境では、記憶スペースに関する節約は、特定の状況に大きく依存し得る（可能性として、特に、べき指数またはスカラーが、多すぎる小部分（＝多すぎる小さな“チャンク（chunk）”）に分割された場合、スループット損失が、非常に低いが生じ得る。次いで、性能への影響が、顕著となり得る）。
【００２９】
実施形態の第１の例：単一累乗
Ｇが、２ｎオーダーのアーベル群であり、かつ、要素ｇεＧおよび整数ｅが与えられていると仮定した場合、本発明に係る目的は、ｘ＝ｇｅを、可能な限り速く計算することである。本発明に係る再符号化は、累乗を非常に速く行なうが、この再符号化は、オンラインでは使うことができず、すなわち、累乗自体の間には行なうことができない。これは、例えば、ｗＮＡＦ（window Non Adjacent Form）において該当する。
【００３０】
ほぼオンラインの再符号化で用いられる技術は、べき指数ｅを、いくつかの“べき指数チャンク”、すなわち、ｗビットよりもかなり長く、しかしまたｅよりもかなり短い、いくつかのべき指数セクションまたはいくつかのべき指数部分に分割することに存する。チャンクまたは部分は、次いで、個別に再符号化され、一度使用され、次いで、チャンクまたは部分が記憶されていたメモリを再び使用して次のチャンクまたは次の部分が再符号化され、よって、べき指数ｎのために必要な合計記憶スペースを、著しく減少させることができる。
【００３１】
以下に示されるほぼオンラインの再符号化は、チャンクまたは部分が、Ｌビットの長さを有する、という仮定のもとで行われる。Ｌが、ｗよりもずっと大きい理由は、再符号化されたべき指数における非消滅（non-vanishing）の係数の数の概算が、通常は漸近的に与えられるが、再符号化されたべき指数における非消滅の係数の実際の数は、時折、小さな加法定数のためにより大きいものとなることであり、このことは、特定の例に基づいて以下に示される。
【００３２】
以下、ほぼオンラインの再符号化の実施形態の第１の例の文脈において、以下のものが入れられたアルゴリズムが提供される。
―アーベル群Ｇの基本要素ｇ、
―ｎビットを有する整数ｅ、
―窓の幅ｗ、および
―チャンクまたは部分の幅Ｌ≫ｗ；
単一累乗ｇｅは、次のように出力される。
【数１】
2007526513.tif 000002
【００３３】
ここで、Ｌビットの後に、上のアルゴリズムが、１つのみの群乗算の代わりに、２つの群乗算を１列で行なうことが起こり得ることに留意すべきである。これは、チャンクｅｉの１つ（＝べき指数部分ｅｉの１つ）が、奇数を表す場合、および続くチャンクｅｉ＋１（＝続くべき指数部分ｅｉ＋１）の再符号化が、１係数だけ長い（ｂＬはゼロに等しくない）場合に生じる。
【００３４】
選択された再符号化がｗＮＡＦ（window Non Adjacent Form）である特定の例を用いて、これより、速度に関する損失が最小であり、記憶スペースに関する節約が非常に大きくなり得ることを、示すことができる。
【００３５】
ｎ＝１６０について、ｗの最適値は、５に等しく（Ｈ．コーエン（Cohen）、“柔軟な窓の２乗アルゴリズムの分析（Analysis of the flexible window powering algorithm）” http://www.math.u-bordeaux.fr/~cohen/において予定原稿を入手可能、を参照）、よって、基本要素ｇの７個の指数ｇ３，ｇ５，ｇ７，ｇ９，ｇ１１，ｇ１３，ｇ１５を、事前計算する必要があり、一時的にｇ２も必要とされる。再符号化される係数ごとに少なくとも５つのビットが、必要とされるが、作成者（implementor）は、おそらく完全な符号付きバイトを使用する。
【００３６】
２つの再符号化されたべき指数は、３２０バイトのＲＡＭ（Random Access Memory）を必要とするが、２つの再符号化された３２ビットチャンク（＝３２ビットセクションまたは３２ビット部分）は、６６バイトのＲＡＭ（Random Access Memory）しか必要としない。節約された２５４バイトのＲＡＭ（Random Access Memory）は、アファイン座標の楕円曲線の６つのポイントの記憶に使用することができる。
【００３７】
ここで、コーエンは（Ｈ．コーエン（Cohen）、“柔軟な窓の２乗アルゴリズムの分析（Analysis of the flexible window powering algorithm）” http://www.math.u-bordeaux.fr/~cohen/において予定原稿を入手可能、を参照）、ｎビット（対応する累乗＋１での乗算の平均数）を有する整数のｗＮＡＦ（window Non Adjacent Form）の平均のハミング重みが、
ｎ／（ｗ＋１）＋１−０．５（ｗ−１）（ｗ＋２）／（ｗ＋１）２＋Ｏ（ρ−ｎ）
に等しいことを証明しており、ここで、ρ＝ρ（ｗ）は、１を超える実数であり、ｗのみに依存しｎには依存しない。数値で表すと、
ｗ＝３について、ρ＝２１／２＝１．４１４・・・、
ｗ＝４について、ρ＝１．２１５７・・・、および
ｗ＝５について、ρ＝１．１２９６・・・である。
【００３８】
ｗＮＡＦ（w Non Adjacent Form）の平均のハミング重みに関する上の集合は、整数がｒチャンクまたはｒ部分に分割された場合、ｒチャンクまたはｒ部分の合計ハミング重みは、元の整数のハミング重みよりも、
（ｒ−１）(１−０．５（ｗ−１）（ｗ＋２）／（ｗ＋１）２)
倍大きいことを意味する。
【００３９】
ｎ＝１６０の場合、Ｌ＝３２、かつその結果ｒ＝５、を選択することができる。“柔軟な窓（flexible window）”の方法は、本発明に係るほぼオンラインの方法よりも、平均で２２／９＝２．４４少ない群演算を必要とする。この差は、累乗アルゴリズムの全実行時間のほぼ１．２６パーセント（事前計算のための時間も含み１９３群演算にわたり）である。しかしながら、符号化されたべき指数のための記憶要件は、ほぼ８パーセント減少されている。
【００４０】
実施形態の第２の例：マルチ累乗
実施形態の第１の例（単一累乗）からの上のアルゴリズムは、マルチ累乗の方法に変換することができる。
【００４１】
ｄ＞１とする群要素ｇ１，・・・，ｇｄεＧと、べき指数ｅ１，・・・，ｅｄが与えられ、かつΠｉ＝１ｄｇｉｅｉが計算されるべき場合、まず、べき指数ｅ１，・・・，ｅｄのスパース再符号化（sparse recoding）を使用する決定が行なわれ、次いで、“２乗および乗算（square-and-multiply）”ループが使用される。
【００４２】
まず、全ての指数ｇｉｃが計算および記憶され、ここでｃは、許容し得る正の係数である。仮変数ｘが、次いで１εＧに設定される。ｊ＝ｎ，ｎ−１，・・・，０について、ｘがまず２乗され、ｉ＝１，・・・，ｄについて、２乗されたｘが、ｇｉｅｉｊで乗算され、ここでｅｉｊは、ｅｉの再符号化における２ｊの係数である。最後に、仮変数ｘは、所望の結果を含む。
【００４３】
この方法は、高速累乗と呼ぶこともできる。実施形態の第１の例に係る状況でのように、再び、良好な右から左への再符号化の利点を、多すぎるメモリを使用することなく保持することが望ましい。
【００４４】
以下の変形は、再符号化を、“ほぼオンライン”で、すなわちほぼ高速マルチ累乗の間に、または高速マルチ累乗のすぐ後に行い、ここで、以下のものがアルゴリズムに入れられる。
―アーベル群Ｇの基本要素ｇ１，・・・，ｇｄ
―それぞれ多くともｎビットを有する整数ｅ１，・・・，ｅｄ（ｄ＞１）、
―窓の幅ｗ、
―チャンクまたは部分の幅Ｌ≫ｗおよび
―係数の集合において、全てのｃについて事前計算された指数ｇｉｃ；
マルチ累乗Πｉ＝０ｄｇｉｅｉは、次のように出力される。
【数２】
2007526513.tif 000003
【００４５】
実施形態の第１の例に係るアルゴリズムに関して付けられたコメントは、ここでも関係し、すなわち、ｎ＝１６０、およびＬ＝３２の有限体（finite field）にわたる楕円曲線の場合、２．４４ｄの群演算が用いられ、ここでｄは、互いに乗算される指数の数である。これは、単一の高速累乗の場合よりも多いが、２５４ｄバイトのＲＡＭ（Random Access Memory）を節約することができ、これはすなわち、アファイン座標における６ｄの事前計算されたポイントの分の記憶スペースである。
【００４６】
実施形態の第３の例：並列シフティング窓によるマルチ累乗
実施形態の第３の例では、ほぼオンラインの再符号化の使用が、イェン（Yen），レア(Laih)およびレンストラ（Lenstra）によるアルゴリズム（Ｓ．−Ｍ．イェン（Yen）、Ｃ．−Ｓ．レア（Laih）およびＡ．Ｋ．レンストラ（Lenstra）、“マルチ累乗（Multi-exponentiation）”、コンピュータデジタル技術のＩＥＥ議事録（IEE Proc. Comput. Digit. Tech.）、ボリューム１４１、Ｎｏ．６、１９９４年１１月、を参照）の一般化（Ｒ．アバンジ（Avanzi）“暗号における特定のマルチ累乗技術の複雑さについて（On the complexity of certain multi-exponentiation techniques in cryptography）”、暗号のジャーナル（Journal of Cryptology）において公開、を参照）で記述されている。
【００４７】
この点に関して、以下に述べるこの実施形態の第３の例は、説明されたアルゴリズムの基本原理を主に説明する。達成可能な効率の増加は、むしろ小さいと考えなければならない。アルゴリズムは、基本的には、移動窓を用いたシャミル（Shamir）によるトリックの変形であり、以下に示される。
【００４８】
以下のものが、アルゴリズムに入れられる。
―窓の幅ｗ、
―整数ｅｉ＝Σｊ＝０ｎｅｉｊ２ｊ、および
―ｇ１，・・・，ｇｄを含む形態Πｉ＝１ｄｇｉｋｉの群Ｇからの事前計算された要素の集合Ｅ（集合Ｅは、窓の幅ｗおよび整数ｅｉの表現に大きく依存する。以下のアルゴリズムの後のコメントを参照）；
マルチ累乗Πｉ＝１ｄｇｉｅｉは、次のように出力される。
【数３】
2007526513.tif 000004
【００４９】
この点で、ステップ２．（ｃ）のスタートにおけるｆｉは、べき指数ｅのｗ連続ビットの鎖で表される整数であることに留意すべきである。標準化ステップ２．（ｅ）の後、ｆｉの少なくとも１つが、奇数である。
【００５０】
群Ｇにおいて、要素の反転が迅速に行なわれる場合、ＮＡＦ（Non Adjacent Form）が、再符号化として選択される。ＮＡＦ（Non Adjacent Form）においてｗビットを有する符合付き整数の数が、Ｉｗ＝（２ｗ＋２−（−１）ｗ）／３）であることが容易に分かる。集合Ｅは、形態Πｉ＝１ｄｇｉｋｉの全ての要素を、以下のように含む。
―ｉ＝１，２，・・・，ｄについて、｜ｋｉ｜≦Ｔｗであり、
―ｋｉの少なくとも１つが奇数であり、
―シーケンスｋ１，ｋ２，・・・ｋｐからの第１の非消滅の値が、正である。
【００５１】
このようにして、ステップ２．（ｆ）（ｉｉ）は、乗算または除算のいずれかによって行なうことができる。Ｅの濃度（cardinality）は、（Ｉｗｄ−Ｉｗ−１ｄ）／２である。
【００５２】
パラメータｗ＝２＝ｄは、次いで、固定され、ＮＡＦ（Non Adjacent Form）が、べき指数を再符号化するために選択される。この理由は、楕円曲線によるデジタル署名の生成である（米国国家規格協会（American National Standards Institute）、“ＡＮＳＩ  Ｘ９．６２：金融サービス業界のための公開キー暗号（Public Key Cryptography for the Financial Services Industry）：楕円曲線デジタル署名アルゴリズム（ＥＣＤＳＡ：Elliptic Curve Digital Signature Algorithm）、１９９９年”を参照）。
【００５３】
この場合、ｄ＝２であり、べき指数の関連サイズ、すなわちｎ＝１６０からｎ＝２４０までについては、パラメータｗ＝２は任意である（Ｒ．アバンジ（Avanzi）“暗号における特定のマルチ累乗技術の複雑さについて（On the complexity of certain multi-exponentiation techniques in cryptography）”、暗号のジャーナル（Journal of Cryptology）において公開、を参照）。実施形態の第３の例からの上のアルゴリズムは、よって、ｄ＝２＝ｗおよびＮＡＦ（Non Adjacent Form）によるほぼオンラインのマルチ累乗のために使用され、ここで、以下のものがアルゴリズムに入れられる。
―アーベル群Ｇの２つの（基本）要素ｇ１，ｇ２、
―多くとも２ビットを有する２つの自然数ｅ１，ｅ２、および
―ｎ≫Ｌ≫２である、チャンクまたは部分の幅Ｌ；
２重の累乗ｇ１ｅ１ｇ２ｅ２が、次のように出力される。
【数４】
2007526513.tif 000005
【００５４】
ここで、ステップ３において、実施形態の第１の例からの上のアルゴリズムの２つのインターリーブされたループ、および実施形態の第３の例からの上の第１のアルゴリズムの同時の連続する質問（interrogation）が見られることに留意されたい。
【００５５】
ステップ３．（ｃ）（ｉｉ）、３．（ｃ）（ｉｉｉ），３．（ｃ）（ｉｖ），３．（ｃ）（ｖ），３．（ｃ）（ｖｉ）において、幅２の窓が、Ｌビットを有する２つのチャンクまたは２つの部分の結合されたＮＡＦ（Non Adjacent Form）を介して形成される。
【００５６】
続く列も非消滅である場合、２つの“持ち越し（carry-over）”ａ１およびａ２が、非消滅の列の値を記憶し、従って、値は、次の反復の間に２倍して、次の列の値に加算することができる。ステップ３．（ｃ）（ｉｉｉ）を参照されたい。ステップ３．（ｃ）（ｉｖ）および３．（ｃ）（ｖｉ）は、乗算または除算によって行なわれる。
【００５７】
２つの整数ｂ１およびｂ２が、次いで、ｂｉ＝Σｔ＝１ｍｂｉ，ｊ２ｊと書かれ、列は、上の表現からの１対の係数（ｂ１，ｔ，ｂ２，ｔ）から成る。このような列の規則正しい連続は、ｂ１とｂ２の共通表現である。共通表現内の非消滅の列の数は、表現のハミング重みと呼ばれ、その密度は、ハミング重みの長さｍに対する商である。
【００５８】
２つのＮＡＦ（Non Adjacent Form）の連結表現の平均ハミング重みは、５／９である。実施形態の第３の例からの上の第２のアルゴリズムのメインループにおいて予測される乗算の数は、１１ｎ／２７であることを証明することが可能であり（Ｒ．アバンジ（Avanzi）“暗号における特定のマルチ累乗技術の複雑さについて（On the complexity of certain multi-exponentiation techniques in cryptography）”、暗号のジャーナル（Journal of Cryptology）において公開、を参照）、ここで、ほぼオンラインの技術によって引き起こされ得る追加的な群演算は、除外される。
【００５９】
Ｌが、スマートカードのＣＰＵ（Central Processing Unit）の固有の（native）ワード長、またはその小さな倍数、例えばＬ＝３２のいずれかである、という仮定も、より簡素な実施を可能にする。
【００６０】
１６０ビットを有するべき指数を使用し、かつ、ＮＡＦ（Non Adjacent Form）は、係数ごとに２ビットのみで効率的に記憶できるという事実を考慮すると、２つの再符号化された３２ビットチャンク（＝２つの再符号化された３２ビットセクションまたは２つの再符号化された３２ビット部分）を記憶するために、ほぼ１６バイトのＲＡＭ（Random Access Memory）が、完全なべき指数のための８０バイトの代わりに必要となる。記憶スペースの面での節約は、１６０ビットを有する有限体に対して、楕円曲線上の投影的な座標における１ポイントの記憶要件に対応し、よって、実施形態の２つの先の例でのようには、大きくはない。
【００６１】
実施形態の第３の例からの上の第２のアルゴリズムにより形成される、所与の長さの数のペアにおける窓の数をカウントするコンピュータプログラムに基づいて、プログラムの１０万回のランスルー（run-through）からの結果の平均を、次いで次のように計算することができる。
【００６２】
１６０ビットを有する数のペアにおける窓の平均数は、６５．８１１５３であり（（１１／２７）１６０＝６５．１８５であることに留意されたい）、３２ビットを有する数のペアにおける窓の平均の数は、１３．６４２１６である（（１１／２７）３２＝１３．０３７であることに留意されたい）。その結果、ｎ＝１６０およびＬ＝３２である場合、ほぼオンラインのアルゴリズムは、５１３．６４２１６−６５．８１１５３＝２．３９９２７のみ、すなわち実施形態の第３の例からの上の第１のアルゴリズムよりも約２．４多い群演算を必要とすることが予想される。
【００６３】
２３５は、実施形態の第３の例からの上の第１のアルゴリズムの、ｎ＝１６０の場合に予測される群演算の合計数なので、本発明に従って使用されるほぼオンラインの技術によって生じる性能に関する損失は、ほぼ１パーセントであると推定することができる。
【００６４】
同一のハミング重みを有するＮＡＦ（Non Adjacent Form）に対する代替表現があり、これは、左から右に演算する簡素なアルゴリズムによって計算できる（Ｍ．ジョイ（Joye）およびＳ．−Ｍ．イェン（Yen）、“最適な左−右バイナリ符号付き数字の再符号化”、コンピュータに関するＩＥＥＥ会報（IEEE Transactions on Computers）４９（７）、２０００年、７４０〜７４８頁、を参照）。この表現が、ほぼオンラインの再符号化の代わりに使用できなかったかどうかについて、疑問が生じるであろう。否定的な反応の理由は、この代替表現が、ＮＡＦ（Non Adjacent Form）性質を持たないこと、すなわち２つの連続する係数が両方とも消滅すべきでないことである。
【００６５】
記憶要件への関連効果は、非常に乏しい。ｗ＝２＝ｄであるこの場合では、集合Ｅは、０＜ａ≦３および−３≦ｂ≦３のいずれかを有する要素ｇ１ａｇ２ｂから成り、ここでａおよび／またはｂは奇数であり、あるいはａ＝０およびｂ＝１またはｂ＝３である。従って、集合Ｅは、密度２０を有する。これは、実施形態の第３の例の上の第１のアルゴリズムの記憶要件を、大きすぎるものにする。
【００６６】
同様の考察が、ソリナスの“ＪＳＦ（Joint Sparse Form）―結合スパース表現（J[oint]S[parse]F[orm]-joint sparse representation）”（Ｊ．Ａ．ソリナス（Solinas）、“整数のペアに対する低荷重バイナリ表現（Low-Weight Binary Representations for Pairs of Integers）”、応用暗号研究センター（Centre for Applied Cryptographic Research）、ワーテルロー大学（University of Waterloo）、組合わせ理論および最適化研究レポート（Combinatorics and Optimization Reserch Report）ＣＯＲＲ２００１−４１、２００１年、http://www.cacr.math.uwaterloo.ca/techreports/2001/corr2001-41.psにおいて入手可能、を参照）に関して生じる。
【００６７】
結合スパース表現（joint sparse representation）は、２つのべき指数を、互いから独立したやりかたで同時に再符号化する。ＪＳＦ（Joint Sparse Form）の平均密度は、１／２であり、実施形態の第３の例からのｗ＝２＝ｄによる上の第１のアルゴリズムのメインループにおける群演算の数は、３ｎ／８である（上のように、事前計算およびほぼオンラインの再符号化のコストを含まない）。
【００６８】
事前計算ポイントの数は１２であり、これは、アルゴリズムのスループットが１６０ビットから２５６ビットへの入力によって著しく改善されていなくても、上に提案された変形における数、８よりもずっと大きい。より詳細な議論および対応する根拠については、Ｈ．コーエン（Cohen）の“柔軟な窓の２乗アルゴリズムの分析（Analysis of the flexible window powering algorithm）”、http://www.math.u-bordeaux.fr/~cohen/において予定原稿を入手可能、のセクション３．３および４．４を参照することができる。
【００６９】
実施形態の第４の例：単一スカラー乗算
加法的に書かれたアーベル群Ｇにおける単一スカラー乗算が、実施形態の上の第１の例（単一累乗）と比べて、明確な置換［←→累乗における自然要素“１”、“２乗”、“積”の代わりに、スカラー乗算における自然要素“０”、“２倍”、“合計”］によって得られ、ほぼオンラインの再符号化の実施形態の第４の例の文脈において、以下のものが入れられるアルゴリズムとして、以下に示される。
―アーベル群Ｇの基本要素ｇ
―ｎビットを有する整数ｅ、
―窓の幅ｗおよび
―チャンクまたは部分の幅Ｌ≫ｗ；
（単一）スカラー乗算ｅ・ｇは、次のように出力される。
【００７０】
【数５】
2007526513.tif 000006
【００７１】
実施形態の第１の例と同様に、ここで、Ｌビットの後に、上のアルゴリズムが、１つのみの群乗算の代わりに、２つの群乗算を１列で行なうことが起こり得ることに留意すべきである。これは、チャンクｅｉの１つ（＝べき指数部分ｅｉの１つ）が、奇数を表す場合、および続くチャンクｅｉ＋１（＝続くべき指数部分ｅｉ＋ｊ）の再符号化が、１係数だけ長い（ｂＬはゼロに等しくない）場合に生じる。
【００７２】
実施形態の第５の例：マルチスカラー乗算
実施形態の第４の例（単一スカラー乗算）からの上のアルゴリズムは、マルチ（スカラー）乗算方法に変換することができる。ここで、マルチスカラー乗算は、加法的に書かれたアーベル群Ｇにおいて得られ、実施形態の上の第２の例（マルチ累乗）と比べて、明確な置換［←→マルチ累乗における自然要素“１”、“２乗”、“積”の代わりに、マルチスカラー乗算における自然要素“０”、“２倍”、“合計”］によって得られ、ほぼオンラインの再符号化の実施形態の第５の例の文脈において、アルゴリズムとして以下に示される。
【００７３】
ｄ＞１とする群要素ｇ１，・・・，ｇｄεＧと、べき指数ｅｉ，・・・，ｅｄが与えられ、かつΣｉ＝１ｄｅｉｇｉが計算されるべき場合、まず、べき指数ｅ１，・・・，ｅｄのスパース再符号化（sparse recoding）を使用する決定が行なわれ、次いで、“２乗および乗算（square-and-multiply）”ループが使用される。
【００７４】
まず、全ての倍数ｃ・ｇｉが計算および記憶され、ここでｃは、許容し得る正の係数である。仮変数ｘが、次いで０εＧに設定される。ｊ＝ｎ，ｎ−１，・・・，０について、ｘがまず２倍され、ｉ＝１，・・・，ｄについて、オペランドｅｉ，ｊ・ｇｉが、２倍されたｘに加えられ、ここでｅｉｊは、ｅｉの再符号化における２ｊの係数である。最後に、仮変数ｘは、所望の結果を含む。
【００７５】
この方法は、高速乗算と呼ぶこともできる。実施形態の第４の例に係る状況でのように、再び、良好な右から左への再符号化の利点を、多すぎるメモリを使用することなく保持することが望ましい。
【００７６】
以下の変形は、“ほぼオンライン”、すなわちほぼ高速マルチスカラー乗算の間、または高速マルチスカラー乗算のすぐ後の再符号化を行い、ここで、以下のものがアルゴリズムに入れられる。
―アーベル群Ｇの基本要素ｇ１，・・・，ｇｄ
―それぞれ多くともｎビットを有する整数ｅ１，・・・，ｅｄ（ｄ＞１）、
―窓の幅ｗ、
―チャンクまたは部分の幅Ｌ≫ｗおよび
―係数の集合において、全てのｃについて事前計算された倍数ｃ・ｇｉ
マルチスカラー積Σｉ＝１ｄｅｉ・ｇｉは、次のように出力される。
【数６】
2007526513.tif 000007
【００７７】
本明細書の最終部として、以下に、本文内に示された番号、要素、べき指数、群、インデックス、係数、集合、パラメータ、スカラー、変数、および数字の一覧を示す。
ｂｉ，ｊ  係数
ｂｉ，Ｌ  ２の最大の指数２Ｌに割り当てられた係数
ｃ  許容可能な正の係数
Ｃ  整数の有限集合
ｄ  群Ｇからの（基本または群）要素ｇｉの数
＝（基本または群）要素ｇｉに割り当てられたべき指数またはスカラーｅｉの数
ｅ  単一累乗の場合の、べき指数、特に整数のべき指数、または、単一スカラー乗算の場合の、スカラー、特に整数のスカラー
ｅｉ  マルチ累乗の場合の、べき指数、特に整数のべき指数、または、マルチスカラー乗算の場合の、スカラー、特に整数のスカラー
ｅｉ，ｋ−１  （べき指数またはスカラー）チャンクまたは（べき指数またはスカラー）部分ｅｉ，ｋに続く、（べき指数またはスカラー）チャンクまたは（べき指数またはスカラー）部分
ｅｉ，ｋ  分割されたべき指数またはスカラーｅｉの（べき指数またはスカラー）チャンクまたは（べき指数またはスカラー）部分
ｇ  単一累乗の場合、または単一スカラー乗算の場合における（基本または群）要素
ｇｉ  マルチ累乗の場合、またはマルチスカラー乗算の場合における（基本または群）要素
Ｇ  群、特にアーベル群
ｉ  インデックス
ｊ  インデックス、特に合計インデックス
ｋ  変数、特にインデックス付き変数
Ｌ  （べき指数またはスカラー）チャンクの幅または（べき指数またはスカラー）部分の幅、特に、（べき指数またはスカラー）チャンクの幅または（べき指数またはスカラー）部分の幅のビットレート
ｎ  最大ビットレートまたは最大ビット長
ｒ  （べき指数またはスカラー）チャンクまたは（べき指数またはスカラー）部分ｅｉ，ｋの数
ｗ  パラメータ
ｘ  仮変数
【国際調査報告】
2007526513.tif 000008