ecc-ecdsa-verify.c

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