AtlatestRepositorysigil-crypto

sigil-crypto / tree / vendor / monocypher / srcmonocypher.c

1// Monocypher version 4.0.3
2//
3// This file is dual-licensed. Choose whichever licence you want from
4// the two licences listed below.
5//
6// The first licence is a regular 2-clause BSD licence. The second licence
7// is the CC-0 from Creative Commons. It is intended to release Monocypher
8// to the public domain. The BSD licence serves as a fallback option.
9//
10// SPDX-License-Identifier: BSD-2-Clause OR CC0-1.0
11//
12// ------------------------------------------------------------------------
13//
14// Copyright (c) 2017-2020, Loup Vaillant
15// All rights reserved.
16//
17//
18// Redistribution and use in source and binary forms, with or without
19// modification, are permitted provided that the following conditions are
20// met:
21//
22// 1. Redistributions of source code must retain the above copyright
23// notice, this list of conditions and the following disclaimer.
24//
25// 2. Redistributions in binary form must reproduce the above copyright
26// notice, this list of conditions and the following disclaimer in the
27// documentation and/or other materials provided with the
28// distribution.
29//
30// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
31// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
32// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
33// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
34// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
36// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
37// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
38// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
39// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
40// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
41//
42// ------------------------------------------------------------------------
43//
44// Written in 2017-2020 by Loup Vaillant
45//
46// To the extent possible under law, the author(s) have dedicated all copyright
47// and related neighboring rights to this software to the public domain
48// worldwide. This software is distributed without any warranty.
49//
50// You should have received a copy of the CC0 Public Domain Dedication along
51// with this software. If not, see
52// <https://creativecommons.org/publicdomain/zero/1.0/>
54#include "monocypher.h"
56#ifdef MONOCYPHER_CPP_NAMESPACE
57namespace MONOCYPHER_CPP_NAMESPACE {
58#endif
60/////////////////
61/// Utilities ///
62/////////////////
63#define FOR_T(type, i, start, end) for (type i = (start); i < (end); i++)
64#define FOR(i, start, end) FOR_T(size_t, i, start, end)
65#define COPY(dst, src, size) FOR(_i_, 0, size) (dst)[_i_] = (src)[_i_]
66#define ZERO(buf, size) FOR(_i_, 0, size) (buf)[_i_] = 0
67#define WIPE_CTX(ctx) crypto_wipe(ctx , sizeof(*(ctx)))
68#define WIPE_BUFFER(buffer) crypto_wipe(buffer, sizeof(buffer))
69#define MIN(a, b) ((a) <= (b) ? (a) : (b))
70#define MAX(a, b) ((a) >= (b) ? (a) : (b))
72typedef int8_t i8;
73typedef uint8_t u8;
74typedef int16_t i16;
75typedef uint32_t u32;
76typedef int32_t i32;
77typedef int64_t i64;
78typedef uint64_t u64;
80static const u8 zero[128] = {0};
82// returns the smallest positive integer y such that
83// (x + y) % pow_2 == 0
84// Basically, y is the "gap" missing to align x.
85// Only works when pow_2 is a power of 2.
86// Note: we use ~x+1 instead of -x to avoid compiler warnings
87static size_t gap(size_t x, size_t pow_2)
89 return (~x + 1) & (pow_2 - 1);
92static u32 load24_le(const u8 s[3])
94 return
95 ((u32)s[0] << 0) |
96 ((u32)s[1] << 8) |
97 ((u32)s[2] << 16);
100static u32 load32_le(const u8 s[4])
102 return
103 ((u32)s[0] << 0) |
104 ((u32)s[1] << 8) |
105 ((u32)s[2] << 16) |
106 ((u32)s[3] << 24);
109static u64 load64_le(const u8 s[8])
111 return load32_le(s) | ((u64)load32_le(s+4) << 32);
114static void store32_le(u8 out[4], u32 in)
116 out[0] = (u8)(in );
117 out[1] = (u8)(in >> 8);
118 out[2] = (u8)(in >> 16);
119 out[3] = (u8)(in >> 24);
122static void store64_le(u8 out[8], u64 in)
124 store32_le(out , (u32)(in ));
125 store32_le(out + 4, (u32)(in >> 32));
128static void load32_le_buf (u32 *dst, const u8 *src, size_t size) {
129 FOR(i, 0, size) { dst[i] = load32_le(src + i*4); }
131static void load64_le_buf (u64 *dst, const u8 *src, size_t size) {
132 FOR(i, 0, size) { dst[i] = load64_le(src + i*8); }
134static void store32_le_buf(u8 *dst, const u32 *src, size_t size) {
135 FOR(i, 0, size) { store32_le(dst + i*4, src[i]); }
137static void store64_le_buf(u8 *dst, const u64 *src, size_t size) {
138 FOR(i, 0, size) { store64_le(dst + i*8, src[i]); }
141static u64 rotr64(u64 x, u64 n) { return (x >> n) ^ (x << (64 - n)); }
142static u32 rotl32(u32 x, u32 n) { return (x << n) ^ (x >> (32 - n)); }
144static int neq0(u64 diff)
146 // constant time comparison to zero
147 // return diff != 0 ? -1 : 0
148 u64 half = (diff >> 32) | ((u32)diff); // half < 2^32
149 u64 eq0 = 1 & ((half - 1) >> 32); // half == 0 ? 1 : 0
150 return (int)eq0 - 1; // half == 0 ? 0 : -1
153static u64 x16(const u8 a[16], const u8 b[16])
155 return (load64_le(a + 0) ^ load64_le(b + 0))
156 | (load64_le(a + 8) ^ load64_le(b + 8));
158static u64 x32(const u8 a[32],const u8 b[32]){return x16(a,b)| x16(a+16, b+16);}
159static u64 x64(const u8 a[64],const u8 b[64]){return x32(a,b)| x32(a+32, b+32);}
160int crypto_verify16(const u8 a[16], const u8 b[16]){ return neq0(x16(a, b)); }
161int crypto_verify32(const u8 a[32], const u8 b[32]){ return neq0(x32(a, b)); }
162int crypto_verify64(const u8 a[64], const u8 b[64]){ return neq0(x64(a, b)); }
164void crypto_wipe(void *secret, size_t size)
166 volatile u8 *v_secret = (u8*)secret;
167 ZERO(v_secret, size);
170/////////////////
171/// Chacha 20 ///
172/////////////////
173#define QUARTERROUND(a, b, c, d) \
174 a += b; d = rotl32(d ^ a, 16); \
175 c += d; b = rotl32(b ^ c, 12); \
176 a += b; d = rotl32(d ^ a, 8); \
177 c += d; b = rotl32(b ^ c, 7)
179static void chacha20_rounds(u32 out[16], const u32 in[16])
181 // The temporary variables make Chacha20 10% faster.
182 u32 t0 = in[ 0]; u32 t1 = in[ 1]; u32 t2 = in[ 2]; u32 t3 = in[ 3];
183 u32 t4 = in[ 4]; u32 t5 = in[ 5]; u32 t6 = in[ 6]; u32 t7 = in[ 7];
184 u32 t8 = in[ 8]; u32 t9 = in[ 9]; u32 t10 = in[10]; u32 t11 = in[11];
185 u32 t12 = in[12]; u32 t13 = in[13]; u32 t14 = in[14]; u32 t15 = in[15];
187 FOR (i, 0, 10) { // 20 rounds, 2 rounds per loop.
188 QUARTERROUND(t0, t4, t8 , t12); // column 0
189 QUARTERROUND(t1, t5, t9 , t13); // column 1
190 QUARTERROUND(t2, t6, t10, t14); // column 2
191 QUARTERROUND(t3, t7, t11, t15); // column 3
192 QUARTERROUND(t0, t5, t10, t15); // diagonal 0
193 QUARTERROUND(t1, t6, t11, t12); // diagonal 1
194 QUARTERROUND(t2, t7, t8 , t13); // diagonal 2
195 QUARTERROUND(t3, t4, t9 , t14); // diagonal 3
196 }
197 out[ 0] = t0; out[ 1] = t1; out[ 2] = t2; out[ 3] = t3;
198 out[ 4] = t4; out[ 5] = t5; out[ 6] = t6; out[ 7] = t7;
199 out[ 8] = t8; out[ 9] = t9; out[10] = t10; out[11] = t11;
200 out[12] = t12; out[13] = t13; out[14] = t14; out[15] = t15;
203static const u8 *chacha20_constant = (const u8*)"expand 32-byte k"; // 16 bytes
205void crypto_chacha20_h(u8 out[32], const u8 key[32], const u8 in [16])
207 u32 block[16];
208 load32_le_buf(block , chacha20_constant, 4);
209 load32_le_buf(block + 4, key , 8);
210 load32_le_buf(block + 12, in , 4);
212 chacha20_rounds(block, block);
214 // prevent reversal of the rounds by revealing only half of the buffer.
215 store32_le_buf(out , block , 4); // constant
216 store32_le_buf(out+16, block+12, 4); // counter and nonce
217 WIPE_BUFFER(block);
220u64 crypto_chacha20_djb(u8 *cipher_text, const u8 *plain_text,
221 size_t text_size, const u8 key[32], const u8 nonce[8],
222 u64 ctr)
224 u32 input[16];
225 load32_le_buf(input , chacha20_constant, 4);
226 load32_le_buf(input + 4, key , 8);
227 load32_le_buf(input + 14, nonce , 2);
228 input[12] = (u32) ctr;
229 input[13] = (u32)(ctr >> 32);
231 // Whole blocks
232 u32 pool[16];
233 size_t nb_blocks = text_size >> 6;
234 FOR (i, 0, nb_blocks) {
235 chacha20_rounds(pool, input);
236 if (plain_text != NULL) {
237 FOR (j, 0, 16) {
238 u32 p = pool[j] + input[j];
239 store32_le(cipher_text, p ^ load32_le(plain_text));
240 cipher_text += 4;
241 plain_text += 4;
242 }
243 } else {
244 FOR (j, 0, 16) {
245 u32 p = pool[j] + input[j];
246 store32_le(cipher_text, p);
247 cipher_text += 4;
248 }
249 }
250 input[12]++;
251 if (input[12] == 0) {
252 input[13]++;
253 }
254 }
255 text_size &= 63;
257 // Last (incomplete) block
258 if (text_size > 0) {
259 if (plain_text == NULL) {
260 plain_text = zero;
261 }
262 chacha20_rounds(pool, input);
263 u8 tmp[64];
264 FOR (i, 0, 16) {
265 store32_le(tmp + i*4, pool[i] + input[i]);
266 }
267 FOR (i, 0, text_size) {
268 cipher_text[i] = tmp[i] ^ plain_text[i];
269 }
270 WIPE_BUFFER(tmp);
271 }
272 ctr = input[12] + ((u64)input[13] << 32) + (text_size > 0);
274 WIPE_BUFFER(pool);
275 WIPE_BUFFER(input);
276 return ctr;
279u32 crypto_chacha20_ietf(u8 *cipher_text, const u8 *plain_text,
280 size_t text_size,
281 const u8 key[32], const u8 nonce[12], u32 ctr)
283 u64 big_ctr = ctr + ((u64)load32_le(nonce) << 32);
284 return (u32)crypto_chacha20_djb(cipher_text, plain_text, text_size,
285 key, nonce + 4, big_ctr);
288u64 crypto_chacha20_x(u8 *cipher_text, const u8 *plain_text,
289 size_t text_size,
290 const u8 key[32], const u8 nonce[24], u64 ctr)
292 u8 sub_key[32];
293 crypto_chacha20_h(sub_key, key, nonce);
294 ctr = crypto_chacha20_djb(cipher_text, plain_text, text_size,
295 sub_key, nonce + 16, ctr);
296 WIPE_BUFFER(sub_key);
297 return ctr;
300/////////////////
301/// Poly 1305 ///
302/////////////////
304// h = (h + c) * r
305// preconditions:
306// ctx->h <= 4_ffffffff_ffffffff_ffffffff_ffffffff
307// ctx->r <= 0ffffffc_0ffffffc_0ffffffc_0fffffff
308// end <= 1
309// Postcondition:
310// ctx->h <= 4_ffffffff_ffffffff_ffffffff_ffffffff
311static void poly_blocks(crypto_poly1305_ctx *ctx, const u8 *in,
312 size_t nb_blocks, unsigned end)
314 // Local all the things!
315 const u32 r0 = ctx->r[0];
316 const u32 r1 = ctx->r[1];
317 const u32 r2 = ctx->r[2];
318 const u32 r3 = ctx->r[3];
319 const u32 rr0 = (r0 >> 2) * 5; // lose 2 bits...
320 const u32 rr1 = (r1 >> 2) + r1; // rr1 == (r1 >> 2) * 5
321 const u32 rr2 = (r2 >> 2) + r2; // rr1 == (r2 >> 2) * 5
322 const u32 rr3 = (r3 >> 2) + r3; // rr1 == (r3 >> 2) * 5
323 const u32 rr4 = r0 & 3; // ...recover 2 bits
324 u32 h0 = ctx->h[0];
325 u32 h1 = ctx->h[1];
326 u32 h2 = ctx->h[2];
327 u32 h3 = ctx->h[3];
328 u32 h4 = ctx->h[4];
330 FOR (i, 0, nb_blocks) {
331 // h + c, without carry propagation
332 const u64 s0 = (u64)h0 + load32_le(in); in += 4;
333 const u64 s1 = (u64)h1 + load32_le(in); in += 4;
334 const u64 s2 = (u64)h2 + load32_le(in); in += 4;
335 const u64 s3 = (u64)h3 + load32_le(in); in += 4;
336 const u32 s4 = h4 + end;
338 // (h + c) * r, without carry propagation
339 const u64 x0 = s0*r0+ s1*rr3+ s2*rr2+ s3*rr1+ s4*rr0;
340 const u64 x1 = s0*r1+ s1*r0 + s2*rr3+ s3*rr2+ s4*rr1;
341 const u64 x2 = s0*r2+ s1*r1 + s2*r0 + s3*rr3+ s4*rr2;
342 const u64 x3 = s0*r3+ s1*r2 + s2*r1 + s3*r0 + s4*rr3;
343 const u32 x4 = s4*rr4;
345 // partial reduction modulo 2^130 - 5
346 const u32 u5 = (u32)(x3 >> 32) + x4; // u5 <= 7ffffff5
347 const u64 u0 = (u32)(u5 >> 2) * 5 + (x0 & 0xffffffff);
348 const u64 u1 = (u32)(u0 >> 32) + (x1 & 0xffffffff) + (x0 >> 32);
349 const u64 u2 = (u32)(u1 >> 32) + (x2 & 0xffffffff) + (x1 >> 32);
350 const u64 u3 = (u32)(u2 >> 32) + (x3 & 0xffffffff) + (x2 >> 32);
351 const u32 u4 = (u32)(u3 >> 32) + (u5 & 3); // u4 <= 4
353 // Update the hash
354 h0 = u0 & 0xffffffff;
355 h1 = u1 & 0xffffffff;
356 h2 = u2 & 0xffffffff;
357 h3 = u3 & 0xffffffff;
358 h4 = u4;
359 }
360 ctx->h[0] = h0;
361 ctx->h[1] = h1;
362 ctx->h[2] = h2;
363 ctx->h[3] = h3;
364 ctx->h[4] = h4;
367void crypto_poly1305_init(crypto_poly1305_ctx *ctx, const u8 key[32])
369 ZERO(ctx->h, 5); // Initial hash is zero
370 ctx->c_idx = 0;
371 // load r and pad (r has some of its bits cleared)
372 load32_le_buf(ctx->r , key , 4);
373 load32_le_buf(ctx->pad, key+16, 4);
374 FOR (i, 0, 1) { ctx->r[i] &= 0x0fffffff; }
375 FOR (i, 1, 4) { ctx->r[i] &= 0x0ffffffc; }
378void crypto_poly1305_update(crypto_poly1305_ctx *ctx,
379 const u8 *message, size_t message_size)
381 // Avoid undefined NULL pointer increments with empty messages
382 if (message_size == 0) {
383 return;
384 }
386 // Align ourselves with block boundaries
387 size_t aligned = MIN(gap(ctx->c_idx, 16), message_size);
388 FOR (i, 0, aligned) {
389 ctx->c[ctx->c_idx] = *message;
390 ctx->c_idx++;
391 message++;
392 message_size--;
393 }
395 // If block is complete, process it
396 if (ctx->c_idx == 16) {
397 poly_blocks(ctx, ctx->c, 1, 1);
398 ctx->c_idx = 0;
399 }
401 // Process the message block by block
402 size_t nb_blocks = message_size >> 4;
403 poly_blocks(ctx, message, nb_blocks, 1);
404 message += nb_blocks << 4;
405 message_size &= 15;
407 // remaining bytes (we never complete a block here)
408 FOR (i, 0, message_size) {
409 ctx->c[ctx->c_idx] = message[i];
410 ctx->c_idx++;
411 }
414void crypto_poly1305_final(crypto_poly1305_ctx *ctx, u8 mac[16])
416 // Process the last block (if any)
417 // We move the final 1 according to remaining input length
418 // (this will add less than 2^130 to the last input block)
419 if (ctx->c_idx != 0) {
420 ZERO(ctx->c + ctx->c_idx, 16 - ctx->c_idx);
421 ctx->c[ctx->c_idx] = 1;
422 poly_blocks(ctx, ctx->c, 1, 0);
423 }
425 // check if we should subtract 2^130-5 by performing the
426 // corresponding carry propagation.
427 u64 c = 5;
428 FOR (i, 0, 4) {
429 c += ctx->h[i];
430 c >>= 32;
431 }
432 c += ctx->h[4];
433 c = (c >> 2) * 5; // shift the carry back to the beginning
434 // c now indicates how many times we should subtract 2^130-5 (0 or 1)
435 FOR (i, 0, 4) {
436 c += (u64)ctx->h[i] + ctx->pad[i];
437 store32_le(mac + i*4, (u32)c);
438 c = c >> 32;
439 }
440 WIPE_CTX(ctx);
443void crypto_poly1305(u8 mac[16], const u8 *message,
444 size_t message_size, const u8 key[32])
446 crypto_poly1305_ctx ctx;
447 crypto_poly1305_init (&ctx, key);
448 crypto_poly1305_update(&ctx, message, message_size);
449 crypto_poly1305_final (&ctx, mac);
452////////////////
453/// BLAKE2 b ///
454////////////////
455static const u64 iv[8] = {
456 0x6a09e667f3bcc908, 0xbb67ae8584caa73b,
457 0x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,
458 0x510e527fade682d1, 0x9b05688c2b3e6c1f,
459 0x1f83d9abfb41bd6b, 0x5be0cd19137e2179,
460};
462static void blake2b_compress(crypto_blake2b_ctx *ctx, int is_last_block)
464 static const u8 sigma[12][16] = {
465 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
466 { 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 },
467 { 11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 },
468 { 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 },
469 { 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 },
470 { 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 },
471 { 12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 },
472 { 13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 },
473 { 6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 },
474 { 10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0 },
475 { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },
476 { 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 },
477 };
479 // increment input offset
480 u64 *x = ctx->input_offset;
481 size_t y = ctx->input_idx;
482 x[0] += y;
483 if (x[0] < y) {
484 x[1]++;
485 }
487 // init work vector
488 u64 v0 = ctx->hash[0]; u64 v8 = iv[0];
489 u64 v1 = ctx->hash[1]; u64 v9 = iv[1];
490 u64 v2 = ctx->hash[2]; u64 v10 = iv[2];
491 u64 v3 = ctx->hash[3]; u64 v11 = iv[3];
492 u64 v4 = ctx->hash[4]; u64 v12 = iv[4] ^ ctx->input_offset[0];
493 u64 v5 = ctx->hash[5]; u64 v13 = iv[5] ^ ctx->input_offset[1];
494 u64 v6 = ctx->hash[6]; u64 v14 = iv[6] ^ (u64)~(is_last_block - 1);
495 u64 v7 = ctx->hash[7]; u64 v15 = iv[7];
497 // mangle work vector
498 u64 *input = ctx->input;
499#define BLAKE2_G(a, b, c, d, x, y) \
500 a += b + x; d = rotr64(d ^ a, 32); \
501 c += d; b = rotr64(b ^ c, 24); \
502 a += b + y; d = rotr64(d ^ a, 16); \
503 c += d; b = rotr64(b ^ c, 63)
504#define BLAKE2_ROUND(i) \
505 BLAKE2_G(v0, v4, v8 , v12, input[sigma[i][ 0]], input[sigma[i][ 1]]); \
506 BLAKE2_G(v1, v5, v9 , v13, input[sigma[i][ 2]], input[sigma[i][ 3]]); \
507 BLAKE2_G(v2, v6, v10, v14, input[sigma[i][ 4]], input[sigma[i][ 5]]); \
508 BLAKE2_G(v3, v7, v11, v15, input[sigma[i][ 6]], input[sigma[i][ 7]]); \
509 BLAKE2_G(v0, v5, v10, v15, input[sigma[i][ 8]], input[sigma[i][ 9]]); \
510 BLAKE2_G(v1, v6, v11, v12, input[sigma[i][10]], input[sigma[i][11]]); \
511 BLAKE2_G(v2, v7, v8 , v13, input[sigma[i][12]], input[sigma[i][13]]); \
512 BLAKE2_G(v3, v4, v9 , v14, input[sigma[i][14]], input[sigma[i][15]])
514#ifdef BLAKE2_NO_UNROLLING
515 FOR (i, 0, 12) {
516 BLAKE2_ROUND(i);
517 }
518#else
519 BLAKE2_ROUND(0); BLAKE2_ROUND(1); BLAKE2_ROUND(2); BLAKE2_ROUND(3);
520 BLAKE2_ROUND(4); BLAKE2_ROUND(5); BLAKE2_ROUND(6); BLAKE2_ROUND(7);
521 BLAKE2_ROUND(8); BLAKE2_ROUND(9); BLAKE2_ROUND(10); BLAKE2_ROUND(11);
522#endif
524 // update hash
525 ctx->hash[0] ^= v0 ^ v8; ctx->hash[1] ^= v1 ^ v9;
526 ctx->hash[2] ^= v2 ^ v10; ctx->hash[3] ^= v3 ^ v11;
527 ctx->hash[4] ^= v4 ^ v12; ctx->hash[5] ^= v5 ^ v13;
528 ctx->hash[6] ^= v6 ^ v14; ctx->hash[7] ^= v7 ^ v15;
531void crypto_blake2b_keyed_init(crypto_blake2b_ctx *ctx, size_t hash_size,
532 const u8 *key, size_t key_size)
534 // initial hash
535 COPY(ctx->hash, iv, 8);
536 ctx->hash[0] ^= 0x01010000 ^ (key_size << 8) ^ hash_size;
538 ctx->input_offset[0] = 0; // beginning of the input, no offset
539 ctx->input_offset[1] = 0; // beginning of the input, no offset
540 ctx->hash_size = hash_size;
541 ctx->input_idx = 0;
542 ZERO(ctx->input, 16);
544 // if there is a key, the first block is that key (padded with zeroes)
545 if (key_size > 0) {
546 u8 key_block[128] = {0};
547 COPY(key_block, key, key_size);
548 // same as calling crypto_blake2b_update(ctx, key_block , 128)
549 load64_le_buf(ctx->input, key_block, 16);
550 ctx->input_idx = 128;
551 WIPE_BUFFER(key_block);
552 }
555void crypto_blake2b_init(crypto_blake2b_ctx *ctx, size_t hash_size)
557 crypto_blake2b_keyed_init(ctx, hash_size, 0, 0);
560void crypto_blake2b_update(crypto_blake2b_ctx *ctx,
561 const u8 *message, size_t message_size)
563 // Avoid undefined NULL pointer increments with empty messages
564 if (message_size == 0) {
565 return;
566 }
568 // Align with word boundaries
569 if ((ctx->input_idx & 7) != 0) {
570 size_t nb_bytes = MIN(gap(ctx->input_idx, 8), message_size);
571 size_t word = ctx->input_idx >> 3;
572 size_t byte = ctx->input_idx & 7;
573 FOR (i, 0, nb_bytes) {
574 ctx->input[word] |= (u64)message[i] << ((byte + i) << 3);
575 }
576 ctx->input_idx += nb_bytes;
577 message += nb_bytes;
578 message_size -= nb_bytes;
579 }
581 // Align with block boundaries (faster than byte by byte)
582 if ((ctx->input_idx & 127) != 0) {
583 size_t nb_words = MIN(gap(ctx->input_idx, 128), message_size) >> 3;
584 load64_le_buf(ctx->input + (ctx->input_idx >> 3), message, nb_words);
585 ctx->input_idx += nb_words << 3;
586 message += nb_words << 3;
587 message_size -= nb_words << 3;
588 }
590 // Process block by block
591 size_t nb_blocks = message_size >> 7;
592 FOR (i, 0, nb_blocks) {
593 if (ctx->input_idx == 128) {
594 blake2b_compress(ctx, 0);
595 }
596 load64_le_buf(ctx->input, message, 16);
597 message += 128;
598 ctx->input_idx = 128;
599 }
600 message_size &= 127;
602 if (message_size != 0) {
603 // Compress block & flush input buffer as needed
604 if (ctx->input_idx == 128) {
605 blake2b_compress(ctx, 0);
606 ctx->input_idx = 0;
607 }
608 if (ctx->input_idx == 0) {
609 ZERO(ctx->input, 16);
610 }
611 // Fill remaining words (faster than byte by byte)
612 size_t nb_words = message_size >> 3;
613 load64_le_buf(ctx->input, message, nb_words);
614 ctx->input_idx += nb_words << 3;
615 message += nb_words << 3;
616 message_size -= nb_words << 3;
618 // Fill remaining bytes
619 FOR (i, 0, message_size) {
620 size_t word = ctx->input_idx >> 3;
621 size_t byte = ctx->input_idx & 7;
622 ctx->input[word] |= (u64)message[i] << (byte << 3);
623 ctx->input_idx++;
624 }
625 }
628void crypto_blake2b_final(crypto_blake2b_ctx *ctx, u8 *hash)
630 blake2b_compress(ctx, 1); // compress the last block
631 size_t hash_size = MIN(ctx->hash_size, 64);
632 size_t nb_words = hash_size >> 3;
633 store64_le_buf(hash, ctx->hash, nb_words);
634 FOR (i, nb_words << 3, hash_size) {
635 hash[i] = (ctx->hash[i >> 3] >> (8 * (i & 7))) & 0xff;
636 }
637 WIPE_CTX(ctx);
640void crypto_blake2b_keyed(u8 *hash, size_t hash_size,
641 const u8 *key, size_t key_size,
642 const u8 *message, size_t message_size)
644 crypto_blake2b_ctx ctx;
645 crypto_blake2b_keyed_init(&ctx, hash_size, key, key_size);
646 crypto_blake2b_update (&ctx, message, message_size);
647 crypto_blake2b_final (&ctx, hash);
650void crypto_blake2b(u8 *hash, size_t hash_size, const u8 *msg, size_t msg_size)
652 crypto_blake2b_keyed(hash, hash_size, 0, 0, msg, msg_size);
655//////////////
656/// Argon2 ///
657//////////////
658// references to R, Z, Q etc. come from the spec
660// Argon2 operates on 1024 byte blocks.
661typedef struct { u64 a[128]; } blk;
663// updates a BLAKE2 hash with a 32 bit word, little endian.
664static void blake_update_32(crypto_blake2b_ctx *ctx, u32 input)
666 u8 buf[4];
667 store32_le(buf, input);
668 crypto_blake2b_update(ctx, buf, 4);
669 WIPE_BUFFER(buf);
672static void blake_update_32_buf(crypto_blake2b_ctx *ctx,
673 const u8 *buf, u32 size)
675 blake_update_32(ctx, size);
676 crypto_blake2b_update(ctx, buf, size);
680static void copy_block(blk *o,const blk*in){FOR(i, 0, 128) o->a[i] = in->a[i];}
681static void xor_block(blk *o,const blk*in){FOR(i, 0, 128) o->a[i] ^= in->a[i];}
683// Hash with a virtually unlimited digest size.
684// Doesn't extract more entropy than the base hash function.
685// Mainly used for filling a whole kilobyte block with pseudo-random bytes.
686// (One could use a stream cipher with a seed hash as the key, but
687// this would introduce another dependency —and point of failure.)
688static void extended_hash(u8 *digest, u32 digest_size,
689 const u8 *input , u32 input_size)
691 crypto_blake2b_ctx ctx;
692 crypto_blake2b_init (&ctx, MIN(digest_size, 64));
693 blake_update_32 (&ctx, digest_size);
694 crypto_blake2b_update(&ctx, input, input_size);
695 crypto_blake2b_final (&ctx, digest);
697 if (digest_size > 64) {
698 // the conversion to u64 avoids integer overflow on
699 // ludicrously big hash sizes.
700 u32 r = (u32)(((u64)digest_size + 31) >> 5) - 2;
701 u32 i = 1;
702 u32 in = 0;
703 u32 out = 32;
704 while (i < r) {
705 // Input and output overlap. This is intentional
706 crypto_blake2b(digest + out, 64, digest + in, 64);
707 i += 1;
708 in += 32;
709 out += 32;
710 }
711 crypto_blake2b(digest + out, digest_size - (32 * r), digest + in , 64);
712 }
715#define LSB(x) ((u64)(u32)x)
716#define G(a, b, c, d) \
717 a += b + ((LSB(a) * LSB(b)) << 1); d ^= a; d = rotr64(d, 32); \
718 c += d + ((LSB(c) * LSB(d)) << 1); b ^= c; b = rotr64(b, 24); \
719 a += b + ((LSB(a) * LSB(b)) << 1); d ^= a; d = rotr64(d, 16); \
720 c += d + ((LSB(c) * LSB(d)) << 1); b ^= c; b = rotr64(b, 63)
721#define ROUND(v0, v1, v2, v3, v4, v5, v6, v7, \
722 v8, v9, v10, v11, v12, v13, v14, v15) \
723 G(v0, v4, v8, v12); G(v1, v5, v9, v13); \
724 G(v2, v6, v10, v14); G(v3, v7, v11, v15); \
725 G(v0, v5, v10, v15); G(v1, v6, v11, v12); \
726 G(v2, v7, v8, v13); G(v3, v4, v9, v14)
728// Core of the compression function G. Computes Z from R in place.
729static void g_rounds(blk *b)
731 // column rounds (work_block = Q)
732 for (int i = 0; i < 128; i += 16) {
733 ROUND(b->a[i ], b->a[i+ 1], b->a[i+ 2], b->a[i+ 3],
734 b->a[i+ 4], b->a[i+ 5], b->a[i+ 6], b->a[i+ 7],
735 b->a[i+ 8], b->a[i+ 9], b->a[i+10], b->a[i+11],
736 b->a[i+12], b->a[i+13], b->a[i+14], b->a[i+15]);
737 }
738 // row rounds (b = Z)
739 for (int i = 0; i < 16; i += 2) {
740 ROUND(b->a[i ], b->a[i+ 1], b->a[i+ 16], b->a[i+ 17],
741 b->a[i+32], b->a[i+33], b->a[i+ 48], b->a[i+ 49],
742 b->a[i+64], b->a[i+65], b->a[i+ 80], b->a[i+ 81],
743 b->a[i+96], b->a[i+97], b->a[i+112], b->a[i+113]);
744 }
747const crypto_argon2_extras crypto_argon2_no_extras = { 0, 0, 0, 0 };
749void crypto_argon2(u8 *hash, u32 hash_size, void *work_area,
750 crypto_argon2_config config,
751 crypto_argon2_inputs inputs,
752 crypto_argon2_extras extras)
754 const u32 segment_size = config.nb_blocks / config.nb_lanes / 4;
755 const u32 lane_size = segment_size * 4;
756 const u32 nb_blocks = lane_size * config.nb_lanes; // rounding down
758 // work area seen as blocks (must be suitably aligned)
759 blk *blocks = (blk*)work_area;
760 {
761 u8 initial_hash[72]; // 64 bytes plus 2 words for future hashes
762 crypto_blake2b_ctx ctx;
763 crypto_blake2b_init (&ctx, 64);
764 blake_update_32 (&ctx, config.nb_lanes ); // p: number of "threads"
765 blake_update_32 (&ctx, hash_size);
766 blake_update_32 (&ctx, config.nb_blocks);
767 blake_update_32 (&ctx, config.nb_passes);
768 blake_update_32 (&ctx, 0x13); // v: version number
769 blake_update_32 (&ctx, config.algorithm); // y: Argon2i, Argon2d...
770 blake_update_32_buf (&ctx, inputs.pass, inputs.pass_size);
771 blake_update_32_buf (&ctx, inputs.salt, inputs.salt_size);
772 blake_update_32_buf (&ctx, extras.key, extras.key_size);
773 blake_update_32_buf (&ctx, extras.ad, extras.ad_size);
774 crypto_blake2b_final(&ctx, initial_hash); // fill 64 first bytes only
776 // fill first 2 blocks of each lane
777 u8 hash_area[1024];
778 FOR_T(u32, l, 0, config.nb_lanes) {
779 FOR_T(u32, i, 0, 2) {
780 store32_le(initial_hash + 64, i); // first additional word
781 store32_le(initial_hash + 68, l); // second additional word
782 extended_hash(hash_area, 1024, initial_hash, 72);
783 load64_le_buf(blocks[l * lane_size + i].a, hash_area, 128);
784 }
785 }
787 WIPE_BUFFER(initial_hash);
788 WIPE_BUFFER(hash_area);
789 }
791 // Argon2i and Argon2id start with constant time indexing
792 int constant_time = config.algorithm != CRYPTO_ARGON2_D;
794 // Fill (and re-fill) the rest of the blocks
795 //
796 // Note: even though each segment within the same slice can be
797 // computed in parallel, (one thread per lane), we are computing
798 // them sequentially, because Monocypher doesn't support threads.
799 //
800 // Yet optimal performance (and therefore security) requires one
801 // thread per lane. The only reason Monocypher supports multiple
802 // lanes is compatibility.
803 blk tmp;
804 FOR_T(u32, pass, 0, config.nb_passes) {
805 FOR_T(u32, slice, 0, 4) {
806 // On the first slice of the first pass,
807 // blocks 0 and 1 are already filled, hence pass_offset.
808 u32 pass_offset = pass == 0 && slice == 0 ? 2 : 0;
809 u32 slice_offset = slice * segment_size;
811 // Argon2id switches back to non-constant time indexing
812 // after the first two slices of the first pass
813 if (slice == 2 && config.algorithm == CRYPTO_ARGON2_ID) {
814 constant_time = 0;
815 }
817 // Each iteration of the following loop may be performed in
818 // a separate thread. All segments must be fully completed
819 // before we start filling the next slice.
820 FOR_T(u32, segment, 0, config.nb_lanes) {
821 blk index_block;
822 u32 index_ctr = 1;
823 FOR_T (u32, block, pass_offset, segment_size) {
824 // Current and previous blocks
825 u32 lane_offset = segment * lane_size;
826 blk *segment_start = blocks + lane_offset + slice_offset;
827 blk *current = segment_start + block;
828 blk *previous =
829 block == 0 && slice_offset == 0
830 ? segment_start + lane_size - 1
831 : segment_start + block - 1;
833 u64 index_seed;
834 if (constant_time) {
835 if (block == pass_offset || (block % 128) == 0) {
836 // Fill or refresh deterministic indices block
838 // seed the beginning of the block...
839 ZERO(index_block.a, 128);
840 index_block.a[0] = pass;
841 index_block.a[1] = segment;
842 index_block.a[2] = slice;
843 index_block.a[3] = nb_blocks;
844 index_block.a[4] = config.nb_passes;
845 index_block.a[5] = config.algorithm;
846 index_block.a[6] = index_ctr;
847 index_ctr++;
849 // ... then shuffle it
850 copy_block(&tmp, &index_block);
851 g_rounds (&index_block);
852 xor_block (&index_block, &tmp);
853 copy_block(&tmp, &index_block);
854 g_rounds (&index_block);
855 xor_block (&index_block, &tmp);
856 }
857 index_seed = index_block.a[block % 128];
858 } else {
859 index_seed = previous->a[0];
860 }
862 // Establish the reference set. *Approximately* comprises:
863 // - The last 3 slices (if they exist yet)
864 // - The already constructed blocks in the current segment
865 u32 next_slice = ((slice + 1) % 4) * segment_size;
866 u32 window_start = pass == 0 ? 0 : next_slice;
867 u32 nb_segments = pass == 0 ? slice : 3;
868 u32 lane =
869 pass == 0 && slice == 0
870 ? segment
871 : (u32)(index_seed >> 32) % config.nb_lanes;
872 u32 window_size =
873 nb_segments * segment_size +
874 (lane == segment ? block-1 :
875 block == 0 ? (u32)-1 : 0);
877 // Find reference block
878 u64 j1 = index_seed & 0xffffffff; // block selector
879 u64 x = (j1 * j1) >> 32;
880 u64 y = (window_size * x) >> 32;
881 u64 z = (window_size - 1) - y;
882 u32 ref = (u32)((window_start + z) % lane_size);
883 u32 index = lane * lane_size + ref;
884 blk *reference = blocks + index;
886 // Shuffle the previous & reference block
887 // into the current block
888 copy_block(&tmp, previous);
889 xor_block (&tmp, reference);
890 if (pass == 0) { copy_block(current, &tmp); }
891 else { xor_block (current, &tmp); }
892 g_rounds (&tmp);
893 xor_block (current, &tmp);
894 }
895 }
896 }
897 }
899 // Wipe temporary block
900 volatile u64* p = tmp.a;
901 ZERO(p, 128);
903 // XOR last blocks of each lane
904 blk *last_block = blocks + lane_size - 1;
905 FOR_T (u32, lane, 1, config.nb_lanes) {
906 blk *next_block = last_block + lane_size;
907 xor_block(next_block, last_block);
908 last_block = next_block;
909 }
911 // Serialize last block
912 u8 final_block[1024];
913 store64_le_buf(final_block, last_block->a, 128);
915 // Wipe work area
916 p = (u64*)work_area;
917 ZERO(p, 128 * nb_blocks);
919 // Hash the very last block with H' into the output hash
920 extended_hash(hash, hash_size, final_block, 1024);
921 WIPE_BUFFER(final_block);
924////////////////////////////////////
925/// Arithmetic modulo 2^255 - 19 ///
926////////////////////////////////////
927// Originally taken from SUPERCOP's ref10 implementation.
928// A bit bigger than TweetNaCl, over 4 times faster.
930// field element
931typedef i32 fe[10];
933// field constants
934//
935// fe_one : 1
936// sqrtm1 : sqrt(-1)
937// d : -121665 / 121666
938// D2 : 2 * -121665 / 121666
939// lop_x, lop_y: low order point in Edwards coordinates
940// ufactor : -sqrt(-1) * 2
941// A2 : 486662^2 (A squared)
942static const fe fe_one = {1};
943static const fe sqrtm1 = {
944 -32595792, -7943725, 9377950, 3500415, 12389472,
945 -272473, -25146209, -2005654, 326686, 11406482,
946};
947static const fe d = {
948 -10913610, 13857413, -15372611, 6949391, 114729,
949 -8787816, -6275908, -3247719, -18696448, -12055116,
950};
951static const fe D2 = {
952 -21827239, -5839606, -30745221, 13898782, 229458,
953 15978800, -12551817, -6495438, 29715968, 9444199,
954};
955static const fe lop_x = {
956 21352778, 5345713, 4660180, -8347857, 24143090,
957 14568123, 30185756, -12247770, -33528939, 8345319,
958};
959static const fe lop_y = {
960 -6952922, -1265500, 6862341, -7057498, -4037696,
961 -5447722, 31680899, -15325402, -19365852, 1569102,
962};
963static const fe ufactor = {
964 -1917299, 15887451, -18755900, -7000830, -24778944,
965 544946, -16816446, 4011309, -653372, 10741468,
966};
967static const fe A2 = {
968 12721188, 3529, 0, 0, 0, 0, 0, 0, 0, 0,
969};
971static void fe_0(fe h) { ZERO(h , 10); }
972static void fe_1(fe h) { h[0] = 1; ZERO(h+1, 9); }
974static void fe_copy(fe h,const fe f ){FOR(i,0,10) h[i] = f[i]; }
975static void fe_neg (fe h,const fe f ){FOR(i,0,10) h[i] = -f[i]; }
976static void fe_add (fe h,const fe f,const fe g){FOR(i,0,10) h[i] = f[i] + g[i];}
977static void fe_sub (fe h,const fe f,const fe g){FOR(i,0,10) h[i] = f[i] - g[i];}
979// Some compilers, when inlining fe_cswap() or fe_ccopy(), may introduce
980// a timing leak. It happens when it notices `b` has only 2 possible
981// values, and either replace the arithmetic by a secret dependent
982// branch, or (as has been observed), swap pointers instead of values,
983// which intruduces a secret dependent index.
984//
985// We apply two mitigations here:
986// - Add `volatile` in the mask declaration.
987// - Unroll the copy loop (costs couple hundred bytes of binary code).
988//
989// As of June 2026, those mitigation work when applied separately or
990// together. Applying them both is currently overkill, but may help
991// delay the day compilers grow clever enough to defeat it. (The true
992// fix is in the semantics of the language itself: C currently has no
993// way to specify constant time code).
994//
995// Note (Loup): as of June 2026, the problem has yet to surface in
996// fe_cswap(), but since this is almost the same code as fe_ccopy() I
997// believe it is more prudent to apply the precaution there too.
998static void fe_cswap(fe f, fe g, int b)
1000 volatile i32 mask = -b; // -1 = 0xffffffff
1001 i32 x0 = (f[0] ^ g[0]) & mask; f[0] = f[0] ^ x0; g[0] = g[0] ^ x0;
1002 i32 x1 = (f[1] ^ g[1]) & mask; f[1] = f[1] ^ x1; g[1] = g[1] ^ x1;
1003 i32 x2 = (f[2] ^ g[2]) & mask; f[2] = f[2] ^ x2; g[2] = g[2] ^ x2;
1004 i32 x3 = (f[3] ^ g[3]) & mask; f[3] = f[3] ^ x3; g[3] = g[3] ^ x3;
1005 i32 x4 = (f[4] ^ g[4]) & mask; f[4] = f[4] ^ x4; g[4] = g[4] ^ x4;
1006 i32 x5 = (f[5] ^ g[5]) & mask; f[5] = f[5] ^ x5; g[5] = g[5] ^ x5;
1007 i32 x6 = (f[6] ^ g[6]) & mask; f[6] = f[6] ^ x6; g[6] = g[6] ^ x6;
1008 i32 x7 = (f[7] ^ g[7]) & mask; f[7] = f[7] ^ x7; g[7] = g[7] ^ x7;
1009 i32 x8 = (f[8] ^ g[8]) & mask; f[8] = f[8] ^ x8; g[8] = g[8] ^ x8;
1010 i32 x9 = (f[9] ^ g[9]) & mask; f[9] = f[9] ^ x9; g[9] = g[9] ^ x9;
1013static void fe_ccopy(fe f, const fe g, int b)
1015 volatile i32 mask = -b; // -1 = 0xffffffff
1016 i32 x0 = (f[0] ^ g[0]) & mask; f[0] = f[0] ^ x0;
1017 i32 x1 = (f[1] ^ g[1]) & mask; f[1] = f[1] ^ x1;
1018 i32 x2 = (f[2] ^ g[2]) & mask; f[2] = f[2] ^ x2;
1019 i32 x3 = (f[3] ^ g[3]) & mask; f[3] = f[3] ^ x3;
1020 i32 x4 = (f[4] ^ g[4]) & mask; f[4] = f[4] ^ x4;
1021 i32 x5 = (f[5] ^ g[5]) & mask; f[5] = f[5] ^ x5;
1022 i32 x6 = (f[6] ^ g[6]) & mask; f[6] = f[6] ^ x6;
1023 i32 x7 = (f[7] ^ g[7]) & mask; f[7] = f[7] ^ x7;
1024 i32 x8 = (f[8] ^ g[8]) & mask; f[8] = f[8] ^ x8;
1025 i32 x9 = (f[9] ^ g[9]) & mask; f[9] = f[9] ^ x9;
1029// Signed carry propagation
1030// ------------------------
1032// Let t be a number. It can be uniquely decomposed thus:
1034// t = h*2^26 + l
1035// such that -2^25 <= l < 2^25
1037// Let c = (t + 2^25) / 2^26 (rounded down)
1038// c = (h*2^26 + l + 2^25) / 2^26 (rounded down)
1039// c = h + (l + 2^25) / 2^26 (rounded down)
1040// c = h (exactly)
1041// Because 0 <= l + 2^25 < 2^26
1043// Let u = t - c*2^26
1044// u = h*2^26 + l - h*2^26
1045// u = l
1046// Therefore, -2^25 <= u < 2^25
1048// Additionally, if |t| < x, then |h| < x/2^26 (rounded down)
1050// Notations:
1051// - In C, 1<<25 means 2^25.
1052// - In C, x>>25 means floor(x / (2^25)).
1053// - All of the above applies with 25 & 24 as well as 26 & 25.
1056// Note on negative right shifts
1057// -----------------------------
1059// In C, x >> n, where x is a negative integer, is implementation
1060// defined. In practice, all platforms do arithmetic shift, which is
1061// equivalent to division by 2^26, rounded down. Some compilers, like
1062// GCC, even guarantee it.
1064// If we ever stumble upon a platform that does not propagate the sign
1065// bit (we won't), visible failures will show at the slightest test, and
1066// the signed shifts can be replaced by the following:
1068// typedef struct { i64 x:39; } s25;
1069// typedef struct { i64 x:38; } s26;
1070// i64 shift25(i64 x) { s25 s; s.x = ((u64)x)>>25; return s.x; }
1071// i64 shift26(i64 x) { s26 s; s.x = ((u64)x)>>26; return s.x; }
1073// Current compilers cannot optimise this, causing a 30% drop in
1074// performance. Fairly expensive for something that never happens.
1077// Precondition
1078// ------------
1080// |t0| < 2^63
1081// |t1|..|t9| < 2^62
1083// Algorithm
1084// ---------
1085// c = t0 + 2^25 / 2^26 -- |c| <= 2^36
1086// t0 -= c * 2^26 -- |t0| <= 2^25
1087// t1 += c -- |t1| <= 2^63
1089// c = t4 + 2^25 / 2^26 -- |c| <= 2^36
1090// t4 -= c * 2^26 -- |t4| <= 2^25
1091// t5 += c -- |t5| <= 2^63
1093// c = t1 + 2^24 / 2^25 -- |c| <= 2^38
1094// t1 -= c * 2^25 -- |t1| <= 2^24
1095// t2 += c -- |t2| <= 2^63
1097// c = t5 + 2^24 / 2^25 -- |c| <= 2^38
1098// t5 -= c * 2^25 -- |t5| <= 2^24
1099// t6 += c -- |t6| <= 2^63
1101// c = t2 + 2^25 / 2^26 -- |c| <= 2^37
1102// t2 -= c * 2^26 -- |t2| <= 2^25 < 1.1 * 2^25 (final t2)
1103// t3 += c -- |t3| <= 2^63
1105// c = t6 + 2^25 / 2^26 -- |c| <= 2^37
1106// t6 -= c * 2^26 -- |t6| <= 2^25 < 1.1 * 2^25 (final t6)
1107// t7 += c -- |t7| <= 2^63
1109// c = t3 + 2^24 / 2^25 -- |c| <= 2^38
1110// t3 -= c * 2^25 -- |t3| <= 2^24 < 1.1 * 2^24 (final t3)
1111// t4 += c -- |t4| <= 2^25 + 2^38 < 2^39
1113// c = t7 + 2^24 / 2^25 -- |c| <= 2^38
1114// t7 -= c * 2^25 -- |t7| <= 2^24 < 1.1 * 2^24 (final t7)
1115// t8 += c -- |t8| <= 2^63
1117// c = t4 + 2^25 / 2^26 -- |c| <= 2^13
1118// t4 -= c * 2^26 -- |t4| <= 2^25 < 1.1 * 2^25 (final t4)
1119// t5 += c -- |t5| <= 2^24 + 2^13 < 1.1 * 2^24 (final t5)
1121// c = t8 + 2^25 / 2^26 -- |c| <= 2^37
1122// t8 -= c * 2^26 -- |t8| <= 2^25 < 1.1 * 2^25 (final t8)
1123// t9 += c -- |t9| <= 2^63
1125// c = t9 + 2^24 / 2^25 -- |c| <= 2^38
1126// t9 -= c * 2^25 -- |t9| <= 2^24 < 1.1 * 2^24 (final t9)
1127// t0 += c * 19 -- |t0| <= 2^25 + 2^38*19 < 2^44
1129// c = t0 + 2^25 / 2^26 -- |c| <= 2^18
1130// t0 -= c * 2^26 -- |t0| <= 2^25 < 1.1 * 2^25 (final t0)
1131// t1 += c -- |t1| <= 2^24 + 2^18 < 1.1 * 2^24 (final t1)
1133// Postcondition
1134// -------------
1135// |t0|, |t2|, |t4|, |t6|, |t8| < 1.1 * 2^25
1136// |t1|, |t3|, |t5|, |t7|, |t9| < 1.1 * 2^24
1137#define FE_CARRY \
1138 i64 c; \
1139 c = (t0 + ((i64)1<<25)) >> 26; t0 -= c * ((i64)1 << 26); t1 += c; \
1140 c = (t4 + ((i64)1<<25)) >> 26; t4 -= c * ((i64)1 << 26); t5 += c; \
1141 c = (t1 + ((i64)1<<24)) >> 25; t1 -= c * ((i64)1 << 25); t2 += c; \
1142 c = (t5 + ((i64)1<<24)) >> 25; t5 -= c * ((i64)1 << 25); t6 += c; \
1143 c = (t2 + ((i64)1<<25)) >> 26; t2 -= c * ((i64)1 << 26); t3 += c; \
1144 c = (t6 + ((i64)1<<25)) >> 26; t6 -= c * ((i64)1 << 26); t7 += c; \
1145 c = (t3 + ((i64)1<<24)) >> 25; t3 -= c * ((i64)1 << 25); t4 += c; \
1146 c = (t7 + ((i64)1<<24)) >> 25; t7 -= c * ((i64)1 << 25); t8 += c; \
1147 c = (t4 + ((i64)1<<25)) >> 26; t4 -= c * ((i64)1 << 26); t5 += c; \
1148 c = (t8 + ((i64)1<<25)) >> 26; t8 -= c * ((i64)1 << 26); t9 += c; \
1149 c = (t9 + ((i64)1<<24)) >> 25; t9 -= c * ((i64)1 << 25); t0 += c * 19; \
1150 c = (t0 + ((i64)1<<25)) >> 26; t0 -= c * ((i64)1 << 26); t1 += c; \
1151 h[0]=(i32)t0; h[1]=(i32)t1; h[2]=(i32)t2; h[3]=(i32)t3; h[4]=(i32)t4; \
1152 h[5]=(i32)t5; h[6]=(i32)t6; h[7]=(i32)t7; h[8]=(i32)t8; h[9]=(i32)t9
1154// Decodes a field element from a byte buffer.
1155// mask specifies how many bits we ignore.
1156// Traditionally we ignore 1. It's useful for EdDSA,
1157// which uses that bit to denote the sign of x.
1158// Elligator however uses positive representatives,
1159// which means ignoring 2 bits instead.
1160static void fe_frombytes_mask(fe h, const u8 s[32], unsigned nb_mask)
1162 u32 mask = 0xffffff >> nb_mask;
1163 i64 t0 = load32_le(s); // t0 < 2^32
1164 i64 t1 = load24_le(s + 4) << 6; // t1 < 2^30
1165 i64 t2 = load24_le(s + 7) << 5; // t2 < 2^29
1166 i64 t3 = load24_le(s + 10) << 3; // t3 < 2^27
1167 i64 t4 = load24_le(s + 13) << 2; // t4 < 2^26
1168 i64 t5 = load32_le(s + 16); // t5 < 2^32
1169 i64 t6 = load24_le(s + 20) << 7; // t6 < 2^31
1170 i64 t7 = load24_le(s + 23) << 5; // t7 < 2^29
1171 i64 t8 = load24_le(s + 26) << 4; // t8 < 2^28
1172 i64 t9 = (load24_le(s + 29) & mask) << 2; // t9 < 2^25
1173 FE_CARRY; // Carry precondition OK
1176static void fe_frombytes(fe h, const u8 s[32])
1178 fe_frombytes_mask(h, s, 1);
1182// Precondition
1183// |h[0]|, |h[2]|, |h[4]|, |h[6]|, |h[8]| < 1.1 * 2^25
1184// |h[1]|, |h[3]|, |h[5]|, |h[7]|, |h[9]| < 1.1 * 2^24
1186// Therefore, |h| < 2^255-19
1187// There are two possibilities:
1189// - If h is positive, all we need to do is reduce its individual
1190// limbs down to their tight positive range.
1191// - If h is negative, we also need to add 2^255-19 to it.
1192// Or just remove 19 and chop off any excess bit.
1193static void fe_tobytes(u8 s[32], const fe h)
1195 i32 t[10];
1196 COPY(t, h, 10);
1197 i32 q = (19 * t[9] + (((i32) 1) << 24)) >> 25;
1198 // |t9| < 1.1 * 2^24
1199 // -1.1 * 2^24 < t9 < 1.1 * 2^24
1200 // -21 * 2^24 < 19 * t9 < 21 * 2^24
1201 // -2^29 < 19 * t9 + 2^24 < 2^29
1202 // -2^29 / 2^25 < (19 * t9 + 2^24) / 2^25 < 2^29 / 2^25
1203 // -16 < (19 * t9 + 2^24) / 2^25 < 16
1204 FOR (i, 0, 5) {
1205 q += t[2*i ]; q >>= 26; // q = 0 or -1
1206 q += t[2*i+1]; q >>= 25; // q = 0 or -1
1208 // q = 0 iff h >= 0
1209 // q = -1 iff h < 0
1210 // Adding q * 19 to h reduces h to its proper range.
1211 q *= 19; // Shift carry back to the beginning
1212 FOR (i, 0, 5) {
1213 t[i*2 ] += q; q = t[i*2 ] >> 26; t[i*2 ] -= q * ((i32)1 << 26);
1214 t[i*2+1] += q; q = t[i*2+1] >> 25; t[i*2+1] -= q * ((i32)1 << 25);
1216 // h is now fully reduced, and q represents the excess bit.
1218 store32_le(s + 0, ((u32)t[0] >> 0) | ((u32)t[1] << 26));
1219 store32_le(s + 4, ((u32)t[1] >> 6) | ((u32)t[2] << 19));
1220 store32_le(s + 8, ((u32)t[2] >> 13) | ((u32)t[3] << 13));
1221 store32_le(s + 12, ((u32)t[3] >> 19) | ((u32)t[4] << 6));
1222 store32_le(s + 16, ((u32)t[5] >> 0) | ((u32)t[6] << 25));
1223 store32_le(s + 20, ((u32)t[6] >> 7) | ((u32)t[7] << 19));
1224 store32_le(s + 24, ((u32)t[7] >> 13) | ((u32)t[8] << 12));
1225 store32_le(s + 28, ((u32)t[8] >> 20) | ((u32)t[9] << 6));
1227 WIPE_BUFFER(t);
1230// Precondition
1231// -------------
1232// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^26
1233// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^25
1235// |g0|, |g2|, |g4|, |g6|, |g8| < 1.65 * 2^26
1236// |g1|, |g3|, |g5|, |g7|, |g9| < 1.65 * 2^25
1237static void fe_mul_small(fe h, const fe f, i32 g)
1239 i64 t0 = f[0] * (i64) g; i64 t1 = f[1] * (i64) g;
1240 i64 t2 = f[2] * (i64) g; i64 t3 = f[3] * (i64) g;
1241 i64 t4 = f[4] * (i64) g; i64 t5 = f[5] * (i64) g;
1242 i64 t6 = f[6] * (i64) g; i64 t7 = f[7] * (i64) g;
1243 i64 t8 = f[8] * (i64) g; i64 t9 = f[9] * (i64) g;
1244 // |t0|, |t2|, |t4|, |t6|, |t8| < 1.65 * 2^26 * 2^31 < 2^58
1245 // |t1|, |t3|, |t5|, |t7|, |t9| < 1.65 * 2^25 * 2^31 < 2^57
1247 FE_CARRY; // Carry precondition OK
1250// Precondition
1251// -------------
1252// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^26
1253// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^25
1255// |g0|, |g2|, |g4|, |g6|, |g8| < 1.65 * 2^26
1256// |g1|, |g3|, |g5|, |g7|, |g9| < 1.65 * 2^25
1257static void fe_mul(fe h, const fe f, const fe g)
1259 // Everything is unrolled and put in temporary variables.
1260 // We could roll the loop, but that would make curve25519 twice as slow.
1261 i32 f0 = f[0]; i32 f1 = f[1]; i32 f2 = f[2]; i32 f3 = f[3]; i32 f4 = f[4];
1262 i32 f5 = f[5]; i32 f6 = f[6]; i32 f7 = f[7]; i32 f8 = f[8]; i32 f9 = f[9];
1263 i32 g0 = g[0]; i32 g1 = g[1]; i32 g2 = g[2]; i32 g3 = g[3]; i32 g4 = g[4];
1264 i32 g5 = g[5]; i32 g6 = g[6]; i32 g7 = g[7]; i32 g8 = g[8]; i32 g9 = g[9];
1265 i32 F1 = f1*2; i32 F3 = f3*2; i32 F5 = f5*2; i32 F7 = f7*2; i32 F9 = f9*2;
1266 i32 G1 = g1*19; i32 G2 = g2*19; i32 G3 = g3*19;
1267 i32 G4 = g4*19; i32 G5 = g5*19; i32 G6 = g6*19;
1268 i32 G7 = g7*19; i32 G8 = g8*19; i32 G9 = g9*19;
1269 // |F1|, |F3|, |F5|, |F7|, |F9| < 1.65 * 2^26
1270 // |G0|, |G2|, |G4|, |G6|, |G8| < 2^31
1271 // |G1|, |G3|, |G5|, |G7|, |G9| < 2^30
1273 i64 t0 = f0*(i64)g0 + F1*(i64)G9 + f2*(i64)G8 + F3*(i64)G7 + f4*(i64)G6
1274 + F5*(i64)G5 + f6*(i64)G4 + F7*(i64)G3 + f8*(i64)G2 + F9*(i64)G1;
1275 i64 t1 = f0*(i64)g1 + f1*(i64)g0 + f2*(i64)G9 + f3*(i64)G8 + f4*(i64)G7
1276 + f5*(i64)G6 + f6*(i64)G5 + f7*(i64)G4 + f8*(i64)G3 + f9*(i64)G2;
1277 i64 t2 = f0*(i64)g2 + F1*(i64)g1 + f2*(i64)g0 + F3*(i64)G9 + f4*(i64)G8
1278 + F5*(i64)G7 + f6*(i64)G6 + F7*(i64)G5 + f8*(i64)G4 + F9*(i64)G3;
1279 i64 t3 = f0*(i64)g3 + f1*(i64)g2 + f2*(i64)g1 + f3*(i64)g0 + f4*(i64)G9
1280 + f5*(i64)G8 + f6*(i64)G7 + f7*(i64)G6 + f8*(i64)G5 + f9*(i64)G4;
1281 i64 t4 = f0*(i64)g4 + F1*(i64)g3 + f2*(i64)g2 + F3*(i64)g1 + f4*(i64)g0
1282 + F5*(i64)G9 + f6*(i64)G8 + F7*(i64)G7 + f8*(i64)G6 + F9*(i64)G5;
1283 i64 t5 = f0*(i64)g5 + f1*(i64)g4 + f2*(i64)g3 + f3*(i64)g2 + f4*(i64)g1
1284 + f5*(i64)g0 + f6*(i64)G9 + f7*(i64)G8 + f8*(i64)G7 + f9*(i64)G6;
1285 i64 t6 = f0*(i64)g6 + F1*(i64)g5 + f2*(i64)g4 + F3*(i64)g3 + f4*(i64)g2
1286 + F5*(i64)g1 + f6*(i64)g0 + F7*(i64)G9 + f8*(i64)G8 + F9*(i64)G7;
1287 i64 t7 = f0*(i64)g7 + f1*(i64)g6 + f2*(i64)g5 + f3*(i64)g4 + f4*(i64)g3
1288 + f5*(i64)g2 + f6*(i64)g1 + f7*(i64)g0 + f8*(i64)G9 + f9*(i64)G8;
1289 i64 t8 = f0*(i64)g8 + F1*(i64)g7 + f2*(i64)g6 + F3*(i64)g5 + f4*(i64)g4
1290 + F5*(i64)g3 + f6*(i64)g2 + F7*(i64)g1 + f8*(i64)g0 + F9*(i64)G9;
1291 i64 t9 = f0*(i64)g9 + f1*(i64)g8 + f2*(i64)g7 + f3*(i64)g6 + f4*(i64)g5
1292 + f5*(i64)g4 + f6*(i64)g3 + f7*(i64)g2 + f8*(i64)g1 + f9*(i64)g0;
1293 // t0 < 0.67 * 2^61
1294 // t1 < 0.41 * 2^61
1295 // t2 < 0.52 * 2^61
1296 // t3 < 0.32 * 2^61
1297 // t4 < 0.38 * 2^61
1298 // t5 < 0.22 * 2^61
1299 // t6 < 0.23 * 2^61
1300 // t7 < 0.13 * 2^61
1301 // t8 < 0.09 * 2^61
1302 // t9 < 0.03 * 2^61
1304 FE_CARRY; // Everything below 2^62, Carry precondition OK
1307// Precondition
1308// -------------
1309// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^26
1310// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^25
1312// Note: we could use fe_mul() for this, but this is significantly faster
1313static void fe_sq(fe h, const fe f)
1315 i32 f0 = f[0]; i32 f1 = f[1]; i32 f2 = f[2]; i32 f3 = f[3]; i32 f4 = f[4];
1316 i32 f5 = f[5]; i32 f6 = f[6]; i32 f7 = f[7]; i32 f8 = f[8]; i32 f9 = f[9];
1317 i32 f0_2 = f0*2; i32 f1_2 = f1*2; i32 f2_2 = f2*2; i32 f3_2 = f3*2;
1318 i32 f4_2 = f4*2; i32 f5_2 = f5*2; i32 f6_2 = f6*2; i32 f7_2 = f7*2;
1319 i32 f5_38 = f5*38; i32 f6_19 = f6*19; i32 f7_38 = f7*38;
1320 i32 f8_19 = f8*19; i32 f9_38 = f9*38;
1321 // |f0_2| , |f2_2| , |f4_2| , |f6_2| , |f8_2| < 1.65 * 2^27
1322 // |f1_2| , |f3_2| , |f5_2| , |f7_2| , |f9_2| < 1.65 * 2^26
1323 // |f5_38|, |f6_19|, |f7_38|, |f8_19|, |f9_38| < 2^31
1325 i64 t0 = f0 *(i64)f0 + f1_2*(i64)f9_38 + f2_2*(i64)f8_19
1326 + f3_2*(i64)f7_38 + f4_2*(i64)f6_19 + f5 *(i64)f5_38;
1327 i64 t1 = f0_2*(i64)f1 + f2 *(i64)f9_38 + f3_2*(i64)f8_19
1328 + f4 *(i64)f7_38 + f5_2*(i64)f6_19;
1329 i64 t2 = f0_2*(i64)f2 + f1_2*(i64)f1 + f3_2*(i64)f9_38
1330 + f4_2*(i64)f8_19 + f5_2*(i64)f7_38 + f6 *(i64)f6_19;
1331 i64 t3 = f0_2*(i64)f3 + f1_2*(i64)f2 + f4 *(i64)f9_38
1332 + f5_2*(i64)f8_19 + f6 *(i64)f7_38;
1333 i64 t4 = f0_2*(i64)f4 + f1_2*(i64)f3_2 + f2 *(i64)f2
1334 + f5_2*(i64)f9_38 + f6_2*(i64)f8_19 + f7 *(i64)f7_38;
1335 i64 t5 = f0_2*(i64)f5 + f1_2*(i64)f4 + f2_2*(i64)f3
1336 + f6 *(i64)f9_38 + f7_2*(i64)f8_19;
1337 i64 t6 = f0_2*(i64)f6 + f1_2*(i64)f5_2 + f2_2*(i64)f4
1338 + f3_2*(i64)f3 + f7_2*(i64)f9_38 + f8 *(i64)f8_19;
1339 i64 t7 = f0_2*(i64)f7 + f1_2*(i64)f6 + f2_2*(i64)f5
1340 + f3_2*(i64)f4 + f8 *(i64)f9_38;
1341 i64 t8 = f0_2*(i64)f8 + f1_2*(i64)f7_2 + f2_2*(i64)f6
1342 + f3_2*(i64)f5_2 + f4 *(i64)f4 + f9 *(i64)f9_38;
1343 i64 t9 = f0_2*(i64)f9 + f1_2*(i64)f8 + f2_2*(i64)f7
1344 + f3_2*(i64)f6 + f4 *(i64)f5_2;
1345 // t0 < 0.67 * 2^61
1346 // t1 < 0.41 * 2^61
1347 // t2 < 0.52 * 2^61
1348 // t3 < 0.32 * 2^61
1349 // t4 < 0.38 * 2^61
1350 // t5 < 0.22 * 2^61
1351 // t6 < 0.23 * 2^61
1352 // t7 < 0.13 * 2^61
1353 // t8 < 0.09 * 2^61
1354 // t9 < 0.03 * 2^61
1356 FE_CARRY;
1359// Parity check. Returns 0 if even, 1 if odd
1360static int fe_isodd(const fe f)
1362 u8 s[32];
1363 fe_tobytes(s, f);
1364 u8 isodd = s[0] & 1;
1365 WIPE_BUFFER(s);
1366 return isodd;
1369// Returns 1 if equal, 0 if not equal
1370static int fe_isequal(const fe f, const fe g)
1372 u8 fs[32];
1373 u8 gs[32];
1374 fe_tobytes(fs, f);
1375 fe_tobytes(gs, g);
1376 int isdifferent = crypto_verify32(fs, gs);
1377 WIPE_BUFFER(fs);
1378 WIPE_BUFFER(gs);
1379 return 1 + isdifferent;
1382// Inverse square root.
1383// Returns true if x is a square, false otherwise.
1384// After the call:
1385// isr = sqrt(1/x) if x is a non-zero square.
1386// isr = sqrt(sqrt(-1)/x) if x is not a square.
1387// isr = 0 if x is zero.
1388// We do not guarantee the sign of the square root.
1390// Notes:
1391// Let quartic = x^((p-1)/4)
1393// x^((p-1)/2) = chi(x)
1394// quartic^2 = chi(x)
1395// quartic = sqrt(chi(x))
1396// quartic = 1 or -1 or sqrt(-1) or -sqrt(-1)
1398// Note that x is a square if quartic is 1 or -1
1399// There are 4 cases to consider:
1401// if quartic = 1 (x is a square)
1402// then x^((p-1)/4) = 1
1403// x^((p-5)/4) * x = 1
1404// x^((p-5)/4) = 1/x
1405// x^((p-5)/8) = sqrt(1/x) or -sqrt(1/x)
1407// if quartic = -1 (x is a square)
1408// then x^((p-1)/4) = -1
1409// x^((p-5)/4) * x = -1
1410// x^((p-5)/4) = -1/x
1411// x^((p-5)/8) = sqrt(-1) / sqrt(x)
1412// x^((p-5)/8) * sqrt(-1) = sqrt(-1)^2 / sqrt(x)
1413// x^((p-5)/8) * sqrt(-1) = -1/sqrt(x)
1414// x^((p-5)/8) * sqrt(-1) = -sqrt(1/x) or sqrt(1/x)
1416// if quartic = sqrt(-1) (x is not a square)
1417// then x^((p-1)/4) = sqrt(-1)
1418// x^((p-5)/4) * x = sqrt(-1)
1419// x^((p-5)/4) = sqrt(-1)/x
1420// x^((p-5)/8) = sqrt(sqrt(-1)/x) or -sqrt(sqrt(-1)/x)
1422// Note that the product of two non-squares is always a square:
1423// For any non-squares a and b, chi(a) = -1 and chi(b) = -1.
1424// Since chi(x) = x^((p-1)/2), chi(a)*chi(b) = chi(a*b) = 1.
1425// Therefore a*b is a square.
1427// Since sqrt(-1) and x are both non-squares, their product is a
1428// square, and we can compute their square root.
1430// if quartic = -sqrt(-1) (x is not a square)
1431// then x^((p-1)/4) = -sqrt(-1)
1432// x^((p-5)/4) * x = -sqrt(-1)
1433// x^((p-5)/4) = -sqrt(-1)/x
1434// x^((p-5)/8) = sqrt(-sqrt(-1)/x)
1435// x^((p-5)/8) = sqrt( sqrt(-1)/x) * sqrt(-1)
1436// x^((p-5)/8) * sqrt(-1) = sqrt( sqrt(-1)/x) * sqrt(-1)^2
1437// x^((p-5)/8) * sqrt(-1) = sqrt( sqrt(-1)/x) * -1
1438// x^((p-5)/8) * sqrt(-1) = -sqrt(sqrt(-1)/x) or sqrt(sqrt(-1)/x)
1439static int invsqrt(fe isr, const fe x)
1441 fe t0, t1, t2;
1443 // t0 = x^((p-5)/8)
1444 // Can be achieved with a simple double & add ladder,
1445 // but it would be slower.
1446 fe_sq(t0, x);
1447 fe_sq(t1,t0); fe_sq(t1, t1); fe_mul(t1, x, t1);
1448 fe_mul(t0, t0, t1);
1449 fe_sq(t0, t0); fe_mul(t0, t1, t0);
1450 fe_sq(t1, t0); FOR (i, 1, 5) { fe_sq(t1, t1); } fe_mul(t0, t1, t0);
1451 fe_sq(t1, t0); FOR (i, 1, 10) { fe_sq(t1, t1); } fe_mul(t1, t1, t0);
1452 fe_sq(t2, t1); FOR (i, 1, 20) { fe_sq(t2, t2); } fe_mul(t1, t2, t1);
1453 fe_sq(t1, t1); FOR (i, 1, 10) { fe_sq(t1, t1); } fe_mul(t0, t1, t0);
1454 fe_sq(t1, t0); FOR (i, 1, 50) { fe_sq(t1, t1); } fe_mul(t1, t1, t0);
1455 fe_sq(t2, t1); FOR (i, 1, 100) { fe_sq(t2, t2); } fe_mul(t1, t2, t1);
1456 fe_sq(t1, t1); FOR (i, 1, 50) { fe_sq(t1, t1); } fe_mul(t0, t1, t0);
1457 fe_sq(t0, t0); FOR (i, 1, 2) { fe_sq(t0, t0); } fe_mul(t0, t0, x);
1459 // quartic = x^((p-1)/4)
1460 i32 *quartic = t1;
1461 fe_sq (quartic, t0);
1462 fe_mul(quartic, quartic, x);
1464 i32 *check = t2;
1465 fe_0 (check); int z0 = fe_isequal(x , check);
1466 fe_1 (check); int p1 = fe_isequal(quartic, check);
1467 fe_neg(check, check ); int m1 = fe_isequal(quartic, check);
1468 fe_neg(check, sqrtm1); int ms = fe_isequal(quartic, check);
1470 // if quartic == -1 or sqrt(-1)
1471 // then isr = x^((p-1)/4) * sqrt(-1)
1472 // else isr = x^((p-1)/4)
1473 fe_mul(isr, t0, sqrtm1);
1474 fe_ccopy(isr, t0, 1 - (m1 | ms));
1476 WIPE_BUFFER(t0);
1477 WIPE_BUFFER(t1);
1478 WIPE_BUFFER(t2);
1479 return p1 | m1 | z0;
1482// Inverse in terms of inverse square root.
1483// Requires two additional squarings to get rid of the sign.
1485// 1/x = x * (+invsqrt(x^2))^2
1486// = x * (-invsqrt(x^2))^2
1488// A fully optimised exponentiation by p-1 would save 6 field
1489// multiplications, but it would require more code.
1490static void fe_invert(fe out, const fe x)
1492 fe tmp;
1493 fe_sq(tmp, x);
1494 invsqrt(tmp, tmp);
1495 fe_sq(tmp, tmp);
1496 fe_mul(out, tmp, x);
1497 WIPE_BUFFER(tmp);
1500// trim a scalar for scalar multiplication
1501void crypto_eddsa_trim_scalar(u8 out[32], const u8 in[32])
1503 COPY(out, in, 32);
1504 out[ 0] &= 248;
1505 out[31] &= 127;
1506 out[31] |= 64;
1509// get bit from scalar at position i
1510static int scalar_bit(const u8 s[32], int i)
1512 if (i < 0) { return 0; } // handle -1 for sliding windows
1513 return (s[i>>3] >> (i&7)) & 1;
1516///////////////
1517/// X-25519 /// Taken from SUPERCOP's ref10 implementation.
1518///////////////
1519static void scalarmult(u8 q[32], const u8 scalar[32], const u8 p[32],
1520 int nb_bits)
1522 // computes the scalar product
1523 fe x1;
1524 fe_frombytes(x1, p);
1526 // computes the actual scalar product (the result is in x2 and z2)
1527 fe x2, z2, x3, z3, t0, t1;
1528 // Montgomery ladder
1529 // In projective coordinates, to avoid divisions: x = X / Z
1530 // We don't care about the y coordinate, it's only 1 bit of information
1531 fe_1(x2); fe_0(z2); // "zero" point
1532 fe_copy(x3, x1); fe_1(z3); // "one" point
1533 int swap = 0;
1534 for (int pos = nb_bits-1; pos >= 0; --pos) {
1535 // constant time conditional swap before ladder step
1536 int b = scalar_bit(scalar, pos);
1537 swap ^= b; // xor trick avoids swapping at the end of the loop
1538 fe_cswap(x2, x3, swap);
1539 fe_cswap(z2, z3, swap);
1540 swap = b; // anticipates one last swap after the loop
1542 // Montgomery ladder step: replaces (P2, P3) by (P2*2, P2+P3)
1543 // with differential addition
1544 fe_sub(t0, x3, z3);
1545 fe_sub(t1, x2, z2);
1546 fe_add(x2, x2, z2);
1547 fe_add(z2, x3, z3);
1548 fe_mul(z3, t0, x2);
1549 fe_mul(z2, z2, t1);
1550 fe_sq (t0, t1 );
1551 fe_sq (t1, x2 );
1552 fe_add(x3, z3, z2);
1553 fe_sub(z2, z3, z2);
1554 fe_mul(x2, t1, t0);
1555 fe_sub(t1, t1, t0);
1556 fe_sq (z2, z2 );
1557 fe_mul_small(z3, t1, 121666);
1558 fe_sq (x3, x3 );
1559 fe_add(t0, t0, z3);
1560 fe_mul(z3, x1, z2);
1561 fe_mul(z2, t1, t0);
1563 // last swap is necessary to compensate for the xor trick
1564 // Note: after this swap, P3 == P2 + P1.
1565 fe_cswap(x2, x3, swap);
1566 fe_cswap(z2, z3, swap);
1568 // normalises the coordinates: x == X / Z
1569 fe_invert(z2, z2);
1570 fe_mul(x2, x2, z2);
1571 fe_tobytes(q, x2);
1573 WIPE_BUFFER(x1);
1574 WIPE_BUFFER(x2); WIPE_BUFFER(z2); WIPE_BUFFER(t0);
1575 WIPE_BUFFER(x3); WIPE_BUFFER(z3); WIPE_BUFFER(t1);
1578void crypto_x25519(u8 raw_shared_secret[32],
1579 const u8 your_secret_key [32],
1580 const u8 their_public_key [32])
1582 // restrict the possible scalar values
1583 u8 e[32];
1584 crypto_eddsa_trim_scalar(e, your_secret_key);
1585 scalarmult(raw_shared_secret, e, their_public_key, 255);
1586 WIPE_BUFFER(e);
1589void crypto_x25519_public_key(u8 public_key[32],
1590 const u8 secret_key[32])
1592 static const u8 base_point[32] = {9};
1593 crypto_x25519(public_key, secret_key, base_point);
1596///////////////////////////
1597/// Arithmetic modulo L ///
1598///////////////////////////
1599static const u32 L[8] = {
1600 0x5cf5d3ed, 0x5812631a, 0xa2f79cd6, 0x14def9de,
1601 0x00000000, 0x00000000, 0x00000000, 0x10000000,
1604// p = a*b + p
1605static void multiply(u32 p[16], const u32 a[8], const u32 b[8])
1607 FOR (i, 0, 8) {
1608 u64 carry = 0;
1609 FOR (j, 0, 8) {
1610 carry += p[i+j] + (u64)a[i] * b[j];
1611 p[i+j] = (u32)carry;
1612 carry >>= 32;
1614 p[i+8] = (u32)carry;
1618static int is_above_l(const u32 x[8])
1620 // We work with L directly, in a 2's complement encoding
1621 // (-L == ~L + 1)
1622 u64 carry = 1;
1623 FOR (i, 0, 8) {
1624 carry += (u64)x[i] + (~L[i] & 0xffffffff);
1625 carry >>= 32;
1627 return (int)carry; // carry is either 0 or 1
1630// Final reduction modulo L, by conditionally removing L.
1631// if x < l , then r = x
1632// if l <= x 2*l, then r = x-l
1633// otherwise the result will be wrong
1634static void remove_l(u32 r[8], const u32 x[8])
1636 u64 carry = (u64)is_above_l(x);
1637 u32 mask = ~(u32)carry + 1; // carry == 0 or 1
1638 FOR (i, 0, 8) {
1639 carry += (u64)x[i] + (~L[i] & mask);
1640 r[i] = (u32)carry;
1641 carry >>= 32;
1645// Full reduction modulo L (Barrett reduction)
1646static void mod_l(u8 reduced[32], const u32 x[16])
1648 static const u32 r[9] = {
1649 0x0a2c131b,0xed9ce5a3,0x086329a7,0x2106215d,
1650 0xffffffeb,0xffffffff,0xffffffff,0xffffffff,0xf,
1651 };
1652 // xr = x * r
1653 u32 xr[25] = {0};
1654 FOR (i, 0, 9) {
1655 u64 carry = 0;
1656 FOR (j, 0, 16) {
1657 carry += xr[i+j] + (u64)r[i] * x[j];
1658 xr[i+j] = (u32)carry;
1659 carry >>= 32;
1661 xr[i+16] = (u32)carry;
1663 // xr = floor(xr / 2^512) * L
1664 // Since the result is guaranteed to be below 2*L,
1665 // it is enough to only compute the first 256 bits.
1666 // The division is performed by saying xr[i+16]. (16 * 32 = 512)
1667 ZERO(xr, 8);
1668 FOR (i, 0, 8) {
1669 u64 carry = 0;
1670 FOR (j, 0, 8-i) {
1671 carry += xr[i+j] + (u64)xr[i+16] * L[j];
1672 xr[i+j] = (u32)carry;
1673 carry >>= 32;
1676 // xr = x - xr
1677 u64 carry = 1;
1678 FOR (i, 0, 8) {
1679 carry += (u64)x[i] + (~xr[i] & 0xffffffff);
1680 xr[i] = (u32)carry;
1681 carry >>= 32;
1683 // Final reduction modulo L (conditional subtraction)
1684 remove_l(xr, xr);
1685 store32_le_buf(reduced, xr, 8);
1687 WIPE_BUFFER(xr);
1690void crypto_eddsa_reduce(u8 reduced[32], const u8 expanded[64])
1692 u32 x[16];
1693 load32_le_buf(x, expanded, 16);
1694 mod_l(reduced, x);
1695 WIPE_BUFFER(x);
1698// r = (a * b) + c
1699void crypto_eddsa_mul_add(u8 r[32],
1700 const u8 a[32], const u8 b[32], const u8 c[32])
1702 u32 A[8]; load32_le_buf(A, a, 8);
1703 u32 B[8]; load32_le_buf(B, b, 8);
1704 u32 p[16]; load32_le_buf(p, c, 8); ZERO(p + 8, 8);
1705 multiply(p, A, B);
1706 mod_l(r, p);
1707 WIPE_BUFFER(p);
1708 WIPE_BUFFER(A);
1709 WIPE_BUFFER(B);
1712///////////////
1713/// Ed25519 ///
1714///////////////
1716// Point (group element, ge) in a twisted Edwards curve,
1717// in extended projective coordinates.
1718// ge : x = X/Z, y = Y/Z, T = XY/Z
1719// ge_cached : Yp = X+Y, Ym = X-Y, T2 = T*D2
1720// ge_precomp: Z = 1
1721typedef struct { fe X; fe Y; fe Z; fe T; } ge;
1722typedef struct { fe Yp; fe Ym; fe Z; fe T2; } ge_cached;
1723typedef struct { fe Yp; fe Ym; fe T2; } ge_precomp;
1725static void ge_zero(ge *p)
1727 fe_0(p->X);
1728 fe_1(p->Y);
1729 fe_1(p->Z);
1730 fe_0(p->T);
1733static void ge_tobytes(u8 s[32], const ge *h)
1735 fe recip, x, y;
1736 fe_invert(recip, h->Z);
1737 fe_mul(x, h->X, recip);
1738 fe_mul(y, h->Y, recip);
1739 fe_tobytes(s, y);
1740 s[31] ^= (u8)fe_isodd(x) << 7;
1742 WIPE_BUFFER(recip);
1743 WIPE_BUFFER(x);
1744 WIPE_BUFFER(y);
1747// h = -s, where s is a point encoded in 32 bytes
1749// Variable time! Inputs must not be secret!
1750// => Use only to *check* signatures.
1752// From the specifications:
1753// The encoding of s contains y and the sign of x
1754// x = sqrt((y^2 - 1) / (d*y^2 + 1))
1755// In extended coordinates:
1756// X = x, Y = y, Z = 1, T = x*y
1758// Note that num * den is a square iff num / den is a square
1759// If num * den is not a square, the point was not on the curve.
1760// From the above:
1761// Let num = y^2 - 1
1762// Let den = d*y^2 + 1
1763// x = sqrt((y^2 - 1) / (d*y^2 + 1))
1764// x = sqrt(num / den)
1765// x = sqrt(num^2 / (num * den))
1766// x = num * sqrt(1 / (num * den))
1768// Therefore, we can just compute:
1769// num = y^2 - 1
1770// den = d*y^2 + 1
1771// isr = invsqrt(num * den) // abort if not square
1772// x = num * isr
1773// Finally, negate x if its sign is not as specified.
1774static int ge_frombytes_neg_vartime(ge *h, const u8 s[32])
1776 fe_frombytes(h->Y, s);
1777 fe_1(h->Z);
1778 fe_sq (h->T, h->Y); // t = y^2
1779 fe_mul(h->X, h->T, d ); // x = d*y^2
1780 fe_sub(h->T, h->T, h->Z); // t = y^2 - 1
1781 fe_add(h->X, h->X, h->Z); // x = d*y^2 + 1
1782 fe_mul(h->X, h->T, h->X); // x = (y^2 - 1) * (d*y^2 + 1)
1783 int is_square = invsqrt(h->X, h->X);
1784 if (!is_square) {
1785 return -1; // Not on the curve, abort
1787 fe_mul(h->X, h->T, h->X); // x = sqrt((y^2 - 1) / (d*y^2 + 1))
1788 if (fe_isodd(h->X) == (s[31] >> 7)) {
1789 fe_neg(h->X, h->X);
1791 fe_mul(h->T, h->X, h->Y);
1792 return 0;
1795static void ge_cache(ge_cached *c, const ge *p)
1797 fe_add (c->Yp, p->Y, p->X);
1798 fe_sub (c->Ym, p->Y, p->X);
1799 fe_copy(c->Z , p->Z );
1800 fe_mul (c->T2, p->T, D2 );
1803// Internal buffers are not wiped! Inputs must not be secret!
1804// => Use only to *check* signatures.
1805static void ge_add(ge *s, const ge *p, const ge_cached *q)
1807 fe a, b;
1808 fe_add(a , p->Y, p->X );
1809 fe_sub(b , p->Y, p->X );
1810 fe_mul(a , a , q->Yp);
1811 fe_mul(b , b , q->Ym);
1812 fe_add(s->Y, a , b );
1813 fe_sub(s->X, a , b );
1815 fe_add(s->Z, p->Z, p->Z );
1816 fe_mul(s->Z, s->Z, q->Z );
1817 fe_mul(s->T, p->T, q->T2);
1818 fe_add(a , s->Z, s->T );
1819 fe_sub(b , s->Z, s->T );
1821 fe_mul(s->T, s->X, s->Y);
1822 fe_mul(s->X, s->X, b );
1823 fe_mul(s->Y, s->Y, a );
1824 fe_mul(s->Z, a , b );
1827// Internal buffers are not wiped! Inputs must not be secret!
1828// => Use only to *check* signatures.
1829static void ge_sub(ge *s, const ge *p, const ge_cached *q)
1831 ge_cached neg;
1832 fe_copy(neg.Ym, q->Yp);
1833 fe_copy(neg.Yp, q->Ym);
1834 fe_copy(neg.Z , q->Z );
1835 fe_neg (neg.T2, q->T2);
1836 ge_add(s, p, &neg);
1839static void ge_madd(ge *s, const ge *p, const ge_precomp *q, fe a, fe b)
1841 fe_add(a , p->Y, p->X );
1842 fe_sub(b , p->Y, p->X );
1843 fe_mul(a , a , q->Yp);
1844 fe_mul(b , b , q->Ym);
1845 fe_add(s->Y, a , b );
1846 fe_sub(s->X, a , b );
1848 fe_add(s->Z, p->Z, p->Z );
1849 fe_mul(s->T, p->T, q->T2);
1850 fe_add(a , s->Z, s->T );
1851 fe_sub(b , s->Z, s->T );
1853 fe_mul(s->T, s->X, s->Y);
1854 fe_mul(s->X, s->X, b );
1855 fe_mul(s->Y, s->Y, a );
1856 fe_mul(s->Z, a , b );
1859// Internal buffers are not wiped! Inputs must not be secret!
1860// => Use only to *check* signatures.
1861static void ge_msub(ge *s, const ge *p, const ge_precomp *q, fe a, fe b)
1863 ge_precomp neg;
1864 fe_copy(neg.Ym, q->Yp);
1865 fe_copy(neg.Yp, q->Ym);
1866 fe_neg (neg.T2, q->T2);
1867 ge_madd(s, p, &neg, a, b);
1870static void ge_double(ge *s, const ge *p, ge *q)
1872 fe_sq (q->X, p->X);
1873 fe_sq (q->Y, p->Y);
1874 fe_sq (q->Z, p->Z); // qZ = pZ^2
1875 fe_mul_small(q->Z, q->Z, 2); // qZ = pZ^2 * 2
1876 fe_add(q->T, p->X, p->Y);
1877 fe_sq (s->T, q->T);
1878 fe_add(q->T, q->Y, q->X);
1879 fe_sub(q->Y, q->Y, q->X);
1880 fe_sub(q->X, s->T, q->T);
1881 fe_sub(q->Z, q->Z, q->Y);
1883 fe_mul(s->X, q->X , q->Z);
1884 fe_mul(s->Y, q->T , q->Y);
1885 fe_mul(s->Z, q->Y , q->Z);
1886 fe_mul(s->T, q->X , q->T);
1889// 5-bit signed window in cached format (Niels coordinates, Z=1)
1890static const ge_precomp b_window[8] = {
1891 {{25967493,-14356035,29566456,3660896,-12694345,
1892 4014787,27544626,-11754271,-6079156,2047605,},
1893 {-12545711,934262,-2722910,3049990,-727428,
1894 9406986,12720692,5043384,19500929,-15469378,},
1895 {-8738181,4489570,9688441,-14785194,10184609,
1896 -12363380,29287919,11864899,-24514362,-4438546,},},
1897 {{15636291,-9688557,24204773,-7912398,616977,
1898 -16685262,27787600,-14772189,28944400,-1550024,},
1899 {16568933,4717097,-11556148,-1102322,15682896,
1900 -11807043,16354577,-11775962,7689662,11199574,},
1901 {30464156,-5976125,-11779434,-15670865,23220365,
1902 15915852,7512774,10017326,-17749093,-9920357,},},
1903 {{10861363,11473154,27284546,1981175,-30064349,
1904 12577861,32867885,14515107,-15438304,10819380,},
1905 {4708026,6336745,20377586,9066809,-11272109,
1906 6594696,-25653668,12483688,-12668491,5581306,},
1907 {19563160,16186464,-29386857,4097519,10237984,
1908 -4348115,28542350,13850243,-23678021,-15815942,},},
1909 {{5153746,9909285,1723747,-2777874,30523605,
1910 5516873,19480852,5230134,-23952439,-15175766,},
1911 {-30269007,-3463509,7665486,10083793,28475525,
1912 1649722,20654025,16520125,30598449,7715701,},
1913 {28881845,14381568,9657904,3680757,-20181635,
1914 7843316,-31400660,1370708,29794553,-1409300,},},
1915 {{-22518993,-6692182,14201702,-8745502,-23510406,
1916 8844726,18474211,-1361450,-13062696,13821877,},
1917 {-6455177,-7839871,3374702,-4740862,-27098617,
1918 -10571707,31655028,-7212327,18853322,-14220951,},
1919 {4566830,-12963868,-28974889,-12240689,-7602672,
1920 -2830569,-8514358,-10431137,2207753,-3209784,},},
1921 {{-25154831,-4185821,29681144,7868801,-6854661,
1922 -9423865,-12437364,-663000,-31111463,-16132436,},
1923 {25576264,-2703214,7349804,-11814844,16472782,
1924 9300885,3844789,15725684,171356,6466918,},
1925 {23103977,13316479,9739013,-16149481,817875,
1926 -15038942,8965339,-14088058,-30714912,16193877,},},
1927 {{-33521811,3180713,-2394130,14003687,-16903474,
1928 -16270840,17238398,4729455,-18074513,9256800,},
1929 {-25182317,-4174131,32336398,5036987,-21236817,
1930 11360617,22616405,9761698,-19827198,630305,},
1931 {-13720693,2639453,-24237460,-7406481,9494427,
1932 -5774029,-6554551,-15960994,-2449256,-14291300,},},
1933 {{-3151181,-5046075,9282714,6866145,-31907062,
1934 -863023,-18940575,15033784,25105118,-7894876,},
1935 {-24326370,15950226,-31801215,-14592823,-11662737,
1936 -5090925,1573892,-2625887,2198790,-15804619,},
1937 {-3099351,10324967,-2241613,7453183,-5446979,
1938 -2735503,-13812022,-16236442,-32461234,-12290683,},},
1941// Incremental sliding windows (left to right)
1942// Based on Roberto Maria Avanzi[2005]
1943typedef struct {
1944 i16 next_index; // position of the next signed digit
1945 i8 next_digit; // next signed digit (odd number below 2^window_width)
1946 u8 next_check; // point at which we must check for a new window
1947} slide_ctx;
1949static void slide_init(slide_ctx *ctx, const u8 scalar[32])
1951 // scalar is guaranteed to be below L, either because we checked (s),
1952 // or because we reduced it modulo L (h_ram). L is under 2^253, so
1953 // so bits 253 to 255 are guaranteed to be zero. No need to test them.
1954 //
1955 // Note however that L is very close to 2^252, so bit 252 is almost
1956 // always zero. If we were to start at bit 251, the tests wouldn't
1957 // catch the off-by-one error (constructing one that does would be
1958 // prohibitively expensive).
1959 //
1960 // We should still check bit 252, though.
1961 int i = 252;
1962 while (i > 0 && scalar_bit(scalar, i) == 0) {
1963 i--;
1965 ctx->next_check = (u8)(i + 1);
1966 ctx->next_index = -1;
1967 ctx->next_digit = -1;
1970static int slide_step(slide_ctx *ctx, int width, int i, const u8 scalar[32])
1972 if (i == ctx->next_check) {
1973 if (scalar_bit(scalar, i) == scalar_bit(scalar, i - 1)) {
1974 ctx->next_check--;
1975 } else {
1976 // compute digit of next window
1977 int w = MIN(width, i + 1);
1978 int v = -(scalar_bit(scalar, i) << (w-1));
1979 FOR_T (int, j, 0, w-1) {
1980 v += scalar_bit(scalar, i-(w-1)+j) << j;
1982 v += scalar_bit(scalar, i-w);
1983 int lsb = v & (~v + 1); // smallest bit of v
1984 int s = // log2(lsb)
1985 (((lsb & 0xAA) != 0) << 0) |
1986 (((lsb & 0xCC) != 0) << 1) |
1987 (((lsb & 0xF0) != 0) << 2);
1988 ctx->next_index = (i16)(i-(w-1)+s);
1989 ctx->next_digit = (i8) (v >> s );
1990 ctx->next_check -= (u8) w;
1993 return i == ctx->next_index ? ctx->next_digit: 0;
1996#define P_W_WIDTH 3 // Affects the size of the stack
1997#define B_W_WIDTH 5 // Affects the size of the binary
1998#define P_W_SIZE (1<<(P_W_WIDTH-2))
2000int crypto_eddsa_check_equation(const u8 signature[64], const u8 public_key[32],
2001 const u8 h[32])
2003 ge minus_A; // -public_key
2004 ge minus_R; // -first_half_of_signature
2005 const u8 *s = signature + 32;
2007 // Check that A and R are on the curve
2008 // Check that 0 <= S < L (prevents malleability)
2009 // *Allow* non-cannonical encoding for A and R
2011 u32 s32[8];
2012 load32_le_buf(s32, s, 8);
2013 if (ge_frombytes_neg_vartime(&minus_A, public_key) ||
2014 ge_frombytes_neg_vartime(&minus_R, signature) ||
2015 is_above_l(s32)) {
2016 return -1;
2020 // look-up table for minus_A
2021 ge_cached lutA[P_W_SIZE];
2023 ge minus_A2, tmp;
2024 ge_double(&minus_A2, &minus_A, &tmp);
2025 ge_cache(&lutA[0], &minus_A);
2026 FOR (i, 1, P_W_SIZE) {
2027 ge_add(&tmp, &minus_A2, &lutA[i-1]);
2028 ge_cache(&lutA[i], &tmp);
2032 // sum = [s]B - [h]A
2033 // Merged double and add ladder, fused with sliding
2034 slide_ctx h_slide; slide_init(&h_slide, h);
2035 slide_ctx s_slide; slide_init(&s_slide, s);
2036 int i = MAX(h_slide.next_check, s_slide.next_check);
2037 ge *sum = &minus_A; // reuse minus_A for the sum
2038 ge_zero(sum);
2039 while (i >= 0) {
2040 ge tmp;
2041 ge_double(sum, sum, &tmp);
2042 int h_digit = slide_step(&h_slide, P_W_WIDTH, i, h);
2043 int s_digit = slide_step(&s_slide, B_W_WIDTH, i, s);
2044 if (h_digit > 0) { ge_add(sum, sum, &lutA[ h_digit / 2]); }
2045 if (h_digit < 0) { ge_sub(sum, sum, &lutA[-h_digit / 2]); }
2046 fe t1, t2;
2047 if (s_digit > 0) { ge_madd(sum, sum, b_window + s_digit/2, t1, t2); }
2048 if (s_digit < 0) { ge_msub(sum, sum, b_window + -s_digit/2, t1, t2); }
2049 i--;
2052 // Compare [8](sum-R) and the zero point
2053 // The multiplication by 8 eliminates any low-order component
2054 // and ensures consistency with batched verification.
2055 ge_cached cached;
2056 u8 check[32];
2057 static const u8 zero_point[32] = {1}; // Point of order 1
2058 ge_cache(&cached, &minus_R);
2059 ge_add(sum, sum, &cached);
2060 ge_double(sum, sum, &minus_R); // reuse minus_R as temporary
2061 ge_double(sum, sum, &minus_R); // reuse minus_R as temporary
2062 ge_double(sum, sum, &minus_R); // reuse minus_R as temporary
2063 ge_tobytes(check, sum);
2064 return crypto_verify32(check, zero_point);
2067// 5-bit signed comb in cached format (Niels coordinates, Z=1)
2068static const ge_precomp b_comb_low[8] = {
2069 {{-6816601,-2324159,-22559413,124364,18015490,
2070 8373481,19993724,1979872,-18549925,9085059,},
2071 {10306321,403248,14839893,9633706,8463310,
2072 -8354981,-14305673,14668847,26301366,2818560,},
2073 {-22701500,-3210264,-13831292,-2927732,-16326337,
2074 -14016360,12940910,177905,12165515,-2397893,},},
2075 {{-12282262,-7022066,9920413,-3064358,-32147467,
2076 2927790,22392436,-14852487,2719975,16402117,},
2077 {-7236961,-4729776,2685954,-6525055,-24242706,
2078 -15940211,-6238521,14082855,10047669,12228189,},
2079 {-30495588,-12893761,-11161261,3539405,-11502464,
2080 16491580,-27286798,-15030530,-7272871,-15934455,},},
2081 {{17650926,582297,-860412,-187745,-12072900,
2082 -10683391,-20352381,15557840,-31072141,-5019061,},
2083 {-6283632,-2259834,-4674247,-4598977,-4089240,
2084 12435688,-31278303,1060251,6256175,10480726,},
2085 {-13871026,2026300,-21928428,-2741605,-2406664,
2086 -8034988,7355518,15733500,-23379862,7489131,},},
2087 {{6883359,695140,23196907,9644202,-33430614,
2088 11354760,-20134606,6388313,-8263585,-8491918,},
2089 {-7716174,-13605463,-13646110,14757414,-19430591,
2090 -14967316,10359532,-11059670,-21935259,12082603,},
2091 {-11253345,-15943946,10046784,5414629,24840771,
2092 8086951,-6694742,9868723,15842692,-16224787,},},
2093 {{9639399,11810955,-24007778,-9320054,3912937,
2094 -9856959,996125,-8727907,-8919186,-14097242,},
2095 {7248867,14468564,25228636,-8795035,14346339,
2096 8224790,6388427,-7181107,6468218,-8720783,},
2097 {15513115,15439095,7342322,-10157390,18005294,
2098 -7265713,2186239,4884640,10826567,7135781,},},
2099 {{-14204238,5297536,-5862318,-6004934,28095835,
2100 4236101,-14203318,1958636,-16816875,3837147,},
2101 {-5511166,-13176782,-29588215,12339465,15325758,
2102 -15945770,-8813185,11075932,-19608050,-3776283,},
2103 {11728032,9603156,-4637821,-5304487,-7827751,
2104 2724948,31236191,-16760175,-7268616,14799772,},},
2105 {{-28842672,4840636,-12047946,-9101456,-1445464,
2106 381905,-30977094,-16523389,1290540,12798615,},
2107 {27246947,-10320914,14792098,-14518944,5302070,
2108 -8746152,-3403974,-4149637,-27061213,10749585,},
2109 {25572375,-6270368,-15353037,16037944,1146292,
2110 32198,23487090,9585613,24714571,-1418265,},},
2111 {{19844825,282124,-17583147,11004019,-32004269,
2112 -2716035,6105106,-1711007,-21010044,14338445,},
2113 {8027505,8191102,-18504907,-12335737,25173494,
2114 -5923905,15446145,7483684,-30440441,10009108,},
2115 {-14134701,-4174411,10246585,-14677495,33553567,
2116 -14012935,23366126,15080531,-7969992,7663473,},},
2119static const ge_precomp b_comb_high[8] = {
2120 {{33055887,-4431773,-521787,6654165,951411,
2121 -6266464,-5158124,6995613,-5397442,-6985227,},
2122 {4014062,6967095,-11977872,3960002,8001989,
2123 5130302,-2154812,-1899602,-31954493,-16173976,},
2124 {16271757,-9212948,23792794,731486,-25808309,
2125 -3546396,6964344,-4767590,10976593,10050757,},},
2126 {{2533007,-4288439,-24467768,-12387405,-13450051,
2127 14542280,12876301,13893535,15067764,8594792,},
2128 {20073501,-11623621,3165391,-13119866,13188608,
2129 -11540496,-10751437,-13482671,29588810,2197295,},
2130 {-1084082,11831693,6031797,14062724,14748428,
2131 -8159962,-20721760,11742548,31368706,13161200,},},
2132 {{2050412,-6457589,15321215,5273360,25484180,
2133 124590,-18187548,-7097255,-6691621,-14604792,},
2134 {9938196,2162889,-6158074,-1711248,4278932,
2135 -2598531,-22865792,-7168500,-24323168,11746309,},
2136 {-22691768,-14268164,5965485,9383325,20443693,
2137 5854192,28250679,-1381811,-10837134,13717818,},},
2138 {{-8495530,16382250,9548884,-4971523,-4491811,
2139 -3902147,6182256,-12832479,26628081,10395408,},
2140 {27329048,-15853735,7715764,8717446,-9215518,
2141 -14633480,28982250,-5668414,4227628,242148,},
2142 {-13279943,-7986904,-7100016,8764468,-27276630,
2143 3096719,29678419,-9141299,3906709,11265498,},},
2144 {{11918285,15686328,-17757323,-11217300,-27548967,
2145 4853165,-27168827,6807359,6871949,-1075745,},
2146 {-29002610,13984323,-27111812,-2713442,28107359,
2147 -13266203,6155126,15104658,3538727,-7513788,},
2148 {14103158,11233913,-33165269,9279850,31014152,
2149 4335090,-1827936,4590951,13960841,12787712,},},
2150 {{1469134,-16738009,33411928,13942824,8092558,
2151 -8778224,-11165065,1437842,22521552,-2792954,},
2152 {31352705,-4807352,-25327300,3962447,12541566,
2153 -9399651,-27425693,7964818,-23829869,5541287,},
2154 {-25732021,-6864887,23848984,3039395,-9147354,
2155 6022816,-27421653,10590137,25309915,-1584678,},},
2156 {{-22951376,5048948,31139401,-190316,-19542447,
2157 -626310,-17486305,-16511925,-18851313,-12985140,},
2158 {-9684890,14681754,30487568,7717771,-10829709,
2159 9630497,30290549,-10531496,-27798994,-13812825,},
2160 {5827835,16097107,-24501327,12094619,7413972,
2161 11447087,28057551,-1793987,-14056981,4359312,},},
2162 {{26323183,2342588,-21887793,-1623758,-6062284,
2163 2107090,-28724907,9036464,-19618351,-13055189,},
2164 {-29697200,14829398,-4596333,14220089,-30022969,
2165 2955645,12094100,-13693652,-5941445,7047569,},
2166 {-3201977,14413268,-12058324,-16417589,-9035655,
2167 -7224648,9258160,1399236,30397584,-5684634,},},
2170static void lookup_add(ge *p, ge_precomp *tmp_c, fe tmp_a, fe tmp_b,
2171 const ge_precomp comb[8], const u8 scalar[32], int i)
2173 u8 teeth = (u8)((scalar_bit(scalar, i) ) +
2174 (scalar_bit(scalar, i + 32) << 1) +
2175 (scalar_bit(scalar, i + 64) << 2) +
2176 (scalar_bit(scalar, i + 96) << 3));
2177 u8 high = teeth >> 3;
2178 u8 index = (teeth ^ (high - 1)) & 7;
2179 FOR (j, 0, 8) {
2180 i32 select = 1 & (((j ^ index) - 1) >> 8);
2181 fe_ccopy(tmp_c->Yp, comb[j].Yp, select);
2182 fe_ccopy(tmp_c->Ym, comb[j].Ym, select);
2183 fe_ccopy(tmp_c->T2, comb[j].T2, select);
2185 fe_neg(tmp_a, tmp_c->T2);
2186 fe_cswap(tmp_c->T2, tmp_a , high ^ 1);
2187 fe_cswap(tmp_c->Yp, tmp_c->Ym, high ^ 1);
2188 ge_madd(p, p, tmp_c, tmp_a, tmp_b);
2191// p = [scalar]B, where B is the base point
2192static void ge_scalarmult_base(ge *p, const u8 scalar[32])
2194 // twin 4-bits signed combs, from Mike Hamburg's
2195 // Fast and compact elliptic-curve cryptography (2012)
2196 // 1 / 2 modulo L
2197 static const u8 half_mod_L[32] = {
2198 247,233,122,46,141,49,9,44,107,206,123,81,239,124,111,10,
2199 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,
2200 };
2201 // (2^256 - 1) / 2 modulo L
2202 static const u8 half_ones[32] = {
2203 142,74,204,70,186,24,118,107,184,231,190,57,250,173,119,99,
2204 255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,7,
2205 };
2207 // All bits set form: 1 means 1, 0 means -1
2208 u8 s_scalar[32];
2209 crypto_eddsa_mul_add(s_scalar, scalar, half_mod_L, half_ones);
2211 // Double and add ladder
2212 fe tmp_a, tmp_b; // temporaries for addition
2213 ge_precomp tmp_c; // temporary for comb lookup
2214 ge tmp_d; // temporary for doubling
2215 fe_1(tmp_c.Yp);
2216 fe_1(tmp_c.Ym);
2217 fe_0(tmp_c.T2);
2219 // Save a double on the first iteration
2220 ge_zero(p);
2221 lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_low , s_scalar, 31);
2222 lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_high, s_scalar, 31+128);
2223 // Regular double & add for the rest
2224 for (int i = 30; i >= 0; i--) {
2225 ge_double(p, p, &tmp_d);
2226 lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_low , s_scalar, i);
2227 lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_high, s_scalar, i+128);
2229 // Note: we could save one addition at the end if we assumed the
2230 // scalar fit in 252 bits. Which it does in practice if it is
2231 // selected at random. However, non-random, non-hashed scalars
2232 // *can* overflow 252 bits in practice. Better account for that
2233 // than leaving that kind of subtle corner case.
2235 WIPE_BUFFER(tmp_a); WIPE_CTX(&tmp_d);
2236 WIPE_BUFFER(tmp_b); WIPE_CTX(&tmp_c);
2237 WIPE_BUFFER(s_scalar);
2240void crypto_eddsa_scalarbase(u8 point[32], const u8 scalar[32])
2242 ge P;
2243 ge_scalarmult_base(&P, scalar);
2244 ge_tobytes(point, &P);
2245 WIPE_CTX(&P);
2248void crypto_eddsa_key_pair(u8 secret_key[64], u8 public_key[32], u8 seed[32])
2250 // To allow overlaps, observable writes happen in this order:
2251 // 1. seed
2252 // 2. secret_key
2253 // 3. public_key
2254 u8 a[64];
2255 COPY(a, seed, 32);
2256 crypto_wipe(seed, 32);
2257 COPY(secret_key, a, 32);
2258 crypto_blake2b(a, 64, a, 32);
2259 crypto_eddsa_trim_scalar(a, a);
2260 crypto_eddsa_scalarbase(secret_key + 32, a);
2261 COPY(public_key, secret_key + 32, 32);
2262 WIPE_BUFFER(a);
2265static void hash_reduce(u8 h[32],
2266 const u8 *a, size_t a_size,
2267 const u8 *b, size_t b_size,
2268 const u8 *c, size_t c_size)
2270 u8 hash[64];
2271 crypto_blake2b_ctx ctx;
2272 crypto_blake2b_init (&ctx, 64);
2273 crypto_blake2b_update(&ctx, a, a_size);
2274 crypto_blake2b_update(&ctx, b, b_size);
2275 crypto_blake2b_update(&ctx, c, c_size);
2276 crypto_blake2b_final (&ctx, hash);
2277 crypto_eddsa_reduce(h, hash);
2280// Digital signature of a message with from a secret key.
2282// The secret key comprises two parts:
2283// - The seed that generates the key (secret_key[ 0..31])
2284// - The public key (secret_key[32..63])
2286// The seed and the public key are bundled together to make sure users
2287// don't use mismatched seeds and public keys, which would instantly
2288// leak the secret scalar and allow forgeries (allowing this to happen
2289// has resulted in critical vulnerabilities in the wild).
2291// The seed is hashed to derive the secret scalar and a secret prefix.
2292// The sole purpose of the prefix is to generate a secret random nonce.
2293// The properties of that nonce must be as follows:
2294// - Unique: we need a different one for each message.
2295// - Secret: third parties must not be able to predict it.
2296// - Random: any detectable bias would break all security.
2298// There are two ways to achieve these properties. The obvious one is
2299// to simply generate a random number. Here that would be a parameter
2300// (Monocypher doesn't have an RNG). It works, but then users may reuse
2301// the nonce by accident, which _also_ leaks the secret scalar and
2302// allows forgeries. This has happened in the wild too.
2304// This is no good, so instead we generate that nonce deterministically
2305// by reducing modulo L a hash of the secret prefix and the message.
2306// The secret prefix makes the nonce unpredictable, the message makes it
2307// unique, and the hash/reduce removes all bias.
2309// The cost of that safety is hashing the message twice. If that cost
2310// is unacceptable, there are two alternatives:
2312// - Signing a hash of the message instead of the message itself. This
2313// is fine as long as the hash is collision resistant. It is not
2314// compatible with existing "pure" signatures, but at least it's safe.
2316// - Using a random nonce. Please exercise **EXTREME CAUTION** if you
2317// ever do that. It is absolutely **critical** that the nonce is
2318// really an unbiased random number between 0 and L-1, never reused,
2319// and wiped immediately.
2321// To lower the likelihood of complete catastrophe if the RNG is
2322// either flawed or misused, you can hash the RNG output together with
2323// the secret prefix and the beginning of the message, and use the
2324// reduction of that hash instead of the RNG output itself. It's not
2325// foolproof (you'd need to hash the whole message) but it helps.
2327// Signing a message involves the following operations:
2329// scalar, prefix = HASH(secret_key)
2330// r = HASH(prefix || message) % L
2331// R = [r]B
2332// h = HASH(R || public_key || message) % L
2333// S = ((h * a) + r) % L
2334// signature = R || S
2335void crypto_eddsa_sign(u8 signature [64], const u8 secret_key[64],
2336 const u8 *message, size_t message_size)
2338 u8 a[64]; // secret scalar and prefix
2339 u8 r[32]; // secret deterministic "random" nonce
2340 u8 h[32]; // publically verifiable hash of the message (not wiped)
2341 u8 R[32]; // first half of the signature (allows overlapping inputs)
2343 crypto_blake2b(a, 64, secret_key, 32);
2344 crypto_eddsa_trim_scalar(a, a);
2345 hash_reduce(r, a + 32, 32, message, message_size, 0, 0);
2346 crypto_eddsa_scalarbase(R, r);
2347 hash_reduce(h, R, 32, secret_key + 32, 32, message, message_size);
2348 COPY(signature, R, 32);
2349 crypto_eddsa_mul_add(signature + 32, h, a, r);
2351 WIPE_BUFFER(a);
2352 WIPE_BUFFER(r);
2355// To check the signature R, S of the message M with the public key A,
2356// there are 3 steps:
2358// compute h = HASH(R || A || message) % L
2359// check that A is on the curve.
2360// check that R == [s]B - [h]A
2362// The last two steps are done in crypto_eddsa_check_equation()
2363int crypto_eddsa_check(const u8 signature[64], const u8 public_key[32],
2364 const u8 *message, size_t message_size)
2366 u8 h[32];
2367 hash_reduce(h, signature, 32, public_key, 32, message, message_size);
2368 return crypto_eddsa_check_equation(signature, public_key, h);
2371/////////////////////////
2372/// EdDSA <--> X25519 ///
2373/////////////////////////
2374void crypto_eddsa_to_x25519(u8 x25519[32], const u8 eddsa[32])
2376 // (u, v) = ((1+y)/(1-y), sqrt(-486664)*u/x)
2377 // Only converting y to u, the sign of x is ignored.
2378 fe t1, t2;
2379 fe_frombytes(t2, eddsa);
2380 fe_add(t1, fe_one, t2);
2381 fe_sub(t2, fe_one, t2);
2382 fe_invert(t2, t2);
2383 fe_mul(t1, t1, t2);
2384 fe_tobytes(x25519, t1);
2385 WIPE_BUFFER(t1);
2386 WIPE_BUFFER(t2);
2389void crypto_x25519_to_eddsa(u8 eddsa[32], const u8 x25519[32])
2391 // (x, y) = (sqrt(-486664)*u/v, (u-1)/(u+1))
2392 // Only converting u to y, x is assumed positive.
2393 fe t1, t2;
2394 fe_frombytes(t2, x25519);
2395 fe_sub(t1, t2, fe_one);
2396 fe_add(t2, t2, fe_one);
2397 fe_invert(t2, t2);
2398 fe_mul(t1, t1, t2);
2399 fe_tobytes(eddsa, t1);
2400 WIPE_BUFFER(t1);
2401 WIPE_BUFFER(t2);
2404/////////////////////////////////////////////
2405/// Dirty ephemeral public key generation ///
2406/////////////////////////////////////////////
2408// Those functions generates a public key, *without* clearing the
2409// cofactor. Sending that key over the network leaks 3 bits of the
2410// private key. Use only to generate ephemeral keys that will be hidden
2411// with crypto_curve_to_hidden().
2413// The public key is otherwise compatible with crypto_x25519(), which
2414// properly clears the cofactor.
2416// Note that the distribution of the resulting public keys is almost
2417// uniform. Flipping the sign of the v coordinate (not provided by this
2418// function), covers the entire key space almost perfectly, where
2419// "almost" means a 2^-128 bias (undetectable). This uniformity is
2420// needed to ensure the proper randomness of the resulting
2421// representatives (once we apply crypto_curve_to_hidden()).
2423// Recall that Curve25519 has order C = 2^255 + e, with e < 2^128 (not
2424// to be confused with the prime order of the main subgroup, L, which is
2425// 8 times less than that).
2427// Generating all points would require us to multiply a point of order C
2428// (the base point plus any point of order 8) by all scalars from 0 to
2429// C-1. Clamping limits us to scalars between 2^254 and 2^255 - 1. But
2430// by negating the resulting point at random, we also cover scalars from
2431// -2^255 + 1 to -2^254 (which modulo C is congruent to e+1 to 2^254 + e).
2433// In practice:
2434// - Scalars from 0 to e + 1 are never generated
2435// - Scalars from 2^255 to 2^255 + e are never generated
2436// - Scalars from 2^254 + 1 to 2^254 + e are generated twice
2438// Since e < 2^128, detecting this bias requires observing over 2^100
2439// representatives from a given source (this will never happen), *and*
2440// recovering enough of the private key to determine that they do, or do
2441// not, belong to the biased set (this practically requires solving
2442// discrete logarithm, which is conjecturally intractable).
2444// In practice, this means the bias is impossible to detect.
2446// s + (x*L) % 8*L
2447// Guaranteed to fit in 256 bits iff s fits in 255 bits.
2448// L < 2^253
2449// x%8 < 2^3
2450// L * (x%8) < 2^255
2451// s < 2^255
2452// s + L * (x%8) < 2^256
2453static void add_xl(u8 s[32], u8 x)
2455 u64 mod8 = x & 7;
2456 u64 carry = 0;
2457 FOR (i , 0, 8) {
2458 carry = carry + load32_le(s + 4*i) + L[i] * mod8;
2459 store32_le(s + 4*i, (u32)carry);
2460 carry >>= 32;
2464// "Small" dirty ephemeral key.
2465// Use if you need to shrink the size of the binary, and can afford to
2466// slow down by a factor of two (compared to the fast version)
2468// This version works by decoupling the cofactor from the main factor.
2470// - The trimmed scalar determines the main factor
2471// - The clamped bits of the scalar determine the cofactor.
2473// Cofactor and main factor are combined into a single scalar, which is
2474// then multiplied by a point of order 8*L (unlike the base point, which
2475// has prime order). That "dirty" base point is the addition of the
2476// regular base point (9), and a point of order 8.
2477void crypto_x25519_dirty_small(u8 public_key[32], const u8 secret_key[32])
2479 // Base point of order 8*L
2480 // Raw scalar multiplication with it does not clear the cofactor,
2481 // and the resulting public key will reveal 3 bits of the scalar.
2482 //
2483 // The low order component of this base point has been chosen
2484 // to yield the same results as crypto_x25519_dirty_fast().
2485 static const u8 dirty_base_point[32] = {
2486 0xd8, 0x86, 0x1a, 0xa2, 0x78, 0x7a, 0xd9, 0x26,
2487 0x8b, 0x74, 0x74, 0xb6, 0x82, 0xe3, 0xbe, 0xc3,
2488 0xce, 0x36, 0x9a, 0x1e, 0x5e, 0x31, 0x47, 0xa2,
2489 0x6d, 0x37, 0x7c, 0xfd, 0x20, 0xb5, 0xdf, 0x75,
2490 };
2491 // separate the main factor & the cofactor of the scalar
2492 u8 scalar[32];
2493 crypto_eddsa_trim_scalar(scalar, secret_key);
2495 // Separate the main factor and the cofactor
2496 //
2497 // The scalar is trimmed, so its cofactor is cleared. The three
2498 // least significant bits however still have a main factor. We must
2499 // remove it for X25519 compatibility.
2500 //
2501 // cofactor = lsb * L (modulo 8*L)
2502 // combined = scalar + cofactor (modulo 8*L)
2503 add_xl(scalar, secret_key[0]);
2504 scalarmult(public_key, scalar, dirty_base_point, 256);
2505 WIPE_BUFFER(scalar);
2508// Select low order point
2509// We're computing the [cofactor]lop scalar multiplication, where:
2511// cofactor = tweak & 7.
2512// lop = (lop_x, lop_y)
2513// lop_x = sqrt((sqrt(d + 1) + 1) / d)
2514// lop_y = -lop_x * sqrtm1
2516// The low order point has order 8. There are 4 such points. We've
2517// chosen the one whose both coordinates are positive (below p/2).
2518// The 8 low order points are as follows:
2520// [0]lop = ( 0 , 1 )
2521// [1]lop = ( lop_x , lop_y)
2522// [2]lop = ( sqrt(-1), -0 )
2523// [3]lop = ( lop_x , -lop_y)
2524// [4]lop = (-0 , -1 )
2525// [5]lop = (-lop_x , -lop_y)
2526// [6]lop = (-sqrt(-1), 0 )
2527// [7]lop = (-lop_x , lop_y)
2529// The x coordinate is either 0, sqrt(-1), lop_x, or their opposite.
2530// The y coordinate is either 0, -1 , lop_y, or their opposite.
2531// The pattern for both is the same, except for a rotation of 2 (modulo 8)
2533// This helper function captures the pattern, and we can use it thus:
2535// select_lop(x, lop_x, sqrtm1, cofactor);
2536// select_lop(y, lop_y, fe_one, cofactor + 2);
2538// This is faster than an actual scalar multiplication,
2539// and requires less code than naive constant time look up.
2540static void select_lop(fe out, const fe x, const fe k, u8 cofactor)
2542 fe tmp;
2543 fe_0(out);
2544 fe_ccopy(out, k , (cofactor >> 1) & 1); // bit 1
2545 fe_ccopy(out, x , (cofactor >> 0) & 1); // bit 0
2546 fe_neg (tmp, out);
2547 fe_ccopy(out, tmp, (cofactor >> 2) & 1); // bit 2
2548 WIPE_BUFFER(tmp);
2551// "Fast" dirty ephemeral key
2552// We use this one by default.
2554// This version works by performing a regular scalar multiplication,
2555// then add a low order point. The scalar multiplication is done in
2556// Edwards space for more speed (*2 compared to the "small" version).
2557// The cost is a bigger binary for programs that don't also sign messages.
2558void crypto_x25519_dirty_fast(u8 public_key[32], const u8 secret_key[32])
2560 // Compute clean scalar multiplication
2561 u8 scalar[32];
2562 ge pk;
2563 crypto_eddsa_trim_scalar(scalar, secret_key);
2564 ge_scalarmult_base(&pk, scalar);
2566 // Compute low order point
2567 fe t1, t2;
2568 select_lop(t1, lop_x, sqrtm1, secret_key[0]);
2569 select_lop(t2, lop_y, fe_one, secret_key[0] + 2);
2570 ge_precomp low_order_point;
2571 fe_add(low_order_point.Yp, t2, t1);
2572 fe_sub(low_order_point.Ym, t2, t1);
2573 fe_mul(low_order_point.T2, t2, t1);
2574 fe_mul(low_order_point.T2, low_order_point.T2, D2);
2576 // Add low order point to the public key
2577 ge_madd(&pk, &pk, &low_order_point, t1, t2);
2579 // Convert to Montgomery u coordinate (we ignore the sign)
2580 fe_add(t1, pk.Z, pk.Y);
2581 fe_sub(t2, pk.Z, pk.Y);
2582 fe_invert(t2, t2);
2583 fe_mul(t1, t1, t2);
2585 fe_tobytes(public_key, t1);
2587 WIPE_BUFFER(t1); WIPE_CTX(&pk);
2588 WIPE_BUFFER(t2); WIPE_CTX(&low_order_point);
2589 WIPE_BUFFER(scalar);
2592///////////////////
2593/// Elligator 2 ///
2594///////////////////
2595static const fe A = {486662};
2597// Elligator direct map
2599// Computes the point corresponding to a representative, encoded in 32
2600// bytes (little Endian). Since positive representatives fits in 254
2601// bits, The two most significant bits are ignored.
2603// From the paper:
2604// w = -A / (fe(1) + non_square * r^2)
2605// e = chi(w^3 + A*w^2 + w)
2606// u = e*w - (fe(1)-e)*(A//2)
2607// v = -e * sqrt(u^3 + A*u^2 + u)
2609// We ignore v because we don't need it for X25519 (the Montgomery
2610// ladder only uses u).
2612// Note that e is either 0, 1 or -1
2613// if e = 0 u = 0 and v = 0
2614// if e = 1 u = w
2615// if e = -1 u = -w - A = w * non_square * r^2
2617// Let r1 = non_square * r^2
2618// Let r2 = 1 + r1
2619// Note that r2 cannot be zero, -1/non_square is not a square.
2620// We can (tediously) verify that:
2621// w^3 + A*w^2 + w = (A^2*r1 - r2^2) * A / r2^3
2622// Therefore:
2623// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3))
2624// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3)) * 1
2625// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3)) * chi(r2^6)
2626// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3) * r2^6)
2627// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * A * r2^3)
2628// Corollary:
2629// e = 1 if (A^2*r1 - r2^2) * A * r2^3) is a non-zero square
2630// e = -1 if (A^2*r1 - r2^2) * A * r2^3) is not a square
2631// Note that w^3 + A*w^2 + w (and therefore e) can never be zero:
2632// w^3 + A*w^2 + w = w * (w^2 + A*w + 1)
2633// w^3 + A*w^2 + w = w * (w^2 + A*w + A^2/4 - A^2/4 + 1)
2634// w^3 + A*w^2 + w = w * (w + A/2)^2 - A^2/4 + 1)
2635// which is zero only if:
2636// w = 0 (impossible)
2637// (w + A/2)^2 = A^2/4 - 1 (impossible, because A^2/4-1 is not a square)
2639// Let isr = invsqrt((A^2*r1 - r2^2) * A * r2^3)
2640// isr = sqrt(1 / ((A^2*r1 - r2^2) * A * r2^3)) if e = 1
2641// isr = sqrt(sqrt(-1) / ((A^2*r1 - r2^2) * A * r2^3)) if e = -1
2643// if e = 1
2644// let u1 = -A * (A^2*r1 - r2^2) * A * r2^2 * isr^2
2645// u1 = w
2646// u1 = u
2648// if e = -1
2649// let ufactor = -non_square * sqrt(-1) * r^2
2650// let vfactor = sqrt(ufactor)
2651// let u2 = -A * (A^2*r1 - r2^2) * A * r2^2 * isr^2 * ufactor
2652// u2 = w * -1 * -non_square * r^2
2653// u2 = w * non_square * r^2
2654// u2 = u
2655void crypto_elligator_map(u8 curve[32], const u8 hidden[32])
2657 fe r, u, t1, t2, t3;
2658 fe_frombytes_mask(r, hidden, 2); // r is encoded in 254 bits.
2659 fe_sq(r, r);
2660 fe_add(t1, r, r);
2661 fe_add(u, t1, fe_one);
2662 fe_sq (t2, u);
2663 fe_mul(t3, A2, t1);
2664 fe_sub(t3, t3, t2);
2665 fe_mul(t3, t3, A);
2666 fe_mul(t1, t2, u);
2667 fe_mul(t1, t3, t1);
2668 int is_square = invsqrt(t1, t1);
2669 fe_mul(u, r, ufactor);
2670 fe_ccopy(u, fe_one, is_square);
2671 fe_sq (t1, t1);
2672 fe_mul(u, u, A);
2673 fe_mul(u, u, t3);
2674 fe_mul(u, u, t2);
2675 fe_mul(u, u, t1);
2676 fe_neg(u, u);
2677 fe_tobytes(curve, u);
2679 WIPE_BUFFER(t1); WIPE_BUFFER(r);
2680 WIPE_BUFFER(t2); WIPE_BUFFER(u);
2681 WIPE_BUFFER(t3);
2684// Elligator inverse map
2686// Computes the representative of a point, if possible. If not, it does
2687// nothing and returns -1. Note that the success of the operation
2688// depends only on the point (more precisely its u coordinate). The
2689// tweak parameter is used only upon success
2691// The tweak should be a random byte. Beyond that, its contents are an
2692// implementation detail. Currently, the tweak comprises:
2693// - Bit 1 : sign of the v coordinate (0 if positive, 1 if negative)
2694// - Bit 2-5: not used
2695// - Bits 6-7: random padding
2697// From the paper:
2698// Let sq = -non_square * u * (u+A)
2699// if sq is not a square, or u = -A, there is no mapping
2700// Assuming there is a mapping:
2701// if v is positive: r = sqrt(-u / (non_square * (u+A)))
2702// if v is negative: r = sqrt(-(u+A) / (non_square * u ))
2704// We compute isr = invsqrt(-non_square * u * (u+A))
2705// if it wasn't a square, abort.
2706// else, isr = sqrt(-1 / (non_square * u * (u+A))
2708// If v is positive, we return isr * u:
2709// isr * u = sqrt(-1 / (non_square * u * (u+A)) * u
2710// isr * u = sqrt(-u / (non_square * (u+A))
2712// If v is negative, we return isr * (u+A):
2713// isr * (u+A) = sqrt(-1 / (non_square * u * (u+A)) * (u+A)
2714// isr * (u+A) = sqrt(-(u+A) / (non_square * u)
2715int crypto_elligator_rev(u8 hidden[32], const u8 public_key[32], u8 tweak)
2717 fe t1, t2, t3;
2718 fe_frombytes(t1, public_key); // t1 = u
2720 fe_add(t2, t1, A); // t2 = u + A
2721 fe_mul(t3, t1, t2);
2722 fe_mul_small(t3, t3, -2);
2723 int is_square = invsqrt(t3, t3); // t3 = sqrt(-1 / non_square * u * (u+A))
2724 if (is_square) {
2725 // The only variable time bit. This ultimately reveals how many
2726 // tries it took us to find a representable key.
2727 // This does not affect security as long as we try keys at random.
2729 fe_ccopy (t1, t2, tweak & 1); // multiply by u if v is positive,
2730 fe_mul (t3, t1, t3); // multiply by u+A otherwise
2731 fe_mul_small(t1, t3, 2);
2732 fe_neg (t2, t3);
2733 fe_ccopy (t3, t2, fe_isodd(t1));
2734 fe_tobytes(hidden, t3);
2736 // Pad with two random bits
2737 hidden[31] |= tweak & 0xc0;
2740 WIPE_BUFFER(t1);
2741 WIPE_BUFFER(t2);
2742 WIPE_BUFFER(t3);
2743 return is_square - 1;
2746void crypto_elligator_key_pair(u8 hidden[32], u8 secret_key[32], u8 seed[32])
2748 u8 pk [32]; // public key
2749 u8 buf[64]; // seed + representative
2750 COPY(buf + 32, seed, 32);
2751 do {
2752 crypto_chacha20_djb(buf, 0, 64, buf+32, zero, 0);
2753 crypto_x25519_dirty_fast(pk, buf); // or the "small" version
2754 } while(crypto_elligator_rev(buf+32, pk, buf[32]));
2755 // Note that the return value of crypto_elligator_rev() is
2756 // independent from its tweak parameter.
2757 // Therefore, buf[32] is not actually reused. Either we loop one
2758 // more time and buf[32] is used for the new seed, or we succeeded,
2759 // and buf[32] becomes the tweak parameter.
2761 crypto_wipe(seed, 32);
2762 COPY(hidden , buf + 32, 32);
2763 COPY(secret_key, buf , 32);
2764 WIPE_BUFFER(buf);
2765 WIPE_BUFFER(pk);
2768///////////////////////
2769/// Scalar division ///
2770///////////////////////
2772// Montgomery reduction.
2773// Divides x by (2^256), and reduces the result modulo L
2775// Precondition:
2776// x < L * 2^256
2777// Constants:
2778// r = 2^256 (makes division by r trivial)
2779// k = (r * (1/r) - 1) // L (1/r is computed modulo L )
2780// Algorithm:
2781// s = (x * k) % r
2782// t = x + s*L (t is always a multiple of r)
2783// u = (t/r) % L (u is always below 2*L, conditional subtraction is enough)
2784static void redc(u32 u[8], u32 x[16])
2786 static const u32 k[8] = {
2787 0x12547e1b, 0xd2b51da3, 0xfdba84ff, 0xb1a206f2,
2788 0xffa36bea, 0x14e75438, 0x6fe91836, 0x9db6c6f2,
2789 };
2791 // s = x * k (modulo 2^256)
2792 // This is cheaper than the full multiplication.
2793 u32 s[8] = {0};
2794 FOR (i, 0, 8) {
2795 u64 carry = 0;
2796 FOR (j, 0, 8-i) {
2797 carry += s[i+j] + (u64)x[i] * k[j];
2798 s[i+j] = (u32)carry;
2799 carry >>= 32;
2802 u32 t[16] = {0};
2803 multiply(t, s, L);
2805 // t = t + x
2806 u64 carry = 0;
2807 FOR (i, 0, 16) {
2808 carry += (u64)t[i] + x[i];
2809 t[i] = (u32)carry;
2810 carry >>= 32;
2813 // u = (t / 2^256) % L
2814 // Note that t / 2^256 is always below 2*L,
2815 // So a constant time conditional subtraction is enough
2816 remove_l(u, t+8);
2818 WIPE_BUFFER(s);
2819 WIPE_BUFFER(t);
2822void crypto_x25519_inverse(u8 blind_salt [32], const u8 private_key[32],
2823 const u8 curve_point[32])
2825 static const u8 Lm2[32] = { // L - 2
2826 0xeb, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
2827 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
2828 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
2829 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
2830 };
2831 // 1 in Montgomery form
2832 u32 m_inv [8] = {
2833 0x8d98951d, 0xd6ec3174, 0x737dcf70, 0xc6ef5bf4,
2834 0xfffffffe, 0xffffffff, 0xffffffff, 0x0fffffff,
2835 };
2837 u8 scalar[32];
2838 crypto_eddsa_trim_scalar(scalar, private_key);
2840 // Convert the scalar in Montgomery form
2841 // m_scl = scalar * 2^256 (modulo L)
2842 u32 m_scl[8];
2844 u32 tmp[16];
2845 ZERO(tmp, 8);
2846 load32_le_buf(tmp+8, scalar, 8);
2847 mod_l(scalar, tmp);
2848 load32_le_buf(m_scl, scalar, 8);
2849 WIPE_BUFFER(tmp); // Wipe ASAP to save stack space
2852 // Compute the inverse
2853 u32 product[16];
2854 for (int i = 252; i >= 0; i--) {
2855 ZERO(product, 16);
2856 multiply(product, m_inv, m_inv);
2857 redc(m_inv, product);
2858 if (scalar_bit(Lm2, i)) {
2859 ZERO(product, 16);
2860 multiply(product, m_inv, m_scl);
2861 redc(m_inv, product);
2864 // Convert the inverse *out* of Montgomery form
2865 // scalar = m_inv / 2^256 (modulo L)
2866 COPY(product, m_inv, 8);
2867 ZERO(product + 8, 8);
2868 redc(m_inv, product);
2869 store32_le_buf(scalar, m_inv, 8); // the *inverse* of the scalar
2871 // Clear the cofactor of scalar:
2872 // cleared = scalar * (3*L + 1) (modulo 8*L)
2873 // cleared = scalar + scalar * 3 * L (modulo 8*L)
2874 // Note that (scalar * 3) is reduced modulo 8, so we only need the
2875 // first byte.
2876 add_xl(scalar, scalar[0] * 3);
2878 // Recall that 8*L < 2^256. However it is also very close to
2879 // 2^255. If we spanned the ladder over 255 bits, random tests
2880 // wouldn't catch the off-by-one error.
2881 scalarmult(blind_salt, scalar, curve_point, 256);
2883 WIPE_BUFFER(scalar); WIPE_BUFFER(m_scl);
2884 WIPE_BUFFER(product); WIPE_BUFFER(m_inv);
2887////////////////////////////////
2888/// Authenticated encryption ///
2889////////////////////////////////
2890static void lock_auth(u8 mac[16], const u8 auth_key[32],
2891 const u8 *ad , size_t ad_size,
2892 const u8 *cipher_text, size_t text_size)
2894 u8 sizes[16]; // Not secret, not wiped
2895 store64_le(sizes + 0, ad_size);
2896 store64_le(sizes + 8, text_size);
2897 crypto_poly1305_ctx poly_ctx; // auto wiped...
2898 crypto_poly1305_init (&poly_ctx, auth_key);
2899 crypto_poly1305_update(&poly_ctx, ad , ad_size);
2900 crypto_poly1305_update(&poly_ctx, zero , gap(ad_size, 16));
2901 crypto_poly1305_update(&poly_ctx, cipher_text, text_size);
2902 crypto_poly1305_update(&poly_ctx, zero , gap(text_size, 16));
2903 crypto_poly1305_update(&poly_ctx, sizes , 16);
2904 crypto_poly1305_final (&poly_ctx, mac); // ...here
2907void crypto_aead_init_x(crypto_aead_ctx *ctx,
2908 u8 const key[32], const u8 nonce[24])
2910 crypto_chacha20_h(ctx->key, key, nonce);
2911 COPY(ctx->nonce, nonce + 16, 8);
2912 ctx->counter = 0;
2915void crypto_aead_init_djb(crypto_aead_ctx *ctx,
2916 const u8 key[32], const u8 nonce[8])
2918 COPY(ctx->key , key , 32);
2919 COPY(ctx->nonce, nonce, 8);
2920 ctx->counter = 0;
2923void crypto_aead_init_ietf(crypto_aead_ctx *ctx,
2924 const u8 key[32], const u8 nonce[12])
2926 COPY(ctx->key , key , 32);
2927 COPY(ctx->nonce, nonce + 4, 8);
2928 ctx->counter = (u64)load32_le(nonce) << 32;
2931void crypto_aead_write(crypto_aead_ctx *ctx, u8 *cipher_text, u8 mac[16],
2932 const u8 *ad, size_t ad_size,
2933 const u8 *plain_text, size_t text_size)
2935 u8 auth_key[64]; // the last 32 bytes are used for rekeying.
2936 crypto_chacha20_djb(auth_key, 0, 64, ctx->key, ctx->nonce, ctx->counter);
2937 crypto_chacha20_djb(cipher_text, plain_text, text_size,
2938 ctx->key, ctx->nonce, ctx->counter + 1);
2939 lock_auth(mac, auth_key, ad, ad_size, cipher_text, text_size);
2940 COPY(ctx->key, auth_key + 32, 32);
2941 WIPE_BUFFER(auth_key);
2944int crypto_aead_read(crypto_aead_ctx *ctx, u8 *plain_text, const u8 mac[16],
2945 const u8 *ad, size_t ad_size,
2946 const u8 *cipher_text, size_t text_size)
2948 u8 auth_key[64]; // the last 32 bytes are used for rekeying.
2949 u8 real_mac[16];
2950 crypto_chacha20_djb(auth_key, 0, 64, ctx->key, ctx->nonce, ctx->counter);
2951 lock_auth(real_mac, auth_key, ad, ad_size, cipher_text, text_size);
2952 int mismatch = crypto_verify16(mac, real_mac);
2953 if (!mismatch) {
2954 crypto_chacha20_djb(plain_text, cipher_text, text_size,
2955 ctx->key, ctx->nonce, ctx->counter + 1);
2956 COPY(ctx->key, auth_key + 32, 32);
2958 WIPE_BUFFER(auth_key);
2959 WIPE_BUFFER(real_mac);
2960 return mismatch;
2963void crypto_aead_lock(u8 *cipher_text, u8 mac[16], const u8 key[32],
2964 const u8 nonce[24], const u8 *ad, size_t ad_size,
2965 const u8 *plain_text, size_t text_size)
2967 crypto_aead_ctx ctx;
2968 crypto_aead_init_x(&ctx, key, nonce);
2969 crypto_aead_write(&ctx, cipher_text, mac, ad, ad_size,
2970 plain_text, text_size);
2971 crypto_wipe(&ctx, sizeof(ctx));
2974int crypto_aead_unlock(u8 *plain_text, const u8 mac[16], const u8 key[32],
2975 const u8 nonce[24], const u8 *ad, size_t ad_size,
2976 const u8 *cipher_text, size_t text_size)
2978 crypto_aead_ctx ctx;
2979 crypto_aead_init_x(&ctx, key, nonce);
2980 int mismatch = crypto_aead_read(&ctx, plain_text, mac, ad, ad_size,
2981 cipher_text, text_size);
2982 crypto_wipe(&ctx, sizeof(ctx));
2983 return mismatch;
2986#ifdef MONOCYPHER_CPP_NAMESPACE
2988#endif