crypto/ec/curve448/f_generic.c

   1 /**
   2  * @file p448/f_generic.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 Generic arithmetic which has to be compiled per field.
  10  *
  11  * @warning This file was automatically generated in Python.
  12  * Please do not edit it.
  13  */
  14 #include "field.h"
  15
  16 static const gf MODULUS = {FIELD_LITERAL(
  17     0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff, 0xfffffffffffffe, 0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff
  18 )};
  19
  20 /** Serialize to wire format. */
  21 void gf_serialize (uint8_t serial[SER_BYTES], const gf x, int with_hibit) {
  22     unsigned int j=0, fill=0;
  23     dword_t buffer = 0;
  24     unsigned int i;
  25     gf red;
  26
  27     gf_copy(red, x);
  28     gf_strong_reduce(red);
  29     if (!with_hibit) { assert(gf_hibit(red) == 0); }
  30
  31     UNROLL for (i=0; i<(with_hibit ? X_SER_BYTES : SER_BYTES); i++) {
  32         if (fill < 8 && j < NLIMBS) {
  33             buffer |= ((dword_t)red->limb[LIMBPERM(j)]) << fill;
  34             fill += LIMB_PLACE_VALUE(LIMBPERM(j));
  35             j++;
  36         }
  37         serial[i] = buffer;
  38         fill -= 8;
  39         buffer >>= 8;
  40     }
  41 }
  42
  43 /** Return high bit of x = low bit of 2x mod p */
  44 mask_t gf_hibit(const gf x) {
  45     gf y;
  46     gf_add(y,x,x);
  47     gf_strong_reduce(y);
  48     return -(y->limb[0]&1);
  49 }
  50
  51 /** Return high bit of x = low bit of 2x mod p */
  52 mask_t gf_lobit(const gf x) {
  53     gf y;
  54     gf_copy(y,x);
  55     gf_strong_reduce(y);
  56     return -(y->limb[0]&1);
  57 }
  58
  59 /** Deserialize from wire format; return -1 on success and 0 on failure. */
  60 mask_t gf_deserialize (gf x, const uint8_t serial[SER_BYTES], int with_hibit, uint8_t hi_nmask) {
  61     unsigned int j=0, fill=0;
  62     dword_t buffer = 0;
  63     dsword_t scarry = 0;
  64     const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
  65     unsigned int i;
  66     mask_t succ;
  67
  68     UNROLL for (i=0; i<NLIMBS; i++) {
  69         UNROLL while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
  70             uint8_t sj = serial[j];
  71             if (j==nbytes-1) sj &= ~hi_nmask;
  72             buffer |= ((dword_t)sj) << fill;
  73             fill += 8;
  74             j++;
  75         }
  76         x->limb[LIMBPERM(i)] = (i<NLIMBS-1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer;
  77         fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
  78         buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
  79         scarry = (scarry + x->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]) >> (8*sizeof(word_t));
  80     }
  81     succ = with_hibit ? -(mask_t)1 : ~gf_hibit(x);
  82     return succ & word_is_zero(buffer) & ~word_is_zero(scarry);
  83 }
  84
  85 /** Reduce to canonical form. */
  86 void gf_strong_reduce (gf a) {
  87     dsword_t scarry;
  88     word_t scarry_0;
  89     dword_t carry = 0;
  90     unsigned int i;
  91
  92     /* first, clear high */
  93     gf_weak_reduce(a); /* Determined to have negligible perf impact. */
  94
  95     /* now the total is less than 2p */
  96
  97     /* compute total_value - p.  No need to reduce mod p. */
  98     scarry = 0;
  99     for (i=0; i<NLIMBS; i++) {
 100         scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
 101         a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
 102         scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
 103     }
 104
 105     /* uncommon case: it was >= p, so now scarry = 0 and this = x
 106      * common case: it was < p, so now scarry = -1 and this = x - p + 2^255
 107      * so let's add back in p.  will carry back off the top for 2^255.
 108      */
 109     assert(word_is_zero(scarry) | word_is_zero(scarry+1));
 110
 111     scarry_0 = scarry;
 112
 113     /* add it back */
 114     for (i=0; i<NLIMBS; i++) {
 115         carry = carry + a->limb[LIMBPERM(i)] + (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
 116         a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
 117         carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
 118     }
 119
 120     assert(word_is_zero(carry + scarry_0));
 121 }
 122
 123 /** Subtract two gf elements d=a-b */
 124 void gf_sub (gf d, const gf a, const gf b) {
 125     gf_sub_RAW ( d, a, b );
 126     gf_bias( d, 2 );
 127     gf_weak_reduce ( d );
 128 }
 129
 130 /** Add two field elements d = a+b */
 131 void gf_add (gf d, const gf a, const gf b) {
 132     gf_add_RAW ( d, a, b );
 133     gf_weak_reduce ( d );
 134 }
 135
 136 /** Compare a==b */
 137 mask_t gf_eq(const gf a, const gf b) {
 138     gf c;
 139     mask_t ret=0;
 140     unsigned int i;
 141
 142     gf_sub(c,a,b);
 143     gf_strong_reduce(c);
 144
 145     for (i=0; i<NLIMBS; i++) {
 146         ret |= c->limb[LIMBPERM(i)];
 147     }
 148
 149     return word_is_zero(ret);
 150 }