// Copyright 2013 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package cipher

import (
	subtleoverlap 
	
	
	
)

// AEAD is a cipher mode providing authenticated encryption with associated
// data. For a description of the methodology, see
//	https://en.wikipedia.org/wiki/Authenticated_encryption
type AEAD interface {
	// NonceSize returns the size of the nonce that must be passed to Seal
	// and Open.
	NonceSize() int

	// Overhead returns the maximum difference between the lengths of a
	// plaintext and its ciphertext.
	Overhead() int

	// Seal encrypts and authenticates plaintext, authenticates the
	// additional data and appends the result to dst, returning the updated
	// slice. The nonce must be NonceSize() bytes long and unique for all
	// time, for a given key.
	//
	// To reuse plaintext's storage for the encrypted output, use plaintext[:0]
	// as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
	Seal(dst, nonce, plaintext, additionalData []byte) []byte

	// Open decrypts and authenticates ciphertext, authenticates the
	// additional data and, if successful, appends the resulting plaintext
	// to dst, returning the updated slice. The nonce must be NonceSize()
	// bytes long and both it and the additional data must match the
	// value passed to Seal.
	//
	// To reuse ciphertext's storage for the decrypted output, use ciphertext[:0]
	// as dst. Otherwise, the remaining capacity of dst must not overlap plaintext.
	//
	// Even if the function fails, the contents of dst, up to its capacity,
	// may be overwritten.
	Open(dst, nonce, ciphertext, additionalData []byte) ([]byte, error)
}

// gcmAble is an interface implemented by ciphers that have a specific optimized
// implementation of GCM, like crypto/aes. NewGCM will check for this interface
// and return the specific AEAD if found.
type gcmAble interface {
	NewGCM(nonceSize, tagSize int) (AEAD, error)
}

// gcmFieldElement represents a value in GF(2¹²⁸). In order to reflect the GCM
// standard and make binary.BigEndian suitable for marshaling these values, the
// bits are stored in big endian order. For example:
//   the coefficient of x⁰ can be obtained by v.low >> 63.
//   the coefficient of x⁶³ can be obtained by v.low & 1.
//   the coefficient of x⁶⁴ can be obtained by v.high >> 63.
//   the coefficient of x¹²⁷ can be obtained by v.high & 1.
type gcmFieldElement struct {
	low, high uint64
}

// gcm represents a Galois Counter Mode with a specific key. See
// https://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/gcm/gcm-revised-spec.pdf
type gcm struct {
	cipher    Block
	nonceSize int
	tagSize   int
	// productTable contains the first sixteen powers of the key, H.
	// However, they are in bit reversed order. See NewGCMWithNonceSize.
	productTable [16]gcmFieldElement
}

// NewGCM returns the given 128-bit, block cipher wrapped in Galois Counter Mode
// with the standard nonce length.
//
// In general, the GHASH operation performed by this implementation of GCM is not constant-time.
// An exception is when the underlying Block was created by aes.NewCipher
// on systems with hardware support for AES. See the crypto/aes package documentation for details.
func ( Block) (AEAD, error) {
	return newGCMWithNonceAndTagSize(, gcmStandardNonceSize, gcmTagSize)
}

// NewGCMWithNonceSize returns the given 128-bit, block cipher wrapped in Galois
// Counter Mode, which accepts nonces of the given length. The length must not
// be zero.
//
// Only use this function if you require compatibility with an existing
// cryptosystem that uses non-standard nonce lengths. All other users should use
// NewGCM, which is faster and more resistant to misuse.
func ( Block,  int) (AEAD, error) {
	return newGCMWithNonceAndTagSize(, , gcmTagSize)
}

// NewGCMWithTagSize returns the given 128-bit, block cipher wrapped in Galois
// Counter Mode, which generates tags with the given length.
//
// Tag sizes between 12 and 16 bytes are allowed.
//
// Only use this function if you require compatibility with an existing
// cryptosystem that uses non-standard tag lengths. All other users should use
// NewGCM, which is more resistant to misuse.
func ( Block,  int) (AEAD, error) {
	return newGCMWithNonceAndTagSize(, gcmStandardNonceSize, )
}

