简析RSA数据加密算法的分析与改进
- 格式：docx
- 大小：136.34 KB
- 文档页数：6
简析RSA数据加密算法的分析与改进
摘要：RSA加密算法中存在着大素数查找的问题，导致RSA运算速度缓慢。本文利用小素数筛值法、偶数排除法、小素数整除法等方法对伪素数进行了初步的剔除，然后利用米勒-拉宾法来进行素数的检测，从而大大地改善了对素数的探测效果。实验证明，与传统Miller-Rabin方法比较，该方法在较短的时间内产生大素数，而不是大素数的几率低于0.1%。因此，RSA的加密速度和RSA的可操作性都得到了改善。
关键词：RSA数据加密算法改进
引言：当前，信息化已成为社会发展的中心趋势，它作为一种重要的战略资源，随着互联网的发展突破了传统的空间和区域概念，使真正意义上的全球信息化逐渐呈现在我们的面前，但由于互联网的互联性、共享性和可开发性，假冒、篡改、泄露等一系列问题也需要我们去正面认识与解决。因此，网络时代确保信息安全始终是一个重要的课题。为了保障网络中的数据安全性，信息加密技术一定是最主要且最基础的保护方式。在大多数情况下，只有通过加密技术才能进一步确保网络中的数据通信安全。为了达到对资料数据的加密处理，一般可以采用多种加密算法技术。目前，已公布的加密算法主要有DESRC4和FEAL-N等，RSA是在1977年由RSA、AdiShamirh和LenAdleman三位科研人员在美国麻省理工大学开发的，而RSA命名是基于三个开发者的姓名组合和零知识证明算法等密钥算法所命名。在这些算法中，RSA算法是综合效果最佳的，对于它的普遍应用，以及更多被证实的安全性测试，本文都将针对此进行更深入的研究和完善，从而尽可能再提高它的性能，使RSA算法具备更佳的可操作性。
1公开RSA加密算法
RSA加密属于公开密钥加密算法，它自身具有很强的代表性，对于密钥来说，不论是加密，还是解密，在关联中都存在着些许的差异。在公开密钥算法里，加密密钥是透明化的，而对于此，解密密钥就具备鲜明的私有性。众所周知，对于公钥和私钥，在被包含的RSA加密算法里，它们具备对数据进行加密的时效性，理论上没有任何限制；而另一个关键在于对应的解密过程，无法从根本上进行密钥的相互的推导，那么在某种程度上就能更好地解决在传输过程中因密钥丢失而造成的安全隐患。其加密算法流程如下：
图1.RSA算法流程图
虽然RSA在数据加密方面表现出较好的性能。然而，在RSA加密算法中，更需要对其参数进行选取，以进一步提高其安全性。如果不正确地选取参数，不仅仅会导致算法的安全性下降，某种意义上算法更是一个漏洞。总体上，有关参数的选取应该符合下列三点：
（1）“p”和“q”不但要做强素数，还要足够大
RSA加密算法的安全性很大程度是采用p、q两个因素进行有效分解作为基础的，保证不能在运算中对系数进行分解，并且确保P、q是强素数。此外，在保证因式分解难度的前提下，增加RSA的安全系数，p和q的数值也要大，因为在实践中，选择的p和q通常都是10进位的强素数，其长度一般大于100。
（2）d不能够过小
在RSA中，解密密钥的数值愈低，其保密效能愈高。然而，若d太小，可以花费一点代价先求出明文，再通过明文来求出密钥。在RSA的算法实际使用中，通常是d>nt。 （3）e不能够过小
e越小，RSA的效率就越高，密钥的处理就会更简单，而e太小，就可以用C=mmodn的密码算法来破解。另外，假如密码密钥过小，还可以利用指数攻击来破译e。
2RSA加密算法存在的问题
RSA是一个很有代表性的公开密钥加密系统，它显著的特点是安全、易于操作。然而，它也有其局限性。
（1）为了得到密钥，必须进行相关大量运算，在进行加密和解密时，必须要先求出一个整模数n的整数倍。而由于RSA存在运算量大的因素，因而其在实际中的使用受到很大的制约。
（2）对于两个大素数p和q，至今并没有一个较好的办法来生成，而通常采用的复杂素数检验和随机产生算法来生成大素数，显然p和q的生成效果并不佳。
（3）通常采用较大的密钥量来确保RSA的安全，以提高RSA的抗穷举攻击性能。因为计算机运算能力的提高、因子分解算法的改进、还有一些实验都表明，1024bit对于提高RSA的抗性而尽可能解决数学攻击问题的n是不可靠的。为了保证密钥因子的系数分解难度，密钥通常要大于1024bit，而这在某种程度上将大大影响RSA的性能。当前，国内RSA加密算法的研究多以提高系统的有效性和安全性为目标，我们还应该重点考虑RSA加密算法的特征如何产生大素数，进而在某种意义上实现对于RSA加密算法的优化。
3安全大素数生成方式的改进
素数产生的关键在于确定一个数字是不是素数。现在产生素数的方式有两种：一是统计概率产生素数，二是确定性素数。通过对素数进行确定性产生的方法，可以确保所产生的素数为素数，但这样产生的素数存在着某种规律，攻击的人只需花费很少的成本就能得到这串资源素数的规律，继而破解。而想要得到更安全的素数，就必须耗费更多的运算开销，并且在运算过程中没有任何规则可言，相对于确定性产生素数，利用统计概率产生素数的方法更安全、更快捷。然而，用统计概率产生素数的办法通常会产生伪素数，RSA算法还必须检查产生素数的性质。通常情况下，对素数进行搜索、预处理和探测，为保证所产生的数字的素数性质，以保证RSA的安全，文中使用的是一种基于确定性的素数检测器来检查所产生的素数，以增加素数产生的概率。对素数素性检测的步骤如下所示：
（1）搜索
由于大素数的分布是不均匀的，并且其密度很低，为了提高对素数的检测效率，必须采用一种更好的搜索算法。当前常用的搜索方式是随机增量搜索和随机搜索。在已有的研究中，已证实随机增量搜索方法比随机搜索搜索次数要小，因此本文以随机增量搜索为主要方法实现对大素数的进一步查找。
（2）预处理
在随机的递增搜索中，需要检验出素数结果，检验的过程就需要大量的时间了。为了尽可能巧妙达到这一目的，通过预处理先行进一步对素数进行检验。它的基本步骤如下：采用小素数筛值法生成伪素点，传统的随机法会去除伪素数，采用小素数整除法对伪素数进行进一步的筛选，并采用米勒-拉宾法对应进行5次检测。
4RAS算法的优化
4.1RSA算法优化原则
因为在传统RSA中，基于大素数的因素对其进行分解极具困难，所以在常规RSA中，很难根据大量的素数因子来进行分解，（要在解密中求取大整数幂）。最佳化原理：
（1）为了增加安全性，最大素数p和q必须是大于100十进制数；
（2）e的正确减少可以加速破解，但过少则会对安全造成影响。
4.2优化RSA算法
（1）多因子优化 利用多个素数因子对算法进行加速，此处选取三个素数因子，可以降低素数选取需要的时间，通过中国剩余定理得出适当的减少素数的位数，可以降低计算量。那么基本算法描述如下：首先选择三个保密大素数：p、q及r。计算n=p*q*r,φ(n)=(p-1)(q-1)(r-1)，φ(n)为欧拉函数，选择整数e，有gcd(φ(n),e)=1，计算d*e=1modφ(n)，以{e,n}为公开钥，{p,q,r}为密钥，与常规 RSA相比，如果明文 m比 n更大，需要对 m进行分块，以便每个数据的块都比n-1小，然后再做 c= m^ emodn。
（2）幂指运算优化
由于传统的RAS方法中，索引码的比特位串长度较大，所以用最小指数索引码来缩短迭代数是提高算法速度的一种方式。然后利用2^ k进制化指数结合e来进一步加快算法模式。对于指数e可以用（2）等式表示出来：
那么在余数运算中，形如g^emod(m)可以如下表示：
（6）式中n为e被2k进制后的序列，其中m表示取模运算。伪代码算法描述如下：
上述共完成了2^k次迭代运算，接下来要进行幂剩余和乘通余运算，此步需完成n次迭代次数，其伪代码如下：
改进后算法流程图如下：
结语：在这个数据与产业紧密融合的年代，为了保证其安全性，必须对加密算法进行改善。本文给出了改进RSA的一种全新理论，在此基础上对该方法进行了模块幂次分解，并利用 CUDA对 GPU中的模块进行了加密解析。实验结果显示，与常规 BR方法相比，改进后的加密算法在 GPU上的运算效率得到了明显的提高。
参考文献：
[1]蒋翔,胡静.基于RSA算法的改进方法研究.工程技术研究,2018(11):251-252.
[2]陈鹏飞,何小东.RSA算法的分析与改进.电子世界,2015(13):111-113.
