diff options
author | Anthony Martin <ality@pbrane.org> | 2011-05-18 18:55:06 -0700 |
---|---|---|
committer | Adam Langley <agl@golang.org> | 2011-05-18 18:55:06 -0700 |
commit | 24b2f48a4a5abc4a35e0ddf104e1d22e6ba1cdaa (patch) | |
tree | 14de5fcd8ffd66f31357539d1569ea153542797f | |
parent | 4ffff35abd9562007b0cf4ee8034ded8760e5e2a (diff) | |
download | go-24b2f48a4a5abc4a35e0ddf104e1d22e6ba1cdaa.tar.gz go-24b2f48a4a5abc4a35e0ddf104e1d22e6ba1cdaa.zip |
crypto/rand: add utility functions for number generation
This code is extracted from crypto/rsa with
a few variables renamed and a comment fixed.
R=agl, rsc, agl
CC=golang-dev
https://golang.org/cl/4446068
-rw-r--r-- | src/pkg/crypto/rand/Makefile | 1 | ||||
-rw-r--r-- | src/pkg/crypto/rand/util.go | 80 | ||||
-rw-r--r-- | src/pkg/crypto/rsa/rsa.go | 86 |
3 files changed, 93 insertions, 74 deletions
diff --git a/src/pkg/crypto/rand/Makefile b/src/pkg/crypto/rand/Makefile index 88b6d71e33..d1321297d9 100644 --- a/src/pkg/crypto/rand/Makefile +++ b/src/pkg/crypto/rand/Makefile @@ -8,6 +8,7 @@ TARG=crypto/rand GOFILES=\ rand.go\ + util.go\ GOFILES_freebsd=\ rand_unix.go\ diff --git a/src/pkg/crypto/rand/util.go b/src/pkg/crypto/rand/util.go new file mode 100644 index 0000000000..77028476e4 --- /dev/null +++ b/src/pkg/crypto/rand/util.go @@ -0,0 +1,80 @@ +// Copyright 2011 The Go Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +package rand + +import ( + "big" + "io" + "os" +) + +// Prime returns a number, p, of the given size, such that p is prime +// with high probability. +func Prime(rand io.Reader, bits int) (p *big.Int, err os.Error) { + if bits < 1 { + err = os.EINVAL + } + + b := uint(bits % 8) + if b == 0 { + b = 8 + } + + bytes := make([]byte, (bits+7)/8) + p = new(big.Int) + + for { + _, err = io.ReadFull(rand, bytes) + if err != nil { + return nil, err + } + + // Clear bits in the first byte to make sure the candidate has a size <= bits. + bytes[0] &= uint8(int(1<<b) - 1) + // Don't let the value be too small, i.e, set the most significant bit. + bytes[0] |= 1 << (b - 1) + // Make the value odd since an even number this large certainly isn't prime. + bytes[len(bytes)-1] |= 1 + + p.SetBytes(bytes) + if big.ProbablyPrime(p, 20) { + return + } + } + + return +} + +// Int returns a uniform random value in [0, max). +func Int(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) { + k := (max.BitLen() + 7) / 8 + + // b is the number of bits in the most significant byte of max. + b := uint(max.BitLen() % 8) + if b == 0 { + b = 8 + } + + bytes := make([]byte, k) + n = new(big.Int) + + for { + _, err = io.ReadFull(rand, bytes) + if err != nil { + return nil, err + } + + // Clear bits in the first byte to increase the probability + // that the candidate is < max. + bytes[0] &= uint8(int(1<<b) - 1) + + n.SetBytes(bytes) + if n.Cmp(max) < 0 { + return + } + } + + return +} diff --git a/src/pkg/crypto/rsa/rsa.go b/src/pkg/crypto/rsa/rsa.go index c702ab1c0e..6bfe6c4e52 100644 --- a/src/pkg/crypto/rsa/rsa.go +++ b/src/pkg/crypto/rsa/rsa.go @@ -9,6 +9,7 @@ package rsa import ( "big" + "crypto/rand" "crypto/subtle" "hash" "io" @@ -18,69 +19,6 @@ import ( var bigZero = big.NewInt(0) var bigOne = big.NewInt(1) -// randomPrime returns a number, p, of the given size, such that p is prime -// with high probability. -func randomPrime(rand io.Reader, bits int) (p *big.Int, err os.Error) { - if bits < 1 { - err = os.EINVAL - } - - bytes := make([]byte, (bits+7)/8) - p = new(big.Int) - - for { - _, err = io.ReadFull(rand, bytes) - if err != nil { - return - } - - // Don't let the value be too small. - bytes[0] |= 0x80 - // Make the value odd since an even number this large certainly isn't prime. - bytes[len(bytes)-1] |= 1 - - p.SetBytes(bytes) - if big.ProbablyPrime(p, 20) { - return - } - } - - return -} - -// randomNumber returns a uniform random value in [0, max). -func randomNumber(rand io.Reader, max *big.Int) (n *big.Int, err os.Error) { - k := (max.BitLen() + 7) / 8 - - // r is the number of bits in the used in the most significant byte of - // max. - r := uint(max.BitLen() % 8) - if r == 0 { - r = 8 - } - - bytes := make([]byte, k) - n = new(big.Int) - - for { - _, err = io.ReadFull(rand, bytes) - if err != nil { - return - } - - // Clear bits in the first byte to increase the probability - // that the candidate is < max. - bytes[0] &= uint8(int(1<<r) - 1) - - n.SetBytes(bytes) - if n.Cmp(max) < 0 { - return - } - } - - return -} - // A PublicKey represents the public part of an RSA key. type PublicKey struct { N *big.Int // modulus @@ -162,8 +100,8 @@ 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) +func GenerateKey(random io.Reader, bits int) (priv *PrivateKey, err os.Error) { + return GenerateMultiPrimeKey(random, 2, bits) } // GenerateMultiPrimeKey generates a multi-prime RSA keypair of the given bit @@ -176,7 +114,7 @@ func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) { // // [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) { +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 @@ -198,7 +136,7 @@ NextSetOfPrimes: for { todo := bits for i := 0; i < nprimes; i++ { - primes[i], err = randomPrime(rand, todo/(nprimes-i)) + primes[i], err = rand.Prime(random, todo/(nprimes-i)) if err != nil { return nil, err } @@ -293,7 +231,7 @@ func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int { // EncryptOAEP encrypts the given message with RSA-OAEP. // The message must be no longer than the length of the public modulus less // twice the hash length plus 2. -func EncryptOAEP(hash hash.Hash, rand io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err os.Error) { +func EncryptOAEP(hash hash.Hash, random io.Reader, pub *PublicKey, msg []byte, label []byte) (out []byte, err os.Error) { hash.Reset() k := (pub.N.BitLen() + 7) / 8 if len(msg) > k-2*hash.Size()-2 { @@ -313,7 +251,7 @@ func EncryptOAEP(hash hash.Hash, rand io.Reader, pub *PublicKey, msg []byte, lab db[len(db)-len(msg)-1] = 1 copy(db[len(db)-len(msg):], msg) - _, err = io.ReadFull(rand, seed) + _, err = io.ReadFull(random, seed) if err != nil { return } @@ -405,7 +343,7 @@ func (priv *PrivateKey) Precompute() { // decrypt performs an RSA decryption, resulting in a plaintext integer. If a // random source is given, RSA blinding is used. -func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.Error) { +func decrypt(random io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.Error) { // TODO(agl): can we get away with reusing blinds? if c.Cmp(priv.N) > 0 { err = DecryptionError{} @@ -413,7 +351,7 @@ func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.E } var ir *big.Int - if rand != nil { + if random != nil { // Blinding enabled. Blinding involves multiplying c by r^e. // Then the decryption operation performs (m^e * r^e)^d mod n // which equals mr mod n. The factor of r can then be removed @@ -422,7 +360,7 @@ func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.E var r *big.Int for { - r, err = randomNumber(rand, priv.N) + r, err = rand.Int(random, priv.N) if err != nil { return } @@ -483,7 +421,7 @@ func decrypt(rand io.Reader, priv *PrivateKey, c *big.Int) (m *big.Int, err os.E // DecryptOAEP decrypts ciphertext using RSA-OAEP. // If rand != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks. -func DecryptOAEP(hash hash.Hash, rand io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err os.Error) { +func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err os.Error) { k := (priv.N.BitLen() + 7) / 8 if len(ciphertext) > k || k < hash.Size()*2+2 { @@ -493,7 +431,7 @@ func DecryptOAEP(hash hash.Hash, rand io.Reader, priv *PrivateKey, ciphertext [] c := new(big.Int).SetBytes(ciphertext) - m, err := decrypt(rand, priv, c) + m, err := decrypt(random, priv, c) if err != nil { return } |