elgamal.go 3.5 KB

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