// mult multiplies two numbers in GF(2^8)
func mult(a, b uint8) (out uint8) {
	var goodVal, zero uint8
	log_a := logTable[a]
	log_b := logTable[b]
	sum := (int(log_a) + int(log_b)) % 255

	ret := expTable[sum]

	// Ensure we return zero if either a or be are zero but aren't subject to
	// timing attacks
	goodVal = ret

	if subtle.ConstantTimeByteEq(a, 0) == 1 {
		ret = zero
	} else {
		ret = goodVal
	}

	if subtle.ConstantTimeByteEq(b, 0) == 1 {
		ret = zero
	} else {
		// This operation does not do anything logically useful. It
		// only ensures a constant number of assignments to thwart
		// timing attacks.
		goodVal = zero
	}

	return ret
}

// VerifyPKCS1v15 verifies an RSA PKCS#1 v1.5 signature.
// hashed is the result of hashing the input message using the given hash
// function and sig is the signature. A valid signature is indicated by
// returning a nil error.
func VerifyPKCS1v15(pub *PublicKey, hash crypto.Hash, hashed []byte, sig []byte) (err error) {
	hashLen, prefix, err := pkcs1v15HashInfo(hash, len(hashed))
	if err != nil {
		return
	}

	tLen := len(prefix) + hashLen
	k := (pub.N.BitLen() + 7) / 8
	if k < tLen+11 {
		err = VerificationError{}
		return
	}

	c := new(big.Int).SetBytes(sig)
	m := encrypt(new(big.Int), pub, c)
	em := leftPad(m.Bytes(), k)
	// EM = 0x00 || 0x01 || PS || 0x00 || T

	ok := subtle.ConstantTimeByteEq(em[0], 0)
	ok &= subtle.ConstantTimeByteEq(em[1], 1)
	ok &= subtle.ConstantTimeCompare(em[k-hashLen:k], hashed)
	ok &= subtle.ConstantTimeCompare(em[k-tLen:k-hashLen], prefix)
	ok &= subtle.ConstantTimeByteEq(em[k-tLen-1], 0)

	for i := 2; i < k-tLen-1; i++ {
		ok &= subtle.ConstantTimeByteEq(em[i], 0xff)
	}

	if ok != 1 {
		return VerificationError{}
	}

	return nil
}

func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, msg []byte, err error) {
	k := (priv.N.BitLen() + 7) / 8
	if k < 11 {
		err = DecryptionError{}
		return
	}

	c := new(big.Int).SetBytes(ciphertext)
	m, err := decrypt(rand, priv, c)
	if err != nil {
		return
	}

	em := leftPad(m.Bytes(), k)
	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
	secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)

	// The remainder of the plaintext must be a string of non-zero random
	// octets, followed by a 0, followed by the message.
	//   lookingForIndex: 1 iff we are still looking for the zero.
	//   index: the offset of the first zero byte.
	var lookingForIndex, index int
	lookingForIndex = 1

	for i := 2; i < len(em); i++ {
		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
	}

	valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1)
	msg = em[index+1:]
	return
}

// Decrypt takes two integers, resulting from an ElGamal encryption, and
// returns the plaintext of the message. An error can result only if the
// ciphertext is invalid. Users should keep in mind that this is a padding
// oracle and thus, if exposed to an adaptive chosen ciphertext attack, can
// be used to break the cryptosystem.  See ``Chosen Ciphertext Attacks
// Against Protocols Based on the RSA Encryption Standard PKCS #1'', Daniel
// Bleichenbacher, Advances in Cryptology (Crypto '98),
func Decrypt(priv *PrivateKey, c1, c2 *big.Int) (msg []byte, err error) {
	s := new(big.Int).Exp(c1, priv.X, priv.P)
	s.ModInverse(s, priv.P)
	s.Mul(s, c2)
	s.Mod(s, priv.P)
	em := s.Bytes()

	firstByteIsTwo := subtle.ConstantTimeByteEq(em[0], 2)

	// The remainder of the plaintext must be a string of non-zero random
	// octets, followed by a 0, followed by the message.
	//   lookingForIndex: 1 iff we are still looking for the zero.
	//   index: the offset of the first zero byte.
	var lookingForIndex, index int
	lookingForIndex = 1

	for i := 1; i < len(em); i++ {
		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
	}

	if firstByteIsTwo != 1 || lookingForIndex != 0 || index < 9 {
		return nil, errors.New("elgamal: decryption error")
	}
	return em[index+1:], nil
}

