JP2004201124A

JP2004201124A - Public key ciphering method, signature method, cipher communication system, and computer program

Info

Publication number: JP2004201124A
Application number: JP2002368691A
Authority: JP
Inventors: Ryuichi Sakai; 隆一境; Masao Kasahara; 正雄笠原
Original assignee: Murata Machinery Ltd
Current assignee: Murata Machinery Ltd
Priority date: 2002-12-19
Filing date: 2002-12-19
Publication date: 2004-07-15
Anticipated expiration: 2022-12-19
Also published as: JP4485122B2

Abstract

<P>PROBLEM TO BE SOLVED: To provide a public key ciphering method capable of easily finding publicly opened information (public key) converted from ID information of an entity by substituting the ID information of the entity for a polynomial and to provide a signature method. <P>SOLUTION: A center 1 sets a polynomial function of a primary one or more, selects a point on an elliptic curve which can define pairing and publicly opens these information as a public key. In an entity V of a transmitting side, a function value obtained by substituting ID information u of an entity U of a receiving side and the selected point on the elliptic curve are used to prepare cipher texts C<SB>1</SB>and C<SB>2</SB>from a plaintext m. In the entity U, a secret key K<SB>U</SB>based on its own ID information u is used and pairing on the elliptic curve is utilized to decrypt the cipher texts C<SB>1</SB>and C<SB>2</SB>to the plaintext m. <P>COPYRIGHT: (C)2004,JPO&NCIPI

Description

【０００１】
【発明の属する技術分野】
本発明は、エンティティを特定する特定情報（以下、ＩＤ（Identity）情報という）を用いて暗号化処理及び復号処理を行う公開鍵暗号方法、エンティティのＩＤ情報を用いて署名データの作成処理及び検証処理を行う署名方法、この公開鍵暗号方法を利用した暗号通信システム、並びに、これらの方法をコンピュータに実行させるためのコンピュータプログラムに関する。
【０００２】
【従来の技術】
高度情報化社会と呼ばれる現代社会では、コンピュータネットワークを基盤として、ビジネス上の重要な文書・画像情報が電子的な情報という形で伝送通信されて処理される。このような電子情報は、容易に複写が可能である、複写物とオリジナルとの区別が困難であるという性質があり、情報保全の問題が重要視されている。特に、「コンピュータリソースの共有」，「マルチアクセス」，「広域化」の各要素を満たすコンピュータネットワークの実現が高度情報化社会の確立に不可欠であるが、これは当事者間の情報保全の問題とは矛盾する要素を含んでいる。このような矛盾を解消するための有効な手法として、人類の過去の歴史上主として軍事，外交面で用いられてきた暗号技術が注目されている。
【０００３】
暗号とは、情報の意味が当事者以外には理解できないように情報を交換することである。暗号において、誰でも理解できる元の文（平文）を第三者には意味がわからない文（暗号文）に変換することが暗号化であり、また、暗号文を平文に戻すことが復号であり、この暗号化と復号との全過程をまとめて暗号系と呼ぶ。暗号化の過程及び復号の過程には、それぞれ暗号化鍵及び復号鍵と呼ばれる秘密の情報が用いられる。復号時には秘密の復号鍵が必要であるので、この復号鍵を知っている者のみが暗号文を復号でき、暗号化によって情報の秘密性が維持され得る。
【０００４】
暗号化鍵と復号鍵とは、等しくても良いし、異なっていても良い。両者の鍵が等しい暗号系は、共通鍵暗号系と呼ばれ、米国商務省標準局が採用したＤＥＳ（Data Encryption Standards)はその典型例である。また、両者の鍵が異なる暗号系の一例として、公開鍵暗号系と呼ばれる暗号系が提案された。この公開鍵暗号系は、暗号系を利用する各エンティティが暗号化鍵と復号鍵とを一対ずつ作成し、暗号化鍵を公開鍵リストにて公開し、復号鍵のみを秘密に保持するという暗号系である。公開鍵暗号系では、この一対となる暗号化鍵と復号鍵とが異なり、一方向性関数を利用することによって暗号化鍵から復号鍵を割り出せないという特徴を持たせている。
【０００５】
公開鍵暗号系は、暗号化鍵を公開するという画期的な暗号系であって、高度情報化社会の確立に必要な上述した３つの要素に適合するものであり、情報通信技術の分野等での利用を図るべく、その研究が活発に行われ、典型的な公開鍵暗号系としてＲＳＡ暗号系が提案された。このＲＳＡ暗号系は、一方向性関数として素因数分解の困難さを利用して実現されている。また、離散対数問題を解くことの困難さ（離散対数問題）を利用した公開鍵暗号系も種々の手法が提案されてきた。
【０００６】
また、各エンティティの住所，氏名，電子メールのアドレス等の個人を特定するＩＤ情報を利用する暗号系が提案された。この暗号系では、ＩＤ情報に基づいて送受信エンティティ間で共通の暗号化・復号鍵を生成する。また、このＩＤ情報に基づく暗号技法には、（１）暗号文通信に先立って送受信エンティティ間での予備通信を必要とする方式と、（２）暗号文通信に先立って送受信エンティティ間での予備通信を必要としない方式とがある。特に、（２）の手法は予備通信が不要であるので、エンティティの利便性が高く、将来の暗号系の中枢をなすものと考えられている。
【０００７】
この（２）の手法による暗号系は、ＩＤ−ＮＩＫＳ（ID-based non-interactive key sharing scheme)と呼ばれており、通信相手のＩＤ情報を用いて予備通信を行うことなく暗号化・復号鍵を共有する方式を採用している。ＩＤ−ＮＩＫＳは、送受信エンティティ間で公開鍵，秘密鍵を交換する必要がなく、また鍵のリスト及び第三者によるサービスも必要としない方式であり、任意のエンティティ間で安全に通信を行える。
【０００８】
上述した公開鍵暗号系では、例えばＲＳＡ暗号系の場合にその公開鍵の長さは現在の電話番号の十数倍となり、極めて煩雑である。これに対して、ＩＤ−ＮＩＫＳでは、各ＩＤ情報を名簿という形式で登録しておけば、この名簿を参照して任意のエンティティとの間で共通鍵を生成することができる。従って、ＩＤ−ＮＩＫＳのシステムが安全に実現されれば、多数のエンティティが加入するコンピュータネットワーク上で便利な暗号系を構築できる。このような理由により、ＩＤ−ＮＩＫＳが将来の暗号系の中心になると期待されている。
【０００９】
そこで、本発明者等は、各エンティティのＩＤ情報を使用して、楕円曲線上のペアリングに基づいて予備通信を行うことなく両エンティティ間で容易に共通鍵を共有し合える鍵共有方法、この鍵共有方法を用いた暗号通信システムを提案している（例えば、特許文献１参照）。
【００１０】
【特許文献１】
特開２００２−２６８９２号公報
【００１１】
【発明が解決しようとする課題】
本発明者等は、特許文献１のような鍵共有方式（ＩＤ−ＮＩＫＳ）を提案した後も、楕円曲線上のペアリングを用いた各エンティティのＩＤ情報に基づく公開鍵暗号方式及び署名方式の研究を続けている。
【００１２】
本発明は斯かる事情に鑑みてなされたものであり、多項式にエンティティのＩＤ情報を代入することにより、エンティティのＩＤ情報から変換される公開情報（公開鍵）を容易に求めることができる公開鍵暗号方法及び署名方法、その公開鍵暗号方法を利用した暗号通信システム、並びに、これらの方法をコンピュータに実行させるためのコンピュータプログラムを提供することを目的とする。
【００１３】
本発明の他の目的は、グループのＩＤ情報及びグループに属する複数のエンティティ夫々のＩＤ情報を使用することにより、グループに対する暗号文または署名データとそのグループに属する複数のエンティティ夫々に対する暗号文または署名データとを独立的に容易に作成できる公開鍵暗号方法または署名方法を提供することにある。
【００１４】
【課題を解決するための手段】
請求項１に係る公開鍵暗号方法は、暗号文を受信するエンティティを特定する特定情報に基づく公開鍵を使用して暗号文を作成する公開鍵暗号方法において、多項式に前記特定情報を代入して得られる結果とペアリングを定義できる代数曲線上の点とを使用して前記暗号文を作成することを特徴とする。
【００１５】
請求項２に係る公開鍵暗号方法は、暗号文を受信するエンティティを特定する特定情報に基づく公開鍵を使用して暗号文を作成する公開鍵暗号方法において、多項式関数を設定し、ペアリングを定義できる代数曲線上の点を選択し、設定した前記多項式関数に前記特定情報を代入して得られる関数値と選択した前記点とを使用して前記暗号文を作成することを特徴とする。
【００１６】
請求項３に係る公開鍵暗号方法は、複数のエンティティが属するグループについて、該グループに対する暗号文及び前記複数のエンティティ夫々に対する暗号文を独立的に作成する公開鍵暗号方法において、前記グループを特定する特定情報及び前記複数のエンティティ夫々を特定する特定情報を使用することを特徴とする。
【００１７】
請求項４に係る署名方法は、第１のエンティティにて作成する署名データを第２のエンティティにて検証する署名方法において、前記第１のエンティティを特定する特定情報を多項式に代入して得られる結果とペアリングを定義できる代数曲線上の点とを使用して前記署名データの作成・検証を行うことを特徴とする。
【００１８】
請求項５に係る署名方法は、第１のエンティティにて作成する署名データを第２のエンティティにて検証する署名方法において、多項式関数を設定し、ペアリングを定義できる代数曲線上の点を選択し、設定した前記多項式関数に前記第１のエンティティを特定する特定情報を代入して得られる関数値と選択した前記点とを使用して前記署名データの作成・検証を行うことを特徴とする。
【００１９】
請求項６に係る署名方法は、複数のエンティティが属するグループについて、前記グループに属するエンティティにて作成する署名データを前記グループに属する他のエンティティまたは前記グループに属しないエンティティにて検証する署名方法において、前記グループを特定する特定情報及び前記署名データを作成する前記エンティティを特定する特定情報を使用することを特徴とする。
【００２０】
請求項７に係る暗号通信システムは、送信すべき情報である平文を暗号文に暗号化する暗号化処理、及び、送信された暗号文を平文に復号する復号処理を、複数のエンティティ間で相互に行う暗号通信システムにおいて、公開鍵と各エンティティを特定する特定情報に基づく各エンティティの秘密鍵とを生成するセンタと、送信対象のエンティティの特定情報に基づく公開鍵を用いて前記暗号化処理を行うと共に、自身の秘密鍵を用いて前記復号処理を行う複数のエンティティとを有しており、前記センタにて、多項式関数を設定すると共にペアリングを定義できる代数曲線上の点を選択し、各エンティティにて、設定した前記多項式関数に前記特定情報を代入して得られる関数値と選択した前記点とを使用して前記暗号文を作成するようにしたことを特徴とする。
【００２１】
請求項８に係るコンピュータプログラムは、コンピュータに、公開鍵暗号方式また署名方式に用いる公開鍵及び秘密鍵を生成させるためのコンピュータプログラムにおいて、コンピュータに、多項式関数を設定させるステップと、コンピュータに、ペアリングを定義できる代数曲線上の点を選択させるステップとを有することを特徴とする。
【００２２】
請求項９に係るコンピュータプログラムは、コンピュータに、暗号文を受信するエンティティを特定する特定情報に基づく公開鍵を使用して暗号文を作成させるためのコンピュータプログラムにおいて、コンピュータに、多項式関数及びペアリングを定義できる代数曲線上の点を入力させるステップと、コンピュータに、前記多項式関数に前記特定情報を代入して関数値を得させるステップと、コンピュータに、得た関数値と前記点とを使用して前記暗号文を作成させるステップとを有することを特徴とする。
【００２３】
請求項１０に係るコンピュータプログラムは、コンピュータに、署名データを作成するエンティティを特定する特定情報を用いて前記署名データを作成させるためのコンピュータプログラムにおいて、コンピュータに、多項式関数及びペアリングを定義できる代数曲線上の点を入力させるステップと、コンピュータに、前記多項式関数に前記特定情報を代入して関数値を得させるステップと、コンピュータに、得た関数値と前記点とを使用して前記署名データを作成させるステップとを有することを特徴とする。
【００２４】
本発明の公開鍵暗号方法にあっては、多項式関数が設定されると共にペアリングを定義できる代数曲線上の点が選択され、暗号文を受信するエンティティのＩＤ情報がその多項式関数に代入されて得られる関数値と代数曲線上の選択した点とを使用して暗号文が作成される。よって、エンティティのＩＤ情報から代数曲線を用いて変換される公開鍵がより容易に求められる。
【００２５】
本発明の署名方法にあっては、多項式関数が設定されると共にペアリングを定義できる代数曲線上の点が選択され、署名データを作成するエンティティのＩＤ情報がその多項式関数に代入されて得られる関数値と代数曲線上の選択した点とを使用して署名データが作成される。よって、エンティティのＩＤ情報から代数曲線を用いて変換される公開鍵がより容易に求められる。
【００２６】
本発明の公開鍵暗号方法または署名方法にあっては、グループのＩＤ情報及びグループに属する複数のエンティティ夫々のＩＤ情報が使用されて、グループに対する暗号文または署名データとそのグループに属する複数のエンティティ夫々に対する暗号文または署名データとが独立的に作成される。よって、これらの暗号文または署名データが容易に作成される。
【００２７】
【発明の実施の形態】
本発明の実施の形態について具体的に説明する。
まず、本発明で用いる楕円曲線のベイユペアリングの基本的性質を述べる。有限体ベクトルＦ_q上で定義された楕円曲線をＥ／ベクトルＦ_qで表し、この楕円曲線をＥ／ベクトルＦ_qのベクトルＦ_q上で有理点がなす群をＥ（ベクトルＦ_q）と表す。ここでは、この楕円曲線の群Ｅ（ベクトルＦ_q）の部分群にｎねじれ部分群Ｅ［ｎ］が含まれるものとする。
【００２８】
楕円曲線上のペアリングは、楕円曲線上の二つのｎねじれ点Ｐ，Ｑ∈Ｅ［ｎ］からベクトルＦ_q上の位数ｎの乗法群への写像である。ペアリングには、以下に示すような性質が存在する。なお、ｅ_n（，）はペアリングを表す。
【００２９】
（非退化）
ある点Ｐ∈Ｅ［ｎ］と任意の点Ｑ∈Ｅ［ｎ］とに対して、
ｅ_n（Ｐ，Ｑ）＝１が成立するとき、Ｐ＝０である。
（反対称）
任意の点Ｐ，Ｑ∈Ｅ［ｎ］に対して、
ｅ_n（Ｐ，Ｑ）＝ｅ_n（Ｑ，Ｐ）^-1が成立する。
（双線形）
任意の点Ｐ，Ｑ，Ｒ∈Ｅ［ｎ］に対して、
ｅ_n（Ｐ＋Ｑ，Ｒ）＝ｅ_n（Ｐ，Ｒ）ｅ_n（Ｑ，Ｒ），
ｅ_n（Ｐ，Ｑ＋Ｒ）＝ｅ_n（Ｐ，Ｑ）ｅ_n（Ｐ，Ｒ）
が成立する。
【００３０】
楕円曲線上のペアリングを暗号方式に適用する場合、十分な安全性を確保するために、利用する楕円曲線とそのｎねじれ部分群とを以下の条件を満たすように選ぶ必要がある。
（１）ｎは１６０ビット以上の素数を因数に持つ。
（２）ｑは２¹⁰²⁴以上である。
（３）ベクトルＦ_qの部分体について次の条件を満たす。
【００３１】
【数１】

