1 /********************************************************************************************
2 * SIDH: an efficient supersingular isogeny cryptography library
3 *
4 * Abstract: ephemeral supersingular isogeny Diffie-Hellman key exchange (SIDH)
5 *********************************************************************************************/
6
7 #include <string.h>
8
init_basis(digit_t * gen,f2elm_t XP,f2elm_t XQ,f2elm_t XR)9 static void init_basis(digit_t *gen, f2elm_t XP, f2elm_t XQ, f2elm_t XR) { // Initialization of basis points
10
11 fpcopy(gen, XP[0]);
12 fpcopy(gen + NWORDS_FIELD, XP[1]);
13 fpcopy(gen + 2 * NWORDS_FIELD, XQ[0]);
14 fpcopy(gen + 3 * NWORDS_FIELD, XQ[1]);
15 fpcopy(gen + 4 * NWORDS_FIELD, XR[0]);
16 fpcopy(gen + 5 * NWORDS_FIELD, XR[1]);
17 }
18
random_mod_order_A(unsigned char * random_digits)19 void random_mod_order_A(unsigned char *random_digits) { // Generation of Alice's secret key
20 // Outputs random value in [0, 2^eA - 1]
21 OQS_randombytes(random_digits, SECRETKEY_A_BYTES);
22 random_digits[SECRETKEY_A_BYTES - 1] &= MASK_ALICE; // Masking last byte
23 }
24
random_mod_order_B(unsigned char * random_digits)25 void random_mod_order_B(unsigned char *random_digits) { // Generation of Bob's secret key
26 // Outputs random value in [0, 2^Floor(Log(2, oB)) - 1]
27 OQS_randombytes(random_digits, SECRETKEY_B_BYTES);
28 random_digits[SECRETKEY_B_BYTES - 1] &= MASK_BOB; // Masking last byte
29 }
30
EphemeralKeyGeneration_A(const unsigned char * PrivateKeyA,unsigned char * PublicKeyA)31 int EphemeralKeyGeneration_A(const unsigned char *PrivateKeyA, unsigned char *PublicKeyA) { // Alice's ephemeral public key generation
32 // Input: a private key PrivateKeyA in the range [0, 2^eA - 1].
33 // Output: the public key PublicKeyA consisting of 3 elements in GF(p^2) which are encoded by removing leading 0 bytes.
34 point_proj_t R, phiP = {0}, phiQ = {0}, phiR = {0}, pts[MAX_INT_POINTS_ALICE];
35 f2elm_t XPA, XQA, XRA, coeff[3], A24plus = {0}, C24 = {0}, A = {0};
36 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_ALICE], npts = 0, ii = 0;
37 digit_t SecretKeyA[NWORDS_ORDER] = {0};
38
39 // Initialize basis points
40 init_basis((digit_t *) A_gen, XPA, XQA, XRA);
41 init_basis((digit_t *) B_gen, phiP->X, phiQ->X, phiR->X);
42 fpcopy((digit_t *) &Montgomery_one, (phiP->Z)[0]);
43 fpcopy((digit_t *) &Montgomery_one, (phiQ->Z)[0]);
44 fpcopy((digit_t *) &Montgomery_one, (phiR->Z)[0]);
45
46 // Initialize constants: A24plus = A+2C, C24 = 4C, where A=6, C=1
47 fpcopy((digit_t *) &Montgomery_one, A24plus[0]);
48 mp2_add(A24plus, A24plus, A24plus);
49 mp2_add(A24plus, A24plus, C24);
50 mp2_add(A24plus, C24, A);
51 mp2_add(C24, C24, A24plus);
52
53 // Retrieve kernel point
54 decode_to_digits(PrivateKeyA, SecretKeyA, SECRETKEY_A_BYTES, NWORDS_ORDER);
55 LADDER3PT(XPA, XQA, XRA, SecretKeyA, ALICE, R, A);
56
57 #if (OALICE_BITS % 2 == 1)
58 point_proj_t S;
59
60 xDBLe(R, S, A24plus, C24, (int) (OALICE_BITS - 1));
61 get_2_isog(S, A24plus, C24);
62 eval_2_isog(phiP, S);
63 eval_2_isog(phiQ, S);
64 eval_2_isog(phiR, S);
65 eval_2_isog(R, S);
66 #endif
67
68 // Traverse tree
69 index = 0;
70 for (row = 1; row < MAX_Alice; row++) {
71 while (index < MAX_Alice - row) {
72 fp2copy(R->X, pts[npts]->X);
73 fp2copy(R->Z, pts[npts]->Z);
74 pts_index[npts++] = index;
75 m = strat_Alice[ii++];
76 xDBLe(R, R, A24plus, C24, (int) (2 * m));
77 index += m;
78 }
79 get_4_isog(R, A24plus, C24, coeff);
80
81 for (i = 0; i < npts; i++) {
82 eval_4_isog(pts[i], coeff);
83 }
84 eval_4_isog(phiP, coeff);
85 eval_4_isog(phiQ, coeff);
86 eval_4_isog(phiR, coeff);
87
88 fp2copy(pts[npts - 1]->X, R->X);
89 fp2copy(pts[npts - 1]->Z, R->Z);
90 index = pts_index[npts - 1];
91 npts -= 1;
92 }
93
94 get_4_isog(R, A24plus, C24, coeff);
95 eval_4_isog(phiP, coeff);
96 eval_4_isog(phiQ, coeff);
97 eval_4_isog(phiR, coeff);
98
99 inv_3_way(phiP->Z, phiQ->Z, phiR->Z);
100 fp2mul_mont(phiP->X, phiP->Z, phiP->X);
101 fp2mul_mont(phiQ->X, phiQ->Z, phiQ->X);
102 fp2mul_mont(phiR->X, phiR->Z, phiR->X);
103
104 // Format public key
105 fp2_encode(phiP->X, PublicKeyA);
106 fp2_encode(phiQ->X, PublicKeyA + FP2_ENCODED_BYTES);
107 fp2_encode(phiR->X, PublicKeyA + 2 * FP2_ENCODED_BYTES);
108
109 return 0;
110 }
111
EphemeralKeyGeneration_B(const unsigned char * PrivateKeyB,unsigned char * PublicKeyB)112 int EphemeralKeyGeneration_B(const unsigned char *PrivateKeyB, unsigned char *PublicKeyB) { // Bob's ephemeral public key generation
113 // Input: a private key PrivateKeyB in the range [0, 2^Floor(Log(2,oB)) - 1].
114 // Output: the public key PublicKeyB consisting of 3 elements in GF(p^2) which are encoded by removing leading 0 bytes.
115 point_proj_t R, phiP = {0}, phiQ = {0}, phiR = {0}, pts[MAX_INT_POINTS_BOB];
116 f2elm_t XPB, XQB, XRB, coeff[3], A24plus = {0}, A24minus = {0}, A = {0};
117 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_BOB], npts = 0, ii = 0;
118 digit_t SecretKeyB[NWORDS_ORDER] = {0};
119
120 // Initialize basis points
121 init_basis((digit_t *) B_gen, XPB, XQB, XRB);
122 init_basis((digit_t *) A_gen, phiP->X, phiQ->X, phiR->X);
123 fpcopy((digit_t *) &Montgomery_one, (phiP->Z)[0]);
124 fpcopy((digit_t *) &Montgomery_one, (phiQ->Z)[0]);
125 fpcopy((digit_t *) &Montgomery_one, (phiR->Z)[0]);
126
127 // Initialize constants: A24minus = A-2C, A24plus = A+2C, where A=6, C=1
128 fpcopy((digit_t *) &Montgomery_one, A24plus[0]);
129 mp2_add(A24plus, A24plus, A24plus);
130 mp2_add(A24plus, A24plus, A24minus);
131 mp2_add(A24plus, A24minus, A);
132 mp2_add(A24minus, A24minus, A24plus);
133
134 // Retrieve kernel point
135 decode_to_digits(PrivateKeyB, SecretKeyB, SECRETKEY_B_BYTES, NWORDS_ORDER);
136 LADDER3PT(XPB, XQB, XRB, SecretKeyB, BOB, R, A);
137
138 // Traverse tree
139 index = 0;
140 for (row = 1; row < MAX_Bob; row++) {
141 while (index < MAX_Bob - row) {
142 fp2copy(R->X, pts[npts]->X);
143 fp2copy(R->Z, pts[npts]->Z);
144 pts_index[npts++] = index;
145 m = strat_Bob[ii++];
146 xTPLe(R, R, A24minus, A24plus, (int) m);
147 index += m;
148 }
149 get_3_isog(R, A24minus, A24plus, coeff);
150
151 for (i = 0; i < npts; i++) {
152 eval_3_isog(pts[i], coeff);
153 }
154 eval_3_isog(phiP, coeff);
155 eval_3_isog(phiQ, coeff);
156 eval_3_isog(phiR, coeff);
157
158 fp2copy(pts[npts - 1]->X, R->X);
159 fp2copy(pts[npts - 1]->Z, R->Z);
160 index = pts_index[npts - 1];
161 npts -= 1;
162 }
163
164 get_3_isog(R, A24minus, A24plus, coeff);
165 eval_3_isog(phiP, coeff);
166 eval_3_isog(phiQ, coeff);
167 eval_3_isog(phiR, coeff);
168
169 inv_3_way(phiP->Z, phiQ->Z, phiR->Z);
170 fp2mul_mont(phiP->X, phiP->Z, phiP->X);
171 fp2mul_mont(phiQ->X, phiQ->Z, phiQ->X);
172 fp2mul_mont(phiR->X, phiR->Z, phiR->X);
173
174 // Format public key
175 fp2_encode(phiP->X, PublicKeyB);
176 fp2_encode(phiQ->X, PublicKeyB + FP2_ENCODED_BYTES);
177 fp2_encode(phiR->X, PublicKeyB + 2 * FP2_ENCODED_BYTES);
178
179 return 0;
180 }
181
EphemeralSecretAgreement_A(const unsigned char * PrivateKeyA,const unsigned char * PublicKeyB,unsigned char * SharedSecretA)182 int EphemeralSecretAgreement_A(const unsigned char *PrivateKeyA, const unsigned char *PublicKeyB, unsigned char *SharedSecretA) { // Alice's ephemeral shared secret computation
183 // It produces a shared secret key SharedSecretA using her secret key PrivateKeyA and Bob's public key PublicKeyB
184 // Inputs: Alice's PrivateKeyA is an integer in the range [0, oA-1].
185 // Bob's PublicKeyB consists of 3 elements in GF(p^2) encoded by removing leading 0 bytes.
186 // Output: a shared secret SharedSecretA that consists of one element in GF(p^2) encoded by removing leading 0 bytes.
187 point_proj_t R, pts[MAX_INT_POINTS_ALICE];
188 f2elm_t coeff[3], PKB[3], jinv;
189 f2elm_t A24plus = {0}, C24 = {0}, A = {0};
190 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_ALICE], npts = 0, ii = 0;
191 digit_t SecretKeyA[NWORDS_ORDER] = {0};
192
193 // Initialize images of Bob's basis
194 fp2_decode(PublicKeyB, PKB[0]);
195 fp2_decode(PublicKeyB + FP2_ENCODED_BYTES, PKB[1]);
196 fp2_decode(PublicKeyB + 2 * FP2_ENCODED_BYTES, PKB[2]);
197
198 // Initialize constants: A24plus = A+2C, C24 = 4C, where C=1
199 get_A(PKB[0], PKB[1], PKB[2], A);
200 mp_add((digit_t*)&Montgomery_one, (digit_t*)&Montgomery_one, C24[0], NWORDS_FIELD);
201 mp2_add(A, C24, A24plus);
202 mp_add(C24[0], C24[0], C24[0], NWORDS_FIELD);
203
204 // Retrieve kernel point
205 decode_to_digits(PrivateKeyA, SecretKeyA, SECRETKEY_A_BYTES, NWORDS_ORDER);
206 LADDER3PT(PKB[0], PKB[1], PKB[2], SecretKeyA, ALICE, R, A);
207
208 #if (OALICE_BITS % 2 == 1)
209 point_proj_t S;
210
211 xDBLe(R, S, A24plus, C24, (int) (OALICE_BITS - 1));
212 get_2_isog(S, A24plus, C24);
213 eval_2_isog(R, S);
214 #endif
215
216 // Traverse tree
217 index = 0;
218 for (row = 1; row < MAX_Alice; row++) {
219 while (index < MAX_Alice - row) {
220 fp2copy(R->X, pts[npts]->X);
221 fp2copy(R->Z, pts[npts]->Z);
222 pts_index[npts++] = index;
223 m = strat_Alice[ii++];
224 xDBLe(R, R, A24plus, C24, (int) (2 * m));
225 index += m;
226 }
227 get_4_isog(R, A24plus, C24, coeff);
228
229 for (i = 0; i < npts; i++) {
230 eval_4_isog(pts[i], coeff);
231 }
232
233 fp2copy(pts[npts - 1]->X, R->X);
234 fp2copy(pts[npts - 1]->Z, R->Z);
235 index = pts_index[npts - 1];
236 npts -= 1;
237 }
238
239 get_4_isog(R, A24plus, C24, coeff);
240 mp2_add(A24plus, A24plus, A24plus);
241 fp2sub(A24plus, C24, A24plus);
242 fp2add(A24plus, A24plus, A24plus);
243 j_inv(A24plus, C24, jinv);
244 fp2_encode(jinv, SharedSecretA); // Format shared secret
245
246 return 0;
247 }
248
EphemeralSecretAgreement_B(const unsigned char * PrivateKeyB,const unsigned char * PublicKeyA,unsigned char * SharedSecretB)249 int EphemeralSecretAgreement_B(const unsigned char *PrivateKeyB, const unsigned char *PublicKeyA, unsigned char *SharedSecretB) { // Bob's ephemeral shared secret computation
250 // It produces a shared secret key SharedSecretB using his secret key PrivateKeyB and Alice's public key PublicKeyA
251 // Inputs: Bob's PrivateKeyB is an integer in the range [0, 2^Floor(Log(2,oB)) - 1].
252 // Alice's PublicKeyA consists of 3 elements in GF(p^2) encoded by removing leading 0 bytes.
253 // Output: a shared secret SharedSecretB that consists of one element in GF(p^2) encoded by removing leading 0 bytes.
254 point_proj_t R, pts[MAX_INT_POINTS_BOB];
255 f2elm_t coeff[3], PKB[3], jinv;
256 f2elm_t A24plus = {0}, A24minus = {0}, A = {0};
257 unsigned int i, row, m, index = 0, pts_index[MAX_INT_POINTS_BOB], npts = 0, ii = 0;
258 digit_t SecretKeyB[NWORDS_ORDER] = {0};
259
260 // Initialize images of Alice's basis
261 fp2_decode(PublicKeyA, PKB[0]);
262 fp2_decode(PublicKeyA + FP2_ENCODED_BYTES, PKB[1]);
263 fp2_decode(PublicKeyA + 2 * FP2_ENCODED_BYTES, PKB[2]);
264
265 // Initialize constants: A24plus = A+2C, A24minus = A-2C, where C=1
266 get_A(PKB[0], PKB[1], PKB[2], A);
267 mp_add((digit_t*)&Montgomery_one, (digit_t*)&Montgomery_one, A24minus[0], NWORDS_FIELD);
268 mp2_add(A, A24minus, A24plus);
269 mp2_sub_p2(A, A24minus, A24minus);
270
271 // Retrieve kernel point
272 decode_to_digits(PrivateKeyB, SecretKeyB, SECRETKEY_B_BYTES, NWORDS_ORDER);
273 LADDER3PT(PKB[0], PKB[1], PKB[2], SecretKeyB, BOB, R, A);
274
275 // Traverse tree
276 index = 0;
277 for (row = 1; row < MAX_Bob; row++) {
278 while (index < MAX_Bob - row) {
279 fp2copy(R->X, pts[npts]->X);
280 fp2copy(R->Z, pts[npts]->Z);
281 pts_index[npts++] = index;
282 m = strat_Bob[ii++];
283 xTPLe(R, R, A24minus, A24plus, (int) m);
284 index += m;
285 }
286 get_3_isog(R, A24minus, A24plus, coeff);
287
288 for (i = 0; i < npts; i++) {
289 eval_3_isog(pts[i], coeff);
290 }
291
292 fp2copy(pts[npts - 1]->X, R->X);
293 fp2copy(pts[npts - 1]->Z, R->Z);
294 index = pts_index[npts - 1];
295 npts -= 1;
296 }
297
298 get_3_isog(R, A24minus, A24plus, coeff);
299 fp2add(A24plus, A24minus, A);
300 fp2add(A, A, A);
301 fp2sub(A24plus, A24minus, A24plus);
302 j_inv(A, A24plus, jinv);
303 fp2_encode(jinv, SharedSecretB); // Format shared secret
304
305 return 0;
306 }
307