JP2002540483A

JP2002540483A - 楕円曲線型公開鍵暗号化アルゴリズムを用いる電子構成部品内の対抗措置方法

Info

Publication number: JP2002540483A
Application number: JP2000608545A
Authority: JP
Inventors: コロン，ジャン−セバスチャン
Original assignee: Gemplus SA
Current assignee: Gemplus SA
Priority date: 1999-03-26
Filing date: 2000-03-13
Publication date: 2002-11-26
Also published as: WO2000059156A1; AU3296500A; FR2791497B1; DE60042448D1; ES2331456T3; EP1166494B1; US7162033B1; CN1345495A; EP1166494A1; ATE434879T1; MXPA01009498A; FR2791497A1

Abstract

(57)【要約】楕円曲線に基づく暗号化アルゴリズムは、計算時間をより短くし、鍵のサイズをより小さくするという利点をＲＳＡに備えた公開鍵式アルゴリズムである。チップカード型環境の枠内でそれらを応用した場合、ＤＰＡ（電力差分解析）型の攻撃に弱いことが分かった。本発明は、このタイプのＤＰＡ攻撃に対して備えることを可能にする対抗措置方法を説明することから成る。この対抗措置は性能を低下させず、チップカード型の構成部品内で容易に利用することができる。

Description

【発明の詳細な説明】

【０００１】本発明は、楕円曲線型の公開鍵暗号化アルゴリズムを用いる電子構成部品にお
ける対抗措置方法に関するものである。

【０００２】秘密鍵暗号方式の従来のモデルでは、安全化されていない経路を介して通信し
たいと望む２人は、前もって、暗号化の秘密鍵Kについて合意しておかなければ
ならない。暗号化関数および復号化関数は、同じ鍵Kを用いる。秘密鍵暗号シス
テムの欠点は、前記システムが、安全化されていない経路を介して何らかの暗号
化メッセージを送信する前に、安全化された経路を介して２人の間の鍵Kを予め
通信しておくことを要することである。実際には、完璧に安全化された通信経路
を見つけるのは一般に難しく、２人を隔てる距離が大きい場合は特に難しい。安
全化された経路とは、前記経路を通過する情報を知ること、または変更すること
が不可能である経路を意味する。このような安全化された経路は、前記２人が所
有する２つの端末を接続するケーブルとすることができる。

【０００３】公開鍵暗号方式のコンセプトは、Whitfield DIFFIEおよびMartin HELLMANに
よって１９７６年に発明された。公開鍵暗号方式により、安全化されていない経
路を介しての鍵配布の問題を解決することができる。公開鍵暗号方式の原理は、
一対の鍵、即ち暗号化の公開鍵および復号化の秘密鍵を用いることから成る。暗
号化の公開鍵から復号化の秘密鍵を見つけるのは、計算上できないことになって
いる。人Ｂに情報を伝達したいとを望む人Ａは、人Ｂの暗号化の公開鍵を用いる
。人Ｂのみがその公開鍵と関連する秘密鍵を所有している。したがって、人Ｂの
みが、自分宛てのメッセージを復号化することができる。

【０００４】秘密鍵暗号方式に対する公開鍵暗号方式の別の利点は、公開鍵暗号方式により
、電子署名の使用による認証が可能になることである。

【０００５】公開鍵暗号の体系の最初の実現は、暗号システムRSAを発明したRivest、Shami
rおよびAdlemanによって１９７７年に開発された。RSAの安全性は、２つの素数
の積である大きな数を因数分解する難しさの上に成り立つものである。

【０００６】それ以来、安全性が多様な計算問題の上に成り立っている数多くの公開鍵暗号
システムが提案されている：（このリストは全部を網羅するものではない）。 −Merckle-Hellmanのナップサック：この暗号システムは、部分集合の和の問題の難しさに基づくものである
。 −McEliece：この暗号システムは、代数符号の理論に基づくものである。それは、線
形符号の復号化の問題に基づく。 −ElGamal：この暗号システムは、有限体における離散対数の難しさに基づくもので
ある。 −楕円曲線：楕円曲線暗号システムは、楕円曲線の領域において適用するための既存
の暗号システムの修正型である。

【０００７】暗号システムにおける楕円曲線の使用は、１９８５年に、Victor Millerおよ
びNeal Koblitzによって、独立に提唱された。楕円曲線の実際への応用は、１
９９０年代の初めに検討された。

【０００８】楕円曲線を基にした暗号システムの利点は、他の暗号システムと同等の安全性
を、より小さいサイズの鍵で提供することである。鍵のサイズによるこの利益は
、メモリの必要性の減少および計算時間の削減をもたらし、それによって、チッ
プカードタイプの応用に特に適した楕円曲線が使用されることとなる。

【０００９】有限体ＧＦ（ｑ＾ｎ）（ｑは素数であり、ｎは整数である）上の楕円曲線は、
次の方程式の解ＧＦ（ｑ＾ｎ）に属する点（ｘ，ｙ）の集合であり、ここでｘは
横座標、ｙは縦座標である：ｑが３以上であるときｙ＾２＝ｘ＾３＋ａ＊ｘ＋ｂｑ＝２であるときｙ＾２＋ｘ＊ｙ＝ｘ＾３＋ａ＊ｘ＾２＋ｂ

【００１０】楕円曲線上の１点を表すための２つの方法が存在する。第一は、アフィン座標表示である。この方法では、楕円曲線上の点Ｐは、その
座標（ｘ，ｙ）で表される。第二は、射影座標表示である。

【００１１】射影座標表示の利点は、有限体内の除算を避けることができることであって、
前記除算とは計算時間を最も必要とする演算である。

【００１２】最も一般的に用いられている射影座標表示は、楕円曲線上の点Ｐを、ｘ＝Ｙ／
Ｚで、ｙ＝Ｙ／Ｚ＾３である座標（Ｘ，Ｙ，Ｚ）によって表すことから成るもの
である。

【００１３】ある点の射影座標は一意ではなく、なぜなら３つの要素（Ｘ，Ｙ，Ｚ）と３つ
の要素（λ＾２＊Ｘ，λ＾３＊Ｙ，λ＊Ｚ）は、楕円曲線が規定される有限体に
属する要素λに関係なく同じ点を表すからである。

【００１４】暗号方式において最も良く利用される曲線の２つのクラスは、以下の通りであ
る：１）以下の方程式を有する、有限体ＧＦ（ｐ）（ｐは素数であって、ｐを
法とする整数の集合）上で規定される曲線：ｙ＾２＝ｘ＾３＋ａ＊ｘ＝ｂ２）式ｙ＾２＋ｘ＊ｙ＝ｘ＾３＋ａ＊ｘ＾２＋ｂを有する、有限体ＧＦ（
２＾ｎ）上で規定される曲線

【００１５】これらの２つのクラスの曲線のそれぞれについて、点の加算および点の倍算の
演算を定義する。

