第13章 公钥密码实现程序-1

1、计计算机硬件基算机硬件基础教学础教学中心中心Copyright by NUPT All rights reserved.1Technology of Network Programming网络编程技术网络编程技术网络编程技术网络编程技术2 公钥密码体制在网络与信息安全应用中公钥密码体制在网络与信息安全应用中具有重要的地位。通过本章学习，读者可具有重要的地位。通过本章学习，读者可以了解非对称密码体系以了解非对称密码体系RSA算法的实算法的实现细节，并可以对现细节，并可以对DES、椭圆曲线等其他、椭圆曲线等其他密码学算法有简单的了解。密码学算法有简单的了解。网络编程技术网络编程技术3 编程训练目的

2、编程训练目的 编程训练要求编程训练要求 相关知识介绍相关知识介绍 程序设计分析程序设计分析 扩展与提高扩展与提高网络编程技术网络编程技术4 实现自己的加密解密程序实现自己的加密解密程序 对密码学的相关知识，尤其是数据对密码学的相关知识，尤其是数据加密解密的过程加密解密的过程有有一个初步的了解一个初步的了解网络编程技术网络编程技术5 编程训练目的编程训练目的 编程训练要求编程训练要求 相关知识介绍相关知识介绍 程序设计分析程序设计分析 扩展与提高扩展与提高网络编程技术网络编程技术6 编写程序，实现编写程序，实现RSA加解密过程，要求：加解密过程，要求： 程序工作在程序工作在Windows环境下环

3、境下 能够使用能够使用RSA加密算法加密指定字符串并加密算法加密指定字符串并对加密后的密文进行解密，并与源字符串对加密后的密文进行解密，并与源字符串进行比对，证明解密无误进行比对，证明解密无误 必须输出加密相关的各项参数，如公钥，必须输出加密相关的各项参数，如公钥，私钥，通过乘积构成大整数的两个素数等私钥，通过乘积构成大整数的两个素数等网络编程技术网络编程技术7 网络编程技术网络编程技术8 编程训练目的编程训练目的 编程训练要求编程训练要求 相关知识介绍相关知识介绍 程序设计分析程序设计分析 扩展与提高扩展与提高网络编程技术网络编程技术9 最早的密码学应用最早的密码学应用 近代密码学发展近代密

4、码学发展 密码学在战争中的应用密码学在战争中的应用网络编程技术网络编程技术10 明文：作为算法的输入，原始可理解的消息或者数明文：作为算法的输入，原始可理解的消息或者数据；据；加密算法：加密算法对明文进行各种代换和变换；加密算法：加密算法对明文进行各种代换和变换；密文：作为算法的输出，看起来完全随机而杂乱的密文：作为算法的输出，看起来完全随机而杂乱的数据，依赖明文和密钥。对于给定的消息，不同的数据，依赖明文和密钥。对于给定的消息，不同的密钥将产生不同的密文，密文是随机的数据流，并密钥将产生不同的密文，密文是随机的数据流，并且其意义是无法理解的；且其意义是无法理解的；密钥：密钥也是加密算法的输入

5、，密钥独立于明文，密钥：密钥也是加密算法的输入，密钥独立于明文，算法将根据所用的特定密钥而产生不同的输出。算算法将根据所用的特定密钥而产生不同的输出。算法所用的代换和变换也依靠密钥；法所用的代换和变换也依靠密钥；解密算法：加密算法的逆。输入密文和密钥可以用解密算法：加密算法的逆。输入密文和密钥可以用解密算法恢复出明文；解密算法恢复出明文；网络编程技术网络编程技术11 网络编程技术网络编程技术12 明文：作为算法的输入，原始可理解的消息或者数据；明文：作为算法的输入，原始可理解的消息或者数据；加密算法：加密算法对明文进行各种代换和变换；加密算法：加密算法对明文进行各种代换和变换；密文：作为算法的

