JPH06308882A - 楕円曲線に基づく公開鍵暗号システム、その鍵生成装置、その暗号化装置及びその復号化装置 - Google Patents

Abstract

(57)【要約】 （修正有） 【目的】 パラメータの素数に制限をなくして、一層安
全を高める。 【構成】 任意の素数ｐ，ｑに対し、楕円曲線Ｅ
_p （ａ，０）：ｙ² ≡ｘ³ ＋ａｘ（mod p)の位数とその
ａとの関係を示す識別子と位数との対応を示す位数表を
装置２２、２３で生成し、各位数と互いに素な整数ｅを
選び、各位数を法としてｅの逆元を計算して、復号化鍵
を求め楕円曲線Ｅ_p （ａ_p ，０），Ｅ_q （ａ_q ，０）の
ａ_p ，ａ_q と復号化鍵を関係付ける識別子と復号化鍵と
の対応付けを示した復号化鍵表を生成する。ｅとｎ（＝
ｐ・ｑ）とを公開ファイル装置１２に復号化装置（加入
者）１６ごとに登録する。送信者は公開ファイル装置１
２より受信者の公開鍵ｅ，ｎを入手し、平文の組Ｍ＝
（ｍ_x ，ｍ_y ）からＥ_n （ａ_M ，０）のパラメータａ_M
を計算器２８で計算し、Ｍの楕円曲線Ｅ_n （ａ_M ，０）
上でｅ倍した点Ｃを乗算器２９で計算して暗号文の組と
して受信者に送信する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】この発明はデジタル化された文書
を公開鍵を用いて楕円曲線に基づいて暗号化する公開鍵
暗号化システム、これに用いられる鍵を生成する装置、
平文を暗号化する装置及び暗号文を平文に復号化する装
置に関する。

【０００２】

【従来の技術】まず、楕円曲線に関する記号の説明をす
る。素数ｐとパラメータａ，ｂに対しｙ² ≡ｘ³ ＋ａｘ
＋ｂ（mod p)を満たす点の集合に無限遠点Ｐ₀ を加えた
集合を楕円曲線Ｅ_p （ａ，ｂ）と呼ぶ。楕円曲線Ｅ
_p （ａ，ｂ）内の点の個数を＃Ｅ_p（ａ，ｂ）と書く。
素数ｐ，ｑ（それぞれ５以上）、その積ｎ（＝ｐｑ）と
パラメータａ，ｂに対し、ｙ² ≡ｘ³ ＋ａｘ＋ｂ（mod
n)を満たす点の集合に無限遠点Ｐ₀ を加えた集合を楕円
曲線Ｅ_n （ａ，ｂ）と書く。

【０００３】１９９１年に楕円曲線に基づく公開鍵暗号
（ＫＭＯＶ方式）が小山らにより提案された（Ｋ．Ｋｏ
ｙａｍａ，Ｕ．Ｍ．Ｍａｕｒｅｒ，Ｔ．Ｏｋａｍｏｔｏ
ａｎｄ Ｓ．Ａ．Ｖａｎｓｔｏｎｅ，“Ｎｅｗ ｐｕ
ｂｌｉｃ−ｋｅｙ ｓｃｈｅｍｅｓ ｂａｓｅｄ ｏｎ
ｅｌｌｉｐｔｉｃ ｃｕｒｖｅｓ ｏｖｅｒ ｔｈｅ
ｒｉｎｇ Ｚ_n ”，Ｌｅｃｔｕｒｅ Ｎｏｔｅ ｉｎ
ＣｏｍｐｕｔｅｒＳｃｉｅｎｃｅ ｖｏｌ．５７６，
ｐｐ．２５２−２６６（１９９１），特願平４−４８２
８５号）。この方式は、パラメータｎ（＝ｐｑ）の素因
数分解の困難さに安全性の根拠をおいている。ＫＭＯＶ
方式は、パラメータの素数ｐ，ｑがｐ≡ｑ≡２（ｍｏｄ
３）またはｐ≡ｑ≡３（ｍｏｄ４）でなければならない
という制限がある。

