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