add ec_p256k1
authorNIIBE Yutaka <gniibe@fsij.org>
Wed, 19 Feb 2014 05:51:09 +0000 (14:51 +0900)
committerNIIBE Yutaka <gniibe@fsij.org>
Wed, 19 Feb 2014 05:51:09 +0000 (14:51 +0900)
ChangeLog
src/ec_p256k1.c [new file with mode: 0644]
src/ec_p256k1.h [new file with mode: 0644]
src/ec_p256r1.c
src/ecc.c [new file with mode: 0644]
src/field-group-select.h [new file with mode: 0644]
src/jpc.c
tool/calc_precompute_table_ecc.py [new file with mode: 0644]

index 658178f..e1a2c89 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,12 @@
+2014-02-19  Niibe Yutaka  <gniibe@fsij.org>
+
+       * tool/calc_precompute_table_ecc.py: New.
+
+       * src/ec_p256k1.c: New.  Use ecc.c.
+       * src/ec_p256k1.h: New.
+       * src/ec_p256r1.c: Use ecc.c.
+       * src/ecc.c: New.
+
 2014-02-18  Niibe Yutaka  <gniibe@fsij.org>
 
        * src/jpc_p256k1.c: New.  Use jpc.c.
diff --git a/src/ec_p256k1.c b/src/ec_p256k1.c
new file mode 100644 (file)
index 0000000..a8b690d
--- /dev/null
@@ -0,0 +1,223 @@
+/*                                                    -*- coding: utf-8 -*-
+ * ec_p256k1.c - Elliptic curve over GF(p256k1)
+ *
+ * Copyright (C) 2014 Free Software Initiative of Japan
+ * Author: NIIBE Yutaka <gniibe@fsij.org>
+ *
+ * This file is a part of Gnuk, a GnuPG USB Token implementation.
+ *
+ * Gnuk is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Gnuk 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 General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include "bn.h"
+#include "modp256k1.h"
+#include "jpc-ac_p256k1.h"
+#include "mod.h"
+#include "ec_p256k1.h"
+
+#define FIELD p256k1
+
+/*
+ * a = 0, b = 7
+ */
+static const bn256 coefficient_a[1] = {
+  {{ 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 }}
+};
+
+static const bn256 coefficient_b[1] = {
+  {{ 0x7, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0 }}
+};
+
+
+static const ac precomputed_KG[15] = {
+  {
+    {{{ 0x16f81798, 0x59f2815b, 0x2dce28d9, 0x029bfcdb,
+       0xce870b07, 0x55a06295, 0xf9dcbbac, 0x79be667e }}},
+    {{{ 0xfb10d4b8, 0x9c47d08f, 0xa6855419, 0xfd17b448,
+       0x0e1108a8, 0x5da4fbfc, 0x26a3c465, 0x483ada77 }}}
+  }, {
+    {{{ 0x42d0e6bd, 0x13b7e0e7, 0xdb0f5e53, 0xf774d163,
+       0x104d6ecb, 0x82a2147c, 0x243c4e25, 0x3322d401 }}},
+    {{{ 0x6c28b2a0, 0x24f3a2e9, 0xa2873af6, 0x2805f63e,
+       0x4ddaf9b7, 0xbfb019bc, 0xe9664ef5, 0x56e70797 }}}
+  }, {
+    {{{ 0x829d122a, 0xdca81127, 0x67e99549, 0x8f17f314,
+       0x6a8a9e73, 0x9b889085, 0x846dd99d, 0x583fdfd9 }}},
+    {{{ 0x63c4eac4, 0xf3c7719e, 0xb734b37a, 0xb44685a3,
+       0x572a47a6, 0x9f92d2d6, 0x2ff57d81, 0xabc6232f }}}
+  }, {
+    {{{ 0x9ec4c0da, 0x1b7b444c, 0x723ea335, 0xe88c5678,
+       0x981f162e, 0x9239c1ad, 0xf63b5f33, 0x8f68b9d2 }}},
+    {{{ 0x501fff82, 0xf23cbf79, 0x95510bfd, 0xbbea2cfe,
+       0xb6be215d, 0xde1d90c2, 0xba063986, 0x662a9f2d }}}
+  }, {
+    {{{ 0x114cbf09, 0x63c5e885, 0x7be77e3e, 0x2f27ce93,
+       0xf54a3e33, 0xdaa6d12d, 0x3eff872c, 0x8b300e51 }}},
+    {{{ 0xb3b10a39, 0x26c6ff28, 0x9aaf7169, 0x08f6a7aa,
+       0x6b8238ea, 0x446f0d46, 0x7f43c0cc, 0x1cec3067 }}}
+  }, {
+    {{{ 0x075e9070, 0xba16ce6a, 0x9b5cfe37, 0xbc26893d,
+       0x9c510774, 0xe1ddadfe, 0xfe3ae2f4, 0x90922d88 }}},
+    {{{ 0x5c08824a, 0x653943cc, 0xfce8f4bc, 0x06d74475,
+       0x533c615d, 0x8d101fa7, 0x742108a9, 0x7b1903f6 }}}
+  }, {
+    {{{ 0x6ebdc96c, 0x1bcfa45c, 0x1c7584ba, 0xe400bc04,
+       0x74cf531f, 0x6395e20e, 0xc5131b30, 0x1edd0bb1 }}},
+    {{{ 0xe358cf9e, 0xa117161b, 0x2724d11c, 0xe490d6f0,
+       0xee6dd8c9, 0xf75062f6, 0xfba373e4, 0x31e03b2b }}}
+  }, {
+    {{{ 0x2120e2b3, 0x7f3b58fa, 0x7f47f9aa, 0x7a58fdce,
+       0x4ce6e521, 0xe7be4ae3, 0x1f51bdba, 0xeaa649f2 }}},
+    {{{ 0xba5ad93d, 0xd47a5305, 0xf13f7e59, 0x01a6b965,
+       0x9879aa5a, 0xc69a80f8, 0x5bbbb03a, 0xbe3279ed }}}
+  }, {
+    {{{ 0x27bb4d71, 0xcf291a33, 0x33524832, 0x6caf7d6b,
+       0x766584ee, 0x6e0ee131, 0xd064c589, 0x160cb0f6 }}},
+    {{{ 0x17136e8d, 0x9d5de554, 0x1aab720e, 0xe3f2d468,
+       0xccf75cc2, 0xd1378b49, 0xc4ff16e1, 0x6920c375 }}}
+  }, {
+    {{{ 0x1a9ee611, 0x3eef9e96, 0x9cc37faf, 0xfe4d7bf3,
+       0xb321d965, 0x462aa9b3, 0x208736c5, 0x1702da3e }}},
+    {{{ 0x3a545ceb, 0xfba57bbf, 0x7ea858f5, 0x6dbcd766,
+       0x680d92f1, 0x088e897c, 0xbc626c80, 0x468c1fd8 }}}
+  }, {
+    {{{ 0xb188660a, 0xb40f85c7, 0x99bc3c36, 0xc5873c19,
+       0x7f33b54c, 0x3c7b4541, 0x1f8c9bf8, 0x4cd3a93c }}},
+    {{{ 0x33099cb0, 0xf8dce380, 0x2edd2f33, 0x7a167dd6,
+       0x0ffe35b7, 0x576d8987, 0xc68ace5c, 0xd2de0386 }}}
+  }, {
+    {{{ 0x6658bb08, 0x9a9e0a72, 0xc589607b, 0xe23c5f2a,
+       0xf2bfb4c8, 0xa048ca14, 0xc62c2291, 0x4d9a0f89 }}},
+    {{{ 0x0f827294, 0x427b5f31, 0x9f2c35cd, 0x1ea7a8b5,
+       0x85a3c00f, 0x95442e56, 0x9b57975a, 0x8cb83121 }}}
+  }, {
+    {{{ 0x51f5cf67, 0x4333f0da, 0xf4f0d3cb, 0x6d3ea47c,
+       0xa05a831f, 0x442fda14, 0x016d3e81, 0x6a496013 }}},
+    {{{ 0xe52e0f48, 0xf647318c, 0x4a0d5ff1, 0x5ff3a66e,
+       0x61199ba8, 0x046ed81a, 0x3e79c23a, 0x578edf08 }}}
+  }, {
+    {{{ 0x3ea01ea7, 0xb8f996f8, 0x7497bb15, 0xc0045d33,
+       0x6205647c, 0xc4749dc9, 0x0efd22c9, 0xd8946054 }}},
+    {{{ 0x12774ad5, 0x062dcb09, 0x8be06e3a, 0xcb13f310,
+       0x235de1a9, 0xca281d35, 0x69c3645c, 0xaf8a7412 }}}
+  }, {
+    {{{ 0xbeb8b1e2, 0x8808ca5f, 0xea0dda76, 0x0262b204,
+       0xddeb356b, 0xb6fffffc, 0xfbb83870, 0x52de253a }}},
+    {{{ 0x8f8d21ea, 0x961f40c0, 0x002f03ed, 0x89686278,
+       0x38e421ea, 0x0ff834d7, 0xd36fb8db, 0x3a270d6f }}}
+  }
+};
+
+static const ac precomputed_2E_KG[15] = {
+  {
+    {{{ 0x39a48db0, 0xefd7835b, 0x9b3c03bf, 0x9f1215a2,
+       0x9b7bde45, 0x2791d0a0, 0x696e7167, 0x100f44da }}},
+    {{{ 0x2bc65a09, 0x0fbd5cd6, 0xff5195ac, 0xb7ff4a18,
+       0x0c090666, 0x2ec8f330, 0x92a00b77, 0xcdd9e131 }}}
+  }, {
+    {{{ 0x40fb27b6, 0x32427e28, 0xbe430576, 0xc76e3db2,
+       0x61686aa5, 0x10f238ad, 0xbe778b1b, 0xfea74e3d }}},
+    {{{ 0xf23cb96f, 0x701d3db7, 0x973f7b77, 0x126b596b,
+       0xccb6af93, 0x7cf674de, 0x9b0b1329, 0x6e0568db }}}
+  }, {
+    {{{ 0x2c8118bc, 0x6cac5154, 0x399ddd98, 0x19bd4b34,
+       0x2e9c8949, 0x47248a8d, 0x2cefa3b1, 0x734cb6a8 }}},
+    {{{ 0x1e410fd5, 0xf1b340ad, 0xc4873539, 0xa2982bee,
+       0xd4de4530, 0x7b5a3ea4, 0x42202574, 0xae46e10e }}}
+  }, {
+    {{{ 0xac1f98cd, 0xcbfc99c8, 0x4d7f0308, 0x52348905,
+       0x1cc66021, 0xfaed8a9c, 0x4a474870, 0x9c3919a8 }}},
+    {{{ 0xd4fc599d, 0xbe7e5e03, 0x6c64c8e6, 0x905326f7,
+       0xf260e641, 0x584f044b, 0x4a4ddd57, 0xddb84f0f }}}
+  }, {
+    {{{ 0xed7cebed, 0xc4aacaa8, 0x4fae424e, 0xb75d2dce,
+       0xba20735e, 0xa01585a2, 0xba122399, 0x3d75f24b }}},
+    {{{ 0xd5570dce, 0xcbe4606f, 0x2da192c2, 0x9d00bfd7,
+       0xa57b7265, 0x9c3ce86b, 0xec4edf5e, 0x987a22f1 }}}
+  }, {
+    {{{ 0x73ea0665, 0x211b9715, 0xf3a1abbb, 0x86f485d4,
+       0xcd076f0e, 0xabd242d8, 0x0ba5dc88, 0x862332ab }}},
+    {{{ 0x7b784911, 0x09af505c, 0xcaf4fae7, 0xc89544e8,
+       0xae9a32eb, 0x256625f6, 0x606d1a3f, 0xe2532b72 }}}
+  }, {
+    {{{ 0x0deaf885, 0x79e9f313, 0x46df21c9, 0x938ff76e,
+       0xa953bb2c, 0x1968f5fb, 0x29155f27, 0xdff538bf }}},
+    {{{ 0x31d5d020, 0xf7bae0b1, 0x1a676a8d, 0x5afdc787,
+       0xfa9d53ff, 0x11b4f032, 0xc5959167, 0x86ba433e }}}
+  }, {
+    {{{ 0x9475b7ba, 0x884fdff0, 0xe4918b3d, 0xe039e730,
+       0xf5018cdb, 0x3d3e57ed, 0x1943785c, 0x95939698 }}},
+    {{{ 0x7524f2fd, 0xe9b8abf8, 0xc8709385, 0x9c653f64,
+       0x4b9cd684, 0x8ba0386a, 0x88c331dd, 0x2e7e5528 }}}
+  }, {
+    {{{ 0xeefe79e5, 0x940bef53, 0xbe9b87f3, 0xc518d286,
+       0x7833042c, 0x9e0c7c76, 0x11fbe152, 0x104e2cb5 }}},
+    {{{ 0x50bbec83, 0xc0d35e0f, 0x4acd0fcc, 0xee4879be,
+       0x006085ee, 0xc8d80f5d, 0x72fe1ac1, 0x3c51bc1c }}}
+  }, {
+    {{{ 0xb2de976e, 0x06187f61, 0xf5e4b4b6, 0x52869e18,
+       0x38d332ca, 0x74d4facd, 0xb3a2f8d9, 0x5c1c90b4 }}},
+    {{{ 0xdaa37893, 0x98644d09, 0xabe39818, 0x682435a8,
+       0x469c53a0, 0x17e46617, 0x77dc2e64, 0x642f9632 }}}
+  }, {
+    {{{ 0x222f6c54, 0xad2101c5, 0xfa74785e, 0xb05c7a58,
+       0x489bcdaf, 0xce55fa79, 0xffe88d54, 0xc1f920fd }}},
+    {{{ 0x9065e490, 0x32553ab0, 0x35329f74, 0x7611b9af,
+       0xab7b24c0, 0x57df19ef, 0x6181c447, 0xb9a78749 }}}
+  }, {
+    {{{ 0xa80b7ea8, 0x392f156f, 0x8ae4a8bf, 0x57ab7ca0,
+       0x50c4b178, 0xac320747, 0x0e781feb, 0x146041b9 }}},
+    {{{ 0x845279b2, 0xd343f075, 0x7387afa5, 0x2d4fe757,
+       0xa72f3c39, 0x151e0948, 0x550da168, 0x41a6d54e }}}
+  }, {
+    {{{ 0x075a0010, 0xb3134ed3, 0x7ae93e23, 0x9fa76f4b,
+       0x7bb4daaa, 0xc0db256f, 0x464dd8a3, 0x7668dc27 }}},
+    {{{ 0x9f5da977, 0x150063f5, 0x05efce00, 0x3acac5c8,
+       0x884493fe, 0xc8e12ffc, 0x88f06bd2, 0x4ab936d8 }}}
+  }, {
+    {{{ 0x5d09ea98, 0x996fde77, 0x4145da58, 0x16ddf512,
+       0xdc2fb225, 0xa97a6ca8, 0xfbdcdf5a, 0xc7331f30 }}},
+    {{{ 0x86a86e52, 0x838f99e0, 0x77795edd, 0x68d39b29,
+       0x9f412aaa, 0xe4e4f97e, 0x30d25352, 0xe5cc2c0a }}}
+  }, {
+    {{{ 0x9c21ff71, 0xb3d68650, 0xddbe3884, 0x11e7589d,
+       0x423bac67, 0x7efd4055, 0x46957425, 0x587a7293 }}},
+    {{{ 0x8f5a8fc6, 0x360adc2e, 0xbd69f12e, 0x6f8bbafb,
+       0x0a3f3b4d, 0xf671f423, 0x59942dc3, 0xb49acb47 }}}
+  }
+};
+
+/*
+ * N: order of G
+ *    0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
+ */
+static const bn256 N[1] = {
+  {{ 0xd0364141, 0xbfd25e8c, 0xaf48a03b, 0xbaaedce6,
+     0xfffffffe, 0xffffffff, 0xffffffff, 0xffffffff }}
+};
+
+/*
+ * MU = 2^512 / N
+ * MU = ( (1 << 256) | MU_lower )
+ */
+static const bn256 MU_lower[1] = {
+  {{ 0x2fc9bec0, 0x402da173, 0x50b75fc4, 0x45512319,
+     0x1, 0x0, 0x0, 0x0 }}
+};
+
+
+#include "ecc.c"
diff --git a/src/ec_p256k1.h b/src/ec_p256k1.h
new file mode 100644 (file)
index 0000000..d2893ac
--- /dev/null
@@ -0,0 +1,4 @@
+int compute_kP_p256k1 (ac *X, const bn256 *K, const ac *P);
+
+int compute_kG_p256k1 (ac *X, const bn256 *K);
+void ecdsa_p256k1 (bn256 *r, bn256 *s, const bn256 *z, const bn256 *d);
index 3b4b397..c77dcaf 100644 (file)
@@ -1,7 +1,7 @@
 /*                                                    -*- coding: utf-8 -*-
  * ec_p256r1.c - Elliptic curve over GF(p256r1)
  *
- * Copyright (C) 2011, 2013, 2014 Free Software Initiative of Japan
+ * Copyright (C) 2014 Free Software Initiative of Japan
  * Author: NIIBE Yutaka <gniibe@fsij.org>
  *
  * This file is a part of Gnuk, a GnuPG USB Token implementation.
  *
  */
 
