Skip to content
返回搜索结果

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)

使用方式

使用方式

1

选择两个大的不同素数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)。

2

要加密消息m,计算密文c = m^e mod n,其中e和n是接收者的公钥。

3

要解密密文c,计算明文m = c^d mod n,其中d和n是私钥。

4

数字签名是通过用私钥加密消息的哈希值来创建的,并通过用公钥解密来验证,以确认哈希值是否匹配。

常见陷阱

  • 未使用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测试等算法测试其素性。现代库会自动处理这些问题。

相关方法

参考文献

  1. 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 文献
    已复制。
  2. Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.

    ISBN:978-0387966618
    已复制。