JP2011091868A - 公開鍵を検証可能に生成する方法及び装置 - Google Patents

Abstract

【課題】公開鍵の検証可能な生成方法を提供すること。本発明は、公開鍵の検証可能な生成のための方法及び装置に関する。
【解決手段】本発明は、公開鍵の検証可能な生成方法を提供する。この方法によると、自己署名された署名がまず生成され、次に、公開鍵及び秘密鍵のペアの生成への入力として用いられる。署名の検証により、これらの鍵が当該署名を用いた鍵生成プロセスから生成されたものであることが証明される。認証機関は、検証可能な鍵生成プロセスから生成された公開鍵の有効性を認め検証する。
【選択図】図１

Description

本発明は、公開鍵の検証可能な生成のための方法及び装置に関する。

公共ネットワークを介して動作する通信システムにおいて通信するときには、多くの場合、暗号技術を用いて通信の安全を保護する。暗号技術は、暗号化とデジタル署名とのそれぞれを通じて機密性及び／又は認証を提供することができる。公開鍵暗号システムでは、ユーザの鍵は、秘密鍵と、数学的に関係のある公開鍵とを含む。公開鍵だけが与えられても、秘密鍵を決定することは不可能である。すべての機関のための公開鍵は公表が可能であるし、そうでなくとも、その通信システムのそれ以外の通信者（correspondents）に配布することが可能である。

公開鍵のために受け入れられているよい慣習には、公開鍵の検証（ＰＫＶ）と、関連する秘密鍵のための所有の証明（ＰＯＰ）とが含まれる。これらの慣習は、公開鍵の潜在的な濫用を回避するのに有用なテストであると考えられている。

公開鍵の検証には、意図された公開鍵を、そのタイプの秘密鍵との一致についてテストすることが含まれる。このテストは、関連する秘密鍵の持ち主の参加を含む場合と含まない場合とがある。公開鍵の検証は、様々な他のセキュリティ手段が配置されている場合に、意図された公開鍵が安全であることを保証するのに役立つ。

所有の証明には、一方の当事者が別の当事者に対して、与えられた公開鍵と関連する秘密鍵を知っていることを証明することが含まれる。これは、多くの場合、秘密鍵に依存するデジタル署名を提供することを通じて、行われる。署名の検証に成功すれば、秘密鍵を知っていることが証明される。

公開鍵の検証も所有の証明も、その秘密鍵が（ａ）盗まれた可能性や（ｂ）不十分なランダム性を用いて生成された可能性を排除できない。鍵が盗まれると、それは、ＩＤの窃盗、公開鍵の窃盗、そして、同様の望まれない詐欺（フロード）を構成する場合がある。不十分なランダム性は、コンピュータ、特に、スマート・カードやそれ以外の強要されたデバイスにおいて一般的な問題である。不十分なランダム性は、推測可能な又は複製された秘密鍵につながるおそれがあり、それによって、セキュリティが著しく損なわれる。

本発明の目的は、これらの問題点を克服することにある。

本発明の発明者は、「検証可能な鍵生成」を実行する方法を開発した。この方法を用いると、第１の当事者は、その第１の当事者は鍵を盗んだのではなく実際に生成したということの他者による検証を可能にする態様で、その鍵のペア（１対の鍵）を生成することができる。更に、信頼のおける機関がその検証可能な鍵生成プロセスに参加して、鍵のペアに追加的なランダム性を提供することができる。

本発明の発明者は、検証可能な鍵生成は上述した鍵の盗難や不十分なランダム性の可能性を排除することに役立つことを見出した。
本発明のある特徴においては、公開鍵の検証可能な鍵生成方法が提供される。この方法によると、自己署名された署名が最初に生成され、次に、秘密鍵と公開鍵とのペアの生成への入力として用いられる。この署名の検証により、これらの鍵が当該署名を用いた鍵生成プロセスから生成されたものであることが証明される。

公開鍵検証、所有の証明及び検証可能な鍵生成の典型的な使用は、公開鍵の認証の間である。認証においては、主体すなわちユーザ又は請求者が、発行者すなわち認証機関（ＣＡ）からの認証を請求する。主体は、おそらくは、十分なランダム性を得るに際してＣＡの助けを用い、鍵のペアを生成する。主体は、また、公開鍵を検証し、公開鍵の生成を検証するのに有用な追加的な情報を生成しうる。次に、主体は、公開鍵又は署名メッセージに署名して、認証リクエストと称されるものを形成し、これを他の情報と共にＣＡに送る。ＣＡは、主体のＩＤを確認して、認証リクエストにおける署名を検証し、公開鍵を有効であると認め、鍵のペアの生成を検証する。ＣＡは、いったん満足すると、認証を発行する。

