(57)【特許請求の範囲】
【請求項１】
ホスト機器であるサーバと１台以上の端末との間の鍵共有方式であって、
前記端末は、
内部状態のランダム性により擬似乱数を生成すると共に、前記内部状態を更新するための状態更新用データの一部を抽出する擬似乱数生成手段と、
前記擬似乱数生成手段により抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する公開鍵暗号化手段と
を有し、
前記サーバは、
前記端末から送信された公開鍵暗号を受信して前記抽出データを復号する公開鍵復号手段と、
前記復号された抽出データに基づいて、前記端末の前記擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成し、前記累積エントロピーと所定の閾値との比較結果に基づいて前記擬似乱数生成手段の内部状態のランダム性判定結果を生成するランダム性評価手段と、
前記ランダム性判定結果が合格を示しているときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第１の鍵共有手段と
を有することを特徴とする鍵共有方式。
【請求項２】
前記ランダム性評価手段は、前記ランダム性判定結果を前記端末へ送信する機能を備え、
前記端末は、前記サーバから送信された前記ランダム性判定結果を受信し、受信した前記ランダム性判定結果が不合格を示しているときに前記公開鍵暗号化手段による前記公開鍵暗号化を実行させ、前記ランダム性判定結果が合格を示しているときに所定の第２の鍵共有アルゴリズムによる鍵共有処理を実行する第２の鍵共有手段を有することを特徴とする請求項１記載の鍵共有方式。
【請求項３】
前記サーバは、前記端末の前記擬似乱数生成手段に対して、前記状態更新用データの一部を抽出する抽出ルールを動的に設定する設定手段を有することを特徴とする請求項１記載の鍵共有方式。
【請求項４】
前記端末は、外部乱数生成手段を有し、
前記擬似乱数生成手段は、前記外部乱数生成手段の出力の一部を前記擬似乱数生成手段のエントロピーソースとして用い、前記外部乱数生成手段の出力の残りを出力系列と加算して、前記公開鍵暗号化手段へ供給する最終的な擬似乱数を生成することを特徴とする請求項１記載の鍵共有方式。
【請求項５】
前記ランダム性評価手段は、前記復号された抽出データにおけるビットパタンの頻度テーブルを備え、受信して復号された前記抽出データのビットパタンの発生確率を、前記頻度テーブルを用いて推定し、前記発生確率の推定結果で前記累積エントロピーを更新し、更新後の前記累積エントロピーを前記端末の前記擬似乱数生成手段の内部状態のランダム性の判定に利用することを特徴とする請求項１記載の鍵共有方式。
【請求項６】
ホスト機器であるサーバと１台以上の端末との間の鍵共有方法であって、
前記端末内にて、擬似乱数生成手段により擬似乱数を生成させると共に、前記擬似乱数生成手段の内部状態を更新するための状態更新用データの一部を抽出する第１のステップと、
前記端末が、前記第１のステップで抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する第２のステップと、
前記サーバが、前記端末から送信された公開鍵暗号を受信して前記抽出データを復号する第３のステップと、
前記サーバ内にて、前記復号された抽出データに基づいて、前記端末の前記擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成する第４のステップと、
前記第４のステップで生成された前記累積エントロピーと所定の閾値との比較結果に基づいて前記擬似乱数生成手段の内部状態のランダム性判定結果を生成する第５のステップと、
前記サーバ内にて、前記ランダム性判定結果が合格のときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第６のステップと
を含むことを特徴とする鍵共有方法。
【請求項７】
前記第５のステップで生成された前記ランダム性判定結果を前記端末へ送信する第７のステップと、
前記端末が、前記サーバから送信された前記ランダム性判定結果を受信して、受信した前記ランダム性判定結果が合格を示しているか否かを判定する第８のステップと、
前記第８のステップで前記ランダム性判定結果が不合格を示しているときに前記第２のステップによる前記公開鍵暗号化を実行させ、前記ランダム性判定結果が合格を示しているときに所定の第２の鍵共有アルゴリズムによる鍵共有処理を実行する第９のステップと
を含むことを特徴とする請求項６記載の鍵共有方法。
【請求項８】
前記サーバが、前記端末の前記第１のステップにおいて前記状態更新用データの一部を抽出する抽出ルールを動的に設定する第１０のステップを含むことを特徴とする請求項６記載の鍵共有方法。
【請求項９】
ホスト機器であるサーバに接続された１台以上の端末が有するコンピュータに鍵共有処理を行わせる鍵共有プログラムであって、
前記コンピュータに、
内部状態のランダム性により擬似乱数を生成する擬似乱数生成手段の前記内部状態を更新するための状態更新用データの一部を抽出する抽出ステップと、
前記抽出ステップで抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する公開鍵暗号化及び送信ステップと、
前記サーバ内において受信した前記公開鍵暗号化された前記抽出データを復号し、復号した前記抽出データに基づいて生成した前記擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーと所定の閾値との比較結果に基づいて前記サーバが生成して送信した前記擬似乱数生成手段の内部状態のランダム性判定結果を前記サーバから受信して、前記ランダム性判定結果が合格を示しているか否かを判定する判定ステップと、
前記判定ステップで前記ランダム性判定結果が不合格を示しているときに前記公開鍵暗号化及び送信ステップによる前記公開鍵暗号化を実行させ、前記ランダム性判定結果が合格を示しているときに所定の鍵共有アルゴリズムによる鍵共有処理を実行する鍵共有ステップと
を実行させることを特徴とする鍵共有プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は鍵共有方式、鍵共有方法及び鍵共有プログラムに係り、特にホスト機器となるサーバと端末との間の通信の暗号化に使用する鍵共有方式、鍵共有方法及び鍵共有プログラムに関する。
【背景技術】
【０００２】
通信秘匿のために暗号化は必須の技術となっている。現代暗号は、アルゴリズムを公開しても暗号の鍵を秘密にすることによって通信秘匿を実現する。暗号を用いた通信ではデータを暗号化するための秘密鍵を、通信を行う送信側と受信側との間でどのように共有するのかが課題となる。
【０００３】
現代暗号は、大きく共通鍵暗号と公開鍵暗号とに分類される。前者はＤＥＳ(Data Encryption Standard)やＡＥＳ(Advanced Encryption Standard)などのブロック暗号が代表的で、送信側と受信側とが予め同一の秘密鍵を持っていることを前提とする。後者はＲＳＡ暗号が代表的で、暗号化と復号で使用する鍵が異なり、暗号化で使用する鍵は公開鍵、復号で使用する鍵は秘密鍵と呼ばれる。公開鍵暗号は、公開鍵から秘密鍵を推測することは非常に困難という性質を持つ。このため、公開鍵は公開してあっても、秘密鍵の漏洩がなければ公開鍵で暗号化した情報は秘密鍵を持つ者のみが復号可能となる。ただし、公開鍵暗号は共通鍵暗号よりも非常な大きな計算量が必要である。このため、公開鍵暗号を用いて共通鍵暗号で使用する秘密鍵（セッション鍵と呼ばれる）を共有し、実際のデータは共通鍵暗号を用いて暗号化処理を行うことが多い。
【０００４】
公開鍵暗号を使用する際には、公開鍵暗号で使用する演算を定義するドメインパラメータや公開鍵が正しいことを保証する必要がある。有限体上の離散対数を用いる方式の場合には、ドメインパラメータは剰余系演算を定める素数ｐと、離散対数問題の生成元となるmod_pの元ｇ (mod p）とからなる。また、秘密鍵ｘ mod qに対して公開鍵は、ｙ＝ｇx mod pと一般に定められる。ここで、素数ｑは元ｇの位数、つまりｇa＝１ mod pとなる最小の自然数ａである。ｑはｐ−１の約数となる。本明細書では、ドメインパラメータと公開鍵とを併せて公開パラメータと呼ぶことにする。
【０００５】
公開鍵暗号を使用した代表的な鍵共有アルゴリズムである、ディフィー(Diffie)とヘルマン(Hellman)により発表されたDiffie-Hellman鍵共有アルゴリズムは、公開鍵のｇr mod pやｇs mod pを盗聴して秘密情報を求める受動的な攻撃には強いが、なりすましなどの能動的な攻撃には弱いことが知られている。そこで、Diffie-Hellman鍵共有アルゴリズムを用いる際には、通信相手を認証することが必須となる。認証付鍵共有に関しては、例えば米国標準技術局(National Institute of Standards and Technology;ＮＩＳＴ)が発行する非特許文献１に記載されている方法が知られている。
【０００６】
ところで、公開鍵パラメータの正当性保証に関しては認証局による公開鍵証明書に基づく方式がよく知られている。その一方で、閉じた暗号通信システムでは、信頼できる機関から公開情報を直接入手することによって、信頼性を確保することが可能となる。
【０００７】
図１２は、上記の閉じた暗号通信システムの一例のブロック図を示す。同図に示すように、この暗号通信システム５００は、パラメータ生成手段５０１、ホスト機器となるサーバ５０２及び端末５０３からなる。１台のサーバ５０２に対して端末５０３は複数存在し、それぞれの端末５０３はサーバ５０２と通信を行う。パラメータ生成手段５０１は、端末配布時に公開鍵暗号のパラメータ、鍵情報を生成し、サーバ５０２と端末５０３に必要な情報を設定してから端末５０３をユーザに渡す。
【０００８】
この暗号通信システム５００では、サーバ５０２と端末５０３の安全性は大きく異なる状況を想定する。つまり、サーバ５０２は安全な場所にあり、秘密情報の漏洩や不正な処理などのリスクは非常に小さいと仮定する。一方、端末５０３は盗難や情報流出の危険性が高いと仮定する。公開鍵パラメータを端末５０３に事前に設定しておく場合、その端末５０３は比較的長期にわたってその設定を利用することになる。そのために、攻撃者が端末５０３のそれらの情報を入手した際には、比較的長期にわたってその公開鍵パラメータに対しての攻撃機会が発生することになる。
【０００９】
高強度セキュリティを要求されるアプリケーションにおいては、そのような状況は望ましくなく、攻撃者が端末５０３から得られる情報は極力小さくすることが望まれる。そのためには、端末５０３には何の鍵情報も事前に格納せずに、セッション開始時に公開鍵パラメータをサーバ５０２が端末５０３に送信する方法が考えられる。
【００１０】
しかしながら、このとき、サーバ５０２のなりすましが容易に行えてしまうという問題が発生する。また、不正なサーバが不正なドメインパラメータを端末５０３に送付した場合には、秘密鍵がたとえ漏洩していなくても安全性が損なわれる場合がある。例えば、非常に小さな位数を持つ元ｇを攻撃者が設定した場合には、攻撃者がたとえ秘密鍵を知らなくても、Diffie-Hellmanアルゴリズムで共有される鍵情報の推測が可能になってしまう。
【００１１】
そこで、この課題に対処する鍵共有システムが特許文献１に開示されている。特許文献１に記載の鍵共有システムは、本発明者により開示された鍵共有方式で、以下、図１３及び図１４を用いてその発明の概略を説明する。図１３及び図１４中、図１２と同一構成部分には同一符号を付してある。なお、鍵共有は、有限体上のDiffie-Hellman鍵共有アルゴリズムを使用しているが、有限体上の楕円曲線の有理点のなす加群を用いても同様の鍵共有を行うことができる。
【００１２】
図１３は、図１２のパラメータ生成手段５０１で生成する情報と、サーバ５０２及び端末５０３が保持する情報を示す。図１３において、パラメータ生成手段５０１は、端末５０３が与えられたときにドメインパラメータのリスト｛p(i),q(i),g(i):i=1,2,3,...｝を生成すると共に、対応する秘密鍵と公開鍵の(x(i),y(i))を設定する。また、パラメータ生成手段５０１は、p(i)とg(i)とを連接したビット列であるp(i)||g(i)を入力データとするハッシュ値h(i)（＝Hash(p(i)||g(i))）を計算する。
【００１３】
サーバ５０２は、パラメータ生成手段５０１から入力されるドメインパラメータのリストと秘密鍵と公開鍵の(x(i),y(i))とからなるリスト６０１を端末５０３毎に保持する。端末５０３は、パラメータ生成手段５０１から入力されるハッシュ値h(i)を公開鍵y(i)と併せたリスト６０２を格納する。
【００１４】
次に、図１４のフローチャートを用いて、特許文献１記載の鍵共有システムの動作について説明する。まず、端末５０３は、サーバ５０２に対して端末ＩＤを送信する（ステップＳ４０１）。これにより、サーバ５０２は、送信元の端末５０３に対してのパラメータリストの中で使用するパラメータのインデックスｉを決定する（ステップＳ４０２）。続いて、サーバ５０２は、インデックスｉと対応するp＝p(i)とg＝g(i)とを連接したビット列p||gを生成し、それを送信する（ステップＳ４０３、Ｓ４０４）。
【００１５】
端末５０３は、受信したビット列p||gに対してハッシュ値Hash(p||g)を計算し、格納しているハッシュ値h(i)と比較する（ステップＳ４０５）。一致していない場合は不正なパラメータが送付されたとして鍵共有処理を終了する。端末５０３は、ステップＳ４０５でｐ，ｇの正当性を確認できた場合は、以下のDiffie-Hellman鍵共有アルゴリズムによる鍵共有処理を実行する。
【００１６】
すなわち、端末５０３は、乱数ｒを発生し（ステップＳ４０６）、その乱数ｒを用いてｗ（＝ｇr mod p）を計算し（ステップＳ４０７）、それをサーバ５０２へ送信する（ステップＳ４０８）。サーバ５０２は、秘密鍵ｘ(i)を使って受信したビット列ｗからＺ（＝ｗx(i) mod p）を計算し（ステップＳ４０９）、その値Ｚから鍵導出関数ｋｄｆ()を用いて秘密鍵Ｋを生成する（ステップＳ４１０）。
【００１７】
一方、端末５０３は、公開鍵ｙ(i)と乱数ｒを使ってｚ(＝ｙ(i)r mod p）を計算し（ステップＳ４１１）、その値ｚから鍵導出関数ｋｄｆ()を用いて秘密鍵ｋを生成する（ステップＳ４１２）。ステップ３１０、３１２の鍵導出関数ｋｄｆ()の入力である「otherinfo」は、サーバ５０２と端末５０３との間で事前に共有している情報である（公開情報でよい）。これにより、端末ＩＤなどの端末５０３に固有の情報を情報「otherinfo」に含ませることで、なりすましの防止を図ることができる。なお、鍵導出関数ｋｄｆ()には、ハッシュ関数などを適用する。
【００１８】
図１４に示したフローチャートから分かるように、特許文献１記載の鍵共有方式の安全性は、端末５０３の生成する乱数ｒのランダム性（攻撃者に対しての予測の困難さ）に大きく依存する。乱数生成器は、物理現象に基づく真性乱数生成器（非決定性ランダムビット生成器）と擬似乱数生成器（決定性ランダムビット生成器）とに大きく分類される。後者は乱数生成器の内部状態に基づいて出力を決定するが、出力されるビット列を観測しても内部状態や次の出力を推測することが困難であるという性質を持ち、ハッシュ関数やブロック暗号を用いて乱数を発生する。擬似乱数発生器は、例えば非特許文献２に詳細に記載されている。
【００１９】
ハードウェアを利用した真性乱数生成器を使用することが理想的ではあるが、これは環境や時間の経過によって特性も変わり、その評価が難しいことなどから端末５０３には擬似乱数生成器を用いることが適切となる場合が多い。
【００２０】
図１５は、擬似乱数生成器の一例の動作機能図を示す。擬似乱数生成器７００は、内部状態（メモリ）７０１に基づいて、出力生成処理７０２により出力するビット列である擬似乱数を決定する。この擬似乱数のビット幅は、出力生成処理７０２で使用するハッシュ関数やブロック暗号のデータ幅によって決まる。出力生成処理７０２を実行するときには、アルゴリズムによって定められているタイミングで内部状態の更新処理７０３を実行し、次の出力に備える。
【００２１】
擬似乱数生成器７００は、攻撃者がある時点で内部状態７０１の推測に成功した場合、その先のすべての系列を攻撃者が決定できてしまうため、外部からランダム性を取り入れて内部状態７０１を更新するリフレッシュ処理７０４が必要となる。また、擬似乱数生成器７００は、起動時に内部状態７０１を設定する起動時処理７０５も必要となる。
【００２２】
外部のランダム性は、端末の機器におけるランダム性を持つ要素である“エントロピーソース”から取得する。端末５０３が計算機であれば、エントロピーソースとしてプロセス番号、サーバ５０２との通信にかかった時間、ハードディスクへのアクセス速度などが候補として挙げられる。これらのデータを表すビット列を図１５ではエントロピー情報７０６と呼んでいる。リフレッシュ処理７０４は、状態更新用データであるエントロピー情報７０６も用いて内部状態７０１を更新する処理であるため、攻撃者がある時点の内部状態７０１の推測に成功したとしても、エントロピー情報７０６を入手できなければ、攻撃者がリフレッシュ処理後の状態の推定を行うことは困難になる。
【００２３】
図１５の起動時処理７０５の入力となる固有情報は、計算機であればＭＡＣ(Media Access Control)アドレスやＩＰ(Internet Protocol)アドレスといった機器固有の情報であり、固定値である。起動時に起動時処理７０５がこの固有情報を利用して内部状態７０１を設定することで、機器毎に異なる内部状態７０１を設定することができる。また、更新処理７０３、リフレッシュ処理７０４の入力となる付加情報７０７は、例えば公開鍵などのランダム性はないがテンポラリの情報である。この付加情報７０７も、固有情報と同様に、なりすましなどに対する実用的な対策の一つとなる。
【００２４】
上記の更新処理７０３は、非特許文献２に記載されている擬似乱数生成処理の更新処理（Update()）を適用することができる。また、上記の出力生成処理７０２は、非特許文献２に記載されている擬似乱数生成処理の出力生成処理（Output()）を適用することができる。
【００２５】
図１６（ａ）は、非特許文献２に記載の擬似乱数生成処理の更新処理（Update()）を示し、鍵付きハッシュ関数であるＨＭＡＣ(Hashed based Message Authentication Code)を利用した更新処理を示す。また、図１６（ｂ）は、非特許文献２に記載の擬似乱数生成処理の出力生成処理（Output()）の具体的構成を示す。図１６（ａ）、（ｂ）において、（Ｋ,Ｖ）が内部状態となる。図１６（ａ）、（ｂ）中の「ＨＭＡＣ」については、非特許文献３に開示されている。
【００２６】
なお、特許文献２には、２台の通信装置間の鍵共有方式において、一方の通信装置が公開鍵を生成して他方の通信装置へ送信する構成が開示されている。また、特許文献３には、乱数検証手段にて受信した乱数と一致するかどうかを比較し、その比較結果に基づいて鍵が共有されたと認識することが開示されている。
【先行技術文献】
【特許文献】
【００２７】
【特許文献１】特開２００９−２３９７３７号公報
【特許文献２】特開２００６−１４０７４３号公報
【特許文献３】特開平９−３１２６４３号公報
【非特許文献】
【００２８】
【非特許文献１】NIST Special Publication (SP) 800-56A,「Recommendation for Pair-Wise Key Establishment Schemes Using Discrete Logarithm Cryptography」,2006年
【非特許文献２】NIST Special Publication 800-90,「Recommendation for Random Number Generator Using Deterministic Random Bit Generators (Rivised)」,2007年
【非特許文献３】NIST Federal Information Processing Standards (FIPS) Publication 198,「The Keyed-Hash Message Authentication Code(HMAC)」,2002年
【発明の概要】
【発明が解決しようとする課題】
【００２９】
図１２に示した、安全なサーバ５０２と、攻撃などに対して脆弱な端末５０３とを含む暗号通信システム５００における鍵共有で生成される秘密鍵の安全性は、端末５０３で使用する乱数の推測困難性に大きく依存する。この端末５０３の脆弱性に対する課題を解決することを目的とする特許文献１に記載の鍵共有方式は、秘密鍵の安全性が端末の生成する乱数に依存し、その乱数を発生する乱数生成器としては、擬似乱数生成器を用いることが適切となることが多く、擬似乱数生成器として非特許文献２に記載されたものを用いることができる。
【００３０】
しかしながら、そのような擬似乱数生成器を用いたとしても、特許文献１記載の鍵共有方式では、安全性を保証するために端末が生成した擬似乱数の乱数性を端末自身で検証することが望ましく、その検証を行うことには計算リソースや評価基準の設定や端末からの統計情報の漏洩リスクなどの問題がある。
【００３１】
また、特許文献２及び特許文献３では、乱数生成器は安全であるという前提の下での構成が開示されているに過ぎず、特許文献３に記載の乱数検証手段は乱数生成器の検証を行ってはいない。
【００３２】
本発明は以上の点に鑑みなされたもので、安全なサーバと、攻撃などに対して脆弱な端末とを含む暗号通信システムにおいて、端末自身が擬似乱数のランダム性の検証を行わないようにすることにより、端末が検証を行う際の評価基準等の設定や情報漏洩リスクの問題をなくすことが可能な鍵共有方式、鍵共有方法及び鍵共有プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３３】
上記の目的を達成するため、本発明の鍵共有方式は、ホスト機器であるサーバと１台以上の端末との間の鍵共有方式であって、
端末は、内部状態のランダム性により擬似乱数を生成すると共に、内部状態を更新するための状態更新用データの一部を抽出する擬似乱数生成手段と、擬似乱数生成手段により抽出された状態更新用データの一部である抽出データを、擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化してサーバへ送信する公開鍵暗号化手段とを有し、
サーバは、端末から送信された公開鍵暗号を受信して抽出データを復号する公開鍵復号手段と、復号された抽出データに基づいて、端末の擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成し、累積エントロピーと所定の閾値との比較結果に基づいて擬似乱数生成手段の内部状態のランダム性判定結果を生成するランダム性評価手段と、ランダム性判定結果が合格を示しているときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第１の鍵共有手段とを有することを特徴とする。
【００３４】
また、上記の目的を達成するため、本発明の鍵共有方法は、ホスト機器であるサーバと１台以上の端末との間の鍵共有方法であって、端末内にて、擬似乱数生成手段により擬似乱数を生成させると共に、擬似乱数生成手段の内部状態を更新するための状態更新用データの一部を抽出する第１のステップと、端末が、第１のステップで抽出された状態更新用データの一部である抽出データを、擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化してサーバへ送信する第２のステップと、サーバが、端末から送信された公開鍵暗号を受信して抽出データを復号する第３のステップと、サーバ内にて、復号された抽出データに基づいて、端末の擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成する第４のステップと、第４のステップで生成された累積エントロピーと所定の閾値との比較結果に基づいて擬似乱数生成手段の内部状態のランダム性判定結果を生成する第５のステップと、サーバ内にて、ランダム性判定結果が合格のときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第６のステップとを含むことを特徴とする。
【００３５】
また、上記の目的を達成するため、本発明の鍵共有プログラムは、ホスト機器であるサーバに接続された１台以上の端末が有するコンピュータに鍵共有処理を行わせる鍵共有プログラムであって、コンピュータに、
内部状態のランダム性により擬似乱数を生成する擬似乱数生成手段の内部状態を更新するための状態更新用データの一部を抽出する抽出ステップと、抽出ステップで抽出された状態更新用データの一部である抽出データを、擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化してサーバへ送信する公開鍵暗号化及び送信ステップと、サーバ内において受信した公開鍵暗号化された抽出データを復号し、復号した抽出データに基づいて生成した擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーと所定の閾値との比較結果に基づいてサーバが生成して送信した擬似乱数生成手段の内部状態のランダム性判定結果をサーバから受信して、ランダム性判定結果が合格を示しているか否かを判定する判定ステップと、判定ステップでランダム性判定結果が不合格を示しているときに公開鍵暗号化及び送信ステップによる公開鍵暗号化を実行させ、ランダム性判定結果が合格を示しているときに所定の鍵共有アルゴリズムによる鍵共有処理を実行する鍵共有ステップと
を実行させることを特徴とする。
【発明の効果】
【００３６】
本発明によれば、公開鍵暗号化を適用することで端末は秘密鍵を保持する必要がなく、また、端末が発生する擬似乱数のランダム性の判定をサーバが行うため、端末自身が擬似乱数のランダム性の検証を行う必要がなく、これにより端末が検証を行う際の評価基準等の設定や情報漏洩リスクの問題をなくすことができる。
【図面の簡単な説明】
【００３７】
【図１】本発明の鍵共有方式の一実施形態のブロック図である。
【図２】図１中の端末の鍵共有モジュールの動作説明用フローチャートである。
【図３】図２中のステップＳ１０４の詳細動作説明用フローチャートである。
【図４】図１中の端末の擬似乱数生成手段がビット若しくはシンボル単位で１個おきにビット（列）を抽出してデータＳを生成するルールを模式的に示す図である。
【図５】図３中のステップＳ２０５の詳細動作説明用フローチャートである。
【図６】図１中のサーバの鍵共有処理の動作説明用フローチャートである。
【図７】図６中のステップＳ３０１の詳細動作説明用フローチャートである。
【図８】図６中のステップＳ３０４の詳細動作説明用フローチャートである。
【図９】エントロピー情報の頻度テーブルの一例の模式図である。
【図１０】エントロピー情報の頻度テーブルの他の例の模式図である。
【図１１】端末内の擬似乱数生成手段の動作の一例の説明図である。
【図１２】暗号通信ステムの一例のブロック図である。
【図１３】図１２中のパラメータ生成手段で生成する情報と、サーバ及び端末が保持する情報を示す図である。
【図１４】図１２の動作説明用フローチャートである。
【図１５】擬似乱数生成器の一例の動作機能図である。
【図１６】非特許文献２に記載されている擬似乱数生成処理の更新処理と出力生成処理とを示す図である。
【発明を実施するための形態】
【００３８】
次に、本発明の実施形態について、図面を参照して説明する。
【００３９】
図１は、本発明になる鍵共有方式の一実施形態のブロック図を示す。同図において、本実施形態の鍵共有方式１００は、端末１１０とサーバ１２０とから構成される。端末１１０は複数台がサーバ１２０に接続されていてもよい。
【００４０】
端末１１０は、鍵共有モジュール１１１を構成要素として持つ。鍵共有モジュール１１１は、鍵共有・公開鍵暗号化手段１１２及び擬似乱数生成手段１１３から構成される。また、端末１１０は、擬似乱数生成手段１１３にエントロピー情報を供給するエントロピーソースを持つ。鍵共有・公開鍵暗号化手段１１２は、擬似乱数生成手段１１３が生成する擬似乱数を使用して例えばDiffie-Hellman鍵共有アルゴリズムに基づき鍵共有処理を行う。また、鍵共有・公開鍵暗号化手段１１２は、擬似乱数生成手段１１３の内部状態を更新するための状態更新用データの一部を取り出し、それを例えばElGamal暗号アルゴリズムに基づき公開鍵暗号化してサーバ１２０へ送信する。
【００４１】
サーバ１２０は、乱数生成手段１２１及び鍵共有モジュール１２２を備える。乱数生成手段１２１は、鍵共有モジュール１２２の外部にある信頼できる乱数生成手段であり、鍵共有モジュール１２２が鍵共有処理で使用する乱数を鍵共有モジュール１２２に供給する。鍵共有モジュール１２２は、鍵共有・公開鍵復号手段１２３とランダム性評価手段１２４とを構成要素として持つ。
【００４２】
ランダム性評価手段１２４は、端末１１０から受信した状態更新用データの一部を更新したデータ（後述する累積エントロピーＥ）と所定の閾値との比較結果に基づいて得られた擬似乱数生成手段１１３の内部状態のランダム性判定結果を、鍵共有・公開鍵復号手段１２３を通して端末１１０へ送信する。また、ランダム性評価手段１２４は、上記のランダム性判定結果に応じて、鍵共有処理の実行を制御する。すなわち、ランダム性評価手段１２４は、ランダム性判定結果が合格のときには、例えばDiffie-Hellman鍵共有アルゴリズムに基づき鍵共有処理を実行する。また、ランダム性評価手段１２４は、ランダム性判定結果が不合格であるときには、鍵共有・公開鍵復号手段１２３が受信して復号した端末１１０から送信された公開鍵暗号化されたデータに基づいて、ランダム性評価・更新処理を行う。なお、上記の鍵共有処理と公開鍵暗号には同一の公開鍵パラメータが使用される。
【００４３】
次に、本実施形態の鍵共有方式１００の動作について説明する。
【００４４】
まず、端末１１０の鍵共有モジュール１１１の動作について、図２のフローチャートを併せ参照して説明する。
【００４５】
端末１１０の鍵共有モジュール１１１は、起動と共に擬似乱数生成手段１１３が起動時処理を実行し、擬似乱数生成手段１１３の状態ステータスを初期状態であることを示す“０”に設定する（ステップＳ１０１）。この擬似乱数生成手段１１３の起動時処理では、端末１１０の固有情報によって擬似乱数生成関数の内部状態の初期化が行われる。
【００４６】
続いて、擬似乱数生成手段１１３は起動後“スタンバイ”の動作となり、定期的に若しくは不定期的にエントロピーソースからエントロピー情報を更新する（ステップＳ１０２）。次に、鍵共有モジュール１１１は、ユーザ／アプリケーションから鍵共有処理実行の要求があるか否かを判定する（ステップＳ１０３）。鍵共有処理実行の要求がない場合は、ステップＳ１０２のスタンバイ動作を継続するが、鍵共有処理実行の要求がある場合は、鍵共有・公開鍵暗号化手段１１２が鍵共有処理を実行する（ステップＳ１０４）。この鍵共有処理では、鍵共有・公開鍵暗号化手段１１２は、後述するように、擬似乱数生成手段１１３からの出力である擬似乱数列も用いてサーバ１２０と通信を行い、擬似乱数生成手段１１３の内部状態のランダム性の検証の上で鍵共有アルゴリズムによる鍵共有処理を実行する。
【００４７】
続いて、鍵共有モジュール１１１は、ユーザ／アプリケーションから鍵共有モジュールの停止要求があるか否かを判定する（ステップＳ１０５）。鍵共有モジュール１１１は、鍵共有モジュールの停止要求がない場合は、ステップＳ１０２のスタンバイ動作に戻るが、鍵共有モジュールの停止要求がある場合は、動作を終了する。
【００４８】
次に、ステップＳ１０４の詳細動作について図３と共に説明する。
【００４９】
図３は、鍵共有処理ステップＳ１０４の詳細動作説明用フローチャートを示す。鍵共有・公開鍵暗号化手段１１２は、鍵共有処理起動時に、サーバ１２０に状態ステータスを送信し、サーバ１２０からはランダム性判定結果を受信する（ステップＳ２０１）。続いて、鍵共有・公開鍵暗号化手段１１２は、送信する状態ステータスが初期状態を示す“０”ではなく、かつ、受信したランダム性判定結果が合格であるかどうかを判定する（ステップＳ２０２）。鍵共有・公開鍵暗号化手段１１２は、ステップＳ２０２の判定条件を満たしているときには後述するステップＳ２０８に進んで鍵共有アルゴリズムによる鍵共有処理を実行するが、判定条件を満たしていないときには、擬似乱数生成手段１１３と共にステップＳ２０３〜Ｓ２０７の処理を実行する。
【００５０】
ステップＳ２０３では、擬似乱数生成手段１１３が、エントロピー情報からサーバ１２０に送信するデータを抽出し、鍵共有・公開鍵暗号化手段１１２に出力する。この抽出データは、擬似乱数生成手段１１３の内部状態を更新するための状態更新用データの一部であり、これを以下、抽出データＳと呼ぶ。続くステップＳ２０４では、擬似乱数生成手段１１３がリフレッシュ処理を実行する。続くステップＳ２０５では、鍵共有・公開鍵暗号化手段１１２が、抽出データＳを後述するように公開鍵暗号化してサーバ１２０に送信する、エントロピー情報送信処理を実行する。
【００５１】
続いて、ステップＳ２０６では、鍵共有・公開鍵暗号化手段１１２がサーバ１２０からランダム性判定結果を受信すると共に、状態ステータスが“０”のときには状態ステータスを初期状態でないことを示す“１”に設定する。そして、ステップＳ２０７では、鍵共有・公開鍵暗号化手段１１２がサーバ１２０から受信したランダム性判定結果が合格を示しているか否かを判定する。ランダム性判定結果が合格を示していないときには、端末鍵共有処理を終了するが、ランダム性判定結果が合格を示しているときには、鍵共有アルゴリズムによる鍵共有処理を実行する（ステップＳ２０８）。
【００５２】
図４は、ステップＳ２０３のエントロピー情報抽出処理を実行するために必要な、擬似乱数生成手段１１３の構成要素を示す。同図において、擬似乱数生成手段１１３は、エントロピー情報１１４から抽出手段１１５によりサーバ１２０に送信するデータＳを抽出する。エントロピー情報１１４はメモリであり、エントロピーソースの種類に対応したデータ＃１〜＃４・・・を保持している。抽出手段１１５は、エントロピー情報１１４の一部の情報を取り出し、送信用の抽出データＳを生成する。
【００５３】
図４は、ビット若しくはシンボル単位で１個おきにビット（列）を抽出してデータＳを生成するルールを模式的に示している。また、図４のソース＃３のようなランダム性が保証されているソースに関しては、サーバ１２０への送信を行わない設定も考えられる。図４に示すように、これらの抽出ルールをサーバ１２０から端末１１０に動的に設定することも考えられる。
【００５４】
次に、図３のステップＳ２０５の詳細動作について、図５と共に説明する。
【００５５】
図５は、エントロピー情報送信処理ステップＳ２０５の詳細動作説明用フローチャートを示す。ステップＳ２０５のエントロピー情報送信処理において、まず、擬似乱数生成手段１１３が、公開鍵暗号化で使用する擬似乱数（一定長のビット列）Ｒを生成して出力する（ステップＳ２０５１）。続いて、鍵共有・公開鍵暗号化手段１１２は、上記のビット列Ｒを乱数として使用して、擬似乱数生成手段１１３により擬似乱数生成手段１１３の内部状態を更新するための状態更新用データから抽出された抽出データＳを公開鍵で暗号化したデータを生成する（ステップＳ２０５２）。そして、鍵共有・公開鍵暗号化手段１１２は、ステップＳ２０５２で暗号化した抽出データＳをサーバ１２０に送信する（ステップＳ２０５３）。
【００５６】
次に、サーバ１２０の鍵共有処理について、図６と共に説明する。
【００５７】
図６は、サーバ１２０の鍵共有処理の動作説明用フローチャートを示す。まず、サーバ１２０内のランダム性評価手段１２４は、端末１１０の擬似乱数生成手段１１３の内部状態のランダム性判定処理を実行する（ステップＳ３０１）。このランダム性判定処理ステップＳ３０１の詳細動作は後述する。
【００５８】
続いて、サーバ１２０内の鍵共有・公開鍵復号手段１２３は、ステップＳ３０１で得られたランダム性判定結果が合格であるか否かを判定する（ステップＳ３０２）。鍵共有・公開鍵復号手段１２３は、ランダム性判定結果が合格であればステップＳ３０６に進んで鍵共有アルゴリズムによる鍵共有処理を実行し、ランダム性判定結果が不合格であれば、以下のステップＳ３０３〜Ｓ３０５の処理を実行する。
【００５９】
ステップＳ３０３では、鍵共有・公開鍵復号手段１２３が、端末１１０から図５のステップＳ２０５３で送信された暗号化データを受信し、これを復号して端末１１０のエントロピー情報からの抽出データＳを得る。続くステップＳ３０４では、ランダム性評価手段１２４が、鍵共有・公開鍵復号手段１２３から入力された抽出データＳに基づき、端末１１０の現在のエントロピー情報のランダム性（情報量）を算出してランダム性判定を行い、ランダム性評価手段１２４における抽出データの統計値を更新する。このランダム性評価・更新処理ステップＳ３０４の詳細動作は後述する。
【００６０】
そして、ステップＳ３０５では、鍵共有・公開鍵復号手段１２３が、ステップＳ３０４で得られたランダム性判定結果が合格であるか否かを判定する。鍵共有・公開鍵復号手段１２３は、ランダム性判定結果が合格であればステップＳ３０６に進んで鍵共有アルゴリズムによる鍵共有処理を実行し、ランダム性判定結果が不合格であれば、鍵共有処理を終了する。
【００６１】
次に、図６のステップＳ３０１の詳細動作について図７と共に説明する。
【００６２】
図７は、ランダム性判定処理ステップＳ３０１の詳細動作説明用フローチャートを示す。ランダム性評価手段１２４は、ステップＳ３０１において、各端末１１０毎の現在の内部状態のランダム性を見積もるための数値（以下、これを累積エントロピーＥと呼ぶ）を管理する。以下、図７のフローチャートを説明する。
【００６３】
ランダム性評価手段１２４は、端末１１０が送信した状態ステータスを鍵共有・公開鍵復号手段１２３を通して受信し（ステップＳ３０１１）、その状態ステータスが“０”である否かを判定する（ステップＳ３０１２）。ランダム性評価手段１２４は、状態ステータスが“０”であると判定したときには、端末１１０が起動時の状態と判断して、その端末１１０に対応する累積エントロピーＥを“０”にリセットし（ステップＳ３０１３）、その端末１１０に対して不合格を示すランダム性判定結果を、鍵共有・公開鍵復号手段１２３を通して通知する（ステップＳ３０１４）。
【００６４】
一方、ランダム性評価手段１２４は、ステップＳ３０１２で状態ステータスが“０”でないと判定したときには、端末１１０が起動時の状態ではないと判断して、その端末に対応する累積エントロピーＥの値が予め設定した閾値Ｔ以上であるか否かを判定する（ステップＳ３０１５）。ステップＳ３０１５にて累積エントロピーＥが閾値Ｔ未満であると判定したときには、ステップＳ３０１４に進んで不合格を示すランダム性判定結果を鍵共有・公開鍵復号手段１２３を通して端末１１０に通知する。
【００６５】
他方、ランダム性評価手段１２４は、ステップＳ３０１５で累積エントロピーＥが閾値Ｔ以上であると判定したときには、その端末１１０に対して合格を示すランダム性判定結果を、鍵共有・公開鍵復号手段１２３を通して通知する（ステップＳ３０１６）。続いて、ランダム性評価手段１２４は、その端末１１０の累積エントロピーＥを更新する（ステップＳ３０１７）。この更新は、鍵共有アルゴリズムで使用する乱数列の量に応じて小さくするもので、鍵共有アルゴリズムでは一定量の乱数列を使用するため、典型的には累積エントロピーＥに対して定数を減ずる形で行われる。
【００６６】
次に、ステップＳ３０４の詳細動作について図８と共に説明する。
【００６７】
図８は、ランダム性評価・更新処理ステップＳ３０４の詳細動作説明用フローチャートを示す。ランダム性評価・更新処理ステップＳ３０４において、まず、ランダム性評価手段１２４は、保持しているエントロピー情報の頻度テーブルを用いて、ステップＳ３０３で復元された抽出データＳに基づいて、端末１１０における現在のエントロピー情報が保持するエントロピーを推定する（ステップＳ３０４１）。このステップＳ３０４１では、頻度テーブルが例えば、復元された抽出データにおけるビットパタンと頻度とからなる頻度テーブルの場合は、受信して復元された抽出データのビットパタンの発生確率を頻度テーブルに基づいて推定する。
【００６８】
続いて、ランダム性評価手段１２４は、ステップＳ３０４１で推定したエントロピーを用いて、端末１１０の擬似乱数生成手段１１３の内部状態の累積エントロピーＥを更新する（ステップＳ３０４２）。この更新は、典型的には擬似乱数生成アルゴリズムから決定される上限の下、ステップＳ３０４１で推定したエントロピーを累積エントロピーＥに加算する形で行われる。
【００６９】
続いて、ランダム性評価手段１２４は、保持しているエントロピー情報の頻度テーブルを、受信して復元された抽出データＳに基づいて更新する（ステップＳ３０４３）。この頻度テーブルの更新のタイミングは、ステップＳ３０４２の処理に続いて行う必要はなく、鍵共有処理の終了後に実行することもできる。
【００７０】
続いて、ランダム性評価手段１２４は、前記のステップＳ３０１５と同様に、端末１１０に対応する累積エントロピーＥの値が予め設定した閾値Ｔ以上であるか否かを判定する（ステップＳ３０４４）。ステップＳ３０４４にて累積エントロピーＥが閾値Ｔ未満であると判定したときには、ステップＳ３０４７に進んで不合格を示すランダム性判定結果を鍵共有・公開鍵復号手段１２３を通して端末１１０に通知する。
【００７１】
他方、ランダム性評価手段１２４は、ステップＳ３０４４で累積エントロピーＥが閾値Ｔ以上であると判定したときには、その端末１１０に対して合格を示すランダム性判定結果を、鍵共有・公開鍵復号手段１２３を通して通知する（ステップＳ３０４５）。続いて、ランダム性評価手段１２４は、その端末１１０の累積エントロピーＥをステップＳ３０１７と同様に更新する（ステップＳ３０４６）。
【００７２】
図９は、ステップＳ３０４１、Ｓ３０４３で使用されるエントロピー情報の頻度テーブルの一例の模式図を示す。頻度テーブルは、図９（Ａ）に模式的に示すように、各端末とエントロピーソースの各ソースとを対応させたテーブルであり、そのテーブルの各欄は図９（Ｂ）に示すようにサーバ１２０が復号した抽出データにおけるビットパタンとその頻度から構成される。ここで、「頻度」は、対応するビットパタンがどの程度発生するかの確率を示す。なお、各ソースに対して端末のトータルを計算した頻度テーブルも考えられる。また、起動時からの時間経緯を考慮して、このような頻度テーブルを複数用意することも考えられる。
【００７３】
図１０は、ステップＳ３０４１、Ｓ３０４３で使用されるエントロピー情報の頻度テーブルの他の例の模式図を示す。他の例の頻度テーブルは、図１０（Ａ）に模式的に示すように、各端末毎に起動回数とエントロピーソースの各ソースとを対応させたテーブルであり、そのテーブルの各欄は図１０（Ｂ）に示すように起動後のエントロピー情報のビットパタンとその頻度から構成される。この頻度テーブルを用いた場合は、起動後のエントロピー情報の変化を考慮して擬似乱数生成手段１１３の内部状態のエントロピーを推定することが可能となる。
【００７４】
次に、上記の実施形態の要部について更に具体的かつ詳細に説明する。
【００７５】
端末１１０におけるステップＳ２０８の鍵共有アルゴリズム、及びサーバ１２０におけるステップＳ３０６の鍵共有アルゴリズムには、前述したDiffie-Hellman鍵共有アルゴリズムを適用することができる。このとき、ステップＳ２０５において用いられる抽出データＳの公開鍵暗号化アルゴリズムとしては、鍵共有アルゴリズムと同一ドメインパラメータと公開鍵とを用いてのElGamal暗号を適用するのが自然である。
【００７６】
このステップＳ２０５におけるElGamal暗号化は、図１４で用いた記述を用いると、Diffie-Hellman鍵共有アルゴリズムのドメインパラメータｐ（法となる素数）、ｇ（生成元）に対して、擬似乱数生成手段１１３からの出力である乱数Ｒを用いて、抽出データＳを次式による暗号文Ｃに変換することである。
【００７７】
Ｃ＝（ｇR mod p，Ｓ・ｙ(i)R mod p）          （１）
サーバ１２０は、ステップＳ１１３において、秘密鍵ｘ(i)と受信した暗号文Ｃ中のｇR mod pとから
ｙ(i)R mod p＝（ｇR）x(i) mod p          （２）
を求め、更に次式により抽出データＳを復号する。
【００７８】
Ｓ・ｙ(i)R ／ｙ(i)R mod p＝Ｓ            （３）
上記のｐ、ｇ、ｙ(i)の正当性の保証は、図１４で説明したと同様に実現することができる。
【００７９】
端末１１０が計算機の場合の典型的なエントロピーソースとしては、前述のようにプロセスＩＤ、ハードディスクのシーク時間、サーバ１２０との通信時間、プログラムの実行時間などが挙げられるが、真性乱数生成器やオペレーティングシステムが提供する外部乱数生成手段をエントロピーソースとして用いることも考えられる。
【００８０】
このとき、図１１に示すように、外部乱数生成手段の出力の一部を擬似乱数生成手段１１３のエントロピー情報１１４に保持されるエントロピーソースとして用い、外部乱数生成手段の出力の残りを擬似乱数生成手段１１３の出力生成処理１１６で得られた出力系列と加算器１１７にて加算して最終的な擬似乱数を生成する方式が考えられる。
【００８１】
また、端末１１０内の擬似乱数生成手段１１３で使用する擬似乱数生成アルゴリズムとしては、例えば非特許文献２に記載されている任意の安全性の保証されたアルゴリズムを使用することができる。図１６に示したＨＭＡＣを用いる擬似乱数アルゴリズムでＨＭＡＣのハッシュ関数としてＳＨＡ−２５６を使用する場合には、セキュリティ強度の最大値が２５６（ビット）であるため、累積エントロピーＥも「２５６」以下とすることが自然となる。このとき、サーバ１２０におけるステップＳ３０４２の累積エントロピーＥの更新時には、この値を上限として更新処理を行う。また、ステップＳ３０１５、Ｓ３０４４にて用いられる閾値Ｔは、システムが設定するセキュリティパラメータであり、ＳＨＡ−２５６のＨＭＡＣを使用する擬似乱数生成アルゴリズムでは、通常、「１１２」以上に設定される。
【００８２】
また、抽出データＳのソース＃１、＃２、＃３、・・・に対応するビットパタンを(s_1,s_2,s_3,・・・）として、図９に示した頻度テーブルから求められるビットパタンs_iの推定確率をp_iとすると、抽出データＳのランダム性（情報量）は各ソースが独立であるという仮定の下、次式により見積もることができる。
【００８３】
ｈ(Ｓ)＝−log p_1−log p_2−log p_3・・・          （４）
ここで、（４）式中logの底は２とする。また、ｈ(Ｓ)の単位はビットである。頻度テーブルの統計量が十分でない場合は、ベイズ推定などに基づいて補正値を考慮して推定確率p_iを決めることが適切である。また、事前に十分に学習して頻度テーブルを生成してから使用することも考えられる。
【００８４】
また、図９に示した頻度テーブルでは、抽出データＳに対して推定確率p_iが各端末１１０及び端末のトータルに対してそれぞれ求められるため、ｈ(Ｓ)もこれに応じて算出することができる。このとき抽出データＳのランダム性は、その最小値で見積もることが適切となる。このように、本実施形態では、サーバ１２０に各端末１１０のエントロピー情報を集約することによって、他の端末に対してのランダム性も測ることができるため、ランダム性評価の精度を向上させることができる。
【００８５】
なお、サーバ１２０内のランダム性評価手段１２４で使用する抽出データＳは、疑似乱数生成手段１１３のエントロピー情報の一部であるため、疑似乱数生成手段１１３のエントロピー情報のランダム性の推定値Ｈは、（４）式に対して
Ｈ＝λｈ(Ｓ)            （５）
と係数λを設定して導出する方式が考えられる。
【００８６】
エントロピー情報全体から比率ρでビットを抜き出して抽出データＳを生成する場合には、単純には上記係数λを１／ρに設定することになる。しかし、抽出データＳと前述したエントロピー情報の残りの部分とが独立とはみなせない場合には、係数λは１／ρより小さな値に設定することが適切となる。また、この独立性は仮定するが、サーバ１２０への送信時の漏洩を仮定する場合には、上記係数λを１／（ρ−１）に設定することが考えられる。これらの事項を総合的に考えて、サーバ１２０は抽出データＳから端末１１０のエントロピー情報のランダム性を定量化する。
【００８７】
また、図７のステップＳ３０１７及び図８のステップＳ３０４６の累積エントロピーＥの更新は、鍵共有で使用した乱数列の量に応じて累積エントロピーＥを減少させる処理となる。擬似乱数生成手段１１３の内部状態をランダムに設定して系列を発生させたテーブルを作成して、実際に発生した乱数列とのマッチングをとって内部状態を推定する攻撃を考えると、同一のテーブルであれば攻撃の成功確率は実際に取得した乱数列の長さに比例する。
【００８８】
そこで、鍵共有アルゴリズムで長さＬの乱数列を使用するとすれば、上記ステップＳ３０１７及びステップＳ３０４６の累積エントロピーＥの更新では、次式のＡで表される定数を現在の累積エントロピーＥから減ずる処理を行う。
【００８９】
Ｅ←Ｅ−Ａ，Ａ＝log（Ｌ）＋ｃ          （６）
ただし、（６）式中、ｃは適切な定数である。
【００９０】
ステップＳ２０５の抽出データＳの公開鍵暗号化処理の際にも、鍵共有アルゴリズムと同一長の乱数列を使用するため、図８のステップＳ３０４２の累積エントロピーＥの更新は、次式のＢで表される値を現在の累積エントロピーＥに加算する処理を行う。
【００９１】
Ｅ←Ｅ＋Ｂ，Ｂ＝max（Ｈ−Ａ，０）      （７）
ただし、（７）式中、Ｈ、Ａはそれぞれ（５）式、（６）式で示される値であり、またmax（ｘ，ｙ）は、ｘとｙとで値が大きい方を選択する関数である。
【００９２】
このように、本実施形態の鍵共有方式では、端末１１０が発生する擬似乱数のランダム性の判定（擬似乱数生成手段１１３の内部状態のランダム性の判定）をサーバ１２０が行うため、端末１１０自身が擬似乱数のランダム性の検証を行う必要がなく、これにより端末１１０が検証を行う際の評価基準等の設定や情報漏洩リスクの問題をなくすことができる。
【００９３】
また、本実施形態の鍵共有方式では、端末１１０のエントロピー情報を端末１１０自身が公開鍵暗号化してからサーバ１２０へ送信するため、通信路上のデータを第三者に取得されたとしても漏洩する情報を抑えることができる。また、本実施形態では、公開鍵暗号化を適用することで端末１１０には秘密鍵を保持する必要がなく、また、鍵共有アルゴリズムと公開鍵暗号とでドメインパラメータや公開鍵の公開情報を端末１１０とサーバ１２０とが共有するようにしているため、その正当性チェックなどの追加処理も不要となる。更に、本実施形態では、サーバ１２０において、各端末１１０のエントロピー情報を集約するようにしたため、ランダム性評価の精度を向上させることができる。
【００９４】
なお、本発明は以上の実施形態に限定されるものではなく、例えば、鍵共有モジュール１１１や１２２の各動作をそれぞれ端末１１０内やサーバ１２０内のコンピュータにより実行させる鍵共有プログラムも包含するものである。
【００９５】
上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【００９６】
（付記１）
ホスト機器であるサーバと１台以上の端末との間の鍵共有方式であって、
前記端末は、
擬似乱数を生成すると共に、その内部状態を更新するための状態更新用データの一部を抽出する擬似乱数生成手段と、
前記擬似乱数生成手段により抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する公開鍵暗号化手段と
を有し、
前記サーバは、
前記端末から送信された公開鍵暗号を受信して前記抽出データを復号する公開鍵復号手段と、
前記復号された抽出データに基づいて、前記端末の前記擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成し、前記累積エントロピーと所定の閾値との比較結果に基づいて前記擬似乱数生成手段の内部状態の前記ランダム性判定結果を生成するランダム性評価手段と、
前記ランダム性判定結果が合格を示しているときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第１の鍵共有手段と
を有することを特徴とする鍵共有方式。
【００９７】
（付記２）
前記ランダム性評価手段は、前記ランダム性判定結果を前記端末へ送信する機能を備え、
前記端末は、前記サーバから送信された前記ランダム性判定結果を受信し、そのランダム判定結果が不合格を示しているときに前記公開鍵暗号化手段による前記公開鍵暗号化を実行させ、前記ランダム判定結果が合格を示しているときに所定の第２の鍵共有アルゴリズムによる鍵共有処理を実行する第２の鍵共有手段を有することを特徴とする付記１記載の鍵共有方式。
【００９８】
（付記３）
前記ランダム性評価手段は、前記累積エントロピーが前記閾値以上であるとき合格を示し、前記閾値未満のときは不合格を示す前記ランダム性判定結果を生成することを特徴とする付記１記載の鍵共有方式。
【００９９】
（付記４）
前記サーバは、前記端末の前記擬似乱数生成手段に対して、前記状態更新用データの一部を抽出する抽出ルールを動的に設定する設定手段を有することを特徴とする付記１記載の鍵共有方式。
【０１００】
（付記５）
前記端末は、外部乱数生成手段を有し、
前記擬似乱数生成手段は、前記外部乱数生成手段の出力の一部を前記擬似乱数生成手段のエントロピーソースとして用い、前記外部乱数生成手段の出力の残りを出力系列と加算して、前記公開鍵暗号化手段へ供給する最終的な擬似乱数を生成することを特徴とする付記１記載の鍵共有方式。
【０１０１】
（付記６）
前記ランダム性評価手段は、前記復号された抽出データにおけるビットパタンの頻度テーブルを備え、受信して復号された前記抽出データのビットパタンの発生確率を、前記頻度テーブルを用いて推定し、その推定結果で前記累積エントロピーを更新し、更新後の前記累積エントロピーを前記端末の前記擬似乱数発生手段の内部状態のランダム性の判定に利用することを特徴とする付記１記載の鍵共有方式。
【０１０２】
（付記７）
前記頻度テーブルは、前記サーバに接続された個々の前記端末毎に、又はすべての前記端末をまとめた頻度テーブルであることを特徴とする付記６記載の鍵共有方式。
【０１０３】
（付記８）
前記ランダム性評価手段は、前記累積エントロピー更新後に前記頻度テーブルを前記復号された抽出データに基づいて更新することを特徴とする付記６又は７記載の鍵共有方式。
【０１０４】
（付記９）
前記公開鍵暗号化手段による公開鍵暗号化と、前記第１の鍵共有手段による鍵共有処理とは同一の公開鍵パラメータを使用することを特徴とする付記１乃至８のうちいずれか一項記載の鍵共有方式。
【０１０５】
（付記１０）
前記公開鍵暗号化手段は、ElGamal暗号により公開鍵暗号化を行い、前記第１及び第２の鍵共有手段は、Diffie-Hellman鍵共有アルゴリズムにより鍵共有処理を行うことを特徴とする付記２乃至８のうちいずれか一項記載の鍵共有方式。
【０１０６】
（付記１１）
ホスト機器であるサーバと１台以上の端末との間の鍵共有方法であって、
前記端末内にて、擬似乱数生成手段により擬似乱数を生成させると共に、前記擬似乱数生成手段の内部状態を更新するための状態更新用データの一部を抽出する第１のステップと、
前記端末が、前記第１のステップで抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する第２のステップと、
前記サーバが、前記端末から送信された公開鍵暗号を受信して前記抽出データを復号する第３のステップと、
前記サーバ内にて、前記復号された抽出データに基づいて、前記端末の前記擬似乱数生成手段の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成する第４のステップと、
前記第４のステップで生成された前記累積エントロピーと所定の閾値との比較結果に基づいて前記擬似乱数生成手段の内部状態の前記ランダム性判定結果を生成する第５のステップと、
前記サーバ内にて、前記ランダム性判定結果が合格のときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する第６のステップと
を含むことを特徴とする鍵共有方法。
【０１０７】
（付記１２）
前記第５のステップで生成された前記ランダム性判定結果を前記端末へ送信する第７のステップと、
前記端末が、前記サーバから送信された前記ランダム性判定結果を受信して、そのランダム性判定結果が合格を示しているか否かを判定する第８のステップと、
前記第８のステップで前記ランダム判定結果が不合格を示しているときに前記第２のステップによる前記公開鍵暗号化を実行させ、前記ランダム判定結果が合格を示しているときに所定の第２の鍵共有アルゴリズムによる鍵共有処理を実行する第９のステップと
を含むことを特徴とする付記１１記載の鍵共有方法。
【０１０８】
（付記１３）
前記第５のステップは、前記累積エントロピーが前記閾値以上であるとき合格を示し、前記閾値未満のときは不合格を示す前記ランダム性判定結果を生成することを特徴とする付記１１記載の鍵共有方法。
【０１０９】
（付記１４）
前記サーバが、前記端末の前記第１のステップにおいて前記状態更新用データの一部を抽出する抽出ルールを動的に設定する第１０のステップを含むことを特徴とする付記１１記載の鍵共有方法。
【０１１０】
（付記１５）
前記第１のステップは、外部乱数生成手段の出力の一部をエントロピーソースとして用いて前記状態更新用データの一部を抽出し、前記外部乱数生成手段の出力の残りを出力系列と加算して、前記第２のステップで使用する最終的な擬似乱数を生成することを特徴とする付記１１記載の鍵共有方法。
【０１１１】
（付記１６）
前記第５のステップは、受信して復号された前記抽出データのビットパタンの発生確率を、前記復号された抽出データにおけるビットパタンの頻度テーブルを用いて推定し、その推定結果で前記累積エントロピーを更新し、更新後の前記累積エントロピーを前記端末の前記擬似乱数発生手段の内部状態のランダム性の判定に利用することを特徴とする付記１１記載の鍵共有方法。
【０１１２】
（付記１７）
前記頻度テーブルは、前記サーバに接続された個々の前記端末毎に、又はすべての前記端末をまとめた頻度テーブルであることを特徴とする付記１６記載の鍵共有方法。
【０１１３】
（付記１８）
前記第５のステップは、前記累積エントロピー更新後に前記頻度テーブルを前記復号された抽出データに基づいて更新することを特徴とする付記１６又は１７記載の鍵共有方法。
【０１１４】
（付記１９）
前記第２のステップによる公開鍵暗号化と、前記第６のステップによる鍵共有処理とは同一の公開鍵パラメータを使用することを特徴とする付記１１乃至１８のうちいずれか一項記載の鍵共有方法。
【０１１５】
（付記２０）
前記第２のステップは、ElGamal暗号により公開鍵暗号化を行い、前記第６のステップ及び前記第８のステップは、Diffie-Hellman鍵共有アルゴリズムにより鍵共有処理を行うことを特徴とする付記１２乃至１８のうちいずれか一項記載の鍵共有方法。
【０１１６】
（付記２１）
ホスト機器であるサーバに接続された１台以上の端末が有するコンピュータに鍵共有処理を行わせる鍵共有プログラムであって、
前記コンピュータに、
擬似乱数を生成すると共に、擬似乱数生成の内部状態を更新するための状態更新用データの一部を抽出する抽出ステップと、
前記抽出ステップで抽出された前記状態更新用データの一部である抽出データを、前記擬似乱数を使用して所定の公開鍵アルゴリズムに基づき公開鍵暗号化して前記サーバへ送信する公開鍵暗号化及び送信ステップと
を実行させることを特徴とする鍵共有プログラム。
【０１１７】
（付記２２）
前記サーバが受信した前記公開鍵暗号化された前記抽出データを復号し、復号されて前記抽出データに基づいて生成して送信した前記擬似乱数の内部状態のランダム性判定結果を受信して、そのランダム性判定結果が合格を示しているか否かを判定する判定ステップと、
前記判定ステップで前記ランダム判定結果が不合格を示しているときに前記公開鍵暗号化及び送信ステップによる前記公開鍵暗号化を実行させ、前記ランダム判定結果が合格を示しているときに所定の鍵共有アルゴリズムによる鍵共有処理を実行する鍵共有ステップと
を更に実行させることを特徴とする付記２１記載の鍵共有プログラム。
【０１１８】
（付記２３）
１台以上の端末に接続されたホスト機器であるサーバが有するコンピュータに鍵共有処理を行わせる鍵共有プログラムであって、
前記コンピュータに、
前記端末が、擬似乱数を生成して、その擬似乱数の内部状態を更新するための状態更新用データの一部を所定の公開鍵アルゴリズムに基づき公開鍵暗号化して送信した公開鍵暗号を受信して、前記状態更新用データの一部である抽出データを復号する復号ステップと、
前記復号された抽出データに基づいて、前記端末の前記擬似乱数の現在の内部状態のランダム性を見積もるための数値である累積エントロピーを生成する累積エントロピー生成ステップと、
生成された前記累積エントロピーと所定の閾値との比較結果に基づいて前記擬似乱数の内部状態の前記ランダム性判定結果を生成するランダム性判定結果生成ステップと、
前記ランダム性判定結果が合格のときに所定の第１の鍵共有アルゴリズムによる鍵共有処理を実行する鍵共有ステップと
を実行させることを特徴とする鍵共有プログラム。
【符号の説明】
【０１１９】
１００  鍵共有方式
１１０、５０３  端末
１１２  鍵共有・公開鍵暗号化手段
１１３  擬似乱数生成手段
１１４  エントロピー情報（メモリ）
１１５  抽出手段
１１６  出力生成処理
１１７  加算器
１２０、５０２  サーバ
１２１  乱数生成手段
１２２、１１１  鍵共有モジュール
１２３  鍵共有・公開鍵復号手段
１２４  ランダム性評価手段
５００  暗号通信システム
５０１  パラメータ生成手段
【図１】
0005440285.tif 000002
【図２】
0005440285.tif 000003
【図３】
0005440285.tif 000004
【図４】
0005440285.tif 000005
【図５】
0005440285.tif 000006
【図６】
0005440285.tif 000007
【図７】
0005440285.tif 000008
【図８】
0005440285.tif 000009
【図９】
0005440285.tif 000010
【図１０】
0005440285.tif 000011
【図１１】
0005440285.tif 000012
【図１２】
0005440285.tif 000013
【図１３】
0005440285.tif 000014
【図１４】
0005440285.tif 000015
【図１５】
0005440285.tif 000016
【図１６】
0005440285.tif 000017