实验4 非对称密码算法RSA（验证型）一、实验目的通过实际编程了解非对称密码算法RSA的加密和解密过程，加深对非对称密码算法的认识。
二、实验原理对称密码算法要求通信双方通过交换密钥实现使用同一个密钥，这在密钥的管理、发布和安全性方面存在很多问题，而非对称密码算法解决了这个问题。
加密密钥和解密密钥是不同的，其中加密密钥是可以公开的，解密密钥是要求保密的，并且不能用其中的一个推导出另一个。
它的安全性是建立在“大数分解和素性检测”这个数论难题的基础上，即将两个大素数相乘在计算上容易实现，而将该乘积分解为两个大素数因子的计算量相当大。
虽然它的安全性还未能得到理论证明，但经过30年的密码分析和攻击，迄今仍然被实践证明是安全的。
三、实验环境运行Windows或者Linux操作系统的PC机，具有gcc（Linux）、VC（Windows）等C语言编译环境。
四、实验内容和步骤1、为了加深对RSA算法的了解，根据已知参数：2qp，手工=M11,,3==计算公私钥，并对明文进行加密，然后对密文进行解密。
2、编写RSA程序，加密一段文字，了解RSA算法原理。
尝试加密一大段文字，记录程序的运行时间。
使用DES算法加密相同的文字，比较两种算法加密的速度。
x e mod，记录程3、编写一个程序，随机选择3个较大的数nx,,，计算ne序运行时间。
查阅资料给出简单说明大数在计算机上是如何表示，如何进行运算。
4、查阅资料，找出目前实际可行的素数判定法则，并比较各自的优缺点。
五、实验步骤1、p=3，q=11 则n=pq=33,f(n)=20，选择e=7,则d=3那么加密得c=29 解密得m=22、打开VC++，编写程序如下：#include<stdio.h>#include <iostream.h>#include <stdlib.h>#include <time.h>//using namespace std;typedef struct RSA_PARAM_Tag{ //64 位数unsigned __int64 p, q; //两个素数，不参与加密解密运算unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1unsigned __int64 s; //块长，满足2^s<=n的最大的s，即log2(n) } RSA_PARAM;//小素数表,用于素性测试前,用小素数来初步筛选素数.const static unsigned __int64 g_PrimeTable[]={3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};const static long g_PrimeCount=sizeof(g_PrimeTable) / sizeof(long); //乘数const unsigned __int64 multiplier=12747293821;// 加数const unsigned __int64 adder=1343545677842234541;//随机数类class RandNumber{private:unsigned __int64 randSeed;/* */public:RandNumber(unsigned __int64 s=0);unsigned __int64 Random(unsigned __int64 n);};/* */RandNumber::RandNumber(unsigned __int64 s){if(!s){randSeed= (unsigned __int64)time(NULL);}else{randSeed=s;}}/* 一个简单的随机数产生算法*/unsigned __int64 RandNumber::Random(unsigned __int64 n){randSeed=multiplier*randSeed+adder;return randSeed%n;}//定义了一个静态的类对象static RandNumber g_Rnd;/*模乘运算，返回值x=a*b mod n*/inline unsigned __int64 MulMod(unsigned __int64 a, unsigned __int64 b, unsigned __int64 n){return a * b % n;}/*模幂运算，返回值x=base^pow mod n*/unsigned __int64 PowMod(unsigned __int64 base, unsigned __int64 pow, unsigned __int64 n){ unsigned __int64 r=1;pow=pow+1;while(pow!=1) //循环结果为pow(a,b)%c{r=r*base;r=r%n;pow--;}return r;}/*{ unsigned __int64 a=base, b=pow, c=1;while(b){while(!(b & 1)){b>>=1; //a=a * a % n; //函数看起来可以处理64位的整数，但由于这里a*a在a>=2^32时已经造成了溢出，因此实际处理范围没有64位a=MulMod(a, a, n);}b--; //c=a * c % n; //这里也会溢出，若把64位整数拆为两个32位整数不知是否可以解决这个问题。
