crypto/ec/curve448/f_generic.c

   1 /*
   2  * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
   3  * Copyright 2015-2016 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 #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     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     for (i = 0; i < (with_hibit ? X_SER_BYTES : SER_BYTES); i++) {
  34         if (fill < 8 && j < NLIMBS) {
  35             buffer |= ((dword_t) red->limb[LIMBPERM(j)]) << fill;
  36             fill += LIMB_PLACE_VALUE(LIMBPERM(j));
  37             j++;
  38         }
  39         serial[i] = (uint8_t)buffer;
  40         fill -= 8;
  41         buffer >>= 8;
  42     }
  43 }
  44
  45 /* Return high bit of x = low bit of 2x mod p */
  46 mask_t gf_hibit(const gf x)
  47 {
  48     gf y;
  49
  50     gf_add(y, x, x);
  51     gf_strong_reduce(y);
  52     return 0 - (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
  60     gf_copy(y, x);
  61     gf_strong_reduce(y);
  62     return 0 - (y->limb[0] & 1);
  63 }
  64
  65 /* Deserialize from wire format; return -1 on success and 0 on failure. */
  66 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
  67                       uint8_t hi_nmask)
  68 {
  69     unsigned int j = 0, fill = 0;
  70     dword_t buffer = 0;
  71     dsword_t scarry = 0;
  72     const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
  73     unsigned int i;
  74     mask_t succ;
  75
  76     for (i = 0; i < NLIMBS; i++) {
  77         while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
  78             uint8_t sj;
  79
  80             sj = serial[j];
  81             if (j == nbytes - 1)
  82                 sj &= ~hi_nmask;
  83             buffer |= ((dword_t) sj) << fill;
  84             fill += 8;
  85             j++;
  86         }
  87         x->limb[LIMBPERM(i)] = (word_t)
  88             ((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer);
  89         fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
  90         buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
  91         scarry =
  92             (scarry + x->limb[LIMBPERM(i)] -
  93              MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t));
  94     }
  95     succ = with_hibit ? 0 - (mask_t) 1 : ~gf_hibit(x);
  96     return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry);
  97 }
  98
  99 /* Reduce to canonical form. */
 100 void gf_strong_reduce(gf a)
 101 {
 102     dsword_t scarry;
 103     word_t scarry_0;
 104     dword_t carry = 0;
 105     unsigned int i;
 106
 107     /* first, clear high */
 108     gf_weak_reduce(a);          /* Determined to have negligible perf impact. */
 109
 110     /* now the total is less than 2p */
 111
 112     /* compute total_value - p.  No need to reduce mod p. */
 113     scarry = 0;
 114     for (i = 0; i < NLIMBS; i++) {
 115         scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
 116         a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
 117         scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
 118     }
 119
 120     /*
 121      * uncommon case: it was >= p, so now scarry = 0 and this = x common case:
 122      * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add
 123      * back in p.  will carry back off the top for 2^255.
 124      */
 125     assert(scarry == 0 || scarry == -1);
 126
 127     scarry_0 = (word_t)scarry;
 128
 129     /* add it back */
 130     for (i = 0; i < NLIMBS; i++) {
 131         carry =
 132             carry + a->limb[LIMBPERM(i)] +
 133             (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
 134         a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
 135         carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
 136     }
 137
 138     assert(carry < 2 && ((word_t)carry + scarry_0) == 0);
 139 }
 140
 141 /* Subtract two gf elements d=a-b */
 142 void gf_sub(gf d, const gf a, const gf b)
 143 {
 144     gf_sub_RAW(d, a, b);
 145     gf_bias(d, 2);
 146     gf_weak_reduce(d);
 147 }
 148
 149 /* Add two field elements d = a+b */
 150 void gf_add(gf d, const gf a, const gf b)
 151 {
 152     gf_add_RAW(d, a, b);
 153     gf_weak_reduce(d);
 154 }
 155
 156 /* Compare a==b */
 157 mask_t gf_eq(const gf a, const gf b)
 158 {
 159     gf c;
 160     mask_t ret = 0;
 161     unsigned int i;
 162
 163     gf_sub(c, a, b);
 164     gf_strong_reduce(c);
 165
 166     for (i = 0; i < NLIMBS; i++)
 167         ret |= c->limb[LIMBPERM(i)];
 168
 169     return word_is_zero(ret);
 170 }
 171
 172 mask_t gf_isr(gf a, const gf x)
 173 {
 174     gf L0, L1, L2;
 175
 176     gf_sqr(L1, x);
 177     gf_mul(L2, x, L1);
 178     gf_sqr(L1, L2);
 179     gf_mul(L2, x, L1);
 180     gf_sqrn(L1, L2, 3);
 181     gf_mul(L0, L2, L1);
 182     gf_sqrn(L1, L0, 3);
 183     gf_mul(L0, L2, L1);
 184     gf_sqrn(L2, L0, 9);
 185     gf_mul(L1, L0, L2);
 186     gf_sqr(L0, L1);
 187     gf_mul(L2, x, L0);
 188     gf_sqrn(L0, L2, 18);
 189     gf_mul(L2, L1, L0);
 190     gf_sqrn(L0, L2, 37);
 191     gf_mul(L1, L2, L0);
 192     gf_sqrn(L0, L1, 37);
 193     gf_mul(L1, L2, L0);
 194     gf_sqrn(L0, L1, 111);
 195     gf_mul(L2, L1, L0);
 196     gf_sqr(L0, L2);
 197     gf_mul(L1, x, L0);
 198     gf_sqrn(L0, L1, 223);
 199     gf_mul(L1, L2, L0);
 200     gf_sqr(L2, L1);
 201     gf_mul(L0, L2, x);
 202     gf_copy(a, L1);
 203     return gf_eq(L0, ONE);
 204 }