summaryrefslogtreecommitdiff
path: root/fe448.c
diff options
context:
space:
mode:
Diffstat (limited to 'fe448.c')
-rw-r--r--fe448.c345
1 files changed, 345 insertions, 0 deletions
diff --git a/fe448.c b/fe448.c
new file mode 100644
index 0000000..961e944
--- /dev/null
+++ b/fe448.c
@@ -0,0 +1,345 @@
+#define WINDOWSIZE 1 /* Should be 1,2, or 4 */
+#define WINDOWMASK ((1 << WINDOWSIZE) - 1)
+
+#include "fe448.h"
+
+/* 2**448-2**224-1 */
+static const crypto_uint32 m[57] = {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, 0xFE, 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, 0x00};
+
+/* 256**114//m */
+static const crypto_uint32 mu[59] = {0x00, 0x00, 0x02, 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, 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, 0x01};
+
+static crypto_uint32 equal(crypto_uint32 a, crypto_uint32 b) /* 16-bit inputs */
+{
+ crypto_uint32 x = a ^ b; /* 0: yes; 1..65535: no */
+ x -= 1; /* 4294967295: yes; 0..65534: no */
+ x >>= 31; /* 1: yes; 0: no */
+ return x;
+}
+
+static crypto_uint32 lt(crypto_uint32 a, crypto_uint32 b) /* 16-bit inputs */
+{
+ unsigned int x = a;
+ x -= (unsigned int)b; /* 0..65535: no; 4294901761..4294967295: yes */
+ x >>= 31; /* 0: no; 1: yes */
+ return x;
+}
+
+static void reduce_add_sub(fe448 *r)
+{
+ crypto_uint32 t;
+ int i, rep;
+
+ for (rep = 0; rep < 4; rep++)
+ {
+ t = r->v[56];
+ r->v[56] = 0;
+ r->v[0] += t;
+ r->v[28] += t;
+ for (i = 0; i < 56; i++)
+ {
+ t = r->v[i] >> 8;
+ r->v[i + 1] += t;
+ r->v[i] &= 255;
+ }
+ }
+}
+
+/* copied from sc448.c, a bit of slowly on 2**448-2**224-1 */
+static void barrett_reduce(fe448 *r, const crypto_uint32 x[114])
+{
+ /* See HAC, Alg. 14.42 */
+ int i, j;
+ crypto_uint32 q2[116];
+ crypto_uint32 *q3 = q2 + 58;
+ crypto_uint32 r1[58];
+ crypto_uint32 r2[58];
+ crypto_uint32 carry;
+ crypto_uint32 pb = 0;
+ crypto_uint32 b;
+
+ for (i = 0; i < 116; ++i)
+ q2[i] = 0;
+ for (i = 0; i < 58; ++i)
+ r2[i] = 0;
+
+ for (i = 0; i < 59; i++)
+ for (j = 0; j < 58; j++)
+ if (i + j >= 56)
+ q2[i + j] += mu[i] * x[j + 56];
+ carry = q2[56] >> 8;
+ q2[57] += carry;
+ carry = q2[57] >> 8;
+ q2[58] += carry;
+
+ for (i = 0; i < 58; i++)
+ r1[i] = x[i];
+ for (i = 0; i < 57; i++)
+ for (j = 0; j < 58; j++)
+ if (i + j < 58)
+ r2[i + j] += m[i] * q3[j];
+
+ for (i = 0; i < 57; i++)
+ {
+ carry = r2[i] >> 8;
+ r2[i + 1] += carry;
+ r2[i] &= 0xff;
+ }
+
+ for (i = 0; i < 57; i++)
+ {
+ pb += r2[i];
+ b = lt(r1[i], pb);
+ r->v[i] = r1[i] - pb + (b << 8);
+ pb = b;
+ }
+
+ reduce_add_sub(r);
+ reduce_add_sub(r);
+ reduce_add_sub(r);
+ reduce_add_sub(r);
+}
+
+/* reduction modulo 2**448-2**224-1 */
+void fe448_freeze(fe448 *r)
+{
+ int i;
+ crypto_uint32 m0;
+ crypto_uint32 m1;
+ crypto_uint32 b = 0, t;
+ m0 = equal(r->v[56], 0);
+ for (i = 55; i > 28; i--)
+ m0 &= equal(r->v[i], 255);
+ m1 = m0;
+ m0 &= equal(r->v[28], 255);
+ m1 &= equal(r->v[28], 254);
+ for (i = 27; i >= 0; i--)
+ m1 &= equal(r->v[i], 255);
+
+ m0 |= m1;
+ m0 = -m0;
+
+ for (i = 0; i < 57; i++)
+ {
+ t = r->v[i] - m[i] - b;
+ r->v[i] -= (m[i] + b) & 255 & m0;
+ b = (t >> 8) & 1;
+ }
+}
+
+void fe448_unpack(fe448 *r, const unsigned char x[57])
+{
+ int i;
+ for (i = 0; i < 56; i++)
+ r->v[i] = x[i];
+ r->v[56] = 0;
+}
+
+/* Assumes input x being reduced below 2^448 */
+void fe448_pack(unsigned char r[57], const fe448 *x)
+{
+ int i;
+ fe448 y = *x;
+ fe448_freeze(&y);
+ for (i = 0; i < 57; i++)
+ r[i] = y.v[i];
+}
+
+int fe448_iszero(const fe448 *x)
+{
+ int i;
+ int r;
+ fe448 t = *x;
+ fe448_freeze(&t);
+ r = equal(t.v[0], 0);
+ for (i = 1; i < 57; i++)
+ r &= equal(t.v[i], 0);
+ return r;
+}
+
+int fe448_iseq_vartime(const fe448 *x, const fe448 *y)
+{
+ int i;
+ fe448 t1 = *x;
+ fe448 t2 = *y;
+ fe448_freeze(&t1);
+ fe448_freeze(&t2);
+ for (i = 0; i < 57; i++)
+ if (t1.v[i] != t2.v[i])
+ return 0;
+ return 1;
+}
+
+void fe448_cmov(fe448 *r, const fe448 *x, unsigned char b)
+{
+ int i;
+ crypto_uint32 mask = b;
+ mask = -mask;
+ for (i = 0; i < 57; i++)
+ r->v[i] ^= mask & (x->v[i] ^ r->v[i]);
+}
+
+unsigned char fe448_getparity(const fe448 *x)
+{
+ fe448 t = *x;
+ fe448_freeze(&t);
+ return t.v[0] & 1;
+}
+
+void fe448_setone(fe448 *r)
+{
+ int i;
+ r->v[0] = 1;
+ for (i = 1; i < 57; i++)
+ r->v[i] = 0;
+}
+
+void fe448_setzero(fe448 *r)
+{
+ int i;
+ for (i = 0; i < 57; i++)
+ r->v[i] = 0;
+}
+
+void fe448_neg(fe448 *r, const fe448 *x)
+{
+ fe448 t;
+ int i;
+ for (i = 0; i < 57; i++)
+ t.v[i] = x->v[i];
+ fe448_setzero(r);
+ fe448_sub(r, r, &t);
+}
+
+void fe448_add(fe448 *r, const fe448 *x, const fe448 *y)
+{
+ int i;
+ for (i = 0; i < 57; i++)
+ r->v[i] = x->v[i] + y->v[i];
+ reduce_add_sub(r);
+}
+
+void fe448_sub(fe448 *r, const fe448 *x, const fe448 *y)
+{
+ int i;
+ crypto_uint32 t[57];
+ for (i = 0; i < 28; i++) /* add x with p previously so that r>0 */
+ {
+ t[i] = x->v[i] + 0x1fe;
+ }
+ t[28] = x->v[28] + 0x1fc;
+ for (i = 29; i < 56; i++)
+ {
+ t[i] = x->v[i] + 0x1fe;
+ }
+ t[56] = 0;
+ for (i = 0; i < 57; i++)
+ r->v[i] = t[i] - y->v[i];
+ reduce_add_sub(r);
+}
+
+/* a slow version copied from sc448.c */
+void fe448_mul(fe448 *r, const fe448 *x, const fe448 *y)
+{
+ int i, j, carry;
+ crypto_uint32 t[114];
+ for (i = 0; i < 114; i++)
+ t[i] = 0;
+
+ for (i = 0; i < 57; i++)
+ for (j = 0; j < 57; j++)
+ t[i + j] += x->v[i] * y->v[j];
+
+ for (i = 0; i < 113; i++)
+ {
+ carry = t[i] >> 8;
+ t[i + 1] += carry;
+ t[i] &= 0xff;
+ }
+
+ barrett_reduce(r, t);
+}
+
+void fe448_square(fe448 *r, const fe448 *x)
+{
+ fe448_mul(r, x, x);
+}
+
+void fe448_invert(fe448 *r, const fe448 *x)
+{
+ fe448 t0;
+ fe448 t1;
+ fe448 t2;
+ int i;
+
+ fe448_square(&t0, x);
+ fe448_mul(&t0, &t0, x); /* 2^2 - 1 */
+ fe448_square(&t0, &t0); /* 2^3 - 2 */
+ fe448_mul(&t1, &t0, x); /* 2^3 - 1 */
+ fe448_square(&t0, &t1); /* 2^4 - 2^1 */
+ for (i = 0; i < 2; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^6 - 2^3 */
+ fe448_mul(&t1, &t1, &t0); /* 2^6 - 1 */
+ fe448_square(&t0, &t1); /* 2^7 - 2^1 */
+ for (i = 0; i < 5; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^12 - 2^6 */
+ fe448_mul(&t1, &t1, &t0); /* 2^12 - 1 */
+ fe448_square(&t1, &t1); /* 2^13 - 2^1 */
+ fe448_mul(&t1, &t1, x); /* 2^13 - 1 */
+ fe448_square(&t0, &t1); /* 2^14 - 2^1 */
+ for (i = 0; i < 12; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^26 - 2^13 */
+ fe448_mul(&t1, &t1, &t0); /* 2^26 - 1 */
+ fe448_square(&t1, &t1); /* 2^26 - 2^1 */
+ fe448_mul(&t1, &t1, x); /* 2^27 - 1 */
+ fe448_square(&t0, &t1); /* 2^28 - 2^1 */
+ for (i = 0; i < 26; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^54 - 2^27 */
+ fe448_mul(&t1, &t1, &t0); /* 2^54 - 1 */
+ fe448_square(&t1, &t1); /* 2^55 - 2^1 */
+ fe448_mul(&t1, &t1, x); /* 2^55 - 1 */
+ fe448_square(&t0, &t1); /* 2^56 - 2^1 */
+ for (i = 0; i < 54; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^110 - 2^55 */
+ fe448_mul(&t1, &t1, &t0); /* 2^110 - 1 */
+ fe448_square(&t1, &t1); /* 2^111 - 2^1 */
+ fe448_mul(&t1, &t1, x); /* 2^111 - 1 */
+ fe448_square(&t0, &t1); /* 2^112 - 2^1 */
+ for (i = 0; i < 110; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^222 - 2^111 */
+ fe448_mul(&t2, &t1, &t0); /* 2^222 - 1 */
+ fe448_square(&t1, &t2); /* 2^223 - 2^1 */
+ fe448_mul(&t1, &t1, x); /* 2^223 - 1 */
+ fe448_square(&t0, &t1); /* 2^224 - 2^1 */
+ for (i = 0; i < 222; i++)
+ {
+ fe448_square(&t0, &t0);
+ } /* 2^446 - 2^223 */
+ fe448_mul(&t0, &t2, &t0); /* 2^446 - 2^222 - 1 */
+ fe448_square(&t0, &t0); /* 2^447 - 2^223 - 2 */
+ fe448_square(&t0, &t0); /* 2^448 - 2^224 - 4 */
+ fe448_mul(r, &t0, x); /* 2^448 - 2^224 - 3 */
+}
+
+/* pow(2**446-2**222-1) */
+void fe448_pow446(fe448 *r, const fe448 *x)
+{
+}
generated by cgit (git 2.46.0) at 2026-10-12 00:58:48 +0000