← Back to branch summary

~ubuntu-branches/ubuntu/precise/kompozer/precise

« back to all changes in this revision

Viewing changes to mozilla/security/nss/lib/freebl/ecl/ecp_224.c

  • Committer: Bazaar Package Importer
  • Author(s): Anthony Yarusso
  • Date: 2007-08-27 01:11:03 UTC
  • Revision ID: james.westby@ubuntu.com-20070827011103-2jgf4s6532gqu2ka
Tags: upstream-0.7.10
Import upstream version 0.7.10

Show diffs side-by-side

added added

removed removed

Lines of Context:
mozilla/security/nss/lib/freebl/ecl/ecp_224.c
 
1
/* 
 
2
 * Version: MPL 1.1/GPL 2.0/LGPL 2.1
 
3
 *
 
4
 * The contents of this file are subject to the Mozilla Public License Version
 
5
 * 1.1 (the "License"); you may not use this file except in compliance with
 
6
 * the License. You may obtain a copy of the License at
 
7
 * http://www.mozilla.org/MPL/
 
8
 *
 
9
 * Software distributed under the License is distributed on an "AS IS" basis,
 
10
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 
11
 * for the specific language governing rights and limitations under the
 
12
 * License.
 
13
 *
 
14
 * The Original Code is the elliptic curve math library for prime
 
15
 * field curves.
 
16
 *
 
17
 * The Initial Developer of the Original Code is Sun Microsystems, Inc.
 
18
 * Portions created by Sun Microsystems, Inc. are Copyright (C) 2003
 
19
 * Sun Microsystems, Inc. All Rights Reserved.
 
20
 *
 
21
 * Contributor(s):
 
22
 *      Douglas Stebila <douglas@stebila.ca>, Sun Microsystems Laboratories
 
23
 *
 
24
 * Alternatively, the contents of this file may be used under the terms of
 
25
 * either the GNU General Public License Version 2 or later (the "GPL"), or
 
26
 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
 
27
 * in which case the provisions of the GPL or the LGPL are applicable instead
 
28
 * of those above. If you wish to allow use of your version of this file only
 
29
 * under the terms of either the GPL or the LGPL, and not to allow others to
 
30
 * use your version of this file under the terms of the MPL, indicate your
 
31
 * decision by deleting the provisions above and replace them with the notice
 
32
 * and other provisions required by the GPL or the LGPL. If you do not delete
 
33
 * the provisions above, a recipient may use your version of this file under
 
34
 * the terms of any one of the MPL, the GPL or the LGPL.
 
35
 *
 
36
 */
 
37
 
 
38
#include "ecp.h"
 
39
#include "mpi.h"
 
40
#include "mplogic.h"
 
41
#include "mpi-priv.h"
 
42
#include <stdlib.h>
 
43
 
 
44
/* Fast modular reduction for p224 = 2^224 - 2^96 + 1.  a can be r. Uses
 
45
 * algorithm 7 from Brown, Hankerson, Lopez, Menezes. Software
 
46
 * Implementation of the NIST Elliptic Curves over Prime Fields. */
 
47
mp_err
 
48
ec_GFp_nistp224_mod(const mp_int *a, mp_int *r, const GFMethod *meth)
 
