事故は偶然ではありませんか？

注釈

この記事は、数字のランダムおよび擬似ランダムシーケンス（SPおよびPSP）に関する基本的な規定の体系化に専念しています。 生成されたシーケンスのランダム性をテストするための既知のアプローチの概要を示します。 このトピックの適用値は、鍵および補助情報（乱数、初期化ベクトルなど）を生成するためにPSPが暗号情報保護システムで広く使用されているという事実によって決まります。







はじめに

古代以来、数学者だけでなくランダム性を研究してきました。 事故は、統計、ゲーム理論、ファジィ集合の理論、物理学と化学の分野、マイクロワールドの特性の研究、経済学の分野、経済危機の発生と発展、世界通貨の軌跡に対するランダム要因の影響の研究において、多くの数学的分野で研究の対象となっています、歴史と社会学-歴史的出来事の発展と時代の変化に関する偶然の要因の重要性の研究。 20世紀にすでに科学が発展したことは、真に予測不可能な一連の出来事が、研究者を混乱ではなく、グローバルな性質の非常に厳格な定期的な結論に導くことを示しました。 この論文は、確率論の中心極限定理（および他の定理）の助けを借りて簡単に説明できます。 ランダムなオブジェクトのシステムの特異性に注意する必要がありますが、これはある意味で逆説的に見えるかもしれません。 極端な場合、大規模なシステムのローカルな法則ではなくグローバルな法則を予測することを記述することがはるかに可能です。 これは、確かに需要がある2つの現代の研究の方向性を定義しています。ランダムシステムのグローバルな法則の検索と、ローカルイベントの予測不能性のランダムシステムの正当化です。 乱数のシーケンスまたは他のセットの要素は、複雑なオブジェクトやシステムの特性を実験的に研究するために効果的に使用されます。



ランダムシーケンス

SPは暗号化で重要な役割を果たします.SPは、暗号化アルゴリズムのキーと初期パラメーター、およびストリーム暗号システムでの暗号化置換のシーケンスを生成するために使用されます。 ランダム性と暗号化は密接に相互接続されています。暗号化システムの主な目標は、非ランダムな意味のある平文を暗号文の文字の外見上ランダムなシーケンスに変換することです。 暗号システムのこのプロパティは、メモリ帯域幅を生成するために使用されます。

暗号システムの最高の暗号特性は、いわゆる理想的なランダムシーケンス （ICP）を使用して達成されます 。その数学的モデルは、特定の有限アルファベット上で均一な確率分布を持つ独立したランダム変数のシーケンスの実装によって表されます。 このようなシーケンスは、 均一に分散された （有限セットで） ランダムシーケンス （RRSP）と呼ばれます。 多くのプロパティ、特に[1]、[4]、[5]および[7]のRRSPのプロパティを記述することに専念しています。



「ランダム性」という用語の定義へのアプローチ

計算可能性とアルゴリズムの複雑さの概念に基づいて、「ランダム性」という用語の正式な定義にはさまざまなアプローチがあります[2]。 歴史的に、最初のアプローチである周波数1は、20世紀の初めにフォンミーゼス（ミーゼス）によって提案され、教会（教会）、コルモゴロフ、およびラブランドによって開発されました。 頻度アプローチの考え方は、合弁事業では、要素の発生頻度が安定している必要があるということです。 たとえば、符号0と1は、バイナリSPだけでなく、生成の初期条件とは無関係に選択されたそのサブシーケンスでも、独立して等しい確率で発生する必要があります。



KolmogorovとChaitinが独自に提案した別のアプローチcomplexは、SP実装の記述はこの実装自体よりも大幅に短くすることはできないという事実に基づいています。 つまり、ジョイントベンチャーは複雑な構造を持たなければならず、その初期要素の エントロピーは大きくなければなりません。 このアプローチでは、アルゴリズムの複雑さがシーケンスの長さに近い場合、シーケンスはランダムであることが示されています。



3番目のアプローチである量的アプローチは、Martin-Lofによって開発されました。 これは、シーケンスの確率空間を非ランダムとランダムに分割することから成ります（後者は比較的多くあります）。 パターンが観察されるシーケンスは、ランダムではないと見なされます。 パターンを特定するために設計された特定のテストのセットに合格すると、シーケンスはランダムと見なされます。 ただし、シーケンスが統計テストに合格する必要がある場合は、ジョイントベンチャーがまったく存在しないことがわかります。 実際には、特定のテストセットが使用されます。テストセットを満たさないSPの割合は0になり、シーケンスの長さは無制限に増加します。



