1 |
747 |
jeremybenn |
// Copyright 2009 The Go Authors. All rights reserved.
|
2 |
|
|
// Use of this source code is governed by a BSD-style
|
3 |
|
|
// license that can be found in the LICENSE file.
|
4 |
|
|
|
5 |
|
|
// Package rsa implements RSA encryption as specified in PKCS#1.
|
6 |
|
|
package rsa
|
7 |
|
|
|
8 |
|
|
// TODO(agl): Add support for PSS padding.
|
9 |
|
|
|
10 |
|
|
import (
|
11 |
|
|
"crypto/rand"
|
12 |
|
|
"crypto/subtle"
|
13 |
|
|
"errors"
|
14 |
|
|
"hash"
|
15 |
|
|
"io"
|
16 |
|
|
"math/big"
|
17 |
|
|
)
|
18 |
|
|
|
19 |
|
|
var bigZero = big.NewInt(0)
|
20 |
|
|
var bigOne = big.NewInt(1)
|
21 |
|
|
|
22 |
|
|
// A PublicKey represents the public part of an RSA key.
|
23 |
|
|
type PublicKey struct {
|
24 |
|
|
N *big.Int // modulus
|
25 |
|
|
E int // public exponent
|
26 |
|
|
}
|
27 |
|
|
|
28 |
|
|
// A PrivateKey represents an RSA key
|
29 |
|
|
type PrivateKey struct {
|
30 |
|
|
PublicKey // public part.
|
31 |
|
|
D *big.Int // private exponent
|
32 |
|
|
Primes []*big.Int // prime factors of N, has >= 2 elements.
|
33 |
|
|
|
34 |
|
|
// Precomputed contains precomputed values that speed up private
|
35 |
|
|
// operations, if available.
|
36 |
|
|
Precomputed PrecomputedValues
|
37 |
|
|
}
|
38 |
|
|
|
39 |
|
|
type PrecomputedValues struct {
|
40 |
|
|
Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
|
41 |
|
|
Qinv *big.Int // Q^-1 mod Q
|
42 |
|
|
|
43 |
|
|
// CRTValues is used for the 3rd and subsequent primes. Due to a
|
44 |
|
|
// historical accident, the CRT for the first two primes is handled
|
45 |
|
|
// differently in PKCS#1 and interoperability is sufficiently
|
46 |
|
|
// important that we mirror this.
|
47 |
|
|
CRTValues []CRTValue
|
48 |
|
|
}
|
49 |
|
|
|
50 |
|
|
// CRTValue contains the precomputed chinese remainder theorem values.
|
51 |
|
|
type CRTValue struct {
|
52 |
|
|
Exp *big.Int // D mod (prime-1).
|
53 |
|
|
Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
|
54 |
|
|
R *big.Int // product of primes prior to this (inc p and q).
|
55 |
|
|
}
|
56 |
|
|
|
57 |
|
|
// Validate performs basic sanity checks on the key.
|
58 |
|
|
// It returns nil if the key is valid, or else an error describing a problem.
|
59 |
|
|
func (priv *PrivateKey) Validate() error {
|
60 |
|
|
// Check that the prime factors are actually prime. Note that this is
|
61 |
|
|
// just a sanity check. Since the random witnesses chosen by
|
62 |
|
|
// ProbablyPrime are deterministic, given the candidate number, it's
|
63 |
|
|
// easy for an attack to generate composites that pass this test.
|
64 |
|
|
for _, prime := range priv.Primes {
|
65 |
|
|
if !prime.ProbablyPrime(20) {
|
66 |
|
|
return errors.New("prime factor is composite")
|
67 |
|
|
}
|
68 |
|
|
}
|
69 |
|
|
|
70 |
|
|
// Check that Î primes == n.
|
71 |
|
|
modulus := new(big.Int).Set(bigOne)
|
72 |
|
|
for _, prime := range priv.Primes {
|
73 |
|
|
modulus.Mul(modulus, prime)
|
74 |
|
|
}
|
75 |
|
|
if modulus.Cmp(priv.N) != 0 {
|
76 |
|
|
return errors.New("invalid modulus")
|
77 |
|
|
}
|
78 |
|
|
// Check that e and totient(Î primes) are coprime.
|
79 |
|
|
totient := new(big.Int).Set(bigOne)
|
80 |
|
|
for _, prime := range priv.Primes {
|
81 |
|
|
pminus1 := new(big.Int).Sub(prime, bigOne)
|
82 |
|
|
totient.Mul(totient, pminus1)
|
83 |
|
|
}
|
84 |
|
|
e := big.NewInt(int64(priv.E))
|
85 |
|
|
gcd := new(big.Int)
|
86 |
|
|
x := new(big.Int)
|
87 |
|
|
y := new(big.Int)
|
88 |
|
|
gcd.GCD(x, y, totient, e)
|
89 |
|
|
if gcd.Cmp(bigOne) != 0 {
|
90 |
|
|
return errors.New("invalid public exponent E")
|
91 |
|
|
}
|
92 |
|
|
// Check that de ≡ 1 (mod totient(Πprimes))
|
93 |
|
|
de := new(big.Int).Mul(priv.D, e)
|
94 |
|
|
de.Mod(de, totient)
|
95 |
|
|
if de.Cmp(bigOne) != 0 {
|
96 |
|
|
return errors.New("invalid private exponent D")
|
97 |
|
|
}
|
98 |
|
|
return nil
|
99 |
|
|
}
|
100 |
|
|
|
101 |
|
|
// GenerateKey generates an RSA keypair of the given bit size.
|
102 |
|
|
func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err error) {
|
103 |
|
|
return GenerateMultiPrimeKey(random, 2, bits)
|
104 |
|
|
}
|
105 |
|
|
|
106 |
|
|
// GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
|
107 |
|
|
// size, as suggested in [1]. Although the public keys are compatible
|
108 |
|
|
// (actually, indistinguishable) from the 2-prime case, the private keys are
|
109 |
|
|
// not. Thus it may not be possible to export multi-prime private keys in
|
110 |
|
|
// certain formats or to subsequently import them into other code.
|
111 |
|
|
//
|
112 |
|
|
// Table 1 in [2] suggests maximum numbers of primes for a given size.
|
113 |
|
|
//
|
114 |
|
|
// [1] US patent 4405829 (1972, expired)
|
115 |
|
|
// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
|
116 |
|
|
func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err error) {
|
117 |
|
|
priv = new(PrivateKey)
|
118 |
|
|
priv.E = 65537
|
119 |
|
|
|
120 |
|
|
if nprimes < 2 {
|
121 |
|
|
return nil, errors.New("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
|
122 |
|
|
}
|
123 |
|
|
|
124 |
|
|
primes := make([]*big.Int, nprimes)
|
125 |
|
|
|
126 |
|
|
NextSetOfPrimes:
|
127 |
|
|
for {
|
128 |
|
|
todo := bits
|
129 |
|
|
for i := 0; i < nprimes; i++ {
|
130 |
|
|
primes[i], err = rand.Prime(random, todo/(nprimes-i))
|
131 |
|
|
if err != nil {
|
132 |
|
|
return nil, err
|
133 |
|
|
}
|
134 |
|
|
todo -= primes[i].BitLen()
|
135 |
|
|
}
|
136 |
|
|
|
137 |
|
|
// Make sure that primes is pairwise unequal.
|
138 |
|
|
for i, prime := range primes {
|
139 |
|
|
for j := 0; j < i; j++ {
|
140 |
|
|
if prime.Cmp(primes[j]) == 0 {
|
141 |
|
|
continue NextSetOfPrimes
|
142 |
|
|
}
|
143 |
|
|
}
|
144 |
|
|
}
|
145 |
|
|
|
146 |
|
|
n := new(big.Int).Set(bigOne)
|
147 |
|
|
totient := new(big.Int).Set(bigOne)
|
148 |
|
|
pminus1 := new(big.Int)
|
149 |
|
|
for _, prime := range primes {
|
150 |
|
|
n.Mul(n, prime)
|
151 |
|
|
pminus1.Sub(prime, bigOne)
|
152 |
|
|
totient.Mul(totient, pminus1)
|
153 |
|
|
}
|
154 |
|
|
|
155 |
|
|
g := new(big.Int)
|
156 |
|
|
priv.D = new(big.Int)
|
157 |
|
|
y := new(big.Int)
|
158 |
|
|
e := big.NewInt(int64(priv.E))
|
159 |
|
|
g.GCD(priv.D, y, e, totient)
|
160 |
|
|
|
161 |
|
|
if g.Cmp(bigOne) == 0 {
|
162 |
|
|
priv.D.Add(priv.D, totient)
|
163 |
|
|
priv.Primes = primes
|
164 |
|
|
priv.N = n
|
165 |
|
|
|
166 |
|
|
break
|
167 |
|
|
}
|
168 |
|
|
}
|
169 |
|
|
|
170 |
|
|
priv.Precompute()
|
171 |
|
|
return
|
172 |
|
|
}
|
173 |
|
|
|
174 |
|
|
// incCounter increments a four byte, big-endian counter.
|
175 |
|
|
func incCounter(c *[4]byte) {
|
176 |
|
|
if c[3]++; c[3] != 0 {
|
177 |
|
|
return
|
178 |
|
|
}
|
179 |
|
|
if c[2]++; c[2] != 0 {
|
180 |
|
|
return
|
181 |
|
|
}
|
182 |
|
|
if c[1]++; c[1] != 0 {
|
183 |
|
|
return
|
184 |
|
|
}
|
185 |
|
|
c[0]++
|
186 |
|
|
}
|
187 |
|
|
|
188 |
|
|
// mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
|
189 |
|
|
// specified in PKCS#1 v2.1.
|
190 |
|
|
func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
|
191 |
|
|
var counter [4]byte
|
192 |
|
|
var digest []byte
|
193 |
|
|
|
194 |
|
|
done := 0
|
195 |
|
|
for done < len(out) {
|
196 |
|
|
hash.Write(seed)
|
197 |
|
|
hash.Write(counter[0:4])
|
198 |
|
|
digest = hash.Sum(digest[:0])
|
199 |
|
|
hash.Reset()
|
200 |
|
|
|
201 |
|
|
for i := 0; i < len(digest) && done < len(out); i++ {
|
202 |
|
|
out[done] ^= digest[i]
|
203 |
|
|
done++
|
204 |
|
|
}
|
205 |
|
|
incCounter(&counter)
|
206 |
|
|
}
|
207 |
|
|
}
|
208 |
|
|
|
209 |
|
|
// MessageTooLongError is returned when attempting to encrypt a message which
|
210 |
|
|
// is too large for the size of the public key.
|
211 |
|
|
type MessageTooLongError struct{}
|
212 |
|
|
|
213 |
|
|
func (MessageTooLongError) Error() string {
|
214 |
|
|
return "message too long for RSA public key size"
|
215 |
|
|
}
|
216 |
|
|
|
217 |
|
|
func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
|
218 |
|
|
e := big.NewInt(int64(pub.E))
|
219 |
|
|
c.Exp(m, e, pub.N)
|
220 |
|
|
return c
|
221 |
|
|
}
|
222 |
|
|
|
223 |
|
|
// EncryptOAEP encrypts the given message with RSA-OAEP.
|
224 |
|
|
// The message must be no longer than the length of the public modulus less
|
225 |
|
|
// twice the hash length plus 2.
|
226 |
|
|
func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err error) {
|
227 |
|
|
hash.Reset()
|
228 |
|
|
k := (pub.N.BitLen() + 7) / 8
|
229 |
|
|
if len(msg) > k-2*hash.Size()-2 {
|
230 |
|
|
err = MessageTooLongError{}
|
231 |
|
|
return
|
232 |
|
|
}
|
233 |
|
|
|
234 |
|
|
hash.Write(label)
|
235 |
|
|
lHash := hash.Sum(nil)
|
236 |
|
|
hash.Reset()
|
237 |
|
|
|
238 |
|
|
em := make([]byte, k)
|
239 |
|
|
seed := em[1 : 1+hash.Size()]
|
240 |
|
|
db := em[1+hash.Size():]
|
241 |
|
|
|
242 |
|
|
copy(db[0:hash.Size()], lHash)
|
243 |
|
|
db[len(db)-len(msg)-1] = 1
|
244 |
|
|
copy(db[len(db)-len(msg):], msg)
|
245 |
|
|
|
246 |
|
|
_, err = io.ReadFull(random, seed)
|
247 |
|
|
if err != nil {
|
248 |
|
|
return
|
249 |
|
|
}
|
250 |
|
|
|
251 |
|
|
mgf1XOR(db, hash, seed)
|
252 |
|
|
mgf1XOR(seed, hash, db)
|
253 |
|
|
|
254 |
|
|
m := new(big.Int)
|
255 |
|
|
m.SetBytes(em)
|
256 |
|
|
c := encrypt(new(big.Int), pub, m)
|
257 |
|
|
out = c.Bytes()
|
258 |
|
|
|
259 |
|
|
if len(out) < k {
|
260 |
|
|
// If the output is too small, we need to left-pad with zeros.
|
261 |
|
|
t := make([]byte, k)
|
262 |
|
|
copy(t[k-len(out):], out)
|
263 |
|
|
out = t
|
264 |
|
|
}
|
265 |
|
|
|
266 |
|
|
return
|
267 |
|
|
}
|
268 |
|
|
|
269 |
|
|
// A DecryptionError represents a failure to decrypt a message.
|
270 |
|
|
// It is deliberately vague to avoid adaptive attacks.
|
271 |
|
|
type DecryptionError struct{}
|
272 |
|
|
|
273 |
|
|
func (DecryptionError) Error() string { return "RSA decryption error" }
|
274 |
|
|
|
275 |
|
|
// A VerificationError represents a failure to verify a signature.
|
276 |
|
|
// It is deliberately vague to avoid adaptive attacks.
|
277 |
|
|
type VerificationError struct{}
|
278 |
|
|
|
279 |
|
|
func (VerificationError) Error() string { return "RSA verification error" }
|
280 |
|
|
|
281 |
|
|
// modInverse returns ia, the inverse of a in the multiplicative group of prime
|
282 |
|
|
// order n. It requires that a be a member of the group (i.e. less than n).
|
283 |
|
|
func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
|
284 |
|
|
g := new(big.Int)
|
285 |
|
|
x := new(big.Int)
|
286 |
|
|
y := new(big.Int)
|
287 |
|
|
g.GCD(x, y, a, n)
|
288 |
|
|
if g.Cmp(bigOne) != 0 {
|
289 |
|
|
// In this case, a and n aren't coprime and we cannot calculate
|
290 |
|
|
// the inverse. This happens because the values of n are nearly
|
291 |
|
|
// prime (being the product of two primes) rather than truly
|
292 |
|
|
// prime.
|
293 |
|
|
return
|
294 |
|
|
}
|
295 |
|
|
|
296 |
|
|
if x.Cmp(bigOne) < 0 {
|
297 |
|
|
// 0 is not the multiplicative inverse of any element so, if x
|
298 |
|
|
// < 1, then x is negative.
|
299 |
|
|
x.Add(x, n)
|
300 |
|
|
}
|
301 |
|
|
|
302 |
|
|
return x, true
|
303 |
|
|
}
|
304 |
|
|
|
305 |
|
|
// Precompute performs some calculations that speed up private key operations
|
306 |
|
|
// in the future.
|
307 |
|
|
func (priv *PrivateKey) Precompute() {
|
308 |
|
|
if priv.Precomputed.Dp != nil {
|
309 |
|
|
return
|
310 |
|
|
}
|
311 |
|
|
|
312 |
|
|
priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
|
313 |
|
|
priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
|
314 |
|
|
|
315 |
|
|
priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
|
316 |
|
|
priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
|
317 |
|
|
|
318 |
|
|
priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
|
319 |
|
|
|
320 |
|
|
r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
|
321 |
|
|
priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
|
322 |
|
|
for i := 2; i < len(priv.Primes); i++ {
|
323 |
|
|
prime := priv.Primes[i]
|
324 |
|
|
values := &priv.Precomputed.CRTValues[i-2]
|
325 |
|
|
|
326 |
|
|
values.Exp = new(big.Int).Sub(prime, bigOne)
|
327 |
|
|
values.Exp.Mod(priv.D, values.Exp)
|
328 |
|
|
|
329 |
|
|
values.R = new(big.Int).Set(r)
|
330 |
|
|
values.Coeff = new(big.Int).ModInverse(r, prime)
|
331 |
|
|
|
332 |
|
|
r.Mul(r, prime)
|
333 |
|
|
}
|
334 |
|
|
}
|
335 |
|
|
|
336 |
|
|
// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
|
337 |
|
|
// random source is given, RSA blinding is used.
|
338 |
|
|
func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
|
339 |
|
|
// TODO(agl): can we get away with reusing blinds?
|
340 |
|
|
if c.Cmp(priv.N) > 0 {
|
341 |
|
|
err = DecryptionError{}
|
342 |
|
|
return
|
343 |
|
|
}
|
344 |
|
|
|
345 |
|
|
var ir *big.Int
|
346 |
|
|
if random != nil {
|
347 |
|
|
// Blinding enabled. Blinding involves multiplying c by r^e.
|
348 |
|
|
// Then the decryption operation performs (m^e * r^e)^d mod n
|
349 |
|
|
// which equals mr mod n. The factor of r can then be removed
|
350 |
|
|
// by multiplying by the multiplicative inverse of r.
|
351 |
|
|
|
352 |
|
|
var r *big.Int
|
353 |
|
|
|
354 |
|
|
for {
|
355 |
|
|
r, err = rand.Int(random, priv.N)
|
356 |
|
|
if err != nil {
|
357 |
|
|
return
|
358 |
|
|
}
|
359 |
|
|
if r.Cmp(bigZero) == 0 {
|
360 |
|
|
r = bigOne
|
361 |
|
|
}
|
362 |
|
|
var ok bool
|
363 |
|
|
ir, ok = modInverse(r, priv.N)
|
364 |
|
|
if ok {
|
365 |
|
|
break
|
366 |
|
|
}
|
367 |
|
|
}
|
368 |
|
|
bigE := big.NewInt(int64(priv.E))
|
369 |
|
|
rpowe := new(big.Int).Exp(r, bigE, priv.N)
|
370 |
|
|
cCopy := new(big.Int).Set(c)
|
371 |
|
|
cCopy.Mul(cCopy, rpowe)
|
372 |
|
|
cCopy.Mod(cCopy, priv.N)
|
373 |
|
|
c = cCopy
|
374 |
|
|
}
|
375 |
|
|
|
376 |
|
|
if priv.Precomputed.Dp == nil {
|
377 |
|
|
m = new(big.Int).Exp(c, priv.D, priv.N)
|
378 |
|
|
} else {
|
379 |
|
|
// We have the precalculated values needed for the CRT.
|
380 |
|
|
m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
|
381 |
|
|
m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
|
382 |
|
|
m.Sub(m, m2)
|
383 |
|
|
if m.Sign() < 0 {
|
384 |
|
|
m.Add(m, priv.Primes[0])
|
385 |
|
|
}
|
386 |
|
|
m.Mul(m, priv.Precomputed.Qinv)
|
387 |
|
|
m.Mod(m, priv.Primes[0])
|
388 |
|
|
m.Mul(m, priv.Primes[1])
|
389 |
|
|
m.Add(m, m2)
|
390 |
|
|
|
391 |
|
|
for i, values := range priv.Precomputed.CRTValues {
|
392 |
|
|
prime := priv.Primes[2+i]
|
393 |
|
|
m2.Exp(c, values.Exp, prime)
|
394 |
|
|
m2.Sub(m2, m)
|
395 |
|
|
m2.Mul(m2, values.Coeff)
|
396 |
|
|
m2.Mod(m2, prime)
|
397 |
|
|
if m2.Sign() < 0 {
|
398 |
|
|
m2.Add(m2, prime)
|
399 |
|
|
}
|
400 |
|
|
m2.Mul(m2, values.R)
|
401 |
|
|
m.Add(m, m2)
|
402 |
|
|
}
|
403 |
|
|
}
|
404 |
|
|
|
405 |
|
|
if ir != nil {
|
406 |
|
|
// Unblind.
|
407 |
|
|
m.Mul(m, ir)
|
408 |
|
|
m.Mod(m, priv.N)
|
409 |
|
|
}
|
410 |
|
|
|
411 |
|
|
return
|
412 |
|
|
}
|
413 |
|
|
|
414 |
|
|
// DecryptOAEP decrypts ciphertext using RSA-OAEP.
|
415 |
|
|
// If random != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks.
|
416 |
|
|
func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) {
|
417 |
|
|
k := (priv.N.BitLen() + 7) / 8
|
418 |
|
|
if len(ciphertext) > k ||
|
419 |
|
|
k < hash.Size()*2+2 {
|
420 |
|
|
err = DecryptionError{}
|
421 |
|
|
return
|
422 |
|
|
}
|
423 |
|
|
|
424 |
|
|
c := new(big.Int).SetBytes(ciphertext)
|
425 |
|
|
|
426 |
|
|
m, err := decrypt(random, priv, c)
|
427 |
|
|
if err != nil {
|
428 |
|
|
return
|
429 |
|
|
}
|
430 |
|
|
|
431 |
|
|
hash.Write(label)
|
432 |
|
|
lHash := hash.Sum(nil)
|
433 |
|
|
hash.Reset()
|
434 |
|
|
|
435 |
|
|
// Converting the plaintext number to bytes will strip any
|
436 |
|
|
// leading zeros so we may have to left pad. We do this unconditionally
|
437 |
|
|
// to avoid leaking timing information. (Although we still probably
|
438 |
|
|
// leak the number of leading zeros. It's not clear that we can do
|
439 |
|
|
// anything about this.)
|
440 |
|
|
em := leftPad(m.Bytes(), k)
|
441 |
|
|
|
442 |
|
|
firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
|
443 |
|
|
|
444 |
|
|
seed := em[1 : hash.Size()+1]
|
445 |
|
|
db := em[hash.Size()+1:]
|
446 |
|
|
|
447 |
|
|
mgf1XOR(seed, hash, db)
|
448 |
|
|
mgf1XOR(db, hash, seed)
|
449 |
|
|
|
450 |
|
|
lHash2 := db[0:hash.Size()]
|
451 |
|
|
|
452 |
|
|
// We have to validate the plaintext in constant time in order to avoid
|
453 |
|
|
// attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
|
454 |
|
|
// Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
|
455 |
|
|
// v2.0. In J. Kilian, editor, Advances in Cryptology.
|
456 |
|
|
lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
|
457 |
|
|
|
458 |
|
|
// The remainder of the plaintext must be zero or more 0x00, followed
|
459 |
|
|
// by 0x01, followed by the message.
|
460 |
|
|
// lookingForIndex: 1 iff we are still looking for the 0x01
|
461 |
|
|
// index: the offset of the first 0x01 byte
|
462 |
|
|
// invalid: 1 iff we saw a non-zero byte before the 0x01.
|
463 |
|
|
var lookingForIndex, index, invalid int
|
464 |
|
|
lookingForIndex = 1
|
465 |
|
|
rest := db[hash.Size():]
|
466 |
|
|
|
467 |
|
|
for i := 0; i < len(rest); i++ {
|
468 |
|
|
equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
|
469 |
|
|
equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
|
470 |
|
|
index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
|
471 |
|
|
lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
|
472 |
|
|
invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
|
473 |
|
|
}
|
474 |
|
|
|
475 |
|
|
if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
|
476 |
|
|
err = DecryptionError{}
|
477 |
|
|
return
|
478 |
|
|
}
|
479 |
|
|
|
480 |
|
|
msg = rest[index+1:]
|
481 |
|
|
return
|
482 |
|
|
}
|
483 |
|
|
|
484 |
|
|
// leftPad returns a new slice of length size. The contents of input are right
|
485 |
|
|
// aligned in the new slice.
|
486 |
|
|
func leftPad(input []byte, size int) (out []byte) {
|
487 |
|
|
n := len(input)
|
488 |
|
|
if n > size {
|
489 |
|
|
n = size
|
490 |
|
|
}
|
491 |
|
|
out = make([]byte, size)
|
492 |
|
|
copy(out[len(out)-n:], input)
|
493 |
|
|
return
|
494 |
|
|
}
|