结论

我现在特别习惯于先讲结论。

简单来说,多素数RSA是指生成RSA密钥时,计算固定长度(比如2048位或者4096位)的模数(modulus)的时候,选择多于2个素数并进行相乘得到最终期望长度的modulus。也就是说,标准RSA的计算方式n = p * q,在多素数RSA中,会变成 n = r1 * r2 * r3 * r4 * r5... 的形式。这也是多素数(multi-prime RSA)名字的由来。 这样做有什么好处?这就需要了解RSA的密钥生成以及加密解密的具体计算方式,具体内容比较多,留到后面慢慢说,咱们还是先通过下图看直观的最终效果:

keygentime

performance

注:因为OpenSSL的素数生成依赖于随机数,因此密钥生成时间不稳定,但是依然具有素数个数越多则时间越短的整体趋势。

由上可知,多素数RSA具备三个特点:

因此合理的范围,应该在3~4个素数(2048位),既可以获得较好的性能,又能兼顾安全性。基于:https://www.imperialviolet.org/2011/04/09/multiprime.html

白山对多素数RSA的支持

白山现已全面支持多素数RSA私钥,并可以为客户源站使用RSA私钥进行技术支持。我们认为,多素数RSA最大优势在于作为一种不需要使用硬件加速卡的低成本方案,可以在某些安全性要求不是特别高的场景下发挥作用。例如,对于静态图片,其对安全强度的要求不如对敏感的动态数据大,因此可以考虑采用多素数RSA方案。

当前OpenSSL对多素数RSA并不支持,白山基于 RFC 8017 在OpenSSL中实现多素数RSA功能,并将其开源,希望可以让更多对HTTPS性能有需求的人和厂商享受到技术带来的便利。开源代码位于:OpenSSL-1.1.1-dev-RSA-mp 此次开源的功能基于最新的OpenSSL-1.1.1-dev版本(目前OpenSSL代码库的master分支),目前也正在向OpenSSL官方合并代码,希望能纳入OpenSSL 1.1.1版本的发布。

在OpenSSL 1.1.1-dev打上多素数RSA的patch后,可以这样来生成多素数密钥并测试其性能:

密钥生成:

openssl genrsa -out rsa-3primes.key -primes 3 2048

openssl genpkey -out rsa-3primes.key -algorithm RSA \
        -pkeyopt rsa_keygen_primes:3 -pkeyopt rsa_keygen_bits:2048

性能测试:

openssl speed -primes 3 rsa2048

我们建议用户还可以考虑使用混合搭配的方式,例如对于某些动态域名,使用2素数(或者3素数)的RSA私钥,而对于静态域名使用更多素数的RSA私钥,这样可以实现安全和性能的平衡。

延伸阅读:为什么多素数更快?

要了解多素数的优化原理,首先要了解RSA的原理。RSA要分成两部分来讲,密钥生成和加解密运算。

RSA密钥生成

  1. 生成两个不同的素数p和q,并计算n = p * q
  2. 计算 lambda(n) = lcm(p - 1, q - 1)
  3. 选择公钥指数e,一般有2个值可选:
    • 3
    • 0x10001
  4. 计算 d = e ^ -1 mod lambda(n)

这样一来,我们可以得到3个值:e,d,n。其中(n, e)为公钥,(n, d)为私钥。

RSA加解密运算

非常简单。

加密:

解密:

其中,M为明文,C为密文

RSA运算优化

由上可见,RSA的加解密运算都是模幂运算,在实际的应用场景中,私钥的指数d和模数n都会非常大,直接进行指数运算再模会使得计算开销大到无法进行实际应用。因此在实际的应用场景中(例如OpenSSL),都会对模幂运算进行优化。应用中国剩余定理则是一种主流的优化手段。

中国剩余定理

此定理最早见于中国古代著名的数学著作《孙子算经》,原文如下:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

说的是:一个整数除以3余2,除以5余3,除以7余2,求该整数的值。转换成数学语言,可以用如下同余方程组来表示(”==“表示同余):

x == 2 mod 3
x == 3 mod 5
x == 2 mod 7