ここ数十年、暗号アプリケーションで生じる要件に関連して、ジョイントベンチャーを決定する暗号アプローチが形成されました。パターンの検索の計算の複雑さが所定の値以上である場合、シーケンスはランダムと見なされます。 このアプローチは、暗号システムの強度を決定する既存の体系的なアプローチと一致しています。



ランダム性の決定に対するこれらのアプローチには欠点があります。 周波数アプローチは、サブシーケンスを選択するためのルールが不確実であるため、実際には困難です。複雑なアプローチでは、プログラミング言語の冗長性を減らす必要があります。 定量的アプローチの使用は、調査されたシーケンスに適用される一連のテストを決定するのが困難です。 暗号化アプローチの複雑さのより低い推定値は、一連のよく知られたテストに焦点を当てており、時間をかけて補充することができ、複雑さの再評価につながります。 同時に、暗号化アプリケーションの場合、シーケンスの統計的特性とその範囲を考慮した暗号化アプローチが最適です。



CAPテスト

（Herring、C.、Palmore、JI Random Number Generators are Chaotic、1995）シーケンスのアルゴリズム実装は不完全であることが証明されています。つまり、真のランダムシーケンスはどのルールでも計算できないため、非周期無限である必要があります。シーケンス。 RRSPをシミュレートする特定のルールによって生成されたシーケンスは、 疑似ランダムシーケンス （PRP）と呼ばれます。 シミュレーションの成功は、生成されたSRPの多くの特性が、COIの同様の特性に近接していると理解されます。



暗号化アプリケーションで使用されるSRPの生成は、有限集合X（多くの場合Xはバイナリn次元ベクトルの集合）の特定の変換の複数の反復の実装に基づいています。 このような出力シーケンスは周期的です。 ただし、周期の長さは非常に大きくなる可能性があります。これは、特に、原始特性多項式を持つ線形シフトレジスタを使用することで保証されます。 多くのPSPジェネレーターでは、良好な統計特性と高い線形複雑度、長い周期長が証明されていますが、分析および統計特性を証明することはできません。 次に、統計テストを使用して多くのプロパティを実証します。



SRPを評価するためのさまざまな基準は非常に大きくなっています。 シーケンス分析の各アプローチは、2つのグループのいずれかに起因します。

最初のグループは、長さが短いセグメントに沿ってシーケンスを再現できるパターンの検索に関連付けられています。 さらに、シーケンスの基本的な要件は、比較的単純な符号間依存関係が存在しないことまで低減されます。

基準の2番目のグループは 、シーケンスの統計的特性の推定に関連付けられています：分析者がシーケンスの既知のセグメントから次の（前の）符号を予測できる、つまり、ランダムよりも高い確率で次の（前の）ビットの値を想定できる、研究中のシーケンスに周波数の不均衡があります選ぶ？ 基準の2番目のグループによるSRPの主な要件は、その統計的特性の多くがCOIの特性に対応するという事実、特に、発生頻度と個々の符号とs-gramが十分に大きいs値で均等に分布する必要があるという事実に限定されます。



体系的なアプローチでは、よく知られたテストがシーケンス分析に使用され、分析されたオブジェクトの特徴を考慮して新しいテストが開発されます。 分析中に特定のクラスのシーケンスで新しい弱点が検出された場合、既知のテストの使用済みセットを補充する、対応する新しいテストが開発されます。

シーケンス分析方法の両方のグループは、メモリ帯域幅の分析、特にストリーム暗号の開発に対する体系的なアプローチを構成します。



周期的バイナリSRPの統計特性の基本的な要件の最初の定式化の1つは、S。Golombによって与えられました。 これらのシーケンス要件は、暗号でGolombの仮定として知られるようになりました（Golomb SW Shift Register Sequences、1967）。 ゴロムの仮定は、特にモノグラフ[7]に記載されています。 仮定は、最大周期長の線形回帰シーケンスに固有の正の統計特性を維持する条件から始まります。

Golombルールは、SRPの高品質を保証するものではなく、むしろ必要です。 実際には、SRPの期間、s –グラムの頻度/期間、および自己相関関数の値の理論計算が複雑であるため、SRPの品質を評価するためのGolomb仮説の使用は困難です。 コンピューター計算は、期間が短いPSPでのみ可能です。これにより、暗号化アプリケーションでのGolomb仮説の使用が制限されます。



統計的検定の目的と目的

SRPのランダム性のテストは、SRPの特性を類似のICPの特性と比較することにより、その特定の特性を識別する方法です。

SRPの統計テストを使用して、次のタスクが解決されます。

1）PSPジェネレーターの出力シーケンスの特性の、暗号化アルゴリズムでの使用の観点からの評価（たとえば、秘密鍵として）;

