OLD | NEW |
1 // Copyright 2009 The Go Authors. All rights reserved. | 1 // Copyright 2009 The Go Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style | 2 // Use of this source code is governed by a BSD-style |
3 // license that can be found in the LICENSE file. | 3 // license that can be found in the LICENSE file. |
4 | 4 |
5 // Package rsa implements RSA encryption as specified in PKCS#1. | 5 // Package rsa implements RSA encryption as specified in PKCS#1. |
6 package rsa | 6 package rsa |
7 | 7 |
8 // TODO(agl): Add support for PSS padding. | 8 // TODO(agl): Add support for PSS padding. |
9 | 9 |
10 import ( | 10 import ( |
(...skipping 46 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
57 // Validate performs basic sanity checks on the key. | 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. | 58 // It returns nil if the key is valid, or else an os.Error describing a problem. |
59 | 59 |
60 func (priv *PrivateKey) Validate() os.Error { | 60 func (priv *PrivateKey) Validate() os.Error { |
61 // Check that the prime factors are actually prime. Note that this is | 61 // Check that the prime factors are actually prime. Note that this is |
62 // just a sanity check. Since the random witnesses chosen by | 62 // just a sanity check. Since the random witnesses chosen by |
63 // ProbablyPrime are deterministic, given the candidate number, it's | 63 // ProbablyPrime are deterministic, given the candidate number, it's |
64 // easy for an attack to generate composites that pass this test. | 64 // easy for an attack to generate composites that pass this test. |
65 for _, prime := range priv.Primes { | 65 for _, prime := range priv.Primes { |
66 if !big.ProbablyPrime(prime, 20) { | 66 if !big.ProbablyPrime(prime, 20) { |
67 » » » return os.ErrorString("prime factor is composite") | 67 » » » return os.NewError("prime factor is composite") |
68 } | 68 } |
69 } | 69 } |
70 | 70 |
71 // Check that Πprimes == n. | 71 // Check that Πprimes == n. |
72 modulus := new(big.Int).Set(bigOne) | 72 modulus := new(big.Int).Set(bigOne) |
73 for _, prime := range priv.Primes { | 73 for _, prime := range priv.Primes { |
74 modulus.Mul(modulus, prime) | 74 modulus.Mul(modulus, prime) |
75 } | 75 } |
76 if modulus.Cmp(priv.N) != 0 { | 76 if modulus.Cmp(priv.N) != 0 { |
77 » » return os.ErrorString("invalid modulus") | 77 » » return os.NewError("invalid modulus") |
78 } | 78 } |
79 // Check that e and totient(Πprimes) are coprime. | 79 // Check that e and totient(Πprimes) are coprime. |
80 totient := new(big.Int).Set(bigOne) | 80 totient := new(big.Int).Set(bigOne) |
81 for _, prime := range priv.Primes { | 81 for _, prime := range priv.Primes { |
82 pminus1 := new(big.Int).Sub(prime, bigOne) | 82 pminus1 := new(big.Int).Sub(prime, bigOne) |
83 totient.Mul(totient, pminus1) | 83 totient.Mul(totient, pminus1) |
84 } | 84 } |
85 e := big.NewInt(int64(priv.E)) | 85 e := big.NewInt(int64(priv.E)) |
86 gcd := new(big.Int) | 86 gcd := new(big.Int) |
87 x := new(big.Int) | 87 x := new(big.Int) |
88 y := new(big.Int) | 88 y := new(big.Int) |
89 big.GcdInt(gcd, x, y, totient, e) | 89 big.GcdInt(gcd, x, y, totient, e) |
90 if gcd.Cmp(bigOne) != 0 { | 90 if gcd.Cmp(bigOne) != 0 { |
91 » » return os.ErrorString("invalid public exponent E") | 91 » » return os.NewError("invalid public exponent E") |
92 } | 92 } |
93 // Check that de ≡ 1 (mod totient(Πprimes)) | 93 // Check that de ≡ 1 (mod totient(Πprimes)) |
94 de := new(big.Int).Mul(priv.D, e) | 94 de := new(big.Int).Mul(priv.D, e) |
95 de.Mod(de, totient) | 95 de.Mod(de, totient) |
96 if de.Cmp(bigOne) != 0 { | 96 if de.Cmp(bigOne) != 0 { |
97 » » return os.ErrorString("invalid private exponent D") | 97 » » return os.NewError("invalid private exponent D") |
98 } | 98 } |
99 return nil | 99 return nil |
100 } | 100 } |
101 | 101 |
102 // GenerateKey generates an RSA keypair of the given bit size. | 102 // GenerateKey generates an RSA keypair of the given bit size. |
103 func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) { | 103 func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) { |
104 return GenerateMultiPrimeKey(random, 2, bits) | 104 return GenerateMultiPrimeKey(random, 2, bits) |
105 } | 105 } |
106 | 106 |
107 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit | 107 // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit |
(...skipping 12 matching lines...) Expand all Loading... |
120 // operations. Since the exponent must be coprime to | 120 // operations. Since the exponent must be coprime to |
121 // (p-1)(q-1), the smallest possible value is 3. Some have | 121 // (p-1)(q-1), the smallest possible value is 3. Some have |
122 // suggested that a larger exponent (often 2**16+1) be used | 122 // suggested that a larger exponent (often 2**16+1) be used |
123 // since previous implementation bugs[1] were avoided when this | 123 // since previous implementation bugs[1] were avoided when this |
124 // was the case. However, there are no current reasons not to use | 124 // was the case. However, there are no current reasons not to use |
125 // small exponents. | 125 // small exponents. |
126 // [1] http://marc.info/?l=cryptography&m=115694833312008&w=2 | 126 // [1] http://marc.info/?l=cryptography&m=115694833312008&w=2 |
127 priv.E = 3 | 127 priv.E = 3 |
128 | 128 |
129 if nprimes < 2 { | 129 if nprimes < 2 { |
130 » » return nil, os.ErrorString("rsa.GenerateMultiPrimeKey: nprimes m
ust be >= 2") | 130 » » return nil, os.NewError("rsa.GenerateMultiPrimeKey: nprimes must
be >= 2") |
131 } | 131 } |
132 | 132 |
133 primes := make([]*big.Int, nprimes) | 133 primes := make([]*big.Int, nprimes) |
134 | 134 |
135 NextSetOfPrimes: | 135 NextSetOfPrimes: |
136 for { | 136 for { |
137 todo := bits | 137 todo := bits |
138 for i := 0; i < nprimes; i++ { | 138 for i := 0; i < nprimes; i++ { |
139 primes[i], err = rand.Prime(random, todo/(nprimes-i)) | 139 primes[i], err = rand.Prime(random, todo/(nprimes-i)) |
140 if err != nil { | 140 if err != nil { |
(...skipping 352 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
493 // aligned in the new slice. | 493 // aligned in the new slice. |
494 func leftPad(input []byte, size int) (out []byte) { | 494 func leftPad(input []byte, size int) (out []byte) { |
495 n := len(input) | 495 n := len(input) |
496 if n > size { | 496 if n > size { |
497 n = size | 497 n = size |
498 } | 498 } |
499 out = make([]byte, size) | 499 out = make([]byte, size) |
500 copy(out[len(out)-n:], input) | 500 copy(out[len(out)-n:], input) |
501 return | 501 return |
502 } | 502 } |
OLD | NEW |