fixes #4477 (libsodium: update to 1.0.20)

11 files changed, 1480 insertions, 378 deletions

diff --git a/libs/libsodium/src/crypto_core/ed25519/core_ed25519.c b/libs/libsodium/src/crypto_core/ed25519/core_ed25519.c
index 007db4656e..99d5fd8780 100644
--- a/libs/libsodium/src/crypto_core/ed25519/core_ed25519.c
+++ b/libs/libsodium/src/crypto_core/ed25519/core_ed25519.c
@@ -1,7 +1,10 @@
-

 #include <stdint.h>

+#include <stdlib.h>

+#include <string.h>

 

+#include "core_h2c.h"

 #include "crypto_core_ed25519.h"

+#include "crypto_hash_sha512.h"

 #include "private/common.h"

 #include "private/ed25519_ref10.h"

 #include "randombytes.h"

@@ -13,9 +16,9 @@ crypto_core_ed25519_is_valid_point(const unsigned char *p)
     ge25519_p3 p_p3;

 

     if (ge25519_is_canonical(p) == 0 ||

-        ge25519_has_small_order(p) != 0 ||

         ge25519_frombytes(&p_p3, p) != 0 ||

         ge25519_is_on_curve(&p_p3) == 0 ||

+        ge25519_has_small_order(&p_p3) != 0 ||

         ge25519_is_on_main_subgroup(&p_p3) == 0) {

         return 0;

     }

