| 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 |
} |