MD5实现

Question

作为一个个人项目，我想在FPGA上实现MD5，但我对实现的细节有一些疑问。算法实现的第一个来源是RFC 1321，其中有一个伪代码，它解释了第1轮将以下列方式执行：

 /* Round 1. */
 /* Let [abcd k s i] denote the operation
      a = b + ((a + F(b,c,d) + X[k] + T[i]) <<< s). */
 /* Do the following 16 operations. */
 [ABCD  0  7  1]  [DABC  1 12  2]  [CDAB  2 17  3]  [BCDA  3 22  4]
 [ABCD  4  7  5]  [DABC  5 12  6]  [CDAB  6 17  7]  [BCDA  7 22  8]
 [ABCD  8  7  9]  [DABC  9 12 10]  [CDAB 10 17 11]  [BCDA 11 22 12]
 [ABCD 12  7 13]  [DABC 13 12 14]  [CDAB 14 17 15]  [BCDA 15 22 16]

好的。当然可以。它打破了我的梦想，能够并行化算法，因为在每个步骤中，一个变量(A、B、C或D)被更新，每个步骤都需要前面的值。

因此，我在一本书的这一章中找到了一些并行化算法的方法：

哈希函数的硬件实现

第31(5)页表2.1给出了该算法的另一个公式。当然，这是相似的，但不是一样的。根据这本书，唯一更新的值是B。显然，这与RFC 1321中看到的原始实现不一样。

我的问题是：

• 这是具有完全相同结果的原始实现的另一种形式吗？(我想是这样，但由于这本书没有解释导致方程的步骤，所以我想确定)
• 这些新的方程式是如何推导出来的？

Answer 1

RFC 1321中的描述是正确的。图书样本中的那个也是如此。差额相当于符号。书中所指出的A，B，C，D相当于RFC 1321中S一世符号的第一、第二、第三和第四个参数，以及这个问题。

这本书在每一轮中都使用相同的变量。RFC的可变访问模式是不同的，每一轮节省三次32位分配，这将在软件中产生相当大的成本。详细说明(以下为评论)：

1. 从本书的A,B,C,D开始，与RFC的A、B、C、D匹配，在第一步中注意到[ABCD 0 7 1] (在RFC中)
   • 本书将前D移至新A，前C移至新D，前B移至新C，计算B_\text{new}并将其分配给新B。
   • RFC计算与RFC注意到的B_\text{new}相同的值a，将其分配给A，并保持B、C和D不变。

2. 现在，本书的A,B,C,D与RFC的D、A、B、C相匹配，在第二步中注意到了RFC 中的[DABC 1 12 2]
   • 本书将前D移至新A，前C移至新D，前B移至新C，计算B_\text{new}并将其分配给新B。
   • RFC计算与RFC注意到的B_\text{new}相同的值a，将其分配给D，并保持A、B和C不变。

此时，本书的A,B,C,D与RFC的C、D、A、B相匹配。

每一步的旋转都在继续。经过步骤i与i倍数的4，包括在最后一轮，书的A,B,C,D匹配RFC的A，B，C，D。

我所知道的MD5中唯一的变化是32位单词中的字节顺序错误。这种情况发生在第一次发布MD5冲突上，很快就得到了纠正。