49
{
 
50
        mp_err res = MP_OKAY;
 
51
        mp_size a_used = MP_USED(a);
 
52
 
 
53
        /* s is a statically-allocated mp_int of exactly the size we need */
 
54
        mp_int s;
 
55
 
 
56
#ifdef ECL_THIRTY_TWO_BIT
 
57
        mp_digit sa[8];
 
58
        mp_digit a13 = 0, a12 = 0, a11 = 0, a10, a9 = 0, a8, a7;
 
59
 
 
60
        MP_SIGN(&s) = MP_ZPOS;
 
61
        MP_ALLOC(&s) = 8;
 
62
        MP_USED(&s) = 7;
 
63
        MP_DIGITS(&s) = sa;
 
64
#else
 
65
        mp_digit sa[4];
 
66
        mp_digit a6 = 0, a5 = 0, a4 = 0, a3 = 0;
 
67
 
 
68
        MP_SIGN(&s) = MP_ZPOS;
 
69
        MP_ALLOC(&s) = 4;
 
70
        MP_USED(&s) = 4;
 
71
        MP_DIGITS(&s) = sa;
 
72
#endif
 
73
 
 
74
        /* reduction not needed if a is not larger than field size */
 
75
#ifdef ECL_THIRTY_TWO_BIT
 
76
        if (a_used < 8) {
 
77
#else
 
78
        if (a_used < 4) {
 
79
#endif
 
80
                return mp_copy(a, r);
 
81
        }
 
82
#ifdef ECL_THIRTY_TWO_BIT
 
83
        /* for polynomials larger than twice the field size, use regular
 
84
         * reduction */
 
85
        if (a_used > 14) {
 
86
                MP_CHECKOK(mp_mod(a, &meth->irr, r));
 
87
        } else {
 
88
                /* copy out upper words of a */
 
89
                switch (a_used) {
 
90
                case 14:
 
91
                        a13 = MP_DIGIT(a, 13);
 
92
                case 13:
 
93
                        a12 = MP_DIGIT(a, 12);
 
94
                case 12:
 
95
                        a11 = MP_DIGIT(a, 11);
 
96
                case 11:
 
97
                        a10 = MP_DIGIT(a, 10);
 
98
                case 10:
 
99
                        a9 = MP_DIGIT(a, 9);
 
100
                case 9:
 
101
                        a8 = MP_DIGIT(a, 8);
 
102
                case 8:
 
103
                        a7 = MP_DIGIT(a, 7);
 
104
                }
 
105
                /* set the lower words of r */
 
106
                if (a != r) {
 
107
                        MP_CHECKOK(s_mp_pad(r, 8));
 
108
                        MP_DIGIT(r, 6) = MP_DIGIT(a, 6);
 
109
                        MP_DIGIT(r, 5) = MP_DIGIT(a, 5);
 
110
                        MP_DIGIT(r, 4) = MP_DIGIT(a, 4);
 
111
                        MP_DIGIT(r, 3) = MP_DIGIT(a, 3);
 
112
                        MP_DIGIT(r, 2) = MP_DIGIT(a, 2);
 
113
                        MP_DIGIT(r, 1) = MP_DIGIT(a, 1);
 
114
                        MP_DIGIT(r, 0) = MP_DIGIT(a, 0);
 
115
                }
 
116
                MP_USED(r) = 7;
 
117
                switch (a_used) {
 
118
                case 14:
 
119
                case 13:
 
120
                case 12:
 
121
                case 11:
 
122
                        sa[6] = a10;
 
123
                case 10:
 
124
                        sa[5] = a9;
 
125
                case 9:
 
126
                        sa[4] = a8;
 
127
                case 8:
 
128
                        sa[3] = a7;
 
129
                        sa[2] = sa[1] = sa[0] = 0;
 
130
                        MP_USED(&s) = a_used - 4;
 
131
                        if (MP_USED(&s) > 7)
 
132
                                MP_USED(&s) = 7;
 
133
                        MP_CHECKOK(mp_add(r, &s, r));
 
134
                }
 
135
                switch (a_used) {
 
136
                case 14:
 
137
                        sa[5] = a13;
 
138
                case 13:
 
139
                        sa[4] = a12;
 
140
                case 12:
 
141
                        sa[3] = a11;
 
142
                        sa[2] = sa[1] = sa[0] = 0;
 
143
                        MP_USED(&s) = a_used - 8;
 
144
                        MP_CHECKOK(mp_add(r, &s, r));
 
145
                }
 
146
                switch (a_used) {
 
147
                case 14:
 
148
                        sa[6] = a13;
 
149
                case 13:
 
150
                        sa[5] = a12;
 
151
                case 12:
 
152
                        sa[4] = a11;
 
153
                case 11:
 
154
                        sa[3] = a10;
 
155
                case 10:
 
156
                        sa[2] = a9;
 
157
                case 9:
 
158
                        sa[1] = a8;
 
159
                case 8:
 
160
                        sa[0] = a7;
 
161
                        MP_USED(&s) = a_used - 7;
 
162
                        MP_CHECKOK(mp_sub(r, &s, r));
 
163
                }
 
164
                switch (a_used) {
 
165
                case 14:
 
166
                        sa[2] = a13;
 
167
                case 13:
 
168
                        sa[1] = a12;
 
169
                case 12:
 
170
                        sa[0] = a11;
 
171
                        MP_USED(&s) = a_used - 11;
 
172
                        MP_CHECKOK(mp_sub(r, &s, r));
 
173
                }
 
174
                /* there might be 1 or 2 bits left to reduce; use regular
 
175
                 * reduction for this */
 
176
                MP_CHECKOK(mp_mod(r, &meth->irr, r));
 
177
        }
 
178
#else
 
179
        /* for polynomials larger than twice the field size, use regular
 
180
         * reduction */
 
181
        if (a_used > 7) {
 
182
                MP_CHECKOK(mp_mod(a, &meth->irr, r));
 
183
        } else {
 
184
                /* copy out upper words of a */
 
185
                switch (a_used) {
 
186
                case 7:
 
187
                        a6 = MP_DIGIT(a, 6);
 
188
                case 6:
 
189
                        a5 = MP_DIGIT(a, 5);
 
190
                case 5:
 
191
                        a4 = MP_DIGIT(a, 4);
 
192
                case 4:
 
193
                        a3 = MP_DIGIT(a, 3) >> 32;
 
194
                }
 
195
                /* set the lower words of r */
 
196
                if (a != r) {
 
197
                        MP_CHECKOK(s_mp_pad(r, 5));
 
198
                        MP_DIGIT(r, 3) = MP_DIGIT(a, 3) & 0xFFFFFFFF;
 
199
                        MP_DIGIT(r, 2) = MP_DIGIT(a, 2);
 
200
                        MP_DIGIT(r, 1) = MP_DIGIT(a, 1);
 
201
                        MP_DIGIT(r, 0) = MP_DIGIT(a, 0);
 
202
                } else {
 
203
                        MP_DIGIT(r, 3) &= 0xFFFFFFFF;
 
204
                }
 
205
                MP_USED(r) = 4;
 
206
                switch (a_used) {
 
207
                case 7:
 
208
                case 6:
 
209
                        sa[3] = a5 & 0xFFFFFFFF;
 
210
                case 5:
 
211
                        sa[2] = a4;
 
212
                case 4:
 
213
                        sa[1] = a3 << 32;
 
214
                        sa[0] = 0;
 
215
                        MP_USED(&s) = a_used - 2;
 
216
                        if (MP_USED(&s) == 5)
 
217
                                MP_USED(&s) = 4;
 
218
                        MP_CHECKOK(mp_add(r, &s, r));
 
219
                }
 
220
                switch (a_used) {
 
221
                case 7:
 
222
                        sa[2] = a6;
 
223
                case 6:
 
224
                        sa[1] = (a5 >> 32) << 32;
 
225
                        sa[0] = 0;
 
226
                        MP_USED(&s) = a_used - 4;
 
227
                        MP_CHECKOK(mp_add(r, &s, r));
 
228
                }
 
229
                sa[2] = sa[1] = sa[0] = 0;
 
230
                switch (a_used) {
 
231
                case 7:
 
232
                        sa[3] = a6 >> 32;
 
233
                        sa[2] = a6 << 32;
 
234
                case 6:
 
235
                        sa[2] |= a5 >> 32;
 
236
                        sa[1] = a5 << 32;
 
237
                case 5:
 
238
                        sa[1] |= a4 >> 32;
 
239
                        sa[0] = a4 << 32;
 
240
                case 4:
 
241
                        sa[0] |= a3;
 
242
                        MP_USED(&s) = a_used - 3;
 
243
                        MP_CHECKOK(mp_sub(r, &s, r));
 
244
                }
 
245
                sa[0] = 0;
 
246
                switch (a_used) {
 
247
                case 7:
 
248
                        sa[1] = a6 >> 32;
 
249
                        sa[0] = a6 << 32;
 
250
                case 6:
 
251
                        sa[0] |= a5 >> 32;
 
252
                        MP_USED(&s) = a_used - 5;
 
253
                        MP_CHECKOK(mp_sub(r, &s, r));
 
254
                }
 
255
                /* there might be 1 or 2 bits left to reduce; use regular
 
256
                 * reduction for this */
 
257
                MP_CHECKOK(mp_mod(r, &meth->irr, r));
 
258
        }
 
259
#endif
 
260
 
 
261
  CLEANUP:
 
262
        return res;
 
263
}
 
264
 
 
265
/* Compute the square of polynomial a, reduce modulo p224. Store the
 
266
 * result in r.  r could be a.  Uses optimized modular reduction for p224. 
 
267
 */
 
268
mp_err
 
269
ec_GFp_nistp224_sqr(const mp_int *a, mp_int *r, const GFMethod *meth)
 
270
{
 
271
        mp_err res = MP_OKAY;
 
272
 
 
273
        MP_CHECKOK(mp_sqr(a, r));
 
274
        MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth));
 
