RSA 密码系统——概念

RSA 密码系统)是最早的公钥密码系统之一，其基础是模幂运算的数学原理，以及RSA 问题和与之密切相关的整数分解问题（IFP）所具有的计算难度。RSA 算法以其作者姓氏的首字母命名（Rivest–Shamir–Adleman），并在计算机密码学的早期得到广泛应用。

后来，随着 ECC 密码学的发展，由于它比 RSA 具有更高的安全性和更短的密钥长度，ECC 逐渐在非对称密码系统中占据主导地位。

RSA 算法提供以下功能：

  • 密钥对生成：生成随机私钥（通常为 1024-4096 位）及其对应的公钥。
  • 加密：使用公钥加密秘密消息（范围为 [0...n) 的整数），再使用私钥将其解密。
  • 数字签名：对消息进行签名（使用私钥），并验证消息签名（使用公钥）。
  • 密钥交换：安全传输秘密密钥，供后续加密通信使用。

RSA 可以使用不同长度的密钥：1024、2048、3072、4096、8192、16384 位，甚至更长。3072 位及以上的密钥被认为是安全的。更长的密钥提供更高的安全性，但会消耗更多计算时间，因此需要在安全性和速度之间进行权衡。非常长的 RSA 密钥（例如 50000 位或 65536 位）可能慢到不适合实际使用，例如密钥生成可能需要几分钟到几小时。

RSA 密钥生成

生成 RSA 公钥 + 私钥对包括以下步骤：

通过一些并不简单的数论数学计算#Key_generation)，找出三个非常大的整数 e、d 和 n，使其满足：

  • (m^e)^d ≡ m (mod n)，其中 m 的取值范围为 [0...n)

整数 n 称为“模数”，它决定 RSA 的密钥长度。它通常是两个大素数的乘积（例如 2048 位）。

数对 {n, e} 是公钥，其设计用途是公开给所有人。数 e 称为“公钥指数”，通常为 65537 (0x010001)。

数对 {n, d} 是私钥，其设计用途是保密保存。从公钥 {n, e} 计算出私钥在实践中不可行。数 d 称为“私钥指数”（秘密指数）。

RSA 公钥——示例

下面是一个 2048 位 RSA 公钥的示例（表示为 2048 位十六进制整数模数 n 和 17 位公钥指数 e）：

n = 0xa709e2f84ac0e21eb0caa018cf7f697f774e96f8115fc2359e9cf60b1dd8d4048d974cdf8422bef6be3c162b04b916f7ea2133f0e3e4e0eee164859bd9c1e0ef0357c142f4f633b4add4aab86c8f8895cd33fbf4e024d9a3ad6be6267570b4a72d2c34354e0139e74ada665a16a2611490debb8e131a6cffc7ef25e74240803dd71a4fcd953c988111b0aa9bbc4c57024fc5e8c4462ad9049c7f1abed859c63455fa6d58b5cc34a3d3206ff74b9e96c336dbacf0cdd18ed0c66796ce00ab07f36b24cbe3342523fd8215a8e77f89e86a08db911f237459388dee642dae7cb2644a03e71ed5c6fa5077cf4090fafa556048b536b879a88f628698f0c7b420c4b7
e = 0x010001

使用传统 RSA 格式 PKCS#8 PEM ASN.1 编码后，同一个 RSA 公钥如下所示：

-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEApwni+ErA4h6wyqAYz39p
f3dOlvgRX8I1npz2Cx3Y1ASNl0zfhCK+9r48FisEuRb36iEz8OPk4O7hZIWb2cHg
7wNXwUL09jO0rdSquGyPiJXNM/v04CTZo61r5iZ1cLSnLSw0NU4BOedK2mZaFqJh
FJDeu44TGmz/x+8l50JAgD3XGk/NlTyYgRGwqpu8TFcCT8XoxEYq2QScfxq+2FnG
NFX6bVi1zDSj0yBv90uelsM226zwzdGO0MZnls4AqwfzayTL4zQlI/2CFajnf4no
agjbkR8jdFk4je5kLa58smRKA+ce1cb6UHfPQJD6+lVgSLU2uHmoj2KGmPDHtCDE
twIDAQAB
-----END PUBLIC KEY-----

可以在此处解码上述包含 RSA 公钥的 PEM ASN.1 编码消息：https://lapo.it/asn1js。

RSA 私钥——示例

下面是与上述公钥对应的 2048 位 RSA 私钥示例（表示为十六进制 2048 位整数模数 n 和 2048 位秘密指数 d）：