検証可能な鍵生成のある実施例は、既存のデジタル署名技術の基づいて構築されている。自己署名された署名は、署名されたメッセージとして定義され、このメッセージ自体は署名のコピーを含む。本発明は、自己署名された署名と鍵ペアとを同時に生成する方法を含み、従って、自己署名された署名の検証により、鍵ペアが盗まれたのではなくて生成されたことが保証される。

信頼された機関がメッセージにいくらかのランダム性を含ませる場合には、十分なランダム性が保証される。鍵ペアの所有者のセキュリティを強化するためには、ソルト（salt）と長い計算とを用いて鍵ペア所有者による当該鍵ペアへのランダム性の寄与の網羅的なサーチを回避することにより、署名の検証を修正することができる。
例えば、本発明は、以下を提供する。
（項目１）
秘密鍵と公開鍵との対を生成する方法であって、
署名を生成するステップと、
データ・メッセージと上記署名とから自己署名された署名メッセージを形成するステップと、
秘密鍵と公開鍵との上記対を上記自己署名された署名メッセージから計算するステップと、
を含み、上記公開鍵は上記署名と上記自己署名された署名メッセージとから検証可能であることを特徴とする方法。
（項目２）
項目１記載の方法において、
上記データ・メッセージを認証機関から受け取るステップを更に含み、
上記データ・メッセージはランダム性を含むことを特徴とする方法。
（項目３）
項目２記載の方法において、
リクエスト・メッセージを上記認証機関に送るステップと、
上記データ・メッセージを上記認証機関から安全なチャネルを介して受け取るステップと、
を更に含み、上記データ・メッセージは、上記認証機関により上記リクエスト・メッセージから生成され、上記認証機関の秘密鍵を用いて署名されることを特徴とする方法。
（項目４）
項目１記載の方法において、上記署名と上記鍵の対とはＤＳＡ署名アルゴリズムに基づいて生成されることを特徴とする方法。
（項目５）
項目１記載の方法において、上記署名と上記鍵の対とはＥＣＤＳＡ署名アルゴリズムに基づいて生成されることを特徴とする方法。
（項目６）
項目１記載の方法において、上記署名は整数を含み、上記署名を生成するステップは、
短期公開鍵を生成するステップと、
ソルト値を提供するステップと、
上記ソルト値と上記短期公開鍵との連結の所定の数の反復に対するハッシュ値を計算するステップと、
上記ハッシュ値の整数値を上記整数に割り当てるステップと、
を含むことを特徴とする方法。
（項目７）
項目１記載の方法において、上記署名は整数を含み、上記署名を生成するステップは、
ランダムに選択された整数である短期公開鍵を選択するステップと、
上記短期公開鍵と楕円曲線点との積である署名短期公開鍵を上記短期公開鍵から計算するステップと、
上記署名短期公開鍵に対応する整数値を上記整数に割り当てるステップと、
を含むことを特徴とする方法。
（項目８）
項目１記載の方法において、上記署名は整数を含み、上記自己署名された署名メッセージを形成するステップは、上記データ・メッセージと上記署名とを上記自己署名された署名メッセージに連結するステップを含み、公開鍵と秘密鍵との上記対を計算するステップは、
上記自己署名された署名メッセージの整数ハッシュ値からメッセージ・ダイジェストを計算するステップと、
上記署名と上記メッセージ・ダイジェストとから上記秘密鍵を計算するステップと、
上記秘密鍵から上記公開鍵を計算するステップと、
を含むことを特徴とする方法。
（項目９）
自己署名された署名と、秘密鍵ｄと公開鍵Ｑとの対とを同時に生成する方法であって、
素数ｎよりも小さな非負整数である短期秘密鍵ｋを選択するステップと、
上記短期秘密鍵ｋから、上記短期秘密鍵と楕円曲線点Ｇとの積である署名短期公開鍵を計算するステップと、
上記署名短期公開鍵に対応する整数値を第１の署名整数ｒに割り当てるステップと、
上記素数ｎよりも小さな非負整数であり上記第１の署名整数と共に署名を形成するる第２の署名整数ｓを選択するステップと、
データ・メッセージと上記署名とから自己署名された署名メッセージを形成するステップと、
数式ｄ＝（ｓｋ−ｅ）／ｒ ｍｏｄｎを用いて上記秘密鍵ｄを計算するステップと、
数式Ｑ＝ｄＧを用いて上記公開鍵を計算するステップと、
を含むことを特徴とする方法。
（項目１０）
項目９記載の方法において、上記整数値を割り当てるステップは、
ソルト値を提供するステップと、
上記ソルト値と上記署名短期公開鍵との連結の所定の数の反復に対するハッシュ値を計算するステップと、
上記ハッシュ値の整数値を上記第１の署名整数ｒに割り当てるステップと、
を含むことを特徴とする方法。
（項目１１）
コンピュータ上で実行可能であり項目９に記載された方法を実装するプログラムを記憶するコンピュータ読取可能な媒体。
（項目１２）
メッセージから、秘密鍵と、上記メッセージと短期公開鍵と秘密鍵との３要素とを生成する方法であって、
整数である短期秘密鍵を選択するステップと、
上記短期秘密鍵から、上記短期秘密鍵と楕円曲線点との積である上記短期公開鍵を計算するステップと、
上記メッセージと上記短期公開鍵との整数ハッシュ値からメッセージ・ダイジェストを計算するステップと、
上記短期秘密鍵と上記メッセージ・ダイジェストとから上記秘密鍵を計算するステップと、
上記秘密鍵と上記短期公開鍵とから上記公開鍵を計算するステップと、
を含むことを特徴とする方法。
（項目１３）
コンピュータ上で実行可能であり秘密鍵と公開鍵との対と自己署名された署名とを同時に生成する方法を実装するプログラムを記憶するコンピュータ読取可能な媒体であって、上記プログラムは、上記コンピュータに、
署名を生成させ、
データ・メッセージと上記署名とから自己署名された署名メッセージを形成させ、
秘密鍵と公開鍵との上記対を上記自己署名された署名メッセージから計算させ、
上記公開鍵は上記署名と上記自己署名された署名メッセージとから検証可能であることを特徴とするコンピュータ読取可能な媒体。
（項目１４）
コンピュータ上で実行可能であり、メッセージから上記メッセージと短期公開鍵と公開鍵との３要素と秘密鍵とを生成する方法を実装するプログラムを記憶するコンピュータ読取可能な媒体であって、上記プログラムは、上記コンピュータに、
ランダムに選択された整数である短期秘密鍵を選択させ、
上記短期秘密鍵から、上記短期秘密鍵と楕円曲線点との積である上記短期公開鍵を計算させ、
上記メッセージと上記短期公開鍵との整数ハッシュ値からメッセージ・ダイジェストを計算させ、
上記短期秘密鍵と上記メッセージ・ダイジェストとから上記秘密鍵を計算させ、
上記秘密鍵と上記短期公開鍵とから上記公開鍵を計算させる、
ことを特徴とするコンピュータ読取可能な媒体。
（項目１５）
認証機関により公開鍵を認証する方法であって、
請求者から公開鍵と自己署名された署名を用いて上記請求者によって署名されたメッセージである認証リクエストとを受け取るステップと、
上記自己署名された署名に基づいて上記公開鍵を検証するステップと、
上記自己署名された署名の検証の成功により上記公開鍵の認証を発行するステップと、
を含むことを特徴とする方法。
（項目１６）
項目１５記載の方法において、
上記認証リクエストに含まれる上記自己署名された署名を検証するステップを更に含み、
上記認証の発行は、上記自己署名された署名の検証の成功を要することを特徴とする方法。
（項目１７）
項目１５記載の方法において、
上記公開鍵に所定のテストの組を行うことにより上記公開鍵の有効性を確認するステップを更に含み、
上記認証の発行は上記公開鍵の有効性確認の成功を要することを特徴とする方法。
（項目１８）
項目１５記載の方法において、
上記認証リクエストを受け取るステップの前に、メッセージ・データを上記請求者に提供し上記請求者からの上記認証リクエストを生成するステップを更に含み、
上記メッセージ・データはランダム性を含むことを特徴とする方法。
（項目１９）
項目１８記載の方法において、上記メッセージ・データは安全なチャネルを介して上記請求者に提供されることを特徴とする方法。
（項目２０）
項目１８記載の方法において、上記メッセージ・データを提供するステップは、
上記請求者からリクエスト・メッセージを受け取るステップと、
上記認証機関の公開鍵を用いて上記リクエスト・メッセージに署名するステップと、
上記署名されたリクエスト・メッセージから上記メッセージ・データを形成するステップと、
を更に含むことを特徴とする方法。
（項目２１）
項目１５記載の方法において、自己署名された署名を用いて署名されたメッセージは公開鍵であることを特徴とする方法。
（項目２２）
項目１５記載の方法において、自己署名された署名を用いて署名されたメッセージは上記自己署名された署名であることを特徴とする方法。

