crypto/ec/curve448/scalar.c

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