n = 0xa709e2f84ac0e21eb0caa018cf7f697f774e96f8115fc2359e9cf60b1dd8d4048d974cdf8422bef6be3c162b04b916f7ea2133f0e3e4e0eee164859bd9c1e0ef0357c142f4f633b4add4aab86c8f8895cd33fbf4e024d9a3ad6be6267570b4a72d2c34354e0139e74ada665a16a2611490debb8e131a6cffc7ef25e74240803dd71a4fcd953c988111b0aa9bbc4c57024fc5e8c4462ad9049c7f1abed859c63455fa6d58b5cc34a3d3206ff74b9e96c336dbacf0cdd18ed0c66796ce00ab07f36b24cbe3342523fd8215a8e77f89e86a08db911f237459388dee642dae7cb2644a03e71ed5c6fa5077cf4090fafa556048b536b879a88f628698f0c7b420c4b7
d = 0x10f22727e552e2c86ba06d7ed6de28326eef76d0128327cd64c5566368fdc1a9f740ad8dd221419a5550fc8c14b33fa9f058b9fa4044775aaf5c66a999a7da4d4fdb8141c25ee5294ea6a54331d045f25c9a5f7f47960acbae20fa27ab5669c80eaf235a1d0b1c22b8d750a191c0f0c9b3561aaa4934847101343920d84f24334d3af05fede0e355911c7db8b8de3bf435907c855c3d7eeede4f148df830b43dd360b43692239ac10e566f138fb4b30fb1af0603cfcf0cd8adf4349a0d0b93bf89804e7c2e24ca7615e51af66dccfdb71a1204e2107abbee4259f2cac917fafe3b029baf13c4dde7923c47ee3fec248390203a384b9eb773c154540c5196bce1

使用传统 RSA 格式 PKCS#8 PEM ASN.1 编码后，同一个 RSA 私钥看起来稍长一些：

-----BEGIN RSA PRIVATE KEY-----
MIIEowIBAAKCAQEApwni+ErA4h6wyqAYz39pf3dOlvgRX8I1npz2Cx3Y1ASNl0zf
hCK+9r48FisEuRb36iEz8OPk4O7hZIWb2cHg7wNXwUL09jO0rdSquGyPiJXNM/v0
4CTZo61r5iZ1cLSnLSw0NU4BOedK2mZaFqJhFJDeu44TGmz/x+8l50JAgD3XGk/N
lTyYgRGwqpu8TFcCT8XoxEYq2QScfxq+2FnGNFX6bVi1zDSj0yBv90uelsM226zw
zdGO0MZnls4AqwfzayTL4zQlI/2CFajnf4noagjbkR8jdFk4je5kLa58smRKA+ce
1cb6UHfPQJD6+lVgSLU2uHmoj2KGmPDHtCDEtwIDAQABAoIBABDyJyflUuLIa6Bt
ftbeKDJu73bQEoMnzWTFVmNo/cGp90CtjdIhQZpVUPyMFLM/qfBYufpARHdar1xm
qZmn2k1P24FBwl7lKU6mpUMx0EXyXJpff0eWCsuuIPonq1ZpyA6vI1odCxwiuNdQ
oZHA8MmzVhqqSTSEcQE0OSDYTyQzTTrwX+3g41WRHH24uN479DWQfIVcPX7u3k8U
jfgwtD3TYLQ2kiOawQ5WbxOPtLMPsa8GA8/PDNit9DSaDQuTv4mATnwuJMp2FeUa
9m3M/bcaEgTiEHq77kJZ8srJF/r+OwKbrxPE3eeSPEfuP+wkg5AgOjhLnrdzwVRU
DFGWvOECgYEAyIk7F0S0AGn2aryhw9CihDfimigCxEmtIO5q7mnItCfeQwYPsX72
1fLpJNgfPc9DDfhAZ2hLSsBlAPLUOa0Cuny9PCBWVuxi1WjLVaeZCV2bF11mAgW2
fjLkAXT34IX+HZl60VoetSWq9ibfkJHeCAPnh/yjdB3Vs+2wxNkU8m8CgYEA1Tzm
mjJq7M6f+zMo7DpRwFazGMmrLKFmHiGBY6sEg7EmoeH2CkAQePIGQw/Rk16gWJR6
DtUZ9666sjCH6/79rx2xg+9AB76XTFFzIxOk9cm49cIosDMk4mogSfK0Zg8nVbyW
5nEb//9JCrZ18g4lD3IrT5VJoF4MhfdBUjAS1jkCgYB+RDIpv3+bNx0KLgWpFwgN
Omb667B6SW2ya4x227KdBPFkwD9HYosnQZDdOxvIvmUZObPLqJan1aaDR2Krgi1S
oNJCNpZGmwbMGvTU1Pd+Nys9NfjR0ykKIx7/b9fXzman2ojDovvs0W/pF6bzD3V/
FH5HWKLOrS5u4X3JJGqVDwKBgQCd953FwW/gujld+EpqpdGGMTRAOrXqPC7QR3X5
Beo0PPonlqOUeF07m9/zsjZJfCJBPM0nS8sO54w7ESTAOYhpQBAPcx/2HMUsrnIj
HBxqUOQKe6l0zo6WhJQi8/+cU8GKDEmlsUlS3iWYIA9EICJoTOW08R04BjQ00jS7
1A1AUQKBgHlHrV/6S/4hjvMp+30hX5DpZviUDiwcGOGasmIYXAgwXepJUq0xN6aa
lnT+ykLGSMMY/LABQiNZALZQtwK35KTshnThK6zB4e9p8JUCVrFpssJ2NCrMY3SU
qw87K1W6engeDrmunkJ/PmvSDLYeGiYWmEKQbLQchTxx1IEddXkK
-----END RSA PRIVATE KEY-----