@@ -27,16 +30,12 @@ crypto_core_ed25519_add(unsigned char *r,
                         const unsigned char *p, const unsigned char *q)

 {

     ge25519_p3     p_p3, q_p3, r_p3;

-    ge25519_p1p1   r_p1p1;

-    ge25519_cached q_cached;

 

     if (ge25519_frombytes(&p_p3, p) != 0 || ge25519_is_on_curve(&p_p3) == 0 ||

         ge25519_frombytes(&q_p3, q) != 0 || ge25519_is_on_curve(&q_p3) == 0) {

         return -1;

     }

-    ge25519_p3_to_cached(&q_cached, &q_p3);

-    ge25519_add(&r_p1p1, &p_p3, &q_cached);

-    ge25519_p1p1_to_p3(&r_p3, &r_p1p1);

+    ge25519_p3_add(&r_p3, &p_p3, &q_p3);

     ge25519_p3_tobytes(r, &r_p3);

 

     return 0;

@@ -47,16 +46,12 @@ crypto_core_ed25519_sub(unsigned char *r,
                         const unsigned char *p, const unsigned char *q)

 {

     ge25519_p3     p_p3, q_p3, r_p3;

-    ge25519_p1p1   r_p1p1;

-    ge25519_cached q_cached;

 

     if (ge25519_frombytes(&p_p3, p) != 0 || ge25519_is_on_curve(&p_p3) == 0 ||

         ge25519_frombytes(&q_p3, q) != 0 || ge25519_is_on_curve(&q_p3) == 0) {

         return -1;

     }

-    ge25519_p3_to_cached(&q_cached, &q_p3);

-    ge25519_sub(&r_p1p1, &p_p3, &q_cached);

-    ge25519_p1p1_to_p3(&r_p3, &r_p1p1);

+    ge25519_p3_sub(&r_p3, &p_p3, &q_p3);

     ge25519_p3_tobytes(r, &r_p3);

 

     return 0;

@@ -67,7 +62,32 @@ crypto_core_ed25519_from_uniform(unsigned char *p, const unsigned char *r)
 {

     ge25519_from_uniform(p, r);

 

-    return - ge25519_has_small_order(p);

+    return 0;

+}

+

+int

+crypto_core_ed25519_from_string(unsigned char p[crypto_core_ed25519_BYTES],

+                                const char *ctx, const unsigned char *msg,

+                                size_t msg_len, int hash_alg)

+{

+    return ge25519_from_string(p, ctx, msg, msg_len, hash_alg);

+}

+

+int

+crypto_core_ed25519_from_string_ro(unsigned char p[crypto_core_ed25519_BYTES],

+                                   const char *ctx, const unsigned char *msg,

+                                   size_t msg_len, int hash_alg)

+{

+    return ge25519_from_string_ro(p, ctx, msg, msg_len, hash_alg);

+}

+

+void

+crypto_core_ed25519_random(unsigned char *p)

+{

+    unsigned char h[crypto_core_ed25519_UNIFORMBYTES];

+

+    randombytes_buf(h, sizeof h);

+    (void) crypto_core_ed25519_from_uniform(p, h);

 }

 

 void

@@ -159,6 +179,13 @@ crypto_core_ed25519_scalar_sub(unsigned char *z, const unsigned char *x,
 }

 

 void

+crypto_core_ed25519_scalar_mul(unsigned char *z, const unsigned char *x,

+                               const unsigned char *y)

+{

+    sc25519_mul(z, x, y);

+}

+

+void

 crypto_core_ed25519_scalar_reduce(unsigned char *r,

                                   const unsigned char *s)

 {

@@ -170,6 +197,12 @@ crypto_core_ed25519_scalar_reduce(unsigned char *r,
     sodium_memzero(t, sizeof t);

 }

 

+int

+crypto_core_ed25519_scalar_is_canonical(const unsigned char *s)

+{

+    return sc25519_is_canonical(s);

+}

+

 size_t

 crypto_core_ed25519_bytes(void)

 {

@@ -189,6 +222,12 @@ crypto_core_ed25519_uniformbytes(void)
 }

 

 size_t

+crypto_core_ed25519_hashbytes(void)

+{

+    return crypto_core_ed25519_HASHBYTES;

+}

+

+size_t

 crypto_core_ed25519_scalarbytes(void)

 {

     return crypto_core_ed25519_SCALARBYTES;

diff --git a/libs/libsodium/src/crypto_core/ed25519/core_h2c.c b/libs/libsodium/src/crypto_core/ed25519/core_h2c.c
new file mode 100644
index 0000000000..37f3ed59fb
--- /dev/null
+++ b/libs/libsodium/src/crypto_core/ed25519/core_h2c.c
@@ -0,0 +1,133 @@
+#include <assert.h>
+#include <errno.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "core_h2c.h"
+#include "crypto_hash_sha256.h"
+#include "crypto_hash_sha512.h"
+#include "private/common.h"
+
+#define HASH_BYTES      crypto_hash_sha256_BYTES
+#define HASH_BLOCKBYTES 64U
+
+static int
+core_h2c_string_to_hash_sha256(unsigned char *h, const size_t h_len, const char *ctx,
+                               const unsigned char *msg, size_t msg_len)
+{
+    crypto_hash_sha256_state st;
+    const unsigned char      empty_block[HASH_BLOCKBYTES] = { 0 };
+    unsigned char            u0[HASH_BYTES];
+    unsigned char            ux[HASH_BYTES] = { 0 };
+    unsigned char            t[3] = { 0U, (unsigned char) h_len, 0U};
+    unsigned char            ctx_len_u8;
+    size_t                   ctx_len = ctx != NULL ? strlen(ctx) : 0U;
+    size_t                   i, j;
+
+    assert(h_len <= 0xff);
+    if (ctx_len > (size_t) 0xff) {
+        crypto_hash_sha256_init(&st);
+        crypto_hash_sha256_update(&st,
+                                  (const unsigned char *) "H2C-OVERSIZE-DST-",
+                                  sizeof "H2C-OVERSIZE-DST-" - 1U);
+        crypto_hash_sha256_update(&st, (const unsigned char *) ctx, ctx_len);
+        crypto_hash_sha256_final(&st, u0);
+        ctx = (const char *) u0;
+        ctx_len = HASH_BYTES;
+        COMPILER_ASSERT(HASH_BYTES <= (size_t) 0xff);
+    }
+    ctx_len_u8 = (unsigned char) ctx_len;
+    crypto_hash_sha256_init(&st);
+    crypto_hash_sha256_update(&st, empty_block, sizeof empty_block);
+    crypto_hash_sha256_update(&st, msg, msg_len);
+    crypto_hash_sha256_update(&st, t, 3U);
+    crypto_hash_sha256_update(&st, (const unsigned char *) ctx, ctx_len);
+    crypto_hash_sha256_update(&st, &ctx_len_u8, 1U);
+    crypto_hash_sha256_final(&st, u0);
+
+    for (i = 0U; i < h_len; i += HASH_BYTES) {
+        for (j = 0U; j < HASH_BYTES; j++) {
+            ux[j] ^= u0[j];
+        }
+        t[2]++;
+        crypto_hash_sha256_init(&st);
+        crypto_hash_sha256_update(&st, ux, HASH_BYTES);
+        crypto_hash_sha256_update(&st, &t[2], 1U);
+        crypto_hash_sha256_update(&st, (const unsigned char *) ctx, ctx_len);
+        crypto_hash_sha256_update(&st, &ctx_len_u8, 1U);
+        crypto_hash_sha256_final(&st, ux);
+        memcpy(&h[i], ux, h_len - i >= (sizeof ux) ? (sizeof ux) : h_len - i);
+    }
+    return 0;
+}
+
+#undef  HASH_BYTES
+#undef  HASH_BLOCKBYTES
+
+#define HASH_BYTES      crypto_hash_sha512_BYTES
+#define HASH_BLOCKBYTES 128U
+
+static int
+core_h2c_string_to_hash_sha512(unsigned char *h, const size_t h_len, const char *ctx,
+                               const unsigned char *msg, size_t msg_len)
+{
+    crypto_hash_sha512_state st;
+    const unsigned char      empty_block[HASH_BLOCKBYTES] = { 0 };
+    unsigned char            u0[HASH_BYTES];
+    unsigned char            ux[HASH_BYTES] = { 0 };
+    unsigned char            t[3] = { 0U, (unsigned char) h_len, 0U};
+    unsigned char            ctx_len_u8;
+    size_t                   ctx_len = ctx != NULL ? strlen(ctx) : 0U;
+    size_t                   i, j;
+
+    assert(h_len <= 0xff);
+    if (ctx_len > (size_t) 0xff) {
+        crypto_hash_sha512_init(&st);
+        crypto_hash_sha512_update(&st,
+                                  (const unsigned char *) "H2C-OVERSIZE-DST-",
+                                  sizeof "H2C-OVERSIZE-DST-" - 1U);
+        crypto_hash_sha512_update(&st, (const unsigned char *) ctx, ctx_len);
+        crypto_hash_sha512_final(&st, u0);
+        ctx = (const char *) u0;
+        ctx_len = HASH_BYTES;
+        COMPILER_ASSERT(HASH_BYTES <= (size_t) 0xff);
+    }
+    ctx_len_u8 = (unsigned char) ctx_len;
+    crypto_hash_sha512_init(&st);
+    crypto_hash_sha512_update(&st, empty_block, sizeof empty_block);
+    crypto_hash_sha512_update(&st, msg, msg_len);
+    crypto_hash_sha512_update(&st, t, 3U);
+    crypto_hash_sha512_update(&st, (const unsigned char *) ctx, ctx_len);
+    crypto_hash_sha512_update(&st, &ctx_len_u8, 1U);
+    crypto_hash_sha512_final(&st, u0);
+
+    for (i = 0U; i < h_len; i += HASH_BYTES) {
+        for (j = 0U; j < HASH_BYTES; j++) {
+            ux[j] ^= u0[j];
+        }
+        t[2]++;
+        crypto_hash_sha512_init(&st);
+        crypto_hash_sha512_update(&st, ux, HASH_BYTES);
+        crypto_hash_sha512_update(&st, &t[2], 1U);
+        crypto_hash_sha512_update(&st, (const unsigned char *) ctx, ctx_len);
+        crypto_hash_sha512_update(&st, &ctx_len_u8, 1U);
+        crypto_hash_sha512_final(&st, ux);
+        memcpy(&h[i], ux, h_len - i >= (sizeof ux) ? (sizeof ux) : h_len - i);
+    }
+    return 0;
+}
+
+int
+core_h2c_string_to_hash(unsigned char *h, const size_t h_len, const char *ctx,
+                        const unsigned char *msg, size_t msg_len, int hash_alg)
+{
+    switch (hash_alg) {
+    case CORE_H2C_SHA256:
+        return core_h2c_string_to_hash_sha256(h, h_len, ctx, msg, msg_len);
+    case CORE_H2C_SHA512:
+        return core_h2c_string_to_hash_sha512(h, h_len, ctx, msg, msg_len);
+    default:
+        errno = EINVAL;
+        return -1;
+    }
+}
diff --git a/libs/libsodium/src/crypto_core/ed25519/core_h2c.h b/libs/libsodium/src/crypto_core/ed25519/core_h2c.h
new file mode 100644
index 0000000000..e595b80c4c
--- /dev/null
+++ b/libs/libsodium/src/crypto_core/ed25519/core_h2c.h
@@ -0,0 +1,12 @@
+#ifndef core_h2c_H
+#define core_h2c_H
+
+#include "private/quirks.h"
+
+#define CORE_H2C_SHA256 1
+#define CORE_H2C_SHA512 2
+
+int core_h2c_string_to_hash(unsigned char *h, const size_t h_len, const char *ctx,
+                            const unsigned char *msg, size_t msg_len,
+                            int hash_alg);
+#endif
diff --git a/libs/libsodium/src/crypto_core/ed25519/core_ristretto255.c b/libs/libsodium/src/crypto_core/ed25519/core_ristretto255.c
new file mode 100644
index 0000000000..6d3a85cd08
--- /dev/null
+++ b/libs/libsodium/src/crypto_core/ed25519/core_ristretto255.c
@@ -0,0 +1,215 @@
+
+#include <assert.h>
+#include <stdint.h>
+#include <string.h>
+
+#include "core_h2c.h"
+#include "crypto_core_ed25519.h"
+#include "crypto_core_ristretto255.h"
+#include "crypto_hash_sha256.h"
+#include "private/common.h"
+#include "private/ed25519_ref10.h"
+#include "randombytes.h"
+#include "utils.h"
+
+int
+crypto_core_ristretto255_is_valid_point(const unsigned char *p)
+{
+    ge25519_p3 p_p3;
+
+    if (ristretto255_frombytes(&p_p3, p) != 0) {
+        return 0;
+    }
+    return 1;
+}
+
+int
+crypto_core_ristretto255_add(unsigned char *r,
+                             const unsigned char *p, const unsigned char *q)
+{
+    ge25519_p3     p_p3, q_p3, r_p3;
+
+    if (ristretto255_frombytes(&p_p3, p) != 0 ||
+        ristretto255_frombytes(&q_p3, q) != 0) {
+        return -1;
+    }
+    ge25519_p3_add(&r_p3, &p_p3, &q_p3);
+    ristretto255_p3_tobytes(r, &r_p3);
+
+    return 0;
+}
+
+int
+crypto_core_ristretto255_sub(unsigned char *r,
+                             const unsigned char *p, const unsigned char *q)
+{
+    ge25519_p3     p_p3, q_p3, r_p3;
+
+    if (ristretto255_frombytes(&p_p3, p) != 0 ||
+        ristretto255_frombytes(&q_p3, q) != 0) {
+        return -1;
+    }
+    ge25519_p3_sub(&r_p3, &p_p3, &q_p3);
+    ristretto255_p3_tobytes(r, &r_p3);
+
+    return 0;
+}
+
+int
+crypto_core_ristretto255_from_hash(unsigned char *p, const unsigned char *r)
+{
+    ristretto255_from_hash(p, r);
+
+    return 0;
+}
+
+static int
+_string_to_element(unsigned char *p,
+                   const char *ctx, const unsigned char *msg, size_t msg_len,
+                   int hash_alg)
+{
+    unsigned char h[crypto_core_ristretto255_HASHBYTES];
+
+    if (core_h2c_string_to_hash(h, sizeof h, ctx, msg, msg_len,
+                                hash_alg) != 0) {
+        return -1;
+    }
+    ristretto255_from_hash(p, h);
+
+    return 0;
+}
+
+int
+crypto_core_ristretto255_from_string(unsigned char p[crypto_core_ristretto255_BYTES],
+                                     const char *ctx, const unsigned char *msg,
+                                     size_t msg_len, int hash_alg)
+{
+    return _string_to_element(p, ctx, msg, msg_len, hash_alg);
+}
+
+int
+crypto_core_ristretto255_from_string_ro(unsigned char p[crypto_core_ristretto255_BYTES],
+                                        const char *ctx, const unsigned char *msg,
+                                        size_t msg_len, int hash_alg)
+{
+    return crypto_core_ristretto255_from_string(p, ctx, msg, msg_len, hash_alg);
+}
+
+void
+crypto_core_ristretto255_random(unsigned char *p)
+{
+    unsigned char h[crypto_core_ristretto255_HASHBYTES];
+
+    randombytes_buf(h, sizeof h);
+    (void) crypto_core_ristretto255_from_hash(p, h);
+}
+
+void
+crypto_core_ristretto255_scalar_random(unsigned char *r)
+{
+    crypto_core_ed25519_scalar_random(r);
+}
+
+int
+crypto_core_ristretto255_scalar_invert(unsigned char *recip,
+                                       const unsigned char *s)
+{
+    return crypto_core_ed25519_scalar_invert(recip, s);
+}
+
+void
+crypto_core_ristretto255_scalar_negate(unsigned char *neg,
+                                       const unsigned char *s)
+{
+    crypto_core_ed25519_scalar_negate(neg, s);
+}
+
+void
+crypto_core_ristretto255_scalar_complement(unsigned char *comp,
+                                           const unsigned char *s)
+{
+    crypto_core_ed25519_scalar_complement(comp, s);
+}
+
+void
+crypto_core_ristretto255_scalar_add(unsigned char *z, const unsigned char *x,
+                                    const unsigned char *y)
+{
+    crypto_core_ed25519_scalar_add(z, x, y);
+}
+
+void
+crypto_core_ristretto255_scalar_sub(unsigned char *z, const unsigned char *x,
+                                    const unsigned char *y)
+{
+    crypto_core_ed25519_scalar_sub(z, x, y);
+}
+
+void
+crypto_core_ristretto255_scalar_mul(unsigned char *z, const unsigned char *x,
+                                    const unsigned char *y)
+{
+    sc25519_mul(z, x, y);
+}
+
+void
+crypto_core_ristretto255_scalar_reduce(unsigned char *r,
+                                       const unsigned char *s)
+{
+    crypto_core_ed25519_scalar_reduce(r, s);
+}
+
+int
+crypto_core_ristretto255_scalar_is_canonical(const unsigned char *s)
+{
+    return sc25519_is_canonical(s);
+}
+
+#define HASH_SC_L 48U
+
+int
+crypto_core_ristretto255_scalar_from_string(unsigned char *s,
+                                            const char *ctx, const unsigned char *msg,
+                                            size_t msg_len, int hash_alg)
+{
+    unsigned char h[crypto_core_ristretto255_NONREDUCEDSCALARBYTES];
+    unsigned char h_be[HASH_SC_L];
+    size_t        i;
+
+    if (core_h2c_string_to_hash(h_be, sizeof h_be, ctx, msg, msg_len,
+                                hash_alg) != 0) {
+        return -1;
+    }
+    COMPILER_ASSERT(sizeof h >= sizeof h_be);
+    for (i = 0U; i < HASH_SC_L; i++) {
+        h[i] = h_be[HASH_SC_L - 1U - i];
+    }
+    memset(&h[i], 0, (sizeof h) - i);
+    crypto_core_ristretto255_scalar_reduce(s, h);
+
+    return 0;
+}
+
+size_t
+crypto_core_ristretto255_bytes(void)
+{
+    return crypto_core_ristretto255_BYTES;
+}
+
+size_t
+crypto_core_ristretto255_nonreducedscalarbytes(void)
+{
+    return crypto_core_ristretto255_NONREDUCEDSCALARBYTES;
+}
+
+size_t
+crypto_core_ristretto255_hashbytes(void)
+{
+    return crypto_core_ristretto255_HASHBYTES;
+}
+
+size_t
+crypto_core_ristretto255_scalarbytes(void)
+{
+    return crypto_core_ristretto255_SCALARBYTES;
+}
diff --git a/libs/libsodium/src/crypto_core/ed25519/ref10/ed25519_ref10.c b/libs/libsodium/src/crypto_core/ed25519/ref10/ed25519_ref10.c
index fdff8eeb90..27ab377609 100644
--- a/libs/libsodium/src/crypto_core/ed25519/ref10/ed25519_ref10.c
+++ b/libs/libsodium/src/crypto_core/ed25519/ref10/ed25519_ref10.c
@@ -4,6 +4,7 @@
 #include <string.h>

 

 #include "crypto_verify_32.h"

+#include "../core_h2c.h"

 #include "private/common.h"

 #include "private/ed25519_ref10.h"

 #include "utils.h"

@@ -50,13 +51,24 @@ load_4(const unsigned char *in)
 # include "fe_25_5/fe.h"

 #endif

 

+static inline void

+fe25519_sqmul(fe25519 s, const int n, const fe25519 a)

+{

+    int i;

+

+    for (i = 0; i < n; i++) {

+        fe25519_sq(s, s);

+    }

+    fe25519_mul(s, s, a);

+}

+

+/*

+ * Inversion - returns 0 if z=0

+ */

 void

 fe25519_invert(fe25519 out, const fe25519 z)

 {

-    fe25519 t0;

-    fe25519 t1;

-    fe25519 t2;

-    fe25519 t3;

+    fe25519 t0, t1, t2, t3;

     int     i;

 

     fe25519_sq(t0, z);

@@ -81,8 +93,7 @@ fe25519_invert(fe25519 out, const fe25519 z)
         fe25519_sq(t3, t3);

     }

     fe25519_mul(t2, t3, t2);

-    fe25519_sq(t2, t2);

-    for (i = 1; i < 10; ++i) {

+    for (i = 1; i < 11; ++i) {

         fe25519_sq(t2, t2);

     }

     fe25519_mul(t1, t2, t1);

@@ -96,24 +107,24 @@ fe25519_invert(fe25519 out, const fe25519 z)
         fe25519_sq(t3, t3);

     }

     fe25519_mul(t2, t3, t2);

-    fe25519_sq(t2, t2);

-    for (i = 1; i < 50; ++i) {

+    for (i = 1; i < 51; ++i) {

         fe25519_sq(t2, t2);

     }

     fe25519_mul(t1, t2, t1);

-    fe25519_sq(t1, t1);

-    for (i = 1; i < 5; ++i) {

+    for (i = 1; i < 6; ++i) {

         fe25519_sq(t1, t1);

     }

     fe25519_mul(out, t1, t0);

 }

 

+/*

+ * returns z^((p-5)/8) = z^(2^252-3)

+ * used to compute square roots since we have p=5 (mod 8); see Cohen and Frey.

+ */

 static void

 fe25519_pow22523(fe25519 out, const fe25519 z)

 {

-    fe25519 t0;

-    fe25519 t1;

-    fe25519 t2;

+    fe25519 t0, t1, t2;

     int     i;

 

     fe25519_sq(t0, z);

@@ -138,8 +149,7 @@ fe25519_pow22523(fe25519 out, const fe25519 z)
         fe25519_sq(t2, t2);

     }

     fe25519_mul(t1, t2, t1);

-    fe25519_sq(t1, t1);

-    for (i = 1; i < 10; ++i) {

+    for (i = 1; i < 11; ++i) {

         fe25519_sq(t1, t1);

     }

     fe25519_mul(t0, t1, t0);

@@ -153,8 +163,7 @@ fe25519_pow22523(fe25519 out, const fe25519 z)
         fe25519_sq(t2, t2);

     }

     fe25519_mul(t1, t2, t1);

-    fe25519_sq(t1, t1);

-    for (i = 1; i < 50; ++i) {

+    for (i = 1; i < 51; ++i) {

         fe25519_sq(t1, t1);

     }

     fe25519_mul(t0, t1, t0);

@@ -163,12 +172,96 @@ fe25519_pow22523(fe25519 out, const fe25519 z)
     fe25519_mul(out, t0, z);

 }

 

+static inline void

+fe25519_cneg(fe25519 h, unsigned int b)

+{

+    fe25519 negf;

+

+    fe25519_neg(negf, h);

+    fe25519_cmov(h, negf, b);

+}

+

+static inline void

+fe25519_abs(fe25519 h)

+{

+    fe25519_cneg(h, fe25519_isnegative(h));

+}

+

+static void

+fe25519_unchecked_sqrt(fe25519 x, const fe25519 x2)

+{

+    fe25519 p_root;

+    fe25519 m_root;

+    fe25519 m_root2;

+    fe25519 e;

+

+    fe25519_pow22523(e, x2);

+    fe25519_mul(p_root, e, x2);

+    fe25519_mul(m_root, p_root, fe25519_sqrtm1);

+    fe25519_sq(m_root2, m_root);

+    fe25519_sub(e, x2, m_root2);

+    fe25519_copy(x, p_root);

+    fe25519_cmov(x, m_root, fe25519_iszero(e));

+}

+

+static int

+fe25519_sqrt(fe25519 x, const fe25519 x2)

+{

+    fe25519 check;

+    fe25519 x2_copy;

+

+    fe25519_copy(x2_copy, x2);

+    fe25519_unchecked_sqrt(x, x2);

+    fe25519_sq(check, x);

+    fe25519_sub(check, check, x2_copy);

+

+    return fe25519_iszero(check) - 1;

+}

+

+static int

+fe25519_notsquare(const fe25519 x)

+{

+    fe25519       _10, _11, _1100, _1111, _11110000, _11111111;

+    fe25519       t, u, v;

+    unsigned char s[32];

+

+    /* Jacobi symbol - x^((p-1)/2) */

+    fe25519_mul(_10, x, x);

+    fe25519_mul(_11, x, _10);

+    fe25519_sq(_1100, _11);

+    fe25519_sq(_1100, _1100);

+    fe25519_mul(_1111, _11, _1100);

+    fe25519_sq(_11110000, _1111);

+    fe25519_sq(_11110000, _11110000);

+    fe25519_sq(_11110000, _11110000);

+    fe25519_sq(_11110000, _11110000);

+    fe25519_mul(_11111111, _1111, _11110000);

+    fe25519_copy(t, _11111111);

+    fe25519_sqmul(t, 2, _11);

+    fe25519_copy(u, t);

+    fe25519_sqmul(t, 10, u);

+    fe25519_sqmul(t, 10, u);

+    fe25519_copy(v, t);

+    fe25519_sqmul(t, 30, v);

+    fe25519_copy(v, t);

+    fe25519_sqmul(t, 60, v);

+    fe25519_copy(v, t);

+    fe25519_sqmul(t, 120, v);

+    fe25519_sqmul(t, 10, u);

+    fe25519_sqmul(t, 3, _11);

+    fe25519_sq(t, t);

+

+    fe25519_tobytes(s, t);

+

+    return s[1] & 1;

+}

+

 /*

  r = p + q

  */

 

-void

-ge25519_add(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_cached *q)

+static void

+ge25519_add_cached(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_cached *q)

 {

     fe25519 t0;

 

@@ -233,7 +326,6 @@ ge25519_frombytes(ge25519_p3 *h, const unsigned char *s)
 {

     fe25519 u;

     fe25519 v;

-    fe25519 v3;

     fe25519 vxx;

     fe25519 m_root_check, p_root_check;

     fe25519 negx;

@@ -243,19 +335,13 @@ ge25519_frombytes(ge25519_p3 *h, const unsigned char *s)
     fe25519_frombytes(h->Y, s);

     fe25519_1(h->Z);

     fe25519_sq(u, h->Y);

-    fe25519_mul(v, u, d);

+    fe25519_mul(v, u, ed25519_d);

     fe25519_sub(u, u, h->Z); /* u = y^2-1 */

     fe25519_add(v, v, h->Z); /* v = dy^2+1 */

 

-    fe25519_sq(v3, v);

-    fe25519_mul(v3, v3, v); /* v3 = v^3 */

-    fe25519_sq(h->X, v3);

-    fe25519_mul(h->X, h->X, v);

-    fe25519_mul(h->X, h->X, u); /* x = uv^7 */

-

-    fe25519_pow22523(h->X, h->X); /* x = (uv^7)^((q-5)/8) */

-    fe25519_mul(h->X, h->X, v3);

-    fe25519_mul(h->X, h->X, u); /* x = uv^3(uv^7)^((q-5)/8) */

+    fe25519_mul(h->X, u, v);

+    fe25519_pow22523(h->X, h->X);

+    fe25519_mul(h->X, u, h->X); /* u((uv)^((q-5)/8)) */

 

     fe25519_sq(vxx, h->X);

     fe25519_mul(vxx, vxx, v);

@@ -263,7 +349,7 @@ ge25519_frombytes(ge25519_p3 *h, const unsigned char *s)
     fe25519_add(p_root_check, vxx, u); /* vx^2+u */

     has_m_root = fe25519_iszero(m_root_check);

     has_p_root = fe25519_iszero(p_root_check);

-    fe25519_mul(x_sqrtm1, h->X, sqrtm1); /* x*sqrt(-1) */

+    fe25519_mul(x_sqrtm1, h->X, fe25519_sqrtm1); /* x*sqrt(-1) */

     fe25519_cmov(h->X, x_sqrtm1, 1 - has_m_root);

 

     fe25519_neg(negx, h->X);

@@ -285,7 +371,7 @@ ge25519_frombytes_negate_vartime(ge25519_p3 *h, const unsigned char *s)
     fe25519_frombytes(h->Y, s);

     fe25519_1(h->Z);

     fe25519_sq(u, h->Y);

-    fe25519_mul(v, u, d);

+    fe25519_mul(v, u, ed25519_d);

     fe25519_sub(u, u, h->Z); /* u = y^2-1 */

     fe25519_add(v, v, h->Z); /* v = dy^2+1 */

 

@@ -307,7 +393,7 @@ ge25519_frombytes_negate_vartime(ge25519_p3 *h, const unsigned char *s)
         if (fe25519_iszero(p_root_check) == 0) {

             return -1;

         }

-        fe25519_mul(h->X, h->X, sqrtm1);

+        fe25519_mul(h->X, h->X, fe25519_sqrtm1);

     }

 

     if (fe25519_isnegative(h->X) == (s[31] >> 7)) {

@@ -323,7 +409,7 @@ ge25519_frombytes_negate_vartime(ge25519_p3 *h, const unsigned char *s)
  */

 

 static void

-ge25519_madd(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_precomp *q)

+ge25519_add_precomp(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_precomp *q)

 {

     fe25519 t0;

 

@@ -344,7 +430,7 @@ ge25519_madd(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_precomp *q)
  */

 

 static void

-ge25519_msub(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_precomp *q)

+ge25519_sub_precomp(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_precomp *q)

 {

     fe25519 t0;

 

@@ -385,6 +471,18 @@ ge25519_p1p1_to_p3(ge25519_p3 *r, const ge25519_p1p1 *p)
     fe25519_mul(r->T, p->X, p->Y);

 }

 

+/*

+ r = p

+ */

+void

+ge25519_p2_to_p3(ge25519_p3 *r, const ge25519_p2 *p)

+{

+    fe25519_copy(r->X, p->X);

+    fe25519_copy(r->Y, p->Y);

+    fe25519_copy(r->Z, p->Z);

+    fe25519_mul(r->T, p->X, p->Y);

+}

+

 static void

 ge25519_p2_0(ge25519_p2 *h)

 {

@@ -435,13 +533,13 @@ ge25519_cached_0(ge25519_cached *h)
  r = p

  */

 

-void

+static void

 ge25519_p3_to_cached(ge25519_cached *r, const ge25519_p3 *p)

 {

     fe25519_add(r->YplusX, p->Y, p->X);

     fe25519_sub(r->YminusX, p->Y, p->X);

     fe25519_copy(r->Z, p->Z);

-    fe25519_mul(r->T2d, p->T, d2);

+    fe25519_mul(r->T2d, p->T, ed25519_d2);

 }

 

 static void

@@ -458,7 +556,7 @@ ge25519_p3_to_precomp(ge25519_precomp *pi, const ge25519_p3 *p)
     fe25519_add(pi->yplusx, y, x);

     fe25519_sub(pi->yminusx, y, x);

     fe25519_mul(xy, x, y);

-    fe25519_mul(pi->xy2d, xy, d2);

+    fe25519_mul(pi->xy2d, xy, ed25519_d2);

 }

 

 /*

@@ -513,7 +611,7 @@ equal(signed char b, signed char c)
     unsigned char ub = b;

     unsigned char uc = c;

     unsigned char x  = ub ^ uc; /* 0: yes; 1..255: no */

-    uint32_t      y  = x;       /* 0: yes; 1..255: no */

+    uint32_t      y  = (uint32_t) x; /* 0: yes; 1..255: no */

 

     y -= 1;   /* 4294967295: yes; 0..254: no */

     y >>= 31; /* 1: yes; 0: no */

@@ -550,7 +648,7 @@ ge25519_cmov_cached(ge25519_cached *t, const ge25519_cached *u, unsigned char b)
 }

 

 static void

-ge25519_select(ge25519_precomp *t, const ge25519_precomp precomp[8], const signed char b)

+ge25519_cmov8(ge25519_precomp *t, const ge25519_precomp precomp[8], const signed char b)

 {

     ge25519_precomp     minust;

     const unsigned char bnegative = negative(b);

@@ -572,7 +670,7 @@ ge25519_select(ge25519_precomp *t, const ge25519_precomp precomp[8], const signe
 }

 

 static void

-ge25519_select_base(ge25519_precomp *t, const int pos, const signed char b)

+ge25519_cmov8_base(ge25519_precomp *t, const int pos, const signed char b)

 {

     static const ge25519_precomp base[32][8] = { /* base[i][j] = (j+1)*256^i*B */

 #ifdef HAVE_TI_MODE

@@ -581,11 +679,11 @@ ge25519_select_base(ge25519_precomp *t, const int pos, const signed char b)
 # include "fe_25_5/base.h"

 #endif

     };

-    ge25519_select(t, base[pos], b);

+    ge25519_cmov8(t, base[pos], b);

 }

 

 static void

-ge25519_select_cached(ge25519_cached *t, const ge25519_cached cached[8], const signed char b)

+ge25519_cmov8_cached(ge25519_cached *t, const ge25519_cached cached[8], const signed char b)

 {

     ge25519_cached      minust;

     const unsigned char bnegative = negative(b);

@@ -611,8 +709,8 @@ ge25519_select_cached(ge25519_cached *t, const ge25519_cached cached[8], const s
  r = p - q

  */

 

-void

-ge25519_sub(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_cached *q)

+static void

+ge25519_sub_cached(ge25519_p1p1 *r, const ge25519_p3 *p, const ge25519_cached *q)

 {

     fe25519 t0;

 

@@ -644,68 +742,76 @@ ge25519_tobytes(unsigned char *s, const ge25519_p2 *h)
 }

 

 /*

- r = a * A + b * B

- where a = a[0]+256*a[1]+...+256^31 a[31].

- and b = b[0]+256*b[1]+...+256^31 b[31].

- B is the Ed25519 base point (x,4/5) with x positive.

-

- Only used for signatures verification.

+ * Precomputation of a base point, to use in multiscalar multiplication algorithm A,3A,5A,7A,9A,11A,13A,15A

  */

-

-void

-ge25519_double_scalarmult_vartime(ge25519_p2 *r, const unsigned char *a,

-                                  const ge25519_p3 *A, const unsigned char *b)

-{

-    static const ge25519_precomp Bi[8] = {

-#ifdef HAVE_TI_MODE

-# include "fe_51/base2.h"

-#else

-# include "fe_25_5/base2.h"

-#endif

-    };

-    signed char    aslide[256];

-    signed char    bslide[256];

-    ge25519_cached Ai[8]; /* A,3A,5A,7A,9A,11A,13A,15A */

+static void point_precomputation(ge25519_cached cached[8], const ge25519_p3 *base) {

     ge25519_p1p1   t;

     ge25519_p3     u;

-    ge25519_p3     A2;

-    int            i;

+    ge25519_p3     A;

 

-    slide_vartime(aslide, a);

-    slide_vartime(bslide, b);

-

-    ge25519_p3_to_cached(&Ai[0], A);

+    // Precomputation of values of A

+    ge25519_p3_to_cached(&cached[0], base);

 

-    ge25519_p3_dbl(&t, A);

-    ge25519_p1p1_to_p3(&A2, &t);

+    ge25519_p3_dbl(&t, base);

+    ge25519_p1p1_to_p3(&A, &t);

 

-    ge25519_add(&t, &A2, &Ai[0]);

+    ge25519_add_cached(&t, &A, &cached[0]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[1], &u);

+    ge25519_p3_to_cached(&cached[1], &u);

 

-    ge25519_add(&t, &A2, &Ai[1]);

+    ge25519_add_cached(&t, &A, &cached[1]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[2], &u);

+    ge25519_p3_to_cached(&cached[2], &u);

 

-    ge25519_add(&t, &A2, &Ai[2]);

+    ge25519_add_cached(&t, &A, &cached[2]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[3], &u);

+    ge25519_p3_to_cached(&cached[3], &u);

 

-    ge25519_add(&t, &A2, &Ai[3]);

+    ge25519_add_cached(&t, &A, &cached[3]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[4], &u);

+    ge25519_p3_to_cached(&cached[4], &u);

 

-    ge25519_add(&t, &A2, &Ai[4]);

+    ge25519_add_cached(&t, &A, &cached[4]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[5], &u);

+    ge25519_p3_to_cached(&cached[5], &u);

 

-    ge25519_add(&t, &A2, &Ai[5]);

+    ge25519_add_cached(&t, &A, &cached[5]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[6], &u);

+    ge25519_p3_to_cached(&cached[6], &u);

 

-    ge25519_add(&t, &A2, &Ai[6]);

+    ge25519_add_cached(&t, &A, &cached[6]);

     ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[7], &u);

+    ge25519_p3_to_cached(&cached[7], &u);

+}

+

+/*

+ Variable time double scalar multiplication with variable bases

+ r = a * A + b * B

+ where a = a[0]+256*a[1]+...+256^31 a[31].

+ and b = b[0]+256*b[1]+...+256^31 b[31].

+

+ If a null pointer is passed as an argument for B, the function uses

+ the precomputed values of the base point for the scalar multiplication.

+

+ Only used for ed25519 and VRF verification.

+ */

+

+void

+ge25519_double_scalarmult_vartime(ge25519_p2 *r, const unsigned char *a,

+                                           const ge25519_p3 *A, const unsigned char *b,

+                                           const ge25519_p3 *B)

+{

+    signed char    aslide[256];

+    signed char    bslide[256];

+    ge25519_cached Ai[8];

+    ge25519_p1p1   t;

+    ge25519_p3     u;

+    int            i;

+

+    slide_vartime(aslide, a);

+    slide_vartime(bslide, b);

+

+    point_precomputation(Ai, A);

 

     ge25519_p2_0(r);

 

@@ -720,18 +826,37 @@ ge25519_double_scalarmult_vartime(ge25519_p2 *r, const unsigned char *a,
 

         if (aslide[i] > 0) {

             ge25519_p1p1_to_p3(&u, &t);

-            ge25519_add(&t, &u, &Ai[aslide[i] / 2]);

+            ge25519_add_cached(&t, &u, &Ai[aslide[i] / 2]);

         } else if (aslide[i] < 0) {

             ge25519_p1p1_to_p3(&u, &t);

-            ge25519_sub(&t, &u, &Ai[(-aslide[i]) / 2]);

+            ge25519_sub_cached(&t, &u, &Ai[(-aslide[i]) / 2]);

         }

 

-        if (bslide[i] > 0) {

-            ge25519_p1p1_to_p3(&u, &t);

-            ge25519_madd(&t, &u, &Bi[bslide[i] / 2]);

-        } else if (bslide[i] < 0) {

-            ge25519_p1p1_to_p3(&u, &t);

-            ge25519_msub(&t, &u, &Bi[(-bslide[i]) / 2]);

+        if (B == NULL) {

+            static const ge25519_precomp Bi[8] = {

+#ifdef HAVE_TI_MODE

+# include "fe_51/base2.h"

+#else

+# include "fe_25_5/base2.h"

+#endif

+            };

+            if (bslide[i] > 0) {

+                ge25519_p1p1_to_p3(&u, &t);

+                ge25519_add_precomp(&t, &u, &Bi[bslide[i] / 2]);

+            } else if (bslide[i] < 0) {

+                ge25519_p1p1_to_p3(&u, &t);

+                ge25519_sub_precomp(&t, &u, &Bi[(-bslide[i]) / 2]);

+            }

+        } else {

+            ge25519_cached Bi[8];

+            point_precomputation(Bi, B);

+            if (bslide[i] > 0) {

+                ge25519_p1p1_to_p3(&u, &t);

+                ge25519_add_cached(&t, &u, &Bi[bslide[i] / 2]);

+            } else if (bslide[i] < 0) {

+                ge25519_p1p1_to_p3(&u, &t);

+                ge25519_sub_cached(&t, &u, &Bi[(-bslide[i]) / 2]);

+            }

         }

 

         ge25519_p1p1_to_p2(r, &t);

@@ -767,7 +892,7 @@ ge25519_scalarmult(ge25519_p3 *h, const unsigned char *a, const ge25519_p3 *p)
     ge25519_p1p1_to_p3(&p2, &t2);

     ge25519_p3_to_cached(&pi[2 - 1], &p2); /* 2p = 2*p */

 

-    ge25519_add(&t3, p, &pi[2 - 1]);

+    ge25519_add_cached(&t3, p, &pi[2 - 1]);

     ge25519_p1p1_to_p3(&p3, &t3);

     ge25519_p3_to_cached(&pi[3 - 1], &p3); /* 3p = 2p+p */

 

@@ -775,7 +900,7 @@ ge25519_scalarmult(ge25519_p3 *h, const unsigned char *a, const ge25519_p3 *p)
     ge25519_p1p1_to_p3(&p4, &t4);

     ge25519_p3_to_cached(&pi[4 - 1], &p4); /* 4p = 2*2p */

 

-    ge25519_add(&t5, p, &pi[4 - 1]);

+    ge25519_add_cached(&t5, p, &pi[4 - 1]);

     ge25519_p1p1_to_p3(&p5, &t5);

     ge25519_p3_to_cached(&pi[5 - 1], &p5); /* 5p = 4p+p */

 

@@ -783,7 +908,7 @@ ge25519_scalarmult(ge25519_p3 *h, const unsigned char *a, const ge25519_p3 *p)
     ge25519_p1p1_to_p3(&p6, &t6);

     ge25519_p3_to_cached(&pi[6 - 1], &p6); /* 6p = 2*3p */

 

-    ge25519_add(&t7, p, &pi[6 - 1]);

+    ge25519_add_cached(&t7, p, &pi[6 - 1]);

     ge25519_p1p1_to_p3(&p7, &t7);

     ge25519_p3_to_cached(&pi[7 - 1], &p7); /* 7p = 6p+p */

 

@@ -811,8 +936,8 @@ ge25519_scalarmult(ge25519_p3 *h, const unsigned char *a, const ge25519_p3 *p)
     ge25519_p3_0(h);

 

     for (i = 63; i != 0; i--) {

-        ge25519_select_cached(&t, pi, e[i]);

-        ge25519_add(&r, h, &t);

+        ge25519_cmov8_cached(&t, pi, e[i]);

+        ge25519_add_cached(&r, h, &t);

 

         ge25519_p1p1_to_p2(&s, &r);

         ge25519_p2_dbl(&r, &s);

@@ -825,8 +950,8 @@ ge25519_scalarmult(ge25519_p3 *h, const unsigned char *a, const ge25519_p3 *p)
 

         ge25519_p1p1_to_p3(h, &r);  /* *16 */

     }

-    ge25519_select_cached(&t, pi, e[i]);

-    ge25519_add(&r, h, &t);

+    ge25519_cmov8_cached(&t, pi, e[i]);

+    ge25519_add_cached(&r, h, &t);

 

     ge25519_p1p1_to_p3(h, &r);

 }

@@ -871,8 +996,8 @@ ge25519_scalarmult_base(ge25519_p3 *h, const unsigned char *a)
     ge25519_p3_0(h);

 

     for (i = 1; i < 64; i += 2) {

-        ge25519_select_base(&t, i / 2, e[i]);

-        ge25519_madd(&r, h, &t);

+        ge25519_cmov8_base(&t, i / 2, e[i]);

+        ge25519_add_precomp(&r, h, &t);

         ge25519_p1p1_to_p3(h, &r);

     }

 

@@ -886,65 +1011,118 @@ ge25519_scalarmult_base(ge25519_p3 *h, const unsigned char *a)
     ge25519_p1p1_to_p3(h, &r);

 

     for (i = 0; i < 64; i += 2) {

-        ge25519_select_base(&t, i / 2, e[i]);

-        ge25519_madd(&r, h, &t);

+        ge25519_cmov8_base(&t, i / 2, e[i]);

+        ge25519_add_precomp(&r, h, &t);

         ge25519_p1p1_to_p3(h, &r);

     }

 }

 

-/* multiply by the order of the main subgroup l = 2^252+27742317777372353535851937790883648493 */

+/* r = 2p */

 static void

-ge25519_mul_l(ge25519_p3 *r, const ge25519_p3 *A)

+ge25519_p3p3_dbl(ge25519_p3 *r, const ge25519_p3 *p)

 {

-    static const signed char aslide[253] = {

-        13, 0, 0, 0, 0, -1, 0, 0, 0, 0, -11, 0, 0, 0, 0, 0, 0, -5, 0, 0, 0, 0, 0, 0, -3, 0, 0, 0, 0, -13, 0, 0, 0, 0, 7, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0, -13, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, 0, 11, 0, 0, 0, 0, -13, 0, 0, 0, 0, 0, 0, -3, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 3, 0, 0, 0, 0, -11, 0, 0, 0, 0, 0, 0, 0, 15, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0, 0, 0, 0, 7, 0, 0, 0, 0, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

-    };

-    ge25519_cached Ai[8];

-    ge25519_p1p1   t;

-    ge25519_p3     u;

-    ge25519_p3     A2;

-    int            i;

+    ge25519_p1p1 p1p1;

 

-    ge25519_p3_to_cached(&Ai[0], A);

-    ge25519_p3_dbl(&t, A);

-    ge25519_p1p1_to_p3(&A2, &t);

-    ge25519_add(&t, &A2, &Ai[0]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[1], &u);

-    ge25519_add(&t, &A2, &Ai[1]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[2], &u);

-    ge25519_add(&t, &A2, &Ai[2]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[3], &u);

-    ge25519_add(&t, &A2, &Ai[3]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[4], &u);

-    ge25519_add(&t, &A2, &Ai[4]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[5], &u);

-    ge25519_add(&t, &A2, &Ai[5]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[6], &u);

-    ge25519_add(&t, &A2, &Ai[6]);

-    ge25519_p1p1_to_p3(&u, &t);

-    ge25519_p3_to_cached(&Ai[7], &u);

+    ge25519_p3_dbl(&p1p1, p);

+    ge25519_p1p1_to_p3(r, &p1p1);

+}

 

-    ge25519_p3_0(r);

+/* r = -p */

+static void

+ge25519_p3_neg(ge25519_p3 *r, const ge25519_p3 *p)

+{

+    fe25519_neg(r->X, p->X);

+    fe25519_copy(r->Y, p->Y);

+    fe25519_copy(r->Z, p->Z);

+    fe25519_neg(r->T, p->T);

+}

 

-    for (i = 252; i >= 0; --i) {

-        ge25519_p3_dbl(&t, r);

+/* r = p+q */

+void

+ge25519_p3_add(ge25519_p3 *r, const ge25519_p3 *p, const ge25519_p3 *q)

+{

+    ge25519_cached q_cached;

+    ge25519_p1p1   p1p1;

 

-        if (aslide[i] > 0) {

-            ge25519_p1p1_to_p3(&u, &t);

-            ge25519_add(&t, &u, &Ai[aslide[i] / 2]);

-        } else if (aslide[i] < 0) {

-            ge25519_p1p1_to_p3(&u, &t);

-            ge25519_sub(&t, &u, &Ai[(-aslide[i]) / 2]);

-        }

+    ge25519_p3_to_cached(&q_cached, q);

+    ge25519_add_cached(&p1p1, p, &q_cached);

+    ge25519_p1p1_to_p3(r, &p1p1);

+}

 

-        ge25519_p1p1_to_p3(r, &t);

+/* r = p-q */

+void

+ge25519_p3_sub(ge25519_p3 *r, const ge25519_p3 *p, const ge25519_p3 *q)

+{

+    ge25519_p3 q_neg;

+

+    ge25519_p3_neg(&q_neg, q);

+    ge25519_p3_add(r, p, &q_neg);

+}

+

+/* r = r*(2^n)+q */

+static void

+ge25519_p3_dbladd(ge25519_p3 *r, const int n, const ge25519_p3 *q)

+{

+    ge25519_p2   p2;

+    ge25519_p1p1 p1p1;

+    int          i;

+

+    ge25519_p3_to_p2(&p2, r);

+    for (i = 0; i < n; i++) {

+        ge25519_p2_dbl(&p1p1, &p2);

+        ge25519_p1p1_to_p2(&p2, &p1p1);

     }

+    ge25519_p1p1_to_p3(r, &p1p1);

+    ge25519_p3_add(r, r, q);

+}

+

+/* multiply by the order of the main subgroup l = 2^252+27742317777372353535851937790883648493 */

+static void

+ge25519_mul_l(ge25519_p3 *r, const ge25519_p3 *p)

+{

+    ge25519_p3 _10, _11, _100, _110, _1000, _1011, _10000, _100000, _100110,

+        _1000000, _1010000, _1010011, _1100011, _1100111, _1101011, _10010011,

+        _10010111, _10111101, _11010011, _11100111, _11101101, _11110101;

+

+    ge25519_p3p3_dbl(&_10, p);

+    ge25519_p3_add(&_11, p, &_10);

+    ge25519_p3_add(&_100, p, &_11);

+    ge25519_p3_add(&_110, &_10, &_100);

+    ge25519_p3_add(&_1000, &_10, &_110);

+    ge25519_p3_add(&_1011, &_11, &_1000);

+    ge25519_p3p3_dbl(&_10000, &_1000);

+    ge25519_p3p3_dbl(&_100000, &_10000);

+    ge25519_p3_add(&_100110, &_110, &_100000);

+    ge25519_p3p3_dbl(&_1000000, &_100000);

+    ge25519_p3_add(&_1010000, &_10000, &_1000000);

+    ge25519_p3_add(&_1010011, &_11, &_1010000);

+    ge25519_p3_add(&_1100011, &_10000, &_1010011);

+    ge25519_p3_add(&_1100111, &_100, &_1100011);

+    ge25519_p3_add(&_1101011, &_100, &_1100111);

+    ge25519_p3_add(&_10010011, &_1000000, &_1010011);

+    ge25519_p3_add(&_10010111, &_100, &_10010011);

+    ge25519_p3_add(&_10111101, &_100110, &_10010111);

+    ge25519_p3_add(&_11010011, &_1000000, &_10010011);

+    ge25519_p3_add(&_11100111, &_1010000, &_10010111);

+    ge25519_p3_add(&_11101101, &_110, &_11100111);

+    ge25519_p3_add(&_11110101, &_1000, &_11101101);

+

+    ge25519_p3_add(r, &_1011, &_11110101);

+    ge25519_p3_dbladd(r, 126, &_1010011);

+    ge25519_p3_dbladd(r, 9, &_10);

+    ge25519_p3_add(r, r, &_11110101);

+    ge25519_p3_dbladd(r, 7, &_1100111);

+    ge25519_p3_dbladd(r, 9, &_11110101);

+    ge25519_p3_dbladd(r, 11, &_10111101);

+    ge25519_p3_dbladd(r, 8, &_11100111);

+    ge25519_p3_dbladd(r, 9, &_1101011);

+    ge25519_p3_dbladd(r, 6, &_1011);

+    ge25519_p3_dbladd(r, 14, &_10010011);

+    ge25519_p3_dbladd(r, 10, &_1100011);

+    ge25519_p3_dbladd(r, 9, &_10010111);

+    ge25519_p3_dbladd(r, 10, &_11110101);

+    ge25519_p3_dbladd(r, 8, &_11010011);

+    ge25519_p3_dbladd(r, 8, &_11101101);

 }

 

 int

@@ -964,7 +1142,7 @@ ge25519_is_on_curve(const ge25519_p3 *p)
     fe25519_mul(t0, t0, z2);

 

     fe25519_mul(t1, x2, y2);

-    fe25519_mul(t1, t1, d);

+    fe25519_mul(t1, t1, ed25519_d);

     fe25519_sq(z4, z2);

     fe25519_add(t1, t1, z4);

     fe25519_sub(t0, t0, t1);

@@ -1000,59 +1178,29 @@ ge25519_is_canonical(const unsigned char *s)
 }

 

 int

-ge25519_has_small_order(const unsigned char s[32])

-{

-    CRYPTO_ALIGN(16)

-    static const unsigned char blacklist[][32] = {

-        /* 0 (order 4) */

-        { 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

-          0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

-          0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },

-        /* 1 (order 1) */

-        { 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

-          0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

-          0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 },

-        /* 2707385501144840649318225287225658788936804267575313519463743609750303402022

-           (order 8) */

-        { 0x26, 0xe8, 0x95, 0x8f, 0xc2, 0xb2, 0x27, 0xb0, 0x45, 0xc3, 0xf4,

-          0x89, 0xf2, 0xef, 0x98, 0xf0, 0xd5, 0xdf, 0xac, 0x05, 0xd3, 0xc6,

-          0x33, 0x39, 0xb1, 0x38, 0x02, 0x88, 0x6d, 0x53, 0xfc, 0x05 },

-        /* 55188659117513257062467267217118295137698188065244968500265048394206261417927

-           (order 8) */

-        { 0xc7, 0x17, 0x6a, 0x70, 0x3d, 0x4d, 0xd8, 0x4f, 0xba, 0x3c, 0x0b,

-          0x76, 0x0d, 0x10, 0x67, 0x0f, 0x2a, 0x20, 0x53, 0xfa, 0x2c, 0x39,

-          0xcc, 0xc6, 0x4e, 0xc7, 0xfd, 0x77, 0x92, 0xac, 0x03, 0x7a },

-        /* p-1 (order 2) */

-        { 0xec, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f },

-        /* p (=0, order 4) */

-        { 0xed, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f },

-        /* p+1 (=1, order 1) */

-        { 0xee, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,

-          0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f }

-    };

-    unsigned char c[7] = { 0 };

-    unsigned int  k;

-    size_t        i, j;

+ge25519_has_small_order(const ge25519_p3 *p)

+{

+    fe25519 recip;

+    fe25519 x;

+    fe25519 x_neg;

+    fe25519 y;

+    fe25519 y_sqrtm1;

+    fe25519 c;

+    int     ret = 0;

 

-    COMPILER_ASSERT(7 == sizeof blacklist / sizeof blacklist[0]);

-    for (j = 0; j < 31; j++) {

-        for (i = 0; i < sizeof blacklist / sizeof blacklist[0]; i++) {

-            c[i] |= s[j] ^ blacklist[i][j];

-        }

-    }

-    for (i = 0; i < sizeof blacklist / sizeof blacklist[0]; i++) {

-        c[i] |= (s[j] & 0x7f) ^ blacklist[i][j];

-    }

-    k = 0;

-    for (i = 0; i < sizeof blacklist / sizeof blacklist[0]; i++) {

-        k |= (c[i] - 1);

-    }

-    return (int) ((k >> 8) & 1);

+    fe25519_invert(recip, p->Z);

+    fe25519_mul(x, p->X, recip);

+    ret |= fe25519_iszero(x);

+    fe25519_mul(y, p->Y, recip);

+    ret |= fe25519_iszero(y);

+    fe25519_neg(x_neg, p->X);

+    fe25519_mul(y_sqrtm1, y, fe25519_sqrtm1);

+    fe25519_sub(c, y_sqrtm1, x);

+    ret |= fe25519_iszero(c);

+    fe25519_sub(c, y_sqrtm1, x_neg);

+    ret |= fe25519_iszero(c);

+

+    return ret;

 }

 

 /*

@@ -1065,7 +1213,7 @@ ge25519_has_small_order(const unsigned char s[32])
  where l = 2^252 + 27742317777372353535851937790883648493.

  */

 

-static void

+void

 sc25519_mul(unsigned char s[32], const unsigned char a[32], const unsigned char b[32])

 {

     int64_t a0  = 2097151 & load_3(a);

@@ -2055,46 +2203,75 @@ sc25519_sqmul(unsigned char s[32], const int n, const unsigned char a[32])
 void

 sc25519_invert(unsigned char recip[32], const unsigned char s[32])

 {

-    unsigned char _10[32], _100[32], _11[32], _101[32], _111[32],

-        _1001[32], _1011[32], _1111[32];

+    unsigned char _10[32], _100[32], _1000[32], _10000[32], _100000[32],

+        _1000000[32], _10010011[32], _10010111[32], _100110[32], _1010[32],

+        _1010000[32], _1010011[32], _1011[32], _10110[32], _10111101[32],

+        _11[32], _1100011[32], _1100111[32], _11010011[32], _1101011[32],

+        _11100111[32], _11101011[32], _11110101[32];

 

     sc25519_sq(_10, s);

-    sc25519_sq(_100, _10);

-    sc25519_mul(_11, _10, s);

-    sc25519_mul(_101, _10, _11);

-    sc25519_mul(_111, _10, _101);

-    sc25519_mul(_1001, _10, _111);

-    sc25519_mul(_1011, _10, _1001);

-    sc25519_mul(_1111, _100, _1011);

-    sc25519_mul(recip, _1111, s);

-

-    sc25519_sqmul(recip, 123 + 3, _101);

-    sc25519_sqmul(recip, 2 + 2, _11);

-    sc25519_sqmul(recip, 1 + 4, _1111);

-    sc25519_sqmul(recip, 1 + 4, _1111);

-    sc25519_sqmul(recip, 4, _1001);

-    sc25519_sqmul(recip, 2, _11);

-    sc25519_sqmul(recip, 1 + 4, _1111);

-    sc25519_sqmul(recip, 1 + 3, _101);

-    sc25519_sqmul(recip, 3 + 3, _101);

-    sc25519_sqmul(recip, 3, _111);

-    sc25519_sqmul(recip, 1 + 4, _1111);

-    sc25519_sqmul(recip, 2 + 3, _111);

-    sc25519_sqmul(recip, 2 + 2, _11);

-    sc25519_sqmul(recip, 1 + 4, _1011);

-    sc25519_sqmul(recip, 2 + 4, _1011);

-    sc25519_sqmul(recip, 6 + 4, _1001);

-    sc25519_sqmul(recip, 2 + 2, _11);

-    sc25519_sqmul(recip, 3 + 2, _11);

-    sc25519_sqmul(recip, 3 + 2, _11);

-    sc25519_sqmul(recip, 1 + 4, _1001);

-    sc25519_sqmul(recip, 1 + 3, _111);

-    sc25519_sqmul(recip, 2 + 4, _1111);

-    sc25519_sqmul(recip, 1 + 4, _1011);

-    sc25519_sqmul(recip, 3, _101);

-    sc25519_sqmul(recip, 2 + 4, _1111);

-    sc25519_sqmul(recip, 3, _101);

-    sc25519_sqmul(recip, 1 + 2, _11);

+    sc25519_mul(_11, s, _10);

+    sc25519_mul(_100, s, _11);

+    sc25519_sq(_1000, _100);

+    sc25519_mul(_1010, _10, _1000);

+    sc25519_mul(_1011, s, _1010);

+    sc25519_sq(_10000, _1000);

+    sc25519_sq(_10110, _1011);

+    sc25519_mul(_100000, _1010, _10110);

+    sc25519_mul(_100110, _10000, _10110);

+    sc25519_sq(_1000000, _100000);

+    sc25519_mul(_1010000, _10000, _1000000);

+    sc25519_mul(_1010011, _11, _1010000);

+    sc25519_mul(_1100011, _10000, _1010011);

+    sc25519_mul(_1100111, _100, _1100011);

+    sc25519_mul(_1101011, _100, _1100111);

+    sc25519_mul(_10010011, _1000000, _1010011);

+    sc25519_mul(_10010111, _100, _10010011);

+    sc25519_mul(_10111101, _100110, _10010111);

+    sc25519_mul(_11010011, _10110, _10111101);

+    sc25519_mul(_11100111, _1010000, _10010111);

+    sc25519_mul(_11101011, _100, _11100111);

+    sc25519_mul(_11110101, _1010, _11101011);

+

+    sc25519_mul(recip, _1011, _11110101);

+    sc25519_sqmul(recip, 126, _1010011);

+    sc25519_sqmul(recip, 9, _10);

+    sc25519_mul(recip, recip, _11110101);

+    sc25519_sqmul(recip, 7, _1100111);

+    sc25519_sqmul(recip, 9, _11110101);

+    sc25519_sqmul(recip, 11, _10111101);

+    sc25519_sqmul(recip, 8, _11100111);

+    sc25519_sqmul(recip, 9, _1101011);

+    sc25519_sqmul(recip, 6, _1011);

+    sc25519_sqmul(recip, 14, _10010011);

+    sc25519_sqmul(recip, 10, _1100011);

+    sc25519_sqmul(recip, 9, _10010111);

+    sc25519_sqmul(recip, 10, _11110101);

+    sc25519_sqmul(recip, 8, _11010011);

+    sc25519_sqmul(recip, 8, _11101011);

+}

+

+/* 2^252+27742317777372353535851937790883648493 */

+static const unsigned char L[] = {

+        0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58, 0xd6, 0x9c, 0xf7,

+        0xa2, 0xde, 0xf9, 0xde, 0x14, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

+        0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10

+};

+

+void

+sc25519_negate(unsigned char neg[32], const unsigned char s[32])

+{

+    unsigned char t_[64];

+    unsigned char s_[64];

+

+    memset(t_, 0, sizeof t_);

+    memset(s_, 0, sizeof s_);

+    memcpy(t_ + 32, L,

+           32);

+    memcpy(s_, s, 32);

+    sodium_sub(t_, s_, sizeof t_);

+    sc25519_reduce(t_);

+    memcpy(neg, t_, 32);

 }

 

 /*

@@ -2453,133 +2630,460 @@ sc25519_is_canonical(const unsigned char s[32])
     return (c != 0);

 }

 

+/* montgomery to edwards */

 static void

-chi25519(fe25519 out, const fe25519 z)

+ge25519_mont_to_ed(fe25519 xed, fe25519 yed, const fe25519 x, const fe25519 y)

 {

-    fe25519 t0, t1, t2, t3;

-    int     i;

+    fe25519 one;

+    fe25519 x_plus_one;

+    fe25519 x_minus_one;

+    fe25519 x_plus_one_y_inv;

+

+    fe25519_1(one);

+    fe25519_add(x_plus_one, x, one);

+    fe25519_sub(x_minus_one, x, one);

+

+    /* xed = sqrt(-A-2)*x/y */

+    fe25519_mul(x_plus_one_y_inv, x_plus_one, y);

+    fe25519_invert(x_plus_one_y_inv, x_plus_one_y_inv); /* 1/((x+1)*y) */

+    fe25519_mul(xed, x, ed25519_sqrtam2);

+    fe25519_mul(xed, xed, x_plus_one_y_inv);            /* sqrt(-A-2)*x/((x+1)*y) */

+    fe25519_mul(xed, xed, x_plus_one);

 

-    fe25519_sq(t0, z);

-    fe25519_mul(t1, t0, z);

-    fe25519_sq(t0, t1);

-    fe25519_sq(t2, t0);

-    fe25519_sq(t2, t2);

-    fe25519_mul(t2, t2, t0);

-    fe25519_mul(t1, t2, z);

-    fe25519_sq(t2, t1);

+    /* yed = (x-1)/(x+1) */

+    fe25519_mul(yed, x_plus_one_y_inv, y);              /* 1/(x+1) */

+    fe25519_mul(yed, yed, x_minus_one);

+    fe25519_cmov(yed, one, fe25519_iszero(x_plus_one_y_inv));

+}

 

-    for (i = 1; i < 5; i++) {

-        fe25519_sq(t2, t2);

-    }

-    fe25519_mul(t1, t2, t1);

-    fe25519_sq(t2, t1);

-    for (i = 1; i < 10; i++) {

-        fe25519_sq(t2, t2);

-    }

-    fe25519_mul(t2, t2, t1);

-    fe25519_sq(t3, t2);

-    for (i = 1; i < 20; i++) {

-        fe25519_sq(t3, t3);

-    }

-    fe25519_mul(t2, t3, t2);

-    fe25519_sq(t2, t2);

-    for (i = 1; i < 10; i++) {

-        fe25519_sq(t2, t2);

-    }

-    fe25519_mul(t1, t2, t1);

-    fe25519_sq(t2, t1);

-    for (i = 1; i < 50; i++) {

-        fe25519_sq(t2, t2);

-    }

-    fe25519_mul(t2, t2, t1);

-    fe25519_sq(t3, t2);

-    for (i = 1; i < 100; i++) {

-        fe25519_sq(t3, t3);

-    }

-    fe25519_mul(t2, t3, t2);

-    fe25519_sq(t2, t2);

-    for (i = 1; i < 50; i++) {

-        fe25519_sq(t2, t2);

-    }

-    fe25519_mul(t1, t2, t1);

-    fe25519_sq(t1, t1);

-    for (i = 1; i < 4; i++) {

-        fe25519_sq(t1, t1);

-    }

-    fe25519_mul(out, t1, t0);

+/* montgomery -- recover y = sqrt(x^3 + A*x^2 + x) */

+static int

+ge25519_xmont_to_ymont(fe25519 y, const fe25519 x)

+{

+    fe25519 x2;

+    fe25519 x3;

+

+    fe25519_sq(x2, x);

+    fe25519_mul(x3, x, x2);

+    fe25519_mul32(x2, x2, ed25519_A_32);

+    fe25519_add(y, x3, x);

+    fe25519_add(y, y, x2);

+

+    return fe25519_sqrt(y, y);

 }

 

+/* multiply by the cofactor */

 void

-ge25519_from_uniform(unsigned char s[32], const unsigned char r[32])

+ge25519_clear_cofactor(ge25519_p3 *p3)

 {

-    fe25519       e;

-    fe25519       negx;

-    fe25519       rr2;

-    fe25519       x, x2, x3;

-    ge25519_p3    p3;

-    ge25519_p1p1  p1;

-    ge25519_p2    p2;

-    unsigned int  e_is_minus_1;

-    unsigned char x_sign;

+    ge25519_p1p1 p1;

+    ge25519_p2   p2;

 

-    memcpy(s, r, 32);

-    x_sign = s[31] & 0x80;

-    s[31] &= 0x7f;

+    ge25519_p3_dbl(&p1, p3);

+    ge25519_p1p1_to_p2(&p2, &p1);

+    ge25519_p2_dbl(&p1, &p2);

+    ge25519_p1p1_to_p2(&p2, &p1);

+    ge25519_p2_dbl(&p1, &p2);

+    ge25519_p1p1_to_p3(p3, &p1);

+}

 

-    fe25519_frombytes(rr2, s);

+static void

+ge25519_elligator2(fe25519 x, fe25519 y, const fe25519 r, int *notsquare_p)

+{

+    fe25519       gx1;

+    fe25519       rr2;

+    fe25519       x2, x3, negx;

+    int           notsquare;

 

-    /* elligator */

-    fe25519_sq2(rr2, rr2);

+    fe25519_sq2(rr2, r);

     rr2[0]++;

     fe25519_invert(rr2, rr2);

-    fe25519_mul(x, curve25519_A, rr2);

-    fe25519_neg(x, x);

+    fe25519_mul32(x, rr2, ed25519_A_32);

+    fe25519_neg(x, x); /* x=x1 */

 

     fe25519_sq(x2, x);

     fe25519_mul(x3, x, x2);

-    fe25519_add(e, x3, x);

-    fe25519_mul(x2, x2, curve25519_A);

-    fe25519_add(e, x2, e);

+    fe25519_mul32(x2, x2, ed25519_A_32); /* x2 = A*x1^2 */

+    fe25519_add(gx1, x3, x);

+    fe25519_add(gx1, gx1, x2); /* gx1 = x1^3 + A*x1^2 + x1 */

 

-    chi25519(e, e);

+    notsquare = fe25519_notsquare(gx1);

 

-    fe25519_tobytes(s, e);

-    e_is_minus_1 = s[1] & 1;

+    /* gx1 not a square  => x = -x1-A */

     fe25519_neg(negx, x);

-    fe25519_cmov(x, negx, e_is_minus_1);

+    fe25519_cmov(x, negx, notsquare);

     fe25519_0(x2);

-    fe25519_cmov(x2, curve25519_A, e_is_minus_1);

+    fe25519_cmov(x2, ed25519_A, notsquare);

     fe25519_sub(x, x, x2);

 

-    /* yed = (x-1)/(x+1) */

-    {

-        fe25519 one;

-        fe25519 x_plus_one;

-        fe25519 x_plus_one_inv;

-        fe25519 x_minus_one;

-        fe25519 yed;

-

-        fe25519_1(one);

-        fe25519_add(x_plus_one, x, one);

-        fe25519_sub(x_minus_one, x, one);

-        fe25519_invert(x_plus_one_inv, x_plus_one);

-        fe25519_mul(yed, x_minus_one, x_plus_one_inv);

-        fe25519_tobytes(s, yed);

+    /* y = sqrt(gx1) or sqrt(gx2) with gx2 = gx1 * (A+x1) / -x1 */

+    /* but it is about as fast to just recompute from the curve equation. */

+    if (ge25519_xmont_to_ymont(y, x) != 0) {

+        abort();

     }

+    *notsquare_p = notsquare;

+}

 

-    /* recover x */

-    s[31] |= x_sign;

-    if (ge25519_frombytes(&p3, s) != 0) {

-        abort(); /* LCOV_EXCL_LINE */

+void

+ge25519_from_uniform(unsigned char s[32], const unsigned char r[32])

+{

+    ge25519_p3    p3;

+    fe25519       x, y, negxed;

+    fe25519       r_fe;

+    int           notsquare;

+    unsigned char x_sign;

+

+    memcpy(s, r, 32);

+    x_sign = s[31] >> 7;

+    s[31] &= 0x7f;

+    fe25519_frombytes(r_fe, s);

+

+    ge25519_elligator2(x, y, r_fe, &notsquare);

+

+    ge25519_mont_to_ed(p3.X, p3.Y, x, y);

+    fe25519_neg(negxed, p3.X);

+    fe25519_cmov(p3.X, negxed, fe25519_isnegative(p3.X) ^ x_sign);

+

+    fe25519_1(p3.Z);

+    fe25519_mul(p3.T, p3.X, p3.Y);

+    ge25519_clear_cofactor(&p3);

+    ge25519_p3_tobytes(s, &p3);

+}

+

+#define HASH_GE_L 48U

+

+static int

+_string_to_points(unsigned char * const px, const size_t n,

+                  const char *ctx, const unsigned char *msg, size_t msg_len,

+                  int hash_alg)

+{

+    unsigned char h[64];

+    unsigned char h_be[2U * HASH_GE_L];

+    size_t        i, j;

+

+    if (n > 2U) {

+        abort(); /* LCOV_EXCL_LINE */;

+    }

+    if (core_h2c_string_to_hash(h_be, n * HASH_GE_L, ctx, msg, msg_len,

+                                hash_alg) != 0) {

+        return -1;

     }

+    COMPILER_ASSERT(sizeof h >= HASH_GE_L);

+    for (i = 0U; i < n; i++) {

+        for (j = 0U; j < HASH_GE_L; j++) {

+            h[j] = h_be[i * HASH_GE_L + HASH_GE_L - 1U - j];

+        }

+        memset(&h[j], 0, (sizeof h) - j);

+        ge25519_from_hash(&px[i * 32], h);

+    }

+    return 0;

+}

 

-    /* multiply by the cofactor */

-    ge25519_p3_dbl(&p1, &p3);

-    ge25519_p1p1_to_p2(&p2, &p1);

-    ge25519_p2_dbl(&p1, &p2);

-    ge25519_p1p1_to_p2(&p2, &p1);

-    ge25519_p2_dbl(&p1, &p2);

-    ge25519_p1p1_to_p3(&p3, &p1);

+int

+ge25519_from_string(unsigned char p[32],

+                    const char *ctx, const unsigned char *msg,

+                    size_t msg_len, int hash_alg)

+{

+    return _string_to_points(p, 1, ctx, msg, msg_len, hash_alg);

+

+

+}

+

+int

+ge25519_from_string_ro(unsigned char p[32],

+                       const char *ctx, const unsigned char *msg,

+                       size_t msg_len, int hash_alg)

+{

+    unsigned char  px[64];

+    ge25519_p3     p_p3, q_p3, r_p3;

+

+    if (_string_to_points(px, 2, ctx, msg, msg_len, hash_alg) != 0) {

+        return -1;

+    }

+

+    if (ge25519_frombytes(&p_p3, &px[0]) != 0 || ge25519_is_on_curve(&p_p3) == 0 ||

+        ge25519_frombytes(&q_p3, &px[32]) != 0 || ge25519_is_on_curve(&q_p3) == 0) {

+        return -1;

+    }

+    ge25519_p3_add(&r_p3, &p_p3, &q_p3);

+    ge25519_p3_tobytes(p, &r_p3);

+

+    return 0;

+}

+

+

+static void

+fe25519_reduce64(fe25519 fe_f, const unsigned char h[64])

+{

+    unsigned char fl[32];

+    unsigned char gl[32];

+    fe25519       fe_g;

+    size_t        i;

+

+    memcpy(fl, h, 32);

+    memcpy(gl, h + 32, 32);

+    fl[31] &= 0x7f;

+    gl[31] &= 0x7f;

+    fe25519_frombytes(fe_f, fl);

+    fe25519_frombytes(fe_g, gl);

+    fe_f[0] += (h[31] >> 7) * 19 + (h[63] >> 7) * 722;

+    for (i = 0; i < sizeof (fe25519) / sizeof fe_f[0]; i++) {

+        fe_f[i] += 38 * fe_g[i];

+    }

+    fe25519_reduce(fe_f, fe_f);

+}

 

+void

+ge25519_from_hash(unsigned char s[32], const unsigned char h[64])

+{

+    ge25519_p3    p3;

+    fe25519       fe_f;

+    fe25519       x, y, negy;

+    int           notsquare;

+    unsigned char y_sign;

+

+    fe25519_reduce64(fe_f, h);

+    ge25519_elligator2(x, y, fe_f, &notsquare);

+

+    y_sign = notsquare ^ 1;

+    fe25519_neg(negy, y);

+    fe25519_cmov(y, negy, fe25519_isnegative(y) ^ y_sign);

+

+    ge25519_mont_to_ed(p3.X, p3.Y, x, y);

+

+    fe25519_1(p3.Z);

+    fe25519_mul(p3.T, p3.X, p3.Y);

+    ge25519_clear_cofactor(&p3);

     ge25519_p3_tobytes(s, &p3);

 }

+

+/* Ristretto group */

+

+static int

+ristretto255_sqrt_ratio_m1(fe25519 x, const fe25519 u, const fe25519 v)

+{

+    fe25519 v3;

+    fe25519 vxx;

+    fe25519 m_root_check, p_root_check, f_root_check;

+    fe25519 x_sqrtm1;

+    int     has_m_root, has_p_root, has_f_root;

+

+    fe25519_sq(v3, v);

+    fe25519_mul(v3, v3, v); /* v3 = v^3 */

+    fe25519_sq(x, v3);

+    fe25519_mul(x, x, u);

+    fe25519_mul(x, x, v); /* x = uv^7 */

+

+    fe25519_pow22523(x, x); /* x = (uv^7)^((q-5)/8) */

+    fe25519_mul(x, x, v3);

+    fe25519_mul(x, x, u); /* x = uv^3(uv^7)^((q-5)/8) */

+

+    fe25519_sq(vxx, x);

+    fe25519_mul(vxx, vxx, v); /* vx^2 */

+    fe25519_sub(m_root_check, vxx, u); /* vx^2-u */

+    fe25519_add(p_root_check, vxx, u); /* vx^2+u */

+    fe25519_mul(f_root_check, u, fe25519_sqrtm1); /* u*sqrt(-1) */

+    fe25519_add(f_root_check, vxx, f_root_check); /* vx^2+u*sqrt(-1) */

+    has_m_root = fe25519_iszero(m_root_check);

+    has_p_root = fe25519_iszero(p_root_check);

+    has_f_root = fe25519_iszero(f_root_check);

+    fe25519_mul(x_sqrtm1, x, fe25519_sqrtm1); /* x*sqrt(-1) */

+

+    fe25519_cmov(x, x_sqrtm1, has_p_root | has_f_root);

+    fe25519_abs(x);

+

+    return has_m_root | has_p_root;

+}

+

+static int

+ristretto255_is_canonical(const unsigned char *s)

+{

+    unsigned char c;

+    unsigned char d;

+    unsigned char e;

+    unsigned int  i;

+

+    c = (s[31] & 0x7f) ^ 0x7f;

+    for (i = 30; i > 0; i--) {

+        c |= s[i] ^ 0xff;

+    }

+    c = (((unsigned int) c) - 1U) >> 8;

+    d = (0xed - 1U - (unsigned int) s[0]) >> 8;

+    e = s[31] >> 7;

+

+    return 1 - (((c & d) | e | s[0]) & 1);

+}

+

+int

+ristretto255_frombytes(ge25519_p3 *h, const unsigned char *s)

+{

+    fe25519 inv_sqrt;

+    fe25519 one;

+    fe25519 s_;

+    fe25519 ss;

+    fe25519 u1, u2;

+    fe25519 u1u1, u2u2;

+    fe25519 v;

+    fe25519 v_u2u2;

+    int     notsquare;

+

+    if (ristretto255_is_canonical(s) == 0) {

+        return -1;

+    }

+    fe25519_frombytes(s_, s);

+    fe25519_sq(ss, s_);                /* ss = s^2 */

+

+    fe25519_1(u1);

+    fe25519_sub(u1, u1, ss);           /* u1 = 1-ss */

+    fe25519_sq(u1u1, u1);              /* u1u1 = u1^2 */

+

+    fe25519_1(u2);

+    fe25519_add(u2, u2, ss);           /* u2 = 1+ss */

+    fe25519_sq(u2u2, u2);              /* u2u2 = u2^2 */

+

+    fe25519_mul(v, ed25519_d, u1u1);   /* v = d*u1^2 */

+    fe25519_neg(v, v);                 /* v = -d*u1^2 */

+    fe25519_sub(v, v, u2u2);           /* v = -(d*u1^2)-u2^2 */

+

+    fe25519_mul(v_u2u2, v, u2u2);      /* v_u2u2 = v*u2^2 */

+

+    fe25519_1(one);

+    notsquare = ristretto255_sqrt_ratio_m1(inv_sqrt, one, v_u2u2);

+    fe25519_mul(h->X, inv_sqrt, u2);

+    fe25519_mul(h->Y, inv_sqrt, h->X);

+    fe25519_mul(h->Y, h->Y, v);

+

+    fe25519_mul(h->X, h->X, s_);

+    fe25519_add(h->X, h->X, h->X);

+    fe25519_abs(h->X);

+    fe25519_mul(h->Y, u1, h->Y);

+    fe25519_1(h->Z);

+    fe25519_mul(h->T, h->X, h->Y);

+

+    return - ((1 - notsquare) |

+              fe25519_isnegative(h->T) | fe25519_iszero(h->Y));

+}

+

+void

+ristretto255_p3_tobytes(unsigned char *s, const ge25519_p3 *h)

+{

+    fe25519 den1, den2;

+    fe25519 den_inv;

+    fe25519 eden;

+    fe25519 inv_sqrt;

+    fe25519 ix, iy;

+    fe25519 one;

+    fe25519 s_;

+    fe25519 t_z_inv;

+    fe25519 u1, u2;

+    fe25519 u1_u2u2;

+    fe25519 x_, y_;

+    fe25519 x_z_inv;

+    fe25519 z_inv;

+    fe25519 zmy;

+    int     rotate;

+

+    fe25519_add(u1, h->Z, h->Y);       /* u1 = Z+Y */

+    fe25519_sub(zmy, h->Z, h->Y);      /* zmy = Z-Y */

+    fe25519_mul(u1, u1, zmy);          /* u1 = (Z+Y)*(Z-Y) */

+    fe25519_mul(u2, h->X, h->Y);       /* u2 = X*Y */

+

+    fe25519_sq(u1_u2u2, u2);           /* u1_u2u2 = u2^2 */

+    fe25519_mul(u1_u2u2, u1, u1_u2u2); /* u1_u2u2 = u1*u2^2 */

+

+    fe25519_1(one);

+    (void) ristretto255_sqrt_ratio_m1(inv_sqrt, one, u1_u2u2);

+    fe25519_mul(den1, inv_sqrt, u1);   /* den1 = inv_sqrt*u1 */

+    fe25519_mul(den2, inv_sqrt, u2);   /* den2 = inv_sqrt*u2 */

+    fe25519_mul(z_inv, den1, den2);    /* z_inv = den1*den2 */

+    fe25519_mul(z_inv, z_inv, h->T);   /* z_inv = den1*den2*T */

+

+    fe25519_mul(ix, h->X, fe25519_sqrtm1);       /* ix = X*sqrt(-1) */

+    fe25519_mul(iy, h->Y, fe25519_sqrtm1);       /* iy = Y*sqrt(-1) */

+    fe25519_mul(eden, den1, ed25519_invsqrtamd); /* eden = den1/sqrt(a-d) */

+

+    fe25519_mul(t_z_inv, h->T, z_inv); /* t_z_inv = T*z_inv */

+    rotate = fe25519_isnegative(t_z_inv);

+

+    fe25519_copy(x_, h->X);

+    fe25519_copy(y_, h->Y);

+    fe25519_copy(den_inv, den2);

+

+    fe25519_cmov(x_, iy, rotate);

+    fe25519_cmov(y_, ix, rotate);

+    fe25519_cmov(den_inv, eden, rotate);

+

+    fe25519_mul(x_z_inv, x_, z_inv);

+    fe25519_cneg(y_, fe25519_isnegative(x_z_inv));

+

+    fe25519_sub(s_, h->Z, y_);

+    fe25519_mul(s_, den_inv, s_);

+    fe25519_abs(s_);

+    fe25519_tobytes(s, s_);

+}

+

+static void

+ristretto255_elligator(ge25519_p3 *p, const fe25519 t)

+{

+    fe25519 c;

+    fe25519 n;

+    fe25519 one;

+    fe25519 r;

+    fe25519 rpd;

+    fe25519 s, s_prime;

+    fe25519 ss;

+    fe25519 u, v;

+    fe25519 w0, w1, w2, w3;

+    int     wasnt_square;

+

+    fe25519_1(one);

+    fe25519_sq(r, t);                  /* r = t^2 */

+    fe25519_mul(r, fe25519_sqrtm1, r); /* r = sqrt(-1)*t^2 */

+    fe25519_add(u, r, one);            /* u = r+1 */

+    fe25519_mul(u, u, ed25519_onemsqd);/* u = (r+1)*(1-d^2) */

+    fe25519_1(c);

+    fe25519_neg(c, c);                 /* c = -1 */

+    fe25519_add(rpd, r, ed25519_d);    /* rpd = r+d */

+    fe25519_mul(v, r, ed25519_d);      /* v = r*d */

+    fe25519_sub(v, c, v);              /* v = c-r*d */

+    fe25519_mul(v, v, rpd);            /* v = (c-r*d)*(r+d) */

+

+    wasnt_square = 1 - ristretto255_sqrt_ratio_m1(s, u, v);

+    fe25519_mul(s_prime, s, t);

+    fe25519_abs(s_prime);

+    fe25519_neg(s_prime, s_prime);     /* s_prime = -|s*t| */

+    fe25519_cmov(s, s_prime, wasnt_square);

+    fe25519_cmov(c, r, wasnt_square);

+

+    fe25519_sub(n, r, one);            /* n = r-1 */

+    fe25519_mul(n, n, c);              /* n = c*(r-1) */

+    fe25519_mul(n, n, ed25519_sqdmone); /* n = c*(r-1)*(d-1)^2 */

+    fe25519_sub(n, n, v);              /* n =  c*(r-1)*(d-1)^2-v */

+

+    fe25519_add(w0, s, s);             /* w0 = 2s */

+    fe25519_mul(w0, w0, v);            /* w0 = 2s*v */

+    fe25519_mul(w1, n, ed25519_sqrtadm1); /* w1 = n*sqrt(ad-1) */

+    fe25519_sq(ss, s);                 /* ss = s^2 */

+    fe25519_sub(w2, one, ss);          /* w2 = 1-s^2 */

+    fe25519_add(w3, one, ss);          /* w3 = 1+s^2 */

+

+    fe25519_mul(p->X, w0, w3);

+    fe25519_mul(p->Y, w2, w1);

+    fe25519_mul(p->Z, w1, w3);

+    fe25519_mul(p->T, w0, w2);

+}

+

+void

+ristretto255_from_hash(unsigned char s[32], const unsigned char h[64])

+{

+    fe25519        r0, r1;

+    ge25519_p3     p0, p1;

+    ge25519_p3     p;

+

+    fe25519_frombytes(r0, h);

+    fe25519_frombytes(r1, h + 32);

+    ristretto255_elligator(&p0, r0);

+    ristretto255_elligator(&p1, r1);

+    ge25519_p3_add(&p, &p0, &p1);

+    ristretto255_p3_tobytes(s, &p);

+}

diff --git a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/constants.h b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/constants.h
index 4371d4ceb8..4bd679755c 100644
--- a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/constants.h
+++ b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/constants.h
@@ -1,20 +1,46 @@
+/* sqrt(-1) */

+static const fe25519 fe25519_sqrtm1 = {

+    -32595792, -7943725,  9377950,  3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482

+};

+

+/* sqrt(-486664) */

+static const fe25519 ed25519_sqrtam2 = {

+    -12222970, -8312128, -11511410, 9067497, -15300785, -241793, 25456130, 14121551, -12187136, 3972024

+};

+

 /* 37095705934669439343138083508754565189542113879843219016388785533085940283555 */

-static const fe25519 d = {

+static const fe25519 ed25519_d = {

     -10913610, 13857413, -15372611, 6949391,   114729, -8787816, -6275908, -3247719, -18696448, -12055116

 };

 

 /* 2 * d =

  * 16295367250680780974490674513165176452449235426866156013048779062215315747161

  */

-static const fe25519 d2 = {

+static const fe25519 ed25519_d2 = {

     -21827239, -5839606,  -30745221, 13898782, 229458, 15978800, -12551817, -6495438, 29715968, 9444199 };

 

-/* sqrt(-1) */

-static const fe25519 sqrtm1 = {

-    -32595792, -7943725,  9377950,  3500415, 12389472, -272473, -25146209, -2005654, 326686, 11406482

+/* A = 486662 */

+#define ed25519_A_32 486662

+static const fe25519 ed25519_A = {

+    ed25519_A_32, 0, 0, 0, 0, 0, 0, 0, 0, 0

 };

 

-/* A = 486662 */

-static const fe25519 curve25519_A = {

-    486662, 0, 0, 0, 0, 0, 0, 0, 0, 0

+/* sqrt(ad - 1) with a = -1 (mod p) */

+static const fe25519 ed25519_sqrtadm1 = {

+    24849947, -153582, -23613485, 6347715, -21072328, -667138, -25271143, -15367704, -870347, 14525639

+};

+

+/* 1 / sqrt(a - d) */

+static const fe25519 ed25519_invsqrtamd = {

+    6111485, 4156064, -27798727, 12243468, -25904040, 120897, 20826367, -7060776, 6093568, -1986012

+};

+

+/* 1 - d ^ 2 */

+static const fe25519 ed25519_onemsqd = {

+    6275446, -16617371, -22938544, -3773710, 11667077, 7397348, -27922721, 1766195, -24433858, 672203

+};

+

+/* (d - 1) ^ 2 */

+static const fe25519 ed25519_sqdmone = {

+    15551795, -11097455, -13425098, -10125071, -11896535, 10178284, -26634327, 4729244, -5282110, -10116402

 };

diff --git a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/fe.h b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/fe.h
index 57062a2dfc..70350baf34 100644
--- a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/fe.h
+++ b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_25_5/fe.h
@@ -1,5 +1,7 @@
+#include "private/quirks.h"

+

 /*

- Ignores top bit of h.

+ Ignores top bit of s.

  */

 

 void

diff --git a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/constants.h b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/constants.h
index 35e70fdc06..0a3d685222 100644
--- a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/constants.h
+++ b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/constants.h
@@ -1,21 +1,47 @@
+/* sqrt(-1) */

+static const fe25519 fe25519_sqrtm1 = {

+    1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133

+};

+

+/* sqrt(-486664) */

+static const fe25519 ed25519_sqrtam2 = {

+    1693982333959686, 608509411481997, 2235573344831311, 947681270984193, 266558006233600

+};

+

 /* 37095705934669439343138083508754565189542113879843219016388785533085940283555 */

-static const fe25519 d = {

+static const fe25519 ed25519_d = {

     929955233495203, 466365720129213, 1662059464998953, 2033849074728123, 1442794654840575

 };

 

 /* 2 * d =

  * 16295367250680780974490674513165176452449235426866156013048779062215315747161

  */

-static const fe25519 d2 = {

+static const fe25519 ed25519_d2 = {

     1859910466990425, 932731440258426, 1072319116312658, 1815898335770999, 633789495995903

 };

 

-/* sqrt(-1) */

-static const fe25519 sqrtm1 = {

-    1718705420411056, 234908883556509, 2233514472574048, 2117202627021982, 765476049583133

+/* A = 486662 */

+#define ed25519_A_32 486662

+static const fe25519 ed25519_A = {

+    ed25519_A_32, 0, 0, 0, 0

 };

 

-/* A = 486662 */

-static const fe25519 curve25519_A = {

-    486662, 0, 0, 0, 0

+/* sqrt(ad - 1) with a = -1 (mod p) */

+static const fe25519 ed25519_sqrtadm1 = {

+    2241493124984347, 425987919032274, 2207028919301688, 1220490630685848, 974799131293748

+};

+

+/* 1 / sqrt(a - d) */

+static const fe25519 ed25519_invsqrtamd = {

+    278908739862762, 821645201101625, 8113234426968, 1777959178193151, 2118520810568447

+};

+

+/* 1 - d ^ 2 */

+static const fe25519 ed25519_onemsqd = {

+    1136626929484150, 1998550399581263, 496427632559748, 118527312129759, 45110755273534

+};

+

+/* (d - 1) ^ 2 */

+static const fe25519 ed25519_sqdmone = {

+    1507062230895904, 1572317787530805, 683053064812840, 317374165784489, 1572899562415810

 };

diff --git a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/fe.h b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/fe.h
index d79370b067..c50567ce45 100644
--- a/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/fe.h
+++ b/libs/libsodium/src/crypto_core/ed25519/ref10/fe_51/fe.h
@@ -1,5 +1,7 @@
+#include "private/quirks.h"

+

 /*

- Ignores top bit of h.

+ Ignores top bit of s.

  */

 

 void

diff --git a/libs/libsodium/src/crypto_core/salsa/ref/core_salsa_ref.c b/libs/libsodium/src/crypto_core/salsa/ref/core_salsa_ref.c
index ce300f67ea..4cbef62a9c 100644
--- a/libs/libsodium/src/crypto_core/salsa/ref/core_salsa_ref.c
+++ b/libs/libsodium/src/crypto_core/salsa/ref/core_salsa_ref.c
@@ -127,7 +127,7 @@ crypto_core_salsa20_constbytes(void)
 }

 

 #ifndef MINIMAL

-

+/* LCOV_EXCL_START */

 int

 crypto_core_salsa2012(unsigned char *out, const unsigned char *in,

                       const unsigned char *k, const unsigned char *c)

@@ -191,5 +191,5 @@ crypto_core_salsa208_constbytes(void)
 {

     return crypto_core_salsa208_CONSTBYTES;

 }

-

+/* LCOV_EXCL_END */

 #endif

diff --git a/libs/libsodium/src/crypto_core/softaes/softaes.c b/libs/libsodium/src/crypto_core/softaes/softaes.c
new file mode 100644
index 0000000000..ae469c8acd
--- /dev/null
+++ b/libs/libsodium/src/crypto_core/softaes/softaes.c
@@ -0,0 +1,143 @@
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "private/common.h"
+#include "private/softaes.h"
+
+uint32_t _aes_lut[256] __attribute__ ((visibility ("hidden"))) = {
+    0xa56363c6, 0x847c7cf8, 0x997777ee, 0x8d7b7bf6, 0x0df2f2ff, 0xbd6b6bd6, 0xb16f6fde, 0x54c5c591,
+    0x50303060, 0x03010102, 0xa96767ce, 0x7d2b2b56, 0x19fefee7, 0x62d7d7b5, 0xe6abab4d, 0x9a7676ec,
+    0x45caca8f, 0x9d82821f, 0x40c9c989, 0x877d7dfa, 0x15fafaef, 0xeb5959b2, 0xc947478e, 0x0bf0f0fb,
+    0xecadad41, 0x67d4d4b3, 0xfda2a25f, 0xeaafaf45, 0xbf9c9c23, 0xf7a4a453, 0x967272e4, 0x5bc0c09b,
+    0xc2b7b775, 0x1cfdfde1, 0xae93933d, 0x6a26264c, 0x5a36366c, 0x413f3f7e, 0x02f7f7f5, 0x4fcccc83,
+    0x5c343468, 0xf4a5a551, 0x34e5e5d1, 0x08f1f1f9, 0x937171e2, 0x73d8d8ab, 0x53313162, 0x3f15152a,
+    0x0c040408, 0x52c7c795, 0x65232346, 0x5ec3c39d, 0x28181830, 0xa1969637, 0x0f05050a, 0xb59a9a2f,
+    0x0907070e, 0x36121224, 0x9b80801b, 0x3de2e2df, 0x26ebebcd, 0x6927274e, 0xcdb2b27f, 0x9f7575ea,
+    0x1b090912, 0x9e83831d, 0x742c2c58, 0x2e1a1a34, 0x2d1b1b36, 0xb26e6edc, 0xee5a5ab4, 0xfba0a05b,
+    0xf65252a4, 0x4d3b3b76, 0x61d6d6b7, 0xceb3b37d, 0x7b292952, 0x3ee3e3dd, 0x712f2f5e, 0x97848413,
+    0xf55353a6, 0x68d1d1b9, 0x00000000, 0x2cededc1, 0x60202040, 0x1ffcfce3, 0xc8b1b179, 0xed5b5bb6,
+    0xbe6a6ad4, 0x46cbcb8d, 0xd9bebe67, 0x4b393972, 0xde4a4a94, 0xd44c4c98, 0xe85858b0, 0x4acfcf85,
+    0x6bd0d0bb, 0x2aefefc5, 0xe5aaaa4f, 0x16fbfbed, 0xc5434386, 0xd74d4d9a, 0x55333366, 0x94858511,
+    0xcf45458a, 0x10f9f9e9, 0x06020204, 0x817f7ffe, 0xf05050a0, 0x443c3c78, 0xba9f9f25, 0xe3a8a84b,
+    0xf35151a2, 0xfea3a35d, 0xc0404080, 0x8a8f8f05, 0xad92923f, 0xbc9d9d21, 0x48383870, 0x04f5f5f1,
+    0xdfbcbc63, 0xc1b6b677, 0x75dadaaf, 0x63212142, 0x30101020, 0x1affffe5, 0x0ef3f3fd, 0x6dd2d2bf,
+    0x4ccdcd81, 0x140c0c18, 0x35131326, 0x2fececc3, 0xe15f5fbe, 0xa2979735, 0xcc444488, 0x3917172e,
+    0x57c4c493, 0xf2a7a755, 0x827e7efc, 0x473d3d7a, 0xac6464c8, 0xe75d5dba, 0x2b191932, 0x957373e6,
+    0xa06060c0, 0x98818119, 0xd14f4f9e, 0x7fdcdca3, 0x66222244, 0x7e2a2a54, 0xab90903b, 0x8388880b,
+    0xca46468c, 0x29eeeec7, 0xd3b8b86b, 0x3c141428, 0x79dedea7, 0xe25e5ebc, 0x1d0b0b16, 0x76dbdbad,
+    0x3be0e0db, 0x56323264, 0x4e3a3a74, 0x1e0a0a14, 0xdb494992, 0x0a06060c, 0x6c242448, 0xe45c5cb8,
+    0x5dc2c29f, 0x6ed3d3bd, 0xefacac43, 0xa66262c4, 0xa8919139, 0xa4959531, 0x37e4e4d3, 0x8b7979f2,
+    0x32e7e7d5, 0x43c8c88b, 0x5937376e, 0xb76d6dda, 0x8c8d8d01, 0x64d5d5b1, 0xd24e4e9c, 0xe0a9a949,
+    0xb46c6cd8, 0xfa5656ac, 0x07f4f4f3, 0x25eaeacf, 0xaf6565ca, 0x8e7a7af4, 0xe9aeae47, 0x18080810,
+    0xd5baba6f, 0x887878f0, 0x6f25254a, 0x722e2e5c, 0x241c1c38, 0xf1a6a657, 0xc7b4b473, 0x51c6c697,
+    0x23e8e8cb, 0x7cdddda1, 0x9c7474e8, 0x211f1f3e, 0xdd4b4b96, 0xdcbdbd61, 0x868b8b0d, 0x858a8a0f,
+    0x907070e0, 0x423e3e7c, 0xc4b5b571, 0xaa6666cc, 0xd8484890, 0x05030306, 0x01f6f6f7, 0x120e0e1c,
+    0xa36161c2, 0x5f35356a, 0xf95757ae, 0xd0b9b969, 0x91868617, 0x58c1c199, 0x271d1d3a, 0xb99e9e27,
+    0x38e1e1d9, 0x13f8f8eb, 0xb398982b, 0x33111122, 0xbb6969d2, 0x70d9d9a9, 0x898e8e07, 0xa7949433,
+    0xb69b9b2d, 0x221e1e3c, 0x92878715, 0x20e9e9c9, 0x49cece87, 0xff5555aa, 0x78282850, 0x7adfdfa5,
+    0x8f8c8c03, 0xf8a1a159, 0x80898909, 0x170d0d1a, 0xdabfbf65, 0x31e6e6d7, 0xc6424284, 0xb86868d0,
+    0xc3414182, 0xb0999929, 0x772d2d5a, 0x110f0f1e, 0xcbb0b07b, 0xfc5454a8, 0xd6bbbb6d, 0x3a16162c
+};
+
+static const uint32_t * const LUT = _aes_lut;
+
+#ifndef SOFTAES_STRIDE
+# ifdef FAVOR_PERFORMANCE
+#  define SOFTAES_STRIDE 256
+# else
+#  define SOFTAES_STRIDE 16
+# endif
+#endif
+
+static SoftAesBlock
+_encrypt(const uint8_t ix0[4], const uint8_t ix1[4], const uint8_t ix2[4], const uint8_t ix3[4])
+{
+    CRYPTO_ALIGN(64) uint32_t     t[4][4][256 / SOFTAES_STRIDE];
+    CRYPTO_ALIGN(64) uint8_t      of[4][4];
+    CRYPTO_ALIGN(64) SoftAesBlock out;
+    size_t                        i;
+    size_t                        j;
+
+    for (j = 0; j < 4; j++) {
+        of[j][0] = ix0[j] % SOFTAES_STRIDE;
+        of[j][1] = ix1[j] % SOFTAES_STRIDE;
+        of[j][2] = ix2[j] % SOFTAES_STRIDE;
+        of[j][3] = ix3[j] % SOFTAES_STRIDE;
+    }
+    for (i = 0; i < 256 / SOFTAES_STRIDE; i++) {
+        for (j = 0; j < 4; j++) {
+            t[j][0][i] = LUT[(i * SOFTAES_STRIDE) | of[j][0]];
+            t[j][1][i] = LUT[(i * SOFTAES_STRIDE) | of[j][1]];
+            t[j][2][i] = LUT[(i * SOFTAES_STRIDE) | of[j][2]];
+            t[j][3][i] = LUT[(i * SOFTAES_STRIDE) | of[j][3]];
+        }
+    }
+
+#ifdef HAVE_INLINE_ASM
+    __asm__ __volatile__("" : : "r"(t) : "memory");
+#endif
+
+    out.w0 = t[0][0][ix0[0] / SOFTAES_STRIDE];
+    out.w0 ^= ROTL32(t[0][1][ix1[0] / SOFTAES_STRIDE], 8);
+    out.w0 ^= ROTL32(t[0][2][ix2[0] / SOFTAES_STRIDE], 16);
+    out.w0 ^= ROTL32(t[0][3][ix3[0] / SOFTAES_STRIDE], 24);
+
+    out.w1 = t[1][0][ix0[1] / SOFTAES_STRIDE];
+    out.w1 ^= ROTL32(t[1][1][ix1[1] / SOFTAES_STRIDE], 8);
+    out.w1 ^= ROTL32(t[1][2][ix2[1] / SOFTAES_STRIDE], 16);
+    out.w1 ^= ROTL32(t[1][3][ix3[1] / SOFTAES_STRIDE], 24);
+
+    out.w2 = t[2][0][ix0[2] / SOFTAES_STRIDE];
+    out.w2 ^= ROTL32(t[2][1][ix1[2] / SOFTAES_STRIDE], 8);
+    out.w2 ^= ROTL32(t[2][2][ix2[2] / SOFTAES_STRIDE], 16);
+    out.w2 ^= ROTL32(t[2][3][ix3[2] / SOFTAES_STRIDE], 24);
+
+    out.w3 = t[3][0][ix0[3] / SOFTAES_STRIDE];
+    out.w3 ^= ROTL32(t[3][1][ix1[3] / SOFTAES_STRIDE], 8);
+    out.w3 ^= ROTL32(t[3][2][ix2[3] / SOFTAES_STRIDE], 16);
+    out.w3 ^= ROTL32(t[3][3][ix3[3] / SOFTAES_STRIDE], 24);
+
+    return out;
+}
+
+SoftAesBlock
+softaes_block_encrypt(const SoftAesBlock block, const SoftAesBlock rk)
+{
+    CRYPTO_ALIGN(64) SoftAesBlock out;
+    CRYPTO_ALIGN(64) uint8_t      ix0[4], ix1[4], ix2[4], ix3[4];
+    const uint32_t                s0 = block.w0;
+    const uint32_t                s1 = block.w1;
+    const uint32_t                s2 = block.w2;
+    const uint32_t                s3 = block.w3;
+
+    ix0[0] = (uint8_t) s0;
+    ix0[1] = (uint8_t) s1;
+    ix0[2] = (uint8_t) s2;
+    ix0[3] = (uint8_t) s3;
+
+    ix1[0] = (uint8_t) (s1 >> 8);
+    ix1[1] = (uint8_t) (s2 >> 8);
+    ix1[2] = (uint8_t) (s3 >> 8);
+    ix1[3] = (uint8_t) (s0 >> 8);
+
+    ix2[0] = (uint8_t) (s2 >> 16);
+    ix2[1] = (uint8_t) (s3 >> 16);
+    ix2[2] = (uint8_t) (s0 >> 16);
+    ix2[3] = (uint8_t) (s1 >> 16);
+
+    ix3[0] = (uint8_t) (s3 >> 24);
+    ix3[1] = (uint8_t) (s0 >> 24);
+    ix3[2] = (uint8_t) (s1 >> 24);
+    ix3[3] = (uint8_t) (s2 >> 24);
+
+    out = _encrypt(ix0, ix1, ix2, ix3);
+
+    out.w0 ^= rk.w0;
+    out.w1 ^= rk.w1;
+    out.w2 ^= rk.w2;
+    out.w3 ^= rk.w3;
+
+    return out;
+}