(57)【特許請求の範囲】
【請求項１】
有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐとし、前記取得手段により取得した自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得した点Ｐの座標と自然数ｄとに基づいて、上記（１）から（４）の演算を、変数ｉをｎ−２から０まで１ずつ変化させて繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【請求項２】
前記演算手段は、変数Ｑ［０］を記憶する第１のレジスタと、変数Ｑ［１］を記憶する第２のレジスタとを有し、
変数Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、変数Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記（１）の前記楕円加算ＥＣＡＤＤと、前記（２）の楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を前記第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を前記第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を前記第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を前記第１のレジスタに格納する請求項１記載の楕円曲線暗号装置。
【請求項３】
前記取得手段は、有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得し、
楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ （＾：べき乗を表す）とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、前記演算手段は、以下の式、
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４×ｂ×（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する請求項１または２記載の楕円曲線暗号装置。
【請求項４】
前記取得手段は、有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１を取得し、
楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ （＾：べき乗を表す）としたときに、前記演算手段は、
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｘ１］／［４×（ｘ１＾３＋ａ×ｘ１＋ｂ）］によりｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を算出することを特徴とする請求項１または２記載の楕円曲線暗号装置。
【請求項５】
前記取得手段は、有限体上の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得し、
楕円曲線Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３ （＾：べき乗を表す）とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１のとき、前記演算手段は、以下の式、
（１）・・・Ｘ３＝Ｚ３×［２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２］−Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
（２）・・・Ｚ３＝Ｚ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
により射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに計算する請求項１または２記載の楕円曲線暗号装置。
【請求項６】
前記取得手段は、有限体上の楕円曲線の射影座標における点Ｐ１のＸ座標Ｘ１と，Ｚ座標Ｚ１を取得し、
楕円曲線Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３ （＾：べき乗を表す）とし、Ｚ１≠０の場合に、前記演算手段は、以下の式、
（１）・・・Ｘ４＝（Ｘ１＾２−ａ×Ｚ１＾２）＾２−８×ｂ×Ｘ１×Ｚ１＾３；（＾：べき乗を表す）
（２）・・・Ｚ４＝４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）
により射影座標における楕円２倍算Ｐ４＝２×Ｐ１のＸ座標Ｘ４とＺ座標Ｚ４を、Ｙ座標を用いずに演算する請求項１または２記載の楕円曲線暗号装置。
【請求項７】
有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得し、変数Ｑ［０］の初期値Ｐ、変数Ｑ［１］の初期値２×Ｐを記憶手段に記憶し、取得した自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
取得した点Ｐの座標と自然数ｄと、前記記憶手段に記憶されている前記変数Ｑ［０］、Ｑ［１］の初期値を読み出し、上記（１）から（４）の演算を、変数ｉをｎ−２から０まで１ずつ変化させて繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号の演算方法。
【請求項８】
前記記憶手段は、変数Ｑ［０］を記憶する第１のレジスタと、変数Ｑ［１］を記憶する第２のレジスタとを有し、変数Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、変数Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記（１）の楕円加算ＥＣＡＤＤと前記（２）の楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を前記第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を前記第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を前記第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を前記第１のレジスタに格納する請求項７記載の楕円曲線暗号の演算方法。
【請求項９】
有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得し、
楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ （＾：べき乗を表す）とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式、
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４×ｂ×（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する請求項７または８記載の楕円曲線暗号の演算方法。
【請求項１０】
有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得し、
楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ （＾：べき乗を表す）とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式、
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４×ｂ×（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する請求項７または８記載の楕円曲線暗号の演算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、楕円曲線暗号装置、楕円曲線暗号プログラム及び楕円曲線暗号の演算方法に関する。
【０００２】
【従来の技術】
楕円曲線暗号は公開鍵暗号の１つであり、文書の暗号化、復号化、署名、認証などの用途に使用される。
【０００３】
楕円曲線暗号はＥＣＥＳ暗号・復号、ＥＣＤＳＡ署名、ＥＣＤＨ秘密共有といった、いくつかの暗号プリミティブから構成されているが、点のスカラー倍と呼ばれる演算はすべての暗号プリミティブで共通であり、かつ暗号処理の中心となるものである。こらから、楕円曲線暗号におけるスカラー倍演算の高速化を実現する技術は必要不可欠である。
【０００４】
楕円曲線暗号の例として、ＥＣＥＳ暗号・復号プリミティブを説明する。送信者Ａは秘密鍵ｓ（ｓは自然数）を持ち、受信者Ｂが秘密鍵ｔ（ｔは自然数）を持つ場合に、楕円曲線Eと、楕円曲線E上に設定されるベースポイントＰ（＝（ｘ，ｙ））と、公開鍵ｓＰ（送信者Aの秘密鍵ｓとベースポイントＰとのスカラー倍算）と、公開鍵ｔＰ（送信者Ｂの秘密鍵ｔとベースポイントＰとのスカラー倍算）があらかじめ公開されている。このとき送信者Ａは、自分の秘密鍵ｓと、受信者Ｂの公開鍵ｔＰとのスカラー倍算ｓ（ｔＰ）を計算し、そのｘ座標のビット表現を求め、このビット表現とメッセージのビット表現との間でビット対応のＥＯＲ演算を施すことで、メッセージｍに対する暗号文Ｃを生成し、それを受信者Ｂに送信する。受信者Ｂは、自分の秘密鍵ｔと、送信者Ａの公開鍵ｓＰとのスカラー倍算ｔ（ｓＰ）を計算し、そのｘ座標のビット表現を求め、そして
ｓ（ｔＰ）＝ｔ（ｓＰ）
という関係式が成立することを考慮して、そのビット表現と暗号文Ｃのビット表現との間でビット対応のＥＯＲ演算を施すことで、暗号文Ｃを復号し、メッセージｍを得る。このようにして、ＥＣＥＳ暗号・復号と呼ばれる楕円曲線暗号のプリミティブでは、スカラー倍演算を用いて暗号・復号処理を行う。
【０００５】
ｐを２以上の素数，ｍを１以上の自然数とすると、要素数ｑ＝ｐ＾ｍの有限体ＧＦ（ｑ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線は、
Ｅ：ｙ＾２＋ａ１×ｘ×ｙ＋ａ３×ｙ＝ｘ＾３＋ａ２×ｘ＾２＋ａ４×ｘ＋ａ６    ：（＾：べき乗を表す）
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表すこともある。
【０００６】
ここでａ１，ａ２，ａ３，ａ４，ａ６，ｘ，ｙはＧＦ（ｑ）の要素である。特にｐが５以上の素数の場合、ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線は、方程式
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
を満たす点（ｘ，ｙ）の集合に、無限遠点と呼ばれる点∞を加えた集合である。無限遠点∞を０と表すこともある。
【０００７】
ａ，ｂ，ｘ，ｙはＧＦ（ｐ＾ｍ）の要素で、４×ａ＾３＋２７×ｂ＾２≠０を満たす。無限遠点∞は（ｘ，ｙ）のような座標形式で表現することができない点である。
【０００８】
ＰをＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点とする。以下のようにしてＰの逆元−Ｐ定義する。
（１）Ｐ＝∞ならば−Ｐ＝∞
（２）Ｐ≠∞ならばＰ＝（ｘ，ｙ）としたときに、
−Ｐ＝（ｘ，−ｙ）
Ｐ１，Ｐ２をＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の２点とする。以下のようにしてＰ１とＰ２の和Ｐ３＝Ｐ１＋Ｐ２を定義する。
（１）Ｐ１＝∞ならばＰ３＝Ｐ２
（２）Ｐ２＝∞ならばＰ３＝Ｐ１
（３）Ｐ１＝−Ｐ２ならばＰ３＝∞
（４）Ｐ１≠−Ｐ２ならばＰ１＝（ｘ１，ｙ１），Ｐ２＝（ｘ２，ｙ２），Ｐ３＝（ｘ３，ｙ３）としたときに、
ｘ３＝λ＾２−ｘ１−ｘ２，    ｙ３＝λ×（ｘ１−ｘ３）−ｙ１，
ただし
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）  ：Ｐ１≠Ｐ２のとき
λ＝（３×ｘ１＾２＋ａ）／（２×ｙ１）  ：Ｐ１＝Ｐ２のとき
Ｐ１≠Ｐ２のときに、Ｐ１＋Ｐ２を計算することを楕円加算ＥＣＡＤＤ、Ｐ１＝Ｐ２のときにＰ１＋Ｐ２＝２×Ｐ１を計算することを楕円２倍算ＥＣＤＢＬと呼ぶ。
【０００９】
図１５及び図１６は、楕円加算と楕円２倍算の説明図である。楕円加算は、図１５に示すように、楕円曲線上の点Ｐ１＝（ｘ１，ｙ１）とＰ２＝（ｘ２，ｙ２）とを結ぶ直線と楕円曲線との交点を、ｘ軸で折り返した点Ｐ３＝Ｐ１＋Ｐ２＝（ｘ３，ｙ３）として定義される。ｘ３，ｙ３は、以下の式で表せる。
【００１０】
ｘ３＝｛（ｙ１−ｙ２）／（ｘ１−ｘ２）｝＾２−ｘ１−ｘ２    ：（＾：べき乗を表す）
ｙ３＝｛（ｙ１−ｙ２）／（ｘ１−ｘ２）｝（ｘ１−ｘ３）−ｙ１
また、楕円２倍算は、図１６に示すように、点Ｐ１＝（ｘ１，ｙ１）の接線と楕円曲線との交点をｘ軸で折り返した点Ｐ４＝２×Ｐ１＝（ｘ４，ｙ４）として定義される。ｘ４，ｙ４は、以下の式で表せる。
【００１１】
ｘ４＝｛（３×ｘ１＾２＋ａ）／（２×ｙ１）｝＾２−２×ｘ１
ｙ４＝｛（３×ｘ１＾２＋ａ）／（２×ｙ１）｝（ｘ１−ｘ４）−ｙ１
有限体上の楕円曲線Ｅと、曲線上の点Ｐと、整数（スカラーとも呼ぶ）ｄに対して、点ｄ×Ｐ＝Ｐ＋Ｐ＋…Ｐ（ｄ個の和）を計算することをスカラー倍算という。スカラー倍算は、楕円加算と楕円２倍算の組み合わせによって実現される。
【００１２】
楕円加算、楕円２倍算、スカラー倍算の計算時間は、ＧＦ（ｑ）での乗算、平方算、逆元計算の計算時間の和によって見積もられることが多い。これは実際の楕円加算、楕円２倍算、スカラー倍算の計算は、ＧＦ（ｑ）での加算・減算・乗算・平方算・逆元計算の組み合わせで、多くの場合、加算・減算・定数による乗算の計算時間はその他の計算時間に比べて無視できるほど短いからである。例えば上記の楕円加算は、ＧＦ（ｐ＾ｍ）における２回の乗算と１回の平方算と１回の逆元計算が必要である。このことを計算時間２Ｍ＋１Ｓ＋１Ｉと記す。
【００１３】
一般にＧＦ（ｐ＾ｍ）での逆元計算の計算時間は、乗算・平方算の計算時間に比べて非常に大きくなる。このため実際のスカラー倍算では、楕円曲線の点を表現する上で射影座標が使用される。射影座標では、点は（Ｘ：Ｙ：Ｚ）のようなＧＦ（ｐ＾ｍ）の３つの要素の組み合わせで表される。ただし（Ｘ：Ｙ：Ｚ）とｒ≠０であるＧＦ（ｐ＾ｍ）の要素ｒに対し（ｒ×Ｘ：ｒ×Ｙ：ｒ×Ｚ）は同じ点と考える。Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線は射影座標では、ｘ＝Ｘ／Ｚ，ｙ＝Ｙ／Ｚを代入して、
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＋ｂ×Ｚ＾３
となる。また無限遠点は∞＝（０：１：０）となる。射影座標を用いると、楕円加算は１２Ｍ＋２Ｓ、楕円２倍算は７Ｍ＋５Ｓで計算できるアルゴリズムが知られている。さらに射影座標を改良したものに、Ｊａｃｏｂｉａｎ座標、Ｃｈｕｄｏｎｏｖｓｋｙ座標、改良Ｊａｃｏｂｉａｎ座標などがある。
【００１４】
一方、ＧＦ（ｐ＾ｍ）の要素Ａ，Ｂに対し、方程式
Ｂ×ｖ＾２＝ｕ＾３＋Ａ×ｕ＾２＋ｕ
を満たす点（ｕ，ｖ）の集合と、無限遠点∞と呼ばれる点の集合を、ＧＦ（ｐ＾ｍ）上のＭｏｎｔｏｇｍｅｒｙ型楕円曲線という。射影座標では、点はＧＦ（ｐ＾ｍ）の３つの要素の組（Ｕ：Ｖ：Ｗ）と表され、曲線は
Ｂ×Ｖ＾２×Ｗ＝Ｕ＾３＋Ａ×Ｕ＾２×Ｗ＋Ｕ×Ｗ＾２
となる。無限遠点は∞＝（０：１：０）である。Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線と同様に楕円加算・楕円２倍算の計算公式が知られている。
【００１５】
楕円曲線におけるスカラー倍計算は楕円加算（ＥＣＡＤＤ）と楕円２倍算（ＥＣＤＢＬ）と呼ばれる演算の組み合わせで実現されるため、全体の計算時間はこれら演算の計算回数として評価される。スカラー倍した点ｄ×Ｐの計算は、ｄの２進展開
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ［ｎ−２］×２＾（ｎ−２）＋・・・・＋ｄ［１］×２＋ｄ［０］
を利用して行われる。
【００１６】
図１７は、従来のスカラー倍算のアルゴリズム１を示す図である。
図１７において、変数Ｑ［０］の初期値Ｐとし、ステップ３で、点Ｑ［０］の楕円２倍算を実行し、演算結果をＱ［０］に格納する。そして、ｄ［ｉ］＝＝１であれば、ステップ５で、点Ｑ［０］と点Ｐの楕円加算ＥＣＡＤＤを実行し、演算結果をＱ［０］に格納する。
【００１７】
このアルゴリズム１のスカラー倍算に必要な計算時間は、平均で（ｎ−１）／２×ＥＣＡＤＤ＋（ｎ−１）×ＥＣＤＢＬである。２進展解法の代わりに符号付き２進展解法を用いることで平均計算時間を（ｎ−１）／３×ＥＣＡＤＤ＋（ｎ−１）×ＥＣＤＢＬに減らすことができる。この他にも平均計算時間が（ｎ−１）／４×ＥＣＡＤＤ＋（ｎ−１）×ＥＣＤＢＬとなる方法が知られている。
【００１８】
【発明が解決しようとする課題】
楕円曲線暗号が現実社会において広く用いられるには、処理時間および実装上必要となるリソース（メモリ・回路量等）の低減が求められる。楕円曲線暗号ではスカラー倍算と呼ばれる演算が共通して使用され、暗号処理全体における比重も高いため、この部分の性能向上が暗号全体の性能向上に直結する。楕円曲線暗号処理においてスカラー倍算処理の比重は高いため、さらなる高速化が望まれている。
【００１９】
しかしながら、上記のアルゴリズム１の演算方法では、楕円２倍算ＥＣＤＢＬの演算結果Ｑ［０］を元にして楕円加算ＥＣＡＤＤを行う必要があり、スカラー倍算の演算時間の短縮に限界があった。
【００２０】
また、楕円曲線暗号は、他の暗号に比べて短い鍵長で高い安全性を確保できることから、特にスマートカードなどの低性能デバイスでの利用が進んでいる。しかしこれらのデバイスに対してはサイドチャンネル攻撃が有効となる場合があり、この攻撃に耐性のあるスカラー倍算のアルゴリズムが必要となる。
【００２１】
本発明の課題は、サイドチャンネル攻撃に対する耐性のある楕円曲線暗号のスカラー倍算を、高速で行えるようにすることである。
【００２４】
本発明の楕円曲線暗号装置は、有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐとし、前記取得手段により取得した自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得した点Ｐの座標と自然数ｄとに基づいて、上記（１）から（４）の演算を、変数ｉをｎ−２から０まで１ずつ変化させて繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する演算手段とを備える。
【００２５】
この発明によれば、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬを並列に計算することができるので、スカラー倍算の演算時間を短縮できる。また、例えば、上記の（１）から（３）の演算において、ｄ［ｉ］に依らず、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬの演算が実行されるので、サイドアタックに対する耐性を持つことができる。
【００２６】
上記の発明において、前記演算手段は、Ｑ［０］を記憶する第１のレジスタと、Ｑ［１］を記憶する第２のレジスタとを有し、Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記楕円加算ＥＣＡＤＤ及び楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第１のレジスタに格納するようにしても良い。
【００２７】
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得する取得手段と、楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（＾：べき乗を表す）、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４×ｂ×（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する演算手段とを備える。
【００２８】
この発明によれば、点のｙ座標を使用せずに、楕円加算の点Ｐ３のｘ座標を計算できるので演算時間を短縮できる。
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１を取得する取得手段と、楕円曲線Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ（＾：べき乗を表す）としたときに、以下の式
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｂ×ｘ１］／［４×（ｘ１＾３＋ａ×ｘ１＋ｂ）］
によりｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を算出する演算手段とを備える。
【００２９】
この発明によれば、点のｙ座標を使用せずに、楕円２倍算の点Ｐ４のｘ座標を計算することができるので演算時間を短縮できる。
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得する取得手段と、
楕円曲線Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１のとき、
（１）・・・Ｘ３＝Ｚ３’×［２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２］−Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
（２）・・・Ｚ３＝Ｚ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
前記取得手段により取得した点Ｐ１，Ｐ２，Ｐ３’のＸ座標とＺ座標に基づいて、上記の（１）と（２）式により、射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに計算する演算手段とを備える。
【００３０】
この発明によれば、射影座標のＹ座標を用いずに、楕円加算Ｐ３の射影座標におけるＸ座標とＺ座標を計算することができるので、計算時間を短縮できる。
本発明の他の楕円曲線暗号装置は、有限体上の楕円曲線の点Ｐ１の射影座標におけるＰ１のＸ座標Ｘ１，Ｚ座標Ｚ１を取得する取得手段と、
楕円曲線Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ１≠０の場合に、
（１）・・・Ｘ４＝（Ｘ１＾２−ａ×Ｚ１＾２）＾２−８×ｂ×Ｘ１×Ｚ１＾３；（＾：べき乗を表す）
（２）・・・Ｚ４＝４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）
前記取得手段により取得した点Ｐの座標と、上記（１）と（２）式から射影座標における楕円２倍算Ｐ４＝２×Ｐ１のＸ座標Ｘ４とＺ座標Ｚ４を、Ｙ座標を用いずに演算する演算手段とを備える。
【００３１】
この発明によれば、射影座標のＹ座標を用いずに、楕円２倍算Ｐ４の射影座標におけるＸ座標とＺ座標を計算することができるので、計算時間を短縮できる。
【００３２】
【発明の実施の形態】
以下、本発明の実施の形態を、図面を参照しながら説明する。実施の形態の楕円曲線暗号装置は、例えば、楕円曲線暗号の専用の情報処理装置、パーソナルコンピュータ、ＩＣカード等に内蔵されたＩＣチップ、携帯電話、携帯情報端末装置（ＰＤＡなど）、ＤＶＤプレーヤ等からなり、少なくとも２個のプロセッサを有し、後述する楕円加算ＥＣＡＤＤと、楕円２倍算ＥＣＤＢＬの演算を並列に実行できる機能を有している。
【００３３】
以下の説明では、本発明に係る楕円曲線暗号の演算方法を、要素数ｐ＾ｍ（＾：べき乗を表す）の有限体ＧＦ（ｐ＾ｍ）上のＷｉｅｒｓｔｒａｓｓ型楕円曲線に適用した場合について説明する。
【００３４】
Ｗｉｅｒｓｔｒａｓｓ型楕円曲線Ｅは、以下の式で表せる。
Ｅ：Ｙ＾２＝Ｘ＾３＋ａ×ｘ＋ｂ
図１は、本発明の第１の実施の形態の楕円曲線暗号のスカラー倍算ｄ×Ｐの演算アルゴリズムであるアルゴリズム２を示す図である。
【００３５】
楕円曲線Ｅ上の点Ｐの座標（ｘ、ｙ）と、ｎビットの自然数ｄを取得（または入力）する。自然数ｄの２進展開を、
ｄ＝ｄ［ｎ−１］×２＾（ｎ−１）＋ｄ（ｎ−２）×２＾（ｎ−２）＋・・・・・・＋ｄ［１］×２＋ｄ［０］
（ｄ［ｎ−１］≠０，ｄ［ｉ］＝０，１）
とする。
【００３６】
最初のステップＳ１で、変数Ｑ［０］の初期値としてＰを、変数Ｑ［１］の初期値として０を設定する。
次のステップＳ２は、ループを一巡する毎に、ｉを０からｎ−１まで１づつ変化させる。
【００３７】
次のステップＳ３は、Ｑ［０］とＱ［１］の楕円加算ＥＣＡＤＤを実行し、演算結果をＱ［２］に格納する。
次のステップＳ４は、Ｑ［０］の楕円２倍算ＥＣＤＢＬを実行し、演算結果をＱ［０］に格納する。
【００３８】
次のステップＳ５は、ｄ［ｉ］の値で決まるＱ［１＋ｄ［ｉ］］、すなわち、Ｑ［０］またはＱ［２］を、Ｑ［１］に格納する。
上記のステップＳ２〜Ｓ５の処理をｉ＝０からｎ−１まで繰り返して、最終的な演算結果のＱ［１］をｄ×Ｐとして求める。
【００３９】
上記のアルゴリズム２は、楕円加算ＥＣＡＤＤと、楕円２倍算ＥＣＤＢＬとを独立に計算することができる。
従って、上記のアルゴリズム２の楕円加算ＥＣＡＤＤと、楕円２倍算ＥＣＤＢＬとを、２個のプロセッサで並列に計算することでスカラー倍算の演算時間を短縮できる。
【００４０】
次に、図２は、本発明の第２の実施の形態の楕円曲線暗号のスカラー倍算ｄ×Ｐの演算アルゴリズムであるアルゴリズム３を示す図である。
楕円曲線Ｅ上の点Ｐの座標（ｘ、ｙ）と、ｎビットの自然数ｄを入力する。
【００４１】
最初のステップＳ１は、Ｑ［０］の初期値としてＰ、Ｑ［１］の初期値として２×Ｐを設定する。
次のステップＳ２は、ループを一巡する毎に、ｉをｎ−２から０まで１づつ変化させる。
【００４２】
次のステップＳ３は、Ｑ［ｄ［ｉ］］の楕円２倍算ＥＣＤＢＬを実行し、演算結果をＱ［２］に格納する。
次のステップＳ４は、Ｑ［０］とＱ［１］の楕円加算ＥＣＡＤＤを実行し、演算結果をＱ［１］に格納する。
【００４３】
次のステップＳ５は、Ｑ［０］にＱ［２−ｄ［ｉ］］を格納する。
次のステップＳ６は、Ｑ［１］にＱ［１＋ｄ［ｉ］］を格納する。
ｄ［ｉ］＝０の場合、ステップＳ５の処理で、Ｑ［２−ｄ［ｉ］］はＱ［２］となるので、楕円２倍算ＥＣＤＢＬの演算結果のＱ［２］がＱ［０］に格納される。また、その場合、ステップＳ５の処理のＱ［１＋ｄ［ｉ］］がＱ［１］となるので、楕円加算ＥＣＡＤＤの演算結果のＱ［１］がＱ［１］に格納される。
【００４４】
他方、ｄ［ｉ］＝１の場合には、ステップＳ５の処理で、Ｑ［２−ｄ［ｉ］］はＱ［１］となるので、楕円加算ＥＣＡＤＤの演算結果のＱ［１］がＱ［０］に格納される。また、その場合、ステップＳ６の処理のＱ［１＋ｄ［ｉ］］がＱ［２］となるので、楕円２倍算ＥＣＤＢＬの演算結果のＱ［２］がＱ［１］に格納される。
【００４５】
上記のアルゴリズム３は、楕円加算ＥＣＡＤＤと、楕円２倍算ＥＣＤＢＬとを独立に計算することができる。従って、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬを、２個のプロセッサで並列に計算することでスカラー倍算の演算時間を短縮できる。
【００４６】
さらに、上記アルゴリズム２及び３は、アルゴリズム１と比べた場合に、ｄ［ｉ］の値に依らず楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬの演算を実行するので、暗号のサイドチャンネル耐性を保持することができる。
【００４７】
図３は楕円曲線暗号装置の楕円曲線暗号プログラムのフローチャートである。最初に、楕円曲線Ｅの係数と、ベースポイントＰと、送信先発行の公開鍵を取得する（図３，Ｓ１１）。
【００４８】
次に、上述したアルゴリズム２または３を利用してスカラー倍演算を実行する（Ｓ１２）。
次に、スカラー倍算の演算結果を使用して暗号文を生成する（Ｓ１３）。最後に、生成した暗号文を送信先に送信する（Ｓ１４）。
【００４９】
楕円曲線暗号においては、例えば、秘密鍵ｓと楕円曲線上の点Ｐのスカラー倍算を行って公開鍵を生成している。
ここで、アルゴリズム３を用いた場合のスカラー倍算（図３のステップＳ１２）の具体的処理の一例を、図４を参照して説明する。
【００５０】
図４は、アルゴリズム３に基づく楕円曲線暗号プログラムの楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬを、２個のプロセッサで並列に実行する場合の処理内容を示している。
【００５１】
楕円曲線暗号装置は、２個のレジスタ１１，１２を有しており、レジスタ１１は、変数Ｑ［０］を記憶し、レジスタ１２は、変数Ｑ［１］を記憶する。
Ｑ［０］の初期値Ｐ、Ｑ［１］の初期値２×Ｐをそれぞれのレジスタ１１，１２に設定する。
【００５２】
第１のプロセッサが、Ｑ［０］にＱ［ｄ［ｉ］］を設定し（図４，Ｓ２１）、Ｑ［０］の楕円２倍算ＥＣＤＢＬを行い、演算結果をＱ［０］に設定する（Ｓ２２）。
【００５３】
また、別のプロセッサが、レジスタ１１に格納されているＱ［０］と、レジスタ１２に格納されているＱ［１］を読み出し、それらの点の楕円加算ＥＣＡＤＤを行い、演算結果をＱ［１］に設定する。
【００５４】
ｄ［ｉ］＝０の場合には、Ｑ［０］をレジスタ１１に、Ｑ［１］をレジスタ１２に格納する。また、ｄ［ｉ］＝１の場合には、ＳＷＡＰ動作をして、Ｑ［０］の内容をレジスタ１２に、Ｑ［１］の内容をレジスタ１１に格納する。
【００５５】
上記の処理を、ｉ＝ｎ−２から０まで繰り返す。
アルゴリズム３を使用すると、スカラー倍算においてＥＣＡＤＤとＥＣＤＢＬの並列計算が可能となる。並列計算を行った場合、通常ＥＣＡＤＤの計算時間の方がＥＣＤＢＬの計算時間よりも大きいため、全体の計算時間は１×ＥＣＤＢＬ＋（ｎ−１）×ＥＣＡＤＤとなり、計算時間を大幅に短縮できる。
【００５６】
次に、本発明の第３の実施の形態を説明する。この第３の実施の形態は、ｙ座標を使用せずに、乗算的（ｘ３とｘ３’が乗算の関係にあることを意味する）な楕円加算により、Ｐ３＝Ｐ１＋Ｐ２のｘ座標を求めるものである。
【００５７】
ＧＦ（ｐ＾ｍ）（要素数ｐの有限体、ｐは５以上の素数）上で定義されたＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅを、
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ，
とする。ａ，ｂはＧＦ（ｐ＾ｍ）の元，４×ａ＾３＋２７×ｂ＾２≠０
楕円曲線Ｅの点Ｐ１のｘ座標ｘ１と、点Ｐ２のｘ座標ｘ２と、Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得する。Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３とする。
（ａ）Ｐ３’＝∞の場合には、楕円２倍算２×Ｐ１によりｘ４を求め、それを出力する。
（ｂ）Ｐ３’≠∞，ｘ１＝ｘ２の場合には、無限遠点∞を出力する。
（ｃ）Ｐ３’≠∞，ｘ１≠ｘ２の場合には、
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４×ｂ×（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
上記の式によりｘ３を求めて出力する。
【００５８】
この第３の実施の形態は、ｙ座標を使用せずに、楕円加算ＥＣＡＤＤのｘ座標を求めることができるので、楕円加算ＥＣＡＤＤの演算プログラムが簡素になり、演算時間を短縮できる。
【００５９】
次に、本発明の第４の実施の形態を説明する。この第４の実施の形態は、ｙ座標を使用せずに、加算的（ｘ３とｘ３’が加算の関係にあることを意味する）な楕円加算により、Ｐ３＝Ｐ１＋Ｐ２のｘ座標を求めるものである。
【００６０】
Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅの点Ｐ１のｘ座標ｘ１と、点Ｐ２のｘ座標ｘ２と、Ｐ３’＝Ｐ１−Ｐ２のｘ座標ｘ３’を取得する。
（ａ）Ｐ３’＝∞場合には、楕円２倍算２×Ｐ１の結果ｘ４を出力する。
（ｂ）Ｐ３’≠∞，ｘ１＝ｘ２の場合には、無限遠点∞を出力する。
（ｃ）Ｐ３’≠∞，ｘ１≠ｘ２の場合には、
ｘ３＝［２×（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４×ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
上記の式により、ｘ３を求めて出力する。
【００６１】
この第４の実施の形態によれば、楕円加算Ｐ３＝Ｐ１＋Ｐ２のｘ座標の計算を、ｙ座標を使用せずに行うことができるので、楕円加算ＥＣＡＤＤの演算プログラムが簡素になり、演算時間を短縮できる。
【００６２】
次に、本発明の第５の実施の形態を説明する。この第５の実施の形態は、ｙ座標を使用せずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標を求めるものである。
Ｗｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点Ｐ１のｘ座標を取得する。
【００６３】
ＧＦ（ｐ＾ｍ）を、要素数ｐの有限体とする。ｐは５以上の素数。
ＧＦ（ｐ＾ｍ）上で定義されたＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅを、
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ
とする。ａ，ｂはＧＦ（ｐ＾ｍ）の元，４×ａ＾３＋２７×ｂ＾２≠０
（ａ）Ｐ１＝∞の場合には、無限遠点∞を出力する。
（ｂ）Ｐ１≠∞の場合には、
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｂ×ｘ１］／［４×（ｘ１＾３＋ａ×ｘ１＋ｂ）］
上記の式によりｘ４を算出する。
【００６４】
この第５の実施の形態によれば、ｙ座標を用いずに、楕円２倍算の計算を行えるので、演算プログラムが簡素になり、演算時間を短縮できる。
次に、本発明の第６の実施の形態を説明する。この第６の実施の形態は、射影座標のＹ座標を使用せずに、乗算的な楕円加算を行い、Ｐ３＝Ｐ１＋Ｐ２のＸ座標とＺ座標を求めるものである。
【００６５】
有限体ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点Ｐ１、Ｐ２，Ｐ３’＝Ｐ１−Ｐ２のｘ座標を入力する。
楕円曲線Eの点Ｐ１の射影座標におけるＸ座標Ｘ１、Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２、Ｚ座標Ｚ２、点Ｐ３’のＸ座標Ｘ３’，Ｚ座標Ｚ３’、Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３，Ｚ座標はＺ３とし、
楕円曲線Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３
とし、
（ａ）Ｚ３’＝０の場合には、楕円２倍算２×Ｐ１の演算結果Ｘ４とＺ４を出力する。
（ｂ）Ｚ３’≠０，Ｘ１×Ｚ２＝Ｘ２×Ｚ１の場合には、Ｘ３＝０，Ｚ３＝０を出力する。
（ｃ）Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合には、
（１Ａ）・・・Ｘ３＝Ｚ３’×［（Ｘ１×Ｘ２−ａ×Ｚ１×Ｚ２）＾２−４×ｂ×Ｚ１×Ｚ２×（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）］
（２Ａ）・・・Ｚ３＝Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１Ａ）式と（２Ａ）式により、Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を算出する。
【００６６】
この第６の実施の形態によれば、射影座標のＹ座標を使用せずに、楕円加算の演算を行えるので、演算プログラムが簡素になり、演算時間を短縮できる。
次に、図５は、上述した第６の実施の形態の具体的な演算プログラムの一例を示す図である。
【００６７】
図５の演算プログラムは、第６の実施の形態の（１Ａ）式と（２Ａ）式の演算を実現するものであり、以下の処理からなる。
（１）点Ｐ１のＸ座標Ｘ１と点Ｐ２のＸ座標Ｘ２を乗算し、結果をメモリまたはレジスタからなる（以下同じ）Ｔ１に設定する。
（２）点Ｐ１のＺ座標Ｚ１と点Ｐ２のＺ座標Ｚ２を乗算し、結果をＴ２に設定する。
（３）Ｘ１とＺ２を乗算し、結果をＴ３に設定する。
（４）Ｘ２とＺ１を乗算し、結果をＴ４に設定する。
（５）Ｔ２にａを乗算し、結果をＴ５に設定する。
（６）Ｔ１からＴ５減算し、結果をＴ６に設定する。この処理は、“Ｘ１×Ｘ２−ａ×Ｚ１×Ｚ２”の演算に対応する。
（７）Ｔ６の２乗を求め、結果をＴ７に設定する。この処理は、（１Ａ）式の“（Ｘ１×Ｘ２−ａ×Ｚ１×Ｚ２）｝＾２”の演算に対応する。
（８）Ｔ２にｂを乗算し、結果をＴ８に設定する。
（９）Ｔ８に４を乗算し、結果をＴ９に設定する。
（１０）Ｔ３とＴ４を加算し、結果をＴ１０に設定する。
（１１）Ｔ９とＴ１０を乗算し、結果をＴ１１に設定する。
（１２）Ｔ７からＴ１１を減算し、結果をＴ１２に設定する。
（１３）Ｚ３’とＴ１２を乗算し、結果をＸ３として設定する。これにより、（１Ａ）式のＸ３座標が求まる。
（１４）Ｔ３からＴ４を減算し、結果をＴ１３に設定する。
（１５）Ｔ１３の２乗を求め、結果をＴ１４に設定する。
（１６）Ｘ３’とＴ１４を乗算し、結果をＺ３として設定する。これにより、（２Ａ）式のＺ３座標が求まる。
【００６８】
上記の演算プログラムによれば、９回の乗算と、２回の平方算と、数回の加算・減算・定数の乗算とにより、楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標とＺ座標を計算することができる。
【００６９】
次に、図６は、Ｚ３’＝１の場合における、第６の実施の形態の（１Ａ）及び（２Ａ）式の具体的な演算プログラムを示す図である。
この場合、Ｚ３’＝１であるので、図５の演算プログラムの（１３）の“Ｚ３’×Ｔ１２”の乗算が不要となる。
【００７０】
従って、図６の演算プログラムは、８回の乗算と、２回の平方算と、数回の加算・減算・定数の乗算により、楕円加算の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算することができる。
【００７１】
次に、本発明の第７の実施の形態を説明する。この第７の実施の形態は、射影座標のＹ座標を使用せずに、楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を求めるものである。
【００７２】
この第７の実施の形態においては、
（ａ）Ｚ３’＝０場合には、楕円２倍算２×Ｐ１の結果Ｘ４，Ｚ４を出力する。
（ｂ）Ｚ３’≠０，Ｘ１×Ｚ２＝Ｘ２×Ｚ１の場合には、Ｘ３＝０，Ｚ３＝０を出力する。
（ｃ）Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合には、
（１Ａ）・・・Ｘ３＝Ｚ３’×［２×（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａ×Ｚ１×Ｚ２）＋４×ｂ×Ｚ１＾２×Ｚ２＾２］−Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
（２Ａ）・・・Ｚ３＝Ｚ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１Ａ）式と（２Ａ）とにより、楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を求めることができる。
【００７３】
この第７の実施の形態によれば、射影座標におけるＹ座標を用いずに、楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３とを求めることができるので、演算時間を短縮できる。
【００７４】
次に、図７は、第７の実施の形態の（１Ａ）及び（２Ａ）式の演算プログラムを示しており、以下の処理からなる。
（１）点Ｐ１のＸ座標Ｘ１と点Ｐ２のＸ座標Ｘ２を乗算し、結果をメモリまたはレジスタからなるＴ１に設定する。
（２）点Ｐ１のＺ座標Ｚ１と点Ｐ２のＺ座標Ｚ２を乗算し、結果をＴ２に設定する。
（３）Ｘ１とＺ２を乗算し、結果をＴ３に設定する。
（４）Ｘ２とＺ１を乗算し、結果をＴ４に設定する。
（５）Ｔ３とＴ４を加算し、結果をＴ５に設定する。
（６）Ｔ２にａを乗算し、結果をＴ６に設定する。
（７）Ｔ１とＴ６を加算し、結果をＴ７に設置する。
（８）Ｔ５とＴ７を乗算し、結果をＴ８に設定する。この処理は、“（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）”の演算に対応する。
（９）Ｔ８に２を乗算し、結果をＴ９に設定する。
（１０）Ｔ２の２乗を計算し、結果をＴ１０に設定する。
（１１）Ｔ１０にｂを乗算し、結果をＴ１１に設定する。
（１２）Ｔ１１に４を乗算し、結果をＴ１２に設定する。
（１３）Ｔ９とＴ１２を加算し、結果をＴ１３に設定する。
（１４）Ｔ３からＴ４を減算し、結果をＴ１４に設定する。
（１５）Ｔ１４の２乗を計算し、結果をＴ１５に設定する。
（１６）Ｚ３’とＴ１３を乗算し、結果をＴ１６に設定する。
（１７）Ｘ３’とＴ１５を乗算し、結果をＴ１７に設定する。
（１８）Ｔ１６からＴ１７を減算し、結果を射影座標のＸ座標Ｘ３として求める。
（１９）Ｚ３’とＴ１５を乗算して、結果を射影座標のＺ座標Ｚ３として求める。
【００７５】
上記の演算プログラムによれば、１０回の乗算と、２回の平方算と、数回の加算・減算・定数による乗算で、楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算することができる。
【００７６】
次に、図８は、Ｚ３’＝１の場合における、第７の実施の形態の（１Ａ）及び（２Ａ）式の具体的な演算プログラムを示す図である。
この場合、Ｚ３’＝１であるので、図７の演算プログラムの（１６）の“Ｚ３’×Ｔ１３”の処理と、（１９）の“Ｚ３’×Ｔ１５”の処理が不要となる。従って、図８の演算プログラムは、８回の乗算と、２回の平方算と、数回の加算・減算・定数による乗算により、楕円加算の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算することができる。
【００７７】
次に、本発明の第８の実施の形態を説明する。この第８の実施の形態は、射影座標におけるＹ座標を使用せずに、楕円２倍算Ｐ４＝２×Ｐ１のＸ座標Ｘ４とＺ座標Ｚ４とを計算するものである。
【００７８】
ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅ上の点Ｐ１のＸ座標Ｘ１とＺ座標Ｚ１を入力する。
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３，
楕円曲線Eの点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、Ｐ４＝２×Ｐ１のＸ座標Ｘ４，Ｚ座標Ｚ４とする。
（ａ）Ｚ１＝０の場合には、Ｘ４＝０，Ｚ４＝０を出力する。
（ｂ）Ｚ１≠０の場合には、
（１Ａ）・・・Ｘ４＝（Ｘ１＾２−ａ×Ｚ１＾２）＾２−８×ｂ×Ｘ１×Ｚ１＾３
（２Ａ）・・・Ｚ４＝４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）
上記の（１Ａ）及び（２Ａ）式により、楕円２倍算の点Ｐ４の射影座標におけるＸ座標Ｘ４とＺ座標Ｚ４を計算する。
【００７９】
この第８の実施の形態によれば、Ｙ座標を使用せずに、楕円２倍算Ｐ４＝２×Ｐの射影座標におけるＸ座標Ｘ４とＺ座標Ｚ４を計算することができるので、演算時間を短縮することができる。
【００８０】
次に、図９は、上記の第８の実施の形態の（１Ａ）及び（２Ａ）式の具体的な演算プログラムの一例を示しており、以下の処理からなる。
（１）点Ｐ１の射影座標におけるＸ座標のＸ１の２乗を計算し、結果をＴ１に設定する。
（２）同様に、点Ｐ１の射影座標におけるＺ座標のＺ１の２乗を計算し、結果をＴ２に設定する。
（３）Ｔ２にａを乗算し、結果をＴ３に設定する。
（４）Ｔ１からＴ３を減算し、結果をＴ４に設定する。
（５）Ｔ４の２乗を計算し、結果をＴ５に設定する。
（６）Ｔ２にｂを乗算し、結果をＴ６に設定する。
（７）点Ｐ１の座標Ｘ１とＺ１を乗算し、結果をＴ７に設定する。
（８）Ｔ６とＴ７を乗算し、結果をＴ８に設定する。
（９）Ｔ８に８を乗算し、結果をＴ９に設定する。
（１０）Ｔ５からＴ９を減算し、結果を点Ｐ４のＸ座標Ｘ４として求める。
（１１）Ｔ１とＴ３を加算し、結果をＴ１０に設定する。
（１２）Ｔ７とＴ１０を乗算し、結果をＴ１１に設定する。
（１３）Ｔ６とＴ２を乗算し、結果をＴ１２に設定する。
（１４）Ｔ１１とＴ１２を加算し、結果をＴ１３に設定する。
（１５）Ｔ１３に４を乗算し、結果を点Ｐ４の座標Ｚ４として求める。
【００８１】
上記の演算プログラムによれば、６回の乗算と、３回の平方算と、数回の加算・減算・定数の乗算とにより、楕円２倍算Ｐ４＝２×Ｐ１のＸ座標Ｘ４とＺ座標Ｚ４を計算できるので、演算時間を短縮することができる。
【００８２】
次に、本発明の第９の実施の形態を説明する。この第９の実施の形態は、楕円曲線Ｅの点Ｐのｘ座標とｙ座標と、点Ｐ［ｄ］とＰ［ｄ＋１］のｘ座標を取得して、点Ｐ［ｄ］のｙ座標を計算するものである。
【００８３】
ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅの点Ｐのｘ座標とｙ座標，点Ｐ［ｄ］，Ｐ［ｄ＋１］のｘ座標を取得する。
Ｅ：ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ，
ａ，ｂはＧＦ（ｐ＾ｍ）の元、４×ａ＾３＋２７×ｂ＾２≠０
楕円曲線Ｅの点Ｐ＝（ｘ，ｙ）、Ｐ［ｄ］＝ｄ×Ｐのｘ座標ｘ［ｄ］、Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐのｘ座標をｘ［ｄ＋１］とする。
【００８４】
ｙ［ｄ］＝［ｙ＾２＋ｘ［ｄ］＾３＋ａ×ｘ［ｄ］＋ｂ−（ｘ−ｘ［ｄ］）＾２×（ｘ＋ｘ［ｄ］＋ｘ［ｄ＋１］）］／［２×ｙ］
上記の式から点Ｐ［ｄ］のｙ座標を求めることができる。
【００８５】
この第９の実施の形態によれば、前述した演算方法により、ｙ座標を使用せずに、点Ｐ［ｄ］、Ｐ［ｄ＋１］のｘ座標を計算し、次に、そのｘ座標を利用して、ｙ座標を求めることができるので、演算時間を短縮できる
次に、本発明の第１０の実施の形態を説明する。この第１０の実施の形態は、Ｐ［ｄ］、Ｐ［ｄ＋１］の射影座標におけるＸ座標とＺ座標を取得した後、Ｐ［ｄ］の射影座標におけるＹ座標を求めるものである。
【００８６】
ＧＦ（ｐ＾ｍ）上のＷｅｉｅｒｓｔｒａｓｓ型楕円曲線Ｅの点Ｐのｘ座標とｙ座標、点Ｐ［ｄ］、Ｐ［ｄ＋１］の射影座標におけるＸ座標、Ｚ座標を取得する。
【００８７】
ＧＦ（ｐ＾ｍ）上で定義されたＷｅｉｅｒｓｔｒａｓｓ型楕円曲線を
Ｅ：Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３，
とする。ａ，ｂはＧＦ（ｐ＾ｍ）の元、４×ａ＾３＋２７×ｂ＾２≠０
楕円曲線Ｅ上の点Ｐ＝（ｘ，ｙ）、Ｐ［ｄ］＝ｄ×Ｐの射影座標におけるＸ座標をＸ［ｄ］，Ｚ座標をＺ［ｄ］、Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐの射影座標におけるＸ座標をＸ［ｄ＋１］，Ｚ座標をＺ［ｄ＋１］とする。また、射影座標を、Ｘ’［ｄ］＝ｒ×Ｘ［ｄ］、Ｙ’［ｄ］＝ｒ×Ｙ［ｄ］、Ｚ’［ｄ］＝ｒ×Ｚ［ｄ］とし、ｒとしてＹ［ｄ］の分母の値を設定する。
【００８８】
Ｐ［ｄ］の射影座標は、以下の式で表せる。
（１Ａ）・・・Ｘ’［ｄ］＝２×ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］
（２Ａ）・・・Ｙ’［ｄ］＝Ｚ［ｄ＋１］×（ｙ＾２×Ｚ［ｄ］＾３＋Ｘ［ｄ］＾３＋ａ×Ｘ［ｄ］×Ｚ［ｄ］＾２＋ｂ×Ｚ［ｄ］＾３）−（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２×（ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ＋１］×Ｚ［ｄ］）
（３Ａ）・・・Ｚ’［ｄ］＝２×ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］
上記の（２Ａ）式からＰ［ｄ］の射影座標におけるＹ座標を、除算を含まない式により計算することができる。射影座標においては、（Ｘ［ｄ］：Ｙ［ｄ］：Ｚ［ｄ］）と、各成分をｒ倍した（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）とは等しいので、上記の結果からＰ［ｄ］のＹ座標を求めることができる。
【００８９】
この第１０の実施の形態によれば、除算を行わずに楕円加算の点Ｐ［ｄ］の射影座標におけるＹ座標を求めることができるので、演算時間を短縮できる。
図１０は、第１０の実施の形態の具体的な演算プログラムの一例を示すである。この演算プログラムは、以下の処理からなる。
（１）点Ｐ［ｄ］のＺ座標Ｚ［ｄ］の２乗を計算し、結果をＴ１に設定する
（２）Ｔ１とＺ［ｄ＋１］を乗算し、結果をＴ２に設定する。この処理は、“Ｚ［ｄ］＾２×Ｚ［ｄ＋１］”の演算に対応する。
（３）点ＰのＹ座標ｙとＴ２を乗算し、結果をＴ３に設定する。この処理は、“ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］”の演算に対応する。
（４）Ｐ［ｄ］の射影座標におけるＸ座標Ｘ［ｄ］とＴ３を乗算し、結果をＴ４に設定する。この処理は、“ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］”の演算に対応する。
（５）Ｔ４に２を乗算し、結果をＸ’［ｄ］に設定する。
（６）Ｐ［ｄ］の射影座標におけるＺ座標Ｚ［ｄ］とＴ３を乗算し、結果をＴ５に設定する。この処理は、“ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］”の演算に対応する。
（７）Ｔ５に２を乗算し、結果をＺ’［ｄ］に設定する。
（８）Ｘ［ｄ］の２乗を計算し、結果をＴ６に設定する。
（９）Ｔ１にａを乗算し、結果をＴ７に設定する。
（１０）Ｔ６とＴ７を加算し、結果をＴ８に設定する。
（１１）Ｘ［ｄ］と点Ｐ［ｄ＋１］のＺ座標Ｚ［ｄ＋１］を乗算し、結果をＴ９に設定する。
（１２）Ｔ９とＴ８を乗算し、結果をＴ１０に設定する。この処理は、“Ｘ［ｄ］×Ｚ［ｄ＋１］×（Ｘ［ｄ］＾２＋ａＺ［ｄ］＾２）”の演算に対応する。
（１３）ｙとＴ５を乗算し、結果をＴ１１に設定する。この処理は、“ｙ＾２×Ｚ［ｄ］＾３×Ｚ［ｄ＋１］”の演算に対応する。
（１４）Ｚ［ｄ］にｂを乗算し、結果をＴ１２に設定する。
（１５）Ｔ１２とＴ２を乗算し、結果をＴ１３に設定する。この処理は、“ｂＺ［ｄ］＾３×Ｚ［ｄ＋１］”の演算に対応する。
（１６）ｘとＺ［ｄ］を乗算し、結果をＴ１４に設定する。
（１７）Ｔ１４からＸ［ｄ］を減算し、結果をＴ１５に設定する。この処理は、“ｘ×Ｚ［ｄ］−Ｘ［ｄ］”の演算に対応する。
（１８）Ｔ１５の２乗を計算し、結果をＴ１６に設定する。この処理は、“（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２”の演算に対応する。
（１９）Ｔ１４とＺ［ｄ＋１］を乗算し、結果をＴ１７に設定する。この処理は、“ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］”の演算に対応する。
（２０）Ｘ［ｄ＋１］とＺ［ｄ］を乗算し、結果をＴ１８に設定する。
（２１）Ｔ１７とＴ９とＴ１８を加算し、結果をＴ１９に設定する。
（２２）Ｔ１６とＴ１９を乗算し、結果をＴ２０に設定する。
（２３）Ｔ１０とＴ１１とＴ１３を加算し、Ｔ２０を減算した結果をＹ’［ｄ］に設定する。これにより、点Ｐ［ｄ］の射影座標におけるＹ座標Ｙ’［ｄ］を求めることができる。
【００９０】
上記の演算プログラムは、１４回の乗算と、３回の平方算と、数回の加算・減算・定数による乗算で実現できる。
次に、第１１の実施の形態を説明する。この第１１の実施の形態は、第３の実施の形態のｙ座標を使用しない乗算的な楕円加算の演算方法と、第５の実施の形態のｙ座標を使用しない楕円２倍算の演算方法と、第９の実施の形態の射影座標におけるＰ［ｄ］の座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を求める演算方法により、Ｐ［ｄ］＝ｄ×Ｐの演算を実行する。
【００９１】
この第１１の実施の形態では、ＧＦ（ｐ＾ｍ）の楕円曲線Ｅの点Ｐのｘ座標とｙ座標、ｎビットの自然数ｄを入力し、初期値Ｑ［０］＝Ｐ、Ｑ［１］＝０として、図２のアルゴリズム３を用いる。
【００９２】
すなわち、図２のアルゴリズム３における楕円加算ＥＣＡＤＤを、第３の実施の形態のｙ座標を使用しない乗算的な楕円加算の演算方法により実行し、楕円２倍算ＥＣＤＢＬを、第５の実施の形態のｙ座標を使用しない楕円２倍算の演算方法により実行する。そして、アルゴリズム３のループが終了した後、ｘ［ｄ］＝Ｑ［０］、ｘ［ｄ＋１］＝Ｑ［１］とおき、第９の実施の形態の演算プログラムにより、点Ｐ［ｄ］、Ｐ［ｄ＋１］のｘ座標からＰ［ｄ］のｙ座標を計算する。
【００９３】
次に、本発明の第１２の実施の形態を説明する。この第１２の実施の形態は、第４の実施の形態のｙ座標を使用しない加算的な楕円加算の演算方法と、第５の実施の形態のｙ座標を使用しない楕円２倍算の演算方法と、第９の実施の形態のｙ座標を計算する演算方法とを用いて、Ｐ［ｄ］＝ｄ×Ｐを計算する。
【００９４】
この第１２の実施の形態では、楕円曲線Ｅ上の点Ｐの座標と、ｎビットの自然数ｄを入力し、図２のアルゴリズム３の演算プログラムにおける楕円加算ＥＣＡＤＤを、第４の実施の形態のｙ座標を使用しない加算的な楕円加算の演算方法により計算し、楕円２倍算ＥＣＤＢＬを、第５の実施の形態のｙ座標を使用しない楕円２倍算の演算方法により計算する。そして、アルゴリズム３のループが終了した後、ｘ［ｄ］＝Ｑ［０］、ｘ［ｄ＋１］＝Ｑ［１］とおき、第９の実施の形態の演算方法により、点Ｐ［ｄ］、Ｐ［ｄ＋１］のｘ座標からＰ［ｄ］のｙ座標を計算する。
【００９５】
次に、本発明の第１３の実施の形態を説明する。この第１３の実施の形態は、第６の実施の形態の射影座標におけるＹ座標を使用しない乗算的な楕円加算の演算方法と、第８の実施の形態の射影座標におけるＹ座標を使用しない楕円２倍算の演算方法と、第１０の実施の形態の射影座標におけるＰ［ｄ］の座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を求める演算方法とを用いて、Ｐ［ｄ］＝ｄ×Ｐを計算する。
【００９６】
この第１３の実施の形態は、楕円曲線Ｅの点Ｐのｘ座標とｙ座標、ｎビットの自然数ｄを入力し、初期値Ｑ［０］＝（ｘ：１）、Ｑ［１］＝（０：１）とし、図２のアルゴリズム３の演算プログラムを用いる。また、点Ｐの射影座標における座標値を（Ｘ：Ｙ：Ｚ）とする。
【００９７】
図２のアルゴリズム３の演算プログラムの楕円加算ＥＣＡＤＤを、第６の実施の形態の射影座標におけるＹ座標を使用しない乗算的な楕円加算の演算方法により計算し、楕円２倍算ＥＣＤＢＬを、第８の実施の形態の射影座標におけるＹ座標を使用しない楕円２倍算の演算方法により計算する。
【００９８】
そして、アルゴリズム３のループが終了したなら、Ｘ［ｄ］をＱ［０］の第１成分（Ｘ成分）、Ｚ［ｄ］をＱ［０］の第２成分（Ｚ成分）、Ｘ［ｄ＋１］をＱ［１］の第１成分（Ｘ成分）、Ｚ［ｄ＋１］をＱ［１］の第２成分（Ｚ成分）とおき、第１０の実施の形態の演算方法を用いて、Ｘ’［ｄ］、Ｙ’［ｄ］、Ｚ’［ｄ］を計算する。さらに、ｘ［ｄ］＝Ｘ’［ｄ］／Ｚ’［ｄ］及びｙ［ｄ］＝Ｙ’［ｄ］／Ｚ’［ｄ］から、点Ｐ［ｄ］のｘ座標、ｙ座標を計算する。
【００９９】
なお、上記の第１３の実施の形態において、アルゴリズム３の楕円加算ＥＣＡＤＤを、図５の第６の実施の形態の楕円加算の演算プログラムにより行い、楕円２倍算ＥＣＤＢＬを、図９の第８の実施の形態の楕円２倍算の演算プログラムにより行うことができる。さらに、アルゴリズム３のループが終了した後、点Ｐ［ｄ］の射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）の計算を、図１０の第１０の実施の形態の射影座標を計算する演算プログラムにより実行することができる。
【０１００】
この場合、アルゴリズム３の各ループでの計算を、１５回の乗算と、５回の平方算と、数回の加算・減算・定数の演算により実現できる。
また、Ｚ＝１の場合に、上記のアルゴリズム３の楕円加算ＥＣＡＤＤを、図５の演算プログラムの替わりに、図６の演算プログラムにより実行することができる。その他の演算は、上記と同じである。
【０１０１】
この場合、アルゴリズム３の各ループでの計算を、１４回の乗算と、５回の平方算と、数回の加算・減算・定数の乗算で実現できる。
次に、本発明の第１４の実施の形態を説明する。この第１４の実施の形態は、第７の実施の形態の射影座標におけるＹ座標を使用しない加算的な楕円加算の演算方法と、第８の実施の形態の射影座標におけるＹ座標を使用しない楕円２倍算の演算方法と、第１０の実施の形態の射影座標におけるＰ［ｄ］の座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を求める演算方法とを用いて、Ｐ［ｄ］＝ｄ×Ｐを計算する。
【０１０２】
この第１４の実施の形態では、楕円曲線Ｅの点Ｐのｘ座標とｙ座標、ｎビットの自然数ｄを入力し、初期値Ｑ［０］＝（ｘ：１）、Ｑ［１］＝（０：１）とし、図２のアルゴリズム３の演算プログラムを用いる。また、点Ｐの射影座標を（Ｘ：Ｙ：Ｚ）とする。
【０１０３】
図２のアルゴリズム３の演算プログラムの楕円加算ＥＣＡＤＤを、第７の実施の形態の射影座標におけるＹ座標を使用しない加算的な楕円加算の演算方法により計算し、楕円２倍算ＥＣＤＢＬを、第８の実施の形態の射影座標におけるＹ座標を使用しない楕円２倍算の演算方法により計算する。その後の演算処理は、上述した第１３の実施の形態のアルゴリズム３のループの終了後の処理と同じである。
【０１０４】
これらの処理により、Ｐ［ｄ］＝（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算することができる。
なお、上記の第１４の実施の形態において、アルゴリズム３の楕円加算ＥＣＡＤＤを、図７（第７の実施の形態）の射影座標のＹ座標を使用しない楕円加算の演算プログラムにより行い、楕円２倍算ＥＣＤＢＬを、図９（第８の実施の形態）の射影座標のＹ座標を使用しない楕円２倍算の演算プログラムにより行うことができる。さらに、アルゴリズム３のループが終了した後、点Ｐ［ｄ］の射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）の計算を、図１０のＰ［ｄ］＝（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算する演算プログラムにより行うことができる。
【０１０５】
この場合、アルゴリズム３の各ループでの計算を、１６回の乗算と、５回の平方算と、数回の加算・減算・定数による演算により実現できる。
また、Ｚ＝１の場合に、上記の図７の演算プログラムの替わりに、図８の演算プログラムを用いることができる。
【０１０６】
この場合、アルゴリズム３の各ループでの計算を、１４回の乗算と、５回の平方算と、数回加算・減算・定数の乗算で実現できる。
図１１は、第１４の実施の形態の楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとで共通する演算をまとめた演算プログラムＥＣＤＤＤＢＬの一例を示す図である。この演算プログラムは、以下の処理からなる。
（１）点Ｐ１の射影座標のＸ座標Ｘ１と、点Ｐ２の射影座標のＸ座標Ｘ２を乗算し、その結果をメモリまたはレジスタ（以下同じ）からなるＴ１に設定する。
（２）点Ｐ１のＺ座標Ｚ１と、点Ｐ２のＺ座標Ｚ２を乗算し、結果をＴ２に設定する。
（３）Ｘ１とＺ２を乗算し、結果をＴ３に設定する。
（４）Ｘ２とＺ１を乗算し、結果をＴ４に設定する。
（５）Ｔ３とＴ４を加算し、結果をＴ５に設定する。
（６）Ｔ２にａを乗算し、結果をＴ６に設定する。
（７）Ｔ１とＴ６を加算し、結果をＴ７に設定する。
（８）Ｔ５とＴ７を乗算し、結果をＴ８に設定する。この処理は、“（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）”の演算に対応する。
（９）Ｔ８に２を乗算し、結果Ｔ９に設定する。
（１０）Ｔ２の２乗を計算し、結果をＴ１０に設定する。この処理は、“Ｚ１＾２×Ｚ２＾２”の演算に対応する。
（１１）Ｔ１０にｂを乗算し、結果をＴ１１に設定する。
（１２）Ｔ１１に４を乗算し、結果をＴ１２に設定する。
（１３）Ｔ９とＴ１２を加算し、結果をＴ１３に設定する。この処理は、２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２）の演算に対応する。
（１４）Ｔ３からＴ４を減算し、結果をＴ１４に設定する。この処理は、Ｘ１×Ｚ２−Ｘ２×Ｚ１に対応する。
（１５）Ｔ１４の２乗を計算し、結果をＴ１５に設定する。この処理は、“（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２”の演算に対応する。
（１６）Ｚ３’とＴ１３を乗算し、結果をＴ１６に設定する。
（１７）Ｘ３’とＴ１５を乗算し、結果をＴ１７に設定する。
（１８）Ｔ１６からＴ１７を減算し、結果をＸ３に設定する。
（１９）Ｚ３’とＴ１５を乗算し、結果をＺ３に設定する。
（２０）Ｔ３の２乗を計算し、結果をＴ２１に設定する。この処理は、“Ｘ１＾２×Ｚ２＾２”の演算に対応する。
（２１）Ｔ６とＴ２を乗算する。この処理は、“ａＺ１＾２×Ｚ２＾２”の演算に対応する。
（２２）Ｔ２１からＴ２２を減算し、結果をＴ２３に設定する。この処理は、“Ｘ１＾２×Ｚ２＾２−ａＺ１＾２×Ｚ２＾２”の演算に対応する。
（２３）Ｔ２３の２乗を計算し、結果をＴ２４に設定する。この処理は、“（Ｘ１＾２×Ｚ２＾２−ａＺ１＾２×Ｚ２＾２）＾２”の演算に対応する。
（２４）Ｔ１１をＴ２５に設定する。
（２５）Ｔ２５にＴ２を乗算し、結果をＴ２６に設定する。この処理は、“ｂＺ１＾３×Ｚ２＾３”の演算に対応する。
（２６）Ｔ２６とＴ３を乗算し、結果をＴ２７に設定する。この処理は、“ｂＸ１×Ｚ１＾３×Ｚ２＾４”に対応する。
（２７）Ｔ２７に８を乗算し、結果をＴ２８に設定する。この処理は、“８ｂＸ１×Ｚ１＾３×Ｚ２＾４”の演算に対応する。
（２８）Ｔ２４からＴ２８を減算し、結果をＸ４に設定する。
（２９）Ｔ２１とＴ２２を加算し、結果をＴ２９に設定する。この処理は、“Ｘ１＾２×Ｚ２＾２＋ａＺ１＾２×Ｚ２＾２”の演算に対応する。
（３０）Ｔ３とＴ２９を乗算し、結果をＴ３０に設定する。この処理は、“Ｘ１×Ｚ２（Ｘ１＾２×Ｚ２＾２＋ａＺ１＾２×Ｚ２＾２）”の演算に対応する。
（３１）Ｔ３０とＴ２６を加算し、結果をＴ３１に設定する。
（３２）Ｔ２とＴ３１を乗算し、結果をＴ３２に設定する。
（３２）Ｔ３２に４を乗算してＺ４を求める。
【０１０７】
上記の演算プログラムにより、Ｐ［ｄ］の射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算することができる。
この場合、アルゴリズム３の各ループでの計算をＧＦ（ｐ＾ｍ）における１４回の乗算と、５回の平方算と、数回の加算・減算・定数の乗算とにより実現できる。
【０１０８】
次に、図１２は、Ｚ３’＝１の場合のＥＣＡＤＤＤＢＬの演算プログラムの一例を示す図である。
この場合、アルゴリズム３の各ループでの計算を、１３回の乗算と、４回の平方算と、数回の加算・減算・定数の乗算とにより実現できる。
【０１０９】
次に、本発明の第１５の実施の形態を説明する。この第１５の実施の形態は、Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線Ｅの点Ｐの座標（ｕ、ｖ），点Ｐ［ｄ］，Ｐ［ｄ＋１］の射影座標におけるＵ座標、Ｗ座標を取得または入力する。Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標値（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）、点Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐの射影座標におけるＵ座標をＵ［ｄ＋１］，Ｗ座標をＷ［ｄ＋１］とする。
【０１１０】
Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線Ｅを、
Ｂ×Ｖ＾２×Ｗ＝Ｕ＾３＋Ａ×Ｕ＾２×Ｗ＋Ｕ×Ｗ＾２
とする。ここで、Ａ，ＢはＧＦ（ｑ＾ｍ）の元、Ｂ（Ａ＾２−４）≠０である。
（１Ａ）・・・Ｕ’［ｄ］＝４Ｂｖ×Ｕ［ｄ＋１］×Ｗ［ｄ＋１］×Ｗ［ｄ］×Ｕ［ｄ］
（２Ａ）・・・Ｖ’［ｄ］＝（ｕ×Ｕ［ｄ］−Ｗ［ｄ］）＾２×Ｗ［ｄ＋１］＾２−（Ｕ［ｄ］−ｕ××Ｗ［ｄ］）＾２×Ｕ［ｄ＋１］＾２  ；（＾：べき乗を表す）
（３Ａ）・・Ｗ’［ｄ］＝４Ｂｖ×Ｕ［ｄ＋１］×Ｗ［ｄ＋１］×Ｗ［ｄ］＾２上記（１Ａ）から（３Ａ）式により、Ｐ［ｄ］＝ｄ×ｐの射影座標における座標（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）を計算する。
【０１１１】
この第１５の実施の形態は、除算を行わずに、Ｐ［ｄ］の射影座標上の座標を計算できるので、演算時間を短縮できる。
図１３は、上記の第１５の実施の形態の（１Ａ）〜（３Ａ）式の演算プログラムの一例を示す図である。この演算プログラムは、以下の処理からなる。
（１）Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線Ｅの点Ｐの座標ｖとＢを乗算し、結果をＴ１に設定する。
（２）Ｔ１とＰ［ｄ］のＷ座標Ｗ［ｄ］を乗算し、結果をＴ２に設定する。
（３）Ｔ２とＰ［ｄ＋１］のＵ座標Ｕ［ｄ＋１］を乗算し、結果をＴ３に設定する。
（４）Ｔ３とＰ［ｄ＋１］のＷ座標Ｗ［ｄ＋１］を乗算し、結果をＴ４に設定する。
（５）Ｔ４とＵ［ｄ］を乗算し、結果をＵ’［ｄ］に設定する。
（６）Ｔ４とＷ［ｄ］を乗算し、結果をＷ’［ｄ］に設定する。
（７）Ｐの座標ｕとＵ［ｄ］を乗算し、結果をＴ５に設定する。
（８）Ｔ５からＷ［ｄ］を減算し、結果をＴ６に設定する。この処理は、“ｕ×Ｕ［ｄ］−Ｗ［ｄ］”の演算に対応する。
（９）Ｔ６とＷ［ｄ＋１］を乗算し、結果をＴ７に設定する。この処理は、“（ｕ×Ｕ［ｄ］−Ｗ［ｄ］）×Ｗ［ｄ＋１］”の演算に対応する。
（１０）ｕとＷ［ｄ］を乗算し、結果をＴ８に設定する。
（１１）Ｕ［ｄ］からＴ８を減算し、結果をＴ９に設定する。この処理は、“Ｕ［ｄ］−ｕ×Ｗ［ｄ］”の演算に対応する。
（１２）Ｔ９とＵ［ｄ＋１］を乗算し、結果をＴ１０に設定する。この処理は、“（Ｕ［ｄ］−ｕ×Ｗ［ｄ］）×Ｕ［ｄ＋１］”の演算に対応する。
（１３）Ｔ７とＴ１０を加算し、結果をＴ１１に設定する。
（１４）Ｔ７からＴ１０を減算し、結果をＴ１２に設定する。
（１５）Ｔ１１とＴ１２を乗算し、Ｖ’［ｄ］を求める。
【０１１２】
上述した演算プログラムにより、Ｐ［ｄ］の射影座標における座標（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）を計算することができる。
この場合、１１回の乗算と、数回の加算・減算・定数の乗算とで計算時することができる。
【０１１３】
ここで、上述した実施の形態の演算プログラムによる演算時間を、図１７のアルゴリズ１による演算時間とを比較する。
ｄのビット数ｎ＝１６０の場合を例にとる。ＧＦ（ｐ＾ｍ）上で乗算に必要な時間をＭ、自乗算に必要な時間をＳ、逆元を計算するのに必要な時間をＩとし、１Ｉ＝３０Ｍ、１Ｓ＝０．８Ｍとする。
【０１１４】
アルゴリズム１（２進展開法）、かつヤコビアン座標におけるスカラー倍算の演算時間は、２２２６．０Ｍとなり、アルゴリズム１（符号付き２進展開法）、かつヤコビアン座標におけるスカラー倍算の演算時間は、１９５０．４Ｍとなる。
【０１１５】
これに対して、本実施の形態では、例えば、アルゴリズム３を使用し、図５の射影座標のＹ座標を使用しない楕円加算の演算プログラムと、図９の射影座標のＹ座標を使用しない楕円２倍算の演算プログラムと、図１０の射影座標における座標値（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算する演算プログラムとを使用した場合のスカラー倍算の計算時間は、１７４２．２Ｍとなる。
【０１１６】
また、アルゴリズム３を使用し、Ｚ＝１の場合に、図６の射影座標のＹ座標を使用しない楕円加算の演算プログラムと、図９の射影座標のＹ座標を使用しない楕円２倍算の演算プログラムと、図１０の射影座標における座標値（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算する演算プログラムとを使用した場合のスカラー倍算の計算時間は、１５８３．２Ｍとなる。
【０１１７】
また、アルゴリズム３を使用し、図７の射影座標のＹ座標を使用しない楕円加算の演算プログラムと、図９の射影座標のＹ座標を使用しない楕円２倍算の演算プログラムと、図１０の射影座標における座標値（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算する演算プログラムとを使用した場合のスカラー倍算の計算時間は、１９０１．２Ｍとなる。
【０１１８】
さらに、アルゴリズム３を使用し、Ｚ＝１の場合に、図８の射影座標のＹ座標を使用しない楕円加算の演算プログラムと、図９の射影座標のＹ座標を使用しない楕円２倍算の演算プログラムと、図１０の射影座標における座標値（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を計算する演算プログラムとを使用した場合のスカラー倍算の計算時間は、１５８３．２Ｍとなる。
【０１１９】
上記のようにスカラー倍算の演算時間を大幅に短縮することができる。
図１４は、本実施形態のスカラー倍算の演算プログラムを実行する情報処理装置２０のハードウェア環境の一例を示す図である。
【０１２０】
バス２１で。２個のＣＰＵ２２，２３と接続されたＲＯＭ２４には、ＢＩＯＳなどの基本プログラムが格納される。また、当該プログラムは、バス２１でＣＰＵ２２，２３と接続された、ハードディスクなどの記憶装置２５に格納され、ＲＡＭ２６にコピーされて、ＣＰＵ２２，２３によって実行される。記録媒体読み取り装置２７は、フレキシブルディスク、ＣＤ−ＲＯＭ、ＤＶＤなどの可搬記録媒体２８から当該プログラムを読み取り、情報処理装置２０にインストールを可能とするものである。あるいは、可搬記録媒体２８から当該プログラムを直接読み込んで、ＣＰＵ２２，２３に実行させても良い。
【０１２１】
入出力装置２９は、キーボード、マウス、テンプレート、ディスプレイなどからなり、情報処理装置２０のユーザからの命令をＣＰＵ２２，２３に伝えたり、ＣＰＵ２２，２３の演算結果をユーザに提示するためのものである。
【０１２２】
通信インターフェース３０は、情報処理装置２０をネットワーク３１を介して情報提供者３２に接続するものである。情報提供者３２は、当該プログラムをサーバ装置等に保持し、これをネットワーク３１経由で情報処理装置２０にダウンロードすることも可能である。
【０１２３】
ｄとＰからｄ×Ｐを求めることは容易だが、ｄ×ＰとＰからｄを求めることは困難である。暗号で言えば、ｄは秘密キーｓまたはｔに対応し、Ｐは秘密キーに掛け算してｄ×Ｐの公開キーを作るのだから、公開キーｄ×Ｐから秘密キーｓまたはｔに対応するdを求めることは困難となる。
【０１２４】
上述した実施の形態に依れば、アルゴリズム２及び３において、ｄ［ｉ］に依らず、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬの計算を行うことができるのでサイドチャネルアタックに対する耐性を持つことができる。
【０１２５】
本発明は、上述した自然数ｄを二進展開する場合に限らず、楕円加算と、楕円２倍算とを並列に計算できるスカラー倍算の演算方法であれば、どのようなものにも適用できる。
【０１２６】
楕円曲線もＷｉｅｒｓｔｒａｓｓ型、Ｍｏｎｔｇｏｍｅｒｙ型に限らず、他の楕円曲線にも適用できる。
（付記１）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を０とし、前記取得手段により取得した自然数ｄの２進展開の係数をｄ［ｉ］（ｉ＝０〜ｎ−１、ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（２）Ｑ［０］＝ＥＣＤＢＬ（Ｑ［０］）
（３）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得した点Ｐの座標及び自然数ｄに基づいて、上記（１）から（３）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１２７】
（付記２）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐとし、前記取得手段により取得した自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｎ−１］〜ｄ［０］、ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得した点Ｐの座標と自然数ｄとに基づいて、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１２８】
（付記３）付記２記載の楕円曲線暗号装置において、
前記演算手段は、Ｑ［０］を記憶する第１のレジスタと、Ｑ［１］を記憶する第２のレジスタとを有し、
Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記楕円加算ＥＣＡＤＤ及び楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第１のレジスタに格納する楕円曲線暗号装置。
【０１２９】
（付記４）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得する取得手段と、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４ｂ（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３０】
（付記５）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得する取得手段と、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、以下の式
ｘ３＝［２（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３１】
（付記６）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１を取得する取得手段と、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、以下の式
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｂ×ｘ１］／［４（ｘ１＾３＋ａ×ｘ１＋ｂ）］
によりｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３２】
（付記７）有限体上の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得する取得手段と、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１のとき
（１）・・・Ｘ３＝Ｚ３’×［（Ｘ１×Ｘ２−ａＺ１×Ｚ２）＾２−４ｂＺ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）］
（２）・・・Ｚ３＝Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１）と（２）式により楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算する演算手段とを備える楕円曲線暗号装置。
【０１３３】
（付記８）付記７の楕円曲線暗号装置において、
前記演算手段が、以下の演算を実行して楕円加算Ｐ３＝Ｐ１＋Ｐ２の射影座標におけるＸ座標を求める
（１）Ｔ１←Ｘ１×Ｘ２
（２）Ｔ２←Ｚ１×Ｚ２
（３）Ｔ３←Ｘ１×Ｚ２
（４）Ｔ４←Ｘ２×Ｚ１
（５）Ｔ５←aＴ２（＝ａＺ１×Ｚ２）
（６）Ｔ６←Ｔ１−Ｔ５（＝Ｘ１×Ｘ２−ａＺ１×Ｚ２）
（７）Ｔ７←Ｔ６＾２（＝(Ｘ１×Ｘ２−ａＺ１×Ｚ２)＾２）
（８）Ｔ８←ｂ×Ｔ２（＝ｂＺ１×Ｚ２）
（９）Ｔ９←４Ｔ８（＝４ｂＺ１×Ｚ２）
（１０）Ｔ１０← Ｔ３＋Ｔ４（＝Ｘ１×Ｚ２＋Ｘ２×Ｚ１）
（１１）Ｔ１１←Ｔ９×Ｔ１０（＝４ｂＺ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１））
（１２）Ｔ１２←Ｔ７−Ｔ１１（＝(Ｘ１×Ｘ２−ａＺ１×Ｚ２)＾２−４×ｂ×Ｚ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１））
（１３）Ｘ３←Ｚ３’×Ｔ１２
（１４）Ｔ１３←Ｔ３−Ｔ４（＝Ｘ１×Ｚ２−Ｘ２×Ｚ１）
（１５）Ｔ１４←Ｔ１３＾２（＝（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２）
（１６）Ｚ３←Ｘ３’×Ｔ１４
（付記９）付記７記載の楕円曲線暗号装置において、
前記演算手段は、Ｚ３’＝１のときに、以下の演算を実行して楕円加算Ｐ３＝Ｐ２＋Ｐ１の射影座標におけるＸ座標とＺ座標を求める
（１）Ｔ１←Ｘ１×Ｘ２
（２）Ｔ２←Ｚ１×Ｚ２
（３）Ｔ３←Ｘ１×Ｚ２
（４）Ｔ４←Ｘ２×Ｚ１
（５）Ｔ５←ａ×Ｔ２(＝ａ×Ｚ１×Ｚ２)
（６）Ｔ６←Ｔ１−Ｔ５(＝Ｘ１×Ｘ２−ａＺ１×Ｚ２)
（７）Ｔ７←Ｔ６＾２(＝（Ｘ１×Ｘ２−ａＺ１×Ｚ２）＾２)
（８）Ｔ８←ｂＴ２(＝ｂＺ１×Ｚ２)
（９）Ｔ９←４Ｔ８(＝４ｂＺ１×Ｚ２)
（１０）Ｔ１０←Ｔ３＋Ｔ４（＝Ｘ１×Ｚ２＋Ｘ２×Ｚ１）
（１１）Ｔ１１←Ｔ９×Ｔ１０(＝４ｂＺ１×Ｚ２(Ｘ１×Ｚ２＋Ｘ２×Ｚ１))
（１２）Ｘ３←Ｔ７−Ｔ１１(＝Ｘ１×Ｘ２−ａＺ１×Ｚ２)＾２−４ｂＺ１×Ｚ２(Ｘ１×Ｚ２＋Ｘ２×Ｚ１))
（１３）Ｔ１３←Ｔ３−Ｔ４(＝Ｘ１×Ｚ２−Ｘ２×Ｚ１)
（１４）Ｔ１４←Ｔ１３＾２（＝Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２）
（１５）Ｚ３−Ｘ３’×Ｔ１４
（付記１０）有限体上の楕円曲線の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得する取得手段と、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１のとき
（１）・・・Ｘ３’＝Ｚ３×［２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２］−Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
（２）・・・Ｚ３＝Ｚ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１）と（２）式により、射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに計算する演算手段とを備える楕円曲線暗号装置。
【０１３４】
（付記１１）付記１０記載の楕円曲線暗号装置において、
前記演算手段は、以下の演算を実行して、射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに演算する
（１）Ｔ１←Ｘ１×Ｘ２
（２）Ｔ２←Ｚ１×Ｚ２
（３）Ｔ３←Ｘ１×Ｚ２
（４）Ｔ４←Ｘ２×Ｚ１
（５）Ｔ５←Ｔ３＋Ｔ４（＝Ｘ１×Ｚ２＋Ｘ２×Ｚ１）
（６）Ｔ６←ａ×Ｔ２（＝ａＺ１×Ｚ２）
（７）Ｔ７←Ｔ１＋Ｔ６（＝Ｘ１×Ｘ２＋ａＺ１×Ｚ２）
（８）Ｔ８←Ｔ５×Ｔ７（＝(Ｘ１×Ｚ２＋Ｘ２×Ｚ１)(Ｘ１×Ｘ２＋ａＺ１×Ｚ２)）
（９）Ｔ９←２×Ｔ８（＝２(Ｘ１×Ｚ２＋Ｘ２×Ｚ１)(Ｘ１×Ｘ２＋ａＺ１×Ｚ２)）
（１０）Ｔ１０←Ｔ２＾２（＝Ｚ１＾２×Ｚ２＾２）
（１１）Ｔ１１←ｂ×Ｔ１０（＝ｂＺ１＾２×Ｚ２＾２）
（１２）Ｔ１２←４・Ｔ１１（＝４ｂＺ１＾２×Ｚ２＾２）
（１４）Ｔ１３←Ｔ９＋Ｔ１２（＝２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２）
（１５）Ｔ１４←Ｔ３−Ｔ４（＝Ｘ１×Ｚ２−Ｘ２×Ｚ１）
（１６）Ｔ１５←Ｔ１４＾２（＝（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２）
（１７）Ｔ１６←Ｚ３’×Ｔ１３
（１８）Ｔ１７←Ｘ３’×Ｔ１５
（１９）Ｘ３←Ｔ１６−Ｔ１７
（２０）Ｚ３←Ｚ３’×Ｔ１５
（付記１２）付記１０の楕円曲線暗号装置において、
Ｚ３’＝１の場合に、前記演算手段は、以下の演算を実行して、射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに演算する
（１）Ｔ１←Ｘ１×Ｘ２
（２）Ｔ２←Ｚ１×Ｚ２
（３）Ｔ３←Ｘ１×Ｚ２
（４）Ｔ４←Ｘ２×Ｚ１
（５）Ｔ５←Ｔ３＋Ｔ４（＝Ｘ１×Ｚ２＋Ｘ２×Ｚ１）
（６）Ｔ６←ａ×Ｔ２（＝ａＺ１×Ｚ２）
（７）Ｔ７←Ｔ１＋Ｔ６（＝Ｘ１×Ｘ２＋ａＺ１×Ｚ２）
（８）Ｔ８←Ｔ５×Ｔ７（＝（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２））
（９）Ｔ９←２・Ｔ８（＝２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２））
（１０）Ｔ１０←Ｔ２＾２（＝Ｚ１＾２×Ｚ２＾２）
（１１）Ｔ１１←ｂ×Ｔ１０（＝ｂＺ１＾２×Ｚ２＾２）
（１２）Ｔ１２←４・Ｔ１１（＝４ｂＺ１＾２×Ｚ２＾２）
（１３）Ｔ１３←Ｔ９＋Ｔ１２（＝２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２）
（１４）Ｔ１４←Ｔ３−Ｔ４（＝Ｘ１×Ｚ２−Ｘ２×Ｚ１）
（１５）Ｔ１５←Ｔ１４＾２  （＝（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２）
（１６）Ｔ１６←Ｔ１３
（１７）Ｔ１７←Ｔ１５
（１８）Ｘ３←Ｔ１６−Ｔ１７
（１９）Ｚ３←Ｚ３’×Ｔ１５
（付記１３）有限体上の楕円曲線の点Ｐ１の座標を取得する取得手段と、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、射影座標におけるＰ１のＸ座標をＸ１，Ｚ座標をＺ１とし、Ｚ１≠０の場合に、
（１）・・・Ｘ４＝［（Ｘ１＾２−ａＺ１＾２）＾２−８ｂＸ１×Ｚ１＾３］；（＾：べき乗を表す）
（２）・・・Ｚ４＝［４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）］
前記取得手段により取得した点Ｐの座標と、上記（１）と（２）式から射影座標における楕円２倍算Ｐ４＝２×Ｐ１のＸ座標とＺ座標を、Ｙ座標を用いずに演算する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３５】
（付記１４）付記１３記載の楕円曲線暗号装置において、
前記演算手段は、以下の演算を実行して、楕円２倍算Ｐ４＝２×Ｐ１の射影座標におけるＸ座標とＺ座標を演算する
（１）Ｔ１←Ｘ１＾２
（２）Ｔ２←Ｚ１＾２
（３）Ｔ３←ａ×Ｔ２（＝ａＺ１＾２）
（４）Ｔ４←Ｔ１−Ｔ３（＝Ｘ１＾２−ａＺ１＾２）
（５）Ｔ５←Ｔ４＾２（＝（Ｘ１＾２−ａＺ１＾２）＾２）
（６）Ｔ６←ｂ×Ｔ２（＝ｂＺ１＾２）
（７）Ｔ７←Ｘ１×Ｚ１（＝Ｘ１×Ｚ１）
（８）Ｔ８←Ｔ６×Ｔ７（＝ｂＸ１×Ｚ１＾３）
（９）Ｔ９←８Ｔ８（＝８ｂＸ１×Ｚ１＾３）
（１０）Ｘ４←Ｔ５−Ｔ９
（１１）Ｔ１０←Ｔ１＋Ｔ３（＝Ｘ１＾２＋ａＺ１＾２）
（１２）Ｔ１１←Ｔ７×Ｔ１０（＝Ｘ１×Ｚ１（Ｘ１＾２＋ａＺ１＾２））
（１３）Ｔ１２←Ｔ６×Ｔ２（＝ｂＺ１＾４）
（１４）Ｔ１３←Ｔ１１＋Ｔ１２（＝Ｘ１×Ｚ１×（Ｘ１＾２＋ａＺ１＾２）＋ｂＺ１＾４））
（１５）Ｚ４←４Ｔ１３
（付記１５）有限体上の楕円曲線の点Ｐのｘ座標とｙ座標，点Ｐ［ｄ］，Ｐ［ｄ＋１］のｘ座標を取得する取得手段と、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、楕円曲線の点Ｐの座標（ｘ，ｙ）、点Ｐ［ｄ］＝ｄ×Ｐのｘ座標をｘ［ｄ］、Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐのｘ座標をｘ［ｄ＋１］としたときに、
ｙ［ｄ］＝［ｙ＾２＋ｘ［ｄ］＾３＋ａｘ［ｄ］＋ｂ−（ｘ−ｘ［ｄ］）＾２×（ｘ＋ｘ［ｄ］＋ｘ［ｄ＋１］）］／［２×ｙ］  ；（＾：べき乗を表す）
前記取得手段により取得した座標データと、上記の式により、Ｐ［ｄ］＝ｄ×Ｐのｙ座標を求める演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３６】
（付記１６）有限体上の楕円曲線の点Ｐのｘ座標とｙ座標，点Ｐ［ｄ］の射影座標におけるＸ座標Ｘ［ｄ］とＺ座標Ｚ［ｄ］，Ｐ［ｄ＋１］＝（ｄ＋１）Ｐの射影座標におけるＸ座標Ｘ［ｄ＋１］とＺ座標Ｚ［ｄ＋１］とを取得する取得手段と、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、
（１）・・・Ｘ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］
（２）・・・Ｙ’［ｄ］＝Ｚ［ｄ＋１］×（ｙ＾２×Ｚ［ｄ］＾３＋Ｘ［ｄ］＾３＋ａＸ［ｄ］×Ｚ［ｄ］＾２＋ｂＺ［ｄ］＾３）−（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２×（ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ＋１］×Ｚ［ｄ］）
（３）・・・Ｚ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］
前記取得手段により取得した座標データに基づいて、上記の（１）から（３）式により点Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３７】
（付記１７）付記１６記載の楕円曲線暗号装置において、
前記演算手段は、以下の演算を実行する
（１）Ｔ１←Ｚ［ｄ］＾２
（２）Ｔ２←Ｔ１×Ｚ［ｄ＋１］（＝Ｚ［ｄ］＾２×Ｚ［ｄ＋１］）
（３）Ｔ３←ｙ×Ｔ２（＝ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］）
（４）Ｔ４←Ｘ［ｄ］×Ｔ３（＝ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］）
（５）Ｘ’［ｄ］←２・Ｔ４
（６）Ｔ５←Ｚ［ｄ］×Ｔ３（＝ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］）
（７）Ｚ’［ｄ］←２・Ｔ５
（８）Ｔ６←Ｘ［ｄ］＾２
（９）Ｔ７←ａ×Ｔ１（＝ａＺ［ｄ］＾２）
（１０）Ｔ８←Ｔ６＋Ｔ７（＝Ｘ［ｄ］＾２＋ａＺ［ｄ］＾２）
（１１）Ｔ９←Ｘ［ｄ］×Ｚ［ｄ＋１］
（１２）Ｔ１０←Ｔ９×Ｔ８（＝Ｘ［ｄ］×Ｚ［ｄ＋１］×（Ｘ［ｄ］＾２＋ａＺ［ｄ］＾２））
（１３）Ｔ１１←ｙ×Ｔ５（＝ｙ＾２×Ｚ［ｄ］＾３×Ｚ［ｄ＋１］）
（１４）Ｔ１２←ｂ×Ｚ［ｄ］
（１５）Ｔ１３←Ｔ１２×Ｔ２（＝ｂＺ［ｄ］＾３×Ｚ［ｄ＋１］）
（１６）Ｔ１４←ｘ×Ｚ［ｄ］
（１７）Ｔ１５←Ｔ１４−Ｘ［ｄ］（＝ｘ×Ｚ［ｄ］−Ｘ［ｄ］）
（１８）Ｔ１６←Ｔ１５＾２（＝（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２）
（１９）Ｔ１７←Ｔ１４×Ｚ［ｄ＋１］（＝ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］）
（２０）Ｔ１８←Ｘ［ｄ＋１］×Ｚ［ｄ］
（２１）Ｔ１９←Ｔ１７＋Ｔ９＋Ｔ１８
（２２）Ｔ２０←Ｔ１６×Ｔ１９
（２３）Ｙ’［ｄ］←Ｔ１０＋Ｔ１１＋Ｔ１３−Ｔ２０
（付記１８）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐ２のｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得する取得手段と、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式
（１）・・・ｘ３＝［（ｘ１×ｘ２−ａ）＾２
−４ｂ（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
上記の（１）式により、ｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出し、
（２）・・・ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｘ１］／［４（ｘ１＾３＋ａ×ｘ１＋ｂ）］
前記取得手段により取得した座標データに基づいて、上記の（２）式により、ｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を算出し、
楕円曲線の点Ｐの座標（ｘ，ｙ）、点Ｐ［ｄ］＝ｄ×Ｐのｘ座標をｘ［ｄ］、Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐのｘ座標をｘ［ｄ＋１］としたときに、
（３）ｙ［ｄ］＝［ｙ＾２＋ｘ［ｄ］＾３＋ａｘ［ｄ］＋ｂ−（ｘ−ｘ［ｄ］）＾２×（ｘ＋ｘ［ｄ］＋ｘ［ｄ＋１］）］／［２×ｙ］
上記の式により、Ｐ［ｄ］＝ｄ×Ｐのｙ座標を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１３８】
（付記１９）付記１８記載の楕円曲線暗号装置において、
前記演算手段は、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する。
【０１３９】
（付記２０）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐのｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２、点Ｐ［ｄ］，Ｐ［ｄ＋１］のｘ座標を取得する取得手段と、変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得したデータに基づいて、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤの演算を、以下の（５）式により実行し、
（５）・・・ｘ３＝［２（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
ｄ×Ｐを求めるための楕円２倍算ＥＣＤＢＬの演算を、以下の（６）式により実行し、
（６）・・・ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｘ１］／［４（ｘ１＾３＋ａ×ｘ１＋ｂ）］
ｘ［ｄ］＝Ｑ［０］、ｘ［ｄ＋１］＝Ｑ［１］としたときに、
（７）・・・ｙ［ｄ］＝［ｙ＾２＋ｘ［ｄ］＾３＋ａｘ［ｄ］＋ｂ−（ｘ−ｘ［ｄ］）＾２×（ｘ＋ｘ［ｄ］＋ｘ［ｄ＋１］）］／［２×ｙ］  ；（＾：べき乗を表す）
上記の（７）式により、Ｐ［ｄ］＝ｄ×Ｐのｙ座標を求める演算を実行する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１４０】
（付記２１）付記２０記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号装置。
【０１４１】
（付記２２）有限体上の楕円曲線の点Ｐ１のｘ座標，Ｐ２のｘ座標、ｎビットの自然数ｄを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得したデータに基づいて、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、
射影座標における、点Ｐ１のＸ座標をＸ１，Ｚ座標をＺ１、点Ｐ２のＸ座標をＸ２，Ｚ座標をＺ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標をＸ３’，Ｚ座標をＺ３’とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合に、
（５）・・・Ｘ３＝Ｚ３’×［（Ｘ１×Ｘ２−ａＺ１×Ｚ２）＾２−４ｂＺ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）］  ；（＾：べき乗を表す）
（６）・・・Ｚ３＝Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（５）と（６）式により楕円加算ＥＣＡＤＤＰ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算し、
（７）・・・Ｘ４＝［（Ｘ１＾２−ａＺ１＾２）＾２−８ｂＸ１×Ｚ１＾３］
（８）・・・Ｚ４＝［４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）］
上記（７）と（８）式により、射影座標における楕円２倍算Ｐ４＝２×Ｐ１のＸ座標とＺ座標を算出し、
Ｘ［ｄ］＝Ｑ［０］のｘ成分，Ｚ［ｄ］＝Ｑ［０］のｙ成分，Ｘ［ｄ＋１］＝Ｑ［１］のｘ成分，Ｚ［ｄ＋１］＝Ｑ［１］のｙ成分とおき、
（９）・・・Ｘ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］
（１０）・・・Ｙ’［ｄ］＝Ｚ［ｄ＋１］×（ｙ＾２×Ｚ［ｄ］＾３＋Ｘ［ｄ］＾３＋ａＸ［ｄ］×Ｚ［ｄ］＾２＋ｂＺ［ｄ］＾３）−（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２×（ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ＋１］×Ｚ［ｄ］）
（１１）・・・Ｚ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］
上記の（９）から（１１）式により点Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を算出する演算手段とを備えることを特徴とする楕円曲線暗号装置。
【０１４２】
（付記２３）付記２２記載の楕円曲線暗号装置において、
前記演算手段は、
付記８記載の楕円加算Ｐ３＝Ｐ１＋Ｐ１の演算と、
付記１４記載の楕円２倍算Ｐ４＝２×Ｐの演算と、
付記１７記載の射影座標におけるＰ［ｄ］の座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を求める演算とを実行する楕円曲線暗号装置。
【０１４３】
（付記２４）付記２２記載の楕円曲線暗号装置において、
Ｚ＝１の場合に、
付記９記載の楕円加算Ｐ３＝Ｐ１＋Ｐ１の演算と、
付記１４記載の楕円２倍算Ｐ４＝２×Ｐの演算と、
付記１７記載の射影座標におけるＰ［ｄ］の座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）を求める演算とを実行する楕円曲線暗号装置。
【０１４４】
（付記２５）付記２２記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記演算手段は、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行することを特徴とする楕円曲線暗号装置。
【０１４５】
（付記２６）付記２３記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記演算手段は、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行することを特徴とする楕円曲線暗号装置。
【０１４６】
（付記２７）付記２４記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記演算手段は、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行することを特徴とする楕円曲線暗号装置。
【０１４７】
（付記２８）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
前記取得手段により取得したデータに基づいて、上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円曲線の射影座標における、点Ｐ１のＸ座標をＸ１，Ｚ座標をＺ１、点Ｐ２のＸ座標をＸ２，Ｚ座標をＺ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標をＸ３’，Ｚ座標をＺ３’とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合に
（１）・・・Ｘ３＝Ｚ３’×［２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）×（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２］−Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
（２）・・・Ｚ３＝Ｚ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１）と（２）式により、射影座標における楕円加算Ｐ３＝Ｐ１＋Ｐ２のＸ座標Ｘ３とＺ座標Ｚ３を、Ｙ座標を用いずに演算し、
射影座標におけるＰ１のＸ座標をＸ１，Ｚ座標をＺ１とし、Ｚ１≠０の場合に、
（３）・・・Ｘ４＝［（Ｘ１＾２−ａＺ１＾２）＾２−８ｂＸ１×Ｚ１＾３］；（＾：べき乗を表す）
（４）・・・Ｚ４＝［４×（Ｘ１×Ｚ１×（Ｘ１＾２＋ａ×Ｚ１＾２）＋ｂ×Ｚ１＾４）］
上記の（３）と（４）式により射影座標における楕円２倍算Ｐ４＝２×Ｐ１のＸ座標とＺ座標を、Ｙ座標を用いずに演算し、
点Ｐ［ｄ］の射影座標におけるＸ座標Ｘ［ｄ］とＺ座標Ｚ［ｄ］，Ｐ［ｄ＋１］＝（ｄ＋１）Ｐの射影座標におけるＸ座標Ｘ［ｄ＋１］とＺ座標Ｚ［ｄ＋１］としたときに、
（５）・・・Ｘ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｘ［ｄ］
（６）・・・Ｙ’［ｄ］＝Ｚ［ｄ＋１］×（ｙ＾２×Ｚ［ｄ］＾３＋Ｘ［ｄ］＾３＋ａＸ［ｄ］×Ｚ［ｄ］＾２＋ｂＺ［ｄ］＾３）−（ｘ×Ｚ［ｄ］−Ｘ［ｄ］）＾２（ｘ×Ｚ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ］×Ｚ［ｄ＋１］＋Ｘ［ｄ＋１］×Ｚ［ｄ］）
（７）・・・Ｚ’［ｄ］＝２ｙ×Ｚ［ｄ］＾２×Ｚ［ｄ＋１］×Ｚ［ｄ］
上記の（５）から（７）式により点Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標（Ｘ’［ｄ］：Ｙ’［ｄ］：Ｚ’［ｄ］）とを演算する演算手段とを備える楕円曲線暗号装置。
【０１４８】
（付記２９）付記２８記載の楕円曲線暗号装置において、
前記演算手段は、
付記１１記載の楕円加算の演算と、
付記１４記載の楕円２倍算の演算と、
付記１７記載の射影座標Ｐ［ｄ］の座標の演算とを実行する楕円曲線暗号装置。
【０１４９】
（付記３０）付記２８記載の楕円曲線暗号装置において、
前記演算手段は、Ｚ＝１である場合に、
付記１４記載の楕円加算の演算と、
付記１７記載の楕円２倍算の演算とを実行する楕円曲線暗号装置。
【０１５０】
（付記３１）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得する取得手段と、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）ｄ［ｉ］＝１ならば、ｓｗａｐ（Ｑ［０］，Ｑ［１］）
（２）ＥＣＡＤＤＤＢＬ（Ｑ［０］，Ｑ［１］）
（ただしＱ［０］＝（Ｘ１：Ｚ１），Ｑ［１］＝（Ｘ２：Ｚ２）とする。）
（３）Ｑ［１］＝（Ｘ３：Ｚ３）
（４）Ｑ［２］＝（Ｘ４：Ｚ４）
（５）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（６）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記の演算を所定数回実行する際に、ＥＣＡＤＤＤＢＬを、以下の式により計算する
（１）Ｔ１←Ｘ１×Ｘ２
（２）Ｔ２←Ｚ１×Ｚ２
（３）Ｔ３←Ｘ１×Ｚ２
（４）Ｔ４←Ｘ２×Ｚ１
（５）Ｔ５←Ｔ３＋Ｔ４（＝Ｘ１×Ｚ２＋Ｘ２×Ｚ１）
（６）Ｔ６←ａ×Ｔ２（＝ａＺ１×Ｚ２）
（７）Ｔ７←Ｔ１＋Ｔ６（＝Ｘ１×Ｘ２＋ａＺ１×Ｚ２）
（８）Ｔ８←Ｔ５×Ｔ７（＝（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２））
（９）Ｔ９←２Ｔ８（＝２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２））
（１０）Ｔ１０←Ｔ２＾２（＝Ｚ１＾２×Ｚ２＾２）
（１１）Ｔ１１←ｂ×Ｔ１０（＝ｂＺ１＾２×Ｚ２＾２）
（１２）Ｔ１２←４Ｔ１１（＝４ｂＺ１＾２×Ｚ２＾２）
（１３）Ｔ１３←Ｔ９＋Ｔ１２（＝２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）（Ｘ１×Ｘ２＋ａＺ１×Ｚ２）＋４ｂＺ１＾２×Ｚ２＾２）
（１４）Ｔ１４←Ｔ３−Ｔ４（＝Ｘ１×Ｚ２−Ｘ２×Ｚ１）
（１５）Ｔ１５←Ｔ１４＾２（＝（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２）
（１６）Ｔ１６←Ｚ３’×Ｔ１３
（１７）Ｔ１７←Ｘ３’×Ｔ１５
（１８）Ｘ３←Ｔ１６−Ｔ１７
（１９）Ｚ３←Ｚ３’×Ｔ１５
（２０）Ｔ２１←Ｔ３＾２（＝Ｘ１＾２×Ｚ２＾２）
（２１）Ｔ２２←Ｔ６×Ｔ２（＝ａＺ１＾２×Ｚ２＾２）
（２２）Ｔ２３←Ｔ２１−Ｔ２２（＝Ｘ１＾２×Ｚ２＾２−ａＺ１＾２×Ｚ２＾２）
（２３）Ｔ２４←Ｔ２３＾２（＝（Ｘ１＾２×Ｚ２＾２−ａＺ１＾２×Ｚ２＾２）＾２）
（２４）Ｔ２５←Ｔ１１
（２５）Ｔ２６←Ｔ２５×Ｔ２（＝ｂＺ１＾３×Ｚ２＾３）
（２６）Ｔ２７←Ｔ２６×Ｔ３（＝ｂＸ１×Ｚ１＾３×Ｚ２＾４）
（２７）Ｔ２８←８・Ｔ２７（＝８ｂＸ１×Ｚ１＾３×Ｚ２＾４）
（２８）Ｘ４←Ｔ２４−Ｔ２８
（２９）Ｔ２９←Ｔ２１＋Ｔ２２（＝Ｘ１＾２×Ｚ２＾２＋ａＺ１＾２×Ｚ２＾２）
（３０）Ｔ３０←Ｔ３×Ｔ２９（＝Ｘ１×Ｚ２（Ｘ１＾２×Ｚ２＾２＋ａＺ１＾２×Ｚ２＾２））
（３１）Ｔ３１←Ｔ３０＋Ｔ２６
（３２）Ｔ３２←Ｔ２×Ｔ３１
（３３）Ｚ４←４Ｔ３２
（付記３２）付記３１記載の楕円曲線暗号装置において、
Ｚ３’＝１である場合に、前記演算手段は、Ｚ３‘＝１として前記ＥＣＡＤＤＤＢＬの演算を実行する楕円曲線暗号装置。
【０１５１】
（付記３３）付記２８記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める楕円曲線暗号装置。
【０１５２】
（付記３４）付記２９記載の楕円曲線暗号装置において、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める楕円曲線暗号装置。
【０１５３】
（付記３５）付記３０記載の楕円曲線暗号装置において
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める楕円曲線暗号装置
（付記３６）Ｍｏｎｔｇｏｍｅｒｙ型楕円曲線Ｅの点Ｐのｕ座標とｖ座標，点Ｐ［ｄ］，Ｐ［ｄ＋１］の射影座標におけるＵ座標・Ｗ座標を取得する取得手段と、
楕円曲線Ｅ：Ｂ×Ｖ＾２×Ｗ＝Ｕ＾３＋Ａ×Ｕ＾２×Ｗ＋Ｕ×Ｗ＾２、
とし、Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標値（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）、点Ｐ［ｄ＋１］＝（ｄ＋１）×Ｐの射影座標におけるＵ座標をＵ［ｄ＋１］，Ｗ座標をＷ［ｄ＋１］としたときに、
（１）・・・Ｕ’［ｄ］＝４Ｂｖ×Ｕ［ｄ＋１］×Ｗ［ｄ＋１］×Ｗ［ｄ］×Ｕ［ｄ］
（２）・・・Ｖ’［ｄ］＝（ｕ×Ｕ［ｄ］−Ｗ［ｄ］）＾２×Ｗ［ｄ＋１］＾２−（Ｕ［ｄ］−ｕ××Ｗ［ｄ］）＾２×Ｕ［ｄ＋１］＾２  ；（＾：べき乗を表す）
（３）・・・Ｗ’［ｄ］＝４Ｂｖ×Ｕ［ｄ＋１］×Ｗ［ｄ＋１］×Ｗ［ｄ］＾２上記（１）から（３）式の演算を実行し、Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）を計算する演算手段とを備える楕円曲線暗号装置。
【０１５４】
（付記３７）付記３６記載の楕円曲線暗号装置において、
（１）Ｔ１←Ｂ×ｖ
（２）Ｔ２←Ｔ１×Ｗ［ｄ］
（３）Ｔ３←Ｔ２×Ｕ［ｄ＋１］
（４）Ｔ４←Ｔ３×Ｗ［ｄ＋１］
（５）Ｕ’［ｄ］←Ｔ４×Ｕ［ｄ］
（６）Ｗ’［ｄ］←Ｔ４×Ｗ［ｄ］
（７）Ｔ５←ｕ×Ｕ［ｄ］
（８）Ｔ６←Ｔ５−Ｗ［ｄ］（＝ｕ×Ｕ［ｄ］−Ｗ［ｄ］）
（９）Ｔ７←Ｔ６×Ｗ［ｄ＋１］（＝（ｕ×Ｕ［ｄ］−Ｗ［ｄ］）×Ｗ［ｄ＋１］）
（１０）Ｔ８←ｕ×Ｗ［ｄ］
（１１）Ｔ９←Ｕ［ｄ］−Ｔ８（＝Ｕ［ｄ］−ｕ×Ｗ［ｄ］）
（１２）Ｔ１０←Ｔ９×Ｕ［ｄ＋１］（＝（Ｕ［ｄ］−ｕ×Ｗ［ｄ］）×Ｕ［ｄ＋１］）
（１３）Ｔ１１←Ｔ７＋Ｔ１０
（１４）Ｔ１２←Ｔ７−Ｔ１０
（１５）Ｗ’［ｄ］←Ｔ１１×Ｔ１２
前記演算手段は、上記の（１）から（１５）の処理を実行して、Ｐ［ｄ］＝ｄ×Ｐの射影座標における座標（Ｕ’［ｄ］：Ｖ’［ｄ］：Ｗ’［ｄ］）を算出することを特徴とする楕円曲線暗号装置。
【０１５５】
（付記３８）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得し、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を０、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（２）Ｑ［０］＝ＥＣＤＢＬ（Ｑ［０］）
（３）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（３）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号プログラム。
【０１５６】
（付記３９）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得し、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号プログラム。
【０１５７】
（付記４０）付記３９記載の楕円曲線暗号プログラムにおいて、
Ｑ［０］を記憶する第１のレジスタと、Ｑ［１］を記憶する第２のレジスタとを有し、
Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記楕円加算ＥＣＡＤＤ及び楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第１のレジスタに格納する楕円曲線暗号プログラム。
【０１５８】
（付記４１）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐのｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式
ｘ３＝［（ｘ１×ｘ２−ａ）＾２
−４ｂ（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する楕円曲線暗号プログラム。
【０１５９】
（付記４２）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐのｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、
ｘ３＝［２（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
上記の式によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する楕円曲線暗号プログラム。
【０１６０】
（付記４３）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｘ１］／［４（ｘ１＾３＋ａ×ｘ１＋ｂ）］
上記の式によりｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を演算する楕円曲線暗号プログラム。
【０１６１】
（付記４４）有限体上の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得し、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合に、
（１）・・・Ｘ３＝Ｚ３’×［（Ｘ１×Ｘ２−ａＺ１×Ｚ２）＾２−４ｂＺ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）］
（２）・・・Ｚ３＝Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１）と（２）式により楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を計算する楕円曲線暗号プログラム。
【０１６２】
（付記４５）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得し、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を０、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（２）Ｑ［０］＝ＥＣＤＢＬ（Ｑ［０］）
（３）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（３）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号の演算方法。
【０１６３】
（付記４６）有限体上の楕円曲線の点Ｐの座標とｎビットの自然数ｄとを取得し、
変数Ｑ［０］の初期値をＰ、変数Ｑ［１］の初期値を２×Ｐ、自然数ｄの２進展開の係数をｄ［ｉ］（ｄ［ｉ］＝０，１）としたときに、
（１）Ｑ［２］＝ＥＣＤＢＬ（Ｑ［ｄ［ｉ］］）
（２）Ｑ［１］＝ＥＣＡＤＤ（Ｑ［０］，Ｑ［１］）
（３）Ｑ［０］＝Ｑ［２−ｄ［ｉ］］
（４）Ｑ［１］＝Ｑ［１＋ｄ［ｉ］］
上記（１）から（４）の演算を所定数回繰り返してｄ×Ｐを求める際に、楕円加算ＥＣＡＤＤと楕円２倍算ＥＣＤＢＬとを並列に実行する楕円曲線暗号の演算方法。
【０１６４】
（付記４７）付記４５記載の楕円曲線暗号の演算方法において、
Ｑ［０］を記憶する第１のレジスタと、Ｑ［１］を記憶する第２のレジスタとを有し、
Ｑ［０］の初期値Ｐを前記第１のレジスタに設定し、Ｑ［１］の初期値２×Ｐを前記第２のレジスタに設定した後、前記楕円加算ＥＣＡＤＤ及び楕円２倍算ＥＣＤＢＬを実行し、ｄ［ｉ］＝０の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第１のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第２のレジスタに格納し、ｄ［ｉ］＝１の場合には、楕円２倍算ＥＣＤＢＬの演算結果を第２のレジスタに格納し、楕円加算ＥＣＡＤＤの演算結果を第１のレジスタに格納する楕円曲線暗号の演算方法。
【０１６５】
（付記４８）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐのｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、Ｐ３＝Ｐ１＋Ｐ２のｘ座標をｘ３としたときに、以下の式
ｘ３＝［（ｘ１×ｘ２−ａ）＾２−４ｂ（ｘ１＋ｘ２）］／［ｘ３’×（ｘ１−ｘ２）＾２］
によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する楕円曲線暗号の演算方法。
【０１６６】
（付記４９）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１，点Ｐのｘ座標ｘ２，Ｐ３’＝Ｐ１−Ｐ２を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、
ｘ３＝［２（ｘ１＋ｘ２）×（ｘ１×ｘ２＋ａ）＋４ｂ］／［（ｘ１−ｘ２）＾２］−ｘ３’
上記の式によりｙ座標を用いずに楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３のｘ座標ｘ３を算出する楕円曲線暗号の演算方法。
【０１６７】
（付記５０）有限体上の楕円曲線の点Ｐ１のｘ座標ｘ１を取得し、
楕円曲線Ｅ；ｙ＾２＝ｘ＾３＋ａ×ｘ＋ｂ    （＾：べき乗を表す）
とし、
ｘ４＝［（ｘ１＾２―ａ）＾２−８×ｘ１］／      ［４（ｘ１＾３＋ａ×ｘ１＋ｂ）］
上記の式によりｙ座標を用いずに楕円２倍算Ｐ４＝２×Ｐ１のｘ座標ｘ４を演算する楕円曲線暗号の演算方法。
【０１６８】
（付記５１）有限体上の楕円曲線の射影座標における、点Ｐ１のＸ座標Ｘ１，Ｚ座標Ｚ１、点Ｐ２のＸ座標Ｘ２，Ｚ座標Ｚ２、点Ｐ３’＝Ｐ１−Ｐ２のＸ座標Ｘ３’，Ｚ座標Ｚ３’を取得し、
楕円曲線Ｅ；Ｙ＾２×Ｚ＝Ｘ＾３＋ａ×Ｘ×Ｚ＾２＋ｂ×Ｚ＾３    （＾：べき乗を表す）
とし、Ｚ３’≠０，Ｘ１×Ｚ２≠Ｘ２×Ｚ１の場合に、
（１）・・・Ｘ３＝Ｚ３’×［（Ｘ１×Ｘ２−ａＺ１×Ｚ２）＾２−４ｂＺ１×Ｚ２（Ｘ１×Ｚ２＋Ｘ２×Ｚ１）］
（２）・・・Ｚ３＝Ｘ３’×［（Ｘ１×Ｚ２−Ｘ２×Ｚ１）＾２］
上記の（１）と（２）式により楕円加算Ｐ３＝Ｐ１＋Ｐ２の点Ｐ３の射影座標におけるＸ座標Ｘ３とＺ座標Ｚ３を演算する楕円曲線暗号の演算方法。
【０１６９】
（付記５２）自然数と楕円曲線Ｅ上に設定されるペースポイントＰとのスカラー倍算を計算する楕円曲線暗号装置において、
前記楕円曲線として有限体上の楕円曲線と、ｎビットの自然数ｄと前記ベースポイントＰとを記憶する記憶手段と、
前記スカラー倍算として点Ｐのｄ倍点ｄ×Ｐを楕円加算と楕円２倍算との並列計算により求める演算手段とを備える楕円曲線暗号装置。
【０１７０】
【発明の効果】
本発明によれば、サイドチャンネル攻撃に対する耐性を保持したまま、スカラー倍算を高速化できる。
【図面の簡単な説明】
【図１】アルゴリズム２のプログラムを示す図である。
【図２】アルゴリズム３のプログラムを示す図である。
【図３】楕円曲線暗号プログラムのフローチャートである。
【図４】アルゴリズム３の具体的処理を示す図である。
【図５】第６の実施の形態の具体的な演算プログラムを示す図である。
【図６】Ｚ３’＝１の場合の第６の実施の形態の具体的な演算プログラムを示す図である。
【図７】第７の実施の形態の具体的な演算プログラムを示す図である。
【図８】Ｚ３’＝１の場合の第７の実施の形態の演算プログラムを示す図である。
【図９】第８の実施の形態の具体的な演算プログラムを示す図である。
【図１０】第９の実施の形態の具体的な演算プログラムを示す図である。
【図１１】ＥＣＤＤＤＢＬの演算プログラムを示す図である。
【図１２】Ｚ３’＝１の場合のＥＣＡＤＤＤＢＬの演算プログラムを示す図である。
【図１３】第１５の実施の形態の演算プログラムを示す図である。
【図１４】実施の形態の演算プログラムを実行するハードウェア環境を示す図である。
【図１５】楕円加算の説明図である。
【図１６】楕円２倍算の説明図である。
【図１７】アルゴリズム１のプログラムを示す図である。
【符号の説明】
１１、１２      レジスタ
２０          情報処理装置
２２，２３    ＣＰＵ
２４          ＲＯＭ
２５          記憶装置
２８          可搬記録媒体
【図１】
0004067818.tif 000002
【図２】
0004067818.tif 000003
【図３】
0004067818.tif 000004
【図４】
0004067818.tif 000005
【図５】
0004067818.tif 000006
【図６】
0004067818.tif 000007
【図７】
0004067818.tif 000008
【図８】
0004067818.tif 000009
【図９】
0004067818.tif 000010
【図１０】
0004067818.tif 000011
【図１１】
0004067818.tif 000012
【図１２】
0004067818.tif 000013
【図１３】
0004067818.tif 000014
【図１４】
0004067818.tif 000015
【図１５】
0004067818.tif 000016
【図１６】
0004067818.tif 000017
【図１７】
0004067818.tif 000018