/**
SpaceMac : This library provide 3 static methods: mac, combine, and verify
The field of operation is GF(2^8) Rijndael field.

- mac : calculate a SpaceMac tag for an input vector
- combine : combine tags of the combining vectors to generate a valid SpaceMac 
tag for the combination
- verify : verify if a tag is valid for an input vector

The PRG and PRF calls are implemented using AES provided by "crypto++" library. 
If using Debian distribution, the package required is "libcrypto++-dev". See 
details about input/output of each function below.
*/

#include "cryptopp/aes.h" // byte = unsigned char
using CryptoPP::AES;

#include "cryptopp/modes.h" // using AES CBC mode
using CryptoPP::CBC_Mode;
		
class SpaceMac {
	public:
		// ----------------------- MAC ---------------------------
		// Compute a SpaceMac tag for a vector given a key pair (k1,k2), 
		// space id, the vector, parameters n and m
		//
		// INPUT
		// k1 : key for the PRG - a byte (unsigned char) array of size 16
		// k2 : key for the PRF - a byte array of size 16
		// id : id of the space - unsigned short in range 1 to MAX_ID
		// n : number of symbols, type unsigned short, e.g., 1019
		// m : number of vectors per generation, type unsigned short, e.g., 5
		// y : input vector to generate tag - a byte array of size (n+m)
		// iv : the IV used with AES - a byte array of size 16
		//
		// OUTPUT
		// t : tag of type byte of y under key (k1,k2)
		static byte mac(byte k1[], byte k2[], unsigned short id, 
				unsigned short n, unsigned short m, byte y[], byte iv[]);

		// ----------------------- VERIFY ---------------------------
		// Verify if an input tag t is a valid tag for vector y under key k=(k1,k2)
		//
		// INPUT
		// k1 : key for the PRG - a byte (unsigned char) array of size 16
		// k2 : key for the PRF - a byte array of size 16
		// id : id of the space - unsigned short in range 1 to MAX_ID
		// n : number of symbols, type unsigned short, e.g., 1019
		// m : number of vectors per generation, type unsigned short, e.g., 5
		// y : input vector to generate tag - a byte array of size (n+m)
		// iv : the IV used with AES - a byte array of size 16
		// t : tag of type byte of the vector to check
		//
		// OUTPUT
		// true if the tag is valid, false otherwise
		static bool verify(byte k1[], byte k2[], unsigned short id, 
				unsigned short n, unsigned short m, byte y[], byte iv[], byte t);

		// ------------------------ COMBINE ----------------------------
		// Combine tags to generate a valid new tag
		//
		// INPUT
		// tags : tags of the incoming vectors - a byte array of length len
		// alphas : local coding coefficents - a byte array of length len
		// len: length of the input arrays - an unsigned short
		//
		// OUTPUT
		// t : tag of the combined vector
		static byte combine(byte tags[], byte alphas[], unsigned short len);

	private: 
		static byte products[256][256];
		static bool initYet;
		static const unsigned short MAX_ID;

		//----------- PRIVATE HELPER FUNCTIONS ---------------------------
		// Multiply two numbers in GF(2^8) finite field defined by
		// the polynomial x^8 + x^4 + x^3 + x + 1 using
		// the "peasant's algorithm"
		static byte gmul(byte a, byte b);

		// Precalculate all the products once
		static void initialize();
};

bool SpaceMac::initYet = false;
byte SpaceMac::products[256][256];
const unsigned short SpaceMac::MAX_ID = 100;

// Multiply two numbers in GF(2^8) finite field defined by
// the polynomial x^8 + x^4 + x^3 + x + 1 using
// the "peasant's algorithm"
byte SpaceMac::gmul(byte a, byte b) {
	byte p=0;
	byte counter;
	byte hiBitSet;
	for (counter=0; counter<8; counter++) {
			if (b & 1) // low bit of b is set?
				p ^= a;
			hiBitSet = (a & 0x80); // high bit of a is set?
			a <<= 1;
			if (hiBitSet)
				a ^= 0x1b; // xor with x^4 + x^3 + x + 1
			b >>= 1;
	}
	return p;
}

// Precalculate all the products once
void SpaceMac::initialize() {
	int i,j;
	for (i=0; i<256; i++)
		for (j=0; j<256; j++)
			products[i][j] = gmul(i,j);
	initYet = true;
}