本発明の好適実施例の以上の及びそれ以外の特徴は、添付の図面を参照してなされる以下の詳細な説明から明らかである。

通信システムの概略的な表現である。 図１の通信システムにおいて実行される鍵生成を示すフローチャートである。 図２の中の１つのステップに関する変更を示すフローチャートである。 図１の通信システムにおいて実行される鍵生成方法の別の実施例を示すフローチャートである。 図１の通信システムにおいて実行される鍵生成方法の更に別の実施例を示すフローチャートである。 図５の方法によって生成された鍵と共に用いられる検証方法を示すフローチャートである。 図１の認証機関によって実行される方法の概略的な表現である。

図１を参照すると、通信システムが、全体として参照番号１０によって示されている。この通信システムは、１対の通信者１２、１４と、認証機関１６とを含む。それぞれの通信者１２、１４は、それぞれ、暗号演算を実行する暗号ユニット１８、２０を有する。通信者１２は、秘密鍵２２と、対応する公開鍵２４とを有する。認証機関１６は、詳細は後述するが、公開鍵２４を認証する認証（certificate）２６を発行する。認証２６は、後述するように、通信者１４に公開鍵２４と暗号的保証とを提供するために、通信者１４との間で共有される。

図１の通信者は、多くの暗号的なプロトコルを実行して、様々な暗号上の目的、特に、秘密鍵２２と公開鍵２４と認証２６との生成を、達成することができる。
まず、「自己署名された署名」及び「検証可能な鍵生成」について述べる。通信者は、ＤＳＡ及びＥＣＤＳＡなどの様々なデジタル署名アルゴリズムに基づいて、「自己署名された署名」を生成する以下の方法を実行することができる。便宜上、この方法を、ＥＣＤＳＡを用いて説明する。

