1 // Copyright 2012 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.
5 // +build amd64,!gccgo,!appengine
9 // These functions are implemented in the .s files. The names of the functions
10 // in the rest of the file are also taken from the SUPERCOP sources to help
11 // people following along.
15 func cswap(inout
*[5]uint64, v
uint64)
19 func ladderstep(inout
*[5][5]uint64)
23 func freeze(inout
*[5]uint64)
27 func mul(dest
, a
, b
*[5]uint64)
31 func square(out
, in
*[5]uint64)
33 // mladder uses a Montgomery ladder to calculate (xr/zr) *= s.
34 func mladder(xr
, zr
*[5]uint64, s
*[32]byte) {
46 for i
:= 31; i
>= 0; i
-- {
48 bit
:= ((*s
)[i
] >> j
) & 1
51 cswap(&work
[1], uint64(swap
))
62 func scalarMult(out
, in
, base
*[32]byte) {
77 func setint(r
*[5]uint64, v
uint64) {
85 // unpack sets r = x where r consists of 5, 51-bit limbs in little-endian
87 func unpack(r
*[5]uint64, x
*[32]byte) {
96 r
[1] = uint64(x
[6])>>3 |
104 r
[2] = uint64(x
[12])>>6 |
113 r
[3] = uint64(x
[19])>>1 |
121 r
[4] = uint64(x
[25])>>4 |
127 uint64(x
[31]&127)<<44
130 // pack sets out = x where out is the usual, little-endian form of the 5,
131 // 51-bit limbs in x.
132 func pack(out
*[32]byte, x
*[5]uint64) {
137 out
[1] = byte(t
[0] >> 8)
138 out
[2] = byte(t
[0] >> 16)
139 out
[3] = byte(t
[0] >> 24)
140 out
[4] = byte(t
[0] >> 32)
141 out
[5] = byte(t
[0] >> 40)
142 out
[6] = byte(t
[0] >> 48)
144 out
[6] ^= byte(t
[1]<<3) & 0xf8
145 out
[7] = byte(t
[1] >> 5)
146 out
[8] = byte(t
[1] >> 13)
147 out
[9] = byte(t
[1] >> 21)
148 out
[10] = byte(t
[1] >> 29)
149 out
[11] = byte(t
[1] >> 37)
150 out
[12] = byte(t
[1] >> 45)
152 out
[12] ^= byte(t
[2]<<6) & 0xc0
153 out
[13] = byte(t
[2] >> 2)
154 out
[14] = byte(t
[2] >> 10)
155 out
[15] = byte(t
[2] >> 18)
156 out
[16] = byte(t
[2] >> 26)
157 out
[17] = byte(t
[2] >> 34)
158 out
[18] = byte(t
[2] >> 42)
159 out
[19] = byte(t
[2] >> 50)
161 out
[19] ^= byte(t
[3]<<1) & 0xfe
162 out
[20] = byte(t
[3] >> 7)
163 out
[21] = byte(t
[3] >> 15)
164 out
[22] = byte(t
[3] >> 23)
165 out
[23] = byte(t
[3] >> 31)
166 out
[24] = byte(t
[3] >> 39)
167 out
[25] = byte(t
[3] >> 47)
169 out
[25] ^= byte(t
[4]<<4) & 0xf0
170 out
[26] = byte(t
[4] >> 4)
171 out
[27] = byte(t
[4] >> 12)
172 out
[28] = byte(t
[4] >> 20)
173 out
[29] = byte(t
[4] >> 28)
174 out
[30] = byte(t
[4] >> 36)
175 out
[31] = byte(t
[4] >> 44)
178 // invert calculates r = x^-1 mod p using Fermat's little theorem.
179 func invert(r
*[5]uint64, x
*[5]uint64) {
180 var z2
, z9
, z11
, z2_5_0
, z2_10_0
, z2_20_0
, z2_50_0
, z2_100_0
, t
[5]uint64
182 square(&z2
, x
) /* 2 */
183 square(&t
, &z2
) /* 4 */
184 square(&t
, &t
) /* 8 */
185 mul(&z9
, &t
, x
) /* 9 */
186 mul(&z11
, &z9
, &z2
) /* 11 */
187 square(&t
, &z11
) /* 22 */
188 mul(&z2_5_0
, &t
, &z9
) /* 2^5 - 2^0 = 31 */
190 square(&t
, &z2_5_0
) /* 2^6 - 2^1 */
191 for i
:= 1; i
< 5; i
++ { /* 2^20 - 2^10 */
194 mul(&z2_10_0
, &t
, &z2_5_0
) /* 2^10 - 2^0 */
196 square(&t
, &z2_10_0
) /* 2^11 - 2^1 */
197 for i
:= 1; i
< 10; i
++ { /* 2^20 - 2^10 */
200 mul(&z2_20_0
, &t
, &z2_10_0
) /* 2^20 - 2^0 */
202 square(&t
, &z2_20_0
) /* 2^21 - 2^1 */
203 for i
:= 1; i
< 20; i
++ { /* 2^40 - 2^20 */
206 mul(&t
, &t
, &z2_20_0
) /* 2^40 - 2^0 */
208 square(&t
, &t
) /* 2^41 - 2^1 */
209 for i
:= 1; i
< 10; i
++ { /* 2^50 - 2^10 */
212 mul(&z2_50_0
, &t
, &z2_10_0
) /* 2^50 - 2^0 */
214 square(&t
, &z2_50_0
) /* 2^51 - 2^1 */
215 for i
:= 1; i
< 50; i
++ { /* 2^100 - 2^50 */
218 mul(&z2_100_0
, &t
, &z2_50_0
) /* 2^100 - 2^0 */
220 square(&t
, &z2_100_0
) /* 2^101 - 2^1 */
221 for i
:= 1; i
< 100; i
++ { /* 2^200 - 2^100 */
224 mul(&t
, &t
, &z2_100_0
) /* 2^200 - 2^0 */
226 square(&t
, &t
) /* 2^201 - 2^1 */
227 for i
:= 1; i
< 50; i
++ { /* 2^250 - 2^50 */
230 mul(&t
, &t
, &z2_50_0
) /* 2^250 - 2^0 */
232 square(&t
, &t
) /* 2^251 - 2^1 */
233 square(&t
, &t
) /* 2^252 - 2^2 */
234 square(&t
, &t
) /* 2^253 - 2^3 */
236 square(&t
, &t
) /* 2^254 - 2^4 */
238 square(&t
, &t
) /* 2^255 - 2^5 */
239 mul(r
, &t
, &z11
) /* 2^255 - 21 */