Home | History | Annotate | Download | only in libmincrypt
      1 /*
      2  * Copyright 2013 The Android Open Source Project
      3  *
      4  * Redistribution and use in source and binary forms, with or without
      5  * modification, are permitted provided that the following conditions are met:
      6  *     * Redistributions of source code must retain the above copyright
      7  *       notice, this list of conditions and the following disclaimer.
      8  *     * Redistributions in binary form must reproduce the above copyright
      9  *       notice, this list of conditions and the following disclaimer in the
     10  *       documentation and/or other materials provided with the distribution.
     11  *     * Neither the name of Google Inc. nor the names of its contributors may
     12  *       be used to endorse or promote products derived from this software
     13  *       without specific prior written permission.
     14  *
     15  * THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
     16  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
     17  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
     18  * EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
     19  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
     20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
     21  * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
     22  * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
     23  * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
     24  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
     25  */
     26 
     27 // This is an implementation of the P256 elliptic curve group. It's written to
     28 // be portable 32-bit, although it's still constant-time.
     29 //
     30 // WARNING: Implementing these functions in a constant-time manner is far from
     31 //          obvious. Be careful when touching this code.
     32 //
     33 // See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background.
     34 
     35 #include <assert.h>
     36 #include <stdint.h>
     37 #include <string.h>
     38 #include <stdio.h>
     39 
     40 #include "mincrypt/p256.h"
     41 
     42 const p256_int SECP256r1_n =  // curve order
     43   {{0xfc632551, 0xf3b9cac2, 0xa7179e84, 0xbce6faad, -1, -1, 0, -1}};
     44 
     45 const p256_int SECP256r1_p =  // curve field size
     46   {{-1, -1, -1, 0, 0, 0, 1, -1 }};
     47 
     48 const p256_int SECP256r1_b =  // curve b
     49   {{0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0,
     50     0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8}};
     51 
     52 void p256_init(p256_int* a) {
     53   memset(a, 0, sizeof(*a));
     54 }
     55 
     56 void p256_clear(p256_int* a) { p256_init(a); }
     57 
     58 int p256_get_bit(const p256_int* scalar, int bit) {
     59   return (P256_DIGIT(scalar, bit / P256_BITSPERDIGIT)
     60               >> (bit & (P256_BITSPERDIGIT - 1))) & 1;
     61 }
     62 
     63 int p256_is_zero(const p256_int* a) {
     64   int i, result = 0;
     65   for (i = 0; i < P256_NDIGITS; ++i) result |= P256_DIGIT(a, i);
     66   return !result;
     67 }
     68 
     69 // top, c[] += a[] * b
     70 // Returns new top
     71 static p256_digit mulAdd(const p256_int* a,
     72                          p256_digit b,
     73                          p256_digit top,
     74                          p256_digit* c) {
     75   int i;
     76   p256_ddigit carry = 0;
     77 
     78   for (i = 0; i < P256_NDIGITS; ++i) {
     79     carry += *c;
     80     carry += (p256_ddigit)P256_DIGIT(a, i) * b;
     81     *c++ = (p256_digit)carry;
     82     carry >>= P256_BITSPERDIGIT;
     83   }
     84   return top + (p256_digit)carry;
     85 }
     86 
     87 // top, c[] -= top_a, a[]
     88 static p256_digit subTop(p256_digit top_a,
     89                          const p256_digit* a,
     90                          p256_digit top_c,
     91                          p256_digit* c) {
     92   int i;
     93   p256_sddigit borrow = 0;
     94 
     95   for (i = 0; i < P256_NDIGITS; ++i) {
     96     borrow += *c;
     97     borrow -= *a++;
     98     *c++ = (p256_digit)borrow;
     99     borrow >>= P256_BITSPERDIGIT;
    100   }
    101   borrow += top_c;
    102   borrow -= top_a;
    103   top_c = (p256_digit)borrow;
    104   assert((borrow >> P256_BITSPERDIGIT) == 0);
    105   return top_c;
    106 }
    107 
    108 // top, c[] -= MOD[] & mask (0 or -1)
    109 // returns new top.
    110 static p256_digit subM(const p256_int* MOD,
    111                        p256_digit top,
    112                        p256_digit* c,
    113                        p256_digit mask) {
    114   int i;
    115   p256_sddigit borrow = 0;
    116   for (i = 0; i < P256_NDIGITS; ++i) {
    117     borrow += *c;
    118     borrow -= P256_DIGIT(MOD, i) & mask;
    119     *c++ = (p256_digit)borrow;
    120     borrow >>= P256_BITSPERDIGIT;
    121   }
    122   return top + (p256_digit)borrow;
    123 }
    124 
    125 // top, c[] += MOD[] & mask (0 or -1)
    126 // returns new top.
    127 static p256_digit addM(const p256_int* MOD,
    128                        p256_digit top,
    129                        p256_digit* c,
    130                        p256_digit mask) {
    131   int i;
    132   p256_ddigit carry = 0;
    133   for (i = 0; i < P256_NDIGITS; ++i) {
    134     carry += *c;
    135     carry += P256_DIGIT(MOD, i) & mask;
    136     *c++ = (p256_digit)carry;
    137     carry >>= P256_BITSPERDIGIT;
    138   }
    139   return top + (p256_digit)carry;
    140 }
    141 
    142 // c = a * b mod MOD. c can be a and/or b.
    143 void p256_modmul(const p256_int* MOD,
    144                  const p256_int* a,
    145                  const p256_digit top_b,
    146                  const p256_int* b,
    147                  p256_int* c) {
    148   p256_digit tmp[P256_NDIGITS * 2 + 1] = { 0 };
    149   p256_digit top = 0;
    150   int i;
    151 
    152   // Multiply/add into tmp.
    153   for (i = 0; i < P256_NDIGITS; ++i) {
    154     if (i) tmp[i + P256_NDIGITS - 1] = top;
    155     top = mulAdd(a, P256_DIGIT(b, i), 0, tmp + i);
    156   }
    157 
    158   // Multiply/add top digit
    159   tmp[i + P256_NDIGITS - 1] = top;
    160   top = mulAdd(a, top_b, 0, tmp + i);
    161 
    162   // Reduce tmp, digit by digit.
    163   for (; i >= 0; --i) {
    164     p256_digit reducer[P256_NDIGITS] = { 0 };
    165     p256_digit top_reducer;
    166 
    167     // top can be any value at this point.
    168     // Guestimate reducer as top * MOD, since msw of MOD is -1.
    169     top_reducer = mulAdd(MOD, top, 0, reducer);
    170 
    171     // Subtract reducer from top | tmp.
    172     top = subTop(top_reducer, reducer, top, tmp + i);
    173 
    174     // top is now either 0 or 1. Make it 0, fixed-timing.
    175     assert(top <= 1);
    176 
    177     top = subM(MOD, top, tmp + i, ~(top - 1));
    178 
    179     assert(top == 0);
    180 
    181     // We have now reduced the top digit off tmp. Fetch new top digit.
    182     top = tmp[i + P256_NDIGITS - 1];
    183   }
    184 
    185   // tmp might still be larger than MOD, yet same bit length.
    186   // Make sure it is less, fixed-timing.
    187   addM(MOD, 0, tmp, subM(MOD, 0, tmp, -1));
    188 
    189   memcpy(c, tmp, P256_NBYTES);
    190 }
    191 int p256_is_odd(const p256_int* a) { return P256_DIGIT(a, 0) & 1; }
    192 int p256_is_even(const p256_int* a) { return !(P256_DIGIT(a, 0) & 1); }
    193 
    194 p256_digit p256_shl(const p256_int* a, int n, p256_int* b) {
    195   int i;
    196   p256_digit top = P256_DIGIT(a, P256_NDIGITS - 1);
    197 
    198   n %= P256_BITSPERDIGIT;
    199   for (i = P256_NDIGITS - 1; i > 0; --i) {
    200     p256_digit accu = (P256_DIGIT(a, i) << n);
    201     accu |= (P256_DIGIT(a, i - 1) >> (P256_BITSPERDIGIT - n));
    202     P256_DIGIT(b, i) = accu;
    203   }
    204   P256_DIGIT(b, i) = (P256_DIGIT(a, i) << n);
    205 
    206   top = (p256_digit)((((p256_ddigit)top) << n) >> P256_BITSPERDIGIT);
    207 
    208   return top;
    209 }
    210 
    211 void p256_shr(const p256_int* a, int n, p256_int* b) {
    212   int i;
    213 
    214   n %= P256_BITSPERDIGIT;
    215   for (i = 0; i < P256_NDIGITS - 1; ++i) {
    216     p256_digit accu = (P256_DIGIT(a, i) >> n);
    217     accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - n));
    218     P256_DIGIT(b, i) = accu;
    219   }
    220   P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> n);
    221 }
    222 
    223 static void p256_shr1(const p256_int* a, int highbit, p256_int* b) {
    224   int i;
    225 
    226   for (i = 0; i < P256_NDIGITS - 1; ++i) {
    227     p256_digit accu = (P256_DIGIT(a, i) >> 1);
    228     accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - 1));
    229     P256_DIGIT(b, i) = accu;
    230   }
    231   P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> 1) |
    232       (highbit << (P256_BITSPERDIGIT - 1));
    233 }
    234 
    235 // Return -1, 0, 1 for a < b, a == b or a > b respectively.
    236 int p256_cmp(const p256_int* a, const p256_int* b) {
    237   int i;
    238   p256_sddigit borrow = 0;
    239   p256_digit notzero = 0;
    240 
    241   for (i = 0; i < P256_NDIGITS; ++i) {
    242     borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i);
    243     // Track whether any result digit is ever not zero.
    244     // Relies on !!(non-zero) evaluating to 1, e.g., !!(-1) evaluating to 1.
    245     notzero |= !!((p256_digit)borrow);
    246     borrow >>= P256_BITSPERDIGIT;
    247   }
    248   return (int)borrow | notzero;
    249 }
    250 
    251 // c = a - b. Returns borrow: 0 or -1.
    252 int p256_sub(const p256_int* a, const p256_int* b, p256_int* c) {
    253   int i;
    254   p256_sddigit borrow = 0;
    255 
    256   for (i = 0; i < P256_NDIGITS; ++i) {
    257     borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i);
    258     if (c) P256_DIGIT(c, i) = (p256_digit)borrow;
    259     borrow >>= P256_BITSPERDIGIT;
    260   }
    261   return (int)borrow;
    262 }
    263 
    264 // c = a + b. Returns carry: 0 or 1.
    265 int p256_add(const p256_int* a, const p256_int* b, p256_int* c) {
    266   int i;
    267   p256_ddigit carry = 0;
    268 
    269   for (i = 0; i < P256_NDIGITS; ++i) {
    270     carry += (p256_ddigit)P256_DIGIT(a, i) + P256_DIGIT(b, i);
    271     if (c) P256_DIGIT(c, i) = (p256_digit)carry;
    272     carry >>= P256_BITSPERDIGIT;
    273   }
    274   return (int)carry;
    275 }
    276 
    277 // b = a + d. Returns carry, 0 or 1.
    278 int p256_add_d(const p256_int* a, p256_digit d, p256_int* b) {
    279   int i;
    280   p256_ddigit carry = d;
    281 
    282   for (i = 0; i < P256_NDIGITS; ++i) {
    283     carry += (p256_ddigit)P256_DIGIT(a, i);
    284     if (b) P256_DIGIT(b, i) = (p256_digit)carry;
    285     carry >>= P256_BITSPERDIGIT;
    286   }
    287   return (int)carry;
    288 }
    289 
    290 // b = 1/a mod MOD, binary euclid.
    291 void p256_modinv_vartime(const p256_int* MOD,
    292                          const p256_int* a,
    293                          p256_int* b) {
    294   p256_int R = P256_ZERO;
    295   p256_int S = P256_ONE;
    296   p256_int U = *MOD;
    297   p256_int V = *a;
    298 
    299   for (;;) {
    300     if (p256_is_even(&U)) {
    301       p256_shr1(&U, 0, &U);
    302       if (p256_is_even(&R)) {
    303         p256_shr1(&R, 0, &R);
    304       } else {
    305         // R = (R+MOD)/2
    306         p256_shr1(&R, p256_add(&R, MOD, &R), &R);
    307       }
    308     } else if (p256_is_even(&V)) {
    309       p256_shr1(&V, 0, &V);
    310       if (p256_is_even(&S)) {
    311         p256_shr1(&S, 0, &S);
    312       } else {
    313         // S = (S+MOD)/2
    314         p256_shr1(&S, p256_add(&S, MOD, &S) , &S);
    315       }
    316     } else {  // U,V both odd.
    317       if (!p256_sub(&V, &U, NULL)) {
    318         p256_sub(&V, &U, &V);
    319         if (p256_sub(&S, &R, &S)) p256_add(&S, MOD, &S);
    320         if (p256_is_zero(&V)) break;  // done.
    321       } else {
    322         p256_sub(&U, &V, &U);
    323         if (p256_sub(&R, &S, &R)) p256_add(&R, MOD, &R);
    324       }
    325     }
    326   }
    327 
    328   p256_mod(MOD, &R, b);
    329 }
    330 
    331 void p256_mod(const p256_int* MOD,
    332               const p256_int* in,
    333               p256_int* out) {
    334   if (out != in) *out = *in;
    335   addM(MOD, 0, P256_DIGITS(out), subM(MOD, 0, P256_DIGITS(out), -1));
    336 }
    337 
    338 // Verify y^2 == x^3 - 3x + b mod p
    339 // and 0 < x < p and 0 < y < p
    340 int p256_is_valid_point(const p256_int* x, const p256_int* y) {
    341   p256_int y2, x3;
    342 
    343   if (p256_cmp(&SECP256r1_p, x) <= 0 ||
    344       p256_cmp(&SECP256r1_p, y) <= 0 ||
    345       p256_is_zero(x) ||
    346       p256_is_zero(y)) return 0;
    347 
    348   p256_modmul(&SECP256r1_p, y, 0, y, &y2);  // y^2
    349 
    350   p256_modmul(&SECP256r1_p, x, 0, x, &x3);  // x^2
    351   p256_modmul(&SECP256r1_p, x, 0, &x3, &x3);  // x^3
    352   if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - x
    353   if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - 2x
    354   if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - 3x
    355   if (p256_add(&x3, &SECP256r1_b, &x3))  // x^3 - 3x + b
    356     p256_sub(&x3, &SECP256r1_p, &x3);
    357 
    358   return p256_cmp(&y2, &x3) == 0;
    359 }
    360 
    361 void p256_from_bin(const uint8_t src[P256_NBYTES], p256_int* dst) {
    362   int i;
    363   const uint8_t* p = &src[0];
    364 
    365   for (i = P256_NDIGITS - 1; i >= 0; --i) {
    366     P256_DIGIT(dst, i) =
    367         (p[0] << 24) |
    368         (p[1] << 16) |
    369         (p[2] << 8) |
    370         p[3];
    371     p += 4;
    372   }
    373 }
    374