tables.mx raw
1 // Copyright (c) 2019 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
4
5 package edwards25519
6
7 import (
8 "crypto/internal/fips140/subtle"
9 )
10
11 // A dynamic lookup table for variable-base, constant-time scalar muls.
12 type projLookupTable struct {
13 points [8]projCached
14 }
15
16 // A precomputed lookup table for fixed-base, constant-time scalar muls.
17 type affineLookupTable struct {
18 points [8]affineCached
19 }
20
21 // A dynamic lookup table for variable-base, variable-time scalar muls.
22 type nafLookupTable5 struct {
23 points [8]projCached
24 }
25
26 // A precomputed lookup table for fixed-base, variable-time scalar muls.
27 type nafLookupTable8 struct {
28 points [64]affineCached
29 }
30
31 // Constructors.
32
33 // Builds a lookup table at runtime. Fast.
34 func (v *projLookupTable) FromP3(q *Point) {
35 // Goal: v.points[i] = (i+1)*Q, i.e., Q, 2Q, ..., 8Q
36 // This allows lookup of -8Q, ..., -Q, 0, Q, ..., 8Q
37 v.points[0].FromP3(q)
38 tmpP3 := Point{}
39 tmpP1xP1 := projP1xP1{}
40 for i := 0; i < 7; i++ {
41 // Compute (i+1)*Q as Q + i*Q and convert to a projCached
42 // This is needlessly complicated because the API has explicit
43 // receivers instead of creating stack objects and relying on RVO
44 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.Add(q, &v.points[i])))
45 }
46 }
47
48 // This is not optimised for speed; fixed-base tables should be precomputed.
49 func (v *affineLookupTable) FromP3(q *Point) {
50 // Goal: v.points[i] = (i+1)*Q, i.e., Q, 2Q, ..., 8Q
51 // This allows lookup of -8Q, ..., -Q, 0, Q, ..., 8Q
52 v.points[0].FromP3(q)
53 tmpP3 := Point{}
54 tmpP1xP1 := projP1xP1{}
55 for i := 0; i < 7; i++ {
56 // Compute (i+1)*Q as Q + i*Q and convert to affineCached
57 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.AddAffine(q, &v.points[i])))
58 }
59 }
60
61 // Builds a lookup table at runtime. Fast.
62 func (v *nafLookupTable5) FromP3(q *Point) {
63 // Goal: v.points[i] = (2*i+1)*Q, i.e., Q, 3Q, 5Q, ..., 15Q
64 // This allows lookup of -15Q, ..., -3Q, -Q, 0, Q, 3Q, ..., 15Q
65 v.points[0].FromP3(q)
66 q2 := Point{}
67 q2.Add(q, q)
68 tmpP3 := Point{}
69 tmpP1xP1 := projP1xP1{}
70 for i := 0; i < 7; i++ {
71 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.Add(&q2, &v.points[i])))
72 }
73 }
74
75 // This is not optimised for speed; fixed-base tables should be precomputed.
76 func (v *nafLookupTable8) FromP3(q *Point) {
77 v.points[0].FromP3(q)
78 q2 := Point{}
79 q2.Add(q, q)
80 tmpP3 := Point{}
81 tmpP1xP1 := projP1xP1{}
82 for i := 0; i < 63; i++ {
83 v.points[i+1].FromP3(tmpP3.fromP1xP1(tmpP1xP1.AddAffine(&q2, &v.points[i])))
84 }
85 }
86
87 // Selectors.
88
89 // Set dest to x*Q, where -8 <= x <= 8, in constant time.
90 func (v *projLookupTable) SelectInto(dest *projCached, x int8) {
91 // Compute xabs = |x|
92 xmask := x >> 7
93 xabs := uint8((x + xmask) ^ xmask)
94
95 dest.Zero()
96 for j := 1; j <= 8; j++ {
97 // Set dest = j*Q if |x| = j
98 cond := subtle.ConstantTimeByteEq(xabs, uint8(j))
99 dest.Select(&v.points[j-1], dest, cond)
100 }
101 // Now dest = |x|*Q, conditionally negate to get x*Q
102 dest.CondNeg(int(xmask & 1))
103 }
104
105 // Set dest to x*Q, where -8 <= x <= 8, in constant time.
106 func (v *affineLookupTable) SelectInto(dest *affineCached, x int8) {
107 // Compute xabs = |x|
108 xmask := x >> 7
109 xabs := uint8((x + xmask) ^ xmask)
110
111 dest.Zero()
112 for j := 1; j <= 8; j++ {
113 // Set dest = j*Q if |x| = j
114 cond := subtle.ConstantTimeByteEq(xabs, uint8(j))
115 dest.Select(&v.points[j-1], dest, cond)
116 }
117 // Now dest = |x|*Q, conditionally negate to get x*Q
118 dest.CondNeg(int(xmask & 1))
119 }
120
121 // Given odd x with 0 < x < 2^4, return x*Q (in variable time).
122 func (v *nafLookupTable5) SelectInto(dest *projCached, x int8) {
123 *dest = v.points[x/2]
124 }
125
126 // Given odd x with 0 < x < 2^7, return x*Q (in variable time).
127 func (v *nafLookupTable8) SelectInto(dest *affineCached, x int8) {
128 *dest = v.points[x/2]
129 }
130