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

计算机科学与技术系 实 验 报 告 专业名称 网络工程 课程名称 计算机网络安全技术 项目名称 密码学 班 级 13网工（1）班 学 号 1304031030 姓 名 余世光 同组人员 无 实验日期 2016/5/8 实验一 密码学 密码学数学基础实验 一、实验内容： 使用运算器工具完成大数运算、素性测试、模幂、原根、求逆和二次剩余的计算。 实验原理： 大数运算 大多数运算器只支持小于64位的整数运算，无法进行加密算法的运算。为满足加密算法的需要，可通过建立大整数运算库来解决这一问题。通常通过以下两种方式进行处理： 将大整数当作字符串处理，即将大整数用10进制字符数组表示；这种方式便于理解，但效率较低。 将大整数当作二进制流进行处理；计算速度快。 2、素性测试 Monte Carlo算法和Las Vegas算法均为素性测试的算法。 Monte Carlo算法 Monte Carlo算法又称为概率素性检测算法，算法描述如下： 输入：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)。 Las Vegas算法 Las Vegas算法又称为素性证明，算法描述如下： 输入：p为一个正基数；q1,q2,…,qk为p-1的全体素因子，其中k≤； 输出：若p为素数，输出YES；否则输出NO。 Prim_ Certify(p,q[k]) 在区间[2,p-1]上均匀随机的选取g for(i=1,i++,k)do 如果，输出NO_DECISION并终止程序； 如果，输出NO并终止程序； 输出YES并终止程序。 模幂 对于b,cm，模幂bcmod m按照整数幂的通常定义，b自乘c次，但要模m；模幂算法描述如下： 输入：整数b、c、m，其中b0，c≥0，m1； 输出：bcmod m mod_exp(b,c,m) if(c=0) return (1)； if (c mod 2=0) return(mod_exp(b2 mod m,c/2,m))；其中c/2表示c除以2取整； return (b·mod_exp(b2 mod m,c/2,m))。 原根 在数论，特别是整除理论中，原根是一个很重要的概念。 对于两个正整数，由欧拉定理可知，存在正整数，比如说欧拉函数，即小于等于?m?的正整数中与?m?互质的正整数的个数，使得。 由此，在时，定义a对模m的指数为使成立的最小的正整数d。由前知一定小于等于?，若，则称a是模m的原根。 求逆 乘法逆元的定义为：对于，存在于，使得于，则w是可逆的，称x为w的乘法逆元，记为；其中Zn表示小于n的所有非负整数集合。 通常通过扩展欧几里得算法和费马小定理求乘法逆元，此处使用扩展欧几里得算法。 扩展欧几里得算法的定义为：如果整数f1，gcd(d,f)=1，那么d有一个模f的乘法逆元；即对于小于f的正整数d，存在一个小于f的正整数d-1，使得。扩展欧几里得算法的具体描述如下： ExtendedEUCLID(d,f) (X1,X2,X3)←(1,0,f)；(Y1,Y2,Y3)←(1,0,d)。 若Y3=0，返回X3=gcd(d,f)；无逆元。 若Y3=1，返回Y3=gcd(d,f)；Y2=d-1mod f。 Q=。 (T1,T2,T3)←(X1-Q·Y1,X2 -Q·Y2,X3-Q·Y3)。 (X1,X2,X3)←(Y1,Y2,Y3)。 (Y1,Y2,Y3)←(T1,T2,T3)。 返回(2)。 二次剩余 二次剩余的定义为：a与p互素，p是奇素数，若，则称a是模p的二次剩余；否则称a是模p的非二次剩余。 二次剩余定理：若p是奇素数，则整数1,2,…,p-1中正好有(p-1)/2个是模p的二次剩余，其余的(p-1)/2个是非二次剩余。 三、实验环境： ISES客户端 四、实验步骤： 加、减、乘、除、模、求逆运算 选择进制类型和计算类型，输入要计算的操作数，点击计算。显示计算后的结果，如图1所示。 图1 模幂运算 选择进制类型和计算类型，输入要计算的b、e、m，点击计算。显示模