JP4502817B2 - Elliptic curve scalar multiplication method and apparatus - Google Patents

Description

  The present invention relates to security technology, and more particularly to a message processing method using elliptic curve calculation.

を計算することにより得られる。ここで、ワイエルシュトラス型楕円曲線の定義式は

で与えられる。すなわち、式３のｘ，ｙに各々ｘ_ｉ，ｙ_ｉ（ｉ＝１，２，３）を代入した場合に、式３の等式が成り立つ。
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ_１，ｙ_１）の２倍算
（ｘ_３，ｙ_３）＝２（ｘ_１，ｙ_１）＝（ｘ_１，ｙ_１）＋（ｘ_１，ｙ_１）は

を計算することにより得られる。
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
楕円曲線上の離散対数問題の求解の困難性が理論的に確立されてきている一方で、実際の実装においては秘密鍵等の秘密情報に関連する情報（計算時間や電力消費量など）が暗号処理において漏洩する場合があり、その漏洩情報をもとに秘密情報を復元するといった、サイドチャネル攻撃という攻撃法が提案されている。
楕円曲線暗号に対するサイドチャネル攻撃が、Ｊ．Ｃｏｒｏｎ，Ｒｅｓｉｓｔａｎｃｅ ａｇａｉｎｓｔ Ｄｉｆｆｅｒｅｎｔｉａｌ Ｐｏｗｅｒ Ａｎａｌｙｓｉｓ ｆｏｒ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，Ｃｒｙｐｔｏｇｒａｐｈｉｃ Ｈａｒｄｗａｒｅ ａｎｄ Ｅｍｂｅｄｄｅｄ Ｓｙｓｔｅｍｓ： Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ＣＨＥＳ’９９，ＬＮＣＳ １７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９９）ｐｐ．２９２−３０２．（文献１）に記載されている。
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の作成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
楕円曲線暗号に対するサイドチャネル攻撃の防御法が、Ｂ．Ｍｏｅｌｌｅｒ，Ｓｅｃｕｒｉｎｇ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｐｏｉｎｔ Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ ａｇａｉｎｓｔ Ｓｉｄｅ−Ｃｈａｎｎｅｌ Ａｔｔａｃｋｓ，Ｉｎｆｏｒｍａｔｉｏｎ Ｓｅｃｕｒｉｔｙ（ＩＳＣ２００１），ＬＮＣＳ ２２００，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（２００１），ｐｐ．３２４−３３４．（文献２）に記載されている。Elliptic curve cryptography Koblitz, V .; S. It is a kind of public key cryptography proposed by Miller. Public key cryptography includes information that can be disclosed to the public called a public key and secret information that must be kept secret, called a secret key. A public key is used for encryption of a given message and signature verification, and a secret key is used for decryption of a given message and creation of a signature.
The secret key in elliptic curve cryptography is a scalar value. The security of elliptic curve cryptography is derived from the difficulty of solving the discrete logarithm problem on the elliptic curve. The discrete logarithm problem on an elliptic curve is a problem of obtaining a scalar value d when a certain point P on the elliptic curve and a point dP that is a scalar multiple thereof are given.
A point on an elliptic curve is a set of numbers that satisfy the definition equation of the elliptic curve. Addition (or addition) is defined. The addition on the elliptic curve by the same points is particularly called doubling on the elliptic curve.
The addition of two points on the elliptic curve is calculated as follows. When a straight line passing through two points is drawn, the straight line intersects the elliptic curve at another point. The intersecting point and a point that is symmetric with respect to the x-axis are taken as points resulting from the addition. For example, in the case of a Weierstrass-type elliptic curve, the addition of the point (x ₁ , y ₁ ) and the point (x ₂ , y ₂ ) (x ₃ , y ₃ ) = (x ₁ , y ₁ ) + ( x ₂ , y ₂ ) is

Is obtained by calculating. Here, the defining formula of the Weierstrass-form elliptic curve is

Given in. That is, when x _i and y _i (i = 1, 2, 3) are substituted for x and y in Equation 3, the equation of Equation 3 is established.
The doubling of the points on the elliptic curve is calculated as follows. When a tangent at a point on the elliptic curve is drawn, the tangent intersects at another point on the elliptic curve. The intersecting point and a point that is symmetric with respect to the x-coordinate are taken as the result of doubling. For example, in the case of a Weierstrass-form elliptic curve, the point _(x 1, _{y 1)} of the doubling _{(x 3, y 3) =} 2 (x 1, y 1) = (x 1, y 1) + (X ₁ , y ₁ ) is

Is obtained by calculating.
Adding a certain number of times to a certain point is called scalar multiplication, the result is called a scalar multiple, and the number of times is called a scalar value.
While the difficulty of solving the discrete logarithm problem on an elliptic curve has been theoretically established, information related to secret information such as a secret key (calculation time, power consumption, etc.) is encrypted in an actual implementation. An attack method called a side channel attack has been proposed in which there is a case of leaking in processing, and secret information is restored based on the leaked information.
Side channel attacks against elliptic curve cryptography are Coron, Resistance against Differential Power Analysis for Elliptic Curve Cryptoysystems, Cryptographic Hardware and Embeded Systems 99, Proceedings 17: Proceeding. 292-302. (Reference 1).
In elliptic curve cryptography, encryption, decryption, signature generation or verification of a given message must be performed using elliptic curve computation. In particular, calculation of scalar multiplication on an elliptic curve is used in cryptographic processing using a scalar value that is secret information.
A side channel attack defense method against elliptic curve cryptography is Moeller, Securing Elliptic Curve Point Multiplication Against Side-Channel Attacks, Information Security (ISC2001), LNCS 2200, Springer-Verlag, (2001). 324-334. (Reference 2).

Cryptographic technology has become an indispensable element for concealing and authenticating electronic information with the development of information and communication networks. Therefore, it is desired to reduce the resources used such as memory as well as the security of encryption technology. Since the discrete logarithm problem on the elliptic curve is very difficult, the elliptic curve cryptography can make the key length relatively short compared to the cryptography based on the difficulty of prime factorization. Therefore, it is possible to perform encryption processing with relatively few resources. However, a smart card (also referred to as an IC card) having a small amount of memory is not always satisfactory. Therefore, cryptographic processing that can be executed with a small amount of memory is required.
Although the above technique is effective as a method for preventing side channel attacks, it does not take into consideration the reduction in memory usage.
The present invention provides an elliptic curve calculation method that can prevent a side channel attack and that uses a small amount of memory.
The present invention further provides an encryption processing method, a decryption processing method, a signature creation method, a signature verification method, and a data sharing method using the above elliptic curve calculation method.
The present invention provides a scalar multiple calculation method for calculating a scalar multiple from a scalar value and a point on an elliptic curve in an elliptic curve calculation, the step of encoding the scalar value into a numerical sequence, and a point on the elliptic curve And a step of calculating a scalar multiple from the encoded numerical sequence and the previous calculation table.
The present invention may also be configured such that the numerical sequence output from the encoding step consists of 0 and an odd number.
In the present invention, the step of calculating the scalar multiple includes a step of executing the first operation a predetermined number of times and a step of executing a second operation different from the first operation. You may comprise as follows.
The present invention also provides a scalar multiplication calculation method for calculating a scalar multiple from a pre-calculation table storing a scalar value and an odd multiple of a point on the elliptic curve in an elliptic curve calculation, wherein the scalar value is a numerical sequence. And a step of calculating a scalar multiple from the encoded numerical sequence and the pre-calculation table, and the numerical sequence output from the encoding step may be composed of 0 and an odd number. Good.
As described above, according to the scalar multiplication calculation method of the present invention, only odd-numbered points are stored in the pre-calculation table, and the scalar value is encoded to use only odd-numbered points, thereby preventing side channel attacks. It is possible to use a scalar multiplication method with a small memory usage.

FIG. 1 is a system configuration diagram according to the embodiment.
FIG. 2 is a sequence diagram showing information delivery in each embodiment.
FIG. 3 is a configuration diagram of the scalar multiplication calculator in the embodiment.
FIG. 4 is a flowchart showing an encoding method performed by the encoding unit.
FIG. 5 is a flowchart showing a pre-calculation method performed by the pre-calculation unit.
FIG. 6 is a flowchart showing an actual calculation method performed by the actual calculation unit.
FIG. 7 is a configuration diagram of a signature verification system in the embodiment.

