1/*
2 * Copyright 2013 The Android Open Source Project
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *     * Redistributions of source code must retain the above copyright
7 *       notice, this list of conditions and the following disclaimer.
8 *     * Redistributions in binary form must reproduce the above copyright
9 *       notice, this list of conditions and the following disclaimer in the
10 *       documentation and/or other materials provided with the distribution.
11 *     * Neither the name of Google Inc. nor the names of its contributors may
12 *       be used to endorse or promote products derived from this software
13 *       without specific prior written permission.
14 *
15 * THIS SOFTWARE IS PROVIDED BY Google Inc. ``AS IS'' AND ANY EXPRESS OR
16 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
17 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO
18 * EVENT SHALL Google Inc. BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
19 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
21 * OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
22 * WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
23 * OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
24 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25 */
26
27// This is an implementation of the P256 elliptic curve group. It's written to
28// be portable 32-bit, although it's still constant-time.
29//
30// WARNING: Implementing these functions in a constant-time manner is far from
31//          obvious. Be careful when touching this code.
32//
33// See http://www.imperialviolet.org/2010/12/04/ecc.html ([1]) for background.
34
35#include <assert.h>
36#include <stdint.h>
37#include <string.h>
38#include <stdio.h>
39
40#include "mincrypt/p256.h"
41
42const p256_int SECP256r1_n =  // curve order
43  {{0xfc632551, 0xf3b9cac2, 0xa7179e84, 0xbce6faad, -1, -1, 0, -1}};
44
45const p256_int SECP256r1_p =  // curve field size
46  {{-1, -1, -1, 0, 0, 0, 1, -1 }};
47
48const p256_int SECP256r1_b =  // curve b
49  {{0x27d2604b, 0x3bce3c3e, 0xcc53b0f6, 0x651d06b0,
50    0x769886bc, 0xb3ebbd55, 0xaa3a93e7, 0x5ac635d8}};
51
52void p256_init(p256_int* a) {
53  memset(a, 0, sizeof(*a));
54}
55
56void p256_clear(p256_int* a) { p256_init(a); }
57
58int p256_get_bit(const p256_int* scalar, int bit) {
59  return (P256_DIGIT(scalar, bit / P256_BITSPERDIGIT)
60              >> (bit & (P256_BITSPERDIGIT - 1))) & 1;
61}
62
63int p256_is_zero(const p256_int* a) {
64  int i, result = 0;
65  for (i = 0; i < P256_NDIGITS; ++i) result |= P256_DIGIT(a, i);
66  return !result;
67}
68
69// top, c[] += a[] * b
70// Returns new top
71static p256_digit mulAdd(const p256_int* a,
72                         p256_digit b,
73                         p256_digit top,
74                         p256_digit* c) {
75  int i;
76  p256_ddigit carry = 0;
77
78  for (i = 0; i < P256_NDIGITS; ++i) {
79    carry += *c;
80    carry += (p256_ddigit)P256_DIGIT(a, i) * b;
81    *c++ = (p256_digit)carry;
82    carry >>= P256_BITSPERDIGIT;
83  }
84  return top + (p256_digit)carry;
85}
86
87// top, c[] -= top_a, a[]
88static p256_digit subTop(p256_digit top_a,
89                         const p256_digit* a,
90                         p256_digit top_c,
91                         p256_digit* c) {
92  int i;
93  p256_sddigit borrow = 0;
94
95  for (i = 0; i < P256_NDIGITS; ++i) {
96    borrow += *c;
97    borrow -= *a++;
98    *c++ = (p256_digit)borrow;
99    borrow >>= P256_BITSPERDIGIT;
100  }
101  borrow += top_c;
102  borrow -= top_a;
103  top_c = (p256_digit)borrow;
104  assert((borrow >> P256_BITSPERDIGIT) == 0);
105  return top_c;
106}
107
108// top, c[] -= MOD[] & mask (0 or -1)
109// returns new top.
110static p256_digit subM(const p256_int* MOD,
111                       p256_digit top,
112                       p256_digit* c,
113                       p256_digit mask) {
114  int i;
115  p256_sddigit borrow = 0;
116  for (i = 0; i < P256_NDIGITS; ++i) {
117    borrow += *c;
118    borrow -= P256_DIGIT(MOD, i) & mask;
119    *c++ = (p256_digit)borrow;
120    borrow >>= P256_BITSPERDIGIT;
121  }
122  return top + (p256_digit)borrow;
123}
124
125// top, c[] += MOD[] & mask (0 or -1)
126// returns new top.
127static p256_digit addM(const p256_int* MOD,
128                       p256_digit top,
129                       p256_digit* c,
130                       p256_digit mask) {
131  int i;
132  p256_ddigit carry = 0;
133  for (i = 0; i < P256_NDIGITS; ++i) {
134    carry += *c;
135    carry += P256_DIGIT(MOD, i) & mask;
136    *c++ = (p256_digit)carry;
137    carry >>= P256_BITSPERDIGIT;
138  }
139  return top + (p256_digit)carry;
140}
141
142// c = a * b mod MOD. c can be a and/or b.
143void p256_modmul(const p256_int* MOD,
144                 const p256_int* a,
145                 const p256_digit top_b,
146                 const p256_int* b,
147                 p256_int* c) {
148  p256_digit tmp[P256_NDIGITS * 2 + 1] = { 0 };
149  p256_digit top = 0;
150  int i;
151
152  // Multiply/add into tmp.
153  for (i = 0; i < P256_NDIGITS; ++i) {
154    if (i) tmp[i + P256_NDIGITS - 1] = top;
155    top = mulAdd(a, P256_DIGIT(b, i), 0, tmp + i);
156  }
157
158  // Multiply/add top digit
159  tmp[i + P256_NDIGITS - 1] = top;
160  top = mulAdd(a, top_b, 0, tmp + i);
161
162  // Reduce tmp, digit by digit.
163  for (; i >= 0; --i) {
164    p256_digit reducer[P256_NDIGITS] = { 0 };
165    p256_digit top_reducer;
166
167    // top can be any value at this point.
168    // Guestimate reducer as top * MOD, since msw of MOD is -1.
169    top_reducer = mulAdd(MOD, top, 0, reducer);
170
171    // Subtract reducer from top | tmp.
172    top = subTop(top_reducer, reducer, top, tmp + i);
173
174    // top is now either 0 or 1. Make it 0, fixed-timing.
175    assert(top <= 1);
176
177    top = subM(MOD, top, tmp + i, ~(top - 1));
178
179    assert(top == 0);
180
181    // We have now reduced the top digit off tmp. Fetch new top digit.
182    top = tmp[i + P256_NDIGITS - 1];
183  }
184
185  // tmp might still be larger than MOD, yet same bit length.
186  // Make sure it is less, fixed-timing.
187  addM(MOD, 0, tmp, subM(MOD, 0, tmp, -1));
188
189  memcpy(c, tmp, P256_NBYTES);
190}
191int p256_is_odd(const p256_int* a) { return P256_DIGIT(a, 0) & 1; }
192int p256_is_even(const p256_int* a) { return !(P256_DIGIT(a, 0) & 1); }
193
194p256_digit p256_shl(const p256_int* a, int n, p256_int* b) {
195  int i;
196  p256_digit top = P256_DIGIT(a, P256_NDIGITS - 1);
197
198  n %= P256_BITSPERDIGIT;
199  for (i = P256_NDIGITS - 1; i > 0; --i) {
200    p256_digit accu = (P256_DIGIT(a, i) << n);
201    accu |= (P256_DIGIT(a, i - 1) >> (P256_BITSPERDIGIT - n));
202    P256_DIGIT(b, i) = accu;
203  }
204  P256_DIGIT(b, i) = (P256_DIGIT(a, i) << n);
205
206  top = (p256_digit)((((p256_ddigit)top) << n) >> P256_BITSPERDIGIT);
207
208  return top;
209}
210
211void p256_shr(const p256_int* a, int n, p256_int* b) {
212  int i;
213
214  n %= P256_BITSPERDIGIT;
215  for (i = 0; i < P256_NDIGITS - 1; ++i) {
216    p256_digit accu = (P256_DIGIT(a, i) >> n);
217    accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - n));
218    P256_DIGIT(b, i) = accu;
219  }
220  P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> n);
221}
222
223static void p256_shr1(const p256_int* a, int highbit, p256_int* b) {
224  int i;
225
226  for (i = 0; i < P256_NDIGITS - 1; ++i) {
227    p256_digit accu = (P256_DIGIT(a, i) >> 1);
228    accu |= (P256_DIGIT(a, i + 1) << (P256_BITSPERDIGIT - 1));
229    P256_DIGIT(b, i) = accu;
230  }
231  P256_DIGIT(b, i) = (P256_DIGIT(a, i) >> 1) |
232      (highbit << (P256_BITSPERDIGIT - 1));
233}
234
235// Return -1, 0, 1 for a < b, a == b or a > b respectively.
236int p256_cmp(const p256_int* a, const p256_int* b) {
237  int i;
238  p256_sddigit borrow = 0;
239  p256_digit notzero = 0;
240
241  for (i = 0; i < P256_NDIGITS; ++i) {
242    borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i);
243    // Track whether any result digit is ever not zero.
244    // Relies on !!(non-zero) evaluating to 1, e.g., !!(-1) evaluating to 1.
245    notzero |= !!((p256_digit)borrow);
246    borrow >>= P256_BITSPERDIGIT;
247  }
248  return (int)borrow | notzero;
249}
250
251// c = a - b. Returns borrow: 0 or -1.
252int p256_sub(const p256_int* a, const p256_int* b, p256_int* c) {
253  int i;
254  p256_sddigit borrow = 0;
255
256  for (i = 0; i < P256_NDIGITS; ++i) {
257    borrow += (p256_sddigit)P256_DIGIT(a, i) - P256_DIGIT(b, i);
258    if (c) P256_DIGIT(c, i) = (p256_digit)borrow;
259    borrow >>= P256_BITSPERDIGIT;
260  }
261  return (int)borrow;
262}
263
264// c = a + b. Returns carry: 0 or 1.
265int p256_add(const p256_int* a, const p256_int* b, p256_int* c) {
266  int i;
267  p256_ddigit carry = 0;
268
269  for (i = 0; i < P256_NDIGITS; ++i) {
270    carry += (p256_ddigit)P256_DIGIT(a, i) + P256_DIGIT(b, i);
271    if (c) P256_DIGIT(c, i) = (p256_digit)carry;
272    carry >>= P256_BITSPERDIGIT;
273  }
274  return (int)carry;
275}
276
277// b = a + d. Returns carry, 0 or 1.
278int p256_add_d(const p256_int* a, p256_digit d, p256_int* b) {
279  int i;
280  p256_ddigit carry = d;
281
282  for (i = 0; i < P256_NDIGITS; ++i) {
283    carry += (p256_ddigit)P256_DIGIT(a, i);
284    if (b) P256_DIGIT(b, i) = (p256_digit)carry;
285    carry >>= P256_BITSPERDIGIT;
286  }
287  return (int)carry;
288}
289
290// b = 1/a mod MOD, binary euclid.
291void p256_modinv_vartime(const p256_int* MOD,
292                         const p256_int* a,
293                         p256_int* b) {
294  p256_int R = P256_ZERO;
295  p256_int S = P256_ONE;
296  p256_int U = *MOD;
297  p256_int V = *a;
298
299  for (;;) {
300    if (p256_is_even(&U)) {
301      p256_shr1(&U, 0, &U);
302      if (p256_is_even(&R)) {
303        p256_shr1(&R, 0, &R);
304      } else {
305        // R = (R+MOD)/2
306        p256_shr1(&R, p256_add(&R, MOD, &R), &R);
307      }
308    } else if (p256_is_even(&V)) {
309      p256_shr1(&V, 0, &V);
310      if (p256_is_even(&S)) {
311        p256_shr1(&S, 0, &S);
312      } else {
313        // S = (S+MOD)/2
314        p256_shr1(&S, p256_add(&S, MOD, &S) , &S);
315      }
316    } else {  // U,V both odd.
317      if (!p256_sub(&V, &U, NULL)) {
318        p256_sub(&V, &U, &V);
319        if (p256_sub(&S, &R, &S)) p256_add(&S, MOD, &S);
320        if (p256_is_zero(&V)) break;  // done.
321      } else {
322        p256_sub(&U, &V, &U);
323        if (p256_sub(&R, &S, &R)) p256_add(&R, MOD, &R);
324      }
325    }
326  }
327
328  p256_mod(MOD, &R, b);
329}
330
331void p256_mod(const p256_int* MOD,
332              const p256_int* in,
333              p256_int* out) {
334  if (out != in) *out = *in;
335  addM(MOD, 0, P256_DIGITS(out), subM(MOD, 0, P256_DIGITS(out), -1));
336}
337
338// Verify y^2 == x^3 - 3x + b mod p
339// and 0 < x < p and 0 < y < p
340int p256_is_valid_point(const p256_int* x, const p256_int* y) {
341  p256_int y2, x3;
342
343  if (p256_cmp(&SECP256r1_p, x) <= 0 ||
344      p256_cmp(&SECP256r1_p, y) <= 0 ||
345      p256_is_zero(x) ||
346      p256_is_zero(y)) return 0;
347
348  p256_modmul(&SECP256r1_p, y, 0, y, &y2);  // y^2
349
350  p256_modmul(&SECP256r1_p, x, 0, x, &x3);  // x^2
351  p256_modmul(&SECP256r1_p, x, 0, &x3, &x3);  // x^3
352  if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - x
353  if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - 2x
354  if (p256_sub(&x3, x, &x3)) p256_add(&x3, &SECP256r1_p, &x3);  // x^3 - 3x
355  if (p256_add(&x3, &SECP256r1_b, &x3))  // x^3 - 3x + b
356    p256_sub(&x3, &SECP256r1_p, &x3);
357
358  return p256_cmp(&y2, &x3) == 0;
359}
360
361void p256_from_bin(const uint8_t src[P256_NBYTES], p256_int* dst) {
362  int i;
363  const uint8_t* p = &src[0];
364
365  for (i = P256_NDIGITS - 1; i >= 0; --i) {
366    P256_DIGIT(dst, i) =
367        (p[0] << 24) |
368        (p[1] << 16) |
369        (p[2] << 8) |
370        p[3];
371    p += 4;
372  }
373}
374