使用wolfSSL进行RSA密钥分析

使用 wolfSSL 进行 RSA 密钥分析

1978 年，RSA 方法发布于世，并在 45 年的时间里，在定义互联网的信任方面占据着至高无上的地位，我们与网站建立的大部分连接仍然主要由 RSA 签名保护。因此，你可以感谢 RSA 确认你连接的网站是有效的。但是，目前 RSA 正受到量子计算机破解的威胁，我们还有大约十年的时间迁移到抗量子的方法。那么，让我们深入了解一下，看看 RSA 密钥是如何实际创建的。

有了 RSA，我们就拥有了公钥密码学的魔力，Bob 可以生成一个密钥对：一个公钥和一个私钥，然后将他的公钥发送给 Alice。如果她想为他加密某些东西，她会用他的公钥加密，然后唯一可以解密它的密钥就是他的私钥。这是一个真正奇妙的概念，Rivest, Shamir 和 Adleman 通过 RSA 方法使其成为现实。

在你的收件箱中获取 Prof Bill Buchanan OBE FRSE’s 的故事

免费加入 Medium 以获取这位作者的更新。

在 RSA 中，我们首先生成两个素数（p，q），然后计算 N = pq 的模数（N）。正是这个模数（N）提供了 RSA 安全性的核心，并且必须难以确定给定模数值的素数。因此，我们的素数必须具有难以分解的大小，并且必须是随机生成的。在这种情况下，我们将生成密钥的 DER 版本，并解析它以给出 ANS.1 格式，以及 PEM 版本。

RSA 基础

使用 RSA，我们首先生成两个随机素数（p 和 q），然后生成一个模数（n）：

正是将该模数分解回其素数因子的难度为 RSA 提供了核心强度。要加密消息值 M，我们生成密文（C）：

其中 e 是加密指数。通常我们使用值 e =65,537。要解密，我们确定一个值 d，它是 e (mod φ (n)) 的模逆：

其中：

要解密，我们取：

然后公钥是（e，n），私钥是（d，n）。以下概述了 RSA 加密：

以下概述了 RSA 签名：

以及公钥方法的基本理论：

那么 dmp1、dmq1、iqmp 是什么？

在密钥中，我们还有 dP、dQ 和 qInv 的其他参数。这些用于通过 CRT（中国剩余定理）简化解密操作。使用 RSA，我们创建两个随机素数（p 和 q），并确定模数：

我们使用以下方法加密消息：

并使用以下方法解密：

其中（e，N）是加密密钥，（d，N）是解密密钥。为了执行解密，我们可以应用 CRT（中国剩余定理）来求解：

为此，我们使用 CRT 求解 M：

并使用费马小定理：

为此，我们需要：

它是 e (mod p −1) 的倒数。还有：

并且：

然后使用不太复杂的操作恢复消息：

此操作可能比执行 M = C^d(mod N) 快四倍。从上面的例子中，现在让我们计算逆 q(mod p):

>>> pow(q,-1,p)
22912084429352545549895539516123883932010399068618835358126059575529436969916

然后是 dP 和 dQ:

>>> pow(e,-1,p-1)
42094444337807335610151571139231770555782681936205452762937671608765740719301
>>> pow(e,-1,q-1)
22116830200221211843789030615620095090924232798420504696801798026445237049317

代码

以下代码使用 wolfSSL 生成 RSA 密钥，然后显示 DER 密钥格式和 PEM 密钥。为了查看密钥的详细信息，我们使用 ANS.1 格式进行解析，并显示密钥的参数：[here]:

##include
##include <wolfssl/wolfcrypt/rsa.h>
##include <wolfssl/wolfcrypt/asn_public.h>

##define RSA_KEY_SIZE 2048
static voic generate_rsa_key(RsaKey* pRsaKey, WC_RNG* rng)
{
    int ret;
    int err = 1;
    printf("Generating RSA key\n");  // 生成 RSA 密钥
    ret = wc_MakeRsaKey(pRsaKey, RSA_KEY_SIZE, WC_RSA_EXPONENT, rng);
}
int main(int argc, char** argv)
{
    RsaKey key;
    WC_RNG rng;
    int ret=0;
    static Asn1 asn1;
    static Asn1PrintOptions opt;
//    if (argc > 1)  hexstring = argv[1];
    wolfCrypt_Init();
    ret = wc_InitRng(&rng);
    ret = wc_InitRsaKey(&key, NULL);
    ret = wc_RsaSetRNG(&key, &rng);
   ret =generate_rsa_key(&key, &rng);
   byte der[4096];
   int  derSz = wc_RsaKeyToDer(&key, der, sizeof(der));

       printf("DER:\n%s\n", to_hex_string(der, derSz));
       wc_Asn1PrintOptions_Init(&opt);
       wc_Asn1PrintOptions_Set(&opt, ASN1_PRINT_OPT_INDENT, 1);
       wc_Asn1_Init(&asn1);
       wc_Asn1_SetFile(&asn1, stdout);

       wc_Asn1_PrintAll(&asn1, &opt, der, derSz);

       byte pem[4096];
       int  pemSz = wc_DerToPem(der, derSz, pem, sizeof(pem), PRIVATEKEY_TYPE);
       printf("\n\nPEM:\n%s\n", pem);

    return 0;
}

