实验五RSA算法的实现.docVIP

上机实验报告（五） 实验课程：应用密码学 实验时间:2013年11月18日 任课教师:刘光军 班级：11级信息与计算科学专业1班 姓名：刘静 学号：0202110123 一、实验名称: RSA算法的实现 二、实验目的 1、了解RSA算法的基本原理； 2、掌握RSA算法的实现方法； 3、通过实际编程了解非对称密码算法RSA的加密和解密过程，同时锻炼编 程能力。 三、实验基础原理 1、RSA密码系统所基于的数学难题是对大素数的因式分解。 2、RSA算法原理： (1) 选择两个大的素数 p 和 q（典型情况下为 1024 位）； (2) 计算 n = p * q 和 z =（p-1）*（q-1）； (3) 选择一个与 z 互素的数，将它称为 d； (4) 找到 e，使其满足 e*d = 1 mod z。 四、实验思路 1、确定密钥的长度； 2、随机选择两个不同的素数p处q，它们的宽度是密钥宽度的二分之一； 3、计算出p和q的乘积n ； 4、在2和Φ(n)之间随机选择一个数e，e 必须和Φ(n)互素整数e用做加密（其中Φ(n)=(p-1)*(q-1)）； 5、从公式ed ≡1 modΦ(n)中求出解密密钥d； 6、得公钥（e，n ），私钥 (d，n)； 7、公开公钥，但不公开私钥； 8、将明文P (假设P是一个小于n的整数)加密为密文C，计算方法为：C = Pe mod n 9、将密文C解密为明文P，计算方法为：P = Cd mod n 然而只根据n和e（不是p和q）要计算出d是不可能的。因此，任何人都可对明文进行加密，但只有授权用户（知道d）才可对密文解密。 五、报告正文（文档，数据，模型，程序，图形） 1、根据以上实验思路编写C/C++程序实现RSA算法，利用该程序给出相关的加解密实例。 #include iostream #include stdlib #include timeusing namespace std;//RSA算法所需参数 typedef struct RSA_PARAM_Tag { unsigned __int64 p, q; //两个素数，不参与加密解密运算 unsigned __int64 f; //f=(p-1)*(q-1)，不参与加密解密运算 unsigned __int64 n, e; //公匙，n=p*q，gcd(e,f)=1 unsigned __int64 d; //私匙，e*d=1 (mod f)，gcd(n,d)=1 unsigned __int64 s; //块长，满足2^s=n的最大的s，即log2(n) } RSA_PARAM;//小素数表 const static long 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 unsigne