図２を参照すると、通信者１２によって実行される自己署名された署名を生成する方法の全体が、参照番号５０によって示されている。ＥＣＤＳＡの手順に従い、最初に、Ｚ_ｐ上で定義された楕円曲線の上にあり位数（order）ｎの点Ｇが選択される。ここで、ｎは、大きな素数である。ステップ５２では、通信者１２は、区間[０，ｎ−１]の中にある整数ｋをランダムに選択する。次に、通信者１２は、ステップ５４で、楕円曲線の点Ｒ＝ｋＧを計算する。ここで、Ｒは署名短期公開鍵と称され、ｋは短期秘密鍵と称される。

署名データ（ｒ，ｓ）は、２つの整数ｒ及びｓを含む。楕円曲線の点Ｒに対応する整数値は、ステップ５６で、整数ｒに割り当てられる。理解できるように、ＥＣＤＳＡによって特定される方法を含み、楕円曲線の点Ｒを整数に変換するのには、多くの方法を用いることができる。ステップ５８では、通信者は、好ましくはランダムに、区間[０，ｎ−１]の中の整数ｓを選択する。

次に、ステップ６０では、プレメッセージ・データｍ_０を取得する。このプレメッセージ・データｍ_０は任意のメッセージ・データでよい。これは、署名されるメッセージとなりうる。これは、検証可能な鍵の所有者に関する情報を含みうる。また、認証機関によって証明され結果的な鍵ペアに与えられるランダム性など、外部のソースから受け取られる情報を含みうる。そして、通信者は、ステップ６２において、例えば連結するなど、プレメッセージ・データｍ_０と署名データ（ｒ，ｓ）とを組み合わせて、自己署名された署名メッセージｍを作成する。

ステップ６４において、通信者は、メッセージ・ダイジェストｅ＝Ｈａｓｈ（ｍ）を計算する。ただしここで、関数Ｈａｓｈは、整数の結果を与える暗号的なハッシュ関数である。ステップ６６では、通信者は、数式ｄ＝（ｓｋ−ｅ）／ｒ ｍｏｄｎを用いて、メッセージ・ダイジェストｅから秘密鍵を計算する。ステップ６８では、公開鍵が、数式Ｑ＝ｄＧを用いて、秘密鍵の値から計算される。注意すべきは、公開鍵は、秘密鍵ｄに関する上述の数式を用いて、Ｑ＝（１／ｒ ｍｏｄｎ）（ｓＲ−ｅＧ）として表現できるということである。