【００１６】点の加算とは、２点をＰおよびＱとすると、和Ｒ＝Ｐ＋Ｑを計算する演算であ
り、Ｒは曲線の一点であって、その座標はAlfred J. Menezesの著作“楕円曲
線公開鍵暗号システム（Elliptic curve public key cryptosystem）”に記
されている式に従う点ＰおよびＱの座標で表される。

【００１７】点の倍算とは、点Ｐが与えられたとき、点Ｒ＝２＊Ｐを計算する演算であり、
Ｒは曲線上の点であって、該曲線の座標は、ＡｌｆｒｅｄＪ．Ｍｅｎｅｚｅｓ
の著作"楕円曲線公開鍵暗号システム（Elliptic curve public key cryptosyste
m）"に記されている式に従う点Ｐ座標で表される。

【００１８】点の加算および点の倍算の演算によって、スカラー乗算の演算を定義すること
ができる。Ｐを楕円曲線に属する点、ｄを整数とすると、Ｐとｄとのスカラー乗
算の結果は、Ｑ＝ｄ＊Ｐ＝Ｐ＋Ｐ＋…＋Ｐをｄ回のようになる点Ｑとなる。

【００１９】楕円曲線における暗号化アルゴリズムの安全性は、楕円曲線上での離散対数問
題の難しさに基づくものであり、前記の問題とは、楕円曲線Ｅに属する２点Ｑお
よびＰから、もし存在するならば、Ｑ＝ｘ＊Ｐであるような整数ｘを見つけるこ
とである。

【００２０】離散対数問題に基づく暗号化アルゴリズムが数多く存在する。これらのアルゴ
リズムは、楕円曲線に容易に移行可能である。

【００２１】例えば、認証、機密性、完全性確認、および鍵交換を保証するアルゴリズムを
実施することが可能である。

【００２２】楕円曲線に基づく暗号化アルゴリズムの大多数に共通する点は、有限体上で規
定される楕円曲線およびこの楕円曲線に属する点Ｐを、パラメータとして含むこ
とである。秘密鍵は、無作為に選択された整数ｄである。公開鍵は、Ｑ＝ｄ＊Ｐ
であるような曲線の１点Ｑである。これらの暗号化アルゴリズムは、一般的に、
ｄが秘密鍵であるときの点Ｒ＝ｄ＊Ｔの計算に、スカラー乗算を介入させる。

【００２３】後の段落において、楕円曲線に基づく暗号化アルゴリズムを説明する。この体
系は、ＥｌＧａｍａｌの暗号化体系に類似している。メッセージｍは、以下の
ように暗号化される。暗号化者は、無作為に整数ｋを選択し、曲線の点、ｋ＊Ｐ＝（ｘ１，ｙ１）お
よびｋ＊Ｑ＝（ｘ２，ｙ２）、そして整数ｃ＝ｘ２＋ｍを計算する。ｍの暗号は
、３つの要素（ｘ１，ｙ１，ｃ）である。

【００２４】ｄを所有する復号化者は、以下を計算することによってｍを復号化する。（ｘ’２，ｙ’２）＝ｄ（ｘ１，ｙ１）およびｍ＝ｃ−ｘ’２

【００２５】前述の計算の手順において必要なスカラー乗算を実行するためには、複数のア
ルゴリズムが存在する。 “倍加算” アルゴリズム “加減算” アルゴリズム加算鎖式アルゴリズム窓式アルゴリズム署名表示アルゴリズム

【００２６】このリストは全体を網羅するものではない。最も単純で最も使用されているア
ルゴリズムは、“倍加算” アルゴリズムである。“倍加算” アルゴリズムは、
ある楕円曲線に属する点Ｐおよび整数ｄを入力する。整数ｄは、ｄ＝（ｄ（ｔ）
，ｄ（ｔ−１），…，ｄ（０））と記されるが、（ｄ（ｔ），ｄ（ｔ−１），…
，ｄ（０））は、ｄの２進法表示であり、ｄ（ｔ）は重みのあるビット、ｄ（０
）は重みのないビットである。アルゴリズムは、点Ｑ＝ｄ・Ｐを出力として返す
。

【００２７】 “倍加算” アルゴリズムは、次の３つのステップを有する。１）点Ｑを値Ｐで初期化する２）ｉが、ｔ−１から０となるまで、以下を実行する２ａ）Ｑに２Ｑを代入する２ｂ）もしｄ（ｉ）＝１ならば、ＱにＱ＋Ｐを代入する３）Ｑを返す

【００２８】楕円曲線型の公開鍵式暗号化アルゴリズムのチップカードへの実装が、復号化
の秘密鍵を見つけ出すことを可能にする消費電力差分解析による攻撃に対して脆
いものであったことが明らかになっている。これらの攻撃は、Differential Po
wer Analysis（電力差分解析）の頭字語で、ＤＰＡ攻撃と呼ばれる。これらの
ＤＰＡ攻撃の原理は、命令を実行するマイクロプロセッサの消費電力は、処理さ
れるデータに依存して変動するという事実に基づくものである。

【００２９】特に、特定の１ビットが一定で、他の複数ビットの値が変動するデータを、命
令が処理する際、命令に関する消費電力を解析すると、特定のビットが０の値を
取るか、または１の値を取るかによって、命令の平均消費は同じではないことが
分かる。従って、ＤＰＡタイプの攻撃は、暗号化アルゴリズムの実行の際、カー
ドのマイクロプロセッサが処理する中間データについての補足的情報を得ること
を可能にするのである。これらの補足的情報は、ある場合では、復号化アルゴリ
ズムの秘密パラメータを暴くこと可能にすることがあり、暗号システムを不確実
なものにする。

【００３０】続くこの文書では、整数ｄが秘密鍵であるときの、点Ｐと整数ｄとのスカラー
乗算タイプの演算を実行する楕円曲線型のアルゴリズムへのＤＰＡ攻撃の手順を
説明する。この攻撃は、秘密鍵ｄを直接暴くことを可能にする。したがって、こ
の攻撃により、楕円曲線のチップカードへの実装の安全性がひどく危うくなる。

【００３１】攻撃の第１のステップは、Ｎ個の異なる点Ｐ（１），…，Ｐ（Ｎ）についての
前述の“倍加算” アルゴリズムの実行に対応する消費電力を記録することであ
る。楕円曲線に基づくアルゴリズムでは、チップカードのマイクロプロセッサは
、Ｎ回のスカラー乗算ｄ・Ｐ（１），…，ｄ・Ｐ（Ｎ）を行う。

【００３２】攻撃の説明から明らかになるように、秘密鍵ｄのビットｄ（ｔ−１）の値を得
ることを可能にする方法を記載することから始めるが、ここで（ｄ（ｔ），ｄ（
ｔ−１），…，ｄ（０））は、ｄの２進法表示であり、ｄ（ｔ）は重みのあるビ
ット、ｄ（０）は重みのないビットである。次に、値ｄを奪取することを可能に
するアルゴリズムを説明する。

