专利摘要

本发明属于信息安全领域，特别是密码学领域，涉及一种基于压缩函数的哈希函数的加固方法。该方法对hash函数的关键性环节进行加固，即对第一个分组和最后一个分组的压缩函数进行加固，针对现有hash函数大多数运算以单个bit为基础，增加多bit的运算，或者利用已有的安全分组密码算法。加固以抗击现有的差分密码分析等方法为主，同时考虑一些其他的攻击，比如第二原像攻击，在最后一个分组的压缩函数的输入中，还增加了一个输入变量，即所有分组信息的一个简单压缩。这种加固的方法的优势在于，在关键性的分组进行加固，随着明文长度的增加，计算量的增加不大，并且通过在最关键的位置设置破译障碍，可有效抗击原像攻击，碰撞攻击，第二原像攻击等。

说明书

技术领域

本发明属于信息安全领域，涉及一种基于压缩函数的单向哈希函数的构造方法。

背景技术

在2004年国际密码学大会上，王小云等人宣布的对于一系列Hash函数的碰撞结果，包括MD4, MD5, HAVAL-128和RIPEMD算法，其中可以找到MD4和 RIPEMD算法碰撞的复杂性分别低于2⁸和2¹⁸。王小云提出了一套新的针对MDx系列的Hash函数的分析技术，同时给出了得到满足差分路线充分条件的方法，以及如何使用明文修改技术来提高碰撞攻击的成功概率。2005年，王小云等应用此技术对MD5,  SHA-0 SHA-1算法进行碰撞攻击，取得了很好的效果，可以在现实中很快找到碰撞。这一攻击技术对现有的Hash函数提出了严峻的挑战，现有的好的设计方法需要进行进一步的改进。现有的hash函数是基于一种迭代的算法，其迭代所用的压缩函数是相同的，在这样的情况下可能存在一些攻击，比如碰撞攻击、原像攻击和第二原像攻击等。

发明内容

现有的hash（又译为哈希、杂凑、散列）函数主要有两大类，它们分别是以压缩函数和分组密码算法为基本计算单元的，以压缩函数构造的hash函数为例，它将明文消息进行一定的填充处理，然后对消息进行分组后，依次对每一个分组采用相同的压缩函数进行压缩，运算到最后一个分组后，得到hash值。这种设计结构简单，便于理解与实现，但是，却存在一定的不合理性：第一个分组和最后一个分组与中间分组采用相同的压缩函数，而第一个分组和最后一个分组的处理有特殊之处，第一个分组由于没有前面的压缩结果，所以需要一个确定的初始值参与运算，这个值是不变的，在密码分析的时候，没有选择的自由度，而最后一个分组包含一定的填充数据和关于消息长度的信息，具有较大的冗余度，并不像其他的分组的数据是完全自由、随机的（抛开明文的冗余度）。这样的冗余数据对于密码分析是不利的，因为对于密码分析者任何一个bit有选择性总比没有选择性好，而且，最后一个分组包含关于消息长度信息。因此，本发明考虑加固这两个分组。对这两个分组进行加强的理由有：第一，它们是比较难以破解的部分，对于hash函数的原像攻击是必须将每一个分组逆推出来，这样，加强最难的分组将会让破译难度更大。第二，它们是必须存在的分组，特殊的时候，第一个分组就是最后一个分组，而中间分组可能是不存在的，所以从这个角度，加强必需分组可增强安全性。第三，对于很长的明文，如果中间分组的运算量很大，则计算hash的运算量会很大，所以，中间分组的计算量应较小，这样中间分组与最前和最后分组不宜采用相同的压缩函数，中间分组采用相对简单，而最前和最后分组采用相对更为复杂的算法则更容易接受。第四，最后一个分组含有重要的信息，即关于明文长度的信息，如果可以随意破解这个分组，则分析者有可能任意设定伪造明文（碰撞消息）的长度，这对于破解是有利的，因为密码分析者可以根据自己的需要设定伪造明文的长度，选择更为有利的、最容易破译的长度，一般地，他可能会设定最短的，使得填充处理后的消息不超过一个分组长度，这样破译的工作量会较小。由于hash是多对一的映射，比如有的hash分组长度是512bit，hash值长度是128bit，即使设定消息的长度（对于一些hash明文消息长度的信息是64bit），对于一个确定的hash值，在该消息长度下平均而言也有大量的消息与这个hash值对应。由此可见，最后一个分组需要进行加固。第五，现有的一些hash分析大多数都是考虑两个明文分组或者单个明文分组的情况寻找碰撞，本设计的加固第一个分组和最后一个分组，使得这些hash分析无法绕过。

鉴于上面的分析，以及传统的hash函数的缺陷，本发明中考虑对第一个分组和最后一个分组进行加固，特别是最后一个分组应该采用有效加固方法：第一个分组采用加固的、比较安全的压缩函数F₁，中间分组采用通常的压缩函数F_z，最后一个分组采用加固的压缩函数F_n。最后一个分组的消息M_n的压缩函数进行特别处理，这个分组的压缩函数F_n增加了一个输入变量Y，Y是对所有明文分组进行压缩得到的，即Y=F_y（M₁,M₂,…,M_n），F_y为一个运算量较低的函数，也就是说最终hash值H_n=F_n（Y, M_n, H_n-1），增加压缩值Y作为输入变量的目的是防止利用中间压缩函数的脆弱性而实施碰撞攻击和第二原像攻击，为了减少计算Y的运算量，可以采用较为简单的函数，比如可以将所有的分组进行异或运算，或者简单的模加运算得到Y，当只有一个分组时，直接采用该分组作为Y。

