crypto/ec/curve448/field.h

   1 /*
   2  * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2014 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
  13 #ifndef OSSL_CRYPTO_EC_CURVE448_FIELD_H
  14 # define OSSL_CRYPTO_EC_CURVE448_FIELD_H
  15
  16 # include "internal/constant_time.h"
  17 # include <string.h>
  18 # include <assert.h>
  19 # include "word.h"
  20
  21 # define NLIMBS (64/sizeof(word_t))
  22 # define X_SER_BYTES 56
  23 # define SER_BYTES 56
  24
  25 # if defined(__GNUC__) || defined(__clang__)
  26 #  define INLINE_UNUSED __inline__ __attribute__((__unused__,__always_inline__))
  27 #  define RESTRICT __restrict__
  28 #  define ALIGNED __attribute__((__aligned__(16)))
  29 # else
  30 #  define INLINE_UNUSED ossl_inline
  31 #  define RESTRICT
  32 #  define ALIGNED
  33 # endif
  34
  35 typedef struct gf_s {
  36     word_t limb[NLIMBS];
  37 } ALIGNED gf_s, gf[1];
  38
  39 /* RFC 7748 support */
  40 # define X_PUBLIC_BYTES  X_SER_BYTES
  41 # define X_PRIVATE_BYTES X_PUBLIC_BYTES
  42 # define X_PRIVATE_BITS  448
  43
  44 static INLINE_UNUSED void gf_copy(gf out, const gf a)
  45 {
  46     *out = *a;
  47 }
  48
  49 static INLINE_UNUSED void gf_add_RAW(gf out, const gf a, const gf b);
  50 static INLINE_UNUSED void gf_sub_RAW(gf out, const gf a, const gf b);
  51 static INLINE_UNUSED void gf_bias(gf inout, int amount);
  52 static INLINE_UNUSED void gf_weak_reduce(gf inout);
  53
  54 void gf_strong_reduce(gf inout);
  55 void gf_add(gf out, const gf a, const gf b);
  56 void gf_sub(gf out, const gf a, const gf b);
  57 void gf_mul(gf_s * RESTRICT out, const gf a, const gf b);
  58 void gf_mulw_unsigned(gf_s * RESTRICT out, const gf a, uint32_t b);
  59 void gf_sqr(gf_s * RESTRICT out, const gf a);
  60 mask_t gf_isr(gf a, const gf x); /** a^2 x = 1, QNR, or 0 if x=0.  Return true if successful */
  61 mask_t gf_eq(const gf x, const gf y);
  62 mask_t gf_lobit(const gf x);
  63 mask_t gf_hibit(const gf x);
  64
  65 void gf_serialize(uint8_t *serial, const gf x, int with_highbit);
  66 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
  67                       uint8_t hi_nmask);
  68
  69
  70 # define LIMBPERM(i) (i)
  71 # if (ARCH_WORD_BITS == 32)
  72 #  include "arch_32/f_impl.h"    /* Bring in the inline implementations */
  73 #  define LIMB_MASK(i) (((1)<<LIMB_PLACE_VALUE(i))-1)
  74 # elif (ARCH_WORD_BITS == 64)
  75 #  include "arch_64/f_impl.h"    /* Bring in the inline implementations */
  76 #  define LIMB_MASK(i) (((1ULL)<<LIMB_PLACE_VALUE(i))-1)
  77 # endif
  78
  79 static const gf ZERO = {{{0}}}, ONE = {{{1}}};
  80
  81 /* Square x, n times. */
  82 static ossl_inline void gf_sqrn(gf_s * RESTRICT y, const gf x, int n)
  83 {
  84     gf tmp;
  85
  86     assert(n > 0);
  87     if (n & 1) {
  88         gf_sqr(y, x);
  89         n--;
  90     } else {
  91         gf_sqr(tmp, x);
  92         gf_sqr(y, tmp);
  93         n -= 2;
  94     }
  95     for (; n; n -= 2) {
  96         gf_sqr(tmp, y);
  97         gf_sqr(y, tmp);
  98     }
  99 }
 100
 101 # define gf_add_nr gf_add_RAW
 102
 103 /* Subtract mod p.  Bias by 2 and don't reduce  */
 104 static ossl_inline void gf_sub_nr(gf c, const gf a, const gf b)
 105 {
 106     gf_sub_RAW(c, a, b);
 107     gf_bias(c, 2);
 108     if (GF_HEADROOM < 3)
 109         gf_weak_reduce(c);
 110 }
 111
 112 /* Subtract mod p. Bias by amt but don't reduce.  */
 113 static ossl_inline void gf_subx_nr(gf c, const gf a, const gf b, int amt)
 114 {
 115     gf_sub_RAW(c, a, b);
 116     gf_bias(c, amt);
 117     if (GF_HEADROOM < amt + 1)
 118         gf_weak_reduce(c);
 119 }
 120
 121 /* Mul by signed int.  Not constant-time WRT the sign of that int. */
 122 static ossl_inline void gf_mulw(gf c, const gf a, int32_t w)
 123 {
 124     if (w > 0) {
 125         gf_mulw_unsigned(c, a, w);
 126     } else {
 127         gf_mulw_unsigned(c, a, -w);
 128         gf_sub(c, ZERO, c);
 129     }
 130 }
 131
 132 /* Constant time, x = is_z ? z : y */
 133 static ossl_inline void gf_cond_sel(gf x, const gf y, const gf z, mask_t is_z)
 134 {
 135     size_t i;
 136
 137     for (i = 0; i < NLIMBS; i++) {
 138 #if ARCH_WORD_BITS == 32
 139         x[0].limb[i] = constant_time_select_32(is_z, z[0].limb[i],
 140                                                y[0].limb[i]);
 141 #else
 142         /* Must be 64 bit */
 143         x[0].limb[i] = constant_time_select_64(is_z, z[0].limb[i],
 144                                                y[0].limb[i]);
 145 #endif
 146     }
 147 }
 148
 149 /* Constant time, if (neg) x=-x; */
 150 static ossl_inline void gf_cond_neg(gf x, mask_t neg)
 151 {
 152     gf y;
 153
 154     gf_sub(y, ZERO, x);
 155     gf_cond_sel(x, x, y, neg);
 156 }
 157
 158 /* Constant time, if (swap) (x,y) = (y,x); */
 159 static ossl_inline void gf_cond_swap(gf x, gf_s * RESTRICT y, mask_t swap)
 160 {
 161     size_t i;
 162
 163     for (i = 0; i < NLIMBS; i++) {
 164 #if ARCH_WORD_BITS == 32
 165         constant_time_cond_swap_32(swap, &(x[0].limb[i]), &(y->limb[i]));
 166 #else
 167         /* Must be 64 bit */
 168         constant_time_cond_swap_64(swap, &(x[0].limb[i]), &(y->limb[i]));
 169 #endif
 170     }
 171 }
 172
 173 #endif                          /* OSSL_CRYPTO_EC_CURVE448_FIELD_H */