def clamp(r):
	r = bytearray(r)
	r[3] &= 15
	r[7] &= 15
	r[11] &= 15
	r[15] &= 15
	r[4] &= 252
	r[8] &= 252
	r[12] &= 252
	return r

def ceildiv(a, b):
	return a // b if a % b == 0 else a // b + 1

def leu(b):
	n = 0
	for i in range(len(b)):
		n |= b[i] << (i * 8)
	return n

def unleu128(n):
	return bytes((n >> i) & 0xff for i in range(0, 128, 8))

def poly1305(message, key):
	r = leu(clamp(key[:16]))
	s = leu(key[16:])
	P = 2**130 - 5
	acc = 0
	for i in range(ceildiv(len(message), 16)):
		num = leu(message[i*16:i*16 + 16] + b'\x01')
		# WARNING: This is most likely not timing-safe
		acc = ((acc + num) * r) % P
	acc += s
	return unleu128(acc)

if __name__ == '__main__':
	key = bytes.fromhex('85:d6:be:78:57:55:6d:33:7f:44:52:fe:42:d5:06:a8:01:03:80:8a:fb:0d:b2:fd:4a:bf:f6:af:41:49:f5:1b'.replace(':', ''))
	message = b'Cryptographic Forum Research Group'
	print(poly1305(message, key).hex() == 'a8:06:1d:c1:30:51:36:c6:c2:2b:8b:af:0c:01:27:a9'.replace(':', ''))