CurvasElipticas - Operaciones de generacion de claves, D-H, firma y…

Users » saranieves92 » Code » CurvasElipticas

sara matheu / Mbed 2 deprecated CurvasElipticas

Operaciones de generacion de claves, D-H, firma y validacion.

ecc.cpp@5:4f619b9a7bb2, 2015-02-20 (annotated)

Committer:: saranieves92
Date:: Fri Feb 20 18:37:50 2015 +0000
Revision:: 5:4f619b9a7bb2
Parent:: 1:4875e39abd1e

intento de rsa

Who changed what in which revision?

User	Revision	Line number	New contents of line
saranieves92	1:4875e39abd1e	1	#include "ecc.h"
saranieves92	1:4875e39abd1e	2
saranieves92	1:4875e39abd1e	3	#include <string.h>
saranieves92	1:4875e39abd1e	4
saranieves92	1:4875e39abd1e	5	typedef unsigned int uint;
saranieves92	1:4875e39abd1e	6
saranieves92	1:4875e39abd1e	7	#define Curve_P_1 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFD}
saranieves92	1:4875e39abd1e	8	#define Curve_P_2 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	9	#define Curve_P_3 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	10	#define Curve_P_4 {0xFFFFFFFF, 0x00000000, 0x00000000, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, \
saranieves92	1:4875e39abd1e	11	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	12	#define Curve_P_5 {0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	13
saranieves92	1:4875e39abd1e	14	#define Curve_B_1 {0x2CEE5ED3, 0xD824993C, 0x1079F43D, 0xE87579C1}
saranieves92	1:4875e39abd1e	15	#define Curve_B_2 {0xC146B9B1, 0xFEB8DEEC, 0x72243049, 0x0FA7E9AB, 0xE59C80E7, 0x64210519}
saranieves92	1:4875e39abd1e	16	#define Curve_B_3 {0x27D2604B, 0x3BCE3C3E, 0xCC53B0F6, 0x651D06B0, 0x769886BC, 0xB3EBBD55, 0xAA3A93E7, 0x5AC635D8}
saranieves92	1:4875e39abd1e	17	#define Curve_B_4 {0xD3EC2AEF, 0x2A85C8ED, 0x8A2ED19D, 0xC656398D, 0x5013875A, 0x0314088F, 0xFE814112, 0x181D9C6E, \
saranieves92	1:4875e39abd1e	18	0xE3F82D19, 0x988E056B, 0xE23EE7E4, 0xB3312FA7}
saranieves92	1:4875e39abd1e	19	#define Curve_B_5 {0x00000007, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000, 0x00000000}
saranieves92	1:4875e39abd1e	20
saranieves92	1:4875e39abd1e	21	#define Curve_G_1 { \
saranieves92	1:4875e39abd1e	22	{0xA52C5B86, 0x0C28607C, 0x8B899B2D, 0x161FF752}, \
saranieves92	1:4875e39abd1e	23	{0xDDED7A83, 0xC02DA292, 0x5BAFEB13, 0xCF5AC839}}
saranieves92	1:4875e39abd1e	24
saranieves92	1:4875e39abd1e	25	#define Curve_G_2 { \
saranieves92	1:4875e39abd1e	26	{0x82FF1012, 0xF4FF0AFD, 0x43A18800, 0x7CBF20EB, 0xB03090F6, 0x188DA80E}, \
saranieves92	1:4875e39abd1e	27	{0x1E794811, 0x73F977A1, 0x6B24CDD5, 0x631011ED, 0xFFC8DA78, 0x07192B95}}
saranieves92	1:4875e39abd1e	28
saranieves92	1:4875e39abd1e	29	#define Curve_G_3 { \
saranieves92	1:4875e39abd1e	30	{0xD898C296, 0xF4A13945, 0x2DEB33A0, 0x77037D81, 0x63A440F2, 0xF8BCE6E5, 0xE12C4247, 0x6B17D1F2}, \
saranieves92	1:4875e39abd1e	31	{0x37BF51F5, 0xCBB64068, 0x6B315ECE, 0x2BCE3357, 0x7C0F9E16, 0x8EE7EB4A, 0xFE1A7F9B, 0x4FE342E2}}
saranieves92	1:4875e39abd1e	32
saranieves92	1:4875e39abd1e	33	#define Curve_G_4 { \
saranieves92	1:4875e39abd1e	34	{0x72760AB7, 0x3A545E38, 0xBF55296C, 0x5502F25D, 0x82542A38, 0x59F741E0, 0x8BA79B98, 0x6E1D3B62, \
saranieves92	1:4875e39abd1e	35	0xF320AD74, 0x8EB1C71E, 0xBE8B0537, 0xAA87CA22}, \
saranieves92	1:4875e39abd1e	36	{0x90EA0E5F, 0x7A431D7C, 0x1D7E819D, 0x0A60B1CE, 0xB5F0B8C0, 0xE9DA3113, 0x289A147C, 0xF8F41DBD, \
saranieves92	1:4875e39abd1e	37	0x9292DC29, 0x5D9E98BF, 0x96262C6F, 0x3617DE4A}}
saranieves92	1:4875e39abd1e	38
saranieves92	1:4875e39abd1e	39	#define Curve_G_5 { \
saranieves92	1:4875e39abd1e	40	{0x16F81798, 0x59F2815B, 0x2DCE28D9, 0x029BFCDB, 0xCE870B07, 0x55A06295, 0xF9DCBBAC, 0x79BE667E}, \
saranieves92	1:4875e39abd1e	41	{0xFB10D4B8, 0x9C47D08F, 0xA6855419, 0xFD17B448, 0x0E1108A8, 0x5DA4FBFC, 0x26A3C465, 0x483ADA77}}
saranieves92	1:4875e39abd1e	42
saranieves92	1:4875e39abd1e	43	#define Curve_N_1 {0x9038A115, 0x75A30D1B, 0x00000000, 0xFFFFFFFE}
saranieves92	1:4875e39abd1e	44	#define Curve_N_2 {0xB4D22831, 0x146BC9B1, 0x99DEF836, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	45	#define Curve_N_3 {0xFC632551, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	46	#define Curve_N_4 {0xCCC52973, 0xECEC196A, 0x48B0A77A, 0x581A0DB2, 0xF4372DDF, 0xC7634D81, 0xFFFFFFFF, 0xFFFFFFFF, \
saranieves92	1:4875e39abd1e	47	0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	48	#define Curve_N_5 {0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
saranieves92	1:4875e39abd1e	49
saranieves92	1:4875e39abd1e	50	static uint32_t curve_p[NUM_ECC_DIGITS] = ECC_CONCAT(Curve_P_, ECC_CURVE);
saranieves92	1:4875e39abd1e	51	static uint32_t curve_b[NUM_ECC_DIGITS] = ECC_CONCAT(Curve_B_, ECC_CURVE);
saranieves92	1:4875e39abd1e	52	static EccPoint curve_G = ECC_CONCAT(Curve_G_, ECC_CURVE);
saranieves92	1:4875e39abd1e	53	static uint32_t curve_n[NUM_ECC_DIGITS] = ECC_CONCAT(Curve_N_, ECC_CURVE);
saranieves92	1:4875e39abd1e	54
saranieves92	1:4875e39abd1e	55	static void vli_clear(uint32_t *p_vli)
saranieves92	1:4875e39abd1e	56	{
saranieves92	1:4875e39abd1e	57	uint i;
saranieves92	1:4875e39abd1e	58	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	59	{
saranieves92	1:4875e39abd1e	60	p_vli[i] = 0;
saranieves92	1:4875e39abd1e	61	}
saranieves92	1:4875e39abd1e	62	}
saranieves92	1:4875e39abd1e	63
saranieves92	1:4875e39abd1e	64	/* Returns 1 if p_vli == 0, 0 otherwise. */
saranieves92	1:4875e39abd1e	65	static int vli_isZero(const uint32_t *p_vli)
saranieves92	1:4875e39abd1e	66	{
saranieves92	1:4875e39abd1e	67	uint i;
saranieves92	1:4875e39abd1e	68	for(i = 0; i < NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	69	{
saranieves92	1:4875e39abd1e	70	if(p_vli[i])
saranieves92	1:4875e39abd1e	71	{
saranieves92	1:4875e39abd1e	72	return 0;
saranieves92	1:4875e39abd1e	73	}
saranieves92	1:4875e39abd1e	74	}
saranieves92	1:4875e39abd1e	75	return 1;
saranieves92	1:4875e39abd1e	76	}
saranieves92	1:4875e39abd1e	77
saranieves92	1:4875e39abd1e	78	/* Returns nonzero if bit p_bit of p_vli is set. */
saranieves92	1:4875e39abd1e	79	static uint32_t vli_testBit(const uint32_t *p_vli, const unsigned int p_bit)
saranieves92	1:4875e39abd1e	80	{
saranieves92	1:4875e39abd1e	81	return (p_vli[p_bit/32] & (1 << (p_bit % 32)));
saranieves92	1:4875e39abd1e	82	}
saranieves92	1:4875e39abd1e	83
saranieves92	1:4875e39abd1e	84	/* Counts the number of 32-bit "digits" in p_vli. */
saranieves92	1:4875e39abd1e	85	static uint vli_numDigits(const uint32_t *p_vli)
saranieves92	1:4875e39abd1e	86	{
saranieves92	1:4875e39abd1e	87	int i;
saranieves92	1:4875e39abd1e	88	/* Search from the end until we find a non-zero digit.
saranieves92	1:4875e39abd1e	89	We do it in reverse because we expect that most digits will be nonzero. */
saranieves92	1:4875e39abd1e	90	for(i = NUM_ECC_DIGITS - 1; i >= 0 && p_vli[i] == 0; --i)
saranieves92	1:4875e39abd1e	91	{
saranieves92	1:4875e39abd1e	92	}
saranieves92	1:4875e39abd1e	93
saranieves92	1:4875e39abd1e	94	return (i + 1);
saranieves92	1:4875e39abd1e	95	}
saranieves92	1:4875e39abd1e	96
saranieves92	1:4875e39abd1e	97	/* Counts the number of bits required for p_vli. */
saranieves92	1:4875e39abd1e	98	static uint vli_numBits(const uint32_t *p_vli)
saranieves92	1:4875e39abd1e	99	{
saranieves92	1:4875e39abd1e	100	uint i;
saranieves92	1:4875e39abd1e	101	uint32_t l_digit;
saranieves92	1:4875e39abd1e	102
saranieves92	1:4875e39abd1e	103	uint l_numDigits = vli_numDigits(p_vli);
saranieves92	1:4875e39abd1e	104	if(l_numDigits == 0)
saranieves92	1:4875e39abd1e	105	{
saranieves92	1:4875e39abd1e	106	return 0;
saranieves92	1:4875e39abd1e	107	}
saranieves92	1:4875e39abd1e	108
saranieves92	1:4875e39abd1e	109	l_digit = p_vli[l_numDigits - 1];
saranieves92	1:4875e39abd1e	110	for(i=0; l_digit; ++i)
saranieves92	1:4875e39abd1e	111	{
saranieves92	1:4875e39abd1e	112	l_digit >>= 1;
saranieves92	1:4875e39abd1e	113	}
saranieves92	1:4875e39abd1e	114
saranieves92	1:4875e39abd1e	115	return ((l_numDigits - 1) * 32 + i);
saranieves92	1:4875e39abd1e	116	}
saranieves92	1:4875e39abd1e	117
saranieves92	1:4875e39abd1e	118	/* Sets p_dest = p_src. */
saranieves92	1:4875e39abd1e	119	static void vli_set(uint32_t p_dest, const uint32_t p_src)
saranieves92	1:4875e39abd1e	120	{
saranieves92	1:4875e39abd1e	121	uint i;
saranieves92	1:4875e39abd1e	122	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	123	{
saranieves92	1:4875e39abd1e	124	p_dest[i] = p_src[i];
saranieves92	1:4875e39abd1e	125	}
saranieves92	1:4875e39abd1e	126	}
saranieves92	1:4875e39abd1e	127
saranieves92	1:4875e39abd1e	128	/* Returns sign of p_left - p_right. */
saranieves92	1:4875e39abd1e	129	static int vli_cmp(const uint32_t p_left, const uint32_t p_right)
saranieves92	1:4875e39abd1e	130	{
saranieves92	1:4875e39abd1e	131	int i;
saranieves92	1:4875e39abd1e	132	for(i = NUM_ECC_DIGITS-1; i >= 0; --i)
saranieves92	1:4875e39abd1e	133	{
saranieves92	1:4875e39abd1e	134	if(p_left[i] > p_right[i])
saranieves92	1:4875e39abd1e	135	{
saranieves92	1:4875e39abd1e	136	return 1;
saranieves92	1:4875e39abd1e	137	}
saranieves92	1:4875e39abd1e	138	else if(p_left[i] < p_right[i])
saranieves92	1:4875e39abd1e	139	{
saranieves92	1:4875e39abd1e	140	return -1;
saranieves92	1:4875e39abd1e	141	}
saranieves92	1:4875e39abd1e	142	}
saranieves92	1:4875e39abd1e	143	return 0;
saranieves92	1:4875e39abd1e	144	}
saranieves92	1:4875e39abd1e	145
saranieves92	1:4875e39abd1e	146	/* Computes p_result = p_in << c, returning carry. Can modify in place (if p_result == p_in). 0 < p_shift < 32. */
saranieves92	1:4875e39abd1e	147	static uint32_t vli_lshift(uint32_t p_result, const uint32_t p_in, const unsigned int p_shift)
saranieves92	1:4875e39abd1e	148	{
saranieves92	1:4875e39abd1e	149	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	150	uint i;
saranieves92	1:4875e39abd1e	151	for(i = 0; i < NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	152	{
saranieves92	1:4875e39abd1e	153	uint32_t l_temp = p_in[i];
saranieves92	1:4875e39abd1e	154	p_result[i] = (l_temp << p_shift) \| l_carry;
saranieves92	1:4875e39abd1e	155	l_carry = l_temp >> (32 - p_shift);
saranieves92	1:4875e39abd1e	156	}
saranieves92	1:4875e39abd1e	157
saranieves92	1:4875e39abd1e	158	return l_carry;
saranieves92	1:4875e39abd1e	159	}
saranieves92	1:4875e39abd1e	160
saranieves92	1:4875e39abd1e	161	/* Computes p_vli = p_vli >> 1. */
saranieves92	1:4875e39abd1e	162	static void vli_rshift1(uint32_t *p_vli)
saranieves92	1:4875e39abd1e	163	{
saranieves92	1:4875e39abd1e	164	uint32_t *l_end = p_vli;
saranieves92	1:4875e39abd1e	165	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	166
saranieves92	1:4875e39abd1e	167	p_vli += NUM_ECC_DIGITS;
saranieves92	1:4875e39abd1e	168	while(p_vli-- > l_end)
saranieves92	1:4875e39abd1e	169	{
saranieves92	1:4875e39abd1e	170	uint32_t l_temp = *p_vli;
saranieves92	1:4875e39abd1e	171	*p_vli = (l_temp >> 1) \| l_carry;
saranieves92	1:4875e39abd1e	172	l_carry = l_temp << 31;
saranieves92	1:4875e39abd1e	173	}
saranieves92	1:4875e39abd1e	174	}
saranieves92	1:4875e39abd1e	175
saranieves92	1:4875e39abd1e	176	/* Computes p_result = p_left + p_right, returning carry. Can modify in place. */
saranieves92	1:4875e39abd1e	177	static uint32_t vli_add(uint32_t p_result, const uint32_t p_left, const uint32_t *p_right)
saranieves92	1:4875e39abd1e	178	{
saranieves92	1:4875e39abd1e	179	#if (ECC_ASM == ecc_asm_thumb \|\| ECC_ASM == ecc_asm_thumb2 \|\| ECC_ASM == ecc_asm_arm)
saranieves92	1:4875e39abd1e	180	uint32_t l_counter = NUM_ECC_DIGITS;
saranieves92	1:4875e39abd1e	181	uint32_t l_carry = 0; /* carry = 0 initially */
saranieves92	1:4875e39abd1e	182	uint32_t l_left;
saranieves92	1:4875e39abd1e	183	uint32_t l_right;
saranieves92	1:4875e39abd1e	184
saranieves92	1:4875e39abd1e	185	asm volatile (
saranieves92	1:4875e39abd1e	186	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	187	"1: \n\t"
saranieves92	1:4875e39abd1e	188	"ldmia %[lptr]!, {%[left]} \n\t" /* Load left word. */
saranieves92	1:4875e39abd1e	189	"ldmia %[rptr]!, {%[right]} \n\t" /* Load right word. */
saranieves92	1:4875e39abd1e	190	"lsrs %[carry], #1 \n\t" /* Set up carry flag (l_carry = 0 after this). */
saranieves92	1:4875e39abd1e	191	"adcs %[left], %[right] \n\t" /* Add with carry. */
saranieves92	1:4875e39abd1e	192	"adcs %[carry], %[carry] \n\t" /* Store carry bit in l_carry. */
saranieves92	1:4875e39abd1e	193	"stmia %[dptr]!, {%[left]} \n\t" /* Store result word. */
saranieves92	1:4875e39abd1e	194	"subs %[ctr], #1 \n\t" /* Decrement index. */
saranieves92	1:4875e39abd1e	195	"bne 1b \n\t" /* Loop until index == 0. */
saranieves92	1:4875e39abd1e	196	#if (ECC_ASM != ecc_asm_thumb2)
saranieves92	1:4875e39abd1e	197	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	198	#endif
saranieves92	1:4875e39abd1e	199	#if (ECC_ASM == ecc_asm_thumb)
saranieves92	1:4875e39abd1e	200	: [dptr] "+l" (p_result), [lptr] "+l" (p_left), [rptr] "+l" (p_right), [ctr] "+l" (l_counter), [carry] "+l" (l_carry), [left] "=l" (l_left), [right] "=l" (l_right)
saranieves92	1:4875e39abd1e	201	#else
saranieves92	1:4875e39abd1e	202	: [dptr] "+r" (p_result), [lptr] "+r" (p_left), [rptr] "+r" (p_right), [ctr] "+r" (l_counter), [carry] "+r" (l_carry), [left] "=r" (l_left), [right] "=r" (l_right)
saranieves92	1:4875e39abd1e	203	#endif
saranieves92	1:4875e39abd1e	204	:
saranieves92	1:4875e39abd1e	205	: "cc", "memory"
saranieves92	1:4875e39abd1e	206	);
saranieves92	1:4875e39abd1e	207	return l_carry;
saranieves92	1:4875e39abd1e	208
saranieves92	1:4875e39abd1e	209	#else
saranieves92	1:4875e39abd1e	210
saranieves92	1:4875e39abd1e	211	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	212	uint i;
saranieves92	1:4875e39abd1e	213	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	214	{
saranieves92	1:4875e39abd1e	215	uint32_t l_sum = p_left[i] + p_right[i] + l_carry;
saranieves92	1:4875e39abd1e	216	if(l_sum != p_left[i])
saranieves92	1:4875e39abd1e	217	{
saranieves92	1:4875e39abd1e	218	l_carry = (l_sum < p_left[i]);
saranieves92	1:4875e39abd1e	219	}
saranieves92	1:4875e39abd1e	220	p_result[i] = l_sum;
saranieves92	1:4875e39abd1e	221	}
saranieves92	1:4875e39abd1e	222	return l_carry;
saranieves92	1:4875e39abd1e	223	#endif
saranieves92	1:4875e39abd1e	224	}
saranieves92	1:4875e39abd1e	225
saranieves92	1:4875e39abd1e	226	/* Computes p_result = p_left - p_right, returning borrow. Can modify in place. */
saranieves92	1:4875e39abd1e	227	static uint32_t vli_sub(uint32_t p_result, const uint32_t p_left, const uint32_t *p_right)
saranieves92	1:4875e39abd1e	228	{
saranieves92	1:4875e39abd1e	229	#if (ECC_ASM == ecc_asm_thumb \|\| ECC_ASM == ecc_asm_thumb2 \|\| ECC_ASM == ecc_asm_arm)
saranieves92	1:4875e39abd1e	230	uint32_t l_counter = NUM_ECC_DIGITS;
saranieves92	1:4875e39abd1e	231	uint32_t l_carry = 1; /* carry = 1 initially (means don't borrow) */
saranieves92	1:4875e39abd1e	232	uint32_t l_left;
saranieves92	1:4875e39abd1e	233	uint32_t l_right;
saranieves92	1:4875e39abd1e	234
saranieves92	1:4875e39abd1e	235	asm volatile (
saranieves92	1:4875e39abd1e	236	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	237	"1: \n\t"
saranieves92	1:4875e39abd1e	238	"ldmia %[lptr]!, {%[left]} \n\t" /* Load left word. */
saranieves92	1:4875e39abd1e	239	"ldmia %[rptr]!, {%[right]} \n\t" /* Load right word. */
saranieves92	1:4875e39abd1e	240	"lsrs %[carry], #1 \n\t" /* Set up carry flag (l_carry = 0 after this). */
saranieves92	1:4875e39abd1e	241	"sbcs %[left], %[right] \n\t" /* Subtract with borrow. */
saranieves92	1:4875e39abd1e	242	"adcs %[carry], %[carry] \n\t" /* Store carry bit in l_carry. */
saranieves92	1:4875e39abd1e	243	"stmia %[dptr]!, {%[left]} \n\t" /* Store result word. */
saranieves92	1:4875e39abd1e	244	"subs %[ctr], #1 \n\t" /* Decrement index. */
saranieves92	1:4875e39abd1e	245	"bne 1b \n\t" /* Loop until index == 0. */
saranieves92	1:4875e39abd1e	246	#if (ECC_ASM != ecc_asm_thumb2)
saranieves92	1:4875e39abd1e	247	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	248	#endif
saranieves92	1:4875e39abd1e	249	#if (ECC_ASM == ecc_asm_thumb)
saranieves92	1:4875e39abd1e	250	: [dptr] "+l" (p_result), [lptr] "+l" (p_left), [rptr] "+l" (p_right), [ctr] "+l" (l_counter), [carry] "+l" (l_carry), [left] "=l" (l_left), [right] "=l" (l_right)
saranieves92	1:4875e39abd1e	251	#else
saranieves92	1:4875e39abd1e	252	: [dptr] "+r" (p_result), [lptr] "+r" (p_left), [rptr] "+r" (p_right), [ctr] "+r" (l_counter), [carry] "+r" (l_carry), [left] "=r" (l_left), [right] "=r" (l_right)
saranieves92	1:4875e39abd1e	253	#endif
saranieves92	1:4875e39abd1e	254	:
saranieves92	1:4875e39abd1e	255	: "cc", "memory"
saranieves92	1:4875e39abd1e	256	);
saranieves92	1:4875e39abd1e	257	return !l_carry;
saranieves92	1:4875e39abd1e	258
saranieves92	1:4875e39abd1e	259	#else
saranieves92	1:4875e39abd1e	260
saranieves92	1:4875e39abd1e	261	uint32_t l_borrow = 0;
saranieves92	1:4875e39abd1e	262	uint i;
saranieves92	1:4875e39abd1e	263	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	264	{
saranieves92	1:4875e39abd1e	265	uint32_t l_diff = p_left[i] - p_right[i] - l_borrow;
saranieves92	1:4875e39abd1e	266	if(l_diff != p_left[i])
saranieves92	1:4875e39abd1e	267	{
saranieves92	1:4875e39abd1e	268	l_borrow = (l_diff > p_left[i]);
saranieves92	1:4875e39abd1e	269	}
saranieves92	1:4875e39abd1e	270	p_result[i] = l_diff;
saranieves92	1:4875e39abd1e	271	}
saranieves92	1:4875e39abd1e	272	return l_borrow;
saranieves92	1:4875e39abd1e	273	#endif
saranieves92	1:4875e39abd1e	274	}
saranieves92	1:4875e39abd1e	275
saranieves92	1:4875e39abd1e	276	/* Computes p_result = p_left * p_right. */
saranieves92	1:4875e39abd1e	277	static void vli_mult(uint32_t p_result, const uint32_t p_left, const uint32_t *p_right)
saranieves92	1:4875e39abd1e	278	{
saranieves92	1:4875e39abd1e	279	#if (ECC_ASM == ecc_asm_thumb2 \|\| ECC_ASM == ecc_asm_arm)
saranieves92	1:4875e39abd1e	280	uint32_t c0 = 0;
saranieves92	1:4875e39abd1e	281	uint32_t c1 = 0;
saranieves92	1:4875e39abd1e	282	uint32_t c2 = 0;
saranieves92	1:4875e39abd1e	283	uint32_t k = 0;
saranieves92	1:4875e39abd1e	284	uint32_t i;
saranieves92	1:4875e39abd1e	285	uint32_t t0, t1;
saranieves92	1:4875e39abd1e	286
saranieves92	1:4875e39abd1e	287	asm volatile (
saranieves92	1:4875e39abd1e	288	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	289
saranieves92	1:4875e39abd1e	290	"1: \n\t" /* outer loop (k < NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	291	"movs %[i], #0 \n\t" /* i = 0 */
saranieves92	1:4875e39abd1e	292	"b 3f \n\t"
saranieves92	1:4875e39abd1e	293
saranieves92	1:4875e39abd1e	294	"2: \n\t" /* outer loop (k >= NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	295	"movs %[i], %[k] \n\t" /* i = k */
saranieves92	1:4875e39abd1e	296	"subs %[i], %[eccdm1] \n\t" /* i = k - (NUM_ECC_DIGITS - 1) (times 4) */
saranieves92	1:4875e39abd1e	297
saranieves92	1:4875e39abd1e	298	"3: \n\t" /* inner loop */
saranieves92	1:4875e39abd1e	299	"subs %[t0], %[k], %[i] \n\t" /* t0 = k-i */
saranieves92	1:4875e39abd1e	300
saranieves92	1:4875e39abd1e	301	"ldr %[t1], [%[right], %[t0]] \n\t" /* t1 = p_right[k-i] */
saranieves92	1:4875e39abd1e	302	"ldr %[t0], [%[left], %[i]] \n\t" /* t0 = p_left[i] */
saranieves92	1:4875e39abd1e	303
saranieves92	1:4875e39abd1e	304	"umull %[t0], %[t1], %[t0], %[t1] \n\t" /* (t0, t1) = p_left[i] * p_right[k-i] */
saranieves92	1:4875e39abd1e	305
saranieves92	1:4875e39abd1e	306	"adds %[c0], %[t0] \n\t" /* add low word to c0 */
saranieves92	1:4875e39abd1e	307	"adcs %[c1], %[t1] \n\t" /* add high word to c1, including carry */
saranieves92	1:4875e39abd1e	308	"adcs %[c2], #0 \n\t" /* add carry to c2 */
saranieves92	1:4875e39abd1e	309
saranieves92	1:4875e39abd1e	310	"adds %[i], #4 \n\t" /* i += 4 */
saranieves92	1:4875e39abd1e	311	"cmp %[i], %[eccd] \n\t" /* i < NUM_ECC_DIGITS (times 4)? */
saranieves92	1:4875e39abd1e	312	"bge 4f \n\t" /* if not, exit the loop */
saranieves92	1:4875e39abd1e	313	"cmp %[i], %[k] \n\t" /* i <= k? */
saranieves92	1:4875e39abd1e	314	"ble 3b \n\t" /* if so, continue looping */
saranieves92	1:4875e39abd1e	315
saranieves92	1:4875e39abd1e	316	"4: \n\t" /* end inner loop */
saranieves92	1:4875e39abd1e	317
saranieves92	1:4875e39abd1e	318	"str %[c0], [%[result], %[k]] \n\t" /* p_result[k] = c0 */
saranieves92	1:4875e39abd1e	319	"mov %[c0], %[c1] \n\t" /* c0 = c1 */
saranieves92	1:4875e39abd1e	320	"mov %[c1], %[c2] \n\t" /* c1 = c2 */
saranieves92	1:4875e39abd1e	321	"movs %[c2], #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	322	"adds %[k], #4 \n\t" /* k += 4 */
saranieves92	1:4875e39abd1e	323	"cmp %[k], %[eccd] \n\t" /* k < NUM_ECC_DIGITS (times 4) ? */
saranieves92	1:4875e39abd1e	324	"blt 1b \n\t" /* if not, loop back, start with i = 0 */
saranieves92	1:4875e39abd1e	325	"cmp %[k], %[eccd2m1] \n\t" /* k < NUM_ECC_DIGITS * 2 - 1 (times 4) ? */
saranieves92	1:4875e39abd1e	326	"blt 2b \n\t" /* if not, loop back, start with i = (k+1) - NUM_ECC_DIGITS */
saranieves92	1:4875e39abd1e	327	/* end outer loop */
saranieves92	1:4875e39abd1e	328
saranieves92	1:4875e39abd1e	329	"str %[c0], [%[result], %[k]] \n\t" /* p_result[NUM_ECC_DIGITS * 2 - 1] = c0 */
saranieves92	1:4875e39abd1e	330	#if (ECC_ASM != ecc_asm_thumb2)
saranieves92	1:4875e39abd1e	331	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	332	#endif
saranieves92	1:4875e39abd1e	333	: [c0] "+r" (c0), [c1] "+r" (c1), [c2] "+r" (c2), [k] "+r" (k), [i] "=&r" (i), [t0] "=&r" (t0), [t1] "=&r" (t1)
saranieves92	1:4875e39abd1e	334	: [result] "r" (p_result), [left] "r" (p_left), [right] "r" (p_right),
saranieves92	1:4875e39abd1e	335	[eccd] "I" (NUM_ECC_DIGITS * 4), [eccdm1] "I" ((NUM_ECC_DIGITS-1) * 4), [eccd2m1] "I" ((NUM_ECC_DIGITS * 2 - 1) * 4)
saranieves92	1:4875e39abd1e	336	: "cc", "memory"
saranieves92	1:4875e39abd1e	337	);
saranieves92	1:4875e39abd1e	338
saranieves92	1:4875e39abd1e	339	#elif (ECC_ASM == ecc_asm_thumb)
saranieves92	1:4875e39abd1e	340
saranieves92	1:4875e39abd1e	341	register uint32_t *r0 asm("r0") = p_result;
saranieves92	1:4875e39abd1e	342	register uint32_t *r1 asm("r1") = p_left;
saranieves92	1:4875e39abd1e	343	register uint32_t *r2 asm("r2") = p_right;
saranieves92	1:4875e39abd1e	344
saranieves92	1:4875e39abd1e	345	asm volatile (
saranieves92	1:4875e39abd1e	346	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	347	"movs r3, #0 \n\t" /* c0 = 0 */
saranieves92	1:4875e39abd1e	348	"movs r4, #0 \n\t" /* c1 = 0 */
saranieves92	1:4875e39abd1e	349	"movs r5, #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	350	"movs r6, #0 \n\t" /* k = 0 */
saranieves92	1:4875e39abd1e	351
saranieves92	1:4875e39abd1e	352	"push {r0} \n\t" /* keep p_result on the stack */
saranieves92	1:4875e39abd1e	353
saranieves92	1:4875e39abd1e	354	"1: \n\t" /* outer loop (k < NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	355	"movs r7, #0 \n\t" /* r7 = i = 0 */
saranieves92	1:4875e39abd1e	356	"b 3f \n\t"
saranieves92	1:4875e39abd1e	357
saranieves92	1:4875e39abd1e	358	"2: \n\t" /* outer loop (k >= NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	359	"movs r7, r6 \n\t" /* r7 = k */
saranieves92	1:4875e39abd1e	360	"subs r7, %[eccdm1] \n\t" /* r7 = i = k - (NUM_ECC_DIGITS - 1) (times 4) */
saranieves92	1:4875e39abd1e	361
saranieves92	1:4875e39abd1e	362	"3: \n\t" /* inner loop */
saranieves92	1:4875e39abd1e	363	"push {r3, r4, r5, r6} \n\t" /* push things, r3 (c0) is at the top of stack. */
saranieves92	1:4875e39abd1e	364	"subs r0, r6, r7 \n\t" /* r0 = k-i */
saranieves92	1:4875e39abd1e	365
saranieves92	1:4875e39abd1e	366	"ldr r4, [r2, r0] \n\t" /* r4 = p_right[k-i] */
saranieves92	1:4875e39abd1e	367	"ldr r0, [r1, r7] \n\t" /* r0 = p_left[i] */
saranieves92	1:4875e39abd1e	368
saranieves92	1:4875e39abd1e	369	"lsrs r3, r0, #16 \n\t" /* r3 = a1 */
saranieves92	1:4875e39abd1e	370	"uxth r0, r0 \n\t" /* r0 = a0 */
saranieves92	1:4875e39abd1e	371
saranieves92	1:4875e39abd1e	372	"lsrs r5, r4, #16 \n\t" /* r5 = b1 */
saranieves92	1:4875e39abd1e	373	"uxth r4, r4 \n\t" /* r4 = b0 */
saranieves92	1:4875e39abd1e	374
saranieves92	1:4875e39abd1e	375	"movs r6, r3 \n\t" /* r6 = a1 */
saranieves92	1:4875e39abd1e	376	"muls r6, r5, r6 \n\t" /* r6 = a1b1 /
saranieves92	1:4875e39abd1e	377	"muls r3, r4, r3 \n\t" /* r3 = b0a1 /
saranieves92	1:4875e39abd1e	378	"muls r5, r0, r5 \n\t" /* r5 = a0b1 /
saranieves92	1:4875e39abd1e	379	"muls r0, r4, r0 \n\t" /* r0 = a0b0 /
saranieves92	1:4875e39abd1e	380
saranieves92	1:4875e39abd1e	381	"movs r4, #0 \n\t" /* r4 = 0 */
saranieves92	1:4875e39abd1e	382	"adds r3, r5 \n\t" /* r3 = b0a1 + a0b1 */
saranieves92	1:4875e39abd1e	383	"adcs r4, r4 \n\t" /* r4 = carry */
saranieves92	1:4875e39abd1e	384	"lsls r4, #16 \n\t" /* r4 = carry << 16 */
saranieves92	1:4875e39abd1e	385	"adds r6, r4 \n\t" /* r6 = a1b1 + carry /
saranieves92	1:4875e39abd1e	386
saranieves92	1:4875e39abd1e	387	"lsls r4, r3, #16 \n\t" /* r4 = (b0a1 + a0b1) << 16 */
saranieves92	1:4875e39abd1e	388	"lsrs r3, #16 \n\t" /* r3 = (b0a1 + a0b1) >> 16 */
saranieves92	1:4875e39abd1e	389	"adds r0, r4 \n\t" /* r0 = low word = a0b0 + ((b0a1 + a0b1) << 16) /
saranieves92	1:4875e39abd1e	390	"adcs r6, r3 \n\t" /* r6 = high word = a1b1 + carry + ((b0a1 + a0b1) >> 16) /
saranieves92	1:4875e39abd1e	391
saranieves92	1:4875e39abd1e	392	"pop {r3, r4, r5} \n\t" /* r3 = c0, r4 = c1, r5 = c2 */
saranieves92	1:4875e39abd1e	393	"adds r3, r0 \n\t" /* add low word to c0 */
saranieves92	1:4875e39abd1e	394	"adcs r4, r6 \n\t" /* add high word to c1, including carry */
saranieves92	1:4875e39abd1e	395	"movs r0, #0 \n\t" /* r0 = 0 (does not affect carry bit) */
saranieves92	1:4875e39abd1e	396	"adcs r5, r0 \n\t" /* add carry to c2 */
saranieves92	1:4875e39abd1e	397
saranieves92	1:4875e39abd1e	398	"pop {r6} \n\t" /* r6 = k */
saranieves92	1:4875e39abd1e	399
saranieves92	1:4875e39abd1e	400	"adds r7, #4 \n\t" /* i += 4 */
saranieves92	1:4875e39abd1e	401	"cmp r7, %[eccd] \n\t" /* i < NUM_ECC_DIGITS (times 4)? */
saranieves92	1:4875e39abd1e	402	"bge 4f \n\t" /* if not, exit the loop */
saranieves92	1:4875e39abd1e	403	"cmp r7, r6 \n\t" /* i <= k? */
saranieves92	1:4875e39abd1e	404	"ble 3b \n\t" /* if so, continue looping */
saranieves92	1:4875e39abd1e	405
saranieves92	1:4875e39abd1e	406	"4: \n\t" /* end inner loop */
saranieves92	1:4875e39abd1e	407
saranieves92	1:4875e39abd1e	408	"ldr r0, [sp, #0] \n\t" /* r0 = p_result */
saranieves92	1:4875e39abd1e	409
saranieves92	1:4875e39abd1e	410	"str r3, [r0, r6] \n\t" /* p_result[k] = c0 */
saranieves92	1:4875e39abd1e	411	"mov r3, r4 \n\t" /* c0 = c1 */
saranieves92	1:4875e39abd1e	412	"mov r4, r5 \n\t" /* c1 = c2 */
saranieves92	1:4875e39abd1e	413	"movs r5, #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	414	"adds r6, #4 \n\t" /* k += 4 */
saranieves92	1:4875e39abd1e	415	"cmp r6, %[eccd] \n\t" /* k < NUM_ECC_DIGITS (times 4) ? */
saranieves92	1:4875e39abd1e	416	"blt 1b \n\t" /* if not, loop back, start with i = 0 */
saranieves92	1:4875e39abd1e	417	"cmp r6, %[eccd2m1] \n\t" /* k < NUM_ECC_DIGITS * 2 - 1 (times 4) ? */
saranieves92	1:4875e39abd1e	418	"blt 2b \n\t" /* if not, loop back, start with i = (k+1) - NUM_ECC_DIGITS */
saranieves92	1:4875e39abd1e	419	/* end outer loop */
saranieves92	1:4875e39abd1e	420
saranieves92	1:4875e39abd1e	421	"str r3, [r0, r6] \n\t" /* p_result[NUM_ECC_DIGITS * 2 - 1] = c0 */
saranieves92	1:4875e39abd1e	422	"pop {r0} \n\t" /* pop p_result off the stack */
saranieves92	1:4875e39abd1e	423
saranieves92	1:4875e39abd1e	424	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	425	:
saranieves92	1:4875e39abd1e	426	: [r0] "l" (r0), [r1] "l" (r1), [r2] "l" (r2), [eccd] "I" (NUM_ECC_DIGITS * 4), [eccdm1] "I" ((NUM_ECC_DIGITS-1) * 4), [eccd2m1] "I" ((NUM_ECC_DIGITS * 2 - 1) * 4)
saranieves92	1:4875e39abd1e	427	: "r3", "r4", "r5", "r6", "r7", "cc", "memory"
saranieves92	1:4875e39abd1e	428	);
saranieves92	1:4875e39abd1e	429
saranieves92	1:4875e39abd1e	430	#else
saranieves92	1:4875e39abd1e	431
saranieves92	1:4875e39abd1e	432	uint64_t r01 = 0;
saranieves92	1:4875e39abd1e	433	uint32_t r2 = 0;
saranieves92	1:4875e39abd1e	434
saranieves92	1:4875e39abd1e	435	uint i, k;
saranieves92	1:4875e39abd1e	436
saranieves92	1:4875e39abd1e	437	/* Compute each digit of p_result in sequence, maintaining the carries. */
saranieves92	1:4875e39abd1e	438	for(k=0; k < NUM_ECC_DIGITS*2 - 1; ++k)
saranieves92	1:4875e39abd1e	439	{
saranieves92	1:4875e39abd1e	440	uint l_min = (k < NUM_ECC_DIGITS ? 0 : (k + 1) - NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	441	for(i=l_min; i<=k && i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	442	{
saranieves92	1:4875e39abd1e	443	uint64_t l_product = (uint64_t)p_left[i] * p_right[k-i];
saranieves92	1:4875e39abd1e	444	r01 += l_product;
saranieves92	1:4875e39abd1e	445	r2 += (r01 < l_product);
saranieves92	1:4875e39abd1e	446	}
saranieves92	1:4875e39abd1e	447	p_result[k] = (uint32_t)r01;
saranieves92	1:4875e39abd1e	448	r01 = (r01 >> 32) \| (((uint64_t)r2) << 32);
saranieves92	1:4875e39abd1e	449	r2 = 0;
saranieves92	1:4875e39abd1e	450	}
saranieves92	1:4875e39abd1e	451
saranieves92	1:4875e39abd1e	452	p_result[NUM_ECC_DIGITS*2 - 1] = (uint32_t)r01;
saranieves92	1:4875e39abd1e	453	#endif
saranieves92	1:4875e39abd1e	454	}
saranieves92	1:4875e39abd1e	455
saranieves92	1:4875e39abd1e	456	/* Computes p_result = (p_left + p_right) % p_mod.
saranieves92	1:4875e39abd1e	457	Assumes that p_left < p_mod and p_right < p_mod, p_result != p_mod. */
saranieves92	1:4875e39abd1e	458	static void vli_modAdd(uint32_t p_result, const uint32_t p_left,
saranieves92	1:4875e39abd1e	459	const uint32_t p_right, const uint32_t p_mod)
saranieves92	1:4875e39abd1e	460	{
saranieves92	1:4875e39abd1e	461	uint32_t l_carry = vli_add(p_result, p_left, p_right);
saranieves92	1:4875e39abd1e	462	if(l_carry \|\| vli_cmp(p_result, p_mod) >= 0)
saranieves92	1:4875e39abd1e	463	{ /* p_result > p_mod (p_result = p_mod + remainder), so subtract p_mod to get remainder. */
saranieves92	1:4875e39abd1e	464	vli_sub(p_result, p_result, p_mod);
saranieves92	1:4875e39abd1e	465	}
saranieves92	1:4875e39abd1e	466	}
saranieves92	1:4875e39abd1e	467
saranieves92	1:4875e39abd1e	468	/* Computes p_result = (p_left - p_right) % p_mod.
saranieves92	1:4875e39abd1e	469	Assumes that p_left < p_mod and p_right < p_mod, p_result != p_mod. */
saranieves92	1:4875e39abd1e	470	static void vli_modSub(uint32_t p_result, const uint32_t p_left,
saranieves92	1:4875e39abd1e	471	const uint32_t p_right, const uint32_t p_mod)
saranieves92	1:4875e39abd1e	472	{
saranieves92	1:4875e39abd1e	473	uint32_t l_borrow = vli_sub(p_result, p_left, p_right);
saranieves92	1:4875e39abd1e	474	if(l_borrow)
saranieves92	1:4875e39abd1e	475	{ /* In this case, p_result == -diff == (max int) - diff.
saranieves92	1:4875e39abd1e	476	Since -x % d == d - x, we can get the correct result from p_result + p_mod (with overflow). */
saranieves92	1:4875e39abd1e	477	vli_add(p_result, p_result, p_mod);
saranieves92	1:4875e39abd1e	478	}
saranieves92	1:4875e39abd1e	479	}
saranieves92	1:4875e39abd1e	480
saranieves92	1:4875e39abd1e	481	#if (ECC_CURVE == secp128r1)
saranieves92	1:4875e39abd1e	482
saranieves92	1:4875e39abd1e	483	/* Computes p_result = p_product % curve_p.
saranieves92	1:4875e39abd1e	484	See algorithm 5 and 6 from http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */
saranieves92	1:4875e39abd1e	485	static void vli_mmod_fast(uint32_t p_result, const uint32_t p_product)
saranieves92	1:4875e39abd1e	486	{
saranieves92	1:4875e39abd1e	487	uint32_t l_tmp[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	488	int l_carry;
saranieves92	1:4875e39abd1e	489
saranieves92	1:4875e39abd1e	490	vli_set(p_result, p_product);
saranieves92	1:4875e39abd1e	491
saranieves92	1:4875e39abd1e	492	l_tmp[0] = p_product[4];
saranieves92	1:4875e39abd1e	493	l_tmp[1] = p_product[5];
saranieves92	1:4875e39abd1e	494	l_tmp[2] = p_product[6];
saranieves92	1:4875e39abd1e	495	l_tmp[3] = (p_product[7] & 0x00000001) \| (p_product[4] << 1);
saranieves92	1:4875e39abd1e	496	l_carry = vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	497
saranieves92	1:4875e39abd1e	498	l_tmp[0] = (p_product[4] >> 31) \| (p_product[5] << 1);
saranieves92	1:4875e39abd1e	499	l_tmp[1] = (p_product[5] >> 31) \| (p_product[6] << 1);
saranieves92	1:4875e39abd1e	500	l_tmp[2] = (p_product[6] >> 31) \| (p_product[7] << 1);
saranieves92	1:4875e39abd1e	501	l_tmp[3] = (p_product[7] >> 31) \| ((p_product[4] & 0x80000000) >> 30) \| (p_product[5] << 2);
saranieves92	1:4875e39abd1e	502	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	503
saranieves92	1:4875e39abd1e	504	l_tmp[0] = (p_product[5] >> 30) \| (p_product[6] << 2);
saranieves92	1:4875e39abd1e	505	l_tmp[1] = (p_product[6] >> 30) \| (p_product[7] << 2);
saranieves92	1:4875e39abd1e	506	l_tmp[2] = (p_product[7] >> 30);
saranieves92	1:4875e39abd1e	507	l_tmp[3] = ((p_product[5] & 0xC0000000) >> 29) \| (p_product[6] << 3);
saranieves92	1:4875e39abd1e	508	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	509
saranieves92	1:4875e39abd1e	510	l_tmp[0] = (p_product[6] >> 29) \| (p_product[7] << 3);
saranieves92	1:4875e39abd1e	511	l_tmp[1] = (p_product[7] >> 29);
saranieves92	1:4875e39abd1e	512	l_tmp[2] = 0;
saranieves92	1:4875e39abd1e	513	l_tmp[3] = ((p_product[6] & 0xE0000000) >> 28) \| (p_product[7] << 4);
saranieves92	1:4875e39abd1e	514	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	515
saranieves92	1:4875e39abd1e	516	l_tmp[0] = (p_product[7] >> 28);
saranieves92	1:4875e39abd1e	517	l_tmp[1] = 0;
saranieves92	1:4875e39abd1e	518	l_tmp[2] = 0;
saranieves92	1:4875e39abd1e	519	l_tmp[3] = (p_product[7] & 0xFFFFFFFE);
saranieves92	1:4875e39abd1e	520	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	521
saranieves92	1:4875e39abd1e	522	l_tmp[0] = 0;
saranieves92	1:4875e39abd1e	523	l_tmp[1] = 0;
saranieves92	1:4875e39abd1e	524	l_tmp[2] = 0;
saranieves92	1:4875e39abd1e	525	l_tmp[3] = ((p_product[7] & 0xF0000000) >> 27);
saranieves92	1:4875e39abd1e	526	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	527
saranieves92	1:4875e39abd1e	528	while(l_carry \|\| vli_cmp(curve_p, p_result) != 1)
saranieves92	1:4875e39abd1e	529	{
saranieves92	1:4875e39abd1e	530	l_carry -= vli_sub(p_result, p_result, curve_p);
saranieves92	1:4875e39abd1e	531	}
saranieves92	1:4875e39abd1e	532	}
saranieves92	1:4875e39abd1e	533
saranieves92	1:4875e39abd1e	534	#elif (ECC_CURVE == secp192r1)
saranieves92	1:4875e39abd1e	535
saranieves92	1:4875e39abd1e	536	/* Computes p_result = p_product % curve_p.
saranieves92	1:4875e39abd1e	537	See algorithm 5 and 6 from http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */
saranieves92	1:4875e39abd1e	538	static void vli_mmod_fast(uint32_t p_result, const uint32_t p_product)
saranieves92	1:4875e39abd1e	539	{
saranieves92	1:4875e39abd1e	540	uint32_t l_tmp[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	541	int l_carry;
saranieves92	1:4875e39abd1e	542
saranieves92	1:4875e39abd1e	543	vli_set(p_result, p_product);
saranieves92	1:4875e39abd1e	544
saranieves92	1:4875e39abd1e	545	vli_set(l_tmp, &p_product[6]);
saranieves92	1:4875e39abd1e	546	l_carry = vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	547
saranieves92	1:4875e39abd1e	548	l_tmp[0] = l_tmp[1] = 0;
saranieves92	1:4875e39abd1e	549	l_tmp[2] = p_product[6];
saranieves92	1:4875e39abd1e	550	l_tmp[3] = p_product[7];
saranieves92	1:4875e39abd1e	551	l_tmp[4] = p_product[8];
saranieves92	1:4875e39abd1e	552	l_tmp[5] = p_product[9];
saranieves92	1:4875e39abd1e	553	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	554
saranieves92	1:4875e39abd1e	555	l_tmp[0] = l_tmp[2] = p_product[10];
saranieves92	1:4875e39abd1e	556	l_tmp[1] = l_tmp[3] = p_product[11];
saranieves92	1:4875e39abd1e	557	l_tmp[4] = l_tmp[5] = 0;
saranieves92	1:4875e39abd1e	558	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	559
saranieves92	1:4875e39abd1e	560	while(l_carry \|\| vli_cmp(curve_p, p_result) != 1)
saranieves92	1:4875e39abd1e	561	{
saranieves92	1:4875e39abd1e	562	l_carry -= vli_sub(p_result, p_result, curve_p);
saranieves92	1:4875e39abd1e	563	}
saranieves92	1:4875e39abd1e	564	}
saranieves92	1:4875e39abd1e	565
saranieves92	1:4875e39abd1e	566	#elif (ECC_CURVE == secp256r1)
saranieves92	1:4875e39abd1e	567
saranieves92	1:4875e39abd1e	568	/* Computes p_result = p_product % curve_p
saranieves92	1:4875e39abd1e	569	from http://www.nsa.gov/ia/_files/nist-routines.pdf */
saranieves92	1:4875e39abd1e	570	static void vli_mmod_fast(uint32_t p_result, const uint32_t p_product)
saranieves92	1:4875e39abd1e	571	{
saranieves92	1:4875e39abd1e	572	uint32_t l_tmp[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	573	int l_carry;
saranieves92	1:4875e39abd1e	574
saranieves92	1:4875e39abd1e	575	/* t */
saranieves92	1:4875e39abd1e	576	vli_set(p_result, p_product);
saranieves92	1:4875e39abd1e	577
saranieves92	1:4875e39abd1e	578	/* s1 */
saranieves92	1:4875e39abd1e	579	l_tmp[0] = l_tmp[1] = l_tmp[2] = 0;
saranieves92	1:4875e39abd1e	580	l_tmp[3] = p_product[11];
saranieves92	1:4875e39abd1e	581	l_tmp[4] = p_product[12];
saranieves92	1:4875e39abd1e	582	l_tmp[5] = p_product[13];
saranieves92	1:4875e39abd1e	583	l_tmp[6] = p_product[14];
saranieves92	1:4875e39abd1e	584	l_tmp[7] = p_product[15];
saranieves92	1:4875e39abd1e	585	l_carry = vli_lshift(l_tmp, l_tmp, 1);
saranieves92	1:4875e39abd1e	586	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	587
saranieves92	1:4875e39abd1e	588	/* s2 */
saranieves92	1:4875e39abd1e	589	l_tmp[3] = p_product[12];
saranieves92	1:4875e39abd1e	590	l_tmp[4] = p_product[13];
saranieves92	1:4875e39abd1e	591	l_tmp[5] = p_product[14];
saranieves92	1:4875e39abd1e	592	l_tmp[6] = p_product[15];
saranieves92	1:4875e39abd1e	593	l_tmp[7] = 0;
saranieves92	1:4875e39abd1e	594	l_carry += vli_lshift(l_tmp, l_tmp, 1);
saranieves92	1:4875e39abd1e	595	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	596
saranieves92	1:4875e39abd1e	597	/* s3 */
saranieves92	1:4875e39abd1e	598	l_tmp[0] = p_product[8];
saranieves92	1:4875e39abd1e	599	l_tmp[1] = p_product[9];
saranieves92	1:4875e39abd1e	600	l_tmp[2] = p_product[10];
saranieves92	1:4875e39abd1e	601	l_tmp[3] = l_tmp[4] = l_tmp[5] = 0;
saranieves92	1:4875e39abd1e	602	l_tmp[6] = p_product[14];
saranieves92	1:4875e39abd1e	603	l_tmp[7] = p_product[15];
saranieves92	1:4875e39abd1e	604	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	605
saranieves92	1:4875e39abd1e	606	/* s4 */
saranieves92	1:4875e39abd1e	607	l_tmp[0] = p_product[9];
saranieves92	1:4875e39abd1e	608	l_tmp[1] = p_product[10];
saranieves92	1:4875e39abd1e	609	l_tmp[2] = p_product[11];
saranieves92	1:4875e39abd1e	610	l_tmp[3] = p_product[13];
saranieves92	1:4875e39abd1e	611	l_tmp[4] = p_product[14];
saranieves92	1:4875e39abd1e	612	l_tmp[5] = p_product[15];
saranieves92	1:4875e39abd1e	613	l_tmp[6] = p_product[13];
saranieves92	1:4875e39abd1e	614	l_tmp[7] = p_product[8];
saranieves92	1:4875e39abd1e	615	l_carry += vli_add(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	616
saranieves92	1:4875e39abd1e	617	/* d1 */
saranieves92	1:4875e39abd1e	618	l_tmp[0] = p_product[11];
saranieves92	1:4875e39abd1e	619	l_tmp[1] = p_product[12];
saranieves92	1:4875e39abd1e	620	l_tmp[2] = p_product[13];
saranieves92	1:4875e39abd1e	621	l_tmp[3] = l_tmp[4] = l_tmp[5] = 0;
saranieves92	1:4875e39abd1e	622	l_tmp[6] = p_product[8];
saranieves92	1:4875e39abd1e	623	l_tmp[7] = p_product[10];
saranieves92	1:4875e39abd1e	624	l_carry -= vli_sub(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	625
saranieves92	1:4875e39abd1e	626	/* d2 */
saranieves92	1:4875e39abd1e	627	l_tmp[0] = p_product[12];
saranieves92	1:4875e39abd1e	628	l_tmp[1] = p_product[13];
saranieves92	1:4875e39abd1e	629	l_tmp[2] = p_product[14];
saranieves92	1:4875e39abd1e	630	l_tmp[3] = p_product[15];
saranieves92	1:4875e39abd1e	631	l_tmp[4] = l_tmp[5] = 0;
saranieves92	1:4875e39abd1e	632	l_tmp[6] = p_product[9];
saranieves92	1:4875e39abd1e	633	l_tmp[7] = p_product[11];
saranieves92	1:4875e39abd1e	634	l_carry -= vli_sub(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	635
saranieves92	1:4875e39abd1e	636	/* d3 */
saranieves92	1:4875e39abd1e	637	l_tmp[0] = p_product[13];
saranieves92	1:4875e39abd1e	638	l_tmp[1] = p_product[14];
saranieves92	1:4875e39abd1e	639	l_tmp[2] = p_product[15];
saranieves92	1:4875e39abd1e	640	l_tmp[3] = p_product[8];
saranieves92	1:4875e39abd1e	641	l_tmp[4] = p_product[9];
saranieves92	1:4875e39abd1e	642	l_tmp[5] = p_product[10];
saranieves92	1:4875e39abd1e	643	l_tmp[6] = 0;
saranieves92	1:4875e39abd1e	644	l_tmp[7] = p_product[12];
saranieves92	1:4875e39abd1e	645	l_carry -= vli_sub(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	646
saranieves92	1:4875e39abd1e	647	/* d4 */
saranieves92	1:4875e39abd1e	648	l_tmp[0] = p_product[14];
saranieves92	1:4875e39abd1e	649	l_tmp[1] = p_product[15];
saranieves92	1:4875e39abd1e	650	l_tmp[2] = 0;
saranieves92	1:4875e39abd1e	651	l_tmp[3] = p_product[9];
saranieves92	1:4875e39abd1e	652	l_tmp[4] = p_product[10];
saranieves92	1:4875e39abd1e	653	l_tmp[5] = p_product[11];
saranieves92	1:4875e39abd1e	654	l_tmp[6] = 0;
saranieves92	1:4875e39abd1e	655	l_tmp[7] = p_product[13];
saranieves92	1:4875e39abd1e	656	l_carry -= vli_sub(p_result, p_result, l_tmp);
saranieves92	1:4875e39abd1e	657
saranieves92	1:4875e39abd1e	658	if(l_carry < 0)
saranieves92	1:4875e39abd1e	659	{
saranieves92	1:4875e39abd1e	660	do
saranieves92	1:4875e39abd1e	661	{
saranieves92	1:4875e39abd1e	662	l_carry += vli_add(p_result, p_result, curve_p);
saranieves92	1:4875e39abd1e	663	} while(l_carry < 0);
saranieves92	1:4875e39abd1e	664	}
saranieves92	1:4875e39abd1e	665	else
saranieves92	1:4875e39abd1e	666	{
saranieves92	1:4875e39abd1e	667	while(l_carry \|\| vli_cmp(curve_p, p_result) != 1)
saranieves92	1:4875e39abd1e	668	{
saranieves92	1:4875e39abd1e	669	l_carry -= vli_sub(p_result, p_result, curve_p);
saranieves92	1:4875e39abd1e	670	}
saranieves92	1:4875e39abd1e	671	}
saranieves92	1:4875e39abd1e	672	}
saranieves92	1:4875e39abd1e	673
saranieves92	1:4875e39abd1e	674	#elif (ECC_CURVE == secp384r1)
saranieves92	1:4875e39abd1e	675
saranieves92	1:4875e39abd1e	676	static void omega_mult(uint32_t p_result, const uint32_t p_right)
saranieves92	1:4875e39abd1e	677	{
saranieves92	1:4875e39abd1e	678	/* Multiply by (2^128 + 2^96 - 2^32 + 1). */
saranieves92	1:4875e39abd1e	679	vli_set(p_result, p_right); /* 1 */
saranieves92	1:4875e39abd1e	680	p_result[3 + NUM_ECC_DIGITS] = vli_add(p_result + 3, p_result + 3, p_right); /* 2^96 + 1 */
saranieves92	1:4875e39abd1e	681	p_result[4 + NUM_ECC_DIGITS] = vli_add(p_result + 4, p_result + 4, p_right); /* 2^128 + 2^96 + 1 */
saranieves92	1:4875e39abd1e	682	if(vli_sub(p_result + 1, p_result + 1, p_right)) /* 2^128 + 2^96 - 2^32 + 1 */
saranieves92	1:4875e39abd1e	683	{ /* Propagate borrow if necessary. */
saranieves92	1:4875e39abd1e	684	uint i;
saranieves92	1:4875e39abd1e	685	for(i = 1 + NUM_ECC_DIGITS; ; ++i)
saranieves92	1:4875e39abd1e	686	{
saranieves92	1:4875e39abd1e	687	--p_result[i];
saranieves92	1:4875e39abd1e	688	if(p_result[i] != 0xffffffff)
saranieves92	1:4875e39abd1e	689	{
saranieves92	1:4875e39abd1e	690	break;
saranieves92	1:4875e39abd1e	691	}
saranieves92	1:4875e39abd1e	692	}
saranieves92	1:4875e39abd1e	693	}
saranieves92	1:4875e39abd1e	694	}
saranieves92	1:4875e39abd1e	695
saranieves92	1:4875e39abd1e	696	/* Computes p_result = p_product % curve_p
saranieves92	1:4875e39abd1e	697	see PDF "Comparing Elliptic Curve Cryptography and RSA on 8-bit CPUs"
saranieves92	1:4875e39abd1e	698	section "Curve-Specific Optimizations" */
saranieves92	1:4875e39abd1e	699	static void vli_mmod_fast(uint32_t p_result, const uint32_t p_product)
saranieves92	1:4875e39abd1e	700	{
saranieves92	1:4875e39abd1e	701	uint32_t l_tmp[2*NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	702
saranieves92	1:4875e39abd1e	703	while(!vli_isZero(p_product + NUM_ECC_DIGITS)) /* While c1 != 0 */
saranieves92	1:4875e39abd1e	704	{
saranieves92	1:4875e39abd1e	705	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	706	uint i;
saranieves92	1:4875e39abd1e	707
saranieves92	1:4875e39abd1e	708	vli_clear(l_tmp);
saranieves92	1:4875e39abd1e	709	vli_clear(l_tmp + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	710	omega_mult(l_tmp, p_product + NUM_ECC_DIGITS); /* tmp = w * c1 */
saranieves92	1:4875e39abd1e	711	vli_clear(p_product + NUM_ECC_DIGITS); /* p = c0 */
saranieves92	1:4875e39abd1e	712
saranieves92	1:4875e39abd1e	713	/* (c1, c0) = c0 + w * c1 */
saranieves92	1:4875e39abd1e	714	for(i=0; i<NUM_ECC_DIGITS+5; ++i)
saranieves92	1:4875e39abd1e	715	{
saranieves92	1:4875e39abd1e	716	uint32_t l_sum = p_product[i] + l_tmp[i] + l_carry;
saranieves92	1:4875e39abd1e	717	if(l_sum != p_product[i])
saranieves92	1:4875e39abd1e	718	{
saranieves92	1:4875e39abd1e	719	l_carry = (l_sum < p_product[i]);
saranieves92	1:4875e39abd1e	720	}
saranieves92	1:4875e39abd1e	721	p_product[i] = l_sum;
saranieves92	1:4875e39abd1e	722	}
saranieves92	1:4875e39abd1e	723	}
saranieves92	1:4875e39abd1e	724
saranieves92	1:4875e39abd1e	725	while(vli_cmp(p_product, curve_p) > 0)
saranieves92	1:4875e39abd1e	726	{
saranieves92	1:4875e39abd1e	727	vli_sub(p_product, p_product, curve_p);
saranieves92	1:4875e39abd1e	728	}
saranieves92	1:4875e39abd1e	729	vli_set(p_result, p_product);
saranieves92	1:4875e39abd1e	730	}
saranieves92	1:4875e39abd1e	731
saranieves92	1:4875e39abd1e	732	#elif (ECC_CURVE == secp256k1)
saranieves92	1:4875e39abd1e	733
saranieves92	1:4875e39abd1e	734	static void omega_mult(uint32_t p_result, const uint32_t p_right)
saranieves92	1:4875e39abd1e	735	{
saranieves92	1:4875e39abd1e	736	/* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */
saranieves92	1:4875e39abd1e	737	uint64_t l_mult = 0x3D1; /* everything except 2^32 */
saranieves92	1:4875e39abd1e	738	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	739	uint i;
saranieves92	1:4875e39abd1e	740	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	741	{
saranieves92	1:4875e39abd1e	742	uint64_t p = l_mult * p_right[i] + l_carry;
saranieves92	1:4875e39abd1e	743	p_result[i] = (p & 0xffffffff);
saranieves92	1:4875e39abd1e	744	l_carry = p >> 32;
saranieves92	1:4875e39abd1e	745	}
saranieves92	1:4875e39abd1e	746	p_result[NUM_ECC_DIGITS] = l_carry;
saranieves92	1:4875e39abd1e	747
saranieves92	1:4875e39abd1e	748	p_result[1 + NUM_ECC_DIGITS] = vli_add(p_result + 1, p_result + 1, p_right); /* add the 2^32 multiple */
saranieves92	1:4875e39abd1e	749	}
saranieves92	1:4875e39abd1e	750
saranieves92	1:4875e39abd1e	751	/* Computes p_result = p_product % curve_p */
saranieves92	1:4875e39abd1e	752	static void vli_mmod_fast(uint32_t p_result, const uint32_t p_product)
saranieves92	1:4875e39abd1e	753	{
saranieves92	1:4875e39abd1e	754	uint32_t l_tmp[2*NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	755
saranieves92	1:4875e39abd1e	756	while(!vli_isZero(p_product + NUM_ECC_DIGITS)) /* While c1 != 0 */
saranieves92	1:4875e39abd1e	757	{
saranieves92	1:4875e39abd1e	758	uint32_t l_carry = 0;
saranieves92	1:4875e39abd1e	759	uint i;
saranieves92	1:4875e39abd1e	760
saranieves92	1:4875e39abd1e	761	vli_clear(l_tmp);
saranieves92	1:4875e39abd1e	762	vli_clear(l_tmp + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	763	omega_mult(l_tmp, p_product + NUM_ECC_DIGITS); /* tmp = w * c1 */
saranieves92	1:4875e39abd1e	764	vli_clear(p_product + NUM_ECC_DIGITS); /* p = c0 */
saranieves92	1:4875e39abd1e	765
saranieves92	1:4875e39abd1e	766	/* (c1, c0) = c0 + w * c1 */
saranieves92	1:4875e39abd1e	767	for(i=0; i<NUM_ECC_DIGITS+2; ++i)
saranieves92	1:4875e39abd1e	768	{
saranieves92	1:4875e39abd1e	769	uint32_t l_sum = p_product[i] + l_tmp[i] + l_carry;
saranieves92	1:4875e39abd1e	770	if(l_sum != p_product[i])
saranieves92	1:4875e39abd1e	771	{
saranieves92	1:4875e39abd1e	772	l_carry = (l_sum < p_product[i]);
saranieves92	1:4875e39abd1e	773	}
saranieves92	1:4875e39abd1e	774	p_product[i] = l_sum;
saranieves92	1:4875e39abd1e	775	}
saranieves92	1:4875e39abd1e	776	}
saranieves92	1:4875e39abd1e	777
saranieves92	1:4875e39abd1e	778	while(vli_cmp(p_product, curve_p) > 0)
saranieves92	1:4875e39abd1e	779	{
saranieves92	1:4875e39abd1e	780	vli_sub(p_product, p_product, curve_p);
saranieves92	1:4875e39abd1e	781	}
saranieves92	1:4875e39abd1e	782	vli_set(p_result, p_product);
saranieves92	1:4875e39abd1e	783	}
saranieves92	1:4875e39abd1e	784
saranieves92	1:4875e39abd1e	785	#endif
saranieves92	1:4875e39abd1e	786
saranieves92	1:4875e39abd1e	787	/* Computes p_result = (p_left * p_right) % curve_p. */
saranieves92	1:4875e39abd1e	788	static void vli_modMult_fast(uint32_t p_result, const uint32_t p_left, const uint32_t *p_right)
saranieves92	1:4875e39abd1e	789	{
saranieves92	1:4875e39abd1e	790	uint32_t l_product[2 * NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	791	vli_mult(l_product, p_left, p_right);
saranieves92	1:4875e39abd1e	792	vli_mmod_fast(p_result, l_product);
saranieves92	1:4875e39abd1e	793	}
saranieves92	1:4875e39abd1e	794
saranieves92	1:4875e39abd1e	795	#if ECC_SQUARE_FUNC
saranieves92	1:4875e39abd1e	796
saranieves92	1:4875e39abd1e	797	/* Computes p_result = p_left^2. */
saranieves92	1:4875e39abd1e	798	static void vli_square(uint32_t p_result, const uint32_t p_left)
saranieves92	1:4875e39abd1e	799	{
saranieves92	1:4875e39abd1e	800	#if (ECC_ASM == ecc_asm_thumb2 \|\| ECC_ASM == ecc_asm_arm)
saranieves92	1:4875e39abd1e	801	uint32_t c0 = 0;
saranieves92	1:4875e39abd1e	802	uint32_t c1 = 0;
saranieves92	1:4875e39abd1e	803	uint32_t c2 = 0;
saranieves92	1:4875e39abd1e	804	uint32_t k = 0;
saranieves92	1:4875e39abd1e	805	uint32_t i, tt;
saranieves92	1:4875e39abd1e	806	uint32_t t0, t1;
saranieves92	1:4875e39abd1e	807
saranieves92	1:4875e39abd1e	808	asm volatile (
saranieves92	1:4875e39abd1e	809	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	810
saranieves92	1:4875e39abd1e	811	"1: \n\t" /* outer loop (k < NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	812	"movs %[i], #0 \n\t" /* i = 0 */
saranieves92	1:4875e39abd1e	813	"b 3f \n\t"
saranieves92	1:4875e39abd1e	814
saranieves92	1:4875e39abd1e	815	"2: \n\t" /* outer loop (k >= NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	816	"movs %[i], %[k] \n\t" /* i = k */
saranieves92	1:4875e39abd1e	817	"subs %[i], %[eccdm1] \n\t" /* i = k - (NUM_ECC_DIGITS - 1) (times 4) */
saranieves92	1:4875e39abd1e	818
saranieves92	1:4875e39abd1e	819	"3: \n\t" /* inner loop */
saranieves92	1:4875e39abd1e	820	"subs %[tt], %[k], %[i] \n\t" /* tt = k-i */
saranieves92	1:4875e39abd1e	821
saranieves92	1:4875e39abd1e	822	"ldr %[t1], [%[left], %[tt]] \n\t" /* t1 = p_left[k-i] */
saranieves92	1:4875e39abd1e	823	"ldr %[t0], [%[left], %[i]] \n\t" /* t0 = p_left[i] */
saranieves92	1:4875e39abd1e	824
saranieves92	1:4875e39abd1e	825	"umull %[t0], %[t1], %[t0], %[t1] \n\t" /* (t0, t1) = p_left[i] * p_right[k-i] */
saranieves92	1:4875e39abd1e	826
saranieves92	1:4875e39abd1e	827	"cmp %[i], %[tt] \n\t" /* (i < k-i) ? */
saranieves92	1:4875e39abd1e	828	"bge 4f \n\t" /* if i >= k-i, skip */
saranieves92	1:4875e39abd1e	829	"lsls %[t1], #1 \n\t" /* high word << 1 */
saranieves92	1:4875e39abd1e	830	"adc %[c2], #0 \n\t" /* add carry bit to c2 */
saranieves92	1:4875e39abd1e	831	"lsls %[t0], #1 \n\t" /* low word << 1 */
saranieves92	1:4875e39abd1e	832	"adc %[t1], #0 \n\t" /* add carry bit to high word */
saranieves92	1:4875e39abd1e	833
saranieves92	1:4875e39abd1e	834	"4: \n\t"
saranieves92	1:4875e39abd1e	835
saranieves92	1:4875e39abd1e	836	"adds %[c0], %[t0] \n\t" /* add low word to c0 */
saranieves92	1:4875e39abd1e	837	"adcs %[c1], %[t1] \n\t" /* add high word to c1, including carry */
saranieves92	1:4875e39abd1e	838	"adc %[c2], #0 \n\t" /* add carry to c2 */
saranieves92	1:4875e39abd1e	839
saranieves92	1:4875e39abd1e	840	"adds %[i], #4 \n\t" /* i += 4 */
saranieves92	1:4875e39abd1e	841	"cmp %[i], %[k] \n\t" /* i <= k? */
saranieves92	1:4875e39abd1e	842	"bge 5f \n\t" /* if not, exit the loop */
saranieves92	1:4875e39abd1e	843	"subs %[tt], %[k], %[i] \n\t" /* tt = k-i */
saranieves92	1:4875e39abd1e	844	"cmp %[i], %[tt] \n\t" /* i <= k-i? */
saranieves92	1:4875e39abd1e	845	"ble 3b \n\t" /* if so, continue looping */
saranieves92	1:4875e39abd1e	846
saranieves92	1:4875e39abd1e	847	"5: \n\t" /* end inner loop */
saranieves92	1:4875e39abd1e	848
saranieves92	1:4875e39abd1e	849	"str %[c0], [%[result], %[k]] \n\t" /* p_result[k] = c0 */
saranieves92	1:4875e39abd1e	850	"mov %[c0], %[c1] \n\t" /* c0 = c1 */
saranieves92	1:4875e39abd1e	851	"mov %[c1], %[c2] \n\t" /* c1 = c2 */
saranieves92	1:4875e39abd1e	852	"movs %[c2], #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	853	"adds %[k], #4 \n\t" /* k += 4 */
saranieves92	1:4875e39abd1e	854	"cmp %[k], %[eccd] \n\t" /* k < NUM_ECC_DIGITS (times 4) ? */
saranieves92	1:4875e39abd1e	855	"blt 1b \n\t" /* if not, loop back, start with i = 0 */
saranieves92	1:4875e39abd1e	856	"cmp %[k], %[eccd2m1] \n\t" /* k < NUM_ECC_DIGITS * 2 - 1 (times 4) ? */
saranieves92	1:4875e39abd1e	857	"blt 2b \n\t" /* if not, loop back, start with i = (k+1) - NUM_ECC_DIGITS */
saranieves92	1:4875e39abd1e	858	/* end outer loop */
saranieves92	1:4875e39abd1e	859
saranieves92	1:4875e39abd1e	860	"str %[c0], [%[result], %[k]] \n\t" /* p_result[NUM_ECC_DIGITS * 2 - 1] = c0 */
saranieves92	1:4875e39abd1e	861	#if (ECC_ASM != ecc_asm_thumb2)
saranieves92	1:4875e39abd1e	862	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	863	#endif
saranieves92	1:4875e39abd1e	864	: [c0] "+r" (c0), [c1] "+r" (c1), [c2] "+r" (c2), [k] "+r" (k), [i] "=&r" (i), [tt] "=&r" (tt), [t0] "=&r" (t0), [t1] "=&r" (t1)
saranieves92	1:4875e39abd1e	865	: [result] "r" (p_result), [left] "r" (p_left),
saranieves92	1:4875e39abd1e	866	[eccd] "I" (NUM_ECC_DIGITS * 4), [eccdm1] "I" ((NUM_ECC_DIGITS-1) * 4), [eccd2m1] "I" ((NUM_ECC_DIGITS * 2 - 1) * 4)
saranieves92	1:4875e39abd1e	867	: "cc", "memory"
saranieves92	1:4875e39abd1e	868	);
saranieves92	1:4875e39abd1e	869
saranieves92	1:4875e39abd1e	870	#elif (ECC_ASM == ecc_asm_thumb)
saranieves92	1:4875e39abd1e	871
saranieves92	1:4875e39abd1e	872	register uint32_t *r0 asm("r0") = p_result;
saranieves92	1:4875e39abd1e	873	register uint32_t *r1 asm("r1") = p_left;
saranieves92	1:4875e39abd1e	874
saranieves92	1:4875e39abd1e	875	asm volatile (
saranieves92	1:4875e39abd1e	876	".syntax unified \n\t"
saranieves92	1:4875e39abd1e	877	"movs r2, #0 \n\t" /* c0 = 0 */
saranieves92	1:4875e39abd1e	878	"movs r3, #0 \n\t" /* c1 = 0 */
saranieves92	1:4875e39abd1e	879	"movs r4, #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	880	"movs r5, #0 \n\t" /* k = 0 */
saranieves92	1:4875e39abd1e	881
saranieves92	1:4875e39abd1e	882	"push {r0} \n\t" /* keep p_result on the stack */
saranieves92	1:4875e39abd1e	883
saranieves92	1:4875e39abd1e	884	"1: \n\t" /* outer loop (k < NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	885	"movs r6, #0 \n\t" /* r6 = i = 0 */
saranieves92	1:4875e39abd1e	886	"b 3f \n\t"
saranieves92	1:4875e39abd1e	887
saranieves92	1:4875e39abd1e	888	"2: \n\t" /* outer loop (k >= NUM_ECC_DIGITS) */
saranieves92	1:4875e39abd1e	889	"movs r6, r5 \n\t" /* r6 = k */
saranieves92	1:4875e39abd1e	890	"subs r6, %[eccdm1] \n\t" /* r6 = i = k - (NUM_ECC_DIGITS - 1) (times 4) */
saranieves92	1:4875e39abd1e	891
saranieves92	1:4875e39abd1e	892	"3: \n\t" /* inner loop */
saranieves92	1:4875e39abd1e	893	"push {r2, r3, r4, r5} \n\t" /* push things, r2 (c0) is at the top of stack. */
saranieves92	1:4875e39abd1e	894	"subs r7, r5, r6 \n\t" /* r7 = k-i */
saranieves92	1:4875e39abd1e	895
saranieves92	1:4875e39abd1e	896	"ldr r3, [r1, r7] \n\t" /* r3 = p_left[k-i] */
saranieves92	1:4875e39abd1e	897	"ldr r0, [r1, r6] \n\t" /* r0 = p_left[i] */
saranieves92	1:4875e39abd1e	898
saranieves92	1:4875e39abd1e	899	"lsrs r2, r0, #16 \n\t" /* r2 = a1 */
saranieves92	1:4875e39abd1e	900	"uxth r0, r0 \n\t" /* r0 = a0 */
saranieves92	1:4875e39abd1e	901
saranieves92	1:4875e39abd1e	902	"lsrs r4, r3, #16 \n\t" /* r4 = b1 */
saranieves92	1:4875e39abd1e	903	"uxth r3, r3 \n\t" /* r3 = b0 */
saranieves92	1:4875e39abd1e	904
saranieves92	1:4875e39abd1e	905	"movs r5, r2 \n\t" /* r5 = a1 */
saranieves92	1:4875e39abd1e	906	"muls r5, r4, r5 \n\t" /* r5 = a1b1 /
saranieves92	1:4875e39abd1e	907	"muls r2, r3, r2 \n\t" /* r2 = b0a1 /
saranieves92	1:4875e39abd1e	908	"muls r4, r0, r4 \n\t" /* r4 = a0b1 /
saranieves92	1:4875e39abd1e	909	"muls r0, r3, r0 \n\t" /* r0 = a0b0 /
saranieves92	1:4875e39abd1e	910
saranieves92	1:4875e39abd1e	911	"movs r3, #0 \n\t" /* r3 = 0 */
saranieves92	1:4875e39abd1e	912	"adds r2, r4 \n\t" /* r2 = b0a1 + a0b1 */
saranieves92	1:4875e39abd1e	913	"adcs r3, r3 \n\t" /* r3 = carry */
saranieves92	1:4875e39abd1e	914	"lsls r3, #16 \n\t" /* r3 = carry << 16 */
saranieves92	1:4875e39abd1e	915	"adds r5, r3 \n\t" /* r5 = a1b1 + carry /
saranieves92	1:4875e39abd1e	916
saranieves92	1:4875e39abd1e	917	"lsls r3, r2, #16 \n\t" /* r3 = (b0a1 + a0b1) << 16 */
saranieves92	1:4875e39abd1e	918	"lsrs r2, #16 \n\t" /* r2 = (b0a1 + a0b1) >> 16 */
saranieves92	1:4875e39abd1e	919	"adds r0, r3 \n\t" /* r0 = low word = a0b0 + ((b0a1 + a0b1) << 16) /
saranieves92	1:4875e39abd1e	920	"adcs r5, r2 \n\t" /* r5 = high word = a1b1 + carry + ((b0a1 + a0b1) >> 16) /
saranieves92	1:4875e39abd1e	921
saranieves92	1:4875e39abd1e	922	"movs r3, #0 \n\t" /* r3 = 0 */
saranieves92	1:4875e39abd1e	923	"cmp r6, r7 \n\t" /* (i < k-i) ? */
saranieves92	1:4875e39abd1e	924	"mov r7, r3 \n\t" /* r7 = 0 (does not affect condition)*/
saranieves92	1:4875e39abd1e	925	"bge 4f \n\t" /* if i >= k-i, skip */
saranieves92	1:4875e39abd1e	926	"lsls r5, #1 \n\t" /* high word << 1 */
saranieves92	1:4875e39abd1e	927	"adcs r7, r3 \n\t" /* r7 = carry bit for c2 */
saranieves92	1:4875e39abd1e	928	"lsls r0, #1 \n\t" /* low word << 1 */
saranieves92	1:4875e39abd1e	929	"adcs r5, r3 \n\t" /* add carry from shift to high word */
saranieves92	1:4875e39abd1e	930
saranieves92	1:4875e39abd1e	931	"4: \n\t"
saranieves92	1:4875e39abd1e	932	"pop {r2, r3, r4} \n\t" /* r2 = c0, r3 = c1, r4 = c2 */
saranieves92	1:4875e39abd1e	933	"adds r2, r0 \n\t" /* add low word to c0 */
saranieves92	1:4875e39abd1e	934	"adcs r3, r5 \n\t" /* add high word to c1, including carry */
saranieves92	1:4875e39abd1e	935	"movs r0, #0 \n\t" /* r0 = 0 (does not affect carry bit) */
saranieves92	1:4875e39abd1e	936	"adcs r4, r0 \n\t" /* add carry to c2 */
saranieves92	1:4875e39abd1e	937	"adds r4, r7 \n\t" /* add carry from doubling (if any) */
saranieves92	1:4875e39abd1e	938
saranieves92	1:4875e39abd1e	939	"pop {r5} \n\t" /* r5 = k */
saranieves92	1:4875e39abd1e	940
saranieves92	1:4875e39abd1e	941	"adds r6, #4 \n\t" /* i += 4 */
saranieves92	1:4875e39abd1e	942	"cmp r6, r5 \n\t" /* i <= k? */
saranieves92	1:4875e39abd1e	943	"bge 5f \n\t" /* if not, exit the loop */
saranieves92	1:4875e39abd1e	944	"subs r7, r5, r6 \n\t" /* r7 = k-i */
saranieves92	1:4875e39abd1e	945	"cmp r6, r7 \n\t" /* i <= k-i? */
saranieves92	1:4875e39abd1e	946	"ble 3b \n\t" /* if so, continue looping */
saranieves92	1:4875e39abd1e	947
saranieves92	1:4875e39abd1e	948	"5: \n\t" /* end inner loop */
saranieves92	1:4875e39abd1e	949
saranieves92	1:4875e39abd1e	950	"ldr r0, [sp, #0] \n\t" /* r0 = p_result */
saranieves92	1:4875e39abd1e	951
saranieves92	1:4875e39abd1e	952	"str r2, [r0, r5] \n\t" /* p_result[k] = c0 */
saranieves92	1:4875e39abd1e	953	"mov r2, r3 \n\t" /* c0 = c1 */
saranieves92	1:4875e39abd1e	954	"mov r3, r4 \n\t" /* c1 = c2 */
saranieves92	1:4875e39abd1e	955	"movs r4, #0 \n\t" /* c2 = 0 */
saranieves92	1:4875e39abd1e	956	"adds r5, #4 \n\t" /* k += 4 */
saranieves92	1:4875e39abd1e	957	"cmp r5, %[eccd] \n\t" /* k < NUM_ECC_DIGITS (times 4) ? */
saranieves92	1:4875e39abd1e	958	"blt 1b \n\t" /* if not, loop back, start with i = 0 */
saranieves92	1:4875e39abd1e	959	"cmp r5, %[eccd2m1] \n\t" /* k < NUM_ECC_DIGITS * 2 - 1 (times 4) ? */
saranieves92	1:4875e39abd1e	960	"blt 2b \n\t" /* if not, loop back, start with i = (k+1) - NUM_ECC_DIGITS */
saranieves92	1:4875e39abd1e	961	/* end outer loop */
saranieves92	1:4875e39abd1e	962
saranieves92	1:4875e39abd1e	963	"str r2, [r0, r5] \n\t" /* p_result[NUM_ECC_DIGITS * 2 - 1] = c0 */
saranieves92	1:4875e39abd1e	964	"pop {r0} \n\t" /* pop p_result off the stack */
saranieves92	1:4875e39abd1e	965
saranieves92	1:4875e39abd1e	966	".syntax divided \n\t"
saranieves92	1:4875e39abd1e	967	: [r0] "+l" (r0), [r1] "+l" (r1)
saranieves92	1:4875e39abd1e	968	: [eccd] "I" (NUM_ECC_DIGITS * 4), [eccdm1] "I" ((NUM_ECC_DIGITS-1) * 4), [eccd2m1] "I" ((NUM_ECC_DIGITS * 2 - 1) * 4)
saranieves92	1:4875e39abd1e	969	: "r2", "r3", "r4", "r5", "r6", "r7", "cc", "memory"
saranieves92	1:4875e39abd1e	970	);
saranieves92	1:4875e39abd1e	971
saranieves92	1:4875e39abd1e	972	#else
saranieves92	1:4875e39abd1e	973
saranieves92	1:4875e39abd1e	974	uint64_t r01 = 0;
saranieves92	1:4875e39abd1e	975	uint32_t r2 = 0;
saranieves92	1:4875e39abd1e	976
saranieves92	1:4875e39abd1e	977	uint i, k;
saranieves92	1:4875e39abd1e	978	for(k=0; k < NUM_ECC_DIGITS*2 - 1; ++k)
saranieves92	1:4875e39abd1e	979	{
saranieves92	1:4875e39abd1e	980	uint l_min = (k < NUM_ECC_DIGITS ? 0 : (k + 1) - NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	981	for(i=l_min; i<=k && i<=k-i; ++i)
saranieves92	1:4875e39abd1e	982	{
saranieves92	1:4875e39abd1e	983	uint64_t l_product = (uint64_t)p_left[i] * p_left[k-i];
saranieves92	1:4875e39abd1e	984	if(i < k-i)
saranieves92	1:4875e39abd1e	985	{
saranieves92	1:4875e39abd1e	986	r2 += l_product >> 63;
saranieves92	1:4875e39abd1e	987	l_product *= 2;
saranieves92	1:4875e39abd1e	988	}
saranieves92	1:4875e39abd1e	989	r01 += l_product;
saranieves92	1:4875e39abd1e	990	r2 += (r01 < l_product);
saranieves92	1:4875e39abd1e	991	}
saranieves92	1:4875e39abd1e	992	p_result[k] = (uint32_t)r01;
saranieves92	1:4875e39abd1e	993	r01 = (r01 >> 32) \| (((uint64_t)r2) << 32);
saranieves92	1:4875e39abd1e	994	r2 = 0;
saranieves92	1:4875e39abd1e	995	}
saranieves92	1:4875e39abd1e	996
saranieves92	1:4875e39abd1e	997	p_result[NUM_ECC_DIGITS*2 - 1] = (uint32_t)r01;
saranieves92	1:4875e39abd1e	998	#endif
saranieves92	1:4875e39abd1e	999	}
saranieves92	1:4875e39abd1e	1000
saranieves92	1:4875e39abd1e	1001	/* Computes p_result = p_left^2 % curve_p. */
saranieves92	1:4875e39abd1e	1002	static void vli_modSquare_fast(uint32_t p_result, const uint32_t p_left)
saranieves92	1:4875e39abd1e	1003	{
saranieves92	1:4875e39abd1e	1004	uint32_t l_product[2 * NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1005	vli_square(l_product, p_left);
saranieves92	1:4875e39abd1e	1006	vli_mmod_fast(p_result, l_product);
saranieves92	1:4875e39abd1e	1007	}
saranieves92	1:4875e39abd1e	1008
saranieves92	1:4875e39abd1e	1009	#else /* ECC_SQUARE_FUNC */
saranieves92	1:4875e39abd1e	1010
saranieves92	1:4875e39abd1e	1011	#define vli_square(result, left, size) vli_mult((result), (left), (left), (size))
saranieves92	1:4875e39abd1e	1012	#define vli_modSquare_fast(result, left) vli_modMult_fast((result), (left), (left))
saranieves92	1:4875e39abd1e	1013
saranieves92	1:4875e39abd1e	1014	#endif /* ECC_SQUARE_FUNC */
saranieves92	1:4875e39abd1e	1015
saranieves92	1:4875e39abd1e	1016	#define EVEN(vli) (!(vli[0] & 1))
saranieves92	1:4875e39abd1e	1017	/* Computes p_result = (1 / p_input) % p_mod. All VLIs are the same size.
saranieves92	1:4875e39abd1e	1018	See "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
saranieves92	1:4875e39abd1e	1019	https://labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf */
saranieves92	1:4875e39abd1e	1020	static void vli_modInv(uint32_t p_result, const uint32_t p_input, const uint32_t *p_mod)
saranieves92	1:4875e39abd1e	1021	{
saranieves92	1:4875e39abd1e	1022	uint32_t a[NUM_ECC_DIGITS], b[NUM_ECC_DIGITS], u[NUM_ECC_DIGITS], v[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1023	uint32_t l_carry;
saranieves92	1:4875e39abd1e	1024
saranieves92	1:4875e39abd1e	1025	vli_set(a, p_input);
saranieves92	1:4875e39abd1e	1026	vli_set(b, p_mod);
saranieves92	1:4875e39abd1e	1027	vli_clear(u);
saranieves92	1:4875e39abd1e	1028	u[0] = 1;
saranieves92	1:4875e39abd1e	1029	vli_clear(v);
saranieves92	1:4875e39abd1e	1030
saranieves92	1:4875e39abd1e	1031	int l_cmpResult;
saranieves92	1:4875e39abd1e	1032	while((l_cmpResult = vli_cmp(a, b)) != 0)
saranieves92	1:4875e39abd1e	1033	{
saranieves92	1:4875e39abd1e	1034	l_carry = 0;
saranieves92	1:4875e39abd1e	1035	if(EVEN(a))
saranieves92	1:4875e39abd1e	1036	{
saranieves92	1:4875e39abd1e	1037	vli_rshift1(a);
saranieves92	1:4875e39abd1e	1038	if(!EVEN(u))
saranieves92	1:4875e39abd1e	1039	{
saranieves92	1:4875e39abd1e	1040	l_carry = vli_add(u, u, p_mod);
saranieves92	1:4875e39abd1e	1041	}
saranieves92	1:4875e39abd1e	1042	vli_rshift1(u);
saranieves92	1:4875e39abd1e	1043	if(l_carry)
saranieves92	1:4875e39abd1e	1044	{
saranieves92	1:4875e39abd1e	1045	u[NUM_ECC_DIGITS-1] \|= 0x80000000;
saranieves92	1:4875e39abd1e	1046	}
saranieves92	1:4875e39abd1e	1047	}
saranieves92	1:4875e39abd1e	1048	else if(EVEN(b))
saranieves92	1:4875e39abd1e	1049	{
saranieves92	1:4875e39abd1e	1050	vli_rshift1(b);
saranieves92	1:4875e39abd1e	1051	if(!EVEN(v))
saranieves92	1:4875e39abd1e	1052	{
saranieves92	1:4875e39abd1e	1053	l_carry = vli_add(v, v, p_mod);
saranieves92	1:4875e39abd1e	1054	}
saranieves92	1:4875e39abd1e	1055	vli_rshift1(v);
saranieves92	1:4875e39abd1e	1056	if(l_carry)
saranieves92	1:4875e39abd1e	1057	{
saranieves92	1:4875e39abd1e	1058	v[NUM_ECC_DIGITS-1] \|= 0x80000000;
saranieves92	1:4875e39abd1e	1059	}
saranieves92	1:4875e39abd1e	1060	}
saranieves92	1:4875e39abd1e	1061	else if(l_cmpResult > 0)
saranieves92	1:4875e39abd1e	1062	{
saranieves92	1:4875e39abd1e	1063	vli_sub(a, a, b);
saranieves92	1:4875e39abd1e	1064	vli_rshift1(a);
saranieves92	1:4875e39abd1e	1065	if(vli_cmp(u, v) < 0)
saranieves92	1:4875e39abd1e	1066	{
saranieves92	1:4875e39abd1e	1067	vli_add(u, u, p_mod);
saranieves92	1:4875e39abd1e	1068	}
saranieves92	1:4875e39abd1e	1069	vli_sub(u, u, v);
saranieves92	1:4875e39abd1e	1070	if(!EVEN(u))
saranieves92	1:4875e39abd1e	1071	{
saranieves92	1:4875e39abd1e	1072	l_carry = vli_add(u, u, p_mod);
saranieves92	1:4875e39abd1e	1073	}
saranieves92	1:4875e39abd1e	1074	vli_rshift1(u);
saranieves92	1:4875e39abd1e	1075	if(l_carry)
saranieves92	1:4875e39abd1e	1076	{
saranieves92	1:4875e39abd1e	1077	u[NUM_ECC_DIGITS-1] \|= 0x80000000;
saranieves92	1:4875e39abd1e	1078	}
saranieves92	1:4875e39abd1e	1079	}
saranieves92	1:4875e39abd1e	1080	else
saranieves92	1:4875e39abd1e	1081	{
saranieves92	1:4875e39abd1e	1082	vli_sub(b, b, a);
saranieves92	1:4875e39abd1e	1083	vli_rshift1(b);
saranieves92	1:4875e39abd1e	1084	if(vli_cmp(v, u) < 0)
saranieves92	1:4875e39abd1e	1085	{
saranieves92	1:4875e39abd1e	1086	vli_add(v, v, p_mod);
saranieves92	1:4875e39abd1e	1087	}
saranieves92	1:4875e39abd1e	1088	vli_sub(v, v, u);
saranieves92	1:4875e39abd1e	1089	if(!EVEN(v))
saranieves92	1:4875e39abd1e	1090	{
saranieves92	1:4875e39abd1e	1091	l_carry = vli_add(v, v, p_mod);
saranieves92	1:4875e39abd1e	1092	}
saranieves92	1:4875e39abd1e	1093	vli_rshift1(v);
saranieves92	1:4875e39abd1e	1094	if(l_carry)
saranieves92	1:4875e39abd1e	1095	{
saranieves92	1:4875e39abd1e	1096	v[NUM_ECC_DIGITS-1] \|= 0x80000000;
saranieves92	1:4875e39abd1e	1097	}
saranieves92	1:4875e39abd1e	1098	}
saranieves92	1:4875e39abd1e	1099	}
saranieves92	1:4875e39abd1e	1100
saranieves92	1:4875e39abd1e	1101	vli_set(p_result, u);
saranieves92	1:4875e39abd1e	1102	}
saranieves92	1:4875e39abd1e	1103
saranieves92	1:4875e39abd1e	1104	/* ------ Point operations ------ */
saranieves92	1:4875e39abd1e	1105
saranieves92	1:4875e39abd1e	1106	/* Returns 1 if p_point is the point at infinity, 0 otherwise. */
saranieves92	1:4875e39abd1e	1107	static int EccPoint_isZero(const EccPoint *p_point)
saranieves92	1:4875e39abd1e	1108	{
saranieves92	1:4875e39abd1e	1109	return (vli_isZero(p_point->x) && vli_isZero(p_point->y));
saranieves92	1:4875e39abd1e	1110	}
saranieves92	1:4875e39abd1e	1111
saranieves92	1:4875e39abd1e	1112	/* Point multiplication algorithm using Montgomery's ladder with co-Z coordinates.
saranieves92	1:4875e39abd1e	1113	From http://eprint.iacr.org/2011/338.pdf
saranieves92	1:4875e39abd1e	1114	*/
saranieves92	1:4875e39abd1e	1115
saranieves92	1:4875e39abd1e	1116	/* Double in place */
saranieves92	1:4875e39abd1e	1117	#if (ECC_CURVE == secp256k1)
saranieves92	1:4875e39abd1e	1118	static void EccPoint_double_jacobian(uint32_t X1, uint32_t Y1, uint32_t *Z1)
saranieves92	1:4875e39abd1e	1119	{
saranieves92	1:4875e39abd1e	1120	/* t1 = X, t2 = Y, t3 = Z */
saranieves92	1:4875e39abd1e	1121	uint32_t t4[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1122	uint32_t t5[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1123
saranieves92	1:4875e39abd1e	1124	if(vli_isZero(Z1))
saranieves92	1:4875e39abd1e	1125	{
saranieves92	1:4875e39abd1e	1126	return;
saranieves92	1:4875e39abd1e	1127	}
saranieves92	1:4875e39abd1e	1128
saranieves92	1:4875e39abd1e	1129	vli_modSquare_fast(t5, Y1); /* t5 = y1^2 */
saranieves92	1:4875e39abd1e	1130	vli_modMult_fast(t4, X1, t5); /* t4 = x1y1^2 = A /
saranieves92	1:4875e39abd1e	1131	vli_modSquare_fast(X1, X1); /* t1 = x1^2 */
saranieves92	1:4875e39abd1e	1132	vli_modSquare_fast(t5, t5); /* t5 = y1^4 */
saranieves92	1:4875e39abd1e	1133	vli_modMult_fast(Z1, Y1, Z1); /* t3 = y1z1 = z3 /
saranieves92	1:4875e39abd1e	1134
saranieves92	1:4875e39abd1e	1135	vli_modAdd(Y1, X1, X1, curve_p); /* t2 = 2x1^2 /
saranieves92	1:4875e39abd1e	1136	vli_modAdd(Y1, Y1, X1, curve_p); /* t2 = 3x1^2 /
saranieves92	1:4875e39abd1e	1137	if(vli_testBit(Y1, 0))
saranieves92	1:4875e39abd1e	1138	{
saranieves92	1:4875e39abd1e	1139	uint32_t l_carry = vli_add(Y1, Y1, curve_p);
saranieves92	1:4875e39abd1e	1140	vli_rshift1(Y1);
saranieves92	1:4875e39abd1e	1141	Y1[NUM_ECC_DIGITS-1] \|= l_carry << 31;
saranieves92	1:4875e39abd1e	1142	}
saranieves92	1:4875e39abd1e	1143	else
saranieves92	1:4875e39abd1e	1144	{
saranieves92	1:4875e39abd1e	1145	vli_rshift1(Y1);
saranieves92	1:4875e39abd1e	1146	}
saranieves92	1:4875e39abd1e	1147	/* t2 = 3/2(x1^2) = B /
saranieves92	1:4875e39abd1e	1148
saranieves92	1:4875e39abd1e	1149	vli_modSquare_fast(X1, Y1); /* t1 = B^2 */
saranieves92	1:4875e39abd1e	1150	vli_modSub(X1, X1, t4, curve_p); /* t1 = B^2 - A */
saranieves92	1:4875e39abd1e	1151	vli_modSub(X1, X1, t4, curve_p); /* t1 = B^2 - 2A = x3 */
saranieves92	1:4875e39abd1e	1152
saranieves92	1:4875e39abd1e	1153	vli_modSub(t4, t4, X1, curve_p); /* t4 = A - x3 */
saranieves92	1:4875e39abd1e	1154	vli_modMult_fast(Y1, Y1, t4); /* t2 = B * (A - x3) */
saranieves92	1:4875e39abd1e	1155	vli_modSub(Y1, Y1, t5, curve_p); /* t2 = B * (A - x3) - y1^4 = y3 */
saranieves92	1:4875e39abd1e	1156	}
saranieves92	1:4875e39abd1e	1157	#else
saranieves92	1:4875e39abd1e	1158	static void EccPoint_double_jacobian(uint32_t X1, uint32_t Y1, uint32_t *Z1)
saranieves92	1:4875e39abd1e	1159	{
saranieves92	1:4875e39abd1e	1160	/* t1 = X, t2 = Y, t3 = Z */
saranieves92	1:4875e39abd1e	1161	uint32_t t4[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1162	uint32_t t5[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1163
saranieves92	1:4875e39abd1e	1164	if(vli_isZero(Z1))
saranieves92	1:4875e39abd1e	1165	{
saranieves92	1:4875e39abd1e	1166	return;
saranieves92	1:4875e39abd1e	1167	}
saranieves92	1:4875e39abd1e	1168
saranieves92	1:4875e39abd1e	1169	vli_modSquare_fast(t4, Y1); /* t4 = y1^2 */
saranieves92	1:4875e39abd1e	1170	vli_modMult_fast(t5, X1, t4); /* t5 = x1y1^2 = A /
saranieves92	1:4875e39abd1e	1171	vli_modSquare_fast(t4, t4); /* t4 = y1^4 */
saranieves92	1:4875e39abd1e	1172	vli_modMult_fast(Y1, Y1, Z1); /* t2 = y1z1 = z3 /
saranieves92	1:4875e39abd1e	1173	vli_modSquare_fast(Z1, Z1); /* t3 = z1^2 */
saranieves92	1:4875e39abd1e	1174
saranieves92	1:4875e39abd1e	1175	vli_modAdd(X1, X1, Z1, curve_p); /* t1 = x1 + z1^2 */
saranieves92	1:4875e39abd1e	1176	vli_modAdd(Z1, Z1, Z1, curve_p); /* t3 = 2z1^2 /
saranieves92	1:4875e39abd1e	1177	vli_modSub(Z1, X1, Z1, curve_p); /* t3 = x1 - z1^2 */
saranieves92	1:4875e39abd1e	1178	vli_modMult_fast(X1, X1, Z1); /* t1 = x1^2 - z1^4 */
saranieves92	1:4875e39abd1e	1179
saranieves92	1:4875e39abd1e	1180	vli_modAdd(Z1, X1, X1, curve_p); /* t3 = 2(x1^2 - z1^4) /
saranieves92	1:4875e39abd1e	1181	vli_modAdd(X1, X1, Z1, curve_p); /* t1 = 3(x1^2 - z1^4) /
saranieves92	1:4875e39abd1e	1182	if(vli_testBit(X1, 0))
saranieves92	1:4875e39abd1e	1183	{
saranieves92	1:4875e39abd1e	1184	uint32_t l_carry = vli_add(X1, X1, curve_p);
saranieves92	1:4875e39abd1e	1185	vli_rshift1(X1);
saranieves92	1:4875e39abd1e	1186	X1[NUM_ECC_DIGITS-1] \|= l_carry << 31;
saranieves92	1:4875e39abd1e	1187	}
saranieves92	1:4875e39abd1e	1188	else
saranieves92	1:4875e39abd1e	1189	{
saranieves92	1:4875e39abd1e	1190	vli_rshift1(X1);
saranieves92	1:4875e39abd1e	1191	}
saranieves92	1:4875e39abd1e	1192	/* t1 = 3/2(x1^2 - z1^4) = B /
saranieves92	1:4875e39abd1e	1193
saranieves92	1:4875e39abd1e	1194	vli_modSquare_fast(Z1, X1); /* t3 = B^2 */
saranieves92	1:4875e39abd1e	1195	vli_modSub(Z1, Z1, t5, curve_p); /* t3 = B^2 - A */
saranieves92	1:4875e39abd1e	1196	vli_modSub(Z1, Z1, t5, curve_p); /* t3 = B^2 - 2A = x3 */
saranieves92	1:4875e39abd1e	1197	vli_modSub(t5, t5, Z1, curve_p); /* t5 = A - x3 */
saranieves92	1:4875e39abd1e	1198	vli_modMult_fast(X1, X1, t5); /* t1 = B * (A - x3) */
saranieves92	1:4875e39abd1e	1199	vli_modSub(t4, X1, t4, curve_p); /* t4 = B * (A - x3) - y1^4 = y3 */
saranieves92	1:4875e39abd1e	1200
saranieves92	1:4875e39abd1e	1201	vli_set(X1, Z1);
saranieves92	1:4875e39abd1e	1202	vli_set(Z1, Y1);
saranieves92	1:4875e39abd1e	1203	vli_set(Y1, t4);
saranieves92	1:4875e39abd1e	1204	}
saranieves92	1:4875e39abd1e	1205	#endif
saranieves92	1:4875e39abd1e	1206
saranieves92	1:4875e39abd1e	1207	/* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
saranieves92	1:4875e39abd1e	1208	static void apply_z(uint32_t X1, uint32_t Y1, uint32_t *Z)
saranieves92	1:4875e39abd1e	1209	{
saranieves92	1:4875e39abd1e	1210	uint32_t t1[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1211
saranieves92	1:4875e39abd1e	1212	vli_modSquare_fast(t1, Z); /* z^2 */
saranieves92	1:4875e39abd1e	1213	vli_modMult_fast(X1, X1, t1); /* x1 * z^2 */
saranieves92	1:4875e39abd1e	1214	vli_modMult_fast(t1, t1, Z); /* z^3 */
saranieves92	1:4875e39abd1e	1215	vli_modMult_fast(Y1, Y1, t1); /* y1 * z^3 */
saranieves92	1:4875e39abd1e	1216	}
saranieves92	1:4875e39abd1e	1217
saranieves92	1:4875e39abd1e	1218	/* P = (x1, y1) => 2P, (x2, y2) => P' */
saranieves92	1:4875e39abd1e	1219	static void XYcZ_initial_double(uint32_t X1, uint32_t Y1, uint32_t X2, uint32_t Y2, const uint32_t *p_initialZ)
saranieves92	1:4875e39abd1e	1220	{
saranieves92	1:4875e39abd1e	1221	uint32_t z[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1222
saranieves92	1:4875e39abd1e	1223	vli_set(X2, X1);
saranieves92	1:4875e39abd1e	1224	vli_set(Y2, Y1);
saranieves92	1:4875e39abd1e	1225
saranieves92	1:4875e39abd1e	1226	vli_clear(z);
saranieves92	1:4875e39abd1e	1227	z[0] = 1;
saranieves92	1:4875e39abd1e	1228	if(p_initialZ)
saranieves92	1:4875e39abd1e	1229	{
saranieves92	1:4875e39abd1e	1230	vli_set(z, p_initialZ);
saranieves92	1:4875e39abd1e	1231	}
saranieves92	1:4875e39abd1e	1232	apply_z(X1, Y1, z);
saranieves92	1:4875e39abd1e	1233
saranieves92	1:4875e39abd1e	1234	EccPoint_double_jacobian(X1, Y1, z);
saranieves92	1:4875e39abd1e	1235
saranieves92	1:4875e39abd1e	1236	apply_z(X2, Y2, z);
saranieves92	1:4875e39abd1e	1237	}
saranieves92	1:4875e39abd1e	1238
saranieves92	1:4875e39abd1e	1239	/* Input P = (x1, y1, Z), Q = (x2, y2, Z)
saranieves92	1:4875e39abd1e	1240	Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3)
saranieves92	1:4875e39abd1e	1241	or P => P', Q => P + Q
saranieves92	1:4875e39abd1e	1242	*/
saranieves92	1:4875e39abd1e	1243	static void XYcZ_add(uint32_t X1, uint32_t Y1, uint32_t X2, uint32_t Y2)
saranieves92	1:4875e39abd1e	1244	{
saranieves92	1:4875e39abd1e	1245	/* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
saranieves92	1:4875e39abd1e	1246	uint32_t t5[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1247
saranieves92	1:4875e39abd1e	1248	vli_modSub(t5, X2, X1, curve_p); /* t5 = x2 - x1 */
saranieves92	1:4875e39abd1e	1249	vli_modSquare_fast(t5, t5); /* t5 = (x2 - x1)^2 = A */
saranieves92	1:4875e39abd1e	1250	vli_modMult_fast(X1, X1, t5); /* t1 = x1A = B /
saranieves92	1:4875e39abd1e	1251	vli_modMult_fast(X2, X2, t5); /* t3 = x2A = C /
saranieves92	1:4875e39abd1e	1252	vli_modSub(Y2, Y2, Y1, curve_p); /* t4 = y2 - y1 */
saranieves92	1:4875e39abd1e	1253	vli_modSquare_fast(t5, Y2); /* t5 = (y2 - y1)^2 = D */
saranieves92	1:4875e39abd1e	1254
saranieves92	1:4875e39abd1e	1255	vli_modSub(t5, t5, X1, curve_p); /* t5 = D - B */
saranieves92	1:4875e39abd1e	1256	vli_modSub(t5, t5, X2, curve_p); /* t5 = D - B - C = x3 */
saranieves92	1:4875e39abd1e	1257	vli_modSub(X2, X2, X1, curve_p); /* t3 = C - B */
saranieves92	1:4875e39abd1e	1258	vli_modMult_fast(Y1, Y1, X2); /* t2 = y1(C - B) /
saranieves92	1:4875e39abd1e	1259	vli_modSub(X2, X1, t5, curve_p); /* t3 = B - x3 */
saranieves92	1:4875e39abd1e	1260	vli_modMult_fast(Y2, Y2, X2); /* t4 = (y2 - y1)(B - x3) /
saranieves92	1:4875e39abd1e	1261	vli_modSub(Y2, Y2, Y1, curve_p); /* t4 = y3 */
saranieves92	1:4875e39abd1e	1262
saranieves92	1:4875e39abd1e	1263	vli_set(X2, t5);
saranieves92	1:4875e39abd1e	1264	}
saranieves92	1:4875e39abd1e	1265
saranieves92	1:4875e39abd1e	1266	/* Input P = (x1, y1, Z), Q = (x2, y2, Z)
saranieves92	1:4875e39abd1e	1267	Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
saranieves92	1:4875e39abd1e	1268	or P => P - Q, Q => P + Q
saranieves92	1:4875e39abd1e	1269	*/
saranieves92	1:4875e39abd1e	1270	static void XYcZ_addC(uint32_t X1, uint32_t Y1, uint32_t X2, uint32_t Y2)
saranieves92	1:4875e39abd1e	1271	{
saranieves92	1:4875e39abd1e	1272	/* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
saranieves92	1:4875e39abd1e	1273	uint32_t t5[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1274	uint32_t t6[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1275	uint32_t t7[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1276
saranieves92	1:4875e39abd1e	1277	vli_modSub(t5, X2, X1, curve_p); /* t5 = x2 - x1 */
saranieves92	1:4875e39abd1e	1278	vli_modSquare_fast(t5, t5); /* t5 = (x2 - x1)^2 = A */
saranieves92	1:4875e39abd1e	1279	vli_modMult_fast(X1, X1, t5); /* t1 = x1A = B /
saranieves92	1:4875e39abd1e	1280	vli_modMult_fast(X2, X2, t5); /* t3 = x2A = C /
saranieves92	1:4875e39abd1e	1281	vli_modAdd(t5, Y2, Y1, curve_p); /* t4 = y2 + y1 */
saranieves92	1:4875e39abd1e	1282	vli_modSub(Y2, Y2, Y1, curve_p); /* t4 = y2 - y1 */
saranieves92	1:4875e39abd1e	1283
saranieves92	1:4875e39abd1e	1284	vli_modSub(t6, X2, X1, curve_p); /* t6 = C - B */
saranieves92	1:4875e39abd1e	1285	vli_modMult_fast(Y1, Y1, t6); /* t2 = y1 * (C - B) */
saranieves92	1:4875e39abd1e	1286	vli_modAdd(t6, X1, X2, curve_p); /* t6 = B + C */
saranieves92	1:4875e39abd1e	1287	vli_modSquare_fast(X2, Y2); /* t3 = (y2 - y1)^2 */
saranieves92	1:4875e39abd1e	1288	vli_modSub(X2, X2, t6, curve_p); /* t3 = x3 */
saranieves92	1:4875e39abd1e	1289
saranieves92	1:4875e39abd1e	1290	vli_modSub(t7, X1, X2, curve_p); /* t7 = B - x3 */
saranieves92	1:4875e39abd1e	1291	vli_modMult_fast(Y2, Y2, t7); /* t4 = (y2 - y1)(B - x3) /
saranieves92	1:4875e39abd1e	1292	vli_modSub(Y2, Y2, Y1, curve_p); /* t4 = y3 */
saranieves92	1:4875e39abd1e	1293
saranieves92	1:4875e39abd1e	1294	vli_modSquare_fast(t7, t5); /* t7 = (y2 + y1)^2 = F */
saranieves92	1:4875e39abd1e	1295	vli_modSub(t7, t7, t6, curve_p); /* t7 = x3' */
saranieves92	1:4875e39abd1e	1296	vli_modSub(t6, t7, X1, curve_p); /* t6 = x3' - B */
saranieves92	1:4875e39abd1e	1297	vli_modMult_fast(t6, t6, t5); /* t6 = (y2 + y1)(x3' - B) /
saranieves92	1:4875e39abd1e	1298	vli_modSub(Y1, t6, Y1, curve_p); /* t2 = y3' */
saranieves92	1:4875e39abd1e	1299
saranieves92	1:4875e39abd1e	1300	vli_set(X1, t7);
saranieves92	1:4875e39abd1e	1301	}
saranieves92	1:4875e39abd1e	1302
saranieves92	1:4875e39abd1e	1303	static void EccPoint_mult(EccPoint p_result, const EccPoint p_point,
saranieves92	1:4875e39abd1e	1304	const uint32_t p_scalar, const uint32_t p_initialZ)
saranieves92	1:4875e39abd1e	1305	{
saranieves92	1:4875e39abd1e	1306	/* R0 and R1 */
saranieves92	1:4875e39abd1e	1307	uint32_t Rx[2][NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1308	uint32_t Ry[2][NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1309	uint32_t z[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1310
saranieves92	1:4875e39abd1e	1311	int i, nb;
saranieves92	1:4875e39abd1e	1312
saranieves92	1:4875e39abd1e	1313	vli_set(Rx[1], p_point->x);
saranieves92	1:4875e39abd1e	1314	vli_set(Ry[1], p_point->y);
saranieves92	1:4875e39abd1e	1315
saranieves92	1:4875e39abd1e	1316	XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], p_initialZ);
saranieves92	1:4875e39abd1e	1317
saranieves92	1:4875e39abd1e	1318	for(i = vli_numBits(p_scalar) - 2; i > 0; --i)
saranieves92	1:4875e39abd1e	1319	{
saranieves92	1:4875e39abd1e	1320	nb = !vli_testBit(p_scalar, i);
saranieves92	1:4875e39abd1e	1321	XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
saranieves92	1:4875e39abd1e	1322	XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);
saranieves92	1:4875e39abd1e	1323	}
saranieves92	1:4875e39abd1e	1324
saranieves92	1:4875e39abd1e	1325	nb = !vli_testBit(p_scalar, 0);
saranieves92	1:4875e39abd1e	1326	XYcZ_addC(Rx[1-nb], Ry[1-nb], Rx[nb], Ry[nb]);
saranieves92	1:4875e39abd1e	1327
saranieves92	1:4875e39abd1e	1328	/* Find final 1/Z value. */
saranieves92	1:4875e39abd1e	1329	vli_modSub(z, Rx[1], Rx[0], curve_p); /* X1 - X0 */
saranieves92	1:4875e39abd1e	1330	vli_modMult_fast(z, z, Ry[1-nb]); /* Yb * (X1 - X0) */
saranieves92	1:4875e39abd1e	1331	vli_modMult_fast(z, z, p_point->x); /* xP * Yb * (X1 - X0) */
saranieves92	1:4875e39abd1e	1332	vli_modInv(z, z, curve_p); /* 1 / (xP * Yb * (X1 - X0)) */
saranieves92	1:4875e39abd1e	1333	vli_modMult_fast(z, z, p_point->y); /* yP / (xP * Yb * (X1 - X0)) */
saranieves92	1:4875e39abd1e	1334	vli_modMult_fast(z, z, Rx[1-nb]); /* Xb * yP / (xP * Yb * (X1 - X0)) */
saranieves92	1:4875e39abd1e	1335	/* End 1/Z calculation */
saranieves92	1:4875e39abd1e	1336
saranieves92	1:4875e39abd1e	1337	XYcZ_add(Rx[nb], Ry[nb], Rx[1-nb], Ry[1-nb]);
saranieves92	1:4875e39abd1e	1338
saranieves92	1:4875e39abd1e	1339	apply_z(Rx[0], Ry[0], z);
saranieves92	1:4875e39abd1e	1340
saranieves92	1:4875e39abd1e	1341	vli_set(p_result->x, Rx[0]);
saranieves92	1:4875e39abd1e	1342	vli_set(p_result->y, Ry[0]);
saranieves92	1:4875e39abd1e	1343	}
saranieves92	1:4875e39abd1e	1344
saranieves92	1:4875e39abd1e	1345	int ecc_make_key(EccPoint *p_publicKey, uint32_t p_privateKey[NUM_ECC_DIGITS],
saranieves92	1:4875e39abd1e	1346	const uint32_t p_random[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1347	{
saranieves92	1:4875e39abd1e	1348	/* Make sure the private key is in the range [1, n-1].
saranieves92	1:4875e39abd1e	1349	For the supported curves, n is always large enough that we only need to subtract once at most. */
saranieves92	1:4875e39abd1e	1350	vli_set(p_privateKey, p_random);
saranieves92	1:4875e39abd1e	1351	if(vli_cmp(curve_n, p_privateKey) != 1)
saranieves92	1:4875e39abd1e	1352	{
saranieves92	1:4875e39abd1e	1353	vli_sub(p_privateKey, p_privateKey, curve_n);
saranieves92	1:4875e39abd1e	1354	}
saranieves92	1:4875e39abd1e	1355
saranieves92	1:4875e39abd1e	1356	if(vli_isZero(p_privateKey))
saranieves92	1:4875e39abd1e	1357	{
saranieves92	1:4875e39abd1e	1358	return 0; /* The private key cannot be 0 (mod p). */
saranieves92	1:4875e39abd1e	1359	}
saranieves92	1:4875e39abd1e	1360
saranieves92	1:4875e39abd1e	1361	EccPoint_mult(p_publicKey, &curve_G, p_privateKey, NULL);
saranieves92	1:4875e39abd1e	1362	return 1;
saranieves92	1:4875e39abd1e	1363	}
saranieves92	1:4875e39abd1e	1364
saranieves92	1:4875e39abd1e	1365	#if (ECC_CURVE == secp256k1)
saranieves92	1:4875e39abd1e	1366	/* Compute p_result = x^3 + b */
saranieves92	1:4875e39abd1e	1367	static void curve_x_side(uint32_t p_result[NUM_ECC_DIGITS], const uint32_t x[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1368	{
saranieves92	1:4875e39abd1e	1369	vli_modSquare_fast(p_result, x); /* r = x^2 */
saranieves92	1:4875e39abd1e	1370	vli_modMult_fast(p_result, p_result, x); /* r = x^3 */
saranieves92	1:4875e39abd1e	1371	vli_modAdd(p_result, p_result, curve_b, curve_p); /* r = x^3 + b */
saranieves92	1:4875e39abd1e	1372	}
saranieves92	1:4875e39abd1e	1373	#else
saranieves92	1:4875e39abd1e	1374	/* Compute p_result = x^3 - 3x + b */
saranieves92	1:4875e39abd1e	1375	static void curve_x_side(uint32_t p_result[NUM_ECC_DIGITS], const uint32_t x[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1376	{
saranieves92	1:4875e39abd1e	1377	uint32_t _3[NUM_ECC_DIGITS] = {3}; /* -a = 3 */
saranieves92	1:4875e39abd1e	1378
saranieves92	1:4875e39abd1e	1379	vli_modSquare_fast(p_result, x); /* r = x^2 */
saranieves92	1:4875e39abd1e	1380	vli_modSub(p_result, p_result, _3, curve_p); /* r = x^2 - 3 */
saranieves92	1:4875e39abd1e	1381	vli_modMult_fast(p_result, p_result, x); /* r = x^3 - 3x */
saranieves92	1:4875e39abd1e	1382	vli_modAdd(p_result, p_result, curve_b, curve_p); /* r = x^3 - 3x + b */
saranieves92	1:4875e39abd1e	1383	}
saranieves92	1:4875e39abd1e	1384	#endif
saranieves92	1:4875e39abd1e	1385
saranieves92	1:4875e39abd1e	1386	int ecc_valid_public_key(const EccPoint *p_publicKey)
saranieves92	1:4875e39abd1e	1387	{
saranieves92	1:4875e39abd1e	1388	uint32_t l_tmp1[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1389	uint32_t l_tmp2[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1390
saranieves92	1:4875e39abd1e	1391	if(EccPoint_isZero(p_publicKey))
saranieves92	1:4875e39abd1e	1392	{
saranieves92	1:4875e39abd1e	1393	return 0;
saranieves92	1:4875e39abd1e	1394	}
saranieves92	1:4875e39abd1e	1395
saranieves92	1:4875e39abd1e	1396	if(vli_cmp(curve_p, p_publicKey->x) != 1 \|\| vli_cmp(curve_p, p_publicKey->y) != 1)
saranieves92	1:4875e39abd1e	1397	{
saranieves92	1:4875e39abd1e	1398	return 0;
saranieves92	1:4875e39abd1e	1399	}
saranieves92	1:4875e39abd1e	1400
saranieves92	1:4875e39abd1e	1401	vli_modSquare_fast(l_tmp1, p_publicKey->y); /* tmp1 = y^2 */
saranieves92	1:4875e39abd1e	1402
saranieves92	1:4875e39abd1e	1403	curve_x_side(l_tmp2, p_publicKey->x); /* tmp2 = x^3 - 3x + b */
saranieves92	1:4875e39abd1e	1404
saranieves92	1:4875e39abd1e	1405	/* Make sure that y^2 == x^3 + ax + b */
saranieves92	1:4875e39abd1e	1406	if(vli_cmp(l_tmp1, l_tmp2) != 0)
saranieves92	1:4875e39abd1e	1407	{
saranieves92	1:4875e39abd1e	1408	return 0;
saranieves92	1:4875e39abd1e	1409	}
saranieves92	1:4875e39abd1e	1410
saranieves92	1:4875e39abd1e	1411	return 1;
saranieves92	1:4875e39abd1e	1412	}
saranieves92	1:4875e39abd1e	1413
saranieves92	1:4875e39abd1e	1414	int ecdh_shared_secret(uint32_t p_secret[NUM_ECC_DIGITS], const EccPoint *p_publicKey,
saranieves92	1:4875e39abd1e	1415	const uint32_t p_privateKey[NUM_ECC_DIGITS], const uint32_t p_random[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1416	{
saranieves92	1:4875e39abd1e	1417	EccPoint l_product;
saranieves92	1:4875e39abd1e	1418
saranieves92	1:4875e39abd1e	1419	EccPoint_mult(&l_product, p_publicKey, p_privateKey, p_random);
saranieves92	1:4875e39abd1e	1420	if(EccPoint_isZero(&l_product))
saranieves92	1:4875e39abd1e	1421	{
saranieves92	1:4875e39abd1e	1422	return 0;
saranieves92	1:4875e39abd1e	1423	}
saranieves92	1:4875e39abd1e	1424
saranieves92	1:4875e39abd1e	1425	vli_set(p_secret, l_product.x);
saranieves92	1:4875e39abd1e	1426
saranieves92	1:4875e39abd1e	1427	return 1;
saranieves92	1:4875e39abd1e	1428	}
saranieves92	1:4875e39abd1e	1429
saranieves92	1:4875e39abd1e	1430	/* -------- ECDSA code -------- */
saranieves92	1:4875e39abd1e	1431
saranieves92	1:4875e39abd1e	1432	/* Computes p_result = (p_left * p_right) % p_mod. */
saranieves92	1:4875e39abd1e	1433	static void vli_modMult(uint32_t p_result, const uint32_t p_left,
saranieves92	1:4875e39abd1e	1434	const uint32_t p_right, const uint32_t p_mod)
saranieves92	1:4875e39abd1e	1435	{
saranieves92	1:4875e39abd1e	1436	uint32_t l_product[2 * NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1437	uint32_t l_modMultiple[2 * NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1438	uint l_digitShift, l_bitShift;
saranieves92	1:4875e39abd1e	1439	uint l_productBits;
saranieves92	1:4875e39abd1e	1440	uint l_modBits = vli_numBits(p_mod);
saranieves92	1:4875e39abd1e	1441
saranieves92	1:4875e39abd1e	1442	vli_mult(l_product, p_left, p_right);
saranieves92	1:4875e39abd1e	1443	l_productBits = vli_numBits(l_product + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	1444	if(l_productBits)
saranieves92	1:4875e39abd1e	1445	{
saranieves92	1:4875e39abd1e	1446	l_productBits += NUM_ECC_DIGITS * 32;
saranieves92	1:4875e39abd1e	1447	}
saranieves92	1:4875e39abd1e	1448	else
saranieves92	1:4875e39abd1e	1449	{
saranieves92	1:4875e39abd1e	1450	l_productBits = vli_numBits(l_product);
saranieves92	1:4875e39abd1e	1451	}
saranieves92	1:4875e39abd1e	1452
saranieves92	1:4875e39abd1e	1453	if(l_productBits < l_modBits)
saranieves92	1:4875e39abd1e	1454	{ /* l_product < p_mod. */
saranieves92	1:4875e39abd1e	1455	vli_set(p_result, l_product);
saranieves92	1:4875e39abd1e	1456	return;
saranieves92	1:4875e39abd1e	1457	}
saranieves92	1:4875e39abd1e	1458
saranieves92	1:4875e39abd1e	1459	/* Shift p_mod by (l_leftBits - l_modBits). This multiplies p_mod by the largest
saranieves92	1:4875e39abd1e	1460	power of two possible while still resulting in a number less than p_left. */
saranieves92	1:4875e39abd1e	1461	vli_clear(l_modMultiple);
saranieves92	1:4875e39abd1e	1462	vli_clear(l_modMultiple + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	1463	l_digitShift = (l_productBits - l_modBits) / 32;
saranieves92	1:4875e39abd1e	1464	l_bitShift = (l_productBits - l_modBits) % 32;
saranieves92	1:4875e39abd1e	1465	if(l_bitShift)
saranieves92	1:4875e39abd1e	1466	{
saranieves92	1:4875e39abd1e	1467	l_modMultiple[l_digitShift + NUM_ECC_DIGITS] = vli_lshift(l_modMultiple + l_digitShift, p_mod, l_bitShift);
saranieves92	1:4875e39abd1e	1468	}
saranieves92	1:4875e39abd1e	1469	else
saranieves92	1:4875e39abd1e	1470	{
saranieves92	1:4875e39abd1e	1471	vli_set(l_modMultiple + l_digitShift, p_mod);
saranieves92	1:4875e39abd1e	1472	}
saranieves92	1:4875e39abd1e	1473
saranieves92	1:4875e39abd1e	1474	/* Subtract all multiples of p_mod to get the remainder. */
saranieves92	1:4875e39abd1e	1475	vli_clear(p_result);
saranieves92	1:4875e39abd1e	1476	p_result[0] = 1; /* Use p_result as a temp var to store 1 (for subtraction) */
saranieves92	1:4875e39abd1e	1477	while(l_productBits > NUM_ECC_DIGITS * 32 \|\| vli_cmp(l_modMultiple, p_mod) >= 0)
saranieves92	1:4875e39abd1e	1478	{
saranieves92	1:4875e39abd1e	1479	int l_cmp = vli_cmp(l_modMultiple + NUM_ECC_DIGITS, l_product + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	1480	if(l_cmp < 0 \|\| (l_cmp == 0 && vli_cmp(l_modMultiple, l_product) <= 0))
saranieves92	1:4875e39abd1e	1481	{
saranieves92	1:4875e39abd1e	1482	if(vli_sub(l_product, l_product, l_modMultiple))
saranieves92	1:4875e39abd1e	1483	{ /* borrow */
saranieves92	1:4875e39abd1e	1484	vli_sub(l_product + NUM_ECC_DIGITS, l_product + NUM_ECC_DIGITS, p_result);
saranieves92	1:4875e39abd1e	1485	}
saranieves92	1:4875e39abd1e	1486	vli_sub(l_product + NUM_ECC_DIGITS, l_product + NUM_ECC_DIGITS, l_modMultiple + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	1487	}
saranieves92	1:4875e39abd1e	1488	uint32_t l_carry = (l_modMultiple[NUM_ECC_DIGITS] & 0x01) << 31;
saranieves92	1:4875e39abd1e	1489	vli_rshift1(l_modMultiple + NUM_ECC_DIGITS);
saranieves92	1:4875e39abd1e	1490	vli_rshift1(l_modMultiple);
saranieves92	1:4875e39abd1e	1491	l_modMultiple[NUM_ECC_DIGITS-1] \|= l_carry;
saranieves92	1:4875e39abd1e	1492
saranieves92	1:4875e39abd1e	1493	--l_productBits;
saranieves92	1:4875e39abd1e	1494	}
saranieves92	1:4875e39abd1e	1495	vli_set(p_result, l_product);
saranieves92	1:4875e39abd1e	1496	}
saranieves92	1:4875e39abd1e	1497
saranieves92	1:4875e39abd1e	1498	static inline unsigned int max(const unsigned int a, const unsigned int b)
saranieves92	1:4875e39abd1e	1499	{
saranieves92	1:4875e39abd1e	1500	return (a > b ? a : b);
saranieves92	1:4875e39abd1e	1501	}
saranieves92	1:4875e39abd1e	1502
saranieves92	1:4875e39abd1e	1503	int ecdsa_sign(uint32_t r[NUM_ECC_DIGITS], uint32_t s[NUM_ECC_DIGITS],
saranieves92	1:4875e39abd1e	1504	const uint32_t p_privateKey[NUM_ECC_DIGITS], const uint32_t p_random[NUM_ECC_DIGITS],
saranieves92	1:4875e39abd1e	1505	const uint32_t p_hash[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1506	{
saranieves92	1:4875e39abd1e	1507	uint32_t k[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1508	EccPoint p;
saranieves92	1:4875e39abd1e	1509
saranieves92	1:4875e39abd1e	1510	if(vli_isZero(p_random))
saranieves92	1:4875e39abd1e	1511	{ /* The random number must not be 0. */
saranieves92	1:4875e39abd1e	1512	return 0;
saranieves92	1:4875e39abd1e	1513	}
saranieves92	1:4875e39abd1e	1514
saranieves92	1:4875e39abd1e	1515	vli_set(k, p_random);
saranieves92	1:4875e39abd1e	1516	if(vli_cmp(curve_n, k) != 1)
saranieves92	1:4875e39abd1e	1517	{
saranieves92	1:4875e39abd1e	1518	vli_sub(k, k, curve_n);
saranieves92	1:4875e39abd1e	1519	}
saranieves92	1:4875e39abd1e	1520
saranieves92	1:4875e39abd1e	1521	/* tmp = k * G */
saranieves92	1:4875e39abd1e	1522	EccPoint_mult(&p, &curve_G, k, NULL);
saranieves92	1:4875e39abd1e	1523
saranieves92	1:4875e39abd1e	1524	/* r = x1 (mod n) */
saranieves92	1:4875e39abd1e	1525	vli_set(r, p.x);
saranieves92	1:4875e39abd1e	1526	if(vli_cmp(curve_n, r) != 1)
saranieves92	1:4875e39abd1e	1527	{
saranieves92	1:4875e39abd1e	1528	vli_sub(r, r, curve_n);
saranieves92	1:4875e39abd1e	1529	}
saranieves92	1:4875e39abd1e	1530	if(vli_isZero(r))
saranieves92	1:4875e39abd1e	1531	{ /* If r == 0, fail (need a different random number). */
saranieves92	1:4875e39abd1e	1532	return 0;
saranieves92	1:4875e39abd1e	1533	}
saranieves92	1:4875e39abd1e	1534
saranieves92	1:4875e39abd1e	1535	vli_modMult(s, r, p_privateKey, curve_n); /* s = rd /
saranieves92	1:4875e39abd1e	1536	vli_modAdd(s, p_hash, s, curve_n); /* s = e + rd /
saranieves92	1:4875e39abd1e	1537	vli_modInv(k, k, curve_n); /* k = 1 / k */
saranieves92	1:4875e39abd1e	1538	vli_modMult(s, s, k, curve_n); /* s = (e + rd) / k /
saranieves92	1:4875e39abd1e	1539
saranieves92	1:4875e39abd1e	1540	return 1;
saranieves92	1:4875e39abd1e	1541	}
saranieves92	1:4875e39abd1e	1542
saranieves92	1:4875e39abd1e	1543	int ecdsa_verify(const EccPoint *p_publicKey, const uint32_t p_hash[NUM_ECC_DIGITS],
saranieves92	1:4875e39abd1e	1544	const uint32_t r[NUM_ECC_DIGITS], const uint32_t s[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1545	{
saranieves92	1:4875e39abd1e	1546	uint32_t u1[NUM_ECC_DIGITS], u2[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1547	uint32_t z[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1548	EccPoint l_sum;
saranieves92	1:4875e39abd1e	1549	uint32_t rx[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1550	uint32_t ry[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1551	uint32_t tx[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1552	uint32_t ty[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1553	uint32_t tz[NUM_ECC_DIGITS];
saranieves92	1:4875e39abd1e	1554
saranieves92	1:4875e39abd1e	1555	if(vli_isZero(r) \|\| vli_isZero(s))
saranieves92	1:4875e39abd1e	1556	{ /* r, s must not be 0. */
saranieves92	1:4875e39abd1e	1557	return 0;
saranieves92	1:4875e39abd1e	1558	}
saranieves92	1:4875e39abd1e	1559
saranieves92	1:4875e39abd1e	1560	if(vli_cmp(curve_n, r) != 1 \|\| vli_cmp(curve_n, s) != 1)
saranieves92	1:4875e39abd1e	1561	{ /* r, s must be < n. */
saranieves92	1:4875e39abd1e	1562	return 0;
saranieves92	1:4875e39abd1e	1563	}
saranieves92	1:4875e39abd1e	1564
saranieves92	1:4875e39abd1e	1565	/* Calculate u1 and u2. */
saranieves92	1:4875e39abd1e	1566	vli_modInv(z, s, curve_n); /* Z = s^-1 */
saranieves92	1:4875e39abd1e	1567	vli_modMult(u1, p_hash, z, curve_n); /* u1 = e/s */
saranieves92	1:4875e39abd1e	1568	vli_modMult(u2, r, z, curve_n); /* u2 = r/s */
saranieves92	1:4875e39abd1e	1569
saranieves92	1:4875e39abd1e	1570	/* Calculate l_sum = G + Q. */
saranieves92	1:4875e39abd1e	1571	vli_set(l_sum.x, p_publicKey->x);
saranieves92	1:4875e39abd1e	1572	vli_set(l_sum.y, p_publicKey->y);
saranieves92	1:4875e39abd1e	1573	vli_set(tx, curve_G.x);
saranieves92	1:4875e39abd1e	1574	vli_set(ty, curve_G.y);
saranieves92	1:4875e39abd1e	1575	vli_modSub(z, l_sum.x, tx, curve_p); /* Z = x2 - x1 */
saranieves92	1:4875e39abd1e	1576	XYcZ_add(tx, ty, l_sum.x, l_sum.y);
saranieves92	1:4875e39abd1e	1577	vli_modInv(z, z, curve_p); /* Z = 1/Z */
saranieves92	1:4875e39abd1e	1578	apply_z(l_sum.x, l_sum.y, z);
saranieves92	1:4875e39abd1e	1579
saranieves92	1:4875e39abd1e	1580	/* Use Shamir's trick to calculate u1G + u2Q */
saranieves92	1:4875e39abd1e	1581	const EccPoint *l_points[4] = {NULL, &curve_G, p_publicKey, &l_sum};
saranieves92	1:4875e39abd1e	1582	uint l_numBits = max(vli_numBits(u1), vli_numBits(u2));
saranieves92	1:4875e39abd1e	1583
saranieves92	1:4875e39abd1e	1584	const EccPoint *l_point = l_points[(!!vli_testBit(u1, l_numBits-1)) \| ((!!vli_testBit(u2, l_numBits-1)) << 1)];
saranieves92	1:4875e39abd1e	1585	vli_set(rx, l_point->x);
saranieves92	1:4875e39abd1e	1586	vli_set(ry, l_point->y);
saranieves92	1:4875e39abd1e	1587	vli_clear(z);
saranieves92	1:4875e39abd1e	1588	z[0] = 1;
saranieves92	1:4875e39abd1e	1589
saranieves92	1:4875e39abd1e	1590	int i;
saranieves92	1:4875e39abd1e	1591	for(i = l_numBits - 2; i >= 0; --i)
saranieves92	1:4875e39abd1e	1592	{
saranieves92	1:4875e39abd1e	1593	EccPoint_double_jacobian(rx, ry, z);
saranieves92	1:4875e39abd1e	1594
saranieves92	1:4875e39abd1e	1595	int l_index = (!!vli_testBit(u1, i)) \| ((!!vli_testBit(u2, i)) << 1);
saranieves92	1:4875e39abd1e	1596	l_point = l_points[l_index];
saranieves92	1:4875e39abd1e	1597	if(l_point)
saranieves92	1:4875e39abd1e	1598	{
saranieves92	1:4875e39abd1e	1599	vli_set(tx, l_point->x);
saranieves92	1:4875e39abd1e	1600	vli_set(ty, l_point->y);
saranieves92	1:4875e39abd1e	1601	apply_z(tx, ty, z);
saranieves92	1:4875e39abd1e	1602	vli_modSub(tz, rx, tx, curve_p); /* Z = x2 - x1 */
saranieves92	1:4875e39abd1e	1603	XYcZ_add(tx, ty, rx, ry);
saranieves92	1:4875e39abd1e	1604	vli_modMult_fast(z, z, tz);
saranieves92	1:4875e39abd1e	1605	}
saranieves92	1:4875e39abd1e	1606	}
saranieves92	1:4875e39abd1e	1607
saranieves92	1:4875e39abd1e	1608	vli_modInv(z, z, curve_p); /* Z = 1/Z */
saranieves92	1:4875e39abd1e	1609	apply_z(rx, ry, z);
saranieves92	1:4875e39abd1e	1610
saranieves92	1:4875e39abd1e	1611	/* v = x1 (mod n) */
saranieves92	1:4875e39abd1e	1612	if(vli_cmp(curve_n, rx) != 1)
saranieves92	1:4875e39abd1e	1613	{
saranieves92	1:4875e39abd1e	1614	vli_sub(rx, rx, curve_n);
saranieves92	1:4875e39abd1e	1615	}
saranieves92	1:4875e39abd1e	1616
saranieves92	1:4875e39abd1e	1617	/* Accept only if v == r. */
saranieves92	1:4875e39abd1e	1618	return (vli_cmp(rx, r) == 0);
saranieves92	1:4875e39abd1e	1619	}
saranieves92	1:4875e39abd1e	1620
saranieves92	1:4875e39abd1e	1621	void ecc_bytes2native(uint32_t p_native[NUM_ECC_DIGITS], const uint8_t p_bytes[NUM_ECC_DIGITS*4])
saranieves92	1:4875e39abd1e	1622	{
saranieves92	1:4875e39abd1e	1623	unsigned i;
saranieves92	1:4875e39abd1e	1624	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	1625	{
saranieves92	1:4875e39abd1e	1626	uint8_t p_digit = (uint8_t )(p_bytes + 4 * (NUM_ECC_DIGITS - 1 - i));
saranieves92	1:4875e39abd1e	1627	p_native[i] = ((uint32_t)p_digit[0] << 24) \| ((uint32_t)p_digit[1] << 16) \| ((uint32_t)p_digit[2] << 8) \| (uint32_t)p_digit[3];
saranieves92	1:4875e39abd1e	1628	}
saranieves92	1:4875e39abd1e	1629	}
saranieves92	1:4875e39abd1e	1630
saranieves92	1:4875e39abd1e	1631	void ecc_native2bytes(uint8_t p_bytes[NUM_ECC_DIGITS*4], const uint32_t p_native[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1632	{
saranieves92	1:4875e39abd1e	1633	unsigned i;
saranieves92	1:4875e39abd1e	1634	for(i=0; i<NUM_ECC_DIGITS; ++i)
saranieves92	1:4875e39abd1e	1635	{
saranieves92	1:4875e39abd1e	1636	uint8_t p_digit = p_bytes + 4 (NUM_ECC_DIGITS - 1 - i);
saranieves92	1:4875e39abd1e	1637	p_digit[0] = p_native[i] >> 24;
saranieves92	1:4875e39abd1e	1638	p_digit[1] = p_native[i] >> 16;
saranieves92	1:4875e39abd1e	1639	p_digit[2] = p_native[i] >> 8;
saranieves92	1:4875e39abd1e	1640	p_digit[3] = p_native[i];
saranieves92	1:4875e39abd1e	1641	}
saranieves92	1:4875e39abd1e	1642	}
saranieves92	1:4875e39abd1e	1643
saranieves92	1:4875e39abd1e	1644	/* Compute a = sqrt(a) (mod curve_p). */
saranieves92	1:4875e39abd1e	1645	static void mod_sqrt(uint32_t a[NUM_ECC_DIGITS])
saranieves92	1:4875e39abd1e	1646	{
saranieves92	1:4875e39abd1e	1647	unsigned i;
saranieves92	1:4875e39abd1e	1648	uint32_t p1[NUM_ECC_DIGITS] = {1};
saranieves92	1:4875e39abd1e	1649	uint32_t l_result[NUM_ECC_DIGITS] = {1};
saranieves92	1:4875e39abd1e	1650
saranieves92	1:4875e39abd1e	1651	/* Since curve_p == 3 (mod 4) for all supported curves, we can
saranieves92	1:4875e39abd1e	1652	compute sqrt(a) = a^((curve_p + 1) / 4) (mod curve_p). */
saranieves92	1:4875e39abd1e	1653	vli_add(p1, curve_p, p1); /* p1 = curve_p + 1 */
saranieves92	1:4875e39abd1e	1654	for(i = vli_numBits(p1) - 1; i > 1; --i)
saranieves92	1:4875e39abd1e	1655	{
saranieves92	1:4875e39abd1e	1656	vli_modSquare_fast(l_result, l_result);
saranieves92	1:4875e39abd1e	1657	if(vli_testBit(p1, i))
saranieves92	1:4875e39abd1e	1658	{
saranieves92	1:4875e39abd1e	1659	vli_modMult_fast(l_result, l_result, a);
saranieves92	1:4875e39abd1e	1660	}
saranieves92	1:4875e39abd1e	1661	}
saranieves92	1:4875e39abd1e	1662	vli_set(a, l_result);
saranieves92	1:4875e39abd1e	1663	}
saranieves92	1:4875e39abd1e	1664
saranieves92	1:4875e39abd1e	1665	void ecc_point_compress(uint8_t p_compressed[NUM_ECC_DIGITS4 + 1], const EccPoint p_point)
saranieves92	1:4875e39abd1e	1666	{
saranieves92	1:4875e39abd1e	1667	p_compressed[0] = 2 + (p_point->y[0] & 0x01);
saranieves92	1:4875e39abd1e	1668	ecc_native2bytes(p_compressed + 1, p_point->x);
saranieves92	1:4875e39abd1e	1669	}
saranieves92	1:4875e39abd1e	1670
saranieves92	1:4875e39abd1e	1671	void ecc_point_decompress(EccPoint p_point, const uint8_t p_compressed[NUM_ECC_DIGITS4 + 1])
saranieves92	1:4875e39abd1e	1672	{
saranieves92	1:4875e39abd1e	1673	ecc_bytes2native(p_point->x, p_compressed + 1);
saranieves92	1:4875e39abd1e	1674	curve_x_side(p_point->y, p_point->x);
saranieves92	1:4875e39abd1e	1675	mod_sqrt(p_point->y);
saranieves92	1:4875e39abd1e	1676	if((p_point->y[0] & 0x01) != (p_compressed[0] & 0x01))
saranieves92	1:4875e39abd1e	1677	{
saranieves92	1:4875e39abd1e	1678	vli_sub(p_point->y, curve_p, p_point->y);
saranieves92	1:4875e39abd1e	1679	}
saranieves92	1:4875e39abd1e	1680	}
saranieves92	1:4875e39abd1e	1681

Repository toolbox

Export to desktop IDE

Build repository

Repository details

Type:	Program
Mbed OS support:	Mbed 2 deprecated
Created:	05 Feb 2015
Imports:	4
Forks:	0
Commits:	6
Dependents:	0
Dependencies:	2
Followers:	1

ecc.cpp@5:4f619b9a7bb2, 2015-02-20 (annotated)

Who changed what in which revision?

Repository toolbox

Repository details

Important Information for this Arm website

Access Warning