From 3b411ebbfc749f9f12b0eb739cb5ba3ec052197e Mon Sep 17 00:00:00 2001
From: Denys Vlasenko <vda.linux@googlemail.com>
Date: Tue, 5 Oct 2021 20:00:50 +0200
Subject: tls: replace "26-bit" P256 code with 32-bit one.

function                                             old     new   delta
sp_256_ecc_mulmod_8                                    -    1171   +1171
sp_256_mod_mul_norm_8                                  -     834    +834
sp_256_proj_point_dbl_8                                -     374    +374
sp_256_mont_reduce_8                                   -     268    +268
sp_256_mont_mul_8                                      -     151    +151
sp_256_sub_8                                           -      76     +76
sp_256_add_8                                           -      76     +76
sp_256_cmp_8                                           -      38     +38
static.sp_256_mont_dbl_8                               -      31     +31
static.sp_256_mont_sub_8                               -      29     +29
sp_256_to_bin_8                                        -      28     +28
sp_256_point_from_bin2x32                             50      73     +23
sp_256_mont_sqr_8                                      -       7      +7
sp_256_mont_sqr_10                                     7       -      -7
p256_mod                                              40      32      -8
curve_P256_compute_pubkey_and_premaster              186     167     -19
sp_256_sub_10                                         22       -     -22
sp_256_add_10                                         22       -     -22
sp_256_cmp_10                                         24       -     -24
sp_256_norm_10                                        31       -     -31
static.sp_256_mont_sub_10                             49       -     -49
static.sp_256_mont_dbl_10                             52       -     -52
static.sp_256_mul_add_10                              82       -     -82
sp_256_from_bin_10                                   119       -    -119
sp_256_to_bin_10                                     120       -    -120
sp_256_mont_reduce_10                                178       -    -178
sp_256_mont_mul_10                                   214       -    -214
sp_256_proj_point_dbl_10                             451       -    -451
sp_256_ecc_mulmod_10                                1216       -   -1216
sp_256_mod_mul_norm_10                              1305       -   -1305
------------------------------------------------------------------------------
(add/remove: 12/15 grow/shrink: 1/2 up/down: 3106/-3919)     Total: -813 bytes

Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
---
 networking/tls.c        |   15 +-
 networking/tls_sp_c32.c | 1071 +++++++++++++++++++++++++----------------------
 2 files changed, 588 insertions(+), 498 deletions(-)

