xref: /btstack/3rd-party/micro-ecc/uECC.c (revision c824d78c0a34df89b57d535abafcc7dacf30bb06)
1af03003cSMatthias Ringwald /* Copyright 2014, Kenneth MacKay. Licensed under the BSD 2-clause license. */
2af03003cSMatthias Ringwald 
3af03003cSMatthias Ringwald #include "uECC.h"
4af03003cSMatthias Ringwald 
501899c8bSMatthias Ringwald // NULL
601899c8bSMatthias Ringwald #include "stddef.h"
701899c8bSMatthias Ringwald 
875aabb0dSMatthias Ringwald // suppress MSVC C4244: conversion from uECC_word_t to int
975aabb0dSMatthias Ringwald #ifdef _MSC_VER
1075aabb0dSMatthias Ringwald #pragma warning( disable : 4244 )
1175aabb0dSMatthias Ringwald #endif
1275aabb0dSMatthias Ringwald 
13af03003cSMatthias Ringwald #ifndef uECC_PLATFORM
14af03003cSMatthias Ringwald     #if __AVR__
15af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_avr
16af03003cSMatthias Ringwald     #elif defined(__thumb2__) || defined(_M_ARMT) /* I think MSVC only supports Thumb-2 targets */
17af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_arm_thumb2
18af03003cSMatthias Ringwald     #elif defined(__thumb__)
19af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_arm_thumb
20af03003cSMatthias Ringwald     #elif defined(__arm__) || defined(_M_ARM)
21af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_arm
22af03003cSMatthias Ringwald     #elif defined(__i386__) || defined(_M_IX86) || defined(_X86_) || defined(__I86__)
23af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_x86
24af03003cSMatthias Ringwald     #elif defined(__amd64__) || defined(_M_X64)
25af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_x86_64
26af03003cSMatthias Ringwald     #else
27af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_arch_other
28af03003cSMatthias Ringwald     #endif
29af03003cSMatthias Ringwald #endif
30af03003cSMatthias Ringwald 
31af03003cSMatthias Ringwald #ifndef uECC_WORD_SIZE
32af03003cSMatthias Ringwald     #if uECC_PLATFORM == uECC_avr
33af03003cSMatthias Ringwald         #define uECC_WORD_SIZE 1
34af03003cSMatthias Ringwald     #elif (uECC_PLATFORM == uECC_x86_64)
35af03003cSMatthias Ringwald         #define uECC_WORD_SIZE 8
36af03003cSMatthias Ringwald     #else
37af03003cSMatthias Ringwald         #define uECC_WORD_SIZE 4
38af03003cSMatthias Ringwald     #endif
39af03003cSMatthias Ringwald #endif
40af03003cSMatthias Ringwald 
41af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1 || uECC_CURVE == uECC_secp224r1) && (uECC_WORD_SIZE == 8)
42af03003cSMatthias Ringwald     #undef uECC_WORD_SIZE
43af03003cSMatthias Ringwald     #define uECC_WORD_SIZE 4
44af03003cSMatthias Ringwald     #if (uECC_PLATFORM == uECC_x86_64)
45af03003cSMatthias Ringwald         #undef uECC_PLATFORM
46af03003cSMatthias Ringwald         #define uECC_PLATFORM uECC_x86
47af03003cSMatthias Ringwald     #endif
48af03003cSMatthias Ringwald #endif
49af03003cSMatthias Ringwald 
50af03003cSMatthias Ringwald #if (uECC_WORD_SIZE != 1) && (uECC_WORD_SIZE != 4) && (uECC_WORD_SIZE != 8)
51af03003cSMatthias Ringwald     #error "Unsupported value for uECC_WORD_SIZE"
52af03003cSMatthias Ringwald #endif
53af03003cSMatthias Ringwald 
54af03003cSMatthias Ringwald #if (uECC_ASM && (uECC_PLATFORM == uECC_avr) && (uECC_WORD_SIZE != 1))
55af03003cSMatthias Ringwald     #pragma message ("uECC_WORD_SIZE must be 1 when using AVR asm")
56af03003cSMatthias Ringwald     #undef uECC_WORD_SIZE
57af03003cSMatthias Ringwald     #define uECC_WORD_SIZE 1
58af03003cSMatthias Ringwald #endif
59af03003cSMatthias Ringwald 
60af03003cSMatthias Ringwald #if (uECC_ASM && \
61af03003cSMatthias Ringwald      (uECC_PLATFORM == uECC_arm || uECC_PLATFORM == uECC_arm_thumb) && \
62af03003cSMatthias Ringwald      (uECC_WORD_SIZE != 4))
63af03003cSMatthias Ringwald     #pragma message ("uECC_WORD_SIZE must be 4 when using ARM asm")
64af03003cSMatthias Ringwald     #undef uECC_WORD_SIZE
65af03003cSMatthias Ringwald     #define uECC_WORD_SIZE 4
66af03003cSMatthias Ringwald #endif
67af03003cSMatthias Ringwald 
68af03003cSMatthias Ringwald #if __STDC_VERSION__ >= 199901L
69af03003cSMatthias Ringwald     #define RESTRICT restrict
70af03003cSMatthias Ringwald #else
71af03003cSMatthias Ringwald     #define RESTRICT
72af03003cSMatthias Ringwald #endif
73af03003cSMatthias Ringwald 
74af03003cSMatthias Ringwald #if defined(__SIZEOF_INT128__) || ((__clang_major__ * 100 + __clang_minor__) >= 302)
75af03003cSMatthias Ringwald     #define SUPPORTS_INT128 1
76af03003cSMatthias Ringwald #else
77af03003cSMatthias Ringwald     #define SUPPORTS_INT128 0
78af03003cSMatthias Ringwald #endif
79af03003cSMatthias Ringwald 
80af03003cSMatthias Ringwald #define MAX_TRIES 64
81af03003cSMatthias Ringwald 
82af03003cSMatthias Ringwald #if (uECC_WORD_SIZE == 1)
83af03003cSMatthias Ringwald 
84af03003cSMatthias Ringwald typedef uint8_t uECC_word_t;
85af03003cSMatthias Ringwald typedef uint16_t uECC_dword_t;
86af03003cSMatthias Ringwald typedef uint8_t wordcount_t;
87af03003cSMatthias Ringwald typedef int8_t swordcount_t;
88af03003cSMatthias Ringwald typedef int16_t bitcount_t;
89af03003cSMatthias Ringwald typedef int8_t cmpresult_t;
90af03003cSMatthias Ringwald 
91af03003cSMatthias Ringwald #define HIGH_BIT_SET 0x80
92af03003cSMatthias Ringwald #define uECC_WORD_BITS 8
93af03003cSMatthias Ringwald #define uECC_WORD_BITS_SHIFT 3
94af03003cSMatthias Ringwald #define uECC_WORD_BITS_MASK 0x07
95af03003cSMatthias Ringwald 
96af03003cSMatthias Ringwald #define uECC_WORDS_1 20
97af03003cSMatthias Ringwald #define uECC_WORDS_2 24
98af03003cSMatthias Ringwald #define uECC_WORDS_3 32
99af03003cSMatthias Ringwald #define uECC_WORDS_4 32
100af03003cSMatthias Ringwald #define uECC_WORDS_5 28
101af03003cSMatthias Ringwald 
102af03003cSMatthias Ringwald #define uECC_N_WORDS_1 21
103af03003cSMatthias Ringwald #define uECC_N_WORDS_2 24
104af03003cSMatthias Ringwald #define uECC_N_WORDS_3 32
105af03003cSMatthias Ringwald #define uECC_N_WORDS_4 32
106af03003cSMatthias Ringwald #define uECC_N_WORDS_5 28
107af03003cSMatthias Ringwald 
108af03003cSMatthias Ringwald #define Curve_P_1 {0xFF, 0xFF, 0xFF, 0x7F, 0xFF, 0xFF, 0xFF, 0xFF, \
109af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
110af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF}
111af03003cSMatthias Ringwald #define Curve_P_2 {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
112af03003cSMatthias Ringwald                    0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
113af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
114af03003cSMatthias Ringwald #define Curve_P_3 {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
115af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0x00, 0x00, 0x00, 0x00, \
116af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, \
117af03003cSMatthias Ringwald                    0x01, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF}
118af03003cSMatthias Ringwald #define Curve_P_4 {0x2F, 0xFC, 0xFF, 0xFF, 0xFE, 0xFF, 0xFF, 0xFF, \
119af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
120af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
121af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
122af03003cSMatthias Ringwald #define Curve_P_5 {0x01, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, \
123af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF, \
124af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
125af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF}
126af03003cSMatthias Ringwald 
127af03003cSMatthias Ringwald #define Curve_B_1 {0x45, 0xFA, 0x65, 0xC5, 0xAD, 0xD4, 0xD4, 0x81, \
128af03003cSMatthias Ringwald                    0x9F, 0xF8, 0xAC, 0x65, 0x8B, 0x7A, 0xBD, 0x54, \
129af03003cSMatthias Ringwald                    0xFC, 0xBE, 0x97, 0x1C}
130af03003cSMatthias Ringwald #define Curve_B_2 {0xB1, 0xB9, 0x46, 0xC1, 0xEC, 0xDE, 0xB8, 0xFE, \
131af03003cSMatthias Ringwald                    0x49, 0x30, 0x24, 0x72, 0xAB, 0xE9, 0xA7, 0x0F, \
132af03003cSMatthias Ringwald                    0xE7, 0x80, 0x9C, 0xE5, 0x19, 0x05, 0x21, 0x64}
133af03003cSMatthias Ringwald #define Curve_B_3 {0x4B, 0x60, 0xD2, 0x27, 0x3E, 0x3C, 0xCE, 0x3B, \
134af03003cSMatthias Ringwald                    0xF6, 0xB0, 0x53, 0xCC, 0xB0, 0x06, 0x1D, 0x65, \
135af03003cSMatthias Ringwald                    0xBC, 0x86, 0x98, 0x76, 0x55, 0xBD, 0xEB, 0xB3, \
136af03003cSMatthias Ringwald                    0xE7, 0x93, 0x3A, 0xAA, 0xD8, 0x35, 0xC6, 0x5A}
137af03003cSMatthias Ringwald #define Curve_B_4 {0x07, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, \
138af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, \
139af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, \
140af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00}
141af03003cSMatthias Ringwald #define Curve_B_5 {0xB4, 0xFF, 0x55, 0x23, 0x43, 0x39, 0x0B, 0x27, \
142af03003cSMatthias Ringwald                    0xBA, 0xD8, 0xBF, 0xD7, 0xB7, 0xB0, 0x44, 0x50, \
143af03003cSMatthias Ringwald                    0x56, 0x32, 0x41, 0xF5, 0xAB, 0xB3, 0x04, 0x0C, \
144af03003cSMatthias Ringwald                    0x85, 0x0A, 0x05, 0xB4}
145af03003cSMatthias Ringwald 
146af03003cSMatthias Ringwald #define Curve_G_1 { \
147af03003cSMatthias Ringwald     {0x82, 0xFC, 0xCB, 0x13, 0xB9, 0x8B, 0xC3, 0x68, \
148af03003cSMatthias Ringwald         0x89, 0x69, 0x64, 0x46, 0x28, 0x73, 0xF5, 0x8E, \
149af03003cSMatthias Ringwald         0x68, 0xB5, 0x96, 0x4A}, \
150af03003cSMatthias Ringwald     {0x32, 0xFB, 0xC5, 0x7A, 0x37, 0x51, 0x23, 0x04, \
151af03003cSMatthias Ringwald         0x12, 0xC9, 0xDC, 0x59, 0x7D, 0x94, 0x68, 0x31, \
152af03003cSMatthias Ringwald         0x55, 0x28, 0xA6, 0x23}}
153af03003cSMatthias Ringwald 
154af03003cSMatthias Ringwald #define Curve_G_2 { \
155af03003cSMatthias Ringwald     {0x12, 0x10, 0xFF, 0x82, 0xFD, 0x0A, 0xFF, 0xF4, \
156af03003cSMatthias Ringwald         0x00, 0x88, 0xA1, 0x43, 0xEB, 0x20, 0xBF, 0x7C, \
157af03003cSMatthias Ringwald         0xF6, 0x90, 0x30, 0xB0, 0x0E, 0xA8, 0x8D, 0x18}, \
158af03003cSMatthias Ringwald     {0x11, 0x48, 0x79, 0x1E, 0xA1, 0x77, 0xF9, 0x73, \
159af03003cSMatthias Ringwald         0xD5, 0xCD, 0x24, 0x6B, 0xED, 0x11, 0x10, 0x63, \
160af03003cSMatthias Ringwald         0x78, 0xDA, 0xC8, 0xFF, 0x95, 0x2B, 0x19, 0x07}}
161af03003cSMatthias Ringwald 
162af03003cSMatthias Ringwald #define Curve_G_3 { \
163af03003cSMatthias Ringwald     {0x96, 0xC2, 0x98, 0xD8, 0x45, 0x39, 0xA1, 0xF4, \
164af03003cSMatthias Ringwald         0xA0, 0x33, 0xEB, 0x2D, 0x81, 0x7D, 0x03, 0x77, \
165af03003cSMatthias Ringwald         0xF2, 0x40, 0xA4, 0x63, 0xE5, 0xE6, 0xBC, 0xF8, \
166af03003cSMatthias Ringwald         0x47, 0x42, 0x2C, 0xE1, 0xF2, 0xD1, 0x17, 0x6B}, \
167af03003cSMatthias Ringwald     {0xF5, 0x51, 0xBF, 0x37, 0x68, 0x40, 0xB6, 0xCB, \
168af03003cSMatthias Ringwald         0xCE, 0x5E, 0x31, 0x6B, 0x57, 0x33, 0xCE, 0x2B, \
169af03003cSMatthias Ringwald         0x16, 0x9E, 0x0F, 0x7C, 0x4A, 0xEB, 0xE7, 0x8E, \
170af03003cSMatthias Ringwald         0x9B, 0x7F, 0x1A, 0xFE, 0xE2, 0x42, 0xE3, 0x4F}}
171af03003cSMatthias Ringwald 
172af03003cSMatthias Ringwald #define Curve_G_4 { \
173af03003cSMatthias Ringwald     {0x98, 0x17, 0xF8, 0x16, 0x5B, 0x81, 0xF2, 0x59, \
174af03003cSMatthias Ringwald         0xD9, 0x28, 0xCE, 0x2D, 0xDB, 0xFC, 0x9B, 0x02, \
175af03003cSMatthias Ringwald         0x07, 0x0B, 0x87, 0xCE, 0x95, 0x62, 0xA0, 0x55, \
176af03003cSMatthias Ringwald         0xAC, 0xBB, 0xDC, 0xF9, 0x7E, 0x66, 0xBE, 0x79}, \
177af03003cSMatthias Ringwald     {0xB8, 0xD4, 0x10, 0xFB, 0x8F, 0xD0, 0x47, 0x9C, \
178af03003cSMatthias Ringwald         0x19, 0x54, 0x85, 0xA6, 0x48, 0xB4, 0x17, 0xFD, \
179af03003cSMatthias Ringwald         0xA8, 0x08, 0x11, 0x0E, 0xFC, 0xFB, 0xA4, 0x5D, \
180af03003cSMatthias Ringwald         0x65, 0xC4, 0xA3, 0x26, 0x77, 0xDA, 0x3A, 0x48}}
181af03003cSMatthias Ringwald 
182af03003cSMatthias Ringwald #define Curve_G_5 { \
183af03003cSMatthias Ringwald     {0x21, 0x1D, 0x5C, 0x11, 0xD6, 0x80, 0x32, 0x34, \
184af03003cSMatthias Ringwald         0x22, 0x11, 0xC2, 0x56, 0xD3, 0xC1, 0x03, 0x4A, \
185af03003cSMatthias Ringwald         0xB9, 0x90, 0x13, 0x32, 0x7F, 0xBF, 0xB4, 0x6B, \
186af03003cSMatthias Ringwald         0xBD, 0x0C, 0x0E, 0xB7}, \
187af03003cSMatthias Ringwald     {0x34, 0x7E, 0x00, 0x85, 0x99, 0x81, 0xD5, 0x44, \
188af03003cSMatthias Ringwald         0x64, 0x47, 0x07, 0x5A, 0xA0, 0x75, 0x43, 0xCD, \
189af03003cSMatthias Ringwald         0xE6, 0xDF, 0x22, 0x4C, 0xFB, 0x23, 0xF7, 0xB5, \
190af03003cSMatthias Ringwald         0x88, 0x63, 0x37, 0xBD}}
191af03003cSMatthias Ringwald 
192af03003cSMatthias Ringwald #define Curve_N_1 {0x57, 0x22, 0x75, 0xCA, 0xD3, 0xAE, 0x27, 0xF9, \
193af03003cSMatthias Ringwald                    0xC8, 0xF4, 0x01, 0x00, 0x00, 0x00, 0x00, 0x00, \
194af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0x01}
195af03003cSMatthias Ringwald #define Curve_N_2 {0x31, 0x28, 0xD2, 0xB4, 0xB1, 0xC9, 0x6B, 0x14, \
196af03003cSMatthias Ringwald                    0x36, 0xF8, 0xDE, 0x99, 0xFF, 0xFF, 0xFF, 0xFF, \
197af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
198af03003cSMatthias Ringwald #define Curve_N_3 {0x51, 0x25, 0x63, 0xFC, 0xC2, 0xCA, 0xB9, 0xF3, \
199af03003cSMatthias Ringwald                    0x84, 0x9E, 0x17, 0xA7, 0xAD, 0xFA, 0xE6, 0xBC, \
200af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
201af03003cSMatthias Ringwald                    0x00, 0x00, 0x00, 0x00, 0xFF, 0xFF, 0xFF, 0xFF}
202af03003cSMatthias Ringwald #define Curve_N_4 {0x41, 0x41, 0x36, 0xD0, 0x8C, 0x5E, 0xD2, 0xBF, \
203af03003cSMatthias Ringwald                    0x3B, 0xA0, 0x48, 0xAF, 0xE6, 0xDC, 0xAE, 0xBA, \
204af03003cSMatthias Ringwald                    0xFE, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
205af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF}
206af03003cSMatthias Ringwald #define Curve_N_5 {0x3D, 0x2A, 0x5C, 0x5C, 0x45, 0x29, 0xDD, 0x13, \
207af03003cSMatthias Ringwald                    0x3E, 0xF0, 0xB8, 0xE0, 0xA2, 0x16, 0xFF, 0xFF, \
208af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, \
209af03003cSMatthias Ringwald                    0xFF, 0xFF, 0xFF, 0xFF}
210af03003cSMatthias Ringwald 
211af03003cSMatthias Ringwald #elif (uECC_WORD_SIZE == 4)
212af03003cSMatthias Ringwald 
213af03003cSMatthias Ringwald typedef uint32_t uECC_word_t;
214af03003cSMatthias Ringwald typedef uint64_t uECC_dword_t;
215af03003cSMatthias Ringwald typedef unsigned wordcount_t;
216af03003cSMatthias Ringwald typedef int swordcount_t;
217af03003cSMatthias Ringwald typedef int bitcount_t;
218af03003cSMatthias Ringwald typedef int cmpresult_t;
219af03003cSMatthias Ringwald 
220af03003cSMatthias Ringwald #define HIGH_BIT_SET 0x80000000
221af03003cSMatthias Ringwald #define uECC_WORD_BITS 32
222af03003cSMatthias Ringwald #define uECC_WORD_BITS_SHIFT 5
223af03003cSMatthias Ringwald #define uECC_WORD_BITS_MASK 0x01F
224af03003cSMatthias Ringwald 
225af03003cSMatthias Ringwald #define uECC_WORDS_1 5
226af03003cSMatthias Ringwald #define uECC_WORDS_2 6
227af03003cSMatthias Ringwald #define uECC_WORDS_3 8
228af03003cSMatthias Ringwald #define uECC_WORDS_4 8
229af03003cSMatthias Ringwald #define uECC_WORDS_5 7
230af03003cSMatthias Ringwald 
231af03003cSMatthias Ringwald #define uECC_N_WORDS_1 6
232af03003cSMatthias Ringwald #define uECC_N_WORDS_2 6
233af03003cSMatthias Ringwald #define uECC_N_WORDS_3 8
234af03003cSMatthias Ringwald #define uECC_N_WORDS_4 8
235af03003cSMatthias Ringwald #define uECC_N_WORDS_5 7
236af03003cSMatthias Ringwald 
237af03003cSMatthias Ringwald #define Curve_P_1 {0x7FFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
238af03003cSMatthias Ringwald #define Curve_P_2 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
239af03003cSMatthias Ringwald #define Curve_P_3 {0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, \
240af03003cSMatthias Ringwald                    0x00000000, 0x00000000, 0x00000001, 0xFFFFFFFF}
241af03003cSMatthias Ringwald #define Curve_P_4 {0xFFFFFC2F, 0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, \
242af03003cSMatthias Ringwald                    0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
243af03003cSMatthias Ringwald #define Curve_P_5 {0x00000001, 0x00000000, 0x00000000, 0xFFFFFFFF, \
244af03003cSMatthias Ringwald                    0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
245af03003cSMatthias Ringwald 
246af03003cSMatthias Ringwald #define Curve_B_1 {0xC565FA45, 0x81D4D4AD, 0x65ACF89F, 0x54BD7A8B, 0x1C97BEFC}
247af03003cSMatthias Ringwald #define Curve_B_2 {0xC146B9B1, 0xFEB8DEEC, 0x72243049, 0x0FA7E9AB, 0xE59C80E7, 0x64210519}
248af03003cSMatthias Ringwald #define Curve_B_3 {0x27D2604B, 0x3BCE3C3E, 0xCC53B0F6, 0x651D06B0, \
249af03003cSMatthias Ringwald                    0x769886BC, 0xB3EBBD55, 0xAA3A93E7, 0x5AC635D8}
250af03003cSMatthias Ringwald #define Curve_B_4 {0x00000007, 0x00000000, 0x00000000, 0x00000000, \
251af03003cSMatthias Ringwald                    0x00000000, 0x00000000, 0x00000000, 0x00000000}
252af03003cSMatthias Ringwald #define Curve_B_5 {0x2355FFB4, 0x270B3943, 0xD7BFD8BA, 0x5044B0B7, \
253af03003cSMatthias Ringwald                    0xF5413256, 0x0C04B3AB, 0xB4050A85}
254af03003cSMatthias Ringwald 
255af03003cSMatthias Ringwald #define Curve_G_1 { \
256af03003cSMatthias Ringwald     {0x13CBFC82, 0x68C38BB9, 0x46646989, 0x8EF57328, 0x4A96B568}, \
257af03003cSMatthias Ringwald     {0x7AC5FB32, 0x04235137, 0x59DCC912, 0x3168947D, 0x23A62855}}
258af03003cSMatthias Ringwald 
259af03003cSMatthias Ringwald #define Curve_G_2 { \
260af03003cSMatthias Ringwald     {0x82FF1012, 0xF4FF0AFD, 0x43A18800, 0x7CBF20EB, 0xB03090F6, 0x188DA80E}, \
261af03003cSMatthias Ringwald     {0x1E794811, 0x73F977A1, 0x6B24CDD5, 0x631011ED, 0xFFC8DA78, 0x07192B95}}
262af03003cSMatthias Ringwald 
263af03003cSMatthias Ringwald #define Curve_G_3 { \
264af03003cSMatthias Ringwald     {0xD898C296, 0xF4A13945, 0x2DEB33A0, 0x77037D81,  \
265af03003cSMatthias Ringwald      0x63A440F2, 0xF8BCE6E5, 0xE12C4247, 0x6B17D1F2}, \
266af03003cSMatthias Ringwald     {0x37BF51F5, 0xCBB64068, 0x6B315ECE, 0x2BCE3357,  \
267af03003cSMatthias Ringwald      0x7C0F9E16, 0x8EE7EB4A, 0xFE1A7F9B, 0x4FE342E2}}
268af03003cSMatthias Ringwald 
269af03003cSMatthias Ringwald #define Curve_G_4 { \
270af03003cSMatthias Ringwald     {0x16F81798, 0x59F2815B, 0x2DCE28D9, 0x029BFCDB,  \
271af03003cSMatthias Ringwald      0xCE870B07, 0x55A06295, 0xF9DCBBAC, 0x79BE667E}, \
272af03003cSMatthias Ringwald     {0xFB10D4B8, 0x9C47D08F, 0xA6855419, 0xFD17B448,  \
273af03003cSMatthias Ringwald      0x0E1108A8, 0x5DA4FBFC, 0x26A3C465, 0x483ADA77}}
274af03003cSMatthias Ringwald 
275af03003cSMatthias Ringwald #define Curve_G_5 { \
276af03003cSMatthias Ringwald     {0x115C1D21, 0x343280D6, 0x56C21122, 0x4A03C1D3, \
277af03003cSMatthias Ringwald      0x321390B9, 0x6BB4BF7F, 0xB70E0CBD}, \
278af03003cSMatthias Ringwald     {0x85007E34, 0x44D58199, 0x5A074764, 0xCD4375A0, \
279af03003cSMatthias Ringwald      0x4C22DFE6, 0xB5F723FB, 0xBD376388}}
280af03003cSMatthias Ringwald 
281af03003cSMatthias Ringwald #define Curve_N_1 {0xCA752257, 0xF927AED3, 0x0001F4C8, 0x00000000, 0x00000000, 0x00000001}
282af03003cSMatthias Ringwald #define Curve_N_2 {0xB4D22831, 0x146BC9B1, 0x99DEF836, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
283af03003cSMatthias Ringwald #define Curve_N_3 {0xFC632551, 0xF3B9CAC2, 0xA7179E84, 0xBCE6FAAD, \
284af03003cSMatthias Ringwald                    0xFFFFFFFF, 0xFFFFFFFF, 0x00000000, 0xFFFFFFFF}
285af03003cSMatthias Ringwald #define Curve_N_4 {0xD0364141, 0xBFD25E8C, 0xAF48A03B, 0xBAAEDCE6, \
286af03003cSMatthias Ringwald                    0xFFFFFFFE, 0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
287af03003cSMatthias Ringwald #define Curve_N_5 {0x5C5C2A3D, 0x13DD2945, 0xE0B8F03E, 0xFFFF16A2, \
288af03003cSMatthias Ringwald                    0xFFFFFFFF, 0xFFFFFFFF, 0xFFFFFFFF}
289af03003cSMatthias Ringwald 
290af03003cSMatthias Ringwald #elif (uECC_WORD_SIZE == 8)
291af03003cSMatthias Ringwald 
292af03003cSMatthias Ringwald typedef uint64_t uECC_word_t;
293af03003cSMatthias Ringwald #if SUPPORTS_INT128
294af03003cSMatthias Ringwald typedef unsigned __int128 uECC_dword_t;
295af03003cSMatthias Ringwald #endif
296af03003cSMatthias Ringwald typedef unsigned wordcount_t;
297af03003cSMatthias Ringwald typedef int swordcount_t;
298af03003cSMatthias Ringwald typedef int bitcount_t;
299af03003cSMatthias Ringwald typedef int cmpresult_t;
300af03003cSMatthias Ringwald 
301af03003cSMatthias Ringwald #define HIGH_BIT_SET 0x8000000000000000ull
302af03003cSMatthias Ringwald #define uECC_WORD_BITS 64
303af03003cSMatthias Ringwald #define uECC_WORD_BITS_SHIFT 6
304af03003cSMatthias Ringwald #define uECC_WORD_BITS_MASK 0x03F
305af03003cSMatthias Ringwald 
306af03003cSMatthias Ringwald #define uECC_WORDS_1 3
307af03003cSMatthias Ringwald #define uECC_WORDS_2 3
308af03003cSMatthias Ringwald #define uECC_WORDS_3 4
309af03003cSMatthias Ringwald #define uECC_WORDS_4 4
310af03003cSMatthias Ringwald #define uECC_WORDS_5 4
311af03003cSMatthias Ringwald 
312af03003cSMatthias Ringwald #define uECC_N_WORDS_1 3
313af03003cSMatthias Ringwald #define uECC_N_WORDS_2 3
314af03003cSMatthias Ringwald #define uECC_N_WORDS_3 4
315af03003cSMatthias Ringwald #define uECC_N_WORDS_4 4
316af03003cSMatthias Ringwald #define uECC_N_WORDS_5 4
317af03003cSMatthias Ringwald 
318af03003cSMatthias Ringwald #define Curve_P_1 {0xFFFFFFFF7FFFFFFFull, 0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull}
319af03003cSMatthias Ringwald #define Curve_P_2 {0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFEull, 0xFFFFFFFFFFFFFFFFull}
320af03003cSMatthias Ringwald #define Curve_P_3 {0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull, \
321af03003cSMatthias Ringwald                    0x0000000000000000ull, 0xFFFFFFFF00000001ull}
322af03003cSMatthias Ringwald #define Curve_P_4 {0xFFFFFFFEFFFFFC2Full, 0xFFFFFFFFFFFFFFFFull, \
323af03003cSMatthias Ringwald                    0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFFFFFFFFFFull}
324af03003cSMatthias Ringwald #define Curve_P_5 {0x0000000000000001ull, 0xFFFFFFFF00000000ull, \
325af03003cSMatthias Ringwald                    0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull}
326af03003cSMatthias Ringwald 
327af03003cSMatthias Ringwald #define Curve_B_1 {0x81D4D4ADC565FA45ull, 0x54BD7A8B65ACF89Full, 0x000000001C97BEFCull}
328af03003cSMatthias Ringwald #define Curve_B_2 {0xFEB8DEECC146B9B1ull, 0x0FA7E9AB72243049ull, 0x64210519E59C80E7ull}
329af03003cSMatthias Ringwald #define Curve_B_3 {0x3BCE3C3E27D2604Bull, 0x651D06B0CC53B0F6ull, \
330af03003cSMatthias Ringwald                    0xB3EBBD55769886BCull, 0x5AC635D8AA3A93E7ull}
331af03003cSMatthias Ringwald #define Curve_B_4 {0x0000000000000007ull, 0x0000000000000000ull, \
332af03003cSMatthias Ringwald                    0x0000000000000000ull, 0x0000000000000000ull}
333af03003cSMatthias Ringwald #define Curve_B_5 {0x270B39432355FFB4ull, 0x5044B0B7D7BFD8BAull, \
334af03003cSMatthias Ringwald                    0x0C04B3ABF5413256ull, 0x00000000B4050A85ull}
335af03003cSMatthias Ringwald 
336af03003cSMatthias Ringwald #define Curve_G_1 { \
337af03003cSMatthias Ringwald     {0x68C38BB913CBFC82ull, 0x8EF5732846646989ull, 0x000000004A96B568ull}, \
338af03003cSMatthias Ringwald     {0x042351377AC5FB32ull, 0x3168947D59DCC912ull, 0x0000000023A62855ull}}
339af03003cSMatthias Ringwald 
340af03003cSMatthias Ringwald #define Curve_G_2 { \
341af03003cSMatthias Ringwald     {0xF4FF0AFD82FF1012ull, 0x7CBF20EB43A18800ull, 0x188DA80EB03090F6ull}, \
342af03003cSMatthias Ringwald     {0x73F977A11E794811ull, 0x631011ED6B24CDD5ull, 0x07192B95FFC8DA78ull}}
343af03003cSMatthias Ringwald 
344af03003cSMatthias Ringwald #define Curve_G_3 { \
345af03003cSMatthias Ringwald     {0xF4A13945D898C296ull, 0x77037D812DEB33A0ull, 0xF8BCE6E563A440F2ull, 0x6B17D1F2E12C4247ull}, \
346af03003cSMatthias Ringwald     {0xCBB6406837BF51F5ull, 0x2BCE33576B315ECEull, 0x8EE7EB4A7C0F9E16ull, 0x4FE342E2FE1A7F9Bull}}
347af03003cSMatthias Ringwald 
348af03003cSMatthias Ringwald #define Curve_G_4 { \
349af03003cSMatthias Ringwald     {0x59F2815B16F81798ull, 0x029BFCDB2DCE28D9ull, 0x55A06295CE870B07ull, 0x79BE667EF9DCBBACull}, \
350af03003cSMatthias Ringwald     {0x9C47D08FFB10D4B8ull, 0xFD17B448A6855419ull, 0x5DA4FBFC0E1108A8ull, 0x483ADA7726A3C465ull}}
351af03003cSMatthias Ringwald 
352af03003cSMatthias Ringwald #define Curve_G_5 { \
353af03003cSMatthias Ringwald     {0x343280D6115C1D21ull, 0x4A03C1D356C21122ull, 0x6BB4BF7F321390B9ull, 0x00000000B70E0CBDull}, \
354af03003cSMatthias Ringwald     {0x44D5819985007E34ull, 0xCD4375A05A074764ull, 0xB5F723FB4C22DFE6ull, 0x00000000BD376388ull}}
355af03003cSMatthias Ringwald 
356af03003cSMatthias Ringwald #define Curve_N_1 {0xF927AED3CA752257ull, 0x000000000001F4C8ull, 0x0000000100000000ull}
357af03003cSMatthias Ringwald #define Curve_N_2 {0x146BC9B1B4D22831ull, 0xFFFFFFFF99DEF836ull, 0xFFFFFFFFFFFFFFFFull}
358af03003cSMatthias Ringwald #define Curve_N_3 {0xF3B9CAC2FC632551ull, 0xBCE6FAADA7179E84ull, \
359af03003cSMatthias Ringwald                    0xFFFFFFFFFFFFFFFFull, 0xFFFFFFFF00000000ull}
360af03003cSMatthias Ringwald #define Curve_N_4 {0xBFD25E8CD0364141ull, 0xBAAEDCE6AF48A03Bull, \
361af03003cSMatthias Ringwald                    0xFFFFFFFFFFFFFFFEull, 0xFFFFFFFFFFFFFFFFull}
362af03003cSMatthias Ringwald #define Curve_N_5 {0x13DD29455C5C2A3Dull, 0xFFFF16A2E0B8F03Eull, \
363af03003cSMatthias Ringwald                    0xFFFFFFFFFFFFFFFFull, 0x00000000FFFFFFFFull}
364af03003cSMatthias Ringwald 
365af03003cSMatthias Ringwald #endif /* (uECC_WORD_SIZE == 8) */
366af03003cSMatthias Ringwald 
367af03003cSMatthias Ringwald #define uECC_WORDS uECC_CONCAT(uECC_WORDS_, uECC_CURVE)
368af03003cSMatthias Ringwald #define uECC_N_WORDS uECC_CONCAT(uECC_N_WORDS_, uECC_CURVE)
369af03003cSMatthias Ringwald 
370af03003cSMatthias Ringwald typedef struct EccPoint {
371af03003cSMatthias Ringwald     uECC_word_t x[uECC_WORDS];
372af03003cSMatthias Ringwald     uECC_word_t y[uECC_WORDS];
373af03003cSMatthias Ringwald } EccPoint;
374af03003cSMatthias Ringwald 
375af03003cSMatthias Ringwald static const uECC_word_t curve_p[uECC_WORDS] = uECC_CONCAT(Curve_P_, uECC_CURVE);
3768334d3d8SMatthias Ringwald // Global object `curve_b' is only referenced from function `curve_x_side', it should be defined within that functions block scope
377af03003cSMatthias Ringwald static const EccPoint curve_G = uECC_CONCAT(Curve_G_, uECC_CURVE);
378af03003cSMatthias Ringwald static const uECC_word_t curve_n[uECC_N_WORDS] = uECC_CONCAT(Curve_N_, uECC_CURVE);
379af03003cSMatthias Ringwald 
380af03003cSMatthias Ringwald static void vli_clear(uECC_word_t *vli);
381af03003cSMatthias Ringwald static uECC_word_t vli_isZero(const uECC_word_t *vli);
382af03003cSMatthias Ringwald static uECC_word_t vli_testBit(const uECC_word_t *vli, bitcount_t bit);
38380dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_ECDSA
384af03003cSMatthias Ringwald static bitcount_t vli_numBits(const uECC_word_t *vli, wordcount_t max_words);
38580dcb211SMatthias Ringwald #endif
386af03003cSMatthias Ringwald static void vli_set(uECC_word_t *dest, const uECC_word_t *src);
387af03003cSMatthias Ringwald static cmpresult_t vli_cmp(const uECC_word_t *left, const uECC_word_t *right);
38880dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_ECDSA
389af03003cSMatthias Ringwald static cmpresult_t vli_equal(const uECC_word_t *left, const uECC_word_t *right);
39080dcb211SMatthias Ringwald #endif
391af03003cSMatthias Ringwald static void vli_rshift1(uECC_word_t *vli);
392af03003cSMatthias Ringwald static uECC_word_t vli_add(uECC_word_t *result,
393af03003cSMatthias Ringwald                            const uECC_word_t *left,
394af03003cSMatthias Ringwald                            const uECC_word_t *right);
395af03003cSMatthias Ringwald static uECC_word_t vli_sub(uECC_word_t *result,
396af03003cSMatthias Ringwald                            const uECC_word_t *left,
397af03003cSMatthias Ringwald                            const uECC_word_t *right);
398af03003cSMatthias Ringwald static void vli_mult(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right);
399af03003cSMatthias Ringwald static void vli_modAdd(uECC_word_t *result,
400af03003cSMatthias Ringwald                        const uECC_word_t *left,
401af03003cSMatthias Ringwald                        const uECC_word_t *right,
402af03003cSMatthias Ringwald                        const uECC_word_t *mod);
403af03003cSMatthias Ringwald static void vli_modSub(uECC_word_t *result,
404af03003cSMatthias Ringwald                        const uECC_word_t *left,
405af03003cSMatthias Ringwald                        const uECC_word_t *right,
406af03003cSMatthias Ringwald                        const uECC_word_t *mod);
407af03003cSMatthias Ringwald static void vli_mmod_fast(uECC_word_t *RESTRICT result, uECC_word_t *RESTRICT product);
408af03003cSMatthias Ringwald static void vli_modMult_fast(uECC_word_t *result,
409af03003cSMatthias Ringwald                              const uECC_word_t *left,
410af03003cSMatthias Ringwald                              const uECC_word_t *right);
411af03003cSMatthias Ringwald static void vli_modInv(uECC_word_t *result, const uECC_word_t *input, const uECC_word_t *mod);
412af03003cSMatthias Ringwald #if uECC_SQUARE_FUNC
413af03003cSMatthias Ringwald static void vli_square(uECC_word_t *result, const uECC_word_t *left);
414af03003cSMatthias Ringwald static void vli_modSquare_fast(uECC_word_t *result, const uECC_word_t *left);
415af03003cSMatthias Ringwald #endif
416af03003cSMatthias Ringwald 
417bf2b6c37SMatthias Ringwald #if ((defined(_WIN32) || defined(_WIN64)) && !defined(uECC_NO_DEFAULT_RNG))
418af03003cSMatthias Ringwald /* Windows */
419af03003cSMatthias Ringwald 
420af03003cSMatthias Ringwald #define WIN32_LEAN_AND_MEAN
421af03003cSMatthias Ringwald #include <windows.h>
422af03003cSMatthias Ringwald #include <wincrypt.h>
423af03003cSMatthias Ringwald 
default_RNG(uint8_t * dest,unsigned size)424af03003cSMatthias Ringwald static int default_RNG(uint8_t *dest, unsigned size) {
425af03003cSMatthias Ringwald     HCRYPTPROV prov;
426af03003cSMatthias Ringwald     if (!CryptAcquireContext(&prov, NULL, NULL, PROV_RSA_FULL, CRYPT_VERIFYCONTEXT)) {
427af03003cSMatthias Ringwald         return 0;
428af03003cSMatthias Ringwald     }
429af03003cSMatthias Ringwald 
430af03003cSMatthias Ringwald     CryptGenRandom(prov, size, (BYTE *)dest);
431af03003cSMatthias Ringwald     CryptReleaseContext(prov, 0);
432af03003cSMatthias Ringwald     return 1;
433af03003cSMatthias Ringwald }
434af03003cSMatthias Ringwald 
435bf2b6c37SMatthias Ringwald #elif (defined(unix) || defined(__linux__) || defined(__unix__) || defined(__unix) || \
436bf2b6c37SMatthias Ringwald     (defined(__APPLE__) && defined(__MACH__)) || defined(uECC_POSIX)) && !defined(uECC_NO_DEFAULT_RNG)
437af03003cSMatthias Ringwald 
438af03003cSMatthias Ringwald /* Some POSIX-like system with /dev/urandom or /dev/random. */
439af03003cSMatthias Ringwald #include <sys/types.h>
440af03003cSMatthias Ringwald #include <fcntl.h>
441af03003cSMatthias Ringwald #include <unistd.h>
442af03003cSMatthias Ringwald 
443af03003cSMatthias Ringwald #ifndef O_CLOEXEC
444af03003cSMatthias Ringwald     #define O_CLOEXEC 0
445af03003cSMatthias Ringwald #endif
446af03003cSMatthias Ringwald 
default_RNG(uint8_t * dest,unsigned size)447af03003cSMatthias Ringwald static int default_RNG(uint8_t *dest, unsigned size) {
448af03003cSMatthias Ringwald     int fd = open("/dev/urandom", O_RDONLY | O_CLOEXEC);
449af03003cSMatthias Ringwald     if (fd == -1) {
450af03003cSMatthias Ringwald         fd = open("/dev/random", O_RDONLY | O_CLOEXEC);
451af03003cSMatthias Ringwald         if (fd == -1) {
452af03003cSMatthias Ringwald             return 0;
453af03003cSMatthias Ringwald         }
454af03003cSMatthias Ringwald     }
455af03003cSMatthias Ringwald 
456af03003cSMatthias Ringwald     char *ptr = (char *)dest;
457af03003cSMatthias Ringwald     size_t left = size;
458af03003cSMatthias Ringwald     while (left > 0) {
459af03003cSMatthias Ringwald         ssize_t bytes_read = read(fd, ptr, left);
460af03003cSMatthias Ringwald         if (bytes_read <= 0) { // read failed
461af03003cSMatthias Ringwald             close(fd);
462af03003cSMatthias Ringwald             return 0;
463af03003cSMatthias Ringwald         }
464af03003cSMatthias Ringwald         left -= bytes_read;
465af03003cSMatthias Ringwald         ptr += bytes_read;
466af03003cSMatthias Ringwald     }
467af03003cSMatthias Ringwald 
468af03003cSMatthias Ringwald     close(fd);
469af03003cSMatthias Ringwald     return 1;
470af03003cSMatthias Ringwald }
471af03003cSMatthias Ringwald 
472af03003cSMatthias Ringwald #else /* Some other platform */
473af03003cSMatthias Ringwald 
default_RNG(uint8_t * dest,unsigned size)474af03003cSMatthias Ringwald static int default_RNG(uint8_t *dest, unsigned size) {
4759389122cSMatthias Ringwald     (void) dest;
4769389122cSMatthias Ringwald     (void) size;
477af03003cSMatthias Ringwald     return 0;
478af03003cSMatthias Ringwald }
479af03003cSMatthias Ringwald 
480af03003cSMatthias Ringwald #endif
481af03003cSMatthias Ringwald 
482af03003cSMatthias Ringwald static uECC_RNG_Function g_rng_function = &default_RNG;
483af03003cSMatthias Ringwald 
uECC_set_rng(uECC_RNG_Function rng_function)484af03003cSMatthias Ringwald void uECC_set_rng(uECC_RNG_Function rng_function) {
485af03003cSMatthias Ringwald     g_rng_function = rng_function;
486af03003cSMatthias Ringwald }
487af03003cSMatthias Ringwald 
488af03003cSMatthias Ringwald #ifdef __GNUC__ /* Only support GCC inline asm for now */
489af03003cSMatthias Ringwald     #if (uECC_ASM && (uECC_PLATFORM == uECC_avr))
490af03003cSMatthias Ringwald         #include "asm_avr.inc"
491af03003cSMatthias Ringwald     #endif
492af03003cSMatthias Ringwald 
493af03003cSMatthias Ringwald     #if (uECC_ASM && (uECC_PLATFORM == uECC_arm || uECC_PLATFORM == uECC_arm_thumb || \
494af03003cSMatthias Ringwald                       uECC_PLATFORM == uECC_arm_thumb2))
495af03003cSMatthias Ringwald         #include "asm_arm.inc"
496af03003cSMatthias Ringwald     #endif
497af03003cSMatthias Ringwald #endif
498af03003cSMatthias Ringwald 
499af03003cSMatthias Ringwald #if !asm_clear
vli_clear(uECC_word_t * vli)500af03003cSMatthias Ringwald static void vli_clear(uECC_word_t *vli) {
501af03003cSMatthias Ringwald     wordcount_t i;
502af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
503af03003cSMatthias Ringwald         vli[i] = 0;
504af03003cSMatthias Ringwald     }
505af03003cSMatthias Ringwald }
506af03003cSMatthias Ringwald #endif
507af03003cSMatthias Ringwald 
508af03003cSMatthias Ringwald /* Returns 1 if vli == 0, 0 otherwise. */
509af03003cSMatthias Ringwald #if !asm_isZero
vli_isZero(const uECC_word_t * vli)510af03003cSMatthias Ringwald static uECC_word_t vli_isZero(const uECC_word_t *vli) {
511af03003cSMatthias Ringwald     wordcount_t i;
512af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
513af03003cSMatthias Ringwald         if (vli[i]) {
514af03003cSMatthias Ringwald             return 0;
515af03003cSMatthias Ringwald         }
516af03003cSMatthias Ringwald     }
517af03003cSMatthias Ringwald     return 1;
518af03003cSMatthias Ringwald }
519af03003cSMatthias Ringwald #endif
520af03003cSMatthias Ringwald 
521af03003cSMatthias Ringwald /* Returns nonzero if bit 'bit' of vli is set. */
522af03003cSMatthias Ringwald #if !asm_testBit
vli_testBit(const uECC_word_t * vli,bitcount_t bit)523af03003cSMatthias Ringwald static uECC_word_t vli_testBit(const uECC_word_t *vli, bitcount_t bit) {
524af03003cSMatthias Ringwald     return (vli[bit >> uECC_WORD_BITS_SHIFT] & ((uECC_word_t)1 << (bit & uECC_WORD_BITS_MASK)));
525af03003cSMatthias Ringwald }
526af03003cSMatthias Ringwald #endif
527af03003cSMatthias Ringwald 
52880dcb211SMatthias Ringwald #ifdef ENABLE_MICO_ECC_ECDSA
52980dcb211SMatthias Ringwald 
530af03003cSMatthias Ringwald /* Counts the number of words in vli. */
531af03003cSMatthias Ringwald #if !asm_numBits
vli_numDigits(const uECC_word_t * vli,wordcount_t max_words)532af03003cSMatthias Ringwald static wordcount_t vli_numDigits(const uECC_word_t *vli, wordcount_t max_words) {
533af03003cSMatthias Ringwald     swordcount_t i;
534af03003cSMatthias Ringwald     /* Search from the end until we find a non-zero digit.
535af03003cSMatthias Ringwald        We do it in reverse because we expect that most digits will be nonzero. */
536af03003cSMatthias Ringwald     for (i = max_words - 1; i >= 0 && vli[i] == 0; --i) {
537af03003cSMatthias Ringwald     }
538af03003cSMatthias Ringwald 
539af03003cSMatthias Ringwald     return (i + 1);
540af03003cSMatthias Ringwald }
541af03003cSMatthias Ringwald 
542af03003cSMatthias Ringwald /* Counts the number of bits required to represent vli. */
vli_numBits(const uECC_word_t * vli,wordcount_t max_words)543af03003cSMatthias Ringwald static bitcount_t vli_numBits(const uECC_word_t *vli, wordcount_t max_words) {
544af03003cSMatthias Ringwald     uECC_word_t i;
545af03003cSMatthias Ringwald     uECC_word_t digit;
546af03003cSMatthias Ringwald 
547af03003cSMatthias Ringwald     wordcount_t num_digits = vli_numDigits(vli, max_words);
548af03003cSMatthias Ringwald     if (num_digits == 0) {
549af03003cSMatthias Ringwald         return 0;
550af03003cSMatthias Ringwald     }
551af03003cSMatthias Ringwald 
552af03003cSMatthias Ringwald     digit = vli[num_digits - 1];
553af03003cSMatthias Ringwald     for (i = 0; digit; ++i) {
554af03003cSMatthias Ringwald         digit >>= 1;
555af03003cSMatthias Ringwald     }
556af03003cSMatthias Ringwald 
557af03003cSMatthias Ringwald     return (((bitcount_t)(num_digits - 1) << uECC_WORD_BITS_SHIFT) + i);
558af03003cSMatthias Ringwald }
55980dcb211SMatthias Ringwald 
56080dcb211SMatthias Ringwald #endif /* ENABLE_MICO_ECC_ECDSA */
56180dcb211SMatthias Ringwald 
562af03003cSMatthias Ringwald #endif /* !asm_numBits */
563af03003cSMatthias Ringwald 
564af03003cSMatthias Ringwald /* Sets dest = src. */
565af03003cSMatthias Ringwald #if !asm_set
vli_set(uECC_word_t * dest,const uECC_word_t * src)566af03003cSMatthias Ringwald static void vli_set(uECC_word_t *dest, const uECC_word_t *src) {
567af03003cSMatthias Ringwald     wordcount_t i;
568af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
569af03003cSMatthias Ringwald         dest[i] = src[i];
570af03003cSMatthias Ringwald     }
571af03003cSMatthias Ringwald }
572af03003cSMatthias Ringwald #endif
573af03003cSMatthias Ringwald 
574af03003cSMatthias Ringwald /* Returns sign of left - right. */
575af03003cSMatthias Ringwald #if !asm_cmp
vli_cmp(const uECC_word_t * left,const uECC_word_t * right)576af03003cSMatthias Ringwald static cmpresult_t vli_cmp(const uECC_word_t *left, const uECC_word_t *right) {
577af03003cSMatthias Ringwald     swordcount_t i;
578af03003cSMatthias Ringwald     for (i = uECC_WORDS - 1; i >= 0; --i) {
579af03003cSMatthias Ringwald         if (left[i] > right[i]) {
580af03003cSMatthias Ringwald             return 1;
581af03003cSMatthias Ringwald         } else if (left[i] < right[i]) {
582af03003cSMatthias Ringwald             return -1;
583af03003cSMatthias Ringwald         }
584af03003cSMatthias Ringwald     }
585af03003cSMatthias Ringwald     return 0;
586af03003cSMatthias Ringwald }
587af03003cSMatthias Ringwald #endif
588af03003cSMatthias Ringwald 
58980dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_ECDSA
59080dcb211SMatthias Ringwald 
vli_equal(const uECC_word_t * left,const uECC_word_t * right)591af03003cSMatthias Ringwald static cmpresult_t vli_equal(const uECC_word_t *left, const uECC_word_t *right) {
592af03003cSMatthias Ringwald     uECC_word_t result = 0;
593af03003cSMatthias Ringwald     swordcount_t i;
594af03003cSMatthias Ringwald     for (i = uECC_WORDS - 1; i >= 0; --i) {
595af03003cSMatthias Ringwald         result |= (left[i] ^ right[i]);
596af03003cSMatthias Ringwald     }
597af03003cSMatthias Ringwald     return (result == 0);
598af03003cSMatthias Ringwald }
599af03003cSMatthias Ringwald 
60080dcb211SMatthias Ringwald #endif
60180dcb211SMatthias Ringwald 
602af03003cSMatthias Ringwald /* Computes vli = vli >> 1. */
603af03003cSMatthias Ringwald #if !asm_rshift1
vli_rshift1(uECC_word_t * vli)604af03003cSMatthias Ringwald static void vli_rshift1(uECC_word_t *vli) {
605af03003cSMatthias Ringwald     uECC_word_t *end = vli;
606af03003cSMatthias Ringwald     uECC_word_t carry = 0;
60741f9be70SMatthias Ringwald     uECC_word_t *vli_ = vli;
608af03003cSMatthias Ringwald 
60941f9be70SMatthias Ringwald     vli_ += uECC_WORDS;
61041f9be70SMatthias Ringwald     while (vli_-- > end) {
61141f9be70SMatthias Ringwald         uECC_word_t temp = *vli_;
61241f9be70SMatthias Ringwald         *vli_ = (temp >> 1) | carry;
613af03003cSMatthias Ringwald         carry = temp << (uECC_WORD_BITS - 1);
614af03003cSMatthias Ringwald     }
615af03003cSMatthias Ringwald }
616af03003cSMatthias Ringwald #endif
617af03003cSMatthias Ringwald 
618af03003cSMatthias Ringwald /* Computes result = left + right, returning carry. Can modify in place. */
619af03003cSMatthias Ringwald #if !asm_add
vli_add(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)620af03003cSMatthias Ringwald static uECC_word_t vli_add(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
621af03003cSMatthias Ringwald     uECC_word_t carry = 0;
622af03003cSMatthias Ringwald     wordcount_t i;
623af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
624af03003cSMatthias Ringwald         uECC_word_t sum = left[i] + right[i] + carry;
625af03003cSMatthias Ringwald         if (sum != left[i]) {
626af03003cSMatthias Ringwald             carry = (sum < left[i]);
627af03003cSMatthias Ringwald         }
628af03003cSMatthias Ringwald         result[i] = sum;
629af03003cSMatthias Ringwald     }
630af03003cSMatthias Ringwald     return carry;
631af03003cSMatthias Ringwald }
632af03003cSMatthias Ringwald #endif
633af03003cSMatthias Ringwald 
634af03003cSMatthias Ringwald /* Computes result = left - right, returning borrow. Can modify in place. */
635af03003cSMatthias Ringwald #if !asm_sub
vli_sub(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)636af03003cSMatthias Ringwald static uECC_word_t vli_sub(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
637af03003cSMatthias Ringwald     uECC_word_t borrow = 0;
638af03003cSMatthias Ringwald     wordcount_t i;
639af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
640af03003cSMatthias Ringwald         uECC_word_t diff = left[i] - right[i] - borrow;
641af03003cSMatthias Ringwald         if (diff != left[i]) {
642af03003cSMatthias Ringwald             borrow = (diff > left[i]);
643af03003cSMatthias Ringwald         }
644af03003cSMatthias Ringwald         result[i] = diff;
645af03003cSMatthias Ringwald     }
646af03003cSMatthias Ringwald     return borrow;
647af03003cSMatthias Ringwald }
648af03003cSMatthias Ringwald #endif
649af03003cSMatthias Ringwald 
650af03003cSMatthias Ringwald #if (!asm_mult || (uECC_SQUARE_FUNC && !asm_square) || uECC_CURVE == uECC_secp256k1)
muladd(uECC_word_t a,uECC_word_t b,uECC_word_t * r0,uECC_word_t * r1,uECC_word_t * r2)651af03003cSMatthias Ringwald static void muladd(uECC_word_t a,
652af03003cSMatthias Ringwald                    uECC_word_t b,
653af03003cSMatthias Ringwald                    uECC_word_t *r0,
654af03003cSMatthias Ringwald                    uECC_word_t *r1,
655af03003cSMatthias Ringwald                    uECC_word_t *r2) {
656af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 8 && !SUPPORTS_INT128
657af03003cSMatthias Ringwald     uint64_t a0 = a & 0xffffffffull;
658af03003cSMatthias Ringwald     uint64_t a1 = a >> 32;
659af03003cSMatthias Ringwald     uint64_t b0 = b & 0xffffffffull;
660af03003cSMatthias Ringwald     uint64_t b1 = b >> 32;
661af03003cSMatthias Ringwald 
662af03003cSMatthias Ringwald     uint64_t i0 = a0 * b0;
663af03003cSMatthias Ringwald     uint64_t i1 = a0 * b1;
664af03003cSMatthias Ringwald     uint64_t i2 = a1 * b0;
665af03003cSMatthias Ringwald     uint64_t i3 = a1 * b1;
666af03003cSMatthias Ringwald 
667af03003cSMatthias Ringwald     uint64_t p0, p1;
668af03003cSMatthias Ringwald 
669af03003cSMatthias Ringwald     i2 += (i0 >> 32);
670af03003cSMatthias Ringwald     i2 += i1;
671af03003cSMatthias Ringwald     if (i2 < i1) { // overflow
672af03003cSMatthias Ringwald         i3 += 0x100000000ull;
673af03003cSMatthias Ringwald     }
674af03003cSMatthias Ringwald 
675af03003cSMatthias Ringwald     p0 = (i0 & 0xffffffffull) | (i2 << 32);
676af03003cSMatthias Ringwald     p1 = i3 + (i2 >> 32);
677af03003cSMatthias Ringwald 
678af03003cSMatthias Ringwald     *r0 += p0;
679af03003cSMatthias Ringwald     *r1 += (p1 + (*r0 < p0));
680af03003cSMatthias Ringwald     *r2 += ((*r1 < p1) || (*r1 == p1 && *r0 < p0));
681af03003cSMatthias Ringwald #else
682af03003cSMatthias Ringwald     uECC_dword_t p = (uECC_dword_t)a * b;
683af03003cSMatthias Ringwald     uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0;
684af03003cSMatthias Ringwald     r01 += p;
685af03003cSMatthias Ringwald     *r2 += (r01 < p);
686af03003cSMatthias Ringwald     *r1 = r01 >> uECC_WORD_BITS;
687af03003cSMatthias Ringwald     *r0 = (uECC_word_t)r01;
688af03003cSMatthias Ringwald #endif
689af03003cSMatthias Ringwald }
690af03003cSMatthias Ringwald #define muladd_exists 1
691af03003cSMatthias Ringwald #endif
692af03003cSMatthias Ringwald 
693af03003cSMatthias Ringwald #if !asm_mult
vli_mult(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)694af03003cSMatthias Ringwald static void vli_mult(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
695af03003cSMatthias Ringwald     uECC_word_t r0 = 0;
696af03003cSMatthias Ringwald     uECC_word_t r1 = 0;
697af03003cSMatthias Ringwald     uECC_word_t r2 = 0;
698af03003cSMatthias Ringwald     wordcount_t i, k;
699af03003cSMatthias Ringwald 
700af03003cSMatthias Ringwald     /* Compute each digit of result in sequence, maintaining the carries. */
701af03003cSMatthias Ringwald     for (k = 0; k < uECC_WORDS; ++k) {
702af03003cSMatthias Ringwald         for (i = 0; i <= k; ++i) {
703af03003cSMatthias Ringwald             muladd(left[i], right[k - i], &r0, &r1, &r2);
704af03003cSMatthias Ringwald         }
705af03003cSMatthias Ringwald         result[k] = r0;
706af03003cSMatthias Ringwald         r0 = r1;
707af03003cSMatthias Ringwald         r1 = r2;
708af03003cSMatthias Ringwald         r2 = 0;
709af03003cSMatthias Ringwald     }
710af03003cSMatthias Ringwald     for (k = uECC_WORDS; k < uECC_WORDS * 2 - 1; ++k) {
711af03003cSMatthias Ringwald         for (i = (k + 1) - uECC_WORDS; i < uECC_WORDS; ++i) {
712af03003cSMatthias Ringwald             muladd(left[i], right[k - i], &r0, &r1, &r2);
713af03003cSMatthias Ringwald         }
714af03003cSMatthias Ringwald         result[k] = r0;
715af03003cSMatthias Ringwald         r0 = r1;
716af03003cSMatthias Ringwald         r1 = r2;
717af03003cSMatthias Ringwald         r2 = 0;
718af03003cSMatthias Ringwald     }
719af03003cSMatthias Ringwald     result[uECC_WORDS * 2 - 1] = r0;
720af03003cSMatthias Ringwald }
721af03003cSMatthias Ringwald #endif
722af03003cSMatthias Ringwald 
723af03003cSMatthias Ringwald #if uECC_SQUARE_FUNC
724af03003cSMatthias Ringwald 
725af03003cSMatthias Ringwald #if !asm_square
mul2add(uECC_word_t a,uECC_word_t b,uECC_word_t * r0,uECC_word_t * r1,uECC_word_t * r2)726af03003cSMatthias Ringwald static void mul2add(uECC_word_t a,
727af03003cSMatthias Ringwald                     uECC_word_t b,
728af03003cSMatthias Ringwald                     uECC_word_t *r0,
729af03003cSMatthias Ringwald                     uECC_word_t *r1,
730af03003cSMatthias Ringwald                     uECC_word_t *r2) {
731af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 8 && !SUPPORTS_INT128
732af03003cSMatthias Ringwald     uint64_t a0 = a & 0xffffffffull;
733af03003cSMatthias Ringwald     uint64_t a1 = a >> 32;
734af03003cSMatthias Ringwald     uint64_t b0 = b & 0xffffffffull;
735af03003cSMatthias Ringwald     uint64_t b1 = b >> 32;
736af03003cSMatthias Ringwald 
737af03003cSMatthias Ringwald     uint64_t i0 = a0 * b0;
738af03003cSMatthias Ringwald     uint64_t i1 = a0 * b1;
739af03003cSMatthias Ringwald     uint64_t i2 = a1 * b0;
740af03003cSMatthias Ringwald     uint64_t i3 = a1 * b1;
741af03003cSMatthias Ringwald 
742af03003cSMatthias Ringwald     uint64_t p0, p1;
743af03003cSMatthias Ringwald 
744af03003cSMatthias Ringwald     i2 += (i0 >> 32);
745af03003cSMatthias Ringwald     i2 += i1;
746af03003cSMatthias Ringwald     if (i2 < i1)
747af03003cSMatthias Ringwald     { // overflow
748af03003cSMatthias Ringwald         i3 += 0x100000000ull;
749af03003cSMatthias Ringwald     }
750af03003cSMatthias Ringwald 
751af03003cSMatthias Ringwald     p0 = (i0 & 0xffffffffull) | (i2 << 32);
752af03003cSMatthias Ringwald     p1 = i3 + (i2 >> 32);
753af03003cSMatthias Ringwald 
754af03003cSMatthias Ringwald     *r2 += (p1 >> 63);
755af03003cSMatthias Ringwald     p1 = (p1 << 1) | (p0 >> 63);
756af03003cSMatthias Ringwald     p0 <<= 1;
757af03003cSMatthias Ringwald 
758af03003cSMatthias Ringwald     *r0 += p0;
759af03003cSMatthias Ringwald     *r1 += (p1 + (*r0 < p0));
760af03003cSMatthias Ringwald     *r2 += ((*r1 < p1) || (*r1 == p1 && *r0 < p0));
761af03003cSMatthias Ringwald #else
762af03003cSMatthias Ringwald     uECC_dword_t p = (uECC_dword_t)a * b;
763af03003cSMatthias Ringwald     uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0;
764af03003cSMatthias Ringwald     *r2 += (p >> (uECC_WORD_BITS * 2 - 1));
765af03003cSMatthias Ringwald     p *= 2;
766af03003cSMatthias Ringwald     r01 += p;
767af03003cSMatthias Ringwald     *r2 += (r01 < p);
768af03003cSMatthias Ringwald     *r1 = r01 >> uECC_WORD_BITS;
769af03003cSMatthias Ringwald     *r0 = (uECC_word_t)r01;
770af03003cSMatthias Ringwald #endif
771af03003cSMatthias Ringwald }
772af03003cSMatthias Ringwald 
vli_square(uECC_word_t * result,const uECC_word_t * left)773af03003cSMatthias Ringwald static void vli_square(uECC_word_t *result, const uECC_word_t *left) {
774af03003cSMatthias Ringwald     uECC_word_t r0 = 0;
775af03003cSMatthias Ringwald     uECC_word_t r1 = 0;
776af03003cSMatthias Ringwald     uECC_word_t r2 = 0;
777af03003cSMatthias Ringwald 
778af03003cSMatthias Ringwald     wordcount_t i, k;
779af03003cSMatthias Ringwald 
780af03003cSMatthias Ringwald     for (k = 0; k < uECC_WORDS * 2 - 1; ++k) {
781af03003cSMatthias Ringwald         uECC_word_t min = (k < uECC_WORDS ? 0 : (k + 1) - uECC_WORDS);
782af03003cSMatthias Ringwald         for (i = min; i <= k && i <= k - i; ++i) {
783af03003cSMatthias Ringwald             if (i < k-i) {
784af03003cSMatthias Ringwald                 mul2add(left[i], left[k - i], &r0, &r1, &r2);
785af03003cSMatthias Ringwald             } else {
786af03003cSMatthias Ringwald                 muladd(left[i], left[k - i], &r0, &r1, &r2);
787af03003cSMatthias Ringwald             }
788af03003cSMatthias Ringwald         }
789af03003cSMatthias Ringwald         result[k] = r0;
790af03003cSMatthias Ringwald         r0 = r1;
791af03003cSMatthias Ringwald         r1 = r2;
792af03003cSMatthias Ringwald         r2 = 0;
793af03003cSMatthias Ringwald     }
794af03003cSMatthias Ringwald 
795af03003cSMatthias Ringwald     result[uECC_WORDS * 2 - 1] = r0;
796af03003cSMatthias Ringwald }
797af03003cSMatthias Ringwald #endif
798af03003cSMatthias Ringwald 
799af03003cSMatthias Ringwald #else /* uECC_SQUARE_FUNC */
800af03003cSMatthias Ringwald 
801af03003cSMatthias Ringwald #define vli_square(result, left, size) vli_mult((result), (left), (left), (size))
802af03003cSMatthias Ringwald 
803af03003cSMatthias Ringwald #endif /* uECC_SQUARE_FUNC */
804af03003cSMatthias Ringwald 
805af03003cSMatthias Ringwald 
806af03003cSMatthias Ringwald /* Computes result = (left + right) % mod.
807af03003cSMatthias Ringwald    Assumes that left < mod and right < mod, and that result does not overlap mod. */
808af03003cSMatthias Ringwald #if !asm_modAdd
vli_modAdd(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right,const uECC_word_t * mod)809af03003cSMatthias Ringwald static void vli_modAdd(uECC_word_t *result,
810af03003cSMatthias Ringwald                        const uECC_word_t *left,
811af03003cSMatthias Ringwald                        const uECC_word_t *right,
812af03003cSMatthias Ringwald                        const uECC_word_t *mod) {
813af03003cSMatthias Ringwald     uECC_word_t carry = vli_add(result, left, right);
814af03003cSMatthias Ringwald     if (carry || vli_cmp(result, mod) >= 0) {
815af03003cSMatthias Ringwald         /* result > mod (result = mod + remainder), so subtract mod to get remainder. */
816af03003cSMatthias Ringwald         vli_sub(result, result, mod);
817af03003cSMatthias Ringwald     }
818af03003cSMatthias Ringwald }
819af03003cSMatthias Ringwald #endif
820af03003cSMatthias Ringwald 
821af03003cSMatthias Ringwald /* Computes result = (left - right) % mod.
822af03003cSMatthias Ringwald    Assumes that left < mod and right < mod, and that result does not overlap mod. */
823af03003cSMatthias Ringwald #if !asm_modSub
vli_modSub(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right,const uECC_word_t * mod)824af03003cSMatthias Ringwald static void vli_modSub(uECC_word_t *result,
825af03003cSMatthias Ringwald                        const uECC_word_t *left,
826af03003cSMatthias Ringwald                        const uECC_word_t *right,
827af03003cSMatthias Ringwald                        const uECC_word_t *mod) {
828af03003cSMatthias Ringwald     uECC_word_t l_borrow = vli_sub(result, left, right);
829af03003cSMatthias Ringwald     if (l_borrow) {
830af03003cSMatthias Ringwald         /* In this case, result == -diff == (max int) - diff. Since -x % d == d - x,
831af03003cSMatthias Ringwald            we can get the correct result from result + mod (with overflow). */
832af03003cSMatthias Ringwald         vli_add(result, result, mod);
833af03003cSMatthias Ringwald     }
834af03003cSMatthias Ringwald }
835af03003cSMatthias Ringwald #endif
836af03003cSMatthias Ringwald 
837af03003cSMatthias Ringwald #if !asm_modSub_fast
838af03003cSMatthias Ringwald     #define vli_modSub_fast(result, left, right) vli_modSub((result), (left), (right), curve_p)
839af03003cSMatthias Ringwald #endif
840af03003cSMatthias Ringwald 
841af03003cSMatthias Ringwald #if !asm_mmod_fast
842af03003cSMatthias Ringwald 
843af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1 || uECC_CURVE == uECC_secp256k1)
844af03003cSMatthias Ringwald /* omega_mult() is defined farther below for the different curves / word sizes */
845af03003cSMatthias Ringwald static void omega_mult(uECC_word_t * RESTRICT result, const uECC_word_t * RESTRICT right);
846af03003cSMatthias Ringwald 
847af03003cSMatthias Ringwald /* Computes result = product % curve_p
848af03003cSMatthias Ringwald     see http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf page 354
849af03003cSMatthias Ringwald 
850af03003cSMatthias Ringwald     Note that this only works if log2(omega) < log2(p) / 2 */
vli_mmod_fast(uECC_word_t * RESTRICT result,uECC_word_t * RESTRICT product)851af03003cSMatthias Ringwald static void vli_mmod_fast(uECC_word_t *RESTRICT result, uECC_word_t *RESTRICT product) {
852af03003cSMatthias Ringwald     uECC_word_t tmp[2 * uECC_WORDS];
853af03003cSMatthias Ringwald     uECC_word_t carry;
854af03003cSMatthias Ringwald 
855af03003cSMatthias Ringwald     vli_clear(tmp);
856af03003cSMatthias Ringwald     vli_clear(tmp + uECC_WORDS);
857af03003cSMatthias Ringwald 
858af03003cSMatthias Ringwald     omega_mult(tmp, product + uECC_WORDS); /* (Rq, q) = q * c */
859af03003cSMatthias Ringwald 
860af03003cSMatthias Ringwald     carry = vli_add(result, product, tmp); /* (C, r) = r + q       */
861af03003cSMatthias Ringwald     vli_clear(product);
862af03003cSMatthias Ringwald     omega_mult(product, tmp + uECC_WORDS); /* Rq*c */
863af03003cSMatthias Ringwald     carry += vli_add(result, result, product); /* (C1, r) = r + Rq*c */
864af03003cSMatthias Ringwald 
865af03003cSMatthias Ringwald     while (carry > 0) {
866af03003cSMatthias Ringwald         --carry;
867af03003cSMatthias Ringwald         vli_sub(result, result, curve_p);
868af03003cSMatthias Ringwald     }
869af03003cSMatthias Ringwald     if (vli_cmp(result, curve_p) > 0) {
870af03003cSMatthias Ringwald         vli_sub(result, result, curve_p);
871af03003cSMatthias Ringwald     }
872af03003cSMatthias Ringwald }
873af03003cSMatthias Ringwald 
874af03003cSMatthias Ringwald #endif
875af03003cSMatthias Ringwald 
876af03003cSMatthias Ringwald #if uECC_CURVE == uECC_secp160r1
877af03003cSMatthias Ringwald 
878af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
omega_mult(uint8_t * RESTRICT result,const uint8_t * RESTRICT right)879af03003cSMatthias Ringwald static void omega_mult(uint8_t * RESTRICT result, const uint8_t * RESTRICT right) {
880af03003cSMatthias Ringwald     uint8_t carry;
881af03003cSMatthias Ringwald     uint8_t i;
882af03003cSMatthias Ringwald 
883af03003cSMatthias Ringwald     /* Multiply by (2^31 + 1). */
884af03003cSMatthias Ringwald     vli_set(result + 4, right); /* 2^32 */
885af03003cSMatthias Ringwald     vli_rshift1(result + 4); /* 2^31 */
886af03003cSMatthias Ringwald     result[3] = right[0] << 7; /* get last bit from shift */
887af03003cSMatthias Ringwald 
888af03003cSMatthias Ringwald     carry = vli_add(result, result, right); /* 2^31 + 1 */
889af03003cSMatthias Ringwald     for (i = uECC_WORDS; carry; ++i) {
890af03003cSMatthias Ringwald         uint16_t sum = (uint16_t)result[i] + carry;
891af03003cSMatthias Ringwald         result[i] = (uint8_t)sum;
892af03003cSMatthias Ringwald         carry = sum >> 8;
893af03003cSMatthias Ringwald     }
894af03003cSMatthias Ringwald }
895af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
omega_mult(uint32_t * RESTRICT result,const uint32_t * RESTRICT right)896af03003cSMatthias Ringwald static void omega_mult(uint32_t * RESTRICT result, const uint32_t * RESTRICT right) {
897af03003cSMatthias Ringwald     uint32_t carry;
898af03003cSMatthias Ringwald     unsigned i;
899af03003cSMatthias Ringwald 
900af03003cSMatthias Ringwald     /* Multiply by (2^31 + 1). */
901af03003cSMatthias Ringwald     vli_set(result + 1, right); /* 2^32 */
902af03003cSMatthias Ringwald     vli_rshift1(result + 1); /* 2^31 */
903af03003cSMatthias Ringwald     result[0] = right[0] << 31; /* get last bit from shift */
904af03003cSMatthias Ringwald 
905af03003cSMatthias Ringwald     carry = vli_add(result, result, right); /* 2^31 + 1 */
906af03003cSMatthias Ringwald     for (i = uECC_WORDS; carry; ++i) {
907af03003cSMatthias Ringwald         uint64_t sum = (uint64_t)result[i] + carry;
908af03003cSMatthias Ringwald         result[i] = (uint32_t)sum;
909af03003cSMatthias Ringwald         carry = sum >> 32;
910af03003cSMatthias Ringwald     }
911af03003cSMatthias Ringwald }
912af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
913af03003cSMatthias Ringwald 
914af03003cSMatthias Ringwald #elif uECC_CURVE == uECC_secp192r1
915af03003cSMatthias Ringwald 
916af03003cSMatthias Ringwald /* Computes result = product % curve_p.
917af03003cSMatthias Ringwald    See algorithm 5 and 6 from http://www.isys.uni-klu.ac.at/PDF/2001-0126-MT.pdf */
918af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
vli_mmod_fast(uint8_t * RESTRICT result,uint8_t * RESTRICT product)919af03003cSMatthias Ringwald static void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) {
920af03003cSMatthias Ringwald     uint8_t tmp[uECC_WORDS];
921af03003cSMatthias Ringwald     uint8_t carry;
922af03003cSMatthias Ringwald 
923af03003cSMatthias Ringwald     vli_set(result, product);
924af03003cSMatthias Ringwald 
925af03003cSMatthias Ringwald     vli_set(tmp, &product[24]);
926af03003cSMatthias Ringwald     carry = vli_add(result, result, tmp);
927af03003cSMatthias Ringwald 
928af03003cSMatthias Ringwald     tmp[0] = tmp[1] = tmp[2] = tmp[3] = tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0;
929af03003cSMatthias Ringwald     tmp[8] = product[24]; tmp[9] = product[25]; tmp[10] = product[26]; tmp[11] = product[27];
930af03003cSMatthias Ringwald     tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31];
931af03003cSMatthias Ringwald     tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35];
932af03003cSMatthias Ringwald     tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39];
933af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
934af03003cSMatthias Ringwald 
935af03003cSMatthias Ringwald     tmp[0] = tmp[8] = product[40];
936af03003cSMatthias Ringwald     tmp[1] = tmp[9] = product[41];
937af03003cSMatthias Ringwald     tmp[2] = tmp[10] = product[42];
938af03003cSMatthias Ringwald     tmp[3] = tmp[11] = product[43];
939af03003cSMatthias Ringwald     tmp[4] = tmp[12] = product[44];
940af03003cSMatthias Ringwald     tmp[5] = tmp[13] = product[45];
941af03003cSMatthias Ringwald     tmp[6] = tmp[14] = product[46];
942af03003cSMatthias Ringwald     tmp[7] = tmp[15] = product[47];
943af03003cSMatthias Ringwald     tmp[16] = tmp[17] = tmp[18] = tmp[19] = tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0;
944af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
945af03003cSMatthias Ringwald 
946af03003cSMatthias Ringwald     while (carry || vli_cmp(curve_p, result) != 1) {
947af03003cSMatthias Ringwald         carry -= vli_sub(result, result, curve_p);
948af03003cSMatthias Ringwald     }
949af03003cSMatthias Ringwald }
950af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
vli_mmod_fast(uint32_t * RESTRICT result,uint32_t * RESTRICT product)951af03003cSMatthias Ringwald static void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product) {
952af03003cSMatthias Ringwald     uint32_t tmp[uECC_WORDS];
953af03003cSMatthias Ringwald     int carry;
954af03003cSMatthias Ringwald 
955af03003cSMatthias Ringwald     vli_set(result, product);
956af03003cSMatthias Ringwald 
957af03003cSMatthias Ringwald     vli_set(tmp, &product[6]);
958af03003cSMatthias Ringwald     carry = vli_add(result, result, tmp);
959af03003cSMatthias Ringwald 
960af03003cSMatthias Ringwald     tmp[0] = tmp[1] = 0;
961af03003cSMatthias Ringwald     tmp[2] = product[6];
962af03003cSMatthias Ringwald     tmp[3] = product[7];
963af03003cSMatthias Ringwald     tmp[4] = product[8];
964af03003cSMatthias Ringwald     tmp[5] = product[9];
965af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
966af03003cSMatthias Ringwald 
967af03003cSMatthias Ringwald     tmp[0] = tmp[2] = product[10];
968af03003cSMatthias Ringwald     tmp[1] = tmp[3] = product[11];
969af03003cSMatthias Ringwald     tmp[4] = tmp[5] = 0;
970af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
971af03003cSMatthias Ringwald 
972af03003cSMatthias Ringwald     while (carry || vli_cmp(curve_p, result) != 1) {
973af03003cSMatthias Ringwald         carry -= vli_sub(result, result, curve_p);
974af03003cSMatthias Ringwald     }
975af03003cSMatthias Ringwald }
976af03003cSMatthias Ringwald #else
vli_mmod_fast(uint64_t * RESTRICT result,uint64_t * RESTRICT product)977af03003cSMatthias Ringwald static void vli_mmod_fast(uint64_t *RESTRICT result, uint64_t *RESTRICT product) {
978af03003cSMatthias Ringwald     uint64_t tmp[uECC_WORDS];
979af03003cSMatthias Ringwald     int carry;
980af03003cSMatthias Ringwald 
981af03003cSMatthias Ringwald     vli_set(result, product);
982af03003cSMatthias Ringwald 
983af03003cSMatthias Ringwald     vli_set(tmp, &product[3]);
984af03003cSMatthias Ringwald     carry = vli_add(result, result, tmp);
985af03003cSMatthias Ringwald 
986af03003cSMatthias Ringwald     tmp[0] = 0;
987af03003cSMatthias Ringwald     tmp[1] = product[3];
988af03003cSMatthias Ringwald     tmp[2] = product[4];
989af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
990af03003cSMatthias Ringwald 
991af03003cSMatthias Ringwald     tmp[0] = tmp[1] = product[5];
992af03003cSMatthias Ringwald     tmp[2] = 0;
993af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
994af03003cSMatthias Ringwald 
995af03003cSMatthias Ringwald     while (carry || vli_cmp(curve_p, result) != 1) {
996af03003cSMatthias Ringwald         carry -= vli_sub(result, result, curve_p);
997af03003cSMatthias Ringwald     }
998af03003cSMatthias Ringwald }
999af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
1000af03003cSMatthias Ringwald 
1001af03003cSMatthias Ringwald #elif uECC_CURVE == uECC_secp256r1
1002af03003cSMatthias Ringwald 
1003af03003cSMatthias Ringwald /* Computes result = product % curve_p
1004*c824d78cSMatthias Ringwald    from www.nsa.gov/ia/_files/nist-routines.pdf */
1005af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
vli_mmod_fast(uint8_t * RESTRICT result,uint8_t * RESTRICT product)1006af03003cSMatthias Ringwald static void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) {
1007af03003cSMatthias Ringwald     uint8_t tmp[uECC_BYTES];
1008af03003cSMatthias Ringwald     int8_t carry;
1009af03003cSMatthias Ringwald 
1010af03003cSMatthias Ringwald     /* t */
1011af03003cSMatthias Ringwald     vli_set(result, product);
1012af03003cSMatthias Ringwald 
1013af03003cSMatthias Ringwald     /* s1 */
1014af03003cSMatthias Ringwald     tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0;
1015af03003cSMatthias Ringwald     tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0;
1016af03003cSMatthias Ringwald     tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0;
1017af03003cSMatthias Ringwald     tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47];
1018af03003cSMatthias Ringwald     tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51];
1019af03003cSMatthias Ringwald     tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55];
1020af03003cSMatthias Ringwald     tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59];
1021af03003cSMatthias Ringwald     tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63];
1022af03003cSMatthias Ringwald     carry = vli_add(tmp, tmp, tmp);
1023af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1024af03003cSMatthias Ringwald 
1025af03003cSMatthias Ringwald     /* s2 */
1026af03003cSMatthias Ringwald     tmp[12] = product[48]; tmp[13] = product[49]; tmp[14] = product[50]; tmp[15] = product[51];
1027af03003cSMatthias Ringwald     tmp[16] = product[52]; tmp[17] = product[53]; tmp[18] = product[54]; tmp[19] = product[55];
1028af03003cSMatthias Ringwald     tmp[20] = product[56]; tmp[21] = product[57]; tmp[22] = product[58]; tmp[23] = product[59];
1029af03003cSMatthias Ringwald     tmp[24] = product[60]; tmp[25] = product[61]; tmp[26] = product[62]; tmp[27] = product[63];
1030af03003cSMatthias Ringwald     tmp[28] = tmp[29] = tmp[30] = tmp[31] = 0;
1031af03003cSMatthias Ringwald     carry += vli_add(tmp, tmp, tmp);
1032af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1033af03003cSMatthias Ringwald 
1034af03003cSMatthias Ringwald     /* s3 */
1035af03003cSMatthias Ringwald     tmp[0] = product[32]; tmp[1] = product[33]; tmp[2] = product[34]; tmp[3] = product[35];
1036af03003cSMatthias Ringwald     tmp[4] = product[36]; tmp[5] = product[37]; tmp[6] = product[38]; tmp[7] = product[39];
1037af03003cSMatthias Ringwald     tmp[8] = product[40]; tmp[9] = product[41]; tmp[10] = product[42]; tmp[11] = product[43];
1038af03003cSMatthias Ringwald     tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0;
1039af03003cSMatthias Ringwald     tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0;
1040af03003cSMatthias Ringwald     tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0;
1041af03003cSMatthias Ringwald     tmp[24] = product[56]; tmp[25] = product[57]; tmp[26] = product[58]; tmp[27] = product[59];
1042af03003cSMatthias Ringwald     tmp[28] = product[60]; tmp[29] = product[61]; tmp[30] = product[62]; tmp[31] = product[63];
1043af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1044af03003cSMatthias Ringwald 
1045af03003cSMatthias Ringwald     /* s4 */
1046af03003cSMatthias Ringwald     tmp[0] = product[36]; tmp[1] = product[37]; tmp[2] = product[38]; tmp[3] = product[39];
1047af03003cSMatthias Ringwald     tmp[4] = product[40]; tmp[5] = product[41]; tmp[6] = product[42]; tmp[7] = product[43];
1048af03003cSMatthias Ringwald     tmp[8] = product[44]; tmp[9] = product[45]; tmp[10] = product[46]; tmp[11] = product[47];
1049af03003cSMatthias Ringwald     tmp[12] = product[52]; tmp[13] = product[53]; tmp[14] = product[54]; tmp[15] = product[55];
1050af03003cSMatthias Ringwald     tmp[16] = product[56]; tmp[17] = product[57]; tmp[18] = product[58]; tmp[19] = product[59];
1051af03003cSMatthias Ringwald     tmp[20] = product[60]; tmp[21] = product[61]; tmp[22] = product[62]; tmp[23] = product[63];
1052af03003cSMatthias Ringwald     tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55];
1053af03003cSMatthias Ringwald     tmp[28] = product[32]; tmp[29] = product[33]; tmp[30] = product[34]; tmp[31] = product[35];
1054af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1055af03003cSMatthias Ringwald 
1056af03003cSMatthias Ringwald     /* d1 */
1057af03003cSMatthias Ringwald     tmp[0] = product[44]; tmp[1] = product[45]; tmp[2] = product[46]; tmp[3] = product[47];
1058af03003cSMatthias Ringwald     tmp[4] = product[48]; tmp[5] = product[49]; tmp[6] = product[50]; tmp[7] = product[51];
1059af03003cSMatthias Ringwald     tmp[8] = product[52]; tmp[9] = product[53]; tmp[10] = product[54]; tmp[11] = product[55];
1060af03003cSMatthias Ringwald     tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0;
1061af03003cSMatthias Ringwald     tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0;
1062af03003cSMatthias Ringwald     tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0;
1063af03003cSMatthias Ringwald     tmp[24] = product[32]; tmp[25] = product[33]; tmp[26] = product[34]; tmp[27] = product[35];
1064af03003cSMatthias Ringwald     tmp[28] = product[40]; tmp[29] = product[41]; tmp[30] = product[42]; tmp[31] = product[43];
1065af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1066af03003cSMatthias Ringwald 
1067af03003cSMatthias Ringwald     /* d2 */
1068af03003cSMatthias Ringwald     tmp[0] = product[48]; tmp[1] = product[49]; tmp[2] = product[50]; tmp[3] = product[51];
1069af03003cSMatthias Ringwald     tmp[4] = product[52]; tmp[5] = product[53]; tmp[6] = product[54]; tmp[7] = product[55];
1070af03003cSMatthias Ringwald     tmp[8] = product[56]; tmp[9] = product[57]; tmp[10] = product[58]; tmp[11] = product[59];
1071af03003cSMatthias Ringwald     tmp[12] = product[60]; tmp[13] = product[61]; tmp[14] = product[62]; tmp[15] = product[63];
1072af03003cSMatthias Ringwald     tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0;
1073af03003cSMatthias Ringwald     tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0;
1074af03003cSMatthias Ringwald     tmp[24] = product[36]; tmp[25] = product[37]; tmp[26] = product[38]; tmp[27] = product[39];
1075af03003cSMatthias Ringwald     tmp[28] = product[44]; tmp[29] = product[45]; tmp[30] = product[46]; tmp[31] = product[47];
1076af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1077af03003cSMatthias Ringwald 
1078af03003cSMatthias Ringwald     /* d3 */
1079af03003cSMatthias Ringwald     tmp[0] = product[52]; tmp[1] = product[53]; tmp[2] = product[54]; tmp[3] = product[55];
1080af03003cSMatthias Ringwald     tmp[4] = product[56]; tmp[5] = product[57]; tmp[6] = product[58]; tmp[7] = product[59];
1081af03003cSMatthias Ringwald     tmp[8] = product[60]; tmp[9] = product[61]; tmp[10] = product[62]; tmp[11] = product[63];
1082af03003cSMatthias Ringwald     tmp[12] = product[32]; tmp[13] = product[33]; tmp[14] = product[34]; tmp[15] = product[35];
1083af03003cSMatthias Ringwald     tmp[16] = product[36]; tmp[17] = product[37]; tmp[18] = product[38]; tmp[19] = product[39];
1084af03003cSMatthias Ringwald     tmp[20] = product[40]; tmp[21] = product[41]; tmp[22] = product[42]; tmp[23] = product[43];
1085af03003cSMatthias Ringwald     tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0;
1086af03003cSMatthias Ringwald     tmp[28] = product[48]; tmp[29] = product[49]; tmp[30] = product[50]; tmp[31] = product[51];
1087af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1088af03003cSMatthias Ringwald 
1089af03003cSMatthias Ringwald     /* d4 */
1090af03003cSMatthias Ringwald     tmp[0] = product[56]; tmp[1] = product[57]; tmp[2] = product[58]; tmp[3] = product[59];
1091af03003cSMatthias Ringwald     tmp[4] = product[60]; tmp[5] = product[61]; tmp[6] = product[62]; tmp[7] = product[63];
1092af03003cSMatthias Ringwald     tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0;
1093af03003cSMatthias Ringwald     tmp[12] = product[36]; tmp[13] = product[37]; tmp[14] = product[38]; tmp[15] = product[39];
1094af03003cSMatthias Ringwald     tmp[16] = product[40]; tmp[17] = product[41]; tmp[18] = product[42]; tmp[19] = product[43];
1095af03003cSMatthias Ringwald     tmp[20] = product[44]; tmp[21] = product[45]; tmp[22] = product[46]; tmp[23] = product[47];
1096af03003cSMatthias Ringwald     tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0;
1097af03003cSMatthias Ringwald     tmp[28] = product[52]; tmp[29] = product[53]; tmp[30] = product[54]; tmp[31] = product[55];
1098af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1099af03003cSMatthias Ringwald 
1100af03003cSMatthias Ringwald     if (carry < 0) {
1101af03003cSMatthias Ringwald         do {
1102af03003cSMatthias Ringwald             carry += vli_add(result, result, curve_p);
1103af03003cSMatthias Ringwald         } while (carry < 0);
1104af03003cSMatthias Ringwald     } else {
1105af03003cSMatthias Ringwald         while (carry || vli_cmp(curve_p, result) != 1) {
1106af03003cSMatthias Ringwald             carry -= vli_sub(result, result, curve_p);
1107af03003cSMatthias Ringwald         }
1108af03003cSMatthias Ringwald     }
1109af03003cSMatthias Ringwald }
1110af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
vli_mmod_fast(uint32_t * RESTRICT result,uint32_t * RESTRICT product)1111af03003cSMatthias Ringwald static void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product) {
1112af03003cSMatthias Ringwald     uint32_t tmp[uECC_WORDS];
1113af03003cSMatthias Ringwald     int carry;
1114af03003cSMatthias Ringwald 
1115af03003cSMatthias Ringwald     /* t */
1116af03003cSMatthias Ringwald     vli_set(result, product);
1117af03003cSMatthias Ringwald 
1118af03003cSMatthias Ringwald     /* s1 */
1119af03003cSMatthias Ringwald     tmp[0] = tmp[1] = tmp[2] = 0;
1120af03003cSMatthias Ringwald     tmp[3] = product[11];
1121af03003cSMatthias Ringwald     tmp[4] = product[12];
1122af03003cSMatthias Ringwald     tmp[5] = product[13];
1123af03003cSMatthias Ringwald     tmp[6] = product[14];
1124af03003cSMatthias Ringwald     tmp[7] = product[15];
1125af03003cSMatthias Ringwald     carry = vli_add(tmp, tmp, tmp);
1126af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1127af03003cSMatthias Ringwald 
1128af03003cSMatthias Ringwald     /* s2 */
1129af03003cSMatthias Ringwald     tmp[3] = product[12];
1130af03003cSMatthias Ringwald     tmp[4] = product[13];
1131af03003cSMatthias Ringwald     tmp[5] = product[14];
1132af03003cSMatthias Ringwald     tmp[6] = product[15];
1133af03003cSMatthias Ringwald     tmp[7] = 0;
1134af03003cSMatthias Ringwald     carry += vli_add(tmp, tmp, tmp);
1135af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1136af03003cSMatthias Ringwald 
1137af03003cSMatthias Ringwald     /* s3 */
1138af03003cSMatthias Ringwald     tmp[0] = product[8];
1139af03003cSMatthias Ringwald     tmp[1] = product[9];
1140af03003cSMatthias Ringwald     tmp[2] = product[10];
1141af03003cSMatthias Ringwald     tmp[3] = tmp[4] = tmp[5] = 0;
1142af03003cSMatthias Ringwald     tmp[6] = product[14];
1143af03003cSMatthias Ringwald     tmp[7] = product[15];
1144af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1145af03003cSMatthias Ringwald 
1146af03003cSMatthias Ringwald     /* s4 */
1147af03003cSMatthias Ringwald     tmp[0] = product[9];
1148af03003cSMatthias Ringwald     tmp[1] = product[10];
1149af03003cSMatthias Ringwald     tmp[2] = product[11];
1150af03003cSMatthias Ringwald     tmp[3] = product[13];
1151af03003cSMatthias Ringwald     tmp[4] = product[14];
1152af03003cSMatthias Ringwald     tmp[5] = product[15];
1153af03003cSMatthias Ringwald     tmp[6] = product[13];
1154af03003cSMatthias Ringwald     tmp[7] = product[8];
1155af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1156af03003cSMatthias Ringwald 
1157af03003cSMatthias Ringwald     /* d1 */
1158af03003cSMatthias Ringwald     tmp[0] = product[11];
1159af03003cSMatthias Ringwald     tmp[1] = product[12];
1160af03003cSMatthias Ringwald     tmp[2] = product[13];
1161af03003cSMatthias Ringwald     tmp[3] = tmp[4] = tmp[5] = 0;
1162af03003cSMatthias Ringwald     tmp[6] = product[8];
1163af03003cSMatthias Ringwald     tmp[7] = product[10];
1164af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1165af03003cSMatthias Ringwald 
1166af03003cSMatthias Ringwald     /* d2 */
1167af03003cSMatthias Ringwald     tmp[0] = product[12];
1168af03003cSMatthias Ringwald     tmp[1] = product[13];
1169af03003cSMatthias Ringwald     tmp[2] = product[14];
1170af03003cSMatthias Ringwald     tmp[3] = product[15];
1171af03003cSMatthias Ringwald     tmp[4] = tmp[5] = 0;
1172af03003cSMatthias Ringwald     tmp[6] = product[9];
1173af03003cSMatthias Ringwald     tmp[7] = product[11];
1174af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1175af03003cSMatthias Ringwald 
1176af03003cSMatthias Ringwald     /* d3 */
1177af03003cSMatthias Ringwald     tmp[0] = product[13];
1178af03003cSMatthias Ringwald     tmp[1] = product[14];
1179af03003cSMatthias Ringwald     tmp[2] = product[15];
1180af03003cSMatthias Ringwald     tmp[3] = product[8];
1181af03003cSMatthias Ringwald     tmp[4] = product[9];
1182af03003cSMatthias Ringwald     tmp[5] = product[10];
1183af03003cSMatthias Ringwald     tmp[6] = 0;
1184af03003cSMatthias Ringwald     tmp[7] = product[12];
1185af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1186af03003cSMatthias Ringwald 
1187af03003cSMatthias Ringwald     /* d4 */
1188af03003cSMatthias Ringwald     tmp[0] = product[14];
1189af03003cSMatthias Ringwald     tmp[1] = product[15];
1190af03003cSMatthias Ringwald     tmp[2] = 0;
1191af03003cSMatthias Ringwald     tmp[3] = product[9];
1192af03003cSMatthias Ringwald     tmp[4] = product[10];
1193af03003cSMatthias Ringwald     tmp[5] = product[11];
1194af03003cSMatthias Ringwald     tmp[6] = 0;
1195af03003cSMatthias Ringwald     tmp[7] = product[13];
1196af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1197af03003cSMatthias Ringwald 
1198af03003cSMatthias Ringwald     if (carry < 0) {
1199af03003cSMatthias Ringwald         do {
1200af03003cSMatthias Ringwald             carry += vli_add(result, result, curve_p);
1201af03003cSMatthias Ringwald         } while (carry < 0);
1202af03003cSMatthias Ringwald     } else {
1203af03003cSMatthias Ringwald         while (carry || vli_cmp(curve_p, result) != 1) {
1204af03003cSMatthias Ringwald             carry -= vli_sub(result, result, curve_p);
1205af03003cSMatthias Ringwald         }
1206af03003cSMatthias Ringwald     }
1207af03003cSMatthias Ringwald }
1208af03003cSMatthias Ringwald #else
vli_mmod_fast(uint64_t * RESTRICT result,uint64_t * RESTRICT product)1209af03003cSMatthias Ringwald static void vli_mmod_fast(uint64_t *RESTRICT result, uint64_t *RESTRICT product) {
1210af03003cSMatthias Ringwald     uint64_t tmp[uECC_WORDS];
1211af03003cSMatthias Ringwald     int carry;
1212af03003cSMatthias Ringwald 
1213af03003cSMatthias Ringwald     /* t */
1214af03003cSMatthias Ringwald     vli_set(result, product);
1215af03003cSMatthias Ringwald 
1216af03003cSMatthias Ringwald     /* s1 */
1217af03003cSMatthias Ringwald     tmp[0] = 0;
1218af03003cSMatthias Ringwald     tmp[1] = product[5] & 0xffffffff00000000ull;
1219af03003cSMatthias Ringwald     tmp[2] = product[6];
1220af03003cSMatthias Ringwald     tmp[3] = product[7];
1221af03003cSMatthias Ringwald     carry = vli_add(tmp, tmp, tmp);
1222af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1223af03003cSMatthias Ringwald 
1224af03003cSMatthias Ringwald     /* s2 */
1225af03003cSMatthias Ringwald     tmp[1] = product[6] << 32;
1226af03003cSMatthias Ringwald     tmp[2] = (product[6] >> 32) | (product[7] << 32);
1227af03003cSMatthias Ringwald     tmp[3] = product[7] >> 32;
1228af03003cSMatthias Ringwald     carry += vli_add(tmp, tmp, tmp);
1229af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1230af03003cSMatthias Ringwald 
1231af03003cSMatthias Ringwald     /* s3 */
1232af03003cSMatthias Ringwald     tmp[0] = product[4];
1233af03003cSMatthias Ringwald     tmp[1] = product[5] & 0xffffffff;
1234af03003cSMatthias Ringwald     tmp[2] = 0;
1235af03003cSMatthias Ringwald     tmp[3] = product[7];
1236af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1237af03003cSMatthias Ringwald 
1238af03003cSMatthias Ringwald     /* s4 */
1239af03003cSMatthias Ringwald     tmp[0] = (product[4] >> 32) | (product[5] << 32);
1240af03003cSMatthias Ringwald     tmp[1] = (product[5] >> 32) | (product[6] & 0xffffffff00000000ull);
1241af03003cSMatthias Ringwald     tmp[2] = product[7];
1242af03003cSMatthias Ringwald     tmp[3] = (product[6] >> 32) | (product[4] << 32);
1243af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1244af03003cSMatthias Ringwald 
1245af03003cSMatthias Ringwald     /* d1 */
1246af03003cSMatthias Ringwald     tmp[0] = (product[5] >> 32) | (product[6] << 32);
1247af03003cSMatthias Ringwald     tmp[1] = (product[6] >> 32);
1248af03003cSMatthias Ringwald     tmp[2] = 0;
1249af03003cSMatthias Ringwald     tmp[3] = (product[4] & 0xffffffff) | (product[5] << 32);
1250af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1251af03003cSMatthias Ringwald 
1252af03003cSMatthias Ringwald     /* d2 */
1253af03003cSMatthias Ringwald     tmp[0] = product[6];
1254af03003cSMatthias Ringwald     tmp[1] = product[7];
1255af03003cSMatthias Ringwald     tmp[2] = 0;
1256af03003cSMatthias Ringwald     tmp[3] = (product[4] >> 32) | (product[5] & 0xffffffff00000000ull);
1257af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1258af03003cSMatthias Ringwald 
1259af03003cSMatthias Ringwald     /* d3 */
1260af03003cSMatthias Ringwald     tmp[0] = (product[6] >> 32) | (product[7] << 32);
1261af03003cSMatthias Ringwald     tmp[1] = (product[7] >> 32) | (product[4] << 32);
1262af03003cSMatthias Ringwald     tmp[2] = (product[4] >> 32) | (product[5] << 32);
1263af03003cSMatthias Ringwald     tmp[3] = (product[6] << 32);
1264af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1265af03003cSMatthias Ringwald 
1266af03003cSMatthias Ringwald     /* d4 */
1267af03003cSMatthias Ringwald     tmp[0] = product[7];
1268af03003cSMatthias Ringwald     tmp[1] = product[4] & 0xffffffff00000000ull;
1269af03003cSMatthias Ringwald     tmp[2] = product[5];
1270af03003cSMatthias Ringwald     tmp[3] = product[6] & 0xffffffff00000000ull;
1271af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1272af03003cSMatthias Ringwald 
1273af03003cSMatthias Ringwald     if (carry < 0) {
1274af03003cSMatthias Ringwald         do {
1275af03003cSMatthias Ringwald             carry += vli_add(result, result, curve_p);
1276af03003cSMatthias Ringwald         } while (carry < 0);
1277af03003cSMatthias Ringwald     } else {
1278af03003cSMatthias Ringwald         while (carry || vli_cmp(curve_p, result) != 1) {
1279af03003cSMatthias Ringwald             carry -= vli_sub(result, result, curve_p);
1280af03003cSMatthias Ringwald         }
1281af03003cSMatthias Ringwald     }
1282af03003cSMatthias Ringwald }
1283af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
1284af03003cSMatthias Ringwald 
1285af03003cSMatthias Ringwald #elif uECC_CURVE == uECC_secp256k1
1286af03003cSMatthias Ringwald 
1287af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
omega_mult(uint8_t * RESTRICT result,const uint8_t * RESTRICT right)1288af03003cSMatthias Ringwald static void omega_mult(uint8_t * RESTRICT result, const uint8_t * RESTRICT right) {
1289af03003cSMatthias Ringwald     /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */
1290af03003cSMatthias Ringwald     uECC_word_t r0 = 0;
1291af03003cSMatthias Ringwald     uECC_word_t r1 = 0;
1292af03003cSMatthias Ringwald     uECC_word_t r2 = 0;
1293af03003cSMatthias Ringwald     wordcount_t k;
1294af03003cSMatthias Ringwald 
1295af03003cSMatthias Ringwald     /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */
1296af03003cSMatthias Ringwald     muladd(0xD1, right[0], &r0, &r1, &r2);
1297af03003cSMatthias Ringwald     result[0] = r0;
1298af03003cSMatthias Ringwald     r0 = r1;
1299af03003cSMatthias Ringwald     r1 = r2;
1300af03003cSMatthias Ringwald     /* r2 is still 0 */
1301af03003cSMatthias Ringwald 
1302af03003cSMatthias Ringwald     for (k = 1; k < uECC_WORDS; ++k) {
1303af03003cSMatthias Ringwald         muladd(0x03, right[k - 1], &r0, &r1, &r2);
1304af03003cSMatthias Ringwald         muladd(0xD1, right[k], &r0, &r1, &r2);
1305af03003cSMatthias Ringwald         result[k] = r0;
1306af03003cSMatthias Ringwald         r0 = r1;
1307af03003cSMatthias Ringwald         r1 = r2;
1308af03003cSMatthias Ringwald         r2 = 0;
1309af03003cSMatthias Ringwald     }
1310af03003cSMatthias Ringwald     muladd(0x03, right[uECC_WORDS - 1], &r0, &r1, &r2);
1311af03003cSMatthias Ringwald     result[uECC_WORDS] = r0;
1312af03003cSMatthias Ringwald     result[uECC_WORDS + 1] = r1;
1313af03003cSMatthias Ringwald 
1314af03003cSMatthias Ringwald     result[4 + uECC_WORDS] = vli_add(result + 4, result + 4, right); /* add the 2^32 multiple */
1315af03003cSMatthias Ringwald }
1316af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
omega_mult(uint32_t * RESTRICT result,const uint32_t * RESTRICT right)1317af03003cSMatthias Ringwald static void omega_mult(uint32_t * RESTRICT result, const uint32_t * RESTRICT right) {
1318af03003cSMatthias Ringwald     /* Multiply by (2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */
1319af03003cSMatthias Ringwald     uint32_t carry = 0;
1320af03003cSMatthias Ringwald     wordcount_t k;
1321af03003cSMatthias Ringwald 
1322af03003cSMatthias Ringwald     for (k = 0; k < uECC_WORDS; ++k) {
1323af03003cSMatthias Ringwald         uint64_t p = (uint64_t)0x3D1 * right[k] + carry;
1324af03003cSMatthias Ringwald         result[k] = (p & 0xffffffff);
1325af03003cSMatthias Ringwald         carry = p >> 32;
1326af03003cSMatthias Ringwald     }
1327af03003cSMatthias Ringwald     result[uECC_WORDS] = carry;
1328af03003cSMatthias Ringwald 
1329af03003cSMatthias Ringwald     result[1 + uECC_WORDS] = vli_add(result + 1, result + 1, right); /* add the 2^32 multiple */
1330af03003cSMatthias Ringwald }
1331af03003cSMatthias Ringwald #else
omega_mult(uint64_t * RESTRICT result,const uint64_t * RESTRICT right)1332af03003cSMatthias Ringwald static void omega_mult(uint64_t * RESTRICT result, const uint64_t * RESTRICT right) {
1333af03003cSMatthias Ringwald     uECC_word_t r0 = 0;
1334af03003cSMatthias Ringwald     uECC_word_t r1 = 0;
1335af03003cSMatthias Ringwald     uECC_word_t r2 = 0;
1336af03003cSMatthias Ringwald     wordcount_t k;
1337af03003cSMatthias Ringwald 
1338af03003cSMatthias Ringwald     /* Multiply by (2^32 + 2^9 + 2^8 + 2^7 + 2^6 + 2^4 + 1). */
1339af03003cSMatthias Ringwald     for (k = 0; k < uECC_WORDS; ++k) {
1340af03003cSMatthias Ringwald         muladd(0x1000003D1ull, right[k], &r0, &r1, &r2);
1341af03003cSMatthias Ringwald         result[k] = r0;
1342af03003cSMatthias Ringwald         r0 = r1;
1343af03003cSMatthias Ringwald         r1 = r2;
1344af03003cSMatthias Ringwald         r2 = 0;
1345af03003cSMatthias Ringwald     }
1346af03003cSMatthias Ringwald     result[uECC_WORDS] = r0;
1347af03003cSMatthias Ringwald }
1348af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
1349af03003cSMatthias Ringwald 
1350af03003cSMatthias Ringwald #elif uECC_CURVE == uECC_secp224r1
1351af03003cSMatthias Ringwald 
1352af03003cSMatthias Ringwald /* Computes result = product % curve_p
1353af03003cSMatthias Ringwald    from http://www.nsa.gov/ia/_files/nist-routines.pdf */
1354af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
1355af03003cSMatthias Ringwald // TODO it may be faster to use the omega_mult method when fully asm optimized.
vli_mmod_fast(uint8_t * RESTRICT result,uint8_t * RESTRICT product)1356af03003cSMatthias Ringwald void vli_mmod_fast(uint8_t *RESTRICT result, uint8_t *RESTRICT product) {
1357af03003cSMatthias Ringwald     uint8_t tmp[uECC_WORDS];
1358af03003cSMatthias Ringwald     int8_t carry;
1359af03003cSMatthias Ringwald 
1360af03003cSMatthias Ringwald     /* t */
1361af03003cSMatthias Ringwald     vli_set(result, product);
1362af03003cSMatthias Ringwald 
1363af03003cSMatthias Ringwald     /* s1 */
1364af03003cSMatthias Ringwald     tmp[0] = tmp[1] = tmp[2] = tmp[3] = 0;
1365af03003cSMatthias Ringwald     tmp[4] = tmp[5] = tmp[6] = tmp[7] = 0;
1366af03003cSMatthias Ringwald     tmp[8] = tmp[9] = tmp[10] = tmp[11] = 0;
1367af03003cSMatthias Ringwald     tmp[12] = product[28]; tmp[13] = product[29]; tmp[14] = product[30]; tmp[15] = product[31];
1368af03003cSMatthias Ringwald     tmp[16] = product[32]; tmp[17] = product[33]; tmp[18] = product[34]; tmp[19] = product[35];
1369af03003cSMatthias Ringwald     tmp[20] = product[36]; tmp[21] = product[37]; tmp[22] = product[38]; tmp[23] = product[39];
1370af03003cSMatthias Ringwald     tmp[24] = product[40]; tmp[25] = product[41]; tmp[26] = product[42]; tmp[27] = product[43];
1371af03003cSMatthias Ringwald     carry = vli_add(result, result, tmp);
1372af03003cSMatthias Ringwald 
1373af03003cSMatthias Ringwald     /* s2 */
1374af03003cSMatthias Ringwald     tmp[12] = product[44]; tmp[13] = product[45]; tmp[14] = product[46]; tmp[15] = product[47];
1375af03003cSMatthias Ringwald     tmp[16] = product[48]; tmp[17] = product[49]; tmp[18] = product[50]; tmp[19] = product[51];
1376af03003cSMatthias Ringwald     tmp[20] = product[52]; tmp[21] = product[53]; tmp[22] = product[54]; tmp[23] = product[55];
1377af03003cSMatthias Ringwald     tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0;
1378af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1379af03003cSMatthias Ringwald 
1380af03003cSMatthias Ringwald     /* d1 */
1381af03003cSMatthias Ringwald     tmp[0]  = product[28]; tmp[1]  = product[29]; tmp[2]  = product[30]; tmp[3]  = product[31];
1382af03003cSMatthias Ringwald     tmp[4]  = product[32]; tmp[5]  = product[33]; tmp[6]  = product[34]; tmp[7]  = product[35];
1383af03003cSMatthias Ringwald     tmp[8]  = product[36]; tmp[9]  = product[37]; tmp[10] = product[38]; tmp[11] = product[39];
1384af03003cSMatthias Ringwald     tmp[12] = product[40]; tmp[13] = product[41]; tmp[14] = product[42]; tmp[15] = product[43];
1385af03003cSMatthias Ringwald     tmp[16] = product[44]; tmp[17] = product[45]; tmp[18] = product[46]; tmp[19] = product[47];
1386af03003cSMatthias Ringwald     tmp[20] = product[48]; tmp[21] = product[49]; tmp[22] = product[50]; tmp[23] = product[51];
1387af03003cSMatthias Ringwald     tmp[24] = product[52]; tmp[25] = product[53]; tmp[26] = product[54]; tmp[27] = product[55];
1388af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1389af03003cSMatthias Ringwald 
1390af03003cSMatthias Ringwald     /* d2 */
1391af03003cSMatthias Ringwald     tmp[0]  = product[44]; tmp[1]  = product[45]; tmp[2]  = product[46]; tmp[3]  = product[47];
1392af03003cSMatthias Ringwald     tmp[4]  = product[48]; tmp[5]  = product[49]; tmp[6]  = product[50]; tmp[7]  = product[51];
1393af03003cSMatthias Ringwald     tmp[8]  = product[52]; tmp[9]  = product[53]; tmp[10] = product[54]; tmp[11] = product[55];
1394af03003cSMatthias Ringwald     tmp[12] = tmp[13] = tmp[14] = tmp[15] = 0;
1395af03003cSMatthias Ringwald     tmp[16] = tmp[17] = tmp[18] = tmp[19] = 0;
1396af03003cSMatthias Ringwald     tmp[20] = tmp[21] = tmp[22] = tmp[23] = 0;
1397af03003cSMatthias Ringwald     tmp[24] = tmp[25] = tmp[26] = tmp[27] = 0;
1398af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1399af03003cSMatthias Ringwald 
1400af03003cSMatthias Ringwald     if (carry < 0) {
1401af03003cSMatthias Ringwald         do {
1402af03003cSMatthias Ringwald             carry += vli_add(result, result, curve_p);
1403af03003cSMatthias Ringwald         } while (carry < 0);
1404af03003cSMatthias Ringwald     } else {
1405af03003cSMatthias Ringwald         while (carry || vli_cmp(curve_p, result) != 1) {
1406af03003cSMatthias Ringwald             carry -= vli_sub(result, result, curve_p);
1407af03003cSMatthias Ringwald         }
1408af03003cSMatthias Ringwald     }
1409af03003cSMatthias Ringwald }
1410af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
vli_mmod_fast(uint32_t * RESTRICT result,uint32_t * RESTRICT product)1411af03003cSMatthias Ringwald void vli_mmod_fast(uint32_t *RESTRICT result, uint32_t *RESTRICT product)
1412af03003cSMatthias Ringwald {
1413af03003cSMatthias Ringwald     uint32_t tmp[uECC_WORDS];
1414af03003cSMatthias Ringwald     int carry;
1415af03003cSMatthias Ringwald 
1416af03003cSMatthias Ringwald     /* t */
1417af03003cSMatthias Ringwald     vli_set(result, product);
1418af03003cSMatthias Ringwald 
1419af03003cSMatthias Ringwald     /* s1 */
1420af03003cSMatthias Ringwald     tmp[0] = tmp[1] = tmp[2] = 0;
1421af03003cSMatthias Ringwald     tmp[3] = product[7];
1422af03003cSMatthias Ringwald     tmp[4] = product[8];
1423af03003cSMatthias Ringwald     tmp[5] = product[9];
1424af03003cSMatthias Ringwald     tmp[6] = product[10];
1425af03003cSMatthias Ringwald     carry = vli_add(result, result, tmp);
1426af03003cSMatthias Ringwald 
1427af03003cSMatthias Ringwald     /* s2 */
1428af03003cSMatthias Ringwald     tmp[3] = product[11];
1429af03003cSMatthias Ringwald     tmp[4] = product[12];
1430af03003cSMatthias Ringwald     tmp[5] = product[13];
1431af03003cSMatthias Ringwald     tmp[6] = 0;
1432af03003cSMatthias Ringwald     carry += vli_add(result, result, tmp);
1433af03003cSMatthias Ringwald 
1434af03003cSMatthias Ringwald     /* d1 */
1435af03003cSMatthias Ringwald     tmp[0] = product[7];
1436af03003cSMatthias Ringwald     tmp[1] = product[8];
1437af03003cSMatthias Ringwald     tmp[2] = product[9];
1438af03003cSMatthias Ringwald     tmp[3] = product[10];
1439af03003cSMatthias Ringwald     tmp[4] = product[11];
1440af03003cSMatthias Ringwald     tmp[5] = product[12];
1441af03003cSMatthias Ringwald     tmp[6] = product[13];
1442af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1443af03003cSMatthias Ringwald 
1444af03003cSMatthias Ringwald     /* d2 */
1445af03003cSMatthias Ringwald     tmp[0] = product[11];
1446af03003cSMatthias Ringwald     tmp[1] = product[12];
1447af03003cSMatthias Ringwald     tmp[2] = product[13];
1448af03003cSMatthias Ringwald     tmp[3] = tmp[4] = tmp[5] = tmp[6] = 0;
1449af03003cSMatthias Ringwald     carry -= vli_sub(result, result, tmp);
1450af03003cSMatthias Ringwald 
1451af03003cSMatthias Ringwald     if (carry < 0) {
1452af03003cSMatthias Ringwald         do {
1453af03003cSMatthias Ringwald             carry += vli_add(result, result, curve_p);
1454af03003cSMatthias Ringwald         } while (carry < 0);
1455af03003cSMatthias Ringwald     } else {
1456af03003cSMatthias Ringwald         while (carry || vli_cmp(curve_p, result) != 1) {
1457af03003cSMatthias Ringwald             carry -= vli_sub(result, result, curve_p);
1458af03003cSMatthias Ringwald         }
1459af03003cSMatthias Ringwald     }
1460af03003cSMatthias Ringwald }
1461af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
1462af03003cSMatthias Ringwald 
1463af03003cSMatthias Ringwald #endif /* uECC_CURVE */
1464af03003cSMatthias Ringwald #endif /* !asm_mmod_fast */
1465af03003cSMatthias Ringwald 
1466af03003cSMatthias Ringwald /* Computes result = (left * right) % curve_p. */
vli_modMult_fast(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)1467af03003cSMatthias Ringwald static void vli_modMult_fast(uECC_word_t *result,
1468af03003cSMatthias Ringwald                              const uECC_word_t *left,
1469af03003cSMatthias Ringwald                              const uECC_word_t *right) {
1470af03003cSMatthias Ringwald     uECC_word_t product[2 * uECC_WORDS];
1471af03003cSMatthias Ringwald     vli_mult(product, left, right);
1472af03003cSMatthias Ringwald     vli_mmod_fast(result, product);
1473af03003cSMatthias Ringwald }
1474af03003cSMatthias Ringwald 
1475af03003cSMatthias Ringwald #if uECC_SQUARE_FUNC
1476af03003cSMatthias Ringwald 
1477af03003cSMatthias Ringwald /* Computes result = left^2 % curve_p. */
vli_modSquare_fast(uECC_word_t * result,const uECC_word_t * left)1478af03003cSMatthias Ringwald static void vli_modSquare_fast(uECC_word_t *result, const uECC_word_t *left) {
1479af03003cSMatthias Ringwald     uECC_word_t product[2 * uECC_WORDS];
1480af03003cSMatthias Ringwald     vli_square(product, left);
1481af03003cSMatthias Ringwald     vli_mmod_fast(result, product);
1482af03003cSMatthias Ringwald }
1483af03003cSMatthias Ringwald 
1484af03003cSMatthias Ringwald #else /* uECC_SQUARE_FUNC */
1485af03003cSMatthias Ringwald 
1486af03003cSMatthias Ringwald #define vli_modSquare_fast(result, left) vli_modMult_fast((result), (left), (left))
1487af03003cSMatthias Ringwald 
1488af03003cSMatthias Ringwald #endif /* uECC_SQUARE_FUNC */
1489af03003cSMatthias Ringwald 
1490af03003cSMatthias Ringwald 
1491af03003cSMatthias Ringwald #define EVEN(vli) (!(vli[0] & 1))
1492af03003cSMatthias Ringwald /* Computes result = (1 / input) % mod. All VLIs are the same size.
1493af03003cSMatthias Ringwald    See "From Euclid's GCD to Montgomery Multiplication to the Great Divide"
1494*c824d78cSMatthias Ringwald    labs.oracle.com/techrep/2001/smli_tr-2001-95.pdf */
1495af03003cSMatthias Ringwald #if !asm_modInv
vli_modInv(uECC_word_t * result,const uECC_word_t * input,const uECC_word_t * mod)1496af03003cSMatthias Ringwald static void vli_modInv(uECC_word_t *result, const uECC_word_t *input, const uECC_word_t *mod) {
1497af03003cSMatthias Ringwald     uECC_word_t a[uECC_WORDS], b[uECC_WORDS], u[uECC_WORDS], v[uECC_WORDS];
1498af03003cSMatthias Ringwald     uECC_word_t carry;
1499af03003cSMatthias Ringwald     cmpresult_t cmpResult;
1500af03003cSMatthias Ringwald 
1501af03003cSMatthias Ringwald     if (vli_isZero(input)) {
1502af03003cSMatthias Ringwald         vli_clear(result);
1503af03003cSMatthias Ringwald         return;
1504af03003cSMatthias Ringwald     }
1505af03003cSMatthias Ringwald 
1506af03003cSMatthias Ringwald     vli_set(a, input);
1507af03003cSMatthias Ringwald     vli_set(b, mod);
1508af03003cSMatthias Ringwald     vli_clear(u);
1509af03003cSMatthias Ringwald     u[0] = 1;
1510af03003cSMatthias Ringwald     vli_clear(v);
1511af03003cSMatthias Ringwald     while ((cmpResult = vli_cmp(a, b)) != 0) {
1512af03003cSMatthias Ringwald         carry = 0;
1513af03003cSMatthias Ringwald         if (EVEN(a)) {
1514af03003cSMatthias Ringwald             vli_rshift1(a);
1515af03003cSMatthias Ringwald             if (!EVEN(u)) {
1516af03003cSMatthias Ringwald                 carry = vli_add(u, u, mod);
1517af03003cSMatthias Ringwald             }
1518af03003cSMatthias Ringwald             vli_rshift1(u);
1519af03003cSMatthias Ringwald             if (carry) {
1520af03003cSMatthias Ringwald                 u[uECC_WORDS - 1] |= HIGH_BIT_SET;
1521af03003cSMatthias Ringwald             }
1522af03003cSMatthias Ringwald         } else if (EVEN(b)) {
1523af03003cSMatthias Ringwald             vli_rshift1(b);
1524af03003cSMatthias Ringwald             if (!EVEN(v)) {
1525af03003cSMatthias Ringwald                 carry = vli_add(v, v, mod);
1526af03003cSMatthias Ringwald             }
1527af03003cSMatthias Ringwald             vli_rshift1(v);
1528af03003cSMatthias Ringwald             if (carry) {
1529af03003cSMatthias Ringwald                 v[uECC_WORDS - 1] |= HIGH_BIT_SET;
1530af03003cSMatthias Ringwald             }
1531af03003cSMatthias Ringwald         } else if (cmpResult > 0) {
1532af03003cSMatthias Ringwald             vli_sub(a, a, b);
1533af03003cSMatthias Ringwald             vli_rshift1(a);
1534af03003cSMatthias Ringwald             if (vli_cmp(u, v) < 0) {
1535af03003cSMatthias Ringwald                 vli_add(u, u, mod);
1536af03003cSMatthias Ringwald             }
1537af03003cSMatthias Ringwald             vli_sub(u, u, v);
1538af03003cSMatthias Ringwald             if (!EVEN(u)) {
1539af03003cSMatthias Ringwald                 carry = vli_add(u, u, mod);
1540af03003cSMatthias Ringwald             }
1541af03003cSMatthias Ringwald             vli_rshift1(u);
1542af03003cSMatthias Ringwald             if (carry) {
1543af03003cSMatthias Ringwald                 u[uECC_WORDS - 1] |= HIGH_BIT_SET;
1544af03003cSMatthias Ringwald             }
1545af03003cSMatthias Ringwald         } else {
1546af03003cSMatthias Ringwald             vli_sub(b, b, a);
1547af03003cSMatthias Ringwald             vli_rshift1(b);
1548af03003cSMatthias Ringwald             if (vli_cmp(v, u) < 0) {
1549af03003cSMatthias Ringwald                 vli_add(v, v, mod);
1550af03003cSMatthias Ringwald             }
1551af03003cSMatthias Ringwald             vli_sub(v, v, u);
1552af03003cSMatthias Ringwald             if (!EVEN(v)) {
1553af03003cSMatthias Ringwald                 carry = vli_add(v, v, mod);
1554af03003cSMatthias Ringwald             }
1555af03003cSMatthias Ringwald             vli_rshift1(v);
1556af03003cSMatthias Ringwald             if (carry) {
1557af03003cSMatthias Ringwald                 v[uECC_WORDS - 1] |= HIGH_BIT_SET;
1558af03003cSMatthias Ringwald             }
1559af03003cSMatthias Ringwald         }
1560af03003cSMatthias Ringwald     }
1561af03003cSMatthias Ringwald     vli_set(result, u);
1562af03003cSMatthias Ringwald }
1563af03003cSMatthias Ringwald #endif /* !asm_modInv */
1564af03003cSMatthias Ringwald 
1565af03003cSMatthias Ringwald /* ------ Point operations ------ */
1566af03003cSMatthias Ringwald 
1567af03003cSMatthias Ringwald /* Returns 1 if 'point' is the point at infinity, 0 otherwise. */
EccPoint_isZero(const EccPoint * point)1568af03003cSMatthias Ringwald static cmpresult_t EccPoint_isZero(const EccPoint *point) {
1569af03003cSMatthias Ringwald     return (vli_isZero(point->x) && vli_isZero(point->y));
1570af03003cSMatthias Ringwald }
1571af03003cSMatthias Ringwald 
1572af03003cSMatthias Ringwald /* Point multiplication algorithm using Montgomery's ladder with co-Z coordinates.
1573*c824d78cSMatthias Ringwald From eprint.iacr.org/2011/338.pdf
1574af03003cSMatthias Ringwald */
1575af03003cSMatthias Ringwald 
1576af03003cSMatthias Ringwald /* Double in place */
1577af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp256k1)
EccPoint_double_jacobian(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,uECC_word_t * RESTRICT Z1)1578af03003cSMatthias Ringwald static void EccPoint_double_jacobian(uECC_word_t * RESTRICT X1,
1579af03003cSMatthias Ringwald                                      uECC_word_t * RESTRICT Y1,
1580af03003cSMatthias Ringwald                                      uECC_word_t * RESTRICT Z1) {
1581af03003cSMatthias Ringwald     /* t1 = X, t2 = Y, t3 = Z */
1582af03003cSMatthias Ringwald     uECC_word_t t4[uECC_WORDS];
1583af03003cSMatthias Ringwald     uECC_word_t t5[uECC_WORDS];
1584af03003cSMatthias Ringwald 
1585af03003cSMatthias Ringwald     if (vli_isZero(Z1)) {
1586af03003cSMatthias Ringwald         return;
1587af03003cSMatthias Ringwald     }
1588af03003cSMatthias Ringwald 
1589af03003cSMatthias Ringwald     vli_modSquare_fast(t5, Y1);   /* t5 = y1^2 */
1590af03003cSMatthias Ringwald     vli_modMult_fast(t4, X1, t5); /* t4 = x1*y1^2 = A */
1591af03003cSMatthias Ringwald     vli_modSquare_fast(X1, X1);   /* t1 = x1^2 */
1592af03003cSMatthias Ringwald     vli_modSquare_fast(t5, t5);   /* t5 = y1^4 */
1593af03003cSMatthias Ringwald     vli_modMult_fast(Z1, Y1, Z1); /* t3 = y1*z1 = z3 */
1594af03003cSMatthias Ringwald 
1595af03003cSMatthias Ringwald     vli_modAdd(Y1, X1, X1, curve_p); /* t2 = 2*x1^2 */
1596af03003cSMatthias Ringwald     vli_modAdd(Y1, Y1, X1, curve_p); /* t2 = 3*x1^2 */
1597af03003cSMatthias Ringwald     if (vli_testBit(Y1, 0)) {
1598af03003cSMatthias Ringwald         uECC_word_t carry = vli_add(Y1, Y1, curve_p);
1599af03003cSMatthias Ringwald         vli_rshift1(Y1);
1600af03003cSMatthias Ringwald         Y1[uECC_WORDS - 1] |= carry << (uECC_WORD_BITS - 1);
1601af03003cSMatthias Ringwald     } else {
1602af03003cSMatthias Ringwald         vli_rshift1(Y1);
1603af03003cSMatthias Ringwald     }
1604af03003cSMatthias Ringwald     /* t2 = 3/2*(x1^2) = B */
1605af03003cSMatthias Ringwald 
1606af03003cSMatthias Ringwald     vli_modSquare_fast(X1, Y1);      /* t1 = B^2 */
1607af03003cSMatthias Ringwald     vli_modSub(X1, X1, t4, curve_p); /* t1 = B^2 - A */
1608af03003cSMatthias Ringwald     vli_modSub(X1, X1, t4, curve_p); /* t1 = B^2 - 2A = x3 */
1609af03003cSMatthias Ringwald 
1610af03003cSMatthias Ringwald     vli_modSub(t4, t4, X1, curve_p); /* t4 = A - x3 */
1611af03003cSMatthias Ringwald     vli_modMult_fast(Y1, Y1, t4);    /* t2 = B * (A - x3) */
1612af03003cSMatthias Ringwald     vli_modSub(Y1, Y1, t5, curve_p); /* t2 = B * (A - x3) - y1^4 = y3 */
1613af03003cSMatthias Ringwald }
1614af03003cSMatthias Ringwald #else
EccPoint_double_jacobian(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,uECC_word_t * RESTRICT Z1)1615af03003cSMatthias Ringwald static void EccPoint_double_jacobian(uECC_word_t * RESTRICT X1,
1616af03003cSMatthias Ringwald                                      uECC_word_t * RESTRICT Y1,
1617af03003cSMatthias Ringwald                                      uECC_word_t * RESTRICT Z1) {
1618af03003cSMatthias Ringwald     /* t1 = X, t2 = Y, t3 = Z */
1619af03003cSMatthias Ringwald     uECC_word_t t4[uECC_WORDS];
1620af03003cSMatthias Ringwald     uECC_word_t t5[uECC_WORDS];
1621af03003cSMatthias Ringwald 
1622af03003cSMatthias Ringwald     if (vli_isZero(Z1)) {
1623af03003cSMatthias Ringwald         return;
1624af03003cSMatthias Ringwald     }
1625af03003cSMatthias Ringwald 
1626af03003cSMatthias Ringwald     vli_modSquare_fast(t4, Y1);   /* t4 = y1^2 */
1627af03003cSMatthias Ringwald     vli_modMult_fast(t5, X1, t4); /* t5 = x1*y1^2 = A */
1628af03003cSMatthias Ringwald     vli_modSquare_fast(t4, t4);   /* t4 = y1^4 */
1629af03003cSMatthias Ringwald     vli_modMult_fast(Y1, Y1, Z1); /* t2 = y1*z1 = z3 */
1630af03003cSMatthias Ringwald     vli_modSquare_fast(Z1, Z1);   /* t3 = z1^2 */
1631af03003cSMatthias Ringwald 
1632af03003cSMatthias Ringwald     vli_modAdd(X1, X1, Z1, curve_p); /* t1 = x1 + z1^2 */
1633af03003cSMatthias Ringwald     vli_modAdd(Z1, Z1, Z1, curve_p); /* t3 = 2*z1^2 */
1634af03003cSMatthias Ringwald     vli_modSub_fast(Z1, X1, Z1);     /* t3 = x1 - z1^2 */
1635af03003cSMatthias Ringwald     vli_modMult_fast(X1, X1, Z1);    /* t1 = x1^2 - z1^4 */
1636af03003cSMatthias Ringwald 
1637af03003cSMatthias Ringwald     vli_modAdd(Z1, X1, X1, curve_p); /* t3 = 2*(x1^2 - z1^4) */
1638af03003cSMatthias Ringwald     vli_modAdd(X1, X1, Z1, curve_p); /* t1 = 3*(x1^2 - z1^4) */
1639af03003cSMatthias Ringwald     if (vli_testBit(X1, 0)) {
1640af03003cSMatthias Ringwald         uECC_word_t l_carry = vli_add(X1, X1, curve_p);
1641af03003cSMatthias Ringwald         vli_rshift1(X1);
1642af03003cSMatthias Ringwald         X1[uECC_WORDS - 1] |= l_carry << (uECC_WORD_BITS - 1);
1643af03003cSMatthias Ringwald     } else {
1644af03003cSMatthias Ringwald         vli_rshift1(X1);
1645af03003cSMatthias Ringwald     }
1646af03003cSMatthias Ringwald     /* t1 = 3/2*(x1^2 - z1^4) = B */
1647af03003cSMatthias Ringwald 
1648af03003cSMatthias Ringwald     vli_modSquare_fast(Z1, X1);   /* t3 = B^2 */
1649af03003cSMatthias Ringwald     vli_modSub_fast(Z1, Z1, t5);  /* t3 = B^2 - A */
1650af03003cSMatthias Ringwald     vli_modSub_fast(Z1, Z1, t5);  /* t3 = B^2 - 2A = x3 */
1651af03003cSMatthias Ringwald     vli_modSub_fast(t5, t5, Z1);  /* t5 = A - x3 */
1652af03003cSMatthias Ringwald     vli_modMult_fast(X1, X1, t5); /* t1 = B * (A - x3) */
1653af03003cSMatthias Ringwald     vli_modSub_fast(t4, X1, t4);  /* t4 = B * (A - x3) - y1^4 = y3 */
1654af03003cSMatthias Ringwald 
1655af03003cSMatthias Ringwald     vli_set(X1, Z1);
1656af03003cSMatthias Ringwald     vli_set(Z1, Y1);
1657af03003cSMatthias Ringwald     vli_set(Y1, t4);
1658af03003cSMatthias Ringwald }
1659af03003cSMatthias Ringwald #endif
1660af03003cSMatthias Ringwald 
1661af03003cSMatthias Ringwald /* Modify (x1, y1) => (x1 * z^2, y1 * z^3) */
apply_z(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,const uECC_word_t * RESTRICT Z)1662af03003cSMatthias Ringwald static void apply_z(uECC_word_t * RESTRICT X1,
1663af03003cSMatthias Ringwald                     uECC_word_t * RESTRICT Y1,
1664af03003cSMatthias Ringwald                     const uECC_word_t * RESTRICT Z) {
1665af03003cSMatthias Ringwald     uECC_word_t t1[uECC_WORDS];
1666af03003cSMatthias Ringwald 
1667af03003cSMatthias Ringwald     vli_modSquare_fast(t1, Z);    /* z^2 */
1668af03003cSMatthias Ringwald     vli_modMult_fast(X1, X1, t1); /* x1 * z^2 */
1669af03003cSMatthias Ringwald     vli_modMult_fast(t1, t1, Z);  /* z^3 */
1670af03003cSMatthias Ringwald     vli_modMult_fast(Y1, Y1, t1); /* y1 * z^3 */
1671af03003cSMatthias Ringwald }
1672af03003cSMatthias Ringwald 
1673af03003cSMatthias Ringwald /* P = (x1, y1) => 2P, (x2, y2) => P' */
XYcZ_initial_double(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,uECC_word_t * RESTRICT X2,uECC_word_t * RESTRICT Y2,const uECC_word_t * RESTRICT initial_Z)1674af03003cSMatthias Ringwald static void XYcZ_initial_double(uECC_word_t * RESTRICT X1,
1675af03003cSMatthias Ringwald                                 uECC_word_t * RESTRICT Y1,
1676af03003cSMatthias Ringwald                                 uECC_word_t * RESTRICT X2,
1677af03003cSMatthias Ringwald                                 uECC_word_t * RESTRICT Y2,
1678af03003cSMatthias Ringwald                                 const uECC_word_t * RESTRICT initial_Z) {
1679af03003cSMatthias Ringwald     uECC_word_t z[uECC_WORDS];
1680af03003cSMatthias Ringwald     if (initial_Z) {
1681af03003cSMatthias Ringwald         vli_set(z, initial_Z);
1682af03003cSMatthias Ringwald     } else {
1683af03003cSMatthias Ringwald         vli_clear(z);
1684af03003cSMatthias Ringwald         z[0] = 1;
1685af03003cSMatthias Ringwald     }
1686af03003cSMatthias Ringwald 
1687af03003cSMatthias Ringwald     vli_set(X2, X1);
1688af03003cSMatthias Ringwald     vli_set(Y2, Y1);
1689af03003cSMatthias Ringwald 
1690af03003cSMatthias Ringwald     apply_z(X1, Y1, z);
1691af03003cSMatthias Ringwald     EccPoint_double_jacobian(X1, Y1, z);
1692af03003cSMatthias Ringwald     apply_z(X2, Y2, z);
1693af03003cSMatthias Ringwald }
1694af03003cSMatthias Ringwald 
1695af03003cSMatthias Ringwald /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1696af03003cSMatthias Ringwald    Output P' = (x1', y1', Z3), P + Q = (x3, y3, Z3)
1697af03003cSMatthias Ringwald    or P => P', Q => P + Q
1698af03003cSMatthias Ringwald */
XYcZ_add(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,uECC_word_t * RESTRICT X2,uECC_word_t * RESTRICT Y2)1699af03003cSMatthias Ringwald static void XYcZ_add(uECC_word_t * RESTRICT X1,
1700af03003cSMatthias Ringwald                      uECC_word_t * RESTRICT Y1,
1701af03003cSMatthias Ringwald                      uECC_word_t * RESTRICT X2,
1702af03003cSMatthias Ringwald                      uECC_word_t * RESTRICT Y2) {
1703af03003cSMatthias Ringwald     /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
1704af03003cSMatthias Ringwald     uECC_word_t t5[uECC_WORDS];
1705af03003cSMatthias Ringwald 
1706af03003cSMatthias Ringwald     vli_modSub_fast(t5, X2, X1);  /* t5 = x2 - x1 */
1707af03003cSMatthias Ringwald     vli_modSquare_fast(t5, t5);   /* t5 = (x2 - x1)^2 = A */
1708af03003cSMatthias Ringwald     vli_modMult_fast(X1, X1, t5); /* t1 = x1*A = B */
1709af03003cSMatthias Ringwald     vli_modMult_fast(X2, X2, t5); /* t3 = x2*A = C */
1710af03003cSMatthias Ringwald     vli_modSub_fast(Y2, Y2, Y1);  /* t4 = y2 - y1 */
1711af03003cSMatthias Ringwald     vli_modSquare_fast(t5, Y2);   /* t5 = (y2 - y1)^2 = D */
1712af03003cSMatthias Ringwald 
1713af03003cSMatthias Ringwald     vli_modSub_fast(t5, t5, X1);  /* t5 = D - B */
1714af03003cSMatthias Ringwald     vli_modSub_fast(t5, t5, X2);  /* t5 = D - B - C = x3 */
1715af03003cSMatthias Ringwald     vli_modSub_fast(X2, X2, X1);  /* t3 = C - B */
1716af03003cSMatthias Ringwald     vli_modMult_fast(Y1, Y1, X2); /* t2 = y1*(C - B) */
1717af03003cSMatthias Ringwald     vli_modSub_fast(X2, X1, t5);  /* t3 = B - x3 */
1718af03003cSMatthias Ringwald     vli_modMult_fast(Y2, Y2, X2); /* t4 = (y2 - y1)*(B - x3) */
1719af03003cSMatthias Ringwald     vli_modSub_fast(Y2, Y2, Y1);  /* t4 = y3 */
1720af03003cSMatthias Ringwald 
1721af03003cSMatthias Ringwald     vli_set(X2, t5);
1722af03003cSMatthias Ringwald }
1723af03003cSMatthias Ringwald 
1724af03003cSMatthias Ringwald /* Input P = (x1, y1, Z), Q = (x2, y2, Z)
1725af03003cSMatthias Ringwald    Output P + Q = (x3, y3, Z3), P - Q = (x3', y3', Z3)
1726af03003cSMatthias Ringwald    or P => P - Q, Q => P + Q
1727af03003cSMatthias Ringwald */
XYcZ_addC(uECC_word_t * RESTRICT X1,uECC_word_t * RESTRICT Y1,uECC_word_t * RESTRICT X2,uECC_word_t * RESTRICT Y2)1728af03003cSMatthias Ringwald static void XYcZ_addC(uECC_word_t * RESTRICT X1,
1729af03003cSMatthias Ringwald                       uECC_word_t * RESTRICT Y1,
1730af03003cSMatthias Ringwald                       uECC_word_t * RESTRICT X2,
1731af03003cSMatthias Ringwald                       uECC_word_t * RESTRICT Y2) {
1732af03003cSMatthias Ringwald     /* t1 = X1, t2 = Y1, t3 = X2, t4 = Y2 */
1733af03003cSMatthias Ringwald     uECC_word_t t5[uECC_WORDS];
1734af03003cSMatthias Ringwald     uECC_word_t t6[uECC_WORDS];
1735af03003cSMatthias Ringwald     uECC_word_t t7[uECC_WORDS];
1736af03003cSMatthias Ringwald 
1737af03003cSMatthias Ringwald     vli_modSub_fast(t5, X2, X1);     /* t5 = x2 - x1 */
1738af03003cSMatthias Ringwald     vli_modSquare_fast(t5, t5);      /* t5 = (x2 - x1)^2 = A */
1739af03003cSMatthias Ringwald     vli_modMult_fast(X1, X1, t5);    /* t1 = x1*A = B */
1740af03003cSMatthias Ringwald     vli_modMult_fast(X2, X2, t5);    /* t3 = x2*A = C */
1741af03003cSMatthias Ringwald     vli_modAdd(t5, Y2, Y1, curve_p); /* t5 = y2 + y1 */
1742af03003cSMatthias Ringwald     vli_modSub_fast(Y2, Y2, Y1);     /* t4 = y2 - y1 */
1743af03003cSMatthias Ringwald 
1744af03003cSMatthias Ringwald     vli_modSub_fast(t6, X2, X1);     /* t6 = C - B */
1745af03003cSMatthias Ringwald     vli_modMult_fast(Y1, Y1, t6);    /* t2 = y1 * (C - B) = E */
1746af03003cSMatthias Ringwald     vli_modAdd(t6, X1, X2, curve_p); /* t6 = B + C */
1747af03003cSMatthias Ringwald     vli_modSquare_fast(X2, Y2);      /* t3 = (y2 - y1)^2 = D */
1748af03003cSMatthias Ringwald     vli_modSub_fast(X2, X2, t6);     /* t3 = D - (B + C) = x3 */
1749af03003cSMatthias Ringwald 
1750af03003cSMatthias Ringwald     vli_modSub_fast(t7, X1, X2);  /* t7 = B - x3 */
1751af03003cSMatthias Ringwald     vli_modMult_fast(Y2, Y2, t7); /* t4 = (y2 - y1)*(B - x3) */
1752af03003cSMatthias Ringwald     vli_modSub_fast(Y2, Y2, Y1);  /* t4 = (y2 - y1)*(B - x3) - E = y3 */
1753af03003cSMatthias Ringwald 
1754af03003cSMatthias Ringwald     vli_modSquare_fast(t7, t5);   /* t7 = (y2 + y1)^2 = F */
1755af03003cSMatthias Ringwald     vli_modSub_fast(t7, t7, t6);  /* t7 = F - (B + C) = x3' */
1756af03003cSMatthias Ringwald     vli_modSub_fast(t6, t7, X1);  /* t6 = x3' - B */
1757af03003cSMatthias Ringwald     vli_modMult_fast(t6, t6, t5); /* t6 = (y2 + y1)*(x3' - B) */
1758af03003cSMatthias Ringwald     vli_modSub_fast(Y1, t6, Y1);  /* t2 = (y2 + y1)*(x3' - B) - E = y3' */
1759af03003cSMatthias Ringwald 
1760af03003cSMatthias Ringwald     vli_set(X1, t7);
1761af03003cSMatthias Ringwald }
1762af03003cSMatthias Ringwald 
EccPoint_mult(EccPoint * RESTRICT result,const EccPoint * RESTRICT point,const uECC_word_t * RESTRICT scalar,const uECC_word_t * RESTRICT initialZ,bitcount_t numBits)1763af03003cSMatthias Ringwald static void EccPoint_mult(EccPoint * RESTRICT result,
1764af03003cSMatthias Ringwald                           const EccPoint * RESTRICT point,
1765af03003cSMatthias Ringwald                           const uECC_word_t * RESTRICT scalar,
1766af03003cSMatthias Ringwald                           const uECC_word_t * RESTRICT initialZ,
1767af03003cSMatthias Ringwald                           bitcount_t numBits) {
1768af03003cSMatthias Ringwald     /* R0 and R1 */
1769af03003cSMatthias Ringwald     uECC_word_t Rx[2][uECC_WORDS];
1770af03003cSMatthias Ringwald     uECC_word_t Ry[2][uECC_WORDS];
1771af03003cSMatthias Ringwald     uECC_word_t z[uECC_WORDS];
1772af03003cSMatthias Ringwald     bitcount_t i;
1773af03003cSMatthias Ringwald     uECC_word_t nb;
1774af03003cSMatthias Ringwald 
1775af03003cSMatthias Ringwald     vli_set(Rx[1], point->x);
1776af03003cSMatthias Ringwald     vli_set(Ry[1], point->y);
1777af03003cSMatthias Ringwald 
1778af03003cSMatthias Ringwald     XYcZ_initial_double(Rx[1], Ry[1], Rx[0], Ry[0], initialZ);
1779af03003cSMatthias Ringwald 
1780af03003cSMatthias Ringwald     for (i = numBits - 2; i > 0; --i) {
1781af03003cSMatthias Ringwald         nb = !vli_testBit(scalar, i);
1782af03003cSMatthias Ringwald         XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb]);
1783af03003cSMatthias Ringwald         XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb]);
1784af03003cSMatthias Ringwald     }
1785af03003cSMatthias Ringwald 
1786af03003cSMatthias Ringwald     nb = !vli_testBit(scalar, 0);
1787af03003cSMatthias Ringwald     XYcZ_addC(Rx[1 - nb], Ry[1 - nb], Rx[nb], Ry[nb]);
1788af03003cSMatthias Ringwald 
1789af03003cSMatthias Ringwald     /* Find final 1/Z value. */
1790af03003cSMatthias Ringwald     vli_modSub_fast(z, Rx[1], Rx[0]);   /* X1 - X0 */
1791af03003cSMatthias Ringwald     vli_modMult_fast(z, z, Ry[1 - nb]); /* Yb * (X1 - X0) */
1792af03003cSMatthias Ringwald     vli_modMult_fast(z, z, point->x); /* xP * Yb * (X1 - X0) */
1793af03003cSMatthias Ringwald     vli_modInv(z, z, curve_p);          /* 1 / (xP * Yb * (X1 - X0)) */
1794af03003cSMatthias Ringwald     vli_modMult_fast(z, z, point->y); /* yP / (xP * Yb * (X1 - X0)) */
1795af03003cSMatthias Ringwald     vli_modMult_fast(z, z, Rx[1 - nb]); /* Xb * yP / (xP * Yb * (X1 - X0)) */
1796af03003cSMatthias Ringwald     /* End 1/Z calculation */
1797af03003cSMatthias Ringwald 
1798af03003cSMatthias Ringwald     XYcZ_add(Rx[nb], Ry[nb], Rx[1 - nb], Ry[1 - nb]);
1799af03003cSMatthias Ringwald     apply_z(Rx[0], Ry[0], z);
1800af03003cSMatthias Ringwald 
1801af03003cSMatthias Ringwald     vli_set(result->x, Rx[0]);
1802af03003cSMatthias Ringwald     vli_set(result->y, Ry[0]);
1803af03003cSMatthias Ringwald }
1804af03003cSMatthias Ringwald 
EccPoint_compute_public_key(EccPoint * result,uECC_word_t * private)1805af03003cSMatthias Ringwald static int EccPoint_compute_public_key(EccPoint *result, uECC_word_t *private) {
1806af03003cSMatthias Ringwald     uECC_word_t tmp1[uECC_WORDS];
1807af03003cSMatthias Ringwald     uECC_word_t tmp2[uECC_WORDS];
1808af03003cSMatthias Ringwald     uECC_word_t *p2[2] = {tmp1, tmp2};
1809af03003cSMatthias Ringwald     uECC_word_t carry;
1810af03003cSMatthias Ringwald 
1811af03003cSMatthias Ringwald     /* Make sure the private key is in the range [1, n-1]. */
1812af03003cSMatthias Ringwald     if (vli_isZero(private)) {
1813af03003cSMatthias Ringwald         return 0;
1814af03003cSMatthias Ringwald     }
1815af03003cSMatthias Ringwald 
1816af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1)
1817af03003cSMatthias Ringwald     // Don't regularize the bitcount for secp160r1, since it would have a larger performance
1818af03003cSMatthias Ringwald     // impact (about 2% slower on average) and requires the vli_xxx_n functions, leading to
1819af03003cSMatthias Ringwald     // a significant increase in code size.
1820af03003cSMatthias Ringwald 
18216e791780SMatthias Ringwald     EccPoint_mult(result, &curve_G, private, NULL, vli_numBits(private, uECC_WORDS));
1822af03003cSMatthias Ringwald #else
1823af03003cSMatthias Ringwald     if (vli_cmp(curve_n, private) != 1) {
1824af03003cSMatthias Ringwald         return 0;
1825af03003cSMatthias Ringwald     }
1826af03003cSMatthias Ringwald 
1827af03003cSMatthias Ringwald     // Regularize the bitcount for the private key so that attackers cannot use a side channel
1828af03003cSMatthias Ringwald     // attack to learn the number of leading zeros.
1829af03003cSMatthias Ringwald     carry = vli_add(tmp1, private, curve_n);
1830af03003cSMatthias Ringwald     vli_add(tmp2, tmp1, curve_n);
18316e791780SMatthias Ringwald     EccPoint_mult(result, &curve_G, p2[!carry], NULL, (uECC_BYTES * 8) + 1);
1832af03003cSMatthias Ringwald #endif
1833af03003cSMatthias Ringwald 
1834af03003cSMatthias Ringwald     if (EccPoint_isZero(result)) {
1835af03003cSMatthias Ringwald         return 0;
1836af03003cSMatthias Ringwald     }
1837af03003cSMatthias Ringwald     return 1;
1838af03003cSMatthias Ringwald }
1839af03003cSMatthias Ringwald 
184080dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_COMPRESSION
184180dcb211SMatthias Ringwald 
1842af03003cSMatthias Ringwald #if uECC_CURVE == uECC_secp224r1
1843af03003cSMatthias Ringwald 
1844af03003cSMatthias Ringwald /* Routine 3.2.4 RS;  from http://www.nsa.gov/ia/_files/nist-routines.pdf */
mod_sqrt_secp224r1_rs(uECC_word_t * d1,uECC_word_t * e1,uECC_word_t * f1,const uECC_word_t * d0,const uECC_word_t * e0,const uECC_word_t * f0)1845af03003cSMatthias Ringwald static void mod_sqrt_secp224r1_rs(uECC_word_t *d1,
1846af03003cSMatthias Ringwald                                   uECC_word_t *e1,
1847af03003cSMatthias Ringwald                                   uECC_word_t *f1,
1848af03003cSMatthias Ringwald                                   const uECC_word_t *d0,
1849af03003cSMatthias Ringwald                                   const uECC_word_t *e0,
1850af03003cSMatthias Ringwald                                   const uECC_word_t *f0) {
1851af03003cSMatthias Ringwald     uECC_word_t t[uECC_WORDS];
1852af03003cSMatthias Ringwald 
1853af03003cSMatthias Ringwald     vli_modSquare_fast(t, d0);                 /* t <-- d0 ^ 2 */
1854af03003cSMatthias Ringwald     vli_modMult_fast(e1, d0, e0);              /* e1 <-- d0 * e0 */
1855af03003cSMatthias Ringwald     vli_modAdd(d1, t, f0, curve_p);            /* d1 <-- t  + f0 */
1856af03003cSMatthias Ringwald     vli_modAdd(e1, e1, e1, curve_p);           /* e1 <-- e1 + e1 */
1857af03003cSMatthias Ringwald     vli_modMult_fast(f1, t, f0);               /* f1 <-- t  * f0 */
1858af03003cSMatthias Ringwald     vli_modAdd(f1, f1, f1, curve_p);           /* f1 <-- f1 + f1 */
1859af03003cSMatthias Ringwald     vli_modAdd(f1, f1, f1, curve_p);           /* f1 <-- f1 + f1 */
1860af03003cSMatthias Ringwald }
1861af03003cSMatthias Ringwald 
1862af03003cSMatthias Ringwald /* Routine 3.2.5 RSS;  from http://www.nsa.gov/ia/_files/nist-routines.pdf */
mod_sqrt_secp224r1_rss(uECC_word_t * d1,uECC_word_t * e1,uECC_word_t * f1,const uECC_word_t * d0,const uECC_word_t * e0,const uECC_word_t * f0,const bitcount_t j)1863af03003cSMatthias Ringwald static void mod_sqrt_secp224r1_rss(uECC_word_t *d1,
1864af03003cSMatthias Ringwald                                    uECC_word_t *e1,
1865af03003cSMatthias Ringwald                                    uECC_word_t *f1,
1866af03003cSMatthias Ringwald                                    const uECC_word_t *d0,
1867af03003cSMatthias Ringwald                                    const uECC_word_t *e0,
1868af03003cSMatthias Ringwald                                    const uECC_word_t *f0,
1869af03003cSMatthias Ringwald                                    const bitcount_t j) {
1870af03003cSMatthias Ringwald     bitcount_t i;
1871af03003cSMatthias Ringwald 
1872af03003cSMatthias Ringwald     vli_set(d1, d0);                           /* d1 <-- d0 */
1873af03003cSMatthias Ringwald     vli_set(e1, e0);                           /* e1 <-- e0 */
1874af03003cSMatthias Ringwald     vli_set(f1, f0);                           /* f1 <-- f0 */
1875af03003cSMatthias Ringwald     for (i = 1; i <= j; i++) {
1876af03003cSMatthias Ringwald         mod_sqrt_secp224r1_rs(d1, e1, f1, d1, e1, f1); /* RS (d1,e1,f1,d1,e1,f1) */
1877af03003cSMatthias Ringwald     }
1878af03003cSMatthias Ringwald }
1879af03003cSMatthias Ringwald 
1880af03003cSMatthias Ringwald /* Routine 3.2.6 RM;  from http://www.nsa.gov/ia/_files/nist-routines.pdf */
mod_sqrt_secp224r1_rm(uECC_word_t * d2,uECC_word_t * e2,uECC_word_t * f2,const uECC_word_t * c,const uECC_word_t * d0,const uECC_word_t * e0,const uECC_word_t * d1,const uECC_word_t * e1)1881af03003cSMatthias Ringwald static void mod_sqrt_secp224r1_rm(uECC_word_t *d2,
1882af03003cSMatthias Ringwald                                   uECC_word_t *e2,
1883af03003cSMatthias Ringwald                                   uECC_word_t *f2,
1884af03003cSMatthias Ringwald                                   const uECC_word_t *c,
1885af03003cSMatthias Ringwald                                   const uECC_word_t *d0,
1886af03003cSMatthias Ringwald                                   const uECC_word_t *e0,
1887af03003cSMatthias Ringwald                                   const uECC_word_t *d1,
1888af03003cSMatthias Ringwald                                   const uECC_word_t *e1) {
1889af03003cSMatthias Ringwald     uECC_word_t t1[uECC_WORDS];
1890af03003cSMatthias Ringwald     uECC_word_t t2[uECC_WORDS];
1891af03003cSMatthias Ringwald 
1892af03003cSMatthias Ringwald     vli_modMult_fast(t1, e0, e1);              /* t1 <-- e0 * e1 */
1893af03003cSMatthias Ringwald     vli_modMult_fast(t1, t1, c);               /* t1 <-- t1 * c */
1894af03003cSMatthias Ringwald     vli_modSub_fast(t1, curve_p, t1);          /* t1 <-- p  - t1 */
1895af03003cSMatthias Ringwald     vli_modMult_fast(t2, d0, d1);              /* t2 <-- d0 * d1 */
1896af03003cSMatthias Ringwald     vli_modAdd(t2, t2, t1, curve_p);           /* t2 <-- t2 + t1 */
1897af03003cSMatthias Ringwald     vli_modMult_fast(t1, d0, e1);              /* t1 <-- d0 * e1 */
1898af03003cSMatthias Ringwald     vli_modMult_fast(e2, d1, e0);              /* e2 <-- d1 * e0 */
1899af03003cSMatthias Ringwald     vli_modAdd(e2, e2, t1, curve_p);           /* e2 <-- e2 + t1 */
1900af03003cSMatthias Ringwald     vli_modSquare_fast(f2, e2);                /* f2 <-- e2^2 */
1901af03003cSMatthias Ringwald     vli_modMult_fast(f2, f2, c);               /* f2 <-- f2 * c */
1902af03003cSMatthias Ringwald     vli_modSub_fast(f2, curve_p, f2);          /* f2 <-- p  - f2 */
1903af03003cSMatthias Ringwald     vli_set(d2, t2);                           /* d2 <-- t2 */
1904af03003cSMatthias Ringwald }
1905af03003cSMatthias Ringwald 
1906af03003cSMatthias Ringwald /* Routine 3.2.7 RP;  from http://www.nsa.gov/ia/_files/nist-routines.pdf */
mod_sqrt_secp224r1_rp(uECC_word_t * d1,uECC_word_t * e1,uECC_word_t * f1,const uECC_word_t * c,const uECC_word_t * r)1907af03003cSMatthias Ringwald static void mod_sqrt_secp224r1_rp(uECC_word_t *d1,
1908af03003cSMatthias Ringwald                                   uECC_word_t *e1,
1909af03003cSMatthias Ringwald                                   uECC_word_t *f1,
1910af03003cSMatthias Ringwald                                   const uECC_word_t *c,
1911af03003cSMatthias Ringwald                                   const uECC_word_t *r) {
1912af03003cSMatthias Ringwald     wordcount_t i;
1913af03003cSMatthias Ringwald     wordcount_t pow2i = 1;
1914af03003cSMatthias Ringwald     uECC_word_t d0[uECC_WORDS];
1915af03003cSMatthias Ringwald     uECC_word_t e0[uECC_WORDS] = {1};          /* e0 <-- 1 */
1916af03003cSMatthias Ringwald     uECC_word_t f0[uECC_WORDS];
1917af03003cSMatthias Ringwald 
1918af03003cSMatthias Ringwald     vli_set(d0, r);                            /* d0 <-- r */
1919af03003cSMatthias Ringwald     vli_modSub_fast(f0, curve_p, c);           /* f0 <-- p  - c */
1920af03003cSMatthias Ringwald     for (i = 0; i <= 6; i++) {
1921af03003cSMatthias Ringwald         mod_sqrt_secp224r1_rss(d1, e1, f1, d0, e0, f0, pow2i); /* RSS (d1,e1,f1,d0,e0,f0,2^i) */
1922af03003cSMatthias Ringwald         mod_sqrt_secp224r1_rm(d1, e1, f1, c, d1, e1, d0, e0);  /* RM (d1,e1,f1,c,d1,e1,d0,e0) */
1923af03003cSMatthias Ringwald         vli_set(d0, d1);                       /* d0 <-- d1 */
1924af03003cSMatthias Ringwald         vli_set(e0, e1);                       /* e0 <-- e1 */
1925af03003cSMatthias Ringwald         vli_set(f0, f1);                       /* f0 <-- f1 */
1926af03003cSMatthias Ringwald         pow2i *= 2;
1927af03003cSMatthias Ringwald     }
1928af03003cSMatthias Ringwald }
1929af03003cSMatthias Ringwald 
1930af03003cSMatthias Ringwald /* Compute a = sqrt(a) (mod curve_p). */
1931af03003cSMatthias Ringwald /* Routine 3.2.8 mp_mod_sqrt_224; from http://www.nsa.gov/ia/_files/nist-routines.pdf */
mod_sqrt(uECC_word_t * a)1932af03003cSMatthias Ringwald static void mod_sqrt(uECC_word_t *a) {
1933af03003cSMatthias Ringwald     bitcount_t i;
1934af03003cSMatthias Ringwald     uECC_word_t e1[uECC_WORDS];
1935af03003cSMatthias Ringwald     uECC_word_t f1[uECC_WORDS];
1936af03003cSMatthias Ringwald     uECC_word_t d0[uECC_WORDS];
1937af03003cSMatthias Ringwald     uECC_word_t e0[uECC_WORDS];
1938af03003cSMatthias Ringwald     uECC_word_t f0[uECC_WORDS];
1939af03003cSMatthias Ringwald     uECC_word_t d1[uECC_WORDS];
1940af03003cSMatthias Ringwald 
1941af03003cSMatthias Ringwald     // s = a; using constant instead of random value
1942af03003cSMatthias Ringwald     mod_sqrt_secp224r1_rp(d0, e0, f0, a, a);           /* RP (d0, e0, f0, c, s) */
1943af03003cSMatthias Ringwald     mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0);     /* RS (d1, e1, f1, d0, e0, f0) */
1944af03003cSMatthias Ringwald     for (i = 1; i <= 95; i++) {
1945af03003cSMatthias Ringwald         vli_set(d0, d1);                               /* d0 <-- d1 */
1946af03003cSMatthias Ringwald         vli_set(e0, e1);                               /* e0 <-- e1 */
1947af03003cSMatthias Ringwald         vli_set(f0, f1);                               /* f0 <-- f1 */
1948af03003cSMatthias Ringwald         mod_sqrt_secp224r1_rs(d1, e1, f1, d0, e0, f0); /* RS (d1, e1, f1, d0, e0, f0) */
1949af03003cSMatthias Ringwald         if (vli_isZero(d1)) {                          /* if d1 == 0 */
1950af03003cSMatthias Ringwald 	        break;
1951af03003cSMatthias Ringwald         }
1952af03003cSMatthias Ringwald     }
1953af03003cSMatthias Ringwald     vli_modInv(f1, e0, curve_p);                       /* f1 <-- 1 / e0 */
1954af03003cSMatthias Ringwald     vli_modMult_fast(a, d0, f1);                       /* a  <-- d0 / e0 */
1955af03003cSMatthias Ringwald }
1956af03003cSMatthias Ringwald 
1957af03003cSMatthias Ringwald #else /* uECC_CURVE */
1958af03003cSMatthias Ringwald 
1959af03003cSMatthias Ringwald /* Compute a = sqrt(a) (mod curve_p). */
mod_sqrt(uECC_word_t * a)1960af03003cSMatthias Ringwald static void mod_sqrt(uECC_word_t *a) {
1961af03003cSMatthias Ringwald     bitcount_t i;
1962af03003cSMatthias Ringwald     uECC_word_t p1[uECC_WORDS] = {1};
1963af03003cSMatthias Ringwald     uECC_word_t l_result[uECC_WORDS] = {1};
1964af03003cSMatthias Ringwald 
1965af03003cSMatthias Ringwald     /* Since curve_p == 3 (mod 4) for all supported curves, we can
1966af03003cSMatthias Ringwald        compute sqrt(a) = a^((curve_p + 1) / 4) (mod curve_p). */
1967af03003cSMatthias Ringwald     vli_add(p1, curve_p, p1); /* p1 = curve_p + 1 */
1968af03003cSMatthias Ringwald     for (i = vli_numBits(p1, uECC_WORDS) - 1; i > 1; --i) {
1969af03003cSMatthias Ringwald         vli_modSquare_fast(l_result, l_result);
1970af03003cSMatthias Ringwald         if (vli_testBit(p1, i)) {
1971af03003cSMatthias Ringwald             vli_modMult_fast(l_result, l_result, a);
1972af03003cSMatthias Ringwald         }
1973af03003cSMatthias Ringwald     }
1974af03003cSMatthias Ringwald     vli_set(a, l_result);
1975af03003cSMatthias Ringwald }
1976af03003cSMatthias Ringwald #endif /* uECC_CURVE */
1977af03003cSMatthias Ringwald 
197880dcb211SMatthias Ringwald #endif /* ENABLE_MICRO_ECC_COMPRESSION */
197980dcb211SMatthias Ringwald 
198080dcb211SMatthias Ringwald 
1981af03003cSMatthias Ringwald #if uECC_WORD_SIZE == 1
1982af03003cSMatthias Ringwald 
vli_nativeToBytes(uint8_t * RESTRICT dest,const uint8_t * RESTRICT src)1983af03003cSMatthias Ringwald static void vli_nativeToBytes(uint8_t * RESTRICT dest, const uint8_t * RESTRICT src) {
1984af03003cSMatthias Ringwald     uint8_t i;
1985af03003cSMatthias Ringwald     for (i = 0; i < uECC_BYTES; ++i) {
1986af03003cSMatthias Ringwald         dest[i] = src[(uECC_BYTES - 1) - i];
1987af03003cSMatthias Ringwald     }
1988af03003cSMatthias Ringwald }
1989af03003cSMatthias Ringwald 
1990af03003cSMatthias Ringwald #define vli_bytesToNative(dest, src) vli_nativeToBytes((dest), (src))
1991af03003cSMatthias Ringwald 
1992af03003cSMatthias Ringwald #elif uECC_WORD_SIZE == 4
1993af03003cSMatthias Ringwald 
vli_nativeToBytes(uint8_t * bytes,const uint32_t * native)1994af03003cSMatthias Ringwald static void vli_nativeToBytes(uint8_t *bytes, const uint32_t *native) {
1995af03003cSMatthias Ringwald     unsigned i;
1996af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
1997af03003cSMatthias Ringwald         uint8_t *digit = bytes + 4 * (uECC_WORDS - 1 - i);
1998af03003cSMatthias Ringwald         digit[0] = native[i] >> 24;
1999af03003cSMatthias Ringwald         digit[1] = native[i] >> 16;
2000af03003cSMatthias Ringwald         digit[2] = native[i] >> 8;
2001af03003cSMatthias Ringwald         digit[3] = native[i];
2002af03003cSMatthias Ringwald     }
2003af03003cSMatthias Ringwald }
2004af03003cSMatthias Ringwald 
vli_bytesToNative(uint32_t * native,const uint8_t * bytes)2005af03003cSMatthias Ringwald static void vli_bytesToNative(uint32_t *native, const uint8_t *bytes) {
2006af03003cSMatthias Ringwald     unsigned i;
2007af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
2008af03003cSMatthias Ringwald         const uint8_t *digit = bytes + 4 * (uECC_WORDS - 1 - i);
2009af03003cSMatthias Ringwald         native[i] = ((uint32_t)digit[0] << 24) | ((uint32_t)digit[1] << 16) |
2010af03003cSMatthias Ringwald                     ((uint32_t)digit[2] << 8) | (uint32_t)digit[3];
2011af03003cSMatthias Ringwald     }
2012af03003cSMatthias Ringwald }
2013af03003cSMatthias Ringwald 
2014af03003cSMatthias Ringwald #else
2015af03003cSMatthias Ringwald 
vli_nativeToBytes(uint8_t * bytes,const uint64_t * native)2016af03003cSMatthias Ringwald static void vli_nativeToBytes(uint8_t *bytes, const uint64_t *native) {
2017af03003cSMatthias Ringwald     unsigned i;
2018af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
2019af03003cSMatthias Ringwald         uint8_t *digit = bytes + 8 * (uECC_WORDS - 1 - i);
2020af03003cSMatthias Ringwald         digit[0] = native[i] >> 56;
2021af03003cSMatthias Ringwald         digit[1] = native[i] >> 48;
2022af03003cSMatthias Ringwald         digit[2] = native[i] >> 40;
2023af03003cSMatthias Ringwald         digit[3] = native[i] >> 32;
2024af03003cSMatthias Ringwald         digit[4] = native[i] >> 24;
2025af03003cSMatthias Ringwald         digit[5] = native[i] >> 16;
2026af03003cSMatthias Ringwald         digit[6] = native[i] >> 8;
2027af03003cSMatthias Ringwald         digit[7] = native[i];
2028af03003cSMatthias Ringwald     }
2029af03003cSMatthias Ringwald }
2030af03003cSMatthias Ringwald 
vli_bytesToNative(uint64_t * native,const uint8_t * bytes)2031af03003cSMatthias Ringwald static void vli_bytesToNative(uint64_t *native, const uint8_t *bytes) {
2032af03003cSMatthias Ringwald     unsigned i;
2033af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS; ++i) {
2034af03003cSMatthias Ringwald         const uint8_t *digit = bytes + 8 * (uECC_WORDS - 1 - i);
2035af03003cSMatthias Ringwald         native[i] = ((uint64_t)digit[0] << 56) | ((uint64_t)digit[1] << 48) |
2036af03003cSMatthias Ringwald                     ((uint64_t)digit[2] << 40) | ((uint64_t)digit[3] << 32) |
2037af03003cSMatthias Ringwald                     ((uint64_t)digit[4] << 24) | ((uint64_t)digit[5] << 16) |
2038af03003cSMatthias Ringwald                     ((uint64_t)digit[6] << 8) | (uint64_t)digit[7];
2039af03003cSMatthias Ringwald     }
2040af03003cSMatthias Ringwald }
2041af03003cSMatthias Ringwald 
2042af03003cSMatthias Ringwald #endif /* uECC_WORD_SIZE */
2043af03003cSMatthias Ringwald 
uECC_make_key(uint8_t public_key[uECC_BYTES * 2],uint8_t private_key[uECC_BYTES])2044af03003cSMatthias Ringwald int uECC_make_key(uint8_t public_key[uECC_BYTES*2], uint8_t private_key[uECC_BYTES]) {
2045af03003cSMatthias Ringwald     uECC_word_t private[uECC_WORDS];
2046af03003cSMatthias Ringwald     EccPoint public;
2047af03003cSMatthias Ringwald     uECC_word_t tries;
2048af03003cSMatthias Ringwald     for (tries = 0; tries < MAX_TRIES; ++tries) {
2049af03003cSMatthias Ringwald         if (g_rng_function((uint8_t *)private, sizeof(private)) &&
2050af03003cSMatthias Ringwald                 EccPoint_compute_public_key(&public, private)) {
2051af03003cSMatthias Ringwald             vli_nativeToBytes(private_key, private);
2052af03003cSMatthias Ringwald             vli_nativeToBytes(public_key, public.x);
2053af03003cSMatthias Ringwald             vli_nativeToBytes(public_key + uECC_BYTES, public.y);
2054af03003cSMatthias Ringwald             return 1;
2055af03003cSMatthias Ringwald         }
2056af03003cSMatthias Ringwald     }
2057af03003cSMatthias Ringwald     return 0;
2058af03003cSMatthias Ringwald }
2059af03003cSMatthias Ringwald 
uECC_shared_secret(const uint8_t public_key[uECC_BYTES * 2],const uint8_t private_key[uECC_BYTES],uint8_t secret[uECC_BYTES])2060af03003cSMatthias Ringwald int uECC_shared_secret(const uint8_t public_key[uECC_BYTES*2],
2061af03003cSMatthias Ringwald                        const uint8_t private_key[uECC_BYTES],
2062af03003cSMatthias Ringwald                        uint8_t secret[uECC_BYTES]) {
2063af03003cSMatthias Ringwald     EccPoint public;
2064af03003cSMatthias Ringwald     EccPoint product;
2065af03003cSMatthias Ringwald     uECC_word_t private[uECC_WORDS];
2066af03003cSMatthias Ringwald     uECC_word_t tmp[uECC_WORDS];
2067af03003cSMatthias Ringwald     uECC_word_t *p2[2] = {private, tmp};
2068af03003cSMatthias Ringwald     uECC_word_t random[uECC_WORDS];
20696e791780SMatthias Ringwald     uECC_word_t *initial_Z = NULL;
2070af03003cSMatthias Ringwald     uECC_word_t tries;
2071af03003cSMatthias Ringwald     uECC_word_t carry;
2072af03003cSMatthias Ringwald 
2073af03003cSMatthias Ringwald     // Try to get a random initial Z value to improve protection against side-channel
2074af03003cSMatthias Ringwald     // attacks. If the RNG fails every time (eg it was not defined), we continue so that
2075af03003cSMatthias Ringwald     // uECC_shared_secret() can still work without an RNG defined.
2076af03003cSMatthias Ringwald     for (tries = 0; tries < MAX_TRIES; ++tries) {
2077af03003cSMatthias Ringwald         if (g_rng_function((uint8_t *)random, sizeof(random)) && !vli_isZero(random)) {
2078af03003cSMatthias Ringwald             initial_Z = random;
2079af03003cSMatthias Ringwald             break;
2080af03003cSMatthias Ringwald         }
2081af03003cSMatthias Ringwald     }
2082af03003cSMatthias Ringwald 
2083af03003cSMatthias Ringwald     vli_bytesToNative(private, private_key);
2084af03003cSMatthias Ringwald     vli_bytesToNative(public.x, public_key);
2085af03003cSMatthias Ringwald     vli_bytesToNative(public.y, public_key + uECC_BYTES);
2086af03003cSMatthias Ringwald 
2087af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1)
2088af03003cSMatthias Ringwald     // Don't regularize the bitcount for secp160r1.
2089af03003cSMatthias Ringwald     EccPoint_mult(&product, &public, private, initial_Z, vli_numBits(private, uECC_WORDS));
2090af03003cSMatthias Ringwald #else
2091af03003cSMatthias Ringwald     // Regularize the bitcount for the private key so that attackers cannot use a side channel
2092af03003cSMatthias Ringwald     // attack to learn the number of leading zeros.
2093af03003cSMatthias Ringwald     carry = vli_add(private, private, curve_n);
2094af03003cSMatthias Ringwald     vli_add(tmp, private, curve_n);
2095af03003cSMatthias Ringwald     EccPoint_mult(&product, &public, p2[!carry], initial_Z, (uECC_BYTES * 8) + 1);
2096af03003cSMatthias Ringwald #endif
2097af03003cSMatthias Ringwald 
2098af03003cSMatthias Ringwald     vli_nativeToBytes(secret, product.x);
2099af03003cSMatthias Ringwald     return !EccPoint_isZero(&product);
2100af03003cSMatthias Ringwald }
2101af03003cSMatthias Ringwald 
210280dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_COMPRESSION
210380dcb211SMatthias Ringwald 
uECC_compress(const uint8_t public_key[uECC_BYTES * 2],uint8_t compressed[uECC_BYTES+1])2104af03003cSMatthias Ringwald void uECC_compress(const uint8_t public_key[uECC_BYTES*2], uint8_t compressed[uECC_BYTES+1]) {
2105af03003cSMatthias Ringwald     wordcount_t i;
2106af03003cSMatthias Ringwald     for (i = 0; i < uECC_BYTES; ++i) {
2107af03003cSMatthias Ringwald         compressed[i+1] = public_key[i];
2108af03003cSMatthias Ringwald     }
2109af03003cSMatthias Ringwald     compressed[0] = 2 + (public_key[uECC_BYTES * 2 - 1] & 0x01);
2110af03003cSMatthias Ringwald }
2111af03003cSMatthias Ringwald 
211280dcb211SMatthias Ringwald #endif
211380dcb211SMatthias Ringwald 
2114af03003cSMatthias Ringwald /* Computes result = x^3 + ax + b. result must not overlap x. */
curve_x_side(uECC_word_t * RESTRICT result,const uECC_word_t * RESTRICT x)2115af03003cSMatthias Ringwald static void curve_x_side(uECC_word_t * RESTRICT result, const uECC_word_t * RESTRICT x) {
21168334d3d8SMatthias Ringwald     static const uECC_word_t curve_b[uECC_WORDS] = uECC_CONCAT(Curve_B_, uECC_CURVE);
2117af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp256k1)
2118af03003cSMatthias Ringwald     vli_modSquare_fast(result, x); /* r = x^2 */
2119af03003cSMatthias Ringwald     vli_modMult_fast(result, result, x); /* r = x^3 */
2120af03003cSMatthias Ringwald     vli_modAdd(result, result, curve_b, curve_p); /* r = x^3 + b */
2121af03003cSMatthias Ringwald #else
2122af03003cSMatthias Ringwald     uECC_word_t _3[uECC_WORDS] = {3}; /* -a = 3 */
2123af03003cSMatthias Ringwald 
2124af03003cSMatthias Ringwald     vli_modSquare_fast(result, x); /* r = x^2 */
2125af03003cSMatthias Ringwald     vli_modSub_fast(result, result, _3); /* r = x^2 - 3 */
2126af03003cSMatthias Ringwald     vli_modMult_fast(result, result, x); /* r = x^3 - 3x */
2127af03003cSMatthias Ringwald     vli_modAdd(result, result, curve_b, curve_p); /* r = x^3 - 3x + b */
2128af03003cSMatthias Ringwald #endif
2129af03003cSMatthias Ringwald }
2130af03003cSMatthias Ringwald 
213180dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_COMPRESSION
213280dcb211SMatthias Ringwald 
uECC_decompress(const uint8_t compressed[uECC_BYTES+1],uint8_t public_key[uECC_BYTES * 2])2133af03003cSMatthias Ringwald void uECC_decompress(const uint8_t compressed[uECC_BYTES+1], uint8_t public_key[uECC_BYTES*2]) {
2134af03003cSMatthias Ringwald     EccPoint point;
2135af03003cSMatthias Ringwald     vli_bytesToNative(point.x, compressed + 1);
2136af03003cSMatthias Ringwald     curve_x_side(point.y, point.x);
2137af03003cSMatthias Ringwald     mod_sqrt(point.y);
2138af03003cSMatthias Ringwald 
2139af03003cSMatthias Ringwald     if ((point.y[0] & 0x01) != (compressed[0] & 0x01)) {
2140af03003cSMatthias Ringwald         vli_sub(point.y, curve_p, point.y);
2141af03003cSMatthias Ringwald     }
2142af03003cSMatthias Ringwald 
2143af03003cSMatthias Ringwald     vli_nativeToBytes(public_key, point.x);
2144af03003cSMatthias Ringwald     vli_nativeToBytes(public_key + uECC_BYTES, point.y);
2145af03003cSMatthias Ringwald }
2146af03003cSMatthias Ringwald 
214780dcb211SMatthias Ringwald #endif /* ENABLE_MICRO_ECC_COMPRESSION */
214880dcb211SMatthias Ringwald 
uECC_valid_public_key(const uint8_t public_key[uECC_BYTES * 2])2149af03003cSMatthias Ringwald int uECC_valid_public_key(const uint8_t public_key[uECC_BYTES*2]) {
2150af03003cSMatthias Ringwald     uECC_word_t tmp1[uECC_WORDS];
2151af03003cSMatthias Ringwald     uECC_word_t tmp2[uECC_WORDS];
2152af03003cSMatthias Ringwald     EccPoint public;
2153af03003cSMatthias Ringwald 
2154af03003cSMatthias Ringwald     vli_bytesToNative(public.x, public_key);
2155af03003cSMatthias Ringwald     vli_bytesToNative(public.y, public_key + uECC_BYTES);
2156af03003cSMatthias Ringwald 
2157af03003cSMatthias Ringwald     // The point at infinity is invalid.
2158af03003cSMatthias Ringwald     if (EccPoint_isZero(&public)) {
2159af03003cSMatthias Ringwald         return 0;
2160af03003cSMatthias Ringwald     }
2161af03003cSMatthias Ringwald 
2162af03003cSMatthias Ringwald     // x and y must be smaller than p.
2163af03003cSMatthias Ringwald     if (vli_cmp(curve_p, public.x) != 1 || vli_cmp(curve_p, public.y) != 1) {
2164af03003cSMatthias Ringwald         return 0;
2165af03003cSMatthias Ringwald     }
2166af03003cSMatthias Ringwald 
2167af03003cSMatthias Ringwald     vli_modSquare_fast(tmp1, public.y); /* tmp1 = y^2 */
2168af03003cSMatthias Ringwald     curve_x_side(tmp2, public.x); /* tmp2 = x^3 + ax + b */
2169af03003cSMatthias Ringwald 
2170af03003cSMatthias Ringwald     /* Make sure that y^2 == x^3 + ax + b */
2171af03003cSMatthias Ringwald     return (vli_cmp(tmp1, tmp2) == 0);
2172af03003cSMatthias Ringwald }
2173af03003cSMatthias Ringwald 
uECC_compute_public_key(const uint8_t private_key[uECC_BYTES],uint8_t public_key[uECC_BYTES * 2])2174af03003cSMatthias Ringwald int uECC_compute_public_key(const uint8_t private_key[uECC_BYTES],
2175af03003cSMatthias Ringwald                             uint8_t public_key[uECC_BYTES * 2]) {
2176af03003cSMatthias Ringwald     uECC_word_t private[uECC_WORDS];
2177af03003cSMatthias Ringwald     EccPoint public;
2178af03003cSMatthias Ringwald 
2179af03003cSMatthias Ringwald     vli_bytesToNative(private, private_key);
2180af03003cSMatthias Ringwald 
2181af03003cSMatthias Ringwald     if (!EccPoint_compute_public_key(&public, private)) {
2182af03003cSMatthias Ringwald         return 0;
2183af03003cSMatthias Ringwald     }
2184af03003cSMatthias Ringwald 
2185af03003cSMatthias Ringwald     vli_nativeToBytes(public_key, public.x);
2186af03003cSMatthias Ringwald     vli_nativeToBytes(public_key + uECC_BYTES, public.y);
2187af03003cSMatthias Ringwald     return 1;
2188af03003cSMatthias Ringwald }
2189af03003cSMatthias Ringwald 
uECC_bytes(void)2190af03003cSMatthias Ringwald int uECC_bytes(void) {
2191af03003cSMatthias Ringwald     return uECC_BYTES;
2192af03003cSMatthias Ringwald }
2193af03003cSMatthias Ringwald 
uECC_curve(void)2194af03003cSMatthias Ringwald int uECC_curve(void) {
2195af03003cSMatthias Ringwald     return uECC_CURVE;
2196af03003cSMatthias Ringwald }
2197af03003cSMatthias Ringwald 
2198af03003cSMatthias Ringwald /* -------- ECDSA code -------- */
2199af03003cSMatthias Ringwald 
220080dcb211SMatthias Ringwald #ifdef ENABLE_MICRO_ECC_ECDSA
220180dcb211SMatthias Ringwald 
2202af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1)
vli_clear_n(uECC_word_t * vli)2203af03003cSMatthias Ringwald static void vli_clear_n(uECC_word_t *vli) {
2204af03003cSMatthias Ringwald     vli_clear(vli);
2205af03003cSMatthias Ringwald     vli[uECC_N_WORDS - 1] = 0;
2206af03003cSMatthias Ringwald }
2207af03003cSMatthias Ringwald 
vli_isZero_n(const uECC_word_t * vli)2208af03003cSMatthias Ringwald static uECC_word_t vli_isZero_n(const uECC_word_t *vli) {
2209af03003cSMatthias Ringwald     if (vli[uECC_N_WORDS - 1]) {
2210af03003cSMatthias Ringwald         return 0;
2211af03003cSMatthias Ringwald     }
2212af03003cSMatthias Ringwald     return vli_isZero(vli);
2213af03003cSMatthias Ringwald }
2214af03003cSMatthias Ringwald 
vli_set_n(uECC_word_t * dest,const uECC_word_t * src)2215af03003cSMatthias Ringwald static void vli_set_n(uECC_word_t *dest, const uECC_word_t *src) {
2216af03003cSMatthias Ringwald     vli_set(dest, src);
2217af03003cSMatthias Ringwald     dest[uECC_N_WORDS - 1] = src[uECC_N_WORDS - 1];
2218af03003cSMatthias Ringwald }
2219af03003cSMatthias Ringwald 
vli_cmp_n(const uECC_word_t * left,const uECC_word_t * right)2220af03003cSMatthias Ringwald static cmpresult_t vli_cmp_n(const uECC_word_t *left, const uECC_word_t *right) {
2221af03003cSMatthias Ringwald     if (left[uECC_N_WORDS - 1] > right[uECC_N_WORDS - 1]) {
2222af03003cSMatthias Ringwald         return 1;
2223af03003cSMatthias Ringwald     } else if (left[uECC_N_WORDS - 1] < right[uECC_N_WORDS - 1]) {
2224af03003cSMatthias Ringwald         return -1;
2225af03003cSMatthias Ringwald     }
2226af03003cSMatthias Ringwald     return vli_cmp(left, right);
2227af03003cSMatthias Ringwald }
2228af03003cSMatthias Ringwald 
vli_rshift1_n(uECC_word_t * vli)2229af03003cSMatthias Ringwald static void vli_rshift1_n(uECC_word_t *vli) {
2230af03003cSMatthias Ringwald     vli_rshift1(vli);
2231af03003cSMatthias Ringwald     vli[uECC_N_WORDS - 2] |= vli[uECC_N_WORDS - 1] << (uECC_WORD_BITS - 1);
2232af03003cSMatthias Ringwald     vli[uECC_N_WORDS - 1] = vli[uECC_N_WORDS - 1] >> 1;
2233af03003cSMatthias Ringwald }
2234af03003cSMatthias Ringwald 
vli_add_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2235af03003cSMatthias Ringwald static uECC_word_t vli_add_n(uECC_word_t *result,
2236af03003cSMatthias Ringwald                              const uECC_word_t *left,
2237af03003cSMatthias Ringwald                              const uECC_word_t *right) {
2238af03003cSMatthias Ringwald     uECC_word_t carry = vli_add(result, left, right);
2239af03003cSMatthias Ringwald     uECC_word_t sum = left[uECC_N_WORDS - 1] + right[uECC_N_WORDS - 1] + carry;
2240af03003cSMatthias Ringwald     if (sum != left[uECC_N_WORDS - 1]) {
2241af03003cSMatthias Ringwald         carry = (sum < left[uECC_N_WORDS - 1]);
2242af03003cSMatthias Ringwald     }
2243af03003cSMatthias Ringwald     result[uECC_N_WORDS - 1] = sum;
2244af03003cSMatthias Ringwald     return carry;
2245af03003cSMatthias Ringwald }
2246af03003cSMatthias Ringwald 
vli_sub_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2247af03003cSMatthias Ringwald static uECC_word_t vli_sub_n(uECC_word_t *result,
2248af03003cSMatthias Ringwald                              const uECC_word_t *left,
2249af03003cSMatthias Ringwald                              const uECC_word_t *right) {
2250af03003cSMatthias Ringwald     uECC_word_t borrow = vli_sub(result, left, right);
2251af03003cSMatthias Ringwald     uECC_word_t diff = left[uECC_N_WORDS - 1] - right[uECC_N_WORDS - 1] - borrow;
2252af03003cSMatthias Ringwald     if (diff != left[uECC_N_WORDS - 1]) {
2253af03003cSMatthias Ringwald         borrow = (diff > left[uECC_N_WORDS - 1]);
2254af03003cSMatthias Ringwald     }
2255af03003cSMatthias Ringwald     result[uECC_N_WORDS - 1] = diff;
2256af03003cSMatthias Ringwald     return borrow;
2257af03003cSMatthias Ringwald }
2258af03003cSMatthias Ringwald 
2259af03003cSMatthias Ringwald #if !muladd_exists
muladd(uECC_word_t a,uECC_word_t b,uECC_word_t * r0,uECC_word_t * r1,uECC_word_t * r2)2260af03003cSMatthias Ringwald static void muladd(uECC_word_t a,
2261af03003cSMatthias Ringwald                    uECC_word_t b,
2262af03003cSMatthias Ringwald                    uECC_word_t *r0,
2263af03003cSMatthias Ringwald                    uECC_word_t *r1,
2264af03003cSMatthias Ringwald                    uECC_word_t *r2) {
2265af03003cSMatthias Ringwald     uECC_dword_t p = (uECC_dword_t)a * b;
2266af03003cSMatthias Ringwald     uECC_dword_t r01 = ((uECC_dword_t)(*r1) << uECC_WORD_BITS) | *r0;
2267af03003cSMatthias Ringwald     r01 += p;
2268af03003cSMatthias Ringwald     *r2 += (r01 < p);
2269af03003cSMatthias Ringwald     *r1 = r01 >> uECC_WORD_BITS;
2270af03003cSMatthias Ringwald     *r0 = (uECC_word_t)r01;
2271af03003cSMatthias Ringwald }
2272af03003cSMatthias Ringwald #define muladd_exists 1
2273af03003cSMatthias Ringwald #endif
2274af03003cSMatthias Ringwald 
vli_mult_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2275af03003cSMatthias Ringwald static void vli_mult_n(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
2276af03003cSMatthias Ringwald     uECC_word_t r0 = 0;
2277af03003cSMatthias Ringwald     uECC_word_t r1 = 0;
2278af03003cSMatthias Ringwald     uECC_word_t r2 = 0;
2279af03003cSMatthias Ringwald     wordcount_t i, k;
2280af03003cSMatthias Ringwald 
2281af03003cSMatthias Ringwald     for (k = 0; k < uECC_N_WORDS * 2 - 1; ++k) {
2282af03003cSMatthias Ringwald         wordcount_t min = (k < uECC_N_WORDS ? 0 : (k + 1) - uECC_N_WORDS);
2283af03003cSMatthias Ringwald         wordcount_t max = (k < uECC_N_WORDS ? k : uECC_N_WORDS - 1);
2284af03003cSMatthias Ringwald         for (i = min; i <= max; ++i) {
2285af03003cSMatthias Ringwald             muladd(left[i], right[k - i], &r0, &r1, &r2);
2286af03003cSMatthias Ringwald         }
2287af03003cSMatthias Ringwald         result[k] = r0;
2288af03003cSMatthias Ringwald         r0 = r1;
2289af03003cSMatthias Ringwald         r1 = r2;
2290af03003cSMatthias Ringwald         r2 = 0;
2291af03003cSMatthias Ringwald     }
2292af03003cSMatthias Ringwald     result[uECC_N_WORDS * 2 - 1] = r0;
2293af03003cSMatthias Ringwald }
2294af03003cSMatthias Ringwald 
vli_modAdd_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right,const uECC_word_t * mod)2295af03003cSMatthias Ringwald static void vli_modAdd_n(uECC_word_t *result,
2296af03003cSMatthias Ringwald                          const uECC_word_t *left,
2297af03003cSMatthias Ringwald                          const uECC_word_t *right,
2298af03003cSMatthias Ringwald                          const uECC_word_t *mod) {
2299af03003cSMatthias Ringwald     uECC_word_t carry = vli_add_n(result, left, right);
2300af03003cSMatthias Ringwald     if (carry || vli_cmp_n(result, mod) >= 0) {
2301af03003cSMatthias Ringwald         vli_sub_n(result, result, mod);
2302af03003cSMatthias Ringwald     }
2303af03003cSMatthias Ringwald }
2304af03003cSMatthias Ringwald 
vli_modInv_n(uECC_word_t * result,const uECC_word_t * input,const uECC_word_t * mod)2305af03003cSMatthias Ringwald static void vli_modInv_n(uECC_word_t *result, const uECC_word_t *input, const uECC_word_t *mod) {
2306af03003cSMatthias Ringwald     uECC_word_t a[uECC_N_WORDS], b[uECC_N_WORDS], u[uECC_N_WORDS], v[uECC_N_WORDS];
2307af03003cSMatthias Ringwald     uECC_word_t carry;
2308af03003cSMatthias Ringwald     cmpresult_t cmpResult;
2309af03003cSMatthias Ringwald 
2310af03003cSMatthias Ringwald     if (vli_isZero_n(input)) {
2311af03003cSMatthias Ringwald         vli_clear_n(result);
2312af03003cSMatthias Ringwald         return;
2313af03003cSMatthias Ringwald     }
2314af03003cSMatthias Ringwald 
2315af03003cSMatthias Ringwald     vli_set_n(a, input);
2316af03003cSMatthias Ringwald     vli_set_n(b, mod);
2317af03003cSMatthias Ringwald     vli_clear_n(u);
2318af03003cSMatthias Ringwald     u[0] = 1;
2319af03003cSMatthias Ringwald     vli_clear_n(v);
2320af03003cSMatthias Ringwald     while ((cmpResult = vli_cmp_n(a, b)) != 0) {
2321af03003cSMatthias Ringwald         carry = 0;
2322af03003cSMatthias Ringwald         if (EVEN(a)) {
2323af03003cSMatthias Ringwald             vli_rshift1_n(a);
2324af03003cSMatthias Ringwald             if (!EVEN(u)) {
2325af03003cSMatthias Ringwald                 carry = vli_add_n(u, u, mod);
2326af03003cSMatthias Ringwald             }
2327af03003cSMatthias Ringwald             vli_rshift1_n(u);
2328af03003cSMatthias Ringwald             if (carry) {
2329af03003cSMatthias Ringwald                 u[uECC_N_WORDS - 1] |= HIGH_BIT_SET;
2330af03003cSMatthias Ringwald             }
2331af03003cSMatthias Ringwald         } else if (EVEN(b)) {
2332af03003cSMatthias Ringwald             vli_rshift1_n(b);
2333af03003cSMatthias Ringwald             if (!EVEN(v)) {
2334af03003cSMatthias Ringwald                 carry = vli_add_n(v, v, mod);
2335af03003cSMatthias Ringwald             }
2336af03003cSMatthias Ringwald             vli_rshift1_n(v);
2337af03003cSMatthias Ringwald             if (carry) {
2338af03003cSMatthias Ringwald                 v[uECC_N_WORDS - 1] |= HIGH_BIT_SET;
2339af03003cSMatthias Ringwald             }
2340af03003cSMatthias Ringwald         } else if (cmpResult > 0) {
2341af03003cSMatthias Ringwald             vli_sub_n(a, a, b);
2342af03003cSMatthias Ringwald             vli_rshift1_n(a);
2343af03003cSMatthias Ringwald             if (vli_cmp_n(u, v) < 0) {
2344af03003cSMatthias Ringwald                 vli_add_n(u, u, mod);
2345af03003cSMatthias Ringwald             }
2346af03003cSMatthias Ringwald             vli_sub_n(u, u, v);
2347af03003cSMatthias Ringwald             if (!EVEN(u)) {
2348af03003cSMatthias Ringwald                 carry = vli_add_n(u, u, mod);
2349af03003cSMatthias Ringwald             }
2350af03003cSMatthias Ringwald             vli_rshift1_n(u);
2351af03003cSMatthias Ringwald             if (carry) {
2352af03003cSMatthias Ringwald                 u[uECC_N_WORDS - 1] |= HIGH_BIT_SET;
2353af03003cSMatthias Ringwald             }
2354af03003cSMatthias Ringwald         } else {
2355af03003cSMatthias Ringwald             vli_sub_n(b, b, a);
2356af03003cSMatthias Ringwald             vli_rshift1_n(b);
2357af03003cSMatthias Ringwald             if (vli_cmp_n(v, u) < 0) {
2358af03003cSMatthias Ringwald                 vli_add_n(v, v, mod);
2359af03003cSMatthias Ringwald             }
2360af03003cSMatthias Ringwald             vli_sub_n(v, v, u);
2361af03003cSMatthias Ringwald             if (!EVEN(v)) {
2362af03003cSMatthias Ringwald                 carry = vli_add_n(v, v, mod);
2363af03003cSMatthias Ringwald             }
2364af03003cSMatthias Ringwald             vli_rshift1_n(v);
2365af03003cSMatthias Ringwald             if (carry) {
2366af03003cSMatthias Ringwald                 v[uECC_N_WORDS - 1] |= HIGH_BIT_SET;
2367af03003cSMatthias Ringwald             }
2368af03003cSMatthias Ringwald         }
2369af03003cSMatthias Ringwald     }
2370af03003cSMatthias Ringwald     vli_set_n(result, u);
2371af03003cSMatthias Ringwald }
2372af03003cSMatthias Ringwald 
vli2_rshift1_n(uECC_word_t * vli)2373af03003cSMatthias Ringwald static void vli2_rshift1_n(uECC_word_t *vli) {
2374af03003cSMatthias Ringwald     vli_rshift1_n(vli);
2375af03003cSMatthias Ringwald     vli[uECC_N_WORDS - 1] |= vli[uECC_N_WORDS] << (uECC_WORD_BITS - 1);
2376af03003cSMatthias Ringwald     vli_rshift1_n(vli + uECC_N_WORDS);
2377af03003cSMatthias Ringwald }
2378af03003cSMatthias Ringwald 
vli2_sub_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2379af03003cSMatthias Ringwald static uECC_word_t vli2_sub_n(uECC_word_t *result,
2380af03003cSMatthias Ringwald                               const uECC_word_t *left,
2381af03003cSMatthias Ringwald                               const uECC_word_t *right) {
2382af03003cSMatthias Ringwald     uECC_word_t borrow = 0;
2383af03003cSMatthias Ringwald     wordcount_t i;
2384af03003cSMatthias Ringwald     for (i = 0; i < uECC_N_WORDS * 2; ++i) {
2385af03003cSMatthias Ringwald         uECC_word_t diff = left[i] - right[i] - borrow;
2386af03003cSMatthias Ringwald         if (diff != left[i]) {
2387af03003cSMatthias Ringwald             borrow = (diff > left[i]);
2388af03003cSMatthias Ringwald         }
2389af03003cSMatthias Ringwald         result[i] = diff;
2390af03003cSMatthias Ringwald     }
2391af03003cSMatthias Ringwald     return borrow;
2392af03003cSMatthias Ringwald }
2393af03003cSMatthias Ringwald 
2394af03003cSMatthias Ringwald /* Computes result = (left * right) % curve_n. */
vli_modMult_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2395af03003cSMatthias Ringwald static void vli_modMult_n(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
2396af03003cSMatthias Ringwald     bitcount_t i;
2397af03003cSMatthias Ringwald     uECC_word_t product[2 * uECC_N_WORDS];
2398af03003cSMatthias Ringwald     uECC_word_t modMultiple[2 * uECC_N_WORDS];
2399af03003cSMatthias Ringwald     uECC_word_t tmp[2 * uECC_N_WORDS];
2400af03003cSMatthias Ringwald     uECC_word_t *v[2] = {tmp, product};
2401af03003cSMatthias Ringwald     uECC_word_t index = 1;
2402af03003cSMatthias Ringwald 
2403af03003cSMatthias Ringwald     vli_mult_n(product, left, right);
2404af03003cSMatthias Ringwald     vli_clear_n(modMultiple);
2405af03003cSMatthias Ringwald     vli_set(modMultiple + uECC_N_WORDS + 1, curve_n);
2406af03003cSMatthias Ringwald     vli_rshift1(modMultiple + uECC_N_WORDS + 1);
2407af03003cSMatthias Ringwald     modMultiple[2 * uECC_N_WORDS - 1] |= HIGH_BIT_SET;
2408af03003cSMatthias Ringwald     modMultiple[uECC_N_WORDS] = HIGH_BIT_SET;
2409af03003cSMatthias Ringwald 
2410af03003cSMatthias Ringwald     for (i = 0;
2411af03003cSMatthias Ringwald          i <= ((((bitcount_t)uECC_N_WORDS) << uECC_WORD_BITS_SHIFT) + (uECC_WORD_BITS - 1));
2412af03003cSMatthias Ringwald          ++i) {
2413af03003cSMatthias Ringwald         uECC_word_t borrow = vli2_sub_n(v[1 - index], v[index], modMultiple);
2414af03003cSMatthias Ringwald         index = !(index ^ borrow); /* Swap the index if there was no borrow */
2415af03003cSMatthias Ringwald         vli2_rshift1_n(modMultiple);
2416af03003cSMatthias Ringwald     }
2417af03003cSMatthias Ringwald     vli_set_n(result, v[index]);
2418af03003cSMatthias Ringwald }
2419af03003cSMatthias Ringwald 
2420af03003cSMatthias Ringwald #else
2421af03003cSMatthias Ringwald 
2422af03003cSMatthias Ringwald #define vli_cmp_n vli_cmp
2423af03003cSMatthias Ringwald #define vli_modInv_n vli_modInv
2424af03003cSMatthias Ringwald #define vli_modAdd_n vli_modAdd
2425af03003cSMatthias Ringwald 
vli2_rshift1(uECC_word_t * vli)2426af03003cSMatthias Ringwald static void vli2_rshift1(uECC_word_t *vli) {
2427af03003cSMatthias Ringwald     vli_rshift1(vli);
2428af03003cSMatthias Ringwald     vli[uECC_WORDS - 1] |= vli[uECC_WORDS] << (uECC_WORD_BITS - 1);
2429af03003cSMatthias Ringwald     vli_rshift1(vli + uECC_WORDS);
2430af03003cSMatthias Ringwald }
2431af03003cSMatthias Ringwald 
vli2_sub(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2432af03003cSMatthias Ringwald static uECC_word_t vli2_sub(uECC_word_t *result,
2433af03003cSMatthias Ringwald                             const uECC_word_t *left,
2434af03003cSMatthias Ringwald                             const uECC_word_t *right) {
2435af03003cSMatthias Ringwald     uECC_word_t borrow = 0;
2436af03003cSMatthias Ringwald     wordcount_t i;
2437af03003cSMatthias Ringwald     for (i = 0; i < uECC_WORDS * 2; ++i) {
2438af03003cSMatthias Ringwald         uECC_word_t diff = left[i] - right[i] - borrow;
2439af03003cSMatthias Ringwald         if (diff != left[i]) {
2440af03003cSMatthias Ringwald             borrow = (diff > left[i]);
2441af03003cSMatthias Ringwald         }
2442af03003cSMatthias Ringwald         result[i] = diff;
2443af03003cSMatthias Ringwald     }
2444af03003cSMatthias Ringwald     return borrow;
2445af03003cSMatthias Ringwald }
2446af03003cSMatthias Ringwald 
2447af03003cSMatthias Ringwald /* Computes result = (left * right) % curve_n. */
vli_modMult_n(uECC_word_t * result,const uECC_word_t * left,const uECC_word_t * right)2448af03003cSMatthias Ringwald static void vli_modMult_n(uECC_word_t *result, const uECC_word_t *left, const uECC_word_t *right) {
2449af03003cSMatthias Ringwald     uECC_word_t product[2 * uECC_WORDS];
2450af03003cSMatthias Ringwald     uECC_word_t modMultiple[2 * uECC_WORDS];
2451af03003cSMatthias Ringwald     uECC_word_t tmp[2 * uECC_WORDS];
2452af03003cSMatthias Ringwald     uECC_word_t *v[2] = {tmp, product};
2453af03003cSMatthias Ringwald     bitcount_t i;
2454af03003cSMatthias Ringwald     uECC_word_t index = 1;
2455af03003cSMatthias Ringwald 
2456af03003cSMatthias Ringwald     vli_mult(product, left, right);
2457af03003cSMatthias Ringwald     vli_set(modMultiple + uECC_WORDS, curve_n); /* works if curve_n has its highest bit set */
2458af03003cSMatthias Ringwald     vli_clear(modMultiple);
2459af03003cSMatthias Ringwald 
2460af03003cSMatthias Ringwald     for (i = 0; i <= uECC_BYTES * 8; ++i) {
2461af03003cSMatthias Ringwald         uECC_word_t borrow = vli2_sub(v[1 - index], v[index], modMultiple);
2462af03003cSMatthias Ringwald         index = !(index ^ borrow); /* Swap the index if there was no borrow */
2463af03003cSMatthias Ringwald         vli2_rshift1(modMultiple);
2464af03003cSMatthias Ringwald     }
2465af03003cSMatthias Ringwald     vli_set(result, v[index]);
2466af03003cSMatthias Ringwald }
2467af03003cSMatthias Ringwald #endif /* (uECC_CURVE != uECC_secp160r1) */
2468af03003cSMatthias Ringwald 
uECC_sign_with_k(const uint8_t private_key[uECC_BYTES],const uint8_t message_hash[uECC_BYTES],uECC_word_t k[uECC_N_WORDS],uint8_t signature[uECC_BYTES * 2])2469af03003cSMatthias Ringwald static int uECC_sign_with_k(const uint8_t private_key[uECC_BYTES],
2470af03003cSMatthias Ringwald                             const uint8_t message_hash[uECC_BYTES],
2471af03003cSMatthias Ringwald                             uECC_word_t k[uECC_N_WORDS],
2472af03003cSMatthias Ringwald                             uint8_t signature[uECC_BYTES*2]) {
2473af03003cSMatthias Ringwald     uECC_word_t tmp[uECC_N_WORDS];
2474af03003cSMatthias Ringwald     uECC_word_t s[uECC_N_WORDS];
2475af03003cSMatthias Ringwald     uECC_word_t *k2[2] = {tmp, s};
2476af03003cSMatthias Ringwald     EccPoint p;
2477af03003cSMatthias Ringwald     uECC_word_t carry;
2478af03003cSMatthias Ringwald     uECC_word_t tries;
2479af03003cSMatthias Ringwald 
2480af03003cSMatthias Ringwald     /* Make sure 0 < k < curve_n */
2481af03003cSMatthias Ringwald     if (vli_isZero(k) || vli_cmp_n(curve_n, k) != 1) {
2482af03003cSMatthias Ringwald         return 0;
2483af03003cSMatthias Ringwald     }
2484af03003cSMatthias Ringwald 
2485af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1)
2486af03003cSMatthias Ringwald     /* Make sure that we don't leak timing information about k.
2487af03003cSMatthias Ringwald        See http://eprint.iacr.org/2011/232.pdf */
2488af03003cSMatthias Ringwald     vli_add_n(tmp, k, curve_n);
2489af03003cSMatthias Ringwald     carry = (tmp[uECC_WORDS] & 0x02);
2490af03003cSMatthias Ringwald     vli_add_n(s, tmp, curve_n);
2491af03003cSMatthias Ringwald 
2492af03003cSMatthias Ringwald     /* p = k * G */
24936e791780SMatthias Ringwald     EccPoint_mult(&p, &curve_G, k2[!carry], NULL, (uECC_BYTES * 8) + 2);
2494af03003cSMatthias Ringwald #else
2495af03003cSMatthias Ringwald     /* Make sure that we don't leak timing information about k.
2496af03003cSMatthias Ringwald        See http://eprint.iacr.org/2011/232.pdf */
2497af03003cSMatthias Ringwald     carry = vli_add(tmp, k, curve_n);
2498af03003cSMatthias Ringwald     vli_add(s, tmp, curve_n);
2499af03003cSMatthias Ringwald 
2500af03003cSMatthias Ringwald     /* p = k * G */
25016e791780SMatthias Ringwald     EccPoint_mult(&p, &curve_G, k2[!carry], NULL, (uECC_BYTES * 8) + 1);
2502af03003cSMatthias Ringwald 
2503af03003cSMatthias Ringwald     /* r = x1 (mod n) */
2504af03003cSMatthias Ringwald     if (vli_cmp(curve_n, p.x) != 1) {
2505af03003cSMatthias Ringwald         vli_sub(p.x, p.x, curve_n);
2506af03003cSMatthias Ringwald     }
2507af03003cSMatthias Ringwald #endif
2508af03003cSMatthias Ringwald     if (vli_isZero(p.x)) {
2509af03003cSMatthias Ringwald         return 0;
2510af03003cSMatthias Ringwald     }
2511af03003cSMatthias Ringwald 
2512af03003cSMatthias Ringwald     // Attempt to get a random number to prevent side channel analysis of k.
2513af03003cSMatthias Ringwald     // If the RNG fails every time (eg it was not defined), we continue so that
2514af03003cSMatthias Ringwald     // deterministic signing can still work (with reduced security) without
2515af03003cSMatthias Ringwald     // an RNG defined.
2516af03003cSMatthias Ringwald     carry = 0; // use to signal that the RNG succeeded at least once.
2517af03003cSMatthias Ringwald     for (tries = 0; tries < MAX_TRIES; ++tries) {
2518af03003cSMatthias Ringwald         if (!g_rng_function((uint8_t *)tmp, sizeof(tmp))) {
2519af03003cSMatthias Ringwald             continue;
2520af03003cSMatthias Ringwald         }
2521af03003cSMatthias Ringwald         carry = 1;
2522af03003cSMatthias Ringwald         if (!vli_isZero(tmp)) {
2523af03003cSMatthias Ringwald             break;
2524af03003cSMatthias Ringwald         }
2525af03003cSMatthias Ringwald     }
2526af03003cSMatthias Ringwald     if (!carry) {
2527af03003cSMatthias Ringwald         vli_clear(tmp);
2528af03003cSMatthias Ringwald         tmp[0] = 1;
2529af03003cSMatthias Ringwald     }
2530af03003cSMatthias Ringwald 
2531af03003cSMatthias Ringwald     /* Prevent side channel analysis of vli_modInv() to determine
2532af03003cSMatthias Ringwald        bits of k / the private key by premultiplying by a random number */
2533af03003cSMatthias Ringwald     vli_modMult_n(k, k, tmp); /* k' = rand * k */
2534af03003cSMatthias Ringwald     vli_modInv_n(k, k, curve_n); /* k = 1 / k' */
2535af03003cSMatthias Ringwald     vli_modMult_n(k, k, tmp); /* k = 1 / k */
2536af03003cSMatthias Ringwald 
2537af03003cSMatthias Ringwald     vli_nativeToBytes(signature, p.x); /* store r */
2538af03003cSMatthias Ringwald 
2539af03003cSMatthias Ringwald     tmp[uECC_N_WORDS - 1] = 0;
2540af03003cSMatthias Ringwald     vli_bytesToNative(tmp, private_key); /* tmp = d */
2541af03003cSMatthias Ringwald     s[uECC_N_WORDS - 1] = 0;
2542af03003cSMatthias Ringwald     vli_set(s, p.x);
2543af03003cSMatthias Ringwald     vli_modMult_n(s, tmp, s); /* s = r*d */
2544af03003cSMatthias Ringwald 
2545af03003cSMatthias Ringwald     vli_bytesToNative(tmp, message_hash);
2546af03003cSMatthias Ringwald     vli_modAdd_n(s, tmp, s, curve_n); /* s = e + r*d */
2547af03003cSMatthias Ringwald     vli_modMult_n(s, s, k); /* s = (e + r*d) / k */
2548af03003cSMatthias Ringwald #if (uECC_CURVE == uECC_secp160r1)
2549af03003cSMatthias Ringwald     if (s[uECC_N_WORDS - 1]) {
2550af03003cSMatthias Ringwald         return 0;
2551af03003cSMatthias Ringwald     }
2552af03003cSMatthias Ringwald #endif
2553af03003cSMatthias Ringwald     vli_nativeToBytes(signature + uECC_BYTES, s);
2554af03003cSMatthias Ringwald     return 1;
2555af03003cSMatthias Ringwald }
2556af03003cSMatthias Ringwald 
uECC_sign(const uint8_t private_key[uECC_BYTES],const uint8_t message_hash[uECC_BYTES],uint8_t signature[uECC_BYTES * 2])2557af03003cSMatthias Ringwald int uECC_sign(const uint8_t private_key[uECC_BYTES],
2558af03003cSMatthias Ringwald               const uint8_t message_hash[uECC_BYTES],
2559af03003cSMatthias Ringwald               uint8_t signature[uECC_BYTES*2]) {
2560af03003cSMatthias Ringwald     uECC_word_t k[uECC_N_WORDS];
2561af03003cSMatthias Ringwald     uECC_word_t tries;
2562af03003cSMatthias Ringwald 
2563af03003cSMatthias Ringwald     for (tries = 0; tries < MAX_TRIES; ++tries) {
2564af03003cSMatthias Ringwald         if(g_rng_function((uint8_t *)k, sizeof(k))) {
2565af03003cSMatthias Ringwald         #if (uECC_CURVE == uECC_secp160r1)
2566af03003cSMatthias Ringwald             k[uECC_WORDS] &= 0x01;
2567af03003cSMatthias Ringwald         #endif
2568af03003cSMatthias Ringwald             if (uECC_sign_with_k(private_key, message_hash, k, signature)) {
2569af03003cSMatthias Ringwald                 return 1;
2570af03003cSMatthias Ringwald             }
2571af03003cSMatthias Ringwald         }
2572af03003cSMatthias Ringwald     }
2573af03003cSMatthias Ringwald     return 0;
2574af03003cSMatthias Ringwald }
2575af03003cSMatthias Ringwald 
2576af03003cSMatthias Ringwald /* Compute an HMAC using K as a key (as in RFC 6979). Note that K is always
2577af03003cSMatthias Ringwald    the same size as the hash result size. */
HMAC_init(uECC_HashContext * hash_context,const uint8_t * K)2578af03003cSMatthias Ringwald static void HMAC_init(uECC_HashContext *hash_context, const uint8_t *K) {
2579af03003cSMatthias Ringwald     uint8_t *pad = hash_context->tmp + 2 * hash_context->result_size;
2580af03003cSMatthias Ringwald     unsigned i;
2581af03003cSMatthias Ringwald     for (i = 0; i < hash_context->result_size; ++i)
2582af03003cSMatthias Ringwald         pad[i] = K[i] ^ 0x36;
2583af03003cSMatthias Ringwald     for (; i < hash_context->block_size; ++i)
2584af03003cSMatthias Ringwald         pad[i] = 0x36;
2585af03003cSMatthias Ringwald 
2586af03003cSMatthias Ringwald     hash_context->init_hash(hash_context);
2587af03003cSMatthias Ringwald     hash_context->update_hash(hash_context, pad, hash_context->block_size);
2588af03003cSMatthias Ringwald }
2589af03003cSMatthias Ringwald 
HMAC_update(uECC_HashContext * hash_context,const uint8_t * message,unsigned message_size)2590af03003cSMatthias Ringwald static void HMAC_update(uECC_HashContext *hash_context,
2591af03003cSMatthias Ringwald                         const uint8_t *message,
2592af03003cSMatthias Ringwald                         unsigned message_size) {
2593af03003cSMatthias Ringwald     hash_context->update_hash(hash_context, message, message_size);
2594af03003cSMatthias Ringwald }
2595af03003cSMatthias Ringwald 
HMAC_finish(uECC_HashContext * hash_context,const uint8_t * K,uint8_t * result)2596af03003cSMatthias Ringwald static void HMAC_finish(uECC_HashContext *hash_context, const uint8_t *K, uint8_t *result) {
2597af03003cSMatthias Ringwald     uint8_t *pad = hash_context->tmp + 2 * hash_context->result_size;
2598af03003cSMatthias Ringwald     unsigned i;
2599af03003cSMatthias Ringwald     for (i = 0; i < hash_context->result_size; ++i)
2600af03003cSMatthias Ringwald         pad[i] = K[i] ^ 0x5c;
2601af03003cSMatthias Ringwald     for (; i < hash_context->block_size; ++i)
2602af03003cSMatthias Ringwald         pad[i] = 0x5c;
2603af03003cSMatthias Ringwald 
2604af03003cSMatthias Ringwald     hash_context->finish_hash(hash_context, result);
2605af03003cSMatthias Ringwald 
2606af03003cSMatthias Ringwald     hash_context->init_hash(hash_context);
2607af03003cSMatthias Ringwald     hash_context->update_hash(hash_context, pad, hash_context->block_size);
2608af03003cSMatthias Ringwald     hash_context->update_hash(hash_context, result, hash_context->result_size);
2609af03003cSMatthias Ringwald     hash_context->finish_hash(hash_context, result);
2610af03003cSMatthias Ringwald }
2611af03003cSMatthias Ringwald 
2612af03003cSMatthias Ringwald /* V = HMAC_K(V) */
update_V(uECC_HashContext * hash_context,uint8_t * K,uint8_t * V)2613af03003cSMatthias Ringwald static void update_V(uECC_HashContext *hash_context, uint8_t *K, uint8_t *V) {
2614af03003cSMatthias Ringwald     HMAC_init(hash_context, K);
2615af03003cSMatthias Ringwald     HMAC_update(hash_context, V, hash_context->result_size);
2616af03003cSMatthias Ringwald     HMAC_finish(hash_context, K, V);
2617af03003cSMatthias Ringwald }
2618af03003cSMatthias Ringwald 
2619af03003cSMatthias Ringwald /* Deterministic signing, similar to RFC 6979. Differences are:
2620af03003cSMatthias Ringwald     * We just use (truncated) H(m) directly rather than bits2octets(H(m))
2621af03003cSMatthias Ringwald       (it is not reduced modulo curve_n).
2622af03003cSMatthias Ringwald     * We generate a value for k (aka T) directly rather than converting endianness.
2623af03003cSMatthias Ringwald 
2624af03003cSMatthias Ringwald    Layout of hash_context->tmp: <K> | <V> | (1 byte overlapped 0x00 or 0x01) / <HMAC pad> */
uECC_sign_deterministic(const uint8_t private_key[uECC_BYTES],const uint8_t message_hash[uECC_BYTES],uECC_HashContext * hash_context,uint8_t signature[uECC_BYTES * 2])2625af03003cSMatthias Ringwald int uECC_sign_deterministic(const uint8_t private_key[uECC_BYTES],
2626af03003cSMatthias Ringwald                             const uint8_t message_hash[uECC_BYTES],
2627af03003cSMatthias Ringwald                             uECC_HashContext *hash_context,
2628af03003cSMatthias Ringwald                             uint8_t signature[uECC_BYTES*2]) {
2629af03003cSMatthias Ringwald     uint8_t *K = hash_context->tmp;
2630af03003cSMatthias Ringwald     uint8_t *V = K + hash_context->result_size;
2631af03003cSMatthias Ringwald     uECC_word_t tries;
2632af03003cSMatthias Ringwald     unsigned i;
2633af03003cSMatthias Ringwald     for (i = 0; i < hash_context->result_size; ++i) {
2634af03003cSMatthias Ringwald         V[i] = 0x01;
2635af03003cSMatthias Ringwald         K[i] = 0;
2636af03003cSMatthias Ringwald     }
2637af03003cSMatthias Ringwald 
2638af03003cSMatthias Ringwald     // K = HMAC_K(V || 0x00 || int2octets(x) || h(m))
2639af03003cSMatthias Ringwald     HMAC_init(hash_context, K);
2640af03003cSMatthias Ringwald     V[hash_context->result_size] = 0x00;
2641af03003cSMatthias Ringwald     HMAC_update(hash_context, V, hash_context->result_size + 1);
2642af03003cSMatthias Ringwald     HMAC_update(hash_context, private_key, uECC_BYTES);
2643af03003cSMatthias Ringwald     HMAC_update(hash_context, message_hash, uECC_BYTES);
2644af03003cSMatthias Ringwald     HMAC_finish(hash_context, K, K);
2645af03003cSMatthias Ringwald 
2646af03003cSMatthias Ringwald     update_V(hash_context, K, V);
2647af03003cSMatthias Ringwald 
2648af03003cSMatthias Ringwald     // K = HMAC_K(V || 0x01 || int2octets(x) || h(m))
2649af03003cSMatthias Ringwald     HMAC_init(hash_context, K);
2650af03003cSMatthias Ringwald     V[hash_context->result_size] = 0x01;
2651af03003cSMatthias Ringwald     HMAC_update(hash_context, V, hash_context->result_size + 1);
2652af03003cSMatthias Ringwald     HMAC_update(hash_context, private_key, uECC_BYTES);
2653af03003cSMatthias Ringwald     HMAC_update(hash_context, message_hash, uECC_BYTES);
2654af03003cSMatthias Ringwald     HMAC_finish(hash_context, K, K);
2655af03003cSMatthias Ringwald 
2656af03003cSMatthias Ringwald     update_V(hash_context, K, V);
2657af03003cSMatthias Ringwald 
2658af03003cSMatthias Ringwald     for (tries = 0; tries < MAX_TRIES; ++tries) {
2659af03003cSMatthias Ringwald         uECC_word_t T[uECC_N_WORDS];
2660af03003cSMatthias Ringwald         uint8_t *T_ptr = (uint8_t *)T;
2661af03003cSMatthias Ringwald         unsigned T_bytes = 0;
2662af03003cSMatthias Ringwald         while (T_bytes < sizeof(T)) {
2663af03003cSMatthias Ringwald             update_V(hash_context, K, V);
2664af03003cSMatthias Ringwald             for (i = 0; i < hash_context->result_size && T_bytes < sizeof(T); ++i, ++T_bytes) {
2665af03003cSMatthias Ringwald                 T_ptr[T_bytes] = V[i];
2666af03003cSMatthias Ringwald             }
2667af03003cSMatthias Ringwald         }
2668af03003cSMatthias Ringwald     #if (uECC_CURVE == uECC_secp160r1)
2669af03003cSMatthias Ringwald         T[uECC_WORDS] &= 0x01;
2670af03003cSMatthias Ringwald     #endif
2671af03003cSMatthias Ringwald 
2672af03003cSMatthias Ringwald         if (uECC_sign_with_k(private_key, message_hash, T, signature)) {
2673af03003cSMatthias Ringwald             return 1;
2674af03003cSMatthias Ringwald         }
2675af03003cSMatthias Ringwald 
2676af03003cSMatthias Ringwald         // K = HMAC_K(V || 0x00)
2677af03003cSMatthias Ringwald         HMAC_init(hash_context, K);
2678af03003cSMatthias Ringwald         V[hash_context->result_size] = 0x00;
2679af03003cSMatthias Ringwald         HMAC_update(hash_context, V, hash_context->result_size + 1);
2680af03003cSMatthias Ringwald         HMAC_finish(hash_context, K, K);
2681af03003cSMatthias Ringwald 
2682af03003cSMatthias Ringwald         update_V(hash_context, K, V);
2683af03003cSMatthias Ringwald     }
2684af03003cSMatthias Ringwald     return 0;
2685af03003cSMatthias Ringwald }
2686af03003cSMatthias Ringwald 
smax(bitcount_t a,bitcount_t b)2687af03003cSMatthias Ringwald static bitcount_t smax(bitcount_t a, bitcount_t b) {
2688af03003cSMatthias Ringwald     return (a > b ? a : b);
2689af03003cSMatthias Ringwald }
2690af03003cSMatthias Ringwald 
uECC_verify(const uint8_t public_key[uECC_BYTES * 2],const uint8_t hash[uECC_BYTES],const uint8_t signature[uECC_BYTES * 2])2691af03003cSMatthias Ringwald int uECC_verify(const uint8_t public_key[uECC_BYTES*2],
2692af03003cSMatthias Ringwald                 const uint8_t hash[uECC_BYTES],
2693af03003cSMatthias Ringwald                 const uint8_t signature[uECC_BYTES*2]) {
2694af03003cSMatthias Ringwald     uECC_word_t u1[uECC_N_WORDS], u2[uECC_N_WORDS];
2695af03003cSMatthias Ringwald     uECC_word_t z[uECC_N_WORDS];
2696af03003cSMatthias Ringwald     EccPoint public, sum;
2697af03003cSMatthias Ringwald     uECC_word_t rx[uECC_WORDS];
2698af03003cSMatthias Ringwald     uECC_word_t ry[uECC_WORDS];
2699af03003cSMatthias Ringwald     uECC_word_t tx[uECC_WORDS];
2700af03003cSMatthias Ringwald     uECC_word_t ty[uECC_WORDS];
2701af03003cSMatthias Ringwald     uECC_word_t tz[uECC_WORDS];
2702af03003cSMatthias Ringwald     const EccPoint *points[4];
2703af03003cSMatthias Ringwald     const EccPoint *point;
2704af03003cSMatthias Ringwald     bitcount_t numBits;
2705af03003cSMatthias Ringwald     bitcount_t i;
2706af03003cSMatthias Ringwald     uECC_word_t r[uECC_N_WORDS], s[uECC_N_WORDS];
2707af03003cSMatthias Ringwald     r[uECC_N_WORDS - 1] = 0;
2708af03003cSMatthias Ringwald     s[uECC_N_WORDS - 1] = 0;
2709af03003cSMatthias Ringwald 
2710af03003cSMatthias Ringwald     vli_bytesToNative(public.x, public_key);
2711af03003cSMatthias Ringwald     vli_bytesToNative(public.y, public_key + uECC_BYTES);
2712af03003cSMatthias Ringwald     vli_bytesToNative(r, signature);
2713af03003cSMatthias Ringwald     vli_bytesToNative(s, signature + uECC_BYTES);
2714af03003cSMatthias Ringwald 
2715af03003cSMatthias Ringwald     if (vli_isZero(r) || vli_isZero(s)) { /* r, s must not be 0. */
2716af03003cSMatthias Ringwald         return 0;
2717af03003cSMatthias Ringwald     }
2718af03003cSMatthias Ringwald 
2719af03003cSMatthias Ringwald #if (uECC_CURVE != uECC_secp160r1)
2720af03003cSMatthias Ringwald     if (vli_cmp(curve_n, r) != 1 || vli_cmp(curve_n, s) != 1) { /* r, s must be < n. */
2721af03003cSMatthias Ringwald         return 0;
2722af03003cSMatthias Ringwald     }
2723af03003cSMatthias Ringwald #endif
2724af03003cSMatthias Ringwald 
2725af03003cSMatthias Ringwald     /* Calculate u1 and u2. */
2726af03003cSMatthias Ringwald     vli_modInv_n(z, s, curve_n); /* Z = s^-1 */
2727af03003cSMatthias Ringwald     u1[uECC_N_WORDS - 1] = 0;
2728af03003cSMatthias Ringwald     vli_bytesToNative(u1, hash);
2729af03003cSMatthias Ringwald     vli_modMult_n(u1, u1, z); /* u1 = e/s */
2730af03003cSMatthias Ringwald     vli_modMult_n(u2, r, z); /* u2 = r/s */
2731af03003cSMatthias Ringwald 
2732af03003cSMatthias Ringwald     /* Calculate sum = G + Q. */
2733af03003cSMatthias Ringwald     vli_set(sum.x, public.x);
2734af03003cSMatthias Ringwald     vli_set(sum.y, public.y);
2735af03003cSMatthias Ringwald     vli_set(tx, curve_G.x);
2736af03003cSMatthias Ringwald     vli_set(ty, curve_G.y);
2737af03003cSMatthias Ringwald     vli_modSub_fast(z, sum.x, tx); /* Z = x2 - x1 */
2738af03003cSMatthias Ringwald     XYcZ_add(tx, ty, sum.x, sum.y);
2739af03003cSMatthias Ringwald     vli_modInv(z, z, curve_p); /* Z = 1/Z */
2740af03003cSMatthias Ringwald     apply_z(sum.x, sum.y, z);
2741af03003cSMatthias Ringwald 
2742af03003cSMatthias Ringwald     /* Use Shamir's trick to calculate u1*G + u2*Q */
2743af03003cSMatthias Ringwald     points[0] = 0;
2744af03003cSMatthias Ringwald     points[1] = &curve_G;
2745af03003cSMatthias Ringwald     points[2] = &public;
2746af03003cSMatthias Ringwald     points[3] = &sum;
2747af03003cSMatthias Ringwald     numBits = smax(vli_numBits(u1, uECC_N_WORDS), vli_numBits(u2, uECC_N_WORDS));
2748af03003cSMatthias Ringwald 
2749af03003cSMatthias Ringwald     point = points[(!!vli_testBit(u1, numBits - 1)) | ((!!vli_testBit(u2, numBits - 1)) << 1)];
2750af03003cSMatthias Ringwald     vli_set(rx, point->x);
2751af03003cSMatthias Ringwald     vli_set(ry, point->y);
2752af03003cSMatthias Ringwald     vli_clear(z);
2753af03003cSMatthias Ringwald     z[0] = 1;
2754af03003cSMatthias Ringwald 
2755af03003cSMatthias Ringwald     for (i = numBits - 2; i >= 0; --i) {
2756af03003cSMatthias Ringwald         uECC_word_t index;
2757af03003cSMatthias Ringwald         EccPoint_double_jacobian(rx, ry, z);
2758af03003cSMatthias Ringwald 
2759af03003cSMatthias Ringwald         index = (!!vli_testBit(u1, i)) | ((!!vli_testBit(u2, i)) << 1);
2760af03003cSMatthias Ringwald         point = points[index];
2761af03003cSMatthias Ringwald         if (point) {
2762af03003cSMatthias Ringwald             vli_set(tx, point->x);
2763af03003cSMatthias Ringwald             vli_set(ty, point->y);
2764af03003cSMatthias Ringwald             apply_z(tx, ty, z);
2765af03003cSMatthias Ringwald             vli_modSub_fast(tz, rx, tx); /* Z = x2 - x1 */
2766af03003cSMatthias Ringwald             XYcZ_add(tx, ty, rx, ry);
2767af03003cSMatthias Ringwald             vli_modMult_fast(z, z, tz);
2768af03003cSMatthias Ringwald         }
2769af03003cSMatthias Ringwald     }
2770af03003cSMatthias Ringwald 
2771af03003cSMatthias Ringwald     vli_modInv(z, z, curve_p); /* Z = 1/Z */
2772af03003cSMatthias Ringwald     apply_z(rx, ry, z);
2773af03003cSMatthias Ringwald 
2774af03003cSMatthias Ringwald     /* v = x1 (mod n) */
2775af03003cSMatthias Ringwald #if (uECC_CURVE != uECC_secp160r1)
2776af03003cSMatthias Ringwald     if (vli_cmp(curve_n, rx) != 1) {
2777af03003cSMatthias Ringwald         vli_sub(rx, rx, curve_n);
2778af03003cSMatthias Ringwald     }
2779af03003cSMatthias Ringwald #endif
2780af03003cSMatthias Ringwald 
2781af03003cSMatthias Ringwald     /* Accept only if v == r. */
2782af03003cSMatthias Ringwald     return vli_equal(rx, r);
2783af03003cSMatthias Ringwald }
278480dcb211SMatthias Ringwald 
278580dcb211SMatthias Ringwald #endif
2786