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] = ∑
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