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 c448_word_t MONTGOMERY_FACTOR = (c448_word_t) 0x3bd440fae918bc5;
  19 static const curve448_scalar_t sc_p = {
  20     {
  21         {
  22             SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55),
  23             SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9),
  24             SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff),
  25             SC_LIMB(0x3fffffffffffffff)
  26         }
  27     }
  28 }, sc_r2 = {
  29     {
  30         {
  31
  32             SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
  33             SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
  34             SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
  35             SC_LIMB(0x3402a939f823b729)
  36         }
  37     }
  38 };
  39
  40 #define WBITS C448_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
  41
  42 const curve448_scalar_t curve448_scalar_one = {{{1}}};
  43 const curve448_scalar_t  curve448_scalar_zero = {{{0}}};
  44
  45 /*
  46  * {extra,accum} - sub +? p
  47  * Must have extra <= 1
  48  */
  49 static void sc_subx(curve448_scalar_t out,
  50                     const c448_word_t accum[C448_448_SCALAR_LIMBS],
  51                     const curve448_scalar_t sub,
  52                     const curve448_scalar_t p, c448_word_t extra)
  53 {
  54     c448_dsword_t chain = 0;
  55     unsigned int i;
  56     c448_word_t borrow;
  57
  58     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
  59         chain = (chain + accum[i]) - sub->limb[i];
  60         out->limb[i] = chain;
  61         chain >>= WBITS;
  62     }
  63     borrow = chain + extra;     /* = 0 or -1 */
  64
  65     chain = 0;
  66     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
  67         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
  68         out->limb[i] = chain;
  69         chain >>= WBITS;
  70     }
  71 }
  72
  73 static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a,
  74                        const curve448_scalar_t b)
  75 {
  76     unsigned int i, j;
  77     c448_word_t accum[C448_448_SCALAR_LIMBS + 1] = { 0 };
  78     c448_word_t hi_carry = 0;
  79
  80     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
  81         c448_word_t mand = a->limb[i];
  82         const c448_word_t *mier = b->limb;
  83
  84         c448_dword_t chain = 0;
  85         for (j = 0; j < C448_448_SCALAR_LIMBS; j++) {
  86             chain += ((c448_dword_t) mand) * mier[j] + accum[j];
  87             accum[j] = chain;
  88             chain >>= WBITS;
  89         }
  90         accum[j] = chain;
  91
  92         mand = accum[0] * MONTGOMERY_FACTOR;
  93         chain = 0;
  94         mier = sc_p->limb;
  95         for (j = 0; j < C448_448_SCALAR_LIMBS; j++) {
  96             chain += (c448_dword_t) mand *mier[j] + accum[j];
  97             if (j)
  98                 accum[j - 1] = chain;
  99             chain >>= WBITS;
 100         }
 101         chain += accum[j];
 102         chain += hi_carry;
 103         accum[j - 1] = chain;
 104         hi_carry = chain >> WBITS;
 105     }
 106
 107     sc_subx(out, accum, sc_p, sc_p, hi_carry);
 108 }
 109
 110 void curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a,
 111                          const curve448_scalar_t b)
 112 {
 113     sc_montmul(out, a, b);
 114     sc_montmul(out, out, sc_r2);
 115 }
 116
 117 void curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a,
 118                          const curve448_scalar_t b)
 119 {
 120     sc_subx(out, a->limb, b, sc_p, 0);
 121 }
 122
 123 void curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
 124                          const curve448_scalar_t b)
 125 {
 126     c448_dword_t chain = 0;
 127     unsigned int i;
 128
 129     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
 130         chain = (chain + a->limb[i]) + b->limb[i];
 131         out->limb[i] = chain;
 132         chain >>= WBITS;
 133     }
 134     sc_subx(out, out->limb, sc_p, sc_p, chain);
 135 }
 136
 137 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
 138                                             const unsigned char *ser,
 139                                             unsigned int nbytes)
 140 {
 141     unsigned int i, j, k = 0;
 142
 143     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
 144         c448_word_t out = 0;
 145
 146         for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++)
 147             out |= ((c448_word_t) ser[k]) << (8 * j);
 148         s->limb[i] = out;
 149     }
 150 }
 151
 152 c448_error_t curve448_scalar_decode(
 153                                 curve448_scalar_t s,
 154                                 const unsigned char ser[C448_448_SCALAR_BYTES])
 155 {
 156     unsigned int i;
 157     c448_dsword_t accum = 0;
 158
 159     scalar_decode_short(s, ser, C448_448_SCALAR_BYTES);
 160     for (i = 0; i < C448_448_SCALAR_LIMBS; i++)
 161         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
 162     /* Here accum == 0 or -1 */
 163
 164     curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
 165
 166     return c448_succeed_if(~word_is_zero(accum));
 167 }
 168
 169 void curve448_scalar_destroy(curve448_scalar_t scalar)
 170 {
 171     OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
 172 }
 173
 174 void curve448_scalar_decode_long(curve448_scalar_t s,
 175                                  const unsigned char *ser, size_t ser_len)
 176 {
 177     size_t i;
 178     curve448_scalar_t t1, t2;
 179
 180     if (ser_len == 0) {
 181         curve448_scalar_copy(s, curve448_scalar_zero);
 182         return;
 183     }
 184
 185     i = ser_len - (ser_len % C448_448_SCALAR_BYTES);
 186     if (i == ser_len)
 187         i -= C448_448_SCALAR_BYTES;
 188
 189     scalar_decode_short(t1, &ser[i], ser_len - i);
 190
 191     if (ser_len == sizeof(curve448_scalar_t)) {
 192         assert(i == 0);
 193         /* ham-handed reduce */
 194         curve448_scalar_mul(s, t1, curve448_scalar_one);
 195         curve448_scalar_destroy(t1);
 196         return;
 197     }
 198
 199     while (i) {
 200         i -= C448_448_SCALAR_BYTES;
 201         sc_montmul(t1, t1, sc_r2);
 202         ignore_result(curve448_scalar_decode(t2, ser + i));
 203         curve448_scalar_add(t1, t1, t2);
 204     }
 205
 206     curve448_scalar_copy(s, t1);
 207     curve448_scalar_destroy(t1);
 208     curve448_scalar_destroy(t2);
 209 }
 210
 211 void curve448_scalar_encode(unsigned char ser[C448_448_SCALAR_BYTES],
 212                             const curve448_scalar_t s)
 213 {
 214     unsigned int i, j, k = 0;
 215
 216     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
 217         for (j = 0; j < sizeof(c448_word_t); j++, k++)
 218             ser[k] = s->limb[i] >> (8 * j);
 219     }
 220 }
 221
 222 void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
 223 {
 224     c448_word_t mask = -(a->limb[0] & 1);
 225     c448_dword_t chain = 0;
 226     unsigned int i;
 227     for (i = 0; i < C448_448_SCALAR_LIMBS; i++) {
 228         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
 229         out->limb[i] = chain;
 230         chain >>= C448_WORD_BITS;
 231     }
 232     for (i = 0; i < C448_448_SCALAR_LIMBS - 1; i++)
 233         out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
 234     out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);
 235 }