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.
8 // TODO(agl): Add support for PSS padding.
19 var bigZero = big.NewInt(0)
20 var bigOne = big.NewInt(1)
22 // A PublicKey represents the public part of an RSA key.
23 type PublicKey struct {
25 E int // public exponent
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.
34 // Precomputed contains precomputed values that speed up private
35 // operations, if available.
36 Precomputed PrecomputedValues
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
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.
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).
57 // Validate performs basic sanity checks on the key.
58 // It returns nil if the key is valid, or else an os.Error describing a problem.
60 func (priv *PrivateKey) Validate() os.Error {
61 // Check that the prime factors are actually prime. Note that this is
62 // just a sanity check. Since the random witnesses chosen by
63 // ProbablyPrime are deterministic, given the candidate number, it's
64 // easy for an attack to generate composites that pass this test.
65 for _, prime := range priv.Primes {
66 if !big.ProbablyPrime(prime, 20) {
67 return os.NewError("prime factor is composite")
71 // Check that Πprimes == n.
72 modulus := new(big.Int).Set(bigOne)
73 for _, prime := range priv.Primes {
74 modulus.Mul(modulus, prime)
76 if modulus.Cmp(priv.N) != 0 {
77 return os.NewError("invalid modulus")
79 // Check that e and totient(Πprimes) are coprime.
80 totient := new(big.Int).Set(bigOne)
81 for _, prime := range priv.Primes {
82 pminus1 := new(big.Int).Sub(prime, bigOne)
83 totient.Mul(totient, pminus1)
85 e := big.NewInt(int64(priv.E))
89 big.GcdInt(gcd, x, y, totient, e)
90 if gcd.Cmp(bigOne) != 0 {
91 return os.NewError("invalid public exponent E")
93 // Check that de ≡ 1 (mod totient(Πprimes))
94 de := new(big.Int).Mul(priv.D, e)
96 if de.Cmp(bigOne) != 0 {
97 return os.NewError("invalid private exponent D")
102 // GenerateKey generates an RSA keypair of the given bit size.
103 func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) {
104 return GenerateMultiPrimeKey(random, 2, bits)
107 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
108 // size, as suggested in [1]. Although the public keys are compatible
109 // (actually, indistinguishable) from the 2-prime case, the private keys are
110 // not. Thus it may not be possible to export multi-prime private keys in
111 // certain formats or to subsequently import them into other code.
113 // Table 1 in [2] suggests maximum numbers of primes for a given size.
115 // [1] US patent 4405829 (1972, expired)
116 // [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
117 func GenerateMultiPrimeKey(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err os.Error) {
118 priv = new(PrivateKey)
122 return nil, os.NewError("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
125 primes := make([]*big.Int, nprimes)
130 for i := 0; i < nprimes; i++ {
131 primes[i], err = rand.Prime(random, todo/(nprimes-i))
135 todo -= primes[i].BitLen()
138 // Make sure that primes is pairwise unequal.
139 for i, prime := range primes {
140 for j := 0; j < i; j++ {
141 if prime.Cmp(primes[j]) == 0 {
142 continue NextSetOfPrimes
147 n := new(big.Int).Set(bigOne)
148 totient := new(big.Int).Set(bigOne)
149 pminus1 := new(big.Int)
150 for _, prime := range primes {
152 pminus1.Sub(prime, bigOne)
153 totient.Mul(totient, pminus1)
157 priv.D = new(big.Int)
159 e := big.NewInt(int64(priv.E))
160 big.GcdInt(g, priv.D, y, e, totient)
162 if g.Cmp(bigOne) == 0 {
163 priv.D.Add(priv.D, totient)
175 // incCounter increments a four byte, big-endian counter.
176 func incCounter(c *[4]byte) {
177 if c[3]++; c[3] != 0 {
180 if c[2]++; c[2] != 0 {
183 if c[1]++; c[1] != 0 {
189 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
190 // specified in PKCS#1 v2.1.
191 func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
195 for done < len(out) {
197 hash.Write(counter[0:4])
201 for i := 0; i < len(digest) && done < len(out); i++ {
202 out[done] ^= digest[i]
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{}
213 func (MessageTooLongError) String() string {
214 return "message too long for RSA public key size"
217 func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
218 e := big.NewInt(int64(pub.E))
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 os.Error) {
228 k := (pub.N.BitLen() + 7) / 8
229 if len(msg) > k-2*hash.Size()-2 {
230 err = MessageTooLongError{}
238 em := make([]byte, k)
239 seed := em[1 : 1+hash.Size()]
240 db := em[1+hash.Size():]
242 copy(db[0:hash.Size()], lHash)
243 db[len(db)-len(msg)-1] = 1
244 copy(db[len(db)-len(msg):], msg)
246 _, err = io.ReadFull(random, seed)
251 mgf1XOR(db, hash, seed)
252 mgf1XOR(seed, hash, db)
256 c := encrypt(new(big.Int), pub, m)
260 // If the output is too small, we need to left-pad with zeros.
262 copy(t[k-len(out):], out)
269 // A DecryptionError represents a failure to decrypt a message.
270 // It is deliberately vague to avoid adaptive attacks.
271 type DecryptionError struct{}
273 func (DecryptionError) String() string { return "RSA decryption error" }
275 // A VerificationError represents a failure to verify a signature.
276 // It is deliberately vague to avoid adaptive attacks.
277 type VerificationError struct{}
279 func (VerificationError) String() string { return "RSA verification error" }
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) {
287 big.GcdInt(g, 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
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.
305 // Precompute performs some calculations that speed up private key operations
307 func (priv *PrivateKey) Precompute() {
308 if priv.Precomputed.Dp != nil {
312 priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
313 priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
315 priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
316 priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
318 priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
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]
326 values.Exp = new(big.Int).Sub(prime, bigOne)
327 values.Exp.Mod(priv.D, values.Exp)
329 values.R = new(big.Int).Set(r)
330 values.Coeff = new(big.Int).ModInverse(r, prime)
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 os.Error) {
339 // TODO(agl): can we get away with reusing blinds?
340 if c.Cmp(priv.N) > 0 {
341 err = DecryptionError{}
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.
355 r, err = rand.Int(random, priv.N)
359 if r.Cmp(bigZero) == 0 {
363 ir, ok = modInverse(r, priv.N)
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)
376 if priv.Precomputed.Dp == nil {
377 m = new(big.Int).Exp(c, priv.D, priv.N)
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])
384 m.Add(m, priv.Primes[0])
386 m.Mul(m, priv.Precomputed.Qinv)
387 m.Mod(m, priv.Primes[0])
388 m.Mul(m, priv.Primes[1])
391 for i, values := range priv.Precomputed.CRTValues {
392 prime := priv.Primes[2+i]
393 m2.Exp(c, values.Exp, prime)
395 m2.Mul(m2, values.Coeff)
414 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
415 // If rand != 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 os.Error) {
417 k := (priv.N.BitLen() + 7) / 8
418 if len(ciphertext) > k ||
419 k < hash.Size()*2+2 {
420 err = DecryptionError{}
424 c := new(big.Int).SetBytes(ciphertext)
426 m, err := decrypt(random, priv, c)
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)
442 firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
444 seed := em[1 : hash.Size()+1]
445 db := em[hash.Size()+1:]
447 mgf1XOR(seed, hash, db)
448 mgf1XOR(db, hash, seed)
450 lHash2 := db[0:hash.Size()]
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)
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
465 rest := db[hash.Size():]
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)
475 if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
476 err = DecryptionError{}
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) {
491 out = make([]byte, size)
492 copy(out[len(out)-n:], input)