【００３３】４・Ｐの横座標の最後のビットの値に従って、点Ｐ（１）からＰ（Ｎ）をまと
めるが、ここで、Ｐは、Ｐ（１）からＰ（Ｎ）の点の１つを示す。第１のグルー
プは、４・Ｐの横座標の最後のビットが１に等しくなるような点Ｐから構成され
る。

【００３４】第２のグループは、４・Ｐの横座標の最後のビットが０に等しくなるような点
Ｐから構成される。２つのグループのそれぞれに対応する消費電力の平均を計算
し、これらの２つ平均の間の差分の曲線を計算する。

【００３５】ｄのビットｄ（ｔ−１）が０に等しい場合、前述のスカラー乗算アルゴリズム
は、４・Ｐの値を計算し、メモリに記憶する。そのことは、チップカードにおい
てアルゴリズムを実行する際に、カードのマイクロプロセッサが実際に４・Ｐを
計算することを意味する。この場合、第１のメッセージグループにおいては、マ
イクロプロセッサが処理するデータの最後のビットは常に１であり、第２のメッ
セージグループにおいては、処理するデータの最後のビットは常に０である。従
って、それぞれのグループに対応する消費電力の平均は異なる。従って、２つの
平均の間の差分の曲線において、消費電力差分のピークが現れている。

【００３６】反対に、ｄのビットｄ（ｔ−１）が１である場合、前述のべき乗アルゴリズム
は、点４・Ｐを計算しない。従って、チップカードがアルゴリズムを実行する際
、マイクロプロセッサは、データ４・Ｐを決して処理しない。従って、消費の差
分のピークは現れない。

【００３７】従って、この方法は、ｄのビットｄ（ｔ−１）の値を決定することができる。

【００３８】次の段落に記載されるアルゴリズムは、先のアルゴリズムを一般化したもので
ある。それは、秘密鍵ｄの値を決定することができる。

【００３９】チップカードが実行するＮ回の計算に対応するＰ（１）からＰ（Ｎ）で表され
るＮ個の点を入力とし、整数ｈを出力とする。

【００４０】前記アルゴリズムは、以下のように、３つのステップで行われる。１）ｈ＝１を実行する２）ｉが、ｔ−１から１になるまで、以下を実行する２）１）（４＊ｈ）・Ｐの横座標の最後のビットの値に従って、点Ｐ（１）
からＰ（Ｎ）を分類する２）２）２つのグループのそれぞれについて、消費電力の平均を計算する２）３）２つの平均の差を計算する２）４）その差が、消費の差分ピークを現すのであれば、ｈ＝ｈ＊２、そう
でなければ、ｈ＝ｈ＊２＋１を行う３）ｈを返す

【００４１】先のアルゴリズムは、ｄ＝２＊ｈまたはｄ＝２＊ｈ＋１であるような整数ｈを
算出する。ｄの値を得るためには、続いて、２つの可能な推定をテストするだけ
で十分である。

【００４２】従って、説明したＤＰＡタイプの攻撃は、秘密鍵ｄを奪取することを可能にす
るのである。

【００４３】本発明の方法は、前述のＤＰＡ攻撃に対して備えることを可能にする１つの対
抗措置を作成することから成る。この対抗措置は、射影座標での楕円曲線上の点
の表示を使用する。

【００４４】先に説明したごとく、射影座標でのある点の代表元は一意ではない。楕円曲線
を規定する有限体が、ｎ個の要素を含むとき、ｎ−１の可能なものの中から一つ
の代表元を選ぶことができる。

【００４５】計算を実行するある点の無作為の代表元を選ぶことによって、計算の中間値は
それ自体が無作為になり、したがって、外部から予測不可能となって、それが上
述のＤＰＡ攻撃を不可能にする。

【００４６】対抗措置方法は、素数ｐについての有限体ＧＦ（ｐ）とＧＦ（２＾ｎ）上に規
定される楕円曲線上の点の加算と点の倍算の演算を変更することから成る。素数
ｐについての有限体ＧＦ（ｐ）とＧＦ（２＾ｎ）上に規定される楕円曲線上の点
の加算と点の倍算の演算は、これらの演算を実行するために用いられるアルゴリ
ズムに関係なく適用される。

【００４７】また、対抗措置方法は、スカラー乗算の演算における４つの変型を定義するこ
とによっても構成される。これらの４つの変型は、スカラー乗算演算を実行する
ために用いられるアルゴリズムに関係なく適用される。

【００４８】本節では、ｐが素数である有限体ＧＦ（ｐ）上に規定される楕円曲線上の点の
倍算アルゴリズムの変更を説明する。したがって、楕円曲線は次式によって定義
される。ｙ＾２＝ｘ＾３＋ａ＊ｘ＋ｂここで、ａとｂは、最初に定められた整数パラメータである。

【００４９】Ｐ＝（Ｘ１，Ｙ１，Ｚ１）で、Ｑ＝２・Ｐである点Ｑ＝（Ｘ２，Ｙ２，Ｚ２）
の射影座標は、次の６ステップでの方法によって計算される。各ステップでは、
ｐを法として計算が行われる。１）Ｍ＝３＊Ｘ１＾２＋ａ＊Ｚ１＾４を計算２）Ｚ２＝２＊Ｙ１＊Ｚ１を計算３）Ｓ＝４＊Ｘ１＊Ｙ１＾２を計算４）Ｘ２＝Ｍ＾２−２＊Ｓを計算５）Ｔ＝８＊Ｙ１＾４を計算６）Ｙ２＝Ｍ＊（Ｓ−Ｘ２）−Ｔを計算

【００５０】対抗措置方法は、上述の方法を変更することから成る。

【００５１】有限体ＧＦ（ｐ）上に規定される楕円曲線上の点の倍算の新しい方法は、次の
８ステップから成る。１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算３）Ｍ＝３＊Ｘ’１＾２＋ａ＊Ｚ’１＾４を計算４）Ｚ２＝２＊Ｙ’１＊Ｚ’１を計算５）Ｓ＝４＊Ｘ’１＊Ｙ’１＾２を計算６）Ｘ２＝Ｍ＾２−２＊Ｓを計算７）Ｔ＝８＊Ｙ’１＾４を計算８）Ｙ２＝Ｍ＊（Ｓ−Ｘ２）−Ｔを計算

【００５２】より一般的に、対抗措置方法は点の倍算演算の実行に用いられる方法（以下に
Ａで表す）に関係なく適用される。方法Ａは、３ステップでの方法Ａ’に置き換
えられる。入力：射影座標で表された点Ｐ＝（Ｘ１，Ｙ１，Ｚ１）出力：Ｑ＝２・Ｐとなる射影座標で表されたＱ＝（Ｘ２，Ｙ２，Ｚ２）１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算ここで、Ｘ’１，Ｙ’１，Ｚ’１は、点Ｐ’＝（Ｘ’１，Ｙ’１，Ｚ’１）の座
標を定義する３）アルゴリズムＡを用いてＱ＝２＊Ｐ’を計算

