libgo/go/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 // This package implements RSA encryption as specified in PKCS#1.
   6 package rsa
   7
   8 // TODO(agl): Add support for PSS padding.
   9
  10 import (
  11         "big"
  12         "crypto/subtle"
  13         "hash"
  14         "io"
  15         "os"
  16 )
  17
  18 var bigZero = big.NewInt(0)
  19 var bigOne = big.NewInt(1)
  20
  21 // randomPrime returns a number, p, of the given size, such that p is prime
  22 // with high probability.
  23 func randomPrime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
  24         if bits < 1 {
  25                 err = os.EINVAL
  26         }
  27
  28         bytes := make([]byte, (bits+7)/8)
  29         p = new(big.Int)
  30
  31         for {
  32                 _, err = io.ReadFull(rand, bytes)
  33                 if err != nil {
  34                         return
  35                 }
  36
  37                 // Don't let the value be too small.
  38                 bytes[0] |= 0x80
  39                 // Make the value odd since an even number this large certainly isn't prime.
  40                 bytes[len(bytes)-1] |= 1
  41
  42                 p.SetBytes(bytes)
  43                 if big.ProbablyPrime(p, 20) {
  44                         return
  45                 }
  46         }
  47
  48         return
  49 }
  50
  51 // randomNumber returns a uniform random value in [0, max).
  52 func randomNumber(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) {
  53         k := (max.BitLen() + 7) / 8
  54
  55         // r is the number of bits in the used in the most significant byte of
  56         // max.
  57         r := uint(max.BitLen() % 8)
  58         if r == 0 {
  59                 r = 8
  60         }
  61
  62         bytes := make([]byte, k)
  63         n = new(big.Int)
  64
  65         for {
  66                 _, err = io.ReadFull(rand, bytes)
  67                 if err != nil {
  68                         return
  69                 }
  70
  71                 // Clear bits in the first byte to increase the probability
  72                 // that the candidate is < max.
  73                 bytes[0] &= uint8(int(1<<r) - 1)
  74
  75                 n.SetBytes(bytes)
  76                 if n.Cmp(max) < 0 {
  77                         return
  78                 }
  79         }
  80
  81         return
  82 }
  83
  84 // A PublicKey represents the public part of an RSA key.
  85 type PublicKey struct {
  86         N *big.Int // modulus
  87         E int      // public exponent
  88 }
  89
  90 // A PrivateKey represents an RSA key
  91 type PrivateKey struct {
  92         PublicKey          // public part.
  93         D         *big.Int // private exponent
  94         P, Q      *big.Int // prime factors of N
  95 }
  96
  97 // Validate performs basic sanity checks on the key.
  98 // It returns nil if the key is valid, or else an os.Error describing a problem.
  99
 100 func (priv PrivateKey) Validate() os.Error {
 101         // Check that p and q are prime. Note that this is just a sanity
 102         // check. Since the random witnesses chosen by ProbablyPrime are
 103         // deterministic, given the candidate number, it's easy for an attack
 104         // to generate composites that pass this test.
 105         if !big.ProbablyPrime(priv.P, 20) {
 106                 return os.ErrorString("P is composite")
 107         }
 108         if !big.ProbablyPrime(priv.Q, 20) {
 109                 return os.ErrorString("Q is composite")
 110         }
 111
 112         // Check that p*q == n.
 113         modulus := new(big.Int).Mul(priv.P, priv.Q)
 114         if modulus.Cmp(priv.N) != 0 {
 115                 return os.ErrorString("invalid modulus")
 116         }
 117         // Check that e and totient(p, q) are coprime.
 118         pminus1 := new(big.Int).Sub(priv.P, bigOne)
 119         qminus1 := new(big.Int).Sub(priv.Q, bigOne)
 120         totient := new(big.Int).Mul(pminus1, qminus1)
 121         e := big.NewInt(int64(priv.E))
 122         gcd := new(big.Int)
 123         x := new(big.Int)
 124         y := new(big.Int)
 125         big.GcdInt(gcd, x, y, totient, e)
 126         if gcd.Cmp(bigOne) != 0 {
 127                 return os.ErrorString("invalid public exponent E")
 128         }
 129         // Check that de ≡ 1 (mod totient(p, q))
 130         de := new(big.Int).Mul(priv.D, e)
 131         de.Mod(de, totient)
 132         if de.Cmp(bigOne) != 0 {
 133                 return os.ErrorString("invalid private exponent D")
 134         }
 135         return nil
 136 }
 137
 138 // GenerateKeyPair generates an RSA keypair of the given bit size.
 139 func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
 140         priv = new(PrivateKey)
 141         // Smaller public exponents lead to faster public key
 142         // operations. Since the exponent must be coprime to
 143         // (p-1)(q-1), the smallest possible value is 3. Some have
 144         // suggested that a larger exponent (often 2**16+1) be used
 145         // since previous implementation bugs[1] were avoided when this
 146         // was the case. However, there are no current reasons not to use
 147         // small exponents.
 148         // [1] http://marc.info/?l=cryptography&m=115694833312008&w=2
 149         priv.E = 3
 150
 151         pminus1 := new(big.Int)
 152         qminus1 := new(big.Int)
 153         totient := new(big.Int)
 154
 155         for {
 156                 p, err := randomPrime(rand, bits/2)
 157                 if err != nil {
 158                         return nil, err
 159                 }
 160
 161                 q, err := randomPrime(rand, bits/2)
 162                 if err != nil {
 163                         return nil, err
 164                 }
 165
 166                 if p.Cmp(q) == 0 {
 167                         continue
 168                 }
 169
 170                 n := new(big.Int).Mul(p, q)
 171                 pminus1.Sub(p, bigOne)
 172                 qminus1.Sub(q, bigOne)
 173                 totient.Mul(pminus1, qminus1)
 174
 175                 g := new(big.Int)
 176                 priv.D = new(big.Int)
 177                 y := new(big.Int)
 178                 e := big.NewInt(int64(priv.E))
 179                 big.GcdInt(g, priv.D, y, e, totient)
 180
 181                 if g.Cmp(bigOne) == 0 {
 182                         priv.D.Add(priv.D, totient)
 183                         priv.P = p
 184                         priv.Q = q
 185                         priv.N = n
 186
 187                         break
 188                 }
 189         }
 190
 191         return
 192 }
 193
 194 // incCounter increments a four byte, big-endian counter.
 195 func incCounter(c *[4]byte) {
 196         if c[3]++; c[3] != 0 {
 197                 return
 198         }
 199         if c[2]++; c[2] != 0 {
 200                 return
 201         }
 202         if c[1]++; c[1] != 0 {
 203                 return
 204         }
 205         c[0]++
 206 }
 207
 208 // mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
 209 // specified in PKCS#1 v2.1.
 210 func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
 211         var counter [4]byte
 212
 213         done := 0
 214         for done < len(out) {
 215                 hash.Write(seed)
 216                 hash.Write(counter[0:4])
 217                 digest := hash.Sum()
 218                 hash.Reset()
 219
 220                 for i := 0; i < len(digest) && done < len(out); i++ {
 221                         out[done] ^= digest[i]
 222                         done++
 223                 }
 224                 incCounter(&counter)
 225         }
 226 }
 227
 228 // MessageTooLongError is returned when attempting to encrypt a message which
 229 // is too large for the size of the public key.
 230 type MessageTooLongError struct{}
 231
 232 func (MessageTooLongError) String() string {
 233         return "message too long for RSA public key size"
 234 }
 235
 236 func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
 237         e := big.NewInt(int64(pub.E))
 238         c.Exp(m, e, pub.N)
 239         return c
 240 }
 241
 242 // EncryptOAEP encrypts the given message with RSA-OAEP.
 243 // The message must be no longer than the length of the public modulus less
 244 // twice the hash length plus 2.
 245 func EncryptOAEP(hash hash.Hash, rand io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err os.Error) {
 246         hash.Reset()
 247         k := (pub.N.BitLen() + 7) / 8
 248         if len(msg) > k-2*hash.Size()-2 {
 249                 err = MessageTooLongError{}
 250                 return
 251         }
 252
 253         hash.Write(label)
 254         lHash := hash.Sum()
 255         hash.Reset()
 256
 257         em := make([]byte, k)
 258         seed := em[1 : 1+hash.Size()]
 259         db := em[1+hash.Size():]
 260
 261         copy(db[0:hash.Size()], lHash)
 262         db[len(db)-len(msg)-1] = 1
 263         copy(db[len(db)-len(msg):], msg)
 264
 265         _, err = io.ReadFull(rand, seed)
 266         if err != nil {
 267                 return
 268         }
 269
 270         mgf1XOR(db, hash, seed)
 271         mgf1XOR(seed, hash, db)
 272
 273         m := new(big.Int)
 274         m.SetBytes(em)
 275         c := encrypt(new(big.Int), pub, m)
 276         out = c.Bytes()
 277         return
 278 }
 279
 280 // A DecryptionError represents a failure to decrypt a message.
 281 // It is deliberately vague to avoid adaptive attacks.
 282 type DecryptionError struct{}
 283
 284 func (DecryptionError) String() string { return "RSA decryption error" }
 285
 286 // A VerificationError represents a failure to verify a signature.
 287 // It is deliberately vague to avoid adaptive attacks.
 288 type VerificationError struct{}
 289
 290 func (VerificationError) String() string { return "RSA verification error" }
 291
 292 // modInverse returns ia, the inverse of a in the multiplicative group of prime
 293 // order n. It requires that a be a member of the group (i.e. less than n).
 294 func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
 295         g := new(big.Int)
 296         x := new(big.Int)
 297         y := new(big.Int)
 298         big.GcdInt(g, x, y, a, n)
 299         if g.Cmp(bigOne) != 0 {
 300                 // In this case, a and n aren't coprime and we cannot calculate
 301                 // the inverse. This happens because the values of n are nearly
 302                 // prime (being the product of two primes) rather than truly
 303                 // prime.
 304                 return
 305         }
 306
 307         if x.Cmp(bigOne) < 0 {
 308                 // 0 is not the multiplicative inverse of any element so, if x
 309                 // < 1, then x is negative.
 310                 x.Add(x, n)
 311         }
 312
 313         return x, true
 314 }
 315
 316 // decrypt performs an RSA decryption, resulting in a plaintext integer. If a
 317 // random source is given, RSA blinding is used.
 318 func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.Error) {
 319         // TODO(agl): can we get away with reusing blinds?
 320         if c.Cmp(priv.N) > 0 {
 321                 err = DecryptionError{}
 322                 return
 323         }
 324
 325         var ir *big.Int
 326         if rand != nil {
 327                 // Blinding enabled. Blinding involves multiplying c by r^e.
 328                 // Then the decryption operation performs (m^e * r^e)^d mod n
 329                 // which equals mr mod n. The factor of r can then be removed
 330                 // by multipling by the multiplicative inverse of r.
 331
 332                 var r *big.Int
 333
 334                 for {
 335                         r, err = randomNumber(rand, priv.N)
 336                         if err != nil {
 337                                 return
 338                         }
 339                         if r.Cmp(bigZero) == 0 {
 340                                 r = bigOne
 341                         }
 342                         var ok bool
 343                         ir, ok = modInverse(r, priv.N)
 344                         if ok {
 345                                 break
 346                         }
 347                 }
 348                 bigE := big.NewInt(int64(priv.E))
 349                 rpowe := new(big.Int).Exp(r, bigE, priv.N)
 350                 c.Mul(c, rpowe)
 351                 c.Mod(c, priv.N)
 352         }
 353
 354         m = new(big.Int).Exp(c, priv.D, priv.N)
 355
 356         if ir != nil {
 357                 // Unblind.
 358                 m.Mul(m, ir)
 359                 m.Mod(m, priv.N)
 360         }
 361
 362         return
 363 }
 364
 365 // DecryptOAEP decrypts ciphertext using RSA-OAEP.
 366 // If rand != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks.
 367 func DecryptOAEP(hash hash.Hash, rand io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err os.Error) {
 368         k := (priv.N.BitLen() + 7) / 8
 369         if len(ciphertext) > k ||
 370                 k < hash.Size()*2+2 {
 371                 err = DecryptionError{}
 372                 return
 373         }
 374
 375         c := new(big.Int).SetBytes(ciphertext)
 376
 377         m, err := decrypt(rand, priv, c)
 378         if err != nil {
 379                 return
 380         }
 381
 382         hash.Write(label)
 383         lHash := hash.Sum()
 384         hash.Reset()
 385
 386         // Converting the plaintext number to bytes will strip any
 387         // leading zeros so we may have to left pad. We do this unconditionally
 388         // to avoid leaking timing information. (Although we still probably
 389         // leak the number of leading zeros. It's not clear that we can do
 390         // anything about this.)
 391         em := leftPad(m.Bytes(), k)
 392
 393         firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
 394
 395         seed := em[1 : hash.Size()+1]
 396         db := em[hash.Size()+1:]
 397
 398         mgf1XOR(seed, hash, db)
 399         mgf1XOR(db, hash, seed)
 400
 401         lHash2 := db[0:hash.Size()]
 402
 403         // We have to validate the plaintext in constant time in order to avoid
 404         // attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
 405         // Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
 406         // v2.0. In J. Kilian, editor, Advances in Cryptology.
 407         lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
 408
 409         // The remainder of the plaintext must be zero or more 0x00, followed
 410         // by 0x01, followed by the message.
 411         //   lookingForIndex: 1 iff we are still looking for the 0x01
 412         //   index: the offset of the first 0x01 byte
 413         //   invalid: 1 iff we saw a non-zero byte before the 0x01.
 414         var lookingForIndex, index, invalid int
 415         lookingForIndex = 1
 416         rest := db[hash.Size():]
 417
 418         for i := 0; i < len(rest); i++ {
 419                 equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
 420                 equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
 421                 index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
 422                 lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
 423                 invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
 424         }
 425
 426         if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
 427                 err = DecryptionError{}
 428                 return
 429         }
 430
 431         msg = rest[index+1:]
 432         return
 433 }
 434
 435 // leftPad returns a new slice of length size. The contents of input are right
 436 // aligned in the new slice.
 437 func leftPad(input []byte, size int) (out []byte) {
 438         n := len(input)
 439         if n > size {
 440                 n = size
 441         }
 442         out = make([]byte, size)
 443         copy(out[len(out)-n:], input)
 444         return
 445 }