以上をまとめると、上述の方法は、以下のステップを含む。
１．例えば[０，ｎ−１]からランダムに、何らかの整数ｋを選択する。
２．楕円曲線の点であるＲ＝ｋＧを計算する。これは、署名短期公開鍵である
３．Ｒを整数ｒに変換する。

４．例えば[０，ｎ−１]からランダムに、何らかの整数ｓを選択する。
５．何らかのプレメッセージ・データｍ_０を取得する。これは、ランダム性など外部ソースからの情報を含みうる。

６．例えば連結するなど、プレメッセージ・データｍ_０と署名データ（ｒ，ｓ）とを組み合わせて、メッセージｍを作成する。
７．メッセージ・ダイジェストｅ＝Ｈａｓｈ（ｍ）を整数形式で計算する。

８．秘密鍵ｄ＝（ｓｋ−ｅ）／ｒ ｍｏｄｎを計算する。
９．公開鍵Ｑ＝ｄＧを計算する。あるいは、Ｑ＝（１／ｒ ｍｏｄｎ）（ｓＲ−ｅＧ）とも表現できる。

ＥＣＤＳＡ検証アルゴリズムをトリプレット（３つ組）、すなわちトリプル（ｍ，（ｒ，ｓ），Ｑ）に適用される場合には、検証アルゴリズムの結果、このトリプルが有効な署名となる。署名されたメッセージｍは署名（ｒ，ｓ）を含むから、この署名は、「自己署名された署名」である。

別の当事者の既存の公開鍵Ｑが与えられている場合には、新たな自己署名された署名を見つけることは、署名を偽造することと同等であり、これは、実行不可能であると考えられる。更に、前もって存在している秘密鍵ｄを用いる場合でも、敵対者がその秘密鍵を盗むであろうことを想定すると、新たな自己署名された署名を見つけることは、実行不可能である。というのは、自己署名された署名を生成すれば、その結果、新たな秘密鍵が生じ、この新たな秘密鍵が古い秘密鍵ではないことはほとんど確実であるからである。

従って、自己署名された署名は、「検証可能な鍵生成」を構成する。ＥＣＤＳＡ検証アルゴリズムによると、署名の検証により、上述の鍵生成プロセスが用いられたことが証明され、秘密鍵が単に盗まれたものであるとか別のソースからの再使用であるという可能性が排除される。

次に、検証可能なランダム性を用いた鍵生成について説明する。自己署名された署名を用いた検証可能な鍵生成では、メッセージｍ_０が鍵ペアの値に影響を与え、このメッセージの一部に寄与することにより、認証機関などの信頼される機関は、所望のセキュリティ・レベルに十分なレベルまで鍵ペアのランダム性を補うことができる。これは、鍵ペアの所有者がランダム性を生成する能力に関して制限がある場合に、特に有用である。

信頼された機関はデータｔを生成し、これを、鍵ペアの生成器がｍ_０に含む。値ｔは、所望のセキュリティ・レベルに従って、十分なランダム性を含む。
値ｔは、安全に鍵ペアの生成器まで運ばれる必要があるが、その理由は、鍵ペアのセキュリティはある程度までｔに依存するからである。ｔを安全に運ぶことは、ｔを機密性（confidentiality）及び真正性（authenticity）をもって運ぶことである。

真正性をもってｔを運ぶ１つの方法は、ｔにデジタル署名を含ませることである。鍵ペア生成器は、署名を検証して、その署名が信頼できる機関からのものであることを保証する。（ｔが敵対者からのものである場合には、セキュリティは著しく脆弱化する。）一般に、デジタル署名も同様に必要なランダム性を提供するのであるが、その理由は、デジタル署名が信頼される機関の秘密鍵に依存するからである。ＥＣＤＳＡなどの確率的な署名アルゴリズムが用いられる場合には、更なるランダム性が存在することができる。従って、ｔが完全にデジタル署名で構成されることも十分でありうる。ｔのために署名されたメッセージは、機関と鍵生成器とからのメッセージの組合せでありうる。