【００５３】方法Ａ’の実行の途中で処理される変数は無作為であるので、上述のＤＰＡ攻
撃はもはや適用されない。

【００５４】本節では、ｐが素数である有限体ＧＦ（ｐ）上に規定される楕円曲線上の点の
加算アルゴリズムの変更を説明する。

【００５５】Ｐ＝（Ｘ０，Ｙ０，Ｚ０）で、Ｑ＝（Ｘ１，Ｙ１，Ｚ１）であるとき、Ｒ＝Ｐ
＋Ｑとなる点Ｒ＝（Ｘ２，Ｙ２，Ｚ２）の射影座標は、次の１２ステップでの方
法で計算される。各ステップでは、ｐを法として計算が行われる。１）Ｕ０＝Ｘ０＊Ｚ１＾２を計算２）Ｓ０＝Ｙ０＊Ｚ１＾３を計算３）Ｕ１＝Ｘ１＊Ｚ０＾２を計算４）Ｓ１＝Ｙ１＊Ｚ０＾３を計算５）Ｗ＝Ｕ０−Ｕ１を計算６）Ｒ＝Ｓ０−Ｓ１を計算７）Ｔ＝Ｕ０＋Ｕ１を計算８）Ｍ＝Ｓ０＋Ｓ１を計算９）Ｚ２＝Ｚ０＊Ｚ１＊Ｗを計算１０）Ｘ２＝Ｒ＾２−Ｔ＊Ｗ＾２を計算１１）Ｖ＝Ｔ＊Ｗ＾２−２＊Ｘ２を計算１２）２＊Ｙ２＝Ｖ＊Ｒ−Ｍ＊Ｗ＾３を計算

【００５６】対抗措置方法は、上述の方法を変更することから成る。有限体ＧＦ（ｐ）上に
規定される楕円曲線上の点の加算の新たな方法は、次の１６ステップから成る。
１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）０＜μ＜ｐである整数μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）Ｕ０＝Ｘ０＊Ｚ１＾２を計算６）Ｓ０＝Ｙ０＊Ｚ１＾３を計算７）Ｕ１＝Ｘ１＊Ｚ０＾２を計算８）Ｓ１＝Ｙ１＊Ｚ０＾３を計算９）Ｗ＝Ｕ０−Ｕ１を計算１０）Ｒ＝Ｓ０−Ｓ１を計算１１）Ｔ＝Ｕ０＋Ｕ１を計算１２）Ｍ＝Ｓ０＋Ｓ１を計算１３）Ｚ２＝Ｚ０＊Ｚ１＊Ｗを計算１４）Ｘ２＝Ｒ＾２−Ｔ＊Ｗ＾２を計算１５）Ｖ＝Ｔ＊Ｗ＾２−２＊Ｘ２を計算１６）２＊Ｙ２＝Ｖ＊Ｒ−Ｍ＊Ｗ＾３を計算

【００５７】より一般的に、対抗措置方法は点の加算演算の実行に用いられる方法（以下に
Ａで表す）に関係なく適用される。方法Ａは、５ステップでの方法Ａ’に置き換
えられる。入力：射影座標で表された２点Ｐ＝（Ｘ０，Ｙ０，Ｚ０）とＱ＝（Ｘ１，Ｙ
１，Ｚ１）出力：Ｒ＝Ｐ＋Ｑとなる射影座標で表されたＲ＝（Ｘ２，Ｙ２，Ｚ２）１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）０＜μ＜ｐである整数μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）アルゴリズムＡを用いてＲ＝Ｐ＋Ｑを計算

【００５８】方法Ａ’の実行の途中で処理される変数は無作為であるので、上述のＤＰＡ攻
撃はもはや適用されない。

【００５９】本節では、有限体ＧＦ（２＾ｎ）上に規定される楕円曲線上の点の倍算アルゴ
リズムの変更を説明する。したがって、楕円曲線は次式で定義される。ｙ＾２＋ｘ＊ｙ＝ｘ＾３＋ａ＊ｘ＾２＋ｂここで、ａとｂは、最初に定められた有限体ＧＦ（２＾ｎ）に属するパラメー
タである。ｃは以下の等式によって定義される：ｃ＝ｂ＾（２＾（ｎ−２））

【００６０】Ｐ＝（Ｘ１，Ｙ１，Ｚ１）のとき、Ｑ＝２・Ｐである点Ｑ＝（Ｘ２，Ｙ２，Ｚ
２）の射影座標は、次の４ステップでの方法によって計算される。各ステップで
は、有限体ＧＦ（２＾ｎ）内で計算が行われる。１）Ｚ２＝Ｘ１＊Ｚ１＾２を計算２）Ｘ２＝（Ｘ１＋ｃ＊Ｚ１＾２）＾４を計算３）Ｕ＝Ｚ２＋Ｘ１＾２＋Ｙ１＊Ｚ１を計算４）Ｙ２＝Ｘ１＾４＊Ｚ２＋Ｕ＊Ｘ２を計算

【００６１】対抗措置方法は、上述の方法を変更することから成る。有限体ＧＦ（２＾ｎ）
上に規定される楕円曲線上の点の倍算の新しい方法は、次の６ステップから成る
。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算３）Ｚ２＝Ｘ’１＊Ｚ’１＾２を計算４）Ｘ２＝（Ｘ’１＋ｃ＊Ｚ’１＾２）＾４を計算５）Ｕ＝Ｚ２＋Ｘ’１＾２＋Ｙ’１＊Ｚ’１を計算６）Ｙ２＝Ｘ’１＾４＊Ｚ２＋Ｕ＊Ｘ２を計算

【００６２】より一般的に、対抗措置方法は、点の倍算演算の実行に用いられる方法（以下
にＡで表す）に関係なく適用される。方法Ａは、３ステップでの方法Ａ’に置き
換えられる：入力：射影座標で表された点Ｐ＝（Ｘ１，Ｙ１，Ｚ１）出力：Ｑ＝２・Ｐである、射影座標で表された点Ｑ＝（Ｘ２，Ｙ２，Ｚ２）１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算Ｘ’１，Ｙ’１，Ｚ’１は、点Ｐ’＝（Ｘ’１，Ｙ’１，Ｚ’１）の座標を定
義する３）アルゴリズムＡによるＱ＝２・Ｐ’の計算方法Ａ’の実行途中で処理される変数は無作為であるので、上述のＤＰＡ攻撃
はもはや適用されない。

【００６３】本節では、有限体ＧＦ（２＾ｎ）上に規定される楕円曲線上の点の加算アルゴ
リズムの変更を説明する。

