7

我正在做一个编程挑战，我对其中一个挑战感到疯狂。在挑战中，我需要计算字符串的 MD5。字符串以下列形式给出：

n[c]: 哪里n是数字，哪里是c字符。例如：b3[a2[c]]=>baccaccacc

一切都很顺利，直到我得到以下字符串：

1[2[3[4[5[6[7[8[9[10[11[12[13[a]]]]]]]]]]]]]

这个字符串变成了一个带有 6227020800 的字符串a。该字符串超过 6GB，因此几乎不可能在实际时间内计算出来。所以，这是我的问题：

我可以在这里使用 MD5 的任何属性吗？

我知道必须有一种形式可以在短时间内完成，并且我怀疑它必须与所有字符串具有重复多次的相同字符这一事实有关。

4

3 回答 3

3

您可能已经创建了一个（递归）函数来将结果生成为单个值。相反，您应该使用生成器将结果生成为字节流。然后，您可以将这些逐个字节输入到您的 MD5 哈希例程中。这样流的大小无关紧要，它只会影响计算时间，而不是使用的内存。

这是一个使用单遍解析器的示例：

import re, sys, md5

def p(s, pos, callBack):
  while pos < len(s):
    m = re.match(r'(d+)[', s[pos:])
    if m:  # repetition?
      number = m.group(1)
      for i in range(int(number)):
        endPos = p(s, pos+len(number)+1, callBack)
      pos = endPos
    elif s[pos] == ']':
      return pos + 1
    else:
      callBack(s[pos])
      pos += 1
  return pos + 1

digest = md5.new()
def feed(s):
  digest.update(s)
  sys.stdout.write(s)
  sys.stdout.flush()

end = p(sys.argv[1], 0, feed)
print
print "MD5:", digest.hexdigest()
print "finished parsing input at pos", end
于 2013-05-06T13:49:54.617 回答
0

所有散列函数都设计用于处理字节流，因此您不应该首先生成整个字符串，然后再对其进行散列 - 您应该编写生成器，它生成字符串数据块，并将其提供给 MD5 上下文。而且，MD5 使用 64 字节（或字符）缓冲区，因此最好将 64 字节的数据块提供给上下文。

于 2013-05-06T14:15:12.633 回答
0

利用哈希的良好特性：

import hashlib
cruncher = hashlib.md5()
chunk = 'a' * 100
for i in xrange(100000):
    cruncher.update(chunk)
print cruncher.hexdigest()

调整轮数 (x = 10000) 和块的长度 (y = 100)，使 x * y = 13!。关键是你正在用你的字符串块（每个 x 个字符长）一个接一个地为算法提供 y 次。

于 2013-05-06T14:25:38.067 回答