RSA算法理论学习解惑――复制粘贴RSA私钥导致tengine出错深入解析

2021-11-03 05:15:01

原创文章：来自RSA算法理论学习解惑――复制粘贴RSA私钥导致tengine出错深入解析

tengine的代码中使用了RSA_check_key函数进行RSA私钥格式正确性检查,有一次加载私钥测试时tengine reload失败。案例的看点是RSA格式私钥文件中的私钥指数d在tengine实际的加解密计算过程中并没有用到，至于为什么请细看下文。

问题背景

在一次配置tengine https服务使用的证书和私钥操作时采用了从原文件复制粘贴的方式，当使用tengine启动服务时提示出错：

$tengine -c tengine.conf –t

nginx: [emerg] RSA private key broken: /xxxx/4ed20dc594d0d75926f517d2b29879e2
140319033337512:error:0407B07B:rsa routines:RSA_check_key:d e not congruent to 1:rsa_chk.c:175:
140319033337512:error:0407B07C:rsa routines:RSA_check_key:dmp1 not congruent to d:rsa_chk.c:194:
140319033337512:error:0407B07D:rsa routines:RSA_check_key:dmq1 not congruent to d:rsa_chk.c:212:

关键性提示背后的含义未知。
d e not congruent to 1
dmp1 not congruent to d
dmq1 not congruent to d

原因分析

排查过程中疑问如下：

从上述提示可以得知rsa_chk.c的行数，从而找到调用来源是tengine中RSA_check_key函数，

    if (RSA_check_key(pkey) != 1) {
        ngx_log_error(NGX_LOG_EMERG, ctx->log, 0,
                      "RSA private key broken: %V", name);
        ERR_print_errors_fp(stderr);
        RSA_free(pkey);
        ret = NGX_ABORT;
        goto out;
    }

排查此用户的证书与私钥的正确性，首先查看私钥的格式与输出：
rsa -in 111.pem –text 测试正常没有错误

$openssl s_server -accept 9999 -cert cert.crt -key 111.pem 
Using default temp DH parameters
Using default temp ECDH parameters

然后用curl访问https://127.0.0.1:9999端口后, 上述openssl s_server服务打印输出如下：

ACCEPT

GET / HTTP/1.1
User-Agent: curl/7.29.0
Host: localhost:9999
Accept: */*

即ssl握手过程中用到证书与私钥能验证通过！应该能说明证书与私钥确实是配对的。这不可能太奇怪了?！
最后用openssl rsa -in 111.pem –check　才发现有问题。到底是什么原因tengine 判断私钥有问题？本着刨根问底的精神，联系了做openssl的几个同事，暂时也没有人对这块有深入的研究。只能自己动手分析了。

首先查openssl中出错时的代码块

/* d*e = 1  mod lcm(p-1,q-1)? */
173     if (!BN_is_one(i)) {
174         ret = 0;
175         RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_D_E_NOT_CONGRUENT_TO_1);
176     }

使用d和q参数计算　dmq1，然后与私钥文件中解出的dmq1比对查看是否正确．

197         /* dmq1 = d mod (q-1)? */
198         r = BN_sub(i, key->q, BN_value_one());
199         if (!r) {
200             ret = -1;
201             goto err;
202         }
203 
204         r = BN_mod(j, key->d, i, ctx);
205         if (!r) {
206             ret = -1;
207             goto err;
208         }
209 
210         if (BN_cmp(j, key->dmq1) != 0) {
211             ret = 0;
212             RSAerr(RSA_F_RSA_CHECK_KEY, RSA_R_DMQ1_NOT_CONGRUENT_TO_D);
213         }

细节分析

看来必须搞清楚这几个参数的含义，但要搞清楚这几个参数的作用需要了解rsa加解密的原理，建议先读“RSA算法原理（二）”
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html

这几个参数在openssl中具体定义是

struct crypto_rsa_key {
    int private_key; /* whether private key is set */
    struct bignum *n; /* modulus (p * q) */
    struct bignum *e; /* public exponent */
    /* The following parameters are available only if private_key is set */
    struct bignum *d; /* private exponent */
    struct bignum *p; /* prime p (factor of n) */
    struct bignum *q; /* prime q (factor of n) */
    struct bignum *dmp1; /* d mod (p - 1); CRT exponent */
    struct bignum *dmq1; /* d mod (q - 1); CRT exponent */
    struct bignum *iqmp; /* 1 / q mod p; CRT coefficient */
};

