/
point.go
224 lines (187 loc) · 5.11 KB
/
point.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
// Package edwards25519 provides an optimized Go implementation of a
// Twisted Edwards curve that is isomorphic to Curve25519. For details see:
// http://ed25519.cr.yp.to/.
//
// This code is based on Adam Langley's Go port of the public domain,
// "ref10" implementation of the ed25519 signing scheme in C from SUPERCOP.
// It was generalized and extended to support full kyber.Group arithmetic
// by the DEDIS lab at Yale and EPFL.
//
// Due to the field element and group arithmetic optimizations
// described in the Ed25519 paper, this implementation generally
// performs extremely well, typically comparable to native C
// implementations. The tradeoff is that this code is completely
// specialized to a single curve.
package edwards25519
import (
"crypto/cipher"
"encoding/hex"
"errors"
"io"
"github.com/MarconiProtocol/kyber"
"github.com/MarconiProtocol/kyber/group/marshalling"
)
type point struct {
ge extendedGroupElement
varTime bool
}
func (P *point) String() string {
var b [32]byte
P.ge.ToBytes(&b)
return hex.EncodeToString(b[:])
}
func (P *point) MarshalSize() int {
return 32
}
func (P *point) MarshalBinary() ([]byte, error) {
var b [32]byte
P.ge.ToBytes(&b)
return b[:], nil
}
func (P *point) UnmarshalBinary(b []byte) error {
if !P.ge.FromBytes(b) {
return errors.New("invalid Ed25519 curve point")
}
return nil
}
func (P *point) MarshalTo(w io.Writer) (int, error) {
return marshalling.PointMarshalTo(P, w)
}
func (P *point) UnmarshalFrom(r io.Reader) (int, error) {
return marshalling.PointUnmarshalFrom(P, r)
}
// Equality test for two Points on the same curve
func (P *point) Equal(P2 kyber.Point) bool {
var b1, b2 [32]byte
P.ge.ToBytes(&b1)
P2.(*point).ge.ToBytes(&b2)
for i := range b1 {
if b1[i] != b2[i] {
return false
}
}
return true
}
// Set point to be equal to P2.
func (P *point) Set(P2 kyber.Point) kyber.Point {
P.ge = P2.(*point).ge
return P
}
// Set point to be equal to P2.
func (P *point) Clone() kyber.Point {
return &point{ge: P.ge}
}
// Set to the neutral element, which is (0,1) for twisted Edwards curves.
func (P *point) Null() kyber.Point {
P.ge.Zero()
return P
}
// Set to the standard base point for this curve
func (P *point) Base() kyber.Point {
P.ge = baseext
return P
}
func (P *point) EmbedLen() int {
// Reserve the most-significant 8 bits for pseudo-randomness.
// Reserve the least-significant 8 bits for embedded data length.
// (Hopefully it's unlikely we'll need >=2048-bit curves soon.)
return (255 - 8 - 8) / 8
}
func (P *point) Embed(data []byte, rand cipher.Stream) kyber.Point {
// How many bytes to embed?
dl := P.EmbedLen()
if dl > len(data) {
dl = len(data)
}
for {
// Pick a random point, with optional embedded data
var b [32]byte
rand.XORKeyStream(b[:], b[:])
if data != nil {
b[0] = byte(dl) // Encode length in low 8 bits
copy(b[1:1+dl], data) // Copy in data to embed
}
if !P.ge.FromBytes(b[:]) { // Try to decode
continue // invalid point, retry
}
// If we're using the full group,
// we just need any point on the curve, so we're done.
// if c.full {
// return P,data[dl:]
// }
// We're using the prime-order subgroup,
// so we need to make sure the point is in that subencoding.
// If we're not trying to embed data,
// we can convert our point into one in the subgroup
// simply by multiplying it by the cofactor.
if data == nil {
P.Mul(cofactorScalar, P) // multiply by cofactor
if P.Equal(nullPoint) {
continue // unlucky; try again
}
return P // success
}
// Since we need the point's y-coordinate to hold our data,
// we must simply check if the point is in the subgroup
// and retry point generation until it is.
var Q point
Q.Mul(primeOrderScalar, P)
if Q.Equal(nullPoint) {
return P // success
}
// Keep trying...
}
}
func (P *point) Pick(rand cipher.Stream) kyber.Point {
return P.Embed(nil, rand)
}
// Extract embedded data from a point group element
func (P *point) Data() ([]byte, error) {
var b [32]byte
P.ge.ToBytes(&b)
dl := int(b[0]) // extract length byte
if dl > P.EmbedLen() {
return nil, errors.New("invalid embedded data length")
}
return b[1 : 1+dl], nil
}
func (P *point) Add(P1, P2 kyber.Point) kyber.Point {
E1 := P1.(*point)
E2 := P2.(*point)
var t2 cachedGroupElement
var r completedGroupElement
E2.ge.ToCached(&t2)
r.Add(&E1.ge, &t2)
r.ToExtended(&P.ge)
return P
}
func (P *point) Sub(P1, P2 kyber.Point) kyber.Point {
E1 := P1.(*point)
E2 := P2.(*point)
var t2 cachedGroupElement
var r completedGroupElement
E2.ge.ToCached(&t2)
r.Sub(&E1.ge, &t2)
r.ToExtended(&P.ge)
return P
}
// Neg finds the negative of point A.
// For Edwards curves, the negative of (x,y) is (-x,y).
func (P *point) Neg(A kyber.Point) kyber.Point {
P.ge.Neg(&A.(*point).ge)
return P
}
// Mul multiplies point p by scalar s using the repeated doubling method.
func (P *point) Mul(s kyber.Scalar, A kyber.Point) kyber.Point {
a := &s.(*scalar).v
if A == nil {
geScalarMultBase(&P.ge, a)
} else {
if P.varTime {
geScalarMultVartime(&P.ge, a, &A.(*point).ge)
} else {
geScalarMult(&P.ge, a, &A.(*point).ge)
}
}
return P
}