func (v *bitvector) SetBit(idx, bit uint) {
	byteIdx := idx / 8
	bitIdx := 7 - idx&7
	oldBit := uint8((v[byteIdx] & (1 << bitIdx)) >> bitIdx)
	flip := 1 ^ subtle.ConstantTimeByteEq(oldBit, uint8(bit))
	v[byteIdx] ^= byte(flip << bitIdx)
}

// div divides two numbers in GF(2^8)
func div(a, b uint8) uint8 {
	if b == 0 {
		// leaks some timing information but we don't care anyways as this
		// should never happen, hence the panic
		panic("divide by zero")
	}

	var goodVal, zero uint8
	log_a := logTable[a]
	log_b := logTable[b]
	diff := (int(log_a) - int(log_b)) % 255
	if diff < 0 {
		diff += 255
	}

	ret := expTable[diff]

	// Ensure we return zero if a is zero but aren't subject to timing attacks
	goodVal = ret

	if subtle.ConstantTimeByteEq(a, 0) == 1 {
		ret = zero
	} else {
		ret = goodVal
	}

	return ret
}

func constantTimeIsZero(x []byte) int {
	var ret byte
	for _, v := range x {
		ret |= v
	}

	return subtle.ConstantTimeByteEq(ret, 0)
}

func incrNonce(n *[24]byte) {
	zero := 0

	// Will always do 6 comparisons and incrs so as to
	// not leak information on how large the nonce counter is.
	// Probably unnecessary but it cant hurt.
	for k, v := range [...]int{23, 22, 21, 20, 19, 18} {
		n[v]++
		// Check for byte wrap around from 255 to 0
		// If it occurs incr the next most significant byte
		if subtle.ConstantTimeByteEq(n[v], 0) != 1 {
			for i := 0; i < 5-k; i++ {
				subtle.ConstantTimeByteEq(0, 0)
				zero++
			}
			break
		}
	}

	zero = 0
}

func main() {
	log.Printf("%d", subtle.ConstantTimeByteEq(43, 65))
	log.Printf("%d", subtle.ConstantTimeCompare([]byte("batman"), []byte("robin ")))

	bytes := make([]byte, 6)
	subtle.ConstantTimeCopy(1, bytes, []byte("batman"))
	log.Printf("%s", bytes)

	log.Printf("%d", subtle.ConstantTimeEq(256, 255))
	log.Printf("%d", subtle.ConstantTimeSelect(1, 2, 3))
	log.Printf("%d", subtle.ConstantTimeSelect(0, 2, 3))
}

// decryptPKCS1v15 decrypts ciphertext using priv and blinds the operation if
// rand is not nil. It returns one or zero in valid that indicates whether the
// plaintext was correctly structured. In either case, the plaintext is
// returned in em so that it may be read independently of whether it was valid
// in order to maintain constant memory access patterns. If the plaintext was
// valid then index contains the index of the original message in em.
func decryptPKCS1v15(rand io.Reader, priv *PrivateKey, ciphertext []byte) (valid int, em []byte, index int, err error) {
	k := (priv.N.BitLen() + 7) / 8
	if k < 11 {
		err = ErrDecryption
		return
	}

	c := new(big.Int).SetBytes(ciphertext)
	m, err := decrypt(rand, priv, c)
	if err != nil {
		return
	}

	em = leftPad(m.Bytes(), k)
	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)
	secondByteIsTwo := subtle.ConstantTimeByteEq(em[1], 2)

	// The remainder of the plaintext must be a string of non-zero random
	// octets, followed by a 0, followed by the message.
	//   lookingForIndex: 1 iff we are still looking for the zero.
	//   index: the offset of the first zero byte.
	lookingForIndex := 1

	for i := 2; i < len(em); i++ {
		equals0 := subtle.ConstantTimeByteEq(em[i], 0)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals0, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals0, 0, lookingForIndex)
	}

	// The PS padding must be at least 8 bytes long, and it starts two
	// bytes into em.
	validPS := subtle.ConstantTimeLessOrEq(2+8, index)

	valid = firstByteIsZero & secondByteIsTwo & (^lookingForIndex & 1) & validPS
	index = subtle.ConstantTimeSelect(valid, index+1, 0)
	return valid, em, index, nil
}