【０００４】ｐ≡ｑ≡２（ｍｏｄ３）の場合のＫＭＯＶ
方式を簡単に説明する。素数ｐ，ｑを選び、その積をｎ
とする。ｐ＋１とｑ＋１の最小公倍数をΨ_n とする。そ
のΨ _n と互いに素な値ｅを選び、ｅ・ｄ≡１（mod
Ψ_n ) をみたすｄを計算する。ｅ，ｎが公開鍵であり、
ｄが秘密鍵である。送信者は平文の組Ｍを楕円曲線Ｅ_n
（０，ｂ）：ｙ² ≡ｘ³ ＋ｂ（mod n)上でｅ倍した点Ｃ
を暗号文の組として送信する。受信者はＣを楕円曲線Ｅ
_n （０，ｂ）：ｙ² ≡ｘ³ ＋ｂ（mod n)上でｄ倍した点
Ｍを平文の組として得る。

【０００５】ｐ≡ｑ≡３（mod 4)の場合のＫＭＯＶ方式
を簡単に説明する。素数ｐ，ｑを選び、その積をｎとす
る。ｐ＋１とｑ＋１の最小公倍数をΨ_n とする。そのΨ
_n と互いに素な値ｅを選び、ｅ・ｄ≡１（mod Ψ_n ) を
みたすｄを計算する。ｅ，ｎが公開鍵であり、ｄが秘密
鍵である。送信者は平文の組Ｍを楕円曲線Ｅ_n （ａ，
０）：ｙ² ≡ｘ³ ＋ａｘ（mod n)上でｅ倍した点Ｃを暗
号文の組として送信する。受信者はＣを楕円曲線Ｅ
_n （ａ，０）：ｙ² ≡ｘ³ ＋ａｘ（mod n)上でｄ倍した
点Ｍを平文の組として得る。

【０００６】

【発明が解決しようとする課題】従来技術のＫＭＯＶ方
式はパラメータｎの素因数分解の困難さに安全性の根拠
をおいている。しかし、ＫＭＯＶ方式においてパラメー
タｎの素因数であるｐ，ｑの値がｐ≡ｑ≡２（ｍｏｄ
３）またはｐ≡ｑ≡３（ｍｏｄ４）でなければならない
ので、パラメータｎの素因数分解が容易になる場合があ
り、安全性が低かった。

【０００７】この発明の目的はパラメータの素数ｐ，ｑ
の選択に制限をなくすことにより安全性を一層高めた楕
円曲線に基づく公開鍵暗号システムを提供することにあ
る。

【０００８】

【課題を解決するための手段】請求項１の発明によれ
ば、受信者ごとに、任意に選んだ素数ｐ，ｑと対応した
暗号化鍵ｅ，ｎが公開ファイル装置に登録され、各ｐ，
ｑ，ｅの組ごとに、楕円曲線Ｅ_p （ａ_p ，０）：ｙ² ≡
ｘ³ ＋ａ_p ｘ（mod p)と楕円曲線Ｅ_q （ａ_q ，０）：ｙ
² ≡ｘ³ ＋ａ_q ｘ（mod q)のパラメータａ_p ，ａ_q と復
号化鍵とを関係付ける識別子と復号化鍵とを対応付ける
復号化鍵表が生成され、その復号化鍵表及び対応ｐ，ｑ
が記憶され、暗号化装置で、公開ファイル装置から得た
送信相手の公開鍵ｅ，ｎを用いて平文の組Ｍ＝（ｍ_x ，
ｍ_y ）から楕円曲線Ｅ_n （ａ_M ，０）：ｙ² ≡ｘ³ ＋ａ
_M ｘ（mod n)のパラメータａ_M を計算し、Ｍの楕円曲線
Ｅ_n（ａ_M ，０）上でｅ倍した点Ｃを暗号文の組として
送信され、復号化装置で暗号文の組Ｃから楕円曲線Ｅ_p
（ａ_p ，０）：ｙ² ≡ｘ³ ＋ａ_p ｘ（mod p)と、楕円曲
線Ｅ_q （ａ_q ，０）：ｙ² ≡ｘ³ ＋ａ_q ｘ（mod q)のパ
ラメータａ_p ，ａ_q を計算し、これらａ_p ，ａ_q から識
別子を求め、この識別子により復号化鍵表を参照して復
号化鍵ｄ_p ，ｄ_q を求め、Ｃを楕円曲線Ｅ_p （ａ_p ，
０）上でｄ_p 倍した点Ｍ_p と、Ｃを楕円曲線Ｅ
_q （ａ_q ，０）上でｄ_q 倍した点Ｍ_q とを求め、これら
Ｍ_p ，Ｍ_q から中国剰余定理を用いて平文の組Ｍを得
る。