考虑只有两个模数的情况,进一步表示为:

x == M1 mod p
x == M2 mod q
即:
M1 == x mod p
M2 == x mod q

中国剩余定理:如果p, q互素,且 0 <= M1 < p,0 <= M2 < q, 令 n = pq,则:

M == x mod n  (1)

可以表示为:

M1 == x mod p 和 M2 == x mod q  (2)

记为(M1, M2)。

令x为C ^ d,代入上述(1)和(2),则得到:

M == C ^ d mod n  (3)
M1 == C ^ d mod p 和 M2 == C ^ d mod q  (4)

可见,(3)是RSA的私钥解密运算,(4)则提供了一种更小模数的计算手段。还可以进一步降低指数d的大小,这里需要介绍另一个定理:欧拉定理。

欧拉定理

如果a和n满足GCD(a, n) = 1,则 a ^ phi(n) == 1 mod n ,其中,phi(n) 为小于或等于n的正整数中与n互质的数的数目(欧拉函数)。

基于欧拉定理,可以进行如下推导:

d = k * phi(p) + d mod phi(p),则:

C ^ d = C ^ (k * phi(p) + d mod phi(p))
      = C ^ (k * phi(p) * C ^ (d mod phi(p)
      = C ^ phi(p) ^ k * C ^ (d mod phi(p))

应用欧拉定理:C ^ phi(p) == 1 mod p,所以:

C ^ d mod p = C ^ (d mod phi(p)) mod p
            = C ^ (d mod (p - 1)) mod p

由此可见,指数d减小到了d mod (p - 1)C ^ d mod q的计算同理。为了方便,我们记 dP = d mod (p - 1), dQ = d mod (q - 1),则:

C ^ d mod p = C ^ dP mod p 并且 C ^ d mod q = C ^ dQ mod q

最后应用Garner方程,可以从(M1, M2)还原出M:

M = M2 + h * q
h = ((M1 - M2))((1/q) mod p)) mod p.

综上所述:

M1 = C ^ dP mod p
M2 = C ^ dQ mod q
并且记:`qInv = (1/q) mod p = q ^ -1 mod p`

这样一来,我们成功把大运算量的C ^ d mod n,削减成了分别对素数p和q的模幂运算,因为参与计算的指数和模数均比d和n小,因此计算的开销显著下降。由此引出了RSA密钥在实际应用场合中的另外一种表示方法:

(n, e, d, p, q, dP, dQ, qInv)

其中公钥依然为(n, e), 私钥有两种方法,除了之前说的(n, d)之外,还可以记录(p, q, dP, dQ, qInv)五元组。

在实际标准中,会将全部的RSA密钥参数记录到私钥文件里,详情可以参考 RFC 8017Appendix-A.1.2

多素数RSA

在了解了2素数RSA如何应用中国剩余定理的基础上,多素数RSA的工作方式就不难理解了,在正确的生成多素数密钥后,只需把上述同余方程组扩展到多个模数的情况,并反复应用Garner方程进行结果合并,就可以正确的解出原文。而素数的个数越多,则私钥运算中的模幂计算运算的开销就越小,从而使性能得到提升。使用中国剩余定理的另外一个好处是,在合并结果之前的计算步骤,可以并发进行,从而充分利用CPU资源。

以下为支持了多素数RSA的OpenSSL读取出的多素数RSA私钥的内容(此例为3素数):

RSA Private-Key: (2048 bit, 3 primes)
modulus:
    00:9a:f1:68:1c:64:92:68:4f:05:ba:02:b9:68:de:
    c1:0e:ec:1c:26:24:3b:37:5f:6d:fd:db:79:95:9c:
    54:eb:43:4d:48:20:e6:f3:64:88:06:e1:75:09:47:
    d5:ac:35:5d:93:86:3c:29:a6:9f:7d:25:36:88:bc:
    a3:fd:9b:a2:dd:e1:a7:f5:82:c3:9c:6d:eb:24:a9:
    ce:85:b1:31:92:72:37:c8:ac:6f:95:d4:a5:a7:ee:
    fe:7e:56:60:7c:9b:8f:f2:55:35:66:00:3c:82:4b:
    58:73:98:73:e3:bf:0a:26:b7:ba:11:d0:61:9d:9d:
    c9:af:fb:d1:e1:61:0a:3d:16:eb:36:c5:f6:5a:23:
    ab:fd:63:23:4c:ab:e6:c5:0a:bd:1b:3c:25:53:35:
    4a:33:ec:a1:0a:9d:3f:b4:25:0b:b6:e5:0b:66:7f:
    0f:74:6c:a1:b3:8c:3e:14:9f:c9:ba:ca:d8:b7:31:
    bb:ab:28:bb:9e:64:e7:e4:b6:51:d9:6f:70:e6:b8:
    f3:cb:04:ed:07:a9:af:ce:45:f6:e4:75:aa:b2:af:
    49:ed:06:da:0d:f0:8f:dd:d2:7a:70:3c:91:cf:e0:
    4f:b1:d5:9e:19:13:2d:dd:45:88:30:da:1d:3d:ed:
    36:db:9b:1a:82:8e:81:59:d3:a4:8c:15:b3:67:1e:
    e2:a1
publicExponent: 65537 (0x10001)
privateExponent:
    6b:41:2c:a6:6a:e0:06:20:9d:80:33:9e:90:ff:91:
    78:78:ec:cb:62:4d:33:79:75:b4:42:97:19:7f:8c:
    31:06:f7:9a:34:5c:6a:a3:6e:9e:04:b7:75:63:2a:
    7f:f8:b8:fc:03:f1:e5:8b:17:e0:13:40:7a:ca:ca:
    62:25:b8:4a:0b:88:ae:a4:84:2f:e6:ce:dd:24:46:
    77:b9:3e:ed:76:ef:32:94:5a:f1:89:47:30:e5:58:
    71:17:9b:98:01:3a:74:21:48:fd:e5:2a:50:1b:d2:
    b1:9f:22:5a:5c:70:93:3b:e7:db:c2:64:a4:79:f6:
    88:63:e4:ae:90:fe:ea:4e:22:d6:e2:69:bf:4e:df:
    1c:01:92:40:ce:b4:a9:47:22:3b:71:5c:0c:d5:d1:
    1d:4a:e9:5d:7e:b5:4a:21:7f:15:6d:d5:ee:13:85:
    a5:cc:00:cc:1b:9e:0c:04:81:1c:be:9e:be:46:26:
    fa:5f:c3:d6:45:37:36:13:60:28:34:f9:23:42:02:
    19:86:98:20:e0:23:24:21:7b:9a:0b:6b:95:7e:82:
    53:1d:1e:3c:14:c0:a8:15:1f:36:47:7c:94:22:38:
    4b:1c:0c:47:40:2f:81:10:b1:90:ec:93:07:94:d3:
    ae:d8:ba:30:88:6c:58:39:18:a3:dd:0b:1a:4e:ff:
    21
prime1:
    06:3d:ac:2f:d2:65:a1:a7:1b:ff:eb:95:61:11:db:
    52:56:1a:41:3f:73:b6:62:1f:04:45:1e:ca:2c:b0:
    16:cf:aa:ae:56:82:80:c8:23:0d:d9:e6:94:fa:18:
    91:38:67:c8:e8:59:64:38:3f:f5:fe:68:9e:3a:9d:
    a2:5e:26:03:84:4d:11:00:1d:b0:67:fd:8d:90:2e:
    a9:5e:58:08:e3:70:7c:85:df:48:d3
prime2:
    06:49:ce:1c:19:46:be:f4:47:7a:c9:6f:02:83:9c:
    d3:c7:16:af:4f:cb:3b:d5:22:79:f2:0b:b4:a6:a5:
    83:e9:fa:09:44:08:27:6c:ab:eb:15:fb:da:42:57:
    dd:16:bc:ce:2a:b1:71:d4:57:35:de:c3:e5:4f:57:
    5b:cc:15:20:a4:b9:f8:c2:28:9c:3e:89:70:54:e0:
    c0:6e:73:ed:7c:ba:93:6d:75:77:8f
exponent1:
    03:9e:db:b9:92:91:ab:4a:4b:10:19:17:bc:0c:a3:
    f4:0c:47:86:fa:cc:a2:4e:22:38:53:f1:1c:d0:f8:
    07:03:ca:bd:01:2b:0c:93:0e:e3:06:3a:a2:ca:c4:
    5d:db:1f:3a:8a:b0:f1:57:40:a3:f1:47:b8:23:c1:
    37:64:ef:20:b3:2c:12:64:c2:d4:88:3f:ac:54:ac:
    fd:4c:e2:3d:a5:d4:a8:28:f1:f4:49
exponent2:
    05:15:24:85:ab:9c:75:fd:65:c5:06:09:36:e4:00:
    1f:60:7c:a2:68:81:61:34:0d:30:b9:85:e2:97:0b:
    93:0a:cb:f1:2f:4e:d3:e6:cf:32:2d:4b:aa:87:13:
    13:7d:2c:50:0b:4b:ef:30:6c:e8:fa:cc:25:8d:32:
    93:dc:e9:7a:c0:0a:1c:d9:7a:0f:87:b0:78:dd:f1:
    e7:37:9f:75:e5:e9:bb:fd:ae:03:5b
coefficient:
    04:9b:4c:cb:4d:f5:58:c3:25:fa:8e:47:50:d8:53:
    f4:cb:51:dc:e8:97:04:86:51:29:33:fa:de:29:7d:
    1f:98:6e:0c:7a:99:45:93:f7:36:e2:35:2b:bc:b4:
    c1:59:3b:82:a8:b8:9d:38:0e:24:cf:fb:f6:aa:2f:
    7f:8d:f9:40:c0:3b:4c:26:e1:46:a9:f2:23:f1:1e:
    f2:34:74:36:af:c4:20:51:10:51:b9
prime3:
    03:f2:b8:41:41:6c:2a:25:a2:72:12:cf:85:4c:34:
    6e:04:6f:f8:89:2e:c5:cc:7e:83:4c:53:f8:36:96:
    71:a8:99:b5:16:a3:37:6a:7e:34:93:31:2d:3e:15:
    2b:a3:2d:4d:ff:38:a4:51:e2:d3:33:63:24:e7:20:
    19:c8:bb:c2:dd:34:17:0a:0b:39:82:cc:5d:26:fc:
    fd:6a:19:4a:dc:62:71:0b:6d:d8:95
exponent3:
    01:02:52:11:6b:95:27:98:82:d2:40:f8:85:0b:1b:
    03:5b:62:fa:d4:a4:fd:ac:ec:50:c6:7b:57:9f:2c:
    08:54:9d:24:69:6a:c1:c9:18:04:7b:f2:3f:ab:f4:
    61:38:cd:65:77:eb:94:23:d1:a3:45:28:fb:cf:8e:
    a6:c8:65:24:c2:c0:83:7a:ef:af:7d:3c:9a:3a:52:
    c2:ba:11:48:ce:d6:e2:29:97:a3:99
coefficient3:
    47:26:bd:74:43:ef:4e:52:3f:c4:a1:44:73:eb:30:
    ba:a0:06:aa:90:58:a3:32:6a:c7:82:eb:75:35:24:
    1e:db:62:60:7d:ee:72:5f:13:71:a6:95:70:79:18:
    8e:99:c9:66:d4:e9:bc:bd:c2:83:bf:c9:61:06:7c:
    02:de:27:1f:8b:f7:99:55:4c:af:e0:b3:c0:fe:f5:
    27:ad:49:a6:73:71:21:d9:f5:e2

作者简介:

杨洋,白山架构师兼驻辽代表,“白十三的码路”缔造者。

NGINX开发、安全系统研发方向布道师。10年研开发经验,先后就职于东软、阿里云、金山云等,OpenSSL代码贡献榜排名17,擅长安全产品研发及各类开发指南编译工作,Bulletproof SSL and TLS第一译者。爱好不断挑战HTTPS流量与加密底线、持续突破各类防御系统极限。