| 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 |
import ( |
| 18 |
"bytes" |
| 19 |
"crypto/rand" |
| 20 |
"fmt" |
| 21 |
"io" |
| 22 |
"io/ioutil" |
| 23 |
"testing" |
| 24 |
) |
| 25 |
|
| 26 |
func TestNTTRoundTrip(t *testing.T) { |
| 27 |
var a Poly |
| 28 |
for i := range a { |
| 29 |
a[i] = uint16(i) |
| 30 |
} |
| 31 |
|
| 32 |
frequency := forwardNTT(&a) |
| 33 |
original := inverseNTT(frequency) |
| 34 |
|
| 35 |
for i, v := range a { |
| 36 |
if v != original[i] { |
| 37 |
t.Errorf("NTT didn't invert correctly: original[%d] = %d", i, original[i]) |
| 38 |
break |
| 39 |
} |
| 40 |
} |
| 41 |
} |
| 42 |
|
| 43 |
func TestNTTInv(t *testing.T) { |
| 44 |
var a Poly |
| 45 |
for i := range a { |
| 46 |
a[i] = uint16(i) |
| 47 |
} |
| 48 |
|
| 49 |
result := ntt(&a, invOmega, 1, invSqrtOmega, invN) |
| 50 |
if result[0] != 6656 || result[1] != 1792 || result[2] != 1234 { |
| 51 |
t.Errorf("NTT^-1 gave bad result: %v", result[:8]) |
| 52 |
} |
| 53 |
} |
| 54 |
|
| 55 |
func disabledTestNoise(t *testing.T) { |
| 56 |
var buckets [1 + 2*k]int |
| 57 |
numSamples := 100 |
| 58 |
|
| 59 |
for i := 0; i < numSamples; i++ { |
| 60 |
noise := sampleNoise(rand.Reader) |
| 61 |
for _, v := range noise { |
| 62 |
value := (int(v) + k) % q |
| 63 |
buckets[value]++ |
| 64 |
} |
| 65 |
} |
| 66 |
|
| 67 |
sum := 0 |
| 68 |
squareSum := 0 |
| 69 |
|
| 70 |
for i, count := range buckets { |
| 71 |
sum += (i - k) * count |
| 72 |
squareSum += (i - k) * (i - k) * count |
| 73 |
} |
| 74 |
|
| 75 |
mean := float64(sum) / float64(n*numSamples) |
| 76 |
if mean < -0.5 || 0.5 < mean { |
| 77 |
t.Errorf("mean out of range: %f", mean) |
| 78 |
} |
| 79 |
|
| 80 |
expectedVariance := 0.5 * 0.5 * float64(k*2) // I think? |
| 81 |
variance := float64(squareSum)/float64(n*numSamples) - mean*mean |
| 82 |
|
| 83 |
if variance < expectedVariance-1.0 || expectedVariance+1.0 < variance { |
| 84 |
t.Errorf("variance out of range: got %f, want %f", variance, expectedVariance) |
| 85 |
} |
| 86 |
|
| 87 |
file, err := ioutil.TempFile("", "noise") |
| 88 |
fmt.Printf("writing noise to %s\n", file.Name()) |
| 89 |
if err != nil { |
| 90 |
t.Fatal(err) |
| 91 |
} |
| 92 |
for i, count := range buckets { |
| 93 |
dots := "" |
| 94 |
for i := 0; i < count/(3*numSamples); i++ { |
| 95 |
dots += "++" |
| 96 |
} |
| 97 |
fmt.Fprintf(file, "%+d\t%d\t%s\n", i-k, count, dots) |
| 98 |
} |
| 99 |
file.Close() |
| 100 |
} |
| 101 |
|
| 102 |
func TestSeedToPolynomial(t *testing.T) { |
| 103 |
seed := make([]byte, 32) |
| 104 |
seed[0] = 1 |
| 105 |
seed[31] = 2 |
| 106 |
|
| 107 |
poly := seedToPolynomial(seed) |
| 108 |
if poly[0] != 3313 || poly[1] != 9277 || poly[2] != 11020 { |
| 109 |
t.Errorf("bad result: %v", poly[:3]) |
| 110 |
} |
| 111 |
} |
| 112 |
|
| 113 |
func TestEncodeDecodePoly(t *testing.T) { |
| 114 |
poly := randomPolynomial(rand.Reader) |
| 115 |
poly2 := decodePoly(encodePoly(poly)) |
| 116 |
if *poly != *poly2 { |
| 117 |
t.Errorf("decodePoly(encodePoly) isn't the identity function") |
| 118 |
} |
| 119 |
} |
| 120 |
|
| 121 |
func TestEncodeDecodeRec(t *testing.T) { |
| 122 |
var r reconciliationData |
| 123 |
if _, err := io.ReadFull(rand.Reader, r[:]); err != nil { |
| 124 |
panic(err) |
| 125 |
} |
| 126 |
for i := range r { |
| 127 |
r[i] &= 3 |
| 128 |
} |
| 129 |
|
| 130 |
encoded := encodeRec(&r) |
| 131 |
decoded := decodeRec(encoded) |
| 132 |
|
| 133 |
if *decoded != r { |
| 134 |
t.Errorf("bad decode of rec") |
| 135 |
} |
| 136 |
} |
| 137 |
|
| 138 |
func TestExchange(t *testing.T) { |
| 139 |
for count := 0; count < 64; count++ { |
| 140 |
offerMsg, state := Offer(rand.Reader) |
| 141 |
sharedKey1, acceptMsg, err := Accept(rand.Reader, offerMsg) |
| 142 |
if err != nil { |
| 143 |
t.Errorf("Accept: %v", err) |
| 144 |
} |
| 145 |
sharedKey2, err := state.Finish(acceptMsg) |
| 146 |
if err != nil { |
| 147 |
t.Fatal("Finish: %v", err) |
| 148 |
} |
| 149 |
|
| 150 |
if !bytes.Equal(sharedKey1[:], sharedKey2[:]) { |
| 151 |
t.Fatalf("keys mismatched on iteration %d: %x vs %x", count, sharedKey1, sharedKey2) |
| 152 |
} |
| 153 |
} |
| 154 |
} |