]>
Commit | Line | Data |
---|---|---|
abfaf8be | 1 | /* ecc-secp192r1.c |
90112edb NM |
2 | |
3 | Compile time constant (but machine dependent) tables. | |
4 | ||
35f12552 NM |
5 | Copyright (C) 2013, 2014, 2019, 2021 Niels Möller |
6 | Copyright (C) 2019 Wim Lewis | |
90112edb NM |
7 | |
8 | This file is part of GNU Nettle. | |
9 | ||
10 | GNU Nettle is free software: you can redistribute it and/or | |
11 | modify it under the terms of either: | |
12 | ||
13 | * the GNU Lesser General Public License as published by the Free | |
14 | Software Foundation; either version 3 of the License, or (at your | |
15 | option) any later version. | |
16 | ||
17 | or | |
18 | ||
19 | * the GNU General Public License as published by the Free | |
20 | Software Foundation; either version 2 of the License, or (at your | |
21 | option) any later version. | |
22 | ||
23 | or both in parallel, as here. | |
24 | ||
25 | GNU Nettle is distributed in the hope that it will be useful, | |
26 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
27 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
28 | General Public License for more details. | |
29 | ||
30 | You should have received copies of the GNU General Public License and | |
31 | the GNU Lesser General Public License along with this program. If | |
32 | not, see http://www.gnu.org/licenses/. | |
33 | */ | |
9422a551 | 34 | |
f1812845 | 35 | /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */ |
9422a551 NM |
36 | |
37 | #if HAVE_CONFIG_H | |
38 | # include "config.h" | |
39 | #endif | |
40 | ||
41 | #include <assert.h> | |
42 | ||
43 | #include "ecc-internal.h" | |
44 | ||
45 | #define USE_REDC 0 | |
46 | ||
abfaf8be | 47 | #include "ecc-secp192r1.h" |
9422a551 | 48 | |
0a5e2524 | 49 | #if HAVE_NATIVE_ecc_secp192r1_modp |
a3888205 | 50 | |
0a5e2524 | 51 | #define ecc_secp192r1_modp _nettle_ecc_secp192r1_modp |
a3888205 | 52 | void |
f4f5625e | 53 | ecc_secp192r1_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp); |
a3888205 | 54 | |
9422a551 NM |
55 | /* Use that p = 2^{192} - 2^64 - 1, to eliminate 128 bits at a time. */ |
56 | ||
a3888205 | 57 | #elif GMP_NUMB_BITS == 32 |
9422a551 NM |
58 | /* p is 6 limbs, p = B^6 - B^2 - 1 */ |
59 | static void | |
f4f5625e | 60 | ecc_secp192r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp, mp_limb_t *xp) |
9422a551 NM |
61 | { |
62 | mp_limb_t cy; | |
63 | ||
64 | /* Reduce from 12 to 9 limbs (top limb small)*/ | |
f4f5625e NM |
65 | cy = mpn_add_n (xp + 2, xp + 2, xp + 8, 4); |
66 | cy = sec_add_1 (xp + 6, xp + 6, 2, cy); | |
67 | cy += mpn_add_n (xp + 4, xp + 4, xp + 8, 4); | |
9422a551 NM |
68 | assert (cy <= 2); |
69 | ||
f4f5625e | 70 | xp[8] = cy; |
9422a551 NM |
71 | |
72 | /* Reduce from 9 to 6 limbs */ | |
f4f5625e NM |
73 | cy = mpn_add_n (xp, xp, xp + 6, 3); |
74 | cy = sec_add_1 (xp + 3, xp + 3, 2, cy); | |
75 | cy += mpn_add_n (xp + 2, xp + 2, xp + 6, 3); | |
76 | cy = sec_add_1 (xp + 5, xp + 5, 1, cy); | |
9422a551 NM |
77 | |
78 | assert (cy <= 1); | |
f4f5625e | 79 | cy = mpn_cnd_add_n (cy, rp, xp, ecc_Bmodp, 6); |
9422a551 NM |
80 | assert (cy == 0); |
81 | } | |
82 | #elif GMP_NUMB_BITS == 64 | |
83 | /* p is 3 limbs, p = B^3 - B - 1 */ | |
84 | static void | |
f4f5625e | 85 | ecc_secp192r1_modp (const struct ecc_modulo *m UNUSED, mp_limb_t *rp, mp_limb_t *xp) |
9422a551 NM |
86 | { |
87 | mp_limb_t cy; | |
88 | ||
89 | /* Reduce from 6 to 5 limbs (top limb small)*/ | |
f4f5625e NM |
90 | cy = mpn_add_n (xp + 1, xp + 1, xp + 4, 2); |
91 | cy = sec_add_1 (xp + 3, xp + 3, 1, cy); | |
92 | cy += mpn_add_n (xp + 2, xp + 2, xp + 4, 2); | |
cf8a68ef | 93 | assert_maybe (cy <= 2); |
9422a551 | 94 | |
f4f5625e | 95 | xp[4] = cy; |
9422a551 NM |
96 | |
97 | /* Reduce from 5 to 4 limbs (high limb small) */ | |
f4f5625e NM |
98 | cy = mpn_add_n (xp, xp, xp + 3, 2); |
99 | cy = sec_add_1 (xp + 2, xp + 2, 1, cy); | |
100 | cy += mpn_add_n (xp + 1, xp + 1, xp + 3, 2); | |
9422a551 | 101 | |
cf8a68ef | 102 | assert_maybe (cy <= 1); |
f4f5625e | 103 | cy = mpn_cnd_add_n (cy, rp, xp, ecc_Bmodp, 3); |
cf8a68ef | 104 | assert_maybe (cy == 0); |
9422a551 NM |
105 | } |
106 | ||
107 | #else | |
0a5e2524 | 108 | #define ecc_secp192r1_modp ecc_mod |
9422a551 NM |
109 | #endif |
110 | ||
6f85f4fe NM |
111 | #define ECC_SECP192R1_INV_ITCH (4*ECC_LIMB_SIZE) |
112 | ||
113 | static void | |
114 | ecc_secp192r1_inv (const struct ecc_modulo *p, | |
115 | mp_limb_t *rp, const mp_limb_t *ap, | |
116 | mp_limb_t *scratch) | |
117 | { | |
118 | #define a62m1 scratch | |
119 | #define t0 (scratch + ECC_LIMB_SIZE) | |
120 | #define tp (scratch + 2*ECC_LIMB_SIZE) | |
121 | ||
122 | /* Addition chain | |
123 | ||
124 | p - 2 = 2^{192} - 2^{64} - 3 | |
125 | = 1 + 2^{192} - 2^{64} - 4 | |
126 | = 1 + 2^2 (2^{190} - 2^{62} - 1) | |
127 | = 1 + 2^2 (2^{62} - 1 + 2^{190} - 2^63) | |
128 | = 1 + 2^2 (2^{62} - 1 + 2^{63}(2^{127} - 1)) | |
129 | = 1 + 2^2 (2^{62} - 1 + 2^{63}(1 + 2 (2^{126} - 1))) | |
130 | = 1 + 2^2 (2^{62} - 1 + 2^{63}(1 + 2 (2^{63} + 1)(2^{63} - 1))) | |
131 | = 1 + 2^2 (2^{62} - 1 + 2^{63}(1 + 2 (2^{63} + 1)(1 + 2(2^{62} - 1)))) | |
132 | ||
133 | 2^{62} - 1 = (2^{31}+1)(2^{31}-1) | |
134 | = (2^{31}+1)(1 + 2(2^{30} - 1)) | |
135 | = (2^{31}+1)(1 + 2(2^{15}+1)(2^15-1)) | |
136 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^{14}-1)))) | |
137 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(2^7-1)))) | |
138 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(2^3-1))))) | |
139 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(1 + 2 (2+1)))))) | |
140 | ||
141 | This addition chain needs 191 squarings and 14 multiplies. | |
142 | ||
143 | Could be improved sligthly as: | |
144 | ||
145 | a^7 = 1 + 2 * (2 + 1) | |
146 | 2^{62} - 1 = (2^{31}+1)(2^{31}-1) | |
147 | = (2^{31}+1)(1 + 2(2^{30} - 1)) | |
148 | = (2^{31}+1)(1 + 2(2^{15}+1)(2^15-1)) | |
149 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^{14}-1)))) | |
150 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(2^7-1)))) | |
151 | = (2^{31}+1)(1 + 2(2^{15}+1)(1 + 2(1 + (2^7+1)(1+2(2^3+1)(2^3-1))))) | |
152 | 2^{65} - 1 = 2^3 (2^{62} - 1) + 2^3 - 1 | |
153 | 2^{127} - 1 = 2^{62} (2^{65} - 1) + 2^{62} - 1 | |
154 | p - 2 = 1 + 2^2 (2^{62} - 1 + 2^{63}(2^{127} - 1)) | |
155 | ||
156 | This needs 191 squarings and 13 multiplies, i.e., saving one | |
157 | multiply, at the cost of additional temporary storage for a^7. | |
158 | */ | |
159 | ||
160 | ecc_mod_sqr (p, rp, ap, tp); /* a^2 */ | |
161 | ecc_mod_mul (p, rp, rp, ap, tp); /* a^3 */ | |
162 | ecc_mod_sqr (p, rp, rp, tp); /* a^6 */ | |
163 | ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^3-1} */ | |
164 | ecc_mod_pow_2kp1 (p, t0, rp, 3, tp); /* a^{2^6-1} */ | |
165 | ecc_mod_sqr (p, rp, t0, tp); /* a^{2^7-2} */ | |
166 | ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^7-1} */ | |
167 | ecc_mod_pow_2kp1 (p, t0, rp, 7, tp); /* a^{2^14-1} */ | |
168 | ecc_mod_sqr (p, rp, t0, tp); /* a^{2^15-2} */ | |
169 | ecc_mod_mul (p, rp, ap, rp, tp); /* a^{2^15-1} */ | |
170 | ecc_mod_pow_2kp1 (p, t0, rp, 15, tp); /* a^{2^30-1} */ | |
171 | ecc_mod_sqr (p, rp, t0, tp); /* a^{2^31-2} */ | |
172 | ecc_mod_mul (p, rp, ap, rp, tp); /* a^{2^31-1} */ | |
173 | ecc_mod_pow_2kp1 (p, a62m1, rp, 31, tp); /* a^{2^62-1} Overlaps t0 */ | |
174 | ||
175 | ecc_mod_sqr (p, rp, a62m1, tp); /* a^{2^63-2} */ | |
176 | ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^63-1} */ | |
177 | ecc_mod_pow_2kp1 (p, t0, rp, 63, tp); /* a^{2^126-1} */ | |
178 | ecc_mod_sqr (p, rp, t0, tp); /* a^{2^127-2} */ | |
179 | ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^127-1} Clobbers t1 */ | |
180 | ecc_mod_pow_2k_mul (p, rp, rp, 63, a62m1, tp); /* a^{2^190 - 2^62 - 1} */ | |
181 | ecc_mod_sqr (p, rp, rp, tp); /* a^{2^191 - 2^63 - 2} */ | |
182 | ecc_mod_sqr (p, rp, rp, tp); /* a^{2^192 - 2^64 - 4} */ | |
183 | ecc_mod_mul (p, rp, rp, ap, tp); | |
35f12552 NM |
184 | |
185 | #undef a62m1 | |
186 | #undef t0 | |
187 | #undef tp | |
188 | } | |
189 | ||
190 | /* To guarantee that inputs to ecc_mod_zero_p are in the required range. */ | |
191 | #if ECC_LIMB_SIZE * GMP_NUMB_BITS != 192 | |
192 | #error Unsupported limb size | |
193 | #endif | |
194 | ||
195 | #define ECC_SECP192R1_SQRT_ITCH (3*ECC_LIMB_SIZE) | |
196 | ||
197 | static int | |
198 | ecc_secp192r1_sqrt (const struct ecc_modulo *p, | |
199 | mp_limb_t *rp, | |
200 | const mp_limb_t *cp, | |
201 | mp_limb_t *scratch) | |
202 | { | |
203 | /* This computes the square root modulo p192 using the identity: | |
204 | ||
205 | sqrt(c) = c^(2^190 - 2^62) (mod P-192) | |
206 | ||
207 | which can be seen as a special case of Tonelli-Shanks with e=1. | |
208 | */ | |
209 | ||
210 | /* We need one t0 (and use clobbering rp) and scratch space for mul and sqr. */ | |
211 | ||
212 | #define t0 scratch | |
213 | #define tp (scratch + ECC_LIMB_SIZE) | |
214 | ||
215 | ecc_mod_sqr(p, rp, cp, tp); /* c^2 */ | |
216 | ecc_mod_mul(p, rp, rp, cp, tp); /* c^3 */ | |
217 | ecc_mod_pow_2kp1(p, t0, rp, 2, tp); /* c^(2^4 - 1) */ | |
218 | ecc_mod_pow_2kp1(p, rp, t0, 4, tp); /* c^(2^8 - 1) */ | |
219 | ecc_mod_pow_2kp1(p, t0, rp, 8, tp); /* c^(2^16 - 1) */ | |
220 | ecc_mod_pow_2kp1(p, rp, t0, 16, tp); /* c^(2^32 - 1) */ | |
221 | ecc_mod_pow_2kp1(p, t0, rp, 32, tp); /* c^(2^64 - 1) */ | |
222 | ecc_mod_pow_2kp1(p, rp, t0, 64, tp); /* c^(2^128 - 1) */ | |
223 | ||
224 | ecc_mod_pow_2k (p, rp, rp, 62, tp); /* c^(2^190 - 2^62) */ | |
225 | ||
226 | /* Check that input was a square, R^2 = C, for non-squares we'd get | |
227 | R^2 = -C. */ | |
228 | ecc_mod_sqr(p, t0, rp, tp); | |
229 | ecc_mod_sub(p, t0, t0, cp); | |
230 | ||
231 | return ecc_mod_zero_p (p, t0); | |
232 | ||
233 | #undef t0 | |
234 | #undef tp | |
6f85f4fe NM |
235 | } |
236 | ||
8bf4747d | 237 | const struct ecc_curve _nettle_secp_192r1 = |
9422a551 | 238 | { |
a78c9459 NM |
239 | { |
240 | 192, | |
241 | ECC_LIMB_SIZE, | |
242 | ECC_BMODP_SIZE, | |
243 | ECC_REDC_SIZE, | |
6f85f4fe | 244 | ECC_SECP192R1_INV_ITCH, |
35f12552 | 245 | ECC_SECP192R1_SQRT_ITCH, |
c510cfa4 | 246 | 0, |
8b6cd994 | 247 | |
a78c9459 NM |
248 | ecc_p, |
249 | ecc_Bmodp, | |
62c74f1f NM |
250 | ecc_Bmodp_shifted, |
251 | ecc_Bm2p, | |
a78c9459 | 252 | ecc_redc_ppm1, |
b524402c NM |
253 | ecc_pp1h, |
254 | ||
0a5e2524 DES |
255 | ecc_secp192r1_modp, |
256 | ecc_secp192r1_modp, | |
6f85f4fe | 257 | ecc_secp192r1_inv, |
35f12552 | 258 | ecc_secp192r1_sqrt, |
c510cfa4 | 259 | NULL, |
a78c9459 NM |
260 | }, |
261 | { | |
262 | 192, | |
263 | ECC_LIMB_SIZE, | |
264 | ECC_BMODQ_SIZE, | |
265 | 0, | |
8b6cd994 | 266 | ECC_MOD_INV_ITCH (ECC_LIMB_SIZE), |
c510cfa4 | 267 | 0, |
35f12552 | 268 | 0, |
8b6cd994 | 269 | |
a78c9459 NM |
270 | ecc_q, |
271 | ecc_Bmodq, | |
272 | ecc_Bmodq_shifted, | |
62c74f1f | 273 | ecc_Bm2q, |
a78c9459 | 274 | NULL, |
b524402c NM |
275 | ecc_qp1h, |
276 | ||
56079909 NM |
277 | ecc_mod, |
278 | ecc_mod, | |
b524402c | 279 | ecc_mod_inv, |
c510cfa4 | 280 | NULL, |
35f12552 | 281 | NULL, |
a78c9459 NM |
282 | }, |
283 | ||
9422a551 | 284 | USE_REDC, |
9422a551 NM |
285 | ECC_PIPPENGER_K, |
286 | ECC_PIPPENGER_C, | |
b9f98cb7 | 287 | |
9ae25aaa | 288 | ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE), |
79a4cff0 | 289 | ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE), |
9ae25aaa | 290 | ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE), |
a45118aa NM |
291 | ECC_MUL_A_ITCH (ECC_LIMB_SIZE), |
292 | ECC_MUL_G_ITCH (ECC_LIMB_SIZE), | |
d7a433dc | 293 | ECC_J_TO_A_ITCH(ECC_LIMB_SIZE, ECC_SECP192R1_INV_ITCH), |
a45118aa | 294 | |
9ae25aaa | 295 | ecc_add_jja, |
79a4cff0 | 296 | ecc_add_jjj, |
9ae25aaa | 297 | ecc_dup_jj, |
a45118aa NM |
298 | ecc_mul_a, |
299 | ecc_mul_g, | |
300 | ecc_j_to_a, | |
301 | ||
9422a551 | 302 | ecc_b, |
9422a551 | 303 | ecc_unit, |
9422a551 NM |
304 | ecc_table |
305 | }; | |
306 | ||
b84dff15 NM |
307 | const struct ecc_curve *nettle_get_secp_192r1(void) |
308 | { | |
8bf4747d | 309 | return &_nettle_secp_192r1; |
b84dff15 | 310 | } |