JP2000502822A - 高速で安全な暗号化のための改良された暗号的に安全な疑似ランダム・ビット・ジェネレータ - Google Patents

Abstract

(57)【要約】 暗号的に安全な疑似ランダム・ビット・ジェネレータ（１００）は、フロントエンド・ジェネレータ(１０２)、セレクタ(１０４)、ランダム関数プロセッサ(１０６)、グラフ・プロセッサ(１０８)、およびビットに関する排他的論理和回路（１１０）を含む。この暗号的に安全な疑似ランダム・ビット・ジェネレータ（１００）は、ビット・ストリングに対するある一方向関数を使用することによりビット・ストリングを伸長する。加えて、ビット・ストリングは、拡大グラフを用いて他の入力ビット・ストリングから生成される。伸長されたビット・ストリングおよび拡大グラフからのビット・ストリングは、ビットに関する排他的論理和回路において結合される。

Description

【発明の詳細な説明】 高速で安全な暗号化のための改良された暗号的に 安全な疑似ランダム・ビット・ジェネレータ 関連出願 本特許出願は以下の米国仮特許出願の利益を主張する。 Ramaranthnam Venkatesan についての１９９６年８月１６日に出願された「改 良された疑似ランダム・ジェネレータ」("An Improved Pseudo-RandomGenerator ")とタイトル付けされたシリアル番号６０／０２３，９６０ Ramaranthnam Venkatesan についての１９９７年１月８日に出願された「高速 で安全な暗号化」("Fast and Secure Encryption")とタイトル付けされたシリア ル番号６０／０３５，２２０ これらの仮出願の内容を参照によりここに取り入れる。本特許出願の主題は１ ９９６年５月７日にWilliam A.Aiello、Sivararnakrishnan Rajagopalan および Ramaranthnam Venkatesan を発明者として発行された「疑似ランダム・ジェネレ ータ」("Pseudo-Random Generator")とタイトル付けされた米国特許第５，５１ ５，３０７号の主題にも関連する。本特許は、本特許出願の譲受人であるＢellC ommunications Research，Inc.に譲渡されている。この特許の内容を参照により ここに取り入れる。本発明の背景 本発明の分野 本発明は高速で安全な暗号化を提供する装置および方法に向けられている。高 速で安全な暗号化を、長く安全なランダム・ビット・ストリングを高速に提供す る改良された暗号的に安全な疑似ランダム・ビット・ジェネレータにより提供す る。 関連技術の説明 ランダム・ナンバー（または以下で議論する見かけ上のランダム・ナンバー） の生成は多くのプロセスで用いられる。ランダム・ナンバーを補助入力として用 いるプロセスには、ソーティング、複雑なシステムのシミュレーションおよびテ スト、暗号化、ならびに他の暗号プロセスが含まれる。高速暗号アプリケーショ ンは、物理デバイスから直接には十分速く生成できない長いストリングのランダ ム・ナンバーをしばしば必要とする。 補助入力の「ランダムさ」がプロセスにとって非常に重要な場合がある。例え ば、ランダム・ナンバー・ジェネレータの「ランダムさ」は暗号の安全性にとっ てしばしば重要である。質の悪いランダム・ナンバー・ジェネレータは、敵によ る暗号システムの攻撃を許し得る相関および再生問題を引き起こすことがある。 他方、完全なランダム・ナンバー・ジェネレータを実現することは不可能かもし れない。真のランダム・シーケンスをコンピュータ上で生成することは不可能で あると信じられている。それは、データをコンピュータに入力し、コンピュータ がプログラムされた予測可能なプロセスをデータに対して実行し、およびコンピ ュータが（プロセスを知っている誰かに対して）予測可能な出力を生成するから である。 その結果、疑似ランダム・シーケンス・ジェネレータが開発された。疑似ラン ダム・シーケンス・ジェネレータは非常に大きな数のランダム・ビットを提供す る。疑似ランダム・ジェネレータは時々ランダムに「見える」ジェネレータとし て定義される。すなわち、それはよく知られたランダムさの統計的テストをパス する。汎用疑似ランダム・ジェネレータは、一定の暗号アプリケーションなどの 多くのアプリケーションにとって都合が悪い。例えば、暗号アプリケーションに 用いられるジェネレータが暗号的に安全であることは重要である。これは以下の ことを意味する。 ジェネレータをＧ（ｓ）＝Ｒ，ｓ∈｛０，１｝ⁿ，Ｒ∈｛０，１｝^m，ｍ＞ｎと する。ここで、 Ｒは生成されたランダム・ビット・ストリングである。 ｓはビット・ストリングのシードである。 ｎは整数である。そして、 ｍはビット・ストリングのビット数である。 そして、ビット・テストは以下の方法で行われる。 ｓを秘密にしたまま、１ビットを除いたＲのすべてを明らかにする： Ｒ＝ｂ₁，ｂ₂,...，ｂ_i+1,...，ｂ_m そして、すべてのビットｂ_iに対して、実行可能な実行時間を有するすべてのア ルゴリズムが１／２より大きい確率で明らかにされていないビットを予測可能で あるべきではない。もちろん、シードｓについて徹底的なサーチを行い、ビット を正確に計算することは可能であるが、それには実行不可能な時間がかかる。暗 号的に強固であることの要件は、この徹底的なサーチがこの攻撃を行うほとんど 最高の方法であることを要求する。すなわち、上で議論した汎用疑似ランダム・ ジェネレータの「ランダムに見えること」に加えて、「暗号的に安全な疑似ラン ダム（ＣＳＰＲ:cryptogaraphically secure pseudo-random）ビット・ジェネレ ータ」は時々予測できないことと定義される。すなわち、シーケンスを生成する アルゴリズムまたはハードウェア、およびビット・ストリングのすべての以前の ビットの完全な知識を与えられたとしても、次のランダム・ナンバーが何である かを予測することが計算的に実行不可能である。 好ましい実施形態においては、ＣＳＰＲビット・ジェネレータは、短いランダ ムなシードを入力として受け取り、そして（ＤＥＳまたは一方向ハッシュ関数な どの）一方向関数(one-way function)を繰り返し用いて、真のランダム・ビット ・ストリングと区別できない長い疑似ランダム・ビット・ストリングを生成する 。（簡単にいえば、一方向関数とは、簡単に計算できるが、その範囲の大部分に ついて逆にすることが難しい関数である。） 従来のＣＳＰＲビット・ジェネレータに関する１つの問題は、ソフトウェアの 暗号化において経験される。ソフトウェアの暗号化は、ビデオ・ストリームの暗 号化およびＴＣＰ／ＩＰレイヤの暗号化などの多くのリアルタイム・アプリケー ションにおいて、ボトルネックを与える。例えば、ワークステーション上でビデ オ・オンライン・ソフトウェアを暗号化するためにＤＥＳのような暗号を用いる 典型的な試みは、数秒後のビデオのフリージング・アップをもたらす。これは、 暗号化を実行するのに典型的に必要な追加のオーバーヘッドが大きいという事実 による。暗号化を追加したときにパフォーマンスが大きく変化しないような小さ なオーバーヘッドのみを追加するアルゴリズムを有することが望ましい。同様の コメントが、インターネット・アプリケーションのカーネル・レベルにおけるパ ケットの暗号化について当てはまる。 この問題に対する１つの解決策は、新しい暗号化アルゴリズムをデザインする ことであるが、この解決策は実用的ではない。なぜなら、新しい暗号システムが 安全であると信用される前に、新しいアルゴリズムが研究され、暗号システム上 で実行され、新しいアルゴリズムは攻撃により暗号システムを破るであろうから である。代わりに、いかなる（信用された）既存の暗号に対しても（代わりとし て）用いることができる高速アルゴリズムを開発し、それを攻撃することは、信 用された暗号または別の信用された暗号プロセスを攻撃することを含むというこ とを論ずることもできる。信用されている暗号の例は、もちろんＤＥＳである。 しかしながら、何か１つの特定の暗号に依存することを避け、いかなる暗号をも 用いることができることが好ましい。その結果、新しいアルゴリズムは、実際に 用いられているものと同じくらい安全であろう。この場合、正式な論証およびそ の実際のテストされた含蓄を有するべきである。しかし、ユーザは新しい構造に ついてのより消耗的で高価な暗号解読を避けることができる。 第２のより実用的な解決策は、上記の米国特許第５，５１５，３０７号（「’ ３０７特許」）において見つかる。’３０７特許における発明の好ましい実施形 態では、遅い疑似ランダム・ナンバー・ジェネレータを、長いランダム・ビット ・ストリングを生成するプレプロセッシング・ステップとして用いている。そし て、ランダム・アフィン・コード(Random Affine Codes)および拡大グラフ(expa ndergraphs)に基づくいくつかの特殊な構造を用いて、このストリングを「伸長 」(“stretches”)する。’３０７には、いかなる暗号をも用いることができる デバイスについて記述されている。このデバイスは、長いストリングを提供し、 証明可能な安全特性を有するランダム・ナンバー・ジェネレータである。 本発明の目的は、ソフトウェア暗号化の際のボトルネックを削減するＣＳＰＲ ビット・ジェネレータを提供することである。 本発明の別の目的は、暗号化の際のオーバヘッドを削減することである。 本発明のさらに別の目的は、改良されたＣＳＰＲビット・ジェネレータを用い た高速で安全な暗号化を提供することである。 本発明のさらなる目的は、以前のＣＳＰＲビット・ジェネレータに比べて使用 するメモリが少ないＣＳＰＲビット・ジェネレータを提供することである。本発明の概要 これらの、および他の本発明の目的は、本発明による暗号的に安全な疑似ラン ダム・ビット・ジェネレータにより達成される。本発明では、疑似ランダム・ナ ンバー・ジェネレータを、長いランダム・ビット・ストリングを生成するプレプ ロセッシング・ステップとして用いている。その後、ビット・ストリングに対し てある一方向関数を実行することにより、ビット・ストリングを「伸長」する。 好ましい実施形態においては、拡大グラフに基づく特殊な構造も用いる。一方向 関数および拡大グラフにより生成されるストリングについて互いに排他的論理和 をとる(exclusive-ored)ことが好ましい。 好ましい実施形態では、以下の方式で動作がなされる。遅いが安全なジェネレ ータＧ₀を想定する。 １．Ｇ₀を用いて、ランダム・ナンバーｘ₁、ｘ₂,...，ｘ_nを生成する。 ２．伸長関数を用いて、ランダム・ナンバーをＲ＝ｒ₁，ｒ₂,,...，ｒ_nに伸長 する。ここで、各ｒ_iはｘ_iよりもあらかじめ決められた量だけ長い。 ３．Ｒを１回のパッド(one-time pad)として暗号化のために用いることができ る。 このプロセスは、長く、ランダムで、暗号的に安全なビット・ストリングを提 供する。このビット・ストリングは、ビデオ・ストリーム暗号化、ＴＣＰ／ＩＰ レイヤ暗号化などのリアルタイム、オンライン暗号化に適した暗号化プロセスを サポートするのに十分なくらい速い。図面の簡単な説明 これらの、および他の本発明の特徴は以下の図面を参照することにより明らか にされる： 図１は、本発明によるＣＳＰＲビット・ジェネレータの好ましい実施形態を示 すブロック・ダイアグラムであり； 図２は、ランダム関数プロセッサの動作を示すブロック・ダイアグラムであり ； 図３は、本発明によるＣＳＰＲの第２の実施形態のブロック・ダイアグラムで ある。好ましい実施形態の詳細な説明 説明の明確化のため、本発明を以下のセクションにより説明する。 Ｉ．概観 本発明の動作および構造の概観を図１を参照して提供する。 ＩＩ．ランダム関数プロセッサ ランダム関数プロセッサを図２を参照して説明する。 ＩＩＩ．グラフ・プロセッサおよび排他的論理和回路 グラフ・プロセッサおよび排他的論理和回路を簡単に説明する。本発明の第２ の実施形態を図３を参照して説明する。 ＩＶ．本発明を用いた暗号化 本発明によるＣＳＰＲビット・ジェネレータを用いた暗号化方法を説明する。 Ｖ．本発明の有利な点および実装 本発明に関する有利な点および実装の問題を論ずる。 ＶＩ．結論 結論を提供する。 Ｉ．概観 図１は、本発明による改良された暗号的に安全な疑似ランダム・ビット・ジェ ネレータ１００の第１の好ましい実施形態のブロック・ダイアグラムである。デ バイスには、フロントエンド・ジェネレータ１０２、セレクタ１０４、ランダム 関数プロセッサ１０６、グラフ・プロセッサ１０８、および排他的論理和回路（ ＸＯＲ）１１０が含まれる。フロントエンド・ジェネレータ１０２は３つの入力 を受け取る：第１のシードｘ_O、第２のシードｈ、およびランダム・キーｍ。疑 似ランダム・ジェネレータ１００はこれらの入力を用いてランダム・ビット・ス トリングｚ_tを出力する。 ジェネレータ１００は、ランダム・ビット・ストリングｂ_iをフロントエンド ・ジェネレータ１０２から受け取る。受け取ったビットはその後、ランダム関数 プロセッサ１０６およびグラフ・プロセッサ１０８により実行されるプロセスに より「伸長」される(以下で論ずるように、いくつかのアプリケーションに適し た ランダム・ビット・ストリングを、グラフ・プロセッサ１０８を用いないで生成 することも考えられる)。この「伸長」プロセスは、フロントエンド・ジェネレ ータ１０２により提供されるものよりも大きいランダム・ビット・ストリングを 提供する。このジェネレータ１００は、長く、ランダムで、暗号的に安全なビッ ト・ストリングを出力する。このジェネレータ１００は、ビデオ・ストリーム暗 号化、ＴＣＰ／ＩＰレイヤ暗号化などのリアルタイム、オンライン暗号化に適し た暗号化プロセスをサポートするのに十分なくらい速い。 好ましい実施形態において、伸長は２つのプロセスＰ₀およびＰ₁により実行さ れる。（１つのプロセスだけを実行することも代替的に考えられる。）これらの プロセスの出力について互いにＸＯＲをとり、ランダム・ビット・ストリングｚ_t を生成する。 プロセスは以下のように要約される： １．Ｇ₀を用いて、ランダム・ナンバーｘ₁、ｘ₂,...，ｘ_nを生成する。 ２．伸長関数を用いて、すべてのランダム・ナンバーをＲ＝ｒ₁，ｒ₂,...，ｒ_n に伸長する。ここで、各ナンバーｒ_iはナンバーｘ_iよりもあらかじめ決められ た量だけ長い。 ３．Ｒを１回のパッドとして暗号化のために用いることができる。 Ｒについて別のビット・ストリングと排他的論理和をとり、ｚ_tを生成するこ ともできる。ランダム・ビット・ストリングｚ_tは高速かつ安全であり、さらに ＣＳＰＲビット・ジェネレータは、’３０７特許に記載されたデバイスよりも使 用するメモリが少ない。１回のパッドのアプリケーションにおいて、２の当事者 は、例えば６４ビットの秘密のシードを共有することができる。このシードを本 発明のデバイスに適用すると、同じランダム・パッドが生成される。したがって 、第１の当事者は本発明のデバイスをＣＳＰＲビット・ジェネレータとして用い てメッセージを暗号化することができる。本発明のデバイスをやはりＣＳＰＲビ ット・ジェネレータとして用いる第２の当事者は、同じ秘密のシードをデバイス に適用することにより、暗号化されたメッセージを解読することができる。 図１に示すフロントエンド・ジェネレータ１０２は暗号的に強いことが好まし く、遅いが暗号的に安全なジェネレータとすることができる。フロントエンド・ ジェネレータは、例えば’３０７特許に記載されたフロントエンド・ジェネレー タとすることができる。フロントエンド・ジェネレータの出力はランダム・ビッ ト・ストリングｂ_iである。（以下の議論はランダムさの弱いビットに対しても 当てはまることに留意されたい。）フロントエンド・ジェネレータ１０２からの ビット・ストリングｂ_iはセレクタ１０４により受け取られる。セレクタ１０４ は受け取ったビットの行き先を決定する。第１のＬビットのブロックをランダム 関数プロセッサ１０６に送り、第２のＬビットのブロックをグラフ・プロセッサ １０８に送り、ビット・ストリームをグラフ・プロセッサ１０８に送ることが好 ましい。 ランダム関数プロセッサ１０６は、受け取ったビット・ブロック（ランダム・ ナンバーｘ_i）をより長いナンバー（ｒ_i）に「伸長」する。比較的短い時間にお ける繰り返しのランダム・ナンバー（すなわち、２²⁴ストリングに約１つの繰り 返しストリング）を避けるために、伸長されたストリングをグラフ・プロセッサ １０８の出力と結合してもよい。ランダム関数プロセッサ１０６およびグラフ・ プロセッサ１０８の出力は、排他的論理和回路１１０により互いに結合される。 ２つのプロセッサの出力について互いにＸＯＲをとる。結果として生じるビット ・ストリングはｚ_tである。 ＩＩ．ランダム関数プロセッサ 本発明にはシンプルで実用的な伸長メカニズムが含まれる。当該メカニズムは 、’３０７特許に記載されたデバイスとの比較において、約２キロビットのメモ リしか必要としないが、同等の効率性を有する。約２キロビットのメモリは、’ ３０７特許のデバイスが必要とするメモリよりもかなり少ない。’３０７特許の デバイスは約０．２５メガバイトのメモリを使用する。このメカニズムはランダ ム関数プロセッサ１０６により実行される。ランダム関数プロセッサ１０６の動 作を図２に示す。 好ましい実施形態において、ランダム関数プロセッサは以下の方式で動作する ことができる。 １．Ｈ（Ｋ，ｘ）は入力“ｘ”に対してランダム関数のようにふるまう暗号関 数を示し、キー“ｋ”はランダムに選ばれるものとする。(適切な暗号関数には 、ＤＥＳ、３ＤＥＳ、すべての安全なハッシュ関数、またはＭＤ５、ＭＤ４およ び ＳＨＡなどのハッシュ関数の組合せが含まれる。) ２．Ｋ₁，Ｋ₂,...，Ｋ_rを“ｒ”キーとし、各キーは十分大きな長さ（例えば １２８ビット）であるとする。 ３．ｘ_tビットをＨ(Ｋ₁，Ｘ_t)，Ｈ(Ｋ₂，Ｘ_t),...，Ｈ（Ｋ_r，ｘ_t）としてＲ_t ビットにマッピングする。 説明のため、ジェネレータ１００は、フロントエンド・ジェネレータ１０６に よる４８ビット長のランダム・ストリングを受け取るものと仮定する。この４８ ビット・ストリングを２５６ビット・ストリングに伸長することができる。伸長 は、同一のビット・ストリングに対して２つの異なる一方向関数（ＭＤ４および ＭＤ５など）を計算して２つのより長いランダム・ナンバーを生成し、２つのよ り長いランダム・ナンバーを連結(concatenating)(または付加)することにより 行う。例えば、４８ビットのランダム・ナンバーｘ_tを以下のように伸長するこ とができる：ＭＤ５ (Ｘ_t)゜ＭＤ４（ｘ_t）(ここで、゜は連結を表す)。もちろん 、他の一方向関数も本発明に用いるのに適している。 多くの４８ビット・ランダム・ナンバーＸ₁,...，ｘ_nが与えられたとき、各ラ ンダム・ナンバーをこの方法により伸長することができる。その結果、結合され た２５６ビット・ストリングのすべてが形式的なセンスではなおランダムに見え る。ストリングを伸長したときにランダムに見えるこの特性は、これらのハッシ ュ関数を圧縮関数として用いるときにこれらのハッシュ関数に必要とされる衝突 安全特性(collision secure property)とはまったく異なることに留意されたい 。 伸長関数はランダム・ナンバーｘをさらに伸長することもできる。 Ｆ₁，Ｆ₂，Ｆ₃，Ｆ₄を、以下で示す仮定Ａ．５を満たす関数のファミリーから 独立に選んだランダム関数とする。ここで、ｇ：{０，１}ⁿ→｛０，１｝^4Nを以 下のように定義する：ｇ（ｘ）＝Ｆ₁(ｘ)，Ｆ₂(ｘ)，Ｆ₃(ｘ)，Ｆ₄(ｘ)。 この関数は異なるキーを有する安全なハッシュ関数にすぎない:例えば、ｇ(ｘ) ＝ＭＤ５(Ｋ₁，ｘ)°ＭＤ５(Ｋ₂，ｘ)°ＭＤ５(Ｋ₃，ｘ)°ＭＤ５(Ｋ₄，ｘ)。 キーは秘密に保つことが好ましい。ある者はエンベロープ法を用いたいと望むか もしれない。この代替法では、種々の関数に対してコードを保有する必要がなく 、いくつかの最適化により装置のパフォーマンスを向上させることができる。敵 は、 選択の入力においてＭＤ５を評価することができないことに留意されたい。この 差が非常に重要なのは、一方向ハッシュ関数の出力のみが与えられたときに、一 方向ハッシュ関数を攻撃する方法が知られていないからである。事実、ここで、 敵はＭＤ５への入力すら知らない；入力はランダムであり、知られていない。 他の関数も適切な伸長関数となり得ることが考えられる。適切な伸長関数はパ ラメータ（ｎ，Ｎ，ｑ）を有し、以下の特性を有する関数Ｆである。ここで、ｎ はランダム・ナンバーのビット数であり、Ｎは伸長されたランダム・ナンバーの ビット数であり、ｑは法(modulus)である。ｘ_i，ｉ≧１を真にランダムなビット のシーケンス、すなわち０・１の値をつけられたベルヌーイ・シーケンス(zero- one valued Bernoulli sequence)により生成されたシーケンスとする。伸長関数 は以下のように定義できる： １ Ｆ：{０，１}ⁿ→｛０，１｝^N，Ｎ＞ｎ ２ 出力Ｆ(ｘ₁)，Ｆ(ｘ₂),...，Ｆ（ｘ_q）のシーケンスは、同じ長さのラン ダム・ストリングのシーケンスと区別できない。 関数に対する制約はどれくらいシビアであろうか？Ｆは決してランダム関数で はなく、この条件はかなり緩やかである。これを理解するために、安全なハッシ ュ関数についての以下の仮定のシーケンスを考慮されたい。いくつかのものは多 くの研究者により仮定されたものである。 Ａ．１ Ｆは固定関数(fixed function)(例えば、ＳＨＡ、ＭＤ５ Ｆ（ｘ） ＝ＭＤ５(ｘ)) である。敵は質問ｘ１を作成し、値Ｆ（ｘ₁）を取得し、場合に よってはこの値に依存して次の質問ｘ２を生成し、値Ｆ（ｘ₂）を見て、適応し てさらに質問ｘ３を生成するなど。出力Ｆ (ｘ₁)，Ｆ (ｘ₂),...，Ｆ（ｘ_q）は 、同じ長さの真にランダムな入力と区別できない。 Ａ．２ Ｆを関数のファミリーから選ぶ(例えば、秘密キーＫを有するＭＤ５ 。Ｆ（ｘ）＝ＭＤ５ (Ｋ，ｘ))。敵は質問ｘ１を作成し、値Ｆ（ｘ₁）を取得し 、場合によってはこの値に依存して次の質問ｘ２を生成し、値Ｆ（ｘ₂）を見て 、適応してさらに質問ｘ３を生成するなど。出力Ｆ (ｘ₁)，Ｆ (ｘ₂),...，Ｆ（ ｘ_q）は、 同じ長さの真にランダムな入力と区別できない。（選ばれたメッセージ攻撃。） Ａ．３ Ｆを関数のファミリーから選ぶ(例えば、秘密キーＫを有するＭＤ５ 。Ｆ（ｘ）＝ＭＤ５ (Ｋ，ｘ))。敵は一群として質問のシーケンスｘ₁，ｘ₂，ｘ₃ ,...,ｘ_qを生成し、その後これらのすべてのポイントに対する関数の値を同時 に質問する。出力Ｆ (ｘ₁)，Ｆ (ｘ₂),...，Ｆ（ｘ_q）は、同じ長さの真にラン ダムな入力と区別できない。（選ばれたメッセージ攻撃。） Ａ．４ Ｆを関数のファミリーから選ぶ(例えば、秘密キーＫを有するＭＤ５ 。Ｆ（ｘ）＝ＭＤ５ (Ｋ，ｘ))。敵は公平なコイン・フリップ(coin flips)を用 い、ランダムな質問のシーケンスｘ₁，ｘ₂，ｘ₃,...，ｘ_qを生成し、これらのポ イントに対する関数の値を一群として質問する。出力Ｆ (ｘ₁)，Ｆ (ｘ₂),...， Ｆ（ｘ_q）は、同じ長さの真にランダムな入力と区別できない。(知られたランダ ムなメッセージ攻撃。) Ａ．５ Ｆを関数のファミリーから選ぶ。例えば、秘密キーＫを有するＭＤ５ 。Ｆ（ｘ）＝ＭＤ５ (Ｋ，ｘ)。公平なコイン・フリップの秘密のソースは、ラ ンダムな質問のシーケンスｘ₁，ｘ₂，ｘ₃,...，ｘ_qを生成し、敵はこれらのラン ダムな質問を知らない。出力Ｆ(ｘ₁)，Ｆ(ｘ₂),...，Ｆ（ｘ_q）は、同じ長さの 真にランダムな入力と区別できない。（ランダムな知られていないメッセージ攻 撃。） ここで述べた特性は、衝突抵抗特性(collision resistant property)よりもか ない弱い。関数は、実際、（入力よりも）長いシーケンスを出力し、ローカルな 独立の仮定（例えば、二面独立(two-wise independence)）の下でも、関数はほ とんどどこでも一対一であり、したがって、ささいな理由により衝突がない。 特性Ａ．５は標準疑似ランダム関数よりも弱い。標準関数とは異なり、質問は （ａ）ランダムであり、（ｂ）関数値を真にランダムなストリングと区別するア ルゴリズムに知られていない。 さらに、関数自体を疑似ランダム方式で選ぶことができる。この場合、関数自 体がすべての評価に対して変化する。したがって、最も弱い可能な仮定は、弱ラ ンダムな知られていないメッセージ攻撃に対する変化する関数のセキュリティで ある。 ＩＩＩ．グラフ・プロセッサおよび排他的論理和回路 グラフ・プロセッサ１０８および排他的論理和回路の動作は、’３０７特許出 願に詳しく記載されている。これらの記載を参照によりここに取り入れる。 １．グラフ・プロセッサ グラフ・プロセッサの動作を簡単に説明する。ランダム関数プロセッサ１０６ により実行される伸長関数ｇは、繰り返し時間（ビット・ストリングが繰り返し を始める時間）を考慮する場合には、十分に安全ではないかもしれない。ランダ ム・ナンバーｘ_iがランダムに生成されたシーケンスＧ₀(ｘ_i)，ｉ≧１である場 合、伸長されたナンバーは、時間２^2Nよりもむしろ２^n/2において誕生日パラド ックス攻撃の影響を受けやすい。これはｘ_iシーケンスが時間２^n/2で繰り返すか らである。(簡単に言えば、誕生日パラドックスとは、特定の誕生日の１人より も、同じランダムな誕生日の２人の方が統計的に見つけやすいということである 。)２つの同じストリングを有することは、敵が暗号システムを「破る」ことを 助ける。この問題を解決するのに、拡大グラフにおけるランダム・ウォークを用 いることができる。拡大グラフに基づく追加により、ランダム関数プロセッサ上 で効率的に実行できるいかなるタイプの統計的攻撃をも避けることができる。 遅いが完全なまたは安全なフロントエンド・ジェネレータ１０２Ｇ₀がランダ ム・ビット・ストリングを提供するものと仮定する。ｘ←Ｇ₀（.）は、ｘが、長 さ｜ｘ｜のランダム・ストリングを割り当てられたナンバーであることを示し、 その割当ては、Ｇ₀をコールし、適切な長さ（すなわち、上述の長さＬ）のラン ダム・ビットの次のブロックを取得することによる。２^Lノードのｄ−レギュラ 拡大グラフを用いることが好ましい。各ノードは、Ｌビット・ストリングにより ラベル付けされる。グラフがｄ−レギュラなので、グラフをカラー｛１,...，ｄ ｝によりエッジ・カラーする(edge-colored)ことができる。すべてのノードｙ， １≦ｒ≦ｄについて、近隣（ｙ，ｒ）は、カラーｒのエッジを横切ることにより 到達するｙの近隣(neighbor)を示すものとする。 ここで、ランダムな近隣に移動することは、マシンのワードごとのシフトおよ び加算を必要とする。プロセスを、ａ，ｂによりラベル付けされたノードについ て説明する。同じノードに１／２の確率で留まるか、ランダムに（ａ，ｂ＋２ａ ）または（ａ，ｂ−２ａ）または（ａ，ｂ＋２ａ＋１）または（ａ，ｂ−２ａ＋ １）または（ａ＋２ｂ，ｂ）または（ａ＋２ｂ−１，ｂ）または（ａ−２ｂ，ｂ ）または（ａ−２ｂ＋１，ｂ）に移動するかのどちらかである。追加の時間およ びハードウェアは最小量である：ナンバーごとの少しのシフトおよび加算；スロ ーダウンは無視することができる。ここで、すべての追加はモジュラ(modular) であり、モジュラは標準のマシンのハードウェアには通常実装されている。 代替的に、伸長関数ｇの繰り返し時間を考慮しないのであれば、グラフ・プロ セッサをジェネレータから除去してもよい。図３は、そのような疑似ランダム・ ビット・ジェネレータ３００のブロック・ダイアグラムである。疑似ランダム・ ビット・ジェネレータは、フロントエンド・ジェネレータ３０２、セパレータ３ ０４、ランダム関数プロセッサ３０６、および排他的論理和回路（ＸＯＲ）３１ ０を有する。フロントエンド・ジェネレータ３０２は３つの入力を受け取る：第 １のシードｘ₀、第２のシードｈ、およびランダム・キーｍ。疑似ランダム・ジ ェネレータ３００はこれらの入力を用いて、ランダム・ビット・ストリングｚ_t を出力する。 フロントエンド・ジェネレータ３０２はランダム・ビット・ストリングｂ_iを 出力する。フロントエンド・ジェネレータ３０２からのビット・ストリングｂ_i は、セレクタ３０４により受け取られる。セレクタ３０４は受け取ったビットの 行き先を決定する。第１のＬビットのブロックをランダム関数プロセッサ３０６ に送り、第２のＬビットのブロックをＸＯＲ回路３０８に直接送ることが好まし い。ランダム関数プロセッサ３０６の出力、およびセレクタ３０４からの第２の Ｌビットのブロックは、排他的論理和回路３１０により互いに結合される。２つ のビット・ストリングについて互いにＸＯＲをとる。結果として生じるビット・ ストリングはｚ_tである。 ２．排他的論理和回路 排他的論理和回路の動作を簡単に説明する。ランダム・ビット生成プロセスＧ 全体は２つのサブ・プロセスを含む:(ランダム関数プロセッサ１０６により実行 される)Ｐ₀、および（グラフ・プロセッサ１０８により実行される）Ｐ_{1 °}各プ ロセスはＬビット・ナンバーのシーケンスを生成する。ストリングをさらに処理 ットに関する排他的論理和(bitwise exclusive-or)を表す。排他的論理和回路の 出力はｚ_tである。ＸＯＲプロセスは、出力ストリングがプロセスＰ₀およびＰ₁ の望ましい特性を受け継ぐことを可能にする。このランダム・ストリングを、長 いランダム・ビット・ストリングを迅速に必要とするアプリケーションに用いる ことができる。そのようなアプリケーションにはリアルタイム・アプリケーショ ン、例えばビデオ・ストリームおよびＴＣＰ／ＩＰレイヤ暗号化が含まれる。 ＩＶ．本発明を用いた暗号化 図３のＣＳＰＲビット・ジェネレータ（すなわち、グラフ・プロセッサなし） を用いて、以下の方式で暗号化を行うことができる。 １．Ｇ₀（ｓ）＝ｘ’₁，ｘ’₂,...，Ｘ’_mを安全なランダム・ジェネレータと する。ｇ_k（ｘ）を上述の伸長関数とする。この実施形態において、これは、各 インボケーション(invocation)に対して異なるランダム隠れキー(random hidden key)を用いた、ＭＤ５などの一方向関数のいくつかのインボケーションにすぎな い。 ２．ファイルを暗号化するために(この説明ではファイルは長さＬの多くのブ ロックにセグメント化されていると仮定する)、以下のことが実行される。Ｌ＝ ４Ｎと仮定する。以下の二者択一の２つのケースを考慮する。 ａ．ブロックはナンバー付けされていない。このことが好ましいケースがあ る。例えば、各ブロックは短すぎることがある。いかなるケースにおいても、入 力ファイルＦが適切な長さであると仮定して、暗号化を以下のように行う。 暗号化を行うファイルの次のブロックをＦ_iとする。次のｘ_iをＧを用いて ｂ．各ブロックにはシーケンス・ナンバーｉが割り当てられている。ナンバ ーｉをランダム化する関数ｈ（ｉ）＝ｙ_iが与えられているものと仮定する。そ して、上のケースａにおけるｘ_iの代わりにｙ_iが伸長される。 図１のＣＳＰＲビット・ジェネレータ（すなわち、グラフ・プロセッサ１０８ あり）を用いて、以下の方式で暗号化を行うことができる。 Ｈは、上述のランダムさの条件を満たす一方向関数を示す。 Ｈ₁，Ｈ₂，Ｈ₃，Ｈ₄は、異なるランダム・キーによりあらかじめ固定された一 方向関数を示すものとする。ここで： ｆｏｒ ｉ：＝１，２,..．ｄｏ ・ｘ’_i←Ｇ₀（.） Ｐ₀： ｘ_i:＝Ｈ₁（ｘ’_i）・Ｈ₂（ｘ’_i）・Ｈ₃（ｘ’_i）・Ｈ₄（ｘ’_i） Ｐ₁： ｂ←Ｇ₀，ｂ∈｛０，１｝ ｉｆ （ｂ＝０） ｙ_i：＝ｙ_i−１（同じノードに留まる） ｅｌｓｅ ｒ←Ｇ₀，ｒ∈{１,...，ｄ}，ｙ_i＝近隣（ｙ_i-1，ｒ）（ランダ ムな近隣に移動する）Ｖ．本発明の有利な点および実装 本発明は、従来のＣＳＰＲビット・ジェネレータに対して、そして’３０７特 許に記載された疑似ランダム・ビット・ジェネレータに対してもいくつかの有利 な点を有する。 第１に、実用の点から見ると、ＭＤ４、ＭＤ５などの一方向関数はＤＥＳより も約１０倍速い。これらの一方向関数が非常に速いので、フロントエンド・ジェ ネレータは、ＤＥＳ（または他の暗号）に基づくかなり安全な（そして遅いと推 定される）暗号化を用いることができる。これらの一方向関数は形式的センスで はＤＥＳと同じくらい破ることが困難である。 第２に、上述のジェネレータはシーケンシャルである。ある者はそれを、ブロ ック・ナンバーが与えられると、そのブロック・ナンバーに対応するランダム・ ストリングを計算できるというセンスにおける「ランダム・アクセス」にしたい と望むであろう。これは、キーまたはＤＥＳを有する安全なハッシュのシードと してブロック・ナンバーを用いることにより簡単に実現される。実装問題:ブロック暗号および安全なハッシュ関数を用いることが考えられる 。 上述の構造は、以下のことを考慮して作成される。 ハッシュ関数： 最近の攻撃でさえも、これらのハッシュ関数の一方向関数の特性を破らない。 事実、一方向ハッシュ関数のこの側面を攻撃する真剣な努力はなされていないと いってもいいであろう。大規模なランダムさのテストにおいて、Ａ．５で使用す る際の関数のふるまいのランダムさにおけるいかなる顕著な矛盾も見い出されな い。我々はいかなる形においてもそれらの衝突抵抗特性に依存せず、それらの「 一方向性」およびランダムさにのみ依存して入力を伸長する。したがって、圧縮 関数としてよりも、単射関数(injective function)としてほぼ的確にふるまう( すなわち、取るに足らない入力の一部を除くすべてに対して)。これは、理にか なった仮定の下で衝突問題を明らかに回避する。 暗号： ＤＥＳのような暗号のランダムさの特性は非常に強力である。 パフォーマンス問題：暗号のスピードは、処理するビット数に関し、ハッシュ 関数のスピードよりも約１オーダー小さい。 以下のことを用いて初期化の時間をスピードアップすることができる。入力バ ッファを５１２ビットのランダム・ビットで満たすこととする。そして、ＭＤ５ の出力を｛０，１｝¹²⁸に一様に分配する。したがって、ｈ∈｛０，１｝¹²⁸であ る内部変数ｈのいかなる値に対しても、ＭＤ５（ｘ）＝ｈとなる５１２ビット・ ストリングｘが存在する。 ここで説明したＣＳＰＲビット・ジェネレータは’３０７デバイスに匹敵する スピードを有する。ここで与えたアルゴリズムは、従来のデバイスと比べて、相 当少ないメモリしか必要とせず、カーネル・レベルのアプリケーションにより適 している。’３０７特許デバイスおよび本発明の双方とも、数十メガビットの範 囲で解読を行うことができる。これは、いくつかのプラットフォームにおける普 通のＤＥＳ暗号化よりも１オーダー速い。正確なスピードはプラットフォームお よび使用する伸長関数に依存する。 ＶＩ．結論 改良された暗号的に安全な疑似ランダム・ビット・ジェネレータについて説明 した。本ジェネレータは長いビット・ストリングを高速に提供するが、従来のデ バイスよりも使用するメモリは少ない。ビット・ストリングは、リアルタイム暗 号化アプリケーションで用いるのに十分長く、十分速く、そして十分安全である 。オーバーヘッドは、カーネル・レベル・アプリケーションで用いるのに十分な くらい小さい。 上述の本発明の実施形態は説明のみを意図したものである。当該技術に熟達し た者は、以下の請求の範囲の精神および範囲から離れることなく、非常に多くの 代替実施形態を考え出すことができる。

