Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.
Real-time collaboration for Jupyter Notebooks, Linux Terminals, LaTeX, VS Code, R IDE, and more,
all in one place. Commercial Alternative to JupyterHub.
Path: blob/master/libraries/AP_CheckFirmware/monocypher.cpp
Views: 1798
// Monocypher version 3.1.21//2// This file is dual-licensed. Choose whichever licence you want from3// the two licences listed below.4//5// The first licence is a regular 2-clause BSD licence. The second licence6// is the CC-0 from Creative Commons. It is intended to release Monocypher7// to the public domain. The BSD licence serves as a fallback option.8//9// SPDX-License-Identifier: BSD-2-Clause OR CC0-1.010//11// ------------------------------------------------------------------------12//13// Copyright (c) 2017-2020, Loup Vaillant14// All rights reserved.15//16//17// Redistribution and use in source and binary forms, with or without18// modification, are permitted provided that the following conditions are19// met:20//21// 1. Redistributions of source code must retain the above copyright22// notice, this list of conditions and the following disclaimer.23//24// 2. Redistributions in binary form must reproduce the above copyright25// notice, this list of conditions and the following disclaimer in the26// documentation and/or other materials provided with the27// distribution.28//29// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS30// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT31// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR32// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT33// HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,34// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT35// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,36// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY37// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT38// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE39// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.40//41// ------------------------------------------------------------------------42//43// Written in 2017-2020 by Loup Vaillant44//45// To the extent possible under law, the author(s) have dedicated all copyright46// and related neighboring rights to this software to the public domain47// worldwide. This software is distributed without any warranty.48//49// You should have received a copy of the CC0 Public Domain Dedication along50// with this software. If not, see51// <https://creativecommons.org/publicdomain/zero/1.0/>5253#include "monocypher.h"5455// we don't need Argon256#define MONOCYPHER_ARGON2_ENABLE 05758// we want the bootloader to be as small as possible59#define BLAKE2_NO_UNROLLING 16061/////////////////62/// Utilities ///63/////////////////64#define FOR_T(type, i0, start, end) for (type i0 = (start); i0 < (end); i0++)65#define FOR(i1, start, end) FOR_T(size_t, i1, start, end)66#define COPY(dst, src, size) FOR(i2, 0, size) (dst)[i2] = (src)[i2]67#define ZERO(buf, size) FOR(i3, 0, size) (buf)[i3] = 068#define WIPE_CTX(ctx) crypto_wipe(ctx , sizeof(*(ctx)))69#define WIPE_BUFFER(buffer) crypto_wipe(buffer, sizeof(buffer))70#define MIN(a, b) ((a) <= (b) ? (a) : (b))71#define MAX(a, b) ((a) >= (b) ? (a) : (b))7273typedef int8_t i8;74typedef uint8_t u8;75typedef int16_t i16;76typedef uint32_t u32;77typedef int32_t i32;78typedef int64_t i64;79typedef uint64_t u64;8081static const u8 zero[128] = {0};8283// returns the smallest positive integer y such that84// (x + y) % pow_2 == 085// Basically, it's how many bytes we need to add to "align" x.86// Only works when pow_2 is a power of 2.87// Note: we use ~x+1 instead of -x to avoid compiler warnings88static size_t align(size_t x, size_t pow_2)89{90return (~x + 1) & (pow_2 - 1);91}9293static u32 load24_le(const u8 s[3])94{95return (u32)s[0]96| ((u32)s[1] << 8)97| ((u32)s[2] << 16);98}99100static u32 load32_le(const u8 s[4])101{102return (u32)s[0]103| ((u32)s[1] << 8)104| ((u32)s[2] << 16)105| ((u32)s[3] << 24);106}107108static u64 load64_le(const u8 s[8])109{110return load32_le(s) | ((u64)load32_le(s+4) << 32);111}112113static void store32_le(u8 out[4], u32 in)114{115out[0] = in & 0xff;116out[1] = (in >> 8) & 0xff;117out[2] = (in >> 16) & 0xff;118out[3] = (in >> 24) & 0xff;119}120121static void store64_le(u8 out[8], u64 in)122{123store32_le(out , (u32)in );124store32_le(out + 4, in >> 32);125}126127static void load32_le_buf (u32 *dst, const u8 *src, size_t size) {128FOR(i, 0, size) { dst[i] = load32_le(src + i*4); }129}130static void load64_le_buf (u64 *dst, const u8 *src, size_t size) {131FOR(i, 0, size) { dst[i] = load64_le(src + i*8); }132}133static void store32_le_buf(u8 *dst, const u32 *src, size_t size) {134FOR(i, 0, size) { store32_le(dst + i*4, src[i]); }135}136static void store64_le_buf(u8 *dst, const u64 *src, size_t size) {137FOR(i, 0, size) { store64_le(dst + i*8, src[i]); }138}139140static u64 rotr64(u64 x, u64 n) { return (x >> n) ^ (x << (64 - n)); }141static u32 rotl32(u32 x, u32 n) { return (x << n) ^ (x >> (32 - n)); }142143static int neq0(u64 diff)144{ // constant time comparison to zero145// return diff != 0 ? -1 : 0146u64 half = (diff >> 32) | ((u32)diff);147return (1 & ((half - 1) >> 32)) - 1;148}149150static u64 x16(const u8 a[16], const u8 b[16])151{152return (load64_le(a + 0) ^ load64_le(b + 0))153| (load64_le(a + 8) ^ load64_le(b + 8));154}155static u64 x32(const u8 a[32],const u8 b[32]){return x16(a,b)| x16(a+16, b+16);}156static u64 x64(const u8 a[64],const u8 b[64]){return x32(a,b)| x32(a+32, b+32);}157int crypto_verify16(const u8 a[16], const u8 b[16]){ return neq0(x16(a, b)); }158int crypto_verify32(const u8 a[32], const u8 b[32]){ return neq0(x32(a, b)); }159int crypto_verify64(const u8 a[64], const u8 b[64]){ return neq0(x64(a, b)); }160161void crypto_wipe(void *secret, size_t size)162{163volatile u8 *v_secret = (u8*)secret;164ZERO(v_secret, size);165}166167/////////////////168/// Chacha 20 ///169/////////////////170#define QUARTERROUND(a, b, c, d) \171a += b; d = rotl32(d ^ a, 16); \172c += d; b = rotl32(b ^ c, 12); \173a += b; d = rotl32(d ^ a, 8); \174c += d; b = rotl32(b ^ c, 7)175176static void chacha20_rounds(u32 out[16], const u32 in[16])177{178// The temporary variables make Chacha20 10% faster.179u32 t0 = in[ 0]; u32 t1 = in[ 1]; u32 t2 = in[ 2]; u32 t3 = in[ 3];180u32 t4 = in[ 4]; u32 t5 = in[ 5]; u32 t6 = in[ 6]; u32 t7 = in[ 7];181u32 t8 = in[ 8]; u32 t9 = in[ 9]; u32 t10 = in[10]; u32 t11 = in[11];182u32 t12 = in[12]; u32 t13 = in[13]; u32 t14 = in[14]; u32 t15 = in[15];183184FOR (i, 0, 10) { // 20 rounds, 2 rounds per loop.185QUARTERROUND(t0, t4, t8 , t12); // column 0186QUARTERROUND(t1, t5, t9 , t13); // column 1187QUARTERROUND(t2, t6, t10, t14); // column 2188QUARTERROUND(t3, t7, t11, t15); // column 3189QUARTERROUND(t0, t5, t10, t15); // diagonal 0190QUARTERROUND(t1, t6, t11, t12); // diagonal 1191QUARTERROUND(t2, t7, t8 , t13); // diagonal 2192QUARTERROUND(t3, t4, t9 , t14); // diagonal 3193}194out[ 0] = t0; out[ 1] = t1; out[ 2] = t2; out[ 3] = t3;195out[ 4] = t4; out[ 5] = t5; out[ 6] = t6; out[ 7] = t7;196out[ 8] = t8; out[ 9] = t9; out[10] = t10; out[11] = t11;197out[12] = t12; out[13] = t13; out[14] = t14; out[15] = t15;198}199200static void chacha20_init_key(u32 block[16], const u8 key[32])201{202load32_le_buf(block , (const u8*)"expand 32-byte k", 4); // constant203load32_le_buf(block+4, key , 8); // key204}205206void crypto_hchacha20(u8 out[32], const u8 key[32], const u8 in [16])207{208u32 block[16];209chacha20_init_key(block, key);210// input211load32_le_buf(block + 12, in, 4);212chacha20_rounds(block, block);213// prevent reversal of the rounds by revealing only half of the buffer.214store32_le_buf(out , block , 4); // constant215store32_le_buf(out+16, block+12, 4); // counter and nonce216WIPE_BUFFER(block);217}218219u64 crypto_chacha20_ctr(u8 *cipher_text, const u8 *plain_text,220size_t text_size, const u8 key[32], const u8 nonce[8],221u64 ctr)222{223u32 input[16];224chacha20_init_key(input, key);225input[12] = (u32) ctr;226input[13] = (u32)(ctr >> 32);227load32_le_buf(input+14, nonce, 2);228229// Whole blocks230u32 pool[16];231size_t nb_blocks = text_size >> 6;232FOR (i, 0, nb_blocks) {233chacha20_rounds(pool, input);234if (plain_text != 0) {235FOR (j, 0, 16) {236u32 p = pool[j] + input[j];237store32_le(cipher_text, p ^ load32_le(plain_text));238cipher_text += 4;239plain_text += 4;240}241} else {242FOR (j, 0, 16) {243u32 p = pool[j] + input[j];244store32_le(cipher_text, p);245cipher_text += 4;246}247}248input[12]++;249if (input[12] == 0) {250input[13]++;251}252}253text_size &= 63;254255// Last (incomplete) block256if (text_size > 0) {257if (plain_text == 0) {258plain_text = zero;259}260chacha20_rounds(pool, input);261u8 tmp[64];262FOR (i, 0, 16) {263store32_le(tmp + i*4, pool[i] + input[i]);264}265FOR (i, 0, text_size) {266cipher_text[i] = tmp[i] ^ plain_text[i];267}268WIPE_BUFFER(tmp);269}270ctr = input[12] + ((u64)input[13] << 32) + (text_size > 0);271272WIPE_BUFFER(pool);273WIPE_BUFFER(input);274return ctr;275}276277u32 crypto_ietf_chacha20_ctr(u8 *cipher_text, const u8 *plain_text,278size_t text_size,279const u8 key[32], const u8 nonce[12], u32 ctr)280{281u64 big_ctr = ctr + ((u64)load32_le(nonce) << 32);282return (u32)crypto_chacha20_ctr(cipher_text, plain_text, text_size,283key, nonce + 4, big_ctr);284}285286u64 crypto_xchacha20_ctr(u8 *cipher_text, const u8 *plain_text,287size_t text_size,288const u8 key[32], const u8 nonce[24], u64 ctr)289{290u8 sub_key[32];291crypto_hchacha20(sub_key, key, nonce);292ctr = crypto_chacha20_ctr(cipher_text, plain_text, text_size,293sub_key, nonce+16, ctr);294WIPE_BUFFER(sub_key);295return ctr;296}297298void crypto_chacha20(u8 *cipher_text, const u8 *plain_text, size_t text_size,299const u8 key[32], const u8 nonce[8])300{301crypto_chacha20_ctr(cipher_text, plain_text, text_size, key, nonce, 0);302303}304void crypto_ietf_chacha20(u8 *cipher_text, const u8 *plain_text,305size_t text_size,306const u8 key[32], const u8 nonce[12])307{308crypto_ietf_chacha20_ctr(cipher_text, plain_text, text_size, key, nonce, 0);309}310311void crypto_xchacha20(u8 *cipher_text, const u8 *plain_text, size_t text_size,312const u8 key[32], const u8 nonce[24])313{314crypto_xchacha20_ctr(cipher_text, plain_text, text_size, key, nonce, 0);315}316317/////////////////318/// Poly 1305 ///319/////////////////320321// h = (h + c) * r322// preconditions:323// ctx->h <= 4_ffffffff_ffffffff_ffffffff_ffffffff324// ctx->c <= 1_ffffffff_ffffffff_ffffffff_ffffffff325// ctx->r <= 0ffffffc_0ffffffc_0ffffffc_0fffffff326// Postcondition:327// ctx->h <= 4_ffffffff_ffffffff_ffffffff_ffffffff328static void poly_block(crypto_poly1305_ctx *ctx)329{330// s = h + c, without carry propagation331const u64 s0 = ctx->h[0] + (u64)ctx->c[0]; // s0 <= 1_fffffffe332const u64 s1 = ctx->h[1] + (u64)ctx->c[1]; // s1 <= 1_fffffffe333const u64 s2 = ctx->h[2] + (u64)ctx->c[2]; // s2 <= 1_fffffffe334const u64 s3 = ctx->h[3] + (u64)ctx->c[3]; // s3 <= 1_fffffffe335const u32 s4 = ctx->h[4] + ctx->c[4]; // s4 <= 5336337// Local all the things!338const u32 r0 = ctx->r[0]; // r0 <= 0fffffff339const u32 r1 = ctx->r[1]; // r1 <= 0ffffffc340const u32 r2 = ctx->r[2]; // r2 <= 0ffffffc341const u32 r3 = ctx->r[3]; // r3 <= 0ffffffc342const u32 rr0 = (r0 >> 2) * 5; // rr0 <= 13fffffb // lose 2 bits...343const u32 rr1 = (r1 >> 2) + r1; // rr1 <= 13fffffb // rr1 == (r1 >> 2) * 5344const u32 rr2 = (r2 >> 2) + r2; // rr2 <= 13fffffb // rr1 == (r2 >> 2) * 5345const u32 rr3 = (r3 >> 2) + r3; // rr3 <= 13fffffb // rr1 == (r3 >> 2) * 5346347// (h + c) * r, without carry propagation348const u64 x0 = s0*r0+ s1*rr3+ s2*rr2+ s3*rr1+ s4*rr0; // <= 97ffffe007fffff8349const u64 x1 = s0*r1+ s1*r0 + s2*rr3+ s3*rr2+ s4*rr1; // <= 8fffffe20ffffff6350const u64 x2 = s0*r2+ s1*r1 + s2*r0 + s3*rr3+ s4*rr2; // <= 87ffffe417fffff4351const u64 x3 = s0*r3+ s1*r2 + s2*r1 + s3*r0 + s4*rr3; // <= 7fffffe61ffffff2352const u32 x4 = s4 * (r0 & 3); // ...recover 2 bits // <= f353354// partial reduction modulo 2^130 - 5355const u32 u5 = x4 + (x3 >> 32); // u5 <= 7ffffff5356const u64 u0 = (u5 >> 2) * 5 + (x0 & 0xffffffff);357const u64 u1 = (u0 >> 32) + (x1 & 0xffffffff) + (x0 >> 32);358const u64 u2 = (u1 >> 32) + (x2 & 0xffffffff) + (x1 >> 32);359const u64 u3 = (u2 >> 32) + (x3 & 0xffffffff) + (x2 >> 32);360const u64 u4 = (u3 >> 32) + (u5 & 3);361362// Update the hash363ctx->h[0] = (u32)u0; // u0 <= 1_9ffffff0364ctx->h[1] = (u32)u1; // u1 <= 1_97ffffe0365ctx->h[2] = (u32)u2; // u2 <= 1_8fffffe2366ctx->h[3] = (u32)u3; // u3 <= 1_87ffffe4367ctx->h[4] = (u32)u4; // u4 <= 4368}369370// (re-)initialises the input counter and input buffer371static void poly_clear_c(crypto_poly1305_ctx *ctx)372{373ZERO(ctx->c, 4);374ctx->c_idx = 0;375}376377static void poly_take_input(crypto_poly1305_ctx *ctx, u8 input)378{379size_t word = ctx->c_idx >> 2;380size_t byte = ctx->c_idx & 3;381ctx->c[word] |= (u32)input << (byte * 8);382ctx->c_idx++;383}384385static void poly_update(crypto_poly1305_ctx *ctx,386const u8 *message, size_t message_size)387{388FOR (i, 0, message_size) {389poly_take_input(ctx, message[i]);390if (ctx->c_idx == 16) {391poly_block(ctx);392poly_clear_c(ctx);393}394}395}396397void crypto_poly1305_init(crypto_poly1305_ctx *ctx, const u8 key[32])398{399// Initial hash is zero400ZERO(ctx->h, 5);401// add 2^130 to every input block402ctx->c[4] = 1;403poly_clear_c(ctx);404// load r and pad (r has some of its bits cleared)405load32_le_buf(ctx->r , key , 4);406load32_le_buf(ctx->pad, key+16, 4);407FOR (i, 0, 1) { ctx->r[i] &= 0x0fffffff; }408FOR (i, 1, 4) { ctx->r[i] &= 0x0ffffffc; }409}410411void crypto_poly1305_update(crypto_poly1305_ctx *ctx,412const u8 *message, size_t message_size)413{414if (message_size == 0) {415return;416}417// Align ourselves with block boundaries418size_t aligned = MIN(align(ctx->c_idx, 16), message_size);419poly_update(ctx, message, aligned);420message += aligned;421message_size -= aligned;422423// Process the message block by block424size_t nb_blocks = message_size >> 4;425FOR (i, 0, nb_blocks) {426load32_le_buf(ctx->c, message, 4);427poly_block(ctx);428message += 16;429}430if (nb_blocks > 0) {431poly_clear_c(ctx);432}433message_size &= 15;434435// remaining bytes436poly_update(ctx, message, message_size);437}438439void crypto_poly1305_final(crypto_poly1305_ctx *ctx, u8 mac[16])440{441// Process the last block (if any)442if (ctx->c_idx != 0) {443// move the final 1 according to remaining input length444// (We may add less than 2^130 to the last input block)445ctx->c[4] = 0;446poly_take_input(ctx, 1);447// one last hash update448poly_block(ctx);449}450451// check if we should subtract 2^130-5 by performing the452// corresponding carry propagation.453u64 c = 5;454FOR (i, 0, 4) {455c += ctx->h[i];456c >>= 32;457}458c += ctx->h[4];459c = (c >> 2) * 5; // shift the carry back to the beginning460// c now indicates how many times we should subtract 2^130-5 (0 or 1)461FOR (i, 0, 4) {462c += (u64)ctx->h[i] + ctx->pad[i];463store32_le(mac + i*4, (u32)c);464c = c >> 32;465}466WIPE_CTX(ctx);467}468469void crypto_poly1305(u8 mac[16], const u8 *message,470size_t message_size, const u8 key[32])471{472crypto_poly1305_ctx ctx;473crypto_poly1305_init (&ctx, key);474crypto_poly1305_update(&ctx, message, message_size);475crypto_poly1305_final (&ctx, mac);476}477478////////////////479/// Blake2 b ///480////////////////481static const u64 iv[8] = {4820x6a09e667f3bcc908, 0xbb67ae8584caa73b,4830x3c6ef372fe94f82b, 0xa54ff53a5f1d36f1,4840x510e527fade682d1, 0x9b05688c2b3e6c1f,4850x1f83d9abfb41bd6b, 0x5be0cd19137e2179,486};487488// increment the input offset489static void blake2b_incr(crypto_blake2b_ctx *ctx)490{491u64 *x = ctx->input_offset;492size_t y = ctx->input_idx;493x[0] += y;494if (x[0] < y) {495x[1]++;496}497}498499static void blake2b_compress(crypto_blake2b_ctx *ctx, int is_last_block)500{501static const u8 sigma[12][16] = {502{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },503{ 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 },504{ 11, 8, 12, 0, 5, 2, 15, 13, 10, 14, 3, 6, 7, 1, 9, 4 },505{ 7, 9, 3, 1, 13, 12, 11, 14, 2, 6, 5, 10, 4, 0, 15, 8 },506{ 9, 0, 5, 7, 2, 4, 10, 15, 14, 1, 11, 12, 6, 8, 3, 13 },507{ 2, 12, 6, 10, 0, 11, 8, 3, 4, 13, 7, 5, 15, 14, 1, 9 },508{ 12, 5, 1, 15, 14, 13, 4, 10, 0, 7, 6, 3, 9, 2, 8, 11 },509{ 13, 11, 7, 14, 12, 1, 3, 9, 5, 0, 15, 4, 8, 6, 2, 10 },510{ 6, 15, 14, 9, 11, 3, 0, 8, 12, 2, 13, 7, 1, 4, 10, 5 },511{ 10, 2, 8, 4, 7, 6, 1, 5, 15, 11, 9, 14, 3, 12, 13, 0 },512{ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15 },513{ 14, 10, 4, 8, 9, 15, 13, 6, 1, 12, 0, 2, 11, 7, 5, 3 },514};515516// init work vector517u64 v0 = ctx->hash[0]; u64 v8 = iv[0];518u64 v1 = ctx->hash[1]; u64 v9 = iv[1];519u64 v2 = ctx->hash[2]; u64 v10 = iv[2];520u64 v3 = ctx->hash[3]; u64 v11 = iv[3];521u64 v4 = ctx->hash[4]; u64 v12 = iv[4] ^ ctx->input_offset[0];522u64 v5 = ctx->hash[5]; u64 v13 = iv[5] ^ ctx->input_offset[1];523u64 v6 = ctx->hash[6]; u64 v14 = iv[6] ^ (u64)~(is_last_block - 1);524u64 v7 = ctx->hash[7]; u64 v15 = iv[7];525526// mangle work vector527u64 *input = ctx->input;528#define BLAKE2_G(a, b, c, d, x, y) \529a += b + x; d = rotr64(d ^ a, 32); \530c += d; b = rotr64(b ^ c, 24); \531a += b + y; d = rotr64(d ^ a, 16); \532c += d; b = rotr64(b ^ c, 63)533#define BLAKE2_ROUND(i) \534BLAKE2_G(v0, v4, v8 , v12, input[sigma[i][ 0]], input[sigma[i][ 1]]); \535BLAKE2_G(v1, v5, v9 , v13, input[sigma[i][ 2]], input[sigma[i][ 3]]); \536BLAKE2_G(v2, v6, v10, v14, input[sigma[i][ 4]], input[sigma[i][ 5]]); \537BLAKE2_G(v3, v7, v11, v15, input[sigma[i][ 6]], input[sigma[i][ 7]]); \538BLAKE2_G(v0, v5, v10, v15, input[sigma[i][ 8]], input[sigma[i][ 9]]); \539BLAKE2_G(v1, v6, v11, v12, input[sigma[i][10]], input[sigma[i][11]]); \540BLAKE2_G(v2, v7, v8 , v13, input[sigma[i][12]], input[sigma[i][13]]); \541BLAKE2_G(v3, v4, v9 , v14, input[sigma[i][14]], input[sigma[i][15]])542543#ifdef BLAKE2_NO_UNROLLING544FOR (i, 0, 12) {545BLAKE2_ROUND(i);546}547#else548BLAKE2_ROUND(0); BLAKE2_ROUND(1); BLAKE2_ROUND(2); BLAKE2_ROUND(3);549BLAKE2_ROUND(4); BLAKE2_ROUND(5); BLAKE2_ROUND(6); BLAKE2_ROUND(7);550BLAKE2_ROUND(8); BLAKE2_ROUND(9); BLAKE2_ROUND(10); BLAKE2_ROUND(11);551#endif552553// update hash554ctx->hash[0] ^= v0 ^ v8; ctx->hash[1] ^= v1 ^ v9;555ctx->hash[2] ^= v2 ^ v10; ctx->hash[3] ^= v3 ^ v11;556ctx->hash[4] ^= v4 ^ v12; ctx->hash[5] ^= v5 ^ v13;557ctx->hash[6] ^= v6 ^ v14; ctx->hash[7] ^= v7 ^ v15;558}559560static void blake2b_set_input(crypto_blake2b_ctx *ctx, u8 input, size_t index)561{562if (index == 0) {563ZERO(ctx->input, 16);564}565size_t word = index >> 3;566size_t byte = index & 7;567ctx->input[word] |= (u64)input << (byte << 3);568569}570571static void blake2b_end_block(crypto_blake2b_ctx *ctx)572{573if (ctx->input_idx == 128) { // If buffer is full,574blake2b_incr(ctx); // update the input offset575blake2b_compress(ctx, 0); // and compress the (not last) block576ctx->input_idx = 0;577}578}579580static void blake2b_update(crypto_blake2b_ctx *ctx,581const u8 *message, size_t message_size)582{583FOR (i, 0, message_size) {584blake2b_end_block(ctx);585blake2b_set_input(ctx, message[i], ctx->input_idx);586ctx->input_idx++;587}588}589590void crypto_blake2b_general_init(crypto_blake2b_ctx *ctx, size_t hash_size,591const u8 *key, size_t key_size)592{593// initial hash594COPY(ctx->hash, iv, 8);595ctx->hash[0] ^= 0x01010000 ^ (key_size << 8) ^ hash_size;596597ctx->input_offset[0] = 0; // beginning of the input, no offset598ctx->input_offset[1] = 0; // beginning of the input, no offset599ctx->hash_size = hash_size; // remember the hash size we want600ctx->input_idx = 0;601602// if there is a key, the first block is that key (padded with zeroes)603if (key_size > 0) {604u8 key_block[128] = {0};605COPY(key_block, key, key_size);606// same as calling crypto_blake2b_update(ctx, key_block , 128)607load64_le_buf(ctx->input, key_block, 16);608ctx->input_idx = 128;609}610}611612void crypto_blake2b_init(crypto_blake2b_ctx *ctx)613{614crypto_blake2b_general_init(ctx, 64, 0, 0);615}616617void crypto_blake2b_update(crypto_blake2b_ctx *ctx,618const u8 *message, size_t message_size)619{620if (message_size == 0) {621return;622}623// Align ourselves with block boundaries624size_t aligned = MIN(align(ctx->input_idx, 128), message_size);625blake2b_update(ctx, message, aligned);626message += aligned;627message_size -= aligned;628629// Process the message block by block630FOR (i, 0, message_size >> 7) { // number of blocks631blake2b_end_block(ctx);632load64_le_buf(ctx->input, message, 16);633message += 128;634ctx->input_idx = 128;635}636message_size &= 127;637638// remaining bytes639blake2b_update(ctx, message, message_size);640}641642void crypto_blake2b_final(crypto_blake2b_ctx *ctx, u8 *hash)643{644// Pad the end of the block with zeroes645FOR (i, ctx->input_idx, 128) {646blake2b_set_input(ctx, 0, i);647}648blake2b_incr(ctx); // update the input offset649blake2b_compress(ctx, 1); // compress the last block650size_t nb_words = ctx->hash_size >> 3;651store64_le_buf(hash, ctx->hash, nb_words);652FOR (i, nb_words << 3, ctx->hash_size) {653hash[i] = (ctx->hash[i >> 3] >> (8 * (i & 7))) & 0xff;654}655WIPE_CTX(ctx);656}657658void crypto_blake2b_general(u8 *hash , size_t hash_size,659const u8 *key , size_t key_size,660const u8 *message, size_t message_size)661{662crypto_blake2b_ctx ctx;663crypto_blake2b_general_init(&ctx, hash_size, key, key_size);664crypto_blake2b_update(&ctx, message, message_size);665crypto_blake2b_final(&ctx, hash);666}667668void crypto_blake2b(u8 hash[64], const u8 *message, size_t message_size)669{670crypto_blake2b_general(hash, 64, 0, 0, message, message_size);671}672673static void blake2b_vtable_init(void *ctx) {674crypto_blake2b_init(&((crypto_sign_ctx*)ctx)->hash);675}676static void blake2b_vtable_update(void *ctx, const u8 *m, size_t s) {677crypto_blake2b_update(&((crypto_sign_ctx*)ctx)->hash, m, s);678}679static void blake2b_vtable_final(void *ctx, u8 *h) {680crypto_blake2b_final(&((crypto_sign_ctx*)ctx)->hash, h);681}682const crypto_sign_vtable crypto_blake2b_vtable = {683crypto_blake2b,684blake2b_vtable_init,685blake2b_vtable_update,686blake2b_vtable_final,687sizeof(crypto_sign_ctx),688};689690#if MONOCYPHER_ARGON2_ENABLE691////////////////692/// Argon2 i ///693////////////////694// references to R, Z, Q etc. come from the spec695696// Argon2 operates on 1024 byte blocks.697typedef struct { u64 a[128]; } block;698699static void wipe_block(block *b)700{701volatile u64* a = b->a;702ZERO(a, 128);703}704705// updates a Blake2 hash with a 32 bit word, little endian.706static void blake_update_32(crypto_blake2b_ctx *ctx, u32 input)707{708u8 buf[4];709store32_le(buf, input);710crypto_blake2b_update(ctx, buf, 4);711WIPE_BUFFER(buf);712}713714static void load_block(block *b, const u8 bytes[1024])715{716load64_le_buf(b->a, bytes, 128);717}718719static void store_block(u8 bytes[1024], const block *b)720{721store64_le_buf(bytes, b->a, 128);722}723724static void copy_block(block *o,const block*in){FOR(i,0,128)o->a[i] = in->a[i];}725static void xor_block(block *o,const block*in){FOR(i,0,128)o->a[i]^= in->a[i];}726727// Hash with a virtually unlimited digest size.728// Doesn't extract more entropy than the base hash function.729// Mainly used for filling a whole kilobyte block with pseudo-random bytes.730// (One could use a stream cipher with a seed hash as the key, but731// this would introduce another dependency —and point of failure.)732static void extended_hash(u8 *digest, u32 digest_size,733const u8 *input , u32 input_size)734{735crypto_blake2b_ctx ctx;736crypto_blake2b_general_init(&ctx, MIN(digest_size, 64), 0, 0);737blake_update_32 (&ctx, digest_size);738crypto_blake2b_update (&ctx, input, input_size);739crypto_blake2b_final (&ctx, digest);740741if (digest_size > 64) {742// the conversion to u64 avoids integer overflow on743// ludicrously big hash sizes.744u32 r = (u32)(((u64)digest_size + 31) >> 5) - 2;745u32 i = 1;746u32 in = 0;747u32 out = 32;748while (i < r) {749// Input and output overlap. This is intentional750crypto_blake2b(digest + out, digest + in, 64);751i += 1;752in += 32;753out += 32;754}755crypto_blake2b_general(digest + out, digest_size - (32 * r),7560, 0, // no key757digest + in , 64);758}759}760761#define LSB(x) ((x) & 0xffffffff)762#define G(a, b, c, d) \763a += b + 2 * LSB(a) * LSB(b); d ^= a; d = rotr64(d, 32); \764c += d + 2 * LSB(c) * LSB(d); b ^= c; b = rotr64(b, 24); \765a += b + 2 * LSB(a) * LSB(b); d ^= a; d = rotr64(d, 16); \766c += d + 2 * LSB(c) * LSB(d); b ^= c; b = rotr64(b, 63)767#define ROUND(v0, v1, v2, v3, v4, v5, v6, v7, \768v8, v9, v10, v11, v12, v13, v14, v15) \769G(v0, v4, v8, v12); G(v1, v5, v9, v13); \770G(v2, v6, v10, v14); G(v3, v7, v11, v15); \771G(v0, v5, v10, v15); G(v1, v6, v11, v12); \772G(v2, v7, v8, v13); G(v3, v4, v9, v14)773774// Core of the compression function G. Computes Z from R in place.775static void g_rounds(block *work_block)776{777// column rounds (work_block = Q)778for (int i = 0; i < 128; i += 16) {779ROUND(work_block->a[i ], work_block->a[i + 1],780work_block->a[i + 2], work_block->a[i + 3],781work_block->a[i + 4], work_block->a[i + 5],782work_block->a[i + 6], work_block->a[i + 7],783work_block->a[i + 8], work_block->a[i + 9],784work_block->a[i + 10], work_block->a[i + 11],785work_block->a[i + 12], work_block->a[i + 13],786work_block->a[i + 14], work_block->a[i + 15]);787}788// row rounds (work_block = Z)789for (int i = 0; i < 16; i += 2) {790ROUND(work_block->a[i ], work_block->a[i + 1],791work_block->a[i + 16], work_block->a[i + 17],792work_block->a[i + 32], work_block->a[i + 33],793work_block->a[i + 48], work_block->a[i + 49],794work_block->a[i + 64], work_block->a[i + 65],795work_block->a[i + 80], work_block->a[i + 81],796work_block->a[i + 96], work_block->a[i + 97],797work_block->a[i + 112], work_block->a[i + 113]);798}799}800801// The compression function G (copy version for the first pass)802static void g_copy(block *result, const block *x, const block *y, block* tmp)803{804copy_block(tmp , x ); // tmp = X805xor_block (tmp , y ); // tmp = X ^ Y = R806copy_block(result, tmp); // result = R (only difference with g_xor)807g_rounds (tmp); // tmp = Z808xor_block (result, tmp); // result = R ^ Z809}810811// The compression function G (xor version for subsequent passes)812static void g_xor(block *result, const block *x, const block *y, block *tmp)813{814copy_block(tmp , x ); // tmp = X815xor_block (tmp , y ); // tmp = X ^ Y = R816xor_block (result, tmp); // result = R ^ old (only difference with g_copy)817g_rounds (tmp); // tmp = Z818xor_block (result, tmp); // result = R ^ old ^ Z819}820821// Unary version of the compression function.822// The missing argument is implied zero.823// Does the transformation in place.824static void unary_g(block *work_block, block *tmp)825{826// work_block == R827copy_block(tmp, work_block); // tmp = R828g_rounds (work_block); // work_block = Z829xor_block (work_block, tmp); // work_block = Z ^ R830}831832// Argon2i uses a kind of stream cipher to determine which reference833// block it will take to synthesise the next block. This context hold834// that stream's state. (It's very similar to Chacha20. The block b835// is analogous to Chacha's own pool)836typedef struct {837block b;838u32 pass_number;839u32 slice_number;840u32 nb_blocks;841u32 nb_iterations;842u32 ctr;843u32 offset;844} gidx_ctx;845846// The block in the context will determine array indices. To avoid847// timing attacks, it only depends on public information. No looking848// at a previous block to seed the next. This makes offline attacks849// easier, but timing attacks are the bigger threat in many settings.850static void gidx_refresh(gidx_ctx *ctx)851{852// seed the beginning of the block...853ctx->b.a[0] = ctx->pass_number;854ctx->b.a[1] = 0; // lane number (we have only one)855ctx->b.a[2] = ctx->slice_number;856ctx->b.a[3] = ctx->nb_blocks;857ctx->b.a[4] = ctx->nb_iterations;858ctx->b.a[5] = 1; // type: Argon2i859ctx->b.a[6] = ctx->ctr;860ZERO(ctx->b.a + 7, 121); // ...then zero the rest out861862// Shuffle the block thus: ctx->b = G((G(ctx->b, zero)), zero)863// (G "square" function), to get cheap pseudo-random numbers.864block tmp;865unary_g(&ctx->b, &tmp);866unary_g(&ctx->b, &tmp);867wipe_block(&tmp);868}869870static void gidx_init(gidx_ctx *ctx,871u32 pass_number, u32 slice_number,872u32 nb_blocks, u32 nb_iterations)873{874ctx->pass_number = pass_number;875ctx->slice_number = slice_number;876ctx->nb_blocks = nb_blocks;877ctx->nb_iterations = nb_iterations;878ctx->ctr = 0;879880// Offset from the beginning of the segment. For the first slice881// of the first pass, we start at the *third* block, so the offset882// starts at 2, not 0.883if (pass_number != 0 || slice_number != 0) {884ctx->offset = 0;885} else {886ctx->offset = 2;887ctx->ctr++; // Compensates for missed lazy creation888gidx_refresh(ctx); // at the start of gidx_next()889}890}891892static u32 gidx_next(gidx_ctx *ctx)893{894// lazily creates the offset block we need895if ((ctx->offset & 127) == 0) {896ctx->ctr++;897gidx_refresh(ctx);898}899u32 index = ctx->offset & 127; // save index for current call900u32 offset = ctx->offset; // save offset for current call901ctx->offset++; // update offset for next call902903// Computes the area size.904// Pass 0 : all already finished segments plus already constructed905// blocks in this segment906// Pass 1+: 3 last segments plus already constructed907// blocks in this segment. THE SPEC SUGGESTS OTHERWISE.908// I CONFORM TO THE REFERENCE IMPLEMENTATION.909int first_pass = ctx->pass_number == 0;910u32 slice_size = ctx->nb_blocks >> 2;911u32 nb_segments = first_pass ? ctx->slice_number : 3;912u32 area_size = nb_segments * slice_size + offset - 1;913914// Computes the starting position of the reference area.915// CONTRARY TO WHAT THE SPEC SUGGESTS, IT STARTS AT THE916// NEXT SEGMENT, NOT THE NEXT BLOCK.917u32 next_slice = ((ctx->slice_number + 1) & 3) * slice_size;918u32 start_pos = first_pass ? 0 : next_slice;919920// Generate offset from J1 (no need for J2, there's only one lane)921u64 j1 = ctx->b.a[index] & 0xffffffff; // pseudo-random number922u64 x = (j1 * j1) >> 32;923u64 y = (area_size * x) >> 32;924u64 z = (area_size - 1) - y;925u64 ref = start_pos + z; // ref < 2 * nb_blocks926return (u32)(ref < ctx->nb_blocks ? ref : ref - ctx->nb_blocks);927}928929// Main algorithm930void crypto_argon2i_general(u8 *hash, u32 hash_size,931void *work_area, u32 nb_blocks,932u32 nb_iterations,933const u8 *password, u32 password_size,934const u8 *salt, u32 salt_size,935const u8 *key, u32 key_size,936const u8 *ad, u32 ad_size)937{938// work area seen as blocks (must be suitably aligned)939block *blocks = (block*)work_area;940{941crypto_blake2b_ctx ctx;942crypto_blake2b_init(&ctx);943944blake_update_32 (&ctx, 1 ); // p: number of threads945blake_update_32 (&ctx, hash_size );946blake_update_32 (&ctx, nb_blocks );947blake_update_32 (&ctx, nb_iterations);948blake_update_32 (&ctx, 0x13 ); // v: version number949blake_update_32 (&ctx, 1 ); // y: Argon2i950blake_update_32 (&ctx, password_size);951crypto_blake2b_update(&ctx, password, password_size);952blake_update_32 (&ctx, salt_size);953crypto_blake2b_update(&ctx, salt, salt_size);954blake_update_32 (&ctx, key_size);955crypto_blake2b_update(&ctx, key, key_size);956blake_update_32 (&ctx, ad_size);957crypto_blake2b_update(&ctx, ad, ad_size);958959u8 initial_hash[72]; // 64 bytes plus 2 words for future hashes960crypto_blake2b_final(&ctx, initial_hash);961962// fill first 2 blocks963block tmp_block;964u8 hash_area[1024];965store32_le(initial_hash + 64, 0); // first additional word966store32_le(initial_hash + 68, 0); // second additional word967extended_hash(hash_area, 1024, initial_hash, 72);968load_block(&tmp_block, hash_area);969copy_block(blocks, &tmp_block);970971store32_le(initial_hash + 64, 1); // slight modification972extended_hash(hash_area, 1024, initial_hash, 72);973load_block(&tmp_block, hash_area);974copy_block(blocks + 1, &tmp_block);975976WIPE_BUFFER(initial_hash);977WIPE_BUFFER(hash_area);978wipe_block(&tmp_block);979}980981// Actual number of blocks982nb_blocks -= nb_blocks & 3; // round down to 4 p (p == 1 thread)983const u32 segment_size = nb_blocks >> 2;984985// fill (then re-fill) the rest of the blocks986block tmp;987gidx_ctx ctx; // public information, no need to wipe988FOR_T (u32, pass_number, 0, nb_iterations) {989int first_pass = pass_number == 0;990991FOR_T (u32, segment, 0, 4) {992gidx_init(&ctx, pass_number, segment, nb_blocks, nb_iterations);993994// On the first segment of the first pass,995// blocks 0 and 1 are already filled.996// We use the offset to skip them.997u32 start_offset = first_pass && segment == 0 ? 2 : 0;998u32 segment_start = segment * segment_size + start_offset;999u32 segment_end = (segment + 1) * segment_size;1000FOR_T (u32, current_block, segment_start, segment_end) {1001u32 reference_block = gidx_next(&ctx);1002u32 previous_block = current_block == 01003? nb_blocks - 11004: current_block - 1;1005block *c = blocks + current_block;1006block *p = blocks + previous_block;1007block *r = blocks + reference_block;1008if (first_pass) { g_copy(c, p, r, &tmp); }1009else { g_xor (c, p, r, &tmp); }1010}1011}1012}1013wipe_block(&tmp);1014u8 final_block[1024];1015store_block(final_block, blocks + (nb_blocks - 1));10161017// wipe work area1018volatile u64 *p = (u64*)work_area;1019ZERO(p, 128 * nb_blocks);10201021// hash the very last block with H' into the output hash1022extended_hash(hash, hash_size, final_block, 1024);1023WIPE_BUFFER(final_block);1024}10251026void crypto_argon2i(u8 *hash, u32 hash_size,1027void *work_area, u32 nb_blocks, u32 nb_iterations,1028const u8 *password, u32 password_size,1029const u8 *salt, u32 salt_size)1030{1031crypto_argon2i_general(hash, hash_size, work_area, nb_blocks, nb_iterations,1032password, password_size, salt , salt_size, 0,0,0,0);1033}10341035#endif // MONOCYPHER_ARGON2_ENABLE10361037////////////////////////////////////1038/// Arithmetic modulo 2^255 - 19 ///1039////////////////////////////////////1040// Originally taken from SUPERCOP's ref10 implementation.1041// A bit bigger than TweetNaCl, over 4 times faster.10421043// field element1044typedef i32 fe[10];10451046// field constants1047//1048// fe_one : 11049// sqrtm1 : sqrt(-1)1050// d : -121665 / 1216661051// D2 : 2 * -121665 / 1216661052// lop_x, lop_y: low order point in Edwards coordinates1053// ufactor : -sqrt(-1) * 21054// A2 : 486662^2 (A squared)1055static const fe fe_one = {1};1056static const fe sqrtm1 = {-32595792, -7943725, 9377950, 3500415, 12389472,1057-272473, -25146209, -2005654, 326686, 11406482,};1058static const fe d = {-10913610, 13857413, -15372611, 6949391, 114729,1059-8787816, -6275908, -3247719, -18696448, -12055116,};1060static const fe D2 = {-21827239, -5839606, -30745221, 13898782, 229458,106115978800, -12551817, -6495438, 29715968, 9444199,};1062static const fe lop_x = {21352778, 5345713, 4660180, -8347857, 24143090,106314568123, 30185756, -12247770, -33528939, 8345319,};1064static const fe lop_y = {-6952922, -1265500, 6862341, -7057498, -4037696,1065-5447722, 31680899, -15325402, -19365852, 1569102,};1066static const fe ufactor = {-1917299, 15887451, -18755900, -7000830, -24778944,1067544946, -16816446, 4011309, -653372, 10741468,};1068static const fe A2 = {12721188, 3529, 0, 0, 0, 0, 0, 0, 0, 0,};10691070static void fe_0(fe h) { ZERO(h , 10); }1071static void fe_1(fe h) { h[0] = 1; ZERO(h+1, 9); }10721073static void fe_copy(fe h,const fe f ){FOR(i,0,10) h[i] = f[i]; }1074static void fe_neg (fe h,const fe f ){FOR(i,0,10) h[i] = -f[i]; }1075static void fe_add (fe h,const fe f,const fe g){FOR(i,0,10) h[i] = f[i] + g[i];}1076static void fe_sub (fe h,const fe f,const fe g){FOR(i,0,10) h[i] = f[i] - g[i];}10771078static void fe_cswap(fe f, fe g, int b)1079{1080i32 mask = -b; // -1 = 0xffffffff1081FOR (i, 0, 10) {1082i32 x = (f[i] ^ g[i]) & mask;1083f[i] = f[i] ^ x;1084g[i] = g[i] ^ x;1085}1086}10871088static void fe_ccopy(fe f, const fe g, int b)1089{1090i32 mask = -b; // -1 = 0xffffffff1091FOR (i, 0, 10) {1092i32 x = (f[i] ^ g[i]) & mask;1093f[i] = f[i] ^ x;1094}1095}109610971098// Signed carry propagation1099// ------------------------1100//1101// Let t be a number. It can be uniquely decomposed thus:1102//1103// t = h*2^26 + l1104// such that -2^25 <= l < 2^251105//1106// Let c = (t + 2^25) / 2^26 (rounded down)1107// c = (h*2^26 + l + 2^25) / 2^26 (rounded down)1108// c = h + (l + 2^25) / 2^26 (rounded down)1109// c = h (exactly)1110// Because 0 <= l + 2^25 < 2^261111//1112// Let u = t - c*2^261113// u = h*2^26 + l - h*2^261114// u = l1115// Therefore, -2^25 <= u < 2^251116//1117// Additionally, if |t| < x, then |h| < x/2^26 (rounded down)1118//1119// Notations:1120// - In C, 1<<25 means 2^25.1121// - In C, x>>25 means floor(x / (2^25)).1122// - All of the above applies with 25 & 24 as well as 26 & 25.1123//1124//1125// Note on negative right shifts1126// -----------------------------1127//1128// In C, x >> n, where x is a negative integer, is implementation1129// defined. In practice, all platforms do arithmetic shift, which is1130// equivalent to division by 2^26, rounded down. Some compilers, like1131// GCC, even guarantee it.1132//1133// If we ever stumble upon a platform that does not propagate the sign1134// bit (we won't), visible failures will show at the slightest test, and1135// the signed shifts can be replaced by the following:1136//1137// typedef struct { i64 x:39; } s25;1138// typedef struct { i64 x:38; } s26;1139// i64 shift25(i64 x) { s25 s; s.x = ((u64)x)>>25; return s.x; }1140// i64 shift26(i64 x) { s26 s; s.x = ((u64)x)>>26; return s.x; }1141//1142// Current compilers cannot optimise this, causing a 30% drop in1143// performance. Fairly expensive for something that never happens.1144//1145//1146// Precondition1147// ------------1148//1149// |t0| < 2^631150// |t1|..|t9| < 2^621151//1152// Algorithm1153// ---------1154// c = t0 + 2^25 / 2^26 -- |c| <= 2^361155// t0 -= c * 2^26 -- |t0| <= 2^251156// t1 += c -- |t1| <= 2^631157//1158// c = t4 + 2^25 / 2^26 -- |c| <= 2^361159// t4 -= c * 2^26 -- |t4| <= 2^251160// t5 += c -- |t5| <= 2^631161//1162// c = t1 + 2^24 / 2^25 -- |c| <= 2^381163// t1 -= c * 2^25 -- |t1| <= 2^241164// t2 += c -- |t2| <= 2^631165//1166// c = t5 + 2^24 / 2^25 -- |c| <= 2^381167// t5 -= c * 2^25 -- |t5| <= 2^241168// t6 += c -- |t6| <= 2^631169//1170// c = t2 + 2^25 / 2^26 -- |c| <= 2^371171// t2 -= c * 2^26 -- |t2| <= 2^25 < 1.1 * 2^25 (final t2)1172// t3 += c -- |t3| <= 2^631173//1174// c = t6 + 2^25 / 2^26 -- |c| <= 2^371175// t6 -= c * 2^26 -- |t6| <= 2^25 < 1.1 * 2^25 (final t6)1176// t7 += c -- |t7| <= 2^631177//1178// c = t3 + 2^24 / 2^25 -- |c| <= 2^381179// t3 -= c * 2^25 -- |t3| <= 2^24 < 1.1 * 2^24 (final t3)1180// t4 += c -- |t4| <= 2^25 + 2^38 < 2^391181//1182// c = t7 + 2^24 / 2^25 -- |c| <= 2^381183// t7 -= c * 2^25 -- |t7| <= 2^24 < 1.1 * 2^24 (final t7)1184// t8 += c -- |t8| <= 2^631185//1186// c = t4 + 2^25 / 2^26 -- |c| <= 2^131187// t4 -= c * 2^26 -- |t4| <= 2^25 < 1.1 * 2^25 (final t4)1188// t5 += c -- |t5| <= 2^24 + 2^13 < 1.1 * 2^24 (final t5)1189//1190// c = t8 + 2^25 / 2^26 -- |c| <= 2^371191// t8 -= c * 2^26 -- |t8| <= 2^25 < 1.1 * 2^25 (final t8)1192// t9 += c -- |t9| <= 2^631193//1194// c = t9 + 2^24 / 2^25 -- |c| <= 2^381195// t9 -= c * 2^25 -- |t9| <= 2^24 < 1.1 * 2^24 (final t9)1196// t0 += c * 19 -- |t0| <= 2^25 + 2^38*19 < 2^441197//1198// c = t0 + 2^25 / 2^26 -- |c| <= 2^181199// t0 -= c * 2^26 -- |t0| <= 2^25 < 1.1 * 2^25 (final t0)1200// t1 += c -- |t1| <= 2^24 + 2^18 < 1.1 * 2^24 (final t1)1201//1202// Postcondition1203// -------------1204// |t0|, |t2|, |t4|, |t6|, |t8| < 1.1 * 2^251205// |t1|, |t3|, |t5|, |t7|, |t9| < 1.1 * 2^241206#define FE_CARRY \1207i64 c; \1208c = (t0 + ((i64)1<<25)) >> 26; t0 -= c * ((i64)1 << 26); t1 += c; \1209c = (t4 + ((i64)1<<25)) >> 26; t4 -= c * ((i64)1 << 26); t5 += c; \1210c = (t1 + ((i64)1<<24)) >> 25; t1 -= c * ((i64)1 << 25); t2 += c; \1211c = (t5 + ((i64)1<<24)) >> 25; t5 -= c * ((i64)1 << 25); t6 += c; \1212c = (t2 + ((i64)1<<25)) >> 26; t2 -= c * ((i64)1 << 26); t3 += c; \1213c = (t6 + ((i64)1<<25)) >> 26; t6 -= c * ((i64)1 << 26); t7 += c; \1214c = (t3 + ((i64)1<<24)) >> 25; t3 -= c * ((i64)1 << 25); t4 += c; \1215c = (t7 + ((i64)1<<24)) >> 25; t7 -= c * ((i64)1 << 25); t8 += c; \1216c = (t4 + ((i64)1<<25)) >> 26; t4 -= c * ((i64)1 << 26); t5 += c; \1217c = (t8 + ((i64)1<<25)) >> 26; t8 -= c * ((i64)1 << 26); t9 += c; \1218c = (t9 + ((i64)1<<24)) >> 25; t9 -= c * ((i64)1 << 25); t0 += c * 19; \1219c = (t0 + ((i64)1<<25)) >> 26; t0 -= c * ((i64)1 << 26); t1 += c; \1220h[0]=(i32)t0; h[1]=(i32)t1; h[2]=(i32)t2; h[3]=(i32)t3; h[4]=(i32)t4; \1221h[5]=(i32)t5; h[6]=(i32)t6; h[7]=(i32)t7; h[8]=(i32)t8; h[9]=(i32)t912221223static void fe_frombytes(fe h, const u8 s[32])1224{1225i64 t0 = load32_le(s); // t0 < 2^321226i64 t1 = load24_le(s + 4) << 6; // t1 < 2^301227i64 t2 = load24_le(s + 7) << 5; // t2 < 2^291228i64 t3 = load24_le(s + 10) << 3; // t3 < 2^271229i64 t4 = load24_le(s + 13) << 2; // t4 < 2^261230i64 t5 = load32_le(s + 16); // t5 < 2^321231i64 t6 = load24_le(s + 20) << 7; // t6 < 2^311232i64 t7 = load24_le(s + 23) << 5; // t7 < 2^291233i64 t8 = load24_le(s + 26) << 4; // t8 < 2^281234i64 t9 = (load24_le(s + 29) & 0x7fffff) << 2; // t9 < 2^251235FE_CARRY; // Carry recondition OK1236}12371238// Precondition1239// |h[0]|, |h[2]|, |h[4]|, |h[6]|, |h[8]| < 1.1 * 2^251240// |h[1]|, |h[3]|, |h[5]|, |h[7]|, |h[9]| < 1.1 * 2^241241//1242// Therefore, |h| < 2^255-191243// There are two possibilities:1244//1245// - If h is positive, all we need to do is reduce its individual1246// limbs down to their tight positive range.1247// - If h is negative, we also need to add 2^255-19 to it.1248// Or just remove 19 and chop off any excess bit.1249static void fe_tobytes(u8 s[32], const fe h)1250{1251i32 t[10];1252COPY(t, h, 10);1253i32 q = (19 * t[9] + (((i32) 1) << 24)) >> 25;1254// |t9| < 1.1 * 2^241255// -1.1 * 2^24 < t9 < 1.1 * 2^241256// -21 * 2^24 < 19 * t9 < 21 * 2^241257// -2^29 < 19 * t9 + 2^24 < 2^291258// -2^29 / 2^25 < (19 * t9 + 2^24) / 2^25 < 2^29 / 2^251259// -16 < (19 * t9 + 2^24) / 2^25 < 161260FOR (i, 0, 5) {1261q += t[2*i ]; q >>= 26; // q = 0 or -11262q += t[2*i+1]; q >>= 25; // q = 0 or -11263}1264// q = 0 iff h >= 01265// q = -1 iff h < 01266// Adding q * 19 to h reduces h to its proper range.1267q *= 19; // Shift carry back to the beginning1268FOR (i, 0, 5) {1269t[i*2 ] += q; q = t[i*2 ] >> 26; t[i*2 ] -= q * ((i32)1 << 26);1270t[i*2+1] += q; q = t[i*2+1] >> 25; t[i*2+1] -= q * ((i32)1 << 25);1271}1272// h is now fully reduced, and q represents the excess bit.12731274store32_le(s + 0, ((u32)t[0] >> 0) | ((u32)t[1] << 26));1275store32_le(s + 4, ((u32)t[1] >> 6) | ((u32)t[2] << 19));1276store32_le(s + 8, ((u32)t[2] >> 13) | ((u32)t[3] << 13));1277store32_le(s + 12, ((u32)t[3] >> 19) | ((u32)t[4] << 6));1278store32_le(s + 16, ((u32)t[5] >> 0) | ((u32)t[6] << 25));1279store32_le(s + 20, ((u32)t[6] >> 7) | ((u32)t[7] << 19));1280store32_le(s + 24, ((u32)t[7] >> 13) | ((u32)t[8] << 12));1281store32_le(s + 28, ((u32)t[8] >> 20) | ((u32)t[9] << 6));12821283WIPE_BUFFER(t);1284}12851286// Precondition1287// -------------1288// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^261289// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^251290//1291// |g0|, |g2|, |g4|, |g6|, |g8| < 1.65 * 2^261292// |g1|, |g3|, |g5|, |g7|, |g9| < 1.65 * 2^251293static void fe_mul_small(fe h, const fe f, i32 g)1294{1295i64 t0 = f[0] * (i64) g; i64 t1 = f[1] * (i64) g;1296i64 t2 = f[2] * (i64) g; i64 t3 = f[3] * (i64) g;1297i64 t4 = f[4] * (i64) g; i64 t5 = f[5] * (i64) g;1298i64 t6 = f[6] * (i64) g; i64 t7 = f[7] * (i64) g;1299i64 t8 = f[8] * (i64) g; i64 t9 = f[9] * (i64) g;1300// |t0|, |t2|, |t4|, |t6|, |t8| < 1.65 * 2^26 * 2^31 < 2^581301// |t1|, |t3|, |t5|, |t7|, |t9| < 1.65 * 2^25 * 2^31 < 2^5713021303FE_CARRY; // Carry precondition OK1304}13051306// Precondition1307// -------------1308// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^261309// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^251310//1311// |g0|, |g2|, |g4|, |g6|, |g8| < 1.65 * 2^261312// |g1|, |g3|, |g5|, |g7|, |g9| < 1.65 * 2^251313static void fe_mul(fe h, const fe f, const fe g)1314{1315// Everything is unrolled and put in temporary variables.1316// We could roll the loop, but that would make curve25519 twice as slow.1317i32 f0 = f[0]; i32 f1 = f[1]; i32 f2 = f[2]; i32 f3 = f[3]; i32 f4 = f[4];1318i32 f5 = f[5]; i32 f6 = f[6]; i32 f7 = f[7]; i32 f8 = f[8]; i32 f9 = f[9];1319i32 g0 = g[0]; i32 g1 = g[1]; i32 g2 = g[2]; i32 g3 = g[3]; i32 g4 = g[4];1320i32 g5 = g[5]; i32 g6 = g[6]; i32 g7 = g[7]; i32 g8 = g[8]; i32 g9 = g[9];1321i32 F1 = f1*2; i32 F3 = f3*2; i32 F5 = f5*2; i32 F7 = f7*2; i32 F9 = f9*2;1322i32 G1 = g1*19; i32 G2 = g2*19; i32 G3 = g3*19;1323i32 G4 = g4*19; i32 G5 = g5*19; i32 G6 = g6*19;1324i32 G7 = g7*19; i32 G8 = g8*19; i32 G9 = g9*19;1325// |F1|, |F3|, |F5|, |F7|, |F9| < 1.65 * 2^261326// |G0|, |G2|, |G4|, |G6|, |G8| < 2^311327// |G1|, |G3|, |G5|, |G7|, |G9| < 2^3013281329i64 t0 = f0*(i64)g0 + F1*(i64)G9 + f2*(i64)G8 + F3*(i64)G7 + f4*(i64)G61330+ F5*(i64)G5 + f6*(i64)G4 + F7*(i64)G3 + f8*(i64)G2 + F9*(i64)G1;1331i64 t1 = f0*(i64)g1 + f1*(i64)g0 + f2*(i64)G9 + f3*(i64)G8 + f4*(i64)G71332+ f5*(i64)G6 + f6*(i64)G5 + f7*(i64)G4 + f8*(i64)G3 + f9*(i64)G2;1333i64 t2 = f0*(i64)g2 + F1*(i64)g1 + f2*(i64)g0 + F3*(i64)G9 + f4*(i64)G81334+ F5*(i64)G7 + f6*(i64)G6 + F7*(i64)G5 + f8*(i64)G4 + F9*(i64)G3;1335i64 t3 = f0*(i64)g3 + f1*(i64)g2 + f2*(i64)g1 + f3*(i64)g0 + f4*(i64)G91336+ f5*(i64)G8 + f6*(i64)G7 + f7*(i64)G6 + f8*(i64)G5 + f9*(i64)G4;1337i64 t4 = f0*(i64)g4 + F1*(i64)g3 + f2*(i64)g2 + F3*(i64)g1 + f4*(i64)g01338+ F5*(i64)G9 + f6*(i64)G8 + F7*(i64)G7 + f8*(i64)G6 + F9*(i64)G5;1339i64 t5 = f0*(i64)g5 + f1*(i64)g4 + f2*(i64)g3 + f3*(i64)g2 + f4*(i64)g11340+ f5*(i64)g0 + f6*(i64)G9 + f7*(i64)G8 + f8*(i64)G7 + f9*(i64)G6;1341i64 t6 = f0*(i64)g6 + F1*(i64)g5 + f2*(i64)g4 + F3*(i64)g3 + f4*(i64)g21342+ F5*(i64)g1 + f6*(i64)g0 + F7*(i64)G9 + f8*(i64)G8 + F9*(i64)G7;1343i64 t7 = f0*(i64)g7 + f1*(i64)g6 + f2*(i64)g5 + f3*(i64)g4 + f4*(i64)g31344+ f5*(i64)g2 + f6*(i64)g1 + f7*(i64)g0 + f8*(i64)G9 + f9*(i64)G8;1345i64 t8 = f0*(i64)g8 + F1*(i64)g7 + f2*(i64)g6 + F3*(i64)g5 + f4*(i64)g41346+ F5*(i64)g3 + f6*(i64)g2 + F7*(i64)g1 + f8*(i64)g0 + F9*(i64)G9;1347i64 t9 = f0*(i64)g9 + f1*(i64)g8 + f2*(i64)g7 + f3*(i64)g6 + f4*(i64)g51348+ f5*(i64)g4 + f6*(i64)g3 + f7*(i64)g2 + f8*(i64)g1 + f9*(i64)g0;1349// t0 < 0.67 * 2^611350// t1 < 0.41 * 2^611351// t2 < 0.52 * 2^611352// t3 < 0.32 * 2^611353// t4 < 0.38 * 2^611354// t5 < 0.22 * 2^611355// t6 < 0.23 * 2^611356// t7 < 0.13 * 2^611357// t8 < 0.09 * 2^611358// t9 < 0.03 * 2^6113591360FE_CARRY; // Everything below 2^62, Carry precondition OK1361}13621363// Precondition1364// -------------1365// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^261366// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^251367//1368// Note: we could use fe_mul() for this, but this is significantly faster1369static void fe_sq(fe h, const fe f)1370{1371i32 f0 = f[0]; i32 f1 = f[1]; i32 f2 = f[2]; i32 f3 = f[3]; i32 f4 = f[4];1372i32 f5 = f[5]; i32 f6 = f[6]; i32 f7 = f[7]; i32 f8 = f[8]; i32 f9 = f[9];1373i32 f0_2 = f0*2; i32 f1_2 = f1*2; i32 f2_2 = f2*2; i32 f3_2 = f3*2;1374i32 f4_2 = f4*2; i32 f5_2 = f5*2; i32 f6_2 = f6*2; i32 f7_2 = f7*2;1375i32 f5_38 = f5*38; i32 f6_19 = f6*19; i32 f7_38 = f7*38;1376i32 f8_19 = f8*19; i32 f9_38 = f9*38;1377// |f0_2| , |f2_2| , |f4_2| , |f6_2| , |f8_2| < 1.65 * 2^271378// |f1_2| , |f3_2| , |f5_2| , |f7_2| , |f9_2| < 1.65 * 2^261379// |f5_38|, |f6_19|, |f7_38|, |f8_19|, |f9_38| < 2^3113801381i64 t0 = f0 *(i64)f0 + f1_2*(i64)f9_38 + f2_2*(i64)f8_191382+ f3_2*(i64)f7_38 + f4_2*(i64)f6_19 + f5 *(i64)f5_38;1383i64 t1 = f0_2*(i64)f1 + f2 *(i64)f9_38 + f3_2*(i64)f8_191384+ f4 *(i64)f7_38 + f5_2*(i64)f6_19;1385i64 t2 = f0_2*(i64)f2 + f1_2*(i64)f1 + f3_2*(i64)f9_381386+ f4_2*(i64)f8_19 + f5_2*(i64)f7_38 + f6 *(i64)f6_19;1387i64 t3 = f0_2*(i64)f3 + f1_2*(i64)f2 + f4 *(i64)f9_381388+ f5_2*(i64)f8_19 + f6 *(i64)f7_38;1389i64 t4 = f0_2*(i64)f4 + f1_2*(i64)f3_2 + f2 *(i64)f21390+ f5_2*(i64)f9_38 + f6_2*(i64)f8_19 + f7 *(i64)f7_38;1391i64 t5 = f0_2*(i64)f5 + f1_2*(i64)f4 + f2_2*(i64)f31392+ f6 *(i64)f9_38 + f7_2*(i64)f8_19;1393i64 t6 = f0_2*(i64)f6 + f1_2*(i64)f5_2 + f2_2*(i64)f41394+ f3_2*(i64)f3 + f7_2*(i64)f9_38 + f8 *(i64)f8_19;1395i64 t7 = f0_2*(i64)f7 + f1_2*(i64)f6 + f2_2*(i64)f51396+ f3_2*(i64)f4 + f8 *(i64)f9_38;1397i64 t8 = f0_2*(i64)f8 + f1_2*(i64)f7_2 + f2_2*(i64)f61398+ f3_2*(i64)f5_2 + f4 *(i64)f4 + f9 *(i64)f9_38;1399i64 t9 = f0_2*(i64)f9 + f1_2*(i64)f8 + f2_2*(i64)f71400+ f3_2*(i64)f6 + f4 *(i64)f5_2;1401// t0 < 0.67 * 2^611402// t1 < 0.41 * 2^611403// t2 < 0.52 * 2^611404// t3 < 0.32 * 2^611405// t4 < 0.38 * 2^611406// t5 < 0.22 * 2^611407// t6 < 0.23 * 2^611408// t7 < 0.13 * 2^611409// t8 < 0.09 * 2^611410// t9 < 0.03 * 2^6114111412FE_CARRY;1413}14141415// h = 2 * (f^2)1416//1417// Precondition1418// -------------1419// |f0|, |f2|, |f4|, |f6|, |f8| < 1.65 * 2^261420// |f1|, |f3|, |f5|, |f7|, |f9| < 1.65 * 2^251421//1422// Note: we could implement fe_sq2() by copying fe_sq(), multiplying1423// each limb by 2, *then* perform the carry. This saves one carry.1424// However, doing so with the stated preconditions does not work (t21425// would overflow). There are 3 ways to solve this:1426//1427// 1. Show that t2 actually never overflows (it really does not).1428// 2. Accept an additional carry, at a small lost of performance.1429// 3. Make sure the input of fe_sq2() is freshly carried.1430//1431// SUPERCOP ref10 relies on (1).1432// Monocypher chose (2) and (3), mostly to save code.1433static void fe_sq2(fe h, const fe f)1434{1435fe_sq(h, f);1436fe_mul_small(h, h, 2);1437}14381439// This could be simplified, but it would be slower1440static void fe_pow22523(fe out, const fe z)1441{1442fe t0, t1, t2;1443fe_sq(t0, z);1444fe_sq(t1,t0); fe_sq(t1, t1); fe_mul(t1, z, t1);1445fe_mul(t0, t0, t1);1446fe_sq(t0, t0); fe_mul(t0, t1, t0);1447fe_sq(t1, t0); FOR (i, 1, 5) fe_sq(t1, t1); fe_mul(t0, t1, t0);1448fe_sq(t1, t0); FOR (i, 1, 10) fe_sq(t1, t1); fe_mul(t1, t1, t0);1449fe_sq(t2, t1); FOR (i, 1, 20) fe_sq(t2, t2); fe_mul(t1, t2, t1);1450fe_sq(t1, t1); FOR (i, 1, 10) fe_sq(t1, t1); fe_mul(t0, t1, t0);1451fe_sq(t1, t0); FOR (i, 1, 50) fe_sq(t1, t1); fe_mul(t1, t1, t0);1452fe_sq(t2, t1); FOR (i, 1, 100) fe_sq(t2, t2); fe_mul(t1, t2, t1);1453fe_sq(t1, t1); FOR (i, 1, 50) fe_sq(t1, t1); fe_mul(t0, t1, t0);1454fe_sq(t0, t0); FOR (i, 1, 2) fe_sq(t0, t0); fe_mul(out, t0, z);1455WIPE_BUFFER(t0);1456WIPE_BUFFER(t1);1457WIPE_BUFFER(t2);1458}14591460// Inverting means multiplying by 2^255 - 211461// 2^255 - 21 = (2^252 - 3) * 8 + 31462// So we reuse the multiplication chain of fe_pow225231463static void fe_invert(fe out, const fe z)1464{1465fe tmp;1466fe_pow22523(tmp, z);1467// tmp2^8 * z^31468fe_sq(tmp, tmp); // 01469fe_sq(tmp, tmp); fe_mul(tmp, tmp, z); // 11470fe_sq(tmp, tmp); fe_mul(out, tmp, z); // 11471WIPE_BUFFER(tmp);1472}14731474// Parity check. Returns 0 if even, 1 if odd1475static int fe_isodd(const fe f)1476{1477u8 s[32];1478fe_tobytes(s, f);1479u8 isodd = s[0] & 1;1480WIPE_BUFFER(s);1481return isodd;1482}14831484// Returns 1 if equal, 0 if not equal1485static int fe_isequal(const fe f, const fe g)1486{1487u8 fs[32];1488u8 gs[32];1489fe_tobytes(fs, f);1490fe_tobytes(gs, g);1491int isdifferent = crypto_verify32(fs, gs);1492WIPE_BUFFER(fs);1493WIPE_BUFFER(gs);1494return 1 + isdifferent;1495}14961497// Inverse square root.1498// Returns true if x is a non zero square, false otherwise.1499// After the call:1500// isr = sqrt(1/x) if x is non-zero square.1501// isr = sqrt(sqrt(-1)/x) if x is not a square.1502// isr = 0 if x is zero.1503// We do not guarantee the sign of the square root.1504//1505// Notes:1506// Let quartic = x^((p-1)/4)1507//1508// x^((p-1)/2) = chi(x)1509// quartic^2 = chi(x)1510// quartic = sqrt(chi(x))1511// quartic = 1 or -1 or sqrt(-1) or -sqrt(-1)1512//1513// Note that x is a square if quartic is 1 or -11514// There are 4 cases to consider:1515//1516// if quartic = 1 (x is a square)1517// then x^((p-1)/4) = 11518// x^((p-5)/4) * x = 11519// x^((p-5)/4) = 1/x1520// x^((p-5)/8) = sqrt(1/x) or -sqrt(1/x)1521//1522// if quartic = -1 (x is a square)1523// then x^((p-1)/4) = -11524// x^((p-5)/4) * x = -11525// x^((p-5)/4) = -1/x1526// x^((p-5)/8) = sqrt(-1) / sqrt(x)1527// x^((p-5)/8) * sqrt(-1) = sqrt(-1)^2 / sqrt(x)1528// x^((p-5)/8) * sqrt(-1) = -1/sqrt(x)1529// x^((p-5)/8) * sqrt(-1) = -sqrt(1/x) or sqrt(1/x)1530//1531// if quartic = sqrt(-1) (x is not a square)1532// then x^((p-1)/4) = sqrt(-1)1533// x^((p-5)/4) * x = sqrt(-1)1534// x^((p-5)/4) = sqrt(-1)/x1535// x^((p-5)/8) = sqrt(sqrt(-1)/x) or -sqrt(sqrt(-1)/x)1536//1537// Note that the product of two non-squares is always a square:1538// For any non-squares a and b, chi(a) = -1 and chi(b) = -1.1539// Since chi(x) = x^((p-1)/2), chi(a)*chi(b) = chi(a*b) = 1.1540// Therefore a*b is a square.1541//1542// Since sqrt(-1) and x are both non-squares, their product is a1543// square, and we can compute their square root.1544//1545// if quartic = -sqrt(-1) (x is not a square)1546// then x^((p-1)/4) = -sqrt(-1)1547// x^((p-5)/4) * x = -sqrt(-1)1548// x^((p-5)/4) = -sqrt(-1)/x1549// x^((p-5)/8) = sqrt(-sqrt(-1)/x)1550// x^((p-5)/8) = sqrt( sqrt(-1)/x) * sqrt(-1)1551// x^((p-5)/8) * sqrt(-1) = sqrt( sqrt(-1)/x) * sqrt(-1)^21552// x^((p-5)/8) * sqrt(-1) = sqrt( sqrt(-1)/x) * -11553// x^((p-5)/8) * sqrt(-1) = -sqrt(sqrt(-1)/x) or sqrt(sqrt(-1)/x)1554static int invsqrt(fe isr, const fe x)1555{1556fe check, quartic;1557fe_copy(check, x);1558fe_pow22523(isr, check);1559fe_sq (quartic, isr);1560fe_mul(quartic, quartic, check);1561fe_1 (check); int p1 = fe_isequal(quartic, check);1562fe_neg(check, check ); int m1 = fe_isequal(quartic, check);1563fe_neg(check, sqrtm1); int ms = fe_isequal(quartic, check);1564fe_mul(check, isr, sqrtm1);1565fe_ccopy(isr, check, m1 | ms);1566WIPE_BUFFER(quartic);1567WIPE_BUFFER(check);1568return p1 | m1;1569}15701571// trim a scalar for scalar multiplication1572static void trim_scalar(u8 scalar[32])1573{1574scalar[ 0] &= 248;1575scalar[31] &= 127;1576scalar[31] |= 64;1577}15781579// get bit from scalar at position i1580static int scalar_bit(const u8 s[32], int i)1581{1582if (i < 0) { return 0; } // handle -1 for sliding windows1583return (s[i>>3] >> (i&7)) & 1;1584}15851586///////////////1587/// X-25519 /// Taken from SUPERCOP's ref10 implementation.1588///////////////1589static void scalarmult(u8 q[32], const u8 scalar[32], const u8 p[32],1590int nb_bits)1591{1592// computes the scalar product1593fe x1;1594fe_frombytes(x1, p);15951596// computes the actual scalar product (the result is in x2 and z2)1597fe x2, z2, x3, z3, t0, t1;1598// Montgomery ladder1599// In projective coordinates, to avoid divisions: x = X / Z1600// We don't care about the y coordinate, it's only 1 bit of information1601fe_1(x2); fe_0(z2); // "zero" point1602fe_copy(x3, x1); fe_1(z3); // "one" point1603int swap = 0;1604for (int pos = nb_bits-1; pos >= 0; --pos) {1605// constant time conditional swap before ladder step1606int b = scalar_bit(scalar, pos);1607swap ^= b; // xor trick avoids swapping at the end of the loop1608fe_cswap(x2, x3, swap);1609fe_cswap(z2, z3, swap);1610swap = b; // anticipates one last swap after the loop16111612// Montgomery ladder step: replaces (P2, P3) by (P2*2, P2+P3)1613// with differential addition1614fe_sub(t0, x3, z3);1615fe_sub(t1, x2, z2);1616fe_add(x2, x2, z2);1617fe_add(z2, x3, z3);1618fe_mul(z3, t0, x2);1619fe_mul(z2, z2, t1);1620fe_sq (t0, t1 );1621fe_sq (t1, x2 );1622fe_add(x3, z3, z2);1623fe_sub(z2, z3, z2);1624fe_mul(x2, t1, t0);1625fe_sub(t1, t1, t0);1626fe_sq (z2, z2 );1627fe_mul_small(z3, t1, 121666);1628fe_sq (x3, x3 );1629fe_add(t0, t0, z3);1630fe_mul(z3, x1, z2);1631fe_mul(z2, t1, t0);1632}1633// last swap is necessary to compensate for the xor trick1634// Note: after this swap, P3 == P2 + P1.1635fe_cswap(x2, x3, swap);1636fe_cswap(z2, z3, swap);16371638// normalises the coordinates: x == X / Z1639fe_invert(z2, z2);1640fe_mul(x2, x2, z2);1641fe_tobytes(q, x2);16421643WIPE_BUFFER(x1);1644WIPE_BUFFER(x2); WIPE_BUFFER(z2); WIPE_BUFFER(t0);1645WIPE_BUFFER(x3); WIPE_BUFFER(z3); WIPE_BUFFER(t1);1646}16471648void crypto_x25519(u8 raw_shared_secret[32],1649const u8 your_secret_key [32],1650const u8 their_public_key [32])1651{1652// restrict the possible scalar values1653u8 e[32];1654COPY(e, your_secret_key, 32);1655trim_scalar(e);1656scalarmult(raw_shared_secret, e, their_public_key, 255);1657WIPE_BUFFER(e);1658}16591660void crypto_x25519_public_key(u8 public_key[32],1661const u8 secret_key[32])1662{1663static const u8 base_point[32] = {9};1664crypto_x25519(public_key, secret_key, base_point);1665}16661667///////////////////////////1668/// Arithmetic modulo L ///1669///////////////////////////1670static const u32 L[8] = {0x5cf5d3ed, 0x5812631a, 0xa2f79cd6, 0x14def9de,16710x00000000, 0x00000000, 0x00000000, 0x10000000,};16721673// p = a*b + p1674static void multiply(u32 p[16], const u32 a[8], const u32 b[8])1675{1676FOR (i, 0, 8) {1677u64 carry = 0;1678FOR (j, 0, 8) {1679carry += p[i+j] + (u64)a[i] * b[j];1680p[i+j] = (u32)carry;1681carry >>= 32;1682}1683p[i+8] = (u32)carry;1684}1685}16861687static int is_above_l(const u32 x[8])1688{1689// We work with L directly, in a 2's complement encoding1690// (-L == ~L + 1)1691u64 carry = 1;1692FOR (i, 0, 8) {1693carry += (u64)x[i] + ~L[i];1694carry >>= 32;1695}1696return carry;1697}16981699// Final reduction modulo L, by conditionally removing L.1700// if x < l , then r = x1701// if l <= x 2*l, then r = x-l1702// otherwise the result will be wrong1703static void remove_l(u32 r[8], const u32 x[8])1704{1705u64 carry = is_above_l(x);1706u32 mask = ~(u32)carry + 1; // carry == 0 or 11707FOR (i, 0, 8) {1708carry += (u64)x[i] + (~L[i] & mask);1709r[i] = (u32)carry;1710carry >>= 32;1711}1712}17131714// Full reduction modulo L (Barrett reduction)1715static void mod_l(u8 reduced[32], const u32 x[16])1716{1717static const u32 r[9] = {0x0a2c131b,0xed9ce5a3,0x086329a7,0x2106215d,17180xffffffeb,0xffffffff,0xffffffff,0xffffffff,0xf,};1719// xr = x * r1720u32 xr[25] = {0};1721FOR (i, 0, 9) {1722u64 carry = 0;1723FOR (j, 0, 16) {1724carry += xr[i+j] + (u64)r[i] * x[j];1725xr[i+j] = (u32)carry;1726carry >>= 32;1727}1728xr[i+16] = (u32)carry;1729}1730// xr = floor(xr / 2^512) * L1731// Since the result is guaranteed to be below 2*L,1732// it is enough to only compute the first 256 bits.1733// The division is performed by saying xr[i+16]. (16 * 32 = 512)1734ZERO(xr, 8);1735FOR (i, 0, 8) {1736u64 carry = 0;1737FOR (j, 0, 8-i) {1738carry += xr[i+j] + (u64)xr[i+16] * L[j];1739xr[i+j] = (u32)carry;1740carry >>= 32;1741}1742}1743// xr = x - xr1744u64 carry = 1;1745FOR (i, 0, 8) {1746carry += (u64)x[i] + ~xr[i];1747xr[i] = (u32)carry;1748carry >>= 32;1749}1750// Final reduction modulo L (conditional subtraction)1751remove_l(xr, xr);1752store32_le_buf(reduced, xr, 8);17531754WIPE_BUFFER(xr);1755}17561757static void reduce(u8 r[64])1758{1759u32 x[16];1760load32_le_buf(x, r, 16);1761mod_l(r, x);1762WIPE_BUFFER(x);1763}17641765// r = (a * b) + c1766static void mul_add(u8 r[32], const u8 a[32], const u8 b[32], const u8 c[32])1767{1768u32 A[8]; load32_le_buf(A, a, 8);1769u32 B[8]; load32_le_buf(B, b, 8);1770u32 p[16];1771load32_le_buf(p, c, 8);1772ZERO(p + 8, 8);1773multiply(p, A, B);1774mod_l(r, p);1775WIPE_BUFFER(p);1776WIPE_BUFFER(A);1777WIPE_BUFFER(B);1778}17791780///////////////1781/// Ed25519 ///1782///////////////17831784// Point (group element, ge) in a twisted Edwards curve,1785// in extended projective coordinates.1786// ge : x = X/Z, y = Y/Z, T = XY/Z1787// ge_cached : Yp = X+Y, Ym = X-Y, T2 = T*D21788// ge_precomp: Z = 11789typedef struct { fe X; fe Y; fe Z; fe T; } ge;1790typedef struct { fe Yp; fe Ym; fe Z; fe T2; } ge_cached;1791typedef struct { fe Yp; fe Ym; fe T2; } ge_precomp;17921793static void ge_zero(ge *p)1794{1795fe_0(p->X);1796fe_1(p->Y);1797fe_1(p->Z);1798fe_0(p->T);1799}18001801static void ge_tobytes(u8 s[32], const ge *h)1802{1803fe recip, x, y;1804fe_invert(recip, h->Z);1805fe_mul(x, h->X, recip);1806fe_mul(y, h->Y, recip);1807fe_tobytes(s, y);1808s[31] ^= fe_isodd(x) << 7;18091810WIPE_BUFFER(recip);1811WIPE_BUFFER(x);1812WIPE_BUFFER(y);1813}18141815// h = s, where s is a point encoded in 32 bytes1816//1817// Variable time! Inputs must not be secret!1818// => Use only to *check* signatures.1819//1820// From the specifications:1821// The encoding of s contains y and the sign of x1822// x = sqrt((y^2 - 1) / (d*y^2 + 1))1823// In extended coordinates:1824// X = x, Y = y, Z = 1, T = x*y1825//1826// Note that num * den is a square iff num / den is a square1827// If num * den is not a square, the point was not on the curve.1828// From the above:1829// Let num = y^2 - 11830// Let den = d*y^2 + 11831// x = sqrt((y^2 - 1) / (d*y^2 + 1))1832// x = sqrt(num / den)1833// x = sqrt(num^2 / (num * den))1834// x = num * sqrt(1 / (num * den))1835//1836// Therefore, we can just compute:1837// num = y^2 - 11838// den = d*y^2 + 11839// isr = invsqrt(num * den) // abort if not square1840// x = num * isr1841// Finally, negate x if its sign is not as specified.1842static int ge_frombytes_vartime(ge *h, const u8 s[32])1843{1844fe_frombytes(h->Y, s);1845fe_1(h->Z);1846fe_sq (h->T, h->Y); // t = y^21847fe_mul(h->X, h->T, d ); // x = d*y^21848fe_sub(h->T, h->T, h->Z); // t = y^2 - 11849fe_add(h->X, h->X, h->Z); // x = d*y^2 + 11850fe_mul(h->X, h->T, h->X); // x = (y^2 - 1) * (d*y^2 + 1)1851int is_square = invsqrt(h->X, h->X);1852if (!is_square) {1853return -1; // Not on the curve, abort1854}1855fe_mul(h->X, h->T, h->X); // x = sqrt((y^2 - 1) / (d*y^2 + 1))1856if (fe_isodd(h->X) != (s[31] >> 7)) {1857fe_neg(h->X, h->X);1858}1859fe_mul(h->T, h->X, h->Y);1860return 0;1861}18621863static void ge_cache(ge_cached *c, const ge *p)1864{1865fe_add (c->Yp, p->Y, p->X);1866fe_sub (c->Ym, p->Y, p->X);1867fe_copy(c->Z , p->Z );1868fe_mul (c->T2, p->T, D2 );1869}18701871// Internal buffers are not wiped! Inputs must not be secret!1872// => Use only to *check* signatures.1873static void ge_add(ge *s, const ge *p, const ge_cached *q)1874{1875fe a, b;1876fe_add(a , p->Y, p->X );1877fe_sub(b , p->Y, p->X );1878fe_mul(a , a , q->Yp);1879fe_mul(b , b , q->Ym);1880fe_add(s->Y, a , b );1881fe_sub(s->X, a , b );18821883fe_add(s->Z, p->Z, p->Z );1884fe_mul(s->Z, s->Z, q->Z );1885fe_mul(s->T, p->T, q->T2);1886fe_add(a , s->Z, s->T );1887fe_sub(b , s->Z, s->T );18881889fe_mul(s->T, s->X, s->Y);1890fe_mul(s->X, s->X, b );1891fe_mul(s->Y, s->Y, a );1892fe_mul(s->Z, a , b );1893}18941895// Internal buffers are not wiped! Inputs must not be secret!1896// => Use only to *check* signatures.1897static void ge_sub(ge *s, const ge *p, const ge_cached *q)1898{1899ge_cached neg;1900fe_copy(neg.Ym, q->Yp);1901fe_copy(neg.Yp, q->Ym);1902fe_copy(neg.Z , q->Z );1903fe_neg (neg.T2, q->T2);1904ge_add(s, p, &neg);1905}19061907static void ge_madd(ge *s, const ge *p, const ge_precomp *q, fe a, fe b)1908{1909fe_add(a , p->Y, p->X );1910fe_sub(b , p->Y, p->X );1911fe_mul(a , a , q->Yp);1912fe_mul(b , b , q->Ym);1913fe_add(s->Y, a , b );1914fe_sub(s->X, a , b );19151916fe_add(s->Z, p->Z, p->Z );1917fe_mul(s->T, p->T, q->T2);1918fe_add(a , s->Z, s->T );1919fe_sub(b , s->Z, s->T );19201921fe_mul(s->T, s->X, s->Y);1922fe_mul(s->X, s->X, b );1923fe_mul(s->Y, s->Y, a );1924fe_mul(s->Z, a , b );1925}19261927static void ge_msub(ge *s, const ge *p, const ge_precomp *q, fe a, fe b)1928{1929fe_add(a , p->Y, p->X );1930fe_sub(b , p->Y, p->X );1931fe_mul(a , a , q->Ym);1932fe_mul(b , b , q->Yp);1933fe_add(s->Y, a , b );1934fe_sub(s->X, a , b );19351936fe_add(s->Z, p->Z, p->Z );1937fe_mul(s->T, p->T, q->T2);1938fe_sub(a , s->Z, s->T );1939fe_add(b , s->Z, s->T );19401941fe_mul(s->T, s->X, s->Y);1942fe_mul(s->X, s->X, b );1943fe_mul(s->Y, s->Y, a );1944fe_mul(s->Z, a , b );1945}19461947static void ge_double(ge *s, const ge *p, ge *q)1948{1949fe_sq (q->X, p->X);1950fe_sq (q->Y, p->Y);1951fe_sq2(q->Z, p->Z);1952fe_add(q->T, p->X, p->Y);1953fe_sq (s->T, q->T);1954fe_add(q->T, q->Y, q->X);1955fe_sub(q->Y, q->Y, q->X);1956fe_sub(q->X, s->T, q->T);1957fe_sub(q->Z, q->Z, q->Y);19581959fe_mul(s->X, q->X , q->Z);1960fe_mul(s->Y, q->T , q->Y);1961fe_mul(s->Z, q->Y , q->Z);1962fe_mul(s->T, q->X , q->T);1963}19641965// 5-bit signed window in cached format (Niels coordinates, Z=1)1966static const ge_precomp b_window[8] = {1967{{25967493,-14356035,29566456,3660896,-12694345,19684014787,27544626,-11754271,-6079156,2047605,},1969{-12545711,934262,-2722910,3049990,-727428,19709406986,12720692,5043384,19500929,-15469378,},1971{-8738181,4489570,9688441,-14785194,10184609,1972-12363380,29287919,11864899,-24514362,-4438546,},},1973{{15636291,-9688557,24204773,-7912398,616977,1974-16685262,27787600,-14772189,28944400,-1550024,},1975{16568933,4717097,-11556148,-1102322,15682896,1976-11807043,16354577,-11775962,7689662,11199574,},1977{30464156,-5976125,-11779434,-15670865,23220365,197815915852,7512774,10017326,-17749093,-9920357,},},1979{{10861363,11473154,27284546,1981175,-30064349,198012577861,32867885,14515107,-15438304,10819380,},1981{4708026,6336745,20377586,9066809,-11272109,19826594696,-25653668,12483688,-12668491,5581306,},1983{19563160,16186464,-29386857,4097519,10237984,1984-4348115,28542350,13850243,-23678021,-15815942,},},1985{{5153746,9909285,1723747,-2777874,30523605,19865516873,19480852,5230134,-23952439,-15175766,},1987{-30269007,-3463509,7665486,10083793,28475525,19881649722,20654025,16520125,30598449,7715701,},1989{28881845,14381568,9657904,3680757,-20181635,19907843316,-31400660,1370708,29794553,-1409300,},},1991{{-22518993,-6692182,14201702,-8745502,-23510406,19928844726,18474211,-1361450,-13062696,13821877,},1993{-6455177,-7839871,3374702,-4740862,-27098617,1994-10571707,31655028,-7212327,18853322,-14220951,},1995{4566830,-12963868,-28974889,-12240689,-7602672,1996-2830569,-8514358,-10431137,2207753,-3209784,},},1997{{-25154831,-4185821,29681144,7868801,-6854661,1998-9423865,-12437364,-663000,-31111463,-16132436,},1999{25576264,-2703214,7349804,-11814844,16472782,20009300885,3844789,15725684,171356,6466918,},2001{23103977,13316479,9739013,-16149481,817875,2002-15038942,8965339,-14088058,-30714912,16193877,},},2003{{-33521811,3180713,-2394130,14003687,-16903474,2004-16270840,17238398,4729455,-18074513,9256800,},2005{-25182317,-4174131,32336398,5036987,-21236817,200611360617,22616405,9761698,-19827198,630305,},2007{-13720693,2639453,-24237460,-7406481,9494427,2008-5774029,-6554551,-15960994,-2449256,-14291300,},},2009{{-3151181,-5046075,9282714,6866145,-31907062,2010-863023,-18940575,15033784,25105118,-7894876,},2011{-24326370,15950226,-31801215,-14592823,-11662737,2012-5090925,1573892,-2625887,2198790,-15804619,},2013{-3099351,10324967,-2241613,7453183,-5446979,2014-2735503,-13812022,-16236442,-32461234,-12290683,},},2015};20162017// Incremental sliding windows (left to right)2018// Based on Roberto Maria Avanzi[2005]2019typedef struct {2020i16 next_index; // position of the next signed digit2021i8 next_digit; // next signed digit (odd number below 2^window_width)2022u8 next_check; // point at which we must check for a new window2023} slide_ctx;20242025static void slide_init(slide_ctx *ctx, const u8 scalar[32])2026{2027// scalar is guaranteed to be below L, either because we checked (s),2028// or because we reduced it modulo L (h_ram). L is under 2^253, so2029// so bits 253 to 255 are guaranteed to be zero. No need to test them.2030//2031// Note however that L is very close to 2^252, so bit 252 is almost2032// always zero. If we were to start at bit 251, the tests wouldn't2033// catch the off-by-one error (constructing one that does would be2034// prohibitively expensive).2035//2036// We should still check bit 252, though.2037int i = 252;2038while (i > 0 && scalar_bit(scalar, i) == 0) {2039i--;2040}2041ctx->next_check = (u8)(i + 1);2042ctx->next_index = -1;2043ctx->next_digit = -1;2044}20452046static int slide_step(slide_ctx *ctx, int width, int i, const u8 scalar[32])2047{2048if (i == ctx->next_check) {2049if (scalar_bit(scalar, i) == scalar_bit(scalar, i - 1)) {2050ctx->next_check--;2051} else {2052// compute digit of next window2053int w = MIN(width, i + 1);2054int v = -(scalar_bit(scalar, i) << (w-1));2055FOR_T (int, j, 0, w-1) {2056v += scalar_bit(scalar, i-(w-1)+j) << j;2057}2058v += scalar_bit(scalar, i-w);2059int lsb = v & (~v + 1); // smallest bit of v2060int s = ( ((lsb & 0xAA) != 0) // log2(lsb)2061| (((lsb & 0xCC) != 0) << 1)2062| (((lsb & 0xF0) != 0) << 2));2063ctx->next_index = (i16)(i-(w-1)+s);2064ctx->next_digit = (i8) (v >> s );2065ctx->next_check -= (u8) w;2066}2067}2068return i == ctx->next_index ? ctx->next_digit: 0;2069}20702071#define P_W_WIDTH 3 // Affects the size of the stack2072#define B_W_WIDTH 5 // Affects the size of the binary2073#define P_W_SIZE (1<<(P_W_WIDTH-2))20742075// P = [b]B + [p]P, where B is the base point2076//2077// Variable time! Internal buffers are not wiped! Inputs must not be secret!2078// => Use only to *check* signatures.2079static void ge_double_scalarmult_vartime(ge *P, const u8 p[32], const u8 b[32])2080{2081// cache P window for addition2082ge_cached cP[P_W_SIZE];2083{2084ge P2, tmp;2085ge_double(&P2, P, &tmp);2086ge_cache(&cP[0], P);2087FOR (i, 1, P_W_SIZE) {2088ge_add(&tmp, &P2, &cP[i-1]);2089ge_cache(&cP[i], &tmp);2090}2091}20922093// Merged double and add ladder, fused with sliding2094slide_ctx p_slide; slide_init(&p_slide, p);2095slide_ctx b_slide; slide_init(&b_slide, b);2096int i = MAX(p_slide.next_check, b_slide.next_check);2097ge *sum = P;2098ge_zero(sum);2099while (i >= 0) {2100ge tmp;2101ge_double(sum, sum, &tmp);2102int p_digit = slide_step(&p_slide, P_W_WIDTH, i, p);2103int b_digit = slide_step(&b_slide, B_W_WIDTH, i, b);2104if (p_digit > 0) { ge_add(sum, sum, &cP[ p_digit / 2]); }2105if (p_digit < 0) { ge_sub(sum, sum, &cP[-p_digit / 2]); }2106fe t1, t2;2107if (b_digit > 0) { ge_madd(sum, sum, b_window + b_digit/2, t1, t2); }2108if (b_digit < 0) { ge_msub(sum, sum, b_window + -b_digit/2, t1, t2); }2109i--;2110}2111}21122113// R_check = s[B] - h_ram[pk], where B is the base point2114//2115// Variable time! Internal buffers are not wiped! Inputs must not be secret!2116// => Use only to *check* signatures.2117static int ge_r_check(u8 R_check[32], u8 s[32], u8 h_ram[32], u8 pk[32])2118{2119ge A; // not secret, not wiped2120u32 s32[8]; // not secret, not wiped2121load32_le_buf(s32, s, 8);2122if (ge_frombytes_vartime(&A, pk) || // A = pk2123is_above_l(s32)) { // prevent s malleability2124return -1;2125}2126fe_neg(A.X, A.X);2127fe_neg(A.T, A.T); // A = -pk2128ge_double_scalarmult_vartime(&A, h_ram, s); // A = [s]B - [h_ram]pk2129ge_tobytes(R_check, &A); // R_check = A2130return 0;2131}21322133// 5-bit signed comb in cached format (Niels coordinates, Z=1)2134static const ge_precomp b_comb_low[8] = {2135{{-6816601,-2324159,-22559413,124364,18015490,21368373481,19993724,1979872,-18549925,9085059,},2137{10306321,403248,14839893,9633706,8463310,2138-8354981,-14305673,14668847,26301366,2818560,},2139{-22701500,-3210264,-13831292,-2927732,-16326337,2140-14016360,12940910,177905,12165515,-2397893,},},2141{{-12282262,-7022066,9920413,-3064358,-32147467,21422927790,22392436,-14852487,2719975,16402117,},2143{-7236961,-4729776,2685954,-6525055,-24242706,2144-15940211,-6238521,14082855,10047669,12228189,},2145{-30495588,-12893761,-11161261,3539405,-11502464,214616491580,-27286798,-15030530,-7272871,-15934455,},},2147{{17650926,582297,-860412,-187745,-12072900,2148-10683391,-20352381,15557840,-31072141,-5019061,},2149{-6283632,-2259834,-4674247,-4598977,-4089240,215012435688,-31278303,1060251,6256175,10480726,},2151{-13871026,2026300,-21928428,-2741605,-2406664,2152-8034988,7355518,15733500,-23379862,7489131,},},2153{{6883359,695140,23196907,9644202,-33430614,215411354760,-20134606,6388313,-8263585,-8491918,},2155{-7716174,-13605463,-13646110,14757414,-19430591,2156-14967316,10359532,-11059670,-21935259,12082603,},2157{-11253345,-15943946,10046784,5414629,24840771,21588086951,-6694742,9868723,15842692,-16224787,},},2159{{9639399,11810955,-24007778,-9320054,3912937,2160-9856959,996125,-8727907,-8919186,-14097242,},2161{7248867,14468564,25228636,-8795035,14346339,21628224790,6388427,-7181107,6468218,-8720783,},2163{15513115,15439095,7342322,-10157390,18005294,2164-7265713,2186239,4884640,10826567,7135781,},},2165{{-14204238,5297536,-5862318,-6004934,28095835,21664236101,-14203318,1958636,-16816875,3837147,},2167{-5511166,-13176782,-29588215,12339465,15325758,2168-15945770,-8813185,11075932,-19608050,-3776283,},2169{11728032,9603156,-4637821,-5304487,-7827751,21702724948,31236191,-16760175,-7268616,14799772,},},2171{{-28842672,4840636,-12047946,-9101456,-1445464,2172381905,-30977094,-16523389,1290540,12798615,},2173{27246947,-10320914,14792098,-14518944,5302070,2174-8746152,-3403974,-4149637,-27061213,10749585,},2175{25572375,-6270368,-15353037,16037944,1146292,217632198,23487090,9585613,24714571,-1418265,},},2177{{19844825,282124,-17583147,11004019,-32004269,2178-2716035,6105106,-1711007,-21010044,14338445,},2179{8027505,8191102,-18504907,-12335737,25173494,2180-5923905,15446145,7483684,-30440441,10009108,},2181{-14134701,-4174411,10246585,-14677495,33553567,2182-14012935,23366126,15080531,-7969992,7663473,},},2183};21842185static const ge_precomp b_comb_high[8] = {2186{{33055887,-4431773,-521787,6654165,951411,2187-6266464,-5158124,6995613,-5397442,-6985227,},2188{4014062,6967095,-11977872,3960002,8001989,21895130302,-2154812,-1899602,-31954493,-16173976,},2190{16271757,-9212948,23792794,731486,-25808309,2191-3546396,6964344,-4767590,10976593,10050757,},},2192{{2533007,-4288439,-24467768,-12387405,-13450051,219314542280,12876301,13893535,15067764,8594792,},2194{20073501,-11623621,3165391,-13119866,13188608,2195-11540496,-10751437,-13482671,29588810,2197295,},2196{-1084082,11831693,6031797,14062724,14748428,2197-8159962,-20721760,11742548,31368706,13161200,},},2198{{2050412,-6457589,15321215,5273360,25484180,2199124590,-18187548,-7097255,-6691621,-14604792,},2200{9938196,2162889,-6158074,-1711248,4278932,2201-2598531,-22865792,-7168500,-24323168,11746309,},2202{-22691768,-14268164,5965485,9383325,20443693,22035854192,28250679,-1381811,-10837134,13717818,},},2204{{-8495530,16382250,9548884,-4971523,-4491811,2205-3902147,6182256,-12832479,26628081,10395408,},2206{27329048,-15853735,7715764,8717446,-9215518,2207-14633480,28982250,-5668414,4227628,242148,},2208{-13279943,-7986904,-7100016,8764468,-27276630,22093096719,29678419,-9141299,3906709,11265498,},},2210{{11918285,15686328,-17757323,-11217300,-27548967,22114853165,-27168827,6807359,6871949,-1075745,},2212{-29002610,13984323,-27111812,-2713442,28107359,2213-13266203,6155126,15104658,3538727,-7513788,},2214{14103158,11233913,-33165269,9279850,31014152,22154335090,-1827936,4590951,13960841,12787712,},},2216{{1469134,-16738009,33411928,13942824,8092558,2217-8778224,-11165065,1437842,22521552,-2792954,},2218{31352705,-4807352,-25327300,3962447,12541566,2219-9399651,-27425693,7964818,-23829869,5541287,},2220{-25732021,-6864887,23848984,3039395,-9147354,22216022816,-27421653,10590137,25309915,-1584678,},},2222{{-22951376,5048948,31139401,-190316,-19542447,2223-626310,-17486305,-16511925,-18851313,-12985140,},2224{-9684890,14681754,30487568,7717771,-10829709,22259630497,30290549,-10531496,-27798994,-13812825,},2226{5827835,16097107,-24501327,12094619,7413972,222711447087,28057551,-1793987,-14056981,4359312,},},2228{{26323183,2342588,-21887793,-1623758,-6062284,22292107090,-28724907,9036464,-19618351,-13055189,},2230{-29697200,14829398,-4596333,14220089,-30022969,22312955645,12094100,-13693652,-5941445,7047569,},2232{-3201977,14413268,-12058324,-16417589,-9035655,2233-7224648,9258160,1399236,30397584,-5684634,},},2234};22352236static void lookup_add(ge *p, ge_precomp *tmp_c, fe tmp_a, fe tmp_b,2237const ge_precomp comb[8], const u8 scalar[32], int i)2238{2239u8 teeth = (u8)((scalar_bit(scalar, i) ) +2240(scalar_bit(scalar, i + 32) << 1) +2241(scalar_bit(scalar, i + 64) << 2) +2242(scalar_bit(scalar, i + 96) << 3));2243u8 high = teeth >> 3;2244u8 index = (teeth ^ (high - 1)) & 7;2245FOR (j, 0, 8) {2246i32 select = 1 & (((j ^ index) - 1) >> 8);2247fe_ccopy(tmp_c->Yp, comb[j].Yp, select);2248fe_ccopy(tmp_c->Ym, comb[j].Ym, select);2249fe_ccopy(tmp_c->T2, comb[j].T2, select);2250}2251fe_neg(tmp_a, tmp_c->T2);2252fe_cswap(tmp_c->T2, tmp_a , high ^ 1);2253fe_cswap(tmp_c->Yp, tmp_c->Ym, high ^ 1);2254ge_madd(p, p, tmp_c, tmp_a, tmp_b);2255}22562257// p = [scalar]B, where B is the base point2258static void ge_scalarmult_base(ge *p, const u8 scalar[32])2259{2260// twin 4-bits signed combs, from Mike Hamburg's2261// Fast and compact elliptic-curve cryptography (2012)2262// 1 / 2 modulo L2263static const u8 half_mod_L[32] = {2264247,233,122,46,141,49,9,44,107,206,123,81,239,124,111,10,22650,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8, };2266// (2^256 - 1) / 2 modulo L2267static const u8 half_ones[32] = {2268142,74,204,70,186,24,118,107,184,231,190,57,250,173,119,99,2269255,255,255,255,255,255,255,255,255,255,255,255,255,255,255,7, };22702271// All bits set form: 1 means 1, 0 means -12272u8 s_scalar[32];2273mul_add(s_scalar, scalar, half_mod_L, half_ones);22742275// Double and add ladder2276fe tmp_a, tmp_b; // temporaries for addition2277ge_precomp tmp_c; // temporary for comb lookup2278ge tmp_d; // temporary for doubling2279fe_1(tmp_c.Yp);2280fe_1(tmp_c.Ym);2281fe_0(tmp_c.T2);22822283// Save a double on the first iteration2284ge_zero(p);2285lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_low , s_scalar, 31);2286lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_high, s_scalar, 31+128);2287// Regular double & add for the rest2288for (int i = 30; i >= 0; i--) {2289ge_double(p, p, &tmp_d);2290lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_low , s_scalar, i);2291lookup_add(p, &tmp_c, tmp_a, tmp_b, b_comb_high, s_scalar, i+128);2292}2293// Note: we could save one addition at the end if we assumed the2294// scalar fit in 252 bit. Which it does in practice if it is2295// selected at random. However, non-random, non-hashed scalars2296// *can* overflow 252 bits in practice. Better account for that2297// than leaving that kind of subtle corner case.22982299WIPE_BUFFER(tmp_a); WIPE_CTX(&tmp_d);2300WIPE_BUFFER(tmp_b); WIPE_CTX(&tmp_c);2301WIPE_BUFFER(s_scalar);2302}23032304void crypto_sign_public_key_custom_hash(u8 public_key[32],2305const u8 secret_key[32],2306const crypto_sign_vtable *hash)2307{2308u8 a[64];2309hash->hash(a, secret_key, 32);2310trim_scalar(a);2311ge A;2312ge_scalarmult_base(&A, a);2313ge_tobytes(public_key, &A);2314WIPE_BUFFER(a);2315WIPE_CTX(&A);2316}23172318void crypto_sign_public_key(u8 public_key[32], const u8 secret_key[32])2319{2320crypto_sign_public_key_custom_hash(public_key, secret_key,2321&crypto_blake2b_vtable);2322}23232324void crypto_sign_init_first_pass_custom_hash(crypto_sign_ctx_abstract *ctx,2325const u8 secret_key[32],2326const u8 public_key[32],2327const crypto_sign_vtable *hash)2328{2329ctx->hash = hash; // set vtable2330u8 *a = ctx->buf;2331u8 *prefix = ctx->buf + 32;2332ctx->hash->hash(a, secret_key, 32);2333trim_scalar(a);23342335if (public_key == 0) {2336crypto_sign_public_key_custom_hash(ctx->pk, secret_key, ctx->hash);2337} else {2338COPY(ctx->pk, public_key, 32);2339}23402341// Deterministic part of EdDSA: Construct a nonce by hashing the message2342// instead of generating a random number.2343// An actual random number would work just fine, and would save us2344// the trouble of hashing the message twice. If we did that2345// however, the user could fuck it up and reuse the nonce.2346ctx->hash->init (ctx);2347ctx->hash->update(ctx, prefix , 32);2348}23492350void crypto_sign_init_first_pass(crypto_sign_ctx_abstract *ctx,2351const u8 secret_key[32],2352const u8 public_key[32])2353{2354crypto_sign_init_first_pass_custom_hash(ctx, secret_key, public_key,2355&crypto_blake2b_vtable);2356}23572358void crypto_sign_update(crypto_sign_ctx_abstract *ctx,2359const u8 *msg, size_t msg_size)2360{2361ctx->hash->update(ctx, msg, msg_size);2362}23632364void crypto_sign_init_second_pass(crypto_sign_ctx_abstract *ctx)2365{2366u8 *r = ctx->buf + 32;2367u8 *half_sig = ctx->buf + 64;2368ctx->hash->final(ctx, r);2369reduce(r);23702371// first half of the signature = "random" nonce times the base point2372ge R;2373ge_scalarmult_base(&R, r);2374ge_tobytes(half_sig, &R);2375WIPE_CTX(&R);23762377// Hash R, the public key, and the message together.2378// It cannot be done in parallel with the first hash.2379ctx->hash->init (ctx);2380ctx->hash->update(ctx, half_sig, 32);2381ctx->hash->update(ctx, ctx->pk , 32);2382}23832384void crypto_sign_final(crypto_sign_ctx_abstract *ctx, u8 signature[64])2385{2386u8 *a = ctx->buf;2387u8 *r = ctx->buf + 32;2388u8 *half_sig = ctx->buf + 64;2389u8 h_ram[64];2390ctx->hash->final(ctx, h_ram);2391reduce(h_ram);2392COPY(signature, half_sig, 32);2393mul_add(signature + 32, h_ram, a, r); // s = h_ram * a + r2394WIPE_BUFFER(h_ram);2395crypto_wipe(ctx, ctx->hash->ctx_size);2396}23972398void crypto_sign(u8 signature[64],2399const u8 secret_key[32],2400const u8 public_key[32],2401const u8 *message, size_t message_size)2402{2403crypto_sign_ctx ctx;2404crypto_sign_ctx_abstract *actx = (crypto_sign_ctx_abstract*)&ctx;2405crypto_sign_init_first_pass (actx, secret_key, public_key);2406crypto_sign_update (actx, message, message_size);2407crypto_sign_init_second_pass(actx);2408crypto_sign_update (actx, message, message_size);2409crypto_sign_final (actx, signature);2410}24112412void crypto_check_init_custom_hash(crypto_check_ctx_abstract *ctx,2413const u8 signature[64],2414const u8 public_key[32],2415const crypto_sign_vtable *hash)2416{2417ctx->hash = hash; // set vtable2418COPY(ctx->buf, signature , 64);2419COPY(ctx->pk , public_key, 32);2420ctx->hash->init (ctx);2421ctx->hash->update(ctx, signature , 32);2422ctx->hash->update(ctx, public_key, 32);2423}24242425void crypto_check_init(crypto_check_ctx_abstract *ctx, const u8 signature[64],2426const u8 public_key[32])2427{2428crypto_check_init_custom_hash(ctx, signature, public_key,2429&crypto_blake2b_vtable);2430}24312432void crypto_check_update(crypto_check_ctx_abstract *ctx,2433const u8 *msg, size_t msg_size)2434{2435ctx->hash->update(ctx, msg, msg_size);2436}24372438int crypto_check_final(crypto_check_ctx_abstract *ctx)2439{2440u8 h_ram[64];2441ctx->hash->final(ctx, h_ram);2442reduce(h_ram);2443u8 *R = ctx->buf; // R2444u8 *s = ctx->buf + 32; // s2445u8 *R_check = ctx->pk; // overwrite ctx->pk to save stack space2446if (ge_r_check(R_check, s, h_ram, ctx->pk)) {2447return -1;2448}2449return crypto_verify32(R, R_check); // R == R_check ? OK : fail2450}24512452int crypto_check(const u8 signature[64], const u8 public_key[32],2453const u8 *message, size_t message_size)2454{2455crypto_check_ctx ctx;2456crypto_check_ctx_abstract *actx = (crypto_check_ctx_abstract*)&ctx;2457crypto_check_init (actx, signature, public_key);2458crypto_check_update(actx, message, message_size);2459return crypto_check_final(actx);2460}24612462///////////////////////2463/// EdDSA to X25519 ///2464///////////////////////2465void crypto_from_eddsa_private(u8 x25519[32], const u8 eddsa[32])2466{2467u8 a[64];2468crypto_blake2b(a, eddsa, 32);2469COPY(x25519, a, 32);2470WIPE_BUFFER(a);2471}24722473void crypto_from_eddsa_public(u8 x25519[32], const u8 eddsa[32])2474{2475fe t1, t2;2476fe_frombytes(t2, eddsa);2477fe_add(t1, fe_one, t2);2478fe_sub(t2, fe_one, t2);2479fe_invert(t2, t2);2480fe_mul(t1, t1, t2);2481fe_tobytes(x25519, t1);2482WIPE_BUFFER(t1);2483WIPE_BUFFER(t2);2484}24852486/////////////////////////////////////////////2487/// Dirty ephemeral public key generation ///2488/////////////////////////////////////////////24892490// Those functions generates a public key, *without* clearing the2491// cofactor. Sending that key over the network leaks 3 bits of the2492// private key. Use only to generate ephemeral keys that will be hidden2493// with crypto_curve_to_hidden().2494//2495// The public key is otherwise compatible with crypto_x25519() and2496// crypto_key_exchange() (those properly clear the cofactor).2497//2498// Note that the distribution of the resulting public keys is almost2499// uniform. Flipping the sign of the v coordinate (not provided by this2500// function), covers the entire key space almost perfectly, where2501// "almost" means a 2^-128 bias (undetectable). This uniformity is2502// needed to ensure the proper randomness of the resulting2503// representatives (once we apply crypto_curve_to_hidden()).2504//2505// Recall that Curve25519 has order C = 2^255 + e, with e < 2^128 (not2506// to be confused with the prime order of the main subgroup, L, which is2507// 8 times less than that).2508//2509// Generating all points would require us to multiply a point of order C2510// (the base point plus any point of order 8) by all scalars from 0 to2511// C-1. Clamping limits us to scalars between 2^254 and 2^255 - 1. But2512// by negating the resulting point at random, we also cover scalars from2513// -2^255 + 1 to -2^254 (which modulo C is congruent to e+1 to 2^254 + e).2514//2515// In practice:2516// - Scalars from 0 to e + 1 are never generated2517// - Scalars from 2^255 to 2^255 + e are never generated2518// - Scalars from 2^254 + 1 to 2^254 + e are generated twice2519//2520// Since e < 2^128, detecting this bias requires observing over 2^1002521// representatives from a given source (this will never happen), *and*2522// recovering enough of the private key to determine that they do, or do2523// not, belong to the biased set (this practically requires solving2524// discrete logarithm, which is conjecturally intractable).2525//2526// In practice, this means the bias is impossible to detect.25272528// s + (x*L) % 8*L2529// Guaranteed to fit in 256 bits iff s fits in 255 bits.2530// L < 2^2532531// x%8 < 2^32532// L * (x%8) < 2^2552533// s < 2^2552534// s + L * (x%8) < 2^2562535static void add_xl(u8 s[32], u8 x)2536{2537u64 mod8 = x & 7;2538u64 carry = 0;2539FOR (i , 0, 8) {2540carry = carry + load32_le(s + 4*i) + L[i] * mod8;2541store32_le(s + 4*i, (u32)carry);2542carry >>= 32;2543}2544}25452546// "Small" dirty ephemeral key.2547// Use if you need to shrink the size of the binary, and can afford to2548// slow down by a factor of two (compared to the fast version)2549//2550// This version works by decoupling the cofactor from the main factor.2551//2552// - The trimmed scalar determines the main factor2553// - The clamped bits of the scalar determine the cofactor.2554//2555// Cofactor and main factor are combined into a single scalar, which is2556// then multiplied by a point of order 8*L (unlike the base point, which2557// has prime order). That "dirty" base point is the addition of the2558// regular base point (9), and a point of order 8.2559void crypto_x25519_dirty_small(u8 public_key[32], const u8 secret_key[32])2560{2561// Base point of order 8*L2562// Raw scalar multiplication with it does not clear the cofactor,2563// and the resulting public key will reveal 3 bits of the scalar.2564static const u8 dirty_base_point[32] = {25650x34, 0xfc, 0x6c, 0xb7, 0xc8, 0xde, 0x58, 0x97, 0x77, 0x70, 0xd9, 0x52,25660x16, 0xcc, 0xdc, 0x6c, 0x85, 0x90, 0xbe, 0xcd, 0x91, 0x9c, 0x07, 0x59,25670x94, 0x14, 0x56, 0x3b, 0x4b, 0xa4, 0x47, 0x0f, };2568// separate the main factor & the cofactor of the scalar2569u8 scalar[32];2570COPY(scalar, secret_key, 32);2571trim_scalar(scalar);25722573// Separate the main factor and the cofactor2574//2575// The scalar is trimmed, so its cofactor is cleared. The three2576// least significant bits however still have a main factor. We must2577// remove it for X25519 compatibility.2578//2579// We exploit the fact that 5*L = 1 (modulo 8)2580// cofactor = lsb * 5 * L (modulo 8*L)2581// combined = scalar + cofactor (modulo 8*L)2582// combined = scalar + (lsb * 5 * L) (modulo 8*L)2583add_xl(scalar, secret_key[0] * 5);2584scalarmult(public_key, scalar, dirty_base_point, 256);2585WIPE_BUFFER(scalar);2586}25872588// "Fast" dirty ephemeral key2589// We use this one by default.2590//2591// This version works by performing a regular scalar multiplication,2592// then add a low order point. The scalar multiplication is done in2593// Edwards space for more speed (*2 compared to the "small" version).2594// The cost is a bigger binary for programs that don't also sign messages.2595void crypto_x25519_dirty_fast(u8 public_key[32], const u8 secret_key[32])2596{2597u8 scalar[32];2598ge pk;2599COPY(scalar, secret_key, 32);2600trim_scalar(scalar);2601ge_scalarmult_base(&pk, scalar);26022603// Select low order point2604// We're computing the [cofactor]lop scalar multiplication, where:2605// cofactor = tweak & 7.2606// lop = (lop_x, lop_y)2607// lop_x = sqrt((sqrt(d + 1) + 1) / d)2608// lop_y = -lop_x * sqrtm12609// Notes:2610// - A (single) Montgomery ladder would be twice as slow.2611// - An actual scalar multiplication would hurt performance.2612// - A full table lookup would take more code.2613u8 cofactor = secret_key[0] & 7;2614int a = (cofactor >> 2) & 1;2615int b = (cofactor >> 1) & 1;2616int c = (cofactor >> 0) & 1;2617fe t1, t2, t3;2618fe_0(t1);2619fe_ccopy(t1, sqrtm1, b);2620fe_ccopy(t1, lop_x , c);2621fe_neg (t3, t1);2622fe_ccopy(t1, t3, a);2623fe_1(t2);2624fe_0(t3);2625fe_ccopy(t2, t3 , b);2626fe_ccopy(t2, lop_y, c);2627fe_neg (t3, t2);2628fe_ccopy(t2, t3, a^b);2629ge_precomp low_order_point;2630fe_add(low_order_point.Yp, t2, t1);2631fe_sub(low_order_point.Ym, t2, t1);2632fe_mul(low_order_point.T2, t2, t1);2633fe_mul(low_order_point.T2, low_order_point.T2, D2);26342635// Add low order point to the public key2636ge_madd(&pk, &pk, &low_order_point, t1, t2);26372638// Convert to Montgomery u coordinate (we ignore the sign)2639fe_add(t1, pk.Z, pk.Y);2640fe_sub(t2, pk.Z, pk.Y);2641fe_invert(t2, t2);2642fe_mul(t1, t1, t2);26432644fe_tobytes(public_key, t1);26452646WIPE_BUFFER(t1); WIPE_BUFFER(scalar);2647WIPE_BUFFER(t2); WIPE_CTX(&pk);2648WIPE_BUFFER(t3); WIPE_CTX(&low_order_point);2649}26502651///////////////////2652/// Elligator 2 ///2653///////////////////2654static const fe A = {486662};26552656// Elligator direct map2657//2658// Computes the point corresponding to a representative, encoded in 322659// bytes (little Endian). Since positive representatives fits in 2542660// bits, The two most significant bits are ignored.2661//2662// From the paper:2663// w = -A / (fe(1) + non_square * r^2)2664// e = chi(w^3 + A*w^2 + w)2665// u = e*w - (fe(1)-e)*(A//2)2666// v = -e * sqrt(u^3 + A*u^2 + u)2667//2668// We ignore v because we don't need it for X25519 (the Montgomery2669// ladder only uses u).2670//2671// Note that e is either 0, 1 or -12672// if e = 0 u = 0 and v = 02673// if e = 1 u = w2674// if e = -1 u = -w - A = w * non_square * r^22675//2676// Let r1 = non_square * r^22677// Let r2 = 1 + r12678// Note that r2 cannot be zero, -1/non_square is not a square.2679// We can (tediously) verify that:2680// w^3 + A*w^2 + w = (A^2*r1 - r2^2) * A / r2^32681// Therefore:2682// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3))2683// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3)) * 12684// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3)) * chi(r2^6)2685// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * (A / r2^3) * r2^6)2686// chi(w^3 + A*w^2 + w) = chi((A^2*r1 - r2^2) * A * r2^3)2687// Corollary:2688// e = 1 if (A^2*r1 - r2^2) * A * r2^3) is a non-zero square2689// e = -1 if (A^2*r1 - r2^2) * A * r2^3) is not a square2690// Note that w^3 + A*w^2 + w (and therefore e) can never be zero:2691// w^3 + A*w^2 + w = w * (w^2 + A*w + 1)2692// w^3 + A*w^2 + w = w * (w^2 + A*w + A^2/4 - A^2/4 + 1)2693// w^3 + A*w^2 + w = w * (w + A/2)^2 - A^2/4 + 1)2694// which is zero only if:2695// w = 0 (impossible)2696// (w + A/2)^2 = A^2/4 - 1 (impossible, because A^2/4-1 is not a square)2697//2698// Let isr = invsqrt((A^2*r1 - r2^2) * A * r2^3)2699// isr = sqrt(1 / ((A^2*r1 - r2^2) * A * r2^3)) if e = 12700// isr = sqrt(sqrt(-1) / ((A^2*r1 - r2^2) * A * r2^3)) if e = -12701//2702// if e = 12703// let u1 = -A * (A^2*r1 - r2^2) * A * r2^2 * isr^22704// u1 = w2705// u1 = u2706//2707// if e = -12708// let ufactor = -non_square * sqrt(-1) * r^22709// let vfactor = sqrt(ufactor)2710// let u2 = -A * (A^2*r1 - r2^2) * A * r2^2 * isr^2 * ufactor2711// u2 = w * -1 * -non_square * r^22712// u2 = w * non_square * r^22713// u2 = u2714void crypto_hidden_to_curve(uint8_t curve[32], const uint8_t hidden[32])2715{2716// Representatives are encoded in 254 bits.2717// The two most significant ones are random padding that must be ignored.2718u8 clamped[32];2719COPY(clamped, hidden, 32);2720clamped[31] &= 0x3f;27212722fe r, u, t1, t2, t3;2723fe_frombytes(r, clamped);2724fe_sq2(t1, r);2725fe_add(u, t1, fe_one);2726fe_sq (t2, u);2727fe_mul(t3, A2, t1);2728fe_sub(t3, t3, t2);2729fe_mul(t3, t3, A);2730fe_mul(t1, t2, u);2731fe_mul(t1, t3, t1);2732int is_square = invsqrt(t1, t1);2733fe_sq(u, r);2734fe_mul(u, u, ufactor);2735fe_ccopy(u, fe_one, is_square);2736fe_sq (t1, t1);2737fe_mul(u, u, A);2738fe_mul(u, u, t3);2739fe_mul(u, u, t2);2740fe_mul(u, u, t1);2741fe_neg(u, u);2742fe_tobytes(curve, u);27432744WIPE_BUFFER(t1); WIPE_BUFFER(r);2745WIPE_BUFFER(t2); WIPE_BUFFER(u);2746WIPE_BUFFER(t3); WIPE_BUFFER(clamped);2747}27482749// Elligator inverse map2750//2751// Computes the representative of a point, if possible. If not, it does2752// nothing and returns -1. Note that the success of the operation2753// depends only on the point (more precisely its u coordinate). The2754// tweak parameter is used only upon success2755//2756// The tweak should be a random byte. Beyond that, its contents are an2757// implementation detail. Currently, the tweak comprises:2758// - Bit 1 : sign of the v coordinate (0 if positive, 1 if negative)2759// - Bit 2-5: not used2760// - Bits 6-7: random padding2761//2762// From the paper:2763// Let sq = -non_square * u * (u+A)2764// if sq is not a square, or u = -A, there is no mapping2765// Assuming there is a mapping:2766// if v is positive: r = sqrt(-(u+A) / u)2767// if v is negative: r = sqrt(-u / (u+A))2768//2769// We compute isr = invsqrt(-non_square * u * (u+A))2770// if it wasn't a non-zero square, abort.2771// else, isr = sqrt(-1 / (non_square * u * (u+A))2772//2773// This causes us to abort if u is zero, even though we shouldn't. This2774// never happens in practice, because (i) a random point in the curve has2775// a negligible chance of being zero, and (ii) scalar multiplication with2776// a trimmed scalar *never* yields zero.2777//2778// Since:2779// isr * (u+A) = sqrt(-1 / (non_square * u * (u+A)) * (u+A)2780// isr * (u+A) = sqrt(-(u+A) / (non_square * u * (u+A))2781// and:2782// isr = u = sqrt(-1 / (non_square * u * (u+A)) * u2783// isr = u = sqrt(-u / (non_square * u * (u+A))2784// Therefore:2785// if v is positive: r = isr * (u+A)2786// if v is negative: r = isr * u2787int crypto_curve_to_hidden(u8 hidden[32], const u8 public_key[32], u8 tweak)2788{2789fe t1, t2, t3;2790fe_frombytes(t1, public_key);27912792fe_add(t2, t1, A);2793fe_mul(t3, t1, t2);2794fe_mul_small(t3, t3, -2);2795int is_square = invsqrt(t3, t3);2796if (!is_square) {2797// The only variable time bit. This ultimately reveals how many2798// tries it took us to find a representable key.2799// This does not affect security as long as we try keys at random.2800WIPE_BUFFER(t1);2801WIPE_BUFFER(t2);2802WIPE_BUFFER(t3);2803return -1;2804}2805fe_ccopy (t1, t2, tweak & 1);2806fe_mul (t3, t1, t3);2807fe_mul_small(t1, t3, 2);2808fe_neg (t2, t3);2809fe_ccopy (t3, t2, fe_isodd(t1));2810fe_tobytes(hidden, t3);28112812// Pad with two random bits2813hidden[31] |= tweak & 0xc0;28142815WIPE_BUFFER(t1);2816WIPE_BUFFER(t2);2817WIPE_BUFFER(t3);2818return 0;2819}28202821void crypto_hidden_key_pair(u8 hidden[32], u8 secret_key[32], u8 seed[32])2822{2823u8 pk [32]; // public key2824u8 buf[64]; // seed + representative2825COPY(buf + 32, seed, 32);2826do {2827crypto_chacha20(buf, 0, 64, buf+32, zero);2828crypto_x25519_dirty_fast(pk, buf); // or the "small" version2829} while(crypto_curve_to_hidden(buf+32, pk, buf[32]));2830// Note that the return value of crypto_curve_to_hidden() is2831// independent from its tweak parameter.2832// Therefore, buf[32] is not actually reused. Either we loop one2833// more time and buf[32] is used for the new seed, or we succeeded,2834// and buf[32] becomes the tweak parameter.28352836crypto_wipe(seed, 32);2837COPY(hidden , buf + 32, 32);2838COPY(secret_key, buf , 32);2839WIPE_BUFFER(buf);2840WIPE_BUFFER(pk);2841}28422843////////////////////2844/// Key exchange ///2845////////////////////2846void crypto_key_exchange(u8 shared_key[32],2847const u8 your_secret_key [32],2848const u8 their_public_key[32])2849{2850crypto_x25519(shared_key, your_secret_key, their_public_key);2851crypto_hchacha20(shared_key, shared_key, zero);2852}28532854///////////////////////2855/// Scalar division ///2856///////////////////////28572858// Montgomery reduction.2859// Divides x by (2^256), and reduces the result modulo L2860//2861// Precondition:2862// x < L * 2^2562863// Constants:2864// r = 2^256 (makes division by r trivial)2865// k = (r * (1/r) - 1) // L (1/r is computed modulo L )2866// Algorithm:2867// s = (x * k) % r2868// t = x + s*L (t is always a multiple of r)2869// u = (t/r) % L (u is always below 2*L, conditional subtraction is enough)2870static void redc(u32 u[8], u32 x[16])2871{2872static const u32 k[8] = { 0x12547e1b, 0xd2b51da3, 0xfdba84ff, 0xb1a206f2,28730xffa36bea, 0x14e75438, 0x6fe91836, 0x9db6c6f2,};2874static const u32 l[8] = { 0x5cf5d3ed, 0x5812631a, 0xa2f79cd6, 0x14def9de,28750x00000000, 0x00000000, 0x00000000, 0x10000000,};2876// s = x * k (modulo 2^256)2877// This is cheaper than the full multiplication.2878u32 s[8] = {0};2879FOR (i, 0, 8) {2880u64 carry = 0;2881FOR (j, 0, 8-i) {2882carry += s[i+j] + (u64)x[i] * k[j];2883s[i+j] = (u32)carry;2884carry >>= 32;2885}2886}2887u32 t[16] = {0};2888multiply(t, s, l);28892890// t = t + x2891u64 carry = 0;2892FOR (i, 0, 16) {2893carry += (u64)t[i] + x[i];2894t[i] = (u32)carry;2895carry >>= 32;2896}28972898// u = (t / 2^256) % L2899// Note that t / 2^256 is always below 2*L,2900// So a constant time conditional subtraction is enough2901// We work with L directly, in a 2's complement encoding2902// (-L == ~L + 1)2903remove_l(u, t+8);29042905WIPE_BUFFER(s);2906WIPE_BUFFER(t);2907}29082909void crypto_x25519_inverse(u8 blind_salt [32], const u8 private_key[32],2910const u8 curve_point[32])2911{2912static const u8 Lm2[32] = { // L - 229130xeb, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7, 0xa2,29140xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,29150x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10, };2916// 1 in Montgomery form2917u32 m_inv [8] = {0x8d98951d, 0xd6ec3174, 0x737dcf70, 0xc6ef5bf4,29180xfffffffe, 0xffffffff, 0xffffffff, 0x0fffffff,};29192920u8 scalar[32];2921COPY(scalar, private_key, 32);2922trim_scalar(scalar);29232924// Convert the scalar in Montgomery form2925// m_scl = scalar * 2^256 (modulo L)2926u32 m_scl[8];2927{2928u32 tmp[16];2929ZERO(tmp, 8);2930load32_le_buf(tmp+8, scalar, 8);2931mod_l(scalar, tmp);2932load32_le_buf(m_scl, scalar, 8);2933WIPE_BUFFER(tmp); // Wipe ASAP to save stack space2934}29352936u32 product[16];2937for (int i = 252; i >= 0; i--) {2938ZERO(product, 16);2939multiply(product, m_inv, m_inv);2940redc(m_inv, product);2941if (scalar_bit(Lm2, i)) {2942ZERO(product, 16);2943multiply(product, m_inv, m_scl);2944redc(m_inv, product);2945}2946}2947// Convert the inverse *out* of Montgomery form2948// scalar = m_inv / 2^256 (modulo L)2949COPY(product, m_inv, 8);2950ZERO(product + 8, 8);2951redc(m_inv, product);2952store32_le_buf(scalar, m_inv, 8); // the *inverse* of the scalar29532954// Clear the cofactor of scalar:2955// cleared = scalar * (3*L + 1) (modulo 8*L)2956// cleared = scalar + scalar * 3 * L (modulo 8*L)2957// Note that (scalar * 3) is reduced modulo 8, so we only need the2958// first byte.2959add_xl(scalar, scalar[0] * 3);29602961// Recall that 8*L < 2^256. However it is also very close to2962// 2^255. If we spanned the ladder over 255 bits, random tests2963// wouldn't catch the off-by-one error.2964scalarmult(blind_salt, scalar, curve_point, 256);29652966WIPE_BUFFER(scalar); WIPE_BUFFER(m_scl);2967WIPE_BUFFER(product); WIPE_BUFFER(m_inv);2968}29692970////////////////////////////////2971/// Authenticated encryption ///2972////////////////////////////////2973static void lock_auth(u8 mac[16], const u8 auth_key[32],2974const u8 *ad , size_t ad_size,2975const u8 *cipher_text, size_t text_size)2976{2977u8 sizes[16]; // Not secret, not wiped2978store64_le(sizes + 0, ad_size);2979store64_le(sizes + 8, text_size);2980crypto_poly1305_ctx poly_ctx; // auto wiped...2981crypto_poly1305_init (&poly_ctx, auth_key);2982crypto_poly1305_update(&poly_ctx, ad , ad_size);2983crypto_poly1305_update(&poly_ctx, zero , align(ad_size, 16));2984crypto_poly1305_update(&poly_ctx, cipher_text, text_size);2985crypto_poly1305_update(&poly_ctx, zero , align(text_size, 16));2986crypto_poly1305_update(&poly_ctx, sizes , 16);2987crypto_poly1305_final (&poly_ctx, mac); // ...here2988}29892990void crypto_lock_aead(u8 mac[16], u8 *cipher_text,2991const u8 key[32], const u8 nonce[24],2992const u8 *ad , size_t ad_size,2993const u8 *plain_text, size_t text_size)2994{2995u8 sub_key[32];2996u8 auth_key[64]; // "Wasting" the whole Chacha block is faster2997crypto_hchacha20(sub_key, key, nonce);2998crypto_chacha20(auth_key, 0, 64, sub_key, nonce + 16);2999crypto_chacha20_ctr(cipher_text, plain_text, text_size,3000sub_key, nonce + 16, 1);3001lock_auth(mac, auth_key, ad, ad_size, cipher_text, text_size);3002WIPE_BUFFER(sub_key);3003WIPE_BUFFER(auth_key);3004}30053006int crypto_unlock_aead(u8 *plain_text, const u8 key[32], const u8 nonce[24],3007const u8 mac[16],3008const u8 *ad , size_t ad_size,3009const u8 *cipher_text, size_t text_size)3010{3011u8 sub_key[32];3012u8 auth_key[64]; // "Wasting" the whole Chacha block is faster3013crypto_hchacha20(sub_key, key, nonce);3014crypto_chacha20(auth_key, 0, 64, sub_key, nonce + 16);3015u8 real_mac[16];3016lock_auth(real_mac, auth_key, ad, ad_size, cipher_text, text_size);3017WIPE_BUFFER(auth_key);3018if (crypto_verify16(mac, real_mac)) {3019WIPE_BUFFER(sub_key);3020WIPE_BUFFER(real_mac);3021return -1;3022}3023crypto_chacha20_ctr(plain_text, cipher_text, text_size,3024sub_key, nonce + 16, 1);3025WIPE_BUFFER(sub_key);3026WIPE_BUFFER(real_mac);3027return 0;3028}30293030void crypto_lock(u8 mac[16], u8 *cipher_text,3031const u8 key[32], const u8 nonce[24],3032const u8 *plain_text, size_t text_size)3033{3034crypto_lock_aead(mac, cipher_text, key, nonce, 0, 0, plain_text, text_size);3035}30363037int crypto_unlock(u8 *plain_text,3038const u8 key[32], const u8 nonce[24], const u8 mac[16],3039const u8 *cipher_text, size_t text_size)3040{3041return crypto_unlock_aead(plain_text, key, nonce, mac, 0, 0,3042cipher_text, text_size);3043}304430453046