8

我必须找到 2^25 个随机字符串的 SHA256 哈希。然后寻找冲突（对最后一个使用生日悖论，例如，仅 50 位散列）。

我将字符串：哈希对存储在 dict 变量中。然后使用值（不是键）对变量进行排序，然后使用 O(n) 循环查找冲突。

问题是因为有 2^25 个字符串和它们的 2^25 个哈希，所以 dict 变量中有 2^50 个值。这是非常耗费资源的。那么，我该如何在有限的 RAM（比如 1GB 左右）的情况下做到这一点？

我已经尝试过：
1. 使用 6GB 交换空间运行它。该程序运行了一夜，仍然没有完成。这基本上比 O(n_square) 搜索还要慢！哈希值是使用大约 3.2 GB 的 RAM 使用量计算的。但在那之后，当涉及到 sort 命令时，使用的 RAM 又开始猛增！我虽然 python 排序使用 In-Place-Quicksort :(
2。我只存储了哈希值并发现了一个冲突。但由于没有存储它而找不到相应的字符串。

我不应该使用数据库等。最多是一个文本文件，但这无济于事。另外，我对 Python 还是很陌生，但不要让这限制了你的答案水平。

PS：这是一个任务。一些人声称在 300MB RAM 的情况下不到一分钟就发现了冲突。不知道这是不是真的。我已经解决了这个问题，但答案是无法得到的！在工作中，所以现在无法访问代码。将很快添加。

代码：

from Crypto.Hash import SHA256
import os
import random
import string
from operator import itemgetter

def shaa():

    trun=[]
    clist={}
    for i in range(0,33554432):

        sha=SHA256.new(str(i)).hexdigest()
        sha=int(bin(int(sha,16))[-50:],2)
        clist[i]=sha

    print 'Hashes done.'

    clist=sorted(clist.items(), key=itemgetter(1))  
    for i in range(0,33554432):

        if(clist[i]==clist[i+1]):
            #print string[i],string[i+1]
            print clist[i]
            return 1
    return 2

result=2
while(result==2):
    result=shaa()
4

5 回答 5

3

我会去做这样的事情：

打开 16 个文件（以二进制模式打开应该没问题；如果所有字符串都具有相同的长度，这将是最简单的）。生成您的字符串和散列，并根据散列的前 4 位将它们写入文件。然后分别加载和处理每个文件。这将使内存使用量减少 16 倍。（当然，您可以使用任意数量的文件，只要您不会用完文件句柄。每次访问时必须打开和关闭每个文件会变得相当慢。）

如果生成字符串和散列相对便宜，您甚至不需要这些文件。只需执行 16 次传递，并且在每次传递中只保留与传递编号匹配的上半字节的哈希值。

于 2012-04-10T13:15:39.640 回答
2

2^25 解决这个问题的一种方法是使用一个非常长的位域，以便每个哈希都映射到位长内存块中的某个位置。

解决此类问题的更好但非 100% 保证的方式是通过布隆过滤器或其他概率数据结构完成。

布隆过滤器是一种节省空间的概率数据结构，用于测试元素是否是集合的成员。假阳性是可能的，但假阴性是不可能的；即查询返回“在集合内（可能是错误的）”或“绝对不在集合内”。

与其他用于表示集合的数据结构相比，布隆过滤器具有强大的空间优势，例如自平衡二叉搜索树、尝试、哈希表或条目的简单数组或链表。

具有 1% 错误的布隆过滤器每个元素只需要大约 9.6 位 — 无论元素的大小如何。

因此，每 2^25 个元素 9.6 位，只需要 38.4 MiB 的内存。

于 2012-04-10T13:28:08.870 回答
1

我认为这里的关键见解——我承认这让我回避了一段时间，直到几个小时后我才回来——是sha256hash digest是它自己的 hash。换句话说，您不必进行任何额外的散列或集合创建。您所要做的就是创建一个自定义哈希表，使用sha256摘要作为哈希。为了节省空间，不要存储字符串；只需创建一个位数组（对使用创建的整数数组中的整数使用移位操作table = numpy.zeros(table_size / bits_per_int + 1, dtype='i')）来检测冲突，然后将冲突字符串保存在 dict 中，将哈希映射到字符串以在第二遍中查找。

table_size应该是一个大素数——我选择了一个比 2 ** 31 稍大的素数，它构成了一个 268MB 的表——因为这会产生很少的新冲突/误报（由哈希的模运算引入）。您可以将字符串本身保存到可以迭代的文本文件中。

因此，对于任何字符串，要设置的相应位的索引将是index = int(hashlib.sha256('foo').hexdigest(), base=16) % table_size. 然后计算major_index = index / bits_in_intand minor_index = index % bits_in_int，使用移位和按位运算minor_index来检查 int at 中的正确位并将其存储table[major_index]，依此类推。

现在通过字符串。每当字符串生成映射到已设置位的哈希时，将一hash:string对存储在字典中。或者更好的是，存储一hash:[string_list]对，在多次冲突的情况下将新字符串附加到列表中。现在对于任何冲突的字符串对（a，b），字典将包含 b 的哈希值和值。然后对字符串进行第二次遍历，依次对每个字符串进行散列，并检查字典中的每个散列。如果哈希在字典中，并且字符串不在相应的列表中，则将字符串添加到列表中。字典中的某些字符串不会对应真正的碰撞；对于[string_list]大多数这些散列将只有一项长，而那些hash:[string_list]对可能会被丢弃。其他的可能是由散列函数本身产生的真正冲突，而不是来自模运算。但是，在同时存在真阳性和假阳性的情况下，您可能仍有一些误报需要清除；您必须仔细检查结果列表是否有误报。

BasicWolf的使用布隆过滤器的建议是一个很好的建议，并且可能会导致表格更小。但这增加了很多复杂性；我没有打扰。'0\n'我在以换行符结尾的字符串 from to上尝试了上述方法'33554431\n'，发现两个具有 54 位重叠的哈希。花了 11 分钟，最大内存使用量约为 350MB（尽管这可能会减少。）我做了一些分析，发现大部分时间都花在计算位表的偏移量上。在 c 中编码可能会显着提高速度，并且预散列和存储散列以及字符串也会有所帮助。

事实上，我尝试对字符串进行预散列处理，并用基于 c 的同名扩展模块中的a 替换了我相当numpy基于ad-hoc 的位数组。这将运行时间减少到 2 分钟多一点，同时将内存配置文件保持在 350MB 左右。bitarray

我认为足够接近政府工作。由于这是一项作业，我不会发布代码，但我很乐意提供额外的指针。

于 2012-04-10T19:47:14.663 回答
0

为什么不使用从最后 50 位哈希到字符串的字典？

于 2012-04-10T13:11:36.697 回答
0

例如，将散列拆分为 10 个字符为一组。并以这种方式嵌套值，您将进行递归搜索，但它应该更快

于 2012-04-10T13:12:06.253 回答