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
|
// Polynomial fields with coefficients in GF(2)
package msp
import (
"bytes"
)
type FieldElem []byte
var (
Modulus FieldElem = []byte{135, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0} // x^128 + x^7 + x^2 + x + 1
ModulusSize int = 16
ModulusBitSize int = 128
Zero FieldElem = []byte{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
One FieldElem = []byte{1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
)
// NewFieldElem returns a new zero element.
func NewFieldElem() FieldElem {
return FieldElem(make([]byte, ModulusSize))
}
// AddM mutates e into e+f.
func (e FieldElem) AddM(f FieldElem) {
for i := 0; i < ModulusSize; i++ {
e[i] ^= f[i]
}
}
// Add returns e+f.
func (e FieldElem) Add(f FieldElem) FieldElem {
out := e.Dup()
out.AddM(f)
return out
}
// Mul returns e*f.
func (e FieldElem) Mul(f FieldElem) FieldElem {
out := NewFieldElem()
for i := 0; i < ModulusBitSize; i++ { // Foreach bit e_i in e:
if e.getCoeff(i) == 1 { // where e_i equals 1:
temp := f.Dup() // Multiply f * x^i mod M(x):
for j := 0; j < i; j++ { // Multiply f by x mod M(x), i times.
carry := temp.shift()
if carry {
temp[0] ^= Modulus[0]
}
}
out.AddM(temp) // Add f * x^i to the output
}
}
return out
}
// Exp returns e^i.
func (e FieldElem) Exp(i int) FieldElem {
out := One.Dup()
for j := 0; j < i; j++ {
out = out.Mul(e)
}
return out
}
// Invert returns the multiplicative inverse of e.
func (e FieldElem) Invert() FieldElem {
out, temp := e.Dup(), e.Dup()
for i := 0; i < 126; i++ {
temp = temp.Mul(temp)
out = out.Mul(temp)
}
return out.Mul(out)
}
// getCoeff returns the ith coefficient of the field element: either 0 or 1.
func (e FieldElem) getCoeff(i int) byte {
return (e[i/8] >> (uint(i) % 8)) & 1
}
// shift multiplies e by 2 and returns true if there was overflow and false if there wasn't.
func (e FieldElem) shift() bool {
carry := false
for i := 0; i < ModulusSize; i++ {
nextCarry := e[i] >= 128
e[i] = e[i] << 1
if carry {
e[i]++
}
carry = nextCarry
}
return carry
}
func (e FieldElem) IsZero() bool { return bytes.Compare(e, Zero) == 0 }
func (e FieldElem) IsOne() bool { return bytes.Compare(e, One) == 0 }
// Dup returns a duplicate of e.
func (e FieldElem) Dup() FieldElem {
out := FieldElem(make([]byte, ModulusSize))
copy(out, e)
return out
}
|
