(57)【要約】要約なし【特許請求の範囲】
【請求項１】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、
前記スカラー値を数値列にエンコードするステップと、
前記楕円曲線上の点から前計算テーブルを作成するステップと、
前記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算するステップと、を有するスカラー倍計算方法。
【請求項２】
請求項１記載のスカラー倍計算方法であって、
前記エンコードするステップが出力する数値列は０と奇数からなるスカラー倍計算方法。
【請求項３】
請求項２記載のスカラー倍計算方法であって、
前記スカラー倍点を計算するステップは、
第１の演算を予め定められた回数を実行するステップと、
第１の演算とは異なる第２の演算を実行するステップとを含むスカラー倍計算方法。
【請求項４】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点の奇数倍点を格納した前計算テーブルからスカラー倍点を計算するスカラー倍計算方法であって、
前記スカラー値を数値列にエンコードするステップと、
前記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算するステップとを有し、
前記エンコードするステップが出力する数値列は０と奇数からなるスカラー倍計算方法。
【請求項５】
請求項３記載のスカラー倍計算方法であって、
楕円曲線としてワイエルシュトラス型楕円曲線を用いるスカラー倍計算方法。
【請求項６】
請求項３記載のスカラー倍計算方法であって、
楕円曲線としてモンゴメリ型楕円曲線を用いるスカラー倍計算方法。
【請求項７】
請求項３記載のスカラー倍計算方法であって、
楕円曲線として標数２の有限体上で定義された楕円曲線を用いるスカラー倍計算方法。
【請求項８】
請求項３記載のスカラー倍計算方法であって、
楕円曲線としてＯＥＦ上で定義された楕円曲線を用いるスカラー倍計算方法。
【請求項９】
第１のデータから第２のデータを生成するデータ生成方法であって、
請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有するデータ生成方法。
【請求項１０】
データから署名データを生成する署名作成方法であって、
請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する署名作成方法。
【請求項１１】
暗号化されたデータから復号化されたデータを生成する復号化方法であって、
請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算するステップを有する復号化方法。
【請求項１２】
楕円曲線暗号における楕円曲線において、スカラー値及び楕円曲線上の点からスカラー倍点を計算するスカラー倍計算装置であって、
前記スカラー値を数値列にエンコードするエンコード部と、
前記楕円曲線上の点から前計算テーブルを作成する前計算部と、
前記エンコードした数値列及び前記前計算テーブルからスカラー倍点を計算する実計算部とを有するスカラー倍計算装置。
【請求項１３】
第１のデータから第２のデータを生成するデータ変換部と、前記データ変換部より依頼されてスカラー倍を計算するスカラー倍計算部とを有するデータ生成装置であって、
前記スカラー倍計算部は、請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算するデータ生成装置。
【請求項１４】
データから署名データを生成する署名部と、前記署名部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する署名作成装置であって、
前記スカラー倍計算部は、請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算する署名作成装置。
【請求項１５】
暗号化されたデータから復号化されたデータを生成する復号部と、前記復号部より依頼されてスカラー倍を計算するスカラー倍計算部とを有する復号化装置であって、
前記スカラー倍計算部は、請求項３に記載のスカラー倍計算方法を用いてスカラー倍を計算する復号化装置。
【請求項１６】
請求項３に記載のスカラー倍計算方法を計算機に実行させるプログラム。
【請求項１７】
請求項１０記載の署名作成方法を計算機に実行させるプログラム。
【請求項１８】
請求項１１記載の復号化方法を計算機に実行させるプログラム。
【発明の詳細な説明】
【技術分野】  本発明はセキュリティ技術に係り、特に楕円曲線演算を用いたメッセージ処理方法に関する。
【背景技術】  楕円曲線暗号はＮ．Ｋｏｂｌｉｔｚ，Ｖ．Ｓ．Ｍｉｌｌｅｒにより提案された公開鍵暗号の一種である。公開鍵暗号には、公開鍵と呼ばれる一般に公開してよい情報と、秘密鍵と呼ばれる秘匿しなければならない秘密情報がある。与えられたメッセージの暗号化や署名の検証には公開鍵を用い、与えられたメッセージの復号化や署名の作成には秘密鍵を用いる。
楕円曲線暗号における秘密鍵は、スカラー値が担っている。また、楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｄＰが与えられた時、スカラー値ｄを求める問題である。
楕円曲線上の点とは、楕円曲線の定義方程式をみたす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（乃至は加算）が定義される。そして、同じ点同士による楕円曲線上の加法のことを、特に楕円曲線上の２倍算という。
楕円曲線上の２点の加法は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）の加算
（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は
2004070681.tif 000002
を計算することにより得られる。ここで、ワイエルシュトラス型楕円曲線の定義式は
2004070681.tif 000003
で与えられる。すなわち、式３のｘ，ｙに各々ｘｉ，ｙｉ（ｉ＝１，２，３）を代入した場合に、式３の等式が成り立つ。
楕円曲線上の点の２倍算は次のようにして計算される。楕円曲線上の点における接線をひくと、その接線は楕円曲線上の他の点において交わる。その交わった点とｘ座標に関して対称な点を、２倍算を行った結果の点とする。例えば、ワイエルシュトラス型楕円曲線の場合には、点（ｘ１，ｙ１）の２倍算
（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は
2004070681.tif 000004
を計算することにより得られる。
ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
楕円曲線上の離散対数問題の求解の困難性が理論的に確立されてきている一方で、実際の実装においては秘密鍵等の秘密情報に関連する情報（計算時間や電力消費量など）が暗号処理において漏洩する場合があり、その漏洩情報をもとに秘密情報を復元するといった、サイドチャネル攻撃という攻撃法が提案されている。
楕円曲線暗号に対するサイドチャネル攻撃が、Ｊ．Ｃｏｒｏｎ，Ｒｅｓｉｓｔａｎｃｅ  ａｇａｉｎｓｔ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ｐｏｗｅｒ  Ａｎａｌｙｓｉｓ  ｆｏｒ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｓｙｓｔｅｍｓ，Ｃｒｙｐｔｏｇｒａｐｈｉｃ  Ｈａｒｄｗａｒｅ  ａｎｄ  Ｅｍｂｅｄｄｅｄ  Ｓｙｓｔｅｍｓ：  Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  ＣＨＥＳ’９９，ＬＮＣＳ  １７１７，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９９）ｐｐ．２９２−３０２．（文献１）に記載されている。
楕円曲線暗号においては、与えられたメッセージの暗号化、復号化、署名の作成またはその検証は、楕円曲線演算を用いて行う必要がある。特に楕円曲線上のスカラー倍の計算は、秘密情報であるスカラー値を用いた暗号処理において用いられる。
楕円曲線暗号に対するサイドチャネル攻撃の防御法が、Ｂ．Ｍｏｅｌｌｅｒ，Ｓｅｃｕｒｉｎｇ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｐｏｉｎｔ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎ  ａｇａｉｎｓｔ  Ｓｉｄｅ−Ｃｈａｎｎｅｌ  Ａｔｔａｃｋｓ，Ｉｎｆｏｒｍａｔｉｏｎ  Ｓｅｃｕｒｉｔｙ（ＩＳＣ２００１），ＬＮＣＳ  ２２００，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（２００１），ｐｐ．３２４−３３４．（文献２）に記載されている。
【発明の開示】
情報通信ネットワークの進展と共に電子情報に対する秘匿や認証の為に暗号技術は不可欠な要素となってきている。そこでは暗号技術の安全性とともにメモリ等の使用リソースの削減が望まれている。楕円曲線上の離散対数問題が非常に困難である為に、素因数分解の困難性を安全性の根拠にしている暗号と比べて、楕円曲線暗号は鍵長を比較的短くすることができる。そのため比較的少ないリソースで暗号処理を行うことが可能である。しかしながら、備えているメモリ量が少ないスマートカード（ＩＣカードともいう）等においては、必ずしも満足できるとは限らない。それゆえに少ないメモリで実行できる暗号処理が必要となる。
上記技術は、サイドチャネル攻撃を防ぐ方法としては有効であるが、メモリ使用量の削減という点は考慮されていない。
本発明は、サイドチャネル攻撃を防ぐことができる、かつメモリ使用量の少ない、楕円曲線演算方法を提供する。
本発明は更に、上記楕円曲線演算方法を用いた、暗号化処理方法、復号化処理方法、署名作成方法、署名検証方法、データ共有方法を提供する。
本発明は、楕円曲線演算において、スカラー値と楕円曲線上の点からスカラー倍点を計算するスカラー倍計算方法であって、上記スカラー値を数値列にエンコードするステップと、上記楕円曲線上の点から前計算テーブルを作成するステップと、上記エンコードした数値列及び上記前計算テーブルからスカラー倍点を計算するステップとを有する。
本発明は、また、上記エンコードするステップの出力する数値列を０と奇数からなるように構成してもよい。
本発明は、また、上記スカラー倍点を計算するステップは、第１の演算を予め定められた回数を実行するステップと、第１の演算とは異なる第２の演算を実行するステップとを含むように構成してもよい。
本発明は、また、楕円曲線演算において、スカラー値と楕円曲線上の点の奇数倍点を格納した前計算テーブルからスカラー倍点を計算するスカラー倍計算方法であって、上記スカラー値を数値列にエンコードするステップと、上記エンコードした数値列と上記前計算テーブルからスカラー倍点を計算するステップとを有し、上記エンコードするステップの出力する数値列は０と奇数からなるように構成してもよい。
以上のように本発明のスカラー倍計算方法によれば、奇数倍の点のみを前計算テーブルに格納し、スカラー値を奇数倍の点のみを用いるようにエンコードすることにより、サイドチャネル攻撃を防ぐことができ、メモリ使用量が少ないスカラー倍計算方法が利用可能になる。
【図面の簡単な説明】図１は、実施形態におけるシステム構成図である。
図２は、各実施形態における情報の受け渡しを示すシーケンス図である。
図３は、実施形態におけるスカラー倍計算部の構成図である。
図４は、エンコード部の行うエンコード方法を示すフローチャート図である。
図５は、前計算部の行う前計算方法を示すフローチャート図である。
図６は、実計算部の行う実計算方法を示すフローチャート図である。
図７は、実施形態における署名検証システム構成図である。
【発明を実施するための最良の形態】  以下、本発明の実施例を図面により説明する。
図１はネットワーク１４２によって接続された本発明による楕円曲線演算方法を適用したコンピュータＡ１０１、コンピュータＢ１２１がネットワーク１４２により接続されたシステム構成を示すものである。
図１の暗号通信システムにおけるコンピュータＡ１０１でメッセージの暗号化を行うには、Ｐｍ＋ｋ（ａＱ）及びｋＱを計算して出力し、コンピュータＢ１２１で暗号文の復号化を行うには、秘密鍵ａ及びｋＱより−ａ（ｋＱ）を計算し、
2004070681.tif 000005
を計算して出力すればよい。ここでＰｍはメッセージ、ｋは乱数、ａは秘密鍵を示す定数、Ｑは定点、ａＱは公開鍵を示す点である。
ネットワーク１４２には、Ｐｍ＋ｋ（ａＱ），ｋＱのみ送信され、メッセージＰｍを復元するためには、ｋａＱ、すなわちｋＱのａ倍を計算する必要がある。ところが、秘密鍵ａはネットワーク１４２には送信されないため、秘密鍵ａを保持しているものだけが、Ｐｍを復元できることになる。
図１において、コンピュータＡ１０１は、ＣＰＵ１１３やコプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置、コンピュータ外部とのデータ入出力を行う入出力インタフェース１１０を装備しており、外部にはコンピュータＡ１０１をユーザが操作するためのディスプレイ１０８、キーボード１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続されている。
更にコンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、データ処理部１１２、スカラー倍計算部１１５を実現する。
データ処理部１１２は、本実施形態においては、暗号化処理部１１２として機能し、入力されたメッセージの暗号化を行う。
スカラー倍計算部１１５は、暗号処理部１１２で暗号化を行うのに必要なパラメタを計算する。記憶部１０２は、定数１０４（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報１０５（例えば、秘密鍵である。）などを記憶している。
コンピュータＢ１２１は、コンピュータＡ１０１と同様のハードウェア構成を備える。
更にコンピュータＢ１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１０７などの記憶装置によって、記憶部１２２を実現し、ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納されたプログラムを実行することにより、データ処理部１３２、スカラー倍計算部１３５を実現する。
データ処理部１３２は、本実施形態においては、復号化処理部１３２として機能し、暗号化されたメッセージである暗号文１４１の復号化を行う。
スカラー倍計算部１３５は、復号化処理部１３２で復号化を行うのに必要なパラメタを計算する。記憶部１２２は、定数１２４（例えば、楕円曲線の定義式や楕円曲線上の定点である。）、秘密情報１２５（例えば、秘密鍵である。）などを記憶している。
なお、上記各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、入出力インタフェース１１０と上記コンピュータ７２１が利用可能な媒体を介して、他の装置から上記記憶部に導入されてもよい。媒体とは、たとえば、入出力インタフェース１１０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
図２は、コンピュータＡ１０１、コンピュータＢ１２１の各処理部が行う情報の受け渡しの様子を示したものである。
次に、図１のコンピュータＡ１０１が、入力されたメッセージを暗号化する場合の動作について説明する。メッセージはディジタル化されたデータであれば良く、テキスト、画像、映像、音などの種類は問わない。
暗号化処理部１１２は、入出力インタフェース１１０を介して、平文メッセージ（図２の入力メッセージ２０４）を受け取ると、入力された平文メッセージのビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように平文メッセージを区切る。以下、所定のビット長に区切られている部分メッセージ（単にメッセージともいう）について説明する。
次に、暗号化処理部１１２は、メッセージのビット列によって表される数値をｘ座標（ｘ１）にもつ楕円曲線上の点Ｐｍのｙ座標の値（ｙ１）を計算する。
例えば、ワイエルシュトラス型楕円曲線は、Ａ，Ｂをそれぞれ定数とするとき、
2004070681.tif 000006
で表されるので、これよりｙ座標の値を求めることができる。
次に、暗号化処理部１１２は、乱数ｋを生成する。そして、記憶部１０２に格納されている定数１０４から読み出した（図２の２０５）公開鍵ａＱとＱのｘ座標と、求めたｙ座標の値と乱数ｋとをスカラー倍計算部１１５へ送る（図２の２０６）。
スカラー倍計算部１１５は、Ｑのｘ座標、ｙ座標の値、乱数ｋによるスカラー倍点（ｘｄ１，ｙｄ１）＝ｋＱと、公開鍵ａＱのｘ座標、ｙ座標の値、乱数によるスカラー倍点（ｘｄ２，ｙｄ２）＝ｋ（ａＱ）とを計算し、計算されたスカラー倍点を暗号化処理部１１２へ送る（図２の２０７）。
暗号化処理部１１２は、送られたスカラー倍点を用いて、暗号化処理を行う。例えば、ワイエルシュトラス型の楕円曲線については、Ｐｍ＋ｋ（ａＱ）とｋＱを計算する。すなわち、
2004070681.tif 000007
を計算し、暗号化されたメッセージｘｅ１，ｘｅ２を得る。
コンピュータＡ１０１は暗号化処理部１１２で暗号化された１つ以上の部分メッセージから暗号化された出力メッセージを組み立てる（図２の２０８）。
コンピュータＡ１０１は、暗号化された出力メッセージをデータ１４１として入出力インタフェース１１０より出力し、ネットワーク１４２を介してコンピュータＢ１２１へ転送する。
なお、図２の記憶部１０２からの情報読み出しは、スカラー計算部１１５へ当該情報を送る前で有れば、入力メッセージを受け付ける前であっても良い。
次に、コンピュータＢ１２１が、暗号化されたメッセージ１４１を復号化する場合の動作について、図２を参照しつつ説明する。
復号化処理部１３２（図２のデータ処理部１１２）は、入出力インタフェース１１０を介して、暗号化されたデータ１４１（図２の入力メッセージ２０４）が入力されると、入力された暗号化されたデータ１４１のビット長が予め定めたビット長か否かを判断する。予め定めたビット長より長い場合には、予め定めたビット長となるように暗号化されたデータを区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）について説明する。
データ１４１のビット列によって表される数値をｘ座標にもつ楕円曲線上のｙ座標の値を計算する。
暗号化されたメッセージがｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型楕円曲線の場合、ｙ座標の値（ｙｅ１）は
2004070681.tif 000008
（ただし、Ａ，Ｂはそれぞれ定数である）
から得ることができる。
復号化処理部１３２は、記憶部１２２（図２の１０２）に格納されている秘密情報１２５から読み出した（図２の２０５）秘密鍵ａと、ｘ座標、ｙ座標の値（ｘｅ１，ｙｅ１）を、スカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部１３５は、ｘ座標、ｙ座標の値、秘密情報ａ１２５からスカラー倍点（ｘｄ３，ｙｄ３）＝ａ（ｘｅ２，ｙｅ２）を計算する。スカラー倍計算部１３５は、計算されたスカラー倍点を復号化処理部１３２へ送る（図２の２０７）。復号化処理部１３２は、送られたスカラー倍点を用いて、復号化処理を行う。
例えば、暗号化されたメッセージが、ｘｅ１，ｘｅ２のビット列であり、ワイエルシュトラス型の楕円曲線の場合は、
（Ｐｍ＋ｋ（ａＱ））−ａ（ｋＱ）＝（ｘｅ１，ｙｅ１）−（ｘｄ３，ｙｄ３）
を計算することにより達成する。すなわち、
2004070681.tif 000009
を計算し、暗号化される前の部分メッセージｘ１に相当するｘｆ１を得る。
コンピュータＢ１２１は、復号化処理部１３２で復号化された部分メッセージから平文メッセージを組み立て（図２の２０８）、入出力インタフェース１１０を介して、ディスプレイ１０８などから出力する。
次に、コンピュータＢ１２１が、復号化処理を行う場合の、スカラー倍計算部１３５の処理を詳細に説明する。
図３は、各実施例で用いるスカラー倍計算部の機能ブロックを示したものである。スカラー倍計算部１１５（図１の１３５）は、エンコード部３０２、前計算部３０３、実計算部３０４からなる。エンコード部３０２は、剰余取得部３２１、剰余変換判定部３２２、剰余変換部３２３、繰り返し判定部３２４、格納部３２５からなる。前計算部３０３は、加算部３３１、２倍算部３３２、繰り返し判定部３３３からなる。実計算部３０４は、ビット値判定部３４１、加算部３４２、２倍算部３４３、繰り返し判定部３４４からなる。
スカラー倍計算部１１５がスカラー値ｄ及び楕円曲線上の点Ｐから、楕円曲線におけるスカラー倍点ｄＰを計算する方法を説明する。
スカラー倍計算部１１５が復号化処理部１３２からスカラー値ｄと楕円曲線上の点Ｐを受け取ると、エンコード部３０２は、入力されたスカラー値ｄを数値列ｄｗ［ｊ］にエンコードする。すなわち、
2004070681.tif 000010
をみたすｄｗ［ｊ］に、スカラー値ｄを変換する。ここで、ｗはあらかじめ定めた小さな正整数で、ウィンドウ幅と呼ばれる。計算時間を優先する場合はｗを大きな値とする。メモリ使用量を小さくする場合はｗを小さな値にする。前計算部３０３は、入力された楕円曲線上の点Ｐから前計算テーブルを作成する。前計算テーブルはＰ，３Ｐ，．．．，（２ｗ−１）Ｐにより構成される。実計算部３０４は、エンコードされたスカラー値と前計算テーブルを用いてスカラー倍点ｄＰを計算する。
なお、エンコード部３０２の行うエンコード処理は、スカラー値ｄを受け取った後、および実計算部３０４がスカラー倍点を計算する前であればよい。すなわち、前計算部３０３が前計算テーブルを作成する前に行っても、後に行なってもよい。
また、点Ｐが固定点である場合、前計算部３０３の行う前計算テーブルの作成処理は、ただ一度行えばよい。すなわち、一旦前計算テーブルを作成すれば、それ以降のスカラー倍計算では前計算テーブルを再作成する必要はない。
次にエンコード部３０２、前計算部３０３、実計算部３０４の行なう各処理について詳細に説明する。
まず、図４を用いて、エンコード部３０２がスカラー値ｄをエンコードする方法を説明する。
変数ｉに初期値０を、変数ｄ’にスカラー値ｄをそれぞれ代入する（４０１）。
剰余取得部３２１は、スカラー値ｄ’の２ｗによる剰余をｕ［ｉ］に格納する（４０２）。
剰余取得部３２１は、（ｄ’−ｕ［ｉ］）／２ｗを計算し、それを新たなｄ’とする（４１１）。
変数ｉを１増加させる（４１２）。
繰り返し判定部３２４は、変数ｉとｋが一致するかどうかを判定する。
一致すればステップ４２１へ行く。一致しなければステップ４１４へ行く（４１３）。
剰余取得部３２１は、ｄ’の２ｗによる剰余をｕ［ｉ］に格納する（４１４）。
剰余変換判定部３２２は、ｕ［ｉ］が偶数か奇数かを判定する。
ｕ［ｉ］が偶数の場合はステップ４１６へ行く。奇数の場合はステップ４１７へ行く（４１５）。
剰余変換部３２３は、ｕ［ｉ］が奇数となるように、
ｕ［ｉ］，ｕ［ｉ−１］を変換する（４１６）。これは、
2004070681.tif 000011
の操作を行なうことにより達成される。ここで、ｓｉｇｎ（ｕ）はｕの符号を取り出す関数であり、ｕが正の時は１、ｕが負の時は−１となる。
格納部３２５は、
ｄｗ［（ｉ−１）ｗ］，ｄｗ［（ｉ−１）ｗ＋１］，．．．，ｄｗ［（ｉ−１）＋ｗ−１］にそれぞれ、ｕ［ｉ−１］，０，…，０を格納し、ステップ４１１へ戻る（４１７）。
ステップ４１３で変数ｉとｋが一致した場合、格納部３２５はｄｗ［ｋｗ］，ｄｗ［ｋｗ＋１］，．．．，ｄｗ［ｋｗ＋ｗ−１］にそれぞれ、ｕ［ｋ］，０，…，０を格納する（４２１）。
エンコード部３０２は、ｄｗ［ｎ］，ｄｗ［ｎ−１］，．．．，ｄｗ［０］を実計算部３０４へ出力する（４２２）。
次に、図５を用いて、前計算部３０３が楕円曲線上の点から、前計算テーブルを作成する方法を説明する。
点ＰをＥＣＤＢＬにより２倍し、その結果を点２Ｐに格納する（５０１）。
変数ｊに初期値１を代入する（５０２）。
ｊが２ｗ−１より小さいかどうかを判定する。ｊが２ｗ−１より小さい場合はステップ５０４へ行く。２ｗ−１以上の場合はステップ５１１へ行く（５０３）。
ステップ５０３でｊが２ｗ−１より小さい場合、点２Ｐと点（２ｊ−１）ＰをＥＣＡＤＤにより加算し、その結果を点（２ｊ＋１）Ｐに格納する（５０４）。
変数ｊを１増加させ、ステップ５０３へ戻る（５０５）。
ステップ５０３でｊが２ｗ−１以上の場合、Ｐ，３Ｐ，．．．，（２ｗ−１）Ｐを前計算テーブルとして出力する（５１１）。
ただし、ＥＣＡＤＤ，ＥＣＤＢＬはそれぞれ楕円曲線における加算、２倍算を表す。加算は式１，２を用いて、２倍算は式４，５を用いてそれぞれ計算される。なお、加算、２倍算の計算には式１，２、および式４，５を用いる以外にも、射影座標やヤコビアン座標における計算公式があり、Ｃｏｈｅｎ，Ｈ．，Ｍｉｙａｊｉ，Ａ．，Ｏｎｏ，Ｔ．，Ｅｆｆｉｃｉｅｎｔ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  Ｕｓｉｎｇ  Ｍｉｘｅｄ  Ｃｏｏｒｄｉｎａｔｅｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ−ＡＳＩＡＣＲＹＰＴ  １９９８，ＬＮＣＳ  １５１４，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９８），ｐｐ．５１−６５．（文献３）に記載されている。
また、楕円曲線上の点Ｑ＝（ｘ，ｙ）に対して、楕円曲線加算に関する逆元の点−Ｑは、−Ｑ＝（ｘ，−ｙ）と表されるため、点Ｑの座標が与えられていれば容易に計算できる。そのため、点Ｐ，３Ｐ，…，（２ｗ−１）Ｐのみを前計算テーブルとして格納する。その後の実計算部３０４が行う計算で必要となる点−Ｐ，−３Ｐ，…，−（２ｗ−１）Ｐは、それらから導出すればよく、前計算テーブルには格納する必要はない。
なお、前計算部３０３の行う前計算テーブルの作成処理は、点Ｐ，３Ｐ，…，（２ｗ−１）Ｐが計算されればよい。そのため、モンゴメリトリックを用いて、楕円曲線演算で必要となる逆元演算の計算の共通化を行うことにより、高速化をはかってもよい。
モンゴメリトリックによる逆元演算共通化方法がＣｏｈｅｎ，Ｈ．，Ａ  ｃｏｕｒｓｅ  ｉｎ  ｃｏｍｐｕｔａｔｉｏｎａｌ  ａｌｇｅｂｒａｉｃ  ｎｕｍｂｅｒ  ｔｈｅｏｒｙ，ＧＴＭ１３８，Ｓｐｒｉｎｇｅｒ−Ｖｅｒｌａｇ，（１９９３）．（文献４）の４８１ページに記載されている。
最後に、図６を用いて、実計算部３０４がエンコードされたスカラー値と楕円曲線上の点から、楕円曲線におけるスカラー倍点を計算する方法を説明する。
変数ｃに初期値ｎを代入する（６０１）。
ｄｗ［ｃ］が０か０でないかを判定する。
ｄｗ［ｃ］が０の場合はステップ６０３へ行く。０でなければステップ６１１へ行く（６０２）。
変数ｃを１減少させ、ステップ６０２へ戻る（６０３）。
ステップ６０２でｄｗ［ｃ］が０でない場合、点Ｑにｄｗ［ｃ］Ｐを代入する（６１１）。
変数ｊに初期値ｃ−１を代入する（６１２）。
ｊが０より小さいかどうかを判定する。ｊが０より小さい場合はステップ６２１へ行く。０以上の場合はステップ６１４へ行く（６１３）。
点ＱをＥＣＤＢＬにより２倍し、点Ｑに再び格納する（６１４）。
ｄｗ［ｊ］が０か０でないかを判定する。
ｄｗ［ｊ］が０の場合はステップ６１７へ行く。０でなければステップ６１６へ行く（６１５）。
ステップ６１５でｄｗ［ｊ］が０でない場合、点Ｑとｄｗ［ｊ］ＰとをＥＣＡＤＤにより加算する。ただし、ｄｗ［ｊ］が負の場合は（−ｄｗ［ｊ］）Ｐのｙ座標を反転したものを用いて加算を行う。その結果を点Ｑに格納し、ステップ６１７へ行く（６１６）。なお、ｄｗ［ｊ］が０でない場合は、ｄｗ［ｊ］は奇数である。そのため、ｄｗ［ｊ］Ｐもしくは（−ｄｗ［ｊ］）Ｐのいずれかが、前計算テーブルに必ず存在する。
変数ｊを１減少させ、ステップ６１３へと戻る（６１７）。
ステップ６１３でｊが０より小さい場合、点Ｑを出力する（６２１）。
エンコード部３０２が行う処理により出力されるｄｗ［ｊ］は、式１２，式１３をみたす。この理由は次の通りである。
ｄｗ［ｊ］はｊがｗで割り切れる時はｕ［ｊ／ｗ］に等しく、割り切れない場合は０に等しい。そのため、式１２の右辺は、
2004070681.tif 000012
と等しい。ただし、ｋ＝ｎ／ｗである。一方、ステップ４１６の変換では、
2004070681.tif 000013
の値は不変である。したがって、ステップ４１６の変換で、式１７の値は不変である。他方、スカラー値ｄを２ｗ−進展開したものがｕ［ｉ］の初期状態であるので、式１７はｄに等しい。ゆえに式１２がみたされる。また、ステップ４１６の変換では、
2004070681.tif 000014
をみたすｕ［ｉ］は、変換後も式１９をみたす。したがって、式１３がみたされる。
エンコード部３０２が行う処理で計算されるｕ［ｉ］はｉ＝０を除き全て奇数となる。この理由は次の通りである。ステップ４１５でｕ［ｉ］が奇数であれば、ｕ［ｉ］の値はそのまま保持されるので、ｕ［ｉ］は奇数である。ステップ４１５でｕ［ｉ］が偶数であれば、ステップ４１６でｕ［ｉ］，ｕ［ｉ−１］は式１５，１６により変換される。式１４によりｂの値が計算されるため、ｂは１もしくは−１である。そのため、式１５の変換で、ｕ［ｉ］は奇数に変換される。また、式１６の変換では、ｕ［ｉ−１］の偶奇性は変化しない。ステップ４１５に初めて来る時のｉは１である。そのため、ｕ［０］は奇数とは限らない。結果として、ｉ＝０を除き、ｕ［ｉ］は全て奇数である。
なお、ｕ［０］も奇数とするためには、スカラー値ｄが奇数であればよい。そのためには、入力されたすカラー値ｄが偶数の時は、ｄ＋１を改めてスカラー値ｄ’としてエンコードする。すなわち、ｄを奇数に変換する。そして、スカラー倍点ｄ’Ｐを計算する。
2004070681.tif 000015
であるので、ｄ’Ｐから点Ｐを引き、その値をスカラー倍点ｄＰとして出力すればよい。
実計算部３０４が出力する点Ｑはスカラー倍点ｄＰに等しい。この理由は次の通りである。
ステップ６１３において点Ｑが
2004070681.tif 000016
と表されるとする。このとき、次にステップ６１３に来る時も点Ｑは式２１をみたすことを示す。
点Ｑはステップ６１４で２倍され、ｄｗ［ｊ］が０でなければステップ６１６でｄｗ［ｊ］Ｐが加えられる。そのためステップ６１６の直後では、点Ｑの値は
2004070681.tif 000017
となる。したがってｄｗ［ｊ］＝０の時も含めて、ステップ６１７の直前で、点Ｑは式２２をみたす。ステップ６１７でｊが１減少するので、式２２のｊにｊ＋１を代入すると式２１になる。すなわち、次にステップ６１３に来る時も点Ｑは式２１をみたす。
ｊ＞ｃに対するｄｗ［ｊ］の値は０であるので、ステップ６２１で出力される点Ｑの値は
2004070681.tif 000018
に等しい。実計算部３０４に入力されるスカラー値は、エンコード部３０２によりエンコードされたｄｗ［ｊ］であるので、そのｄｗ［ｊ］は式１２をみたす。したがって、Ｑ＝ｄＰである。
上記スカラー倍におけるメモリ使用量は、前計算部３０３の前計算テーブルの大きさにより定まる。上記スカラー倍計算方法では、前計算テーブルはＰ，３Ｐ，…，（２ｗ−１）Ｐのみ、すなわち奇数倍の点のみを格納すればよいので、その点の数は２ｗ−１個である。文献２の方法では、ウィンドウ幅ｗに対して、２ｗ個の点を格納する必要がある。そのため、上記スカラー倍計算方法は、文献２の方法と比べて格納する点の数が少なく、メモリ使用量が小さくてすむ。
さらに、いかなる方法をもってしても、前計算テーブルに格納する点の数をこれ以上削減することができないという意味で、メモリ使用量は最小である。この理由は次の通りである。
ｍ個の点からなる前計算テーブルを用いた場合、ｋ＋１個のｕ［ｉ］を用いて、エンコードされたスカラー値として表すことのできる数は（２ｍ）ｋ＋１個である。他方、ｎビット以下のスカラー値は全部で２ｎ個あり、各々のスカラー値はそれぞれ異なる数値列にエンコードされなければならない。そのため、（２ｍ）ｋ＋１≧２ｎが成り立つ。ｋ＋１＝ｎ／ｗであるので、ｍ≧２ｗ−１となる。実際、上記スカラー倍計算方法における前計算テーブルの点の個数は２ｗ−１であり、最小である。
また、上記スカラー倍方法は、サイドチャネル攻撃に対する防御法に関しても有効である。この理由は次の通りである。
エンコード部３０２によりスカラー値ｄは数値列ｄｗ［ｊ］にエンコードされる。この数値列ｄｗ［ｊ］は固定されたパターン
2004070681.tif 000019
をもつ。ここで各ｘは各々非０の値であり、それぞれｄｗ［ｉｗ］に対応する。そのため、実計算部３０４がスカラー倍点を計算する際に、ステップ６１３−６１７の繰り返し処理において、｜０…０ｘ｜のブロックに対応する楕円曲線演算は、｜Ｄ…ＤＡ｜、すなわちｗ回のＤの後にＡとなる。ただし、ＤはＥＣＤＢＬを、ＡはＥＣＡＤＤをそれぞれ表す。したがって、全てのスカラー値に対して、実行する楕円曲線演算は、
2004070681.tif 000020
となり、必ず楕円加算が実行されるので、スカラー値との依存関係がない。
なお、文献１のランダム化射影座標を併用してスカラー倍計算を行ってもよい。そうすると、同じ点Ｐを入力しても実行毎に異なる値に変換してスカラー倍計算を行うので、攻撃者が中間値の値を予測できなくなる。
また、前計算テーブルに格納されている点が読み出されるたびに、再びランダム化して、前計算テーブルに書き込んでもよい。そうすると、同じデータの再使用がなくなるため、より一層、サイドチャネル攻撃への耐性が増す。
以上の通り、上記計算方法は、サイドチャネル攻撃に有用な情報を与えないので、サイドチャネル攻撃に対して耐性がある。また、奇数倍の点のみを前計算テーブルとして格納するため、メモリ使用量が小さくてすむという特徴がある。
なお、上記計算方法では楕円曲線としてワイエルシュトラス型楕円曲線を用いたが、標数２の有限体上で定義された楕円曲線や、ＯＥＦ（Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄ）上で定義された楕円曲線、もしくはモンゴメリ型楕円曲線を用いてもよい。ＯＥＦについては、Ｄ．Ｖ．Ｂａｉｌｅｙ，Ｃ．Ｐａａｒ，Ｏｐｔｉｍａｌ  Ｅｘｔｅｎｓｉｏｎ  Ｆｉｅｌｄｓ  ｆｏｒ  Ｆａｓｔ  Ａｒｉｔｈｍｅｔｉｃ  ｉｎ  Ｐｕｂｌｉｃ−Ｋｅｙ  Ａｌｇｏｒｉｔｈｍｓ，Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  Ｃｒｙｐｔｏ  ’９８，ＬＮＣＳ  １４６２，（１９９８），４７２−４８５．（文献５）に記載されている。
以上、コンピュータＢ１２１が、暗号化されたデータ１４１を復号化する場合のスカラー倍計算部１３５の動作を説明したが、コンピュータＡ１０１が入力メッセージを暗号化する場合も同様である。
その場合には、コンピュータＡ１０１のスカラー倍計算部１１５は、既に説明した楕円曲線上の点Ｑ、乱数ｋによるスカラー倍点ｋＱと、公開鍵ａＱと乱数ｋによるスカラー倍点ｋ（ａＱ）を出力する。このとき、上記計算方法で説明したスカラー値ｄを乱数ｋ、楕円曲線上の点Ｐを楕円曲線上の点Ｑ、公開鍵ａＱとして同様の処理を行うことにより、それぞれのスカラー倍点を求めることができる。
次に本発明を署名検証システムに適用する実施例を、図７と図２を用いて説明する。
図７の署名検証システムは、スマートカード７０１と署名検証処理を行うコンピュータ７２１とから成る。
スマートカード７０１は、機能としてはコンピュータＡ１０１と類似の構成を備えるが、ＣＰＵ１１３やコプロセッサ１１４などの演算装置とが記憶部１０２に格納されているプログラムを実行することにより、データ処理部１１２ではなく、署名生成処理部７１２を実現する。ただし、外部記憶装置、ディスプレイ、キーボードを備えない。
コンピュータ７２１は、コンピュータＡ１０１と同様の構成を備えるが、ＣＰＵ１１３がプログラムを実行することによりデータ処理部１１２ではなく、署名検証処理部７３２を実現する。
スカラー倍計算部７１５と７３５は、図１に示すスカラー倍計算部１１５または１３５と同様の機能を備える。
なお、本実施例において、コンピュータ７２１内の各プログラムは、あらかじめ、上記コンピュータ内の記憶部に格納されていても良いし、必要なときに、コンピュータ７２１が利用可能な媒体を介して他の装置から上記記憶部に導入されてもよい。
さらに、スマートカード内の各プログラムは、あらかじめ、上記スマートカード内の記憶部に格納されていても良いし、必要なときに、入出力インタフェースを介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。
媒体とは、たとえば当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
図７の署名検証システムにおける署名作成と署名検証動作を、図２を参照して説明する。
コンピュータ７２１は、ランダムに選んだ数値をチャレンジコード７４３として、インタフェース７４２を介してスマートカード７０１に転送する。
署名生成処理部７１２（図２の１１２）は、チャレンジコード７４３を受け付け、チャレンジコード７４３のハッシュ値をとり、所定のビット長の数値ｆに変換する。
署名生成処理部７１２は、乱数ｕを生成し、記憶部７０２（図２の１０２）に格納されている定数７０４から読み出した（図２の２０５）楕円曲線上の定点Ｑとともにスカラー倍計算部７１５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部７１５は、定点Ｑ、乱数ｕによるスカラー倍点（ｘｕ，ｙｕ）を計算し、計算されたスカラー倍点を署名生成処理部７１２へ送る（図２の２０７）。
署名生成処理部７１２は、送られたスカラー倍点を用いて署名の生成を行う。例えば、ＥＣＤＳＡ署名であれば、
2004070681.tif 000021
を計算することによりチャレンジコード７４３に対応する署名（ｓ，ｔ）を得る（図２の２０８）。
ここで、ｑは定点Ｑの位数、すなわち定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
ＥＣＤＳＡ署名については、ＡＮＳＩ  Ｘ９．６２  Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｒｙｐｔｏｇｒａｐｈｙ  ｆｏｒ  ｔｈｅ  Ｆｉｎａｎｃｉａｌ  Ｓｅｒｖｉｃｅｓ  Ｉｎｄｕｓｔｒｙ，Ｔｈｅ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｄｉｇｉｔａｌ  Ｓｉｇｎａｔｕｒｅ  Ａｌｇｏｒｉｔｈｍ（ＥＣＤＳＡ），（１９９９）（文献６）に記載されている。
スマートカード７０１は、署名生成処理部７１２で作成した署名７４１を入出力インタフェース７１０より出力し、インタフェース７４２を介してコンピュータ７２１へ転送する。
コンピュータ７２１の署名検証処理部７３２（図２の１１２）は、署名７４１が入力される（図２の２０４）と、署名７４１の数値ｓ，ｔが適切な範囲内すなわち１≦ｓ，ｔ＜ｑであるかを調べる。
数値ｓ，ｔが上記範囲内になければチャレンジコード７４３に対する署名の検証結果として「無効」を出力し、スマートカード７０１を拒絶する。数値ｓ，ｔが上記範囲内にあれば、署名検証処理部７３２は、
2004070681.tif 000022
を計算する。そして、記憶部７２２（図２の１０２）に格納されている定数７２４から読み出した（図２の２０５）公開鍵ａＱ及び定点Ｑと計算したｈ１，ｈ２をスカラー倍計算部７３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部７３５は、定点Ｑとｈ１によるスカラー倍点ｈ１Ｑと、公開鍵ａＱとｈ２によるスカラー倍点ｈ２ａＱとを計算し、計算されたスカラー倍点を署名検証処理部７３２へ送る（図２の２０７）。
署名検証処理部７３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡの署名検証であれば、点Ｒ
2004070681.tif 000023
を計算し、そのｘ座標をｘＲとしたとき、
2004070681.tif 000024
を計算し、ｓ’＝ｓであればチャレンジコード７４３に対する署名の検証結果として「有効」を出力し、スマートカード７０１を認証し、受け入れる（図２の２０８）。
ｓ’＝ｓでなければ「無効」を出力し、スマートカードを拒絶する（図２の２０８）。
上記実施形態のスカラー倍計算部７１５、７３５は、図１のスカラー倍計算部１１５または１３５と同様の機能を備えるので、サイドチャネル攻撃を防ぎ且つメモリ使用量の少ないスカラー倍計算を実行できる。
そのためスマートカード７０１は署名作成処理を行う際に、コンピュータ７２１は署名検証処理を行う際に、サイドチャネル攻撃を防ぎ、その上少ないメモリ使用量で実行できる。
次に本発明を鍵交換システムに適用する例を説明する。本実施形態においては、図１のシステム構成が応用できる。
図１のデータ処理部１１２、１３２は、本実施形態においては、それぞれ鍵交換処理部１１２、１３２として機能する。
鍵交換システムのコンピュータＡ１０１が、入力されたデータ１４３から共有情報の導出を行う場合の動作について図１、図２を参照して説明する。
コンピュータＢ１２１のデータ処理部１３２（図２の１１２）は、記憶部１２２（図２の１０２）の定数１２５から秘密鍵ｂを読み出しコンピュータＢ１２１の公開鍵ｂＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｂＱをデータ１４３としてコンピュータＡ１０１に転送する。
コンピュータＡ１０１の鍵交換処理部１１２（図２の１１２）はコンピュータＢ１２１の公開鍵ｂＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１１２は、記憶部１０２から読み出した（図２の２０５）秘密情報１０５であるコンピュータＡ１０１の秘密鍵ａと、コンピュータＢ１２１の公開鍵ｂＱとをスカラー倍計算部１１５へ送る（図２の２０６）。
スカラー倍計算部１１５は、秘密鍵ａと、公開鍵ｂＱによるスカラー倍点ａｂＱを計算し、計算されたスカラー倍点を鍵交換処理部１１２へ送る（図２の２０７）。
鍵交換処理部１１２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１０２に秘密情報１０５として格納する。例えば、スカラー倍点ａｂＱのｘ座標を、共有情報とする。
次に、コンピュータ１２１が、入力されたデータ１４１から共有情報の導出を行う場合の動作について説明する。
コンピュータＡ１０１のデータ処理部１１２は、記憶部１０２の定数１０５から秘密鍵ａを読み出しコンピュータＡ１０１の公開鍵ａＱを計算する。そして、ネットワーク１４２を介して、公開鍵ａＱをデータ１４１としてコンピュータＢ１２１に転送する。
コンピュータＢ１２１の鍵交換処理部１３２（図２の１１２）はコンピュータＡ１０１の公開鍵ａＱの入力を受け付ける（図２の２０４）と、鍵交換処理部１３２は、記憶部１２２（図２の１０２）の定数１２５から読み出した（図２の２０５）秘密情報１２５であるコンピュータＢ１２１の秘密鍵ｂと、コンピュータＡ１０１の公開鍵ａＱとをスカラー倍計算部１３５（図２の１１５）へ送る（図２の２０６）。
スカラー倍計算部１３５は、秘密鍵ｂと、公開鍵ａＱによるスカラー倍点ｂａＱを計算し、計算されたスカラー倍点を鍵交換処理部１３２へ送る（図２の２０７）。
鍵交換処理部１３２は、送られたスカラー倍点を用いて共有情報の導出を行い、記憶部１２２に秘密情報１２５として格納する。例えば、スカラー倍点ｂａＱのｘ座標を、共有情報とする。
ここで、数ａｂと数ｂａは数値として同じなので、点ａｂＱと点ｂａＱは同じ点となり、同じ情報が導出されたことになる。
ネットワーク１４２には、点ａＱと点ｂＱが送信されるが、点ａｂＱ（もしくは点ｂａＱ）を計算するには秘密鍵ａもしくは秘密鍵ｂを用いなければならない。すなわち、秘密鍵ａもしくは秘密鍵ｂを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
本実施形態においても、スカラー倍計算部１１５、１３５は、上述の特徴を備えるので、サイドチャネル攻撃を防ぎ、そのうえ少ないメモリ使用量で鍵交換処理が可能になる。
また、上記各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現しても良い。
また、データ処理部は、上記暗号化処理、復号化処理、署名作成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
本発明によれば、サイドチャネル攻撃に対して安全で、かつメモリ使用量の少ない、楕円曲線演算を用いたメッセージ処理が可能になる。
【図１】
2004070681.tif 000025
【図２】
2004070681.tif 000026
【図３】
2004070681.tif 000027
【図４】
2004070681.tif 000028
【図５】
2004070681.tif 000029
【図６】
2004070681.tif 000030
【図７】
2004070681.tif 000031