--- /dev/null
+/* -*-c-*-
+ *
+ * The Ed25519 signature scheme
+ *
+ * (c) 2017 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of secnet.
+ * See README for full list of copyright holders.
+ *
+ * secnet is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version d of the License, or
+ * (at your option) any later version.
+ *
+ * secnet is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * version 3 along with secnet; if not, see
+ * https://www.gnu.org/licenses/gpl.html.
+ *
+ * This file was originally part of Catacomb, but has been automatically
+ * modified for incorporation into secnet: see `import-catacomb-crypto'
+ * for details.
+ *
+ * Catacomb is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * Catacomb is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with Catacomb; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <string.h>
+
+#include "f25519.h"
+#include "ed25519.h"
+#include "scaf.h"
+#include "scmul.h"
+#include "sha512.h"
+
+/*----- A number of magic numbers -----------------------------------------*/
+
+# define PIECEWD 24
+ static const scaf_piece l[] = {
+ 0xf5d3ed, 0x631a5c, 0xd65812, 0xa2f79c, 0xdef9de, 0x000014,
+ 0x000000, 0x000000, 0x000000, 0x000000, 0x001000
+ };
+ static const scaf_piece mu[] = {
+ 0x1b3994, 0x0a2c13, 0x9ce5a3, 0x29a7ed, 0x5d0863, 0x210621,
+ 0xffffeb, 0xffffff, 0xffffff, 0xffffff, 0xffffff, 0x000fff
+ };
+
+#define NPIECE SCAF_NPIECE(255, PIECEWD)
+
+# define P p26
+ static const f25519_piece bx_pieces[] = {
+ -14297830, -7645148, 16144683, -16471763, 27570974,
+ -2696100, -26142465, 8378389, 20764389, 8758491
+ }, by_pieces[] = {
+ -26843541, -6710886, 13421773, -13421773, 26843546,
+ 6710886, -13421773, 13421773, -26843546, -6710886
+ }, d_pieces[] = {
+ -10913610, 13857413, -15372611, 6949391, 114729,
+ -8787816, -6275908, -3247719, -18696448, -12055116
+ };
+
+static const f25519_piece bz_pieces[NPIECE] = { 1, 0, /* ... */ };
+#define BX ((const f25519 *)bx_pieces)
+#define BY ((const f25519 *)by_pieces)
+#define BZ ((const f25519 *)bz_pieces)
+#define D ((const f25519 *)d_pieces)
+
+/*----- Point encoding and decoding ---------------------------------------*/
+
+static void ptencode(octet q[32],
+ const f25519 *X, const f25519 *Y, const f25519 *Z)
+{
+ f25519 x, y, t;
+ octet b[32];
+
+ f25519_inv(&t, Z); f25519_mul(&x, X, &t); f25519_mul(&y, Y, &t);
+ f25519_store(q, &y); f25519_store(b, &x); q[31] |= (b[0]&1u) << 7;
+}
+
+static int ptdecode(f25519 *X, f25519 *Y, f25519 *Z, const octet q[32])
+{
+ octet b[32];
+ unsigned i, a;
+ f25519 t, u;
+ uint32 m;
+ int rc = 0;
+
+ /* Load the y-coordinate. */
+ memcpy(b, q, 32); b[31] &= 0x7fu; f25519_load(Y, b);
+
+ /* Check that the coordinate was in range. If we store it, we'll get a
+ * canonical version which we can compare against Q; be careful not to
+ * check the top bit.
+ */
+ f25519_store(b, Y);
+ for (i = a = 0; i < 31; i++) a |= b[i] ^ q[i];
+ a |= (b[31] ^ q[31])&0x7fu;
+ a = ((a - 1) >> 8)&0x01u; /* 0 |-> 1, non-0 |-> 0 */
+ rc |= (int)a - 1;
+
+ /* Decompress the x-coordinate. */
+ f25519_sqr(&t, Y); f25519_mul(&u, &t, D); t.P[0] -= 1; u.P[0] += 1;
+ rc |= f25519_quosqrt(X, &t, &u);
+ f25519_store(b, X); m = -(uint32)(((q[31] >> 7) ^ b[0])&0x1u);
+ f25519_condneg(X, X, m);
+
+ /* Set Z. */
+ f25519_set(Z, 1);
+
+ /* And we're done. */
+ return (rc);
+}
+
+/*----- Edwards curve arithmetic ------------------------------------------*/
+
+static void ptadd(f25519 *X, f25519 *Y, f25519 *Z,
+ const f25519 *X0, const f25519 *Y0, const f25519 *Z0,
+ const f25519 *X1, const f25519 *Y1, const f25519 *Z1)
+{
+ f25519 t0, t1, t2, t3;
+
+ /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
+ * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
+ * formulae as:
+ *
+ * A = Z1 Z2; B = A^2; C = X1 X2; D = Y1 Y2;
+ * E = d C D; F = B - E; G = B + E;
+ * X3 = A F ((X1 + Y1) (X2 + Y2) - C - D);
+ * Y3 = A G (D - a C); Z3 = F G.
+ *
+ * Note that a = -1, which things easier.
+ */
+
+ f25519_mul(&t0, Z0, Z1); /* t0 = A = Z0 Z1 */
+ f25519_add(&t1, X0, Y0); /* t1 = X0 + Y0 */
+ f25519_add(&t2, X1, Y1); /* t2 = X1 + Y1 */
+ f25519_mul(&t1, &t1, &t2); /* t1 = (X0 + Y0) (X1 + Y1) */
+ f25519_mul(&t2, X0, X1); /* t2 = C = X0 X1 */
+ f25519_mul(&t3, Y0, Y1); /* t3 = D = Y0 Y1 */
+ f25519_add(Y, &t2, &t3); /* Y = C + D = D - a C */
+ f25519_sub(X, &t1, Y); /* X = (X0 + Y0) (X1 + Y1) - C - D */
+ f25519_mul(X, X, &t0); /* X = A ((X0 + Y0) (X1 + Y1) - C - D) */
+ f25519_mul(Y, Y, &t0); /* Y = A (D - a C) */
+ f25519_sqr(&t0, &t0); /* t0 = B = A^2 */
+ f25519_mul(&t1, &t2, &t3); /* t1 = C D */
+ f25519_mul(&t1, &t1, D); /* t1 = E = d C D */
+ f25519_sub(&t2, &t0, &t1); /* t2 = F = B - E */
+ f25519_add(&t1, &t0, &t1); /* t1 = G = B + E */
+ f25519_mul(X, X, &t2); /* X = A F ((X0 + Y0) (X1 + Y1) - C - D) */
+ f25519_mul(Y, Y, &t1); /* Y = A G (D - a C) */
+ f25519_mul(Z, &t1, &t2); /* Z = F G */
+}
+
+static void ptdbl(f25519 *X, f25519 *Y, f25519 *Z,
+ const f25519 *X0, const f25519 *Y0, const f25519 *Z0)
+{
+ f25519 t0, t1, t2;
+
+ /* Bernstein, Birkner, Joye, Lange, and Peters, `Twisted Edwards Curves',
+ * 2008-03-13, https://cr.yp.to/newelliptic/twisted-20080313.pdf shows the
+ * formulae as:
+ *
+ * B = (X1 + Y1)^2; C = X1^2; D = Y1^2; E = a C;
+ * F = E + D; H = Z1^2; J = F - 2 H;
+ * X3 = (B - C - D) J; Y3 = F (E - D); Z3 = F J.
+ *
+ * Note that a = -1, which things easier.
+ */
+
+ f25519_add(&t0, X0, Y0); /* t0 = X0 + Y0 */
+ f25519_sqr(&t0, &t0); /* t0 = B = (X0 + Y0)^2 */
+ f25519_sqr(&t1, X0); /* t1 = C = X0^2 */
+ f25519_sqr(&t2, Y0); /* t2 = D = Y0^2 */
+ f25519_add(Y, &t1, &t2); /* Y = C + D = -(E - D) */
+ f25519_sub(X, &t0, Y); /* X = B - C - D */
+ /* (E = a C = -C) */
+ f25519_sub(&t0, &t2, &t1); /* t0 = F = D - C = E + D */
+ f25519_sqr(&t1, Z0); /* t1 = H = Z0^2 */
+ f25519_add(&t1, &t1, &t1); /* t1 = 2 H */
+ f25519_sub(&t1, &t0, &t1); /* t1 = J = F - 2 H */
+ f25519_mul(X, X, &t1); /* X = (B - C - D) J */
+ f25519_mul(Y, Y, &t0); /* Y = -F (E - D) */
+ f25519_neg(Y, Y); /* Y = F (E - D) */
+ f25519_mul(Z, &t0, &t1); /* Z = F J */
+}
+
+static DEFINE_SCMUL(ptmul, f25519, 4, PIECEWD, NPIECE, ptadd, ptdbl)
+static DEFINE_SCSIMMUL(ptsimmul, f25519, 2, PIECEWD, NPIECE, ptadd, ptdbl)
+
+/*----- Key derivation utilities ------------------------------------------*/
+
+static void unpack_key(scaf_piece a[NPIECE], octet h1[32],
+ const octet *k, size_t ksz)
+{
+ struct sha512_ctx h;
+ octet b[SHA512_DIGEST_SIZE];
+
+ sha512_init_ctx(&h); sha512_process_bytes(k, ksz, &h); sha512_finish_ctx(&h, b);
+ b[0] &= 0xf8u; b[31] = (b[31]&0x3f) | 0x40;
+ scaf_load(a, b, 32, NPIECE, PIECEWD);
+ if (h1) memcpy(h1, b + 32, 32);
+}
+
+#define PREFIX_BUFSZ 290
+static size_t prefix(octet b[PREFIX_BUFSZ],
+ int phflag, const octet *p, size_t psz)
+{
+ if (phflag < 0) return (0);
+ memcpy(b, "SigEd25519 no Ed25519 collisions", 32);
+ b[32] = phflag;
+ assert(psz < ED25519_MAXPERSOSZ); b[33] = psz; memcpy(b + 34, p, psz);
+ return (psz + 34);
+}
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @ed25519_pubkey@ --- *
+ *
+ * Arguments: @octet K[ED25519_PUBSZ]@ = where to put the public key
+ * @const void *k@ = private key
+ * @size_t ksz@ = length of private key
+ *
+ * Returns: ---
+ *
+ * Use: Derives the public key from a private key.
+ */
+
+void ed25519_pubkey(octet K[ED25519_PUBSZ], const void *k, size_t ksz)
+{
+ scaf_piece a[NPIECE];
+ f25519 AX, AY, AZ;
+
+ unpack_key(a, 0, k, ksz);
+ ptmul(&AX, &AY, &AZ, a, BX, BY, BZ);
+ ptencode(K, &AX, &AY, &AZ);
+}
+
+/* --- @ed25519_sign@, @ed25519ctx_sign@ --- *
+ *
+ * Arguments: @octet sig[ED25519_SIGSZ]@ = where to put the signature
+ * @const void *k@ = private key
+ * @size_t ksz@ = length of private key
+ * @const octet K[ED25519_PUBSZ]@ = public key
+ * @int phflag@ = whether the `message' has been hashed already
+ * @const void *p@ = personalization string
+ * @size_t psz@ = length of personalization string
+ * @const void *m@ = message to sign
+ * @size_t msz@ = length of message
+ *
+ * Returns: ---
+ *
+ * Use: Signs a message.
+ *
+ * In @ed25519ctx_sign@, if @phflag@ is @-1@ then you get plain
+ * old Ed25519: the personalization string pointer @p@ will be
+ * ignored. If @phflag > 0@ then the `message' @m@ should be a
+ * SHA512 hash of the actual message.
+ */
+
+void ed25519ctx_sign(octet sig[ED25519_SIGSZ],
+ const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
+ int phflag, const void *p, size_t psz,
+ const void *m, size_t msz)
+{
+ struct sha512_ctx h;
+ scaf_piece a[NPIECE], r[NPIECE], t[NPIECE], scratch[3*NPIECE];
+ scaf_dblpiece tt[2*NPIECE];
+ f25519 RX, RY, RZ;
+ octet h1[32], pb[PREFIX_BUFSZ], rb[SHA512_DIGEST_SIZE];
+ unsigned i;
+
+ /* Get my private key. */
+ unpack_key(a, h1, k, ksz);
+
+ /* Determine the prefix string. */
+ psz = prefix(pb, phflag, p, psz);
+
+ /* Select the nonce and the vector part. */
+ sha512_init_ctx(&h);
+ sha512_process_bytes(pb, psz, &h);
+ sha512_process_bytes(h1, 32, &h);
+ sha512_process_bytes(m, msz, &h);
+ sha512_finish_ctx(&h, rb);
+ scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
+ scaf_reduce(r, tt, l, mu, NPIECE, PIECEWD, scratch);
+ ptmul(&RX, &RY, &RZ, r, BX, BY, BZ);
+ ptencode(sig, &RX, &RY, &RZ);
+
+ /* Calculate the scalar part. */
+ sha512_init_ctx(&h);
+ sha512_process_bytes(pb, psz, &h);
+ sha512_process_bytes(sig, 32, &h);
+ sha512_process_bytes(K, 32, &h);
+ sha512_process_bytes(m, msz, &h);
+ sha512_finish_ctx(&h, rb);
+ scaf_loaddbl(tt, rb, 64, 2*NPIECE, PIECEWD);
+ scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
+ scaf_mul(tt, t, a, NPIECE);
+ for (i = 0; i < NPIECE; i++) tt[i] += r[i];
+ scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
+ scaf_store(sig + 32, 32, t, NPIECE, PIECEWD);
+}
+
+void ed25519_sign(octet sig[ED25519_SIGSZ],
+ const void *k, size_t ksz, const octet K[ED25519_PUBSZ],
+ const void *m, size_t msz)
+ { ed25519ctx_sign(sig, k, ksz, K, -1, 0, 0, m, msz); }
+
+/* --- @ed25519_verify@, @ed25519ctx_verify@ --- *
+ *
+ * Arguments: @const octet K[ED25519_PUBSZ]@ = public key
+ * @int phflag@ = whether the `message' has been hashed already
+ * @const void *p@ = personalization string
+ * @size_t psz@ = length of personalization string
+ * @const void *m@ = message to sign
+ * @size_t msz@ = length of message
+ * @const octet sig[ED25519_SIGSZ]@ = signature
+ *
+ * Returns: Zero if OK, negative on failure.
+ *
+ * Use: Verify a signature.
+ *
+ * In @ed25519ctx_verify@, if @phflag@ is @-1@ then you get
+ * plain old Ed25519: the personalization string pointer @p@
+ * will be ignored. If @phflag > 0@ then the `message' @m@
+ * should be a SHA512 hash of the actual message.
+ */
+
+int ed25519ctx_verify(const octet K[ED25519_PUBSZ],
+ int phflag, const void *p, size_t psz,
+ const void *m, size_t msz,
+ const octet sig[ED25519_SIGSZ])
+{
+ struct sha512_ctx h;
+ scaf_piece s[NPIECE], t[NPIECE], scratch[3*NPIECE];
+ scaf_dblpiece tt[2*NPIECE];
+ f25519 AX, AY, AZ, RX, RY, RZ;
+ octet b[PREFIX_BUFSZ];
+
+ /* Unpack the public key. Negate it: we're meant to subtract the term
+ * involving the public key point, and this is easier than negating the
+ * scalar.
+ */
+ if (ptdecode(&AX, &AY, &AZ, K)) return (-1);
+ f25519_neg(&AX, &AX);
+
+ /* Load the scalar and check that it's in range. The easy way is to store
+ * it again and see if the two match.
+ */
+ scaf_loaddbl(tt, sig + 32, 32, 2*NPIECE, PIECEWD);
+ scaf_reduce(s, tt, l, mu, NPIECE, PIECEWD, scratch);
+ scaf_store(b, 32, s, NPIECE, PIECEWD);
+ if (memcmp(b, sig + 32, 32) != 0) return (-1);
+
+ /* Check the signature. */
+ psz = prefix(b, phflag, p, psz);
+ sha512_init_ctx(&h);
+ sha512_process_bytes(b, psz, &h);
+ sha512_process_bytes(sig, 32, &h);
+ sha512_process_bytes(K, 32, &h);
+ sha512_process_bytes(m, msz, &h);
+ sha512_finish_ctx(&h, b);
+ scaf_loaddbl(tt, b, 64, 2*NPIECE, PIECEWD);
+ scaf_reduce(t, tt, l, mu, NPIECE, PIECEWD, scratch);
+ ptsimmul(&RX, &RY, &RZ, s, BX, BY, BZ, t, &AX, &AY, &AZ);
+ ptencode(b, &RX, &RY, &RZ);
+ if (memcmp(b, sig, 32) != 0) return (-1);
+
+ /* All is good. */
+ return (0);
+}
+
+int ed25519_verify(const octet K[ED25519_PUBSZ],
+ const void *m, size_t msz,
+ const octet sig[ED25519_SIGSZ])
+ { return (ed25519ctx_verify(K, -1, 0, 0, m, msz, sig)); }
+
+/*----- That's all, folks -------------------------------------------------*/
~mdw / secnet / blobdiff