2）ICPと区別できない出力シーケンスによる暗号化プリミティブ（ハッシュ関数、ブロック暗号、ストリーム暗号）の品質の評価、特に、歪み中のアルゴリズムの出力を変更する雪崩効果、中間および出力の相関などの暗号特性の検証シーケンス;

3）「非ランダム」シーケンスを提供するPSPジェネレーターの識別。 新しいPSPジェネレーターの開発。 SRPジェネレーターの正しい実装の検証。

テストの本質は通常、長さkのシーケンスx（k）=（x_1、...、x_k）に関するいわゆる「帰無仮説」H0のテストに帰着します。これにより、xは一様分布の確率スキームのk個の独立したテストに基づいて取得されます。



一般に、統計的検定Tは2桁の関数です。

、

ここで、A *はアルファベットAのシーケンスのセットです。統計的検定Tは、長さkのシーケンスのセットV（k）を「非ランダム」シーケンスのセットV（k、0）（通常は比較的小さい）とセットV（k、1）= V（k）/ V（k、0）ランダムシーケンス。 テストがランダムに選択されたバイナリシーケンスx（k）を拒否する確率Pは、V（k、0）/ 2 ^ kに等しくなります。 原則として、実際のテストではPは0.01を超えません。

定義領域が扱いにくいため、関数Tの正確な計算の複雑さは大きい。 したがって、仮説H0を受け入れる/拒否するための統計的検定は、f_T統計、つまり、多くのシーケンスを多くの実数にマッピングする比較的単純な計算可能な関数と、確率理論法によって決定された仮説H0の統計の確率分布を使用して実行されます。 統計的検定は、ソースデータと決定ルールから計算された統計の組み合わせであり、これに従って、統計値が仮説H0を受け入れるか拒否するかを決定します。

統計的検定は確率的です。つまり、検定の重要な特性である2種類のエラーが発生します。

1）シーケンスがランダムであるが、H0が拒否される場合の第1種のエラー。

2）シーケンスがランダムではないが、H0が受け入れられる場合、第2種のエラーb。

統計的テストシーケンスに合格するかどうかの決定は、さまざまな基準に基づいて行われます[7]。

しきい値に基づきます 。 このアプローチは、特定のシーケンスx（k）のテストf_T（x（k））の統計の計算と、特定のしきい値c（k）とのその後の比較に基づいています。 基準によると、f_T（x（k））<c（k）の場合、バイナリシーケンスx（k）は統計検定に合格しません。 このアプローチでは、誤った判断が比較的頻繁に行われ、信頼性が低いと見なされます。

固定信頼区間に基づきます 。 このアプローチでは、f_T（x（k））が特定の有意水準aに対して計算された統計の信頼区間外にある場合、シーケンスx（k）は統計検定に合格しません。 有意水準が低い場合、信頼区間の幅は大きくなります。 この基準は、最初の基準よりも信頼性があります。

p値計算に基づいています。 基準の3番目のクラスは、 p値（p値）と呼ばれるセグメント[0,1]からのテストの特性の計算に依存しています。 既知の分布則を持つランダム変数と見なされるテストの統計は、大きな値がシーケンスのランダム性の特定の欠陥を示すように構築されます。 確率値p値は、シーケンスがランダムであるという仮定の下で、テスト統計が実験で観測された値よりも大きい値を取る確率です。 つまり、小さなp値はシーケンスのランダム性に対応します。 決定的ルール：有意水準aでは、p値<aの場合、シーケンスx（k）は統計検定に合格しません。 aの値は、間隔[10 ^（-3）; 10 ^（-2）]から取得する必要があります。 以前のアプローチに対するこのアプローチの利点は、計算された確率p値が追加の計算なしで選択された有意水準と比較されることです。



したがって、メモリ帯域幅をテストする主な段階は次のとおりです。

1.仮説H0の乱数列の定式化;

2.有意水準a（第1種のエラーの確率）を設定します。通常、aは間隔[10 ^（-3）; 10 ^（-2）]から取得されます。

3.調査したシーケンスx（k）の統計値f_T（x（k））の計算。

4.特定のテストに依存する式に従って、間隔（0; 1）からp値を計算します。

5. p値と値aの比較：p値> aの場合、テストに合格します。



メモリ帯域幅の統計的テストのための既存のツール

分析されたPSPのパターン（およびさまざまな長さのセグメント）を識別するには、さまざまな統計テストが使用されます。 近年、メモリ帯域幅の分析のために多数のテストが開発されています。 統計テストのよく知られたセットは次のとおりです。



