libgo/go/crypto/rsa/pkcs1v15.go

   1 // Copyright 2009 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 rsa
   6
   7 import (
   8         "crypto"
   9         "crypto/subtle"
  10         "errors"
  11         "io"
  12         "math/big"
  13 )
  14
  15 // This file implements encryption and decryption using PKCS#1 v1.5 padding.
  16
  17 // EncryptPKCS1v15 encrypts the given message with RSA and the padding scheme from PKCS#1 v1.5.
  18 // The message must be no longer than the length of the public modulus minus 11 bytes.
  19 // WARNING: use of this function to encrypt plaintexts other than session keys
  20 // is dangerous. Use RSA OAEP in new protocols.
  21 func EncryptPKCS1v15(rand io.Reader, pub *PublicKey, msg []byte) (out []byte, err error) {
  22         k := (pub.N.BitLen() + 7) / 8
  23         if len(msg) > k-11 {
  24                 err = MessageTooLongError{}
  25                 return
  26         }
  27
  28         // EM = 0x02 || PS || 0x00 || M
  29         em := make([]byte, k-1)
  30         em[0] = 2
  31         ps, mm := em[1:len(em)-len(msg)-1], em[len(em)-len(msg):]
  32         err = nonZeroRandomBytes(ps, rand)
  33         if err != nil {
  34                 return
  35         }
  36         em[len(em)-len(msg)-1] = 0
  37         copy(mm, msg)
  38
  39         m := new(big.Int).SetBytes(em)
  40         c := encrypt(new(big.Int), pub, m)
  41         out = c.Bytes()
  42         return
  43 }
  44
  45 // DecryptPKCS1v15 decrypts a plaintext using RSA and the padding scheme from PKCS#1 v1.5.
  46 // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
  47 func DecryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (out []byte, err error) {
  48         valid, out, err := decryptPKCS1v15(rand, priv, ciphertext)
  49         if err == nil && valid == 0 {
  50                 err = DecryptionError{}
  51         }
  52
  53         return
  54 }
  55
  56 // DecryptPKCS1v15SessionKey decrypts a session key using RSA and the padding scheme from PKCS#1 v1.5.
  57 // If rand != nil, it uses RSA blinding to avoid timing side-channel attacks.
  58 // It returns an error if the ciphertext is the wrong length or if the
  59 // ciphertext is greater than the public modulus. Otherwise, no error is
  60 // returned. If the padding is valid, the resulting plaintext message is copied
  61 // into key. Otherwise, key is unchanged. These alternatives occur in constant
  62 // time. It is intended that the user of this function generate a random
  63 // session key beforehand and continue the protocol with the resulting value.
  64 // This will remove any possibility that an attacker can learn any information
  65 // about the plaintext.
  66 // See ``Chosen Ciphertext Attacks Against Protocols Based on the RSA
  67 // Encryption Standard PKCS #1'', Daniel Bleichenbacher, Advances in Cryptology
  68 // (Crypto '98),
  69 func DecryptPKCS1v15SessionKey(rand io.Reader, priv *PrivateKey, ciphertext []byte, key []byte) (err error) {
  70         k := (priv.N.BitLen() + 7) / 8
  71         if k-(len(key)+3+8) < 0 {
  72                 err = DecryptionError{}
  73                 return
  74         }
  75
  76         valid, msg, err := decryptPKCS1v15(rand, priv, ciphertext)
  77         if err != nil {
  78                 return
  79         }
  80
  81         valid &= subtle.ConstantTimeEq(int32(len(msg)), int32(len(key)))
  82         subtle.ConstantTimeCopy(valid, key, msg)
  83         return
  84 }
  85
  86 func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, msg []byte, err error) {
  87         k := (priv.N.BitLen() + 7) / 8
  88         if k < 11 {
  89                 err = DecryptionError{}
  90                 return
  91         }
  92
  93         c := new(big.Int).SetBytes(ciphertext)
  94         m, err := decrypt(rand, priv, c)
  95         if err != nil {
  96                 return
  97         }
  98
  99         em := leftPad(m.Bytes(), k)
 100         firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
 101         secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)
 102
 103         // The remainder of the plaintext must be a string of non-zero random
 104         // octets, followed by a 0, followed by the message.
 105         //   lookingForIndex: 1 iff we are still looking for the zero.
 106         //   index: the offset of the first zero byte.
 107         var lookingForIndex, index int
 108         lookingForIndex = 1
 109
 110         for i := 2; i < len(em); i++ {
 111                 equals0 := subtle.ConstantTimeByteEq(em[i], 0)
 112                 index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
 113                 lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
 114         }
 115
 116         valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1)
 117         msg = em[index+1:]
 118         return
 119 }
 120
 121 // nonZeroRandomBytes fills the given slice with non-zero random octets.
 122 func nonZeroRandomBytes(s []byte, rand io.Reader) (err error) {
 123         _, err = io.ReadFull(rand, s)
 124         if err != nil {
 125                 return
 126         }
 127
 128         for i := 0; i < len(s); i++ {
 129                 for s[i] == 0 {
 130                         _, err = io.ReadFull(rand, s[i:i+1])
 131                         if err != nil {
 132                                 return
 133                         }
 134                         // In tests, the PRNG may return all zeros so we do
 135                         // this to break the loop.
 136                         s[i] ^= 0x42
 137                 }
 138         }
 139
 140         return
 141 }
 142
 143 // These are ASN1 DER structures:
 144 //   DigestInfo ::= SEQUENCE {
 145 //     digestAlgorithm AlgorithmIdentifier,
 146 //     digest OCTET STRING
 147 //   }
 148 // For performance, we don't use the generic ASN1 encoder. Rather, we
 149 // precompute a prefix of the digest value that makes a valid ASN1 DER string
 150 // with the correct contents.
 151 var hashPrefixes = map[crypto.Hash][]byte{
 152         crypto.MD5:       {0x30, 0x20, 0x30, 0x0c, 0x06, 0x08, 0x2a, 0x86, 0x48, 0x86, 0xf7, 0x0d, 0x02, 0x05, 0x05, 0x00, 0x04, 0x10},
 153         crypto.SHA1:      {0x30, 0x21, 0x30, 0x09, 0x06, 0x05, 0x2b, 0x0e, 0x03, 0x02, 0x1a, 0x05, 0x00, 0x04, 0x14},
 154         crypto.SHA256:    {0x30, 0x31, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x01, 0x05, 0x00, 0x04, 0x20},
 155         crypto.SHA384:    {0x30, 0x41, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x02, 0x05, 0x00, 0x04, 0x30},
 156         crypto.SHA512:    {0x30, 0x51, 0x30, 0x0d, 0x06, 0x09, 0x60, 0x86, 0x48, 0x01, 0x65, 0x03, 0x04, 0x02, 0x03, 0x05, 0x00, 0x04, 0x40},
 157         crypto.MD5SHA1:   {}, // A special TLS case which doesn't use an ASN1 prefix.
 158         crypto.RIPEMD160: {0x30, 0x20, 0x30, 0x08, 0x06, 0x06, 0x28, 0xcf, 0x06, 0x03, 0x00, 0x31, 0x04, 0x14},
 159 }
 160
 161 // SignPKCS1v15 calculates the signature of hashed using RSASSA-PKCS1-V1_5-SIGN from RSA PKCS#1 v1.5.
 162 // Note that hashed must be the result of hashing the input message using the
 163 // given hash function.
 164 func SignPKCS1v15(rand io.Reader, priv *PrivateKey, hash crypto.Hash, hashed []byte) (s []byte, err error) {
 165         hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
 166         if err != nil {
 167                 return
 168         }
 169
 170         tLen := len(prefix) + hashLen
 171         k := (priv.N.BitLen() + 7) / 8
 172         if k < tLen+11 {
 173                 return nil, MessageTooLongError{}
 174         }
 175
 176         // EM = 0x00 || 0x01 || PS || 0x00 || T
 177         em := make([]byte, k)
 178         em[1] = 1
 179         for i := 2; i < k-tLen-1; i++ {
 180                 em[i] = 0xff
 181         }
 182         copy(em[k-tLen:k-hashLen], prefix)
 183         copy(em[k-hashLen:k], hashed)
 184
 185         m := new(big.Int).SetBytes(em)
 186         c, err := decrypt(rand, priv, m)
 187         if err == nil {
 188                 s = c.Bytes()
 189         }
 190         return
 191 }
 192
 193 // VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
 194 // hashed is the result of hashing the input message using the given hash
 195 // function and sig is the signature. A valid signature is indicated by
 196 // returning a nil error.
 197 func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) (err error) {
 198         hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
 199         if err != nil {
 200                 return
 201         }
 202
 203         tLen := len(prefix) + hashLen
 204         k := (pub.N.BitLen() + 7) / 8
 205         if k < tLen+11 {
 206                 err = VerificationError{}
 207                 return
 208         }
 209
 210         c := new(big.Int).SetBytes(sig)
 211         m := encrypt(new(big.Int), pub, c)
 212         em := leftPad(m.Bytes(), k)
 213         // EM = 0x00 || 0x01 || PS || 0x00 || T
 214
 215         ok := subtle.ConstantTimeByteEq(em[0], 0)
 216         ok &= subtle.ConstantTimeByteEq(em[1], 1)
 217         ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
 218         ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
 219         ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)
 220
 221         for i := 2; i < k-tLen-1; i++ {
 222                 ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
 223         }
 224
 225         if ok != 1 {
 226                 return VerificationError{}
 227         }
 228
 229         return nil
 230 }
 231
 232 func pkcs1v15HashInfo(hash crypto.Hash, inLen int) (hashLen int, prefix []byte, err error) {
 233         hashLen = hash.Size()
 234         if inLen != hashLen {
 235                 return 0, nil, errors.New("input must be hashed message")
 236         }
 237         prefix, ok := hashPrefixes[hash]
 238         if !ok {
 239                 return 0, nil, errors.New("unsupported hash function")
 240         }
 241         return
 242 }