機密性を伴うｔの輸送は、様々な手段によって達成することができる。安全なチャネルが確立することができる場合には、暗号化を用いることができる。鍵ペアの生成器は、一次的なセッション鍵を生成し、信頼される機関まで、この機関の公開鍵を用いて、このセッション鍵を安全に送ることができる。一次的な公開鍵が検証可能に生成される鍵から独立であることが重要である。

典型的には、信頼される機関は、ＣＡであり、何らかの非暗号的方法を用いて鍵ペアの生成器の真正を確認する。
図３を参照すると、プレメッセージｍ_０を提供する方法の全体が参照番号７０によって示されている。ステップ７２では、通信者は、まず、認証機関に鍵生成に関する情報を請求する。このリクエストに応答して、認証機関は、ステップ７４で、メッセージを生成する。上述したように、このメッセージは、認証機関だけによって生成されたものでもありうるし、通信者と認証機関とからのメッセージの組合せでもありうる。組合せが用いられる場合には、ステップ７２において作られるリクエストは、認証機関のメッセージに含まれる通信者からのメッセージを含む。

次に、ステップ７６において、認証機関は、それ自身の鍵を用いてメッセージに署名し、ＣＡ署名を取得する。ＣＡ署名は、ステップ７８で、安全なチャネルを介して通信者に送られる。安全なチャネルは、上述したように、暗号化によって達成することができる。そして、通信者は、プレメッセージ・データｍ_０として、この署名を用いる。通信者は、ステップ６０において、この署名を用いて、図２の方法により、鍵ペアと自己署名された署名とを生成する。

次に、鍵ペア生成器の弱い秘密の保護について説明する。鍵ペア生成器が検証可能な鍵生成のために自己署名された署名を用い、図２の方法によって生成された秘密値ｋのランダム性が不十分である場合には、以下のようなセキュリティ上の問題が結果として生じる。このセキュリティ問題は、以下で図４を参照して詳細を説明するように、自己署名された署名において用いられたＥＣＤＳＡアルゴリズムを若干修正することにより緩和することができる。

このセキュリティ問題とは、敵対者が信頼される機関であるか鍵生成を検証することを希望するそれ以外の者である場合にそうなのであるが、敵対者がｋを推測することができ、ｒ、ｓ及びｍのコピーを有しているのならば、この敵対者は鍵ペア生成器が用いるのと同じ数式を用いて秘密鍵を回復することができるということである。

ｋの網羅的な推測を可能な限り困難にするために、図２の方法を、図４に示されるように修正する。図４の方法におけるステップは、図２におけるステップに類似している。
ステップ９２では、通信者１２は、区間[０，ｎ−１]の中にある整数ｋをランダムに選択する。次に、通信者１２は、ステップ９４で、署名短期公開鍵と称される楕円曲線の点Ｒ＝ｋＧを計算する。

ステップ９６では、通信者は、ｒ＝Ｈａｓｈ（Ａ‖Ｒ‖Ａ‖Ｒ‖・・・‖Ａ‖Ｒ）を計算する。ただし、ここで、反復の回数は、希望するだけまだ便宜によっていくらでも多くすることができる。「‖」は、ビット・ストリングの連結を意味する。反復回数が多くなればなるほど、計算に要する時間が長くなる。ｋのそれぞれの推測には、ｒの１階の計算を要する。従って、長い計算は、ｋを推測しようとしている敵対者により多くの作業を強制することになる。よって、反復の回数は、通信者とＣＡとが認容できる最大のものであるであることが好ましい。値Ａはソルト値であり、鍵ペア生成器に対して一意的である。ソルトは、ｋからｒの関数が鍵ペア生成器にとって一意的であることを保証し、それにより、敵対者が、異なる鍵ペア生成器のために再利用可能な計算された値の辞書を構築することを防止する。

ステップ９８では、通信者は、区間[０，ｎ−１]の中からランダムに整数ｓを選択する。次に、ステップ１００では、プレメッセージ・データｍ_０を取得する。このプレメッセージ・データｍ_０は、結果的な鍵ペアに与えられるランダム性を含みうる。そして、通信者は、ステップ１０２において、プレメッセージ・データｍ_０と署名データ（ｒ，ｓ）とを連結して、メッセージｍを作成する。ステップ１０４において、通信者は、メッセージ・ダイジェストｅ＝Ｈａｓｈ（ｍ）を計算する。ここで、関数Ｈａｓｈは、整数の結果を与える暗号的なハッシュ関数である。通信者は、ステップ１０６で秘密鍵ｄ＝（ｓｋ−ｅ）／ｒ ｍｏｄｎを計算し、ステップ１０８で公開鍵Ｑ＝ｄＧを計算する。注意すべきは、公開鍵は、秘密鍵ｄに関する上述の数式を用いて、Ｑ＝（１／ｒ ｍｏｄｎ）（ｓＲ−ｅＧ）として表現できるということである。

