1*c40a6cd7SToomas Soome /*
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.
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 * Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
24f9fbec18Smcpowers *
25f9fbec18Smcpowers * Alternatively, the contents of this file may be used under the terms of
26f9fbec18Smcpowers * either the GNU General Public License Version 2 or later (the "GPL"), or
27f9fbec18Smcpowers * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
28f9fbec18Smcpowers * in which case the provisions of the GPL or the LGPL are applicable instead
29f9fbec18Smcpowers * of those above. If you wish to allow use of your version of this file only
30f9fbec18Smcpowers * under the terms of either the GPL or the LGPL, and not to allow others to
31f9fbec18Smcpowers * use your version of this file under the terms of the MPL, indicate your
32f9fbec18Smcpowers * decision by deleting the provisions above and replace them with the notice
33f9fbec18Smcpowers * and other provisions required by the GPL or the LGPL. If you do not delete
34f9fbec18Smcpowers * the provisions above, a recipient may use your version of this file under
35f9fbec18Smcpowers * the terms of any one of the MPL, the GPL or the LGPL.
36f9fbec18Smcpowers *
37f9fbec18Smcpowers * ***** END LICENSE BLOCK ***** */
38f9fbec18Smcpowers /*
39f9fbec18Smcpowers * Copyright 2007 Sun Microsystems, Inc. All rights reserved.
40f9fbec18Smcpowers * Use is subject to license terms.
41f9fbec18Smcpowers *
42f9fbec18Smcpowers * Sun elects to use this software under the MPL license.
43f9fbec18Smcpowers */
44f9fbec18Smcpowers
45f9fbec18Smcpowers /* Uses Montgomery reduction for field arithmetic. See mpi/mpmontg.c for
46f9fbec18Smcpowers * code implementation. */
47f9fbec18Smcpowers
48f9fbec18Smcpowers #include "mpi.h"
49f9fbec18Smcpowers #include "mplogic.h"
50f9fbec18Smcpowers #include "mpi-priv.h"
51f9fbec18Smcpowers #include "ecl-priv.h"
52f9fbec18Smcpowers #include "ecp.h"
53f9fbec18Smcpowers #ifndef _KERNEL
54f9fbec18Smcpowers #include <stdlib.h>
55f9fbec18Smcpowers #include <stdio.h>
56f9fbec18Smcpowers #endif
57f9fbec18Smcpowers
58f9fbec18Smcpowers /* Construct a generic GFMethod for arithmetic over prime fields with
59f9fbec18Smcpowers * irreducible irr. */
60f9fbec18Smcpowers GFMethod *
GFMethod_consGFp_mont(const mp_int * irr)61f9fbec18Smcpowers GFMethod_consGFp_mont(const mp_int *irr)
62f9fbec18Smcpowers {
63f9fbec18Smcpowers mp_err res = MP_OKAY;
64f9fbec18Smcpowers int i;
65f9fbec18Smcpowers GFMethod *meth = NULL;
66f9fbec18Smcpowers mp_mont_modulus *mmm;
67f9fbec18Smcpowers
68f9fbec18Smcpowers meth = GFMethod_consGFp(irr);
69f9fbec18Smcpowers if (meth == NULL)
70f9fbec18Smcpowers return NULL;
71f9fbec18Smcpowers
72f9fbec18Smcpowers #ifdef _KERNEL
73f9fbec18Smcpowers mmm = (mp_mont_modulus *) kmem_alloc(sizeof(mp_mont_modulus),
74f9fbec18Smcpowers FLAG(irr));
75f9fbec18Smcpowers #else
76f9fbec18Smcpowers mmm = (mp_mont_modulus *) malloc(sizeof(mp_mont_modulus));
77f9fbec18Smcpowers #endif
78f9fbec18Smcpowers if (mmm == NULL) {
79f9fbec18Smcpowers res = MP_MEM;
80f9fbec18Smcpowers goto CLEANUP;
81f9fbec18Smcpowers }
82f9fbec18Smcpowers
83f9fbec18Smcpowers meth->field_mul = &ec_GFp_mul_mont;
84f9fbec18Smcpowers meth->field_sqr = &ec_GFp_sqr_mont;
85f9fbec18Smcpowers meth->field_div = &ec_GFp_div_mont;
86f9fbec18Smcpowers meth->field_enc = &ec_GFp_enc_mont;
87f9fbec18Smcpowers meth->field_dec = &ec_GFp_dec_mont;
88f9fbec18Smcpowers meth->extra1 = mmm;
89f9fbec18Smcpowers meth->extra2 = NULL;
90f9fbec18Smcpowers meth->extra_free = &ec_GFp_extra_free_mont;
91f9fbec18Smcpowers
92f9fbec18Smcpowers mmm->N = meth->irr;
93f9fbec18Smcpowers i = mpl_significant_bits(&meth->irr);
94f9fbec18Smcpowers i += MP_DIGIT_BIT - 1;
95f9fbec18Smcpowers mmm->b = i - i % MP_DIGIT_BIT;
96f9fbec18Smcpowers mmm->n0prime = 0 - s_mp_invmod_radix(MP_DIGIT(&meth->irr, 0));
97f9fbec18Smcpowers
98f9fbec18Smcpowers CLEANUP:
99f9fbec18Smcpowers if (res != MP_OKAY) {
100f9fbec18Smcpowers GFMethod_free(meth);
101f9fbec18Smcpowers return NULL;
102f9fbec18Smcpowers }
103f9fbec18Smcpowers return meth;
104f9fbec18Smcpowers }
105f9fbec18Smcpowers
106f9fbec18Smcpowers /* Wrapper functions for generic prime field arithmetic. */
107f9fbec18Smcpowers
108f9fbec18Smcpowers /* Field multiplication using Montgomery reduction. */
109f9fbec18Smcpowers mp_err
ec_GFp_mul_mont(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)110f9fbec18Smcpowers ec_GFp_mul_mont(const mp_int *a, const mp_int *b, mp_int *r,
111f9fbec18Smcpowers const GFMethod *meth)
112f9fbec18Smcpowers {
113f9fbec18Smcpowers mp_err res = MP_OKAY;
114f9fbec18Smcpowers
115f9fbec18Smcpowers #ifdef MP_MONT_USE_MP_MUL
116f9fbec18Smcpowers /* if MP_MONT_USE_MP_MUL is defined, then the function s_mp_mul_mont
117*c40a6cd7SToomas Soome * is not implemented and we have to use mp_mul and s_mp_redc directly
118f9fbec18Smcpowers */
119f9fbec18Smcpowers MP_CHECKOK(mp_mul(a, b, r));
120f9fbec18Smcpowers MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
121f9fbec18Smcpowers #else
122f9fbec18Smcpowers mp_int s;
123f9fbec18Smcpowers
124f9fbec18Smcpowers MP_DIGITS(&s) = 0;
125f9fbec18Smcpowers /* s_mp_mul_mont doesn't allow source and destination to be the same */
126f9fbec18Smcpowers if ((a == r) || (b == r)) {
127f9fbec18Smcpowers MP_CHECKOK(mp_init(&s, FLAG(a)));
128f9fbec18Smcpowers MP_CHECKOK(s_mp_mul_mont
129f9fbec18Smcpowers (a, b, &s, (mp_mont_modulus *) meth->extra1));
130f9fbec18Smcpowers MP_CHECKOK(mp_copy(&s, r));
131f9fbec18Smcpowers mp_clear(&s);
132f9fbec18Smcpowers } else {
133f9fbec18Smcpowers return s_mp_mul_mont(a, b, r, (mp_mont_modulus *) meth->extra1);
134f9fbec18Smcpowers }
135f9fbec18Smcpowers #endif
136f9fbec18Smcpowers CLEANUP:
137f9fbec18Smcpowers return res;
138f9fbec18Smcpowers }
139f9fbec18Smcpowers
140f9fbec18Smcpowers /* Field squaring using Montgomery reduction. */
141f9fbec18Smcpowers mp_err
ec_GFp_sqr_mont(const mp_int * a,mp_int * r,const GFMethod * meth)142f9fbec18Smcpowers ec_GFp_sqr_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
143f9fbec18Smcpowers {
144f9fbec18Smcpowers return ec_GFp_mul_mont(a, a, r, meth);
145f9fbec18Smcpowers }
146f9fbec18Smcpowers
147f9fbec18Smcpowers /* Field division using Montgomery reduction. */
148f9fbec18Smcpowers mp_err
ec_GFp_div_mont(const mp_int * a,const mp_int * b,mp_int * r,const GFMethod * meth)149f9fbec18Smcpowers ec_GFp_div_mont(const mp_int *a, const mp_int *b, mp_int *r,
150f9fbec18Smcpowers const GFMethod *meth)
151f9fbec18Smcpowers {
152f9fbec18Smcpowers mp_err res = MP_OKAY;
153f9fbec18Smcpowers
154*c40a6cd7SToomas Soome /* if A=aZ represents a encoded in montgomery coordinates with Z and #
155f9fbec18Smcpowers * and \ respectively represent multiplication and division in
156f9fbec18Smcpowers * montgomery coordinates, then A\B = (a/b)Z = (A/B)Z and Binv =
157f9fbec18Smcpowers * (1/b)Z = (1/B)(Z^2) where B # Binv = Z */
158f9fbec18Smcpowers MP_CHECKOK(ec_GFp_div(a, b, r, meth));
159f9fbec18Smcpowers MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
160f9fbec18Smcpowers if (a == NULL) {
161f9fbec18Smcpowers MP_CHECKOK(ec_GFp_enc_mont(r, r, meth));
162f9fbec18Smcpowers }
163f9fbec18Smcpowers CLEANUP:
164f9fbec18Smcpowers return res;
165f9fbec18Smcpowers }
166f9fbec18Smcpowers
167f9fbec18Smcpowers /* Encode a field element in Montgomery form. See s_mp_to_mont in
168f9fbec18Smcpowers * mpi/mpmontg.c */
169f9fbec18Smcpowers mp_err
ec_GFp_enc_mont(const mp_int * a,mp_int * r,const GFMethod * meth)170f9fbec18Smcpowers ec_GFp_enc_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
171f9fbec18Smcpowers {
172f9fbec18Smcpowers mp_mont_modulus *mmm;
173f9fbec18Smcpowers mp_err res = MP_OKAY;
174f9fbec18Smcpowers
175f9fbec18Smcpowers mmm = (mp_mont_modulus *) meth->extra1;
176f9fbec18Smcpowers MP_CHECKOK(mpl_lsh(a, r, mmm->b));
177f9fbec18Smcpowers MP_CHECKOK(mp_mod(r, &mmm->N, r));
178f9fbec18Smcpowers CLEANUP:
179f9fbec18Smcpowers return res;
180f9fbec18Smcpowers }
181f9fbec18Smcpowers
182f9fbec18Smcpowers /* Decode a field element from Montgomery form. */
183f9fbec18Smcpowers mp_err
ec_GFp_dec_mont(const mp_int * a,mp_int * r,const GFMethod * meth)184f9fbec18Smcpowers ec_GFp_dec_mont(const mp_int *a, mp_int *r, const GFMethod *meth)
185f9fbec18Smcpowers {
186f9fbec18Smcpowers mp_err res = MP_OKAY;
187f9fbec18Smcpowers
188f9fbec18Smcpowers if (a != r) {
189f9fbec18Smcpowers MP_CHECKOK(mp_copy(a, r));
190f9fbec18Smcpowers }
191f9fbec18Smcpowers MP_CHECKOK(s_mp_redc(r, (mp_mont_modulus *) meth->extra1));
192f9fbec18Smcpowers CLEANUP:
193f9fbec18Smcpowers return res;
194f9fbec18Smcpowers }
195f9fbec18Smcpowers
196f9fbec18Smcpowers /* Free the memory allocated to the extra fields of Montgomery GFMethod
197f9fbec18Smcpowers * object. */
198f9fbec18Smcpowers void
ec_GFp_extra_free_mont(GFMethod * meth)199f9fbec18Smcpowers ec_GFp_extra_free_mont(GFMethod *meth)
200f9fbec18Smcpowers {
201f9fbec18Smcpowers if (meth->extra1 != NULL) {
202f9fbec18Smcpowers #ifdef _KERNEL
203f9fbec18Smcpowers kmem_free(meth->extra1, sizeof(mp_mont_modulus));
204f9fbec18Smcpowers #else
205f9fbec18Smcpowers free(meth->extra1);
206f9fbec18Smcpowers #endif
207f9fbec18Smcpowers meth->extra1 = NULL;
208f9fbec18Smcpowers }
209f9fbec18Smcpowers }
210