// ----------------------- MAC ---------------------------
// Compute a SpaceMac tag for a vector given a key pair (k1,k2), 
// space id, the vector, parameters n and m
//
// INPUT
// k1 : key for the PRG - a byte (unsigned char) array of size 16
// k2 : key for the PRF - a byte array of size 16
// id : id of the space - unsigned short in range 1 to MAX_ID
// n : number of symbols, type unsigned short, e.g., 1019
// m : number of vectors per generation, type unsigned short, e.g., 5
// y : input vector to generate tag - a byte array of size (n+m)
// iv : the IV used with AES - a byte array of size 16
//
// OUTPUT
// t : tag of type byte of y under key (k1,k2)
byte SpaceMac::mac(byte k1[], byte k2[], unsigned short id, 
		unsigned short n, unsigned short m, byte y[], byte iv[]) {
	unsigned short i,j; // vanilla loop index
	short padSize;    // padding size	
	byte r[n+m];      // result of PRG call
	byte f[m];        // results of PRF calls
	byte msgF[16];    // msg used with AES to produce PRF
	byte cipherF[16]; // cipher stored encryption of msgF
	
	byte key1[16];    // key used for PRG
	byte key2[16];    // key used for PRF
	CBC_Mode< AES >::Encryption enc; // AES CBC-mode encryption obj
	byte t;           // tag of vector y
	
	// precompute products once
	if (!initYet) {
		initialize();
		initYet=true;
	}

	// prepare keys
	for (i=0; i<16; i++) {		
		key1[i] = *(k1+i);
		key2[i] = *(k2+i);
	}

	// -------------------------------------- 1. get r from a PRG on k1	
	padSize = (n+m)%16;
	if (padSize>0)
		padSize = 16-padSize; // if divisible by 16, no need to pad
	byte msg[n+m+padSize];
	for (i=0; i<n+m; i++)
		msg[i]=i%256;
	for (i=n+m; i<n+m+padSize; i++)
		msg[i]=padSize; //PKCS5 Padding		
	byte cipher[n+m+padSize];
	enc.SetKeyWithIV(key1, sizeof(key1), iv);	
	enc.ProcessData(cipher,msg,n+m+padSize);
	
	for (i=0; i<n+m; i++) // extract r
		r[i] = cipher[i];
	

	//--------------------------------------- 2. get f's = F(k2, id, j)'s	
	enc.SetKeyWithIV(key2, sizeof(key2), iv);
	for (i=0; i<m; i++) {
		msgF[0] = (byte) id; //msg is composed of id and i
		msgF[1] = (byte) (id>>8);
		msgF[2] = (byte) i;
		msgF[3] = (byte) (i>>8);
		for (j=4; j<16; j++) // 16 is the block size
			msgF[j] = 12; // PKCS5 Padding, needed to pad 12 bytes
		enc.ProcessData(cipherF,msgF,16);	
		f[i] = cipherF[0]; //use the first byte		
	}

	//--------------------------------------- 3. compute the tag using r,f,y
	t = 0;
	for (i=0; i<n+m; i++)
		t ^= products[ r[i] ][ y[i] ]; // adding in GF(2^8) is XOR
	for (i=0; i<m; i++)
		t ^= products[ y[n+i] ][ f[i] ];

	return t;
}

// ----------------------- VERIFY ---------------------------
// Verify if an input tag t is a valid tag for vector y under key k=(k1,k2)
//
// INPUT
// k1 : key for the PRG - a byte (unsigned char) array of size 16
// k2 : key for the PRF - a byte array of size 16
// id : id of the space - unsigned short in range 1 to MAX_ID
// n : number of symbols, type unsigned short, e.g., 1019
// m : number of vectors per generation, type unsigned short, e.g., 5
// y : input vector to generate tag - a byte array of size (n+m)
// iv : the IV used with AES - a byte array of size 16
// t : tag of type byte of the vector to check
//
// OUTPUT
// true if the tag is valid, false otherwise
bool SpaceMac::verify(byte k1[], byte k2[], unsigned short id, 
		unsigned short n, unsigned short m, byte y[], byte iv[], byte t) {
	// precompute products once
	if (!initYet) {
		initialize();
		initYet=true;
	}
	return (t==mac(k1,k2,id,n,m,y,iv));
}

// ------------------------ COMBINE ----------------------------
// Combine tags to generate a valid new tag
//
// INPUT
// tags : tags of the incoming vectors - a byte array of length len
// alphas : local coding coefficents - a byte array of length len
// len: length of the input arrays - an unsigned short
//
// OUTPUT
// t : tag of the combined vector
byte SpaceMac::combine(byte tags[], byte alphas[], unsigned short len) {
	unsigned short i; // loop counter
	byte t; // result 

	// precompute products once
	if (!initYet) {
		initialize();
		initYet=true;
	}

	t = 0;
	for (i=0; i<len; i++)
		t ^= products[ alphas[i] ][ tags[i] ];
	return t;
}