crypto/ec/curve448/scalar.c

   1 /*
   2  * Copyright 2017-2021 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2015-2016 Cryptography Research, Inc.
   4  *
   5  * Licensed under the Apache License 2.0 (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) 0x3bd440fae918bc5ULL;
  18 static const curve448_scalar_t sc_p = {
  19     {
  20         {
  21             SC_LIMB(0x2378c292ab5844f3ULL), SC_LIMB(0x216cc2728dc58f55ULL),
  22             SC_LIMB(0xc44edb49aed63690ULL), SC_LIMB(0xffffffff7cca23e9ULL),
  23             SC_LIMB(0xffffffffffffffffULL), SC_LIMB(0xffffffffffffffffULL),
  24             SC_LIMB(0x3fffffffffffffffULL)
  25         }
  26     }
  27 }, sc_r2 = {
  28     {
  29         {
  30
  31             SC_LIMB(0xe3539257049b9b60ULL), SC_LIMB(0x7af32c4bc1b195d9ULL),
  32             SC_LIMB(0x0d66de2388ea1859ULL), SC_LIMB(0xae17cf725ee4d838ULL),
  33             SC_LIMB(0x1a9cc14ba3c47c44ULL), SC_LIMB(0x2052bcb7e4d070afULL),
  34             SC_LIMB(0x3402a939f823b729ULL)
  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 ossl_curve448_scalar_one = {{{1}}};
  42 const curve448_scalar_t ossl_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 ossl_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
 117 ossl_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
 124 ossl_curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
 125                          const curve448_scalar_t b)
 126 {
 127     c448_dword_t chain = 0;
 128     unsigned int i;
 129
 130     for (i = 0; i < C448_SCALAR_LIMBS; i++) {
 131         chain = (chain + a->limb[i]) + b->limb[i];
 132         out->limb[i] = (c448_word_t)chain;
 133         chain >>= WBITS;
 134     }
 135     sc_subx(out, out->limb, sc_p, sc_p, (c448_word_t)chain);
 136 }
 137
 138 static ossl_inline void scalar_decode_short(curve448_scalar_t s,
 139                                             const unsigned char *ser,
 140                                             size_t nbytes)
 141 {
 142     size_t i, j, k = 0;
 143
 144     for (i = 0; i < C448_SCALAR_LIMBS; i++) {
 145         c448_word_t out = 0;
 146
 147         for (j = 0; j < sizeof(c448_word_t) && k < nbytes; j++, k++)
 148             out |= ((c448_word_t) ser[k]) << (8 * j);
 149         s->limb[i] = out;
 150     }
 151 }
 152
 153 c448_error_t
 154 ossl_curve448_scalar_decode(curve448_scalar_t s,
 155                             const unsigned char ser[C448_SCALAR_BYTES])
 156 {
 157     unsigned int i;
 158     c448_dsword_t accum = 0;
 159
 160     scalar_decode_short(s, ser, C448_SCALAR_BYTES);
 161     for (i = 0; i < C448_SCALAR_LIMBS; i++)
 162         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
 163     /* Here accum == 0 or -1 */
 164
 165     ossl_curve448_scalar_mul(s, s, ossl_curve448_scalar_one); /* ham-handed reduce */
 166
 167     return c448_succeed_if(~word_is_zero((uint32_t)accum));
 168 }
 169
 170 void ossl_curve448_scalar_destroy(curve448_scalar_t scalar)
 171 {
 172     OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
 173 }
 174
 175 void
 176 ossl_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, ossl_curve448_scalar_zero);
 184         return;
 185     }
 186
 187     i = ser_len - (ser_len % C448_SCALAR_BYTES);
 188     if (i == ser_len)
 189         i -= C448_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         ossl_curve448_scalar_mul(s, t1, ossl_curve448_scalar_one);
 197         ossl_curve448_scalar_destroy(t1);
 198         return;
 199     }
 200
 201     while (i) {
 202         i -= C448_SCALAR_BYTES;
 203         sc_montmul(t1, t1, sc_r2);
 204         (void)ossl_curve448_scalar_decode(t2, ser + i);
 205         ossl_curve448_scalar_add(t1, t1, t2);
 206     }
 207
 208     curve448_scalar_copy(s, t1);
 209     ossl_curve448_scalar_destroy(t1);
 210     ossl_curve448_scalar_destroy(t2);
 211 }
 212
 213 void
 214 ossl_curve448_scalar_encode(unsigned char ser[C448_SCALAR_BYTES],
 215                             const curve448_scalar_t s)
 216 {
 217     unsigned int i, j, k = 0;
 218
 219     for (i = 0; i < C448_SCALAR_LIMBS; i++) {
 220         for (j = 0; j < sizeof(c448_word_t); j++, k++)
 221             ser[k] = s->limb[i] >> (8 * j);
 222     }
 223 }
 224
 225 void
 226 ossl_curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
 227 {
 228     c448_word_t mask = 0 - (a->limb[0] & 1);
 229     c448_dword_t chain = 0;
 230     unsigned int i;
 231
 232     for (i = 0; i < C448_SCALAR_LIMBS; i++) {
 233         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
 234         out->limb[i] = (c448_word_t)chain;
 235         chain >>= C448_WORD_BITS;
 236     }
 237     for (i = 0; i < C448_SCALAR_LIMBS - 1; i++)
 238         out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
 239     out->limb[i] = out->limb[i] >> 1 | (c448_word_t)(chain << (WBITS - 1));
 240 }