【０００９】表現を簡単にするために、ｘとｙの最大公
約数を計算することをｇｃｄ（ｘ，ｙ）と書き、楕円曲
線Ｅ_p （ａ，ｂ）：ｙ² ＝ｘ³ ＋ａｘ＋ｂ（mod p)上で
演算を行なうことをｏｖｅｒ Ｅ_P （ａ，ｂ）と書くこ
とにする。この発明による鍵生成装置、暗号化装置、復
号化装置のそれぞれの動作手順を以下に述べる。

【００１０】（１）鍵生成装置の動作手順 鍵生成装置は位数表生成装置と復号化鍵表生成装置から
成る。 （１．１）位数表生成装置の動作手順 位数表は各識別子に対する位数を示すものであって、位
数は楕円曲線Ｅ_p （ａ，０）：ｙ² ≡ｘ³ ＋ａｘ（mod
p)の位数であり、識別子はこの位数とパラメータａとの
関係を示すものである。 １．入力は素数ｐとする。 ２．もしｐ≡３（mod 4)ならば、位数表は とし、これを出力し、位数表生成装置の動作は終了す
る。 ３．ｐ≡３（mod 4)でなければ、ｐ＝ｓ² ＋ｔ² をみた
すｓ，ｔを計算する。ただし、ｓは正の奇数、ｔは正の
偶数とする。 ４．もし、ｓ≡１（mod 4)ならば、 Ｎ_p0＝ｐ＋１−２ｓ， Ｎ_p2＝ｐ＋１＋２ｓ とし、さもなければ、 Ｎ_p0＝ｐ＋１＋２ｓ， Ｎ_p2＝ｐ＋１−２ｓ とする。 ５．乱数を発生させその中から平方非剰余ｈを見つけ
る。 ６．楕円曲線Ｅ_p （ｈ，０）上の点Ｒをランダムに選
ぶ。 ７．ｋ_t ＝ｇｃｄ（ｐ＋１−２ｔ，ｐ＋１＋２ｔ）と
し、以下の式が成立しなければ、つまりｋ_t ・ＲがＥ_p
（ｈ，０）の無限遠点になれば６．に戻る。

【００１１】 ｋ_t ・Ｒ≠Ｐ₀ ｏｖｅｒ Ｅ_p （ｈ，０） ８．Ｅ_p （ｈ，０）上でＲをｋ_t 倍した値が無限遠点Ｐ
₀ になり、もし、（ｐ＋１−２ｔ）・Ｒ＝Ｐ₀ ｏｖｅｒ
Ｅ_p （ｈ，０）ならば、つまりＲをＥ_p （ｈ，０）上
で（ｐ＋１−２ｔ）倍した値が無限遠点Ｐ₀ となるなら
ば、 Ｎ_p1＝ｐ＋１−２ｔ， Ｎ_p3＝ｐ＋１＋２ｔ さもなければ、 Ｎ_p1＝ｐ＋１＋２ｔ， Ｎ_p3＝ｐ＋１−２ｔ とする。 ９．τ_p1＝ｈ^(p-1)/4 mod p を計算する（τ_p1≠±
１）。 １０．τ_p0＝１，τ_p2＝−１，τ_p3＝−τ_p1として位数
表を とし、これを出力し、位数表生成装置の動作は終了す
る。

【００１２】同様にして素数ｑについて位数表 を生成する。

【００１３】 （１．２）復号化鍵表生成装置の動作手順 以上のようにして生成された位数表と素数ｐ，ｑとを用
いて復号化鍵を生成するが、この生成手順は（１）ｐ≡
ｑ≡３（mod 4)の場合と、（２）ｐ≡３（mod3)，ｑ≡
１（mod 4)の場合と、（３）ｐ≡ｑ≡１（mod 4)の場合
とにより以下のように異なる手順をとる。