-/*
- * References:
- *
- * [1] Suite B Implementer's Guide to FIPS 186-3 (ECDSA), February 3, 2010.
- *
- * [2] Michael Brown, Darrel Hankerson, Julio López, and Alfred Menezes,
- *     Software Implementation of the NIST Elliptic Curves Over Prime Fields,
- *     Proceedings of the 2001 Conference on Topics in Cryptology: The
- *     Cryptographer's Track at RSA
- *     Pages 250-265, Springer-Verlag London, UK, 2001
- *     ISBN:3-540-41898-9
- *
- * [3] Mustapha Hedabou, Pierre Pinel, Lucien Bénéteau, 
- *     A comb method to render ECC resistant against Side Channel Attacks,
- *     2004
- */
-
 #include <stdint.h>
 #include <string.h>
 #include "bn.h"
 #include "mod.h"
 #include "ec_p256r1.h"
 
+#define FIELD p256r1
+
 /*
- * a = -3 mod p256
+ * a = -3 mod p256r1
  */
 static const bn256 coefficient_a[1] = {
   {{  0xfffffffc, 0xffffffff, 0xffffffff, 0x00000000,
@@ -60,13 +45,6 @@ static const bn256 coefficient_b[1] = {
 };
 
 
-/*
- * w = 4
- * m = 256
- * d = 64
- * e = 32
- */
-
 static const ac precomputed_KG[15] = {
   {
     {{{ 0xd898c296, 0xf4a13945, 0x2deb33a0, 0x77037d81,
@@ -225,115 +203,6 @@ static const ac precomputed_2E_KG[15] = {
   }
 };
 
-
-#if TEST
-/*
- * Generator of Elliptic curve over GF(p256)
- */
-const ac *G = &precomputed_KG[0];
-#endif
-
-
-static int
-get_vk (const bn256 *K, int i)
-{
-  uint32_t w0, w1, w2, w3;
-
-  if (i < 32)
-    {
-      w3 = K->word[6]; w2 = K->word[4]; w1 = K->word[2]; w0 = K->word[0];
-    }
-  else
-    {
-      w3 = K->word[7]; w2 = K->word[5]; w1 = K->word[3]; w0 = K->word[1];
-      i -= 32;
-    }
-
-  w3 >>= i;  w2 >>= i;  w1 >>= i;  w0 >>= i;
-  return ((w3 & 1) << 3) | ((w2 & 1) << 2) | ((w1 & 1) << 1) | (w0 & 1);
-}
-
-
-/**
- * @brief      X  = k * G
- *
- * @param K    scalar k
- *
- * Return -1 on error.
- * Return 0 on success.
- */
-int
-compute_kG_p256r1 (ac *X, const bn256 *K)
-{
-  uint8_t index[64]; /* Lower 4-bit for index absolute value, msb is
-                       for sign (encoded as: 0 means 1, 1 means -1).  */
-  bn256 K_dash[1];
-  jpc Q[1], tmp[1], *dst;
-  int i;
-  int vk;
-  uint32_t k_is_even = bn256_is_even (K);
-
-  bn256_sub_uint (K_dash, K, k_is_even);
-  /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
-
-  /* Fill index.  */
-  vk = get_vk (K_dash, 0);
-  for (i = 1; i < 64; i++)
-    {
-      int vk_next, is_zero;
-
-      vk_next = get_vk (K_dash, i);
-      is_zero = (vk_next == 0);
-      index[i-1] = (vk - 1) | (is_zero << 7);
-      vk = (is_zero ? vk : vk_next);
-    }
-  index[63] = vk - 1;
-
-  memset (Q->z, 0, sizeof (bn256)); /* infinity */
-  for (i = 31; i >= 0; i--)
-    {
-      jpc_double_p256r1 (Q, Q);
-
-      jpc_add_ac_signed_p256r1 (Q, Q, &precomputed_KG[index[i]&0x0f],
-                               index[i] >> 7);
-      jpc_add_ac_signed_p256r1 (Q, Q, &precomputed_2E_KG[index[i+32]&0x0f],
-                               index[i+32] >> 7);
-    }
-
-  dst = k_is_even ? Q : tmp;
-  jpc_add_ac_p256r1 (dst, Q, &precomputed_KG[0]);
-
-  return jpc_to_ac_p256r1 (X, Q);
-}
-
-
-
-/**
- * check if P is on the curve.
- *
- * Return -1 on error.
- * Return 0 on success.
- */
-static int
-point_is_on_the_curve (const ac *P)
-{
-  bn256 s[1], t[1];
-
-  /* Elliptic curve: y^2 = x^3 + a*x + b */
-  modp256r1_sqr (s, P->x);
-  modp256r1_mul (s, s, P->x);
-
-  modp256r1_mul (t, coefficient_a, P->x);
-  modp256r1_add (s, s, t);
-  modp256r1_add (s, s, coefficient_b);
-
-  modp256r1_sqr (t, P->y);
-  if (bn256_cmp (s, t) == 0)
-    return 0;
-  else
-    return -1;
-}
-
 /*
  * N: order of G
  */
@@ -342,141 +211,6 @@ static const bn256 N[1] = {
      0xffffffff, 0xffffffff, 0x00000000, 0xffffffff }}
 };
 
-
-static int
-get_vk_kP (const bn256 *K, int i)
-{
-  uint32_t w;
-  uint8_t blk = i/32;
-  uint8_t pos = i%32;
-  uint8_t col = 3*(pos % 11) + (pos >= 11) + (pos >= 22);
-  uint8_t word_index = (blk * 3) + (pos / 11);
-
-  w = ((K->word[word_index] >> col) & 7);
-  if (word_index < 7 && (pos == 10 || pos == 21))
-    {
-      uint8_t mask;
-      uint8_t shift;
-
-      word_index++;
-      if (pos == 10)
-       {
-         shift = 2;
-         mask = 4;
-       }
-      else
-       {
-         shift = 1;
-         mask = 6;
-       }
-
-      w |= ((K->word[word_index] << shift) & mask);
-    }
-
-  return w;
-}
-
-/**
- * @brief      X  = k * P
- *
- * @param K    scalar k
- * @param P    P in affine coordiate
- *
- * Return -1 on error.
- * Return 0 on success.
- *
- * For the curve (cofactor is 1 and n is prime), possible error cases are:
- *
- *     P is not on the curve.
- *     P = G, k = n
- *     Something wrong in the code.
- *
- * Mathmatically, k=1 and P=O is another possible case, but O cannot be
- * represented by affine coordinate.
- */
-int
-compute_kP_p256r1 (ac *X, const bn256 *K, const ac *P)
-{
-  uint8_t index[86]; /* Lower 2-bit for index absolute value, msb is
-                       for sign (encoded as: 0 means 1, 1 means -1).  */
-  bn256 K_dash[1];
-  uint32_t k_is_even = bn256_is_even (K);
-  jpc Q[1], tmp[1], *dst;
-  int i;
-  int vk;
-  ac P3[1], P5[1], P7[1];
-  const ac *p_Pi[4];
-
-  if (point_is_on_the_curve (P) < 0)
-    return -1;
-
-  if (bn256_sub (K_dash, K, N) == 0)   /* >= N, it's too big.  */
-    return -1;
-
-  bn256_sub_uint (K_dash, K, k_is_even);
-  /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
-
-  p_Pi[0] = P;
-  p_Pi[1] = P3;
-  p_Pi[2] = P5;
-  p_Pi[3] = P7;
-
-  {
-    jpc Q1[1];
-
-    memcpy (Q->x, P->x, sizeof (bn256));
-    memcpy (Q->y, P->y, sizeof (bn256));
-    memset (Q->z, 0, sizeof (bn256));
-    Q->z->word[0] = 1;
-
-    jpc_double_p256r1 (Q, Q);
-    jpc_add_ac_p256r1 (Q1, Q, P);
-    if (jpc_to_ac_p256r1 (P3, Q1) < 0) /* Never occurs, except coding errors.  */
-      return -1;
-    jpc_double_p256r1 (Q, Q);
-    jpc_add_ac_p256r1 (Q1, Q, P);
-    if (jpc_to_ac_p256r1 (P5, Q1) < 0) /* Never occurs, except coding errors.  */
-      return -1;
-
-    memcpy (Q->x, P3->x, sizeof (bn256));
-    memcpy (Q->y, P3->y, sizeof (bn256));
-    memset (Q->z, 0, sizeof (bn256));
-    Q->z->word[0] = 1;
-    jpc_double_p256r1 (Q, Q);
-    jpc_add_ac_p256r1 (Q1, Q, P);
-    if (jpc_to_ac_p256r1 (P7, Q1) < 0) /* Never occurs, except coding errors.  */
-      return -1;
-  }
-
-  /* Fill index.  */
-  vk = get_vk_kP (K_dash, 0);
-  for (i = 1; i < 86; i++)
-    {
-      int vk_next, is_even;
-
-      vk_next = get_vk_kP (K_dash, i);
-      is_even = ((vk_next & 1) == 0);
-      index[i-1] = (is_even << 7) | ((is_even?7-vk:vk-1) >> 1);
-      vk = vk_next + is_even;
-    }
-  index[85] = ((vk - 1) >> 1);
-
-  memset (Q->z, 0, sizeof (bn256)); /* infinity */
-  for (i = 85; i >= 0; i--)
-    {
-      jpc_double_p256r1 (Q, Q);
-      jpc_double_p256r1 (Q, Q);
-      jpc_double_p256r1 (Q, Q);
-      jpc_add_ac_signed_p256r1 (Q, Q, p_Pi[index[i]&0x03], index[i] >> 7);
-    }
-
-  dst = k_is_even ? Q : tmp;
-  jpc_add_ac_p256r1 (dst, Q, &precomputed_KG[0]);
-
-  return jpc_to_ac_p256r1 (X, Q);
-}
-
-
 /*
  * MU = 2^512 / N
  * MU = ( (1 << 256) | MU_lower )
@@ -487,52 +221,4 @@ static const bn256 MU_lower[1] = {
 };
 
 
-/**
- * @brief Compute signature (r,s) of hash string z with secret key d
- */
-void
-ecdsa_p256r1 (bn256 *r, bn256 *s, const bn256 *z, const bn256 *d)
-{
-  bn256 k[1];
-  ac KG[1];
-  bn512 tmp[1];
-  bn256 k_inv[1];
-  uint32_t carry;
-#define borrow carry
-#define tmp_k k_inv
-
-  do
-    {
-      do
-       {
-         bn256_random (k);
-         if (bn256_add_uint (k, k, 1))
-           continue;
-         if (bn256_sub (tmp_k, k, N) == 0)     /* >= N, it's too big.  */
-           continue;
-         /* 1 <= k <= N - 1 */
-         compute_kG_p256r1 (KG, k);
-         borrow = bn256_sub (r, KG->x, N);
-         if (borrow)
-           memcpy (r, KG->x, sizeof (bn256));
-         else
-           memcpy (KG->x, r, sizeof (bn256));
-       }
-      while (bn256_is_zero (r));
-
-      mod_inv (k_inv, k, N);
-      bn256_mul (tmp, r, d);
-      mod_reduce (s, tmp, N, MU_lower);
-      carry = bn256_add (s, s, z);
-      if (carry)
-       bn256_sub (s, s, N);
-      else
-       bn256_sub ((bn256 *)tmp, s, N);
-      bn256_mul (tmp, s, k_inv);
-      mod_reduce (s, tmp, N, MU_lower);
-    }
-  while (bn256_is_zero (s));
-
-#undef tmp_k
-#undef borrow
-}
+#include "ecc.c"
diff --git a/src/ecc.c b/src/ecc.c
new file mode 100644 (file)
index 0000000..f82e89a
--- /dev/null
+++ b/src/ecc.c
@@ -0,0 +1,367 @@
+/*                                                    -*- coding: utf-8 -*-
+ * ecc.c - Elliptic curve over GF(prime)
+ *
+ * Copyright (C) 2011, 2013, 2014 Free Software Initiative of Japan
+ * Author: NIIBE Yutaka <gniibe@fsij.org>
+ *
+ * This file is a part of Gnuk, a GnuPG USB Token implementation.
+ *
+ * Gnuk is free software: you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Gnuk 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 General Public
+ * License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ */
+
+/*
+ * References:
+ *
+ * [1] Suite B Implementer's Guide to FIPS 186-3 (ECDSA), February 3, 2010.
+ *
+ * [2] Michael Brown, Darrel Hankerson, Julio López, and Alfred Menezes,
+ *     Software Implementation of the NIST Elliptic Curves Over Prime Fields,
+ *     Proceedings of the 2001 Conference on Topics in Cryptology: The
+ *     Cryptographer's Track at RSA
+ *     Pages 250-265, Springer-Verlag London, UK, 2001
+ *     ISBN:3-540-41898-9
+ *
+ * [3] Mustapha Hedabou, Pierre Pinel, Lucien Bénéteau, 
+ *     A comb method to render ECC resistant against Side Channel Attacks,
+ *     2004
+ */
+
+#include "field-group-select.h"
+
+/*
+ * Coefficients
+ */
+/*
+ * static const bn256 *coefficient_a;
+ * static const bn256 *coefficient_b;
+ */
+/*
+ * N: order of G
+ */
+/*
+ * static const bn256 N[1];
+ */
+/*
+ * MU = 2^512 / N
+ * MU = ( (1 << 256) | MU_lower )
+ */
+/*
+ * static const bn256 MU_lower[1];
+ */
+
+/*
+ * w = 4
+ * m = 256
+ * d = 64
+ * e = 32
+ */
+
+/*
+ * static const ac precomputed_KG[15];
+ * static const ac precomputed_2E_KG[15];
+ */
+
+#if TEST
+/*
+ * Generator of Elliptic curve over GF(p256)
+ */
+const ac *G = &precomputed_KG[0];
+#endif
+
+
+static int
+get_vk (const bn256 *K, int i)
+{
+  uint32_t w0, w1, w2, w3;
+
+  if (i < 32)
+    {
+      w3 = K->word[6]; w2 = K->word[4]; w1 = K->word[2]; w0 = K->word[0];
+    }
+  else
+    {
+      w3 = K->word[7]; w2 = K->word[5]; w1 = K->word[3]; w0 = K->word[1];
+      i -= 32;
+    }
+
+  w3 >>= i;  w2 >>= i;  w1 >>= i;  w0 >>= i;
+  return ((w3 & 1) << 3) | ((w2 & 1) << 2) | ((w1 & 1) << 1) | (w0 & 1);
+}
+
+
+/**
+ * @brief      X  = k * G
+ *
+ * @param K    scalar k
+ *
+ * Return -1 on error.
+ * Return 0 on success.
+ */
+int
+FUNC(compute_kG) (ac *X, const bn256 *K)
+{
+  uint8_t index[64]; /* Lower 4-bit for index absolute value, msb is
+                       for sign (encoded as: 0 means 1, 1 means -1).  */
+  bn256 K_dash[1];
+  jpc Q[1], tmp[1], *dst;
+  int i;
+  int vk;
+  uint32_t k_is_even = bn256_is_even (K);
+
+  bn256_sub_uint (K_dash, K, k_is_even);
+  /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
+
+  /* Fill index.  */
+  vk = get_vk (K_dash, 0);
+  for (i = 1; i < 64; i++)
+    {
+      int vk_next, is_zero;
+
+      vk_next = get_vk (K_dash, i);
+      is_zero = (vk_next == 0);
+      index[i-1] = (vk - 1) | (is_zero << 7);
+      vk = (is_zero ? vk : vk_next);
+    }
+  index[63] = vk - 1;
+
+  memset (Q->z, 0, sizeof (bn256)); /* infinity */
+  for (i = 31; i >= 0; i--)
+    {
+      FUNC(jpc_double) (Q, Q);
+
+      FUNC(jpc_add_ac_signed) (Q, Q, &precomputed_KG[index[i]&0x0f],
+                              index[i] >> 7);
+      FUNC(jpc_add_ac_signed) (Q, Q, &precomputed_2E_KG[index[i+32]&0x0f],
+                              index[i+32] >> 7);
+    }
+
+  dst = k_is_even ? Q : tmp;
+  FUNC(jpc_add_ac) (dst, Q, &precomputed_KG[0]);
+
+  return FUNC(jpc_to_ac) (X, Q);
+}
+
+
+
+/**
+ * check if P is on the curve.
+ *
+ * Return -1 on error.
+ * Return 0 on success.
+ */
+static int
+point_is_on_the_curve (const ac *P)
+{
+  bn256 s[1], t[1];
+
+  /* Elliptic curve: y^2 = x^3 + a*x + b */
+  MFNC(sqr) (s, P->x);
+  MFNC(mul) (s, s, P->x);
+
+  MFNC(mul) (t, coefficient_a, P->x);
+  MFNC(add) (s, s, t);
+  MFNC(add) (s, s, coefficient_b);
+
+  MFNC(sqr) (t, P->y);
+  if (bn256_cmp (s, t) == 0)
+    return 0;
+  else
+    return -1;
+}
+
+
+static int
+get_vk_kP (const bn256 *K, int i)
+{
+  uint32_t w;
+  uint8_t blk = i/32;
+  uint8_t pos = i%32;
+  uint8_t col = 3*(pos % 11) + (pos >= 11) + (pos >= 22);
+  uint8_t word_index = (blk * 3) + (pos / 11);
+
+  w = ((K->word[word_index] >> col) & 7);
+  if (word_index < 7 && (pos == 10 || pos == 21))
+    {
+      uint8_t mask;
+      uint8_t shift;
+
+      word_index++;
+      if (pos == 10)
+       {
+         shift = 2;
+         mask = 4;
+       }
+      else
+       {
+         shift = 1;
+         mask = 6;
+       }
+
+      w |= ((K->word[word_index] << shift) & mask);
+    }
+
+  return w;
+}
+
+/**
+ * @brief      X  = k * P
+ *
+ * @param K    scalar k
+ * @param P    P in affine coordiate
+ *
+ * Return -1 on error.
+ * Return 0 on success.
+ *
+ * For the curve (cofactor is 1 and n is prime), possible error cases are:
+ *
+ *     P is not on the curve.
+ *     P = G, k = n
+ *     Something wrong in the code.
+ *
+ * Mathmatically, k=1 and P=O is another possible case, but O cannot be
+ * represented by affine coordinate.
+ */
+int
+FUNC(compute_kP) (ac *X, const bn256 *K, const ac *P)
+{
+  uint8_t index[86]; /* Lower 2-bit for index absolute value, msb is
+                       for sign (encoded as: 0 means 1, 1 means -1).  */
+  bn256 K_dash[1];
+  uint32_t k_is_even = bn256_is_even (K);
+  jpc Q[1], tmp[1], *dst;
+  int i;
+  int vk;
+  ac P3[1], P5[1], P7[1];
+  const ac *p_Pi[4];
+
+  if (point_is_on_the_curve (P) < 0)
+    return -1;
+
+  if (bn256_sub (K_dash, K, N) == 0)   /* >= N, it's too big.  */
+    return -1;
+
+  bn256_sub_uint (K_dash, K, k_is_even);
+  /* It keeps the condition: 1 <= K' <= N - 2, and K' is odd.  */
+
+  p_Pi[0] = P;
+  p_Pi[1] = P3;
+  p_Pi[2] = P5;
+  p_Pi[3] = P7;
+
+  {
+    jpc Q1[1];
+
+    memcpy (Q->x, P->x, sizeof (bn256));
+    memcpy (Q->y, P->y, sizeof (bn256));
+    memset (Q->z, 0, sizeof (bn256));
+    Q->z->word[0] = 1;
+
+    FUNC(jpc_double) (Q, Q);
+    FUNC(jpc_add_ac) (Q1, Q, P);
+    if (FUNC(jpc_to_ac) (P3, Q1) < 0) /* Never occurs, except coding errors.  */
+      return -1;
+    FUNC(jpc_double) (Q, Q);
+    FUNC(jpc_add_ac) (Q1, Q, P);
+    if (FUNC(jpc_to_ac) (P5, Q1) < 0) /* Never occurs, except coding errors.  */
+      return -1;
+
+    memcpy (Q->x, P3->x, sizeof (bn256));
+    memcpy (Q->y, P3->y, sizeof (bn256));
+    memset (Q->z, 0, sizeof (bn256));
+    Q->z->word[0] = 1;
+    FUNC(jpc_double) (Q, Q);
+    FUNC(jpc_add_ac) (Q1, Q, P);
+    if (FUNC(jpc_to_ac) (P7, Q1) < 0) /* Never occurs, except coding errors.  */
+      return -1;
+  }
+
+  /* Fill index.  */
+  vk = get_vk_kP (K_dash, 0);
+  for (i = 1; i < 86; i++)
+    {
+      int vk_next, is_even;
+
+      vk_next = get_vk_kP (K_dash, i);
+      is_even = ((vk_next & 1) == 0);
+      index[i-1] = (is_even << 7) | ((is_even?7-vk:vk-1) >> 1);
+      vk = vk_next + is_even;
+    }
+  index[85] = ((vk - 1) >> 1);
+
+  memset (Q->z, 0, sizeof (bn256)); /* infinity */
+  for (i = 85; i >= 0; i--)
+    {
+      FUNC(jpc_double) (Q, Q);
+      FUNC(jpc_double) (Q, Q);
+      FUNC(jpc_double) (Q, Q);
+      FUNC(jpc_add_ac_signed) (Q, Q, p_Pi[index[i]&0x03], index[i] >> 7);
+    }
+
+  dst = k_is_even ? Q : tmp;
+  FUNC(jpc_add_ac) (dst, Q, &precomputed_KG[0]);
+
+  return FUNC(jpc_to_ac) (X, Q);
+}
+
+
+/**
+ * @brief Compute signature (r,s) of hash string z with secret key d
+ */
+void
+FUNC(ecdsa) (bn256 *r, bn256 *s, const bn256 *z, const bn256 *d)
+{
+  bn256 k[1];
+  ac KG[1];
+  bn512 tmp[1];
+  bn256 k_inv[1];
+  uint32_t carry;
+#define borrow carry
+#define tmp_k k_inv
+
+  do
+    {
+      do
+       {
+         bn256_random (k);
+         if (bn256_add_uint (k, k, 1))
+           continue;
+         if (bn256_sub (tmp_k, k, N) == 0)     /* >= N, it's too big.  */
+           continue;
+         /* 1 <= k <= N - 1 */
+         FUNC(compute_kG) (KG, k);
+         borrow = bn256_sub (r, KG->x, N);
+         if (borrow)
+           memcpy (r, KG->x, sizeof (bn256));
+         else
+           memcpy (KG->x, r, sizeof (bn256));
+       }
+      while (bn256_is_zero (r));
+
+      mod_inv (k_inv, k, N);
+      bn256_mul (tmp, r, d);
+      mod_reduce (s, tmp, N, MU_lower);
+      carry = bn256_add (s, s, z);
+      if (carry)
+       bn256_sub (s, s, N);
+      else
+       bn256_sub ((bn256 *)tmp, s, N);
+      bn256_mul (tmp, s, k_inv);
+      mod_reduce (s, tmp, N, MU_lower);
+    }
+  while (bn256_is_zero (s));
+
+#undef tmp_k
+#undef borrow
+}
diff --git a/src/field-group-select.h b/src/field-group-select.h
new file mode 100644 (file)
index 0000000..78cb6a5
--- /dev/null
@@ -0,0 +1,7 @@
+#define CONCAT0(a,b) a##b
+#define CONCAT1(a,b) CONCAT0(a,b)
+#define CONCAT2(a,b,c) CONCAT1(a,b##c)
+#define CONCAT3(a,b,c) CONCAT2(a,b,c)
+
+#define FUNC(func) CONCAT1(func##_,FIELD)
+#define MFNC(func) CONCAT3(mod,FIELD,_##func)
index d34bf25..5a1093b 100644 (file)
--- a/src/jpc.c
+++ b/src/jpc.c
  *
  */
 
-#define CONCAT0(a,b) a##b
-#define CONCAT1(a,b) CONCAT0(a,b)
-#define CONCAT2(a,b,c) CONCAT1(a,b##c)
-#define CONCAT3(a,b,c) CONCAT2(a,b,c)
-
-#define FUNC(func) CONCAT1(func##_,FIELD)
-#define MFNC(func) CONCAT3(mod,FIELD,_##func)
+#include "field-group-select.h"
 
 /**
  * @brief      X = 2 * A
diff --git a/tool/calc_precompute_table_ecc.py b/tool/calc_precompute_table_ecc.py
new file mode 100644 (file)
index 0000000..2b59789
--- /dev/null
@@ -0,0 +1,28 @@
+from ecdsa import curves, ecdsa
+G = ecdsa.generator_secp256k1
+# G = ecdsa.generator_256
+
+def print_nG(n):
+   nG = n*G
+   nGx_str = "%064x" % nG.x()
+   nGy_str = "%064x" % nG.y()
+   print256(nGx_str)
+   print256(nGy_str)
+   print
+
+def print256(s):
+   print("0x%s, 0x%s, 0x%s, 0x%s," % (s[56:64], s[48:56], s[40:48], s[32:40]))
+   print("0x%s, 0x%s, 0x%s, 0x%s" %  (s[24:32], s[16:24], s[8:16], s[0:8]))
+   print
+
+
+for i in range(1,16):
+  n = (i & 1) + (i & 2) * 0x8000000000000000L + (i & 4) * 0x40000000000000000000000000000000L + (i & 8) * 0x200000000000000000000000000000000000000000000000L
+  print "%064x" % n
+  print_nG(n)
+
+for i in range(1,16):
+  n = (i & 1) + (i & 2) * 0x8000000000000000L + (i & 4) * 0x40000000000000000000000000000000L + (i & 8) * 0x200000000000000000000000000000000000000000000000L
+  n = n * 0x100000000L
+  print "%064x" % n
+  print_nG(n)