Debian Codegraph @

external/boringssl/ssl/test/runner/newhope/reconciliation.go

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