elgamal.go

Documentation: golang.org/x/crypto/openpgp/elgamal

     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.
    19  package elgamal // import "golang.org/x/crypto/openpgp/elgamal"
    20  
    21  import (
    22  	"crypto/rand"
    23  	"crypto/subtle"
    24  	"errors"
    25  	"io"
    26  	"math/big"
    27  )
    28  
    29  // PublicKey represents an ElGamal public key.
    30  type PublicKey struct {
    31  	G, P, Y *big.Int
    32  }
    33  
    34  // PrivateKey represents an ElGamal private key.
    35  type 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.
    43  func 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),
    83  func 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.
   114  func 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
View as plain text