1304031030-余世光-计算机网络安全技术-实验一-密码学基础

计算机科学与技术系实验报告专业名称网络工程课程名称计算机网络安全技术项目名称密码学班级13网工（1）班学号1304031030姓名余世光同组人员无实验日期2016/5/8实验一密码学密码学数学基础实验一、实验内容：使用运算器工具完成大数运算、素性测试、模幂、原根、求逆和二次剩余的计算。二、实验原理：1、大数运算大多数运算器只支持小于64位的整数运算，无法进行加密算法的运算。为满足加密算法的需要，可通过建立大整数运算库来解决这一问题。通常通过以下两种方式进行处理：(1)将大整数当作字符串处理，即将大整数用10进制字符数组表示；这种方式便于理解，但效率较低。(2)将大整数当作二进制流进行处理；计算速度快。2、素性测试MonteCarlo算法和LasVegas算法均为素性测试的算法。(1)MonteCarlo算法MonteCarlo算法又称为概率素性检测算法，算法描述如下：输入：p为一个正整数；输出：若p为素数，输出YES；否则输出NO。Prime_Test(p)flag=0；重复次：在(1,p-1]区间上均匀随机的选取x；如果gcd(x,p)1或，return(NO)；如果flag=0且，flag=1；结束重复；如果flag=0，即在重复中没有出现过，return(NO)；return(YES)。(2)LasVegas算法LasVegas算法又称为素性证明，算法描述如下：输入：p为一个正基数；q1,q2,…,qk为p-1的全体素因子，其中k≤；输出：若p为素数，输出YES；否则输出NO。Prim_Certify(p,q[k])在区间[2,p-1]上均匀随机的选取gfor(i=1,i++,k)do如果，输出NO_DECISION并终止程序；如果，输出NO并终止程序；输出YES并终止程序。2、模幂对于b,cm，模幂bcmodm按照整数幂的通常定义，b自乘c次，但要模m；模幂算法描述如下：输入：整数b、c、m，其中b0，c≥0，m1；输出：bcmodmmod_exp(b,c,m)if(c=0)return(1)；if(cmod2=0)return(mod_exp(b2modm,c/2,m))；其中c/2表示c除以2取整；return(b·mod_exp(b2modm,c/2,m))。3、原根在数论，特别是整除理论中，原根是一个很重要的概念。对于两个正整数，由欧拉定理可知，存在正整数，比如说欧拉函数，即小于等于m的正整数中与m互质的正整数的个数，使得。由此，在时，定义a对模m的指数为使成立的最小的正整数d。由前知一定小于等于，若，则称a是模m的原根。4、求逆乘法逆元的定义为：对于，存在于，使得于，则w是可逆的，称x为w的乘法逆元，记为；其中Zn表示小于n的所有非负整数集合。通常通过扩展欧几里得算法和费马小定理求乘法逆元，此处使用扩展欧几里得算法。扩展欧几里得算法的定义为：如果整数f1，gcd(d,f)=1，那么d有一个模f的乘法逆元；即对于小于f的正整数d，存在一个小于f的正整数d-1，使得。扩展欧几里得算法的具体描述如下：ExtendedEUCLID(d,f)(1)(X1,X2,X3)←(1,0,f)；(Y1,Y2,Y3)←(1,0,d)。(2)若Y3=0，返回X3=gcd(d,f)；无逆元。(3)若Y3=1，返回Y3=gcd(d,f)；Y2=d-1modf。(4)Q=。(5)(T1,T2,T3)←(X1-Q·Y1,X2-Q·Y2,X3-Q·Y3)。(6)(X1,X2,X3)←(Y1,Y2,Y3)。(7)(Y1,Y2,Y3)←(T1,T2,T3)。(8)返回(2)。5、二次剩余二次剩余的定义为：a与p互素，p是奇素数，若，则称a是模p的二次剩余；否则称a是模p的非二次剩余。二次剩余定理：若p是奇素数，则整数1,2,…,p-1中正好有(p-1)/2个是模p的二次剩余，其余的(p-1)/2个是非二次剩余。三、实验环境：ISES客户端四、实验步骤：(1)加、减、乘、除、模、求逆运算选择进制类型和计算类型，输入要计算的操作数，点击计算。显示计算后的结果，如图1所示。图1(2)模幂运算选择进制类型和计算类型，输入要计算的b、e、m，点击计算。显示模幂计算后的结果，如图2所示。图2(3)生成大素数原根选择进制类型和计算类型，点击随机生成按钮，显示随机生成的大素数以及大素数的原根，如图3所示。图3(4)二次剩余判断选择进制类型和计算类型，输入a、p，点击计算。显示二次剩余的判断结果，如图4所示。图4(5)素性测试选择进制类型和计算类型，输入待测试的大整数，点击测试。显示测试结果，如图5，6所示。图5图6五、实验总结：六.实验思考：1、计算MonteCarlo算法和LasVegas算法的时间复杂度2、将模幂算法修改为非递归算法，并计算递归与非递归算法的复杂度3、思考如何将扩展欧几里得算法和费马小定理用于求逆散列函数实验一、实验内容：1、通过运算器工具实现MD5、SHA-1/256、HMAC等算法的加解密。2、对两个报文的MD5值进行异或比对，进行SHA-1的分步计算。3、对MD5、SHA-1/256等算法进行扩展实验和算法跟踪。二、实验原理：散列函数是一种单向密码，即是一个从明文到密文的不可逆映射，只有加密过程，不可解密；同时散列函数可以将任意长度的输入经过变换以后得到固定长度的输出。散列函数在完整性认证和数字签名等领域有广泛应用。散列函数应满足以下要求：(1)算法公开，不需要密钥。(2)具有数据压缩功能，可将任意长度的输入转换为固定长度的输出。(3)已知m，容易计算出H(m)。(4)给定消息散列值H(m)，要计算出m在计算上是不可行的。(5)对任意不同的输入m和n，它们的散列值是不能相同的。1、MD5算法MD5(Message-DigestAlgorithm5)即信息-摘要算法，是MD4算法的改进；算法的输入为任意长度的消息，分为512比特长的分组，输出为128比特的消息摘要。处理过程如下：(1)对消息进行填充，使其比特长度为n512+448(n为正整数)，填充方式是固定的：第一位为1，其后各位为0。(2)附加消息长度，使用上一步骤留出的64比特以小端(最低有效字节/位存储于低地址字节/位)方式来表示消息被填充前的长度，若消息长度大于264，则以264为模数取模。(3)对消息摘要缓冲区初始化，算法使用128比特长的缓冲区来存储中间结果和最终散列值，将缓冲区表示成4个32比特长的寄存器A、B、C、D，每个寄存器以小端方式存储数据，初始值为(十六进制，低位字节在前)A=01234567，B=89ABCDEF，C=FEDCBA98，D=76543210。(4)以分组为单位对消息进行处理，每一个分组都经过压缩函数HMD5处理；HMD5有4轮处理过程，每轮有16步迭代，4轮处理过程的处理结构一样，所用逻辑函数不同，分别表示为F、G、H、I；每轮的输入为当前处理的消息分组和缓冲区当前的值，输出仍存放在缓冲区中。最后第四轮的输出与第一轮输入的缓冲区值V相加，相加时将V看做4个32比特的字，每个字与第四轮输出的对应的字按模232相加，相加结果为HMD5的输出。(5)消息的所有分组均被处理完后，最后一个HMD5的输出即为产生的128位消息摘要。2、SHA-1/256算法SHA的全称为SecureHashAlgorithm(安全杂凑算法)，SHA家族的五个算法分别是SHA-1、SHA-224、SHA-256、SHA-384和SHA-512，由美国国家安全局(NSA)所设计，并由美国国家标准与技术研究院(NIST)发布，后四者有时并称为SHA-2。SHA-1基于MD4算法，算法的输入最大长度为264-1比特，分为512比特长的分组，输出为160比特的消息摘要。处理过程如下：(1)对消息进行填充，与MD5第一步相同。(2)附加消息长度，与MD5第二步类似，不同的是以大端(最高有效字节/位存储于低地址字节/位)方式来表示消息被填充前的长度。(3)对消息摘要缓冲区初始化，算法使用160比特长的缓冲区来存储中间结果和最终散列值，将缓冲区表示成5个32比特长的寄存器A、B、C、D、E，每个寄存器以大端方式存储数据，初始值为(十六进制，高位字节在前)A=67452301，B=EFCDAB89，C=98BADCFE，D=10325476，E=C3D2E1F0。(4)以分组为单位对消息进行处理，每一个分组都经过压缩函数HSHA处理；HSHA有4轮处理过程，每一轮又有20步迭代；4轮处理过程的处理结构一样，所用逻辑函数不同，分别表示为f1、f2、f3、f4；每轮的输入为当前处理的消息分组和缓冲区当前的值，输出仍存放在缓冲区中。最后第四轮的输出与第一轮输入的缓冲区值V相加，相加时将V看做5个32比特的字，每个字与第四轮输出的对应的字按模232相加，相加结果为HMD5的输出。(5)消息的所有分组均被处理完后，最后一个HSHA的输出即为产生的160位消息摘要。SHA-256使用6个逻辑函数，均基于32位的字进行操作，算法输出的消息摘要为256位。SHA与MD5处理过程类似，主要区别在于所使用的压缩函数不同。3、HMAC算法HMAC的全称为Hash-basedMessageAuthenticationCode(基于散列的消息认证码)，HMAC将散列函数作为一个黑盒使用，，散列函数的实现可作为实现HMAC的一个模块，并可使用新模块代替旧模块。设H为嵌入的散列函数，M为HMAC的输入消息(包括散列函数所要求的填充位)，Yi(0≤i≤L-1)是M的第i个分组，L为M的分组数，b为一个分组中的比特数，n为嵌入的散列函数所产生的散列值的长度，K为密钥，若密钥长度大于b，则将密钥输入到散列函数中产生一个n比特长的密钥，K+是左边将填充0后的K，K+的长度为b比特，ipad为b/8个00110110，opad为b/8个01011010；则算法的输出可表示为：三、实验环境：ISES客户端；MicrosoftCLRDebugger2005或其它调试器。四、实验步骤：1、散列值计算(1)选择明文格式，输入明文；(2)勾选计算使用的算法，默认为全选；(3)点击“计算”按钮，使用所选算法分别计算明文的散列值；算法对应的文本框中将显示相应的散列值，如图1所示。图12、MD5值比对(1)点击“扩展实验”框中的“MD5值比对”按钮，进入MD5值比对窗体。(2)相同报文的MD5散列值比对分别在第一组报文和第二组报文处输入相同的报文值，并计算MD5散列值；点击“异或比较”按钮，进行散列值的比对，非0元个数即为散列值中互不相同的位数，此处为0，即相同报文的散列值相同，如图2所示。图2(3)相似报文的MD5散列值比对保持第一组报文中的内容不变，修改第二组报文值中的最后一位，计算其散列值，并进行异或比较，结果如图3所示；可以看出对两个极为相似的报文进行散列后得到的散列值差异是非常大的。图33、MD5扩展实验(1)点击“扩展实验”框中的“MD5扩展实验”，进入MD5扩展实验窗体。(2)在测试向量文本框中输入任意长度的ASCII字符串，点击“运行”，MD5算法的运行结果会出现在信息摘要文本框中，如图4所示。图4(3)观察MD5算法的执行过程。点击“算法演示”按钮，激活算法演示界面，如图5所示，其中表示模232加。图5①在“数据分组编号（q）”文本框中输入一个小于“数据最大分组数”文本框中的非负整数，然后点击“开始”，启动算法执行，如图6所示。图6②点击“第一轮函数变换”按钮，进入轮函数变换窗口。依次点击界面中的按钮，得到MD5算法中的各种中间步骤结果，如图7所示。图7③依次执行“第二轮函数变换”，“第三轮函数变换”，“第四轮函数变换”后，进入该组信息摘要变换的最后一步。点击最下面的加法异或按钮，得到该分组的信息摘要结果。具体如图8所示。图84、SHA扩展实验SHA扩展实验包括SHA1扩展实验和SHA2-224/256扩展实验等，此处以SHA1扩展实验为例，其他可参照完成。点击扩展实验下的“SHA1扩展”按钮，进入S