Manual formatting tweaks to Curve448 code
[openssl.git] / crypto / ec / curve448 / scalar.c
index 5bc7b24..5077680 100644 (file)
@@ -1,15 +1,13 @@
-/**
- * @file ed448goldilocks/scalar.c
- * @author Mike Hamburg
+/*
+ * Copyright 2017 The OpenSSL Project Authors. All Rights Reserved.
+ * Copyright 2015-2016 Cryptography Research, Inc.
  *
- * @copyright
- *   Copyright (c) 2015-2016 Cryptography Research, Inc.  \n
- *   Released under the MIT License.  See LICENSE.txt for license information.
+ * Licensed under the OpenSSL license (the "License").  You may not use
+ * this file except in compliance with the License.  You can obtain a copy
+ * in the file LICENSE in the source distribution or at
+ * https://www.openssl.org/source/license.html
  *
- * @brief Decaf high-level functions.
- *
- * @warning This file was automatically generated in Python.
- * Please do not edit it.
+ * Originally written by Mike Hamburg
  */
 #include <openssl/crypto.h>
 
 #include "constant_time.h"
 #include "point_448.h"
 
-/* Template stuff */
-#define API_NS(_id) decaf_448_##_id
-#define SCALAR_BITS DECAF_448_SCALAR_BITS
-#define SCALAR_SER_BYTES DECAF_448_SCALAR_BYTES
-#define SCALAR_LIMBS DECAF_448_SCALAR_LIMBS
-#define scalar_t API_NS(scalar_t)
-
-static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t)0x3bd440fae918bc5ull;
-static const scalar_t sc_p = {{{
-    SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55), SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9), SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff), SC_LIMB(0x3fffffffffffffff)
-}}}, sc_r2 = {{{
-    SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9), SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838), SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af), SC_LIMB(0x3402a939f823b729)
-}}};
+static const decaf_word_t MONTGOMERY_FACTOR = (decaf_word_t) 0x3bd440fae918bc5;
+static const curve448_scalar_t sc_p = {
+    {
+        {
+            SC_LIMB(0x2378c292ab5844f3), SC_LIMB(0x216cc2728dc58f55),
+            SC_LIMB(0xc44edb49aed63690), SC_LIMB(0xffffffff7cca23e9),
+            SC_LIMB(0xffffffffffffffff), SC_LIMB(0xffffffffffffffff),
+            SC_LIMB(0x3fffffffffffffff)
+        }
+    }
+}, sc_r2 = {
+    {
+        {
+
+            SC_LIMB(0xe3539257049b9b60), SC_LIMB(0x7af32c4bc1b195d9),
+            SC_LIMB(0x0d66de2388ea1859), SC_LIMB(0xae17cf725ee4d838),
+            SC_LIMB(0x1a9cc14ba3c47c44), SC_LIMB(0x2052bcb7e4d070af),
+            SC_LIMB(0x3402a939f823b729)
+        }
+    }
+};
+
 /* End of template stuff */
 
-#define WBITS DECAF_WORD_BITS /* NB this may be different from ARCH_WORD_BITS */
+#define WBITS DECAF_WORD_BITS   /* NB this may be different from ARCH_WORD_BITS */
 
-const scalar_t API_NS(scalar_one) = {{{1}}}, API_NS(scalar_zero) = {{{0}}};
+const curve448_scalar_t curve448_scalar_one = {{{1}}};
+const curve448_scalar_t  curve448_scalar_zero = {{{0}}};
 
-/** {extra,accum} - sub +? p
+/*
+ * {extra,accum} - sub +? p
  * Must have extra <= 1
  */
-static DECAF_NOINLINE void sc_subx(
-    scalar_t out,
-    const decaf_word_t accum[SCALAR_LIMBS],
-    const scalar_t sub,
-    const scalar_t p,
-    decaf_word_t extra
-) {
+static void sc_subx(curve448_scalar_t out,
+                    const decaf_word_t accum[DECAF_448_SCALAR_LIMBS],
+                    const curve448_scalar_t sub,
+                    const curve448_scalar_t p, decaf_word_t extra)
+{
     decaf_dsword_t chain = 0;
     unsigned int i;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+    decaf_word_t borrow;
+
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         chain = (chain + accum[i]) - sub->limb[i];
         out->limb[i] = chain;
         chain >>= WBITS;
     }
-    decaf_word_t borrow = chain+extra; /* = 0 or -1 */
-    
+    borrow = chain + extra;     /* = 0 or -1 */
+
     chain = 0;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         chain = (chain + out->limb[i]) + (p->limb[i] & borrow);
         out->limb[i] = chain;
         chain >>= WBITS;
     }
 }
 
