(57)【要約】      （修正有）【課題】楕円曲線暗号は、楕円曲線上の離散対数問題を利用しており、鍵長を比較的短くでき、計算能力・メモリ容量などのリソースが比較的少ない環境でも暗号処理を行う事ができるが、さらなる効率化が求められている。すなわち、処理で最も計算リソースを必要とする楕円曲線スカラー倍計算を高速かつ効率的に行う楕円曲線スカラー倍計算方法を提供する。【解決手段】事前計算テーブルを利用した楕円曲線スカラー倍計算において、事前計算テーブル作成時に、逆元計算の分母を変換することにより、逆元計算回数を削減する。これにより、楕円曲線スカラー倍計算を効率的に実行する。【選択図】図８
2007212768.tif 000002
【特許請求の範囲】
【請求項１】
楕円曲線演算を用いてデータを変換する変換装置において、スカラー値および楕円曲線上のベースとなる点（ベース点）とからスカラー倍を計算するスカラー倍計算のために、入力された前記ベース点から所定数のスカラー倍計算を行って楕円点として保持する事前計算テーブルを作成する楕円曲線暗号における事前計算テーブル作成装置であって、
前記ベース点から前記楕円点を計算する際に必要となる逆元計算の分母を変換し、変換分母として出力する分母変換手段と、
前記変換分母を集約して逆元計算を行った後に展開して同時逆元計算結果として出力する同時逆元計算手段と、
前記同時逆元計算結果を、前記楕円曲線上の前記ベース点から前記スカラー倍を計算する際に必要な逆元計算結果に復元し復元分母として出力する分母復元手段と、
前記復元分母を用いて前記楕円点を計算して出力する楕円点計算手段と、
前記計算した楕円点を前記事前計算テーブルに格納する事前計算テーブル生成手段と、を備えること
を特徴とする事前計算テーブル作成装置。
【請求項２】
請求項１記載の事前計算テーブル作成装置であって、
前記分母変換手段における変換は、
変換前の分母をδ１，  δ２，...，  δｋとし、変換分母をｄ１，ｄ２，...，ｄｋとすると、
変換分母がそれぞれ、
ｄ１＝δ１
ｄｉ＝（ｄ１ｄ２...ｄｉ−１）２δｉ（ｉ＝２，３，...，ｋ）
と表される変換であること
を特徴とする事前計算テーブル作成装置。
【請求項３】
請求項１または２記載の事前計算テーブル作成装置であって、
既に計算した複数の楕円点を用いて次の楕円点群をモンゴメリトリックの手法を利用して並列に計算することを繰り返す前計算手段をさらに備えること
を特徴とする事前計算テーブル作成装置。
【請求項４】
請求項１から３いずれか１項記載の事前計算テーブル作成装置であって、
前記楕円曲線として、素体上の楕円曲線またはバイナリ曲線を用いること
を特徴とする事前計算テーブル作成装置。
【請求項５】
楕円曲線演算を用いてデータを変換する変換装置において、スカラー値と楕円曲線上のベースとなる点（ベース点）からスカラー倍を計算するスカラー倍計算装置であって、
請求項１から４のいずれか１項記載の事前計算テーブル作成装置を用いて作成した事前計算テーブルを用いて前記ベース点のスカラー倍を計算すること
を特徴とするスカラー倍計算装置。
【請求項６】
楕円曲線演算を用いてメッセージを暗号化する暗号化装置であって、
請求項５記載のスカラー倍計算装置を用いてスカラー値と楕円曲線上のベースとなる点（ベース点）から前記楕円曲線演算におけるスカラー倍計算を行うこと
を特徴とする暗号化装置。
【請求項７】
暗号化されたデータを楕円曲線演算を用いて復号する復号化装置であって、
請求項５記載のスカラー倍計算装置を用いてスカラー値と楕円曲線上のベースとなる点（ベース点）から前記楕円曲線演算におけるスカラー倍計算を行うこと
を特徴とする復号化装置。
【請求項８】
請求項６の暗号化装置と請求項７の復号化装置とを備える暗号通信システム。
【請求項９】
楕円曲線演算を用いてデータからディジタル署名データを生成する署名生成装置であって、
請求項５記載のスカラー倍計算装置を用いてスカラー値と楕円曲線上のベースとなる点（ベース点）から前記楕円曲線演算におけるスカラー倍計算を行うこと
を特徴とする署名生成装置。
【請求項１０】
楕円曲線演算を用いて、データと署名データとから署名の正当性を検証する署名検証装置であって、
請求項５記載のスカラー倍計算装置を用いてスカラー値と楕円曲線上のベースとなる点（ベース点）から前記楕円曲線演算におけるスカラー倍計算を行うこと
を特徴とする署名検証装置。
【請求項１１】
第一の処理装置と第二の処理装置との間でデータを共有するデータ共有システムであって、
前記第一の処理装置と前記第二の処理装置とはそれぞれ、
自身の秘密鍵をスカラー値として楕円曲線上のベースとなる点（ベース点）のスカラー倍計算を行いスカラー倍点を算出する送出情報生成手段と、
前記算出したスカラー倍点を送出するとともに、他方の処理装置から送出された前記スカラー倍点を受信する入出力手段と、
自身の秘密鍵をスカラー値として前記入出力手段で受け取ったスカラー倍点のスカラー倍計算を行い共有情報を算出する共有情報算出手段と、を備え、
前記送出情報生成手段および前記共有情報算出手段におけるスカラー倍計算は、前記請求項５のスカラー倍装置を用いて行うこと
を特徴とするデータ共有システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はセキュリティ技術に係り、特に楕円曲線演算を用いてメッセージを処理し、暗号通信や電子情報の認証を行う技術に関する。
【背景技術】
【０００２】
情報通信ネットワークの進展に伴い、電子情報の秘匿や認証の為に暗号技術は不可欠な要素となってきている。暗号技術には，共通鍵暗号と公開鍵暗号があり、楕円曲線暗号は、Ｎ．Ｋｏｂｌｉｔｚ，Ｖ．Ｓ．Ｍｉｌｌｅｒにより提案された公開鍵暗号の１種である。公開鍵暗号には、公開鍵（Ｐｕｂｌｉｃ  Ｋｅｙ）と呼ばれる一般に公開してよい情報と、秘密鍵（Ｐｒｉｖａｔｅ  Ｋｅｙ）と呼ばれる秘匿しなければならない秘密情報がある。平文メッセージの暗号化や署名の検証には公開鍵を用い、暗号文メッセージの復号化や署名の生成には秘密鍵を用いる。
【０００３】
楕円曲線暗号の安全性は楕円曲線上の離散対数問題の求解が困難であることに由来している。楕円曲線上の離散対数問題とは、楕円曲線上のある点Ｐとそのスカラー倍の点ｍＰが与えられた時、スカラー値ｍを求める問題である。楕円曲線暗号における秘密鍵は、このスカラー値ｍが担っている。
【０００４】
楕円曲線上の点（または楕円点）とは、楕円曲線の定義式を満たす数の組をいい、楕円曲線上の点全体には、無限遠点という仮想的な点を単位元とした演算、すなわち楕円曲線上の加法（または加算）が定義される。そして、ある点に対し、特定の回数だけ加法を行うことをスカラー倍といい、その結果をスカラー倍点、その回数のことをスカラー値という。
【０００５】
なお、同じ点同士による楕円曲線上の加法のことを、特に、楕円曲線上の２倍算という。また、楕円曲線上の加算、２倍算は、それぞれ、楕円加算、楕円２倍算とも呼ばれる。
【０００６】
楕円曲線上の２点の加法（楕円加算）は次のようにして計算される。２点を通る直線を引くとその直線は楕円曲線と他の点において交わる。その交わった点とｘ軸に関して対称な点を、加法を行った結果の点とする。例えば、素体上の楕円曲線の場合には、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）との加算（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は、
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１）      （式１）
ｘ３＝λ２−ｘ１−ｘ２                  （式２）
ｙ３＝λ（ｘ１−ｘ３）−ｙ１            （式３）
を計算することにより得られる。
【０００７】
なお、素体上の楕円曲線の定義式は、
ｙ２＝ｘ３＋ａｘ＋ｂ  ｍｏｄ  ｐ        （式４）
で与えられる。ここでａ，ｂは定数、ｐは対応する有限体（素体）の素数である。すなわち、式４のｘ、ｙに、各々ｘｉ、ｙｉ（ｉ＝１，２，３）を代入した場合、式４の等式が成り立つ。
【０００８】
また、楕円曲線上の点の２倍算（楕円２倍算）は次のようにして計算される。楕円曲線上の点における接線を引くと、その接線は楕円曲線上の他の一点において交わる。その交わった点とｘ軸に関して対象な点を、２倍算を行った結果の点とする。例えば、素体上の楕円曲線の場合には、点（ｘ１，ｙ１）の２倍算を行った結果（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は、
λ＝（３ｘ１２＋ａ）／（２ｙ１）        （式５）
を計算し、このλを用いて式２、式３で与えられるｘ３，ｙ３を計算することにより得られる。
【０００９】
このように、楕円加算、楕円２倍算では、式１、式５のλを計算する際に逆元計算が必要となる。
【００１０】
楕円曲線暗号において、与えられたメッセージの暗号化、復号化、署名の作成またはその検証等の各処理において、最もリソースを必要とする計算は、上述の楕円曲線上のスカラー倍計算（以下、楕円曲線スカラー倍計算と呼ぶ。）である。そのため、楕円曲線暗号を効率的に実行するためには、楕円曲線スカラー倍計算を効率的に行う必要がある。
【００１１】
楕円曲線スカラー倍計算を効率的に行うものとして、スカラー値がさほど大きくない楕円曲線スカラー倍計算を予め行い、その結果を格納した事前計算テーブルを用いるものがある（例えば、非特許文献１参照。）。非特許文献１に開示されている手法によれば、楕円曲線スカラー倍計算を高速化できる。
【００１２】
また、楕円曲線スカラー倍計算は、楕円加算、楕円２倍算を組み合わせて行う。楕円加算、楕円２倍算には、上述のように逆元計算が必要であり、この逆元計算は、処理負担が重いことが知られている。このため、楕円曲線スカラー倍計算を効率的に行うものとして、逆元計算の回数を削減する手法が提案されている（例えば、非特許文献２、非特許文献３参照。）。非特許文献２には、ある逆元の出力結果が別の逆元計算の入力の一部として用いられた場合、逆元計算をまとめて行い、計算回数を削減する手法が提案されている。また、非特許文献３には、事前計算テーブル作成時の逆元計算をまとめて行い、計算回数を削減する手法が提案されている。
【００１３】
【非特許文献１】Ｏｋｅｙａ，  Ｋ．，  Ｓｃｈｍｉｄｔ−Ｓａｍｏａ，  Ｋ．，  Ｓｐａｈｎ，  Ｃ．，  Ｔａｋａｇｉ，  Ｔ．，  “Ｓｉｇｎｅｄ  Ｂｉｎａｒｙ  Ｒｅｐｒｅｓｅｎｔａｔｉｏｎｓ  Ｒｅｖｉｓｉｔｅｄ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＣＲＹＰＴＯ  ２００４，  ＬＮＣＳ  ３１５２，  （２００４），  ｐｐ．１２３−１３９．
【非特許文献２】Ｃｉｅｔ，  Ｍ．，  Ｊｏｙｅ，  Ｍ．，  Ｌａｕｔｅｒ，  Ｋ．，  Ｍｏｎｔｇｏｍｅｒｙ，  Ｐ．Ｌ．，  “Ｔｒａｄｉｎｇ  Ｉｎｖｅｒｓｉｏｎｓ  ｆｏｒ  Ｍｕｌｔｉｐｌｉｃａｔｉｏｎｓ  ｉｎ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｃｒｙｐｔｏｇｒａｐｈｙ，”  Ｃｒｙｐｔｏｌｏｇｙ  ｅＰｒｉｎｔ  Ａｒｃｈｉｖｅ，  Ｒｅｐｏｒｔ  ２００３／２５７，  （２００３）．［平成１８年２月２日検索］インターネット＜ＵＲＬ：ｈｔｔｐ：／／ｅｐｒｉｎｔ．ｉａｃｒ．ｏｒｇ／２００３／２５７．ｐｄｆ＞
【非特許文献３】Ｃｏｈｅｎ，  Ｈ．，  Ｍｉｙａｊｉ，  Ａ．，  Ｏｎｏ，  Ｔ．，  “Ｅｆｆｉｃｉｅｎｔ  Ｅｌｌｉｐｔｉｃ  Ｃｕｒｖｅ  Ｅｘｐｏｎｅｎｔｉａｔｉｏｎ  Ｕｓｉｎｇ  Ｍｉｘｅｄ  Ｃｏｏｒｄｉｎａｔｅｓ，”  Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＡＳＩＡＣＲＹＰＴ  ’９８，  ＬＮＣＳ１５１４，  （１９９８），  ｐｐ．５１−６５．
【発明の開示】
【発明が解決しようとする課題】
【００１４】
暗号技術に課せられる要件には、安全性、処理速度、少ないメモリ使用量などがある。しかし、一般的に安全性、処理速度、メモリ使用量の間にはトレードオフの関係があり、全ての要件を満たすことは難しい。
【００１５】
楕円曲線暗号は、楕円曲線上の離散対数問題が非常に困難であることを利用している。このため、素因数分解の困難性を安全性の根拠にしている公開鍵暗号に比べて、楕円曲線暗号は公開鍵、秘密鍵の鍵長を比較的短くすることができ、計算能力、メモリ容量などのリソースが比較的少ない環境であっても暗号処理を行うことが可能である。しかし、昨今用いられているスマートカード（ＩＣカードともいう）等においては、利用可能なリソースが極めて限られているため、暗号処理の更なる効率化、すなわち、処理速度を犠牲にせずにメモリ使用量や計算負担を改善することが求められている。
【００１６】
非特許文献１に開示されている技術は、楕円曲線スカラー倍計算を行う際、事前計算テーブルを用いることにより処理速度を改善しているが、事前計算テーブルの作成時には、依然、処理負担の大きい逆元計算が必要である。
【００１７】
非特許文献２および非特許文献３には、楕円曲線スカラー倍計算を行う際の逆元計算の回数を削減する手法が開示されている。しかし、非特許文献２に開示されている技術は、事前計算テーブル作成への適用については考察されていない。また、非特許文献３に開示されている技術は、各々の逆元計算への入力が独立に与えられた場合にのみ逆元計算の回数を削減することができる。このため、特殊な方法で事前計算テーブルを生成する場合にのみ適用が可能という制約があり、ある逆元計算の出力結果を別の逆元計算の入力の一部として用いるといった一般的な方法での事前計算テーブルを生成する場合には適用できない。
【００１８】
本発明は、上記事情に鑑みてなされたもので、楕円曲線暗号を用いてメッセージ等のデータを暗号化、復号化するにあたり、楕円曲線スカラー倍計算を効率的に実行することが可能な技術、特に、高速かつ低負担の楕円曲線スカラー倍計算を実現する技術を提供する。
【課題を解決するための手段】
【００１９】
本発明は、事前計算テーブルを利用した楕円曲線スカラー倍計算において、事前計算テーブル作成時の逆元計算回数を削減する。
【００２０】
具体的には、楕円曲線演算を用いてデータを変換する変換装置において、スカラー値および楕円曲線上のベースとなる点（ベース点）とからスカラー倍を計算するスカラー倍計算のために、入力された前記ベース点から所定数のスカラー倍計算を行って楕円点として保持する事前計算テーブルを作成する楕円曲線暗号における事前計算テーブル作成装置であって、前記ベース点から前記楕円点を計算する際に必要となる逆元計算の分母を変換し、変換分母として出力する分母変換手段と、前記変換分母を集約して逆元計算を行った後に展開して同時逆元計算結果として出力する同時逆元計算手段と、前記同時逆元計算結果を、前記楕円曲線上の前記ベース点から前記スカラー倍を計算する際に必要な逆元計算結果に復元し復元分母として出力する分母復元手段と、前記復元分母を用いて前記楕円点を計算して出力する楕円点計算手段と、前記計算した楕円点を前記事前計算テーブルに格納する事前計算テーブル生成手段と、を備えることを特徴とする事前計算テーブル作成装置提供する。
【発明の効果】
【００２１】
本発明によれば、楕円曲線暗号を用いてメッセージなどのデータを暗号化、復号化するにあたり、楕円曲線スカラー倍計算を効率的に実行することができる。従って、高速かつ低負担の楕円曲線暗号処理を用いたシステムを実現することができる。
【発明を実施するための最良の形態】
【００２２】
＜＜第一の実施形態＞＞
以下、本発明を適用した実施形態を図面を用いて説明する。本実施形態は、本発明を暗号通信システムに適用したものである。そして、楕円曲線として素体上の楕円曲線を用いる。
【００２３】
図１は、本発明を適用した本実施形態の暗号通信システムのシステム構成図である。本図に示すように、本実施形態の暗号通信システムは、本実施形態の楕円曲線暗号技術をそれぞれ適用したコンピュータＡ１０１およびコンピュータＢ１２１がネットワーク１４２により接続されている。コンピュータＡ１０１は、入力されたメッセージの暗号化を行い、暗号化されたメッセージ（暗号文）をデータ１４１として出力する。コンピュータＢ１２１は、入力された暗号文１４１の復号を行う。コンピュータＢ１２１からは、例えば、公開鍵、暗号化データの送信要求などがデータ１４３として出力される。
【００２４】
本実施形態の暗号通信システムにおけるメッセージの暗号化および復号の概略を説明する。
【００２５】
コンピュータＡ１０１では、メッセージＭの暗号化を、Ｃ１＝ＰＭ＋ｒ（ｕＱ）及びＣ２＝ｒＱを計算することにより行う。また、コンピュータＢ１２１では、暗号文（Ｃ１、Ｃ２）の復号を、秘密鍵ｕを用いて−ｕＣ２を計算し、
Ｃ１−ｕＣ２＝（ＰＭ＋ｒ（ｕＱ））−ｕ（ｒＱ）＝ＰＭ      （式６）
を計算することにより行う。ここでＰＭはメッセージＭに対応する楕円点、ｒは乱数、ｕは秘密鍵を示す定数、Ｑは楕円曲線上の定点、ｕＱは公開鍵を示す点である。
【００２６】
本実施形態の暗号通信システムでは、ネットワーク１４２上には、暗号文（Ｃ１、Ｃ２）のみ送信される。暗号文（Ｃ１、Ｃ２）からメッセージＭを復元するためには、上述のようにＰＭを計算する。ＰＭを計算するためには、ｒｕＱ、すなわち、Ｃ２のｕ倍を計算する必要がある。ところが、秘密鍵ｕはネットワーク１４２には送信されないため、秘密鍵ｕを保持している者だけが、ＰＭを計算でき、すなわち、メッセージＭを復元することができる。
【００２７】
次に、本実施形態の暗号通信システムを構成するコンピュータＡ１０１およびＢ１２１それぞれの構成を説明する。
【００２８】
コンピュータＡ１０１は、ＣＰＵ１１３、コプロセッサ１１４などの演算装置、ＲＡＭ１０３、ＲＯＭ１０６、外部記憶装置１０７などの記憶装置、コンピュータＡ１０１の外部とのデータ入出力を行なう入出力インタフェース１１０を装備し、外部にはコンピュータＡ１０１をユーザが操作するためのディスプレイ１０８、キーボード１０９、着脱可能な可搬型記憶媒体の読み書き装置などが接続される。
【００２９】
コンピュータＡ１０１は、ＲＡＭ１０３、ＲＯＭ１０６や外部記憶装置１０７などの記憶装置によって、記憶部１０２を実現し、ＣＰＵ１１３やコプロセッサ１１４などの演算装置が、記憶部１０２に格納されたプログラムを実行することにより、データ処理部１１２、スカラー倍計算部１１５およびそれらに含まれる各処理部を実現する。なお、コプロセッサ１１４は特殊用途用の計算装置であり、スカラー倍計算などの算術演算を行う。
【００３０】
データ処理部１１２は、本実施形態では暗号化処理部として機能し、入力されたメッセージＭの暗号化を行なう。スカラー倍計算部１１５は、データ処理部（暗号化処理部）１１２で暗号化を行なうのに必要なパラメタを計算する。
【００３１】
記憶部１０２は、ＲＡＭ１０３に、定数１０４、秘密情報１０５（例えば、秘密鍵である）などを記憶する。ＲＡＭ１０３が記憶する定数１０４には、例えば、楕円曲線の定義式、対応する有限体における標数や既約多項式などの定数や、楕円曲線上の定点などがある。また、楕円曲線パラメタと呼ばれる、楕円曲線を定める定数ａ、ｂ、対応する有限体の素数ｐなどもＲＡＭ１０３に記憶される。さらに、ＲＡＭ１０３にはデータ処理部１１２の行う計算の中間値、変数などが格納される。もちろん、これらの定数等は、ＲＯＭ１０６に記憶するよう構成してもよい。
【００３２】
コンピュータＢ１２１は、コンピュータＡ１０１と同様のハードウェア構成を備える。すなわち、ＣＰＵ１３３、コプロセッサ１３４などの演算装置、ＲＡＭ１２３、ＲＯＭ１２６、外部記憶装置１２７などの記憶装置、コンピュータＢ１２１の外部とのデータ入出力を行なう入出力インタフェース１３０を装備し、外部にはコンピュータＢ１２１をユーザが操作するためのディスプレイ１２８、キーボード１２９、着脱可能な可搬型記憶媒体の読み書き装置などが接続される。
【００３３】
コンピュータＢ１２１は、ＲＡＭ１２３、ＲＯＭ１２６や外部記憶装置１２７などの記憶装置によって、記憶部１２２を実現し、ＣＰＵ１３３やコプロセッサ１３４などの演算装置が、記憶部１２２に格納されたプログラムを実行することにより、データ処理部１３２、スカラー倍計算部１３５とそれらに含まれる各処理部を実現する。なお、コプロセッサ１３４は特殊用途用の計算装置であり、スカラー倍計算などの算術演算を行う。
【００３４】
データ処理部１３２は、本実施形態では復号化処理部として機能し、暗号化されたメッセージである暗号文１４１の復号化を行なう。スカラー倍計算部１３５は、データ処理部（復号化処理部）１３２で復号を行なうのに必要なパラメタを計算する。
【００３５】
記憶部１２２は、ＲＡＭ１２３に、定数１２４（例えば、楕円曲線の定義式、対応する有限体における標数や既約多項式などの定数や、楕円曲線上の定点である）、秘密情報１２５（例えば、秘密鍵である）などを記憶する。また、ＲＡＭ１２３にはデータ処理部１３２の行う計算の中間データ、変数などが格納される。
【００３６】
なお、上記プログラムは、予め、上記コンピュータＡ１０１、Ｂ１２１内の記憶部１０２、１２２に格納されていてもよいし、必要なときに、入出力インタフェース１１０、１３０と上記コンピュータＡ１０１、Ｂ１２１が利用可能な媒体を介して、他の装置から上記記憶媒部１０２、１２２に導入されてもよい、媒体とは、例えば、入出力インタフェース１１０、１３０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【００３７】
次に、図１の暗号通信システムにおいて、コンピュータＡ１０１が入力されたメッセージを暗号化する場合の動作およびコンピュータＢ１２１が入力された暗号文を復号する場合の動作について説明する。図２は、メッセージＭが入力された際のコンピュータＡ１０１および暗号文が入力された際のコンピュータＢ１２１それぞれの各処理部間の情報の受け渡しの様子を示すシーケンス図である。なお、メッセージはディジタル化されたデータであればよく、テキスト、画像、映像、音などの種類は問わない。
【００３８】
まず、コンピュータＡ１０１が入力されたメッセージを暗号化する場合の動作について説明する。
【００３９】
データ処理部（暗号化処理部）１１２は、入出力インタフェース１１０を介して、平文のメッセージＭを入力メッセージとして受け取ると（２０１）、入力されたメッセージＭのビット長が予め定めたビット長か否かを判断する。予め定めたビット長よりも長い場合には、予め定めたビット長となるようにメッセージＭを区切る。以下、所定のビット長に区切られている部分メッセージ（以下、単にメッセージともいう）に対する暗号化処理時の動作を説明する。
【００４０】
データ処理部（暗号化処理部）１１２は、メッセージのビット列によって表される数値をｘ座標（ｘ１）に持つ楕円点ＰＭのｙ座標（ｙ１）の値を計算する。
【００４１】
素体上の楕円曲線の場合、ａ，ｂを定数とすると、
ｙ１２＝ｘ１３＋ａｘ１＋ｂ                  （式７）
で表される。上記式を用いてｙ座標の値を求めることができる。
【００４２】
次に、データ処理部（暗号化処理部）１１２は、乱数ｒを生成する。また、データ処理部（暗号化処理部）１１２は、記憶部１０２に格納されている定数１０４から秘密鍵ｕ、公開鍵ｕＱ、楕円曲線パラメタ、楕円曲線上の定点Ｑであるベース点を読み出す（２０２）。
【００４３】
データ処理部（暗号化処理部）１１２は、乱数ｒを生成してスカラー値とし、また、利用可能なメモリ容量に応じてウィンドウ幅ｗを設定する。そして、ベース点Ｑ、スカラー値ｒ、ウィンドウ幅ｗを、スカラー倍計算部１１５へ送る（２０３）。
【００４４】
スカラー倍計算部１１５は、スカラー値ｒ（乱数ｒ）による定点Ｑのスカラー倍点ｒＱ（＝（ｘｒＱ，ｙｒＱ））と、公開鍵ｕＱのスカラー値ｒ（乱数ｒ）によるスカラー倍点ｒ（ｕＱ）とを、ウィンドウ幅ｗに応じた事前計算テーブルを利用して計算し、計算されたスカラー倍点ｒＱおよびｒ（ｕＱ）をデータ処理部（暗号化処理部）１１２へ送る（２０４）。
【００４５】
データ処理部（暗号化処理部）１１２は、送られたスカラー倍点ｒＱおよびｒ（ｕＱ）を用いて、暗号化処理を行なう。ここでは、Ｃ１＝ＰＭ＋ｒ（ｕＱ）およびＣ２＝ｒＱを計算する。この計算は、例えば式１、式２、式３に示す楕円曲線の加算公式を利用することにより計算できる。そして、暗号化されたメッセージＣ１、Ｃ２を得る。得られた各部分メッセージの暗号化されたメッセージＣ１、Ｃ２は一時的に記憶部１０２に格納される。
【００４６】
メッセージＭの全ての部分メッセージについての暗号化が終了すると、コンピュータＡ１０１の処理部１１１は暗号化された１つ以上の部分メッセージから暗号化された出力メッセージを組み立てる。そして、処理部１１１は、組み立てた出力メッセージをデータ１４１として入出力インタフェース１１０より出力し（２０５）、ネットワーク１４２を介してコンピュータＢ１２１へ転送する。
【００４７】
なお、記憶部１０２からの情報読出し（上記２０２）は、データ処理部（暗号化処理部）１１２がスカラー倍計算部１１５へ当該当情報を送る前であれば、入力メッセージを受付ける（上記２０１）前であってもよい。
【００４８】
次に、コンピュータＢ１２１が、暗号化されたメッセージ（暗号文）であるデータ１４１を復号する場合の動作について、同じく図２を参照しつつ説明する。
【００４９】
データ処理部（復号化処理部）１３２は、入出力インタフェース１１０を介して、暗号化されたメッセージ（データ１４１）を入力メッセージとして受け取ると（２０１）、データ１４１のビット長が予め定めたビット長か否かを判断する。予め定めたビット長よりも長い場合は、予め定めたビット長となるようにデータ１４１を区切る。以下、所定のビット長に区切られている部分データ（単にデータともいう）に対する復号処理時の動作を説明する。
【００５０】
データ処理部（復号化処理部）１３２は、データ１４１のビット列によって表される数値に対応する楕円点Ｃ１、Ｃ２を計算する。
【００５１】
データ処理部（復号化処理部）１３２は、記憶部１２２に格納されている秘密情報１２５から秘密鍵ｕを読み出す（２０２）。そして、点Ｃ２をベース点として、ベース点Ｃ２と秘密鍵ｕと設定したウィンドウ幅ｗとをスカラー倍計算部１３５へ送る（２０３）。
【００５２】
スカラー倍計算部１３５は、ベース点Ｃ２、秘密鍵ｕとからスカラー倍点ｕＣ２を計算する。スカラー倍計算部１３５は、計算されたスカラー倍点ｕＣ２をデータ処理部（復号化処理部）１３２へ送る（２０４）。
【００５３】
データ処理部（復号化処理部）１３２は、送られたスカラー倍点ｕＣ２を用いて、復号化処理を行う。ここでは、Ｃ１−ｕＣ２を計算する。本実施形態では、楕円曲線として素体上の楕円曲線を用いる。従って、この計算は、式１、式２、式３に示す楕円曲線の加算公式を利用して行う。計算結果の点のｘ座標（ｘ１）は、暗号化される前の部分メッセージに相当する。得られた各部分データの復号結果（部分メッセージ）は一時的に記憶部１２２に格納される。
【００５４】
データ１４１の全ての部分データについての復号が終了すると、コンピュータＢ１２１の処理部１３１は、復号された１つ以上の部分メッセージから平文メッセージを組み立てる。そして、処理部１３１は、組み立てた平文メッセージ（出力メッセージ）を、入出力インタフェース１３０を介してディスプレイ１０８などから出力する（２０５）。
【００５５】
次に、コンピュータＡ１０１が、暗号化処理を行う場合の、スカラー倍計算部１１５の処理を詳細に説明する。なお、コンピュータＢ１２１がメッセージを復号する場合のスカラー倍計算部１３５における処理も基本的に同様である。以下においては、スカラー倍計算部１１５が、スカラー値ｍ及び楕円点Ｐから、ウィンドウ幅ｗに応じた事前計算テーブルを用いて楕円曲線におけるスカラー倍点ｍＰを計算するものとする。スカラー値ｍはｎビットとする。
【００５６】
まず、スカラー倍計算部１１５の機能構成について説明する。図３は、本実施形態のスカラー倍計算部１１５の機能ブロック図である。本図に示すように、本実施形態のスカラー倍計算部１１５は、エンコード部３０１と、前計算部３０２と、実計算部３０３と、スカラー倍計算部１１５の全体を制御する制御部３０４と、を備える。また、実計算部３０３は、エンコード値判定部３３１と、楕円加算部３３２と、楕円２倍算部３３３と、繰り返し判定部３３４とを備える。
【００５７】
以下、各機能部（モジュール）の処理、モジュール間のデータの流れについて説明する。図４は、スカラー倍計算部１１５の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。
【００５８】
制御部３０４は、スカラー倍計算部１１５へ入力されたスカラー値ｍ、ベース点Ｐ、ウィンドウ幅ｗを受け取る（４０１）。制御部３０４は、ベース点Ｐおよびウィンドウ幅ｗを前計算部３０２へ送る（４０２）。
【００５９】
前計算部３０２は、ベース点Ｐおよびウィンドウ幅ｗから事前計算テーブルを作成する。事前計算テーブルには、楕円点Ｐ、３Ｐ、５Ｐ、．．．、（２ｋ−１）Ｐが格納される。ここでｋは事前計算テーブルに格納する要素数（格納要素数）を示す値であり、ウィンドウ幅ｗに対して２ｋ−１＜＝２ｗ−１を満たす最大の整数ｋとして定まる。なお、計算時間を優先する場合はｗを大きな値とし、格納要素数ｋを大きな値とすればよい。メモリ使用量を小さくする場合は、ｗを小さな値とし、格納要素数ｋを小さな値とすればよい。前計算部３０２は、作成した事前計算テーブルをスカラー倍計算部１１５に送る（４０３）。
【００６０】
制御部３０４は、スカラー値ｍおよびウィンドウ幅ｗをエンコード部に送る（４０４）。
【００６１】
エンコード部３０１は、スカラー値ｍおよびウィンドウ幅ｗを用いて、スカラー値ｍを数値列ｍｊにエンコードするエンコード処理を行う。すなわち、
ｍ＝ｍｎ２ｎ＋ｍｎ−１２ｎ−１＋．．．＋ｍｊ２ｊ＋．．．＋ｍ０          （式８）
−２ｗ−１＜＝ｍｊ＜＝２ｗ−１、  ｍｊ＝０  ｏｒ  奇数      （式９）
を満たすｍｊに、スカラー値ｍを変換する。そして、エンコード部３０１は、エンコード列ｍｊを実計算部３０３へ送る（４０５）。
【００６２】
制御部３０４は、前計算部３０２の作成した事前計算テーブルを実計算部に送る（４０６）。
【００６３】
実計算部３０３は、エンコード列ｍｊ、事前計算テーブルを用いてスカラー倍点ｍＰを計算する。実計算部３０３は、スカラー倍計算結果を制御部３０４へ送る（４０７）。制御部３０４は、スカラー倍計算結果をスカラー倍計算部１１５からの出力として出力する（４０８）。
【００６４】
なお、上記のシーケンスでは、格納要素数ｋを、２ｋ−１＜＝２ｗ−１を満たす最大の整数ｋとして定めたが、最大としなくともよい。ただし、その場合は、エンコード処理で出力されるエンコード列の非零の各数値ｍｊに対応する楕円点ｍｊＰが、事前計算テーブルに存在する必要がある。また、エンコード処理で出力されるエンコード列の非零の各数値ｍｊに対応する楕円点ｍｊＰが、事前計算テーブルに存在していれば、式９の条件は他の条件に置き換えてもよい。例えば、ｍｊを偶数としてもよいし、格納要素数ｋに対してｍｊ＜＝２ｋ−１としてもよい。
【００６５】
なお、エンコード部３０１の行うエンコード処理は、例えば、非特許文献１に記載の手法などを用いて実現できる。また、前計算部３０２の行う事前計算テーブルの作成処理は、実計算部３０３の行うスカラー倍計算処理の前であれば、エンコード部３０１の行うエンコード処理の後であってもよい。さらに、各モジュール間のデータの受け渡しは、上述のようにデータを直接転送する以外に、記憶部１０２にデータを書き込み、転送先モジュールが記憶部１２２にアクセスし、データを読み出すよう構成してもよい。  次に、スカラー倍計算部１１５によるスカラー倍計算処理について説明する。図５は、スカラー倍計算部１１５におけるスカラー倍計算処理の処理フローである。
【００６６】
スカラー倍計算部１１５の制御部３０４は、ベース点Ｐ、ｎビットスカラー値ｍ、前計算部３０２の作成した事前計算テーブルを入力として受け取る（ステップ５０１）。
【００６７】
エンコード部３０１は、式８、式９によりエンコード列ｍ０、．．．、ｍｎを計算する（ステップ５０２）。
【００６８】
実計算部３０３は、中間値Ｔに無限遠点Ｏを、変数ｊにｎを代入し、ステップ５１１へ行く（ステップ５０３）。
【００６９】
繰り返し判定部３３４は、変数ｊについて条件：ｊ＞＝０が成立するか否かを判定する。条件が成立する場合、ステップ５１２へ行く。条件が成立しない場合、ステップ５２１へ行く（ステップ５１１）。
【００７０】
ステップ５１１で条件が成立した場合、楕円２倍算部３３３は、中間値Ｔに対して楕円２倍算を行い、その結果を中間値Ｔに格納する（ステップ５１２）。
【００７１】
エンコード値判定部３３１は、エンコード値ｍｊについて条件：ｍｊ＝０が成立するか否かを判定する。条件が成立する場合、ステップ５１５へ行く。条件が成立しない場合、ステップ５１４へ行く（ステップ５１３）。
【００７２】
ステップ５１３で条件が成立しなかった場合、楕円加算部３３２は、中間値Ｔと、事前計算テーブルに格納されている事前計算点ｍｊＰとの楕円加算を行い、その結果を中間値Ｔに格納し（ステップ５１４）、ステップ５１５へ行く。
【００７３】
繰り返し判定部３３４は、変数ｊにｊ−１を代入し、ステップ５１１へと戻る（ステップ５１５）。
【００７４】
ステップ５１１で条件が成立しなかった場合、すなわち、ｊが０より小さい場合は、実計算部３０３は、中間値Ｔをスカラー倍計算結果ｍＰとして出力する（ステップ５２１）。
【００７５】
次に、本実施形態における、上記スカラー倍計算処理内の前計算部３０２による事前計算テーブル作成処理について説明する。前計算部３０２は、制御部３０４から受け取った、ベース点Ｐ、ウィンドウ幅ｗから、事前計算テーブルを作成する。
【００７６】
まず、本実施形態の前計算部３０の機能について説明する。図６は、本実施形態の前計算部３０２を構成する各モジュールを示す機能ブロック図である。
【００７７】
本図に示すように、本実施形態の前計算部３０２は、分母変換部６１０と、同時逆元計算部６２０と、分母復元部６３０と、楕円点計算部６４０と、全体を制御する前計算制御部６６０とを備える。分母変換部６１０は、加算部６１１と、減算部６１２と、乗算部６１３と、繰り返し判定部６１４とを備える。同時逆元計算部６２０は、乗算部６２１と、逆元計算部６２２と、繰り返し判定部６２３とを備える。分母復元部６３０は、乗算部６３１と、繰り返し判定部６３２とを備える。楕円点計算部６４０は、加算部６４１と、減算部６４２と、乗算部６４３と、繰り返し判定部６４４とを備える。
【００７８】
以下、これらの各モジュールにより、本実施形態の前計算部３０２が実現する事前計算テーブル生成処理の詳細を説明する。図７は、前計算部３０２の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。各モジュールが行う処理の詳細については後述する。
【００７９】
前計算制御部６６０は、前計算部３０２へ入力されたベース点Ｐ、ウィンドウ幅ｗを受け取る（７０１）。前計算制御部６５０は、ベース点Ｐおよびウィンドウ幅ｗから算出した格納要素数ｋを、分母変換部６１０へ送る（７０２）。
【００８０】
分母変換部６１０は、分母変換処理を行い、ベース点Ｐおよび格納要素数ｋから変換分母ｄｉを計算する（８０１）。分母変換部６１０は、得られた変換分母ｄｉを同時逆元計算部６２０へ送る（７０３）。
【００８１】
同時逆元計算部６２０は、同時逆元計算処理を行い、変換分母ｄｉから逆元計算結果ｆｉを計算する（８０２）。同時逆元計算部６２０は、得られた逆元計算結果ｆｉを分母復元部６３０へ送る（７０５）。
【００８２】
分母復元部６３０は、分母復元処理を行い、逆元計算結果ｆｉから復元分母Ｌｉを計算する（８０３）。分母復元部６３０は、得られた復元分母Ｌｉを楕円点計算部６４０へ送る（７０７）。
【００８３】
前計算制御部６６０は、ベース点Ｐを楕円点計算部６４０へ送る（７０８）。
【００８４】
楕円点計算部６４０は、楕円点計算処理を行い、楕円点３Ｐ、５Ｐ、．．．、（２ｋ−１）Ｐを計算する（８０４）。なお、ここで計算した楕円点を事前計算楕円点と呼ぶ。そして、楕円点計算部６４０は、得られた事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ−１）Ｐを前計算部３０２へ送る（７０９）。
【００８５】
前計算制御部６６０は、得られた事前計算楕円点を格納した事前計算テーブルを生成し、出力する（７１０）。
【００８６】
なお、各モジュール間のデータの受け渡しは、データを直接転送する以外にも、記憶部１０２にデータを書き込み、転送先モジュールが記憶部１０２にアクセスし、データを読み出すよう構成してもよい。
【００８７】
また、各モジュールは必要に応じて楕円曲線パラメタを用いる。これらのデータは、予め記憶部１０２に書き込んでおき、各モジュールが記憶部１０２にアクセスし、データを読み出すよう構成してもよい。
【００８８】
楕円点計算部６４０の受け取る復元分母Ｌｉ、ベース点Ｐは、楕円点計算部６４０が楕円点計算処理を行う前であれば、受け取る順番は問わない。例えば、前計算制御部６６０がベース点Ｐを楕円点計算部６４０に送った後で、分母変換部６１０、同時逆元計算部６２０、分母復元部６３０が各々の処理を行い、分母復元部６３０が復元分母Ｌｉを楕円点計算部６４０に送るよう構成してもよい。
【００８９】
また、各モジュールは、各々の処理の過程で算出した演算結果を再利用データとして出力してもよい。処理過程で同じ演算を必要とする他のモジュールがその再利用データを入力として受け取り利用することにより、演算を削減ることができ、当該モジュール処理を効率化することができる。
【００９０】
図８は、上記シーケンスにおいて事前計算テーブル生成処理時の各モジュールが行う処理の流れを示す処理フローである。
【００９１】
分母変換部６１０が分母変換処理を行い、前述のλの分母である２ｙｉのねじれを取る（ステップ８０１）。
【００９２】
次に、同時逆元計算部６２０が、モンゴメリトリックの手法を利用して同時逆元計算処理を行い、逆元を計算する（ステップ８０２）。
【００９３】
その後、分母復元部６３０が、分母復元処理を行い、分母を元の表現に復帰させる（ステップ８０３）。
【００９４】
最後に楕円点計算部６４０が、楕円点計算処理を行う（ステップ８０４）。
【００９５】
次に、上記前計算部６２０の各処理の詳細を説明する。
【００９６】
まず、分母変換部６１０が前計算制御部６６０からデータの入力を受け取り処理を開始する分母変換処理について説明する。図９は、本実施形態の分母変換処理の処理フローである。
【００９７】
分母変換部６１０は、ベース点Ｐ＝（ｘ１，ｙ１）、格納要素数ｋ，楕円曲線パラメタａ，ｐを入力として受け取る（ステップ９０１）。
【００９８】
加算部６１１は、ベース点Ｐのｙ座標ｙ１を用いて２ｙ１  ｍｏｄ  ｐを計算し、その結果を変数ｄ１に格納する（ステップ９０２）。
【００９９】
加算部６１１、減算部６１２、乗算部６１３は、変数ｄ１、ベース点Ｐのｘ座標ｘ１、楕円曲線パラメタａを用いて、以下の処理を行う（ステップ９０３）。
・ｄ１２  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・３ｘ１２＋ａ  ｍｏｄ  ｐを計算し、その結果を変数Ａに格納する。
・Ｃ・３ｘ１  ｍｏｄ  ｐを計算し、その結果を変数Ｂに格納する。
・Ａ２−Ｂ  ｍｏｄ  ｐを計算し、その結果を変換分母ｄ２に格納する。
【０１００】
次に、加算部６１１、減算部６１２、乗算部６１３は、変数ｄ２、変数Ａ、変数Ｂ、変数Ｃを用いて、以下の処理を行う（ステップ９０４）。
・ｄ２２  ｍｏｄ  ｐを計算し、その結果を変数Ｅに格納する。
・Ｅ・Ｂ  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・Ｃ２  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・Ｅ・ｄ２  ｍｏｄ  ｐを計算し、その結果を変数Ｄに格納する。
・−ｄ２・Ａ−Ｃ  ｍｏｄ  ｐを計算し、その結果を変数Ａに格納する。
・Ａ２−２Ｄ−Ｂ  ｍｏｄ  ｐを計算し、その結果を変数ｄ３に格納する。
【０１０１】
次に、加算部６１１、減算部６１２、乗算部６１３は、変数ｄ３、変数Ａ、変数Ｂ、変数Ｃ、変数Ｄを用いて、以下の処理を行う（ステップ９０５）。
・ｄ３２  ｍｏｄ  ｐを計算し、その結果を変数Ｅに格納する。
・Ｅ（Ｂ＋３Ｄ）  ｍｏｄ  ｐを計算し、その結果を変数Ｂに格納する。
・Ｄ（２Ａ＋Ｃ）  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・Ｅ・ｄ３  ｍｏｄ  ｐを計算し、その結果を変数Ｄに格納する。
・−ｄ３・Ａ−Ｃ  ｍｏｄ  ｐを計算し、その結果を変数Ａに格納する。
・Ａ２−Ｄ−Ｂ  ｍｏｄ  ｐを計算し、その結果を変数ｄ４に格納する。
【０１０２】
次に、繰り返し判定部６１４は、変数ｉに初期値５を代入し、ステップ９１１へ行く（ステップ９０６）。
【０１０３】
次に、加算部６１１、減算部６１２、乗算部６１３は、変数ｄｉ−１、変数Ａ、変数Ｂ、変数Ｃ、変数Ｄを用いて、以下の処理を行う（ステップ９１１）。
・ｄｉ−１ ２  ｍｏｄ  ｐを計算し、その結果を変数Ｅに格納する。
・Ｅ・Ｂ  ｍｏｄ  ｐを計算し、その結果を変数Ｂに格納する。
・Ｄ・Ｃ  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・Ｅ・ｄｉ−１  ｍｏｄ  ｐを計算し、その結果を変数Ｄに格納する。
・−ｄｉ−１・Ａ−Ｃ  ｍｏｄ  ｐを計算し、その結果を変数Ａに格納する。
・Ａ２−Ｄ−Ｂ  ｍｏｄ  ｐを計算し、その結果を変数ｄｉに格納する。
【０１０４】
次に、繰り返し判定部６１４は、変数ｉにｉ＋１を代入する（ステップ９１２）。
【０１０５】
繰り返し判定部６１４は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ９１１へ戻る。条件が成立しない場合、ステップ９２１へ行く（ステップ９１３）。
【０１０６】
ステップ９１２で条件が成立しなかった場合、分母変換部６１０は、変数ｄ１，．．．，ｄｋを変換分母として出力し（ステップ９２１）、処理を終了する。
【０１０７】
なお、上記分母変換処理において、格納要素数ｋが４以下の値である場合は、格納要素数ｋの値（ｋ＝１、２、３、４）に応じて、それぞれ、ステップ９０２、ステップ９０３、ステップ９０４、ステップ９０５で処理を打ち切り、ステップ９２１へ行き、値を出力するよう構成してもよい。本構成により、それ以降の処理を省くことができ、さらに高速化できる。
【０１０８】
次に、同時逆元計算部６２０が分母変換部６１０からデータの入力を受け取り処理を開始する同時逆元計算処理について説明する。本実施形態では、同時逆元計算部６２０が、同時逆元計算処理の処理過程で算出したデータｅ１，．．．，ｅｋを、再利用データとして出力する場合を例にとり説明する。図１０は、本実施形態の同時逆元処理の処理フローである。
【０１０９】
同時逆元計算部６２０は、変換分母ｄ１，．．．，ｄｋを入力として受け取る（ステップ１００１）。
【０１１０】
同時逆元計算部６２０は、変数ｅ１に変換分母ｄ１を代入する（ステップ１００２）。
【０１１１】
繰り返し判定部６２３は、変数ｉに初期値２を代入し、ステップ１０１１へ行く（ステップ１００３）。
【０１１２】
乗算部６２１は、変換分母ｄｉ、変数ｅｉ−１を用いて、ｅｉ−１・ｄｉ  ｍｏｄ  ｐを計算し、その結果を変数ｅｉに格納する（ステップ１０１１）。
【０１１３】
繰り返し判定部６２３は、変数ｉにｉ＋１を代入する（ステップ１０１２）。
【０１１４】
繰り返し判定部６２３は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１０１１へ行く。条件が成立しない場合、ステップ１０２１へ行く（ステップ１０１３）。
【０１１５】
ステップ１０１３で条件が成立しなかった場合、逆元計算部６２２は、変数ｅｋの逆元ｅｋ−１  ｍｏｄ  ｐを計算し、その結果を変数Ｔ１に格納する（ステップ１０２１）。
【０１１６】
繰り返し判定部６２３は、変数ｉにｋを代入し、ステップ１０３１へ行く（ステップ１０２２）。
【０１１７】
乗算部６２１は、変換分母ｄｉ、変数Ｔ１を用いて、以下の処理を行う（ステップ１０３１）。
・変数Ｔ２にｄｉを代入する。
・ｅｉ−１・Ｔ１  ｍｏｄ  ｐを計算し、その結果を変数ｆｉに格納する。
・Ｔ１・Ｔ２  ｍｏｄ  ｐを計算し、その結果を変数Ｔ１に格納する。
【０１１８】
次に、繰り返し判定部６２３は、変数ｉにｉ−１を代入する（ステップ１０３２）。
【０１１９】
繰り返し判定部６２３は、変数ｉについて条件：ｉ＞＝２が成立するか否かを判定する。条件が成立する場合、ステップ１０３２へ行く。条件が成立しない場合、ステップ１０４１へ行く（ステップ１０３３）。
【０１２０】
ステップ１０３３で条件が成立しなかった場合、同時逆元計算部６２０は、変数ｆ１に変数Ｔ１を代入する（ステップ１０４１）。
【０１２１】
同時逆元計算部６２０は、変数ｆ１，．．．，ｆｋを逆元計算結果として、出力する。また、本実施形態では、同時逆元計算部６２０は、ステップ１００２、１０１１で算出した変数ｅ１，．．．，ｅｋを再利用データとして出力する（ステップ１０４２）。以上で同時逆元処理を終了する。
【０１２２】
次に、分母復元部６３０が同時逆元計算部６２０からデータの入力を受け取り処理を開始する分母復元処理について説明する。図１１は、本実施形態の分母復元処理の処理フローである。ここでは、分母復元部６３０が同時逆元計算部６２０から逆元計算結果ｆ１，．．．，ｆｋとともに変数ｅ１，．．．，ｅｋを再利用データとして受け取る場合を例に挙げて説明する。
【０１２３】
分母復元部６３０は、再利用データｅ１，．．．，ｅｋと逆元計算結果ｆ１，．．．，ｆｋとを入力として受け取る（ステップ１１０１）。
【０１２４】
分母復元部６３０は、変数Ｌ１に逆元計算結果ｆ１を代入する（ステップ１１０２）。
【０１２５】
繰り返し判定部６３２は、変数ｉに初期値２を代入し、ステップ１１１１へ行く。
【０１２６】
乗算部６３１は、再利用データｅｉ−１、逆元計算結果ｆｉを用いて、ｅｉ−１２・ｆｉ  ｍｏｄ  ｐを計算し、その結果を変数Ｌｉに格納する（ステップ１１１１）。
【０１２７】
繰り返し判定部６３２は、変数ｉにｉ＋１を代入する（ステップ１１１２）。
【０１２８】
繰り返し判定部６３２は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１１１１へ行く。条件が成立しない場合、ステップ１１２１へ行く（ステップ１１１３）。
【０１２９】
ステップ１１１２で条件が成立しなかった場合、分母復元部６３０は、変数Ｌ１，．．．，Ｌｋを復元分母として出力し（ステップ１１２１）、処理を終了する。
【０１３０】
次に、楕円点計算部６４０が分母復元部６３０および前計算制御部６６０からデータの入力を受け取り処理を開始する楕円点計算処理について説明する。図１２は、本実施形態の楕円点計算処理の処理フローである。
【０１３１】
楕円点計算部６４０は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ１，．．．，Ｌｋ、楕円曲線パラメタａを入力として受け取る（ステップ１２０１）。
【０１３２】
加算部６４１、減算部６４２、乗算部６４３は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ１、楕円曲線パラメタａを用いて、以下の処理を行う（ステップ１２０２）。
・（３ｘ１２＋ａ）Ｌ１  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・Ｔ２−２ｘ１  ｍｏｄ  ｐを計算し、その結果を変数ｘ２に格納する。
・Ｔ（ｘ１−ｘ２）−ｙ１  ｍｏｄ  ｐを計算し、その結果を変数ｙ２に格納する。
【０１３３】
次に、加算部６４１、減算部６４２、乗算部６４３は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ２、変数ｘ２、変数ｙ２を用いて、以下の処理を行う（ステップ１２０３）。
・（ｙ２−ｙ１）Ｌ２  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・Ｔ２−ｘ２−ｘ１  ｍｏｄ  ｐを計算し、その結果を変数ｘ３に格納する。
・Ｔ（ｘ２−ｘ３）−ｙ２  ｍｏｄ  ｐを計算し、その結果を変数ｙ３に格納する。
【０１３４】
次に、繰り返し判定部６４４は、変数ｉに初期値３を代入し、ステップ１２１１へ行く（１２０４）。
【０１３５】
次に、加算部６４１、減算部６４２、乗算部６４３は、変数ｘ２、変数ｙ２、変数ｘｉ、変数ｙｉ、復元分母Ｌｉを用いて、以下の処理を行う（ステップ１２１１）。
・（ｙｉ−ｙ２）Ｌｉ  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・Ｔ２−ｘ２−ｘｉ  ｍｏｄ  ｐを計算し、その結果を変数ｘｉ＋１に格納する。
・Ｔ（ｘ２−ｘｉ＋１）−ｙ２  ｍｏｄ  ｐを計算し、その結果をｙｉ＋１に格納する。
【０１３６】
次に、繰り返し判定部６４４は、変数ｉにｉ＋１を代入する（ステップ１２１２）。
【０１３７】
繰り返し判定部６４４は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１２１１へ行く。条件が成立しない場合、ステップ１２２１へ行く（ステップ１２１３）。
【０１３８】
ステップ１２１３で条件が成立しなかった場合、楕円点計算部６４０は、変数ｘ３，．．．，ｘｋ＋１、変数ｙ３，．．．，ｙｋ＋１を事前計算楕円点３Ｐ＝（ｘ３，ｙ３）、５Ｐ＝（ｘ４，ｙ４）、．．．、（２ｋ−１）Ｐ＝（ｘｋ＋１，ｙｋ＋１）として出力し（ステップ１２２１）、処理を終了する。
【０１３９】
以上、本実施形態の事前計算テーブル作成処理を説明した。本実施形態の事前計算テーブル作成処理によれば、ベース点Ｐから楕円点２Ｐを計算し、その後３Ｐ（＝Ｐ＋２Ｐ）、５Ｐ（＝３Ｐ＋２Ｐ）、７Ｐ（＝５Ｐ＋２Ｐ）、．．．、（２ｋ−１）Ｐ（＝（２ｋ−３）Ｐ＋２Ｐ）を計算する。楕円点２Ｐ、３Ｐ、５Ｐ、７Ｐ、．．．、（２ｋ−１）Ｐに対するλの分母を、それぞれ、δ１、δ２、．．．、δｋとすると、以下の数式が成立する。
ｄ１＝２ｙ１＝δ１  ｍｏｄ  ｐ                    （式１０）
ｄｉ＝（ｄ１ｄ２．．．ｄｉ−１）２δｉ  ｍｏｄ  ｐ        （式１１）
ｅｉ＝ｄ１ｄ２．．．ｄｉ  ｍｏｄ  ｐ                    （式１２）
ｆｉ＝１／ｄｉ  ｍｏｄ  ｐ                        （式１３）
Ｌｉ＝（ｄ１ｄ２．．．ｄｉ−１）２ｆｉ＝ｅｉ−１２ｆｉ  ｍｏｄ  ｐ    （式１４）
Ｌｉ＝１／δｉ  ｍｏｄ  ｐ                        （式１５）
また、上記楕円点計算処理（図１２）のステップ１２０２、ステップ１２０３、ステップ１２１１は、それぞれ、楕円２倍算、楕円加算、楕円加算をＬｉを用いて計算したものである。従って、本実施形態の事前計算テーブル作成処理により算出され出力される値は、事前計算楕円点といえる。
【０１４０】
また、本実施形態の事前計算テーブル作成処理では、逆元計算は同時逆元処理（図１０）のステップ１０２１でのみ行われる。しかも、上述のように、ステップ１０２１を実行する回数は１回である。従って、本実施形態の事前計算テーブル作成処理全体における逆元計算回数は１回である。
【０１４１】
以上説明した通り、本実施形態によれば、楕円曲線が素体上の楕円曲線である楕円曲線暗号を用いた暗号通信システムにおいて、楕円曲線演算のスカラー倍計算を高速に行うための事前計算テーブルを作成する際に、逆元計算回数を一回に削減することができる。従って、処理速度を犠牲にせず、処理負担、メモリ使用量の少ない楕円曲線演算を実現することができ、これらの特徴を備えた暗号通信システムを実現することができる。
＜＜第二の実施形態＞＞
次に、本発明を適用した第二の実施形態を図面を用いて説明する。本実施形態は、楕円曲線としてバイナリ曲線を用いる。
【０１４２】
本実施形態の暗号通信システムのシステム構成、各処理部間の情報の受け渡し等は、基本的に第一の実施形態と同様である。以下、本実施形態について、第一の実施形態同様、コンピュータＡ１０１が暗号化処理を行う場合の、スカラー倍計算部１１５の処理を例にあげ、第一の実施形態と異なる構成についてのみ説明する。
【０１４３】
本実施形態の第一の実施形態と異なる構成は、事前計算テーブルを作成する前計算部３０２の各モジュールによる分母変換処理、同時逆元処理、分母復元処理、楕円点計算処理である。
【０１４４】
なお、本実施形態では、上述のように楕円曲線としてバイナリ曲線を用いる。事前計算テーブルを作成するにあたり、基本的には、第一の実施形態の前計算部３０２の機能ブロックをそのまま適用可能である。ただし、バイナリ曲線に対応するバイナリ体では、加算は排他的論理和であり、そのため減算も排他的論理和となり、加算とその処理は一致する。したがって加算部（６１１、６４１）と減算部（６１２、６４２）とを共通化、ないしは加算部（６１１、６４１）または減算部（６１２、６４２）のいずれか一方のみを実装してもよい。
【０１４５】
バイナリ曲線の場合、点（ｘ１，ｙ１）と点（ｘ２，ｙ２）の加算（ｘ３，ｙ３）＝（ｘ１，ｙ１）＋（ｘ２，ｙ２）は、
λ＝（ｙ２＋ｙ１）／（ｘ２＋ｘ１）            （式１６）
ｘ３＝λ２＋λ＋ａ２＋ｘ１＋ｘ２                （式１７）
ｙ３＝λ（ｘ１＋ｘ３）＋ｘ３＋ｙ１              （式１８）
を計算することにより得られる。
【０１４６】
ここで、バイナリ曲線の定義式は
ｙ２＋ｘｙ＝ｘ３＋ａ２ｘ２＋ａ６                          （式１９）
で与えられる。ここでａ２，ａ６は定数である。すなわち、式１９のｘ、ｙに各々ｘｉ、ｙｉ（ｉ＝１、２、３）を代入した場合に、式１９の等式が成り立つ。本実施形態では、上記２，ａ６が楕円曲線パラメタとして定数１０４、１２４に格納される。
【０１４７】
バイナリ曲線の場合、点（ｘ１，ｙ１）の２倍算を行った結果（ｘ３，ｙ３）＝２（ｘ１，ｙ１）＝（ｘ１，ｙ１）＋（ｘ１，ｙ１）は、
λ＝（ｘ１２＋ｙ１）／（ｘ１）                  （式２０）
を計算し、このλを用いて式１７、式１８で与えられるｘ３、ｙ３を計算することにより得られる。バイナリ曲線においても、λを計算する際に逆元計算が必要となる。
【０１４８】
次に、本実施形態における前計算部３０２による事前計算テーブル作成処理について説明する。前計算部３０２を構成する各モジュールの処理および各モジュール間のデータの流れは第一の実施形態と同じである。すなわち、本実施形態においても、前計算部３０２は、制御部３０４から受け取った、ベース点Ｐ、ウィンドウ幅ｗから、事前計算テーブルを作成する。ただし、各モジュールの処理が異なる。以下、それぞれ説明する。
【０１４９】
まず、分母変換部６１０が前計算制御部６６０からのデータを受け取り処理を開始する、本実施形態の分母変換処理について説明する。図１３は、本実施形態の分母変換処理の処理フローである。なお、本実施形態では、分母変換部６１０が処理過程で算出したデータｅ１，．．．，ｅｋを、再利用データとして出力する場合を例にとり説明する。
【０１５０】
分母変換部６１０は、ベース点Ｐ＝（ｘ１，ｙ１）、格納要素数ｋ、楕円曲線パラメタａ２を入力として受け取る（ステップ１３０１）。
【０１５１】
加算部６１１は、ベース点Ｐのｘ座標ｘ１を用いて以下の処理を行う（ステップ１３０２）。
・ベース点のｘ座標ｘ１を変数ｄ１に格納する。
・変数ｄ１を変数ｅ１に格納する。
【０１５２】
次に、加算部６１１、乗算部６１３は、変数ｄ１、ベース点Ｐのｙ座標ｙ１、楕円曲線パラメタａ２、変数ｅ１を用いて、以下の処理を行う（ステップ１３０３）。
・ｄ１２を計算し、その結果を変数Ｅに格納する。
・ｅ・ｄ１を計算し、その結果を変数Ｄに格納する。
・Ｅ＋ｙ１を計算し、その結果を変数Ａに格納する。
・Ａ（Ａ＋ｄ１）を計算し、その結果をＢに格納する。
・Ｂ＋ａ２Ｅ＋Ｄを計算し、その結果を変数ｄ２に格納する。
・ｅ１・ｄ２を計算し、その結果を変数ｅ２に格納する。
【０１５３】
次に、加算部６１１、乗算部６１３は、変数ｄ２、変数ｅ２、変数Ａ、変数Ｂ、変数Ｅを用いて、以下の処理を行う（ステップ１３０４）。
・ｄ２２を計算し、その結果を変数Ｆに格納する。
・Ｆ・ｄ２を計算し、その結果を変数Ｄに格納する。
・Ａ・ｄ２を計算し、その結果を変数Ｃに格納する。
・Ｂ・Ｆを計算し、その結果を変数Ｂに格納する。
・Ｃ＋ｅ２＋Ｅ２を計算し、その結果を変数Ａに格納する。
・Ａ（Ａ＋ｅ２）＋Ｂ＋Ｄを計算し、その結果を変数ｄ３に格納する。
・ｅ２・ｄ３を計算し、その結果を変数ｅ３に格納する。
【０１５４】
次に、加算部６１１、乗算部６１３は、変数ｄ３、変数ｅ３、変数Ａ、変数Ｂ、変数Ｃ、変数Ｄを用いて、以下の処理を行う（ステップ１３０５）。
・ｄ３２を計算し、その結果を変数Ｆに格納する。
・変数Ｄを変数Ｅに代入する。
・Ｆ・ｄ３を計算し、その結果を変数Ｄに格納する。
・（Ｃ＋Ａ）Ｅを計算し、その結果を変数Ｃに格納する。
・Ｂ・Ｆを計算し、その結果を変数Ｂに格納する。
・Ｃ＋ｅ３＋Ａｄ３を計算し、その結果を変数Ａに格納する。
・Ａ（Ａ＋ｅ３）＋Ｂ＋Ｄを計算し、その結果を変数ｄ４に格納する。
・ｅ３・ｄ４を計算し、その結果を変数ｅ４に格納する。
【０１５５】
次に、繰り返し判定部６１４は、変数ｉに初期値５を代入し、ステップ１３１１へ行く（ステップ１３０６）。
【０１５６】
加算部６１１、乗算部６１３は、変数ｄｉ−１、変数ｅｉ−１、変数Ａ、変数Ｂ、変数Ｃ、変数Ｄを用いて、以下の処理を行う（ステップ１３１１）。
・ｄｉ−１２を計算し、その結果を変数Ｆに代入する。
・変数Ｄを変数Ｅに代入する。
・Ｆ・ｄｉ−１を計算し、その結果を変数Ｄに格納する。
・Ｃ・Ｅを計算し、その結果を変数Ｃに格納する。
・Ｂ・Ｆを計算し、その結果を変数Ｂに格納する。
・Ｃ＋ｅｉ−１＋Ａ・ｄｉ−１を計算し、その結果を変数Ａに格納する。
・Ａ（Ａ＋ｅｉ−１）＋Ｂ＋Ｄを計算し、その結果を変数ｄｉに格納する。
・ｅｉ−１・Ｄを計算し、その結果を変数ｅｉに格納する。
【０１５７】
次に、繰り返し判定部６１４は、変数ｉにｉ＋１を代入する（ステップ１３１２）。
【０１５８】
繰り返し判定部６１４は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１３１１へ行く。条件が成立しない場合、ステップ１３２１へ行く（ステップ１３１３）。
【０１５９】
ステップ１３１３で条件が成立しなった場合、分母変換部６１０は、変数ｄ１，．．．，ｄｋを変換分母として出力する。また、ステップ１３０２、１３０３、１３０４、１３０５、１３１１で算出した変数ｅ１，．．．，ｅｋを再利用データとして出力する（ステップ１３２１）。以上で分母変換処理を終了する。
【０１６０】
なお、上記分母変換処理において、格納要素数ｋが４以下の値である場合は、格納要素数ｋの値（ｋ＝１，２，３，４）に応じて、それぞれ、ステップ１３０２、ステップ１３０３、ステップ１３０４、ステップ１３０５で処理を打ち切り、ステップ１３２１へ行き、値を出力するよう構成してもよい。本構成により、それ以降の処理を省くことができ、さらに高速化できる。
【０１６１】
次に、本実施形態の同時逆元計算部６２０が分母変換部６１０からデータの入力を受け取り処理を開始する同時逆元計算処理について説明する。本実施形態においても、同時逆元計算部６２０が、同時逆元計算処理の処理過程で算出したデータｅ１，．．．，ｅｋを、再利用データとして出力する場合を例にとり説明する。図１４は、本実施形態の同時逆元処理の処理フローである。
【０１６２】
同時逆元計算部６２０は、変換分母ｄ１，．．．．．．，ｄｋおよび再利用データｅ１，．．．，ｅｋを入力として受け取る（ステップ１４０１）。
【０１６３】
逆元計算部６２２は、再利用データｅｋの逆元ｅｋ−１を計算し、その結果を変数Ｔ１に格納する（ステップ１４０２）。
【０１６４】
繰り返し判定部６２３は、変数ｉに初期値ｋを代入し、ステップ１４１１へ行く（ステップ１４０３）。
【０１６５】
乗算部６２１は、変換分母ｄｉ、変数Ｔ１、再利用データｅｉ−１を用いて、以下の処理を行う（ステップ１４１１）。
・変数ｄｉを変数Ｔ２に代入する。
・ｅｉ−１・Ｔ１を計算し、その結果を変数ｆｉに格納する。
・Ｔ１・Ｔ２を計算し、その結果を変数Ｔ１に格納する。
【０１６６】
次に、繰り返し判定部６２３は、変数ｉにｉ−１を代入する（ステップ１４１２）。
【０１６７】
繰り返し判定部６２３は、変数ｉについて条件：ｉ＞＝２が成立するか否かを判定する。条件が成立する場合、ステップ１４１１へ行く。条件が成立しない場合、ステップ１４２１へ行く（ステップ１４１３）。
【０１６８】
ステップ１４１３で条件が成立しなかった場合、同時逆元計算部６２０は、変数Ｔ１を変数ｆ１に代入する（ステップ１４２１）。
【０１６９】
同時逆元計算部６２０は、変数ｆ１，．．．，ｆｋを逆元計算結果として、出力し（ステップ１４２２）、処理を終了する。
【０１７０】
次に、本実施形態の分母復元部６３０が同時逆元計算部６２０からデータの入力を受け取り処理を開始する分母復元処理について説明する。本実施形態では、分母復元部６３０は、さらに、分母変換部６１０が再利用データとして出力した変数ｅ１，．．．，ｅｋを利用する。図１５は、本実施形態の分母復元処理の処理フローである。
【０１７１】
分母復元部６３０は、再利用データｅ１，．．．，ｅｋ、逆元計算結果ｆ１，．．．，ｆｋを入力として受け取る（ステップ１５０１）。
【０１７２】
分母復元部６３０は、逆元計算結果ｆ１を変数Ｌ１に代入する（ステップ１５０２）。
【０１７３】
分母復元部６３０は、変数ｉに初期値２を代入し、ステップ１５１１へ行く（ステップ１５０３）。
【０１７４】
乗算部６３１は、再利用データｅｉ−１、逆元計算結果ｆｉを用いて、ｅｉ−１２・ｆｉを計算し、その結果を変数Ｌｉに格納する（ステップ１５１１）。
【０１７５】
繰り返し判定部６３２は、変数ｉにｉ＋１を代入する（ステップ１５１２）。
【０１７６】
繰り返し判定部６３２は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１５１１へ行く。条件が成立しない場合、ステップ１５２１へ行く（ステップ１５１３）。
【０１７７】
ステップ１５１３で条件が成立しなかった場合、分母復元部６３２は、変数Ｌ１，．．．，Ｌｋを復元分母として出力し（ステップ１５２１）、処理を終了する。
【０１７８】
次に、本実施形態の楕円点計算部６４０が分母復元部６３０および前計算制御部６６０からデータの入力を受け取り処理を開始する楕円点計算処理について説明する。図１６は、本実施形態の楕円点計算処理の処理フローである。
【０１７９】
楕円点計算部６４０は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ１，．．．，Ｌｋ、楕円曲線パラメタａ２を入力として受け取る（ステップ１６０１）。
【０１８０】
加算部６４１、乗算部６４３は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ１、楕円曲線パラメタａ２を用いて、以下の処理を行う（ステップ１６０２）。
・（ｘ１２＋ｙ１）Ｌ１を計算し、その結果を変数Ｔに格納する。
・Ｔ２＋Ｔ＋ａ２を計算し、その結果を変数ｘ２に格納する。
・Ｔ（ｘ１＋ｘ２）＋ｘ２＋ｙ１を計算し、その結果を変数ｙ２に格納する。
【０１８１】
次に、加算部６４１、乗算部６４３は、ベース点Ｐ＝（ｘ１，ｙ１）、復元分母Ｌ２、楕円パラメタａ２を用いて、以下の処理を行う（ステップ１６０３）。
・（ｙ２＋ｙ１）Ｌ２を計算し、その結果を変数Ｔに格納する。
・Ｔ２＋Ｔ＋ａ２＋ｘ１＋ｘ２を計算し、その結果を変数ｘ３に格納する。
・Ｔ（ｘ２＋ｘ３）＋ｘ３＋ｙ２を計算し、その結果を変数ｙ３に格納する。
【０１８２】
次に、繰り返し判定部６４４は、変数ｉに初期値３を代入し、ステップ１６１１へ行く（ステップ１６０４）。
【０１８３】
加算部６４１、乗算部６４３は、変数ｘ２、変数ｙ２、変数ｘｉ、変数ｙｉ、復元分母Ｌｉ、楕円パラメタａ２を用いて、以下の処理を行う（ステップ１６１１）。
・（ｙ２＋ｙｉ）Ｌｉを計算し、その結果を変数Ｔに格納する。
・Ｔ２＋Ｔ＋ａ２＋ｘｉ＋ｘ２を計算し、その結果を変数ｘｉ＋１に格納する。
・Ｔ（ｘ２＋ｘｉ＋１）＋ｘｉ＋１＋ｙ２を計算し、その結果を変数ｙｉ＋１に格納する。
【０１８４】
次に、繰り返し判定部６４４は、変数ｉにｉ＋１を代入する（ステップ１６１２）。
【０１８５】
繰り返し判定部６４４は、変数ｉについて条件：ｉ＜＝ｋが成立するか否かを判定する。条件が成立する場合、ステップ１６１１へ行く。条件が成立しない場合、ステップ１６２１へ行く（ステップ１６１３）。
【０１８６】
ステップ１６１３で条件が成立しなかった場合、楕円点計算部６４０は、変数ｘ３，．．．，ｘｋ＋１、変数ｙ３，．．．，ｙｋ＋１を事前計算楕円点３Ｐ＝（ｘ３，ｙ３）、５Ｐ＝（ｘ４，ｙ４）、．．．、（２ｋ−１）Ｐ＝（ｘｋ＋１，ｙｋ＋１）として出力し（ステップ１６２１）、処理を終了する。
【０１８７】
以上、本実施形態の事前計算テーブル作成処理を説明した。本実施形態の事前計算テーブル作成処理によれば、第一の実施形態と同様に、ベース点Ｐから楕円点２Ｐを計算し、その後３Ｐ（＝Ｐ＋２Ｐ）、５Ｐ（＝３Ｐ＋２Ｐ）、７Ｐ（＝５Ｐ＋２Ｐ）、．．．、（２ｋ−１）Ｐ（＝（２ｋ−３）Ｐ＋２Ｐ）を計算する。楕円点２Ｐ、３Ｐ、５Ｐ、７Ｐ、．．．、（２ｋ−１）Ｐに対するλの分母を、それぞれ、δ１、δ２、．．．、δｋとすると、以下の数式が成立する。
ｄ１＝ｘ１＝δ１                                （式２１）
ｄｉ＝（ｄ１ｄ２．．．ｄｉ−１）２δｉ                  （式２２）
ｅｉ＝ｄ１ｄ２．．．ｄｉ                            （式２３）
ｆｉ＝１／ｄｉ                                  （式２４）
Ｌｉ＝（ｄ１ｄ２．．．ｄｉ−１）２ｆｉ＝ｅｉ−１２ｆｉ      （式２５）
Ｌｉ＝１／δｉ                                  （式２６）
また、上記楕円点計算処理（図１６）のステップ１６０２、ステップ１６０３、ステップ１６１１は、それぞれ、楕円２倍算、楕円加算、楕円加算をＬｉを用いて計算したものである。従って、本実施形態の事前計算テーブル作成処理により算出され出力される値は、事前計算楕円点といえる。
【０１８８】
また、本実施形態の事前計算テーブル作成処理では、第一の実施形態同様、逆元計算は同時逆元処理（図１４）のステップ１４０２でのみ行われている。しかも、上述のように、ステップ１４０２を実行する回数は１回である。従って、本実施形態の事前計算テーブル作成処理全体における逆元計算回数は１回である。
【０１８９】
以上説明した通り、本実施形態によれば、楕円曲線がバイナリ曲線である楕円曲線暗号を用いた暗号通信システムにおいて、楕円曲線演算のスカラー倍計算を高速に行うための事前計算テーブルを作成する際に、逆元計算回数を一回に削減することができる。従って、処理速度を犠牲にせず、処理負担、メモリ使用量の少ない楕円曲線演算を実現することができ、これらの特徴を備えた暗号通信システムを実現することができる。
＜＜第三の実施形態＞＞
本発明を適用した第三の実施形態を図面を用いて説明する。本実施形態は、楕円曲線暗号における暗号化、復号化処理におけるスカラー倍計算の事前計算テーブル作成を、非特許文献３に示されている手法と上記の第一の実施形態および第二の実施形態で説明した事前計算テーブルの作成方法とを組み合わせて行うものである。以下においては、第一の実施形態、すなわち、楕円曲線が素体上の楕円曲線である場合を例にあげて説明する。
【０１９０】
ここで、以下に非特許文献３の事前計算テーブル生成手法（以下、ＣＭＯ（Ｃｏｈｅｎ、Ｍｉｙａｊｉ、Ｏｎｏ）前計算処理と呼ぶ。）の概要を説明する。ＣＭＯ前計算処理では、ベース点Ｐから楕円点２Ｐを計算し、次のステップで楕円点３Ｐ（Ｐ＋２Ｐ）、４Ｐ（２Ｐ＋２Ｐ）を計算する。次のステップで楕円点５Ｐ（Ｐ＋４Ｐ）、７Ｐ（３Ｐ＋４Ｐ）、８Ｐ（４Ｐ＋４Ｐ）を計算する。そして、同様の処理ステップを繰り返すことにより、楕円点３Ｐ、５Ｐ、．．．、（２ｋ−１）Ｐを計算する。すなわち、ＣＭＯ前計算処理では、先に計算した複数の楕円点のみを用いて、次の楕円点群を計算する処理ステップを繰り返す。１ステップ内の楕円点群の計算は、既に計算されている複数の楕円点を用いて行うため、モンゴメリトリックの手法を利用して並列に処理することが可能である。本方法によれば、上記ステップごとに一回の逆元計算を必要とし、処理全体ではｗ（ウィンドウ幅）回程度の逆元計算を必要とする。
【０１９１】
本実施形態では、所定数の必要な楕円点の中の連続した楕円点をまとめて上記第一の実施形態の方法で算出し、その後の楕円点を上記非特許文献３の手法を用いて算出する。例えば、３Ｐ，５Ｐ，７Ｐ，８Ｐを第一の実施形態の手法により算出し、これらの楕円点を用いて残りの楕円点をＣＭＯ前計算処理を用いて算出する。本実施形態の方法によれば、逆元計算の削減回数を、メモリ使用量、乗算・逆元演算など各種演算の相対速度比、デバイス特性などに応じて調整することができ、所定条件下で更なる高速化が可能である。
【０１９２】
本実施形態の暗号通信システムのシステム構成、各処理部間の情報の受け渡し等は基本的に第一の実施形態と同様である。以下、本実施形態について、コンピュータＡ１０１が暗号化処理を行う場合の、スカラー倍計算部１１５の処理について、第一の実施形態と異なる構成についてのみ説明する。
【０１９３】
第一の実施形態と本実施形態との異なる構成は、事前計算テーブルを作成する前計算部である。図１７は、本実施形態の前計算部１７０２を構成する各モジュールを示す機能ブロック図である。本実施形態の前計算部１７０２は、第一の実施形態の前計算部３０２の構成に加え、ＣＭＯ前計算部１７５０を備える。すなわち、本図に示すように、本実施形態の前計算部１７０２は、分母変換部１７１０と、同時逆元計算部１７２０と、分母復元部１７３０と、楕円点計算部１７４０と、全体を制御する前計算制御部１７６０と、ＣＭＯ前計算部１７５０と、を備える。分母変換部１７１０は、加算部１７１１と、減算部１７１２と、乗算部１７１３と、繰り返し判定部１７１４とを備える。同時逆元計算部１７２０は、乗算部１７２１と、逆元計算部１７２２と、繰り返し判定部１７２３とを備える。分母復元部１７３０は、乗算部１７３１と、繰り返し判定部１７３２とを備える。楕円点計算部１７４０は、加算部１７４１と、減算部１７４２と、乗算部１７４３と、繰り返し判定部１７４４とを備える。第一の実施形態と同名の構成は、基本的に同様の機能を有する。また、ＣＭＯ前計算部１７５０は、ＣＭＯ前計算処理を実行する。
【０１９４】
次に、本実施形態における前計算部１７０２が実現する事前計算テーブル生成処理の詳細を説明する。図１８は、本実施形態の前計算部１７０２の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。
【０１９５】
前計算制御部１７６０が、前計算部１７０２に入力されたベース点Ｐ、ウィンドウ幅ｗを受け取る（１８０１）。前計算制御部１７６０は、ベース点Ｐ、ウィンドウ幅ｗから算出した格納要素数ｋ以下の値である、予め定めた第一の実施形態の方法を応用して計算する楕円点の個数を示す適用要素数ｋ´を、分母変換部１７１０へ送る（１８０２）。
【０１９６】
分母変換部１７１０は、ベース点Ｐおよび適用要素数ｋ´から、ｉ＝１，．．．，ｋ´に対する変換分母ｄｉを計算する。分母変換部１７１０は、得られた変換分母ｄｉを同時逆元計算部１７２０へ送る（１８０３）。ここで行われる分母変換処理は、第一の実施形態と同様である。
【０１９７】
同時逆元計算部１７２０は、ｉ＝１，．．．，ｋ´に対して変換分母ｄｉから、再利用データとして変数ｅｉを計算する。そして、同時逆元計算部１７２０は、ｉ＝１，．．．，ｋ´に対する再利用データｅｉを分母変換部１７１０へ送る（１８０４）。
【０１９８】
分母変換部１７１０は、再利用データｅｉ、分母変換処理で計算した変換分母ｄｋ´から変換分母ｄ〜ｋ´＋１を計算し、同時逆元計算部１７２０に送る（１８０５）。
【０１９９】
同時逆元計算部１７２０は、変換分母ｄ〜ｋ´＋１からｉ＝１，．．．，ｋ´＋１に対する逆元計算ｆｉを得る。そして、結果ｆｉを分母復元部１７３０へ送る（１８０６）。
【０２００】
分母復元部１７３０は、逆元計算結果ｆｉからｉ＝１，．．．，ｋ´＋１に対する復元分母Ｌｉを得、結果Ｌｉを楕円点計算部１７４０へ送る（１８０７）。
【０２０１】
前計算制御部１７６０は、ベース点Ｐを楕円点計算部１７４０へ送る（１８０８）。
【０２０２】
楕円点計算部１７４０は、復元分母Ｌｉおよびベース点Ｐから事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐを計算し、ＣＭＯ前計算部１７５０へ送る（１８０９）。
【０２０３】
また、前計算制御部１７６０は、格納要素数ｋをＣＭＯ前計算部１７５０へ送る（１８１０）。
【０２０４】
ＣＭＯ前計算部１７５０は、事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐと格納要素数ｋとから、ＣＭＯ前計算処理を行い、さらなる事前計算楕円点（２ｋ´＋１）Ｐ、（２ｋ´＋２）Ｐ、．．．、（２ｋ−１）Ｐを計算する。そして、ＣＭＯ前計算部１７５０は、得られた事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ−１）Ｐを前計算制御部１７６０へ送る（１８１１）。
【０２０５】
前計算制御部１７６０は、得られた事前計算楕円点を格納した事前計算テーブルを生成し、出力する（１８１２）。
【０２０６】
次に、上記シーケンスにおいて事前計算テーブル生成処理時の各モジュールが行う処理の流れを、各処理の詳細とともに説明する。図１９は、本実施形態の事前計算テーブル生成処理の処理フローである。
【０２０７】
まず、分母変換部１７１０が、第一の実施形態で説明した分母変換処理を行い、ベース点Ｐおよび適用要素数ｋ´から、ｉ＝１，．．．，ｋ´に対する変換分母ｄｉを計算する（ステップ１９０１）。
【０２０８】
次に、同時逆元計算部１７２０が、再利用データ計算処理を行い、再利用データとして変数ｅｉを計算する（ステップ１９０２）。この計算は第一の実施形態の同時逆元計算処理（図１０）のステップ１００２からステップ１０１３までの処理を行うことにより達成できる。
【０２０９】
次に、分母変換部１７１０が、ステップ１９０２で計算した再利用データｅｉおよびステップ１９０１で計算した変換分母ｄｋ´から変換分母ｄ〜ｋ´＋１を計算する（ステップ１９０３）。本処理は、加算部１７１１、減算部１７１２、乗算部１７１３が以下の処理を行うことにより達成する。
・ｄｋ２  ｍｏｄ  ｐを計算し、その結果を変数Ｅに格納する。
・Ｂ・Ｅ  ｍｏｄ  ｐを計算し、その結果を変数Ｂに格納する。
・Ｃ・Ｄ  ｍｏｄ  ｐを計算し、その結果を変数Ｃに格納する。
・Ｅ・ｄｋ  ｍｏｄ  ｐを計算し、その結果を変数Ｄに格納する。
・−Ａ・ｄｋ´−Ｃ  ｍｏｄ  ｐを計算し、その結果を変数Ａに格納する。
・ｄ１２（Ａ２−Ｄ−Ｂ）＋ｄ２・ｅｋ´２  ｍｏｄ  ｐを計算し、その結果を変換分母ｄ〜ｋ´＋１に格納する。
【０２１０】
次に、同時逆元計算部１７２０は、再利用データｅｋ´および変換分母ｄ〜ｋ´＋１から再利用データｅｋ´＋１を計算する（ステップ１９０４）。この計算は、乗算部１７２１がｅｋ´・ｄｋ´＋１  ｍｏｄ  ｐを計算し、その結果を再利用データｅｋ´＋１に格納することにより達成できる。
【０２１１】
次に、同時逆元計算部１７２０は、ｉ＝１，．．．，ｋ´に対する変換分母ｄｋ、変換分母ｄ〜ｋ´＋１、ｉ＝１，．．．，ｋ´＋１に対する再利用データから、第一の実施形態で説明した同時逆元計算処理を行い、ｉ＝１，．．．，ｋ´に対する逆元計算結果ｆｉおよび逆元計算結果ｆ〜ｋ´＋１を計算する（ステップ１９０５）。
【０２１２】
さらに、同時逆元計算部１７２０は、変換分母ｄ１および逆元計算結果ｆ〜ｋ´＋１から逆元計算結果ｆｋ´＋１を計算する（ステップ１９０６）。この計算は、乗算部１７２１が、ｄ１２ｆ〜ｋ´＋１  ｍｏｄ  ｐを計算し、その結果を逆元計算結果ｆｋ´＋１に格納することにより達成できる。
【０２１３】
分母復元部１７３０は、ｉ＝１，．．．，ｋ´＋１に対して逆元計算結果ｆｉから、第一の実施形態で説明した分母復元処理を行い、復元分母Ｌｉを計算する（ステップ１９０７）。
【０２１４】
楕円点計算部１７４０は、ｉ＝１，．．．，ｋ´に対して第一の実施形態で説明した楕円点計算処理を行い、事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐを計算する（ステップ１９０８）。
【０２１５】
次に、楕円点計算部１７４０は、楕円点２ｋ´Ｐを計算する（ステップ１９０９）。この計算は、加算部１７４１、減算部１７４２、乗算部１７４３が以下の処理を行うことにより達成できる。
・（ｙｋ´＋１−ｙ１）・Ｌｋ´＋１  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・Ｔ２−ｘ１−ｘｋ´＋１  ｍｏｄ  ｐを計算し、その結果を楕円点２ｋ´Ｐのｘ座標ｘｋ´＋２に格納する。
・Ｔ（ｘ１−ｘｋ´＋１）−ｙ１  ｍｏｄ  ｐを計算し、その結果を楕円点２ｋ´Ｐのｙ座標ｙｋ´＋２に格納する。
【０２１６】
次に、ＣＭＯ前計算部１７５０は、事前計算楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐ、格納要素数ｋから、ＣＭＯ前計算処理を行い、（２ｋ´＋１）Ｐ，（２ｋ´＋２）Ｐ，．．．，（２ｋ−１）Ｐを計算する（ステップ１９１０）。
【０２１７】
なお、本実施形態においても、各モジュール間のデータの受け渡しは、データを直接転送する以外にも、記憶部１０２にデータを書き込み、転送先モジュールが記憶部１０２にアクセスし、データを読み出すよう構成してもよい。
【０２１８】
また、各モジュールは必要に応じて楕円曲線パラメタ（例えば、楕円曲線を定める定数ａや対応する有限体の素数ｐなど）を用いる。これらのデータは、予め記憶部１０２に書き込んでおき、各モジュールが記憶部１０２にアクセスし、データを読み出すよう構成してもよい。
【０２１９】
楕円点計算部１７４０の受け取る復元分母Ｌｉ、ベース点Ｐは、楕円点計算部１７４０が楕円点計算処理を行う前であれば、受け取る順番は問わない。例えば、前計算制御部１７６０がベース点Ｐを楕円点計算部１７４０に送った後で、分母変換部１７１０、同時逆元計算部１７２０、分母復元部１７３０が各々の処理を行い、分母復元部１７３０が復元分母Ｌｉを楕円点計算部１７４０に送るよう構成してもよい。
【０２２０】
また、各モジュールは、各々の処理の過程で算出した演算結果を再利用データとして出力してもよい。処理過程で同じ演算を必要とする他のモジュールがその再利用データを入力として受け取り利用することにより、演算を削減することができ、当該モジュール処理を効率化することができる。
【０２２１】
なお、本実施形態では、同時逆元計算部１７２０が再利用データを計算する場合を例に取り説明したが、分母変換部１７１０、分母復元部１７３０などが再利用データを計算してもよい。
【０２２２】
また、上記の説明においては、楕円曲線暗号に用いる楕円曲線が第一の実施形態の素体上の楕円曲線の場合との組み合せを例に取り説明したが、上述したように第二の実施形態のバイナリ曲線の場合と組み合わせてもよい。その場合、ステップ１９０３、ステップ１９０９などの楕円曲線の形状により異なる処理は、バイナリ曲線の加算式（式１６、式１７、式１８）に基づいたものに修正すればよい。
【０２２３】
なお、本実施形態では、楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐを一回の逆元計算で求めている。しかし、楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐを一回の逆元計算で求め、その後、楕円点計算部１７４０が、楕円点（２ｋ´）Ｐを計算することにより、楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐを求めるよう構成してもよい。
【０２２４】
この場合、楕円点３Ｐ、５Ｐ、．．．、（２ｋ´−１）Ｐの計算に第一の実施形態および第二の実施形態の計算方法をそのまま適用することができるため、前計算部１７０２の構成を簡略化でき、回路規模を小さくすることができる。なお、この場合の楕円点（２ｋ´）Ｐの計算は、例えば素体上の楕円曲線の場合には楕円点計算部１７４０が以下の処理を行うことにより達成できる。
・（ｘｋ´＋１−ｘ１）  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・１／Ｔ  ｍｏｄ  ｐを計算し、その結果を変数Ｔに格納する。
・Ｔ・（ｙｋ´＋１−ｙ１）  ｍｏｄ  ｐを計算し、その結果をＴに格納する。
・Ｔ２−ｘ１−ｘｋ´＋１  ｍｏｄ  ｐを計算し、その結果を楕円点（２ｋ´）Ｐのｘ座標ｘｋ＋２に格納する。
・Ｔ・（ｘ１−ｘｋ´＋１）−ｙ１  ｍｏｄ  ｐを計算し、その結果を楕円点（２ｋ´）Ｐのｙ座標ｙｋ＋２に格納する。
【０２２５】
ただし、本構成の場合、１／Ｔ  ｍｏｄ  ｐの計算に逆元計算部が必要となる。このため、楕円点計算部１７４０が逆元計算部を備えるか、または同時逆元計算部１７２０の逆元計算部１７２２を利用して行うよう構成する必要がある。なお、楕円曲線としてバイナリ曲線を用いる場合は、式１６、式１７、式１８を利用して（２ｋ´）Ｐを計算する。
【０２２６】
以上、本実施形態の事前計算テーブル作成処理を説明した。本実施形態の事前計算テーブル作成処理によれば、ベース点Ｐから楕円点２Ｐを計算し、その後３Ｐ（＝Ｐ＋２Ｐ）、５Ｐ（＝３Ｐ＋２Ｐ）、７Ｐ（＝５Ｐ＋２Ｐ）、．．．、（２ｋ´−１）Ｐ（＝（２ｋ´−３）Ｐ＋２Ｐ）および（２ｋ´）Ｐ（＝（２ｋ´−１）Ｐ＋Ｐ）を計算する。楕円点２Ｐ、３Ｐ、５Ｐ、７Ｐ、．．．、（２ｋ´−１）Ｐおよび（２ｋ´）Ｐに対するλの分母を、それぞれ、δ１、δ２、．．．、δｋとすると、以下の数式が成立する。
ｄ１＝２ｙ１＝δ１  ｍｏｄ  ｐ                                  （式２７）
ｄｉ＝（ｄ１ｄ２．．．ｄｉ−１）２δｉ  ｍｏｄ  ｐ
（ｉ＝１，．．．，ｋ´＋１）        （式２８）
ｄ〜ｋ´＋１＝ｄ１２ｄｋ´＋１  ｍｏｄ  ｐ                      （式２９）
ｅｉ＝ｄ１ｄ２．．．ｄｉ  ｍｏｄ  ｐ
（ｉ＝１，．．．，ｋ´）          （式３０）
ｅｋ´＋１＝ｅｋｄｋ´＋１  ｍｏｄ  ｐ                          （式３１）
ｆｉ＝１／ｄｉ  ｍｏｄ  ｐ
（ｉ＝１，．．．，ｋ´＋１）          （式３２）
ｆ〜ｋ´＋１＝１／ｄ〜ｋ´＋１  ｍｏｄ  ｐ                        （式３３）
Ｌｉ＝（ｄ１ｄ２．．．ｄｉ−１）２ｆｉ＝ｅｉ−１２ｆｉ  ｍｏｄ  ｐ
（ｉ＝１，．．．，ｋ´＋１）          （式３４）
Ｌｉ＝１／δｉ  ｍｏｄ  ｐ
（ｉ＝１，．．．，ｋ´＋１）          （式３５）
また、上記ステップ１９０９の楕円点計算処理（図１９）は、楕円加算をＬｉを用いて計算したものである。従って、本実施形態の事前計算テーブル作成処理により算出され出力される値は、事前計算点といえる。
【０２２７】
また、本実施形態の事前計算テーブル処理では、逆元計算は図１９のステップ１９０５およびステップ１９１０でのみ行われる。ステップ１９０５では、逆元計算は１回である。従って、本実施形態の事前計算テーブル作成処理全体においては、従来の方法に比べて逆元計算回数を抑えることができる。
【０２２８】
以上説明した通り、本実施形態によれば、楕円曲線暗号を用いた暗号通信システムにおいて、楕円曲線演算のスカラー倍計算を高速に行うための事前計算テーブルを作成する際に、逆元計算回数を低減することができる。従って、処理速度を犠牲にせず、処理負担、メモリ使用量の少ない楕円曲線演算を実現することができ、これらの特徴を備えた暗号通信システムを実現することができる。
＜＜第四の実施形態＞＞
次に、本発明を署名検証システムに適用する実施形態を図面を用いて説明する。本実施形態の署名検証システムでは、署名の生成および検証に楕円曲線演算（楕円曲線暗号）を用いる。本実施形態はこの楕円曲線演算に本発明を適用し、その処理の高速化、効率化を実現する。
【０２２９】
図２０は、本発明を適用した署名検証システムのシステム構成図である。本図に示すように、本実施形態の署名検証システムは、第一の実施形態の暗号通信システムで用いられた楕円曲線暗号技術をそれぞれ適用したスマートカード２００１と署名検証処理を行うコンピュータ２０２１とを備える。スマートカード２００１は署名を生成し、コンピュータ２０２１は、生成された署名を検証する。
【０２３０】
スマートカード２００１は、第一の実施形態のコンピュータＡ１０１と類似の構成を備え、ＣＰＵ２０１３、コプロセッサ２０１４などの演算装置、ＲＡＭ２００３、ＲＯＭ２００６などの記憶装置、外部とのデータ入出力を行なう入出力インタフェース２０１０を備える。記憶装置に格納されたプログラムを演算装置が実行することにより、署名生成処理部２０１２およびスカラー倍計算部２０１５からなる処理部２０１１を実現する。ＲＡＭ２００３には、処理に必要な定数２００４、秘密情報２００５が保持される。
【０２３１】
コンピュータ２０２１は、第一の実施形態のコンピュータＡ１０１と同様の構成を備え、ＣＰＵ２０１３、コプロセッサ２０１４などの演算装置、ＲＡＭ２０２３、ＲＯＭ２０２６、外部記憶装置２０２７などの記憶装置、コンピュータ２０２１の外部とのデータ入出力を行なう入出力インタフェース２０３０を装備し、外部にはコンピュータ２０２１をユーザが操作するためのディスプレイ２００８、キーボード２００９、着脱可能な可搬型記憶媒体の読み書き装置などが接続される。記憶装置に格納されたプログラムを演算装置が実行することにより、署名検証処理部２０３２およびスカラー倍計算部２０３５からなる処理部２０３１を実現する。ＲＡＭ２０２３には、処理に必要な定数２０２４、秘密情報２０２５が保持される。
【０２３２】
本実施形態のスカラー倍計算部２０１５と２０３５とは第一の実施形態のスカラー倍計算部１１５または１３５と基本的に同様の機能を備える。
【０２３３】
なお、本実施形態において、コンピュータ２０２１内の各プログラムは、予め、上記コンピュータ内の記憶部２０２２に格納されていてもよいし、必要なときに、コンピュータ２０２１が利用可能な媒体を介して他の装置から上記記憶部２０２２に導入されてもよい。媒体とは、例えば、入出力インタフェース２０３０に着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０２３４】
さらに、スマートカード２００１内の各プログラムは、予め、上記スマートカード２００１内の記憶部２００２に格納されてもよいし、必要なときに、入出力インタフェース２０１０を介して接続するコンピュータ、または当該コンピュータが利用可能な媒体を介して上記記憶部に導入されてもよい。媒体とは、例えば、当該コンピュータに着脱可能な記憶媒体、または通信媒体（すなわちネットワークまたはネットワークを伝搬する搬送波）を指す。
【０２３５】
次に、本実施形態の署名検証システムにおける署名生成と署名検証動作を説明する。ここでは、第一の実施形態の図２を参照して説明する。まず、スマートカード２００１における署名生成時の動作について説明する。なお、本実施形態では、図２のデータ処理部１１２は、署名生成処理部２０１２、スカラー倍計算部１１５はスカラー倍計算部２０１５、記憶部１０２は、記憶部２００２である。
【０２３６】
コンピュータ２０２１は、ランダムに選んだ数値をチャレンジコード２０４３として、スマートカード２００１に転送する。
【０２３７】
署名生成処理部２０１２は、入出力インタフェース２０１０を介して、チャレンジコードを受け取ると（２０１）、チャレンジコード２０４３のハッシュ値をとり、所定のビット長の数値ｆに変換する。
【０２３８】
署名生成処理部２０１２は、乱数ｒを生成する。また、署名生成処理部２０１２は、記憶部２００２に格納されている定数２００４から楕円曲線上の定点Ｑを読み出す（２０２）。そして、署名生成処理部２０１２は、乱数ｒをスカラー値とし、読み出した定点Ｑをベース点とし、利用可能なメモリ容量に応じてウィンドウ幅ｗを設定する。そして、スカラー値ｒ、ベース点Ｑ、ウィンドウ幅ｗをスカラー倍計算部２０１５へ送る（２０３）。
【０２３９】
スカラー倍計算部２０１５は、スカラー値ｒ（乱数ｒ）による定点Ｑのスカラー倍点ｒＱ（＝（ｘｒ，ｙｒ））を計算し、計算されたスカラー倍点ｒＱを署名生成処理部２０１２へ送る（２０４）。
【０２４０】
署名生成部２０１２は、送られたスカラー倍点ｒＱを用いて署名の生成を行う。例えば、ＥＣＤＳＡ署名であれば、
ｓ＝ｘｒ  ｍｏｄ  ｑ                      （式３６）
ｔ＝ｒ−１（ｆ＋ｄｓ）  ｍｏｄ  ｑ        （式３７）
を計算することによりチャレンジコード２０４３に対応する署名（ｓ，ｔ）を得る。ここで、ｑは定点Ｑの位数、すなわち定点Ｑのｑ倍点ｑＱが無限遠点になり、ｑより小さな数値ｍに対する定点Ｑのｍ倍点ｍＱは無限遠点にはならない、というような数値のことである。
【０２４１】
署名生成部２０１２は、入出力インタフェース２０１０を介して生成した署名（ｓ，ｔ）を出力データとして出力する（２０５）。
【０２４２】
スマートカード２００１は、署名生成処理部２０１２で作成した署名（ｓ，ｔ）を入出力インタフェース２０１０より署名２０４１として出力し、コンピュータ２０２１へ転送する。
【０２４３】
次に、署名２０４１を受け取ったコンピュータ２０２１側の動作について図２を用いて説明する。ここでは、図２のデータ処理部１１２は、署名検証処理部２０３２、スカラー倍計算部１１５は、スカラー倍計算部２０３５、記憶部１０２は、記憶部２０２２とする。
【０２４４】
コンピュータ２０２１の署名検証処理部２０３２（図２の１１２）は、入出力インタフェース２０３０を介して、署名２０４１を入力メッセージとして受け取る（２０１）と、署名２０４１の数値ｓ，ｔが適切な範囲内、すなわち１≦ｓ，ｔ＜ｑであるかを調べる。
【０２４５】
数値ｓ，ｔが上記範囲内になければチャレンジコード２０４３に対する署名の検証結果として「無効」を出力し、スマートカード２００１を拒絶する。一方、数値ｓ，ｔが上記範囲内にあれば、署名検証処理部２０３２は、
ｈ＝ｔ−１  ｍｏｄ  ｑ              （式３８）
ｈ１＝ｆ・ｈ  ｍｏｄ  ｑ            （式３９）
ｈ２＝ｓ・ｈ  ｍｏｄ  ｑ            （式４０）
を計算する。
【０２４６】
次に、署名検証処理部２０３２は、記憶部２０２２（図２の１０２）に格納されている定数２０２４から公開鍵ｕＱ及び定点Ｑを読み出す（２０２）。そして、計算したｈ１，ｈ２とともに、公開鍵ｕＱ、定点Ｑをスカラー倍計算部２０３５へ送る（２０３）。
【０２４７】
スカラー倍計算部２０３５は、定点Ｑとｈ１とによるスカラー倍点ｈ１Ｑと、公開鍵ｕＱとｈ２とによるスカラー倍点ｈ２ｕＱとを計算し、両スカラー倍点ｈ１Ｑ、ｈ２ｕＱを署名検証処理部２０３２へ送る（２０４）。
【０２４８】
署名検証処理部２０３２は、送られたスカラー倍点を用いて、署名検証処理を行う。例えば、ＥＣＤＳＡの署名検証であれば、点Ｒ
Ｒ＝ｈ１Ｑ＋ｈ２ｕＱ                    （式４１）
を計算し、そのｘ座標をｘＲとしたとき、
ｓ’＝ｘＲ  ｍｏｄ  ｑ                  （式４２）
を計算する。
【０２４９】
ここで、ｓ’＝ｓであれば、署名検証処理部２０３２は、チャレンジコード２０４３に対する署名の検証結果として「有効」を出力する（２０５）。この場合、コンピュータ２０２１は、スマートカード２００１を認証し、受入れる。
【０２５０】
一方、ｓ’＝ｓでなければ、署名検証処理部２０３２は、署名の検証結果として「無効」を出力する（２０５）。この場合、コンピュータ２０２１は、スマートカードを拒絶する。
【０２５１】
本実施形態のスカラー倍計算部２０１５、２０３５は、第一の実施形態のスカラー倍計算部１１５または１３５と同様の機能を備える。このため、高速かつ低負担で事前計算テーブルを作成し、スカラー倍計算を実行することができる。
【０２５２】
従って、本実施形態によれば、処理速度を犠牲にせず、処理負担、メモリ使用量の少ない楕円曲線演算を実現することができ、これらの特徴を備えた署名生成、検証装置を実現することができる。
【０２５３】
なお、上記の実施形態では、第一の実施形態のスカラー倍計算処理を署名生成、署名検証に適用した場合を例にあげて説明したが、もちろん、第二、第三の実施形態のスカラー倍計算処理を適用することも可能である。
＜＜第五の実施形態＞＞
次に、本発明を鍵交換システムに適用する実施形態を図面を用いて説明する。本実施形態の鍵交換システムでは、交換する鍵データの生成および抽出に楕円曲線演算（楕円曲線暗号）を用いる。本実施形態はこの楕円曲線演算に本発明を適用し、その処理の高速化、効率化を実現する。
【０２５４】
本実施形態の鍵交換システムのシステム構成は、第一の実施形態と基本的に同様である。従って、以下においては、図１を用いて説明する。ただし、図１のデータ処理部１１２、１３２は、本実施形態においては、それぞれ鍵交換処理部１１２、１３２として機能する。本実施形態における鍵の交換は、コンピュータＡ１０１およびコンピュータＢ１２１において、それぞれ、ネットワークを介して取得したデータ（公開鍵）と自身が有する秘密鍵とを用いて新たなデータを生成し、それを秘密裏の共有することにより、両者間の暗号通信における新たな鍵とすることにより実現する。
【０２５５】
鍵交換システムのコンピュータＡ１０１が、入力されたデータ１４３から共有情報の導出を行う場合の動作について図１、図２を参照して説明する。
【０２５６】
コンピュータＢ１２１の鍵交換処理部１３２は、記憶部１２２（の定数１２５から秘密鍵ｖを読み出し、コンピュータＢ１２１の公開鍵ｖＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｖＱをデータ１４３としてコンピュータＡ１０１に転送する。
【０２５７】
コンピュータＡ１０１の鍵交換処理部１１２は、入出力インタフェース１１０を介してコンピュータＢ１２１の公開鍵ｖＱを受け取る（２０１）。また、鍵交換処理部１１２は、記憶部１０２から秘密情報１０５であるコンピュータＡ１０１の秘密鍵ｕ読み出す（２０２）。
【０２５８】
鍵交換処理部１１２は、コンピュータＢ１２１の公開鍵ｖＱと自身の秘密鍵ｕと設定したウィンドウ幅ｗとをスカラー倍計算部１１５へ送る（２０３）。
【０２５９】
スカラー倍計算部１１５は、秘密鍵ｕと公開鍵ｖＱとによるスカラー倍点ｕｖＱを計算し、計算されたスカラー倍点ｕｖＱを鍵交換処理部１１２へ送る（２０４）。
【０２６０】
鍵交換処理部１１２は、送られたスカラー倍点ｕｖＱを用いて共有情報の導出を行ない、記憶部１０２に秘密情報１０５として格納する。例えば、スカラー倍点ｕｖＱのｘ座標を、共有情報とする。
【０２６１】
次に、コンピュータＢ１２１が、入力されたデータ１４１から共有情報の導出を行なう場合の動作について説明する。
【０２６２】
コンピュータＡ１０１の鍵交換処理部１１２は、記憶部１０２の定数１０５から秘密鍵ｕを読み出し、コンピュータＡ１０１の公開鍵ｕＱを計算する。そして、ネットワーク１４２を介して、公開鍵ｕＱをデータ１４１としてコンピュータＢ１２１に転送する。
【０２６３】
コンピュータＢ１２１の鍵交換処理部１３２は、入出力インタフェース１３０を介してコンピュータＡ１０１の公開鍵ｕＱを受け取る（２０１）。また、鍵交換処理部１３２は、記憶部１２２から秘密情報１２５であるコンピュータＢ１２１の秘密鍵ｖを読み出す（２０２）。
【０２６４】
鍵交換処理部１３２は、秘密鍵ｖとコンピュータＡ１０１の公開鍵ｕＱと設定したウィンドウ幅ｗとをスカラー倍計算部１３５へ送る（２０３）。
【０２６５】
スカラー倍計算部１３５は、秘密鍵ｖと公開鍵ｕＱとによるスカラー倍点ｖｕＱを計算し、計算されたスカラー倍点ｖｕＱを鍵交換処理部１３２へ送る（２０４）。
【０２６６】
鍵交換処理部１３２は、送られたスカラー倍点ｖｕＱを用いて共有情報の導出を行ない、記憶部１２２に秘密情報１２５として格納する。例えば、スカラー倍点ｂａＱのｘ座標を、共有情報とする。
【０２６７】
ここで、数ｕｖと数ｖｕとは数値として等しいので、点ｕｖＱと点ｖｕＱは同一の点となり、同一の情報が導出されたことになる。
【０２６８】
ネットワーク１４２には、点ｕＱと点ｖＱが送信されるが、点ｕｖＱ（もしくはｖｕＱ）は送信されない。点ｕｖＱ（もしくはｖｕＱ）を計算するためには秘密鍵ｕもしくは秘密鍵ｖを用いなけらばならない。すなわち、秘密鍵ｕもしくは秘密鍵ｖを知らなければ、共有情報を得ることができない。このようにして得られた共有情報は、共通鍵暗号の秘密鍵として利用できる。
【０２６９】
以上の方法により、本実施形態の鍵交換システムは、共通鍵暗号の秘密鍵の交換を実現する。
【０２７０】
本実施形態においても、スカラー倍計算部１１５、１３５は、上記各実施形態のいずれの構成も採用が可能である。従って、本実施形態においても、処理速度を犠牲にせず、処理負担、メモリ使用量の少ないスカラー倍計算による楕円曲線演算を実現でき、これらの特徴を備えた鍵交換システムを実現することができる。なお、本実施形態のシステムで交換する情報は、鍵情報に限られない。従って、本実施形態は、一般のデータを共有するシステムとして利用できる。
【０２７１】
なお、上記の実施形態では、第一の実施形態を適用した場合を例にあげて説明したが、もちろん、第二、第三の実施形態のスカラー倍計算処理を適用することも可能である。
【０２７２】
なお、上記の各実施形態における暗号化処理部、復号化処理部、署名作成部、署名検証部、鍵交換処理部は、専用のハードウェアを用いて行ってもよい。また、スカラー倍計算部、前計算部、加算部、減算部、乗算部、逆元計算部をコプロセッサまたはそれ以外の専用ハードウェアで実現してもよい。
【０２７３】
また、データ処理部は、上記暗号化処理、復号化処理、署名生成処理、署名検証処理、鍵交換処理のうち、任意の一つ以上の処理を行えるように構成してもよい。
【図面の簡単な説明】
【０２７４】
【図１】第一の実施形態の暗号通信システムのシステム構成図である。
【図２】第一の実施形態のコンピュータ内の各処理部間の情報の受け渡しを示すシーケンス図である。
【図３】第一の実施形態のスカラー倍計算部の機能ブロック図である。
【図４】第一の実施形態のスカラー倍計算部内の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。
【図５】第一の実施形態のスカラー倍計算処理の処理フローである。
【図６】第一の実施形態の前計算部の機能ブロック図である。
【図７】第一の実施形態の前計算部内の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。
【図８】第一の実施形態の事前計算テーブル生成処理の処理フローである。
【図９】第一の実施形態の分母変換処理の処理フローである。
【図１０】第一の実施形態の同時逆元処理の処理フローである。
【図１１】第一の実施形態の分母復元処理の処理フローである。
【図１２】第一の実施形態の楕円点計算処理の処理フローである。
【図１３】第二の実施形態の分母変換処理の処理フローである。
【図１４】第二の実施形態の同時逆元処理の処理フローである。
【図１５】第二の実施形態の分母復元処理の処理フローである。
【図１６】第二の実施形態の楕円点計算処理の処理フローである。
【図１７】第三の実施形態の前計算部の機能ブロック図である。
【図１８】第三の実施形態の前計算部内の各モジュールの処理および各モジュール間のデータの流れを示すシーケンス図である。
【図１９】第三の実施形態の事前計算テーブル生成処理の処理フローである。
【図２０】第四の実施形態の署名検証システムのシステム構成図である。
【符号の説明】
【０２７５】
１０１：コンピュータＡ、１０２：記憶部、１０３：ＲＡＭ、１０４：定数、１０５：秘密情報、１０６：ＲＯＭ、１０７：外部記憶装置、１０８：ディスプレイ、１０９：キーボード、１１０：入出力インタフェース、１１１：処理部、１１２：データ処理部、１１３：ＣＰＵ、１１４：コプロセッサ、１１５：スカラー倍計算部、１２１：コンピュータＢ、１２２：記憶部、１２３：ＲＡＭ、１２４：定数、１２５：秘密情報、１２６：ＲＯＭ、１２７：外部記憶装置、１２８：ディスプレイ、１２９：キーボード、１３０：入出力インタフェース、１３１：処理部、１３２：データ処理部、１３３：ＣＰＵ、１３４：コプロセッサ、１３５：スカラー倍計算部、１４１：データ、１４２：ネットワーク、１４３：データ、３０１：エンコード部、３０２：前計算部、３０３：実計算部、３０４：制御部、３３１：エンコード値判定部、３３２：楕円加算部、３３３：楕円２倍算部、３３４：繰り返し判定部、６１０：分母変換部、６２０：同時逆元計算部、６３０：分母復元部、６４０：楕円点計算部、６６０：前計算制御部、６１１：加算部、６１２：減算部、６１３：乗算部、６１４：繰り返し判定部、６２１：乗算部、６２２：逆元計算部、６２３：繰り返し判定部、６３１：乗算部、６３２：繰り返し判定部、６４１：加算部、６４２：減算部、６４３：乗算部、６４４：繰り返し判定部、１７０２：前計算部、１７１０：分母変換部、１７２０：同時逆元計算部、１７３０：分母復元部、１７４０：楕円点計算部、１７５０：ＣＭＯ計算部、１７６０：前計算制御部、１７１１：加算部、１７１２：減算部、１７１３：乗算部、１７１４：繰り返し判定部、１７６２１：乗算部、１７２２：逆元計算部、１７２３：繰り返し判定部、１７３１：乗算部、１７３２：繰り返し判定部、１７４１：加算部、１７４２：減算部、１７４３：乗算部、１７４４：繰り返し判定部、２００１：スマートカード、２００２：記憶部、２００３：ＲＡＭ、２００４：定数、２００５：秘密情報、２００６：ＲＯＭ、２０１０：入出力インタフェース、２０１１：処理部、２０１２：署名生成処理部、２０１３：ＣＰＵ、２０１４：コプロセッサ、２０１５：スカラー倍計算部、２０２１：コンピュータ、２０２２：記憶部、２０２３：ＲＡＭ、２０２４：定数、２０２５：秘密情報、２０２６：ＲＯＭ、２０２７：外部記憶装置、２０２８：ディスプレイ、２０２９：キーボード、２０３０：入出力インタフェース、２０３１：処理部、２０３２：署名検証処理部、２０３３：ＣＰＵ、２０３４：コプロセッサ、２０３５：スカラー倍計算部、２０４１：署名、２０４２：チャレンジコード
【図１】
2007212768.tif 000003
【図２】
2007212768.tif 000004
【図３】
2007212768.tif 000005
【図４】
2007212768.tif 000006
【図５】
2007212768.tif 000007
【図６】
2007212768.tif 000008
【図７】
2007212768.tif 000009
【図８】
2007212768.tif 000010
【図９】
2007212768.tif 000011
【図１０】
2007212768.tif 000012
【図１１】
2007212768.tif 000013
【図１２】
2007212768.tif 000014
【図１３】
2007212768.tif 000015
【図１４】
2007212768.tif 000016
【図１５】
2007212768.tif 000017
【図１６】
2007212768.tif 000018
【図１７】
2007212768.tif 000019
【図１８】
2007212768.tif 000020
【図１９】
2007212768.tif 000021
【図２０】
2007212768.tif 000022