| 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 |
package newhope |
| 16 |
|
| 17 |
// This file contains the reconciliation algorithm for NewHope. This is simply a |
| 18 |
// monkey-see-monkey-do version of the reference code, with the exception that |
| 19 |
// the key resulting from reconciliation is whitened with SHA2 rather than SHA3. |
| 20 |
// |
| 21 |
// Thanks to the authors of the reference code for allowing us to release this |
| 22 |
// under the BoringSSL license. |
| 23 |
|
| 24 |
import ( |
| 25 |
"crypto/sha256" |
| 26 |
"io" |
| 27 |
) |
| 28 |
|
| 29 |
func abs(v int32) int32 { |
| 30 |
mask := v >> 31 |
| 31 |
return (v ^ mask) - mask |
| 32 |
} |
| 33 |
|
| 34 |
func f(x int32) (v0, v1, k int32) { |
| 35 |
// Next 6 lines compute t = x/q; |
| 36 |
b := x * 2730 |
| 37 |
t := b >> 25 |
| 38 |
b = x - t*12289 |
| 39 |
b = 12288 - b |
| 40 |
b >>= 31 |
| 41 |
t -= b |
| 42 |
|
| 43 |
r := t & 1 |
| 44 |
xit := (t >> 1) |
| 45 |
v0 = xit + r // v0 = round(x/(2*q)) |
| 46 |
|
| 47 |
t -= 1 |
| 48 |
r = t & 1 |
| 49 |
v1 = (t >> 1) + r |
| 50 |
|
| 51 |
k = abs(x - (v0 * 2 * q)) |
| 52 |
return |
| 53 |
} |
| 54 |
|
| 55 |
// reconciliationData is the data needed for reconciliation. There are 2 bits |
| 56 |
// per coefficient; this is the unpacked form. |
| 57 |
type reconciliationData [n]uint8 |
| 58 |
|
| 59 |
func helprec(rand io.Reader, v *Poly) *reconciliationData { |
| 60 |
var randBits [n / (4 * 8)]byte |
| 61 |
if _, err := io.ReadFull(rand, randBits[:]); err != nil { |
| 62 |
panic(err) |
| 63 |
} |
| 64 |
|
| 65 |
ret := new(reconciliationData) |
| 66 |
|
| 67 |
for i := uint(0); i < n/4; i++ { |
| 68 |
rbit := int32((randBits[i>>3] >> (i & 7)) & 1) |
| 69 |
|
| 70 |
a0, b0, k0 := f(8*int32(v[i]) + 4*rbit) |
| 71 |
a1, b1, k1 := f(8*int32(v[256+i]) + 4*rbit) |
| 72 |
a2, b2, k2 := f(8*int32(v[512+i]) + 4*rbit) |
| 73 |
a3, b3, k3 := f(8*int32(v[768+i]) + 4*rbit) |
| 74 |
|
| 75 |
k := (2*q - 1 - (k0 + k1 + k2 + k3)) >> 31 |
| 76 |
|
| 77 |
v0 := ((^k) & a0) ^ (k & b0) |
| 78 |
v1 := ((^k) & a1) ^ (k & b1) |
| 79 |
v2 := ((^k) & a2) ^ (k & b2) |
| 80 |
v3 := ((^k) & a3) ^ (k & b3) |
| 81 |
|
| 82 |
ret[i] = uint8((v0 - v3) & 3) |
| 83 |
ret[i+256] = uint8((v1 - v3) & 3) |
| 84 |
ret[i+512] = uint8((v2 - v3) & 3) |
| 85 |
ret[i+768] = uint8((-k + 2*v3) & 3) |
| 86 |
} |
| 87 |
|
| 88 |
return ret |
| 89 |
} |
| 90 |
|
| 91 |
func g(x int32) int32 { |
| 92 |
// Next 6 lines compute t = x/(4*q); |
| 93 |
b := x * 2730 |
| 94 |
t := b >> 27 |
| 95 |
b = x - t*49156 |
| 96 |
b = 49155 - b |
| 97 |
b >>= 31 |
| 98 |
t -= b |
| 99 |
|
| 100 |
c := t & 1 |
| 101 |
t = (t >> 1) + c // t = round(x/(8*q)) |
| 102 |
|
| 103 |
t *= 8 * q |
| 104 |
|
| 105 |
return abs(t - x) |
| 106 |
} |
| 107 |
|
| 108 |
func ldDecode(xi0, xi1, xi2, xi3 int32) uint8 { |
| 109 |
t := g(xi0) |
| 110 |
t += g(xi1) |
| 111 |
t += g(xi2) |
| 112 |
t += g(xi3) |
| 113 |
|
| 114 |
t -= 8 * q |
| 115 |
t >>= 31 |
| 116 |
return uint8(t & 1) |
| 117 |
} |
| 118 |
|
| 119 |
func reconcile(v *Poly, reconciliation *reconciliationData) Key { |
| 120 |
key := new(Key) |
| 121 |
|
| 122 |
for i := uint(0); i < n/4; i++ { |
| 123 |
t0 := 16*q + 8*int32(v[i]) - q*(2*int32(reconciliation[i])+int32(reconciliation[i+768])) |
| 124 |
t1 := 16*q + 8*int32(v[i+256]) - q*(2*int32(reconciliation[256+i])+int32(reconciliation[i+768])) |
| 125 |
t2 := 16*q + 8*int32(v[i+512]) - q*(2*int32(reconciliation[512+i])+int32(reconciliation[i+768])) |
| 126 |
t3 := 16*q + 8*int32(v[i+768]) - q*int32(reconciliation[i+768]) |
| 127 |
|
| 128 |
key[i>>3] |= ldDecode(t0, t1, t2, t3) << (i & 7) |
| 129 |
} |
| 130 |
|
| 131 |
return sha256.Sum256(key[:]) |
| 132 |
} |