(57)【特許請求の範囲】
【請求項１】
一対の通信者の間で実装される公開鍵データ通信システムにおいて、前記一対の通信者のうちの一方の通信者によって一対の鍵として用いられる秘密鍵と対応する公開鍵とを生成する方法であって、前記公開鍵データ通信システムは、生成手段と試験手段とプロセッサとを含み、
前記方法は、
前記生成手段が、数を生成するステップと、
前記試験手段が、前記数を所定の組の試験に適用するステップと、
前記試験手段が、前記数が所定の組の基準を満たしていることを示す一組の結果を前記試験が提供することを確認するステップであって、前記数が所定の組の基準を満たしていることは、前記数が秘密鍵として適合していることを示す、ステップと、
前記一組の結果が前記所定の組の基準を満たしていない場合には、前記試験手段が、前記数を拒絶するステップと、
前記一組の結果が前記所定の組の基準を満たしている場合には、前記試験手段が、前記数が秘密鍵として用いられることを受け入れるステップと、
前記試験手段が、前記秘密鍵の後続する確認のために、前記一方の通信者において前記秘密鍵と前記所定の組の基準とを保持するステップと、
前記プロセッサが、前記秘密鍵から、対応する公開鍵を生成するステップと
を含み、
これにより、前記データ通信システムにおいて前記一対の鍵が利用される場合には、前記一対の鍵に対して前記プロセッサを用い、それによって得られた結果と前記所定の組の基準とを比較することによって、前記一対の鍵の否認が抑制される、方法。
【請求項２】
前記所定の組の試験は、前記数の統計的ランダムさを決定するための統計的試験を含む、請求項１に記載の方法。
【請求項３】
前記一組の結果は、前記統計的試験の信頼レベルに関連付けられている、請求項２に記載の方法。
【請求項４】
前記所定の組の基準は、前記一方の通信者によって保持されている選択可能な組である、請求項１に記載の方法。
【請求項５】
前記数は、シードに対して定義された数学的演算を行うことによって生成され、前記方法は、前記シードと前記数と前記所定の組の基準とを安全に保持するステップを含む、請求項１に記載の方法。
【請求項６】
公開鍵データ通信システムにおいて、デジタル署名を生成するために用いられる秘密鍵を確認する方法であって、前記公開鍵データ通信システムは、生成手段と試験手段とプロセッサとを含み、
前記方法は、
前記生成手段が、秘密鍵として用いられる数を生成するステップと、
前記試験手段が、前記数を所定の組の試験に適用するステップと、
前記試験手段が、前記数が所定の組の基準を満たしていることを示す一組の結果を前記試験が提供することを確認するステップであって、前記数が所定の組の基準を満たしていることは、前記数が秘密鍵として適合していることを示す、ステップと、
前記一組の結果が前記所定の組の基準を満たしている場合には、前記試験手段が、前記数を秘密鍵として受け入れるステップと、
前記プロセッサが、前記秘密鍵から、対応する公開鍵を生成するステップと、
前記試験手段が、前記秘密鍵と前記所定の組の基準とを安全に保持するステップと、
前記プロセッサが、前記秘密鍵を用いてメッセージに署名することにより、デジタル署名を生成するステップと、
前記プロセッサが、前記秘密鍵と前記所定の組の基準とを取り出すことによって、前記秘密鍵の妥当性を検証するステップと、
前記プロセッサが、前記取り出された秘密鍵を試験することにより、さらなる組の結果を得るステップと、
前記プロセッサが、前記さらなる組の結果と前記所定の組の基準とを比較するステップと、
前記さらなる組の結果が前記所定の組の基準を満たしている場合には、前記プロセッサが、前記秘密鍵を確認するステップであって、これにより、前記署名の否認が抑制される、ステップと
を含む、方法。
【請求項７】
前記所定の組の試験は、統計的試験を含む、請求項６に記載の方法。
【請求項８】
前記所定の組の基準は、前記一方の通信者によって選択可能である、請求項７に記載の方法。
【請求項９】
前記取り出された秘密鍵は、対応する公開鍵を生成するために用いられ、前記取り出された秘密鍵から生成された前記公開鍵は、前記受け入れられた秘密鍵から生成された秘密鍵に対応する公開鍵と比較される、請求項７に記載の方法。
【請求項１０】
前記数は、シードに対してハッシュ関数を行うことによって取得され、前記方法は、前記シードを保持することと、前記シードに対して前記ハッシュ関数を行うことと、その結果と前記取り出された秘密鍵とを比較することとを含む、請求項９に記載の方法。
【請求項１１】
公開鍵データ通信システムにおいて、一対の通信者のうちの一方の通信者によって用いられる暗号化ユニットであって、前記暗号化ユニットは、生成手段と試験手段とプロセッサとを含み、前記暗号化ユニットは、請求項１〜１０のうちのいずれか一項に記載の方法を行うように構成されている、暗号化ユニット。
【発明の詳細な説明】
本発明は、安全なデジタルデータ伝達システムに関し、そして特に、適切なランダム特性（それ自身により考慮される）を有するあるランダム暗号化秘密鍵値を保証する方法、およびそのようなシステムにおいて暗号化秘密鍵を確認する方法に関する。
【０００１】
（発明の背景）
安全なデータ伝達システムは、通信者のペア間で情報を転送するために使用される。交換される情報の少なくとも一部は、送信者による所定の数学的操作によって暗号に書き直される（ｅｎｃｏｄｅ）（書き換えられる（ｅｎｃｉｐｈｅｒ））。次いで、受信者は、結びの数学的操作を行って、その情報を解読する（ｕｎｅｎｃｏｄｅ）（解読する（ｄｅｃｉｐｈｅｒ））ことができる。情報の暗号化および解読は、通常、通信者間で実行された特定の暗号化スキームによって決定される暗号化鍵を利用して行われる。従って、前もって通信者間で知られている確実なパラメータが存在する。例えば、公開鍵または対称鍵システムにおいて、種々のスキームおよびプロトコルは、送信者の公開鍵、送信者の身元等を確認するために考案されている。
【０００２】
これらの全てのスキームにおいて、秘密鍵、公開鍵または対称鍵である暗号化鍵が、派生し、そしてプロトコルスキームにおいて特定されるので妥当であると考えられる。しかしながら、問題は、これらのパラメータがある点で偽造または欠陥のいずれかである場合が生じる。
【０００３】
デジタル署名法は、第三者に証明するために、メッセージが実際の創作者によって署名されることを起源としている。実用的な公開鍵署名スキームは、許可されていない集合（ｐａｒｔｙ）による変更または偽造を困難するためのある数学的問題を解くことの困難さに基づいている。提案されるスキームのほとんどは、大きな整数を素因数分解する問題または有限の値（ｆｉｎｉｔｅ  ｆｉｅｌｄ）（または、一般に有限の集団（ｆｉｎｉｔｅ  ｇｒｏｕｐ））の離散対数を計算する困難さのいずれかに基づいている。例えば、ＲＳＡシステムは、大きな整数を素因数分解することの困難さに依存している。
【０００４】
メッセージのデジタル署名は、署名者のみに知られるある秘密、そしてさらに署名されたメッセージの内容に依存する数である。署名は、証明可能でなければならない。もし、集合が署名されたかどうかについて議論が生じる（作成された署名を拒絶しようとする署名者または偽の要求者かのいずれかによって生じる）のであれば、公平な第三者が、署名者の秘密情報にアクセスする必要なしに公正に問題を解決することができる（すなわち、秘密鍵）。
【０００５】
ＥｌＧａｍａｌ署名スキームは、ランダム化された署名メカニズムである。ＥｌＧａｍａｌ署名スキームについての鍵を生成するために、各実体（ｅｎｔｉｔｙ）は公開鍵および対応する秘密鍵を作成する。従って、各実体は大きなランダムな素数（ｒａｎｄｏｍ  ｐｒｉｍｅ）ｐと倍数グループ（ｍｕｌｔｉｐｌｉｃａｔｉｖｅ  ｇｒｏｕｐ）Ｚ* P の発生器αを生成する。次に、上記実体は、１≦α≦ｐ−２のようなランダムな整数αを選択し、そして値ｙ＝αa ｍｏｄｐを計算する。従って、例えば、実体Ａの公開鍵は、システムパラメータｐおよびαとともに（ｙ）であり、一方Ａの秘密鍵は、αである。
【０００６】
システム上の安全は、一般に、離散対数問題の困難さに基づく。ＲＳＡ暗号は、ｎ＝ｐｑ（ここでｐおよびｑは異なった奇妙な（ｏｄｄ）素数である）の形の係数を用いる。素数ｐおよびｑは、素因数分解の積が計算範囲を越えるのに十分な大きさでなければならない。さらに、それらは、徹底的なアタックが不可能である十分に主要な候補の予備（ｐｏｏｌ）を定義する処理を介するランダム入力の関数として選択される意味で、ランダムな素数であるべきである。実際には、結果の素数も、システムの仕様に対応する所定のビット長でなければならない。これらが、素数ｐおよびｑを強制的に選択しない場合には、ＲＳＡシステムはいわゆる「ファーストパーソンアタック（ｆｉｒｓｔ  ｐｅｒｓｏｎ  ａｔｔａｃｋ）」に弱い。
【０００７】
楕円曲線暗号においては、楕円曲線公開鍵は、１とｎ−１との間で選択される統計的に独特でかつ予測できない値（ここで、ｎはＧ（関連するＥＣドメインパラメータにより特定される大きなサブグループの生成点）の素数の桁（ｐｒｉｍｅ  ｏｒｄｅｒ）である）である。
【０００８】
可能な「ファーストパーソンアタック」において、アタッカーとしての実体Ａは、弱点である秘密鍵を作成し、サービス等を得るために秘密鍵を使用する。後に、不正な実体は、弱い秘密鍵を否認または拒絶し、それからこれらのサービスを要求しなかったと主張する。すなわち、集合Ａは、不注意に使用された弱い秘密鍵が容易にアタックされる公開鍵の結果であり、そして第三者をオリジナルの実体Ａになりすますことができる秘密鍵に派生させることを主張する。例えば、鍵は２64を生成することによって１６１ビットの秘密ＥＣ鍵を作るためのシードされた（ｓｅｅｄｅｄ）ハッシュを用いて生成され、集合Ａは高オーダーの６４ビットの０で一つの（期待される）鍵を選択することができる。第１の集合は、否認要求で判断に向けられ、そして反対するものが実効時間において残りの９７ビットをアタックすることができることを指摘する。従って、彼は彼の鍵が否認され、そのときすでに９７ビットの鍵が壊されてしまっていることを示している。明らかに、高い安全アプリケーションにおいて、ファーストパーソンアタックを避けることが望ましい。
【０００９】
第１集合の否認に関するこの可能性をアドレスするためのある方法は、全ての第１集合否認要求を単に否定することである。しかしながら、これは、もし鍵が実質的に弱く生成された場合には、問題が生じるかもしれない。必要とされることは、彼の特定の秘密鍵が弱くないことを保証させる所有者の能力である。あるアプリケーションにおいては、弱い鍵のペアの生成が統計的にありそうもないことを十分に主張することができないかもしれない。所有者は、たとえどんな値であっても、彼の特定の鍵が弱くなる特性を有していないことを保証させたいが、彼は後に否認することができない。
【００１０】
鍵の暗号強度は、鍵として使用された二進法の表示におけるビットのランダム分布（ｄｉｓｔｒｉｂｕｔｉｏｎ）の大きな範囲に依存する。従って、鍵は、擬似乱数発生器によって生成されてもよいが、数字（ｄｉｓｉｔ）が、認識できるパターンにおいて分布されるか、またはより短い鍵を作るためにグループ化される場合に弱くなり得る。
【００１１】
従って、秘密鍵否認の確率が最小であるＥＣＣ  ＥｌＧａｍａｌ型スキームを実行することが望ましい。
【００１２】
（発明の要旨）
一般的に、本発明は、通信者のペア間で実行する公開鍵データ伝達システムにおいて使用するための秘密鍵の生成方法を提供し、該方法は、秘密鍵として使用するための乱数を生成する工程、該数の統計的ランダムさを決定するための所定の基準のセットに対して該数を試験する工程、および該基準を満足する該乱数を利用する工程を含む。
【００１３】
（好ましい実施形態の説明）
本発明の好ましい実施形態のこれらおよび他の特徴は、添付の図面を参照して以下の詳細な説明でさらに明らかになる。
【００１４】
図１を参照して、デジタルデータ伝達システム１０は、伝達チャンネル１６により接続される送信者１２および受信者１４として表される通信者のペアを含む。通信者１２および１４の各々は、それぞれ、以下に説明されるように、デジタル情報を処理することができ、そしてそれにチャンネル１６を介する伝達の準備をさせることができる暗号化ユニット１８、２０を含む。
【００１５】
以下の説明において、本発明の実施形態は、楕円曲線ＥｌＧａｍａｌ型スキームを参照して例示され、他の暗号化システムまたはＤｉｆｆｉｅ  Ｈｅｌｌｍａｎ鍵変換が等しく利用されることができることが理解されるべきである。
【００１６】
楕円曲線秘密鍵は、１とｎ−１との間で選択される統計的に独特でかつ予測されない値（ここで、ｎはＧ（関連する楕円曲線（ＥＣ）ドメインパラメータにより特定される大きなサブグループの生成点）の素数の桁である）である。である。高い安全アプリケーションにおいては、保証することができることが望まれ、次いで、厳密な鍵の生成基準が対応するように実行する。このことを容易にするために、鍵試験プロセッサ２８は鍵生成に含まれ、そして該鍵を確認するためにＥＣ秘密鍵確認プロセッサ３０が暗号化ユニット１８、２０に組み込まれる。
【００１７】
図２に示すように、秘密鍵ｋは、図２に示すような標準的な秘密鍵生成関数３２で生成される。関数３２から可能な秘密鍵として提供された乱数は、ｎ（生成点Ｇの素数の桁）とほぼ同じ大きさである大きさになるように選択される。この数は、適正なノイズハードウェアランダマイザー（ｎｏｉｓｅ  ｈａｒｄｗｅａｒ  ｒａｎｄｏｍｉｚｅｒ）かまたは図３に示すようなシード（ｓｅｅｄ）の擬似ランダム関数を介してのいずれかによって、生成させることができる。
【００１８】
（適正な）乱数発生器（ＲＮＧ）３６または擬似乱数発生器（ＰＲＮＧ）３８はＳＥＥＤ（シード）３４を作る。ＰＲＮＧ３８を利用するためには、ランダムシードを、ＰＲＮＧに入力し、出力でＳＥＥＤ３４を生成しているのに対して、ＲＮＧは、ＳＥＥＤ３４を直接生成する。ＳＥＥＤ３４は、４０である方法関数でハッシュ（ｈａｓｈ）され、ハッシュからの出力が形成されて、秘密鍵のための適切な大きさになる。結果の値は、ｋとして表される秘密鍵として使用され得るビット列（ｂｉｔ  ｓｔｒｉｎｇ）である。
【００１９】
使用されるハッシュ関数は、ＳＨＡ−１である。カウンター値（ｃｏｕｎｔｅｒ  ｖａｌｕｅ）Ｘ’０１’、Ｘ’０２’等は、異なる１６０ビット値を生成するためにＳＥＥＤにつなげられ、これは、結果の値がｎより大きくなるまで正確につなげられる。使用される形成関数（ｓｈａｐｅ  ｆｕｎｃｔｉｏｎ）はモジューロ（ｍｏｄｕｌｏ）ｎである。
【００２０】
鍵試験プロセッサ２８は、鍵生成関数３２により生成された値を受け取り、所定の、鍵ｋがユーザーに容認可能と見なされる基準のセットに対応することを確認する選択可能な試験のセットに適用する。典型的には、該プロセッサは、標準の統計的試験に適用して、鍵におけるビット分布がランダムであり予測できないことを保証することができる。見掛けのランダムさをチェックするために使用することができる試験には、
１．頻度試験（ｆｒｅｑｑｕｅｎｃｙ  ｔｅｓｔ）（モノビット試験（ｍｏｎｏｂｉｔ  ｔｅｓｔ））
２．ポーカー試験（Ｐｏｋｅｒ  ｔｅｓｔ）
３．実行試験（Ｒｕｎｓ  ｔｅｓｔ）
４．ロングラン試験（Ｌｏｎｇ  ｒｕｎ  ｔｅｓｔ）
がある。
【００２１】
発生器関数３２からの出力は、以下の各々の試験に供され、たとえ試験が失敗しても、そのときには、候補の秘密鍵ｋが否認される。例として、モノビット試験は２０，０００ビットのストリームの中の１の数を計算する必要がある。Ｘによりこの量を表す。この試験は、６５＜Ｘ＜１３５の場合に、１，０００，０００の中の１のエラー確率、すなわち非常に高い信頼レベルを通過する。
【００２２】
同様に、ポーカー試験は、６６の連続した３ビットのセグメントの中の２００ビットのストリームに由来する。８の可能な３ビットの値の各々の発生の数を計算および保存が、計算され、保存される。各３ビット値ｉの数としてｆ（ｉ）で表す（ここで、ｉは０＜＝ｉ＜＝８）。
【００２３】
以下で評価する：
Ｘ＝（８／６６）* ＳＵＭ  ｆｒｏｍ  ｉ＝０  ｔｏ  ８〔（ｆ（ｉ））**２〕−６６
試験は、ｘの値Ａが必要とされる信頼レベルによって決定される所定の範囲内にある場合に通過した見なされる。
【００２４】
ランズ試験は、２００ビットのサンプルストリームの部分である、全てが１かまたは全てが０であるいずれかの連続したビットの最大の配列として定義される実行を利用する。サンプルストリームにおける全ての長さ（＞＝１）の実行（連続する１と連続する０の両方についての）の範囲は、計算され、保存される。この長さの分布は、必要とされる信頼レベルによって決定された容認可能な基準と比較される各範囲における実行長さの頻度によって監視される。
【００２５】
さらに、ロングラン試験は、１６の長さ以上（０または１のいずれか）の実行のために定義されるロングラン試験（Ｌｏｎｇ  Ｒｕｎ  Ｔｅｓｔ）を含むことができる。２００ビットのサンプルにおいて、この試験はＮＯロングランである場合に通過する。
【００２６】
上記のようにロングラン試験を含むことによって、多くの特定の秘密鍵がランダムであり、従ってアタックすることが困難であることを保証することができる。
【００２７】
秘密鍵に使用するための、特定の要求されるランダム配列のためのユーザーにより望まれる信頼レベルに関連する各統計的試験のための適切な値を選択することにより、選択された鍵のみが、ユーザーによる基準セットに容認することができるものである。その後、否認は、不可能であるが、ただし、基準は対応する。信頼レベルが０である場合、そのときには、統計的試験は実行されない。信頼レベルが８０％または９０％である場合、そのときには、値の適切な容認可能な範囲が、容認可能な範囲に実際の値がある場合を見るために、各試験（単数または複数）の実行を決定する。統計的アプローチが１００％の場合の注意として、さらなる候補秘密鍵値が放棄され、従って、鍵ペアの生成がこれ以上起こることを予測される。
【００２８】
もちろん、さらなる試験を、適切と見なされる場合に代用しても、または含んでもよい。
【００２９】
図２を参照して、鍵ｋが容認された後、暗号化ユニット１８をＥＣドメインパラメータ２４のセットに関連づける。ドメインパラメータは、鍵ｋに由来するＥＣ公開鍵ｋＧを含む。このパラメータはまた、ＥＣドメインパラメータおよびＥＣ公開鍵の上記セットと関連づけられることが要求される平文（開かれた）ＥＣ秘密鍵データ構造を含む。平文ＥＣ秘密鍵データ構造は、（少なくとも）以下の情報を含む：
１．この秘密鍵と関連づけられるＥＣドメインパラメータの表示。
２．秘密鍵ｋの値を生成するＳＥＥＤ。
３．秘密鍵ｋの値。
４．秘密鍵ｋの値がランダムに見える信頼レベルの表示。これは、統計的試験中に適用され、パーセンテージで表す０と９９との間の値である。
【００３０】
この処理での出力は、通過するか失敗のいずれかである。通過は、全ての確認試験を通過したＥＣ秘密鍵を示す。失敗は、確認試験を必ずしも通過しないＥＣ秘密鍵を示す。次いで、秘密鍵および公開鍵を、メッセージに署名するために使用することができ、または通信者１２、１４間の確立されたプロトコルを使用する鍵を信頼できることを証明することができる。
【００３１】
ＥＣ秘密鍵データ構造は、ドメインにおける安全を維持することができ、そして実施依存手段（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ−ｄｅｐｅｎｄｅｎｔ  ｍｅａｎｓ）によって公開されるので、秘密鍵の公開は、回復され、そしてその完全な状態が鍵を公開する処理の一部として実証される。
【００３２】
署名が、否認された場合には、鍵の妥当性は秘密鍵データ構造２４を使用して実証することができる。パラメータは、基準の所定のセットに対して秘密鍵の妥当性を試験するプロセッサ３０に転送される。
【００３３】
プロセッサ３０で行われる処理は、以下に記載される：
１．（要求される）ＥＣドメインパラメータを、全てのそれぞれの構成要素が値において理想であることを保証するために関連づけられたＥＣドメインパラメータの秘密鍵データ構造における表示と比較する。
２．ｎ（生成点Ｇの素数の桁）より長いことを保証するためにＳＥＥＤの長さを確認する。
３．秘密鍵ｋが結果であることを保証するために標準的なシードされたハッシュ関数に入力する場合に通過することによってＳＥＥＤを確認する。
４．ｋＧを、値において理想的であることを保証するために（要求された）関連づけられた公開鍵の値と比較することによって秘密鍵ｋを確認する。
５．試験関数２８による統計的試験の実行において特定された信頼レベルに対応することを保証するために秘密鍵ｋの値を確認する。
６．全て試験が製鋼した場合、そのとき「通過」を出力し；そうでなければ、「失敗」を出力する。通過は、秘密鍵が通信者１２によって特定された全ての基準に対応することを表示し、従って、否認することができない。
【００３４】
非常に高い安全要件でのアプリケーションはまた、ペルメッセージ秘密ｋ値（ｐｅｒ−ｍｅｓｓａｇｅ  ｓｅｃｒｅｔ  ｋ  ｖａｌｕｅ）がＫＳＥＥＤ値から認められた擬似乱数発生器の使用によって生成されることを確認することを望むかもしれない。この選択が望まれる場合、特定のＫＳＥＥＤ値は特定の秘密鍵と関係づけられ、そしてＫＳＥＥＤ値は他のいかなる目的に使用されるべきではない。ＫＳＥＥＤ値は、擬似乱数発生器が使用されることに関する表示と一緒に秘密鍵の他の構成要素とともに安全性に確保するべきである。ｋについての可能な値の範囲は、ドメインパラメータの特定のセットに関連する秘密鍵についての可能な値の範囲と同様である。唯一の異なることは、倍数の（ｍｕｌｔｉｐｌｅ）ｋ値がＫＳＥＥＤから生成されることであるが、一方ある秘密鍵は、ＳＥＥＤから生成される。この情報からわかるように、確認ルーチンはｋ値の呼び出し特定数（ｃａｌｌｅｒ−ｓｐｅｃｉｆｉｅｄ  ｎｕｍｂｅｒ）および関連づけられるｒ値（通常、デジタル署名の一部である）を出力する。次いで、呼び出しは、一致することを保証するために、出力ｒ値を前の署名からのｒ値の保存リストと比較する。
【００３５】
本発明は、その特定の実施形態、特定の使用に関して記載してきたが、その種々の改変が添付の請求の範囲に記載される本発明の精神から逸脱することなく当業者に見いだされるであろう。
【００３６】
本明細書で使用されている用語および語句は、記載の用語として使用され、限定として使用されることはなく、そのような用語および語句の使用において、示されそして記載された特徴またはその部分のいかなる等価物を除外する意図はないが、本発明の請求の範囲内で可能である種々の改変が認識される。
【図面の簡単な説明】
【図１】  デジタル伝達システムの概略のダイヤグラムである。
【図２】  図１の解読単位の概略のダイヤグラムである。
【図３】  標準的な公開鍵生成スキームの流れダイヤグラムを示す。
【図１】
0004731686.tif 000002
【図２】
0004731686.tif 000003
【図３】
0004731686.tif 000004