如何找到相同校验和的校验和?(面试问题)

如果你知道算法是如何工作的,可能会有一些聪明的数学方法来找到它(或者证明不存在)。

但由于我很懒,而且crc32只有2^32个值,所以我会强行执行它。在等待算法遍历所有的2^32值时,我会使用google和stack overflow来查找是否有人有解决方案。

如果是sha-1,md5和其他或多或少的密码安全算法,我会被那些设计这些算法的数学家吓倒,然后放弃。

编辑1: 残忍的强迫…到目前为止,我已经找到了一个;CC4FBB6A采用大端编码。可能还有更多。我检查了4种不同的编码:ascii大小写,二进制big-endian和little-endian。

编辑2: 残忍的暴力。结果如下:

CC4FBB6A(大端)
ffffffff(大端和小端)
32f3b737(大写ascii)

代码是 here . 我的超频C2Q6600需要1.5个小时才能运行。现在该程序是单线程的,但是很容易使它成为多线程的,这将提供良好的线性可伸缩性。

除了Jerry Coffin和Esko Luontola对一个不寻常的问题给出了很好的答案外,我还要补充一点:

数学上,我们寻找x,这样f(x)=x,其中f是校验和函数,x是数据本身。 因为校验和的输出是固定大小的,而我们要查找的输入是相同大小的, 不能保证这样的X存在! 很可能固定大小的每个输入值都与该大小的不同值相关。

编辑:您的问题没有指定校验和在文件中格式化的确切方式,所以我假设您指的是校验和的字节表示。当字符串、编码和格式化字符串开始播放时,事情变得更加复杂。

由于没有任何相反的具体指导,我将不存在的数据的校验和定义为不存在的校验和,因此创建一个空文件将满足要求。

另一种典型的方法是负校验和——即在数据写入一个值后,使整个文件(包括校验和)的校验和为零。在这种情况下,你写了一个0的校验和,它就全部解决了。

暴力。这是ADLER32,我以前没有实现过,也不麻烦测试,所以很可能是我弄糟了。不过,除非我做错了什么,否则我不会指望一个修正版的运行速度会明显减慢。

这假设32位校验和值被写入文件little endian(我没有找到它的固定点big endian):

#include <iostream>
#include <stdint.h>
#include <iomanip>

const int modulus = 65521;

void checkAllAdlers(uint32_t sofar, int depth, uint32_t a, uint32_t b) {
    if (depth == 4) {
        if ((b << 16) + a == sofar) {
            std::cout << "Got a fixed point: 0x" << 
                std::hex << std::setw(8) << std::setfill('0') << 
                sofar << "\n";
        }
        return;
    }
    for (uint32_t i = 0; i < 256; ++i) {
        uint32_t newa = a + i;
        if (newa >= modulus) newa -= modulus;
        uint32_t newb = b + a;
        if (newb >= modulus) newb -= modulus;

        checkAllAdlers(sofar + (i << (depth*8)), depth + 1, newa, newb);
    }
    return;
}

int main() {
    checkAllAdlers(0, 0, 1, 0);
}

输出:

$ g++     adler32fp.cpp   -o adler32fp -O3 && time ./adler32fp
Got a fixed point: 0x03fb01fe

real    0m31.215s
user    0m30.326s
sys     0m0.015s

[编辑:已经修复了几个错误,我对这段代码的正确性没有信心;-)不管怎样,你得到的想法是:一个32位校验和只使用一次输入的每个字节是非常便宜的暴力。校验和通常设计为计算速度快,而散列通常要慢得多,即使它们有表面上相似的效果。如果你的校验和是“2轮ADLER32”(意思是目标校验和是计算校验和然后计算校验和的结果),那么我的递归方法就没有那么大帮助了,在有一个公共前缀的输入之间会有比例上较小的共同点。MD5有4发,SHA-512有80发。]

残忍地强迫它。crc-32给出一个长度为8的字符串,其中包含a-f的数字和字母(换句话说,它是一个十六进制数)。尝试每种组合,给你16 ^八 =多种可能性。然后对每个可能性进行散列,看看它是否给出了原始字符串。

您可以尝试通过假设解决方案将每个字符的使用次数不超过两到三次来优化它,这可能会使它完成得更快。

如果你有权访问一个crc32实现,你也可以尝试打破算法,找到一个更快的解决方案,但我不知道你会怎么做。