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

   1 /*
   2  * Copyright (c) 2016 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 I31_LEN     ((BR_MAX_EC_SIZE + 61) / 31)
  28 #define POINT_LEN   (1 + (((BR_MAX_EC_SIZE + 7) >> 3) << 1))
  29
  30 /* see bearssl_ec.h */
  31 uint32_t
  32 br_ecdsa_i31_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         uint32_t n[I31_LEN], r[I31_LEN], s[I31_LEN], t1[I31_LEN], t2[I31_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         uint32_t n0i, res;
  49
  50         /*
  51          * If the curve is not supported, then report an error.
  52          */
  53         if (((impl->supported_curves >> pk->curve) & 1) == 0) {
  54                 return 0;
  55         }
  56
  57         /*
  58          * Get the curve parameters (generator and order).
  59          */
  60         switch (pk->curve) {
  61         case BR_EC_secp256r1:
  62                 cd = &br_secp256r1;
  63                 break;
  64         case BR_EC_secp384r1:
  65                 cd = &br_secp384r1;
  66                 break;
  67         case BR_EC_secp521r1:
  68                 cd = &br_secp521r1;
  69                 break;
  70         default:
  71                 return 0;
  72         }
  73
  74         /*
  75          * Signature length must be even.
  76          */
  77         if (sig_len & 1) {
  78                 return 0;
  79         }
  80         rlen = sig_len >> 1;
  81
  82         /*
  83          * Public key point must have the proper size for this curve.
  84          */
  85         if (pk->qlen != cd->generator_len) {
  86                 return 0;
  87         }
  88
  89         /*
  90          * Get modulus; then decode the r and s values. They must be
  91          * lower than the modulus, and s must not be null.
  92          */
  93         nlen = cd->order_len;
  94         br_i31_decode(n, cd->order, nlen);
  95         n0i = br_i31_ninv31(n[1]);
  96         if (!br_i31_decode_mod(r, sig, rlen, n)) {
  97                 return 0;
  98         }
  99         if (!br_i31_decode_mod(s, (const unsigned char *)sig + rlen, rlen, n)) {
 100                 return 0;
 101         }
 102         if (br_i31_iszero(s)) {
 103                 return 0;
 104         }
 105
 106         /*
 107          * Invert s. We do that with a modular exponentiation; we use
 108          * the fact that for all the curves we support, the least
 109          * significant byte is not 0 or 1, so we can subtract 2 without
 110          * any carry to process.
 111          * We also want 1/s in Montgomery representation, which can be
 112          * done by converting _from_ Montgomery representation before
 113          * the inversion (because (1/s)*R = 1/(s/R)).
 114          */
 115         br_i31_from_monty(s, n, n0i);
 116         memcpy(tx, cd->order, nlen);
 117         tx[nlen - 1] -= 2;
 118         br_i31_modpow(s, tx, nlen, n, n0i, t1, t2);
 119
 120         /*
 121          * Truncate the hash to the modulus length (in bits) and reduce
 122          * it modulo the curve order. The modular reduction can be done
 123          * with a subtraction since the truncation already reduced the
 124          * value to the modulus bit length.
 125          */
 126         br_ecdsa_i31_bits2int(t1, hash, hash_len, n[0]);
 127         br_i31_sub(t1, n, br_i31_sub(t1, n, 0) ^ 1);
 128
 129         /*
 130          * Multiply the (truncated, reduced) hash value with 1/s, result in
 131          * t2, encoded in ty.
 132          */
 133         br_i31_montymul(t2, t1, s, n, n0i);
 134         br_i31_encode(ty, nlen, t2);
 135
 136         /*
 137          * Multiply r with 1/s, result in t1, encoded in tx.
 138          */
 139         br_i31_montymul(t1, r, s, n, n0i);
 140         br_i31_encode(tx, nlen, t1);
 141
 142         /*
 143          * Compute the point x*Q + y*G.
 144          */
 145         ulen = cd->generator_len;
 146         memcpy(eU, pk->q, ulen);
 147         res = impl->muladd(eU, NULL, ulen,
 148                 tx, nlen, ty, nlen, cd->curve);
 149
 150         /*
 151          * Get the X coordinate, reduce modulo the curve order, and
 152          * compare with the 'r' value.
 153          *
 154          * The modular reduction can be done with subtractions because
 155          * we work with curves of prime order, so the curve order is
 156          * close to the field order (Hasse's theorem).
 157          */
 158         br_i31_zero(t1, n[0]);
 159         br_i31_decode(t1, &eU[1], ulen >> 1);
 160         t1[0] = n[0];
 161         br_i31_sub(t1, n, br_i31_sub(t1, n, 0) ^ 1);
 162         res &= ~br_i31_sub(t1, r, 1);
 163         res &= br_i31_iszero(t1);
 164         return res;
 165 }