を計算して出力すればよい。ここでＰ_ｍはメッセージ、ｋは乱数、ａは秘密鍵を示す定数、Ｑは定点、ａＱは公開鍵を示す点である。
ネットワーク１４２には、Ｐ_ｍ＋ｋ（ａＱ），ｋＱのみ送信され、メッセージＰ_ｍを復元するためには、ｋａＱ、すなわちｋＱのａ倍を計算する必要がある。ところが、秘密鍵ａはネットワーク１４２には送信されないため、秘密鍵ａを保持しているものだけが、Ｐ_ｍを復元できることになる。
図１において、コンピュータＡ１０１は、ＣＰＵ１１３やコプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース１１０を装備しており、外部にはコンピュータＡ１０１をユーザが操作するためのディスプレイ１０８、キーボード１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
更にコンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、データ処理部１１２、スカラー倍計算部１１５を実現する。
データ処理部１１２は、本実施形態においては、暗号化処理部１１２として機能し、入力されたメッセージの暗号化を行う。
スカラー倍計算部１１５は、暗号処理部１１２で暗号化を行うのに必要なパラメタを計算する。記憶部１０２は、定数１０４（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報１０５（例えば、秘密鍵である。）などを記憶している。
コンピュータＢ１２１は、コンピュータＡ１０１と同様のハードウェア構成を備える。
更にコンピュータＢ１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１０７などの記憶装置によって、記憶部１２２を実現し、ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納されたプログラムを実行することにより、データ処理部１３２、スカラー倍計算部１３５を実現する。
データ処理部１３２は、本実施形態においては、復号化処理部１３２として機能し、暗号化されたメッセージである暗号文１４１の復号化を行う。
スカラー倍計算部１３５は、復号化処理部１３２で復号化を行うのに必要なパラメタを計算する。記憶部１２２は、定数１２４（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報１２５（例えば、秘密鍵である。）などを記憶している。
なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース１１０と上記コンピュータ７２１が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース１１０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
図２は、コンピュータＡ１０１、コンピュータＢ１２１の各処理部が行う情報の受け渡しの様子を示したものである。
次に、図１のコンピュータＡ１０１が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであれば良く、テキスト、画像、映像、音などの種類は問わない。
暗号化処理部１１２は、入出力インタフェース１１０を介して、平文メッセージ（図２の入力メッセージ２０４）を受け取ると、入力された平文メッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文メッセージを区切る。以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。
次に、暗号化処理部１１２は、メッセージのビット列によって表される数値をｘ座標（ｘ_１）にもつ楕円曲線上の点Ｐ_ｍのｙ座標の値（ｙ_１）を計算する。
例えば、ワイエルシュトラス型楕円曲線は、Ａ，Ｂをそれぞれ定数とするとき、

で表されるので、これよりｙ座標の値を求めることができる。
次に、暗号化処理部１１２は、乱数ｋを生成する。そして、記憶部１０２に格納されている定数１０４から読み出した（図２の２０５）公開鍵ａＱとＱのｘ座標と、求めたｙ座標の値と乱数ｋとをスカラー倍計算部１１５へ送る（図２の２０６）。
スカラー倍計算部１１５は、Ｑのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘ_ｄ１，ｙ_ｄ１）＝ｋＱと、公開鍵ａＱのｘ座標、ｙ座標の値、乱数によるスカラー倍点（ｘ_ｄ２，ｙ_ｄ２）＝ｋ（ａＱ）とを計算し、計算されたスカラー倍点を暗号化処理部１１２へ送る（図２の２０７）。
暗号化処理部１１２は、送られたスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型の楕円曲線については、Ｐ_ｍ＋ｋ（ａＱ）とｋＱを計算する。すなわち、

を計算し、暗号化されたメッセージｘ_ｅ１，ｘ_ｅ２を得る。
コンピュータＡ１０１は暗号化処理部１１２で暗号化された１つ以上の部分メッセージから暗号化された出力メッセージを組み立てる（図２の２０８）。
コンピュータＡ１０１は、暗号化された出力メッセージをデータ１４１として入出力インタフェース１１０より出力し、ネットワーク１４２を介してコンピュータＢ１２１へ転送する。
なお、図２の記憶部１０２からの情報読み出しは、スカラー計算部１１５へ当該情報を送る前で有れば、入力メッセージを受け付ける前であっても良い。
次に、コンピュータＢ１２１が、暗号化されたメッセージ１４１を復号化する場合の動作について、図２を参照しつつ説明する。
復号化処理部１３２（図２のデータ処理部１１２）は、入出力インタフェース１１０を介して、暗号化されたデータ１４１（図２の入力メッセージ２０４）が入力されると、入力された暗号化されたデータ１４１のビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように暗号化されたデータを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。
データ１４１のビット列によって表される数値をｘ座標にもつ楕円曲線上のｙ座標の値を計算する。
暗号化されたメッセージがｘ_ｅ１，ｘ_ｅ２のビット列であり、ワイエルシュトラス型楕円曲線の場合、ｙ座標の値（ｙ_ｅ１）は

（ただし、Ａ，Ｂはそれぞれ定数である）
から得ることができる。
復号化処理部１３２は、記憶部１２２（図２の１０２）に格納されている秘密情報１２５から読み出した（図２の２０５）秘密鍵ａと、ｘ座標、ｙ座標の値（ｘ_ｅ１，ｙ_ｅ１）を、スカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部１３５は、ｘ座標、ｙ座標の値、秘密情報ａ１２５からスカラー倍点（ｘ_ｄ３，ｙ_ｄ３）＝ａ（ｘ_ｅ２，ｙ_ｅ２）を計算する。スカラー倍計算部１３５は、計算されたスカラー倍点を復号化処理部１３２へ送る（図２の２０７）。復号化処理部１３２は、送られたスカラー倍点を用いて、復号化処理を行う。
例えば、暗号化されたメッセージが、ｘ_ｅ１，ｘ_ｅ２のビット列であり、ワイエルシュトラス型の楕円曲線の場合は、
（Ｐ_ｍ＋ｋ（ａＱ））−ａ（ｋＱ）＝（ｘ_ｅ１，ｙ_ｅ１）−（ｘ_ｄ３，ｙ_ｄ３）
を計算することにより達成する。すなわち、

を計算し、暗号化される前の部分メッセージｘ_１に相当するｘ_ｆ１を得る。
コンピュータＢ１２１は、復号化処理部１３２で復号化された部分メッセージから平文メッセージを組み立て（図２の２０８）、入出力インタフェース１１０を介して、ディスプレイ１０８などから出力する。
次に、コンピュータＢ１２１が、復号化処理を行う場合の、スカラー倍計算部１３５の処理を詳細に説明する。
図３は、各実施例で用いるスカラー倍計算部の機能ブロックを示したものである。スカラー倍計算部１１５（図１の１３５）は、エンコード部３０２、前計算部３０３、実計算部３０４からなる。エンコード部３０２は、剰余取得部３２１、剰余変換判定部３２２、剰余変換部３２３、繰り返し判定部３２４、格納部３２５からなる。前計算部３０３は、加算部３３１、２倍算部３３２、繰り返し判定部３３３からなる。実計算部３０４は、ビット値判定部３４１、加算部３４２、２倍算部３４３、繰り返し判定部３４４からなる。
スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する方法を説明する。
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部３０２は、入力されたスカラー値ｄを数値列ｄ_ｗ［ｊ］にエンコードする。すなわち、

をみたすｄ_ｗ［ｊ］に、スカラー値ｄを変換する。ここで、ｗはあらかじめ定めた小さな正整数で、ウィンドウ幅と呼ばれる。計算時間を優先する場合はｗを大きな値とする。メモリ使用量を小さくする場合はｗを小さな値にする。前計算部３０３は、入力された楕円曲線上の点Ｐから前計算テーブルを作成する。前計算テーブルはＰ，３Ｐ，．．．，（２^ｗ−１）Ｐにより構成される。実計算部３０４は、エンコードされたスカラー値と前計算テーブルを用いてスカラー倍点ｄＰを計算する。
なお、エンコード部３０２の行うエンコード処理は、スカラー値ｄを受け取った後、および実計算部３０４がスカラー倍点を計算する前であればよい。すなわち、前計算部３０３が前計算テーブルを作成する前に行っても、後に行なってもよい。
また、点Ｐが固定点である場合、前計算部３０３の行う前計算テーブルの作成処理は、ただ一度行えばよい。すなわち、一旦前計算テーブルを作成すれば、それ以降のスカラー倍計算では前計算テーブルを再作成する必要はない。
次にエンコード部３０２、前計算部３０３、実計算部３０４の行なう各処理について詳細に説明する。
まず、図４を用いて、エンコード部３０２がスカラー値ｄをエンコードする方法を説明する。
変数ｉに初期値０を、変数ｄ’にスカラー値ｄをそれぞれ代入する（４０１）。
剰余取得部３２１は、スカラー値ｄ’の２^ｗによる剰余をｕ［ｉ］に格納する（４０２）。
剰余取得部３２１は、（ｄ’−ｕ［ｉ］）／２^ｗを計算し、それを新たなｄ’とする（４１１）。
変数ｉを１増加させる（４１２）。
繰り返し判定部３２４は、変数ｉとｋが一致するかどうかを判定する。
一致すればステップ４２１へ行く。一致しなければステップ４１４へ行く（４１３）。
剰余取得部３２１は、ｄ’の２^ｗによる剰余をｕ［ｉ］に格納する（４１４）。
剰余変換判定部３２２は、ｕ［ｉ］が偶数か奇数かを判定する。
ｕ［ｉ］が偶数の場合はステップ４１６へ行く。奇数の場合はステップ４１７へ行く（４１５）。
剰余変換部３２３は、ｕ［ｉ］が奇数となるように、
ｕ［ｉ］，ｕ［ｉ−１］を変換する（４１６）。これは、