他の通信者や認証機関は、修正された自己署名された署名を検証できる。第１に、検証者は、楕円曲線の点Ｒ‘＝（１／ｓ ｍｏｄｎ）（ｅＧ＋ｒＱ）を計算するが、これは、ＥＣＤＳＡの検証プロセスの一部である。これには、メッセージｍのコピーと公開鍵Ｑとが必要である。検証者は、鍵ペア生成器がｒを計算するのに用いたソルトＡと反復回数とを必要とする。検証者は、次に、ｒ’＝Ｈａｓｈ（Ａ‖Ｒ‘‖Ａ‖Ｒ’‖・・・‖Ａ‖Ｒ‘）を計算する。ｒ’＝ｒである場合には、検証者は署名を受け入れ、そうでない場合には、検証者は署名を拒絶する。

敵対者がｋを網羅的に推測することを阻止するには、他の長い計算が必要になる可能性がある。敵対者は、秘密鍵に対する数式であるｄ＝（ｓｋ−ｅ）／ｒ ｍｏｄｎと公開鍵Ｑの知識とを用いて、秘密ｋに対するすなわち秘密鍵ｄに対する推測を確認することができる。ｋを推測するアプローチを遅くさせるためには、メッセージｍをｍ＝ｒ‖ｓ‖ｔ‖r‖ｓ‖ｔ‖・・・‖ｒ‖ｓ‖ｔという形式で選択することができる。その場合、ｅ＝Ｈａｓｈ（ｍ）の計算には長い時間を要し、ｋのそれぞれの推測に対して別個に行わなければならない。メッセージｍの形式は、用いられるデジタル署名アルゴリズムへの更なる修正を必要としない。

これら２つの方法を組み合わせることで、鍵ペア所有者の私的事項を、ｔを生成する信頼される機関や、信頼される機関とは独立にＱの生成を検証することを望みｍ、ｒ、ｓ及びＱを取得する任意の他の当事者から、保護することに役立つ。

次に、自己署名された署名を用いない代替的方法について説明する。図５に示されている別の実施例では、通信者は、あるメッセージｍとシードすなわち短期公開鍵Ｒと公開鍵Ｑとで構成されるハッシュ指数トリプル（ｍ，Ｒ，Ｑ）を生成する方法を実行する。これは、ＥＣＤＳＡ署名を用いる方法への代替的方法である。便宜のため、この方法を、楕円曲線（ＥＣ）公開鍵の用語を用いて説明する。この方法は、全体として参照番号１１０によって示されている。

通信者は、まず、ステップ１１２で、区間[０，ｎ−１]の中の整数ｋを選択する。次に、通信者は、ステップ１１４で、シード公開鍵として用いられる楕円曲線Ｒ＝ｋＧを計算する。ステップ１１６では、整数の形式でメッセージ・ダイジェストｆ＝ＳＨＡ−１（ｍ，Ｒ）が計算される。次に、ステップ１１８において秘密鍵ｄ＝ｋｆが計算され、ステップ１２０において公開鍵Ｑ＝ｆＲが計算される。

ハッシュ指数トリプル（ｍ，Ｒ，Ｑ）を受け取ると、受け手は、参照番号１３０で図６に示されている方法を用いてこのトリプルを検証することができる。検証者は、まず、ステップ１３２で、整数形式でメッセージ・ダイジェストｆ＝ＳＨＡ−１（ｍ，Ｒ）を計算する。次に、検証者は、ステップ１３４でＴ＝ｆＲを計算し、ステップ１３６でＱ＝Ｔであることを確認する。Ｑ＝Ｔであるときには、ハッシュ検証トリプルは、検証者に受け入れられる。ソフトウェアでなければ、無効として拒絶される。

