ハッシュ関数
パラグラフは退屈です、知っている人-スクロールしてください。 しかし、あなたが知らない、または疑う場合、私たちは先に進みます。
ハッシュ関数は、一方向の変換関数です。 行（パスワード）が与えられると、特定のハッシュ値（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）に基づく