【００３２】
以下の説明では、これらの（１）〜（３）の条件を満たす楕円曲線を、ペアリングの計算が可能な安全な楕円曲線と称する。また、以下では簡単のためにｎを素数とする。
【００３３】
（第１実施の形態：ＩＤ情報に基づく公開鍵暗号方法）
図１は、本発明の暗号通信システムの構成を示す模式図である。情報の隠匿を信頼できるセンタ１が設定されており、このセンタ１としては、例えば社会の公的機関を該当できる。このセンタ１と、この暗号通信システムを利用するユーザとしての複数の各エンティティＡ，Ｂ，…，Ｚとは、秘密通信路２ａ，２ｂ，…，２ｚにより接続されており、これらの秘密通信路２ａ，２ｂ，…，２ｚを介してセンタ１から秘密の鍵情報（秘密鍵Ｋ_A，Ｋ_B，…，Ｋ_Z）が各エンティティＡ，Ｂ，…，Ｚへ配布されるようになっている。また、二つのエンティティの間には通信路３ab，３az，３bz，…が設けられており、この通信路３ab，３az，３bz，…を介して通信情報を暗号化した暗号文が互いのエンティティ間で伝送されるようになっている。
【００３４】
次に、暗号通信システムにおけるエンティティ間の情報通信について説明する。図２は、二つのエンティティＶ，Ｕ間における情報の通信状態を示す模式図である。図２の例は、エンティティＶで平文（メッセージ）ｍを暗号文Ｃ₁，Ｃ₂に暗号化してそれをエンティティＵへ伝送し、エンティティＵでその暗号文Ｃ₁，Ｃ₂を元の平文（メッセージ）ｍに復号する場合を示している。なお、エンティティとしては、人間、装置、機械、プログラム、または、それらを構成要素としたシステムなど多様なものがあり、これらの何れの間であっても、本発明は適用可能である。
【００３５】
センタ１は、公開情報であるベクトルＨを含む各種の公開鍵を生成する公開鍵生成部１ａと、各エンティティＶ，Ｕの秘密鍵Ｋ_V，Ｋ_Uを求める秘密鍵生成部１ｂと、生成した秘密鍵Ｋ_V，Ｋ_Uを各エンティティＶ，Ｕへ配布する秘密鍵配布部１ｃとを備えている。
【００３６】
送信側であるエンティティＶの暗号化装置１０は、センタ１から秘密鍵Ｋ_Vを受け取る秘密鍵受取部１１と、乱数ｒを生成する乱数生成部１２と、平文ｍを暗号文Ｃ₁，Ｃ₂に暗号化する暗号化部１３と、作成した暗号文Ｃ₁，Ｃ₂を通信路５０へ送り出す暗号文送出部１４とを備えている。
【００３７】
また、送信側であるエンティティＵの復号装置２０は、センタ１から秘密鍵Ｋ_Uを受け取る秘密鍵受取部２１と、通信路５０から暗号文Ｃ₁，Ｃ₂を受け取る暗号文受取部２２と、暗号文Ｃ₁，Ｃ₂を平文ｍに復号する復号部２３と、復号した平文ｍを出力する平文出力部２４とを備えている。
【００３８】
次に、動作について説明する。図３はセンタ１での処理の動作手順を示すフローチャート、図４はエンティティＶ（送信側）での暗号化処理の動作手順を示すフローチャート、図５はエンティティＵ（受信側）での復号処理の動作手順を示すフローチャートである。
【００３９】
まず、センタ１において、ペアリングが計算可能な安全な楕円曲線が生成され（ステップＳ１）、ｎねじれ点ＰとＱとがランダムに選ばれる（ステップＳ２）。但し、ｅ_n（Ｐ，Ｑ）≠１とならないように、点Ｐ，Ｑが選択される。次いで、下記式（１）に示すようなｄ次の多項式関数ｆ（ｘ）が生成される（ステップＳ３）。なお、式（１）において、最高次の係数ａ_dは１で良く、また、ｄ＝１つまり一次式であっても良い。
ｆ（ｘ）＝ａ_dｘ^d＋ａ_d-1ｘ^d-1＋・・・＋ａ₁ｘ＋ａ₀ …（１）
【００４０】
センタ１において、下記式（２）に示すようなベクトルＨが計算され、そのベクトルＨが公開情報として公開される（ステップＳ４）。また、エンティティＶ，ＵのＩＤ情報ｖ，ｕを用いて、秘密鍵Ｋ_V，Ｋ_Uが下記式（３），（４）に示すように生成されて（ステップＳ５）、各エンティティＶ，Ｕへ配布される（ステップＳ６）。
【００４１】
【数２】

【００４２】
エンティティＶでは、乱数ｒが乱数生成部１２にて生成され（ステップＳ１１）、エンティティＵのＩＤ情報ｕとセンタ１の公開情報ベクトルＨと乱数ｒとを用いて、下記式（５），（６）に示すように平文ｍから暗号文Ｃ₁，Ｃ₂が暗号化部１３にて作成される（ステップＳ１２，１３）。なお、式（６）における演算記号は、例えば公開鍵暗号でのビット毎のＥＸＯＲ（排他的論理和）を表す．
【００４３】
【数３】

【００４４】
なお、上記暗号文Ｃ₂におけるｅ_n（Ｐ，Ｑ）は、エンティティＶのＩＤ情報ｖとエンティティＶの秘密鍵Ｋ_Vとセンタ１の公開情報ベクトルＨとを用いて、以下のように算出できる。
【００４５】
【数４】

【００４６】
作成された暗号文Ｃ₁，Ｃ₂は、暗号文送出部１４から通信路５０を介してエンティティＵへ伝送される（ステップＳ１４）。
【００４７】
通信路５０を伝送された暗号文Ｃ₁，Ｃ₂は、エンティティＵの暗号文受取部２２で受け取られる（ステップＳ２１）。エンティティＵでは、復号部２３において、自身の秘密鍵Ｋ_Uを用いて、下記式（７）に示すように暗号文Ｃ₁，Ｃ₂が平文ｍに復号される（ステップＳ２２）。
【００４８】
【数５】

【００４９】
以上のようにして、比較的簡単なアルゴリズムによって、暗号文により情報通信を安全に行える。
【００５０】
なお、上述した第１実施の形態では、エンティティＶ（送信側）がセンタ１に登録されており、自身の秘密鍵Ｋ_Vを利用してｅ_n（Ｐ，Ｑ）を求めるようにしたが、このｅ_n（Ｐ，Ｑ）がセンタ１からの公開情報として公開されている場合には、エンティティＶ（送信側）はセンタ１に登録されていなくても暗号文を作成することができる。
【００５１】
（第２実施の形態：ＩＤ情報に基づく署名方法）
次に、第１実施の形態で説明した公開鍵暗号方式と同様の手法を用いる、ＩＤ情報に基づく署名方式について説明する。
【００５２】
図６は、二つのエンティティＵ，Ｖ間における署名システムを示す模式図である。図６の例は、エンティティＵが署名データを作成し、エンティティＶがその署名データを検証する場合を示している。
【００５３】
センタ１は、第１実施の形態と同様の公開鍵生成部１ａ，秘密鍵生成部１ｂ及び秘密鍵配布部１ｃを備えている。
【００５４】
署名側であるエンティティＵの署名装置３０は、センタ１から秘密鍵Ｋ_Uを受け取る秘密鍵受取部３１と、乱数を生成する乱数生成部３２と、各種の公開鍵と自身のＩＤ情報ｕと自身の秘密鍵Ｋ_Uとを用いて署名データを作成する署名データ作成部３３とを備えている。また、検証側であるエンティティＶの検証装置４０は、センタ１から秘密鍵Ｋ_Vを受け取る秘密鍵受取部４１と、エンティティＵからの署名データを検証する署名データ検証部４２とを備えている。
【００５５】
次に、動作について説明する。図７はセンタ１での処理の動作手順を示すフローチャート、図８は署名データを作成するエンティティＵ（署名側）での署名処理の動作手順を示すフローチャート、図９は署名データを検証するエンティティＶ（検証側）での検証処理の動作手順を示すフローチャートである。
【００５６】
まず、センタ１において、第１実施の形態と同様に、ペアリングが計算可能な安全な楕円曲線が生成され（ステップＳ３１）、ｎねじれ点ＰとＱとがランダムに選ばれる（ステップＳ３２）。次いで、上記式（１）に示すようなｄ次の多項式関数ｆ（ｘ）が生成される（ステップＳ３３）。各種（後述する各手法によって異なる）の公開鍵が公開情報として公開される（ステップＳ３４）。また、エンティティＵ，ＶのＩＤ情報ｕ，ｖを用いて、秘密鍵Ｋ_U，Ｋ_Vが前記式（４），（３）に示すように生成されて（ステップＳ３５）、各エンティティＵ，Ｖへ配布される（ステップＳ３６）。
【００５７】
エンティティＵでは、乱数ｋが乱数生成部３２にて生成され（ステップＳ４１）、エンティティＵのＩＤ情報ｕ及び秘密鍵Ｋ_Uと各種の公開鍵（公開情報）と乱数ｋとを用いて、署名データ作成部３３にて署名データが作成される（ステップＳ４２）。作成された署名データは、エンティティＶへ送られる（ステップＳ４３）。
【００５８】
作成された署名データは、エンティティＶで受け取られ（ステップＳ５１）、署名データ検証部４２において、自身及びエンティティＵのＩＤ情報ｖ及びｕと自身の秘密鍵Ｋ_Vと各種の公開鍵（公開情報）とを用いて、その署名データが検証される（ステップＳ５２）。
【００５９】
次に、本発明の署名方法の具体例（第１例〜第６例）について説明する。署名方式の代表的な型として、ElGamal 型とSchnorr 型とが知られており、以下ではこれらの型を中心にして説明する。
【００６０】
〔第１例〕（ElGamal 型のＩ）
第１実施の形態でのセンタ１における公開鍵に、Ｐ∈Ｅ［ｎ］を追加する。センタの公開鍵ベクトルＨと任意のエンティティＣのＩＤ情報ｃとから、下記式（８）のようにｆ（ｃ）Ｑを計算することができる。更に、自身の秘密鍵Ｋ_Cを用いてエンティティＣは下記式（９）のようにｅ_n（Ｐ，Ｑ）を計算することが可能である。つまり、自身の秘密鍵を持っている任意のエンティティはｅ_n（Ｐ，Ｑ）を計算できる。
【００６１】
【数６】

