← Back to branch summary

~ubuntu-branches/ubuntu/lucid/nss/lucid-security

« back to all changes in this revision

Viewing changes to nss/lib/freebl/ecl/ecp_jm.c

  • Committer: Package Import Robot
  • Author(s): Marc Deslauriers
  • Date: 2013-11-15 08:08:08 UTC
  • mfrom: (1.2.7)
  • Revision ID: package-import@ubuntu.com-20131115080808-dba1asgnjl9tc66s
Tags: 3.15.3-0ubuntu0.10.04.1
* SECURITY UPDATE: New upstream release to fix multiple security issues
  and add TLSv1.2 support.
  - CVE-2013-1739
  - CVE-2013-1741
  - CVE-2013-5605
  - CVE-2013-5606
* Adjusted packaging for 3.15.3:
  - debian/patches/*: refreshed.
  - debian/patches/01_dont_build_nspr.patch: removed, changed build
    options in debian/rules instead.
  - debian/libnss3-1d.symbols: added new symbols.
  - debian/rules: updated for new source layout.

Show diffs side-by-side

added added

removed removed

Lines of Context:
nss/lib/freebl/ecl/ecp_jm.c
 
1
/* This Source Code Form is subject to the terms of the Mozilla Public
 
2
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 
3
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
4
 
 
5
#include "ecp.h"
 
6
#include "ecl-priv.h"
 
7
#include "mplogic.h"
 
8
#include <stdlib.h>
 
9
 
 
10
#define MAX_SCRATCH 6
 
11
 
 
12
/* Computes R = 2P.  Elliptic curve points P and R can be identical.  Uses 
 
13
 * Modified Jacobian coordinates.
 
14
 *
 
15
 * Assumes input is already field-encoded using field_enc, and returns 
 
16
 * output that is still field-encoded.
 
17
 *
 
18
 */
 
19
mp_err
 
20
ec_GFp_pt_dbl_jm(const mp_int *px, const mp_int *py, const mp_int *pz,
 
21
                                 const mp_int *paz4, mp_int *rx, mp_int *ry, mp_int *rz,
 
22
                                 mp_int *raz4, mp_int scratch[], const ECGroup *group)
 
23
{
 
24
        mp_err res = MP_OKAY;
 
25
        mp_int *t0, *t1, *M, *S;
 
26
 
 
27
        t0 = &scratch[0];
 
28
        t1 = &scratch[1];
 
29
        M = &scratch[2];
 
30
        S = &scratch[3];
 
31
 
 
32
#if MAX_SCRATCH < 4
 
33
#error "Scratch array defined too small "
 
34
#endif
 
35
 
 
36
        /* Check for point at infinity */
 
37
        if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) {
 
38
                /* Set r = pt at infinity by setting rz = 0 */
 
39
 
 
40
                MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, rz));
 
41
                goto CLEANUP;
 
42
        }
 
43
 
 
44
        /* M = 3 (px^2) + a*(pz^4) */
 
45
        MP_CHECKOK(group->meth->field_sqr(px, t0, group->meth));
 
46
        MP_CHECKOK(group->meth->field_add(t0, t0, M, group->meth));
 
47
        MP_CHECKOK(group->meth->field_add(t0, M, t0, group->meth));
 
48
        MP_CHECKOK(group->meth->field_add(t0, paz4, M, group->meth));
 
49
 
 
50
        /* rz = 2 * py * pz */
 
51
        MP_CHECKOK(group->meth->field_mul(py, pz, S, group->meth));
 
52
        MP_CHECKOK(group->meth->field_add(S, S, rz, group->meth));
 
53
 
 
54
        /* t0 = 2y^2 , t1 = 8y^4 */
 
55
        MP_CHECKOK(group->meth->field_sqr(py, t0, group->meth));
 
56
        MP_CHECKOK(group->meth->field_add(t0, t0, t0, group->meth));
 
57
        MP_CHECKOK(group->meth->field_sqr(t0, t1, group->meth));
 
58
        MP_CHECKOK(group->meth->field_add(t1, t1, t1, group->meth));
 
59
 
 
60
        /* S = 4 * px * py^2 = 2 * px * t0 */
 
61
        MP_CHECKOK(group->meth->field_mul(px, t0, S, group->meth));
 
