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

Hash函数MD5攻击技术研究

第二章相关的基础知识

２．１．３移位和明文字顺序表

在对ＭＤ５算法进行碰撞攻击的过程中，必须考虑移位对整个差分路径的影响。在碰撞攻击过程中，明文字的编排顺序是差分引入的重要考虑因素之一；在原像攻击过程中，明文字的编排顺序很大程度上确定了初始结构和过渡结构的位置。

表２．４移位比特表

步骤

１，２……，１５

１６，１７……，３１

３２，３３……，４７

４８，４９……，６３７１２１７２２５９１４２０４１１１６２３６１０１５２ｌ移位比特数７１２１７２２５９１４２０４１１１６２３６１０１５２１７１２１７２２５９１４２０４１１１６２３６１０１５２１７１２１７２２５９１４２０４１１１６２３６１０１５２１

表２．５明文字顺序

步骤

１，２，……，１５

１６，１７，……，３１

３２，３３，……，４７

４８，４９，……，６３Ｏ１５Ｏ１６８７２１１１１１４３Ｏ１４５４５１１２５１０４３明文字的顺序６７１５７１０８４１０１９９１３８１０１４Ｏ１５１１３３６８６１３１２１３９４１３２１２１１１４７１５２１５１２２９

２．２ＭＤ５的差分分析

２．２．１三种差分的概念引入

差分分析是破译Ｈａｓｈ函数最有效的工具之一，其中涉及到异或差分、符号差分和模差分等几个重要的概念。

异或差分：设Ｘ和Ｘ’是两个３２位的数，其异或差分为两个数的比特位的异或运算，表示为ＸｏＸ’。异或差分能反映两个数的对应位的相同与否。

符号差分：同样，设Ｘ和Ｘ７是两个３２位的数，为了更好的体现这两个数的某一位的差别，在异或差分的基础上进一步引入符号差分“＋＂、“Ｉ＂号。例如，Ｘ’．Ｘ＝【５，６，７，８，＂－，－２７］，这说明Ｘ和Ｘ’从第５到第２７位都不同，而且从符号可以看出Ｘ的第５到第２６位是０，第２７位是１；而Ｘ７的第５到第２６位是１，第２７位是０。符号差分可以很容易看出两个数的各位的差别。

模差分：同样，设Ｘ和Ｘ’是两个３２位的数，模差分是将两个数的差别用整数减法体现出来。例如，Ｘ７．Ｘ用符号差分表示为【５，６，７，８，－＂，－２７］，此时用模差分表示为Ｘ７．Ｘ＝－２４。

符号差分的扩展在ＭＤ５算法破译过程中具有广泛的应用，利用符号差分的扩展，可以达到自己所需要的差分目标。例如，对２ｋ、．２ｋ可以进行如下扩展：

２ｋ＝２ｋ¨．２ｋ＝２ｋ＋２．２ｋ＋１－２ｋ＝＇＇＇＝２ｎ－ｌ＿２ｎ－２．２ｎ－３．．．．．２ｋ，其中０ｓｋ＜ｎｓ３２．２ｋ＝．２ｋ＋１＋２ｋ＝．２ｋ＋２＋２ｋ＋１＋２ｋ＝…＝．２ｎ～＋２ｎ＇２＋２ｎ－３．．． ＋２ｋ，其中０＜ｋ＜ｎ＂：３２