(57)【特許請求の範囲】
【請求項１】
署名者装置の整数生成部が、秘密鍵として２つの整数ｐ，ｑを生成するステップと、
秘密鍵記憶部が、上記秘密鍵を記憶するステップと、
署名者装置の公開鍵生成部が、上記秘密鍵ｐ及びｑから公開鍵ｎをｎ＝ｐ2・ｑにより計算するステップと、
署名者装置の記憶部が、上記公開鍵を記憶するステップと、
署名者装置の乱数生成部が、メッセージｍに対し、乱数ｒを生成するステップと、
署名者装置のハッシュ関数演算部が、上記メッセージｍと上記乱数ｒとをビット結合し
た値に対しハッシュ演算Ｈを施して署名者ハッシュ値Ｈ（ｍ，ｒ）を計算するステップと、
署名者装置の乱数生成部が、乱数ｔを生成するステップと、
署名者装置の剰余有理式演算部が、上記乱数ｔを有理関数ｈの変数に代入して上記ｎを法とする署名者剰余演算を行うステップと、
ｗ計算部が、上記署名者ハッシュ値Ｈ（ｍ，ｒ）と上記署名者剰余演算結果ｈ（ｔ）mod ｎと上記秘密鍵ｐ，ｑとからｗを、
ｗ＝［（Ｈ（ｍ，ｒ）−（ｈ（ｔ）mod ｎ））／（ｐ・ｑ）］
（ここで［ａ］は、ａ以上の最小の整数値を表す）により計算するステップと、
剰余除算乗算部が、上記ｗと上記ｈ（ｔ）mod ｎとからｕを、
ｕ＝ｗ／ｈ´（ｔ）mod ｐ
（ここでｈ´（ｔ）はｈ（ｔ）の微分値を表す）により計算するステップと、
乗算加算部が、上記ｕと上記ｐ，ｑと上記ｔとからｓを、ｓ＝ｔ＋ｕ・ｐ・ｑにより計算するステップと、
署名者装置の通信部が、上記ｍに対する署名として上記ｓ及び上記ｒを、ｍと共に検証者装置へ送信するステップと、
検証者装置の通信部が、上記署名ｓ及びｒと上記メッセージｍとを署名者装置から受信するステップと、
検証者装置の記憶部が、上記署名ｓ及びｒと上記メッセージｍとを記憶するステップと、
検証者装置のハッシュ関数演算部が、上記メッセージｍと上記乱数ｒとをビット結合した値に対しハッシュ演算Ｈを施して検証者ハッシュ値Ｈ（ｍ，ｒ）を計算するステップと、
検証者装置の剰余有理式演算部が、上記ｓを上記有理関数ｈの変数に代入して、上記ｎを法とする検証者剰余演算を行うステップと、
比較部が、上記検証者剰余演算結果ｈ（ｓ）mod ｎと上記検証者ハッシュ値Ｈ（ｍ，ｒ）とから、上記署名ｓ及びｒが上記メッセージｍに対する正当な署名か否かを
Ｈ（ｍ，ｒ）＜ｈ（ｓ）mod ｎ＜Ｈ（ｍ，ｒ）＋２^２｜ｎ｜／３
（ここでａ^ｂはａbを表す）を満足するか否かにより検証するステップと、
を実行する安全性証明可能電子署名方法。
【請求項２】
署名者装置の整数生成部が、秘密鍵として２つの整数ｐ，ｑを生成するステップと、
秘密鍵記憶部が、上記秘密鍵を記憶するステップと、
署名者装置の公開鍵生成部が、上記秘密鍵ｐ及びｑから公開鍵ｎをｎ＝ｐ2・ｑにより計算するステップと、
署名者装置の記憶部が、上記公開鍵を記憶するステップと、
署名者装置の乱数生成部が、メッセージｍに対し、乱数ｒを生成するステップと、
署名者装置のハッシュ関数演算部が、上記メッセージｍと上記乱数ｒとをビット結合し
た値に対しハッシュ演算Ｈを施して署名者ハッシュ値Ｈ（ｍ，ｒ）を計算するステップと、
署名者装置の乱数生成部が、乱数ｔを生成するステップと、
署名者装置の剰余有理式演算部が、上記乱数ｔを有理関数ｈの変数に代入して上記ｎを法とする署名者剰余演算を行うステップと、
ｗ計算部が、上記署名者ハッシュ値Ｈ（ｍ，ｒ）と上記署名者剰余演算結果ｈ（ｔ）mod ｎと上記秘密鍵ｐ，ｑとからｗを、
ｗ＝［（Ｈ（ｍ，ｒ）−（ｈ（ｔ）mod ｎ））／（ｐ・ｑ）］
（ここで［ａ］は、ａ以上の最小の整数値を表す）により計算するステップと、
剰余除算乗算部が、上記ｗと上記ｈ（ｔ）mod ｎとからｕを、
ｕ＝ｗ・ｈ´（ｔ）(p-2)mod ｐ
（ここでｈ´（ｔ）はｈ（ｔ）の微分値を表す）により計算するステップと、
乗算加算部が、上記ｕと上記ｐ，ｑと上記ｔとからｓを、ｓ＝ｔ＋ｕ・ｐ・ｑにより計算するステップと、
署名者装置の通信部が、上記ｍに対する署名として上記ｓ及び上記ｒを、ｍと共に検証者装置へ送信するステップと、
検証者装置の通信部が、上記署名ｓ及びｒと上記メッセージｍとを署名者装置から受信するステップと、
検証者装置の記憶部が、上記署名ｓ及びｒと上記メッセージｍとを記憶するステップと、
検証者装置のハッシュ関数演算部が、上記メッセージｍと上記乱数ｒとをビット結合した値に対しハッシュ演算Ｈを施して検証者ハッシュ値Ｈ（ｍ，ｒ）を計算するステップと、
検証者装置の剰余有理式演算部が、上記ｓを上記有理関数ｈの変数に代入して、上記ｎを法とする検証者剰余演算を行うステップと、
比較部が、上記検証者剰余演算結果ｈ（ｓ）mod ｎと上記検証者ハッシュ値Ｈ（ｍ，ｒ）とから、上記署名ｓ及びｒが上記メッセージｍに対する正当な署名か否かを
Ｈ（ｍ，ｒ）＜ｈ（ｓ）mod ｎ＜Ｈ（ｍ，ｒ）＋２^２｜ｎ｜／３
（ここでａ^ｂはａbを表す）を満足するか否かにより検証するステップと、
を実行する安全性証明可能電子署名方法。
【請求項３】
秘密鍵として２つの整数ｐ，ｑを生成する整数生成部と、
上記秘密鍵ｐ及びｑを記憶する秘密鍵記憶部と、
上記秘密鍵ｐ及びｑから公開鍵ｎをｎ＝ｐ2・ｑにより計算する公開鍵生成部と、
上記公開鍵ｎを記憶する記憶部と、
署名作成時に乱数ｒとｔとを生成する乱数生成部と、
上記メッセージｍと上記乱数ｒとをビット結合した値に対しハッシュ演算Ｈを施して署名者ハッシュ値Ｈ（ｍ，ｒ）を計算するハッシュ関数演算部と、
有理関数ｈの変数に上記乱数ｔを代入して上記ｎを法とする署名者剰余演算を行う剰余有理式演算部と、
上記署名者剰余演算結果ｈ（ｔ）mod ｎと、上記署名者ハッシュ値Ｈ（ｍ，ｒ）と、上記秘密鍵ｐ及びｑとからｗを、
ｗ＝［（Ｈ（ｍ，ｒ）−（ｈ（ｔ）mod ｎ））／（ｐ・ｑ）］
（ここで［ａ］は、ａ以上の最小の整数値を表す）を計算するｗ計算部と、
上記ｗと上記ｈ（ｔ）mod ｎとからｕを、
ｕ＝ｗ／ｈ´（ｔ）mod ｐ
（ここでｈ´（ｔ）はｈ（ｔ）の微分値を表す）により計算する剰余除算乗算部と、
上記ｕと上記ｐ，ｑと上記ｔとからｓを、ｓ＝ｔ＋ｕ・ｐ・ｑにより計算する乗算加算部と、
上記ｓと上記ｒとを上記ｍに対する署名としてｍと共に検証者装置へ送信する通信部と
を具備する安全性証明可能電子署名の署名者装置。
【請求項４】
秘密鍵として２つの整数ｐ，ｑを生成する整数生成部と、
上記秘密鍵ｐ及びｑを記憶する秘密鍵記憶部と、
上記秘密鍵ｐ及びｑから公開鍵ｎをｎ＝ｐ2・ｑにより計算する公開鍵生成部と、
上記公開鍵ｎを記憶する記憶部と、
署名作成時に乱数ｒとｔとを生成する乱数生成部と、
上記メッセージｍと上記乱数ｒとをビット結合した値に対しハッシュ演算Ｈを施して署名者ハッシュ値Ｈ（ｍ，ｒ）を計算するハッシュ関数演算部と、
有理関数ｈの変数に上記乱数ｔを代入して上記ｎを法とする署名者剰余演算を行う剰余有理式演算部と、
上記署名者剰余演算結果ｈ（ｔ）mod ｎと、上記署名者ハッシュ値Ｈ（ｍ，ｒ）と、上記秘密鍵ｐ及びｑとからｗを、
ｗ＝［（Ｈ（ｍ，ｒ）−（ｈ（ｔ）mod ｎ））／（ｐ・ｑ）］
（ここで［ａ］は、ａ以上の最小の整数値を表す）を計算するｗ計算部と、
上記ｗと上記ｈ（ｔ）mod ｎとからｕを、
ｕ＝ｗ・ｈ´（ｔ）(p-2)mod ｐ
（ここでｈ´（ｔ）はｈ（ｔ）の微分値を表す）により計算する剰余除算乗算部と、
上記ｕと上記ｐ，ｑと上記ｔとからｓを、ｓ＝ｔ＋ｕ・ｐ・ｑにより計算する乗算加算部と、
上記ｓと上記ｒとを上記ｍに対する署名としてｍと共に検証者装置へ送信する通信部と
を具備する安全性証明可能電子署名の署名者装置。
【請求項５】
請求項３、４のいずれかに記載の署名者装置としてコンピュータを機能させるための電子署名プログラム。
【請求項６】
請求項５に記載の電子署名プログラムを記録したコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、電子化された文書の稟議／決済、電子投票システム等で、署名対象に電子的署名／捺印を付与する電子署名方法、その装置及びプログラム、その記録媒体に関する。
【０００２】
【従来の技術】
従来技術として多数の電子署名方式が知られているが、ＥＳＩＧＮ署名は、素因数分解問題に基づく高速な電子署名であり、ＲＳＡ署名に比較して署名作成が数十倍高速であり、ＩＣカードのような計算能力がない装置の上でも適用可能である。以下にＥＳＩＧＮ署名を簡単に述べる。
署名者Ａは、整数ｐ，ｑを秘密鍵とし、ｎ＝ｐ2 ｑを公開鍵とし、有理式関数ｈ（ｘ）を公開し、メッセージｍに対してハッシュ関数演算を実施してＨ（ｍ）（Ｈ（ｍ）∈Ｚn ）を生成する。また乱数ｔ∈Ｚ* pqを生成し、以下の演算を行う。
【０００３】
ｗ＝［（Ｈ（ｍ）−（ｈ（ｔ）mod ｎ））／ｐｑ］
なお、［ａ］は、ａ以上の最小の整数値を意味する。次に、以下の方程式を満足するｕを求める。
ｗ≡ｈ′(ｔ）ｕ（mod ｐ）
ここで、ｈ′は、微分ｄｈ／ｄｘを意味し、有理式関数ｈが定まると、有理式関数ｄｈ／ｄｘは定まる。従って、ｔが与えられたとき、（ｄｈ（ｔ）／ｄｘ）mod   ｐの値を求め、次式によりｕを求める。なおｕが存在するには、ｐが素数よりｈ′(ｔ）mod ｐ≠０で十分となる。
【０００４】
ｕ＝ｈ′(ｔ）-1ｗ mod ｐ＝ｈ′(ｔ)(p-2)ｗ mod ｐ
ｕが求まると次式により署名ｓ（ｓ∈Ｚ*n ）を求める。
ｓ＝ｔ＋ｕｐｑ
ｍとｓの対を検証者Ｂへ送る。
検証者Ｂは、署名ｓが署名者Ａのメッセージｍに対する正しい署名であるかどうかを以下の検証式を満足するかどうかで検査する。検証者は、ｍに対しハッシュ関数を施し、Ｈ（ｍ）を生成し、またｈ（ｓ）mod ｎを演算し、
Ｈ（ｍ）＜ｈ（ｓ）mod ｎ＜Ｈ（ｍ）＋２^２｜ｎ｜／３
（ここでＡ^ＢはＡB を表わす）
なる関係を満たせば、この署名付きメッセージｍを正しいもの（ＯＫ）とし、さもなければ不正なもの（ＮＧ）とする。｜ｎ｜は公開鍵ｎのビット長（数）を表わす。
【０００５】
このＥＳＩＧＮ署名の安全性は、ｅ−乗根近似問題の解読が困難であることに関係している。
定義  ｅ−乗根近似問題とは、公開鍵｛ｎ，ｅ｝とｙ∈Ｚが与えられたとき、ｙ＜ｓe  mod ｎ＜ｙ＋２^２｜ｎ｜／３（ここでＡ^ＢはＡB を表わす）となるｓ∈Ｚを見つける問題である。このようなｓを見つけるのが困難な時、ｅ−乗根近似問題は難しいという。ｅ−乗根近似問題が難しいという仮定を、ｅ−乗根近似仮定と呼ぶ。
ｅ−乗根近似仮定についてこれまで様々な研究が行われてきたが、ｅが４以上の場合について現在まで有効な攻撃は発見されていない。
【０００６】
有理式ｈの次数をｅとすると、ＥＳＩＧＮ署名の安全性とｅ−乗根近似仮定が関係していることは知られている。ただし、ＥＳＩＧＮ署名の安全性がｅ−乗根近似仮定で証明されているわけではない。単に、ｅ−乗根近似問題を解くことが出来るならば、ＥＳＩＧＮ署名を破ることが出来るということがわかっているだけである。
適応的選択文書攻撃は電子署名に対するもっとも強い攻撃法である。この攻撃法は、不正者Ａが正規の署名者に繰り返し自分の望むメッセージに署名を付けてもらい、最後に正規の署名者が署名していないメッセージに対し署名を出力する。不正者は、署名者につけてもらった署名をもらいながら適応的に次のメッセージを作り署名をもらうことができるので、この攻撃は適応的選択文書攻撃と呼ばれる。
【０００７】
ＥＳＩＧＮ署名がランダムオラクルモデル（ランダム関数）で適応的選択文書攻撃に対して安全であると証明するには、背理法を使う。仮にＥＳＩＧＮ署名を適応的選択文書攻撃で偽造できる敵（デバイス）Ａが存在したとする。すると、その敵（デバイス）Ａをブラックボックスとして使って、ｅ−乗根近似問題を解くアルゴリズムＢを構成できることになる。しかしｅ−乗根近似問題は難しい問題と仮定しているので、結局そのような敵（デバイス）Ａが存在することは前記仮定と矛盾する。
アルゴリズムＢが、敵Ａをブラックボックスに使ってｅ−乗根近似問題を解く時、アルゴリズムＢは、ｅ−乗根近似問題を解くアルゴリズムを、敵Ａをブラックボックスに使ってシミュレーションしていると言う。適応的選択文書攻撃により署名を偽造するには、文書ｍに対する署名者から署名ｓと、その文書と、検証式とから、秘密鍵ｐ，ｑを知ることになる。よって、このシミュレーションの中で、敵Ａはハッシュ関数Ｈと署名関数をオラクルとして利用出来る。Ｈをランダム関数と仮定した時、このシミュレーションはランダムオラクルモデルで行われているという。
【０００８】
Ｂは敵Ａがオラクルに聞いてくる質問に答えを返してやらなければいけない（なぜならば、敵Ａはハッシュオラクルと署名オラクルの力を借りることでようやく署名の偽造ができるので、正しい答えを返してやらないと正常に動作しないかもしれない）。もちろんＢは上記のようなオラクルは持っていないので自力で質問の答えを作らなければいけなく、この部分をどうするかが、ブラックボックスシミュレーションの最大の要点である。
さて上記の設定で、従来のＥＳＩＧＮ署名について、ＥＳＩＧＮ署名が安全性（ｅ−乗根近似仮定）を保証しているかを確認するシミュレーションは次のようになる。
【０００９】
敵Ａが文書ｍの署名を署名オラクルに要求してきた時：
そのｍが既にハッシュオラクルに聞いたことのあるｍと同一であれば、その先の要求の際に定めたｓを返す。それ以外の時は、
１．まずｓをランダムに選び、ｈ（ｓ）mod ｎを計算する。
２．ｈ（ｓ）mod ｎ−２^２｜ｎ｜／３＜Ｈ＜ｈ（ｓ）なるＨ、つまり検証式を満すＨをひとつ選ぶ（ここでＡ^ＢはＡB を表わす）。
３．Ｈ＝Ｈ（ｍ）とハッシュ関数Ｈの出力値を定義し、（ｍ，Ｈ，ｓ）を記録しておく。
４．ｓを署名オラクルの答えとして答えを返す。
【００１０】
敵Ａが文書ｍのハッシュ値をハッシュオラクルに要求してきた時：
そのｍが既に署名オラクルに聞いたことのあるｍと同一の場合は、その先の要求の際に選んだＨを返す。それ以外の時は、
１．まずｓをランダムに選び、ｈ（ｓ）mod ｎを計算する。
２．ｈ（ｓ）mod ｎ−２^２｜ｎ｜／３＜Ｈ＜ｈ（ｓ）なるＨをひとつ選ぶ（
ここでＡ^ＢはＡB を表わす）。
３．Ｈ＝Ｈ（ｍ）とハッシュ関数Ｈの出力値を定義し、（ｍ，Ｈ，ｓ）を記録しておく。
４．Ｈをハッシュオラクルの答えとして答えを返す。
【００１１】
このシミュレーションには欠点がある。それは、敵Ａが同じ文書ｍに対して二度署名オラクルに署名を求めてきたと考えよう。すると、上記のやり方では、同じ文書ｍには同じ署名ｓしか返せない。しかし、現実のＥＳＩＧＮ署名では毎回違う乱数ｔを選ぶので同じ署名が返ってくるというのはおかしい。敵Ａは本来の適応的文書攻撃の攻撃環境を与えられていないので、署名の偽造はできないかもしれない。つまりＥＳＩＧＮ署名が安全性つまりｅ−乗根近似仮定を保証していることを確認するためのシミュレーションを行うことができない。このためこのシミュレーションにより、ｅ−乗根近似問題を解くアルゴリズムが存在するという矛盾に持ち込むことはできない。
【００１２】
【発明が解決しようとする課題】
以上述べたように従来のＥＳＩＧＮ署名は、安全性の証明をすることができるものでなかった。
従来のＥＳＩＧＮ署名を変更することにより、適応的選択文書攻撃に対する安全性をｅ−乗根近似問題の困難性に帰着することが試みられている（T.Okamoto他,TSH-ESIGN：Efficient digital signature scheme using trisection size hash,Proposal to IEEE P1363a,Nov.1998）。しかしこの手法は、従来の定義より狭い攻撃法に対して証明がなされるに過ぎない。
【００１３】
この発明の目的は従来の定義での適応的選択文書攻撃に対する安全性をｅ−乗根近似問題の困難に帰着することができるようにＥＳＩＧＮ署名を変更した署名方法、その装置、及びプログラム、その記録媒体を提供することにある。
【００１４】
【課題を解決するための手段】
この発明によれば、従来のＥＳＩＧＮ署名と異なる点は、署名を生成する際に対象メッセージｍごとに乱数ｒを生成し、ｍとｒに対しハッシュ演算を施し、Ｈ（ｍ，ｒ）を求め、Ｈ（ｍ，ｒ）を従来のＥＳＩＧＮ署名のＨ（ｍ）として処理して署名ｓを求め、検証者装置へｍとその署名（ｓ，ｒ）を送り、検証者装置ではＨ（ｍ，ｒ）を演算し、従来のＥＳＩＧＮ署名の検証式においてＨ（ｍ）をＨ（ｍ，ｒ）として検証を行う。
この発明の署名方法によれば、その安全性を保証できることを確認するためのシミュレーションを次のように行うことができる。
【００１５】
敵Ａが文書ｍの署名を署名オラクルに要求してきた時：
１．まずｓをランダムに選び、ｈ（ｓ）mod ｎを計算する。
２．ｈ（ｓ）mod ｎ−２^２｜ｎ｜／３＜Ｈ＜ｈ（ｓ）なるＨをひとつ選ぶ（ここでＡ^ＢはＡB を表わす）。
３．ｒをランダに選び、Ｈ＝Ｈ（ｍ，ｒ）とハッシュ関数Ｈの出力値を定義する。
４．ｒ，ｓを署名オラクルの答えとして答えを返す。
同じｍを質問してきても、ステップ１から新しく繰り返して、新しい（ｒ，ｓ）を返す。従って同一ｍの質問に対し、ｓ，ｒの何れもランダムに選ぶため、同一の（ｓ，ｒ）が返されることはない。
【００１６】
敵Ａが文書ｍと乱数ｒのハッシュ値をハッシュオラクルに要求してきた時はもっと単純になる。
１．Ｈをランダムに選び、Ｈ＝Ｈ（ｍ，ｒ）はハッシュ関数Ｈの出力値を定義する。
２．Ｈをハッシュオラクルの答えとして答えを返す。
これによりＢは、同じｍに対して異なった署名を返すことが出来、シミュレーションは巧く行く。従ってｅ−乗根近似問題を解くことができるＢが存在することになり、ｅ−乗根近似問題は難しい問題であるとした仮定と矛盾することになる。このようにこの発明の署名方法はその安全性を証明することができる。
【００１７】
なお、従来の電子投票や電子現金方式の中にも、真の情報に乱数を結合したものを新たに情報とみなすことで、安全性を高めることを行っているものもあるが、この発明とは意味が本質的に異なる。それらでの乱数の付加は、電子投票や電子現金に必要とされる安全性の要件（二重投票や同一コインの二重使用等）を満たすために行われている。
一方、確定的な電子署名方式（同一メッセージに対しては常に同じ署名を返すような電子署名方式）において、真のメッセージに乱数を結合して新たなメッセージとみなし署名することで確率的な電子署名方式（同一メッセージに対しても違う署名を返す可能性のある電子署名方式）に変換し、安全性を高めることを行っているものもあるが、これもこの発明とは意味が本質的に異なる。これらは多くの場合、確定的な電子署名方式より確率的な電子署名方式が安全であるという直感に従っているだけである。
【００１８】
この発明方法は、確率的で形の特定されたある電子署名方法においてメッセージに乱数をつけることで安全性の証明を可能に（つまり、安全性の保障を）したものであり、上記した従来のような乱数の利用法とは本質的に異なっている。
【００１９】
【発明の実施の形態】
以下、この発明の実施形態を図を参照して説明する。
図１にこの発明方法が適用されるシステムの構成例を示す。署名者装置１００と検証者装置２００は安全でない通信路３００を介して結合することができる。署名者装置１００は登録センタ装置４００に署名者装置の公開鍵を登録することができ、検証者装置２００は登録センタ装置４００から署名者装置１００の公開鍵を取得することができる。
（１）鍵の登録
図２にこの発明による署名者装置１００の機能構成例を示す。署名者装置１００がシステムに加入するとき、鍵生成部１０１の整数生成部１０１ａで秘密鍵として２つの整数ｐ，ｑを生成し、それを秘密鍵記憶部１０２に秘密に保持し、また公開鍵生成部１０１ｂでｎ＝ｐ2 ｑを演算して公開鍵ｎを生成し、これを記憶部１０３に格納すると共にｎを登録センタ装置４００の公開鍵簿４００ａに登録する。
【００２０】
（２）署名の作成
以降では、署名者装置１００がメッセージｍに署名する場合について説明する。従来のＥＳＩＧＮ署名と同様に、ｘ，ｙ∈Ｚn （Ｚn ＝｛０，１，…，ｎ−１｝）とし、また、Ｚ*n（Ｚn の中で、ｎの約数と既約なもの）とし、有理関数ｈが定義されており、
ｙ≡ｈ（ｘ）（mod ｎ）
という関係を満足し、
ｈ（ｘ）＝ａ（ｘ）／ｂ（ｘ）
となるような多項式関数ａ（ｘ）及びｂ（ｘ）が存在する。
【００２１】
署名者装置１００は、まず、乱数生成部１０４を用いて、適当な長さは長い程安全性が高いが、それ程長くしても意味がなく、素因数分解の困難性の問題から例えば１６０ビットの乱数ｒを生成し、乱数ｒとメッセージｍをハッシュ関数演算部１０５に入力してＨ（ｍ，ｒ）（Ｈ（ｍ）∈Ｚn ）を演算する。
また乱数生成部１０４を用いて、乱数ｔ∈Ｚ* pqを生成し、その乱数ｔを剰余有理式演算部１０６に入力してｈ（ｔ）mod ｎを演算し、減算部１０７でＨ（ｍ，ｒ）からｈ（ｔ）mod ｎを減算し、その結果を除算部１０８において秘密鍵ｐ，ｑで割算し、切り上げ演算部１０９で切り上げ演算して、
ｗ＝［（Ｈ（ｍ，ｒ）−（ｈ（ｔ）mod ｎ））／ｐｑ］
を求める。なお、［ａ］は、ａ以上の最小の整数値を意味し、この記号を実行する演算部を「切り上げ演算部」と呼ぶ。次に、以下の方程式を満足するｕを求める。
【００２２】
ｗ≡ｈ′(ｔ）ｕ（mod ｐ）
ここでｈ′（ｔ）＝ｄｈ（ｔ）／ｄｘ
例えば、剰余有理式演算部１１０を用いてｈ′(ｔ）mod ｐを求め、更に、剰余除算部１１１でｈ′(ｔ）-1  mod ｐを演算し、この結果に対し、剰余乗算部１１２でｗを乗算してｕを求める。なおｕが存在するには、ｐが素数よりｈ′(ｔ） mod       ｐ≠０で十分となる。またｕを求めるには、図２中に破線で示すように剰余べき乗算部１１３でｈ′(ｔ）(p-2) mod ｐを演算し、その結果に対し、剰余乗算部１１２でｗを乗算してもよい。つまりｕは次式により求めることができる。
【００２３】
ｕ＝ｈ′(ｔ）-1ｗ mod ｐ＝ｈ′(ｔ)(p-2)ｗ mod ｐ
このようにして得られたｕに対し、秘密（署名）鍵ｐ，ｑを乗算部１１４で乗算し、その結果に乱数ｔを加算部１１５で加算して
ｓ＝ｔ＋ｕｐｑ
を求める。このｓ（ｓ＝∈Ｚ*n ）と乱数ｒをメッセージｍに対する署名として、ｍと（ｓ，ｒ）を検証者装置２００へ通信部１１６より送信する。
なお署名者装置１００はメッセージｍを入力する入力部１１７を備え、入力されたメッセージｍは必要に応じて一旦、記憶部１０３に格納されるようにすることもできる。
【００２４】
（３）署名の検査
検証者装置２００は図３に示すように通信部２０１に（ｍ，ｓ，ｒ）を受信すると、これを必要に応じて記憶部２０２に一度記憶し、ｍ，ｒをハッシュ関数演算部２０３に入力して、Ｈ（ｍ，ｒ）を演算生成し、これに対し加算部２０４で２^２｜ｍ｜／３（ここでＡ^ＢはＡB を表わす）を加算し、また剰余有理式演算部２０５で受信したｓに対しｈ（ｓ）mod ｎを演算する。公開鍵ｎは記憶部２０２に格納してあればそれを用い、なければ登録センタ装置４００から取得する。比較部２０６で演算部２０３，２０４，２０５の各演算結果が次式の関係を満すかを比較検証する。
【００２５】
Ｈ（ｍ，ｒ）＜ｈ（ｓ）mod ｎ＜Ｈ（ｍ，ｒ）＋２^２｜ｎ｜／３
（ここでＡ^ＢはＡB を表わす）
上記検査に合格すれば、この受信した署名ｓ，ｒがメッセージｍに対する正しい署名としてＯＫを示す信号を、さもなければ不正なものとしてＮＧを示す信号を比較部２０６は出力する。
署名者装置１００はコンピュータにより機能させることもできる。その場合は図２に示した署名者装置としてコンピュータに機能させるためのプログラムをコンピュータに、ＣＤ−ＲＯＭや可撓性磁気ディスクなどの記録媒体からコンピュータにインストールし、又は通信回線を介してダウンロードして、そのプログラムをコンピュータに実行させればよい。上述では乱数ｔを変調とする有理関数の剰余演算として、１変調有理関数ｈ（ｘ）を用いたが、多変数有理関数ｈ（ｘ1，…，ｘi）を用いて複数のしょめいを作成する電子署名方法にもこの発明を適用できる。多変調有理関数を用いる方法は例えば特開平５−２６００４２号公報に示されている。
【００２６】
【発明の効果】
以上述べたようにこの発明は、高速で安全性を保証した電子署名方法を構成する。安全性の保証については既に述べた通りである。この発明の電子署名方法の高速性をＲＳＡ署名と比較する。
上記実現例として、ｈ（ｘ）＝ｘ^２4 （Ａ＾ＢはＡB を表わし、ｈ（ｘ）は２4 次の多項式）である場合について考える。このとき署名生成のための計算量は、法ｎ（ｎ；１０２４ビットとする）の下での剰余乗算の回数が４回、法ｐ（ｐは、ｎの１／３の長さ）の下での剰余乗算が２回、剰余除算が１回となる。これは、法ｎの下での剰余乗算に換算すると４＋（２＋１／９）ｃ＜１１となる（ここで、ｃは、剰余除算の計算量／剰余乗算の計算量であり、高々ｃ＜３）。一方、ＲＳＡ法の剰余乗算の計算量が数１００回以上であることより、この発明の方法は、ＲＳＡ法より数倍以上の高速処理が可能である。
【図面の簡単な説明】
【図１】この発明方法が適用されるシステムの構成例を示す図。
【図２】署名者装置の機能構成例を示すブロック図。
【図３】認証者装置の機能構成例を示すブロック図。
【図１】
0003946082.tif 000002
【図２】
0003946082.tif 000003
【図３】
0003946082.tif 000004