(57)【要約】【課題】公開鍵と公開鍵証明書を更新する際のユーザ（利用端末）の負担を減らすこと、及び、更新を確実に行うことができるようにする。【解決手段】認証局ｃａの発行装置Ｄｃａは、ユーザｉが登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成部１０１と、これら補助情報と新しい公開鍵と公開鍵証明書とを利用端末Ｔｉに発行する発行部１０２とを備えている。利用端末Ｔｉは、自分の秘密情報と発行された補助情報とから新しい公開鍵に対応する秘密鍵を計算する計算部１０３を備えている。発行装置Ｄｃａでは、利用端末Ｔｉから情報を受け取る必要が無く、必要なときに単独で新しい公開鍵と公開鍵証明書を生成し、利用端末Ｔｉに発行できるので、利用端末Ｔｉでは新しい秘密鍵と公開鍵の生成を行う必要は無く、発行装置Ｄｃａに情報を送る必要も無い。【選択図】      図２
2005072648.tif 000002
【特許請求の範囲】
【請求項１】
発行装置と利用端末とを備えた公開鍵証明書システムであって、
上記発行装置は、上記利用端末が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成手段と、上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用端末に発行する発行手段とを有し、
上記利用端末は、自分の秘密情報と上記発行された補助情報とから上記新しい公開鍵に対応する秘密鍵を計算する計算手段を有し、
上記発行装置が適宜新しい公開鍵とそれに対応する公開鍵証明書とを上記利用端末に対して発行することを特徴とする公開鍵証明書システム。
【請求項２】
利用端末が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成手段と、
上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用端末に発行する発行手段とを備えたことを特徴とする発行装置。
【請求項３】
自分の秘密情報と発行装置から発行された補助情報とから、上記発行装置で生成された新しい公開鍵に対応する秘密鍵を計算する計算手段を備えたことを特徴とする利用端末。
【請求項４】
利用者と発行者との間で行われる公開鍵及び公開鍵証明書の更新方法であって、
上記発行者側では、上記利用者が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成処理と、上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用者に発行する発行処理とを行い、
上記利用者側では、自分の秘密情報と上記発行された補助情報とから上記新しい公開鍵に対応する秘密鍵を計算する計算処理を行い、
上記発行者が適宜新しい公開鍵とそれに対応する公開鍵証明書とを上記利用者に対して発行することを特徴とする公開鍵及び公開鍵証明書の更新方法。
【請求項５】
利用者が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成処理と、
上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用者に発行する発行処理とを行うことを特徴とする公開鍵及び公開鍵証明書の更新方法。
【請求項６】
自分の秘密情報と発行者から発行された補助情報とから、上記発行者により生成された新しい公開鍵に対応する秘密鍵を計算する計算処理を行うことを特徴とする公開鍵及び公開鍵証明書の更新方法。
【請求項７】
請求項２に記載の発行装置の各手段又は請求項３に記載の利用端末の各手段としてコンピュータを機能させることを特徴とするコンピュータプログラム。
【請求項８】
請求項５又は６に記載の公開鍵及び公開鍵証明書の更新方法の各処理をコンピュータに実行させることを特徴とするコンピュータプログラム。
【請求項９】
請求項７又は８に記載のコンピュータプログラムを格納したことを特徴とするコンピュータ読み取り可能な記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、公開鍵証明書システム、発行装置、利用端末、公開鍵及び公開鍵証明書の更新方法、コンピュータプログラム、及びコンピュータ読み取り可能な記憶媒体に係り、公開鍵と公開鍵証明書を更新するのに好適なものに関する。
【０００２】
【従来の技術】
インターネットの普及に伴って、暗号が使われる機会が増えている。後述するように、暗号には共通鍵暗号と公開鍵暗号があり、共通鍵暗号を用いると高速な暗号化が実現でき、公開鍵暗号を用いると暗号化の機能に加えて認証機能（ディジタル署名）をも実現できる。インターネット上での安全な通信や電子商取引に、暗号は欠かせないものとなっている。
【０００３】
公開鍵暗号を利用する場合、公開鍵とユーザの対応を保証するための公開鍵証明書が用いられることが多い。ところで、安全のため公開鍵を適宜更新（変更）することが望ましいが、公開鍵を更新する際には、公開鍵証明書も一緒に更新しなければならない。以下では、最初に暗号について説明し、次に公開鍵証明書について、そしてその更新について説明する。
【０００４】
［暗号］
暗号とは、情報の意味が当事者以外にはわからないように情報を変換することをいう。暗号において、元の文を平文といい、それを第三者に意味の分からない暗号文に変えることを暗号化、その変換手順を暗号アルゴリズムという。平文、暗号文といっても、テキストに限るわけではなく、データ、音声、画像等あらゆる情報を想定している。暗号化は、暗号化鍵というパラメータに依存する変換である。当事者が暗号文を元の平文に戻すことを復号といい、暗号化鍵に対応するパラメータ、復号鍵と呼ぶ、を用いて行う。当事者以外の第三者が暗号文を元の平文に戻すこと、或いは復号鍵を見出すことを、解読という。
【０００５】
現代の暗号では、暗号の安全性を暗号化或いは復号に用いる鍵に帰着させており、鍵を知らなければ、たとえ暗号アルゴリズムを知っていても平文は得られないようになっている。従って、暗号装置の製作者でも解読できない暗号を実現することができる。
【０００６】
暗号には多くのアルゴリズムがあるが、以下では、暗号化鍵を公開できるか否かの観点から、非対称暗号（公開鍵暗号）と対称暗号（共通鍵暗号）の二つに分類する。
【０００７】
［非対称暗号（公開鍵暗号）］
非対称暗号は公開鍵暗号とも呼ばれ、暗号化鍵と復号鍵とが異なり、暗号化鍵から復号鍵が容易に計算できないようになっており、暗号化鍵を公開、復号鍵を秘密に保持して使われる暗号のことをいう。
【０００８】
非対称暗号は、以下の特徴を持つ。すなわち、１．暗号化鍵と復号鍵とが異なり、暗号化鍵を公開できるため、暗号化鍵を秘密に配送する必要がなく、鍵配送が容易である。２．各利用者の暗号化鍵は公開されるので、利用者は各自の復号鍵のみ秘密に記憶しておけばよい。３．送られてきた通信文の送信者が偽者でないこと及びその通信文が改ざんされていないことを受信者が確認するための認証機能（ディジタル署名）を実現できる。
【０００９】
暗号機能と認証機能を実現できる非対称暗号として、ＲＳＡ暗号（非特許文献１）や、ＥｌＧａｍａｌ暗号（非特許文献２）が有名である。
【００１０】
認証機能（ディジタル署名）を実現できる非対称暗号として、Ｆｉａｔ−Ｓｈａｍｉｒ暗号（非特許文献３）や、Ｓｃｈｎｏｒｒ暗号（非特許文献４）が有名である。
【００１１】
一例として、ＥｌＧａｍａｌ暗号による暗号機能と、ＥｌＧａｍａｌ暗号を修正した暗号によるディジタル署名方式について詳しく述べる。この修正ＥｌＧａｍａｌ暗号によるディジタル署名方式は、非特許文献５で安全性が証明されている。
【００１２】
まず、記号の準備をする。Ｚは整数全体の集合、Ｚｐは０以上ｐ未満の整数の集合、Ｚｐ＼｛０｝はＺｐから０を除いた集合、Ｚｐ＊はＺｐの要素でありかつｐと互いに素である整数の集合を表す。整数Ａ，Ｂ，Ｃに対しＡ＝ＢｍｏｄＣが成り立つとき、ＢをＣで割ったときの余りがＡである（ある整数ｋが存在し、Ｂ＝ｋ・Ｃ＋Ａが成り立つ）ことを意味し、Ａ≡Ｂ（ｍｏｄＣ）が成り立つとき、ＡをＣで割ったときの余りとＢをＣで割ったときの余りとが等しいことを意味する。
【００１３】
次のような、素数ｐ、整数ｇ、及び一方向性ハッシュ関数を用いる。素数ｐは、ｐ−１が少なくとも一つの大きな素因数を持つ。整数ｇは、Ｚｐ＊の要素でありかつ位数がｐ−１である。ｇが位数ｐ−１であるとは、下記の数１に示す関係が成り立つことである。
【００１４】
【数１】
2005072648.tif 000003
【００１５】
一方向性ハッシュ関数とは、衝突を起こしにくい圧縮関数のことであり、ある長さのビット列を出力する関数で、同じ出力となる入力を見つけることが困難であるという特徴を持つ。具体的には、一方向性ハッシュ関数は、下記の数２に示す式で表される。
【００１６】
【数２】
2005072648.tif 000004
【００１７】
すなわち、２つの入力を１つの出力に変換する関数であり、最初の入力はＺｐの要素、２つめの入力はＺの要素であり、出力は｛０，１，…，２ｔ−１｝のいずれかの要素となるものである。なお、ｔはセキュリティ・パラメータである。
【００１８】
あるユーザｉの秘密鍵をｓｉ∈Ｚｐ−１、公開鍵をｖｉ＝ｇｓｉｍｏｄｐとする。ｐとｇは複数のユーザが共通に使うことができる。以下では、共通に使われるものとして説明する。
【００１９】
（ＥｌＧａｍａｌ暗号の）暗号化
ユーザｊが、メッセージｍ（∈Ｚｐ）を暗号化してユーザｉに送る場合、次のようにして行う。メッセージがＺｐの要素でない場合（ｐ以上の数値の場合）は、Ｚｐの要素になるよう適当に分割し、分割したそれぞれに対して暗号化する。
【００２０】
１．ユーザｊは乱数ｋを生成する。
２．ユーザｊはＣ１＝ｇｋｍｏｄｐを計算する。
３．ユーザｊはＣ２＝ｍ・ｖｉｋｍｏｄｐを計算する。
４．ユーザｊは、Ｃ１とＣ２をユーザｉに送る。
【００２１】
（ＥｌＧａｍａｌ暗号の）復号
１．ユーザｉはｍ＝Ｃ２／Ｃ１ｓｉｍｏｄｐにより、ｍを求める。
【００２２】
（修正ＥｌＧａｍａｌ暗号の）ディジタル署名の生成
ユーザｉがメッセージｍ∈Ｚに対してディジタル署名を生成する場合、次のように行う。暗号化のようにメッセージを複数ブロックに分割する方法もあるが、以下では一方向性ハッシュ関数を用いる方法を説明する。
１．ユーザｉは乱数ｋ∈Ｚｐ−１＊を生成する。
２．ユーザｉはｒ＝ｇｋｍｏｄｐを計算する。
３．ユーザｉは下記の数３に示す式を満たすｓ（ｍｏｄ（ｐ−１））計算する。
【００２３】
【数３】
2005072648.tif 000005
【００２４】
４．ユーザｉはｍと署名ｒ，ｓを検証者に送る。
【００２５】
（修正ＥｌＧａｍａｌ暗号の）ディジタル署名の検証
１．ユーザｊは下記の数４に示す式を確認する。
【００２６】
【数４】
2005072648.tif 000006
【００２７】
［対称暗号（公開鍵暗号）］
対称暗号は、暗号化鍵と復号鍵が同一の暗号であり、共通鍵暗号とも呼ばれる。１９７０年代後半に公開鍵暗号が現れて、従来から存在する対称暗号は慣用暗号とも呼ばれるようになった。対称暗号は、適当な長さの文字列（ブロック）ごとに同じ鍵で暗号化するブロック暗号と文字列又はビットごとに鍵を変えていくストリーム暗号に分けることができる。
【００２８】
ブロック暗号には、文字の順序を置き換えて暗号化する転置式暗号や、文字を他の文字に換える換字式暗号等があり、アルゴリズムが公開さ札でいるＤＥＳ（Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ｓｔａｎｄａｒｄ）やＩＤＥＡ（Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｄａｔａ  Ｅｎｃｒｙｐｔｉｏｎ  Ａｌｇｏｒｉｔｈｍ）が有名である。
【００２９】
ストリーム暗号は、メッセージに乱数をＸＯＲして内容を撹乱する方式であり、無限周期の乱数列を１回限りの使い捨て鍵として用いるバーナム暗号が有名である。
【００３０】
暗号に関しては、非特許文献６〜８に更に詳しい説明がある。
【００３１】
［公開鍵証明書（Ｐｕｂｌｉｃ  Ｋｅｙ  Ｃｅｒｔｉｆｉｃａｔｅｓ）］
公開鍵証明書とは、公開鍵とそれに対応するユーザの識別情報（ＩＤ）の組が正しいことを、信頼できる第三者が保証した証明書である。この信頼できる第三者は認証局（Ｃｅｒｔｉｆｉｃａｔｉｏｎ  Ａｕｔｈｏｒｉｔｙ）と呼ばれ、公開鍵証明書は具体的には認証局によるディジタル署名であり、そのディジタル署名の正当性を確認するための認証局の公開鍵は何らかの手段で広く知られている。
【００３２】
公開鍵証明書の発行は、以下のような手順で行われる（図３を参照）。以下では、認証局をＣＡ、ユーザをｉと表す。整数論に関する記号の定義は、前述の説明と同じとする。認証局ＣＡの秘密鍵をｓｃａ∈Ｚｐ−１＊、公開鍵をｖｃａ＝ｇｓｃａｍｏｄｐ、ユーザｉの秘密鍵をｓｉ∈Ｚｐ−１＊、公開鍵をｖｉ＝ｇｓｉｍｏｄｐとする。認証局ＣＡ及びユーザｉが行う計算や通信等の処理は、実際には計算機や通信ネットワークによって実現される。認証局ＣＡとユーザｉの計算や通信を行う実際の機械を、それぞれ発行装置Ｄｃａと利用端末Ｔｉとし、それらは認証局ＣＡ及びユーザｉによって適切に管理されているものとする。
【００３３】
１．ユーザｉは、利用端末Ｔｉを用いて、秘密鍵ｓｉ∈Ｚｐ−１＊と公開鍵ｖｉ＝ｇｓｉｍｏｄｐを生成し、公開鍵ｖｉを認証局ＣＡに提出し、公開鍵証明書の発行を申請する。
【００３４】
２．認証局ＣＡは、何らかの手段、例えば、パスポートでユーザｉの身元を確認し、提出された公開鍵ｖｉをデータベースに登録する。
【００３５】
３．発行装置Ｄｃａは、ユーザｉの識別情報ＩＤｉと公開鍵ｖｉと証明書の管理や運用に用いる情報Ｘに対するディジタル署名を生成する。Ｘは、その証明書のシリアル番号、有効期限、認証局の公開鍵等の情報を含む。メッセージＭに対する発行装置Ｄｃａのディジタル署名をＳｉｇｃａ（Ｍ）と表すと、（ｖｉ，ＩＤｉ，Ｘ，Ｓｉｇｃａ（ｖｉ，ＩＤｉ，Ｘ））がユーザｉの証明書ＰＫＣｉになる。一具体例として、発行装置が修正ＥｌＧａｍａｌ暗号のディジタル署名方式を用いる場合を以下に述べる。発行装置Ｄｃａは乱数ｋ∈Ｚｐ−１＊を生成し、ｒ＝ｇｋｍｏｄｐを計算する。下記の数５に示す式を満たすｓ（ｍｏｄ（ｐ−１））を計算する。
【００３６】
【数５】
2005072648.tif 000007
【００３７】
ここで、‖は連接を表し、Ｓｉｇｃａ（ｖｉ，ＩＤｉ，Ｘ）をＳｉｇｃａ（ｖｉ‖ＩＤｉ‖Ｘ）＝（ｒ，ｓ）とした。ただし、必ずしも‖を使わなければならないというわけではなく、複数の値を一つの値にまとめることが可能で、まとめられた値から複数の元の値を取り出せる演算子であればよい。
【００３８】
４．発行装置Ｄｃａは、証明書ＰＫＣｉ＝（ｖｉ，ＩＤｉ，Ｘ，Ｓｉｇｃａ（ｖｉ，ＩＤｉ，Ｘ））＝（ｖｉ，ＩＤｉ，Ｘ，ｒ，ｓ）をユーザｉに発行する。証明書ＰＫＣｉは、利用端末Ｔｉに格納される。
【００３９】
５．利用端末Ｔｉは、ＰＫＣｉ＝（ｖｉ，ＩＤｉ，Ｘ，Ｓｉｇｃａ（ｖｉ，ＩＤｉ，Ｘ））＝（ｖｉ，ＩＤｉ，Ｘ，ｒ，ｓ）を受け取ったら、公開鍵ｖｉとＩＤｉ及びＸに対する発行装置Ｄｃａの署名Ｓｉｇｃａ（ｖｉ，ＩＤｉ，Ｘ）の正当性を確認する。つまり、下記の数６に示す式を確認する（公開鍵証明書の発行手順終了）。
【００４０】
【数６】
2005072648.tif 000008
【００４１】
ユーザｉと通信するユーザｊ、すなわち利用端末ｉと通信する利用端末ｊは、ＰＫＣｉ＝（ｖｉ，ＩＤｉ，Ｘ，ｒ，ｓ）を入手し、上記の数６に示した式を確認する。
【００４２】
この確認を行なった利用端末ｊは、ｖｉを公開鍵として用いて、離散対数問題に基づく暗号方式を利用して通信文を暗号化し、暗号文を利用端末ｉに送信できる。或いは、利用端末ｉから受け取った、離散対数問題に基づくディジタル署名の正当性をｖｉを用いて確認できる。
【００４３】
公開鍵証明書には有効期限があるが、何らかの原因で変更されて無効になったが有効期隈を過ぎていない証明書は、発行装置Ｄｃａによって証明書無効化リスト（Ｃｅｒｔｉｆｉｃａｔｅ  Ｒｅｖｏｃａｔｉｏｎ  Ｌｉｓｔｓ）に載せられる。ところで、安全のため公開鍵を適宜更新（変更）することが望ましいが、公開鍵を更新する際には公開鍵証明書も一緒に更新しなければならない。
【００４４】
［従来の公開鍵と公開鍵証明書の更新手続き］
公開鍵と公開鍵証明書の更新手続きは、通常は以下のように行われる（図４を参照）。
１．ユーザｉは、利用端末Ｔｉを用いて、秘密鍵ｓｉ´∈Ｚｐ−１＊と公開鍵ｖｉ´＝ｇｓｉ´ｍｏｄｐを生成し、公開鍵ｖｉ´を認証局ＣＡに提出する。
【００４５】
２．認証局ＣＡは初期登録のときと同様に、何らかの手段でユーザｉの身元を確認し、提出された公開鍵ｖｉ´を登録する。発行装置Ｄｃａは、新しい公開鍵証明書ＰＫＣｉ´＝（ｖｉ´，ＩＤｉ，Ｘ´，Ｓｉｇｃａ（ｖｉ´，ＩＤｉ，Ｘ´））を生成，発行する。Ｘ´は、その証明書のシリアル番号、有効期限、認証局の公開鍵等の（更新された）情報を含む。ＰＫＣｉの有効期限が残っている場合は、ＰＫＣｉを証明書無効化リストに載せる。
【００４６】
３．利用端末ｉは、公開鍵ｖｉ´とＩＤｉ及びＸ´に対する発行装置の署名Ｓｉｇｃａ（ｖｉ´，ＩＤｉ，Ｘ´）の正当性を確認する。
【００４７】
以上により、公開鍵と公開鍵証明書の更新手続きは終了する。この更新手続きは、更新の都度繰り返される。
【００４８】
【非特許文献１】
Ｒ．  Ｌ．  Ｒｉｖｅｓｔ，  Ａ．  Ｓｈａｍｉｒ  ａｎｄ  Ｌ．  Ａｄｌｅｍａｎ，“Ａ  ｍｅｔｈｏｄ  ｏｆ  ｏｂｔａｉｎｉｎｇ  ｄｉｇｉｔａｌ  ｓｉｇｎａｔｕｒｅｓ  ａｎｄ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍｓ，”Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  ｏｆ  ＡＣＭ，  ｖｏｌ．２１，  Ｎｏ．２，  ｐｐ．  １２０−１２６，  １９７８
【非特許文献２】
Ｔ．  Ｅ．  ＥｌＧａｍａｌ，“Ａ  ｐｕｂｌｉｃ  ｋｅｙ  ｃｒｙｐｔｏｓｙｓｔｅｍ  ａｎｄ  ａ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅ  ｂａｓｅｄ  ｏｎ  ｄｉｓｃｒｅｔｅ  ｌｏｇａｒｉｔｈｍｓ，”ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，  Ｖｏｌ．  ＩＴ−３１，  Ｎｏ．４，  ｐｐ．４６９−４７２，  １９８５
【非特許文献３】
Ａ．  Ｆｉａｔ，  Ａ．  Ｓｈａｍｉｒ，“Ｈｏｗ  ｔｏ  ｐｒｏｖｅ  ｙｏｕｒｓｅｌｆ：  ｐｒａｃｔｉｃａｌ  ｓｏｌｕｔｉｏｎｓ  ｏｆ  ｉｄｅｎｔｉｆｉｃａｔｉｏｎ  ａｎｄ  ｓｉｇｎａｔｕｒｅ  ｐｒｏｂｌｅｍｓ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −
ＣＲＹＰＴ  ｀８６，  ｐｐ．  １８６−１９４，１９８７
【非特許文献４】
Ｃ．  Ｐ．  Ｓｃｈｎｏｒｒ，“Ｅｆｆｉｃｉｅｎｔ  ｓｉｇｎａｔｕｒｅ  ｇｅｎｅｒａｔｉｏｎ  ｂｙ  ｓｍａｒｔ  ｃａｒｄｓ，”Ｊｏｕｒｎａｌ  ｏｆ  Ｃｒｙｐｔｏｌｏｇｙ，  ｖｏｌ．４，  ｐｐ．１６１−１７４，  １９９１
【非特許文献５】
Ｄ．  Ｐｏｉｎｔｃｈｅｖａｌ，  Ｊ．  Ｓｔｅｒｎ，“Ｓｅｃｕｒｉｔｙ  ｐｒｏｏｆｓ  ｆｏｒ  ｓｉｇｎａｔｕｒｅ  ｓｃｈｅｍｅｓ，”Ａｄｖａｎｃｅｓ  ｉｎ  Ｃｒｙｐｔｏｌｏｇｙ  −  ＥＵＲＯＣＲＹＰＴ  ｀９６，  ｐｐ．３８７−３９８，  Ｓｐｒｉｎｇｅｒ  −  Ｖｅｒｌａｇ，１９９６
【非特許文献６】
岡本栄司著、暗号理論入門、共立出版株式会社
【非特許文献７】
岡本龍明、山本博資著、現代暗号、産業図書
【非特許文献８】
Ｂｒｕｃｅ  Ｓｃｈｎｅｉｅｒ著、Ａｐｐｌｉｅｄ  ｃｒｙｐｔｏｇｒａｐｈｙ  ｓｅｃｏｎｄ  ｅｄｉｔｏｎ：ｐｒｏｔｏｃｏｌｓ，  ａｌｇｏｒｉｔｈｍｓ，  ａｎｄ  ｓｏｕｒｃｅ  ｃｏｄｅ  ｉｎ  Ｃ，  Ｊｏｈｎ  Ｗｉｌｅｙ  ＆  Ｓｏｎｓ，  Ｉｎｃ．
【００４９】
【発明が解決しようとする課題】
上述の更新手続から明らかなように、公開鍵の更新と公開鍵証明書の更新を行うためには、新しい秘密鍵と公開鍵を生成するための計算と、認証局ＣＡへの公開鍵の登録（物理的に出向いて行う提出或いは通信による提出）が必要となる。
そのため、ユーザ（利用端末Ｔｉ）は更新回数に比例する計算量と登録のコスト（ユーザが発行装置Ｄｃａのところに出頭する物理的な移動コスト或いは発行装置Ｄｃａへ送信するコスト）がかかってしまう。特に、秘密鍵と公開鍵の生成は計算量が大きいため、負担となってしまうという問題があった。また、ユーザが更新を怠けたり、忘れたりしてしまうことも問題であった。
【００５０】
本発明は、上記のような点に鑑みてなされたものであり、公開鍵と公開鍵証明書を更新する際のユーザ（利用端末）の負担を減らすこと、及び、更新を確実に行うことができるようにすることを目的とする。
【００５１】
【課題を解決するための手段】
本発明の公開鍵証明書システムは、発行装置と利用端末とを備えた公開鍵証明書システムであって、上記発行装置は、上記利用端末が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成手段と、上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用端末に発行する発行手段とを有し、上記利用端末は、自分の秘密情報と上記発行された補助情報とから上記新しい公開鍵に対応する秘密鍵を計算する計算手段を有し、上記発行装置が適宜新しい公開鍵とそれに対応する公開鍵証明書とを上記利用端末に対して発行する点に特徴を有する。
【００５２】
また、本発明の公開鍵及び公開鍵証明書の更新方法は、利用者と発行者との間で行われる公開鍵及び公開鍵証明書の更新方法であって、上記発行者側では、上記利用者が登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成処理と、上記補助情報と上記新しい公開鍵と上記公開鍵証明書とを上記利用者に発行する発行処理とを行い、上記利用者側では、自分の秘密情報と上記発行された補助情報とから上記新しい公開鍵に対応する秘密鍵を計算する計算処理を行い、上記発行者が適宜新しい公開鍵とそれに対応する公開鍵証明書とを上記利用者に対して発行する点に特徴を有する。
【００５３】
【発明の実施の形態】
以下、図面を参照して、本発明の公開鍵証明書システム、発行装置、利用端末、公開鍵及び公開鍵証明書の更新方法、コンピュータプログラム、及びコンピュータ読み取り可能な記憶媒体の実施の形態について説明する。
【００５４】
図１に示すように、本実施の形態のシステムは、認証局ＣＡの発行装置Ｄｃａと、ユーザｉの利用端末Ｔｉとにより構成されている。
【００５５】
発行装置Ｄｃａは、利用端末Ｔｉが登録した情報と乱数を基にして、補助情報と新しい公開鍵と新しい公開鍵に対する公開鍵証明書とを生成する生成部１０１と、補助情報と新しい公開鍵と公開鍵証明書とを利用端末Ｔｉに発行する発行部１０２とを備えている。
【００５６】
利用端末Ｔｉは、自分の秘密情報と発行された補助情報とから新しい公開鍵に対応する秘密鍵を計算する計算部１０３を有する。
【００５７】
上記発行装置Ｄｃａは、適宜新しい公開鍵とそれに対応する公開鍵証明書とを上記利用端末Ｔｉに対して発行する。
【００５８】
（第１の実施の形態における公開鍵と公開鍵証明書の更新手続き）
第１の実施の形態におけるプロトコルを図２に示す。なお、図２には、ステップ０として、下記手順が書かれている。
【００５９】
０１．ユーザｉが、利用端末Ｔｉを用いて、秘密鍵ｓｉ∈Ｚｐ−１＊と公開鍵ｖｉ＝ｇｓｉｍｏｄｐを生成し、公開鍵ｖｉを認証局ＣＡに提出し、公開鍵証明書の発行を申請する。
０２．認証局ＣＡが何らかの手段でユーザｉの身元を確認し、提出された公開鍵ｖｉをデータベースに登録する。
０３．発行装置Ｄｃａが最初の公開鍵証明書ＰＫＣｉを生成する。
０４．発行装置Ｄｃａが最初の公開鍵証明書ＰＫＣｉを発行する。
０５．利用端末Ｔｉは、公開鍵証明書ＰＫＣｉの正当性を確認する。
【００６０】
この手順は、ユーザｉがシステムに加入する際に一度だけ行われ、更新手続きには含まれない。なお、ステップ０３からステップ０５までの、公開鍵証明書ＰＫＣｉを生成・発行し確認する手続きを省き、いきなりＰＫＣｉ´を発行しても構わない。
【００６１】
更新手続きのプロトコルは以下の通りである。
１．発行装置Ｄｃａは、乱数ｒ´∈Ｚｐ−１＊を生成し、ｖｉ´＝ｖｉｒ´ｍｏｄｐを求める。
【００６２】
２．発行装置Ｄｃａは、更新された公開鍵ｖｉ´をデータベースに登録し、ユーザｉの識別情報ＩＤｉと公開鍵ｖｉ´と証明書の管理に必要な情報Ｘ´に対するディジタル署名を生成する。Ｘ´は、その証明書のシリアル番号、有効期限、認証局の公開鍵等の（更新された）情報を含む。ユーザｉの証明書ＰＫＣｉ´は（ｖｉ´，ＩＤｉ，Ｘ´，Ｓｉｇｃａ（ｖｉ´，ＩＤｉ，Ｘ´））である。
【００６３】
３．発行装置Ｄｃａは、乱数ｒ´と更新された証明書ＰＫＣｉ´＝（ｖｉ´，ＩＤｉ，Ｘ´，Ｓｉｇｃａ（ｖｉ´，ＩＤｉ，Ｘ´））をユーザｉに発行する。乱数ｒ´は、ｖｉを用いる公開鍵暗号により暗号化され、ユーザｉに送られる。
【００６４】
４．利用端末Ｔｉは、ＰＫＣｉ´＝（ｖｉ´，ＩＤｉ，Ｘ´，Ｓｉｇｃａ（ｖｉ´，ＩＤｉ，Ｘ´））と乱数ｒ´の暗号文を受け取ったら、公開鍵ｖｉ´とＩＤｉ及びＸ´に対する発行装置の署名の正当性を確認し、ｒ´を復号し、ｖｉ´≡ｖｉｒ´≡ｇＳｉ・ｒ´（ｍｏｄｐ）を確認する。
【００６５】
以上により、更新手続きが終了する。この更新手続きは、更新の都度繰り返される。
【００６６】
上記の証明書ＰＫＣｉ´を発行されたユーザｉは、ｖｉ´を公開鍵、ｓｉ´＝ｓｉ・ｒ´ｍｏｄ（ｐ−１）を秘密鍵として、公開鍵暗号を利用できる。なお、上記実施の形態ではｒ´をｖｉを用いる公開鍵暗号で暗号化する例を述べたが、ｒ´がユーザｉに送られるときに、安全な通信路を用いてユーザｉ（利用端末Ｔｉ）のみにｒ´を確実に渡すことができるのであれば、ｖｉを用いる公開鍵暗号に限る必要はなく、他の手段を用いても問題はない。
【００６７】
（第２の実施の形態）
上記第１の実施の形態においては、新しい公開鍵としてｖｉのみが変更され、底ｇと法ｐは変更されなかった。本実施の形態では、公開鍵及び底が変更される例を説明する。
【００６８】
１．発行装置Ｄｃａは、乱数ｒ＾∈Ｚｐ−１＊を生成し、ｇ＾＝ｖｉｒ＾ｍｏｄｐを計算するととも、下記の数７に示す式を計算し、下記の数８に示す式を満たすｓｉ＾を求める。Ｘ＾は、その証明書のシリアル番号、有効期限、認証局の公開鍵等の（更新された）情報を含む。
【００６９】
【数７】
2005072648.tif 000009
【００７０】
【数８】
2005072648.tif 000010
【００７１】
２．次に、発行装置Ｄｃａは、Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾）を求める。
【００７２】
３．発行装置Ｄｃａは、ＰＫＣｉ＾＝（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾，Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾））とｓｉ＾をユーザｉに発行する。ｓｉ＾は、ｖｉを用いる公開鍵暗号により暗号化されて送られる。
【００７３】
４．ＰＫＣｉ＾より前に発行した公開鍵証明書の有効期限が残っている場合は、発行装置Ｄｃａはそれらを証明書無効化リストに載せる。
【００７４】
利用端末Ｔｉは、以下のような処理を行う。
１．ＰＫＣｉ＾＝（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾，Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾））とｓｉ＾の暗号文を受け取った利用端末Ｔｉは、ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾に対する発行装置のディジタル署名Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾）の正当性を確認する。
【００７５】
２．次に、ｓｉ＾を復号し、ｓｉ´´・ｓｉ≡ｓｉ＾（ｍｏｄ（ｐ−１））を満たすｓｉ´´を計算し、下記の数９に示す式を確認する。
【００７６】
【数９】
2005072648.tif 000011
【００７７】
以上により、更新手続きが終了する。この更新手続きは、更新の都度繰り返される。
【００７８】
なお、上記実施の形態では、ｓｉ＾をｖｉを用いる公開鍵暗号で暗号化する例を述べたが、ｓｉ＾がユーザｉに送られるときに、安全な通信路を用いてユーザｉ（利用端末Ｔｉ）のみに確実に渡すことができるのであれば、ｖｉを用いる公開鍵暗号に限る必要はなく、他の手段を用いても問題はない。
【００７９】
ディジタル署名を利用する場合、ユーザｉ（利用端末Ｔｉ）は、ｖｉの代わりにｖｉ＾を、ｇの代わりにｇ＾を、ｓｉの代わりにｓｉ´´を用いて、離散対数問題に基づくディジタル署名方式を利用する。暗号通信を行う場合、ユーザｊ（利用端末Ｔｊ）は、ｖｉの代わりにｖｉ＾を、ｇの代わりにｇ＾を用いて、離散対数問題に基づく暗号方式を利用して通信文をユーザｉ（利用端末Ｔｉ）に送る。
【００８０】
一具体例として、ユーザｉ（利用端末Ｔｉ）がディジタル署名方式として修正ＥｌＧａｍａｌ暗号のディジタル署名方式を用いる場合を述べる。
【００８１】
１．利用端末Ｔｉは、メッセージｍ∈Ｚに対して、乱数ｋｉ∈Ｚｐ−１＊を生成し、ｓｉｇ１＝ｇ＾ｋｉｍｏｄｐを計算し、下記の数１０に示す式を満たすｓｉｇ２を求める。
【００８２】
【数１０】
2005072648.tif 000012
【００８３】
２．利用端末Ｔｉは、ＰＫＣｉ＾とｍと署名（ｓｉｇ１，ｓｉｇ２）を検証者（他の端末）に送る。
【００８４】
３．検証者（他の端末）は、ＰＫＣｉ＾＝（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾，Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾））の正当性を、認証局ＣＡの公開鍵で確認し、ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾が認証局ＣＡによって保証されていることを確かめる。
【００８５】
４．検証者（他の端末）は、下記の数１１に示す式を確認する。
【００８６】
【数１１】
2005072648.tif 000013
【００８７】
（第３の実施の形態）
上記第２の実施の形態では、認証局ＣＡがｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾に対するディジタル署名Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾）を生成し、ユーザに発行していた。ところで、下記の数１２に示す式を満たすｇ＾とｓｉ´´を求めることは、認証局ＣＡとユーザｉの両者が前述の手続きに従うときのみに限って可能である。
【００８８】
【数１２】
2005072648.tif 000014
【００８９】
認証局ＣＡは、ｇ＾とｓｉ´を求めることはできるが、ユーザｉの秘密情報ｓｉを知らないので、ｓｉ´´≡（ｓｉ＾／ｓｉ）・（ｍｏｄ（ｐ−１））を単独で求めることはできない。一方、認証局ＣＡの秘密情報ｓｃａを知らないユーザｉは、ｇ＾とｓｉ´を単独で求めることはできない。また、認証局ＣＡでも、ユーザｉでもない複数のユーザが協力したとしてもｓｉもｓｃａも知らないので、ｇ＾とｓｉ´´を求めることはできない。
【００９０】
よって、下記の数１３に示す式を満たすｓｉ´´を有するユーザは、認証局ＣＡからｓｉ＾を発行されたユーザのみである。
【００９１】
【数１３】
2005072648.tif 000015
【００９２】
ところで、下記の数１４に示す式は、ｇ＾とＸ＾を除けばすべて公開の情報であるので、ｇ＾とＸ＾が与えられれば誰でも計算して求めることができる。よって、ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾に対する認証局ＣＡのディジタル署名Ｓｉｇｃａ（ｇ＾，ｖｉ＾，ＩＤｉ，Ｘ＾）を省くことができる。
【００９３】
【数１４】
2005072648.tif 000016
【００９４】
この場合、（ｇ＾，ＩＤｉ，Ｘ＾）が公開鍵でありかつ公開鍵証明書をも兼ねているとみなすことができる。ｇ＾，ＩＤｉ，Ｘ＾の正当性は、その正規の所有者（利用端末）が生成したディジタル署名の正当性を検証するときに同時に確認可能である。
【００９５】
一具体例として、前述の具体例と同じ修正ＥｌＧａｍａｌ暗号のディジタル署名をユーザｉ（利用端末Ｔｉ）が用いる場合を説明する。
【００９６】
１．発行装置Ｄｃａは、乱数ｒ〜∈Ｚｐ−１＊を生成し、ｇ〜＝ｖｉｒ〜ｍｏｄｐを計算する。
【００９７】
２．次に、発行装置Ｄｃａは、下記の数１５に示す式を満たすｓｉ〜を求める。Ｘ〜は、その証明書のシリアル番号、有効期限、認証局の公開鍵等の（更新された）情報を含む。
【００９８】
【数１５】
2005072648.tif 000017
【００９９】
３．発行装置Ｄｃａは、ＰＫＣｉ〜＝（ｇ〜，ＩＤｉ，Ｘ〜）とｓｉ〜を利用端末Ｔｉに発行する。ｓｉ〜は、ｖｉを用いる公開鍵暗号によって暗号化されて送られる。
【０１００】
４．ＰＫＣｉ〜より前に発行した公開鍵証明書の有効期限が残っている場合は、発行装置Ｄｃａは、それらを証明書無効化リストに載せる。
【０１０１】
５．ＰＫＣｉ〜を受け取った利用端末Ｔｉは、ｓｉ〜を復号し、ｓｉ´´´・ｓｉ≡ｓｉ〜（ｍｏｄ（ｐ−１））を満たすｓｉ´´´（ｍｏｄ（ｐ−１）を計算し、下記の数１６に示す式を確認する。
【０１０２】
【数１６】
2005072648.tif 000018
【０１０３】
６．次に、利用端末Ｔｉは、メッセージｍ∈Ｚに対して、乱数ｋｉ∈Ｚｐ−１＊を生成し、ｓｉｇ１＝ｇｋｉ〜ｍｏｄｐを計算し、下記の数１７に示す式を満たすｓｉｇ２を求める。
【０１０４】
【数１７】
2005072648.tif 000019
【０１０５】
７．利用端末Ｔｉは、ＰＫＣｉ〜＝（ｇ〜，ＩＤｉ，Ｘ〜）とｍと署名（ｓｉｇ１，ｓｉｇ２）を検証者（他の端末）に送る。
【０１０６】
８．検証者（他の端末）は、下記の数１８に示す式を確認する。
【０１０７】
【数１８】
2005072648.tif 000020
【０１０８】
この簡略化された公開鍵証明書は、通常の公開鍵証明書には必要な、公開鍵に対する発行装置のディジタル署名を省くことができるため、証明書全体のサイズが小さいという特徴がありメモリのコストを下げる効果がある。
【０１０９】
なお、上記実施の形態では、ｓｉ〜をｖｉを用いる公開鍵暗号で暗号化する例を述べたが、ｓｉ〜がユーザｉに送られるときに、安全な通信路を用いてユーザｉ（利用端末Ｔｉ）のみに確実に渡すことができるのであれば、ｖｉを用いる公開鍵暗号に限る必要はなく、他の手段を用いても問題はない。
【０１１０】
（その他の実施の形態）
上述した実施の形態の機能を実現するべく各種のデバイスを動作させるように、該各種デバイスと接続された装置或いはシステム内のコンピュータに対し、上記実施の形態の機能を実現するためのソフトウェアのプログラムコードを供給し、そのシステム或いは装置のコンピュータ（ＣＰＵ或いはＭＰＵ）に格納されたプログラムに従って上記各種デバイスを動作させることによって実施したものも、本発明の範疇に含まれる。
【０１１１】
また、この場合、上記ソフトウェアのプログラムコード自体が上述した実施の形態の機能を実現することになり、そのプログラムコード自体は本発明の範疇に含まれる。そのプログラムコードの伝送媒体としては、プログラム情報を搬送波として伝搬させて供給するためのコンピュータネットワーク（ＬＡＮ、インターネット等のＷＡＮ、無線通信ネットワーク等）システムにおける通信媒体（光ファイバ等の有線回線や無線回線等）を用いることができる。
【０１１２】
また、そのプログラムコードをコンピュータに供給するための手段、例えばかかるプログラムコードを格納した記録媒体は本発明を構成する。かかるプログラムコードを記憶する記録媒体としては、例えばフレキシブルディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、磁気テープ、不揮発性のメモリカード、ＲＯＭ等を用いることができる。
【０１１３】
また、コンピュータが供給されたプログラムコードを実行することにより、上述の実施の形態の機能が実現されるだけでなく、そのプログラムコードがコンピュータにおいて稼働しているＯＳ（オペレーティングシステム）或いは他のアプリケーションソフト等と共同して上述の実施の形態の機能が実現される場合にもかかるプログラムコードは本発明の実施の形態に含まれることはいうまでもない。
【０１１４】
さらに、供給されたプログラムコードがコンピュータの機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに格納された後、そのプログラムコードの指示に基づいてその機能拡張ボードや機能拡張ユニットに備わるＣＰＵ等が実際の処理の一部又は全部を行い、その処理によって上述した実施の形態の機能が実現される場合にも本発明に含まれることはいうまでもない。
【０１１５】
なお、上記実施の形態において示した各部の形状及び構造は、何れも本発明を実施するにあたっての具体化のほんの一例を示したものに過ぎず、これらによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその精神、又はその主要な特徴から逸脱することなく、様々な形で実施することができる。
【０１１６】
【発明の効果】
以上説明したように、本発明によれば、発行処理の際に認証局（発行装置）はユーザが最初に登録した情報と乱数とから新しい公開鍵を生成するので、ユーザ（利用端末）から情報を受け取る必要が無い。従って、必要なときに認証局（発行装置）単独で新しい公開鍵とそれに対応する公開鍵証明書を生成し、ユーザ（利用端末）に発行できる。ユーザ（利用端末）は新しい秘密鍵と公開鍵の生成を行う必要は無く、認証局（発行装置）に情報を送る必要も無い。
【０１１７】
つまり、認証局（発行装置）はユーザの新しい公開鍵とそれに対応する公開鍵証明書を一方的に発行することができる。従って、たとえユーザ（利用端末）が鍵の変更を忘れてしまったとしても、認証局（発行装置）が新しい公開鍵とそれに対応する公開鍵証明書を生成することができ、古い公開鍵証明書は証明書無効化リストに載せることができる。これにより、公開鍵の変更に関してユーザ（利用端末）の負担を減らすことができ、変更を確実に行うことが可能となる。
【図面の簡単な説明】
【図１】システムの構成を示す図である。
【図２】第１の実施の形態における公開鍵証明書更新プロトコルを示す図である。
【図３】公開鍵証明書発行プロトコルを示す図である。
【図４】従来の公開鍵証明書更新プロトコルを示す図である。
【符号の説明】
Ｄｃａ    発行装置
Ｔｉ      利用端末
１０１  生成部
１０２  発行部
１０３  計算部
【図１】
2005072648.tif 000021
【図２】
2005072648.tif 000022
【図３】
2005072648.tif 000023
【図４】
2005072648.tif 000024