───────────────────────────────────────────────────── フロントページの続き (81)指定国 ＥＰ(ＡＴ，ＢＥ，ＣＨ，ＤＥ， ＤＫ，ＥＳ，ＦＩ，ＦＲ，ＧＢ，ＧＲ，ＩＥ，ＩＴ，Ｌ Ｕ，ＭＣ，ＮＬ，ＰＴ，ＳＥ)，ＣＡ，ＪＰ

Claims (1)

1. 【特許請求の範囲】 １．ランダム・ナンバーをより長いランダム・ナンバーに伸長する方法であって 、 ａ．前記ランダム・ナンバーを受け取るステップと、 ｂ．前記ランダム・ナンバーに対して一方向関数を実行し、前記より長いラン ダム・ナンバーを提供するステップと を備えることを特徴とする方法。 ２．請求項１に記載の方法において、前記より長いランダム・ナンバーを暗号化 のために１回のパッドとして用いるステップをさらに備えることを特徴とする方 法。 ３．請求項１に記載の方法において、前記ランダム・ナンバーを受け取る前記ス テップは、暗号的に安全なランダム・ナンバーを受け取るステップをさらに備え ることを特徴とする方法。 ４．請求項１に記載の方法において、前記一方向関数を実行する前記ステップは 、ランダム関数のようにふるまう暗号関数を実行するステップをさらに備えるこ とを特徴とする方法。 ５．請求項１に記載の方法において、前記一方向関数を実行する前記ステップは 、 ａ．前記ランダム・ナンバーに対して複数の一方向関数を実行し、複数のより 長いランダム・ナンバーを生成するステップと、 ｂ．前記より長いランダム・ナンバーを連結するステップと をさらに備えることを特徴とする方法。 ６．請求項５に記載の方法において、前記複数の一方向関数は、疑似ランダム方 式により選択されることを特徴とする方法。 ７．請求項１に記載の方法において、前記一方向関数を実行する前記ステップは 、 ａ．異なるキーを用いて前記ランダム・ナンバーに対して安全なハッシュ関数 を実行し、複数のより長いランダム・ナンバーを生成するステップと、 ｂ．前記より長いランダム・ナンバーを連結するステップと をさらに備えることを特徴とする方法。 ８．請求項１に記載の方法において、前記ランダム・ナンバーは第１のランダム ・ナンバーであり、前記より長いランダム・ナンバーは第１のより長いランダム ・ナンバーであり、前記方法は、 ａ．第２のランダム・ナンバーを受け取るステップと、 ｂ．前記第２のランダム・ナンバーに対して拡大グラフ関数を実行し、第２の より長いランダム・ナンバーを生成するステップと、 ｃ．前記第１および第２のより長いランダム・ナンバーを結合するステップと をさらに備えることを特徴とする方法。 ９．請求項８に記載の方法において、前記結合するステップは、前記第１および 第２のより長いランダム・ナンバーに対して排他的論理和関数を実行するステッ プを備えることを特徴とする方法。 １０．暗号的に安全なランダム・ナンバーを高速に生成する方法であって、 ａ．安全なランダム・ビット・ストリングを生成するステップと、 ｂ．前記安全なランダム・ビット・ストリングに対して一方向関数を実行し、 より長いランダム・ビット・ストリングを生成するステップと、 ｃ．前記より長いランダム・ビット・ストリングに別のビット・ストリングを 結合するステップと を備えることを特徴とする方法。 １１．請求項１０に記載の方法において、前記一方向関数を実行するステップは 、 ａ．前記安全なランダム・ビット・ストリングに対して複数の一方向関数を実 行し、複数のより長いランダム・ビット・ストリングを生成するステップと、 ｂ．前記より長いランダム・ビット・ストリングを連結するステップと を備えることを特徴とする方法。 １２．請求項１１に記載の方法において、前記複数の一方向関数は、疑似ランダ ム方式により選択されることを特徴とする方法。 １３．請求項１０に記載の方法において、前記一方向関数を実行する前記ステッ プは、 ａ．異なるキーを用いて前記安全なランダム・ビット・ストリングに対して安 全なハッシュ関数を実行し、複数のより長いランダム・ビット・ストリングを生 成するステップと、 ｂ．前記より長いランダム・ビット・ストリングを連結するステップと をさらに備えることを特徴とする方法。 １４．請求項１０に記載の方法において、前記結合するステップは、 ａ．第２の安全なランダム・ビット・ストリングを受け取るステップと、 ｂ．前記第２の安全なランダム・ビット・ストリングに対して拡大グラフ関数 を実行し、第２のより長いランダム・ビット・ストリングを生成するステップと 、 ｃ．前記第１および第２のより長いランダム・ビット・ストリングを結合する ステップと をさらに備えることを特徴とする方法。 １５．請求項１４に記載の方法において、前記結合するステップは、前記第１お よび第２のより長いランダム・ナンバーに対して排他的論理和関数を実行するス テップを備えることを特徴とする方法。 １６．暗号的に安全な疑似ランダム（ＣＳＰＲ）ビット・ジェネレータであって 、 ａ．安全なランダム・ビット・ストリングを出力するように構成されたフロン トエンド・ジェネレータと、 ｂ．ランダム関数プロセッサであって、 （１）前記安全なランダム・ビット・ストリングの一部を少なくとも受け取 り、 （２）前記安全なランダム・ビット・ストリングの前記受け取った部分に対 して一方向関数を実行し、 （３）前記安全なランダム・ビット・ストリングの前記受け取った部分より 長いランダム・ビット・ストリングを出力する ように構成されたランダム関数プロセッサと を備えたことを特徴とするＣＳＰＲビット・ジェネレータ。 １７．請求項１６に記載のＣＳＰＲビット・ジェネレータにおいて、前記ランダ ム関数プロセッサはさらに、 ａ．前記ビット・ストリングの前記受け取った部分に対して複数の一方向関数 を実行し、複数のより長いランダム・ビット・ストリングを生成し、 ｂ．前記より長いランダム・ビット・ストリングを連結する ように構成されたことを特徴とするＣＳＰＲビット・ジェネレータ。 １８．請求項１７に記載のＣＳＰＲビット・ジェネレータにおいて、前記複数の 一方向関数は、疑似ランダム方式により選択されることを特徴とするＣＳＰＲビ ット・ジェネレータ。 １９．請求項１６に記載のＣＳＰＲビット・ジェネレータにおいて、前記ランダ ム関数プロセッサはさらに、 ａ．異なるキーを用いて前記ランダム・ビット・ストリングに対して安全なハ ッシュ関数を実行し、複数のより長いランダム・ビット・ストリングを生成し、 ｂ．前記より長いランダム・ビット・ストリングを連結する ように構成されたことを特徴とするＣＳＰＲビット・ジェネレータ。 ２０．請求項１６に記載のＣＳＰＲビット・ジェネレータにおいて、 ａ．前記フロントエンド・ジェネレータから前記安全なビット・ストリングの 第２の一部を少なくとも受け取り、拡大されたビット・ストリングを出力するよ うに構成され、前記第２の一部は前記ランダム関数プロセッサにより受け取られ る前記部分とは異なるグラフ・プロセッサと、 ｂ．排他的論理和回路であって、 （１）前記より長いランダム・ビット・ストリングおよび前記拡大されたビ ット・ストリングを受け取り、 （２）排他的論理和プロセスを実行することにより前記受け取ったビット・ ストリングを結合する ように構成された排他的論理和回路と をさらに備えたことを特徴とするＣＳＰＲビット・ジェネレータ。