(57)【要約】本発明は、楕円曲線上の点の汎用計算方法に関する。本発明は、楕円曲線が四次方程式により定義され、同じプログラム式計算手段が、点の加算演算、点の倍加演算、および中性点の加算演算を行うために使用されることを特徴とする。計算手段は、特にメモリ（４，６，８）に関連する中央処理装置（２）を備える。本発明は、また、上記汎用方法を使用する暗号化方法に関する。さらに、本発明は、汎用計算方法および／または暗号化方法を実施するための構成要素に関する。例えば、本発明はスマートカードに適用することができる。
2005535927.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線上の点の汎用計算方法であって、前記楕円曲線は四次方程式により定義され、点の加算演算、点の倍加演算、および中性点の加算演算を行うために同じプログラム式計算手段が使用され、前記計算手段が、特にメモリ（４，６，８）に関連する中央処理装置（２）を備えることを特徴とする方法。
【請求項２】
前記楕円曲線が、下記のタイプの四次方程式により定義されることを特徴とする、請求項１に記載の方法：
Ｖ２＝ｂ．Ｕ４＋ａ．Ｕ３Ｗ＋ＵＷ３
ここで、（Ｕ：Ｖ：Ｗ）は、前記楕円曲線上の点Ｐのヤコビ投影座標であり、ａ、ｂは、前記楕円曲線のパラメータであり、座標（０：０：１）の点は前記楕円曲線の中性点Ｏであり、座標（Ｕ：−Ｖ：Ｗ）の点は座標（Ｕ：Ｖ：Ｗ）の前記点Ｐの反転点（−Ｐ）である。
【請求項３】
前記点Ｐが、アフィン座標（Ｘ，Ｙ）で定義され、前記点Ｐのアフィン座標（Ｘ，Ｙ）およびヤコビ投影座標（Ｕ：Ｖ：Ｗ）が、下記の関係：
（Ｘ，Ｙ）＝（Ｕ／Ｗ，Ｖ／Ｗ２）
によりリンクされることを特徴とする、請求項２に記載の方法。
【請求項４】
第１のヤコビ投影座標（Ｕ１：Ｖ１：Ｗ１）により定義される第１の点Ｐ１と第２のヤコビ投影座標（Ｕ２：Ｖ２：Ｗ２）により定義される第２の点Ｐ２の加算を行うために、前記第１の点Ｐ１の座標および前記第２の点Ｐ２の座標が、前記メモリ（４，６，８）の第１および第２のレジスタ内に記憶され、前記第１の点および前記第２の点が前記楕円曲線に属し、
前記プログラム式計算手段が、下式：
Ｕ３＝２．ｂ．Ｕ１２．Ｕ２２＋（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）．（Ｕ１．Ｗ２＋Ｗ１．Ｕ２）＋２Ｖ１．Ｖ２
Ｖ３＝（Ｕ１２．Ｖ２＋Ｕ２２．Ｖ１）＊（４ｂ．（Ｕ１．Ｗ２＋Ｕ２．Ｗ１）．Ｗ１．Ｗ２−８ｂ２．（Ｕ１．Ｕ２）２＋ａ．［（２Ｗ１．Ｗ２）２−（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）２］＋（Ｗ１２．Ｖ２＋Ｗ２２．Ｖ１）＊［（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）２−（２ａＵ１．Ｕ２）２＋４ｂＵ１．Ｕ２．（Ｗ１．Ｕ２＋Ｕ１．Ｗ２）］−４ｂＵ１．Ｕ２．（Ｕ１．Ｗ１．Ｖ２＋Ｕ２．Ｗ２．Ｖ１）（ａＵ１．Ｕ２−Ｗ１．Ｗ２）
Ｗ３＝（ａＵ１．Ｕ２−Ｗ１．Ｗ２）２−４ｂＵ１．Ｕ２（Ｕ１．Ｗ２＋Ｕ２．Ｗ１）
により、前記加算の結果である第３の点Ｐ３を定義する第３のヤコビ投影座標（Ｕ３：Ｖ３：Ｗ３）を計算し、
次に、前記第３の投影座標（Ｕ３：Ｖ３：Ｗ３）を前記メモリ（６，８）の第３のレジスタ内に記憶することを特徴とする、請求項２または３に記載の方法。
【請求項５】
前記楕円曲線が、次数２の１つの点を含む曲線であって、下記のタイプの四次方程式により定義され、
Ｖ２＝ε．Ｕ４−２δ．Ｕ２．Ｗ２＋Ｗ４
（Ｕ：Ｖ：Ｗ）が、前記楕円曲線上の点Ｐのヤコビ投影座標であり、ε、δが前記楕円曲線のパラメータであり、座標（０：１：１）の前記点が前記楕円曲線の中性点Ｏであり、座標（−Ｕ：＋Ｖ：Ｗ）の点が前記点Ｐ（Ｕ：Ｖ：Ｗ）の反転点（−Ｐ）であることを特徴とする、請求項１に記載の方法。
【請求項６】
第１のヤコビ投影座標（Ｕ１：Ｖ１：Ｗ１）により定義される前記第１の点Ｐ１と第２のヤコビ投影座標（Ｕ２：Ｖ２：Ｗ２）により定義される前記第２の点Ｐ２の加算を行うために、前記第１の点Ｐ１の座標および前記第２の点Ｐ２の座標が前記メモリ（４，６，８）の第１および第２のレジスタ内に記憶され、前記第１の点および前記第２の点が前記楕円曲線に属し、
前記プログラム式計算手段が、下式：
Ｕ３＝Ｕ１．Ｗ１．Ｖ２＋Ｖ１．Ｕ２．Ｗ２
Ｖ３＝［（Ｗ１．Ｗ２）２＋ε（Ｕ１．Ｕ２）２］＊［Ｖ１．Ｖ２−２δＵ１．Ｕ２．Ｗ１．Ｗ２］＋２ε．Ｕ１．Ｕ２．Ｗ１．Ｗ２（Ｕ１２Ｗ２２＋Ｗ１２Ｕ２２）
Ｗ３＝（Ｗ１．Ｗ２）２−ε（Ｕ１．Ｕ２）２
により、前記加算の結果である第３の点Ｐ３を定義する第３のヤコビ投影座標（Ｕ３：Ｖ３：Ｗ３）を計算し、
次に、前記第３の投影座標（Ｕ３：Ｖ３：Ｗ３）を前記メモリ（６，８）の前記第３のレジスタ内に記憶することを特徴とする、請求項５に記載の方法。
【請求項７】
前記楕円曲線が、下記のタイプの式によりアフィン座標で定義され、
Ｙ２＝ε．Ｘ４−２δ．Ｘ２＋１
（Ｘ，Ｙ）は前記楕円曲線上の点Ｐのアフィン座標であることを特徴とする、請求項５または６に記載の方法。
【請求項８】
第１のアフィン座標（Ｘ１，Ｙ１）により定義される前記第１の点Ｐ１と第２のアフィン座標（Ｘ２，Ｙ２）により定義される前記第２の点Ｐ２の加算を行うために、前記第１の点Ｐ１の座標および前記第２の点Ｐ２の座標が前記メモリ（４，６，８）の第１および第２のレジスタ内に記憶され、前記第１の点Ｐ１および前記第２の点Ｐ２が前記楕円曲線に属し、
前記プログラム式計算手段が、下式：
Ｘ３＝（Ｘ１．Ｙ２＋Ｙ１．Ｘ２）／［１−ε（Ｘ１．Ｘ２）２］
Ｙ３＝｛［１＋ε（Ｘ１．Ｘ２）２］．［Ｙ１．Ｙ２−２δ．Ｘ１．Ｘ２］＋２ε．Ｘ１．Ｘ２．（Ｘ１２＋Ｘ２２）｝／［１−ε（Ｘ１．Ｘ２）２］
により、前記加算の結果である第３の点Ｐ３を定義する第３のアフィン座標（Ｘ３，Ｙ３）を計算し、
次に、前記第３のアフィン座標（Ｘ３，Ｙ３）を前記メモリ（６，８）の前記第３のレジスタ内に記憶することを特徴とする、請求項７に記載の方法。
【請求項９】
前記楕円曲線が次数２の３つの点を有する曲線であり、ε＝１をパラメータとして有することを特徴とする、請求項５乃至８のいずれかに記載の方法。
【請求項１０】
楕円曲線上の点に適用されるスカラ乗算計算方法における、請求項１乃至９のいずれかに記載の計算方法の使用。
【請求項１１】
暗号化方法における、請求項１乃至９のいずれかに記載の計算方法の使用。
【請求項１２】
請求項１乃至９のいずれかに記載の方法を実施するためのプログラム式計算手段を備える電子構成要素であって、前記計算手段が、特にメモリ（４，６，８）に関連する中央処理装置（２）を備えることを特徴とする電子構成要素。
【請求項１３】
請求項１乃至９のいずれかに記載の方法を使用する暗号化アルゴリズムを実施するための手段を備える電子構成要素。
【請求項１４】
請求項１２または１３に記載の電子構成要素を備えるスマートカード。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、楕円曲線上の点に適用される汎用計算方法、および上記方法を実施するための手段を備える電子構成要素に関する。本発明は、特に例えば、スマートカードにおいて公開鍵タイプの暗号化アルゴリズムを実施するために適用することができる。
【背景技術】
【０００２】
楕円曲線上の公開鍵アルゴリズムを使用すれば、暗号化、デジタル署名、認証等のタイプの暗号アプリケーションが可能となる。
上記アルゴリズムは、スマートカード・タイプの用途に特に多く使用される。何故なら、これらのアルゴリズムを使用すれば、短い長さの鍵を使用することができ、処理時間をかなり短くすることができ、またこれらのアルゴリズムは、実施するために暗号化プロセッサを使用する必要がなく、そのためこれらアルゴリズムが実施される電子構成要素の製造コストを低減することができる。
【０００３】
さらに説明を進める前に、最初に楕円曲線について少し説明する必要がある。
楕円曲線上の点は、フィールドＫ上で定義され、グループ演算が＋で示す点の加算であり、Ｏで示す中性要素が識別されるアーベル群Ｅ（Ｋ）を形成する。
有限体の場合には、Ｅ（Ｋ）の基数は有限である。それ故、任意の点Ｐに対して下式のように１つの整数ｍが存在する。
Ｏ＝ｍ．Ｐ＝Ｐ＋Ｐ＋．．．＋Ｐ、（ｍ回加算）
それ故、任意の整数に対して、ｋ＜ｍであり、ｋ．Ｐ≠Ｏである。このような整数ｍはＰの次数と呼ばれる。この場合、Ｅ（Ｋ）の基数はｍにより割られる。
【０００４】
いくつかの曲線は特有の特性を有する。例えば、次数２の点を有する楕円曲線は、２で割ることができる基数を有する。または、次数３の点を有する楕円曲線は、グループＥ（Ｋ）の基数を３で割ることができる曲線である。同じ特有の特性を有する曲線は同じグループに分類される。
楕円曲線上の点は、いくつかのタイプの座標、例えば、アフィン座標またはヤコビ投影座標により表すことができる。
【０００５】
暗号化に適用することができる楕円曲線を定義するための種々のモデルが存在する。通常使用されるモデルは、いわゆるワイエルストラス・モデルである。ワイエルストラス・モデルは非常に包括的なものである。何故なら、このモデルはすべての楕円曲線を含むことができるからである。
【０００６】
各モデルは、異なるタイプの座標により使用することができる。
例えば、アフィン座標の場合、およびフィールドＫの指標ｐが２および３と異なる場合、ワイエルストラス・モデルは下記のように定義される。中性点Ｏ（ワイエルストラス・モデルにおける無限遠点）および一組の点（Ｘ，Ｙ）χＫ×Ｋは下式を満足させる。
Ｅ／Ｋ：Ｙ２＝Ｘ３＋ａ＊Ｘ＋ｂ  （Ｆ１）
【０００７】
４ａ３＋２７ｂ２≠０のようなａ、ｂχＫは、楕円曲線Ｅ（Ｋ）上で有理点のグループを形成する。点Ｐは、また、一般的な形（Ｕ，Ｖ，Ｗ）のヤコビ投影座標により表すことができる。（Ｘ，Ｙ）および（Ｕ，Ｖ，Ｗ）は、下式によりリンクされる。
Ｘ＝Ｕ／Ｗ  および  Ｙ＝Ｖ／Ｗ２  （Ｆ２）
【０００８】
これらのヤコビ投影座標を使用した場合、楕円曲線のワイエルストラス式は下式により表される。
Ｅ／Ｋ：Ｖ２＝Ｕ３＋ａ＊ＵＷ４＋ｂ＊Ｗ６  （Ｆ３）
投影座標は、楕円曲線上の点に適用される累乗計算の場合、特に有利である。何故なら、投影座標はフィールド内に逆計算を含んでいないからである。
【０００９】
式Ｆ２が示すように、１つの同じ点は、ヤコビ投影座標で種々の方法で表すことができる。また、下記の同値関係は、Ｋ３＼｛（０，０，０）｝上で定義される。座標が（Ｕ，Ｖ，Ｗ）および（Ｕ’，Ｖ’，Ｗ’）の２つの要素は等価であるといわれ、下式のようにＫのヌルでない要素λが存在している場合だけ同じ等価クラスに属する。
（Ｕ’，Ｖ’，Ｗ’）＝λＵ，λ２Ｖ，λＷ）  （Ｆ４）
このクラスの要素の座標は、（Ｕ：Ｖ：Ｗ）で表される。
【００１０】
楕円曲線を定義するモデルにより、また作業のために使用する座標により、点の加算、減算および倍加のための異なる式を適用することができる。ワイエルストラス・モデルの場合には、このような式は既知であり、周知の正割規則（ｓｅｃａｎｔ  ｒｕｌｅ）および正接規則（ｔａｎｇｅｎｔ  ｒｕｌｅ）により与えられる。
【００１１】
２および３とは異なる指標を有するフィールド上のアフィン座標のワイエルストラス・モデルにより与えられる楕円曲線Ｅの例の場合には、点の加算、減算および倍加のための最も簡単な式は下記の通りである。
曲線Ｅ上の点Ｐ１＝（Ｘ１，Ｙ１）の逆数は、下式による点−Ｐ１＝（Ｘ１，￣Ｙ１）である。
￣Ｙ１＝−Ｙ１  （Ｆ５）
【００１２】
この曲線上の座標が（Ｘ１，Ｙ１）である点Ｐ１、および座標が（Ｘ２，Ｙ２）である点Ｐ２を加算すると、Ｐ１≠−Ｐ２の場合には、その座標（Ｘ３，Ｙ３）が下式で表される点Ｐ３＝Ｐ１＋Ｐ２が得られる。
Ｘ３＝λ２−Ｘ１−Ｘ２  （Ｆ６）
Ｙ３＝λ×（Ｘ１−Ｘ３）−Ｙ１，  （Ｆ７）
この場合、
λ＝（Ｙ１−Ｙ２）／（Ｘ１−Ｘ２）、（Ｐ１≠Ｐ２の場合）  （Ｆ８）
λ＝（３×Ｘ１２＋ａ）／（２×Ｙ１）、（Ｐ１＝Ｐ２の場合）  （Ｆ９）
【００１３】
式Ｆ８は、２つの異なる点を加算するために使用され（Ｐ３＝Ｐ１＋Ｐ２）、一方、式Ｆ９は、点を倍加するために使用される（Ｐ３＝２×Ｐ１）。
Ｐ１および／またはＰ２が中性点Ｏと等しい場合には、式Ｆ６乃至Ｆ９は成立しない。ほとんどの場合、実際には、Ｐ３＝Ｐ１＋Ｏのタイプの演算は行われない。もっと簡単な場合には、Ｐ３＝Ｐ１＋Ｐ２のタイプの加算を行う前に、複数の点のうちの少なくとも１つが中性点Ｏに等しいかどうかの試験が行われる。次に、Ｐ１＝Ｏの場合には、演算Ｐ３＝Ｐ１が行われ、Ｐ２＝Ｏの場合には、演算Ｐ３＝Ｐ２が行われる。
【００１４】
点の加算または減算または倍加演算、および中性点の加算演算は、楕円曲線上のスカラ乗算アルゴリズムで使用される基本的な演算である。点Ｐ１がある楕円曲線Ｅに属していて、ｄが所定の数（整数）である場合には、数ｄによる点Ｐ１のスカラ乗算の結果は、Ｐ２＝ｄ×Ｐ１＝Ｐ１＋Ｐ１＋．．．＋Ｐ１、（ｄ回加算）のような曲線Ｅ上の点Ｐ２になる。Ｐ１の次数がｎである場合には、ｎ×Ｐ１＝Ｏ、（ｎ＋１）×Ｐ１＝Ｐ１＋Ｏ＝Ｐ１等になることに留意されたい。Ｏは中性点である。
【００１５】
楕円曲線上での公開鍵暗号化アルゴリズムは、所定の数ｄ、すなわち秘密鍵による曲線上の選択した点Ｐ１のスカラ乗算をベースとしている。このスカラ乗算ｄ×Ｐ１の結果は、楕円曲線上の点Ｐ２である。エルガマル法による暗号化への適用の一例の場合には、得られた点Ｐ２は、メッセージを暗号化するために使用する公開鍵である。
【００１６】
スカラ乗算Ｐ２＝ｄ×Ｐ１の計算は、種々のアルゴリズムにより行うことができる。その中のいくつかを引用することができる。そのようなアルゴリズムとしては、乗数ｄの２進表示をベースとする倍加および加算アルゴリズム、乗数ｄの符号付き２進表示をベースとするいわゆる「加算／減算」アルゴリズム、ウィンドウ・アルゴリズム等がある。
【００１７】
これらすべてのアルゴリズムは、加算、減算、倍加および楕円曲線上で定義された中性点の加算のための式を使用する。
しかし、これらのアルゴリズムは、特に秘密鍵ｄの値を発見しようとする攻撃に弱いことがわかっている。特に単純または差分カバート・チャネル攻撃（ｄｉｆｆｅｒｅｎｔｉａｌ  ｃｏｖｅｒｔ  ｃｈａｎｎｅｌ  ａｔｔａｃｋ）を挙げることができる。
【００１８】
単純または差分カバート・チャネル攻撃は、デバイスの外部から測定することができ、その直接的分析（単純攻撃）または統計的方法（差分攻撃）による分析により、デバイス内に含まれている、また処理の際に操作された情報を発見することができる物理量をベースとしている攻撃を意味する。それ故、これらの攻撃により秘密情報を知ることができる。これらの攻撃については、特に、D１（下記非特許文献１）に詳細に開示されている。これらの目的のために使用することができる物理量の中から、実行時間、電流消費、計算を実行するために使用する構成要素の一部により照射された電磁界等を挙げることができる。これらの攻撃は、ビットの乗算、すなわち特定の命令によるその処理は、このビットの値によるおよび／または命令による当該物理量上に特定の影響を与えるという事実をベースとしている。
【００１９】
楕円曲線をベースとする暗号化システムにおいては、これらの攻撃の目的は、連続的に行われた一組の演算内の演算（例えば、Ｐ３＝Ｐ１＋Ｐ２タイプの点の加算、Ｐ３＝Ｐ１＋Ｏタイプの加算、またはＰ３＝ｄ＊Ｐ１タイプのスカラ乗算）を識別することである。
ワイエルストラス・モデルによる楕円曲線上でのスカラ乗算アルゴリズムの上記例を取り上げると、このアルゴリズムは単純カバート・チャネル攻撃に弱い場合がある。何故なら、点の倍加、点の加算、または中性点の加算の基本的演算は、上式Ｆ８およびＦ９内のラムダの計算で示すように、かなり異なっているからである。
【００２０】
それ故、種々の攻撃が成功するのを防止することができる対抗手段を講じる必要がある。すなわち、スカラ乗算アルゴリズムを機密保護する必要がある。
このため、Ｄ２（下記非特許文献２）から、点を倍加する演算、点を加算する演算のための１つの定式化は周知である。それ故、２つの演算は、もはやカバート・チャネル攻撃により識別することはできない。しかし、この定式化は、中性点の加算演算を実行するのに役に立たないという欠点がある。
【００２１】
Ｄ３（下記非特許文献３）から、点の加算演算および倍加演算の１つの定式化も周知である。しかし、この定式化は、次数２の３つの点を有する楕円曲線のコンテキスト内でしか適用することができない。さらに、Ｄ３が提案しているこの定式化は、実施するのにかなりのメモリ空間を必要とする。何故なら、これらの点は４つの座標で記憶されるからである。これはスマートカード・タイプ用に簡単に使用することはできない。
Ｄ４（下記非特許文献４）から、点の加算演算および点の倍加演算の１つの定式化も周知である。しかし、この定式化は、次数３の点を有する楕円曲線だけにしか適用することができない。
Ｄ３およびＤ４は、中性点の加算の問題に言及していない。
【００２２】
【非特許文献１】Paul Kocher, Joshua Jaffe and Benjamin Jun. Differential Power Analysis. Advances in Cryptology  CRYPTO '99, vol.1666 of Lecture Notes in Computer Science, pp. 388-397. SpringerVerlag, 1999
【非特許文献２】Eric Brier and Marc Joye. Weierstrass elliptic curves and side-channel attacks. In D. Naccache, editor, Public Key Cryptography, volume 2274 of Lecture Notes in Computer Science, pages 335-345. SpringerVerlag, 2002
【非特許文献３】Pierre-Yvan Liardet and Nigel P. Smart. Preventing SPA/DPA in ECC systems using the Jacobi form. In C.K.Koc, D. Naccache, and C. Paar, editors, Cryptographic Hardware and Embedded Systems  CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 391-401. SpringerVerlag, 2001
【非特許文献４】Marc Joye and Jean-Jacques Quisquater. Hessian elliptic curves and side-channel attacks. In C.K.Koc, D. Naccache, and C. Paar, editors, Cryptographic Hardware and Embedded Systems  CHES 2001, volume 2162 of Lecture Notes in Computer Science, pages 402-410. Springer-Verlag, 2001
【発明の開示】
【発明が解決しようとする課題】
【００２３】
本発明の１つの目的は、周知の解決方法よりも効率的なカバート・チャネル攻撃、特にＳＰＡ攻撃に対する保護についての解決方法を提案することである。
本発明のもう１つの目的は、例えば、スマートカード・タイプの用途用に、使用できるメモリ空間が広くない回路で実施することができる解決方法を提案することである。
【課題を解決するための手段】
【００２４】
これらの目的は、２つの異なる点の加算、点の倍加、および中性点の加算演算の実行を可能にする１つの定式化により本発明で達成される。さらに、本発明による上記定式化は最小限度のものである。それ故、実行する演算の数およびその実施のために必要なメモリ空間が少なくてすむ。
それ故、本発明は、楕円曲線上の点の汎用計算方法に関する。本発明によれば、楕円曲線は四次方程式により定義され、同じプログラム式計算手段が、点の加算演算、点の倍加演算、および中性点の加算演算を行うために使用される。上記計算手段は、特にメモリに関連する中央処理装置を備える。
【００２５】
すなわち、本発明によれば、四次方程式（すなわち、四次の多項式）の形をしている楕円曲線のモデルを使用することにより、点の加算、点の倍加、および曲線の中性点の加算演算を実行するために１つの定式化を使用することができる。
この場合、カバート・チャネル攻撃のような攻撃により、これら演算のうちの１つを他の演算から識別することができなくなる。
さらに、四次方程式の形をしている曲線のモデルを使用することにより、３つの投影座標だけで点を表すことができるようになり、それにより、点の座標を記憶するために必要なメモリ空間が少なくてすみ、点上での演算中の計算時間が短縮する。
【００２６】
最後に、例を見ればよりよく理解することができるように、３つのタイプの加算（２つの異なる点の加算、複数の点の倍加、および中性点の加算）を実行するための本発明により入手した１つの定式化の場合、乗算タイプの基本操作の数が少なくてすみ、それにより必要な計算時間がさらに短縮され、メモリ空間が少なくてすむ。
【００２７】
本発明は、また楕円曲線上の点および／または暗号化方法で適用されるスカラ乗算計算方法での上記汎用計算方法の使用に関する。
本発明は、また上記汎用計算方法または上記汎用計算方法を使用する暗号化方法を実施するためのプログラム式計算手段を備える電子構成要素に関する。上記計算手段は、特にメモリに関連する中央処理装置を備える。
最後に、本発明は、また、上記電子構成要素を備えるスマートカードに関する。
１枚の添付の図面を参照しながら、単に例示としてのものに過ぎない本発明の特定の例示としての実施形態の以下の説明を読めば、本発明およびその利点をよりはっきり理解することができるだろう。
【発明を実施するための最良の形態】
【００２８】
下記の例の場合、デバイス１は、暗号化プログラムを実行するためのスマートカードである。そのために、デバイス１は、チップ内で下記のものを含む一組のメモリに機能的に接続している中央処理装置２からなるプログラム式計算手段を組合わせる。
・マスクＲＯＭ（マスク読取専用メモリ）タイプの例において、読出しモードの場合だけアクセスすることができるメモリ４；
・ＥＥＰＲＯＭ（電気的に消去可能なプログラマブルＲＯＭ）タイプの例において、電気的に再プログラムすることができるメモリ６；
・ＲＡＭ（ランダム・アクセス・メモリ）タイプの例の、読出しモードおよび書込みモードでアクセスすることができる作業メモリ８。このメモリは、特にデバイス１が使用する計算レジスタを備える。
【００２９】
スカラ乗算アルゴリズムに対応する実行可能なコードは、プログラム・メモリに内蔵されている。このコードは、実際には、読出しモードの時だけアクセスすることができるメモリ４、および／または再書き込み可能なメモリ６に内蔵することができる。
中央処理装置２は、外部およびチップ用電源と信号の交換をする通信インタフェース１０に接続している。このインタフェースは、いわゆる「無接点」カードの場合、読出装置および／またはアンテナと、いわゆる「接点」接続を行うためにカード上にパッドを備えることができる。
【００３０】
デバイス１の機能のうちの１つは、それぞれ外部へ送信、または外部から受信した秘密メッセージｍを暗号化または解読することである。このメッセージは、例えば、個人コード、医療情報、銀行口座または商取引、ある制限されているサービスにアクセスするための許可等に関連することができる。もう１つの機能は、デジタル署名を計算し、確認することである。
【００３１】
これらの機能を実行するために、中央処理装置２は、マスクＲＯＭ４および／またはＥＥＰＲＯＭ６部分に記憶しているプログラミング・データに対して暗号化アルゴリズムを実行する。
ここで使用するアルゴリズムは、四次方程式の形をしているモデルのコンテキスト内の楕円曲線上の公開鍵アルゴリズムである。もっと正確に言うと、この場合重要なのは、基本演算、すなわち、加算演算、２つの異なる点、２つの同じ点（すなわち、１つの点の倍加演算）、またはすべての任意の点および中性点の加算の実行を可能にするこのアルゴリズムの一部であることである。
【００３２】
本発明によれば、これら３つの演算を同じ定式化により実行されること、およびそれ故、単純カバート・チャネル攻撃に対して外部から相互に識別できないことに留意されたい。
本発明のコンテキスト内においては、重要なものは、通常使用されるワイエルストラス三次方程式の代わりに、四次方程式により定義される楕円曲線モデルである。
【００３３】
アフィン座標の四次方程式の一般的な形は下式により表される。
Ｙ２＝ａ０．Ｘ４＋ａ１．Ｘ３＋ａ２．Ｘ２＋ａ３．Ｘ＋ａ４  （Ｆ１０）
【００３４】
または、ヤコビ投影座標においては、下式により表される。
Ｖ２＝ａ０．Ｕ４＋ａ１．Ｕ３Ｗ＋ａ２．Ｕ２Ｗ２＋ａ３．ＵＷ３＋ａ４Ｗ４  （Ｆ１１）
【００３５】
同じ点のアフィン座標およびヤコビ投影座標が下記の関係によりリンクされていることが分かっている場合には、
（Ｘ，Ｙ）＝（Ｕ／Ｗ，Ｖ／Ｗ２）  （Ｆ１２）
となる。
【００３６】
本発明の第１の例示としての実施形態の場合には、すべての任意の楕円曲線が考慮され、Ｐ１、Ｐ２のようなすべての任意の２つの点が楕円曲線上に位置する状態で、Ｐ３＝Ｐ１＋Ｐ２タイプの演算が行われる。Ｐ２はＰ１とは異なるものであっても、Ｐ１に等しくても、および／または曲線の中性点Ｏに等しくてもよい。加算はヤコビ投影座標で行われる。
【００３７】
式：Ｙ２＝Ｘ３＋ａ．Ｘ＋ｂ（ワイエルストラス式）による任意の曲線は、二有理的に下式による曲線と等価であることが分かっている。
Ｙ２＝ｂ．Ｘ４＋ａ．Ｘ３＋Ｘ  （Ｆ１３）
式Ｆ１３は、最終的には、ａ０＝ｂ、ａ１＝ａ、ａ２＝０、ａ３＝１、ａ４＝０の場合の式Ｆ１０の特殊な場合である。
【００３８】
また、同値関係Ｆ１２により、式Ｆ１３をヤコビ投影座標で描くことができることが分かっている。
Ｖ２＝ｂ．Ｕ４＋ａ．Ｕ３Ｗ＋ＵＷ３  （Ｆ１４）
【００３９】
加算演算を行うためにスカラ乗算計算デバイスを呼び出した場合には、中央処理装置２は、最初に、計算レジスタ内に、加算する楕円曲線上の点Ｐ１、Ｐ２の座標（Ｕ１：Ｖ１：Ｗ１）および（Ｕ２：Ｖ２：Ｗ２）を記憶する。
【００４０】
中央処理装置２は、次に、下式により点Ｐ３の座標を計算する。
Ｕ３＝２．ｂ．Ｕ１２．Ｕ２２＋（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）．（Ｕ１．Ｗ２＋Ｗ１．Ｕ２）＋２Ｖ１．Ｖ２  （Ｆ１５）
Ｖ３＝（Ｕ１２．Ｖ２＋Ｕ２２．Ｖ１）＊（４ｂ．（Ｕ１．Ｗ２＋Ｕ２．Ｗ１）．Ｗ１．Ｗ２−８ｂ２．（Ｕ１．Ｕ２）２＋ａ．［（２Ｗ１．Ｗ２）２−（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）２］＋（Ｗ１２．Ｖ２＋Ｗ２２．Ｖ１）＊［（ａＵ１．Ｕ２＋Ｗ１．Ｗ２）２−（２ａＵ１．Ｕ２）２＋４ｂＵ１．Ｕ２．（Ｗ１．Ｕ２＋Ｕ１．Ｗ２）］−４ｂＵ１．Ｕ２．（Ｕ１．Ｗ１．Ｖ２＋Ｕ２．Ｗ２．Ｖ１）（ａＵ１．Ｕ２−Ｗ１．Ｗ２）  （Ｆ１６）
Ｗ３＝（ａＵ１．Ｕ２−Ｗ１．Ｗ２）２−４ｂＵ１．Ｕ２（Ｕ１．Ｗ２＋Ｕ２．Ｗ１）  （Ｆ１７）
【００４１】
点Ｐ３の座標（Ｕ３：Ｖ３：Ｗ３）は、例えば、暗号化アルゴリズムの残りのために、他の場所で使用する目的で、最終的に作業メモリ８内のレジスタに記憶される。
Ｐ１＝Ｐ２（点の倍加）の場合、またはＰ２＝Ｏ（０：０：１）（中性点の加算）の場合でも、式Ｆ１５乃至Ｆ１７が使用できるかどうかの確認が行われる。
【００４２】
本発明の第２の例示としての実施形態の場合には、アフィン座標（θ，０）による次数２の１つの点を有する楕円曲線が考慮され、Ｐ１、Ｐ２のようなすべての任意の２つの点が楕円曲線上に位置する状態で、Ｐ３＝Ｐ１＋Ｐ２タイプの演算が行われる。この場合、Ｐ２はＰ１と異なっていても、Ｐ１と等しくても、および／または曲線の中性点Ｏに等しくてもよい。加算演算はヤコビ投影座標で行われる。
【００４３】
楕円曲線を定義しているワイエルストラス式を満足する次数２の点θは、下式により定義される。
θ３＋ａ．θ＋ｂ＝０
この場合、下式により表され、
Ｙ２＝Ｘ３＋ａ．Ｘ＋ｂ（ワイエルストラス式）
次数２の１つの点（θ，０）を有する任意の曲線は、二有理的に下式により表される曲線と等価であることが分かっている。
【００４４】
Ｙ２＝ε．Ｘ４−２δ．Ｘ２＋１  （Ｆ１８）
ここで、
ε＝−（ａ＋３θ２／４）／４  および  δ＝３θ／４  （Ｆ１９）
式Ｆ１８は、最終的には、ａ０＝ε、ａ１＝０、ａ２＝−２δ、ａ３＝０、ａ４＝１の場合の、式１０の特殊な場合である。
また、同値関係Ｆ１２により、式Ｆ１８をヤコビ投影座標に描くことができることが分かっている。
Ｖ２＝ε．Ｘ４−２δ．Ｕ２Ｘ２＋Ｗ４  （Ｆ２０）
【００４５】
三次モデルＹ２＝Ｘ３＋ａＸ＋ｂから四次モデルＹ２＝ε．Ｘ４−２δ．Ｘ２＋１への変更は、下記変換により行われる。
ワイエルストラス・モデル  四次モデル
（θ，０）ξ（０：−１：１）
（Ｘ，Ｙ）ξ（２（Ｘ−θ）：（２Ｘ＋θ）（Ｘ−θ）２−Ｙ２：Ｙ）
Ｏ  ξ  （０：１：１）
【００４６】
四次モデル  ワイエルストラス・モデル
（０：１：１）ξＯ
（０：−１：１）ξ（θ，０）
（Ｕ：Ｖ：Ｗ）ξ（２（Ｖ＋Ｗ２）／Ｕ２−θ／２，Ｗ（４Ｖ＋４Ｗ２−３θＵ２）Ｕ３）
この四次モデルに対して、点−Ｐ（−Ｕ：Ｖ：Ｗ）により中性点Ｏ（０：１：１）および点Ｐ（Ｕ：Ｖ：Ｗ）の反転点が定義される。
【００４７】
加算演算を行うために累乗計算デバイスを呼び出した場合には、中央処理装置２は、最初に、計算レジスタ内に、加算する楕円曲線上の点Ｐ１、Ｐ２の座標（Ｕ１：Ｖ１：Ｗ１）および（Ｕ２：Ｖ２：Ｗ２）を記憶する。
【００４８】
中央処理装置２は、次に、下式により点Ｐ３の座標を計算する。
Ｕ３＝Ｕ１．Ｗ１．Ｖ２＋Ｖ１．Ｕ２．Ｗ２  （Ｆ２１）
Ｖ３＝［（Ｗ１．Ｗ２）２＋ε（Ｕ１．Ｕ２）２］＊［Ｖ１．Ｖ２−２δＵ１．Ｕ２．Ｗ１．Ｗ２］＋２ε．Ｕ１．Ｕ２．Ｗ１．Ｗ２（Ｕ１２Ｗ２２＋Ｗ１２Ｕ２２）  （Ｆ２２）
Ｗ３＝（Ｗ１．Ｗ２）２−ε（Ｕ１．Ｕ２）２  （Ｆ２３）
【００４９】
点Ｐ３の座標（Ｕ３：Ｖ３：Ｗ３）は、例えば、暗号化アルゴリズムの残りのために、他の場所で使用する目的で最終的に作業メモリ８のレジスタ内に記憶される。
この場合も、Ｐ１＝Ｐ２（点の倍加）の場合またはＰ２＝Ｏ（中性点の加算）の場合でも、式Ｆ２１乃至Ｆ２３が使用できるかどうかの確認が行われる。
【００５０】
本発明の第３の例としての実施形態の場合には、楕円曲線が次数２の３つの点を有し、ε＝１であるような第２の例の特殊な場合が考慮される。また、Ｐ３＝Ｐ１＋Ｐ２タイプの演算が行われる。この場合、Ｐ１、Ｐ２は、楕円曲線上のすべての任意の２つの点である。Ｐ２は、Ｐ１と異なっていても、Ｐ１と等しくても、および／または曲線の中性点Ｏに等しくてもよい。加算演算は、アフィン・モデルＹ２＝Ｘ４＋２δ．Ｘ２＋１に対応するモデルＵ４−２δ．Ｕ２．Ｗ２＋Ｗ４に対するヤコビ投影座標で行われる。
【００５１】
式Ｆ２４は、最終的には、ａ０＝１、ａ１＝０、ａ２＝−２δ、ａ３＝０、ａ４＝１の場合の最も一般的な式Ｆ１０の特殊な場合である。
加算演算を行うために累乗計算デバイスを呼び出した場合には、中央処理装置２は、最初に、計算レジスタ内に、加算する楕円曲線上の点Ｐ１、Ｐ２の座標（Ｕ１：Ｖ１：Ｗ１）および（Ｕ２：Ｖ２：Ｗ２）を記憶する。
【００５２】
中央処理装置２は、次に、下式により点Ｐ３の座標を計算する。
Ｕ３＝Ｕ１．Ｗ１．Ｖ２＋Ｖ１．Ｕ２．Ｗ２  （Ｆ２７）
Ｖ３＝［（Ｗ１．Ｗ２）２＋（Ｕ１．Ｕ２）２］＊［Ｖ１．Ｖ２−２δＵ１．Ｕ２．Ｗ１．Ｗ２］＋２Ｕ１．Ｕ２．Ｗ１．Ｗ２（Ｕ１２Ｗ２２＋Ｗ１２Ｕ２２）  （Ｆ２８）
Ｗ３＝（Ｗ１．Ｗ２）２−（Ｕ１．Ｕ２）２  （Ｆ２９）
【００５３】
点Ｐ３の座標（Ｕ３：Ｖ３：Ｗ３）は、例えば、暗号化アルゴリズムの残りのために、他の場所で使用する目的で、最終的に作業メモリ８のレジスタ内に記憶される。
この場合も、Ｐ１＝Ｐ２（点の倍加）の場合またはＰ２＝Ｏ（中性点の加算）の場合でも、式Ｆ２７乃至Ｆ２９が使用できるかどうかの確認が行われる。
【００５４】
実際に実施する見地から、式Ｆ２７乃至Ｆ２９を下記のように実施することができる。
ｒ１  ρ  ｕ１．ｕ２
ｒ２  ρ  ｗ１．ｗ２
ｒ３  ρ  ｒ１．ｒ２
ｒ４  ρ  ｖ１．ｖ２
ｒ５  ρ  ｕ１．ｗ１＋ｖ１
ｒ６  ρ  ｕ２．ｗ２＋ｖ２
ｕ３  ρ  ｒ５．ｒ６−ｒ４−ｒ３
ｗ３  ρ  （ｒ２−ｒ１）.（ｒ２＋ｒ１）
ｒ６  ρ  δ＊ｒ３
ｒ４  ρ  ｒ４−２．ｒ６
ｒ６  ρ  （ｒ２＋ｒ１）２−２ｒ３
ｒ４  ρ  ｒ４．ｒ６
ｒ６  ρ  （ｕ１＋ｗ１）．（ｕ２＋ｗ２）−ｒ１−ｒ２
ｒ５  ρ  ｒ６２−２ｒ３
ｒ６  ρ  ｒ５．ｒ３
ｖ３  ρ  ｒ４＋２．ｒ６
【００５５】
ここで、ｕ１、ｖ１、ｗ１、ｕ２、ｖ２、ｗ２、ｕ３、ｖ３、ｗ３は、点Ｐ１、Ｐ２およびＰ３の投影座標が記憶される計算レジスタであり、ｒ１乃至ｒ６は、一時的計算レジスタである。
それ故、この実施形態によれば、点Ｐ３の座標は、２つのレジスタの内容の乗算のためにかかる時間の約１３倍に、ある定数によりレジスタの内容を乗算するためにかかる時間の１倍を加えたものに等しい時間で入手することができる。それ故、本発明による定式化によりＰ３の座標を計算するのに必要な時間は、従来技術のような定式化によるＰ３の座標の計算に必要な時間より遥かに短い。
【００５６】
この近似は完全に現実的なものであることに留意されたい。何故なら、ある定数によりレジスタの内容を乗算するのに必要な時間、または２つのレジスタの内容を乗算するのに必要な時間は、実際には、２つのレジスタの内容の加算を行うのに必要な時間より遥かに長いからである。
このことは、式Ｆ１５乃至Ｆ１７または式Ｆ２１乃至Ｆ２３を実施する場合にも当てはまる。
【００５７】
本発明の第４の例としての実施形態の場合には、アフィン座標（θ，０）の次数２の１つの点を有する楕円曲線が考慮され、Ｐ３＝Ｐ１＋Ｐ２タイプの演算が行われる。この場合、Ｐ１、Ｐ２は、楕円曲線上のすべての任意の２つの点である。Ｐ２は、Ｐ１と異なっていても、Ｐ１と等しくても、および／または曲線の中性点Ｏに等しくてもよい。
第２の例に示すように、θ３＋ａ．θ＋ｂ＝０である。
【００５８】
次のワイエルストラス式：Ｙ２＝Ｘ３＋ａ．Ｘ＋ｂによる次数２の１つの点（θ，０）を有する曲線は、二有理的に下式による曲線と等価である。
Ｙ２＝ε．Ｘ４−２δ．Ｘ２＋１  （Ｆ１８）
ここで、ε＝−（ａ＋３θ２／４）／４およびδ＝３θ／４  （Ｆ１９）
この例の場合には、加算演算はアフィン座標で行われる。
加算演算を行うために累乗計算デバイスを呼び出した場合には、中央処理装置２は、最初に、計算レジスタ内に、加算する楕円曲線上の点Ｐ１、Ｐ２の座標（Ｘ１，Ｙ１）および（Ｘ２，Ｙ２）を記憶する。
【００５９】
中央処理装置２は、次に、下式により点Ｐ３の座標を計算する。
Ｘ３＝（Ｘ１．Ｙ２＋Ｙ１．Ｘ２）／［１−ε（Ｘ１．Ｘ２）２］  （Ｆ３０）
Ｙ３＝｛［１＋ε（Ｘ１．Ｘ２）２］．［Ｙ１．Ｙ２−２δ．Ｘ１．Ｘ２］＋２ε．Ｘ１．Ｘ２．（Ｘ１２＋Ｘ２２）｝／［１−ε（Ｘ１．Ｘ２）２］  （Ｆ３１）
【００６０】
点Ｐ３の座標（Ｘ３，Ｙ３）は、例えば、暗号化アルゴリズムの残りのために、他の場所で使用する目的で、最終的に作業メモリ８のレジスタ内に記憶される。
この場合も、Ｐ１＝Ｐ２（点の倍加）の場合、またはＰ２＝Ｏ（中性点の加算）の場合でも、式Ｆ３０乃至Ｆ３１が使用できるかどうかの確認が行われる。
【図面の簡単な説明】
【００６１】
【図１】暗号化計算を行うことができる電子デバイス１のブロック図である。
【図１】
2005535927.tif 000003
【国際調査報告】
2005535927.tif 000004
2005535927.tif 000005
2005535927.tif 000006
2005535927.tif 000007