一个示例运行给出 [ here]:

Generating RSA key
DER:
308204a20201000282010100e637518a6ba9b1e9eb0e80fae8f634eb978b64d8b2c91a1d88cb220c592fb0e45070f95228669506dd66f7972b3c2f52f5faa11b97aa0e690947a00d143d7815551cbb1c6719efbbc204b224ac5ec696b75c42919eac37c8c4d78bf2e4fc94070879a942adba60bd848ea4cc5b1a838dff12aed952082975fa5f6f543ec054bd38484a8f01be98bec9cf02aa886275a41237fcf7042e38e272c0f7cd59fc696b44bc196dad108c02b33b10492ff4f35ac92fa004635cd8a3ffbf0be34b1d524e276455f0999dc55d266020ffe3d4e52881262e3451c2f4bf05378929c8ce6537e7b9ebd988960de74c94c87c0fd385d08521003244acee15b1ffb6389af8c2d70203010001028201006c92924631d86a2be3cb8750ce25af779c95050e9de2f20a13c5995d3182a86e44f1c2e3d861e8cec0041ba8939f62c24177de1b613fb6641b18488762904adde4b2141ca5133a58d67bd8782b42d76da53441c0e3905d0eb6a6e13dc078ce6732bc0df3807371c46f8bc6750a524ad0e10732a71364fe08c1f7d84d66fad5fb325f57dce0fd4b5f9e4d4b1eebc6103b463e8309f729a78f1cf115093f52c33a2e2d30ec29d192b1ccdd68bfd695c41f59381d1832f15285d22ebb0273d65edf5d976afdb96861298da9b8df6df0efe0a4f64ad69ca1319336fe8365676e62179b9a62044a0355ec8c5fc1fef540577b7bb480c676743992d3fd1aea7b8115e102818100f3854fc79dc3dc763f5e1024cf3ead17b394c940adaab3423993d2042d006234dd6efdebfaed9927873e6ccf76267e5bbfe86df05e6d5959cbad8c3272322b5ee0dc70e941e4d2fb24154e01206907ef2a7f05b589aa8297db53f21e9bd830d949b99a4c2c094b654d8094bc4866d43c5d77e8f2101ecc5d2e92585a193d825502818100f203776192bde79c506c084115f6a8d4ce45d4534adadd61e68c0ce2aeec2bae7505c06b60529e8b43b704922607e20d894c93a529fefd7dc82850de14837f47908dfc6053fe90e58c0e241f572e426444cdec30aa03b895d0a7702ea293ba554b200b538c64bd1349c0b1860168adc5296aa2bd369ec356ee4e98f1c4ca947b02818051121e9f3bfc8a96ab3deb6df5b8cdf3480bce7c43d4c25cd7c24876af6ca3452a3adb3a068db7211bbb428a46b145fbd185d5a3e22bd1453db3872afc2d8b96c8915addacdc3b08f4d84ae1c122764bbf000eac832a4ad3b766d9022babeb874b2e091a36c6d95cde526231d480b7436972941092214eb3eedf359eb92c6b09028180389c3af6a5feaa08d47f10c738be03ec137c1e1885b0008d0002ce98cfd60ab9ba41e82ab5d35da6b1e643b9740feffebe991d084b748c133a18c421cea69bc53fb916c9e99be884e967fd671f5b80c83797fba1be833450470883a345004d5bda40daa56677c20a9afbea0ab095ade02ab9f8eb4db58177fa328470395a31b5028180276f9feb80ef3d8094f34f2b3f0fdb6d083d750dfbaee007589239c8adad8b1f1cb496971ecfe0eb736521346c0a0218be957a0a8e23e12a955587489b82c484af015b454c31cc82e6b6af940b66be79eb26bf5eda5d5e7490ee32cfef544a57c1755f66527391e104d5e78611e6a54bdfe1d359bbad739746eb6a0508f484a9
   0: 4 [1186]  (0) SEQUENCE
   4: 2 +   1   (1)  INTEGER         :00
   7: 4 + 257   (1)  INTEGER         :00e637518a6ba9b1e9eb0e80fae8f634eb978b64d8b2c91a1d88cb220c592fb0e45070f95228669506dd66f7972b3c2f52f5faa11b97aa0e690947a00d143d7815551cbb1c6719efbbc204b224ac5ec696b75c42919eac37c8c4d78bf2e4fc94070879a942adba60bd848ea4cc5b1a838dff12aed952082975fa5f6f543ec054bd38484a8f01be98bec9cf02aa886275a41237fcf7042e38e272c0f7cd59fc696b44bc196dad108c02b33b10492ff4f35ac92fa004635cd8a3ffbf0be34b1d524e276455f0999dc55d266020ffe3d4e52881262e3451c2f4bf05378929c8ce6537e7b9ebd988960de74c94c87c0fd385d08521003244acee15b1ffb6389af8c2d7
 268: 2 +   3   (1)  INTEGER         :010001
 273: 4 + 256   (1)  INTEGER         :6c92924631d86a2be3cb8750ce25af779c95050e9de2f20a13c5995d3182a86e44f1c2e3d861e8cec0041ba8939f62c24177de1b613fb6641b18488762904adde4b2141ca5133a58d67bd8782b42d76da53441c0e3905d0eb6a6e13dc078ce6732bc0df3807371c46f8bc6750a524ad0e10732a71364fe08c1f7d84d66fad5fb325f57dce0fd4b5f9e4d4b1eebc6103b463e8309f729a78f1cf115093f52c33a2e2d30ec29d192b1ccdd68bfd695c41f59381d1832f15285d22ebb0273d65edf5d976afdb96861298da9b8df6df0efe0a4f64ad69ca1319336fe8365676e62179b9a62044a0355ec8c5fc1fef540577b7bb480c676743992d3fd1aea7b8115e1
 533: 3 + 129   (1)  INTEGER         :00f3854fc79dc3dc763f5e1024cf3ead17b394c940adaab3423993d2042d006234dd6efdebfaed9927873e6ccf76267e5bbfe86df05e6d5959cbad8c3272322b5ee0dc70e941e4d2fb24154e01206907ef2a7f05b589aa8297db53f21e9bd830d949b99a4c2c094b654d8094bc4866d43c5d77e8f2101ecc5d2e92585a193d8255
 665: 3 + 129   (1)  INTEGER         :00f203776192bde79c506c084115f6a8d4ce45d4534adadd61e68c0ce2aeec2bae7505c06b60529e8b43b704922607e20d894c93a529fefd7dc82850de14837f47908dfc6053fe90e58c0e241f572e426444cdec30aa03b895d0a7702ea293ba554b200b538c64bd1349c0b1860168adc5296aa2bd369ec356ee4e98f1c4ca947b
 797: 3 + 128   (1)  INTEGER         :51121e9f3bfc8a96ab3deb6df5b8cdf3480bce7c43d4c25cd7c24876af6ca3452a3adb3a068db7211bbb428a46b145fbd185d5a3e22bd1453db3872afc2d8b96c8915addacdc3b08f4d84ae1c122764bbf000eac832a4ad3b766d9022babeb874b2e091a36c6d95cde526231d480b7436972941092214eb3eedf359eb92c6b09
 928: 3 + 128   (1)  INTEGER         :389c3af6a5feaa08d47f10c738be03ec137c1e1885b0008d0002ce98cfd60ab9ba41e82ab5d35da6b1e643b9740feffebe991d084b748c133a18c421cea69bc53fb916c9e99be884e967fd671f5b80c83797fba1be833450470883a345004d5bda40daa56677c20a9afbea0ab095ade02ab9f8eb4db58177fa328470395a31b5
