/* $Id: feistel_bits.c $ */
/*
   $Date: 2013-02-17 11:55Z $
   $Revision: 1.0.1 $
*/
/********************* COPYRIGHT NOTICE ****************************
The source code in this module was originally written by David 
Ireland, copyright (c) 2013 D.I. Management Services Pty Limited,
all rights reserved. It is provided "as is" with no warranties.
You are free to use this code as part of your own applications.
However, it may not be reproduced or distributed separately by any 
means without the express written permission of the author. 
****************** END OF COPYRIGHT NOTICE *************************/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "bitarray.h"

typedef unsigned char BYTE;
typedef unsigned long WORD32;
typedef unsigned long long WORD64;

#define QLEN (sizeof(WORD64))

/** Convert 64-bit word into array of 8 bytes in bigendian order */
static void word64_to_bytes(BYTE *into, WORD64 outof)
{
  *into++ = (BYTE)((outof >> 56) & 0xffL);
  *into++ = (BYTE)((outof >> 48) & 0xffL);
  *into++ = (BYTE)((outof >> 40) & 0xffL);
  *into++ = (BYTE)((outof >> 32) & 0xffL);
  *into++ = (BYTE)((outof >> 24) & 0xffL);
  *into++ = (BYTE)((outof >> 16) & 0xffL);
  *into++ = (BYTE)((outof >>  8) & 0xffL);
  *into++ = (BYTE)( outof        & 0xffL);
}

/** Convert 8-byte array in bigendian order into 64-bit word */
static WORD64 word64_from_bytes(const BYTE *outof)
{
  WORD64 into;
  into    = (WORD64)(*outof++ & 0xffL) << 56;
  into   |= (WORD64)(*outof++ & 0xffL) << 48;
  into   |= (WORD64)(*outof++ & 0xffL) << 40;
  into   |= (WORD64)(*outof++ & 0xffL) << 32;
  into   |= (WORD64)(*outof++ & 0xffL) << 24;
  into   |= (WORD64)(*outof++ & 0xffL) << 16;
  into   |= (WORD64)(*outof++ & 0xffL) << 8;
  into   |= (WORD64)(*outof++ & 0xffL);
  return into;
}

/**************************/
/* LOCAL ENCRYPTION STUFF */
/**************************/
/* Interface: */
int encrypt_128(const BYTE key[16], BYTE data[16]);

/* (replace the internals here with your own AES function if you need to) */

// MSVC-specific explicit link to library
#define LIB_NAME "diCryptosys.lib"
#if !defined(unix) && (_MSC_VER >= 1400)
/* Link to the static library */
#if _WIN64
  #if _DEBUG
  #define MYLIBDIR "../x64/Debug/"
  #else
  #define MYLIBDIR "../x64/Release/"
  #endif
#else
  #if _DEBUG
  #define MYLIBDIR "../Debug/"
  #else
  #define MYLIBDIR "../Release/"
  #endif
#endif
#pragma comment(lib, MYLIBDIR LIB_NAME)
#endif

/* From diCryptoSys.h <http://www.cryptosys.net/#api> */
long _stdcall AES128_Bytes(unsigned char *lpOutput, const unsigned char *lpInput, long nBytes, const unsigned char *lpKey, int fEncrypt);

/** Encrypt exactly 128-bits of data using a 128-bit key, both in 16-byte arrays:
 *  data = E(key, data) */
int encrypt_128(const BYTE key[16], BYTE data[16])
{
  int r;
  r = AES128_Bytes(data, data, 16, key, 1);
  return r;
}
/*********************************/
/* END OF LOCAL ENCRYPTION STUFF */
/*********************************/

void ffsem_prf(BYTE *E, const BYTE *data, size_t nbytes, size_t nbits, const BYTE *key, size_t tweak)
{
  /* PRF(x) = [E(k, x||0..0||tweak)]_nbits */
  BYTE B[16]; /* 128-bit encryption block */
  size_t blen = sizeof(B);

  memset(B, 0, blen);
  memcpy(B, data, nbytes);
  B[blen-1] = (BYTE)tweak;
  bit_pr_bytes("B=      ", B, blen, "\n");
  encrypt_128(key, B);  /* B = E(key, B) */
  bit_pr_bytes("E(k,B)= ", B, blen, "\n");
  /* Truncate E(.) to nbits */
  bit_substr(E, B, nbytes, nbits, 0, nbits);
}

