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