【００６２】
具体的な署名及び検証は以下のように行う。なお、センタ１は、一方向性関数であるハッシュ関数ｈ（・）を公開鍵として公開する。
【００６３】
署名：（署名データ（Ｒ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され（Ｓ４１）、下記式（10），（11）のように署名データ（Ｒ，Ｓ）が作成される（Ｓ４２）。作成された署名データ（Ｒ，Ｓ）がエンティティＶへ送られる（Ｓ４３）。但し、ｘはＲのｘ座標を表す。
【００６４】
【数７】

【００６５】
検証：エンティティＶにおいて、署名データ（Ｒ，Ｓ）が受け取られ（Ｓ５１）、下記式（12）に示すｖ₁と下記式（13）に示すｖ₂とが等しいことが確かめられて、署名データの検証が行われる（Ｓ５２）。
【００６６】
【数８】

【００６７】
〔第２例〕（Schnorr 型のＩ）
第１実施の形態でのセンタ１における公開鍵に、Ｐ∈Ｅ［ｎ］を追加する。具体的な署名及び検証は以下のように行う。なお、センタ１は、ハッシュ関数ｈ（・）を公開鍵として公開する。
【００６８】
署名：（署名データ（ｅ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され（Ｓ４１）、下記式（14）のような中間データｒが計算された後、下記式（15），（16）のように署名データ（ｅ，Ｓ）が作成される（Ｓ４２）。なお、署名データｅは、式（15）で示す如く、平文ｍと中間データｒとの連接のハッシュ値として求められる。作成された署名データ（ｅ，Ｓ）がエンティティＶへ送られる（Ｓ４３）。
【００６９】
【数９】

【００７０】
検証：エンティティＶにおいて、署名データ（ｅ，Ｓ）が受け取られ（Ｓ５１）、下記式（17），（18）の成立が確かめられて、署名データの検証が行われる（Ｓ５２）。
【００７１】
【数１０】

【００７２】
〔第３例〕（ElGamal 型のII）
この第３例の方式では、Ｐを用いないので、このＰをセンタ１の秘密情報として使用することができる。具体的な署名及び検証は以下のように行う。なお、センタ１は、ハッシュ関数ｈ（・）を公開鍵として公開する。
【００７３】
署名：（署名データ（ベクトルＲ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され（Ｓ４１）、下記式（19），（20）のように署名データ（ベクトルＲ，Ｓ）が作成される（Ｓ４２）。作成された署名データ（ベクトルＲ，Ｓ）がエンティティＶへ送られる（Ｓ４３）。但し、ｘはｋＨ₀のｘ座標を表す。
【００７４】
【数１１】

【００７５】
検証：エンティティＶにおいて、署名データ（ベクトルＲ，Ｓ）が受け取られ（Ｓ５１）、以下の関係の成立が確かめられて、署名データの検証が行われる（Ｓ５２）。まず、ベクトルＲより下記式（21）のようにｋｆ（ｖ）Ｑが求められ、次に、下記式（22），（23），（24）のようにｗ₁，ｗ₂，ｗ₃が得られる。そして、下記式（25）の成立により、署名データ（ベクトルＲ，Ｓ）の正当性が検証される。
【００７６】
【数１２】

【００７７】
〔第４例〕（Schnorr 型のII）
この第４例の方式では、第３例と同様、Ｐを用いないので、このＰをセンタ１の秘密情報として使用することができる。具体的な署名及び検証は以下のように行う。なお、センタ１は、ハッシュ関数ｈ（・）を公開鍵として公開する。
【００７８】
署名：（署名データ（ｅ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され（Ｓ４１）、下記式（26）のような中間データｒが計算された後、下記式（27），（28）のように署名データ（ｅ，Ｓ）が作成される（Ｓ４２）。作成された署名データ（ｅ，Ｓ）がエンティティＶへ送られる（Ｓ４３）。
【００７９】
【数１３】

【００８０】
検証：エンティティＶにおいて、署名データ（ｅ，Ｓ）が受け取られ（Ｓ５１）、以下のようにして、署名データの検証が行われる（Ｓ５２）。まず、下記式（29）に従ってｗが求められ、次に、下記式（30）が成立することにより、署名データ（ｅ，Ｓ）と平文ｍとの正当性が検証される。
【００８１】
【数１４】

【００８２】
〔第５例〕（ElGamal 型のIII)
この第５例の方式では、Ｐをセンタ１の公開鍵とする。この方式の特徴は、署名データの検証時に必ず自身の秘密鍵を必要とする点にある。具体的な署名及び検証は以下のように行う。なお、センタ１は、ハッシュ関数ｈ（・）を公開鍵として公開する。
【００８３】
署名：（署名データ（ベクトルＲ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され（Ｓ４１）、下記式（31），（32）のように署名データ（ベクトルＲ，Ｓ）が作成される（Ｓ４２）。作成された署名データ（ベクトルＲ，Ｓ）がエンティティＶへ送られる（Ｓ４３）。但し、ｘはｋＨ₀のｘ座標を表す。
【００８４】
【数１５】

【００８５】
検証：エンティティＶにおいて、署名データ（ベクトルＲ，Ｓ）が受け取られ（Ｓ５１）、以下の関係の成立が確かめられて、署名データの検証が行われる（Ｓ５２）。下記式（33），（34），（35）のようにｗ₁，ｗ₂，ｗ₃が計算された後、下記式（36）の成立により、署名データ（ベクトルＲ，Ｓ）の正当性が検証される。
【００８６】
【数１６】

【００８７】
〔第６例〕（その他の型）
この第６例の方式での具体的な署名及び検証は以下のように行う。なお、センタ１は、ハッシュ関数ｈ（・）を公開鍵として公開する。
【００８８】
署名：エンティティＵにおいて、乱数ｋ，ｒ∈Ｚ_nが生成され（Ｓ４１）、ハッシュ関数ｈ（・）を用いて平文ｍに対応する楕円曲線上のｎねじれ点Ｍ＝ｈ（ｍ）が計算される。そして、平文ｍに対する署名データ（Ｓ₁，Ｓ₂，ベクトルＳ₃）が、エンティティＵの秘密鍵Ｐ_U（エンティティＵのＩＤ情報ｕを楕円曲線上のｎねじれ点Ｐに写像したもの）と、センタの公開情報ｈ（・），ベクトルＨとを用いて、下記式（37），（38），（39）のように作成される（Ｓ４２）。作成された署名データ（Ｓ₁，Ｓ₂，ベクトルＳ₃）がエンティティＶへ送られる（Ｓ４３）。
【００８９】
【数１７】

【００９０】
検証：エンティティＶにおいて、署名データ（Ｓ₁，Ｓ₂，ベクトルＳ₃）が受け取られ（Ｓ５１）、平文ｍからＭ＝ｈ（ｍ）が得られた後、エンティティＶの秘密鍵Ｐ_Vを用いて、下記式（40）の成立が確かめられて、署名データの検証が行われる（Ｓ５２）。
【００９１】
【数１８】

【００９２】
なお、上述した第２実施の形態では、エンティティＶ（検証側）がセンタ１に登録されており、自身の秘密鍵Ｋ_Vを利用してｅ_n（Ｐ，Ｑ）を求めるようにしたが、このｅ_n（Ｐ，Ｑ）がセンタ１からの公開情報として公開されている場合には、エンティティＶ（検証側）はセンタ１に登録されていなくても署名データの検証を行うことができる。
【００９３】
（第３実施の形態）
次に、第２実施の形態とは異なる秘密鍵及び公開鍵を使用する第３実施の形態の署名方法について、ElGamal 型（第７例）とSchnorr 型（第８例）とを例として説明する。なお、第３実施の形態における署名装置及び検証装置の構成、並びに、センタ処理，署名処理及び検証処理の動作手順は、第２実施の形態（図６〜図９）と同様であるのでそれらの説明は省略する。
【００９４】
〔第７例〕（ElGamal 型）
準備：信頼がおけるセンタにて、ペアリングの計算が可能な安全な楕円曲線が生成され、エンティティＵ（署名側）のＩＤ情報ｕがその楕円曲線上のｎねじれ点Ｐ_Uに変換されると共に、ハッシュ関数ｈ（・）が公開される。また、センタにて、秘密鍵ｙ∈Ｚ_nが生成され、ｎねじれ点Ｑ∈Ｅ［ｎ］を用いて、Ｑ，ｙＱが計算されて公開される。更に、センタにて、エンティティＵのＩＤ情報ｕからエンティティＵの秘密鍵Ｋ_U＝ｙＰ_Uが計算されて、この秘密鍵Ｋ_UがエンティティＵへ送られる。
【００９５】
署名：（署名データ（Ｒ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され、下記式（41），（42）のように署名データ（Ｒ，Ｓ）が作成される。作成された署名データ（Ｒ，Ｓ）がエンティティＶへ送られる。但し、ｘはＲのｘ座標である。
【００９６】
【数１９】

【００９７】
検証：エンティティＶにおいて、署名データ（Ｒ，Ｓ）が受け取られ、下記式（43）の成立が確かめられて、署名データの検証が行われる。
【００９８】
【数２０】

【００９９】
〔第８例〕（Schnorr 型）
準備：センタにおける準備処理は、第７例と同様である。
【０１００】
署名：（署名データ（ｅ，Ｓ））エンティティＵにおいて、乱数ｋ∈Ｚ_nが生成され、下記式（44）のような中間データｒが計算された後、下記式（45），（46）のように署名データ（ｅ，Ｓ）が作成される。作成された署名データ（ｅ，Ｓ）がエンティティＶへ送られる。
【０１０１】
【数２１】

【０１０２】
検証：エンティティＶにおいて、署名データ（ｅ，Ｓ）が受け取られ、下記式（47），（48）の成立が確かめられて、署名データの検証が行われる。
【０１０３】
【数２２】

