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 neccessary, 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. 21package rsa 22 23import ( 24 "crypto" 25 "crypto/rand" 26 "crypto/subtle" 27 "errors" 28 "hash" 29 "io" 30 "math/big" 31) 32 33var bigZero = big.NewInt(0) 34var bigOne = big.NewInt(1) 35 36// A PublicKey represents the public part of an RSA key. 37type PublicKey struct { 38 N *big.Int // modulus 39 E int64 // public exponent 40} 41 42// OAEPOptions is an interface for passing options to OAEP decryption using the 43// crypto.Decrypter interface. 44type OAEPOptions struct { 45 // Hash is the hash function that will be used when generating the mask. 46 Hash crypto.Hash 47 // Label is an arbitrary byte string that must be equal to the value 48 // used when encrypting. 49 Label []byte 50} 51 52var ( 53 errPublicModulus = errors.New("crypto/rsa: missing public modulus") 54 errPublicExponentSmall = errors.New("crypto/rsa: public exponent too small") 55 errPublicExponentLarge = errors.New("crypto/rsa: public exponent too large") 56) 57 58// checkPub sanity checks the public key before we use it. 59// We require pub.E to fit into a 32-bit integer so that we 60// do not have different behavior depending on whether 61// int is 32 or 64 bits. See also 62// http://www.imperialviolet.org/2012/03/16/rsae.html. 63func checkPub(pub *PublicKey) error { 64 if pub.N == nil { 65 return errPublicModulus 66 } 67 if pub.E < 2 { 68 return errPublicExponentSmall 69 } 70 if pub.E > 1<<63-1 { 71 return errPublicExponentLarge 72 } 73 return nil 74} 75 76// A PrivateKey represents an RSA key 77type PrivateKey struct { 78 PublicKey // public part. 79 D *big.Int // private exponent 80 Primes []*big.Int // prime factors of N, has >= 2 elements. 81 82 // Precomputed contains precomputed values that speed up private 83 // operations, if available. 84 Precomputed PrecomputedValues 85} 86 87// Public returns the public key corresponding to priv. 88func (priv *PrivateKey) Public() crypto.PublicKey { 89 return &priv.PublicKey 90} 91 92// Sign signs msg with priv, reading randomness from rand. If opts is a 93// *PSSOptions then the PSS algorithm will be used, otherwise PKCS#1 v1.5 will 94// be used. This method is intended to support keys where the private part is 95// kept in, for example, a hardware module. Common uses should use the Sign* 96// functions in this package. 97func (priv *PrivateKey) Sign(rand io.Reader, msg []byte, opts crypto.SignerOpts) ([]byte, error) { 98 if pssOpts, ok := opts.(*PSSOptions); ok { 99 return SignPSS(rand, priv, pssOpts.Hash, msg, pssOpts) 100 } 101 102 return SignPKCS1v15(rand, priv, opts.HashFunc(), msg) 103} 104 105// Decrypt decrypts ciphertext with priv. If opts is nil or of type 106// *PKCS1v15DecryptOptions then PKCS#1 v1.5 decryption is performed. Otherwise 107// opts must have type *OAEPOptions and OAEP decryption is done. 108func (priv *PrivateKey) Decrypt(rand io.Reader, ciphertext []byte, opts crypto.DecrypterOpts) (plaintext []byte, err error) { 109 if opts == nil { 110 return DecryptPKCS1v15(rand, priv, ciphertext) 111 } 112 113 switch opts := opts.(type) { 114 case *OAEPOptions: 115 return DecryptOAEP(opts.Hash.New(), rand, priv, ciphertext, opts.Label) 116 117 case *PKCS1v15DecryptOptions: 118 if l := opts.SessionKeyLen; l > 0 { 119 plaintext = make([]byte, l) 120 if _, err := io.ReadFull(rand, plaintext); err != nil { 121 return nil, err 122 } 123 if err := DecryptPKCS1v15SessionKey(rand, priv, ciphertext, plaintext); err != nil { 124 return nil, err 125 } 126 return plaintext, nil 127 } else { 128 return DecryptPKCS1v15(rand, priv, ciphertext) 129 } 130 131 default: 132 return nil, errors.New("crypto/rsa: invalid options for Decrypt") 133 } 134} 135 136type PrecomputedValues struct { 137 Dp, Dq *big.Int // D mod (P-1) (or mod Q-1) 138 Qinv *big.Int // Q^-1 mod P 139 140 // CRTValues is used for the 3rd and subsequent primes. Due to a 141 // historical accident, the CRT for the first two primes is handled 142 // differently in PKCS#1 and interoperability is sufficiently 143 // important that we mirror this. 144 CRTValues []CRTValue 145} 146 147// CRTValue contains the precomputed Chinese remainder theorem values. 148type CRTValue struct { 149 Exp *big.Int // D mod (prime-1). 150 Coeff *big.Int // R·Coeff ≡ 1 mod Prime. 151 R *big.Int // product of primes prior to this (inc p and q). 152} 153 154// Validate performs basic sanity checks on the key. 155// It returns nil if the key is valid, or else an error describing a problem. 156func (priv *PrivateKey) Validate() error { 157 if err := checkPub(&priv.PublicKey); err != nil { 158 return err 159 } 160 161 // Check that Πprimes == n. 162 modulus := new(big.Int).Set(bigOne) 163 for _, prime := range priv.Primes { 164 // Any primes ≤ 1 will cause divide-by-zero panics later. 165 if prime.Cmp(bigOne) <= 0 { 166 return errors.New("crypto/rsa: invalid prime value") 167 } 168 modulus.Mul(modulus, prime) 169 } 170 if modulus.Cmp(priv.N) != 0 { 171 return errors.New("crypto/rsa: invalid modulus") 172 } 173 174 // Check that de ≡ 1 mod p-1, for each prime. 175 // This implies that e is coprime to each p-1 as e has a multiplicative 176 // inverse. Therefore e is coprime to lcm(p-1,q-1,r-1,...) = 177 // exponent(ℤ/nℤ). It also implies that a^de ≡ a mod p as a^(p-1) ≡ 1 178 // mod p. Thus a^de ≡ a mod n for all a coprime to n, as required. 179 congruence := new(big.Int) 180 de := new(big.Int).SetInt64(int64(priv.E)) 181 de.Mul(de, priv.D) 182 for _, prime := range priv.Primes { 183 pminus1 := new(big.Int).Sub(prime, bigOne) 184 congruence.Mod(de, pminus1) 185 if congruence.Cmp(bigOne) != 0 { 186 return errors.New("crypto/rsa: invalid exponents") 187 } 188 } 189 return nil 190} 191 192// GenerateKey generates an RSA keypair of the given bit size using the 193// random source random (for example, crypto/rand.Reader). 194func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err error) { 195 return GenerateMultiPrimeKey(random, 2, bits) 196} 197 198// GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit 199// size and the given random source, as suggested in [1]. Although the public 200// keys are compatible (actually, indistinguishable) from the 2-prime case, 201// the private keys are not. Thus it may not be possible to export multi-prime 202// private keys in certain formats or to subsequently import them into other 203// code. 204// 205// Table 1 in [2] suggests maximum numbers of primes for a given size. 206// 207// [1] US patent 4405829 (1972, expired) 208// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf 209func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err error) { 210 priv = new(PrivateKey) 211 priv.E = 65537 212 213 if nprimes < 2 { 214 return nil, errors.New("crypto/rsa: GenerateMultiPrimeKey: nprimes must be >= 2") 215 } 216 217 primes := make([]*big.Int, nprimes) 218 219NextSetOfPrimes: 220 for { 221 todo := bits 222 // crypto/rand should set the top two bits in each prime. 223 // Thus each prime has the form 224 // p_i = 2^bitlen(p_i) × 0.11... (in base 2). 225 // And the product is: 226 // P = 2^todo × α 227 // where α is the product of nprimes numbers of the form 0.11... 228 // 229 // If α < 1/2 (which can happen for nprimes > 2), we need to 230 // shift todo to compensate for lost bits: the mean value of 0.11... 231 // is 7/8, so todo + shift - nprimes * log2(7/8) ~= bits - 1/2 232 // will give good results. 233 if nprimes >= 7 { 234 todo += (nprimes - 2) / 5 235 } 236 for i := 0; i < nprimes; i++ { 237 primes[i], err = rand.Prime(random, todo/(nprimes-i)) 238 if err != nil { 239 return nil, err 240 } 241 todo -= primes[i].BitLen() 242 } 243 244 // Make sure that primes is pairwise unequal. 245 for i, prime := range primes { 246 for j := 0; j < i; j++ { 247 if prime.Cmp(primes[j]) == 0 { 248 continue NextSetOfPrimes 249 } 250 } 251 } 252 253 n := new(big.Int).Set(bigOne) 254 totient := new(big.Int).Set(bigOne) 255 pminus1 := new(big.Int) 256 for _, prime := range primes { 257 n.Mul(n, prime) 258 pminus1.Sub(prime, bigOne) 259 totient.Mul(totient, pminus1) 260 } 261 if n.BitLen() != bits { 262 // This should never happen for nprimes == 2 because 263 // crypto/rand should set the top two bits in each prime. 264 // For nprimes > 2 we hope it does not happen often. 265 continue NextSetOfPrimes 266 } 267 268 g := new(big.Int) 269 priv.D = new(big.Int) 270 y := new(big.Int) 271 e := big.NewInt(int64(priv.E)) 272 g.GCD(priv.D, y, e, totient) 273 274 if g.Cmp(bigOne) == 0 { 275 if priv.D.Sign() < 0 { 276 priv.D.Add(priv.D, totient) 277 } 278 priv.Primes = primes 279 priv.N = n 280 281 break 282 } 283 } 284 285 priv.Precompute() 286 return 287} 288 289// incCounter increments a four byte, big-endian counter. 290func incCounter(c *[4]byte) { 291 if c[3]++; c[3] != 0 { 292 return 293 } 294 if c[2]++; c[2] != 0 { 295 return 296 } 297 if c[1]++; c[1] != 0 { 298 return 299 } 300 c[0]++ 301} 302 303// mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function 304// specified in PKCS#1 v2.1. 305func mgf1XOR(out []byte, hash hash.Hash, seed []byte) { 306 var counter [4]byte 307 var digest []byte 308 309 done := 0 310 for done < len(out) { 311 hash.Write(seed) 312 hash.Write(counter[0:4]) 313 digest = hash.Sum(digest[:0]) 314 hash.Reset() 315 316 for i := 0; i < len(digest) && done < len(out); i++ { 317 out[done] ^= digest[i] 318 done++ 319 } 320 incCounter(&counter) 321 } 322} 323 324// ErrMessageTooLong is returned when attempting to encrypt a message which is 325// too large for the size of the public key. 326var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size") 327 328func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int { 329 e := big.NewInt(int64(pub.E)) 330 c.Exp(m, e, pub.N) 331 return c 332} 333 334// EncryptOAEP encrypts the given message with RSA-OAEP. 335// 336// OAEP is parameterised by a hash function that is used as a random oracle. 337// Encryption and decryption of a given message must use the same hash function 338// and sha256.New() is a reasonable choice. 339// 340// The random parameter is used as a source of entropy to ensure that 341// encrypting the same message twice doesn't result in the same ciphertext. 342// 343// The label parameter may contain arbitrary data that will not be encrypted, 344// but which gives important context to the message. For example, if a given 345// public key is used to decrypt two types of messages then distinct label 346// values could be used to ensure that a ciphertext for one purpose cannot be 347// used for another by an attacker. If not required it can be empty. 348// 349// The message must be no longer than the length of the public modulus less 350// twice the hash length plus 2. 351func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err error) { 352 if err := checkPub(pub); err != nil { 353 return nil, err 354 } 355 hash.Reset() 356 k := (pub.N.BitLen() + 7) / 8 357 if len(msg) > k-2*hash.Size()-2 { 358 err = ErrMessageTooLong 359 return 360 } 361 362 hash.Write(label) 363 lHash := hash.Sum(nil) 364 hash.Reset() 365 366 em := make([]byte, k) 367 seed := em[1 : 1+hash.Size()] 368 db := em[1+hash.Size():] 369 370 copy(db[0:hash.Size()], lHash) 371 db[len(db)-len(msg)-1] = 1 372 copy(db[len(db)-len(msg):], msg) 373 374 _, err = io.ReadFull(random, seed) 375 if err != nil { 376 return 377 } 378 379 mgf1XOR(db, hash, seed) 380 mgf1XOR(seed, hash, db) 381 382 m := new(big.Int) 383 m.SetBytes(em) 384 c := encrypt(new(big.Int), pub, m) 385 out = c.Bytes() 386 387 if len(out) < k { 388 // If the output is too small, we need to left-pad with zeros. 389 t := make([]byte, k) 390 copy(t[k-len(out):], out) 391 out = t 392 } 393 394 return 395} 396 397// ErrDecryption represents a failure to decrypt a message. 398// It is deliberately vague to avoid adaptive attacks. 399var ErrDecryption = errors.New("crypto/rsa: decryption error") 400 401// ErrVerification represents a failure to verify a signature. 402// It is deliberately vague to avoid adaptive attacks. 403var ErrVerification = errors.New("crypto/rsa: verification error") 404 405// modInverse returns ia, the inverse of a in the multiplicative group of prime 406// order n. It requires that a be a member of the group (i.e. less than n). 407func modInverse(a, n *big.Int) (ia *big.Int, ok bool) { 408 g := new(big.Int) 409 x := new(big.Int) 410 y := new(big.Int) 411 g.GCD(x, y, a, n) 412 if g.Cmp(bigOne) != 0 { 413 // In this case, a and n aren't coprime and we cannot calculate 414 // the inverse. This happens because the values of n are nearly 415 // prime (being the product of two primes) rather than truly 416 // prime. 417 return 418 } 419 420 if x.Cmp(bigOne) < 0 { 421 // 0 is not the multiplicative inverse of any element so, if x 422 // < 1, then x is negative. 423 x.Add(x, n) 424 } 425 426 return x, true 427} 428 429// Precompute performs some calculations that speed up private key operations 430// in the future. 431func (priv *PrivateKey) Precompute() { 432 if priv.Precomputed.Dp != nil { 433 return 434 } 435 436 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne) 437 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp) 438 439 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne) 440 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq) 441 442 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0]) 443 444 r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1]) 445 priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2) 446 for i := 2; i < len(priv.Primes); i++ { 447 prime := priv.Primes[i] 448 values := &priv.Precomputed.CRTValues[i-2] 449 450 values.Exp = new(big.Int).Sub(prime, bigOne) 451 values.Exp.Mod(priv.D, values.Exp) 452 453 values.R = new(big.Int).Set(r) 454 values.Coeff = new(big.Int).ModInverse(r, prime) 455 456 r.Mul(r, prime) 457 } 458} 459 460// decrypt performs an RSA decryption, resulting in a plaintext integer. If a 461// random source is given, RSA blinding is used. 462func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) { 463 // TODO(agl): can we get away with reusing blinds? 464 if c.Cmp(priv.N) > 0 { 465 err = ErrDecryption 466 return 467 } 468 469 var ir *big.Int 470 if random != nil { 471 // Blinding enabled. Blinding involves multiplying c by r^e. 472 // Then the decryption operation performs (m^e * r^e)^d mod n 473 // which equals mr mod n. The factor of r can then be removed 474 // by multiplying by the multiplicative inverse of r. 475 476 var r *big.Int 477 478 for { 479 r, err = rand.Int(random, priv.N) 480 if err != nil { 481 return 482 } 483 if r.Cmp(bigZero) == 0 { 484 r = bigOne 485 } 486 var ok bool 487 ir, ok = modInverse(r, priv.N) 488 if ok { 489 break 490 } 491 } 492 bigE := big.NewInt(int64(priv.E)) 493 rpowe := new(big.Int).Exp(r, bigE, priv.N) 494 cCopy := new(big.Int).Set(c) 495 cCopy.Mul(cCopy, rpowe) 496 cCopy.Mod(cCopy, priv.N) 497 c = cCopy 498 } 499 500 if priv.Precomputed.Dp == nil { 501 m = new(big.Int).Exp(c, priv.D, priv.N) 502 } else { 503 // We have the precalculated values needed for the CRT. 504 m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0]) 505 m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1]) 506 m.Sub(m, m2) 507 if m.Sign() < 0 { 508 m.Add(m, priv.Primes[0]) 509 } 510 m.Mul(m, priv.Precomputed.Qinv) 511 m.Mod(m, priv.Primes[0]) 512 m.Mul(m, priv.Primes[1]) 513 m.Add(m, m2) 514 515 for i, values := range priv.Precomputed.CRTValues { 516 prime := priv.Primes[2+i] 517 m2.Exp(c, values.Exp, prime) 518 m2.Sub(m2, m) 519 m2.Mul(m2, values.Coeff) 520 m2.Mod(m2, prime) 521 if m2.Sign() < 0 { 522 m2.Add(m2, prime) 523 } 524 m2.Mul(m2, values.R) 525 m.Add(m, m2) 526 } 527 } 528 529 if ir != nil { 530 // Unblind. 531 m.Mul(m, ir) 532 m.Mod(m, priv.N) 533 } 534 535 return 536} 537 538func decryptAndCheck(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) { 539 m, err = decrypt(random, priv, c) 540 if err != nil { 541 return nil, err 542 } 543 544 // In order to defend against errors in the CRT computation, m^e is 545 // calculated, which should match the original ciphertext. 546 check := encrypt(new(big.Int), &priv.PublicKey, m) 547 if c.Cmp(check) != 0 { 548 return nil, errors.New("rsa: internal error") 549 } 550 return m, nil 551} 552 553// DecryptOAEP decrypts ciphertext using RSA-OAEP. 554 555// OAEP is parameterised by a hash function that is used as a random oracle. 556// Encryption and decryption of a given message must use the same hash function 557// and sha256.New() is a reasonable choice. 558// 559// The random parameter, if not nil, is used to blind the private-key operation 560// and avoid timing side-channel attacks. Blinding is purely internal to this 561// function – the random data need not match that used when encrypting. 562// 563// The label parameter must match the value given when encrypting. See 564// EncryptOAEP for details. 565func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) { 566 if err := checkPub(&priv.PublicKey); err != nil { 567 return nil, err 568 } 569 k := (priv.N.BitLen() + 7) / 8 570 if len(ciphertext) > k || 571 k < hash.Size()*2+2 { 572 err = ErrDecryption 573 return 574 } 575 576 c := new(big.Int).SetBytes(ciphertext) 577 578 m, err := decrypt(random, priv, c) 579 if err != nil { 580 return 581 } 582 583 hash.Write(label) 584 lHash := hash.Sum(nil) 585 hash.Reset() 586 587 // Converting the plaintext number to bytes will strip any 588 // leading zeros so we may have to left pad. We do this unconditionally 589 // to avoid leaking timing information. (Although we still probably 590 // leak the number of leading zeros. It's not clear that we can do 591 // anything about this.) 592 em := leftPad(m.Bytes(), k) 593 594 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0) 595 596 seed := em[1 : hash.Size()+1] 597 db := em[hash.Size()+1:] 598 599 mgf1XOR(seed, hash, db) 600 mgf1XOR(db, hash, seed) 601 602 lHash2 := db[0:hash.Size()] 603 604 // We have to validate the plaintext in constant time in order to avoid 605 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal 606 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 607 // v2.0. In J. Kilian, editor, Advances in Cryptology. 608 lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2) 609 610 // The remainder of the plaintext must be zero or more 0x00, followed 611 // by 0x01, followed by the message. 612 // lookingForIndex: 1 iff we are still looking for the 0x01 613 // index: the offset of the first 0x01 byte 614 // invalid: 1 iff we saw a non-zero byte before the 0x01. 615 var lookingForIndex, index, invalid int 616 lookingForIndex = 1 617 rest := db[hash.Size():] 618 619 for i := 0; i < len(rest); i++ { 620 equals0 := subtle.ConstantTimeByteEq(rest[i], 0) 621 equals1 := subtle.ConstantTimeByteEq(rest[i], 1) 622 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index) 623 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex) 624 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid) 625 } 626 627 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 { 628 err = ErrDecryption 629 return 630 } 631 632 msg = rest[index+1:] 633 return 634} 635 636// leftPad returns a new slice of length size. The contents of input are right 637// aligned in the new slice. 638func leftPad(input []byte, size int) (out []byte) { 639 n := len(input) 640 if n > size { 641 n = size 642 } 643 out = make([]byte, size) 644 copy(out[len(out)-n:], input) 645 return 646} 647