破解哈希算法

Question

我试图破解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();
    }

我的解决方案似乎有严重的数据丢失,我认为由于整数溢出,我不能完全取消长文本数据.有什么建议？

Answer 1

这不是整数溢出问题.这就像驾驶熔岩,让你的汽车爆炸,并断定你没有买到合适的汽油.

真正的问题是你不能"破解"哈希算法.有一个重要原因:

信息论

信息理论中有一个称为香农熵的术语.(公平警告:该文章不容易通过.)快速版本是编码任何给定的信息块所需的最小位数.

该站点具有计算器,该计算器声称确定对给定文本进行无损编码所需的熵量(即,最小位数).我提供了这一块手工填充文字:

Meggings牧草苦豆腐,Wes Anderson食品卡车工艺啤酒iPhone.单一来源的咖啡情景独角鲸,mumblecore mlkshk牛仔短裤chia信托基金艺术派对你可能还没有听说过他们的苦涩.宝丽来工艺啤酒Intelligentsia,乙烯基Marfa Brooklyn umami.

假设int您的系统是32位,您只有32位空间来编码任何给定文件.但是上面的那个块 - 与我可能使用的相比,如战争与和平或美国法典 - 并不需要太长时间,如果你想要重建文本的任何希望,至少需要1472位进行编码.

(Commentor templatetypedef指向Kolmogorov复杂性(对该概念的另一个很好的解释),这是一种更好的方式来表示字符串的信息内容和破解哈希的无用.)

因此,从理论上讲信息(并留下作弊,如预先填写的压缩字典),就不可能从32位int中重构那些少数(简单的手工制作的本地源代码)句子.不幸的是,这是宇宙的基本定律.不会发生.

实例,来自代码

另一个评论家提到了Pigeonhole原则 - 一个简单的想法,如果你有N个插槽(在这种情况下是2 ^ 32),你不能在它们中放置超过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();

我想哈希两个文件:

mary had a little lamb

Mary Had A Little Lamb

他们的哈希值是多少？想一想.

(旁注:即使说了这么多,你也会溢出.:) 模块化算术是你的朋友,如果你想做那样的事情.)