【００１４】 （１．２．１）復号化鍵表生成装置（１）の動作手順 １．入力はｐ，ｑとそれらの位数表である。この場合は
ｐ≡ｑ≡３（mod 4)であるから、前記（１．１）の２に
示す位数表が用いられる。 ２．ｇｃｄ（ｅ，ｐ＋１）＝ｇｃｄ（ｅ，ｑ＋１）＝１
となるｅをランダムに設定する。つまりすべての位数ｐ
＋１，ｑ＋１と互いに素な整数ｅを選ぶ。 ３．以下の式を満たすｄ_p0，ｄ_q0を計算する。つまりｐ
＋１，ｑ＋１をそれぞれ法としてｅの逆元を計算する。

【００１５】 ｅ・ｄ_p0≡１（mod p+1)， ｅ・ｄ_q0≡１（mod q+1) ４．この場合はｐ≡ｑ≡３（mod 4)の場合であるから、
前記位数表生成装置の動作手順の（１．１）の２に示す
ように識別子τ_p ＝τ_q ＝０であって、復号化鍵表は、 とする。 ５．暗号化鍵ｅ，ｎ（＝ｐ・ｑ）と復号化鍵表を出力
し、復号化鍵表生成装置（１）の動作を終了する。

【００１６】 （１．２．２）復号化鍵表生成装置（２）の動作手順 １．入力はｐ，ｑとそれらの位数表である。ｐ≡ｑ≡３
（mod 4)でないから、前記（１．１）の１０の位数表が
用いられる。 ２．ｇｃｄ（ｅ，Ｎ_p0）＝ｇｃｄ（ｅ，Ｎ_p1）＝ｇｃｄ
（ｅ，Ｎ_p2）＝ｇｃｄ（ｅ，Ｎ_p3）＝ｇｃｄ（ｅ，ｑ＋
１）＝１となるｅをランダムに設定する。つまりすべて
の位数と素な整数ｅを選ぶ。 ３．以下の式を満たすｄ_pi（ｉ＝０〜３），ｄ_q0を計算
する。

【００１７】ｅ・ｄ_pi≡１（mod Ｎ_pi）（ｉ＝０〜
３），ｅ・ｄ_qo≡１（mod q+1) ４．復号化鍵表は、 とする。 ５．暗号化鍵ｅ，ｎと復号化鍵表を出力し、復号化鍵表
生成装置（２）の動作を終了する。

【００１８】（１．２．３）復号化鍵表生成装置（３）
の動作手順 １．入力はｐ，ｑとそれらの位数表である。 ２．ｇｃｄ（ｅ，Ｎ_pi）＝ｇｃｄ（ｅ，Ｎ_qi）＝１（ｉ
＝０〜３）となるｅをランダムに設定する。 ３．以下の式を満たすｄ_pi，ｄ_qi（ｉ＝０〜３）を計算
する。

【００１９】ｅ・ｄ_pi≡１（mod Ｎ_pi），ｅ・ｄ_qi≡１
（mod Ｎ_qi）（ｉ＝０〜３） ４．復号化鍵表は、 とする。 ５．暗号化鍵ｅ，ｎと復号化鍵表を出力し、復号化鍵表
生成装置（３）の動作を終了する。

【００２０】（２）暗号化装置の動作手順 １．入力はｅ，ｎと平文の組Ｍ＝（ｍ_x ，ｍ_y ）であ
る。ただし、０＜ｍ_x ＜ｎ，０＜ｍ_y ＜ｎかつｇｃｄ
（ｍ_x ，ｎ）＝ｇｃｄ（ｍ_y ，ｎ）＝１とする。 ２．（ｍ_y ² −ｍ_x ³ ）／ｍ_x mod n を計算し、その計
算結果をａ_M とする。 ３．ｅ・Ｍ ｏｖｅｒ Ｅ_n （ａ_M ，０）を計算し、つ
まりＥ_n （ａ_M ，０）上でＭをｅ倍し、その計算結果を
Ｃとする。 ４．Ｃ＝（ｃ_x ，ｃ_y ）を暗号文の組として出力し、暗
号化装置の動作を終了する。