func matchHash(hash1, hash2 []byte) bool {
	var size = len(hash1)
	if size > len(hash2) {
		size = len(hash2)
	}

	var matched = 0
	for i := 0; i < size; i++ {
		matched += subtle.ConstantTimeByteEq(hash1[i], hash2[i])
	}

	match := (matched == size)
	sameSize := len(hash1) == len(hash2)
	return match && sameSize
}

func CompareHash(hash, key, in []byte) bool {
	matched := 0

	in_hash, err := Hmac(key, in)
	if err != nil {
		in_hash = make([]byte, len(hash))
	} else if len(hash) < len(in_hash) {
		extend := make([]byte, HashLen-len(hash))
		hash = append(hash, extend...)
	}

	for i := 0; i < HashLen; i++ {
		matched += subtle.ConstantTimeByteEq(hash[i], in_hash[i])
	}

	return matched == HashLen
}

// MatchPassword compares the input password with the password hash.
// It returns true if they match.
func MatchPassword(password string, ph *PasswordHash) bool {
	matched := 0
	new_hash := HashPasswordWithSalt(password, ph.Salt)

	size := len(new_hash.Hash)
	if size > len(ph.Hash) {
		size = len(ph.Hash)
	}

	for i := 0; i < size; i++ {
		matched += subtle.ConstantTimeByteEq(new_hash.Hash[i], ph.Hash[i])
	}

	passed := matched == size
	if len(new_hash.Hash) != len(ph.Hash) {
		return false
	}
	return passed
}

// MatchPassword compares the input password with the password hash.
// It returns true if they match.
func MatchPassword(password string, pk *PasswordKey) bool {
	matched := 0
	new_key := DeriveKeyWithSalt(password, pk.Salt)

	size := len(new_key.Key)
	if size > len(pk.Key) {
		size = len(pk.Key)
	}

	for i := 0; i < size; i++ {
		matched += subtle.ConstantTimeByteEq(new_key.Key[i], pk.Key[i])
	}

	passed := matched == size
	if len(new_key.Key) != len(pk.Key) {
		return false
	}
	return passed
}

// pkcsUnpad implements PKCS#7 un-padding.  If the padding is valid a valid value of 1 is returned.
// If the padding is invalid, valid is returned as 0.  Any unpaddeddata value should not be used
// if pcksUnpad determines the padding is invalid.  A logic error returns an error.  If you
// have not already authenticated the ciphertext, reporting a padding error, even through side channels
// (like timing), leaves you open to padding oracle attacks, so beware.
//
// I am implementing pkcsPad with constant time operations to forestall timing attacks that might
// be used to create a padding oracle. Since this package always authenticates first,
// timing and padding oracle attacks are ineffective because ciphertexts cannot be
// forged or manipulated with more than insignificant probability of success.
// In such a case constant time operation is unimportant, but constant timing may be important if this
// code is reused elsewhere.
func pkcsUnpad(data []byte, blocklen int) (valid int, unpaddeddata []byte, err error) {

	if blocklen > math.MaxUint8 {
		err = fmt.Errorf("Unpadding error: Blocklen %d exceeds maximum one byte unsigned integer",
			blocklen, math.MaxUint8)
		return
	}

	origlen := len(data)

	if origlen < blocklen {
		err = fmt.Errorf("Unpadding error: Data length %d is less than blocklen %d",
			origlen, blocklen)
		return
	}

	if origlen%blocklen != 0 {
		err = fmt.Errorf("Unpadding error: Data length %d is not a multiple of blocklen %d",
			origlen, blocklen)
		return
	}

	padchar := data[origlen-1]
	padcharlen := int(padchar)

	datalen := origlen - padcharlen

	valid = subtle.ConstantTimeLessOrEq(padcharlen, blocklen)

	for i := 1; i <= blocklen; i++ {
		// valid = (i > padcharlen || data[origlen-i] == padchar) && valid
		iLePadcharlen := subtle.ConstantTimeLessOrEq(i, padcharlen)
		isPadChar := subtle.ConstantTimeByteEq(data[origlen-i], padchar)
		stillvalid := subtle.ConstantTimeSelect(iLePadcharlen, isPadChar, 1)
		valid &= stillvalid
	}

	unpaddeddata = data[:datalen] // This data should not be used if invalid.
	// Returning it in any case simplifies constant timing
	return
}