【０１０４】
（第４実施の形態）
次に、複数のエンティティにて構成されるグループを考慮した公開鍵暗号方法及び署名方法について説明する。なお、第４実施の形態の公開鍵暗号方法における暗号化装置及び復号装置の構成、並びに、センタ処理，暗号化処理及び復号処理の動作手順は、第１実施の形態（図２〜図５）と同様であり、また、第４実施の形態の署名方法における署名装置及び検証装置の構成、並びに、センタ処理，署名処理及び検証処理の動作手順は、第２実施の形態（図６〜図９）と同様であるので、それらの説明は省略する。
【０１０５】
第４実施の形態にあっては、第１，第２実施の形態で述べたようなセンタ秘密の多項式関数を、各エンティティ用とグループ用との２組生成する。具体的には、下記式（49）に示すような各エンティティ用のｄ次の多項式関数ｆ（ｘ）（上記式（１）と同様）と、下記式（50）に示すようなグループ用のｚ次の多項式関数ｔ（ｘ）とが生成される。
ｆ（ｘ）＝ａ_dｘ^d＋ａ_d-1ｘ^d-1＋・・・＋ａ₁ｘ＋ａ₀ …（49）
ｔ（ｘ）＝ｂ_zｘ^z＋ｂ_z-1ｘ^z-1＋・・・＋ｂ₁ｘ＋ｂ₀ …（50）
【０１０６】
エンティティＵがグループＧに属しているとする。また、エンティティＵのＩＤ情報をｕ、グループＧのＩＤ情報をｇとする。この場合、エンティティＵの秘密鍵Ｋ_UGは下記式（51）で与えられ、センタで計算される。また、センタが公開する公開情報としてのグループＧの公開鍵は下記式（52）で与えられ、エンティティＵのための情報（公開する必要はない）は下記式（53）で与えられ、何れもセンタで計算される。
【０１０７】
【数２３】

【０１０８】
以下、公開鍵暗号方法（第９例及び第１０例）並びに署名方法（第１１例〜第１４例）の具体例について説明する。
【０１０９】
〔第９例〕（ＩＤ情報に基づくグループへの公開鍵暗号方法）
グループＧに属するエンティティであれば、誰でも復号可能であるグループＧへの公開鍵暗号方法について説明する。この例は、一つのグループＧに属する全てのエンティティへ同じ暗号文を送付する場合に好適である。
【０１１０】
暗号化：送信エンティティ（送信側）において、乱数ｒ∈Ｚ_nが生成され、グループＧへの暗号文として下記式（54），（55）のようなＣ_i，Ｃ_d+1が作成される。ｅ_n（Ｐ，Ｑ）は、送信エンティティのＩＤ情報及び秘密鍵とセンタの公開情報とから計算することができる。
【０１１１】
【数２４】

【０１１２】
復号：グループＧに属する任意のエンティティＵ（受信側）において、下記式（56）に従って、暗号文Ｃ_i，Ｃ_d+1から平文ｍが復号される。
【０１１３】
【数２５】

【０１１４】
〔第１０例〕（ＩＤ情報に基づく各エンティティへの公開鍵暗号方法）
第９例と同様の秘密鍵及び公開鍵を用いて、グループＧに属する特定のエンティティＵへ暗号文を送付する例について説明する。グループＧに属するエンティティＵ（受信側）への暗号化及びエンティティＵでの復号は、第１実施の形態と同様に行うことができる。
【０１１５】
暗号化：送信エンティティ（送信側）において、乱数ｒ∈Ｚ_nが生成され、エンティティＵへの暗号文として下記式（57），（58）のようなＣ₁，Ｃ₂が作成される。
【０１１６】
【数２６】

【０１１７】
復号：エンティティＵ側において、下記式（59）に従って、暗号文Ｃ₁，Ｃ₂から平文ｍが復号される。
【０１１８】
【数２７】

【０１１９】
〔第１１例〕（ＩＤ情報に基づくグループ署名方法：Schnorr 型）
署名データからは、グループ内のどのエンティティが署名したかは特定できないが、そのグループに属するエンティティが署名したということを検証できる署名方法について説明する。
【０１２０】
署名：エンティティＵ（署名側）において、乱数ｋ∈Ｚ_nが生成され、下記式（60）のような中間データｒが計算された後、下記式（61），（62）のようにグループＧの署名データ（ｅ，Ｓ_i）が作成される。ｅ_n（Ｐ，Ｑ）は、エンティティＵのＩＤ情報及び秘密鍵とセンタの公開情報とから計算することができる。
【０１２１】
【数２８】

【０１２２】
検証：グループＧ′に属する任意のエンティティＶ（検証側）において、まず、下記式（63），（64）に従ってｅ_n（Ｐ，Ｑ），ｗが求められ、次に、下記式（65）により、署名データ（ｅ，Ｓ_i）の正当性が検証される。
【０１２３】
【数２９】

【０１２４】
第１１例は、下記式（66）を満たすｕ′をＩＤ情報に持つエンティティＵ′（署名側）がこのｘ′とｋとを選択した場合、全く同じ署名データになるという性質を有している。従って、署名データからは署名エンティティを特定できないという特徴を有している。
ｘｆ（ｕ）≡ｘ′ｆ（ｕ′）（mod ｎ） …（66）
グループＧの秘密鍵Ｋ_G＝（１／ｔ（ｇ））ＰとエンティティＵの秘密鍵Ｋ_U＝（１／ｆ（ｕ））Ｐとを両方持てば同等の機能を有するように考えられるが、この第１１例ではグループの秘密鍵とエンティティの秘密鍵とを分離できないため、夫々の秘密鍵を各別に譲渡したりすることは不可能である。
【０１２５】
〔第１２例〕（ＩＤ情報に基づくグループ署名方法：ElGamal 型）
検証エンティティをグループに属するエンティティに限定する署名方法について説明する。この第１２例の方法では、Ｐをセンタの公開鍵とする。
【０１２６】
署名：エンティティＵ（署名側）において、乱数ｋ∈Ｚ_nが生成され、下記式（67），（68）のようにグループＧの署名データ（ベクトルＲ，Ｓ）が作成される。但し、ｘはｋＵ₀のｘ座標を表す。
【０１２７】
【数３０】

【０１２８】
検証：グループＧに属する任意のエンティティＶ（検証側）において、まず、下記式（69）に従ってｋｆ（ｕ）ｔ（ｇ）Ｑが求められ、次に、下記式（70），（71），（72）のようにｗ₁，ｗ₂，ｗ₃が計算された後、下記式（73）の成立により、署名データ（ベクトルＲ，Ｓ）の正当性が検証される。
【０１２９】
【数３１】

【０１３０】
〔第１３例〕（ＩＤ情報に基づくエンティティ署名方法：Schnorr 型Ｉ）
第１１例における署名方法を以下のように変更することにより、エンティティＵ（署名側）の署名データを得ることができる。
【０１３１】
署名：エンティティＵ（署名側）において、乱数ｋ∈Ｚ_nが生成され、下記式（74）のような中間データｒが計算された後、下記式（75），（76）のようにエンティティＵの署名データ（ｅ，Ｓ_i）が作成される。ｅ_n（Ｐ，Ｑ）は、エンティティＵのＩＤ情報及び秘密鍵とセンタの公開情報とから計算することができる。
【０１３２】
【数３２】

【０１３３】
検証：グループＧ′に属する任意のエンティティＶ（検証側）において、まず、下記式（77），（78）に従ってｅ_n（Ｐ，Ｑ），ｗが求められ、次に、下記式（79）により、署名データ（ｅ，Ｓ_i）の正当性が検証される。
【０１３４】
【数３３】

【０１３５】
〔第１４例〕（ＩＤ情報に基づくエンティティ署名方法：Schnorr 型II）
第１３例における署名方法を以下のように変更することにより、検証エンティティをグループＧに属するエンティティに限定することができる。
【０１３６】
署名：エンティティＵ（署名側）において、乱数ｋ∈Ｚ_nが生成され、下記式（80）のような中間データｒが計算された後、下記式（81），（82）のようにエンティティＵの署名データ（ｅ，Ｓ_i）が作成される。ｅ_n（Ｐ，Ｑ）は、エンティティＵのＩＤ情報及び秘密鍵とセンタの公開情報とから計算することができる。
【０１３７】
【数３４】

【０１３８】
検証：グループＧに属する任意のエンティティＶ（検証側）において、まず、下記式（83），（84）に従ってｅ_n（Ｐ，Ｑ）^x，ｗが求められ、次に、下記式（85）により、署名データ（ｅ，Ｓ_i）の正当性が検証される。
【０１３９】
【数３５】

