← Back to branch summary

~ubuntu-branches/ubuntu/vivid/nettle/vivid-proposed

« back to all changes in this revision

Viewing changes to ecc-256.c

  • Committer: Package Import Robot
  • Author(s): Magnus Holmgren
  • Date: 2013-05-04 19:50:28 UTC
  • mfrom: (1.4.6) (3.1.11 experimental)
  • mto: This revision was merged to the branch mainline in revision 14.
  • Revision ID: package-import@ubuntu.com-20130504195028-fp6c9fw1tsm5scwa
Tags: 2.7-1
http://bugs.debian.org/706081
* New upstream release (Closes: #706081).
* Include watch file improvements from Bart Martens <bartm@debian.org>
  via the QA system.

Show diffs side-by-side

added added

removed removed

Lines of Context:
ecc-256.c
 
1
/* ecc-256.c.c */
 
2
 
 
3
/* Compile time constant (but machine dependent) tables. */
 
4
 
 
5
/* nettle, low-level cryptographics library
 
6
 *
 
7
 * Copyright (C) 2013 Niels Möller
 
8
 *  
 
9
 * The nettle library is free software; you can redistribute it and/or modify
 
10
 * it under the terms of the GNU Lesser General Public License as published by
 
11
 * the Free Software Foundation; either version 2.1 of the License, or (at your
 
12
 * option) any later version.
 
13
 * 
 
14
 * The nettle library is distributed in the hope that it will be useful, but
 
15
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 
16
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
 
17
 * License for more details.
 
18
 * 
 
19
 * You should have received a copy of the GNU Lesser General Public License
 
20
 * along with the nettle library; see the file COPYING.LIB.  If not, write to
 
21
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
 
22
 * MA 02111-1301, USA.
 
23
 */
 
24
 
 
25
/* Development of Nettle's ECC support was funded by the .SE Internet Fund. */
 
26
 
 
27
#if HAVE_CONFIG_H
 
28
# include "config.h"
 
29
#endif
 
30
 
 
31
#include <assert.h>
 
32
 
 
33
#include "ecc-internal.h"
 
34
 
 
35
#if HAVE_NATIVE_ecc_256_redc
 
36
# define USE_REDC 1
 
37
#else
 
38
# define USE_REDC (ECC_REDC_SIZE != 0)
 
39
#endif
 
40
 
 
41
#include "ecc-256.h"
 
42
 
 
43
#if HAVE_NATIVE_ecc_256_redc
 
44
# define ecc_256_redc nettle_ecc_256_redc
 
45
void
 
46
ecc_256_redc (const struct ecc_curve *ecc, mp_limb_t *rp);
 
47
#else /* !HAVE_NATIVE_ecc_256_redc */
 
48
# define ecc_256_redc ecc_generic_redc
 
49
#endif
 
50
 
 
51
#if ECC_BMODP_SIZE < ECC_LIMB_SIZE
 
52
#define ecc_256_modp ecc_generic_modp
 
53
#define ecc_256_modq ecc_generic_modq
 
54
#elif GMP_NUMB_BITS == 64
 
55
 
 
56
static void
 
57
ecc_256_modp (const struct ecc_curve *ecc, mp_limb_t *rp)
 
58
{
 
59
  mp_limb_t u1, u0;
 
60
  mp_size_t n;
 
61
 
 
62
  n = 2*ecc->size;
 
63
  u1 = rp[--n];
 
64
  u0 = rp[n-1];
 
65
 
 
66
  /* This is not particularly fast, but should work well with assembly implementation. */
 
67
  for (; n >= ecc->size; n--)
 
68
    {
 
69
      mp_limb_t q2, q1, q0, t, cy;
 
70
 
 
71
      /* <q2, q1, q0> = v * u1 + <u1,u0>, with v = 2^32 - 1:
 
72
 
 
73
           +---+---+
 
74
           | u1| u0|
 
75
           +---+---+
 
76
               |-u1|
 
77
             +-+-+-+
 
78
             | u1|
 
79
       +---+-+-+-+-+
 
80
       | q2| q1| q0|
 
81
       +---+---+---+
 
82
      */
 
83
      q1 = u1 - (u1 > u0);
 
84
      q0 = u0 - u1;
 
85
      t = u1 << 32;
 
86
      q0 += t;
 
87
      t = (u1 >> 32) + (q0 < t) + 1;
 
88
      q1 += t;
 
89
      q2 = q1 < t;
 
90
 
 
91
      /* Compute candidate remainder */
 
92
      u1 = u0 + (q1 << 32) - q1;
 
93
      t = -(mp_limb_t) (u1 > q0);
 
94
      u1 -= t & 0xffffffff;
 
95
      q1 += t;
 
96
      q2 += t + (q1 < t);
 
97
 
 
98
      assert (q2 < 2);
 
99
 
 
100
      /* We multiply by two low limbs of p, 2^96 - 1, so we could use
 
101
         shifts rather than mul. */
 
102
      t = mpn_submul_1 (rp + n - 4, ecc->p, 2, q1);
 
103
      t += cnd_sub_n (q2, rp + n - 3, ecc->p, 1);
 
104
      t += (-q2) & 0xffffffff;
 
105
 
 
106
      u0 = rp[n-2];
 
107
      cy = (u0 < t);
 
108
      u0 -= t;
 
109
      t = (u1 < cy);
 
110
      u1 -= cy;
 
111
      u1 += cnd_add_n (t, rp + n - 4, ecc->p, 3);
 
112
      u1 -= (-t) & 0xffffffff;
 
113
    }
 
114
  rp[2] = u0;
 
115
  rp[3] = u1;
 
116
}
 
117
 
 
118
static void
 
119
ecc_256_modq (const struct ecc_curve *ecc, mp_limb_t *rp)
 
120
{
 
121
  mp_limb_t u2, u1, u0;
 
122
  mp_size_t n;
 
123
 
 
124
  n = 2*ecc->size;
 
125
  u2 = rp[--n];
 
126
  u1 = rp[n-1];
 
127
 
 
128
  /* This is not particularly fast, but should work well with assembly implementation. */
 
129
  for (; n >= ecc->size; n--)
 
130
    {
 
131
      mp_limb_t q2, q1, q0, t, c1, c0;
 
132
 
 
133
      u0 = rp[n-2];
 
134
      
 
135
      /* <q2, q1, q0> = v * u2 + <u2,u1>, same method as above.
 
136
 
 
137
           +---+---+
 
138
           | u2| u1|
 
139
           +---+---+
 
140
               |-u2|
 
141
             +-+-+-+
 
142
             | u2|
 
143
       +---+-+-+-+-+
 
144
       | q2| q1| q0|
 
145
       +---+---+---+
 
146
      */
 
147
      q1 = u2 - (u2 > u1);
 
148
      q0 = u1 - u2;
 
149
      t = u2 << 32;
 
150
      q0 += t;
 
151
      t = (u2 >> 32) + (q0 < t) + 1;
 
152
      q1 += t;
 
153
      q2 = q1 < t;
 
154
 
 
155
      /* Compute candidate remainder, <u1, u0> - <q2, q1> * (2^128 - 2^96 + 2^64 - 1)
 
156
         <u1, u0> + 2^64 q2 + (2^96 - 2^64 + 1) q1 (mod 2^128)
 
157
 
 
158
           +---+---+
 
159
           | u1| u0|
 
160
           +---+---+
 
161
           | q2| q1|
 
162
           +---+---+
 
163
           |-q1|
 
164
         +-+-+-+
 
165
         | q1|
 
166
       --+-+-+-+---+
 
167
           | u2| u1|
 
168
           +---+---+
 
169
      */         
 
170
      u2 = u1 + q2 - q1;
 
171
      u1 = u0 + q1;
 
172
      u2 += (u1 < q1);
 
173
      u2 += (q1 << 32);
 
174
 
 
175
      t = -(mp_limb_t) (u2 >= q0);
 
176
      q1 += t;
 
177
      q2 += t + (q1 < t);
 
178
      u1 += t;
 
179
      u2 += (t << 32) + (u1 < t);
 
180
 
 
181
      assert (q2 < 2);
 
182
 
 
183
      c0 = cnd_sub_n (q2, rp + n - 3, ecc->q, 1);
 
184
      c0 += (-q2) & ecc->q[1];
 
185
      t = mpn_submul_1 (rp + n - 4, ecc->q, 2, q1);
 
186
      c0 += t;
 
187
      c1 = c0 < t;
 
188
      
 
189
      /* Construct underflow condition. */
 
190
      c1 += (u1 < c0);
 
191
      t = - (mp_limb_t) (u2 < c1);
 
192
 
 
193
      u1 -= c0;
 
194
      u2 -= c1;
 
195
 
 
196
      /* Conditional add of p */
 
197
      u1 += t;
 
198
      u2 += (t<<32) + (u0 < t);
 
199
 
 
200
      t = cnd_add_n (t, rp + n - 4, ecc->q, 2);
 
201
      u1 += t;
 
202
      u2 += (u1 < t);
 
203
    }
 
204
  rp[2] = u1;
 
205
  rp[3] = u2;
 
206
}
 
207
      
 
208
#else
 
209
#error Unsupported parameters
 
210
#endif
 
211
 
 
212
const struct ecc_curve nettle_secp_256r1 =
 
213
{
 
214
  256,
 
215
  ECC_LIMB_SIZE,    
 
216
  ECC_BMODP_SIZE,
 
217
  ECC_BMODQ_SIZE,
 
218
  USE_REDC,
 
219
  ECC_REDC_SIZE,
 
220
  ECC_PIPPENGER_K,
 
221
  ECC_PIPPENGER_C,
 
222
  ecc_p,
 
223
  ecc_b,
 
224
  ecc_q,
 
225
  ecc_g,
 
226
  ecc_redc_g,
 
227
  ecc_256_modp,
 
228
  ecc_256_redc,
 
229
  USE_REDC ? ecc_256_redc : ecc_256_modp,
 
230
  ecc_256_modq,
 
231
  ecc_Bmodp,
 
232
  ecc_Bmodp_shifted,
 
233
  ecc_pp1h,
 
234
  ecc_redc_ppm1,
 
235
  ecc_unit,
 
236
  ecc_Bmodq,
 
237
  ecc_Bmodq_shifted,
 
238
  ecc_qp1h,
 
239
  ecc_table
 
240
};