static void ffsem_round_common(BYTE *data, size_t nbytes, size_t nbits, 
  const BYTE *key, size_t tweak, int encrypt)
{
  size_t halfbits = nbits / 2;  // half-length
  size_t hlen = nbytes / 2;
  size_t n, i, index, length;
  BYTE E[8];
  BYTE right[8], left[8];

  assert(8 == nbytes);  /* PRE nbytes == 8 */
  /* Split input data into left and right blocks */
  index = 0;
  length = halfbits;
  n = bit_substr(left, data, nbytes, nbits, index, length);
  //printf("bit_substr[%d,%d] returns %d\n", index, length, n);
  bit_pr_bytes("L=", left, hlen, "\t");
  bit_print("", left, hlen, n, "\n");
  index = halfbits;
  length = halfbits;
  n = bit_substr(right, data, nbytes, nbits, index, length);
  //printf("bit_substr[%d,%d] returns %d\n", index, length, n);
  bit_pr_bytes("R=", right, hlen, "\t");
  bit_print("", right, hlen, n, "\n");

  if (encrypt)
  {
    /* Algorithm:
      INPUT: L || R
      L' = R
      R' = L XOR PRF(R)
      OUTPUT: L' || R'
    */
    /* R' = L XOR PRF(R) */
    ffsem_prf(E, right, hlen, halfbits, key, tweak);
    bit_pr_bytes("E=      ", E, hlen, "\n");
    bit_pr_bytes("L=      ", left, hlen, "\n");
    for (i = 0; i < hlen; i++)
      left[i] = left[i] ^ E[i];
    /* Truncate R' to 54-bits */
    bit_substr(left, left, hlen, halfbits, 0, halfbits);
    bit_pr_bytes("L XOR E=", left, hlen, "\n");
    /* L' || R' = R || (L XOR PRF(R)) */
  }
  else
  {
    /* Algorithm:
      INPUT: L || R
      R' = L
      L' = R XOR PRF(L)
      OUTPUT: L' || R'
    */  
    /* L' = R XOR PRF(L) */
    ffsem_prf(E, left, hlen, halfbits, key, tweak);
    bit_pr_bytes("E=      ", E, hlen, "\n");
    bit_pr_bytes("R=      ", right, hlen, "\n");
    for (i = 0; i < hlen; i++)
      right[i] = right[i] ^ E[i];
    /* Truncate L' to 54-bits */
    bit_substr(right, right, hlen, halfbits, 0, halfbits);
    bit_pr_bytes("R XOR E=", right, hlen, "\n");
    /* L' || R' = (R XOR PRF(L)) || L */
  }

  /* Concatenate bitstrings L' || R' */
  bit_pr_bytes("L'=", right, hlen, "\t");
  bit_print("", right, hlen, halfbits, "\n");
  bit_pr_bytes("R'=", left, hlen, "\t");
  bit_print("", left, hlen, halfbits, "\n");
  bit_concat(data, nbytes, right, hlen, halfbits, left, hlen, halfbits);
  bit_print("", data, nbytes, nbits, "\n");
  bit_pr_index("", nbits, "\n");
}

void ffsem_round_encr(BYTE *data, size_t nbytes, size_t nbits, const BYTE *key, size_t tweak)
{
  ffsem_round_common(data, nbytes, nbits, key, tweak, 1);
}

void ffsem_round_decr(BYTE *data, size_t nbytes, size_t nbits, const BYTE *key, size_t tweak)
{
  ffsem_round_common(data, nbytes, nbits, key, tweak, 0);
}

