Hash函数MD5攻击技术研究(15)

Hash函数MD5攻击技术研究

１２Ｈａｓｈ函数ＭＤ５攻击技术研究

在ＭＤ５的运算中，第３２位的位置既特殊又重要，其“＋＂和“．”在某种程度上是可以看成一致的。鉴于这一位的特殊性，可以将上面两个等式进行进一步扩展：

２ｋ＝２ｋ＋Ｉ．２ｋ：２ｋ＋２＿２ｋ＋１．２ｋ＝…＝２３１．２３０．２２９一 ．２ｋ

＝一（２３１＋２３０＋２２９＋…＋２ｋ）式（２．６）

．２ｋ＝．２ｋ＋１＋２ｋ＝．２ｋ＋２＋２“１＋２ｋ＝…＝．２３１＋２３０＋２２９－．．．＋２ｋ

＝（２３１＋２３０＋２２９一 ＋２ｋ）式（２．７）

为了便于分析，符号差分可以简化为如下的表示方式：

【ｋ】＝【ｋ＋１，－ｋ】＝【ｋ＋２，一（ｋ＋１），－ｋ】＝…＝Ｉｎ一１，－（ｎ一２）…－ｋ】

＝【３２，－３１－－＇，－ｋ】＝【一３２，－３１＂－，－ｋ】

【－ｋ】＝【－（ｋ＋１），ｋ】＝【－（ｋ＋２），（ｋ＋１），ｋ】＝…＝【－（ｎ一１），（ｎ－２）…ｋ】＝【－３２，３１…，ｋ】

＝【３２，３１…，ｋ】

另外，上面的差分扩展还可以将两个元素联合起来考虑：

【－＠＋２），ｋ】＝【－（ｋ＋２），（ｋ＋１），一ｋ】＝【－（ｋ＋１），－ｋ】＝【 （ｋ＋３），（ｋ＋２），（ｋ＋１），－ｋ】

＝【－（ｋ＋３），（ｋ＋２），ｋ】＝…

在模差分确定后，可以根据具体需要确定符号差分。

２．２．２循环左移的结果分析式（２－１０）式（２—９）式（２－８）符号差分扩展在ＭＤ５差分路径的控制上有着至关重要的作用，一般情况下，

ＭＤ５算法在运算过程中有大量的左循环移位，所以在引入差分之后，符号差分的左循环移位会出现几种不同的情况，需要分别进行分析处理。

例如，文献【２４】，设２。＝【ｋ＋ｘ， （１【＋ｘ－１），－－－，－ｋ］，其中１

数为ｓ（用＜＜＜ｓ表示），分三种情况讨论移位后的结果：

当ｋ＋ｘ＋ｓ＜３２，移位的结果为（２。＜＜＜ｓ）＝２“。；ｓｘ≤３２－ｋ，，设循环左移的位

当ｋ＋ｘ＋ｓ＞３２且ｋ＋ｘ＜３２，移位的结果为（２。＜＜＜ｓ）＝２ｍ＋１；

当ｋ＋ｘ＞３２，移位的结果为（２。＜＜＜ｓ）＝２。砝。

证明过程如下：

１．当ｋ＋ｘ＋ｓｓ３２时，．

（２。＜＜＜ｓ）＝【ｋ＋ｘ，一（ｋ＋ｘ一１），－（ｋ＋ｘ一２，…），－ｋ，】＜＜＜ｓ

＝【ｋ＋ｘ＋ｓ，．（ｋ＋ｘ＋ｓ．１），…，－（ｋ＋ｓ）】＝２ｋ＋５ｍｏｄ（２３２）

２．当ｋ＋ｘ＋ｓ＞３２且ｋ＋ｓ＜３２时，式（２．１１）

（２。＜＜＜ｓ）＝【ｋ＋ｘ，－（ｋ＋ｘ一１），一（ｋ＋ｘ ２，…），－ｋ，】＜＜＜ｓ

＝【－３２，＂－－，－（ｋ＋ｘ），ｋ＋ｘ＋ｓ－３２，一（ｋ＋ｘ＋ｓ一３２－１），…，一１］＝【３２，＂－，－（ｋ＋ｘ），ｋ＋ｘ＋ｓ一３２，一（ｋ＋ｘ＋ｓ－３２－１），…，一１］