diff --git a/cipher/ecc-curves.c b/cipher/ecc-curves.c index 4a3139c3..aa8b0e7c 100644 --- a/cipher/ecc-curves.c +++ b/cipher/ecc-curves.c @@ -1,1379 +1,1395 @@ /* ecc-curves.c - Elliptic Curve parameter mangement * Copyright (C) 2007, 2008, 2010, 2011 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 #include "g10lib.h" #include "mpi.h" #include "mpi-internal.h" #include "cipher.h" #include "context.h" #include "ec-context.h" #include "pubkey-internal.h" #include "ecc-common.h" /* This tables defines aliases for curve names. */ static const struct { const char *name; /* Our name. */ const char *other; /* Other name. */ } curve_aliases[] = { { "Curve25519", "1.3.6.1.4.1.3029.1.5.1" }, /* OpenPGP */ { "Ed25519", "1.3.6.1.4.1.11591.15.1" }, /* OpenPGP */ #if 0 /* FIXME: We have a naming issue here. RFC-8032 says that its * Ed25519 is the pureEdDSA, that is w.o. the SHA512 prehasing we * use in OpenPGP. */ { "Ed25519", "1.3.101.112" }, /* rfc8410 */ { "Ed448", "1.3.101.113" }, /* rfc8410 */ { "X22519", "1.3.101.110" }, /* rfc8410 */ - - { "X448", "1.3.101.111" }, /* rfc8410 */ #endif + { "Curve448", "1.3.101.111" }, /* X448 in rfc8410 */ + { "NIST P-192", "1.2.840.10045.3.1.1" }, /* X9.62 OID */ { "NIST P-192", "prime192v1" }, /* X9.62 name. */ { "NIST P-192", "secp192r1" }, /* SECP name. */ { "NIST P-192", "nistp192" }, /* rfc5656. */ { "NIST P-224", "secp224r1" }, { "NIST P-224", "1.3.132.0.33" }, /* SECP OID. */ { "NIST P-224", "nistp224" }, /* rfc5656. */ { "NIST P-256", "1.2.840.10045.3.1.7" }, /* From NIST SP 800-78-1. */ { "NIST P-256", "prime256v1" }, { "NIST P-256", "secp256r1" }, { "NIST P-256", "nistp256" }, /* rfc5656. */ { "NIST P-384", "secp384r1" }, { "NIST P-384", "1.3.132.0.34" }, { "NIST P-384", "nistp384" }, /* rfc5656. */ { "NIST P-521", "secp521r1" }, { "NIST P-521", "1.3.132.0.35" }, { "NIST P-521", "nistp521" }, /* rfc5656. */ { "brainpoolP160r1", "1.3.36.3.3.2.8.1.1.1" }, { "brainpoolP192r1", "1.3.36.3.3.2.8.1.1.3" }, { "brainpoolP224r1", "1.3.36.3.3.2.8.1.1.5" }, { "brainpoolP256r1", "1.3.36.3.3.2.8.1.1.7" }, { "brainpoolP320r1", "1.3.36.3.3.2.8.1.1.9" }, { "brainpoolP384r1", "1.3.36.3.3.2.8.1.1.11"}, { "brainpoolP512r1", "1.3.36.3.3.2.8.1.1.13"}, { "GOST2001-test", "1.2.643.2.2.35.0" }, { "GOST2001-CryptoPro-A", "1.2.643.2.2.35.1" }, { "GOST2001-CryptoPro-B", "1.2.643.2.2.35.2" }, { "GOST2001-CryptoPro-C", "1.2.643.2.2.35.3" }, { "GOST2001-CryptoPro-A", "GOST2001-CryptoPro-XchA" }, { "GOST2001-CryptoPro-C", "GOST2001-CryptoPro-XchB" }, { "GOST2001-CryptoPro-A", "1.2.643.2.2.36.0" }, { "GOST2001-CryptoPro-C", "1.2.643.2.2.36.1" }, { "GOST2012-tc26-A", "1.2.643.7.1.2.1.2.1" }, { "GOST2012-tc26-B", "1.2.643.7.1.2.1.2.2" }, { "secp256k1", "1.3.132.0.10" }, { NULL, NULL} }; typedef struct { const char *desc; /* Description of the curve. */ unsigned int nbits; /* Number of bits. */ unsigned int fips:1; /* True if this is a FIPS140-2 approved curve. */ /* The model describing this curve. This is mainly used to select the group equation. */ enum gcry_mpi_ec_models model; /* The actual ECC dialect used. This is used for curve specific optimizations and to select encodings etc. */ enum ecc_dialects dialect; const char *p; /* The prime defining the field. */ const char *a, *b; /* The coefficients. For Twisted Edwards Curves b is used for d. For Montgomery Curves (a,b) has ((A-2)/4,B^-1). */ const char *n; /* The order of the base point. */ const char *g_x, *g_y; /* Base point. */ const char *h; /* Cofactor. */ } ecc_domain_parms_t; /* This static table defines all available curves. */ static const ecc_domain_parms_t domain_parms[] = { { /* (-x^2 + y^2 = 1 + dx^2y^2) */ "Ed25519", 256, 0, MPI_EC_EDWARDS, ECC_DIALECT_ED25519, "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", "-0x01", "-0x2DFC9311D490018C7338BF8688861767FF8FF5B2BEBE27548A14B235ECA6874A", "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED", "0x216936D3CD6E53FEC0A4E231FDD6DC5C692CC7609525A7B2C9562D608F25D51A", "0x6666666666666666666666666666666666666666666666666666666666666658", "0x08" }, { /* (y^2 = x^3 + 486662*x^2 + x) */ "Curve25519", 256, 0, MPI_EC_MONTGOMERY, ECC_DIALECT_STANDARD, "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", "0x01DB41", "0x01", "0x1000000000000000000000000000000014DEF9DEA2F79CD65812631A5CF5D3ED", "0x0000000000000000000000000000000000000000000000000000000000000009", "0x20AE19A1B8A086B4E01EDD2C7748D14C923D4D7E6D7C61B229E9C5A27ECED3D9", "0x08" /* Note: As per RFC-7748 errata eid4730 the g_y value should be * "0x5F51E65E475F794B1FE122D388B72EB36DC2B28192839E4DD6163A5D81312C14" * but that breaks the keygrip. The new value is recovered in * the function _gcry_ecc_fill_in_curve. */ }, + { + /* (y^2 = x^3 + 156326*x^2 + x) */ + "Curve448", 448, 0, + MPI_EC_MONTGOMERY, ECC_DIALECT_STANDARD, + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + "0x98A9", + "0x01", + "0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" + "7CCA23E9C44EDB49AED63690216CC2728DC58F552378C292AB5844F3", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000005", + "0x7D235D1295F5B1F66C98AB6E58326FCECBAE5D34F55545D060F75DC2" + "8DF3F6EDB8027E2346430D211312C4B150677AF76FD7223D457B5B1A", + "0x04" + }, #if 0 /* No real specs yet found. */ { /* x^2 + y^2 = 1 + 3617x^2y^2 mod 2^414 - 17 */ "Curve3617", "0x3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF" "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEF", MPI_EC_EDWARDS, 0, "0x01", "0x0e21", "0x07FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEB3CC92414CF" "706022B36F1C0338AD63CF181B0E71A5E106AF79", "0x1A334905141443300218C0631C326E5FCD46369F44C03EC7F57FF35498A4AB4D" "6D6BA111301A73FAA8537C64C4FD3812F3CBC595", "0x22", "0x08" }, #endif /*0*/ { "NIST P-192", 192, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xfffffffffffffffffffffffffffffffeffffffffffffffff", "0xfffffffffffffffffffffffffffffffefffffffffffffffc", "0x64210519e59c80e70fa7e9ab72243049feb8deecc146b9b1", "0xffffffffffffffffffffffff99def836146bc9b1b4d22831", "0x188da80eb03090f67cbf20eb43a18800f4ff0afd82ff1012", "0x07192b95ffc8da78631011ed6b24cdd573f977a11e794811", "0x01" }, { "NIST P-224", 224, 1, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xffffffffffffffffffffffffffffffff000000000000000000000001", "0xfffffffffffffffffffffffffffffffefffffffffffffffffffffffe", "0xb4050a850c04b3abf54132565044b0b7d7bfd8ba270b39432355ffb4", "0xffffffffffffffffffffffffffff16a2e0b8f03e13dd29455c5c2a3d" , "0xb70e0cbd6bb4bf7f321390b94a03c1d356c21122343280d6115c1d21", "0xbd376388b5f723fb4c22dfe6cd4375a05a07476444d5819985007e34", "0x01" }, { "NIST P-256", 256, 1, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xffffffff00000001000000000000000000000000ffffffffffffffffffffffff", "0xffffffff00000001000000000000000000000000fffffffffffffffffffffffc", "0x5ac635d8aa3a93e7b3ebbd55769886bc651d06b0cc53b0f63bce3c3e27d2604b", "0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551", "0x6b17d1f2e12c4247f8bce6e563a440f277037d812deb33a0f4a13945d898c296", "0x4fe342e2fe1a7f9b8ee7eb4a7c0f9e162bce33576b315ececbb6406837bf51f5", "0x01" }, { "NIST P-384", 384, 1, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" "ffffffff0000000000000000ffffffff", "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffe" "ffffffff0000000000000000fffffffc", "0xb3312fa7e23ee7e4988e056be3f82d19181d9c6efe8141120314088f5013875a" "c656398d8a2ed19d2a85c8edd3ec2aef", "0xffffffffffffffffffffffffffffffffffffffffffffffffc7634d81f4372ddf" "581a0db248b0a77aecec196accc52973", "0xaa87ca22be8b05378eb1c71ef320ad746e1d3b628ba79b9859f741e082542a38" "5502f25dbf55296c3a545e3872760ab7", "0x3617de4a96262c6f5d9e98bf9292dc29f8f41dbd289a147ce9da3113b5f0b8c0" "0a60b1ce1d7e819d7a431d7c90ea0e5f", "0x01" }, { "NIST P-521", 521, 1, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff", "0x01ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffc", "0x051953eb9618e1c9a1f929a21a0b68540eea2da725b99b315f3b8b489918ef10" "9e156193951ec7e937b1652c0bd3bb1bf073573df883d2c34f1ef451fd46b503f00", "0x1fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "ffa51868783bf2f966b7fcc0148f709a5d03bb5c9b8899c47aebb6fb71e91386409", "0x00c6858e06b70404e9cd9e3ecb662395b4429c648139053fb521f828af606b4d" "3dbaa14b5e77efe75928fe1dc127a2ffa8de3348b3c1856a429bf97e7e31c2e5bd66", "0x011839296a789a3bc0045c8a5fb42c7d1bd998f54449579b446817afbd17273e" "662c97ee72995ef42640c550b9013fad0761353c7086a272c24088be94769fd16650", "0x01" }, { "brainpoolP160r1", 160, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xe95e4a5f737059dc60dfc7ad95b3d8139515620f", "0x340e7be2a280eb74e2be61bada745d97e8f7c300", "0x1e589a8595423412134faa2dbdec95c8d8675e58", "0xe95e4a5f737059dc60df5991d45029409e60fc09", "0xbed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3", "0x1667cb477a1a8ec338f94741669c976316da6321", "0x01" }, { "brainpoolP192r1", 192, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xc302f41d932a36cda7a3463093d18db78fce476de1a86297", "0x6a91174076b1e0e19c39c031fe8685c1cae040e5c69a28ef", "0x469a28ef7c28cca3dc721d044f4496bcca7ef4146fbf25c9", "0xc302f41d932a36cda7a3462f9e9e916b5be8f1029ac4acc1", "0xc0a0647eaab6a48753b033c56cb0f0900a2f5c4853375fd6", "0x14b690866abd5bb88b5f4828c1490002e6773fa2fa299b8f", "0x01" }, { "brainpoolP224r1", 224, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xd7c134aa264366862a18302575d1d787b09f075797da89f57ec8c0ff", "0x68a5e62ca9ce6c1c299803a6c1530b514e182ad8b0042a59cad29f43", "0x2580f63ccfe44138870713b1a92369e33e2135d266dbb372386c400b", "0xd7c134aa264366862a18302575d0fb98d116bc4b6ddebca3a5a7939f", "0x0d9029ad2c7e5cf4340823b2a87dc68c9e4ce3174c1e6efdee12c07d", "0x58aa56f772c0726f24c6b89e4ecdac24354b9e99caa3f6d3761402cd", "0x01" }, { "brainpoolP256r1", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xa9fb57dba1eea9bc3e660a909d838d726e3bf623d52620282013481d1f6e5377", "0x7d5a0975fc2c3057eef67530417affe7fb8055c126dc5c6ce94a4b44f330b5d9", "0x26dc5c6ce94a4b44f330b5d9bbd77cbf958416295cf7e1ce6bccdc18ff8c07b6", "0xa9fb57dba1eea9bc3e660a909d838d718c397aa3b561a6f7901e0e82974856a7", "0x8bd2aeb9cb7e57cb2c4b482ffc81b7afb9de27e1e3bd23c23a4453bd9ace3262", "0x547ef835c3dac4fd97f8461a14611dc9c27745132ded8e545c1d54c72f046997", "0x01" }, { "brainpoolP320r1", 320, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xd35e472036bc4fb7e13c785ed201e065f98fcfa6f6f40def4f92b9ec7893ec28" "fcd412b1f1b32e27", "0x3ee30b568fbab0f883ccebd46d3f3bb8a2a73513f5eb79da66190eb085ffa9f4" "92f375a97d860eb4", "0x520883949dfdbc42d3ad198640688a6fe13f41349554b49acc31dccd88453981" "6f5eb4ac8fb1f1a6", "0xd35e472036bc4fb7e13c785ed201e065f98fcfa5b68f12a32d482ec7ee8658e9" "8691555b44c59311", "0x43bd7e9afb53d8b85289bcc48ee5bfe6f20137d10a087eb6e7871e2a10a599c7" "10af8d0d39e20611", "0x14fdd05545ec1cc8ab4093247f77275e0743ffed117182eaa9c77877aaac6ac7" "d35245d1692e8ee1", "0x01" }, { "brainpoolP384r1", 384, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b412b1da197fb71123" "acd3a729901d1a71874700133107ec53", "0x7bc382c63d8c150c3c72080ace05afa0c2bea28e4fb22787139165efba91f90f" "8aa5814a503ad4eb04a8c7dd22ce2826", "0x04a8c7dd22ce28268b39b55416f0447c2fb77de107dcd2a62e880ea53eeb62d5" "7cb4390295dbc9943ab78696fa504c11", "0x8cb91e82a3386d280f5d6f7e50e641df152f7109ed5456b31f166e6cac0425a7" "cf3ab6af6b7fc3103b883202e9046565", "0x1d1c64f068cf45ffa2a63a81b7c13f6b8847a3e77ef14fe3db7fcafe0cbd10e8" "e826e03436d646aaef87b2e247d4af1e", "0x8abe1d7520f9c2a45cb1eb8e95cfd55262b70b29feec5864e19c054ff9912928" "0e4646217791811142820341263c5315", "0x01" }, { "brainpoolP512r1", 512, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330871" "7d4d9b009bc66842aecda12ae6a380e62881ff2f2d82c68528aa6056583a48f3", "0x7830a3318b603b89e2327145ac234cc594cbdd8d3df91610a83441caea9863bc" "2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a72bf2c7b9e7c1ac4d77fc94ca", "0x3df91610a83441caea9863bc2ded5d5aa8253aa10a2ef1c98b9ac8b57f1117a7" "2bf2c7b9e7c1ac4d77fc94cadc083e67984050b75ebae5dd2809bd638016f723", "0xaadd9db8dbe9c48b3fd4e6ae33c9fc07cb308db3b3c9d20ed6639cca70330870" "553e5c414ca92619418661197fac10471db1d381085ddaddb58796829ca90069", "0x81aee4bdd82ed9645a21322e9c4c6a9385ed9f70b5d916c1b43b62eef4d0098e" "ff3b1f78e2d0d48d50d1687b93b97d5f7c6d5047406a5e688b352209bcb9f822", "0x7dde385d566332ecc0eabfa9cf7822fdf209f70024a57b1aa000c55b881f8111" "b2dcde494a5f485e5bca4bd88a2763aed1ca2b2fa8f0540678cd1e0f3ad80892", "0x01" }, { "GOST2001-test", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x8000000000000000000000000000000000000000000000000000000000000431", "0x0000000000000000000000000000000000000000000000000000000000000007", "0x5fbff498aa938ce739b8e022fbafef40563f6e6a3472fc2a514c0ce9dae23b7e", "0x8000000000000000000000000000000150fe8a1892976154c59cfc193accf5b3", "0x0000000000000000000000000000000000000000000000000000000000000002", "0x08e2a8a0e65147d4bd6316030e16d19c85c97f0a9ca267122b96abbcea7e8fc8", "0x01" }, { "GOST2001-CryptoPro-A", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd97", "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffd94", "0x00000000000000000000000000000000000000000000000000000000000000a6", "0xffffffffffffffffffffffffffffffff6c611070995ad10045841b09b761b893", "0x0000000000000000000000000000000000000000000000000000000000000001", "0x8d91e471e0989cda27df505a453f2b7635294f2ddf23e3b122acc99c9e9f1e14", "0x01" }, { "GOST2001-CryptoPro-B", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x8000000000000000000000000000000000000000000000000000000000000c99", "0x8000000000000000000000000000000000000000000000000000000000000c96", "0x3e1af419a269a5f866a7d3c25c3df80ae979259373ff2b182f49d4ce7e1bbc8b", "0x800000000000000000000000000000015f700cfff1a624e5e497161bcc8a198f", "0x0000000000000000000000000000000000000000000000000000000000000001", "0x3fa8124359f96680b83d1c3eb2c070e5c545c9858d03ecfb744bf8d717717efc", "0x01" }, { "GOST2001-CryptoPro-C", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x9b9f605f5a858107ab1ec85e6b41c8aacf846e86789051d37998f7b9022d759b", "0x9b9f605f5a858107ab1ec85e6b41c8aacf846e86789051d37998f7b9022d7598", "0x000000000000000000000000000000000000000000000000000000000000805a", "0x9b9f605f5a858107ab1ec85e6b41c8aa582ca3511eddfb74f02f3a6598980bb9", "0x0000000000000000000000000000000000000000000000000000000000000000", "0x41ece55743711a8c3cbf3783cd08c0ee4d4dc440d4641a8f366e550dfdb3bb67", "0x01" }, { "GOST2012-test", 511, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d" "f1d852741af4704a0458047e80e4546d35b8336fac224dd81664bbf528be6373", "0x0000000000000000000000000000000000000000000000000000000000000007", "0x1cff0806a31116da29d8cfa54e57eb748bc5f377e49400fdd788b649eca1ac4" "361834013b2ad7322480a89ca58e0cf74bc9e540c2add6897fad0a3084f302adc", "0x4531acd1fe0023c7550d267b6b2fee80922b14b2ffb90f04d4eb7c09b5d2d15d" "a82f2d7ecb1dbac719905c5eecc423f1d86e25edbe23c595d644aaf187e6e6df", "0x24d19cc64572ee30f396bf6ebbfd7a6c5213b3b3d7057cc825f91093a68cd762" "fd60611262cd838dc6b60aa7eee804e28bc849977fac33b4b530f1b120248a9a", "0x2bb312a43bd2ce6e0d020613c857acddcfbf061e91e5f2c3f32447c259f39b2" "c83ab156d77f1496bf7eb3351e1ee4e43dc1a18b91b24640b6dbb92cb1add371e", "0x01" }, { "GOST2012-tc26-A", 512, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdc7", "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffdc4", "0xe8c2505dedfc86ddc1bd0b2b6667f1da34b82574761cb0e879bd081cfd0b6265" "ee3cb090f30d27614cb4574010da90dd862ef9d4ebee4761503190785a71c760", "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff" "27e69532f48d89116ff22b8d4e0560609b4b38abfad2b85dcacdb1411f10b275", "0x0000000000000000000000000000000000000000000000000000000000000000" "0000000000000000000000000000000000000000000000000000000000000003", "0x7503cfe87a836ae3a61b8816e25450e6ce5e1c93acf1abc1778064fdcbefa921" "df1626be4fd036e93d75e6a50e3a41e98028fe5fc235f5b889a589cb5215f2a4", "0x01" }, { "GOST2012-tc26-B", 512, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0x8000000000000000000000000000000000000000000000000000000000000000" "000000000000000000000000000000000000000000000000000000000000006f", "0x8000000000000000000000000000000000000000000000000000000000000000" "000000000000000000000000000000000000000000000000000000000000006c", "0x687d1b459dc841457e3e06cf6f5e2517b97c7d614af138bcbf85dc806c4b289f" "3e965d2db1416d217f8b276fad1ab69c50f78bee1fa3106efb8ccbc7c5140116", "0x8000000000000000000000000000000000000000000000000000000000000001" "49a1ec142565a545acfdb77bd9d40cfa8b996712101bea0ec6346c54374f25bd", "0x0000000000000000000000000000000000000000000000000000000000000000" "0000000000000000000000000000000000000000000000000000000000000002", "0x1a8f7eda389b094c2c071e3647a8940f3c123b697578c213be6dd9e6c8ec7335" "dcb228fd1edf4a39152cbcaaf8c0398828041055f94ceeec7e21340780fe41bd", "0x01" }, { "secp256k1", 256, 0, MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F", "0x0000000000000000000000000000000000000000000000000000000000000000", "0x0000000000000000000000000000000000000000000000000000000000000007", "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141", "0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798", "0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8", "0x01" }, { NULL, 0, 0, 0, 0, NULL, NULL, NULL, NULL, NULL } }; /* Return a copy of POINT. */ static gcry_mpi_point_t point_copy (gcry_mpi_point_t point) { gcry_mpi_point_t newpoint; if (point) { newpoint = mpi_point_new (0); point_set (newpoint, point); } else newpoint = NULL; return newpoint; } /* Helper to scan a hex string. */ static gcry_mpi_t scanval (const char *string) { gpg_err_code_t rc; gcry_mpi_t val; rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); if (rc) log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc)); return val; } /* Return the index of the domain_parms table for a curve with NAME. Return -1 if not found. */ static int find_domain_parms_idx (const char *name) { int idx, aliasno; /* First check our native curves. */ for (idx = 0; domain_parms[idx].desc; idx++) if (!strcmp (name, domain_parms[idx].desc)) return idx; /* If not found consult the alias table. */ if (!domain_parms[idx].desc) { for (aliasno = 0; curve_aliases[aliasno].name; aliasno++) if (!strcmp (name, curve_aliases[aliasno].other)) break; if (curve_aliases[aliasno].name) { for (idx = 0; domain_parms[idx].desc; idx++) if (!strcmp (curve_aliases[aliasno].name, domain_parms[idx].desc)) return idx; } } return -1; } /* Generate the crypto system setup. This function takes the NAME of a curve or the desired number of bits and stores at R_CURVE the parameters of the named curve or those of a suitable curve. If R_NBITS is not NULL, the chosen number of bits is stored there. NULL may be given for R_CURVE, if the value is not required and for example only a quick test for availability is desired. Note that the curve fields should be initialized to zero because fields which are not NULL are skipped. */ gpg_err_code_t _gcry_ecc_fill_in_curve (unsigned int nbits, const char *name, elliptic_curve_t *curve, unsigned int *r_nbits) { int idx; const char *resname = NULL; /* Set to a found curve name. */ if (name) idx = find_domain_parms_idx (name); else { for (idx = 0; domain_parms[idx].desc; idx++) if (nbits == domain_parms[idx].nbits && domain_parms[idx].model == MPI_EC_WEIERSTRASS) break; if (!domain_parms[idx].desc) idx = -1; } if (idx < 0) return GPG_ERR_UNKNOWN_CURVE; resname = domain_parms[idx].desc; /* In fips mode we only support NIST curves. Note that it is possible to bypass this check by specifying the curve parameters directly. */ if (fips_mode () && !domain_parms[idx].fips ) return GPG_ERR_NOT_SUPPORTED; switch (domain_parms[idx].model) { case MPI_EC_WEIERSTRASS: case MPI_EC_EDWARDS: case MPI_EC_MONTGOMERY: break; default: return GPG_ERR_BUG; } if (r_nbits) *r_nbits = domain_parms[idx].nbits; if (curve) { curve->model = domain_parms[idx].model; curve->dialect = domain_parms[idx].dialect; if (!curve->p) curve->p = scanval (domain_parms[idx].p); if (!curve->a) { curve->a = scanval (domain_parms[idx].a); if (curve->a->sign) { mpi_resize (curve->a, curve->p->nlimbs); _gcry_mpih_sub_n (curve->a->d, curve->p->d, curve->a->d, curve->p->nlimbs); curve->a->nlimbs = curve->p->nlimbs; curve->a->sign = 0; } } if (!curve->b) { curve->b = scanval (domain_parms[idx].b); if (curve->b->sign) { mpi_resize (curve->b, curve->p->nlimbs); _gcry_mpih_sub_n (curve->b->d, curve->p->d, curve->b->d, curve->p->nlimbs); curve->b->nlimbs = curve->p->nlimbs; curve->b->sign = 0; } } if (!curve->n) curve->n = scanval (domain_parms[idx].n); if (!curve->h) curve->h = scanval (domain_parms[idx].h); if (!curve->G.x) curve->G.x = scanval (domain_parms[idx].g_x); if (!curve->G.y) curve->G.y = scanval (domain_parms[idx].g_y); /* * In the constants of domain_parms, we defined Curve25519 * domain parameters as the ones in RFC-7748 before the errata * (eid4730). To keep the computation having exact same values, * we recover the new value of g_y, here. */ if (!strcmp (resname, "Curve25519")) mpi_sub (curve->G.y, curve->p, curve->G.y); if (!curve->G.z) curve->G.z = mpi_alloc_set_ui (1); if (!curve->name) curve->name = resname; } return 0; } /* Give the name of the curve NAME, store the curve parameters into P, A, B, G, N, and H if they point to NULL value. Note that G is returned in standard uncompressed format. Also update MODEL and DIALECT if they are not NULL. */ gpg_err_code_t _gcry_ecc_update_curve_param (const char *name, enum gcry_mpi_ec_models *model, enum ecc_dialects *dialect, gcry_mpi_t *p, gcry_mpi_t *a, gcry_mpi_t *b, gcry_mpi_t *g, gcry_mpi_t *n, gcry_mpi_t *h) { int idx; idx = find_domain_parms_idx (name); if (idx < 0) return GPG_ERR_UNKNOWN_CURVE; if (g) { char *buf; size_t len; len = 4; len += strlen (domain_parms[idx].g_x+2); len += strlen (domain_parms[idx].g_y+2); len++; buf = xtrymalloc (len); if (!buf) return gpg_err_code_from_syserror (); strcpy (stpcpy (stpcpy (buf, "0x04"), domain_parms[idx].g_x+2), domain_parms[idx].g_y+2); _gcry_mpi_release (*g); *g = scanval (buf); xfree (buf); } if (model) *model = domain_parms[idx].model; if (dialect) *dialect = domain_parms[idx].dialect; if (p) { _gcry_mpi_release (*p); *p = scanval (domain_parms[idx].p); } if (a) { _gcry_mpi_release (*a); *a = scanval (domain_parms[idx].a); } if (b) { _gcry_mpi_release (*b); *b = scanval (domain_parms[idx].b); } if (n) { _gcry_mpi_release (*n); *n = scanval (domain_parms[idx].n); } if (h) { _gcry_mpi_release (*h); *h = scanval (domain_parms[idx].h); } return 0; } /* Return the name matching the parameters in PKEY. This works only with curves described by the Weierstrass equation. */ const char * _gcry_ecc_get_curve (gcry_sexp_t keyparms, int iterator, unsigned int *r_nbits) { gpg_err_code_t rc; const char *result = NULL; elliptic_curve_t E; gcry_mpi_t mpi_g = NULL; gcry_mpi_t tmp = NULL; int idx; memset (&E, 0, sizeof E); if (r_nbits) *r_nbits = 0; if (!keyparms) { idx = iterator; if (idx >= 0 && idx < DIM (domain_parms)) { result = domain_parms[idx].desc; if (r_nbits) *r_nbits = domain_parms[idx].nbits; } return result; } /* * Extract the curve parameters.. */ rc = gpg_err_code (sexp_extract_param (keyparms, NULL, "-pabgnh", &E.p, &E.a, &E.b, &mpi_g, &E.n, &E.h, NULL)); if (rc == GPG_ERR_NO_OBJ) { /* This might be the second use case of checking whether a specific curve given by name is supported. */ gcry_sexp_t l1; char *name; l1 = sexp_find_token (keyparms, "curve", 5); if (!l1) goto leave; /* No curve name parameter. */ name = sexp_nth_string (l1, 1); sexp_release (l1); if (!name) goto leave; /* Name missing or out of core. */ idx = find_domain_parms_idx (name); xfree (name); if (idx >= 0) /* Curve found. */ { result = domain_parms[idx].desc; if (r_nbits) *r_nbits = domain_parms[idx].nbits; } return result; } if (rc) goto leave; if (mpi_g) { _gcry_mpi_point_init (&E.G); if (_gcry_ecc_os2ec (&E.G, mpi_g)) goto leave; } for (idx = 0; domain_parms[idx].desc; idx++) { mpi_free (tmp); tmp = scanval (domain_parms[idx].p); if (!mpi_cmp (tmp, E.p)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].a); if (!mpi_cmp (tmp, E.a)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].b); if (!mpi_cmp (tmp, E.b)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].n); if (!mpi_cmp (tmp, E.n)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].h); if (!mpi_cmp (tmp, E.h)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].g_x); if (!mpi_cmp (tmp, E.G.x)) { mpi_free (tmp); tmp = scanval (domain_parms[idx].g_y); if (!mpi_cmp (tmp, E.G.y)) { result = domain_parms[idx].desc; if (r_nbits) *r_nbits = domain_parms[idx].nbits; goto leave; } } } } } } } } leave: _gcry_mpi_release (tmp); _gcry_mpi_release (E.p); _gcry_mpi_release (E.a); _gcry_mpi_release (E.b); _gcry_mpi_release (mpi_g); _gcry_mpi_point_free_parts (&E.G); _gcry_mpi_release (E.n); _gcry_mpi_release (E.h); return result; } /* Helper to extract an MPI from key parameters. */ static gpg_err_code_t mpi_from_keyparam (gcry_mpi_t *r_a, gcry_sexp_t keyparam, const char *name) { gcry_err_code_t ec = 0; gcry_sexp_t l1; l1 = sexp_find_token (keyparam, name, 0); if (l1) { *r_a = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_USG); sexp_release (l1); if (!*r_a) ec = GPG_ERR_INV_OBJ; } return ec; } /* Helper to extract a point from key parameters. If no parameter with NAME is found, the functions tries to find a non-encoded point by appending ".x", ".y" and ".z" to NAME. ".z" is in this case optional and defaults to 1. EC is the context which at this point may not be fully initialized. */ static gpg_err_code_t point_from_keyparam (gcry_mpi_point_t *r_a, gcry_sexp_t keyparam, const char *name, mpi_ec_t ec) { gcry_err_code_t rc; gcry_sexp_t l1; gcry_mpi_point_t point; l1 = sexp_find_token (keyparam, name, 0); if (l1) { gcry_mpi_t a; a = sexp_nth_mpi (l1, 1, GCRYMPI_FMT_OPAQUE); sexp_release (l1); if (!a) return GPG_ERR_INV_OBJ; point = mpi_point_new (0); rc = _gcry_mpi_ec_decode_point (point, a, ec); mpi_free (a); if (rc) { mpi_point_release (point); return rc; } } else { char *tmpname; gcry_mpi_t x = NULL; gcry_mpi_t y = NULL; gcry_mpi_t z = NULL; tmpname = xtrymalloc (strlen (name) + 2 + 1); if (!tmpname) return gpg_err_code_from_syserror (); strcpy (stpcpy (tmpname, name), ".x"); rc = mpi_from_keyparam (&x, keyparam, tmpname); if (rc) { xfree (tmpname); return rc; } strcpy (stpcpy (tmpname, name), ".y"); rc = mpi_from_keyparam (&y, keyparam, tmpname); if (rc) { mpi_free (x); xfree (tmpname); return rc; } strcpy (stpcpy (tmpname, name), ".z"); rc = mpi_from_keyparam (&z, keyparam, tmpname); if (rc) { mpi_free (y); mpi_free (x); xfree (tmpname); return rc; } if (!z) z = mpi_set_ui (NULL, 1); if (x && y) point = mpi_point_snatch_set (NULL, x, y, z); else { mpi_free (x); mpi_free (y); mpi_free (z); point = NULL; } xfree (tmpname); } if (point) *r_a = point; return 0; } /* This function creates a new context for elliptic curve operations. Either KEYPARAM or CURVENAME must be given. If both are given and KEYPARAM has no curve parameter, CURVENAME is used to add missing parameters. On success 0 is returned and the new context stored at R_CTX. 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_new (gcry_ctx_t *r_ctx, gcry_sexp_t keyparam, const char *curvename) { gpg_err_code_t errc; gcry_ctx_t ctx = NULL; enum gcry_mpi_ec_models model = MPI_EC_WEIERSTRASS; enum ecc_dialects dialect = ECC_DIALECT_STANDARD; gcry_mpi_t p = NULL; gcry_mpi_t a = NULL; gcry_mpi_t b = NULL; gcry_mpi_point_t G = NULL; gcry_mpi_t n = NULL; gcry_mpi_t h = NULL; gcry_mpi_point_t Q = NULL; gcry_mpi_t d = NULL; int flags = 0; gcry_sexp_t l1; *r_ctx = NULL; if (keyparam) { /* Parse an optional flags list. */ l1 = sexp_find_token (keyparam, "flags", 0); if (l1) { errc = _gcry_pk_util_parse_flaglist (l1, &flags, NULL); sexp_release (l1); l1 = NULL; if (errc) goto leave; } /* Check whether a curve name was given. */ l1 = sexp_find_token (keyparam, "curve", 5); /* If we don't have a curve name or if override parameters have explicitly been requested, parse them. */ if (!l1 || (flags & PUBKEY_FLAG_PARAM)) { errc = mpi_from_keyparam (&p, keyparam, "p"); if (errc) goto leave; errc = mpi_from_keyparam (&a, keyparam, "a"); if (errc) goto leave; errc = mpi_from_keyparam (&b, keyparam, "b"); if (errc) goto leave; errc = point_from_keyparam (&G, keyparam, "g", NULL); if (errc) goto leave; errc = mpi_from_keyparam (&n, keyparam, "n"); if (errc) goto leave; errc = mpi_from_keyparam (&h, keyparam, "h"); if (errc) goto leave; } } else l1 = NULL; /* No curvename. */ /* Check whether a curve parameter is available and use that to fill in missing values. If no curve parameter is available try an optional provided curvename. If only the curvename has been given use that one. */ if (l1 || curvename) { char *name; elliptic_curve_t *E; if (l1) { name = sexp_nth_string (l1, 1); sexp_release (l1); if (!name) { errc = GPG_ERR_INV_OBJ; /* Name missing or out of core. */ goto leave; } } else name = NULL; E = xtrycalloc (1, sizeof *E); if (!E) { errc = gpg_err_code_from_syserror (); xfree (name); goto leave; } errc = _gcry_ecc_fill_in_curve (0, name? name : curvename, E, NULL); xfree (name); if (errc) { xfree (E); goto leave; } model = E->model; dialect = E->dialect; if (!p) { p = E->p; E->p = NULL; } if (!a) { a = E->a; E->a = NULL; } if (!b) { b = E->b; E->b = NULL; } if (!G) { G = mpi_point_snatch_set (NULL, E->G.x, E->G.y, E->G.z); E->G.x = NULL; E->G.y = NULL; E->G.z = NULL; } if (!n) { n = E->n; E->n = NULL; } if (!h) { h = E->h; E->h = NULL; } _gcry_ecc_curve_free (E); xfree (E); } errc = _gcry_mpi_ec_p_new (&ctx, model, dialect, flags, p, a, b); if (!errc) { mpi_ec_t ec = _gcry_ctx_get_pointer (ctx, CONTEXT_TYPE_EC); if (b) { mpi_free (ec->b); ec->b = b; b = NULL; } if (G) { ec->G = G; G = NULL; } if (n) { ec->n = n; n = NULL; } if (h) { ec->h = h; h = NULL; } /* Now that we know the curve name we can look for the public key Q. point_from_keyparam needs to know the curve parameters so that it is able to use the correct decompression. Parsing the private key D could have been done earlier but it is less surprising if we do it here as well. */ if (keyparam) { errc = point_from_keyparam (&Q, keyparam, "q", ec); if (errc) goto leave; errc = mpi_from_keyparam (&d, keyparam, "d"); if (errc) goto leave; } if (Q) { ec->Q = Q; Q = NULL; } if (d) { ec->d = d; d = NULL; } *r_ctx = ctx; ctx = NULL; } leave: _gcry_ctx_release (ctx); mpi_free (p); mpi_free (a); mpi_free (b); _gcry_mpi_point_release (G); mpi_free (n); mpi_free (h); _gcry_mpi_point_release (Q); mpi_free (d); return errc; } /* Return the parameters of the curve NAME as an S-expression. */ gcry_sexp_t _gcry_ecc_get_param_sexp (const char *name) { unsigned int nbits; elliptic_curve_t E; mpi_ec_t ctx; gcry_mpi_t g_x, g_y; gcry_mpi_t pkey[7]; gcry_sexp_t result; int i; memset (&E, 0, sizeof E); if (_gcry_ecc_fill_in_curve (0, name, &E, &nbits)) return NULL; g_x = mpi_new (0); g_y = mpi_new (0); ctx = _gcry_mpi_ec_p_internal_new (MPI_EC_WEIERSTRASS, ECC_DIALECT_STANDARD, 0, E.p, E.a, NULL); if (_gcry_mpi_ec_get_affine (g_x, g_y, &E.G, ctx)) log_fatal ("ecc get param: Failed to get affine coordinates\n"); _gcry_mpi_ec_free (ctx); _gcry_mpi_point_free_parts (&E.G); pkey[0] = E.p; pkey[1] = E.a; pkey[2] = E.b; pkey[3] = _gcry_ecc_ec2os (g_x, g_y, E.p); pkey[4] = E.n; pkey[5] = E.h; pkey[6] = NULL; mpi_free (g_x); mpi_free (g_y); if (sexp_build (&result, NULL, "(public-key(ecc(p%m)(a%m)(b%m)(g%m)(n%m)(h%m)))", pkey[0], pkey[1], pkey[2], pkey[3], pkey[4], pkey[5])) result = NULL; for (i=0; pkey[i]; i++) _gcry_mpi_release (pkey[i]); return result; } /* Return an MPI (or opaque MPI) described by NAME and the context EC. If COPY is true a copy is returned, if not a const MPI may be returned. In any case mpi_free must be used. */ gcry_mpi_t _gcry_ecc_get_mpi (const char *name, mpi_ec_t ec, int copy) { if (!*name) return NULL; if (!strcmp (name, "p") && ec->p) return mpi_is_const (ec->p) && !copy? ec->p : mpi_copy (ec->p); if (!strcmp (name, "a") && ec->a) return mpi_is_const (ec->a) && !copy? ec->a : mpi_copy (ec->a); if (!strcmp (name, "b") && ec->b) return mpi_is_const (ec->b) && !copy? ec->b : mpi_copy (ec->b); if (!strcmp (name, "n") && ec->n) return mpi_is_const (ec->n) && !copy? ec->n : mpi_copy (ec->n); if (!strcmp (name, "h") && ec->h) return mpi_is_const (ec->h) && !copy? ec->h : mpi_copy (ec->h); if (!strcmp (name, "d") && ec->d) return mpi_is_const (ec->d) && !copy? ec->d : mpi_copy (ec->d); /* Return a requested point coordinate. */ if (!strcmp (name, "g.x") && ec->G && ec->G->x) return mpi_is_const (ec->G->x) && !copy? ec->G->x : mpi_copy (ec->G->x); if (!strcmp (name, "g.y") && ec->G && ec->G->y) return mpi_is_const (ec->G->y) && !copy? ec->G->y : mpi_copy (ec->G->y); if (!strcmp (name, "q.x") && ec->Q && ec->Q->x) return mpi_is_const (ec->Q->x) && !copy? ec->Q->x : mpi_copy (ec->Q->x); if (!strcmp (name, "q.y") && ec->Q && ec->Q->y) return mpi_is_const (ec->Q->y) && !copy? ec->Q->y : mpi_copy (ec->Q->y); /* If the base point has been requested, return it in standard encoding. */ if (!strcmp (name, "g") && ec->G) return _gcry_mpi_ec_ec2os (ec->G, ec); /* If the public key has been requested, return it by default in standard uncompressed encoding or if requested in other encodings. */ if (*name == 'q' && (!name[1] || name[1] == '@')) { /* If only the private key is given, compute the public key. */ if (!ec->Q) ec->Q = _gcry_ecc_compute_public (NULL, ec, NULL, NULL); if (!ec->Q) return NULL; if (name[1] != '@') return _gcry_mpi_ec_ec2os (ec->Q, ec); if (!strcmp (name+2, "eddsa") && ec->model == MPI_EC_EDWARDS) { unsigned char *encpk; unsigned int encpklen; if (!_gcry_ecc_eddsa_encodepoint (ec->Q, ec, NULL, NULL, 0, &encpk, &encpklen)) return mpi_set_opaque (NULL, encpk, encpklen*8); } } return NULL; } /* Return a point described by NAME and the context EC. */ gcry_mpi_point_t _gcry_ecc_get_point (const char *name, mpi_ec_t ec) { if (!strcmp (name, "g") && ec->G) return point_copy (ec->G); if (!strcmp (name, "q")) { /* If only the private key is given, compute the public key. */ if (!ec->Q) ec->Q = _gcry_ecc_compute_public (NULL, ec, NULL, NULL); if (ec->Q) return point_copy (ec->Q); } return NULL; } /* Store the MPI NEWVALUE into the context EC under NAME. */ gpg_err_code_t _gcry_ecc_set_mpi (const char *name, gcry_mpi_t newvalue, mpi_ec_t ec) { gpg_err_code_t rc = 0; if (!*name) ; else if (!strcmp (name, "p")) { mpi_free (ec->p); ec->p = mpi_copy (newvalue); _gcry_mpi_ec_get_reset (ec); } else if (!strcmp (name, "a")) { mpi_free (ec->a); ec->a = mpi_copy (newvalue); _gcry_mpi_ec_get_reset (ec); } else if (!strcmp (name, "b")) { mpi_free (ec->b); ec->b = mpi_copy (newvalue); } else if (!strcmp (name, "n")) { mpi_free (ec->n); ec->n = mpi_copy (newvalue); } else if (!strcmp (name, "h")) { mpi_free (ec->h); ec->h = mpi_copy (newvalue); } else if (*name == 'q' && (!name[1] || name[1] == '@')) { if (newvalue) { if (!ec->Q) ec->Q = mpi_point_new (0); rc = _gcry_mpi_ec_decode_point (ec->Q, newvalue, ec); } if (rc || !newvalue) { _gcry_mpi_point_release (ec->Q); ec->Q = NULL; } /* Note: We assume that Q matches d and thus do not reset d. */ } else if (!strcmp (name, "d")) { mpi_free (ec->d); ec->d = mpi_copy (newvalue); if (ec->d) { /* We need to reset the public key because it may not anymore match. */ _gcry_mpi_point_release (ec->Q); ec->Q = NULL; } } else rc = GPG_ERR_UNKNOWN_NAME; return rc; } /* Store the point NEWVALUE into the context EC under NAME. */ gpg_err_code_t _gcry_ecc_set_point (const char *name, gcry_mpi_point_t newvalue, mpi_ec_t ec) { if (!strcmp (name, "g")) { _gcry_mpi_point_release (ec->G); ec->G = point_copy (newvalue); } else if (!strcmp (name, "q")) { _gcry_mpi_point_release (ec->Q); ec->Q = point_copy (newvalue); } else return GPG_ERR_UNKNOWN_NAME; return 0; } diff --git a/cipher/ecc-ecdh.c b/cipher/ecc-ecdh.c index bfd07d40..405fc142 100644 --- a/cipher/ecc-ecdh.c +++ b/cipher/ecc-ecdh.c @@ -1,142 +1,141 @@ /* ecc-ecdh.c - Elliptic Curve Diffie-Hellman key agreement * Copyright (C) 2019 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 . * SPDX-License-Identifier: LGPL-2.1+ */ #include #include #include #include #include #include "g10lib.h" #include "mpi.h" #include "cipher.h" #include "context.h" #include "ec-context.h" #include "ecc-common.h" #define ECC_CURVE25519_BITS 256 #define ECC_CURVE448_BITS 448 static mpi_ec_t prepare_ec (const char *curve_name, elliptic_curve_t *E) { mpi_ec_t ec; memset (E, 0, sizeof *E); if (_gcry_ecc_fill_in_curve (0, curve_name, E, NULL)) return NULL; ec = _gcry_mpi_ec_p_internal_new (E->model, E->dialect, PUBKEY_FLAG_DJB_TWEAK, E->p, E->a, E->b); return ec; } unsigned int _gcry_ecc_get_algo_keylen (int algo) { unsigned int len = 0; if (algo == GCRY_ECC_CURVE25519) len = ECC_CURVE25519_BITS/8; else if (algo == GCRY_ECC_CURVE448) len = ECC_CURVE448_BITS/8; return len; } gpg_error_t _gcry_ecc_mul_point (int algo, unsigned char *result, const unsigned char *scalar, const unsigned char *point) { unsigned int nbits; unsigned int nbytes; const char *curve; gpg_err_code_t err; elliptic_curve_t E; unsigned char buffer[ECC_CURVE448_BITS/8]; gcry_mpi_t mpi_k; mpi_ec_t ec; gcry_mpi_t mpi_u; mpi_point_t Q; gcry_mpi_t x; unsigned int len; int i; unsigned char *buf; if (algo == GCRY_ECC_CURVE25519) { nbits = ECC_CURVE25519_BITS; curve = "Curve25519"; } else if (algo == GCRY_ECC_CURVE448) { nbits = ECC_CURVE448_BITS; - curve = "X448"; - return gpg_error (GPG_ERR_UNSUPPORTED_ALGORITHM); + curve = "Curve448"; } else return gpg_error (GPG_ERR_UNKNOWN_ALGORITHM); nbytes = nbits / 8; mpi_k = mpi_new (nbits); ec = prepare_ec (curve, &E); mpi_u = mpi_new (nbits); Q = mpi_point_new (nbits); x = mpi_new (nbits); memcpy (buffer, scalar, nbytes); reverse_buffer (buffer, nbytes); _gcry_mpi_set_buffer (mpi_k, buffer, nbytes, 0); for (i = 0; i < mpi_get_nbits (E.h) - 1; i++) mpi_clear_bit (mpi_k, i); mpi_set_highbit (mpi_k, mpi_get_nbits (E.p) - 1); if (point) { mpi_point_t P = mpi_point_new (nbits); _gcry_mpi_set_buffer (mpi_u, point, nbytes, 0); err = _gcry_ecc_mont_decodepoint (mpi_u, ec, P); _gcry_mpi_release (mpi_u); if (err) goto leave; _gcry_mpi_ec_mul_point (Q, mpi_k, P, ec); _gcry_mpi_point_release (P); } else _gcry_mpi_ec_mul_point (Q, mpi_k, &E.G, ec); _gcry_mpi_ec_get_affine (x, NULL, Q, ec); buf = _gcry_mpi_get_buffer (x, nbytes, &len, NULL); if (!buf) err = gpg_error_from_syserror (); memcpy (result, buf, nbytes); xfree (buf); leave: _gcry_mpi_release (x); _gcry_mpi_point_release (Q); _gcry_mpi_release (mpi_k); return err; } diff --git a/mpi/ec.c b/mpi/ec.c index ed936d74..2b2fc22a 100644 --- a/mpi/ec.c +++ b/mpi/ec.c @@ -1,1847 +1,2047 @@ /* 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 functions. 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); } /* Return a copy of POINT. */ gcry_mpi_point_t _gcry_mpi_point_copy (gcry_mpi_point_t point) { mpi_point_t newpoint; newpoint = _gcry_mpi_point_new (0); if (point) point_set (newpoint, point); return newpoint; } static void point_resize (mpi_point_t p, mpi_ec_t ctx) { size_t nlimbs = ctx->p->nlimbs; mpi_resize (p->x, nlimbs); p->x->nlimbs = nlimbs; mpi_resize (p->z, nlimbs); p->z->nlimbs = nlimbs; if (ctx->model != MPI_EC_MONTGOMERY) { mpi_resize (p->y, nlimbs); p->y->nlimbs = 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); } } static void mpih_set_cond (mpi_ptr_t wp, mpi_ptr_t up, mpi_size_t usize, unsigned long set) { mpi_size_t i; mpi_limb_t mask = ((mpi_limb_t)0) - set; mpi_limb_t x; for (i = 0; i < usize; i++) { x = mask & (wp[i] ^ up[i]); wp[i] = wp[i] ^ x; } } - + /* Routines for 2^255 - 19. */ #define LIMB_SIZE_25519 ((256+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) static void ec_addm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug ("addm_25519: different sizes\n"); memset (n, 0, sizeof n); up = u->d; vp = v->d; wp = w->d; _gcry_mpih_add_n (wp, up, vp, wsize); borrow = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize); mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL)); _gcry_mpih_add_n (wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); } static void ec_subm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519]; mpi_limb_t borrow; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug ("subm_25519: different sizes\n"); memset (n, 0, sizeof n); up = u->d; vp = v->d; wp = w->d; borrow = _gcry_mpih_sub_n (wp, up, vp, wsize); mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL)); _gcry_mpih_add_n (wp, wp, n, wsize); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); } static void ec_mulm_25519 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) { mpi_ptr_t wp, up, vp; mpi_size_t wsize = LIMB_SIZE_25519; mpi_limb_t n[LIMB_SIZE_25519*2]; mpi_limb_t m[LIMB_SIZE_25519+1]; mpi_limb_t cy; int msb; (void)ctx; if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) log_bug ("mulm_25519: different sizes\n"); up = u->d; vp = v->d; wp = w->d; _gcry_mpih_mul_n (n, up, vp, wsize); memcpy (wp, n, wsize * BYTES_PER_MPI_LIMB); wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); memcpy (m, n+LIMB_SIZE_25519-1, (wsize+1) * BYTES_PER_MPI_LIMB); _gcry_mpih_rshift (m, m, LIMB_SIZE_25519+1, (255 % BITS_PER_MPI_LIMB)); memcpy (n, m, wsize * BYTES_PER_MPI_LIMB); cy = _gcry_mpih_lshift (m, m, LIMB_SIZE_25519, 4); m[LIMB_SIZE_25519] = cy; cy = _gcry_mpih_add_n (m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = _gcry_mpih_add_n (m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = _gcry_mpih_add_n (m, m, n, wsize); m[LIMB_SIZE_25519] += cy; cy = _gcry_mpih_add_n (wp, wp, m, wsize); m[LIMB_SIZE_25519] += cy; memset (m, 0, wsize * BYTES_PER_MPI_LIMB); msb = (wp[LIMB_SIZE_25519-1] >> (255 % BITS_PER_MPI_LIMB)); m[0] = (m[LIMB_SIZE_25519] * 2 + msb) * 19; wp[LIMB_SIZE_25519-1] &= ~((mpi_limb_t)1 << (255 % BITS_PER_MPI_LIMB)); _gcry_mpih_add_n (wp, wp, m, wsize); m[0] = 0; cy = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize); mpih_set_cond (m, ctx->p->d, wsize, (cy != 0UL)); _gcry_mpih_add_n (wp, wp, m, wsize); } static void ec_mul2_25519 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx) { ec_addm_25519 (w, u, u, ctx); } static void ec_pow2_25519 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx) { ec_mulm_25519 (w, b, b, ctx); } + +/* Routines for 2^448 - 2^224 - 1. */ + +#define LIMB_SIZE_448 ((448+BITS_PER_MPI_LIMB-1)/BITS_PER_MPI_LIMB) +#define LIMB_SIZE_HALF_448 ((LIMB_SIZE_448+1)/2) + +static void +ec_addm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t cy; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug ("addm_448: different sizes\n"); + + memset (n, 0, sizeof n); + up = u->d; + vp = v->d; + wp = w->d; + + cy = _gcry_mpih_add_n (wp, up, vp, wsize); + mpih_set_cond (n, ctx->p->d, wsize, (cy != 0UL)); + _gcry_mpih_sub_n (wp, wp, n, wsize); +} + +static void +ec_subm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448]; + mpi_limb_t borrow; + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug ("subm_448: different sizes\n"); + + memset (n, 0, sizeof n); + up = u->d; + vp = v->d; + wp = w->d; + + borrow = _gcry_mpih_sub_n (wp, up, vp, wsize); + mpih_set_cond (n, ctx->p->d, wsize, (borrow != 0UL)); + _gcry_mpih_add_n (wp, wp, n, wsize); +} + +static void +ec_mulm_448 (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx) +{ + mpi_ptr_t wp, up, vp; + mpi_size_t wsize = LIMB_SIZE_448; + mpi_limb_t n[LIMB_SIZE_448*2]; + mpi_limb_t a2[LIMB_SIZE_HALF_448]; + mpi_limb_t a3[LIMB_SIZE_HALF_448]; + mpi_limb_t b0[LIMB_SIZE_HALF_448]; + mpi_limb_t b1[LIMB_SIZE_HALF_448]; + mpi_limb_t cy; + int i; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + mpi_limb_t b1_rest, a3_rest; +#endif + + if (w->nlimbs != wsize || u->nlimbs != wsize || v->nlimbs != wsize) + log_bug ("mulm_448: different sizes\n"); + + up = u->d; + vp = v->d; + wp = w->d; + + _gcry_mpih_mul_n (n, up, vp, wsize); + + for (i = 0; i < (wsize + 1)/ 2; i++) + { + b0[i] = n[i]; + b1[i] = n[i+wsize/2]; + a2[i] = n[i+wsize]; + a3[i] = n[i+wsize+wsize/2]; + } + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b0[LIMB_SIZE_HALF_448-1] &= (1UL<<32)-1; + a2[LIMB_SIZE_HALF_448-1] &= (1UL<<32)-1; + + b1_rest = 0; + a3_rest = 0; + + for (i = (wsize + 1)/ 2 -1; i >= 0; i--) + { + mpi_limb_t b1v, a3v; + b1v = b1[i]; + a3v = a3[i]; + b1[i] = (b1_rest<<32) | (b1v >> 32); + a3[i] = (a3_rest<<32) | (a3v >> 32); + b1_rest = b1v & ((1UL <<32)-1); + a3_rest = a3v & ((1UL <<32)-1); + } +#endif + + cy = _gcry_mpih_add_n (b0, b0, a2, LIMB_SIZE_HALF_448); + cy += _gcry_mpih_add_n (b0, b0, a3, LIMB_SIZE_HALF_448); + for (i = 0; i < (wsize + 1)/ 2; i++) + wp[i] = b0[i]; +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + wp[LIMB_SIZE_HALF_448-1] &= ((1UL <<32)-1); +#endif + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b0[LIMB_SIZE_HALF_448-1] >> 32; +#endif + + cy = _gcry_mpih_add_1 (b1, b1, LIMB_SIZE_HALF_448, cy); + cy += _gcry_mpih_add_n (b1, b1, a2, LIMB_SIZE_HALF_448); + cy += _gcry_mpih_add_n (b1, b1, a3, LIMB_SIZE_HALF_448); + cy += _gcry_mpih_add_n (b1, b1, a3, LIMB_SIZE_HALF_448); +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + b1_rest = 0; + for (i = (wsize + 1)/ 2 -1; i >= 0; i--) + { + mpi_limb_t b1v = b1[i]; + b1[i] = (b1_rest<<32) | (b1v >> 32); + b1_rest = b1v & ((1UL <<32)-1); + } + wp[LIMB_SIZE_HALF_448-1] |= (b1_rest << 32); +#endif + for (i = 0; i < wsize / 2; i++) + wp[i+(wsize + 1) / 2] = b1[i]; + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + cy = b1[LIMB_SIZE_HALF_448-1]; +#endif + + memset (n, 0, wsize * BYTES_PER_MPI_LIMB); + +#if (LIMB_SIZE_HALF_448 > LIMB_SIZE_448/2) + n[LIMB_SIZE_HALF_448-1] = cy << 32; +#else + n[LIMB_SIZE_HALF_448] = cy; +#endif + n[0] = cy; + _gcry_mpih_add_n (wp, wp, n, wsize); + + memset (n, 0, wsize * BYTES_PER_MPI_LIMB); + cy = _gcry_mpih_sub_n (wp, wp, ctx->p->d, wsize); + mpih_set_cond (n, ctx->p->d, wsize, (cy != 0UL)); + _gcry_mpih_add_n (wp, wp, n, wsize); +} +static void +ec_mul2_448 (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx) +{ + ec_addm_448 (w, u, u, ctx); +} + +static void +ec_pow2_448 (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx) +{ + ec_mulm_448 (w, b, b, ctx); +} + struct field_table { const char *p; /* computation routines for the field. */ void (* addm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx); void (* subm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx); void (* mulm) (gcry_mpi_t w, gcry_mpi_t u, gcry_mpi_t v, mpi_ec_t ctx); void (* mul2) (gcry_mpi_t w, gcry_mpi_t u, mpi_ec_t ctx); void (* pow2) (gcry_mpi_t w, const gcry_mpi_t b, mpi_ec_t ctx); }; static const struct field_table field_table[] = { { "0x7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED", ec_addm_25519, ec_subm_25519, ec_mulm_25519, ec_mul2_25519, ec_pow2_25519 }, + { + "0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFE" + "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF", + ec_addm_448, + ec_subm_448, + ec_mulm_448, + ec_mul2_448, + ec_pow2_448 + }, { NULL, NULL, NULL, NULL, NULL, NULL }, }; /* 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; } -static const char *curve25519_bad_points[] = { +static const char *const curve25519_bad_points[] = { + "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", "0x0000000000000000000000000000000000000000000000000000000000000000", "0x0000000000000000000000000000000000000000000000000000000000000001", "0x00b8495f16056286fdb1329ceb8d09da6ac49ff1fae35616aeb8413b7c7aebe0", "0x57119fd0dd4e22d8868e1c58c45c44045bef839c55b1d0b1248c50a3bc959c5f", "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffec", - "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffed", "0x7fffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffee", NULL }; + +static const char *const curve448_bad_points[] = { + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "ffffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "0x00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000001", + "0xfffffffffffffffffffffffffffffffffffffffffffffffffffffffe" + "fffffffffffffffffffffffffffffffffffffffffffffffffffffffe", + "0xffffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "00000000000000000000000000000000000000000000000000000000", + NULL +}; + +static const char *const *bad_points_table[] = { + curve25519_bad_points, + curve448_bad_points, +}; + static gcry_mpi_t scanval (const char *string) { gpg_err_code_t rc; gcry_mpi_t val; rc = _gcry_mpi_scan (&val, GCRYMPI_FMT_HEX, string, 0, NULL); if (rc) log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc)); return val; } /* 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); if (model == MPI_EC_MONTGOMERY) { - for (i=0; i< DIM(ctx->t.scratch) && curve25519_bad_points[i]; i++) - ctx->t.scratch[i] = scanval (curve25519_bad_points[i]); + for (i=0; i< DIM(bad_points_table); i++) + { + gcry_mpi_t p_candidate = scanval (bad_points_table[i][0]); + int match_p = !mpi_cmp (ctx->p, p_candidate); + int j; + + mpi_free (p_candidate); + if (!match_p) + continue; + + for (j=0; i< DIM(ctx->t.scratch) && bad_points_table[i][j]; j++) + ctx->t.scratch[j] = scanval (bad_points_table[i][j]); + } } else { /* Allocate scratch variables. */ for (i=0; i< DIM(ctx->t.scratch); i++) ctx->t.scratch[i] = mpi_alloc_like (ctx->p); } ctx->addm = ec_addm; ctx->subm = ec_subm; ctx->mulm = ec_mulm; ctx->mul2 = ec_mul2; ctx->pow2 = ec_pow2; for (i=0; field_table[i].p; i++) { gcry_mpi_t f_p; gpg_err_code_t rc; rc = _gcry_mpi_scan (&f_p, GCRYMPI_FMT_HEX, field_table[i].p, 0, NULL); if (rc) log_fatal ("scanning ECC parameter failed: %s\n", gpg_strerror (rc)); if (!mpi_cmp (p, f_p)) { ctx->addm = field_table[i].addm; ctx->subm = field_table[i].subm; ctx->mulm = field_table[i].mulm; ctx->mul2 = field_table[i].mul2; ctx->pow2 = field_table[i].pow2; _gcry_mpi_release (f_p); mpi_resize (ctx->a, ctx->p->nlimbs); ctx->a->nlimbs = ctx->p->nlimbs; mpi_resize (ctx->b, ctx->p->nlimbs); ctx->b->nlimbs = ctx->p->nlimbs; for (i=0; i< DIM(ctx->t.scratch) && ctx->t.scratch[i]; i++) ctx->t.scratch[i]->nlimbs = ctx->p->nlimbs; break; } _gcry_mpi_release (f_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); mpi_resize (z, ctx->p->nlimbs); z->nlimbs = ctx->p->nlimbs; if (x) { mpi_resize (x, ctx->p->nlimbs); x->nlimbs = ctx->p->nlimbs; ctx->mulm (x, point->x, z, ctx); } if (y) { mpi_resize (y, ctx->p->nlimbs); y->nlimbs = ctx->p->nlimbs; ctx->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 */ ctx->addm (B, X1, Y1, ctx); ctx->pow2 (B, B, ctx); /* C = X_1^2 */ /* D = Y_1^2 */ ctx->pow2 (C, X1, ctx); ctx->pow2 (D, Y1, ctx); /* E = aC */ if (ctx->dialect == ECC_DIALECT_ED25519) ctx->subm (E, ctx->p, C, ctx); else ctx->mulm (E, ctx->a, C, ctx); /* F = E + D */ ctx->addm (F, E, D, ctx); /* H = Z_1^2 */ ctx->pow2 (H, Z1, ctx); /* J = F - 2H */ ctx->mul2 (J, H, ctx); ctx->subm (J, F, J, ctx); /* X_3 = (B - C - D) · J */ ctx->subm (X3, B, C, ctx); ctx->subm (X3, X3, D, ctx); ctx->mulm (X3, X3, J, ctx); /* Y_3 = F · (E - D) */ ctx->subm (Y3, E, D, ctx); ctx->mulm (Y3, Y3, F, ctx); /* Z_3 = F · J */ ctx->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]) point_resize (result, ctx); /* Compute: (X_3 : Y_3 : Z_3) = (X_1 : Y_1 : Z_1) + (X_2 : Y_2 : Z_3) */ /* A = Z1 · Z2 */ ctx->mulm (A, Z1, Z2, ctx); /* B = A^2 */ ctx->pow2 (B, A, ctx); /* C = X1 · X2 */ ctx->mulm (C, X1, X2, ctx); /* D = Y1 · Y2 */ ctx->mulm (D, Y1, Y2, ctx); /* E = d · C · D */ ctx->mulm (E, ctx->b, C, ctx); ctx->mulm (E, E, D, ctx); /* F = B - E */ ctx->subm (F, B, E, ctx); /* G = B + E */ ctx->addm (G, B, E, ctx); /* X_3 = A · F · ((X_1 + Y_1) · (X_2 + Y_2) - C - D) */ ctx->addm (tmp, X1, Y1, ctx); ctx->addm (X3, X2, Y2, ctx); ctx->mulm (X3, X3, tmp, ctx); ctx->subm (X3, X3, C, ctx); ctx->subm (X3, X3, D, ctx); ctx->mulm (X3, X3, F, ctx); ctx->mulm (X3, X3, A, ctx); /* Y_3 = A · G · (D - aC) */ if (ctx->dialect == ECC_DIALECT_ED25519) { ctx->addm (Y3, D, C, ctx); } else { ctx->mulm (Y3, ctx->a, C, ctx); ctx->subm (Y3, D, Y3, ctx); } ctx->mulm (Y3, Y3, G, ctx); ctx->mulm (Y3, Y3, A, ctx); /* Z_3 = F · G */ ctx->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) { ctx->addm (sum->x, p2->x, p2->z, ctx); ctx->subm (p2->z, p2->x, p2->z, ctx); ctx->addm (prd->x, p1->x, p1->z, ctx); ctx->subm (p1->z, p1->x, p1->z, ctx); ctx->mulm (p2->x, p1->z, sum->x, ctx); ctx->mulm (p2->z, prd->x, p2->z, ctx); ctx->pow2 (p1->x, prd->x, ctx); ctx->pow2 (p1->z, p1->z, ctx); ctx->addm (sum->x, p2->x, p2->z, ctx); ctx->subm (p2->z, p2->x, p2->z, ctx); ctx->mulm (prd->x, p1->x, p1->z, ctx); ctx->subm (p1->z, p1->x, p1->z, ctx); ctx->pow2 (sum->x, sum->x, ctx); ctx->pow2 (sum->z, p2->z, ctx); ctx->mulm (prd->z, p1->z, ctx->a, ctx); /* CTX->A: (a-2)/4 */ ctx->mulm (sum->z, sum->z, dif_x, ctx); ctx->addm (prd->z, p1->x, prd->z, ctx); ctx->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); ctx->subm (p2i->x, ctx->p, p2i->x, ctx); 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. 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; if (mpi_cmp (scalar, ctx->p) >= 0) nbits = mpi_get_nbits (scalar); else nbits = mpi_get_nbits (ctx->p); 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); point_resize (point, ctx); } 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 { if (ctx->model == MPI_EC_EDWARDS) { point_resize (result, ctx); point_resize (point, ctx); } 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; mpi_size_t rsize; /* 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); mpi_resize (point->x, ctx->p->nlimbs); point->x->nlimbs = ctx->p->nlimbs; 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); rsize = p1.z->nlimbs; MPN_NORMALIZE (p1.z->d, rsize); if (rsize == 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); /* Check that the point is in range. This needs to be done here and * not after conversion to affine coordinates. */ if (mpi_cmpabs (point->x, ctx->p) >= 0) goto leave; if (mpi_cmpabs (point->y, ctx->p) >= 0) goto leave; if (mpi_cmpabs (point->z, ctx->p) >= 0) goto leave; 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; mpi_resize (w, ctx->p->nlimbs); w->nlimbs = ctx->p->nlimbs; /* a · x^2 + y^2 - 1 - b · x^2 · y^2 == 0 */ ctx->pow2 (x, x, ctx); ctx->pow2 (y, y, ctx); if (ctx->dialect == ECC_DIALECT_ED25519) ctx->subm (w, ctx->p, x, ctx); else ctx->mulm (w, ctx->a, x, ctx); ctx->addm (w, w, y, ctx); ctx->mulm (x, x, y, ctx); ctx->mulm (x, x, ctx->b, ctx); ctx->subm (w, w, x, ctx); if (!mpi_cmp_ui (w, 1)) res = 1; } break; } leave: _gcry_mpi_release (w); _gcry_mpi_release (x); _gcry_mpi_release (y); return res; } int _gcry_mpi_ec_bad_point (gcry_mpi_point_t point, mpi_ec_t ctx) { int i; gcry_mpi_t x_bad; for (i = 0; (x_bad = ctx->t.scratch[i]); i++) if (!mpi_cmp (point->x, x_bad)) return 1; return 0; } diff --git a/tests/Makefile.am b/tests/Makefile.am index 9e117970..2ae70e54 100644 --- a/tests/Makefile.am +++ b/tests/Makefile.am @@ -1,67 +1,68 @@ # Copyright (C) 2001, 2002, 2003, 2005 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, write to the Free Software # Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA ## Process this file with automake to produce Makefile.in tests_bin = \ version t-secmem mpitests t-sexp t-convert \ t-mpi-bit t-mpi-point curves t-lock \ prime basic keygen pubkey hmac hashtest t-kdf keygrip \ - fips186-dsa aeswrap pkcs1v2 random dsa-rfc6979 t-ed25519 t-cv25519 + fips186-dsa aeswrap pkcs1v2 random dsa-rfc6979 \ + t-ed25519 t-cv25519 t-cv448 tests_bin_last = benchmark bench-slope tests_sh = basic-disable-all-hwf tests_sh_last = hashtest-256g TESTS = $(tests_bin) $(tests_sh) $(tests_bin_last) $(tests_sh_last) # Force sequential run of some tests. bench-slope.log: benchmark.log hashtest-256g.log: bench-slope.log TESTS_ENVIRONMENT = GCRYPT_IN_REGRESSION_TEST=1 # Need to include ../src in addition to top_srcdir because gcrypt.h is # a built header. AM_CPPFLAGS = -I../src -I$(top_srcdir)/src AM_CFLAGS = $(GPG_ERROR_CFLAGS) AM_LDFLAGS = -no-install standard_ldadd = \ ../src/libgcrypt.la $(DL_LIBS) \ ../compat/libcompat.la EXTRA_PROGRAMS = testapi pkbench noinst_PROGRAMS = $(tests_bin) $(tests_bin_last) fipsdrv rsacvt genhashdata \ gchash noinst_HEADERS = t-common.h EXTRA_DIST = README rsa-16k.key cavs_tests.sh cavs_driver.pl \ pkcs1v2-oaep.h pkcs1v2-pss.h pkcs1v2-v15c.h pkcs1v2-v15s.h \ t-ed25519.inp stopwatch.h hashtest-256g.in \ sha3-224.h sha3-256.h sha3-384.h sha3-512.h \ blake2b.h blake2s.h \ basic-disable-all-hwf.in basic_all_hwfeature_combinations.sh LDADD = $(standard_ldadd) $(GPG_ERROR_LIBS) @LDADD_FOR_TESTS_KLUDGE@ t_lock_LDADD = $(standard_ldadd) $(GPG_ERROR_MT_LIBS) @LDADD_FOR_TESTS_KLUDGE@ t_lock_CFLAGS = $(GPG_ERROR_MT_CFLAGS) diff --git a/tests/curves.c b/tests/curves.c index dc5ebe77..bacc1302 100644 --- a/tests/curves.c +++ b/tests/curves.c @@ -1,190 +1,190 @@ /* curves.c - ECC curves regression tests * Copyright (C) 2011 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, write to the Free Software * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA */ #ifdef HAVE_CONFIG_H #include #endif #include #include #include #include #include "../src/gcrypt-int.h" #define PGM "curves" #include "t-common.h" /* Number of curves defined in ../cipger/ecc.c */ -#define N_CURVES 22 +#define N_CURVES 23 /* A real world sample public key. */ static char const sample_key_1[] = "(public-key\n" " (ecdsa\n" " (p #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFF#)\n" " (a #00FFFFFFFF00000001000000000000000000000000FFFFFFFFFFFFFFFFFFFFFFFC#)\n" " (b #5AC635D8AA3A93E7B3EBBD55769886BC651D06B0CC53B0F63BCE3C3E27D2604B#)\n" " (g #046B17D1F2E12C4247F8BCE6E563A440F277037D812DEB33A0F4A13945D898C296" "4FE342E2FE1A7F9B8EE7EB4A7C0F9E162BCE33576B315ECECBB6406837BF51F5#)\n" " (n #00FFFFFFFF00000000FFFFFFFFFFFFFFFFBCE6FAADA7179E84F3B9CAC2FC632551#)\n" " (h #000000000000000000000000000000000000000000000000000000000000000001#)\n" " (q #0442B927242237639A36CE9221B340DB1A9AB76DF2FE3E171277F6A4023DED146EE" "86525E38CCECFF3FB8D152CC6334F70D23A525175C1BCBDDE6E023B2228770E#)\n" " ))"; static char const sample_key_1_curve[] = "NIST P-256"; static unsigned int sample_key_1_nbits = 256; /* A made up sample public key. */ static char const sample_key_2[] = "(public-key\n" " (ecdh\n" " (p #00e95e4a5f737059dc60dfc7ad95b3d8139515620f#)\n" " (a #340e7be2a280eb74e2be61bada745d97e8f7c300#)\n" " (b #1e589a8595423412134faa2dbdec95c8d8675e58#)\n" " (g #04bed5af16ea3f6a4f62938c4631eb5af7bdbcdbc3" "1667cb477a1a8ec338f94741669c976316da6321#)\n" " (n #00e95e4a5f737059dc60df5991d45029409e60fc09#)\n" " (h #000000000000000000000000000000000000000000000000000000000000000001#)\n" " (q #041111111111111111111111111111111111111111" "2222222222222222222222222222222222222222#)\n" " ))"; static char const sample_key_2_curve[] = "brainpoolP160r1"; static unsigned int sample_key_2_nbits = 160; static void list_curves (void) { int idx; const char *name; unsigned int nbits; for (idx=0; (name = gcry_pk_get_curve (NULL, idx, &nbits)); idx++) { if (verbose) printf ("%s - %u bits\n", name, nbits); } if (idx != N_CURVES) fail ("expected %d curves but got %d\n", N_CURVES, idx); if (gcry_pk_get_curve (NULL, -1, NULL)) fail ("curve iteration failed\n"); } static void check_matching (void) { gpg_error_t err; gcry_sexp_t key; const char *name; unsigned int nbits; err = gcry_sexp_new (&key, sample_key_1, 0, 1); if (err) die ("parsing s-expression string failed: %s\n", gpg_strerror (err)); name = gcry_pk_get_curve (key, 0, &nbits); if (!name) fail ("curve name not found for sample_key_1\n"); else if (strcmp (name, sample_key_1_curve)) fail ("expected curve name %s but got %s for sample_key_1\n", sample_key_1_curve, name); else if (nbits != sample_key_1_nbits) fail ("expected curve size %u but got %u for sample_key_1\n", sample_key_1_nbits, nbits); gcry_sexp_release (key); err = gcry_sexp_new (&key, sample_key_2, 0, 1); if (err) die ("parsing s-expression string failed: %s\n", gpg_strerror (err)); name = gcry_pk_get_curve (key, 0, &nbits); if (!name) fail ("curve name not found for sample_key_2\n"); else if (strcmp (name, sample_key_2_curve)) fail ("expected curve name %s but got %s for sample_key_2\n", sample_key_2_curve, name); else if (nbits != sample_key_2_nbits) fail ("expected curve size %u but got %u for sample_key_2\n", sample_key_2_nbits, nbits); gcry_sexp_release (key); } static void check_get_params (void) { gcry_sexp_t param; const char *name; param = gcry_pk_get_param (GCRY_PK_ECDSA, sample_key_1_curve); if (!param) fail ("error gerring parameters for `%s'\n", sample_key_1_curve); name = gcry_pk_get_curve (param, 0, NULL); if (!name) fail ("get_param: curve name not found for sample_key_1\n"); else if (strcmp (name, sample_key_1_curve)) fail ("get_param: expected curve name %s but got %s for sample_key_1\n", sample_key_1_curve, name); gcry_sexp_release (param); /* Brainpool curves are not supported in fips mode */ if (gcry_fips_mode_active()) return; param = gcry_pk_get_param (GCRY_PK_ECDSA, sample_key_2_curve); if (!param) fail ("error gerring parameters for `%s'\n", sample_key_2_curve); name = gcry_pk_get_curve (param, 0, NULL); if (!name) fail ("get_param: curve name not found for sample_key_2\n"); else if (strcmp (name, sample_key_2_curve)) fail ("get_param: expected curve name %s but got %s for sample_key_2\n", sample_key_2_curve, name); gcry_sexp_release (param); } int main (int argc, char **argv) { if (argc > 1 && !strcmp (argv[1], "--verbose")) verbose = 1; else if (argc > 1 && !strcmp (argv[1], "--debug")) verbose = debug = 1; if (!gcry_check_version (GCRYPT_VERSION)) die ("version mismatch\n"); xgcry_control ((GCRYCTL_DISABLE_SECMEM, 0)); xgcry_control ((GCRYCTL_INITIALIZATION_FINISHED, 0)); if (debug) xgcry_control ((GCRYCTL_SET_DEBUG_FLAGS, 1u, 0)); list_curves (); check_matching (); check_get_params (); return error_count ? 1 : 0; } diff --git a/tests/t-cv448.c b/tests/t-cv448.c new file mode 100644 index 00000000..85fea298 --- /dev/null +++ b/tests/t-cv448.c @@ -0,0 +1,602 @@ +/* t-cv448.c - Check the Curve488 computation + * Copyright (C) 2019 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 . + * SPDX-License-Identifier: LGPL-2.1+ + */ + +#ifdef HAVE_CONFIG_H +#include +#endif +#include +#include +#include +#include +#include +#include + +#include "stopwatch.h" + +#define PGM "t-cv448" +#include "t-common.h" +#define N_TESTS 9 + + +static void +print_mpi (const char *text, gcry_mpi_t a) +{ + gcry_error_t err; + char *buf; + void *bufaddr = &buf; + + err = gcry_mpi_aprint (GCRYMPI_FMT_HEX, bufaddr, NULL, a); + if (err) + fprintf (stderr, "%s: [error printing number: %s]\n", + text, gpg_strerror (err)); + else + { + fprintf (stderr, "%s: %s\n", text, buf); + gcry_free (buf); + } +} + + +static void +show_note (const char *format, ...) +{ + va_list arg_ptr; + + if (!verbose && getenv ("srcdir")) + fputs (" ", stderr); /* To align above "PASS: ". */ + else + fprintf (stderr, "%s: ", PGM); + va_start (arg_ptr, format); + vfprintf (stderr, format, arg_ptr); + if (*format && format[strlen(format)-1] != '\n') + putc ('\n', stderr); + va_end (arg_ptr); +} + + +/* Convert STRING consisting of hex characters into its binary + representation and return it as an allocated buffer. The valid + length of the buffer is returned at R_LENGTH. The string is + delimited by end of string. The function returns NULL on + error. */ +static void * +hex2buffer (const char *string, size_t *r_length) +{ + const char *s; + unsigned char *buffer; + size_t length; + + buffer = xmalloc (strlen(string)/2+1); + length = 0; + for (s=string; *s; s +=2 ) + { + if (!hexdigitp (s) || !hexdigitp (s+1)) + return NULL; /* Invalid hex digits. */ + ((unsigned char*)buffer)[length++] = xtoi_2 (s); + } + *r_length = length; + return buffer; +} + +static void +reverse_buffer (unsigned char *buffer, unsigned int length) +{ + unsigned int tmp, i; + + for (i=0; i < length/2; i++) + { + tmp = buffer[i]; + buffer[i] = buffer[length-1-i]; + buffer[length-1-i] = tmp; + } +} + + +/* + * Test X448 functionality through higher layer crypto routines. + * + * Input: K (as hex string), U (as hex string), R (as hex string) + * + * where R is expected result of X448 (K, U). + * + */ +static void +test_cv_hl (int testno, const char *k_str, const char *u_str, + const char *result_str) +{ + gpg_error_t err; + void *buffer = NULL; + size_t buflen; + gcry_sexp_t s_pk = NULL; + gcry_mpi_t mpi_k = NULL; + gcry_sexp_t s_data = NULL; + gcry_sexp_t s_result = NULL; + gcry_sexp_t s_tmp = NULL; + unsigned char *res = NULL; + size_t res_len; + + if (verbose > 1) + info ("Running test %d\n", testno); + + if (!(buffer = hex2buffer (k_str, &buflen)) || buflen != 56) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "k", "invalid hex string"); + goto leave; + } + + reverse_buffer (buffer, buflen); + if ((err = gcry_mpi_scan (&mpi_k, GCRYMPI_FMT_USG, buffer, buflen, NULL))) + { + fail ("error converting MPI for test %d: %s", testno, gpg_strerror (err)); + goto leave; + } + + if ((err = gcry_sexp_build (&s_data, NULL, "%m", mpi_k))) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "data", gpg_strerror (err)); + goto leave; + } + + xfree (buffer); + if (!(buffer = hex2buffer (u_str, &buflen)) || buflen != 56) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "u", "invalid hex string"); + goto leave; + } + + /* + * The procedure of decodeUCoordinate will be done internally + * by _gcry_ecc_mont_decodepoint. So, we just put the little-endian + * binary to build S-exp. + * + * We could add the prefix 0x40, but libgcrypt also supports + * format with no prefix. So, it is OK not to put the prefix. + */ + if ((err = gcry_sexp_build (&s_pk, NULL, + "(public-key" + " (ecc" + " (curve \"Curve448\")" + " (flags djb-tweak)" + " (q%b)))", (int)buflen, buffer))) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "pk", gpg_strerror (err)); + goto leave; + } + + xfree (buffer); + buffer = NULL; + + if ((err = gcry_pk_encrypt (&s_result, s_data, s_pk))) + fail ("gcry_pk_encrypt failed for test %d: %s", testno, + gpg_strerror (err)); + + s_tmp = gcry_sexp_find_token (s_result, "s", 0); + if (!s_tmp || !(res = gcry_sexp_nth_buffer (s_tmp, 1, &res_len))) + fail ("gcry_pk_encrypt failed for test %d: %s", testno, "missing value"); + else + { + char *r, *r0; + int i; + + /* To skip the prefix 0x40, for-loop start with i=1 */ + r0 = r = xmalloc (2*(res_len)+1); + if (!r0) + { + fail ("memory allocation for test %d", testno); + goto leave; + } + + for (i=1; i < res_len; i++, r += 2) + snprintf (r, 3, "%02x", res[i]); + if (strcmp (result_str, r0)) + { + fail ("gcry_pk_encrypt failed for test %d: %s", + testno, "wrong value returned"); + info (" expected: '%s'", result_str); + info (" got: '%s'", r0); + } + xfree (r0); + } + + leave: + xfree (res); + gcry_mpi_release (mpi_k); + gcry_sexp_release (s_tmp); + gcry_sexp_release (s_result); + gcry_sexp_release (s_data); + gcry_sexp_release (s_pk); + xfree (buffer); +} + +/* + * Test X448 functionality through the API for X448. + * + * Input: K (as hex string), U (as hex string), R (as hex string) + * + * where R is expected result of X448 (K, U). + * + */ +static void +test_cv_x448 (int testno, const char *k_str, const char *u_str, + const char *result_str) +{ + gpg_error_t err; + void *scalar; + void *point = NULL; + size_t buflen; + unsigned char result[56]; + char result_hex[113]; + int i; + + if (verbose > 1) + info ("Running test %d\n", testno); + + if (!(scalar = hex2buffer (k_str, &buflen)) || buflen != 56) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "k", "invalid hex string"); + goto leave; + } + + if (!(point = hex2buffer (u_str, &buflen)) || buflen != 56) + { + fail ("error building s-exp for test %d, %s: %s", + testno, "u", "invalid hex string"); + goto leave; + } + + if ((err = gcry_ecc_mul_point (GCRY_ECC_CURVE448, result, scalar, point))) + fail ("gcry_ecc_mul_point failed for test %d: %s", testno, + gpg_strerror (err)); + + for (i=0; i < 56; i++) + snprintf (&result_hex[i*2], 3, "%02x", result[i]); + + if (strcmp (result_str, result_hex)) + { + fail ("gcry_ecc_mul_point failed for test %d: %s", + testno, "wrong value returned"); + info (" expected: '%s'", result_str); + info (" got: '%s'", result_hex); + } + + leave: + xfree (scalar); + xfree (point); +} + +static void +test_cv (int testno, const char *k_str, const char *u_str, + const char *result_str) +{ + test_cv_hl (testno, k_str, u_str, result_str); + test_cv_x448 (testno, k_str, u_str, result_str); +} + +/* + * Test iterative X448 computation through lower layer MPI routines. + * + * Input: K (as hex string), ITER, R (as hex string) + * + * where R is expected result of iterating X448 by ITER times. + * + */ +static void +test_it (int testno, const char *k_str, int iter, const char *result_str) +{ + gcry_ctx_t ctx; + gpg_error_t err; + void *buffer = NULL; + size_t buflen; + gcry_mpi_t mpi_k = NULL; + gcry_mpi_t mpi_x = NULL; + gcry_mpi_point_t P = NULL; + gcry_mpi_point_t Q; + int i; + gcry_mpi_t mpi_kk = NULL; + + if (verbose > 1) + info ("Running test %d: iteration=%d\n", testno, iter); + + gcry_mpi_ec_new (&ctx, NULL, "Curve448"); + Q = gcry_mpi_point_new (0); + + if (!(buffer = hex2buffer (k_str, &buflen)) || buflen != 56) + { + fail ("error scanning MPI for test %d, %s: %s", + testno, "k", "invalid hex string"); + goto leave; + } + reverse_buffer (buffer, buflen); + if ((err = gcry_mpi_scan (&mpi_x, GCRYMPI_FMT_USG, buffer, buflen, NULL))) + { + fail ("error scanning MPI for test %d, %s: %s", + testno, "x", gpg_strerror (err)); + goto leave; + } + + xfree (buffer); + buffer = NULL; + + P = gcry_mpi_point_set (NULL, mpi_x, NULL, GCRYMPI_CONST_ONE); + + mpi_k = gcry_mpi_copy (mpi_x); + if (debug) + print_mpi ("k", mpi_k); + + for (i = 0; i < iter; i++) + { + /* + * Another variant of decodeScalar448 thing. + */ + mpi_kk = gcry_mpi_set (mpi_kk, mpi_k); + gcry_mpi_set_bit (mpi_kk, 447); + gcry_mpi_clear_bit (mpi_kk, 0); + gcry_mpi_clear_bit (mpi_kk, 1); + + gcry_mpi_ec_mul (Q, mpi_kk, P, ctx); + + P = gcry_mpi_point_set (P, mpi_k, NULL, GCRYMPI_CONST_ONE); + gcry_mpi_ec_get_affine (mpi_k, NULL, Q, ctx); + + if (debug) + print_mpi ("k", mpi_k); + } + + { + unsigned char res[56]; + char *r, *r0; + + gcry_mpi_print (GCRYMPI_FMT_USG, res, 56, NULL, mpi_k); + reverse_buffer (res, 56); + + r0 = r = xmalloc (113); + if (!r0) + { + fail ("memory allocation for test %d", testno); + goto leave; + } + + for (i=0; i < 56; i++, r += 2) + snprintf (r, 3, "%02x", res[i]); + + if (strcmp (result_str, r0)) + { + fail ("X448 failed for test %d: %s", + testno, "wrong value returned"); + info (" expected: '%s'", result_str); + info (" got: '%s'", r0); + } + xfree (r0); + } + + leave: + gcry_mpi_release (mpi_kk); + gcry_mpi_release (mpi_k); + gcry_mpi_point_release (P); + gcry_mpi_release (mpi_x); + xfree (buffer); + gcry_mpi_point_release (Q); + gcry_ctx_release (ctx); +} + +/* + * X-coordinate of generator of the X448. + */ +#define G_X ("0500000000000000000000000000000000000000000000000000000000000000" \ + "000000000000000000000000000000000000000000000000") + +/* + * Test Diffie-Hellman in RFC-7748. + * + * Note that it's not like the ECDH of OpenPGP, where we use + * ephemeral public key. + */ +static void +test_dh (int testno, const char *a_priv_str, const char *a_pub_str, + const char *b_priv_str, const char *b_pub_str, + const char *result_str) +{ + /* Test A for private key corresponds to public key. */ + test_cv (testno, a_priv_str, G_X, a_pub_str); + /* Test B for private key corresponds to public key. */ + test_cv (testno, b_priv_str, G_X, b_pub_str); + /* Test DH with A's private key and B's public key. */ + test_cv (testno, a_priv_str, b_pub_str, result_str); + /* Test DH with B's private key and A's public key. */ + test_cv (testno, b_priv_str, a_pub_str, result_str); +} + + +static void +check_x448 (void) +{ + int ntests; + + info ("Checking X448.\n"); + + ntests = 0; + + /* + * Values are cited from RFC-7748: 5.2. Test Vectors. + * Following two tests are for the first type test. + */ + test_cv (1, + "3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121" + "700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3", + "06fce640fa3487bfda5f6cf2d5263f8aad88334cbd07437f020f08f9" + "814dc031ddbdc38c19c6da2583fa5429db94ada18aa7a7fb4ef8a086", + "ce3e4ff95a60dc6697da1db1d85e6afbdf79b50a2412d7546d5f239f" + "e14fbaadeb445fc66a01b0779d98223961111e21766282f73dd96b6f"); + ntests++; + test_cv (2, + "203d494428b8399352665ddca42f9de8fef600908e0d461cb021f8c5" + "38345dd77c3e4806e25f46d3315c44e0a5b4371282dd2c8d5be3095f", + "0fbcc2f993cd56d3305b0b7d9e55d4c1a8fb5dbb52f8e9a1e9b6201b" + "165d015894e56c4d3570bee52fe205e28a78b91cdfbde71ce8d157db", + "884a02576239ff7a2f2f63b2db6a9ff37047ac13568e1e30fe63c4a7" + "ad1b3ee3a5700df34321d62077e63633c575c1c954514e99da7c179d"); + ntests++; + + /* + * Additional test. Value is from second type test. + */ + test_cv (3, + G_X, + G_X, + "3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a" + "4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113"); + ntests++; + + /* + * Following two tests are for the second type test, + * with one iteration and 1,000 iterations. (1,000,000 iterations + * takes too long.) + */ + test_it (4, + G_X, + 1, + "3f482c8a9f19b01e6c46ee9711d9dc14fd4bf67af30765c2ae2b846a" + "4d23a8cd0db897086239492caf350b51f833868b9bc2b3bca9cf4113"); + ntests++; + + test_it (5, + G_X, + 1000, + "aa3b4749d55b9daf1e5b00288826c467274ce3ebbdd5c17b975e09d4" + "af6c67cf10d087202db88286e2b79fceea3ec353ef54faa26e219f38"); + ntests++; + + /* + * Last test is from: 6. Diffie-Hellman, 6.2. Curve448 + */ + test_dh (6, + /* Alice's private key, a */ + "9a8f4925d1519f5775cf46b04b5800d4ee9ee8bae8bc5565d498c28d" + "d9c9baf574a9419744897391006382a6f127ab1d9ac2d8c0a598726b", + /* Alice's public key, X448(a, 5) */ + "9b08f7cc31b7e3e67d22d5aea121074a273bd2b83de09c63faa73d2c" + "22c5d9bbc836647241d953d40c5b12da88120d53177f80e532c41fa0", + /* Bob's private key, b */ + "1c306a7ac2a0e2e0990b294470cba339e6453772b075811d8fad0d1d" + "6927c120bb5ee8972b0d3e21374c9c921b09d1b0366f10b65173992d", + /* Bob's public key, X448(b, 5) */ + "3eb7a829b0cd20f5bcfc0b599b6feccf6da4627107bdb0d4f345b430" + "27d8b972fc3e34fb4232a13ca706dcb57aec3dae07bdc1c67bf33609", + /* Their shared secret, K */ + "07fff4181ac6cc95ec1c16a94a0f74d12da232ce40a77552281d282b" + "b60c0b56fd2464c335543936521c24403085d59a449a5037514a879d"); + ntests++; + + /* three tests which results 0. */ + test_cv (7, + "3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121" + "700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3", + "00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000"); + ntests++; + + test_cv (8, + "3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121" + "700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3", + "01000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000", + "00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000"); + ntests++; + + test_cv (9, + "3d262fddf9ec8e88495266fea19a34d28882acef045104d0d1aae121" + "700a779c984c24f8cdd78fbff44943eba368f54b29259a4f1c600ad3", + "feffffffffffffffffffffffffffffffffffffffffffffffffffffff" + "feffffffffffffffffffffffffffffffffffffffffffffffffffffff", + "00000000000000000000000000000000000000000000000000000000" + "00000000000000000000000000000000000000000000000000000000"); + ntests++; + + if (ntests != N_TESTS) + fail ("did %d tests but expected %d", ntests, N_TESTS); + else if ((ntests % 256)) + show_note ("%d tests done\n", ntests); +} + + +int +main (int argc, char **argv) +{ + int last_argc = -1; + + if (argc) + { argc--; argv++; } + + while (argc && last_argc != argc ) + { + last_argc = argc; + if (!strcmp (*argv, "--")) + { + argc--; argv++; + break; + } + else if (!strcmp (*argv, "--help")) + { + fputs ("usage: " PGM " [options]\n" + "Options:\n" + " --verbose print timings etc.\n" + " --debug flyswatter\n", + stdout); + exit (0); + } + else if (!strcmp (*argv, "--verbose")) + { + verbose++; + argc--; argv++; + } + else if (!strcmp (*argv, "--debug")) + { + verbose += 2; + debug++; + argc--; argv++; + } + else if (!strncmp (*argv, "--", 2)) + die ("unknown option '%s'", *argv); + } + + xgcry_control ((GCRYCTL_DISABLE_SECMEM, 0)); + if (!gcry_check_version (GCRYPT_VERSION)) + die ("version mismatch\n"); + if (debug) + xgcry_control ((GCRYCTL_SET_DEBUG_FLAGS, 1u , 0)); + xgcry_control ((GCRYCTL_ENABLE_QUICK_RANDOM, 0)); + xgcry_control ((GCRYCTL_INITIALIZATION_FINISHED, 0)); + + start_timer (); + check_x448 (); + stop_timer (); + + info ("All tests completed in %s. Errors: %d\n", + elapsed_time (1), error_count); + return !!error_count; +}