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