// Software optimized 48-bit Philips/NXP Mifare "Classic" CRYPTO-1 stream cipher algorithm by I.C. Wiener 2007-2008.
// For educational purposes only.
// No warranties or guarantees of any kind.
// This code is released into the public domain by its author.

#include <stdio.h>

// Basic macros:

#define u8				unsigned char
#define u32				unsigned long
#define u64				unsigned long long
#define rev8(x)			((((x)>>7)&1)^((((x)>>6)&1)<<1)^((((x)>>5)&1)<<2)^((((x)>>4)&1)<<3)^((((x)>>3)&1)<<4)^((((x)>>2)&1)<<5)^((((x)>>1)&1)<<6)^(((x)&1)<<7))
#define rev16(x)		(rev8 (x)^(rev8 (x>> 8)<< 8))
#define rev32(x)		(rev16(x)^(rev16(x>>16)<<16))
#define bit(x,n)		(((x)>>(n))&1)

// Single bit CRYPTO-1 functions:

// PRNG

static u32 crypto1_next (u32 x, const u32 n)
{
	u32		i;
	
	x = rev32(x);
	for (i = 0; i < n; i++) x=(x<<1)+(((x>>15)^(x>>13)^(x>>12)^(x>>10))&1);
	return rev32(x);
}

#define i4(x,a,b,c,d)	((u32)((((x)>>(a))&1)+(((x)>>(b))&1)*2+(((x)>>(c))&1)*4+(((x)>>(d))&1)*8))

static const u32 mf1_f4a = 0x9E98;
static const u32 mf1_f4b = 0xB48E;
static const u32 mf1_f5c = 0xEC57E80A;

// Nonlinear output/feedback function

static u32 nf20 (const u64 x)
{
	u32		i5;
	
	i5 = ((mf1_f4b >> i4 (x, 9,11,13,15)) & 1)* 1
	   + ((mf1_f4a >> i4 (x,17,19,21,23)) & 1)* 2
	   + ((mf1_f4a >> i4 (x,25,27,29,31)) & 1)* 4
	   + ((mf1_f4b >> i4 (x,33,35,37,39)) & 1)* 8
	   + ((mf1_f4a >> i4 (x,41,43,45,47)) & 1)*16;
	
	return (mf1_f5c >> i5) & 1;
}

// Linear output/feedback function

static u32 lf18 (const u64 x)
{
	return  (((x >>  0) ^ (x >>  5) ^ (x >>  9) ^ (x >> 10) ^ (x >> 12) ^ (x >> 14)
			^ (x >> 15) ^ (x >> 17) ^ (x >> 19) ^ (x >> 24) ^ (x >> 25) ^ (x >> 27)
			^ (x >> 29) ^ (x >> 35) ^ (x >> 39) ^ (x >> 41) ^ (x >> 42) ^ (x >> 43)) & 1);
}

// Single CRYPTO-1 round

// 0 - no feedback
// 1 - linear feedback
// 2 - nonlinear feedback
// 3 - both

static u32 crypto1_round (u64 *state, const u64 in_bit, const u32 fb)
{
	u64		x = *state;
	u32		lf, nf;
	
	lf = lf18(x);
	nf = nf20 (x);
	x = (x>>1) ^ ((in_bit ^ (fb&1?lf:0) ^ (fb&2?nf:0)) << 47);
	*state = x;
	return nf;
}

// 32 CRYPTO-1 rounds

static u32 crypto1_word (u64 * x, const u32 in_word, const u32 fb)
{
	u32		i, o;
	
	for (i = 0, o = 0; i < 32; i++) o += (u32) crypto1_round (x, bit(in_word,i^24), fb) << (i^24);
	return o;
}

#define tests	8

