JPH0798563A - 楕円曲線による署名、認証及び秘密通信方式 - Google Patents
楕円曲線による署名、認証及び秘密通信方式Info
- Publication number
- JPH0798563A JPH0798563A JP6134339A JP13433994A JPH0798563A JP H0798563 A JPH0798563 A JP H0798563A JP 6134339 A JP6134339 A JP 6134339A JP 13433994 A JP13433994 A JP 13433994A JP H0798563 A JPH0798563 A JP H0798563A
- Authority
- JP
- Japan
- Prior art keywords
- elliptic curve
- user
- communication
- prime
- secret
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Granted
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F7/00—Methods or arrangements for processing data by operating upon the order or content of the data handled
- G06F7/60—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers
- G06F7/72—Methods or arrangements for performing computations using a digital non-denominational number representation, i.e. number representation without radix; Computing devices using combinations of denominational and non-denominational quantity representations, e.g. using difunction pulse trains, STEELE computers, phase computers using residue arithmetic
- G06F7/724—Finite field arithmetic
- G06F7/725—Finite field arithmetic over elliptic curves
Landscapes
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Engineering & Computer Science (AREA)
- Computational Mathematics (AREA)
- Mathematical Analysis (AREA)
- Mathematical Optimization (AREA)
- Pure & Applied Mathematics (AREA)
- Theoretical Computer Science (AREA)
- Computing Systems (AREA)
- Mathematical Physics (AREA)
- General Engineering & Computer Science (AREA)
Abstract
(57)【要約】
【目的】 楕円曲線を使用した安全、確実な署名、認証
及び秘密通信方式を提供する。 【構成】 楕円曲線は以下のものとする。 （１）楕円曲線の定義体である有限体ＧＦ（ｐ）を、正
整数ｄが虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さくな
るようにとり、２t −αと表される（ここに、αは小さ
い数）素数ｐをｐ＋１−ａ若しくはｐ＋１＋ａが大きな
素数で割れ、更に上記整数ａに対して、４ｐ−ａ2 ＝ｄ
・ｂ2 と表されるようにとる。この有限体ＧＦ（ｐ）
上、類多項式Ｈd （ｘ）＝０の根をｊ不変数にもつ楕円
曲線及び元を用いる。 （２）有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線
Ｅ1 ，Ｅ2 ，…，Ｅn を、互いに同型ではないが元の個
数が等しくなるように構成し、使用する楕円曲線を適宜
変更する。
及び秘密通信方式を提供する。 【構成】 楕円曲線は以下のものとする。 （１）楕円曲線の定義体である有限体ＧＦ（ｐ）を、正
整数ｄが虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さくな
るようにとり、２t −αと表される（ここに、αは小さ
い数）素数ｐをｐ＋１−ａ若しくはｐ＋１＋ａが大きな
素数で割れ、更に上記整数ａに対して、４ｐ−ａ2 ＝ｄ
・ｂ2 と表されるようにとる。この有限体ＧＦ（ｐ）
上、類多項式Ｈd （ｘ）＝０の根をｊ不変数にもつ楕円
曲線及び元を用いる。 （２）有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線
Ｅ1 ，Ｅ2 ，…，Ｅn を、互いに同型ではないが元の個
数が等しくなるように構成し、使用する楕円曲線を適宜
変更する。
Description
【０００１】
【産業上の利用分野】本発明は情報セキュリテイ技術と
しての暗号技術に関し、特に、楕円曲線を用いた暗号技
術に関する。
しての暗号技術に関し、特に、楕円曲線を用いた暗号技
術に関する。
【０００２】
【従来の技術】近年、一般に公開されたディジタル通信
回線網を使用して相互に通信を行ったり、有料で放送番
組を提供したりすることがさかんになってきている。と
ころで、一般に公開された通信回線網を使用する場合、
第三者による盗聴や詐称、あるいは送信者による送信先
の間違いを完全に防止することは困難である。このた
め、秘密通信方式並びに署名及び認証方式と呼ばれる通
信方式が重要なものとなっている。ここに、秘密通信方
式とは、特定の通信相手以外に通信内容を漏らすことな
く通信を行う方式である。また署名及び認証通信方式と
は、通信相手に通信内容の正当性を示したり、本人であ
ることを証明する通信方式である。この署名、認証及び
秘密通信方式には公開鍵暗号とよばれる通信方式があ
る。公開鍵暗号は通信相手が多数のとき、通信相手ごと
に異なる暗号鍵を容易に管理するための方式であり、多
数の通信相手と通信を行うのに不可欠な基盤技術であ
る。以下、これについて、歴史的な経緯もふまえて本発
明に関係する原理と手順とを簡単に説明する。なお、こ
の秘密通信方式等の一般技術については、池野信一，小
山謙二著「現代暗号理論」 電子通信学会発行 １９８
６年に詳しい。 （１）有限体上の離散対数問題を使用した秘密通信方
式。 （原理）ｐを素数、ｇをその一の原始根、ｕを任意の自
然数、αをｇのｕ乗のｐを法とする剰余とする。すなわ
ち、ｇu ≡α（ｍｏｄ ｐ）とする。この場合、ｇとｐ
とｕを与えられたときにαを求めるのは容易である。し
かし、ｐが１４０桁程度の素数となると、大型計算機の
発達した今日でも、ｇとｐとαからｕを求めるのは困難
である。これは丁度、２つの素数ｒとｓがあるときｒと
ｓからその積を求めるのは容易であるが、ｒとｓが各１
４０桁程度となれば、積は２８０桁となるため、これか
ら素因数分解によりｒとｓを求めるのは困難なことに似
る。
回線網を使用して相互に通信を行ったり、有料で放送番
組を提供したりすることがさかんになってきている。と
ころで、一般に公開された通信回線網を使用する場合、
第三者による盗聴や詐称、あるいは送信者による送信先
の間違いを完全に防止することは困難である。このた
め、秘密通信方式並びに署名及び認証方式と呼ばれる通
信方式が重要なものとなっている。ここに、秘密通信方
式とは、特定の通信相手以外に通信内容を漏らすことな
く通信を行う方式である。また署名及び認証通信方式と
は、通信相手に通信内容の正当性を示したり、本人であ
ることを証明する通信方式である。この署名、認証及び
秘密通信方式には公開鍵暗号とよばれる通信方式があ
る。公開鍵暗号は通信相手が多数のとき、通信相手ごと
に異なる暗号鍵を容易に管理するための方式であり、多
数の通信相手と通信を行うのに不可欠な基盤技術であ
る。以下、これについて、歴史的な経緯もふまえて本発
明に関係する原理と手順とを簡単に説明する。なお、こ
の秘密通信方式等の一般技術については、池野信一，小
山謙二著「現代暗号理論」 電子通信学会発行 １９８
６年に詳しい。 （１）有限体上の離散対数問題を使用した秘密通信方
式。 （原理）ｐを素数、ｇをその一の原始根、ｕを任意の自
然数、αをｇのｕ乗のｐを法とする剰余とする。すなわ
ち、ｇu ≡α（ｍｏｄ ｐ）とする。この場合、ｇとｐ
とｕを与えられたときにαを求めるのは容易である。し
かし、ｐが１４０桁程度の素数となると、大型計算機の
発達した今日でも、ｇとｐとαからｕを求めるのは困難
である。これは丁度、２つの素数ｒとｓがあるときｒと
ｓからその積を求めるのは容易であるが、ｒとｓが各１
４０桁程度となれば、積は２８０桁となるため、これか
ら素因数分解によりｒとｓを求めるのは困難なことに似
る。
【０００３】次に、ｖを他の任意の自然数とし、βをｇ
のｖ乗のｐを法とする剰余とする。すなわち、ｇv ≡β
（ｍｏｄ ｐ）とする。この場合、αのｖ乗のｐを法と
する剰余とβのｕ乗のｐを法とする剰余とは等しい。す
なわち、αv ≡（ｇu ）v ≡（ｇv ）u ≡βu （ｍｏｄ
ｐ）である。 （手順）以下、図２を参照しつつ、この原理を利用した
有限体上の離散対数問題（整数論では法と剰余と原始根
から指数を求めることの困難性であるが、通信分野では
通常このように言われる。）を使用した秘密通信方式の
手順の一例として、共有鍵暗号方式といわれているもの
を示す。
のｖ乗のｐを法とする剰余とする。すなわち、ｇv ≡β
（ｍｏｄ ｐ）とする。この場合、αのｖ乗のｐを法と
する剰余とβのｕ乗のｐを法とする剰余とは等しい。す
なわち、αv ≡（ｇu ）v ≡（ｇv ）u ≡βu （ｍｏｄ
ｐ）である。 （手順）以下、図２を参照しつつ、この原理を利用した
有限体上の離散対数問題（整数論では法と剰余と原始根
から指数を求めることの困難性であるが、通信分野では
通常このように言われる。）を使用した秘密通信方式の
手順の一例として、共有鍵暗号方式といわれているもの
を示す。
【０００４】通信網の提供者により、ｐとｇが与えら
れ、各ユーザに通知される。ユーザＵは、任意の自然数
ｕを選択し、ｇu ≡α（ｍｏｄ ｐ）の演算によりαを
計算する。ユーザＶは、同じくｖを選択し、ｇv ≡β
（ｍｏｄ ｐ）の演算によりβを計算する。
れ、各ユーザに通知される。ユーザＵは、任意の自然数
ｕを選択し、ｇu ≡α（ｍｏｄ ｐ）の演算によりαを
計算する。ユーザＶは、同じくｖを選択し、ｇv ≡β
（ｍｏｄ ｐ）の演算によりβを計算する。
【０００５】ユーザＵは、ｕは秘密に保持した上でαを
公開通信網を使用してユーザＢに通知し、一方ユーザＶ
はｖを秘密に保持した上でβを公開通信網を使用してユ
ーザＵに通知する。両者は、ｇuvのｐを法とする剰余ｋ
uvを計算し、これを両者の共有鍵とし、また第三者には
秘密にしておく。
公開通信網を使用してユーザＢに通知し、一方ユーザＶ
はｖを秘密に保持した上でβを公開通信網を使用してユ
ーザＵに通知する。両者は、ｇuvのｐを法とする剰余ｋ
uvを計算し、これを両者の共有鍵とし、また第三者には
秘密にしておく。
【０００６】ここに ｋuv≡ｇuv（ｍｏｄ ｐ）であ
る。以上の手順を、理解の便宜のため小さな素数を例に
とって具体的に示す。ｐ＝１１、ｇ＝２とする。今、ユ
ーザＵがｕとして４をとったとする。この場合、ｇu ＝
２4 ＝１６であり、１６の１１を法とする剰余は５であ
るため、α＝５となる。同じく、ユーザＶがｖとして８
をとったとする。この場合、ｇv ＝２ 8 ＝２５６であ
り、２５６の１１を法とする剰余は３であるため、β＝
３となる。更に、αv ＝５8 、βu ＝３4 とも１１を法
とする剰余は４（ｍｏｄ １１）であるため、ｋuv＝４
となる。
る。以上の手順を、理解の便宜のため小さな素数を例に
とって具体的に示す。ｐ＝１１、ｇ＝２とする。今、ユ
ーザＵがｕとして４をとったとする。この場合、ｇu ＝
２4 ＝１６であり、１６の１１を法とする剰余は５であ
るため、α＝５となる。同じく、ユーザＶがｖとして８
をとったとする。この場合、ｇv ＝２ 8 ＝２５６であ
り、２５６の１１を法とする剰余は３であるため、β＝
３となる。更に、αv ＝５8 、βu ＝３4 とも１１を法
とする剰余は４（ｍｏｄ １１）であるため、ｋuv＝４
となる。
【０００７】ユーザＵが通信文をユーザＶに送信する場
合、ビット情報たる通信文をある定まった個数毎に区切
った上で、各区切れたビット情報毎にｋuvと演算を行っ
て秘密化する。送信文を（０１０）とする。ｋuv＝４、
これは２進数で（１００）となる。このため、今演算を
排他的論理和とするならば、秘密化された送信文は
｛（０１０）ＸＯＲ（１００）＝｝（１１０）となる。
合、ビット情報たる通信文をある定まった個数毎に区切
った上で、各区切れたビット情報毎にｋuvと演算を行っ
て秘密化する。送信文を（０１０）とする。ｋuv＝４、
これは２進数で（１００）となる。このため、今演算を
排他的論理和とするならば、秘密化された送信文は
｛（０１０）ＸＯＲ（１００）＝｝（１１０）となる。
【０００８】この上で、ユーザＶに送信する。一方、こ
れを受信したユーザＶは、ｋuvを使用して復号すること
により本来の通信文を入手する。もし、受信した暗号文
が（１１０）ならば、復号後の通信文は｛（１１０）Ｘ
ＯＲ（１００）＝｝（０１０）となる。
れを受信したユーザＶは、ｋuvを使用して復号すること
により本来の通信文を入手する。もし、受信した暗号文
が（１１０）ならば、復号後の通信文は｛（１１０）Ｘ
ＯＲ（１００）＝｝（０１０）となる。
【０００９】勿論、上記演算はこの他、２進数とみなし
ての加算や引算、各対応するビットごとの他の論理演算
等としてもよい。本方式は、たとえ第三者がユーザＵと
ユーザＶが公開通信網を使用してαとβを相互に知らせ
あう際に、これらを盗聴等により知得しえても、ｕ若し
くはｖを知らない限りｋuvを知ることは困難であること
を秘密性の根拠としている。
ての加算や引算、各対応するビットごとの他の論理演算
等としてもよい。本方式は、たとえ第三者がユーザＵと
ユーザＶが公開通信網を使用してαとβを相互に知らせ
あう際に、これらを盗聴等により知得しえても、ｕ若し
くはｖを知らない限りｋuvを知ることは困難であること
を秘密性の根拠としている。
【００１０】また、上記通信方法においては、受信した
ユーザＶは、Ｋuvを知っているのはユーザＵのみである
ため、復号した受信文が意味のある内容であるならば、
確かにユーザＵから送られてきたものであるという確認
も得られることとなる。また、ユーザＷ，Ｘ等は各任意
の自然数ｗ，ｘ，…を選定し、例えばユーザＵとユーザ
Ｗとはｇu ・ w のｐを法とする剰余を共有鍵として使用
する等多数のユーザに柔軟に対処しえるという利点があ
る。
ユーザＶは、Ｋuvを知っているのはユーザＵのみである
ため、復号した受信文が意味のある内容であるならば、
確かにユーザＵから送られてきたものであるという確認
も得られることとなる。また、ユーザＷ，Ｘ等は各任意
の自然数ｗ，ｘ，…を選定し、例えばユーザＵとユーザ
Ｗとはｇu ・ w のｐを法とする剰余を共有鍵として使用
する等多数のユーザに柔軟に対処しえるという利点があ
る。
【００１１】更に、各ユーザＵ，Ｖ，Ｗ，…は、秘密に
保持する自然数ｕ，ｖ，ｗ，…等を定期的に他の自然数
ｕ’，ｖ’，ｗ’，…等に変更したり、特定のユーザＵ
が通信相手によって更に他の自然数ｕ1 ，ｕ2 ，…等を
使いわけたりもしえる。このため、企業等の組織体で使
用する場合には、組織変更に柔軟に対応しえる。なお、
実際の暗号通信に際しては、素数ｐのかわりに複数の充
分大きな素数ｐ，ｑ，ｒ，…の積やｐの２乗や３乗を使
用したり、また原始根ｇに換えて充分に位数の大きな自
然数が使用されたりすることもある。
保持する自然数ｕ，ｖ，ｗ，…等を定期的に他の自然数
ｕ’，ｖ’，ｗ’，…等に変更したり、特定のユーザＵ
が通信相手によって更に他の自然数ｕ1 ，ｕ2 ，…等を
使いわけたりもしえる。このため、企業等の組織体で使
用する場合には、組織変更に柔軟に対応しえる。なお、
実際の暗号通信に際しては、素数ｐのかわりに複数の充
分大きな素数ｐ，ｑ，ｒ，…の積やｐの２乗や３乗を使
用したり、また原始根ｇに換えて充分に位数の大きな自
然数が使用されたりすることもある。
【００１２】しかしながら、近年の大型計算機の発達を
背景にして、数学の理論（類体論の高次相互律、分解法
則等）は、ｇとｐとαとから比較的少ない計算量でｕを
求める方法を種々開発しつつある。その対策の一として
は、素数ｐを１４０桁程度のものでなく２００桁等充分
に大きいものとすることがあげられる。ただし、この場
合には、桁数が大きいだけに各種の必要な計算の絶対量
が多くなる等の不都合が生じえる。
背景にして、数学の理論（類体論の高次相互律、分解法
則等）は、ｇとｐとαとから比較的少ない計算量でｕを
求める方法を種々開発しつつある。その対策の一として
は、素数ｐを１４０桁程度のものでなく２００桁等充分
に大きいものとすることがあげられる。ただし、この場
合には、桁数が大きいだけに各種の必要な計算の絶対量
が多くなる等の不都合が生じえる。
【００１３】これらのため、楕円曲線を使用した秘密通
信方式が開発された。以下これについて説明する。 （２）楕円曲線上の離散対数問題を使用した秘密通信方
式。 以下、楕円曲線上の離散対数問題について説明する。な
お、これはニール コブリッツ著「整数論と暗号表記法
の解説（意訳）」スプリンガー書店 １９８７年，（Ne
al koblitz , " A Course in Number Theory and Crypt
ography ",Springer-Verlag,1987）に詳しく述べられて
いる。また、楕円曲線の理論そのものは、日本語文献で
は、志村五郎，谷山豊著「近代的整数論」 共立出版
１９５７年をあげられる。 （楕円曲線そのものとその上での演算）楕円曲線とは、
１次元アーベル（Ａｂｅｌ）多様体、あるいは既約で非
特異な種数１の射影代線曲線をいい、例えばＹ2 ＝Ｘ3
＋ａＸ＋ｂ等の形で表される。
信方式が開発された。以下これについて説明する。 （２）楕円曲線上の離散対数問題を使用した秘密通信方
式。 以下、楕円曲線上の離散対数問題について説明する。な
お、これはニール コブリッツ著「整数論と暗号表記法
の解説（意訳）」スプリンガー書店 １９８７年，（Ne
al koblitz , " A Course in Number Theory and Crypt
ography ",Springer-Verlag,1987）に詳しく述べられて
いる。また、楕円曲線の理論そのものは、日本語文献で
は、志村五郎，谷山豊著「近代的整数論」 共立出版
１９５７年をあげられる。 （楕円曲線そのものとその上での演算）楕円曲線とは、
１次元アーベル（Ａｂｅｌ）多様体、あるいは既約で非
特異な種数１の射影代線曲線をいい、例えばＹ2 ＝Ｘ3
＋ａＸ＋ｂ等の形で表される。
【００１４】さて、楕円曲線上の２点をＢＰ1 ，ＢＰ2
としたとき、演算ＢＰ1 ＋ＢＰ2 は、以下のようにして
定義される。ＢＰ1 とＢＰ2 を結ぶ直線がこの楕円曲線
と交わる第三の点ＢＰ3 のＸ軸に対して線対称な点をＢ
Ｐ3 ’とする。このＢＰ3 ’がＢＰ1 ＋ＢＰ2 である。
図３にこの演算の内容を示す。なお、ＢＰ1 ＝ＢＰ2 で
あるならば、ＢＰ1 とＢＰ2を結ぶ直線とは、ＢＰ1 に
おける接線をいう。
としたとき、演算ＢＰ1 ＋ＢＰ2 は、以下のようにして
定義される。ＢＰ1 とＢＰ2 を結ぶ直線がこの楕円曲線
と交わる第三の点ＢＰ3 のＸ軸に対して線対称な点をＢ
Ｐ3 ’とする。このＢＰ3 ’がＢＰ1 ＋ＢＰ2 である。
図３にこの演算の内容を示す。なお、ＢＰ1 ＝ＢＰ2 で
あるならば、ＢＰ1 とＢＰ2を結ぶ直線とは、ＢＰ1 に
おける接線をいう。
【００１５】ところで、この楕円曲線をＥとしたとき、
暗号化に使用されるのはＥ｛ＧＦ（ｑ）｝である。ここ
に、ｑは素数べきであり、ＧＦ（ｑ）は有限体(Galois
Field)とし、楕円曲線ＥのＧＦ（ｑ）上の元で生成され
る群がＥ｛ＧＦ（ｑ）｝である。このＥ｛ＧＦ（ｑ）｝
の簡単な例としては、Ｅがｙ2 ＝ｘ3 ＋３ｘ＋２という
楕円曲線であり、ｑ＝５の場合に、その元として（１，
１）、（１，−１）、（２，１）、（２，−１）及び無
限遠点という５つの元からなる集合を挙げられる。 （原理）次にＥ｛ＧＦ（ｑ）｝の性質、すなわち秘密通
信の根拠の原理について説明する。
暗号化に使用されるのはＥ｛ＧＦ（ｑ）｝である。ここ
に、ｑは素数べきであり、ＧＦ（ｑ）は有限体(Galois
Field)とし、楕円曲線ＥのＧＦ（ｑ）上の元で生成され
る群がＥ｛ＧＦ（ｑ）｝である。このＥ｛ＧＦ（ｑ）｝
の簡単な例としては、Ｅがｙ2 ＝ｘ3 ＋３ｘ＋２という
楕円曲線であり、ｑ＝５の場合に、その元として（１，
１）、（１，−１）、（２，１）、（２，−１）及び無
限遠点という５つの元からなる集合を挙げられる。 （原理）次にＥ｛ＧＦ（ｑ）｝の性質、すなわち秘密通
信の根拠の原理について説明する。
【００１６】Ｅ｛ＧＦ（ｑ）｝の位数が大きな素数で割
れる元ＢＰをベースポイント、ｄは任意の自然数とす
る。このとき、ＢＰとｄとからｄ・ＢＰを計算する（Ｂ
Ｐをｄ回加える）のは容易である。しかし、Ｅ｛ＧＦ
（ｑ）｝の与えられた元ＱとＢＰに対して、 Ｑ＝ｄ・ＢＰ となる自然数ｄが存在するならばｄを求めよという問題
は、計算機の発達した今日でもＢＰやｑ等が３０桁程度
の自然数となるならば困難である。なお、ここにＢＰ
は、ｐを法とする有限体ＧＦ（ｐ）上でのｇに相当する
役を担うものである。 （手順）前記有限体上の場合と基本的には異ならない。
れる元ＢＰをベースポイント、ｄは任意の自然数とす
る。このとき、ＢＰとｄとからｄ・ＢＰを計算する（Ｂ
Ｐをｄ回加える）のは容易である。しかし、Ｅ｛ＧＦ
（ｑ）｝の与えられた元ＱとＢＰに対して、 Ｑ＝ｄ・ＢＰ となる自然数ｄが存在するならばｄを求めよという問題
は、計算機の発達した今日でもＢＰやｑ等が３０桁程度
の自然数となるならば困難である。なお、ここにＢＰ
は、ｐを法とする有限体ＧＦ（ｐ）上でのｇに相当する
役を担うものである。 （手順）前記有限体上の場合と基本的には異ならない。
【００１７】すなわち、前記ｐに相当するのがＥ｛ＧＦ
（ｑ）｝であり、ｇに相当するのがＢＰであり、ｕやｖ
に相当するのがｄであり、またｐを法とするｇのｕ乗の
剰余を求める等のＧＦ（ｐ）での演算がＥ｛ＧＦ
（ｑ）｝での演算となる。ただし、楕円曲線上の点は、
ｘ軸とｙ軸の二次元座標で与えられ、この一方、通信文
は一次元である。このため、二次元座標値のうち、あら
かじめのユーザ同志の取極めでｘ座標値とｙ座標値のい
ずれか一方のみ使用するものとし、通信毎に任意に選択
したいずれか一方のみ使用し併せて別途いずれを使用し
たかを判別可能とするためのデータを送る等の手順が加
わる点が異なる。 （３）現時点における楕円曲線を使用した秘密通信方式
の発展の方向。
（ｑ）｝であり、ｇに相当するのがＢＰであり、ｕやｖ
に相当するのがｄであり、またｐを法とするｇのｕ乗の
剰余を求める等のＧＦ（ｐ）での演算がＥ｛ＧＦ
（ｑ）｝での演算となる。ただし、楕円曲線上の点は、
ｘ軸とｙ軸の二次元座標で与えられ、この一方、通信文
は一次元である。このため、二次元座標値のうち、あら
かじめのユーザ同志の取極めでｘ座標値とｙ座標値のい
ずれか一方のみ使用するものとし、通信毎に任意に選択
したいずれか一方のみ使用し併せて別途いずれを使用し
たかを判別可能とするためのデータを送る等の手順が加
わる点が異なる。 （３）現時点における楕円曲線を使用した秘密通信方式
の発展の方向。
【００１８】ところで、この楕円曲線上の離散対数問題
も、１９９１年に楕円曲線上の離散対数問題を有限体上
の離散対数問題に帰着させて比較的容易に解く解法が考
案された。ただし、これをのぞくとｐの桁数に比較し
て、その対数程度の計算で解きえるサブイクスポーネン
シャルといわれている解法は存在しない。サブイクスポ
ーネンシャルな解法を用いると１００ビット程度の大き
さの定義体上での通常の楕円曲線の離散対数問題は比較
的容易に解法される。１９９１年に考案されたこの解法
はＭＯＶ帰着法と呼ばれ、ア・メネゼス，エス・ヴァン
ストン，ティー・岡本著「楕円曲線における離散対数問
題を有限体における離散対数問題に帰着させる方法（意
訳）」STOC １９９１年，（A.Menezes,S.Vanstone and
T. Okamoto,"Reducing Elliptic Curve Logarithm to
Logarithms in a Finite Field",STOC 91）に詳しく述
べられている。ＭＯＶ帰着法では、ｑを素数べきとし、
有限体ＧＦ（ｑ）上定義された楕円曲線をＥとし、Ｅの
ＧＦ（ｑ）上の元で構成される群をＥ｛ＧＦ（ｑ）｝と
する。このときＥ（ＧＦ（ｑ））∋ＢＰをベースとする
楕円曲線上の離散対数問題は、ＢＰの位数とｑが互いに
素なときには、有限体ＧＦ（ｑ）のある拡大体ＧＦ（ｑ
r ）上の離散対数問題に帰着させて解くものである。特
にＥがスーパーシンギュラと呼ばれる楕円曲線の場合に
は、有限体ＧＦ（ｑ）の高々６次拡大体ＧＦ（ｑ6 ）上
の離散対数問題に帰着して解くことができる。
も、１９９１年に楕円曲線上の離散対数問題を有限体上
の離散対数問題に帰着させて比較的容易に解く解法が考
案された。ただし、これをのぞくとｐの桁数に比較し
て、その対数程度の計算で解きえるサブイクスポーネン
シャルといわれている解法は存在しない。サブイクスポ
ーネンシャルな解法を用いると１００ビット程度の大き
さの定義体上での通常の楕円曲線の離散対数問題は比較
的容易に解法される。１９９１年に考案されたこの解法
はＭＯＶ帰着法と呼ばれ、ア・メネゼス，エス・ヴァン
ストン，ティー・岡本著「楕円曲線における離散対数問
題を有限体における離散対数問題に帰着させる方法（意
訳）」STOC １９９１年，（A.Menezes,S.Vanstone and
T. Okamoto,"Reducing Elliptic Curve Logarithm to
Logarithms in a Finite Field",STOC 91）に詳しく述
べられている。ＭＯＶ帰着法では、ｑを素数べきとし、
有限体ＧＦ（ｑ）上定義された楕円曲線をＥとし、Ｅの
ＧＦ（ｑ）上の元で構成される群をＥ｛ＧＦ（ｑ）｝と
する。このときＥ（ＧＦ（ｑ））∋ＢＰをベースとする
楕円曲線上の離散対数問題は、ＢＰの位数とｑが互いに
素なときには、有限体ＧＦ（ｑ）のある拡大体ＧＦ（ｑ
r ）上の離散対数問題に帰着させて解くものである。特
にＥがスーパーシンギュラと呼ばれる楕円曲線の場合に
は、有限体ＧＦ（ｑ）の高々６次拡大体ＧＦ（ｑ6 ）上
の離散対数問題に帰着して解くことができる。
【００１９】そこで、上記ＭＯＶ帰着法による解法を避
けるように楕円曲線を構成する研究が行われるようにな
った。この方法は種々あるが、例えば、ティー・ベス，
エス・シャッファー「公開鍵暗号システムにおける非ス
ーパーシンギュラーな楕円曲線（意訳）」エウロクリプ
ト９１，１９９１年（T.Beth,F.Schaefer "Non Supers
ingular Elliptic Curves for Public Key Cryptosyste
ms",Eurocrypt 91,1991 ）或いは宮地充子著「普通の楕
円曲線上の暗号システム（意訳）」アジアクリプトの要
約９１，１９９１年（"On ordinary elliptic curve cr
yptosystems",Asiacrypt'91,1991 ）等に詳しく解説さ
れている。これらの方法を用いて構成すると、現時点で
はサブイクスポーネンシャルなアルゴリズム（ある目的
達成のための論理演算等の規則）を与える解法がないた
め、有限体上の離散対数問題と同程度の安全性ならばは
るかに小さな定義体で構成することができる。
けるように楕円曲線を構成する研究が行われるようにな
った。この方法は種々あるが、例えば、ティー・ベス，
エス・シャッファー「公開鍵暗号システムにおける非ス
ーパーシンギュラーな楕円曲線（意訳）」エウロクリプ
ト９１，１９９１年（T.Beth,F.Schaefer "Non Supers
ingular Elliptic Curves for Public Key Cryptosyste
ms",Eurocrypt 91,1991 ）或いは宮地充子著「普通の楕
円曲線上の暗号システム（意訳）」アジアクリプトの要
約９１，１９９１年（"On ordinary elliptic curve cr
yptosystems",Asiacrypt'91,1991 ）等に詳しく解説さ
れている。これらの方法を用いて構成すると、現時点で
はサブイクスポーネンシャルなアルゴリズム（ある目的
達成のための論理演算等の規則）を与える解法がないた
め、有限体上の離散対数問題と同程度の安全性ならばは
るかに小さな定義体で構成することができる。
【００２０】ところが楕円曲線の場合、楕円曲線上の一
加算に１２、３回の乗算を要求する。すなわち、楕円曲
線上のＢＰ1 （ｘ1,y1）、ＢＰ2 （ｘ2,y2）とした場合
一般には、 ＢＰ1 ＋ＢＰ2 ＝｛ｆ1 （x1, y1, x2, y2），ｆ2 （x
1, y , x2, y2）｝， もしもＢＰ1 ＝ＢＰ2 ならば、 ２ＢＰ1 ＝｛ｇ1(x1,y1), g2(x ,y ) ｝ と表わされるが、このときｆ1,f2,g1,g2はＧＦ（ｐ）上
の１２．３回の演算のみの関数となる。このため、定義
体の大きさが小さくなってもあまり処理速度が速くなら
ない。そこでＭＯＶ帰着法を避けることと共に、さらに
処理速度を速くするための研究が行われるようになっ
た。以下、後者の研究について説明する。 （４）楕円曲線を用いた暗号の処理速度を速くする従来
の技術。
加算に１２、３回の乗算を要求する。すなわち、楕円曲
線上のＢＰ1 （ｘ1,y1）、ＢＰ2 （ｘ2,y2）とした場合
一般には、 ＢＰ1 ＋ＢＰ2 ＝｛ｆ1 （x1, y1, x2, y2），ｆ2 （x
1, y , x2, y2）｝， もしもＢＰ1 ＝ＢＰ2 ならば、 ２ＢＰ1 ＝｛ｇ1(x1,y1), g2(x ,y ) ｝ と表わされるが、このときｆ1,f2,g1,g2はＧＦ（ｐ）上
の１２．３回の演算のみの関数となる。このため、定義
体の大きさが小さくなってもあまり処理速度が速くなら
ない。そこでＭＯＶ帰着法を避けることと共に、さらに
処理速度を速くするための研究が行われるようになっ
た。以下、後者の研究について説明する。 （４）楕円曲線を用いた暗号の処理速度を速くする従来
の技術。
【００２１】その一は、エヌ・コブリッツ著「秘密性の
良好なＣＭ−曲線（意訳）」Crypto'91,１９９１年（N.
Koblitz, "CM-curves with good cryptographic prope
rties", Crypto'91, 1991 ）に詳しく解説されている。
図４は、従来例における署名、認証及び秘密通信方式の
処理速度を高速にする楕円曲線の構成の手順の概略を示
すものである。
良好なＣＭ−曲線（意訳）」Crypto'91,１９９１年（N.
Koblitz, "CM-curves with good cryptographic prope
rties", Crypto'91, 1991 ）に詳しく解説されている。
図４は、従来例における署名、認証及び秘密通信方式の
処理速度を高速にする楕円曲線の構成の手順の概略を示
すものである。
【００２２】以下、同図を参照しながら従来例の手順を
説明する。 （Ｓ１）楕円曲線の候補の決定 次の二つのＧＦ（２）を定義体にもつアノマラス（anom
alous ）楕円曲線を考える。 E1：y2＋xy＝x3＋x2＋１ E2：y2＋xy＝x3＋１ 楕円曲線ＥのＧＦ（２m ）上の元で構成される群Ｅ｛Ｇ
Ｆ（２m ｝とは次のような群である。
説明する。 （Ｓ１）楕円曲線の候補の決定 次の二つのＧＦ（２）を定義体にもつアノマラス（anom
alous ）楕円曲線を考える。 E1：y2＋xy＝x3＋x2＋１ E2：y2＋xy＝x3＋１ 楕円曲線ＥのＧＦ（２m ）上の元で構成される群Ｅ｛Ｇ
Ｆ（２m ｝とは次のような群である。
【００２３】E1｛GF( 2 m ) ｝＝｛x,y ∈GF(2m ) ｜y2
＋xy＝x3＋x2＋１｝∪｛∞｝ E2｛GF( 2 m ) ｝＝｛x,y ∈GF(2m ) ｜y2＋xy＝x3＋
１｝∪｛∞｝ ここで∞は無限遠点を表わす。 （Ｓ２）適当な拡大次数ｍの決定 既述のごとく、公開鍵暗号の安全性の根拠となる上述の
楕円曲線の離散対数問題は、ベースポイントである元Ｂ
Ｐの位数が大きな素因数を持たなければ簡単に解けるこ
とが知られている。
＋xy＝x3＋x2＋１｝∪｛∞｝ E2｛GF( 2 m ) ｝＝｛x,y ∈GF(2m ) ｜y2＋xy＝x3＋
１｝∪｛∞｝ ここで∞は無限遠点を表わす。 （Ｓ２）適当な拡大次数ｍの決定 既述のごとく、公開鍵暗号の安全性の根拠となる上述の
楕円曲線の離散対数問題は、ベースポイントである元Ｂ
Ｐの位数が大きな素因数を持たなければ簡単に解けるこ
とが知られている。
【００２４】位数が大きな素因数を持つ元ＢＰが存在す
るための必要十分条件はＥ｛ＧＦ（ｑ）｝の元の個数が
大きな素因数を持つことである。そこで、（Ｓ１）に述
べた楕円曲線Ｅi についてその元の個数＃Ｅi ｛ＧＦ
（２m ）｝が大きな素因数で割り切れるようにｍを求め
る。（ここに、ｉ＝１、２） なお、Ｅ｛ＧＦ（２m ）｝等における各種楕円曲線の元
の個数は、ｍ等が具体的に与えられればハッセ（Ｈａｓ
ｓｅ）やデュー（Ｄｅｕ）等の研究により正確に計算可
能となっている。例えば、上記＃Ｅi ｛ＧＦ（２m ）｝
では、大よそ２ m のオーダーである。 （Ｓ３）実際の楕円曲線の構成 ３０桁以上の素因数を持つということより、ｍは大よそ
〔３０ ｌｏｇ2 １０〕となる。ここに〔 〕は、ガウ
ス（Ｇａｕｓｓ）の記号であり、記号内の数以下の最大
の整数を意味する。以下、基本的には試行錯誤によりか
かるｍをいくつかとって、＃Ｅi ｛ＧＦ（２m ）｝を与
える公式をもとに３０桁以上の素因数を有するか否か判
断する。
るための必要十分条件はＥ｛ＧＦ（ｑ）｝の元の個数が
大きな素因数を持つことである。そこで、（Ｓ１）に述
べた楕円曲線Ｅi についてその元の個数＃Ｅi ｛ＧＦ
（２m ）｝が大きな素因数で割り切れるようにｍを求め
る。（ここに、ｉ＝１、２） なお、Ｅ｛ＧＦ（２m ）｝等における各種楕円曲線の元
の個数は、ｍ等が具体的に与えられればハッセ（Ｈａｓ
ｓｅ）やデュー（Ｄｅｕ）等の研究により正確に計算可
能となっている。例えば、上記＃Ｅi ｛ＧＦ（２m ）｝
では、大よそ２ m のオーダーである。 （Ｓ３）実際の楕円曲線の構成 ３０桁以上の素因数を持つということより、ｍは大よそ
〔３０ ｌｏｇ2 １０〕となる。ここに〔 〕は、ガウ
ス（Ｇａｕｓｓ）の記号であり、記号内の数以下の最大
の整数を意味する。以下、基本的には試行錯誤によりか
かるｍをいくつかとって、＃Ｅi ｛ＧＦ（２m ）｝を与
える公式をもとに３０桁以上の素因数を有するか否か判
断する。
【００２５】楕円曲線Ｅi ｛ＧＦ（２m ）｝上の元で構
成される群Ｅi ｛ＧＦ（２m ）｝の元の個数を求め、そ
の素因数分解を行った結果 ｍ＝１０１のとき、＃Ｅ1 ｛ＧＦ（２n ）｝＝２×素数
ｐ1 ｍ＝１３１のとき、＃Ｅ2 ｛ＧＦ（２m ）｝＝４×素数
ｐ2 となることがわかった。また、ＭＯＶ帰着法により埋め
込まれる有限体が十分大きくなることも確かめられる。
成される群Ｅi ｛ＧＦ（２m ）｝の元の個数を求め、そ
の素因数分解を行った結果 ｍ＝１０１のとき、＃Ｅ1 ｛ＧＦ（２n ）｝＝２×素数
ｐ1 ｍ＝１３１のとき、＃Ｅ2 ｛ＧＦ（２m ）｝＝４×素数
ｐ2 となることがわかった。また、ＭＯＶ帰着法により埋め
込まれる有限体が十分大きくなることも確かめられる。
【００２６】従ってＥ2 ｛ＧＦ（２ 131）｝上の位数が
素数ｐ2 となる元をベースポイントＢＰとする楕円曲線
上の離散対数問題若しくはＥ1 ｛ＧＦ（２101 ）｝上の
位数が素数ｐ1 となる元をベースポイントＢＰとする楕
円曲線上の離散対数問題を安全性の根拠にした公開鍵暗
号を構成すればよいことが結論づけられる。さて、アノ
マラスではＴをＥ（ｘ，ｙ）からＥ（ｘ2 ，ｙ2 ）への
写像とするとき〔２〕（２倍）＝Ｔ−Ｔ2 となる。な
お、これについては、ジェイ・エッチ・シルバーマン著
「楕円曲線の数学（意訳）」スプリンガー書店 １９８
６年（J. H.Silverman, " The arithmetic of ellipti
c curves",Springer-Verlag,1986）に述べられている。
つまり、ＢＰ＝（ｘ，ｙ）とするとき、２ＢＰ＝（Ｔ−
Ｔ2 ）（ｘ，ｙ）＝（ｘ，ｙ）−（ｘ2 ，ｙ2 ）とな
る。このため、このように構成した楕円曲線は、２i Ｂ
Ｐ＝｛ＢＰ＝（ｘ，ｙ）；i ＝１、２、３、４｝の計算
が次のように求められる。
素数ｐ2 となる元をベースポイントＢＰとする楕円曲線
上の離散対数問題若しくはＥ1 ｛ＧＦ（２101 ）｝上の
位数が素数ｐ1 となる元をベースポイントＢＰとする楕
円曲線上の離散対数問題を安全性の根拠にした公開鍵暗
号を構成すればよいことが結論づけられる。さて、アノ
マラスではＴをＥ（ｘ，ｙ）からＥ（ｘ2 ，ｙ2 ）への
写像とするとき〔２〕（２倍）＝Ｔ−Ｔ2 となる。な
お、これについては、ジェイ・エッチ・シルバーマン著
「楕円曲線の数学（意訳）」スプリンガー書店 １９８
６年（J. H.Silverman, " The arithmetic of ellipti
c curves",Springer-Verlag,1986）に述べられている。
つまり、ＢＰ＝（ｘ，ｙ）とするとき、２ＢＰ＝（Ｔ−
Ｔ2 ）（ｘ，ｙ）＝（ｘ，ｙ）−（ｘ2 ，ｙ2 ）とな
る。このため、このように構成した楕円曲線は、２i Ｂ
Ｐ＝｛ＢＰ＝（ｘ，ｙ）；i ＝１、２、３、４｝の計算
が次のように求められる。
【００２７】２ＢＰ＝ＢＰ＋ＢＰ ４ＢＰ＝２（Ｔ−Ｔ2 ）＝−Ｔ3 −Ｔ2 ＝−（ｘ2 ＾ 3，ｙ2 ＾ 3）−（ｘ2 ＾ 2，ｙ2 ＾ 2） ８ＢＰ＝（−Ｔ3 −Ｔ2 ）（Ｔ−Ｔ2 ） ＝−（ｘ2 ＾ 3，ｙ2 ＾ 3）＋（ｘ2 ＾ 5，ｙ2 ＾ 5） １６ＢＰ＝（Ｔ3 ＋Ｔ2 ）2 ＝Ｔ6 ＋２Ｔ5 ＋Ｔ4 ＝２
Ｔ6 −Ｔ7 ＋Ｔ4 ＝Ｔ4 −Ｔ8 ＝（ｘ2 ＾ 4，ｙ2 ＾ 4）−（ｘ2 ＾ 8，ｙ2 ＾ 8） （ここに、上添え字中の＾の意味であるが、２＾３は２
3 を意味する。他も同様である。） 一方ＧＦ（２）の拡大体上の演算は、基底として正規基
底を用いると２乗の計算が巡回シフトでなされるのでハ
ードウエアで行なうときには、処理速度は無視できる。
よって、２i ＢＰ（i ＝１、２、３、４）の計算が２回
の楕円曲線の足し算で実行できることになり、高速化が
望める。また特にＥ2 では定義体ＧＦ（２131 ）上の正
規基底は最適な正規基底となり、一回の乗算に必要とな
る論理積及び排他的論理和の回数が最小になるので、基
本演算（有限体の乗算）の高速化が望める。なお、ここ
に最適な正規基底とは、乗法関数の項数が２ｍ−１とな
るものをいう。これは、アール・シー・ムリン他３名著
「ＧＦ（ｐ）における最適な正規基底（意訳）」ディス
クリート アプライド マシマテックス２２ １４９〜
１６１頁（R. C. Mullin他３名“Optimal normal bases
in GF(p a )”Discrete Applied Mathematics 22 P149
〜161 ）等に詳しい。
Ｔ6 −Ｔ7 ＋Ｔ4 ＝Ｔ4 −Ｔ8 ＝（ｘ2 ＾ 4，ｙ2 ＾ 4）−（ｘ2 ＾ 8，ｙ2 ＾ 8） （ここに、上添え字中の＾の意味であるが、２＾３は２
3 を意味する。他も同様である。） 一方ＧＦ（２）の拡大体上の演算は、基底として正規基
底を用いると２乗の計算が巡回シフトでなされるのでハ
ードウエアで行なうときには、処理速度は無視できる。
よって、２i ＢＰ（i ＝１、２、３、４）の計算が２回
の楕円曲線の足し算で実行できることになり、高速化が
望める。また特にＥ2 では定義体ＧＦ（２131 ）上の正
規基底は最適な正規基底となり、一回の乗算に必要とな
る論理積及び排他的論理和の回数が最小になるので、基
本演算（有限体の乗算）の高速化が望める。なお、ここ
に最適な正規基底とは、乗法関数の項数が２ｍ−１とな
るものをいう。これは、アール・シー・ムリン他３名著
「ＧＦ（ｐ）における最適な正規基底（意訳）」ディス
クリート アプライド マシマテックス２２ １４９〜
１６１頁（R. C. Mullin他３名“Optimal normal bases
in GF(p a )”Discrete Applied Mathematics 22 P149
〜161 ）等に詳しい。
【００２８】しかし上記従来例においては、楕円曲線の
一回の加法が高速になるというわけではない。このた
め、より高速にするには、演算を高速にする条件｛最適
な正規基底をもつ有限体ＧＦ（２m ）｝と安全で２i 倍
点（ｉ＝１、２、３、４）が簡単になる楕円曲線の条件
（アノラマス楕円曲線でかつ元の個数が大きな素数で割
れる）の両方の条件を満たす楕円曲線を見つける必要が
ある。しかし両者の条件は包含関係にあるわけではない
ので、両者を満たす楕円曲線の数は少なくなる。 （６）楕円曲線の高速化を図る他の技術 （加法鎖）楕円曲線のｋＢＰの計算を高速にする方法の
一つに加法鎖の研究がある。加法鎖とは、例えば７ＢＰ
を求めるのに単にＢＰを７回足すのではなく、２｛２
（２ＢＰ）｝−ＢＰとして、１回の足算と３回の２倍算
とするがごとく、足し方を工夫するものであり、有限体
のｇi の計算の加法鎖の研究と平行してなされる。これ
は、予備計算テーブルの持ち方及び計算の順序の工夫を
行う研究である。これについては、M. J. Coster, "Som
e algorithms on addition chains and theircomplexi
ty", Center for Mathematics and Computer Science R
eport CS-R9024 に詳しい。この方法を用いたk ・ ＢＰ
の計算と、上述の２i 倍点（ｉ＝１、２、３、４）が簡
単になる方法を用いたk ・ ＢＰの計算では、加法鎖を用
いたほうが高速に実現される。 （有限体について）参考までに有限体を用いた暗号方式
について記すならば、これも様々な高速化の手法が提案
されている。しかし、有限体を用いるが故に解読防止の
面から秘密通信に使用する定義体が大きくなるという問
題がある。これについては、ディー・エム・ゴードン
「数体のふるい法を使用した有限体ＧＦ（ｐ）の離散対
数問題（意訳）」離散数学のＳＩＡＭ内の雑誌（D.M.Go
rdon, " Discrete logarithmsin GF(p) using the numb
er field sieve", to appear in SIAM Journal on Disc
rete Math. ）を参照されたい。
一回の加法が高速になるというわけではない。このた
め、より高速にするには、演算を高速にする条件｛最適
な正規基底をもつ有限体ＧＦ（２m ）｝と安全で２i 倍
点（ｉ＝１、２、３、４）が簡単になる楕円曲線の条件
（アノラマス楕円曲線でかつ元の個数が大きな素数で割
れる）の両方の条件を満たす楕円曲線を見つける必要が
ある。しかし両者の条件は包含関係にあるわけではない
ので、両者を満たす楕円曲線の数は少なくなる。 （６）楕円曲線の高速化を図る他の技術 （加法鎖）楕円曲線のｋＢＰの計算を高速にする方法の
一つに加法鎖の研究がある。加法鎖とは、例えば７ＢＰ
を求めるのに単にＢＰを７回足すのではなく、２｛２
（２ＢＰ）｝−ＢＰとして、１回の足算と３回の２倍算
とするがごとく、足し方を工夫するものであり、有限体
のｇi の計算の加法鎖の研究と平行してなされる。これ
は、予備計算テーブルの持ち方及び計算の順序の工夫を
行う研究である。これについては、M. J. Coster, "Som
e algorithms on addition chains and theircomplexi
ty", Center for Mathematics and Computer Science R
eport CS-R9024 に詳しい。この方法を用いたk ・ ＢＰ
の計算と、上述の２i 倍点（ｉ＝１、２、３、４）が簡
単になる方法を用いたk ・ ＢＰの計算では、加法鎖を用
いたほうが高速に実現される。 （有限体について）参考までに有限体を用いた暗号方式
について記すならば、これも様々な高速化の手法が提案
されている。しかし、有限体を用いるが故に解読防止の
面から秘密通信に使用する定義体が大きくなるという問
題がある。これについては、ディー・エム・ゴードン
「数体のふるい法を使用した有限体ＧＦ（ｐ）の離散対
数問題（意訳）」離散数学のＳＩＡＭ内の雑誌（D.M.Go
rdon, " Discrete logarithmsin GF(p) using the numb
er field sieve", to appear in SIAM Journal on Disc
rete Math. ）を参照されたい。
【００２９】
【発明が解決しようとする課題】しかしながら、上記楕
円曲線上の離散対数問題を安全性の根拠にした公開鍵暗
号は、高速な処理が求められる。従来例１のように特定
の自然数ｃに対しｃＢＰが高速になるという方法の場
合、一般の自然数ｋに対しｋＢＰを高速にする際、加法
鎖の方法と組み合わせて高速にするのが困難である。ま
た、特定のｃに対してｃＢＰが高速になるということか
らくる条件と基本演算が高速になる条件の両方を満たす
楕円曲線を構成すると定義体が大きくなる。このため、
定義体が小さく、一般の自然数に対してｋＢＰの演算が
高速にしえ、加法鎖と組み合わせることが容易、かつ基
本演算が高速な楕円曲線を使用して署名、認証及び秘密
通信を行うことが望まれている。
円曲線上の離散対数問題を安全性の根拠にした公開鍵暗
号は、高速な処理が求められる。従来例１のように特定
の自然数ｃに対しｃＢＰが高速になるという方法の場
合、一般の自然数ｋに対しｋＢＰを高速にする際、加法
鎖の方法と組み合わせて高速にするのが困難である。ま
た、特定のｃに対してｃＢＰが高速になるということか
らくる条件と基本演算が高速になる条件の両方を満たす
楕円曲線を構成すると定義体が大きくなる。このため、
定義体が小さく、一般の自然数に対してｋＢＰの演算が
高速にしえ、加法鎖と組み合わせることが容易、かつ基
本演算が高速な楕円曲線を使用して署名、認証及び秘密
通信を行うことが望まれている。
【００３０】また暗号システムの安全性を高めるために
は、一システムの安全性が損なわれた際に秘密通信を前
提として成り立っている取引等の全システムの安全性が
損なわれてしまう危険性あるいは一システムの安全性が
たまたま損なわれる確率を下げる必要性がある。このた
め、通信相手、通信目的等のシステム毎にもしくは同じ
システムであっても定期的に暗号のパラメータを変える
ことが望ましい。またこの際、変更量を最小限に抑える
こと及びシステム性能（速度、メモリサイズ等）が変わ
らないようにすることが要求される。これは、有限体で
いうならば、既述のごとく、ｐを定期的に変更するよう
なものである。
は、一システムの安全性が損なわれた際に秘密通信を前
提として成り立っている取引等の全システムの安全性が
損なわれてしまう危険性あるいは一システムの安全性が
たまたま損なわれる確率を下げる必要性がある。このた
め、通信相手、通信目的等のシステム毎にもしくは同じ
システムであっても定期的に暗号のパラメータを変える
ことが望ましい。またこの際、変更量を最小限に抑える
こと及びシステム性能（速度、メモリサイズ等）が変わ
らないようにすることが要求される。これは、有限体で
いうならば、既述のごとく、ｐを定期的に変更するよう
なものである。
【００３１】しかし上記従来例においては、ＧＦ（２）
上の楕円曲線をＧＦ（２m ）上に持ち上げる方法のた
め、システム性能を変えない楕円曲線を構成するのは困
難である。このため、システム毎に若しくは同じシステ
ムであっても必要な時期毎に暗号のパラメータを変更可
能かつこの際必要なメモリサイズ等の変更量が必要最小
限、しかも高速演算が可能な楕円曲線を使用しての署
名、認証及び秘密通信を行うことが望まれている。
上の楕円曲線をＧＦ（２m ）上に持ち上げる方法のた
め、システム性能を変えない楕円曲線を構成するのは困
難である。このため、システム毎に若しくは同じシステ
ムであっても必要な時期毎に暗号のパラメータを変更可
能かつこの際必要なメモリサイズ等の変更量が必要最小
限、しかも高速演算が可能な楕円曲線を使用しての署
名、認証及び秘密通信を行うことが望まれている。
【００３２】更に、これらの場合に、楕円曲線にはＭＯ
Ｖ帰着法が適用できないという条件がつくのは勿論であ
る。
Ｖ帰着法が適用できないという条件がつくのは勿論であ
る。
【００３３】
【課題を解決するための手段】本発明は、以上の目的を
達成するべくなされたものである。このため、請求項１
の発明においては、以下の手順からなる秘密通信方式と
している。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝と、そのベースポイントＢＰを通信網の
使用者たる各ユーザに提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を秘密鍵として選定
し、この自然数回前記ベースポイントＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに例えば通信網により相互に通知
する。 （４）相互に通信を行う２人のユーザは、相手方ユーザ
から通知されてきた公開鍵を各自が秘密に保持している
自分が選定した自然数回Ｅ｛ＧＦ（ｐ）｝上で加算した
値を求め、これを両者の共有鍵とする。 （５）相互に通信を行う２人のユーザは、共有鍵を使用
してビット情報たる通信文（含，映像、音響情報）を暗
号化及び復号するに際して、共有鍵と通信文の秘密化、
復号に使用する演算の内容、例えば足し算、排他的論理
和等を取極める。 （６）一方のユーザが通信文を共有鍵を使用してその取
極めに従って秘密化した上で他方のユーザに公開通信網
を使用して送信する。 （７）秘密化された通信文を受信した他方のユーザは、
取極めに従って共有鍵を使用して復号する。
達成するべくなされたものである。このため、請求項１
の発明においては、以下の手順からなる秘密通信方式と
している。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝と、そのベースポイントＢＰを通信網の
使用者たる各ユーザに提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を秘密鍵として選定
し、この自然数回前記ベースポイントＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに例えば通信網により相互に通知
する。 （４）相互に通信を行う２人のユーザは、相手方ユーザ
から通知されてきた公開鍵を各自が秘密に保持している
自分が選定した自然数回Ｅ｛ＧＦ（ｐ）｝上で加算した
値を求め、これを両者の共有鍵とする。 （５）相互に通信を行う２人のユーザは、共有鍵を使用
してビット情報たる通信文（含，映像、音響情報）を暗
号化及び復号するに際して、共有鍵と通信文の秘密化、
復号に使用する演算の内容、例えば足し算、排他的論理
和等を取極める。 （６）一方のユーザが通信文を共有鍵を使用してその取
極めに従って秘密化した上で他方のユーザに公開通信網
を使用して送信する。 （７）秘密化された通信文を受信した他方のユーザは、
取極めに従って共有鍵を使用して復号する。
【００３４】ここにＥ｛ＧＦ（ｐ）｝は以下のものであ
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつｐ＋１−
ａあるいはｐ＋１＋ａの一方が３０桁以上の大きい素数
で割れかつ、正整数ｔ及び小さい正整数αに対して２t
±αと表せる素数とする。
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつｐ＋１−
ａあるいはｐ＋１＋ａの一方が３０桁以上の大きい素数
で割れかつ、正整数ｔ及び小さい正整数αに対して２t
±αと表せる素数とする。
【００３５】楕円曲線Ｅはｄにより定まる類多項式Ｈd
（ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体Ｇ
Ｆ（ｐ）を定義体にもつ。請求項２の発明においては、
以下のようにしている。前記楕円曲線Ｅは有限体ＧＦ
（ｐ）を定義体にもつ楕円曲線ＥのＧＦ（ｐ）上の元で
構成される群をＥ｛ＧＦ（ｐ）｝とするとき、Ｅ｛ＧＦ
（ｐ）｝の元の個数が３０桁以上の大きな素数で割れ
る。
（ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体Ｇ
Ｆ（ｐ）を定義体にもつ。請求項２の発明においては、
以下のようにしている。前記楕円曲線Ｅは有限体ＧＦ
（ｐ）を定義体にもつ楕円曲線ＥのＧＦ（ｐ）上の元で
構成される群をＥ｛ＧＦ（ｐ）｝とするとき、Ｅ｛ＧＦ
（ｐ）｝の元の個数が３０桁以上の大きな素数で割れ
る。
【００３６】請求項３の発明においては、正整数αは、
２進数表記で２ｔ／３ビット以下の大きさである。請求
項４の発明においては、ｐを素数、ｒを正整数とし、有
限体ＧＦ（ｐr ）を定義体にもつ楕円曲線ＥのＧＦ（ｐ
r ）上の元で構成される群をＥ｛ＧＦ（ｐ r ）｝とする
とき、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線
Ｅ1 ，Ｅ2 ，・・・，Ｅn を、互いに同型ではないが元
の個数が等しくなるように構成し、各システムごと、各
通信相手ごと、１システムかつ同一通信相手で例えば１
年等の一定時期経過後ごとの少なくも一により使用する
楕円曲線を変えるようにしている。
２進数表記で２ｔ／３ビット以下の大きさである。請求
項４の発明においては、ｐを素数、ｒを正整数とし、有
限体ＧＦ（ｐr ）を定義体にもつ楕円曲線ＥのＧＦ（ｐ
r ）上の元で構成される群をＥ｛ＧＦ（ｐ r ）｝とする
とき、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線
Ｅ1 ，Ｅ2 ，・・・，Ｅn を、互いに同型ではないが元
の個数が等しくなるように構成し、各システムごと、各
通信相手ごと、１システムかつ同一通信相手で例えば１
年等の一定時期経過後ごとの少なくも一により使用する
楕円曲線を変えるようにしている。
【００３７】請求項５の発明においては、楕円曲線Ｅ
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅn である。請求項６の発明に
おいては、通信文を共有鍵を使用して取極めに従って秘
密化する際及び復号する際の演算において、２t ≡α
（mod p)若しくは２t ≡−α（mod p)という性質及び加
法鎖を使用するものとしている。
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅn である。請求項６の発明に
おいては、通信文を共有鍵を使用して取極めに従って秘
密化する際及び復号する際の演算において、２t ≡α
（mod p)若しくは２t ≡−α（mod p)という性質及び加
法鎖を使用するものとしている。
【００３８】請求項７の発明においては、以下の手順か
らなる秘密通信方式としている。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回、前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加
算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに通知する。 （４）２人のユーザは、通知された公開鍵と乱数を使用
しての通信文を暗号化及び復号するに際して、公開鍵と
乱数とを使用しての通信文の演算の内容の方法を取極め
る。 （５）公開鍵の通知を受けた他のユーザは、自分が所定
の手順で選定した乱数と相手方ユーザから通知されてき
た公開鍵をもとに、取極めに従って通信文をハード若し
くはソフト的な手段で暗号化する。 （６）ユーザは暗号化した通信文を、公開鍵を知らせて
きたユーザに送信する。 （７）受信した他方のユーザは、取極めに従って秘密化
された通信文を、ハード的若しくはソフト的な手段で復
号する。この際、自分が選定し秘密に保持している整数
を使用する。
らなる秘密通信方式としている。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回、前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加
算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに通知する。 （４）２人のユーザは、通知された公開鍵と乱数を使用
しての通信文を暗号化及び復号するに際して、公開鍵と
乱数とを使用しての通信文の演算の内容の方法を取極め
る。 （５）公開鍵の通知を受けた他のユーザは、自分が所定
の手順で選定した乱数と相手方ユーザから通知されてき
た公開鍵をもとに、取極めに従って通信文をハード若し
くはソフト的な手段で暗号化する。 （６）ユーザは暗号化した通信文を、公開鍵を知らせて
きたユーザに送信する。 （７）受信した他方のユーザは、取極めに従って秘密化
された通信文を、ハード的若しくはソフト的な手段で復
号する。この際、自分が選定し秘密に保持している整数
を使用する。
【００３９】ここにＥ｛ＧＦ（ｐ）｝は以下のものであ
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつ、ｐ＋１
−ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割
れかつ、正整数ｔ及び小さい正整数αに対して２t ±α
と表せる素数とする。
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつ、ｐ＋１
−ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割
れかつ、正整数ｔ及び小さい正整数αに対して２t ±α
と表せる素数とする。
【００４０】楕円曲線Ｅは、ｄにより定まる類多項式Ｈ
d （ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体
ＧＦ（ｐ）を定義体にもつ。請求項８の発明においては
更に、前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にも
つ楕円曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ
｛ＧＦ（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個
数が３０桁以上の大きな素数で割れるようにしている。
d （ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体
ＧＦ（ｐ）を定義体にもつ。請求項８の発明においては
更に、前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にも
つ楕円曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ
｛ＧＦ（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個
数が３０桁以上の大きな素数で割れるようにしている。
【００４１】請求項９の発明においては、正整数αは、
２ｔ／３ビット以下の大きさとする。請求項１０の発明
においては、ｐを素数、ｒを正整数とし、有限体ＧＦ
（ｐr）を定義体にもつ楕円曲線ＥのＧＦ（ｐr ）上の
元で構成される群をＥ｛ＧＦ（ｐr ）｝とするとき、有
限体ＧＦ（ｐr ）を定義体に持つ楕円曲線Ｅ1,Ｅ2 ，・
・・，Ｅn を、互いに同型ではないが元の個数が等しく
なるように構成し、発注、購入、純粋な通信等の各シス
テムごと、客、官庁、本社等の各通信相手ごと、１シス
テムかつ同一通信相手で一定時期経過後ごとの少なくも
一により使用する楕円曲線を変えるようにしている。
２ｔ／３ビット以下の大きさとする。請求項１０の発明
においては、ｐを素数、ｒを正整数とし、有限体ＧＦ
（ｐr）を定義体にもつ楕円曲線ＥのＧＦ（ｐr ）上の
元で構成される群をＥ｛ＧＦ（ｐr ）｝とするとき、有
限体ＧＦ（ｐr ）を定義体に持つ楕円曲線Ｅ1,Ｅ2 ，・
・・，Ｅn を、互いに同型ではないが元の個数が等しく
なるように構成し、発注、購入、純粋な通信等の各シス
テムごと、客、官庁、本社等の各通信相手ごと、１シス
テムかつ同一通信相手で一定時期経過後ごとの少なくも
一により使用する楕円曲線を変えるようにしている。
【００４２】請求項１１の発明においては、楕円曲線Ｅ
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅnである。請求項１２の発明
においては、通信文を共有鍵を使用して取極めに従って
秘密化する際及び復号する際の演算において、２t ≡α
（mod n)若しくは２t ≡−α（mod p)という性質及び加
法鍵を使用するものとしている。
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅnである。請求項１２の発明
においては、通信文を共有鍵を使用して取極めに従って
秘密化する際及び復号する際の演算において、２t ≡α
（mod n)若しくは２t ≡−α（mod p)という性質及び加
法鍵を使用するものとしている。
【００４３】
【作用】上記構成により請求項１の発明においては、以
下の手順で秘密通信がなされる。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
公開通信網や郵送により提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加算
した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに相互に通知する。 （４）相互に通信を行う２人のユーザは、相手方ユーザ
から通知されてきた公開鍵を各自が秘密に保持している
自分が選定した自然数回Ｅ｛ＧＦ（ｐ）｝上で加算した
値を求め、これを両者の共有鍵とする。 （５）相互に通信を行う２人のユーザは、共有鍵を使用
して通信文を暗号化及び復号するに際して、共有鍵と通
信文の演算の内容を別途取極める。 （６）一方のユーザが通信文を共有鍵を使用して取極め
に従って演算をすることにより秘密化した上で他方のユ
ーザに送信する。 （７）受信した他方のユーザは、取極めに従って共有鍵
を使用して逆演算、排他的論理和なら再度排他的論理和
等して復号する。
下の手順で秘密通信がなされる。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
公開通信網や郵送により提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加算
した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに相互に通知する。 （４）相互に通信を行う２人のユーザは、相手方ユーザ
から通知されてきた公開鍵を各自が秘密に保持している
自分が選定した自然数回Ｅ｛ＧＦ（ｐ）｝上で加算した
値を求め、これを両者の共有鍵とする。 （５）相互に通信を行う２人のユーザは、共有鍵を使用
して通信文を暗号化及び復号するに際して、共有鍵と通
信文の演算の内容を別途取極める。 （６）一方のユーザが通信文を共有鍵を使用して取極め
に従って演算をすることにより秘密化した上で他方のユ
ーザに送信する。 （７）受信した他方のユーザは、取極めに従って共有鍵
を使用して逆演算、排他的論理和なら再度排他的論理和
等して復号する。
【００４４】ここにＥ｛ＧＦ（ｐ）｝は以下のものであ
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつｐ＋１−
ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割れ
かつ、正整数ｔ及び小さい正整数αに対して２t ±αと
表せる素数とする。
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつｐ＋１−
ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割れ
かつ、正整数ｔ及び小さい正整数αに対して２t ±αと
表せる素数とする。
【００４５】楕円曲線Ｅはｄにより定まる類多項式Ｈd
（ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体Ｇ
Ｆ（ｐ）を定義体にもつ。請求項２の発明においては、
前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ楕円
曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛ＧＦ
（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が３
０桁以上の大きな素数で割れるものとされている。
（ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体Ｇ
Ｆ（ｐ）を定義体にもつ。請求項２の発明においては、
前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ楕円
曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛ＧＦ
（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が３
０桁以上の大きな素数で割れるものとされている。
【００４６】請求項３の発明においては、正整数αは、
２ｔ／３ビット以下の大きさであるものとされている。
請求項４の発明においては、ｐを素数、ｒを正整数と
し、有限体ＧＦ（ｐr ）を定義体にもつ楕円曲線ＥのＧ
Ｆ（ｐr ）上の元で構成される群をＥ｛ＧＦ（ｐ r ）｝
とするとき、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲
線Ｅ1 ，Ｅ2 ，・・・，Ｅn を、互いに同型ではないが
元の個数が等しくなるように構成し、各システムごと、
各通信相手ごと、１システムかつ同一通信相手で一定時
期経過後ごとの少なくも一により使用する楕円曲線が変
更される。
２ｔ／３ビット以下の大きさであるものとされている。
請求項４の発明においては、ｐを素数、ｒを正整数と
し、有限体ＧＦ（ｐr ）を定義体にもつ楕円曲線ＥのＧ
Ｆ（ｐr ）上の元で構成される群をＥ｛ＧＦ（ｐ r ）｝
とするとき、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲
線Ｅ1 ，Ｅ2 ，・・・，Ｅn を、互いに同型ではないが
元の個数が等しくなるように構成し、各システムごと、
各通信相手ごと、１システムかつ同一通信相手で一定時
期経過後ごとの少なくも一により使用する楕円曲線が変
更される。
【００４７】請求項５の発明においては、楕円曲線Ｅ
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅn であるものとしている。請
求項６の発明においては、通信文を共有鍵を使用して取
極めに従って秘密化する際及び復号する際の演算におい
て、２t ≡α（mod p)若しくは２t ≡−α（mod p)とい
う性質及び加法鎖を使用することにより、秘密化と復号
の際の信号処理が高速になされる。
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅn であるものとしている。請
求項６の発明においては、通信文を共有鍵を使用して取
極めに従って秘密化する際及び復号する際の演算におい
て、２t ≡α（mod p)若しくは２t ≡−α（mod p)とい
う性質及び加法鎖を使用することにより、秘密化と復号
の際の信号処理が高速になされる。
【００４８】請求項７の発明においては、以下の手順に
て秘密通信がなされる。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回、前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加
算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに通知する。 （４）２人のユーザは、通知された公開鍵と乱数を使用
しての通信文を暗号化及び復号するに際して、公開鍵と
乱数を使用しての通信文の演算の内容の方法例えば通信
文のブロック分割方法等を取極める。 （５）公開鍵の通知を受けた他のユーザは、自分が別途
のプログラム等により選定した乱数と相手方ユーザから
通知されてきた公開鍵をもとに、取極めに従って送信す
べき通信文を暗号化する。 （６）ユーザは暗号化した通信文を、公開鍵を知らせて
きたユーザに送信する。 （７）受信した他方のユーザは、取極めに従って秘密化
された通信文をハード的若しくはソフト的に復号する。
この際、自分が選定し秘密に保持している整数を使用す
る。
て秘密通信がなされる。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回、前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加
算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに通知する。 （４）２人のユーザは、通知された公開鍵と乱数を使用
しての通信文を暗号化及び復号するに際して、公開鍵と
乱数を使用しての通信文の演算の内容の方法例えば通信
文のブロック分割方法等を取極める。 （５）公開鍵の通知を受けた他のユーザは、自分が別途
のプログラム等により選定した乱数と相手方ユーザから
通知されてきた公開鍵をもとに、取極めに従って送信す
べき通信文を暗号化する。 （６）ユーザは暗号化した通信文を、公開鍵を知らせて
きたユーザに送信する。 （７）受信した他方のユーザは、取極めに従って秘密化
された通信文をハード的若しくはソフト的に復号する。
この際、自分が選定し秘密に保持している整数を使用す
る。
【００４９】ここにＥ｛ＧＦ（ｐ）｝は以下のものであ
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつ、ｐ＋１
−ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割
れかつ、正整数ｔ及び小さい正整数αに対して２t ±α
と表せる素数とする。
る。正整数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が
小さくなるようにとる。素数ｐを、ある整数ａに対して
４×ｐ−ａ2 の素因数がｄ×平方数となりかつ、ｐ＋１
−ａあるいはｐ＋１＋ａが３０桁以上の大きい素数で割
れかつ、正整数ｔ及び小さい正整数αに対して２t ±α
と表せる素数とする。
【００５０】楕円曲線Ｅは、ｄにより定まる類多項式Ｈ
d （ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体
ＧＦ（ｐ）を定義体にもつ。請求項８の発明において
は、前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ
楕円曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛Ｇ
Ｆ（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が
３０桁以上の大きな素数で割れるようにされている。
d （ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体
ＧＦ（ｐ）を定義体にもつ。請求項８の発明において
は、前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ
楕円曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛Ｇ
Ｆ（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が
３０桁以上の大きな素数で割れるようにされている。
【００５１】請求項９の発明においては、正整数αは、
２ｔ／３ビット以下の大きさとされている。請求項１０
の発明においては、ｐを素数、ｒを正整数とし、有限体
ＧＦ（ｐr）を定義体にもつ楕円曲線ＥのＧＦ（ｐr ）
上の元で構成される群をＥ｛ＧＦ（ｐr ）｝とすると
き、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線Ｅ1,Ｅ
2 ，・・・，Ｅn を、互いに同型ではないが元の個数が
等しくなるように構成し、各システムごと、各通信相手
ごと、１システムかつ同一通信相手で一定時期経過後ご
との少なくも一により使用する楕円曲線を変えるものと
している。
２ｔ／３ビット以下の大きさとされている。請求項１０
の発明においては、ｐを素数、ｒを正整数とし、有限体
ＧＦ（ｐr）を定義体にもつ楕円曲線ＥのＧＦ（ｐr ）
上の元で構成される群をＥ｛ＧＦ（ｐr ）｝とすると
き、有限体ＧＦ（ｐr ）を定義体に持つ楕円曲線Ｅ1,Ｅ
2 ，・・・，Ｅn を、互いに同型ではないが元の個数が
等しくなるように構成し、各システムごと、各通信相手
ごと、１システムかつ同一通信相手で一定時期経過後ご
との少なくも一により使用する楕円曲線を変えるものと
している。
【００５２】請求項１１の発明においては、楕円曲線Ｅ
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅnであるものとしている。請
求項１２の発明においては、通信文を共有鍵を使用して
取極めに従って秘密化する際及び復号する際の演算にお
いて、２t ≡α（mod n)若しくは２t ≡−α（mod p)と
いう性質及び加法鍵を使用するものとしている。
は、ｄにより定まる類多項式Ｈd （ｘ）＝０の次数をｎ
とし、ｐを法とした解をｊ1 、…、ｊn とするとき、こ
れらの根をｊ不変数にもつ有限体ＧＦ（ｐ）を定義体に
もつ楕円曲線Ｅ1 、…、Ｅnであるものとしている。請
求項１２の発明においては、通信文を共有鍵を使用して
取極めに従って秘密化する際及び復号する際の演算にお
いて、２t ≡α（mod n)若しくは２t ≡−α（mod p)と
いう性質及び加法鍵を使用するものとしている。
【００５３】
【実施例】以下、楕円曲線の作成とこの作成した楕円曲
線での信号処理並びに署名、認証及び秘密通信の手順と
に分けて本発明の実施例を説明する。 （第１実施例）図１に、本発明の署名、認証及び秘密通
信方式に使用する楕円曲線の作成手順の概略を示す。本
図のうち、Ａは全体の基本的な流れを示し、Ｂはそのう
ちの一部、具体的には素数ｐの決定のステップの詳細を
示す。
線での信号処理並びに署名、認証及び秘密通信の手順と
に分けて本発明の実施例を説明する。 （第１実施例）図１に、本発明の署名、認証及び秘密通
信方式に使用する楕円曲線の作成手順の概略を示す。本
図のうち、Ａは全体の基本的な流れを示し、Ｂはそのう
ちの一部、具体的には素数ｐの決定のステップの詳細を
示す。
【００５４】以下、本図を参照しながら実施例の手順を
説明する。 （ａ１）自然数ｄの決定 自然数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さ
くなるようにとる。ここではｄ＝３とする。ここに、ｄ
＝３としたのは、後に示すＨｄ（ｘ）＝０のｐを法とし
た根を求める計算が楽なことによる。なお虚二次体Ｑ
｛（−ｄ）1/2 ｝及び類数については、前提のSilverma
n に詳しく述べられている。 （ａ２）素数ｐの生成 素数ｐを、ａとｂを自然数としたとき４ｐ−ａ2 ＝ｄ×
ｂ2 となりかつ、ｐ＋１−ａあるいはｐ＋１＋ａが大き
な素数で割れかつ、自然数ｔ及び小さい自然数αに対し
２t −αと表されるようにとる。
説明する。 （ａ１）自然数ｄの決定 自然数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さ
くなるようにとる。ここではｄ＝３とする。ここに、ｄ
＝３としたのは、後に示すＨｄ（ｘ）＝０のｐを法とし
た根を求める計算が楽なことによる。なお虚二次体Ｑ
｛（−ｄ）1/2 ｝及び類数については、前提のSilverma
n に詳しく述べられている。 （ａ２）素数ｐの生成 素数ｐを、ａとｂを自然数としたとき４ｐ−ａ2 ＝ｄ×
ｂ2 となりかつ、ｐ＋１−ａあるいはｐ＋１＋ａが大き
な素数で割れかつ、自然数ｔ及び小さい自然数αに対し
２t −αと表されるようにとる。
【００５５】この選定手順は試行錯誤法によるが、これ
を本図のＢを参照しつつ説明する。なお、この前に、本
手順の実現可能性に関係のある数学の理論について概略
紹介しておく。 （１）４ｐ＝ａ2 ＋ｄ×ｂ2 という形の方程式は、Ｐｅ
ｌｌ方程式といわれているものの特殊なものであり、ｐ
が与えられた場合に、これを充たすａとｂは連分数展開
で容易に求められる。
を本図のＢを参照しつつ説明する。なお、この前に、本
手順の実現可能性に関係のある数学の理論について概略
紹介しておく。 （１）４ｐ＝ａ2 ＋ｄ×ｂ2 という形の方程式は、Ｐｅ
ｌｌ方程式といわれているものの特殊なものであり、ｐ
が与えられた場合に、これを充たすａとｂは連分数展開
で容易に求められる。
【００５６】（２）素数定理により、ある自然数ｎのあ
たりには、ほぼｌｏｇｎ個に１個のわりで素数が存在し
ているのが証明されている。このため、２t −αという
形で表される３０桁程度の自然数は、ほぼ１００個に１
個が素数であるのがわかる。更に、２、３、５等小さな
素数の倍数は比較的容易に排除しえるため、これらを排
除すると素数である確率はうんと高くなる。従って２、
３、５等の小さな素数の倍数でない２t −αという自然
数が素数か否かは、現在の計算機と数学の理論（Mille
r,Cohen,Lenstra）で一層容易に確かめられる。
たりには、ほぼｌｏｇｎ個に１個のわりで素数が存在し
ているのが証明されている。このため、２t −αという
形で表される３０桁程度の自然数は、ほぼ１００個に１
個が素数であるのがわかる。更に、２、３、５等小さな
素数の倍数は比較的容易に排除しえるため、これらを排
除すると素数である確率はうんと高くなる。従って２、
３、５等の小さな素数の倍数でない２t −αという自然
数が素数か否かは、現在の計算機と数学の理論（Mille
r,Cohen,Lenstra）で一層容易に確かめられる。
【００５７】（３）ほとんどの自然数は、ｌｏｇ ｌｏ
ｇｎ個程度の素因数を有する（Hardy-Ramanujan ）。こ
のため、ｐが３０桁程度の数ならば、ｐ＋１−ａ、ｐ＋
１＋ａの素因数の個数は多くの場合、４〜７個である。
従って、ｐ＋１−ａあるいはｐ＋１＋ａが充分大きい素
因数を有するか否かは、多くの場合容易に判定できる。
勿論、その自然数自身が素数であるのを確かめたりもで
きる。
ｇｎ個程度の素因数を有する（Hardy-Ramanujan ）。こ
のため、ｐが３０桁程度の数ならば、ｐ＋１−ａ、ｐ＋
１＋ａの素因数の個数は多くの場合、４〜７個である。
従って、ｐ＋１−ａあるいはｐ＋１＋ａが充分大きい素
因数を有するか否かは、多くの場合容易に判定できる。
勿論、その自然数自身が素数であるのを確かめたりもで
きる。
【００５８】次に、具体的なｐ，ａ，α，ｔの選定順序
を図４のＢをもとに説明する。まず、ｔを選定した上で
初期設定としてｉ＝０、α＝〔２ｔ／３〕とする（ｂ
１）。次いで、αをα−ｉとする（ｂ２）。ｐ＝２t −
αを計算する（ｂ３）。４ｐが、ａ2 ＋３ｂ2 という形
に表しえるか否かを判定する（ｂ４）。もし、表しえな
いならば、ｉ＝ｉ＋１とし（ｂ５）、ステップｂ２へも
どる。
を図４のＢをもとに説明する。まず、ｔを選定した上で
初期設定としてｉ＝０、α＝〔２ｔ／３〕とする（ｂ
１）。次いで、αをα−ｉとする（ｂ２）。ｐ＝２t −
αを計算する（ｂ３）。４ｐが、ａ2 ＋３ｂ2 という形
に表しえるか否かを判定する（ｂ４）。もし、表しえな
いならば、ｉ＝ｉ＋１とし（ｂ５）、ステップｂ２へも
どる。
【００５９】４ｐが、ａ2 ＋３ｂ2 という形に表しえる
ならば、ｐが素数か否かを判定する（ｂ６）。素数でな
いならば、ステップｂ５へもどる。ｐが素数であるなら
ば、ｐ＋１＋ａ、ｐ＋１−ａの一方は大きい素因数を有
するか否かを判別する（ｂ７）。有しなければステップ
ｂ５へもどる。大きな素数で割り切れば、終了する。
ならば、ｐが素数か否かを判定する（ｂ６）。素数でな
いならば、ステップｂ５へもどる。ｐが素数であるなら
ば、ｐ＋１＋ａ、ｐ＋１−ａの一方は大きい素因数を有
するか否かを判別する（ｂ７）。有しなければステップ
ｂ５へもどる。大きな素数で割り切れば、終了する。
【００６０】ここでは ｐ＝２t −α ｔ＝１０７ α＝１ ａ＝２４ ３８７８９ ２３０３７ ４０８１５ ととる。
【００６１】このとき、ｐ＋１＋ａは１００ビットの素
数で割れる。 （ａ３）楕円曲線Ｅの決定 Ｅは、類多項式Ｈ3 （Ｘ）＝Ｘのｐを法とした根ｊ＝０
をもとにもとめられる。なお、この数学的な面について
は、前記Silverman の本に掲載されている。さて、有限
体ＧＦ（ｐ）を定義体にもち、元の個数が丁度ｐ＋１＋
ａ個になる楕円曲線Ｅのｊ不変数は０になるので、Ｅは
次で与えられる。
数で割れる。 （ａ３）楕円曲線Ｅの決定 Ｅは、類多項式Ｈ3 （Ｘ）＝Ｘのｐを法とした根ｊ＝０
をもとにもとめられる。なお、この数学的な面について
は、前記Silverman の本に掲載されている。さて、有限
体ＧＦ（ｐ）を定義体にもち、元の個数が丁度ｐ＋１＋
ａ個になる楕円曲線Ｅのｊ不変数は０になるので、Ｅは
次で与えられる。
【００６２】Ｅ：ｙ2 ＝ｘ3 ＋Ｂ Ｂ＝６２５ このとき、＃Ｅ｛ＧＦ（ｐ）｝＝ｐ＋１＋ａである。な
お、これは前記Silverman の本に示されている。このた
め、安全で高速な楕円曲線暗号が構成できる。上記のよ
うにして構成された楕円曲線Ｅを従来例２の楕円曲線上
の署名、認証及び秘密通信方式に用いると、ベースポイ
ントＢＰの位数が大きな素数で割れ、かつＭＯＶ帰着法
を避けることができるので安全な方式が実現される。
お、これは前記Silverman の本に示されている。このた
め、安全で高速な楕円曲線暗号が構成できる。上記のよ
うにして構成された楕円曲線Ｅを従来例２の楕円曲線上
の署名、認証及び秘密通信方式に用いると、ベースポイ
ントＢＰの位数が大きな素数で割れ、かつＭＯＶ帰着法
を避けることができるので安全な方式が実現される。
【００６３】さらに方式の実現に要求される基本演算の
ひとつであるＧＦ（ｐ）上の乗法は、２t ＝αと置き換
えることによりｐによる剰余を求めることなく次のよう
に実現できる。 ここに、ｓi とｓi+tは１又は０である。また従来例の
ように特定の自然数ｃに対してのみｃ・ＢＰの計算が速
くなるというものではない。このため、一般の自然数ｋ
に対してｋ・ＢＰの計算を高速にする手法である加算鎖
の方法と組み合わせることにより、一層の高速化が可能
になる。またデータ量についても、定義体のデータとし
て信号処理用のスマートカードにｐを覚える代わりにｔ
とαを覚えさせることができ、この場合ｔのビット数は
無視でき、αは〔２ｔ／３〕ビット以下であるため、定
義体のデータ量が削減できる。また、演算の高速化にも
寄与する。
ひとつであるＧＦ（ｐ）上の乗法は、２t ＝αと置き換
えることによりｐによる剰余を求めることなく次のよう
に実現できる。 ここに、ｓi とｓi+tは１又は０である。また従来例の
ように特定の自然数ｃに対してのみｃ・ＢＰの計算が速
くなるというものではない。このため、一般の自然数ｋ
に対してｋ・ＢＰの計算を高速にする手法である加算鎖
の方法と組み合わせることにより、一層の高速化が可能
になる。またデータ量についても、定義体のデータとし
て信号処理用のスマートカードにｐを覚える代わりにｔ
とαを覚えさせることができ、この場合ｔのビット数は
無視でき、αは〔２ｔ／３〕ビット以下であるため、定
義体のデータ量が削減できる。また、演算の高速化にも
寄与する。
【００６５】なお、上述の実施例は自然数ｄを３として
行ったが、これは素数ｐを求める計算が楽なことと虚二
次体Ｑ｛（−ｄ）1/2 ｝の類数が小さく、この場合１と
なることによるものであり、他の虚二次体Ｑ｛（−ｄ）
1/2 ｝の類数が小さくなるような自然数なら何でもよ
い。また、虚二次体Ｑ｛（−ｄ1/2 ）｝の類数が小さい
のは、楕円曲線を求める演算が楽なことによるものであ
り、類数は１に限定されるものではない。なお、ｄ＜１
０００ならば、演算が実用上充分可能である。参考まで
に記すならば、類数が１の虚二次体をつくるｄとして
は、必ずしも全てが本発明の実施に適当とは限らない
が、他に１、２、７、１１、１９、４３、６７、１６３
の８個があり、同じく類数が２の虚二次体をつくるｄと
しては、１０、１５、２６、３０等がある。また、ｄに
対して条件を満たす素数ｐは上述の実施例だけに限定さ
れるのでなく、本実施例に示したｐに関する条件を満た
す素数なら何でもよい。蛇足ながら、ｐが３０桁以上で
あるならば、近い将来においても、充分な安全性、すな
わち逆演算の困難性が維持されるであろう。 （第２実施例）本発明の署名、認証及び秘密通信方式に
使用する楕円曲線の他の作成手順の実施例を示す。本実
施例の作成手順も、基本的には図４に示すのと同じであ
る。以下、同図のＡを流用しながら実施例の手順を説明
する。 （ａ１）自然数ｄの決定 自然数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さ
くなるようにとる。ここではｄ＝２４とする。 （ａ２）素数ｐの生成 素数ｐを、ａ，ｂを自然数としたとき４ｐ−ａ2 ＝２４
×ｂ2 となりかつ、ｐ＋１−ａあるいはｐ＋１＋ａが大
きな素数で割れかつ、自然数ｔ及び小さい自然数αに対
し２t −αと表されるようにとる。
行ったが、これは素数ｐを求める計算が楽なことと虚二
次体Ｑ｛（−ｄ）1/2 ｝の類数が小さく、この場合１と
なることによるものであり、他の虚二次体Ｑ｛（−ｄ）
1/2 ｝の類数が小さくなるような自然数なら何でもよ
い。また、虚二次体Ｑ｛（−ｄ1/2 ）｝の類数が小さい
のは、楕円曲線を求める演算が楽なことによるものであ
り、類数は１に限定されるものではない。なお、ｄ＜１
０００ならば、演算が実用上充分可能である。参考まで
に記すならば、類数が１の虚二次体をつくるｄとして
は、必ずしも全てが本発明の実施に適当とは限らない
が、他に１、２、７、１１、１９、４３、６７、１６３
の８個があり、同じく類数が２の虚二次体をつくるｄと
しては、１０、１５、２６、３０等がある。また、ｄに
対して条件を満たす素数ｐは上述の実施例だけに限定さ
れるのでなく、本実施例に示したｐに関する条件を満た
す素数なら何でもよい。蛇足ながら、ｐが３０桁以上で
あるならば、近い将来においても、充分な安全性、すな
わち逆演算の困難性が維持されるであろう。 （第２実施例）本発明の署名、認証及び秘密通信方式に
使用する楕円曲線の他の作成手順の実施例を示す。本実
施例の作成手順も、基本的には図４に示すのと同じであ
る。以下、同図のＡを流用しながら実施例の手順を説明
する。 （ａ１）自然数ｄの決定 自然数ｄを、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さ
くなるようにとる。ここではｄ＝２４とする。 （ａ２）素数ｐの生成 素数ｐを、ａ，ｂを自然数としたとき４ｐ−ａ2 ＝２４
×ｂ2 となりかつ、ｐ＋１−ａあるいはｐ＋１＋ａが大
きな素数で割れかつ、自然数ｔ及び小さい自然数αに対
し２t −αと表されるようにとる。
【００６６】ここでは ｐ＝２t −α ｔ＝１２７ α＝１ ａ＝１０６７１ ９３１７９ ３１４５５ ４５２１９ ととる。このとき、ｐ＋１−ａは１２４ビットの素数で
割れる。
割れる。
【００６７】なお、この際の詳細な手順も基本的には図
４のＢに示すのと同じである。 （ａ３）楕円曲線Ｅの決定 類多項式Ｈ24（Ｘ）＝Ｘ2 ー４８３４９４４Ｘ＋１４６
７０１３９３９２のｐを法とした根は ｊ1 ＝3 14934 62074 25766 39325 56096 ｊ2 ＝1701 41183 46043 77382 69613 04605 19563 845
75 である。有限体ＧＦ（ｐ）を定義体にもち、元の個数が
丁度ｐ＋１−ａ個になる楕円曲線Ｅのｊ不変数はｊ1 と
ｊ2 で与えられる。よってそれぞれをｊ不変数にもつ楕
円曲線は次で与えられる。
４のＢに示すのと同じである。 （ａ３）楕円曲線Ｅの決定 類多項式Ｈ24（Ｘ）＝Ｘ2 ー４８３４９４４Ｘ＋１４６
７０１３９３９２のｐを法とした根は ｊ1 ＝3 14934 62074 25766 39325 56096 ｊ2 ＝1701 41183 46043 77382 69613 04605 19563 845
75 である。有限体ＧＦ（ｐ）を定義体にもち、元の個数が
丁度ｐ＋１−ａ個になる楕円曲線Ｅのｊ不変数はｊ1 と
ｊ2 で与えられる。よってそれぞれをｊ不変数にもつ楕
円曲線は次で与えられる。
【００６８】Ｅ1 ：ｙ2 ＝ｘ3 ＋Ａ1 ｘ＋Ｂ1 Ａ1 ＝915 03150 65123 53429 89289 36723 21130 5448
8 Ｂ1 ＝1177 15828 25431 33059 03422 01272 67034 049
01 Ｅ2 ：ｙ2 ＝ｘ3 ＋Ａ2 ｘ＋Ｂ2 Ａ2 ＝1400 68970 50479 08325 24538 34292 93927 226
73 Ｂ2 ＝366 65585 84970 41444 39129 79404 76337 7987
3 このとき、＃Ｅ1 ｛ＧＦ（ｐ）｝＝＃Ｅ2 ｛ＧＦ
（ｐ）｝＝ｐ＋１−ａであるが、ｊ不変数が異なるので
互いに同型でない。このためＥ1 による暗号方式が解読
されたところでＥ2 による暗号方式が解読されることは
ない。
8 Ｂ1 ＝1177 15828 25431 33059 03422 01272 67034 049
01 Ｅ2 ：ｙ2 ＝ｘ3 ＋Ａ2 ｘ＋Ｂ2 Ａ2 ＝1400 68970 50479 08325 24538 34292 93927 226
73 Ｂ2 ＝366 65585 84970 41444 39129 79404 76337 7987
3 このとき、＃Ｅ1 ｛ＧＦ（ｐ）｝＝＃Ｅ2 ｛ＧＦ
（ｐ）｝＝ｐ＋１−ａであるが、ｊ不変数が異なるので
互いに同型でない。このためＥ1 による暗号方式が解読
されたところでＥ2 による暗号方式が解読されることは
ない。
【００６９】暗号システムをより強固なものにするに
は、システム毎にもしくは同じシステムでも定期的に暗
号方式のパラメータを変更することが望ましい。この
際、基本演算（定義体のｐと楕円曲線の元の個数Ｎを法
とした演算）は同一である方が変更を容易にする。上記
のように構成された楕円曲線Ｅ1 及びＥ2 は、基本演算
は同じであるが同型でない暗号方式、すなわち異なる暗
号を提供できる。よってＥ 1 とＥ2 を２つのシステムで
別々に用いる、あるいは一つのシステムにおいてＥ 1 か
らＥ2 に変更することにより容易に暗号システムを強固
にできる。さらに方式の実現に要求される基本演算の一
つであるＧＦ（ｐ）上の乗法は、ｐ＝２t ±αという形
から一般の有限体上の乗法に比較して高速に実現でき
る。また従来例のように特定の自然数ｃのみに対しｃ・
ＢＰの計算が速くなるというものではない。このため、
一般の自然数ｋに対してｋ・ＢＰの計算を高速にする手
法である加算鎖の方法と容易に組み合わせることにより
高速化が可能になる。またデータ量についても、定義体
のデータとしてｐを記憶する代わりにｔとαを記憶する
だけでよいので、定義体のデータ量は小さくなる。
は、システム毎にもしくは同じシステムでも定期的に暗
号方式のパラメータを変更することが望ましい。この
際、基本演算（定義体のｐと楕円曲線の元の個数Ｎを法
とした演算）は同一である方が変更を容易にする。上記
のように構成された楕円曲線Ｅ1 及びＥ2 は、基本演算
は同じであるが同型でない暗号方式、すなわち異なる暗
号を提供できる。よってＥ 1 とＥ2 を２つのシステムで
別々に用いる、あるいは一つのシステムにおいてＥ 1 か
らＥ2 に変更することにより容易に暗号システムを強固
にできる。さらに方式の実現に要求される基本演算の一
つであるＧＦ（ｐ）上の乗法は、ｐ＝２t ±αという形
から一般の有限体上の乗法に比較して高速に実現でき
る。また従来例のように特定の自然数ｃのみに対しｃ・
ＢＰの計算が速くなるというものではない。このため、
一般の自然数ｋに対してｋ・ＢＰの計算を高速にする手
法である加算鎖の方法と容易に組み合わせることにより
高速化が可能になる。またデータ量についても、定義体
のデータとしてｐを記憶する代わりにｔとαを記憶する
だけでよいので、定義体のデータ量は小さくなる。
【００７０】なお、本実施例は正整数ｄを２４として行
ったが、これは勿論他の虚二次体Ｑ｛（−ｄ）1/2 ｝の
類数が小さくなるような正整数なら何でもよい。また、
ｄに対して条件を満たす素数ｐは上述の実施例だけに限
定されるのでなく先に示したｐに関する条件を満たす素
数なら何でもよい。そして、これらのことは先の実施例
と同じである。
ったが、これは勿論他の虚二次体Ｑ｛（−ｄ）1/2 ｝の
類数が小さくなるような正整数なら何でもよい。また、
ｄに対して条件を満たす素数ｐは上述の実施例だけに限
定されるのでなく先に示したｐに関する条件を満たす素
数なら何でもよい。そして、これらのことは先の実施例
と同じである。
【００７１】次に、上記第１実施例、第２実施例で示し
た手順で作成した楕円曲線を使用した離散対数問題を根
拠とする署名、認証及び秘密通信方式の実施例を説明す
る。 （第３実施例）本実施例は、先の第１実施例の楕円曲線
を使用した共有鍵暗号方式であり、図２に示す従来技術
の離散対数問題の困難性に基づくものと基本的な手順は
同じである。
た手順で作成した楕円曲線を使用した離散対数問題を根
拠とする署名、認証及び秘密通信方式の実施例を説明す
る。 （第３実施例）本実施例は、先の第１実施例の楕円曲線
を使用した共有鍵暗号方式であり、図２に示す従来技術
の離散対数問題の困難性に基づくものと基本的な手順は
同じである。
【００７２】すなわち、通信網の提供者がＥ｛ＧＦ
（ｐ）｝とＢＰを全ユーザに公開し、各ユーザＵ，Ｖ，
Ｗ，…は、各々任意の自然数ｕ，ｖ，ｗ，…を選定し、
これは秘密に保持する。この上で、各ユーザＵ，Ｖ，
Ｗ，…は各々ｕ・ＢＰ，ｖ・ＢＰ，ｗ・ＢＰ…を相互に
知らせあう。任意の二人のユーザは、自分の秘密に保持
する自然数と通信相手から知らされた値との積を計算
し、これを両者の共有鍵とする。例えばユーザＵとＶな
らばユーザＵは、自分の秘密に保持するｕとＶから知ら
されたｖ・ＢＰとの積ｕ・ｖ・ＢＰを計算する。同様
に、ユーザＶは、ｖとｕ・ＢＰとからｖ・ｕ・ＢＰを計
算する。ここに、当然ｕ・ｖ・ＢＰ＝ｖ・ｕ・ＢＰであ
る。この上で、両者は、ｕ・ｖ・ＢＰを秘密に保持す
る。
（ｐ）｝とＢＰを全ユーザに公開し、各ユーザＵ，Ｖ，
Ｗ，…は、各々任意の自然数ｕ，ｖ，ｗ，…を選定し、
これは秘密に保持する。この上で、各ユーザＵ，Ｖ，
Ｗ，…は各々ｕ・ＢＰ，ｖ・ＢＰ，ｗ・ＢＰ…を相互に
知らせあう。任意の二人のユーザは、自分の秘密に保持
する自然数と通信相手から知らされた値との積を計算
し、これを両者の共有鍵とする。例えばユーザＵとＶな
らばユーザＵは、自分の秘密に保持するｕとＶから知ら
されたｖ・ＢＰとの積ｕ・ｖ・ＢＰを計算する。同様
に、ユーザＶは、ｖとｕ・ＢＰとからｖ・ｕ・ＢＰを計
算する。ここに、当然ｕ・ｖ・ＢＰ＝ｖ・ｕ・ＢＰであ
る。この上で、両者は、ｕ・ｖ・ＢＰを秘密に保持す
る。
【００７３】さて、この場合、通信文は１次元の数値で
あり、ｕ・ｖ・ＢＰはｘ座標値とｙ座標値を有する２次
元の数値であるため、通信文の暗号化及び復号にはｘ座
標値若しくはｙ座標値のいずれか一方のみ使用され、い
ずれを使用したかを知らすため、別途１ビットのデータ
Ｃ（ｕ・ｖ・ＢＰ）を知らせるものとする。この際、第
１実施例の楕円曲線ではｐ≡３（ｍｏｄ ４）であるた
め、以下の性質を利用している。
あり、ｕ・ｖ・ＢＰはｘ座標値とｙ座標値を有する２次
元の数値であるため、通信文の暗号化及び復号にはｘ座
標値若しくはｙ座標値のいずれか一方のみ使用され、い
ずれを使用したかを知らすため、別途１ビットのデータ
Ｃ（ｕ・ｖ・ＢＰ）を知らせるものとする。この際、第
１実施例の楕円曲線ではｐ≡３（ｍｏｄ ４）であるた
め、以下の性質を利用している。
【００７４】 （ｘ3 ＋Ａｘ＋Ｂ）p-1 ＝１ （フェルマーの定理） ｙ4=（ｘ3 ＋Ａｘ＋Ｂ）2=（ｘ3 ＋Ａｘ＋Ｂ）4S+2＊（ｘ3 ＋Ａｘ＋Ｂ）2 ここに、Ｓ＝（ｐ−３）／４ 故に、ｙ＝±（ｘ3+Ａｘ＋Ｂ）S+1 このため、Ｃ（ｕ・ｖ・Ｂｐ）＝１のとき、ｙ＝−（ｘ
3+Ａｘ＋Ｂ）、 Ｃ（ｕ・ｖ・Ｂｐ）＝−１のとき、ｙ＝（ｘ3+Ａｘ＋
Ｂ）とあらかじめ取極めておく。 （第４実施例）本実施例では、第３実施例と同じ原理の
秘密通信を行なうものであるが、ユーザＵとユーザＶと
の間に証人の役を担う仲介者Ｗが存在するものである。
3+Ａｘ＋Ｂ）、 Ｃ（ｕ・ｖ・Ｂｐ）＝−１のとき、ｙ＝（ｘ3+Ａｘ＋
Ｂ）とあらかじめ取極めておく。 （第４実施例）本実施例では、第３実施例と同じ原理の
秘密通信を行なうものであるが、ユーザＵとユーザＶと
の間に証人の役を担う仲介者Ｗが存在するものである。
【００７５】最初、仲介者Ｗは、第２実施例にて示した
２つの楕円曲線Ｅ1 とＥ2 をもとに秘密通信に使用する
Ｅ1 ｛ＧＦ（ｐ）｝及びそのベースポイントＢＰu 並び
にＥ 2 ｛ＧＦ（ｐ）｝及びそのベースポイントＢＰV を
もとめる。この上で、ユーザＷは、ユーザＵに対しては
Ｅ1 ｛ＧＦ（ｐ）｝と自己が選択したベースポイントＢ
Ｐu を知らせる。ここにＢＰu はＥ1 ｛ＧＦ（ｐ）｝の
零元でない元である。勿論ユーザＶに対してはＥ1 ｛Ｇ
Ｆ（ｐ）｝もＢＰu も秘密にしておく。
２つの楕円曲線Ｅ1 とＥ2 をもとに秘密通信に使用する
Ｅ1 ｛ＧＦ（ｐ）｝及びそのベースポイントＢＰu 並び
にＥ 2 ｛ＧＦ（ｐ）｝及びそのベースポイントＢＰV を
もとめる。この上で、ユーザＷは、ユーザＵに対しては
Ｅ1 ｛ＧＦ（ｐ）｝と自己が選択したベースポイントＢ
Ｐu を知らせる。ここにＢＰu はＥ1 ｛ＧＦ（ｐ）｝の
零元でない元である。勿論ユーザＶに対してはＥ1 ｛Ｇ
Ｆ（ｐ）｝もＢＰu も秘密にしておく。
【００７６】ユーザＶに対してはＥ2 ｛ＧＦ（ｐ）｝と
自己が選定したベースポイントＢＰ V を知らせる。ここ
にＢＰV はＥ2 ｛ＧＦ（ｐ）｝の零元でない元である。
勿論ユーザＵに対してはＥ2 ｛ＧＦ（ｐ）｝もＢＰV も
秘密にしておく。しかる後、ユーザＵは任意の整数ｄu
を秘密に選定し、ユーザＷに対する自分の識別情報Ｙu
を式Ｙu ＝ｄu ・ＢＰu により計算する。
自己が選定したベースポイントＢＰ V を知らせる。ここ
にＢＰV はＥ2 ｛ＧＦ（ｐ）｝の零元でない元である。
勿論ユーザＵに対してはＥ2 ｛ＧＦ（ｐ）｝もＢＰV も
秘密にしておく。しかる後、ユーザＵは任意の整数ｄu
を秘密に選定し、ユーザＷに対する自分の識別情報Ｙu
を式Ｙu ＝ｄu ・ＢＰu により計算する。
【００７７】ユーザＷは任意の整数ｄuwを秘密に選定
し、ユーザＵに対する自分の識別情報Ｙuwを式Ｙuw＝ｄ
uw・ＢＰu により計算する。この上で、ユーザＵとユー
ザＷとは相互にＹu とＹuwとを通知しあい、Ｋuw＝ｄu
・Ｙuw＝ｄuw・Ｙu を両者の共有鍵とする。この上でユ
ーザＵからユーザＷへ共有鍵Ｋuwを暗号化鍵及び復号化
鍵とする秘密鍵暗号通信方式により署名を希望する平文
Ｍを送信する。この場合の演算は例えば平文Ｍと共有鍵
との排他的論理和（暗号化時）及びその逆演算（復号
時）とすることができる。
し、ユーザＵに対する自分の識別情報Ｙuwを式Ｙuw＝ｄ
uw・ＢＰu により計算する。この上で、ユーザＵとユー
ザＷとは相互にＹu とＹuwとを通知しあい、Ｋuw＝ｄu
・Ｙuw＝ｄuw・Ｙu を両者の共有鍵とする。この上でユ
ーザＵからユーザＷへ共有鍵Ｋuwを暗号化鍵及び復号化
鍵とする秘密鍵暗号通信方式により署名を希望する平文
Ｍを送信する。この場合の演算は例えば平文Ｍと共有鍵
との排他的論理和（暗号化時）及びその逆演算（復号
時）とすることができる。
【００７８】尚、前記Ｙu 、Ｙuw及びＫuwはユーザＶは
勿論のこと、第三者にも秘密に保持される。次に、ユー
ザＷは任意の整数ｄv を秘密に選定し、ユーザＶに対す
る自分の識別情報Ｙv を式Ｙv ＝ｄv ・ＢＰv により計
算する。ユーザＷは任意の整数ｄvwを秘密に選定し、ユ
ーザＶに対する自分の識別情報Ｙvw＝ｄvw・ＢＰv によ
り計算する。
勿論のこと、第三者にも秘密に保持される。次に、ユー
ザＷは任意の整数ｄv を秘密に選定し、ユーザＶに対す
る自分の識別情報Ｙv を式Ｙv ＝ｄv ・ＢＰv により計
算する。ユーザＷは任意の整数ｄvwを秘密に選定し、ユ
ーザＶに対する自分の識別情報Ｙvw＝ｄvw・ＢＰv によ
り計算する。
【００７９】この上でユーザＶとユーザＷは相互にＹv
とＹvwを通知しあい、Ｋvw＝ｄvw・Ｙv ＝ｄv ・ＢＰv
を両者の共有鍵とする。更に、ユーザＶとユーザＷとの
通信においては、この共有鍵Ｋvwを使用しての通信文の
秘密化の演算は排他的論理和ではなく、EXCLUSTIVE-NOR
が採用される。この場合にも、Ｙv 、Ｙvw及びＫvwはユ
ーザＵは勿論のこと第三者にも秘密に保持される。
とＹvwを通知しあい、Ｋvw＝ｄvw・Ｙv ＝ｄv ・ＢＰv
を両者の共有鍵とする。更に、ユーザＶとユーザＷとの
通信においては、この共有鍵Ｋvwを使用しての通信文の
秘密化の演算は排他的論理和ではなく、EXCLUSTIVE-NOR
が採用される。この場合にも、Ｙv 、Ｙvw及びＫvwはユ
ーザＵは勿論のこと第三者にも秘密に保持される。
【００８０】ここで、ユーザＵとユーザＷ及びユーザＶ
とユーザＷとで採用する楕円曲線を変更しているのは、
ユーザＵとユーザＷの通信文の内容をユーザＶに知得さ
れることとユーザＶとユーザＷの通信文の内容をユーア
Ｕに知得されることとを少しでも防ぐためである。また
秘密化そして復号の演算を変更しているのは、ユーザＷ
の過誤に対して少しでも安全性を増すためであり、また
その演算の具体的例として排他的論理和（EXCLUSIVE-O
R）、排他的論理和の反転（EXCLUSIVE-NOR ）を採用し
ているのは、秘密化と復号の処理に要する時間がほぼ同
じであるため通信効率がよいことによる。
とユーザＷとで採用する楕円曲線を変更しているのは、
ユーザＵとユーザＷの通信文の内容をユーザＶに知得さ
れることとユーザＶとユーザＷの通信文の内容をユーア
Ｕに知得されることとを少しでも防ぐためである。また
秘密化そして復号の演算を変更しているのは、ユーザＷ
の過誤に対して少しでも安全性を増すためであり、また
その演算の具体的例として排他的論理和（EXCLUSIVE-O
R）、排他的論理和の反転（EXCLUSIVE-NOR ）を採用し
ているのは、秘密化と復号の処理に要する時間がほぼ同
じであるため通信効率がよいことによる。
【００８１】以上のもとで、ユーザＵとユーザＶとの通
信はユーザＷを介在してなされることになる。この場
合、ユーザＷは一方のユーザ（Ｕ又はＶ）から他方のユ
ーザ（Ｖ又はＵ）への通信文を介在する場合に、認証し
た旨の証明文とその受付日時、発信日時等をも付加す
る。これにより、ユーザＵとユーザＶとの秘密通信はユ
ーザＷにより認証されたこととなる。
信はユーザＷを介在してなされることになる。この場
合、ユーザＷは一方のユーザ（Ｕ又はＶ）から他方のユ
ーザ（Ｖ又はＵ）への通信文を介在する場合に、認証し
た旨の証明文とその受付日時、発信日時等をも付加す
る。これにより、ユーザＵとユーザＶとの秘密通信はユ
ーザＷにより認証されたこととなる。
【００８２】この場合、秘密性の向上のため異なる楕円
曲線Ｅ1 ，Ｅ2 を使用するが、定義体のｐと楕円曲線の
元の個数Ｎを法とした演算が同じであるため、仲介者Ｗ
の処理も剰余演算ルーチンを共通化できる等種々便利と
なる。 （第５実施例）本実施例は第１実施例の楕円曲線を署
名、認証通信に使用したものである。図５は、その手順
を示したものである。
曲線Ｅ1 ，Ｅ2 を使用するが、定義体のｐと楕円曲線の
元の個数Ｎを法とした演算が同じであるため、仲介者Ｗ
の処理も剰余演算ルーチンを共通化できる等種々便利と
なる。 （第５実施例）本実施例は第１実施例の楕円曲線を署
名、認証通信に使用したものである。図５は、その手順
を示したものである。
【００８３】網提供者は、Ｅ｛ＧＦ（ｐ）｝とＢＰとを
全ユーザに公開する。一方、秘密通信を希望するユーザ
ＵとユーザＶとは、任意の整数ｕ、ｖを秘密に作成し
（ステップ３）、網提供者から得た元ＢＰを用いて、Ｅ
｛ＧＦ（ｐ）｝上でＹu ＝ｕ・ＢＰ、Ｙv ＝ｖ・ＢＰを
計算する。そして、このＹu 、Ｙv を公開通信網を使用
して相互に通知する。
全ユーザに公開する。一方、秘密通信を希望するユーザ
ＵとユーザＶとは、任意の整数ｕ、ｖを秘密に作成し
（ステップ３）、網提供者から得た元ＢＰを用いて、Ｅ
｛ＧＦ（ｐ）｝上でＹu ＝ｕ・ＢＰ、Ｙv ＝ｖ・ＢＰを
計算する。そして、このＹu 、Ｙv を公開通信網を使用
して相互に通知する。
【００８４】次に、ユーザＵからユーザＶに平文Ｍを送
る場合であると、Ｕは秘密に整数である乱数ｒu を選
び、自分だけが知っているこの乱数ｒu とＶの公開鍵Ｙ
v を用いて次の２組の通信文Ｃ1 、Ｃ2 を作成する。 Ｃ1 ＝ｒu ・ＢＰ …〔２〕 Ｃ2 ＝Ｍ＋ｒu ・Ｙv …〔３〕 そしてＵはＶにＣ1 、Ｃ2 を送る。
る場合であると、Ｕは秘密に整数である乱数ｒu を選
び、自分だけが知っているこの乱数ｒu とＶの公開鍵Ｙ
v を用いて次の２組の通信文Ｃ1 、Ｃ2 を作成する。 Ｃ1 ＝ｒu ・ＢＰ …〔２〕 Ｃ2 ＝Ｍ＋ｒu ・Ｙv …〔３〕 そしてＵはＶにＣ1 、Ｃ2 を送る。
【００８５】通信文Ｃ1 、Ｃ2 を受け取ったユーザＶは
自分だけが知っているｖを用いて次式を計算してＭを得
る。 Ｍ＝Ｃ2 −ｖ・Ｃ1 …〔４〕 この場合、もしユーザＵが通信先を誤って第三者である
他のユーザＷに送信したとしても、このＷはｖを知り得
ないため、通信文の復号をなしえない。 （第６実施例）次に、通信文の信号処理について説明す
る。
自分だけが知っているｖを用いて次式を計算してＭを得
る。 Ｍ＝Ｃ2 −ｖ・Ｃ1 …〔４〕 この場合、もしユーザＵが通信先を誤って第三者である
他のユーザＷに送信したとしても、このＷはｖを知り得
ないため、通信文の復号をなしえない。 （第６実施例）次に、通信文の信号処理について説明す
る。
【００８６】発生させた乱数及び通信文の秘密化と復号
に通信毎にＣ1 ＝ｒu ・ＢＰ1 ，Ｃ 2 ＝Ｍ＋ｘ（ｒu ・
Ｙv ）等の演算が必要とされる。この場合、例えば乱数
ｒu をとるならば、これは２進数では１と０とのみから
なり、これが１０進数で１５ならば２進数では２3 ＋２
2 ＋２＋１と表記される。この際、Ｅ｛ＧＦ（ｐ）｝上
でのｒu ・ＢＰ1 の演算にはあらかじめ求めていた２3
ＢＰ1 ，２2 ＢＰ1 ，２ＢＰ1 を使用するのにかえて２
4 ＢＰ1 −ＢＰ1が採用される。
に通信毎にＣ1 ＝ｒu ・ＢＰ1 ，Ｃ 2 ＝Ｍ＋ｘ（ｒu ・
Ｙv ）等の演算が必要とされる。この場合、例えば乱数
ｒu をとるならば、これは２進数では１と０とのみから
なり、これが１０進数で１５ならば２進数では２3 ＋２
2 ＋２＋１と表記される。この際、Ｅ｛ＧＦ（ｐ）｝上
でのｒu ・ＢＰ1 の演算にはあらかじめ求めていた２3
ＢＰ1 ，２2 ＢＰ1 ，２ＢＰ1 を使用するのにかえて２
4 ＢＰ1 −ＢＰ1が採用される。
【００８７】更に、２4 ＢＰ−ＢＰの計算は、ＧＦ
（ｐ）上の乗算を用いてできるので、２t ≡α（mod
ｐ）又は２t ≡−α（mod ｐ）という性質を利用する。
この他、値の如何によりRelated Artsで説明した加法鎖
も採用されるのは勿論である。以上、本発明を実施例に
もとづいて説明してきたが、本発明は何も上記実施例に
限定されるものではないのは勿論である。すなわち、例
えば （１）自然数ｄや類数は、素数や楕円曲線を求めるプロ
グラムや計算そのものの便宜のため、比較的小さな数と
したものとしている。しかしながら、外交、金融等秘密
の要請が高い場合には、計算費用は多少かかろうがより
桁数の高い値、例えば１００００、５００００、１００
０００前後等としてもよい。 （２）通信文の楕円曲線上でのＢＰとの演算を使用して
の暗号化等は、実施例では桁数が増加しないように論理
演算としたものであり、これに限定されない。具体的に
は、送信者と受信者の取極めで乱数を併用したり、通信
文をブロック分割し、この分割したブロックの入れ換え
に使用する等してもよい。なお、これらの場合には別途
使用した乱数の通知やブロック分割の仕方や入れ換え等
についての取極めがなされるのは勿論である。また、こ
れらについては、前揚の「現代暗号理論」に詳しい。 （３）楕円曲線Ｅ｛ＧＦ（ｐ）｝上の点のｘ座標、ｙ座
標の両方を交互にあるいは偶数日か奇数日かに応じて使
いわける等して通信文の暗号化に使用する。
（ｐ）上の乗算を用いてできるので、２t ≡α（mod
ｐ）又は２t ≡−α（mod ｐ）という性質を利用する。
この他、値の如何によりRelated Artsで説明した加法鎖
も採用されるのは勿論である。以上、本発明を実施例に
もとづいて説明してきたが、本発明は何も上記実施例に
限定されるものではないのは勿論である。すなわち、例
えば （１）自然数ｄや類数は、素数や楕円曲線を求めるプロ
グラムや計算そのものの便宜のため、比較的小さな数と
したものとしている。しかしながら、外交、金融等秘密
の要請が高い場合には、計算費用は多少かかろうがより
桁数の高い値、例えば１００００、５００００、１００
０００前後等としてもよい。 （２）通信文の楕円曲線上でのＢＰとの演算を使用して
の暗号化等は、実施例では桁数が増加しないように論理
演算としたものであり、これに限定されない。具体的に
は、送信者と受信者の取極めで乱数を併用したり、通信
文をブロック分割し、この分割したブロックの入れ換え
に使用する等してもよい。なお、これらの場合には別途
使用した乱数の通知やブロック分割の仕方や入れ換え等
についての取極めがなされるのは勿論である。また、こ
れらについては、前揚の「現代暗号理論」に詳しい。 （３）楕円曲線Ｅ｛ＧＦ（ｐ）｝上の点のｘ座標、ｙ座
標の両方を交互にあるいは偶数日か奇数日かに応じて使
いわける等して通信文の暗号化に使用する。
【００８８】
【発明の効果】以上説明してきたように、本発明では、
各種解法の存在しない、しかも比較的小さな楕円曲線上
の有限体を使用することにより秘密性の高いしかも信号
処理の迅速な署名、認証及び秘密通信方式を提供しえ
る。更に、この際、加法錠等の高速演算の併用も容易で
ある。
各種解法の存在しない、しかも比較的小さな楕円曲線上
の有限体を使用することにより秘密性の高いしかも信号
処理の迅速な署名、認証及び秘密通信方式を提供しえ
る。更に、この際、加法錠等の高速演算の併用も容易で
ある。
【００８９】また、ＩＣ回路等に記憶させることが必要
な情報量も少なくてすむ。また秘密性向上のため定期的
に楕円曲線を変更する際にも、必要なハード等の変更は
最小限ですむ。
な情報量も少なくてすむ。また秘密性向上のため定期的
に楕円曲線を変更する際にも、必要なハード等の変更は
最小限ですむ。
【図１】本発明における署名、認証及び秘密通信方式に
使用する楕円曲線を作成するフローチャートである。
使用する楕円曲線を作成するフローチャートである。
【図２】有限体上での離散対数問題の困難性に根拠をお
く秘密通信方式の手順の内容を示した図である。
く秘密通信方式の手順の内容を示した図である。
【図３】楕円曲線の演算の内容を示す図である。
【図４】従来の楕円曲線を見出す手順のフローチャート
である。
である。
【図５】本発明における署名、認証及び秘密通信方式に
使用する楕円曲線を使用しての秘密送信の際の通信文の
暗号化と復号の手順の一例を示した図である。
使用する楕円曲線を使用しての秘密送信の際の通信文の
暗号化と復号の手順の一例を示した図である。
Claims (12)
- 【請求項１】 以下の手順からなる秘密通信方式。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加算
した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに相互に通知する。 （４）相互に通信を行う２人のユーザは、各自が秘密に
保持している自分が選定した自然数回、相手方ユーザか
ら通知されてきた公開鍵とＥ｛ＧＦ（ｐ）｝上で加算し
た値を求め、これを両者の共有鍵とする。 （５）相互に通信を行う２人のユーザは、共有鍵を使用
して通信文を暗号化及び復号するに際して、共有鍵と通
信文の演算の内容を取極める。 （６）一方のユーザが通信文を共有鍵を使用して取極め
に従って秘密化した上で他方のユーザに送信する。 （７）受信した他方のユーザは、取極めに従って共有鍵
を使用して復号する。 ここにＥ｛ＧＦ（ｐ）｝は以下のものである。正整数ｄ
を、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さくなるよ
うにとる。素数ｐを、ある整数ａに対して４×ｐ−ａ2
の素因数がｄ×平方数となりかつｐ＋１−ａあるいはｐ
＋１＋ａが３０桁以上の大きい素数で割れかつ、正整数
ｔ及び小さい正整数αに対して２t ±αと表せる素数と
する。楕円曲線Ｅはｄにより定まる類多項式Ｈd （ｘ）
＝０のｐを法とした解をｊ不変数にもつ有限体ＧＦ
（ｐ）を定義体にもつ。 - 【請求項２】 請求項１において更に、 前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ楕円
曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛ＧＦ
（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が３
０桁以上の大きな素数で割れる。 - 【請求項３】 請求項１若しくは請求項２において更
に、 正整数αは、２ｔ／３ビット以下の大きさである。 - 【請求項４】 請求項１若しくは請求項２若しくは請求
項３において更に、 ｐを素数、ｒを正整数とし、有限体ＧＦ（ｐr ）を定義
体にもつ楕円曲線ＥのＧＦ（ｐr ）上の元で構成される
群をＥ｛ＧＦ（ｐr ）｝とするとき、有限体ＧＦ
（ｐr ）を定義体に持つ楕円曲線Ｅ1 ，Ｅ2 ，・・・，
Ｅn を、互いに同型ではないが元の個数が等しくなるよ
うに構成し、各システムごと、各通信相手ごと、１シス
テムかつ同一通信相手で一定時期経過後ごとの少なくも
一により使用する楕円曲線を変える。 - 【請求項５】 請求項１若しくは請求項２若しくは請求
項３若しくは請求項４において更に、 楕円曲線Ｅは、ｄにより定まる類多項式Ｈd （ｘ）＝０
の次数をｎとし、ｐを法とした解をｊ1 、…、ｊn とす
るとき、これらの根をｊ不変数にもつ有限体ＧＦ（ｐ）
を定義体にもつ楕円曲線Ｅ1 、…、Ｅn である。 - 【請求項６】 請求項１若しくは請求項２若しくは請求
項３若しくは請求項４若しくは請求項５において更に、 通信文を共有鍵を使用して取極めに従って秘密化する際
及び復号する際の演算において、２t ≡α（mod p)若し
くは２t ≡−α（mod p)という性質及び加法鎖を使用す
る。 - 【請求項７】 以下の手順からなる秘密通信方式。 （１）秘密通信網の提供者は、秘密通信に使用するＥ
｛ＧＦ（ｐ）｝とそのベースポイントＢＰを各ユーザに
提供する。 （２）Ｅ｛ＧＦ（ｐ）｝とベースポイントＢＰの提供を
受けた各ユーザは、任意の自然数を選定し、この自然数
回、前記ベースポイントＢＰをＥ｛ＧＦ（ｐ）｝上で加
算した値を求める。 （３）各ユーザは自分が任意に選択した自然数は秘密に
保持し、この一方、前記自然数回、ＢＰをＥ｛ＧＦ
（ｐ）｝上で加算した値は自己の公開鍵として通信を希
望する相手方のユーザに通知する。 （４）２人のユーザは、通知された公開鍵と乱数を使用
しての通信文を暗号化及び復号するに際して、公開鍵と
乱数と通信文の演算の内容の方法を取極める。 （５）公開鍵の通知を受けた他のユーザは、自分が選定
した乱数と相手方ユーザから通知されてきた公開鍵をも
とに、取極めに従って通信文を暗号化する。 （６）ユーザは暗号化した通信文を、公開鍵を知らせて
きたユーザに送信する。 （７）受信した他方のユーザは、取極めに従って秘密化
された通信文を復号する。この際、自分が選定し秘密に
保持している整数を使用する。 ここにＥ｛ＧＦ（ｐ）｝は以下のものである。正整数ｄ
を、虚二次体Ｑ｛（−ｄ）1/2 ｝の類数が小さくなるよ
うにとる。素数ｐを、ある整数ａに対して４×ｐ−ａ2
の素因数がｄ×平方数となりかつ、ｐ＋１−ａあるいは
ｐ＋１＋ａが３０桁以上の大きい素数で割れかつ、正整
数ｔ及び小さい正整数αに対して２t ±αと表せる素数
とする。楕円曲線Ｅは、ｄにより定まる類多項式Ｈ
d （ｘ）＝０のｐを法とした解をｊ不変数にもつ有限体
ＧＦ（ｐ）を定義体にもつ。 - 【請求項８】 請求項７において更に、 前記楕円曲線Ｅは有限体ＧＦ（ｐ）を定義体にもつ楕円
曲線ＥのＧＦ（ｐ）上の元で構成される群をＥ｛ＧＦ
（ｐ）｝とするとき、Ｅ｛ＧＦ（ｐ）｝の元の個数が３
０桁以上の大きな素数で割れる。 - 【請求項９】 請求項７若しくは請求項８において更
に、 正整数αは、２ｔ／３ビット以下の大きさとする。 - 【請求項１０】 請求項７若しくは請求項８若しくは請
求項９において更に、 ｐを素数、ｒを正整数とし、有限体ＧＦ（ｐr ）を定義
体にもつ楕円曲線ＥのＧＦ（ｐr ）上の元で構成される
群をＥ｛ＧＦ（ｐr ）｝とするとき、有限体ＧＦ
（ｐr ）を定義体に持つ楕円曲線Ｅ1,Ｅ2 ，・・・，Ｅ
n を、互いに同型ではないが元の個数が等しくなるよう
に構成し、各システムごと、各通信相手ごと、１システ
ムかつ同一通信相手で一定時期経過後ごとの少なくも一
により使用する楕円曲線を変える。 - 【請求項１１】 請求項７若しくは請求項８若しくは請
求項９若しくは請求項１０において更に、 楕円曲線Ｅは、ｄにより定まる類多項式Ｈd （ｘ）＝０
の次数をｎとし、ｐを法とした解をｊ1 、…、ｊn とす
るとき、これらの根をｊ不変数にもつ有限体ＧＦ（ｐ）
を定義体にもつ楕円曲線Ｅ1 、…、Ｅn である。 - 【請求項１２】 請求項７若しくは請求項８若しくは請
求項９若しくは請求項１０若しくは請求項１１において
更に、 通信文を共有鍵を使用して取極めに従って秘密化する際
及び復号する際の演算において、２t ≡α（mod n)若し
くは２t ≡−α（mod p)という性質及び加法鍵を使用す
る。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP13433994A JP3706398B2 (ja) | 1993-06-18 | 1994-06-16 | 楕円曲線による署名、認証及び秘密通信方式 |
Applications Claiming Priority (3)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| JP5-147334 | 1993-06-18 | ||
| JP14733493 | 1993-06-18 | ||
| JP13433994A JP3706398B2 (ja) | 1993-06-18 | 1994-06-16 | 楕円曲線による署名、認証及び秘密通信方式 |
Related Child Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP2003426428A Division JP2004139125A (ja) | 1993-06-18 | 2003-12-24 | 楕円曲線による署名、認証及び秘密通信方式 |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| JPH0798563A true JPH0798563A (ja) | 1995-04-11 |
| JP3706398B2 JP3706398B2 (ja) | 2005-10-12 |
Family
ID=26468471
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP13433994A Expired - Lifetime JP3706398B2 (ja) | 1993-06-18 | 1994-06-16 | 楕円曲線による署名、認証及び秘密通信方式 |
Country Status (1)
| Country | Link |
|---|---|
| JP (1) | JP3706398B2 (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JP2005284111A (ja) * | 2004-03-30 | 2005-10-13 | Japan Science & Technology Agency | 楕円曲線暗号の高速演算処理方法および装置 |
| US7431149B2 (en) | 2004-03-17 | 2008-10-07 | Sanki Engineering Co., Ltd. | Belt junction conveyor |
| JP2011253018A (ja) * | 2010-06-02 | 2011-12-15 | National Institute Of Advanced Industrial & Technology | 公開鍵暗号技術におけるドメインパラメータの生成 |
| JP2012518331A (ja) * | 2009-02-17 | 2012-08-09 | アルカテル−ルーセント | アイデンティティベースの認証鍵共有プロトコル |
-
1994
- 1994-06-16 JP JP13433994A patent/JP3706398B2/ja not_active Expired - Lifetime
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US7431149B2 (en) | 2004-03-17 | 2008-10-07 | Sanki Engineering Co., Ltd. | Belt junction conveyor |
| JP2005284111A (ja) * | 2004-03-30 | 2005-10-13 | Japan Science & Technology Agency | 楕円曲線暗号の高速演算処理方法および装置 |
| JP2012518331A (ja) * | 2009-02-17 | 2012-08-09 | アルカテル−ルーセント | アイデンティティベースの認証鍵共有プロトコル |
| US8510558B2 (en) | 2009-02-17 | 2013-08-13 | Alcatel Lucent | Identity based authenticated key agreement protocol |
| US9106410B2 (en) | 2009-02-17 | 2015-08-11 | Alcatel Lucent | Identity based authenticated key agreement protocol |
| JP2011253018A (ja) * | 2010-06-02 | 2011-12-15 | National Institute Of Advanced Industrial & Technology | 公開鍵暗号技術におけるドメインパラメータの生成 |
Also Published As
| Publication number | Publication date |
|---|---|
| JP3706398B2 (ja) | 2005-10-12 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US5497423A (en) | Method of implementing elliptic curve cryptosystems in digital signatures or verification and privacy communication | |
| KR101098701B1 (ko) | 암호체계의 설계를 위한 아이소지니의 사용 | |
| Paar et al. | Introduction to public-key cryptography | |
| US20080165955A1 (en) | Password protocols using xz-elliptic curve cryptography | |
| Gu et al. | New public key cryptosystems based on non‐Abelian factorization problems | |
| Vanstone et al. | Elliptic curve cryptosystems using curves of smooth order over the ring Z/sub n | |
| CN109756335A (zh) | 一种阶为梅森素数的有限域乘法群的公钥加密解密方法 | |
| Hwu et al. | An efficient identity-based cryptosystem for end-to-end mobile security | |
| Mittal et al. | A quantum secure ID-based cryptographic encryption based on group rings | |
| Mikhail et al. | Extension and application of El-Gamal encryption scheme | |
| US20050135610A1 (en) | Identifier-based signcryption | |
| Jeng et al. | An ECC-based blind signature scheme | |
| JP3706398B2 (ja) | 楕円曲線による署名、認証及び秘密通信方式 | |
| CN113872757B (zh) | 一种基于sm2公钥加密算法的广播加密方法 | |
| Lizama-Perez | Non-invertible key exchange protocol | |
| Heß et al. | The magic of elliptic curves and public-key cryptography | |
| Vagle | A gentle introduction to elliptic curve cryptography | |
| Bashir et al. | Cryptanalysis and improvement of an encryption scheme that uses elliptic curves over finite fields | |
| Karim | Cryptanalysis and Modification of Certificateless Blind Signature Scheme using Elliptic Curve Cryptography | |
| Mohapatra et al. | Signcryption schemes with forward secrecy based on elliptic curve cryptography | |
| JP2004139125A (ja) | 楕円曲線による署名、認証及び秘密通信方式 | |
| Dissanayake | Identification of Fake Messages Using Two PKCs | |
| Wang | A Review of Threshold Digital Signature Schemes | |
| Neelima et al. | Data Security Architecture in Cloud Computing based on Elliptic Curve Cryptography with Special Focus on Lowering the Cipher Space | |
| Zia et al. | Cryptanalysis and improvement of an encryption scheme that uses elliptic curves over finite fields |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20031224 |
|
| A911 | Transfer to examiner for re-examination before appeal (zenchi) |
Free format text: JAPANESE INTERMEDIATE CODE: A911 Effective date: 20040128 |
|
| A912 | Re-examination (zenchi) completed and case transferred to appeal board |
Free format text: JAPANESE INTERMEDIATE CODE: A912 Effective date: 20040319 |
|
| A521 | Request for written amendment filed |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20050622 |
|
| A61 | First payment of annual fees (during grant procedure) |
Free format text: JAPANESE INTERMEDIATE CODE: A61 Effective date: 20050729 |
|
| R150 | Certificate of patent or registration of utility model |
Free format text: JAPANESE INTERMEDIATE CODE: R150 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20080805 Year of fee payment: 3 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090805 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20090805 Year of fee payment: 4 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20100805 Year of fee payment: 5 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110805 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20110805 Year of fee payment: 6 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20120805 Year of fee payment: 7 |
|
| FPAY | Renewal fee payment (event date is renewal date of database) |
Free format text: PAYMENT UNTIL: 20130805 Year of fee payment: 8 |
|
| S533 | Written request for registration of change of name |
Free format text: JAPANESE INTERMEDIATE CODE: R313533 |
|
| R350 | Written notification of registration of transfer |
Free format text: JAPANESE INTERMEDIATE CODE: R350 |
|
| EXPY | Cancellation because of completion of term |