1059: 3 + 128   (1)  INTEGER         :276f9feb80ef3d8094f34f2b3f0fdb6d083d750dfbaee007589239c8adad8b1f1cb496971ecfe0eb736521346c0a0218be957a0a8e23e12a955587489b82c484af015b454c31cc82e6b6af940b66be79eb26bf5eda5d5e7490ee32cfef544a57c1755f66527391e104d5e78611e6a54bdfe1d359bbad739746eb6a0508f484a9

PEM:
-----BEGIN RSA PRIVATE KEY-----
MIIEogIBAAKCAQEA5jdRimupsenrDoD66PY065eLZNiyyRodiMsiDFkvsORQcPlS
KGaVBt1m95crPC9S9fqhG5eqDmkJR6ANFD14FVUcuxxnGe+7wgSyJKxexpa3XEKR
nqw3yMTXi/Lk/JQHCHmpQq26YL2EjqTMWxqDjf8SrtlSCCl1+l9vVD7AVL04SEqP
Ab6YvsnPAqqIYnWkEjf89wQuOOJywPfNWfxpa0S8GW2tEIwCszsQSS/081rJL6AE
Y1zYo/+/C+NLHVJOJ2RV8JmdxV0mYCD/49TlKIEmLjRRwvS/BTeJKcjOZTfnuevZ
iJYN50yUyHwP04XQhSEAMkSs7hWx/7Y4mvjC1wIDAQABAoIBAGySkkYx2Gor48uH
UM4lr3eclQUOneLyChPFmV0xgqhuRPHC49hh6M7ABBuok59iwkF33hthP7ZkGxhI
h2KQSt3kshQcpRM6WNZ72HgrQtdtpTRBwOOQXQ62puE9wHjOZzK8DfOAc3HEb4vG
dQpSStDhBzKnE2T+CMH32E1m+tX7Ml9X3OD9S1yeTUse68YQO0Y+gwn3KaePHPEV
CT9SwzouLTDsKdGSsczdaL/WlcQfWTgdGDLxUoXSLrsCc9Ze312Xav25aGEpjam4
323w7+Ck9krWnKExkzb+g2VnbmIXm5piBEoDVeyMX8H+9UBXe3u0gMZ2dDmS0/0a
6nuBFeECgYEA84VPx53D3HY/XhAkzz6tF7OUyUCtqrNCOZPSBC0AYjTdbv3r+u2Z
J4c+bM92Jn5bv+ht8F5tWVnLrYwycjIrXuDccOlB5NL7JBVOASBpB+8qfwW1iaqC
l9tT8h6b2DDZSbmaTCwJS2VNgJS8SGbUPF136PIQHsxdLpJYWhk9glUCgYEA8gN3
YZK955xQbAhBFfao1M5F1FNK2t1h5owM4q7sK651BcBrYFKei0O3BJImB+INiUyT
pSn+/X3IKFDeFIN/R5CN/GBT/pDljA4kH1cuQmREzewwqgO4ldCncC6ik7pVSyAL
U4xkvRNJwLGGAWitxSlqor02nsNW7k6Y8cTKlHsCgYBREh6fO/yKlqs96231uM3z
SAvOfEPUwlzXwkh2r2yjRSo62zoGjbchG7tCikaxRfvRhdWj4ivRRT2zhyr8LYuW
yJFa3azcOwj02ErhwSJ2S78ADqyDKkrTt2bZAiur64dLLgkaNsbZXN5SYjHUgLdD
aXKUEJIhTrPu3zWeuSxrCQKBgDicOval/qoI1H8Qxzi+A+wTfB4YhbAAjQACzpjP
1gq5ukHoKrXTXaax5kO5dA/v/r6ZHQhLdIwTOhjEIc6mm8U/uRbJ6ZvohOln/Wcf
W4DIN5f7ob6DNFBHCIOjRQBNW9pA2qVmd8IKmvvqCrCVreAqufjrTbWBd/oyhHA5
WjG1AoGAJ2+f64DvPYCU808rPw/bbQg9dQ37ruAHWJI5yK2tix8ctJaXHs/g63Nl
ITRsCgIYvpV6Co4j4SqVVYdIm4LEhK8BW0VMMcyC5ravlAtmvnnrJr9e2l1edJDu
Ms/vVEpXwXVfZlJzkeEE1eeGEealS9/h01m7rXOXRutqBQj0hKk=
-----END RSA PRIVATE KEY-----

此格式为：

参数是 N，d，e =0 x 010001，p，q，dp，dq 和 qInv。在这种情况下，p 是 0x00f3854fc79dc3dc763f5e1024cf3ead17b394c940adaab3423993d2042d006234dd6efdebfaed9927873e6ccf76267e5bbfe86df05e6d5959cbad8c3272322b5ee0dc70e941e4d2fb24154e01206907ef2a7f05b589aa8297db53f21e9

• 原文链接： billatnapier.medium.com/...
• 登链社区 AI 助手，为大家转译优秀英文文章，如有翻译不通的地方，还请包涵～