0

Java でハッシュ アルゴリズムをクラックしようとしています。

    public static int encode(String file) {
            int hash = 0;
            file = file.toUpperCase();

            for(int i = 0; i < file.length(); i++) {
                    hash = (hash * 61 + file.charAt(i)) - 32;
            }
            return hash;
    }

これは私の試みです：

public static String decode(int hash) {
            long realHash = (hash < 0 ? Integer.MAX_VALUE + Math.abs(hash) : hash);
            ByteBuffer buffer = ByteBuffer.allocate(50);

            while (realHash > 0) {
                    buffer.put((byte) ((realHash % 61) + 32));
                    realHash = (realHash - 32) / 61;
            }
            buffer.flip();
            return new String(buffer.array()).trim();
    }

私のソリューションでは深刻なデータ損失が発生しているようです。整数のオーバーフローにより、長いテキスト データを完全にハッシュ解除できるとは思いません。助言がありますか？

4

1 に答える 1

8

問題なのは整数オーバーフローではありません。それは、溶岩の上を運転して車を爆発させ、適切な種類のガソリンを購入しなかったと結論付けるようなものです.

本当の問題は、ハッシュ アルゴリズムを「クラック」できないことです。それには、次の 1 つの大きな理由があります。

情報理論

シャノン エントロピーとして知られる情報理論の用語があります。(公正な警告: この記事を理解するのは簡単ではありません。) 簡単に言えば、特定の情報のチャンクをエンコードするのに必要な最小ビット数があるということです。

このサイトには、特定のテキストを無損失でエンコードするために必要なエントロピーの量 (つまり、最小ビット数) を決定すると主張する計算機があります。私はこの職人的なフィラーテキストのチャンクを提供しました：

メギンズはビターズ豆腐を食べ、ウェス・アンダーソンはフードトラックのクラフトビールをiPhoneに。シングルオリジン コーヒー シーンスター イッカク、マンブルコア mlkshk ジーンズ ショートパンツ チア トラスト ファンド アート パーティー ポアオーバー ビターズについて聞いたことがないかもしれません。ポラロイド クラフト ビール インテリジア、ビニール マーファ ブルックリン うま味。

システムで が 32 ビットであると仮定するとint、特定のファイルをエンコードするためのスペースは 32 ビットしかありません。しかし、上記のチャンクは、戦争と平和や米国のコードなど、私が使用した可能性のあるものと比較してそれほど長くはありませんが、テキストを再構築する希望を持ちたい場合は、エンコードに少なくとも1472 ビットが必要です。

(コメンターのtemplatetypedefは、コルモゴロフの複雑さ(その概念のもう 1 つの良い説明) を指しています。これは、文字列の情報内容とハッシュをクラックすることの無益さを表現するさらに優れた方法です。)

そのため、情報理論的には (事前に入力された圧縮辞書を使用するなどの不正行為は別として) 、32 ビットの int からこれらの少数の (単純な手作りのローカルソースの) 文を再構築することは不可能です。残念ながら宇宙の基本法則です。起こらない。

コードからの実際の例

別のコメンターはピジョンホールの原理について言及しています。これは、N 個のスロット (この場合は 2^32) がある場合、同じスロットに 2 つ以上のものを入れないと N 個を超えるものを入れることができないという単純な考え方です。

ハッシュ関数を見てみましょう:

public static int encode(String file) {
        int hash = 0;
        file = file.toUpperCase();

        for(int i = 0; i < file.length(); i++) {
                hash = (hash * 61 + file.charAt(i)) - 32;
        }
        return hash;
}

具体的には、次の行：

file = file.toUpperCase();

2 つのファイルをハッシュしたい:

mary had a little lamb

Mary Had A Little Lamb

それらのハッシュ値はどうなりますか? 考えてみてください。

(補足: とは言っても、あなたはint をオーバーフローしています。:)そのようなことをしたいなら、モジュラー演算はあなたの友達です。)

于 2013-10-21T00:09:44.223 に答える