summaryrefslogtreecommitdiff
path: root/mpi/ec.c
Commit message (Collapse)AuthorAgeFilesLines
* ec: add zSeries/s390x accelerated scalar multiplicationJussi Kivilinna2021-07-021-1/+9
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * cipher/asm-inline-s390x.h (PCC_FUNCTION_*): New. (pcc_query, pcc_scalar_multiply): New. * mpi/Makefile.am: Add 'ec-hw-s390x.c'. * mpi/ec-hw-s390x.c: New. * mpi/ec-internal.h (_gcry_s390x_ec_hw_mul_point) (mpi_ec_hw_mul_point): New. * mpi/ec.c (_gcry_mpi_ec_mul_point): Call 'mpi_ec_hw_mul_point'. * src/g10lib.h (HWF_S390X_MSA_9): New. * src/hwf-s390x.c (s390x_features): Add MSA9. * src/hwfeatures.c (hwflist): Add 's390x-msa-9'. -- Patch adds ECC scalar multiplication acceleration using s390x's PCC instruction. Following curves are supported: - Ed25519 - Ed448 - X25519 - X448 - NIST curves P-256, P-384 and P-521 Benchmark on z15 (5.2Ghz): Before: Ed25519 | nanosecs/iter cycles/iter mult | 389791 2026916 keygen | 572017 2974487 sign | 636603 3310336 verify | 1189097 6183305 = X25519 | nanosecs/iter cycles/iter mult | 296805 1543385 = Ed448 | nanosecs/iter cycles/iter mult | 1693373 8805541 keygen | 2382473 12388858 sign | 2609562 13569725 verify | 5177606 26923552 = X448 | nanosecs/iter cycles/iter mult | 1136178 5908127 = NIST-P256 | nanosecs/iter cycles/iter mult | 792620 4121625 keygen | 4627835 24064740 sign | 1528268 7946991 verify | 1678205 8726664 = NIST-P384 | nanosecs/iter cycles/iter mult | 1766418 9185373 keygen | 10158485 52824123 sign | 3341172 17374095 verify | 3694750 19212700 = NIST-P521 | nanosecs/iter cycles/iter mult | 3172566 16497346 keygen | 18184747 94560683 sign | 6039956 31407771 verify | 6480882 33700588 After: Ed25519 | nanosecs/iter cycles/iter speed-up mult | 25913 134746 15x keygen | 44447 231124 12x sign | 106928 556028 6x verify | 164681 856341 7x = X25519 | nanosecs/iter cycles/iter speed-up mult | 17761 92358 16x = Ed448 | nanosecs/iter cycles/iter speed-up mult | 50808 264199 33x keygen | 68644 356951 34x sign | 317446 1650720 8x verify | 457115 2376997 11x = X448 | nanosecs/iter cycles/iter speed-up mult | 35637 185313 31x = NIST-P256 | nanosecs/iter cycles/iter speed-up mult | 30678 159528 25x keygen | 323722 1683356 14x sign | 114176 593713 13x verify | 169901 883487 9x = NIST-P384 | nanosecs/iter cycles/iter speed-up mult | 59966 311822 29x keygen | 607778 3160445 16x sign | 209832 1091128 16x verify | 329506 1713431 11x = NIST-P521 | nanosecs/iter cycles/iter speed-up mult | 98230 510797 32x keygen | 1131686 5884765 16x sign | 397777 2068442 15x verify | 623076 3239998 10x Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi/ec: cache converted field_table MPIsJussi Kivilinna2021-07-011-6/+16
| | | | | | | | * mpi/ec.c (field_table_mpis): New. (ec_p_init): Cache converted field table MPIs. -- Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi_ec_get_affine: fast path for Z==1 caseJussi Kivilinna2021-07-011-0/+18
| | | | | | | | * mpi/ec.c (_gcry_mpi_ec_get_affine): Return X and Y as is if Z is 1 (for Weierstrass and Edwards curves). -- Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi/ec: add fast reduction for secp256k1Jussi Kivilinna2021-06-191-0/+62
| | | | | | | | | | | | | | | | | | | * mpi/ec.c (ec_secp256k1_mod): New. (field_table): Add 'secp256k1'. * tests/t-mpi-point.c (check_ec_mul): Add secp256k1 test vectors. -- Benchmark on Ryzen 7 5800X (x86_64): Before: secp256k1 | nanosecs/iter cycles/iter auto Mhz mult | 482336 2340443 4852 After (~20% faster): secp256k1 | nanosecs/iter cycles/iter auto Mhz mult | 392941 1906540 4852 Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi/ec: add fast reduction functions for NIST curvesJussi Kivilinna2021-06-191-16/+74
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * configure.ac (ASM_DISABLED): New. * mpi/Makefile.am: Add 'ec-nist.c' and 'ec-inline.h'. * mpi/ec-nist.c: New. * mpi/ec-inline.h: New. * mpi/ec-internal.h (_gcry_mpi_ec_nist192_mod) (_gcry_mpi_ec_nist224_mod, _gcry_mpi_ec_nist256_mod) (_gcry_mpi_ec_nist384_mod, _gcry_mpi_ec_nist521_mod): New. * mpi/ec.c (ec_addm, ec_subm, ec_mulm, ec_mul2): Use 'ctx->mod'. (field_table): Add 'mod' function; Add NIST reduction functions. (ec_p_init): Setup ctx->mod; Setup function pointers from field_table only if pointer is not NULL; Resize ctx->a and ctx->b only if set. * mpi/mpi-internal.h (RESIZE_AND_CLEAR_IF_NEEDED): New. * mpi/mpiutil.c (_gcry_mpi_resize): Clear all unused limbs also in realloc case. * src/ec-context.h (mpi_ec_ctx_s): Add 'mod' function. -- Benchmark on AMD Ryzen 7 5800X (x86_64): Before: NIST-P192 | nanosecs/iter cycles/iter auto Mhz mult | 283346 1369473 4833 keygen | 1688442 8185744 4848 sign | 549683 2662984 4845 verify | 615284 2984325 4850 = NIST-P224 | nanosecs/iter cycles/iter auto Mhz mult | 516443 2501173 4843 keygen | 2859746 13866802 4849 sign | 918472 4455043 4850 verify | 1057940 5131372 4850 = NIST-P256 | nanosecs/iter cycles/iter auto Mhz mult | 423536 2054040 4850 keygen | 2383097 11557572 4850 sign | 774346 3754243 4848 verify | 864934 4196315 4852 = NIST-P384 | nanosecs/iter cycles/iter auto Mhz mult | 929985 4511881 4852 keygen | 5230788 25367299 4850 sign | 1671432 8109726 4852 verify | 1902729 9228568 4850 = NIST-P521 | nanosecs/iter cycles/iter auto Mhz mult | 2123546 10300952 4851 keygen | 12019340 58297774 4850 sign | 3886988 18853054 4850 verify | 4507885 21864015 4850 After: NIST-P192 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 186679 905603 4851 +51% keygen | 1161423 5623822 4842 +46% sign | 389531 1887557 4846 +41% verify | 412936 2000461 4844 +49% = NIST-P224 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 260621 1256327 4821 +99% keygen | 1557845 7531677 4835 +84% sign | 521678 2527083 4844 +76% verify | 554084 2677949 4833 +92% = NIST-P256 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 319045 1542061 4833 +33% keygen | 1834822 8898950 4850 +30% sign | 612866 2972630 4850 +26% verify | 664821 3222597 4847 +30% = NIST-P384 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 593894 2875260 4841 +57% keygen | 3526600 17089717 4846 +48% sign | 1178098 5710151 4847 +42% verify | 1260185 6107449 4846 +51% = NIST-P521 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 1160220 5621946 4846 +83% keygen | 6862975 33247351 4844 +75%´ sign | 2287366 11096711 4851 +70% verify | 2455858 11888045 4841 +84% Benchmark on AMD Ryzen 7 5800X (i386): Before: NIST-P192 | nanosecs/iter cycles/iter auto Mhz mult | 648039 3143236 4850 keygen | 3554452 17244822 4852 sign | 1163173 5641932 4850 verify | 1300076 6305673 4850 = NIST-P224 | nanosecs/iter cycles/iter auto Mhz mult | 798607 3874405 4851 keygen | 4657604 22589864 4850 sign | 1515803 7352049 4850 verify | 1635470 7935373 4852 = NIST-P256 | nanosecs/iter cycles/iter auto Mhz mult | 927033 4496283 4850 keygen | 5313601 25771983 4850 sign | 1735795 8418514 4850 verify | 1945804 9438212 4851 = NIST-P384 | nanosecs/iter cycles/iter auto Mhz mult | 2301781 11164473 4850 keygen | 12856001 62353242 4850 sign | 4161041 20180651 4850 verify | 4705961 22827478 4851 = NIST-P521 | nanosecs/iter cycles/iter auto Mhz mult | 6066635 29422721 4850 keygen | 32995868 160046407 4850 sign | 10503306 50945387 4850 verify | 12225252 59294323 4850 After: NIST-P192 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 413605 2007498 4854 +57% keygen | 2479429 12010926 4844 +44% sign | 825111 3997147 4844 +41% verify | 890206 4318723 4851 +46% = NIST-P224 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 551703 2676454 4851 +45% keygen | 3257022 15781844 4845 +43% sign | 1085678 5258894 4844 +40% verify | 1172195 5678499 4844 +40% = NIST-P256 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 720395 3497486 4855 +29% keygen | 4217758 20461257 4851 +26% sign | 1404350 6814131 4852 +24% verify | 1515136 7353955 4854 +28% = NIST-P384 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 1525742 7400771 4851 +51% keygen | 9046660 43877889 4850 +42% sign | 2974641 14408703 4844 +40% verify | 3265285 15834951 4849 +44% = NIST-P521 | nanosecs/iter cycles/iter auto Mhz speed-up mult | 3289348 15968678 4855 +84% keygen | 19354174 93873531 4850 +70% sign | 6351493 30830140 4854 +65% verify | 6979292 33854215 4851 +75% Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi/ec: small optimization for ec_mulm_448Jussi Kivilinna2021-06-191-54/+22
| | | | | | | | | | | | | | | | | | | | | | | | | * mpi/ec.c (ec_addm_448, ec_subm_448): Change order of sub_n and set_cond to remove need to clear 'n'. (ec_mulm_448): Use memcpy where possible; Use mpih_rshift where possible; Use mpih_lshift for doubling a3; Remove one addition at end. -- Benchmarks on AMD Ryzen 7 5800X: Before: Ed448 | nanosecs/iter cycles/iter auto Mhz keygen | 893096 4343326 4863 sign | 988422 4795694 4852 verify | 1899706 9215952 4851 After (~5% faster): Ed448 | nanosecs/iter cycles/iter auto Mhz keygen | 822078 3987952 4851 sign | 947327 4595433 4851 verify | 1776259 8616675 4851 Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* mpi/ec: small optimization for ec_mulm_25519Jussi Kivilinna2021-06-191-29/+12
| | | | | | | | | | | | | | | | | | | | | | | | | * mpi/ec.c (ec_addm_25519): Remove one addition. (ec_subm_25519): Change order of add_n and set_cond to remove need to clear 'n'. (ec_mulm_25519): Avoid extra memory copies; Use _gcry_mpih_addmul_1 for multiplying by 19 and adding; Remove one addition at end. -- Benchmarks on AMD Ryzen 7 5800X: Before: Ed25519 | nanosecs/iter cycles/iter auto Mhz keygen | 304980 1478913 4849 sign | 328657 1589657 4837 verify | 625133 3032355 4851 After (~22% faster): Ed25519 | nanosecs/iter cycles/iter auto Mhz keygen | 244288 1184862 4850 sign | 267831 1298934 4850 verify | 504745 2449106 4852 Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* ecc: Fix the regression of gcry_mpi_ec_add.NIIBE Yutaka2021-03-301-12/+12
| | | | | | | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_point_resize): Export the routine for internal use. (add_points_edwards, _gcry_mpi_ec_mul_point): Use mpi_point_resize. * src/gcrypt-int.h (_gcry_mpi_ec_point_resize): Declare. * src/visibility.c (gcry_mpi_ec_dup, gcry_mpi_ec_add): Make sure for the size of limb before calling the internal functions. (gcry_mpi_ec_sub): Likewise. -- GnuPG-bug-id: 5372 Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Support reading EC point in compressed format for good curves.NIIBE Yutaka2020-07-141-2/+2
| | | | | | | | | | | | | | | | * cipher/ecc-curves.c (gcry_ecc_get_curve): Handle G, differently. * cipher/ecc-misc.c (_gcry_ecc_sec_decodepoint): Support compressed representation of EC point. Rename from _gcry_ecc_os2ec. * cipher/ecc-sm2.c (_gcry_ecc_sm2_decrypt) Follow the change. * cipher/ecc.c (ecc_decrypt_raw): Likewise. * mpi/ec.c (_gcry_mpi_ec_set_point): Likewise. * src/ec-context.h: API change _gcry_ecc_sec_decodepoint from _gcry_ecc_os2ec. * tests/basic.c (check_pubkey): Use compressed representation for two public keys of NIST P192 and NIST P256. GnuPG-bug-id: 4951 Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Support Ed448 in decoding point.NIIBE Yutaka2020-06-161-1/+4
| | | | | | | | | | * cipher/ecc-eddsa.c (ecc_ed448_recover_x): New. (_gcry_ecc_eddsa_recover_x): Support Ed448. (_gcry_ecc_eddsa_decodepoint): Support Ed448. * mpi/ec.c (_gcry_mpi_ec_decode_point): For Ed448, use _gcry_ecc_eddsa_decodepoint. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* mpih: Expose const-time MPI helper functions.NIIBE Yutaka2020-04-161-14/+0
| | | | | | | | | | | * mpi/Makefile.am (libmpi_la_SOURCES): Add mpih-const-time.c. * mpi/ec.c (mpih_set_cond): Move to mpih-const-time.c. * mpi/mpi-internal.h: Add macros and declarations. * mpi/mpi-inv.c (mpih_add_n_cond): Likewise. (mpih_sub_n_cond, mpih_swap_cond, mpih_abs_cond): Likewise. * mpi/mpih-const-time.c: New. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Remove hard-coded value for ECC_DIALECT_ED25519.NIIBE Yutaka2020-04-141-4/+1
| | | | | | | | | | | | | * mpi/ec.c (ec_p_init): Remove special handling for Ed25519. * cipher/ecc-eddsa.c (_gcry_ecc_eddsa_encodepoint): Fix assumption ec->nbits is 256 for EdDSA. (_gcry_ecc_eddsa_decodepoint): Likewise. (_gcry_ecc_eddsa_verify): Likewise. -- GnuPG-bug-id: 4914 Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ec: fix left shift overflows on WIN64 buildJussi Kivilinna2019-11-051-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * mpi/ec.c (ec_mulm_448): Cast constants to (mpi_limb_t) before shifting left by 32. -- Patch fixes following warnings: .../libgcrypt/mpi/ec.c: In function 'ec_mulm_448': .../libgcrypt/mpi/ec.c:563:35: warning: left shift count >= width of type [-Wshift-count-overflow] 563 | b0[LIMB_SIZE_HALF_448-1] &= (1UL<<32)-1; | ^~ .../libgcrypt/mpi/ec.c:564:35: warning: left shift count >= width of type [-Wshift-count-overflow] 564 | a2[LIMB_SIZE_HALF_448-1] &= (1UL<<32)-1; | ^~ .../libgcrypt/mpi/ec.c:576:29: warning: left shift count >= width of type [-Wshift-count-overflow] 576 | b1_rest = b1v & ((1UL <<32)-1); | ^~ .../libgcrypt/mpi/ec.c:577:29: warning: left shift count >= width of type [-Wshift-count-overflow] 577 | a3_rest = a3v & ((1UL <<32)-1); | ^~ .../libgcrypt/mpi/ec.c:586:37: warning: left shift count >= width of type [-Wshift-count-overflow] 586 | wp[LIMB_SIZE_HALF_448-1] &= ((1UL <<32)-1); | ^~ .../libgcrypt/mpi/ec.c:603:29: warning: left shift count >= width of type [-Wshift-count-overflow] 603 | b1_rest = b1v & ((1UL <<32)-1); | ^~ Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* ecc: Add Curve for X448 with ECC_DIALECT_SAFECURVE.NIIBE Yutaka2019-10-281-5/+205
| | | | | | | | | | | | | | | | | | | | | | | | | | | * cipher/ecc-curves.c (domain_parms): Add X448. * cipher/ecc-ecdh.c (_gcry_ecc_mul_point): Support X448. * mpi/ec.c (ec_addm_448, ec_subm_448, ec_mulm_448): New. (ec_mul2_448, ec_pow2_448): New. (field_table): Add for X448. (curve448_bad_points): New. (bad_points_table): New. (ec_p_init): Use bad_points_table. * tests/Makefile.am (t-x448): Add. * tests/curves.c (N_CURVES): Update. * tests/t-x448.c: New. -- Note that it uses new practice of ECC_DIALECT_SAFECURVE (that is: native for the algorithm; fixed-size and little-endian) for its point representation and secret representation. It uses new practice in public key, secret key, and ephemeral key in ECDH. In future, when it will be applied to EdDSA, it will use new practice also in "s" (integer) in signature, as well as "r" (point) in signature. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Make _gcry_mpi_ec_mul_point friendly to X25519 computation.NIIBE Yutaka2019-10-251-0/+30
| | | | | | | | * mpi/ec.c (_gcry_mpi_ec_mul_point): Support scalar input as an opaque MPI in little-endian native format. * cipher/ecc-ecdh.c (_gcry_ecc_mul_point): Use an opaque scalar. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Simply use unsigned int for cofactor, not MPI.NIIBE Yutaka2019-10-211-1/+0
| | | | | | | | | | | | | | | | | | | | | | | * cipher/ecc-common.h (elliptic_curve_t): Use unsigned int for H. * src/ec-context.h (struct mpi_ec_ctx_s): Ditto. * cipher/ecc-curves.c (ecc_domain_parms_t): Ditto. (domain_parms): Update for the cofactors. (_gcry_ecc_fill_in_curve): H is no longer MPI, but unsigned int. (_gcry_ecc_get_curve): Remove handling for H. (_gcry_mpi_ec_new): In KEYPARM, cofactor is still MPI. (_gcry_ecc_get_param_sexp): H is no longer MPI, but unsigned int. (_gcry_ecc_get_mpi): Keep the API, returning MPI for "h". (_gcry_ecc_set_mpi): Likewise. * cipher/ecc-ecdh.c (_gcry_ecc_mul_point): Fix for unsigned int. * cipher/ecc-eddsa.c (_gcry_ecc_eddsa_genkey): Likewise. * cipher/ecc-misc.c (_gcry_ecc_curve_free): Likewise. * cipher/ecc.c (nist_generate_key, test_ecdh_only_keys): Likewise. (test_ecdh_only_keys, ecc_generate, ecc_check_secret_key): Likewise. (ecc_sign, ecc_verify, ecc_encrypt_raw, ecc_decrypt_raw): Likewise. (_gcry_pk_ecc_get_sexp): Likewise. * mpi/ec.c (ec_deinit): Likewise. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Add mitigation against timing attack.NIIBE Yutaka2019-08-071-1/+5
| | | | | | | | | | * cipher/ecc-ecdsa.c (_gcry_ecc_ecdsa_sign): Add the order N to K. * mpi/ec.c (_gcry_mpi_ec_mul_point): Compute with NBITS of P or larger. CVE-id: CVE-2019-13627 GnuPG-bug-id: 4626 Co-authored-by: Ján Jančár <johny@neuromancer.sk> Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Improve gcry_mpi_ec_curve_pointWerner Koch2018-06-061-0/+9
| | | | | | | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_curve_point): Check range of coordinates. * tests/t-mpi-point.c (point_on_curve): New. -- Due to the conversion to affine coordinates we didn't detected points with values >= P. The solution here might not be the best according to the NIST standard (it is done there at an earlier opportunity) but it reliably detects points we do not expect to receive. The new test vectors have been compared against gnutls/nettle. Reported-by: Stephan Müller Signed-off-by: Werner Koch <wk@gnupg.org>
* mpi/ec: fix when 'unsigned long' is 32-bit but limb size is 64-bitJussi Kivilinna2018-01-091-4/+4
| | | | | | | | | | | * mpi/ec.c (ec_addm_25519, ec_subm_25519, ec_mulm_25519): Cast '1' to mpi_limb_t before left shift. -- Patch fixes mpi/ec.c compiler warnings and failing tests cases on Win64. Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
* ecc: Fix scratch MPI.NIIBE Yutaka2017-08-291-1/+1
| | | | | | * mpi/ec.c (ec_p_init): Check if scratch MPI is allocated. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Fix ec_mulm_25519.NIIBE Yutaka2017-08-291-5/+2
| | | | | | * mpi/ec.c (ec_mulm_25519): Improve reduction to 25519. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Use 25519 method also for ed25519.NIIBE Yutaka2017-08-291-68/+86
| | | | | | | | | | | | | * cipher/ecc-curves.c (_gcry_ecc_fill_in_curve): Don't use mpi_add since it resizes to have more limbs. * mpi/ec.c (point_resize): Fix for Edwards curve. (ec_p_init): Support Edwards curve. (_gcry_mpi_ec_get_affine): Use the methods. (dup_point_edwards, add_points_edwards, sub_points_edwards): Ditto. (_gcry_mpi_ec_mul_point): Resize MPIs of point to fixed size. (_gcry_mpi_ec_curve_point): Use the methods. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Clean up curve specific method support.NIIBE Yutaka2017-08-291-11/+1
| | | | | | | | * src/ec-context.h (struct mpi_ec_ctx_s): Remove MOD method. * mpi/ec.c (ec_mod_25519): Remove. (ec_p_init): Follow the removal of the MOD method. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Relax condition for 25519 computations.NIIBE Yutaka2017-08-291-3/+3
| | | | | | | * mpi/ec.c (ec_addm_25519, ec_subm_25519, ec_mulm_25519): Check number of limbs, allocated more is OK. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Fix ec_mulm_25519.NIIBE Yutaka2017-08-291-0/+5
| | | | | | * mpi/ec.c (ec_mulm_25519): Fix the cases of 0 to 18. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: field specific routines for 25519.NIIBE Yutaka2017-08-291-13/+211
| | | | | | | | | | * mpi/ec.c (point_resize): Improve for X25519. (mpih_set_cond): New. (ec_mod_25519, ec_addm_25519, ec_subm_25519, ec_mulm_25519) (ec_mul2_25519, ec_pow2_25519): New. (ec_p_init): Fill by FIELD_TABLE. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Add field specific computation methods.NIIBE Yutaka2017-08-291-18/+25
| | | | | | | | * src/ec-context.h (struct mpi_ec_ctx_s): Add methods. * mpi/ec.c (ec_p_init): Initialize the default methods. (montgomery_ladder): Use the methods. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Add input validation for X25519.NIIBE Yutaka2017-08-271-3/+48
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | * cipher/ecc.c (ecc_decrypt_raw): Add input validation. * mpi/ec.c (ec_p_init): Use scratch buffer for bad points. (_gcry_mpi_ec_bad_point): New. -- Following is the paper describing the attack: May the Fourth Be With You: A Microarchitectural Side Channel Attack on Real-World Applications of Curve25519 by Daniel Genkin, Luke Valenta, and Yuval Yarom In the current implementation, we do output checking and it results an error for those bad points. However, when attacked, the computation will done with leak of private key, even it will results errors. To mitigate leak, we added input validation. Note that we only list bad points with MSB=0. By X25519, MSB is always cleared. In future, we should implement constant-time field computation. Then, this input validation could be removed, if performance is important and we are sure for no leak. CVE-id: CVE-2017-0379 Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* api: New function gcry_mpi_point_copy.Werner Koch2017-07-181-0/+14
| | | | | | | | | | | * src/gcrypt.h.in (gcry_mpi_point_copy): New. (mpi_point_copy): New macro. * src/visibility.c (gcry_mpi_point_copy): New. * src/libgcrypt.def, src/libgcrypt.vers: Add function. * mpi/ec.c (_gcry_mpi_point_copy): New. * tests/t-mpi-point.c (set_get_point): Add test. Signed-off-by: Werner Koch <wk@gnupg.org>
* doc: Comment fixesWerner Koch2017-05-231-1/+6
|
* Spelling fixes in docs and comments.NIIBE Yutaka2017-04-281-1/+1
| | | | | | | | -- GnuPG-bug-id: 3120 Reported-by: ka7 (klemens) Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Positive values in computation.NIIBE Yutaka2016-04-061-15/+6
| | | | | | | | | | | | | | | | | | | | | | | * cipher/ecc-curves.c (_gcry_ecc_fill_in_curve): Make sure coefficients A and B are positive. * cipher/ecc-eddsa.c (_gcry_ecc_eddsa_recover_x): For negation, do "P - T" instead of "-T", so that the result will be positive. (_gcry_ecc_eddsa_verify): Likewise. * cipher/ecc.c (ecc_check_secret_key): Use _gcry_ecc_fill_in_curve instead of _gcry_ecc_update_curve_param. * mpi/ec.c (ec_subm): Make sure the result will be positive. (dup_point_edwards, sub_points_edwards, _gcry_mpi_ec_curve_point): Use mpi_sub instead of mpi_neg. (add_points_edwards): Simply use ec_addm. * tests/t-mpi-point.c (test_curve): Define curves with positive coefficients. -- We keep the coefficients of domain_parms in ecc-curves.c, so that keygrip computations won't change. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Fix memory leaks on error.NIIBE Yutaka2016-02-101-4/+7
| | | | | | | | | * cipher/ecc.c (ecc_decrypt_raw): Go to leave to release memory. * mpi/ec.c (_gcry_mpi_ec_curve_point): Likewise. -- Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: New API function gcry_mpi_ec_decode_point.Werner Koch2016-01-281-0/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_decode_point): New. * cipher/ecc-common.h: Move two prototypes to ... * src/ec-context.h: here. * src/gcrypt.h.in (gcry_mpi_ec_decode_point): New. * src/libgcrypt.def (gcry_mpi_ec_decode_point): New. * src/libgcrypt.vers (gcry_mpi_ec_decode_point): New. * src/visibility.c (gcry_mpi_ec_decode_point): New. * src/visibility.h: Add new function. -- This new function make the use of the gcry_mpi_ec_curve_point function possible in many contexts. Here is a code snippet which could be used in gpg to check a point: static gpg_error_t check_point (PKT_public_key *pk, gcry_mpi_t m_point) { gpg_error_t err; char *curve; gcry_ctx_t gctx = NULL; gcry_mpi_point_t point = NULL; /* Get the curve name from the first OpenPGP key parameter. */ curve = openpgp_oid_to_str (pk->pkey[0]); if (!curve) { err = gpg_error_from_syserror (); goto leave; } point = gcry_mpi_point_new (0); if (!point) { err = gpg_error_from_syserror (); goto leave; } err = gcry_mpi_ec_new (&gctx, NULL, curve); if (err) goto leave; err = gcry_mpi_ec_decode_point (point, m_point, gctx); if (err) goto leave; if (!gcry_mpi_ec_curve_point (point, gctx)) err = gpg_error (GPG_ERR_BAD_DATA); leave: gcry_ctx_release (gctx); gcry_mpi_point_release (point); xfree (curve); return err; } Signed-off-by: Werner Koch <wk@gnupg.org>
* ecc: minor improvement of point multiplication.NIIBE Yutaka2015-11-261-3/+4
| | | | * mpi/ec.c (_gcry_mpi_ec_mul_point): Move ec_subm out of the loop.
* ecc: Constant-time multiplication for Weierstrass curve.NIIBE Yutaka2015-11-251-4/+15
| | | | | * mpi/ec.c (_gcry_mpi_ec_mul_point): Use simple left-to-right binary method for Weierstrass curve when SCALAR is secure.
* ecc: multiplication of Edwards curve to be constant-time.NIIBE Yutaka2015-11-251-2/+3
| | | | | | | | * mpi/ec.c (_gcry_mpi_ec_mul_point): Use point_swap_cond. -- Reported-by: Taylor R Campbell.
* ecc: Add point_resize and point_swap_cond.NIIBE Yutaka2015-11-251-16/+35
| | | | | | | | | * mpi/ec.c (point_resize, point_swap_cond): New. (_gcry_mpi_ec_mul_point): Use point_resize and point_swap_cond. -- Thanks to Taylor R Campbell who suggests.
* ecc: fix Montgomery curve bugs.NIIBE Yutaka2015-08-101-1/+1
| | | | | | * cipher/ecc.c (check_secret_key): Y1 should not be NULL when check. (ecc_check_secret_key): Support Montgomery curve. * mpi/ec.c (_gcry_mpi_ec_curve_point): Fix condition.
* ecc: Improve Montgomery curve implementation.NIIBE Yutaka2014-11-191-16/+27
| | | | | | | | | | | * cipher/ecc-curves.c (_gcry_ecc_fill_in_curve): Support MPI_EC_MONTGOMERY. * cipher/ecc.c (test_ecdh_only_keys): New. (nist_generate_key): Call test_ecdh_only_keys for MPI_EC_MONTGOMERY. (check_secret_key): Handle Montgomery curve of x-coordinate only. * mpi/ec.c (_gcry_mpi_ec_mul_point): Resize points before the loop. Simplify, using pointers of Q1, Q2, PRD, and SUM. --
* mpi: Add gcry_mpi_ec_sub.Markus Teich2014-10-081-0/+65
| | | | | | | | | | | | | | | | | | | | * NEWS (gcry_mpi_ec_sub): New. * doc/gcrypt.texi (gcry_mpi_ec_sub): New. * mpi/ec.c (_gcry_mpi_ec_sub, sub_points_edwards): New. (sub_points_montgomery, sub_points_weierstrass): New stubs. * src/gcrypt-int.h (_gcry_mpi_ec_sub): New. * src/gcrypt.h.in (gcry_mpi_ec_sub): New. * src/libgcrypt.def (gcry_mpi_ec_sub): New. * src/libgcrypt.vers (gcry_mpi_ec_sub): New. * src/mpi.h (_gcry_mpi_ec_sub_points): New. * src/visibility.c (gcry_mpi_ec_sub): New. * src/visibility.h (gcry_mpi_ec_sub): New. -- This function subtracts two points on the curve. Only Twisted Edwards curves are supported with this change. Signed-off-by: Markus Teich <markus dot teich at stusta dot mhn dot de>
* ecc: Support Montgomery curve for gcry_mpi_ec_mul_point.NIIBE Yutaka2014-08-121-8/+139
| | | | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_get_affine): Support Montgomery curve. (montgomery_ladder): New. (_gcry_mpi_ec_mul_point): Implemention using montgomery_ladder. (_gcry_mpi_ec_curve_point): Check x-coordinate is valid. -- Given Montgomery curve: b * y^2 == x^3 + a * x^2 + x CTX->A has (a-2)/4 and CTX->B has b^-1 Note that _gcry_mpi_ec_add_points is not supported for this curve.
* ecc: Add cofactor to domain parameters.NIIBE Yutaka2014-08-081-0/+1
| | | | | | | | | | | | | | | | | | | | | | | | | | | | * src/ec-context.h (mpi_ec_ctx_s): Add cofactor 'h'. * cipher/ecc-common.h (elliptic_curve_t): Add cofactor 'h'. (_gcry_ecc_update_curve_param): New API adding cofactor. * cipher/ecc-curves.c (ecc_domain_parms_t): Add cofactor 'h'. (ecc_domain_parms_t domain_parms): Add cofactors. (_gcry_ecc_fill_in_curve, _gcry_ecc_update_curve_param) (_gcry_ecc_get_curve, _gcry_mpi_ec_new, _gcry_ecc_get_param_sexp) (_gcry_ecc_get_mpi): Handle cofactor. * cipher/ecc-eddsa.c (_gcry_ecc_eddsa_genkey): Likewise. * cipher/ecc-misc.c (_gcry_ecc_curve_free) (_gcry_ecc_curve_copy): Likewise. * cipher/ecc.c (nist_generate_key, ecc_generate) (ecc_check_secret_key, ecc_sign, ecc_verify, ecc_encrypt_raw) (ecc_decrypt_raw, _gcry_pk_ecc_get_sexp, _gcry_pubkey_spec_ecc): Likewise. (compute_keygrip): Handle cofactor, but skip it for its computation. * mpi/ec.c (ec_deinit): Likewise. * tests/t-mpi-point.c (context_param): Likewise. (test_curve): Add cofactors. * tests/curves.c (sample_key_1, sample_key_2): Add cofactors. * tests/keygrip.c (key_grips): Add cofactors. -- We keep compatibility of compute_keygrip in cipher/ecc.c.
* ecc: Fix _gcry_mpi_ec_p_new to allow secp256k1.NIIBE Yutaka2014-01-151-1/+1
| | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_p_new): Remove checking a!=0. * tests/t-mpi-point.c (context_alloc): Remove two spurious tests. -- It is no problem when a==0. Signed-off-by: NIIBE Yutaka <gniibe@fsij.org>
* ecc: Make a macro shorter.Werner Koch2014-01-131-11/+11
| | | | | | | | | | | * src/mpi.h (MPI_EC_TWISTEDEDWARDS): Rename to MPI_EC_EDWARDS. CHnage all users. * cipher/ecc-curves.c (domain_parms): Add parameters for Curve3617 as comment. * mpi/ec.c (dup_point_twistededwards): Rename to dup_point_edwards. (add_points_twistededwards): Rename to add_points_edwards. Signed-off-by: Werner Koch <wk@gnupg.org>
* Remove macro hacks for internal vs. external functions. Part 2 and last.Werner Koch2013-12-121-5/+5
| | | | | | | | | | | | | | | | | | | * src/visibility.h: Remove remaining define/undef hacks for symbol visibility. Add macros to detect the use of the public functions. Change all affected functions by replacing them by the x-macros. * src/g10lib.h: Add internal prototypes. (xtrymalloc, xtrycalloc, xtrymalloc_secure, xtrycalloc_secure) (xtryrealloc, xtrystrdup, xmalloc, xcalloc, xmalloc_secure) (xcalloc_secure, xrealloc, xstrdup, xfree): New macros. -- The use of xmalloc/xtrymalloc/xfree is a more common pattern than the gcry_free etc. functions. Those functions behave like those defined by C and thus for better readability we use these macros and not the underscore prefixed functions. Signed-off-by: Werner Koch <wk@gnupg.org>
* Remove macro hacks for internal vs. external functions. Part 1.Werner Koch2013-12-051-25/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | * src/visibility.h: Remove almost all define/undef hacks for symbol visibility. Add macros to detect the use of the public functions. Change all affected functions by prefixing them explicitly with an underscore and change all internal callers to call the underscore prefixed versions. Provide convenience macros from sexp and mpi functions. * src/visibility.c: Change all functions to use only gpg_err_code_t and translate to gpg_error_t only in visibility.c. -- The use of the macro magic made if hard to follow the function calls in the source. It was not easy to see if an internal or external function (as defined by visibility.c) was called. The change is quite large but hopefully makes Libgcrypt easier to maintain. Some function have not yet been fixed; this will be done soon. Because Libgcrypt does no make use of any other libgpg-error using libraries it is useless to always translate between gpg_error_t and gpg_err_code_t (i.e with and w/o error source identifier). This translation has no mostly be moved to the function wrappers in visibility.c. An additional advantage of using gpg_err_code_t is that comparison can be done without using gpg_err_code(). I am sorry for that large patch, but a series of patches would actually be more work to audit. Signed-off-by: Werner Koch <wk@gnupg.org>
* ecc: Use constant time point operation for Twisted Edwards.Werner Koch2013-12-021-4/+23
| | | | | | | | * mpi/ec.c (_gcry_mpi_ec_mul_point): Try to do a constant time operation if needed. * tests/benchmark.c (main): Add option --use-secmem. Signed-off-by: Werner Koch <wk@gnupg.org>
* ecc: Fix gcry_mpi_ec_curve_point for Weierstrass.Werner Koch2013-12-021-10/+18
| | | | | | | | | | | * mpi/ec.c (_gcry_mpi_ec_curve_point): Use correct equation. (ec_pow3): New. (ec_p_init): Always copy B. -- The code path was obviously never tested. Signed-off-by: Werner Koch <wk@gnupg.org>
* ecc: Fully implement Ed25519 compression in ECDSA mode.Werner Koch2013-11-051-2/+6
| | | | | | | | | | | * src/ec-context.h (mpi_ec_ctx_s): Add field FLAGS. * mpi/ec.c (ec_p_init): Add arg FLAGS. Change all callers to pass it. * cipher/ecc-curves.c (point_from_keyparam): Add arg EC, parse as opaque mpi and use eddsa decoding depending on the flag. (_gcry_mpi_ec_new): Rearrange to parse Q and D after knowing the curve. Signed-off-by: Werner Koch <wk@gnupg.org>
View Lorry Controller Status