一种改进的RSA算法的研究

科技信息　一计算机与网络　种改进昀ＲＳＡ算法昀研究　哈尔滨师范大学计算机科学与通信工程学院　吴迪　［摘要］Ｐ．ｓＡ算法在对数据加密和数字签名方面应用广泛。但ＲＳＡ算法在实现上较其他算法来讲具有实现速度慢的缺点。主要通　过对ＲＳＡ参数的选择及ＲＳＡ算法本身的优化两方面来提出一些改进措施，从一定程度上提高了ＲＳＡ算法的实现速度。　［关键词］数据加密技术密钥ＲＳＡ　０．引言　随着信息技术的日新月异及其广泛的普及和应用，计算机及其网　络的安全问题已经成为当今科技发展的一个全新的课题。　ＲＳＡ算法是当今所使用的当中最为成熟完善的各种公钥加密算　３．２另一种对ＲＳＡ公钥私钥加密算法的改进　根据上面传统的改进方式，可将ｘ的二进制值每四位进行一次运　算，根据上式　对于ｉ＝ｔ，ｔ一１，ｔ一２，……，１，０重复执行①②。　法，它其实已经成为当代公钥非对称加密算法的代表。现在所广泛使用　的各种加密安全产品以及相应的安全标准大多使用的都是ＲＳＡ公钥　加密算法。ＲＳＡ算法作为第一个可以用于数字签名的非对称加密算法，　对于解决密钥分配，身份认证和在日常的在线电子交易的应用有着极　为广泛的前景。但其自身的一些缺陷，如加密效率的低下所带来的矛盾　已经越加的尖锐。针对以上的缺点，笔者尝试进行改进。　１．ＲＳＡ算法的描述　１．１密钥的生成　１）生成两个互异的大素数Ｐ和ｑ，在实际的情况下大多使用随机数　生成器来生成随机数，再检查它们的互素性。考虑到抗破译需要，ＲＳＡ　要求Ｐ和ｑ为强素数。　２）计算模数ｎ＝ｐ　Ｘ　ｑ，ｕ（ｎ）＝（ｐ一１）（ｑ—１）（式中ｕ（ｎ）为欧拉函数值小　于Ｕ且与ｎ互素的正整数的个数）　３）选一正整数ｅ，ｅ满足ｌ＜ｅ＜ｕ（ｎ），且ｇｄｃ（Ｕ（ｎ），ｅ）＝１。　４）计算ｄ满足ｄ・ｅ＝１　ｍｏｄ　ｕ（ｎ）其中Ｉ１，ｅ为公钥，ｄ为私钥。　１．２加密　根据ＲＳＡ算法，要加密的明文为ｎｌ，加密后的密文为ｅ。加密的过　程为ｃ＝ｍ　ｍｏｄｆｎ），其中ｅ为加密公钥。　ｌ＿３解密　根据ＲＳＡ算法，ｍ＝ｅ　ｍｏｄ（ｎ），其中ｅ为公钥，ｄ为私钥。　２．ＲＳＡ算法的参数选择　在实际应用中，大多数的信息揭露以及破解不是由于破解了ＲＳＡ　系统，而是由于加密过程中的参数选择不当，因此为保证信息的安全性　和系统的安全性，ＲＳＡ算法的参数选择必须符合一定的标准。ＲＳＡ算法　的主要参数有三个：模数ｎ，加密密钥ｅ，解密ｄ。　２．１　ＲＳＡ算法的加密安全性的基础是ｎ＝ｐｘｑ，如果模数ｎ被分解，　就可以根据Ｐ和ｑ得到ｕ㈤，进而通过公钥ｅ得到解密ｄ，ＲＳＡ算法　加密解密系统将被完全破解。所以普遍的ＲＳＡ算法的破解攻击时分解　模数ｎ。　２．２　Ｐ、ｑ应为强素数，强素数是指ｐ＋ｌ或ｑ＋ｌ应有大素数因子。　２．３　Ｐ、ｑ之差要大（差几位之上）若Ｐ、ｑ之差很小，则可由ｎ＝ｐ・ｑ可　估计（ｐ＋ｑ）／２￣ｎ　又可知（（Ｐ＋ｑ）／２）２－ｎ＝（（ｐ－ｑ）／２）　两式联立方程可试探Ｐ，ｑ的值。　２．４　ｐ－１和ｑ一１的公因子要小。　２．５　Ｐ、ｑ要足够大，这是ＲＳＡ算法要遵循的最基本的原则，如果希　望算法安全，则ｎ＝ｐ・ｑ必须足够大，使得大数分解基本不可能。　３．ＲＳＡ算法的优化　３．１　ＲＳＡ算法的传统优化方法　通过ＲＳＡ算法的加密公式ｃ：ｍ　ｍｏｄ（ｎ）可知ＲＳＡ算法涉及一个整　数的幂运算然后进行取模运算。传统ＲＳＡ算法的幂剩余计算所用的时　间过长，已经成为广泛认同的ＲＳＡ算法的发展的瓶颈。而如果直接计　算指数，又会产生巨大的中间计算结果。传统的优化方式是利用取模运　算的一个特性：　Ｈａｍｏｄ　ｎ）ｘ　ｍｏｄｎ）】ｍｏｄ　ｎ＝（ａｘｂ）ｍｏｄ　ｎ　利用次公式构造平方求模算法，利用的是相乘后求模与重复平方　求模迭代的方式。具体的步骤如下（ａ＝ｇ＇ｍｏｄｐ为例）：　１）将ｘ的十进制数转化成二进制数　２）设ａ的初值是ｌ，ａ＝ｌ。　３）对于ｉ＝ｔ，ｔ一１，ｔ一２，……，１，０重复执行①②。　（ｊ）ａ＝ａＥ（ｍｏｄｐ）　②若ｘ＝ｌ则ａ＝ａｘ　ｇ（ｍｏｄｐ）　４）得到ａ结束。　以上的算法是每一步迭代对Ｐ求模，可以控制中间结果的大小。每　一次迭代需要二次乘法和二次求模总共需要ｌｏｇ￣ｘ次迭代。显然，２１ｏｇａｘ　次乘法和２１ｏｇａｘ次求模是影响算法实际速度的关键，传统的改进方式　是用以上的方式和ＳＭＭ算法相结合。　（￣）ａ＝ａ２（ｍｏｄｐ）　②若ｘ＝ｌ则ａ＝ａｘｇ（ｍｏｄｐ）　既若ｘ的四位二进制值为０００１则ａ＝　（ｍ０ｄｐ）＝【（（ａ２（ｍｏｄｐ））　（ｍｏｄｐ））　（ｍｏｄｐ）】×ｇ（ｍｏｄｐ）＝ａ　×ｇ（ｍｏｄｐ）　根据此式可将传统的方式具体改进为以下算法（使用类ｃ语言）：　１）将Ｘ的二进制数按每四位转化成１６进制数　ｉｎｔ　ａ＝ｌ：　ｓｅｌｅｃｔｘ　｛ｃａｓｅ　ｘ＝０　ａ＝ａＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅ　ｘ＝ｌ　ａ＝ａｓ×ｇ（ｍｏｄｐ）；ｂｒｅｈｋ；　ｅａｓｅ　ｘ＝２　ａ＝ａｓ×ｇ２（ｍｏｄｐ）；ｂｒｅａｋ；　ｃａｓｅ　ｘ＝３　ａ＝ａ８　Ｘ　ｇＺ（ｍｏｄｐ）；ｂｒｅａｋ；　ｃａｓｅ　ｘ＝４　ａ－－ａ　ｘ　ｍ０ｄｐ）；ｂｒｅａｋ；　ｃａｓｅ　ｘ＝５　ａ＝ａｓ　ｘ　ｄ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅ　ｘ＝６　ａ＝ａ８　Ｘ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅ　ｘ＝７　ａ：ａｓ　Ｘ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｃａｓｅ　ｘ＝８　ａ＝ａｓ　Ｘ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅ　ｘ＝９　ａ＝ａｓ　Ｘ　ｇＴ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅｘ＝Ａ　ａ＝ａｓ×ｇＴ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅｘ＝Ｂ　ａ＝ａ　ｘ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅｘ＝Ｃ　ａ＝ａｓ　ｇＴ（ｍｏｄｐ）；ｂｒｅａｋ；　ｃａｓｅｘ＝Ｄ　ａ＝ａｓ　Ｘ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｅａｓｅ　ｘ＝Ｅ　ａ＝ａｓ　ｇＳ（ｍｏｄｐ）；ｂｒｅａｋ；　ｃａｓｅ　ｘｍＦ　ａ＝ａｓ×ｇ９（ｍｏｄｐ）；ｂｒｅａｋ；　ｄｅｆａｕｌｔ；　Ｊ　２）ｘ的每位１６进制数重复以上步骤。　３）得到ａ结束。　此方法也可与ＳＭＭ算法相结合，在此笔者不再冗述。　４．结束语　通过合理的选择ＲＳＡ算法的参数以及对ＲＳＡ算法本身的优化，实　现了ＲＳＡ算法的速度的优化，使其在实际应用中更加具有可靠性和稳　定性。　参考文献　［１］施奈尔（美国）．《应用密码学（ｔｈｅ　２ｒｄ　ｅｄｉｔｉｏｎ）￣．北京：机械工业　出版社，２０００．　［２］冯登国，裴定一．《密码学引论》．科学出版社，１９９９．　［３］杨波．《现代密码学》．北京：清华大学出版社，２００３．　１４］Ｗａｇｎｅｒ　Ｎｅａｒ　Ｒ（（ｔｈｅ　ｌａｗｓ　ｏｆｔｈｅ　ｃｒｙｐｔｏｇｒａｐｈｙ））．２００４．　．．．——２２３．．．——