【００２１】（３）復号化装置の動作手順 １．入力は暗号文の組Ｃ＝（ｃ_x ，ｃ_y ）である。この
装置には、ｐ，ｑ，復号化鍵表が記憶されている。 ２．（ｃ_y ² −ｃ_x ³ ）／ｃ_x mod p と（ｃ_y ² −ｃ_x
³ ）／ｃ_x mod q を計算し、各々の計算結果をａ_p ，ａ
_q とする。 ３．もし、ｐ≡ｑ≡３（mod 4)ならば、識別子を、τ_p
＝０，τ_q ＝０として６．へ行く。 ４．もし、ｐ≡ｑ≡３（mod 4)でなく、かつｐ≡１（mo
d 4)，ｑ≡３（mod 4)ならば、ａ_p ^(p-1)/4mod pを計算
し、その計算結果に応じて識別子を決定し、つまり計算
結果が１ならτ_p0とし、τ_p1の値ならばτ_p1とし、−１
ならτ_p2とし、−τ_p1ならτ_p3とし、更にτ_q ＝０とし
て６．へ行く。 ５．ｐ≡１（mod 4)，ｑ≡３（mod 4)でもなければ、ａ
_p ^(p-1)/4 mod p とａ_q ^(q-1)/4 mod q を計算し、各々
の計算結果から識別子τ_p ，τ_q を決定する。 ６．このようにして決定された識別子τ_p ，τ_q と対応
する復号化鍵ｄ_p ，ｄ_qを復号化鍵表から検索する。 ７．検索した復号化鍵ｄ_p ，ｄ_q と暗号文の組Ｃとを用
いてｄ_p ・Ｃ ｏｖｅｒＥ_p （ａ_p ，０）とｄ_q ・Ｃ
ｏｖｅｒ Ｅ_q （ａ_q ，０）を計算し、各々の計算結果
をＭ_p ，Ｍ_q とする。 ８．中国剰余定理を用いてＭ_p ，Ｍ_q からＭを計算す
る。 ９．Ｍを平文の組として出力し、復号化装置の動作を終
了する。

【００２２】

【実施例】図１に請求項１の発明の実施例を示す。セン
タ１１に設けられた公開ファイル装置１２と、送信側１
３に設けられた暗号化装置１４と、受信側１５に設けら
れた復号化装置１６及び鍵生成装置１７とを主たる構成
としてシステムが構成される。公開ファイル装置１２に
は各復号化装置１６、つまり各受信側加入者Ａ，Ｂ，
Ｃ，…ごとに、個有の公開鍵（ｎ_A,ｅ_A ），（ｎ
_B,ｅ_B ），（ｎ_C,ｅ_C ），……が登録されている。

【００２３】公開鍵ｎ，ｅは、鍵生成装置１７で復号化
鍵表と共に生成される。つまり鍵生成装置１７は図２Ａ
に示すように素数生成器２１から５以上の任意の素数ｐ
及びｑが生成され、その素数ｐ，ｑはそれぞれ位数表生
成装置２２，２３に供給される。位数表生成装置２２で
は先に述べた（１_. １）位数表生成装置の動作手順に従
って各識別子０，τ_p0〜τ_p3に対する位数ｐ＋１，Ｎ_p0
〜Ｎ_p3を求めて位数表を生成する。同様に位数表生成装
置２３では同様の手順に従って各識別子０，τ _q0〜τ_q3
に対する位数ｑ＋１，Ｎ_q0〜Ｎ_q3を求めて位数表を生成
する。

【００２４】これら生成された両位数表と素数ｐ，ｑと
を復号化鍵表生成装置２４に入力して、公開鍵ｅを生成
すると共に復号化鍵表を生成し、また公開鍵ｎも生成す
る。即ち前記（１．２）復号化鍵表生成装置の動作手順
に従って、公開鍵ｅを生成し、これと各識別子０，τ_p0
〜τ_p3，τ_q0〜τ_q3とに応じた復号化鍵ｄ_p0，ｄ_q0，ｄ
_p0〜ｄ_p3，ｄ_q0〜ｄ_q3を求め、これらより識別子と復号
化鍵との対応を示す復号化鍵表を生成する。またｎ＝ｐ
・ｑを計算して公開鍵ｎを生成する。

