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.
13//
14// Deprecated: this package was only provided to support ElGamal encryption in
15// OpenPGP. The golang.org/x/crypto/openpgp package is now deprecated (see
16// https://golang.org/issue/44226), and ElGamal in the OpenPGP ecosystem has
17// compatibility and security issues (see https://eprint.iacr.org/2021/923).
18// Moreover, this package doesn't protect against side-channel attacks.
19package elgamal // import "golang.org/x/crypto/openpgp/elgamal"
20
21import (
22	"crypto/rand"
23	"crypto/subtle"
24	"errors"
25	"io"
26	"math/big"
27)
28
29// PublicKey represents an ElGamal public key.
30type PublicKey struct {
31	G, P, Y *big.Int
32}
33
34// PrivateKey represents an ElGamal private key.
35type PrivateKey struct {
36	PublicKey
37	X *big.Int
38}
39
40// Encrypt encrypts the given message to the given public key. The result is a
41// pair of integers. Errors can result from reading random, or because msg is
42// too large to be encrypted to the public key.
43func Encrypt(random io.Reader, pub *PublicKey, msg []byte) (c1, c2 *big.Int, err error) {
44	pLen := (pub.P.BitLen() + 7) / 8
45	if len(msg) > pLen-11 {
46		err = errors.New("elgamal: message too long")
47		return
48	}
49
50	// EM = 0x02 || PS || 0x00 || M
51	em := make([]byte, pLen-1)
52	em[0] = 2
53	ps, mm := em[1:len(em)-len(msg)-1], em[len(em)-len(msg):]
54	err = nonZeroRandomBytes(ps, random)
55	if err != nil {
56		return
57	}
58	em[len(em)-len(msg)-1] = 0
59	copy(mm, msg)
60
61	m := new(big.Int).SetBytes(em)
62
63	k, err := rand.Int(random, pub.P)
64	if err != nil {
65		return
66	}
67
68	c1 = new(big.Int).Exp(pub.G, k, pub.P)
69	s := new(big.Int).Exp(pub.Y, k, pub.P)
70	c2 = s.Mul(s, m)
71	c2.Mod(c2, pub.P)
72
73	return
74}
75
76// Decrypt takes two integers, resulting from an ElGamal encryption, and
77// returns the plaintext of the message. An error can result only if the
78// ciphertext is invalid. Users should keep in mind that this is a padding
79// oracle and thus, if exposed to an adaptive chosen ciphertext attack, can
80// be used to break the cryptosystem.  See ``Chosen Ciphertext Attacks
81// Against Protocols Based on the RSA Encryption Standard PKCS #1'', Daniel
82// Bleichenbacher, Advances in Cryptology (Crypto '98),
83func Decrypt(priv *PrivateKey, c1, c2 *big.Int) (msg []byte, err error) {
84	s := new(big.Int).Exp(c1, priv.X, priv.P)
85	if s.ModInverse(s, priv.P) == nil {
86		return nil, errors.New("elgamal: invalid private key")
87	}
88	s.Mul(s, c2)
89	s.Mod(s, priv.P)
90	em := s.Bytes()
91
92	firstByteIsTwo := subtle.ConstantTimeByteEq(em[0], 2)
93
94	// The remainder of the plaintext must be a string of non-zero random
95	// octets, followed by a 0, followed by the message.
96	//   lookingForIndex: 1 iff we are still looking for the zero.
97	//   index: the offset of the first zero byte.
98	var lookingForIndex, index int
99	lookingForIndex = 1
100
101	for i := 1; i < len(em); i++ {
102		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
103		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
104		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
105	}
106
107	if firstByteIsTwo != 1 || lookingForIndex != 0 || index < 9 {
108		return nil, errors.New("elgamal: decryption error")
109	}
110	return em[index+1:], nil
111}
112
113// nonZeroRandomBytes fills the given slice with non-zero random octets.
114func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
115	_, err = io.ReadFull(rand, s)
116	if err != nil {
117		return
118	}
119
120	for i := 0; i < len(s); i++ {
121		for s[i] == 0 {
122			_, err = io.ReadFull(rand, s[i:i+1])
123			if err != nil {
124				return
125			}
126		}
127	}
128
129	return
130}
131