crypto/openpgp: add ElGamal support.

R=bradfitz, r
CC=golang-dev
https://golang.org/cl/4639049

6 files changed, 176 insertions, 37 deletions

diff --git a/src/pkg/crypto/openpgp/packet/encrypted_key.go b/src/pkg/crypto/openpgp/packet/encrypted_key.go
index 329493c08f..b4730cbc9b 100644
--- a/src/pkg/crypto/openpgp/packet/encrypted_key.go
+++ b/src/pkg/crypto/openpgp/packet/encrypted_key.go
@@ -5,6 +5,8 @@
 package packet
 
 import (
+	"big"
+	"crypto/openpgp/elgamal"
 	"crypto/openpgp/error"
 	"crypto/rand"
 	"crypto/rsa"
@@ -21,9 +23,10 @@ const encryptedKeyVersion = 3
 type EncryptedKey struct {
 	KeyId      uint64
 	Algo       PublicKeyAlgorithm
-	Encrypted  []byte
 	CipherFunc CipherFunction // only valid after a successful Decrypt
 	Key        []byte         // only valid after a successful Decrypt
+
+	encryptedMPI1, encryptedMPI2 []byte
 }
 
 func (e *EncryptedKey) parse(r io.Reader) (err os.Error) {
@@ -37,8 +40,15 @@ func (e *EncryptedKey) parse(r io.Reader) (err os.Error) {
 	}
 	e.KeyId = binary.BigEndian.Uint64(buf[1:9])
 	e.Algo = PublicKeyAlgorithm(buf[9])
-	if e.Algo == PubKeyAlgoRSA || e.Algo == PubKeyAlgoRSAEncryptOnly {
-		e.Encrypted, _, err = readMPI(r)
+	switch e.Algo {
+	case PubKeyAlgoRSA, PubKeyAlgoRSAEncryptOnly:
+		e.encryptedMPI1, _, err = readMPI(r)
+	case PubKeyAlgoElGamal:
+		e.encryptedMPI1, _, err = readMPI(r)
+		if err != nil {
+			return
+		}
+		e.encryptedMPI2, _, err = readMPI(r)
 	}
 	_, err = consumeAll(r)
 	return
@@ -52,15 +62,29 @@ func checksumKeyMaterial(key []byte) uint16 {
 	return checksum
 }
 
-// DecryptRSA decrypts an RSA encrypted session key with the given private key.
-func (e *EncryptedKey) DecryptRSA(priv *rsa.PrivateKey) (err os.Error) {
-	if e.Algo != PubKeyAlgoRSA && e.Algo != PubKeyAlgoRSAEncryptOnly {
-		return error.InvalidArgumentError("EncryptedKey not RSA encrypted")
+// Decrypt decrypts an encrypted session key with the given private key. The
+// private key must have been decrypted first.
+func (e *EncryptedKey) Decrypt(priv *PrivateKey) os.Error {
+	var err os.Error
+	var b []byte
+
+	// TODO(agl): use session key decryption routines here to avoid
+	// padding oracle attacks.
+	switch priv.PubKeyAlgo {
+	case PubKeyAlgoRSA, PubKeyAlgoRSAEncryptOnly:
+		b, err = rsa.DecryptPKCS1v15(rand.Reader, priv.PrivateKey.(*rsa.PrivateKey), e.encryptedMPI1)
+	case PubKeyAlgoElGamal:
+		c1 := new(big.Int).SetBytes(e.encryptedMPI1)
+		c2 := new(big.Int).SetBytes(e.encryptedMPI2)
+		b, err = elgamal.Decrypt(priv.PrivateKey.(*elgamal.PrivateKey), c1, c2)
+	default:
+		err = error.InvalidArgumentError("cannot decrypted encrypted session key with private key of type " + strconv.Itoa(int(priv.PubKeyAlgo)))
 	}
-	b, err := rsa.DecryptPKCS1v15(rand.Reader, priv, e.Encrypted)
+
 	if err != nil {
-		return
+		return err
 	}
+
 	e.CipherFunc = CipherFunction(b[0])
 	e.Key = b[1 : len(b)-2]
 	expectedChecksum := uint16(b[len(b)-2])<<8 | uint16(b[len(b)-1])
@@ -69,7 +93,7 @@ func (e *EncryptedKey) DecryptRSA(priv *rsa.PrivateKey) (err os.Error) {
 		return error.StructuralError("EncryptedKey checksum incorrect")
 	}
 
-	return
+	return nil
 }
 
 // SerializeEncryptedKey serializes an encrypted key packet to w that contains
@@ -90,6 +114,8 @@ func SerializeEncryptedKey(w io.Writer, rand io.Reader, pub *PublicKey, cipherFu
 	switch pub.PubKeyAlgo {
 	case PubKeyAlgoRSA, PubKeyAlgoRSAEncryptOnly:
 		return serializeEncryptedKeyRSA(w, rand, buf, pub.PublicKey.(*rsa.PublicKey), keyBlock)
+	case PubKeyAlgoElGamal:
+		return serializeEncryptedKeyElGamal(w, rand, buf, pub.PublicKey.(*elgamal.PublicKey), keyBlock)
 	case PubKeyAlgoDSA, PubKeyAlgoRSASignOnly:
 		return error.InvalidArgumentError("cannot encrypt to public key of type " + strconv.Itoa(int(pub.PubKeyAlgo)))
 	}
@@ -115,3 +141,28 @@ func serializeEncryptedKeyRSA(w io.Writer, rand io.Reader, header [10]byte, pub
 	}
 	return writeMPI(w, 8*uint16(len(cipherText)), cipherText)
 }
+
+func serializeEncryptedKeyElGamal(w io.Writer, rand io.Reader, header [10]byte, pub *elgamal.PublicKey, keyBlock []byte) os.Error {
+	c1, c2, err := elgamal.Encrypt(rand, pub, keyBlock)
+	if err != nil {
+		return error.InvalidArgumentError("ElGamal encryption failed: " + err.String())
+	}
+
+	packetLen := 10 /* header length */
+	packetLen += 2 /* mpi size */ + (c1.BitLen()+7)/8
+	packetLen += 2 /* mpi size */ + (c2.BitLen()+7)/8
+
+	err = serializeHeader(w, packetTypeEncryptedKey, packetLen)
+	if err != nil {
+		return err
+	}
+	_, err = w.Write(header[:])
+	if err != nil {
+		return err
+	}
+	err = writeBig(w, c1)
+	if err != nil {
+		return err
+	}
+	return writeBig(w, c2)
+}
diff --git a/src/pkg/crypto/openpgp/packet/encrypted_key_test.go b/src/pkg/crypto/openpgp/packet/encrypted_key_test.go
index d4e147c0ef..b0a14904a8 100644
--- a/src/pkg/crypto/openpgp/packet/encrypted_key_test.go
+++ b/src/pkg/crypto/openpgp/packet/encrypted_key_test.go
@@ -27,11 +27,18 @@ var encryptedKeyPub = rsa.PublicKey{
 	N: bigFromBase10("115804063926007623305902631768113868327816898845124614648849934718568541074358183759250136204762053879858102352159854352727097033322663029387610959884180306668628526686121021235757016368038585212410610742029286439607686208110250133174279811431933746643015923132833417396844716207301518956640020862630546868823"),
 }
 
-var encryptedKeyPriv = &rsa.PrivateKey{
+var encryptedKeyRSAPriv = &rsa.PrivateKey{
 	PublicKey: encryptedKeyPub,
 	D:         bigFromBase10("32355588668219869544751561565313228297765464314098552250409557267371233892496951383426602439009993875125222579159850054973310859166139474359774543943714622292329487391199285040721944491839695981199720170366763547754915493640685849961780092241140181198779299712578774460837139360803883139311171713302987058393"),
 }
 
+var encryptedKeyPriv = &PrivateKey{
+	PublicKey: PublicKey{
+		PubKeyAlgo: PubKeyAlgoRSA,
+	},
+	PrivateKey: encryptedKeyRSAPriv,
+}
+
 func TestDecryptingEncryptedKey(t *testing.T) {
 	const encryptedKeyHex = "c18c032a67d68660df41c70104005789d0de26b6a50c985a02a13131ca829c413a35d0e6fa8d6842599252162808ac7439c72151c8c6183e76923fe3299301414d0c25a2f06a2257db3839e7df0ec964773f6e4c4ac7ff3b48c444237166dd46ba8ff443a5410dc670cb486672fdbe7c9dfafb75b4fea83af3a204fe2a7dfa86bd20122b4f3d2646cbeecb8f7be8"
 	const expectedKeyHex = "d930363f7e0308c333b9618617ea728963d8df993665ae7be1092d4926fd864b"
@@ -52,9 +59,9 @@ func TestDecryptingEncryptedKey(t *testing.T) {
 		return
 	}
 
-	err = ek.DecryptRSA(encryptedKeyPriv)
+	err = ek.Decrypt(encryptedKeyPriv)
 	if err != nil {
-		t.Errorf("error from DecryptRSA: %s", err)
+		t.Errorf("error from Decrypt: %s", err)
 		return
 	}
 
@@ -102,9 +109,9 @@ func TestEncryptingEncryptedKey(t *testing.T) {
 		return
 	}
 
-	err = ek.DecryptRSA(encryptedKeyPriv)
+	err = ek.Decrypt(encryptedKeyPriv)
 	if err != nil {
-		t.Errorf("error from DecryptRSA: %s", err)
+		t.Errorf("error from Decrypt: %s", err)
 		return
 	}
 
diff --git a/src/pkg/crypto/openpgp/packet/packet.go b/src/pkg/crypto/openpgp/packet/packet.go
index 60bd067e90..1d7297e388 100644
--- a/src/pkg/crypto/openpgp/packet/packet.go
+++ b/src/pkg/crypto/openpgp/packet/packet.go
@@ -372,7 +372,7 @@ const (
 	PubKeyAlgoRSA            PublicKeyAlgorithm = 1
 	PubKeyAlgoRSAEncryptOnly PublicKeyAlgorithm = 2
 	PubKeyAlgoRSASignOnly    PublicKeyAlgorithm = 3
-	PubKeyAlgoElgamal        PublicKeyAlgorithm = 16
+	PubKeyAlgoElGamal        PublicKeyAlgorithm = 16
 	PubKeyAlgoDSA            PublicKeyAlgorithm = 17
 )
 
@@ -380,7 +380,7 @@ const (
 // key of the given type.
 func (pka PublicKeyAlgorithm) CanEncrypt() bool {
 	switch pka {
-	case PubKeyAlgoRSA, PubKeyAlgoRSAEncryptOnly, PubKeyAlgoElgamal:
+	case PubKeyAlgoRSA, PubKeyAlgoRSAEncryptOnly, PubKeyAlgoElGamal:
 		return true
 	}
 	return false
diff --git a/src/pkg/crypto/openpgp/packet/private_key.go b/src/pkg/crypto/openpgp/packet/private_key.go
index 6244661320..6f8133d981 100644
--- a/src/pkg/crypto/openpgp/packet/private_key.go
+++ b/src/pkg/crypto/openpgp/packet/private_key.go
@@ -9,6 +9,7 @@ import (
 	"bytes"
 	"crypto/cipher"
 	"crypto/dsa"
+	"crypto/openpgp/elgamal"
 	"crypto/openpgp/error"
 	"crypto/openpgp/s2k"
 	"crypto/rsa"
@@ -224,6 +225,8 @@ func (pk *PrivateKey) parsePrivateKey(data []byte) (err os.Error) {
 		return pk.parseRSAPrivateKey(data)
 	case PubKeyAlgoDSA:
 		return pk.parseDSAPrivateKey(data)
+	case PubKeyAlgoElGamal:
+		return pk.parseElGamalPrivateKey(data)
 	}
 	panic("impossible")
 }
@@ -277,3 +280,22 @@ func (pk *PrivateKey) parseDSAPrivateKey(data []byte) (err os.Error) {
 
 	return nil
 }
+
+func (pk *PrivateKey) parseElGamalPrivateKey(data []byte) (err os.Error) {
+	pub := pk.PublicKey.PublicKey.(*elgamal.PublicKey)
+	priv := new(elgamal.PrivateKey)
+	priv.PublicKey = *pub
+
+	buf := bytes.NewBuffer(data)
+	x, _, err := readMPI(buf)
+	if err != nil {
+		return
+	}
+
+	priv.X = new(big.Int).SetBytes(x)
+	pk.PrivateKey = priv
+	pk.Encrypted = false
+	pk.encryptedData = nil
+
+	return nil
+}
diff --git a/src/pkg/crypto/openpgp/packet/private_key_test.go b/src/pkg/crypto/openpgp/packet/private_key_test.go
index e941cc735c..60eebaa6b0 100644
--- a/src/pkg/crypto/openpgp/packet/private_key_test.go
+++ b/src/pkg/crypto/openpgp/packet/private_key_test.go
@@ -8,30 +8,50 @@ import (
 	"testing"
 )
 
+var privateKeyTests = []struct {
+	privateKeyHex string
+	creationTime  uint32
+}{
+	{
+		privKeyRSAHex,
+		0x4cc349a8,
+	},
+	{
+		privKeyElGamalHex,
+		0x4df9ee1a,
+	},
+}
+
 func TestPrivateKeyRead(t *testing.T) {
-	packet, err := Read(readerFromHex(privKeyHex))
-	if err != nil {
-		t.Error(err)
-		return
-	}
+	for i, test := range privateKeyTests {
+		packet, err := Read(readerFromHex(test.privateKeyHex))
+		if err != nil {
+			t.Errorf("#%d: failed to parse: %s", i, err)
+			continue
+		}
 
-	privKey := packet.(*PrivateKey)
+		privKey := packet.(*PrivateKey)
 
-	if !privKey.Encrypted {
-		t.Error("private key isn't encrypted")
-		return
-	}
+		if !privKey.Encrypted {
+			t.Errorf("#%d: private key isn't encrypted", i)
+			continue
+		}
 
-	err = privKey.Decrypt([]byte("testing"))
-	if err != nil {
-		t.Error(err)
-		return
-	}
+		err = privKey.Decrypt([]byte("testing"))
+		if err != nil {
+			t.Errorf("#%d: failed to decrypt: %s", i, err)
+			continue
+		}
 
-	if privKey.CreationTime != 0x4cc349a8 || privKey.Encrypted {
-		t.Errorf("failed to parse, got: %#v", privKey)
+		if privKey.CreationTime != test.creationTime || privKey.Encrypted {
+			t.Errorf("#%d: bad result, got: %#v", i, privKey)
+		}
 	}
 }
 
 // Generated with `gpg --export-secret-keys "Test Key 2"`
-const privKeyHex = "9501fe044cc349a8010400b70ca0010e98c090008d45d1ee8f9113bd5861fd57b88bacb7c68658747663f1e1a3b5a98f32fda6472373c024b97359cd2efc88ff60f77751adfbf6af5e615e6a1408cfad8bf0cea30b0d5f53aa27ad59089ba9b15b7ebc2777a25d7b436144027e3bcd203909f147d0e332b240cf63d3395f5dfe0df0a6c04e8655af7eacdf0011010001fe0303024a252e7d475fd445607de39a265472aa74a9320ba2dac395faa687e9e0336aeb7e9a7397e511b5afd9dc84557c80ac0f3d4d7bfec5ae16f20d41c8c84a04552a33870b930420e230e179564f6d19bb153145e76c33ae993886c388832b0fa042ddda7f133924f3854481533e0ede31d51278c0519b29abc3bf53da673e13e3e1214b52413d179d7f66deee35cac8eacb060f78379d70ef4af8607e68131ff529439668fc39c9ce6dfef8a5ac234d234802cbfb749a26107db26406213ae5c06d4673253a3cbee1fcbae58d6ab77e38d6e2c0e7c6317c48e054edadb5a40d0d48acb44643d998139a8a66bb820be1f3f80185bc777d14b5954b60effe2448a036d565c6bc0b915fcea518acdd20ab07bc1529f561c58cd044f723109b93f6fd99f876ff891d64306b5d08f48bab59f38695e9109c4dec34013ba3153488ce070268381ba923ee1eb77125b36afcb4347ec3478c8f2735b06ef17351d872e577fa95d0c397c88c71b59629a36aec"
+const privKeyRSAHex = "9501fe044cc349a8010400b70ca0010e98c090008d45d1ee8f9113bd5861fd57b88bacb7c68658747663f1e1a3b5a98f32fda6472373c024b97359cd2efc88ff60f77751adfbf6af5e615e6a1408cfad8bf0cea30b0d5f53aa27ad59089ba9b15b7ebc2777a25d7b436144027e3bcd203909f147d0e332b240cf63d3395f5dfe0df0a6c04e8655af7eacdf0011010001fe0303024a252e7d475fd445607de39a265472aa74a9320ba2dac395faa687e9e0336aeb7e9a7397e511b5afd9dc84557c80ac0f3d4d7bfec5ae16f20d41c8c84a04552a33870b930420e230e179564f6d19bb153145e76c33ae993886c388832b0fa042ddda7f133924f3854481533e0ede31d51278c0519b29abc3bf53da673e13e3e1214b52413d179d7f66deee35cac8eacb060f78379d70ef4af8607e68131ff529439668fc39c9ce6dfef8a5ac234d234802cbfb749a26107db26406213ae5c06d4673253a3cbee1fcbae58d6ab77e38d6e2c0e7c6317c48e054edadb5a40d0d48acb44643d998139a8a66bb820be1f3f80185bc777d14b5954b60effe2448a036d565c6bc0b915fcea518acdd20ab07bc1529f561c58cd044f723109b93f6fd99f876ff891d64306b5d08f48bab59f38695e9109c4dec34013ba3153488ce070268381ba923ee1eb77125b36afcb4347ec3478c8f2735b06ef17351d872e577fa95d0c397c88c71b59629a36aec"
+
+// Generated by `gpg --export-secret-keys` followed by a manual extraction of
+// the ElGamal subkey from the packets.
+const privKeyElGamalHex = "9d0157044df9ee1a100400eb8e136a58ec39b582629cdadf830bc64e0a94ed8103ca8bb247b27b11b46d1d25297ef4bcc3071785ba0c0bedfe89eabc5287fcc0edf81ab5896c1c8e4b20d27d79813c7aede75320b33eaeeaa586edc00fd1036c10133e6ba0ff277245d0d59d04b2b3421b7244aca5f4a8d870c6f1c1fbff9e1c26699a860b9504f35ca1d700030503fd1ededd3b840795be6d9ccbe3c51ee42e2f39233c432b831ddd9c4e72b7025a819317e47bf94f9ee316d7273b05d5fcf2999c3a681f519b1234bbfa6d359b4752bd9c3f77d6b6456cde152464763414ca130f4e91d91041432f90620fec0e6d6b5116076c2985d5aeaae13be492b9b329efcaf7ee25120159a0a30cd976b42d7afe030302dae7eb80db744d4960c4df930d57e87fe81412eaace9f900e6c839817a614ddb75ba6603b9417c33ea7b6c93967dfa2bcff3fa3c74a5ce2c962db65b03aece14c96cbd0038fc"
diff --git a/src/pkg/crypto/openpgp/packet/public_key.go b/src/pkg/crypto/openpgp/packet/public_key.go
index 46d365b2a9..ba4d481f0f 100644
--- a/src/pkg/crypto/openpgp/packet/public_key.go
+++ b/src/pkg/crypto/openpgp/packet/public_key.go
@@ -7,6 +7,7 @@ package packet
 import (
 	"big"
 	"crypto/dsa"
+	"crypto/openpgp/elgamal"
 	"crypto/openpgp/error"
 	"crypto/rsa"
 	"crypto/sha1"
@@ -69,6 +70,8 @@ func (pk *PublicKey) parse(r io.Reader) (err os.Error) {
 		err = pk.parseRSA(r)
 	case PubKeyAlgoDSA:
 		err = pk.parseDSA(r)
+	case PubKeyAlgoElGamal:
+		err = pk.parseElGamal(r)
 	default:
 		err = error.UnsupportedError("public key type: " + strconv.Itoa(int(pk.PubKeyAlgo)))
 	}
@@ -117,7 +120,7 @@ func (pk *PublicKey) parseRSA(r io.Reader) (err os.Error) {
 	return
 }
 
-// parseRSA parses DSA public key material from the given Reader. See RFC 4880,
+// parseDSA parses DSA public key material from the given Reader. See RFC 4880,
 // section 5.5.2.
 func (pk *PublicKey) parseDSA(r io.Reader) (err os.Error) {
 	pk.p.bytes, pk.p.bitLength, err = readMPI(r)
@@ -146,6 +149,30 @@ func (pk *PublicKey) parseDSA(r io.Reader) (err os.Error) {
 	return
 }
 
+// parseElGamal parses ElGamal public key material from the given Reader. See
+// RFC 4880, section 5.5.2.
+func (pk *PublicKey) parseElGamal(r io.Reader) (err os.Error) {
+	pk.p.bytes, pk.p.bitLength, err = readMPI(r)
+	if err != nil {
+		return
+	}
+	pk.g.bytes, pk.g.bitLength, err = readMPI(r)
+	if err != nil {
+		return
+	}
+	pk.y.bytes, pk.y.bitLength, err = readMPI(r)
+	if err != nil {
+		return
+	}
+
+	elgamal := new(elgamal.PublicKey)
+	elgamal.P = new(big.Int).SetBytes(pk.p.bytes)
+	elgamal.G = new(big.Int).SetBytes(pk.g.bytes)
+	elgamal.Y = new(big.Int).SetBytes(pk.y.bytes)
+	pk.PublicKey = elgamal
+	return
+}
+
 // SerializeSignaturePrefix writes the prefix for this public key to the given Writer.
 // The prefix is used when calculating a signature over this public key. See
 // RFC 4880, section 5.2.4.
@@ -160,6 +187,10 @@ func (pk *PublicKey) SerializeSignaturePrefix(h hash.Hash) {
 		pLength += 2 + uint16(len(pk.q.bytes))
 		pLength += 2 + uint16(len(pk.g.bytes))
 		pLength += 2 + uint16(len(pk.y.bytes))
+	case PubKeyAlgoElGamal:
+		pLength += 2 + uint16(len(pk.p.bytes))
+		pLength += 2 + uint16(len(pk.g.bytes))
+		pLength += 2 + uint16(len(pk.y.bytes))
 	default:
 		panic("unknown public key algorithm")
 	}
@@ -180,6 +211,12 @@ func (pk *PublicKey) Serialize(w io.Writer) (err os.Error) {
 		length += 2 + len(pk.q.bytes)
 		length += 2 + len(pk.g.bytes)
 		length += 2 + len(pk.y.bytes)
+	case PubKeyAlgoElGamal:
+		length += 2 + len(pk.p.bytes)
+		length += 2 + len(pk.g.bytes)
+		length += 2 + len(pk.y.bytes)
+	default:
+		panic("unknown public key algorithm")
 	}
 
 	err = serializeHeader(w, packetTypePublicKey, length)
@@ -210,13 +247,15 @@ func (pk *PublicKey) serializeWithoutHeaders(w io.Writer) (err os.Error) {
 		return writeMPIs(w, pk.n, pk.e)
 	case PubKeyAlgoDSA:
 		return writeMPIs(w, pk.p, pk.q, pk.g, pk.y)
+	case PubKeyAlgoElGamal:
+		return writeMPIs(w, pk.p, pk.g, pk.y)
 	}
 	return error.InvalidArgumentError("bad public-key algorithm")
 }
 
 // CanSign returns true iff this public key can generate signatures
 func (pk *PublicKey) CanSign() bool {
-	return pk.PubKeyAlgo != PubKeyAlgoRSAEncryptOnly && pk.PubKeyAlgo != PubKeyAlgoElgamal
+	return pk.PubKeyAlgo != PubKeyAlgoRSAEncryptOnly && pk.PubKeyAlgo != PubKeyAlgoElGamal
 }
 
 // VerifySignature returns nil iff sig is a valid signature, made by this