(57)【特許請求の範囲】
【請求項１】
入出力端子から入出力ポートを経由してメッセージを受け取る手段と、
前記メッセージに対する公開鍵暗号処理を行う手段と、
前記公開鍵暗号処理の処理結果を入出力ポートを介して入出力端子から出力する手段とを備え、
前記公開鍵暗号処理手段は、正の整数Ａ、Ｂ、Ｎ、Ｒ（ただし、前記、Ａ、Ｂは入力変数または中間変数として与えられる変数であり、Ｎは入力変数として与えられる変数であり、Ｒは定数として与えられる数値である）に対して中間演算処理で生じる計算対象数値を表すＡＢＲ−１ｍｏｄＮと、Ａ２Ｒ−１ｍｏｄＮ、及びＡＲ−１ｍｏｄＮを剰余多倍長の乗算演算で計算する多倍長演算手段と、
前記多倍長演算手段を用いて、有限群上の乗算である前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮを繰り返して逆元計算を行う計算手段とを備え、
前記計算手段は、素数ｎと互いに素な正の整数ｋに対する演算ｋ−１ｍｏｄｎを、ｋ−１ｍｏｄｎ≡ｋｎ−２ｍｏｄｎという関係式を利用し、前記ｋ−１ｍｏｄｎを前記ｋｎ−２ｍｏｄｎに置き換え、前記ｋｎ−２ｍｏｄｎの計算を前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮの剰余乗算演算を繰り返し用いて行う逆元計算手段を備えることを特徴とするＩＣカード。
【請求項２】
前記多倍長演算手段はコプロセッサで構成され、前記Ｒは前記コプロセッサの性能によって定まる定数であることを特徴とする請求項１記載のＩＣカード。
【請求項３】
前記公開鍵暗号は楕円曲線暗号であって、
２Ｒｍｏｄｐ、３Ｒｍｏｄｐ、４Ｒｍｏｄｐ、８Ｒｍｏｄｐ、２−１Ｒｍｏｄｐ、ａＲｍｏｄｐ、Ｒｍｏｄｐ、Ｒ２ｍｏｄｐ、Ｒｍｏｄｎ、Ｒ２ｍｏｄｎ（ただし、有限体上の楕円曲線Ｅｐ：ｙ２≡ｘ３＋ａｘ＋ｂ（ｍｏｄｐ）としたときに、有限体位数ｐに対してＲ＞ｐ、Ｒ＞ｎを満たす正整数をＲとする）の数値の少なくとも一つを予め記憶し、前記多倍長演算手段から参照可能にされている書き換え可能な不揮発性メモリ
を備えることを特徴とする請求項１または２記載のＩＣカード。
【請求項４】
前記楕円曲線上のベースポイントＰの正の整数倍の点の値を予め記憶し、前記多倍長演算手段からベースポイントＰの正整数倍の点の値を参照可能にされている書き換え可能な不揮発性メモリ
を備えることを特徴とする請求項１ないし３のいずれか一に記載のＩＣカード。
【請求項５】
ＣＰＵ、及びコプロセッサを有するＩＣカードを用いた暗号処理方法であって、
前記ＣＰＵは、
入出力端子から入出力ポートを経由してメッセージを受け取るステップと、
前記メッセージに対する楕円曲線暗号処理を行うステップと、
前記楕円曲線暗号処理ステップの処理結果を入出力ポートを介して入出力端子から出力するステップと、
を実行し、
前記楕円曲線暗号処理ステップは、
正の整数Ａ、Ｂ、Ｎ、Ｒ（ただし、前記、Ａ、Ｂは入力変数または中間変数として与えられる変数であり、Ｎは入力変数として与えられる変数であり、Ｒは定数として与えられる数値である）に対して中間演算処理で生じる計算対象数値を表すＡＢＲ−１ｍｏｄＮと、Ａ２Ｒ−１ｍｏｄＮ、及びＡＲ−１ｍｏｄＮを剰余多倍長の乗算演算で計算するステップと、
前記コプロセッサを用いて、有限群上の乗算である前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮを繰り返して逆元計算を行うステップと、
を含み、
前記逆元計算ステップは、素数ｎと互いに素な正の整数ｋに対する演算ｋ−１ｍｏｄｎを、ｋ−１ｍｏｄｎ≡ｋｎ−２ｍｏｄｎという関係式を利用し、前記ｋ−１ｍｏｄｎを前記ｋｎ−２ｍｏｄｎに置き換え、前記ｋｎ−２ｍｏｄｎの計算を前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮの剰余乗算演算を繰り返し用いて行う逆元計算を実行するステップ
を含むことを特徴とする暗号処理方法。
【請求項６】
ＣＰＵ、及びコプロセッサを有するＩＣカードに暗号処理を実行させるためのプログラムを記憶する記録媒体であって、
当該プログラムは、前記ＩＣカードに、
入出力端子から入出力ポートを経由してメッセージを受け取るステップと、
前記メッセージに対する楕円曲線暗号処理を行うステップと、
前記楕円曲線暗号処理ステップの処理結果を入出力ポートを介して入出力端子から出力するステップと、
を実行させ、
前記楕円曲線暗号処理ステップは、
正の整数Ａ、Ｂ、Ｎ、Ｒ（ただし、前記、Ａ、Ｂは入力変数または中間変数として与えられる変数であり、Ｎは入力変数として与えられる変数であり、Ｒは定数として与えられる数値である）に対して中間演算処理で生じる計算対象数値を表すＡＢＲ−１ｍｏｄＮと、Ａ２Ｒ−１ｍｏｄＮ、及びＡＲ−１ｍｏｄＮを剰余多倍長の乗算演算で計算するステップと、
前記コプロセッサを用いて、有限群上の乗算である前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮを繰り返して逆元計算を行うステップと、
を含み、
前記逆元計算ステップは、素数ｎと互いに素な正の整数ｋに対する演算ｋ−１ｍｏｄｎを、ｋ−１ｍｏｄｎ≡ｋｎ−２ｍｏｄｎという関係式を利用し、前記ｋ−１ｍｏｄｎを前記ｋｎ−２ｍｏｄｎに置き換え、前記ｋｎ−２ｍｏｄｎの計算を前記ＡＢＲ−１ｍｏｄＮと前記Ａ２Ｒ−１ｍｏｄＮの剰余乗算演算を繰り返し用いて行う逆元計算を実行するステップ
を含むことを特徴とする暗号処理を実行させるためのプログラムを記憶する記録媒体。
【請求項７】
剰余乗算演算器を用いる暗号処理装置を備えた電子装置に用いられ、
暗号処理において、生成すべき値ｋ、剰余乗算演算器の性能によって決まる定数Ｒ、素数ｎと互いに素な正の整数ｋに対する演算ｋ−１ｍｏｄｎを、ｋ−１ｍｏｄｎ≡ｋｎ−２ｍｏｄｎという関係式を利用して演算する逆元演算モジュールであって、
前記剰余乗算演算器でｋＲｍｏｄｎを計算し、その計算結果を第１レジスタと第２レジスタとに記憶させる第１手段と、
前記第１レジスタの値を二乗しＲ−１をかけて、その結果のｍｏｄｎをとった値を第１レジスタに記憶するＡ２Ｒ−１ｍｏｄＮの演算器と、
前記第１レジスタと前記第２レジスタの値を乗算しＲ−１をかけて、その結果のｍｏｄｎをとった値を第１レジスタに記憶するＡＢＲ−１ｍｏｄＮの演算器と、
前記Ａ２Ｒ−１ｍｏｄＮの演算器と前記ＡＢＲ−１ｍｏｄＮの演算器による処理を繰り返し、ｋｎ−２ｍｏｄｎを求める第２手段と、
を含むことを特徴とする逆元演算モジュール。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、暗号を処理するＩＣカードに関する。
【０００２】
【従来の技術】
公開鍵暗号系の暗号であり、１９７８年にリヴェスト（Ｒｉｖｅｓｔ）、シャミア（Ｓｈａｍｉｒ）、エイドルマン（Ａｄｌｍａｎ）の３人によって発明されたＲＳＡ暗号の基本原理を述べる。
【０００３】
［ＲＳＡ暗号の基本原理］秘密鍵を（ｄ，ｎ）、公開鍵を（ｅ，ｎ）、平文をＭ、暗号文をＣとすると暗号化と復号化は次のような計算式で表すことができる。
【０００４】
暗号化：Ｃ≡Ｍｅ（ｍｏｄｎ）
復号化：Ｍ≡Ｃｄ（ｍｏｄｎ）
但し、ｎ＝ｐ・ｑ（ｐ、ｑは大きな素数）、λ（ｎ）＝ＬＣＭ｛（ｐ−１），（ｑ−１）｝（ＬＣＭ：最小公倍数）、ＧＣＤ｛ｅ，λ（ｎ）｝＝１（ＧＣＤ：最大公約数）、ｄ＝ｅ−１ｍｏｄλ（ｎ）を満たす。
【０００５】
ＲＳＡ暗号の安全性は、ｎを素因数分解することの困難さに基づいており、ｅ、ｄ、ｎ、Ｍ等のパラメータには１０２４ビット程度の大きな整数を用いることが推奨されている。この時、１回の暗号化式Ｍｅｍｏｄｎにおける処理はバイナリ演算法（Ｄ．Ｅ．Ｋｎｕｔｈ，“Ｓｅｍｉｎｕｍｅｒｉｃａｌ ａｌｇｏｒｉｔｈｍｓ（ａｒｉｔｈｍｅｔｉｃ）”，Ｔｈｅ Ａｒｔ ｏｆ Ｃｏｍｐｕｔｅｒ Ｐｒｏｇｒａｍｍｉｎｇ，Ｖｏｌｕｍｅ２，Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ，１９６９に詳しく述べられている）を用いた場合、平均１５３４．５回の剰余乗算演算が必要となる。
【０００６】
また、公開鍵暗号系の暗号であり、１９８５年にコブリッツ（Ｋｏｂｌｉｔｚ）とミラー（Ｍｉｌｌｅｒ）によってそれぞれ独立に提案された楕円曲線暗号の基本原理を述べる。
【０００７】
［楕円曲線暗号の原理］楕円曲線の概要を説明する。有限体の位数を素数ｐ、楕円曲線を決定するパラメータ（ａ，ｂ）に対して以下の式を満たす点の集合に仮想的な無限遠点Ｏを加えた集合を、楕円曲線Ｅｐと呼ぶ。ここでは便宜上、２次元アフィン座標系で表す。
【０００８】
Ｅｐ：ｙ２≡ｘ３＋ａｘ＋ｂ（ｍｏｄｐ）
楕円曲線上では曲線上の２点の間に楕円曲線上の加法が定義され、
Ｐ３＝Ｐ１＋Ｐ２（但し、Ｐｉ＝（ｘｉ，ｙｉ））は以下のように定義される。
【０００９】
［（Ｐ１≠Ｐ２）の場合］以降、この場合を楕円加算演算と呼ぶ。
【００１０】
楕円加算演算：加算０回、減算６回、乗算２回、除算１回
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１），ｘ３＝λ２−ｘ１−ｘ２，
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
［（Ｐ１＝Ｐ２）の場合］以降、この場合を楕円２倍演算と呼ぶ。
【００１１】
楕円２倍演算：加算１回、減算３回、乗算３回、除算１回
λ＝（３ｘ１２＋ａ）／２ｙ１，ｘ３＝λ２−２ｘ１，
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
但し、上記演算はすべてｐを法とする剰余系で行われる。
【００１２】
楕円曲線暗号の安全性は、楕円曲線上の点Ａをｘ倍（すなわちＡをｘ回加算した）点をＢ（＝ｘ・Ａ）とする時、点Ａと点Ｂの値が分かったとしてもその値からｘを求めることが非常に困難であることに基づく。この性質を楕円曲線上の離散対数問題と呼び、ＲＳＡ暗号の１０２４ビットと同程度の安全性を確保するためには、ｐ、ａ、ｘｉ、ｙｉ等のパラメータには１６０ビット程度の整数が推奨されている。
【００１３】
楕円曲線暗号の基本演算となる点Ｐのｋ倍点（ｋ・Ｐ）の演算は、上記の楕円曲線上の加法を用いて計算を行うこととなるが、この演算においてはλを求める際に剰余除算演算を行う必要がある。剰余除算演算は拡張ユークリッド互除法等のアルゴリズムを用いて処理するのが一般的であるが、多くの処理時間を必要とする。そのため、２次元アフィン座標系の点を３次元座標系の点に変換することにより、その剰余除算演算を行うことなく楕円曲線上の演算を処理する方法が広く用いられている。詳しくは、Ｄ．Ｖ．Ｃｈｕｄｎｏｖｓｋｙ ａｎｄ Ｇ．Ｖ．Ｃｈｕｄｎｏｖｓｋｙ， ”Ｓｅｑｕｅｎｃｅｓ ｏｆ ＮｕｍｂｅｒｓＧｅｎｅｒａｔｅｄ ｂｙ Ａｄｄｉｔｉｏｎ ｉｎ Ｆｏｒｍａｌ Ｇｒｏｕｐｓ ａｎｄ Ｎｅｗ Ｐｒｉｍａｌｉｔｙ ａｎｄ Ｆａｃｔｏｒｉｚａｔｉｏｎ Ｔｅｓｔｓ”，Ａｄｖａｎｃｅｓ ｉｎ Ａｐｐｌｉｅｄ Ｍａｔｈｅｍａｔｉｃｓ，７，ｐｐ．３８５−４３４，１９８６に述べられている。一例として、２次元アフィン座標系での楕円曲線Ｅｐ上の加算演算を、ｘ≡Ｘ／Ｚ２（ｍｏｄｐ）、
ｙ≡Ｙ／Ｚ３（ｍｏｄｐ）を満たすような３次元射影座標系に変換した場合は、以下のように定義される。
【００１４】
楕円加算演算：加算２回、減算５回、乗算１６回、除算０回
Ｘ３＝Ｒ２−ＴＷ２，２Ｙ３＝ＶＲ−ＭＷ３，Ｚ３＝Ｚ１Ｚ２Ｗ
但し、Ｗ＝Ｘ１Ｚ２２−Ｘ２Ｚ１２，Ｒ＝Ｙ１Ｚ２３−Ｙ２Ｚ１３，
Ｔ＝Ｘ１Ｚ２２＋Ｘ２Ｚ１２，Ｍ＝Ｙ１Ｚ２３−Ｙ２Ｚ１３，
Ｖ＝ＴＷ２−２Ｘ３
楕円２倍演算：加算１回、減算３回、乗算１０回、除算０回
Ｘ３＝Ｍ２−２Ｓ，Ｙ３＝Ｍ（Ｓ−Ｘ３）−Ｔ，Ｚ３＝２Ｙ１Ｚ１
但し、Ｍ＝３Ｘ１２＋ａＺ１４，Ｓ＝４Ｘ１Ｙ１２，Ｔ＝８Ｙ１４
但し、上記演算はすべてｐを法とする剰余系で行われる。
【００１５】
この他の座標変換の例としては、ｘ≡Ｘ／Ｚ（ｍｏｄｐ）、
ｙ≡Ｙ／Ｚ（ｍｏｄｐ）を満たすような３次元同次座標系への変換法などがある。
【００１６】
但し、３次元座標系から２次元座標系へ再び変換する時に剰余除算演算が一度必要となる。
【００１７】
仮に、１６０ビット楕円曲線暗号を３次元射影座標系に変換し、ｋ・Ｐ演算を上述のバイナリ演算法を用いて処理した場合、平均２８６２回の剰余乗算演算が必要となる。
【００１８】
上述したように、ＲＳＡ暗号や楕円曲線暗号等の公開鍵暗号ではその基本演算として多くの剰余乗算演算処理を必要とする。そのため、剰余乗算演算の高速アルゴリズムを用いることにより剰余乗算演算の高速化を図り、暗号処理全体の高速化を図る方式が考案されている。
【００１９】
特に、ＲＳＡ暗号はその演算の大部分が剰余乗算演算であることから、剰余乗算演算の高速アルゴリズムを実行するハードウェアと、それを用いることによりＲＳＡ暗号処理を高速に実行するＩＣカードが、ＩＣカードの標準規格であるＩＳＯ７８１６に基づいて実現されている。
【００２０】
【発明が解決しようとする課題】
これに対し、ＲＳＡ以外の公開鍵暗号やディジタル署名では、剰余除算演算を必要とすることがある。剰余四則演算の中でも剰余除算演算は特に演算時間を必要とするため、暗号処理、署名生成処理の高速化を図る上での大きな課題となっている。剰余除算演算を利用する公開鍵暗号方式の一つとして、楕円曲線暗号がある。この楕円曲線暗号処理における剰余除算演算回数を減らすための方法や、その剰余除算演算を高速に計算する方法が、新保淳"楕円曲線暗号へのモンゴメリ演算の適用"ＳＣＩＳ'９７（Ｔｈｅ １９９７ Ｓｙｍｐｏｓｉｕｍ ｏｎ Ｃｒｙｐｔｏｇｒａｐｈｙ ａｎｄ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ）において検討されている。
【００２１】
しかし、この文献における方法を、上記ISO7816規格で規定されるＩＣカードのような装置に適用する場合、上記規格、現在の半導体技術の限界などによりＣＰＵの演算能力に限界がある。したがって剰余除算演算における逆元演算に時間がかかり、処理の高速化を図ることが困難となる。
【００２２】
従って、本発明の目的は、剰余乗算演算の高速アルゴリズムを実行するハードウェアを具えた暗号処理装置において、楕円曲線暗号処理を高速に実行できる方法、及びそれを用いた装置、たとえばＩＣカードを提供することである。
【００２３】
また、本発明の他の目的は、剰余乗算演算の高速アルゴリズムを実行するハードウェアを具えた装置、たとえばＩＣカードにおいて、ディジタル署名処理を高速に実行する方法、及び該方法を実現する装置を提供することである。
【００２４】
本発明の他の目的は、楕円曲線暗号処理において、剰余除算における逆元演算を高速化できる方法およびそれを用いたプログラムまたは装置を提供することである。
【００２５】
また、本発明の他の目的は、剰余乗算演算の高速アルゴリズムを実行するハードウェアを具えた暗号処理装置において、ＤＳＡ署名、Ｓｃｈｎｏｒｒ署名等、各種処理を高速に実行できる方法、及びそれを用いた装置、たとえばＩＣカードを提供することである。
【００２６】
本発明の他の目的は、ＤＳＡ署名、Ｓｃｈｎｏｒｒ署名処理等の剰余除算演算を必要とする各種公開鍵方式、ディジタル署名方式において、剰余除算における逆元演算を高速化できる方法およびそれを用いた装置を提供することである。
【００２７】
【課題を解決するための手段】
上記目的を達成するため、本発明に従えば以下の様態が提供される。
まず、本発明の1つの態様に従えば、剰余乗算演算の高速アルゴリズムをハードウェア化した装置（以降、剰余乗算器と呼ぶ）を具えた装置、たとえばＩＣカードにおいて、その剰余乗算器を効果的に利用するように、楕円曲線暗号における演算を剰余乗算演算を中心とした演算で構成する楕円曲線暗号処理方法を提供する。
具体的には、楕円曲線暗号処理に必要な乱数生成の後の剰余演算や、署名作成処理における剰余演算を、剰余乗算器を用いて演算できるように構成する。また、剰余乗算器を楕円曲線上の演算でも効果的に利用するために、楕円曲線上の点を２次元アフィン座標系から３次元座標系に変換することにより、楕円曲線上の加算演算における剰余除算演算を剰余乗算演算に変換し、その剰余乗算演算に剰余乗算器を利用できるように処理する。
【００２８】
また、本発明の他の態様では、上記課題にも述べた逆元演算を高速化するために、３次元座標系から２次元アフィン座標系に変換する場合と署名データを求める際に必要となる逆元演算をも、剰余乗算演算を用いて計算する。剰余系における逆元演算は、拡張ユークリッド互除法等のアルゴリズムを用いて求めるのが一般的であるが、剰余の法が素数である場合には、拡張ユークリッド互除法等のアルゴリズムを用いることなく、剰余乗算演算のみを用いて求めることができる。以下にその方法を示す。
フェルマーの小定理によると、素数βと互いに素な正整数αに対し、
αβ−１≡１（ｍｏｄβ）
が成立する。この定理を用いれば、逆元演算α−１ｍｏｄβは以下のように表すことができる。
α−１≡αβ−２（ｍｏｄβ）
本発明では、楕円曲線暗号の安全性を保つために有限体の位数ｐ及びベースポイント位数ｎの値は大きな素数を用いており、上記フェルマーの小定理における条件、素数βと正整数αは互いに素であることを常に満たす。従って、
α−１ｍｏｄβの値はαβ−２ｍｏｄβと等しくなり、仮にバイナリ演算法を用いて剰余乗算演算を行った場合、平均（（｜β−２｜−１）×３／２）
（ただし｜β−２｜は（β−２）のビット数を表す）回の剰余乗算を行うことにより逆元演算α−１ｍｏｄβの値を求めることが可能である。この方法を用いた場合、ユークリッド互除法等のアルゴリズムをプログラムとして作成する必要が無いため、プログラムサイズの低減を図ることにもなった。
【００２９】
この逆元演算方法は、楕円曲線暗号に限らず、逆元演算を必要とする他の各種公開鍵方式、ディジタル署名方式、例えば、ＤＳＡ署名、Ｓｃｈｎｏｒｒ署名等の処理にも利用することができる。
【００３０】
また、演算で頻繁に使用されるパラメータで、事前に計算可能なものはパソコン等で事前に計算し、システム情報の一つとしてＩＣカード内の書き換え可能な不揮発性メモリに記憶させておくことにより、計算量を削減できる。事前に記憶させておくシステム情報としてのデータは、有限体位数ｐと、楕円曲線パラメータａを変換したａＲｍｏｄｐと、楕円曲線上の点Ｐ（ベースポイント）の２次元アフィン座標（ｘ，ｙ）を3次元射影座標系の座標に変換し、さらに剰余乗算装置用に変換した点Ｐ（Ｘ，Ｙ，Ｚ）と、ベースポイントの位数ｎと、秘密鍵ｄと、楕円曲線上の演算で用いる定数を変換した２Ｒｍｏｄｐと３Ｒｍｏｄｐと４Ｒｍｏｄｐと８Ｒｍｏｄｐと２−１Ｒｍｏｄｐと、剰余演算に用いるためのＲｍｏｄｐとＲｍｏｄｎとＲ２ｍｏｄｐとＲ２ｍｏｄｎとする。但し、ここで用いたＲは有限体位数ｐ，ベースポイントの位数ｎに対しＲ＞ｐ，Ｒ＞ｎを満たす正整数、例えば、ｐ、ｎのビット数をそれぞれ｜ｐ｜、｜ｎ｜と表す時、
｜ｐ｜＋１または｜ｎ｜＋１のうち大きいほうに等しいビット長を持つ最小の正整数、とする。
【００３１】
さらに、ＩＣカードにおける楕円曲線上の加算演算における処理回数を減らして全体の計算量を減らすために、ベースポイントの定数倍の点をテーブルとしてＩＣカード内の書き換え可能な不揮発性メモリに記憶させておくこととした。但し、テーブルの数が増加するにつれて計算量は減少するが、逆に前記メモリに記憶するデータサイズが大きくなる。そのため、本発明ではベースポイントの４のべき乗倍の点をテーブルとして持つこととした。この時、テーブルとして持つ点の数、即ちテーブルの個数は有限体位数ｐのビット数を｜ｐ｜と表す時、
（｜ｐ｜／２）個となり、テーブルの値は3次元射影座標系の座標に変換し、さらに剰余乗算装置の演算域に変換した後の点Ｐｉ＝（Ｘｉ，Ｙｉ，Ｚｉ）
（ｉは０≦ｉ＜｜ｐ｜／２の整数）とする。
【００３２】
また、メモリサイズがより大きな場合には、ベースポイントの２のべき乗倍の点をテーブルとして持つことにより、楕円曲線上の演算を楕円加算演算のみで構成することも可能となり、この場合、さらに処理回数を減らすことができる。
【００３３】
なお、一般的には、ベースポイントの２のｎ乗倍（ｎは自然数）の点の値をテーブルとして持つ場合、テーブルの個数は、有限体位数ｐのビット数を｜ｐ｜と表す時、（｜ｐ｜／ｎ）個となり、ＣＰＵの演算性能とテーブルを記憶するメモリ容量とのトレードオフで決めることが出来る。
【００３４】
【発明の実施の形態】
本発明の一実施例を図面を用いて説明する。
【００３５】
図1は、本発明による有限体上の楕円曲線における加算演算を用いたディジタル署名システム実行装置を、例えば日立製作所のＨ８／３１１１マイコンに基づいて、ＩＣカード内に実現する際の概略構成図を示す。この種のＩＣカード１０１は、ＣＰＵ１０２と、特に本発明を実施する動作命令を含むＲＯＭ１０３と、有限体位数や楕円曲線パラメータ等のシステム情報のデータを記憶する書き換え可能な不揮発メモリとしてのＥＥＰＲＯＭ１０４と、ＩＣカード１０１への入力／出力を制御するＩ／Ｏポート１０５と、ＲＡＭ１０６と、剰余乗算演算を実行可能な剰余乗算器１０７と、電源端子Ｖｃｃ１１０と、グランド端子Ｖｓｓ１１１と、クロック端子ＣＬＫ１１２と、リセット端子ＲＥＳ１１１３と、Ｉ／Ｏ端子Ｉ／Ｏ１１４とを含む。ＩＣカード１０１の各端子は、ＩＣカード１０１内の必要な部分に接続されている。剰余乗算器は例えば高速演算機能を備えた日立製作所製マイコンH8/3111のコプロセッサにより構成することができる。他の相当コプロセッサを用いることもできる。
【００３６】
この剰余乗算器１０７は内部にＣＰＵ１０２と共通に利用できるＣＰＵ・剰余乗算器共通ＲＡＭ１０９を具え、そのＲＡＭ１０９は少なくともＣＤＡ、ＣＤＢ、ＣＤＮの３本のデータレジスタを備える。剰余乗算器１０７の演算は、入力データをレジスタＣＤＡ，ＣＤＢ，ＣＤＮに記憶させて実行すると、その演算結果はＣＤＡの値を書き換えて記憶される。また、演算後にＣＤＢとＣＤＮの値は変化しない特徴を持つ。この剰余乗算器１０７は演算タイプを指定することにより、以下の３種類の演算を実行可能な装置にする。
【００３７】
ＣＤＡ←（ＣＤＡ・ＣＤＢ）Ｒ−１ｍｏｄ（ＣＤＮ）：以降、剰余演算１と呼ぶ。
ＣＤＡ←（ＣＤＡ２）Ｒ−１ｍｏｄ（ＣＤＮ）：以降、剰余演算２と呼ぶ。
ＣＤＡ←（ＣＤＡ）Ｒ−１ｍｏｄ（ＣＤＮ）：以降、剰余演算３と呼ぶ。
ＩＣカード１０１内の前記各素子はバス１０８により相互接続される。
また、本発明に用いた楕円曲線Ｅｐは有限体の位数を素数ｐとし、楕円曲線を決定するパラメータ（ａ，ｂ）に対して以下の式を満たす点の集合に仮想的な無限遠点Ｏを加えた集合とした。ここでは便宜上、アフィン座標系で表す。
Ｅｐ：ｙ２≡ｘ３＋ａｘ＋ｂ（ｍｏｄｐ）
さらにベースポイントをＰ（ｘ，ｙ）とし、そのベースポイントの位数も素数ｎとなるものを用いた。
【００３８】
（１）システム情報の記憶
有限体位数ｐと、楕円曲線パラメータａＲｍｏｄｐと、楕円曲線上の点Ｐ（ベースポイント）の座標の定数倍の点Ｐｉ（Ｘｉ，Ｙｉ，Ｚｉ）
（ｉは０≦ｉ＜｜ｐ｜／２の整数、｜ｐ｜は有限体位数ｐのビット数を表す）と、ベースポイントの位数ｎと、秘密鍵ｄと、楕円曲線上の演算で用いる定数を変換した２Ｒｍｏｄｐと３Ｒｍｏｄｐと４Ｒｍｏｄｐと８Ｒｍｏｄｐと２−１Ｒｍｏｄｐと、剰余演算に用いるためのＲｍｏｄｐとＲｍｏｄｎとＲ２ｍｏｄｐとＲ２ｍｏｄｎとをＥＥＰＲＯＭ１０４に記憶しておく。但し、ここで用いたＲは、Ｒ＞ｐ，Ｒ＞ｎを満たす正整数、例えば、ｐ、ｎのビット数をそれぞれ｜ｐ｜、｜ｎ｜と表す時、｜ｐ｜＋１または｜ｎ｜＋１のうち大きいほうに等しいビット長を持つ最小の正整数、とする。
【００３９】
これらシステム情報の記憶は、以下の暗号処理が実行される前に行われているものとする。ここでRは定数として与えられる数値であって、多倍長演算手段を構成する、例えばコプロセッサの演算性能に依存して決まるパラメータである。
【００４０】
（２）署名作成
図２から図7は、本実施例における楕円曲線暗号処理装置が行うディジタル署名作成のフローチャートを示す。以下、図２を参照しながらディジタル署名作成の概略の手順を示す。
なお、以下の各フローチャートは、ＣＰＵ１０２が、ＲＡＭ１０６、ＥＥＰＲＯＭ１０４に格納されたデータを用いながら、必要に応じて剰余演算器１０７に処理を実行させながら、ＲＯＭ１０３に記憶されたプログラムを実行する内容を示している。
【００４１】
ステップ２０１：開始
ステップ２０２：乱数ｋを生成し、剰余乗算器１０７のレジスタＣＤＡにその乱数ｋを、またレジスタＣＤＢにＥＥＰＲＯＭ１０４に記憶しておいたＲｍｏｄｎを記憶させ、剰余乗算器１０７に前述定義した剰余演算１を実行させる。ＣＤＡに記憶される実行結果を改めて乱数ｋとする。
ステップ２０３：ステップ２０２で生成した乱数ｋとＥＥＰＲＯＭ１０４に記憶しておいたシステム情報ｐ、ａＲｍｏｄｐ、Ｐ（Ｘ，Ｙ，Ｚ）を入力とし、楕円曲線Ｅｐ上においてベースポイントＰの乱数ｋ倍の演算ｋ・Ｐを計算する。この演算は、３次元射影座標系で有限体上の楕円曲線における加算演算すなわちスカラー倍演算をＣＰＵ１０２で行い、その演算における剰余乗算は、コプロセッサである剰余乗算器１０７を用いて計算する。
【００４２】
ステップ２０４：ステップ２０３の実行結果（Ｘ，Ｙ，Ｚ）は３次元射影座標系の点であるため、アフィン座標系の点（ｘ，ｙ）に変換する。この変換のための演算はｘ≡Ｘ／Ｚ２（ｍｏｄｐ）であるがその代わりに演算ｘ≡Ｘ・Ｚｐ−３（ｍｏｄｐ）を行えばよい。何故ならフェルマーの小定理を応用することによりｘ≡Ｘ・Ｚｐ−３（ｍｏｄｐ）が成り立つからである。従ってｘ≡Ｘ／Ｚ２（ｍｏｄｐ）を使わずにＸ・Ｚｐ−３（ｍｏｄｐ）を使うことにより剰余除算演算を用いることなく剰余乗算のみで座標変換を行える。
ステップ２０５：ステップ２０２で生成した乱数ｋと、Ｉ／Ｏ端子１１４からＩ／Ｏポート１０５経由で入力された、メッセージＭに対するハッシュ値(ダイジェスト値)Ｈ（Ｍ）と、ＥＥＰＲＯＭ１０４に記憶しておいた秘密鍵ｄ、ベースポイントの位数ｎと、ステップ２０４で計算したｘｍｏｄｐとを用いて以下の演算を行う。
【００４３】
署名ｒの生成：ｒ≡ｘ（ｍｏｄｎ）
署名ｓの生成：ｓ≡ｋ−１・（Ｈ（Ｍ）＋ｄ・ｒ）（ｍｏｄｎ）
上記演算における署名ｓの演算の際に逆元演算が必要となるが、この演算もステップ２０４と同様の方法によりｋ−１ｍｏｄｎの値をｋｎ−２ｍｏｄｎの剰余乗算に置き換え、その剰余乗算を剰余乗算器１０７を用いて計算する。この演算結果を署名（ｒ，ｓ）とし、メッセージＭに対するディジタル署名としてＩ／Ｏポート１０５を経由してＩ／Ｏ端子１１４から出力する。
ステップ２０６：終了
次に図３から図７を用いて、本実施例におけるディジタル署名作成の手順をさらに詳しく説明する。
図３は、図２ステップ２０３の処理の詳細なフローチャートである。
ステップ３０１：開始
ステップ３０２：ステップ２０２で生成した乱数ｋの２進数表記を２ビットずつ組にしたｋ＝（ｋｉ，ｋｉ−１，…，ｋ１，ｋ０）２を計算し、そのビット列を下位から走査してｋｉ＝（１１）である時、その上位ビット列ｋｉ＋１にたいして（０１）を加算し、最上位ビットまでを書き換える。その変換例は、元のビット列を（１０，１１，１０，１１）とすると、変換後のビット列は（０１，１１，００，１１，１１）となる。この変換を最上位ビットまで行い、改めてそのビット列を
ｋ＝（ｋｌ，ｋｌ−１，…，ｋ１，ｋ０）２（但し、ｋｌ≠（００））とする。
この時得られるｌの値を楕円曲線上の演算を繰り返す回数として変数ｉ（以降、ループカウンタと呼ぶ）に（ｌ＋１）を記憶する。
【００４４】
ステップ３０３：前述したようにＥＥＰＲＯＭ１０４に記憶しておいたテーブル値である楕円曲線上のベースポイントの3次元座標変換後の剰余乗算器用に変換した点
Ｐｉ（Ｘｉ，Ｙｉ，Ｚｉ）から初期値をＲＡＭ１０６に記憶させ、Ｐｉに対応するｋｉの値を書き換える。
ステップ３０４：ループカウンタｉを１だけカウントダウンする。
ステップ３０５：ループカウンタｉの判定を行う。ｉが０より小さければステップ３０７へ進む。そうでなければステップ３０６へ進む。
ステップ３０６：ｋｉの値が（００）であれば、ステップ３０４へ戻る。ｋｉの値が（０１）であれば、テーブル値Ｐｉを加算する楕円加算演算を行いステップ３０４へ戻る。ｋｉの値が（１０）であれば、テーブル値Ｐｉを２倍する楕円２倍演算を行い、その結果を加算する楕円加算演算を行いステップ３０４へ戻る。ｋｉの値が（１１）であれば、テーブル値ＰｉのＹ座標の値に対し、法をｐとした加法に対する逆元を求め、その値を改めてテーブル値ＰｉのＹ座標とし、その点を加算する楕円加算演算を行いステップ３０４へ戻る。
ステップ３０７：終了
図４は、図３の処理における楕円加算演算の詳細なフローチャートである。
ステップ４０１：開始。ステップ３０３において剰余乗算器１０７のＣＤＮにはｐが記憶されているため、ｐを法とした剰余乗算が行われる。
【００４５】
ステップ４０２：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ４０３：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４０４：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ４０５：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４０６：ＣＰＵ１０２は剰余減算演算を行い、中間値Ｗを得る。
ステップ４０７：ＣＰＵ１０２は剰余加算演算を行い、中間値Ｔを得る。
ステップ４０８：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４０９：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４１０：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４１１：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４１２：ＣＰＵ１０２は剰余減算演算を行い、中間値Ｒを得る。
ステップ４１３：ＣＰＵ１０２は剰余加算演算を行い、中間値Ｍを得る。
【００４６】
ステップ４１４：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４１５：剰余乗算器１０７を用いて剰余演算１を実行し、楕円加算演算後の点のＺ座標を得る。
ステップ４１６：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ４１７：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ４１８：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４１９：ＣＰＵ１０２は剰余減算演算を行い、楕円加算演算後の点のＸ座標を得る。
ステップ４２０：ＣＰＵ１０２は剰余減算演算を行い、中間値Ｖを得る。
ステップ４２１：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４２２：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４２３：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ４２４：ＣＰＵ１０２は剰余減算演算を行い、中間値Ｙを得る。
ステップ４２５：ＥＥＰＲＯＭ１０４に記憶しておいた２−１Ｒｍｏｄｐと中間値Ｙを剰余乗算器１０７に入力し、剰余演算１を実行する。これにより楕円加算演算後の点のＹ座標を得る。
ステップ４２６：終了
図５は、図３の処理における楕円２倍演算の詳細なフローチャートを示す。
ステップ５０１：開始。ステップ３０３において剰余乗算器１０７のＣＤＮにはｐが記憶されているため、ｐを法とした剰余乗算が行われる。
ステップ５０２：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５０３：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５０４：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５０５：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ５０６：ＥＥＰＲＯＭ１０４に記憶しておいた３Ｒｍｏｄｐとステップ５０２で求めたＸ１２Ｒｍｏｄｐを剰余乗算器１０７に入力し、剰余演算１を実行する。
ステップ５０７：ＣＰＵ１０２は剰余加算演算を行い、中間値Ｍを得る。
ステップ５０８：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５０９：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ５１０：ＥＥＰＲＯＭ１０４に記憶しておいた４Ｒｍｏｄｐとステップ５０９で求めたＸ１Ｙ１２Ｒｍｏｄｐを剰余乗算器１０７に入力し、剰余演算１を実行する。これにより中間値Ｓを得る。
【００４７】
ステップ５１１：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５１２：ＥＥＰＲＯＭ１０４に記憶しておいた８Ｒｍｏｄｐとステップ５１１で求めたＹ１４Ｒｍｏｄｐを剰余乗算器１０７に入力し、剰余演算１を実行する。これにより中間値Ｔを得る。
ステップ５１３：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ５１４：ＥＥＰＲＯＭ１０４に記憶しておいた２Ｒｍｏｄｐとステップ５１３で求めたＹ１Ｚ１Ｒｍｏｄｐを剰余乗算器１０７に入力し、剰余演算１を実行する。これにより楕円２倍演算後の点のＺ座標を得る。
ステップ５１５：剰余乗算器１０７を用いて剰余演算２を実行する。
ステップ５１６：ＥＥＰＲＯＭ１０４に記憶しておいた２Ｒｍｏｄｐと中間値Ｓを剰余乗算器１０７に入力し、剰余演算１を実行する。
ステップ５１７：ＣＰＵ１０２は剰余減算演算を行い、楕円２倍演算後の点のＸ座標を得る。
ステップ５１８：剰余乗算器１０７を用いて剰余演算１を実行する。
ステップ５１９：ＣＰＵ１０２は剰余減算演算を行い、楕円２倍演算後の点のＹ座標を得る。
ステップ５２０：終了
図６は、図２ステップ２０４の処理(逆元演算)の詳細なフローチャートを示す。
ステップ６０１：開始
ステップ６０２：ＥＥＰＲＯＭ１０４に記憶しておいた有限体位数ｐから（ｐ−３）を計算し、その２進数表記
（ｐ−３）＝（ｊｌ，ｊｌ−１，…，ｊ１，ｊ０）２（但し、ｊｌ＝１）から得られるｌの値を剰余乗算演算を繰り返す回数としてループカウンタｉに記憶する。
ステップ６０３：剰余乗算器１０７のＣＤＡ，ＣＤＢにステップ２０３の演算後の点のＺ座標を記憶させる。また、ＣＤＮの値はステップ３０３において剰余乗算器１０７のＣＤＮにｐを記憶させたまま変化していないため、ｐの値が記憶されている。
ステップ６０４：ループカウンタｉを１だけカウントダウンする。
ステップ６０５：ループカウンタｉの判定を行う。ｉが０より小さければステップ６０９へ進む。そうでなければステップ６０６へ進む。
ステップ６０６：剰余乗算器１０７を用いて剰余演算２を実行する。
【００４８】
ステップ６０７：（ｐ−３）のループカウンタｉに対する値ｊｉの判定を行う。ｊｉが１でなければステップ６０４へ戻る。ｊｉが１であればステップ６０８へ進む。
ステップ６０８：剰余乗算器１０７を用いて剰余演算１を実行する。その後、ステップ６０４へ戻る。
ステップ６０９：剰余乗算器１０７のＣＤＢにステップ２０３の演算後の点のＸ座標を記憶させる。この時、ＣＤＡにはＺｐ−３Ｒｍｏｄｐの値が記憶されている。
ステップ６１０：剰余乗算器１０７を用いて剰余演算１を実行する。この結果、ＣＤＡにはＸＺｐ−３Ｒｍｏｄｐの値、すなわちステップ２０３の実行結果の２次元アフィン座標系における座標のｘ座標の剰余乗算装置の演算域への変換値ｘＲ≡ＸＺ−２Ｒ（ｍｏｄｐ）の値が記憶されている。
ステップ６１１：剰余乗算器１０７を用いて剰余演算３を実行する。この結果、ＣＤＡにはＸＺ−２ｍｏｄｐの値、すなわちステップ２０３の実行結果の２次元アフィン座標系における座標のｘ座標ｘ≡ＸＺ−２（ｍｏｄｐ）の値が記憶されている。上記ステップ６０４から６０８では、Ｘ／Ｚ２を求める演算の１／Ｚ２を、Ｚｐ−３に変換し、剰余演算器１０７によってその値を求めている。
ステップ６１２：終了
上述のように、本発明では、剰余乗算器１０７の多倍長剰余乗算機能を用いることにより、ＣＰＵ１０２を用いた多倍長剰余乗算演算を行う必要が無い。このため、演算ステップが少なくて済み、処理の高速化が可能である。
【００４９】
図７は、図２ステップ２０５の処理の詳細なフローチャートである。
ステップ７０１：開始
ステップ７０２：ステップ２０４で計算されたｋＰのｘ座標の値ｘｍｏｄｐを剰余乗算器１０７のＣＤＡに記憶させる。
ステップ７０３：剰余乗算器１０７のＣＤＢにＥＥＰＲＯＭ１０４に記憶しておいたＲｍｏｄｎを記憶させる。Ｒはコプロセッサの固有の値、ｎは楕円曲線上のＰの位数である。
ステップ７０４：剰余乗算器１０７のＣＤＮにＥＥＰＲＯＭ１０４に記憶しておいたベースポイント位数ｎを記憶させる。
ステップ７０５：剰余乗算器（コプロセッサ）１０７を用いて剰余演算１を実行する。この演算結果であるｘｍｏｄｎの値がＣＤＡに記憶される。この値が署名
ｒ≡ｘ（ｍｏｄｎ）となる。次に署名ｓを求めるステップ７０６〜７１３に進む。
ステップ７０６：剰余乗算器１０７のＣＤＢに、ＥＥＰＲＯＭ１０４に記憶させておいたＲ２ｍｏｄｎを記憶させる。
ステップ７０７：剰余乗算器１０７を用いて剰余演算１を実行する。この演算結果であるｒＲｍｏｄｎの値が、ＣＤＡに保持される。
ステップ７０８：剰余乗算器１０７のＣＤＢに、ＥＥＰＲＯＭ１０４に記憶させておいた秘密鍵ｄを記憶させる。
ステップ７０９：剰余乗算器１０７を用いて剰余演算１を実行する。この演算結果であるｄ・ｒｍｏｄｎの値がＣＤＡに記憶される。
【００５０】
ステップ７１０：ＣＰＵ１０２を用いて、メッセージＭに対するハッシュ値Ｈ（Ｍ）と、上記ステップ７０９で求めたｄ・ｒｍｏｄｎとの和を計算し、
（Ｈ（Ｍ）＋ｄ・ｒ）ｍｏｄｎの値をＲＡＭ１０６に記憶する。
ステップ７１１：逆元演算ｋ−１Ｒｍｏｄｎを剰余乗算器１０７を用いた剰余乗算ｋｎ−２Ｒｍｏｄｎにより計算する。この計算法は、図６におけるステップ６０１からステップ６０９までの処理を参照のこと。この演算結果
ｋ−１Ｒｍｏｄｎは、剰余乗算器１０７のＣＤＡに記憶される。
ステップ７１２：剰余乗算器１０７のＣＤＢにステップ７１０でＲＡＭ１０６に記憶しておいた（Ｈ（Ｍ）＋ｄ・ｒ）ｍｏｄｎの値を記憶する。
ステップ７１３：剰余乗算器１０７を用いて剰余演算１を実行する。この演算結果であるｋ−１・（Ｈ（Ｍ）＋ｄ・ｒ）ｍｏｄｎの値がCDAに記憶される。この値が署名ｓ≡ｋ−１・（Ｈ（Ｍ）＋ｄ・ｒ）（ｍｏｄｎ）となる。
ステップ７１４：終了
本発明の効果を確認するために、上記実施例に従ったプログラムを作成して、ＣＰＵの動作クロック数が５ＭＨｚにおける実行時間を測定した。
具体的には、１６０ビット鍵長の楕円曲線上のｋ・Ｐ演算を、３次元射影座標系において、それぞれがベースポイントの４のべき乗倍の点の値を示す８０個の参照テーブルを用いて行い、さらに逆元計算をフェルマーの小定理とバイナリ演算法とを組み合わせて行うように構成した。実行環境には、日立製作所製の多倍長剰余乗算コプロセッサ内蔵ＩＣカード用マイコンＨ８／３１１１エミュレータを使用し、プログラム言語として、アセンブラを用いた。この結果、１６０ビット鍵長の楕円曲線暗号による署名作成時間（ステップ２０１からステップ２０６までにかかった時間）は、０．３０８秒／署名となった。
【００５１】
以上述べたように、本発明によれば、剰余乗算、剰余除算は、剰余乗算器を用いて行い、その他の剰余加算、剰余減算はＣＰＵを用いて行ない、また、事前に計算した値を参照することで、楕円曲線暗号を高速に処理することができる。
なお、上記説明では、ディジタル署名作成処理を中心に説明したが、これに限定されず、同様の方法により、楕円曲線暗号を用いた署名検証処理、暗号作成処理をも高速に行うことができる。
また、上記説明で述べた、逆元演算を剰余乗算器を用いて、高速に処理する方法は、他の逆元演算を利用する各種公開鍵暗号、ディジタル署名方式、例えば、ＤＳＡ署名、Ｓｃｈｎｏｒｒ署名に対しても適用可能である。
【００５２】
また、本発明は、上記実施例のようなＩＣカードには限定されず、ＣＰＵの処理能力が限定されていて乗算器を備える同様の装置であれば、これを適用することができる。例えば認証処理を行うマイクロコントローラや暗号化処理のためのＩＥＥＥ１３９４ＬＳＩ等に適用できる。これらの用途はＮＩＫＫＥＩ  ＥＬＥＣＴＲＯＮＩＣＳ  １９９８．１２．１４（Ｎｏ．７３２）ｐｐ２７−２８にも記載されている。
【００５３】
また、本発明では、書き換え可能な不揮発メモリ１０４として、ＥＥＰＲＯＭを例に挙げたが、これに限定されることはなく、フラッシュメモリを使うことも可能である。また、ＲＯＭ１０３に於いてもフラッシュメモリを使うことができる。
図６に示すコプロセッサ１０７を用いて逆元演算を実現するモジュールは、ソフトウェアや半導体チップなどのハードウェア単体又は、それらの組み合わせ、いずれの形態でも実現でき、汎用/専用を問わず用途は広いことが理解されよう。
【００５４】
【発明の効果】
以上説明したように、本発明によって、楕円曲線に基づいたディジタル署名作成処理を剰余乗算演算を効果的に利用する方法を用いて構成したことにより、剰余乗算器を具えた装置において高速に処理可能な方法及び装置を提供できる。
【図面の簡単な説明】
【図１】本発明が適用される装置のブロック図である。
【図２】本発明の一実施例における楕円曲線暗号による署名作成手順を示すフローチャートである。
【図３】図２のステップ２０３における処理の詳細なフローチャートである。
【図４】図３における楕円加算演算の詳細なフローチャートである。
【図５】図３における楕円２倍演算の詳細なフローチャートである。
【図６】図２のステップ２０４における処理の詳細なフローチャートである。
【図７】図２のステップ２０６における処理のフローチャートである。
【符号の説明】
１０１…ＩＣカード、
１０２…ＣＰＵ、
１０３…ＲＯＭ、
１０４…ＥＥＰＲＯＭ、
１０５…Ｉ／Ｏポート、
１０６…ＲＡＭ、
１０７…剰余乗算器、
１０８…バス、
１０９…ＣＰＵ・剰余乗算器共通ＲＡＭ、
１１０…電源（Ｖｃｃ）端子、
１１１…グランド（Ｖｓｓ）端子、
１１２…クロック（ＣＬＫ）端子、
１１３…リセット（ＲＥＳ）端子、
１１４…Ｉ／Ｏ端子。
【図１】
0003779479.tif 000002
【図２】
0003779479.tif 000003
【図３】
0003779479.tif 000004
【図４】
0003779479.tif 000005
【図５】
0003779479.tif 000006
【図６】
0003779479.tif 000007
【図７】
0003779479.tif 000008