【００２５】このようにして生成された公開鍵ｅ，ｎ
を、受信側１５（図１）の送信器２５によりセンタ１１
へ送信して公開ファイル装置１２に登録する。また生成
された素数ｐ，ｑと復号化鍵表とを秘密鍵として復号化
装置１６内の記憶部２６に記憶する。送信側１３におい
て平文の組Ｍを暗号化して送信する場合は、その送信相
手加入者の公開鍵ｎ，ｅを、送受信器２７を用いてセン
タ１１と通信することにより、受取り、暗号化装置１４
で平文の組Ｍを暗号化する。暗号化装置１４は図２Ｂに
示すように、前記（２）暗号化装置の動作手順に従っ
て、入力平文の組Ｍと公開鍵ｎとからａ_M 計算器２８に
より（ｍ_y ² −ｍ_x ³ ）／ｍ_x mod n ＝ａ_M を計算し、
このａ_M とＭと、ｅと、ｎとを楕円曲線乗算器２９に入
力して、Ｅ_n （ａ _M ，０）上でＭをｅ倍し、その結果を
暗号文の組Ｃとして出力する。暗号文の組Ｃを送信器３
１（図１）により受信側１５へ送信する。

【００２６】受信側１５で送信側１３より送信された暗
号文の組Ｃを受信器３２で受信し、復号化装置１６で復
号化する。復号化装置１６は図３に示す構成をしてお
り、前記（３）復号化装置の動作手順に従って動作す
る。即ち、暗号文の組Ｃと記憶部２６からのｐ，ｑとが
それぞれａ_p 計算器３３、ａ_q 計算器３４に入力され
て、（Ｃ_y ² −Ｃ_x ³ ）／Ｃ_x mod p ＝ａ_p ，（Ｃ_y ²
−Ｃ_x ³ ）／Ｃ_x mod q ＝ａ _p が計算される。これらａ
_p ，ａ_q とｐ，ｑとがそれぞれτ_p 計算器３５、τ_q計
算器３６に入力され、そのｐ，ｑに応じてτ_p ＝０，τ
_q ＝０とされ、あるいはａ_p ^(p-1)/4 mod p ＝τ_p ，ａ
_q ^(q-1)/4 mod q ＝τ_p が計算される。これら識別子τ
_p ，τ_q により復号化鍵表検索器３７で記憶部２６内の
復号化鍵表を検索して対応する復号化鍵ｄ_p ，ｄ_q を求
める。

【００２７】楕円曲線乗算器３８にＣ，ａ_p ，ｄ_p ，ｐ
を入力して、Ｅ_p （ａ_p ，０）上でＣをｄ_p 倍した値Ｍ
_p を計算し、楕円曲線乗算器３９にＣ，ａ_q ，ｄ_q ，ｑ
を入力して、Ｅ_q （ａ_q ，０）上でＣをｄ_q 倍した値Ｍ
_q を計算する。ｐ，ｑ，Ｍ_p，Ｍ_q を中国剰余定理計算
器４１に入力して、中国剰余定理を用いてＭを計算し、
その結果を平文の組Ｍとして出力する。

【００２８】

【発明の効果】以上述べたようにこの発明の暗号方式に
おいても素数ｐ，ｑの桁数をその積ｎ（＝ｐｑ）の素因
数分解の困難さを考慮して決め、この困難さに安全性を
求めているが、前記（１）鍵生成装置の動作手順で述べ
たように、ｐ≡３（mod 4)以外の素数、つまり、任意の
素数を利用できるため、素数ｐ，ｑの大きさを同じにし
た場合にＫＭＯＶ方式に比べてより安全である。なぜな
らば、法のｎの素因数ｐ，ｑに制限がないため、その素
因数分解がより難しくなっているからである。なお、こ
のようにパラメータの素数の制限をなくすため、この発
明では複数個の復号化鍵を用意して暗号文に応じて復号
化鍵を選択している。

【図面の簡単な説明】

【図１】 請求項１の発明による公開鍵暗号システムの
構成例を示すブロック図。

【図２】 請求項２の発明による鍵生成装置の構成例を
示すブロック図、Ｂは請求項３の発明による暗号化装置
の構成例を示すブロック図である。

【図３】 請求項４の発明の鍵生成装置の構成例を示す
ブロック図。

Claims (4)

