RSA 加密算法在C++中的实现 面向初学者(附代码) |
您所在的位置:网站首页 › 福彩rsa代码 › RSA 加密算法在C++中的实现 面向初学者(附代码) |
概述
博文的一,二部分为基础知识的铺垫。分别从密码学,数论两个方面为理解RSA算法做好了准备。第三部分是对RSA加密过程的具体介绍,主要涉及其密钥对(key-pair)的获取。前三个部分与编程实践无关,可以当作独立的关于RSA加密算法的介绍。第四部分开始介绍在编程层面实现RSA算法的基础知识,主要涉及一些算法,如拓展欧几里得算法,米勒-拉宾素性检验算法,是为C++中实现RSA加密所作的铺垫。第五部分阐述了面向初学者实现RSA算法的思路,以及其局限,可改善之处。第六部分为提供的参考代码。 一. RSA算法的密码学基础密钥:将明文转换为密文,对于窃听者来说,密钥和明文等价。 对称加密(symmetric cryptograph),特征在于加密和解密使用同一个密钥。 非对称加密(asymmetric cryptography),也被称作公钥加密(public-key cryptography)。最主要的特征在于使用公钥加密,私钥解密。 下面我们通过一个例子,来简述非对称加密的过程,假设A,B两人进行公钥加密通信,则整个通信的过程,由信息接受者B启动(A为信息发出者)。 B首先通过一定算法生成包含公钥,私钥的密钥对(key-pair),然后将公钥发送给A,自己保留私钥,请求A利用这个公钥对信息进行加密。 A利用该公钥对信息进行加密后,将密文传送给B,B利用自己的私钥对密文进行解密。 值得注意的是:首先公钥是可公开的,因为光凭借公钥只能加密,而并不能解密,所以不用担心公钥传输过程中被窃听者截获,同理也不用担心密文被截获,因为唯一能够破解密文的密钥在信息接收者处。 RSA算法(Rivest-Shamir-Adleman 取自开发者首字母),正是一种公钥密码算法。 二. RSA算法的数论基础(看之前需要理解同余符号的含义) 1.欧拉函数: 对于正整数n,不大于n,且与n互素的数的个数记为 2.欧拉定理: (其弱化形式,即在n为素数时,变为费马小定理) 证明需要用到群论知识,与RSA算法关联不大,故在此不加赘述,可参考: 欧拉定理 证明及推论_有钱哥哥家的的博客-CSDN博客_欧拉定理证明 3.同余的一些基本性质: /1:乘积同余:即两数乘积,与两数模n的余数的乘积,关于模n同余,证明可以通过将两数写作kn+q(q为余数)的形式,比较其乘积与q1,q2乘积在模n时的结果。 /2:幂运算同余:若,则,证明可以通过移项,由因式定理可知,其必有a-b这个因式 4.逆元: 若,则称a为b,关于模n的逆元 三.RSA算法介绍我们用A来代表明文,B代表经过RSA算法加密后的密文。则可以用一个等式来阐明A,B间的关系:,且,即B为A的e次方后除以n的余数。其中(e,n)为公钥。 设(d,n)为私钥,则私钥满足的关系为 下面我们来看如何得到公钥和私钥组成的密钥对(需要用到二.介绍的数学知识)。 1.得到公钥: 选取两个充分大的素数p,q, 其乘积的值即为n,在得到n后,计算其欧拉函数的值,即在1到n-1中有多少数与n互素。 因为n包含两个质因子p,q,所以在1到n-1中包含p,q因子的数均与n不互素。 包含p因子的有p,2p,3p一直到p(q-1),同理含q的有q到q(p-1)。一共p+q-2个数 则在这n-1个数中与n互素的数一共有n-1-(p+q-2)=n-p-q+1,且n可以写作p*q,可以得到: 我们选取与互素的小于的数e,则(e,n)组成公钥。 2.得到私钥: 取e关于的逆元为d,则得到(d,n)私钥。 下面来证明为何(d,n)为私钥: 即证明: 两侧同时取e次幂可以得到 因为d为e的逆元,所以,将该等式带入到上式中,我们可以得到: 由欧拉定理可知,由同余的性质中的幂运算同余知,两侧同时取k次幂,可以得到: ,再由同余基本性质中的乘积同余,可知,此即为公钥的条件,于是我们发现在d取e 关于的逆元时,两者等价,即私钥条件成立。 上述生成的公钥与密钥组成的密钥对便可用于加密。 RSA算法的核心在于,对于一个大数的质因数分解是很困难的,一旦能够发现对于大数质因数的高效算法,RSA就能够被破译。 四.RSA在C++实现的算法基础在利用c++实现RSA加密时,含需要一些补充的算法知识: 1.裴蜀定理(Bezout’s lemma): 一定存在整数x,y,使得线性方程组ax+by=gcd(a,b)成立。而ax+by=gcd(a,b)则称为裴蜀等式。 2.拓展欧几里得算法(extended Euclidean algorithm): 欧几里得算法(辗转相除法)常用于求算最大公约数(gcd),而拓展欧几里得算法则是在具备欧几里得算法的功能前提下,增加了求解裴蜀等式的功能。而在我们通过公钥(e,n)计算私钥(d,n)时,就需要用到拓展欧几里得算法。 因为,可以写作 又因为,故上式可化为,符合裴蜀等式。 d与-k分别为欲求的x,y,故可以使用拓展欧几里得算法来求解 关于拓展欧几里得算法的细节可以参考:扩展欧几里得算法详解__Warning_的博客-CSDN博客_扩展欧几里得 3.米勒-拉宾素性检验(Miller-Rabin prime test) RSA加密的关键在于其最初生成的两个充分大的素数p,q,其大小决定了密码破译的难度。但是要随机生成两个大素数是比较困难的,所以RSA算法中大多都采用通过米勒-拉宾素性检验的伪素数来作为p,q。 米勒-拉宾素性检验是基于费马小定理,对给定的任意奇数进行检验,检验通过则代表其有概率为素数,在进行多次检验后,若都通过,则其为素数的概率会非常高,可以作为素数使用。 五.RSA算法在C++中的实现基本思路: 1.随机素数p,q的获取:利用数组,生成一定范围内一定质数的数表,产生随机数i,j对应素数数组的下标,由此达到在数表中随机选取素数的功能。 2.密钥的获取:利用拓展欧几里得算法获取d的值。 3.加密过程:将输入字符的ASCII码值进行RSA加密,密文为一串数字,实现方法是用字符数组与整型数组间的值传递。 局限与改善: 1.没有使用米勒-拉宾素性检验来获取大素数,而是用素数数表产生的素数对,其构成的密钥空间小,一旦数表范围被获取,则密钥极有可能被破解。 2.加密文本的读入没有涉及文件的读写层面,需要依靠人为输入,较为不方便。 3.部分计算没有考虑在选取充分大的素数时可能产生的数据溢出问题。 六.C++代码#include #include #include #include #include #include using namespace std; int exgcd(int a, int b,int *x,int *y) //拓展欧几里得算法 { if(b==0) { *x=1; *y=0; return a; } int gcd=exgcd(b,a%b,x,y); int temp=*x; *x=*y; *y=temp-a/b*(*y); return gcd; } int isprime(int a) //素数判断 { int i; for(i=2;i int i,j=0; for(i=91;i prime[j]=i; j++; } if(j>9)break; } } int main() { int prime[10]; primegenerator(prime); int seed,p,q; seed=time(0); srand((unsigned int)seed); //生成在范围内的随机素数p,q p=rand()%9; do{ q=rand()%9; }while(q==p); int e,d,n,fi_n,r,nu,w1,w2; int a; cout shuma_minwen[i]=minwen[i]; } int shuma_miwen[strlen(minwen)]; //录入结束,开始加密 for(i=0;i shuma_miwen[i]=(shuma_miwen[i]*mi)%n; } } cout int shuma_jiemiwen[10000]; cout ming=shuma_jiemiwen[i]; shuma_jieminwen[i]=1; for(j=0;j jieminwen[i]=shuma_jieminwen[i]; } cout |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |