Security Scol plugin
donna_64.cpp
1// donna_64.cpp - written and placed in public domain by Jeffrey Walton
2// Crypto++ specific implementation wrapped around Andrew
3// Moon's public domain curve25519-donna and ed25519-donna,
4// https://github.com/floodyberry/curve25519-donna and
5// https://github.com/floodyberry/ed25519-donna.
6
7// The curve25519 and ed25519 source files multiplex different repos and
8// architectures using namespaces. The repos are Andrew Moon's
9// curve25519-donna and ed25519-donna. The architectures are 32-bit, 64-bit
10// and SSE. For example, 32-bit x25519 uses symbols from Donna::X25519 and
11// Donna::Arch32.
12
13// A fair amount of duplication happens below, but we could not directly
14// use curve25519 for both x25519 and ed25519. A close examination reveals
15// slight differences in the implementation. For example, look at the
16// two curve25519_sub functions.
17
18// If needed, see Moon's commit "Go back to ignoring 256th bit [sic]",
19// https://github.com/floodyberry/curve25519-donna/commit/57a683d18721a658
20
21#include "pch.h"
22
23#include "config.h"
24#include "donna.h"
25#include "secblock.h"
26#include "sha.h"
27#include "misc.h"
28#include "cpu.h"
29
30#include <istream>
31#include <sstream>
32
33#if CRYPTOPP_GCC_DIAGNOSTIC_AVAILABLE
34# pragma GCC diagnostic ignored "-Wunused-function"
35#endif
36
37#if CRYPTOPP_MSC_VERSION
38# pragma warning(disable: 4244)
39#endif
40
41// Squash MS LNK4221 and libtool warnings
42extern const char DONNA64_FNAME[] = __FILE__;
43
44ANONYMOUS_NAMESPACE_BEGIN
45
46// Can't use GetAlignmentOf<word64>() because of C++11 and constexpr
47// Can use 'const unsigned int' because of MSVC 2013
48#if (CRYPTOPP_BOOL_X86 || CRYPTOPP_BOOL_X32 || CRYPTOPP_BOOL_X64)
49# define ALIGN_SPEC 16
50#else
51# define ALIGN_SPEC 8
52#endif
53
54ANONYMOUS_NAMESPACE_END
55
56#if defined(CRYPTOPP_CURVE25519_64BIT)
57
58#include "donna_64.h"
59
60ANONYMOUS_NAMESPACE_BEGIN
61
62using CryptoPP::byte;
63using CryptoPP::word64;
64using CryptoPP::GetWord;
65using CryptoPP::PutWord;
66using CryptoPP::LITTLE_ENDIAN_ORDER;
67
68inline word64 U8TO64_LE(const byte* p)
69{
70 return GetWord<word64>(false, LITTLE_ENDIAN_ORDER, p);
71}
72
73inline void U64TO8_LE(byte* p, word64 w)
74{
75 PutWord(false, LITTLE_ENDIAN_ORDER, p, w);
76}
77
78ANONYMOUS_NAMESPACE_END
79
80NAMESPACE_BEGIN(CryptoPP)
81NAMESPACE_BEGIN(Donna)
82NAMESPACE_BEGIN(X25519)
83ANONYMOUS_NAMESPACE_BEGIN
84
85using CryptoPP::byte;
86using CryptoPP::word32;
87using CryptoPP::sword32;
88using CryptoPP::word64;
89using CryptoPP::sword64;
90
91using CryptoPP::GetBlock;
92using CryptoPP::LittleEndian;
93
94// Bring in all the symbols from the 64-bit header
95using namespace CryptoPP::Donna::Arch64;
96
97/* out = in */
98inline void
99curve25519_copy(bignum25519 out, const bignum25519 in) {
100 out[0] = in[0]; out[1] = in[1];
101 out[2] = in[2]; out[3] = in[3];
102 out[4] = in[4];
103}
104
105/* out = a + b */
106inline void
107curve25519_add(bignum25519 out, const bignum25519 a, const bignum25519 b) {
108 out[0] = a[0] + b[0];
109 out[1] = a[1] + b[1];
110 out[2] = a[2] + b[2];
111 out[3] = a[3] + b[3];
112 out[4] = a[4] + b[4];
113}
114
115/* out = a - b */
116inline void
117curve25519_sub(bignum25519 out, const bignum25519 a, const bignum25519 b) {
118 out[0] = a[0] + two54m152 - b[0];
119 out[1] = a[1] + two54m8 - b[1];
120 out[2] = a[2] + two54m8 - b[2];
121 out[3] = a[3] + two54m8 - b[3];
122 out[4] = a[4] + two54m8 - b[4];
123}
124
125/* out = (in * scalar) */
126inline void
127curve25519_scalar_product(bignum25519 out, const bignum25519 in, const word64 scalar) {
128 word128 a;
129 word64 c;
130
131#if defined(CRYPTOPP_WORD128_AVAILABLE)
132 a = ((word128) in[0]) * scalar; out[0] = (word64)a & reduce_mask_51; c = (word64)(a >> 51);
133 a = ((word128) in[1]) * scalar + c; out[1] = (word64)a & reduce_mask_51; c = (word64)(a >> 51);
134 a = ((word128) in[2]) * scalar + c; out[2] = (word64)a & reduce_mask_51; c = (word64)(a >> 51);
135 a = ((word128) in[3]) * scalar + c; out[3] = (word64)a & reduce_mask_51; c = (word64)(a >> 51);
136 a = ((word128) in[4]) * scalar + c; out[4] = (word64)a & reduce_mask_51; c = (word64)(a >> 51);
137 out[0] += c * 19;
138#else
139 mul64x64_128(a, in[0], scalar) out[0] = lo128(a) & reduce_mask_51; shr128(c, a, 51);
140 mul64x64_128(a, in[1], scalar) add128_64(a, c) out[1] = lo128(a) & reduce_mask_51; shr128(c, a, 51);
141 mul64x64_128(a, in[2], scalar) add128_64(a, c) out[2] = lo128(a) & reduce_mask_51; shr128(c, a, 51);
142 mul64x64_128(a, in[3], scalar) add128_64(a, c) out[3] = lo128(a) & reduce_mask_51; shr128(c, a, 51);
143 mul64x64_128(a, in[4], scalar) add128_64(a, c) out[4] = lo128(a) & reduce_mask_51; shr128(c, a, 51);
144 out[0] += c * 19;
145#endif
146}
147
148/* out = a * b */
149inline void
150curve25519_mul(bignum25519 out, const bignum25519 a, const bignum25519 b) {
151#if !defined(CRYPTOPP_WORD128_AVAILABLE)
152 word128 mul;
153#endif
154 word128 t[5];
155 word64 r0,r1,r2,r3,r4,s0,s1,s2,s3,s4,c;
156
157 r0 = b[0]; r1 = b[1]; r2 = b[2]; r3 = b[3]; r4 = b[4];
158 s0 = a[0]; s1 = a[1]; s2 = a[2]; s3 = a[3]; s4 = a[4];
159
160#if defined(CRYPTOPP_WORD128_AVAILABLE)
161 t[0] = ((word128) r0) * s0;
162 t[1] = ((word128) r0) * s1 + ((word128) r1) * s0;
163 t[2] = ((word128) r0) * s2 + ((word128) r2) * s0 + ((word128) r1) * s1;
164 t[3] = ((word128) r0) * s3 + ((word128) r3) * s0 + ((word128) r1) * s2 + ((word128) r2) * s1;
165 t[4] = ((word128) r0) * s4 + ((word128) r4) * s0 + ((word128) r3) * s1 + ((word128) r1) * s3 + ((word128) r2) * s2;
166#else
167 mul64x64_128(t[0], r0, s0)
168 mul64x64_128(t[1], r0, s1) mul64x64_128(mul, r1, s0) add128(t[1], mul)
169 mul64x64_128(t[2], r0, s2) mul64x64_128(mul, r2, s0) add128(t[2], mul) mul64x64_128(mul, r1, s1) add128(t[2], mul)
170 mul64x64_128(t[3], r0, s3) mul64x64_128(mul, r3, s0) add128(t[3], mul) mul64x64_128(mul, r1, s2) add128(t[3], mul) mul64x64_128(mul, r2, s1) add128(t[3], mul)
171 mul64x64_128(t[4], r0, s4) mul64x64_128(mul, r4, s0) add128(t[4], mul) mul64x64_128(mul, r3, s1) add128(t[4], mul) mul64x64_128(mul, r1, s3) add128(t[4], mul) mul64x64_128(mul, r2, s2) add128(t[4], mul)
172#endif
173
174 r1 *= 19; r2 *= 19; r3 *= 19; r4 *= 19;
175
176#if defined(CRYPTOPP_WORD128_AVAILABLE)
177 t[0] += ((word128) r4) * s1 + ((word128) r1) * s4 + ((word128) r2) * s3 + ((word128) r3) * s2;
178 t[1] += ((word128) r4) * s2 + ((word128) r2) * s4 + ((word128) r3) * s3;
179 t[2] += ((word128) r4) * s3 + ((word128) r3) * s4;
180 t[3] += ((word128) r4) * s4;
181#else
182 mul64x64_128(mul, r4, s1) add128(t[0], mul) mul64x64_128(mul, r1, s4) add128(t[0], mul) mul64x64_128(mul, r2, s3) add128(t[0], mul) mul64x64_128(mul, r3, s2) add128(t[0], mul)
183 mul64x64_128(mul, r4, s2) add128(t[1], mul) mul64x64_128(mul, r2, s4) add128(t[1], mul) mul64x64_128(mul, r3, s3) add128(t[1], mul)
184 mul64x64_128(mul, r4, s3) add128(t[2], mul) mul64x64_128(mul, r3, s4) add128(t[2], mul)
185 mul64x64_128(mul, r4, s4) add128(t[3], mul)
186#endif
187
188 r0 = lo128(t[0]) & reduce_mask_51; shr128(c, t[0], 51);
189 add128_64(t[1], c) r1 = lo128(t[1]) & reduce_mask_51; shr128(c, t[1], 51);
190 add128_64(t[2], c) r2 = lo128(t[2]) & reduce_mask_51; shr128(c, t[2], 51);
191 add128_64(t[3], c) r3 = lo128(t[3]) & reduce_mask_51; shr128(c, t[3], 51);
192 add128_64(t[4], c) r4 = lo128(t[4]) & reduce_mask_51; shr128(c, t[4], 51);
193 r0 += c * 19; c = r0 >> 51; r0 = r0 & reduce_mask_51;
194 r1 += c;
195
196 out[0] = r0; out[1] = r1; out[2] = r2; out[3] = r3; out[4] = r4;
197}
198
199/* out = in^(2 * count) */
200inline void
201curve25519_square_times(bignum25519 out, const bignum25519 in, word64 count) {
202#if !defined(CRYPTOPP_WORD128_AVAILABLE)
203 word128 mul;
204#endif
205 word128 t[5];
206 word64 r0,r1,r2,r3,r4,c;
207 word64 d0,d1,d2,d4,d419;
208
209 r0 = in[0]; r1 = in[1]; r2 = in[2]; r3 = in[3]; r4 = in[4];
210
211 do {
212 d0 = r0 * 2; d1 = r1 * 2;
213 d2 = r2 * 2 * 19;
214 d419 = r4 * 19; d4 = d419 * 2;
215
216#if defined(CRYPTOPP_WORD128_AVAILABLE)
217 t[0] = ((word128) r0) * r0 + ((word128) d4) * r1 + (((word128) d2) * (r3 ));
218 t[1] = ((word128) d0) * r1 + ((word128) d4) * r2 + (((word128) r3) * (r3 * 19));
219 t[2] = ((word128) d0) * r2 + ((word128) r1) * r1 + (((word128) d4) * (r3 ));
220 t[3] = ((word128) d0) * r3 + ((word128) d1) * r2 + (((word128) r4) * (d419 ));
221 t[4] = ((word128) d0) * r4 + ((word128) d1) * r3 + (((word128) r2) * (r2 ));
222#else
223 mul64x64_128(t[0], r0, r0) mul64x64_128(mul, d4, r1) add128(t[0], mul) mul64x64_128(mul, d2, r3) add128(t[0], mul)
224 mul64x64_128(t[1], d0, r1) mul64x64_128(mul, d4, r2) add128(t[1], mul) mul64x64_128(mul, r3, r3 * 19) add128(t[1], mul)
225 mul64x64_128(t[2], d0, r2) mul64x64_128(mul, r1, r1) add128(t[2], mul) mul64x64_128(mul, d4, r3) add128(t[2], mul)
226 mul64x64_128(t[3], d0, r3) mul64x64_128(mul, d1, r2) add128(t[3], mul) mul64x64_128(mul, r4, d419) add128(t[3], mul)
227 mul64x64_128(t[4], d0, r4) mul64x64_128(mul, d1, r3) add128(t[4], mul) mul64x64_128(mul, r2, r2) add128(t[4], mul)
228#endif
229
230 r0 = lo128(t[0]) & reduce_mask_51; shr128(c, t[0], 51);
231 add128_64(t[1], c) r1 = lo128(t[1]) & reduce_mask_51; shr128(c, t[1], 51);
232 add128_64(t[2], c) r2 = lo128(t[2]) & reduce_mask_51; shr128(c, t[2], 51);
233 add128_64(t[3], c) r3 = lo128(t[3]) & reduce_mask_51; shr128(c, t[3], 51);
234 add128_64(t[4], c) r4 = lo128(t[4]) & reduce_mask_51; shr128(c, t[4], 51);
235 r0 += c * 19; c = r0 >> 51; r0 = r0 & reduce_mask_51;
236 r1 += c;
237 } while(--count);
238
239 out[0] = r0; out[1] = r1; out[2] = r2; out[3] = r3; out[4] = r4;
240}
241
242inline void
243curve25519_square(bignum25519 out, const bignum25519 in) {
244#if !defined(CRYPTOPP_WORD128_AVAILABLE)
245 word128 mul;
246#endif
247 word128 t[5];
248 word64 r0,r1,r2,r3,r4,c;
249 word64 d0,d1,d2,d4,d419;
250
251 r0 = in[0]; r1 = in[1]; r2 = in[2]; r3 = in[3]; r4 = in[4];
252
253 d0 = r0 * 2; d1 = r1 * 2;
254 d2 = r2 * 2 * 19;
255 d419 = r4 * 19; d4 = d419 * 2;
256
257#if defined(CRYPTOPP_WORD128_AVAILABLE)
258 t[0] = ((word128) r0) * r0 + ((word128) d4) * r1 + (((word128) d2) * (r3 ));
259 t[1] = ((word128) d0) * r1 + ((word128) d4) * r2 + (((word128) r3) * (r3 * 19));
260 t[2] = ((word128) d0) * r2 + ((word128) r1) * r1 + (((word128) d4) * (r3 ));
261 t[3] = ((word128) d0) * r3 + ((word128) d1) * r2 + (((word128) r4) * (d419 ));
262 t[4] = ((word128) d0) * r4 + ((word128) d1) * r3 + (((word128) r2) * (r2 ));
263#else
264 mul64x64_128(t[0], r0, r0) mul64x64_128(mul, d4, r1) add128(t[0], mul) mul64x64_128(mul, d2, r3) add128(t[0], mul)
265 mul64x64_128(t[1], d0, r1) mul64x64_128(mul, d4, r2) add128(t[1], mul) mul64x64_128(mul, r3, r3 * 19) add128(t[1], mul)
266 mul64x64_128(t[2], d0, r2) mul64x64_128(mul, r1, r1) add128(t[2], mul) mul64x64_128(mul, d4, r3) add128(t[2], mul)
267 mul64x64_128(t[3], d0, r3) mul64x64_128(mul, d1, r2) add128(t[3], mul) mul64x64_128(mul, r4, d419) add128(t[3], mul)
268 mul64x64_128(t[4], d0, r4) mul64x64_128(mul, d1, r3) add128(t[4], mul) mul64x64_128(mul, r2, r2) add128(t[4], mul)
269#endif
270
271 r0 = lo128(t[0]) & reduce_mask_51; shr128(c, t[0], 51);
272 add128_64(t[1], c) r1 = lo128(t[1]) & reduce_mask_51; shr128(c, t[1], 51);
273 add128_64(t[2], c) r2 = lo128(t[2]) & reduce_mask_51; shr128(c, t[2], 51);
274 add128_64(t[3], c) r3 = lo128(t[3]) & reduce_mask_51; shr128(c, t[3], 51);
275 add128_64(t[4], c) r4 = lo128(t[4]) & reduce_mask_51; shr128(c, t[4], 51);
276 r0 += c * 19; c = r0 >> 51; r0 = r0 & reduce_mask_51;
277 r1 += c;
278
279 out[0] = r0; out[1] = r1; out[2] = r2; out[3] = r3; out[4] = r4;
280}
281
282/* Take a little-endian, 32-byte number and expand it into polynomial form */
283inline void
284curve25519_expand(bignum25519 out, const byte *in) {
285 word64 x0,x1,x2,x3;
286 GetBlock<word64, LittleEndian> block(in);
287 block(x0)(x1)(x2)(x3);
288
289 out[0] = x0 & reduce_mask_51; x0 = (x0 >> 51) | (x1 << 13);
290 out[1] = x0 & reduce_mask_51; x1 = (x1 >> 38) | (x2 << 26);
291 out[2] = x1 & reduce_mask_51; x2 = (x2 >> 25) | (x3 << 39);
292 out[3] = x2 & reduce_mask_51; x3 = (x3 >> 12);
293 out[4] = x3 & reduce_mask_51; /* ignore the top bit */
294}
295
296/* Take a fully reduced polynomial form number and contract it into a
297 * little-endian, 32-byte array
298 */
299inline void
300curve25519_contract(byte *out, const bignum25519 input) {
301 word64 t[5];
302 word64 f, i;
303
304 t[0] = input[0];
305 t[1] = input[1];
306 t[2] = input[2];
307 t[3] = input[3];
308 t[4] = input[4];
309
310 #define curve25519_contract_carry() \
311 t[1] += t[0] >> 51; t[0] &= reduce_mask_51; \
312 t[2] += t[1] >> 51; t[1] &= reduce_mask_51; \
313 t[3] += t[2] >> 51; t[2] &= reduce_mask_51; \
314 t[4] += t[3] >> 51; t[3] &= reduce_mask_51;
315
316 #define curve25519_contract_carry_full() curve25519_contract_carry() \
317 t[0] += 19 * (t[4] >> 51); t[4] &= reduce_mask_51;
318
319 #define curve25519_contract_carry_final() curve25519_contract_carry() \
320 t[4] &= reduce_mask_51;
321
322 curve25519_contract_carry_full()
323 curve25519_contract_carry_full()
324
325 /* now t is between 0 and 2^255-1, properly carried. */
326 /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */
327 t[0] += 19;
328 curve25519_contract_carry_full()
329
330 /* now between 19 and 2^255-1 in both cases, and offset by 19. */
331 t[0] += 0x8000000000000 - 19;
332 t[1] += 0x8000000000000 - 1;
333 t[2] += 0x8000000000000 - 1;
334 t[3] += 0x8000000000000 - 1;
335 t[4] += 0x8000000000000 - 1;
336
337 /* now between 2^255 and 2^256-20, and offset by 2^255. */
338 curve25519_contract_carry_final()
339
340 #define write51full(n,shift) \
341 f = ((t[n] >> shift) | (t[n+1] << (51 - shift))); \
342 for (i = 0; i < 8; i++, f >>= 8) *out++ = (byte)f;
343 #define write51(n) write51full(n,13*n)
344
345 write51(0)
346 write51(1)
347 write51(2)
348 write51(3)
349
350 #undef curve25519_contract_carry
351 #undef curve25519_contract_carry_full
352 #undef curve25519_contract_carry_final
353 #undef write51full
354 #undef write51
355}
356
357/*
358 * Swap the contents of [qx] and [qpx] iff @swap is non-zero
359 */
360inline void
361curve25519_swap_conditional(bignum25519 x, bignum25519 qpx, word64 iswap) {
362 const word64 swap = (word64)(-(sword64)iswap);
363 word64 x0,x1,x2,x3,x4;
364
365 x0 = swap & (x[0] ^ qpx[0]); x[0] ^= x0; qpx[0] ^= x0;
366 x1 = swap & (x[1] ^ qpx[1]); x[1] ^= x1; qpx[1] ^= x1;
367 x2 = swap & (x[2] ^ qpx[2]); x[2] ^= x2; qpx[2] ^= x2;
368 x3 = swap & (x[3] ^ qpx[3]); x[3] ^= x3; qpx[3] ^= x3;
369 x4 = swap & (x[4] ^ qpx[4]); x[4] ^= x4; qpx[4] ^= x4;
370}
371
372/*
373 * In: b = 2^5 - 2^0
374 * Out: b = 2^250 - 2^0
375 */
376void
377curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b) {
378 ALIGN(ALIGN_SPEC) bignum25519 t0,c;
379
380 /* 2^5 - 2^0 */ /* b */
381 /* 2^10 - 2^5 */ curve25519_square_times(t0, b, 5);
382 /* 2^10 - 2^0 */ curve25519_mul(b, t0, b);
383 /* 2^20 - 2^10 */ curve25519_square_times(t0, b, 10);
384 /* 2^20 - 2^0 */ curve25519_mul(c, t0, b);
385 /* 2^40 - 2^20 */ curve25519_square_times(t0, c, 20);
386 /* 2^40 - 2^0 */ curve25519_mul(t0, t0, c);
387 /* 2^50 - 2^10 */ curve25519_square_times(t0, t0, 10);
388 /* 2^50 - 2^0 */ curve25519_mul(b, t0, b);
389 /* 2^100 - 2^50 */ curve25519_square_times(t0, b, 50);
390 /* 2^100 - 2^0 */ curve25519_mul(c, t0, b);
391 /* 2^200 - 2^100 */ curve25519_square_times(t0, c, 100);
392 /* 2^200 - 2^0 */ curve25519_mul(t0, t0, c);
393 /* 2^250 - 2^50 */ curve25519_square_times(t0, t0, 50);
394 /* 2^250 - 2^0 */ curve25519_mul(b, t0, b);
395}
396
397/*
398 * z^(p - 2) = z(2^255 - 21)
399 */
400void
401curve25519_recip(bignum25519 out, const bignum25519 z) {
402 ALIGN(ALIGN_SPEC) bignum25519 a, t0, b;
403
404 /* 2 */ curve25519_square(a, z); /* a = 2 */
405 /* 8 */ curve25519_square_times(t0, a, 2);
406 /* 9 */ curve25519_mul(b, t0, z); /* b = 9 */
407 /* 11 */ curve25519_mul(a, b, a); /* a = 11 */
408 /* 22 */ curve25519_square(t0, a);
409 /* 2^5 - 2^0 = 31 */ curve25519_mul(b, t0, b);
410 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
411 /* 2^255 - 2^5 */ curve25519_square_times(b, b, 5);
412 /* 2^255 - 21 */ curve25519_mul(out, b, a);
413}
414
415ANONYMOUS_NAMESPACE_END
416NAMESPACE_END // X25519
417NAMESPACE_END // Donna
418NAMESPACE_END // CryptoPP
419
420//******************************* ed25519 *******************************//
421
422NAMESPACE_BEGIN(CryptoPP)
423NAMESPACE_BEGIN(Donna)
424NAMESPACE_BEGIN(Ed25519)
425ANONYMOUS_NAMESPACE_BEGIN
426
427using CryptoPP::byte;
428using CryptoPP::word32;
429using CryptoPP::sword32;
430using CryptoPP::word64;
431using CryptoPP::sword64;
432
433using CryptoPP::GetBlock;
434using CryptoPP::LittleEndian;
435
436using CryptoPP::SHA512;
437
438// Bring in all the symbols from the 64-bit header
439using namespace CryptoPP::Donna::Arch64;
440
441/* out = in */
442inline void
443curve25519_copy(bignum25519 out, const bignum25519 in) {
444 out[0] = in[0]; out[1] = in[1];
445 out[2] = in[2]; out[3] = in[3];
446 out[4] = in[4];
447}
448
449/* out = a + b */
450inline void
451curve25519_add(bignum25519 out, const bignum25519 a, const bignum25519 b) {
452 out[0] = a[0] + b[0]; out[1] = a[1] + b[1];
453 out[2] = a[2] + b[2]; out[3] = a[3] + b[3];
454 out[4] = a[4] + b[4];
455}
456
457/* out = a + b, where a and/or b are the result of a basic op (add,sub) */
458inline void
459curve25519_add_after_basic(bignum25519 out, const bignum25519 a, const bignum25519 b) {
460 out[0] = a[0] + b[0]; out[1] = a[1] + b[1];
461 out[2] = a[2] + b[2]; out[3] = a[3] + b[3];
462 out[4] = a[4] + b[4];
463}
464
465inline void
466curve25519_add_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) {
467 word64 c;
468 out[0] = a[0] + b[0] ; c = (out[0] >> 51); out[0] &= reduce_mask_51;
469 out[1] = a[1] + b[1] + c; c = (out[1] >> 51); out[1] &= reduce_mask_51;
470 out[2] = a[2] + b[2] + c; c = (out[2] >> 51); out[2] &= reduce_mask_51;
471 out[3] = a[3] + b[3] + c; c = (out[3] >> 51); out[3] &= reduce_mask_51;
472 out[4] = a[4] + b[4] + c; c = (out[4] >> 51); out[4] &= reduce_mask_51;
473 out[0] += c * 19;
474}
475
476/* out = a - b */
477inline void
478curve25519_sub(bignum25519 out, const bignum25519 a, const bignum25519 b) {
479 out[0] = a[0] + twoP0 - b[0];
480 out[1] = a[1] + twoP1234 - b[1];
481 out[2] = a[2] + twoP1234 - b[2];
482 out[3] = a[3] + twoP1234 - b[3];
483 out[4] = a[4] + twoP1234 - b[4];
484}
485
486/* out = a - b, where a and/or b are the result of a basic op (add,sub) */
487inline void
488curve25519_sub_after_basic(bignum25519 out, const bignum25519 a, const bignum25519 b) {
489 out[0] = a[0] + fourP0 - b[0];
490 out[1] = a[1] + fourP1234 - b[1];
491 out[2] = a[2] + fourP1234 - b[2];
492 out[3] = a[3] + fourP1234 - b[3];
493 out[4] = a[4] + fourP1234 - b[4];
494}
495
496inline void
497curve25519_sub_reduce(bignum25519 out, const bignum25519 a, const bignum25519 b) {
498 word64 c;
499 out[0] = a[0] + fourP0 - b[0] ; c = (out[0] >> 51); out[0] &= reduce_mask_51;
500 out[1] = a[1] + fourP1234 - b[1] + c; c = (out[1] >> 51); out[1] &= reduce_mask_51;
501 out[2] = a[2] + fourP1234 - b[2] + c; c = (out[2] >> 51); out[2] &= reduce_mask_51;
502 out[3] = a[3] + fourP1234 - b[3] + c; c = (out[3] >> 51); out[3] &= reduce_mask_51;
503 out[4] = a[4] + fourP1234 - b[4] + c; c = (out[4] >> 51); out[4] &= reduce_mask_51;
504 out[0] += c * 19;
505}
506
507/* out = -a */
508inline void
509curve25519_neg(bignum25519 out, const bignum25519 a) {
510 word64 c;
511 out[0] = twoP0 - a[0] ; c = (out[0] >> 51); out[0] &= reduce_mask_51;
512 out[1] = twoP1234 - a[1] + c; c = (out[1] >> 51); out[1] &= reduce_mask_51;
513 out[2] = twoP1234 - a[2] + c; c = (out[2] >> 51); out[2] &= reduce_mask_51;
514 out[3] = twoP1234 - a[3] + c; c = (out[3] >> 51); out[3] &= reduce_mask_51;
515 out[4] = twoP1234 - a[4] + c; c = (out[4] >> 51); out[4] &= reduce_mask_51;
516 out[0] += c * 19;
517}
518
519/* out = a * b */
520inline void
521curve25519_mul(bignum25519 out, const bignum25519 in2, const bignum25519 in) {
522#if !defined(CRYPTOPP_WORD128_AVAILABLE)
523 word128 mul;
524#endif
525 word128 t[5];
526 word64 r0,r1,r2,r3,r4,s0,s1,s2,s3,s4,c;
527
528 r0 = in[0]; r1 = in[1];
529 r2 = in[2]; r3 = in[3];
530 r4 = in[4];
531
532 s0 = in2[0]; s1 = in2[1];
533 s2 = in2[2]; s3 = in2[3];
534 s4 = in2[4];
535
536#if defined(CRYPTOPP_WORD128_AVAILABLE)
537 t[0] = ((word128) r0) * s0;
538 t[1] = ((word128) r0) * s1 + ((word128) r1) * s0;
539 t[2] = ((word128) r0) * s2 + ((word128) r2) * s0 + ((word128) r1) * s1;
540 t[3] = ((word128) r0) * s3 + ((word128) r3) * s0 + ((word128) r1) * s2 + ((word128) r2) * s1;
541 t[4] = ((word128) r0) * s4 + ((word128) r4) * s0 + ((word128) r3) * s1 + ((word128) r1) * s3 + ((word128) r2) * s2;
542#else
543 mul64x64_128(t[0], r0, s0)
544 mul64x64_128(t[1], r0, s1) mul64x64_128(mul, r1, s0) add128(t[1], mul)
545 mul64x64_128(t[2], r0, s2) mul64x64_128(mul, r2, s0) add128(t[2], mul) mul64x64_128(mul, r1, s1) add128(t[2], mul)
546 mul64x64_128(t[3], r0, s3) mul64x64_128(mul, r3, s0) add128(t[3], mul) mul64x64_128(mul, r1, s2) add128(t[3], mul) mul64x64_128(mul, r2, s1) add128(t[3], mul)
547 mul64x64_128(t[4], r0, s4) mul64x64_128(mul, r4, s0) add128(t[4], mul) mul64x64_128(mul, r3, s1) add128(t[4], mul) mul64x64_128(mul, r1, s3) add128(t[4], mul) mul64x64_128(mul, r2, s2) add128(t[4], mul)
548#endif
549
550 r1 *= 19; r2 *= 19;
551 r3 *= 19; r4 *= 19;
552
553#if defined(CRYPTOPP_WORD128_AVAILABLE)
554 t[0] += ((word128) r4) * s1 + ((word128) r1) * s4 + ((word128) r2) * s3 + ((word128) r3) * s2;
555 t[1] += ((word128) r4) * s2 + ((word128) r2) * s4 + ((word128) r3) * s3;
556 t[2] += ((word128) r4) * s3 + ((word128) r3) * s4;
557 t[3] += ((word128) r4) * s4;
558#else
559 mul64x64_128(mul, r4, s1) add128(t[0], mul) mul64x64_128(mul, r1, s4) add128(t[0], mul) mul64x64_128(mul, r2, s3) add128(t[0], mul) mul64x64_128(mul, r3, s2) add128(t[0], mul)
560 mul64x64_128(mul, r4, s2) add128(t[1], mul) mul64x64_128(mul, r2, s4) add128(t[1], mul) mul64x64_128(mul, r3, s3) add128(t[1], mul)
561 mul64x64_128(mul, r4, s3) add128(t[2], mul) mul64x64_128(mul, r3, s4) add128(t[2], mul)
562 mul64x64_128(mul, r4, s4) add128(t[3], mul)
563#endif
564
565 r0 = lo128(t[0]) & reduce_mask_51; shr128(c, t[0], 51);
566 add128_64(t[1], c) r1 = lo128(t[1]) & reduce_mask_51; shr128(c, t[1], 51);
567 add128_64(t[2], c) r2 = lo128(t[2]) & reduce_mask_51; shr128(c, t[2], 51);
568 add128_64(t[3], c) r3 = lo128(t[3]) & reduce_mask_51; shr128(c, t[3], 51);
569 add128_64(t[4], c) r4 = lo128(t[4]) & reduce_mask_51; shr128(c, t[4], 51);
570 r0 += c * 19; c = r0 >> 51; r0 = r0 & reduce_mask_51;
571 r1 += c;
572
573 out[0] = r0; out[1] = r1;
574 out[2] = r2; out[3] = r3;
575 out[4] = r4;
576}
577
578void
579curve25519_mul_noinline(bignum25519 out, const bignum25519 in2, const bignum25519 in) {
580 curve25519_mul(out, in2, in);
581}
582
583/* out = in^(2 * count) */
584void
585curve25519_square_times(bignum25519 out, const bignum25519 in, word64 count) {
586#if !defined(CRYPTOPP_WORD128_AVAILABLE)
587 word128 mul;
588#endif
589 word128 t[5];
590 word64 r0,r1,r2,r3,r4,c;
591 word64 d0,d1,d2,d4,d419;
592
593 r0 = in[0]; r1 = in[1];
594 r2 = in[2]; r3 = in[3];
595 r4 = in[4];
596
597 do {
598 d0 = r0 * 2;
599 d1 = r1 * 2;
600 d2 = r2 * 2 * 19;
601 d419 = r4 * 19;
602 d4 = d419 * 2;
603
604#if defined(CRYPTOPP_WORD128_AVAILABLE)
605 t[0] = ((word128) r0) * r0 + ((word128) d4) * r1 + (((word128) d2) * (r3 ));
606 t[1] = ((word128) d0) * r1 + ((word128) d4) * r2 + (((word128) r3) * (r3 * 19));
607 t[2] = ((word128) d0) * r2 + ((word128) r1) * r1 + (((word128) d4) * (r3 ));
608 t[3] = ((word128) d0) * r3 + ((word128) d1) * r2 + (((word128) r4) * (d419 ));
609 t[4] = ((word128) d0) * r4 + ((word128) d1) * r3 + (((word128) r2) * (r2 ));
610#else
611 mul64x64_128(t[0], r0, r0) mul64x64_128(mul, d4, r1) add128(t[0], mul) mul64x64_128(mul, d2, r3) add128(t[0], mul)
612 mul64x64_128(t[1], d0, r1) mul64x64_128(mul, d4, r2) add128(t[1], mul) mul64x64_128(mul, r3, r3 * 19) add128(t[1], mul)
613 mul64x64_128(t[2], d0, r2) mul64x64_128(mul, r1, r1) add128(t[2], mul) mul64x64_128(mul, d4, r3) add128(t[2], mul)
614 mul64x64_128(t[3], d0, r3) mul64x64_128(mul, d1, r2) add128(t[3], mul) mul64x64_128(mul, r4, d419) add128(t[3], mul)
615 mul64x64_128(t[4], d0, r4) mul64x64_128(mul, d1, r3) add128(t[4], mul) mul64x64_128(mul, r2, r2) add128(t[4], mul)
616#endif
617
618 r0 = lo128(t[0]) & reduce_mask_51;
619 r1 = lo128(t[1]) & reduce_mask_51; shl128(c, t[0], 13); r1 += c;
620 r2 = lo128(t[2]) & reduce_mask_51; shl128(c, t[1], 13); r2 += c;
621 r3 = lo128(t[3]) & reduce_mask_51; shl128(c, t[2], 13); r3 += c;
622 r4 = lo128(t[4]) & reduce_mask_51; shl128(c, t[3], 13); r4 += c;
623 shl128(c, t[4], 13); r0 += c * 19;
624 c = r0 >> 51; r0 &= reduce_mask_51;
625 r1 += c ; c = r1 >> 51; r1 &= reduce_mask_51;
626 r2 += c ; c = r2 >> 51; r2 &= reduce_mask_51;
627 r3 += c ; c = r3 >> 51; r3 &= reduce_mask_51;
628 r4 += c ; c = r4 >> 51; r4 &= reduce_mask_51;
629 r0 += c * 19;
630 } while(--count);
631
632 out[0] = r0; out[1] = r1;
633 out[2] = r2; out[3] = r3;
634 out[4] = r4;
635}
636
637inline void
638curve25519_square(bignum25519 out, const bignum25519 in) {
639#if !defined(CRYPTOPP_WORD128_AVAILABLE)
640 word128 mul;
641#endif
642 word128 t[5];
643 word64 r0,r1,r2,r3,r4,c;
644 word64 d0,d1,d2,d4,d419;
645
646 r0 = in[0]; r1 = in[1];
647 r2 = in[2]; r3 = in[3];
648 r4 = in[4];
649
650 d0 = r0 * 2; d1 = r1 * 2;
651 d2 = r2 * 2 * 19;
652 d419 = r4 * 19;
653 d4 = d419 * 2;
654
655#if defined(CRYPTOPP_WORD128_AVAILABLE)
656 t[0] = ((word128) r0) * r0 + ((word128) d4) * r1 + (((word128) d2) * (r3 ));
657 t[1] = ((word128) d0) * r1 + ((word128) d4) * r2 + (((word128) r3) * (r3 * 19));
658 t[2] = ((word128) d0) * r2 + ((word128) r1) * r1 + (((word128) d4) * (r3 ));
659 t[3] = ((word128) d0) * r3 + ((word128) d1) * r2 + (((word128) r4) * (d419 ));
660 t[4] = ((word128) d0) * r4 + ((word128) d1) * r3 + (((word128) r2) * (r2 ));
661#else
662 mul64x64_128(t[0], r0, r0) mul64x64_128(mul, d4, r1) add128(t[0], mul) mul64x64_128(mul, d2, r3) add128(t[0], mul)
663 mul64x64_128(t[1], d0, r1) mul64x64_128(mul, d4, r2) add128(t[1], mul) mul64x64_128(mul, r3, r3 * 19) add128(t[1], mul)
664 mul64x64_128(t[2], d0, r2) mul64x64_128(mul, r1, r1) add128(t[2], mul) mul64x64_128(mul, d4, r3) add128(t[2], mul)
665 mul64x64_128(t[3], d0, r3) mul64x64_128(mul, d1, r2) add128(t[3], mul) mul64x64_128(mul, r4, d419) add128(t[3], mul)
666 mul64x64_128(t[4], d0, r4) mul64x64_128(mul, d1, r3) add128(t[4], mul) mul64x64_128(mul, r2, r2) add128(t[4], mul)
667#endif
668
669 r0 = lo128(t[0]) & reduce_mask_51; shr128(c, t[0], 51);
670 add128_64(t[1], c) r1 = lo128(t[1]) & reduce_mask_51; shr128(c, t[1], 51);
671 add128_64(t[2], c) r2 = lo128(t[2]) & reduce_mask_51; shr128(c, t[2], 51);
672 add128_64(t[3], c) r3 = lo128(t[3]) & reduce_mask_51; shr128(c, t[3], 51);
673 add128_64(t[4], c) r4 = lo128(t[4]) & reduce_mask_51; shr128(c, t[4], 51);
674 r0 += c * 19; c = r0 >> 51; r0 = r0 & reduce_mask_51;
675 r1 += c;
676
677 out[0] = r0; out[1] = r1;
678 out[2] = r2; out[3] = r3;
679 out[4] = r4;
680}
681
682/* Take a little-endian, 32-byte number and expand it into polynomial form */
683inline void
684curve25519_expand(bignum25519 out, const byte *in) {
685 word64 x0,x1,x2,x3;
686 GetBlock<word64, LittleEndian> block(in);
687 block(x0)(x1)(x2)(x3);
688
689 out[0] = x0 & reduce_mask_51; x0 = (x0 >> 51) | (x1 << 13);
690 out[1] = x0 & reduce_mask_51; x1 = (x1 >> 38) | (x2 << 26);
691 out[2] = x1 & reduce_mask_51; x2 = (x2 >> 25) | (x3 << 39);
692 out[3] = x2 & reduce_mask_51; x3 = (x3 >> 12);
693 out[4] = x3 & reduce_mask_51;
694}
695
696/* Take a fully reduced polynomial form number and contract it into a
697 * little-endian, 32-byte array
698 */
699inline void
700curve25519_contract(byte *out, const bignum25519 input) {
701 word64 t[5];
702 word64 f, i;
703
704 t[0] = input[0];
705 t[1] = input[1];
706 t[2] = input[2];
707 t[3] = input[3];
708 t[4] = input[4];
709
710 #define curve25519_contract_carry() \
711 t[1] += t[0] >> 51; t[0] &= reduce_mask_51; \
712 t[2] += t[1] >> 51; t[1] &= reduce_mask_51; \
713 t[3] += t[2] >> 51; t[2] &= reduce_mask_51; \
714 t[4] += t[3] >> 51; t[3] &= reduce_mask_51;
715
716 #define curve25519_contract_carry_full() curve25519_contract_carry() \
717 t[0] += 19 * (t[4] >> 51); t[4] &= reduce_mask_51;
718
719 #define curve25519_contract_carry_final() curve25519_contract_carry() \
720 t[4] &= reduce_mask_51;
721
722 curve25519_contract_carry_full()
723 curve25519_contract_carry_full()
724
725 /* now t is between 0 and 2^255-1, properly carried. */
726 /* case 1: between 0 and 2^255-20. case 2: between 2^255-19 and 2^255-1. */
727 t[0] += 19;
728 curve25519_contract_carry_full()
729
730 /* now between 19 and 2^255-1 in both cases, and offset by 19. */
731 t[0] += (reduce_mask_51 + 1) - 19;
732 t[1] += (reduce_mask_51 + 1) - 1;
733 t[2] += (reduce_mask_51 + 1) - 1;
734 t[3] += (reduce_mask_51 + 1) - 1;
735 t[4] += (reduce_mask_51 + 1) - 1;
736
737 /* now between 2^255 and 2^256-20, and offset by 2^255. */
738 curve25519_contract_carry_final()
739
740 #define write51full(n,shift) \
741 f = ((t[n] >> shift) | (t[n+1] << (51 - shift))); \
742 for (i = 0; i < 8; i++, f >>= 8) *out++ = (byte)f;
743 #define write51(n) write51full(n,13*n)
744 write51(0)
745 write51(1)
746 write51(2)
747 write51(3)
748}
749
750#if !defined(ED25519_GCC_64BIT_CHOOSE)
751
752/* out = (flag) ? in : out */
753inline void
754curve25519_move_conditional_bytes(byte out[96], const byte in[96], word64 flag)
755{
756 // TODO: enable this code path once we can test and benchmark it.
757 // It is about 24 insns shorter, it avoids punning which may be UB,
758 // and it is guaranteed constant time.
759#if defined(__GNUC__) && defined(__x86_64__) && 0
760 const word32 iter = 96/sizeof(word64);
761 word64* outq = reinterpret_cast<word64*>(out);
762 const word64* inq = reinterpret_cast<const word64*>(in);
763 word64 idx=0, val;
764
765 __asm__ __volatile__ (
766 ".att_syntax ;\n"
767 "cmpq $0, %[flag] ;\n" // compare, set ZERO flag
768 "movq %[iter], %%rcx ;\n" // load iteration count
769 "1: ;\n"
770 " movq (%[idx],%[out]), %[val] ;\n" // val = out[idx]
771 " cmovnzq (%[idx],%[in]), %[val] ;\n" // copy in[idx] to val if NZ
772 " movq %[val], (%[idx],%[out]) ;\n" // out[idx] = val
773 " leaq 8(%[idx]), %[idx] ;\n" // increment index
774 " loopnz 1b ;\n" // does not affect flags
775 : [out] "+S" (outq), [in] "+D" (inq),
776 [idx] "+b" (idx), [val] "=r" (val)
777 : [flag] "g" (flag), [iter] "I" (iter)
778 : "rcx", "memory", "cc"
779 );
780#else
781 const word64 nb = flag - 1, b = ~nb;
782 const word64 *inq = (const word64 *)(const void*)in;
783 word64 *outq = (word64 *)(void *)out;
784 outq[0] = (outq[0] & nb) | (inq[0] & b);
785 outq[1] = (outq[1] & nb) | (inq[1] & b);
786 outq[2] = (outq[2] & nb) | (inq[2] & b);
787 outq[3] = (outq[3] & nb) | (inq[3] & b);
788 outq[4] = (outq[4] & nb) | (inq[4] & b);
789 outq[5] = (outq[5] & nb) | (inq[5] & b);
790 outq[6] = (outq[6] & nb) | (inq[6] & b);
791 outq[7] = (outq[7] & nb) | (inq[7] & b);
792 outq[8] = (outq[8] & nb) | (inq[8] & b);
793 outq[9] = (outq[9] & nb) | (inq[9] & b);
794 outq[10] = (outq[10] & nb) | (inq[10] & b);
795 outq[11] = (outq[11] & nb) | (inq[11] & b);
796#endif
797}
798
799/* if (iswap) swap(a, b) */
800inline void
801curve25519_swap_conditional(bignum25519 a, bignum25519 b, word64 iswap) {
802 const word64 swap = (word64)(-(sword64)iswap);
803 word64 x0,x1,x2,x3,x4;
804
805 x0 = swap & (a[0] ^ b[0]); a[0] ^= x0; b[0] ^= x0;
806 x1 = swap & (a[1] ^ b[1]); a[1] ^= x1; b[1] ^= x1;
807 x2 = swap & (a[2] ^ b[2]); a[2] ^= x2; b[2] ^= x2;
808 x3 = swap & (a[3] ^ b[3]); a[3] ^= x3; b[3] ^= x3;
809 x4 = swap & (a[4] ^ b[4]); a[4] ^= x4; b[4] ^= x4;
810}
811
812#endif /* ED25519_GCC_64BIT_CHOOSE */
813
814// ************************************************************************************
815
816inline void
817ed25519_hash(byte *hash, const byte *in, size_t inlen) {
818 SHA512().CalculateDigest(hash, in, inlen);
819}
820
821inline void
822ed25519_extsk(hash_512bits extsk, const byte sk[32]) {
823 ed25519_hash(extsk, sk, 32);
824 extsk[0] &= 248;
825 extsk[31] &= 127;
826 extsk[31] |= 64;
827}
828
829void
830UpdateFromStream(HashTransformation& hash, std::istream& stream)
831{
832 SecByteBlock block(4096);
833 while (stream.read((char*)block.begin(), block.size()))
834 hash.Update(block, block.size());
835
836 std::streamsize rem = stream.gcount();
837 if (rem)
838 hash.Update(block, rem);
839
840 block.SetMark(0);
841}
842
843void
844ed25519_hram(hash_512bits hram, const byte RS[64], const byte pk[32], const byte *m, size_t mlen) {
845 SHA512 hash;
846 hash.Update(RS, 32);
847 hash.Update(pk, 32);
848 hash.Update(m, mlen);
849 hash.Final(hram);
850}
851
852void
853ed25519_hram(hash_512bits hram, const byte RS[64], const byte pk[32], std::istream& stream) {
854 SHA512 hash;
855 hash.Update(RS, 32);
856 hash.Update(pk, 32);
857 UpdateFromStream(hash, stream);
858 hash.Final(hram);
859}
860
861bignum256modm_element_t
862lt_modm(bignum256modm_element_t a, bignum256modm_element_t b) {
863 return (a - b) >> 63;
864}
865
866void
867reduce256_modm(bignum256modm r) {
868 bignum256modm t;
869 bignum256modm_element_t b = 0, pb, mask;
870
871 /* t = r - m */
872 pb = 0;
873 pb += modm_m[0]; b = lt_modm(r[0], pb); t[0] = (r[0] - pb + (b << 56)); pb = b;
874 pb += modm_m[1]; b = lt_modm(r[1], pb); t[1] = (r[1] - pb + (b << 56)); pb = b;
875 pb += modm_m[2]; b = lt_modm(r[2], pb); t[2] = (r[2] - pb + (b << 56)); pb = b;
876 pb += modm_m[3]; b = lt_modm(r[3], pb); t[3] = (r[3] - pb + (b << 56)); pb = b;
877 pb += modm_m[4]; b = lt_modm(r[4], pb); t[4] = (r[4] - pb + (b << 32));
878
879 /* keep r if r was smaller than m */
880 mask = b - 1;
881
882 r[0] ^= mask & (r[0] ^ t[0]);
883 r[1] ^= mask & (r[1] ^ t[1]);
884 r[2] ^= mask & (r[2] ^ t[2]);
885 r[3] ^= mask & (r[3] ^ t[3]);
886 r[4] ^= mask & (r[4] ^ t[4]);
887}
888
889void
890barrett_reduce256_modm(bignum256modm r, const bignum256modm q1, const bignum256modm r1) {
891 bignum256modm q3, r2;
892 word128 c, mul;
893 bignum256modm_element_t f, b, pb;
894
895 /* q1 = x >> 248 = 264 bits = 5 56 bit elements
896 q2 = mu * q1
897 q3 = (q2 / 256(32+1)) = q2 / (2^8)^(32+1) = q2 >> 264 */
898 mul64x64_128(c, modm_mu[0], q1[3]) mul64x64_128(mul, modm_mu[3], q1[0]) add128(c, mul) mul64x64_128(mul, modm_mu[1], q1[2]) add128(c, mul) mul64x64_128(mul, modm_mu[2], q1[1]) add128(c, mul) shr128(f, c, 56);
899 mul64x64_128(c, modm_mu[0], q1[4]) add128_64(c, f) mul64x64_128(mul, modm_mu[4], q1[0]) add128(c, mul) mul64x64_128(mul, modm_mu[3], q1[1]) add128(c, mul) mul64x64_128(mul, modm_mu[1], q1[3]) add128(c, mul) mul64x64_128(mul, modm_mu[2], q1[2]) add128(c, mul)
900 f = lo128(c); q3[0] = (f >> 40) & 0xffff; shr128(f, c, 56);
901 mul64x64_128(c, modm_mu[4], q1[1]) add128_64(c, f) mul64x64_128(mul, modm_mu[1], q1[4]) add128(c, mul) mul64x64_128(mul, modm_mu[2], q1[3]) add128(c, mul) mul64x64_128(mul, modm_mu[3], q1[2]) add128(c, mul)
902 f = lo128(c); q3[0] |= (f << 16) & 0xffffffffffffff; q3[1] = (f >> 40) & 0xffff; shr128(f, c, 56);
903 mul64x64_128(c, modm_mu[4], q1[2]) add128_64(c, f) mul64x64_128(mul, modm_mu[2], q1[4]) add128(c, mul) mul64x64_128(mul, modm_mu[3], q1[3]) add128(c, mul)
904 f = lo128(c); q3[1] |= (f << 16) & 0xffffffffffffff; q3[2] = (f >> 40) & 0xffff; shr128(f, c, 56);
905 mul64x64_128(c, modm_mu[4], q1[3]) add128_64(c, f) mul64x64_128(mul, modm_mu[3], q1[4]) add128(c, mul)
906 f = lo128(c); q3[2] |= (f << 16) & 0xffffffffffffff; q3[3] = (f >> 40) & 0xffff; shr128(f, c, 56);
907 mul64x64_128(c, modm_mu[4], q1[4]) add128_64(c, f)
908 f = lo128(c); q3[3] |= (f << 16) & 0xffffffffffffff; q3[4] = (f >> 40) & 0xffff; shr128(f, c, 56);
909 q3[4] |= (f << 16);
910
911 mul64x64_128(c, modm_m[0], q3[0])
912 r2[0] = lo128(c) & 0xffffffffffffff; shr128(f, c, 56);
913 mul64x64_128(c, modm_m[0], q3[1]) add128_64(c, f) mul64x64_128(mul, modm_m[1], q3[0]) add128(c, mul)
914 r2[1] = lo128(c) & 0xffffffffffffff; shr128(f, c, 56);
915 mul64x64_128(c, modm_m[0], q3[2]) add128_64(c, f) mul64x64_128(mul, modm_m[2], q3[0]) add128(c, mul) mul64x64_128(mul, modm_m[1], q3[1]) add128(c, mul)
916 r2[2] = lo128(c) & 0xffffffffffffff; shr128(f, c, 56);
917 mul64x64_128(c, modm_m[0], q3[3]) add128_64(c, f) mul64x64_128(mul, modm_m[3], q3[0]) add128(c, mul) mul64x64_128(mul, modm_m[1], q3[2]) add128(c, mul) mul64x64_128(mul, modm_m[2], q3[1]) add128(c, mul)
918 r2[3] = lo128(c) & 0xffffffffffffff; shr128(f, c, 56);
919 mul64x64_128(c, modm_m[0], q3[4]) add128_64(c, f) mul64x64_128(mul, modm_m[4], q3[0]) add128(c, mul) mul64x64_128(mul, modm_m[3], q3[1]) add128(c, mul) mul64x64_128(mul, modm_m[1], q3[3]) add128(c, mul) mul64x64_128(mul, modm_m[2], q3[2]) add128(c, mul)
920 r2[4] = lo128(c) & 0x0000ffffffffff;
921
922 pb = 0;
923 pb += r2[0]; b = lt_modm(r1[0], pb); r[0] = (r1[0] - pb + (b << 56)); pb = b;
924 pb += r2[1]; b = lt_modm(r1[1], pb); r[1] = (r1[1] - pb + (b << 56)); pb = b;
925 pb += r2[2]; b = lt_modm(r1[2], pb); r[2] = (r1[2] - pb + (b << 56)); pb = b;
926 pb += r2[3]; b = lt_modm(r1[3], pb); r[3] = (r1[3] - pb + (b << 56)); pb = b;
927 pb += r2[4]; b = lt_modm(r1[4], pb); r[4] = (r1[4] - pb + (b << 40));
928
929 reduce256_modm(r);
930 reduce256_modm(r);
931}
932
933void
934add256_modm(bignum256modm r, const bignum256modm x, const bignum256modm y) {
935 bignum256modm_element_t c;
936
937 c = x[0] + y[0]; r[0] = c & 0xffffffffffffff; c >>= 56;
938 c += x[1] + y[1]; r[1] = c & 0xffffffffffffff; c >>= 56;
939 c += x[2] + y[2]; r[2] = c & 0xffffffffffffff; c >>= 56;
940 c += x[3] + y[3]; r[3] = c & 0xffffffffffffff; c >>= 56;
941 c += x[4] + y[4]; r[4] = c;
942
943 reduce256_modm(r);
944}
945
946void
947mul256_modm(bignum256modm r, const bignum256modm x, const bignum256modm y) {
948 bignum256modm q1, r1;
949 word128 c, mul;
950 bignum256modm_element_t f;
951
952 mul64x64_128(c, x[0], y[0])
953 f = lo128(c); r1[0] = f & 0xffffffffffffff; shr128(f, c, 56);
954 mul64x64_128(c, x[0], y[1]) add128_64(c, f) mul64x64_128(mul, x[1], y[0]) add128(c, mul)
955 f = lo128(c); r1[1] = f & 0xffffffffffffff; shr128(f, c, 56);
956 mul64x64_128(c, x[0], y[2]) add128_64(c, f) mul64x64_128(mul, x[2], y[0]) add128(c, mul) mul64x64_128(mul, x[1], y[1]) add128(c, mul)
957 f = lo128(c); r1[2] = f & 0xffffffffffffff; shr128(f, c, 56);
958 mul64x64_128(c, x[0], y[3]) add128_64(c, f) mul64x64_128(mul, x[3], y[0]) add128(c, mul) mul64x64_128(mul, x[1], y[2]) add128(c, mul) mul64x64_128(mul, x[2], y[1]) add128(c, mul)
959 f = lo128(c); r1[3] = f & 0xffffffffffffff; shr128(f, c, 56);
960 mul64x64_128(c, x[0], y[4]) add128_64(c, f) mul64x64_128(mul, x[4], y[0]) add128(c, mul) mul64x64_128(mul, x[3], y[1]) add128(c, mul) mul64x64_128(mul, x[1], y[3]) add128(c, mul) mul64x64_128(mul, x[2], y[2]) add128(c, mul)
961 f = lo128(c); r1[4] = f & 0x0000ffffffffff; q1[0] = (f >> 24) & 0xffffffff; shr128(f, c, 56);
962 mul64x64_128(c, x[4], y[1]) add128_64(c, f) mul64x64_128(mul, x[1], y[4]) add128(c, mul) mul64x64_128(mul, x[2], y[3]) add128(c, mul) mul64x64_128(mul, x[3], y[2]) add128(c, mul)
963 f = lo128(c); q1[0] |= (f << 32) & 0xffffffffffffff; q1[1] = (f >> 24) & 0xffffffff; shr128(f, c, 56);
964 mul64x64_128(c, x[4], y[2]) add128_64(c, f) mul64x64_128(mul, x[2], y[4]) add128(c, mul) mul64x64_128(mul, x[3], y[3]) add128(c, mul)
965 f = lo128(c); q1[1] |= (f << 32) & 0xffffffffffffff; q1[2] = (f >> 24) & 0xffffffff; shr128(f, c, 56);
966 mul64x64_128(c, x[4], y[3]) add128_64(c, f) mul64x64_128(mul, x[3], y[4]) add128(c, mul)
967 f = lo128(c); q1[2] |= (f << 32) & 0xffffffffffffff; q1[3] = (f >> 24) & 0xffffffff; shr128(f, c, 56);
968 mul64x64_128(c, x[4], y[4]) add128_64(c, f)
969 f = lo128(c); q1[3] |= (f << 32) & 0xffffffffffffff; q1[4] = (f >> 24) & 0xffffffff; shr128(f, c, 56);
970 q1[4] |= (f << 32);
971
972 barrett_reduce256_modm(r, q1, r1);
973}
974
975void
976expand256_modm(bignum256modm out, const byte *in, size_t len) {
977 byte work[64] = {0};
978 bignum256modm_element_t x[16];
979 bignum256modm q1;
980
981 memcpy(work, in, len);
982 x[0] = U8TO64_LE(work + 0);
983 x[1] = U8TO64_LE(work + 8);
984 x[2] = U8TO64_LE(work + 16);
985 x[3] = U8TO64_LE(work + 24);
986 x[4] = U8TO64_LE(work + 32);
987 x[5] = U8TO64_LE(work + 40);
988 x[6] = U8TO64_LE(work + 48);
989 x[7] = U8TO64_LE(work + 56);
990
991 /* r1 = (x mod 256^(32+1)) = x mod (2^8)(31+1) = x & ((1 << 264) - 1) */
992 out[0] = ( x[0]) & 0xffffffffffffff;
993 out[1] = ((x[ 0] >> 56) | (x[ 1] << 8)) & 0xffffffffffffff;
994 out[2] = ((x[ 1] >> 48) | (x[ 2] << 16)) & 0xffffffffffffff;
995 out[3] = ((x[ 2] >> 40) | (x[ 3] << 24)) & 0xffffffffffffff;
996 out[4] = ((x[ 3] >> 32) | (x[ 4] << 32)) & 0x0000ffffffffff;
997
998 /* under 252 bits, no need to reduce */
999 if (len < 32)
1000 return;
1001
1002 /* q1 = x >> 248 = 264 bits */
1003 q1[0] = ((x[ 3] >> 56) | (x[ 4] << 8)) & 0xffffffffffffff;
1004 q1[1] = ((x[ 4] >> 48) | (x[ 5] << 16)) & 0xffffffffffffff;
1005 q1[2] = ((x[ 5] >> 40) | (x[ 6] << 24)) & 0xffffffffffffff;
1006 q1[3] = ((x[ 6] >> 32) | (x[ 7] << 32)) & 0xffffffffffffff;
1007 q1[4] = ((x[ 7] >> 24) );
1008
1009 barrett_reduce256_modm(out, q1, out);
1010}
1011
1012void
1013expand_raw256_modm(bignum256modm out, const byte in[32]) {
1014 bignum256modm_element_t x[4];
1015
1016 x[0] = U8TO64_LE(in + 0);
1017 x[1] = U8TO64_LE(in + 8);
1018 x[2] = U8TO64_LE(in + 16);
1019 x[3] = U8TO64_LE(in + 24);
1020
1021 out[0] = ( x[0]) & 0xffffffffffffff;
1022 out[1] = ((x[ 0] >> 56) | (x[ 1] << 8)) & 0xffffffffffffff;
1023 out[2] = ((x[ 1] >> 48) | (x[ 2] << 16)) & 0xffffffffffffff;
1024 out[3] = ((x[ 2] >> 40) | (x[ 3] << 24)) & 0xffffffffffffff;
1025 out[4] = ((x[ 3] >> 32) ) & 0x000000ffffffff;
1026}
1027
1028void
1029contract256_modm(byte out[32], const bignum256modm in) {
1030 U64TO8_LE(out + 0, (in[0] ) | (in[1] << 56));
1031 U64TO8_LE(out + 8, (in[1] >> 8) | (in[2] << 48));
1032 U64TO8_LE(out + 16, (in[2] >> 16) | (in[3] << 40));
1033 U64TO8_LE(out + 24, (in[3] >> 24) | (in[4] << 32));
1034}
1035
1036void
1037contract256_window4_modm(signed char r[64], const bignum256modm in) {
1038 char carry;
1039 signed char *quads = r;
1040 bignum256modm_element_t i, j, v, m;
1041
1042 for (i = 0; i < 5; i++) {
1043 v = in[i];
1044 m = (i == 4) ? 8 : 14;
1045 for (j = 0; j < m; j++) {
1046 *quads++ = (v & 15);
1047 v >>= 4;
1048 }
1049 }
1050
1051 /* making it signed */
1052 carry = 0;
1053 for(i = 0; i < 63; i++) {
1054 r[i] += carry;
1055 r[i+1] += (r[i] >> 4);
1056 r[i] &= 15;
1057 carry = (r[i] >> 3);
1058 r[i] -= (carry << 4);
1059 }
1060 r[63] += carry;
1061}
1062
1063void
1064contract256_slidingwindow_modm(signed char r[256], const bignum256modm s, int windowsize) {
1065 int i,j,k,b;
1066 int m = (1 << (windowsize - 1)) - 1, soplen = 256;
1067 signed char *bits = r;
1068 bignum256modm_element_t v;
1069
1070 /* first put the binary expansion into r */
1071 for (i = 0; i < 4; i++) {
1072 v = s[i];
1073 for (j = 0; j < 56; j++, v >>= 1)
1074 *bits++ = (v & 1);
1075 }
1076 v = s[4];
1077 for (j = 0; j < 32; j++, v >>= 1)
1078 *bits++ = (v & 1);
1079
1080 /* Making it sliding window */
1081 for (j = 0; j < soplen; j++) {
1082 if (!r[j])
1083 continue;
1084
1085 for (b = 1; (b < (soplen - j)) && (b <= 6); b++) {
1086 if ((r[j] + (r[j + b] << b)) <= m) {
1087 r[j] += r[j + b] << b;
1088 r[j + b] = 0;
1089 } else if ((r[j] - (r[j + b] << b)) >= -m) {
1090 r[j] -= r[j + b] << b;
1091 for (k = j + b; k < soplen; k++) {
1092 if (!r[k]) {
1093 r[k] = 1;
1094 break;
1095 }
1096 r[k] = 0;
1097 }
1098 } else if (r[j + b]) {
1099 break;
1100 }
1101 }
1102 }
1103}
1104
1105/*
1106 * In: b = 2^5 - 2^0
1107 * Out: b = 2^250 - 2^0
1108 */
1109void
1110curve25519_pow_two5mtwo0_two250mtwo0(bignum25519 b) {
1111 ALIGN(ALIGN_SPEC) bignum25519 t0,c;
1112
1113 /* 2^5 - 2^0 */ /* b */
1114 /* 2^10 - 2^5 */ curve25519_square_times(t0, b, 5);
1115 /* 2^10 - 2^0 */ curve25519_mul_noinline(b, t0, b);
1116 /* 2^20 - 2^10 */ curve25519_square_times(t0, b, 10);
1117 /* 2^20 - 2^0 */ curve25519_mul_noinline(c, t0, b);
1118 /* 2^40 - 2^20 */ curve25519_square_times(t0, c, 20);
1119 /* 2^40 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
1120 /* 2^50 - 2^10 */ curve25519_square_times(t0, t0, 10);
1121 /* 2^50 - 2^0 */ curve25519_mul_noinline(b, t0, b);
1122 /* 2^100 - 2^50 */ curve25519_square_times(t0, b, 50);
1123 /* 2^100 - 2^0 */ curve25519_mul_noinline(c, t0, b);
1124 /* 2^200 - 2^100 */ curve25519_square_times(t0, c, 100);
1125 /* 2^200 - 2^0 */ curve25519_mul_noinline(t0, t0, c);
1126 /* 2^250 - 2^50 */ curve25519_square_times(t0, t0, 50);
1127 /* 2^250 - 2^0 */ curve25519_mul_noinline(b, t0, b);
1128}
1129
1130/*
1131 * z^(p - 2) = z(2^255 - 21)
1132 */
1133void
1134curve25519_recip(bignum25519 out, const bignum25519 z) {
1135 ALIGN(ALIGN_SPEC) bignum25519 a,t0,b;
1136
1137 /* 2 */ curve25519_square_times(a, z, 1); /* a = 2 */
1138 /* 8 */ curve25519_square_times(t0, a, 2);
1139 /* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
1140 /* 11 */ curve25519_mul_noinline(a, b, a); /* a = 11 */
1141 /* 22 */ curve25519_square_times(t0, a, 1);
1142 /* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
1143 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
1144 /* 2^255 - 2^5 */ curve25519_square_times(b, b, 5);
1145 /* 2^255 - 21 */ curve25519_mul_noinline(out, b, a);
1146}
1147
1148/*
1149 * z^((p-5)/8) = z^(2^252 - 3)
1150 */
1151void
1152curve25519_pow_two252m3(bignum25519 two252m3, const bignum25519 z) {
1153 ALIGN(ALIGN_SPEC) bignum25519 b,c,t0;
1154
1155 /* 2 */ curve25519_square_times(c, z, 1); /* c = 2 */
1156 /* 8 */ curve25519_square_times(t0, c, 2); /* t0 = 8 */
1157 /* 9 */ curve25519_mul_noinline(b, t0, z); /* b = 9 */
1158 /* 11 */ curve25519_mul_noinline(c, b, c); /* c = 11 */
1159 /* 22 */ curve25519_square_times(t0, c, 1);
1160 /* 2^5 - 2^0 = 31 */ curve25519_mul_noinline(b, t0, b);
1161 /* 2^250 - 2^0 */ curve25519_pow_two5mtwo0_two250mtwo0(b);
1162 /* 2^252 - 2^2 */ curve25519_square_times(b, b, 2);
1163 /* 2^252 - 3 */ curve25519_mul_noinline(two252m3, b, z);
1164}
1165
1166inline void
1167ge25519_p1p1_to_partial(ge25519 *r, const ge25519_p1p1 *p) {
1168 curve25519_mul(r->x, p->x, p->t);
1169 curve25519_mul(r->y, p->y, p->z);
1170 curve25519_mul(r->z, p->z, p->t);
1171}
1172
1173inline void
1174ge25519_p1p1_to_full(ge25519 *r, const ge25519_p1p1 *p) {
1175 curve25519_mul(r->x, p->x, p->t);
1176 curve25519_mul(r->y, p->y, p->z);
1177 curve25519_mul(r->z, p->z, p->t);
1178 curve25519_mul(r->t, p->x, p->y);
1179}
1180
1181void
1182ge25519_full_to_pniels(ge25519_pniels *p, const ge25519 *r) {
1183 curve25519_sub(p->ysubx, r->y, r->x);
1184 curve25519_add(p->xaddy, r->y, r->x);
1185 curve25519_copy(p->z, r->z);
1186 curve25519_mul(p->t2d, r->t, ge25519_ec2d);
1187}
1188
1189void
1190ge25519_add_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519 *q) {
1191 bignum25519 a,b,c,d,t,u;
1192
1193 curve25519_sub(a, p->y, p->x);
1194 curve25519_add(b, p->y, p->x);
1195 curve25519_sub(t, q->y, q->x);
1196 curve25519_add(u, q->y, q->x);
1197 curve25519_mul(a, a, t);
1198 curve25519_mul(b, b, u);
1199 curve25519_mul(c, p->t, q->t);
1200 curve25519_mul(c, c, ge25519_ec2d);
1201 curve25519_mul(d, p->z, q->z);
1202 curve25519_add(d, d, d);
1203 curve25519_sub(r->x, b, a);
1204 curve25519_add(r->y, b, a);
1205 curve25519_add_after_basic(r->z, d, c);
1206 curve25519_sub_after_basic(r->t, d, c);
1207}
1208
1209void
1210ge25519_double_p1p1(ge25519_p1p1 *r, const ge25519 *p) {
1211 bignum25519 a,b,c;
1212
1213 curve25519_square(a, p->x);
1214 curve25519_square(b, p->y);
1215 curve25519_square(c, p->z);
1216 curve25519_add_reduce(c, c, c);
1217 curve25519_add(r->x, p->x, p->y);
1218 curve25519_square(r->x, r->x);
1219 curve25519_add(r->y, b, a);
1220 curve25519_sub(r->z, b, a);
1221 curve25519_sub_after_basic(r->x, r->x, r->y);
1222 curve25519_sub_after_basic(r->t, c, r->z);
1223}
1224
1225void
1226ge25519_nielsadd2_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_niels *q, byte signbit) {
1227 const bignum25519 *qb = (const bignum25519 *)q;
1228 bignum25519 *rb = (bignum25519 *)r;
1229 bignum25519 a,b,c;
1230
1231 curve25519_sub(a, p->y, p->x);
1232 curve25519_add(b, p->y, p->x);
1233 curve25519_mul(a, a, qb[signbit]); /* x for +, y for - */
1234 curve25519_mul(r->x, b, qb[signbit^1]); /* y for +, x for - */
1235 curve25519_add(r->y, r->x, a);
1236 curve25519_sub(r->x, r->x, a);
1237 curve25519_mul(c, p->t, q->t2d);
1238 curve25519_add_reduce(r->t, p->z, p->z);
1239 curve25519_copy(r->z, r->t);
1240 curve25519_add(rb[2+signbit], rb[2+signbit], c); /* z for +, t for - */
1241 curve25519_sub(rb[2+(signbit^1)], rb[2+(signbit^1)], c); /* t for +, z for - */
1242}
1243
1244void
1245ge25519_pnielsadd_p1p1(ge25519_p1p1 *r, const ge25519 *p, const ge25519_pniels *q, byte signbit) {
1246 const bignum25519 *qb = (const bignum25519 *)q;
1247 bignum25519 *rb = (bignum25519 *)r;
1248 bignum25519 a,b,c;
1249
1250 curve25519_sub(a, p->y, p->x);
1251 curve25519_add(b, p->y, p->x);
1252 curve25519_mul(a, a, qb[signbit]); /* ysubx for +, xaddy for - */
1253 curve25519_mul(r->x, b, qb[signbit^1]); /* xaddy for +, ysubx for - */
1254 curve25519_add(r->y, r->x, a);
1255 curve25519_sub(r->x, r->x, a);
1256 curve25519_mul(c, p->t, q->t2d);
1257 curve25519_mul(r->t, p->z, q->z);
1258 curve25519_add_reduce(r->t, r->t, r->t);
1259 curve25519_copy(r->z, r->t);
1260 curve25519_add(rb[2+signbit], rb[2+signbit], c); /* z for +, t for - */
1261 curve25519_sub(rb[2+(signbit^1)], rb[2+(signbit^1)], c); /* t for +, z for - */
1262}
1263
1264void
1265ge25519_double_partial(ge25519 *r, const ge25519 *p) {
1266 ge25519_p1p1 t;
1267 ge25519_double_p1p1(&t, p);
1268 ge25519_p1p1_to_partial(r, &t);
1269}
1270
1271void
1272ge25519_double(ge25519 *r, const ge25519 *p) {
1273 ge25519_p1p1 t;
1274 ge25519_double_p1p1(&t, p);
1275 ge25519_p1p1_to_full(r, &t);
1276}
1277
1278void
1279ge25519_add(ge25519 *r, const ge25519 *p, const ge25519 *q) {
1280 ge25519_p1p1 t;
1281 ge25519_add_p1p1(&t, p, q);
1282 ge25519_p1p1_to_full(r, &t);
1283}
1284
1285void
1286ge25519_nielsadd2(ge25519 *r, const ge25519_niels *q) {
1287 bignum25519 a,b,c,e,f,g,h;
1288
1289 curve25519_sub(a, r->y, r->x);
1290 curve25519_add(b, r->y, r->x);
1291 curve25519_mul(a, a, q->ysubx);
1292 curve25519_mul(e, b, q->xaddy);
1293 curve25519_add(h, e, a);
1294 curve25519_sub(e, e, a);
1295 curve25519_mul(c, r->t, q->t2d);
1296 curve25519_add(f, r->z, r->z);
1297 curve25519_add_after_basic(g, f, c);
1298 curve25519_sub_after_basic(f, f, c);
1299 curve25519_mul(r->x, e, f);
1300 curve25519_mul(r->y, h, g);
1301 curve25519_mul(r->z, g, f);
1302 curve25519_mul(r->t, e, h);
1303}
1304
1305void
1306ge25519_pnielsadd(ge25519_pniels *r, const ge25519 *p, const ge25519_pniels *q) {
1307 bignum25519 a,b,c,x,y,z,t;
1308
1309 curve25519_sub(a, p->y, p->x);
1310 curve25519_add(b, p->y, p->x);
1311 curve25519_mul(a, a, q->ysubx);
1312 curve25519_mul(x, b, q->xaddy);
1313 curve25519_add(y, x, a);
1314 curve25519_sub(x, x, a);
1315 curve25519_mul(c, p->t, q->t2d);
1316 curve25519_mul(t, p->z, q->z);
1317 curve25519_add(t, t, t);
1318 curve25519_add_after_basic(z, t, c);
1319 curve25519_sub_after_basic(t, t, c);
1320 curve25519_mul(r->xaddy, x, t);
1321 curve25519_mul(r->ysubx, y, z);
1322 curve25519_mul(r->z, z, t);
1323 curve25519_mul(r->t2d, x, y);
1324 curve25519_copy(y, r->ysubx);
1325 curve25519_sub(r->ysubx, r->ysubx, r->xaddy);
1326 curve25519_add(r->xaddy, r->xaddy, y);
1327 curve25519_mul(r->t2d, r->t2d, ge25519_ec2d);
1328}
1329
1330void
1331ge25519_pack(byte r[32], const ge25519 *p) {
1332 bignum25519 tx, ty, zi;
1333 byte parity[32];
1334 curve25519_recip(zi, p->z);
1335 curve25519_mul(tx, p->x, zi);
1336 curve25519_mul(ty, p->y, zi);
1337 curve25519_contract(r, ty);
1338 curve25519_contract(parity, tx);
1339 r[31] ^= ((parity[0] & 1) << 7);
1340}
1341
1342int
1343ed25519_verify(const byte *x, const byte *y, size_t len) {
1344 size_t differentbits = 0;
1345 while (len--)
1346 differentbits |= (*x++ ^ *y++);
1347 return (int) (1 & ((differentbits - 1) >> 8));
1348}
1349
1350int
1351ge25519_unpack_negative_vartime(ge25519 *r, const byte p[32]) {
1352 const byte zero[32] = {0};
1353 const bignum25519 one = {1};
1354 byte parity = p[31] >> 7;
1355 byte check[32];
1356 bignum25519 t, root, num, den, d3;
1357
1358 curve25519_expand(r->y, p);
1359 curve25519_copy(r->z, one);
1360 curve25519_square(num, r->y); /* x = y^2 */
1361 curve25519_mul(den, num, ge25519_ecd); /* den = dy^2 */
1362 curve25519_sub_reduce(num, num, r->z); /* x = y^1 - 1 */
1363 curve25519_add(den, den, r->z); /* den = dy^2 + 1 */
1364
1365 /* Computation of sqrt(num/den) */
1366 /* 1.: computation of num^((p-5)/8)*den^((7p-35)/8) = (num*den^7)^((p-5)/8) */
1367 curve25519_square(t, den);
1368 curve25519_mul(d3, t, den);
1369 curve25519_square(r->x, d3);
1370 curve25519_mul(r->x, r->x, den);
1371 curve25519_mul(r->x, r->x, num);
1372 curve25519_pow_two252m3(r->x, r->x);
1373
1374 /* 2. computation of r->x = num * den^3 * (num*den^7)^((p-5)/8) */
1375 curve25519_mul(r->x, r->x, d3);
1376 curve25519_mul(r->x, r->x, num);
1377
1378 /* 3. Check if either of the roots works: */
1379 curve25519_square(t, r->x);
1380 curve25519_mul(t, t, den);
1381 curve25519_sub_reduce(root, t, num);
1382 curve25519_contract(check, root);
1383 if (!ed25519_verify(check, zero, 32)) {
1384 curve25519_add_reduce(t, t, num);
1385 curve25519_contract(check, t);
1386 if (!ed25519_verify(check, zero, 32))
1387 return 0;
1388 curve25519_mul(r->x, r->x, ge25519_sqrtneg1);
1389 }
1390
1391 curve25519_contract(check, r->x);
1392 if ((check[0] & 1) == parity) {
1393 curve25519_copy(t, r->x);
1394 curve25519_neg(r->x, t);
1395 }
1396 curve25519_mul(r->t, r->x, r->y);
1397 return 1;
1398}
1399
1400/* computes [s1]p1 + [s2]basepoint */
1401void
1402ge25519_double_scalarmult_vartime(ge25519 *r, const ge25519 *p1, const bignum256modm s1, const bignum256modm s2) {
1403 signed char slide1[256], slide2[256];
1404 ge25519_pniels pre1[S1_TABLE_SIZE];
1405 ge25519 d1;
1406 ge25519_p1p1 t;
1407 sword32 i;
1408
1409 contract256_slidingwindow_modm(slide1, s1, S1_SWINDOWSIZE);
1410 contract256_slidingwindow_modm(slide2, s2, S2_SWINDOWSIZE);
1411
1412 ge25519_double(&d1, p1);
1413 ge25519_full_to_pniels(pre1, p1);
1414 for (i = 0; i < S1_TABLE_SIZE - 1; i++)
1415 ge25519_pnielsadd(&pre1[i+1], &d1, &pre1[i]);
1416
1417 /* set neutral */
1418 memset(r, 0, sizeof(ge25519));
1419 r->y[0] = 1;
1420 r->z[0] = 1;
1421
1422 i = 255;
1423 while ((i >= 0) && !(slide1[i] | slide2[i]))
1424 i--;
1425
1426 for (; i >= 0; i--) {
1427 ge25519_double_p1p1(&t, r);
1428
1429 if (slide1[i]) {
1430 ge25519_p1p1_to_full(r, &t);
1431 ge25519_pnielsadd_p1p1(&t, r, &pre1[abs(slide1[i]) / 2], (byte)slide1[i] >> 7);
1432 }
1433
1434 if (slide2[i]) {
1435 ge25519_p1p1_to_full(r, &t);
1436 ge25519_nielsadd2_p1p1(&t, r, &ge25519_niels_sliding_multiples[abs(slide2[i]) / 2], (byte)slide2[i] >> 7);
1437 }
1438
1439 ge25519_p1p1_to_partial(r, &t);
1440 }
1441}
1442
1443#if !defined(HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS)
1444
1445word32
1446ge25519_windowb_equal(word32 b, word32 c) {
1447 return ((b ^ c) - 1) >> 31;
1448}
1449
1450void
1451ge25519_scalarmult_base_choose_niels(ge25519_niels *t, const byte table[256][96], word32 pos, signed char b) {
1452 bignum25519 neg;
1453 word32 sign = (word32)((byte)b >> 7);
1454 word32 mask = ~(sign - 1);
1455 word32 u = (b + mask) ^ mask;
1456 word32 i;
1457
1458 /* ysubx, xaddy, t2d in packed form. initialize to ysubx = 1, xaddy = 1, t2d = 0 */
1459 byte packed[96] = {0};
1460 packed[0] = 1;
1461 packed[32] = 1;
1462
1463 for (i = 0; i < 8; i++)
1464 curve25519_move_conditional_bytes(packed, table[(pos * 8) + i], ge25519_windowb_equal(u, i + 1));
1465
1466 /* expand in to t */
1467 curve25519_expand(t->ysubx, packed + 0);
1468 curve25519_expand(t->xaddy, packed + 32);
1469 curve25519_expand(t->t2d , packed + 64);
1470
1471 /* adjust for sign */
1472 curve25519_swap_conditional(t->ysubx, t->xaddy, sign);
1473 curve25519_neg(neg, t->t2d);
1474 curve25519_swap_conditional(t->t2d, neg, sign);
1475}
1476
1477#endif /* HAVE_GE25519_SCALARMULT_BASE_CHOOSE_NIELS */
1478
1479/* computes [s]basepoint */
1480void
1481ge25519_scalarmult_base_niels(ge25519 *r, const byte basepoint_table[256][96], const bignum256modm s) {
1482 signed char b[64];
1483 word32 i;
1484 ge25519_niels t;
1485
1486 contract256_window4_modm(b, s);
1487
1488 ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[1]);
1489 curve25519_sub_reduce(r->x, t.xaddy, t.ysubx);
1490 curve25519_add_reduce(r->y, t.xaddy, t.ysubx);
1491 memset(r->z, 0, sizeof(bignum25519));
1492 curve25519_copy(r->t, t.t2d);
1493 r->z[0] = 2;
1494 for (i = 3; i < 64; i += 2) {
1495 ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
1496 ge25519_nielsadd2(r, &t);
1497 }
1498 ge25519_double_partial(r, r);
1499 ge25519_double_partial(r, r);
1500 ge25519_double_partial(r, r);
1501 ge25519_double(r, r);
1502 ge25519_scalarmult_base_choose_niels(&t, basepoint_table, 0, b[0]);
1503 curve25519_mul(t.t2d, t.t2d, ge25519_ecd);
1504 ge25519_nielsadd2(r, &t);
1505 for(i = 2; i < 64; i += 2) {
1506 ge25519_scalarmult_base_choose_niels(&t, basepoint_table, i / 2, b[i]);
1507 ge25519_nielsadd2(r, &t);
1508 }
1509}
1510
1511ANONYMOUS_NAMESPACE_END
1512NAMESPACE_END // Ed25519
1513NAMESPACE_END // Donna
1514NAMESPACE_END // CryptoPP
1515
1516//***************************** curve25519 *****************************//
1517
1518NAMESPACE_BEGIN(CryptoPP)
1519NAMESPACE_BEGIN(Donna)
1520
1521int curve25519_mult_CXX(byte sharedKey[32], const byte secretKey[32], const byte othersKey[32])
1522{
1523 using namespace CryptoPP::Donna::X25519;
1524
1525 FixedSizeSecBlock<byte, 32> e;
1526 for (size_t i = 0;i < 32;++i)
1527 e[i] = secretKey[i];
1528 e[0] &= 0xf8; e[31] &= 0x7f; e[31] |= 0x40;
1529
1530 bignum25519 nqpqx = {1}, nqpqz = {0}, nqz = {1}, nqx;
1531 bignum25519 q, qx, qpqx, qqx, zzz, zmone;
1532 size_t bit, lastbit;
1533
1534 curve25519_expand(q, othersKey);
1535 curve25519_copy(nqx, q);
1536
1537 /* bit 255 is always 0, and bit 254 is always 1, so skip bit 255 and
1538 start pre-swapped on bit 254 */
1539 lastbit = 1;
1540
1541 /* we are doing bits 254..3 in the loop, but are swapping in bits 253..2 */
1542 for (int i = 253; i >= 2; i--) {
1543 curve25519_add(qx, nqx, nqz);
1544 curve25519_sub(nqz, nqx, nqz);
1545 curve25519_add(qpqx, nqpqx, nqpqz);
1546 curve25519_sub(nqpqz, nqpqx, nqpqz);
1547 curve25519_mul(nqpqx, qpqx, nqz);
1548 curve25519_mul(nqpqz, qx, nqpqz);
1549 curve25519_add(qqx, nqpqx, nqpqz);
1550 curve25519_sub(nqpqz, nqpqx, nqpqz);
1551 curve25519_square(nqpqz, nqpqz);
1552 curve25519_square(nqpqx, qqx);
1553 curve25519_mul(nqpqz, nqpqz, q);
1554 curve25519_square(qx, qx);
1555 curve25519_square(nqz, nqz);
1556 curve25519_mul(nqx, qx, nqz);
1557 curve25519_sub(nqz, qx, nqz);
1558 curve25519_scalar_product(zzz, nqz, 121665);
1559 curve25519_add(zzz, zzz, qx);
1560 curve25519_mul(nqz, nqz, zzz);
1561
1562 bit = (e[i/8] >> (i & 7)) & 1;
1563 curve25519_swap_conditional(nqx, nqpqx, bit ^ lastbit);
1564 curve25519_swap_conditional(nqz, nqpqz, bit ^ lastbit);
1565 lastbit = bit;
1566 }
1567
1568 /* the final 3 bits are always zero, so we only need to double */
1569 for (int i = 0; i < 3; i++) {
1570 curve25519_add(qx, nqx, nqz);
1571 curve25519_sub(nqz, nqx, nqz);
1572 curve25519_square(qx, qx);
1573 curve25519_square(nqz, nqz);
1574 curve25519_mul(nqx, qx, nqz);
1575 curve25519_sub(nqz, qx, nqz);
1576 curve25519_scalar_product(zzz, nqz, 121665);
1577 curve25519_add(zzz, zzz, qx);
1578 curve25519_mul(nqz, nqz, zzz);
1579 }
1580
1581 curve25519_recip(zmone, nqz);
1582 curve25519_mul(nqz, nqx, zmone);
1583 curve25519_contract(sharedKey, nqz);
1584
1585 return 0;
1586}
1587
1588int curve25519_mult(byte publicKey[32], const byte secretKey[32])
1589{
1590 using namespace CryptoPP::Donna::X25519;
1591
1592#if (CRYPTOPP_CURVE25519_SSE2)
1593 if (HasSSE2())
1594 return curve25519_mult_SSE2(publicKey, secretKey, basePoint);
1595 else
1596#endif
1597
1598 return curve25519_mult_CXX(publicKey, secretKey, basePoint);
1599}
1600
1601int curve25519_mult(byte sharedKey[32], const byte secretKey[32], const byte othersKey[32])
1602{
1603#if (CRYPTOPP_CURVE25519_SSE2)
1604 if (HasSSE2())
1605 return curve25519_mult_SSE2(sharedKey, secretKey, othersKey);
1606 else
1607#endif
1608
1609 return curve25519_mult_CXX(sharedKey, secretKey, othersKey);
1610}
1611
1612NAMESPACE_END // Donna
1613NAMESPACE_END // CryptoPP
1614
1615//******************************* ed25519 *******************************//
1616
1617NAMESPACE_BEGIN(CryptoPP)
1618NAMESPACE_BEGIN(Donna)
1619
1620int
1621ed25519_publickey_CXX(byte publicKey[32], const byte secretKey[32])
1622{
1623 using namespace CryptoPP::Donna::Ed25519;
1624
1625 bignum256modm a;
1626 ALIGN(ALIGN_SPEC) ge25519 A;
1627 hash_512bits extsk;
1628
1629 /* A = aB */
1630 ed25519_extsk(extsk, secretKey);
1631 expand256_modm(a, extsk, 32);
1632 ge25519_scalarmult_base_niels(&A, ge25519_niels_base_multiples, a);
1633 ge25519_pack(publicKey, &A);
1634
1635 return 0;
1636}
1637
1638int
1639ed25519_publickey(byte publicKey[32], const byte secretKey[32])
1640{
1641 return ed25519_publickey_CXX(publicKey, secretKey);
1642}
1643
1644int
1645ed25519_sign_CXX(std::istream& stream, const byte sk[32], const byte pk[32], byte RS[64])
1646{
1647 using namespace CryptoPP::Donna::Ed25519;
1648
1649 bignum256modm r, S, a;
1650 ALIGN(ALIGN_SPEC) ge25519 R;
1651 hash_512bits extsk, hashr, hram;
1652
1653 // Unfortunately we need to read the stream twice. The first time calculates
1654 // 'r = H(aExt[32..64], m)'. The second time calculates 'S = H(R,A,m)'. There
1655 // is a data dependency due to hashing 'RS' with 'R = [r]B' that does not
1656 // allow us to read the stream once.
1657 std::streampos where = stream.tellg();
1658
1659 ed25519_extsk(extsk, sk);
1660
1661 /* r = H(aExt[32..64], m) */
1662 SHA512 hash;
1663 hash.Update(extsk + 32, 32);
1664 UpdateFromStream(hash, stream);
1665 hash.Final(hashr);
1666 expand256_modm(r, hashr, 64);
1667
1668 /* R = rB */
1669 ge25519_scalarmult_base_niels(&R, ge25519_niels_base_multiples, r);
1670 ge25519_pack(RS, &R);
1671
1672 // Reset stream for the second digest
1673 stream.clear();
1674 stream.seekg(where);
1675
1676 /* S = H(R,A,m).. */
1677 ed25519_hram(hram, RS, pk, stream);
1678 expand256_modm(S, hram, 64);
1679
1680 /* S = H(R,A,m)a */
1681 expand256_modm(a, extsk, 32);
1682 mul256_modm(S, S, a);
1683
1684 /* S = (r + H(R,A,m)a) */
1685 add256_modm(S, S, r);
1686
1687 /* S = (r + H(R,A,m)a) mod L */
1688 contract256_modm(RS + 32, S);
1689 return 0;
1690}
1691
1692int
1693ed25519_sign_CXX(const byte *m, size_t mlen, const byte sk[32], const byte pk[32], byte RS[64])
1694{
1695 using namespace CryptoPP::Donna::Ed25519;
1696
1697 bignum256modm r, S, a;
1698 ALIGN(ALIGN_SPEC) ge25519 R;
1699 hash_512bits extsk, hashr, hram;
1700
1701 ed25519_extsk(extsk, sk);
1702
1703 /* r = H(aExt[32..64], m) */
1704 SHA512 hash;
1705 hash.Update(extsk + 32, 32);
1706 hash.Update(m, mlen);
1707 hash.Final(hashr);
1708 expand256_modm(r, hashr, 64);
1709
1710 /* R = rB */
1711 ge25519_scalarmult_base_niels(&R, ge25519_niels_base_multiples, r);
1712 ge25519_pack(RS, &R);
1713
1714 /* S = H(R,A,m).. */
1715 ed25519_hram(hram, RS, pk, m, mlen);
1716 expand256_modm(S, hram, 64);
1717
1718 /* S = H(R,A,m)a */
1719 expand256_modm(a, extsk, 32);
1720 mul256_modm(S, S, a);
1721
1722 /* S = (r + H(R,A,m)a) */
1723 add256_modm(S, S, r);
1724
1725 /* S = (r + H(R,A,m)a) mod L */
1726 contract256_modm(RS + 32, S);
1727 return 0;
1728}
1729
1730int
1731ed25519_sign(std::istream& stream, const byte secretKey[32], const byte publicKey[32],
1732 byte signature[64])
1733{
1734 return ed25519_sign_CXX(stream, secretKey, publicKey, signature);
1735}
1736
1737int
1738ed25519_sign(const byte* message, size_t messageLength, const byte secretKey[32],
1739 const byte publicKey[32], byte signature[64])
1740{
1741 return ed25519_sign_CXX(message, messageLength, secretKey, publicKey, signature);
1742}
1743
1744int
1745ed25519_sign_open_CXX(const byte *m, size_t mlen, const byte pk[32], const byte RS[64]) {
1746
1747 using namespace CryptoPP::Donna::Ed25519;
1748
1749 ALIGN(ALIGN_SPEC) ge25519 R, A;
1750 hash_512bits hash;
1751 bignum256modm hram, S;
1752 byte checkR[32];
1753
1754 if ((RS[63] & 224) || !ge25519_unpack_negative_vartime(&A, pk))
1755 return -1;
1756
1757 /* hram = H(R,A,m) */
1758 ed25519_hram(hash, RS, pk, m, mlen);
1759 expand256_modm(hram, hash, 64);
1760
1761 /* S */
1762 expand256_modm(S, RS + 32, 32);
1763
1764 /* SB - H(R,A,m)A */
1765 ge25519_double_scalarmult_vartime(&R, &A, hram, S);
1766 ge25519_pack(checkR, &R);
1767
1768 /* check that R = SB - H(R,A,m)A */
1769 return ed25519_verify(RS, checkR, 32) ? 0 : -1;
1770}
1771
1772int
1773ed25519_sign_open_CXX(std::istream& stream, const byte pk[32], const byte RS[64]) {
1774
1775 using namespace CryptoPP::Donna::Ed25519;
1776
1777 ALIGN(ALIGN_SPEC) ge25519 R, A;
1778 hash_512bits hash;
1779 bignum256modm hram, S;
1780 byte checkR[32];
1781
1782 if ((RS[63] & 224) || !ge25519_unpack_negative_vartime(&A, pk))
1783 return -1;
1784
1785 /* hram = H(R,A,m) */
1786 ed25519_hram(hash, RS, pk, stream);
1787 expand256_modm(hram, hash, 64);
1788
1789 /* S */
1790 expand256_modm(S, RS + 32, 32);
1791
1792 /* SB - H(R,A,m)A */
1793 ge25519_double_scalarmult_vartime(&R, &A, hram, S);
1794 ge25519_pack(checkR, &R);
1795
1796 /* check that R = SB - H(R,A,m)A */
1797 return ed25519_verify(RS, checkR, 32) ? 0 : -1;
1798}
1799
1800int
1801ed25519_sign_open(std::istream& stream, const byte publicKey[32], const byte signature[64])
1802{
1803 return ed25519_sign_open_CXX(stream, publicKey, signature);
1804}
1805
1806int
1807ed25519_sign_open(const byte *message, size_t messageLength, const byte publicKey[32], const byte signature[64])
1808{
1809 return ed25519_sign_open_CXX(message, messageLength, publicKey, signature);
1810}
1811
1812NAMESPACE_END // Donna
1813NAMESPACE_END // CryptoPP
1814
1815#endif // CRYPTOPP_CURVE25519_64BIT
FixedSizeSecBlock
Fixed size stack-based SecBlock.
Definition secblock.h:1246
GetBlock
Access a block of memory.
Definition misc.h:2766
HashTransformation
Interface for hash functions and data processing part of MACs.
Definition cryptlib.h:1113
HashTransformation::Update
virtual void Update(const byte *input, size_t length)=0
Updates a hash with additional input.
SHA512
SHA-512 message digest.
Definition sha.h:142
config.h
Library configuration file.
sword32
signed int sword32
32-bit signed datatype
Definition config_int.h:81
word32
unsigned int word32
32-bit unsigned datatype
Definition config_int.h:62
cpu.h
Functions for CPU features and intrinsics.
ed25519_sign_open
int ed25519_sign_open(const byte *message, size_t messageLength, const byte publicKey[32], const byte signature[64])
Verifies a signature on a message.
Definition donna_32.cpp:2088
ed25519_sign
int ed25519_sign(const byte *message, size_t messageLength, const byte secretKey[32], const byte publicKey[32], byte signature[64])
Creates a signature on a message.
Definition donna_32.cpp:2025
ed25519_publickey
int ed25519_publickey(byte publicKey[32], const byte secretKey[32])
Creates a public key from a secret key.
Definition donna_32.cpp:1924
curve25519_mult
int curve25519_mult(byte publicKey[32], const byte secretKey[32])
Generate a public key.
Definition donna_32.cpp:1873
misc.h
Utility functions for the Crypto++ library.
PutWord
void PutWord(bool assumeAligned, ByteOrder order, byte *block, T value, const byte *xorBlock=NULLPTR)
Access a block of memory.
Definition misc.h:2739
pch.h
Precompiled header file.
secblock.h
Classes and functions for secure memory allocations.
sha.h
Classes for SHA-1 and SHA-2 family of message digests.
ge25519_niels
Definition donna_32.h:53
ge25519_p1p1
Definition donna_32.h:49
ge25519_pniels
Definition donna_32.h:57
Generated by doxygen 1.9.8