の操作を行なうことにより達成される。ここで、ｓｉｇｎ（ｕ）はｕの符号を取り出す関数であり、ｕが正の時は１、ｕが負の時は−１となる。
格納部３２５は、
ｄ_ｗ［（ｉ−１）ｗ］，ｄ_ｗ［（ｉ−１）ｗ＋１］，．．．，ｄ_ｗ［（ｉ−１）＋ｗ−１］にそれぞれ、ｕ［ｉ−１］，０，…，０を格納し、ステップ４１１へ戻る（４１７）。
ステップ４１３で変数ｉとｋが一致した場合、格納部３２５はｄ_ｗ［ｋｗ］，ｄ_ｗ［ｋｗ＋１］，．．．，ｄ_ｗ［ｋｗ＋ｗ−１］にそれぞれ、ｕ［ｋ］，０，…，０を格納する（４２１）。
エンコード部３０２は、ｄ_ｗ［ｎ］，ｄ_ｗ［ｎ−１］，．．．，ｄ_ｗ［０］を実計算部３０４へ出力する（４２２）。
次に、図５を用いて、前計算部３０３が楕円曲線上の点から、前計算テーブルを作成する方法を説明する。
点ＰをＥＣＤＢＬにより２倍し、その結果を点２Ｐに格納する（５０１）。
変数ｊに初期値１を代入する（５０２）。
ｊが２^ｗ−１より小さいかどうかを判定する。ｊが２^ｗ−１より小さい場合はステップ５０４へ行く。２^ｗ−１以上の場合はステップ５１１へ行く（５０３）。
ステップ５０３でｊが２^ｗ−１より小さい場合、点２Ｐと点（２ｊ−１）ＰをＥＣＡＤＤにより加算し、その結果を点（２ｊ＋１）Ｐに格納する（５０４）。
変数ｊを１増加させ、ステップ５０３へ戻る（５０５）。
ステップ５０３でｊが２^ｗ−１以上の場合、Ｐ，３Ｐ，．．．，（２^ｗ−１）Ｐを前計算テーブルとして出力する（５１１）。
ただし、ＥＣＡＤＤ，ＥＣＤＢＬはそれぞれ楕円曲線における加算、２倍算を表す。加算は式１，２を用いて、２倍算は式４，５を用いてそれぞれ計算される。なお、加算、２倍算の計算には式１，２、および式４，５を用いる以外にも、射影座標やヤコビアン座標における計算公式があり、Ｃｏｈｅｎ，Ｈ．，Ｍｉｙａｊｉ，Ａ．，Ｏｎｏ，Ｔ．，Ｅｆｆｉｃｉｅｎｔ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ Ｕｓｉｎｇ Ｍｉｘｅｄ Ｃｏｏｒｄｉｎａｔｅｓ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ １９９８，ＬＮＣＳ １５１４，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９８），ｐｐ．５１−６５．（文献３）に記載されている。
また、楕円曲線上の点Ｑ＝（ｘ，ｙ）に対して、楕円曲線加算に関する逆元の点−Ｑは、−Ｑ＝（ｘ，−ｙ）と表されるため、点Ｑの座標が与えられていれば容易に計算できる。そのため、点Ｐ，３Ｐ，…，（２^ｗ−１）Ｐのみを前計算テーブルとして格納する。その後の実計算部３０４が行う計算で必要となる点−Ｐ，−３Ｐ，…，−（２^ｗ−１）Ｐは、それらから導出すればよく、前計算テーブルには格納する必要はない。
なお、前計算部３０３の行う前計算テーブルの作成処理は、点Ｐ，３Ｐ，…，（２^ｗ−１）Ｐが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
モンゴメリトリックによる逆元演算共通化方法がＣｏｈｅｎ，Ｈ．，Ａ ｃｏｕｒｓｅ ｉｎ ｃｏｍｐｕｔａｔｉｏｎａｌ ａｌｇｅｂｒａｉｃ ｎｕｍｂｅｒ ｔｈｅｏｒｙ，ＧＴＭ１３８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９３）．（文献４）の４８１ページに記載されている。
最後に、図６を用いて、実計算部３０４がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
変数ｃに初期値ｎを代入する（６０１）。
ｄ_ｗ［ｃ］が０か０でないかを判定する。
ｄ_ｗ［ｃ］が０の場合はステップ６０３へ行く。０でなければステップ６１１へ行く（６０２）。
変数ｃを１減少させ、ステップ６０２へ戻る（６０３）。
ステップ６０２でｄ_ｗ［ｃ］が０でない場合、点Ｑにｄ_ｗ［ｃ］Ｐを代入する（６１１）。
変数ｊに初期値ｃ−１を代入する（６１２）。
ｊが０より小さいかどうかを判定する。ｊが０より小さい場合はステップ６２１へ行く。０以上の場合はステップ６１４へ行く（６１３）。
点ＱをＥＣＤＢＬにより２倍し、点Ｑに再び格納する（６１４）。
ｄ_ｗ［ｊ］が０か０でないかを判定する。
ｄ_ｗ［ｊ］が０の場合はステップ６１７へ行く。０でなければステップ６１６へ行く（６１５）。
ステップ６１５でｄ_ｗ［ｊ］が０でない場合、点Ｑとｄ_ｗ［ｊ］ＰとをＥＣＡＤＤにより加算する。ただし、ｄ_ｗ［ｊ］が負の場合は（−ｄ_ｗ［ｊ］）Ｐのｙ座標を反転したものを用いて加算を行う。その結果を点Ｑに格納し、ステップ６１７へ行く（６１６）。なお、ｄ_ｗ［ｊ］が０でない場合は、ｄ_ｗ［ｊ］は奇数である。そのため、ｄ_ｗ［ｊ］Ｐもしくは（−ｄ_ｗ［ｊ］）Ｐのいずれかが、前計算テーブルに必ず存在する。
変数ｊを１減少させ、ステップ６１３へと戻る（６１７）。
ステップ６１３でｊが０より小さい場合、点Ｑを出力する（６２１）。
エンコード部３０２が行う処理により出力されるｄ_ｗ［ｊ］は、式１２，式１３をみたす。この理由は次の通りである。
ｄ_ｗ［ｊ］はｊがｗで割り切れる時はｕ［ｊ／ｗ］に等しく、割り切れない場合は０に等しい。そのため、式１２の右辺は、

と等しい。ただし、ｋ＝ｎ／ｗである。一方、ステップ４１６の変換では、

の値は不変である。したがって、ステップ４１６の変換で、式１７の値は不変である。他方、スカラー値ｄを２^ｗ−進展開したものがｕ［ｉ］の初期状態であるので、式１７はｄに等しい。ゆえに式１２がみたされる。また、ステップ４１６の変換では、

をみたすｕ［ｉ］は、変換後も式１９をみたす。したがって、式１３がみたされる。
エンコード部３０２が行う処理で計算されるｕ［ｉ］はｉ＝０を除き全て奇数となる。この理由は次の通りである。ステップ４１５でｕ［ｉ］が奇数であれば、ｕ［ｉ］の値はそのまま保持されるので、ｕ［ｉ］は奇数である。ステップ４１５でｕ［ｉ］が偶数であれば、ステップ４１６でｕ［ｉ］，ｕ［ｉ−１］は式１５，１６により変換される。式１４によりｂの値が計算されるため、ｂは１もしくは−１である。そのため、式１５の変換で、ｕ［ｉ］は奇数に変換される。また、式１６の変換では、ｕ［ｉ−１］の偶奇性は変化しない。ステップ４１５に初めて来る時のｉは１である。そのため、ｕ［０］は奇数とは限らない。結果として、ｉ＝０を除き、ｕ［ｉ］は全て奇数である。
なお、ｕ［０］も奇数とするためには、スカラー値ｄが奇数であればよい。そのためには、入力されたすカラー値ｄが偶数の時は、ｄ＋１を改めてスカラー値ｄ’としてエンコードする。すなわち、ｄを奇数に変換する。そして、スカラー倍点ｄ’Ｐを計算する。

であるので、ｄ’Ｐから点Ｐを引き、その値をスカラー倍点ｄＰとして出力すればよい。
実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
ステップ６１３において点Ｑが

と表されるとする。このとき、次にステップ６１３に来る時も点Ｑは式２１をみたすことを示す。
点Ｑはステップ６１４で２倍され、ｄ_ｗ［ｊ］が０でなければステップ６１６でｄ_ｗ［ｊ］Ｐが加えられる。そのためステップ６１６の直後では、点Ｑの値は

となる。したがってｄ_ｗ［ｊ］＝０の時も含めて、ステップ６１７の直前で、点Ｑは式２２をみたす。ステップ６１７でｊが１減少するので、式２２のｊにｊ＋１を代入すると式２１になる。すなわち、次にステップ６１３に来る時も点Ｑは式２１をみたす。
ｊ＞ｃに対するｄ_ｗ［ｊ］の値は０であるので、ステップ６２１で出力される点Ｑの値は

