diff --git a/cipher/rsa.c b/cipher/rsa.c index b6c73741..2e13fd6e 100644 --- a/cipher/rsa.c +++ b/cipher/rsa.c @@ -1,1990 +1,1990 @@ /* rsa.c - RSA implementation * Copyright (C) 1997, 1998, 1999 by Werner Koch (dd9jn) * Copyright (C) 2000, 2001, 2002, 2003, 2008 Free Software Foundation, Inc. * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ /* This code uses an algorithm protected by U.S. Patent #4,405,829 which expired on September 20, 2000. The patent holder placed that patent into the public domain on Sep 6th, 2000. */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "pubkey-internal.h" typedef struct { gcry_mpi_t n; /* modulus */ gcry_mpi_t e; /* exponent */ } RSA_public_key; typedef struct { gcry_mpi_t n; /* public modulus */ gcry_mpi_t e; /* public exponent */ gcry_mpi_t d; /* exponent */ gcry_mpi_t p; /* prime p. */ gcry_mpi_t q; /* prime q. */ gcry_mpi_t u; /* inverse of p mod q. */ } RSA_secret_key; static const char *rsa_names[] = { "rsa", "openpgp-rsa", "oid.1.2.840.113549.1.1.1", NULL, }; /* A sample 2048 bit RSA key used for the selftests. */ static const char sample_secret_key[] = " (private-key" " (rsa" " (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC" " 7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8" " 7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C" " 958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917" " DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613" " 6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C" " 42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918" " 664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)" " (e #010001#)" " (d #07EF82500C403899934FE993AC5A36F14FF2DF38CF1EF315F205EE4C83EDAA19" " 8890FC23DE9AA933CAFB37B6A8A8DBA675411958337287310D3FF2F1DDC0CB93" " 7E70F57F75F833C021852B631D2B9A520E4431A03C5C3FCB5742DCD841D9FB12" " 771AA1620DCEC3F1583426066ED9DC3F7028C5B59202C88FDF20396E2FA0EC4F" " 5A22D9008F3043673931BC14A5046D6327398327900867E39CC61B2D1AFE2F48" " EC8E1E3861C68D257D7425F4E6F99ABD77D61F10CA100EFC14389071831B33DD" " 69CC8EABEF860D1DC2AAA84ABEAE5DFC91BC124DAF0F4C8EF5BBEA436751DE84" " 3A8063E827A024466F44C28614F93B0732A100D4A0D86D532FE1E22C7725E401#)" " (p #00C29D438F115825779631CD665A5739367F3E128ADC29766483A46CA80897E0" " 79B32881860B8F9A6A04C2614A904F6F2578DAE13EA67CD60AE3D0AA00A1FF9B" " 441485E44B2DC3D0B60260FBFE073B5AC72FAF67964DE15C8212C389D20DB9CF" " 54AF6AEF5C4196EAA56495DD30CF709F499D5AB30CA35E086C2A1589D6283F1783#)" " (q #00D1984135231CB243FE959C0CBEF551EDD986AD7BEDF71EDF447BE3DA27AF46" " 79C974A6FA69E4D52FE796650623DE70622862713932AA2FD9F2EC856EAEAA77" " 88B4EA6084DC81C902F014829B18EA8B2666EC41586818E0589E18876065F97E" " 8D22CE2DA53A05951EC132DCEF41E70A9C35F4ACC268FFAC2ADF54FA1DA110B919#)" " (u #67CF0FD7635205DD80FA814EE9E9C267C17376BF3209FB5D1BC42890D2822A04" " 479DAF4D5B6ED69D0F8D1AF94164D07F8CD52ECEFE880641FA0F41DDAB1785E4" " A37A32F997A516480B4CD4F6482B9466A1765093ED95023CA32D5EDC1E34CEE9" " AF595BC51FE43C4BF810FA225AF697FB473B83815966188A4312C048B885E3F7#)))"; /* A sample 2048 bit RSA key used for the selftests (public only). */ static const char sample_public_key[] = " (public-key" " (rsa" " (n #009F56231A3D82E3E7D613D59D53E9AB921BEF9F08A782AED0B6E46ADBC853EC" " 7C71C422435A3CD8FA0DB9EFD55CD3295BADC4E8E2E2B94E15AE82866AB8ADE8" " 7E469FAE76DC3577DE87F1F419C4EB41123DFAF8D16922D5EDBAD6E9076D5A1C" " 958106F0AE5E2E9193C6B49124C64C2A241C4075D4AF16299EB87A6585BAE917" " DEF27FCDD165764D069BC18D16527B29DAAB549F7BBED4A7C6A842D203ED6613" " 6E2411744E432CD26D940132F25874483DCAEECDFD95744819CBCF1EA810681C" " 42907EBCB1C7EAFBE75C87EC32C5413EA10476545D3FC7B2ADB1B66B7F200918" " 664B0E5261C2895AA28B0DE321E921B3F877172CCCAB81F43EF98002916156F6CB#)" " (e #010001#)))"; static int test_keys (RSA_secret_key *sk, unsigned nbits); static int check_secret_key (RSA_secret_key *sk); static void public (gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *skey); static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey); static unsigned int rsa_get_nbits (gcry_sexp_t parms); /* Check that a freshly generated key actually works. Returns 0 on success. */ static int test_keys (RSA_secret_key *sk, unsigned int nbits) { int result = -1; /* Default to failure. */ RSA_public_key pk; gcry_mpi_t plaintext = mpi_new (nbits); gcry_mpi_t ciphertext = mpi_new (nbits); gcry_mpi_t decr_plaintext = mpi_new (nbits); gcry_mpi_t signature = mpi_new (nbits); /* Put the relevant parameters into a public key structure. */ pk.n = sk->n; pk.e = sk->e; /* Create a random plaintext. */ _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM); /* Encrypt using the public key. */ public (ciphertext, plaintext, &pk); /* Check that the cipher text does not match the plaintext. */ if (!mpi_cmp (ciphertext, plaintext)) goto leave; /* Ciphertext is identical to the plaintext. */ /* Decrypt using the secret key. */ secret (decr_plaintext, ciphertext, sk); /* Check that the decrypted plaintext matches the original plaintext. */ if (mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Plaintext does not match. */ /* Create another random plaintext as data for signature checking. */ _gcry_mpi_randomize (plaintext, nbits, GCRY_WEAK_RANDOM); /* Use the RSA secret function to create a signature of the plaintext. */ secret (signature, plaintext, sk); /* Use the RSA public function to verify this signature. */ public (decr_plaintext, signature, &pk); if (mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Signature does not match. */ /* Modify the signature and check that the signing fails. */ mpi_add_ui (signature, signature, 1); public (decr_plaintext, signature, &pk); if (!mpi_cmp (decr_plaintext, plaintext)) goto leave; /* Signature matches but should not. */ result = 0; /* All tests succeeded. */ leave: _gcry_mpi_release (signature); _gcry_mpi_release (decr_plaintext); _gcry_mpi_release (ciphertext); _gcry_mpi_release (plaintext); return result; } /* Callback used by the prime generation to test whether the exponent is suitable. Returns 0 if the test has been passed. */ static int check_exponent (void *arg, gcry_mpi_t a) { gcry_mpi_t e = arg; gcry_mpi_t tmp; int result; mpi_sub_ui (a, a, 1); tmp = _gcry_mpi_alloc_like (a); result = !mpi_gcd(tmp, e, a); /* GCD is not 1. */ _gcry_mpi_release (tmp); mpi_add_ui (a, a, 1); return result; } /**************** * Generate a key pair with a key of size NBITS. * USE_E = 0 let Libcgrypt decide what exponent to use. * = 1 request the use of a "secure" exponent; this is required by some * specification to be 65537. * > 2 Use this public exponent. If the given exponent * is not odd one is internally added to it. * TRANSIENT_KEY: If true, generate the primes using the standard RNG. * Returns: 2 structures filled with all needed values */ static gpg_err_code_t generate_std (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, int transient_key) { gcry_mpi_t p, q; /* the two primes */ gcry_mpi_t d; /* the private key */ gcry_mpi_t u; gcry_mpi_t t1, t2; gcry_mpi_t n; /* the public key */ gcry_mpi_t e; /* the exponent */ gcry_mpi_t phi; /* helper: (p-1)(q-1) */ gcry_mpi_t g; gcry_mpi_t f; gcry_random_level_t random_level; if (fips_mode ()) { if (nbits < 1024) return GPG_ERR_INV_VALUE; if (transient_key) return GPG_ERR_INV_VALUE; } /* The random quality depends on the transient_key flag. */ random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; /* Make sure that nbits is even so that we generate p, q of equal size. */ if ( (nbits&1) ) nbits++; if (use_e == 1) /* Alias for a secure value */ use_e = 65537; /* as demanded by Sphinx. */ /* Public exponent: In general we use 41 as this is quite fast and more secure than the commonly used 17. Benchmarking the RSA verify function with a 1024 bit key yields (2001-11-08): e=17 0.54 ms e=41 0.75 ms e=257 0.95 ms e=65537 1.80 ms */ e = mpi_alloc( (32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB ); if (!use_e) mpi_set_ui (e, 41); /* This is a reasonable secure and fast value */ else { use_e |= 1; /* make sure this is odd */ mpi_set_ui (e, use_e); } n = mpi_new (nbits); p = q = NULL; do { /* select two (very secret) primes */ if (p) _gcry_mpi_release (p); if (q) _gcry_mpi_release (q); if (use_e) { /* Do an extra test to ensure that the given exponent is suitable. */ p = _gcry_generate_secret_prime (nbits/2, random_level, check_exponent, e); q = _gcry_generate_secret_prime (nbits/2, random_level, check_exponent, e); } else { /* We check the exponent later. */ p = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL); q = _gcry_generate_secret_prime (nbits/2, random_level, NULL, NULL); } if (mpi_cmp (p, q) > 0 ) /* p shall be smaller than q (for calc of u)*/ mpi_swap(p,q); /* calculate the modulus */ mpi_mul( n, p, q ); } while ( mpi_get_nbits(n) != nbits ); /* calculate Euler totient: phi = (p-1)(q-1) */ t1 = mpi_alloc_secure( mpi_get_nlimbs(p) ); t2 = mpi_alloc_secure( mpi_get_nlimbs(p) ); phi = mpi_snew ( nbits ); g = mpi_snew ( nbits ); f = mpi_snew ( nbits ); mpi_sub_ui( t1, p, 1 ); mpi_sub_ui( t2, q, 1 ); mpi_mul( phi, t1, t2 ); mpi_gcd (g, t1, t2); mpi_fdiv_q(f, phi, g); while (!mpi_gcd(t1, e, phi)) /* (while gcd is not 1) */ { if (use_e) BUG (); /* The prime generator already made sure that we never can get to here. */ mpi_add_ui (e, e, 2); } - /* calculate the secret key d = e^1 mod phi */ + /* calculate the secret key d = e^-1 mod phi */ d = mpi_snew ( nbits ); mpi_invm (d, e, f ); /* calculate the inverse of p and q (used for chinese remainder theorem)*/ u = mpi_snew ( nbits ); mpi_invm(u, p, q ); if( DBG_CIPHER ) { log_mpidump(" p= ", p ); log_mpidump(" q= ", q ); log_mpidump("phi= ", phi ); log_mpidump(" g= ", g ); log_mpidump(" f= ", f ); log_mpidump(" n= ", n ); log_mpidump(" e= ", e ); log_mpidump(" d= ", d ); log_mpidump(" u= ", u ); } _gcry_mpi_release (t1); _gcry_mpi_release (t2); _gcry_mpi_release (phi); _gcry_mpi_release (f); _gcry_mpi_release (g); sk->n = n; sk->e = e; sk->p = p; sk->q = q; sk->d = d; sk->u = u; /* Now we can test our keys. */ if (test_keys (sk, nbits - 64)) { _gcry_mpi_release (sk->n); sk->n = NULL; _gcry_mpi_release (sk->e); sk->e = NULL; _gcry_mpi_release (sk->p); sk->p = NULL; _gcry_mpi_release (sk->q); sk->q = NULL; _gcry_mpi_release (sk->d); sk->d = NULL; _gcry_mpi_release (sk->u); sk->u = NULL; fips_signal_error ("self-test after key generation failed"); return GPG_ERR_SELFTEST_FAILED; } return 0; } /**************** * Generate a key pair with a key of size NBITS. * USE_E = 0 let Libcgrypt decide what exponent to use. * = 1 request the use of a "secure" exponent; this is required by some * specification to be 65537. * > 2 Use this public exponent. If the given exponent * is not odd one is internally added to it. * TESTPARMS: If set, do not generate but test whether the p,q is probably prime * Returns key with zeroes to not break code calling this function. * TRANSIENT_KEY: If true, generate the primes using the standard RNG. * Returns: 2 structures filled with all needed values */ static gpg_err_code_t generate_fips (RSA_secret_key *sk, unsigned int nbits, unsigned long use_e, gcry_sexp_t testparms, int transient_key) { gcry_mpi_t p, q; /* the two primes */ gcry_mpi_t d; /* the private key */ gcry_mpi_t u; gcry_mpi_t p1, q1; gcry_mpi_t n; /* the public key */ gcry_mpi_t e; /* the exponent */ gcry_mpi_t g; gcry_mpi_t minp; gcry_mpi_t diff, mindiff; gcry_random_level_t random_level; unsigned int pbits = nbits/2; unsigned int i; int pqswitch; gpg_err_code_t ec = GPG_ERR_NO_PRIME; if (nbits < 1024 || (nbits & 0x1FF)) return GPG_ERR_INV_VALUE; if (_gcry_enforced_fips_mode() && nbits != 2048 && nbits != 3072) return GPG_ERR_INV_VALUE; /* The random quality depends on the transient_key flag. */ random_level = transient_key ? GCRY_STRONG_RANDOM : GCRY_VERY_STRONG_RANDOM; if (testparms) { /* Parameters to derive the key are given. */ /* Note that we explicitly need to setup the values of tbl because some compilers (e.g. OpenWatcom, IRIX) don't allow to initialize a structure with automatic variables. */ struct { const char *name; gcry_mpi_t *value; } tbl[] = { { "e" }, { "p" }, { "q" }, { NULL } }; int idx; gcry_sexp_t oneparm; tbl[0].value = &e; tbl[1].value = &p; tbl[2].value = &q; for (idx=0; tbl[idx].name; idx++) { oneparm = sexp_find_token (testparms, tbl[idx].name, 0); if (oneparm) { *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG); sexp_release (oneparm); } } for (idx=0; tbl[idx].name; idx++) if (!*tbl[idx].value) break; if (tbl[idx].name) { /* At least one parameter is missing. */ for (idx=0; tbl[idx].name; idx++) _gcry_mpi_release (*tbl[idx].value); return GPG_ERR_MISSING_VALUE; } } else { if (use_e < 65537) use_e = 65537; /* This is the smallest value allowed by FIPS */ e = mpi_alloc ((32+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB); use_e |= 1; /* make sure this is odd */ mpi_set_ui (e, use_e); p = mpi_snew (pbits); q = mpi_snew (pbits); } n = mpi_new (nbits); d = mpi_snew (nbits); u = mpi_snew (nbits); /* prepare approximate minimum p and q */ minp = mpi_new (pbits); mpi_set_ui (minp, 0xB504F334); mpi_lshift (minp, minp, pbits - 32); /* prepare minimum p and q difference */ diff = mpi_new (pbits); mindiff = mpi_new (pbits - 99); mpi_set_ui (mindiff, 1); mpi_lshift (mindiff, mindiff, pbits - 100); p1 = mpi_snew (pbits); q1 = mpi_snew (pbits); g = mpi_snew (pbits); retry: /* generate p and q */ for (i = 0; i < 5 * pbits; i++) { ploop: if (!testparms) { _gcry_mpi_randomize (p, pbits, random_level); } if (mpi_cmp (p, minp) < 0) { if (testparms) goto err; goto ploop; } mpi_sub_ui (p1, p, 1); if (mpi_gcd (g, p1, e)) { if (_gcry_fips186_4_prime_check (p, pbits) != GPG_ERR_NO_ERROR) { /* not a prime */ if (testparms) goto err; } else break; } else if (testparms) goto err; } if (i >= 5 * pbits) goto err; for (i = 0; i < 5 * pbits; i++) { qloop: if (!testparms) { _gcry_mpi_randomize (q, pbits, random_level); } if (mpi_cmp (q, minp) < 0) { if (testparms) goto err; goto qloop; } if (mpi_cmp (p, q) > 0) { pqswitch = 1; mpi_sub (diff, p, q); } else { pqswitch = 0; mpi_sub (diff, q, p); } if (mpi_cmp (diff, mindiff) < 0) { if (testparms) goto err; goto qloop; } mpi_sub_ui (q1, q, 1); if (mpi_gcd (g, q1, e)) { if (_gcry_fips186_4_prime_check (q, pbits) != GPG_ERR_NO_ERROR) { /* not a prime */ if (testparms) goto err; } else break; } else if (testparms) goto err; } if (i >= 5 * pbits) goto err; if (testparms) { mpi_clear (p); mpi_clear (q); } else { gcry_mpi_t f; if (pqswitch) { gcry_mpi_t tmp; tmp = p; p = q; q = tmp; } f = mpi_snew (nbits); /* calculate the modulus */ mpi_mul (n, p, q); /* calculate the secret key d = e^1 mod phi */ mpi_gcd (g, p1, q1); mpi_fdiv_q (f, p1, g); mpi_mul (f, f, q1); mpi_invm (d, e, f); _gcry_mpi_release (f); if (mpi_get_nbits (d) < pbits) goto retry; /* calculate the inverse of p and q (used for chinese remainder theorem)*/ mpi_invm (u, p, q ); } ec = 0; if (DBG_CIPHER) { log_mpidump(" p= ", p ); log_mpidump(" q= ", q ); log_mpidump(" n= ", n ); log_mpidump(" e= ", e ); log_mpidump(" d= ", d ); log_mpidump(" u= ", u ); } err: _gcry_mpi_release (p1); _gcry_mpi_release (q1); _gcry_mpi_release (g); _gcry_mpi_release (minp); _gcry_mpi_release (mindiff); _gcry_mpi_release (diff); sk->n = n; sk->e = e; sk->p = p; sk->q = q; sk->d = d; sk->u = u; /* Now we can test our keys. */ if (ec || (!testparms && test_keys (sk, nbits - 64))) { _gcry_mpi_release (sk->n); sk->n = NULL; _gcry_mpi_release (sk->e); sk->e = NULL; _gcry_mpi_release (sk->p); sk->p = NULL; _gcry_mpi_release (sk->q); sk->q = NULL; _gcry_mpi_release (sk->d); sk->d = NULL; _gcry_mpi_release (sk->u); sk->u = NULL; if (!ec) { fips_signal_error ("self-test after key generation failed"); return GPG_ERR_SELFTEST_FAILED; } } return ec; } /* Helper for generate_x931. */ static gcry_mpi_t gen_x931_parm_xp (unsigned int nbits) { gcry_mpi_t xp; xp = mpi_snew (nbits); _gcry_mpi_randomize (xp, nbits, GCRY_VERY_STRONG_RANDOM); /* The requirement for Xp is: sqrt{2}*2^{nbits-1} <= xp <= 2^{nbits} - 1 We set the two high order bits to 1 to satisfy the lower bound. By using mpi_set_highbit we make sure that the upper bound is satisfied as well. */ mpi_set_highbit (xp, nbits-1); mpi_set_bit (xp, nbits-2); gcry_assert ( mpi_get_nbits (xp) == nbits ); return xp; } /* Helper for generate_x931. */ static gcry_mpi_t gen_x931_parm_xi (void) { gcry_mpi_t xi; xi = mpi_snew (101); _gcry_mpi_randomize (xi, 101, GCRY_VERY_STRONG_RANDOM); mpi_set_highbit (xi, 100); gcry_assert ( mpi_get_nbits (xi) == 101 ); return xi; } /* Variant of the standard key generation code using the algorithm from X9.31. Using this algorithm has the advantage that the generation can be made deterministic which is required for CAVS testing. */ static gpg_err_code_t generate_x931 (RSA_secret_key *sk, unsigned int nbits, unsigned long e_value, gcry_sexp_t deriveparms, int *swapped) { gcry_mpi_t p, q; /* The two primes. */ gcry_mpi_t e; /* The public exponent. */ gcry_mpi_t n; /* The public key. */ gcry_mpi_t d; /* The private key */ gcry_mpi_t u; /* The inverse of p and q. */ gcry_mpi_t pm1; /* p - 1 */ gcry_mpi_t qm1; /* q - 1 */ gcry_mpi_t phi; /* Euler totient. */ gcry_mpi_t f, g; /* Helper. */ *swapped = 0; if (e_value == 1) /* Alias for a secure value. */ e_value = 65537; /* Point 1 of section 4.1: k = 1024 + 256s with S >= 0 */ if (nbits < 1024 || (nbits % 256)) return GPG_ERR_INV_VALUE; /* Point 2: 2 <= bitlength(e) < 2^{k-2} Note that we do not need to check the upper bound because we use an unsigned long for E and thus there is no way for E to reach that limit. */ if (e_value < 3) return GPG_ERR_INV_VALUE; /* Our implementaion requires E to be odd. */ if (!(e_value & 1)) return GPG_ERR_INV_VALUE; /* Point 3: e > 0 or e 0 if it is to be randomly generated. We support only a fixed E and thus there is no need for an extra test. */ /* Compute or extract the derive parameters. */ { gcry_mpi_t xp1 = NULL; gcry_mpi_t xp2 = NULL; gcry_mpi_t xp = NULL; gcry_mpi_t xq1 = NULL; gcry_mpi_t xq2 = NULL; gcry_mpi_t xq = NULL; gcry_mpi_t tmpval; if (!deriveparms) { /* Not given: Generate them. */ xp = gen_x931_parm_xp (nbits/2); /* Make sure that |xp - xq| > 2^{nbits - 100} holds. */ tmpval = mpi_snew (nbits/2); do { _gcry_mpi_release (xq); xq = gen_x931_parm_xp (nbits/2); mpi_sub (tmpval, xp, xq); } while (mpi_get_nbits (tmpval) <= (nbits/2 - 100)); _gcry_mpi_release (tmpval); xp1 = gen_x931_parm_xi (); xp2 = gen_x931_parm_xi (); xq1 = gen_x931_parm_xi (); xq2 = gen_x931_parm_xi (); } else { /* Parameters to derive the key are given. */ /* Note that we explicitly need to setup the values of tbl because some compilers (e.g. OpenWatcom, IRIX) don't allow to initialize a structure with automatic variables. */ struct { const char *name; gcry_mpi_t *value; } tbl[] = { { "Xp1" }, { "Xp2" }, { "Xp" }, { "Xq1" }, { "Xq2" }, { "Xq" }, { NULL } }; int idx; gcry_sexp_t oneparm; tbl[0].value = &xp1; tbl[1].value = &xp2; tbl[2].value = &xp; tbl[3].value = &xq1; tbl[4].value = &xq2; tbl[5].value = &xq; for (idx=0; tbl[idx].name; idx++) { oneparm = sexp_find_token (deriveparms, tbl[idx].name, 0); if (oneparm) { *tbl[idx].value = sexp_nth_mpi (oneparm, 1, GCRYMPI_FMT_USG); sexp_release (oneparm); } } for (idx=0; tbl[idx].name; idx++) if (!*tbl[idx].value) break; if (tbl[idx].name) { /* At least one parameter is missing. */ for (idx=0; tbl[idx].name; idx++) _gcry_mpi_release (*tbl[idx].value); return GPG_ERR_MISSING_VALUE; } } e = mpi_alloc_set_ui (e_value); /* Find two prime numbers. */ p = _gcry_derive_x931_prime (xp, xp1, xp2, e, NULL, NULL); q = _gcry_derive_x931_prime (xq, xq1, xq2, e, NULL, NULL); _gcry_mpi_release (xp); xp = NULL; _gcry_mpi_release (xp1); xp1 = NULL; _gcry_mpi_release (xp2); xp2 = NULL; _gcry_mpi_release (xq); xq = NULL; _gcry_mpi_release (xq1); xq1 = NULL; _gcry_mpi_release (xq2); xq2 = NULL; if (!p || !q) { _gcry_mpi_release (p); _gcry_mpi_release (q); _gcry_mpi_release (e); return GPG_ERR_NO_PRIME; } } /* Compute the public modulus. We make sure that p is smaller than q to allow the use of the CRT. */ if (mpi_cmp (p, q) > 0 ) { mpi_swap (p, q); *swapped = 1; } n = mpi_new (nbits); mpi_mul (n, p, q); /* Compute the Euler totient: phi = (p-1)(q-1) */ pm1 = mpi_snew (nbits/2); qm1 = mpi_snew (nbits/2); phi = mpi_snew (nbits); mpi_sub_ui (pm1, p, 1); mpi_sub_ui (qm1, q, 1); mpi_mul (phi, pm1, qm1); g = mpi_snew (nbits); gcry_assert (mpi_gcd (g, e, phi)); /* Compute: f = lcm(p-1,q-1) = phi / gcd(p-1,q-1) */ mpi_gcd (g, pm1, qm1); f = pm1; pm1 = NULL; _gcry_mpi_release (qm1); qm1 = NULL; mpi_fdiv_q (f, phi, g); _gcry_mpi_release (phi); phi = NULL; d = g; g = NULL; /* Compute the secret key: d = e^{-1} mod lcm(p-1,q-1) */ mpi_invm (d, e, f); /* Compute the inverse of p and q. */ u = f; f = NULL; mpi_invm (u, p, q ); if( DBG_CIPHER ) { if (*swapped) log_debug ("p and q are swapped\n"); log_mpidump(" p", p ); log_mpidump(" q", q ); log_mpidump(" n", n ); log_mpidump(" e", e ); log_mpidump(" d", d ); log_mpidump(" u", u ); } sk->n = n; sk->e = e; sk->p = p; sk->q = q; sk->d = d; sk->u = u; /* Now we can test our keys. */ if (test_keys (sk, nbits - 64)) { _gcry_mpi_release (sk->n); sk->n = NULL; _gcry_mpi_release (sk->e); sk->e = NULL; _gcry_mpi_release (sk->p); sk->p = NULL; _gcry_mpi_release (sk->q); sk->q = NULL; _gcry_mpi_release (sk->d); sk->d = NULL; _gcry_mpi_release (sk->u); sk->u = NULL; fips_signal_error ("self-test after key generation failed"); return GPG_ERR_SELFTEST_FAILED; } return 0; } /**************** * Test whether the secret key is valid. * Returns: true if this is a valid key. */ static int check_secret_key( RSA_secret_key *sk ) { int rc; gcry_mpi_t temp = mpi_alloc( mpi_get_nlimbs(sk->p)*2 ); mpi_mul(temp, sk->p, sk->q ); rc = mpi_cmp( temp, sk->n ); mpi_free(temp); return !rc; } /**************** * Public key operation. Encrypt INPUT with PKEY and put result into OUTPUT. * * c = m^e mod n * * Where c is OUTPUT, m is INPUT and e,n are elements of PKEY. */ static void public(gcry_mpi_t output, gcry_mpi_t input, RSA_public_key *pkey ) { if( output == input ) /* powm doesn't like output and input the same */ { gcry_mpi_t x = mpi_alloc( mpi_get_nlimbs(input)*2 ); mpi_powm( x, input, pkey->e, pkey->n ); mpi_set(output, x); mpi_free(x); } else mpi_powm( output, input, pkey->e, pkey->n ); } #if 0 static void stronger_key_check ( RSA_secret_key *skey ) { gcry_mpi_t t = mpi_alloc_secure ( 0 ); gcry_mpi_t t1 = mpi_alloc_secure ( 0 ); gcry_mpi_t t2 = mpi_alloc_secure ( 0 ); gcry_mpi_t phi = mpi_alloc_secure ( 0 ); /* check that n == p * q */ mpi_mul( t, skey->p, skey->q); if (mpi_cmp( t, skey->n) ) log_info ( "RSA Oops: n != p * q\n" ); /* check that p is less than q */ if( mpi_cmp( skey->p, skey->q ) > 0 ) { log_info ("RSA Oops: p >= q - fixed\n"); _gcry_mpi_swap ( skey->p, skey->q); } /* check that e divides neither p-1 nor q-1 */ mpi_sub_ui(t, skey->p, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides p-1\n" ); mpi_sub_ui(t, skey->q, 1 ); mpi_fdiv_r(t, t, skey->e ); if ( !mpi_cmp_ui( t, 0) ) log_info ( "RSA Oops: e divides q-1\n" ); /* check that d is correct */ mpi_sub_ui( t1, skey->p, 1 ); mpi_sub_ui( t2, skey->q, 1 ); mpi_mul( phi, t1, t2 ); gcry_mpi_gcd(t, t1, t2); mpi_fdiv_q(t, phi, t); mpi_invm(t, skey->e, t ); if ( mpi_cmp(t, skey->d ) ) { log_info ( "RSA Oops: d is wrong - fixed\n"); mpi_set (skey->d, t); log_printmpi (" fixed d", skey->d); } /* check for correctness of u */ mpi_invm(t, skey->p, skey->q ); if ( mpi_cmp(t, skey->u ) ) { log_info ( "RSA Oops: u is wrong - fixed\n"); mpi_set (skey->u, t); log_printmpi (" fixed u", skey->u); } log_info ( "RSA secret key check finished\n"); mpi_free (t); mpi_free (t1); mpi_free (t2); mpi_free (phi); } #endif /**************** * Secret key operation. Encrypt INPUT with SKEY and put result into OUTPUT. * * m = c^d mod n * * Or faster: * * m1 = c ^ (d mod (p-1)) mod p * m2 = c ^ (d mod (q-1)) mod q * h = u * (m2 - m1) mod q * m = m1 + h * p * * Where m is OUTPUT, c is INPUT and d,n,p,q,u are elements of SKEY. */ static void secret (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *skey ) { /* Remove superfluous leading zeroes from INPUT. */ mpi_normalize (input); if (!skey->p || !skey->q || !skey->u) { mpi_powm (output, input, skey->d, skey->n); } else { gcry_mpi_t m1 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t m2 = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); gcry_mpi_t h = mpi_alloc_secure( mpi_get_nlimbs(skey->n)+1 ); /* m1 = c ^ (d mod (p-1)) mod p */ mpi_sub_ui( h, skey->p, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m1, input, h, skey->p ); /* m2 = c ^ (d mod (q-1)) mod q */ mpi_sub_ui( h, skey->q, 1 ); mpi_fdiv_r( h, skey->d, h ); mpi_powm( m2, input, h, skey->q ); /* h = u * ( m2 - m1 ) mod q */ mpi_sub( h, m2, m1 ); if ( mpi_has_sign ( h ) ) mpi_add ( h, h, skey->q ); mpi_mulm( h, skey->u, h, skey->q ); /* m = m1 + h * p */ mpi_mul ( h, h, skey->p ); mpi_add ( output, m1, h ); mpi_free ( h ); mpi_free ( m1 ); mpi_free ( m2 ); } } static void secret_blinded (gcry_mpi_t output, gcry_mpi_t input, RSA_secret_key *sk, unsigned int nbits) { gcry_mpi_t r; /* Random number needed for blinding. */ gcry_mpi_t ri; /* Modular multiplicative inverse of r. */ gcry_mpi_t bldata; /* Blinded data to decrypt. */ /* First, we need a random number r between 0 and n - 1, which is * relatively prime to n (i.e. it is neither p nor q). The random * number needs to be only unpredictable, thus we employ the * gcry_create_nonce function by using GCRY_WEAK_RANDOM with * gcry_mpi_randomize. */ r = mpi_snew (nbits); ri = mpi_snew (nbits); bldata = mpi_snew (nbits); do { _gcry_mpi_randomize (r, nbits, GCRY_WEAK_RANDOM); mpi_mod (r, r, sk->n); } while (!mpi_invm (ri, r, sk->n)); /* Do blinding. We calculate: y = (x * r^e) mod n, where r is the * random number, e is the public exponent, x is the non-blinded * input data and n is the RSA modulus. */ mpi_powm (bldata, r, sk->e, sk->n); mpi_mulm (bldata, bldata, input, sk->n); /* Perform decryption. */ secret (output, bldata, sk); _gcry_mpi_release (bldata); /* Undo blinding. Here we calculate: y = (x * r^-1) mod n, where x * is the blinded decrypted data, ri is the modular multiplicative * inverse of r and n is the RSA modulus. */ mpi_mulm (output, output, ri, sk->n); _gcry_mpi_release (r); _gcry_mpi_release (ri); } /********************************************* ************** interface ****************** *********************************************/ static gcry_err_code_t rsa_generate (const gcry_sexp_t genparms, gcry_sexp_t *r_skey) { gpg_err_code_t ec; unsigned int nbits; unsigned long evalue; RSA_secret_key sk; gcry_sexp_t deriveparms; int flags = 0; gcry_sexp_t l1; gcry_sexp_t swap_info = NULL; memset (&sk, 0, sizeof sk); ec = _gcry_pk_util_get_nbits (genparms, &nbits); if (ec) return ec; ec = _gcry_pk_util_get_rsa_use_e (genparms, &evalue); if (ec) return ec; /* Parse the optional flags list. */ l1 = sexp_find_token (genparms, "flags", 0); if (l1) { ec = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); sexp_release (l1); if (ec) return ec; } deriveparms = (genparms? sexp_find_token (genparms, "derive-parms", 0) : NULL); if (!deriveparms) { /* Parse the optional "use-x931" flag. */ l1 = sexp_find_token (genparms, "use-x931", 0); if (l1) { flags |= PUBKEY_FLAG_USE_X931; sexp_release (l1); } } if (deriveparms || (flags & PUBKEY_FLAG_USE_X931)) { int swapped; ec = generate_x931 (&sk, nbits, evalue, deriveparms, &swapped); sexp_release (deriveparms); if (!ec && swapped) ec = sexp_new (&swap_info, "(misc-key-info(p-q-swapped))", 0, 1); } else { /* Parse the optional "transient-key" flag. */ if (!(flags & PUBKEY_FLAG_TRANSIENT_KEY)) { l1 = sexp_find_token (genparms, "transient-key", 0); if (l1) { flags |= PUBKEY_FLAG_TRANSIENT_KEY; sexp_release (l1); } } deriveparms = (genparms? sexp_find_token (genparms, "test-parms", 0) /**/ : NULL); /* Generate. */ if (deriveparms || fips_mode()) { ec = generate_fips (&sk, nbits, evalue, deriveparms, !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); } else { ec = generate_std (&sk, nbits, evalue, !!(flags & PUBKEY_FLAG_TRANSIENT_KEY)); } sexp_release (deriveparms); } if (!ec) { ec = sexp_build (r_skey, NULL, "(key-data" " (public-key" " (rsa(n%m)(e%m)))" " (private-key" " (rsa(n%m)(e%m)(d%m)(p%m)(q%m)(u%m)))" " %S)", sk.n, sk.e, sk.n, sk.e, sk.d, sk.p, sk.q, sk.u, swap_info); } mpi_free (sk.n); mpi_free (sk.e); mpi_free (sk.p); mpi_free (sk.q); mpi_free (sk.d); mpi_free (sk.u); sexp_release (swap_info); return ec; } static gcry_err_code_t rsa_check_secret_key (gcry_sexp_t keyparms) { gcry_err_code_t rc; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; /* To check the key we need the optional parameters. */ rc = sexp_extract_param (keyparms, NULL, "nedpqu", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (!check_secret_key (&sk)) rc = GPG_ERR_BAD_SECKEY; leave: _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); if (DBG_CIPHER) log_debug ("rsa_testkey => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_encrypt (gcry_sexp_t *r_ciph, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_mpi_t data = NULL; RSA_public_key pk = {NULL, NULL}; gcry_mpi_t ciph = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_ENCRYPT, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_mpidump ("rsa_encrypt data", data); if (!data || mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_mpidump ("rsa_encrypt n", pk.n); log_mpidump ("rsa_encrypt e", pk.e); } /* Do RSA computation and build result. */ ciph = mpi_new (0); public (ciph, data, &pk); if (DBG_CIPHER) log_mpidump ("rsa_encrypt res", ciph); if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN)) { /* We need to make sure to return the correct length to avoid problems with missing leading zeroes. */ unsigned char *em; size_t emlen = (mpi_get_nbits (pk.n)+7)/8; rc = _gcry_mpi_to_octet_string (&em, NULL, ciph, emlen); if (!rc) { rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%b)))", (int)emlen, em); xfree (em); } } else rc = sexp_build (r_ciph, NULL, "(enc-val(rsa(a%m)))", ciph); leave: _gcry_mpi_release (ciph); _gcry_mpi_release (pk.n); _gcry_mpi_release (pk.e); _gcry_mpi_release (data); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_encrypt => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_decrypt (gcry_sexp_t *r_plain, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gpg_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; gcry_mpi_t data = NULL; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; gcry_mpi_t plain = NULL; unsigned char *unpad = NULL; size_t unpadlen = 0; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_DECRYPT, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_preparse_encval (s_data, rsa_names, &l1, &ctx); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, "a", &data, NULL); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_decrypt data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_decrypt n", sk.n); log_printmpi ("rsa_decrypt e", sk.e); if (!fips_mode ()) { log_printmpi ("rsa_decrypt d", sk.d); log_printmpi ("rsa_decrypt p", sk.p); log_printmpi ("rsa_decrypt q", sk.q); log_printmpi ("rsa_decrypt u", sk.u); } } /* Better make sure that there are no superfluous leading zeroes in the input and it has not been "padded" using multiples of N. This mitigates side-channel attacks (CVE-2013-4576). */ mpi_normalize (data); mpi_fdiv_r (data, data, sk.n); /* Allocate MPI for the plaintext. */ plain = mpi_snew (ctx.nbits); /* We use blinding by default to mitigate timing attacks which can be practically mounted over the network as shown by Brumley and Boney in 2003. */ if ((ctx.flags & PUBKEY_FLAG_NO_BLINDING)) secret (plain, data, &sk); else secret_blinded (plain, data, &sk, ctx.nbits); if (DBG_CIPHER) log_printmpi ("rsa_decrypt res", plain); /* Reverse the encoding and build the s-expression. */ switch (ctx.encoding) { case PUBKEY_ENC_PKCS1: rc = _gcry_rsa_pkcs1_decode_for_enc (&unpad, &unpadlen, ctx.nbits, plain); mpi_free (plain); plain = NULL; if (!rc) rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad); break; case PUBKEY_ENC_OAEP: rc = _gcry_rsa_oaep_decode (&unpad, &unpadlen, ctx.nbits, ctx.hash_algo, plain, ctx.label, ctx.labellen); mpi_free (plain); plain = NULL; if (!rc) rc = sexp_build (r_plain, NULL, "(value %b)", (int)unpadlen, unpad); break; default: /* Raw format. For backward compatibility we need to assume a signed mpi by using the sexp format string "%m". */ rc = sexp_build (r_plain, NULL, (ctx.flags & PUBKEY_FLAG_LEGACYRESULT) ? "%m":"(value %m)", plain); break; } leave: xfree (unpad); _gcry_mpi_release (plain); _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); _gcry_mpi_release (data); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_decrypt => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_sign (gcry_sexp_t *r_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gpg_err_code_t rc; struct pk_encoding_ctx ctx; gcry_mpi_t data = NULL; RSA_secret_key sk = {NULL, NULL, NULL, NULL, NULL, NULL}; RSA_public_key pk; gcry_mpi_t sig = NULL; gcry_mpi_t result = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_SIGN, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_sign data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "nedp?q?u?", &sk.n, &sk.e, &sk.d, &sk.p, &sk.q, &sk.u, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_sign n", sk.n); log_printmpi ("rsa_sign e", sk.e); if (!fips_mode ()) { log_printmpi ("rsa_sign d", sk.d); log_printmpi ("rsa_sign p", sk.p); log_printmpi ("rsa_sign q", sk.q); log_printmpi ("rsa_sign u", sk.u); } } /* Do RSA computation. */ sig = mpi_new (0); if ((ctx.flags & PUBKEY_FLAG_NO_BLINDING)) secret (sig, data, &sk); else secret_blinded (sig, data, &sk, ctx.nbits); if (DBG_CIPHER) log_printmpi ("rsa_sign res", sig); /* Check that the created signature is good. This detects a failure of the CRT algorithm (Lenstra's attack on RSA's use of the CRT). */ result = mpi_new (0); pk.n = sk.n; pk.e = sk.e; public (result, sig, &pk); if (mpi_cmp (result, data)) { rc = GPG_ERR_BAD_SIGNATURE; goto leave; } /* Convert the result. */ if ((ctx.flags & PUBKEY_FLAG_FIXEDLEN)) { /* We need to make sure to return the correct length to avoid problems with missing leading zeroes. */ unsigned char *em; size_t emlen = (mpi_get_nbits (sk.n)+7)/8; rc = _gcry_mpi_to_octet_string (&em, NULL, sig, emlen); if (!rc) { rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%b)))", (int)emlen, em); xfree (em); } } else rc = sexp_build (r_sig, NULL, "(sig-val(rsa(s%M)))", sig); leave: _gcry_mpi_release (result); _gcry_mpi_release (sig); _gcry_mpi_release (sk.n); _gcry_mpi_release (sk.e); _gcry_mpi_release (sk.d); _gcry_mpi_release (sk.p); _gcry_mpi_release (sk.q); _gcry_mpi_release (sk.u); _gcry_mpi_release (data); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_sign => %s\n", gpg_strerror (rc)); return rc; } static gcry_err_code_t rsa_verify (gcry_sexp_t s_sig, gcry_sexp_t s_data, gcry_sexp_t keyparms) { gcry_err_code_t rc; struct pk_encoding_ctx ctx; gcry_sexp_t l1 = NULL; gcry_mpi_t sig = NULL; gcry_mpi_t data = NULL; RSA_public_key pk = { NULL, NULL }; gcry_mpi_t result = NULL; _gcry_pk_util_init_encoding_ctx (&ctx, PUBKEY_OP_VERIFY, rsa_get_nbits (keyparms)); /* Extract the data. */ rc = _gcry_pk_util_data_to_mpi (s_data, &data, &ctx); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_verify data", data); if (mpi_is_opaque (data)) { rc = GPG_ERR_INV_DATA; goto leave; } /* Extract the signature value. */ rc = _gcry_pk_util_preparse_sigval (s_sig, rsa_names, &l1, NULL); if (rc) goto leave; rc = sexp_extract_param (l1, NULL, "s", &sig, NULL); if (rc) goto leave; if (DBG_CIPHER) log_printmpi ("rsa_verify sig", sig); /* Extract the key. */ rc = sexp_extract_param (keyparms, NULL, "ne", &pk.n, &pk.e, NULL); if (rc) goto leave; if (DBG_CIPHER) { log_printmpi ("rsa_verify n", pk.n); log_printmpi ("rsa_verify e", pk.e); } /* Do RSA computation and compare. */ result = mpi_new (0); public (result, sig, &pk); if (DBG_CIPHER) log_printmpi ("rsa_verify cmp", result); if (ctx.verify_cmp) rc = ctx.verify_cmp (&ctx, result); else rc = mpi_cmp (result, data) ? GPG_ERR_BAD_SIGNATURE : 0; leave: _gcry_mpi_release (result); _gcry_mpi_release (pk.n); _gcry_mpi_release (pk.e); _gcry_mpi_release (data); _gcry_mpi_release (sig); sexp_release (l1); _gcry_pk_util_free_encoding_ctx (&ctx); if (DBG_CIPHER) log_debug ("rsa_verify => %s\n", rc?gpg_strerror (rc):"Good"); return rc; } /* Return the number of bits for the key described by PARMS. On error * 0 is returned. The format of PARMS starts with the algorithm name; * for example: * * (rsa * (n ) * (e )) * * More parameters may be given but we only need N here. */ static unsigned int rsa_get_nbits (gcry_sexp_t parms) { gcry_sexp_t l1; gcry_mpi_t n; unsigned int nbits; l1 = sexp_find_token (parms, "n", 1); if (!l1) return 0; /* Parameter N not found. */ n = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); sexp_release (l1); nbits = n? mpi_get_nbits (n) : 0; _gcry_mpi_release (n); return nbits; } /* Compute a keygrip. MD is the hash context which we are going to update. KEYPARAM is an S-expression with the key parameters, this is usually a public key but may also be a secret key. An example of such an S-expression is: (rsa (n #00B...#) (e #010001#)) PKCS-15 says that for RSA only the modulus should be hashed - however, it is not clear whether this is meant to use the raw bytes (assuming this is an unsigned integer) or whether the DER required 0 should be prefixed. We hash the raw bytes. */ static gpg_err_code_t compute_keygrip (gcry_md_hd_t md, gcry_sexp_t keyparam) { gcry_sexp_t l1; const char *data; size_t datalen; l1 = sexp_find_token (keyparam, "n", 1); if (!l1) return GPG_ERR_NO_OBJ; data = sexp_nth_data (l1, 1, &datalen); if (!data) { sexp_release (l1); return GPG_ERR_NO_OBJ; } _gcry_md_write (md, data, datalen); sexp_release (l1); return 0; } /* Self-test section. */ static const char * selftest_sign_2048 (gcry_sexp_t pkey, gcry_sexp_t skey) { static const char sample_data[] = "(data (flags pkcs1)" " (hash sha256 #11223344556677889900aabbccddeeff" /**/ "102030405060708090a0b0c0d0f01121#))"; static const char sample_data_bad[] = "(data (flags pkcs1)" " (hash sha256 #11223344556677889900aabbccddeeff" /**/ "802030405060708090a0b0c0d0f01121#))"; const char *errtxt = NULL; gcry_error_t err; gcry_sexp_t data = NULL; gcry_sexp_t data_bad = NULL; gcry_sexp_t sig = NULL; /* raw signature data reference */ const char ref_data[] = "6252a19a11e1d5155ed9376036277193d644fa239397fff03e9b92d6f86415d6" "d30da9273775f290e580d038295ff8ff89522becccfa6ae870bf76b76df402a8" "54f69347e3db3de8e1e7d4dada281ec556810c7a8ecd0b5f51f9b1c0e7aa7557" "61aa2b8ba5f811304acc6af0eca41fe49baf33bf34eddaf44e21e036ac7f0b68" "03cdef1c60021fb7b5b97ebacdd88ab755ce29af568dbc5728cc6e6eff42618d" "62a0386ca8beed46402bdeeef29b6a3feded906bace411a06a39192bf516ae10" "67e4320fa8ea113968525f4574d022a3ceeaafdc41079efe1f22cc94bf59d8d3" "328085da9674857db56de5978a62394aab48aa3b72e23a1b16260cfd9daafe65"; gcry_mpi_t ref_mpi = NULL; gcry_mpi_t sig_mpi = NULL; err = sexp_sscan (&data, NULL, sample_data, strlen (sample_data)); if (!err) err = sexp_sscan (&data_bad, NULL, sample_data_bad, strlen (sample_data_bad)); if (err) { errtxt = "converting data failed"; goto leave; } err = _gcry_pk_sign (&sig, data, skey); if (err) { errtxt = "signing failed"; goto leave; } err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL); if (err) { errtxt = "converting ref_data to mpi failed"; goto leave; } err = _gcry_sexp_extract_param(sig, "sig-val!rsa", "s", &sig_mpi, NULL); if (err) { errtxt = "extracting signature data failed"; goto leave; } if (mpi_cmp (sig_mpi, ref_mpi)) { errtxt = "signature does not match reference data"; goto leave; } err = _gcry_pk_verify (sig, data, pkey); if (err) { errtxt = "verify failed"; goto leave; } err = _gcry_pk_verify (sig, data_bad, pkey); if (gcry_err_code (err) != GPG_ERR_BAD_SIGNATURE) { errtxt = "bad signature not detected"; goto leave; } leave: sexp_release (sig); sexp_release (data_bad); sexp_release (data); _gcry_mpi_release (ref_mpi); _gcry_mpi_release (sig_mpi); return errtxt; } /* Given an S-expression ENCR_DATA of the form: (enc-val (rsa (a a-value))) as returned by gcry_pk_decrypt, return the the A-VALUE. On error, return NULL. */ static gcry_mpi_t extract_a_from_sexp (gcry_sexp_t encr_data) { gcry_sexp_t l1, l2, l3; gcry_mpi_t a_value; l1 = sexp_find_token (encr_data, "enc-val", 0); if (!l1) return NULL; l2 = sexp_find_token (l1, "rsa", 0); sexp_release (l1); if (!l2) return NULL; l3 = sexp_find_token (l2, "a", 0); sexp_release (l2); if (!l3) return NULL; a_value = sexp_nth_mpi (l3, 1, 0); sexp_release (l3); return a_value; } static const char * selftest_encr_2048 (gcry_sexp_t pkey, gcry_sexp_t skey) { const char *errtxt = NULL; gcry_error_t err; static const char plaintext[] = "Jim quickly realized that the beautiful gowns are expensive."; gcry_sexp_t plain = NULL; gcry_sexp_t encr = NULL; gcry_mpi_t ciphertext = NULL; gcry_sexp_t decr = NULL; char *decr_plaintext = NULL; gcry_sexp_t tmplist = NULL; /* expected result of encrypting the plaintext with sample_secret_key */ static const char ref_data[] = "18022e2593a402a737caaa93b4c7e750e20ca265452980e1d6b7710fbd3e" "7dce72be5c2110fb47691cb38f42170ee3b4a37f2498d4a51567d762585e" "4cb81d04fbc7df4144f8e5eac2d4b8688521b64011f11d7ad53f4c874004" "819856f2e2a6f83d1c9c4e73ac26089789c14482b0b8d44139133c88c4a5" "2dba9dd6d6ffc622666b7d129168333d999706af30a2d7d272db7734e5ed" "fb8c64ea3018af3ad20f4a013a5060cb0f5e72753967bebe294280a6ed0d" "dbd3c4f11d0a8696e9d32a0dc03deb0b5e49b2cbd1503392642d4e1211f3" "e8e2ee38abaa3671ccd57fcde8ca76e85fd2cb77c35706a970a213a27352" "cec92a9604d543ddb5fc478ff50e0622"; gcry_mpi_t ref_mpi = NULL; /* Put the plaintext into an S-expression. */ err = sexp_build (&plain, NULL, "(data (flags raw) (value %s))", plaintext); if (err) { errtxt = "converting data failed"; goto leave; } /* Encrypt. */ err = _gcry_pk_encrypt (&encr, plain, pkey); if (err) { errtxt = "encrypt failed"; goto leave; } err = _gcry_mpi_scan(&ref_mpi, GCRYMPI_FMT_HEX, ref_data, 0, NULL); if (err) { errtxt = "converting encrydata to mpi failed"; goto leave; } /* Extraxt the ciphertext from the returned S-expression. */ /*sexp_dump (encr);*/ ciphertext = extract_a_from_sexp (encr); if (!ciphertext) { errtxt = "gcry_pk_decrypt returned garbage"; goto leave; } /* Check that the ciphertext does no match the plaintext. */ /* _gcry_log_printmpi ("plaintext", plaintext); */ /* _gcry_log_printmpi ("ciphertxt", ciphertext); */ if (mpi_cmp (ref_mpi, ciphertext)) { errtxt = "ciphertext doesn't match reference data"; goto leave; } /* Decrypt. */ err = _gcry_pk_decrypt (&decr, encr, skey); if (err) { errtxt = "decrypt failed"; goto leave; } /* Extract the decrypted data from the S-expression. Note that the output of gcry_pk_decrypt depends on whether a flags lists occurs in its input data. Because we passed the output of gcry_pk_encrypt directly to gcry_pk_decrypt, such a flag value won't be there as of today. To be prepared for future changes we take care of it anyway. */ tmplist = sexp_find_token (decr, "value", 0); if (tmplist) decr_plaintext = sexp_nth_string (tmplist, 1); else decr_plaintext = sexp_nth_string (decr, 0); if (!decr_plaintext) { errtxt = "decrypt returned no plaintext"; goto leave; } /* Check that the decrypted plaintext matches the original plaintext. */ if (strcmp (plaintext, decr_plaintext)) { errtxt = "mismatch"; goto leave; } leave: sexp_release (tmplist); xfree (decr_plaintext); sexp_release (decr); _gcry_mpi_release (ciphertext); _gcry_mpi_release (ref_mpi); sexp_release (encr); sexp_release (plain); return errtxt; } static gpg_err_code_t selftests_rsa (selftest_report_func_t report) { const char *what; const char *errtxt; gcry_error_t err; gcry_sexp_t skey = NULL; gcry_sexp_t pkey = NULL; /* Convert the S-expressions into the internal representation. */ what = "convert"; err = sexp_sscan (&skey, NULL, sample_secret_key, strlen (sample_secret_key)); if (!err) err = sexp_sscan (&pkey, NULL, sample_public_key, strlen (sample_public_key)); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "key consistency"; err = _gcry_pk_testkey (skey); if (err) { errtxt = _gcry_strerror (err); goto failed; } what = "sign"; errtxt = selftest_sign_2048 (pkey, skey); if (errtxt) goto failed; what = "encrypt"; errtxt = selftest_encr_2048 (pkey, skey); if (errtxt) goto failed; sexp_release (pkey); sexp_release (skey); return 0; /* Succeeded. */ failed: sexp_release (pkey); sexp_release (skey); if (report) report ("pubkey", GCRY_PK_RSA, what, errtxt); return GPG_ERR_SELFTEST_FAILED; } /* Run a full self-test for ALGO and return 0 on success. */ static gpg_err_code_t run_selftests (int algo, int extended, selftest_report_func_t report) { gpg_err_code_t ec; (void)extended; switch (algo) { case GCRY_PK_RSA: ec = selftests_rsa (report); break; default: ec = GPG_ERR_PUBKEY_ALGO; break; } return ec; } gcry_pk_spec_t _gcry_pubkey_spec_rsa = { GCRY_PK_RSA, { 0, 1 }, (GCRY_PK_USAGE_SIGN | GCRY_PK_USAGE_ENCR), "RSA", rsa_names, "ne", "nedpqu", "a", "s", "n", rsa_generate, rsa_check_secret_key, rsa_encrypt, rsa_decrypt, rsa_sign, rsa_verify, rsa_get_nbits, run_selftests, compute_keygrip }; diff --git a/mpi/ec.c b/mpi/ec.c index 26dd9478..3ac0547f 100644 --- a/mpi/ec.c +++ b/mpi/ec.c @@ -1,1555 +1,1560 @@ /* ec.c - Elliptic Curve functions * Copyright (C) 2007 Free Software Foundation, Inc. * Copyright (C) 2013 g10 Code GmbH * * This file is part of Libgcrypt. * * Libgcrypt is free software; you can redistribute it and/or modify * it under the terms of the GNU Lesser General Public License as * published by the Free Software Foundation; either version 2.1 of * the License, or (at your option) any later version. * * Libgcrypt is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU Lesser General Public License for more details. * * You should have received a copy of the GNU Lesser General Public * License along with this program; if not, see . */ #include #include #include #include #include "mpi-internal.h" #include "longlong.h" #include "g10lib.h" #include "context.h" #include "ec-context.h" #include "ec-internal.h" #define point_init(a) _gcry_mpi_point_init ((a)) #define point_free(a) _gcry_mpi_point_free_parts ((a)) /* Print a point using the log fucntions. If CTX is not NULL affine coordinates will be printed. */ void _gcry_mpi_point_log (const char *name, mpi_point_t point, mpi_ec_t ctx) { gcry_mpi_t x, y; char buf[100]; if (!point) { snprintf (buf, sizeof buf - 1, "%s.*", name); log_mpidump (buf, NULL); return; } snprintf (buf, sizeof buf - 1, "%s.X", name); if (ctx) { x = mpi_new (0); y = mpi_new (0); } if (!ctx || _gcry_mpi_ec_get_affine (x, y, point, ctx)) { log_mpidump (buf, point->x); buf[strlen(buf)-1] = 'Y'; log_mpidump (buf, point->y); buf[strlen(buf)-1] = 'Z'; log_mpidump (buf, point->z); } else { buf[strlen(buf)-1] = 'x'; log_mpidump (buf, x); buf[strlen(buf)-1] = 'y'; log_mpidump (buf, y); } if (ctx) { _gcry_mpi_release (x); _gcry_mpi_release (y); } } /* Create a new point option. NBITS gives the size in bits of one coordinate; it is only used to pre-allocate some resources and might also be passed as 0 to use a default value. */ mpi_point_t _gcry_mpi_point_new (unsigned int nbits) { mpi_point_t p; (void)nbits; /* Currently not used. */ p = xmalloc (sizeof *p); _gcry_mpi_point_init (p); return p; } /* Release the point object P. P may be NULL. */ void _gcry_mpi_point_release (mpi_point_t p) { if (p) { _gcry_mpi_point_free_parts (p); xfree (p); } } /* Initialize the fields of a point object. gcry_mpi_point_free_parts may be used to release the fields. */ void _gcry_mpi_point_init (mpi_point_t p) { p->x = mpi_new (0); p->y = mpi_new (0); p->z = mpi_new (0); } /* Release the parts of a point object. */ void _gcry_mpi_point_free_parts (mpi_point_t p) { mpi_free (p->x); p->x = NULL; mpi_free (p->y); p->y = NULL; mpi_free (p->z); p->z = NULL; } /* Set the value from S into D. */ static void point_set (mpi_point_t d, mpi_point_t s) { mpi_set (d->x, s->x); mpi_set (d->y, s->y); mpi_set (d->z, s->z); } static void point_resize (mpi_point_t p, mpi_ec_t ctx) { /* * For now, we allocate enough limbs for our EC computation of ec_*. * Once we will improve ec_* to be constant size (and constant * time), NLIMBS can be ctx->p->nlimbs. */ size_t nlimbs = 2*ctx->p->nlimbs+1; mpi_resize (p->x, nlimbs); if (ctx->model != MPI_EC_MONTGOMERY) mpi_resize (p->y, nlimbs); mpi_resize (p->z, nlimbs); } static void point_swap_cond (mpi_point_t d, mpi_point_t s, unsigned long swap, mpi_ec_t ctx) { mpi_swap_cond (d->x, s->x, swap); if (ctx->model != MPI_EC_MONTGOMERY) mpi_swap_cond (d->y, s->y, swap); mpi_swap_cond (d->z, s->z, swap); } /* Set the projective coordinates from POINT into X, Y, and Z. If a coordinate is not required, X, Y, or Z may be passed as NULL. */ void _gcry_mpi_point_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z, mpi_point_t point) { if (x) mpi_set (x, point->x); if (y) mpi_set (y, point->y); if (z) mpi_set (z, point->z); } /* Set the projective coordinates from POINT into X, Y, and Z and release POINT. If a coordinate is not required, X, Y, or Z may be passed as NULL. */ void _gcry_mpi_point_snatch_get (gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z, mpi_point_t point) { mpi_snatch (x, point->x); mpi_snatch (y, point->y); mpi_snatch (z, point->z); xfree (point); } /* Set the projective coordinates from X, Y, and Z into POINT. If a coordinate is given as NULL, the value 0 is stored into point. If POINT is given as NULL a new point object is allocated. Returns POINT or the newly allocated point object. */ mpi_point_t _gcry_mpi_point_set (mpi_point_t point, gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z) { if (!point) point = mpi_point_new (0); if (x) mpi_set (point->x, x); else mpi_clear (point->x); if (y) mpi_set (point->y, y); else mpi_clear (point->y); if (z) mpi_set (point->z, z); else mpi_clear (point->z); return point; } /* Set the projective coordinates from X, Y, and Z into POINT. If a coordinate is given as NULL, the value 0 is stored into point. If POINT is given as NULL a new point object is allocated. The coordinates X, Y, and Z are released. Returns POINT or the newly allocated point object. */ mpi_point_t _gcry_mpi_point_snatch_set (mpi_point_t point, gcry_mpi_t x, gcry_mpi_t y, gcry_mpi_t z) { if (!point) point = mpi_point_new (0); if (x) mpi_snatch (point->x, x); else mpi_clear (point->x); if (y) mpi_snatch (point->y, y); else mpi_clear (point->y); if (z) mpi_snatch (point->z, z); else mpi_clear (point->z); return point; } /* W = W mod P. */ static void ec_mod (gcry_mpi_t w, mpi_ec_t ec) { if (0 && ec->dialect == ECC_DIALECT_ED25519) _gcry_mpi_ec_ed25519_mod (w); else if (ec->t.p_barrett) _gcry_mpi_mod_barrett (w, w, ec->t.p_barrett); else _gcry_mpi_mod (w, w, ec->p); } static void ec_addm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) { mpi_add (w, u, v); ec_mod (w, ctx); } static void ec_subm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ec) { mpi_sub (w, u, v); while (w->sign) mpi_add (w, w, ec->p); /*ec_mod (w, ec);*/ } static void ec_mulm (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) { mpi_mul (w, u, v); ec_mod (w, ctx); } /* W = 2 * U mod P. */ static void ec_mul2 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx) { mpi_lshift (w, u, 1); ec_mod (w, ctx); } static void ec_powm (gcry_mpi_t w, const gcry_mpi_t b, const gcry_mpi_t e, mpi_ec_t ctx) { mpi_powm (w, b, e, ctx->p); /* _gcry_mpi_abs (w); */ } /* Shortcut for ec_powm (B, B, mpi_const (MPI_C_TWO), ctx); for easier optimization. */ static void ec_pow2 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx) { /* Using mpi_mul is slightly faster (at least on amd64). */ /* mpi_powm (w, b, mpi_const (MPI_C_TWO), ctx->p); */ ec_mulm (w, b, b, ctx); } /* Shortcut for ec_powm (B, B, mpi_const (MPI_C_THREE), ctx); for easier optimization. */ static void ec_pow3 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx) { mpi_powm (w, b, mpi_const (MPI_C_THREE), ctx->p); } static void ec_invm (gcry_mpi_t x, gcry_mpi_t a, mpi_ec_t ctx) { if (!mpi_invm (x, a, ctx->p)) { log_error ("ec_invm: inverse does not exist:\n"); log_mpidump (" a", a); log_mpidump (" p", ctx->p); } } /* Force recomputation of all helper variables. */ void _gcry_mpi_ec_get_reset (mpi_ec_t ec) { ec->t.valid.a_is_pminus3 = 0; ec->t.valid.two_inv_p = 0; } /* Accessor for helper variable. */ static int ec_get_a_is_pminus3 (mpi_ec_t ec) { gcry_mpi_t tmp; if (!ec->t.valid.a_is_pminus3) { ec->t.valid.a_is_pminus3 = 1; tmp = mpi_alloc_like (ec->p); mpi_sub_ui (tmp, ec->p, 3); ec->t.a_is_pminus3 = !mpi_cmp (ec->a, tmp); mpi_free (tmp); } return ec->t.a_is_pminus3; } /* Accessor for helper variable. */ static gcry_mpi_t ec_get_two_inv_p (mpi_ec_t ec) { if (!ec->t.valid.two_inv_p) { ec->t.valid.two_inv_p = 1; if (!ec->t.two_inv_p) ec->t.two_inv_p = mpi_alloc (0); ec_invm (ec->t.two_inv_p, mpi_const (MPI_C_TWO), ec); } return ec->t.two_inv_p; } /* This function initialized a context for elliptic curve based on the field GF(p). P is the prime specifying this field, A is the first coefficient. CTX is expected to be zeroized. */ static void ec_p_init (mpi_ec_t ctx, enum gcry_mpi_ec_models model, enum ecc_dialects dialect, int flags, gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b) { int i; static int use_barrett; if (!use_barrett) { if (getenv ("GCRYPT_BARRETT")) use_barrett = 1; else use_barrett = -1; } /* Fixme: Do we want to check some constraints? e.g. a < p */ ctx->model = model; ctx->dialect = dialect; ctx->flags = flags; if (dialect == ECC_DIALECT_ED25519) ctx->nbits = 256; else ctx->nbits = mpi_get_nbits (p); ctx->p = mpi_copy (p); ctx->a = mpi_copy (a); ctx->b = mpi_copy (b); ctx->t.p_barrett = use_barrett > 0? _gcry_mpi_barrett_init (ctx->p, 0):NULL; _gcry_mpi_ec_get_reset (ctx); /* Allocate scratch variables. */ for (i=0; i< DIM(ctx->t.scratch); i++) ctx->t.scratch[i] = mpi_alloc_like (ctx->p); /* Prepare for fast reduction. */ /* FIXME: need a test for NIST values. However it does not gain us any real advantage, for 384 bits it is actually slower than using mpi_mulm. */ /* ctx->nist_nbits = mpi_get_nbits (ctx->p); */ /* if (ctx->nist_nbits == 192) */ /* { */ /* for (i=0; i < 4; i++) */ /* ctx->s[i] = mpi_new (192); */ /* ctx->c = mpi_new (192*2); */ /* } */ /* else if (ctx->nist_nbits == 384) */ /* { */ /* for (i=0; i < 10; i++) */ /* ctx->s[i] = mpi_new (384); */ /* ctx->c = mpi_new (384*2); */ /* } */ } static void ec_deinit (void *opaque) { mpi_ec_t ctx = opaque; int i; _gcry_mpi_barrett_free (ctx->t.p_barrett); /* Domain parameter. */ mpi_free (ctx->p); mpi_free (ctx->a); mpi_free (ctx->b); _gcry_mpi_point_release (ctx->G); mpi_free (ctx->n); mpi_free (ctx->h); /* The key. */ _gcry_mpi_point_release (ctx->Q); mpi_free (ctx->d); /* Private data of ec.c. */ mpi_free (ctx->t.two_inv_p); for (i=0; i< DIM(ctx->t.scratch); i++) mpi_free (ctx->t.scratch[i]); /* if (ctx->nist_nbits == 192) */ /* { */ /* for (i=0; i < 4; i++) */ /* mpi_free (ctx->s[i]); */ /* mpi_free (ctx->c); */ /* } */ /* else if (ctx->nist_nbits == 384) */ /* { */ /* for (i=0; i < 10; i++) */ /* mpi_free (ctx->s[i]); */ /* mpi_free (ctx->c); */ /* } */ } /* This function returns a new context for elliptic curve based on the field GF(p). P is the prime specifying this field, A is the first coefficient, B is the second coefficient, and MODEL is the model for the curve. This function is only used within Libgcrypt and not part of the public API. This context needs to be released using _gcry_mpi_ec_free. */ mpi_ec_t _gcry_mpi_ec_p_internal_new (enum gcry_mpi_ec_models model, enum ecc_dialects dialect, int flags, gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b) { mpi_ec_t ctx; ctx = xcalloc (1, sizeof *ctx); ec_p_init (ctx, model, dialect, flags, p, a, b); return ctx; } /* This is a variant of _gcry_mpi_ec_p_internal_new which returns an public context and does some error checking on the supplied arguments. On success the new context is stored at R_CTX and 0 is returned; on error NULL is stored at R_CTX and an error code is returned. The context needs to be released using gcry_ctx_release. */ gpg_err_code_t _gcry_mpi_ec_p_new (gcry_ctx_t *r_ctx, enum gcry_mpi_ec_models model, enum ecc_dialects dialect, int flags, gcry_mpi_t p, gcry_mpi_t a, gcry_mpi_t b) { gcry_ctx_t ctx; mpi_ec_t ec; *r_ctx = NULL; if (!p || !a) return GPG_ERR_EINVAL; ctx = _gcry_ctx_alloc (CONTEXT_TYPE_EC, sizeof *ec, ec_deinit); if (!ctx) return gpg_err_code_from_syserror (); ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); ec_p_init (ec, model, dialect, flags, p, a, b); *r_ctx = ctx; return 0; } void _gcry_mpi_ec_free (mpi_ec_t ctx) { if (ctx) { ec_deinit (ctx); xfree (ctx); } } gcry_mpi_t _gcry_mpi_ec_get_mpi (const char *name, gcry_ctx_t ctx, int copy) { mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); return _gcry_ecc_get_mpi (name, ec, copy); } gcry_mpi_point_t _gcry_mpi_ec_get_point (const char *name, gcry_ctx_t ctx, int copy) { mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); (void)copy; /* Not used. */ return _gcry_ecc_get_point (name, ec); } gpg_err_code_t _gcry_mpi_ec_set_mpi (const char *name, gcry_mpi_t newvalue, gcry_ctx_t ctx) { mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); return _gcry_ecc_set_mpi (name, newvalue, ec); } gpg_err_code_t _gcry_mpi_ec_set_point (const char *name, gcry_mpi_point_t newvalue, gcry_ctx_t ctx) { mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); return _gcry_ecc_set_point (name, newvalue, ec); } /* Given an encoded point in the MPI VALUE and a context EC, decode * the point according to the context and store it in RESULT. On * error an error code is return but RESULT might have been changed. * If no context is given the function tries to decode VALUE by * assuming a 0x04 prefixed uncompressed encoding. */ gpg_err_code_t _gcry_mpi_ec_decode_point (mpi_point_t result, gcry_mpi_t value, mpi_ec_t ec) { gcry_err_code_t rc; if (ec && ec->dialect == ECC_DIALECT_ED25519) rc = _gcry_ecc_eddsa_decodepoint (value, ec, result, NULL, NULL); else if (ec && ec->model == MPI_EC_MONTGOMERY) rc = _gcry_ecc_mont_decodepoint (value, ec, result); else rc = _gcry_ecc_os2ec (result, value); return rc; } /* Compute the affine coordinates from the projective coordinates in POINT. Set them into X and Y. If one coordinate is not required, X or Y may be passed as NULL. CTX is the usual context. Returns: 0 on success or !0 if POINT is at infinity. */ int _gcry_mpi_ec_get_affine (gcry_mpi_t x, gcry_mpi_t y, mpi_point_t point, mpi_ec_t ctx) { if (!mpi_cmp_ui (point->z, 0)) return -1; switch (ctx->model) { case MPI_EC_WEIERSTRASS: /* Using Jacobian coordinates. */ { gcry_mpi_t z1, z2, z3; z1 = mpi_new (0); z2 = mpi_new (0); ec_invm (z1, point->z, ctx); /* z1 = z^(-1) mod p */ ec_mulm (z2, z1, z1, ctx); /* z2 = z^(-2) mod p */ if (x) ec_mulm (x, point->x, z2, ctx); if (y) { z3 = mpi_new (0); ec_mulm (z3, z2, z1, ctx); /* z3 = z^(-3) mod p */ ec_mulm (y, point->y, z3, ctx); mpi_free (z3); } mpi_free (z2); mpi_free (z1); } return 0; case MPI_EC_MONTGOMERY: { if (x) mpi_set (x, point->x); if (y) { log_fatal ("%s: Getting Y-coordinate on %s is not supported\n", "_gcry_mpi_ec_get_affine", "Montgomery"); return -1; } } return 0; case MPI_EC_EDWARDS: { gcry_mpi_t z; z = mpi_new (0); ec_invm (z, point->z, ctx); if (x) ec_mulm (x, point->x, z, ctx); if (y) ec_mulm (y, point->y, z, ctx); _gcry_mpi_release (z); } return 0; default: return -1; } } /* RESULT = 2 * POINT (Weierstrass version). */ static void dup_point_weierstrass (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx) { #define x3 (result->x) #define y3 (result->y) #define z3 (result->z) #define t1 (ctx->t.scratch[0]) #define t2 (ctx->t.scratch[1]) #define t3 (ctx->t.scratch[2]) #define l1 (ctx->t.scratch[3]) #define l2 (ctx->t.scratch[4]) #define l3 (ctx->t.scratch[5]) if (!mpi_cmp_ui (point->y, 0) || !mpi_cmp_ui (point->z, 0)) { /* P_y == 0 || P_z == 0 => [1:1:0] */ mpi_set_ui (x3, 1); mpi_set_ui (y3, 1); mpi_set_ui (z3, 0); } else { if (ec_get_a_is_pminus3 (ctx)) /* Use the faster case. */ { /* L1 = 3(X - Z^2)(X + Z^2) */ /* T1: used for Z^2. */ /* T2: used for the right term. */ ec_pow2 (t1, point->z, ctx); ec_subm (l1, point->x, t1, ctx); ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx); ec_addm (t2, point->x, t1, ctx); ec_mulm (l1, l1, t2, ctx); } else /* Standard case. */ { /* L1 = 3X^2 + aZ^4 */ /* T1: used for aZ^4. */ ec_pow2 (l1, point->x, ctx); ec_mulm (l1, l1, mpi_const (MPI_C_THREE), ctx); ec_powm (t1, point->z, mpi_const (MPI_C_FOUR), ctx); ec_mulm (t1, t1, ctx->a, ctx); ec_addm (l1, l1, t1, ctx); } /* Z3 = 2YZ */ ec_mulm (z3, point->y, point->z, ctx); ec_mul2 (z3, z3, ctx); /* L2 = 4XY^2 */ /* T2: used for Y2; required later. */ ec_pow2 (t2, point->y, ctx); ec_mulm (l2, t2, point->x, ctx); ec_mulm (l2, l2, mpi_const (MPI_C_FOUR), ctx); /* X3 = L1^2 - 2L2 */ /* T1: used for L2^2. */ ec_pow2 (x3, l1, ctx); ec_mul2 (t1, l2, ctx); ec_subm (x3, x3, t1, ctx); /* L3 = 8Y^4 */ /* T2: taken from above. */ ec_pow2 (t2, t2, ctx); ec_mulm (l3, t2, mpi_const (MPI_C_EIGHT), ctx); /* Y3 = L1(L2 - X3) - L3 */ ec_subm (y3, l2, x3, ctx); ec_mulm (y3, y3, l1, ctx); ec_subm (y3, y3, l3, ctx); } #undef x3 #undef y3 #undef z3 #undef t1 #undef t2 #undef t3 #undef l1 #undef l2 #undef l3 } /* RESULT = 2 * POINT (Montgomery version). */ static void dup_point_montgomery (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx) { (void)result; (void)point; (void)ctx; log_fatal ("%s: %s not yet supported\n", "_gcry_mpi_ec_dup_point", "Montgomery"); } /* RESULT = 2 * POINT (Twisted Edwards version). */ static void dup_point_edwards (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx) { #define X1 (point->x) #define Y1 (point->y) #define Z1 (point->z) #define X3 (result->x) #define Y3 (result->y) #define Z3 (result->z) #define B (ctx->t.scratch[0]) #define C (ctx->t.scratch[1]) #define D (ctx->t.scratch[2]) #define E (ctx->t.scratch[3]) #define F (ctx->t.scratch[4]) #define H (ctx->t.scratch[5]) #define J (ctx->t.scratch[6]) /* Compute: (X_3 : Y_3 : Z_3) = 2( X_1 : Y_1 : Z_1 ) */ /* B = (X_1 + Y_1)^2 */ ec_addm (B, X1, Y1, ctx); ec_pow2 (B, B, ctx); /* C = X_1^2 */ /* D = Y_1^2 */ ec_pow2 (C, X1, ctx); ec_pow2 (D, Y1, ctx); /* E = aC */ if (ctx->dialect == ECC_DIALECT_ED25519) mpi_sub (E, ctx->p, C); else ec_mulm (E, ctx->a, C, ctx); /* F = E + D */ ec_addm (F, E, D, ctx); /* H = Z_1^2 */ ec_pow2 (H, Z1, ctx); /* J = F - 2H */ ec_mul2 (J, H, ctx); ec_subm (J, F, J, ctx); /* X_3 = (B - C - D) · J */ ec_subm (X3, B, C, ctx); ec_subm (X3, X3, D, ctx); ec_mulm (X3, X3, J, ctx); /* Y_3 = F · (E - D) */ ec_subm (Y3, E, D, ctx); ec_mulm (Y3, Y3, F, ctx); /* Z_3 = F · J */ ec_mulm (Z3, F, J, ctx); #undef X1 #undef Y1 #undef Z1 #undef X3 #undef Y3 #undef Z3 #undef B #undef C #undef D #undef E #undef F #undef H #undef J } /* RESULT = 2 * POINT */ void _gcry_mpi_ec_dup_point (mpi_point_t result, mpi_point_t point, mpi_ec_t ctx) { switch (ctx->model) { case MPI_EC_WEIERSTRASS: dup_point_weierstrass (result, point, ctx); break; case MPI_EC_MONTGOMERY: dup_point_montgomery (result, point, ctx); break; case MPI_EC_EDWARDS: dup_point_edwards (result, point, ctx); break; } } /* RESULT = P1 + P2 (Weierstrass version).*/ static void add_points_weierstrass (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { #define x1 (p1->x ) #define y1 (p1->y ) #define z1 (p1->z ) #define x2 (p2->x ) #define y2 (p2->y ) #define z2 (p2->z ) #define x3 (result->x) #define y3 (result->y) #define z3 (result->z) #define l1 (ctx->t.scratch[0]) #define l2 (ctx->t.scratch[1]) #define l3 (ctx->t.scratch[2]) #define l4 (ctx->t.scratch[3]) #define l5 (ctx->t.scratch[4]) #define l6 (ctx->t.scratch[5]) #define l7 (ctx->t.scratch[6]) #define l8 (ctx->t.scratch[7]) #define l9 (ctx->t.scratch[8]) #define t1 (ctx->t.scratch[9]) #define t2 (ctx->t.scratch[10]) if ( (!mpi_cmp (x1, x2)) && (!mpi_cmp (y1, y2)) && (!mpi_cmp (z1, z2)) ) { /* Same point; need to call the duplicate function. */ _gcry_mpi_ec_dup_point (result, p1, ctx); } else if (!mpi_cmp_ui (z1, 0)) { /* P1 is at infinity. */ mpi_set (x3, p2->x); mpi_set (y3, p2->y); mpi_set (z3, p2->z); } else if (!mpi_cmp_ui (z2, 0)) { /* P2 is at infinity. */ mpi_set (x3, p1->x); mpi_set (y3, p1->y); mpi_set (z3, p1->z); } else { int z1_is_one = !mpi_cmp_ui (z1, 1); int z2_is_one = !mpi_cmp_ui (z2, 1); /* l1 = x1 z2^2 */ /* l2 = x2 z1^2 */ if (z2_is_one) mpi_set (l1, x1); else { ec_pow2 (l1, z2, ctx); ec_mulm (l1, l1, x1, ctx); } if (z1_is_one) mpi_set (l2, x2); else { ec_pow2 (l2, z1, ctx); ec_mulm (l2, l2, x2, ctx); } /* l3 = l1 - l2 */ ec_subm (l3, l1, l2, ctx); /* l4 = y1 z2^3 */ ec_powm (l4, z2, mpi_const (MPI_C_THREE), ctx); ec_mulm (l4, l4, y1, ctx); /* l5 = y2 z1^3 */ ec_powm (l5, z1, mpi_const (MPI_C_THREE), ctx); ec_mulm (l5, l5, y2, ctx); /* l6 = l4 - l5 */ ec_subm (l6, l4, l5, ctx); if (!mpi_cmp_ui (l3, 0)) { if (!mpi_cmp_ui (l6, 0)) { /* P1 and P2 are the same - use duplicate function. */ _gcry_mpi_ec_dup_point (result, p1, ctx); } else { /* P1 is the inverse of P2. */ mpi_set_ui (x3, 1); mpi_set_ui (y3, 1); mpi_set_ui (z3, 0); } } else { /* l7 = l1 + l2 */ ec_addm (l7, l1, l2, ctx); /* l8 = l4 + l5 */ ec_addm (l8, l4, l5, ctx); /* z3 = z1 z2 l3 */ ec_mulm (z3, z1, z2, ctx); ec_mulm (z3, z3, l3, ctx); /* x3 = l6^2 - l7 l3^2 */ ec_pow2 (t1, l6, ctx); ec_pow2 (t2, l3, ctx); ec_mulm (t2, t2, l7, ctx); ec_subm (x3, t1, t2, ctx); /* l9 = l7 l3^2 - 2 x3 */ ec_mul2 (t1, x3, ctx); ec_subm (l9, t2, t1, ctx); /* y3 = (l9 l6 - l8 l3^3)/2 */ ec_mulm (l9, l9, l6, ctx); ec_powm (t1, l3, mpi_const (MPI_C_THREE), ctx); /* fixme: Use saved value*/ ec_mulm (t1, t1, l8, ctx); ec_subm (y3, l9, t1, ctx); ec_mulm (y3, y3, ec_get_two_inv_p (ctx), ctx); } } #undef x1 #undef y1 #undef z1 #undef x2 #undef y2 #undef z2 #undef x3 #undef y3 #undef z3 #undef l1 #undef l2 #undef l3 #undef l4 #undef l5 #undef l6 #undef l7 #undef l8 #undef l9 #undef t1 #undef t2 } /* RESULT = P1 + P2 (Montgomery version).*/ static void add_points_montgomery (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { (void)result; (void)p1; (void)p2; (void)ctx; log_fatal ("%s: %s not yet supported\n", "_gcry_mpi_ec_add_points", "Montgomery"); } /* RESULT = P1 + P2 (Twisted Edwards version).*/ static void add_points_edwards (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { #define X1 (p1->x) #define Y1 (p1->y) #define Z1 (p1->z) #define X2 (p2->x) #define Y2 (p2->y) #define Z2 (p2->z) #define X3 (result->x) #define Y3 (result->y) #define Z3 (result->z) #define A (ctx->t.scratch[0]) #define B (ctx->t.scratch[1]) #define C (ctx->t.scratch[2]) #define D (ctx->t.scratch[3]) #define E (ctx->t.scratch[4]) #define F (ctx->t.scratch[5]) #define G (ctx->t.scratch[6]) #define tmp (ctx->t.scratch[7]) /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ /* A = Z1 · Z2 */ ec_mulm (A, Z1, Z2, ctx); /* B = A^2 */ ec_pow2 (B, A, ctx); /* C = X1 · X2 */ ec_mulm (C, X1, X2, ctx); /* D = Y1 · Y2 */ ec_mulm (D, Y1, Y2, ctx); /* E = d · C · D */ ec_mulm (E, ctx->b, C, ctx); ec_mulm (E, E, D, ctx); /* F = B - E */ ec_subm (F, B, E, ctx); /* G = B + E */ ec_addm (G, B, E, ctx); /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ ec_addm (tmp, X1, Y1, ctx); ec_addm (X3, X2, Y2, ctx); ec_mulm (X3, X3, tmp, ctx); ec_subm (X3, X3, C, ctx); ec_subm (X3, X3, D, ctx); ec_mulm (X3, X3, F, ctx); ec_mulm (X3, X3, A, ctx); /* Y_3 = A · G · (D - aC) */ if (ctx->dialect == ECC_DIALECT_ED25519) { ec_addm (Y3, D, C, ctx); } else { ec_mulm (Y3, ctx->a, C, ctx); ec_subm (Y3, D, Y3, ctx); } ec_mulm (Y3, Y3, G, ctx); ec_mulm (Y3, Y3, A, ctx); /* Z_3 = F · G */ ec_mulm (Z3, F, G, ctx); #undef X1 #undef Y1 #undef Z1 #undef X2 #undef Y2 #undef Z2 #undef X3 #undef Y3 #undef Z3 #undef A #undef B #undef C #undef D #undef E #undef F #undef G #undef tmp } /* Compute a step of Montgomery Ladder (only use X and Z in the point). Inputs: P1, P2, and x-coordinate of DIF = P1 - P1. Outputs: PRD = 2 * P1 and SUM = P1 + P2. */ static void montgomery_ladder (mpi_point_t prd, mpi_point_t sum, mpi_point_t p1, mpi_point_t p2, gcry_mpi_t dif_x, mpi_ec_t ctx) { ec_addm (sum->x, p2->x, p2->z, ctx); ec_subm (p2->z, p2->x, p2->z, ctx); ec_addm (prd->x, p1->x, p1->z, ctx); ec_subm (p1->z, p1->x, p1->z, ctx); ec_mulm (p2->x, p1->z, sum->x, ctx); ec_mulm (p2->z, prd->x, p2->z, ctx); ec_pow2 (p1->x, prd->x, ctx); ec_pow2 (p1->z, p1->z, ctx); ec_addm (sum->x, p2->x, p2->z, ctx); ec_subm (p2->z, p2->x, p2->z, ctx); ec_mulm (prd->x, p1->x, p1->z, ctx); ec_subm (p1->z, p1->x, p1->z, ctx); ec_pow2 (sum->x, sum->x, ctx); ec_pow2 (sum->z, p2->z, ctx); ec_mulm (prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ ec_mulm (sum->z, sum->z, dif_x, ctx); ec_addm (prd->z, p1->x, prd->z, ctx); ec_mulm (prd->z, prd->z, p1->z, ctx); } /* RESULT = P1 + P2 */ void _gcry_mpi_ec_add_points (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { switch (ctx->model) { case MPI_EC_WEIERSTRASS: add_points_weierstrass (result, p1, p2, ctx); break; case MPI_EC_MONTGOMERY: add_points_montgomery (result, p1, p2, ctx); break; case MPI_EC_EDWARDS: add_points_edwards (result, p1, p2, ctx); break; } } /* RESULT = P1 - P2 (Weierstrass version).*/ static void sub_points_weierstrass (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { (void)result; (void)p1; (void)p2; (void)ctx; log_fatal ("%s: %s not yet supported\n", "_gcry_mpi_ec_sub_points", "Weierstrass"); } /* RESULT = P1 - P2 (Montgomery version).*/ static void sub_points_montgomery (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { (void)result; (void)p1; (void)p2; (void)ctx; log_fatal ("%s: %s not yet supported\n", "_gcry_mpi_ec_sub_points", "Montgomery"); } /* RESULT = P1 - P2 (Twisted Edwards version).*/ static void sub_points_edwards (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { mpi_point_t p2i = _gcry_mpi_point_new (0); point_set (p2i, p2); mpi_sub (p2i->x, ctx->p, p2i->x); add_points_edwards (result, p1, p2i, ctx); _gcry_mpi_point_release (p2i); } /* RESULT = P1 - P2 */ void _gcry_mpi_ec_sub_points (mpi_point_t result, mpi_point_t p1, mpi_point_t p2, mpi_ec_t ctx) { switch (ctx->model) { case MPI_EC_WEIERSTRASS: sub_points_weierstrass (result, p1, p2, ctx); break; case MPI_EC_MONTGOMERY: sub_points_montgomery (result, p1, p2, ctx); break; case MPI_EC_EDWARDS: sub_points_edwards (result, p1, p2, ctx); break; } } /* Scalar point multiplication - the main function for ECC. If takes an integer SCALAR and a POINT as well as the usual context CTX. RESULT will be set to the resulting point. */ void _gcry_mpi_ec_mul_point (mpi_point_t result, gcry_mpi_t scalar, mpi_point_t point, mpi_ec_t ctx) { gcry_mpi_t x1, y1, z1, k, h, yy; unsigned int i, loops; mpi_point_struct p1, p2, p1inv; if (ctx->model == MPI_EC_EDWARDS || (ctx->model == MPI_EC_WEIERSTRASS && mpi_is_secure (scalar))) { - /* Simple left to right binary method. GECC Algorithm 3.27 */ + /* Simple left to right binary method. Algorithm 3.27 from + * {author={Hankerson, Darrel and Menezes, Alfred J. and Vanstone, Scott}, + * title = {Guide to Elliptic Curve Cryptography}, + * year = {2003}, isbn = {038795273X}, + * url = {http://www.cacr.math.uwaterloo.ca/ecc/}, + * publisher = {Springer-Verlag New York, Inc.}} */ unsigned int nbits; int j; nbits = mpi_get_nbits (scalar); if (ctx->model == MPI_EC_WEIERSTRASS) { mpi_set_ui (result->x, 1); mpi_set_ui (result->y, 1); mpi_set_ui (result->z, 0); } else { mpi_set_ui (result->x, 0); mpi_set_ui (result->y, 1); mpi_set_ui (result->z, 1); } if (mpi_is_secure (scalar)) { /* If SCALAR is in secure memory we assume that it is the secret key we use constant time operation. */ mpi_point_struct tmppnt; point_init (&tmppnt); point_resize (result, ctx); point_resize (&tmppnt, ctx); for (j=nbits-1; j >= 0; j--) { _gcry_mpi_ec_dup_point (result, result, ctx); _gcry_mpi_ec_add_points (&tmppnt, result, point, ctx); point_swap_cond (result, &tmppnt, mpi_test_bit (scalar, j), ctx); } point_free (&tmppnt); } else { for (j=nbits-1; j >= 0; j--) { _gcry_mpi_ec_dup_point (result, result, ctx); if (mpi_test_bit (scalar, j)) _gcry_mpi_ec_add_points (result, result, point, ctx); } } return; } else if (ctx->model == MPI_EC_MONTGOMERY) { unsigned int nbits; int j; mpi_point_struct p1_, p2_; mpi_point_t q1, q2, prd, sum; unsigned long sw; /* Compute scalar point multiplication with Montgomery Ladder. Note that we don't use Y-coordinate in the points at all. RESULT->Y will be filled by zero. */ nbits = mpi_get_nbits (scalar); point_init (&p1); point_init (&p2); point_init (&p1_); point_init (&p2_); mpi_set_ui (p1.x, 1); mpi_free (p2.x); p2.x = mpi_copy (point->x); mpi_set_ui (p2.z, 1); point_resize (&p1, ctx); point_resize (&p2, ctx); point_resize (&p1_, ctx); point_resize (&p2_, ctx); q1 = &p1; q2 = &p2; prd = &p1_; sum = &p2_; for (j=nbits-1; j >= 0; j--) { mpi_point_t t; sw = mpi_test_bit (scalar, j); point_swap_cond (q1, q2, sw, ctx); montgomery_ladder (prd, sum, q1, q2, point->x, ctx); point_swap_cond (prd, sum, sw, ctx); t = q1; q1 = prd; prd = t; t = q2; q2 = sum; sum = t; } mpi_clear (result->y); sw = (nbits & 1); point_swap_cond (&p1, &p1_, sw, ctx); if (p1.z->nlimbs == 0) { mpi_set_ui (result->x, 1); mpi_set_ui (result->z, 0); } else { z1 = mpi_new (0); ec_invm (z1, p1.z, ctx); ec_mulm (result->x, p1.x, z1, ctx); mpi_set_ui (result->z, 1); mpi_free (z1); } point_free (&p1); point_free (&p2); point_free (&p1_); point_free (&p2_); return; } x1 = mpi_alloc_like (ctx->p); y1 = mpi_alloc_like (ctx->p); h = mpi_alloc_like (ctx->p); k = mpi_copy (scalar); yy = mpi_copy (point->y); if ( mpi_has_sign (k) ) { k->sign = 0; ec_invm (yy, yy, ctx); } if (!mpi_cmp_ui (point->z, 1)) { mpi_set (x1, point->x); mpi_set (y1, yy); } else { gcry_mpi_t z2, z3; z2 = mpi_alloc_like (ctx->p); z3 = mpi_alloc_like (ctx->p); ec_mulm (z2, point->z, point->z, ctx); ec_mulm (z3, point->z, z2, ctx); ec_invm (z2, z2, ctx); ec_mulm (x1, point->x, z2, ctx); ec_invm (z3, z3, ctx); ec_mulm (y1, yy, z3, ctx); mpi_free (z2); mpi_free (z3); } z1 = mpi_copy (mpi_const (MPI_C_ONE)); mpi_mul (h, k, mpi_const (MPI_C_THREE)); /* h = 3k */ loops = mpi_get_nbits (h); if (loops < 2) { /* If SCALAR is zero, the above mpi_mul sets H to zero and thus LOOPs will be zero. To avoid an underflow of I in the main loop we set LOOP to 2 and the result to (0,0,0). */ loops = 2; mpi_clear (result->x); mpi_clear (result->y); mpi_clear (result->z); } else { mpi_set (result->x, point->x); mpi_set (result->y, yy); mpi_set (result->z, point->z); } mpi_free (yy); yy = NULL; p1.x = x1; x1 = NULL; p1.y = y1; y1 = NULL; p1.z = z1; z1 = NULL; point_init (&p2); point_init (&p1inv); /* Invert point: y = p - y mod p */ point_set (&p1inv, &p1); ec_subm (p1inv.y, ctx->p, p1inv.y, ctx); for (i=loops-2; i > 0; i--) { _gcry_mpi_ec_dup_point (result, result, ctx); if (mpi_test_bit (h, i) == 1 && mpi_test_bit (k, i) == 0) { point_set (&p2, result); _gcry_mpi_ec_add_points (result, &p2, &p1, ctx); } if (mpi_test_bit (h, i) == 0 && mpi_test_bit (k, i) == 1) { point_set (&p2, result); _gcry_mpi_ec_add_points (result, &p2, &p1inv, ctx); } } point_free (&p1); point_free (&p2); point_free (&p1inv); mpi_free (h); mpi_free (k); } /* Return true if POINT is on the curve described by CTX. */ int _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx) { int res = 0; gcry_mpi_t x, y, w; x = mpi_new (0); y = mpi_new (0); w = mpi_new (0); switch (ctx->model) { case MPI_EC_WEIERSTRASS: { gcry_mpi_t xxx; if (_gcry_mpi_ec_get_affine (x, y, point, ctx)) goto leave; xxx = mpi_new (0); /* y^2 == x^3 + a·x + b */ ec_pow2 (y, y, ctx); ec_pow3 (xxx, x, ctx); ec_mulm (w, ctx->a, x, ctx); ec_addm (w, w, ctx->b, ctx); ec_addm (w, w, xxx, ctx); if (!mpi_cmp (y, w)) res = 1; _gcry_mpi_release (xxx); } break; case MPI_EC_MONTGOMERY: { #define xx y /* With Montgomery curve, only X-coordinate is valid. */ if (_gcry_mpi_ec_get_affine (x, NULL, point, ctx)) goto leave; /* The equation is: b * y^2 == x^3 + a · x^2 + x */ /* We check if right hand is quadratic residue or not by Euler's criterion. */ /* CTX->A has (a-2)/4 and CTX->B has b^-1 */ ec_mulm (w, ctx->a, mpi_const (MPI_C_FOUR), ctx); ec_addm (w, w, mpi_const (MPI_C_TWO), ctx); ec_mulm (w, w, x, ctx); ec_pow2 (xx, x, ctx); ec_addm (w, w, xx, ctx); ec_addm (w, w, mpi_const (MPI_C_ONE), ctx); ec_mulm (w, w, x, ctx); ec_mulm (w, w, ctx->b, ctx); #undef xx /* Compute Euler's criterion: w^(p-1)/2 */ #define p_minus1 y ec_subm (p_minus1, ctx->p, mpi_const (MPI_C_ONE), ctx); mpi_rshift (p_minus1, p_minus1, 1); ec_powm (w, w, p_minus1, ctx); res = !mpi_cmp_ui (w, 1); #undef p_minus1 } break; case MPI_EC_EDWARDS: { if (_gcry_mpi_ec_get_affine (x, y, point, ctx)) goto leave; /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ ec_pow2 (x, x, ctx); ec_pow2 (y, y, ctx); if (ctx->dialect == ECC_DIALECT_ED25519) mpi_sub (w, ctx->p, x); else ec_mulm (w, ctx->a, x, ctx); ec_addm (w, w, y, ctx); ec_subm (w, w, mpi_const (MPI_C_ONE), ctx); ec_mulm (x, x, y, ctx); ec_mulm (x, x, ctx->b, ctx); ec_subm (w, w, x, ctx); if (!mpi_cmp_ui (w, 0)) res = 1; } break; } leave: _gcry_mpi_release (w); _gcry_mpi_release (x); _gcry_mpi_release (y); return res; }