【０１４０】
この第１４例の方式では、エンティティＶ（検証側）の秘密鍵Ｋ_VGが検証時に不可欠であり、しかも、同じグループに属するエンティティＶでなければｅ_n（Ｐ，Ｑ）^xを計算できないため、エンティティＶをエンティティＵ（署名側）と同じグループＧに属するエンティティに限定することができる。
【０１４１】
なお、上述した例では代数曲線として楕円曲線を用いる場合について説明したが、超楕円曲線を用いる場合にあっても、同様のペアリングを定義できるので、簡単に拡張することができる。
【０１４２】
ここで、前述した暗号化装置１０，復号装置２０のハードウェアの構成例について図１０を参照して説明する。
【０１４３】
暗号化装置１０は、ＣＰＵ５１，通信部５２，操作部５３，表示部５４，ＲＯＭ５５，ＲＡＭ５６，鍵格納部５７等を備えている。ＣＰＵ５１は、バス５８を介して暗号化装置１０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ５５に格納された暗号化処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。通信部５２は、通信路５０を介した送信・受信処理を実行する。操作部５３は、ユーザによる暗号化すべき平文の入力等の外部からの操作を受け付ける。表示部５４は、入力された暗号化すべき平文等を表示する。ＲＯＭ５５は、暗号化装置１０の上述した暗号化処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ５６は、ＳＲＡＭまたはフラッシュメモリ等で構成され、暗号化処理の動作時に発生する一時的なデータを記憶する。鍵格納部５７は、上述したベクトルＨを含む公開鍵を格納している。
【０１４４】
一方、復号装置２０は、ＣＰＵ６１，通信部６２，操作部６３，表示部６４，ＲＯＭ６５，ＲＡＭ６６，鍵格納部６７，出力部６８等を備えている。ＣＰＵ６１は、バス６９を介して復号装置２０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ６５に格納された復号処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。通信部６２は、通信路５０を介した送信・受信処理を実行する。操作部６３は、ユーザによる外部からの操作を受け付ける。表示部６４は、復号結果等を表示する。ＲＯＭ６５は、復号装置２０の上述した復号処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ６６は、ＳＲＡＭまたはフラッシュメモリ等で構成され、復号処理の動作時に発生する一時的なデータを記憶する。鍵格納部６７は、上述した秘密鍵及び公開鍵を格納している。出力部６８は、復号した平文を出力する。
【０１４５】
次に、前述した署名装置３０，検証装置４０のハードウェアの構成例について図１１を参照して説明する。
【０１４６】
署名装置３０は、ＣＰＵ７１，操作部７２，表示部７３，ＲＯＭ７４，ＲＡＭ７５，鍵格納部７６等を備えている。ＣＰＵ７１は、バス７７を介して署名装置３０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ７４に格納された署名処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。操作部７２は、ユーザによる外部からの操作を受け付ける。表示部７３は、署名データ等を表示する。ＲＯＭ７４は、署名装置３０の上述した署名処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ７５は、ＳＲＡＭまたはフラッシュメモリ等で構成され、署名処理の動作時に発生する一時的なデータを記憶する。鍵格納部７６は、上述したベクトルＨを含む公開鍵を格納している。
【０１４７】
一方、検証装置４０は、ＣＰＵ８１，操作部８２，表示部８３，ＲＯＭ８４，ＲＡＭ８５，鍵格納部８６，出力部８７等を備えている。ＣＰＵ８１は、バス８８を介して検証装置４０の上記ハードウェア各部と接続されていて、それらを制御すると共に、ＲＯＭ８４に格納された検証処理のコンピュータプログラムに従って、種々のソフトウェア的機能を実行する。操作部８２は、ユーザによる外部からの操作を受け付ける。表示部８３は、検証結果等を表示する。ＲＯＭ８４は、検証装置４０の上述した検証処理の動作に必要な種々のソフトウェアのコンピュータプログラムを予め格納している。ＲＡＭ８５は、ＳＲＡＭまたはフラッシュメモリ等で構成され、検証処理の動作時に発生する一時的なデータを記憶する。鍵格納部８６は、上述した秘密鍵及び公開鍵を格納している。出力部８７は、署名データの検証結果を出力する。
【０１４８】
図１２は、本発明の記録媒体の実施の形態の構成を示す図である。ここに例示するコンピュータプログラムは、上述した第１〜第４実施の形態にあって、公開鍵及び秘密鍵を生成する鍵生成処理、暗号文を作成する暗号化処理、暗号文を復号する復号処理、署名データを作成する署名処理、または、署名データを検証する検証処理を含んでおり、以下に説明する記録媒体に記録されている。なお、コンピュータ９０は、センタ１側か、または、各エンティティ側に設けられている。
【０１４９】
図１２において、コンピュータ９０とオンライン接続する記録媒体９１は、コンピュータ９０の設置場所から隔たって設置される例えばＷＷＷ(World Wide Web)のサーバコンピュータを用いてなり、記録媒体９１には前述の如きコンピュータプログラム９１ａが記録されている。記録媒体９１から通信線等の伝送媒体９４を介して読み出されたコンピュータプログラム９１ａがコンピュータ９０を制御することにより、コンピュータ９０が上述した処理のいずれかを実行する。
【０１５０】
コンピュータ９０の内部に設けられた記録媒体９２は、内蔵設置される例えばハードディスクドライブまたはＲＯＭ（図１０のＲＯＭ５５またはＲＯＭ６５、図１１のＲＯＭ７４またはＲＯＭ８４に相当）等を用いてなり、記録媒体９２には前述の如きコンピュータプログラム９２ａが記録されている。記録媒体９２から読み出されたコンピュータプログラム９２ａがコンピュータ９０を制御することにより、コンピュータ９０が上述した処理のいずれかを実行する。
【０１５１】
コンピュータ９０に設けられたディスクドライブ９０ａに装填して使用される記録媒体９３は、運搬可能な例えば光磁気ディスク，ＣＤ−ＲＯＭまたはフレキシブルディスク等を用いてなり、記録媒体９３には前述の如きプログラム９３ａが記録されている。記録媒体９３から読み出されたコンピュータプログラム９３ａがコンピュータ９０を制御することにより、コンピュータ９０が上述した処理のいずれかを実行する。
【０１５２】
【発明の効果】
以上詳述したように、本発明の公開鍵暗号方法では、多項式関数を設定すると共にペアリングを定義できる代数曲線上の点を選択し、暗号文を受信するエンティティのＩＤ情報をその多項式関数に代入して得られる関数値と代数曲線上の選択した点とを使用して暗号文を作成するようにしたので、エンティティのＩＤ情報から代数曲線を用いて変換される公開鍵をより容易に求めることができる。
【０１５３】
また、本発明の署名方法では、多項式関数を設定すると共にペアリングを定義できる代数曲線上の点を選択し、署名データを作成するエンティティのＩＤ情報をその多項式関数に代入して得られる関数値と代数曲線上の選択した点とを使用して署名データを作成するようにしたので、エンティティのＩＤ情報から代数曲線を用いて変換される公開鍵をより容易に求めることができる。
【０１５４】
更に、本発明の公開鍵暗号方法または署名方法では、グループのＩＤ情報及びグループに属する複数のエンティティ夫々のＩＤ情報を使用して、グループに対する暗号文または署名データとそのグループに属する複数のエンティティ夫々に対する暗号文または署名データとを独立的に作成するようにしたので、これらの暗号文または署名データを容易に作成することができる。
【図面の簡単な説明】
【図１】本発明の暗号通信システムの構成を示す模式図である。
【図２】二つのエンティティ間における情報の通信状態を示す模式図である。
【図３】センタでの処理の動作手順を示すフローチャートである。
【図４】送信側のエンティティでの暗号化処理の動作手順を示すフローチャートである。
【図５】受信側のエンティティでの復号処理の動作手順を示すフローチャートである。
【図６】二つのエンティティ間における署名システムを示す模式図である。
【図７】センタでの処理の動作手順を示すフローチャートである。
【図８】署名側のエンティティでの署名処理の動作手順を示すフローチャートである。
【図９】検証側のエンティティでの検証処理の動作手順を示すフローチャートである。
【図１０】暗号化装置及び復号装置のハードウェア構成例を示す図である。
【図１１】署名装置及び検証装置のハードウェア構成例を示す図である。
【図１２】記録媒体の実施の形態の構成を示す図である。
【符号の説明】
１センタ
１ａ公開鍵生成部
１ｂ秘密鍵生成部
１０暗号化装置
１３暗号化部
２０復号装置
２３復号部
３０署名装置
３３署名データ作成部
４０検証装置
４２署名データ検証部
５０通信路
９０コンピュータ
９１，９２，９３記録媒体
９１ａ，９２ａ，９３ａコンピュータプログラム
Ａ，Ｂ，Ｕ，Ｖ，Ｚエンティティ[0001]
TECHNICAL FIELD OF THE INVENTION
The present invention relates to a public key encryption method for performing an encryption process and a decryption process using identification information for identifying an entity (hereinafter, referred to as ID (Identity) information), a process for creating and verifying signature data using ID information of an entity. The present invention relates to a signature method for performing processing, an encryption communication system using the public key encryption method, and a computer program for causing a computer to execute these methods.
[0002]
[Prior art]
In a modern society called an advanced information society, important document and image information in business is transmitted, communicated, and processed in the form of electronic information based on a computer network. Such electronic information has a property that it can be easily copied, and it is difficult to distinguish a copy from an original, and thus the importance of information security is emphasized. In particular, the realization of a computer network that satisfies the elements of “computer resource sharing”, “multi-access”, and “wide-area” is indispensable for the establishment of an advanced information society. Contains inconsistent elements. As an effective method for resolving such contradictions, cryptographic techniques that have been used mainly in military and diplomatic aspects in the past history of humankind have been attracting attention.
[0003]
Cryptography is the exchange of information so that the meaning of the information cannot be understood by anyone other than the parties. In encryption, it is encryption to convert an original sentence (plaintext) that anyone can understand into a sentence (ciphertext) whose meaning is unknown to a third party, and decryption is to return the ciphertext to plaintext. The entire process of encryption and decryption is collectively called an encryption system. In the encryption process and the decryption process, secret information called an encryption key and a decryption key are used, respectively. Since a secret decryption key is required at the time of decryption, only a person who knows the decryption key can decrypt the ciphertext, and the encryption can maintain the confidentiality of the information.
[0004]
The encryption key and the decryption key may be equal or different. An encryption system in which both keys are equal is called a common key encryption system, and DES (Data Encryption Standards) adopted by the United States Department of Commerce Standard Bureau is a typical example. As an example of an encryption system in which both keys are different, an encryption system called a public key encryption system has been proposed. In this public key cryptosystem, each entity using the cryptosystem creates a pair of an encryption key and a decryption key, publishes the encryption key in a public key list, and keeps only the decryption key secret. System. In the public key cryptosystem, the pair of the encryption key and the decryption key are different from each other, and have a feature that the decryption key cannot be determined from the encryption key by using the one-way function.
[0005]
The public key cryptosystem is an epoch-making cryptosystem that publishes an encryption key, and conforms to the above three elements necessary for establishing an advanced information society. The research has been actively conducted in order to use the RSA cryptosystem, and the RSA cryptosystem has been proposed as a typical public key cryptosystem. This RSA encryption system is realized by utilizing the difficulty of factorization as a one-way function. In addition, various methods have been proposed for a public key cryptosystem utilizing the difficulty of solving the discrete logarithm problem (discrete logarithm problem).
[0006]
In addition, an encryption system using ID information that specifies an individual, such as the address, name, and e-mail address of each entity, has been proposed. In this encryption system, a common encryption / decryption key is generated between the transmitting and receiving entities based on the ID information. Further, the encryption technique based on the ID information includes (1) a method that requires preliminary communication between transmitting and receiving entities before ciphertext communication, and (2) a method that requires preliminary communication between transmitting and receiving entities before ciphertext communication. Some systems do not require communication. In particular, since the method (2) does not require preliminary communication, the convenience of the entity is high, and it is considered that the method will be the center of the future cryptosystem.
[0007]
The encryption system according to the method (2) is called an ID-NIKS (ID-based non-interactive key sharing scheme), and an encryption / decryption key is used without performing preliminary communication using ID information of a communication partner. Is adopted. The ID-NIKS is a method in which there is no need to exchange a public key and a secret key between transmitting and receiving entities, and does not require a key list or a service by a third party, and secure communication can be performed between arbitrary entities.
[0008]
In the public key cryptosystem described above, for example, in the case of the RSA cryptosystem, the length of the public key is ten and several times the current telephone number, which is extremely complicated. On the other hand, in the ID-NIKS, if each ID information is registered in the form of a list, a common key can be generated with an arbitrary entity by referring to the list. Therefore, if the ID-NIKS system is safely realized, a convenient encryption system can be constructed on a computer network to which many entities subscribe. For these reasons, ID-NIKS is expected to become the center of future cryptosystems.
[0009]
Therefore, the present inventors have proposed a key sharing method that allows two entities to easily share a common key without performing preliminary communication based on pairing on an elliptic curve using ID information of each entity. An encryption communication system using a key sharing method has been proposed (for example, see Patent Document 1).
[0010]
[Patent Document 1]
JP 2002-26892 A
[0011]
[Problems to be solved by the invention]
Even after proposing a key sharing scheme (ID-NIKS) as disclosed in Patent Document 1, the present inventors have proposed a public key encryption scheme and a signature scheme based on ID information of each entity using pairing on an elliptic curve. Research continues.
[0012]
The present invention has been made in view of such circumstances, and a public key capable of easily obtaining public information (public key) converted from ID information of an entity by substituting the ID information of the entity into a polynomial. It is an object to provide an encryption method and a signature method, an encryption communication system using the public key encryption method, and a computer program for causing a computer to execute these methods.
[0013]
Another object of the present invention is to use cipher text or signature data for a group and cipher text or signature for each of a plurality of entities belonging to the group by using ID information of the group and ID information of each of the plurality of entities belonging to the group. An object of the present invention is to provide a public key encryption method or a signature method that can easily create data independently.
[0014]
[Means for Solving the Problems]
The public key encryption method according to claim 1, wherein in the public key encryption method for creating a ciphertext using a public key based on specific information for specifying an entity that receives a ciphertext, the specific information is substituted into a polynomial. The ciphertext is created using an obtained result and a point on an algebraic curve for which pairing can be defined.
[0015]
The public key cryptography method according to claim 2 is a public key cryptography method for generating a ciphertext using a public key based on specific information for specifying an entity that receives a ciphertext, wherein a polynomial function is set and pairing is performed. A point on the algebraic curve that can be defined is selected, and the ciphertext is created using a function value obtained by substituting the specific information into the set polynomial function and the selected point.
[0016]
A public key encryption method according to claim 3, wherein, for a group to which a plurality of entities belong, a cipher text for the group and a cipher text for each of the plurality of entities are independently created to specify the group. Specific information and specific information for specifying each of the plurality of entities are used.
[0017]
According to a fourth aspect of the present invention, in the signature method for verifying signature data created by a first entity with a second entity, the signature method is obtained by substituting identification information for identifying the first entity into a polynomial. The signature data is created and verified using a result and a point on an algebraic curve for which pairing can be defined.
[0018]
A signature method according to claim 5, wherein in the signature method in which signature data created by the first entity is verified by the second entity, a polynomial function is set and a point on the algebraic curve where pairing can be defined is selected. And generating and verifying the signature data using a function value obtained by substituting specific information for specifying the first entity into the set polynomial function and the selected point. .
[0019]
7. The signature method according to claim 6, wherein, for a group to which a plurality of entities belong, signature data created by an entity belonging to the group is verified by another entity belonging to the group or an entity not belonging to the group. And specifying information for specifying the group and specifying information for specifying the entity that creates the signature data.
[0020]
The cryptographic communication system according to claim 7, wherein an encryption process of encrypting a plaintext, which is information to be transmitted, into a ciphertext, and a decryption process of decrypting the transmitted ciphertext into a plaintext, are mutually performed between a plurality of entities. In the cryptographic communication system performed in the center, a center that generates a public key and a secret key of each entity based on specific information identifying each entity, and the encryption process using a public key based on the specific information of the entity to be transmitted And having a plurality of entities that perform the decryption process using its own secret key, and at the center, set a polynomial function and select a point on an algebraic curve that can define pairing, In each entity, the ciphertext is created using a function value obtained by substituting the specific information into the set polynomial function and the selected point. Characterized in that was.
[0021]
9. A computer program for causing a computer to generate a public key and a secret key used in a public key cryptosystem or a signature system, the computer program comprising the steps of: setting a polynomial function in the computer; Selecting a point on an algebraic curve that can define a ring.
[0022]
10. A computer program for causing a computer to create a ciphertext using a public key based on specific information identifying an entity that receives the ciphertext, the computer program comprising: Inputting a point on an algebraic curve that can define a function, a step of causing a computer to obtain a function value by substituting the specific information into the polynomial function, and causing the computer to use the obtained function value and the point. Generating the ciphertext by using the above method.
[0023]
The computer program according to claim 10, wherein the computer program causes the computer to create the signature data using identification information that identifies an entity that creates the signature data, wherein the computer can define a polynomial function and a pairing algebra. Inputting a point on a curve; causing a computer to obtain a function value by substituting the specific information into the polynomial function; and causing the computer to obtain the signature data using the obtained function value and the point. And the step of creating
[0024]
In the public key cryptography method of the present invention, a polynomial function is set and a point on an algebraic curve that can define pairing is selected, and ID information of an entity that receives a ciphertext is substituted into the polynomial function. A ciphertext is created using the resulting function values and selected points on the algebraic curve. Therefore, the public key converted from the entity ID information using the algebraic curve can be more easily obtained.
[0025]
According to the signature method of the present invention, a polynomial function is set and a point on an algebraic curve that can define pairing is selected, and ID information of an entity that creates signature data is obtained by substituting into the polynomial function. Signature data is created using the function values and selected points on the algebraic curve. Therefore, the public key converted from the entity ID information using the algebraic curve can be more easily obtained.
[0026]
In the public key encryption method or the signature method of the present invention, the ID information of the group and the ID information of each of the plurality of entities belonging to the group are used, and the cipher text or signature data for the group and the plurality of entities belonging to the group are used. The ciphertext or signature data for each is created independently. Therefore, these ciphertexts or signature data are easily created.
[0027]
BEST MODE FOR CARRYING OUT THE INVENTION
An embodiment of the present invention will be specifically described.
First, the basic properties of the Bayle pairing of elliptic curves used in the present invention will be described. Finite field vector F _q The elliptic curve defined above is represented by E / vector F _q And the elliptic curve is represented by E / vector F _q Vector F _q A group formed by rational points above is represented by E (vector F _q ). Here, this group of elliptic curves E (vector F _q ) Includes an n-twisted subgroup E [n].
[0028]
The pairing on the elliptic curve is performed by the vector F from two n-torsion points P, QｎE [n] on the elliptic curve. _q This is a mapping of the upper order n to a multiplicative group. Pairing has the following properties. Note that e _n (,) Represents pairing.
[0029]
(Non-degenerate)
For a point P∈E [n] and an arbitrary point Q∈E [n],
e _n When (P, Q) = 1 holds, P = 0.
(Antisymmetric)
For any point P, Q∈E [n],
e _n (P, Q) = e _n (Q, P) ^-1 Holds.
(Bilinear)
For any point P, Q, R∈E [n],
e _n (P + Q, R) = e _n (P, R) e _n (Q, R),
e _n (P, Q + R) = e _n (P, Q) e _n (P, R)
Holds.
[0030]
When applying pairing on an elliptic curve to a cryptographic method, it is necessary to select an elliptic curve to be used and its n-twist subgroup so as to satisfy the following conditions in order to secure sufficient security.
(1) n has a prime number of 160 bits or more as a factor.
(2) q is 2 ¹⁰²⁴ That is all.
(3) Vector F _q Satisfies the following condition.
[0031]
(Equation 1)

