1 /* *********************************************************************
2 *
3 * Sun elects to have this file available under and governed by the
4 * Mozilla Public License Version 1.1 ("MPL") (see
5 * http://www.mozilla.org/MPL/ for full license text). For the avoidance
6 * of doubt and subject to the following, Sun also elects to allow
7 * licensees to use this file under the MPL, the GNU General Public
8 * License version 2 only or the Lesser General Public License version
9 * 2.1 only. Any references to the "GNU General Public License version 2
10 * or later" or "GPL" in the following shall be construed to mean the
11 * GNU General Public License version 2 only. Any references to the "GNU
12 * Lesser General Public License version 2.1 or later" or "LGPL" in the
13 * following shall be construed to mean the GNU Lesser General Public
14 * License version 2.1 only. However, the following notice accompanied
15 * the original version of this file:
16 *
17 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
18 *
19 * The contents of this file are subject to the Mozilla Public License Version
20 * 1.1 (the "License"); you may not use this file except in compliance with
21 * the License. You may obtain a copy of the License at
22 * http://www.mozilla.org/MPL/
23 *
24 * Software distributed under the License is distributed on an "AS IS" basis,
25 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
26 * for the specific language governing rights and limitations under the
27 * License.
28 *
29 * The Original Code is the elliptic curve math library for prime field curves.
30 *
31 * The Initial Developer of the Original Code is
32 * Sun Microsystems, Inc.
33 * Portions created by the Initial Developer are Copyright (C) 2003
34 * the Initial Developer. All Rights Reserved.
35 *
36 * Contributor(s):
37 * Douglas Stebila <douglas@stebila.ca>
38 *
39 * Alternatively, the contents of this file may be used under the terms of
40 * either the GNU General Public License Version 2 or later (the "GPL"), or
41 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
42 * in which case the provisions of the GPL or the LGPL are applicable instead
43 * of those above. If you wish to allow use of your version of this file only
44 * under the terms of either the GPL or the LGPL, and not to allow others to
45 * use your version of this file under the terms of the MPL, indicate your
46 * decision by deleting the provisions above and replace them with the notice
47 * and other provisions required by the GPL or the LGPL. If you do not delete
48 * the provisions above, a recipient may use your version of this file under
49 * the terms of any one of the MPL, the GPL or the LGPL.
50 *
51 *********************************************************************** */
52 /*
53 * Copyright (c) 2007, 2010, Oracle and/or its affiliates. All rights reserved.
54 * Use is subject to license terms.
55 */
56
57 #include "ecp.h"
58 #include "mpi.h"
59 #include "mplogic.h"
60 #include "mpi-priv.h"
61 #ifndef _KERNEL
62 #include <stdlib.h>
63 #endif
64
65 #define ECP521_DIGITS ECL_CURVE_DIGITS(521)
66
67 /* Fast modular reduction for p521 = 2^521 - 1. a can be r. Uses
68 * algorithm 2.31 from Hankerson, Menezes, Vanstone. Guide to
69 * Elliptic Curve Cryptography. */
70 mp_err
71 ec_GFp_nistp521_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
72 {
73 mp_err res = MP_OKAY;
74 int a_bits = mpl_significant_bits(a);
75 unsigned int i;
76
77 /* m1, m2 are statically-allocated mp_int of exactly the size we need */
78 mp_int m1;
79
80 mp_digit s1[ECP521_DIGITS] = { 0 };
81
82 MP_SIGN(&m1) = MP_ZPOS;
83 MP_ALLOC(&m1) = ECP521_DIGITS;
84 MP_USED(&m1) = ECP521_DIGITS;
85 MP_DIGITS(&m1) = s1;
86
87 if (a_bits < 521) {
88 if (a==r) return MP_OKAY;
89 return mp_copy(a, r);
90 }
91 /* for polynomials larger than twice the field size or polynomials
92 * not using all words, use regular reduction */
93 if (a_bits > (521*2)) {
94 MP_CHECKOK(mp_mod(a, &meth->irr, r));
95 } else {
96 #define FIRST_DIGIT (ECP521_DIGITS-1)
97 for (i = FIRST_DIGIT; i < MP_USED(a)-1; i++) {
98 s1[i-FIRST_DIGIT] = (MP_DIGIT(a, i) >> 9)
99 | (MP_DIGIT(a, 1+i) << (MP_DIGIT_BIT-9));
100 }
101 s1[i-FIRST_DIGIT] = MP_DIGIT(a, i) >> 9;
102
103 if ( a != r ) {
104 MP_CHECKOK(s_mp_pad(r,ECP521_DIGITS));
105 for (i = 0; i < ECP521_DIGITS; i++) {
106 MP_DIGIT(r,i) = MP_DIGIT(a, i);
107 }
108 }
109 MP_USED(r) = ECP521_DIGITS;
110 MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
111
112 MP_CHECKOK(s_mp_add(r, &m1));
113 if (MP_DIGIT(r, FIRST_DIGIT) & 0x200) {
114 MP_CHECKOK(s_mp_add_d(r,1));
115 MP_DIGIT(r,FIRST_DIGIT) &= 0x1FF;
116 }
117 s_mp_clamp(r);
118 }
119
120 CLEANUP:
121 return res;
122 }
123
124 /* Compute the square of polynomial a, reduce modulo p521. Store the
125 * result in r. r could be a. Uses optimized modular reduction for p521.
126 */
127 mp_err
128 ec_GFp_nistp521_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
129 {
130 mp_err res = MP_OKAY;
131
132 MP_CHECKOK(mp_sqr(a, r));
133 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
134 CLEANUP:
135 return res;
136 }
137
138 /* Compute the product of two polynomials a and b, reduce modulo p521.
139 * Store the result in r. r could be a or b; a could be b. Uses
140 * optimized modular reduction for p521. */
141 mp_err
142 ec_GFp_nistp521_mul(const mp_int *a, const mp_int *b, mp_int *r,
143 const GFMethod *meth)
144 {
145 mp_err res = MP_OKAY;
146
147 MP_CHECKOK(mp_mul(a, b, r));
148 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
149 CLEANUP:
150 return res;
151 }
152
153 /* Divides two field elements. If a is NULL, then returns the inverse of
154 * b. */
155 mp_err
156 ec_GFp_nistp521_div(const mp_int *a, const mp_int *b, mp_int *r,
157 const GFMethod *meth)
158 {
159 mp_err res = MP_OKAY;
160 mp_int t;
161
162 /* If a is NULL, then return the inverse of b, otherwise return a/b. */
163 if (a == NULL) {
164 return mp_invmod(b, &meth->irr, r);
165 } else {
166 /* MPI doesn't support divmod, so we implement it using invmod and
167 * mulmod. */
168 MP_CHECKOK(mp_init(&t, FLAG(b)));
169 MP_CHECKOK(mp_invmod(b, &meth->irr, &t));
170 MP_CHECKOK(mp_mul(a, &t, r));
171 MP_CHECKOK(ec_GFp_nistp521_mod(r, r, meth));
172 CLEANUP:
173 mp_clear(&t);
174 return res;
175 }
176 }
177
178 /* Wire in fast field arithmetic and precomputation of base point for
179 * named curves. */
180 mp_err
181 ec_group_set_gfp521(ECGroup *group, ECCurveName name)
182 {
183 if (name == ECCurve_NIST_P521) {
184 group->meth->field_mod = &ec_GFp_nistp521_mod;
185 group->meth->field_mul = &ec_GFp_nistp521_mul;
186 group->meth->field_sqr = &ec_GFp_nistp521_sqr;
187 group->meth->field_div = &ec_GFp_nistp521_div;
188 }
189 return MP_OKAY;
190 }