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. 4 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. 15// 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. 21// 22// The RSA operations in this package are not implemented using constant-time algorithms. 23package rsa 24 25import ( 26 "crypto" 27 "crypto/rand" 28 "crypto/subtle" 29 "errors" 30 "hash" 31 "io" 32 "math" 33 "math/big" 34) 35 36var bigZero = big.NewInt(0) 37var bigOne = big.NewInt(1) 38 39// A PublicKey represents the public part of an RSA key. 40type PublicKey struct { 41 N *big.Int // modulus 42 E int // public exponent 43} 44 45// OAEPOptions is an interface for passing options to OAEP decryption using the 46// crypto.Decrypter interface. 47type 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 53} 54 55var ( 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") 59) 60 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. 66func checkPub(pub *PublicKey) error { 67 if pub.N == nil { 68 return errPublicModulus 69 } 70 if pub.E < 2 { 71 return errPublicExponentSmall 72 } 73 if pub.E > 1<<31-1 { 74 return errPublicExponentLarge 75 } 76 return nil 77} 78 79// A PrivateKey represents an RSA key 80type PrivateKey struct { 81 PublicKey // public part. 82 D *big.Int // private exponent 83 Primes []*big.Int // prime factors of N, has >= 2 elements. 84 85 // Precomputed contains precomputed values that speed up private 86 // operations, if available. 87 Precomputed PrecomputedValues 88} 89 90// Public returns the public key corresponding to priv. 91func (priv *PrivateKey) Public() crypto.PublicKey { 92 return &priv.PublicKey 93} 94 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. 98// 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. 102func (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) 105 } 106 107 return SignPKCS1v15(rand, priv, opts.HashFunc(), digest) 108} 109 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. 113func (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) 116 } 117 118 switch opts := opts.(type) { 119 case *OAEPOptions: 120 return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label) 121 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 127 } 128 if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil { 129 return nil, err 130 } 131 return plaintext, nil 132 } else { 133 return DecryptPKCS1v15(rand, priv, ciphertext) 134 } 135 136 default: 137 return nil, errors.New("crypto/rsa: invalid options for Decrypt") 138 } 139} 140 141type PrecomputedValues struct { 142 Dp, Dq *big.Int // D mod (P-1) (or mod Q-1) 143 Qinv *big.Int // Q^-1 mod P 144 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 150} 151 152// CRTValue contains the precomputed Chinese remainder theorem values. 153type 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). 157} 158 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. 161func (priv *PrivateKey) Validate() error { 162 if err := checkPub(&priv.PublicKey); err != nil { 163 return err 164 } 165 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") 172 } 173 modulus.Mul(modulus, prime) 174 } 175 if modulus.Cmp(priv.N) != 0 { 176 return errors.New("crypto/rsa: invalid modulus") 177 } 178 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") 192 } 193 } 194 return nil 195} 196 197// GenerateKey generates an RSA keypair of the given bit size using the 198// random source random (for example, crypto/rand.Reader). 199func GenerateKey(random io.Reader, bits int) (*PrivateKey, error) { 200 return GenerateMultiPrimeKey(random, 2, bits) 201} 202 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. 209// 210// Table 1 in [2] suggests maximum numbers of primes for a given size. 211// 212// [1] US patent 4405829 (1972, expired) 213// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf 214func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (*PrivateKey, error) { 215 priv := new(PrivateKey) 216 priv.E = 65537 217 218 if nprimes < 2 { 219 return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2") 220 } 221 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") 234 } 235 } 236 237 primes := make([]*big.Int, nprimes) 238 239NextSetOfPrimes: 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... 248 // 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 255 } 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 261 } 262 todo -= primes[i].BitLen() 263 } 264 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 270 } 271 } 272 } 273 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) 281 } 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 287 } 288 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) 293 294 if g.Cmp(bigOne) == 0 { 295 if priv.D.Sign() < 0 { 296 priv.D.Add(priv.D, totient) 297 } 298 priv.Primes = primes 299 priv.N = n 300 301 break 302 } 303 } 304 305 priv.Precompute() 306 return priv, nil 307} 308 309// incCounter increments a four byte, big-endian counter. 310func incCounter(c *[4]byte) { 311 if c[3]++; c[3] != 0 { 312 return 313 } 314 if c[2]++; c[2] != 0 { 315 return 316 } 317 if c[1]++; c[1] != 0 { 318 return 319 } 320 c[0]++ 321} 322 323// mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function 324// specified in PKCS#1 v2.1. 325func mgf1XOR(out []byte, hash hash.Hash, seed []byte) { 326 var counter [4]byte 327 var digest []byte 328 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() 335 336 for i := 0; i < len(digest) && done < len(out); i++ { 337 out[done] ^= digest[i] 338 done++ 339 } 340 incCounter(&counter) 341 } 342} 343 344// ErrMessageTooLong is returned when attempting to encrypt a message which is 345// too large for the size of the public key. 346var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size") 347 348func 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 352} 353 354// EncryptOAEP encrypts the given message with RSA-OAEP. 355// 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. 359// 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. 362// 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. 368// 369// The message must be no longer than the length of the public modulus minus 370// twice the hash length, minus a further 2. 371func 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 374 } 375 hash.Reset() 376 k := (pub.N.BitLen() + 7) / 8 377 if len(msg) > k-2*hash.Size()-2 { 378 return nil, ErrMessageTooLong 379 } 380 381 hash.Write(label) 382 lHash := hash.Sum(nil) 383 hash.Reset() 384 385 em := make([]byte, k) 386 seed := em[1 : 1+hash.Size()] 387 db := em[1+hash.Size():] 388 389 copy(db[0:hash.Size()], lHash) 390 db[len(db)-len(msg)-1] = 1 391 copy(db[len(db)-len(msg):], msg) 392 393 _, err := io.ReadFull(random, seed) 394 if err != nil { 395 return nil, err 396 } 397 398 mgf1XOR(db, hash, seed) 399 mgf1XOR(seed, hash, db) 400 401 m := new(big.Int) 402 m.SetBytes(em) 403 c := encrypt(new(big.Int), pub, m) 404 out := c.Bytes() 405 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 411 } 412 413 return out, nil 414} 415 416// ErrDecryption represents a failure to decrypt a message. 417// It is deliberately vague to avoid adaptive attacks. 418var ErrDecryption = errors.New("crypto/rsa: decryption error") 419 420// ErrVerification represents a failure to verify a signature. 421// It is deliberately vague to avoid adaptive attacks. 422var ErrVerification = errors.New("crypto/rsa: verification error") 423 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). 426func 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 436 } 437 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) 442 } 443 444 return x, true 445} 446 447// Precompute performs some calculations that speed up private key operations 448// in the future. 449func (priv *PrivateKey) Precompute() { 450 if priv.Precomputed.Dp != nil { 451 return 452 } 453 454 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne) 455 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp) 456 457 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne) 458 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq) 459 460 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0]) 461 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] 467 468 values.Exp = new(big.Int).Sub(prime, bigOne) 469 values.Exp.Mod(priv.D, values.Exp) 470 471 values.R = new(big.Int).Set(r) 472 values.Coeff = new(big.Int).ModInverse(r, prime) 473 474 r.Mul(r, prime) 475 } 476} 477 478// decrypt performs an RSA decryption, resulting in a plaintext integer. If a 479// random source is given, RSA blinding is used. 480func 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 485 } 486 if priv.N.Sign() == 0 { 487 return nil, ErrDecryption 488 } 489 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. 496 497 var r *big.Int 498 499 for { 500 r, err = rand.Int(random, priv.N) 501 if err != nil { 502 return 503 } 504 if r.Cmp(bigZero) == 0 { 505 r = bigOne 506 } 507 var ok bool 508 ir, ok = modInverse(r, priv.N) 509 if ok { 510 break 511 } 512 } 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 519 } 520 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]) 530 } 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) 535 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) 544 } 545 m2.Mul(m2, values.R) 546 m.Add(m, m2) 547 } 548 } 549 550 if ir != nil { 551 // Unblind. 552 m.Mul(m, ir) 553 m.Mod(m, priv.N) 554 } 555 556 return 557} 558 559func 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 563 } 564 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") 570 } 571 return m, nil 572} 573 574// DecryptOAEP decrypts ciphertext using RSA-OAEP. 575 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. 579// 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. 583// 584// The label parameter must match the value given when encrypting. See 585// EncryptOAEP for details. 586func 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 589 } 590 k := (priv.N.BitLen() + 7) / 8 591 if len(ciphertext) > k || 592 k < hash.Size()*2+2 { 593 return nil, ErrDecryption 594 } 595 596 c := new(big.Int).SetBytes(ciphertext) 597 598 m, err := decrypt(random, priv, c) 599 if err != nil { 600 return nil, err 601 } 602 603 hash.Write(label) 604 lHash := hash.Sum(nil) 605 hash.Reset() 606 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) 613 614 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0) 615 616 seed := em[1 : hash.Size()+1] 617 db := em[hash.Size()+1:] 618 619 mgf1XOR(seed, hash, db) 620 mgf1XOR(db, hash, seed) 621 622 lHash2 := db[0:hash.Size()] 623 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) 629 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():] 638 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) 645 } 646 647 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 { 648 return nil, ErrDecryption 649 } 650 651 return rest[index+1:], nil 652} 653 654// leftPad returns a new slice of length size. The contents of input are right 655// aligned in the new slice. 656func leftPad(input []byte, size int) (out []byte) { 657 n := len(input) 658 if n > size { 659 n = size 660 } 661 out = make([]byte, size) 662 copy(out[len(out)-n:], input) 663 return 664} 665