楕円曲線乱数生成
【課題】ネットワーク内でセキュリティドメインのためのエスクロー鍵を確立する方法を提供する。
【解決手段】楕円曲線乱数生成器は、楕円曲線上の２点であってＰ＝ｅＱとなるような２点Ｐ、Ｑを入力とする。まず、点Ｐの値を含むビット列のハッシュ値が計算され、ハッシュ値は体の元に変換され、体の元は、楕円曲線上の点Ｑのｘ座標として見なされ、ｘ座標は、所望の楕円曲線上で有効性がテストされる。有効であれば、ｘ座標は点Ｑに伸張され、ｙ座標の符号の選択もまたハッシュ値から導出される。ｅはエスクロー鍵と呼ばれセキュリティドメインの管理者のみが知る。ＰとＱが与えられれば、点Ｑが点Ｐと特定の関係にあることが検証できる。エスクロー鍵の意図的な使用により、バックアップ機能が提供される。エスクロー鍵はセキュリティドメインに格納される。管理者は、生成器の出力を記録して、エスクロー鍵で乱数を再構築する。
【解決手段】楕円曲線乱数生成器は、楕円曲線上の２点であってＰ＝ｅＱとなるような２点Ｐ、Ｑを入力とする。まず、点Ｐの値を含むビット列のハッシュ値が計算され、ハッシュ値は体の元に変換され、体の元は、楕円曲線上の点Ｑのｘ座標として見なされ、ｘ座標は、所望の楕円曲線上で有効性がテストされる。有効であれば、ｘ座標は点Ｑに伸張され、ｙ座標の符号の選択もまたハッシュ値から導出される。ｅはエスクロー鍵と呼ばれセキュリティドメインの管理者のみが知る。ＰとＱが与えられれば、点Ｑが点Ｐと特定の関係にあることが検証できる。エスクロー鍵の意図的な使用により、バックアップ機能が提供される。エスクロー鍵はセキュリティドメインに格納される。管理者は、生成器の出力を記録して、エスクロー鍵で乱数を再構築する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は暗号乱数生成のシステムと方法に関する。
【背景技術】
【０００２】
乱数は、基盤となる安全性を提供するために、多数の暗号演算において利用される。公
開鍵基盤において、例えば、鍵対の私的鍵は、乱数生成器により生成され、対応する公開
鍵は数学的に私的鍵から導出される。各セッションに対して新しい鍵対が生成され、その
ため、生成器のランダム性が暗号システムの安全性にきわめて重要となる。
【０００３】
乱数の安全なソースを提供するために、暗号的に安全な擬似乱数ビット生成器が開発さ
れており、その中で、各生成器の安全性は、基盤となる数論問題の推測できる対処の困難
さに依存する。ＡＮＳＩ（American National Standards Institute：米国規格協会）は
、ＡＳＣ（AccreditedStandards Committee）Ｘ９を、金融サービス産業のために設立し
、それは、暗号乱数生成（ＲＮＧ）のためのＡＮＳ（American National Standard）Ｘ９
．８２を準備している。Ｄｕａｌ＿ＥＣ＿ＤＲＢＧと称されるＸ９．８２の草案における
ＲＮＧ方法の１つは、安全性のために楕円曲線暗号（ＥＣＣ）を使用している。Ｄｕａｌ
＿ＥＣ＿ＤＲＢＧは、以降、楕円曲線乱数生成（ＥＣＲＮＧ）と呼ぶ。
【０００４】
楕円曲線暗号は、楕円曲線群の巡回部分群における離散対数問題の難しさに依存する。
楕円曲線Ｅは、楕円曲線の定義方程式を満たす点（ｘ，ｙ）の集合である。定義方程式は
、三次方程式であり、非特異性である。座標ｘとｙは、体の元であり、加法、減法、およ
びゼロを除く除法が可能な元の集合である。体の例としては、有理数および実数がある。
また有限体もあり、暗号においてはもっともよく使用される。有限体の例としては、素数
ｑを法とする整数の集合がある。
【０００５】
一般性を失うことなく、楕円曲線の定義方程式は、ワイエルシュトラス（Weierstrass
）形式で可能であり、それは、座標の体に依存している。体Ｆが素数ｑ＞３を法とする整
数の場合、ワイエルシュトラス（Weierstrass）方程式は、ｙ２＝ｘ３＋ａｘ＋ｂの形式
となり、ここでａとｂは体Ｆの元である。
【０００６】
楕円曲線Ｅは点（ｘ，ｙ）と、更に１つの点、つまり、無限大における点Ｏを含む。
楕円曲線Ｅはまた、群構造を有し、それは、曲線上の2点ＰとＱは加法が可能で、第３の
点Ｐ＋Ｑを形成することを意味する。点Ｏは、群の単位元であり、すべての点Ｐに対して
Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐである。加法は、すべての点Ｐ、ＱおよびＲに対して結合律が成り立
ち、Ｐ＋（Ｑ＋Ｒ）＝（Ｐ＋Ｑ）＋Ｒであり、かつ、可換であり、Ｐ＋Ｑ＝Ｑ＋Ｒである
。各点ＰはＰ＋（−Ｐ）＝Ｏとなる負の点−Ｐを有している。曲線方程式がｙ２＝ｘ３＋
ａｘ＋ｂの形式のワイエルシュトラス（Weierstrass）方程式のときは、Ｐ＝（ｘ，ｙ）
の負は容易に−Ｐ＝（ｘ，−ｙ）として決定できる。座標について点ＰとＱを加える公式
は、数回の体の演算を含むだけの、適度の複雑さである。
【０００７】
ＥＣＲＮＧは入力として、固定の２つの楕円曲線点ＰとＱを使用する。これらの点は、
秘密とは仮定されていない。典型的には、Ｐは楕円曲線ドメインパラメータの標準生成器
であり、Ｑは、ある他の点である。更に、秘密シードがＥＣＲＮＧに挿入される。
【０００８】
ＥＣＲＮＧは、整数ｓと考えられる、ある状態を有している。状態ｓは、ＥＣＲＮＧが
出力を生成するたびに更新される。更新された状態はｕ＝ｚ（ｓＰ）として計算され、こ
こでｚ（）は、楕円曲線点を整数に変換する関数である。一般的に、ｚは点のｘ座標を取
ることで構成され、結果としての体の元を整数に変換する。このように、ｕは、典型的に
は、点ｓのｘ座標から導出される整数である。
【０００９】
ＥＣＲＮＧの出力は、ｒ＝ｔ（ｚ（ｓＱ））として計算され、ここにおいてｔは打切り
関数である。一般的に打切り関数は、入力の最左端のビットを除去する。ＥＣＲＮＧにお
いては、打ち切られるビット数は、楕円曲線の選択に依存し、典型的には、６から１９ビ
ットの範囲である。
【００１０】
ＰとＱが分かっていても、出力ｒはランダムで、予測できないと信じられている。従っ
て、連続する値は、私的鍵を得て、暗号関数を破るために利用できる関係を有しない。本
発明の出願者は、Ｑ＝ｄＰとなるような整数ｄを知っていれば誰でもｅｄ＝１ ｍｏｄ
ｎであって、ここでｎはＧの位数であるような整数ｅを推測でき、それにより、Ｐ＝ｅＱ
となるような整数ｅを入手できるということを認識した。更新された状態およびＥＣＲＮ
Ｇ出力の前駆体を、Ｕ＝ｓＰおよびＲ＝ｓＱと想定する。整数ｅにより、ＵをＲからＵ＝
ｅＲとして計算できる。従って、出力ｒ＝ｔ（ｚ（Ｒ））であり、Ｒの可能な値は、ｒか
ら決定できる。打切り関数は、Ｒの打ち切られたビットは、推測されなければならないこ
とを意味している。ｚ関数は、ｘ座標のみが利用でき、そのため、全点Ｒを得るためには
、伸張を適用しなければならないことを意味している。ＥＣＲＮＧの場合は、約２６＝６
４と２１９（つまり、約５００，０００）の間のどこかに、ｒに対応する可能な点Ｒがあ
ることになり、正確な数は曲線とｒの特別な値に依存する。
【００１１】
Ｒ値の全体集合は、ｒから決定するのは容易で、上述したように、Ｒに対する正確な
値の決定は、ｅを知っていれば、Ｕ＝ｅＲを決定する。更新された状態は、ｕ＝ｚ（Ｕ）
であり、Ｒの正しい値から決定できる。従って、ｒとｅを知っていれば、２６と２１９の
間のどこかで、多数の可能性から次の状態を決定できる。この不確定さは、別の出力が観
測されると、一方向性関数を介して直接または間接的に、確実に排除される。
【００１２】
次の状態がいったん決定されると、ＥＣＲＮＧのすべての将来の状態は、ＥＣＲＮＧが
決定関数なので決定できる（少なくとも追加的なランダムエントロピーがＥＣＲＮＧ状態
に供給されない限り）。ＥＣＲＮＧのすべての出力は、ＥＣＲＮＧの決定状態から決定さ
れる。従って、ｒとｅを知っていると、ＥＣＲＮＧのすべての将来の出力を決定できる。
【００１３】
従って、本発明の出願人によって、本方法は、潜在的に侵入口を有していることが特定
され、そのため、アルゴリズムの標準化に携わる者、あるいは導入者は、単一の出力と、
ＲＮＧの実例を使用して、すべての将来の状態とＲＮＧの出力を決定でき、それにより、
その安全性を完全に損なってしまう。従って、本発明の目的は、上述した不都合な点を除
去または緩和することである。
【発明の概要】
【課題を解決するための手段】
【００１４】
１つの形態において、本発明は、検証可能にランダムな点Ｑを、楕円曲線乱数生成器内
の別の点Ｐとの使用のために計算する方法であって、点Ｐを入力として含むハッシュを計
算するステップと、ハッシュから点Ｑを導出するステップを備える方法を提供する。
【００１５】
別の形態においては、本発明は、楕円曲線乱数を生成する方法であって、楕円曲線乱数
生成器を使用して出力を生成するステップと、出力を打ち切って、乱数を生成するステッ
プを備える方法を提供する。
【００１６】
更に別の形態においては、本発明は、楕円曲線乱数を生成する方法であって、楕円曲線
乱数生成器を使用して出力を生成するステップと、出力を一方向性関数に適用して乱数を
生成するステップを備える方法を提供する。
【００１７】
更に別の形態においては、本発明は、楕円曲線乱数生成器に対するバックアップ機能の
方法であって、楕円曲線の点Ｑが決定されるとエスクロー鍵ｅを計算し、それによりＰ＝
ｅＱであって、Ｐは楕円曲線の別の点であるステップと、管理者を置くステップと、管理
者にエスクロー鍵ｅを格納させるステップと、楕円曲線乱数生成器を有するメンバーに、
生成器の出力値の前に生成された出力ｒを管理者に送らせるステップと、管理者が、出力
ｒを、生成器の状態の将来の決定のために記録するステップを備える方法を提供する。
例えば、本願発明は以下の項目を提供する。
（項目１）
暗号演算において使用される乱数を計算する方法であって、１対の入力を楕円曲線乱数生成器に提供するステップを備え、各入力が楕円曲線点の少なくとも１つの座標を示し、前記入力のうち少なくとも１つは検証可能にランダムである計算する方法。
（項目２）
前記少なくとも１つの入力は、ハッシュ関数の出力から得られる項目１に記載の計算する方法。
（項目３）
前記入力の他方は、前記ハッシュ関数の入力として利用される項目２に記載の計算する方法。
（項目４）
前記乱数生成器は秘密値を有し、前記秘密値は、前記入力により示される前記点のスカラー倍を計算するために使用される項目１に記載の計算する方法。
（項目５）
前記スカラー倍の１つは、前記乱数を導出するために使用され、前記スカラー倍の他方は、次の使用のために前記秘密値を変更するために使用される項目４に記載の計算する方法。
（項目６）
前記ハッシュ関数の前記出力は、前記入力として利用される前に、楕円曲線上の点の座標として有効化される項目２に記載の計算する方法。
（項目７）
前記点の別の座標が、前記入力として含むために前記１つの座標から得られる項目６に記載の計算する方法。
（項目８）
前記他の入力は、楕円曲線点を示す項目７に記載の計算する方法。
（項目９）
前記乱数は、前記スカラー倍により示される前記点の１つの座標を選択し、前記座標を前記乱数としての使用のためにビット列に打ち切ることにより、前記スカラー倍から導出される項目５に記載の計算する方法。
（項目１０）
前記１つの座標は、楕円曲線点表現を示す長さの約半分の大きさに打ち切られる項目９に記載の計算する方法。
（項目１１）
前記乱数は、前記スカラー倍により示される前記点の１つの座標を選択し、前記１つの座標をハッシングし、前記乱数として使用するためにビット列を提供することにより、前記スカラー倍から導出される項目５に記載の計算する方法。
（項目１２）
前記検証可能にランダムな入力は標準形として選択され、それにより、前記入力間の所定の関係を維持することは困難になる項目１に記載の計算する方法。
（項目１３）
暗号演算において使用される乱数を計算する方法であって、それぞれが、１対の楕円曲線点の少なくとも１つの座標を示す１対の入力を楕円曲線乱数生成器に提供するステップと、楕円曲線点のスカラー倍の少なくとも１つの座標を示す出力を得るステップと、前記出力を一方向性関数に通して、乱数としての使用のためのビット列を得るステップと、を備える計算する方法。
（項目１４）
前記一方向性関数は、ハッシュ関数である項目１３に記載の計算する方法。
（項目１５）
楕円曲線乱数生成器であって、それぞれが、１対の楕円曲線点の少なくとも１つの座標を示す１対の入力と、暗号演算において乱数として使用される出力を有し、前記入力の少なくとも１つは、検証可能にランダムである楕円曲線乱数生成器。
（項目１６）
前記１つの入力は、一方向性関数の出力から導出される項目１５に記載の楕円曲線乱数生成器。
（項目１７）
前記一方向性関数はハッシュ関数である項目１６に記載の楕円曲線乱数生成器。
（項目１８）
前記入力の他方は、前記ハッシュ関数への入力として提供される項目１７に記載の楕円曲線乱数生成器。
（項目１９）
ネットワーク内でセキュリティドメインのためのエスクロー鍵を確立する方法であって、楕円曲線乱数生成器へのそれぞれの入力としての１対の点ＰＱを、前記点の間の関係がＰ＝ｅＱとなるように確立するステップと、前記関係ｅを、管理者と共にエスクロー鍵として格納するステップと、前記楕円曲線乱数生成器から、前記ドメイン内の暗号演算で使用される乱数を生成するステップを備える方法。
【図面の簡単な説明】
【００１８】
本発明の実施形態は、ここで、添付された図面を参照することのみにより、例として説
明される。
【００１９】
【図１】暗号乱数生成方式の模式図である。
【図２】楕円曲線点を選択するための選択工程を示すフローチャートである。
【図３】更なる実施形態を示す、図１に類似のブロック図である。
【図４】図３の装置により実行される工程を示すフローチャートである。
【図５】更なる実施形態を示すブロック図である。
【図６】図２の工程の更に別の実施形態を示すフローチャートである。
【図７】管理された暗号乱数生成方式の模式図である。
【図８】エスクロー鍵選択工程を示すフローチャートである。
【図９】エスクロー鍵を安全に利用する方法を示すフローチャートである。
【発明を実施するための形態】
【００２０】
図１を参照すると、暗号乱数生成器（ＥＣＲＮＧ）１０は、楕円曲線計算を行う演算ユ
ニット１２を含んでいる。ＥＣＲＮＧはまた、状態値ｓを保持するセキュアレジスタ１４
を含み、初期設定点ＰとＱの対を受信するための入力１６と１８の対を有している。点Ｐ
とＱは、既知と仮定されている楕円曲線点である。出力２０は、暗号モジュール２２への
乱整数の通信のために供給される。レジスタ１４の初期内容は、シード入力Ｓにより供給
される。
【００２１】
点Ｐを表現する入力１６は、第１実施形態においては、そのような使用に適切であると
して公表された既知の値から選択される。
【００２２】
入力１８は、一方向性関数の出力から、典型的には、入力として点Ｐを受信するＳＨＡ
１またはＳＨＡ２のような暗号的に安全なハッシュ関数である、ハッシュ関数の形態で得
られる。関数２４は、任意のビット列Ａ上で作動し、ハッシュされた出力２６を生成する
。出力２６は、更なる処理のために演算ユニット１２に適用されて入力Ｑを供給する。
【００２３】
作動中、ＥＣＲＮＧは、シードとしてビット列を受信し、それはレジスタ１４に格納さ
れる。シードは、秘密に維持され、ランダム性およびハミング重さのような、特定のアプ
リケーションに適合するように選択された、前もって確立された暗号基準に合うように選
択される。
【００２４】
ｄが知られる可能性がないことを確実にするために（例えば、Ｐ＝ｄＱおよびｅｄ＝１
ｍｏｄ ｎのように）、入力１６と１８の１つまたは両者は、検証可能にランダムであ
るように選択される。図１の実施形態においては、Ｑは、その入力が点Ｐを含むハッシュ
関数（好ましくは一方向性）の出力から導出することにより、検証可能にランダムである
ような方法で選択される。図２に示されるように、任意の列Ａがステップ２０２で選択さ
れ、ＡのハッシュＨは、Ｐと随意にＳを、ハッシュベース関数ＦＨ（）への入力としてス
テップ２０４で計算され、ハッシュＨは、演算ユニット１２により、ステップ２０６にお
いて所望の体Ｆの体の元Ｘに変換される。Ｐは、前計算されていても、固定でも、または
検証可能にランダムな選択値として選択されてもよい。体の元Ｘは、Ｑのｘ座標として見
なされる（このように、Ｑの「圧縮された」表現）。ｘ座標は、ステップ２０８で、所望
の楕円曲線Ｅ上で有効性がテストされ、Ｘが有効かどうかがステップ２１０において決定
される。有効の場合は、元Ｘにより提供されたｘ座標は伸張され、ステップ２１２におい
て点Ｑを提供する。ｙ座標の２つの可能な値のどちらを選択するかは、一般的には、ハッ
シュ値から導出される。
【００２５】
点ＰとＱは、個々の点１６と１８において適用され、演算ユニット１２は、点ｓＱを
計算し、ここでｓは、レジスタ１４に格納されている現在の値である。演算ユニット１２
は、点（この例では、点ｓＱ）のｘ座標を整数に変換し、その値を打ち切って、ｒ＝ｔ（
ｚ（ｓＱ））を得る。打ち切られた値ｒは出力２０に供給される。
【００２６】
演算ユニット１２は同様に値を計算して、ｓがレジスタ１４の値であるときのｓＰを
計算することでレジスタ１４を更新して、点ｓＰのｘ座標を整数ｕに変換する。整数ｕは
、レジスタに格納され、次の反復に対してｓと置換される。（上記を繰り返す）
【００２７】
上述したように、点Ｐもまた検証可能にランダムであってよいが、確立されたまたは
固定された値であってもよい。従って、図１の実施形態は、ある基点（例えば、Ｐ）が既
にハードウェアに実装されている場合は、システムに適用または後付け追加できる。典型
的に、基点Ｐは、米国連邦情報処理標準規格（ＦＩＰＳ：Federal Information Processi
ng Standard）１８６−２で推奨されているような、ある既存の基点になる。そのような
場合は、Ｐは、検証可能にランダムになるようには選択されない。
【００２８】
一般的に、点Ｐを、ハッシュ関数の入力に含むことは、ハッシュ関数の一方向性特性
のため、およびＱが既に決定されたＰから導出されるので、Ｐが、Ｑが決定される前に決
定されたことを確実にする。ＰはＱの前に決定されたので、ＰがＱの倍数（例えば、Ｐ＝
ｅＱの場合）として選択されることは有り得ず、従って、ｄを見出すことは一般的には、
離散対数問題のランダムなケースを解くのと同じ程度難しいということは明確に理解でき
る。
【００２９】
このように、提供されたシード値Ｓと、提供されたハッシュに基づく関数Ｆ（）を有
しているので、検証者は、Ｑ＝Ｆ（Ｓ，Ｐ）を決定でき、ここにおいてＰは、検証可能に
ランダムではなくてもよい。同様に、Ｐ＝Ｆ（Ｓ，Ｑ）を計算して同じ効果を得ることが
できるが、これは、Ｘ９．８２の初期の草案におけるＰの値が、ＦＩＰＳ１８６−２で指
定された基点と同一であるならば必要ではないと考えられている。
【００３０】
上記に概要を記述したように、ビット列からＱを生成することは、ＥＣＲＮＧ１０の
外部で行うことができ、または好ましくは、演算ユニット１２を使用して内部的に行うこ
とができる。ＰとＱの両方が検証可能にランダムであることが必要な場合は、図１に点線
で示される第２ハッシュ関数２４が、ビット列Ａから点Ｐの座標を生成するために組み込
まれる。入力の少なくとも１つに対してハッシュ関数を提供することにより、検証可能に
ランダムな入力が得られる。
【００３１】
生成される出力は、点ｓＰのｘ座標から導出されるということも分かるであろう。従
って、入力１６と１８は、点ＰとＱのｘ座標であってよく、対応するｓＰとｓＱの値は、
モントゴメリ（Montgomery）乗法技術を使用して得られ、それにより、ｙ座標を取り出す
必要性を除去する。
【００３２】
Ｑを選択する方法の代替方法は、Ｑを、そのビット表現が、例えば、名前の表現のよ
うに、ある既知のｄとＰに対してＱ＝ｄＰを生成することで生成するのが困難なある列を
含むように、ある標準形で選択することである。この方法と、好適な方法の間の中間的な
形式もまた存在し、その場合は、Ｑは部分的に標準形であり、部分的に検証可能にランダ
ムに導出されるということは理解されよう。Ｑのそのような選択は、検証可能にランダム
であっても、標準形であっても、またはある中間形式であっても、検証可能と呼ばれる。
【００３３】
図３と図４に示す、ＥＣＲＮＧの出力に対する鍵エスクロー攻撃を防止する別の代替
方法は、打切り関数２８をＥＣＲＮＧ１０に追加して、ＥＣＲＮＧ出力を、圧縮楕円曲線
点の長さの約半分に打ち切ることである。好ましくは、この演算は、図１および図２の好
適な方法に追加して行われるが、それは、鍵エスクロー攻撃を防止する主要な手段として
行うことができるということは理解されよう。打切りの利点は、単一のＥＣＲＮＧ出力ｒ
に関連するＲ値のリストは、典型的には、探すのが現実的には不可能であるということで
ある。例えば、１６０ビット楕円曲線群に対して、リストに可能な点Ｒの数は、約２８０
であり、リストを探索することは、離散対数問題を解くことと同じ程度に困難である。こ
の方法のコストは、出力長が事実上半分にされるので、ＥＣＲＮＧの効率が半分になると
いうことである。
【００３４】
図５と図６に示す、更に別の代替方法は、新しい入力を生成するハッシュ関数のよう
な、３４として特定される、別の一方向性関数ＦＨ２を介する、ＥＣＲＮＧの出力のフィ
ルタ処理を備える。ここで再び、好ましくは、この演算は、図２に示される好適な方法に
追加して行われるが、鍵エスクロー攻撃を防止する主要な手段として行うこともできる。
追加のハッシュは、演算ユニット１２で行われる楕円曲線演算と比べて、相対的にコスト
が小さく、ＥＣＲＮＧの安全性を問題になるほど削減しない。
【００３５】
上述したように、エスクロー鍵の存在を有効的に防止するためには、検証可能にラン
ダムなＱに、検証可能にランダムなＰまたは、前もって確立されたＰを付随させるべきで
ある。前もって確立されたＰは、広く公開され、ＥＣＲＮＧ１２の概念の前に選択された
と容認されている点Ｐであってよく、従ってそれは、Ｑは、Ｐが確立されたときに生成さ
れていなかったので、Ｐが、Ｐ＝ｅＱとして選択されることは不可能であったことを意味
する。
【００３６】
上記の技術が、侵入口を「閉じる」ことにより、ＥＣＲＮＧを使用するシステムの安
全性を確実にする一方、ＰとＱの可能性のある相互依存性、つまり、ｅの存在を注意深く
使用することにより、Ｐ＝ｅＱであることの利点を利用することもまた可能である。
【００３７】
そのようなシナリオにおいては、値ｅは、エスクロー鍵と見なしてよい。ＰとＱが管
理者により制御されたセキュリティドメインにおいて確立されると、ドメインでＱを生成
するエンティティは、ｅを知って（またはｄを知ることで間接的に知って）それを行う。
管理者は、その標準に従うすべてのＥＣＲＮＧに対してエスクロー鍵を有することになる
。
【００３８】
エスクロー鍵は、ある状況では利点があることが知られている。エスクロー鍵は、バッ
クアップ機能を提供する。暗号鍵が紛失した場合、その鍵で暗号化されたデータもまた失
われる。しかし、暗号鍵は一般的には、乱数生成器の出力である。従って、ＥＣＲＮＧが
、暗号鍵Ｋの生成に使用されると、エスクロー鍵ｅを使用して、暗号鍵Ｋを取り出すこと
が可能になる。エスクロー鍵は、盗聴に使用されるような、他の機能も提供する。この場
合、信頼できる法施行機関が、犯罪者の暗号化トラフィックを復号することが必要になり
、これを行うため、暗号鍵を取り出すために、エスクロー鍵を使用できることを所望する
ことがある。
【００３９】
図７は、それぞれが、ドメイン４０の個々のメンバーと関連している、多数のＥＣＲ
ＮＧ１０を有するドメイン４０を示している。ドメイン４０は、他のドメイン４０ａ、４
０ｂ、および４０ｃと、インターネットのようなネットワーク４２を介して通信する。ド
メインの各ＥＣＲＮＧは、同一の入力ＰとＱの対を有している。ドメイン４０は、安全な
方法でエスクロー鍵ｅを維持する管理者４４を含む。
【００４０】
管理者４４は、Ｑ＝ｅＰとなるようなエスクロー鍵ｅを知り得るようにＰとＱの値を
選択する。ドメイン４０の他のメンバーは、ＰとＱの値を使用し、それにより、管理者４
４に、組織のすべてのメンバーに対して機能するエスクロー鍵ｅを与える。
【００４１】
これは、暗号鍵の紛失に対する対処策としてのバックアップ機能において最も有益で
ある。エスクロー鍵ｅは、メンバー特有にすることもでき、それにより、各メンバーは、
管理者４４から選択された点からの自分自身のエスクローｅ’を有する。
【００４２】
図８において、全体を数字４００で示したように、管理者は、最初は、所望の楕円曲
線に対する標準生成器Ｐとして一般的に選択される点Ｐを選択する（４０２）。そして、
管理者は、値ｄを選択して、点Ｑは、適切なサイズの、ある乱整数ｄに対して、Ｑ＝ｄＰ
として決定される（４０４）。エスクロー鍵ｅは、ｅ＝ｄ−１ ｍｏｄ ｎとして計算さ
れ（４０６）、ここでｎは、生成器Ｐの位数であり、管理者により格納される。
【００４３】
そのようなエスクロー鍵３４ｅの安全な使用法は、数字５００により全体的に示され
、図９に示されている。管理者４４が、まず設置され（５０２）、そしてエスクロー鍵ｅ
が選択され、管理者４４により格納される（５０４）。
【００４４】
エスクロー鍵が完全な有効性で機能するためには、エスクロー管理者４４は、取り出
されるＥＣＲＮＧ出力値ｋ（例えば１６）の前に生成されたＥＣＲＮＧ出力値ｒへの直接
アクセスを必要とする。一方向性関数または暗号アルゴリズムを介するｒへの間接アクセ
スを有するだけでは十分ではない。これを達成するための形式化された方法は、図７にお
いて４６で示され、図９においてステップ５０６において示されるように、ＥＣＲＮＧ１
２を有する各メンバーに、管理者４４と通信させることである。これは暗号化ファイル格
納システムまたは暗号化電子メールアカウントに対して最も有益であろう。よりシームレ
スな方法を暗号アプリケーションに適用できる。例えば、ウェブ（ＨＴＴＰ）トラフィッ
クを安全にするＳＳＬおよびＴＬＳプロトコルにおいて、クライアントおよびサーバーは
、ハンドシェークを行い、それらの最初の行動は、平文で送信された乱数値を交換するこ
とである。
【００４５】
他の多数のプロトコルは、しばしばナンスと呼ばれる、そのような乱数値を交換する。
エスクロー管理者がこれらのナンスを観測し、それらの記録を維持すれば（５０８）、後
日、必要なｒ値を決定することが可能になる。これにより、管理者が、クライアントまた
はサーバー（ドメインのメンバーであれば誰でも）のＥＣＲＮＧ１２の次の状態を決定す
ることができ（５１０）、それにより、次のＥＣＲＮＧ１２値を取り出すことができる。
特に、ＳＳＬまたはＴＬＳセッションに対する暗号鍵が導出されるランダムなプレマスタ
ー秘密を一般的に生成するクライアントに対して、エスクロー鍵は、セッション鍵の取り
出しを可能にする。セッション鍵の取り出しは、全ＳＳＬまたはＴＬＳセッションの取り
出しを可能にする。
【００４６】
セッションが記録されていれば、それは取り出すことができる。これは長期私的鍵を
危険に晒すものではなく、ＥＣＲＮＧの出力から得られたセッション鍵のみで、エスクロ
ーに関連する一般的な疑いに関するいかなる問題も緩和される。
【００４７】
エスクロー鍵は他の状況において、不都合な点も有することが知られているが、特定
のセキュリティドメイン内の制御により、これらの問題のいくつかは緩和される。例えば
、非拒絶に対するデジタル署名では、署名者以外は、署名鍵を有しないということが重要
で、そうでなければ、署名者は、合法的に署名の拒絶を主張できる。エスクロー鍵の存在
は、他のあるエンティティが署名鍵へのアクセスを有し、それにより署名者は、エスクロ
ー鍵が使用されて署名鍵を得て、その署名を生成したと主張することを可能にする。しか
し、ドメインが特別な組織、または組織の一部に制限されている場合は、組織が署名を拒
絶できないということで十分である。暗号鍵とは異なり、紛失した署名鍵は、データの紛
失を意味しないので、署名鍵のバックアップはほとんど必要ない。
【００４８】
本発明は、ある特別な実施形態を参照して説明されてきたが、この技術に精通した者
には、本明細書に付随する請求項で概要が記載される本発明の精神および範囲から逸脱す
ることのない本発明の種々の修正が明白であろう。
【技術分野】
【０００１】
本発明は暗号乱数生成のシステムと方法に関する。
【背景技術】
【０００２】
乱数は、基盤となる安全性を提供するために、多数の暗号演算において利用される。公
開鍵基盤において、例えば、鍵対の私的鍵は、乱数生成器により生成され、対応する公開
鍵は数学的に私的鍵から導出される。各セッションに対して新しい鍵対が生成され、その
ため、生成器のランダム性が暗号システムの安全性にきわめて重要となる。
【０００３】
乱数の安全なソースを提供するために、暗号的に安全な擬似乱数ビット生成器が開発さ
れており、その中で、各生成器の安全性は、基盤となる数論問題の推測できる対処の困難
さに依存する。ＡＮＳＩ（American National Standards Institute：米国規格協会）は
、ＡＳＣ（AccreditedStandards Committee）Ｘ９を、金融サービス産業のために設立し
、それは、暗号乱数生成（ＲＮＧ）のためのＡＮＳ（American National Standard）Ｘ９
．８２を準備している。Ｄｕａｌ＿ＥＣ＿ＤＲＢＧと称されるＸ９．８２の草案における
ＲＮＧ方法の１つは、安全性のために楕円曲線暗号（ＥＣＣ）を使用している。Ｄｕａｌ
＿ＥＣ＿ＤＲＢＧは、以降、楕円曲線乱数生成（ＥＣＲＮＧ）と呼ぶ。
【０００４】
楕円曲線暗号は、楕円曲線群の巡回部分群における離散対数問題の難しさに依存する。
楕円曲線Ｅは、楕円曲線の定義方程式を満たす点（ｘ，ｙ）の集合である。定義方程式は
、三次方程式であり、非特異性である。座標ｘとｙは、体の元であり、加法、減法、およ
びゼロを除く除法が可能な元の集合である。体の例としては、有理数および実数がある。
また有限体もあり、暗号においてはもっともよく使用される。有限体の例としては、素数
ｑを法とする整数の集合がある。
【０００５】
一般性を失うことなく、楕円曲線の定義方程式は、ワイエルシュトラス（Weierstrass
）形式で可能であり、それは、座標の体に依存している。体Ｆが素数ｑ＞３を法とする整
数の場合、ワイエルシュトラス（Weierstrass）方程式は、ｙ２＝ｘ３＋ａｘ＋ｂの形式
となり、ここでａとｂは体Ｆの元である。
【０００６】
楕円曲線Ｅは点（ｘ，ｙ）と、更に１つの点、つまり、無限大における点Ｏを含む。
楕円曲線Ｅはまた、群構造を有し、それは、曲線上の2点ＰとＱは加法が可能で、第３の
点Ｐ＋Ｑを形成することを意味する。点Ｏは、群の単位元であり、すべての点Ｐに対して
Ｐ＋Ｏ＝Ｏ＋Ｐ＝Ｐである。加法は、すべての点Ｐ、ＱおよびＲに対して結合律が成り立
ち、Ｐ＋（Ｑ＋Ｒ）＝（Ｐ＋Ｑ）＋Ｒであり、かつ、可換であり、Ｐ＋Ｑ＝Ｑ＋Ｒである
。各点ＰはＰ＋（−Ｐ）＝Ｏとなる負の点−Ｐを有している。曲線方程式がｙ２＝ｘ３＋
ａｘ＋ｂの形式のワイエルシュトラス（Weierstrass）方程式のときは、Ｐ＝（ｘ，ｙ）
の負は容易に−Ｐ＝（ｘ，−ｙ）として決定できる。座標について点ＰとＱを加える公式
は、数回の体の演算を含むだけの、適度の複雑さである。
【０００７】
ＥＣＲＮＧは入力として、固定の２つの楕円曲線点ＰとＱを使用する。これらの点は、
秘密とは仮定されていない。典型的には、Ｐは楕円曲線ドメインパラメータの標準生成器
であり、Ｑは、ある他の点である。更に、秘密シードがＥＣＲＮＧに挿入される。
【０００８】
ＥＣＲＮＧは、整数ｓと考えられる、ある状態を有している。状態ｓは、ＥＣＲＮＧが
出力を生成するたびに更新される。更新された状態はｕ＝ｚ（ｓＰ）として計算され、こ
こでｚ（）は、楕円曲線点を整数に変換する関数である。一般的に、ｚは点のｘ座標を取
ることで構成され、結果としての体の元を整数に変換する。このように、ｕは、典型的に
は、点ｓのｘ座標から導出される整数である。
【０００９】
ＥＣＲＮＧの出力は、ｒ＝ｔ（ｚ（ｓＱ））として計算され、ここにおいてｔは打切り
関数である。一般的に打切り関数は、入力の最左端のビットを除去する。ＥＣＲＮＧにお
いては、打ち切られるビット数は、楕円曲線の選択に依存し、典型的には、６から１９ビ
ットの範囲である。
【００１０】
ＰとＱが分かっていても、出力ｒはランダムで、予測できないと信じられている。従っ
て、連続する値は、私的鍵を得て、暗号関数を破るために利用できる関係を有しない。本
発明の出願者は、Ｑ＝ｄＰとなるような整数ｄを知っていれば誰でもｅｄ＝１ ｍｏｄ
ｎであって、ここでｎはＧの位数であるような整数ｅを推測でき、それにより、Ｐ＝ｅＱ
となるような整数ｅを入手できるということを認識した。更新された状態およびＥＣＲＮ
Ｇ出力の前駆体を、Ｕ＝ｓＰおよびＲ＝ｓＱと想定する。整数ｅにより、ＵをＲからＵ＝
ｅＲとして計算できる。従って、出力ｒ＝ｔ（ｚ（Ｒ））であり、Ｒの可能な値は、ｒか
ら決定できる。打切り関数は、Ｒの打ち切られたビットは、推測されなければならないこ
とを意味している。ｚ関数は、ｘ座標のみが利用でき、そのため、全点Ｒを得るためには
、伸張を適用しなければならないことを意味している。ＥＣＲＮＧの場合は、約２６＝６
４と２１９（つまり、約５００，０００）の間のどこかに、ｒに対応する可能な点Ｒがあ
ることになり、正確な数は曲線とｒの特別な値に依存する。
【００１１】
Ｒ値の全体集合は、ｒから決定するのは容易で、上述したように、Ｒに対する正確な
値の決定は、ｅを知っていれば、Ｕ＝ｅＲを決定する。更新された状態は、ｕ＝ｚ（Ｕ）
であり、Ｒの正しい値から決定できる。従って、ｒとｅを知っていれば、２６と２１９の
間のどこかで、多数の可能性から次の状態を決定できる。この不確定さは、別の出力が観
測されると、一方向性関数を介して直接または間接的に、確実に排除される。
【００１２】
次の状態がいったん決定されると、ＥＣＲＮＧのすべての将来の状態は、ＥＣＲＮＧが
決定関数なので決定できる（少なくとも追加的なランダムエントロピーがＥＣＲＮＧ状態
に供給されない限り）。ＥＣＲＮＧのすべての出力は、ＥＣＲＮＧの決定状態から決定さ
れる。従って、ｒとｅを知っていると、ＥＣＲＮＧのすべての将来の出力を決定できる。
【００１３】
従って、本発明の出願人によって、本方法は、潜在的に侵入口を有していることが特定
され、そのため、アルゴリズムの標準化に携わる者、あるいは導入者は、単一の出力と、
ＲＮＧの実例を使用して、すべての将来の状態とＲＮＧの出力を決定でき、それにより、
その安全性を完全に損なってしまう。従って、本発明の目的は、上述した不都合な点を除
去または緩和することである。
【発明の概要】
【課題を解決するための手段】
【００１４】
１つの形態において、本発明は、検証可能にランダムな点Ｑを、楕円曲線乱数生成器内
の別の点Ｐとの使用のために計算する方法であって、点Ｐを入力として含むハッシュを計
算するステップと、ハッシュから点Ｑを導出するステップを備える方法を提供する。
【００１５】
別の形態においては、本発明は、楕円曲線乱数を生成する方法であって、楕円曲線乱数
生成器を使用して出力を生成するステップと、出力を打ち切って、乱数を生成するステッ
プを備える方法を提供する。
【００１６】
更に別の形態においては、本発明は、楕円曲線乱数を生成する方法であって、楕円曲線
乱数生成器を使用して出力を生成するステップと、出力を一方向性関数に適用して乱数を
生成するステップを備える方法を提供する。
【００１７】
更に別の形態においては、本発明は、楕円曲線乱数生成器に対するバックアップ機能の
方法であって、楕円曲線の点Ｑが決定されるとエスクロー鍵ｅを計算し、それによりＰ＝
ｅＱであって、Ｐは楕円曲線の別の点であるステップと、管理者を置くステップと、管理
者にエスクロー鍵ｅを格納させるステップと、楕円曲線乱数生成器を有するメンバーに、
生成器の出力値の前に生成された出力ｒを管理者に送らせるステップと、管理者が、出力
ｒを、生成器の状態の将来の決定のために記録するステップを備える方法を提供する。
例えば、本願発明は以下の項目を提供する。
（項目１）
暗号演算において使用される乱数を計算する方法であって、１対の入力を楕円曲線乱数生成器に提供するステップを備え、各入力が楕円曲線点の少なくとも１つの座標を示し、前記入力のうち少なくとも１つは検証可能にランダムである計算する方法。
（項目２）
前記少なくとも１つの入力は、ハッシュ関数の出力から得られる項目１に記載の計算する方法。
（項目３）
前記入力の他方は、前記ハッシュ関数の入力として利用される項目２に記載の計算する方法。
（項目４）
前記乱数生成器は秘密値を有し、前記秘密値は、前記入力により示される前記点のスカラー倍を計算するために使用される項目１に記載の計算する方法。
（項目５）
前記スカラー倍の１つは、前記乱数を導出するために使用され、前記スカラー倍の他方は、次の使用のために前記秘密値を変更するために使用される項目４に記載の計算する方法。
（項目６）
前記ハッシュ関数の前記出力は、前記入力として利用される前に、楕円曲線上の点の座標として有効化される項目２に記載の計算する方法。
（項目７）
前記点の別の座標が、前記入力として含むために前記１つの座標から得られる項目６に記載の計算する方法。
（項目８）
前記他の入力は、楕円曲線点を示す項目７に記載の計算する方法。
（項目９）
前記乱数は、前記スカラー倍により示される前記点の１つの座標を選択し、前記座標を前記乱数としての使用のためにビット列に打ち切ることにより、前記スカラー倍から導出される項目５に記載の計算する方法。
（項目１０）
前記１つの座標は、楕円曲線点表現を示す長さの約半分の大きさに打ち切られる項目９に記載の計算する方法。
（項目１１）
前記乱数は、前記スカラー倍により示される前記点の１つの座標を選択し、前記１つの座標をハッシングし、前記乱数として使用するためにビット列を提供することにより、前記スカラー倍から導出される項目５に記載の計算する方法。
（項目１２）
前記検証可能にランダムな入力は標準形として選択され、それにより、前記入力間の所定の関係を維持することは困難になる項目１に記載の計算する方法。
（項目１３）
暗号演算において使用される乱数を計算する方法であって、それぞれが、１対の楕円曲線点の少なくとも１つの座標を示す１対の入力を楕円曲線乱数生成器に提供するステップと、楕円曲線点のスカラー倍の少なくとも１つの座標を示す出力を得るステップと、前記出力を一方向性関数に通して、乱数としての使用のためのビット列を得るステップと、を備える計算する方法。
（項目１４）
前記一方向性関数は、ハッシュ関数である項目１３に記載の計算する方法。
（項目１５）
楕円曲線乱数生成器であって、それぞれが、１対の楕円曲線点の少なくとも１つの座標を示す１対の入力と、暗号演算において乱数として使用される出力を有し、前記入力の少なくとも１つは、検証可能にランダムである楕円曲線乱数生成器。
（項目１６）
前記１つの入力は、一方向性関数の出力から導出される項目１５に記載の楕円曲線乱数生成器。
（項目１７）
前記一方向性関数はハッシュ関数である項目１６に記載の楕円曲線乱数生成器。
（項目１８）
前記入力の他方は、前記ハッシュ関数への入力として提供される項目１７に記載の楕円曲線乱数生成器。
（項目１９）
ネットワーク内でセキュリティドメインのためのエスクロー鍵を確立する方法であって、楕円曲線乱数生成器へのそれぞれの入力としての１対の点ＰＱを、前記点の間の関係がＰ＝ｅＱとなるように確立するステップと、前記関係ｅを、管理者と共にエスクロー鍵として格納するステップと、前記楕円曲線乱数生成器から、前記ドメイン内の暗号演算で使用される乱数を生成するステップを備える方法。
【図面の簡単な説明】
【００１８】
本発明の実施形態は、ここで、添付された図面を参照することのみにより、例として説
明される。
【００１９】
【図１】暗号乱数生成方式の模式図である。
【図２】楕円曲線点を選択するための選択工程を示すフローチャートである。
【図３】更なる実施形態を示す、図１に類似のブロック図である。
【図４】図３の装置により実行される工程を示すフローチャートである。
【図５】更なる実施形態を示すブロック図である。
【図６】図２の工程の更に別の実施形態を示すフローチャートである。
【図７】管理された暗号乱数生成方式の模式図である。
【図８】エスクロー鍵選択工程を示すフローチャートである。
【図９】エスクロー鍵を安全に利用する方法を示すフローチャートである。
【発明を実施するための形態】
【００２０】
図１を参照すると、暗号乱数生成器（ＥＣＲＮＧ）１０は、楕円曲線計算を行う演算ユ
ニット１２を含んでいる。ＥＣＲＮＧはまた、状態値ｓを保持するセキュアレジスタ１４
を含み、初期設定点ＰとＱの対を受信するための入力１６と１８の対を有している。点Ｐ
とＱは、既知と仮定されている楕円曲線点である。出力２０は、暗号モジュール２２への
乱整数の通信のために供給される。レジスタ１４の初期内容は、シード入力Ｓにより供給
される。
【００２１】
点Ｐを表現する入力１６は、第１実施形態においては、そのような使用に適切であると
して公表された既知の値から選択される。
【００２２】
入力１８は、一方向性関数の出力から、典型的には、入力として点Ｐを受信するＳＨＡ
１またはＳＨＡ２のような暗号的に安全なハッシュ関数である、ハッシュ関数の形態で得
られる。関数２４は、任意のビット列Ａ上で作動し、ハッシュされた出力２６を生成する
。出力２６は、更なる処理のために演算ユニット１２に適用されて入力Ｑを供給する。
【００２３】
作動中、ＥＣＲＮＧは、シードとしてビット列を受信し、それはレジスタ１４に格納さ
れる。シードは、秘密に維持され、ランダム性およびハミング重さのような、特定のアプ
リケーションに適合するように選択された、前もって確立された暗号基準に合うように選
択される。
【００２４】
ｄが知られる可能性がないことを確実にするために（例えば、Ｐ＝ｄＱおよびｅｄ＝１
ｍｏｄ ｎのように）、入力１６と１８の１つまたは両者は、検証可能にランダムであ
るように選択される。図１の実施形態においては、Ｑは、その入力が点Ｐを含むハッシュ
関数（好ましくは一方向性）の出力から導出することにより、検証可能にランダムである
ような方法で選択される。図２に示されるように、任意の列Ａがステップ２０２で選択さ
れ、ＡのハッシュＨは、Ｐと随意にＳを、ハッシュベース関数ＦＨ（）への入力としてス
テップ２０４で計算され、ハッシュＨは、演算ユニット１２により、ステップ２０６にお
いて所望の体Ｆの体の元Ｘに変換される。Ｐは、前計算されていても、固定でも、または
検証可能にランダムな選択値として選択されてもよい。体の元Ｘは、Ｑのｘ座標として見
なされる（このように、Ｑの「圧縮された」表現）。ｘ座標は、ステップ２０８で、所望
の楕円曲線Ｅ上で有効性がテストされ、Ｘが有効かどうかがステップ２１０において決定
される。有効の場合は、元Ｘにより提供されたｘ座標は伸張され、ステップ２１２におい
て点Ｑを提供する。ｙ座標の２つの可能な値のどちらを選択するかは、一般的には、ハッ
シュ値から導出される。
【００２５】
点ＰとＱは、個々の点１６と１８において適用され、演算ユニット１２は、点ｓＱを
計算し、ここでｓは、レジスタ１４に格納されている現在の値である。演算ユニット１２
は、点（この例では、点ｓＱ）のｘ座標を整数に変換し、その値を打ち切って、ｒ＝ｔ（
ｚ（ｓＱ））を得る。打ち切られた値ｒは出力２０に供給される。
【００２６】
演算ユニット１２は同様に値を計算して、ｓがレジスタ１４の値であるときのｓＰを
計算することでレジスタ１４を更新して、点ｓＰのｘ座標を整数ｕに変換する。整数ｕは
、レジスタに格納され、次の反復に対してｓと置換される。（上記を繰り返す）
【００２７】
上述したように、点Ｐもまた検証可能にランダムであってよいが、確立されたまたは
固定された値であってもよい。従って、図１の実施形態は、ある基点（例えば、Ｐ）が既
にハードウェアに実装されている場合は、システムに適用または後付け追加できる。典型
的に、基点Ｐは、米国連邦情報処理標準規格（ＦＩＰＳ：Federal Information Processi
ng Standard）１８６−２で推奨されているような、ある既存の基点になる。そのような
場合は、Ｐは、検証可能にランダムになるようには選択されない。
【００２８】
一般的に、点Ｐを、ハッシュ関数の入力に含むことは、ハッシュ関数の一方向性特性
のため、およびＱが既に決定されたＰから導出されるので、Ｐが、Ｑが決定される前に決
定されたことを確実にする。ＰはＱの前に決定されたので、ＰがＱの倍数（例えば、Ｐ＝
ｅＱの場合）として選択されることは有り得ず、従って、ｄを見出すことは一般的には、
離散対数問題のランダムなケースを解くのと同じ程度難しいということは明確に理解でき
る。
【００２９】
このように、提供されたシード値Ｓと、提供されたハッシュに基づく関数Ｆ（）を有
しているので、検証者は、Ｑ＝Ｆ（Ｓ，Ｐ）を決定でき、ここにおいてＰは、検証可能に
ランダムではなくてもよい。同様に、Ｐ＝Ｆ（Ｓ，Ｑ）を計算して同じ効果を得ることが
できるが、これは、Ｘ９．８２の初期の草案におけるＰの値が、ＦＩＰＳ１８６−２で指
定された基点と同一であるならば必要ではないと考えられている。
【００３０】
上記に概要を記述したように、ビット列からＱを生成することは、ＥＣＲＮＧ１０の
外部で行うことができ、または好ましくは、演算ユニット１２を使用して内部的に行うこ
とができる。ＰとＱの両方が検証可能にランダムであることが必要な場合は、図１に点線
で示される第２ハッシュ関数２４が、ビット列Ａから点Ｐの座標を生成するために組み込
まれる。入力の少なくとも１つに対してハッシュ関数を提供することにより、検証可能に
ランダムな入力が得られる。
【００３１】
生成される出力は、点ｓＰのｘ座標から導出されるということも分かるであろう。従
って、入力１６と１８は、点ＰとＱのｘ座標であってよく、対応するｓＰとｓＱの値は、
モントゴメリ（Montgomery）乗法技術を使用して得られ、それにより、ｙ座標を取り出す
必要性を除去する。
【００３２】
Ｑを選択する方法の代替方法は、Ｑを、そのビット表現が、例えば、名前の表現のよ
うに、ある既知のｄとＰに対してＱ＝ｄＰを生成することで生成するのが困難なある列を
含むように、ある標準形で選択することである。この方法と、好適な方法の間の中間的な
形式もまた存在し、その場合は、Ｑは部分的に標準形であり、部分的に検証可能にランダ
ムに導出されるということは理解されよう。Ｑのそのような選択は、検証可能にランダム
であっても、標準形であっても、またはある中間形式であっても、検証可能と呼ばれる。
【００３３】
図３と図４に示す、ＥＣＲＮＧの出力に対する鍵エスクロー攻撃を防止する別の代替
方法は、打切り関数２８をＥＣＲＮＧ１０に追加して、ＥＣＲＮＧ出力を、圧縮楕円曲線
点の長さの約半分に打ち切ることである。好ましくは、この演算は、図１および図２の好
適な方法に追加して行われるが、それは、鍵エスクロー攻撃を防止する主要な手段として
行うことができるということは理解されよう。打切りの利点は、単一のＥＣＲＮＧ出力ｒ
に関連するＲ値のリストは、典型的には、探すのが現実的には不可能であるということで
ある。例えば、１６０ビット楕円曲線群に対して、リストに可能な点Ｒの数は、約２８０
であり、リストを探索することは、離散対数問題を解くことと同じ程度に困難である。こ
の方法のコストは、出力長が事実上半分にされるので、ＥＣＲＮＧの効率が半分になると
いうことである。
【００３４】
図５と図６に示す、更に別の代替方法は、新しい入力を生成するハッシュ関数のよう
な、３４として特定される、別の一方向性関数ＦＨ２を介する、ＥＣＲＮＧの出力のフィ
ルタ処理を備える。ここで再び、好ましくは、この演算は、図２に示される好適な方法に
追加して行われるが、鍵エスクロー攻撃を防止する主要な手段として行うこともできる。
追加のハッシュは、演算ユニット１２で行われる楕円曲線演算と比べて、相対的にコスト
が小さく、ＥＣＲＮＧの安全性を問題になるほど削減しない。
【００３５】
上述したように、エスクロー鍵の存在を有効的に防止するためには、検証可能にラン
ダムなＱに、検証可能にランダムなＰまたは、前もって確立されたＰを付随させるべきで
ある。前もって確立されたＰは、広く公開され、ＥＣＲＮＧ１２の概念の前に選択された
と容認されている点Ｐであってよく、従ってそれは、Ｑは、Ｐが確立されたときに生成さ
れていなかったので、Ｐが、Ｐ＝ｅＱとして選択されることは不可能であったことを意味
する。
【００３６】
上記の技術が、侵入口を「閉じる」ことにより、ＥＣＲＮＧを使用するシステムの安
全性を確実にする一方、ＰとＱの可能性のある相互依存性、つまり、ｅの存在を注意深く
使用することにより、Ｐ＝ｅＱであることの利点を利用することもまた可能である。
【００３７】
そのようなシナリオにおいては、値ｅは、エスクロー鍵と見なしてよい。ＰとＱが管
理者により制御されたセキュリティドメインにおいて確立されると、ドメインでＱを生成
するエンティティは、ｅを知って（またはｄを知ることで間接的に知って）それを行う。
管理者は、その標準に従うすべてのＥＣＲＮＧに対してエスクロー鍵を有することになる
。
【００３８】
エスクロー鍵は、ある状況では利点があることが知られている。エスクロー鍵は、バッ
クアップ機能を提供する。暗号鍵が紛失した場合、その鍵で暗号化されたデータもまた失
われる。しかし、暗号鍵は一般的には、乱数生成器の出力である。従って、ＥＣＲＮＧが
、暗号鍵Ｋの生成に使用されると、エスクロー鍵ｅを使用して、暗号鍵Ｋを取り出すこと
が可能になる。エスクロー鍵は、盗聴に使用されるような、他の機能も提供する。この場
合、信頼できる法施行機関が、犯罪者の暗号化トラフィックを復号することが必要になり
、これを行うため、暗号鍵を取り出すために、エスクロー鍵を使用できることを所望する
ことがある。
【００３９】
図７は、それぞれが、ドメイン４０の個々のメンバーと関連している、多数のＥＣＲ
ＮＧ１０を有するドメイン４０を示している。ドメイン４０は、他のドメイン４０ａ、４
０ｂ、および４０ｃと、インターネットのようなネットワーク４２を介して通信する。ド
メインの各ＥＣＲＮＧは、同一の入力ＰとＱの対を有している。ドメイン４０は、安全な
方法でエスクロー鍵ｅを維持する管理者４４を含む。
【００４０】
管理者４４は、Ｑ＝ｅＰとなるようなエスクロー鍵ｅを知り得るようにＰとＱの値を
選択する。ドメイン４０の他のメンバーは、ＰとＱの値を使用し、それにより、管理者４
４に、組織のすべてのメンバーに対して機能するエスクロー鍵ｅを与える。
【００４１】
これは、暗号鍵の紛失に対する対処策としてのバックアップ機能において最も有益で
ある。エスクロー鍵ｅは、メンバー特有にすることもでき、それにより、各メンバーは、
管理者４４から選択された点からの自分自身のエスクローｅ’を有する。
【００４２】
図８において、全体を数字４００で示したように、管理者は、最初は、所望の楕円曲
線に対する標準生成器Ｐとして一般的に選択される点Ｐを選択する（４０２）。そして、
管理者は、値ｄを選択して、点Ｑは、適切なサイズの、ある乱整数ｄに対して、Ｑ＝ｄＰ
として決定される（４０４）。エスクロー鍵ｅは、ｅ＝ｄ−１ ｍｏｄ ｎとして計算さ
れ（４０６）、ここでｎは、生成器Ｐの位数であり、管理者により格納される。
【００４３】
そのようなエスクロー鍵３４ｅの安全な使用法は、数字５００により全体的に示され
、図９に示されている。管理者４４が、まず設置され（５０２）、そしてエスクロー鍵ｅ
が選択され、管理者４４により格納される（５０４）。
【００４４】
エスクロー鍵が完全な有効性で機能するためには、エスクロー管理者４４は、取り出
されるＥＣＲＮＧ出力値ｋ（例えば１６）の前に生成されたＥＣＲＮＧ出力値ｒへの直接
アクセスを必要とする。一方向性関数または暗号アルゴリズムを介するｒへの間接アクセ
スを有するだけでは十分ではない。これを達成するための形式化された方法は、図７にお
いて４６で示され、図９においてステップ５０６において示されるように、ＥＣＲＮＧ１
２を有する各メンバーに、管理者４４と通信させることである。これは暗号化ファイル格
納システムまたは暗号化電子メールアカウントに対して最も有益であろう。よりシームレ
スな方法を暗号アプリケーションに適用できる。例えば、ウェブ（ＨＴＴＰ）トラフィッ
クを安全にするＳＳＬおよびＴＬＳプロトコルにおいて、クライアントおよびサーバーは
、ハンドシェークを行い、それらの最初の行動は、平文で送信された乱数値を交換するこ
とである。
【００４５】
他の多数のプロトコルは、しばしばナンスと呼ばれる、そのような乱数値を交換する。
エスクロー管理者がこれらのナンスを観測し、それらの記録を維持すれば（５０８）、後
日、必要なｒ値を決定することが可能になる。これにより、管理者が、クライアントまた
はサーバー（ドメインのメンバーであれば誰でも）のＥＣＲＮＧ１２の次の状態を決定す
ることができ（５１０）、それにより、次のＥＣＲＮＧ１２値を取り出すことができる。
特に、ＳＳＬまたはＴＬＳセッションに対する暗号鍵が導出されるランダムなプレマスタ
ー秘密を一般的に生成するクライアントに対して、エスクロー鍵は、セッション鍵の取り
出しを可能にする。セッション鍵の取り出しは、全ＳＳＬまたはＴＬＳセッションの取り
出しを可能にする。
【００４６】
セッションが記録されていれば、それは取り出すことができる。これは長期私的鍵を
危険に晒すものではなく、ＥＣＲＮＧの出力から得られたセッション鍵のみで、エスクロ
ーに関連する一般的な疑いに関するいかなる問題も緩和される。
【００４７】
エスクロー鍵は他の状況において、不都合な点も有することが知られているが、特定
のセキュリティドメイン内の制御により、これらの問題のいくつかは緩和される。例えば
、非拒絶に対するデジタル署名では、署名者以外は、署名鍵を有しないということが重要
で、そうでなければ、署名者は、合法的に署名の拒絶を主張できる。エスクロー鍵の存在
は、他のあるエンティティが署名鍵へのアクセスを有し、それにより署名者は、エスクロ
ー鍵が使用されて署名鍵を得て、その署名を生成したと主張することを可能にする。しか
し、ドメインが特別な組織、または組織の一部に制限されている場合は、組織が署名を拒
絶できないということで十分である。暗号鍵とは異なり、紛失した署名鍵は、データの紛
失を意味しないので、署名鍵のバックアップはほとんど必要ない。
【００４８】
本発明は、ある特別な実施形態を参照して説明されてきたが、この技術に精通した者
には、本明細書に付随する請求項で概要が記載される本発明の精神および範囲から逸脱す
ることのない本発明の種々の修正が明白であろう。
【特許請求の範囲】
【請求項１】
ネットワーク内でセキュリティドメインのためのエスクロー鍵を確立する方法であって、該方法は、楕円曲線乱数生成器へのそれぞれの入力としての１対の点ＰＱを、前記点の間の関係がＰ＝ｅＱとなるように確立するステップと、前記関係ｅを、管理者と共にエスクロー鍵として格納するステップと、前記楕円曲線乱数生成器から、前記ドメイン内の暗号演算で使用される乱数を生成するステップとを含む、方法。
【請求項２】
本願明細書に記載された発明。
【請求項１】
ネットワーク内でセキュリティドメインのためのエスクロー鍵を確立する方法であって、該方法は、楕円曲線乱数生成器へのそれぞれの入力としての１対の点ＰＱを、前記点の間の関係がＰ＝ｅＱとなるように確立するステップと、前記関係ｅを、管理者と共にエスクロー鍵として格納するステップと、前記楕円曲線乱数生成器から、前記ドメイン内の暗号演算で使用される乱数を生成するステップとを含む、方法。
【請求項２】
本願明細書に記載された発明。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【公開番号】特開２０１２−７３６３８（Ｐ２０１２−７３６３８Ａ）
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１１−２５９３６３（Ｐ２０１１−２５９３６３）
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【分割の表示】特願２００７−５５１５２２（Ｐ２００７−５５１５２２）の分割
【原出願日】平成１８年１月２３日（２００６．１．２３）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
【公開日】平成２４年４月１２日（２０１２．４．１２）
【国際特許分類】
【出願番号】特願２０１１−２５９３６３（Ｐ２０１１−２５９３６３）
【出願日】平成２３年１１月２８日（２０１１．１１．２８）
【分割の表示】特願２００７−５５１５２２（Ｐ２００７−５５１５２２）の分割
【原出願日】平成１８年１月２３日（２００６．１．２３）
【出願人】（３９７０７１７９１）サーティコム コーポレーション (38)
【Ｆターム（参考）】
[ Back to top ]