kem.mx raw
1 // Ring-LWE Key Encapsulation Mechanism (IND-CCA2 via Fujisaki-Okamoto).
2 package ring
3
4 import (
5 "crypto/rand"
6 "crypto/subtle"
7 "errors"
8 "io"
9
10 "crypto/sha3"
11 )
12
13 type KEMParams struct {
14 Ring Params
15 Eta1 int32
16 Eta2 int32
17 SharedKeyLen int32
18 }
19
20 func DefaultKEMParams() (kp KEMParams) {
21 return KEMParams{
22 Ring: Falcon512(),
23 Eta1: 3,
24 Eta2: 3,
25 SharedKeyLen: 32,
26 }
27 }
28
29 type KEMPublicKey struct {
30 A *Poly
31 B *Poly
32 P KEMParams
33 }
34
35 type KEMSecretKey struct {
36 S *Poly
37 PK *KEMPublicKey
38 Z []byte
39 }
40
41 type KEMCiphertext struct {
42 U *Poly
43 V *Poly
44 }
45
46 func KEMKeyGen(kp KEMParams) (pk *KEMPublicKey, sk *KEMSecretKey) {
47 return KEMKeyGenFrom(kp, rand.Reader)
48 }
49
50 func KEMKeyGenFrom(kp KEMParams, rng io.Reader) (pk *KEMPublicKey, sk *KEMSecretKey) {
51 p := kp.Ring
52
53 a := UniformPolyFrom(p, rng)
54 NTT(a)
55
56 s := CBDPolyFrom(p, kp.Eta1, rng)
57 NTT(s)
58
59 e := CBDPolyFrom(p, kp.Eta1, rng)
60 NTT(e)
61
62 b := MulPointwise(a, s)
63 b = Add(b, e)
64
65 z := []byte{:kp.SharedKeyLen}
66 _, err := io.ReadFull(rng, z)
67 if err != nil {
68 panic("ring/kem: randomness source failed: " | err.Error())
69 }
70
71 pk = &KEMPublicKey{A: a, B: b, P: kp}
72 sk = &KEMSecretKey{S: s, PK: pk, Z: z}
73 return pk, sk
74 }
75
76 func cpaPKEEncrypt(pk *KEMPublicKey, m []byte, coins []byte) (ct *KEMCiphertext) {
77 p := pk.P.Ring
78
79 rng := sha3.NewSHAKE256()
80 rng.Write(coins)
81
82 r := CBDPolyFrom(p, pk.P.Eta1, rng)
83 NTT(r)
84
85 e1 := CBDPolyFrom(p, pk.P.Eta2, rng)
86 e2 := CBDPolyFrom(p, pk.P.Eta2, rng)
87
88 u := MulPointwise(pk.A, r)
89 INTT(u)
90 u = Add(u, e1)
91
92 v := MulPointwise(pk.B, r)
93 INTT(v)
94 v = Add(v, e2)
95
96 encoded := encodeMessage(p, m)
97 v = Add(v, encoded)
98
99 return &KEMCiphertext{U: u, V: v}
100 }
101
102 func cpaPKEDecrypt(sk *KEMSecretKey, ct *KEMCiphertext) (m []byte) {
103 uNTT := ct.U.Clone()
104 NTT(uNTT)
105
106 su := MulPointwise(sk.S, uNTT)
107 INTT(su)
108
109 noisy := Sub(ct.V, su)
110 return decodeMessage(noisy)
111 }
112
113 const kemMessageBytes = 32
114
115 func encodeMessage(p Params, m []byte) (poly *Poly) {
116 poly = New(p)
117 half := p.Q / 2
118 bits := int32(kemMessageBytes * 8)
119 if bits > p.N {
120 bits = p.N
121 }
122 for i := int32(0); i < bits; i++ {
123 byteIdx := i / 8
124 bitIdx := uint32(i % 8)
125 if byteIdx < int32(len(m)) && m[byteIdx]&(1<<bitIdx) != 0 {
126 poly.Coeffs[i] = half
127 }
128 }
129 return poly
130 }
131
132 func decodeMessage(a *Poly) (m []byte) {
133 q := a.params.Q
134 half := q / 2
135 quarter := q / 4
136 m = []byte{:kemMessageBytes}
137
138 bits := int32(kemMessageBytes * 8)
139 if bits > a.params.N {
140 bits = a.params.N
141 }
142 for i := int32(0); i < bits; i++ {
143 c := a.Coeffs[i]
144 var distHalf uint32
145 if c > half {
146 distHalf = c - half
147 } else {
148 distHalf = half - c
149 }
150 if distHalf < quarter {
151 m[i/8] |= 1 << uint32(i%8)
152 }
153 }
154 return m
155 }
156
157 func Encapsulate(pk *KEMPublicKey) (sharedKey []byte, ct *KEMCiphertext, err error) {
158 return EncapsulateFrom(pk, rand.Reader)
159 }
160
161 func EncapsulateFrom(pk *KEMPublicKey, rng io.Reader) (sharedKey []byte, ct *KEMCiphertext, err error) {
162 m := []byte{:32}
163 _, err = io.ReadFull(rng, m)
164 if err != nil {
165 return nil, nil, errors.New("ring/kem: randomness failed")
166 }
167
168 pkHash := hashPublicKey(pk)
169 K, coins := deriveKCoins(m, pkHash)
170
171 ct = cpaPKEEncrypt(pk, m, coins)
172
173 ctHash := hashCiphertext(ct)
174 sharedKey = kemKDF(K, ctHash, pk.P.SharedKeyLen)
175 return sharedKey, ct, nil
176 }
177
178 func Decapsulate(sk *KEMSecretKey, ct *KEMCiphertext) (sharedKey []byte, err error) {
179 if ct == nil || ct.U == nil || ct.V == nil {
180 return nil, errors.New("ring/kem: nil ciphertext")
181 }
182
183 mPrime := cpaPKEDecrypt(sk, ct)
184
185 pkHash := hashPublicKey(sk.PK)
186 KPrime, coinsPrime := deriveKCoins(mPrime, pkHash)
187
188 ctPrime := cpaPKEEncrypt(sk.PK, mPrime, coinsPrime)
189
190 match := ciphertextEqual(ct, ctPrime)
191
192 ctHash := hashCiphertext(ct)
193 realKey := kemKDF(KPrime, ctHash, sk.PK.P.SharedKeyLen)
194 rejectKey := kemKDF(sk.Z, ctHash, sk.PK.P.SharedKeyLen)
195
196 sharedKey = []byte{:sk.PK.P.SharedKeyLen}
197 subtle.ConstantTimeCopy(match, sharedKey, realKey)
198 subtle.ConstantTimeCopy(1-match, sharedKey, rejectKey)
199
200 return sharedKey, nil
201 }
202
203 func hashPublicKey(pk *KEMPublicKey) (out []byte) {
204 h := sha3.NewSHAKE256()
205 h.Write([]byte("hamadryad-kem-pk"))
206 h.Write(Serialize(pk.A))
207 h.Write(Serialize(pk.B))
208 out = []byte{:32}
209 h.Read(out)
210 return out
211 }
212
213 func hashCiphertext(ct *KEMCiphertext) (out []byte) {
214 h := sha3.NewSHAKE256()
215 h.Write([]byte("hamadryad-kem-ct"))
216 h.Write(Serialize(ct.U))
217 h.Write(Serialize(ct.V))
218 out = []byte{:32}
219 h.Read(out)
220 return out
221 }
222
223 func deriveKCoins(m, pkHash []byte) (K, coins []byte) {
224 h := sha3.NewSHAKE256()
225 h.Write([]byte("hamadryad-kem-g"))
226 h.Write(m)
227 h.Write(pkHash)
228 out := []byte{:64}
229 h.Read(out)
230 return out[:32], out[32:]
231 }
232
233 func kemKDF(key, label []byte, outLen int32) (out []byte) {
234 h := sha3.NewSHAKE256()
235 h.Write([]byte("hamadryad-kem-kdf"))
236 h.Write(key)
237 h.Write(label)
238 out = []byte{:outLen}
239 h.Read(out)
240 return out
241 }
242
243 func ciphertextEqual(a, b *KEMCiphertext) (result int32) {
244 aU := Serialize(a.U)
245 bU := Serialize(b.U)
246 aV := Serialize(a.V)
247 bV := Serialize(b.V)
248
249 if int32(len(aU)) != int32(len(bU)) || int32(len(aV)) != int32(len(bV)) {
250 return 0
251 }
252
253 return subtle.ConstantTimeCompare(aU, bU) & subtle.ConstantTimeCompare(aV, bV)
254 }
255