1 /*
2 * Copyright (c) 2007, 2011, Oracle and/or its affiliates. All rights reserved.
3 * Use is subject to license terms.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
14 *
15 * You should have received a copy of the GNU Lesser General Public License
16 * along with this library; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 /* *********************************************************************
25 *
26 * The Original Code is the elliptic curve math library for binary polynomial field curves.
27 *
28 * The Initial Developer of the Original Code is
29 * Sun Microsystems, Inc.
30 * Portions created by the Initial Developer are Copyright (C) 2003
31 * the Initial Developer. All Rights Reserved.
32 *
33 * Contributor(s):
34 * Sheueling Chang-Shantz <sheueling.chang@sun.com>,
35 * Stephen Fung <fungstep@hotmail.com>, and
36 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
37 *
38 *********************************************************************** */
39
40 #include "ec2.h"
41 #include "mp_gf2m.h"
42 #include "mp_gf2m-priv.h"
43 #include "mpi.h"
44 #include "mpi-priv.h"
45 #ifndef _KERNEL
46 #include <stdlib.h>
47 #endif
48
49 /* Fast reduction for polynomials over a 163-bit curve. Assumes reduction
50 * polynomial with terms {163, 7, 6, 3, 0}. */
51 mp_err
ec_GF2m_163_mod(const mp_int * a,mp_int * r,const GFMethod * meth)52 ec_GF2m_163_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
53 {
54 mp_err res = MP_OKAY;
55 mp_digit *u, z;
56
57 if (a != r) {
58 MP_CHECKOK(mp_copy(a, r));
59 }
60 #ifdef ECL_SIXTY_FOUR_BIT
61 if (MP_USED(r) < 6) {
62 MP_CHECKOK(s_mp_pad(r, 6));
63 }
64 u = MP_DIGITS(r);
65 MP_USED(r) = 6;
66
67 /* u[5] only has 6 significant bits */
68 z = u[5];
69 u[2] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
70 z = u[4];
71 u[2] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35);
72 u[1] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
73 z = u[3];
74 u[1] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35);
75 u[0] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
76 z = u[2] >> 35; /* z only has 29 significant bits */
77 u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z;
78 /* clear bits above 163 */
79 u[5] = u[4] = u[3] = 0;
80 u[2] ^= z << 35;
81 #else
82 if (MP_USED(r) < 11) {
83 MP_CHECKOK(s_mp_pad(r, 11));
84 }
85 u = MP_DIGITS(r);
86 MP_USED(r) = 11;
87
88 /* u[11] only has 6 significant bits */
89 z = u[10];
90 u[5] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
91 u[4] ^= (z << 29);
92 z = u[9];
93 u[5] ^= (z >> 28) ^ (z >> 29);
94 u[4] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
95 u[3] ^= (z << 29);
96 z = u[8];
97 u[4] ^= (z >> 28) ^ (z >> 29);
98 u[3] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
99 u[2] ^= (z << 29);
100 z = u[7];
101 u[3] ^= (z >> 28) ^ (z >> 29);
102 u[2] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
103 u[1] ^= (z << 29);
104 z = u[6];
105 u[2] ^= (z >> 28) ^ (z >> 29);
106 u[1] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
107 u[0] ^= (z << 29);
108 z = u[5] >> 3; /* z only has 29 significant bits */
109 u[1] ^= (z >> 25) ^ (z >> 26);
110 u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z;
111 /* clear bits above 163 */
112 u[11] = u[10] = u[9] = u[8] = u[7] = u[6] = 0;
113 u[5] ^= z << 3;
114 #endif
115 s_mp_clamp(r);
116
117 CLEANUP:
118 return res;
119 }
120
121 /* Fast squaring for polynomials over a 163-bit curve. Assumes reduction
122 * polynomial with terms {163, 7, 6, 3, 0}. */
123 mp_err
ec_GF2m_163_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)124 ec_GF2m_163_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
125 {
126 mp_err res = MP_OKAY;
127 mp_digit *u, *v;
128
129 v = MP_DIGITS(a);
130
131 #ifdef ECL_SIXTY_FOUR_BIT
132 if (MP_USED(a) < 3) {
133 return mp_bsqrmod(a, meth->irr_arr, r);
134 }
135 if (MP_USED(r) < 6) {
136 MP_CHECKOK(s_mp_pad(r, 6));
137 }
138 MP_USED(r) = 6;
139 #else
140 if (MP_USED(a) < 6) {
141 return mp_bsqrmod(a, meth->irr_arr, r);
142 }
143 if (MP_USED(r) < 12) {
144 MP_CHECKOK(s_mp_pad(r, 12));
145 }
146 MP_USED(r) = 12;
147 #endif
148 u = MP_DIGITS(r);
149
150 #ifdef ECL_THIRTY_TWO_BIT
151 u[11] = gf2m_SQR1(v[5]);
152 u[10] = gf2m_SQR0(v[5]);
153 u[9] = gf2m_SQR1(v[4]);
154 u[8] = gf2m_SQR0(v[4]);
155 u[7] = gf2m_SQR1(v[3]);
156 u[6] = gf2m_SQR0(v[3]);
157 #endif
158 u[5] = gf2m_SQR1(v[2]);
159 u[4] = gf2m_SQR0(v[2]);
160 u[3] = gf2m_SQR1(v[1]);
161 u[2] = gf2m_SQR0(v[1]);
162 u[1] = gf2m_SQR1(v[0]);
163 u[0] = gf2m_SQR0(v[0]);
164 return ec_GF2m_163_mod(r, r, meth);
165
166 CLEANUP:
167 return res;
168 }
169
170 /* Fast multiplication for polynomials over a 163-bit curve. Assumes
171 * reduction polynomial with terms {163, 7, 6, 3, 0}. */
172 mp_err
ec_GF2m_163_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)173 ec_GF2m_163_mul(const mp_int *a, const mp_int *b, mp_int *r,
174 const GFMethod *meth)
175 {
176 mp_err res = MP_OKAY;
177 mp_digit a2 = 0, a1 = 0, a0, b2 = 0, b1 = 0, b0;
178
179 #ifdef ECL_THIRTY_TWO_BIT
180 mp_digit a5 = 0, a4 = 0, a3 = 0, b5 = 0, b4 = 0, b3 = 0;
181 mp_digit rm[6];
182 #endif
183
184 if (a == b) {
185 return ec_GF2m_163_sqr(a, r, meth);
186 } else {
187 switch (MP_USED(a)) {
188 #ifdef ECL_THIRTY_TWO_BIT
189 case 6:
190 a5 = MP_DIGIT(a, 5);
191 case 5:
192 a4 = MP_DIGIT(a, 4);
193 case 4:
194 a3 = MP_DIGIT(a, 3);
195 #endif
196 case 3:
197 a2 = MP_DIGIT(a, 2);
198 case 2:
199 a1 = MP_DIGIT(a, 1);
200 default:
201 a0 = MP_DIGIT(a, 0);
202 }
203 switch (MP_USED(b)) {
204 #ifdef ECL_THIRTY_TWO_BIT
205 case 6:
206 b5 = MP_DIGIT(b, 5);
207 case 5:
208 b4 = MP_DIGIT(b, 4);
209 case 4:
210 b3 = MP_DIGIT(b, 3);
211 #endif
212 case 3:
213 b2 = MP_DIGIT(b, 2);
214 case 2:
215 b1 = MP_DIGIT(b, 1);
216 default:
217 b0 = MP_DIGIT(b, 0);
218 }
219 #ifdef ECL_SIXTY_FOUR_BIT
220 MP_CHECKOK(s_mp_pad(r, 6));
221 s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0);
222 MP_USED(r) = 6;
223 s_mp_clamp(r);
224 #else
225 MP_CHECKOK(s_mp_pad(r, 12));
226 s_bmul_3x3(MP_DIGITS(r) + 6, a5, a4, a3, b5, b4, b3);
227 s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0);
228 s_bmul_3x3(rm, a5 ^ a2, a4 ^ a1, a3 ^ a0, b5 ^ b2, b4 ^ b1,
229 b3 ^ b0);
230 rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 11);
231 rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 10);
232 rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 9);
233 rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 8);
234 rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 7);
235 rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 6);
236 MP_DIGIT(r, 8) ^= rm[5];
237 MP_DIGIT(r, 7) ^= rm[4];
238 MP_DIGIT(r, 6) ^= rm[3];
239 MP_DIGIT(r, 5) ^= rm[2];
240 MP_DIGIT(r, 4) ^= rm[1];
241 MP_DIGIT(r, 3) ^= rm[0];
242 MP_USED(r) = 12;
243 s_mp_clamp(r);
244 #endif
245 return ec_GF2m_163_mod(r, r, meth);
246 }
247
248 CLEANUP:
249 return res;
250 }
251
252 /* Wire in fast field arithmetic for 163-bit curves. */
253 mp_err
ec_group_set_gf2m163(ECGroup * group,ECCurveName name)254 ec_group_set_gf2m163(ECGroup *group, ECCurveName name)
255 {
256 group->meth->field_mod = &ec_GF2m_163_mod;
257 group->meth->field_mul = &ec_GF2m_163_mul;
258 group->meth->field_sqr = &ec_GF2m_163_sqr;
259 return MP_OKAY;
260 }
261