275
  CLEANUP:
 
276
        return res;
 
277
}
 
278
 
 
279
/* Compute the product of two polynomials a and b, reduce modulo p224.
 
280
 * Store the result in r.  r could be a or b; a could be b.  Uses
 
281
 * optimized modular reduction for p224. */
 
282
mp_err
 
283
ec_GFp_nistp224_mul(const mp_int *a, const mp_int *b, mp_int *r,
 
284
                                        const GFMethod *meth)
 
285
{
 
286
        mp_err res = MP_OKAY;
 
287
 
 
288
        MP_CHECKOK(mp_mul(a, b, r));
 
289
        MP_CHECKOK(ec_GFp_nistp224_mod(r, r, meth));
 
290
  CLEANUP:
 
291
        return res;
 
292
}
 
293
 
 
294
/* Wire in fast field arithmetic and precomputation of base point for
 
295
 * named curves. */
 
296
mp_err
 
297
ec_group_set_gfp224(ECGroup *group, ECCurveName name)
 
298
{
 
299
        if (name == ECCurve_NIST_P224) {
 
300
                group->meth->field_mod = &ec_GFp_nistp224_mod;
 
301
                group->meth->field_mul = &ec_GFp_nistp224_mul;
 
302
                group->meth->field_sqr = &ec_GFp_nistp224_sqr;
 
303
        }
 
304
        return MP_OKAY;
 
305
}