【００６４】Ｐ＝（Ｘ０，Ｙ０，Ｚ０）で、Ｑ＝（Ｘ１，Ｙ１，Ｚ１）であるとき、Ｒ＝Ｐ
＋Ｑとなる点Ｒ＝（Ｘ２，Ｙ２，Ｚ２）の射影座標は、次の１２ステップでの方
法によって計算される。各ステップでは、有限体ＧＦ（２＾ｎ）内で計算が行わ
れる。１）Ｕ０＝Ｘ０＊Ｚ１＾２を計算２）Ｓ０＝Ｙ０＊Ｚ１＾３を計算３）Ｕ１＝Ｘ１＊Ｚ０＾２を計算４）Ｓ１＝Ｙ１＊Ｚ０＾３を計算５）Ｗ＝Ｕ０＋Ｕ１を計算６）Ｒ＝Ｓ０＋Ｓ１を計算７）Ｌ＝Ｚ０＊Ｗを計算８）Ｖ＝Ｒ＊Ｘ１＋Ｌ＊Ｙ１を計算９）Ｚ２＝Ｌ＊Ｚ１を計算１０）Ｔ＝Ｒ＋Ｚ２を計算１１）Ｘ２＝ａ＊Ｚ２＾２＋Ｔ＊Ｒ＋Ｗ＾３を計算１２）Ｙ２＝Ｔ＊Ｘ２＋Ｖ＊Ｌ＾２を計算

【００６５】対抗措置方法は、先の方法を変更することから成る。有限体ＧＦ（２＾ｎ）上
に規定される楕円曲線上の点の加算の新しい方法は、次の１４ステップから成る
。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）ＧＦ（２＾ｎ）のゼロでない要素μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）Ｕ０＝Ｘ０＊Ｚ１＾２を計算６）Ｓ０＝Ｙ０＊Ｚ１＾３を計算７）Ｕ１＝Ｘ１＊Ｚ０＾２を計算８）Ｓ１＝Ｙ１＊Ｚ０＾３を計算９）Ｗ＝Ｕ０＋Ｕ１を計算１０）Ｒ＝Ｓ０＋Ｓ１を計算１１）Ｌ＝Ｚ０＊Ｗを計算１２）Ｖ＝Ｒ＊Ｘ１＋Ｌ＊Ｙ１を計算１３）Ｚ２＝Ｌ＊Ｚ１を計算１４）Ｔ＝Ｒ＋Ｚ２を計算１５）Ｘ２＝ａ＊Ｚ２＾２＋Ｔ＊Ｒ＋Ｗ＾３を計算１６）Ｙ２＝Ｔ＊Ｘ２＋Ｖ＊Ｌ＾２を計算

【００６６】より一般的に、対抗措置方法は、点の加算演算の実行に用いられる方法（以下
にＡで表す）に関係なく適用される。方法Ａは、５ステップでの方法Ａ’に置き
換えられる。入力：射影座標で表された２つの点Ｐ＝（Ｘ０，Ｙ０，Ｚ０）とＱ＝（Ｘ１
，Ｙ１，Ｚ１）出力：Ｒ＝Ｐ＋Ｑである、射影座標で表されたＲ＝（Ｘ２，Ｙ２，Ｚ２）１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）ＧＦ（２＾ｎ）のゼロでない要素μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）アルゴリズムＡを用いてＲ＝Ｐ＋Ｑを計算

【００６７】方法Ａ’の実行の途中で処理される変数は無作為であるので、上述のＤＰＡ攻
撃はもはや適用されない。

【００６８】対抗措置はまた、スカラー乗算の演算の４つの変型を定義することから成る。
スカラー乗算演算には、Ｄｏで示した点の倍算演算と、Ａｄで示した点の加算演
算とが用いられる。

【００６９】上述の変更された点の倍算演算をＤｏ’とし、上述の変更された点の加算演算を
Ａｄ’とする。

【００７０】本節では、スカラー乗算演算を変更する第一の変型を説明する。第一の変型は
、計算過程の最初の点の表示を無作為にすることから成る。“倍加算”アルゴリ
ズムを利用する場合、スカラー乗算を変更する方法は、５ステップでの次のもの
になる。この方法は、点Ｐと整数ｄを入力とする。整数ｄは、ｄ＝（ｄ（ｔ），
ｄ（ｔ−１），…，ｄ（０））で表され、ここで（ｄ（ｔ），ｄ（ｔ−１），…
，ｄ（０））はｄの２進数表示であり、ｄ（ｔ）は重みのあるビット、ｄ（０）
は重みのないビットである。アルゴリズムは点Ｑ＝ｄ・Ｐを出力に返す。

【００７１】この第一の変型は、５ステップで実行される。１）値Ｐで点Ｑを初期化する２）方法Ｄｏ’を用いてＱに２・Ｑを代入する３）もしｄ（ｔ−１）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する４）ｉがｔ−２から０になるまで、下記を実行する４ａ）Ｑに２Ｑを代入する４ｂ）もしｄ（ｉ）＝１ならば、ＱにＱ＋Ｐを代入する５）Ｑを返す

【００７２】より一般的に、上述の第一の変型の方法は、スカラー乗算計算の実行に用いら
れる方法（以下にＡで表す）に関係なく、スカラー乗算演算に適用される。方法
Ａは、先に定義した演算ＤｏとＡｄを利用する。

【００７３】対抗措置の第一の変型は、第一の演算Ｄｏを先に定義したＤｏ’に置き換える
ことから成る。

【００７４】したがって、第一の変型は、スカラー乗算演算の際に処理される中間変数が無
作為になることを保証する。これによって上述のＤＰＡ攻撃は適用できなくなる
。

【００７５】本節では、スカラー乗算演算の変更の第二の変型を説明する。

【００７６】第二の変型は、計算方法の最初の点と計算方法と最後の点の表示を無作為にす
ることから成る。“倍加算”アルゴリズムを利用する場合、スカラー乗算を変更
する方法は、７ステップでの次のものになる。この方法は点Ｐと整数ｄを入力と
する。整数ｄは、ｄ＝（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））で表され、こ
こで（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））はｄの２進数表示であり、ｄ（
ｔ）は重みのあるビット、ｄ（０）は重みのないビットである。アルゴリズムは
点Ｑ＝ｄ・Ｐを出力に返す。

【００７７】この第二の変型は、７ステップで実行される。１）値Ｐで点Ｑを初期化する２）方法Ｄｏ’を用いてＱに２・Ｑを代入する３）もしｄ（ｔ−１）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する４）ｉがｔ−２から１になるまで、下記を実行する４ａ）Ｑに２Ｑを代入する４ｂ）もしｄ（ｉ）＝１ならば、ＱにＱ＋Ｐを代入する５）方法Ｄｏ’を用いてＱに２・Ｑを代入する６）もしｄ（０）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する７）Ｑを返す

【００７８】より一般的に、上述の第二の変型の方法は、スカラー乗算計算の実行に用いら
れる方法（以下にＡで表す）に関係なく、スカラー乗算演算に適用される。方法
Ａは、先に定義した演算ＤｏとＡｄを利用する。対抗措置の第二の変型は第一の
演算Ｄｏを先に定義したＤｏ’に、最後の演算ＤｏをＤｏ’に置き換えることを
もって成る。

