30 #include <botan/curve25519.h>
31 #include <botan/mul128.h>
32 #include <botan/internal/donna128.h>
33 #include <botan/internal/ct_utils.h>
34 #include <botan/loadstor.h>
52 const limb* q_minus_q_dash;
58 fmonty_pair_t q_plus_q_dash;
62 #if !defined(BOTAN_TARGET_HAS_NATIVE_UINT128)
68 fsum(limb *output,
const limb *in) {
83 fdifference_backwards(felem out,
const felem in) {
85 static const limb two54m152 = (
static_cast<limb
>(1) << 54) - 152;
86 static const limb two54m8 = (
static_cast<limb
>(1) << 54) - 8;
88 out[0] = in[0] + two54m152 - out[0];
89 out[1] = in[1] + two54m8 - out[1];
90 out[2] = in[2] + two54m8 - out[2];
91 out[3] = in[3] + two54m8 - out[3];
92 out[4] = in[4] + two54m8 - out[4];
97 fscalar_product(felem output,
const felem in,
const limb scalar) {
99 output[0] = a & 0x7ffffffffffff;
102 output[1] = a & 0x7ffffffffffff;
105 output[2] = a & 0x7ffffffffffff;
108 output[3] = a & 0x7ffffffffffff;
111 output[4] = a & 0x7ffffffffffff;
125 fmul(felem output,
const felem in2,
const felem in) {
127 limb r0,r1,r2,r3,r4,s0,s1,s2,s3,s4,c;
157 r0 = t[0] & 0x7ffffffffffff; c =
carry_shift(t[0], 51);
158 t[1] += c; r1 = t[1] & 0x7ffffffffffff; c =
carry_shift(t[1], 51);
159 t[2] += c; r2 = t[2] & 0x7ffffffffffff; c =
carry_shift(t[2], 51);
160 t[3] += c; r3 = t[3] & 0x7ffffffffffff; c =
carry_shift(t[3], 51);
161 t[4] += c; r4 = t[4] & 0x7ffffffffffff; c =
carry_shift(t[4], 51);
162 r0 += c * 19; c =
carry_shift(r0, 51); r0 = r0 & 0x7ffffffffffff;
163 r1 += c; c =
carry_shift(r1, 51); r1 = r1 & 0x7ffffffffffff;
173 static inline void fsquare_times(felem output,
const felem in, limb count) {
175 limb r0,r1,r2,r3,r4,c;
176 limb d0,d1,d2,d4,d419;
197 r0 = t[0] & 0x7ffffffffffff; c =
carry_shift(t[0], 51);
198 t[1] += c; r1 = t[1] & 0x7ffffffffffff; c =
carry_shift(t[1], 51);
199 t[2] += c; r2 = t[2] & 0x7ffffffffffff; c =
carry_shift(t[2], 51);
200 t[3] += c; r3 = t[3] & 0x7ffffffffffff; c =
carry_shift(t[3], 51);
201 t[4] += c; r4 = t[4] & 0x7ffffffffffff; c =
carry_shift(t[4], 51);
202 r0 += c * 19; c = r0 >> 51; r0 = r0 & 0x7ffffffffffff;
203 r1 += c; c = r1 >> 51; r1 = r1 & 0x7ffffffffffff;
216 load_limb(
const u8 *in) {
221 store_limb(u8 *out, limb in) {
227 fexpand(limb *output,
const u8 *in) {
228 output[0] = load_limb(in) & 0x7ffffffffffff;
229 output[1] = (load_limb(in+6) >> 3) & 0x7ffffffffffff;
230 output[2] = (load_limb(in+12) >> 6) & 0x7ffffffffffff;
231 output[3] = (load_limb(in+19) >> 1) & 0x7ffffffffffff;
232 output[4] = (load_limb(in+24) >> 12) & 0x7ffffffffffff;
239 fcontract(u8 *output,
const felem input) {
248 t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff;
249 t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff;
250 t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff;
251 t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff;
252 t[0] += (t[4] >> 51) * 19; t[4] &= 0x7ffffffffffff;
254 t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff;
255 t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff;
256 t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff;
257 t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff;
258 t[0] += (t[4] >> 51) * 19; t[4] &= 0x7ffffffffffff;
265 t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff;
266 t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff;
267 t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff;
268 t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff;
269 t[0] += (t[4] >> 51) * 19; t[4] &= 0x7ffffffffffff;
273 t[0] += 0x8000000000000 - 19;
274 t[1] += 0x8000000000000 - 1;
275 t[2] += 0x8000000000000 - 1;
276 t[3] += 0x8000000000000 - 1;
277 t[4] += 0x8000000000000 - 1;
281 t[1] += t[0] >> 51; t[0] &= 0x7ffffffffffff;
282 t[2] += t[1] >> 51; t[1] &= 0x7ffffffffffff;
283 t[3] += t[2] >> 51; t[2] &= 0x7ffffffffffff;
284 t[4] += t[3] >> 51; t[3] &= 0x7ffffffffffff;
285 t[4] &= 0x7ffffffffffff;
303 fmonty(fmonty_out_t& result, fmonty_in_t& in)
305 limb origx[5], origxprime[5], zzz[5], xx[5], zz[5], xxprime[5],
306 zzprime[5], zzzprime[5];
309 fsum(in.q.x, in.q.z);
310 fdifference_backwards(in.q.z, origx);
312 copy_mem(origxprime, in.q_dash.x, 5);
313 fsum(in.q_dash.x, in.q_dash.z);
314 fdifference_backwards(in.q_dash.z, origxprime);
315 fmul(xxprime, in.q_dash.x, in.q.z);
316 fmul(zzprime, in.q.x, in.q_dash.z);
318 fsum(xxprime, zzprime);
319 fdifference_backwards(zzprime, origxprime);
320 fsquare_times(result.q_plus_q_dash.x, xxprime, 1);
321 fsquare_times(zzzprime, zzprime, 1);
322 fmul(result.q_plus_q_dash.z, zzzprime, in.q_minus_q_dash);
324 fsquare_times(xx, in.q.x, 1);
325 fsquare_times(zz, in.q.z, 1);
326 fmul(result.two_q.x, xx, zz);
327 fdifference_backwards(zz, xx);
328 fscalar_product(zzz, zz, 121665);
330 fmul(result.two_q.z, zz, zzz);
341 swap_conditional(limb a[5], limb b[5], limb iswap) {
343 const limb swap =
static_cast<limb
>(-iswap);
345 for (i = 0; i < 5; ++i) {
346 const limb x = swap & (a[i] ^ b[i]);
359 cmult(limb *resultx, limb *resultz,
const u8 *n,
const limb *q) {
360 limb a[5] = {0}, b[5] = {1}, c[5] = {1}, d[5] = {0};
361 limb *nqpqx = a, *nqpqz = b, *nqx = c, *nqz = d, *t;
362 limb e[5] = {0}, f[5] = {1}, g[5] = {0}, h[5] = {1};
363 limb *nqpqx2 = e, *nqpqz2 = f, *nqx2 = g, *nqz2 = h;
369 for (i = 0; i < 32; ++i) {
370 u8 byteval = n[31 - i];
371 for (j = 0; j < 8; ++j) {
372 const limb bit = byteval >> 7;
374 swap_conditional(nqx, nqpqx, bit);
375 swap_conditional(nqz, nqpqz, bit);
377 fmonty_out_t result { {nqx2, nqz2}, {nqpqx2, nqpqz2} };
378 fmonty_in_t in { { nqx, nqz }, { nqpqx, nqpqz }, q };
380 swap_conditional(nqx2, nqpqx2, bit);
381 swap_conditional(nqz2, nqpqz2, bit);
409 crecip(felem out,
const felem z) {
412 fsquare_times(a, z, 1);
413 fsquare_times(t0, a, 2);
416 fsquare_times(t0, a, 1);
418 fsquare_times(t0, b, 5);
420 fsquare_times(t0, b, 10);
422 fsquare_times(t0, c, 20);
424 fsquare_times(t0, t0, 10);
426 fsquare_times(t0, b, 50);
428 fsquare_times(t0, c, 100);
430 fsquare_times(t0, t0, 50);
432 fsquare_times(t0, t0, 5);
442 limb bp[5], x[5], z[5], zmone[5];
446 for (i = 0;i < 32;++i) e[i] = secret[i];
451 fexpand(bp, basepoint);
455 fcontract(mypublic, z);
void poison(const T *p, size_t n)
uint64_t carry_shift(const donna128 &a, size_t shift)
uint64_t combine_lower(const donna128 &a, size_t s1, const donna128 &b, size_t s2)
uint64_t load_le< uint64_t >(const uint8_t in[], size_t off)
void copy_mem(T *out, const T *in, size_t n)
void unpoison(const T *p, size_t n)
void BOTAN_DLL curve25519_donna(uint8_t mypublic[32], const uint8_t secret[32], const uint8_t basepoint[32])
void store_le(uint16_t in, uint8_t out[2])