に等しい。実計算部３０４に入力されるスカラー値は、エンコード部３０２によりエンコードされたｄ_ｗ［ｊ］であるので、そのｄ_ｗ［ｊ］は式１２をみたす。したがって、Ｑ＝ｄＰである。
上記スカラー倍におけるメモリ使用量は、前計算部３０３の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルはＰ，３Ｐ，…，（２^ｗ−１）Ｐのみ、すなわち奇数倍の点のみを格納すればよいので、その点の数は２^ｗ−１個である。文献２の方法では、ウィンドウ幅ｗに対して、２^ｗ個の点を格納する必要がある。そのため、上記スカラー倍計算方法は、文献２の方法と比べて格納する点の数が少なく、メモリ使用量が小さくてすむ。
さらに、いかなる方法をもってしても、前計算テーブルに格納する点の数をこれ以上削減することができないという意味で、メモリ使用量は最小である。この理由は次の通りである。
ｍ個の点からなる前計算テーブルを用いた場合、ｋ＋１個のｕ［ｉ］を用いて、エンコードされたスカラー値として表すことのできる数は（２ｍ）^ｋ＋１個である。他方、ｎビット以下のスカラー値は全部で２^ｎ個あり、各々のスカラー値はそれぞれ異なる数値列にエンコードされなければならない。そのため、（２ｍ）^ｋ＋１≧２^ｎが成り立つ。ｋ＋１＝ｎ／ｗであるので、ｍ≧２^ｗ−１となる。実際、上記スカラー倍計算方法における前計算テーブルの点の個数は２^ｗ−１であり、最小である。
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
エンコード部３０２によりスカラー値ｄは数値列ｄ_ｗ［ｊ］にエンコードされる。この数値列ｄ_ｗ［ｊ］は固定されたパターン

をもつ。ここで各ｘは各々非０の値であり、それぞれｄ_ｗ［ｉｗ］に対応する。そのため、実計算部３０４がスカラー倍点を計算する際に、ステップ６１３−６１７の繰り返し処理において、｜０…０ｘ｜のブロックに対応する楕円曲線演算は、｜Ｄ…ＤＡ｜、すなわちｗ回のＤの後にＡとなる。ただし、ＤはＥＣＤＢＬを、ＡはＥＣＡＤＤをそれぞれ表す。したがって、全てのスカラー値に対して、実行する楕円曲線演算は、

となり、必ず楕円加算が実行されるので、スカラー値との依存関係がない。
なお、文献１のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Ｐを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
また、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
以上の通り、上記計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、奇数倍の点のみを前計算テーブルとして格納するため、メモリ使用量が小さくてすむという特徴がある。
なお、上記計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数２の有限体上で定義された楕円曲線や、ＯＥＦ（Ｏｐｔｉｍａｌ Ｅｘｔｅｎｓｉｏｎ Ｆｉｅｌｄ）上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。ＯＥＦについては、Ｄ．Ｖ．Ｂａｉｌｅｙ，Ｃ．Ｐａａｒ，Ｏｐｔｉｍａｌ Ｅｘｔｅｎｓｉｏｎ Ｆｉｅｌｄｓ ｆｏｒ Ｆａｓｔ Ａｒｉｔｈｍｅｔｉｃ ｉｎ Ｐｕｂｌｉｃ−Ｋｅｙ Ａｌｇｏｒｉｔｈｍｓ，Ａｄｖａｎｃｅｓ ｉｎ Ｃｒｙｐｔｏｌｏｇｙ Ｃｒｙｐｔｏ ’９８，ＬＮＣＳ １４６２，（１９９８），４７２−４８５．（文献５）に記載されている。
以上、コンピュータＢ１２１が、暗号化されたデータ１４１を復号化する場合のスカラー倍計算部１３５の動作を説明したが、コンピュータＡ１０１が入力メッセージを暗号化する場合も同様である。
その場合には、コンピュータＡ１０１のスカラー倍計算部１１５は、既に説明した楕円曲線上の点Ｑ、乱数ｋによるスカラー倍点ｋＱと、公開鍵ａＱと乱数ｋによるスカラー倍点ｋ（ａＱ）を出力する。このとき、上記計算方法で説明したスカラー値ｄを乱数ｋ、楕円曲線上の点Ｐを楕円曲線上の点Ｑ、公開鍵ａＱとして同様の処理を行うことにより、それぞれのスカラー倍点を求めることができる。
次に本発明を署名検証システムに適用する実施例を、図７と図２を用いて説明する。
図７の署名検証システムは、スマートカード７０１と署名検証処理を行うコンピュータ７２１とから成る。
スマートカード７０１は、機能としてはコンピュータＡ１０１と類似の構成を備えるが、ＣＰＵ１１３やコプロセッサ１１４などの演算装置とが記憶部１０２に格納されているプログラムを実行することにより、データ処理部１１２ではなく、署名生成処理部７１２を実現する。ただし、外部記憶装置、ディスプレイ、キーボードを備えない。
コンピュータ７２１は、コンピュータＡ１０１と同様の構成を備えるが、ＣＰＵ１１３がプログラムを実行することによりデータ処理部１１２ではなく、署名検証処理部７３２を実現する。
スカラー倍計算部７１５と７３５は、図１に示すスカラー倍計算部１１５または１３５と同様の機能を備える。
なお、本実施例において、コンピュータ７２１内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、コンピュータ７２１が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
さらに、スマートカード内の各プログラムは、あらかじめ、上記スマートカード内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。
媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
図７の署名検証システムにおける署名作成と署名検証動作を、図２を参照して説明する。
コンピュータ７２１は、ランダムに選んだ数値をチャレンジコード７４３として、インタフェース７４２を介してスマートカード７０１に転送する。
署名生成処理部７１２（図２の１１２）は、チャレンジコード７４３を受け付け、チャレンジコード７４３のハッシュ値をとり、所定のビット長の数値ｆに変換する。
署名生成処理部７１２は、乱数ｕを生成し、記憶部７０２（図２の１０２）に格納されている定数７０４から読み出した（図２の２０５）楕円曲線上の定点Ｑとともにスカラー倍計算部７１５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部７１５は、定点Ｑ、乱数ｕによるスカラー倍点（ｘ_ｕ，ｙ_ｕ）を計算し、計算されたスカラー倍点を署名生成処理部７１２へ送る（図２の２０７）。
署名生成処理部７１２は、送られたスカラー倍点を用いて署名の生成を行う。例えば、ＥＣＤＳＡ署名であれば、

を計算することによりチャレンジコード７４３に対応する署名（ｓ，ｔ）を得る（図２の２０８）。
ここで、ｑは定点Ｑの位数、すなわち定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
ＥＣＤＳＡ署名については、ＡＮＳＩ Ｘ９．６２ Ｐｕｂｌｉｃ Ｋｅｙ Ｃｒｙｐｔｏｇｒａｐｈｙ ｆｏｒ ｔｈｅ Ｆｉｎａｎｃｉａｌ Ｓｅｒｖｉｃｅｓ Ｉｎｄｕｓｔｒｙ，Ｔｈｅ Ｅｌｌｉｐｔｉｃ Ｃｕｒｖｅ Ｄｉｇｉｔａｌ Ｓｉｇｎａｔｕｒｅ Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ），（１９９９）（文献６）に記載されている。
スマートカード７０１は、署名生成処理部７１２で作成した署名７４１を入出力インタフェース７１０より出力し、インタフェース７４２を介してコンピュータ７２１へ転送する。
コンピュータ７２１の署名検証処理部７３２（図２の１１２）は、署名７４１が入力される（図２の２０４）と、署名７４１の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ，ｔ＜ｑであるかを調べる。
数値ｓ，ｔが上記範囲内になければチャレンジコード７４３に対する署名の検証結果として「無効」を出力し、スマートカード７０１を拒絶する。数値ｓ，ｔが上記範囲内にあれば、署名検証処理部７３２は、

を計算する。そして、記憶部７２２（図２の１０２）に格納されている定数７２４から読み出した（図２の２０５）公開鍵ａＱ及び定点Ｑと計算したｈ_１，ｈ_２をスカラー倍計算部７３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部７３５は、定点Ｑとｈ_１によるスカラー倍点ｈ_１Ｑと、公開鍵ａＱとｈ_２によるスカラー倍点ｈ_２ａＱとを計算し、計算されたスカラー倍点を署名検証処理部７３２へ送る（図２の２０７）。
署名検証処理部７３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡの署名検証であれば、点Ｒ

を計算し、そのｘ座標をｘ_Ｒとしたとき、