[0032]
In the following description, an elliptic curve satisfying these conditions (1) to (3) is referred to as a safe elliptic curve for which pairing can be calculated. In the following, n is a prime number for simplicity.
[0033]
(First Embodiment: Public Key Encryption Method Based on ID Information)
FIG. 1 is a schematic diagram showing the configuration of the cryptographic communication system of the present invention. A center 1 that can trust information concealment is set, and this center 1 can be, for example, a public organization of society. The center 1 and a plurality of entities A, B,..., Z as users who use the cryptographic communication system are connected by

secret communication paths

2a, 2b,. 2a, 2b,..., 2z, secret key information (secret key K _A , K _B , ..., K _Z ) Are distributed to each of the entities A, B,..., Z. Further, communication paths 3ab, 3az, 3bz,... Are provided between the two entities, and a ciphertext obtained by encrypting communication information via the communication paths 3ab, 3az, 3bz,. It is to be transmitted by.
[0034]
Next, information communication between entities in the cryptographic communication system will be described. FIG. 2 is a schematic diagram showing a communication state of information between two entities V and U. In the example shown in FIG. 2, a plaintext (message) m is ₁ , C _Two And transmits it to the entity U, and the entity U uses the ciphertext C ₁ , C _Two Is decoded to the original plaintext (message) m. In addition, there are various entities such as a human, an apparatus, a machine, a program, and a system including them as components, and the present invention can be applied to any entity among them.
[0035]
The center 1 includes a public key generation unit 1a that generates various public keys including a vector H that is public information, and a secret key K of each of the entities V and U. _V , K _U Secret key generation unit 1b for obtaining the secret key K _V , K _U And a secret key distribution unit 1c that distributes the secret key to each entity V and U.
[0036]
The encryption device 10 of the entity V on the transmission side sends the secret key K _V , A random number generator 12 for generating a random number r, and a plaintext m ₁ , C _Two Encrypting unit 13 and encrypted ciphertext C ₁ , C _Two To the communication path 50.
[0037]
Further, the decryption device 20 of the entity U on the transmitting side sends the secret key K _U And the secret key receiving unit 21 for receiving the ₁ , C _Two And the ciphertext C, which receives the ₁ , C _Two To a plaintext m, and a plaintext output unit 24 for outputting the decrypted plaintext m.
[0038]
Next, the operation will be described. FIG. 3 is a flowchart showing an operation procedure of processing in the center 1, FIG. 4 is a flowchart showing an operation procedure of encryption processing in the entity V (transmission side), and FIG. 5 is a flowchart of decryption processing in the entity U (reception side). It is a flowchart which shows an operation | movement procedure.
[0039]
First, in the center 1, a safe elliptic curve for which pairing can be calculated is generated (step S1), and n twist points P and Q are randomly selected (step S2). Where e _n Points P and Q are selected so that (P, Q) ≠ 1 does not hold. Next, a d-order polynomial function f (x) as shown in the following equation (1) is generated (step S3). In equation (1), the highest order coefficient a _d May be 1, and d = 1, that is, a linear expression.
f (x) = a _d x ^d + A _d-1 x ^d-1 + ... + a ₁ x + a ₀ … (1)
[0040]
In the center 1, a vector H as shown in the following equation (2) is calculated, and the vector H is made public as public information (step S4). Also, the secret key K is determined by using the ID information v, u of the entities V, U. _V , K _U Is generated as shown in the following equations (3) and (4) (step S5), and is distributed to the entities V and U (step S6).
[0041]
(Equation 2)

[0042]
In the entity V, a random number r is generated by the random number generation unit 12 (step S11), and the following equations (5) and (6) are obtained by using the ID information u of the entity U, the public information vector H of the center 1, and the random number r. ), The plaintext m to the ciphertext C ₁ , C _Two Is created by the encryption unit 13 (steps S12 and S13). The operation symbol in Expression (6) represents, for example, EXOR (exclusive OR) for each bit in public key cryptography.
[0043]
[Equation 3]

[0044]
The cipher text C _Two E in _n (P, Q) is the ID information v of the entity V and the secret key K of the entity V _V It can be calculated as follows using the public information vector H of the center 1.
[0045]
(Equation 4)

[0046]
Created ciphertext C ₁ , C _Two Is transmitted from the ciphertext sending unit 14 to the entity U via the communication path 50 (step S14).
[0047]
Ciphertext C transmitted through communication channel 50 ₁ , C _Two Is received by the ciphertext receiving unit 22 of the entity U (step S21). In the entity U, the decryption unit 23 uses its own secret key K _U And the ciphertext C as shown in the following equation (7). ₁ , C _Two Is decrypted into a plaintext m (step S22).
[0048]
(Equation 5)

[0049]
As described above, information communication can be safely performed by cipher text using a relatively simple algorithm.
[0050]
In the first embodiment described above, the entity V (transmitting side) is registered in the center 1 and own secret key K _V Using e _n (P, Q) was obtained, but this e _n When (P, Q) is disclosed as public information from the center 1, the entity V (transmitting side) can create a ciphertext even if it is not registered in the center 1.
[0051]
(Second Embodiment: Signature Method Based on ID Information)
Next, a signature scheme based on ID information using a technique similar to the public key encryption scheme described in the first embodiment will be described.
[0052]
FIG. 6 is a schematic diagram showing a signature system between two entities U and V. The example of FIG. 6 shows a case where the entity U creates signature data and the entity V verifies the signature data.
[0053]
The center 1 includes a public key generation unit 1a, a secret key generation unit 1b, and a secret key distribution unit 1c similar to those in the first embodiment.
[0054]
The signature device 30 of the entity U on the signing side sends the secret key K _U , A random number generator 32 for generating random numbers, various public keys, own ID information u, and own secret key K _U And a signature data creation unit 33 for creating signature data using the above. Further, the verification device 40 of the entity V on the verification side transmits the secret key K _V And a signature data verifying unit 42 for verifying the signature data from the entity U.
[0055]
Next, the operation will be described. 7 is a flowchart showing an operation procedure of processing in the center 1, FIG. 8 is a flowchart showing an operation procedure of signature processing in an entity U (signature side) for creating signature data, and FIG. 9 is an entity V for verifying signature data. It is a flowchart which shows the operation | movement procedure of the verification process in (verification side).
[0056]
First, in the center 1, as in the first embodiment, a safe elliptic curve for which pairing can be calculated is generated (step S31), and n torsion points P and Q are randomly selected (step S32). Next, a d-order polynomial function f (x) as shown in the above equation (1) is generated (step S33). Various public keys (which differ depending on each method described later) are disclosed as public information (step S34). Also, the secret key K is determined using the ID information u, v of the entities U, V. _U , K _V Is generated as shown in the above equations (4) and (3) (step S35), and is distributed to the entities U and V (step S36).
[0057]
In the entity U, the random number k is generated by the random number generation unit 32 (step S41), and the ID information u of the entity U and the secret key K _U The signature data is created by the signature data creation unit 33 using the public key (public information) and the random number k (step S42). The created signature data is sent to the entity V (step S43).
[0058]
The created signature data is received by the entity V (step S51), and the signature data verification unit 42 checks the ID information v and u of the entity and the entity U and the secret key K of the entity. _V The signature data is verified using the public key and various public keys (public information) (step S52).
[0059]
Next, specific examples (first to sixth examples) of the signature method of the present invention will be described. As typical types of the signature scheme, an ElGamal type and a Schnorr type are known, and the following description will focus on these types.
[0060]
[First example] (ElGamal type I)
P @ E [n] is added to the public key in the center 1 in the first embodiment. From the public key vector H of the center and the ID information c of any entity C, f (c) Q can be calculated as in the following equation (8). Further, own secret key K _C , The entity C is expressed by e as shown in the following equation (9). _n It is possible to calculate (P, Q). That is, any entity that has its own private key is e _n (P, Q) can be calculated.
[0061]
(Equation 6)

[0062]
The specific signature and verification are performed as follows. The center 1 publishes a hash function h (·), which is a one-way function, as a public key.
[0063]
Signature: (signature data (R, S)) In entity U, random number k 乱数 Z _n Is generated (S41), and signature data (R, S) is created as in the following equations (10) and (11) (S42). The created signature data (R, S) is sent to the entity V (S43). Here, x represents the x coordinate of R.
[0064]
(Equation 7)

[0065]
Verification: In entity V, signature data (R, S) is received (S51), and v ₁ And v shown in the following equation (13) _Two Are confirmed to be equal, and the signature data is verified (S52).
[0066]
(Equation 8)

