PR c++/86342 - -Wdeprecated-copy and system headers.
[official-gcc.git] / libgo / go / crypto / rsa / rsa.go
blob0faca43e430766dac34d87a6c4b5e864866bb0f4
1 // 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.
5 // Package rsa implements RSA encryption as specified in PKCS#1.
6 //
7 // RSA is a single, fundamental operation that is used in this package to
8 // implement either public-key encryption or public-key signatures.
9 //
10 // The original specification for encryption and signatures with RSA is PKCS#1
11 // and the terms "RSA encryption" and "RSA signatures" by default refer to
12 // PKCS#1 version 1.5. However, that specification has flaws and new designs
13 // should use version two, usually called by just OAEP and PSS, where
14 // possible.
16 // Two sets of interfaces are included in this package. When a more abstract
17 // interface isn't necessary, there are functions for encrypting/decrypting
18 // with v1.5/OAEP and signing/verifying with v1.5/PSS. If one needs to abstract
19 // over the public-key primitive, the PrivateKey struct implements the
20 // Decrypter and Signer interfaces from the crypto package.
22 // The RSA operations in this package are not implemented using constant-time algorithms.
23 package rsa
25 import (
26 "crypto"
27 "crypto/rand"
28 "crypto/subtle"
29 "errors"
30 "hash"
31 "io"
32 "math"
33 "math/big"
36 var bigZero = big.NewInt(0)
37 var bigOne = big.NewInt(1)
39 // A PublicKey represents the public part of an RSA key.
40 type PublicKey struct {
41 N *big.Int // modulus
42 E int // public exponent
45 // OAEPOptions is an interface for passing options to OAEP decryption using the
46 // crypto.Decrypter interface.
47 type OAEPOptions struct {
48 // Hash is the hash function that will be used when generating the mask.
49 Hash crypto.Hash
50 // Label is an arbitrary byte string that must be equal to the value
51 // used when encrypting.
52 Label []byte
55 var (
56 errPublicModulus = errors.New("crypto/rsa: missing public modulus")
57 errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small")
58 errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large")
61 // checkPub sanity checks the public key before we use it.
62 // We require pub.E to fit into a 32-bit integer so that we
63 // do not have different behavior depending on whether
64 // int is 32 or 64 bits. See also
65 // http://www.imperialviolet.org/2012/03/16/rsae.html.
66 func checkPub(pub *PublicKey) error {
67 if pub.N == nil {
68 return errPublicModulus
70 if pub.E < 2 {
71 return errPublicExponentSmall
73 if pub.E > 1<<31-1 {
74 return errPublicExponentLarge
76 return nil
79 // A PrivateKey represents an RSA key
80 type PrivateKey struct {
81 PublicKey // public part.
82 D *big.Int // private exponent
83 Primes []*big.Int // prime factors of N, has >= 2 elements.
85 // Precomputed contains precomputed values that speed up private
86 // operations, if available.
87 Precomputed PrecomputedValues
90 // Public returns the public key corresponding to priv.
91 func (priv *PrivateKey) Public() crypto.PublicKey {
92 return &priv.PublicKey
95 // Sign signs digest with priv, reading randomness from rand. If opts is a
96 // *PSSOptions then the PSS algorithm will be used, otherwise PKCS#1 v1.5 will
97 // be used.
99 // This method implements crypto.Signer, which is an interface to support keys
100 // where the private part is kept in, for example, a hardware module. Common
101 // uses should use the Sign* functions in this package directly.
102 func (priv *PrivateKey) Sign(rand io.Reader, digest []byte, opts crypto.SignerOpts) ([]byte, error) {
103 if pssOpts, ok := opts.(*PSSOptions); ok {
104 return SignPSS(rand, priv, pssOpts.Hash, digest, pssOpts)
107 return SignPKCS1v15(rand, priv, opts.HashFunc(), digest)
110 // Decrypt decrypts ciphertext with priv. If opts is nil or of type
111 // *PKCS1v15DecryptOptions then PKCS#1 v1.5 decryption is performed. Otherwise
112 // opts must have type *OAEPOptions and OAEP decryption is done.
113 func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) {
114 if opts == nil {
115 return DecryptPKCS1v15(rand, priv, ciphertext)
118 switch opts := opts.(type) {
119 case *OAEPOptions:
120 return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label)
122 case *PKCS1v15DecryptOptions:
123 if l := opts.SessionKeyLen; l > 0 {
124 plaintext = make([]byte, l)
125 if _, err := io.ReadFull(rand, plaintext); err != nil {
126 return nil, err
128 if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil {
129 return nil, err
131 return plaintext, nil
132 } else {
133 return DecryptPKCS1v15(rand, priv, ciphertext)
136 default:
137 return nil, errors.New("crypto/rsa: invalid options for Decrypt")
141 type PrecomputedValues struct {
142 Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
143 Qinv *big.Int // Q^-1 mod P
145 // CRTValues is used for the 3rd and subsequent primes. Due to a
146 // historical accident, the CRT for the first two primes is handled
147 // differently in PKCS#1 and interoperability is sufficiently
148 // important that we mirror this.
149 CRTValues []CRTValue
152 // CRTValue contains the precomputed Chinese remainder theorem values.
153 type CRTValue struct {
154 Exp *big.Int // D mod (prime-1).
155 Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
156 R *big.Int // product of primes prior to this (inc p and q).
159 // Validate performs basic sanity checks on the key.
160 // It returns nil if the key is valid, or else an error describing a problem.
161 func (priv *PrivateKey) Validate() error {
162 if err := checkPub(&priv.PublicKey); err != nil {
163 return err
166 // Check that Πprimes == n.
167 modulus := new(big.Int).Set(bigOne)
168 for _, prime := range priv.Primes {
169 // Any primes ≤ 1 will cause divide-by-zero panics later.
170 if prime.Cmp(bigOne) <= 0 {
171 return errors.New("crypto/rsa: invalid prime value")
173 modulus.Mul(modulus, prime)
175 if modulus.Cmp(priv.N) != 0 {
176 return errors.New("crypto/rsa: invalid modulus")
179 // Check that de ≡ 1 mod p-1, for each prime.
180 // This implies that e is coprime to each p-1 as e has a multiplicative
181 // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) =
182 // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1
183 // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required.
184 congruence := new(big.Int)
185 de := new(big.Int).SetInt64(int64(priv.E))
186 de.Mul(de, priv.D)
187 for _, prime := range priv.Primes {
188 pminus1 := new(big.Int).Sub(prime, bigOne)
189 congruence.Mod(de, pminus1)
190 if congruence.Cmp(bigOne) != 0 {
191 return errors.New("crypto/rsa: invalid exponents")
194 return nil
197 // GenerateKey generates an RSA keypair of the given bit size using the
198 // random source random (for example, crypto/rand.Reader).
199 func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) {
200 return GenerateMultiPrimeKey(random, 2, bits)
203 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
204 // size and the given random source, as suggested in [1]. Although the public
205 // keys are compatible (actually, indistinguishable) from the 2-prime case,
206 // the private keys are not. Thus it may not be possible to export multi-prime
207 // private keys in certain formats or to subsequently import them into other
208 // code.
210 // Table 1 in [2] suggests maximum numbers of primes for a given size.
212 // [1] US patent 4405829 (1972, expired)
213 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
214 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) {
215 priv := new(PrivateKey)
216 priv.E = 65537
218 if nprimes < 2 {
219 return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2")
222 if bits < 64 {
223 primeLimit := float64(uint64(1) << uint(bits/nprimes))
224 // pi approximates the number of primes less than primeLimit
225 pi := primeLimit / (math.Log(primeLimit) - 1)
226 // Generated primes start with 11 (in binary) so we can only
227 // use a quarter of them.
228 pi /= 4
229 // Use a factor of two to ensure that key generation terminates
230 // in a reasonable amount of time.
231 pi /= 2
232 if pi <= float64(nprimes) {
233 return nil, errors.New("crypto/rsa: too few primes of given length to generate an RSA key")
237 primes := make([]*big.Int, nprimes)
239 NextSetOfPrimes:
240 for {
241 todo := bits
242 // crypto/rand should set the top two bits in each prime.
243 // Thus each prime has the form
244 // p_i = 2^bitlen(p_i) × 0.11... (in base 2).
245 // And the product is:
246 // P = 2^todo × α
247 // where α is the product of nprimes numbers of the form 0.11...
249 // If α < 1/2 (which can happen for nprimes > 2), we need to
250 // shift todo to compensate for lost bits: the mean value of 0.11...
251 // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2
252 // will give good results.
253 if nprimes >= 7 {
254 todo += (nprimes - 2) / 5
256 for i := 0; i < nprimes; i++ {
257 var err error
258 primes[i], err = rand.Prime(random, todo/(nprimes-i))
259 if err != nil {
260 return nil, err
262 todo -= primes[i].BitLen()
265 // Make sure that primes is pairwise unequal.
266 for i, prime := range primes {
267 for j := 0; j < i; j++ {
268 if prime.Cmp(primes[j]) == 0 {
269 continue NextSetOfPrimes
274 n := new(big.Int).Set(bigOne)
275 totient := new(big.Int).Set(bigOne)
276 pminus1 := new(big.Int)
277 for _, prime := range primes {
278 n.Mul(n, prime)
279 pminus1.Sub(prime, bigOne)
280 totient.Mul(totient, pminus1)
282 if n.BitLen() != bits {
283 // This should never happen for nprimes == 2 because
284 // crypto/rand should set the top two bits in each prime.
285 // For nprimes > 2 we hope it does not happen often.
286 continue NextSetOfPrimes
289 g := new(big.Int)
290 priv.D = new(big.Int)
291 e := big.NewInt(int64(priv.E))
292 g.GCD(priv.D, nil, e, totient)
294 if g.Cmp(bigOne) == 0 {
295 if priv.D.Sign() < 0 {
296 priv.D.Add(priv.D, totient)
298 priv.Primes = primes
299 priv.N = n
301 break
305 priv.Precompute()
306 return priv, nil
309 // incCounter increments a four byte, big-endian counter.
310 func incCounter(c *[4]byte) {
311 if c[3]++; c[3] != 0 {
312 return
314 if c[2]++; c[2] != 0 {
315 return
317 if c[1]++; c[1] != 0 {
318 return
320 c[0]++
323 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
324 // specified in PKCS#1 v2.1.
325 func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
326 var counter [4]byte
327 var digest []byte
329 done := 0
330 for done < len(out) {
331 hash.Write(seed)
332 hash.Write(counter[0:4])
333 digest = hash.Sum(digest[:0])
334 hash.Reset()
336 for i := 0; i < len(digest) && done < len(out); i++ {
337 out[done] ^= digest[i]
338 done++
340 incCounter(&counter)
344 // ErrMessageTooLong is returned when attempting to encrypt a message which is
345 // too large for the size of the public key.
346 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size")
348 func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
349 e := big.NewInt(int64(pub.E))
350 c.Exp(m, e, pub.N)
351 return c
354 // EncryptOAEP encrypts the given message with RSA-OAEP.
356 // OAEP is parameterised by a hash function that is used as a random oracle.
357 // Encryption and decryption of a given message must use the same hash function
358 // and sha256.New() is a reasonable choice.
360 // The random parameter is used as a source of entropy to ensure that
361 // encrypting the same message twice doesn't result in the same ciphertext.
363 // The label parameter may contain arbitrary data that will not be encrypted,
364 // but which gives important context to the message. For example, if a given
365 // public key is used to decrypt two types of messages then distinct label
366 // values could be used to ensure that a ciphertext for one purpose cannot be
367 // used for another by an attacker. If not required it can be empty.
369 // The message must be no longer than the length of the public modulus minus
370 // twice the hash length, minus a further 2.
371 func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) ([]byte, error) {
372 if err := checkPub(pub); err != nil {
373 return nil, err
375 hash.Reset()
376 k := (pub.N.BitLen() + 7) / 8
377 if len(msg) > k-2*hash.Size()-2 {
378 return nil, ErrMessageTooLong
381 hash.Write(label)
382 lHash := hash.Sum(nil)
383 hash.Reset()
385 em := make([]byte, k)
386 seed := em[1 : 1+hash.Size()]
387 db := em[1+hash.Size():]
389 copy(db[0:hash.Size()], lHash)
390 db[len(db)-len(msg)-1] = 1
391 copy(db[len(db)-len(msg):], msg)
393 _, err := io.ReadFull(random, seed)
394 if err != nil {
395 return nil, err
398 mgf1XOR(db, hash, seed)
399 mgf1XOR(seed, hash, db)
401 m := new(big.Int)
402 m.SetBytes(em)
403 c := encrypt(new(big.Int), pub, m)
404 out := c.Bytes()
406 if len(out) < k {
407 // If the output is too small, we need to left-pad with zeros.
408 t := make([]byte, k)
409 copy(t[k-len(out):], out)
410 out = t
413 return out, nil
416 // ErrDecryption represents a failure to decrypt a message.
417 // It is deliberately vague to avoid adaptive attacks.
418 var ErrDecryption = errors.New("crypto/rsa: decryption error")
420 // ErrVerification represents a failure to verify a signature.
421 // It is deliberately vague to avoid adaptive attacks.
422 var ErrVerification = errors.New("crypto/rsa: verification error")
424 // modInverse returns ia, the inverse of a in the multiplicative group of prime
425 // order n. It requires that a be a member of the group (i.e. less than n).
426 func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
427 g := new(big.Int)
428 x := new(big.Int)
429 g.GCD(x, nil, a, n)
430 if g.Cmp(bigOne) != 0 {
431 // In this case, a and n aren't coprime and we cannot calculate
432 // the inverse. This happens because the values of n are nearly
433 // prime (being the product of two primes) rather than truly
434 // prime.
435 return
438 if x.Cmp(bigOne) < 0 {
439 // 0 is not the multiplicative inverse of any element so, if x
440 // < 1, then x is negative.
441 x.Add(x, n)
444 return x, true
447 // Precompute performs some calculations that speed up private key operations
448 // in the future.
449 func (priv *PrivateKey) Precompute() {
450 if priv.Precomputed.Dp != nil {
451 return
454 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
455 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
457 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
458 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
460 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
462 r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
463 priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
464 for i := 2; i < len(priv.Primes); i++ {
465 prime := priv.Primes[i]
466 values := &priv.Precomputed.CRTValues[i-2]
468 values.Exp = new(big.Int).Sub(prime, bigOne)
469 values.Exp.Mod(priv.D, values.Exp)
471 values.R = new(big.Int).Set(r)
472 values.Coeff = new(big.Int).ModInverse(r, prime)
474 r.Mul(r, prime)
478 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
479 // random source is given, RSA blinding is used.
480 func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
481 // TODO(agl): can we get away with reusing blinds?
482 if c.Cmp(priv.N) > 0 {
483 err = ErrDecryption
484 return
486 if priv.N.Sign() == 0 {
487 return nil, ErrDecryption
490 var ir *big.Int
491 if random != nil {
492 // Blinding enabled. Blinding involves multiplying c by r^e.
493 // Then the decryption operation performs (m^e * r^e)^d mod n
494 // which equals mr mod n. The factor of r can then be removed
495 // by multiplying by the multiplicative inverse of r.
497 var r *big.Int
499 for {
500 r, err = rand.Int(random, priv.N)
501 if err != nil {
502 return
504 if r.Cmp(bigZero) == 0 {
505 r = bigOne
507 var ok bool
508 ir, ok = modInverse(r, priv.N)
509 if ok {
510 break
513 bigE := big.NewInt(int64(priv.E))
514 rpowe := new(big.Int).Exp(r, bigE, priv.N) // N != 0
515 cCopy := new(big.Int).Set(c)
516 cCopy.Mul(cCopy, rpowe)
517 cCopy.Mod(cCopy, priv.N)
518 c = cCopy
521 if priv.Precomputed.Dp == nil {
522 m = new(big.Int).Exp(c, priv.D, priv.N)
523 } else {
524 // We have the precalculated values needed for the CRT.
525 m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
526 m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
527 m.Sub(m, m2)
528 if m.Sign() < 0 {
529 m.Add(m, priv.Primes[0])
531 m.Mul(m, priv.Precomputed.Qinv)
532 m.Mod(m, priv.Primes[0])
533 m.Mul(m, priv.Primes[1])
534 m.Add(m, m2)
536 for i, values := range priv.Precomputed.CRTValues {
537 prime := priv.Primes[2+i]
538 m2.Exp(c, values.Exp, prime)
539 m2.Sub(m2, m)
540 m2.Mul(m2, values.Coeff)
541 m2.Mod(m2, prime)
542 if m2.Sign() < 0 {
543 m2.Add(m2, prime)
545 m2.Mul(m2, values.R)
546 m.Add(m, m2)
550 if ir != nil {
551 // Unblind.
552 m.Mul(m, ir)
553 m.Mod(m, priv.N)
556 return
559 func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) {
560 m, err = decrypt(random, priv, c)
561 if err != nil {
562 return nil, err
565 // In order to defend against errors in the CRT computation, m^e is
566 // calculated, which should match the original ciphertext.
567 check := encrypt(new(big.Int), &priv.PublicKey, m)
568 if c.Cmp(check) != 0 {
569 return nil, errors.New("rsa: internal error")
571 return m, nil
574 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
576 // OAEP is parameterised by a hash function that is used as a random oracle.
577 // Encryption and decryption of a given message must use the same hash function
578 // and sha256.New() is a reasonable choice.
580 // The random parameter, if not nil, is used to blind the private-key operation
581 // and avoid timing side-channel attacks. Blinding is purely internal to this
582 // function – the random data need not match that used when encrypting.
584 // The label parameter must match the value given when encrypting. See
585 // EncryptOAEP for details.
586 func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) ([]byte, error) {
587 if err := checkPub(&priv.PublicKey); err != nil {
588 return nil, err
590 k := (priv.N.BitLen() + 7) / 8
591 if len(ciphertext) > k ||
592 k < hash.Size()*2+2 {
593 return nil, ErrDecryption
596 c := new(big.Int).SetBytes(ciphertext)
598 m, err := decrypt(random, priv, c)
599 if err != nil {
600 return nil, err
603 hash.Write(label)
604 lHash := hash.Sum(nil)
605 hash.Reset()
607 // Converting the plaintext number to bytes will strip any
608 // leading zeros so we may have to left pad. We do this unconditionally
609 // to avoid leaking timing information. (Although we still probably
610 // leak the number of leading zeros. It's not clear that we can do
611 // anything about this.)
612 em := leftPad(m.Bytes(), k)
614 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
616 seed := em[1 : hash.Size()+1]
617 db := em[hash.Size()+1:]
619 mgf1XOR(seed, hash, db)
620 mgf1XOR(db, hash, seed)
622 lHash2 := db[0:hash.Size()]
624 // We have to validate the plaintext in constant time in order to avoid
625 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
626 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
627 // v2.0. In J. Kilian, editor, Advances in Cryptology.
628 lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
630 // The remainder of the plaintext must be zero or more 0x00, followed
631 // by 0x01, followed by the message.
632 // lookingForIndex: 1 iff we are still looking for the 0x01
633 // index: the offset of the first 0x01 byte
634 // invalid: 1 iff we saw a non-zero byte before the 0x01.
635 var lookingForIndex, index, invalid int
636 lookingForIndex = 1
637 rest := db[hash.Size():]
639 for i := 0; i < len(rest); i++ {
640 equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
641 equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
642 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
643 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
644 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
647 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
648 return nil, ErrDecryption
651 return rest[index+1:], nil
654 // leftPad returns a new slice of length size. The contents of input are right
655 // aligned in the new slice.
656 func leftPad(input []byte, size int) (out []byte) {
657 n := len(input)
658 if n > size {
659 n = size
661 out = make([]byte, size)
662 copy(out[len(out)-n:], input)
663 return