62
        MP_CHECKOK(group->meth->field_add(S, S, S, group->meth));
 
63
 
 
64
 
 
65
        /* rx = M^2 - 2S */
 
66
        MP_CHECKOK(group->meth->field_sqr(M, rx, group->meth));
 
67
        MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth));
 
68
        MP_CHECKOK(group->meth->field_sub(rx, S, rx, group->meth));
 
69
 
 
70
        /* ry = M * (S - rx) - t1 */
 
71
        MP_CHECKOK(group->meth->field_sub(S, rx, S, group->meth));
 
72
        MP_CHECKOK(group->meth->field_mul(S, M, ry, group->meth));
 
73
        MP_CHECKOK(group->meth->field_sub(ry, t1, ry, group->meth));
 
74
 
 
75
        /* ra*z^4 = 2*t1*(apz4) */
 
76
        MP_CHECKOK(group->meth->field_mul(paz4, t1, raz4, group->meth));
 
77
        MP_CHECKOK(group->meth->field_add(raz4, raz4, raz4, group->meth));
 
78
 
 
79
 
 
80
  CLEANUP:
 
81
        return res;
 
82
}
 
83
 
 
84
/* Computes R = P + Q where R is (rx, ry, rz), P is (px, py, pz) and Q is
 
85
 * (qx, qy, 1).  Elliptic curve points P, Q, and R can all be identical.
 
86
 * Uses mixed Modified_Jacobian-affine coordinates. Assumes input is
 
87
 * already field-encoded using field_enc, and returns output that is still
 
88
 * field-encoded. */
 
89
mp_err
 
90
ec_GFp_pt_add_jm_aff(const mp_int *px, const mp_int *py, const mp_int *pz,
 
91
                                         const mp_int *paz4, const mp_int *qx,
 
92
                                         const mp_int *qy, mp_int *rx, mp_int *ry, mp_int *rz,
 
93
                                         mp_int *raz4, mp_int scratch[], const ECGroup *group)
 
94
{
 
95
        mp_err res = MP_OKAY;
 
96
        mp_int *A, *B, *C, *D, *C2, *C3;
 
97
 
 
98
        A = &scratch[0];
 
99
        B = &scratch[1];
 
100
        C = &scratch[2];
 
101
        D = &scratch[3];
 
102
        C2 = &scratch[4];
 
103
        C3 = &scratch[5];
 
104
 
 
105
#if MAX_SCRATCH < 6
 
106
#error "Scratch array defined too small "
 
107
#endif
 
108
 
 
109
        /* If either P or Q is the point at infinity, then return the other
 
110
         * point */
 
111
        if (ec_GFp_pt_is_inf_jac(px, py, pz) == MP_YES) {
 
112
                MP_CHECKOK(ec_GFp_pt_aff2jac(qx, qy, rx, ry, rz, group));
 
113
                MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth));
 
114
                MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth));
 
115
                MP_CHECKOK(group->meth->
 
116
                                   field_mul(raz4, &group->curvea, raz4, group->meth));
 
117
                goto CLEANUP;
 
118
        }
 
119
        if (ec_GFp_pt_is_inf_aff(qx, qy) == MP_YES) {
 
120
                MP_CHECKOK(mp_copy(px, rx));
 
121
                MP_CHECKOK(mp_copy(py, ry));
 
122
                MP_CHECKOK(mp_copy(pz, rz));
 
123
                MP_CHECKOK(mp_copy(paz4, raz4));
 
124
                goto CLEANUP;
 
125
        }
 
126
 
 
127
        /* A = qx * pz^2, B = qy * pz^3 */
 
128
        MP_CHECKOK(group->meth->field_sqr(pz, A, group->meth));
 
129
        MP_CHECKOK(group->meth->field_mul(A, pz, B, group->meth));
 
130
        MP_CHECKOK(group->meth->field_mul(A, qx, A, group->meth));
 
131
        MP_CHECKOK(group->meth->field_mul(B, qy, B, group->meth));
 
132
 
 
133
        /* C = A - px, D = B - py */
 
134
        MP_CHECKOK(group->meth->field_sub(A, px, C, group->meth));
 
135
        MP_CHECKOK(group->meth->field_sub(B, py, D, group->meth));
 