static int ffsem_crypt_common(WORD64 *ccout, WORD64 ccn, WORD64 ccmax, size_t maxbits, 
  BYTE key[16], size_t nrounds, int encrypt)
{
  BYTE a[QLEN], b[QLEN], c[QLEN];
  size_t n, nbits, r;
  int loops = 0;

  bit_pr_bytes("KEY=", key, 16, "\n");
  do 
  {
    loops++;
    printf("ccn=0x%llx\n", ccn);
    word64_to_bytes(a, ccn);
    bit_pr_bytes("arr=", a, QLEN, "\n");

    // Encode to 54-bit string
    nbits = maxbits;
    n = bit_encode(b, a, QLEN, nbits);
    printf("bit_encode[%d]=", nbits);
    bit_pr_bytes("", b, n, "\n");
    bit_print("", b, n, nbits, "\n");

    if (encrypt)
    {
      /* Fiestel encryption on blocks of nbits */
      for (r = 1; r <= nrounds; r++)
      {
        printf("Round %d:\n", r);
        bit_pr_bytes("input=  ", b, n, "\n");
        ffsem_round_encr(b, QLEN, nbits, key, r);
        bit_pr_bytes("output= ", b, n, "\n");
      }
    }
    else
    {
      /* Fiestel decryption on blocks of nbits */
      for (r = nrounds; r >= 1; r--)
      {
        printf("Round %d:\n", r);
        bit_pr_bytes("input=  ", b, n, "\n");
        ffsem_round_decr(b, QLEN, nbits, key, r);
        bit_pr_bytes("output= ", b, n, "\n");
      }
    }

    // Decode to 64-bit QWORD
    n = bit_decode(c, b, QLEN, nbits);
    printf("bit_decode[%d]=", nbits);
    bit_pr_bytes("", c, QLEN, "\n");
    bit_print("", c, QLEN, QLEN*8, "\n");
    ccn = word64_from_bytes(c);
    printf("ccn=0x%llx\n", ccn);
    printf("ccn=%016lld_d %s %016lld_d %s\n", ccn, (ccn <= ccmax ? "<=" : ">"), ccmax,
      (ccn <= ccmax ? "OK" : "Repeat..."));
  } while (ccn > ccmax);

  printf("Found solution in %d loop%s\n", loops, (loops > 1 ? "s" : ""));
  *ccout = ccn;
  return loops;
}

int ffsem_encrypt(WORD64 *ccout, WORD64 ccn, WORD64 ccmax, size_t maxbits, BYTE key[16], size_t nrounds)
{
  return ffsem_crypt_common(ccout, ccn, ccmax, maxbits, key, nrounds, 1);
}
int ffsem_decrypt(WORD64 *ccout, WORD64 ccn, WORD64 ccmax, size_t maxbits, BYTE key[16], size_t nrounds)
{
  return ffsem_crypt_common(ccout, ccn, ccmax, maxbits, key, nrounds, 0);
}

int stop_on_multiple_loops = 0;

int main(void)
{
  BYTE key[16] = {  /* (0x)000102030405060708090a0b0c0d0e0f */
    0x00, 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 
    0x08, 0x09, 0x0A, 0x0B, 0x0C, 0x0D, 0x0E, 0x0F,
  };
  // Set of example 16-digit decimal numbers like credit card numbers
  WORD64 ccset[] = { 
    9999999999999997, 9999999999999999, 8888888888888888,
    7777777777777777, 6666666666666666,
  };
  int nccs = sizeof(ccset) / sizeof(ccset[0]);

  // Specific for 16-digit decimal numbers..
  const WORD64 ccmax = 9999999999999999;
  const size_t maxbits = 54;
  const size_t nrounds = 6;

  WORD64 ccn, cce, ccd;
  int i, nloops;

  //for (i = 0; i < nccs; i++)
  for (i = 3; i < 4; i++) // Just 7777777777777777
  {
    ccn = ccset[i];
    printf("ccn=%016lld_d\n", ccn);
    nloops = ffsem_encrypt(&cce, ccn, ccmax, maxbits, key, nrounds);
    printf("cce=%016lld_d\n", cce);
    if (stop_on_multiple_loops && nloops > 1)
    {
      printf("Hit enter to continue...");
      getchar();
    }
    // DECRYPT...
    nloops = ffsem_decrypt(&ccd, cce, ccmax, maxbits, key, nrounds);
    printf("ccd=%016lld_d\n", ccd);
    if (stop_on_multiple_loops && nloops > 1)
    {
      printf("Hit enter to continue...");
      getchar();
    }
    assert(ccd == ccn);
  }

  return 0;
}