-static DECAF_NOINLINE void sc_montmul (
-    scalar_t out,
-    const scalar_t a,
-    const scalar_t b
-) {
-    unsigned int i,j;
-    decaf_word_t accum[SCALAR_LIMBS+1] = {0};
+static void sc_montmul(curve448_scalar_t out, const curve448_scalar_t a,
+                       const curve448_scalar_t b)
+{
+    unsigned int i, j;
+    decaf_word_t accum[DECAF_448_SCALAR_LIMBS + 1] = { 0 };
     decaf_word_t hi_carry = 0;
-    
-    for (i=0; i<SCALAR_LIMBS; i++) {
+
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         decaf_word_t mand = a->limb[i];
         const decaf_word_t *mier = b->limb;
-        
+
         decaf_dword_t chain = 0;
-        for (j=0; j<SCALAR_LIMBS; j++) {
-            chain += ((decaf_dword_t)mand)*mier[j] + accum[j];
+        for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
+            chain += ((decaf_dword_t) mand) * mier[j] + accum[j];
             accum[j] = chain;
             chain >>= WBITS;
         }
         accum[j] = chain;
-        
+
         mand = accum[0] * MONTGOMERY_FACTOR;
         chain = 0;
         mier = sc_p->limb;
-        for (j=0; j<SCALAR_LIMBS; j++) {
-            chain += (decaf_dword_t)mand*mier[j] + accum[j];
-            if (j) accum[j-1] = chain;
+        for (j = 0; j < DECAF_448_SCALAR_LIMBS; j++) {
+            chain += (decaf_dword_t) mand *mier[j] + accum[j];
+            if (j)
+                accum[j - 1] = chain;
             chain >>= WBITS;
         }
         chain += accum[j];
         chain += hi_carry;
-        accum[j-1] = chain;
+        accum[j - 1] = chain;
         hi_carry = chain >> WBITS;
     }
-    
-    sc_subx(out, accum, sc_p, sc_p, hi_carry);
-}
 
-void API_NS(scalar_mul) (
-    scalar_t out,
-    const scalar_t a,
-    const scalar_t b
-) {
-    sc_montmul(out,a,b);
-    sc_montmul(out,out,sc_r2);
+    sc_subx(out, accum, sc_p, sc_p, hi_carry);
 }
 
-/* PERF: could implement this */
-static DECAF_INLINE void sc_montsqr (scalar_t out, const scalar_t a) {
-    sc_montmul(out,a,a);
+void curve448_scalar_mul(curve448_scalar_t out, const curve448_scalar_t a,
+                         const curve448_scalar_t b)
+{
+    sc_montmul(out, a, b);
+    sc_montmul(out, out, sc_r2);
 }
 
-decaf_error_t API_NS(scalar_invert) (
-    scalar_t out,
-    const scalar_t a
-) {
-    /* Fermat's little theorem, sliding window.
-     * Sliding window is fine here because the modulus isn't secret.
-     */
-    const int SCALAR_WINDOW_BITS = 3;
-    scalar_t precmp[1<<SCALAR_WINDOW_BITS];
-    const int LAST = (1<<SCALAR_WINDOW_BITS)-1;
-
-    /* Precompute precmp = [a^1,a^3,...] */
-    sc_montmul(precmp[0],a,sc_r2);
-    if (LAST > 0) sc_montmul(precmp[LAST],precmp[0],precmp[0]);
-
-    int i;
-    for (i=1; i<=LAST; i++) {
-        sc_montmul(precmp[i],precmp[i-1],precmp[LAST]);
-    }
-    
-    /* Sliding window */
-    unsigned residue = 0, trailing = 0, started = 0;
-    for (i=SCALAR_BITS-1; i>=-SCALAR_WINDOW_BITS; i--) {
-        
-        if (started) sc_montsqr(out,out);
-        
-        decaf_word_t w = (i>=0) ? sc_p->limb[i/WBITS] : 0;
-        if (i >= 0 && i<WBITS) {
-            assert(w >= 2);
-            w-=2;
-        }
-        
-        residue = (residue<<1) | ((w>>(i%WBITS))&1);
-        if (residue>>SCALAR_WINDOW_BITS != 0) {
-            assert(trailing == 0);
-            trailing = residue;
-            residue = 0;
-        }
-        
-        if (trailing > 0 && (trailing & ((1<<SCALAR_WINDOW_BITS)-1)) == 0) {
-            if (started) {
-                sc_montmul(out,out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
-            } else {
-                API_NS(scalar_copy)(out,precmp[trailing>>(SCALAR_WINDOW_BITS+1)]);
-                started = 1;
-            }
-            trailing = 0;
-        }
-        trailing <<= 1;
-        
-    }
-    assert(residue==0);
-    assert(trailing==0);
-    
-    /* Demontgomerize */
-    sc_montmul(out,out,API_NS(scalar_one));
-    OPENSSL_cleanse(precmp, sizeof(precmp));
-    return decaf_succeed_if(~API_NS(scalar_eq)(out,API_NS(scalar_zero)));
-}
-
-void API_NS(scalar_sub) (
-    scalar_t out,
-    const scalar_t a,
-    const scalar_t b
-) {
+void curve448_scalar_sub(curve448_scalar_t out, const curve448_scalar_t a,
+                         const curve448_scalar_t b)
+{
     sc_subx(out, a->limb, b, sc_p, 0);
 }
 
-void API_NS(scalar_add) (
-    scalar_t out,
-    const scalar_t a,
-    const scalar_t b
-) {
+void curve448_scalar_add(curve448_scalar_t out, const curve448_scalar_t a,
+                         const curve448_scalar_t b)
+{
     decaf_dword_t chain = 0;
     unsigned int i;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         chain = (chain + a->limb[i]) + b->limb[i];
         out->limb[i] = chain;
         chain >>= WBITS;
@@ -198,146 +136,102 @@ void API_NS(scalar_add) (
     sc_subx(out, out->limb, sc_p, sc_p, chain);
 }
 
-void
-API_NS(scalar_set_unsigned) (
-    scalar_t out,
-    uint64_t w
-) {
-    memset(out,0,sizeof(scalar_t));
-    unsigned int i = 0;
-    for (; i<sizeof(uint64_t)/sizeof(decaf_word_t); i++) {
-        out->limb[i] = w;
-#if DECAF_WORD_BITS < 64
-        w >>= 8*sizeof(decaf_word_t);
-#endif
-    }
-}
-
-decaf_bool_t
-API_NS(scalar_eq) (
-    const scalar_t a,
-    const scalar_t b
-) {
-    decaf_word_t diff = 0;
-    unsigned int i;
-    for (i=0; i<SCALAR_LIMBS; i++) {
-        diff |= a->limb[i] ^ b->limb[i];
-    }
-    return mask_to_bool(word_is_zero(diff));
-}
+static ossl_inline void scalar_decode_short(curve448_scalar_t s,
+                                            const unsigned char *ser,
+                                            unsigned int nbytes)
+{
+    unsigned int i, j, k = 0;
 
-static DECAF_INLINE void scalar_decode_short (
-    scalar_t s,
-    const unsigned char *ser,
-    unsigned int nbytes
-) {
-    unsigned int i,j,k=0;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         decaf_word_t out = 0;
-        for (j=0; j<sizeof(decaf_word_t) && k<nbytes; j++,k++) {
-            out |= ((decaf_word_t)ser[k])<<(8*j);
-        }
+
+        for (j = 0; j < sizeof(decaf_word_t) && k < nbytes; j++, k++)
+            out |= ((decaf_word_t) ser[k]) << (8 * j);
         s->limb[i] = out;
     }
 }
 
-decaf_error_t API_NS(scalar_decode)(
-    scalar_t s,
-    const unsigned char ser[SCALAR_SER_BYTES]
-{
+decaf_error_t curve448_scalar_decode(
+                                curve448_scalar_t s,
+                                const unsigned char ser[DECAF_448_SCALAR_BYTES])
+{
     unsigned int i;
-    scalar_decode_short(s, ser, SCALAR_SER_BYTES);
     decaf_dsword_t accum = 0;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+
+    scalar_decode_short(s, ser, DECAF_448_SCALAR_BYTES);
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++)
         accum = (accum + s->limb[i] - sc_p->limb[i]) >> WBITS;
-    }
     /* Here accum == 0 or -1 */
-    
-    API_NS(scalar_mul)(s,s,API_NS(scalar_one)); /* ham-handed reduce */
-    
+
+    curve448_scalar_mul(s, s, curve448_scalar_one); /* ham-handed reduce */
+
     return decaf_succeed_if(~word_is_zero(accum));
 }
 
-void API_NS(scalar_destroy) (
-    scalar_t scalar
-) {
-    OPENSSL_cleanse(scalar, sizeof(scalar_t));
+void curve448_scalar_destroy(curve448_scalar_t scalar)
+{
+    OPENSSL_cleanse(scalar, sizeof(curve448_scalar_t));
 }
 
-void API_NS(scalar_decode_long)(
-    scalar_t s,
-    const unsigned char *ser,
-    size_t ser_len
-) {
+void curve448_scalar_decode_long(curve448_scalar_t s,
+                                 const unsigned char *ser, size_t ser_len)
+{
+    size_t i;
+    curve448_scalar_t t1, t2;
+
     if (ser_len == 0) {
-        API_NS(scalar_copy)(s, API_NS(scalar_zero));
+        curve448_scalar_copy(s, curve448_scalar_zero);
         return;
     }
-    
-    size_t i;
-    scalar_t t1, t2;
 
-    i = ser_len - (ser_len%SCALAR_SER_BYTES);
-    if (i==ser_len) i -= SCALAR_SER_BYTES;
-    
-    scalar_decode_short(t1, &ser[i], ser_len-i);
+    i = ser_len - (ser_len % DECAF_448_SCALAR_BYTES);
+    if (i == ser_len)
+        i -= DECAF_448_SCALAR_BYTES;
+
+    scalar_decode_short(t1, &ser[i], ser_len - i);
 
-    if (ser_len == sizeof(scalar_t)) {
-        assert(i==0);
+    if (ser_len == sizeof(curve448_scalar_t)) {
+        assert(i == 0);
         /* ham-handed reduce */
-        API_NS(scalar_mul)(s,t1,API_NS(scalar_one));
-        API_NS(scalar_destroy)(t1);
+        curve448_scalar_mul(s, t1, curve448_scalar_one);
+        curve448_scalar_destroy(t1);
         return;
     }
 
     while (i) {
-        i -= SCALAR_SER_BYTES;
-        sc_montmul(t1,t1,sc_r2);
-        ignore_result( API_NS(scalar_decode)(t2, ser+i) );
-        API_NS(scalar_add)(t1, t1, t2);
+        i -= DECAF_448_SCALAR_BYTES;
+        sc_montmul(t1, t1, sc_r2);
+        ignore_result(curve448_scalar_decode(t2, ser + i));
+        curve448_scalar_add(t1, t1, t2);
     }
 
-    API_NS(scalar_copy)(s, t1);
-    API_NS(scalar_destroy)(t1);
-    API_NS(scalar_destroy)(t2);
+    curve448_scalar_copy(s, t1);
+    curve448_scalar_destroy(t1);
+    curve448_scalar_destroy(t2);
 }
 
-void API_NS(scalar_encode)(
-    unsigned char ser[SCALAR_SER_BYTES],
-    const scalar_t s
-) {
-    unsigned int i,j,k=0;
-    for (i=0; i<SCALAR_LIMBS; i++) {
-        for (j=0; j<sizeof(decaf_word_t); j++,k++) {
-            ser[k] = s->limb[i] >> (8*j);
-        }
-    }
-}
+void curve448_scalar_encode(unsigned char ser[DECAF_448_SCALAR_BYTES],
+                            const curve448_scalar_t s)
+{
+    unsigned int i, j, k = 0;
 
-void API_NS(scalar_cond_sel) (
-    scalar_t out,
-    const scalar_t a,
-    const scalar_t b,
-    decaf_bool_t pick_b
-) {
-    constant_time_select(out,a,b,sizeof(scalar_t),bool_to_mask(pick_b),sizeof(out->limb[0]));
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
+        for (j = 0; j < sizeof(decaf_word_t); j++, k++)
+            ser[k] = s->limb[i] >> (8 * j);
+    }
 }
 
-void API_NS(scalar_halve) (
-    scalar_t out,
-    const scalar_t a
-) {
+void curve448_scalar_halve(curve448_scalar_t out, const curve448_scalar_t a)
+{
     decaf_word_t mask = -(a->limb[0] & 1);
     decaf_dword_t chain = 0;
     unsigned int i;
-    for (i=0; i<SCALAR_LIMBS; i++) {
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS; i++) {
         chain = (chain + a->limb[i]) + (sc_p->limb[i] & mask);
         out->limb[i] = chain;
         chain >>= DECAF_WORD_BITS;
     }
-    for (i=0; i<SCALAR_LIMBS-1; i++) {
-        out->limb[i] = out->limb[i]>>1 | out->limb[i+1]<<(WBITS-1);
-    }
-    out->limb[i] = out->limb[i]>>1 | chain<<(WBITS-1);
+    for (i = 0; i < DECAF_448_SCALAR_LIMBS - 1; i++)
+        out->limb[i] = out->limb[i] >> 1 | out->limb[i + 1] << (WBITS - 1);
+    out->limb[i] = out->limb[i] >> 1 | chain << (WBITS - 1);
 }
-