136
 
 
137
        /* C2 = C^2, C3 = C^3 */
 
138
        MP_CHECKOK(group->meth->field_sqr(C, C2, group->meth));
 
139
        MP_CHECKOK(group->meth->field_mul(C, C2, C3, group->meth));
 
140
 
 
141
        /* rz = pz * C */
 
142
        MP_CHECKOK(group->meth->field_mul(pz, C, rz, group->meth));
 
143
 
 
144
        /* C = px * C^2 */
 
145
        MP_CHECKOK(group->meth->field_mul(px, C2, C, group->meth));
 
146
        /* A = D^2 */
 
147
        MP_CHECKOK(group->meth->field_sqr(D, A, group->meth));
 
148
 
 
149
        /* rx = D^2 - (C^3 + 2 * (px * C^2)) */
 
150
        MP_CHECKOK(group->meth->field_add(C, C, rx, group->meth));
 
151
        MP_CHECKOK(group->meth->field_add(C3, rx, rx, group->meth));
 
152
        MP_CHECKOK(group->meth->field_sub(A, rx, rx, group->meth));
 
153
 
 
154
        /* C3 = py * C^3 */
 
155
        MP_CHECKOK(group->meth->field_mul(py, C3, C3, group->meth));
 
156
 
 
157
        /* ry = D * (px * C^2 - rx) - py * C^3 */
 
158
        MP_CHECKOK(group->meth->field_sub(C, rx, ry, group->meth));
 
159
        MP_CHECKOK(group->meth->field_mul(D, ry, ry, group->meth));
 
160
        MP_CHECKOK(group->meth->field_sub(ry, C3, ry, group->meth));
 
161
 
 
162
        /* raz4 = a * rz^4 */
 
163
        MP_CHECKOK(group->meth->field_sqr(rz, raz4, group->meth));
 
164
        MP_CHECKOK(group->meth->field_sqr(raz4, raz4, group->meth));
 
165
        MP_CHECKOK(group->meth->
 
166
                           field_mul(raz4, &group->curvea, raz4, group->meth));
 
167
CLEANUP:
 
168
        return res;
 
169
}
 
170
 
 
171
/* Computes R = nP where R is (rx, ry) and P is the base point. Elliptic
 
172
 * curve points P and R can be identical. Uses mixed Modified-Jacobian
 
173
 * co-ordinates for doubling and Chudnovsky Jacobian coordinates for
 
174
 * additions. Assumes input is already field-encoded using field_enc, and
 
175
 * returns output that is still field-encoded. Uses 5-bit window NAF
 
176
 * method (algorithm 11) for scalar-point multiplication from Brown,
 
177
 * Hankerson, Lopez, Menezes. Software Implementation of the NIST Elliptic 
 
178
 * Curves Over Prime Fields. */
 
179
mp_err
 
180
ec_GFp_pt_mul_jm_wNAF(const mp_int *n, const mp_int *px, const mp_int *py,
 
181
                                          mp_int *rx, mp_int *ry, const ECGroup *group)
 
