1*55fea89dSDan Cross /*
2f9fbec18Smcpowers * ***** BEGIN LICENSE BLOCK *****
3f9fbec18Smcpowers * Version: MPL 1.1/GPL 2.0/LGPL 2.1
4f9fbec18Smcpowers *
5f9fbec18Smcpowers * The contents of this file are subject to the Mozilla Public License Version
6f9fbec18Smcpowers * 1.1 (the "License"); you may not use this file except in compliance with
7f9fbec18Smcpowers * the License. You may obtain a copy of the License at
8f9fbec18Smcpowers * http://www.mozilla.org/MPL/
9f9fbec18Smcpowers *
10f9fbec18Smcpowers * Software distributed under the License is distributed on an "AS IS" basis,
11f9fbec18Smcpowers * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
12f9fbec18Smcpowers * for the specific language governing rights and limitations under the
13f9fbec18Smcpowers * License.
14f9fbec18Smcpowers *
15f9fbec18Smcpowers * The Original Code is the elliptic curve math library for binary polynomial field curves.
16f9fbec18Smcpowers *
17f9fbec18Smcpowers * The Initial Developer of the Original Code is
18f9fbec18Smcpowers * Sun Microsystems, Inc.
19f9fbec18Smcpowers * Portions created by the Initial Developer are Copyright (C) 2003
20f9fbec18Smcpowers * the Initial Developer. All Rights Reserved.
21f9fbec18Smcpowers *
22f9fbec18Smcpowers * Contributor(s):
23f9fbec18Smcpowers * Sheueling Chang-Shantz <sheueling.chang@sun.com>,
24f9fbec18Smcpowers * Stephen Fung <fungstep@hotmail.com>, and
25f9fbec18Smcpowers * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories.
26f9fbec18Smcpowers *
27f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of
28f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
29f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
30f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
31f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only
32f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
33f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your
34f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice
35f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
36f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under
37f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL.
38f9fbec18Smcpowers *
39f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */
40f9fbec18Smcpowers /*
41f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
42f9fbec18Smcpowers * Use is subject to license terms.
43f9fbec18Smcpowers *
44f9fbec18Smcpowers * Sun elects to use this software under the MPL license.
45f9fbec18Smcpowers */
46f9fbec18Smcpowers
47f9fbec18Smcpowers #include "ec2.h"
48f9fbec18Smcpowers #include "mp_gf2m.h"
49f9fbec18Smcpowers #include "mp_gf2m-priv.h"
50f9fbec18Smcpowers #include "mpi.h"
51f9fbec18Smcpowers #include "mpi-priv.h"
52f9fbec18Smcpowers #ifndef _KERNEL
53f9fbec18Smcpowers #include <stdlib.h>
54f9fbec18Smcpowers #endif
55f9fbec18Smcpowers
56f9fbec18Smcpowers /* Fast reduction for polynomials over a 163-bit curve. Assumes reduction
57f9fbec18Smcpowers * polynomial with terms {163, 7, 6, 3, 0}. */
58f9fbec18Smcpowers mp_err
ec_GF2m_163_mod(const mp_int * a,mp_int * r,const GFMethod * meth)59f9fbec18Smcpowers ec_GF2m_163_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
60f9fbec18Smcpowers {
61f9fbec18Smcpowers mp_err res = MP_OKAY;
62f9fbec18Smcpowers mp_digit *u, z;
63f9fbec18Smcpowers
64f9fbec18Smcpowers if (a != r) {
65f9fbec18Smcpowers MP_CHECKOK(mp_copy(a, r));
66f9fbec18Smcpowers }
67f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT
68f9fbec18Smcpowers if (MP_USED(r) < 6) {
69f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
70f9fbec18Smcpowers }
71f9fbec18Smcpowers u = MP_DIGITS(r);
72f9fbec18Smcpowers MP_USED(r) = 6;
73f9fbec18Smcpowers
74f9fbec18Smcpowers /* u[5] only has 6 significant bits */
75f9fbec18Smcpowers z = u[5];
76f9fbec18Smcpowers u[2] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
77f9fbec18Smcpowers z = u[4];
78f9fbec18Smcpowers u[2] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35);
79f9fbec18Smcpowers u[1] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
80f9fbec18Smcpowers z = u[3];
81f9fbec18Smcpowers u[1] ^= (z >> 28) ^ (z >> 29) ^ (z >> 32) ^ (z >> 35);
82f9fbec18Smcpowers u[0] ^= (z << 36) ^ (z << 35) ^ (z << 32) ^ (z << 29);
83f9fbec18Smcpowers z = u[2] >> 35; /* z only has 29 significant bits */
84f9fbec18Smcpowers u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z;
85f9fbec18Smcpowers /* clear bits above 163 */
86f9fbec18Smcpowers u[5] = u[4] = u[3] = 0;
87f9fbec18Smcpowers u[2] ^= z << 35;
88f9fbec18Smcpowers #else
89f9fbec18Smcpowers if (MP_USED(r) < 11) {
90f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 11));
91f9fbec18Smcpowers }
92f9fbec18Smcpowers u = MP_DIGITS(r);
93f9fbec18Smcpowers MP_USED(r) = 11;
94f9fbec18Smcpowers
95f9fbec18Smcpowers /* u[11] only has 6 significant bits */
96f9fbec18Smcpowers z = u[10];
97f9fbec18Smcpowers u[5] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
98f9fbec18Smcpowers u[4] ^= (z << 29);
99f9fbec18Smcpowers z = u[9];
100f9fbec18Smcpowers u[5] ^= (z >> 28) ^ (z >> 29);
101f9fbec18Smcpowers u[4] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
102f9fbec18Smcpowers u[3] ^= (z << 29);
103f9fbec18Smcpowers z = u[8];
104f9fbec18Smcpowers u[4] ^= (z >> 28) ^ (z >> 29);
105f9fbec18Smcpowers u[3] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
106f9fbec18Smcpowers u[2] ^= (z << 29);
107f9fbec18Smcpowers z = u[7];
108f9fbec18Smcpowers u[3] ^= (z >> 28) ^ (z >> 29);
109f9fbec18Smcpowers u[2] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
110f9fbec18Smcpowers u[1] ^= (z << 29);
111f9fbec18Smcpowers z = u[6];
112f9fbec18Smcpowers u[2] ^= (z >> 28) ^ (z >> 29);
113f9fbec18Smcpowers u[1] ^= (z << 4) ^ (z << 3) ^ z ^ (z >> 3);
114f9fbec18Smcpowers u[0] ^= (z << 29);
115f9fbec18Smcpowers z = u[5] >> 3; /* z only has 29 significant bits */
116f9fbec18Smcpowers u[1] ^= (z >> 25) ^ (z >> 26);
117f9fbec18Smcpowers u[0] ^= (z << 7) ^ (z << 6) ^ (z << 3) ^ z;
118f9fbec18Smcpowers /* clear bits above 163 */
119f9fbec18Smcpowers u[11] = u[10] = u[9] = u[8] = u[7] = u[6] = 0;
120f9fbec18Smcpowers u[5] ^= z << 3;
121f9fbec18Smcpowers #endif
122f9fbec18Smcpowers s_mp_clamp(r);
123f9fbec18Smcpowers
124f9fbec18Smcpowers CLEANUP:
125f9fbec18Smcpowers return res;
126f9fbec18Smcpowers }
127f9fbec18Smcpowers
128f9fbec18Smcpowers /* Fast squaring for polynomials over a 163-bit curve. Assumes reduction
129f9fbec18Smcpowers * polynomial with terms {163, 7, 6, 3, 0}. */
130f9fbec18Smcpowers mp_err
ec_GF2m_163_sqr(const mp_int * a,mp_int * r,const GFMethod * meth)131f9fbec18Smcpowers ec_GF2m_163_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
132f9fbec18Smcpowers {
133f9fbec18Smcpowers mp_err res = MP_OKAY;
134f9fbec18Smcpowers mp_digit *u, *v;
135f9fbec18Smcpowers
136f9fbec18Smcpowers v = MP_DIGITS(a);
137f9fbec18Smcpowers
138f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT
139f9fbec18Smcpowers if (MP_USED(a) < 3) {
140f9fbec18Smcpowers return mp_bsqrmod(a, meth->irr_arr, r);
141f9fbec18Smcpowers }
142f9fbec18Smcpowers if (MP_USED(r) < 6) {
143f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
144f9fbec18Smcpowers }
145f9fbec18Smcpowers MP_USED(r) = 6;
146f9fbec18Smcpowers #else
147f9fbec18Smcpowers if (MP_USED(a) < 6) {
148f9fbec18Smcpowers return mp_bsqrmod(a, meth->irr_arr, r);
149f9fbec18Smcpowers }
150f9fbec18Smcpowers if (MP_USED(r) < 12) {
151f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 12));
152f9fbec18Smcpowers }
153f9fbec18Smcpowers MP_USED(r) = 12;
154f9fbec18Smcpowers #endif
155f9fbec18Smcpowers u = MP_DIGITS(r);
156f9fbec18Smcpowers
157f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
158f9fbec18Smcpowers u[11] = gf2m_SQR1(v[5]);
159f9fbec18Smcpowers u[10] = gf2m_SQR0(v[5]);
160f9fbec18Smcpowers u[9] = gf2m_SQR1(v[4]);
161f9fbec18Smcpowers u[8] = gf2m_SQR0(v[4]);
162f9fbec18Smcpowers u[7] = gf2m_SQR1(v[3]);
163f9fbec18Smcpowers u[6] = gf2m_SQR0(v[3]);
164f9fbec18Smcpowers #endif
165f9fbec18Smcpowers u[5] = gf2m_SQR1(v[2]);
166f9fbec18Smcpowers u[4] = gf2m_SQR0(v[2]);
167f9fbec18Smcpowers u[3] = gf2m_SQR1(v[1]);
168f9fbec18Smcpowers u[2] = gf2m_SQR0(v[1]);
169f9fbec18Smcpowers u[1] = gf2m_SQR1(v[0]);
170f9fbec18Smcpowers u[0] = gf2m_SQR0(v[0]);
171f9fbec18Smcpowers return ec_GF2m_163_mod(r, r, meth);
172f9fbec18Smcpowers
173f9fbec18Smcpowers CLEANUP:
174f9fbec18Smcpowers return res;
175f9fbec18Smcpowers }
176f9fbec18Smcpowers
177f9fbec18Smcpowers /* Fast multiplication for polynomials over a 163-bit curve. Assumes
178f9fbec18Smcpowers * reduction polynomial with terms {163, 7, 6, 3, 0}. */
179f9fbec18Smcpowers mp_err
ec_GF2m_163_mul(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)180f9fbec18Smcpowers ec_GF2m_163_mul(const mp_int *a, const mp_int *b, mp_int *r,
181f9fbec18Smcpowers const GFMethod *meth)
182f9fbec18Smcpowers {
183f9fbec18Smcpowers mp_err res = MP_OKAY;
184f9fbec18Smcpowers mp_digit a2 = 0, a1 = 0, a0, b2 = 0, b1 = 0, b0;
185f9fbec18Smcpowers
186f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
187f9fbec18Smcpowers mp_digit a5 = 0, a4 = 0, a3 = 0, b5 = 0, b4 = 0, b3 = 0;
188f9fbec18Smcpowers mp_digit rm[6];
189f9fbec18Smcpowers #endif
190f9fbec18Smcpowers
191f9fbec18Smcpowers if (a == b) {
192f9fbec18Smcpowers return ec_GF2m_163_sqr(a, r, meth);
193f9fbec18Smcpowers } else {
194f9fbec18Smcpowers switch (MP_USED(a)) {
195f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
196f9fbec18Smcpowers case 6:
197f9fbec18Smcpowers a5 = MP_DIGIT(a, 5);
19838a641c5SToomas Soome /* FALLTHROUGH */
199f9fbec18Smcpowers case 5:
200f9fbec18Smcpowers a4 = MP_DIGIT(a, 4);
20138a641c5SToomas Soome /* FALLTHROUGH */
202f9fbec18Smcpowers case 4:
203f9fbec18Smcpowers a3 = MP_DIGIT(a, 3);
204f9fbec18Smcpowers #endif
20538a641c5SToomas Soome /* FALLTHROUGH */
206f9fbec18Smcpowers case 3:
207f9fbec18Smcpowers a2 = MP_DIGIT(a, 2);
20838a641c5SToomas Soome /* FALLTHROUGH */
209f9fbec18Smcpowers case 2:
210f9fbec18Smcpowers a1 = MP_DIGIT(a, 1);
21138a641c5SToomas Soome /* FALLTHROUGH */
212f9fbec18Smcpowers default:
213f9fbec18Smcpowers a0 = MP_DIGIT(a, 0);
214f9fbec18Smcpowers }
215f9fbec18Smcpowers switch (MP_USED(b)) {
216f9fbec18Smcpowers #ifdef ECL_THIRTY_TWO_BIT
217f9fbec18Smcpowers case 6:
218f9fbec18Smcpowers b5 = MP_DIGIT(b, 5);
21938a641c5SToomas Soome /* FALLTHROUGH */
220f9fbec18Smcpowers case 5:
221f9fbec18Smcpowers b4 = MP_DIGIT(b, 4);
22238a641c5SToomas Soome /* FALLTHROUGH */
223f9fbec18Smcpowers case 4:
224f9fbec18Smcpowers b3 = MP_DIGIT(b, 3);
225f9fbec18Smcpowers #endif
22638a641c5SToomas Soome /* FALLTHROUGH */
227f9fbec18Smcpowers case 3:
228f9fbec18Smcpowers b2 = MP_DIGIT(b, 2);
22938a641c5SToomas Soome /* FALLTHROUGH */
230f9fbec18Smcpowers case 2:
231f9fbec18Smcpowers b1 = MP_DIGIT(b, 1);
23238a641c5SToomas Soome /* FALLTHROUGH */
233f9fbec18Smcpowers default:
234f9fbec18Smcpowers b0 = MP_DIGIT(b, 0);
235f9fbec18Smcpowers }
236f9fbec18Smcpowers #ifdef ECL_SIXTY_FOUR_BIT
237f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 6));
238f9fbec18Smcpowers s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0);
239f9fbec18Smcpowers MP_USED(r) = 6;
240f9fbec18Smcpowers s_mp_clamp(r);
241f9fbec18Smcpowers #else
242f9fbec18Smcpowers MP_CHECKOK(s_mp_pad(r, 12));
243f9fbec18Smcpowers s_bmul_3x3(MP_DIGITS(r) + 6, a5, a4, a3, b5, b4, b3);
244f9fbec18Smcpowers s_bmul_3x3(MP_DIGITS(r), a2, a1, a0, b2, b1, b0);
245f9fbec18Smcpowers s_bmul_3x3(rm, a5 ^ a2, a4 ^ a1, a3 ^ a0, b5 ^ b2, b4 ^ b1,
246f9fbec18Smcpowers b3 ^ b0);
247f9fbec18Smcpowers rm[5] ^= MP_DIGIT(r, 5) ^ MP_DIGIT(r, 11);
248f9fbec18Smcpowers rm[4] ^= MP_DIGIT(r, 4) ^ MP_DIGIT(r, 10);
249f9fbec18Smcpowers rm[3] ^= MP_DIGIT(r, 3) ^ MP_DIGIT(r, 9);
250f9fbec18Smcpowers rm[2] ^= MP_DIGIT(r, 2) ^ MP_DIGIT(r, 8);
251f9fbec18Smcpowers rm[1] ^= MP_DIGIT(r, 1) ^ MP_DIGIT(r, 7);
252f9fbec18Smcpowers rm[0] ^= MP_DIGIT(r, 0) ^ MP_DIGIT(r, 6);
253f9fbec18Smcpowers MP_DIGIT(r, 8) ^= rm[5];
254f9fbec18Smcpowers MP_DIGIT(r, 7) ^= rm[4];
255f9fbec18Smcpowers MP_DIGIT(r, 6) ^= rm[3];
256f9fbec18Smcpowers MP_DIGIT(r, 5) ^= rm[2];
257f9fbec18Smcpowers MP_DIGIT(r, 4) ^= rm[1];
258f9fbec18Smcpowers MP_DIGIT(r, 3) ^= rm[0];
259f9fbec18Smcpowers MP_USED(r) = 12;
260f9fbec18Smcpowers s_mp_clamp(r);
261f9fbec18Smcpowers #endif
262f9fbec18Smcpowers return ec_GF2m_163_mod(r, r, meth);
263f9fbec18Smcpowers }
264f9fbec18Smcpowers
265f9fbec18Smcpowers CLEANUP:
266f9fbec18Smcpowers return res;
267f9fbec18Smcpowers }
268f9fbec18Smcpowers
269f9fbec18Smcpowers /* Wire in fast field arithmetic for 163-bit curves. */
270f9fbec18Smcpowers mp_err
ec_group_set_gf2m163(ECGroup * group,ECCurveName name)271f9fbec18Smcpowers ec_group_set_gf2m163(ECGroup *group, ECCurveName name)
272f9fbec18Smcpowers {
273f9fbec18Smcpowers group->meth->field_mod = &ec_GF2m_163_mod;
274f9fbec18Smcpowers group->meth->field_mul = &ec_GF2m_163_mul;
275f9fbec18Smcpowers group->meth->field_sqr = &ec_GF2m_163_sqr;
276f9fbec18Smcpowers return MP_OKAY;
277f9fbec18Smcpowers }
278