1 /*
2 * Copyright 2014-2016 The OpenSSL Project Authors. All Rights Reserved.
3 * Copyright (c) 2014, Intel Corporation. All Rights Reserved.
4 *
5 * Licensed under the OpenSSL license (the "License"). You may not use
6 * this file except in compliance with the License. You can obtain a copy
7 * in the file LICENSE in the source distribution or at
8 * https://www.openssl.org/source/license.html
9 *
10 * Originally written by Shay Gueron (1, 2), and Vlad Krasnov (1)
11 * (1) Intel Corporation, Israel Development Center, Haifa, Israel
12 * (2) University of Haifa, Israel
13 *
14 * Reference:
15 * S.Gueron and V.Krasnov, "Fast Prime Field Elliptic Curve Cryptography with
16 * 256 Bit Primes"
17 */
18
19 #include <ring-core/base.h>
20
21 #include "../../limbs/limbs.inl"
22
23 #include <stdint.h>
24
25 #include "p256-nistz.h"
26
27 #if defined(OPENSSL_USE_NISTZ256)
28
29 typedef P256_POINT_AFFINE PRECOMP256_ROW[64];
30
31 // One converted into the Montgomery domain
32 static const BN_ULONG ONE[P256_LIMBS] = {
33 TOBN(0x00000000, 0x00000001), TOBN(0xffffffff, 0x00000000),
34 TOBN(0xffffffff, 0xffffffff), TOBN(0x00000000, 0xfffffffe),
35 };
36
37 // Precomputed tables for the default generator
38 #include "p256-nistz-table.h"
39
40 // Recode window to a signed digit, see |nistp_recode_scalar_bits| in
41 // util.c for details
booth_recode_w5(crypto_word_t in)42 static crypto_word_t booth_recode_w5(crypto_word_t in) {
43 crypto_word_t s, d;
44
45 s = ~((in >> 5) - 1);
46 d = (1 << 6) - in - 1;
47 d = (d & s) | (in & ~s);
48 d = (d >> 1) + (d & 1);
49
50 return (d << 1) + (s & 1);
51 }
52
booth_recode_w7(crypto_word_t in)53 static crypto_word_t booth_recode_w7(crypto_word_t in) {
54 crypto_word_t s, d;
55
56 s = ~((in >> 7) - 1);
57 d = (1 << 8) - in - 1;
58 d = (d & s) | (in & ~s);
59 d = (d >> 1) + (d & 1);
60
61 return (d << 1) + (s & 1);
62 }
63
64 // The `(P256_LIMBS == 8)` case is unreachable for 64-bit targets.
65 #if defined(OPENSSL_64_BIT) && defined(__clang__)
66 #pragma GCC diagnostic push
67 #pragma GCC diagnostic ignored "-Wunreachable-code"
68 #endif
69
70 // copy_conditional copies |src| to |dst| if |move| is one and leaves it as-is
71 // if |move| is zero.
72 //
73 // WARNING: this breaks the usual convention of constant-time functions
74 // returning masks.
copy_conditional(BN_ULONG dst[P256_LIMBS],const BN_ULONG src[P256_LIMBS],BN_ULONG move)75 static void copy_conditional(BN_ULONG dst[P256_LIMBS],
76 const BN_ULONG src[P256_LIMBS], BN_ULONG move) {
77 BN_ULONG mask1 = ((BN_ULONG)0) - move;
78 BN_ULONG mask2 = ~mask1;
79
80 dst[0] = (src[0] & mask1) ^ (dst[0] & mask2);
81 dst[1] = (src[1] & mask1) ^ (dst[1] & mask2);
82 dst[2] = (src[2] & mask1) ^ (dst[2] & mask2);
83 dst[3] = (src[3] & mask1) ^ (dst[3] & mask2);
84 if (P256_LIMBS == 8) {
85 dst[4] = (src[4] & mask1) ^ (dst[4] & mask2);
86 dst[5] = (src[5] & mask1) ^ (dst[5] & mask2);
87 dst[6] = (src[6] & mask1) ^ (dst[6] & mask2);
88 dst[7] = (src[7] & mask1) ^ (dst[7] & mask2);
89 }
90 }
91
92 #if defined(__clang__)
93 #pragma GCC diagnostic pop
94 #endif
95
96 // is_not_zero returns one iff in != 0 and zero otherwise.
97 //
98 // WARNING: this breaks the usual convention of constant-time functions
99 // returning masks.
100 //
101 // (define-fun is_not_zero ((in (_ BitVec 64))) (_ BitVec 64)
102 // (bvlshr (bvor in (bvsub #x0000000000000000 in)) #x000000000000003f)
103 // )
104 //
105 // (declare-fun x () (_ BitVec 64))
106 //
107 // (assert (and (= x #x0000000000000000) (= (is_not_zero x) #x0000000000000001)))
108 // (check-sat)
109 //
110 // (assert (and (not (= x #x0000000000000000)) (= (is_not_zero x) #x0000000000000000)))
111 // (check-sat)
112 //
is_not_zero(BN_ULONG in)113 static BN_ULONG is_not_zero(BN_ULONG in) {
114 in |= (0 - in);
115 in >>= BN_BITS2 - 1;
116 return in;
117 }
118
119
120 // r = p * p_scalar
ecp_nistz256_windowed_mul(P256_POINT * r,const BN_ULONG p_scalar[P256_LIMBS],const BN_ULONG p_x[P256_LIMBS],const BN_ULONG p_y[P256_LIMBS])121 static void ecp_nistz256_windowed_mul(P256_POINT *r,
122 const BN_ULONG p_scalar[P256_LIMBS],
123 const BN_ULONG p_x[P256_LIMBS],
124 const BN_ULONG p_y[P256_LIMBS]) {
125 debug_assert_nonsecret(r != NULL);
126 debug_assert_nonsecret(p_scalar != NULL);
127 debug_assert_nonsecret(p_x != NULL);
128 debug_assert_nonsecret(p_y != NULL);
129
130 static const size_t kWindowSize = 5;
131 static const crypto_word_t kMask = (1 << (5 /* kWindowSize */ + 1)) - 1;
132
133 // A |P256_POINT| is (3 * 32) = 96 bytes, and the 64-byte alignment should
134 // add no more than 63 bytes of overhead. Thus, |table| should require
135 // ~1599 ((96 * 16) + 63) bytes of stack space.
136 alignas(64) P256_POINT table[16];
137 P256_SCALAR_BYTES p_str;
138 p256_scalar_bytes_from_limbs(p_str, p_scalar);
139
140 // table[0] is implicitly (0,0,0) (the point at infinity), therefore it is
141 // not stored. All other values are actually stored with an offset of -1 in
142 // table.
143 P256_POINT *row = table;
144
145 limbs_copy(row[1 - 1].X, p_x, P256_LIMBS);
146 limbs_copy(row[1 - 1].Y, p_y, P256_LIMBS);
147 limbs_copy(row[1 - 1].Z, ONE, P256_LIMBS);
148
149 ecp_nistz256_point_double(&row[2 - 1], &row[1 - 1]);
150 ecp_nistz256_point_add(&row[3 - 1], &row[2 - 1], &row[1 - 1]);
151 ecp_nistz256_point_double(&row[4 - 1], &row[2 - 1]);
152 ecp_nistz256_point_double(&row[6 - 1], &row[3 - 1]);
153 ecp_nistz256_point_double(&row[8 - 1], &row[4 - 1]);
154 ecp_nistz256_point_double(&row[12 - 1], &row[6 - 1]);
155 ecp_nistz256_point_add(&row[5 - 1], &row[4 - 1], &row[1 - 1]);
156 ecp_nistz256_point_add(&row[7 - 1], &row[6 - 1], &row[1 - 1]);
157 ecp_nistz256_point_add(&row[9 - 1], &row[8 - 1], &row[1 - 1]);
158 ecp_nistz256_point_add(&row[13 - 1], &row[12 - 1], &row[1 - 1]);
159 ecp_nistz256_point_double(&row[14 - 1], &row[7 - 1]);
160 ecp_nistz256_point_double(&row[10 - 1], &row[5 - 1]);
161 ecp_nistz256_point_add(&row[15 - 1], &row[14 - 1], &row[1 - 1]);
162 ecp_nistz256_point_add(&row[11 - 1], &row[10 - 1], &row[1 - 1]);
163 ecp_nistz256_point_double(&row[16 - 1], &row[8 - 1]);
164
165 BN_ULONG tmp[P256_LIMBS];
166 alignas(32) P256_POINT h;
167 size_t index = 255;
168 crypto_word_t wvalue = p_str[(index - 1) / 8];
169 wvalue = (wvalue >> ((index - 1) % 8)) & kMask;
170
171 ecp_nistz256_select_w5(r, table, (int)(booth_recode_w5(wvalue) >> 1));
172
173 while (index >= 5) {
174 if (index != 255) {
175 size_t off = (index - 1) / 8;
176
177 wvalue = (crypto_word_t)p_str[off] | (crypto_word_t)p_str[off + 1] << 8;
178 wvalue = (wvalue >> ((index - 1) % 8)) & kMask;
179
180 wvalue = booth_recode_w5(wvalue);
181
182 ecp_nistz256_select_w5(&h, table, (int)(wvalue >> 1));
183
184 ecp_nistz256_neg(tmp, h.Y);
185 copy_conditional(h.Y, tmp, (wvalue & 1));
186
187 ecp_nistz256_point_add(r, r, &h);
188 }
189
190 index -= kWindowSize;
191
192 ecp_nistz256_point_double(r, r);
193 ecp_nistz256_point_double(r, r);
194 ecp_nistz256_point_double(r, r);
195 ecp_nistz256_point_double(r, r);
196 ecp_nistz256_point_double(r, r);
197 }
198
199 // Final window
200 wvalue = p_str[0];
201 wvalue = (wvalue << 1) & kMask;
202
203 wvalue = booth_recode_w5(wvalue);
204
205 ecp_nistz256_select_w5(&h, table, (int)(wvalue >> 1));
206
207 ecp_nistz256_neg(tmp, h.Y);
208 copy_conditional(h.Y, tmp, wvalue & 1);
209
210 ecp_nistz256_point_add(r, r, &h);
211 }
212
calc_first_wvalue(size_t * index,const uint8_t p_str[33])213 static crypto_word_t calc_first_wvalue(size_t *index, const uint8_t p_str[33]) {
214 static const size_t kWindowSize = 7;
215 static const crypto_word_t kMask = (1 << (7 /* kWindowSize */ + 1)) - 1;
216 *index = kWindowSize;
217
218 crypto_word_t wvalue = ((crypto_word_t)p_str[0] << 1) & kMask;
219 return booth_recode_w7(wvalue);
220 }
221
calc_wvalue(size_t * index,const uint8_t p_str[33])222 static crypto_word_t calc_wvalue(size_t *index, const uint8_t p_str[33]) {
223 static const size_t kWindowSize = 7;
224 static const crypto_word_t kMask = (1 << (7 /* kWindowSize */ + 1)) - 1;
225
226 const size_t off = (*index - 1) / 8;
227 crypto_word_t wvalue =
228 (crypto_word_t)p_str[off] | (crypto_word_t)p_str[off + 1] << 8;
229 wvalue = (wvalue >> ((*index - 1) % 8)) & kMask;
230 *index += kWindowSize;
231
232 return booth_recode_w7(wvalue);
233 }
234
p256_point_mul(P256_POINT * r,const Limb p_scalar[P256_LIMBS],const Limb p_x[P256_LIMBS],const Limb p_y[P256_LIMBS])235 void p256_point_mul(P256_POINT *r, const Limb p_scalar[P256_LIMBS],
236 const Limb p_x[P256_LIMBS],
237 const Limb p_y[P256_LIMBS]) {
238 alignas(32) P256_POINT out;
239 ecp_nistz256_windowed_mul(&out, p_scalar, p_x, p_y);
240
241 limbs_copy(r->X, out.X, P256_LIMBS);
242 limbs_copy(r->Y, out.Y, P256_LIMBS);
243 limbs_copy(r->Z, out.Z, P256_LIMBS);
244 }
245
p256_point_mul_base(P256_POINT * r,const Limb scalar[P256_LIMBS])246 void p256_point_mul_base(P256_POINT *r, const Limb scalar[P256_LIMBS]) {
247 P256_SCALAR_BYTES p_str;
248 p256_scalar_bytes_from_limbs(p_str, scalar);
249
250 // First window
251 size_t index = 0;
252 crypto_word_t wvalue = calc_first_wvalue(&index, p_str);
253
254 alignas(32) P256_POINT_AFFINE t;
255 alignas(32) P256_POINT p;
256 ecp_nistz256_select_w7(&t, ecp_nistz256_precomputed[0], (int)(wvalue >> 1));
257 ecp_nistz256_neg(p.Z, t.Y);
258 copy_conditional(t.Y, p.Z, wvalue & 1);
259
260 // Convert |t| from affine to Jacobian coordinates. We set Z to zero if |t|
261 // is infinity and |ONE| otherwise. |t| was computed from the table, so it
262 // is infinity iff |wvalue >> 1| is zero.
263 limbs_copy(p.X, t.X, P256_LIMBS);
264 limbs_copy(p.Y, t.Y, P256_LIMBS);
265 limbs_zero(p.Z, P256_LIMBS);
266 copy_conditional(p.Z, ONE, is_not_zero(wvalue >> 1));
267
268 for (int i = 1; i < 37; i++) {
269 wvalue = calc_wvalue(&index, p_str);
270
271 ecp_nistz256_select_w7(&t, ecp_nistz256_precomputed[i], (int)(wvalue >> 1));
272
273 alignas(32) BN_ULONG neg_Y[P256_LIMBS];
274 ecp_nistz256_neg(neg_Y, t.Y);
275 copy_conditional(t.Y, neg_Y, wvalue & 1);
276
277 // Note |ecp_nistz256_point_add_affine| does not work if |p| and |t| are the
278 // same non-infinity point.
279 ecp_nistz256_point_add_affine(&p, &p, &t);
280 }
281
282 limbs_copy(r->X, p.X, P256_LIMBS);
283 limbs_copy(r->Y, p.Y, P256_LIMBS);
284 limbs_copy(r->Z, p.Z, P256_LIMBS);
285 }
286
287 #endif /* defined(OPENSSL_USE_NISTZ256) */
288