crypto/ec/curve448/scalar.c

   1 /*
   2  * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2015-2016 Cryptography Research, Inc.
   4  *
   5  * Licensed under the OpenSSL license (the "License").  You may not use
   6  * this file except in compliance with the License.  You can obtain a copy
   7  * in the file LICENSE in the source distribution or at
   8  * https://www.openssl.org/source/license.html
   9  *
  10  * Originally written by Mike Hamburg
  11  */
  12 #include <openssl/crypto.h>
  13
  14 #include "word.h"
  15 #include "constant_time.h"
  16 #include "point_448.h"
  17
  18 static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t) 0x3bd440fae918bc5;
  19 static const curve448_scalar_t sc_p = { {{
  20                                           SC_LIMB(0x2378c292ab5844f3),
  21                                           SC_LIMB(0x216cc2728dc58f55),
  22                                           SC_LIMB(0xc44edb49aed63690),
  23                                           SC_LIMB(0xffffffff7cca23e9),
  24                                           SC_LIMB(0xffffffffffffffff),
  25                                           SC_LIMB(0xffffffffffffffff),
  26                                           SC_LIMB(0x3fffffffffffffff)
  27                                           }}
  28 }, sc_r2 = { { {
  29
  30             SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
  31                 SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
  32                 SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
  33                 SC_LIMB(0x3402a939f823b729)
  34 }}};
  35
  36 /* End of template stuff */
  37
  38 #define WBITS DECAF_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
  39
  40 const curve448_scalar_t curve448_scalar_one = { {{1}} }, curve448_scalar_zero = { { {
  41 0}}};
  42
  43 /** {extra,accum} - sub +? p
  44  * Must have extra <= 1
  45  */
  46 static void sc_subx(curve448_scalar_t out,
  47                     const decaf_word_t accum[DECAF_448_SCALAR_LIMBS],
  48                     const curve448_scalar_t sub,
  49                     const curve448_scalar_t p, decaf_word_t extra)
  50 {
  51     decaf_dsword_t chain = 0;
  52     unsigned int i;
  53     decaf_word_t borrow;
  54
  55     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
  56         chain = (chain + accum[i]) - sub->limb[i];
  57         out->limb[i] = chain;
  58         chain >>= WBITS;
  59     }
  60     borrow = chain + extra;     /* = 0 or -1 */
  61
  62     chain = 0;
  63     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
  64         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
  65         out->limb[i] = chain;
  66         chain >>= WBITS;
  67     }
  68 }
  69
  70 static void sc_montmul(curve448_scalar_t out,
  71                        const curve448_scalar_t a, const curve448_scalar_t b)
  72 {
  73     unsigned int i, j;
  74     decaf_word_t accum[DECAF_448_SCALAR_LIMBS + 1] = { 0 };
  75     decaf_word_t hi_carry = 0;
  76
  77     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
  78         decaf_word_t mand = a->limb[i];
  79         const decaf_word_t *mier = b->limb;
  80
  81         decaf_dword_t chain = 0;
  82         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
  83             chain += ((decaf_dword_t) mand) * mier[j] + accum[j];
  84             accum[j] = chain;
  85             chain >>= WBITS;
  86         }
  87         accum[j] = chain;
  88
  89         mand = accum[0] * MONTGOMERY_FACTOR;
  90         chain = 0;
  91         mier = sc_p->limb;
  92         for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
  93             chain += (decaf_dword_t) mand *mier[j] + accum[j];
  94             if (j)
  95                 accum[j - 1] = chain;
  96             chain >>= WBITS;
  97         }
  98         chain += accum[j];
  99         chain += hi_carry;
 100         accum[j - 1] = chain;
 101         hi_carry = chain >> WBITS;
 102     }
 103
 104     sc_subx(out, accum, sc_p, sc_p, hi_carry);
 105 }
 106
 107 void curve448_scalar_mul(curve448_scalar_t out,
 108                          const curve448_scalar_t a, const curve448_scalar_t b)
 109 {
 110     sc_montmul(out, a, b);
 111     sc_montmul(out, out, sc_r2);
 112 }
 113
 114 void curve448_scalar_sub(curve448_scalar_t out,
 115                          const curve448_scalar_t a, const curve448_scalar_t b)
 116 {
 117     sc_subx(out, a->limb, b, sc_p, 0);
 118 }
 119
 120 void curve448_scalar_add(curve448_scalar_t out,
 121                          const curve448_scalar_t a, const curve448_scalar_t b)
 122 {
 123     decaf_dword_t chain = 0;
 124     unsigned int i;
 125     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
 126         chain = (chain + a->limb[i]) + b->limb[i];
 127         out->limb[i] = chain;
 128         chain >>= WBITS;
 129     }
 130     sc_subx(out, out->limb, sc_p, sc_p, chain);
 131 }
 132
 133 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
 134                                             const unsigned char *ser,
 135                                             unsigned int nbytes)
 136 {
 137     unsigned int i, j, k = 0;
 138     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
 139         decaf_word_t out = 0;
 140         for (j = 0; j < sizeof(decaf_word_t) && k < nbytes; j++, k++) {
 141             out |= ((decaf_word_t) ser[k]) << (8 * j);
 142         }
 143         s->limb[i] = out;
 144     }
 145 }
 146
 147 decaf_error_t curve448_scalar_decode(curve448_scalar_t s,
 148                                      const unsigned char
 149                                      ser[DECAF_448_SCALAR_BYTES]
 150     )
 151 {
 152     unsigned int i;
 153     decaf_dsword_t accum = 0;
 154
 155     scalar_decode_short(s, ser, DECAF_448_SCALAR_BYTES);
 156     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
 157         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
 158     }
 159     /* Here accum == 0 or -1 */
 160
 161     curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
 162
 163     return decaf_succeed_if(~word_is_zero(accum));
 164 }
 165
 166 void curve448_scalar_destroy(curve448_scalar_t scalar)
 167 {
 168     OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
 169 }
 170
 171 void curve448_scalar_decode_long(curve448_scalar_t s,
 172                                  const unsigned char *ser, size_t ser_len)
 173 {
 174     size_t i;
 175     curve448_scalar_t t1, t2;
 176
 177     if (ser_len == 0) {
 178         curve448_scalar_copy(s, curve448_scalar_zero);
 179         return;
 180     }
 181
 182     i = ser_len - (ser_len % DECAF_448_SCALAR_BYTES);
 183     if (i == ser_len)
 184         i -= DECAF_448_SCALAR_BYTES;
 185
 186     scalar_decode_short(t1, &ser[i], ser_len - i);
 187
 188     if (ser_len == sizeof(curve448_scalar_t)) {
 189         assert(i == 0);
 190         /* ham-handed reduce */
 191         curve448_scalar_mul(s, t1, curve448_scalar_one);
 192         curve448_scalar_destroy(t1);
 193         return;
 194     }
 195
 196     while (i) {
 197         i -= DECAF_448_SCALAR_BYTES;
 198         sc_montmul(t1, t1, sc_r2);
 199         ignore_result(curve448_scalar_decode(t2, ser + i));
 200         curve448_scalar_add(t1, t1, t2);
 201     }
 202
 203     curve448_scalar_copy(s, t1);
 204     curve448_scalar_destroy(t1);
 205     curve448_scalar_destroy(t2);
 206 }
 207
 208 void curve448_scalar_encode(unsigned char ser[DECAF_448_SCALAR_BYTES],
 209                             const curve448_scalar_t s)
 210 {
 211     unsigned int i, j, k = 0;
 212     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
 213         for (j = 0; j < sizeof(decaf_word_t); j++, k++) {
 214             ser[k] = s->limb[i] >> (8 * j);
 215         }
 216     }
 217 }
 218
 219 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
 220 {
 221     decaf_word_t mask = -(a->limb[0] & 1);
 222     decaf_dword_t chain = 0;
 223     unsigned int i;
 224     for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
 225         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
 226         out->limb[i] = chain;
 227         chain >>= DECAF_WORD_BITS;
 228     }
 229     for (i = 0; i < DECAF_448_SCALAR_LIMBS - 1; i++) {
 230         out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
 231     }
 232     out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);
 233 }