Hash算法的设计与实现(基础)Word格式文档下载.doc
- 文档编号:468685
- 上传时间:2023-04-29
- 格式:DOC
- 页数:14
- 大小:112KB
Hash算法的设计与实现(基础)Word格式文档下载.doc
《Hash算法的设计与实现(基础)Word格式文档下载.doc》由会员分享,可在线阅读,更多相关《Hash算法的设计与实现(基础)Word格式文档下载.doc(14页珍藏版)》请在冰点文库上搜索。
F(X,Y,Z)=(X&
Y)|((~X)&
Z)
G(X,Y,Z)=(X&
Z)|(Y&
(~Z))
H(X,Y,Z)=X^Y^Z
I(X,Y,Z)=Y^(X|(~Z))
3)设Mj表示消息的第j个子分组(从0到15),<
<
s表示循环左移s位,则四种操作为:
FF(a,b,c,d,Mj,s,ti)表示a=b+((a+F(b,c,d)+Mj+ti)<
s)
GG(a,b,c,d,Mj,s,ti)表示a=b+((a+G(b,c,d)+Mj+ti)<
HH(a,b,c,d,Mj,s,ti)表示a=b+((a+H(b,c,d)+Mj+ti)<
II(a,b,c,d,Mj,s,ti)表示a=b+((a+I(b,c,d)+Mj+ti)<
4)四轮运算
第一轮
FF(a,b,c,d,M0,7,0xd76aa478)
FF(d,a,b,c,M1,12,0xe8c7b756)
FF(c,d,a,b,M2,17,0x242070db)
FF(b,c,d,a,M3,22,0xc1bdceee)
FF(a,b,c,d,M4,7,0xf57c0faf)
FF(d,a,b,c,M5,12,0x4787c62a)
FF(c,d,a,b,M6,17,0xa8304613)
FF(b,c,d,a,M7,22,0xfd469501)
FF(a,b,c,d,M8,7,0x698098d8)
FF(d,a,b,c,M9,12,0x8b44f7af)
FF(c,d,a,b,M10,17,0xffff5bb1)
FF(b,c,d,a,M11,22,0x895cd7be)
FF(a,b,c,d,M12,7,0x6b901122)
FF(d,a,b,c,M13,12,0xfd987193)
FF(c,d,a,b,M14,17,0xa679438e)
FF(b,c,d,a,M15,22,0x49b40821)
第二轮
GG(a,b,c,d,M1,5,0xf61e2562)
GG(d,a,b,c,M6,9,0xc040b340)
GG(c,d,a,b,M11,14,0x265e5a51)
GG(b,c,d,a,M0,20,0xe9b6c7aa)
GG(a,b,c,d,M5,5,0xd62f105d)
GG(d,a,b,c,M10,9,0x02441453)
GG(c,d,a,b,M15,14,0xd8a1e681)
GG(b,c,d,a,M4,20,0xe7d3fbc8)
GG(a,b,c,d,M9,5,0x21e1cde6)
GG(d,a,b,c,M14,9,0xc33707d6)
GG(c,d,a,b,M3,14,0xf4d50d87)
GG(b,c,d,a,M8,20,0x455a14ed)
GG(a,b,c,d,M13,5,0xa9e3e905)
GG(d,a,b,c,M2,9,0xfcefa3f8)
GG(c,d,a,b,M7,14,0x676f02d9)
GG(b,c,d,a,M12,20,0x8d2a4c8a)
第三轮
HH(a,b,c,d,M5,4,0xfffa3942)
HH(d,a,b,c,M8,11,0x8771f681)
HH(c,d,a,b,M11,16,0x6d9d6122)
HH(b,c,d,a,M14,23,0xfde5380c)
HH(a,b,c,d,M1,4,0xa4beea44)
HH(d,a,b,c,M4,11,0x4bdecfa9)
HH(c,d,a,b,M7,16,0xf6bb4b60)
HH(b,c,d,a,M10,23,0xbebfbc70)
HH(a,b,c,d,M13,4,0x289b7ec6)
HH(d,a,b,c,M0,11,0xeaa127fa)
HH(c,d,a,b,M3,16,0xd4ef3085)
HH(b,c,d,a,M6,23,0x04881d05)
HH(a,b,c,d,M9,4,0xd9d4d039)
HH(d,a,b,c,M12,11,0xe6db99e5)
HH(c,d,a,b,M15,16,0x1fa27cf8)
HH(b,c,d,a,M2,23,0xc4ac5665)
第四轮
Ⅱ(a,b,c,d,M0,6,0xf4292244)
Ⅱ(d,a,b,c,M7,10,0x432aff97)
Ⅱ(c,d,a,b,M14,15,0xab9423a7)
Ⅱ(b,c,d,a,M5,21,0xfc93a039)
Ⅱ(a,b,c,d,M12,6,0x655b59c3)
Ⅱ(d,a,b,c,M3,10,0x8f0ccc92)
Ⅱ(c,d,a,b,M10,15,0xffeff47d)
Ⅱ(b,c,d,a,M1,21,0x85845dd1)
Ⅱ(a,b,c,d,M8,6,0x6fa87e4f)
Ⅱ(d,a,b,c,M15,10,0xfe2ce6e0)
Ⅱ(c,d,a,b,M6,15,0xa3014314)
Ⅱ(b,c,d,a,M13,21,0x4e0811a1)
Ⅱ(a,b,c,d,M4,6,0xf7537e82)
Ⅱ(d,a,b,c,M11,10,0xbd3af235)
Ⅱ(c,d,a,b,M2,15,0x2ad7d2bb)
Ⅱ(b,c,d,a,M9,21,0xeb86d391)
5)所有这些完成之后,将A、B、C、D分别加上a、b、c、d。
然后用下一分组数据继续运行算法,最后的输出是A、B、C和D的级联。
SHA1:
在SHA1算法中,我们必须把原始消息(字符串,文件等)转换成位字符串。
SHA1算法只接受位作为输入。
假设我们对字符串“abc”产生消息摘要。
首先,我们将它转换成位字符串如下:
011000010110001001100011
―――――――――――――
‘a’=97
‘b’=98
‘c’=99
第一步补位:
消息必须进行补位,以使其长度在对512取模以后的余数是448。
也就是说,(补位后的消息长度)%512=448。
即使长度已经满足对512取模后余数是448,补位也必须要进行。
补位是这样进行的:
先补一个1,然后再补0,直到长度满足对512取模后余数是448。
总而言之,补位是至少补一位,最多补512位。
还是以前面的“abc”为例显示补位的过程。
原始信息:
补位第一步:
0110000101100010011000111(补一个“1”)
补位第二步:
01100001011000100110001110…..0(补423个“0”)
我们可以把最后补位完成后的数据用16进制写成下面的样子
61626380000000000000000000000000
00000000000000000000000000000000
0000000000000000
现在,数据的长度是448了,我们可以进行下一步操作。
第二步补长度:
所谓的补长度是将原始数据的长度补到已经进行了补位操作的消息后面。
通常用一个64位的数据来表示原始消息的长度。
如果消息长度不大于2^64,那么第一个字就是0。
在进行了补长度的操作以后,整个消息就变成下面这样了(16进制格式)
00000000000000000000000000000018
如果原始的消息长度超过了512,我们需要将它补成512的倍数。
然后我们把整个消息分成一个一个512位的数据块,分别处理每一个数据块,从而得到消息摘要。
第三步使用的常量:
一系列的常量字K(0),K
(1),...,K(79),如果以16进制给出。
它们如下:
Kt
=0x5A827999
(0<
=t<
=19)
=0x6ED9EBA1(20<
=39)
=0x8F1BBCDC(40<
=59)
=0xCA62C1D6(60<
=79).
第四步
1)需要使用的函数:
在SHA1中我们需要一系列的函数。
每个函数ft
(0<
=79)都操作32位字B,C,D并且产生32位字作为输出。
ft(B,C,D)可以如下定义
ft(B,C,D)=(BANDC)or((NOTB)ANDD)(0<
ft(B,C,D)=BXORCXORD
(20<
ft(B,C,D)=(BANDC)or(BANDD)or(CANDD)(40<
(60<
2)计算消息摘要
必须使用进行了补位和补长度后的消息来计算消息摘要。
计算需要两个缓冲区,每个都由5个32位的字组成,还需要一个80个32位字的缓冲区。
第一个5个字的缓冲区被标识为A,B,C,D,E。
第一个5个字的缓冲区被标识为H0,
H1,H2,H3,H4。
80个字的缓冲区被标识为W0,W1,...,W79另外还需要一个一个字的TEMP缓冲区。
为了产生消息摘要,在第4部分中定义的16个字的数据块M1,M2,...,Mn会依次进行处理,处理每个数据块Mi
包含80个步骤。
在处理每个数据块之前,缓冲区{Hi}
被初始化为下面的值(16进制)
H0
=0x67452301
H1
=0xEFCDAB89
H2
=0x98BADCFE
H3
=0x10325476
H4
=0xC3D2E1F0.
现在开始处理M1,M2,...,Mn。
为了处理
Mi,需要进行下面的步骤
(1).
将
Mi
分成
16
个字
W0,W1,...,W15,
W0
是最左边的字
(2).
对于
t=16
到
79
令
Wt
=S1(Wt-3
XORWt-8
XORWt-14
XORWt-16).
(3).
A=H0,B=H1,C=H2,D=H3,E=H4.
(4)
t=0
79,执行下面的循环
TEMP=S5(A)+ft(B,C,D)+E+Wt
+Kt;
E=D;
D=C;
C=S30(B);
B=A;
A=TEMP;
(5).
=H0
+A,H1
=H1
+B,H2
=H2
+C,H3
=H3
+D,H4
=H4
+E.
在处理完所有的
Mn,
后,消息摘要是一个160位的字符串,以下面的顺序标识H0
H4.
五、功能描述与模块划分
功能描述:
采用hash算法(包括MD5及SHA-1两种)计算明文摘要。
模块划分:
分为两大块及MD5部分和SHA1部分。
四个线性函数:
inlineMD5:
:
uint4MD5:
F(uint4x,uint4y,uint4z)
{return(x&
y)|((~x)&
z);
}
消息子分组表示循环左移s位:
rotate_left(uint4x,intn)
{return(x<
n)|(x>
>
(32-n));
四轮运算:
inlinevoidMD5:
FF(uint4&
a,uint4b,uint4c,uint4d,uint4x,uint4s,uint4ac)
{a=rotate_left(a+F(b,c,d)+x+ac,s)+b;
初始化:
voidMD5:
init()将当前的有效信息的长度设成0,初始化链接变量
把字符形式的缓冲区中的数据copy到4字节的整数中(即以整数形式保存):
decode(uint4output[],constuint1input[],size_typelen)
将4字节的整数copy到字符形式的缓冲区中:
encode(uint1output[],constuint4input[],size_typelen)
对512bits信息(即block缓冲区)进行一次处理,每次处理包括四轮:
transform(constuint1block[blocksize])
填充:
update(constunsignedcharinput[],size_typelength)
返回十六进制表示的字符串:
std:
stringMD5:
hexdigest()const
voidSHA1:
SHAInit()
补充长度:
AddDataLen(intnDealDataLen)
轮运算:
ProcessMessageBlock()
PadMessage()
循环移位:
unsignedSHA1:
CircularShift(intbits,unsignedword)
六、核心代码
PartA-1:
md5.h
#ifndefBZF_MD5_H
#defineBZF_MD5_H
#include<
string>
iostream>
classMD5
{
public:
typedefunsignedintsize_type;
MD5();
MD5(conststd:
string&
text);
voidupdate(constunsignedchar*buf,size_typelength);
voidupdate(constchar*buf,size_typelength);
MD5&
finalize();
std:
stringhexdigest()const;
stringmd5()const;
friendstd:
ostream&
operator<
(std:
MD5md5);
private:
voidinit();
typedefunsignedcharuint1;
typedefunsignedintuint4;
enum{blocksize=64};
voidtransform(constuint1block[blocksize]);
staticvoiddecode(uint4output[],constuint1input[],size_typelen);
staticvoidencode(uint1output[],constuint4input[],size_typelen);
boolfinalized;
uint1buffer[blocksize];
uint4count[2];
uint4state[4];
uint1digest[16];
staticinlineuint4F(uint4x,uint4y,uint4z);
staticinlineuint4G(uint4x,uint4y,uint4z);
staticinlineuint4H(uint4x,uint4y,uint4z);
staticinlineuint4I(uint4x,uint4y,uint4z);
staticinlineuint4rotate_left(uint4x,intn);
staticinlinevoidFF(uint4&
a,uint4b,uint4c,uint4d,uint4x,uint4s,uint4ac);
staticinlinevoidGG(uint4&
staticinlinevoidHH(uint4&
staticinlinevoidII(uint4&
};
#endif
PartA-2:
md5.cpp
#include"
md5.h"
stdio.h>
string.h>
usingnamespacestd;
#defineS117
#defineS1212
#defineS1317
#defineS1422
#defineS215
#defineS229
#defineS2314
#defineS2420
#defineS314
#defineS3211
#defineS3316
#defineS3423
#defineS416
#defineS4210
#defineS4315
#defineS4421
G(uint4x,uint4y,uint4z)
{return(x&
z)|(y&
~z);
H(uint4x,uint4y,uint4z)
{returnx^y^z;
I(uint4x,uint4y,uint4z)
{returny^(x|~z);
GG(uint4&
{a=rotate_left(a+G(b,c,d)+x+ac,s)+b;
HH(uint4&
{a=rotate_left(a+H(b,c,d)+x+ac,s)+b;
II(uint4&
{a=rotate_left(a+I(b,c,d)+x+ac,s)+b;
MD5:
MD5()
{init();
MD5(conststd:
string&
text)
init();
update(text.c_str(),text.length());
finali
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- Hash 算法 设计 实现 基础