scalar.mx raw
1 package gnarl
2
3 // Scalar arithmetic modulo Q (~213-bit prime subgroup order).
4 // 4x uint64 little-endian limbs, NOT Montgomery form.
5
6 import (
7 "crypto/rand"
8 "math/big"
9 "math/bits"
10 )
11
12 type scalar [4]uint64
13
14 var qLimbs scalar
15 var scZero scalar
16 var scOneVal scalar
17
18 func initScalarConstants() {
19 qLimbs = scalar{0xdda9942fad452629, 0xd85a69a223c0776e, 0x1e7959f44807ba64, 0x000000000018e5f1}
20 scOneVal = scalar{1, 0, 0, 0}
21 }
22
23 func scIsZero(s *scalar) (result bool) {
24 return (s[0] | s[1] | s[2] | s[3]) == 0
25 }
26
27 func scGte(a, b *scalar) (result bool) {
28 var borrow uint64
29 _, borrow = bits.Sub64(a[0], b[0], 0)
30 _, borrow = bits.Sub64(a[1], b[1], borrow)
31 _, borrow = bits.Sub64(a[2], b[2], borrow)
32 _, borrow = bits.Sub64(a[3], b[3], borrow)
33 return borrow == 0
34 }
35
36 // scReduce reduces s to [0, Q) using math/big.
37 func scReduce(s *scalar) {
38 if !scGte(s, &qLimbs) {
39 return
40 }
41 val := &big.Int{}
42 val.SetUint64(s[3])
43 val.Lsh(val, 64)
44 val.Or(val, (&big.Int{}).SetUint64(s[2]))
45 val.Lsh(val, 64)
46 val.Or(val, (&big.Int{}).SetUint64(s[1]))
47 val.Lsh(val, 64)
48 val.Or(val, (&big.Int{}).SetUint64(s[0]))
49 val.Mod(val, qBig)
50
51 mask64 := (&big.Int{}).SetUint64(0xFFFFFFFFFFFFFFFF)
52 s[0] = (&big.Int{}).And(val, mask64).Uint64()
53 val.Rsh(val, 64)
54 s[1] = (&big.Int{}).And(val, mask64).Uint64()
55 val.Rsh(val, 64)
56 s[2] = (&big.Int{}).And(val, mask64).Uint64()
57 val.Rsh(val, 64)
58 s[3] = val.Uint64()
59 }
60
61 func scAdd(r, a, b *scalar) {
62 var carry, borrow, underflow uint64
63 var d0, d1, d2, d3 uint64
64 r[0], carry = bits.Add64(a[0], b[0], 0)
65 r[1], carry = bits.Add64(a[1], b[1], carry)
66 r[2], carry = bits.Add64(a[2], b[2], carry)
67 r[3], carry = bits.Add64(a[3], b[3], carry)
68
69 d0, borrow = bits.Sub64(r[0], qLimbs[0], 0)
70 d1, borrow = bits.Sub64(r[1], qLimbs[1], borrow)
71 d2, borrow = bits.Sub64(r[2], qLimbs[2], borrow)
72 d3, borrow = bits.Sub64(r[3], qLimbs[3], borrow)
73
74 underflow = borrow &^ carry
75 mask := uint64(0) - underflow
76 r[0] = (r[0] & mask) | (d0 & ^mask)
77 r[1] = (r[1] & mask) | (d1 & ^mask)
78 r[2] = (r[2] & mask) | (d2 & ^mask)
79 r[3] = (r[3] & mask) | (d3 & ^mask)
80 }
81
82 func scSub(r, a, b *scalar) {
83 var borrow, carry uint64
84 r[0], borrow = bits.Sub64(a[0], b[0], 0)
85 r[1], borrow = bits.Sub64(a[1], b[1], borrow)
86 r[2], borrow = bits.Sub64(a[2], b[2], borrow)
87 r[3], borrow = bits.Sub64(a[3], b[3], borrow)
88
89 mask := uint64(0) - borrow
90 r[0], carry = bits.Add64(r[0], qLimbs[0]&mask, 0)
91 r[1], carry = bits.Add64(r[1], qLimbs[1]&mask, carry)
92 r[2], carry = bits.Add64(r[2], qLimbs[2]&mask, carry)
93 r[3], _ = bits.Add64(r[3], qLimbs[3]&mask, carry)
94 }
95
96 func scNeg(r, a *scalar) {
97 scSub(r, &scZero, a)
98 }
99
100 // scMul computes r = a * b mod Q using math/big.
101 func scMul(r, a, b *scalar) {
102 var abuf, bbuf [27]byte
103 scToBytes27(abuf[:], a)
104 scToBytes27(bbuf[:], b)
105 aBig := (&big.Int{}).SetBytes(abuf[:])
106 bBig := (&big.Int{}).SetBytes(bbuf[:])
107 prod := (&big.Int{}).Mul(aBig, bBig)
108 prod.Mod(prod, qBig)
109
110 var rbuf [27]byte
111 prodBytes := prod.Bytes()
112 copy(rbuf[27-int32(len(prodBytes)):], prodBytes)
113 scFromBytes27(r, rbuf[:])
114 }
115
116 func scFromBytes27(s *scalar, b []byte) {
117 if int32(len(b)) < 27 {
118 *s = scZero
119 return
120 }
121 s[3] = uint64(b[0])<<16 | uint64(b[1])<<8 | uint64(b[2])
122 s[2] = uint64(b[3])<<56 | uint64(b[4])<<48 | uint64(b[5])<<40 | uint64(b[6])<<32 |
123 uint64(b[7])<<24 | uint64(b[8])<<16 | uint64(b[9])<<8 | uint64(b[10])
124 s[1] = uint64(b[11])<<56 | uint64(b[12])<<48 | uint64(b[13])<<40 | uint64(b[14])<<32 |
125 uint64(b[15])<<24 | uint64(b[16])<<16 | uint64(b[17])<<8 | uint64(b[18])
126 s[0] = uint64(b[19])<<56 | uint64(b[20])<<48 | uint64(b[21])<<40 | uint64(b[22])<<32 |
127 uint64(b[23])<<24 | uint64(b[24])<<16 | uint64(b[25])<<8 | uint64(b[26])
128 scReduce(s)
129 }
130
131 func scToBytes27(b []byte, s *scalar) {
132 b[0] = byte(s[3] >> 16)
133 b[1] = byte(s[3] >> 8)
134 b[2] = byte(s[3])
135 b[3] = byte(s[2] >> 56)
136 b[4] = byte(s[2] >> 48)
137 b[5] = byte(s[2] >> 40)
138 b[6] = byte(s[2] >> 32)
139 b[7] = byte(s[2] >> 24)
140 b[8] = byte(s[2] >> 16)
141 b[9] = byte(s[2] >> 8)
142 b[10] = byte(s[2])
143 b[11] = byte(s[1] >> 56)
144 b[12] = byte(s[1] >> 48)
145 b[13] = byte(s[1] >> 40)
146 b[14] = byte(s[1] >> 32)
147 b[15] = byte(s[1] >> 24)
148 b[16] = byte(s[1] >> 16)
149 b[17] = byte(s[1] >> 8)
150 b[18] = byte(s[1])
151 b[19] = byte(s[0] >> 56)
152 b[20] = byte(s[0] >> 48)
153 b[21] = byte(s[0] >> 40)
154 b[22] = byte(s[0] >> 32)
155 b[23] = byte(s[0] >> 24)
156 b[24] = byte(s[0] >> 16)
157 b[25] = byte(s[0] >> 8)
158 b[26] = byte(s[0])
159 }
160
161 func scRandom(s *scalar) (err error) {
162 var buf [27]byte
163 for {
164 _, err = rand.Read(buf[:])
165 if err != nil {
166 return err
167 }
168 buf[0] &= 0x1F
169 scFromBytes27(s, buf[:])
170 if !scIsZero(s) {
171 return nil
172 }
173 }
174 }
175