1one-w01f opened a new issue #90:
URL: https://github.com/apache/incubator-milagro-crypto-c/issues/90
Hi,
I recently run into a rather interesting problem. It appears to me that the
RSA key generation in milagro might sometimes be incorrect, and I have no ideas
to why that would be the case.
Here's the source code I prepared to illustrate the problem. For simplicity
I just replaced the source code of `test/test_rsa_2048.c` with this. The build
target I used was `LINUX_64BIT_NIST256_RSA2048`.
```C
#include <stdio.h>
#include <time.h>
#include "rsa_2048.h"
#include "randapi.h"
void print_keypair(rsa_private_key_2048 *priv, rsa_public_key_2048 *pub)
{
printf(" priv->p = ");
FF_2048_output(priv->p,FFLEN_2048/2);
printf("\n");
printf(" priv->q = ");
FF_2048_output(priv->q,FFLEN_2048/2);
printf("\n");
printf("\n");
printf(" pub->n = ");
FF_2048_output(pub->n,FFLEN_2048);
printf("\n");
printf("\n");
printf("priv->dp = ");
FF_2048_output(priv->dp,FFLEN_2048/2);
printf("\n");
printf("priv->dq = ");
FF_2048_output(priv->dq,FFLEN_2048/2);
printf("\n");
printf(" priv->c = ");
FF_2048_output(priv->c,FFLEN_2048/2);
printf("\n");
}
int main(int argc, char *argv[])
{
char m[RFS_2048],ml[RFS_2048],c[RFS_2048],s[RFS_2048];
char p[RFS_2048/2], q[RFS_2048/2];
rsa_public_key_2048 pub;
rsa_private_key_2048 priv;
octet M= {0,sizeof(m),m};
octet ML= {0,sizeof(ml),ml};
octet C= {0,sizeof(c),c};
octet S= {0,sizeof(s),s};
octet P= {sizeof(p), sizeof(p), p};
octet Q= {sizeof(q), sizeof(q), q};
// somehow this prime number leads to incorrect dp, which is quite weird
OCT_fromHex(&P,
"f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");
OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");
// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);
print_keypair(&priv, &pub);
// ======
printf("\n===\n\n");
OCT_fromHex(&P,
"db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb");
OCT_fromHex(&Q,
"f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93");
// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);
print_keypair(&priv, &pub);
// === clean up ===
RSA_2048_PRIVATE_KEY_KILL(&priv);
OCT_clear(&M);
OCT_clear(&ML); /* clean up afterwards */
OCT_clear(&C);
return 0;
}
```
Which produces the following output:
---
priv->p =
f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed
priv->q =
f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363
pub->n =
e932ac92252f585b3a80a4dd76a897c8b7652952fe788f6ec8dd640587a1ee5647670a8ad4c2be0f9fa6e49c605adf77b5174230af7bd50e5d6d6d6d28ccf0a886a514cc72e51d209cc772a52ef419f6a953f3135929588ebe9b351fca61ced78f346fe00dbb6306e5c2a4c6dfc3779af85ab417371cf34d8387b9b30ae46d7a
5ff5a655b8d8455f1b94ae736989d60a6f2fd5cadbffbd504c5a756a2e6bb5cecc13bca7503f6df8b52ace5c410997e98809db4dc30d943de4e812a47553dce54844a78e36401d13f77dc650619fed88d8b3926e3d8e319c80c744779ac5d6abe252896950917476ece5e8fc27d5f053d6018d91b502c4787558a002b9283da7
**priv->dp =
4c8b6ace1ba4747563b3d9f6c29e01fb968c96e116707fb4556b811f39b047aac0d7fc303650ff6a0a14e969656094a08dab8231a71c76613ae1063d87aea343b8a2146fc5b850693e1d7167ab97e063b8c383462e8394f47ff0fdb4c6d4e5872c49c2b459841670b808f68173248883f16d95c698b0dd39a5e167e840047571**
priv->dq =
a2345ca519cd21e1b59b0b3cfaa39d0832e6e74d729db31de5152da6404903f479814863c9fa28b45418a091b60e6e1890fafe3a29e26baf07ff6f9932e7beb6d06fb767e8e7538bc07e47fb7f6f0b1554f3b7e223eefae63bd6350361591e31b34663ef50c98609a6ea9c7726a89155ab29e80ffc56416ff73957802dd5d797
**priv->c =
6f1e5e6d113bffba6e9fe60cbfd0b959f0b78fb8f71db4ab4f63147abec85beb2a982acde258672046843ce3b9f93a33ff1b25602762dfd8dbddf36e3b9815a1bf14a9dbba3d28df3dfb830fb976662cc1b41026207aa16686f49c23f93f1312ba29ef76a0c13fb03e727247b632dda5a06bf6d385da9831af4ec18d1d23df95**
===
priv->p =
db59a11194cb81be97715d9ea436484c7fd39cee1a71dd1e896e08cc2d91d95a2d6d561f48db72acea57450ecfd4dc5399c1f8ce7abbb8b99c92f9c7be7ab2df6990b473c5a464eaa4d34747d022e47c17b549905db305986af5970442ad54714ee7fce2c8c443da7b22f4354e105c009a8d36de733d9fb02bfbcd57803bdcfb
priv->q =
f6457c323b66f43fa7a20f03b01a8c09c257f7fa65c7ce6a01acd816bca4de5da7692fd82ac036ca18bcc1d36e03a9ca6c2c1cf9007c106932c946cb51acb151c5c2912369553a70ddea742bc5673baaa962f8028c5ec7f4699bffd6c7beab3c278424a15548a4fce75946784036d2a9a118698224b3f218e66d980786252c93
pub->n =
d303aa59c3248225f2ff52e32e33cdcb797c3b501fed5e51c0189f27ef7cd614c7c4cbf2079e663b24f7ae2e9683b4878ce662d6c944196874f4a48422353303c9ad8ffd2824b4f70996ee558a89e1e98679305209a124aaf62eecd3187d2d8ee2cf5eb1b5a1b7347958aa53205b1f726856903d6a953ed72a74673c92f46f52
92b4f1c59cdb645a6afc4d0381dec80444775658c54995bf0cba58e5f90f152a557172bc040c432fe63ede5b1cf14f2f1a11d30d3a96baa24c3a3982461292be8e9db35fd088a8cbaf0e26326e630ee690368cd0a8868502e9ddb17dde45179ce7bb22b10f9deb2e3d8ddcd30ca97c9bae84ca7c3c9a13afa95de4783ea20821
priv->dp =
923bc0b66332567f0fa0e9146d7985885537bdf411a13e145b9eb0881e613b91739e396a30924c7346e4d8b48a8de837bbd6a5defc7d25d1130ca68529a721ea4660784d2e6d989c6de22f85356c9852ba78dbb593ccae659ca3ba02d71e384b89effdec85d82d3c52174d78deb592ab11b379e9a22915201d5288e50027e8a7**
priv->dq =
a42e52cc2799f82a6fc15f57cabc5d5bd6e54ffc43da899c011de5647dc33ee91a461fe571d579dc107dd68cf40271319d72bdfb55a80af0cc862f32367320e12e81b6179b8e26f5e946f81d2e44d271c641faac5d94854d9bbd5539da7f1cd2c502c31638db18a89a3b84502acf371bc0baf1016dcd4c10999e655a596e1db7
priv->c =
b163cc8298e63ea294f20288143304adc9a555ca170e55942954773801405652d8f998da549541782bb565ff49b32ae5f6d814bf38a878c598c6307fc294a0151f2681b8a39d6ace0a732feb6cb514a03de8d92290a8f1499231a945d698c8461cde13156d9bfc5b09ca3bf0d27a770f3ab3fedb375bd4135c8dcb57f9d60881
---
The primes `P` and `Q` were all copied from RSA private keys generated by
OpenSSL. If we use OpenSSL to check the numbers of the 2 private keys:
```bash
$ openssl rsa -in privkey.pem -noout -text
RSA Private-Key: (2048 bit, 2 primes)
modulus:
00:e9:32:ac:92:25:2f:58:5b:3a:80:a4:dd:76:a8:
97:c8:b7:65:29:52:fe:78:8f:6e:c8:dd:64:05:87:
a1:ee:56:47:67:0a:8a:d4:c2:be:0f:9f:a6:e4:9c:
60:5a:df:77:b5:17:42:30:af:7b:d5:0e:5d:6d:6d:
6d:28:cc:f0:a8:86:a5:14:cc:72:e5:1d:20:9c:c7:
72:a5:2e:f4:19:f6:a9:53:f3:13:59:29:58:8e:be:
9b:35:1f:ca:61:ce:d7:8f:34:6f:e0:0d:bb:63:06:
e5:c2:a4:c6:df:c3:77:9a:f8:5a:b4:17:37:1c:f3:
4d:83:87:b9:b3:0a:e4:6d:7a:5f:f5:a6:55:b8:d8:
45:5f:1b:94:ae:73:69:89:d6:0a:6f:2f:d5:ca:db:
ff:bd:50:4c:5a:75:6a:2e:6b:b5:ce:cc:13:bc:a7:
50:3f:6d:f8:b5:2a:ce:5c:41:09:97:e9:88:09:db:
4d:c3:0d:94:3d:e4:e8:12:a4:75:53:dc:e5:48:44:
a7:8e:36:40:1d:13:f7:7d:c6:50:61:9f:ed:88:d8:
b3:92:6e:3d:8e:31:9c:80:c7:44:77:9a:c5:d6:ab:
e2:52:89:69:50:91:74:76:ec:e5:e8:fc:27:d5:f0:
53:d6:01:8d:91:b5:02:c4:78:75:58:a0:02:b9:28:
3d:a7
publicExponent: 3 (0x3)
privateExponent:
00:9b:77:1d:b6:c3:74:e5:92:27:00:6d:e8:f9:c5:
ba:85:cf:98:c6:37:54:50:5f:9f:30:93:98:03:af:
c1:49:8e:da:44:b1:b1:e3:2c:7e:b5:15:19:ed:bd:
95:91:ea:4f:ce:0f:81:75:ca:52:8e:09:93:9e:48:
f3:70:88:a0:70:59:c3:63:32:f7:43:68:c0:68:84:
f7:18:c9:f8:11:4f:1b:8d:4c:b7:90:c6:3b:09:d4:
67:78:bf:dc:41:34:8f:b4:cd:9f:ea:b3:d2:42:04:
99:2c:6d:d9:ea:82:4f:bc:a5:91:cd:64:cf:68:a2:
33:ad:05:26:77:5c:98:48:fa:fa:31:52:81:77:e1:
f8:df:91:81:a8:b9:45:08:11:06:fd:58:bd:3d:73:
79:9b:22:95:75:c4:f3:b2:91:01:a0:3e:e1:f0:54:
72:b3:61:57:84:d9:24:4c:e0:ed:63:9c:77:e8:e2:
12:ab:52:ab:dd:f4:a9:28:22:4b:6b:6f:74:b7:11:
47:86:dd:60:71:bd:91:13:d7:87:0c:6b:52:c0:bc:
8b:9c:10:2c:fe:32:1d:ac:35:7e:03:0e:d6:c5:80:
04:0c:a4:1c:13:d6:b4:96:78:11:80:7e:f2:a2:25:
98:3e:a9:f8:8d:67:fa:a4:26:20:f4:2a:4f:5b:db:
e0:3b
prime1:
00:f5:5d:1f:9b:de:51:9d:3d:30:e9:a0:82:0a:08:
50:f3:a6:d0:5e:fa:82:dc:c7:ef:94:8a:09:83:42:
24:ad:6f:b7:7e:e7:92:f5:3b:1e:e6:ef:c0:27:0e:
5e:8f:dd:59:fa:b4:0a:da:83:3d:f0:ea:69:eb:2f:
0b:37:d7:17:a3:fd:03:29:28:0c:d4:75:25:fd:22:
97:0c:8f:d8:60:c7:be:74:94:82:c4:2a:6e:16:a4:
b5:b7:ed:f2:7e:01:21:4f:55:fd:58:39:a1:1c:86:
be:6b:bd:8b:01:e5:dd:ee:f7:43:bc:a5:9e:89:6c:
17:51:14:5d:4b:6a:9d:a9:ed
prime2:
00:f3:4e:8a:f7:a6:b3:b2:d2:90:68:90:db:77:f5:
6b:8c:4c:5a:5a:f4:2b:ec:8c:ac:d7:9f:c4:79:60:
6d:85:ee:b6:41:ec:95:ae:f7:3d:0e:7e:24:f0:da:
91:15:a5:24:d9:78:7d:57:3e:d3:a1:86:8b:ff:27:
65:cc:5b:9e:12:38:a7:93:1b:dd:5a:fd:51:a0:bd:
6b:f9:3f:26:90:9f:ff:6d:93:d3:35:e6:78:59:59:
c1:4f:85:12:05:ad:4a:8c:e9:95:e6:f9:2e:49:0e:
7a:5f:ea:b2:b9:fc:da:00:80:be:dc:17:fa:81:62:
27:f2:d6:03:40:44:c0:c3:63
exponent1:
00:a3:93:6a:67:e9:8b:be:28:cb:46:6b:01:5c:05:
8b:4d:19:e0:3f:51:ac:93:2f:f5:0d:b1:5b:ac:d6:
c3:1e:4a:7a:54:9a:61:f8:d2:14:99:f5:2a:c4:b4:
3f:0a:93:91:51:cd:5c:91:ac:d3:f5:f1:9b:f2:1f:
5c:cf:e4:ba:6d:53:57:70:c5:5d:e2:f8:c3:fe:17:
0f:5d:b5:3a:eb:2f:d4:4d:b8:57:2d:71:9e:b9:c3:
23:cf:f3:f6:fe:ab:6b:8a:39:53:90:26:6b:68:59:
d4:47:d3:b2:01:43:e9:49:fa:2d:28:6e:69:b0:f2:
ba:36:0d:93:87:9c:69:1b:f3
exponent2:
00:a2:34:5c:a5:19:cd:21:e1:b5:9b:0b:3c:fa:a3:
9d:08:32:e6:e7:4d:72:9d:b3:1d:e5:15:2d:a6:40:
49:03:f4:79:81:48:63:c9:fa:28:b4:54:18:a0:91:
b6:0e:6e:18:90:fa:fe:3a:29:e2:6b:af:07:ff:6f:
99:32:e7:be:b6:d0:6f:b7:67:e8:e7:53:8b:c0:7e:
47:fb:7f:6f:0b:15:54:f3:b7:e2:23:ee:fa:e6:3b:
d6:35:03:61:59:1e:31:b3:46:63:ef:50:c9:86:09:
a6:ea:9c:77:26:a8:91:55:ab:29:e8:0f:fc:56:41:
6f:f7:39:57:80:2d:d5:d7:97
coefficient:
00:85:4e:43:ad:27:2d:f5:81:12:c9:84:ca:73:eb:
bf:9a:57:8a:56:53:ff:eb:79:dc:43:a4:20:27:b5:
5a:69:27:d7:74:65:c4:2d:83:e9:d8:ee:9e:7c:bc:
91:6f:ed:76:2a:7b:90:24:a5:bd:ee:8a:f3:1d:38:
d5:c1:84:0d:80:78:13:9a:3c:b0:04:7c:c7:36:cf:
22:4d:99:25:f6:1a:42:fd:0f:48:87:09:e7:24:a5:
c6:f3:21:40:a0:5f:22:e4:9b:37:2d:f7:f4:39:c6:
ad:86:07:89:6b:d6:b3:8a:d5:9e:bd:be:1b:8d:e9:
32:54:35:25:7e:4c:a4:b0:9d
```
```bash
$ openssl rsa -in privkey.pem -noout -text
RSA Private-Key: (2048 bit, 2 primes)
modulus:
00:d3:03:aa:59:c3:24:82:25:f2:ff:52:e3:2e:33:
cd:cb:79:7c:3b:50:1f:ed:5e:51:c0:18:9f:27:ef:
7c:d6:14:c7:c4:cb:f2:07:9e:66:3b:24:f7:ae:2e:
96:83:b4:87:8c:e6:62:d6:c9:44:19:68:74:f4:a4:
84:22:35:33:03:c9:ad:8f:fd:28:24:b4:f7:09:96:
ee:55:8a:89:e1:e9:86:79:30:52:09:a1:24:aa:f6:
2e:ec:d3:18:7d:2d:8e:e2:cf:5e:b1:b5:a1:b7:34:
79:58:aa:53:20:5b:1f:72:68:56:90:3d:6a:95:3e:
d7:2a:74:67:3c:92:f4:6f:52:92:b4:f1:c5:9c:db:
64:5a:6a:fc:4d:03:81:de:c8:04:44:77:56:58:c5:
49:95:bf:0c:ba:58:e5:f9:0f:15:2a:55:71:72:bc:
04:0c:43:2f:e6:3e:de:5b:1c:f1:4f:2f:1a:11:d3:
0d:3a:96:ba:a2:4c:3a:39:82:46:12:92:be:8e:9d:
b3:5f:d0:88:a8:cb:af:0e:26:32:6e:63:0e:e6:90:
36:8c:d0:a8:86:85:02:e9:dd:b1:7d:de:45:17:9c:
e7:bb:22:b1:0f:9d:eb:2e:3d:8d:dc:d3:0c:a9:7c:
9b:ae:84:ca:7c:3c:9a:13:af:a9:5d:e4:78:3e:a2:
08:21
publicExponent: 3 (0x3)
privateExponent:
00:8c:ad:1c:3b:d7:6d:ac:19:4c:aa:37:42:1e:cd:
33:dc:fb:a8:27:8a:bf:f3:94:36:80:10:6a:1a:9f:
a8:8e:b8:85:2d:dd:4c:05:14:44:27:6d:fa:74:1f:
0f:02:78:5a:5d:ee:ec:8f:30:d8:10:f0:4d:f8:6d:
ad:6c:23:77:57:db:c9:0a:a8:c5:6d:cd:fa:06:64:
9e:e3:b1:b1:41:46:59:a6:20:36:b1:16:18:71:f9:
74:9d:e2:10:53:73:b4:97:34:e9:cb:ce:6b:cf:78:
50:e5:c6:e2:15:92:14:f6:f0:39:b5:7e:47:0e:29:
e4:c6:f8:44:d3:0c:a2:f4:e0:80:b9:38:56:88:70:
9e:e8:1d:45:ea:eb:73:b3:f7:c9:56:dd:2b:a0:2e:
0a:9c:24:56:6a:50:02:09:e5:93:a1:ab:11:f3:2d:
b5:a0:66:7b:42:1c:8f:a5:ea:10:86:0b:62:c2:7e:
2e:7f:94:a0:ff:a8:93:fb:4a:23:f2:1f:08:ea:31:
9e:85:c1:0a:06:4a:c8:35:9c:7f:3b:3b:49:d5:34:
be:dc:d3:d4:4d:cf:a4:0e:32:bc:6c:8d:3b:65:4a:
4b:8a:00:c8:a1:0b:56:e4:92:0b:c1:6e:54:41:89:
4b:a1:ea:1c:12:6d:c5:ab:ef:0f:4d:aa:10:d0:2b:
54:63
prime1:
00:f6:45:7c:32:3b:66:f4:3f:a7:a2:0f:03:b0:1a:
8c:09:c2:57:f7:fa:65:c7:ce:6a:01:ac:d8:16:bc:
a4:de:5d:a7:69:2f:d8:2a:c0:36:ca:18:bc:c1:d3:
6e:03:a9:ca:6c:2c:1c:f9:00:7c:10:69:32:c9:46:
cb:51:ac:b1:51:c5:c2:91:23:69:55:3a:70:dd:ea:
74:2b:c5:67:3b:aa:a9:62:f8:02:8c:5e:c7:f4:69:
9b:ff:d6:c7:be:ab:3c:27:84:24:a1:55:48:a4:fc:
e7:59:46:78:40:36:d2:a9:a1:18:69:82:24:b3:f2:
18:e6:6d:98:07:86:25:2c:93
prime2:
00:db:59:a1:11:94:cb:81:be:97:71:5d:9e:a4:36:
48:4c:7f:d3:9c:ee:1a:71:dd:1e:89:6e:08:cc:2d:
91:d9:5a:2d:6d:56:1f:48:db:72:ac:ea:57:45:0e:
cf:d4:dc:53:99:c1:f8:ce:7a:bb:b8:b9:9c:92:f9:
c7:be:7a:b2:df:69:90:b4:73:c5:a4:64:ea:a4:d3:
47:47:d0:22:e4:7c:17:b5:49:90:5d:b3:05:98:6a:
f5:97:04:42:ad:54:71:4e:e7:fc:e2:c8:c4:43:da:
7b:22:f4:35:4e:10:5c:00:9a:8d:36:de:73:3d:9f:
b0:2b:fb:cd:57:80:3b:dc:fb
exponent1:
00:a4:2e:52:cc:27:99:f8:2a:6f:c1:5f:57:ca:bc:
5d:5b:d6:e5:4f:fc:43:da:89:9c:01:1d:e5:64:7d:
c3:3e:e9:1a:46:1f:e5:71:d5:79:dc:10:7d:d6:8c:
f4:02:71:31:9d:72:bd:fb:55:a8:0a:f0:cc:86:2f:
32:36:73:20:e1:2e:81:b6:17:9b:8e:26:f5:e9:46:
f8:1d:2e:44:d2:71:c6:41:fa:ac:5d:94:85:4d:9b:
bd:55:39:da:7f:1c:d2:c5:02:c3:16:38:db:18:a8:
9a:3b:84:50:2a:cf:37:1b:c0:ba:f1:01:6d:cd:4c:
10:99:9e:65:5a:59:6e:1d:b7
exponent2:
00:92:3b:c0:b6:63:32:56:7f:0f:a0:e9:14:6d:79:
85:88:55:37:bd:f4:11:a1:3e:14:5b:9e:b0:88:1e:
61:3b:91:73:9e:39:6a:30:92:4c:73:46:e4:d8:b4:
8a:8d:e8:37:bb:d6:a5:de:fc:7d:25:d1:13:0c:a6:
85:29:a7:21:ea:46:60:78:4d:2e:6d:98:9c:6d:e2:
2f:85:35:6c:98:52:ba:78:db:b5:93:cc:ae:65:9c:
a3:ba:02:d7:1e:38:4b:89:ef:fd:ec:85:d8:2d:3c:
52:17:4d:78:de:b5:92:ab:11:b3:79:e9:a2:29:15:
20:1d:52:88:e5:00:27:e8:a7
coefficient:
00:b1:63:cc:82:98:e6:3e:a2:94:f2:02:88:14:33:
04:ad:c9:a5:55:ca:17:0e:55:94:29:54:77:38:01:
40:56:52:d8:f9:98:da:54:95:41:78:2b:b5:65:ff:
49:b3:2a:e5:f6:d8:14:bf:38:a8:78:c5:98:c6:30:
7f:c2:94:a0:15:1f:26:81:b8:a3:9d:6a:ce:0a:73:
2f:eb:6c:b5:14:a0:3d:e8:d9:22:90:a8:f1:49:92:
31:a9:45:d6:98:c8:46:1c:de:13:15:6d:9b:fc:5b:
09:ca:3b:f0:d2:7a:77:0f:3a:b3:fe:db:37:5b:d4:
13:5c:8d:cb:57:f9:d6:08:81
```
It can be seen that for the first RSA private key, the numbers `dp` and `c`
(both styled in bold) are not right. This could be potentially dangerous when
signatures are involved.
Because of the Chinese Remainder Theorem, if one uses the incorrectly
computed private key to sign a message and sends the resulting wrong signature
directly without first verifying it, this can lead to the so-called "fault
attack" (e.g., explained
[here](https://www.cryptologie.net/article/371/fault-attacks-on-rsas-signatures/)).
Continuing with the example above, if we sign the message `Hello World\n`
using the first RSA private key:
```C
// somehow this prime number leads to incorrect dp, which is quite weird
OCT_fromHex(&P,
"f55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed");
OCT_fromHex(&Q,"f34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363");
// use our choice of P and Q
RSA_2048_KEY_PAIR(NULL,3,&priv,&pub,&P,&Q);
print_keypair(&priv, &pub);
printf("Signing message\n");
OCT_jstring(&M,(char *)"Hello World\n");
PKCS15(HASH_TYPE_RSA_2048,&M,&C);
RSA_2048_DECRYPT(&priv,&C,&S); /* create signature in S */
printf("Signature= ");
OCT_output(&S);
```
We get a faulty signature: `s =
0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6`.
If an attacker obtains this signature, and knows the choice of hash
algorithm as well as the message of `Hello World\n`, then he/she can also
compute the hash value and prepare the PKCS1v1.5 structure accordingly: `r =
0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26`
And now the attacker can factorize the modulus `n` by computing `GCD(s^e -
r, n)`. In Python3:
```python
import math
# faulty signature
s =
0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6
# precomputed PKCS1v1.5 structure
r =
0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26
# modulus
n =
0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed
*
0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363
# now factorize n
p1 = math.gcd(pow(s,3,n)-r, n)
p2 = n // p1
print("p=",hex(max(p1,p2)))
print("q=",hex(min(p1,p2)))
```
Which outputs
---
p=
0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed
q=
0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363
---
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@milagro.apache.org
For additional commands, e-mail: issues-h...@milagro.apache.org
