1// Copyright 2011 The Go Authors. All rights reserved.
  2// Use of this source code is governed by a BSD-style
  3// license that can be found in the LICENSE file.
  4
  5// Package elgamal implements ElGamal encryption, suitable for OpenPGP,
  6// as specified in "A Public-Key Cryptosystem and a Signature Scheme Based on
  7// Discrete Logarithms," IEEE Transactions on Information Theory, v. IT-31,
  8// n. 4, 1985, pp. 469-472.
  9//
 10// This form of ElGamal embeds PKCS#1 v1.5 padding, which may make it
 11// unsuitable for other protocols. RSA should be used in preference in any
 12// case.
 13package elgamal // import "github.com/ProtonMail/go-crypto/openpgp/elgamal"
 14
 15import (
 16	"crypto/rand"
 17	"crypto/subtle"
 18	"errors"
 19	"io"
 20	"math/big"
 21)
 22
 23// PublicKey represents an ElGamal public key.
 24type PublicKey struct {
 25	G, P, Y *big.Int
 26}
 27
 28// PrivateKey represents an ElGamal private key.
 29type PrivateKey struct {
 30	PublicKey
 31	X *big.Int
 32}
 33
 34// Encrypt encrypts the given message to the given public key. The result is a
 35// pair of integers. Errors can result from reading random, or because msg is
 36// too large to be encrypted to the public key.
 37func Encrypt(random io.Reader, pub *PublicKey, msg []byte) (c1, c2 *big.Int, err error) {
 38	pLen := (pub.P.BitLen() + 7) / 8
 39	if len(msg) > pLen-11 {
 40		err = errors.New("elgamal: message too long")
 41		return
 42	}
 43
 44	// EM = 0x02 || PS || 0x00 || M
 45	em := make([]byte, pLen-1)
 46	em[0] = 2
 47	ps, mm := em[1:len(em)-len(msg)-1], em[len(em)-len(msg):]
 48	err = nonZeroRandomBytes(ps, random)
 49	if err != nil {
 50		return
 51	}
 52	em[len(em)-len(msg)-1] = 0
 53	copy(mm, msg)
 54
 55	m := new(big.Int).SetBytes(em)
 56
 57	k, err := rand.Int(random, pub.P)
 58	if err != nil {
 59		return
 60	}
 61
 62	c1 = new(big.Int).Exp(pub.G, k, pub.P)
 63	s := new(big.Int).Exp(pub.Y, k, pub.P)
 64	c2 = s.Mul(s, m)
 65	c2.Mod(c2, pub.P)
 66
 67	return
 68}
 69
 70// Decrypt takes two integers, resulting from an ElGamal encryption, and
 71// returns the plaintext of the message. An error can result only if the
 72// ciphertext is invalid. Users should keep in mind that this is a padding
 73// oracle and thus, if exposed to an adaptive chosen ciphertext attack, can
 74// be used to break the cryptosystem.  See “Chosen Ciphertext Attacks
 75// Against Protocols Based on the RSA Encryption Standard PKCS #1”, Daniel
 76// Bleichenbacher, Advances in Cryptology (Crypto '98),
 77func Decrypt(priv *PrivateKey, c1, c2 *big.Int) (msg []byte, err error) {
 78	s := new(big.Int).Exp(c1, priv.X, priv.P)
 79	if s.ModInverse(s, priv.P) == nil {
 80		return nil, errors.New("elgamal: invalid private key")
 81	}
 82	s.Mul(s, c2)
 83	s.Mod(s, priv.P)
 84	em := s.Bytes()
 85
 86	firstByteIsTwo := subtle.ConstantTimeByteEq(em[0], 2)
 87
 88	// The remainder of the plaintext must be a string of non-zero random
 89	// octets, followed by a 0, followed by the message.
 90	//   lookingForIndex: 1 iff we are still looking for the zero.
 91	//   index: the offset of the first zero byte.
 92	var lookingForIndex, index int
 93	lookingForIndex = 1
 94
 95	for i := 1; i < len(em); i++ {
 96		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
 97		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
 98		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
 99	}
100
101	if firstByteIsTwo != 1 || lookingForIndex != 0 || index < 9 {
102		return nil, errors.New("elgamal: decryption error")
103	}
104	return em[index+1:], nil
105}
106
107// nonZeroRandomBytes fills the given slice with non-zero random octets.
108func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
109	_, err = io.ReadFull(rand, s)
110	if err != nil {
111		return
112	}
113
114	for i := 0; i < len(s); i++ {
115		for s[i] == 0 {
116			_, err = io.ReadFull(rand, s[i:i+1])
117			if err != nil {
118				return
119			}
120		}
121	}
122
123	return
124}