加固的方法可以考虑现有hash函数的缺陷而进行，比如考虑现有的差分密码分析，可以在原有算法的基础上增加S盒或者其他抗差分分析部件，考虑现有hash函数大多数压缩都是bit级别的运算，增加多bit压缩的部件以防止比特跟踪，另外现有分组密码算法的设计已经非常安全、成熟，可以对于这两个分组采用基于对称算法的压缩方法，或者进行多重运算等等。考虑现有许多差分分析依赖的两个分组采用相同的算法，第一个和最后一个分组的压缩函数采用不同的结构，最后一个分组的压缩函数F_n可设计得更加复杂、更安全，两个分组重合时，选取最后一个分组的函数。 考虑到hash函数结构的简化，这两个分组的加固可以在中间分组的压缩函数的基础上增加一些运算，或者是采用多重的同一压缩函数的运算，特别考虑增加抗差分分析的部件。

附图说明

图1是本发明的hash迭代示意图。

具体实施方式

以下为实施例，以加固SHA-1为例。

 中间分组依然采用不太安全的SHA-1的压缩函数F_z，由于该函数已经很清楚，所以这里不再详述。第一个分组和最后一个分组采用不相同的加固的函数F₁和F_n。加固的算法和SHA-1一样是以压缩函数为基础，它有一个缓冲区存储运算160bit的中间结果和最终hash结果H_i，i是分组的次序，它的输入则是512bit的明文分组M_i和前一个分组的中间结果H_i-1，最后一个分组增加了一个输入Y。Hash的迭代过程可以表示如下：H₁=F₁（M₁，H₀），其中H₀为缓冲区初始值，H_i=F_i（M_i，H_i-1），其中i大于1小于n，H_n=F_n（Y，M_n，H_n-1），n为分组个数。

第一个分组压缩函数F₁的加固方法体现在消息分组输入和缓冲区中间运算结果的S盒替换和左循环移位两个方面：第一，在明文分组M₁进行S盒替换得到M_s，然后对得到的512bit的M_s整体进行左循环移位4bit得到M_s4，然后将M_s4作为函数F_ze的输入，其中F_ze为中间分组的压缩函数F_z的加固，H₁=F₁（M₁，H₀）= F_ze（M_s4，H₀），第二， F_ze函数是在原来的压缩函数F_z的基础上进行加固得到的函数，F_ze函数对F_z加固体现在F_z的20步和21步之间、40步和41步之间、60步和61步之间对缓冲区的结果先进行S盒替换，再进行左循环移位，SHA-1的压缩函数中间总共有80步迭代，加固体现在分别将20步、40步、60步得到的缓冲区的160bit的值采用S盒替换，替换后整体进行左循环移位12bit，得到的等长的160bit结果依然存储在缓冲区，参与下面的运算，S盒和左循环移位用于抗现有的一些hash分析，下面是对本实施例S盒的介绍：

S盒替换的单位为8bit，S盒替换采用运算步骤如下： 1）将消息分组以8bit为单位变换为GF（2⁸）上的乘法逆元，额外地，二进制00000000映射为00000000，2）对前面逆运算的结果采用仿射变换如下：

上面描述中采用的所有的S盒都同是上述的S盒，下面的S盒也是采用该S盒。

最后一个分组的加固方法除了采用S盒避免bit跟踪和差分分析，还采用变化的算法来防止对bit级别进行跟踪，防止通过确定算法列方程的方法进行原像攻击，由于最后一个函数的输入包括所有明文分组的压缩Y和最后一个分组M_n，在本实施例中，将这个压缩函数F_n用两个中间分组的压缩函数F_z为基础来进行加固， 这样便于算法实现，可以直接调用中间的压缩函数的类或库，减少了系统的复杂度。最后一个分组加固方法如下：

1）将明文的所有分组逐一进行异或运算，得到512bit的最终的压缩分组Y，即Y=M₁ xor M₂ xor …M_n-1 xor M_n。对Y采用上述S盒进行替换得到M_Y，采用的S盒同上。将M_Y的512bit划分为16bit的单元，将这些单元进行异或运算，得到的16bit的二进制数据，依次划分为2个8bit数据，其值为R₁和R₂。

2）对Y进行S盒替换的结果M_Y进行左循环移位R₁ bit得到M_Ym，对得到的二进制数据M_Ym采用压缩函数F_z压缩，缓冲区采用H_n-1，得到160bit的新的中间结果A_f=F_z（M_Ym，H_n-1）。

3）将M_n采用S盒替换后的消息M_ns再次左循环移位R₂ bit得到M_nsm，采用压缩函数F_z对M_nsm进行压缩，缓冲区的值采用前一步计算得到的A_f，运算得到这个分组的运算结果，也就是最终hash函数值H_n= F_z（M_nsm，A_f）。

一种加固的基于压缩函数的hash函数构造方法专利购买费用说明

Q：办理专利转让的流程及所需资料

A：专利权人变更需要办理著录项目变更手续，有代理机构的，变更手续应当由代理机构办理。

1：专利变更应当使用专利局统一制作的“著录项目变更申报书”提出。

2：按规定缴纳著录项目变更手续费。

3：同时提交相关证明文件原件。

4：专利权转移的，变更后的专利权人委托新专利代理机构的，应当提交变更后的全体专利申请人签字或者盖章的委托书。

Q:专利著录项目变更费用如何缴交

A：（1）直接到国家知识产权局受理大厅收费窗口缴纳,（2）通过代办处缴纳，（3）通过邮局或者银行汇款,更多缴纳方式

Q：专利转让变更，多久能出结果

A：著录项目变更请求书递交后，一般1-2个月左右就会收到通知，国家知识产权局会下达《转让手续合格通知书》。