crypto/ec/curve448/scalar.c

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