基于c语言的rsa算法高效实现

《基于c语言的rsa算法高效实现》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、研究与开发基于C语言的RSA算法高效实现郭海民（陕西大荔县城郊中学，大荔715100）摘要：RSA算法是现代公钥密码体制事实上的标准，虽然它有被椭圆曲线密码算法（ECC）取代的局势，但是研究RSA加密算法还有一定的实际意义。深入讨论RSA算法的实现细节，对RSA的快速实现给出一种高效实用算法。关键词：RSA算法；加密/解密；素数计算密文：C≡Me0引言modn（3）解密算法RSA算法最早是由美国MIT的Rivest、Shamir和已知：密文C和私钥sk=（n，d）。Adleman在1978年提出来的，它是现今使用最广泛的计算明文：M≡Cd公钥密码体制，也是公钥密码的国际标准。RSA

2、算法基modn。于几百年来广为流传的初等数论知识，事实上，它的安1.2算法安全性分析全性是建立在大整数因子分解难题的基础之上。由于RSA的安全性基于大整数因子分解的困难性，所进行的都是大数计算，使得RSA最快的情况也比DES以在密钥生成时，尽量要求n很大，这样攻击者要成功慢上几倍，所以无论是软件还是硬件实现，速度一直是地分解为φ（n）=（p-1）·（q-1）非常困难，从而保证了攻RSA的缺陷。一般来说RSA只用于少量的数据加密，因击者即使知道了pk=｛n，e｝也不能通过d≡e-1mod（n）推此提高RSA公钥密码加密算法的速度是非常关键的。导出sk=d。RSA的加密函数是一个单项函

3、数，在已知明1RSA密码体制的描述文M和公钥pk=｛n，e｝的情况下，计算出密文C是很容易的；但它的逆函数计算过程是很困难的，所以，攻击1.1RSA算法过程者在未知道陷门的情况下要恢复明文M是不可能的。（1）密钥的产生对于接收方来说，知道自己的私钥sk=｛d，n｝，即陷门信首先，随机生成两个不同的大素数p和q，并计算息，从而很容易地恢复出明文M。n=p·q，φ（n）=（p-1）（q-1），随机选取整数e（0

4、ed≡1mod（φ（n））的d=emodφ（n）的整数，其中e就是加密密钥，而d就是解密密钥，n称为模数。公开（n，e），选择100位以上的十进制数。保密（p，q，d）。2RSA算法的有效实现方案（2）加密算法RSA属于公钥加密体制，而公钥加密算法有一个已知明文M（M

5、是非常重要的。{if（isPower（n））2.1快速实现模运算Return0;从RSA算法的过程可以知道，指数运算占有很大R=min（r

6、ord（n,z/r）>4*（log（n）^2））;For（a=2;a<=r;a++）的比例，而我们一般是使用降阶的方法实现的，这种方{gcd=gcd（a,n）;法的缺点就是占用了大量的内存空间。为了有效地进If（gcd>1&&gcd

7、）;iΣ2iiFor（a=1;a<=s;a++）mbi=1（2）（2）amodn=amodn=仪仪a仪modn=仪仪仪［aIf（（x+a）^n!=x^n+a（modx^r-1,n））bi=1bi=1modn］modnReturn0;Return1;这种方法就是快速指数算法，C语言算法描述如下：该算法主要分三个步骤：①主要判断n是否为某Main（）个数的幂次；②选择满足于定理假设的r，s；③本算法C=0;d=1;最耗时的，计算复杂度为O（log7.5+εn），这里ε为任意小For（i=k;i=0;i--）的正数，如果r为素数且r

8、n和（x-1）nnr=x-1mod（x-1，c=2*c

9、;2n），这时n为素数或n≡1mod（r），则算法的复杂度可d=d*d（modn）;降至O（log3+εn），由此看来Agrawal-Kayal-Saxnena算法Ifbi=1then具有很大的实用价值。c++;d=d*a（modn）;（2）快速找到素数p和qReturn（d）;在公钥密码体制中，因安全性的需要，常常需要不2.2素数检测法的快速实现同结构的素数，例如筛数法、Miller-Rabin、DSA中的素RSA算法基于素数理论，但目前还没有一种简单数等。筛选法的