1 /* ecc-secp224r1.c
2
3 Compile time constant (but machine dependent) tables.
4
5 Copyright (C) 2013, 2014 Niels Möller
6
7 This file is part of GNU Nettle.
8
9 GNU Nettle is free software: you can redistribute it and/or
10 modify it under the terms of either:
11
12 * the GNU Lesser General Public License as published by the Free
13 Software Foundation; either version 3 of the License, or (at your
14 option) any later version.
15
16 or
17
18 * the GNU General Public License as published by the Free
19 Software Foundation; either version 2 of the License, or (at your
20 option) any later version.
21
22 or both in parallel, as here.
23
24 GNU Nettle is distributed in the hope that it will be useful,
25 but WITHOUT ANY WARRANTY; without even the implied warranty of
26 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 General Public License for more details.
28
29 You should have received copies of the GNU General Public License and
30 the GNU Lesser General Public License along with this program. If
31 not, see http://www.gnu.org/licenses/.
32 */
33
34 /* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
35
36 #if HAVE_CONFIG_H
37 # include "config.h"
38 #endif
39
40 #include "ecc.h"
41 #include "ecc-internal.h"
42
43 #if HAVE_NATIVE_ecc_secp224r1_modp
44
45 #define USE_REDC 0
46 #define ecc_secp224r1_modp _nettle_ecc_secp224r1_modp
47 void
48 ecc_secp224r1_modp (const struct ecc_modulo *m, mp_limb_t *rp, mp_limb_t *xp);
49
50 #else
51 #define USE_REDC (ECC_REDC_SIZE != 0)
52 #define ecc_secp224r1_modp ecc_mod
53 #endif
54
55 #include "ecc-secp224r1.h"
56
57 #if ECC_REDC_SIZE < 0
58 # define ecc_secp224r1_redc ecc_pm1_redc
59 #elif ECC_REDC_SIZE == 0
60 # define ecc_secp224r1_redc NULL
61 #else
62 # error Configuration error
63 #endif
64
65 #define ECC_SECP224R1_INV_ITCH (4*ECC_LIMB_SIZE)
66
67 static void
ecc_secp224r1_inv(const struct ecc_modulo * p,mp_limb_t * rp,const mp_limb_t * ap,mp_limb_t * scratch)68 ecc_secp224r1_inv (const struct ecc_modulo *p,
69 mp_limb_t *rp, const mp_limb_t *ap,
70 mp_limb_t *scratch)
71 {
72 #define a7 scratch
73 #define t0 (scratch + 1*ECC_LIMB_SIZE)
74 #define a31m1 t0
75 #define a96m1 a7
76 #define tp (scratch + 2*ECC_LIMB_SIZE)
77
78 /* Addition chain for p - 2 = 2^{224} - 2^{96} - 1
79
80 7 = 1 + 2 (2+1) 2 S + 2 M
81 2^{31} - 1 = 1 + 2 (2^{15} + 1)(1 + 2 (2^7 + 1) (1 + 2 (2^3+1) * 7))
82 28 S + 6 M
83 2^{34} - 1 = 2^3 (2^{31} - 1) + 7 3 S + M
84 2^{65} - 1 = 2^{31}(2^{34} - 1) + 2^{31} - 1 31 S + M
85 2^{96} - 1 = 2^{31}(2^{65} - 1) + 2^{31} - 1 31 S + M
86 2^{127} - 1 = 2^{31}(2^{96} - 1) + 2^{31} - 1 31 S + M
87
88 2^{224} - 2^{96} - 1 97 S + M
89 = 2^{97}(2^{127} - 1) + 2^{96} - 1
90
91 This addition chain needs 223 squarings and 13 multiplies.
92 */
93 ecc_mod_sqr (p, rp, ap, tp); /* a^2 */
94 ecc_mod_mul (p, rp, rp, ap, tp); /* a^3 */
95 ecc_mod_sqr (p, rp, rp, tp); /* a^6 */
96 ecc_mod_mul (p, a7, rp, ap, tp); /* a^{2^3-1} a7 */
97
98 ecc_mod_pow_2kp1 (p, rp, a7, 3, tp); /* a^{2^6 - 1} */
99 ecc_mod_sqr (p, rp, rp, tp); /* a^{2^7 - 2} */
100 ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^7 - 1} */
101 ecc_mod_pow_2kp1 (p, t0, rp, 7, tp); /* a^{2^14 - 1} */
102 ecc_mod_sqr (p, rp, t0, tp); /* a^{2^15 - 2} */
103 ecc_mod_mul (p, rp, rp, ap, tp); /* a^{2^15 - 1} */
104 ecc_mod_pow_2kp1 (p, t0, rp, 15, tp); /* a^{2^30 - 1} */
105 ecc_mod_sqr (p, rp, t0, tp); /* a^{2^31 - 2} */
106 ecc_mod_mul (p, a31m1, rp, ap, tp); /* a^{2^31 - 1} a7, a31m1 */
107
108 ecc_mod_pow_2k_mul (p, rp, a31m1, 3, a7, tp); /* a^{2^34 - 1} a31m1 */
109 ecc_mod_pow_2k_mul (p, rp, rp, 31, a31m1, tp); /* a^{2^65 - 1} a31m1 */
110 ecc_mod_pow_2k_mul (p, a96m1, rp, 31, a31m1, tp); /* a^{2^96 - 1} a31m1, a96m1 */
111 ecc_mod_pow_2k_mul (p, rp, a96m1, 31, a31m1, tp); /* a^{2^{127} - 1} a96m1 */
112 ecc_mod_pow_2k_mul (p, rp, rp, 97, a96m1, tp); /* a^{2^{224} - 2^{96} - 1 */
113 }
114
115
116 const struct ecc_curve _nettle_secp_224r1 =
117 {
118 {
119 224,
120 ECC_LIMB_SIZE,
121 ECC_BMODP_SIZE,
122 -ECC_REDC_SIZE,
123 ECC_SECP224R1_INV_ITCH,
124 0,
125
126 ecc_p,
127 ecc_Bmodp,
128 ecc_Bmodp_shifted,
129 ecc_redc_ppm1,
130 ecc_pp1h,
131
132 ecc_secp224r1_modp,
133 USE_REDC ? ecc_secp224r1_redc : ecc_secp224r1_modp,
134 ecc_secp224r1_inv,
135 NULL,
136 },
137 {
138 224,
139 ECC_LIMB_SIZE,
140 ECC_BMODQ_SIZE,
141 0,
142 ECC_MOD_INV_ITCH (ECC_LIMB_SIZE),
143 0,
144
145 ecc_q,
146 ecc_Bmodq,
147 ecc_Bmodq_shifted,
148 NULL,
149 ecc_qp1h,
150
151 ecc_mod,
152 ecc_mod,
153 ecc_mod_inv,
154 NULL,
155 },
156
157 USE_REDC,
158 ECC_PIPPENGER_K,
159 ECC_PIPPENGER_C,
160
161 ECC_ADD_JJA_ITCH (ECC_LIMB_SIZE),
162 ECC_ADD_JJJ_ITCH (ECC_LIMB_SIZE),
163 ECC_DUP_JJ_ITCH (ECC_LIMB_SIZE),
164 ECC_MUL_A_ITCH (ECC_LIMB_SIZE),
165 ECC_MUL_G_ITCH (ECC_LIMB_SIZE),
166 ECC_J_TO_A_ITCH(ECC_LIMB_SIZE, ECC_SECP224R1_INV_ITCH),
167
168 ecc_add_jja,
169 ecc_add_jjj,
170 ecc_dup_jj,
171 ecc_mul_a,
172 ecc_mul_g,
173 ecc_j_to_a,
174
175 ecc_b,
176 ecc_unit,
177 ecc_table
178 };
179
nettle_get_secp_224r1(void)180 const struct ecc_curve *nettle_get_secp_224r1(void)
181 {
182 return &_nettle_secp_224r1;
183 }
184