182
{
 
183
        mp_err res = MP_OKAY;
 
184
        mp_int precomp[16][2], rz, tpx, tpy;
 
185
        mp_int raz4;
 
186
        mp_int scratch[MAX_SCRATCH];
 
187
        signed char *naf = NULL;
 
188
        int i, orderBitSize;
 
189
 
 
190
        MP_DIGITS(&rz) = 0;
 
191
        MP_DIGITS(&raz4) = 0;
 
192
        MP_DIGITS(&tpx) = 0;
 
193
        MP_DIGITS(&tpy) = 0;
 
194
        for (i = 0; i < 16; i++) {
 
195
                MP_DIGITS(&precomp[i][0]) = 0;
 
196
                MP_DIGITS(&precomp[i][1]) = 0;
 
197
        }
 
198
        for (i = 0; i < MAX_SCRATCH; i++) {
 
199
                MP_DIGITS(&scratch[i]) = 0;
 
200
        }
 
201
 
 
202
        ARGCHK(group != NULL, MP_BADARG);
 
203
        ARGCHK((n != NULL) && (px != NULL) && (py != NULL), MP_BADARG);
 
204
 
 
205
        /* initialize precomputation table */
 
206
        MP_CHECKOK(mp_init(&tpx));
 
207
        MP_CHECKOK(mp_init(&tpy));;
 
208
        MP_CHECKOK(mp_init(&rz));
 
209
        MP_CHECKOK(mp_init(&raz4));
 
210
 
 
211
        for (i = 0; i < 16; i++) {
 
212
                MP_CHECKOK(mp_init(&precomp[i][0]));
 
213
                MP_CHECKOK(mp_init(&precomp[i][1]));
 
214
        }
 
215
        for (i = 0; i < MAX_SCRATCH; i++) {
 
216
                MP_CHECKOK(mp_init(&scratch[i]));
 
217
        }
 
218
 
 
219
        /* Set out[8] = P */
 
220
        MP_CHECKOK(mp_copy(px, &precomp[8][0]));
 
221
        MP_CHECKOK(mp_copy(py, &precomp[8][1]));
 
222
 
 
223
        /* Set (tpx, tpy) = 2P */
 
224
        MP_CHECKOK(group->
 
225
                           point_dbl(&precomp[8][0], &precomp[8][1], &tpx, &tpy,
 
226
                                                 group));
 
227
 
 
228
        /* Set 3P, 5P, ..., 15P */
 
229
        for (i = 8; i < 15; i++) {
 
230
                MP_CHECKOK(group->
 
231
                                   point_add(&precomp[i][0], &precomp[i][1], &tpx, &tpy,
 
232
                                                         &precomp[i + 1][0], &precomp[i + 1][1],
 
233
                                                         group));
 
234
        }
 
235
 
 
236
        /* Set -15P, -13P, ..., -P */
 
237
        for (i = 0; i < 8; i++) {
 
238
                MP_CHECKOK(mp_copy(&precomp[15 - i][0], &precomp[i][0]));
 
239
                MP_CHECKOK(group->meth->
 
240
                                   field_neg(&precomp[15 - i][1], &precomp[i][1],
 
241
                                                         group->meth));
 
242
        }
 
243
 
 
244
        /* R = inf */
 
245
        MP_CHECKOK(ec_GFp_pt_set_inf_jac(rx, ry, &rz));
 
246
 
 
247
        orderBitSize = mpl_significant_bits(&group->order);
 
248
 
 
249
        /* Allocate memory for NAF */
 
250
        naf = (signed char *) malloc(sizeof(signed char) * (orderBitSize + 1));
 
251
        if (naf == NULL) {
 
252
                res = MP_MEM;
 
253
                goto CLEANUP;
 
254
        }
 
255
 
 
256
        /* Compute 5NAF */
 
257
        ec_compute_wNAF(naf, orderBitSize, n, 5);
 
258
 
 
259
        /* wNAF method */
 
260
        for (i = orderBitSize; i >= 0; i--) {
 
261
                /* R = 2R */
 
262
                ec_GFp_pt_dbl_jm(rx, ry, &rz, &raz4, rx, ry, &rz, 
 
263
                                             &raz4, scratch, group);
 
264
                if (naf[i] != 0) {
 
265
                        ec_GFp_pt_add_jm_aff(rx, ry, &rz, &raz4,
 
266
                                                                 &precomp[(naf[i] + 15) / 2][0],
 
267
                                                                 &precomp[(naf[i] + 15) / 2][1], rx, ry,
 
268
                                                                 &rz, &raz4, scratch, group);
 
269
                }
 
270
        }
 
271
 
 
272
        /* convert result S to affine coordinates */
 
273
        MP_CHECKOK(ec_GFp_pt_jac2aff(rx, ry, &rz, rx, ry, group));
 
274
 
 
275
  CLEANUP:
 
276
        for (i = 0; i < MAX_SCRATCH; i++) {
 
277
                mp_clear(&scratch[i]);
 
278
        }
 
279
        for (i = 0; i < 16; i++) {
 
280
                mp_clear(&precomp[i][0]);
 
281
                mp_clear(&precomp[i][1]);
 
282
        }
 
283
        mp_clear(&tpx);
 
284
        mp_clear(&tpy);
 
285
        mp_clear(&rz);
 
286
        mp_clear(&raz4);
 
287
        free(naf);
 
288
        return res;
 
289
}