单向散列函数算法Hash算法一种将任意长度的消息压缩到某一.docx
《单向散列函数算法Hash算法一种将任意长度的消息压缩到某一.docx》由会员分享,可在线阅读,更多相关《单向散列函数算法Hash算法一种将任意长度的消息压缩到某一.docx(23页珍藏版)》请在冰点文库上搜索。
单向散列函数算法Hash算法一种将任意长度的消息压缩到某一
单向散列函数算法(Hash算法):
一种将任意长度的消息压缩到某一固定长度(消息摘要)的函数(过程不可逆),常见的单向散列算法有MD5,SHA.RIPE-MD,HAVAL,N-Hash
由于Hash函数的为不可逆算法,所以软件智能使用Hash函数作为一个加密的中间步骤
MD5算法:
即为消息摘要算法(MessageDigestAlgorithm),对输入的任意长度的消息进行预算,产生一个128位的消息摘要
简易过程:
1、数据填充..即填出消息使得其长度与448(mod512)同余,也就是说长度比512要小64位(为什么数据长度本身已经满足却仍然需要填充?
直接填充一个整数倍)
填充方法是附一个1在后面,然后用0来填充..
2、添加长度..在上述结果之后附加64位的消息长度,使得最终消息的长度正好是512的倍数..
3、初始化变量..用到4个变量来计算消息长度(即4轮运算),设4个变量分别为A,B,C,D(全部为32位寄存器)A=1234567H,B=89abcdefH,C=fedcba98H,D=7654321H
4、数据处理..首先进行分组,以512位为一个单位,以单位来处理消息..
首先定义4个辅助函数,以3个32为双字作为输入,输出一个32为双字
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))
其中,^是异或操作
这4轮变换是对进入主循环的512为消息分组的16个32位字分别进行如下操作:
(重点)将A,B,C,D的副本a,b,c,d中的3个经F,G,H,I运算后的结果与第四个相加,再加上32位字和一个32位字的加法常数(所用的加法常数由这样一张表T[i]定义,期中i为1至64之中的值,T[i]等于4294967296乘以abs(sin(i))所得结果的整数部分)(什么是加法常数),并将所得之值循环左移若干位(若干位是随机的?
?
),最后将所得结果加上a,b,c,d之一(这个之一也是随机的?
)(一轮运算中这个之一是有规律的递增的..如下运算式),并回送至A,B,C,D,由此完成一次循环。
(这个循环式对4个变量值进行计算还是对数据进行变换?
?
)
Fori=0toN/16do
Forj=0to15do
SetX[i]toM[i*16+j]
End
AA=A
BB=B
CC=C
DD=D
//第一轮,令[ABCDKSI]表示下面的操作:
//A=B+((A+F(B,C,D)+X[K]+T[I])<<
//做如下16次操作
[ABCD071]
[DABC1122]
[CDAB2173]
[BCDA3224]
[ABCD475]
[DABC5126]
[CDAB6177]
[BCDA7228]
[ABCD879]
….有一共16次
//第二轮,令[ABCDKSI]表示如下操作
//A=B+((A+G(B,C,D)+X[K]+T[I])<<
//操作循环16次
[ABCD1517]
[DABC6918]
[CDAB111419]
[BCDA02020]
[ABCD5521]
[DABC10922]
[CDAB151423]
..进行有规律的16运算
//第三轮,令[ABCDKSI]表示如下操作
//A=B+((A+H(B,C,D)+X[K]+T[I])<<
//做如下16次操作
[ABCD5433]
[DABC81134]
[CDAB111635]
[BCDA142336]
//第四轮,令[ABCDKSI]表示如下运算
//A=B+((A+I(B,C,D)+X[K]+T[I])<<
//做如下16次运算..
[ABCD0649]
[DABC71050]
[CDAB141551]
[BCDA52152]
然后做如下加法运算…
A=A+AA
B=B+BB
C=C+CC
D=D+DD
END
当所有的512位分组运算完毕后,ABCD的级联将被输出成为MD5散列结果
SHA算法
即安全散列算法(SecureHashAlgorithm),有SHA-1,SHA-256,SHA-384和SHA-512几种
分别产生160位,256位,384位和512位的散列值
简易过程:
1、消息分组和填充方式与MD5相同
2、使用了f0,f1,…,f79这样一个逻辑函数序列,每一个ft(0<=t<=79)对3个32位的双字B,C,D进行操作,产生一个32位双字的输出。
Ft(B,C,D)定义如下:
Ft(B,C,D)=(B&C)|((~B)&D)0<=t=19
Ft(B,C,D)=B^C^D20<=t<=39
Ft(B,C,D)=(B&C)|(B&D)|(C&D)40<=t<=59
Ft(B,C,D)=B^C^D60<=t<=79
在C语言中常用宏定义进行初始化
同样SHA-1也使用了一系列的常数K(0),K
(1),….,K(79)).用十六进制表示就是
Kt=5A8279990<=t<=19
Kt=6ED9EBA120<=t<=39
Kt=8F1BBCDC40<=t<=59
Kt=CA62C1D660<=t<=79(为什么用这些常数进行初始化?
?
范围是怎么回事?
?
)
SHA-1产生160位的消息摘要
对称加密算法
对称加密算法的加密密钥和解密密钥是完全相同的..
安全性主要依赖于---1.加密算大必须是足够强(其中有依赖于数学问题),可以抵御各种类型的攻击..2.加密的安全性依赖于密钥的秘密性,而不是保密性..
常见的对称分组加密算法有DES(DataEncryptionStandard)(数据加密标准),IDEA(InternationalDataEncryptionAlgorithm)(国际数据加密算法),AES(AdvancedEncryptionStandard)(改进加密标准),BlowFish,Twofish,TEA,流密码RC4
RC4流密码
为现在最为流行的流密码,应用于SSL(SecureSockesLayer)(安全套接层),WEP
简易原理:
生成一种称为密钥流的伪随机流(伪在这里表示有规律之意)同明文通过异或操作相混合以达到加密的目的,解密时,同密文进行异或操作。
其密钥流由两部分组成:
:
KSA和PRGA
1,KSA(theKey-SchedulingAlgorithm)(密钥调度算法)
首先使用KSA来完成对大小为256的字节数组S(这个字节数组是什么?
?
是要加密的消息么?
?
)的初始化及替换,在替换时使用密钥,密钥长度一般取5-16字节,即40-128位,首先用0-255初始化数组S,然后使用密钥进行替换,伪代码如下:
Fori=0to255do
S[i]=i;
j:
=0;
Fori=0to255do
j:
=(j+S[i]+key[imodkeylength])mod256;//重复使用密钥
swap(S[i],S[j]);
2,PRGA(thePseudo-RandomGenerationAlgorithm)(伪随机流产生算法)
数组S在完成初始化之后,输入密钥便不再使用。
密钥流的生成是从S[0]到S[255],对每个S[i],根据当前S的值,将S[i]与S中的另一字节置换。
当S[255]完成转换后,操作继续重复执行(不明白!
!
)
得到子密码K用以和明文进行XOR运算,得到密文,解密方法相同…
3,弱点:
因为RC4加密所用的是XOR,所以一旦子密钥序列出现了重复,密文就可能被破解(为什么出现重复就容易被破解?
?
因为异或运算可逆?
?
这的重复是指什么?
?
相同的子密钥?
?
)
RC4产生一个伪随机比特流(akeystream),加密的时候,把它跟明文进行比特级别的异或处理,解密时进行一样的步骤(因为异或操作是对称的)。
(这个类似于Vernamcipher,只不过后者不使用伪随机比特流而直接使用随机比特流)。
为了产生keystream,本密码算法使用时需要两个数据的私有空间来保存内部状态:
1. 总共256个字节的序列(下面用“S"代替)
2. 两个8比特的索引指针(下面用“i”和“j”代替)
比特流序列的初始化是根据key的长度(key的长度通常在40到256比特之间),使用key-scheduling算法来进行的(KSA),一旦完成了初始化,比特流就可以根据伪随机生成算法(PRGA)来产生。
Thekey-schedulingalgorithm(KSA)
key-scheduling算法用来初始化数组“S”中的字节序列,“keylength”定义了key的字节长度,可能的范围是[1,256],典型的值是5到16之间,相应的key长度就是40-128比特。
首先,数组“S”被初始化成identitypermutation(身份鉴别的序列),随后在PRGA的算法中进行256为周期的循环列举出来,每次处理的方式都是一样的,是联合key的字节进行的。
for i from 0 to 255
S[i]:
=i
endfor
j:
=0
for i from 0 to 255
j:
=(j+S[i]+key[i mod keylength])mod256
swap(&S[i],&S[j])
endfor
伪随机生成算法(PRGA)
对于尽可能多的每个列举过程,PRGA算法修改内部的状态并输出keystream的一个字节。
在每次循环中,PRGA把i加一,并把i所指向的S值加到j上去,然后交换S[i]和S[j]的值,最后输出S[i]和S[j]的和(取256的模)对应的S值。
至多经过256次,S每个位置上的值都被交换一次。
i:
=0j:
=0
while GeneratingOutput:
i:
=(i+1)mod256
j:
=(j+S[i])mod256
swap(&S[i],&S[j])
outputS[(S[i]+S[j])mod256]
endwhile
TEA算法
全称TinyEncryptionAlgorithm(微型加密算法)
简易原理:
1,TEA分组长度为64位,密钥长度为128位。
采用Feistel网络(在BlowFish算法处有解释),作者推荐使用32次循环加密,即64轮,加密过程如下(其中K[0]-K[3]为密钥,v[0]-v[1]为待加密消息):
voidTEA_Encrypt(long*v,long*k)
{
Unsignedlongy=v[0],z=v[1],sum=0,delta=0x9e3779b9(密钥调服常数),n=32(循环次数);
while(n-->0)
{
sum+=delta;
y+=((z<<4)+k[0])^(z+sum)^((z>>5)+k[1]);
z+=((y<<4)+k[2])^(y+sum)^((y>>5)+k[3]);
}
v[0]=y;
v[1]=z;
}
其中,delta是由黄金分割得来的,解密算法是加密算法的逆过程..
2,弱点:
:
比如相关密钥攻击对其可以造成很大威胁,也提出了改进算法XTEA..
IDEA算法
IDEA(InternationalDataEncryptionAlgorithm)(国际数据加密算法)
简易原理:
1,分组密码IDEA明文和密文的分组长度为64位,密钥长度为128位。
特点是使用了3中不同的代数群(在代数几何中,一个代数群(或群簇)是一个群是一个代数簇,其簇之乘与逆由正则函数提供。
以范畴论描述,一个代数群是一个于代数簇范畴(数学)中的群对象)(还是不懂..囧!
!
)上的操作。
2,子密钥的产生:
IDEA共使用52个16位的子密钥,其由输入的128为密钥生成。
过程如下
●首先,输入的128位密钥被分成8个16位的分组,直接作为前8个子密钥。
●128位密钥循环左移25位,生成的新的128位密钥被重新分成8组16位的分组,作为后面的8个子密钥。
●重复上述步骤,直至52个子密钥全部生成。
(52个子密钥不是8的倍数,最后一次分组只分了4组,这样的话128位被分成4组,每组的数量就不同了..?
?
还是分组方式我理解错了?
?
)
3,加密算法:
IDEA的加密过程由8个相同的加密步骤(称为加密轮函数)和一个输出变换组成,过程如图(图看不懂!
!
):
4,过程:
首先,64位明文(明文在加密过程中呈什么形式?
?
是一些2进制数据?
?
为什么说是64位明文?
?
)(这里是因为IDEA加密算法对明文进行分组,即64位一组,以组为单位来处理数据)被分成4个16位分组,每一轮加密都需要6个子密钥,最后的输出变换需要4个子密钥,在第一轮加密中,4个16位的子密钥分别通过两个模216+1的乘法运算和两个模216的加法运算与明文进行混合,结果用两个16位的子密钥以及按位异或操作。
第一轮加密的结果,在进行部分交换后,作为第二轮加密的输入。
如此在重复进行7轮,在接下来的输出变换(OutputTransform)中,使用52个子密钥中的最后4个,通过模加和模乘运算与第八轮的结果进行混合,产生最后的密文..
5,IDEA解密算法:
过程同加密相同,不同之处在于:
:
使用的子密钥不相同,解密所使用的子密钥是加密的子密钥的相应于不同操作运算的逆元。
其次,解密时子密钥必须以相反的顺序使用。
IDEA中的加法与乘法逆元的规则定义如下:
X+addinv(x)=0(mod65535)
X*mulinv(x)=1(mod65537)
其中,模216+1的乘法逆元的计算可以使用欧几里得算法(查!
!
主要查这个算法是用来解决什么问题的。
。
。
)来求,代码如下:
Unsignedinv(unsignedxin)
{
Longn1,n2,q,r,b1,b2,t;
If(xin==0)b2=0;
Else
{
n1=maxim;n2=xin;b2=1;b1=0;
do{r=(n1%n2);q=(n1-r)/n2;
if(r==0){if(b2<0)b2=maxim+b2;}
else{n1=n2;n2=r;t=b2;b2=b1-q*b2;b1=t}
}while(r!
=0);
}
Return(unsigned)b2;
}
BlowFish算法
BIowFish算法是一个64位分组及可变密钥长度的分组密码算法。
简易原理:
BlowFish算法基于Feistel网络(Feistel网络是基于Shannon1945年的设计提出的,为现在正使用所有重要的分组密码都几乎沿用着这种结构,Feistel的思路是可以用乘积密码的概念来近似简单的代替密码。
乘积密码就是以某种方式连续执行两个或多个密码,以使所得到的“乘积”从密码编码的角度,比任意一个组成密码都强,特别是Feistel提出的用“代替”和“置换”交替的方式)(详细见文档)(替换/置换网络的典型代表),加密函数迭代执行16轮,分组长度为64位(这里长度为64位,不够是否要进行填充?
?
),密钥长度可以从32位到448位。
算法由两个部分组成:
密钥扩展部分和数据加密部分。
1,密钥扩展部分:
这部分将最长为448位的密钥转化成共4168字节长度的子密钥数组。
其中,数据加密由一个16轮的Feistel网络来完成。
每一轮由一个密钥相关置换和一个密钥与数据相关的替换组成,
2,子密钥:
BlowFish使用大量的子密钥。
这些密钥必须在进行加密前预计算产生。
●P数组由18个32位字的子密钥组成:
P1,P2,…,P18。
●4个8*32的包含总共1024个32位字的S-box(什么是S-box?
?
):
子密钥的扩展算法如下:
-1,按顺序使用常数
的小数部分初始化P数组和S-box。
比如:
P1=0x243f6a88
P2=0x85a308d3
-2,对P数组的密钥进行逐位异或,需要时重用密钥(什么事重用密钥?
?
什么时候才算是需要时?
?
)。
-3,使用当前的P数组和S-box对全0的64位分组(怎么会有全0的分组?
?
)使用BlowFish算法进行加密,用输出替代P1,P2。
-4,使用当前的P和S对第三部的输出进行加密,并用输出替代P3,P4。
-5,继续上面的过程,知道按顺序替代所有的P数组和S-box中的元素。
3,加密:
BlowFish是由16轮的Feistel网络组成的。
输入时一个64位的数据元素x,将x分成两个32位的部分,xL,xR。
加密算法的伪代码如下:
For(i=1;i<=16;i++)
{
xR[i]=xL[i-1]^P[i];
xL[i]=F(xR[i]^xR[i-1]);
}
xL[17]=xR[16]^P[18];
xR[17]=xL[16]^P[17];
其中函数F的输入时一个32位双字,共四个字节,分别作为4个S-box的索引(索引?
?
),取出相应的S-box的值,然后进行模232加运算。
解密与加密完全相同,只不过P1,P2,…P18以相反的顺序使用。
AES算法
AES(AdvandcedEncryptionStandard)(高级加密标准),是NIST(NationalInstituteofStandardsTechnology)(国家标准技术研究所)与1997年开始向世界范围内征集的加密算法,用于替代DES成为新一代的加密标准。
最终,由比利时密码学加JoanDaemen和VincentRijmen设计的Rijndael当选,实际上,Rijndael算法和AES的唯一区别在于各自所支持的分组长度和密码密钥长度的范围不同,Rijndael是具有可变分组长度和可变密钥长度的分组密码,其分组长度和密钥长度均可独立的设定为32比特的任意倍数,最小值为128bit,最大值为256bit。
。
AES将分组长度固定为128位,而且仅支持128,192,和256位的密钥长度,分别称作AES-128,AES-192,AES-256。
下面提到的AES算法专指FIPS-197(什么组织?
?
)中规定的AES算法。
1,基本术语:
(1),字节:
AES算法的基本处理单元叫字节,由八个比特序列组成,被看成一个整体,这些字节以有限域上的多项式(什么是有限域上的多项式?
?
)来表示
(2),状态(State):
AES的所有操作都是在一个称作状态的二维字节数组上进行的。
状态由4行字节组成,每行包括Nb个字节,Nb为分组长度除以32的值。
用s来表示状态,状态数组中的每个字节有两个坐标,行号r的范围为0<=r<4,列号c的范围为0<=c可用s[r,c]来应用状态中的每个字节。
在AES算法的加密和解密开始,输入字节数组in0,in1,…in15复制到状态中,然后对状态数组中的元素进行加解密操作,最后将结果复制到输出字节数组out0,out1,…out15,如图:
3,数学背景:
(1),加法:
有限域上的两个元素的画法运算是通过对相应的多项式中的相同次幂的系数进行相加来实现的。
其加法是模2的运算.也就是异或操作..
简易原理:
对于AES算法来讲,输入分组,输出分组及状态数组的长度都是128bit,即Nb=4,密钥K的长度为128,192或者256bit,用Nk=4,6或者8来表示。
加密或者解密函数所执行的轮数取决于密钥的长度。
轮数用Nr来表示,分别对应10,12,14。
1,加密过程:
先将输入复制待状态数组。
在进行一个初始轮密钥加操作(RoundKeyAddition)(这是什么操作?
?
)之后,执行Nr次轮函数对状态数组进行变换,其中最后一轮不同于前Nr-1轮。
最终的状态数组复制到输出即为最后的密文。
轮函数有4个部分组成,分别是Subytes(),ShiftRows(),MixColumns(),AddRoundKey(),加密算法的伪代码如下:
:
轮函数介绍:
1,SubBytes(),字节替换,实际上就是一个简单的查表操作。
AES定义了一个16*16的字节的S盒,以状态数组中的每个字节元素的高4位作为行标,低4位作为列标,取出相应的元素啊作为SubBytes()操作的结果。
S盒如下:
(这里X为行标,Y为列标)
按照此操作,将状态数组中的所有值都替换成S盒中对应的数值。
2,ShiftRows:
此操作规则是状态数组的第一行保持不变,第二行循环左移一个字节,第三行循环左移两个字节,第四行循环左移3个字节
3,MixColims:
MixColums操作是以列为单位,把状态中的每一列看做一个系数在(GF是什么?
)GF(28)上的四项多项式,然后乘以一个固定的多项式a(x),再模(x4+1).a(x)的定义如下:
a(x)={03}x3+{01}x2+{01}x+{02}
4,AddRoundKey():
此操作是将状态中的元素同轮密钥(论密钥是由用户输入的密钥通过密钥扩展过程生成的,同样可以看作一个状态数组)通过简单的异或运算相加。
密钥扩展(KeyExpansion):
密钥扩展算法通过对用户输入的128,192或者256位的密钥进行处理,共生成Nb(Nr+1)个32位双子,为加解密算法的论函数提供轮密钥。
其中,SubWord函数以一个4个字节的双字作为输入,然后对每个字节利用S盒进行替换作为输出。
函数RotWord以双字[a0,a1,a2,a3]作为输入,做循环左移操作,输出为[a1,a2,a3,a0]。
轮常量数组Rcon中的每一个元素Rcon[i]为一个32位双字,且低24位恒为0高8位,即一个字节按如下规则定义:
Rcon[1]=1,Rcon[i]=2*Rcon[i-1],乘法定义与GF(28)上,
解密过程:
解密过程的轮函数有4个部分组成InvShiftEows(),InvSubBytes(),InvMixColums(),AddRoundKey().
InvShiftRows是ShiftRows的逆过程,即相应的进行循环右移操作。
InvSubBytes是SubBytes的逆过程,AES同时也定义了一个逆S盒。
InvMixColums与MixColums的原理是相同的,不同的是使用了不同的多项式。
AddRoundKey的逆过程就是他本身,因为异或操作时其本身的逆
在加解密及逆向工程中,常见的AES算法的事项与上述的过程是不同的。
实际的软件实现采用了以空间换时间的方法,将轮函数的几个步骤合并为一组简单的查表操作。
DES算法
公开密钥加密算法(非对称加密算法)
对称加密算法的缺点在于一旦加解密密钥被获取,那么加密保护立即失效,1976年提出了公开密钥加密算法。
公钥加密算法加密与解密使用不同的密钥,加密所使用的叫做公钥,解密所使用的叫做私钥,任何人都可以使用公钥分配者分配的公开密钥对信息进行加密,但是