密码学课程设计报告

密码学课程设计报告班级：信安10-1班姓名：刘文学号：08103656指导老师：谢林目录1.Hash算法的实现—MD5算法 31.1算法概述 31.2算法原理及设计思想 31.3实现算法分析 31.4程序运行结果 41.5密码安全性分析 41.6设计实现中的问题及解决方法 42.AES算法的实现 42.1算法概述 42.2算法原理及设计思想 52.3程序主要代码分析 82.4程序运行结果 92.5安全性分析 92.6设计实现中的问题及解决方法 93.RSA算法的实现 .93.1算法概述 103.2算法原理及设计思想 103.3程序主要算法分析 103.4程序运行结果 113.5安全性分析 113.6设计实现中的问题及解决方法 11一、Hash算法的实现——MD5算法1.1算法概述MD5算法是一种消息摘要算法，此算法以任意长度的信息作为输入进行计算，产生一个128-bit(16-byte)的指纹或报文摘要。两个不同的message产生相同messagedigest的几率相当小，从一个给定的messagedigest逆向产生原始message更是困难(不过据说我国的某个教授很善于从messagedigest构造message)，因此MD5算法适合用在数字签名应用中。MD5实现简单，在32位的机器上运行速度也相当快，当然实际应用也不仅仅局限于数字签名。除了MD5以外，其中比较有名的还有sha-1、RIPEMD以及Haval等。1.2算法原理及设计思想MD5散列函数的处理过程分为如下几步：(1)消息填充：对原始消息填充，使得其比特长在模512下余448，即填充后消息的长度为512的某一倍数减64.这一步是必需的，即使原始消息的长度已经满足要求，仍需要填充。例如：消息的长度正好为448bit，则需要填充512bit，使其长度为960bit，因此填充的比特数在1到512之间。填充方式是固定的：第一位为1，其他位为0，例如需要填充100bit，则填充一个1和后面附上99个0。(2)添加消息长度：在第一步填充后，留有64个bit位，这64bit用来填充消息被填充前的长度。如果消息长度大于264，则以264取模。前两步完成以后，消息的长度为512的倍数（设倍数为L）。可将消息表示成分组长为512的一系列分组Y0，Y1，…Yl-1。每一个512bit分组是16个（32bit）字，因此消息中的总字数为N=16L。(3)初始化MD缓冲区：MD5算法使用128bit长的缓冲区以存储中间结果和最终Hash值。缓冲区可表示为4个32位长的寄存器（A，B，C，D），将存储器初始化为以下的32位整数：A=67452301、B=EFCDAB、C=98BADCFE、D=10325476.每个寄存器都以little-endian方式存储数据，也就是最低有效字节存储在低位地址字节位置，4个寄存器按如下存储：A=01234567，B=89ABCDEF，C=FEDCBA98,D=7654321(4)以分组为单位进行消息处理：每个分组Ya都经过一个压缩函数HMD5处理，包括4轮处理过程，MD5算法是一种迭代型Hash函数，压缩函数HMD5是算法的核心。压缩函数按如下方式工作：a.四个轮运算的结构相同，但各轮使用不同的基本逻辑函数，我们分别称之为F、G、H和I；b.每轮的输入时当前要处理的512位的分组Yq和128位缓冲区的当前值A、B、C、D的内容，输出仍然放在缓冲区中产生新的A、B、C、D；c.每轮的处理过程还需要使用常数表T中元素的1/4.第4轮的输出再与第1轮的输入CVq相加，相加时将CVq看作4个32bit的字，每个字与第4轮输出的对应的字按模232相加，相加的结果就是本轮压缩函数的输出。(5)输出：消息的所有L个分组被处理完以后，最后一个HMD5的输出即为产生的消息摘要（Hash值）。1.3实现算法分析(1)staticunsignedcharPADDING[64]说明：用于bits填充的缓冲区，要64个字节,因为当欲加密的信息的bits数被512除其余数为448时，需要填充的bits的最大值为512=64*8。(2)#defineF(x,y,z)(((x)&(y))|((~x)&(z)))#defineG(x,y,z)(((x)&(z))|((y)&(~z)))#defineH(x,y,z)((x)^(y)^(z))#defineI(x,y,z)((y)^((x)|(~z)))说明：这几个宏定义是md5算法规定的，就是对信息进行md5加密都要做的运算。F,G,HandI是基本的MD5算法。(3)#defineFF(a,b,c,d,x,s,ac)#defineGG(a,b,c,d,x,s,ac)#defineHH(a,b,c,d,x,s,ac)#defineII(a,b,c,d,x,s,ac)说明：四轮处理中每一轮的16步都是循环左移，移动的位数用s表示。(4)voidMD5Init(MD5_CTX*context)函数说明：初始化md5的结构。(5)voidMD5Update(MD5_CTX*context,unsignedchar*input,unsignedintinputLen)函数说明：将与加密的信息传递给md5结构，可以多次调用。context：初始化过了的md5结构input：欲加密的信息，可以任意长inputLen：指定input的长度(6)voidMD5Final(unsignedchardigest[16],MD5_CTX*context)函数说明：获取加密的最终结果。digest：保存最终的加密串context：你前面初始化并填入了信息的md5结构(7)staticvoidMD5Transform(UINT4state[4],unsignedcharblock[64])函数说明：对512bits信息(即block缓冲区)进行一次处理，每次处理包括四轮。state[4]：md5结构中的state[4]，用于保存对512bits信息加密的中间结果或者最终结果block[64]：欲加密的512bits信息(8)staticvoidEncode(unsignedchar*output,UINT4*input,unsignedintlen)函数说明：将4字节的整数copy到字符形式的缓冲区中。output：用于输出的字符缓冲区input：欲转换的四字节的整数形式的数组len：output缓冲区的长度，要求是4的整数倍(9)staticvoidDecode(UINT4*output,unsignedchar*input,unsignedintlen)函数说明：与上面的函数正好相反，这一个把字符形式的缓冲区中的数据copy到4字节的整数中（即以整数形式保存）。output：保存转换出的整数input：欲转换的字符缓冲区len：输入的字符缓冲区的长度，要求是4的整数倍1.4程序运行结果（1）源代码运行结果：1.5安全性分析MD5算法中，输出的每一位都是输入的每一位的函数，逻辑函数F、G、H、I的复杂迭代使得输出对输入的依赖非常小。但是，Berson已经证明，对单轮的MD5算法，利用差分密码分析，可以在合理时间内找出摘要相同的两条报文。MD5算法抗密码分析的能力较弱，对MD5的生日攻击所需代价是需要试验2^64个消息。2004年8月17日，在美国加州圣巴巴拉召开的美密会（Crypto2004）上，中国的王小云、冯登国、来学嘉、于红波4位学者宣布，利用差分分析只需1小时就可找出MD5的碰撞。1.6设计实现中的问题及解决方法（1）字符输入问题因为对于MD5的实现使用的是C语言而不是C++，所以在编写程序的时候由于对C的不熟悉出现了关于字符输入的问题。在最初的程序编写时，对字符输入没有使用scanf()函数，而是使用了gets()函数，但是后来发现gets()函数功能本身就不完善，容易出现溢出，所以后来就换成了更加稳定和实用的scanf()函数。（2）文件拖拽问题在设计的MD5程序中能够实现字符输入加密和文件读取加密两种功能，在文件读取中又分成了手动输入文件路径和拖拽文件至对话框自动获取文件路径两种方式，可是文件拖拽中会产生双引号，无法获取正确格式的文件路径，后来在CSDN上看到了一篇博客中提到了去除拖拽文件时出现的双引号的方法，后来被我引用到程序里并做了一些改动，便实现了去除双引号，程序代码如下：if(filename[0]==34)filename[strlen(filename)-1]=0,strcpy(filename,filename+1);//支持文件拖曳,但会多出双引号,这里是处理多余的双引号二、AES算法的实现2.1算法概述AES加密算法即密码学中的高级加密标准（AdvancedEncryptionStandard，AES），又称Rijndael加密法，是美国联邦政府采用的一种区块加密标准。这个标准用来替代原先的DES，已经被多方分析且广为全世界所使用。经过五年的甄选流程，高级加密标准由美国国家标准与技术研究院（NIST）于2001年11月26日发布于FIPSPUB197，并在2002年5月26日成为有效的标准。AES的基本要求是，采用对称分组密码体制，密钥长度的最少支持为128、192、256，分组长度128位，AES加密数据块大小最大是256bit，但是密钥大小在理论上没有上限。AES加密有很多轮的重复和变换。大致步骤如下：1、密钥扩展（KeyExpansion），2、初始轮（InitialRound），3、重复轮（Rounds），每一轮又包括：SubBytes、ShiftRows、MixColumns、AddRoundKey，4、最终轮（FinalRound），最终轮没有MixColumns。2.2算法原理及设计思想1、加密原理AES具有128bits的分组长度，三种可选的密钥长度，即128比特、192比特、256比特。AES是一个迭代型密码；轮数Nr依赖于密钥长度。如果密钥长度为128比特，则Nr=10；如果密钥长度为192比特，则Nr=12；如果密钥长度为256比特，则Nr=14。首先，AES的总体描述如下：1、给定一个明文x，将state初始化为x，并进行AddRoundKey操作，将RoundKey与state进行异或操作。2、对前Nr-1轮中的每一轮，用S盒对state进行一次代换操作，称为SubBytes；对state做一置换ShiftRows；再对State做一次MixColumns操作；然后进行AddRoundKey操作。3、依次进行SubBytes、ShiftRows和AddRoundKey操作。4、将state定义为密文y。从上述总体描述中，我们可以看到AES与我们所熟知的SPN在许多方面均有相似之处。在这两种密码体制的每一轮中，都要进行轮密钥混合、代换和置换。这两个密码都包括白化过程，而AES更“大”一些，它还在每一轮中包括一个额外的线性变换MixColumns。2、解密原理为了解密，只需将所有的操作逆序进行，并逆序使用密钥编排方案即可。另外，操作ShiftRows、SubBytes以及MixColumns均需要他们的逆操作来代替（操作AddRoundKey的逆操作就是它自己）。构造一个AES的“等价逆密码”在理论上是可能的，在这里我也是采用了这种方式。这个“等价逆密码”能通过一系列的逆操作来实现AES的解密，这些逆操作将以与AES加密相同的顺序进行，这样做可以在一定程度上提高实现效率。在该程序中，工作模式采用了电码本模式（ECB）。电码本模式就是一个分组密码的直接使用：给定一个128位的明文分组序列：x1x2……，每一个xi都用同一个密钥K来加密，产生密文分组序列y1y2……。（1）首先将明文以字节为单位进行处理，以128位分组、128位的密钥为例。先将明文按字节分成列组，将明文的前四字节组成一列，接下来的4个字节组成第二列，后面的字节依次组成第三列和第四列，则组成了一个4乘4的矩阵。（2）AES也是由基本的变换单位“轮”多次迭代而成的。AES的轮变换由四个不同的变换组成：1）字节代替变换非线性的字节替代，单独处理每个字节：求该字节在有限域GF(28)上的乘法逆，"0"被映射为自身，即对于α∈GF(28)，求β∈GF(28)，使得α•β=β•α=1mod(x8+x4+x2+x+1)。对上一步求得的乘法逆作仿射变换yi=xi+x(i+4)mod8+x(i+6)mod8+x(i+7)mod8+ci(其中ci是6310即011000112的第i位）2)行移位变换行移位变换完成基于行的循环位移操作，变换方法：即行移位变换作用于行上，第0行不变，第1行循环左移1个字节，第2行循环左移2个字节，第3行循环左移3个字节。3）列混合变换（最后一轮中没有）逐列混合，方法：矩阵表示形式：4）与子密钥异或只是简单的将密钥按位异或到一个状态上。每轮加密密钥按顺序取自扩展密钥，扩展密钥是由初始密钥扩展而成。密钥扩展：AES密钥扩展算法输入值是4字(16字节)，输出值是一个44字(176字节)的一维线性数组，为初始轮密钥加阶段和其他10轮中的每一轮提供4字的轮秘密钥，输入密钥直接被复制到扩展密钥数组的前四个字，然后每次用四个字填充扩展密钥数组余下的部分2.3程序主要代码分析ES.vcproj这是使用应用程序向导生成的VC++项目的主项目文件。它包含生成该文件的VisualC++的版本信息，以及有关使用应用程序向导选择的平台、配置和项目功能的信息。AES.h这是应用程序的主要头文件。它包括其他项目特定的头文件(包括Resource.h)，并声明CAESApp应用程序类。AES.cpp这是包含应用程序类CAESApp的主要应用程序源文件。AES.rc这是程序使用的所有MicrosoftWindows资源的列表。它包括RES子目录中存储的图标、位图和光标。此文件可以直接在MicrosoftVisualC++中进行编辑。项目资源位于2052中。res\AES.ico这是用作应用程序图标的图标文件。此图标包括在主要资源文件AES.rc中。res\AES.rc2此文件包含不在MicrosoftVisualC++中进行编辑的资源。您应该将不可由资源编辑器编辑的所有资源放在此文件中。2.4程序运行结果2.5安全性分析（1）暴力攻击单就密钥长度来看，AES里面最少128位的密钥绝对比DES的56位密钥要安全的多（2）统计攻击已经有很多的测试都无法对AES所产生的密文进行统计攻击（3）差分攻击与线性攻击AES系统目前仍然没有任何已知的差分攻击或者线性攻击存在。2.6设计实现中的问题及解决方法字符串输入的问题程序起初设计的是能够支持字符串的输入，可是使用scanf()函数读入字符串后会造成解密出现错误，后来经过查找资料和与同学的交流探讨，觉得这个错误应该是由于scanf()函数对于不满足数组定义长度的字符串的填充方式引起的。可是经过一段时间的修改还是没有解决问题，最后只好退而求次，将所要进行AES操作的字符串定义在主函数中，这样修改后的程序就没有出现解密的错误。三、RSA算法的实现3.1算法概述RSA密码体制是美国麻省理工学院（MIT）Rivest、Shami和Adleman于1978年提出来的，它是第一个理论上最为成功的公开密钥密码体制，它的安全性基于数论中的Euler定理和计算复杂性理论中的下述论断：求两个大素数的乘积是很容易计算的，但要分解两个大素数的乘积，求出它们的素数因子却是非常困难的，它属于NP—完全类，是一种幂模运算的加密体制。除了用于加密外，它还能用于数字签字和身份认证。下面将从各个方面来详细对RSA公钥体制进行研究。3.2算法原理及设计思想(1)密钥的产生1)选取两个保密的大素数p和q；2)计算n=p×q，Φ(n)=(p-1)(q-1),其中Φ(n)是n的欧拉函数值；3)选一整数e，满足1<e<Φ(n)，且gcd(Φ(n),e)=1；4)计算d，满足d×e=1modΦ(n),即d是e在模Φ(n)下的乘法逆元，因e与Φ(n)互素，由模运算可知，它的乘法逆元一定存在；5)以{e,n}为公开密钥，{d，n}为私密钥。(2)加密加密时首先将明文比特串分组，使得每个分组对应的十进制数小于n，即分组长度小于log2n，然后对每个明文分组m，作加密运算：c=memodn。(3)解密对密文分组的解密运算为：m=cdmodn。(4)安全分析RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯定可以修改成为大数分解算法。目前，RSA的一些变种算法已被证明等价于大数分解。不管怎样，分解n是最显然的攻击方法。现在，人们已能分解多个十进制位的大素数。因此，模数n必须选大一些，因具体适用情况而定。3.3程序主要代码分析(1)structPU{ Elemtypee; Elemtypen;}说明：公钥(2)structPR{ Elemtyped; Elemtypen;}说明：私钥(3)booltest_prime(Elemtypem)函数说明：判断一个数是否为为素数，返回值为布尔型，true即为素数，反之则不是素数。(4)voidswitch_to_bit(Elemtypeb,Elemtypebin[32])函数说明：将十进制数据转化为二进制数组。(5)Elemtypegcd(Elemtypea,Elemtypeb)函数说明：求最大公约数。(6)Elemtypeextend_euclid(Elemtypem,Elemtypebin)函数说明：用扩展的欧几里得算法求乘法逆元。(7)Elemtypemodular_multiplication(Elemtypea,Elemtypeb,Elemtypen)函数说明：快速模幂算法。(8)voidproduce_key()函数说明：产生密钥。(9)voidencrypt()函数说明：加密函数。(10)voiddecrypt()函数说明：解密函数。3.4程序运行结果1.源代码运行结果：3.5安全性分析目前国内外对RSA算法实现的研究大多是在运算速度很高的计算机上，在硬件上也主要采用串行处理，为了提高速度，安全性就必然很差，相反，为提高安全强度，则运算处理速度又会降低。在RSA算法中，最基本的算法主要包括模加、模乘、模逆和模幂运算。大数运算很费时间，尤其是大整数的模逆和模幂运算。RSA的安全性依赖于大数分解，但是否等同于大数分解一直未能得到理论上的证明，因为没有证明破解RSA就一定需要作大数分解。假设存在一种无须分解大数的算法，那它肯