[0067]
[Second example] (Schnorr type I)
P @ E [n] is added to the public key in the center 1 in the first embodiment. The specific signature and verification are performed as follows. The center 1 publishes the hash function h (·) as a public key.
[0068]
Signature: (signature data (e, S)) In entity U, random number k 乱数 Z _n Is generated (S41), and after calculating intermediate data r as shown in the following equation (14), signature data (e, S) is created as shown in the following equations (15) and (16) (S42). . Note that the signature data e is obtained as a hash value of the concatenation of the plaintext m and the intermediate data r, as shown in Expression (15). The created signature data (e, S) is sent to the entity V (S43).
[0069]
(Equation 9)

[0070]
Verification: The entity V receives the signature data (e, S) (S51), confirms that the following equations (17) and (18) hold, and verifies the signature data (S52).
[0071]
(Equation 10)

[0072]
[Third example] (ElGamal type II)
In the third example, since P is not used, this P can be used as secret information of the center 1. The specific signature and verification are performed as follows. The center 1 publishes the hash function h (·) as a public key.
[0073]
Signature: (signature data (vector R, S)) In entity U, random number k∈Z _n Is generated (S41), and signature data (vectors R and S) are generated as shown in the following equations (19) and (20) (S42). The created signature data (vectors R and S) is sent to the entity V (S43). Where x is kH ₀ Represents the x coordinate.
[0074]
[Equation 11]

[0075]
Verification: The entity V receives the signature data (vectors R and S) (S51), verifies that the following relationship is established, and verifies the signature data (S52). First, kf (v) Q is calculated from the vector R as in the following equation (21), and then wf is calculated as in the following equations (22), (23) and (24). ₁ , W _Two , W _Three Is obtained. Then, when the following equation (25) holds, the validity of the signature data (vectors R and S) is verified.
[0076]
(Equation 12)

[0077]
[Fourth example] (Schnorr type II)
In the method of the fourth example, as in the third example, P is not used, so that P can be used as secret information of the center 1. The specific signature and verification are performed as follows. The center 1 publishes the hash function h (·) as a public key.
[0078]
Signature: (signature data (e, S)) In entity U, random number k 乱数 Z _n Is generated (S41), and after calculating intermediate data r as shown in the following equation (26), signature data (e, S) is created as shown in the following equations (27) and (28) (S42). . The created signature data (e, S) is sent to the entity V (S43).
[0079]
(Equation 13)

[0080]
Verification: The entity V receives the signature data (e, S) (S51), and verifies the signature data as follows (S52). First, w is obtained according to the following equation (29), and then the following equation (30) is established, so that the validity of the signature data (e, S) and the plaintext m is verified.
[0081]
[Equation 14]

[0082]
[Fifth example] (ElGamal type III)
In the method of the fifth example, P is the public key of the center 1. The feature of this method is that it always needs its own private key when verifying signature data. The specific signature and verification are performed as follows. The center 1 publishes the hash function h (·) as a public key.
[0083]
Signature: (signature data (vector R, S)) In entity U, random number k∈Z _n Is generated (S41), and signature data (vectors R and S) are generated as shown in the following equations (31) and (32) (S42). The created signature data (vector R, S) is sent to the entity V (S43). Where x is kH ₀ Represents the x coordinate.
[0084]
(Equation 15)

[0085]
Verification: The entity V receives the signature data (vectors R and S) (S51), verifies that the following relationship is established, and verifies the signature data (S52). As in the following equations (33), (34), and (35), w ₁ , W _Two , W _Three Is calculated, the validity of the signature data (vectors R and S) is verified by the following equation (36).
[0086]
(Equation 16)

[0087]
[Sixth example] (Other types)
The specific signature and verification in the method of the sixth example are performed as follows. The center 1 publishes the hash function h (·) as a public key.
[0088]
Signature: In entity U, random number k, r∈Z _n Is generated (S41), and an n-twist point M = h (m) on the elliptic curve corresponding to the plaintext m is calculated using the hash function h (·). Then, the signature data (S ₁ , S _Two , Vector S _Three ) Is the private key P of the entity U _U Using the ID information u of the entity U mapped to the n-twist point P on the elliptic curve and the public information h (·) of the center and the vector H, the following equations (37), (38), and ( 39) (S42). The created signature data (S ₁ , S _Two , Vector S _Three ) Is sent to the entity V (S43).
[0089]
[Equation 17]

[0090]
Verification: In entity V, signature data (S ₁ , S _Two , Vector S _Three ) Is received (S51), and after M = h (m) is obtained from the plaintext m, the secret key P of the entity V is obtained. _V Is used to verify that the following equation (40) holds, and the signature data is verified (S52).
[0091]
(Equation 18)

[0092]
In the second embodiment described above, the entity V (verifying side) is registered in the center 1 and its own secret key K _V Using e _n (P, Q) was obtained, but this e _n When (P, Q) is disclosed as public information from the center 1, the entity V (verifying side) can verify the signature data even if it is not registered in the center 1.
[0093]
(Third embodiment)
Next, a signature method according to the third embodiment using a secret key and a public key different from those of the second embodiment will be described using an ElGamal type (seventh example) and a Schnorr type (eighth example) as examples. . Note that the configurations of the signature device and the verification device in the third embodiment, and the operation procedures of the center process, the signature process, and the verification process are the same as those in the second embodiment (FIGS. 6 to 9). Description is omitted.
[0094]
[Seventh example] (ElGamal type)
Preparation: A reliable elliptic curve capable of calculating a pairing is generated at a reliable center, and the ID information u of the entity U (signature side) is converted into an n-twist point P on the elliptic curve. _U And a hash function h (·) is made public. At the center, the secret key y 鍵 Z _n Is generated, and Q and yQ are calculated and published using the n torsion points Q ［E [n]. Further, at the center, the secret key K of the entity U is obtained from the ID information u of the entity U. _U = YP _U Is calculated and this secret key K _U Is sent to the entity U.
[0095]
Signature: (signature data (R, S)) In entity U, random number k 乱数 Z _n Is generated, and signature data (R, S) is created as in the following equations (41) and (42). The created signature data (R, S) is sent to the entity V. Here, x is the x coordinate of R.
[0096]
[Equation 19]

[0097]
Verification: In the entity V, the signature data (R, S) is received, and the establishment of the following equation (43) is confirmed, and the signature data is verified.
[0098]
(Equation 20)

[0099]
[Eighth example] (Schnorr type)
Preparation: Preparation processing in the center is the same as in the seventh example.
[0100]
Signature: (signature data (e, S)) In entity U, random number k 乱数 Z _n Is generated and the intermediate data r as shown in the following equation (44) is calculated, and then the signature data (e, S) is created as in the following equations (45) and (46). The created signature data (e, S) is sent to the entity V.
[0101]
(Equation 21)

[0102]
Verification: In the entity V, the signature data (e, S) is received, and it is confirmed that the following expressions (47) and (48) hold, and the signature data is verified.
[0103]
(Equation 22)

[0104]
(Fourth embodiment)
Next, a public key encryption method and a signature method in consideration of a group including a plurality of entities will be described. The configuration of the encryption device and the decryption device in the public key encryption method according to the fourth embodiment, and the operation procedure of the center process, the encryption process, and the decryption process are the same as those of the first embodiment (FIGS. 2 to 5). The configuration of the signature device and the verification device in the signature method according to the fourth embodiment, and the operation procedure of the center processing, the signature process, and the verification process are the same as those of the second embodiment (FIGS. 6 to 9). ), And their description is omitted.
[0105]
In the fourth embodiment, two sets of the center secret polynomial function as described in the first and second embodiments are generated for each entity and for the group. Specifically, a d-order polynomial function f (x) (similar to the above equation (1)) for each entity as shown in the following equation (49) and a group polynomial function f (x) for the group as shown in the following equation (50) A z-order polynomial function t (x) is generated.
f (x) = a _d x ^d + A _d-1 x ^d-1 + ... + a ₁ x + a ₀ … (49)
t (x) = b _z x ^z + B _z-1 x ^z-1 + ... + b ₁ x + b ₀ … (50)
[0106]
Assume that the entity U belongs to the group G. The ID information of the entity U is represented by u, and the ID information of the group G is represented by g. In this case, the secret key K of the entity U _UG Is given by the following equation (51) and is calculated at the center. Further, the public key of the group G as public information to be made public by the center is given by the following equation (52), and information for the entity U (which need not be made public) is given by the following equation (53). Calculated at the center.
[0107]
[Equation 23]

[0108]
Hereinafter, specific examples of the public key encryption method (ninth and tenth examples) and the signature method (eleventh to fourteenth examples) will be described.
[0109]
[Ninth example] (Public key encryption method for group based on ID information)
A public key encryption method for the group G that can be decrypted by any entity belonging to the group G will be described. This example is suitable for transmitting the same ciphertext to all entities belonging to one group G.
[0110]
Encryption: random number r∈Z at the transmitting entity (transmitting side) _n Is generated, and as a ciphertext to the group G, C as in the following equations (54) and (55) is used. _i , C _{d + 1} Is created. e _n (P, Q) can be calculated from the ID information and secret key of the transmitting entity and the public information of the center.
[0111]
(Equation 24)

[0112]
Decryption: At any entity U (reception side) belonging to the group G, the ciphertext C _i , C _{d + 1} Is decrypted from the plaintext m.
[0113]
(Equation 25)

[0114]
[Tenth Example] (Public key encryption method for each entity based on ID information)
An example in which a ciphertext is sent to a specific entity U belonging to a group G using the same secret key and public key as in the ninth example will be described. The encryption to the entity U (reception side) belonging to the group G and the decryption by the entity U can be performed in the same manner as in the first embodiment.
[0115]
Encryption: random number r∈Z at the transmitting entity (transmitting side) _n Is generated, and as a ciphertext to the entity U, C such as the following equations (57) and (58) ₁ , C _Two Is created.
[0116]
(Equation 26)

[0117]
Decryption: On the entity U side, a ciphertext C ₁ , C _Two Is decrypted from the plaintext m.
[0118]
[Equation 27]

[0119]
[Eleventh example] (Group signature method based on ID information: Schnorr type)
It is not possible to specify which entity in the group signed from the signature data, but a signature method that can verify that the entity belonging to the group has signed will be described.
[0120]
Signature: In entity U (signature side), random number k 乱数 Z _n Is generated, and the intermediate data r as shown in the following equation (60) is calculated. Then, as shown in the following equations (61) and (62), the signature data (e, S _i ) Is created. e _n (P, Q) can be calculated from the ID information and secret key of the entity U and the public information of the center.
[0121]
[Equation 28]

[0122]
Verification: In an arbitrary entity V (verification side) belonging to the group G ′, first, e is calculated according to the following equations (63) and (64). _n (P, Q), w are obtained, and then the signature data (e, S) is calculated by the following equation (65). _i ) Is verified.
[0123]
(Equation 29)

[0124]
The eleventh example has a property that when an entity U ′ (signature side) having u ′ satisfying the following equation (66) as ID information selects x ′ and k, the signature data becomes completely the same. I have. Therefore, a signature entity cannot be specified from signature data.
xf (u) ≡x′f (u ′) (mod n) (66)
Group G private key K _G = (1 / t (g)) P and private key K of entity U _U = (1 / f (u)) P, it is considered to have the same function. However, in the eleventh example, since the secret key of the group and the secret key of the entity cannot be separated, each secret key It is impossible to transfer each one separately.
[0125]
[Twelfth example] (Group signature method based on ID information: ElGamal type)
A signature method for limiting a verification entity to entities belonging to a group will be described. In the twelfth example, P is the public key of the center.
[0126]
Signature: In entity U (signature side), random number k 乱数 Z _n Is generated, and signature data (vectors R and S) of the group G is created as shown in the following equations (67) and (68). Where x is kU ₀ Represents the x coordinate.
[0127]
[Equation 30]

[0128]
Verification: In an arbitrary entity V (verification side) belonging to the group G, first, kf (u) t (g) Q is obtained according to the following equation (69), and then the following equations (70), (71), W as in (72) ₁ , W _Two , W _Three Is calculated, the validity of the signature data (vectors R, S) is verified by the following equation (73).
[0129]
[Equation 31]

