OLD | NEW |
1 /* This Source Code Form is subject to the terms of the Mozilla Public | 1 /* This Source Code Form is subject to the terms of the Mozilla Public |
2 * License, v. 2.0. If a copy of the MPL was not distributed with this | 2 * License, v. 2.0. If a copy of the MPL was not distributed with this |
3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ |
4 | 4 |
5 #include "ec2.h" | 5 #include "ec2.h" |
6 #include "mp_gf2m.h" | 6 #include "mp_gf2m.h" |
7 #include "mp_gf2m-priv.h" | 7 #include "mp_gf2m-priv.h" |
8 #include "mpi.h" | 8 #include "mpi.h" |
9 #include "mpi-priv.h" | 9 #include "mpi-priv.h" |
10 #include <stdlib.h> | 10 #include <stdlib.h> |
11 | 11 |
12 /* Fast reduction for polynomials over a 233-bit curve. Assumes reduction | 12 /* Fast reduction for polynomials over a 233-bit curve. Assumes reduction |
13 * polynomial with terms {233, 74, 0}. */ | 13 * polynomial with terms {233, 74, 0}. */ |
14 mp_err | 14 mp_err ec_GF2m_233_mod(const mp_int *a, mp_int *r, const GFMethod *meth) { |
15 ec_GF2m_233_mod(const mp_int *a, mp_int *r, const GFMethod *meth) | 15 mp_err res = MP_OKAY; |
16 { | 16 mp_digit *u, z; |
17 » mp_err res = MP_OKAY; | 17 |
18 » mp_digit *u, z; | 18 if (a != r) { |
19 | 19 MP_CHECKOK(mp_copy(a, r)); |
20 » if (a != r) { | 20 } |
21 » » MP_CHECKOK(mp_copy(a, r)); | |
22 » } | |
23 #ifdef ECL_SIXTY_FOUR_BIT | 21 #ifdef ECL_SIXTY_FOUR_BIT |
24 » if (MP_USED(r) < 8) { | 22 if (MP_USED(r) < 8) { |
25 » » MP_CHECKOK(s_mp_pad(r, 8)); | 23 MP_CHECKOK(s_mp_pad(r, 8)); |
26 » } | 24 } |
27 » u = MP_DIGITS(r); | 25 u = MP_DIGITS(r); |
28 » MP_USED(r) = 8; | 26 MP_USED(r) = 8; |
29 | 27 |
30 » /* u[7] only has 18 significant bits */ | 28 /* u[7] only has 18 significant bits */ |
31 » z = u[7]; | 29 z = u[7]; |
32 » u[4] ^= (z << 33) ^ (z >> 41); | 30 u[4] ^= (z << 33) ^ (z >> 41); |
33 » u[3] ^= (z << 23); | 31 u[3] ^= (z << 23); |
34 » z = u[6]; | 32 z = u[6]; |
35 » u[4] ^= (z >> 31); | 33 u[4] ^= (z >> 31); |
36 » u[3] ^= (z << 33) ^ (z >> 41); | 34 u[3] ^= (z << 33) ^ (z >> 41); |
37 » u[2] ^= (z << 23); | 35 u[2] ^= (z << 23); |
38 » z = u[5]; | 36 z = u[5]; |
39 » u[3] ^= (z >> 31); | 37 u[3] ^= (z >> 31); |
40 » u[2] ^= (z << 33) ^ (z >> 41); | 38 u[2] ^= (z << 33) ^ (z >> 41); |
41 » u[1] ^= (z << 23); | 39 u[1] ^= (z << 23); |
42 » z = u[4]; | 40 z = u[4]; |
43 » u[2] ^= (z >> 31); | 41 u[2] ^= (z >> 31); |
44 » u[1] ^= (z << 33) ^ (z >> 41); | 42 u[1] ^= (z << 33) ^ (z >> 41); |
45 » u[0] ^= (z << 23); | 43 u[0] ^= (z << 23); |
46 » z = u[3] >> 41;»» » » /* z only has 23 significant bit
s */ | 44 z = u[3] >> 41; /* z only has 23 significant bits */ |
47 » u[1] ^= (z << 10); | 45 u[1] ^= (z << 10); |
48 » u[0] ^= z; | 46 u[0] ^= z; |
49 » /* clear bits above 233 */ | 47 /* clear bits above 233 */ |
50 » u[7] = u[6] = u[5] = u[4] = 0; | 48 u[7] = u[6] = u[5] = u[4] = 0; |
51 » u[3] ^= z << 41; | 49 u[3] ^= z << 41; |
52 #else | 50 #else |
53 » if (MP_USED(r) < 15) { | 51 if (MP_USED(r) < 15) { |
54 » » MP_CHECKOK(s_mp_pad(r, 15)); | 52 MP_CHECKOK(s_mp_pad(r, 15)); |
55 » } | 53 } |
56 » u = MP_DIGITS(r); | 54 u = MP_DIGITS(r); |
57 » MP_USED(r) = 15; | 55 MP_USED(r) = 15; |
58 | 56 |
59 » /* u[14] only has 18 significant bits */ | 57 /* u[14] only has 18 significant bits */ |
60 » z = u[14]; | 58 z = u[14]; |
61 » u[9] ^= (z << 1); | 59 u[9] ^= (z << 1); |
62 » u[7] ^= (z >> 9); | 60 u[7] ^= (z >> 9); |
63 » u[6] ^= (z << 23); | 61 u[6] ^= (z << 23); |
64 » z = u[13]; | 62 z = u[13]; |
65 » u[9] ^= (z >> 31); | 63 u[9] ^= (z >> 31); |
66 » u[8] ^= (z << 1); | 64 u[8] ^= (z << 1); |
67 » u[6] ^= (z >> 9); | 65 u[6] ^= (z >> 9); |
68 » u[5] ^= (z << 23); | 66 u[5] ^= (z << 23); |
69 » z = u[12]; | 67 z = u[12]; |
70 » u[8] ^= (z >> 31); | 68 u[8] ^= (z >> 31); |
71 » u[7] ^= (z << 1); | 69 u[7] ^= (z << 1); |
72 » u[5] ^= (z >> 9); | 70 u[5] ^= (z >> 9); |
73 » u[4] ^= (z << 23); | 71 u[4] ^= (z << 23); |
74 » z = u[11]; | 72 z = u[11]; |
75 » u[7] ^= (z >> 31); | 73 u[7] ^= (z >> 31); |
76 » u[6] ^= (z << 1); | 74 u[6] ^= (z << 1); |
77 » u[4] ^= (z >> 9); | 75 u[4] ^= (z >> 9); |
78 » u[3] ^= (z << 23); | 76 u[3] ^= (z << 23); |
79 » z = u[10]; | 77 z = u[10]; |
80 » u[6] ^= (z >> 31); | 78 u[6] ^= (z >> 31); |
81 » u[5] ^= (z << 1); | 79 u[5] ^= (z << 1); |
82 » u[3] ^= (z >> 9); | 80 u[3] ^= (z >> 9); |
83 » u[2] ^= (z << 23); | 81 u[2] ^= (z << 23); |
84 » z = u[9]; | 82 z = u[9]; |
85 » u[5] ^= (z >> 31); | 83 u[5] ^= (z >> 31); |
86 » u[4] ^= (z << 1); | 84 u[4] ^= (z << 1); |
87 » u[2] ^= (z >> 9); | 85 u[2] ^= (z >> 9); |
88 » u[1] ^= (z << 23); | 86 u[1] ^= (z << 23); |
89 » z = u[8]; | 87 z = u[8]; |
90 » u[4] ^= (z >> 31); | 88 u[4] ^= (z >> 31); |
91 » u[3] ^= (z << 1); | 89 u[3] ^= (z << 1); |
92 » u[1] ^= (z >> 9); | 90 u[1] ^= (z >> 9); |
93 » u[0] ^= (z << 23); | 91 u[0] ^= (z << 23); |
94 » z = u[7] >> 9;» » » » /* z only has 23 significant bit
s */ | 92 z = u[7] >> 9; /* z only has 23 significant bits */ |
95 » u[3] ^= (z >> 22); | 93 u[3] ^= (z >> 22); |
96 » u[2] ^= (z << 10); | 94 u[2] ^= (z << 10); |
97 » u[0] ^= z; | 95 u[0] ^= z; |
98 » /* clear bits above 233 */ | 96 /* clear bits above 233 */ |
99 » u[14] = u[13] = u[12] = u[11] = u[10] = u[9] = u[8] = 0; | 97 u[14] = u[13] = u[12] = u[11] = u[10] = u[9] = u[8] = 0; |
100 » u[7] ^= z << 9; | 98 u[7] ^= z << 9; |
101 #endif | 99 #endif |
102 » s_mp_clamp(r); | 100 s_mp_clamp(r); |
103 | 101 |
104 CLEANUP: | 102 CLEANUP: |
105 » return res; | 103 return res; |
106 } | 104 } |
107 | 105 |
108 /* Fast squaring for polynomials over a 233-bit curve. Assumes reduction | 106 /* Fast squaring for polynomials over a 233-bit curve. Assumes reduction |
109 * polynomial with terms {233, 74, 0}. */ | 107 * polynomial with terms {233, 74, 0}. */ |
110 mp_err | 108 mp_err ec_GF2m_233_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) { |
111 ec_GF2m_233_sqr(const mp_int *a, mp_int *r, const GFMethod *meth) | 109 mp_err res = MP_OKAY; |
112 { | 110 mp_digit *u, *v; |
113 » mp_err res = MP_OKAY; | 111 |
114 » mp_digit *u, *v; | 112 v = MP_DIGITS(a); |
115 | |
116 » v = MP_DIGITS(a); | |
117 | 113 |
118 #ifdef ECL_SIXTY_FOUR_BIT | 114 #ifdef ECL_SIXTY_FOUR_BIT |
119 » if (MP_USED(a) < 4) { | 115 if (MP_USED(a) < 4) { |
120 » » return mp_bsqrmod(a, meth->irr_arr, r); | 116 return mp_bsqrmod(a, meth->irr_arr, r); |
121 » } | 117 } |
122 » if (MP_USED(r) < 8) { | 118 if (MP_USED(r) < 8) { |
123 » » MP_CHECKOK(s_mp_pad(r, 8)); | 119 MP_CHECKOK(s_mp_pad(r, 8)); |
124 » } | 120 } |
125 » MP_USED(r) = 8; | 121 MP_USED(r) = 8; |
126 #else | 122 #else |
127 » if (MP_USED(a) < 8) { | 123 if (MP_USED(a) < 8) { |
128 » » return mp_bsqrmod(a, meth->irr_arr, r); | 124 return mp_bsqrmod(a, meth->irr_arr, r); |
129 » } | 125 } |
130 » if (MP_USED(r) < 15) { | 126 if (MP_USED(r) < 15) { |
131 » » MP_CHECKOK(s_mp_pad(r, 15)); | 127 MP_CHECKOK(s_mp_pad(r, 15)); |
132 » } | 128 } |
133 » MP_USED(r) = 15; | 129 MP_USED(r) = 15; |
134 #endif | 130 #endif |
135 » u = MP_DIGITS(r); | 131 u = MP_DIGITS(r); |
136 | 132 |
137 #ifdef ECL_THIRTY_TWO_BIT | 133 #ifdef ECL_THIRTY_TWO_BIT |
138 » u[14] = gf2m_SQR0(v[7]); | 134 u[14] = gf2m_SQR0(v[7]); |
139 » u[13] = gf2m_SQR1(v[6]); | 135 u[13] = gf2m_SQR1(v[6]); |
140 » u[12] = gf2m_SQR0(v[6]); | 136 u[12] = gf2m_SQR0(v[6]); |
141 » u[11] = gf2m_SQR1(v[5]); | 137 u[11] = gf2m_SQR1(v[5]); |
142 » u[10] = gf2m_SQR0(v[5]); | 138 u[10] = gf2m_SQR0(v[5]); |
143 » u[9] = gf2m_SQR1(v[4]); | 139 u[9] = gf2m_SQR1(v[4]); |
144 » u[8] = gf2m_SQR0(v[4]); | 140 u[8] = gf2m_SQR0(v[4]); |
145 #endif | 141 #endif |
146 » u[7] = gf2m_SQR1(v[3]); | 142 u[7] = gf2m_SQR1(v[3]); |
147 » u[6] = gf2m_SQR0(v[3]); | 143 u[6] = gf2m_SQR0(v[3]); |
148 » u[5] = gf2m_SQR1(v[2]); | 144 u[5] = gf2m_SQR1(v[2]); |
149 » u[4] = gf2m_SQR0(v[2]); | 145 u[4] = gf2m_SQR0(v[2]); |
150 » u[3] = gf2m_SQR1(v[1]); | 146 u[3] = gf2m_SQR1(v[1]); |
151 » u[2] = gf2m_SQR0(v[1]); | 147 u[2] = gf2m_SQR0(v[1]); |
152 » u[1] = gf2m_SQR1(v[0]); | 148 u[1] = gf2m_SQR1(v[0]); |
153 » u[0] = gf2m_SQR0(v[0]); | 149 u[0] = gf2m_SQR0(v[0]); |
154 » return ec_GF2m_233_mod(r, r, meth); | 150 return ec_GF2m_233_mod(r, r, meth); |
155 | 151 |
156 CLEANUP: | 152 CLEANUP: |
157 » return res; | 153 return res; |
158 } | 154 } |
159 | 155 |
160 /* Fast multiplication for polynomials over a 233-bit curve. Assumes | 156 /* Fast multiplication for polynomials over a 233-bit curve. Assumes |
161 * reduction polynomial with terms {233, 74, 0}. */ | 157 * reduction polynomial with terms {233, 74, 0}. */ |
162 mp_err | 158 mp_err ec_GF2m_233_mul(const mp_int *a, const mp_int *b, mp_int *r, |
163 ec_GF2m_233_mul(const mp_int *a, const mp_int *b, mp_int *r, | 159 const GFMethod *meth) { |
164 » » » » const GFMethod *meth) | 160 mp_err res = MP_OKAY; |
165 { | 161 mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0; |
166 » mp_err res = MP_OKAY; | 162 |
167 » mp_digit a3 = 0, a2 = 0, a1 = 0, a0, b3 = 0, b2 = 0, b1 = 0, b0; | 163 #ifdef ECL_THIRTY_TWO_BIT |
168 | 164 mp_digit a7 = 0, a6 = 0, a5 = 0, a4 = 0, b7 = 0, b6 = 0, b5 = 0, b4 = 0; |
169 #ifdef ECL_THIRTY_TWO_BIT | 165 mp_digit rm[8]; |
170 » mp_digit a7 = 0, a6 = 0, a5 = 0, a4 = 0, b7 = 0, b6 = 0, b5 = 0, b4 = | 166 #endif |
171 » » 0; | 167 |
172 » mp_digit rm[8]; | 168 if (a == b) { |
173 #endif | 169 return ec_GF2m_233_sqr(a, r, meth); |
174 | 170 } else { |
175 » if (a == b) { | 171 switch (MP_USED(a)) { |
176 » » return ec_GF2m_233_sqr(a, r, meth); | 172 #ifdef ECL_THIRTY_TWO_BIT |
177 » } else { | 173 case 8: |
178 » » switch (MP_USED(a)) { | 174 a7 = MP_DIGIT(a, 7); |
179 #ifdef ECL_THIRTY_TWO_BIT | 175 case 7: |
180 » » case 8: | 176 a6 = MP_DIGIT(a, 6); |
181 » » » a7 = MP_DIGIT(a, 7); | 177 case 6: |
182 » » case 7: | 178 a5 = MP_DIGIT(a, 5); |
183 » » » a6 = MP_DIGIT(a, 6); | 179 case 5: |
184 » » case 6: | 180 a4 = MP_DIGIT(a, 4); |
185 » » » a5 = MP_DIGIT(a, 5); | 181 #endif |
186 » » case 5: | 182 case 4: |
187 » » » a4 = MP_DIGIT(a, 4); | 183 a3 = MP_DIGIT(a, 3); |
188 #endif | 184 case 3: |
189 » » case 4: | 185 a2 = MP_DIGIT(a, 2); |
190 » » » a3 = MP_DIGIT(a, 3); | 186 case 2: |
191 » » case 3: | 187 a1 = MP_DIGIT(a, 1); |
192 » » » a2 = MP_DIGIT(a, 2); | 188 default: |
193 » » case 2: | 189 a0 = MP_DIGIT(a, 0); |
194 » » » a1 = MP_DIGIT(a, 1); | 190 } |
195 » » default: | 191 switch (MP_USED(b)) { |
196 » » » a0 = MP_DIGIT(a, 0); | 192 #ifdef ECL_THIRTY_TWO_BIT |
197 » » } | 193 case 8: |
198 » » switch (MP_USED(b)) { | 194 b7 = MP_DIGIT(b, 7); |
199 #ifdef ECL_THIRTY_TWO_BIT | 195 case 7: |
200 » » case 8: | 196 b6 = MP_DIGIT(b, 6); |
201 » » » b7 = MP_DIGIT(b, 7); | 197 case 6: |
202 » » case 7: | 198 b5 = MP_DIGIT(b, 5); |
203 » » » b6 = MP_DIGIT(b, 6); | 199 case 5: |
204 » » case 6: | 200 b4 = MP_DIGIT(b, 4); |
205 » » » b5 = MP_DIGIT(b, 5); | 201 #endif |
206 » » case 5: | 202 case 4: |
207 » » » b4 = MP_DIGIT(b, 4); | 203 b3 = MP_DIGIT(b, 3); |
208 #endif | 204 case 3: |
209 » » case 4: | 205 b2 = MP_DIGIT(b, 2); |
210 » » » b3 = MP_DIGIT(b, 3); | 206 case 2: |
211 » » case 3: | 207 b1 = MP_DIGIT(b, 1); |
212 » » » b2 = MP_DIGIT(b, 2); | 208 default: |
213 » » case 2: | 209 b0 = MP_DIGIT(b, 0); |
214 » » » b1 = MP_DIGIT(b, 1); | 210 } |
215 » » default: | |
216 » » » b0 = MP_DIGIT(b, 0); | |
217 » » } | |
218 #ifdef ECL_SIXTY_FOUR_BIT | 211 #ifdef ECL_SIXTY_FOUR_BIT |
219 » » MP_CHECKOK(s_mp_pad(r, 8)); | 212 MP_CHECKOK(s_mp_pad(r, 8)); |
220 » » s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); | 213 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); |
221 » » MP_USED(r) = 8; | 214 MP_USED(r) = 8; |
222 » » s_mp_clamp(r); | 215 s_mp_clamp(r); |
223 #else | 216 #else |
224 » » MP_CHECKOK(s_mp_pad(r, 16)); | 217 MP_CHECKOK(s_mp_pad(r, 16)); |
225 » » s_bmul_4x4(MP_DIGITS(r) + 8, a7, a6, a5, a4, b7, b6, b5, b4); | 218 s_bmul_4x4(MP_DIGITS(r) + 8, a7, a6, a5, a4, b7, b6, b5, b4); |
226 » » s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); | 219 s_bmul_4x4(MP_DIGITS(r), a3, a2, a1, a0, b3, b2, b1, b0); |
227 » » s_bmul_4x4(rm, a7 ^ a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b7 ^ b3, | 220 s_bmul_4x4(rm, a7 ^ a3, a6 ^ a2, a5 ^ a1, a4 ^ a0, b7 ^ b3, b6 ^ b2, |
228 » » » » b6 ^ b2, b5 ^ b1, b4 ^ b0); | 221 b5 ^ b1, b4 ^ b0); |
229 » » rm[7] ^= MP_DIGIT(r, 7) ^ MP_DIGIT(r, 15); | 222 rm[7] ^= MP_DIGIT(r, 7) ^ MP_DIGIT(r, 15); |
230 » » rm[6] ^= MP_DIGIT(r, 6) ^ MP_DIGIT(r, 14); | 223 rm[6] ^= MP_DIGIT(r, 6) ^ MP_DIGIT(r, 14); |
231 » » rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13); | 224 rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 13); |
232 » » rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12); | 225 rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 12); |
233 » » rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11); | 226 rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 11); |
234 » » rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10); | 227 rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 10); |
235 » » rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9); | 228 rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 9); |
236 » » rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8); | 229 rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 8); |
237 » » MP_DIGIT(r, 11) ^= rm[7]; | 230 MP_DIGIT(r, 11) ^= rm[7]; |
238 » » MP_DIGIT(r, 10) ^= rm[6]; | 231 MP_DIGIT(r, 10) ^= rm[6]; |
239 » » MP_DIGIT(r, 9) ^= rm[5]; | 232 MP_DIGIT(r, 9) ^= rm[5]; |
240 » » MP_DIGIT(r, 8) ^= rm[4]; | 233 MP_DIGIT(r, 8) ^= rm[4]; |
241 » » MP_DIGIT(r, 7) ^= rm[3]; | 234 MP_DIGIT(r, 7) ^= rm[3]; |
242 » » MP_DIGIT(r, 6) ^= rm[2]; | 235 MP_DIGIT(r, 6) ^= rm[2]; |
243 » » MP_DIGIT(r, 5) ^= rm[1]; | 236 MP_DIGIT(r, 5) ^= rm[1]; |
244 » » MP_DIGIT(r, 4) ^= rm[0]; | 237 MP_DIGIT(r, 4) ^= rm[0]; |
245 » » MP_USED(r) = 16; | 238 MP_USED(r) = 16; |
246 » » s_mp_clamp(r); | 239 s_mp_clamp(r); |
247 #endif | 240 #endif |
248 » » return ec_GF2m_233_mod(r, r, meth); | 241 return ec_GF2m_233_mod(r, r, meth); |
249 » } | 242 } |
250 | 243 |
251 CLEANUP: | 244 CLEANUP: |
252 » return res; | 245 return res; |
253 } | 246 } |
254 | 247 |
255 /* Wire in fast field arithmetic for 233-bit curves. */ | 248 /* Wire in fast field arithmetic for 233-bit curves. */ |
256 mp_err | 249 mp_err ec_group_set_gf2m233(ECGroup *group, ECCurveName name) { |
257 ec_group_set_gf2m233(ECGroup *group, ECCurveName name) | 250 group->meth->field_mod = &ec_GF2m_233_mod; |
258 { | 251 group->meth->field_mul = &ec_GF2m_233_mul; |
259 » group->meth->field_mod = &ec_GF2m_233_mod; | 252 group->meth->field_sqr = &ec_GF2m_233_sqr; |
260 » group->meth->field_mul = &ec_GF2m_233_mul; | 253 return MP_OKAY; |
261 » group->meth->field_sqr = &ec_GF2m_233_sqr; | 254 } |
262 » return MP_OKAY; | |
263 } | |
OLD | NEW |