1 /* Arithmetic mod p = 2^255-19
2 * Daniel Beer <dlbeer@gmail.com>, 5 Jan 2014
4 * This file is in the public domain.
9 const uint8_t f25519_one[F25519_SIZE] = {1};
11 void f25519_load(uint8_t *x, uint32_t c)
15 for (i = 0; i < sizeof(c); i++) {
20 for (; i < F25519_SIZE; i++)
24 void f25519_normalize(uint8_t *x)
26 uint8_t minusp[F25519_SIZE];
30 /* Reduce using 2^255 = 19 mod p */
31 c = (x[31] >> 7) * 19;
34 for (i = 0; i < F25519_SIZE; i++) {
40 /* The number is now less than 2^255 + 18, and therefore less than
41 * 2p. Try subtracting p, and conditionally load the subtracted
42 * value if underflow did not occur.
46 for (i = 0; i + 1 < F25519_SIZE; i++) {
52 c += ((uint16_t)x[i]) - 128;
55 /* Load x-p if no underflow */
56 f25519_select(x, minusp, x, (c >> 15) & 1);
59 uint8_t f25519_eq(const uint8_t *x, const uint8_t *y)
64 for (i = 0; i < F25519_SIZE; i++)
74 void f25519_select(uint8_t *dst,
75 const uint8_t *zero, const uint8_t *one,
78 const uint8_t mask = -condition;
81 for (i = 0; i < F25519_SIZE; i++)
82 dst[i] = zero[i] ^ (mask & (one[i] ^ zero[i]));
85 void f25519_add(uint8_t *r, const uint8_t *a, const uint8_t *b)
91 for (i = 0; i < F25519_SIZE; i++) {
93 c += ((uint16_t)a[i]) + ((uint16_t)b[i]);
97 /* Reduce with 2^255 = 19 mod p */
101 for (i = 0; i < F25519_SIZE; i++) {
108 void f25519_sub(uint8_t *r, const uint8_t *a, const uint8_t *b)
113 /* Calculate a + 2p - b, to avoid underflow */
115 for (i = 0; i + 1 < F25519_SIZE; i++) {
116 c += 65280 + ((uint32_t)a[i]) - ((uint32_t)b[i]);
121 c += ((uint32_t)a[31]) - ((uint32_t)b[31]);
125 for (i = 0; i < F25519_SIZE; i++) {
132 void f25519_neg(uint8_t *r, const uint8_t *a)
137 /* Calculate 2p - a, to avoid underflow */
139 for (i = 0; i + 1 < F25519_SIZE; i++) {
140 c += 65280 - ((uint32_t)a[i]);
145 c -= ((uint32_t)a[31]);
149 for (i = 0; i < F25519_SIZE; i++) {
156 void f25519_mul__distinct(uint8_t *r, const uint8_t *a, const uint8_t *b)
161 for (i = 0; i < F25519_SIZE; i++) {
165 for (j = 0; j <= i; j++)
166 c += ((uint32_t)a[j]) * ((uint32_t)b[i - j]);
168 for (; j < F25519_SIZE; j++)
169 c += ((uint32_t)a[j]) *
170 ((uint32_t)b[i + F25519_SIZE - j]) * 38;
178 for (i = 0; i < F25519_SIZE; i++) {
185 static void f25519_mul_c(uint8_t *r, const uint8_t *a, uint32_t b)
190 for (i = 0; i < F25519_SIZE; i++) {
192 c += b * ((uint32_t)a[i]);
200 for (i = 0; i < F25519_SIZE; i++) {
207 void f25519_inv__distinct(uint8_t *r, const uint8_t *x)
209 uint8_t s[F25519_SIZE];
212 /* This is a prime field, so by Fermat's little theorem:
216 * Therefore, raise to (p-2) = 2^255-21 to get a multiplicative
219 * This is a 255-bit binary number with the digits:
223 * We compute the result by the usual binary chain, but
224 * alternate between keeping the accumulator in r and s, so as
225 * to avoid copying temporaries.
229 f25519_mul__distinct(s, x, x);
230 f25519_mul__distinct(r, s, x);
233 for (i = 0; i < 248; i++) {
234 f25519_mul__distinct(s, r, r);
235 f25519_mul__distinct(r, s, x);
239 f25519_mul__distinct(s, r, r);
242 f25519_mul__distinct(r, s, s);
243 f25519_mul__distinct(s, r, x);
246 f25519_mul__distinct(r, s, s);
249 f25519_mul__distinct(s, r, r);
250 f25519_mul__distinct(r, s, x);
253 f25519_mul__distinct(s, r, r);
254 f25519_mul__distinct(r, s, x);
257 /* Raise x to the power of (p-5)/8 = 2^252-3, using s for temporary
260 static void exp2523(uint8_t *r, const uint8_t *x, uint8_t *s)
264 /* This number is a 252-bit number with the binary expansion:
270 f25519_mul__distinct(r, x, x);
271 f25519_mul__distinct(s, r, x);
274 for (i = 0; i < 248; i++) {
275 f25519_mul__distinct(r, s, s);
276 f25519_mul__distinct(s, r, x);
280 f25519_mul__distinct(r, s, s);
283 f25519_mul__distinct(s, r, r);
284 f25519_mul__distinct(r, s, x);
287 void f25519_sqrt(uint8_t *r, const uint8_t *a)
289 uint8_t v[F25519_SIZE];
290 uint8_t i[F25519_SIZE];
291 uint8_t x[F25519_SIZE];
292 uint8_t y[F25519_SIZE];
294 /* v = (2a)^((p-5)/8) [x = 2a] */
295 f25519_mul_c(x, a, 2);
299 f25519_mul__distinct(y, v, v);
300 f25519_mul__distinct(i, x, y);
305 f25519_mul__distinct(x, v, a);
306 f25519_mul__distinct(r, x, i);