func newGCMWithNonceAndTagSize( Block, ,  int) (AEAD, error) {
	if  < gcmMinimumTagSize ||  > gcmBlockSize {
		return nil, errors.New("cipher: incorrect tag size given to GCM")
	}

	if  <= 0 {
		return nil, errors.New("cipher: the nonce can't have zero length, or the security of the key will be immediately compromised")
	}

	if ,  := .(gcmAble);  {
		return .NewGCM(, )
	}

	if .BlockSize() != gcmBlockSize {
		return nil, errors.New("cipher: NewGCM requires 128-bit block cipher")
	}

	var  [gcmBlockSize]byte
	.Encrypt([:], [:])

	 := &gcm{cipher: , nonceSize: , tagSize: }

	// We precompute 16 multiples of |key|. However, when we do lookups
	// into this table we'll be using bits from a field element and
	// therefore the bits will be in the reverse order. So normally one
	// would expect, say, 4*key to be in index 4 of the table but due to
	// this bit ordering it will actually be in index 0010 (base 2) = 2.
	 := gcmFieldElement{
		binary.BigEndian.Uint64([:8]),
		binary.BigEndian.Uint64([8:]),
	}
	.productTable[reverseBits(1)] = 

	for  := 2;  < 16;  += 2 {
		.productTable[reverseBits()] = gcmDouble(&.productTable[reverseBits(/2)])
		.productTable[reverseBits(+1)] = gcmAdd(&.productTable[reverseBits()], &)
	}

	return , nil
}

const (
	gcmBlockSize         = 16
	gcmTagSize           = 16
	gcmMinimumTagSize    = 12 // NIST SP 800-38D recommends tags with 12 or more bytes.
	gcmStandardNonceSize = 12
)

func ( *gcm) () int {
	return .nonceSize
}

func ( *gcm) () int {
	return .tagSize
}

func ( *gcm) (, , ,  []byte) []byte {
	if len() != .nonceSize {
		panic("crypto/cipher: incorrect nonce length given to GCM")
	}
	if uint64(len()) > ((1<<32)-2)*uint64(.cipher.BlockSize()) {
		panic("crypto/cipher: message too large for GCM")
	}

	,  := sliceForAppend(, len()+.tagSize)
	if subtleoverlap.InexactOverlap(, ) {
		panic("crypto/cipher: invalid buffer overlap")
	}

	var ,  [gcmBlockSize]byte
	.deriveCounter(&, )

	.cipher.Encrypt([:], [:])
	gcmInc32(&)

	.counterCrypt(, , &)

	var  [gcmTagSize]byte
	.auth([:], [:len()], , &)
	copy([len():], [:])

	return 
}

var errOpen = errors.New("cipher: message authentication failed")

func ( *gcm) (, , ,  []byte) ([]byte, error) {
	if len() != .nonceSize {
		panic("crypto/cipher: incorrect nonce length given to GCM")
	}
	// Sanity check to prevent the authentication from always succeeding if an implementation
	// leaves tagSize uninitialized, for example.
	if .tagSize < gcmMinimumTagSize {
		panic("crypto/cipher: incorrect GCM tag size")
	}

	if len() < .tagSize {
		return nil, errOpen
	}
	if uint64(len()) > ((1<<32)-2)*uint64(.cipher.BlockSize())+uint64(.tagSize) {
		return nil, errOpen
	}

	 := [len()-.tagSize:]
	 = [:len()-.tagSize]

	var ,  [gcmBlockSize]byte
	.deriveCounter(&, )

	.cipher.Encrypt([:], [:])
	gcmInc32(&)

	var  [gcmTagSize]byte
	.auth([:], , , &)

	,  := sliceForAppend(, len())
	if subtleoverlap.InexactOverlap(, ) {
		panic("crypto/cipher: invalid buffer overlap")
	}

	if subtle.ConstantTimeCompare([:.tagSize], ) != 1 {
		// The AESNI code decrypts and authenticates concurrently, and
		// so overwrites dst in the event of a tag mismatch. That
		// behavior is mimicked here in order to be consistent across
		// platforms.
		for  := range  {
			[] = 0
		}
		return nil, errOpen
	}

	.counterCrypt(, , &)

	return , nil
}

// reverseBits reverses the order of the bits of 4-bit number in i.
func reverseBits( int) int {
	 = (( << 2) & 0xc) | (( >> 2) & 0x3)
	 = (( << 1) & 0xa) | (( >> 1) & 0x5)
	return 
}

// gcmAdd adds two elements of GF(2¹²⁸) and returns the sum.
func gcmAdd(,  *gcmFieldElement) gcmFieldElement {
	// Addition in a characteristic 2 field is just XOR.
	return gcmFieldElement{.low ^ .low, .high ^ .high}
}

// gcmDouble returns the result of doubling an element of GF(2¹²⁸).
func gcmDouble( *gcmFieldElement) ( gcmFieldElement) {
	 := .high&1 == 1

	// Because of the bit-ordering, doubling is actually a right shift.
	.high = .high >> 1
	.high |= .low << 63
	.low = .low >> 1

	// If the most-significant bit was set before shifting then it,
	// conceptually, becomes a term of x^128. This is greater than the
	// irreducible polynomial so the result has to be reduced. The
	// irreducible polynomial is 1+x+x^2+x^7+x^128. We can subtract that to
	// eliminate the term at x^128 which also means subtracting the other
	// four terms. In characteristic 2 fields, subtraction == addition ==
	// XOR.
	if  {
		.low ^= 0xe100000000000000
	}

	return
}

