main
1package ed25519
2
3import (
4 "encoding/binary"
5 "math/bits"
6)
7
8var order = [paramB]byte{
9 0xed, 0xd3, 0xf5, 0x5c, 0x1a, 0x63, 0x12, 0x58,
10 0xd6, 0x9c, 0xf7, 0xa2, 0xde, 0xf9, 0xde, 0x14,
11 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
12 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x10,
13}
14
15// isLessThan returns true if 0 <= x < y, and assumes that slices have the same length.
16func isLessThan(x, y []byte) bool {
17 i := len(x) - 1
18 for i > 0 && x[i] == y[i] {
19 i--
20 }
21 return x[i] < y[i]
22}
23
24// reduceModOrder calculates k = k mod order of the curve.
25func reduceModOrder(k []byte, is512Bit bool) {
26 var X [((2 * paramB) * 8) / 64]uint64
27 numWords := len(k) >> 3
28 for i := 0; i < numWords; i++ {
29 X[i] = binary.LittleEndian.Uint64(k[i*8 : (i+1)*8])
30 }
31 red512(&X, is512Bit)
32 for i := 0; i < numWords; i++ {
33 binary.LittleEndian.PutUint64(k[i*8:(i+1)*8], X[i])
34 }
35}
36
37// red512 calculates x = x mod Order of the curve.
38func red512(x *[8]uint64, full bool) {
39 // Implementation of Algs.(14.47)+(14.52) of Handbook of Applied
40 // Cryptography, by A. Menezes, P. van Oorschot, and S. Vanstone.
41 const (
42 ell0 = uint64(0x5812631a5cf5d3ed)
43 ell1 = uint64(0x14def9dea2f79cd6)
44 ell160 = uint64(0x812631a5cf5d3ed0)
45 ell161 = uint64(0x4def9dea2f79cd65)
46 ell162 = uint64(0x0000000000000001)
47 )
48
49 var c0, c1, c2, c3 uint64
50 r0, r1, r2, r3, r4 := x[0], x[1], x[2], x[3], uint64(0)
51
52 if full {
53 q0, q1, q2, q3 := x[4], x[5], x[6], x[7]
54
55 for i := 0; i < 3; i++ {
56 h0, s0 := bits.Mul64(q0, ell160)
57 h1, s1 := bits.Mul64(q1, ell160)
58 h2, s2 := bits.Mul64(q2, ell160)
59 h3, s3 := bits.Mul64(q3, ell160)
60
61 s1, c0 = bits.Add64(h0, s1, 0)
62 s2, c1 = bits.Add64(h1, s2, c0)
63 s3, c2 = bits.Add64(h2, s3, c1)
64 s4, _ := bits.Add64(h3, 0, c2)
65
66 h0, l0 := bits.Mul64(q0, ell161)
67 h1, l1 := bits.Mul64(q1, ell161)
68 h2, l2 := bits.Mul64(q2, ell161)
69 h3, l3 := bits.Mul64(q3, ell161)
70
71 l1, c0 = bits.Add64(h0, l1, 0)
72 l2, c1 = bits.Add64(h1, l2, c0)
73 l3, c2 = bits.Add64(h2, l3, c1)
74 l4, _ := bits.Add64(h3, 0, c2)
75
76 s1, c0 = bits.Add64(s1, l0, 0)
77 s2, c1 = bits.Add64(s2, l1, c0)
78 s3, c2 = bits.Add64(s3, l2, c1)
79 s4, c3 = bits.Add64(s4, l3, c2)
80 s5, s6 := bits.Add64(l4, 0, c3)
81
82 s2, c0 = bits.Add64(s2, q0, 0)
83 s3, c1 = bits.Add64(s3, q1, c0)
84 s4, c2 = bits.Add64(s4, q2, c1)
85 s5, c3 = bits.Add64(s5, q3, c2)
86 s6, s7 := bits.Add64(s6, 0, c3)
87
88 q := q0 | q1 | q2 | q3
89 m := -((q | -q) >> 63) // if q=0 then m=0...0 else m=1..1
90 s0 &= m
91 s1 &= m
92 s2 &= m
93 s3 &= m
94 q0, q1, q2, q3 = s4, s5, s6, s7
95
96 if (i+1)%2 == 0 {
97 r0, c0 = bits.Add64(r0, s0, 0)
98 r1, c1 = bits.Add64(r1, s1, c0)
99 r2, c2 = bits.Add64(r2, s2, c1)
100 r3, c3 = bits.Add64(r3, s3, c2)
101 r4, _ = bits.Add64(r4, 0, c3)
102 } else {
103 r0, c0 = bits.Sub64(r0, s0, 0)
104 r1, c1 = bits.Sub64(r1, s1, c0)
105 r2, c2 = bits.Sub64(r2, s2, c1)
106 r3, c3 = bits.Sub64(r3, s3, c2)
107 r4, _ = bits.Sub64(r4, 0, c3)
108 }
109 }
110
111 m := -(r4 >> 63)
112 r0, c0 = bits.Add64(r0, m&ell160, 0)
113 r1, c1 = bits.Add64(r1, m&ell161, c0)
114 r2, c2 = bits.Add64(r2, m&ell162, c1)
115 r3, c3 = bits.Add64(r3, 0, c2)
116 r4, _ = bits.Add64(r4, m&1, c3)
117 x[4], x[5], x[6], x[7] = 0, 0, 0, 0
118 }
119
120 q0 := (r4 << 4) | (r3 >> 60)
121 r3 &= (uint64(1) << 60) - 1
122
123 h0, s0 := bits.Mul64(ell0, q0)
124 h1, s1 := bits.Mul64(ell1, q0)
125 s1, c0 = bits.Add64(h0, s1, 0)
126 s2, _ := bits.Add64(h1, 0, c0)
127
128 r0, c0 = bits.Sub64(r0, s0, 0)
129 r1, c1 = bits.Sub64(r1, s1, c0)
130 r2, c2 = bits.Sub64(r2, s2, c1)
131 r3, _ = bits.Sub64(r3, 0, c2)
132
133 x[0], x[1], x[2], x[3] = r0, r1, r2, r3
134}
135
136// calculateS performs s = r+k*a mod Order of the curve.
137func calculateS(s, r, k, a []byte) {
138 K := [4]uint64{
139 binary.LittleEndian.Uint64(k[0*8 : 1*8]),
140 binary.LittleEndian.Uint64(k[1*8 : 2*8]),
141 binary.LittleEndian.Uint64(k[2*8 : 3*8]),
142 binary.LittleEndian.Uint64(k[3*8 : 4*8]),
143 }
144 S := [8]uint64{
145 binary.LittleEndian.Uint64(r[0*8 : 1*8]),
146 binary.LittleEndian.Uint64(r[1*8 : 2*8]),
147 binary.LittleEndian.Uint64(r[2*8 : 3*8]),
148 binary.LittleEndian.Uint64(r[3*8 : 4*8]),
149 }
150 var c3 uint64
151 for i := range K {
152 ai := binary.LittleEndian.Uint64(a[i*8 : (i+1)*8])
153
154 h0, l0 := bits.Mul64(K[0], ai)
155 h1, l1 := bits.Mul64(K[1], ai)
156 h2, l2 := bits.Mul64(K[2], ai)
157 h3, l3 := bits.Mul64(K[3], ai)
158
159 l1, c0 := bits.Add64(h0, l1, 0)
160 l2, c1 := bits.Add64(h1, l2, c0)
161 l3, c2 := bits.Add64(h2, l3, c1)
162 l4, _ := bits.Add64(h3, 0, c2)
163
164 S[i+0], c0 = bits.Add64(S[i+0], l0, 0)
165 S[i+1], c1 = bits.Add64(S[i+1], l1, c0)
166 S[i+2], c2 = bits.Add64(S[i+2], l2, c1)
167 S[i+3], c3 = bits.Add64(S[i+3], l3, c2)
168 S[i+4], _ = bits.Add64(S[i+4], l4, c3)
169 }
170 red512(&S, true)
171 binary.LittleEndian.PutUint64(s[0*8:1*8], S[0])
172 binary.LittleEndian.PutUint64(s[1*8:2*8], S[1])
173 binary.LittleEndian.PutUint64(s[2*8:3*8], S[2])
174 binary.LittleEndian.PutUint64(s[3*8:4*8], S[3])
175}