を計算し、ｓ’＝ｓであればチャレンジコード７４３に対する署名の検証結果として「有効」を出力し、スマートカード７０１を認証し、受け入れる（図２の２０８）。
ｓ’＝ｓでなければ「無効」を出力し、スマートカードを拒絶する（図２の２０８）。
上記実施形態のスカラー倍計算部７１５、７３５は、図１のスカラー倍計算部１１５または１３５と同様の機能を備えるので、サイドチャネル攻撃を防ぎ且つメモリ使用量の少ないスカラー倍計算を実行できる。
そのためスマートカード７０１は署名作成処理を行う際に、コンピュータ７２１は署名検証処理を行う際に、サイドチャネル攻撃を防ぎ、その上少ないメモリ使用量で実行できる。
次に本発明を鍵交換システムに適用する例を説明する。本実施形態においては、図１のシステム構成が応用できる。
図１のデータ処理部１１２、１３２は、本実施形態においては、それぞれ鍵交換処理部１１２、１３２として機能する。
鍵交換システムのコンピュータＡ１０１が、入力されたデータ１４３から共有情報の導出を行う場合の動作について図１、図２を参照して説明する。
コンピュータＢ１２１のデータ処理部１３２（図２の１１２）は、記憶部１２２（図２の１０２）の定数１２５から秘密鍵ｂを読み出しコンピュータＢ１２１の公開鍵ｂＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｂＱをデータ１４３としてコンピュータＡ１０１に転送する。
コンピュータＡ１０１の鍵交換処理部１１２（図２の１１２）はコンピュータＢ１２１の公開鍵ｂＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１１２は、記憶部１０２から読み出した（図２の２０５）秘密情報１０５であるコンピュータＡ１０１の秘密鍵ａと、コンピュータＢ１２１の公開鍵ｂＱとをスカラー倍計算部１１５へ送る（図２の２０６）。
スカラー倍計算部１１５は、秘密鍵ａと、公開鍵ｂＱによるスカラー倍点ａｂＱを計算し、計算されたスカラー倍点を鍵交換処理部１１２へ送る（図２の２０７）。
鍵交換処理部１１２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１０２に秘密情報１０５として格納する。例えば、スカラー倍点ａｂＱのｘ座標を、共有情報とする。
次に、コンピュータ１２１が、入力されたデータ１４１から共有情報の導出を行う場合の動作について説明する。
コンピュータＡ１０１のデータ処理部１１２は、記憶部１０２の定数１０５から秘密鍵ａを読み出しコンピュータＡ１０１の公開鍵ａＱを計算する。そして、ネットワーク１４２を介して、公開鍵ａＱをデータ１４１としてコンピュータＢ１２１に転送する。
コンピュータＢ１２１の鍵交換処理部１３２（図２の１１２）はコンピュータＡ１０１の公開鍵ａＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１３２は、記憶部１２２（図２の１０２）の定数１２５から読み出した（図２の２０５）秘密情報１２５であるコンピュータＢ１２１の秘密鍵ｂと、コンピュータＡ１０１の公開鍵ａＱとをスカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部１３５は、秘密鍵ｂと、公開鍵ａＱによるスカラー倍点ｂａＱを計算し、計算されたスカラー倍点を鍵交換処理部１３２へ送る（図２の２０７）。
鍵交換処理部１３２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１２２に秘密情報１２５として格納する。例えば、スカラー倍点ｂａＱのｘ座標を、共有情報とする。
ここで、数ａｂと数ｂａは数値として同じなので、点ａｂＱと点ｂａＱは同じ点となり、同じ情報が導出されたことになる。
ネットワーク１４２には、点ａＱと点ｂＱが送信されるが、点ａｂＱ（もしくは点ｂａＱ）を計算するには秘密鍵ａもしくは秘密鍵ｂを用いなければならない。すなわち、秘密鍵ａもしくは秘密鍵ｂを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
本実施形態においても、スカラー倍計算部１１５、１３５は、上述の特徴を備えるので、サイドチャネル攻撃を防ぎ、そのうえ少ないメモリ使用量で鍵交換処理が可能になる。
また、上記各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。
また、データ処理部は、上記暗号化処理、復号化処理、署名作成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
本発明によれば、サイドチャネル攻撃に対して安全で、かつメモリ使用量の少ない、楕円曲線演算を用いたメッセージ処理が可能になる。Embodiments of the present invention will be described below with reference to the drawings.
FIG. 1 shows a system configuration in which a computer A 101 and a computer B 121 to which an elliptic curve calculation method according to the present invention connected by a network 142 is applied are connected by a network 142.
In order to encrypt a message at the computer A101 in the cryptographic communication system of FIG. _m + K (aQ) and kQ are calculated and output, and in order to decrypt the ciphertext by the computer B121, -a (kQ) is calculated from the secret keys a and kQ,

Can be calculated and output. Where P _m Is a message, k is a random number, a is a constant indicating a secret key, Q is a fixed point, and aQ is a point indicating a public key.
Network 142 has P _m Only + k (aQ), kQ is sent and message P _m Is required to calculate kaQ, that is, a times kQ. However, since the secret key a is not transmitted to the network 142, only the one holding the secret key a is P _m Can be restored.
In FIG. 1, a computer A101 is equipped with an arithmetic device such as a CPU 113 and a coprocessor 114, a storage device such as a RAM 103, a ROM 106, and an external storage device 107, and an input / output interface 110 that performs data input / output with the outside of the computer. A display 108, a keyboard 109, and a removable portable storage medium read / write device for operating the computer A101 by the user are connected to the outside.
Further, the computer A101 realizes the storage unit 102 by a storage device such as the RAM 103, the ROM 106, and the external storage device 107, and an arithmetic device such as the CPU 113 or the coprocessor 114 executes the program stored in the storage unit 102. The data processing unit 112 and the scalar multiplication calculation unit 115 are realized.
In the present embodiment, the data processing unit 112 functions as the encryption processing unit 112 and encrypts the input message.
The scalar multiplication calculation unit 115 calculates parameters necessary for the encryption processing unit 112 to perform encryption. The storage unit 102 stores a constant 104 (for example, an elliptic curve definition formula or a fixed point on the elliptic curve), secret information 105 (for example, a secret key), and the like.
The computer B121 has the same hardware configuration as the computer A101.
Further, the computer B 121 implements the storage unit 122 by a storage device such as the RAM 123, ROM 126, and external storage device 107, and an arithmetic device such as the CPU 133 or the coprocessor 134 executes a program stored in the storage unit 122. The data processing unit 132 and the scalar multiplication calculation unit 135 are realized.
In the present embodiment, the data processing unit 132 functions as the decryption processing unit 132 and decrypts the ciphertext 141 that is an encrypted message.
The scalar multiplication calculator 135 calculates parameters necessary for the decoding processor 132 to perform decoding. The storage unit 122 stores a constant 124 (for example, an elliptic curve definition formula or a fixed point on the elliptic curve), secret information 125 (for example, a secret key), and the like.
Each program may be stored in advance in a storage unit in the computer, or when necessary, from other devices via a medium that can be used by the input / output interface 110 and the computer 721. It may be introduced into the storage unit. The medium refers to, for example, a storage medium that can be attached to and detached from the input / output interface 110, or a communication medium (that is, a network or a carrier wave that propagates through the network).
FIG. 2 shows how information is transferred by each processing unit of the computer A101 and the computer B121.
Next, an operation when the computer A101 in FIG. 1 encrypts an input message will be described. The message may be any digitized data, and may be any text, image, video, or sound.
When receiving the plaintext message (input message 204 in FIG. 2) via the input / output interface 110, the encryption processing unit 112 determines whether or not the bit length of the input plaintext message is a predetermined bit length. When the bit length is longer than a predetermined bit length, the plaintext message is divided so as to have a predetermined bit length. Hereinafter, a partial message (also simply referred to as a message) divided into a predetermined bit length will be described.
Next, the encryption processing unit 112 converts the numerical value represented by the bit string of the message into an x coordinate (x ₁ ) Point P on the elliptic curve _m Y coordinate value (y ₁ ).
For example, the Weierstrass-type elliptic curve has A and B as constants, respectively.

Therefore, the value of the y coordinate can be obtained from this.
Next, the encryption processing unit 112 generates a random number k. Then, the public key aQ and the x coordinate of Q read from the constant 104 stored in the storage unit 102 and the value of the obtained y coordinate and the random number k are sent to the scalar multiplication unit 115 (205). 206 in FIG.
The scalar multiplication calculation unit 115 calculates the value of the x coordinate of the Q, the value of the y coordinate, and the scalar multiple (x _d1 , Y _d1 ) = KQ, x coordinate of public key aQ, y coordinate value, scalar multiple (x _d2 , Y _d2 ) = K (aQ) and sends the calculated scalar multiple to the encryption processing unit 112 (207 in FIG. 2).
The encryption processing unit 112 performs encryption processing using the sent scalar multiple. For example, for the Weierstrass type elliptic curve, P _m + K (aQ) and kQ are calculated. That is,

Computes the encrypted message x _e1 , X _e2 Get.
The computer A101 assembles an encrypted output message from the one or more partial messages encrypted by the encryption processing unit 112 (208 in FIG. 2).
The computer A 101 outputs the encrypted output message as data 141 from the input / output interface 110 and transfers it to the computer B 121 via the network 142.
Note that the information read from the storage unit 102 in FIG. 2 may be performed before the input message is received as long as the information is transmitted to the scalar calculation unit 115.
Next, an operation when the computer B 121 decrypts the encrypted message 141 will be described with reference to FIG.
When the encrypted data 141 (input message 204 in FIG. 2) is input via the input / output interface 110, the decryption processing unit 132 (data processing unit 112 in FIG. 2) receives the input encrypted data. It is determined whether the bit length of the data 141 is a predetermined bit length. When the bit length is longer than the predetermined bit length, the encrypted data is divided so as to have the predetermined bit length. Hereinafter, partial data (also simply referred to as data) divided into a predetermined bit length will be described.
The value of the y coordinate on the elliptic curve having the numerical value represented by the bit string of the data 141 at the x coordinate is calculated.
The encrypted message is x _e1 , X _e2 In the case of a Weierstrass-type elliptic curve, the y coordinate value (y _e1 )

