2 * Copyright 2017-2018 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright 2015-2016 Cryptography Research, Inc.
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
10 * Originally written by Mike Hamburg
14 static const gf MODULUS = {
15 FIELD_LITERAL(0xffffffffffffff, 0xffffffffffffff, 0xffffffffffffff,
16 0xffffffffffffff, 0xfffffffffffffe, 0xffffffffffffff,
17 0xffffffffffffff, 0xffffffffffffff)
20 /* Serialize to wire format. */
21 void gf_serialize(uint8_t serial[SER_BYTES], const gf x, int with_hibit)
23 unsigned int j = 0, fill = 0;
29 gf_strong_reduce(red);
31 assert(gf_hibit(red) == 0);
33 UNROLL 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));
39 serial[i] = (uint8_t)buffer;
45 /* Return high bit of x = low bit of 2x mod p */
46 mask_t gf_hibit(const gf x)
51 return 0 - (y->limb[0] & 1);
54 /* Return high bit of x = low bit of 2x mod p */
55 mask_t gf_lobit(const gf x)
60 return 0 - (y->limb[0] & 1);
63 /* Deserialize from wire format; return -1 on success and 0 on failure. */
64 mask_t gf_deserialize(gf x, const uint8_t serial[SER_BYTES], int with_hibit,
67 unsigned int j = 0, fill = 0;
70 const unsigned nbytes = with_hibit ? X_SER_BYTES : SER_BYTES;
74 UNROLL for (i = 0; i < NLIMBS; i++) {
75 UNROLL while (fill < LIMB_PLACE_VALUE(LIMBPERM(i)) && j < nbytes) {
76 uint8_t sj = serial[j];
79 buffer |= ((dword_t) sj) << fill;
83 x->limb[LIMBPERM(i)] = (word_t)
84 ((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer);
85 fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
86 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
88 (scarry + x->limb[LIMBPERM(i)] -
89 MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t));
91 succ = with_hibit ? 0 - (mask_t) 1 : ~gf_hibit(x);
92 return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry);
95 /* Reduce to canonical form. */
96 void gf_strong_reduce(gf a)
103 /* first, clear high */
104 gf_weak_reduce(a); /* Determined to have negligible perf impact. */
106 /* now the total is less than 2p */
108 /* compute total_value - p. No need to reduce mod p. */
110 for (i = 0; i < NLIMBS; i++) {
111 scarry = scarry + a->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)];
112 a->limb[LIMBPERM(i)] = scarry & LIMB_MASK(LIMBPERM(i));
113 scarry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
117 * uncommon case: it was >= p, so now scarry = 0 and this = x common case:
118 * it was < p, so now scarry = -1 and this = x - p + 2^255 so let's add
119 * back in p. will carry back off the top for 2^255.
121 assert(word_is_zero(scarry) | word_is_zero(scarry + 1));
123 scarry_0 = (word_t)scarry;
126 for (i = 0; i < NLIMBS; i++) {
128 carry + a->limb[LIMBPERM(i)] +
129 (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
130 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
131 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
134 assert(word_is_zero(carry + scarry_0));
137 /* Subtract two gf elements d=a-b */
138 void gf_sub(gf d, const gf a, const gf b)
145 /* Add two field elements d = a+b */
146 void gf_add(gf d, const gf a, const gf b)
153 mask_t gf_eq(const gf a, const gf b)
162 for (i = 0; i < NLIMBS; i++) {
163 ret |= c->limb[LIMBPERM(i)];
166 return word_is_zero(ret);
169 mask_t gf_isr(gf a, const gf x)
190 gf_sqrn(L0, L1, 111);
194 gf_sqrn(L0, L1, 223);
199 return gf_eq(L0, ONE);