它包含完整的 RSA 密钥对结构以及若干附加参数：2048 位模数 n、24 位公钥指数 e、2048 位秘密指数 d、第一个因子 p、第二个因子 q，以及 RSA 内部数据结构中的另外 3 个整数：

可以在此处解码上述包含 RSA 私钥数据的 PEM ASN.1 编码消息：https://lapo.it/asn1js。

RSA 密码学：加密消息

使用某个 RSA 公钥 {n, e} 加密消息时，执行以下变换：

  • encryptedMsg = msg^e mod n

这里的 msg 是范围 [0...n) 内的一个数。文本消息应在加密前编码为整数，且取值范围为 [0...n)（参见 OAEP）。对于较长的文本，应使用混合加密（加密一个秘密密钥，再用它对称加密文本，参见 RSA-KEM）。

上述操作不可逆：不存在高效算法能够根据 encryptedMsg、e 和 n 计算出 msg（参见 RSA 问题），而根据设计，这些值都是公开的（非秘密）。

RSA 密码学：解密消息

使用对应的 RSA 私钥 {n, d} 解密加密消息时，执行以下变换：

  • decryptedMsg = encryptedMsg^d mod n

为什么这样是正确的？回想一下，根据定义，RSA 密钥对具有以下性质：

  • (m^e)^d ≡ m (mod n)，其中 m 的取值范围为 [0...n)

根据加密变换可得：

  • encryptedMsg = msg^e mod n

因此：

  • decryptedMsg = encryptedMsg^d mod n = (msg^e)^d mod n = msg

RSA 加密与解密——示例

下面按照上述公式，通过一个RSA 加密与解密示例来查看具体计算过程。假设已经生成以下 RSA 公私钥对：

  • 模数 n = 143
  • 公钥指数 e = 7
  • 私钥指数 d = 103
  • 公钥 = {n, e} = {143, 7}
  • 私钥 = {n, d} = {143, 103}

现在加密秘密消息 msg = 83。只需遵循以下公式：

  • encryptedMsg = msg^e mod n = 83^7 mod 143 = 27136050989627 mod 143 = 8

现在将加密消息解密回其原始值：

  • decryptedMsg = encryptedMsg^d mod n = 8^103 mod 143 = 1042962419883256876169444192465601618458351817556959360325703910069443225478828393565899456512 mod 143 = 83

RSA 计算结果正确，这是因为该密钥对满足 RSA 性质：

  • (m^e)^d ≡ m (mod n)，其中 m 的取值范围为 [0...n)
  • (m^7)^103 ≡ m (mod 143)，其中 m 的取值范围为 [0...143_)

在现实中，RSA 模数 n 和私钥指数 d 通常是 3072 位或 4096 位整数，公钥指数 e 则为 65537。

如需进一步阅读，请查看这篇关于 RSA 工作原理的优秀文章，其中包含详细说明和示例：http://doctrina.org/How-RSA-Works-With-Examples.html。

由于 RSA 加密是确定性的（没有随机成分），攻击者可以用公钥加密可能的明文，再测试结果是否等于目标密文，从而成功发起选择明文攻击。这不一定会构成问题，但确实是一个弱点，开发者选择加密方案时应加以考虑。

RSA-KEM 等混合加密方案解决了这一漏洞，并支持加密更长的文本。

results matching ""

    No results matching ""