11.11テスト：Donald Knuth（スタンフォード大学）、The Art Of Computer Programming Vol。 2半数値アルゴリズム、 www-cs-faculty.stanford.edu /〜uno / taocp.html

2.15テスト：Andrew Rukhin、et。 al。 （NIST ITL）、NIST Statistics Test Suite、 csrc.nist.gov / groups / ST / toolkit / rng / documentation_software.html

3.12テスト：George Marsaglia（フロリダ州立大学）、DIEHARD、 stat.fsu.edu / pub / diehard

4.11テスト：Pierre L'Ecuyer、Richard Simard（モントリオール大学総合情報学部）、TestU01、 www.iro.umontreal.ca /〜simardr / testu01 / tu01.html

5. 5つのテスト：Helen Gustafson、et。 al。（クイーンズランド工科大学）、Crypt-XS、商用版、 www.qut.edu.au / institute - for - future - environments



上記のセットのテストを主に繰り返す統計テストの他の説明と実装があります。



1. Alfred Menezes et al。、応用暗号ハンドブック

2. Peter Hellekalek（ザルツブルク大学）、pLabプロジェクト、 random.mat.sbg.ac.at

3.ジョンウォーカー（Autodesk、Inc。）、ENT、 www.fourmilab.ch / random

4. Robert G. Brown（デューク大学）、Dieharder、 www.phy.duke.edu / 〜rgb / General / dieharder.php

5. George Marsaglia（フロリダ州立大学）、Wai Wan Tsang（香港大学）、 Diehardの 「蒸留」バージョン、 www.jstatsoft.org / v07 / i03



メモリ帯域幅の統計テストのかなりの数の既存の実装にもかかわらず、この方向は絶えず進化しており、分散コンピューティングシステムを含む、考慮されたテストの新しい実装を提供する新しいプロジェクトが積極的に登場しています。

考慮されたメモリ帯域幅の統計テストのセットは、暗号化アプリケーションで使用される周波数帯域幅ジェネレーターを研究するための便利で柔軟なツールを構成します。

NIST STSパッケージは、より柔軟性、拡張性、効率が高く（テストに費やす時間に関して）、バイナリシーケンスの統計的テストに利用できる最も包括的なパッケージです（詳細については、[5]、[8]、[9]を参照） 。 NIST STSパッケージのテストについては、記事「NISTメソッドを使用した統計的乱数チェック」 habrahabr.ru/company/securitycode/blog/237695 [3]で詳細に説明されています。 NIST STSパッケージに基づいて、ジェネレーターによって開発されたメモリ帯域幅の品質を確実に評価するために、1つではなく複数のテストを実施することが推奨される場合、シーケンスのより完全な統計および構造分析のための方法を構築できます。

すべてのテストは、ランダム性のさまざまな欠陥を特定することを目的としています。明らかになったランダム性の欠陥に関する詳細は、[8]にあります。

実際には、帰無仮説の受け入れまたは拒否は、いくつかの独立したテストの結果に基づいています。独立したテストが異なる結論につながる場合、使用されるすべてのテストの結果の全体を考慮した統計を使用して、テスト結果の組み合わせが使用されます。少数の結合テストでは、Fisher-Pearson統計が使用され、カイ2乗分布と比較されます。組み合わせたテストの数が多い場合は、コルモゴロフ-スミルノフテストをお勧めします。

表1は、さまざまな長さのPSPのテストに推奨されるテストの一部を示しています。



表1 さまざまな長さのPSPの





統計テスト考慮された統計テストの予備分析により、暗号情報保護ツールを開発するさまざまなタスクでの使用に最適なものを判断できました。



使用された文献のリスト

1. Agibalov G.P.暗号化の初期コースの選択された定理。学習ガイド。 : - , 2005. – 116 .

2. .. . , , 2008. – 182 .

3. : NIST. – habrahabr.ru/company/securitycode/blog/237695

4. .., .., .. . . , .: , 2000. – 272 .

5. .., .., .. // . – www.tusur.ru/filearchive/reports-magazine/2012-25-2/108.pdf

6. .., .., .. NIST STS.

7. .. , .: -, 2010. – 424.

8. Rukhin, A., Soto, J., Nechvatal, J., Smid, M., Barker, E., Leigh, S., Levenson, M., Van- gel, M., Banks, D., Heckert, A., Dray, J., Vo, S. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. – www.csrc.nist.gov/publications/nistpubs/800-22/sp-800-22-051501.pdf .

9. Soto Juan, Statistical Testing of Random Number Generators, National Institute of Standards & Technology. – csrc.nist.gov/groups/ST/toolkit/rng/documents/nissc-paper.pdf