summaryrefslogtreecommitdiff
path: root/src/pkg/crypto/rsa/rsa.go
diff options
context:
space:
mode:
Diffstat (limited to 'src/pkg/crypto/rsa/rsa.go')
-rw-r--r--src/pkg/crypto/rsa/rsa.go290
1 files changed, 126 insertions, 164 deletions
diff --git a/src/pkg/crypto/rsa/rsa.go b/src/pkg/crypto/rsa/rsa.go
index b3b212c20..e1813dbf9 100644
--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -2,7 +2,7 @@
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
-// This package implements RSA encryption as specified in PKCS#1.
+// Package rsa implements RSA encryption as specified in PKCS#1.
package rsa
// TODO(agl): Add support for PSS padding.
@@ -13,7 +13,6 @@ import (
"hash"
"io"
"os"
- "sync"
)
var bigZero = big.NewInt(0)
@@ -90,50 +89,60 @@ type PublicKey struct {
// A PrivateKey represents an RSA key
type PrivateKey struct {
- PublicKey // public part.
- D *big.Int // private exponent
- P, Q, R *big.Int // prime factors of N (R may be nil)
-
- rwMutex sync.RWMutex // protects the following
- dP, dQ, dR *big.Int // D mod (P-1) (or mod Q-1 etc)
- qInv *big.Int // q^-1 mod p
- pq *big.Int // P*Q
- tr *big.Int // pq·tr ≡ 1 mod r
+ PublicKey // public part.
+ D *big.Int // private exponent
+ Primes []*big.Int // prime factors of N, has >= 2 elements.
+
+ // Precomputed contains precomputed values that speed up private
+ // operations, if availible.
+ Precomputed PrecomputedValues
+}
+
+type PrecomputedValues struct {
+ Dp, Dq *big.Int // D mod (P-1) (or mod Q-1)
+ Qinv *big.Int // Q^-1 mod Q
+
+ // CRTValues is used for the 3rd and subsequent primes. Due to a
+ // historical accident, the CRT for the first two primes is handled
+ // differently in PKCS#1 and interoperability is sufficiently
+ // important that we mirror this.
+ CRTValues []CRTValue
+}
+
+// CRTValue contains the precomputed chinese remainder theorem values.
+type CRTValue struct {
+ Exp *big.Int // D mod (prime-1).
+ Coeff *big.Int // R·Coeff ≡ 1 mod Prime.
+ R *big.Int // product of primes prior to this (inc p and q).
}
// Validate performs basic sanity checks on the key.
// It returns nil if the key is valid, or else an os.Error describing a problem.
func (priv *PrivateKey) Validate() os.Error {
- // Check that p, q and, maybe, r are prime. Note that this is just a
- // sanity check. Since the random witnesses chosen by ProbablyPrime are
- // deterministic, given the candidate number, it's easy for an attack
- // to generate composites that pass this test.
- if !big.ProbablyPrime(priv.P, 20) {
- return os.ErrorString("P is composite")
- }
- if !big.ProbablyPrime(priv.Q, 20) {
- return os.ErrorString("Q is composite")
- }
- if priv.R != nil && !big.ProbablyPrime(priv.R, 20) {
- return os.ErrorString("R is composite")
+ // Check that the prime factors are actually prime. Note that this is
+ // just a sanity check. Since the random witnesses chosen by
+ // ProbablyPrime are deterministic, given the candidate number, it's
+ // easy for an attack to generate composites that pass this test.
+ for _, prime := range priv.Primes {
+ if !big.ProbablyPrime(prime, 20) {
+ return os.ErrorString("Prime factor is composite")
+ }
}
- // Check that p*q*r == n.
- modulus := new(big.Int).Mul(priv.P, priv.Q)
- if priv.R != nil {
- modulus.Mul(modulus, priv.R)
+ // Check that Πprimes == n.
+ modulus := new(big.Int).Set(bigOne)
+ for _, prime := range priv.Primes {
+ modulus.Mul(modulus, prime)
}
if modulus.Cmp(priv.N) != 0 {
return os.ErrorString("invalid modulus")
}
- // Check that e and totient(p, q, r) are coprime.
- pminus1 := new(big.Int).Sub(priv.P, bigOne)
- qminus1 := new(big.Int).Sub(priv.Q, bigOne)
- totient := new(big.Int).Mul(pminus1, qminus1)
- if priv.R != nil {
- rminus1 := new(big.Int).Sub(priv.R, bigOne)
- totient.Mul(totient, rminus1)
+ // Check that e and totient(Πprimes) are coprime.
+ totient := new(big.Int).Set(bigOne)
+ for _, prime := range priv.Primes {
+ pminus1 := new(big.Int).Sub(prime, bigOne)
+ totient.Mul(totient, pminus1)
}
e := big.NewInt(int64(priv.E))
gcd := new(big.Int)
@@ -143,7 +152,7 @@ func (priv *PrivateKey) Validate() os.Error {
if gcd.Cmp(bigOne) != 0 {
return os.ErrorString("invalid public exponent E")
}
- // Check that de ≡ 1 (mod totient(p, q, r))
+ // Check that de ≡ 1 (mod totient(Πprimes))
de := new(big.Int).Mul(priv.D, e)
de.Mod(de, totient)
if de.Cmp(bigOne) != 0 {
@@ -154,6 +163,20 @@ func (priv *PrivateKey) Validate() os.Error {
// GenerateKey generates an RSA keypair of the given bit size.
func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
+ return GenerateMultiPrimeKey(rand, 2, bits)
+}
+
+// GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit
+// size, as suggested in [1]. Although the public keys are compatible
+// (actually, indistinguishable) from the 2-prime case, the private keys are
+// not. Thus it may not be possible to export multi-prime private keys in
+// certain formats or to subsequently import them into other code.
+//
+// Table 1 in [2] suggests maximum numbers of primes for a given size.
+//
+// [1] US patent 4405829 (1972, expired)
+// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
+func GenerateMultiPrimeKey(rand io.Reader, nprimes int, bits int) (priv *PrivateKey, err os.Error) {
priv = new(PrivateKey)
// Smaller public exponents lead to faster public key
// operations. Since the exponent must be coprime to
@@ -165,100 +188,41 @@ func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
// [1] http://marc.info/?l=cryptography&m=115694833312008&w=2
priv.E = 3
- pminus1 := new(big.Int)
- qminus1 := new(big.Int)
- totient := new(big.Int)
-
- for {
- p, err := randomPrime(rand, bits/2)
- if err != nil {
- return nil, err
- }
-
- q, err := randomPrime(rand, bits/2)
- if err != nil {
- return nil, err
- }
-
- if p.Cmp(q) == 0 {
- continue
- }
-
- n := new(big.Int).Mul(p, q)
- pminus1.Sub(p, bigOne)
- qminus1.Sub(q, bigOne)
- totient.Mul(pminus1, qminus1)
-
- g := new(big.Int)
- priv.D = new(big.Int)
- y := new(big.Int)
- e := big.NewInt(int64(priv.E))
- big.GcdInt(g, priv.D, y, e, totient)
-
- if g.Cmp(bigOne) == 0 {
- priv.D.Add(priv.D, totient)
- priv.P = p
- priv.Q = q
- priv.N = n
-
- break
- }
+ if nprimes < 2 {
+ return nil, os.ErrorString("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
}
- return
-}
-
-// Generate3PrimeKey generates a 3-prime RSA keypair of the given bit size, as
-// suggested in [1]. Although the public keys are compatible (actually,
-// indistinguishable) from the 2-prime case, the private keys are not. Thus it
-// may not be possible to export 3-prime private keys in certain formats or to
-// subsequently import them into other code.
-//
-// Table 1 in [2] suggests that size should be >= 1024 when using 3 primes.
-//
-// [1] US patent 4405829 (1972, expired)
-// [2] http://www.cacr.math.uwaterloo.ca/techreports/2006/cacr2006-16.pdf
-func Generate3PrimeKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
- priv = new(PrivateKey)
- priv.E = 3
-
- pminus1 := new(big.Int)
- qminus1 := new(big.Int)
- rminus1 := new(big.Int)
- totient := new(big.Int)
+ primes := make([]*big.Int, nprimes)
+NextSetOfPrimes:
for {
- p, err := randomPrime(rand, bits/3)
- if err != nil {
- return nil, err
- }
-
- todo := bits - p.BitLen()
- q, err := randomPrime(rand, todo/2)
- if err != nil {
- return nil, err
+ todo := bits
+ for i := 0; i < nprimes; i++ {
+ primes[i], err = randomPrime(rand, todo/(nprimes-i))
+ if err != nil {
+ return nil, err
+ }
+ todo -= primes[i].BitLen()
}
- todo -= q.BitLen()
- r, err := randomPrime(rand, todo)
- if err != nil {
- return nil, err
+ // Make sure that primes is pairwise unequal.
+ for i, prime := range primes {
+ for j := 0; j < i; j++ {
+ if prime.Cmp(primes[j]) == 0 {
+ continue NextSetOfPrimes
+ }
+ }
}
- if p.Cmp(q) == 0 ||
- q.Cmp(r) == 0 ||
- r.Cmp(p) == 0 {
- continue
+ n := new(big.Int).Set(bigOne)
+ totient := new(big.Int).Set(bigOne)
+ pminus1 := new(big.Int)
+ for _, prime := range primes {
+ n.Mul(n, prime)
+ pminus1.Sub(prime, bigOne)
+ totient.Mul(totient, pminus1)
}
- n := new(big.Int).Mul(p, q)
- n.Mul(n, r)
- pminus1.Sub(p, bigOne)
- qminus1.Sub(q, bigOne)
- rminus1.Sub(r, bigOne)
- totient.Mul(pminus1, qminus1)
- totient.Mul(totient, rminus1)
-
g := new(big.Int)
priv.D = new(big.Int)
y := new(big.Int)
@@ -267,15 +231,14 @@ func Generate3PrimeKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error
if g.Cmp(bigOne) == 0 {
priv.D.Add(priv.D, totient)
- priv.P = p
- priv.Q = q
- priv.R = r
+ priv.Primes = primes
priv.N = n
break
}
}
+ priv.Precompute()
return
}
@@ -409,23 +372,34 @@ func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
return x, true
}
-// precompute performs some calculations that speed up private key operations
+// Precompute performs some calculations that speed up private key operations
// in the future.
-func (priv *PrivateKey) precompute() {
- priv.dP = new(big.Int).Sub(priv.P, bigOne)
- priv.dP.Mod(priv.D, priv.dP)
+func (priv *PrivateKey) Precompute() {
+ if priv.Precomputed.Dp != nil {
+ return
+ }
- priv.dQ = new(big.Int).Sub(priv.Q, bigOne)
- priv.dQ.Mod(priv.D, priv.dQ)
+ priv.Precomputed.Dp = new(big.Int).Sub(priv.Primes[0], bigOne)
+ priv.Precomputed.Dp.Mod(priv.D, priv.Precomputed.Dp)
- priv.qInv = new(big.Int).ModInverse(priv.Q, priv.P)
+ priv.Precomputed.Dq = new(big.Int).Sub(priv.Primes[1], bigOne)
+ priv.Precomputed.Dq.Mod(priv.D, priv.Precomputed.Dq)
- if priv.R != nil {
- priv.dR = new(big.Int).Sub(priv.R, bigOne)
- priv.dR.Mod(priv.D, priv.dR)
+ priv.Precomputed.Qinv = new(big.Int).ModInverse(priv.Primes[1], priv.Primes[0])
- priv.pq = new(big.Int).Mul(priv.P, priv.Q)
- priv.tr = new(big.Int).ModInverse(priv.pq, priv.R)
+ r := new(big.Int).Mul(priv.Primes[0], priv.Primes[1])
+ priv.Precomputed.CRTValues = make([]CRTValue, len(priv.Primes)-2)
+ for i := 2; i < len(priv.Primes); i++ {
+ prime := priv.Primes[i]
+ values := &priv.Precomputed.CRTValues[i-2]
+
+ values.Exp = new(big.Int).Sub(prime, bigOne)
+ values.Exp.Mod(priv.D, values.Exp)
+
+ values.R = new(big.Int).Set(r)
+ values.Coeff = new(big.Int).ModInverse(r, prime)
+
+ r.Mul(r, prime)
}
}
@@ -463,53 +437,41 @@ func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.E
}
bigE := big.NewInt(int64(priv.E))
rpowe := new(big.Int).Exp(r, bigE, priv.N)
- c.Mul(c, rpowe)
- c.Mod(c, priv.N)
- }
-
- priv.rwMutex.RLock()
-
- if priv.dP == nil && priv.P != nil {
- priv.rwMutex.RUnlock()
- priv.rwMutex.Lock()
- if priv.dP == nil && priv.P != nil {
- priv.precompute()
- }
- priv.rwMutex.Unlock()
- priv.rwMutex.RLock()
+ cCopy := new(big.Int).Set(c)
+ cCopy.Mul(cCopy, rpowe)
+ cCopy.Mod(cCopy, priv.N)
+ c = cCopy
}
- if priv.dP == nil {
+ if priv.Precomputed.Dp == nil {
m = new(big.Int).Exp(c, priv.D, priv.N)
} else {
// We have the precalculated values needed for the CRT.
- m = new(big.Int).Exp(c, priv.dP, priv.P)
- m2 := new(big.Int).Exp(c, priv.dQ, priv.Q)
+ m = new(big.Int).Exp(c, priv.Precomputed.Dp, priv.Primes[0])
+ m2 := new(big.Int).Exp(c, priv.Precomputed.Dq, priv.Primes[1])
m.Sub(m, m2)
if m.Sign() < 0 {
- m.Add(m, priv.P)
+ m.Add(m, priv.Primes[0])
}
- m.Mul(m, priv.qInv)
- m.Mod(m, priv.P)
- m.Mul(m, priv.Q)
+ m.Mul(m, priv.Precomputed.Qinv)
+ m.Mod(m, priv.Primes[0])
+ m.Mul(m, priv.Primes[1])
m.Add(m, m2)
- if priv.dR != nil {
- // 3-prime CRT.
- m2.Exp(c, priv.dR, priv.R)
+ for i, values := range priv.Precomputed.CRTValues {
+ prime := priv.Primes[2+i]
+ m2.Exp(c, values.Exp, prime)
m2.Sub(m2, m)
- m2.Mul(m2, priv.tr)
- m2.Mod(m2, priv.R)
+ m2.Mul(m2, values.Coeff)
+ m2.Mod(m2, prime)
if m2.Sign() < 0 {
- m2.Add(m2, priv.R)
+ m2.Add(m2, prime)
}
- m2.Mul(m2, priv.pq)
+ m2.Mul(m2, values.R)
m.Add(m, m2)
}
}
- priv.rwMutex.RUnlock()
-
if ir != nil {
// Unblind.
m.Mul(m, ir)