一种改进的大素数乘法的设计与实现_达斯孟.pdf
《一种改进的大素数乘法的设计与实现_达斯孟.pdf》由会员分享,可在线阅读,更多相关《一种改进的大素数乘法的设计与实现_达斯孟.pdf(3页珍藏版)》请在咨信网上搜索。
1、SOFTWARE软 件2023第 44 卷 第 1 期2023 年Vol.44,No.1作者简介:达斯孟(1986),男,蒙古族,内蒙古鄂尔多斯人,硕士研究生,高级工程师,研究方向:社保大数据应用与研究、非对称加密算法等。一种改进的大素数乘法的设计与实现达斯孟(鄂尔多斯市人力资源和社会保障局,内蒙古鄂尔多斯 017400)摘要:RSA 算法作为应用较为广泛的非对称加密算法,经过蒙哥马利模乘等算法的优化后主要基于有限域运算中大数的加法运算和乘法运算,数位规模通常在 1024 位甚至更高。大数的乘法运算随着参与运算位数的增加会导致 RSA 算法的运行时间效率下降。随着多核处理器架构的普及,如何在多
2、核多线程并行运算背景下提高 RSA 算法效率就成为解决 RSA 算法性能瓶颈的关键。本文通过多核并行运算背景下分析大数乘法算法从而提出一种改进的适应多核运算的大数相乘算法,依靠此算法提高 RSA 算法和大规模科学计算中高精度浮点数运算效率。关键词:非对称加密算法;RSA;大数乘法运算;COMBA 算法中图分类号:TP393 文献标识码:A DOI:10.3969/j.issn.1003-6970.2023.01.027本文著录格式:达斯孟.一种改进的大素数乘法的设计与实现J.软件,2023,44(01):104-106Design and Implementation of an Improv
3、ed Multiplication of Large Prime Numbers DA Simeng(Ordos Human Resources and Social Security Bureau,Ordos Inner Mongolia 017400)【Abstract】:As a widely used asymmetric encryption algorithm,the RSA algorithm is mainly based on the addition and multiplication of large numbers in finite field operations
4、 after the optimization of Montgomery modular multiplication and other algorithms.The digital scale is usually 1024 bits or even higher.The multiplication of large numbers will lead to a decrease in the running time efficiency of the RSA algorithm as the number of bits involved in the operation incr
5、eases.With the popularization of multi-core processor architecture,how to improve the efficiency of RSA algorithm in the context of multi-core and multi-thread parallel computing has become the key to solving the performance bottleneck of RSA algorithm.This paper analyzes the multiplication algorith
6、m of large numbers in the context of multi-core parallel computing,and proposes an improved multi-core multiplication algorithm for large numbers.Relying on this algorithm,it improves the efficiency of high-precision floating-point arithmetic in RSA algorithm and large-scale scientific computing.【Ke
7、y words】:asymmetric encryption algorithm;RSA;big integer multiplication;COMBA algorithm设计研究与应用0 引言RSA 密码算法作为迄今最成熟最广泛应用的公钥密码体制,由于其安全性高、抗数学攻击能力强等优点而被广泛用于 SoC 智能芯片等各领域1。RSA 算法的安全性是基于数论和计算复杂性理论,即计算两个大素数乘积是十分容易的,但是想要很快将两个大素数的乘积分解,求出它的因子在计算上是困难的,至今还没有一种方法能够很好地将其破解2。计算机科学领域近年来涌现出了很多关于 RSA 算法研究,包括了软件和硬件领域。作
8、为 RSA 算法的提出人Rivest 提出了硬件思路,而 Shamir and Adleman 则提出了先进的模运算的算法3。RSA 加密算法迄今为止已经成功商业运营超过 40 年,由于计算性能和 RSA 算法研究的深入进行,在 2001 年 Lenstra and Verheul 得出结论表明如果想要在 2040 年仍然确保 RSA 算法的安全性,就要将目前流行的 1024 位的秘钥扩大三倍4。随着多核多线程架构的诞生和普遍使用。由于 RSA 算法的使用范围非常广泛,且很多项目并没有专门针对 RSA算法的硬件加速器支持,因此本文聚焦在多核并行计算背景下从纯软件角度提升 RSA 算法运行的时间
9、性能。105达斯孟:一种改进的大素数乘法的设计与实现RSA 算法的运行性能的关键点在于模幂运算即C=Me mod n 和 M=Cd mod n。模幂运算通常会被分解为一系列的模乘运算实现优化。许多现代密码学算法都强烈依赖于对大整数的模运算,所需大整数通常是素数或两个素数的乘积。因此提升 RSA 算法性能相关研究的一个重点方向在于有限域中如何提升大数运算性能。在模幂运算中通常有大概 25%的运算时间用于乘法操作5,因此近年来关于大数相乘算法的研究一直是 RSA算法性能提升的重点。提高加密算法效率的一种有效方式是在有限域中提高大数乘法的效率6。目前软件提高大整数乘法算法的研究主要集中在两方面:(1
10、)基于现有大数乘法运算较为成熟的算法例如基线算法、Karatsuba 算法、Toom-Cook3算法进行算法优化和性能调优;(2)随着多核多线程CPU 的普及,通过提高算法的并行度进而提升算法的时间性能。本文结合上述两种研究思路,通过引入一种更适应多核多线程运算规则的大数乘法算法,从而提高整个 RSA 算法的运行时间效率。1 大数相乘算法效率比较与改进的大数相乘算法目前的处理器对于二进制数位的移位运算会比乘法要快很多,因此可以使用左移位操作代替乘以 2 的次幂,乘以不同数的乘法也可以用一连串的移位和加减法来代替。大数相乘的算法主要有基线算法、傅立叶相乘算法、Karatsuba 乘法、Toom-
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 一种 改进 素数 乘法 设计 实现 达斯孟
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。