このクラスのプログラムの中心にあるのは、 擬似乱数ジェネレーター 、つまり関数G:{0,1} n- > {0,1} n + 1です。 実際、擬似ランダムジェネレータのタスクは、初期データに基づいて少なくとも1ビットの「ランダム性」を取得することです。 次に、そのようなジェネレーターを数回実行して、必要なビット数を取得し、それらを文字範囲に変換して、新しいパスワードを受け取ります。 実際には、2つの問題が発生します。
- 初期データを取得する場所(ジェネレーターの初期化);
- 使用できる機能。
初期データ
すべてのCプログラマーが乱数ジェネレーターを初期化するかなり馴染みのある方法は、現在の時間値の初期値を設定することです。
srand ( time(NULL) );
この方法は非常に悪く、ただの災害です!
time
関数の説明を読むと、1970年1月1日UTCの00:00時から始まる秒数が出力されていることがわかります。
したがって、
time
関数で実行される特定のジェネレーターを使用したことを知っているため、リソースへの登録日(またはサイトへの最後の訪問時などの最後のパスワード変更)を見つけて86400以上の初期値(1日で何秒も)を繰り返すだけで十分です数分で。 そして、彼のパスワードが異なるレジスタ、数字、特殊文字の何百もの文字で構成されていることは問題ではありません。唯一の事故はジェネレータの起動時だからです。
プロセッサがリセットされてからのクロックサイクル数を返すRDTSC関数を使用すると、状況は多少改善されますが、値の範囲は0〜2 64 -1であり、異なるステップを備えた異なるプロセッサでは個別です。 彼の妄想を満たすために-これは良くありません。 現実には、ランダム性のこのマージンは、使用される文字セットに応じて、6〜8文字で生成されたパスワードに対してのみ十分です。
これらは最も単純な方法です(そして、それらが最も頻繁に使用されないことを望みます。そうでなければ、そのようなプログラムには意味がありません)。 十分に良い初期値を与えることができるものは何ですか?
まず、環境分析:起動時に、ユーザードキュメントのハッシュを読み取るプログラム。 誰もそれらが何であるかを予測することはできません。そして、ほぼあらゆる長さと良質のジェネレーターの初期値を取得します。 例外は、何も存在しない実用的なベアコンピュータです。
第二に、ユーザーと対話的です:十数個のボタンを押すように無意味になります。qwerty123456のようなパターンでもほとんど明らかです(これはパスワードではありませんが、A6 @ sIp!V0 ] x、ただし、ジェネレータプログラムを使用したことを知っているので、簡単に破ることができます)、しかし、マウスをひきつけることは非常に良いオプションであるため、一般的なパターンのない非常に大量の乱数があります。
さらに良いのは、カメラの電源を入れるか、マイクから録音することです。ハッシュ関数を通過する「ノイズのある」データの膨大なストリームは、任意の長さの優れたイニシャライザーを提供します。
したがって、いくつかの道徳:プログラムがパスワードを生成する方法、量、初期データを取得する場所はそれほど重要ではありません。 インタラクティビティがまったく発生しない場合は、疑う必要があります。
生成関数
実際、何かを発明する意味はほとんどありません。 良いチャンスを与えることができる最も単純なオブジェクトはハッシュ関数です。
プログラムが他の何かを使用する場合、それを信頼しない可能性がすべてあります。 X i + 1 =(a * X i + c)mod mのような素晴らしいマジックシーケンスは、信頼できる(暗号のランダム性)を与えません。
ハッシュ関数の場合、それらの使用の合法性についてはかなり単純な根拠があります。 だから。
関数F:{0,1} n- > {0,1} mは、 一方向関数と呼ばれます。
1)多項式時間で計算可能です。
2)良い確率(2 -mより大きい)でF -1を正しく計算する多項式アルゴリズムはありません。
m = nの場合、このような関数は一方向の置換と呼ばれます。
一般に、擬似乱数ジェネレーターは一方向関数です。
そして、任意の片側置換により、疑似乱数ジェネレーターを構築できます。
G({a 1 、a 2 、... an})= {a 1 、a 2 、... an、F({{a 1 、a 2 、... a n })}。
一般的な構築スキームは次のとおりです。

ここで、Gは一方向の関数呼び出し(MD5など)で、y '、y、...は出力ランダムパスワードのビットです。
そのため、擬似乱数ジェネレーターの存在は、一方向関数の存在に続くと主張されています[P] = NPの場合、それは順番に存在します。
ハッシュ関数(MD5、SHA1、GOST)の特定のケースでは、出力値のランダム性に疑問を投げかけるためにF -1を計算するためのアルゴリズムはこれまでのところありません。
したがって、P = NPであることが突然判明した場合にのみ、疑似ランダム生成でハッシュ関数の使用を恐れることができます。
しかし、これも私たちを悩ませません:結局、ハッシュ関数の逆を簡単に構築することができる場合、値との整合性をチェックする必要がある理論的なパスワードにつながる擬似ランダムバイトのチェーンを構築するよりも、データベースからハッシュ値を回すことでパスワードを取得する方が簡単ですベースから。
簡単な論文:MD5でさえ 、擬似ランダムジェネレーター(パスワード用)に使用できます!
ブロック暗号は、擬似ランダムジェネレーター、楕円曲線、微分方程式の解を得るためによく使用されます-これには理由がありますが、私は(今のところ)それらに触れません。
[*]応用暗号ハンドブック、A。メネゼス、P。ヴァンオーショー、S。ヴァンストーン。
UDP:きちんとした絵の作者-bad_guy