いいえ、レインボーテーブルを生成するために必要なパラメーターや、「強力な」パスワードを作成する方法については説明しません。 トピック自体は少し時代遅れであり、抽象的な問題に役立つ可能性は低いです。 しかし、判明したように、「レインボーテーブル」の基礎は、メモリの時間、つまり「時間とメモリのトレードオフ」を変更する素晴らしい方法です（メソッドまたはアルゴリズムとは呼びません）。 これは
、プリコンピューティングに関する
最初の （おそらく最後ではない）トピックではありませんが、楽しんでください。
ハッシュ関数
パラグラフは退屈です、知っている人-スクロールしてください。 しかし、あなたが知らない、または疑う場合、私たちは先に進みます。
ハッシュ関数は、一方向の変換関数です。 行（パスワード）が与えられると、特定のハッシュ値（16進表記：通常は数字と文字のシーケンスa-f）を受け取るため、元のパスワード行に関する情報を取得することは非常に困難です。
最初は、単語は英語から取られました：ハッシュ-ハッシュ、ゴミ、不要な情報。 ロシア語では、ハッシュまたはハッシュという2つの音訳オプションが可能です。
単語の意味は次のように解釈できます。ハッシュ値によると、有用な情報は受信されません。したがって、それ自体は意味のないバイトのセット、つまりゴミです。
ただし、通常の関数のプロパティを使用すると（つまり、同じハッシュ値を取得するときに常に同じ行で）、ハッシュ関数は承認（アクセス制御）の領域で役立ちます。 パスワードを使用すると、保存して、パスワードを元のパスワードと比較するために使用できるハッシュ値を非常に簡単に取得できます。 同時に、ハッシュ値データベースにアクセスしても、パスワードにアクセスできないように思われます。
簡単な例：文字列
testを管理ユーザーのパスワードとして保存します。 これを行うには、パスワードデータベースに書き込みます。
管理者：
098f6bcd4621d373cade4e832627b4f6 （この一連の文字は、文字列
testの MD5ハッシュ値です）。
これで、どの行もパスワードに準拠しているかどうかを非常に簡単に確認できます。それからハッシュ値を計算し、データベースに保存したものと比較します。
たとえば、
残りの行のMD5は
65e8800b5c6800aad896f888b2a62afcあり、保存したものと一致しません。 したがって、
restはAdminのパスワードではありません。
同時に、回線
テストの MD5は常に
098f6bcd4621d373cade4e832627b4f6であり、保存された値と一致します。 そのため、
テストは常に管理者のパスワードとして機能します。
パスワード回復
「ハッキング」という言葉は忘れてください。「回復」は「自分の」パスワードにしかならない-今では重要ではありません。 ハッシュ関数
fとハッシュ値
yがあります。
f（x）= y 、mathとなるストリング
x （パスワード）を見つけます。
また、
f（x）が
x ^ 2に等しければ、問題を簡単に解決できます。彼らは学校で教えたようです。 しかし、数学者は、正直なハッシュ関数では、特定のポイントで反対を見つけることは徹底的な検索によってのみ可能であると言いました。 そして、O（2 ^ビットのハッシュ値）をソートする必要があります。
実際、これはそうではなく、すべての実際の関数について、この列挙の順序は小さく、正直なハッシュ関数はまったく存在しない可能性があり、この質問は擬似ランダムジェネレータの存在に依存し、それらは順番に反論しません...できないからという理由だけで。バスト。
列挙オプション
列挙のタスクは非常に簡単に形式化されます（多くの点ではありますが）。 アルファベット
Aを持ってみましょう（まだ文字を覚えていますか？）。 与えられた
n （ここでは覚えておいてください）に対して、アルファベット
Aの n文字のすべての文字列を作成します
。 各行について、そのハッシュ値を計算します。
yと一致する場合、問題を解決したようです。
ここで、パスワードの長さによって決まるパスワードの強度を依然として考慮している人々を混乱させたいと思います。 アルファベットの内容よりも長さにほとんど依存しません。
また、例として、
b 、
b 、
test 、
restの4行で構成されるアルファベットを取り上げます。
n = 2の場合、列挙は、aa、ab、atest、arest、ba、bb、btest、brest ...
などの行をカバーし
ます。4^ 2 = 16オプションのみです。ブルートフォースアルゴリズムの複雑さはO（| A | ^ n）です。
パラメータ推定
列挙は、次の2つの場合のいずれかで成功します。
1.第1種の
ハッシュ衝突に遭遇します。
2.元のパスワードは
A ^ nに含まれます（つまり、アルファベット順に構成できます）。
最初のケースに関しては、このアイデアは残す価値があると言えます。 わずか2 ^ 128の異なるハッシュ値しか持たない
MD5の場合でも、これには非常に長い時間がかかります（1秒間に10億個のハッシュ値を反復処理する場合は数千年）。 第1種の衝突と（第2種の）自由衝突とを混同しないでください。それらは
簡単に見つける
ことができますが、実際にはまったく役に立ちません。
したがって、状況2を目指し
ます 。通常の状況
では 、
パラメーターと計算の順序を簡単に推定
できます 。
不正行為なし
したがって、テーブルではこの順序を減らすことはできません。 これは、ハッシュ関数の「不可逆性」のテーゼに反するでしょう。 テーブルでできる
ことは、事前に計算された（直接列挙よりも長い時間）情報を保存することです。これにより、特定の各値に対応するパスワードをかなり迅速に見つけることができます 。
事前計算アルゴリズム
テーブルに2つのハッシュ値s
iとe
iのペアを記録します。 多くの、そのようなペア。
ここで、s
i =
f （
アルファベットからのランダムな文字列 ）。
s
i 1 =
f （
r （s
i ））
s
i 2 =
f （
r （s
i 1 ））
...
e
i =
f （
r （s
i m ））
停止、
rとは何ですか？ そして、これはそのような特別な
リダクション関数です。 任意の法則に従って関数
fのハッシュ値をアルファベット
A ^ nにマップしますが、可能な場合は常に単射性を保持します（関数は異なる引数から異なる値を与える必要があります）。
しばらくの間値を取得する方法を忘れた場合、
チェーンでそれらを書くことができます：
s i →s
i 1 →s
i 2 →...→s
i m →
e i 、ここで
mはチェーンの長さで、同じテーブルのすべてのチェーンで同じです。
O（m）の1つのペアを取得することの難しさ、テーブルにはそれぞれ
N個のペアがあり、O（N * m）時間はテーブルの生成に費やされます。 ディスクO（N）メモリに保存します。 そして、中間値s
i kのいずれかのパスワードはO（m）にあります。
「人間の言語」への翻訳は次のように聞こえます。アルファベット
A ^ nのパスワードを回復できるようにするには、約A ^ n / 5000（m = 5000）バイトのディスクスペース、回復アルゴリズムの約5000ステップが必要です。
事前に計算されるほど、より多くのパスワードを同時に回復できます。 しかし、そのようなテーブルはより「重く」なります。 これが時間とメモリのトレードオフです。
極端な場合は単純です。m= 1の場合、指定されたアルファベットのすべてのハッシュ値をディスクに保存する必要があり、これは非常に多くなります。 ただし、回復時間もO（1）になります（実際にはO（検索（| A | ^ n）の使用により、検索が使用されますが、まあまあです）。
また、m = | A | ^ nの場合、テーブルにかかるのはn〜11バイトだけですが、検索にはテーブルがない場合と同じくらいの時間がかかります。 さらに、テーブルの確率的性質のために成功しないかもしれません（ああ、私はこれを無駄に言ったので、私はそれから膨張しなければなりません）。
使用表
素晴らしい、同じハッシュ値
yとペアのテーブル（s
0 、e
0 ）を持ってみましょう。 （s
1 、e
1 ）; ...（s
N 、e
N ）。
アルゴリズムの最初の反復で、チェーンのエンドポイントの中で
yの値e
iを探します。
幸運なことに、いくつかのk に対して y = e kです。 次に、対応するs kで始まるチェーンを再生成しますが、e kの前にある要素s k N-1は、構造上、f（r（s k N-1 ））= e k = yです。これは、r（ s k N-1 ）必要なパスワード！
それを不幸にして、y
1 = f（r（y））を計算します。 そして、私たちの不運が繰り返されます、y
i =（（f○r）^ i）（y）、
これはfとrをi回連続で書き留めた方法です（表のチェーンと同じように） 。 y
N + 1以上を数えることは意味がないことに注意する価値があります-それらがテーブルにあるとしても、テーブルは私たちを助けません。 そのため、ここでは最大N個のステップがあり、各ステップでy
iをカウントし、e
kを調べます。 そして、最終的にそれが見つかった場合：
s k → s k 1 → ... → s k v → s k v+1 → ... → ... → e k
y → y 1 → ... → y i
ここの矢印は同じことを意味します-fとrの構成です。 したがって、
r（s k v ）は y のパスワードです！
ここで、
y Nを数える必要
がない理由を説明します。「下側」のチェーンは上側のチェーンよりも短くする必要があります
。yについては前の要素を参照します。
それから？
影響を受けないいくつかの質問：
1.テーブルでハッシュをすばやく見つける方法
2.「確率についての何か」:)
3.レインボーテーブルが必要な理由と配置方法
4.多分もっと例が必要になる5）特徴的なポイントとRTとの同時使用
6）GSM A5 / 1暗号解析の飛行解析、5）に基づく