_ Git - BearSSL/blob - src/ec/ecdsa_i15_vrfy_raw.c

   1 /*
   2  * Copyright (c) 2017 Thomas Pornin <pornin@bolet.org>
   3  *
   4  * Permission is hereby granted, free of charge, to any person obtaining
   5  * a copy of this software and associated documentation files (the
   6  * "Software"), to deal in the Software without restriction, including
   7  * without limitation the rights to use, copy, modify, merge, publish,
   8  * distribute, sublicense, and/or sell copies of the Software, and to
   9  * permit persons to whom the Software is furnished to do so, subject to
  10  * the following conditions:
  11  *
  12  * The above copyright notice and this permission notice shall be
  13  * included in all copies or substantial portions of the Software.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  17  * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  18  * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
  19  * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
  20  * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  21  * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  22  * SOFTWARE.
  23  */
  24
  25 #include "inner.h"
  26
  27 #define I15_LEN     ((BR_MAX_EC_SIZE + 29) / 15)
  28 #define POINT_LEN   (1 + (((BR_MAX_EC_SIZE + 7) >> 3) << 1))
  29
  30 /* see bearssl_ec.h */
  31 uint32_t
  32 br_ecdsa_i15_vrfy_raw(const br_ec_impl *impl,
  33         const void *hash, size_t hash_len,
  34         const br_ec_public_key *pk,
  35         const void *sig, size_t sig_len)
  36 {
  37         /*
  38          * IMPORTANT: this code is fit only for curves with a prime
  39          * order. This is needed so that modular reduction of the X
  40          * coordinate of a point can be done with a simple subtraction.
  41          */
  42         const br_ec_curve_def *cd;
  43         uint16_t n[I15_LEN], r[I15_LEN], s[I15_LEN], t1[I15_LEN], t2[I15_LEN];
  44         unsigned char tx[(BR_MAX_EC_SIZE + 7) >> 3];
  45         unsigned char ty[(BR_MAX_EC_SIZE + 7) >> 3];
  46         unsigned char eU[POINT_LEN];
  47         size_t nlen, rlen, ulen;
  48         uint16_t n0i;
  49         uint32_t res;
  50
  51         /*
  52          * If the curve is not supported, then report an error.
  53          */
  54         if (((impl->supported_curves >> pk->curve) & 1) == 0) {
  55                 return 0;
  56         }
  57
  58         /*
  59          * Get the curve parameters (generator and order).
  60          */
  61         switch (pk->curve) {
  62         case BR_EC_secp256r1:
  63                 cd = &br_secp256r1;
  64                 break;
  65         case BR_EC_secp384r1:
  66                 cd = &br_secp384r1;
  67                 break;
  68         case BR_EC_secp521r1:
  69                 cd = &br_secp521r1;
  70                 break;
  71         default:
  72                 return 0;
  73         }
  74
  75         /*
  76          * Signature length must be even.
  77          */
  78         if (sig_len & 1) {
  79                 return 0;
  80         }
  81         rlen = sig_len >> 1;
  82
  83         /*
  84          * Public key point must have the proper size for this curve.
  85          */
  86         if (pk->qlen != cd->generator_len) {
  87                 return 0;
  88         }
  89
  90         /*
  91          * Get modulus; then decode the r and s values. They must be
  92          * lower than the modulus, and s must not be null.
  93          */
  94         nlen = cd->order_len;
  95         br_i15_decode(n, cd->order, nlen);
  96         n0i = br_i15_ninv15(n[1]);
  97         if (!br_i15_decode_mod(r, sig, rlen, n)) {
  98                 return 0;
  99         }
 100         if (!br_i15_decode_mod(s, (const unsigned char *)sig + rlen, rlen, n)) {
 101                 return 0;
 102         }
 103         if (br_i15_iszero(s)) {
 104                 return 0;
 105         }
 106
 107         /*
 108          * Invert s. We do that with a modular exponentiation; we use
 109          * the fact that for all the curves we support, the least
 110          * significant byte is not 0 or 1, so we can subtract 2 without
 111          * any carry to process.
 112          * We also want 1/s in Montgomery representation, which can be
 113          * done by converting _from_ Montgomery representation before
 114          * the inversion (because (1/s)*R = 1/(s/R)).
 115          */
 116         br_i15_from_monty(s, n, n0i);
 117         memcpy(tx, cd->order, nlen);
 118         tx[nlen - 1] -= 2;
 119         br_i15_modpow(s, tx, nlen, n, n0i, t1, t2);
 120
 121         /*
 122          * Truncate the hash to the modulus length (in bits) and reduce
 123          * it modulo the curve order. The modular reduction can be done
 124          * with a subtraction since the truncation already reduced the
 125          * value to the modulus bit length.
 126          */
 127         br_ecdsa_i15_bits2int(t1, hash, hash_len, n[0]);
 128         br_i15_sub(t1, n, br_i15_sub(t1, n, 0) ^ 1);
 129
 130         /*
 131          * Multiply the (truncated, reduced) hash value with 1/s, result in
 132          * t2, encoded in ty.
 133          */
 134         br_i15_montymul(t2, t1, s, n, n0i);
 135         br_i15_encode(ty, nlen, t2);
 136
 137         /*
 138          * Multiply r with 1/s, result in t1, encoded in tx.
 139          */
 140         br_i15_montymul(t1, r, s, n, n0i);
 141         br_i15_encode(tx, nlen, t1);
 142
 143         /*
 144          * Compute the point x*Q + y*G.
 145          */
 146         ulen = cd->generator_len;
 147         memcpy(eU, pk->q, ulen);
 148         res = impl->muladd(eU, NULL, ulen,
 149                 tx, nlen, ty, nlen, cd->curve);
 150
 151         /*
 152          * Get the X coordinate, reduce modulo the curve order, and
 153          * compare with the 'r' value.
 154          *
 155          * The modular reduction can be done with subtractions because
 156          * we work with curves of prime order, so the curve order is
 157          * close to the field order (Hasse's theorem).
 158          */
 159         br_i15_zero(t1, n[0]);
 160         br_i15_decode(t1, &eU[1], ulen >> 1);
 161         t1[0] = n[0];
 162         br_i15_sub(t1, n, br_i15_sub(t1, n, 0) ^ 1);
 163         res &= ~br_i15_sub(t1, r, 1);
 164         res &= br_i15_iszero(t1);
 165         return res;
 166 }