(However, A and B are constants)
Can be obtained from
The decryption processing unit 132 (205 in FIG. 2) read from the secret information 125 stored in the storage unit 122 (102 in FIG. 2) and the values of the x and y coordinates (x _e1 , Y _e1 ) Is sent to the scalar multiplication unit 135 (115 in FIG. 2) (206 in FIG. 2).
The scalar multiplication calculation unit 135 calculates the scalar multiple (x _d3 , Y _d3 ) = A (x _e2 , Y _e2 ). The scalar multiplication calculation unit 135 sends the calculated scalar multiplication point to the decoding processing unit 132 (207 in FIG. 2). The decoding processing unit 132 performs a decoding process using the sent scalar multiple.
For example, an encrypted message is x _e1 , X _e2 In the case of a Weierstrass-type elliptic curve,
(P _m + K (aQ))-a (kQ) = (x _e1 , Y _e1 )-(X _d3 , Y _d3 )
This is achieved by calculating That is,

And the partial message x before being encrypted ₁ X corresponding to _f1 Get.
The computer B 121 assembles a plaintext message from the partial message decrypted by the decryption processing unit 132 (208 in FIG. 2), and outputs it from the display 108 or the like via the input / output interface 110.
Next, the process of the scalar multiplication unit 135 when the computer B121 performs the decoding process will be described in detail.
FIG. 3 shows a functional block of the scalar multiplication unit used in each embodiment. The scalar multiplication calculation unit 115 (135 in FIG. 1) includes an encoding unit 302, a previous calculation unit 303, and an actual calculation unit 304. The encoding unit 302 includes a residue acquisition unit 321, a residue conversion determination unit 322, a residue conversion unit 323, a repetition determination unit 324, and a storage unit 325. The pre-calculation unit 303 includes an addition unit 331, a multiplication unit 332, and a repetition determination unit 333. The actual calculation unit 304 includes a bit value determination unit 341, an addition unit 342, a doubling unit 343, and a repetition determination unit 344.
A method by which the scalar multiplication unit 115 calculates the scalar multiplication point dP in the elliptic curve from the scalar value d and the point P on the elliptic curve will be described.
When the scalar multiplication calculation unit 115 receives the scalar value d and the point P on the elliptic curve from the decoding processing unit 132, the encoding unit 302 converts the input scalar value d into a numeric string d. _w Encode to [j]. That is,

D _w The scalar value d is converted into [j]. Here, w is a predetermined small positive integer and is called a window width. When priority is given to calculation time, w is set to a large value. To reduce the memory usage, w is set to a small value. The pre-calculation unit 303 creates a pre-calculation table from the input point P on the elliptic curve. The pre-calculation table is P, 3P,. . . , (2 ^w -1) It is comprised by P. The actual calculation unit 304 calculates a scalar multiple dP using the encoded scalar value and the pre-calculation table.
The encoding process performed by the encoding unit 302 may be performed after the scalar value d is received and before the actual calculation unit 304 calculates the scalar multiple. That is, it may be performed before or after the pre-calculation unit 303 creates the pre-calculation table.
When the point P is a fixed point, the pre-calculation table creation process performed by the pre-calculation unit 303 only needs to be performed once. That is, once the pre-calculation table is created, it is not necessary to re-create the pre-calculation table in subsequent scalar multiplication.
Next, each process performed by the encoding unit 302, the pre-calculation unit 303, and the actual calculation unit 304 will be described in detail.
First, a method in which the encoding unit 302 encodes the scalar value d will be described with reference to FIG.
The initial value 0 is assigned to the variable i, and the scalar value d is assigned to the variable d ′ (401).
The remainder acquisition unit 321 uses a scalar value d ′ of 2 ^w Is stored in u [i] (402).
The remainder acquisition unit 321 calculates (d′−u [i]) / 2. ^w And set it as a new d ′ (411).
The variable i is increased by 1 (412).
The repetition determination unit 324 determines whether or not the variables i and k match.
If they match, go to step 421. If they do not match, the process goes to step 414 (413).
The remainder acquisition unit 321 uses d ′ 2 ^w Is stored in u [i] (414).
The remainder conversion determination unit 322 determines whether u [i] is an even number or an odd number.
If u [i] is an even number, go to Step 416. If it is odd, the process goes to step 417 (415).
The remainder conversion unit 323 is configured so that u [i] is an odd number.
u [i] and u [i-1] are converted (416). this is,

This is achieved by performing the operation. Here, sign (u) is a function for extracting the sign of u, and is 1 when u is positive, and is -1 when u is negative.
The storage unit 325
d _w [(I-1) w], d _w [(I-1) w + 1],. . . , D _w U [i−1], 0,..., 0 are stored in [(i−1) + w−1], respectively, and the process returns to Step 411 (417).
If the variables i and k match in step 413, the storage unit 325 stores d. _w [Kw], d _w [Kw + 1],. . . , D _w U [k], 0,..., 0 are stored in [kw + w−1], respectively (421).
The encoding unit 302 is d _w [N], d _w [N-1],. . . , D _w [0] is output to the actual calculation unit 304 (422).
Next, a method in which the pre-calculation unit 303 creates a pre-calculation table from points on the elliptic curve will be described with reference to FIG.
The point P is doubled by ECDBL, and the result is stored in the point 2P (501).
The initial value 1 is assigned to the variable j (502).
j is 2 ^w-1 Determine if less than. j is 2 ^w-1 If smaller, go to step 504. 2 ^w-1 In the above case, the process goes to Step 511 (503).
In step 503, j is 2 ^w-1 If it is smaller, the point 2P and the point (2j-1) P are added by ECADD, and the result is stored in the point (2j + 1) P (504).
The variable j is incremented by 1, and the process returns to step 503 (505).
In step 503, j is 2 ^w-1 In the above case, P, 3P,. . . , (2 ^w -1) Output P as a pre-calculation table (511).
However, ECADD and ECDBL represent addition and doubling in an elliptic curve, respectively. Addition is calculated using equations 1 and 2, and doubling is calculated using equations 4 and 5, respectively. In addition, in addition to using Equations 1 and 2 and Equations 4 and 5 for calculation of addition and doubling, there are calculation formulas in projective coordinates and Jacobian coordinates. , Miyaji, A .; , Ono, T .; , Effective Elliptic Curve Exploration Using Mixed Coordinates, Advances in Cryptology-ASIACRYPT 1998, LNCS 1514, Springer-Verlag, (1998), pp. 197 51-65. (Reference 3).
Further, for the point Q = (x, y) on the elliptic curve, the inverse point -Q relating to the addition of the elliptic curve is expressed as -Q = (x, -y). It can be easily calculated if given. Therefore, the points P, 3P, ..., (2 ^w -1) Store only P as a pre-calculation table. Points -P, -3P,...,-(2) required for the calculation performed by the actual calculation unit 304 thereafter. ^w -1) P may be derived from them and need not be stored in the pre-calculation table.
Note that the pre-calculation table creation process performed by the pre-calculation unit 303 includes points P, 3P,. ^w -1) It is sufficient that P is calculated. Therefore, the speed may be increased by using the Montgomery trick to share the calculation of the inverse element operation required for the elliptic curve calculation.
A method of common inverse operation by Montgomery trick is described in Cohen, H. et al. , A course in computational algal number number theory, GTM138, Springer-Verlag, (1993). (Reference 4), page 481.
Finally, a method of calculating a scalar multiple point in an elliptic curve from the encoded scalar value and a point on the elliptic curve will be described with reference to FIG.
An initial value n is substituted for variable c (601).
d _w It is determined whether [c] is 0 or not.
d _w If [c] is 0, go to Step 603. If it is not 0, go to step 611 (602).
The variable c is decreased by 1 and the process returns to step 602 (603).
D in step 602 _w If [c] is not 0, the point Q is d _w [C] Substitute P (611).
An initial value c-1 is substituted for variable j (612).
Determine if j is less than zero. If j is smaller than 0, go to Step 621. If it is 0 or more, the process goes to step 614 (613).
Point Q is doubled by ECDBL and stored again at point Q (614).
d _w It is determined whether [j] is 0 or not.
d _w If [j] is 0, go to Step 617. If not 0, the process goes to step 616 (615).
D in step 615 _w If [j] is not 0, points Q and d _w [J] Add P to ECADD. Where d _w If [j] is negative (-d _w [J]) Addition is performed using the inverted y coordinate of P. The result is stored at point Q and the process goes to step 617 (616). D _w If [j] is not 0, d _w [J] is an odd number. Therefore, d _w [J] P or (-d _w [J]) Any of P always exists in the pre-calculation table.
The variable j is decreased by 1, and the process returns to step 613 (617).
If j is smaller than 0 in step 613, a point Q is output (621).
D output by processing performed by the encoding unit 302 _w [J] satisfies Expressions 12 and 13. The reason is as follows.
d _w [J] is equal to u [j / w] when j is divisible by w, and is equal to 0 when it is not divisible. Therefore, the right side of Equation 12 is

Is equal to However, k = n / w. On the other hand, in the conversion of step 416,

The value of is unchanged. Therefore, the value of Expression 17 is unchanged by the conversion in step 416. On the other hand, the scalar value d is 2 ^w Since the evolution is the initial state of u [i], Equation 17 is equal to d. Therefore, Equation 12 is satisfied. In the conversion in step 416,

