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.go298
1 files changed, 149 insertions, 149 deletions
diff --git a/src/pkg/crypto/rsa/rsa.go b/src/pkg/crypto/rsa/rsa.go
index e47b02060..a4a3cfd38 100644
--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -8,11 +8,11 @@ package rsa
// TODO(agl): Add support for PSS padding.
import (
- "big";
- "crypto/subtle";
- "hash";
- "io";
- "os";
+ "big"
+ "crypto/subtle"
+ "hash"
+ "io"
+ "os"
)
var bigZero = big.NewInt(0)
@@ -25,77 +25,77 @@ func randomSafePrime(rand io.Reader, bits int) (p *big.Int, err os.Error) {
err = os.EINVAL
}
- bytes := make([]byte, (bits+7)/8);
- p = new(big.Int);
- p2 := new(big.Int);
+ bytes := make([]byte, (bits+7)/8)
+ p = new(big.Int)
+ p2 := new(big.Int)
for {
- _, err = io.ReadFull(rand, bytes);
+ _, err = io.ReadFull(rand, bytes)
if err != nil {
return
}
// Don't let the value be too small.
- bytes[0] |= 0x80;
+ bytes[0] |= 0x80
// Make the value odd since an even number this large certainly isn't prime.
- bytes[len(bytes)-1] |= 1;
+ bytes[len(bytes)-1] |= 1
- p.SetBytes(bytes);
+ p.SetBytes(bytes)
if big.ProbablyPrime(p, 20) {
- p2.Rsh(p, 1); // p2 = (p - 1)/2
+ p2.Rsh(p, 1) // p2 = (p - 1)/2
if big.ProbablyPrime(p2, 20) {
return
}
}
}
- 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.Len() + 7) / 8;
+ k := (max.Len() + 7) / 8
// r is the number of bits in the used in the most significant byte of
// max.
- r := uint(max.Len() % 8);
+ r := uint(max.Len() % 8)
if r == 0 {
r = 8
}
- bytes := make([]byte, k);
- n = new(big.Int);
+ bytes := make([]byte, k)
+ n = new(big.Int)
for {
- _, err = io.ReadFull(rand, bytes);
+ _, 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);
+ bytes[0] &= uint8(int(1<<r) - 1)
- n.SetBytes(bytes);
+ n.SetBytes(bytes)
if n.Cmp(max) < 0 {
return
}
}
- return;
+ return
}
// A PublicKey represents the public part of an RSA key.
type PublicKey struct {
- N *big.Int; // modulus
- E int; // public exponent
+ N *big.Int // modulus
+ E int // public exponent
}
// A PrivateKey represents an RSA key
type PrivateKey struct {
- PublicKey; // public part.
- D *big.Int; // private exponent
- P, Q *big.Int; // prime factors of N
+ PublicKey // public part.
+ D *big.Int // private exponent
+ P, Q *big.Int // prime factors of N
}
// Validate performs basic sanity checks on the key.
@@ -114,34 +114,34 @@ func (priv PrivateKey) Validate() os.Error {
}
// Check that p*q == n.
- modulus := new(big.Int).Mul(priv.P, priv.Q);
+ modulus := new(big.Int).Mul(priv.P, priv.Q)
if modulus.Cmp(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);
+ 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 gcd.Cmp(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);
+ 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;
+ return nil
}
// 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);
+ 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
@@ -150,19 +150,19 @@ func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
// 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;
+ priv.E = 3
- pminus1 := new(big.Int);
- qminus1 := new(big.Int);
- totient := new(big.Int);
+ pminus1 := new(big.Int)
+ qminus1 := new(big.Int)
+ totient := new(big.Int)
for {
- p, err := randomSafePrime(rand, bits/2);
+ p, err := randomSafePrime(rand, bits/2)
if err != nil {
return nil, err
}
- q, err := randomSafePrime(rand, bits/2);
+ q, err := randomSafePrime(rand, bits/2)
if err != nil {
return nil, err
}
@@ -171,28 +171,28 @@ func GenerateKey(rand io.Reader, bits int) (priv *PrivateKey, err os.Error) {
continue
}
- n := new(big.Int).Mul(p, q);
- pminus1.Sub(p, bigOne);
- qminus1.Sub(q, bigOne);
- totient.Mul(pminus1, qminus1);
+ 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);
+ 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;
+ priv.D.Add(priv.D, totient)
+ priv.P = p
+ priv.Q = q
+ priv.N = n
- break;
+ break
}
}
- return;
+ return
}
// incCounter increments a four byte, big-endian counter.
@@ -206,26 +206,26 @@ func incCounter(c *[4]byte) {
if c[1]++; c[1] != 0 {
return
}
- c[0]++;
+ c[0]++
}
// mgf1XOR XORs the bytes in out with a mask generated using the MGF1 function
// specified in PKCS#1 v2.1.
func mgf1XOR(out []byte, hash hash.Hash, seed []byte) {
- var counter [4]byte;
+ var counter [4]byte
- done := 0;
+ done := 0
for done < len(out) {
- hash.Write(seed);
- hash.Write(counter[0:4]);
- digest := hash.Sum();
- hash.Reset();
+ hash.Write(seed)
+ hash.Write(counter[0:4])
+ digest := hash.Sum()
+ hash.Reset()
for i := 0; i < len(digest) && done < len(out); i++ {
- out[done] ^= digest[i];
- done++;
+ out[done] ^= digest[i]
+ done++
}
- incCounter(&counter);
+ incCounter(&counter)
}
}
@@ -238,68 +238,68 @@ func (MessageTooLongError) String() string {
}
func encrypt(c *big.Int, pub *PublicKey, m *big.Int) *big.Int {
- e := big.NewInt(int64(pub.E));
- c.Exp(m, e, pub.N);
- return c;
+ e := big.NewInt(int64(pub.E))
+ c.Exp(m, e, pub.N)
+ return c
}
// 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) {
- hash.Reset();
- k := (pub.N.Len() + 7) / 8;
+ hash.Reset()
+ k := (pub.N.Len() + 7) / 8
if len(msg) > k-2*hash.Size()-2 {
- err = MessageTooLongError{};
- return;
+ err = MessageTooLongError{}
+ return
}
- hash.Write(label);
- lHash := hash.Sum();
- hash.Reset();
+ hash.Write(label)
+ lHash := hash.Sum()
+ hash.Reset()
- em := make([]byte, k);
- seed := em[1 : 1+hash.Size()];
- db := em[1+hash.Size():];
+ em := make([]byte, k)
+ seed := em[1 : 1+hash.Size()]
+ db := em[1+hash.Size():]
- copy(db[0:hash.Size()], lHash);
- db[len(db)-len(msg)-1] = 1;
- copy(db[len(db)-len(msg):], msg);
+ copy(db[0:hash.Size()], lHash)
+ db[len(db)-len(msg)-1] = 1
+ copy(db[len(db)-len(msg):], msg)
- _, err = io.ReadFull(rand, seed);
+ _, err = io.ReadFull(rand, seed)
if err != nil {
return
}
- mgf1XOR(db, hash, seed);
- mgf1XOR(seed, hash, db);
+ mgf1XOR(db, hash, seed)
+ mgf1XOR(seed, hash, db)
- m := new(big.Int);
- m.SetBytes(em);
- c := encrypt(new(big.Int), pub, m);
- out = c.Bytes();
- return;
+ m := new(big.Int)
+ m.SetBytes(em)
+ c := encrypt(new(big.Int), pub, m)
+ out = c.Bytes()
+ return
}
// A DecryptionError represents a failure to decrypt a message.
// It is deliberately vague to avoid adaptive attacks.
type DecryptionError struct{}
-func (DecryptionError) String() string { return "RSA decryption error" }
+func (DecryptionError) String() string { return "RSA decryption error" }
// A VerificationError represents a failure to verify a signature.
// It is deliberately vague to avoid adaptive attacks.
type VerificationError struct{}
-func (VerificationError) String() string { return "RSA verification error" }
+func (VerificationError) String() string { return "RSA verification error" }
// 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);
+ 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
@@ -314,7 +314,7 @@ func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
x.Add(x, n)
}
- return x, true;
+ return x, true
}
// decrypt performs an RSA decryption, resulting in a plaintext integer. If a
@@ -322,128 +322,128 @@ func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
func decrypt(rand 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{};
- return;
+ err = DecryptionError{}
+ return
}
- var ir *big.Int;
+ var ir *big.Int
if rand != 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
// by multipling by the multiplicative inverse of r.
- var r *big.Int;
+ var r *big.Int
for {
- r, err = randomNumber(rand, priv.N);
+ r, err = randomNumber(rand, priv.N)
if err != nil {
return
}
if r.Cmp(bigZero) == 0 {
r = bigOne
}
- var ok bool;
- ir, ok = modInverse(r, priv.N);
+ var ok bool
+ ir, ok = modInverse(r, priv.N)
if ok {
break
}
}
- bigE := big.NewInt(int64(priv.E));
- rpowe := new(big.Int).Exp(r, bigE, priv.N);
- c.Mul(c, rpowe);
- c.Mod(c, priv.N);
+ bigE := big.NewInt(int64(priv.E))
+ rpowe := new(big.Int).Exp(r, bigE, priv.N)
+ c.Mul(c, rpowe)
+ c.Mod(c, priv.N)
}
- m = new(big.Int).Exp(c, priv.D, priv.N);
+ m = new(big.Int).Exp(c, priv.D, priv.N)
if ir != nil {
// Unblind.
- m.Mul(m, ir);
- m.Mod(m, priv.N);
+ m.Mul(m, ir)
+ m.Mod(m, priv.N)
}
- return;
+ return
}
// 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) {
- k := (priv.N.Len() + 7) / 8;
+ k := (priv.N.Len() + 7) / 8
if len(ciphertext) > k ||
k < hash.Size()*2+2 {
- err = DecryptionError{};
- return;
+ err = DecryptionError{}
+ return
}
- c := new(big.Int).SetBytes(ciphertext);
+ c := new(big.Int).SetBytes(ciphertext)
- m, err := decrypt(rand, priv, c);
+ m, err := decrypt(rand, priv, c)
if err != nil {
return
}
- hash.Write(label);
- lHash := hash.Sum();
- hash.Reset();
+ hash.Write(label)
+ lHash := hash.Sum()
+ hash.Reset()
// Converting the plaintext number to bytes will strip any
// leading zeros so we may have to left pad. We do this unconditionally
// to avoid leaking timing information. (Although we still probably
// leak the number of leading zeros. It's not clear that we can do
// anything about this.)
- em := leftPad(m.Bytes(), k);
+ em := leftPad(m.Bytes(), k)
- firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0);
+ firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
- seed := em[1 : hash.Size()+1];
- db := em[hash.Size()+1:];
+ seed := em[1 : hash.Size()+1]
+ db := em[hash.Size()+1:]
- mgf1XOR(seed, hash, db);
- mgf1XOR(db, hash, seed);
+ mgf1XOR(seed, hash, db)
+ mgf1XOR(db, hash, seed)
- lHash2 := db[0:hash.Size()];
+ lHash2 := db[0:hash.Size()]
// We have to validate the plaintext in contanst time in order to avoid
// attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
// Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
// v2.0. In J. Kilian, editor, Advances in Cryptology.
- lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2);
+ lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)
// The remainder of the plaintext must be zero or more 0x00, followed
// by 0x01, followed by the message.
// lookingForIndex: 1 iff we are still looking for the 0x01
// index: the offset of the first 0x01 byte
// invalid: 1 iff we saw a non-zero byte before the 0x01.
- var lookingForIndex, index, invalid int;
- lookingForIndex = 1;
- rest := db[hash.Size():];
+ var lookingForIndex, index, invalid int
+ lookingForIndex = 1
+ rest := db[hash.Size():]
for i := 0; i < len(rest); i++ {
- equals0 := subtle.ConstantTimeByteEq(rest[i], 0);
- equals1 := subtle.ConstantTimeByteEq(rest[i], 1);
- index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index);
- lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex);
- invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid);
+ equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
+ equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
+ index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
+ lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
+ invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
}
if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
- err = DecryptionError{};
- return;
+ err = DecryptionError{}
+ return
}
- msg = rest[index+1:];
- return;
+ msg = rest[index+1:]
+ return
}
// leftPad returns a new slice of length size. The contents of input are right
// aligned in the new slice.
func leftPad(input []byte, size int) (out []byte) {
- n := len(input);
+ n := len(input)
if n > size {
n = size
}
- out = make([]byte, size);
- copy(out[len(out)-n:], input);
- return;
+ out = make([]byte, size)
+ copy(out[len(out)-n:], input)
+ return
}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-12 15:33:21 +0000