ntru.go raw
1 package gnarlring
2
3 import (
4 "crypto/rand"
5 "io"
6 "math"
7
8 "git.smesh.lol/gnarl-hamadryad/crypto"
9 )
10
11 type NTRUPublicKey struct {
12 H *Poly27
13 }
14
15 type NTRUPrivateKey struct {
16 BTop [2]*Poly27 // b_i_top for each of 2 basis vectors
17 BBot [2]*Poly27 // b_i_bot
18 Sigma float64
19 PK *NTRUPublicKey
20 }
21
22 type NTRUSignature struct {
23 Salt [16]byte
24 S2 *Poly27
25 }
26
27 func NTRUKeyGen() (*NTRUPublicKey, *NTRUPrivateKey) {
28 return NTRUKeyGenFrom(rand.Reader)
29 }
30
31 func NTRUKeyGenFrom(rng io.Reader) (*NTRUPublicKey, *NTRUPrivateKey) {
32 sigma := math.Sqrt(float64(N)) * 2.0
33 gs := NewGaussSamplerFrom(sigma, rng)
34
35 var f, g, h *Poly27
36 for {
37 f = gs.SamplePoly()
38 g = gs.SamplePoly()
39 if Inverse(f) != nil {
40 h = Mul(g, Inverse(f))
41 break
42 }
43 }
44
45 // Build NTRU lattice, LLL-reduce, use first 2 reduced columns as basis.
46 bTop0, bBot0, bTop1, bBot1 := ntruBasisFromLLL(h)
47
48 pk := &NTRUPublicKey{H: h}
49 sk := &NTRUPrivateKey{
50 BTop: [2]*Poly27{bTop0, bTop1},
51 BBot: [2]*Poly27{bBot0, bBot1},
52 Sigma: sigma,
53 PK: pk,
54 }
55 return pk, sk
56 }
57
58 func ntruBasisFromLLL(h *Poly27) (*Poly27, *Poly27, *Poly27, *Poly27) {
59 n := N
60 q := int64(Q)
61 d := 2 * n
62
63 hMat := buildIntMatrix(h, n)
64
65 // Build kernel lattice K = {(u,v) ∈ Z^{2n} : u + h*v ≡ 0 mod q}.
66 // Basis columns:
67 // col j (0 ≤ j < n): u = -H_mat[:,j], v = e_j
68 // col n+j (0 ≤ j < n): u = q*e_j, v = 0
69 B := make([][]int64, d)
70 for i := range B {
71 B[i] = make([]int64, d)
72 }
73
74 for j := 0; j < n; j++ {
75 // Top half: u = -H_mat[:,j]
76 for i := 0; i < n; i++ {
77 B[j][i] = -hMat[i][j]
78 }
79 // Bottom half: v = e_j
80 B[j][n+j] = 1
81 }
82
83 for j := 0; j < n; j++ {
84 // Top half: u = q*e_j
85 B[n+j][j] = q
86 // Bottom half: v = 0 (already zero)
87 }
88
89 lllReduce(B, 0.99)
90
91 bTop0 := NewPoly27()
92 bBot0 := NewPoly27()
93 bTop1 := NewPoly27()
94 bBot1 := NewPoly27()
95 for i := 0; i < n; i++ {
96 bTop0.Coeffs[i] = modInt64(B[0][i])
97 bBot0.Coeffs[i] = modInt64(B[0][n+i])
98 bTop1.Coeffs[i] = modInt64(B[1][i])
99 bBot1.Coeffs[i] = modInt64(B[1][n+i])
100 }
101
102 n0 := float64(NormSq(bTop0) + NormSq(bBot0))
103 n1 := float64(NormSq(bTop1) + NormSq(bBot1))
104 if n1 < n0 {
105 bTop0, bTop1 = bTop1, bTop0
106 bBot0, bBot1 = bBot1, bBot0
107 }
108
109 return bTop0, bBot0, bTop1, bBot1
110 }
111
112 func buildIntMatrix(a *Poly27, n int) [][]int64 {
113 M := make([][]int64, n)
114 for k := 0; k < n; k++ {
115 M[k] = make([]int64, n)
116 for j := 0; j <= k; j++ {
117 M[k][j] = int64(a.Coeffs[k-j])
118 }
119 for j := k + 1; j < n; j++ {
120 M[k][j] = -int64(a.Coeffs[k-j+n])
121 }
122 }
123 return M
124 }
125
126 func modInt64(x int64) uint16 {
127 for x < 0 {
128 x += int64(Q)
129 }
130 return uint16(uint64(x) % uint64(Q))
131 }
132
133 func ffSampling(bTop [2]*Poly27, bBot [2]*Poly27, target *Poly27, sigma float64, rng io.Reader) (*Poly27, *Poly27) {
134 tTop := NewPoly27()
135 tBot := target.Clone()
136
137 b1Top := bTop[0]
138 b1Bot := bBot[0]
139 b2Top := bTop[1]
140 b2Bot := bBot[1]
141
142 b1NormSq := float64(Dot(b1Top, b1Top) + Dot(b1Bot, b1Bot))
143 b1b2 := float64(Dot(b2Top, b1Top) + Dot(b2Bot, b1Bot))
144 mu := b1b2 / b1NormSq
145
146 b2StarTop := Sub(b2Top, scalarMul(b1Top, mu))
147 b2StarBot := Sub(b2Bot, scalarMul(b1Bot, mu))
148 b2StarNormSq := float64(Dot(b2StarTop, b2StarTop) + Dot(b2StarBot, b2StarBot))
149
150 if b1NormSq < 1 {
151 b1NormSq = 1
152 }
153 if b2StarNormSq < 1 {
154 b2StarNormSq = 1
155 }
156
157 tb2 := float64(Dot(tTop, b2Top) + Dot(tBot, b2Bot))
158 tb1 := float64(Dot(tTop, b1Top) + Dot(tBot, b1Bot))
159 c2 := (tb2 - mu*tb1) / b2StarNormSq
160 sigma2 := sigma / math.Sqrt(b2StarNormSq)
161 gs2 := NewGaussSamplerFrom(sigma2, rng)
162 z2 := gs2.SampleZ(c2)
163
164 for i := 0; i < N; i++ {
165 tTop.Coeffs[i] = subMod(tTop.Coeffs[i], mulModInt(b2Top.Coeffs[i], z2))
166 tBot.Coeffs[i] = subMod(tBot.Coeffs[i], mulModInt(b2Bot.Coeffs[i], z2))
167 }
168
169 tb1r := float64(Dot(tTop, b1Top) + Dot(tBot, b1Bot))
170 c1 := tb1r / b1NormSq
171 sigma1 := sigma / math.Sqrt(b1NormSq)
172 gs1 := NewGaussSamplerFrom(sigma1, rng)
173 z1 := gs1.SampleZ(c1)
174
175 for i := 0; i < N; i++ {
176 tTop.Coeffs[i] = subMod(tTop.Coeffs[i], mulModInt(b1Top.Coeffs[i], z1))
177 tBot.Coeffs[i] = subMod(tBot.Coeffs[i], mulModInt(b1Bot.Coeffs[i], z1))
178 }
179
180 return tTop, tBot
181 }
182
183 func scalarMul(a *Poly27, s float64) *Poly27 {
184 r := NewPoly27()
185 si := uint16(math.Round(math.Abs(s)))
186 if si == 0 {
187 return r
188 }
189 for i, v := range a.Coeffs {
190 m := crypto.Mod271(uint32(v) * uint32(si))
191 if s < 0 {
192 r.Coeffs[i] = subMod(0, m)
193 } else {
194 r.Coeffs[i] = m
195 }
196 }
197 return r
198 }
199
200 func mulModInt(a uint16, z int64) uint16 {
201 if z >= 0 {
202 return crypto.Mod271(uint32(z) * uint32(a))
203 }
204 neg := crypto.Mod271(uint32(-z) * uint32(a))
205 return subMod(0, neg)
206 }
207
208 // NTRUSignTarget signs a pre-hashed target polynomial directly.
209 func NTRUSignTarget(sk *NTRUPrivateKey, target *Poly27, rng io.Reader) *NTRUSignature {
210 if rng == nil {
211 rng = rand.Reader
212 }
213 var salt [16]byte
214 io.ReadFull(rng, salt[:])
215 _, s2 := ffSampling(sk.BTop, sk.BBot, target, sk.Sigma, rng)
216 return &NTRUSignature{Salt: salt, S2: s2}
217 }
218
219 // NTRUVerifyTarget verifies a signature against a pre-hashed target.
220 func NTRUVerifyTarget(pk *NTRUPublicKey, target *Poly27, sig *NTRUSignature) bool {
221 sigma := math.Sqrt(float64(N)) * 2.0
222 hs2 := Mul(pk.H, sig.S2)
223 s1 := Sub(target, hs2)
224 tail := 13
225 bound := uint16(sigma * (1.5 + float64(tail)))
226 return Norm(s1) <= bound && Norm(sig.S2) <= bound
227 }
228
229 func NTRUSign(sk *NTRUPrivateKey, message []byte) *NTRUSignature {
230 return NTRUSignFrom(sk, message, rand.Reader)
231 }
232
233 func NTRUSignFrom(sk *NTRUPrivateKey, message []byte, rng io.Reader) *NTRUSignature {
234 if rng == nil {
235 rng = rand.Reader
236 }
237 var salt [16]byte
238 io.ReadFull(rng, salt[:])
239 c := hashToTarget(salt[:], sk.PK.H, message)
240 return NTRUSignTarget(sk, c, rng)
241 }
242
243 func NTRUVerify(pk *NTRUPublicKey, message []byte, sig *NTRUSignature) bool {
244 c := hashToTarget(sig.Salt[:], pk.H, message)
245 return NTRUVerifyTarget(pk, c, sig)
246 }
247
248 func hashToTarget(salt []byte, h *Poly27, msg []byte) *Poly27 {
249 input := make([]byte, 0, len(salt)+PolyBytes+len(msg)+32)
250 input = append(input, []byte("gnarl-ntru-v1")...)
251 input = append(input, salt...)
252 input = append(input, h.MarshalBinary()...)
253 input = append(input, msg...)
254
255 var state uint64 = 14695981039346656037
256 c := NewPoly27()
257 for i := 0; i < N; i++ {
258 for _, b := range input {
259 state ^= uint64(b)
260 state *= 1099511628211
261 }
262 state ^= uint64(i)
263 state *= 1099511628211
264 c.Coeffs[i] = uint16(state % uint64(Q))
265 }
266 return c
267 }
268
269 func (pk *NTRUPublicKey) MarshalBinary() []byte {
270 return pk.H.MarshalBinary()
271 }
272
273 func UnmarshalNTRUPK(data []byte) (*NTRUPublicKey, error) {
274 h, err := UnmarshalBinary(data)
275 if err != nil {
276 return nil, err
277 }
278 return &NTRUPublicKey{H: h}, nil
279 }
280
281 func (sk *NTRUPrivateKey) MarshalBinary() []byte {
282 buf := make([]byte, 0, 4*PolyBytes)
283 buf = append(buf, sk.BTop[0].MarshalBinary()...)
284 buf = append(buf, sk.BBot[0].MarshalBinary()...)
285 buf = append(buf, sk.BTop[1].MarshalBinary()...)
286 buf = append(buf, sk.BBot[1].MarshalBinary()...)
287 return buf
288 }
289
290 func UnmarshalNTRUSK(data []byte, pk *NTRUPublicKey) (*NTRUPrivateKey, error) {
291 if len(data) < 4*PolyBytes {
292 return nil, errShortData
293 }
294 sigma := math.Sqrt(float64(N)) * 2.0
295 var err error
296 sk := &NTRUPrivateKey{Sigma: sigma, PK: pk}
297 sk.BTop[0], err = UnmarshalBinary(data[0*PolyBytes : 1*PolyBytes])
298 if err != nil {
299 return nil, err
300 }
301 sk.BBot[0], err = UnmarshalBinary(data[1*PolyBytes : 2*PolyBytes])
302 if err != nil {
303 return nil, err
304 }
305 sk.BTop[1], err = UnmarshalBinary(data[2*PolyBytes : 3*PolyBytes])
306 if err != nil {
307 return nil, err
308 }
309 sk.BBot[1], err = UnmarshalBinary(data[3*PolyBytes : 4*PolyBytes])
310 if err != nil {
311 return nil, err
312 }
313 return sk, nil
314 }
315
316 const sigBytes = 16 + 31
317
318 func (sig *NTRUSignature) MarshalBinary() []byte {
319 buf := make([]byte, 0, sigBytes)
320 buf = append(buf, sig.Salt[:]...)
321 buf = append(buf, Serialize(sig.S2, 9, true)...)
322 return buf
323 }
324
325 func UnmarshalNTRUSig(data []byte) (*NTRUSignature, error) {
326 if len(data) < sigBytes {
327 return nil, errShortData
328 }
329 sig := &NTRUSignature{}
330 copy(sig.Salt[:], data[0:16])
331 s2 := Deserialize(data[16:sigBytes], 9, true)
332 if s2 == nil {
333 return nil, errShortData
334 }
335 sig.S2 = s2
336 return sig, nil
337 }
338