1 /*
2 * Copyright 2017-2023 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(0xffffffffffffffULL, 0xffffffffffffffULL, 0xffffffffffffffULL,
16 0xffffffffffffffULL, 0xfffffffffffffeULL, 0xffffffffffffffULL,
17 0xffffffffffffffULL, 0xffffffffffffffULL)
18 };
19
20 /* Serialize to wire format. */
gf_serialize(uint8_t serial[SER_BYTES],const gf x,int with_hibit)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 */
gf_hibit(const gf x)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 */
gf_lobit(const gf x)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. */
gf_deserialize(gf x,const uint8_t serial[SER_BYTES],int with_hibit,uint8_t hi_nmask)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)((i < NLIMBS - 1) ? buffer & LIMB_MASK(LIMBPERM(i)) : buffer);
88 fill -= LIMB_PLACE_VALUE(LIMBPERM(i));
89 buffer >>= LIMB_PLACE_VALUE(LIMBPERM(i));
90 scarry = (scarry + x->limb[LIMBPERM(i)] - MODULUS->limb[LIMBPERM(i)]) >> (8 * sizeof(word_t));
91 }
92 succ = with_hibit ? 0 - (mask_t)1 : ~gf_hibit(x);
93 return succ & word_is_zero((word_t)buffer) & ~word_is_zero((word_t)scarry);
94 }
95
96 /* Reduce to canonical form. */
gf_strong_reduce(gf a)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(scarry == 0 || scarry == -1);
123
124 scarry_0 = (word_t)scarry;
125
126 /* add it back */
127 for (i = 0; i < NLIMBS; i++) {
128 carry = carry + a->limb[LIMBPERM(i)] + (scarry_0 & MODULUS->limb[LIMBPERM(i)]);
129 a->limb[LIMBPERM(i)] = carry & LIMB_MASK(LIMBPERM(i));
130 carry >>= LIMB_PLACE_VALUE(LIMBPERM(i));
131 }
132
133 assert(carry < 2 && ((word_t)carry + scarry_0) == 0);
134 }
135
136 /* Subtract two gf elements d=a-b */
gf_sub(gf d,const gf a,const gf b)137 void gf_sub(gf d, const gf a, const gf b)
138 {
139 gf_sub_RAW(d, a, b);
140 gf_bias(d, 2);
141 gf_weak_reduce(d);
142 }
143
144 /* Add two field elements d = a+b */
gf_add(gf d,const gf a,const gf b)145 void gf_add(gf d, const gf a, const gf b)
146 {
147 gf_add_RAW(d, a, b);
148 gf_weak_reduce(d);
149 }
150
151 /* Compare a==b */
gf_eq(const gf a,const gf b)152 mask_t gf_eq(const gf a, const gf b)
153 {
154 gf c;
155 mask_t ret = 0;
156 unsigned int i;
157
158 gf_sub(c, a, b);
159 gf_strong_reduce(c);
160
161 for (i = 0; i < NLIMBS; i++)
162 ret |= c->limb[LIMBPERM(i)];
163
164 return word_is_zero(ret);
165 }
166
gf_isr(gf a,const gf x)167 mask_t gf_isr(gf a, const gf x)
168 {
169 gf L0, L1, L2;
170
171 ossl_gf_sqr(L1, x);
172 ossl_gf_mul(L2, x, L1);
173 ossl_gf_sqr(L1, L2);
174 ossl_gf_mul(L2, x, L1);
175 gf_sqrn(L1, L2, 3);
176 ossl_gf_mul(L0, L2, L1);
177 gf_sqrn(L1, L0, 3);
178 ossl_gf_mul(L0, L2, L1);
179 gf_sqrn(L2, L0, 9);
180 ossl_gf_mul(L1, L0, L2);
181 ossl_gf_sqr(L0, L1);
182 ossl_gf_mul(L2, x, L0);
183 gf_sqrn(L0, L2, 18);
184 ossl_gf_mul(L2, L1, L0);
185 gf_sqrn(L0, L2, 37);
186 ossl_gf_mul(L1, L2, L0);
187 gf_sqrn(L0, L1, 37);
188 ossl_gf_mul(L1, L2, L0);
189 gf_sqrn(L0, L1, 111);
190 ossl_gf_mul(L2, L1, L0);
191 ossl_gf_sqr(L0, L2);
192 ossl_gf_mul(L1, x, L0);
193 gf_sqrn(L0, L1, 223);
194 ossl_gf_mul(L1, L2, L0);
195 ossl_gf_sqr(L2, L1);
196 ossl_gf_mul(L0, L2, x);
197 gf_copy(a, L1);
198 return gf_eq(L0, ONE);
199 }
200