给定功能:
def md5(r, n):
i = 0
while i != n:
r = hashlib.md5(r[:9]).hexdigest()
i+=1
return r
结果:
md5("00000000000000000000000000000000", 0) #00000000000000000000000000000000
md5("00000000000000000000000000000000", 1) #4c93008615c2d041e33ebac605d14b5b
md5("00000000000000000000000000000000", 2) #c6246d2a39695fb74971b09ced30874f
md5("4c93008615c2d041e33ebac605d14b5b", 1) #c6246d2a39695fb74971b09ced30874f
md5("00000000000000000000000000000000", 2017) #57ab27ac3626d4565913485ff42b037b
有没有办法计算:
md5("00000000000000000000000000000000", 2017201720172017)
当然,不用先死。
md5("00000000000000000000000000000000", 20172017)
我需要 84 秒,所以 2017201720172017 是 100000001 倍。大约200万小时。
我不使用xrange
或range
因为值 2017201720172017 太大。
是的,但是有一台量子超级计算机。
我同意这个评论:
普朗克时间说一秒钟有 10 43个瞬间。
它的长度是 32,所以可以存在的MD5哈希数是:
假设每个散列花费一千个瞬间:
这意味着物理上可以在很短的时间内散列,但目前没有计算机这么快。让我们以 100 年为可接受的,有些人比这更长寿。所以我们做数学,100 年除以 16 32。
根据公历, 100年有3k 155 1 695 200秒。除以 16 32得出:
结果是 100,000 万亿秒,即 9 * 10 -30秒。
这是超级计算机检查每个哈希所需的时间,接受它可能需要 100 年。目前,一台普通计算机的每个哈希值大约为 10 -8,在整个人类的帮助下,这可能是可能的,或者也许在未来的时间里,不会太远。
亲爱的,在绞尽脑汁几天之后,我能够在不使用量子超级计算机的情况下得出结果。需要说明的是,这只是为了计算
md5("00000000000000000000000000000000", 2017201720172017)
由于前九个字符被用于下一次迭代,因此可能会在某个时候重复它们。保存并比较之前的结果,可以确定在迭代333399次之后,产生了已知结果60301次迭代的重复,即:
他们都给出相同的结果。
因此,我们开始计算:
(2017201720172017 - 333399) 模组 60301 = 45742
45742 的结果将是迭代 2017201720172017 在重复的 60301 的间隔中的偏移量。
然后:
因此不需要计算 2017201720172017 次迭代,而只需计算 379141。
在通用公式中,它会是这样的(我不是数学家):
r(i)=r((i - 333399) Mod 60301 + 333399)
前任:
r(401265) = r((401265 - 333399) Mod 60301 + 333399) = r(340964) r(74589651) = r((74589651 - 333399) Mod 60301 + 333399) = r(359120) r(201720172017) = r((201720172017 - 333399) Mod 60301 + 333399) = r(362302) r(20122017) = r((20122017 - 333399) Mod 60301 + 333399) = r(343289) r(2017201720172017) = r((2017201720172017 - 333399) Mod 60301 + 333399) = r(379141)
其中 i 是寻求的迭代并且 i >= 333399
r 是使用参数 "00000000000000000000000000000000" ei 调用 md5 函数的结果
前任:
r(401265) = md5("00000000000000000000000000000000", 401265) r(340964) = md5("00000000000000000000000000000000", 340964) r(2017201720172017) = md5("00000000000000000000000000000000", 201720172017) #Imposible de resolver r(379141) = md5("00000000000000000000000000000000", 379141) #Mismo resultado que el anterior
向所有人问好。
正如我在对自动回复的评论中指出的那样,我根本不清楚解决方案。经过深思熟虑,我被鼓励写这篇文章。
直截了当:是的。
如果我们分析问题中显示的示例代码
我们清楚地观察到,我们唯一感兴趣的是前 72 位(8 * 9)。此外,除了第一次,我们使用输出的前 72 位作为输入。
分析问题,我们可以这样改写:
反过来,可以将其重写为两个单独的问题:
给定一个由数据位组成的输入数据序列,在达到这 72 位的最大可能值之前
72
,该序列是否会有重复的元素?如果答案是肯定的,我们需要多少位才能确定找到第一个重复的元素?
所以,正如开膛手杰克所说,让我们分部分...
在达到 72 位限制之前会有重复吗?
从技术上讲,我们正在寻找的是摘要碰撞的存在与否。直接从上面的链接复制
为什么我们要寻找碰撞?非常简单。如果我们能够在 72 位的范围内,找到2 个产生与输出相同的 72 位的值,我们将不可避免地进入一个循环,从中无路可走。
回想一下,输出数据又被用作输入数据。一些假设的输出数据(它们是下一次迭代的输入):
可以观察到两者都
9
生成17
相同的输出(本例中为 4)。17
循环从那里开始。现在,在咨询了 MD5 的工作原理之后,我们来到了第一个绊脚石。虽然我们只使用 72 位,但该函数在内部使用 128 位。它提供相同大小的结果。
直觉告诉我们不会有冲突,因为输出的宽度大于输入。我们很快就会了解我们只使用 72 位的细节。其余数据(56 位)总是在所有输入上重复。有了这个,我们人为地限制了输出的宽度。出于实际目的,输出将仅包含72 位。
即便如此,是否存在重复仍不清楚。有必要更彻底地回顾一下MD5的内部,直到我们意识到一件事:
足够了。如果不为不同的输入数据获得重复输出,就不可能将 96 位映射到仅32位。即使我们混合不同的操作,也会发生信息丢失,并且肯定会有重复的输出。
因此,我们第一个问题的答案是:
现在,进入我们的第二个问题。
这种重复何时会发生?
哈希冲突的主题已被广泛研究;最著名的方法是
Ataque del cumpleaños
. 所述攻击是基于概率的;告诉我们,经过一定次数的尝试后,我们找到两个生成相同结果的输入数据的概率。不幸的是,我的数学知识并不是那么好。幸运的是,在前面的链接中,我们有一个表格。使用它,我们推断,对于 72 位数据,所需的试验次数,对于 50% 的概率,将介于
5.1 × 10^9
和之间2.2 × 10^19
。正如我们所看到的,一个不小的数字。现在,考虑到我们谈论的是概率,我们第二个问题的答案有点不精确:
因此,原始问题的答案是否可以在合理的时间内完成?很好奇:
为什么有可能?
对于之前所说的关于
ataque del cumpleaños
. 我们谈论的是概率,而不是某些数据。我们有可能(尽管不太可能)在第二次迭代中循环(当然不是在第一次迭代中)。我们也有可能在最后一个循环中进入。
一旦卷被释放,我重申我的评论。虽然没有说明,但它具有作为练习的所有特征。选择这些特定数据的巧合是不太可能的。因此,我得出结论,它是 MD5 的一个已知特性,肯定是在它所经历的多次测试中发现的。