blob: 3e805b889acd242f0ce2f3e9e283d2663e2fe8a1 [file] [log] [blame]
/* Copyright (c) 2015, Google Inc.
*
* Permission to use, copy, modify, and/or distribute this software for any
* purpose with or without fee is hereby granted, provided that the above
* copyright notice and this permission notice appear in all copies.
*
* THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
* WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
* MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
* SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
* WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
* OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
* CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
/* This code is mostly taken from the ref10 version of Ed25519 in SUPERCOP
* 20141124 (http://bench.cr.yp.to/supercop.html). That code is released as
* public domain but this file has the ISC license just to keep licencing
* simple.
*
* The field functions are shared by Ed25519 and X25519, although Ed25519 is
* disabled when |OPENSSL_SMALL| is defined. */
#include <openssl/curve25519.h>
#include <string.h>
#include <stdio.h>
#include <openssl/mem.h>
#include <openssl/rand.h>
#include <openssl/sha.h>
/* fe means field element. Here the field is \Z/(2^255-19). An element t,
* entries t[0]...t[9], represents the integer t[0]+2^26 t[1]+2^51 t[2]+2^77
* t[3]+2^102 t[4]+...+2^230 t[9]. Bounds on each t[i] vary depending on
* context. */
typedef int32_t fe[10];
static uint64_t load_3(const uint8_t *in) {
uint64_t result;
result = (uint64_t)in[0];
result |= ((uint64_t)in[1]) << 8;
result |= ((uint64_t)in[2]) << 16;
return result;
}
static uint64_t load_4(const uint8_t *in) {
uint64_t result;
result = (uint64_t)in[0];
result |= ((uint64_t)in[1]) << 8;
result |= ((uint64_t)in[2]) << 16;
result |= ((uint64_t)in[3]) << 24;
return result;
}
static void fe_frombytes(fe h, const uint8_t *s) {
/* Ignores top bit of h. */
int64_t h0 = load_4(s);
int64_t h1 = load_3(s + 4) << 6;
int64_t h2 = load_3(s + 7) << 5;
int64_t h3 = load_3(s + 10) << 3;
int64_t h4 = load_3(s + 13) << 2;
int64_t h5 = load_4(s + 16);
int64_t h6 = load_3(s + 20) << 7;
int64_t h7 = load_3(s + 23) << 5;
int64_t h8 = load_3(s + 26) << 4;
int64_t h9 = (load_3(s + 29) & 8388607) << 2;
int64_t carry0;
int64_t carry1;
int64_t carry2;
int64_t carry3;
int64_t carry4;
int64_t carry5;
int64_t carry6;
int64_t carry7;
int64_t carry8;
int64_t carry9;
carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
h[0] = h0;
h[1] = h1;
h[2] = h2;
h[3] = h3;
h[4] = h4;
h[5] = h5;
h[6] = h6;
h[7] = h7;
h[8] = h8;
h[9] = h9;
}
/* Preconditions:
* |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
*
* Write p=2^255-19; q=floor(h/p).
* Basic claim: q = floor(2^(-255)(h + 19 2^(-25)h9 + 2^(-1))).
*
* Proof:
* Have |h|<=p so |q|<=1 so |19^2 2^(-255) q|<1/4.
* Also have |h-2^230 h9|<2^231 so |19 2^(-255)(h-2^230 h9)|<1/4.
*
* Write y=2^(-1)-19^2 2^(-255)q-19 2^(-255)(h-2^230 h9).
* Then 0<y<1.
*
* Write r=h-pq.
* Have 0<=r<=p-1=2^255-20.
* Thus 0<=r+19(2^-255)r<r+19(2^-255)2^255<=2^255-1.
*
* Write x=r+19(2^-255)r+y.
* Then 0<x<2^255 so floor(2^(-255)x) = 0 so floor(q+2^(-255)x) = q.
*
* Have q+2^(-255)x = 2^(-255)(h + 19 2^(-25) h9 + 2^(-1))
* so floor(2^(-255)(h + 19 2^(-25) h9 + 2^(-1))) = q. */
static void fe_tobytes(uint8_t *s, const fe h) {
int32_t h0 = h[0];
int32_t h1 = h[1];
int32_t h2 = h[2];
int32_t h3 = h[3];
int32_t h4 = h[4];
int32_t h5 = h[5];
int32_t h6 = h[6];
int32_t h7 = h[7];
int32_t h8 = h[8];
int32_t h9 = h[9];
int32_t q;
int32_t carry0;
int32_t carry1;
int32_t carry2;
int32_t carry3;
int32_t carry4;
int32_t carry5;
int32_t carry6;
int32_t carry7;
int32_t carry8;
int32_t carry9;
q = (19 * h9 + (((int32_t) 1) << 24)) >> 25;
q = (h0 + q) >> 26;
q = (h1 + q) >> 25;
q = (h2 + q) >> 26;
q = (h3 + q) >> 25;
q = (h4 + q) >> 26;
q = (h5 + q) >> 25;
q = (h6 + q) >> 26;
q = (h7 + q) >> 25;
q = (h8 + q) >> 26;
q = (h9 + q) >> 25;
/* Goal: Output h-(2^255-19)q, which is between 0 and 2^255-20. */
h0 += 19 * q;
/* Goal: Output h-2^255 q, which is between 0 and 2^255-20. */
carry0 = h0 >> 26; h1 += carry0; h0 -= carry0 << 26;
carry1 = h1 >> 25; h2 += carry1; h1 -= carry1 << 25;
carry2 = h2 >> 26; h3 += carry2; h2 -= carry2 << 26;
carry3 = h3 >> 25; h4 += carry3; h3 -= carry3 << 25;
carry4 = h4 >> 26; h5 += carry4; h4 -= carry4 << 26;
carry5 = h5 >> 25; h6 += carry5; h5 -= carry5 << 25;
carry6 = h6 >> 26; h7 += carry6; h6 -= carry6 << 26;
carry7 = h7 >> 25; h8 += carry7; h7 -= carry7 << 25;
carry8 = h8 >> 26; h9 += carry8; h8 -= carry8 << 26;
carry9 = h9 >> 25; h9 -= carry9 << 25;
/* h10 = carry9 */
/* Goal: Output h0+...+2^255 h10-2^255 q, which is between 0 and 2^255-20.
* Have h0+...+2^230 h9 between 0 and 2^255-1;
* evidently 2^255 h10-2^255 q = 0.
* Goal: Output h0+...+2^230 h9. */
s[0] = h0 >> 0;
s[1] = h0 >> 8;
s[2] = h0 >> 16;
s[3] = (h0 >> 24) | (h1 << 2);
s[4] = h1 >> 6;
s[5] = h1 >> 14;
s[6] = (h1 >> 22) | (h2 << 3);
s[7] = h2 >> 5;
s[8] = h2 >> 13;
s[9] = (h2 >> 21) | (h3 << 5);
s[10] = h3 >> 3;
s[11] = h3 >> 11;
s[12] = (h3 >> 19) | (h4 << 6);
s[13] = h4 >> 2;
s[14] = h4 >> 10;
s[15] = h4 >> 18;
s[16] = h5 >> 0;
s[17] = h5 >> 8;
s[18] = h5 >> 16;
s[19] = (h5 >> 24) | (h6 << 1);
s[20] = h6 >> 7;
s[21] = h6 >> 15;
s[22] = (h6 >> 23) | (h7 << 3);
s[23] = h7 >> 5;
s[24] = h7 >> 13;
s[25] = (h7 >> 21) | (h8 << 4);
s[26] = h8 >> 4;
s[27] = h8 >> 12;
s[28] = (h8 >> 20) | (h9 << 6);
s[29] = h9 >> 2;
s[30] = h9 >> 10;
s[31] = h9 >> 18;
}
/* h = f */
static void fe_copy(fe h, const fe f) {
memmove(h, f, sizeof(int32_t) * 10);
}
/* h = 0 */
static void fe_0(fe h) { memset(h, 0, sizeof(int32_t) * 10); }
/* h = 1 */
static void fe_1(fe h) {
memset(h, 0, sizeof(int32_t) * 10);
h[0] = 1;
}
/* Replace (f,g) with (g,f) if b == 1;
* replace (f,g) with (f,g) if b == 0.
*
* Preconditions: b in {0,1}. */
static void fe_cswap(fe f, fe g, unsigned int b) {
b = -b;
unsigned i;
for (i = 0; i < 10; i++) {
int32_t x = f[i] ^ g[i];
x &= b;
f[i] ^= x;
g[i] ^= x;
}
}
/* h = f + g
* Can overlap h with f or g.
*
* Preconditions:
* |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
* |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
*
* Postconditions:
* |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
static void fe_add(fe h, const fe f, const fe g) {
unsigned i;
for (i = 0; i < 10; i++) {
h[i] = f[i] + g[i];
}
}
/* h = f - g
* Can overlap h with f or g.
*
* Preconditions:
* |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
* |g| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
*
* Postconditions:
* |h| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
static void fe_sub(fe h, const fe f, const fe g) {
unsigned i;
for (i = 0; i < 10; i++) {
h[i] = f[i] - g[i];
}
}
/* h = f * g
* Can overlap h with f or g.
*
* Preconditions:
* |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
* |g| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
*
* Postconditions:
* |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
*
* Notes on implementation strategy:
*
* Using schoolbook multiplication.
* Karatsuba would save a little in some cost models.
*
* Most multiplications by 2 and 19 are 32-bit precomputations;
* cheaper than 64-bit postcomputations.
*
* There is one remaining multiplication by 19 in the carry chain;
* one *19 precomputation can be merged into this,
* but the resulting data flow is considerably less clean.
*
* There are 12 carries below.
* 10 of them are 2-way parallelizable and vectorizable.
* Can get away with 11 carries, but then data flow is much deeper.
*
* With tighter constraints on inputs can squeeze carries into int32. */
static void fe_mul(fe h, const fe f, const fe g) {
int32_t f0 = f[0];
int32_t f1 = f[1];
int32_t f2 = f[2];
int32_t f3 = f[3];
int32_t f4 = f[4];
int32_t f5 = f[5];
int32_t f6 = f[6];
int32_t f7 = f[7];
int32_t f8 = f[8];
int32_t f9 = f[9];
int32_t g0 = g[0];
int32_t g1 = g[1];
int32_t g2 = g[2];
int32_t g3 = g[3];
int32_t g4 = g[4];
int32_t g5 = g[5];
int32_t g6 = g[6];
int32_t g7 = g[7];
int32_t g8 = g[8];
int32_t g9 = g[9];
int32_t g1_19 = 19 * g1; /* 1.959375*2^29 */
int32_t g2_19 = 19 * g2; /* 1.959375*2^30; still ok */
int32_t g3_19 = 19 * g3;
int32_t g4_19 = 19 * g4;
int32_t g5_19 = 19 * g5;
int32_t g6_19 = 19 * g6;
int32_t g7_19 = 19 * g7;
int32_t g8_19 = 19 * g8;
int32_t g9_19 = 19 * g9;
int32_t f1_2 = 2 * f1;
int32_t f3_2 = 2 * f3;
int32_t f5_2 = 2 * f5;
int32_t f7_2 = 2 * f7;
int32_t f9_2 = 2 * f9;
int64_t f0g0 = f0 * (int64_t) g0;
int64_t f0g1 = f0 * (int64_t) g1;
int64_t f0g2 = f0 * (int64_t) g2;
int64_t f0g3 = f0 * (int64_t) g3;
int64_t f0g4 = f0 * (int64_t) g4;
int64_t f0g5 = f0 * (int64_t) g5;
int64_t f0g6 = f0 * (int64_t) g6;
int64_t f0g7 = f0 * (int64_t) g7;
int64_t f0g8 = f0 * (int64_t) g8;
int64_t f0g9 = f0 * (int64_t) g9;
int64_t f1g0 = f1 * (int64_t) g0;
int64_t f1g1_2 = f1_2 * (int64_t) g1;
int64_t f1g2 = f1 * (int64_t) g2;
int64_t f1g3_2 = f1_2 * (int64_t) g3;
int64_t f1g4 = f1 * (int64_t) g4;
int64_t f1g5_2 = f1_2 * (int64_t) g5;
int64_t f1g6 = f1 * (int64_t) g6;
int64_t f1g7_2 = f1_2 * (int64_t) g7;
int64_t f1g8 = f1 * (int64_t) g8;
int64_t f1g9_38 = f1_2 * (int64_t) g9_19;
int64_t f2g0 = f2 * (int64_t) g0;
int64_t f2g1 = f2 * (int64_t) g1;
int64_t f2g2 = f2 * (int64_t) g2;
int64_t f2g3 = f2 * (int64_t) g3;
int64_t f2g4 = f2 * (int64_t) g4;
int64_t f2g5 = f2 * (int64_t) g5;
int64_t f2g6 = f2 * (int64_t) g6;
int64_t f2g7 = f2 * (int64_t) g7;
int64_t f2g8_19 = f2 * (int64_t) g8_19;
int64_t f2g9_19 = f2 * (int64_t) g9_19;
int64_t f3g0 = f3 * (int64_t) g0;
int64_t f3g1_2 = f3_2 * (int64_t) g1;
int64_t f3g2 = f3 * (int64_t) g2;
int64_t f3g3_2 = f3_2 * (int64_t) g3;
int64_t f3g4 = f3 * (int64_t) g4;
int64_t f3g5_2 = f3_2 * (int64_t) g5;
int64_t f3g6 = f3 * (int64_t) g6;
int64_t f3g7_38 = f3_2 * (int64_t) g7_19;
int64_t f3g8_19 = f3 * (int64_t) g8_19;
int64_t f3g9_38 = f3_2 * (int64_t) g9_19;
int64_t f4g0 = f4 * (int64_t) g0;
int64_t f4g1 = f4 * (int64_t) g1;
int64_t f4g2 = f4 * (int64_t) g2;
int64_t f4g3 = f4 * (int64_t) g3;
int64_t f4g4 = f4 * (int64_t) g4;
int64_t f4g5 = f4 * (int64_t) g5;
int64_t f4g6_19 = f4 * (int64_t) g6_19;
int64_t f4g7_19 = f4 * (int64_t) g7_19;
int64_t f4g8_19 = f4 * (int64_t) g8_19;
int64_t f4g9_19 = f4 * (int64_t) g9_19;
int64_t f5g0 = f5 * (int64_t) g0;
int64_t f5g1_2 = f5_2 * (int64_t) g1;
int64_t f5g2 = f5 * (int64_t) g2;
int64_t f5g3_2 = f5_2 * (int64_t) g3;
int64_t f5g4 = f5 * (int64_t) g4;
int64_t f5g5_38 = f5_2 * (int64_t) g5_19;
int64_t f5g6_19 = f5 * (int64_t) g6_19;
int64_t f5g7_38 = f5_2 * (int64_t) g7_19;
int64_t f5g8_19 = f5 * (int64_t) g8_19;
int64_t f5g9_38 = f5_2 * (int64_t) g9_19;
int64_t f6g0 = f6 * (int64_t) g0;
int64_t f6g1 = f6 * (int64_t) g1;
int64_t f6g2 = f6 * (int64_t) g2;
int64_t f6g3 = f6 * (int64_t) g3;
int64_t f6g4_19 = f6 * (int64_t) g4_19;
int64_t f6g5_19 = f6 * (int64_t) g5_19;
int64_t f6g6_19 = f6 * (int64_t) g6_19;
int64_t f6g7_19 = f6 * (int64_t) g7_19;
int64_t f6g8_19 = f6 * (int64_t) g8_19;
int64_t f6g9_19 = f6 * (int64_t) g9_19;
int64_t f7g0 = f7 * (int64_t) g0;
int64_t f7g1_2 = f7_2 * (int64_t) g1;
int64_t f7g2 = f7 * (int64_t) g2;
int64_t f7g3_38 = f7_2 * (int64_t) g3_19;
int64_t f7g4_19 = f7 * (int64_t) g4_19;
int64_t f7g5_38 = f7_2 * (int64_t) g5_19;
int64_t f7g6_19 = f7 * (int64_t) g6_19;
int64_t f7g7_38 = f7_2 * (int64_t) g7_19;
int64_t f7g8_19 = f7 * (int64_t) g8_19;
int64_t f7g9_38 = f7_2 * (int64_t) g9_19;
int64_t f8g0 = f8 * (int64_t) g0;
int64_t f8g1 = f8 * (int64_t) g1;
int64_t f8g2_19 = f8 * (int64_t) g2_19;
int64_t f8g3_19 = f8 * (int64_t) g3_19;
int64_t f8g4_19 = f8 * (int64_t) g4_19;
int64_t f8g5_19 = f8 * (int64_t) g5_19;
int64_t f8g6_19 = f8 * (int64_t) g6_19;
int64_t f8g7_19 = f8 * (int64_t) g7_19;
int64_t f8g8_19 = f8 * (int64_t) g8_19;
int64_t f8g9_19 = f8 * (int64_t) g9_19;
int64_t f9g0 = f9 * (int64_t) g0;
int64_t f9g1_38 = f9_2 * (int64_t) g1_19;
int64_t f9g2_19 = f9 * (int64_t) g2_19;
int64_t f9g3_38 = f9_2 * (int64_t) g3_19;
int64_t f9g4_19 = f9 * (int64_t) g4_19;
int64_t f9g5_38 = f9_2 * (int64_t) g5_19;
int64_t f9g6_19 = f9 * (int64_t) g6_19;
int64_t f9g7_38 = f9_2 * (int64_t) g7_19;
int64_t f9g8_19 = f9 * (int64_t) g8_19;
int64_t f9g9_38 = f9_2 * (int64_t) g9_19;
int64_t h0 = f0g0+f1g9_38+f2g8_19+f3g7_38+f4g6_19+f5g5_38+f6g4_19+f7g3_38+f8g2_19+f9g1_38;
int64_t h1 = f0g1+f1g0 +f2g9_19+f3g8_19+f4g7_19+f5g6_19+f6g5_19+f7g4_19+f8g3_19+f9g2_19;
int64_t h2 = f0g2+f1g1_2 +f2g0 +f3g9_38+f4g8_19+f5g7_38+f6g6_19+f7g5_38+f8g4_19+f9g3_38;
int64_t h3 = f0g3+f1g2 +f2g1 +f3g0 +f4g9_19+f5g8_19+f6g7_19+f7g6_19+f8g5_19+f9g4_19;
int64_t h4 = f0g4+f1g3_2 +f2g2 +f3g1_2 +f4g0 +f5g9_38+f6g8_19+f7g7_38+f8g6_19+f9g5_38;
int64_t h5 = f0g5+f1g4 +f2g3 +f3g2 +f4g1 +f5g0 +f6g9_19+f7g8_19+f8g7_19+f9g6_19;
int64_t h6 = f0g6+f1g5_2 +f2g4 +f3g3_2 +f4g2 +f5g1_2 +f6g0 +f7g9_38+f8g8_19+f9g7_38;
int64_t h7 = f0g7+f1g6 +f2g5 +f3g4 +f4g3 +f5g2 +f6g1 +f7g0 +f8g9_19+f9g8_19;
int64_t h8 = f0g8+f1g7_2 +f2g6 +f3g5_2 +f4g4 +f5g3_2 +f6g2 +f7g1_2 +f8g0 +f9g9_38;
int64_t h9 = f0g9+f1g8 +f2g7 +f3g6 +f4g5 +f5g4 +f6g3 +f7g2 +f8g1 +f9g0 ;
int64_t carry0;
int64_t carry1;
int64_t carry2;
int64_t carry3;
int64_t carry4;
int64_t carry5;
int64_t carry6;
int64_t carry7;
int64_t carry8;
int64_t carry9;
/* |h0| <= (1.65*1.65*2^52*(1+19+19+19+19)+1.65*1.65*2^50*(38+38+38+38+38))
* i.e. |h0| <= 1.4*2^60; narrower ranges for h2, h4, h6, h8
* |h1| <= (1.65*1.65*2^51*(1+1+19+19+19+19+19+19+19+19))
* i.e. |h1| <= 1.7*2^59; narrower ranges for h3, h5, h7, h9 */
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
/* |h0| <= 2^25 */
/* |h4| <= 2^25 */
/* |h1| <= 1.71*2^59 */
/* |h5| <= 1.71*2^59 */
carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
/* |h1| <= 2^24; from now on fits into int32 */
/* |h5| <= 2^24; from now on fits into int32 */
/* |h2| <= 1.41*2^60 */
/* |h6| <= 1.41*2^60 */
carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
/* |h2| <= 2^25; from now on fits into int32 unchanged */
/* |h6| <= 2^25; from now on fits into int32 unchanged */
/* |h3| <= 1.71*2^59 */
/* |h7| <= 1.71*2^59 */
carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
/* |h3| <= 2^24; from now on fits into int32 unchanged */
/* |h7| <= 2^24; from now on fits into int32 unchanged */
/* |h4| <= 1.72*2^34 */
/* |h8| <= 1.41*2^60 */
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
/* |h4| <= 2^25; from now on fits into int32 unchanged */
/* |h8| <= 2^25; from now on fits into int32 unchanged */
/* |h5| <= 1.01*2^24 */
/* |h9| <= 1.71*2^59 */
carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
/* |h9| <= 2^24; from now on fits into int32 unchanged */
/* |h0| <= 1.1*2^39 */
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
/* |h0| <= 2^25; from now on fits into int32 unchanged */
/* |h1| <= 1.01*2^24 */
h[0] = h0;
h[1] = h1;
h[2] = h2;
h[3] = h3;
h[4] = h4;
h[5] = h5;
h[6] = h6;
h[7] = h7;
h[8] = h8;
h[9] = h9;
}
/* h = f * f
* Can overlap h with f.
*
* Preconditions:
* |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
*
* Postconditions:
* |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
*
* See fe_mul.c for discussion of implementation strategy. */
static void fe_sq(fe h, const fe f) {
int32_t f0 = f[0];
int32_t f1 = f[1];
int32_t f2 = f[2];
int32_t f3 = f[3];
int32_t f4 = f[4];
int32_t f5 = f[5];
int32_t f6 = f[6];
int32_t f7 = f[7];
int32_t f8 = f[8];
int32_t f9 = f[9];
int32_t f0_2 = 2 * f0;
int32_t f1_2 = 2 * f1;
int32_t f2_2 = 2 * f2;
int32_t f3_2 = 2 * f3;
int32_t f4_2 = 2 * f4;
int32_t f5_2 = 2 * f5;
int32_t f6_2 = 2 * f6;
int32_t f7_2 = 2 * f7;
int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
int64_t f0f0 = f0 * (int64_t) f0;
int64_t f0f1_2 = f0_2 * (int64_t) f1;
int64_t f0f2_2 = f0_2 * (int64_t) f2;
int64_t f0f3_2 = f0_2 * (int64_t) f3;
int64_t f0f4_2 = f0_2 * (int64_t) f4;
int64_t f0f5_2 = f0_2 * (int64_t) f5;
int64_t f0f6_2 = f0_2 * (int64_t) f6;
int64_t f0f7_2 = f0_2 * (int64_t) f7;
int64_t f0f8_2 = f0_2 * (int64_t) f8;
int64_t f0f9_2 = f0_2 * (int64_t) f9;
int64_t f1f1_2 = f1_2 * (int64_t) f1;
int64_t f1f2_2 = f1_2 * (int64_t) f2;
int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
int64_t f1f4_2 = f1_2 * (int64_t) f4;
int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
int64_t f1f6_2 = f1_2 * (int64_t) f6;
int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
int64_t f1f8_2 = f1_2 * (int64_t) f8;
int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
int64_t f2f2 = f2 * (int64_t) f2;
int64_t f2f3_2 = f2_2 * (int64_t) f3;
int64_t f2f4_2 = f2_2 * (int64_t) f4;
int64_t f2f5_2 = f2_2 * (int64_t) f5;
int64_t f2f6_2 = f2_2 * (int64_t) f6;
int64_t f2f7_2 = f2_2 * (int64_t) f7;
int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
int64_t f2f9_38 = f2 * (int64_t) f9_38;
int64_t f3f3_2 = f3_2 * (int64_t) f3;
int64_t f3f4_2 = f3_2 * (int64_t) f4;
int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
int64_t f3f6_2 = f3_2 * (int64_t) f6;
int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
int64_t f4f4 = f4 * (int64_t) f4;
int64_t f4f5_2 = f4_2 * (int64_t) f5;
int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
int64_t f4f7_38 = f4 * (int64_t) f7_38;
int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
int64_t f4f9_38 = f4 * (int64_t) f9_38;
int64_t f5f5_38 = f5 * (int64_t) f5_38;
int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
int64_t f6f6_19 = f6 * (int64_t) f6_19;
int64_t f6f7_38 = f6 * (int64_t) f7_38;
int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
int64_t f6f9_38 = f6 * (int64_t) f9_38;
int64_t f7f7_38 = f7 * (int64_t) f7_38;
int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
int64_t f8f8_19 = f8 * (int64_t) f8_19;
int64_t f8f9_38 = f8 * (int64_t) f9_38;
int64_t f9f9_38 = f9 * (int64_t) f9_38;
int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;
int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;
int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
int64_t carry0;
int64_t carry1;
int64_t carry2;
int64_t carry3;
int64_t carry4;
int64_t carry5;
int64_t carry6;
int64_t carry7;
int64_t carry8;
int64_t carry9;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
h[0] = h0;
h[1] = h1;
h[2] = h2;
h[3] = h3;
h[4] = h4;
h[5] = h5;
h[6] = h6;
h[7] = h7;
h[8] = h8;
h[9] = h9;
}
static void fe_invert(fe out, const fe z) {
fe t0;
fe t1;
fe t2;
fe t3;
int i;
fe_sq(t0, z);
for (i = 1; i < 1; ++i) {
fe_sq(t0, t0);
}
fe_sq(t1, t0);
for (i = 1; i < 2; ++i) {
fe_sq(t1, t1);
}
fe_mul(t1, z, t1);
fe_mul(t0, t0, t1);
fe_sq(t2, t0);
for (i = 1; i < 1; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t1, t2);
fe_sq(t2, t1);
for (i = 1; i < 5; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t2, t1);
fe_sq(t2, t1);
for (i = 1; i < 10; ++i) {
fe_sq(t2, t2);
}
fe_mul(t2, t2, t1);
fe_sq(t3, t2);
for (i = 1; i < 20; ++i) {
fe_sq(t3, t3);
}
fe_mul(t2, t3, t2);
fe_sq(t2, t2);
for (i = 1; i < 10; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t2, t1);
fe_sq(t2, t1);
for (i = 1; i < 50; ++i) {
fe_sq(t2, t2);
}
fe_mul(t2, t2, t1);
fe_sq(t3, t2);
for (i = 1; i < 100; ++i) {
fe_sq(t3, t3);
}
fe_mul(t2, t3, t2);
fe_sq(t2, t2);
for (i = 1; i < 50; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t2, t1);
fe_sq(t1, t1);
for (i = 1; i < 5; ++i) {
fe_sq(t1, t1);
}
fe_mul(out, t1, t0);
}
/* h = f * 121666
* Can overlap h with f.
*
* Preconditions:
* |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc.
*
* Postconditions:
* |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. */
static void fe_mul121666(fe h, fe f) {
int32_t f0 = f[0];
int32_t f1 = f[1];
int32_t f2 = f[2];
int32_t f3 = f[3];
int32_t f4 = f[4];
int32_t f5 = f[5];
int32_t f6 = f[6];
int32_t f7 = f[7];
int32_t f8 = f[8];
int32_t f9 = f[9];
int64_t h0 = f0 * (int64_t) 121666;
int64_t h1 = f1 * (int64_t) 121666;
int64_t h2 = f2 * (int64_t) 121666;
int64_t h3 = f3 * (int64_t) 121666;
int64_t h4 = f4 * (int64_t) 121666;
int64_t h5 = f5 * (int64_t) 121666;
int64_t h6 = f6 * (int64_t) 121666;
int64_t h7 = f7 * (int64_t) 121666;
int64_t h8 = f8 * (int64_t) 121666;
int64_t h9 = f9 * (int64_t) 121666;
int64_t carry0;
int64_t carry1;
int64_t carry2;
int64_t carry3;
int64_t carry4;
int64_t carry5;
int64_t carry6;
int64_t carry7;
int64_t carry8;
int64_t carry9;
carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
h[0] = h0;
h[1] = h1;
h[2] = h2;
h[3] = h3;
h[4] = h4;
h[5] = h5;
h[6] = h6;
h[7] = h7;
h[8] = h8;
h[9] = h9;
}
/* Ed25519 support is disabled when built with |OPENSSL_SMALL|. */
#if !defined(OPENSSL_SMALL)
/* h = -f
*
* Preconditions:
* |f| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc.
*
* Postconditions:
* |h| bounded by 1.1*2^25,1.1*2^24,1.1*2^25,1.1*2^24,etc. */
static void fe_neg(fe h, const fe f) {
unsigned i;
for (i = 0; i < 10; i++) {
h[i] = -f[i];
}
}
/* Replace (f,g) with (g,g) if b == 1;
* replace (f,g) with (f,g) if b == 0.
*
* Preconditions: b in {0,1}. */
static void fe_cmov(fe f, const fe g, unsigned b) {
b = -b;
unsigned i;
for (i = 0; i < 10; i++) {
int32_t x = f[i] ^ g[i];
x &= b;
f[i] ^= x;
}
}
/* return 0 if f == 0
* return 1 if f != 0
*
* Preconditions:
* |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
static int fe_isnonzero(const fe f) {
uint8_t s[32];
fe_tobytes(s, f);
static const uint8_t zero[32] = {0};
return CRYPTO_memcmp(s, zero, sizeof(zero)) != 0;
}
/* return 1 if f is in {1,3,5,...,q-2}
* return 0 if f is in {0,2,4,...,q-1}
*
* Preconditions:
* |f| bounded by 1.1*2^26,1.1*2^25,1.1*2^26,1.1*2^25,etc. */
static int fe_isnegative(const fe f) {
uint8_t s[32];
fe_tobytes(s, f);
return s[0] & 1;
}
/* h = 2 * f * f
* Can overlap h with f.
*
* Preconditions:
* |f| bounded by 1.65*2^26,1.65*2^25,1.65*2^26,1.65*2^25,etc.
*
* Postconditions:
* |h| bounded by 1.01*2^25,1.01*2^24,1.01*2^25,1.01*2^24,etc.
*
* See fe_mul.c for discussion of implementation strategy. */
static void fe_sq2(fe h, const fe f) {
int32_t f0 = f[0];
int32_t f1 = f[1];
int32_t f2 = f[2];
int32_t f3 = f[3];
int32_t f4 = f[4];
int32_t f5 = f[5];
int32_t f6 = f[6];
int32_t f7 = f[7];
int32_t f8 = f[8];
int32_t f9 = f[9];
int32_t f0_2 = 2 * f0;
int32_t f1_2 = 2 * f1;
int32_t f2_2 = 2 * f2;
int32_t f3_2 = 2 * f3;
int32_t f4_2 = 2 * f4;
int32_t f5_2 = 2 * f5;
int32_t f6_2 = 2 * f6;
int32_t f7_2 = 2 * f7;
int32_t f5_38 = 38 * f5; /* 1.959375*2^30 */
int32_t f6_19 = 19 * f6; /* 1.959375*2^30 */
int32_t f7_38 = 38 * f7; /* 1.959375*2^30 */
int32_t f8_19 = 19 * f8; /* 1.959375*2^30 */
int32_t f9_38 = 38 * f9; /* 1.959375*2^30 */
int64_t f0f0 = f0 * (int64_t) f0;
int64_t f0f1_2 = f0_2 * (int64_t) f1;
int64_t f0f2_2 = f0_2 * (int64_t) f2;
int64_t f0f3_2 = f0_2 * (int64_t) f3;
int64_t f0f4_2 = f0_2 * (int64_t) f4;
int64_t f0f5_2 = f0_2 * (int64_t) f5;
int64_t f0f6_2 = f0_2 * (int64_t) f6;
int64_t f0f7_2 = f0_2 * (int64_t) f7;
int64_t f0f8_2 = f0_2 * (int64_t) f8;
int64_t f0f9_2 = f0_2 * (int64_t) f9;
int64_t f1f1_2 = f1_2 * (int64_t) f1;
int64_t f1f2_2 = f1_2 * (int64_t) f2;
int64_t f1f3_4 = f1_2 * (int64_t) f3_2;
int64_t f1f4_2 = f1_2 * (int64_t) f4;
int64_t f1f5_4 = f1_2 * (int64_t) f5_2;
int64_t f1f6_2 = f1_2 * (int64_t) f6;
int64_t f1f7_4 = f1_2 * (int64_t) f7_2;
int64_t f1f8_2 = f1_2 * (int64_t) f8;
int64_t f1f9_76 = f1_2 * (int64_t) f9_38;
int64_t f2f2 = f2 * (int64_t) f2;
int64_t f2f3_2 = f2_2 * (int64_t) f3;
int64_t f2f4_2 = f2_2 * (int64_t) f4;
int64_t f2f5_2 = f2_2 * (int64_t) f5;
int64_t f2f6_2 = f2_2 * (int64_t) f6;
int64_t f2f7_2 = f2_2 * (int64_t) f7;
int64_t f2f8_38 = f2_2 * (int64_t) f8_19;
int64_t f2f9_38 = f2 * (int64_t) f9_38;
int64_t f3f3_2 = f3_2 * (int64_t) f3;
int64_t f3f4_2 = f3_2 * (int64_t) f4;
int64_t f3f5_4 = f3_2 * (int64_t) f5_2;
int64_t f3f6_2 = f3_2 * (int64_t) f6;
int64_t f3f7_76 = f3_2 * (int64_t) f7_38;
int64_t f3f8_38 = f3_2 * (int64_t) f8_19;
int64_t f3f9_76 = f3_2 * (int64_t) f9_38;
int64_t f4f4 = f4 * (int64_t) f4;
int64_t f4f5_2 = f4_2 * (int64_t) f5;
int64_t f4f6_38 = f4_2 * (int64_t) f6_19;
int64_t f4f7_38 = f4 * (int64_t) f7_38;
int64_t f4f8_38 = f4_2 * (int64_t) f8_19;
int64_t f4f9_38 = f4 * (int64_t) f9_38;
int64_t f5f5_38 = f5 * (int64_t) f5_38;
int64_t f5f6_38 = f5_2 * (int64_t) f6_19;
int64_t f5f7_76 = f5_2 * (int64_t) f7_38;
int64_t f5f8_38 = f5_2 * (int64_t) f8_19;
int64_t f5f9_76 = f5_2 * (int64_t) f9_38;
int64_t f6f6_19 = f6 * (int64_t) f6_19;
int64_t f6f7_38 = f6 * (int64_t) f7_38;
int64_t f6f8_38 = f6_2 * (int64_t) f8_19;
int64_t f6f9_38 = f6 * (int64_t) f9_38;
int64_t f7f7_38 = f7 * (int64_t) f7_38;
int64_t f7f8_38 = f7_2 * (int64_t) f8_19;
int64_t f7f9_76 = f7_2 * (int64_t) f9_38;
int64_t f8f8_19 = f8 * (int64_t) f8_19;
int64_t f8f9_38 = f8 * (int64_t) f9_38;
int64_t f9f9_38 = f9 * (int64_t) f9_38;
int64_t h0 = f0f0 +f1f9_76+f2f8_38+f3f7_76+f4f6_38+f5f5_38;
int64_t h1 = f0f1_2+f2f9_38+f3f8_38+f4f7_38+f5f6_38;
int64_t h2 = f0f2_2+f1f1_2 +f3f9_76+f4f8_38+f5f7_76+f6f6_19;
int64_t h3 = f0f3_2+f1f2_2 +f4f9_38+f5f8_38+f6f7_38;
int64_t h4 = f0f4_2+f1f3_4 +f2f2 +f5f9_76+f6f8_38+f7f7_38;
int64_t h5 = f0f5_2+f1f4_2 +f2f3_2 +f6f9_38+f7f8_38;
int64_t h6 = f0f6_2+f1f5_4 +f2f4_2 +f3f3_2 +f7f9_76+f8f8_19;
int64_t h7 = f0f7_2+f1f6_2 +f2f5_2 +f3f4_2 +f8f9_38;
int64_t h8 = f0f8_2+f1f7_4 +f2f6_2 +f3f5_4 +f4f4 +f9f9_38;
int64_t h9 = f0f9_2+f1f8_2 +f2f7_2 +f3f6_2 +f4f5_2;
int64_t carry0;
int64_t carry1;
int64_t carry2;
int64_t carry3;
int64_t carry4;
int64_t carry5;
int64_t carry6;
int64_t carry7;
int64_t carry8;
int64_t carry9;
h0 += h0;
h1 += h1;
h2 += h2;
h3 += h3;
h4 += h4;
h5 += h5;
h6 += h6;
h7 += h7;
h8 += h8;
h9 += h9;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry1 = (h1 + (int64_t) (1<<24)) >> 25; h2 += carry1; h1 -= carry1 << 25;
carry5 = (h5 + (int64_t) (1<<24)) >> 25; h6 += carry5; h5 -= carry5 << 25;
carry2 = (h2 + (int64_t) (1<<25)) >> 26; h3 += carry2; h2 -= carry2 << 26;
carry6 = (h6 + (int64_t) (1<<25)) >> 26; h7 += carry6; h6 -= carry6 << 26;
carry3 = (h3 + (int64_t) (1<<24)) >> 25; h4 += carry3; h3 -= carry3 << 25;
carry7 = (h7 + (int64_t) (1<<24)) >> 25; h8 += carry7; h7 -= carry7 << 25;
carry4 = (h4 + (int64_t) (1<<25)) >> 26; h5 += carry4; h4 -= carry4 << 26;
carry8 = (h8 + (int64_t) (1<<25)) >> 26; h9 += carry8; h8 -= carry8 << 26;
carry9 = (h9 + (int64_t) (1<<24)) >> 25; h0 += carry9 * 19; h9 -= carry9 << 25;
carry0 = (h0 + (int64_t) (1<<25)) >> 26; h1 += carry0; h0 -= carry0 << 26;
h[0] = h0;
h[1] = h1;
h[2] = h2;
h[3] = h3;
h[4] = h4;
h[5] = h5;
h[6] = h6;
h[7] = h7;
h[8] = h8;
h[9] = h9;
}
static void fe_pow22523(fe out, const fe z) {
fe t0;
fe t1;
fe t2;
int i;
fe_sq(t0, z);
for (i = 1; i < 1; ++i) {
fe_sq(t0, t0);
}
fe_sq(t1, t0);
for (i = 1; i < 2; ++i) {
fe_sq(t1, t1);
}
fe_mul(t1, z, t1);
fe_mul(t0, t0, t1);
fe_sq(t0, t0);
for (i = 1; i < 1; ++i) {
fe_sq(t0, t0);
}
fe_mul(t0, t1, t0);
fe_sq(t1, t0);
for (i = 1; i < 5; ++i) {
fe_sq(t1, t1);
}
fe_mul(t0, t1, t0);
fe_sq(t1, t0);
for (i = 1; i < 10; ++i) {
fe_sq(t1, t1);
}
fe_mul(t1, t1, t0);
fe_sq(t2, t1);
for (i = 1; i < 20; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t2, t1);
fe_sq(t1, t1);
for (i = 1; i < 10; ++i) {
fe_sq(t1, t1);
}
fe_mul(t0, t1, t0);
fe_sq(t1, t0);
for (i = 1; i < 50; ++i) {
fe_sq(t1, t1);
}
fe_mul(t1, t1, t0);
fe_sq(t2, t1);
for (i = 1; i < 100; ++i) {
fe_sq(t2, t2);
}
fe_mul(t1, t2, t1);
fe_sq(t1, t1);
for (i = 1; i < 50; ++i) {
fe_sq(t1, t1);
}
fe_mul(t0, t1, t0);
fe_sq(t0, t0);
for (i = 1; i < 2; ++i) {
fe_sq(t0, t0);
}
fe_mul(out, t0, z);
}
/* ge means group element.
* Here the group is the set of pairs (x,y) of field elements (see fe.h)
* satisfying -x^2 + y^2 = 1 + d x^2y^2
* where d = -121665/121666.
*
* Representations:
* ge_p2 (projective): (X:Y:Z) satisfying x=X/Z, y=Y/Z
* ge_p3 (extended): (X:Y:Z:T) satisfying x=X/Z, y=Y/Z, XY=ZT
* ge_p1p1 (completed): ((X:Z),(Y:T)) satisfying x=X/Z, y=Y/T
* ge_precomp (Duif): (y+x,y-x,2dxy) */
typedef struct {
fe X;
fe Y;
fe Z;
} ge_p2;
typedef struct {
fe X;
fe Y;
fe Z;
fe T;
} ge_p3;
typedef struct {
fe X;
fe Y;
fe Z;
fe T;
} ge_p1p1;
typedef struct {
fe yplusx;
fe yminusx;
fe xy2d;
} ge_precomp;
typedef struct {
fe YplusX;
fe YminusX;
fe Z;
fe T2d;
} ge_cached;
static void ge_tobytes(uint8_t *s, const ge_p2 *h) {
fe recip;
fe x;
fe y;
fe_invert(recip, h->Z);
fe_mul(x, h->X, recip);
fe_mul(y, h->Y, recip);
fe_tobytes(s, y);
s[31] ^= fe_isnegative(x) << 7;
}
static void ge_p3_tobytes(uint8_t *s, const ge_p3 *h) {
fe recip;
fe x;
fe y;
fe_invert(recip, h->Z);
fe_mul(x, h->X, recip);
fe_mul(y, h->Y, recip);
fe_tobytes(s, y);
s[31] ^= fe_isnegative(x) << 7;
}
static const fe d = {-10913610, 13857413, -15372611, 6949391, 114729,
-8787816, -6275908, -3247719, -18696448, -12055116};
static const fe sqrtm1 = {-32595792, -7943725, 9377950, 3500415, 12389472,
-272473, -25146209, -2005654, 326686, 11406482};
static int ge_frombytes_negate_vartime(ge_p3 *h, const uint8_t *s) {
fe u;
fe v;
fe v3;
fe vxx;
fe check;
fe_frombytes(h->Y, s);
fe_1(h->Z);
fe_sq(u, h->Y);
fe_mul(v, u, d);
fe_sub(u, u, h->Z); /* u = y^2-1 */
fe_add(v, v, h->Z); /* v = dy^2+1 */
fe_sq(v3, v);
fe_mul(v3, v3, v); /* v3 = v^3 */
fe_sq(h->X, v3);
fe_mul(h->X, h->X, v);
fe_mul(h->X, h->X, u); /* x = uv^7 */
fe_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */
fe_mul(h->X, h->X, v3);
fe_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */
fe_sq(vxx, h->X);
fe_mul(vxx, vxx, v);
fe_sub(check, vxx, u); /* vx^2-u */
if (fe_isnonzero(check)) {
fe_add(check, vxx, u); /* vx^2+u */
if (fe_isnonzero(check)) {
return -1;
}
fe_mul(h->X, h->X, sqrtm1);
}
if (fe_isnegative(h->X) == (s[31] >> 7)) {
fe_neg(h->X, h->X);
}
fe_mul(h->T, h->X, h->Y);
return 0;
}
static void ge_p2_0(ge_p2 *h) {
fe_0(h->X);
fe_1(h->Y);
fe_1(h->Z);
}
static void ge_p3_0(ge_p3 *h) {
fe_0(h->X);
fe_1(h->Y);
fe_1(h->Z);
fe_0(h->T);
}
static void ge_precomp_0(ge_precomp *h) {
fe_1(h->yplusx);
fe_1(h->yminusx);
fe_0(h->xy2d);
}
/* r = p */
static void ge_p3_to_p2(ge_p2 *r, const ge_p3 *p) {
fe_copy(r->X, p->X);
fe_copy(r->Y, p->Y);
fe_copy(r->Z, p->Z);
}
static const fe d2 = {-21827239, -5839606, -30745221, 13898782, 229458,
15978800, -12551817, -6495438, 29715968, 9444199};
/* r = p */
static void ge_p3_to_cached(ge_cached *r, const ge_p3 *p) {
fe_add(r->YplusX, p->Y, p->X);
fe_sub(r->YminusX, p->Y, p->X);
fe_copy(r->Z, p->Z);
fe_mul(r->T2d, p->T, d2);
}
/* r = p */
static void ge_p1p1_to_p2(ge_p2 *r, const ge_p1p1 *p) {
fe_mul(r->X, p->X, p->T);
fe_mul(r->Y, p->Y, p->Z);
fe_mul(r->Z, p->Z, p->T);
}
/* r = p */
static void ge_p1p1_to_p3(ge_p3 *r, const ge_p1p1 *p) {
fe_mul(r->X, p->X, p->T);
fe_mul(r->Y, p->Y, p->Z);
fe_mul(r->Z, p->Z, p->T);
fe_mul(r->T, p->X, p->Y);
}
/* r = 2 * p */
static void ge_p2_dbl(ge_p1p1 *r, const ge_p2 *p) {
fe t0;
fe_sq(r->X, p->X);
fe_sq(r->Z, p->Y);
fe_sq2(r->T, p->Z);
fe_add(r->Y, p->X, p->Y);
fe_sq(t0, r->Y);
fe_add(r->Y, r->Z, r->X);
fe_sub(r->Z, r->Z, r->X);
fe_sub(r->X, t0, r->Y);
fe_sub(r->T, r->T, r->Z);
}
/* r = 2 * p */
static void ge_p3_dbl(ge_p1p1 *r, const ge_p3 *p) {
ge_p2 q;
ge_p3_to_p2(&q, p);
ge_p2_dbl(r, &q);
}
/* r = p + q */
static void ge_madd(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
fe t0;
fe_add(r->X, p->Y, p->X);
fe_sub(r->Y, p->Y, p->X);
fe_mul(r->Z, r->X, q->yplusx);
fe_mul(r->Y, r->Y, q->yminusx);
fe_mul(r->T, q->xy2d, p->T);
fe_add(t0, p->Z, p->Z);
fe_sub(r->X, r->Z, r->Y);
fe_add(r->Y, r->Z, r->Y);
fe_add(r->Z, t0, r->T);
fe_sub(r->T, t0, r->T);
}
/* r = p - q */
static void ge_msub(ge_p1p1 *r, const ge_p3 *p, const ge_precomp *q) {
fe t0;
fe_add(r->X, p->Y, p->X);
fe_sub(r->Y, p->Y, p->X);
fe_mul(r->Z, r->X, q->yminusx);
fe_mul(r->Y, r->Y, q->yplusx);
fe_mul(r->T, q->xy2d, p->T);
fe_add(t0, p->Z, p->Z);
fe_sub(r->X, r->Z, r->Y);
fe_add(r->Y, r->Z, r->Y);
fe_sub(r->Z, t0, r->T);
fe_add(r->T, t0, r->T);
}
/* r = p + q */
static void ge_add(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
fe t0;
fe_add(r->X, p->Y, p->X);
fe_sub(r->Y, p->Y, p->X);
fe_mul(r->Z, r->X, q->YplusX);
fe_mul(r->Y, r->Y, q->YminusX);
fe_mul(r->T, q->T2d, p->T);
fe_mul(r->X, p->Z, q->Z);
fe_add(t0, r->X, r->X);
fe_sub(r->X, r->Z, r->Y);
fe_add(r->Y, r->Z, r->Y);
fe_add(r->Z, t0, r->T);
fe_sub(r->T, t0, r->T);
}
/* r = p - q */
static void ge_sub(ge_p1p1 *r, const ge_p3 *p, const ge_cached *q) {
fe t0;
fe_add(r->X, p->Y, p->X);
fe_sub(r->Y, p->Y, p->X);
fe_mul(r->Z, r->X, q->YminusX);
fe_mul(r->Y, r->Y, q->YplusX);
fe_mul(r->T, q->T2d, p->T);
fe_mul(r->X, p->Z, q->Z);
fe_add(t0, r->X, r->X);
fe_sub(r->X, r->Z, r->Y);
fe_add(r->Y, r->Z, r->Y);
fe_sub(r->Z, t0, r->T);
fe_add(r->T, t0, r->T);
}
static uint8_t equal(signed char b, signed char c) {
uint8_t ub = b;
uint8_t uc = c;
uint8_t x = ub ^ uc; /* 0: yes; 1..255: no */
uint32_t y = x; /* 0: yes; 1..255: no */
y -= 1; /* 4294967295: yes; 0..254: no */
y >>= 31; /* 1: yes; 0: no */
return y;
}
static void cmov(ge_precomp *t, ge_precomp *u, uint8_t b) {
fe_cmov(t->yplusx, u->yplusx, b);
fe_cmov(t->yminusx, u->yminusx, b);
fe_cmov(t->xy2d, u->xy2d, b);
}
#if 0
/* At the moment, building with |OPENSSL_SMALL| causes Ed25519 to be disabled.
* In the future we might enable it but, in that case, we'll still probably
* want to keep the size down. This block of code replaces the standard
* base-point table with a much smaller one. The standard table is 30,720 bytes
* while this one is just 960.
*
* This table contains 15 pairs of group elements, (x, y), where each field
* element is serialised with |fe_tobytes|. If |i| is the index of the group
* element then consider i+1 as a four-bit number: (i₀, i₁, i₂, i₃) (where i₀
* is the most significant bit). The value of the group element is then:
* (i₀×2^192 + i₁×2^128 + i₂×2^64 + i₃)G, where G is the generator. */
static const uint8_t kSmallPrecomp[15 * 2 * 32] = {
0x1a, 0xd5, 0x25, 0x8f, 0x60, 0x2d, 0x56, 0xc9, 0xb2, 0xa7, 0x25, 0x95,
0x60, 0xc7, 0x2c, 0x69, 0x5c, 0xdc, 0xd6, 0xfd, 0x31, 0xe2, 0xa4, 0xc0,
0xfe, 0x53, 0x6e, 0xcd, 0xd3, 0x36, 0x69, 0x21, 0x58, 0x66, 0x66, 0x66,
0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66, 0x66,
0x66, 0x66, 0x66, 0x66, 0x02, 0xa2, 0xed, 0xf4, 0x8f, 0x6b, 0x0b, 0x3e,
0xeb, 0x35, 0x1a, 0xd5, 0x7e, 0xdb, 0x78, 0x00, 0x96, 0x8a, 0xa0, 0xb4,
0xcf, 0x60, 0x4b, 0xd4, 0xd5, 0xf9, 0x2d, 0xbf, 0x88, 0xbd, 0x22, 0x62,
0x13, 0x53, 0xe4, 0x82, 0x57, 0xfa, 0x1e, 0x8f, 0x06, 0x2b, 0x90, 0xba,
0x08, 0xb6, 0x10, 0x54, 0x4f, 0x7c, 0x1b, 0x26, 0xed, 0xda, 0x6b, 0xdd,
0x25, 0xd0, 0x4e, 0xea, 0x42, 0xbb, 0x25, 0x03, 0xa2, 0xfb, 0xcc, 0x61,
0x67, 0x06, 0x70, 0x1a, 0xc4, 0x78, 0x3a, 0xff, 0x32, 0x62, 0xdd, 0x2c,
0xab, 0x50, 0x19, 0x3b, 0xf2, 0x9b, 0x7d, 0xb8, 0xfd, 0x4f, 0x29, 0x9c,
0xa7, 0x91, 0xba, 0x0e, 0x46, 0x5e, 0x51, 0xfe, 0x1d, 0xbf, 0xe5, 0xe5,
0x9b, 0x95, 0x0d, 0x67, 0xf8, 0xd1, 0xb5, 0x5a, 0xa1, 0x93, 0x2c, 0xc3,
0xde, 0x0e, 0x97, 0x85, 0x2d, 0x7f, 0xea, 0xab, 0x3e, 0x47, 0x30, 0x18,
0x24, 0xe8, 0xb7, 0x60, 0xae, 0x47, 0x80, 0xfc, 0xe5, 0x23, 0xe7, 0xc2,
0xc9, 0x85, 0xe6, 0x98, 0xa0, 0x29, 0x4e, 0xe1, 0x84, 0x39, 0x2d, 0x95,
0x2c, 0xf3, 0x45, 0x3c, 0xff, 0xaf, 0x27, 0x4c, 0x6b, 0xa6, 0xf5, 0x4b,
0x11, 0xbd, 0xba, 0x5b, 0x9e, 0xc4, 0xa4, 0x51, 0x1e, 0xbe, 0xd0, 0x90,
0x3a, 0x9c, 0xc2, 0x26, 0xb6, 0x1e, 0xf1, 0x95, 0x7d, 0xc8, 0x6d, 0x52,
0xe6, 0x99, 0x2c, 0x5f, 0x9a, 0x96, 0x0c, 0x68, 0x29, 0xfd, 0xe2, 0xfb,
0xe6, 0xbc, 0xec, 0x31, 0x08, 0xec, 0xe6, 0xb0, 0x53, 0x60, 0xc3, 0x8c,
0xbe, 0xc1, 0xb3, 0x8a, 0x8f, 0xe4, 0x88, 0x2b, 0x55, 0xe5, 0x64, 0x6e,
0x9b, 0xd0, 0xaf, 0x7b, 0x64, 0x2a, 0x35, 0x25, 0x10, 0x52, 0xc5, 0x9e,
0x58, 0x11, 0x39, 0x36, 0x45, 0x51, 0xb8, 0x39, 0x93, 0xfc, 0x9d, 0x6a,
0xbe, 0x58, 0xcb, 0xa4, 0x0f, 0x51, 0x3c, 0x38, 0x05, 0xca, 0xab, 0x43,
0x63, 0x0e, 0xf3, 0x8b, 0x41, 0xa6, 0xf8, 0x9b, 0x53, 0x70, 0x80, 0x53,
0x86, 0x5e, 0x8f, 0xe3, 0xc3, 0x0d, 0x18, 0xc8, 0x4b, 0x34, 0x1f, 0xd8,
0x1d, 0xbc, 0xf2, 0x6d, 0x34, 0x3a, 0xbe, 0xdf, 0xd9, 0xf6, 0xf3, 0x89,
0xa1, 0xe1, 0x94, 0x9f, 0x5d, 0x4c, 0x5d, 0xe9, 0xa1, 0x49, 0x92, 0xef,
0x0e, 0x53, 0x81, 0x89, 0x58, 0x87, 0xa6, 0x37, 0xf1, 0xdd, 0x62, 0x60,
0x63, 0x5a, 0x9d, 0x1b, 0x8c, 0xc6, 0x7d, 0x52, 0xea, 0x70, 0x09, 0x6a,
0xe1, 0x32, 0xf3, 0x73, 0x21, 0x1f, 0x07, 0x7b, 0x7c, 0x9b, 0x49, 0xd8,
0xc0, 0xf3, 0x25, 0x72, 0x6f, 0x9d, 0xed, 0x31, 0x67, 0x36, 0x36, 0x54,
0x40, 0x92, 0x71, 0xe6, 0x11, 0x28, 0x11, 0xad, 0x93, 0x32, 0x85, 0x7b,
0x3e, 0xb7, 0x3b, 0x49, 0x13, 0x1c, 0x07, 0xb0, 0x2e, 0x93, 0xaa, 0xfd,
0xfd, 0x28, 0x47, 0x3d, 0x8d, 0xd2, 0xda, 0xc7, 0x44, 0xd6, 0x7a, 0xdb,
0x26, 0x7d, 0x1d, 0xb8, 0xe1, 0xde, 0x9d, 0x7a, 0x7d, 0x17, 0x7e, 0x1c,
0x37, 0x04, 0x8d, 0x2d, 0x7c, 0x5e, 0x18, 0x38, 0x1e, 0xaf, 0xc7, 0x1b,
0x33, 0x48, 0x31, 0x00, 0x59, 0xf6, 0xf2, 0xca, 0x0f, 0x27, 0x1b, 0x63,
0x12, 0x7e, 0x02, 0x1d, 0x49, 0xc0, 0x5d, 0x79, 0x87, 0xef, 0x5e, 0x7a,
0x2f, 0x1f, 0x66, 0x55, 0xd8, 0x09, 0xd9, 0x61, 0x38, 0x68, 0xb0, 0x07,
0xa3, 0xfc, 0xcc, 0x85, 0x10, 0x7f, 0x4c, 0x65, 0x65, 0xb3, 0xfa, 0xfa,
0xa5, 0x53, 0x6f, 0xdb, 0x74, 0x4c, 0x56, 0x46, 0x03, 0xe2, 0xd5, 0x7a,
0x29, 0x1c, 0xc6, 0x02, 0xbc, 0x59, 0xf2, 0x04, 0x75, 0x63, 0xc0, 0x84,
0x2f, 0x60, 0x1c, 0x67, 0x76, 0xfd, 0x63, 0x86, 0xf3, 0xfa, 0xbf, 0xdc,
0xd2, 0x2d, 0x90, 0x91, 0xbd, 0x33, 0xa9, 0xe5, 0x66, 0x0c, 0xda, 0x42,
0x27, 0xca, 0xf4, 0x66, 0xc2, 0xec, 0x92, 0x14, 0x57, 0x06, 0x63, 0xd0,
0x4d, 0x15, 0x06, 0xeb, 0x69, 0x58, 0x4f, 0x77, 0xc5, 0x8b, 0xc7, 0xf0,
0x8e, 0xed, 0x64, 0xa0, 0xb3, 0x3c, 0x66, 0x71, 0xc6, 0x2d, 0xda, 0x0a,
0x0d, 0xfe, 0x70, 0x27, 0x64, 0xf8, 0x27, 0xfa, 0xf6, 0x5f, 0x30, 0xa5,
0x0d, 0x6c, 0xda, 0xf2, 0x62, 0x5e, 0x78, 0x47, 0xd3, 0x66, 0x00, 0x1c,
0xfd, 0x56, 0x1f, 0x5d, 0x3f, 0x6f, 0xf4, 0x4c, 0xd8, 0xfd, 0x0e, 0x27,
0xc9, 0x5c, 0x2b, 0xbc, 0xc0, 0xa4, 0xe7, 0x23, 0x29, 0x02, 0x9f, 0x31,
0xd6, 0xe9, 0xd7, 0x96, 0xf4, 0xe0, 0x5e, 0x0b, 0x0e, 0x13, 0xee, 0x3c,
0x09, 0xed, 0xf2, 0x3d, 0x76, 0x91, 0xc3, 0xa4, 0x97, 0xae, 0xd4, 0x87,
0xd0, 0x5d, 0xf6, 0x18, 0x47, 0x1f, 0x1d, 0x67, 0xf2, 0xcf, 0x63, 0xa0,
0x91, 0x27, 0xf8, 0x93, 0x45, 0x75, 0x23, 0x3f, 0xd1, 0xf1, 0xad, 0x23,
0xdd, 0x64, 0x93, 0x96, 0x41, 0x70, 0x7f, 0xf7, 0xf5, 0xa9, 0x89, 0xa2,
0x34, 0xb0, 0x8d, 0x1b, 0xae, 0x19, 0x15, 0x49, 0x58, 0x23, 0x6d, 0x87,
0x15, 0x4f, 0x81, 0x76, 0xfb, 0x23, 0xb5, 0xea, 0xcf, 0xac, 0x54, 0x8d,
0x4e, 0x42, 0x2f, 0xeb, 0x0f, 0x63, 0xdb, 0x68, 0x37, 0xa8, 0xcf, 0x8b,
0xab, 0xf5, 0xa4, 0x6e, 0x96, 0x2a, 0xb2, 0xd6, 0xbe, 0x9e, 0xbd, 0x0d,
0xb4, 0x42, 0xa9, 0xcf, 0x01, 0x83, 0x8a, 0x17, 0x47, 0x76, 0xc4, 0xc6,
0x83, 0x04, 0x95, 0x0b, 0xfc, 0x11, 0xc9, 0x62, 0xb8, 0x0c, 0x76, 0x84,
0xd9, 0xb9, 0x37, 0xfa, 0xfc, 0x7c, 0xc2, 0x6d, 0x58, 0x3e, 0xb3, 0x04,
0xbb, 0x8c, 0x8f, 0x48, 0xbc, 0x91, 0x27, 0xcc, 0xf9, 0xb7, 0x22, 0x19,
0x83, 0x2e, 0x09, 0xb5, 0x72, 0xd9, 0x54, 0x1c, 0x4d, 0xa1, 0xea, 0x0b,
0xf1, 0xc6, 0x08, 0x72, 0x46, 0x87, 0x7a, 0x6e, 0x80, 0x56, 0x0a, 0x8a,
0xc0, 0xdd, 0x11, 0x6b, 0xd6, 0xdd, 0x47, 0xdf, 0x10, 0xd9, 0xd8, 0xea,
0x7c, 0xb0, 0x8f, 0x03, 0x00, 0x2e, 0xc1, 0x8f, 0x44, 0xa8, 0xd3, 0x30,
0x06, 0x89, 0xa2, 0xf9, 0x34, 0xad, 0xdc, 0x03, 0x85, 0xed, 0x51, 0xa7,
0x82, 0x9c, 0xe7, 0x5d, 0x52, 0x93, 0x0c, 0x32, 0x9a, 0x5b, 0xe1, 0xaa,
0xca, 0xb8, 0x02, 0x6d, 0x3a, 0xd4, 0xb1, 0x3a, 0xf0, 0x5f, 0xbe, 0xb5,
0x0d, 0x10, 0x6b, 0x38, 0x32, 0xac, 0x76, 0x80, 0xbd, 0xca, 0x94, 0x71,
0x7a, 0xf2, 0xc9, 0x35, 0x2a, 0xde, 0x9f, 0x42, 0x49, 0x18, 0x01, 0xab,
0xbc, 0xef, 0x7c, 0x64, 0x3f, 0x58, 0x3d, 0x92, 0x59, 0xdb, 0x13, 0xdb,
0x58, 0x6e, 0x0a, 0xe0, 0xb7, 0x91, 0x4a, 0x08, 0x20, 0xd6, 0x2e, 0x3c,
0x45, 0xc9, 0x8b, 0x17, 0x79, 0xe7, 0xc7, 0x90, 0x99, 0x3a, 0x18, 0x25,
};
static void ge_scalarmult_base(ge_p3 *h, const uint8_t a[32]) {
/* kSmallPrecomp is first expanded into matching |ge_precomp| elements. */
ge_precomp multiples[15];
unsigned i;
for (i = 0; i < 15; i++) {
const uint8_t *bytes = &kSmallPrecomp[i*(2 * 32)];
fe x, y;
fe_frombytes(x, bytes);
fe_frombytes(y, bytes + 32);
ge_precomp *out = &multiples[i];
fe_add(out->yplusx, y, x);
fe_sub(out->yminusx, y, x);
fe_mul(out->xy2d, x, y);
fe_mul(out->xy2d, out->xy2d, d2);
}
/* See the comment above |kSmallPrecomp| about the structure of the
* precomputed elements. This loop does 64 additions and 64 doublings to
* calculate the result. */
ge_p3_0(h);
for (i = 63; i < 64; i--) {
unsigned j;
signed char index = 0;
for (j = 0; j < 4; j++) {
const uint8_t bit = 1 & (a[(8 * j) + (i / 8)] >> (i & 7));
index |= (bit << j);
}
ge_precomp e;
ge_precomp_0(&e);
for (j = 1; j < 16; j++) {
cmov(&e, &multiples[j-1], equal(index, j));
}
ge_cached cached;
ge_p1p1 r;
ge_p3_to_cached(&cached, h);
ge_add(&r, h, &cached);
ge_p1p1_to_p3(h, &r);
ge_madd(&r, h, &e);
ge_p1p1_to_p3(h, &r);
}
}
#else
/* base[i][j] = (j+1)*256^i*B */
static ge_precomp base[32][8] = {
{
{
{25967493, -14356035, 29566456, 3660896, -12694345, 4014787,
27544626, -11754271, -6079156, 2047605},
{-12545711, 934262, -2722910, 3049990, -727428, 9406986, 12720692,
5043384, 19500929, -15469378},
{-8738181, 4489570, 9688441, -14785194, 10184609, -12363380,
29287919, 11864899, -24514362, -4438546},
},
{
{-12815894, -12976347, -21581243, 11784320, -25355658, -2750717,
-11717903, -3814571, -358445, -10211303},
{-21703237, 6903825, 27185491, 6451973, -29577724, -9554005,
-15616551, 11189268, -26829678, -5319081},
{26966642, 11152617, 32442495, 15396054, 14353839, -12752335,
-3128826, -9541118, -15472047, -4166697},
},
{
{15636291, -9688557, 24204773, -7912398, 616977, -16685262,
27787600, -14772189, 28944400, -1550024},
{16568933, 4717097, -11556148, -1102322, 15682896, -11807043,
16354577, -11775962, 7689662, 11199574},
{30464156, -5976125, -11779434, -15670865, 23220365, 15915852,
7512774, 10017326, -17749093, -9920357},
},
{
{-17036878, 13921892, 10945806, -6033431, 27105052, -16084379,
-28926210, 15006023, 3284568, -6276540},
{23599295, -8306047, -11193664, -7687416, 13236774, 10506355,
7464579, 9656445, 13059162, 10374397},
{7798556, 16710257, 3033922, 2874086, 28997861, 2835604, 32406664,
-3839045, -641708, -101325},
},
{
{10861363, 11473154, 27284546, 1981175, -30064349, 12577861,
32867885, 14515107, -15438304, 10819380},
{4708026, 6336745, 20377586, 9066809, -11272109, 6594696, -25653668,
12483688, -12668491, 5581306},
{19563160, 16186464, -29386857, 4097519, 10237984, -4348115,
28542350, 13850243, -23678021, -15815942},
},
{
{-15371964, -12862754, 32573250, 4720197, -26436522, 5875511,
-19188627, -15224819, -9818940, -12085777},
{-8549212, 109983, 15149363, 2178705, 22900618, 4543417, 3044240,
-15689887, 1762328, 14866737},
{-18199695, -15951423, -10473290, 1707278, -17185920, 3916101,
-28236412, 3959421, 27914454, 4383652},
},
{
{5153746, 9909285, 1723747, -2777874, 30523605, 5516873, 19480852,
5230134, -23952439, -15175766},
{-30269007, -3463509, 7665486, 10083793, 28475525, 1649722,
20654025, 16520125, 30598449, 7715701},
{28881845, 14381568, 9657904, 3680757, -20181635, 7843316,
-31400660, 1370708, 29794553, -1409300},
},
{
{14499471, -2729599, -33191113, -4254652, 28494862, 14271267,
30290735, 10876454, -33154098, 2381726},
{-7195431, -2655363, -14730155, 462251, -27724326, 3941372,
-6236617, 3696005, -32300832, 15351955},
{27431194, 8222322, 16448760, -3907995, -18707002, 11938355,
-32961401, -2970515, 29551813, 10109425},
},
},
{
{
{-13657040, -13155431, -31283750, 11777098, 21447386, 6519384,
-2378284, -1627556, 10092783, -4764171},
{27939166, 14210322, 4677035, 16277044, -22964462, -12398139,
-32508754, 12005538, -17810127, 12803510},
{17228999, -15661624, -1233527, 300140, -1224870, -11714777,
30364213, -9038194, 18016357, 4397660},
},
{
{-10958843, -7690207, 4776341, -14954238, 27850028, -15602212,
-26619106, 14544525, -17477504, 982639},
{29253598, 15796703, -2863982, -9908884, 10057023, 3163536, 7332899,
-4120128, -21047696, 9934963},
{5793303, 16271923, -24131614, -10116404, 29188560, 1206517,
-14747930, 4559895, -30123922, -10897950},
},
{
{-27643952, -11493006, 16282657, -11036493, 28414021, -15012264,
24191034, 4541697, -13338309, 5500568},
{12650548, -1497113, 9052871, 11355358, -17680037, -8400164,
-17430592, 12264343, 10874051, 13524335},
{25556948, -3045990, 714651, 2510400, 23394682, -10415330, 33119038,
5080568, -22528059, 5376628},
},
{
{-26088264, -4011052, -17013699, -3537628, -6726793, 1920897,
-22321305, -9447443, 4535768, 1569007},
{-2255422, 14606630, -21692440, -8039818, 28430649, 8775819,
-30494562, 3044290, 31848280, 12543772},
{-22028579, 2943893, -31857513, 6777306, 13784462, -4292203,
-27377195, -2062731, 7718482, 14474653},
},
{
{2385315, 2454213, -22631320, 46603, -4437935, -15680415, 656965,
-7236665, 24316168, -5253567},
{13741529, 10911568, -33233417, -8603737, -20177830, -1033297,
33040651, -13424532, -20729456, 8321686},
{21060490, -2212744, 15712757, -4336099, 1639040, 10656336,
23845965, -11874838, -9984458, 608372},
},
{
{-13672732, -15087586, -10889693, -7557059, -6036909, 11305547,
1123968, -6780577, 27229399, 23887},
{-23244140, -294205, -11744728, 14712571, -29465699, -2029617,
12797024, -6440308, -1633405, 16678954},
{-29500620, 4770662, -16054387, 14001338, 7830047, 9564805,
-1508144, -4795045, -17169265, 4904953},
},
{
{24059557, 14617003, 19037157, -15039908, 19766093, -14906429,
5169211, 16191880, 2128236, -4326833},
{-16981152, 4124966, -8540610, -10653797, 30336522, -14105247,
-29806336, 916033, -6882542, -2986532},
{-22630907, 12419372, -7134229, -7473371, -16478904, 16739175,
285431, 2763829, 15736322, 4143876},
},
{
{2379352, 11839345, -4110402, -5988665, 11274298, 794957, 212801,
-14594663, 23527084, -16458268},
{33431127, -11130478, -17838966, -15626900, 8909499, 8376530,
-32625340, 4087881, -15188911, -14416214},
{1767683, 7197987, -13205226, -2022635, -13091350, 448826, 5799055,
4357868, -4774191, -16323038},
},
},
{
{
{6721966, 13833823, -23523388, -1551314, 26354293, -11863321,
23365147, -3949732, 7390890, 2759800},
{4409041, 2052381, 23373853, 10530217, 7676779, -12885954, 21302353,
-4264057, 1244380, -12919645},
{-4421239, 7169619, 4982368, -2957590, 30256825, -2777540, 14086413,
9208236, 15886429, 16489664},
},
{
{1996075, 10375649, 14346367, 13311202, -6874135, -16438411,
-13693198, 398369, -30606455, -712933},
{-25307465, 9795880, -2777414, 14878809, -33531835, 14780363,
13348553, 12076947, -30836462, 5113182},
{-17770784, 11797796, 31950843, 13929123, -25888302, 12288344,
-30341101, -7336386, 13847711, 5387222},
},
{
{-18582163, -3416217, 17824843, -2340966, 22744343, -10442611,
8763061, 3617786, -19600662, 10370991},
{20246567, -14369378, 22358229, -543712, 18507283, -10413996,
14554437, -8746092, 32232924, 16763880},
{9648505, 10094563, 26416693, 14745928, -30374318, -6472621,
11094161, 15689506, 3140038, -16510092},
},
{
{-16160072, 5472695, 31895588, 4744994, 8823515, 10365685,
-27224800, 9448613, -28774454, 366295},
{19153450, 11523972, -11096490, -6503142, -24647631, 5420647,
28344573, 8041113, 719605, 11671788},
{8678025, 2694440, -6808014, 2517372, 4964326, 11152271, -15432916,
-15266516, 27000813, -10195553},
},
{
{-15157904, 7134312, 8639287, -2814877, -7235688, 10421742, 564065,
5336097, 6750977, -14521026},
{11836410, -3979488, 26297894, 16080799, 23455045, 15735944,
1695823, -8819122, 8169720, 16220347},
{-18115838, 8653647, 17578566, -6092619, -8025777, -16012763,
-11144307, -2627664, -5990708, -14166033},
},
{
{-23308498, -10968312, 15213228, -10081214, -30853605, -11050004,
27884329, 2847284, 2655861, 1738395},
{-27537433, -14253021, -25336301, -8002780, -9370762, 8129821,
21651608, -3239336, -19087449, -11005278},
{1533110, 3437855, 23735889, 459276, 29970501, 11335377, 26030092,
5821408, 10478196, 8544890},
},
{
{32173121, -16129311, 24896207, 3921497, 22579056, -3410854,
19270449, 12217473, 17789017, -3395995},
{-30552961, -2228401, -15578829, -10147201, 13243889, 517024,
15479401, -3853233, 30460520, 1052596},
{-11614875, 13323618, 32618793, 8175907, -15230173, 12596687,
27491595, -4612359, 3179268, -9478891},
},
{
{31947069, -14366651, -4640583, -15339921, -15125977, -6039709,
-14756777, -16411740, 19072640, -9511060},
{11685058, 11822410, 3158003, -13952594, 33402194, -4165066,
5977896, -5215017, 473099, 5040608},
{-20290863, 8198642, -27410132, 11602123, 1290375, -2799760,
28326862, 1721092, -19558642, -3131606},
},
},
{
{
{7881532, 10687937, 7578723, 7738378, -18951012, -2553952, 21820786,
8076149, -27868496, 11538389},
{-19935666, 3899861, 18283497, -6801568, -15728660, -11249211,
8754525, 7446702, -5676054, 5797016},
{-11295600, -3793569, -15782110, -7964573, 12708869, -8456199,
2014099, -9050574, -2369172, -5877341},
},
{
{-22472376, -11568741, -27682020, 1146375, 18956691, 16640559,
1192730, -3714199, 15123619, 10811505},
{14352098, -3419715, -18942044, 10822655, 32750596, 4699007, -70363,
15776356, -28886779, -11974553},
{-28241164, -8072475, -4978962, -5315317, 29416931, 1847569,
-20654173, -16484855, 4714547, -9600655},
},
{
{15200332, 8368572, 19679101, 15970074, -31872674, 1959451,
24611599, -4543832, -11745876, 12340220},
{12876937, -10480056, 33134381, 6590940, -6307776, 14872440,
9613953, 8241152, 15370987, 9608631},
{-4143277, -12014408, 8446281, -391603, 4407738, 13629032, -7724868,
15866074, -28210621, -8814099},
},
{
{26660628, -15677655, 8393734, 358047, -7401291, 992988, -23904233,
858697, 20571223, 8420556},
{14620715, 13067227, -15447274, 8264467, 14106269, 15080814,
33531827, 12516406, -21574435, -12476749},
{236881, 10476226, 57258, -14677024, 6472998, 2466984, 17258519,
7256740, 8791136, 15069930},
},
{
{1276410, -9371918, 22949635, -16322807, -23493039, -5702186,
14711875, 4874229, -30663140, -2331391},
{5855666, 4990204, -13711848, 7294284, -7804282, 1924647, -1423175,
-7912378, -33069337, 9234253},
{20590503, -9018988, 31529744, -7352666, -2706834, 10650548,
31559055, -11609587, 18979186, 13396066},
},
{
{24474287, 4968103, 22267082, 4407354, 24063882, -8325180,
-18816887, 13594782, 33514650, 7021958},
{-11566906, -6565505, -21365085, 15928892, -26158305, 4315421,
-25948728, -3916677, -21480480, 12868082},
{-28635013, 13504661, 19988037, -2132761, 21078225, 6443208,
-21446107, 2244500, -12455797, -8089383},
},
{
{-30595528, 13793479, -5852820, 319136, -25723172, -6263899,
33086546, 8957937, -15233648, 5540521},
{-11630176, -11503902, -8119500, -7643073, 2620056, 1022908,
-23710744, -1568984, -16128528, -14962807},
{23152971, 775386, 27395463, 14006635, -9701118, 4649512, 1689819,
892185, -11513277, -15205948},
},
{
{9770129, 9586738, 26496094, 4324120, 1556511, -3550024, 27453819,
4763127, -19179614, 5867134},
{-32765025, 1927590, 31726409, -4753295, 23962434, -16019500,
27846559, 5931263, -29749703, -16108455},
{27461885, -2977536, 22380810, 1815854, -23033753, -3031938,
7283490, -15148073, -19526700, 7734629},
},
},
{
{
{-8010264, -9590817, -11120403, 6196038, 29344158, -13430885,
7585295, -3176626, 18549497, 15302069},
{-32658337, -6171222, -7672793, -11051681, 6258878, 13504381,
10458790, -6418461, -8872242, 8424746},
{24687205, 8613276, -30667046, -3233545, 1863892, -1830544,
19206234, 7134917, -11284482, -828919},
},
{
{11334899, -9218022, 8025293, 12707519, 17523892, -10476071,
10243738, -14685461, -5066034, 16498837},
{8911542, 6887158, -9584260, -6958590, 11145641, -9543680, 17303925,
-14124238, 6536641, 10543906},
{-28946384, 15479763, -17466835, 568876, -1497683, 11223454,
-2669190, -16625574, -27235709, 8876771},
},
{
{-25742899, -12566864, -15649966, -846607, -33026686, -796288,
-33481822, 15824474, -604426, -9039817},
{10330056, 70051, 7957388, -9002667, 9764902, 15609756, 27698697,
-4890037, 1657394, 3084098},
{10477963, -7470260, 12119566, -13250805, 29016247, -5365589,
31280319, 14396151, -30233575, 15272409},
},
{
{-12288309, 3169463, 28813183, 16658753, 25116432, -5630466,
-25173957, -12636138, -25014757, 1950504},
{-26180358, 9489187, 11053416, -14746161, -31053720, 5825630,
-8384306, -8767532, 15341279, 8373727},
{28685821, 7759505, -14378516, -12002860, -31971820, 4079242,
298136, -10232602, -2878207, 15190420},
},
{
{-32932876, 13806336, -14337485, -15794431, -24004620, 10940928,
8669718, 2742393, -26033313, -6875003},
{-1580388, -11729417, -25979658, -11445023, -17411874, -10912854,
9291594, -16247779, -12154742, 6048605},
{-30305315, 14843444, 1539301, 11864366, 20201677, 1900163,
13934231, 5128323, 11213262, 9168384},
},
{
{-26280513, 11007847, 19408960, -940758, -18592965, -4328580,
-5088060, -11105150, 20470157, -16398701},
{-23136053, 9282192, 14855179, -15390078, -7362815, -14408560,
-22783952, 14461608, 14042978, 5230683},
{29969567, -2741594, -16711867, -8552442, 9175486, -2468974,
21556951, 3506042, -5933891, -12449708},
},
{
{-3144746, 8744661, 19704003, 4581278, -20430686, 6830683,
-21284170, 8971513, -28539189, 15326563},
{-19464629, 10110288, -17262528, -3503892, -23500387, 1355669,
-15523050, 15300988, -20514118, 9168260},
{-5353335, 4488613, -23803248, 16314347, 7780487, -15638939,
-28948358, 9601605, 33087103, -9011387},
},
{
{-19443170, -15512900, -20797467, -12445323, -29824447, 10229461,
-27444329, -15000531, -5996870, 15664672},
{23294591, -16632613, -22650781, -8470978, 27844204, 11461195,
13099750, -2460356, 18151676, 13417686},
{-24722913, -4176517, -31150679, 5988919, -26858785, 6685065,
1661597, -12551441, 15271676, -15452665},
},
},
{
{
{11433042, -13228665, 8239631, -5279517, -1985436, -725718,
-18698764, 2167544, -6921301, -13440182},
{-31436171, 15575146, 30436815, 12192228, -22463353, 9395379,
-9917708, -8638997, 12215110, 12028277},
{14098400, 6555944, 23007258, 5757252, -15427832, -12950502,
30123440, 4617780, -16900089, -655628},
},
{
{-4026201, -15240835, 11893168, 13718664, -14809462, 1847385,
-15819999, 10154009, 23973261, -12684474},
{-26531820, -3695990, -1908898, 2534301, -31870557, -16550355,
18341390, -11419951, 32013174, -10103539},
{-25479301, 10876443, -11771086, -14625140, -12369567, 1838104,
21911214, 6354752, 4425632, -837822},
},
{
{-10433389, -14612966, 22229858, -3091047, -13191166, 776729,
-17415375, -12020462, 4725005, 14044970},
{19268650, -7304421, 1555349, 8692754, -21474059, -9910664, 6347390,
-1411784, -19522291, -16109756},
{-24864089, 12986008, -10898878, -5558584, -11312371, -148526,
19541418, 8180106, 9282262, 10282508},
},
{
{-26205082, 4428547, -8661196, -13194263, 4098402, -14165257,
15522535, 8372215, 5542595, -10702683},
{-10562541, 14895633, 26814552, -16673850, -17480754, -2489360,
-2781891, 6993761, -18093885, 10114655},
{-20107055, -929418, 31422704, 10427861, -7110749, 6150669,
-29091755, -11529146, 25953725, -106158},
},
{
{-4234397, -8039292, -9119125, 3046000, 2101609, -12607294,
19390020, 6094296, -3315279, 12831125},
{-15998678, 7578152, 5310217, 14408357, -33548620, -224739,
31575954, 6326196, 7381791, -2421839},
{-20902779, 3296811, 24736065, -16328389, 18374254, 7318640,
6295303, 8082724, -15362489, 12339664},
},
{
{27724736, 2291157, 6088201, -14184798, 1792727, 5857634, 13848414,
15768922, 25091167, 14856294},
{-18866652, 8331043, 24373479, 8541013, -701998, -9269457, 12927300,
-12695493, -22182473, -9012899},
{-11423429, -5421590, 11632845, 3405020, 30536730, -11674039,
-27260765, 13866390, 30146206, 9142070},
},
{
{3924129, -15307516, -13817122, -10054960, 12291820, -668366,
-27702774, 9326384, -8237858, 4171294},
{-15921940, 16037937, 6713787, 16606682, -21612135, 2790944,
26396185, 3731949, 345228, -5462949},
{-21327538, 13448259, 25284571, 1143661, 20614966, -8849387,
2031539, -12391231, -16253183, -13582083},
},
{
{31016211, -16722429, 26371392, -14451233, -5027349, 14854137,
17477601, 3842657, 28012650, -16405420},
{-5075835, 9368966, -8562079, -4600902, -15249953, 6970560,
-9189873, 16292057, -8867157, 3507940},
{29439664, 3537914, 23333589, 6997794, -17555561, -11018068,
-15209202, -15051267, -9164929, 6580396},
},
},
{
{
{-12185861, -7679788, 16438269, 10826160, -8696817, -6235611,
17860444, -9273846, -2095802, 9304567},
{20714564, -4336911, 29088195, 7406487, 11426967, -5095705,
14792667, -14608617, 5289421, -477127},
{-16665533, -10650790, -6160345, -13305760, 9192020, -1802462,
17271490, 12349094, 26939669, -3752294},
},
{
{-12889898, 9373458, 31595848, 16374215, 21471720, 13221525,
-27283495, -12348559, -3698806, 117887},
{22263325, -6560050, 3984570, -11174646, -15114008, -566785,
28311253, 5358056, -23319780, 541964},
{16259219, 3261970, 2309254, -15534474, -16885711, -4581916,
24134070, -16705829, -13337066, -13552195},
},
{
{9378160, -13140186, -22845982, -12745264, 28198281, -7244098,
-2399684, -717351, 690426, 14876244},
{24977353, -314384, -8223969, -13465086, 28432343, -1176353,
-13068804, -12297348, -22380984, 6618999},
{-1538174, 11685646, 12944378, 13682314, -24389511, -14413193,
8044829, -13817328, 32239829, -5652762},
},
{
{-18603066, 4762990, -926250, 8885304, -28412480, -3187315, 9781647,
-10350059, 32779359, 5095274},
{-33008130, -5214506, -32264887, -3685216, 9460461, -9327423,
-24601656, 14506724, 21639561, -2630236},
{-16400943, -13112215, 25239338, 15531969, 3987758, -4499318,
-1289502, -6863535, 17874574, 558605},
},
{
{-13600129, 10240081, 9171883, 16131053, -20869254, 9599700,
33499487, 5080151, 2085892, 5119761},
{-22205145, -2519528, -16381601, 414691, -25019550, 2170430,
30634760, -8363614, -31999993, -5759884},
{-6845704, 15791202, 8550074, -1312654, 29928809, -12092256,
27534430, -7192145, -22351378, 12961482},
},
{
{-24492060, -9570771, 10368194, 11582341, -23397293, -2245287,
16533930, 8206996, -30194652, -5159638},
{-11121496, -3382234, 2307366, 6362031, -135455, 8868177, -16835630,
7031275, 7589640, 8945490},
{-32152748, 8917967, 6661220, -11677616, -1192060, -15793393,
7251489, -11182180, 24099109, -14456170},
},
{
{5019558, -7907470, 4244127, -14714356, -26933272, 6453165,
-19118182, -13289025, -6231896, -10280736},
{10853594, 10721687, 26480089, 5861829, -22995819, 1972175,
-1866647, -10557898, -3363451, -6441124},
{-17002408, 5906790, 221599, -6563147, 7828208, -13248918, 24362661,
-2008168, -13866408, 7421392},
},
{
{8139927, -6546497, 32257646, -5890546, 30375719, 1886181,
-21175108, 15441252, 28826358, -4123029},
{6267086, 9695052, 7709135, -16603597, -32869068, -1886135,
14795160, -7840124, 13746021, -1742048},
{28584902, 7787108, -6732942, -15050729, 22846041, -7571236,
-3181936, -363524, 4771362, -8419958},
},
},
{
{
{24949256, 6376279, -27466481, -8174608, -18646154, -9930606,
33543569, -12141695, 3569627, 11342593},
{26514989, 4740088, 27912651, 3697550, 19331575, -11472339, 6809886,
4608608, 7325975, -14801071},
{-11618399, -14554430, -24321212, 7655128, -1369274, 5214312,
-27400540, 10258390, -17646694, -8186692},
},
{
{11431204, 15823007, 26570245, 14329124, 18029990, 4796082,
-31446179, 15580664, 9280358, -3973687},
{-160783, -10326257, -22855316, -4304997, -20861367, -13621002,
-32810901, -11181622, -15545091, 4387441},
{-20799378, 12194512, 3937617, -5805892, -27154820, 9340370,
-24513992, 8548137, 20617071, -7482001},
},
{
{-938825, -3930586, -8714311, 16124718, 24603125, -6225393,
-13775352, -11875822, 24345683, 10325460},
{-19855277, -1568885, -22202708, 8714034, 14007766, 6928528,
16318175, -1010689, 4766743, 3552007},
{-21751364, -16730916, 1351763, -803421, -4009670, 3950935