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
);