(57)【要約】  乱数（２０２）を生成する方法（３００）は、内側ビットと外側ビットとを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ）（２００）を初期化することを含み、内側ビットは、２，０４８ビットの第１の１２８ビットを含み、外側ビットは、２，０４８ビットの残りのビットを含む。当該方法は、ＡＥＳラウンドキー（１９２）をキーソース（１９２）から検索することと、しきい値回数にわたって、１２８ビットの１６ブランチを有するファイステルネットワークの奇数番号のブランチ（２２０）を、ファイステルネットワークの、対応する偶数番号の隣接ブランチの関数とＸＯＲすることにより、ＡＥＳラウンドキーを用いてラウンド関数を実行することと、１２８ビットの各ブランチを所定の順序にシャッフルすることとも含む。当該方法は、並べ替えられた状態の内側ビットの、以前の状態の内側ビットとのＸＯＲを実行することも含む。
2021501902.tif 000002
【特許請求の範囲】
【請求項１】
乱数（２０２）を生成するための方法（３００）であって、前記方法は、
データ処理ハードウェア（１４２）が、内側ビット（２１０ｉ）と外側ビット（２１０ｏ）とを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ：pseudo-random number generator）（２００）を初期化することを備え、
前記内側ビット（２１０ｉ）は、前記２，０４８ビットの第１の１２８ビットを含み、前記外側ビット（２１０ｏ）は、前記２，０４８ビットの残りのビットを含み、
前記方法は、さらに、前記データ処理ハードウェア（１４２）が、前記ＰＲＮＧ（２００）の前記状態を並べ替えることを備え、
前記並べ替えることは、
キーソース（１９０）から先進暗号化標準（ＡＥＳ：Advanced Encryption Standard）ラウンドキー（１９２）を検索することと、
しきい値回数にわたって、前記ＡＥＳラウンドキー（１９２）を用いてラウンド関数を実行することとによって実行され、
前記ラウンド関数は、１２８ビットの１６ブランチ（２２０）を有するファイステルネットワークの奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の関数とＸＯＲすることを含み、
前記並べ替えることは、さらに、
前記しきい値回数にわたって、１２８ビットの各ブランチ（２２０）を所定の順序にシャッフルすることによって実行され、
前記方法は、さらに、
前記データ処理ハードウェア（１４２）が、前記並べ替えられた状態の前記内側ビット（２１０ｉ）の、以前の状態の前記内側ビット（２１０ｉ）とのＸＯＲを実行することを備える、方法。
【請求項２】
前記ＰＲＮＧ（２００）を初期化することは、
前記ＰＲＮＧ（２００）の前記状態をゼロに設定することと、
前記外側ビット（２１０ｏ）を任意のシード値に設定することとを含む、請求項１に記載の方法（３００）。
【請求項３】
前記ＰＲＮＧ（２００）を初期化することは、前記ＰＲＮＧ（２００）の前記状態を以前の状態に設定することを含む、請求項１に記載の方法（３００）。
【請求項４】
前記しきい値回数は、少なくとも１７回を含む、請求項１〜３のいずれか１項に記載の方法（３００）。
【請求項５】
前記ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む、請求項１〜４のいずれか１項に記載の方法（３００）。
【請求項６】
ＡＥＳの前記少なくとも２ラウンドの各々は、ＡＥＳの他のラウンドの前記ＡＥＳラウンドキー（１９２）とは異なる、対応するＡＥＳラウンドキー（１９２）を用いる、請求項１〜５のいずれか１項に記載の方法（３００）。
【請求項７】
前記ファイステルネットワークの前記奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の前記関数とＸＯＲすることは、ランダムビット（２１０）という結果を生じ、前記外側ビット（２１０ｏ）は、前記結果として生じるランダムビット（２１０）を含む、請求項１〜６のいずれか１項に記載の方法（３００）。
【請求項８】
１２８ビットの各ブランチ（２２０）を前記所定の順序にシャッフルすることは、８回、前記ラウンド関数を実行して各ブランチ（２２０）をシャッフルした後に、全サブブランチ拡散を達成する、請求項１〜７のいずれか１項に記載の方法（３００）。
【請求項９】
前記所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む、請求項１〜８のいずれか１項に記載の方法（３００）。
【請求項１０】
前記内側ビット（２１０ｉ）へのアクセスを防止し、前記外側ビット（２１０ｏ）へのアクセスを許可することをさらに含む、請求項１〜９のいずれか１項に記載の方法（３００）。
【請求項１１】
システム（１００）であって、前記システムは、
データ処理ハードウェア（１４２）と、
前記データ処理ハードウェア（１４２）に通信するメモリハードウェア（１４４）とを備え、前記メモリハードウェア（１４４）は、前記データ処理ハードウェア（１４２）上で実行されると前記データ処理ハードウェア（１４２）に以下の動作を行わせる命令を格納し、前記動作は、
内側ビット（２１０ｉ）と外側ビット（２１０ｏ）とを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ）（２００）を初期化することを含み、
前記内側ビット（２１０ｉ）は、前記２，０４８ビットの第１の１２８ビットを含み、前記外側ビット（２１０ｏ）は、前記２，０４８ビットの残りのビットを含み、
前記動作は、さらに、前記ＰＲＮＧ（２００）の前記状態を並べ替えることを含み、
前記並べ替えることは、
キーソース（１９０）から先進暗号化標準（ＡＥＳ）ラウンドキー（１９２）を検索することと、
しきい値回数にわたって、前記ＡＥＳラウンドキー（１９２）を用いてラウンド関数を実行することとによって実行され、
前記ラウンド関数は、１２８ビットの１６ブランチ（２２０）を有するファイステルネットワークの奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の関数とＸＯＲすることを含み、
前記並べ替えることは、さらに、
前記しきい値回数にわたって、１２８ビットの各ブランチ（２２０）を所定の順序にシャッフルすることによって実行され、
前記動作は、さらに、
前記並べ替えられた状態の前記内側ビット（２１０ｉ）の、以前の状態の前記内側ビット（２１０ｉ）とのＸＯＲを実行することを含む、システム。
【請求項１２】
前記ＰＲＮＧ（２００）を初期化することは、
前記ＰＲＮＧ（２００）の前記状態をゼロに設定することと、
前記外側ビット（２１０ｏ）を任意のシード値に設定することとを含む、請求項１１に記載のシステム（１００）。
【請求項１３】
前記ＰＲＮＧ（２００）を初期化することは、前記ＰＲＮＧ（２００）の前記状態を以前の状態に設定することを含む、請求項１１に記載のシステム（１００）。
【請求項１４】
前記しきい値回数は、少なくとも１７回を含む、請求項１１〜１３のいずれか一項に記載のシステム（１００）。
【請求項１５】
前記ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む、請求項１１〜１４のいずれか一項に記載のシステム（１００）。
【請求項１６】
ＡＥＳの前記少なくとも２ラウンドの各々は、ＡＥＳの他のラウンドの前記ＡＥＳラウンドキー（１９２）とは異なる、対応するＡＥＳラウンドキー（１９２）を用いる、請求項１１〜１５のいずれか１項に記載のシステム（１００）。
【請求項１７】
前記ファイステルネットワークの前記奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の前記関数とＸＯＲすることは、ランダムビット（２０２）という結果を生じ、前記外側ビット（２１０ｏ）は、前記結果として生じるランダムビット（２０２）を含む、請求項１１〜１６のいずれか１項に記載のシステム（１００）。
【請求項１８】
１２８ビットの各ブランチ（２２０）を前記所定の順序にシャッフルすることは、８回、前記ラウンド関数を実行して各ブランチ（２２０）をシャッフルした後に、全サブブランチ拡散を達成する、請求項１１〜１７のいずれか１項に記載のシステム（１００）。
【請求項１９】
前記所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む、請求項１１〜１８のいずれか１項に記載のシステム（１００）。
【請求項２０】
前記動作は、前記内側ビット（２１０ｉ）へのアクセスを防止し、前記外側ビット（２１０ｏ）へのアクセスを許可することをさらに含む、請求項１１〜１９のいずれか１項に記載のシステム（１００）。
【発明の詳細な説明】
【技術分野】
【０００１】
技術分野
本開示は、乱数を生成することに関する。
【背景技術】
【０００２】
背景
ランダムアルゴリズムは、クライアントに属するデータを安全に保つために、大きなデータストリームからソート、シャッフル、および／またはサンプリングを行うときに、擬似乱数生成器（ＰＲＮＧ：pseudorandom number generator）に一般的に依存する。ＰＲＮＧは、決定論的アルゴリズムを用いて、シードと呼ばれるランダム入力から非常に高速に擬似乱数を生成する。ＰＲＮＧに依存するアルゴリズムは、敵がＰＲＮＧの動きを予測できるとき、その性能の保証を失い得る。強力なＰＲＮＧは、敵からの攻撃耐性を提供する一方で、一般に回避策に時間がかかる。一方、速いＰＲＮＧは、一般に簡単に予測可能であり、当該ＰＲＮＧは、攻撃者／敵による予期しない相関または搾取に対して脆弱になる。したがって、開発者は、ランダム化されたアプリケーションに対してＰＲＮＧを選択するときに、適切なセキュリティ／速度のトレードオフを決定することが必要になる。しばしば、開発者は、ランダム化されたアプリケーションが敵に対して脆弱であり得ることに気づいておらず、それゆえ、セキュリティに対して速度を犠牲にすることに消極的である。セキュリティ／速度のトレードオフを確認するために数万回のランダム生成器の使用を監査するタスクは、それが費用がかかるのと同じくらい困難である。
【発明の概要】
【課題を解決するための手段】
【０００３】
概要
本開示の一態様は、擬似乱数を生成するための方法を提供する。当該方法は、データ処理ハードウェアが、内側ビットと外側ビットとを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ）を初期化することを含む。内側ビットは、２，０４８ビットの第１の１２８ビットを含み、外側ビットは、２，０４８ビットの残りのビットを含む。当該方法は、データ処理ハードウェアが、先進暗号化標準（ＡＥＳ：Advanced Encryption Standard）ラウンドキーをキーソースから検索することによるＰＲＮＧの状態を並び替えることも含む。当該方法は、ＡＥＳラウンドキーを用いてラウンド関数（Round Function）を実行することにより、ＰＲＮＧの状態をしきい値回数にわたって並び替えることをさらに含む。ラウンド関数は、１２８ビットの１６ブランチを有するファイステルネットワークの奇数番号のブランチを、ファイステルネットワークの、対応する偶数番号の隣接ブランチの関数とＸＯＲすることを含む。しきい値回数にわたって、当該方法は、１２８ビットの各ブランチを所定の順序にシャッフルすることによりＰＲＮＧの状態を並び替えることも含む。当該方法は、データ処理ハードウェアが、並べ替えられた状態の内側ビットの、以前の状態の内側ビットとのＸＯＲを実行することも含む。
【０００４】
いくつかまたは全ての状態、特にいくつかまたは全ての外側ビットは、要求されるさらに他の使用もしくは操作のために、擬似乱数として、または擬似乱数を提供するためにそのときに用いられ得る。
【０００５】
ファイステルネットワークは、一般化されたファイステルネットワーク、言い換えれば、より具体的には一般化された２型のファイステルネットワークであり得る。
【０００６】
本開示の実施形態は、１つ以上の以下の任意の特徴を含み得る。いくつかの実施形態において、ＰＲＮＧを初期化することは、ＰＲＮＧの状態をゼロに設定することと、外側ビットを任意のシード値に設定することとを含む。任意に、ＰＲＮＧを初期化することは、ＰＲＮＧの状態を以前の状態に設定することも含み得る。しきい値の回数は、少なくとも１７回を含み得る。いくつかの例において、ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む。これらの例において、ＡＥＳの当該少なくとも２つのラウンドの各々は、ＡＥＳの他のラウンドのＡＥＳラウンドキーとは異なる、対応するＡＥＳラウンドキーを用い得る。
【０００７】
いくつかの例において、ファイステルネットワークの奇数番号のブランチを、ファイステルネットワークの、対応する偶数番号の隣接ブランチの関数とＸＯＲすることは、ランダムビットという結果を生ずる。これらの例において、外側ビットは、結果として生じるランダムビットを含む。１２８ビットの各ブランチを所定の順序にシャッフルすることは、８回、ラウンド関数を実行して各ブランチをシャッフルした後、全サブブランチ拡散を実現し得る。いくつかの実施形態において、所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む。任意に、当該方法は、内側ビットへのアクセスを防止し、外側ビットへのアクセスを許可することを含み得る。
【０００８】
本開示は、好適なコンピュータ機器上で実施されたときに、説明される方法を実行するように構成されているコンピュータプログラムコードを備える、１つ以上のコンピュータ読み取り可能な媒体も提供する。
【０００９】
本開示は、説明される方法を実施するために構成されている機器も提供する。例えば、本開示の別の態様は、乱数を生成するためのシステムを提供する。当該システムは、データ処理ハードウェアと、当該データ処理ハードウェアに通信するメモリハードウェアとを含む。メモリハードウェアは、データ処理ハードウェア上で実行されると当該データ処理ハードウェアに動作を行わせる命令を格納する。当該動作は、内側ビットと外側ビットとを含む、２，０４８ビットの状態を有する疑似乱数生成器（ＰＲＮＧ）を初期化することを含む。内側ビットは、２，０４８ビットの第１の１２８ビットを含み、外側ビットは、２，０４８ビットの残りのビットを含む。当該動作は、先進暗号化標準（ＡＥＳ）ラウンドキーをキーソースから検索することにより、ＰＲＮＧの状態を並べ替えることも含む。ＰＲＮＧの状態を並び替えることは、しきい値回数にわたって、ＡＥＳラウンドキーを用いてラウンド関数を実行することも含む。ラウンド関数は、１２８ビットの１６ブランチを有するファイステルネットワークの奇数番号のブランチを、ファイステルネットワークの、対応する偶数番号の隣接ブランチの関数とＸＯＲすることを含む。ＰＲＮＧの状態を並び替えることは、しきい値回数にわたって、１２８ビットの各ブランチを所定の順序にシャッフルすることをさらに含む。当該動作は、並べ替えられた状態の内側ビットの、以前の状態の内側ビットとのＸＯＲを実行することも含む。
【００１０】
本開示の実施形態は、１つ以上の以下の任意の特徴を含み得る。システムのいくつかの構成において、ＰＲＮＧを初期化することは、ＰＲＮＧの状態をゼロに設定することと、外側ビットを任意のシード値に設定することとを含む。しきい値回数は、少なくとも１７回を含み得る。いくつかの例において、ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む。これらの例において、ＡＥＳの当該少なくとも２つのラウンドの各々は、ＡＥＳの他のラウンドのＡＥＳラウンドキーとは異なる、対応するＡＥＳラウンドキーを用い得る。
【００１１】
いくつかの実施形態において、ファイステルネットワークの奇数番号のブランチを、ファイステルネットワークの、対応する偶数番号の隣接ブランチの当該関数とＸＯＲすることは、ランダムビットという結果を生ずる。１２８ビットの各ブランチを所定の順序にシャッフルすることは、８回、ラウンド関数を実行して各ブランチをシャッフルした後、全サブブランチ拡散を達成し得る。いくつかの実施形態において、所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む。任意に、当該方法は、内側ビットへのアクセスを防止し、外側ビットへのアクセスを許可することを含み得る。
【００１２】
本開示の１つ以上の実施形態の詳細は、添付の図面および以下の説明に記載されている。他の態様、特徴および利点は、説明および図面、ならびに請求の範囲から明らかになるであろう。
【図面の簡単な説明】
【００１３】
図面の説明
【図１】乱数を生成するための例示的なシステムの概略図である。
【図２Ａ】１２８ビットの１６ブランチを有する一般化されたファイステルネットワークを実現する例示的な擬似乱数発生器（ＰＲＮＧ）の概略図である。
【図２Ｂ】１２８ビットの１６ブランチを有する一般化されたファイステルネットワークを実現する例示的な擬似乱数発生器（ＰＲＮＧ）の概略図である。
【図２Ｃ】並べ替えられた状態の内側ビットと以前の状態の内側ビットとの間でＸＯＲを実行する、図２Ａおよび図２ＢのＰＲＮＧの概略図である。
【図３】乱数を生成するための例示的な方法のフローチャートである。
【図４】例示的なコンピューティング装置の概略図である。
【発明を実施するための形態】
【００１４】
様々な図面における同様の参照記号は、同様の要素を示す。
詳細な説明
本明細書における実施形態は、より高い基準レベルのセキュリティを提供しながら、既存の汎用乱数生成器と互角の実行時間コストを達成する擬似乱数生成器（ＰＲＮＧ）に向けられる。例えば、「より高い基準レベルのセキュリティ」は、経験的ランダム性、予測不能性、およびバックトラッキング耐性の特性により特徴付けられるＰＲＮＧを指す。既存の汎用乱数生成器は、経験的ランダム性、予測不能性、およびバックトラッキング耐性のこれらの特性の１つまたは２つを示し得るが、速度を大幅に犠牲にすること（例えば、実行時間コストを増加すること）なく３つ全てを示すものは知られていない。
【００１５】
本明細書において用いられるように、「経験的ランダム性」は、シミュレーションに影響し得る相関などの欠陥の低減された可能性を示すＰＲＮＧを指し、「予測不能性」は、２６４以上のランダム出力を生成および格納できる比較的強力な敵がＰＲＮＧの現在の状態を知らない限り、当該敵が将来の出力を予測することをＰＲＮＧが防ぐことができることを指す。したがって、敵が現在の状態にアクセスするか、または少なくとも２６４クエリを発行できない限り、当該敵は、ＰＲＮＧによる将来の出力を正しく予測する無視できるほどの可能性を有しているにすぎない。少なくとも２６４クエリの攻撃を発行するために１１０，０００ＵＳＤを超える費用が敵にかかり得るため、潜在的な攻撃者がランダムな出力を予測しようとすることを試みることをやめさせるための控えめな推定値として、２６４の下限が選択される。ＰＲＮＧの「予測不能性」は、ランダムアルゴリズムにおいて敵が最悪のケースをトリガーすることを難しくすることにより、またはランダム化されたオンラインのサンプリングアルゴリズムにより描かれたサンプルに影響を及ぼすことにより、非暗号化アプリケーションに対してＰＲＮＧを役立つようにもする。最後に、「バックトラッキング耐性」は、ＰＲＮＧの現在の状態が損なわれる場合であっても、過去の出力の再構築をＰＲＮＧが防ぐことを指す。シミュレーションアプリケーションに対して「バックトラッキング耐性」の特性は必要ではないかもしれないが、この特性は、入力サンプルがスニッフィング／サンプリングされた過去の動きの出力を敵が発見することを防ぐであろう。
【００１６】
いくつかの実施形態において、ＰＲＮＧは、１２８ビットの１６ブランチを有する一般化された２型のファイステルネットワークを採用して、先進暗号化標準ラウンドキーを用いてラウンド関数を実行することと、ラウンド関数を実行した後に１２８ビットの各ブランチを所定の順序にシャッフルすることとによりＰＲＮＧの状態を入れ替える。並び替えは、シャッフルが全ビット拡散を首尾よく達成するために、ラウンド関数の実行と後続のシャッフルとをしきい値回数にわたって繰り返し得る。本明細書において用いられるように、「しきい値回数」という用語は、各並べ替えラウンドが、ＡＥＳキーを用いる対応するラウンド関数と後続のシャッフリングとを実行する、しきい値回数の並べ替えラウンドを指し得る。いくつかの例において、シャッフリングが１６ラウンド後に２つのサブブロック拡散を達成するため、しきい値回数は、全ビット拡散に対して少なくとも１７回を含む。さらに、ラウンド関数を実行することは、全ビット拡散を達成するためにＡＥＳの少なくとも２ラウンドを実行することを含む。一般に、ＡＥＳの単一のラウンドは、アクティブな置換ボックスの比率の観点から、２回のＡＥＳラウンドよりも効率が低い。
【００１７】
図１を参照して、いくつかの実施形態において、システム１００は、ユーザー１０に関連付けられた１つ以上のクライアント装置１１０，１１０ａ〜ｎを含む。ユーザー１０は、ネットワーク１３０を介して、リモートシステム１４０に通信し得る。リモートシステム１４０は、スケーラブルな／融通性のあるリソース１４２を有する分散システム（例えば、クラウド環境）であり得る。リソース１４２は、コンピューティングリソース１４４（例えば、データ処理ハードウェア）および／またはストレージリソース１４６（例えば、メモリハードウェア）を含む。いくつかの実施形態において、リモートシステム１４０は、先進暗号化標準（ＡＥＳ）ラウンドキー１９２を含むキーソース１９０と、キーソース１９０に通信し、ラウンド関数を実行することによりランダムビット２０２を生成するように構成されている擬似乱数生成器（ＰＲＮＧ）２００とを実行する。ラウンド関数は、キーソース１９０から検索されたＡＥＳラウンドキー１９２を用いる。本明細書において用いられるように、ランダムビット２０２および乱数（複数可）という用語は、交換可能に用いられ得る。ラウンド関数は、ＡＥＳの２ラウンドを含んでもよく、ＡＥＳの各ラウンドが、ＡＥＳの他のラウンドのＡＥＳラウンドキー１９２とは異なる、対応するＡＥＳラウンドキー１９２を用いる。ラウンド関数は、ＡＥＳの２ラウンドよりも多いラウンドも含んでもよく、ＡＥＳの各ラウンドは、異なる対応するＡＥＳラウンドキー１９２を用い得る。ＡＥＳラウンドキー１９２は、対応するラウンドのＡＥＳが、全て等しい列を伴う平文の対称性を破ることを確実にするために、密であって互いに独立していてもよく、それにより敵からの攻撃を回避する。
【００１８】
いくつかの例において、リモートシステム１４０は、ＰＲＮＧ２００へのアクセスを管理するためのＰＲＮＧマネージャ１５０を実行する。クライアント装置１１０は、ネットワーク１３０を介してＰＲＮＧマネージャ１５０に通信できる任意のコンピューティング装置であり得る。クライアント装置１１０は、ラップトップ、タブレット、スマートフォン、およびウェアラブルコンピューティング装置（例えば、ヘッドセットおよび／または時計）などの、デスクトップコンピューティング装置とモバイルコンピューティング装置とを含むが、これらに限定されない。クライアント装置１１０は、リモートシステム１４０上で実行されているソフトウェアアプリケーション１７０を配備、および／または当該ソフトウェアアプリケーション１７０にアクセスするリモートシステム１４０のユーザー１０に対応し得る。例えば、リモートシステム１４０は、メモリハードウェア内に１つ以上のコンテナ１８０，１８０ａ−ｎを有するコンテナ環境を実行し、１つ以上のコンテナ１８０のコンテンツは、リモートシステム１４０上で実行されているソフトウェアアプリケーション１７０と集合的に関連付けられ得る。クライアント装置１１０は、追加的または代替的に、ソフトウェアアプリケーション１７０を実行し得る。
【００１９】
いくつかの実施形態において、ＰＲＮＧ２００は、クライアント装置１１０から乱数リクエスト１２０を受信することに応答して乱数２０２を生成し、ＰＲＮＧマネージャ１５０は、クライアント装置１１０に乱数２０２を送り返す。追加的または代替的に、リモートシステム１４０で実行されているソフトウェアアプリケーション１７０は、乱数リクエスト１２０を提供し、ＰＲＮＧ２００により生成された乱数２０２をＰＲＮＧマネージャ１５０から直接受信し得る。本開示は、リクエスト１２０を提供する、いかなる１つの特定のソースにも限定されない。実際、ＰＲＮＧ２００は、リクエスト１２０を受信することとは無関係にランダムビット２０２を生成するように構成され得る。いくつかのシナリオにおいて、ソフトウェアアプリケーション１７０は、入力シード値として乱数２０２を用いる。他のシナリオにおいては、ソフトウェアアプリケーション１６４は、宝くじ番号（または宝くじ番号の順序）としてＰＲＮＧ２００により出力された乱数２０２を用いる、電子宝くじなどのゲームアプリケーションに対応する。ＰＲＮＧ２００は、乱数を必要とする任意のタスク／アルゴリズムによる使用のための乱数／ランダムビット２０２を生成し得る。
【００２０】
図１および図２Ａ〜２Ｃを参照して、いくつかの実施形態において、ＰＲＮＧ２００は、内側ビット２１０ｉと外側ビット２１０ｏとを含む２，０４８ビット２１０の状態を有する。内側ビット２１０ｉは、第１の１２８ビットを含み、外側ビット２１０ｏは、２，０４８ビットの残りのビットを含む。内側ビット２１０ｉは、スポンジの「容量」に関連する、アクセス不能な「内側」部分に対応する。暗号法において、スポンジ関数またはスポンジ構造は、任意の長さの入力ビットストリームを取得して任意の所望の長さの出力ビットストリームを生み出す有限内部状態を備えるアルゴリズムのクラスである。データ処理ハードウェア１４２は、（ｉ）ＰＲＮＧ２００を初期化し、それから、ファイステルネットワークを実装して、乱数２０２を生成するためのＰＲＮＧ２００の状態を入れ替える。ＰＲＮＧ２００は、乱数２０２の再現可能な順序を生成するように構成されているため、外部エントロピーソースから状態をシードすることは望ましくない。いくつかのシナリオにおいて、ＰＲＮＧ２００を初期化することは、ＰＲＮＧ２００の状態をゼロに設定することと、外側ビット２１０ｏの少なくとも一部を任意のユーザー指定のシード値に任意に設定することとを含む。他のシナリオにおいて、ＰＲＮＧ２００を初期化することは、ＰＲＮＧ２００の状態を以前の状態に設定することを含む。ＰＲＮＧ２００を初期化するこのシナリオは、状態をゼロに設定して外側ビット２１０ｏを任意のユーザー指定のシード値に設定することの初期化を通じてＰＲＮＧ２００が最初に構築された後に、用いられ得る。
【００２１】
ＰＲＮＧ２００を初期化した後、データ処理ハードウェア１４２は、キーソース１９０からＡＥＳラウンドキー１９２を検索することにより、並べ替えを開始する。ファイステルネットワークは、各ブランチが１２８ビットを有する１６のブランチ２２０を含む。ファイステルネットワークは、より小さなブロック／ブランチ（例えば、１６〜３２ビットブロックなど）からの相当な並べ替えを構築するために従来指定されている２型の一般化されたファイステルネットワークを含む。２型の一般化されたファイステルネットワーク構成は、疑似乱数関数の十分な数の並べ替えラウンドの後に強力な疑似ランダムな並べ替えを生み出すという意味において「堅実」である。けれども、８つよりも多いブランチ／ブロックを備えるファイステルネットワークを用いるいくつかの既存の数生成器とは異なり、本明細書において開示されているファイステルネットワークは、複数の独立した入力に依存しない。図２Ａに示される例において、ＰＲＮＧ２００が初期化されるとき（ｉ）、第１のブランチＳｏ２２０は、内側ビット２１０ｉ（例えば、１２８ビット）を含み、第２から第１６のブランチＳ１〜Ｓ１５２２０は、外側ビット２１０о（例えば、各ブランチＳ１−Ｓ１５における１２８外側ビット）を含む。並べ替えは、（１）ラウンド関数を実行することと；（２）ラウンド関数を実行した後に１２８ビットの各ブランチ２２０を所定の順序にシャッフルすることとの２つのステップを含む。
【００２２】
並べ替えの第１のステップの間、データ処理ハードウェア１４２は、ＡＥＳラウンドキー１９２を用いてラウンド関数を実行する。ラウンド関数は、データ処理ハードウェア１４２上でハードウェアアクセラレートされるＡＥＳブロック暗号を含んでもよく、既存の乱数生成器による並び替えを上回りながら、ラウンド関数が、最適化されたソフトウェア実装よりも５倍から１０倍速くなるようにＡＥＳＮＩ命令を用い得る。ＰＲＮＧ２００により採用されるラウンド関数は、ファイステルネットワークの奇数番号のブランチ２２０を、ファイステルネットワークの、対応する偶数番号の隣接ブランチ２２０の関数２３０とＸＯＲするためのＸＯＲ２４０を用いる。示される例において、ラウンド関数は、奇数番号のブランチＳ１２２０を、対応する偶数番号の隣接ブランチＳ０２２０の関数２３０とＸＯＲして、対応するランダム外側ビット２１０ＯＲを出力する。同様に、ラウンド関数が最後の奇数番号のブランチＳ１５２２０を対応する偶数番号の隣接ブランチＳ１４２２０とＸＯＲして対応するランダム外側ビット２１０ＯＲを出力するまで、ラウンド関数は、奇数番号のブランチＳ３２２０を対応する偶数番号の隣接ブランチＳ２２２０とＸＯＲして対応するランダム外側ビット２１０ＯＲなどを出力する。したがって、１つのラウンド関数が２つの隣接する偶奇ブランチ２２０を含むため、並べ替えは、８つのラウンド関数を並列に実行する。対照的に、従来の並べ替え技術は、一度に１つのラウンド関数を実行するか、せいぜい４から６つのラウンド関数を並列に実行するにすぎない。しかしながら、ハードウェアアクセラレーションプロセッサの近年の進歩により、ＰＲＮＧ２００は、ＡＥＳの少なくとも２ラウンドを含む各ラウンド関数とともに、８つのラウンド関数を並列に実行できる。
【００２３】
ＰＲＮＧ２００に２，０４８ビットの状態を提供することは、ラウンド関数の並列計算を可能にし、それゆえ、ＡＥＳＥＮＣ命令に関連する長いレイテンシを隠す。対照的に、より遅いコンピューティング性能により制限される既存の数生成器は、２５６ビットの状態を通常有し、それにより、ブランチを並び替えるために必要とされる合計４つのラウンド関数に対して、各々３２ビットの８つのブランチを有するファイステルネットワークを必要とするにすぎない。
【００２４】
いくつかの例において、ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含み、ＡＥＳの各ラウンドが、ＡＥＳの他のラウンドのＡＥＳラウンドキー１９２とは異なる、対応するＡＥＳラウンドキー１９２を用いる。例えば、ＡＥＳの２つのラウンドを含むラウンド関数は、次のように表現され得る。
【００２５】
【数１】
2021501902.tif 000003
【００２６】
並べ替えの第２ステップの間に、シャッフラー２５０は、１２８ビットの各ブランチ２２０を所定の順序にシャッフルする。例えば、シャッフラーは、偶数番号のブランチＳ０，Ｓ２，...，Ｓ１４２２０の各々からビット２１０と、ファイステルネットワークの各奇数番号のブランチ２２０を、ファイステルネットワークの、対応する偶数番号の隣接ブランチ２２０の関数２３０とＸＯＲするラウンド関数により生成されたランダム外側ビット２１０ＯＲとを受信する。いくつかの例において、シャッフラー２５０の所定の順序は、ファイステルネットワークが、８回の並べ替えラウンド（例えば、ラウンド関数の実行と後続のシャッフリングとが８回行われた）後に全サブブランチ拡散に達するように選択される。ここで、「全サブブランチ拡散」という用語は、１つおきの入力ブランチ２２０に依存するファイステルネットワークの各ブランチ２２０を指す。対照的に、巡回シフトを用いる従来のシャッフリング技術は、全サブブランチ拡散を達成するために１６ブランチ上で１６回の並べ替えラウンドを必要とするであろうため、速度がより遅い。ある実施形態において、シャッフラー２５０の所定の順序は、１６ブランチを並び替えることに対して最善の攻撃耐性を提供すると知られている順序である｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む。例えば、ブランチ２２０を所定の順序にシャッフルするための並べ替えステップは、次のように表され得る。
【００２７】
【数２】
2021501902.tif 000004
【００２８】
図２Ａにおいて示されるように、シャッフラー２５０は、シャッフルされたブランチＳ'１，Ｓ，'２，Ｓ'３，Ｓ'４，..., Ｓ'１４，Ｓ'１５２２０'を第１の並べ替えラウンドの間に所定の順序で出力する。上述されたように、並び替えは、シャッフルが全ビット拡散を首尾よく達成するように、ラウンド関数の実行と後続のシャッフリングとを、並び替えラウンドのしきい値（ｎ）回（例えば、しきい値回数）にわたって繰り返し得る。したがって、第１の並べ替えラウンドの後に発生する各並べ替えラウンドは、直前の並べ替えラウンドの間にシャッフラー２５０により出力されシャッフルされるブランチ２２０を用いる。例えば、図２Ｂは、第１の並べ替えラウンドから出力されシャッフルされるブランチＳ'１，Ｓ'２，...，Ｓ'１４，Ｓ'１５２２０'を、図２Ａを参照して上述されたように、ラウンド関数の実行と後続のシャッフリングとに対して対応する入力として用いる第２の並べ替えラウンドを示す。ここで、シャッフラー２５０は、シャッフルされたブランチＳ”１，Ｓ”２，...Ｓ”１４，Ｓ”１５２２０”を第２の並べ替えラウンドの間に所定の順序で出力する。それにより、第３の並べ替えラウンドは、これらのシャッフルされたブランチを、ラウンド関数の実行と後続のシャッフルとに対する入力として用い、シャッフルされたブランチＳ’”１，Ｓ’”２，...Ｓ’”１４，Ｓ’”１５２２０’”を所定の順序で出力する。図２Ｂは、並べ替えラウンドのしきい値数（ｎ）に達するまで、ラウンド関数の実行と後続のシャッフルとを繰り返して並べ替えることを示し、それによりシャッフラー２５０は、シャッフルされたブランチＳｎ１，Ｓｎ２，... ，Ｓｎ１，Ｓｎ１５２２０ｎを所定の順序で出力する。ここで、ブランチＳｎ１，Ｓｎ２，... ，Ｓｎ１，Ｓｎ１５２２０ｎは、並べ替え状態の２，０４８ビットを含む。いくつかの実施形態において、１２８ビットの各ブランチを｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝の所定の順序にシャッフルすることが、１６の並べ替えラウンド後に２つのサブブロック拡散を実現するため、並べ替えラウンドのしきい値（ｎ）は、全ビット拡散を達成するための少なくとも１７の並べ替えラウンド（例えば、ｎ＝１７）を含む。
【００２９】
上述されたように、データ処理ハードウェア１４２は、並べ替えの時にキーソース１９０からＡＥＳラウンドキー１９２を検索し得る。キーソース１９０は、暗号的に安全であり、ＰＲＮＧ２００を初期化する時に任意の技術を用いてＡＥＳラウンドキー１９２を生成し得る。ＰＲＮＧ２００を初期化し、１７の並べ替えラウンドに対してＰＲＮＧ２００の状態を並べ替えすることは、以下のように表され得る。
【００３０】
【数３】
2021501902.tif 000005
【００３１】
引き続き図２Ｂを参照して、第１のブランチＳｎ１２２０ｎは、並べ替え状態の２，０４８ビットの第１の１２８ビットに対応する、並べ替えられた内側ビット２１０ｉｐを含み、第２から第１６のブランチＳn２〜Ｓｎ１５の各々は、並べ替え状態の２，０４８ビットの残りのビットに対応する、並べ替えられたランダム外側ビット２１０ＯＲを含む。ここで、ランダム外側ビット２１０ＯＲは、リモートシステム１４０上でおよび／またはクライアント装置１１０上で実行されているソフトウェアアプリケーション１７０による使用のためにＰＲＮＧ２００によって生成および出力される、乱数（複数可）／ランダムビット２０２に対応する。
【００３２】
図２Ｃを参照して、いくつかの実施形態において、ＰＲＮＧ２００は、（例えば、データ処理ハードウェア１４２を介して）並べ替え状態（例えば、状態［１］）の並べ替えられた内側ビット２１０ｉｐの、前の状態（例えば、状態［０］）の内側ビット２１０ｉとのＸＯＲを実行して、ＸＯＲされた内側ビット２１０ｉｘを生成する。図示される例において、以前の状態の内側ビット２１０ｉは、ＰＲＮＧ２００が初期化されたとき（図２Ａ）、第１のブランチＳ０２２０の第１の１２８ビットを含む。ここで、ＸＯＲされた内側ビット２１０ｉｘは、ＰＲＮＧ２００の現在の状態（例えば、並べ替えられた状態［１］）が損なわれた場合でも、過去の出力の再構築を防ぐために、ＰＲＮＧ２００に前述の「バックトラッキング耐性」を提供する。したがって、攻撃者は、並べ替えに対する２１２７未満の順方向または逆方向のクエリを伴うランダムと以前の出力を（例えば、ＸＯＲされた内側ビット２１０ｉｘを推測することにより）区別することを期待できない。したがって、ＰＲＮＧ２００は、乱数（複数可）／ランダムビット２０２に対応するランダム外側ビット２１０ＯＲへのアクセスを許可し、内側ビット２１０ｉ，２１０ｉｘへのアクセスを防止する。並べ替えられた状態の内側ビットの、以前の状態の内側ビットとのＸＯＲを実行することは、次のように表され得る。
【００３３】
【数４】
2021501902.tif 000006
【００３４】
図３は、乱数を生成するための例示的な方法３００のフローチャートである。フローチャートは、データ処理ハードウェア１４２が、内側ビット２１０ｉ，２１０と外側ビット２１０ｏ，２１０とを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ）を初期化するとき、動作３０２において開始する。内側ビット２１０ｉは、２，０４８ビットの第１の１２８ビットを含み、外側ビット２１０ｏは、２，０４８ビットの残りのビットを含む。ＰＲＮＧ２００の状態を初期化することは、ＰＲＮＧ２００の状態をゼロに設定することと、外側ビット２１０ｏを任意のシード値に設定することとを含み得る。任意のシード値は、ユーザー指定であり得る。他の例において、ＰＲＮＧ２００の状態を初期化することは、ＰＲＮＧ２００の状態を以前の状態に設定することを含む。
【００３５】
動作３０４において、データ処理ハードウェア１４２は、キーソース１９０から先進暗号化標準（ＡＥＳ）ラウンドキー１９２をまず検索することにより、ＰＲＮＧ２００の状態を並び替える。データ処理ハードウェア１４２は、少なくとも２つの異なるＡＥＳラウンドキー１９２を検索でき、キーソース１９０は、暗号的に安全であり得る。しきい値回数にわたって、データ処理１４２は、ＡＥＳラウンドキー１９２を用いてラウンド関数を実行することと、ブランチ２２０をシャッフルすることとにより、ＰＲＮＧ２００の状態をさらに並び替える。具体的には、動作３０６において、ＡＥＳラウンドキー１９２を用いてラウンド関数を実行することは、１２８ビットの１６ブランチを有するファイステルネットワークの奇数番号のブランチ２２０を、ファイステルネットワークの、対応する偶数番号の隣接ブランチ２２０の関数とＸＯＲすることを含む。いくつかの例において、ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む。ＡＥＳの少なくとも２つのラウンドの各々は、ＡＥＳの他のラウンドのＡＥＳラウンドキー１９２とは異なる、対応するＡＥＳラウンドキー１９２を含み得る。動作３０８において、ブランチ２２０をシャッフルすることは、１２８ビットの各ブランチ２２０を所定の順序にシャッフルすることを含む。８回、ラウンド関数を実行して各ブランチ２２０をシャッフルした後に全サブブランチ拡散を達成するために、所定の順序は選択され得る。いくつかの例において、所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む。いくつかの実施形態において、並べ替えが全ビット拡散を達成するために、しきい値回数は、少なくとも１７回を含む。動作３０８において、データ処理ハードウェア１４２は、並べ替えられた状態の内側ビット２１０，２１０ｉＰの、以前の状態の内側ビット２１０ｉとのＸＯＲを実行する。ＸＯＲは、ＸＯＲされた内側ビット２１０ｉｘを生成し、ＰＲＮＧ２００に「バックトラッキング耐性」を提供し、ＰＲＮＧ２００の現在の状態（例えば、並べ替えられた状態［１］）が損なわれた場合でも過去の出力の再構築を防ぐ。
【００３６】
ソフトウェアアプリケーション（すなわち、ソフトウェアリソース）は、コンピューティング装置にタスクを行わせるコンピュータソフトウェアを指し得る。いくつかの例において、ソフトウェアアプリケーションは、「アプリケーション」、「アプリ」または「プログラム」と呼ばれ得る。例示的なアプリケーションは、システム診断アプリケーション、システム管理アプリケーション、システム保守アプリケーション、ワードプロセッシングアプリケーション、スプレッドシートアプリケーション、メッセージングアプリケーション、メディアストリーミングアプリケーション、ソーシャルネットワーキングアプリケーションおよびゲームアプリケーションを含むが、これらに限定されない。
【００３７】
非一時的メモリは、コンピューティング装置による使用のための一時的または永続的な基盤上にプログラム（例えば、命令の列）またはデータ（例えば、プログラム状態情報）を格納するために用いられる物理的装置であり得る。非一時的メモリは、揮発性および／または不揮発性のアドレス指定できる半導体メモリであり得る。不揮発性メモリの例は、フラッシュメモリおよび読み取り専用メモリ（ＲＯＭ：read-only memory）／プログラマブル読み取り専用メモリ（ＰＲＯＭ：programmable read-only memory）／消去可能なプログラマブル読み取り専用メモリ（ＥＰＲＯＭ：erasable programmable read-only memory）／電子的に消去可能なプログラマブル読み取り専用メモリ（ＥＥＰＲＯＭ：electronically erasable programmable read-only memory）（例えば、ブートプログラムなどのファームウェアに対して通常用いられる）を含むが、これらに限定されない。揮発性メモリの例は、ランダムアクセスメモリ（ＲＡＭ：random access memory）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ：dynamic random access memory）、スタティックランダムアクセスメモリ（ＳＲＡＭ:static random access memory）、相変化メモリ（ＰＣＭ: phase change memory）、およびディスクまたはテープを含むが、これらに限定されない。
【００３８】
図４は、本明細書において説明されるシステムおよび方法を実施するために用いられ得る例示的なコンピューティング装置４００の概略図である。コンピューティング装置４００は、ラップトップ、デスクトップ、ワークステーション、携帯情報端末、サーバ、ブレードサーバ、メインフレーム、および他の適切なコンピュータなど、様々な形態のデジタルコンピュータを表すことを意図している。ここに示されている構成要素、それらの接続および関係、並びにそれらの機能は、例示的であることのみを意図しており、本明細書において説明および／または請求されている発明の実施を制限することを意図していない。
【００３９】
コンピューティング装置４００は、プロセッサ４１０と、メモリ４２０と、ストレージ装置４３０と、メモリ４２０および高速拡張ポート４４０に接続する高速インターフェース／コントローラ４４０と、低速バス４７０およびストレージ装置４３０に接続する低速インターフェース／コントローラ４６０とを含む。ＰＲＮＧ２００は、コンピューティング装置４００上に存在し得る。構成要素４１０，４２０，４３０，４４０，４５０および４６０の各々は、様々なバスを用いて相互接続され、共通のマザーボード上に、または適切に他の方法で取り付けられ得る。プロセッサ４１０（例えば、データ処理ハードウェア１４２）は、高速インターフェース４４０に結合されたディスプレイ４８０などの外部の入力／出力装置上のグラフィカルユーザーインターフェース（ＧＵＩ：graphical user interface）のためのグラフィカル情報を表示するためにメモリ４２０にまたはストレージ装置４３０上に格納された命令を含む、コンピューティング装置４００内で実行するための命令を処理できる。他の実施形態において、多数のメモリおよび多数種類のメモリとともに、多数のプロセッサおよび／または多数のバスは、適切に用いられ得る。また、多数のコンピューティング装置４００は、必要な動作の一部を提供する各装置と接続され得る（例えば、サーババンク、ブレードサーバのグループ、またはマルチプロセッサシステムとして）。
【００４０】
メモリ４２０（例えば、メモリハードウェア１４４）は、コンピューティング装置４００内に一時的に情報を格納する。メモリ４２０は、コンピュータ読み取り可能な媒体、揮発性メモリユニット（複数可）、または不揮発性メモリユニット（複数可）であり得る。非一時的メモリ４２０は、コンピューティング装置４００による使用のための一時的または永続的な基盤上のプログラム（例えば、命令の列）またはデータ（例えば、プログラム状態情報）を格納するために用いられる物理的な装置であり得る。不揮発性メモリの例は、フラッシュメモリおよび読み取り専用メモリ（ＲＯＭ）／プログラマブル読み取り専用メモリ（ＰＲＯＭ）／消去可能なプログラマブル読み取り専用メモリ（ＥＰＲＯＭ）／電子的に消去可能なプログラマブル読み取り専用メモリ（ＥＥＰＲＯＭ）（例えば、ブートプログラムなどのファームウェアに通常用いられる）を含むが、これらに限定されない。揮発性メモリの例は、ランダムアクセスメモリ（ＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、スタティックランダムアクセスメモリ（ＳＲＡＭ）、相変化メモリ（ＰＣＭ）、およびディスクまたはテープを含むが、これらに限定されない。
【００４１】
ストレージ装置４３０は、コンピューティング装置４００のための大容量ストレージを提供できる。いくつかの実施形態において、ストレージ装置４３０は、コンピュータ読み取り可能な媒体である。様々な異なる実施形態において、ストレージ装置４３０は、フロッピー（登録商標）ディスク装置、ハードディスク装置、光ディスク装置、もしくはテープ装置、フラッシュメモリもしくは他の同様の固体メモリ装置、またはストレージエリアネットワークもしくはその他の構成における装置を含む、装置のアレイであり得る。追加的な実施形態において、コンピュータプログラム製品は、情報担体において明白に具現化される。コンピュータプログラム製品は、実行されると上述の方法などの１つ以上の方法を行う命令を含む。情報担体は、メモリ４２０、ストレージ装置４３０、またはプロセッサ４１０上のメモリなどの、コンピュータまたは機械読み取り可能な媒体である。
【００４２】
低速コントローラ４６０が低帯域幅集約型の動作を管理する一方で、高速コントローラ４４０は、コンピューティング装置４００に対する帯域幅集約型の動作を管理する。デューティのそのような割り当ては例示的にすぎない。いくつかの実施形態において、高速コントローラ４４０は、メモリ４２０と、（例えば、グラフィックスプロセッサまたはアクセラレータを介して）ディスプレイ４８０と、様々な拡張カード（図示しない）を受け入れ得る高速拡張ポート４５０とに結合される。いくつかの実施形態において、低速コントローラ４６０は、ストレージ装置４３０と低速拡張ポート４９０とに結合される。低速拡張ポート４９０は、様々な通信ポート（例えば、ＵＳＢ、ブルートゥース（登録商標）、イーサネット（登録商標）、ワイヤレスイーサネット）を含んでもよく、キーボード、ポインティング装置、スキャナー、または、例えばネットワークアダプタなどを介した、スイッチもしくはルーターなどのネットワーク装置などの１つ以上の入力／出力装置に結合され得る。
【００４３】
コンピューティング装置４００は、図示されるように、いくつかの異なる形態において実現され得る。例えば、それは、標準サーバ４００ａとして若しくはそのようなサーバ４００ａのグループにおいて複数回、ラップトップコンピュータ４００ｂとして、またはラックサーバシステム４００ｃの一部として実現され得る。
【００４４】
本明細書において説明されるシステム及び技術の様々な実施形態は、デジタル電子回路および／もしくは光回路、集積回路、特定用途向け集積回路（ＡＳＩＣｓ：application specific integrated circuits）、コンピュータハードウェア、ファームウェア、ソフトウェア、並びに／又はそれらの組み合わせにおいて実現できる。これらの様々な実施形態は、少なくとも１つのプログラマブルプロセッサを含むプログラマブルシステム上で実行可能および／または解釈可能な１つ以上のコンピュータプログラムにおける実施形態を含み得る。そのシステムは、ストレージシステム、少なくとも１つの入力装置、および少なくとも１つの出力装置からデータ並びに命令を受信し、それらにデータ並びに命令を送信するように結合された、専用または汎用のものであり得る。
【００４５】
これらのコンピュータプログラム（プログラム、ソフトウェア、ソフトウェアアプリケーション、又はコードとしても知られる）は、プログラマブルプロセッサのための機械命令を含み、高水準手続き型および／もしくはオブジェクト指向プログラミング言語、ならびに／またはアセンブリ／機械言語において実施され得る。本明細書において用いるとき、「機械読み取り可能な媒体」、および「コンピュータ読み取り可能な媒体」という用語は、機械命令および／もしくはデータをプログラマブルプロセッサに提供するために用いられる、任意のコンピュータプログラム製品、非一時的なコンピュータ読み取り可能な媒体、機器ならびに／または装置（例えば、磁気ディスク、光ディスク、メモリ、プログラマブルロジックデバイス（ＰＬＤｓ：Programmable Logic Devices））を指す。当該媒体は、機械命令を機械読み取り可能な信号として受信する、機械読み取り可能な媒体を含む。「機械読み取り可能な信号」という用語は、機械命令および／またはデータをプログラマブルプロセッサに提供するために用いられる任意の信号を指す。
【００４６】
本明細書において説明されるプロセスおよび論理フローは、入力データ上で動作し出力を生成することにより機能を行うための、１つ以上のコンピュータプログラムを実行する１つ以上のプログラマブルプロセッサによって行われ得る。当該プロセスおよび論理フローは、専用の論理回路、例えばフィールドプログラマブルゲートアレイ（ＦＰＧＡ：field programmable gate array）または特定用途向け集積回路（ＡＳＩＣ）によっても行われ得る。コンピュータプログラムの実行に対して好適なプロセッサは、例として、汎用のマイクロプロセッサおよび専用のマイクロプロセッサの両方、ならびに任意の種類のデジタルコンピュータの任意の１つ以上のプロセッサを含む。一般に、プロセッサは、読み取り専用メモリ若しくはランダムアクセスメモリ、またはその両方から命令およびデータを受け取る。コンピュータの必須の要素は、命令を実行するためのプロセッサ、および命令とデータとを格納するための１つ以上のメモリ装置である。一般に、コンピュータは、データを格納するための１つ以上の大容量ストレージ装置、例えば磁気ディスク、光磁気ディスクもしくは光ディスクも含むか、当該１つ以上の大容量記憶装置からデータを受信するか若しくは当該１つ以上の大容量記憶装置にデータを転送するよう動作可能に結合されるか、または両方の場合がある。しかしながら、コンピュータは、そのような装置を有していなくてもよい。コンピュータプログラム命令およびデータを格納することに対して好適である、コンピュータ読み取り可能な媒体は、半導体メモリ装置、例えばＥＰＲＯＭ、ＥＥＰＲＯＭおよびフラッシュメモリ装置；磁気ディスク、例えば内部のハードディスクまたはリムーバブルディスク；光磁気ディスク；ならびにＣＤ−ＲＯＭおよびＤＶＤ−ＲＯＭディスクを例として含む、全ての形態の不揮発性メモリ、媒体ならびにメモリ装置を含む。プロセッサおよびメモリは、専用の論理回路によって補完され得るか、または専用の論理回路に組み込まれ得る。
【００４７】
ユーザーとの対話を提供するために、本開示の１つ以上の側面は、ユーザーに情報を表示するためのディスプレイ装置、例えば、陰極線管（ＣＲＴ：cathode ray tube）、液晶ディスプレイ（ＬＣＤ：liquid crystal display）モニターまたはタッチスクリーンと、任意にキーボード及びポインティング装置、例えば、マウスまたはトラックボールとを有するコンピュータ上で実施され得る。ユーザーは、当該キーボード及びポインティング装置により、コンピュータに入力を与えることができる。他の種類の装置は、ユーザーとの対話を与えるために同様に用いられ得る；例えば、ユーザーに与えられるフィードバックは、任意の形態の感覚のフィードバック、例えば、視覚のフィードバック、聴覚のフィードバック、又は触覚のフィードバックであり得る；そして、ユーザーからの入力は、音響、音声、又は触覚の入力を含む、任意の形態において受信され得る。加えて、コンピュータは、ユーザーにより用いられる装置へ文書を送信することにより、および当該装置から文書を受信することによりユーザーと対話できる；例えば、コンピュータは、ウェブブラウザーから受信されたリクエストに応答して、ユーザーのクライアント装置上のウェブブラウザーへウェブページを送信することにより、ユーザーと対話できる。
【００４８】
多くの実施形態が説明された。それにもかかわらず、本開示の趣旨および範囲から逸脱することなく、様々な変更がなされ得ることが理解されるであろう。したがって、他の実施形態は、以下の請求の範囲内にある。
【図１】
2021501902.tif 000007
【図２Ａ】
2021501902.tif 000008
【図２Ｂ】
2021501902.tif 000009
【図２Ｃ】
2021501902.tif 000010
【図３】
2021501902.tif 000011
【図４】
2021501902.tif 000012
【手続補正書】
【提出日】令和2年7月22日(2020.7.22)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
乱数（２０２）を生成するための方法（３００）であって、前記方法は、
データ処理ハードウェア（１４２）が、内側ビット（２１０ｉ）と外側ビット（２１０ｏ）とを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ：pseudo-random number generator）（２００）を初期化することを備え、
前記内側ビット（２１０ｉ）は、前記２，０４８ビットの第１の１２８ビットを含み、前記外側ビット（２１０ｏ）は、前記２，０４８ビットの残りのビットを含み、
前記方法は、さらに、前記データ処理ハードウェア（１４２）が、前記ＰＲＮＧ（２００）の前記状態を並べ替えることを備え、
前記並べ替えることは、
キーソース（１９０）から先進暗号化標準（ＡＥＳ：Advanced Encryption Standard）ラウンドキー（１９２）を検索することと、
しきい値回数にわたって、前記ＡＥＳラウンドキー（１９２）を用いてラウンド関数を実行することとによって実行され、
前記ラウンド関数は、１２８ビットの１６ブランチ（２２０）を有するファイステルネットワークの奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の関数とＸＯＲすることを含み、
前記並べ替えることは、さらに、
前記しきい値回数にわたって、１２８ビットの各ブランチ（２２０）を所定の順序にシャッフルすることによって実行され、
前記方法は、さらに、
前記データ処理ハードウェア（１４２）が、前記並べ替えられた状態の前記内側ビット（２１０ｉ）の、以前の状態の前記内側ビット（２１０ｉ）とのＸＯＲを実行することを備える、方法。
【請求項２】
前記ＰＲＮＧ（２００）を初期化することは、
前記ＰＲＮＧ（２００）の前記状態をゼロに設定することと、
前記外側ビット（２１０ｏ）を任意のシード値に設定することとを含む、請求項１に記載の方法（３００）。
【請求項３】
前記ＰＲＮＧ（２００）を初期化することは、前記ＰＲＮＧ（２００）の前記状態を以前の状態に設定することを含む、請求項１に記載の方法（３００）。
【請求項４】
前記しきい値回数は、少なくとも１７回を含む、請求項１〜３のいずれか１項に記載の方法（３００）。
【請求項５】
前記ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む、請求項１〜４のいずれか１項に記載の方法（３００）。
【請求項６】
ＡＥＳの前記少なくとも２ラウンドの各々は、ＡＥＳの他のラウンドの前記ＡＥＳラウンドキー（１９２）とは異なる、対応するＡＥＳラウンドキー（１９２）を用いる、請求項５に記載の方法（３００）。
【請求項７】
前記ファイステルネットワークの前記奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の前記関数とＸＯＲすることは、ランダムビット（２１０）という結果を生じ、前記外側ビット（２１０ｏ）は、前記結果として生じるランダムビット（２１０）を含む、請求項１〜６のいずれか１項に記載の方法（３００）。
【請求項８】
１２８ビットの各ブランチ（２２０）を前記所定の順序にシャッフルすることは、８回、前記ラウンド関数を実行して各ブランチ（２２０）をシャッフルした後に、全サブブランチ拡散を達成する、請求項１〜７のいずれか１項に記載の方法（３００）。
【請求項９】
前記所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む、請求項１〜８のいずれか１項に記載の方法（３００）。
【請求項１０】
前記内側ビット（２１０ｉ）へのアクセスを防止し、前記外側ビット（２１０ｏ）へのアクセスを許可することをさらに含む、請求項１〜９のいずれか１項に記載の方法（３００）。
【請求項１１】
システム（１００）であって、前記システムは、
データ処理ハードウェア（１４２）と、
前記データ処理ハードウェア（１４２）に通信するメモリハードウェア（１４４）とを備え、前記メモリハードウェア（１４４）は、前記データ処理ハードウェア（１４２）上で実行されると前記データ処理ハードウェア（１４２）に以下の動作を行わせる命令を格納し、前記動作は、
内側ビット（２１０ｉ）と外側ビット（２１０ｏ）とを含む２，０４８ビットの状態を有する擬似乱数生成器（ＰＲＮＧ）（２００）を初期化することを含み、
前記内側ビット（２１０ｉ）は、前記２，０４８ビットの第１の１２８ビットを含み、前記外側ビット（２１０ｏ）は、前記２，０４８ビットの残りのビットを含み、
前記動作は、さらに、前記ＰＲＮＧ（２００）の前記状態を並べ替えることを含み、
前記並べ替えることは、
キーソース（１９０）から先進暗号化標準（ＡＥＳ）ラウンドキー（１９２）を検索することと、
しきい値回数にわたって、前記ＡＥＳラウンドキー（１９２）を用いてラウンド関数を実行することとによって実行され、
前記ラウンド関数は、１２８ビットの１６ブランチ（２２０）を有するファイステルネットワークの奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の関数とＸＯＲすることを含み、
前記並べ替えることは、さらに、
前記しきい値回数にわたって、１２８ビットの各ブランチ（２２０）を所定の順序にシャッフルすることによって実行され、
前記動作は、さらに、
前記並べ替えられた状態の前記内側ビット（２１０ｉ）の、以前の状態の前記内側ビット（２１０ｉ）とのＸＯＲを実行することを含む、システム。
【請求項１２】
前記ＰＲＮＧ（２００）を初期化することは、
前記ＰＲＮＧ（２００）の前記状態をゼロに設定することと、
前記外側ビット（２１０ｏ）を任意のシード値に設定することとを含む、請求項１１に記載のシステム（１００）。
【請求項１３】
前記ＰＲＮＧ（２００）を初期化することは、前記ＰＲＮＧ（２００）の前記状態を以前の状態に設定することを含む、請求項１１に記載のシステム（１００）。
【請求項１４】
前記しきい値回数は、少なくとも１７回を含む、請求項１１〜１３のいずれか一項に記載のシステム（１００）。
【請求項１５】
前記ラウンド関数は、ＡＥＳの少なくとも２ラウンドを含む、請求項１１〜１４のいずれか一項に記載のシステム（１００）。
【請求項１６】
ＡＥＳの前記少なくとも２ラウンドの各々は、ＡＥＳの他のラウンドの前記ＡＥＳラウンドキー（１９２）とは異なる、対応するＡＥＳラウンドキー（１９２）を用いる、請求項１５に記載のシステム（１００）。
【請求項１７】
前記ファイステルネットワークの前記奇数番号のブランチ（２２０）を、前記ファイステルネットワークの、対応する偶数番号の隣接ブランチ（２２０）の前記関数とＸＯＲすることは、ランダムビット（２０２）という結果を生じ、前記外側ビット（２１０ｏ）は、前記結果として生じるランダムビット（２０２）を含む、請求項１１〜１６のいずれか１項に記載のシステム（１００）。
【請求項１８】
１２８ビットの各ブランチ（２２０）を前記所定の順序にシャッフルすることは、８回、前記ラウンド関数を実行して各ブランチ（２２０）をシャッフルした後に、全サブブランチ拡散を達成する、請求項１１〜１７のいずれか１項に記載のシステム（１００）。
【請求項１９】
前記所定の順序は、｛７，２，１３，４，１１，８，３，６，１５，０，９，１０，１，１４，５，１２｝を含む、請求項１１〜１８のいずれか１項に記載のシステム（１００）。
【請求項２０】
前記動作は、前記内側ビット（２１０ｉ）へのアクセスを防止し、前記外側ビット（２１０ｏ）へのアクセスを許可することをさらに含む、請求項１１〜１９のいずれか１項に記載のシステム（１００）。
【国際調査報告】
2021501902.tif 000013
2021501902.tif 000014