1
2
3
4
5 package nistec_test
6
7 import (
8 "bytes"
9 "crypto/elliptic"
10 "crypto/internal/nistec"
11 "fmt"
12 "internal/testenv"
13 "math/big"
14 "math/rand"
15 "testing"
16 )
17
18 func TestAllocations(t *testing.T) {
19 testenv.SkipIfOptimizationOff(t)
20
21 t.Run("P224", func(t *testing.T) {
22 if allocs := testing.AllocsPerRun(10, func() {
23 p := nistec.NewP224Point().SetGenerator()
24 scalar := make([]byte, 28)
25 rand.Read(scalar)
26 p.ScalarBaseMult(scalar)
27 p.ScalarMult(p, scalar)
28 out := p.Bytes()
29 if _, err := nistec.NewP224Point().SetBytes(out); err != nil {
30 t.Fatal(err)
31 }
32 out = p.BytesCompressed()
33 if _, err := p.SetBytes(out); err != nil {
34 t.Fatal(err)
35 }
36 }); allocs > 0 {
37 t.Errorf("expected zero allocations, got %0.1f", allocs)
38 }
39 })
40 t.Run("P256", func(t *testing.T) {
41 if allocs := testing.AllocsPerRun(10, func() {
42 p := nistec.NewP256Point().SetGenerator()
43 scalar := make([]byte, 32)
44 rand.Read(scalar)
45 p.ScalarBaseMult(scalar)
46 p.ScalarMult(p, scalar)
47 out := p.Bytes()
48 if _, err := nistec.NewP256Point().SetBytes(out); err != nil {
49 t.Fatal(err)
50 }
51 out = p.BytesCompressed()
52 if _, err := p.SetBytes(out); err != nil {
53 t.Fatal(err)
54 }
55 }); allocs > 0 {
56 t.Errorf("expected zero allocations, got %0.1f", allocs)
57 }
58 })
59 t.Run("P384", func(t *testing.T) {
60 if allocs := testing.AllocsPerRun(10, func() {
61 p := nistec.NewP384Point().SetGenerator()
62 scalar := make([]byte, 48)
63 rand.Read(scalar)
64 p.ScalarBaseMult(scalar)
65 p.ScalarMult(p, scalar)
66 out := p.Bytes()
67 if _, err := nistec.NewP384Point().SetBytes(out); err != nil {
68 t.Fatal(err)
69 }
70 out = p.BytesCompressed()
71 if _, err := p.SetBytes(out); err != nil {
72 t.Fatal(err)
73 }
74 }); allocs > 0 {
75 t.Errorf("expected zero allocations, got %0.1f", allocs)
76 }
77 })
78 t.Run("P521", func(t *testing.T) {
79 if allocs := testing.AllocsPerRun(10, func() {
80 p := nistec.NewP521Point().SetGenerator()
81 scalar := make([]byte, 66)
82 rand.Read(scalar)
83 p.ScalarBaseMult(scalar)
84 p.ScalarMult(p, scalar)
85 out := p.Bytes()
86 if _, err := nistec.NewP521Point().SetBytes(out); err != nil {
87 t.Fatal(err)
88 }
89 out = p.BytesCompressed()
90 if _, err := p.SetBytes(out); err != nil {
91 t.Fatal(err)
92 }
93 }); allocs > 0 {
94 t.Errorf("expected zero allocations, got %0.1f", allocs)
95 }
96 })
97 }
98
99 type nistPoint[T any] interface {
100 Bytes() []byte
101 SetGenerator() T
102 SetBytes([]byte) (T, error)
103 Add(T, T) T
104 Double(T) T
105 ScalarMult(T, []byte) (T, error)
106 ScalarBaseMult([]byte) (T, error)
107 }
108
109 func TestEquivalents(t *testing.T) {
110 t.Run("P224", func(t *testing.T) {
111 testEquivalents(t, nistec.NewP224Point, elliptic.P224())
112 })
113 t.Run("P256", func(t *testing.T) {
114 testEquivalents(t, nistec.NewP256Point, elliptic.P256())
115 })
116 t.Run("P384", func(t *testing.T) {
117 testEquivalents(t, nistec.NewP384Point, elliptic.P384())
118 })
119 t.Run("P521", func(t *testing.T) {
120 testEquivalents(t, nistec.NewP521Point, elliptic.P521())
121 })
122 }
123
124 func testEquivalents[P nistPoint[P]](t *testing.T, newPoint func() P, c elliptic.Curve) {
125 p := newPoint().SetGenerator()
126
127 elementSize := (c.Params().BitSize + 7) / 8
128 two := make([]byte, elementSize)
129 two[len(two)-1] = 2
130 nPlusTwo := make([]byte, elementSize)
131 new(big.Int).Add(c.Params().N, big.NewInt(2)).FillBytes(nPlusTwo)
132
133 p1 := newPoint().Double(p)
134 p2 := newPoint().Add(p, p)
135 p3, err := newPoint().ScalarMult(p, two)
136 fatalIfErr(t, err)
137 p4, err := newPoint().ScalarBaseMult(two)
138 fatalIfErr(t, err)
139 p5, err := newPoint().ScalarMult(p, nPlusTwo)
140 fatalIfErr(t, err)
141 p6, err := newPoint().ScalarBaseMult(nPlusTwo)
142 fatalIfErr(t, err)
143
144 if !bytes.Equal(p1.Bytes(), p2.Bytes()) {
145 t.Error("P+P != 2*P")
146 }
147 if !bytes.Equal(p1.Bytes(), p3.Bytes()) {
148 t.Error("P+P != [2]P")
149 }
150 if !bytes.Equal(p1.Bytes(), p4.Bytes()) {
151 t.Error("G+G != [2]G")
152 }
153 if !bytes.Equal(p1.Bytes(), p5.Bytes()) {
154 t.Error("P+P != [N+2]P")
155 }
156 if !bytes.Equal(p1.Bytes(), p6.Bytes()) {
157 t.Error("G+G != [N+2]G")
158 }
159 }
160
161 func TestScalarMult(t *testing.T) {
162 t.Run("P224", func(t *testing.T) {
163 testScalarMult(t, nistec.NewP224Point, elliptic.P224())
164 })
165 t.Run("P256", func(t *testing.T) {
166 testScalarMult(t, nistec.NewP256Point, elliptic.P256())
167 })
168 t.Run("P384", func(t *testing.T) {
169 testScalarMult(t, nistec.NewP384Point, elliptic.P384())
170 })
171 t.Run("P521", func(t *testing.T) {
172 testScalarMult(t, nistec.NewP521Point, elliptic.P521())
173 })
174 }
175
176 func testScalarMult[P nistPoint[P]](t *testing.T, newPoint func() P, c elliptic.Curve) {
177 G := newPoint().SetGenerator()
178 checkScalar := func(t *testing.T, scalar []byte) {
179 p1, err := newPoint().ScalarBaseMult(scalar)
180 fatalIfErr(t, err)
181 p2, err := newPoint().ScalarMult(G, scalar)
182 fatalIfErr(t, err)
183 if !bytes.Equal(p1.Bytes(), p2.Bytes()) {
184 t.Error("[k]G != ScalarBaseMult(k)")
185 }
186
187 expectInfinity := new(big.Int).Mod(new(big.Int).SetBytes(scalar), c.Params().N).Sign() == 0
188 if expectInfinity {
189 if !bytes.Equal(p1.Bytes(), newPoint().Bytes()) {
190 t.Error("ScalarBaseMult(k) != ∞")
191 }
192 if !bytes.Equal(p2.Bytes(), newPoint().Bytes()) {
193 t.Error("[k]G != ∞")
194 }
195 } else {
196 if bytes.Equal(p1.Bytes(), newPoint().Bytes()) {
197 t.Error("ScalarBaseMult(k) == ∞")
198 }
199 if bytes.Equal(p2.Bytes(), newPoint().Bytes()) {
200 t.Error("[k]G == ∞")
201 }
202 }
203
204 d := new(big.Int).SetBytes(scalar)
205 d.Sub(c.Params().N, d)
206 d.Mod(d, c.Params().N)
207 g1, err := newPoint().ScalarBaseMult(d.FillBytes(make([]byte, len(scalar))))
208 fatalIfErr(t, err)
209 g1.Add(g1, p1)
210 if !bytes.Equal(g1.Bytes(), newPoint().Bytes()) {
211 t.Error("[N - k]G + [k]G != ∞")
212 }
213 }
214
215 byteLen := len(c.Params().N.Bytes())
216 bitLen := c.Params().N.BitLen()
217 t.Run("0", func(t *testing.T) { checkScalar(t, make([]byte, byteLen)) })
218 t.Run("1", func(t *testing.T) {
219 checkScalar(t, big.NewInt(1).FillBytes(make([]byte, byteLen)))
220 })
221 t.Run("N-1", func(t *testing.T) {
222 checkScalar(t, new(big.Int).Sub(c.Params().N, big.NewInt(1)).Bytes())
223 })
224 t.Run("N", func(t *testing.T) { checkScalar(t, c.Params().N.Bytes()) })
225 t.Run("N+1", func(t *testing.T) {
226 checkScalar(t, new(big.Int).Add(c.Params().N, big.NewInt(1)).Bytes())
227 })
228 t.Run("all1s", func(t *testing.T) {
229 s := new(big.Int).Lsh(big.NewInt(1), uint(bitLen))
230 s.Sub(s, big.NewInt(1))
231 checkScalar(t, s.Bytes())
232 })
233 if testing.Short() {
234 return
235 }
236 for i := 0; i < bitLen; i++ {
237 t.Run(fmt.Sprintf("1<<%d", i), func(t *testing.T) {
238 s := new(big.Int).Lsh(big.NewInt(1), uint(i))
239 checkScalar(t, s.FillBytes(make([]byte, byteLen)))
240 })
241 }
242 for i := 0; i <= 64; i++ {
243 t.Run(fmt.Sprintf("%d", i), func(t *testing.T) {
244 checkScalar(t, big.NewInt(int64(i)).FillBytes(make([]byte, byteLen)))
245 })
246 }
247
248
249 for i := int64(-64); i <= 64; i++ {
250 t.Run(fmt.Sprintf("N%+d", i), func(t *testing.T) {
251 checkScalar(t, new(big.Int).Add(c.Params().N, big.NewInt(i)).Bytes())
252 })
253 }
254 }
255
256 func fatalIfErr(t *testing.T, err error) {
257 t.Helper()
258 if err != nil {
259 t.Fatal(err)
260 }
261 }
262
263 func BenchmarkScalarMult(b *testing.B) {
264 b.Run("P224", func(b *testing.B) {
265 benchmarkScalarMult(b, nistec.NewP224Point().SetGenerator(), 28)
266 })
267 b.Run("P256", func(b *testing.B) {
268 benchmarkScalarMult(b, nistec.NewP256Point().SetGenerator(), 32)
269 })
270 b.Run("P384", func(b *testing.B) {
271 benchmarkScalarMult(b, nistec.NewP384Point().SetGenerator(), 48)
272 })
273 b.Run("P521", func(b *testing.B) {
274 benchmarkScalarMult(b, nistec.NewP521Point().SetGenerator(), 66)
275 })
276 }
277
278 func benchmarkScalarMult[P nistPoint[P]](b *testing.B, p P, scalarSize int) {
279 scalar := make([]byte, scalarSize)
280 rand.Read(scalar)
281 b.ReportAllocs()
282 b.ResetTimer()
283 for i := 0; i < b.N; i++ {
284 p.ScalarMult(p, scalar)
285 }
286 }
287
288 func BenchmarkScalarBaseMult(b *testing.B) {
289 b.Run("P224", func(b *testing.B) {
290 benchmarkScalarBaseMult(b, nistec.NewP224Point().SetGenerator(), 28)
291 })
292 b.Run("P256", func(b *testing.B) {
293 benchmarkScalarBaseMult(b, nistec.NewP256Point().SetGenerator(), 32)
294 })
295 b.Run("P384", func(b *testing.B) {
296 benchmarkScalarBaseMult(b, nistec.NewP384Point().SetGenerator(), 48)
297 })
298 b.Run("P521", func(b *testing.B) {
299 benchmarkScalarBaseMult(b, nistec.NewP521Point().SetGenerator(), 66)
300 })
301 }
302
303 func benchmarkScalarBaseMult[P nistPoint[P]](b *testing.B, p P, scalarSize int) {
304 scalar := make([]byte, scalarSize)
305 rand.Read(scalar)
306 b.ReportAllocs()
307 b.ResetTimer()
308 for i := 0; i < b.N; i++ {
309 p.ScalarBaseMult(scalar)
310 }
311 }
312
View as plain text