RSA科普-大质数生成算法与公钥指数的选取
1、大质数生成算法
如何生成这两个大质数，这是个值得研究的问题。首先可以想到的是生成质数序列，从中随机选取2个大质数即可。一种改进的方法是: 除了2外的偶数肯定不是质数，而奇数可能是质数，可能不是，那就可以跳过2与3的倍数，即对于6n，6n+1, 6n+2, 6n+3, 6n+4, 6n+5，我们只需要判断6n+1与6n+5是否是质数即可。而判断某个数m是否是质数，最基本的方法就是对2到m-1之间的数除m，如果有一个数能够整除m，则m就不是质数。判断m是否是质数还可以进一步改进，只需要对2到根号√m之间的数除m就可以。继续优化，其实只用2到√m之间的质数去除即可。上面生成大质数是很基础的方法，效率比较低，一般会采用更快的方式，比如随机生成一个nbits位的奇数p，然后从p 开始遍历之后的奇数，并通过Miller–Rabin质数判定算法对遍历到的数字进行质数判定，如果是质数，即可返回(当然，该算法有一定的误判率，不过在判定次数设置够大的情况下，误判率基本可以忽略)。
2、公钥指数的选取
公钥指数是可以随意选取的，但是为了提高RSA的加密速度实际使用中公钥指数最长用的三个值是3、17、65537(=2^16+1，65537的二进制表示中只有两个1，所以需要17次乘法来实现指数运算)。PEM建议用3，PKCS#1建议用3或65537，X.509建议用65537。这样选取主要是为了提高加密或签名验证的性能，因为3、17或65537分别只需要2或17次模乘运算，而一个随机选择的e（假设n是1024-bit）则大约需要1000次模乘运算。这种方法刻意把公钥指数选的小一点，其对应私钥指数就会很大，这么做的目的是节约公钥运算的时间。因为正常使用中都是用公钥加密，所以需要节约大部分人的时间，而极少部分人也会选用私钥解密，那么就只能少数服从多数了。在选用公钥指数时，人们普遍会认为3和17没有65537安全。然而这种想法并没有合理的依据。实际上采用这三个值中的任何一个都不存在安全问题。前提是使用正确的填充方案。
3、RSA公私钥生成流程
(1)选择两个不同的大素数p和q；
(2)计算公共模数（n=pq）和欧拉数（eular=(p-1)(q-1)）；
(3)选择公钥指数e；
(4)计算inverse（d）；
(5)生成公钥、私钥。
- |
- +1 赞 0
- 收藏
- 评论 0
本文由ll转载自凌科芯安加密芯片公众号，原文标题为:RSA科普——大质数与指数选取，本站所有转载文章系出于传递更多信息之目的，且明确注明来源，不希望被转载的媒体或个人可与我们联系，我们将立即进行删除处理。
相关推荐
【技术】PEM格式RSA密钥解析（一）——Base64转16进制格式
本文介绍如何将BASE64编码转换16进制。
【技术】PEM格式RSA密钥解析（二）——RSA密钥参数
上一部分讲解了将Base64编码的密钥数据转换成hex格式数据，本章将介绍如何获从转码后的数据中获取RSA密钥的相关参数。
【技术】ECDSA签名算法及其原理，签名及验证过程详解
关于ECDSA签名算法您有哪些了解？本文凌科芯安将针对ECDSA签名算法及其原理，签名及验证过程进行介绍。
凌科芯安LKT/LCS系列版权保护芯片方案简介
本文介绍了凌科芯安LKT/LCS系列版权保护芯片的几种方案，包括对比认证方案、参数保护方案、算法移植方案和混合加密方案。
【经验】凌科芯安LKT/LCS系列IIC接口加密芯片调试常见问题及解决方法
凌科芯安定位在嵌入式数据安全领域，产品涵盖了嵌入式数据加解密及版权保护芯片、智能卡、软件加密锁、加密存储产品、读写机具以及密钥安全系统的定制开发服务。本文基于LKT/LCS系列加密芯片，介绍芯片调试中经常遇到的问题及解决方法。
【经验】凌科芯安带你了解常用国密算法：SM1（SCB2）、SM2、SM3、SM4、SM7
国密算法是国家商用密码管理办公室制定的一系列密码标准，包括SM1（SCB2）、SM2、SM3、SM4、SM7、SM9、祖冲之密码算法（ZUC)等等。在终端设备上通常需要使用内嵌国密算法的安全芯片配合使用，倚靠安全芯片的安全性来实现密钥的存储和安全防护。
FLASH数据丢失原因分析及解决方案
本文中凌科芯安来为大家介绍FLASH数据丢失原因分析及解决方案，希望对各位工程师朋友有所帮助。
凌科芯安的LCS4110A可以用在医疗耗材上吗？
只要是数据加密或者尤其是程序防盗版都可以用，车用电子、智能眼镜、车载诊断设备、游戏手柄、医疗耗材、移动互联、智能网关、打印耗材、工业控制、智能门锁、智能楼宇、工业喷码、人脸识别、工业相机、智能家居。
探讨加密芯片在AI领域的应用与推广
随着人工智能（AI）技术的快速发展，数据安全与隐私保护成为了各行各业关注的焦点。加密芯片作为硬件层面的安全保障，正在AI领域中发挥着越来越重要的作用。本文凌科芯安将探讨加密芯片在AI领域的应用，并分析其对AI安全性、效率及未来发展的影响。
【产品】8位IIC接口防盗版加密芯片LKT4106 ，支持DES、SHA1等国际标准加密算法
凌科芯安推出的8位IIC接口防盗版加密芯片LKT4106，以8位安全芯片平台为基础，内部嵌入凌科芯安公司的LKCOS智能操作系统，通讯速度最高可达400Kbps。支持DES、SHA1等国际标准加密算法，用户可将自定义关键算法下载到芯片中运行，从而实现产品防盗版、身份认证、数据加解密等功能。
【产品】支持SM1/2/3/4/7算法的加密芯片LKT4305-GM，具有32位CPU内核及操作系统
LKT4305-GM是凌科芯安科技（北京）有限公司行业内开发的以32位安全处理器为基础的具有高性能高安全性的国密算法加密产品。加密芯片满足商密安全检测标准 GM/T 0008-2012《安全芯片密码检测标准》安全等级第二级。
分组对称算法中常用的PKCS7数据填充介绍
在数据加解密应用中，数据填充是其中重要的组成部分。数据填充通常有两个作用一是按要求将数据补足到分组块长度来满足加密算法的应用需求；二是通过增加填充数据来进一步提高密文的安全性。本文凌科芯安主要介绍分组对称算法中常用的PKCS7。
LKT4305GM 32 位高端 SPI/I2C 接口国密芯片数据手册
描述- 该资料为凌科芯安科技（北京）有限公司生产的LKT4305GM 32位高端SPI/I2C接口国密芯片的数据手册。文档介绍了芯片的特点、引脚说明、工作条件和应用电路，包括I2C和SPI两种接口的使用方法。
型号- LKT4305GM
【IC】LKT4202UGM安全芯片符合EAL4+安全等级设计要求、功耗低，智能门锁设备首选安全解决方案
凌科芯安LKT4202UGM是以32位安全CPU内核为基础的高性价比安全芯片，符合EAL4+安全等级设计要求，支持低功耗，自带DES/TDES硬件协处理器，同时支持SM2协处理器、SM3协处理器、SM4协处理器。
电子商城
授权代理品牌：集成电路
授权代理品牌：分立元件
授权代理品牌：接插件及结构件
授权代理品牌：部件、组件及配件
授权代理品牌：电源及模块
授权代理品牌：电子材料
授权代理品牌：仪器仪表及测试配组件
授权代理品牌：电工工具及材料
授权代理品牌：机械电子元件
授权代理品牌：加工与定制
我要提问
登录 | 立即注册
提交评论