You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@milagro.apache.org by GitBox <gi...@apache.org> on 2021/03/28 12:01:46 UTC
[GitHub] [incubator-milagro-crypto-c] mcarrickscott commented on issue #90: Incorrect RSA private key generation and potentials for fault attack
mcarrickscott commented on issue #90:
URL: https://github.com/apache/incubator-milagro-crypto-c/issues/90#issuecomment-808887175
The problem here is that p=1 mod 4 and q=3 mod 4
The Milagro code only works for primes that are 3 mod 4,and the primes it
generates internally are all of this form. In general 3 mod 4 primes are
easier to handle,and since half of all primes are of this form,there is no
loss of generality in restricting to such primes.
The specific problem is that the function invmodp(r,a,n) only calculates
the correct inverse if n is odd. Now p-1 is even, but in p=3 mod 4 case
(given that e is odd) we can calculate inverse(r,a,(p-1)/2) and this will
be correct. But the same trick won't work if p is 1 mod 4, as in that case
(p-1)/2 will still be even. It would not be hard to fix, but probably
simpler just to restrict to 3 mod 4 primes
Mike
On Sun, Mar 28, 2021 at 7:02 AM 1one.w01f ***@***.***> wrote:
> 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.
>
> #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:
>
> $ 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
>
> $ 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:
>
> // 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:
>
> import math
> # faulty signatures = 0xc606cf94940847b48011db1297bc1798af372bb3293e901bc1e065346f9ba1be85afc92e481870b3fe45eebe75e53a95cdeada659388cafcd88ece6ebdf039b57cb83d8119cdf589fa1b61c6ee42dbd59ac015117eb17fb4b8b577c39e42dd1a3041e471d2acf0ec2d669fcb2c85ab8b11309df32ef0a0116e2e579843467e2ee24f18f5a67148e843959df1f316fc3a483ebc9b065f52750f2863ba4a2f38fb1d6f2fa22204b2a723a76de740937438321b0102ce1ffbadbab0b0fcfd0a97f5a1f9d69fe31a4633ec70c0ad552f3be8740607194ee8ee434ca770da81e0c9fbcb02ace5838a848609443535066221ad24e7ff5da1a031fecac579645604a3b6
> # precomputed PKCS1v1.5 structurer = 0x0001ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003031300d060960864801650304020105000420d2a84f4b8b650937ec8f73cd8be2c74add5a911ba64df27458ed8229da804a26
> # modulusn = 0xf55d1f9bde519d3d30e9a0820a0850f3a6d05efa82dcc7ef948a09834224ad6fb77ee792f53b1ee6efc0270e5e8fdd59fab40ada833df0ea69eb2f0b37d717a3fd0329280cd47525fd22970c8fd860c7be749482c42a6e16a4b5b7edf27e01214f55fd5839a11c86be6bbd8b01e5ddeef743bca59e896c1751145d4b6a9da9ed * 0xf34e8af7a6b3b2d2906890db77f56b8c4c5a5af42bec8cacd79fc479606d85eeb641ec95aef73d0e7e24f0da9115a524d9787d573ed3a1868bff2765cc5b9e1238a7931bdd5afd51a0bd6bf93f26909fff6d93d335e6785959c14f851205ad4a8ce995e6f92e490e7a5feab2b9fcda0080bedc17fa816227f2d6034044c0c363
> # now factorize np1 = 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
> ------------------------------
>
> —
> You are receiving this because you are subscribed to this thread.
> Reply to this email directly, view it on GitHub
> <https://github.com/apache/incubator-milagro-crypto-c/issues/90>, or
> unsubscribe
> <https://github.com/notifications/unsubscribe-auth/AAU3ZDS5XX6G5MYXVIHHFA3TF3A7LANCNFSM4Z5WGOQA>
> .
>
--
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:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@milagro.apache.org
For additional commands, e-mail: issues-help@milagro.apache.org