我以个人理解简单点来解释：公钥可以用n和e代表，私钥可以用n和d代表；且n=p*q算出，e和d需要满足　ed ≡ 1 (mod φ(n))，其中φ(n)代表n的欧拉函数；私钥文件中有了这几个参数完全可以实现用来私钥解密和签名等功能了。以m代表明文，c代表密文，所谓"加密"过程，就是算出下式的c：
me ≡ c (mod n)
所谓解密就是c的d次方除以n的余数为m：
cd ≡ m (mod n)

但是直接用n d大数来直接使用存在效率不高的问题，然后就有数学大牛们引入了新的算法－中国余数定理，用于解决效率的问题（本文简称为RSA-CRT算法）。解密和签名的过程就改为了　

https://w1.fi/cgit/hostap/plain/src/tls/rsa.c
/*
* Decrypt (or sign) using Chinese remainer theorem to speed
* up calculation. This is equivalent to tmp = tmp^d mod n
* (which would require more CPU to calculate directly).
*
* dmp1 = (1/e) mod (p-1)
* dmq1 = (1/e) mod (q-1)
* iqmp = (1/q) mod p, where p > q
* m1 = c^dmp1 mod p
* m2 = c^dmq1 mod q
* h = q^-1 (m1 - m2) mod p
* m = m2 + hq
*/

即RSA-CRT算法只需要5个元素就可以完成模幂运算，不需要用到d.现在也可以清楚了上述crypto_rsa_key结构中最后参数的含义了，即用于RSA-CRT计算用的，且dmp1　dmq1也可以通过d计算得到。

一个RSA私钥文件中的内容解析如下：

$openssl rsa -in serverkey.pem -text
Private-Key: (2048 bit)
modulus:
    00:e3:b7:cb:15:a0:92:a2:0f:10:25:a4:cd:a8:2f:
    24:95:d2:65:e1:3f:cf:4d:87:64:52:f8:d9:f9:dc:
    …………

publicExponent: 65537 (0x10001)
privateExponent:
    6b:39:60:c4:07:3e:e4:56:29:69:40:47:a2:38:c8:
    86:4f:72:af:74:87:5d:5f:32:2b:2b:88:1f:f2:17:
    ……。

prime1:
    00:ff:6a:2f:e3:fb:6c:3c:65:e9:03:0e:0e:8f:4b:
    65:9b:26:8d:22:39:07:26:e5:ca:cc:b2:79:05:4e:
   …………
prime2:
    00:e4:3d:5c:57:35:26:39:18:ab:ba:c4:91:45:cd:
    77:9a:f9:93:75:12:3b:50:d7:53:0b:ee:17:57:70:
    …………
exponent1:
    00:c9:f5:c0:0a:88:6a:ec:53:34:ed:6a:77:0e:cd:
    72:79:3d:01:8a:17:07:d5:b5:0c:27:d1:d3:a9:e3:
    …………
exponent2:
    69:42:23:23:d4:cf:1b:e5:d4:cc:fd:7a:41:c6:d0:
    32:18:87:78:a6:3f:d4:b8:79:04:37:79:6c:49:d0:
    …………
coefficient:
    00:c0:7a:72:d3:fe:81:de:de:3d:21:21:cc:c2:20:
    a0:0e:2e:d2:91:1f:af:b3:89:a2:12:50:88:2c:c6:
    …………
writing RSA key

从上可以看出所有的参数都包含在私钥文件中。

现在可以理解RSA_check_key(pkey)　函数为什么出错了：即拿到私钥文件中dmp1，dmq1,d用公式计算他们的关系发现结果不一致所以报错了。
与原文件正确的私钥经过对比发现有一个字符出错，下图中101行代表原始的pem格式私钥数据C13改为了C12，第32行是经过转换后的数据，

查32行得知属于privateExponent部分，即属于私钥元素d

到此本该结束了，但还有一个疑问为什么nginx与 openssl s_server都没有出错，追了一下openssl代码

rsa->meth->rsa_mod_exp()最后调用 RSA_eay_mod_exp()此函数实现解密没有用到d参数。
nginx与 openssl s_server都没有调用RSA_check_key函数，而tengine做加载私钥用到了RSA_check_key函数。
推断openssl rsa -in 111.pem –check应该也用到了此RSA_check_key函数

小结

主要是需要对RSA私钥文件中各参数的作用需要详细了解，由于需要数论原理很多，理解openssl代码难度还是很高的，搞了几个小时终于搞明白了原理。

码农公寓

问题背景

原因分析

细节分析

小结

相关文章