int main (void)
{
	u32		i, k;
	u64		s[tests];
	u64		key[tests] = {-1ULL>>16,  -1ULL>>16,  -1ULL>>16,  -1ULL>>16,  -1ULL>>16,  -1ULL>>16,  -1ULL>>16,  -1ULL>>16};
	u32		ID[tests] = {0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD, 0x7BED1AFD};
	u32		TC[tests] = {0x01020304, 0x02030405, 0x03040506, 0x04050607, 0x05060708, 0x06070809, 0x0708090A, 0x08090A0B};
	u32		RC[tests] = {0x12345678, 0x23456789, 0x3456789A, 0x456789AB, 0x56789ABC, 0x6789ABCD, 0x789ABCDE, 0x89ABCDEF};
	u32		RR[tests] = {0x8D3A9A9C, 0x525BF719, 0xB3B6BCF5, 0x8D58D582, 0x1A4389AD, 0x8E791939, 0x6D3566AF, 0x870B0215};
	u32		TR[tests] = {0x7208E6C6, 0xBBEF66AE, 0xC622FC7F, 0x21741A05, 0xE350ACD9, 0xD0240BF8, 0xF0B5A5C5, 0x8AD097B3};
	u32		KS[tests][5] =
	{
		{0xF0293188, 0x96188BA7, 0x8743C386, 0x4BAFEEF2, 0x9F5B3C53},
		{0x6C5976CF, 0x4B2F94B8, 0x77B92595, 0xDDB19335, 0xB811C5A5},
		{0x7E55F18D, 0xE0AB17F7, 0xFFCF6559, 0x131E7093, 0x7145E26B},
		{0xBFDC7361, 0x9403B607, 0x26E4D8F2, 0xFEBAB9F0, 0x81AEB1C9},
		{0xD556A1EC, 0x8759D54D, 0xC5B10ACE, 0xB6A9C3CD, 0x94F5A51C},
		{0x0916465B, 0x0A9AE66B, 0x31EF4F79, 0x044D4505, 0xEE4125C4},
		{0x99C49847, 0x525B1DE4, 0xB7F78842, 0xF3A36608, 0x72E92768},
		{0xFEA22F39, 0x3B809753, 0x9893345F, 0x82371E6D, 0xBB9DEFAF}
	};
	
	for (k = 0; k < tests; k++)
	{
	//	s[k] = key[k];
	//	crypto1_word (s+k, ID[k] ^ TC[k], 1);
	//	crypto1_word (s+k, RC[k]        , 3);
	//	RR[k] = crypto1_next (TC[k], 64) ^ crypto1_word (s+k, 0, 1);
	//	TR[k] = crypto1_next (TC[k], 96) ^ crypto1_word (s+k, 0, 1);
	//	KS[k][0] = 0x3002108B ^ crypto1_word (s+k, 0, 1);
	//	for (i = 1; i < 5; i++) KS[k][i] = crypto1_word (s+k, 0, 1);
		s[k] = key[k];
		crypto1_word (s+k, ID[k] ^ TC[k], 1); printf ("%08X ", TC[k]);
		crypto1_word (s+k, RC[k]        , 3); printf ("%08X ", RC[k]);
		printf ("UID: %08X\nTag Challenge: %08X\nReader Challenge: %08X\nReader Response: %08X\nTag Response:%08X\nTag Command:%08X\nTag Data: %08X %08X %08X %08X\n\n",
			ID[k], TC[k], RC[k], RR[k], TR[k], KS[k][0], KS[k][1], KS[k][2], KS[k][3], KS[k][4]);
		printf ("%s ", (crypto1_next (TC[k], 64) ^ crypto1_word (s+k, 0, 1)) == RR[k] ? "OK" : "??");
		printf ("%s ", (crypto1_next (TC[k], 96) ^ crypto1_word (s+k, 0, 1)) == TR[k] ? "OK" : "??");
		for (i = 0; i < 5; i++) printf ("%08X ", KS[k][i] ^ crypto1_word (s+k, 0, 1));
		printf ("\n\n");
	}
	return 0;
}