crypto/ec/curve448/f_generic.c

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