var gcmReductionTable = []uint16{
	0x0000, 0x1c20, 0x3840, 0x2460, 0x7080, 0x6ca0, 0x48c0, 0x54e0,
	0xe100, 0xfd20, 0xd940, 0xc560, 0x9180, 0x8da0, 0xa9c0, 0xb5e0,
}

// mul sets y to y*H, where H is the GCM key, fixed during NewGCMWithNonceSize.
func ( *gcm) ( *gcmFieldElement) {
	var  gcmFieldElement

	for  := 0;  < 2; ++ {
		 := .high
		if  == 1 {
			 = .low
		}

		// Multiplication works by multiplying z by 16 and adding in
		// one of the precomputed multiples of H.
		for  := 0;  < 64;  += 4 {
			 := .high & 0xf
			.high >>= 4
			.high |= .low << 60
			.low >>= 4
			.low ^= uint64(gcmReductionTable[]) << 48

			// the values in |table| are ordered for
			// little-endian bit positions. See the comment
			// in NewGCMWithNonceSize.
			 := &.productTable[&0xf]

			.low ^= .low
			.high ^= .high
			 >>= 4
		}
	}

	* = 
}

// updateBlocks extends y with more polynomial terms from blocks, based on
// Horner's rule. There must be a multiple of gcmBlockSize bytes in blocks.
func ( *gcm) ( *gcmFieldElement,  []byte) {
	for len() > 0 {
		.low ^= binary.BigEndian.Uint64()
		.high ^= binary.BigEndian.Uint64([8:])
		.mul()
		 = [gcmBlockSize:]
	}
}

// update extends y with more polynomial terms from data. If data is not a
// multiple of gcmBlockSize bytes long then the remainder is zero padded.
func ( *gcm) ( *gcmFieldElement,  []byte) {
	 := (len() >> 4) << 4
	.updateBlocks(, [:])

	if len() !=  {
		var  [gcmBlockSize]byte
		copy([:], [:])
		.updateBlocks(, [:])
	}
}

// gcmInc32 treats the final four bytes of counterBlock as a big-endian value
// and increments it.
func gcmInc32( *[16]byte) {
	 := [len()-4:]
	binary.BigEndian.PutUint32(, binary.BigEndian.Uint32()+1)
}

// sliceForAppend takes a slice and a requested number of bytes. It returns a
// slice with the contents of the given slice followed by that many bytes and a
// second slice that aliases into it and contains only the extra bytes. If the
// original slice has sufficient capacity then no allocation is performed.
func sliceForAppend( []byte,  int) (,  []byte) {
	if  := len() + ; cap() >=  {
		 = [:]
	} else {
		 = make([]byte, )
		copy(, )
	}
	 = [len():]
	return
}

// counterCrypt crypts in to out using g.cipher in counter mode.
func ( *gcm) (,  []byte,  *[gcmBlockSize]byte) {
	var  [gcmBlockSize]byte

	for len() >= gcmBlockSize {
		.cipher.Encrypt([:], [:])
		gcmInc32()

		xorWords(, , [:])
		 = [gcmBlockSize:]
		 = [gcmBlockSize:]
	}

	if len() > 0 {
		.cipher.Encrypt([:], [:])
		gcmInc32()
		xorBytes(, , [:])
	}
}

// deriveCounter computes the initial GCM counter state from the given nonce.
// See NIST SP 800-38D, section 7.1. This assumes that counter is filled with
// zeros on entry.
func ( *gcm) ( *[gcmBlockSize]byte,  []byte) {
	// GCM has two modes of operation with respect to the initial counter
	// state: a "fast path" for 96-bit (12-byte) nonces, and a "slow path"
	// for nonces of other lengths. For a 96-bit nonce, the nonce, along
	// with a four-byte big-endian counter starting at one, is used
	// directly as the starting counter. For other nonce sizes, the counter
	// is computed by passing it through the GHASH function.
	if len() == gcmStandardNonceSize {
		copy([:], )
		[gcmBlockSize-1] = 1
	} else {
		var  gcmFieldElement
		.update(&, )
		.high ^= uint64(len()) * 8
		.mul(&)
		binary.BigEndian.PutUint64([:8], .low)
		binary.BigEndian.PutUint64([8:], .high)
	}
}

// auth calculates GHASH(ciphertext, additionalData), masks the result with
// tagMask and writes the result to out.
func ( *gcm) (, ,  []byte,  *[gcmTagSize]byte) {
	var  gcmFieldElement
	.update(&, )
	.update(&, )

	.low ^= uint64(len()) * 8
	.high ^= uint64(len()) * 8

	.mul(&)

	binary.BigEndian.PutUint64(, .low)
	binary.BigEndian.PutUint64([8:], .high)

	xorWords(, , [:])
}