vendor/golang.org/x/crypto/openpgp/elgamal/elgamal.go

   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 package elgamal // import "golang.org/x/crypto/openpgp/elgamal"
  14
  15 import (
  16         "crypto/rand"
  17         "crypto/subtle"
  18         "errors"
  19         "io"
  20         "math/big"
  21 )
  22
  23 // PublicKey represents an ElGamal public key.
  24 type PublicKey struct {
  25         G, P, Y *big.Int
  26 }
  27
  28 // PrivateKey represents an ElGamal private key.
  29 type 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.
  37 func 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),
  77 func Decrypt(priv *PrivateKey, c1, c2 *big.Int) (msg []byte, err error) {
  78         s := new(big.Int).Exp(c1, priv.X, priv.P)
  79         s.ModInverse(s, priv.P)
  80         s.Mul(s, c2)
  81         s.Mod(s, priv.P)
  82         em := s.Bytes()
  83
  84         firstByteIsTwo := subtle.ConstantTimeByteEq(em[0], 2)
  85
  86         // The remainder of the plaintext must be a string of non-zero random
  87         // octets, followed by a 0, followed by the message.
  88         //   lookingForIndex: 1 iff we are still looking for the zero.
  89         //   index: the offset of the first zero byte.
  90         var lookingForIndex, index int
  91         lookingForIndex = 1
  92
  93         for i := 1; i < len(em); i++ {
  94                 equals0 := subtle.ConstantTimeByteEq(em[i], 0)
  95                 index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
  96                 lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
  97         }
  98
  99         if firstByteIsTwo != 1 || lookingForIndex != 0 || index < 9 {
 100                 return nil, errors.New("elgamal: decryption error")
 101         }
 102         return em[index+1:], nil
 103 }
 104
 105 // nonZeroRandomBytes fills the given slice with non-zero random octets.
 106 func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
 107         _, err = io.ReadFull(rand, s)
 108         if err != nil {
 109                 return
 110         }
 111
 112         for i := 0; i < len(s); i++ {
 113                 for s[i] == 0 {
 114                         _, err = io.ReadFull(rand, s[i:i+1])
 115                         if err != nil {
 116                                 return
 117                         }
 118                 }
 119         }
 120
 121         return
 122 }