【特許請求の範囲】
1. 【請求項１】 受信者ごとに、任意に選んだ素数ｐ，ｑ
   と対応した暗号化鍵ｅ，ｎが登録されている公開ファイ
   ル装置と、 上記各ｐ，ｑ，ｅの組ごとに、楕円曲線Ｅ_p （ａ_p ，
   ０）：ｙ² ≡ｘ³ ＋ａ_pｘ（mod p ）と楕円曲線Ｅ
   _q （ａ_q ，０）：ｙ² ≡ｘ³ ＋ａ_q ｘ（mod q ）のパラ
   メータａ_p ，ａ_q と復号化鍵とを関係付ける識別子と上
   記復号化鍵とを対応付ける復号化鍵表を生成し、その復
   号化鍵表及び対応ｐ，ｑを記憶する手段と、 上記公開ファイル装置から得た送信相手の公開鍵ｅ，ｎ
   を用いて、平文の組Ｍ＝（ｍ_x ，ｍ_y ）から楕円曲線Ｅ
   _n （ａ_M , ０) ：ｙ² ≡ｘ³ ＋ａ_M ｘ(mod n)のパラメ
   ータａ_M を計算し、Ｍの楕円曲線Ｅ_n （ａ_M ，０）上で
   ｅ倍した点Ｃを暗号文の組として送信する暗号化装置
   と、 暗号文の組Ｃから楕円曲線Ｅ_p （ａ_p ，０）：ｙ² ≡ｘ
   ³ ＋ａ_p ｘ（mod p)と、楕円曲線Ｅ_q （ａ_q ，０）：ｙ
   ² ≡ｘ³ ＋ａ_q ｘ（mod q)のパラメータａ_p ，ａ_q を計
   算し、これらａ_p ，ａ_q から識別子を求め、この識別子
   により上記復号化鍵表を参照して復号化鍵ｄ_p ，ｄ_q を
   求め、Ｃを楕円曲線Ｅ_p （ａ_p ，０）上でｄ_p 倍した点
   Ｍ_p と、Ｃを楕円曲線Ｅ_q （ａ_q ，０）上でｄ_q 倍した
   点Ｍ_q とを求め、これらＭ_p ，Ｍ_q から中国剰余定理を
   用いて平文の組Ｍを得る復号化装置と、 を備えた楕円曲線に基づく公開鍵暗号システム。
2. 【請求項２】 素数ｐに対して楕円曲線Ｅ_p （ａ，
   ０）：ｙ² ≡ｘ³ ＋ａｘ（mod p)の位数とパラメータａ
   との関係を示す識別子と上記位数との対応を示す位数表
   を生成する手段と、 素数ｐとｑとの積ｎを計算する手段と、 上記位数表中の全ての位数と互いに素な整数ｅを選ぶ手
   段と、 上記位数中の各位数を法としてｅの逆元をそれぞれ計算
   し、それら各計算結果を復号化鍵とする手段と、 上記復号化鍵と上記位数表の識別子との対応を示す復号
   化鍵表を生成する手段と、 を具備する鍵生成装置。
3. 【請求項３】 平文の組Ｍ＝（ｍ_x ，ｍ_y ）と公開鍵ｎ
   とから楕円曲線Ｅ_n（ａ_M ，０）：ｙ² ≡ｘ³ ＋ａ_M （m
   od n)のパラメータａ_M を計算する手段と、 上記平文の組Ｍと、公開鍵ｎ，ｅと上記パラメータａ_M
   とから楕円曲線Ｅ_n （ａ_M ，０）上でＭをｅ倍してその
   結果Ｃを暗号文の組とする手段と、 を具備する暗号化装置。
4. 【請求項４】 暗号文の組Ｃと素数ｐから楕円曲線Ｅ_p
   （ａ_p ，０）：ｙ²≡ｘ³ ＋ａ_p ｘ（mod p)のパラメー
   タａ_p を計算する手段と、 上記暗号文の組Ｃと素数ｑから楕円曲線Ｅ_q （ａ_q ，
   ０）：ｙ² ≡ｘ³ ＋ａ_qｘ（mod q)のパラメータａ_q を
   計算する手段と、 上記ａ_p とパラメータｐから識別子τ_p を計算する手段
   と、 上記パラメータａ_q とｑから識別子τ_q を計算する手段
   と、 上記識別子τ_p ，τ_q に対する各復号化鍵ｄ_p ，ｄ_q を
   復号化鍵表から検索する手段と、 上記Ｃを楕円曲線Ｅ_p （ａ_p ，０）上でｄ_p 倍してＭ_p
   を得る手段と、 上記Ｃを楕円曲線Ｅ_q （ａ_q ，０）上でｄ_q 倍してＭ_q
   を得る手段と、 上記Ｍ_p ，Ｍ_q ，ｐ，ｑから中国剰余定理を用いて平文
   Ｍを得る手段と、 を具備する復号化装置。