ハッシュ指数トリプルは自己署名された署名と類似の性質を有しており、同様の態様で機能しうることがわかっている。
次に、検証可能な鍵生成を用いた通信について説明する。図１のシステムにおける典型的な通信セッションでは、このシステムのユーザすなわち通信者１２は、まず、認証機関１４との通信を開始して認証２６を得る。この場合に、通信者１２は、認証の「主体」（subject）と称される。図７を参照すると、認証機関は、ステップ１５２において、主体に入力を提供してランダム性を与える。認証機関によって提供された入力は、例えば、認証機関の署名である。主体は、ステップ１５４で鍵ペアを生成し、ステップ１５６で認証リクエストを形成する。認証リクエストは、主体の自己署名された署名を用いて署名される。認証リクエストは、例えば、主体の署名された公開鍵であるか、又は、単純に、主体の自己署名された署名である。主体は、認証リクエストと公開鍵とを、認証のために認証機関へ送る。主体は、主体の名前などの他の情報を、認証リクエスト及び公開鍵と共に送ることもありうる。認証リクエストと公開鍵とを（更に、それ以外の情報も）受け取ると、認証機関は、典型的には、ステップ１５８において、主体のＩＤを確認する。ＣＡは、次に、ステップ１６０で、認証リクエストの中の署名を検証することがある。ＣＡは、ステップ１６２において公開鍵の有効性を確認するが、これには、公開鍵が「有効」であることを保証するいくつかのテストが含まれる。ＣＡは、次に、ステップ１６４において、鍵ペアの生成を検証する。この検証の詳細は既に上述したとおりである。公開鍵が実行されるテストに合格すると、ＣＡは、ステップ１６６において、認証を発行する。認証には、情報に関するＣＡのデジタル署名が含まれ、これには、主体のＩＤと公開鍵とが含まれる。

認証を発行するＣＡが公開鍵の有効性確認と鍵生成の認証とを行う場合には、認証は、当該認証とその公開鍵との他のユーザに、当該公開鍵は有効であり、盗まれたものではなく、十分なランダム性を有していることを保証するのに役立つ。認証の他のユーザが認証を発行するＣＡを完全には信頼しない場合には、そのユーザは、公開鍵の有効性確認と鍵生成検証とを直接に実行することを可能にする情報を見ることを求めることができる。

以上では、本発明の様々な特定の実施例について詳細に説明した。この技術分野の当業者であれば、本発明の範囲から逸脱せずに、多くの修正、適用及び改変をこれらの実施例に対して行うことが可能であることを理解するはずである。上述した最良の形態の変更やそれへの追加は本発明の本質、精神又は範囲から逸脱することなく行うことができるので、本発明は、以上で述べた詳細に限定されることなく、冒頭の特許請求の範囲によってのみ範囲が画定される。

Claims (8)

1. 認証機関により公開鍵を認証する方法であって、
   前記方法は、
   請求者から認証リクエストと公開鍵とを受け取るステップであって、前記認証リクエストは、自己署名された署名を用いて前記請求者によって署名されたメッセージである、ステップと、
   前記自己署名された署名に基づいて前記公開鍵を検証するステップと、
   前記自己署名された署名の検証の成功により前記公開鍵の認証を発行するステップと
   を含む、方法。
2. 前記認証リクエストに含まれる前記自己署名された署名を検証するステップをさらに含み、
   前記認証の発行は、前記自己署名された署名の検証の成功を要する、請求項１に記載の方法。
3. 前記公開鍵に所定のテストの組を行うことにより前記公開鍵の有効性を確認するステップをさらに含み、
   前記認証の発行は、前記公開鍵の有効性確認の成功を要する、請求項１に記載の方法。
4. 前記認証リクエストを受け取るステップの前に、メッセージ・データを前記請求者に提供し前記請求者からの前記認証リクエストを生成するステップをさらに含み、
   前記メッセージ・データは、ランダム性を含む、請求項１に記載の方法。
5. 前記メッセージ・データは、安全なチャネルを介して前記請求者に提供される、請求項４に記載の方法。
6. 前記メッセージ・データを提供するステップは、
   前記請求者からリクエスト・メッセージを受け取るステップと、
   前記認証機関の公開鍵を用いて前記リクエスト・メッセージに署名するステップと、
   前記署名されたリクエスト・メッセージから前記メッセージ・データを形成するステップと
   をさらに含む、請求項４に記載の方法。
7. 自己署名された署名を用いて署名されたメッセージは、公開鍵である、請求項１に記載の方法。
8. 自己署名された署名を用いて署名されたメッセージは、前記自己署名された署名である、請求項１に記載の方法。

Images