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