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