ecc: Improve gcry_mpi_ec_curve_point
authorWerner Koch <wk@gnupg.org>
Tue, 5 Jun 2018 12:33:01 +0000 (14:33 +0200)
committerWerner Koch <wk@gnupg.org>
Wed, 6 Jun 2018 16:59:21 +0000 (18:59 +0200)
* 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.c
tests/t-mpi-point.c

index 2c396a7..97afbfe 100644 (file)
--- a/mpi/ec.c
+++ b/mpi/ec.c
@@ -1731,6 +1731,15 @@ _gcry_mpi_ec_curve_point (gcry_mpi_point_t point, mpi_ec_t ctx)
   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:
index 1eaa08a..f2378bf 100644 (file)
@@ -1045,6 +1045,271 @@ twistededwards_math (void)
 }
 
 
+/* Check the point on curve function.  */
+static void
+point_on_curve (void)
+{
+  static struct {
+    const char *curve;
+    int oncurve;      /* Point below is on the curve.  */
+    const char *qx;
+    const char *qy;
+  } t[] = {
+    {
+      "NIST P-256", 0,
+      "015B4F6775D68D4D2E2192C6B8027FC5A3D49957E453CB251155AA3FF5D3EC9974",
+      "4BC4C87B57A25E1056831208AB5B8F091142F891E9FF19F1E090B030DF1087B3"
+    }, {
+      "NIST P-256", 0,
+      "D22C316E7EBE7B293BD66808E000806F0754398A5D72A4F9BBC21C26EAC0A651",
+      "3C8DB80CC3CDE5E530D040536E6A58AAB41C33FA70B30896943513FF3690132D"
+    }, {
+      "NIST P-256", 0,
+      "0130F7E7BC52854CA493A0DE87DC4AB3B4343758F2B634F15B10D70DBC0A5A5291",
+      "86F9CA73C25CE86D54CB21C181AECBB52A5971334FF5040F76CAE9845ED46023"
+    }, {
+      "NIST P-256", 1,
+      "14957B602C7849F28858C7407696F014BC091D6D68C449560B7A38147D6E6A9B",
+      "A8E09EFEECFE00C797A0848F38B61992D30C61FAB13021E88C8BD3545B3A6C63"
+    }, {
+      "NIST P-256", 0,
+      "923DE4957241DD97780841C76294DB0D4F5DC04C3045081174764D2D32AD2D53",
+      "01B4B1A2027C02F0F520A3B01E4CE3C668BF481346A74499C5D1044A53E210B600"
+    }, {
+      "NIST P-256", 1,
+      "9021DFAB8B4DAEAADA634AAA26D6E5FFDF8C0476FF5CA31606C870A1B933FB36",
+      "9AFC65EEB24E46C7B75712EF29A981CB09FAC56E2B81D3ED024748CCAB1CB77E"
+    }, {
+      "NIST P-256", 0,
+      "011529F0B26DE5E0EB2DA4BFB6C149C802CB52EE479DD666553286928A4005E990",
+      "0EBC63DB2104884456DC0AA81A3F4E99D93B7AE2CD4B1489655EA9BE6289CF9E"
+    }, {
+      "NIST P-256", 1,
+      "216EC5DE8CA989199D31F0DFCD381DCC9270A0785365EC3E34CA347C070A87BE",
+      "87A88897BA763509ECC1DBE28D9D37F6F4E70E3B99B1CD3C0B934D4190968A6D"
+    }, {
+      "NIST P-256", 1,
+      "7ABAA44ACBC6016FDB52A6F45F6178E65CBFC35F9920D99149CA9999612CE945",
+      "88F7684BDCDA31EAFB6CAD859F8AB29B5D921D7DB2B34DF7E40CE36235F45B63"
+    }, {
+      "NIST P-256", 0,
+      "E765B4272D211DD0064189B55421FB76BB3A7756364A6CB1627FAED848157A84",
+      "C13171CFFB243E06B203F0996BBDD16F52292AD11F2DA81106E9C2FD87F4FA0F"
+    }, {
+      "NIST P-256", 0,
+      "EE4999DFC3A1871EE7A592BE26A09BEC9D9B561613EE9EFB6ED42F17985C9CDC",
+      "8399E967338A7A618336AF70DA67D9CAC1C19267809652F5C5183C8B129E0902"
+    }, {
+      "NIST P-256", 0,
+      "F755D0CF2642A2C7FBACCC8E9E442B8B047A99C6E052B2FA5AB0544B36B4D51C",
+      "AA080F17657B6565D9A4D94BD260B54D92FEE8DC4A78C4FC9C19209933AF39B0"
+    } , {
+      "NIST P-384", 0,
+      "CBFC7DBEBF15BEAD682549757F9BBA0E3F67669DF13FCE0EBE8024B725B38B00"
+      "83EC46A8F2FF3203C5C7F8C7E722A5EF",
+      "0548FE281BEAB18FD1AB86F59B0CA524479A4A81373C83B78AFFD801FAC75922"
+      "96470753DCF46173C9AA4A8A4C2FBE51"
+    }, {
+      "NIST P-384", 0,
+      "1DC8E054A883DB81EAEDE6C487B26816C927B8196780525A6CA8F675D2557752"
+      "02CE06CCBE705EA8A38AA2894D4BEEE6",
+      "010191050E867AFAA96A199FE9C591CF8B853D81486786DA889124881FB39D2F"
+      "8E0875F4C4BB1E3D0F8535C7A52306FB82"
+    }, {
+      "NIST P-384", 1,
+      "2539FC368CE1D5E464B6C0FBB12D557B712327DB086975255AD7D17F7E7E4F23"
+      "D719ED4116E2CC907AEB92CF22331A60",
+      "8843FDBA742CB64323E49CEBE8DD74908CFC9C3AA0015662DFBB7219E92CF32E"
+      "9FC63F61EF19DE9B3CEA98D163ABF254"
+    }, {
+      "NIST P-384", 0,
+      "0B786DACF400D43575394349EDD9F9CD145FC7EF737A3C5F69B253BE7639DB24"
+      "EC2F0CA62FF1F90B6515DE356EC2A404",
+      "225D6B2939CC7F7133F43353946A682C68DAC6BB75EE9CF6BD9A1609FA915692"
+      "72F4D3A87E88529754E109BB9B61B03B"
+    }, {
+      "NIST P-384", 0,
+      "76C660C9F58CF2051F9F8B06049694AB6FE418009DE6F0A0833BC690CEC06CC2"
+      "9A440AD51C94CF5BC28817C8C6E2D302",
+      "012974E5D9E55304ED294AB6C7A3C65B663E67ABC5E6F6C0F6498B519F2F6CA1"
+      "8306976291F3ADC0B5ABA42DED376EA9A5"
+    }, {
+      "NIST P-384", 0,
+      "23D758B1EDB8E12E9E707C53C131A19D9464B20EE05C99766F5ABDF9F906AD03"
+      "B958BF28B022E54E320672C4BAD4EEC0",
+      "01E9E72870C88F4C82A5AB3CC8A3398E8F006BF3EC05FFBB1EFF8AEE88020FEA"
+      "9E558E9F58ED1D324C9DCBCB4E8F2A5970"
+    }, {
+      "NIST P-384", 0,
+      "D062B96D5A10F715ACF361F99262ABF0F7693A8BB60ECB1DF459CF95750E4293"
+      "18BCB9FC60499D009F949298F3F9F47B",
+      "9089C6328E4B39A73D7EE6FAE1A77E48CE354B83BBCE432082C32C8FD6784B86"
+      "CFE9C552E2E720F5DA5806503D3784CD"
+    }, {
+      "NIST P-384", 0,
+      "2A951D4D6EB35C43D94866280D37365B82441BC84D62CBFF3365CAB1FD0A3E20"
+      "823CA8F84D2BBF4EA687885437DE7839",
+      "01CC7D762AFE613F7B5568BC516568A421159C40599E8D52DE10E8F9488931E1"
+      "69F3656C322DE45C4A70DC6DB9A661E599"
+    }, {
+      "NIST P-384", 1,
+      "A4BAEE6CDAF3AEB69032B3FBA811707C54F5753670DA5173D891547E8CBAEEF3"
+      "89B92C9A55573A596123415FBFA26991",
+      "3241EA716583C11C71BB30AF6C5E3A6637956F17ADBBE641BAB52E8539F9FC7B"
+      "F3B04F46DBFFE08151E0F0950CC70081"
+    }, {
+      "NIST P-384", 0,
+      "5C0E18B0DE3261BCBCFC7B702C2D75CF481336BFBADF420BADC616235C1966AB"
+      "4C0F876575DDEC1BDB3F3F04061C9AE4",
+      "E90C78550D1C922F1D8161D8C9C0576E29BD09CA665376FA887D13FA8DF48352"
+      "D7BBEEFB803F6CC8FC7895E47F348D33"
+    }, {
+      "NIST P-384", 1,
+      "2015864CD50F0A1A50E6401F44191665C19E4AD4B4903EA9EB464E95D1070E36"
+      "F1D8325E45734D5A0FDD103F4DF6F83E",
+      "5FB3E9A5C59DD5C5262A8176CB7032A00AE33AED08485884A3E5D68D9EEB990B"
+      "F26E8D87EC175577E782AD51A6A12C02"
+    }, {
+      "NIST P-384", 1,
+      "56EBF5310EEF5A5D8D001F570A18625383ECD4882B3FC738A69874E7C9D8F89C"
+      "187BECA23369DFD6C15CC0DA0629958F",
+      "C1230B349FB662CB762563DB8F9FCB32D5CCA16120681C474D67D279CCA6F6DB"
+      "73DE6AA96140B5C457B7486E06D318CE"
+    }, {
+      "NIST P-521", 0,
+      "01E4D82EE5CD6DA37080252295EFA273BBBA6952012D0120EAF131E73F1E5024"
+      "36E3324624471040030E1C345D65490ECEE9B64E03B15B6C7EB69A39C618BAFEED70",
+      "03EE3A3C88A6933B7B16016BE4CC4E3BF5EA0625CB3DB2604CDCBBD02CABBC90"
+      "8904D9DB42998F6C5101D4D4318ACFC9643C9CD641F636D1810ED86F1840EA74F3C0"
+    }, {
+      "NIST P-521", 0,
+      "01F3DFCB5433387B6B2E3F74177F4F3D7300F05E1AD49DE112630E27B1C8A437"
+      "1E742CB020E0039B5477FC897D17332034F9660B3066764EFF5FB440EB8856E782E3",
+      "02D337616C9D202DC5E290C486F5855CBD6A8470AE62CA96245834CF49257D8D"
+      "96D4041B15007650DEE668C00DDBF749054256C571F60980AC74D0DBCA7FB96C2F48"
+    }, {
+      "NIST P-521", 1,
+      "822A846606DC9E96452CAC373567A8B57D9ACA15B177F75DD7EF10C635F52CE4"
+      "EF6ABEEDB90D3F48F50A0C9015A95C955A25C45DE8413DE3BF899B6B1E62CF7CB8",
+      "0102771B5F3EC8C36838CEC04DCBC28AD1E38C37DAB0EA89B5EE92D21F7A35CE"
+      "ABC8B155EDC70154D6DFA2E77EC1D8C4A3406A6BD0ECF8F1EE2AC33A02464CB70C97"
+    }, {
+      "NIST P-521", 0,
+      "F733D48467912D1FFE46CF442F27FDD218D190E7B8A829D822DA3B6BAF9B987E"
+      "5B4BCCE34499248F59EEAF74F63ED15FF73F243C6FC3FD5E5842F6A3BA34C2022D",
+      "0281AAAD1B7EEBABEB6EC67932CB7E95717AFA3B4CF7A2DB151CD537C419C3A5"
+      "156ED9160758190B47696CDC15E81BBAD12975283907A571604DB23F702AEA4B38FF"
+    }, {
+      "NIST P-521", 0,
+      "03B1B274175AAEB5907152E5114CCAEADA28A7ADD4A2B1831C3D8302E8596489"
+      "E2C98B9B8D0CAE98C03BB11E28CE66D4736449758AF58BAFE40EF5A5FA22C9A43117",
+      "94C5951F81D544E959EDFC5DC1D5F42FE427871D4FB91A43A0B4A6BEA6B35B9E"
+      "BC5FB444C70BE4FD47B4ED16704F8C86EF019FC47C7FF2271F8B0DDEA9E2D3BCDD"
+    }, {
+      "NIST P-521", 1,
+      "F2248C318055DE37CD706D4FCAF7E7D96737A4A7B6B8067A66DCD58B6B8DFC55"
+      "90ECE67F6AA67F9C51B57E7B023075F2F42909BF47361CB6881C10F55FB7215B56",
+      "0162F735CE6A2ADA54CAF96A12D6888C02DE0A74638CF34CE39DABBACA4D651B"
+      "7E6ED1A65B551B36BAE7BE474BB6E6905ED0E33C7BA2021885027C7C6E40C5613004"
+    }, {
+      "NIST P-521", 0,
+      "9F08E97FEADCF0A391CA1EA4D97B5FE62D3B164593E12027EB967BD6E1FA841A"
+      "9831158DF164BCAD0BF3ADA96127745E25F349BDDD52EEA1654892B35960C9C023",
+      "AE2A25F5440F258AFACA6925C4C9F7AEAD3CB67153C4FACB31AC33F58B43A78C"
+      "B14F682FF726CEE2A6B6F6B481AEEB29A9B3150F02D1CFB764672BA8294C477291"
+    }, {
+      "NIST P-521", 0,
+      "01047B52014748C904980716953206A93F0D01B34CA94A997407FA93FE304F86"
+      "17BB6E402B2BB8B434C2671ECE953ABE7BADB75713CD9DF950943A33A9A19ACCDABE",
+      "7433533F098037DEA616337986887D01C5CC8DEC3DC1FDB9CDF7287EF27CC125"
+      "54FCF3A5E212DF9DAD9F8A3A7173B23FC6E15930704F3AEE1B074BDDB0ED6823E4"
+    }, {
+      "NIST P-521", 0,
+      "01C2A9EBF51592FE6589F618EAADA1697D9B2EC7CE5D48C9E80FC597642B23F1"
+      "F0EBE953449762BD3F094F57791D9850AFE98BBDA9872BE399B7BDD617860076BB03",
+      "0B822E27692F63DB8E12C59BB3CCA172B9BBF613CAE5F9D1474186E45E8B26FF"
+      "962084E1C6BE74821EDBB60941A3B75516F603719563433383812BFEA89EC14B89"
+    }, {
+      "NIST P-521", 0,
+      "99390F342C3F0D46E80C5B65C61E8AA8ACA0B6D4E1352404586364A05D8398E9"
+      "2BC71A644E8663F0A9B87D0B3ACAEE32F2AB9B321317AD23059D045EBAB91C5D93",
+      "82FCF93AE4467EB57766F2B150E736636727E7282500CD482DA70D153D195F2B"
+      "DF9B96D689A0DC1BB9137B41557A33F202F1B71840544CBEFF03072E77E4BB6F0B"
+    }, {
+      "NIST P-521", 1,
+      "018E48E80594FF5496D8CC7DF8A19D6AA18805A4EF4490038AED6A1E9AA18056"
+      "D0244A97DCF6D132C6804E3F4F369922119544B4C057D783C848FB798B48730A382C",
+      "01AF510B4F5E1C40BC9C110216D35E7C6D7A2BEE52914FC98258676288449901"
+      "F27A07EE91DF2D5D79259712906C3E18A990CBF35BCAC41A952820CE2BA8D0220080"
+    }, {
+      "NIST P-521", 1,
+      "ADCEF3539B4BC831DC0AFD173137A4426152058AFBAE06A17FCB89F4DB6E48B5"
+      "335CB88F8E4DB475A1E390E5656072F06605BFB84CBF9795B7992ECA04A8E10CA1",
+      "01BCB985AFD6404B9EDA49B6190AAA346BF7D5909CA440C0F7E505C62FAC8635"
+      "31D3EB7B2AC4DD4F4404E4B12E9D6D3C596179587F3724B1EFFF684CFDB4B21826B9"
+    }
+  };
+  gpg_error_t err;
+  int tidx;
+  const char *lastcurve = NULL;
+  gcry_ctx_t ctx = NULL;
+  gcry_mpi_t qx = NULL;
+  gcry_mpi_t qy = NULL;
+  gcry_mpi_point_t Q;
+  int oncurve;
+
+  wherestr = "point_on_curve";
+  for (tidx=0; tidx < DIM (t); tidx++)
+    {
+      if (!t[tidx].curve)
+        {
+          if (!lastcurve || !ctx)
+            die ("invalid test vectors at idx %d\n", tidx);
+        }
+      else if (!ctx || !lastcurve || strcmp (t[tidx].curve, lastcurve))
+        {
+          lastcurve = t[tidx].curve;
+          gcry_ctx_release (ctx);
+          err = gcry_mpi_ec_new (&ctx, NULL, lastcurve);
+          if (err)
+            die ("error creating context for curve %s at idx %d: %s\n",
+                 lastcurve, tidx, gpg_strerror (err));
+
+          info ("checking points on curve %s\n", lastcurve);
+        }
+
+      gcry_mpi_release (qx);
+      gcry_mpi_release (qy);
+      qx = hex2mpi (t[tidx].qx);
+      qy = hex2mpi (t[tidx].qy);
+
+      Q = gcry_mpi_point_set (NULL, qx, qy, GCRYMPI_CONST_ONE);
+      if (!Q)
+        die ("gcry_mpi_point_set(Q) failed at idx %d\n", tidx);
+
+      oncurve = gcry_mpi_ec_curve_point (Q, ctx);
+
+      if (t[tidx].oncurve && !oncurve)
+        {
+          fail ("point expected on curve but not identified as such (i=%d):\n",
+                tidx);
+          print_point ("  Q", Q);
+        }
+      else if (!t[tidx].oncurve && oncurve)
+        {
+          fail ("point not expected on curve but identified as such (i=%d):\n",
+                tidx);
+          print_point ("  Q", Q);
+        }
+      gcry_mpi_point_release (Q);
+    }
+
+  gcry_mpi_release (qx);
+  gcry_mpi_release (qy);
+  gcry_ctx_release (ctx);
+}
+
+
 int
 main (int argc, char **argv)
 {
@@ -1067,6 +1332,7 @@ main (int argc, char **argv)
   context_alloc ();
   context_param ();
   basic_ec_math ();
+  point_on_curve ();
 
   /* The tests are for P-192 and ed25519 which are not supported in
      FIPS mode.  */