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
|
package csidh
import (
"fmt"
"math/big"
mrand "math/rand"
)
// Commonly used variables
var (
// Number of interations
numIter = 10
// Modulus
modulus, _ = new(big.Int).SetString(fp2S(p), 16)
// Zero in fp
zeroFp512 = fp{}
// One in fp
oneFp512 = fp{1, 0, 0, 0, 0, 0, 0, 0}
)
// Converts dst to Montgomery if "toMont==true" or from Montgomery domain otherwise.
func toMont(dst *big.Int, toMont bool) {
var bigP, bigR big.Int
intSetU64(&bigP, p[:])
bigR.SetUint64(1)
bigR.Lsh(&bigR, 512)
if !toMont {
bigR.ModInverse(&bigR, &bigP)
}
dst.Mul(dst, &bigR)
dst.Mod(dst, &bigP)
}
func fp2S(v fp) string {
var str string
for i := 0; i < 8; i++ {
str = fmt.Sprintf("%016x", v[i]) + str
}
return str
}
// zeroize fp
func zero(v *fp) {
for i := range *v {
v[i] = 0
}
}
// returns random value in a range (0,p)
func randomFp() fp {
var u fp
for i := 0; i < 8; i++ {
u[i] = mrand.Uint64()
}
return u
}
// x<y: <0
// x>y: >0
// x==y: 0
func cmp512(x, y *fp) int {
if len(*x) == len(*y) {
for i := len(*x) - 1; i >= 0; i-- {
if x[i] < y[i] {
return -1
} else if x[i] > y[i] {
return 1
}
}
return 0
}
return len(*x) - len(*y)
}
// return x==y for fp
func ceqFp(l, r *fp) bool {
for idx := range l {
if l[idx] != r[idx] {
return false
}
}
return true
}
// return x==y for point
func ceqpoint(l, r *point) bool {
return ceqFp(&l.x, &r.x) && ceqFp(&l.z, &r.z)
}
// return x==y
func ceq512(x, y *fp) bool {
return cmp512(x, y) == 0
}
// Converts src to big.Int. Function assumes that src is a slice of uint64
// values encoded in little-endian byte order.
func intSetU64(dst *big.Int, src []uint64) *big.Int {
var tmp big.Int
dst.SetUint64(0)
for i := range src {
tmp.SetUint64(src[i])
tmp.Lsh(&tmp, uint(i*64))
dst.Add(dst, &tmp)
}
return dst
}
// Converts src to an array of uint64 values encoded in little-endian
// byte order.
func intGetU64(src *big.Int) []uint64 {
var tmp, mod big.Int
dst := make([]uint64, (src.BitLen()/64)+1)
u64 := uint64(0)
u64--
mod.SetUint64(u64)
for i := 0; i < (src.BitLen()/64)+1; i++ {
tmp.Set(src)
tmp.Rsh(&tmp, uint(i)*64)
tmp.And(&tmp, &mod)
dst[i] = tmp.Uint64()
}
return dst
}
// Returns projective coordinate X of normalized EC 'point' (point.x / point.z).
func toNormX(point *point) big.Int {
var bigP, bigDnt, bigDor big.Int
intSetU64(&bigP, p[:])
intSetU64(&bigDnt, point.x[:])
intSetU64(&bigDor, point.z[:])
bigDor.ModInverse(&bigDor, &bigP)
bigDnt.Mul(&bigDnt, &bigDor)
bigDnt.Mod(&bigDnt, &bigP)
return bigDnt
}
// Converts string to fp element in Montgomery domain of cSIDH-512
func toFp(num string) fp {
var tmp big.Int
var ok bool
var ret fp
_, ok = tmp.SetString(num, 0)
if !ok {
panic("Can't parse a number")
}
toMont(&tmp, true)
copy(ret[:], intGetU64(&tmp))
return ret
}
|
