p256-x86_64_test.cc revision 8ff035535f7cf2903f02bbe94d2fa10b7ab855f1 
1/* Copyright (c) 2016, Google Inc.
2 *
3 * Permission to use, copy, modify, and/or distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY
10 * SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION
12 * OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
13 * CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. */
14
15#if !defined(__STDC_FORMAT_MACROS)
16#define __STDC_FORMAT_MACROS
17#endif
18
19#include <openssl/base.h>
20
21#include <stdio.h>
22#include <string.h>
23
24#include <gtest/gtest.h>
25
26#include <openssl/bn.h>
27#include <openssl/mem.h>
28
29#include "../bn/internal.h"
30#include "../../test/file_test.h"
31#include "../../test/test_util.h"
32#include "p256-x86_64.h"
33
34
35// Disable tests if BORINGSSL_SHARED_LIBRARY is defined. These tests need access
36// to internal functions.
37#if !defined(OPENSSL_NO_ASM) && defined(OPENSSL_X86_64) && \
38    !defined(OPENSSL_SMALL) && !defined(BORINGSSL_SHARED_LIBRARY)
39
40TEST(P256_X86_64Test, SelectW5) {
41  // Fill a table with some garbage input.
42  P256_POINT table[16];
43  for (size_t i = 0; i < 16; i++) {
44    OPENSSL_memset(table[i].X, 3 * i, sizeof(table[i].X));
45    OPENSSL_memset(table[i].Y, 3 * i + 1, sizeof(table[i].Y));
46    OPENSSL_memset(table[i].Z, 3 * i + 2, sizeof(table[i].Z));
47  }
48
49  for (int i = 0; i <= 16; i++) {
50    P256_POINT val;
51    ecp_nistz256_select_w5(&val, table, i);
52
53    P256_POINT expected;
54    if (i == 0) {
55      OPENSSL_memset(&expected, 0, sizeof(expected));
56    } else {
57      expected = table[i-1];
58    }
59
60    EXPECT_EQ(Bytes(reinterpret_cast<const char *>(&expected), sizeof(expected)),
61              Bytes(reinterpret_cast<const char *>(&val), sizeof(val)));
62  }
63}
64
65TEST(P256_X86_64Test, SelectW7) {
66  // Fill a table with some garbage input.
67  P256_POINT_AFFINE table[64];
68  for (size_t i = 0; i < 64; i++) {
69    OPENSSL_memset(table[i].X, 2 * i, sizeof(table[i].X));
70    OPENSSL_memset(table[i].Y, 2 * i + 1, sizeof(table[i].Y));
71  }
72
73  for (int i = 0; i <= 64; i++) {
74    P256_POINT_AFFINE val;
75    ecp_nistz256_select_w7(&val, table, i);
76
77    P256_POINT_AFFINE expected;
78    if (i == 0) {
79      OPENSSL_memset(&expected, 0, sizeof(expected));
80    } else {
81      expected = table[i-1];
82    }
83
84    EXPECT_EQ(Bytes(reinterpret_cast<const char *>(&expected), sizeof(expected)),
85              Bytes(reinterpret_cast<const char *>(&val), sizeof(val)));
86  }
87}
88
89static bool GetFieldElement(FileTest *t, BN_ULONG out[P256_LIMBS],
90                            const char *name) {
91  std::vector<uint8_t> bytes;
92  if (!t->GetBytes(&bytes, name)) {
93    return false;
94  }
95
96  if (bytes.size() != BN_BYTES * P256_LIMBS) {
97    ADD_FAILURE() << "Invalid length: " << name;
98    return false;
99  }
100
101  // |byte| contains bytes in big-endian while |out| should contain |BN_ULONG|s
102  // in little-endian.
103  OPENSSL_memset(out, 0, P256_LIMBS * sizeof(BN_ULONG));
104  for (size_t i = 0; i < bytes.size(); i++) {
105    out[P256_LIMBS - 1 - (i / BN_BYTES)] <<= 8;
106    out[P256_LIMBS - 1 - (i / BN_BYTES)] |= bytes[i];
107  }
108
109  return true;
110}
111
112static std::string FieldElementToString(const BN_ULONG a[P256_LIMBS]) {
113  std::string ret;
114  for (size_t i = P256_LIMBS-1; i < P256_LIMBS; i--) {
115    char buf[2 * BN_BYTES + 1];
116    BIO_snprintf(buf, sizeof(buf), BN_HEX_FMT2, a[i]);
117    ret += buf;
118  }
119  return ret;
120}
121
122static testing::AssertionResult ExpectFieldElementsEqual(
123    const char *expected_expr, const char *actual_expr,
124    const BN_ULONG expected[P256_LIMBS], const BN_ULONG actual[P256_LIMBS]) {
125  if (OPENSSL_memcmp(expected, actual, sizeof(BN_ULONG) * P256_LIMBS) == 0) {
126    return testing::AssertionSuccess();
127  }
128
129  return testing::AssertionFailure()
130         << "Expected: " << FieldElementToString(expected) << " ("
131         << expected_expr << ")\n"
132         << "Actual:   " << FieldElementToString(actual) << " (" << actual_expr
133         << ")";
134}
135
136#define EXPECT_FIELD_ELEMENTS_EQUAL(a, b) \
137  EXPECT_PRED_FORMAT2(ExpectFieldElementsEqual, a, b)
138
139static bool PointToAffine(P256_POINT_AFFINE *out, const P256_POINT *in) {
140  static const uint8_t kP[] = {
141      0xff, 0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x01, 0x00, 0x00, 0x00,
142      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0xff, 0xff,
143      0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff,
144  };
145
146  bssl::UniquePtr<BIGNUM> x(BN_new()), y(BN_new()), z(BN_new());
147  bssl::UniquePtr<BIGNUM> p(BN_bin2bn(kP, sizeof(kP), nullptr));
148  if (!x || !y || !z || !p ||
149      !bn_set_words(x.get(), in->X, P256_LIMBS) ||
150      !bn_set_words(y.get(), in->Y, P256_LIMBS) ||
151      !bn_set_words(z.get(), in->Z, P256_LIMBS)) {
152    return false;
153  }
154
155  // Coordinates must be fully-reduced.
156  if (BN_cmp(x.get(), p.get()) >= 0 ||
157      BN_cmp(y.get(), p.get()) >= 0 ||
158      BN_cmp(z.get(), p.get()) >= 0) {
159    return false;
160  }
161
162  OPENSSL_memset(out, 0, sizeof(P256_POINT_AFFINE));
163
164  if (BN_is_zero(z.get())) {
165    // The point at infinity is represented as (0, 0).
166    return true;
167  }
168
169  bssl::UniquePtr<BN_CTX> ctx(BN_CTX_new());
170  bssl::UniquePtr<BN_MONT_CTX> mont(BN_MONT_CTX_new());
171  if (!ctx || !mont ||
172      !BN_MONT_CTX_set(mont.get(), p.get(), ctx.get()) ||
173      // Invert Z.
174      !BN_from_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
175      !BN_mod_inverse(z.get(), z.get(), p.get(), ctx.get()) ||
176      !BN_to_montgomery(z.get(), z.get(), mont.get(), ctx.get()) ||
177      // Convert (X, Y, Z) to (X/Z^2, Y/Z^3).
178      !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
179                             ctx.get()) ||
180      !BN_mod_mul_montgomery(x.get(), x.get(), z.get(), mont.get(),
181                             ctx.get()) ||
182      !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
183                             ctx.get()) ||
184      !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
185                             ctx.get()) ||
186      !BN_mod_mul_montgomery(y.get(), y.get(), z.get(), mont.get(),
187                             ctx.get())) {
188    return false;
189  }
190
191  OPENSSL_memcpy(out->X, x->d, sizeof(BN_ULONG) * x->top);
192  OPENSSL_memcpy(out->Y, y->d, sizeof(BN_ULONG) * y->top);
193  return true;
194}
195
196static testing::AssertionResult ExpectPointsEqual(
197    const char *expected_expr, const char *actual_expr,
198    const P256_POINT_AFFINE *expected, const P256_POINT *actual) {
199  // There are multiple representations of the same |P256_POINT|, so convert to
200  // |P256_POINT_AFFINE| and compare.
201  P256_POINT_AFFINE affine;
202  if (!PointToAffine(&affine, actual)) {
203    return testing::AssertionFailure()
204           << "Could not convert " << actual_expr << " to affine: ("
205           << FieldElementToString(actual->X) << ", "
206           << FieldElementToString(actual->Y) << ", "
207           << FieldElementToString(actual->Z) << ")";
208  }
209
210  if (OPENSSL_memcmp(expected, &affine, sizeof(P256_POINT_AFFINE)) != 0) {
211    return testing::AssertionFailure()
212           << "Expected: (" << FieldElementToString(expected->X) << ", "
213           << FieldElementToString(expected->Y) << ") (" << expected_expr
214           << "; affine)\n"
215           << "Actual:   (" << FieldElementToString(affine.X) << ", "
216           << FieldElementToString(affine.Y) << ") (" << actual_expr << ")";
217  }
218
219  return testing::AssertionSuccess();
220}
221
222#define EXPECT_POINTS_EQUAL(a, b) EXPECT_PRED_FORMAT2(ExpectPointsEqual, a, b)
223
224static void TestNegate(FileTest *t) {
225  BN_ULONG a[P256_LIMBS], b[P256_LIMBS];
226  ASSERT_TRUE(GetFieldElement(t, a, "A"));
227  ASSERT_TRUE(GetFieldElement(t, b, "B"));
228
229  // Test that -A = B.
230  BN_ULONG ret[P256_LIMBS];
231  ecp_nistz256_neg(ret, a);
232  EXPECT_FIELD_ELEMENTS_EQUAL(b, ret);
233
234  OPENSSL_memcpy(ret, a, sizeof(ret));
235  ecp_nistz256_neg(ret, ret /* a */);
236  EXPECT_FIELD_ELEMENTS_EQUAL(b, ret);
237
238  // Test that -B = A.
239  ecp_nistz256_neg(ret, b);
240  EXPECT_FIELD_ELEMENTS_EQUAL(a, ret);
241
242  OPENSSL_memcpy(ret, b, sizeof(ret));
243  ecp_nistz256_neg(ret, ret /* b */);
244  EXPECT_FIELD_ELEMENTS_EQUAL(a, ret);
245}
246
247static void TestMulMont(FileTest *t) {
248  BN_ULONG a[P256_LIMBS], b[P256_LIMBS], result[P256_LIMBS];
249  ASSERT_TRUE(GetFieldElement(t, a, "A"));
250  ASSERT_TRUE(GetFieldElement(t, b, "B"));
251  ASSERT_TRUE(GetFieldElement(t, result, "Result"));
252
253  BN_ULONG ret[P256_LIMBS];
254  ecp_nistz256_mul_mont(ret, a, b);
255  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
256
257  ecp_nistz256_mul_mont(ret, b, a);
258  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
259
260  OPENSSL_memcpy(ret, a, sizeof(ret));
261  ecp_nistz256_mul_mont(ret, ret /* a */, b);
262  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
263
264  OPENSSL_memcpy(ret, a, sizeof(ret));
265  ecp_nistz256_mul_mont(ret, b, ret);
266  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
267
268  OPENSSL_memcpy(ret, b, sizeof(ret));
269  ecp_nistz256_mul_mont(ret, a, ret /* b */);
270  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
271
272  OPENSSL_memcpy(ret, b, sizeof(ret));
273  ecp_nistz256_mul_mont(ret, ret /* b */, a);
274  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
275
276  if (OPENSSL_memcmp(a, b, sizeof(a)) == 0) {
277    ecp_nistz256_sqr_mont(ret, a);
278    EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
279
280    OPENSSL_memcpy(ret, a, sizeof(ret));
281    ecp_nistz256_sqr_mont(ret, ret /* a */);
282    EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
283  }
284}
285
286static void TestFromMont(FileTest *t) {
287  BN_ULONG a[P256_LIMBS], result[P256_LIMBS];
288  ASSERT_TRUE(GetFieldElement(t, a, "A"));
289  ASSERT_TRUE(GetFieldElement(t, result, "Result"));
290
291  BN_ULONG ret[P256_LIMBS];
292  ecp_nistz256_from_mont(ret, a);
293  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
294
295  OPENSSL_memcpy(ret, a, sizeof(ret));
296  ecp_nistz256_from_mont(ret, ret /* a */);
297  EXPECT_FIELD_ELEMENTS_EQUAL(result, ret);
298}
299
300static void TestPointAdd(FileTest *t) {
301  P256_POINT a, b;
302  P256_POINT_AFFINE result;
303  ASSERT_TRUE(GetFieldElement(t, a.X, "A.X"));
304  ASSERT_TRUE(GetFieldElement(t, a.Y, "A.Y"));
305  ASSERT_TRUE(GetFieldElement(t, a.Z, "A.Z"));
306  ASSERT_TRUE(GetFieldElement(t, b.X, "B.X"));
307  ASSERT_TRUE(GetFieldElement(t, b.Y, "B.Y"));
308  ASSERT_TRUE(GetFieldElement(t, b.Z, "B.Z"));
309  ASSERT_TRUE(GetFieldElement(t, result.X, "Result.X"));
310  ASSERT_TRUE(GetFieldElement(t, result.Y, "Result.Y"));
311
312  P256_POINT ret;
313  ecp_nistz256_point_add(&ret, &a, &b);
314  EXPECT_POINTS_EQUAL(&result, &ret);
315
316  ecp_nistz256_point_add(&ret, &b, &a);
317  EXPECT_POINTS_EQUAL(&result, &ret);
318
319  OPENSSL_memcpy(&ret, &a, sizeof(ret));
320  ecp_nistz256_point_add(&ret, &ret /* a */, &b);
321  EXPECT_POINTS_EQUAL(&result, &ret);
322
323  OPENSSL_memcpy(&ret, &a, sizeof(ret));
324  ecp_nistz256_point_add(&ret, &b, &ret /* a */);
325  EXPECT_POINTS_EQUAL(&result, &ret);
326
327  OPENSSL_memcpy(&ret, &b, sizeof(ret));
328  ecp_nistz256_point_add(&ret, &a, &ret /* b */);
329  EXPECT_POINTS_EQUAL(&result, &ret);
330
331  OPENSSL_memcpy(&ret, &b, sizeof(ret));
332  ecp_nistz256_point_add(&ret, &ret /* b */, &a);
333  EXPECT_POINTS_EQUAL(&result, &ret);
334
335  P256_POINT_AFFINE a_affine, b_affine, infinity;
336  OPENSSL_memset(&infinity, 0, sizeof(infinity));
337  ASSERT_TRUE(PointToAffine(&a_affine, &a));
338  ASSERT_TRUE(PointToAffine(&b_affine, &b));
339
340  // ecp_nistz256_point_add_affine does not work when a == b unless doubling the
341  // point at infinity.
342  if (OPENSSL_memcmp(&a_affine, &b_affine, sizeof(a_affine)) != 0 ||
343      OPENSSL_memcmp(&a_affine, &infinity, sizeof(a_affine)) == 0) {
344    ecp_nistz256_point_add_affine(&ret, &a, &b_affine);
345    EXPECT_POINTS_EQUAL(&result, &ret);
346
347    OPENSSL_memcpy(&ret, &a, sizeof(ret));
348    ecp_nistz256_point_add_affine(&ret, &ret /* a */, &b_affine);
349    EXPECT_POINTS_EQUAL(&result, &ret);
350
351    ecp_nistz256_point_add_affine(&ret, &b, &a_affine);
352    EXPECT_POINTS_EQUAL(&result, &ret);
353
354    OPENSSL_memcpy(&ret, &b, sizeof(ret));
355    ecp_nistz256_point_add_affine(&ret, &ret /* b */, &a_affine);
356    EXPECT_POINTS_EQUAL(&result, &ret);
357  }
358
359  if (OPENSSL_memcmp(&a, &b, sizeof(a)) == 0) {
360    ecp_nistz256_point_double(&ret, &a);
361    EXPECT_POINTS_EQUAL(&result, &ret);
362
363    ret = a;
364    ecp_nistz256_point_double(&ret, &ret /* a */);
365    EXPECT_POINTS_EQUAL(&result, &ret);
366  }
367}
368
369TEST(P256_X86_64Test, TestVectors) {
370  return FileTestGTest("crypto/fipsmodule/ec/p256-x86_64_tests.txt",
371                       [](FileTest *t) {
372    if (t->GetParameter() == "Negate") {
373      TestNegate(t);
374    } else if (t->GetParameter() == "MulMont") {
375      TestMulMont(t);
376    } else if (t->GetParameter() == "FromMont") {
377      TestFromMont(t);
378    } else if (t->GetParameter() == "PointAdd") {
379      TestPointAdd(t);
380    } else {
381      FAIL() << "Unknown test type:" << t->GetParameter();
382    }
383  });
384}
385
386#endif
387