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 "word.h"
  15 #include "constant_time.h"
  16 #include <decaf.h>
  17
  18 /* Template stuff */
  19 #define API_NS(_id) decaf_448_##_id
  20 #define SCALAR_BITS DECAF_448_SCALAR_BITS
  21 #define SCALAR_SER_BYTES DECAF_448_SCALAR_BYTES
  22 #define SCALAR_LIMBS DECAF_448_SCALAR_LIMBS
  23 #define scalar_t API_NS(scalar_t)
  24
  25 static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t)0x3bd440fae918bc5ull;
  26 static const scalar_t sc_p = {{{
  27     SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55), SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9), SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff), SC_LIMB(0x3fffffffffffffff)
  28 }}}, sc_r2 = {{{
  29     SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9), SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838), SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af), SC_LIMB(0x3402a939f823b729)
  30 }}};
  31 /* End of template stuff */
  32
  33 #define WBITS DECAF_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */
  34
  35 const scalar_t API_NS(scalar_one) = {{{1}}}, API_NS(scalar_zero) = {{{0}}};
  36
  37 /** {extra,accum} - sub +? p
  38  * Must have extra <= 1
  39  */
  40 static DECAF_NOINLINE void sc_subx(
  41     scalar_t out,
  42     const decaf_word_t accum[SCALAR_LIMBS],
  43     const scalar_t sub,
  44     const scalar_t p,
  45     decaf_word_t extra
  46 ) {
  47     decaf_dsword_t chain = 0;
  48     unsigned int i;
  49     for (i=0; i<SCALAR_LIMBS; i++) {
  50         chain = (chain + accum[i]) - sub->limb[i];
  51         out->limb[i] = chain;
  52         chain >>= WBITS;
  53     }
  54     decaf_word_t borrow = chain+extra; /* = 0 or -1 */
  55
  56     chain = 0;
  57     for (i=0; i<SCALAR_LIMBS; i++) {
  58         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
  59         out->limb[i] = chain;
  60         chain >>= WBITS;
  61     }
  62 }
  63
  64 static DECAF_NOINLINE void sc_montmul (
  65     scalar_t out,
  66     const scalar_t a,
  67     const scalar_t b
  68 ) {
  69     unsigned int i,j;
  70     decaf_word_t accum[SCALAR_LIMBS+1] = {0};
  71     decaf_word_t hi_carry = 0;
  72
  73     for (i=0; i<SCALAR_LIMBS; i++) {
  74         decaf_word_t mand = a->limb[i];
  75         const decaf_word_t *mier = b->limb;
  76
  77         decaf_dword_t chain = 0;
  78         for (j=0; j<SCALAR_LIMBS; j++) {
  79             chain += ((decaf_dword_t)mand)*mier[j] + accum[j];
  80             accum[j] = chain;
  81             chain >>= WBITS;
  82         }
  83         accum[j] = chain;
  84
  85         mand = accum[0] * MONTGOMERY_FACTOR;
  86         chain = 0;
  87         mier = sc_p->limb;
  88         for (j=0; j<SCALAR_LIMBS; j++) {
  89             chain += (decaf_dword_t)mand*mier[j] + accum[j];
  90             if (j) accum[j-1] = chain;
  91             chain >>= WBITS;
  92         }
  93         chain += accum[j];
  94         chain += hi_carry;
  95         accum[j-1] = chain;
  96         hi_carry = chain >> WBITS;
  97     }
  98
  99     sc_subx(out, accum, sc_p, sc_p, hi_carry);
 100 }
 101
 102 void API_NS(scalar_mul) (
 103     scalar_t out,
 104     const scalar_t a,
 105     const scalar_t b
 106 ) {
 107     sc_montmul(out,a,b);
 108     sc_montmul(out,out,sc_r2);
 109 }
 110
 111 /* PERF: could implement this */
 112 static DECAF_INLINE void sc_montsqr (scalar_t out, const scalar_t a) {
 113     sc_montmul(out,a,a);
 114 }
 115
 116 decaf_error_t API_NS(scalar_invert) (
 117     scalar_t out,
 118     const scalar_t a
 119 ) {
 120     /* Fermat's little theorem, sliding window.
 121      * Sliding window is fine here because the modulus isn't secret.
 122      */
 123     const int SCALAR_WINDOW_BITS = 3;
 124     scalar_t precmp[1<<SCALAR_WINDOW_BITS];
 125     const int LAST = (1<<SCALAR_WINDOW_BITS)-1;
 126
 127     /* Precompute precmp = [a^1,a^3,...] */
 128     sc_montmul(precmp[0],a,sc_r2);
 129     if (LAST > 0) sc_montmul(precmp[LAST],precmp[0],precmp[0]);
 130
 131     int i;
 132     for (i=1; i<=LAST; i++) {
 133         sc_montmul(precmp[i],precmp[i-1],precmp[LAST]);
 134     }
 135
 136     /* Sliding window */
 137     unsigned residue = 0, trailing = 0, started = 0;
 138     for (i=SCALAR_BITS-1; i>=-SCALAR_WINDOW_BITS; i--) {
 139
 140         if (started) sc_montsqr(out,out);
 141
 142         decaf_word_t w = (i>=0) ? sc_p->limb[i/WBITS] : 0;
 143         if (i >= 0 && i<WBITS) {
 144             assert(w >= 2);
 145             w-=2;
 146         }
 147
 148         residue = (residue<<1) | ((w>>(i%WBITS))&1);
 149         if (residue>>SCALAR_WINDOW_BITS != 0) {
 150             assert(trailing == 0);
 151             trailing = residue;
 152             residue = 0;
 153         }
 154
 155         if (trailing > 0 && (trailing & ((1<<SCALAR_WINDOW_BITS)-1)) == 0) {
 156             if (started) {
 157                 sc_montmul(out,out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
 158             } else {
 159                 API_NS(scalar_copy)(out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
 160                 started = 1;
 161             }
 162             trailing = 0;
 163         }
 164         trailing <<= 1;
 165
 166     }
 167     assert(residue==0);
 168     assert(trailing==0);
 169
 170     /* Demontgomerize */
 171     sc_montmul(out,out,API_NS(scalar_one));
 172     decaf_bzero(precmp, sizeof(precmp));
 173     return decaf_succeed_if(~API_NS(scalar_eq)(out,API_NS(scalar_zero)));
 174 }
 175
 176 void API_NS(scalar_sub) (
 177     scalar_t out,
 178     const scalar_t a,
 179     const scalar_t b
 180 ) {
 181     sc_subx(out, a->limb, b, sc_p, 0);
 182 }
 183
 184 void API_NS(scalar_add) (
 185     scalar_t out,
 186     const scalar_t a,
 187     const scalar_t b
 188 ) {
 189     decaf_dword_t chain = 0;
 190     unsigned int i;
 191     for (i=0; i<SCALAR_LIMBS; i++) {
 192         chain = (chain + a->limb[i]) + b->limb[i];
 193         out->limb[i] = chain;
 194         chain >>= WBITS;
 195     }
 196     sc_subx(out, out->limb, sc_p, sc_p, chain);
 197 }
 198
 199 void
 200 API_NS(scalar_set_unsigned) (
 201     scalar_t out,
 202     uint64_t w
 203 ) {
 204     memset(out,0,sizeof(scalar_t));
 205     unsigned int i = 0;
 206     for (; i<sizeof(uint64_t)/sizeof(decaf_word_t); i++) {
 207         out->limb[i] = w;
 208 #if DECAF_WORD_BITS < 64
 209         w >>= 8*sizeof(decaf_word_t);
 210 #endif
 211     }
 212 }
 213
 214 decaf_bool_t
 215 API_NS(scalar_eq) (
 216     const scalar_t a,
 217     const scalar_t b
 218 ) {
 219     decaf_word_t diff = 0;
 220     unsigned int i;
 221     for (i=0; i<SCALAR_LIMBS; i++) {
 222         diff |= a->limb[i] ^ b->limb[i];
 223     }
 224     return mask_to_bool(word_is_zero(diff));
 225 }
 226
 227 static DECAF_INLINE void scalar_decode_short (
 228     scalar_t s,
 229     const unsigned char *ser,
 230     unsigned int nbytes
 231 ) {
 232     unsigned int i,j,k=0;
 233     for (i=0; i<SCALAR_LIMBS; i++) {
 234         decaf_word_t out = 0;
 235         for (j=0; j<sizeof(decaf_word_t) && k<nbytes; j++,k++) {
 236             out |= ((decaf_word_t)ser[k])<<(8*j);
 237         }
 238         s->limb[i] = out;
 239     }
 240 }
 241
 242 decaf_error_t API_NS(scalar_decode)(
 243     scalar_t s,
 244     const unsigned char ser[SCALAR_SER_BYTES]
 245 ) {
 246     unsigned int i;
 247     scalar_decode_short(s, ser, SCALAR_SER_BYTES);
 248     decaf_dsword_t accum = 0;
 249     for (i=0; i<SCALAR_LIMBS; i++) {
 250         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
 251     }
 252     /* Here accum == 0 or -1 */
 253
 254     API_NS(scalar_mul)(s,s,API_NS(scalar_one)); /* ham-handed reduce */
 255
 256     return decaf_succeed_if(~word_is_zero(accum));
 257 }
 258
 259 void API_NS(scalar_destroy) (
 260     scalar_t scalar
 261 ) {
 262     decaf_bzero(scalar, sizeof(scalar_t));
 263 }
 264
 265 void API_NS(scalar_decode_long)(
 266     scalar_t s,
 267     const unsigned char *ser,
 268     size_t ser_len
 269 ) {
 270     if (ser_len == 0) {
 271         API_NS(scalar_copy)(s, API_NS(scalar_zero));
 272         return;
 273     }
 274
 275     size_t i;
 276     scalar_t t1, t2;
 277
 278     i = ser_len - (ser_len%SCALAR_SER_BYTES);
 279     if (i==ser_len) i -= SCALAR_SER_BYTES;
 280
 281     scalar_decode_short(t1, &ser[i], ser_len-i);
 282
 283     if (ser_len == sizeof(scalar_t)) {
 284         assert(i==0);
 285         /* ham-handed reduce */
 286         API_NS(scalar_mul)(s,t1,API_NS(scalar_one));
 287         API_NS(scalar_destroy)(t1);
 288         return;
 289     }
 290
 291     while (i) {
 292         i -= SCALAR_SER_BYTES;
 293         sc_montmul(t1,t1,sc_r2);
 294         ignore_result( API_NS(scalar_decode)(t2, ser+i) );
 295         API_NS(scalar_add)(t1, t1, t2);
 296     }
 297
 298     API_NS(scalar_copy)(s, t1);
 299     API_NS(scalar_destroy)(t1);
 300     API_NS(scalar_destroy)(t2);
 301 }
 302
 303 void API_NS(scalar_encode)(
 304     unsigned char ser[SCALAR_SER_BYTES],
 305     const scalar_t s
 306 ) {
 307     unsigned int i,j,k=0;
 308     for (i=0; i<SCALAR_LIMBS; i++) {
 309         for (j=0; j<sizeof(decaf_word_t); j++,k++) {
 310             ser[k] = s->limb[i] >> (8*j);
 311         }
 312     }
 313 }
 314
 315 void API_NS(scalar_cond_sel) (
 316     scalar_t out,
 317     const scalar_t a,
 318     const scalar_t b,
 319     decaf_bool_t pick_b
 320 ) {
 321     constant_time_select(out,a,b,sizeof(scalar_t),bool_to_mask(pick_b),sizeof(out->limb[0]));
 322 }
 323
 324 void API_NS(scalar_halve) (
 325     scalar_t out,
 326     const scalar_t a
 327 ) {
 328     decaf_word_t mask = -(a->limb[0] & 1);
 329     decaf_dword_t chain = 0;
 330     unsigned int i;
 331     for (i=0; i<SCALAR_LIMBS; i++) {
 332         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
 333         out->limb[i] = chain;
 334         chain >>= DECAF_WORD_BITS;
 335     }
 336     for (i=0; i<SCALAR_LIMBS-1; i++) {
 337         out->limb[i] = out->limb[i]>>1 | out->limb[i+1]<<(WBITS-1);
 338     }
 339     out->limb[i] = out->limb[i]>>1 | chain<<(WBITS-1);
 340 }
 341