U [i] that satisfies the equation satisfies the equation 19 even after the conversion. Therefore, Equation 13 is satisfied.
U [i] calculated in the processing performed by the encoding unit 302 is all odd except for i = 0. The reason is as follows. If u [i] is an odd number in step 415, the value of u [i] is held as it is, so u [i] is an odd number. If u [i] is an even number in step 415, u [i] and u [i-1] are converted by equations 15 and 16 in step 416. Since the value of b is calculated by Equation 14, b is 1 or -1. Therefore, u [i] is converted to an odd number by the conversion of Expression 15. In addition, the evenness of u [i−1] does not change in the conversion of Expression 16. When first coming to step 415, i is 1. Therefore, u [0] is not necessarily an odd number. As a result, all u [i] are odd except for i = 0.
In order to make u [0] odd, the scalar value d may be an odd number. For this purpose, when the input color value d is an even number, d + 1 is re-encoded as the scalar value d ′. That is, d is converted to an odd number. Then, a scalar multiple d′ P is calculated.

Therefore, the point P is subtracted from d′ P, and the value is output as the scalar multiple dP.
The point Q output from the actual calculation unit 304 is equal to the scalar multiple dP. The reason is as follows.
In step 613, the point Q is

It is assumed that At this time, the point Q also indicates that the expression 21 is satisfied when the next step 613 is reached.
Point Q is doubled in step 614 and d _w If [j] is not 0, d in step 616 _w [J] P is added. Therefore, immediately after step 616, the value of point Q is

It becomes. Therefore d _w The point Q satisfies Equation 22 just before step 617, including when [j] = 0. Since j is decreased by 1 in step 617, substituting j + 1 for j in equation 22 yields equation 21. That is, the next time when it comes to step 613, the point Q satisfies the equation (21).
d for j> c _w Since the value of [j] is 0, the value of the point Q output in step 621 is

be equivalent to. The scalar value input to the actual calculation unit 304 is d encoded by the encoding unit 302. _w [J], so that d _w [J] satisfies Equation 12. Therefore, Q = dP.
The memory usage in the scalar multiplication is determined by the size of the pre-calculation table of the pre-calculation unit 303. In the above scalar multiplication calculation method, the pre-calculation table is P, 3P,. ^w -1) Since only P, that is, only odd-numbered points need to be stored, the number of points is 2 ^w-1 It is a piece. In the method of Document 2, 2 is given to the window width w ^w Need to store points. For this reason, the scalar multiplication calculation method requires a smaller number of points to store and a smaller memory usage than the method of Document 2.
Furthermore, the memory usage is minimal in the sense that the number of points stored in the pre-calculation table cannot be reduced any further by any method. The reason is as follows.
When a pre-calculation table composed of m points is used, a number that can be expressed as an encoded scalar value using (k + 1) u [i] is (2m). ^{k + 1} It is a piece. On the other hand, all scalar values of n bits or less are 2 ⁿ Each scalar value must be encoded into a different sequence of numbers. Therefore, (2m) ^{k + 1} ≧ 2 ⁿ Holds. Since k + 1 = n / w, m ≧ 2 ^w-1 It becomes. Actually, the number of points in the previous calculation table in the above scalar multiplication method is 2 ^w-1 It is the minimum.
The scalar multiplication method is also effective for a defense method against side channel attacks. The reason is as follows.
The encoding unit 302 converts the scalar value d into a numeric string d. _w [J] is encoded. This numeric string d _w [J] is a fixed pattern

It has. Where each x is a non-zero value and d _w Corresponds to [iw]. Therefore, when the real calculation unit 304 calculates a scalar multiple, in the iterative processing of steps 613-617, the elliptic curve calculation corresponding to the block of | 0 ... 0x | is | D ... DA | A after D. However, D represents ECDBL and A represents ECADD. Therefore, for all scalar values, the elliptic curve operation to be performed is

Since ellipse addition is always executed, there is no dependency on the scalar value.
In addition, you may perform a scalar multiplication calculation using the randomized projection coordinate of literature 1 together. Then, even if the same point P is input, it is converted into a different value for each execution and a scalar multiplication is performed, so that the attacker cannot predict the intermediate value.
Alternatively, each time a point stored in the precalculation table is read, it may be randomized again and written to the precalculation table. In this case, since the same data is not reused, the resistance to side channel attacks is further increased.
As described above, the above calculation method does not give useful information for the side channel attack, and is resistant to the side channel attack. Further, since only odd-numbered points are stored as the pre-calculation table, the memory usage is small.
In the above calculation method, a Weierstrass-type elliptic curve is used as the elliptic curve, but an elliptic curve defined on a finite field of characteristic 2 or an elliptic curve defined on OEF (Optical Extension Field), Alternatively, a Montgomery-type elliptic curve may be used. For OEF, see D.C. V. Bailey, C.I. Paar, Optimal Extension Fields for Fast Arithmetic in Public-Key Algorithms, Advances in Cryptology Crypto '98, LNCS 1462, (1998), 472-485. (Reference 5).
The operation of the scalar multiplication calculator 135 when the computer B 121 decrypts the encrypted data 141 has been described above, but the same applies when the computer A 101 encrypts the input message.
In that case, the scalar multiplication unit 115 of the computer A101 outputs the already-explained point Q on the elliptic curve, the scalar multiple kQ by the random number k, and the scalar multiple k (aQ) by the public key aQ and the random number k. To do. At this time, the scalar value d described in the above calculation method is used as the random number k, the point P on the elliptic curve is set as the point Q on the elliptic curve, and the same processing is performed to obtain the respective scalar multiples. Can do.
Next, an embodiment in which the present invention is applied to a signature verification system will be described with reference to FIGS.
The signature verification system of FIG. 7 includes a smart card 701 and a computer 721 that performs signature verification processing.
The smart card 701 has a configuration similar to that of the computer A101 as a function. However, the smart card 701 is not the data processing unit 112 when the arithmetic unit such as the CPU 113 or the coprocessor 114 executes the program stored in the storage unit 102. The signature generation processing unit 712 is realized. However, it does not have an external storage device, display, or keyboard.
The computer 721 has the same configuration as the computer A101, but the signature verification processing unit 732 is realized instead of the data processing unit 112 by the CPU 113 executing the program.
The scalar multiplication calculators 715 and 735 have the same function as the scalar multiplication calculator 115 or 135 shown in FIG.
In the present embodiment, each program in the computer 721 may be stored in advance in the storage unit in the computer, or other devices via a medium that can be used by the computer 721 when necessary. To the storage unit.
Further, each program in the smart card may be stored in advance in the storage unit in the smart card, and when necessary, a computer connected via the input / output interface or the computer can be used. You may introduce | transduce into the said memory | storage part via a medium.
The medium refers to, for example, a storage medium removable from the computer or a communication medium (that is, a network or a carrier wave propagating through the network).
A signature creation and signature verification operation in the signature verification system of FIG. 7 will be described with reference to FIG.
The computer 721 transfers the randomly selected numerical value as a challenge code 743 to the smart card 701 via the interface 742.
The signature generation processing unit 712 (112 in FIG. 2) receives the challenge code 743, takes the hash value of the challenge code 743, and converts it into a numerical value f having a predetermined bit length.
The signature generation processing unit 712 generates a random number u, and reads out from the constant 704 stored in the storage unit 702 (102 in FIG. 2) (205 in FIG. 2) together with the fixed point Q on the elliptic curve, the scalar multiplication calculation unit 715. (115 in FIG. 2) (206 in FIG. 2).
The scalar multiplication calculator 715 calculates a scalar multiple (x _u , Y _u ) And sends the calculated scalar multiple to the signature generation processing unit 712 (207 in FIG. 2).
The signature generation processing unit 712 generates a signature using the sent scalar multiple. For example, if it is an ECDSA signature,

To obtain a signature (s, t) corresponding to the challenge code 743 (208 in FIG. 2).
Here, q is the order of the fixed point Q, that is, the q point qQ of the fixed point Q is an infinite point, and the m times point mQ of the fixed point Q for a numerical value m smaller than q is not an infinite point. It is a numerical value.
The ECDSA signature is described in ANSI X9.62 Public Key Cryptography for the Final Services Industry, The Elliptic Curve Digital Signature (6) (19).
The smart card 701 outputs the signature 741 created by the signature generation processing unit 712 from the input / output interface 710 and transfers it to the computer 721 via the interface 742.
When the signature 741 is input (204 in FIG. 2), the signature verification processing unit 732 (112 in FIG. 2) of the computer 721 has values s and t within the appropriate range, that is, 1 ≦ s and t <q. Find out if it is.
If the numerical values s and t are not within the above range, “invalid” is output as the signature verification result for the challenge code 743 and the smart card 701 is rejected. If the numerical values s and t are within the above range, the signature verification processing unit 732

Calculate Then, h calculated with the public key aQ and the fixed point Q read out from the constant 724 stored in the storage unit 722 (102 in FIG. 2) (205 in FIG. 2). ₁ , H ₂ Is sent to the scalar multiplication unit 735 (115 in FIG. 2) (206 in FIG. 2).
The scalar multiplication unit 735 calculates the fixed points Q and h. ₁ By scalar multiple h ₁ Q and public keys aQ and h ₂ By scalar multiple h ₂ aQ is calculated, and the calculated scalar multiple is sent to the signature verification processing unit 732 (207 in FIG. 2).
The signature verification processing unit 732 performs signature verification processing using the sent scalar multiple. For example, for ECDSA signature verification, the point R

