ecc-ecdsa-verify.c

   1 /* ecc-ecdsa-verify.c */
   2
   3 /* nettle, low-level cryptographics library
   4  *
   5  * Copyright (C) 2013 Niels Möller
   6  *
   7  * The nettle library is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU Lesser General Public License as published by
   9  * the Free Software Foundation; either version 2.1 of the License, or (at your
  10  * option) any later version.
  11  *
  12  * The nettle library is distributed in the hope that it will be useful, but
  13  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  14  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  15  * License for more details.
  16  *
  17  * You should have received a copy of the GNU Lesser General Public License
  18  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  20  * MA 02111-1301, USA.
  21  */
  22
  23 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
  24
  25 #if HAVE_CONFIG_H
  26 # include "config.h"
  27 #endif
  28
  29 #include <assert.h>
  30 #include <stdlib.h>
  31
  32 #include "ecdsa.h"
  33 #include "ecc-internal.h"
  34
  35 /* Low-level ECDSA verify */
  36
  37 static int
  38 zero_p (const mp_limb_t *xp, mp_size_t n)
  39 {
  40   while (n > 0)
  41     if (xp[--n] > 0)
  42       return 0;
  43   return 1;
  44 }
  45
  46 static int
  47 ecdsa_in_range (const struct ecc_curve *ecc, const mp_limb_t *xp)
  48 {
  49   return !zero_p (xp, ecc->size)
  50     && mpn_cmp (xp, ecc->q, ecc->size) < 0;
  51 }
  52
  53 mp_size_t
  54 ecc_ecdsa_verify_itch (const struct ecc_curve *ecc)
  55 {
  56   /* Largest storage need is for the ecc_mul_a call, 6 * ecc->size +
  57      ECC_MUL_A_ITCH (size) */
  58   return ECC_ECDSA_VERIFY_ITCH (ecc->size);
  59 }
  60
  61 /* FIXME: Use faster primitives, not requiring side-channel silence. */
  62 int
  63 ecc_ecdsa_verify (const struct ecc_curve *ecc,
  64                   const mp_limb_t *pp, /* Public key */
  65                   unsigned length, const uint8_t *digest,
  66                   const mp_limb_t *rp, const mp_limb_t *sp,
  67                   mp_limb_t *scratch)
  68 {
  69   /* Procedure, according to RFC 6090, "KT-I". q denotes the group
  70      order.
  71
  72      1. Check 0 < r, s < q.
  73
  74      2. s' <-- s^{-1}  (mod q)
  75
  76      3. u1  <-- h * s' (mod q)
  77
  78      4. u2  <-- r * s' (mod q)
  79
  80      5. R = u1 G + u2 Y
  81
  82      6. Signature is valid if R_x = r (mod q).
  83   */
  84
  85 #define P2 scratch
  86 #define P1 (scratch + 3*ecc->size)
  87 #define sinv (scratch + 3*ecc->size)
  88 #define u2 (scratch + 4*ecc->size)
  89 #define hp (scratch + 4*ecc->size)
  90 #define u1 (scratch + 6*ecc->size)
  91
  92   if (! (ecdsa_in_range (ecc, rp)
  93          && ecdsa_in_range (ecc, sp)))
  94     return 0;
  95
  96   /* FIXME: Micro optimizations: Either simultaneous multiplication.
  97      Or convert to projective coordinates (can be done without
  98      division, I think), and write an ecc_add_ppp. */
  99
 100   /* Compute sinv, use P2 as scratch */
 101   mpn_copyi (sinv + ecc->size, sp, ecc->size);
 102   ecc_modq_inv (ecc, sinv, sinv + ecc->size, P2);
 103
 104   /* u2 = r / s, P2 = u2 * Y */
 105   ecc_modq_mul (ecc, u2, rp, sinv);
 106
 107    /* Total storage: 5*ecc->size + ECC_MUL_A_ITCH (ecc->size) */
 108   ecc_mul_a (ecc, 1, P2, u2, pp, u2 + ecc->size);
 109
 110   /* u1 = h / s, P1 = u1 * G */
 111   ecc_hash (ecc, hp, length, digest);
 112   ecc_modq_mul (ecc, u1, hp, sinv);
 113
 114   /* u = 0 can happen only if h = 0 or h = q, which is extremely
 115      unlikely. */
 116   if (!zero_p (u1, ecc->size))
 117     {
 118       /* Total storage: 6*ecc->size + ECC_MUL_G_ITCH (ecc->size) */
 119       ecc_mul_g (ecc, P1, u1, u1 + ecc->size);
 120
 121       /* NOTE: ecc_add_jjj and/or ecc_j_to_a will produce garbage in
 122          case u1 G = +/- u2 V. However, anyone who gets his or her
 123          hands on a signature where this happens during verification,
 124          can also get the private key as z = +/- u1 / u_2 (mod q). And
 125          then it doesn't matter very much if verification of
 126          signatures with that key succeeds or fails.
 127
 128          u1 G = - u2 V can never happen for a correctly generated
 129          signature, since it implies k = 0.
 130
 131          u1 G = u2 V is possible, if we are unlucky enough to get h /
 132          s_1 = z. Hitting that is about as unlikely as finding the
 133          private key by guessing.
 134        */
 135       /* Total storage: 6*ecc->size + ECC_ADD_JJJ_ITCH (ecc->size) */
 136       ecc_add_jjj (ecc, P1, P1, P2, u1);
 137     }
 138   ecc_j_to_a (ecc, 3, P2, P1, u1);
 139
 140   if (mpn_cmp (P2, ecc->q, ecc->size) >= 0)
 141     mpn_sub_n (P2, P2, ecc->q, ecc->size);
 142
 143   return (mpn_cmp (rp, P2, ecc->size) == 0);
 144 #undef P2
 145 #undef P1
 146 #undef sinv
 147 #undef u2
 148 #undef hp
 149 #undef u1
 150 }