[0130]
[Thirteenth example] (Entity signature method based on ID information: Schnorr type I)
By changing the signature method in the eleventh example as follows, signature data of the entity U (signature side) can be obtained.
[0131]
Signature: In entity U (signature side), random number k 乱数 Z _n Is generated and the intermediate data r is calculated as in the following equation (74), and then the signature data (e, S) of the entity U is calculated as in the following equations (75) and (76). _i ) Is created. e _n (P, Q) can be calculated from the ID information and secret key of the entity U and the public information of the center.
[0132]
(Equation 32)

[0133]
Verification: In an arbitrary entity V (verification side) belonging to the group G ′, first, e is calculated according to the following equations (77) and (78). _n (P, Q), w are obtained, and then the signature data (e, S) is calculated by the following equation (79). _i ) Is verified.
[0134]
[Equation 33]

[0135]
[14th example] (Entity signature method based on ID information: Schnorr type II)
By changing the signature method in the thirteenth example as follows, the verification entities can be limited to the entities belonging to the group G.
[0136]
Signature: In entity U (signature side), random number k 乱数 Z _n Is generated, and the intermediate data r as shown in the following equation (80) is calculated. Then, as shown in the following equations (81) and (82), the signature data (e, S _i ) Is created. e _n (P, Q) can be calculated from the ID information and secret key of the entity U and the public information of the center.
[0137]
(Equation 34)

[0138]
Verification: In any entity V (verification side) belonging to the group G, first, e _n (P, Q) ^x , W are obtained, and then the signature data (e, S _i ) Is verified.
[0139]
(Equation 35)

[0140]
In the method of the fourteenth example, the secret key K of the entity V (verifying side) _VG Is indispensable at the time of verification, and e is not an entity V belonging to the same group. _n (P, Q) ^x Cannot be calculated, the entity V can be limited to entities belonging to the same group G as the entity U (signature side).
[0141]
Note that, in the above-described example, the case where an elliptic curve is used as the algebraic curve has been described. However, even when a superelliptic curve is used, the same pairing can be defined, so that it can be easily expanded.
[0142]
Here, an example of a hardware configuration of the encryption device 10 and the decryption device 20 described above will be described with reference to FIG.
[0143]
The encryption device 10 includes a CPU 51, a communication unit 52, an operation unit 53, a display unit 54, a ROM 55, a RAM 56, a key storage unit 57, and the like. The CPU 51 is connected to the above hardware components of the encryption device 10 via the bus 58, controls them, and executes various software functions according to the computer program of the encryption processing stored in the ROM 55. . The communication unit 52 performs transmission / reception processing via the communication path 50. The operation unit 53 receives an external operation such as input of a plain text to be encrypted by the user. The display unit 54 displays the input plaintext or the like to be encrypted. The ROM 55 stores computer programs of various software necessary for the operation of the above-described encryption processing of the encryption device 10 in advance. The RAM 56 is composed of an SRAM, a flash memory, or the like, and stores temporary data generated during the operation of the encryption process. The key storage unit 57 stores a public key including the above-described vector H.
[0144]
On the other hand, the decryption device 20 includes a CPU 61, a communication unit 62, an operation unit 63, a display unit 64, a ROM 65, a RAM 66, a key storage unit 67, an output unit 68, and the like. The CPU 61 is connected to the above-described hardware units of the decoding device 20 via the bus 69, controls the hardware units, and executes various software functions according to a decoding computer program stored in the ROM 65. The communication unit 62 performs transmission / reception processing via the communication path 50. The operation unit 63 receives an external operation by the user. The display unit 64 displays a decoding result and the like. The ROM 65 stores in advance computer programs of various software necessary for the operation of the decoding process of the decoding device 20 described above. The RAM 66 is composed of an SRAM, a flash memory, or the like, and stores temporary data generated during the operation of the decoding process. The key storage section 67 stores the above-mentioned secret key and public key. The output unit 68 outputs the decrypted plaintext.
[0145]
Next, an example of a hardware configuration of the above-described signature device 30 and verification device 40 will be described with reference to FIG.
[0146]
The signature device 30 includes a CPU 71, an operation unit 72, a display unit 73, a ROM 74, a RAM 75, a key storage unit 76, and the like. The CPU 71 is connected to the above hardware units of the signature device 30 via the bus 77, controls them, and executes various software functions according to the computer program of the signature processing stored in the ROM 74. The operation unit 72 receives an external operation by the user. The display unit 73 displays signature data and the like. The ROM 74 stores in advance computer programs of various software necessary for the above-described signature processing operation of the signature device 30. The RAM 75 is composed of an SRAM, a flash memory, or the like, and stores temporary data generated during a signature processing operation. The key storage unit 76 stores a public key including the vector H described above.
[0147]
On the other hand, the verification device 40 includes a CPU 81, an operation unit 82, a display unit 83, a ROM 84, a RAM 85, a key storage unit 86, an output unit 87, and the like. The CPU 81 is connected to the above-described hardware units of the verification device 40 via the bus 88, controls them, and executes various software functions according to a computer program of the verification process stored in the ROM 84. The operation unit 82 receives an external operation by the user. The display unit 83 displays the verification result and the like. The ROM 84 stores in advance computer programs of various software necessary for the operation of the above-described verification processing of the verification device 40. The RAM 85 is configured by an SRAM, a flash memory, or the like, and stores temporary data generated during the operation of the verification process. The key storage unit 86 stores the above-mentioned secret key and public key. The output unit 87 outputs the verification result of the signature data.
[0148]
FIG. 12 is a diagram showing the configuration of the embodiment of the recording medium of the present invention. The computer program exemplified here is a computer program according to the first to fourth embodiments described above, which is a key generation process for generating a public key and a secret key, an encryption process for creating a ciphertext, and a decryption process for decoding a ciphertext. , A signature process for creating signature data, or a verification process for verifying the signature data, which is recorded on a recording medium described below. The computer 90 is provided on the center 1 side or on each entity side.
[0149]
In FIG. 12, a recording medium 91 that is connected online to a computer 90 is, for example, a WWW (World Wide Web) server computer that is installed separately from the installation location of the computer 90. The program 91a is recorded. The computer 90 executes one of the processes described above by controlling the computer 90 by the computer program 91a read from the recording medium 91 via the transmission medium 94 such as a communication line.
[0150]
The recording medium 92 provided inside the computer 90 includes, for example, a hard disk drive or a ROM (corresponding to the ROM 55 or ROM 65 in FIG. 10 or the ROM 74 or ROM 84 in FIG. 11) or the like which is installed therein. The computer program 92a as described above is recorded. The computer program 92a read from the recording medium 92 controls the computer 90, so that the computer 90 executes any of the processes described above.
[0151]
The recording medium 93 used by being loaded into the disk drive 90a provided in the computer 90 is a transportable medium such as a magneto-optical disk, a CD-ROM, or a flexible disk. 93a is recorded. The computer program 93a read from the recording medium 93 controls the computer 90, so that the computer 90 executes any of the processes described above.
[0152]
【The invention's effect】
As described in detail above, in the public key cryptography method of the present invention, a polynomial function is set, a point on an algebraic curve that can define pairing is selected, and the ID information of the entity that receives the ciphertext is used as the polynomial function. Since the ciphertext is created using the function value obtained by the substitution and the selected point on the algebraic curve, the public key to be converted using the algebraic curve from the ID information of the entity is more easily obtained. be able to.
[0153]
In the signature method of the present invention, a function value obtained by setting a polynomial function and selecting a point on an algebraic curve that can define pairing, and substituting ID information of an entity for creating signature data into the polynomial function Since the signature data is created using and the selected point on the algebraic curve, a public key to be converted using the algebraic curve can be more easily obtained from the ID information of the entity.
[0154]
Further, in the public key encryption method or the signature method of the present invention, the cipher text or signature data for the group and the plurality of entities belonging to the group are used by using the ID information of the group and the ID information of each of the plurality of entities belonging to the group. Since the cipher text or the signature data is generated independently, the cipher text or the signature data can be easily created.
[Brief description of the drawings]
FIG. 1 is a schematic diagram showing a configuration of a cryptographic communication system of the present invention.
FIG. 2 is a schematic diagram showing a communication state of information between two entities.
FIG. 3 is a flowchart showing an operation procedure of processing in a center.
FIG. 4 is a flowchart illustrating an operation procedure of an encryption process in a transmitting entity.
FIG. 5 is a flowchart showing an operation procedure of a decoding process in a receiving entity.
FIG. 6 is a schematic diagram showing a signature system between two entities.
FIG. 7 is a flowchart showing an operation procedure of processing in a center.
FIG. 8 is a flowchart showing an operation procedure of a signature process in a signing entity.
FIG. 9 is a flowchart illustrating an operation procedure of a verification process in a verification-side entity.
FIG. 10 is a diagram illustrating an example of a hardware configuration of an encryption device and a decryption device.
FIG. 11 is a diagram illustrating an example of a hardware configuration of a signature device and a verification device.
FIG. 12 is a diagram illustrating a configuration of an embodiment of a recording medium.
[Explanation of symbols]
1 center
1a Public key generation unit
1b Secret key generation unit
10 Encryption device
13 Encryption section
20 Decoding device
23 Decoding unit
30 Signature device
33 Signature Data Creation Unit
40 Verification device
42 Signature Data Verification Unit
50 communication channels
90 Computer
91, 92, 93 Recording medium
91a, 92a, 93a Computer program
A, B, U, V, Z entities

Claims

In a public key cryptography method for creating a cipher text using a public key based on specific information that specifies an entity that receives a cipher text, an algebraic curve that can define pairing with a result obtained by substituting the specific information into a polynomial A public key encryption method, wherein the ciphertext is created using the above points.

In a public key cryptography method that creates a cipher text using a public key based on specific information that identifies an entity that receives the cipher text, a polynomial function is set, and a point on an algebraic curve that can define pairing is selected. A public key encryption method, wherein the ciphertext is created using a function value obtained by substituting the specific information into the set polynomial function and the selected point.

For a group to which a plurality of entities belong, in a public key cryptographic method for independently creating a ciphertext for the group and a ciphertext for each of the plurality of entities, specifying information for specifying the group and each of the plurality of entities A public key cryptographic method using specific information.

In a signature method for verifying signature data created by a first entity by a second entity, an algebraic curve that can define a pairing with a result obtained by substituting identification information that identifies the first entity into a polynomial expression A signature method, wherein the signature data is created and verified using the above points.

In a signature method for verifying signature data created by a first entity by a second entity, a polynomial function is set, a point on an algebraic curve that can define pairing is selected, and the set polynomial function is assigned to the set polynomial function. A signature method, wherein the signature data is created and verified using a function value obtained by substituting identification information for identifying a first entity and the selected point.

For a group to which a plurality of entities belong, in a signature method of verifying signature data created by an entity belonging to the group with another entity belonging to the group or an entity not belonging to the group, identification information identifying the group; A signature method comprising using identification information that identifies the entity that creates the signature data.

In a cryptographic communication system in which a plurality of entities mutually perform encryption processing for encrypting plaintext, which is information to be transmitted, into ciphertext, and decryption processing for decrypting the transmitted ciphertext into plaintext, a public key and a public key are used. A center that generates a secret key of each entity based on specific information identifying each entity, and performs the encryption process using a public key based on the specific information of the entity to be transmitted, and uses its own secret key. A plurality of entities for performing the decoding process, and at the center, set a polynomial function and select a point on an algebraic curve that can define pairing, and at each entity, set the polynomial function Wherein the ciphertext is created by using a function value obtained by substituting the specific information into the specified information and the selected point. .

In a computer program for causing a computer to generate a public key and a secret key used for a public key cryptosystem or a signature system, a step of causing the computer to set a polynomial function; and a step of allowing the computer to define a pairing on an algebraic curve. Selecting a computer program.

A computer program for causing a computer to create a ciphertext using a public key based on specific information identifying an entity that receives the ciphertext, wherein the computer identifies points on an algebraic curve that can define polynomial functions and pairings. Causing the computer to substitute the specific information into the polynomial function to obtain a function value; and causing the computer to create the ciphertext using the obtained function value and the point. A computer program comprising:

A computer program for causing a computer to create the signature data using identification information that specifies an entity for which the signature data is created; and causing the computer to input a point on an algebraic curve that can define a polynomial function and pairing. Having the computer obtain the function value by substituting the specific information into the polynomial function, and causing the computer to create the signature data using the obtained function value and the point. Characteristic computer program.