And its x coordinate is x _R When

If s ′ = s, “valid” is output as the signature verification result for the challenge code 743, and the smart card 701 is authenticated and accepted (208 in FIG. 2).
If s ′ = s, “invalid” is output and the smart card is rejected (208 in FIG. 2).
Since the scalar multiplication calculators 715 and 735 according to the above embodiment have the same functions as the scalar multiplication calculator 115 or 135 of FIG. 1, it is possible to execute a scalar multiplication calculation that prevents a side channel attack and uses a small amount of memory.
Therefore, when the smart card 701 performs the signature generation process, the computer 721 can prevent the side channel attack when performing the signature verification process, and can execute the process with a small memory usage.
Next, an example in which the present invention is applied to a key exchange system will be described. In the present embodiment, the system configuration of FIG. 1 can be applied.
The data processing units 112 and 132 in FIG. 1 function as the key exchange processing units 112 and 132, respectively, in this embodiment.
The operation when the computer A101 of the key exchange system derives the shared information from the input data 143 will be described with reference to FIGS.
The data processing unit 132 (112 in FIG. 2) of the computer B121 reads the secret key b from the constant 125 of the storage unit 122 (102 in FIG. 2) and calculates the public key bQ of the computer B121. Then, the public key bQ is transferred as data 143 to the computer A101 via the network 142.
When the key exchange processing unit 112 (112 in FIG. 2) of the computer A101 receives the input of the public key bQ of the computer B121 (204 in FIG. 2), the key exchange processing unit 112 reads out from the storage unit 102 (FIG. 2). 205) Send the secret key a of the computer A101, which is the secret information 105, and the public key bQ of the computer B121 to the scalar multiplication unit 115 (206 in FIG. 2).
The scalar multiplication unit 115 calculates a scalar multiple abQ based on the secret key a and the public key bQ, and sends the calculated scalar multiple to the key exchange processing unit 112 (207 in FIG. 2).
The key exchange processing unit 112 derives shared information using the sent scalar multiple and stores it as the secret information 105 in the storage unit 102. For example, the x coordinate of the scalar multiple abQ is used as shared information.
Next, an operation when the computer 121 derives shared information from input data 141 will be described.
The data processing unit 112 of the computer A101 reads the secret key a from the constant 105 of the storage unit 102 and calculates the public key aQ of the computer A101. Then, the public key aQ is transferred as data 141 to the computer B 121 via the network 142.
When the key exchange processing unit 132 (112 in FIG. 2) of the computer B121 accepts the input of the public key aQ of the computer A101 (204 in FIG. 2), the key exchange processing unit 132 stores in the storage unit 122 (102 in FIG. 2). The private key b of the computer B121 and the public key aQ of the computer A101 which are the secret information 125 read from the constant 125 (205 in FIG. 2) are sent to the scalar multiplication unit 135 (115 in FIG. 2) (206 in FIG. 2). ).
The scalar multiplication unit 135 calculates a scalar multiplication point baQ based on the secret key b and the public key aQ, and sends the calculated scalar multiplication point to the key exchange processing unit 132 (207 in FIG. 2).
The key exchange processing unit 132 derives shared information using the sent scalar multiple and stores it as the secret information 125 in the storage unit 122. For example, the x coordinate of the scalar multiple baQ is used as shared information.
Here, since the number ab and the number ba are the same as numerical values, the point abQ and the point baQ are the same point, and the same information is derived.
A point aQ and a point bQ are transmitted to the network 142. To calculate the point abQ (or point baQ), the secret key a or the secret key b must be used. That is, the shared information cannot be obtained without knowing the secret key a or the secret key b. The shared information obtained in this way can be used as a secret key for common key cryptography.
Also in this embodiment, the scalar multiplication calculators 115 and 135 have the above-described features, so that side channel attacks can be prevented and key exchange processing can be performed with a small memory usage.
In addition, the encryption processing unit, the decryption processing unit, the signature creation unit, the signature verification unit, and the key exchange processing unit in each of the above embodiments may be performed using dedicated hardware. Further, the scalar multiplication calculation unit may be realized by a coprocessor or other dedicated hardware.
Further, the data processing unit may be configured to perform any one or more of the encryption process, the decryption process, the signature creation process, the signature verification process, and the key exchange process.
According to the present invention, it is possible to perform message processing using elliptic curve calculation that is safe against side channel attacks and uses a small amount of memory.

Claims (6)

In an elliptic curve in elliptic curve cryptography, a scalar multiple calculation device for calculating a scalar multiple from a scalar value and a point on an elliptic curve,
An encoding unit that encodes the scalar value into a numerical sequence having an absolute value of even number r or less ;
A pre-calculation unit that creates a pre-calculation table from points on the elliptic curve;
A real calculation unit for calculating a scalar multiple from the encoded numerical sequence and the previous calculation table,
The encoding unit is
A first step of initializing a numerical sequence for storing an encoding result and substituting the scalar value into a first variable;
A second step of substituting a remainder modulo the even number r for the first variable into a second variable;
A third step of storing in the first variable a quotient obtained by dividing a value obtained by subtracting the second variable from the first variable by the even number r;
A fourth step of substituting the second variable for the third variable;
A fifth step of substituting a remainder modulo the even number r for the first variable into a second variable;
A sixth step of determining whether the second variable is an even number;
If it is determined in the sixth step that the second variable is an even number,
If the third variable is positive, add 1 to the second variable and subtract an even number r from the third variable;
If the third variable is negative, a seventh step of subtracting 1 from the second variable and adding an even number r to the third variable;
An eighth step of adding the numerical value indicated by the third variable to the numerical string;
Run
The encoding unit is
After repeatedly executing the third to eighth steps a predetermined number of times, the numerical sequence is output as the encoded numerical sequence,
The pre-calculation table created by the pre-calculation unit is
Including points that are odd multiples of the points on the elliptic curve,
The actual calculation unit is
A ninth step of calculating even r times points on the elliptic curve;
A tenth step of adding the points of the calculation results of the ninth step and the points stored in the pre-calculation table;
Run
The scalar multiplication apparatus according to claim 10, wherein the point stored in the pre-calculation table added by the actual calculation unit in the tenth step is a multiple by a numerical value belonging to the encoded numerical sequence . In an elliptic curve in elliptic curve cryptography, a scalar multiple calculation device for calculating a scalar multiple from a pre-calculation table storing a scalar value and an odd multiple of a point on an elliptic curve,
An encoding unit that encodes the scalar value into a numerical sequence having an absolute value of even number r or less ;
A real calculation unit for calculating a scalar multiple from the encoded numerical sequence and the previous calculation table,
The encoding unit is
A first step of initializing a numerical sequence for storing an encoding result and substituting the scalar value into a first variable;
A second step of substituting a remainder modulo the even number r for the first variable into a second variable;
A third step of storing in the first variable a quotient obtained by dividing a value obtained by subtracting the second variable from the first variable by the even number r;
A fourth step of substituting the second variable for the third variable;
A fifth step of substituting a remainder modulo the even number r for the first variable into a second variable;
A sixth step of determining whether the second variable is an even number;
If it is determined in the sixth step that the second variable is an even number,
If the third variable is positive, add 1 to the second variable and subtract an even number r from the third variable;
If the third variable is negative, a seventh step of subtracting 1 from the second variable and adding an even number r to the third variable;
An eighth step of adding the numerical value indicated by the third variable to the numerical string;
Run
The encoding unit is
After repeatedly executing the third to eighth steps a predetermined number of times, the numerical sequence is output as the encoded numerical sequence,
The actual calculation unit is
A ninth step of calculating even r times points on the elliptic curve;
A tenth step of adding the points of the calculation results of the ninth step and the points stored in the pre-calculation table;
Run
The scalar multiplication apparatus according to claim 10, wherein the point stored in the pre-calculation table added by the actual calculation unit in the tenth step is a multiple by a numerical value belonging to the encoded numerical sequence . The scalar multiplication apparatus according to claim 1 or 2 ,
As the elliptic curve, any one of a Weierstrass type elliptic curve, a Montgomery type elliptic curve, an elliptic curve defined on a finite field of characteristic 2 and an elliptic curve defined on OEF is used. A scalar multiplication calculator. A data conversion unit for generating second data from the first data;
A data generation device having a scalar multiplication calculation unit that is requested by the data conversion unit to calculate a scalar multiplication,
The scalar multiplication calculator
3. A data generation apparatus that calculates a scalar multiplication using the scalar multiplication apparatus according to claim 1 . A signature part for generating signature data from the data;
A signature creation device having a scalar multiplication calculation unit requested by the signature unit to calculate a scalar multiplication,
The scalar multiplication calculator
A signature creation device, wherein a scalar multiplication is calculated using the scalar multiplication device according to claim 1 . A decryption unit for generating decrypted data from the encrypted data;
A decoding device having a scalar multiplication unit requested by the decoding unit to calculate a scalar multiplication,
The scalar multiplication calculator
A decoding device, wherein a scalar multiplication is calculated using the scalar multiplication device according to claim 1 .

Images