Branch data Line data Source code
1 : : /* Arithmetic mod p = 2^255-19
2 : : * Daniel Beer <dlbeer@gmail.com>, 5 Jan 2014
3 : : *
4 : : * This file is in the public domain.
5 : : */
6 : :
7 : : #include "f25519.h"
8 : :
9 : : #ifdef FULL_C25519_CODE
10 : : const uint8_t f25519_zero[F25519_SIZE] = {0};
11 : : #endif
12 : : const uint8_t f25519_one[F25519_SIZE] = {1};
13 : :
14 : 8 : void f25519_load(uint8_t *x, uint32_t c)
15 : : {
16 : 8 : unsigned int i;
17 : :
18 [ + + ]: 40 : for (i = 0; i < sizeof(c); i++) {
19 : 32 : x[i] = c;
20 : 32 : c >>= 8;
21 : : }
22 : :
23 [ + + ]: 232 : for (; i < F25519_SIZE; i++)
24 : 224 : x[i] = 0;
25 : 8 : }
26 : :
27 : 34 : void f25519_normalize(uint8_t *x)
28 : : {
29 : 34 : uint8_t minusp[F25519_SIZE];
30 : 34 : uint16_t c;
31 : 34 : int i;
32 : :
33 : : /* Reduce using 2^255 = 19 mod p */
34 : 34 : c = (x[31] >> 7) * 19;
35 : 34 : x[31] &= 127;
36 : :
37 [ + + ]: 1122 : for (i = 0; i < F25519_SIZE; i++) {
38 : 1088 : c += x[i];
39 : 1088 : x[i] = c;
40 : 1088 : c >>= 8;
41 : : }
42 : :
43 : : /* The number is now less than 2^255 + 18, and therefore less than
44 : : * 2p. Try subtracting p, and conditionally load the subtracted
45 : : * value if underflow did not occur.
46 : : */
47 : : c = 19;
48 : :
49 [ + + ]: 1088 : for (i = 0; i + 1 < F25519_SIZE; i++) {
50 : 1054 : c += x[i];
51 : 1054 : minusp[i] = c;
52 : 1054 : c >>= 8;
53 : : }
54 : :
55 : 34 : c += ((uint16_t)x[i]) - 128;
56 : 34 : minusp[31] = c;
57 : :
58 : : /* Load x-p if no underflow */
59 : 34 : f25519_select(x, minusp, x, (c >> 15) & 1);
60 : 34 : }
61 : :
62 : 6 : uint8_t f25519_eq(const uint8_t *x, const uint8_t *y)
63 : : {
64 : 6 : uint8_t sum = 0;
65 : 6 : int i;
66 : :
67 [ + + ]: 198 : for (i = 0; i < F25519_SIZE; i++)
68 : 192 : sum |= x[i] ^ y[i];
69 : :
70 : 6 : sum |= (sum >> 4);
71 : 6 : sum |= (sum >> 2);
72 : 6 : sum |= (sum >> 1);
73 : :
74 : 6 : return (sum ^ 1) & 1;
75 : : }
76 : :
77 : 8214 : void f25519_select(uint8_t *dst,
78 : : const uint8_t *zero, const uint8_t *one,
79 : : uint8_t condition)
80 : : {
81 : 8214 : const uint8_t mask = -condition;
82 : 8214 : int i;
83 : :
84 [ + + ]: 271062 : for (i = 0; i < F25519_SIZE; i++)
85 : 262848 : dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
86 : 8214 : }
87 : :
88 : 14830 : void f25519_add(uint8_t *r, const uint8_t *a, const uint8_t *b)
89 : : {
90 : 14830 : uint16_t c = 0;
91 : 14830 : int i;
92 : :
93 : : /* Add */
94 [ + + ]: 489390 : for (i = 0; i < F25519_SIZE; i++) {
95 : 474560 : c >>= 8;
96 : 474560 : c += ((uint16_t)a[i]) + ((uint16_t)b[i]);
97 : 474560 : r[i] = c;
98 : : }
99 : :
100 : : /* Reduce with 2^255 = 19 mod p */
101 : 14830 : r[31] &= 127;
102 : 14830 : c = (c >> 7) * 19;
103 : :
104 [ + + ]: 489390 : for (i = 0; i < F25519_SIZE; i++) {
105 : 474560 : c += r[i];
106 : 474560 : r[i] = c;
107 : 474560 : c >>= 8;
108 : : }
109 : 14830 : }
110 : :
111 : 17396 : void f25519_sub(uint8_t *r, const uint8_t *a, const uint8_t *b)
112 : : {
113 : 17396 : uint32_t c = 0;
114 : 17396 : int i;
115 : :
116 : : /* Calculate a + 2p - b, to avoid underflow */
117 : 17396 : c = 218;
118 [ + + ]: 556672 : for (i = 0; i + 1 < F25519_SIZE; i++) {
119 : 539276 : c += 65280 + ((uint32_t)a[i]) - ((uint32_t)b[i]);
120 : 539276 : r[i] = c;
121 : 539276 : c >>= 8;
122 : : }
123 : :
124 : 17396 : c += ((uint32_t)a[31]) - ((uint32_t)b[31]);
125 : 17396 : r[31] = c & 127;
126 : 17396 : c = (c >> 7) * 19;
127 : :
128 [ + + ]: 574068 : for (i = 0; i < F25519_SIZE; i++) {
129 : 556672 : c += r[i];
130 : 556672 : r[i] = c;
131 : 556672 : c >>= 8;
132 : : }
133 : 17396 : }
134 : :
135 : 1540 : void f25519_neg(uint8_t *r, const uint8_t *a)
136 : : {
137 : 1540 : uint32_t c = 0;
138 : 1540 : int i;
139 : :
140 : : /* Calculate 2p - a, to avoid underflow */
141 : 1540 : c = 218;
142 [ + + ]: 49280 : for (i = 0; i + 1 < F25519_SIZE; i++) {
143 : 47740 : c += 65280 - ((uint32_t)a[i]);
144 : 47740 : r[i] = c;
145 : 47740 : c >>= 8;
146 : : }
147 : :
148 : 1540 : c -= ((uint32_t)a[31]);
149 : 1540 : r[31] = c & 127;
150 : 1540 : c = (c >> 7) * 19;
151 : :
152 [ + + ]: 50820 : for (i = 0; i < F25519_SIZE; i++) {
153 : 49280 : c += r[i];
154 : 49280 : r[i] = c;
155 : 49280 : c >>= 8;
156 : : }
157 : 1540 : }
158 : :
159 : 42892 : void f25519_mul__distinct(uint8_t *r, const uint8_t *a, const uint8_t *b)
160 : : {
161 : 42892 : uint32_t c = 0;
162 : 42892 : int i;
163 : :
164 [ + + ]: 1415436 : for (i = 0; i < F25519_SIZE; i++) {
165 : 1372544 : int j;
166 : :
167 : 1372544 : c >>= 8;
168 [ + + ]: 24019520 : for (j = 0; j <= i; j++)
169 : 22646976 : c += ((uint32_t)a[j]) * ((uint32_t)b[i - j]);
170 : :
171 [ + + ]: 22646976 : for (; j < F25519_SIZE; j++)
172 : 21274432 : c += ((uint32_t)a[j]) *
173 : 21274432 : ((uint32_t)b[i + F25519_SIZE - j]) * 38;
174 : :
175 : 1372544 : r[i] = c;
176 : : }
177 : :
178 : 42892 : r[31] &= 127;
179 : 42892 : c = (c >> 7) * 19;
180 : :
181 [ + + ]: 1415436 : for (i = 0; i < F25519_SIZE; i++) {
182 : 1372544 : c += r[i];
183 : 1372544 : r[i] = c;
184 : 1372544 : c >>= 8;
185 : : }
186 : 42892 : }
187 : :
188 : : #ifdef FULL_C25519_CODE
189 : : void f25519_mul(uint8_t *r, const uint8_t *a, const uint8_t *b)
190 : : {
191 : : uint8_t tmp[F25519_SIZE];
192 : :
193 : : f25519_mul__distinct(tmp, a, b);
194 : : f25519_copy(r, tmp);
195 : : }
196 : : #endif
197 : :
198 : 1020 : void f25519_mul_c(uint8_t *r, const uint8_t *a, uint32_t b)
199 : : {
200 : 1020 : uint32_t c = 0;
201 : 1020 : int i;
202 : :
203 [ + + ]: 33660 : for (i = 0; i < F25519_SIZE; i++) {
204 : 32640 : c >>= 8;
205 : 32640 : c += b * ((uint32_t)a[i]);
206 : 32640 : r[i] = c;
207 : : }
208 : :
209 : 1020 : r[31] &= 127;
210 : 1020 : c >>= 7;
211 : 1020 : c *= 19;
212 : :
213 [ + + ]: 33660 : for (i = 0; i < F25519_SIZE; i++) {
214 : 32640 : c += r[i];
215 : 32640 : r[i] = c;
216 : 32640 : c >>= 8;
217 : : }
218 : 1020 : }
219 : :
220 : 12 : void f25519_inv__distinct(uint8_t *r, const uint8_t *x)
221 : : {
222 : 12 : uint8_t s[F25519_SIZE];
223 : 12 : int i;
224 : :
225 : : /* This is a prime field, so by Fermat's little theorem:
226 : : *
227 : : * x^(p-1) = 1 mod p
228 : : *
229 : : * Therefore, raise to (p-2) = 2^255-21 to get a multiplicative
230 : : * inverse.
231 : : *
232 : : * This is a 255-bit binary number with the digits:
233 : : *
234 : : * 11111111... 01011
235 : : *
236 : : * We compute the result by the usual binary chain, but
237 : : * alternate between keeping the accumulator in r and s, so as
238 : : * to avoid copying temporaries.
239 : : */
240 : :
241 : : /* 1 1 */
242 : 12 : f25519_mul__distinct(s, x, x);
243 : 12 : f25519_mul__distinct(r, s, x);
244 : :
245 : : /* 1 x 248 */
246 [ + + ]: 3000 : for (i = 0; i < 248; i++) {
247 : 2976 : f25519_mul__distinct(s, r, r);
248 : 2976 : f25519_mul__distinct(r, s, x);
249 : : }
250 : :
251 : : /* 0 */
252 : 12 : f25519_mul__distinct(s, r, r);
253 : :
254 : : /* 1 */
255 : 12 : f25519_mul__distinct(r, s, s);
256 : 12 : f25519_mul__distinct(s, r, x);
257 : :
258 : : /* 0 */
259 : 12 : f25519_mul__distinct(r, s, s);
260 : :
261 : : /* 1 */
262 : 12 : f25519_mul__distinct(s, r, r);
263 : 12 : f25519_mul__distinct(r, s, x);
264 : :
265 : : /* 1 */
266 : 12 : f25519_mul__distinct(s, r, r);
267 : 12 : f25519_mul__distinct(r, s, x);
268 : 12 : }
269 : :
270 : : #ifdef FULL_C25519_CODE
271 : : void f25519_inv(uint8_t *r, const uint8_t *x)
272 : : {
273 : : uint8_t tmp[F25519_SIZE];
274 : :
275 : : f25519_inv__distinct(tmp, x);
276 : : f25519_copy(r, tmp);
277 : : }
278 : : #endif
279 : :
280 : : /* Raise x to the power of (p-5)/8 = 2^252-3, using s for temporary
281 : : * storage.
282 : : */
283 : 4 : static void exp2523(uint8_t *r, const uint8_t *x, uint8_t *s)
284 : : {
285 : 4 : int i;
286 : :
287 : : /* This number is a 252-bit number with the binary expansion:
288 : : *
289 : : * 111111... 01
290 : : */
291 : :
292 : : /* 1 1 */
293 : 4 : f25519_mul__distinct(r, x, x);
294 : 4 : f25519_mul__distinct(s, r, x);
295 : :
296 : : /* 1 x 248 */
297 [ + + ]: 1000 : for (i = 0; i < 248; i++) {
298 : 992 : f25519_mul__distinct(r, s, s);
299 : 992 : f25519_mul__distinct(s, r, x);
300 : : }
301 : :
302 : : /* 0 */
303 : 4 : f25519_mul__distinct(r, s, s);
304 : :
305 : : /* 1 */
306 : 4 : f25519_mul__distinct(s, r, r);
307 : 4 : f25519_mul__distinct(r, s, x);
308 : 4 : }
309 : :
310 : 4 : void f25519_sqrt(uint8_t *r, const uint8_t *a)
311 : : {
312 : 4 : uint8_t v[F25519_SIZE];
313 : 4 : uint8_t i[F25519_SIZE];
314 : 4 : uint8_t x[F25519_SIZE];
315 : 4 : uint8_t y[F25519_SIZE];
316 : :
317 : : /* v = (2a)^((p-5)/8) [x = 2a] */
318 : 4 : f25519_mul_c(x, a, 2);
319 : 4 : exp2523(v, x, y);
320 : :
321 : : /* i = 2av^2 - 1 */
322 : 4 : f25519_mul__distinct(y, v, v);
323 : 4 : f25519_mul__distinct(i, x, y);
324 : 4 : f25519_load(y, 1);
325 : 4 : f25519_sub(i, i, y);
326 : :
327 : : /* r = avi */
328 : 4 : f25519_mul__distinct(x, v, a);
329 : 4 : f25519_mul__distinct(r, x, i);
330 : 4 : }
|