// VerifyValue extracts a value from a string created by SignValue. An error is
// returned if the expiration time has elapsed or the signature is not correct.
func VerifyValue(secret, context string, signedValue string) (string, os.Error) {
	a := strings.SplitN(signedValue, "~", 3)
	if len(a) != 3 {
		return "", errVerificationFailure
	}
	expiration, err := strconv.Btoi64(a[1], 16)
	if err != nil || expiration < time.Seconds() {
		return "", errVerificationFailure
	}
	expectedSig := signature(secret, context, a[1], a[2])
	actualSig := a[0]
	if len(actualSig) != len(expectedSig) {
		return "", errVerificationFailure
	}
	// Constant time compare
	var v byte
	for i := 0; i < len(actualSig); i++ {
		v |= actualSig[i] ^ expectedSig[i]
	}
	if subtle.ConstantTimeByteEq(v, 0) != 1 {
		return "", errVerificationFailure
	}
	return a[2], nil
}

// DecryptOAEP decrypts ciphertext using RSA-OAEP.
// If random != nil, DecryptOAEP uses RSA blinding to avoid timing side-channel attacks.
func DecryptOAEP(hash hash.Hash, random io.Reader, priv *PrivateKey, ciphertext []byte, label []byte) (msg []byte, err error) {
	if err := checkPub(&priv.PublicKey); err != nil {
		return nil, err
	}
	k := (priv.N.BitLen() + 7) / 8
	if len(ciphertext) > k ||
		k < hash.Size()*2+2 {
		err = ErrDecryption
		return
	}

	c := new(big.Int).SetBytes(ciphertext)

	m, err := decrypt(random, priv, c)
	if err != nil {
		return
	}

	hash.Write(label)
	lHash := hash.Sum(nil)
	hash.Reset()

	// Converting the plaintext number to bytes will strip any
	// leading zeros so we may have to left pad. We do this unconditionally
	// to avoid leaking timing information. (Although we still probably
	// leak the number of leading zeros. It's not clear that we can do
	// anything about this.)
	em := leftPad(m.Bytes(), k)

	firstByteIsZero := subtle.ConstantTimeByteEq(em[0], 0)

	seed := em[1 : hash.Size()+1]
	db := em[hash.Size()+1:]

	mgf1XOR(seed, hash, db)
	mgf1XOR(db, hash, seed)

	lHash2 := db[0:hash.Size()]

	// We have to validate the plaintext in constant time in order to avoid
	// attacks like: J. Manger. A Chosen Ciphertext Attack on RSA Optimal
	// Asymmetric Encryption Padding (OAEP) as Standardized in PKCS #1
	// v2.0. In J. Kilian, editor, Advances in Cryptology.
	lHash2Good := subtle.ConstantTimeCompare(lHash, lHash2)

	// The remainder of the plaintext must be zero or more 0x00, followed
	// by 0x01, followed by the message.
	//   lookingForIndex: 1 iff we are still looking for the 0x01
	//   index: the offset of the first 0x01 byte
	//   invalid: 1 iff we saw a non-zero byte before the 0x01.
	var lookingForIndex, index, invalid int
	lookingForIndex = 1
	rest := db[hash.Size():]

	for i := 0; i < len(rest); i++ {
		equals0 := subtle.ConstantTimeByteEq(rest[i], 0)
		equals1 := subtle.ConstantTimeByteEq(rest[i], 1)
		index = subtle.ConstantTimeSelect(lookingForIndex&equals1, i, index)
		lookingForIndex = subtle.ConstantTimeSelect(equals1, 0, lookingForIndex)
		invalid = subtle.ConstantTimeSelect(lookingForIndex&^equals0, 1, invalid)
	}

	if firstByteIsZero&lHash2Good&^invalid&^lookingForIndex != 1 {
		err = ErrDecryption
		return
	}

	msg = rest[index+1:]
	return
}