Source file src/pkg/crypto/rsa/rsa.go
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 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 // ErrMessageTooLong is returned when attempting to encrypt a message which is 210 // too large for the size of the public key. 211 var ErrMessageTooLong = errors.New("crypto/rsa: message too long for RSA public key size") 212 213 func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int { 214 e := big.NewInt(int64(pub.E)) 215 c.Exp(m, e, pub.N) 216 return c 217 } 218 219 // EncryptOAEP encrypts the given message with RSA-OAEP. 220 // The message must be no longer than the length of the public modulus less 221 // twice the hash length plus 2. 222 func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err error) { 223 hash.Reset() 224 k := (pub.N.BitLen() + 7) / 8 225 if len(msg) > k-2*hash.Size()-2 { 226 err = ErrMessageTooLong 227 return 228 } 229 230 hash.Write(label) 231 lHash := hash.Sum(nil) 232 hash.Reset() 233 234 em := make([]byte, k) 235 seed := em[1 : 1+hash.Size()] 236 db := em[1+hash.Size():] 237 238 copy(db[0:hash.Size()], lHash) 239 db[len(db)-len(msg)-1] = 1 240 copy(db[len(db)-len(msg):], msg) 241 242 _, err = io.ReadFull(random, seed) 243 if err != nil { 244 return 245 } 246 247 mgf1XOR(db, hash, seed) 248 mgf1XOR(seed, hash, db) 249 250 m := new(big.Int) 251 m.SetBytes(em) 252 c := encrypt(new(big.Int), pub, m) 253 out = c.Bytes() 254 255 if len(out) < k { 256 // If the output is too small, we need to left-pad with zeros. 257 t := make([]byte, k) 258 copy(t[k-len(out):], out) 259 out = t 260 } 261 262 return 263 } 264 265 // ErrDecryption represents a failure to decrypt a message. 266 // It is deliberately vague to avoid adaptive attacks. 267 var ErrDecryption = errors.New("crypto/rsa: decryption error") 268 269 // ErrVerification represents a failure to verify a signature. 270 // It is deliberately vague to avoid adaptive attacks. 271 var ErrVerification = errors.New("crypto/rsa: verification error") 272 273 // modInverse returns ia, the inverse of a in the multiplicative group of prime 274 // order n. It requires that a be a member of the group (i.e. less than n). 275 func modInverse(a, n *big.Int) (ia *big.Int, ok bool) { 276 g := new(big.Int) 277 x := new(big.Int) 278 y := new(big.Int) 279 g.GCD(x, y, a, n) 280 if g.Cmp(bigOne) != 0 { 281 // In this case, a and n aren't coprime and we cannot calculate 282 // the inverse. This happens because the values of n are nearly 283 // prime (being the product of two primes) rather than truly 284 // prime. 285 return 286 } 287 288 if x.Cmp(bigOne) < 0 { 289 // 0 is not the multiplicative inverse of any element so, if x 290 // < 1, then x is negative. 291 x.Add(x, n) 292 } 293 294 return x, true 295 } 296 297 // Precompute performs some calculations that speed up private key operations 298 // in the future. 299 func (priv *PrivateKey) Precompute() { 300 if priv.Precomputed.Dp != nil { 301 return 302 } 303 304 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne) 305 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp) 306 307 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne) 308 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq) 309 310 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0]) 311 312 r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1]) 313 priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2) 314 for i := 2; i < len(priv.Primes); i++ { 315 prime := priv.Primes[i] 316 values := &priv.Precomputed.CRTValues[i-2] 317 318 values.Exp = new(big.Int).Sub(prime, bigOne) 319 values.Exp.Mod(priv.D, values.Exp) 320 321 values.R = new(big.Int).Set(r) 322 values.Coeff = new(big.Int).ModInverse(r, prime) 323 324 r.Mul(r, prime) 325 } 326 } 327 328 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a 329 // random source is given, RSA blinding is used. 330 func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err error) { 331 // TODO(agl): can we get away with reusing blinds? 332 if c.Cmp(priv.N) > 0 { 333 err = ErrDecryption 334 return 335 } 336 337 var ir *big.Int 338 if random != nil { 339 // Blinding enabled. Blinding involves multiplying c by r^e. 340 // Then the decryption operation performs (m^e * r^e)^d mod n 341 // which equals mr mod n. The factor of r can then be removed 342 // by multiplying by the multiplicative inverse of r. 343 344 var r *big.Int 345 346 for { 347 r, err = rand.Int(random, priv.N) 348 if err != nil { 349 return 350 } 351 if r.Cmp(bigZero) == 0 { 352 r = bigOne 353 } 354 var ok bool 355 ir, ok = modInverse(r, priv.N) 356 if ok { 357 break 358 } 359 } 360 bigE := big.NewInt(int64(priv.E)) 361 rpowe := new(big.Int).Exp(r, bigE, priv.N) 362 cCopy := new(big.Int).Set(c) 363 cCopy.Mul(cCopy, rpowe) 364 cCopy.Mod(cCopy, priv.N) 365 c = cCopy 366 } 367 368 if priv.Precomputed.Dp == nil { 369 m = new(big.Int).Exp(c, priv.D, priv.N) 370 } else { 371 // We have the precalculated values needed for the CRT. 372 m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0]) 373 m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1]) 374 m.Sub(m, m2) 375 if m.Sign() < 0 { 376 m.Add(m, priv.Primes[0]) 377 } 378 m.Mul(m, priv.Precomputed.Qinv) 379 m.Mod(m, priv.Primes[0]) 380 m.Mul(m, priv.Primes[1]) 381 m.Add(m, m2) 382 383 for i, values := range priv.Precomputed.CRTValues { 384 prime := priv.Primes[2+i] 385 m2.Exp(c, values.Exp, prime) 386 m2.Sub(m2, m) 387 m2.Mul(m2, values.Coeff) 388 m2.Mod(m2, prime) 389 if m2.Sign() < 0 { 390 m2.Add(m2, prime) 391 } 392 m2.Mul(m2, values.R) 393 m.Add(m, m2) 394 } 395 } 396 397 if ir != nil { 398 // Unblind. 399 m.Mul(m, ir) 400 m.Mod(m, priv.N) 401 } 402 403 return 404 } 405 406 // DecryptOAEP decrypts ciphertext using RSA-OAEP. 407 // If random != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks. 408 func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) { 409 k := (priv.N.BitLen() + 7) / 8 410 if len(ciphertext) > k || 411 k < hash.Size()*2+2 { 412 err = ErrDecryption 413 return 414 } 415 416 c := new(big.Int).SetBytes(ciphertext) 417 418 m, err := decrypt(random, priv, c) 419 if err != nil { 420 return 421 } 422 423 hash.Write(label) 424 lHash := hash.Sum(nil) 425 hash.Reset() 426 427 // Converting the plaintext number to bytes will strip any 428 // leading zeros so we may have to left pad. We do this unconditionally 429 // to avoid leaking timing information. (Although we still probably 430 // leak the number of leading zeros. It's not clear that we can do 431 // anything about this.) 432 em := leftPad(m.Bytes(), k) 433 434 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0) 435 436 seed := em[1 : hash.Size()+1] 437 db := em[hash.Size()+1:] 438 439 mgf1XOR(seed, hash, db) 440 mgf1XOR(db, hash, seed) 441 442 lHash2 := db[0:hash.Size()] 443 444 // We have to validate the plaintext in constant time in order to avoid 445 // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal 446 // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1 447 // v2.0. In J. Kilian, editor, Advances in Cryptology. 448 lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2) 449 450 // The remainder of the plaintext must be zero or more 0x00, followed 451 // by 0x01, followed by the message. 452 // lookingForIndex: 1 iff we are still looking for the 0x01 453 // index: the offset of the first 0x01 byte 454 // invalid: 1 iff we saw a non-zero byte before the 0x01. 455 var lookingForIndex, index, invalid int 456 lookingForIndex = 1 457 rest := db[hash.Size():] 458 459 for i := 0; i < len(rest); i++ { 460 equals0 := subtle.ConstantTimeByteEq(rest[i], 0) 461 equals1 := subtle.ConstantTimeByteEq(rest[i], 1) 462 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index) 463 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex) 464 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid) 465 } 466 467 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 { 468 err = ErrDecryption 469 return 470 } 471 472 msg = rest[index+1:] 473 return 474 } 475 476 // leftPad returns a new slice of length size. The contents of input are right 477 // aligned in the new slice. 478 func leftPad(input []byte, size int) (out []byte) { 479 n := len(input) 480 if n > size { 481 n = size 482 } 483 out = make([]byte, size) 484 copy(out[len(out)-n:], input) 485 return 486 }