【００７９】したがって、第二の変型はスカラー乗算演算の際に処理される中間変数が無作
為になることを保証する。第二の変型の利点は、スカラー乗算アルゴリズムの終
わりのＤＰＡ攻撃に対する安全性が向上することである。とくに、第二の変型は
上述のＤＰＡ攻撃を適用できなくする。

【００８０】本節では、スカラー乗算演算を変更する第三の変型を説明する。

【００８１】第三の変型は、スカラー乗算方法の途中で処理されるそれぞれの点の表示を無
作為にすることから成る。“倍加算”アルゴリズムを利用する場合、スカラー乗
算を変更する方法は、４ステップでの次のものになる。この方法は点Ｐと整数ｄ
を入力とする。整数ｄは、ｄ＝（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））で表
され、ここで（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））はｄの２進数表示であ
り、ｄ（ｔ）は重みのあるビット、ｄ（０）は重みのないビットである。アルゴ
リズムは点Ｑ＝ｄ・Ｐを出力に返す。

【００８２】この第三の変型は３ステップで実行される。１）点Ｐで点Ｑを初期化する２）ｉがｔ−２から０になるまで、下記を実行する２ａ）方法Ｄｏ’を用いてＱに２Ｑを代入する２ｂ）もしｄ（ｉ）＝１ならば、方法Ａｄ’を用いてＱにＱ＋Ｐを代入する３）Ｑを返す

【００８３】より一般的に、上述の第三の変型の方法は、スカラー乗算計算の実行に用いら
れる方法（以下にＡで表す）に関係なく、スカラー乗算の演算に適用される。方
法Ａは、先に定義した演算ＤｏとＡｄを利用する。

【００８４】対抗措置の第三の変型はすべての演算についてＤｏをＤｏ’に、ＡｄをＡｄ’
に置き換えることをもって成る。

【００８５】したがって、第三の変型はスカラー乗算演算の際に処理される中間変数が無作
為になることを保証する。第二の変型に対する第三の変型の利点は、スカラー乗
算方法の中間演算へのＤＰＡ攻撃に対する安全性が向上することである。とくに
、第三の変型は上述のＤＰＡ攻撃を適用できなくする。

【００８６】本節では、スカラー乗算演算を変更する第四の変型を説明する。第四の変型は
、スカラー乗算方法の過程で処理されるそれぞれの点の表示を無作為にすること
をもって成る。第四の変型は、カウンタを用いることによって第三の変型を変更
するものであり、前記カウンタは、ある点の表示を無作為にするスカラー乗算ア
ルゴリズムのステップを決定することを可能にするものである。このために、セ
キュリティ変数Ｔを定義する。実際には、Ｔ＝５とすることができる。“倍加算
”アルゴリズムを利用する場合、スカラー乗算を変更する方法は、４ステップで
の次のものになる。この方法は、点Ｐと整数ｄを入力とする。

【００８７】整数ｄは、ｄ＝（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））で表され、ここで
（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））はｄの２進数表示であり、ｄ（ｔ）
は重みのあるビット、ｄ（０）は重みのないビットである。アルゴリズムは点Ｑ
＝ｄ・Ｐを出力に返す。

【００８８】第四の変型は３ステップで実行される。１）点Ｐで点Ｑを初期化する２）カウンタｃｏを値Ｔに初期化する３）ｉがｔ−１から０になるまで、下記を実行する３ａ）もしｃｏが０でははないならば、方法Ｄｏを用いてＱを２Ｑに代え、それ
以外の場合、方法Ｄｏ’を用いる３ｂ）もしｄ（ｉ）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する３ｃ）もしｃｏ＝０ならば、カウンタｃｏを値Ｔに再度初期化する３ｄ）カウンタｃｏをデクリメントする３）Ｑを返す

【００８９】より一般的に、上述の第三の変型の方法は、スカラー乗算の計算の実行に用い
られる方法（以下にＡで表す）に関係なく、スカラー乗算の演算に適用される。
方法Ａは先に定義した演算ＤｏとＡｄを利用する。

【００９０】第三の対抗措置の変型は、カウンタｃｏを値Ｔに初期化することから成る。カ
ウンタの値が０に等しいとき、演算Ｄｏは演算Ｄｏ’に置き換えられる。

【００９１】演算ＤｏまたはＤｏ’の実行の都度、カウンタが値０に達していれば、カウン
タは値Ｔに再度初期化される；次にデクリメントする。

【００９２】したがって、第四の変型はスカラー乗算の演算の際に処理される中間変数が無
作為になることを保証する。第三の変型に対する第四の変型の利点は、実行速度
がはるかに速いことである。第四の変型は上述のＤＰＡ攻撃を適用できなくする
。

【００９３】したがって、上述の４つの変型の一つを適用することによって、楕円曲線に基
づくあらゆる暗号化アルゴリズムを、上述のＤＰＡ型の攻撃から保護することが
できる。

【手続補正書】特許協力条約第３４条補正の翻訳文提出書

【提出日】平成１３年５月２日（２００１．５．２）

【手続補正１】

【補正対象書類名】明細書

【補正対象項目名】特許請求の範囲

【補正方法】変更

【補正の内容】

【特許請求の範囲】

───────────────────────────────────────────────────── フロントページの続き (81)指定国ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＣＹ，ＤＥ，ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，ＬＵ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＯＡ(ＢＦ，ＢＪ，ＣＦ，ＣＧ，ＣＩ，ＣＭ，ＧＡ，ＧＮ，ＧＷ，ＭＬ，ＭＲ，ＮＥ，ＳＮ，ＴＤ，ＴＧ)，ＡＰ(ＧＨ，ＧＭ，ＫＥ，ＬＳ，ＭＷ，ＳＤ，ＳＬ，ＳＺ，ＴＺ，ＵＧ，ＺＷ )，ＥＡ(ＡＭ，ＡＺ，ＢＹ，ＫＧ，ＫＺ，ＭＤ，ＲＵ，ＴＪ，ＴＭ)，ＡＥ，ＡＬ，ＡＭ，ＡＴ，ＡＵ，ＡＺ，ＢＡ，ＢＢ，ＢＧ，ＢＲ，ＢＹ，ＣＡ，ＣＨ，ＣＮ，ＣＲ，ＣＵ，ＣＺ，ＤＥ，ＤＫ，ＤＭ，ＥＥ，ＥＳ，ＦＩ，ＧＢ，ＧＤ，ＧＥ，ＧＨ，ＧＭ，ＨＲ，ＨＵ，ＩＤ，ＩＬ，ＩＮ，ＩＳ，ＪＰ，ＫＥ，ＫＧ，ＫＰ，ＫＲ，ＫＺ，ＬＣ，ＬＫ，ＬＲ，ＬＳ，ＬＴ，ＬＵ，ＬＶ，ＭＡ，ＭＤ，ＭＧ，ＭＫ，ＭＮ，ＭＷ，ＭＸ，ＮＯ，ＮＺ，ＰＬ，ＰＴ，ＲＯ，ＲＵ，ＳＤ，ＳＥ，ＳＧ，ＳＩ，ＳＫ，ＳＬ，ＴＪ，ＴＭ，ＴＲ，ＴＴ，ＴＺ，ＵＡ，ＵＧ，ＵＳ，ＵＺ，ＶＮ，ＹＵ，ＺＡ，ＺＷ

