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