RSA密码系统
- 提出者
- Ronald Rivest
- 年份
- 1978
- 类型
- asymmetric encryption algorithm
- 类别
- Public-key cryptography
本文为机器翻译,尚未经过审校。 阅读英文原文
它有什么作用?
RSA是由Rivest、Shamir和Adleman于1978年开发的一种基础公钥密码系统。它通过使用一对数学上相关联的密钥来实现安全加密和数字签名:公钥用于加密,私钥用于解密。RSA的安全性依赖于分解大合数为其素因数的计算难度。
方法背后的直觉
RSA基于一个简单的数学原理:将两个大素数相乘很容易,但通过分解它们的乘积来逆转这个过程却极其困难。每个用户从两个大素数的乘积中生成两个密钥。公钥公开共享,用于加密消息;私钥保密,用于解密消息。其安全性在于,如果不知道素因数,攻击者就无法从公钥实际推导出私钥。
历史学
RSA于1978年发布,成为首批实用的公钥密码系统之一。它通过实现无需预共享密钥的安全通信,从根本上改变了密码学。该算法在美国曾获得专利直至2000年,之后进入公共领域。近五十年来,RSA一直受到持续的分析和改进,现代变体采用了填充方案和更大的密钥长度来应对不断演变的攻击。
何时使用
RSA适用于加密少量数据、建立安全通道和创建数字签名。它常用于TLS/SSL协议、电子邮件加密(PGP)和证书颁发机构。RSA需要仔细的填充方案(加密使用OAEP,签名使用PSS)才能保证安全。现代实现应使用至少2048位的密钥长度,以应对当前计算能力提供合理的安全性。
局限与注意事项
- 与对称加密相比计算成本高;通常用于密钥交换而非批量数据加密
- 为保证足够安全性,密钥长度必须较大(2048位或更高),这使得加密和解密比对称算法慢
- 如果量子计算机得以实用化,将易受攻击,需要后量子替代方案
来源中的条件不能替代独立的科学审查或分析引擎的验证。
优势
- 在平台和库中得到广泛标准化和支持
- 使用同一密钥对即可实现加密和数字签名生成
- 基于分解问题的数学优雅基础
- 向后兼容数十年的现有基础设施
应用
- 用于保护网络通信和电子商务的HTTPS和TLS/SSL协议
- 用于加密电子邮件消息的PGP和S/MIME
- 用于在线身份认证的数字证书和公钥基础设施(PKI)
- 区块链系统和加密货币的交易签名和验证
- 智能卡认证和政府身份证加密
- 用于企业密钥管理的安全硬件模块(HSM)
使用方式
使用方式
选择两个大的不同素数p和q,计算它们的乘积n = p × q,计算欧拉函数φ(n) = (p-1)(q-1),选择一个与φ(n)互素的整数e,满足1 < e < φ(n),计算d使得e × d ≡ 1 (mod φ(n))。公钥是(e, n),私钥是(d, n)。
要加密消息m,计算密文c = m^e mod n,其中e和n是接收者的公钥。
要解密密文c,计算明文m = c^d mod n,其中d和n是私钥。
数字签名是通过用私钥加密消息的哈希值来创建的,并通过用公钥解密来验证,以确认哈希值是否匹配。
常见陷阱
- 未使用RSA的正确填充方案(OAEP或PSS)可能使算法暴露于各种攻击
- 将同一RSA密钥同时用于加密和签名操作会增加攻击面;倾向于使用专用密钥对
- 不正确的素数生成或密钥生成中的弱随机性可能完全破坏安全性
常见问题
为什么RSA比AES等对称加密慢?
RSA涉及非常大的数字(2048位或更大)的模幂运算,这比AES高效的字节级操作需要多出几个数量级的计算量。实际上,RSA用于加密一个小的密钥,然后该密钥再用AES加密大量数据。
如果有人分解了我的公钥模数n会怎样?
如果攻击者将n分解为其素因数p和q,他们就可以计算φ(n),然后从你的公钥指数e推导出你的私钥d。这就是为什么使用足够大的素数和密钥长度至关重要。
没有私钥是否可以伪造RSA签名?
使用正确填充(PSS)的签名则不行。然而,未填充或填充不当的RSA签名容易受到各种数学攻击。务必使用标准填充方案。
2026年RSA是否仍然安全?
对于经典计算机而言,2048位密钥的RSA仍然被认为是安全的,尽管建议使用4096位密钥以获得长期安全性。然而,如果量子计算机大规模构建,RSA将易受攻击,因此后量子密码学的研究正在积极进行中。
如何选择合适的素数p和q?
使用密码学安全的随机数生成器生成大数,然后使用Miller-Rabin测试等算法测试其素性。现代库会自动处理这些问题。
相关方法
参考文献
Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.
打开 DOI 文献已复制。Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.
ISBN:978-0387966618已复制。