Claims

【特許請求の範囲】

【請求項１】射影座標の楕円曲線上の点の表示を使用する楕円曲線型公開鍵
暗号化アルゴリズムを用いる電子構成部品内の対抗措置方法であって、ｘとｙが
アフィン座標での楕円曲線上の点の座標であるとき、ｘ＝Ｘ／Ｚで、ｙ＝Ｙ／Ｚ
＾３である座標（Ｘ，Ｙ，Ｚ）によって楕円曲線上の点Ｐを表すことから成り、
前記曲線は、ｎ個の要素を含み、かつｐが素数である有限体ＧＦ（ｐ）上で規定
され、ａとｂが最初に定められた整数パラメータであるとき、前記曲線の等式は
、ｙ＾２＝ｘ＾３＋ａ＊ｘ＋ｂであるか、あるいは有限体ＧＦ（２＾ｎ）上に規
定された前記曲線の等式ｙ＾２＋ｘ＊ｙ＝ｘ＾３＋ａ＊ｘ＾２＋ｂであり、前記
方法は、楕円曲線の射影座標内の可能なｎ個の要素の中から無作為の代表元を選
択し、点の加算と前記点の倍算の演算を変更すること及びスカラー乗算演算を変
更することから成ることを特徴とする方法。
【請求項２】対抗措置方法が、点の倍算演算の実行に用いられる以下にＡで
表す方法またはアルゴリズムに関係なく適用され、楕円曲線の、射影座標で表さ
れた点Ｐ＝（Ｘ１，Ｙ１，Ｚ１）によって規定された入力と、射影座標で表され
たＱ＝２・Ｐである点Ｑ＝（Ｘ２，Ｙ２，Ｚ２）によって規定される出力を用い
て、方法Ａが３ステップでの方法Ａ’に置換され、前記ステップが以下であるこ
とを特徴とする、請求項１に記載の対抗措置方法。１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算ここでＸ’１，Ｙ’１，Ｚ’１は、点Ｐ’＝（Ｘ’１，Ｙ’１，Ｚ’１）の座標
を定義する３）アルゴリズムＡを用いてＱ＝２＊Ｐ’を計算。
【請求項３】前記有限体ＧＦ（ｐ）上に規定される楕円曲線上の点の倍算ア
ルゴリズム、または点の倍算演算が以下の８ステップから成ることを特徴とする
、請求項１に記載の対抗措置方法。１）０＜λ＜ｐである整数λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算３）Ｍ＝３＊Ｘ’１＾２＋ａ＊Ｚ’１＾４を計算４）Ｚ２＝２＊Ｙ’１＊Ｚ’１を計算５）Ｓ＝４＊Ｘ’１＊Ｙ’１＾２を計算６）Ｘ２＝Ｍ＾２−２＊Ｓを計算７）Ｔ＝８＊Ｙ’１＾４を計算８）Ｙ２＝Ｍ＊（Ｓ−Ｘ２）−Ｔを計算
【請求項４】より一般的に、対抗措置方法は、前記有限体ＧＦ（ｐ）上に規
定される楕円曲線上の点の加算演算の実行に用いられる以下にＡで表す方法に関
係なく適用され、５ステップで実行されることを特徴とする、請求項１に記載の
対抗措置方法。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）ＧＦ（２＾ｎ）のゼロでない要素μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）アルゴリズムＡを用いてＲ＝Ｐ＋Ｑを計算
【請求項５】ｐが素数である有限体ＧＦ（ｐ）上に規定される楕円曲線上の
点の加算アルゴリズムが以下の通りに変更され、Ｐ＝（Ｘ０，Ｙ０，Ｚ０）で、
Ｑ＝（Ｘ１，Ｙ１，Ｚ１）のとき、Ｒ＝Ｐ＋Ｑとなる点Ｒ＝（Ｘ２，Ｙ２，Ｚ２
）の射影座標は、１６ステップでの次の方法で計算され、各ステップでは、ｐを
法として計算が行われることを特徴とする、請求項１に記載の対抗措置方法。１）０＜λ＜ｐである、前記有限体ＧＦ（ｐ）に属する整数λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ Ｚ０に置き換え
る３）０＜μ＜ｐなどに属する整数μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）Ｕ０＝Ｘ０＊Ｚ１＾２を計算６）Ｓ０＝Ｙ０＊Ｚ１＾３を計算７）Ｕ１＝Ｘ１＊Ｚ０＾２を計算８）Ｓ１＝Ｙ１＊Ｚ０＾３を計算９）Ｗ＝Ｕ０−Ｕ１を計算１０）Ｒ＝Ｓ０−Ｓ１を計算１１）Ｔ＝Ｕ０＋Ｕ１を計算１２）Ｍ＝Ｓ０＋Ｓ１を計算１３）Ｚ２＝Ｚ０＊Ｚ１＊Ｗを計算１４）Ｘ２＝Ｒ＾２−Ｔ＊Ｗ＾２を計算１５）Ｖ＝Ｔ＊Ｗ＾２−２＊Ｘ２を計算１６）２＊Ｙ２＝Ｖ＊Ｒ−Ｍ＊Ｗ＾３を計算
【請求項６】より一般的に、ｎが素数である有限体ＧＦ（２＾ｎ）上に規定
される楕円曲線上の点の加算アルゴリズムが以下の通りに変更され、Ｒ＝Ｐ＋Ｑ
で、Ｑ＝（Ｘ２，Ｙ２，Ｚ２）である点Ｐ＝（Ｘ１，Ｙ１，Ｚ１）の射影座標が
３ステップでの次の方法で計算され、各ステップでは、ｐを法として計算が行わ
れることを特徴とする、請求項１に記載の対抗措置方法。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算ここでＸ’１，Ｙ’１，Ｚ’１は、点Ｐ’＝（Ｘ’１，Ｙ’１，Ｚ’１）の座標
を定義する３）アルゴリズムＡを用いてＱ＝２・Ｐ’を計算
【請求項７】対抗措置方法が先の方法を変更することから成り、有限体ＧＦ
（２＾ｎ）上に規定される楕円曲線上の点の倍算の新しい方法が次の６ステップ
から成ることを特徴とする、請求項１に記載の対抗措置方法。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ’１＝λ＾２＊Ｘ１，Ｙ’１＝λ＾３＊Ｙ１，Ｚ’１＝λ＊Ｚ１を計
算３）Ｚ２＝Ｘ’１＊Ｚ’１＾２を計算４）Ｘ２＝（Ｘ’１＋ｃ＊Ｚ’１＾２）＾４を計算５）Ｕ＝Ｚ２＋Ｘ’１＾２＋Ｙ’１＊Ｚ’１を計算６）Ｙ２＝Ｘ’１＾４＊Ｚ２＋Ｕ＊Ｘ２を計算
【請求項８】より一般的に、ｎが素数である有限体ＧＦ（２＾ｎ）上に規定
される楕円曲線上の点の加算アルゴリズムが以下の通りに変更され、入力の点
Ｐ＝（Ｘ０，Ｙ０，Ｚ０）及びＱ＝（Ｘ１，Ｙ１，Ｚ２）とＲ＝（Ｘ２，Ｙ２，
Ｚ２）との射影座標が、５ステップの次の方法で計算され、各ステップでは、計
算が剰算で実行されることを特徴とする、請求項１に記載の対抗措置方法。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）ＧＦ（２＾ｎ）のゼロでない要素μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）アルゴリズムＡを用いてＲ＝Ｐ＋Ｑを計算
【請求項９】対抗措置方法は、有限体ＧＦ（２＾ｎ）上に規定される楕円曲
線上の点の加算法を変更することから成り、次の１６ステップから成ることを特
徴とする、請求項１に記載の対抗措置方法。１）ＧＦ（２＾ｎ）のゼロでない要素λを無作為抽出２）Ｘ０をλ＾２＊Ｘ０に、Ｙ０をλ＾３＊Ｙ０に、Ｚ０をλ＊Ｚ０に置き換え
る３）ＧＦ（２＾ｎ）のゼロでない要素μを無作為抽出４）Ｘ１をμ＾２＊Ｘ１に、Ｙ１をμ＾３＊Ｙ１に、Ｚ１をμ＊Ｚ１に置き換え
る５）Ｕ０＝Ｘ０＊Ｚ１＾２を計算６）Ｓ０＝Ｙ０＊Ｚ１＾３を計算７）Ｕ１＝Ｘ１＊Ｚ０＾２を計算８）Ｓ１＝Ｙ１＊Ｚ０＾３を計算９）Ｗ＝Ｕ０＋Ｕ１を計算１０）Ｒ＝Ｓ０＋Ｓ１を計算１１）Ｌ＝Ｚ０＊Ｗを計算１２）Ｖ＝Ｒ＊Ｘ１＋Ｌ＊Ｙ１を計算１３）Ｚ２＝Ｌ＊Ｚ１を計算１４）Ｔ＝Ｒ＋Ｚ２を計算１５）Ｘ２＝ａ＊Ｚ２＾２＋Ｔ＊Ｒ＋Ｗ＾３を計算１６）Ｙ２＝Ｔ＊Ｘ２＋Ｖ＊Ｌ＾２を計算
【請求項１０】スカラー乗算演算を変更する第一の変型が、“倍加算”アル
ゴリズムを利用して計算方法の最初に点の表示を無作為にすることから成り、ス
カラー乗算を変更する方法は５ステップの次のものになり、点Ｐと整数ｄを入力
とし、整数ｄはｄ＝（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））で表され、ここ
で（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））はｄの２進数表示であり、ｄ（ｔ
）は重みのあるビット、ｄ（０）は重みのないビットであり、アルゴリズムは点
Ｑ＝ｄ・Ｐを出力に返し、方法Ｄｏは点の倍算法であり、方法Ｄｏ’が請求項１
から９のいずれか一つに従って変更される点の倍算法であり、この第一の変型が
５ステップで実行されることを特徴とする、請求項１に記載の対抗措置方法。１）値Ｐで点Ｑを初期化する２）方法Ｄｏ’を用いてＱに２・Ｑを代入する３）もしｄ（ｔ−１）＝１ならば、方法Ａｄが点の加算法である、方法Ａｄを用
いてＱにＱ＋Ｐを代入する４）ｉがｔ−２から０になるまで、下記を実行する４ａ）Ｑに２Ｑを代入する４ｂ）もしｄ（ｉ）＝１ならば、ＱにＱ＋Ｐを代入する５）Ｑを返す
【請求項１１】スカラー乗算演算の第二の変型が、“倍加算”アルゴリズム
を利用する場合に、計算方法の最初と計算方法の最後に、点の表示を無作為にす
ることから成り、スカラー乗算を変更する方法は、７ステップでの次のものになり、点Ｐと整数ｄ
を入力とし、整数ｄは、ｄ＝（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））で表さ
れ、ここで（ｄ（ｔ），ｄ（ｔ−１），…，ｄ（０））はｄの２進数表示であり
、ｄ（ｔ）は重みのあるビット、ｄ（０）は重みのないビットであり、アルゴリ
ズムが点Ｑ＝ｄ・Ｐを出力に返し、前記第二の変型が７ステップで実行されるこ
とを特徴とする、請求項１に記載の対抗措置方法。１）値Ｐで点Ｑを初期化する２）方法Ｄｏ’を用いてＱに２・Ｑを代入する３）もしｄ（ｔ−１）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する４）ｉがｔ−２から１になるまで、下記を実行する４ａ）Ｑに２Ｑを代入する４ｂ）もしｄ（ｉ）＝１ならば、ＱにＱ＋Ｐを代入する５）方法Ｄｏ’を用いてＱに２・Ｑを代入する６）ｄ（０）＝１のとき、方法Ａｄを用いてＱにＱ＋Ｐを代入する７）Ｑを返す
【請求項１２】スカラー乗算演算の変更の第三の変型が３ステップで実行さ
れることを特徴とする、請求項１に記載の対抗措置方法。１）点Ｐで点Ｑを初期化する２）ｉがｔ−２から０になるまで、下記を実行する２ａ）方法Ｄｏ’を用いてＱに２Ｑを代入する２ｂ）もしｄ（ｉ）＝１ならば、方法Ａｄ’を用いてＱにＱ＋Ｐを代入する
が、Ａｄ’は請求項１から１２のいずれか一つに従って変更された点の加算法で
ある３）Ｑを返す
【請求項１３】スカラー乗算演算の第四の変型が３ステップで実行されるこ
とを特徴とする、請求項１に記載の対抗措置方法。１）点Ｐで点Ｑを初期化する２）カウンタｃｏを値Ｔに初期化する３）ｉがｔ−１から０になるまで、下記を実行する３ａ）もしｃｏが０ではないならば、方法Ｄｏを用いてＱを２Ｑに代え、そ
れ以外の場合、方法Ｄｏ’を用いる３ｂ）もしｄ（ｉ）＝１ならば、方法Ａｄを用いてＱにＱ＋Ｐを代入する３ｃ）もしｃｏ＝０ならば、カウンタｃｏを値Ｔに再度初期化する３ｄ）カウンタｃｏをデクリメントする３）Ｑを返す
【請求項１４】チップカードであり得ることを特徴とする、請求項１から１
３のいずれか一つに記載の方法を利用する電子構成部品。