1 /********************************************************************************************
2 * Supersingular Isogeny Key Encapsulation Library
3 *
4 * Abstract: ephemeral supersingular isogeny Diffie-Hellman key exchange (SIDH)
5 *********************************************************************************************/
6
7 #include "sike_r1_namespace.h"
8 #include "P503_internal_r1.h"
9 #include "pq-crypto/s2n_pq_random.h"
10 #include "utils/s2n_safety.h"
11
clear_words(void * mem,digit_t nwords)12 static void clear_words(void* mem, digit_t nwords)
13 { // Clear digits from memory. "nwords" indicates the number of digits to be zeroed.
14 // This function uses the volatile type qualifier to inform the compiler not to optimize out the memory clearing.
15 unsigned int i;
16 volatile digit_t *v = mem;
17
18 for (i = 0; i < nwords; i++) {
19 v[i] = 0;
20 }
21 }
22
init_basis(const digit_t * gen,f2elm_t * XP,f2elm_t * XQ,f2elm_t * XR)23 static void init_basis(const digit_t *gen, f2elm_t *XP, f2elm_t *XQ, f2elm_t *XR)
24 { // Initialization of basis points
25
26 fpcopy(gen, XP->e[0]);
27 fpcopy(gen + NWORDS_FIELD, XP->e[1]);
28 fpcopy(gen + 2*NWORDS_FIELD, XQ->e[0]);
29 fpzero(XQ->e[1]);
30 fpcopy(gen + 3*NWORDS_FIELD, XR->e[0]);
31 fpcopy(gen + 4*NWORDS_FIELD, XR->e[1]);
32 }
33
34
fp2_encode(const f2elm_t * x,unsigned char * enc)35 static void fp2_encode(const f2elm_t *x, unsigned char *enc)
36 { // Conversion of GF(p^2) element from Montgomery to standard representation, and encoding by removing leading 0 bytes
37 unsigned int i;
38 f2elm_t t;
39
40 from_fp2mont(x, &t);
41 for (i = 0; i < FP2_ENCODED_BYTES / 2; i++) {
42 enc[i] = ((unsigned char*)t.e)[i];
43 enc[i + FP2_ENCODED_BYTES / 2] = ((unsigned char*)t.e)[i + MAXBITS_FIELD / 8];
44 }
45 }
46
47
fp2_decode(const unsigned char * enc,f2elm_t * x)48 static void fp2_decode(const unsigned char *enc, f2elm_t *x)
49 { // Parse byte sequence back into GF(p^2) element, and conversion to Montgomery representation
50 unsigned int i;
51
52 for (i = 0; i < 2*(MAXBITS_FIELD / 8); i++) ((unsigned char *)x->e)[i] = 0;
53 for (i = 0; i < FP2_ENCODED_BYTES / 2; i++) {
54 ((unsigned char*)x->e)[i] = enc[i];
55 ((unsigned char*)x->e)[i + MAXBITS_FIELD / 8] = enc[i + FP2_ENCODED_BYTES / 2];
56 }
57 to_fp2mont(x, x);
58 }
59
random_mod_order_B(unsigned char * random_digits)60 int random_mod_order_B(unsigned char* random_digits)
61 { // Generation of Bob's secret key
62 // Outputs random value in [0, 2^Floor(Log(2, oB)) - 1]
63 unsigned long long nbytes = NBITS_TO_NBYTES(OBOB_BITS-1);
64
65 clear_words((void*)random_digits, MAXWORDS_ORDER);
66 POSIX_GUARD_RESULT(s2n_get_random_bytes(random_digits, nbytes));
67 random_digits[nbytes-1] &= MASK_BOB; // Masking last byte
68
69 return S2N_SUCCESS;
70 }
71
72
EphemeralKeyGeneration_A(const digit_t * PrivateKeyA,unsigned char * PublicKeyA)73 int EphemeralKeyGeneration_A(const digit_t* PrivateKeyA, unsigned char* PublicKeyA)
74 { // Alice's ephemeral public key generation
75 // Input: a private key PrivateKeyA in the range [0, 2^eA - 1].
76 // Output: the public key PublicKeyA consisting of 3 elements in GF(p^2) which are encoded by removing leading 0 bytes.
77 point_proj_t R, phiP = {0}, phiQ = {0}, phiR = {0}, pts[MAX_INT_POINTS_ALICE];
78 f2elm_t _XPA, _XQA, _XRA, coeff[3], _A24plus = {0}, _C24 = {0}, _A = {0};
79 f2elm_t *XPA=&_XPA, *XQA=&_XQA, *XRA=&_XRA, *A24plus=&_A24plus, *C24=&_C24, *A=&_A;
80 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_ALICE], npts = 0, ii = 0;
81
82
83 // Initialize basis points
84 init_basis((const digit_t*)A_gen, XPA, XQA, XRA);
85 init_basis((const digit_t*)B_gen, &phiP->X, &phiQ->X, &phiR->X);
86 fpcopy((const digit_t*)&Montgomery_one, (phiP->Z.e)[0]);
87 fpcopy((const digit_t*)&Montgomery_one, (phiQ->Z.e)[0]);
88 fpcopy((const digit_t*)&Montgomery_one, (phiR->Z.e)[0]);
89
90 // Initialize constants
91 fpcopy((const digit_t*)&Montgomery_one, A24plus->e[0]);
92 fp2add(A24plus, A24plus, C24);
93
94 // Retrieve kernel point
95 LADDER3PT(XPA, XQA, XRA, PrivateKeyA, ALICE, R, A);
96
97 // Traverse tree
98 index = 0;
99 for (row = 1; row < MAX_Alice; row++) {
100 while (index < MAX_Alice-row) {
101 fp2copy(&R->X, &pts[npts]->X);
102 fp2copy(&R->Z, &pts[npts]->Z);
103 pts_index[npts++] = index;
104 m = strat_Alice[ii++];
105 xDBLe(R, R, A24plus, C24, (int)(2*m));
106 index += m;
107 }
108 get_4_isog(R, A24plus, C24, coeff);
109
110 for (i = 0; i < npts; i++) {
111 eval_4_isog(pts[i], coeff);
112 }
113 eval_4_isog(phiP, coeff);
114 eval_4_isog(phiQ, coeff);
115 eval_4_isog(phiR, coeff);
116
117 fp2copy(&pts[npts-1]->X, &R->X);
118 fp2copy(&pts[npts-1]->Z, &R->Z);
119 index = pts_index[npts-1];
120 npts -= 1;
121 }
122
123 get_4_isog(R, A24plus, C24, coeff);
124 eval_4_isog(phiP, coeff);
125 eval_4_isog(phiQ, coeff);
126 eval_4_isog(phiR, coeff);
127
128 inv_3_way(&phiP->Z, &phiQ->Z, &phiR->Z);
129 fp2mul_mont(&phiP->X, &phiP->Z, &phiP->X);
130 fp2mul_mont(&phiQ->X, &phiQ->Z, &phiQ->X);
131 fp2mul_mont(&phiR->X, &phiR->Z, &phiR->X);
132
133 // Format public key
134 fp2_encode(&phiP->X, PublicKeyA);
135 fp2_encode(&phiQ->X, PublicKeyA + FP2_ENCODED_BYTES);
136 fp2_encode(&phiR->X, PublicKeyA + 2*FP2_ENCODED_BYTES);
137
138 return S2N_SUCCESS;
139 }
140
141
EphemeralKeyGeneration_B(const digit_t * PrivateKeyB,unsigned char * PublicKeyB)142 int EphemeralKeyGeneration_B(const digit_t* PrivateKeyB, unsigned char* PublicKeyB)
143 { // Bob's ephemeral public key generation
144 // Input: a private key PrivateKeyB in the range [0, 2^Floor(Log(2,oB)) - 1].
145 // Output: the public key PublicKeyB consisting of 3 elements in GF(p^2) which are encoded by removing leading 0 bytes.
146 point_proj_t R, phiP = {0}, phiQ = {0}, phiR = {0}, pts[MAX_INT_POINTS_BOB];
147 f2elm_t _XPB, _XQB, _XRB, coeff[3], _A24plus = {0}, _A24minus = {0}, _A = {0};
148 f2elm_t *XPB=&_XPB, *XQB=&_XQB, *XRB=&_XRB, *A24plus=&_A24plus, *A24minus=&_A24minus, *A=&_A;
149 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_BOB], npts = 0, ii = 0;
150
151 // Initialize basis points
152 init_basis((const digit_t*)B_gen, XPB, XQB, XRB);
153 init_basis((const digit_t*)A_gen, &phiP->X, &phiQ->X, &phiR->X);
154 fpcopy((const digit_t*)&Montgomery_one, (phiP->Z.e)[0]);
155 fpcopy((const digit_t*)&Montgomery_one, (phiQ->Z.e)[0]);
156 fpcopy((const digit_t*)&Montgomery_one, (phiR->Z.e)[0]);
157
158 // Initialize constants
159 fpcopy((const digit_t*)&Montgomery_one, A24plus->e[0]);
160 fp2add(A24plus, A24plus, A24plus);
161 fp2copy(A24plus, A24minus);
162 fp2neg(A24minus);
163
164 // Retrieve kernel point
165 LADDER3PT(XPB, XQB, XRB, PrivateKeyB, BOB, R, A);
166
167 // Traverse tree
168 index = 0;
169 for (row = 1; row < MAX_Bob; row++) {
170 while (index < MAX_Bob-row) {
171 fp2copy(&R->X, &pts[npts]->X);
172 fp2copy(&R->Z, &pts[npts]->Z);
173 pts_index[npts++] = index;
174 m = strat_Bob[ii++];
175 xTPLe(R, R, A24minus, A24plus, (int)m);
176 index += m;
177 }
178 get_3_isog(R, A24minus, A24plus, coeff);
179
180 for (i = 0; i < npts; i++) {
181 eval_3_isog(pts[i], coeff);
182 }
183 eval_3_isog(phiP, coeff);
184 eval_3_isog(phiQ, coeff);
185 eval_3_isog(phiR, coeff);
186
187 fp2copy(&pts[npts-1]->X, &R->X);
188 fp2copy(&pts[npts-1]->Z, &R->Z);
189 index = pts_index[npts-1];
190 npts -= 1;
191 }
192
193 get_3_isog(R, A24minus, A24plus, coeff);
194 eval_3_isog(phiP, coeff);
195 eval_3_isog(phiQ, coeff);
196 eval_3_isog(phiR, coeff);
197
198 inv_3_way(&phiP->Z, &phiQ->Z, &phiR->Z);
199 fp2mul_mont(&phiP->X, &phiP->Z, &phiP->X);
200 fp2mul_mont(&phiQ->X, &phiQ->Z, &phiQ->X);
201 fp2mul_mont(&phiR->X, &phiR->Z, &phiR->X);
202
203 // Format public key
204 fp2_encode(&phiP->X, PublicKeyB);
205 fp2_encode(&phiQ->X, PublicKeyB + FP2_ENCODED_BYTES);
206 fp2_encode(&phiR->X, PublicKeyB + 2*FP2_ENCODED_BYTES);
207
208 return S2N_SUCCESS;
209 }
210
211
EphemeralSecretAgreement_A(const digit_t * PrivateKeyA,const unsigned char * PublicKeyB,unsigned char * SharedSecretA)212 int EphemeralSecretAgreement_A(const digit_t* PrivateKeyA, const unsigned char* PublicKeyB, unsigned char* SharedSecretA)
213 { // Alice's ephemeral shared secret computation
214 // It produces a shared secret key SharedSecretA using her secret key PrivateKeyA and Bob's public key PublicKeyB
215 // Inputs: Alice's PrivateKeyA is an integer in the range [0, oA-1].
216 // Bob's PublicKeyB consists of 3 elements in GF(p^2) encoded by removing leading 0 bytes.
217 // Output: a shared secret SharedSecretA that consists of one element in GF(p^2) encoded by removing leading 0 bytes.
218 point_proj_t R, pts[MAX_INT_POINTS_ALICE];
219 f2elm_t coeff[3], PKB[3], _jinv;
220 f2elm_t _A24plus = {0}, _C24 = {0}, _A = {0};
221 f2elm_t *jinv=&_jinv, *A24plus=&_A24plus, *C24=&_C24, *A=&_A;
222 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_ALICE], npts = 0, ii = 0;
223
224 // Initialize images of Bob's basis
225 fp2_decode(PublicKeyB, &PKB[0]);
226 fp2_decode(PublicKeyB + FP2_ENCODED_BYTES, &PKB[1]);
227 fp2_decode(PublicKeyB + 2*FP2_ENCODED_BYTES, &PKB[2]);
228
229 // Initialize constants
230 get_A(&PKB[0], &PKB[1], &PKB[2], A); // TODO: Can return projective A?
231 fpadd((const digit_t*)&Montgomery_one, (const digit_t*)&Montgomery_one, C24->e[0]);
232 fp2add(A, C24, A24plus);
233 fpadd(C24->e[0], C24->e[0], C24->e[0]);
234
235 // Retrieve kernel point
236 LADDER3PT(&PKB[0], &PKB[1], &PKB[2], PrivateKeyA, ALICE, R, A);
237
238 // Traverse tree
239 index = 0;
240 for (row = 1; row < MAX_Alice; row++) {
241 while (index < MAX_Alice-row) {
242 fp2copy(&R->X, &pts[npts]->X);
243 fp2copy(&R->Z, &pts[npts]->Z);
244 pts_index[npts++] = index;
245 m = strat_Alice[ii++];
246 xDBLe(R, R, A24plus, C24, (int)(2*m));
247 index += m;
248 }
249 get_4_isog(R, A24plus, C24, coeff);
250
251 for (i = 0; i < npts; i++) {
252 eval_4_isog(pts[i], coeff);
253 }
254
255 fp2copy(&pts[npts-1]->X, &R->X);
256 fp2copy(&pts[npts-1]->Z, &R->Z);
257 index = pts_index[npts-1];
258 npts -= 1;
259 }
260
261 get_4_isog(R, A24plus, C24, coeff);
262 fp2div2(C24, C24);
263 fp2sub(A24plus, C24, A24plus);
264 fp2div2(C24, C24);
265 j_inv(A24plus, C24, jinv);
266 fp2_encode(jinv, SharedSecretA); // Format shared secret
267
268 return S2N_SUCCESS;
269 }
270
271
EphemeralSecretAgreement_B(const digit_t * PrivateKeyB,const unsigned char * PublicKeyA,unsigned char * SharedSecretB)272 int EphemeralSecretAgreement_B(const digit_t* PrivateKeyB, const unsigned char* PublicKeyA, unsigned char* SharedSecretB)
273 { // Bob's ephemeral shared secret computation
274 // It produces a shared secret key SharedSecretB using his secret key PrivateKeyB and Alice's public key PublicKeyA
275 // Inputs: Bob's PrivateKeyB is an integer in the range [0, 2^Floor(Log(2,oB)) - 1].
276 // Alice's PublicKeyA consists of 3 elements in GF(p^2) encoded by removing leading 0 bytes.
277 // Output: a shared secret SharedSecretB that consists of one element in GF(p^2) encoded by removing leading 0 bytes.
278 point_proj_t R, pts[MAX_INT_POINTS_BOB];
279 f2elm_t coeff[3], PKB[3], _jinv;
280 f2elm_t _A24plus = {0}, _A24minus = {0}, _A = {0};
281 f2elm_t *jinv=&_jinv, *A24plus=&_A24plus, *A24minus=&_A24minus, *A=&_A;
282 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_BOB], npts = 0, ii = 0;
283
284 // Initialize images of Alice's basis
285 fp2_decode(PublicKeyA, &PKB[0]);
286 fp2_decode(PublicKeyA + FP2_ENCODED_BYTES, &PKB[1]);
287 fp2_decode(PublicKeyA + 2*FP2_ENCODED_BYTES, &PKB[2]);
288
289 // Initialize constants
290 get_A(&PKB[0], &PKB[1], &PKB[2], A); // TODO: Can return projective A?
291 fpadd((const digit_t*)&Montgomery_one, (const digit_t*)&Montgomery_one, A24minus->e[0]);
292 fp2add(A, A24minus, A24plus);
293 fp2sub(A, A24minus, A24minus);
294
295 // Retrieve kernel point
296 LADDER3PT(&PKB[0], &PKB[1], &PKB[2], PrivateKeyB, BOB, R, A);
297
298 // Traverse tree
299 index = 0;
300 for (row = 1; row < MAX_Bob; row++) {
301 while (index < MAX_Bob-row) {
302 fp2copy(&R->X, &pts[npts]->X);
303 fp2copy(&R->Z, &pts[npts]->Z);
304 pts_index[npts++] = index;
305 m = strat_Bob[ii++];
306 xTPLe(R, R, A24minus, A24plus, (int)m);
307 index += m;
308 }
309 get_3_isog(R, A24minus, A24plus, coeff);
310
311 for (i = 0; i < npts; i++) {
312 eval_3_isog(pts[i], coeff);
313 }
314
315 fp2copy(&pts[npts-1]->X, &R->X);
316 fp2copy(&pts[npts-1]->Z, &R->Z);
317 index = pts_index[npts-1];
318 npts -= 1;
319 }
320
321 get_3_isog(R, A24minus, A24plus, coeff);
322 fp2add(A24plus, A24minus, A);
323 fp2add(A, A, A);
324 fp2sub(A24plus, A24minus, A24plus);
325 j_inv(A, A24plus, jinv);
326 fp2_encode(jinv, SharedSecretB); // Format shared secret
327
328 return S2N_SUCCESS;
329 }
330