(57)【特許請求の範囲】
【請求項１】
有限体位数をｐ、与えられた楕円曲線上のベースポイントをＰ、その位数をＮ、秘密鍵をｄ、ＲをＲ＞ｐ，Ｒ＞Ｎを満たす正整数とし、
第２演算処理部が、乱数ｋを生成し、
上記第２演算処理部が、ベースポイントＰを楕円曲線上でｋ倍した点ｋＰを求め、
上記第２演算処理部が、ｋＰのｘ座標ＸとしてＸmodｐ＝ｕｘを計算し、
上記第２演算処理部が、データ管理部から第１乗算データであるＲｍｏｄＮ又はＲ２ｍｏｄＮを取出して、これと上記ｕｘを第１演算処理部に入力して、ｕｘＲｍｏｄＮ又はｕｘＲ２ｍｏｄＮＲ−１ｍｏｄＮを計算させて、ｕｘをモンゴメリ空間へ変換したデータＵ′を求め、ただし、Ｎ、Ｒは正の整数であり、
上記第２演算処理部が、データ管理部から第１乗算データであるＲｍｏｄＮ又はＲ２ｍｏｄＮを取出して、これと上記ｋを上記第１演算処理部に入力して、ｋＲｍｏｄＮ又はｋＲ２ｍｏｄＮＲ−１ｍｏｄＮを計算させて、ｋをモンゴメリ空間へ変換したデータＫを求め、
上記第２演算処理部が、そのデータＫを上記第１演算処理部に入力して、モンゴメリ空間での逆元Ｋ−１Ｒ２modＮを計算させてデータＫ′を求め、
上記第２演算処理部が、データ管理部から秘密データＤ＝ｄＲmodＮを取出して、これと上記データＵ′を上記第１演算処理部に入力して、乗算値Ｄ′＝Ｕ′ＤmodＮを計算させて、
上記第２演算処理部が、入力されたメッセージｍに対し一方向性関数を施してｈ（ｍ）を求め、
上記第２演算処理部が、データ管理部から第１乗算データであるＲｍｏｄＮ又はＲ２ｍｏｄＮを取出して、これと上記ｈ（ｍ）を上記第１演算処理部に入力して、ｈ（ｍ）ＲｍｏｄＮ又はｈ（ｍ）Ｒ２ｍｏｄＮＲ−１ｍｏｄＮを計算させて、ｈ（ｍ）をモンゴメリ空間へ変換したデータＨを求め、
上記第２演算処理部が、データＨと乗算値Ｄ′を加算して加算値Ｓ′＝（Ｈ＋Ｄ′）modＮを求め、
上記第２演算処理部が、加算値Ｓ′とデータＫ′を上記１演算処理部に入力して、乗算値Ｓ＝Ｋ′Ｓ′ｍｏｄNを計算させて、
上記第２演算処理部が、データ管理部から第２乗算データであるＲ−１ｍｏｄＮを取出して、これと上記Ｓを上記第１演算処理部に入力して、ＳＲ−１ｍｏｄＮを計算させて、剰余系に変換したデータｓを求め、
出力部が、データｓとデータｕｘをメッセージｍに対する署名として出力することを特徴とする暗号処理方法。
【請求項２】
有限体位数をｐ、与えられた楕円曲線上のベースポイントを
Ｐ、その位数をＮ、秘密鍵をｄ、ＲをＲ＞ｐ，Ｒ＞Ｎを満たす正整数とし、
第２演算処理部が、乱数ｋを生成し、
上記第２演算処理部が、ベースポイントＰを楕円曲線上でｋ倍した点ｋＰを求め、
上記第２演算処理部が、ｋＰのｘ座標ＸとしてＸmodｐ＝ｕｘを計算し、
上記第２演算処理部が、データ管理部から第１乗算データであるＣＲｍｏｄＮ又はＣＲ２ｍｏｄＮを取出して、これと上記ｕｘを第１演算処理部に入力して、ｕｘＣＲｍｏｄＮ又はｕｘＣＲ２ｍｏｄＮＲ−１ｍｏｄＮを計算させて、ｕｘをモンゴメリ空間へ変換したデータＵ′を求め、ただし、Ｃは正整数１であり、Ｎ、Ｒは正の整数であり、
上記第２演算処理部が、データ管理部から第１乗算データであるＲｍｏｄＮ又はＲ２ｍｏｄＮを取出して、これと上記ｕｘを第１演算処理部に入力して、ｋＲｍｏｄＮ又はｋＲ２ｍｏｄＮＲ−１ｍｏｄＮを計算して、ｋをモンゴメリ空間へ変換したデータＫを求め、
上記第２演算処理部が、そのデータＫを上記第１演算処理部に入力して、モンゴメリ空間での逆元Ｋ−１Ｒ２modＮを計算させてデータＫ′を求め、
上記第２演算処理部が、データ管理部から秘密データＤ＝ｄＲmodＮを取出して、これとデータＵ′を上記第１演算処理部に入力して、乗算値Ｄ′＝Ｕ′ＤmodＮを計算させ、
上記第２演算処理部が、入力されたメッセージｍに対し一方向性関数を施してｈ（ｍ）を求め、
上記第２演算処理部が、データ管理部から第２乗算データであるＲ−１ｍｏｄＮを取出し、これと上記Ｄ′を上記第１演算処理部に入力して、Ｄ′Ｒ−１ｍｏｄＮを計算させて、乗算値Ｄ′を剰余系データｄ′に変換し、
上記第２演算処理部が、ｈ（ｍ）とデータｄ′を加算してデータｓ′＝（ｈ（ｍ）＋ｄ′）modＮを求め、
上記第２演算処理部が、データ管理部から第２乗算データであるＲ−１ｍｏｄＮを取出し、これと上記Ｋ′を上記第１演算処理部に入力して、Ｋ′Ｒ−１ｍｏｄＮを計算させて、データＫ′を剰余系データｋ′に変換し、
上記第２演算処理部が、データｋ′とデータｓ′を乗算してデータｓ＝ｋ′ｓ′modＮを求め、
出力部が、データｓ及びデータｕｘをメッセージｍに対する署名として出力することを特徴とする暗号処理方法。
【請求項３】
請求項１又は２記載の暗号処理方法の各過程をコンピュータに実行させるための暗号処理プログラム。
【請求項４】
請求項３記載の暗号処理プログラムを記録したコンピュータ読み出し可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、例えばコンピュータネットワークにおける情報のセキュリティ（安全性）の確保に適用され、特に公開鍵暗号、ディジタル署名の実行に適する暗号処理方法、そのプログラム及びその記録媒体に関する。
【０００２】
【従来の技術】
公開鍵暗号の一つである楕円曲線暗号の概要を説明する。有限体の位数を素数ｐ、楕円曲線を決定するパラメータ（ａ，ｂ）に対して以下の式を満たす点の集合に仮想的な無限遠点Ｏを加えた集合を、楕円曲線Ｅｐと呼ぶ。
Ｅｐ：ｙ2 ≡ｘ3 ＋ａｘ＋ｂ（mod Ｐ）
楕円曲線上の２点の間に楕円曲線上の加法が定義され、Ｐ３＝Ｐ１＋Ｐ２（但し、Ｐｉ＝（ｘｉ，ｙｉ））は以下のように定義される。
［（Ｐ１≠Ｐ２）の場合］以降、この場合を楕円加算演算と呼ぶ。楕円加算演算：加算０回、減算６回、乗算２回、除算１回
λ＝（ｙ２−ｙ１）／（ｘ２−ｘ１），ｘ３＝λ2 −ｘ１−ｘ２
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
［（Ｐ１＝Ｐ２）の場合］以降、この場合を楕円２倍演算と呼ぶ。楕円２倍演算：加算１回、減算３回、乗算３回、除算１回
λ＝（３ｘ１2 ＋ａ）／２ｙ1 ，ｘ３＝λ2 −２ｘ１，
ｙ３＝λ（ｘ１−ｘ３）−ｙ１
但し、上記演算はすべてｐを法とする剰余系で行われる。
【０００３】
楕円曲線暗号の安全性は、楕円曲線上の点Ａをｘ倍（すなわちＡをｘ回加算した）点をＢ（＝ｘ・Ａ）とする時、点Ａと点Ｂの値が分かったとしてもその値からｘを求めることが非常に困難であることに基づく。この性質を楕円曲線上の離散対数問題と呼ぶ。ＲＳＡ暗号の１０２４ビットと同程度の安全性を確保するためには、ｐ，ａ，ｘｉ，ｙｉ等のパラメータには１６０ビット程度の整数が推奨されている。
楕円曲線暗号の基本演算となる点Ｐのｋ倍点（ｋ・Ｐ）の演算は、上記の楕円曲線上の加法を用いて計算を行うこととなるが、この演算においてはλを求める際に剰余除算演算を行う必要がある。
【０００４】
このように、ディジタル署名などの暗号処理を行う際に剰余除算演算を行う必要がある。
上記剰余除算演算は拡張ユークリッド互除法等のアルゴリズムを用いて処理するのが一般的である。しかし、拡張ユークリッド互除法等では、剰余系での元のまま演算処理を行うため、多くの処理時間を必要とする。そのため、剰余系での元をモンゴメリ空間へ変換することにより、その剰余除算演算を行うことなく演算処理する方式（以下、モンゴメリ方式と呼ぶ）が用いられている。詳しくは、Peter L.Montgomery,“Modular Multiplication Without Trial Division”，Mathematics of Computation,44,pp.519-521,1985に述べられている。
【０００５】
モンゴメリ方式を使うためには、適当な剰余系での元をモンゴメリ空間へ変換し、モンゴメリ空間で演算をした後、剰余系の元へ再変換しなければならない。
【０００６】
【発明が解決しようとする課題】
しかしながら、このモンゴメリ空間への変換また剰余系への再変換の処理に時間がかかるために、変換が何度も行われる場合には、拡張ユークリッド互除法等を用いた時よりも処理全体が遅くなってしまうという問題がある。この発明はこの問題を解決した暗号処理装置、その方法、そのプログラム及びその記録媒体を提供することにある。
【０００７】
【課題を解決するための手段】
この発明によれば、剰余系からモンゴメリ空間へ変換するための第１乗算データとモンゴメリ空間から剰余系へ変換するための第２乗算データがデータ管理部に保存され、入力された正整数の変数Ａ，Ｂに対し、正整数の定数Ｎ，Ｒを用いて、Ａ-1Ｒ2 mod ＮとＡＢmod Ｎ及び／又はＡＢＲ-1mod Ｎを計算する第１演算処理部が設けられ、第２演算処理部により、データとデータ管理部の第１乗算データを第１演算処理部に入力して、そのデータをモンゴメリ空間へ変換し、モンゴメリ空間のデータとデータ管理部の第２乗算データを第１演算処理部に入力してそのデータを剰余系に変換し、更にモンゴメリ空間のデータを第１演算処理部に入力してそのデータの逆元を求めることができるように構成されている。更に好ましくは秘密鍵などをモンゴメリ空間に変換した秘密データもデータ管理部に保存され、秘密データを用いた演算が行われるようになされる。
【０００８】
【発明の実施の形態】
図１に、公開鍵暗号処理やディジタル署名処理などの暗号処理を行うこの発明の装置の実施形態を示す。
この発明においてはデータ管理部１００が設けられ、データ管理部１００に、データを剰余系からモンゴメリ空間へ変換するための第１乗算データとしてＲmod Ｎ又は／及びＲ2 mod Ｎと、データをモンゴメリ空間から剰余系に変換するための第２乗算データとしてＲ-1mod Ｎが保存され、更にこの例では秘密鍵ｄをモンゴメリ空間に変換した秘密データＤ＝ｄＲmod Ｎをデータ管理部１００に保存してある。Ｒ及びＮは正整数定数である。
【０００９】
またモンゴメリ方式を用いるために必要な演算を行う第１演算処理部２００が設けられる。第１演算処理部２００は入力された正整数Ａ，Ｂに対し、Ａ-1Ｒ2 mod ＮとＡＢmod Ｎ又は／及びＡＢＲ-1Ｎを計算する。この際、定数Ｒ及びＮは第１演算処理部２００内のレジスタに保持しておいてもよく、データ管理部１００から取出してもよい。
更に第２演算処理部３００が設けられる。第２演算処理部３００は、データ管理部１００内の第１乗算データとデータとを第１演算処理部２００へ入力して、そのデータを剰余系からモンゴメリ空間へ変換する機能３０１とデータ管理部１００内の第２乗算データとデータとを第１演算処理部２００へ入力してそのデータをモンゴメリ空間から剰余系へ変換する機能３０２、剰余系のデータ間の演算機能３０３、モンゴメリ空間データ内の演算機能３０４、更にデータ管理部１００に対するデータ格納機能３０５を具備する。
【００１０】
更にこの暗号処理装置４００に対するデータの入力部５００、暗号処理結果を外部へ出力する出力部７００を備えている。またこの実施例では暗号処理装置４００に、事前に計算可能なデータを計算しておく事前データ演算部６００が設けられ、事前データ演算部６００は、図２に示すように入力された正整数Ａに対し、ＡＲ-1mod Ｎを計算して出力し、またＡＲmod Ｎ及び／又はＡ-1Ｒ2 mod Ｎを計算し、これら計算結果を第２演算処理部３００のデータ格納部３０５によりデータ管理部１００に格納される。この例ではＡ＝１とすることにより事前データ演算部６００から第１乗算データＲmod Ｎ及び／又はＲ2 mod Ｎを、また第２乗算データＲ-1 mod Ｎを求めて、これらをデータ管理部１００に保存する。更にＡ＝ｄとしてＤ＝ｄＲmod Ｎを求めてデータ管理部１００に保存する。事前データ演算部６００としては、外部の電子計算機を用い、その演算結果を入力部５００から第２演算処理部３００を通じてデータ管理部１００に格納してもよい。
【００１１】
暗号、復号、ディジタル署名生成、署名検証などの暗号処理を実行する場合、適切なデータが入力部５００に入力され、第２演算処理部３００で適切な計算が行われる。その際モンゴメリ方式を用いるための演算に必要なデータＤS は剰余系→モンゴメリ空間変換機能３０１により、データ管理部１００から第１乗算データＲmod Ｎが取出され、これとＤS が第１演算処理部２００に入力され、第１演算処理部２００で剰余系データＤS がモンゴメリ空間データＤM ＝ＤS Ｒmod Ｎに変換されて第２演算処理部３００に戻される。この第１乗算データＲ2 mod Ｎ（＝Ａ）とＤS （＝Ｂ）を入力させ、ＡＢＲ-1mod Ｎの計算を第１演算処理部２００に行わせて、ＤM ＝ＤS Ｒmod Ｎを得てもよい。
【００１２】
第２演算処理部３００はモンゴメリ空間に変換されたデータと、秘密データＤなどのデータを第１演算処理部２００に入力させてモンゴメリ方式の計算を行わせ、あるいは一つのデータを入力させその逆元計算Ａ-1Ｒ2 mod Ｎを行わせる。第２演算処理部３００はモンゴメリ方式による演算結果を、モンゴメリ→剰余系変換機能３０２により、データ管理部１００の第２乗算データＲ-1mod Ｎと共に第１演算処理部２００に入力して、剰余系に変換したデータを戻してもらう。第２演算処理部３００はモンゴメリ演算機能３０４によりモンゴメリ空間データ間の加減算を行い、剰余系演算機能３０３により剰余系データについて剰余系において計算を行う。暗号処理の最終結果は剰余系データとして出力部７００から出力される。
【００１３】
以上の説明から理解されるように、この発明の暗号処理方法の実施形態は、図３に示すように、第１乗算データＲmod Ｎ及び／又はＲ2 mod Ｎと第２乗算データＲ-1mod Ｎ、秘密データＤ＝ｄＲmod Ｎをそれぞれ計算して、データ管理部に保存させる過程（Ｓ１）、
その後、第１乗算データをデータ管理部から取出し、これと剰余系データを第１演算処理部に入力させて、その剰余系データをモンゴメリ空間のデータに変換する過程（Ｓ２）、
秘密データＤをデータ管理部１００から取出し、これを用いた演算を行う過程（Ｓ３）、
更にデータ管理部から第２乗算データＲ-1mod Ｎを取出し、これとモンゴメリ空間データを第１演算処理部に入力して、そのデータを剰余系データに変換する過程（Ｓ４）
を少くとも含む。
実施例
以下、図１に示した暗号処理装置を用いて、楕円ＤＳＡの署名生成を行う実施例を図面と共に説明する。図１におけるデータ管理部１００に、次のシステム情報を記憶する。
【００１４】
▲１▼  有限体位数ｐと、楕円曲線パラメータ（ａ，ｂ）と、楕円曲線上の点Ｐ（ベースポイント）座標（Ｐｘ，Ｐｙ）と、ベースポイントの位数Ｎと、秘密鍵ｄ。
▲２▼  ｄをモンゴメリ空間へ変換した秘密データＤ（＝ｄＲmod Ｎ）と、剰余演算に用いるためのＲ-1mod ＮとＲmod Ｎ又は／及びＲ2 mod Ｎ各乗算データ。但し、ここで用いたＲは、Ｒ＞ｐ，Ｒ＞Ｎを満たす正整数、例えば、ｐ，Ｎのビット数をそれぞれ｜ｐ｜，｜Ｎ｜と表す時、｜ｐ｜＋１または｜Ｎ｜＋１のうち大きいほうに等しいビット長を持つ最小の正整数とする。
【００１５】
▲１▼に属するシステム情報は、以下の暗号処理が実行される前に、記憶されているものとする。
▲２▼に属するシステム情報の秘密データＤ以外は、以下の暗号処理が実行される前に、記憶されているものとする。
図４に、図１中の第２演算処理部３００が行う署名生成のフローチャートを示す。
ステップ４０１：開始
ステップ４０２：第２演算処理部３００で乱数ｋを生成。１＜ｋ＜ｎ−１
ステップ４０３：第２演算処理部３００は点Ｐのｋ倍点ｋＰを計算。
ステップ４０４：ｋＰのｘ座標をＸとして、第２演算処理部３００でＸmod Ｐ（＝ｕｘ）を計算。
ステップ４０５：ｕｘとデータ管理部１００からのデータＲmod Ｎを第１演算処理部２００へ入力し、演算結果（モンゴメリ空間に変換されたデータ）ｕｘＲmod Ｎ（＝Ｕ′）を第２演算処理部３００が受け取る。
ステップ４０６：ｋとデータ管理部１００からのデータＲmod Ｎを第１演算処理部２００へ入力し、演算結果（モンゴメリ空間に変換されたデータ）ｋＲmod Ｎ（＝Ｋ）を第２演算処理部３００が受け取る。
ステップ４０７：Ｋを第１演算処理部２００へ入力し、Ｋの逆元演算結果Ｋ-1Ｒ2 mod Ｎ（＝Ｋ′）を第２演算処理部３００が受け取る。
ステップ４０８：Ｕ′とデータ管理部１００からの秘密データＤを第１演算処理部２００へ入力し、演算結果Ｕ′Ｄmod Ｎ（＝Ｄ′）を第２演算処理部３００が受け取る。
ステップ４０９：入力部５００からの入力データ（メッセージ）ｍを一方向ハッシュ関数ｈで圧縮し、その値ｈ（ｍ）とデータ管理部１００からのデータＲmod Ｎを第１演算処理部２００へ入力し、演算結果（モンゴメリ空間に変換されたデータ）ｈ（ｍ）Ｒmod Ｎ（＝Ｈ）を第２演算処理部３００が受け取る。
ステップ４１０：第２演算処理部３００で（Ｈ＋Ｄ′）mod Ｎ（＝Ｓ′）を計算。
ステップ４１１：Ｋ′とＳ′を第１演算処理部２００へ入力し、演算結果Ｋ′Ｓ′mod Ｎ（＝Ｓ）を第２演算処理部３００が受け取る。
ステップ４１２：Ｓとデータ管理部１００からのデータＲ-1mod Ｎを第１演算処理部２００へ入力し、演算結果（剰余系に変換されたデータ）ＳＲ-1mod Ｎ（＝ｓ）を第２演算処理部３００が受け取る。この値ｓとステップ４０４で受け取った値ｕｘの組を署名として出力部７００から出力する。
ステップ４１３：終了。
【００１６】
なお楕円ＤＳＡ署名では、乱数ｋを生成し、ベースポイントＰのｋ倍点ｋＰ（Ｐｘ，Ｐｙ）を求め、ｒ＝Ｐｘmod ｐを求め、ｅ＝ｈ（ｍ）を求め、ｓ＝ｋ-1（ｅ＋ｄ・ｒ）mod Ｎを求め、ｒとｓをｍに対する署名としている。これより、ｒをステップ４０３で、ｒ＝Ｐｘ modｐをステップ４０４で、ｋ-1mod Ｎをステップ４０６と４０７で、ｄ・ｒをステップ４０８で、ｅ＋ｄ・ｒをステップ４１０でｋ-1（ｅ＋ｄ・ｒ）mod Ｎをステップ４１１でそれぞれ求めたことになる。
モンゴメリ方式を用いて楕円ＤＳＡで署名生成を実行する際、４つの剰余系での元ｄ，ｕｘ，ｋ，ｈ（ｍ）をモンゴメリ空間へ変換し、１つのモンゴメリ空間での元Ｓを剰余系の元に変換することが必須である。図４に示した実施例によれば、この５回の変換のうち、ｄは保存したデータＤを使用するから１回は変換の必要がなく、残り４回では事前に保持した第１、第２乗算データを用いて、高速に変換することができる。したがって、モンゴメリ空間へ変換するあるいは剰余系へ変換する処理時間が大幅に低減することができる。
【００１７】
図４に示した例ではステップ４０５〜４１２ではステップ４０９中のハッシュ値ｈ（ｍ）を求める以外は全てモンゴメリ空間で計算したが、必ずしもその必要はない。
例えばステップ４０８以後の処理を、図５に示すように剰余系に変換して行ってもよい。
ステップ５０１：図４中のステップ４０８で得られた演算結果Ｄ′と、データ管理部１００からのデータＲ-1mod Ｎを第１演算処理部２００に入力して、演算結果（剰余系に変換されたデータ）Ｄ′Ｒ-1mod Ｎ＝ｄ′を第２演算処理部３００が受け取る。
ステップ５０２：第２演算処理部３００は入力されたメッセージｍに対しハッシュ関数ｈを適用してハッシュ値ｈ（ｍ）を求める。
ステップ５０３：第２演算処理部３００はｈ（ｍ）とｄ′を剰余加算して（ｈ（ｍ）＋ｄ′）mod Ｎ＝ｓ′を求める。
ステップ５０４：第２演算処理部３００は図４中のステップ４０７の演算結果Ｋ′とデータ管理部１００よりのデータＲ-1mod Ｎを第１演算処理部２００へ入力して演算結果（剰余系に変換されたデータ）Ｋ′Ｒ-1mod Ｎ＝ｋ′を受け取る。
ステップ５０５：第２演算処理部３００は演算結果ｋ′と加算結果ｓ′との剰余乗算を行ってｋ′ｓ′mod Ｎ＝ｓを求める。このｓと図４のステップ４０４で求めたｕｘをメッセージｍに対する署名として出力する。
【００１８】
これら実施例から理解されるように秘密鍵ｄをモンゴメリ空間のデータＤ＝ｄＲmod Ｎに変換し、これをデータ管理部１００に保存しておけば、署名生成の都度、ｄをモンゴメリ空間へ変換する処理が省略できる。このようにしてその他の暗号処理においても同様の効果を得ることができる。
図４及び図５に示した暗号処理方法はコンピュータにプログラムを実行させて署名を生成させることもできる。この場合は例えば図６に示すように、入力部１０、出力部１１、データ管理部１２、乱数生成部１３、ハッシュ関数演算部１４、プログラムメモリ１５、ＣＰＵ（マイクロプロセッサ）１６がバス１７に接続され、データ管理部１２に、図４の実施例で説明したように、図１中のデータ管理部１００に保存されているシステム情報が格納される。乱数生成部１３は入力部１０より入力されたメッセージｍに対しハッシュ関数（１方向性関数）を適用する。プログラムメモリ１５には図４又は図５に示した方法をコンピュータに実行させるための暗号処理プログラムが格納されてあり、このプログラムをＣＰＵ１６が実行して署名ｓ，ｕｘを生成する。
【００１９】
以上に述べたように、この実施例によれば、暗号処理装置、事前データ演算処理装置を用いて楕円ＤＳＡ署名処理を高速に処理することができる。この発明によれば同様にしてＤＳＡ署名、ＥｌＧａｍａｌ署名、楕円ＥｌＧａｍａｌ署名、暗号、復号、検証などの暗号処理に対しても適用して高速処理が可能となる。特に剰余乗算を必要とする場合にモンゴメリ空間への変換、その逆変換のために用いる第１、第２乗算データを予め演算して保存しておき、これを利用することにより、高速度処理が可能となる。剰余乗算の場合も同様に高速処理が可能となる。
【００２０】
【発明の効果】
以上述べたようにこの発明によればモンゴメリ空間への変換、その逆変換のための第１、第２乗算データをデータ管理部に保存しておき、これを用いて変換処理を行うため暗号処理を高速に行うことができる。
【図面の簡単な説明】
【図１】この発明の実施形態の機能構成例を示すブロック図。
【図２】図１中の事前データ演算部６００の機能構成例を示す図。
【図３】この発明の方法の実施形態の例を示す流れ図。
【図４】図１を用いた楕円ＤＳＡ署名生成の具体的方法を示すフローチャート。
【図５】図４に示した方法の一部変形を示すフローチャート。
【図６】この発明装置をコンピュータで構成した場合の機能構成例を示す図。
【図１】
0003966714.tif 000002
【図２】
0003966714.tif 000003
【図３】
0003966714.tif 000004
【図４】
0003966714.tif 000005
【図５】
0003966714.tif 000006
【図６】
0003966714.tif 000007