RSA科普-大质数生成算法与公钥指数的选取

时间： 2024-08-12 来源：凌科芯安加密芯片公众号

技术问答

选型帮助

研发客服

商务客服

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科普——大质数与指数选取，本站所有转载文章系出于传递更多信息之目的，且明确注明来源，不希望被转载的媒体或个人可与我们联系，我们将立即进行删除处理。

全部评论（0）

暂无评论

【技术】PEM格式RSA密钥解析（二）——RSA密钥参数

上一部分讲解了将Base64编码的密钥数据转换成hex格式数据，本章将介绍如何获从转码后的数据中获取RSA密钥的相关参数。

技术探讨发布时间 : 2023-02-08

【技术】PEM格式RSA密钥解析（一）——Base64转16进制格式

本文介绍如何将BASE64编码转换16进制。

技术探讨发布时间 : 2023-01-11

探讨加密芯片在AI领域的应用与推广

随着人工智能（AI）技术的快速发展，数据安全与隐私保护成为了各行各业关注的焦点。加密芯片作为硬件层面的安全保障，正在AI领域中发挥着越来越重要的作用。本文凌科芯安将探讨加密芯片在AI领域的应用，并分析其对AI安全性、效率及未来发展的影响。

技术探讨发布时间 : 2024-11-06

【经验】凌科芯安LKT/LCS系列IIC接口加密芯片调试常见问题及解决方法

凌科芯安定位在嵌入式数据安全领域，产品涵盖了嵌入式数据加解密及版权保护芯片、智能卡、软件加密锁、加密存储产品、读写机具以及密钥安全系统的定制开发服务。本文基于LKT/LCS系列加密芯片，介绍芯片调试中经常遇到的问题及解决方法。

设计经验发布时间 : 2023-08-22

【技术】ECDSA签名算法及其原理，签名及验证过程详解

关于ECDSA签名算法您有哪些了解？本文凌科芯安将针对ECDSA签名算法及其原理，签名及验证过程进行介绍。

技术探讨发布时间 : 2022-06-05

分组对称算法中常用的PKCS7数据填充介绍

在数据加解密应用中，数据填充是其中重要的组成部分。数据填充通常有两个作用一是按要求将数据补足到分组块长度来满足加密算法的应用需求；二是通过增加填充数据来进一步提高密文的安全性。本文凌科芯安主要介绍分组对称算法中常用的PKCS7。

技术探讨发布时间 : 2024-10-22

【经验】凌科芯安带你了解常用国密算法：SM1（SCB2）、SM2、SM3、SM4、SM7

国密算法是国家商用密码管理办公室制定的一系列密码标准，包括SM1（SCB2）、SM2、SM3、SM4、SM7、SM9、祖冲之密码算法（ZUC)等等。在终端设备上通常需要使用内嵌国密算法的安全芯片配合使用，倚靠安全芯片的安全性来实现密钥的存储和安全防护。

设计经验发布时间 : 2022-06-02

凌科芯安的LCS4110A可以用在医疗耗材上吗？

只要是数据加密或者尤其是程序防盗版都可以用，车用电子、智能眼镜、车载诊断设备、游戏手柄、医疗耗材、移动互联、智能网关、打印耗材、工业控制、智能门锁、智能楼宇、工业喷码、人脸识别、工业相机、智能家居。

技术问答发布时间 : 2024-07-29

【IC】LKT4202UGM安全芯片符合EAL4+安全等级设计要求、功耗低，智能门锁设备首选安全解决方案

凌科芯安LKT4202UGM是以32位安全CPU内核为基础的高性价比安全芯片，符合EAL4+安全等级设计要求，支持低功耗，自带DES/TDES硬件协处理器，同时支持SM2协处理器、SM3协处理器、SM4协处理器。

产品发布时间 : 2024-08-03

【产品】8位IIC接口防盗版加密芯片LKT4106 ，支持DES、SHA1等国际标准加密算法

凌科芯安推出的8位IIC接口防盗版加密芯片LKT4106，以8位安全芯片平台为基础，内部嵌入凌科芯安公司的LKCOS智能操作系统，通讯速度最高可达400Kbps。支持DES、SHA1等国际标准加密算法，用户可将自定义关键算法下载到芯片中运行，从而实现产品防盗版、身份认证、数据加解密等功能。

产品发布时间 : 2022-06-06

【产品】支持SM1/2/3/4/7算法的加密芯片LKT4305-GM，具有32位CPU内核及操作系统

LKT4305-GM是凌科芯安科技（北京）有限公司行业内开发的以32位安全处理器为基础的具有高性能高安全性的国密算法加密产品。加密芯片满足商密安全检测标准 GM/T 0008-2012《安全芯片密码检测标准》安全等级第二级。

产品发布时间 : 2022-05-25

凌科芯安的LCS4110A加密芯片支持多大的容量，温度参数怎么样？

32位内核，25M内频，IIC接口，待机低功耗0.1uA，28KB程序存储区，4KB数据存储区，1.75B RAM，-45℃到零上85℃嵌入式代码程序移植（超高安全性，自主版权保护，具备专利证书），3DES/AES认证（快速认证），参数保护（参数+3DES/AES动态防护）多种方案，可定制方案。

技术问答发布时间 : 2024-07-29

凌科芯安（LINK CORESAFE）加密芯片选型指南

描述- 凌科芯安科技（北京）有限公司成立于2006年1月，公司定位在嵌入式数据安全领域，产品涵盖了嵌入式数据加解密及版权保护芯片、智能卡、软件加密锁、加密存储产品、读写机具以及密钥安全系统的定制开发服务。全部产品以LKCOS智能操作系统为核心，为合作伙伴提供产品数据安全方面的解决方案。

型号- LKT4110U,LCS6810,LCS4110A,LKT4105U,LKT4200HS

选型指南 - 凌科芯安 - 2022/5/17 PDF 中文下载

【IC】高性价比国产安全MCU——LKT6850，最高工作频率48MHz，供电电压2.5~5.5V

LKT6850是一款以32位ARMCortexTM -M0处理器内核为基础的高性价比安全MCU。LKT6850具有最高64KBFlash、4KBRAM、48MHZ工作频率，具有丰富的外设资源供开发人员使用。芯片可实现DES/TDES/AES/SM4等对称算法，可实现多种安全身份认证、数据加解密等功能。该产品广泛应用于各种产品和行业中，能实现防止产品被破解、盗版等问题从而保护产品开发商知识产权。

产品发布时间 : 2024-05-01