diff --git a/networking/tls.c b/networking/tls.c
index 4f0e2b6eb..675ef4b3a 100644
--- a/networking/tls.c
+++ b/networking/tls.c
@@ -2334,7 +2334,6 @@ void FAST_FUNC tls_run_copy_loop(tls_state_t *tls, unsigned flags)
 // e.g. at the very beginning of wget_main()
 //
 {
-//kbuild:lib-$(CONFIG_TLS) += tls_sp_c32_new.o
 	uint8_t ecc_pub_key32[2 * 32];
 	uint8_t pubkey2x32[2 * 32];
 	uint8_t premaster32[32];
@@ -2345,14 +2344,14 @@ void FAST_FUNC tls_run_copy_loop(tls_state_t *tls, unsigned flags)
 //	memset(ecc_pub_key32, 0x00, sizeof(ecc_pub_key32));
 //	ecc_pub_key32[18] = 0xab;
 //Random key:
-	tls_get_random(ecc_pub_key32, sizeof(ecc_pub_key32));
+//	tls_get_random(ecc_pub_key32, sizeof(ecc_pub_key32));
 //Biased random (almost all zeros or almost all ones):
-//	srand(time(NULL) ^ getpid());
-//	if (rand() & 1)
-//		memset(ecc_pub_key32, 0x00, sizeof(ecc_pub_key32));
-//	else
-//		memset(ecc_pub_key32, 0xff, sizeof(ecc_pub_key32));
-//	ecc_pub_key32[rand() & 0x3f] = rand();
+	srand(time(NULL) ^ getpid());
+	if (rand() & 1)
+		memset(ecc_pub_key32, 0x00, sizeof(ecc_pub_key32));
+	else
+		memset(ecc_pub_key32, 0xff, sizeof(ecc_pub_key32));
+	ecc_pub_key32[rand() & 0x3f] = rand();
 
 	xmove_fd(xopen("p256.OLD", O_WRONLY | O_CREAT | O_TRUNC), 2);
 	curve_P256_compute_pubkey_and_premaster(
diff --git a/networking/tls_sp_c32.c b/networking/tls_sp_c32.c
index bba22dee3..b99951890 100644
--- a/networking/tls_sp_c32.c
+++ b/networking/tls_sp_c32.c
@@ -9,6 +9,8 @@
 #define FIXED_SECRET      0
 #define FIXED_PEER_PUBKEY 0
 
+#define ALLOW_ASM         1
+
 #if SP_DEBUG
 # define dbg(...) fprintf(stderr, __VA_ARGS__)
 static void dump_hex(const char *fmt, const void *vp, int len)
@@ -24,7 +26,8 @@ static void dump_hex(const char *fmt, const void *vp, int len)
 # define dump_hex(...) ((void)0)
 #endif
 
-typedef int32_t sp_digit;
+typedef uint32_t sp_digit;
+typedef int32_t signed_sp_digit;
 
 /* The code below is taken from parts of
  *  wolfssl-3.15.3/wolfcrypt/src/sp_c32.c
@@ -32,53 +35,23 @@ typedef int32_t sp_digit;
  * Header comment is kept intact:
  */
 
-/* sp.c
- *
- * Copyright (C) 2006-2018 wolfSSL Inc.
- *
- * This file is part of wolfSSL.
- *
- * wolfSSL 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 2 of the License, or
- * (at your option) any later version.
- *
- * wolfSSL 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
- * along with this program; if not, write to the Free Software
- * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1335, USA
- */
-
-/* Implementation by Sean Parkinson. */
-
 typedef struct sp_point {
-	sp_digit x[2 * 10];
-	sp_digit y[2 * 10];
-	sp_digit z[2 * 10];
+	sp_digit x[2 * 8];
+	sp_digit y[2 * 8];
+	sp_digit z[2 * 8];
 	int infinity;
 } sp_point;
 
 /* The modulus (prime) of the curve P256. */
-static const sp_digit p256_mod[10] = {
-	0x3ffffff,0x3ffffff,0x3ffffff,0x003ffff,0x0000000,
-	0x0000000,0x0000000,0x0000400,0x3ff0000,0x03fffff,
+static const sp_digit p256_mod[8] = {
+	0xffffffff,0xffffffff,0xffffffff,0x00000000,
+	0x00000000,0x00000000,0x00000001,0xffffffff,
 };
 
 #define p256_mp_mod ((sp_digit)0x000001)
 
-/* Normalize the values in each word to 26 bits. */
-static void sp_256_norm_10(sp_digit* a)
-{
-	int i;
-	for (i = 0; i < 9; i++) {
-		a[i+1] += a[i] >> 26;
-		a[i] &= 0x3ffffff;
-	}
-}
+/* Normalize the values in each word to 32 bits - NOP */
+#define sp_256_norm_8(a) ((void)0)
 
 /* Write r as big endian to byte array.
  * Fixed length number of bytes written: 32
@@ -86,31 +59,17 @@ static void sp_256_norm_10(sp_digit* a)
  * r  A single precision integer.
  * a  Byte array.
  */
-static void sp_256_to_bin_10(sp_digit* r, uint8_t* a)
-{
-	int i, j, s = 0, b;
-
-	sp_256_norm_10(r);
-
-	j = 256 / 8 - 1;
-	a[j] = 0;
-	for (i = 0; i < 10 && j >= 0; i++) {
-		b = 0;
-		a[j--] |= r[i] << s;
-		b += 8 - s;
-		if (j < 0)
-			break;
-		while (b < 26) {
-			a[j--] = r[i] >> b;
-			b += 8;
-			if (j < 0)
-				break;
-		}
-		s = 8 - (b - 26);
-		if (j >= 0)
-			a[j] = 0;
-		if (s != 0)
-			j++;
+static void sp_256_to_bin_8(const sp_digit* r, uint8_t* a)
+{
+	int i;
+
+	sp_256_norm_8(r);
+
+	r += 8;
+	for (i = 0; i < 8; i++) {
+		r--;
+		move_to_unaligned32(a, SWAP_BE32(*r));
+		a += 4;
 	}
 }
 
@@ -120,67 +79,32 @@ static void sp_256_to_bin_10(sp_digit* r, uint8_t* a)
  * a  Byte array.
  * n  Number of bytes in array to read.
  */
-static void sp_256_from_bin_10(sp_digit* r, const uint8_t* a)
-{
-	int i, j = 0, s = 0;
-
-	r[0] = 0;
-	for (i = 32 - 1; i >= 0; i--) {
-		r[j] |= ((sp_digit)a[i]) << s;
-		if (s >= 18) {
-			r[j] &= 0x3ffffff;
-			s = 26 - s;
-			r[++j] = a[i] >> s;
-			s = 8 - s;
-		}
-		else
-			s += 8;
+static void sp_256_from_bin_8(sp_digit* r, const uint8_t* a)
+{
+	int i;
+
+	r += 8;
+	for (i = 0; i < 8; i++) {
+		sp_digit v;
+		move_from_unaligned32(v, a);
+		*--r = SWAP_BE32(v);
+		a += 4;
 	}
 }
 
 #if SP_DEBUG
-static void dump_256(const char *fmt, const sp_digit* cr)
+static void dump_256(const char *fmt, const sp_digit* r)
 {
-	sp_digit* r = (sp_digit*)cr;
 	uint8_t b32[32];
-	sp_256_to_bin_10(r, b32);
+	sp_256_to_bin_8(r, b32);
 	dump_hex(fmt, b32, 32);
 }
-static void dump_512(const char *fmt, const sp_digit* cr)
+static void dump_512(const char *fmt, const sp_digit* r)
 {
-	sp_digit* r = (sp_digit*)cr;
-	uint8_t a[64];
-	int i, j, s, b;
-
-	/* sp_512_norm_10: */
-	for (i = 0; i < 19; i++) {
-		r[i+1] += r[i] >> 26;
-		r[i] &= 0x3ffffff;
-	}
-	/* sp_512_to_bin_10: */
-	s = 0;
-	j = 512 / 8 - 1;
-	a[j] = 0;
-	for (i = 0; i < 20 && j >= 0; i++) {
-		b = 0;
-		a[j--] |= r[i] << s;
-		b += 8 - s;
-		if (j < 0)
-			break;
-		while (b < 26) {
-			a[j--] = r[i] >> b;
-			b += 8;
-			if (j < 0)
-				break;
-		}
-		s = 8 - (b - 26);
-		if (j >= 0)
-			a[j] = 0;
-		if (s != 0)
-			j++;
-	}
-
-	dump_hex(fmt, a, 64);
+	uint8_t b64[64];
+	sp_256_to_bin_8(r, b64 + 32);
+	sp_256_to_bin_8(r+8, b64);
+	dump_hex(fmt, b64, 64);
 }
 #else
 # define dump_256(...) ((void)0)
@@ -192,8 +116,8 @@ static void sp_256_point_from_bin2x32(sp_point* p, const uint8_t *bin2x32)
 {
 	memset(p, 0, sizeof(*p));
 	/*p->infinity = 0;*/
-	sp_256_from_bin_10(p->x, bin2x32);
-	sp_256_from_bin_10(p->y, bin2x32 + 32);
+	sp_256_from_bin_8(p->x, bin2x32);
+	sp_256_from_bin_8(p->y, bin2x32 + 32);
 	p->z[0] = 1; /* p->z = 1 */
 }
 
@@ -202,170 +126,303 @@ static void sp_256_point_from_bin2x32(sp_point* p, const uint8_t *bin2x32)
  * return -ve, 0 or +ve if a is less than, equal to or greater than b
  * respectively.
  */
-static sp_digit sp_256_cmp_10(const sp_digit* a, const sp_digit* b)
+static signed_sp_digit sp_256_cmp_8(const sp_digit* a, const sp_digit* b)
 {
-	sp_digit r;
 	int i;
-	for (i = 9; i >= 0; i--) {
-		r = a[i] - b[i];
-		if (r != 0)
-			break;
+	for (i = 7; i >= 0; i--) {
+/*		signed_sp_digit r = a[i] - b[i];
+ *		if (r != 0)
+ *			return r;
+ * does not work: think about a[i]=0, b[i]=0xffffffff
+ */
+		if (a[i] == b[i])
+			continue;
+		return (a[i] > b[i]) * 2 - 1;
 	}
-	return r;
+	return 0;
 }
 
 /* Compare two numbers to determine if they are equal.
  *
  * return 1 when equal and 0 otherwise.
  */
-static int sp_256_cmp_equal_10(const sp_digit* a, const sp_digit* b)
+static int sp_256_cmp_equal_8(const sp_digit* a, const sp_digit* b)
 {
-	return sp_256_cmp_10(a, b) == 0;
+	return sp_256_cmp_8(a, b) == 0;
 }
 
-/* Add b to a into r. (r = a + b) */
-static void sp_256_add_10(sp_digit* r, const sp_digit* a, const sp_digit* b)
+/* Add b to a into r. (r = a + b). Return !0 on overflow */
+static int sp_256_add_8(sp_digit* r, const sp_digit* a, const sp_digit* b)
 {
+#if ALLOW_ASM && defined(__GNUC__) && defined(__i386__)
+	sp_digit reg;
+	asm volatile (
+"\n		movl	(%0), %3"
+"\n		addl	(%1), %3"
+"\n		movl	%3, (%2)"
+"\n"
+"\n		movl	1*4(%0), %3"
+"\n		adcl	1*4(%1), %3"
+"\n		movl	%3, 1*4(%2)"
+"\n"
+"\n		movl	2*4(%0), %3"
+"\n		adcl	2*4(%1), %3"
+"\n		movl	%3, 2*4(%2)"
+"\n"
+"\n		movl	3*4(%0), %3"
+"\n		adcl	3*4(%1), %3"
+"\n		movl	%3, 3*4(%2)"
+"\n"
+"\n		movl	4*4(%0), %3"
+"\n		adcl	4*4(%1), %3"
+"\n		movl	%3, 4*4(%2)"
+"\n"
+"\n		movl	5*4(%0), %3"
+"\n		adcl	5*4(%1), %3"
+"\n		movl	%3, 5*4(%2)"
+"\n"
+"\n		movl	6*4(%0), %3"
+"\n		adcl	6*4(%1), %3"
+"\n		movl	%3, 6*4(%2)"
+"\n"
+"\n		movl	7*4(%0), %3"
+"\n		adcl	7*4(%1), %3"
+"\n		movl	%3, 7*4(%2)"
+"\n"
+"\n		sbbl	%3, %3"
+"\n"
+		: "=r" (a), "=r" (b), "=r" (r), "=r" (reg)
+		: "0" (a), "1" (b), "2" (r)
+		: "memory"
+	);
+	return reg;
+#else
 	int i;
-	for (i = 0; i < 10; i++)
-		r[i] = a[i] + b[i];
+	sp_digit carry;
+
+	carry = 0;
+	for (i = 0; i < 8; i++) {
+		sp_digit w, v;
+		w = b[i] + carry;
+		v = a[i];
+		if (w != 0) {
+			v = a[i] + w;
+			carry = (v < a[i]);
+			/* hope compiler detects above as "carry flag set" */
+		}
+		/* else: b + carry == 0, two cases:
+		 * b:ffffffff, carry:1
+		 * b:00000000, carry:0
+		 * in either case, r[i] = a[i] and carry remains unchanged
+		 */
+		r[i] = v;
+	}
+	return carry;
+#endif
 }
 
-/* Sub b from a into r. (r = a - b) */
-static void sp_256_sub_10(sp_digit* r, const sp_digit* a, const sp_digit* b)
+/* Sub b from a into r. (r = a - b). Return !0 on underflow */
+static int sp_256_sub_8(sp_digit* r, const sp_digit* a, const sp_digit* b)
 {
+#if ALLOW_ASM && defined(__GNUC__) && defined(__i386__)
+	sp_digit reg;
+	asm volatile (
+"\n		movl	(%0), %3"
+"\n		subl	(%1), %3"
+"\n		movl	%3, (%2)"
+"\n"
+"\n		movl	1*4(%0), %3"
+"\n		sbbl	1*4(%1), %3"
+"\n		movl	%3, 1*4(%2)"
+"\n"
+"\n		movl	2*4(%0), %3"
+"\n		sbbl	2*4(%1), %3"
+"\n		movl	%3, 2*4(%2)"
+"\n"
+"\n		movl	3*4(%0), %3"
+"\n		sbbl	3*4(%1), %3"
+"\n		movl	%3, 3*4(%2)"
+"\n"
+"\n		movl	4*4(%0), %3"
+"\n		sbbl	4*4(%1), %3"
+"\n		movl	%3, 4*4(%2)"
+"\n"
+"\n		movl	5*4(%0), %3"
+"\n		sbbl	5*4(%1), %3"
+"\n		movl	%3, 5*4(%2)"
+"\n"
+"\n		movl	6*4(%0), %3"
+"\n		sbbl	6*4(%1), %3"
+"\n		movl	%3, 6*4(%2)"
+"\n"
+"\n		movl	7*4(%0), %3"
+"\n		sbbl	7*4(%1), %3"
+"\n		movl	%3, 7*4(%2)"
+"\n"
+"\n		sbbl	%3, %3"
+"\n"
+		: "=r" (a), "=r" (b), "=r" (r), "=r" (reg)
+		: "0" (a), "1" (b), "2" (r)
+		: "memory"
+	);
+	return reg;
+#else
 	int i;
-	for (i = 0; i < 10; i++)
-		r[i] = a[i] - b[i];
+	sp_digit borrow;
+
+	borrow = 0;
+	for (i = 0; i < 8; i++) {
+		sp_digit w, v;
+		w = b[i] + borrow;
+		v = a[i];
+		if (w != 0) {
+			v = a[i] - w;
+			borrow = (v > a[i]);
+			/* hope compiler detects above as "carry flag set" */
+		}
+		/* else: b + borrow == 0, two cases:
+		 * b:ffffffff, borrow:1
+		 * b:00000000, borrow:0
+		 * in either case, r[i] = a[i] and borrow remains unchanged
+		 */
+		r[i] = v;
+	}
+	return borrow;
+#endif
 }
 
 /* Multiply a and b into r. (r = a * b) */
-static void sp_256_mul_10(sp_digit* r, const sp_digit* a, const sp_digit* b)
+static void sp_256_mul_8(sp_digit* r, const sp_digit* a, const sp_digit* b)
 {
+	sp_digit rr[15]; /* in case r coincides with a or b */
 	int i, j, k;
-	int64_t c;
-
-	c = ((int64_t)a[9]) * b[9];
-	r[19] = (sp_digit)(c >> 26);
-	c = (c & 0x3ffffff) << 26;
-	for (k = 17; k >= 0; k--) {
-		for (i = 9; i >= 0; i--) {
-			j = k - i;
-			if (j >= 10)
-				break;
-			if (j < 0)
-				continue;
-			c += ((int64_t)a[i]) * b[j];
+	uint64_t acc;
+
+	acc = 0;
+	for (k = 0; k < 15; k++) {
+		uint32_t acc_hi;
+		i = k - 7;
+		if (i < 0)
+			i = 0;
+		j = k - i;
+		acc_hi = 0;
+		while (i != 8 && i <= k) {
+			uint64_t m = ((uint64_t)a[i]) * b[j];
+			acc += m;
+			if (acc < m)
+				acc_hi++;
+		        j--;
+			i++;
 		}
-		r[k + 2] += c >> 52;
-		r[k + 1] = (c >> 26) & 0x3ffffff;
-		c = (c & 0x3ffffff) << 26;
+		rr[k] = acc;
+		acc = (acc >> 32) | ((uint64_t)acc_hi << 32);
 	}
-	r[0] = (sp_digit)(c >> 26);
+	r[15] = acc;
+	memcpy(r, rr, sizeof(rr));
 }
 
 /* Shift number right one bit. Bottom bit is lost. */
-static void sp_256_rshift1_10(sp_digit* r, sp_digit* a)
+static void sp_256_rshift1_8(sp_digit* r, sp_digit* a, sp_digit carry)
 {
 	int i;
-	for (i = 0; i < 9; i++)
-		r[i] = ((a[i] >> 1) | (a[i + 1] << 25)) & 0x3ffffff;
-	r[9] = a[9] >> 1;
+
+	carry = (!!carry << 31);
+	for (i = 7; i >= 0; i--) {
+		sp_digit c = a[i] << 31;
+		r[i] = (a[i] >> 1) | carry;
+		carry = c;
+	}
 }
 
 /* Divide the number by 2 mod the modulus (prime). (r = a / 2 % m) */
-static void sp_256_div2_10(sp_digit* r, const sp_digit* a, const sp_digit* m)
+static void sp_256_div2_8(sp_digit* r, const sp_digit* a, const sp_digit* m)
 {
+	int carry = 0;
 	if (a[0] & 1)
-		sp_256_add_10(r, a, m);
-	sp_256_norm_10(r);
-	sp_256_rshift1_10(r, r);
+		carry = sp_256_add_8(r, a, m);
+	sp_256_norm_8(r);
+	sp_256_rshift1_8(r, r, carry);
 }
 
 /* Add two Montgomery form numbers (r = a + b % m) */
-static void sp_256_mont_add_10(sp_digit* r, const sp_digit* a, const sp_digit* b,
+static void sp_256_mont_add_8(sp_digit* r, const sp_digit* a, const sp_digit* b,
 		const sp_digit* m)
 {
-	sp_256_add_10(r, a, b);
-	sp_256_norm_10(r);
-	if ((r[9] >> 22) > 0) {
-		sp_256_sub_10(r, r, m);
-		sp_256_norm_10(r);
+	int carry = sp_256_add_8(r, a, b);
+	sp_256_norm_8(r);
+	if (carry) {
+		sp_256_sub_8(r, r, m);
+		sp_256_norm_8(r);
 	}
 }
 
 /* Subtract two Montgomery form numbers (r = a - b % m) */
-static void sp_256_mont_sub_10(sp_digit* r, const sp_digit* a, const sp_digit* b,
+static void sp_256_mont_sub_8(sp_digit* r, const sp_digit* a, const sp_digit* b,
 		const sp_digit* m)
 {
-	sp_256_sub_10(r, a, b);
-	sp_256_norm_10(r);
-	if (r[9] >> 22) {
-		sp_256_add_10(r, r, m);
-		sp_256_norm_10(r);
-		r[9] &= 0x03fffff; /* truncate to 22 bits */
+	int borrow;
+	borrow = sp_256_sub_8(r, a, b);
+	sp_256_norm_8(r);
+	if (borrow) {
+		sp_256_add_8(r, r, m);
+		sp_256_norm_8(r);
 	}
 }
 
 /* Double a Montgomery form number (r = a + a % m) */
-static void sp_256_mont_dbl_10(sp_digit* r, const sp_digit* a, const sp_digit* m)
+static void sp_256_mont_dbl_8(sp_digit* r, const sp_digit* a, const sp_digit* m)
 {
-	sp_256_add_10(r, a, a);
-	sp_256_norm_10(r);
-	if ((r[9] >> 22) > 0)
-		sp_256_sub_10(r, r, m);
-	sp_256_norm_10(r);
+	int carry = sp_256_add_8(r, a, a);
+	sp_256_norm_8(r);
+	if (carry)
+		sp_256_sub_8(r, r, m);
+	sp_256_norm_8(r);
 }
 
 /* Triple a Montgomery form number (r = a + a + a % m) */
-static void sp_256_mont_tpl_10(sp_digit* r, const sp_digit* a, const sp_digit* m)
+static void sp_256_mont_tpl_8(sp_digit* r, const sp_digit* a, const sp_digit* m)
 {
-	sp_256_add_10(r, a, a);
-	sp_256_norm_10(r);
-	if ((r[9] >> 22) > 0) {
-		sp_256_sub_10(r, r, m);
-		sp_256_norm_10(r);
+	int carry = sp_256_add_8(r, a, a);
+	sp_256_norm_8(r);
+	if (carry) {
+		sp_256_sub_8(r, r, m);
+		sp_256_norm_8(r);
 	}
-	sp_256_add_10(r, r, a);
-	sp_256_norm_10(r);
-	if ((r[9] >> 22) > 0) {
-		sp_256_sub_10(r, r, m);
-		sp_256_norm_10(r);
+	carry = sp_256_add_8(r, r, a);
+	sp_256_norm_8(r);
+	if (carry) {
+		sp_256_sub_8(r, r, m);
+		sp_256_norm_8(r);
 	}
-	r[9] &= 0x03fffff; /* truncate to 22 bits */
 }
 
 /* Shift the result in the high 256 bits down to the bottom. */
-static void sp_256_mont_shift_10(sp_digit* r, const sp_digit* a)
+static void sp_256_mont_shift_8(sp_digit* r, const sp_digit* a)
 {
 	int i;
-	sp_digit n, s;
-
-	s = a[10];
-	n = a[9] >> 22;
-	for (i = 0; i < 9; i++) {
-		n += (s & 0x3ffffff) << 4;
-		r[i] = n & 0x3ffffff;
-		n >>= 26;
-		s = a[11 + i] + (s >> 26);
+
+	for (i = 0; i < 8; i++) {
+		r[i] = a[i+8];
+		r[i+8] = 0;
 	}
-	n += s << 4;
-	r[9] = n;
-	memset(&r[10], 0, sizeof(*r) * 10);
 }
 
 /* Mul a by scalar b and add into r. (r += a * b) */
-static void sp_256_mul_add_10(sp_digit* r, const sp_digit* a, sp_digit b)
+static int sp_256_mul_add_8(sp_digit* r, const sp_digit* a, sp_digit b)
 {
-	int64_t t = 0;
+	uint64_t t = 0;
 	int i;
 
-	for (i = 0; i < 10; i++) {
-		t += ((int64_t)b * a[i]) + r[i];
-		r[i] = t & 0x3ffffff;
-		t >>= 26;
+	for (i = 0; i < 8; i++) {
+		uint32_t t_hi;
+		uint64_t m = ((uint64_t)b * a[i]) + r[i];
+		t += m;
+		t_hi = (t < m);
+		r[i] = (sp_digit)t;
+		t = (t >> 32) | ((uint64_t)t_hi << 32);
 	}
-	r[10] += t;
+	r[8] += (sp_digit)t;
+	return (r[8] < (sp_digit)t); /* 1 if addition overflowed */
 }
 
 /* Reduce the number back to 256 bits using Montgomery reduction.
@@ -374,7 +431,7 @@ static void sp_256_mul_add_10(sp_digit* r, const sp_digit* a, sp_digit b)
  * m   The single precision number representing the modulus.
  * mp  The digit representing the negative inverse of m mod 2^n.
  */
-static void sp_256_mont_reduce_10(sp_digit* a /*, const sp_digit* m, sp_digit mp*/)
+static void sp_256_mont_reduce_8(sp_digit* a/*, const sp_digit* m, sp_digit mp*/)
 {
 	const sp_digit* m = p256_mod;
 	sp_digit mp = p256_mp_mod;
@@ -383,33 +440,144 @@ static void sp_256_mont_reduce_10(sp_digit* a /*, const sp_digit* m, sp_digit mp
 	sp_digit mu;
 
 	if (mp != 1) {
-		for (i = 0; i < 9; i++) {
-			mu = (a[i] * mp) & 0x3ffffff;
-			sp_256_mul_add_10(a+i, m, mu);
-			a[i+1] += a[i] >> 26;
+		int too_wide;
+		for (i = 0; i < 7; i++) {
+			mu = (sp_digit)(a[i] * mp);
+			if (sp_256_mul_add_8(a+i, m, mu))
+				(a+i)[9]++;
 		}
-		mu = (a[i] * mp) & 0x03fffff;
-		sp_256_mul_add_10(a+i, m, mu);
-		a[i+1] += a[i] >> 26;
-		a[i] &= 0x3ffffff;
+		mu = (sp_digit)(a[7] * mp);
+		too_wide = sp_256_mul_add_8(a+7, m, mu);
+		sp_256_mont_shift_8(a, a);
+		if (too_wide)
+			sp_256_sub_8(a, a, m);
+		sp_256_norm_8(a);
 	}
 	else { /* Same code for explicit mp == 1 (which is always the case for P256) */
-		for (i = 0; i < 9; i++) {
-			mu = a[i] & 0x3ffffff;
-			sp_256_mul_add_10(a+i, m, mu);
-			a[i+1] += a[i] >> 26;
+		sp_digit word16th = 0;
+		for (i = 0; i < 8; i++) {
+			mu = a[i];
+//m = ffffffff 00000001 00000000 00000000 00000000 ffffffff ffffffff ffffffff
+			if (sp_256_mul_add_8(a+i, m, mu)) {
+				int j = i + 8;
+ inc_next_word:
+				if (++j > 15) { /* a[16] array has no more words? */
+					word16th++;
+					continue;
+				}
+				if (++a[j] == 0) /* did this overflow too? */
+					goto inc_next_word;
+			}
 		}
-		mu = a[i] & 0x03fffff;
-		sp_256_mul_add_10(a+i, m, mu);
-		a[i+1] += a[i] >> 26;
-		a[i] &= 0x3ffffff;
+		sp_256_mont_shift_8(a, a);
+		if (word16th != 0)
+			sp_256_sub_8(a, a, m);
+		sp_256_norm_8(a);
 	}
-
-	sp_256_mont_shift_10(a, a);
-	if ((a[9] >> 22) > 0)
-		sp_256_sub_10(a, a, m);
-	sp_256_norm_10(a);
 }
+#if 0
+//TODO: arm32 asm (also adapt for x86?)
+static void sp_256_mont_reduce_8(sp_digit* a, sp_digit* m, sp_digit mp)
+{
+	sp_digit ca = 0;
+
+	asm volatile (
+	# i = 0
+	mov	r12, #0                 #  i = 0
+	ldr	r10, [%[a], #0]         #  r10 = a[0]
+	ldr	r14, [%[a], #4]         #  r14 = a[1]
+1:
+	# mu = a[i] * mp                #
+	mul	r8, %[mp], r10          # mu = a[i] * mp
+	# a[i+0] += m[0] * mu           #
+	ldr	r7, [%[m], #0]          # a[i+0] += m[0] * mu
+	ldr	r9, [%[a], #0]          #
+	umull	r6, r7, r8, r7          #  r7:r6 = mu * m[0]
+	adds	r10, r10, r6            #  r5:r10 += r7:r6
+	adc	r5, r7, #0              #
+	# a[i+1] += m[1] * mu           #
+	ldr	r7, [%[m], #4]          # a[i+1] += m[1] * mu
+	ldr	r9, [%[a], #4]          #
+	umull	r6, r7, r8, r7          #  r7:r6 = mu * m[1]
+	adds	r10, r14, r6            #  r4:r10 = r7:r14 + r7:r6
+	adc	r4, r7, #0              #
+	adds	r10, r10, r5            #  r4:r10 += r5
+	adc	r4, r4, #0              #
+	# a[i+2] += m[2] * mu           #
+	ldr	r7, [%[m], #8]          # a[i+2] += m[2] * mu
+	ldr	r14, [%[a], #8]         #
+	umull	r6, r7, r8, r7          #
+	adds	r14, r14, r6            #
+	adc	r5, r7, #0              #
+	adds	r14, r14, r4            #
+	adc	r5, r5, #0              #
+	# a[i+3] += m[3] * mu           #
+	ldr	r7, [%[m], #12]         # a[i+3] += m[3] * mu
+	ldr	r9, [%[a], #12]         #
+	umull	r6, r7, r8, r7          #
+	adds	r9, r9, r6              #
+	adc	r4, r7, #0              #
+	adds	r9, r9, r5              #
+	str	r9, [%[a], #12]         #  a[3] = r9
+	adc	r4, r4, #0              #
+	# a[i+4] += m[4] * mu           #
+	ldr	r7, [%[m], #16]         # a[i+4] += m[4] * mu
+	ldr	r9, [%[a], #16]         #
+	umull	r6, r7, r8, r7          #
+	adds	r9, r9, r6              #
+	adc	r5, r7, #0              #
+	adds	r9, r9, r4              #
+	str	r9, [%[a], #16]         #  a[4] = r9
+	adc	r5, r5, #0              #
+	# a[i+5] += m[5] * mu           #
+	ldr	r7, [%[m], #20]         # a[i+5] += m[5] * mu
+	ldr	r9, [%[a], #20]         #
+	umull	r6, r7, r8, r7          #
+	adds	r9, r9, r6              #
+	adc	r4, r7, #0              #
+	adds	r9, r9, r5              #
+	str	r9, [%[a], #20]         #  a[5] = r9
+	adc	r4, r4, #0              #
+	# a[i+6] += m[6] * mu           #
+	ldr	r7, [%[m], #24]         # a[i+6] += m[6] * mu
+	ldr	r9, [%[a], #24]         #
+	umull	r6, r7, r8, r7          #
+	adds	r9, r9, r6              #
+	adc	r5, r7, #0              #
+	adds	r9, r9, r4              #
+	str	r9, [%[a], #24]         #  a[6] = r9
+	adc	r5, r5, #0              #
+	# a[i+7] += m[7] * mu           #
+	ldr	r7, [%[m], #28]         # a[i+7] += m[7] * mu
+	ldr	r9, [%[a], #28]         #
+	umull	r6, r7, r8, r7          #
+	adds	r5, r5, r6              #
+	adcs	r7, r7, %[ca]           #
+	mov	%[ca], #0               #
+	adc	%[ca], %[ca], %[ca]     #  ca = CF
+	adds	r9, r9, r5              #
+	str	r9, [%[a], #28]         #  a[7] = r9
+	ldr	r9, [%[a], #32]         #  r9 = a[8]
+	adcs	r9, r9, r7              #
+	str	r9, [%[a], #32]         #  a[8] = r9
+	adc	%[ca], %[ca], #0        #  ca += CF
+	# i += 1                        # i++
+	add	%[a], %[a], #4          #  a++
+	add	r12, r12, #4            #  i += 4
+	cmp	r12, #32                #  if (i < 32)
+	blt	1b                      #   goto 1
+
+	str	r10, [%[a], #0]         #  a[0] = r10
+	str	r14, [%[a], #4]         #  a[1] = r14
+	: [ca] "+r" (ca), [a] "+r" (a)
+	: [m] "r" (m), [mp] "r" (mp)
+	: "memory", "r4", "r5", "r6", "r7", "r8", "r9", "r10", "r14", "r12"
+	);
+
+	if (ca)
+		a -= m;
+}
+#endif
 
 /* Multiply two Montogmery form numbers mod the modulus (prime).
  * (r = a * b mod m)
@@ -420,14 +588,13 @@ static void sp_256_mont_reduce_10(sp_digit* a /*, const sp_digit* m, sp_digit mp
  * m   Modulus (prime).
  * mp  Montogmery mulitplier.
  */
-static void sp_256_mont_mul_10(sp_digit* r, const sp_digit* a, const sp_digit* b
+static void sp_256_mont_mul_8(sp_digit* r, const sp_digit* a, const sp_digit* b
 		/*, const sp_digit* m, sp_digit mp*/)
 {
 	//const sp_digit* m = p256_mod;
 	//sp_digit mp = p256_mp_mod;
-
-	sp_256_mul_10(r, a, b);
-	sp_256_mont_reduce_10(r /*, m, mp*/);
+	sp_256_mul_8(r, a, b);
+	sp_256_mont_reduce_8(r /*, m, mp*/);
 }
 
 /* Square the Montgomery form number. (r = a * a mod m)
@@ -437,13 +604,12 @@ static void sp_256_mont_mul_10(sp_digit* r, const sp_digit* a, const sp_digit* b
  * m   Modulus (prime).
  * mp  Montogmery mulitplier.
  */
-static void sp_256_mont_sqr_10(sp_digit* r, const sp_digit* a
+static void sp_256_mont_sqr_8(sp_digit* r, const sp_digit* a
 		/*, const sp_digit* m, sp_digit mp*/)
 {
 	//const sp_digit* m = p256_mod;
 	//sp_digit mp = p256_mp_mod;
-
-	sp_256_mont_mul_10(r, a, a /*, m, mp*/);
+	sp_256_mont_mul_8(r, a, a /*, m, mp*/);
 }
 
 /* Invert the number, in Montgomery form, modulo the modulus (prime) of the
@@ -464,19 +630,19 @@ static const uint32_t p256_mod_2[8] = {
 //543210987654321098765432109876543210987654321098765432109876543210...09876543210...09876543210
 //111111111111111111111111111111110000000000000000000000000000000100...00000111111...11111111101
 #endif
-static void sp_256_mont_inv_10(sp_digit* r, sp_digit* a)
+static void sp_256_mont_inv_8(sp_digit* r, sp_digit* a)
 {
-	sp_digit t[2*10]; //can be just [10]?
+	sp_digit t[2*8]; //can be just [8]?
 	int i;
 
-	memcpy(t, a, sizeof(sp_digit) * 10);
+	memcpy(t, a, sizeof(sp_digit) * 8);
 	for (i = 254; i >= 0; i--) {
-		sp_256_mont_sqr_10(t, t /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sqr_8(t, t /*, p256_mod, p256_mp_mod*/);
 		/*if (p256_mod_2[i / 32] & ((sp_digit)1 << (i % 32)))*/
 		if (i >= 224 || i == 192 || (i <= 95 && i != 1))
-			sp_256_mont_mul_10(t, t, a /*, p256_mod, p256_mp_mod*/);
+			sp_256_mont_mul_8(t, t, a /*, p256_mod, p256_mp_mod*/);
 	}
-	memcpy(r, t, sizeof(sp_digit) * 10);
+	memcpy(r, t, sizeof(sp_digit) * 8);
 }
 
 /* Multiply a number by Montogmery normalizer mod modulus (prime).
@@ -484,93 +650,29 @@ static void sp_256_mont_inv_10(sp_digit* r, sp_digit* a)
  * r  The resulting Montgomery form number.
  * a  The number to convert.
  */
-static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
+static void sp_256_mod_mul_norm_8(sp_digit* r, const sp_digit* a)
 {
 	int64_t t[8];
-	int64_t o;
-	uint32_t a32;
+	int32_t o;
 
+#define A(n) ((uint64_t)a[n])
 	/*  1  1  0 -1 -1 -1 -1  0 */
+	t[0] = 0 + A(0) + A(1) - A(3) - A(4) - A(5) - A(6);
 	/*  0  1  1  0 -1 -1 -1 -1 */
+	t[1] = 0 + A(1) + A(2) - A(4) - A(5) - A(6) - A(7);
 	/*  0  0  1  1  0 -1 -1 -1 */
+	t[2] = 0 + A(2) + A(3) - A(5) - A(6) - A(7);
 	/* -1 -1  0  2  2  1  0 -1 */
+	t[3] = 0 - A(0) - A(1) + 2 * A(3) + 2 * A(4) + A(5) - A(7);
 	/*  0 -1 -1  0  2  2  1  0 */
+	t[4] = 0 - A(1) - A(2) + 2 * A(4) + 2 * A(5) + A(6);
 	/*  0  0 -1 -1  0  2  2  1 */
+	t[5] = 0 - A(2) - A(3) + 2 * A(5) + 2 * A(6) + A(7);
 	/* -1 -1  0  0  0  1  3  2 */
+	t[6] = 0 - A(0) - A(1) + A(5) + 3 * A(6) + 2 * A(7);
 	/*  1  0 -1 -1 -1 -1  0  3 */
-	// t[] should be calculated from "a" (converted from 26-bit to 32-bit vector a32[8])
-	// according to the above matrix:
-	//t[0] = 0 + a32[0] + a32[1]            - a32[3]   - a32[4]   - a32[5]   - a32[6]             ;
-	//t[1] = 0          + a32[1] + a32[2]              - a32[4]   - a32[5]   - a32[6]   - a32[7]  ;
-	//t[2] = 0                   + a32[2]   + a32[3]              - a32[5]   - a32[6]   - a32[7]  ;
-	//t[3] = 0 - a32[0] - a32[1]            + 2*a32[3] + 2*a32[4] + a32[5]              - a32[7]  ;
-	//t[4] = 0          - a32[1] - a32[2]              + 2*a32[4] + 2*a32[5] + a32[6]             ;
-	//t[5] = 0                   - a32[2]   - a32[3]              + 2*a32[5] + 2*a32[6] + a32[7]  ;
-	//t[6] = 0 - a32[0] - a32[1]                                  + a32[5]   + 3*a32[6] + 2*a32[7];
-	//t[7] = 0 + a32[0]          - a32[2]   - a32[3]   - a32[4]   - a32[5]              + 3*a32[7];
-	// We can do it "piecemeal" after each a32[i] is known, no need to store entire a32[8] vector:
-
-#define A32 (int64_t)a32
-	a32 = a[0] | (a[1] << 26);
-	t[0] = 0 + A32;
-	t[3] = 0 - A32;
-	t[6] = 0 - A32;
-	t[7] = 0 + A32;
-
-	a32 = (a[1] >> 6) | (a[2] << 20);
-	t[0] += A32    ;
-	t[1]  = 0 + A32;
-	t[3] -= A32    ;
-	t[4]  = 0 - A32;
-	t[6] -= A32    ;
-
-	a32 = (a[2] >> 12) | (a[3] << 14);
-	t[1] += A32    ;
-	t[2]  = 0 + A32;
-	t[4] -= A32    ;
-	t[5]  = 0 - A32;
-	t[7] -= A32    ;
-
-	a32 = (a[3] >> 18) | (a[4] << 8);
-	t[0] -= A32  ;
-	t[2] += A32  ;
-	t[3] += 2*A32;
-	t[5] -= A32  ;
-	t[7] -= A32  ;
-
-	a32 = (a[4] >> 24) | (a[5] << 2) | (a[6] << 28);
-	t[0] -= A32  ;
-	t[1] -= A32  ;
-	t[3] += 2*A32;
-	t[4] += 2*A32;
-	t[7] -= A32  ;
-
-	a32 = (a[6] >> 4) | (a[7] << 22);
-	t[0] -= A32  ;
-	t[1] -= A32  ;
-	t[2] -= A32  ;
-	t[3] += A32  ;
-	t[4] += 2*A32;
-	t[5] += 2*A32;
-	t[6] += A32  ;
-	t[7] -= A32  ;
-
-	a32 = (a[7] >> 10) | (a[8] << 16);
-	t[0] -= A32  ;
-	t[1] -= A32  ;
-	t[2] -= A32  ;
-	t[4] += A32  ;
-	t[5] += 2*A32;
-	t[6] += 3*A32;
-
-	a32 = (a[8] >> 16) | (a[9] << 10);
-	t[1] -= A32  ;
-	t[2] -= A32  ;
-	t[3] -= A32  ;
-	t[5] += A32  ;
-	t[6] += 2*A32;
-	t[7] += 3*A32;
-#undef A32
+	t[7] = 0 + A(0) - A(2) - A(3) - A(4) - A(5) + 3 * A(7);
+#undef A
 
 	t[1] += t[0] >> 32; t[0] &= 0xffffffff;
 	t[2] += t[1] >> 32; t[1] &= 0xffffffff;
@@ -579,29 +681,27 @@ static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
 	t[5] += t[4] >> 32; t[4] &= 0xffffffff;
 	t[6] += t[5] >> 32; t[5] &= 0xffffffff;
 	t[7] += t[6] >> 32; t[6] &= 0xffffffff;
-	o     = t[7] >> 32; t[7] &= 0xffffffff;
+	o     = t[7] >> 32; //t[7] &= 0xffffffff;
 	t[0] += o;
 	t[3] -= o;
 	t[6] -= o;
 	t[7] += o;
-	t[1] += t[0] >> 32; //t[0] &= 0xffffffff;
-	t[2] += t[1] >> 32; //t[1] &= 0xffffffff;
-	t[3] += t[2] >> 32; //t[2] &= 0xffffffff;
-	t[4] += t[3] >> 32; //t[3] &= 0xffffffff;
-	t[5] += t[4] >> 32; //t[4] &= 0xffffffff;
-	t[6] += t[5] >> 32; //t[5] &= 0xffffffff;
-	t[7] += t[6] >> 32; //t[6] &= 0xffffffff; - (uint32_t)t[i] casts below accomplish masking
-
-	r[0] = 0x3ffffff & ((sp_digit)((uint32_t)t[0]));
-	r[1] = 0x3ffffff & ((sp_digit)((uint32_t)t[0] >> 26) | ((sp_digit)t[1] <<  6));
-	r[2] = 0x3ffffff & ((sp_digit)((uint32_t)t[1] >> 20) | ((sp_digit)t[2] << 12));
-	r[3] = 0x3ffffff & ((sp_digit)((uint32_t)t[2] >> 14) | ((sp_digit)t[3] << 18));
-	r[4] = 0x3ffffff & ((sp_digit)((uint32_t)t[3] >>  8) | ((sp_digit)t[4] << 24));
-	r[5] = 0x3ffffff & ((sp_digit)((uint32_t)t[4] >>  2));
-	r[6] = 0x3ffffff & ((sp_digit)((uint32_t)t[4] >> 28) | ((sp_digit)t[5] <<  4));
-	r[7] = 0x3ffffff & ((sp_digit)((uint32_t)t[5] >> 22) | ((sp_digit)t[6] << 10));
-	r[8] = 0x3ffffff & ((sp_digit)((uint32_t)t[6] >> 16) | ((sp_digit)t[7] << 16));
-	r[9] =             ((sp_digit)((uint32_t)t[7] >> 10));
+	r[0] = (sp_digit)t[0];
+	t[1] += t[0] >> 32;
+	r[1] = (sp_digit)t[1];
+	t[2] += t[1] >> 32;
+	r[2] = (sp_digit)t[2];
+	t[3] += t[2] >> 32;
+	r[3] = (sp_digit)t[3];
+	t[4] += t[3] >> 32;
+	r[4] = (sp_digit)t[4];
+	t[5] += t[4] >> 32;
+	r[5] = (sp_digit)t[5];
+	t[6] += t[5] >> 32;
+	r[6] = (sp_digit)t[6];
+//	t[7] += t[6] >> 32;
+//	r[7] = (sp_digit)t[7];
+	r[7] = (sp_digit)t[7] + (sp_digit)(t[6] >> 32);
 }
 
 /* Map the Montgomery form projective co-ordinate point to an affine point.
@@ -609,33 +709,33 @@ static void sp_256_mod_mul_norm_10(sp_digit* r, const sp_digit* a)
  * r  Resulting affine co-ordinate point.
  * p  Montgomery form projective co-ordinate point.
  */
-static void sp_256_map_10(sp_point* r, sp_point* p)
+static void sp_256_map_8(sp_point* r, sp_point* p)
 {
-	sp_digit t1[2*10];
-	sp_digit t2[2*10];
+	sp_digit t1[2*8];
+	sp_digit t2[2*8];
 
-	sp_256_mont_inv_10(t1, p->z);
+	sp_256_mont_inv_8(t1, p->z);
 
-	sp_256_mont_sqr_10(t2, t1 /*, p256_mod, p256_mp_mod*/);
-	sp_256_mont_mul_10(t1, t2, t1 /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_sqr_8(t2, t1 /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(t1, t2, t1 /*, p256_mod, p256_mp_mod*/);
 
 	/* x /= z^2 */
-	sp_256_mont_mul_10(r->x, p->x, t2 /*, p256_mod, p256_mp_mod*/);
-	memset(r->x + 10, 0, sizeof(r->x) / 2);
-	sp_256_mont_reduce_10(r->x /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->x, p->x, t2 /*, p256_mod, p256_mp_mod*/);
+	memset(r->x + 8, 0, sizeof(r->x) / 2);
+	sp_256_mont_reduce_8(r->x /*, p256_mod, p256_mp_mod*/);
 	/* Reduce x to less than modulus */
-	if (sp_256_cmp_10(r->x, p256_mod) >= 0)
-		sp_256_sub_10(r->x, r->x, p256_mod);
-	sp_256_norm_10(r->x);
+	if (sp_256_cmp_8(r->x, p256_mod) >= 0)
+		sp_256_sub_8(r->x, r->x, p256_mod);
+	sp_256_norm_8(r->x);
 
 	/* y /= z^3 */
-	sp_256_mont_mul_10(r->y, p->y, t1 /*, p256_mod, p256_mp_mod*/);
-	memset(r->y + 10, 0, sizeof(r->y) / 2);
-	sp_256_mont_reduce_10(r->y /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->y, p->y, t1 /*, p256_mod, p256_mp_mod*/);
+	memset(r->y + 8, 0, sizeof(r->y) / 2);
+	sp_256_mont_reduce_8(r->y /*, p256_mod, p256_mp_mod*/);
 	/* Reduce y to less than modulus */
-	if (sp_256_cmp_10(r->y, p256_mod) >= 0)
-		sp_256_sub_10(r->y, r->y, p256_mod);
-	sp_256_norm_10(r->y);
+	if (sp_256_cmp_8(r->y, p256_mod) >= 0)
+		sp_256_sub_8(r->y, r->y, p256_mod);
+	sp_256_norm_8(r->y);
 
 	memset(r->z, 0, sizeof(r->z));
 	r->z[0] = 1;
@@ -646,16 +746,16 @@ static void sp_256_map_10(sp_point* r, sp_point* p)
  * r  Result of doubling point.
  * p  Point to double.
  */
-static void sp_256_proj_point_dbl_10(sp_point* r, sp_point* p)
+static void sp_256_proj_point_dbl_8(sp_point* r, sp_point* p)
 {
-	sp_digit t1[2*10];
-	sp_digit t2[2*10];
+	sp_digit t1[2*8];
+	sp_digit t2[2*8];
 
 	/* Put point to double into result */
 	if (r != p)
 		*r = *p; /* struct copy */
 
-	if (r->infinity) /* If infinity, don't double */
+	if (r->infinity)
 		return;
 
 	if (SP_DEBUG) {
@@ -666,41 +766,42 @@ static void sp_256_proj_point_dbl_10(sp_point* r, sp_point* p)
 	}
 
 	/* T1 = Z * Z */
-	sp_256_mont_sqr_10(t1, r->z /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_sqr_8(t1, r->z /*, p256_mod, p256_mp_mod*/);
 	/* Z = Y * Z */
-	sp_256_mont_mul_10(r->z, r->y, r->z /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->z, r->y, r->z /*, p256_mod, p256_mp_mod*/);
 	/* Z = 2Z */
-	sp_256_mont_dbl_10(r->z, r->z, p256_mod);
+	sp_256_mont_dbl_8(r->z, r->z, p256_mod);
 	/* T2 = X - T1 */
-	sp_256_mont_sub_10(t2, r->x, t1, p256_mod);
+	sp_256_mont_sub_8(t2, r->x, t1, p256_mod);
 	/* T1 = X + T1 */
-	sp_256_mont_add_10(t1, r->x, t1, p256_mod);
+	sp_256_mont_add_8(t1, r->x, t1, p256_mod);
 	/* T2 = T1 * T2 */
-	sp_256_mont_mul_10(t2, t1, t2 /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(t2, t1, t2 /*, p256_mod, p256_mp_mod*/);
 	/* T1 = 3T2 */
-	sp_256_mont_tpl_10(t1, t2, p256_mod);
+	sp_256_mont_tpl_8(t1, t2, p256_mod);
 	/* Y = 2Y */
-	sp_256_mont_dbl_10(r->y, r->y, p256_mod);
+	sp_256_mont_dbl_8(r->y, r->y, p256_mod);
 	/* Y = Y * Y */
-	sp_256_mont_sqr_10(r->y, r->y /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_sqr_8(r->y, r->y /*, p256_mod, p256_mp_mod*/);
 	/* T2 = Y * Y */
-	sp_256_mont_sqr_10(t2, r->y /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_sqr_8(t2, r->y /*, p256_mod, p256_mp_mod*/);
 	/* T2 = T2/2 */
-	sp_256_div2_10(t2, t2, p256_mod);
+	sp_256_div2_8(t2, t2, p256_mod);
 	/* Y = Y * X */
-	sp_256_mont_mul_10(r->y, r->y, r->x /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->y, r->y, r->x /*, p256_mod, p256_mp_mod*/);
 	/* X = T1 * T1 */
-	sp_256_mont_mul_10(r->x, t1, t1 /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->x, t1, t1 /*, p256_mod, p256_mp_mod*/);
 	/* X = X - Y */
-	sp_256_mont_sub_10(r->x, r->x, r->y, p256_mod);
+	sp_256_mont_sub_8(r->x, r->x, r->y, p256_mod);
 	/* X = X - Y */
-	sp_256_mont_sub_10(r->x, r->x, r->y, p256_mod);
+	sp_256_mont_sub_8(r->x, r->x, r->y, p256_mod);
 	/* Y = Y - X */
-	sp_256_mont_sub_10(r->y, r->y, r->x, p256_mod);
+	sp_256_mont_sub_8(r->y, r->y, r->x, p256_mod);
 	/* Y = Y * T1 */
-	sp_256_mont_mul_10(r->y, r->y, t1 /*, p256_mod, p256_mp_mod*/);
+	sp_256_mont_mul_8(r->y, r->y, t1 /*, p256_mod, p256_mp_mod*/);
 	/* Y = Y - T2 */
-	sp_256_mont_sub_10(r->y, r->y, t2, p256_mod);
+	sp_256_mont_sub_8(r->y, r->y, t2, p256_mod);
+	dump_512("y2 %s\n", r->y);
 }
 
 /* Add two Montgomery form projective points.
@@ -709,13 +810,13 @@ static void sp_256_proj_point_dbl_10(sp_point* r, sp_point* p)
  * p  Frist point to add.
  * q  Second point to add.
  */
-static void sp_256_proj_point_add_10(sp_point* r, sp_point* p, sp_point* q)
+static void sp_256_proj_point_add_8(sp_point* r, sp_point* p, sp_point* q)
 {
-	sp_digit t1[2*10];
-	sp_digit t2[2*10];
-	sp_digit t3[2*10];
-	sp_digit t4[2*10];
-	sp_digit t5[2*10];
+	sp_digit t1[2*8];
+	sp_digit t2[2*8];
+	sp_digit t3[2*8];
+	sp_digit t4[2*8];
+	sp_digit t5[2*8];
 
 	/* Ensure only the first point is the same as the result. */
 	if (q == r) {
@@ -725,13 +826,13 @@ static void sp_256_proj_point_add_10(sp_point* r, sp_point* p, sp_point* q)
 	}
 
 	/* Check double */
-	sp_256_sub_10(t1, p256_mod, q->y);
-	sp_256_norm_10(t1);
-	if (sp_256_cmp_equal_10(p->x, q->x)
-	 && sp_256_cmp_equal_10(p->z, q->z)
-	 && (sp_256_cmp_equal_10(p->y, q->y) || sp_256_cmp_equal_10(p->y, t1))
+	sp_256_sub_8(t1, p256_mod, q->y);
+	sp_256_norm_8(t1);
+	if (sp_256_cmp_equal_8(p->x, q->x)
+	 && sp_256_cmp_equal_8(p->z, q->z)
+	 && (sp_256_cmp_equal_8(p->y, q->y) || sp_256_cmp_equal_8(p->y, t1))
 	) {
-		sp_256_proj_point_dbl_10(r, p);
+		sp_256_proj_point_dbl_8(r, p);
 	}
 	else {
 		sp_point tp;
@@ -746,37 +847,37 @@ static void sp_256_proj_point_add_10(sp_point* r, sp_point* p, sp_point* q)
 		*r = p->infinity ? *q : *p; /* struct copy */
 
 		/* U1 = X1*Z2^2 */
-		sp_256_mont_sqr_10(t1, q->z /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t3, t1, q->z /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t1, t1, v->x /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sqr_8(t1, q->z /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t3, t1, q->z /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t1, t1, v->x /*, p256_mod, p256_mp_mod*/);
 		/* U2 = X2*Z1^2 */
-		sp_256_mont_sqr_10(t2, v->z /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t4, t2, v->z /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t2, t2, q->x /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sqr_8(t2, v->z /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t4, t2, v->z /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t2, t2, q->x /*, p256_mod, p256_mp_mod*/);
 		/* S1 = Y1*Z2^3 */
-		sp_256_mont_mul_10(t3, t3, v->y /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t3, t3, v->y /*, p256_mod, p256_mp_mod*/);
 		/* S2 = Y2*Z1^3 */
-		sp_256_mont_mul_10(t4, t4, q->y /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t4, t4, q->y /*, p256_mod, p256_mp_mod*/);
 		/* H = U2 - U1 */
-		sp_256_mont_sub_10(t2, t2, t1, p256_mod);
+		sp_256_mont_sub_8(t2, t2, t1, p256_mod);
 		/* R = S2 - S1 */
-		sp_256_mont_sub_10(t4, t4, t3, p256_mod);
+		sp_256_mont_sub_8(t4, t4, t3, p256_mod);
 		/* Z3 = H*Z1*Z2 */
-		sp_256_mont_mul_10(v->z, v->z, q->z /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(v->z, v->z, t2 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(v->z, v->z, q->z /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(v->z, v->z, t2 /*, p256_mod, p256_mp_mod*/);
 		/* X3 = R^2 - H^3 - 2*U1*H^2 */
-		sp_256_mont_sqr_10(v->x, t4 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_sqr_10(t5, t2 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(v->y, t1, t5 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t5, t5, t2 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_sub_10(v->x, v->x, t5, p256_mod);
-		sp_256_mont_dbl_10(t1, v->y, p256_mod);
-		sp_256_mont_sub_10(v->x, v->x, t1, p256_mod);
+		sp_256_mont_sqr_8(v->x, t4 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sqr_8(t5, t2 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(v->y, t1, t5 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t5, t5, t2 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sub_8(v->x, v->x, t5, p256_mod);
+		sp_256_mont_dbl_8(t1, v->y, p256_mod);
+		sp_256_mont_sub_8(v->x, v->x, t1, p256_mod);
 		/* Y3 = R*(U1*H^2 - X3) - S1*H^3 */
-		sp_256_mont_sub_10(v->y, v->y, v->x, p256_mod);
-		sp_256_mont_mul_10(v->y, v->y, t4 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_mul_10(t5, t5, t3 /*, p256_mod, p256_mp_mod*/);
-		sp_256_mont_sub_10(v->y, v->y, t5, p256_mod);
+		sp_256_mont_sub_8(v->y, v->y, v->x, p256_mod);
+		sp_256_mont_mul_8(v->y, v->y, t4 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_mul_8(t5, t5, t3 /*, p256_mod, p256_mp_mod*/);
+		sp_256_mont_sub_8(v->y, v->y, t5, p256_mod);
 	}
 }
 
@@ -788,12 +889,11 @@ static void sp_256_proj_point_add_10(sp_point* r, sp_point* p, sp_point* q)
  * k     Scalar to multiply by.
  * map   Indicates whether to convert result to affine.
  */
-static void sp_256_ecc_mulmod_10(sp_point* r, const sp_point* g, const sp_digit* k /*, int map*/)
+static void sp_256_ecc_mulmod_8(sp_point* r, const sp_point* g, const sp_digit* k /*, int map*/)
 {
 	enum { map = 1 }; /* we always convert result to affine coordinates */
 	sp_point t[3];
-	sp_digit n;
-	int i;
+	sp_digit n = n; /* for compiler */
 	int c, y;
 
 	memset(t, 0, sizeof(t));
@@ -801,36 +901,44 @@ static void sp_256_ecc_mulmod_10(sp_point* r, const sp_point* g, const sp_digit*
 	/* t[0] = {0, 0, 1} * norm */
 	t[0].infinity = 1;
 	/* t[1] = {g->x, g->y, g->z} * norm */
-	sp_256_mod_mul_norm_10(t[1].x, g->x);
-	sp_256_mod_mul_norm_10(t[1].y, g->y);
-	sp_256_mod_mul_norm_10(t[1].z, g->z);
-	dump_512("t[1].x %s\n", t[1].x);
-	dump_512("t[1].y %s\n", t[1].y);
-	dump_512("t[1].z %s\n", t[1].z);
-
-	i = 9;
-	c = 22;
-	n = k[i--] << (26 - c);
-	for (; ; c--) {
-		if (c == 0) {
-			if (i == -1)
-				break;
+	sp_256_mod_mul_norm_8(t[1].x, g->x);
+	sp_256_mod_mul_norm_8(t[1].y, g->y);
+	sp_256_mod_mul_norm_8(t[1].z, g->z);
 
-			n = k[i--];
-			c = 26;
+	/* For every bit, starting from most significant... */
+	k += 7;
+	c = 256;
+	for (;;) {
+		if ((c & 0x1f) == 0) {
+			if (c == 0)
+				break;
+			n = *k--;
 		}
 
-		y = (n >> 25) & 1;
-		n <<= 1;
-
-		sp_256_proj_point_add_10(&t[y^1], &t[0], &t[1]);
+		y = (n >> 31);
+		dbg("y:%d t[%d] = t[0]+t[1]\n", y, y^1);
+		sp_256_proj_point_add_8(&t[y^1], &t[0], &t[1]);
+		dump_512("t[0].x %s\n", t[0].x);
+		dump_512("t[0].y %s\n", t[0].y);
+		dump_512("t[0].z %s\n", t[0].z);
+		dump_512("t[1].x %s\n", t[1].x);
+		dump_512("t[1].y %s\n", t[1].y);
+		dump_512("t[1].z %s\n", t[1].z);
+		dbg("t[2] = t[%d]\n", y);
 		memcpy(&t[2], &t[y], sizeof(sp_point));
-		sp_256_proj_point_dbl_10(&t[2], &t[2]);
+		dbg("t[2] *= 2\n");
+		sp_256_proj_point_dbl_8(&t[2], &t[2]);
+		dump_512("t[2].x %s\n", t[2].x);
+		dump_512("t[2].y %s\n", t[2].y);
+		dump_512("t[2].z %s\n", t[2].z);
 		memcpy(&t[y], &t[2], sizeof(sp_point));
+
+		n <<= 1;
+		c--;
 	}
 
 	if (map)
-		sp_256_map_10(r, &t[0]);
+		sp_256_map_8(r, &t[0]);
 	else
 		memcpy(r, &t[0], sizeof(sp_point));
 
@@ -844,7 +952,7 @@ static void sp_256_ecc_mulmod_10(sp_point* r, const sp_point* g, const sp_digit*
  * k     Scalar to multiply by.
  * map   Indicates whether to convert result to affine.
  */
-static void sp_256_ecc_mulmod_base_10(sp_point* r, sp_digit* k /*, int map*/)
+static void sp_256_ecc_mulmod_base_8(sp_point* r, sp_digit* k /*, int map*/)
 {
 	/* Since this function is called only once, save space:
 	 * don't have "static const sp_point p256_base = {...}",
@@ -861,7 +969,7 @@ static void sp_256_ecc_mulmod_base_10(sp_point* r, sp_digit* k /*, int map*/)
 
 	sp_256_point_from_bin2x32(&p256_base, p256_base_bin);
 
-	sp_256_ecc_mulmod_10(r, &p256_base, k /*, map*/);
+	sp_256_ecc_mulmod_8(r, &p256_base, k /*, map*/);
 }
 
 /* Multiply the point by the scalar and serialize the X ordinate.
@@ -871,7 +979,7 @@ static void sp_256_ecc_mulmod_base_10(sp_point* r, sp_digit* k /*, int map*/)
  * pub2x32 Point to multiply.
  * out32   Buffer to hold X ordinate.
  */
-static void sp_ecc_secret_gen_256(const sp_digit priv[10], const uint8_t *pub2x32, uint8_t* out32)
+static void sp_ecc_secret_gen_256(const sp_digit priv[8], const uint8_t *pub2x32, uint8_t* out32)
 {
 	sp_point point[1];
 
@@ -885,66 +993,48 @@ static void sp_ecc_secret_gen_256(const sp_digit priv[10], const uint8_t *pub2x3
 	dump_512("point->x %s\n", point->x);
 	dump_512("point->y %s\n", point->y);
 
-	sp_256_ecc_mulmod_10(point, point, priv);
+	sp_256_ecc_mulmod_8(point, point, priv);
 
-	sp_256_to_bin_10(point->x, out32);
+	sp_256_to_bin_8(point->x, out32);
 	dump_hex("out32: %s\n", out32, 32);
 }
 
-/* Generates a scalar that is in the range 1..order-1. */
-#define SIMPLIFY 1
-/* Add 1 to a. (a = a + 1) */
-static void sp_256_add_one_10(sp_digit* a)
-{
-	a[0]++;
-	sp_256_norm_10(a);
-}
-static void sp_256_ecc_gen_k_10(sp_digit k[10])
+/* Generates a random scalar in [1..order-1] range. */
+static void sp_256_ecc_gen_k_8(sp_digit k[8])
 {
-#if !SIMPLIFY
-	/* The order of the curve P256 minus 2. */
-	static const sp_digit p256_order2[10] = {
-		0x063254f,0x272b0bf,0x1e84f3b,0x2b69c5e,0x3bce6fa,
-		0x3ffffff,0x3ffffff,0x00003ff,0x3ff0000,0x03fffff,
-	};
-#endif
-	uint8_t buf[32];
-
-	for (;;) {
-		tls_get_random(buf, sizeof(buf));
+	/* Since 32-bit words are "dense", no need to use
+	 * sp_256_from_bin_8(k, buf) to convert random stream
+	 * to sp_digit array - just store random bits there directly.
+	 */
+	tls_get_random(k, 8 * sizeof(k[0]));
 #if FIXED_SECRET
-		memset(buf, 0x77, sizeof(buf));
+	memset(k, 0x77, 8 * sizeof(k[0]));
 #endif
-		sp_256_from_bin_10(k, buf);
-#if !SIMPLIFY
-		if (sp_256_cmp_10(k, p256_order2) < 0)
-			break;
-#else
-		/* non-loopy version (and not needing p256_order2[]):
-		 * if most-significant word seems that k can be larger
-		 * than p256_order2, fix it up:
-		 */
-		if (k[9] >= 0x03fffff)
-			k[9] = 0x03ffffe;
-		break;
-#endif
-	}
-	sp_256_add_one_10(k);
-#undef SIMPLIFY
+
+// If scalar is too large, try again (pseudo-code)
+//	if (k >= 0xffffffff00000000ffffffffffffffffbce6faada7179e84f3b9cac2fc632551 - 1) // order of P256
+//		goto pick_another_random;
+//	k++; // ensure non-zero
+	/* Simpler alternative, at the cost of not choosing some valid
+	 * random values, and slightly non-uniform distribution */
+	if (k[0] == 0)
+		k[0] = 1;
+	if (k[7] >= 0xffffffff)
+		k[7] = 0xfffffffe;
 }
 
 /* Makes a random EC key pair. */
-static void sp_ecc_make_key_256(sp_digit privkey[10], uint8_t *pubkey)
+static void sp_ecc_make_key_256(sp_digit privkey[8], uint8_t *pubkey)
 {
 	sp_point point[1];
 
-	sp_256_ecc_gen_k_10(privkey);
+	sp_256_ecc_gen_k_8(privkey);
 	dump_256("privkey %s\n", privkey);
-	sp_256_ecc_mulmod_base_10(point, privkey);
+	sp_256_ecc_mulmod_base_8(point, privkey);
 	dump_512("point->x %s\n", point->x);
 	dump_512("point->y %s\n", point->y);
-	sp_256_to_bin_10(point->x, pubkey);
-	sp_256_to_bin_10(point->y, pubkey + 32);
+	sp_256_to_bin_8(point->x, pubkey);
+	sp_256_to_bin_8(point->y, pubkey + 32);
 
 	memset(point, 0, sizeof(point)); //paranoia
 }
@@ -953,8 +1043,9 @@ void FAST_FUNC curve_P256_compute_pubkey_and_premaster(
 		uint8_t *pubkey2x32, uint8_t *premaster32,
 		const uint8_t *peerkey2x32)
 {
-	sp_digit privkey[10];
+	sp_digit privkey[8];
 
+	dump_hex("peerkey2x32: %s\n", peerkey2x32, 64);
 	sp_ecc_make_key_256(privkey, pubkey2x32);
 	dump_hex("pubkey: %s\n", pubkey2x32, 32);
 	dump_hex("        %s\n", pubkey2x32 + 32, 32);
-- 
cgit v1.2.3