哈希游戏- 哈希游戏平台- 哈希游戏官方网站

　　第8章Hash函数  Hash函数的定义 Hash函数H，也称为杂凑函数，是一个公开函数，将任意长度的消息M映射为较短的、固定长度的一个值H(M) H(M)称为杂凑值、消息摘要，为消息中所有bit的函数，提供了错误检测的能力 Hash函数与数字签名 Hash函数可以用于数字签名。将Hash函数用于数字签名的好处： （1）可以提高签名的速度； （2）可以不泄漏签名所对应的消息； （3）可以将对消息的签名变换与加密变换分开处理 此外，Hash函数还可以用于消息的完整性检测等方面 几个定义 给定一个消息x,如果寻找另外一个与x不同的消息y，使得H(x)=H(y)是计算上不可行的，则称H关于消息x是弱无碰撞的. 如果寻找两个不同的消息x和y，使得H(x)=H(y)在计算上是不可行的，则称H是强无碰撞的. 如果对于任意给定的z，寻找满足H(x)=z的消息x是计算上不可行的，则称H是单向的. Hash函数的性质 函数的输入可以是任意长，输出是固定长 已知x,求H(x)较为容易 H(x)是单向的 寻找两个不同的消息x,y，使得H(x)=H(y)是难解的 生日攻击 （第I类生日攻击）H有n个输出，H(x)是一个特定的输出，如果对H随机取k个输入，至少有一个y使H(y)=H(x)的概率为0.5时，k有多大？ H(y)=H(x)的概率为1/n，不等的概率为1-1/n.取k个值都不等的为[1-1/n]k.至少有一个等的概率为1－ [1-1/n]k，近似等于k/n。所以概率为0.5，k为n/2。 生日悖论 在一个会场参加会议的人中，问使参会人员中至少有两个同日生的概率超过0.5的参会人数至少多少？ t个人都不同时生日概率为 ，因此，至少有两人于同日生的概率为 解之，当t?23时，p0.5。对于n比特杂凑值的生日攻击，由上式可计算出，当进行2n/2次的选择明文攻击下成功的概率将超过0.63。 Hash函数MD5 MD5 Hash Algorithm 算法步骤(1)－分组填充 Ron Rivest于1990年提出MD-4杂凑算法。输入消息可任意长，压缩后输出为128bits。1992年改进为MD-5。 消息的填充 设x是一个消息，用二进制表示。M为由x生成的一个数组 M=M[0]M[1]……M[N-1] 其中M[i]是长度为32位的(0,1)序列，N=0(mod16).M[i]称为一个字。M按下述 算法由x生成： (1)d=(447-x)mod512 (2)令L为xmod264 的二进制表示，L的长度为64位。如果L的长度不足64位，则在L的左端添0补足. (3)M=x10dL 其中x表示x的长度，表示序列的连接。在M的构造中，首先在x的右端添 加一个1，然后填充尽可能多的0使其长度恰好位512的倍数减去64，最后64 位表示消息填充前长度的二进制表示.如果x的长度不小于264 ，则最后64位 为xmod264 的二进制表示。这样M的长度恰好为512的倍数。 算法步骤(2)－缓冲初始化 MD5从M开始产生一个128位的消息摘要： 每轮输出为128 bit，可用4个32bits字表示：A，B,C,D。初始存数以十六进制表示为 A B=89ABCDEF， C=FEDCBA98， D 算法步骤(3) -HMD5运算 对512 bit(16-字)组进行运算，Yq表示输入的第q组512 bit数据，在各轮中参加运算。 T[1,…,64]为64个元素表，分四组参与不同轮的计算。T[i]可用32 bit二元数表示，T是32 bit随机数源。 轮运算 MD-5是四轮运算，各轮逻辑函数不同。每轮又要进行16步迭代运算，4轮共需64步完成。每步完成 b ? b＋CLSS (a＋g(B,C,D)＋X[k]＋T[i]) 其中 a,b,c,d=缓存器中的四个字，按特定次序变化。 g=基本逻辑函数F, G, H, I中之一，算法的每一轮用其中之一。 MD5相对MD4所作的改进 1. 增加了第四轮； 2. 每一步均有唯一的加法常数； 3. 为减弱第二轮中函数G的对称性从(XY)(XZ)(YZ)变为(XZ)(Y(~Z))； 4. 第一步加上了上一步的结果，这将引起更快的雪崩效应； 5. 改变了第二轮和第三轮中访问消息子分组的次序，使其更不相似； 6. 近似优化了每一轮中的循环左移位移量以实现更快的雪崩效应。各轮的位移量互不相同。 MD-5的安全性 MD-5的输出为128-bit，若采用纯强力攻击寻找一个消息具有给定Hash值的计算困难性为2128，用每秒可试验1 000 000 000个消息的计算机需时1.07×1022年。 采用生日攻击法，寻找有相同Hash值的两个消息需要试验264个消息，易受第II类生日攻击。 差分攻击攻击MD-5单轮可以在合理的时间内找到具有相同杂凑值的两个不同的消息。但未能推广到4轮 SHA 算法 Secure Hash Algorithm 算法简介 美国NIST设计 1993年成为联邦信息处理标准(FIPS PUB 180) 基于MD4算法，与之非常类似。 输入为小于264比特长的任意消息 分组512bit长 输出160bit 算法描述 消息填充：与MD5完全相同 附加消息长度：64bit长度 缓冲区初始化 AB＝EFCDAB89 C＝98BADCFB DE＝C3D2E1F0 分组处理 SHA的压缩函数 A,B,C,D,E?(E+ft(B,C,D)+CLS5(A)+Wt+Kt),A,CLS30(B),C,D) SHA中基本逻辑函数定义 SHA分组处理所需的80个字的产生过程 * * 消息 100…0 64bit 消息长度 填充图样 L×512bit Kbit MDq ，128 Yq 512 A B C D 32 ABCD＂fF(ABCD,Yq,T[1…16]) A B C D ABCD＂fG(ABCD,Yq,T[17…32]) A B C D ABCD＂fH(ABCD,Yq,T[33…48]) A B C D ABCD＂fI(ABCD,Yq,T[49…64]) + + + + + ：mod 232 MD-5的一个 MDq+1 128 512-bit组的处理 A B C D A B C D + + + CLSS + + X[k] T[i] CLSs:循环左移s位。 X[k]:第q-512-bit组 的第k个32-bit字。 T[i]：矩阵T中第I个 32-bit字。 ＋：模232加法。 基本逻辑函数定义 MD0=IV（ABCD缓存器的初始矢量） MDq+1 =MDq+fI[Yq,fH[Yq,fG[Yq,fF[Yq,MDq]]]] MD=MDL—1（最终的杂凑值）。 MD5的数学表达式 可找到一个消息分组和两个相关的连接变量，使算法产生相同的输出，但还未能成功的推广到4轮。 对单个512比特长的消息分组已经成功的找出了碰撞，为推广到在有初值IV时整个消息运算该算法。 MD-5的安全性 模232加