6、输出，看起来完全随机而杂乱的数据，密文：作为算法的输出，看起来完全随机而杂乱的数据，依赖明文和密钥。对于给定的消息，不同的密钥将产生依赖明文和密钥。对于给定的消息，不同的密钥将产生不同的密文，密文是随机的数据流，并且其意义是无法不同的密文，密文是随机的数据流，并且其意义是无法理解的；理解的；公钥和私钥：算法输入的一部分，公钥和私钥成对出现，公钥和私钥：算法输入的一部分，公钥和私钥成对出现，一个用来加密，另一个用来解密，加密算法执行的变化一个用来加密，另一个用来解密，加密算法执行的变化依赖与公钥和私钥依赖与公钥和私钥 ；解密算法：该算法用来接收密文和相应的密钥，并产生解密算法：该算法用来接收密文

7、和相应的密钥，并产生原始的明文；原始的明文；网络编程技术网络编程技术13 网络编程技术网络编程技术14 编程训练目的编程训练目的 编程训练要求编程训练要求 相关知识介绍相关知识介绍 程序设计分析程序设计分析 扩展与提高扩展与提高网络编程技术网络编程技术15模乘运算和模幂运算模块模乘运算和模幂运算模块 模乘运算即计算两个数的乘积然后取模，其中模乘运算即计算两个数的乘积然后取模，其中为了避免大数相乘造成的溢出，根据求模运算为了避免大数相乘造成的溢出，根据求模运算的 性 质 ， 优 化 了 算 法 ， 其 中的 性 质 ， 优 化 了 算 法 ， 其 中“(a%n)*(b%n)%n”等价于等价于“(

8、a*b) %n”。 模幂运算模幂运算就是计算一个数的就是计算一个数的n次幂，然后进行次幂，然后进行取模运算，同样是出于避免大数相乘造成溢出取模运算，同样是出于避免大数相乘造成溢出的情况，这里编程使用了一些数学技巧，基于的情况，这里编程使用了一些数学技巧，基于快速模幂算法进行优化。快速模幂算法进行优化。网络编程技术网络编程技术161、模乘运算和模幂运算模块、模乘运算和模幂运算模块static RandNumber cRadom;/*模乘运算，返回值模乘运算，返回值 x=a*b mod n*/inline unsigned _int64 MulMod(unsigned _int64 a, unsi

9、gned _int64 b, unsigned _int64 n) return (a%n) * (b%n) % n;网络编程技术网络编程技术171、模乘运算和模幂运算模块、模乘运算和模幂运算模块/*模幂运算，返回值模幂运算，返回值 x=basepow mod n*/unsigned _int64 PowMod(unsigned _int64 base, unsigned _int64 pow, unsigned _int64 n) unsigned _int64 a=base, b=pow, c=1; while(b) /保证保证b0 while(!(b & 1) /保证保证b为偶数为偶数

10、b=1; / b/2 a=MulMod(a, a, n); /调用模乘运算调用模乘运算 b-; c=MulMod(a, c, n); /调用模乘运算，记录中间变量调用模乘运算，记录中间变量c return c;网络编程技术网络编程技术18生成最大随机数生成最大随机数 本模块主要由三个函数构成：本模块主要由三个函数构成：l第一个函数用来完成第一个函数用来完成Rabin-Miller素数测试，这个素数测试，这个函数利用了函数利用了Femat定理：如果定理：如果n是素数，是素数，an-1 1 mod n，使用此定理可以，使用此定理可以大概率大概率确定一个数可能为素数；确定一个数可能为素数； l重复调

11、用重复调用Rabin-Miller检验函数检验函数确定确定一个数字是否一个数字是否为素数的函数；为素数的函数；l生成一个随机的大素数，程序首先生成一个生成一个随机的大素数，程序首先生成一个确保最确保最高位是高位是1（确保足够大）的随机奇数（确保足够大）的随机奇数，然后，检验，然后，检验该奇数是否是素数，重复该过程直到找到所需的素该奇数是否是素数，重复该过程直到找到所需的素数为止；数为止； 网络编程技术网络编程技术192、生成最大随机数、生成最大随机数 long RabinMillerKnl(unsigned _int64 &n) unsigned _int64 a, q, k, v ; q=n

12、 - 1; k=0; while(!(q & 1) +k; q=1; /q/2，实际上计算，实际上计算q * 2k /计算出计算出q，k，使得，使得n-1 = q * 2k a=2 + cRadom.Random(n - 3); /生成随机数生成随机数a，并且，并且2=an-1 v=PowMod(a, q, n); /计算计算aq mod n ,如果结果如果结果v1则可能是素数则可能是素数 网络编程技术网络编程技术202、生成最大随机数、生成最大随机数 if(v = 1) return 1; for(int j=0;jk;j+)unsigned int z=1;for(int w=0;wj;w

13、+)z*=2;if(PowMod(a, z*q, n)=n-1)return 1;return 0;网络编程技术网络编程技术212、生成最大随机数、生成最大随机数 long RabinMiller(unsigned _int64 &n, long loop) /先用小素数筛选一次，提高效率先用小素数筛选一次，提高效率 for(long i=0; i g_PrimeCount; i+) if(n % g_PrimeTablei = 0) return 0; /循环调用循环调用Rabin-Miller测试测试loop次，使得非素数通过测试的概率降为次，使得非素数通过测试的概率降为(1/4)loop

14、 for(long i=0; i loop; i+) if(!RabinMillerKnl(n) return 0; /*网络编程技术网络编程技术222、生成最大随机数、生成最大随机数 随机生成一个随机生成一个bits位位(二进制位二进制位)的素数，最多的素数，最多32位位*/unsigned _int64 RandomPrime(char bits) unsigned _int64 base; do base= (unsigned long)1 q ? p : q; unsigned _int64 b=p Max)return 0;return 0; 网络编程技术网络编程技术27加密解密过程

15、加密解密过程 首先程序初始化相关变量，定义字符串首先程序初始化相关变量，定义字符串“abcdefghijklmnopqrstuvwxyz”作为加密的源字符作为加密的源字符串，其中串，其中RSA_PARAM是一个预先定义的结构体，是一个预先定义的结构体，用来存储和用来存储和RSA加密算法相关的参数。加密算法相关的参数。 通过调用函数通过调用函数RsaGetParam()初始化与初始化与RSA加密相加密相关的各项参数，并在终端输出；关的各项参数，并在终端输出； 循环调用模幂运算函数针对每个字节计算循环调用模幂运算函数针对每个字节计算C = Me mod n，并输出加密后的运算结果；，并输出加密后的

16、运算结果； 同样循环调用模幂运算函数计算同样循环调用模幂运算函数计算M=Cd mod n；并；并输出解密后的字符串；输出解密后的字符串； 网络编程技术网络编程技术285、加密解密过程、加密解密过程/*随机产生一个随机产生一个RSA加密参数加密参数*/RSA_PARAM RsaGetParam(void) Rsa.p=RandomPrime(16); /随机生成两个素数随机生成两个素数 Rsa.q=RandomPrime(16); Rsa.n=Rsa.p * Rsa.q; Rsa.f=(Rsa.p - 1) * (Rsa.q - 1); do Rsa.e=cRadom.Random(65536)

17、; /小于小于216，65536=216 Rsa.e|=1; /保证最低位是保证最低位是1，因，因f一定是偶数，要互素，只能是奇数一定是偶数，要互素，只能是奇数 while(Gcd(Rsa.e, Rsa.f) != 1); Rsa.d=Euclid(Rsa.e, Rsa.f); Rsa.s=0; t=Rsa.n 1; while(t) Rsa.s+; t=1; return Rsa;网络编程技术网络编程技术295、加密解密过程、加密解密过程 cout Encode:rn; for(unsigned long i=0; i n; i+) pEnci=PowMod(pSrci, r.e, r.n); C=Me mod n cout hex pEnci ; cout endl; cout Decode:rn; for(unsigned long i=0; i n; i+) pDeci=PowMod(pEnci, r.d, r.n); M=Cd mod n cout hex (unsigned long)pDeci ; cout endl