Golang big.GcdInt类(方法)实例源码

// 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)

	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 -= q.BitLen()
		r, err := randomPrime(rand, todo)
		if err != nil {
			return nil, err
		}

		if p.Cmp(q) == 0 ||
			q.Cmp(r) == 0 ||
			r.Cmp(p) == 0 {
			continue
		}

		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)
		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.R = r
			priv.N = n

			break
		}
	}

	return
}

// 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(random io.Reader, nprimes int, bits int) (priv *PrivateKey, err error) {
	priv = new(PrivateKey)
	priv.E = 65537

	if nprimes < 2 {
		return nil, errors.New("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		for i := 0; i < nprimes; i++ {
			primes[i], err = rand.Prime(random, todo/(nprimes-i))
			if err != nil {
				return nil, err
			}
			todo -= primes[i].BitLen()
		}

		// 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
				}
			}
		}

		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)
		}

		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.Primes = primes
			priv.N = n

			break
		}
	}

	priv.Precompute()
	return
}

// GenerateKeyPair generates an RSA keypair of the given bit size.
func GenerateKey(rand io.Reader, 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
	// (p-1)(q-1), the smallest possible value is 3. Some have
	// suggested that a larger exponent (often 2**16+1) be used
	// since previous implementation bugs[1] were avoided when this
	// was the case. However, there are no current reasons not to use
	// small exponents.
	// [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
		}
	}

	return
}

// modInverse returns ia, the inverse of a in the multiplicative group of prime
// order n. It requires that a be a member of the group (i.e. less than n).
func modInverse(a, n *big.Int) (ia *big.Int) {
	g := new(big.Int)
	x := new(big.Int)
	y := new(big.Int)
	big.GcdInt(g, x, y, a, n)
	if big.CmpInt(x, bigOne) < 0 {
		// 0 is not the multiplicative inverse of any element so, if x
		// < 1, then x is negative.
		x.Add(x, n)
	}

	return x
}

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 p*q*r == n.
	modulus := new(big.Int).Mul(priv.P, priv.Q)
	if priv.R != nil {
		modulus.Mul(modulus, priv.R)
	}
	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)
	}
	e := big.NewInt(int64(priv.E))
	gcd := new(big.Int)
	x := new(big.Int)
	y := new(big.Int)
	big.GcdInt(gcd, x, y, totient, e)
	if gcd.Cmp(bigOne) != 0 {
		return os.ErrorString("invalid public exponent E")
	}
	// Check that de ≡ 1 (mod totient(p, q, r))
	de := new(big.Int).Mul(priv.D, e)
	de.Mod(de, totient)
	if de.Cmp(bigOne) != 0 {
		return os.ErrorString("invalid private exponent D")
	}
	return nil
}

func (priv *PrivateKey) Validate() os.Error {
	// 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 Π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(Π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)
	x := new(big.Int)
	y := new(big.Int)
	big.GcdInt(gcd, x, y, totient, e)
	if gcd.Cmp(bigOne) != 0 {
		return os.ErrorString("invalid public exponent E")
	}
	// Check that de ≡ 1 (mod totient(Πprimes))
	de := new(big.Int).Mul(priv.D, e)
	de.Mod(de, totient)
	if de.Cmp(bigOne) != 0 {
		return os.ErrorString("invalid private exponent D")
	}
	return nil
}

// modInverse returns ia, the inverse of a in the multiplicative group of prime
// order n. It requires that a be a member of the group (i.e. less than n).
func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
	g := new(big.Int)
	x := new(big.Int)
	y := new(big.Int)
	big.GcdInt(g, x, y, a, n)
	if g.Cmp(bigOne) != 0 {
		// In this case, a and n aren't coprime and we cannot calculate
		// the inverse. This happens because the values of n are nearly
		// prime (being the product of two primes) rather than truly
		// prime.
		return
	}

	if x.Cmp(bigOne) < 0 {
		// 0 is not the multiplicative inverse of any element so, if x
		// < 1, then x is negative.
		x.Add(x, n)
	}

	return x, true
}

func (priv PrivateKey) Validate() os.Error {
	/*
		TODO(agl): Enable once big implements ProbablyPrime.

		// Check that p and q are prime.
		if !priv.P.ProbablyPrime(20) {
			return os.ErrorString("P is composite");
		}
		if !priv.Q.ProbablyPrime(20) {
			return os.ErrorString("Q is composite");
		}
	*/
	// Check that p*q == n.
	modulus := new(big.Int).Mul(priv.P, priv.Q)
	if big.CmpInt(modulus, priv.N) != 0 {
		return os.ErrorString("invalid modulus")
	}
	// Check that e and totient(p, q) 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)
	e := big.NewInt(int64(priv.E))
	gcd := new(big.Int)
	x := new(big.Int)
	y := new(big.Int)
	big.GcdInt(gcd, x, y, totient, e)
	if big.CmpInt(gcd, bigOne) != 0 {
		return os.ErrorString("invalid public exponent E")
	}
	// Check that de ≡ 1 (mod totient(p, q))
	de := new(big.Int).Mul(priv.D, e)
	de.Mod(de, totient)
	if big.CmpInt(de, bigOne) != 0 {
		return os.ErrorString("invalid private exponent D")
	}
	return nil
}

// 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(random 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
	// (p-1)(q-1), the smallest possible value is 3. Some have
	// suggested that a larger exponent (often 2**16+1) be used
	// since previous implementation bugs[1] were avoided when this
	// was the case. However, there are no current reasons not to use
	// small exponents.
	// [1] http://marc.info/?l=cryptography&m=115694833312008&w=2
	priv.E = 3

	if nprimes < 2 {
		return nil, os.ErrorString("rsa.GenerateMultiPrimeKey: nprimes must be >= 2")
	}

	primes := make([]*big.Int, nprimes)

NextSetOfPrimes:
	for {
		todo := bits
		for i := 0; i < nprimes; i++ {
			primes[i], err = rand.Prime(random, todo/(nprimes-i))
			if err != nil {
				return nil, err
			}
			todo -= primes[i].BitLen()
		}

		// 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
				}
			}
		}

		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)
		}

		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.Primes = primes
			priv.N = n

			break
		}
	}

	priv.Precompute()
	return
}