RSA 简介

主要算法简介

RSA 的原理是在于能够找到三个很大的正整数 \(e,d,n\) 使得对于任何 \(0 \le m \lt n\)：

\[ (m^e)^d \equiv m \pmod{n} \]

其中公钥为 \((n,e)\)，可以发送给任何人；私钥为 \((n,d)\)，只能由所有者掌握。RSA 支持 4 种操作：加密/解密，签名/验证签名。

加密

首先用一些编码手段把需要加密的信息转换成整数 \(m\)，用公钥中的两个参数计算

\[ c = m^e \pmod{n} \]

其中 \(c\) 就是加密后的信息了。

解密

由私钥所有者计算

\[ \begin{align} c^d \pmod{n} &= (m^e \pmod{n})^d \pmod{n} \\ &= (m^e)^d \pmod{n} \\ &= m \pmod{n} \end{align} \]

就能还原原来的信息了（乘积与其余数乘积同余，见同余命题 a）

签名

首先对要签名的信息作一个 message digest，常用的如 MD5 和 SHA 系列；
然后把这个 digest 转换成整数 \(m\) 使得 \(1 \le m \lt n\)；
最后用私钥 \((n,d)\) 计算 \(s = m^d \pmod{n}\)

验签

用公钥 \((n,e)\) 计算 \(v = s^e \pmod{n}\)
把 \(v\) 转换回 digest
独立对要签名的信息再作一次 digest
对比这两个 digest，如果相同的话，那这个签名就是有效的

Note

可以看到加解密和签名验签刚好是两个方向：前者是公钥加密发送给所有者解密，后者是用私钥签名发送给其他人用公钥验签；所以这就是为何一般不建议使用相同的 key 同时用作加密和签名：

Using the same key for encryption and signing

Given that the underlying mathematics is the same for encryption and signing, only in reverse, if an attacker can convince a key holder to sign an unformatted encrypted messageusing the same key then she gets the original.

公私钥生成

生成 \(e,d,n\) 的算法大致如下：

生成两个大的随机质数 \(p\) 和 \(q\)
计算 \(n = pq\)，\(n\) 是公钥的一部分
计算 \(n\) 的欧拉函数 \(\varphi(n) = (p - 1)(q - 1)\)
选择公钥幂 \(1 < e < \varphi(n)\)，且 \(e\) 和 \(\varphi(n)\) 互质
计算私钥幂 \(d\) 使得 \(ed \equiv 1 \pmod{\varphi(n)}\)
\((e, n)\) 是公钥，其余 \(p,q,d,\varphi(n)\) 这些都需要保密

通过这样算法生成出来的 \(e,d,n\) 即可满足最开始的要求，证明可看下面

注意 \(e\) 和 \(n\) 是公开的，而通过 \(\varphi(n)\) 和 \(e\) 则可以算出 \(d\)，故其实 RSA 的安全性即来自于 从 \(n\) 难以计算出 \(\varphi(n) = (p - 1)(q - 1) = (n + 1) - (p + q)\)，这是因为大数质数分解目前没有有效算法，也就是从 \(n\) 难以分解出 \(p,q\)，也就难以算出 \(\varphi(n)\) 了

实现细节

更多细节有兴趣可以看一下下面参考的链接，稍微摘录一些：

计算 \(y = x^e \pmod{n}\) （所谓 modular exponentiation）的复杂度大约为 \(O(k^3)\)，其中 \(k\) 是 \(n\) 的长度（例如 1024 bits），且当 \(e\) 的二进制表示中 1 的数量越多则越慢。
公钥幂 \(e\) 一般选取固定的：例如 \[ \begin{split} 3 = 2^{2^0}+1 \\ 5 = 2^{2^1}+1 \\ 17 = 2^{2^2}+1 \\ 257 = 2^{2^3}+1 \\ 65537 = 2^{2^4}+1 \end{split} \] 这5个是前五个 fermat number：\(F_x = 2^{2^x}+1\) ，恰好都是素数，但 \(F_5\) 以及后面的 fermat number 不是素数。显然这些数字的二进制表示只有两个 1，如上述原因，在加密的过程中能节省计算时间。实际应用中一般都是使用 65537 ，因为小的 \(e\) 不太安全。
多个素数相乘结果作为模的一个好处是可以更快速的计算 \(m = c^d \pmod{n}\)
- 使用中国剩余定理（Chinese Remainder Theorem，CRT）可以把这个计算转换成对 \(p,q\) 的 modular exponentiation 计算，而 \(p,q\) 的长度都只有 \(n\) 的一半，所以复杂度会降低到原来的四分之一：\(O(2(\cfrac{k}{2})^3) = O(\cfrac{k^3}{4})\)

存储格式

如上所述，RSA 的公私钥实际上就是些数字，但我们平时实际使用的是 .pem 格式（或 .der）的 key 。

.pem 格式头部和尾部的有一些标识符（-----BEGIN XXXX-----）这些是为了让 parser 可以马上知道这个文件包含的是公钥私钥，或是证书等。

中间的数据其实是 base64 编码过后的 DER（Distinguished Encoding Rules）编码的 ASN.1（Abstract Syntax Notation One）数据。

不妨写个程序看一下（dec.py）：

import sys
from base64 import b64decode
from pyasn1.codec.der.decoder import decode as der_decode
from pyasn1_modules import rfc2437

def read_key_pem(src):
    if isinstance(src, bytes):
        src = src.decode('ascii')
    data = ''.join((line.strip() for line in src.split('\n') if not line.startswith('-----')))
    return der_decode(b64decode(data), asn1Spec=rfc2437.RSAPrivateKey())[0]

obj = read_key_pem(open(sys.argv[1]).read())
print(obj.prettyPrint())

生成一个 rsa private key 来跑一下：

$ openssl genrsa -out pri.pem 2048
Generating RSA private key, 2048 bit long modulus (2 primes)
...........................+++++
............+++++
e is 65537 (0x010001)
$ python ./dec.py pri.pem
RSAPrivateKey:
 version=0
 modulus=30078218357432552470030675464869....
 publicExponent=65537
 privateExponent=5666198999662210....
 prime1=17622717115310961559542629....
 ...

可以看到实际上存储的就是上面所述的各种数字，完整的定义是在 PKCS#1 标准中：

RSAPrivateKey ::= SEQUENCE {
  version           Version,
  modulus           INTEGER,  -- n
  publicExponent    INTEGER,  -- e
  privateExponent   INTEGER,  -- d
  prime1            INTEGER,  -- p
  prime2            INTEGER,  -- q
  exponent1         INTEGER,  -- d mod (p-1)
  exponent2         INTEGER,  -- d mod (q-1)
  coefficient       INTEGER,  -- (inverse of q) mod p
  otherPrimeInfos   OtherPrimeInfos OPTIONAL
}

其中 modulus/publicExponent/privateExponent 即模/公钥幂/私钥幂，可以看到实际中的 RSA 私钥也是包含 publicExponent 的；所以这就是为什么 openssl 工具中能从私钥中导出公钥的原因。

更新 2022-09-10: 现在也可以用 jupyterlite 来跑上述程序啦～

POSTS2017

RSA 简介

主要算法简介

加密

解密

签名

验签

Note

公私钥生成

实现细节

存储格式

相关数学

同余命题

Euler’s totient function

Euler’s theorem

RSA 正确性证明

参考