Debian Codegraph @

external/boringssl/crypto/newhope/error_correction.c

raw
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 #include <string.h>
16
17 #include <openssl/base.h>
18 #include <openssl/rand.h>
19
20 #include "internal.h"
21
22
23 /* See paper for details on the error reconciliation */
24
25 static int32_t abs_32(int32_t v) {
26 int32_t mask = v >> 31;
27 return (v ^ mask) - mask;
28 }
29
30 static int32_t f(int32_t* v0, int32_t* v1, int32_t x) {
31 int32_t xit, t, r, b;
32
33 /* Next 6 lines compute t = x/PARAM_Q */
34 b = x * 2730;
35 t = b >> 25;
36 b = x - t * 12289;
37 b = 12288 - b;
38 b >>= 31;
39 t -= b;
40
41 r = t & 1;
42 xit = (t >> 1);
43 *v0 = xit + r; /* v0 = round(x/(2*PARAM_Q)) */
44
45 t -= 1;
46 r = t & 1;
47 *v1 = (t >> 1) + r;
48
49 return abs_32(x - ((*v0) * 2 * PARAM_Q));
50 }
51
52 static int32_t g(int32_t x) {
53 int32_t t, c, b;
54
55 /* Next 6 lines compute t = x/(4*PARAM_Q); */
56 b = x * 2730;
57 t = b >> 27;
58 b = x - t * 49156;
59 b = 49155 - b;
60 b >>= 31;
61 t -= b;
62
63 c = t & 1;
64 t = (t >> 1) + c; /* t = round(x/(8*PARAM_Q)) */
65
66 t *= 8 * PARAM_Q;
67
68 return abs_32(t - x);
69 }
70
71 static int16_t LDDecode(int32_t xi0, int32_t xi1, int32_t xi2, int32_t xi3) {
72 int32_t t;
73
74 t = g(xi0);
75 t += g(xi1);
76 t += g(xi2);
77 t += g(xi3);
78
79 t -= 8 * PARAM_Q;
80 t >>= 31;
81 return t & 1;
82 }
83
84 void newhope_helprec(NEWHOPE_POLY* c, const NEWHOPE_POLY* v,
85 const uint8_t rand[32]) {
86 int32_t v0[4], v1[4], v_tmp[4], k;
87 uint8_t rbit;
88 unsigned i;
89
90 for (i = 0; i < 256; i++) {
91 rbit = (rand[i >> 3] >> (i & 7)) & 1;
92
93 k = f(v0 + 0, v1 + 0, 8 * v->coeffs[0 + i] + 4 * rbit);
94 k += f(v0 + 1, v1 + 1, 8 * v->coeffs[256 + i] + 4 * rbit);
95 k += f(v0 + 2, v1 + 2, 8 * v->coeffs[512 + i] + 4 * rbit);
96 k += f(v0 + 3, v1 + 3, 8 * v->coeffs[768 + i] + 4 * rbit);
97
98 k = (2 * PARAM_Q - 1 - k) >> 31;
99
100 v_tmp[0] = ((~k) & v0[0]) ^ (k & v1[0]);
101 v_tmp[1] = ((~k) & v0[1]) ^ (k & v1[1]);
102 v_tmp[2] = ((~k) & v0[2]) ^ (k & v1[2]);
103 v_tmp[3] = ((~k) & v0[3]) ^ (k & v1[3]);
104
105 c->coeffs[0 + i] = (v_tmp[0] - v_tmp[3]) & 3;
106 c->coeffs[256 + i] = (v_tmp[1] - v_tmp[3]) & 3;
107 c->coeffs[512 + i] = (v_tmp[2] - v_tmp[3]) & 3;
108 c->coeffs[768 + i] = (-k + 2 * v_tmp[3]) & 3;
109 }
110 }
111
112 void newhope_reconcile(uint8_t* key, const NEWHOPE_POLY* v,
113 const NEWHOPE_POLY* c) {
114 int i;
115 int32_t tmp[4];
116
117 memset(key, 0, NEWHOPE_KEY_LENGTH);
118
119 for (i = 0; i < 256; i++) {
120 tmp[0] = 16 * PARAM_Q + 8 * (int32_t)v->coeffs[0 + i] -
121 PARAM_Q * (2 * c->coeffs[0 + i] + c->coeffs[768 + i]);
122 tmp[1] = 16 * PARAM_Q + 8 * (int32_t)v->coeffs[256 + i] -
123 PARAM_Q * (2 * c->coeffs[256 + i] + c->coeffs[768 + i]);
124 tmp[2] = 16 * PARAM_Q + 8 * (int32_t)v->coeffs[512 + i] -
125 PARAM_Q * (2 * c->coeffs[512 + i] + c->coeffs[768 + i]);
126 tmp[3] = 16 * PARAM_Q + 8 * (int32_t)v->coeffs[768 + i] -
127 PARAM_Q * (c->coeffs[768 + i]);
128
129 key[i >> 3] |= LDDecode(tmp[0], tmp[1], tmp[2], tmp[3]) << (i & 7);
130 }
131 }