文档介绍：1 实验二: RSA 公钥密码加、解密技术一、实验目的通过编写 RSA 算法( 小素数)程序, 并运行此程序对实验数据进行加密和解密操作,使学生进一步掌握 RSA 公钥密码体制。二、实验要求(1)用VC++ 写出加密、解密程序代码。( 要求完成加密和解密, 明文仅限为英文字母、数字、空格和标点符号); (2) 运行自己编写的程序, 输入素数 p=7,q=13 : 明文为最多两位整数学号:如 2,23 等,得出相应的密文,并对其解密,验证解密后得到的明文是否与输入的学号相同。三、相关知识 1976 年, 提出了公钥密码学的思想。在公钥密码体制中, 加密密钥和解密密钥是不一样的,加密密钥可以公开传播而不危及密码体制的安全性。公钥密码体制主要有三种: RSA 公钥密码体制、 EIGamal 公钥密码体制、 Menezes-Vanstone 公钥密码体制。本次实验内容是关于 RSA 公钥密码体制。 RSA 公钥密码体制的安全性是基于大整数的素分解问题的难解性。其有自身的优缺点, 优点是加密密钥可以公开传播,缺点是运算速度较慢。算法描述:(本次试验只要求对小素数实现 RSA 算法) 1. 密钥的产生 1) 找出两个相异的素数 P和Q,令 N=P×Q,M=( P-1)( Q-1)。 2) 找出与 M 互素的整数 E,且1<E<M 利用欧氏算法计算出整数 D,使D×E≡1MOD M。欧氏算法:①n1←M,n2 ←E,b1 ←0,b2 ←1; ② k=[n1/n2],r ←n1-k*n2; ③如果 r≠0,则 n1←n2,n2 ←r,t ←b2,b2 ←b1-k*b2,b1 ←t;转第②步; ④如果 n2≠1,则E模M 不存在逆元; ⑤如果 n2=1 ,则 E模M 的逆元为 b2mod M 为什么有: E模M 的逆元为 b2mod M 根据课本中定理 ,只要 E,M 互素且 1<E<M ,则存在整数 a,b使得: b*E +a*M=1 于是: b*E mod M=1 令 b1(0)=0,b2(0)=1, 则: n1(0)=a1(0) n1(0) +b1(0) n2(0) n2(0)=a2(0) n1(0) +b2(0) n2(0) 假设 i=j 时成立,则有 2 n1(j)=a1(j) n1(0) +b1(j) n2(0) n2(j)=a2(j) n1(0) +b2(j) n2(0) 当i=j+1 时有: n1(j+1)=n2(j) =a2(j) n1(0) +b2(j) n2(0) n2(j+1)=n1(j)-q(j)n2(j) =a1(j) n1(0) +b1(j) n2(0) -q(j){ a2(j) n1(0) +b2(j) n2(0) } =(a1(j)- q(j) a2(j)) n1(0) +(b1(j)- q(j) b2(j) )n2(0) 这样循环下去,直到 q(i)=0,n2(i)=1 则b2(i )满足: b2(i)*E+a*M=1 令: b2= b2(i)mod M,则b2*E mod M=1 故: b2是E关于模 M的逆元 3)丢弃 P和Q,公开 E,D和N。E和N 即加密密钥, D和N 即解密密钥。 2. 明文加密字符 a 属于明文集 A, 进行 c=a^E MOD N 运算。 c 就是密文数