/*
 * Copyright (C) Sergey P. Derevyago, 2005.
 *
 * Permission to copy, use, modify, sell and distribute this software is granted
 * provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied warranty, and
 * with no claim as to its suitability for any purpose.
 *
 */

import java.io.EOFException;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.RandomAccessFile;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * This is the reference implementation of DersCrypt symmetric-key block cipher.
 *
 * @see <a href="http://ders.stml.net/crypt/derscrypt/derscrypt.html">Crypto
 * algorithm DersCrypt</a> -- DersCrypt home page.
 * @version 1.1 2005-12-24
 * @author Sergey P. Derevyago
 */
public final class DersCrypt
{
 /**
  * Encrypts <code>in</code> and writes the result to <code>out</code>.
  *
  * @param key key to use
  * @param in stream to read plain text from
  * @param out stream to write encrypted text to
  * @return number of bytes read from <code>in</code>
  * @throws Exception in case of errors
  */
 public static long streamEncrypt(byte[] key, InputStream in, OutputStream out)
   throws Exception
 {
  long readCnt=0;
  int minLen=minBlockLength(key.length);

  byte[] buf1=readMax(in, minLen);
  readCnt+=buf1.length;

  for (byte[] prevEncr=null; buf1.length>0; ) {
      byte[] plain, buf2=readMax(in, minLen);
      readCnt+=buf2.length;

      if (buf2.length==minLen) {  // [1]
         plain=buf1;
         buf1=buf2;
      }
      else {
           plain=new byte[buf1.length+buf2.length];
           System.arraycopy(buf1, 0, plain, 0, buf1.length);
           System.arraycopy(buf2, 0, plain, buf1.length, buf2.length);

           buf1=new byte[0];
      }

      byte[] encr=blockEncrypt(key, plain, prevEncr);  // [2]
      prevEncr=encr;

      writeInt16(out, encr.length);  // [3]
      out.write(encr);
  }

  return readCnt;
 }

 /**
  * Decrypts <code>in</code> and writes the result to <code>out</code>.
  *
  * @param key key to use
  * @param in stream to read encrypted text from
  * @param out stream to write decrypted text to
  * @return number of bytes read from <code>in</code>
  * @throws Exception in case of errors
  */
 public static long streamDecrypt(byte[] key, InputStream in, OutputStream out)
   throws Exception
 {
  long readCnt=0;
  int minLen=minBlockLength(key.length);

  String errMsg="Invalid data: Invalid block format";
  byte[] prevEncr=null;

  for (int len; (len=readInt16(in))!=-1; ) {
      readCnt+=2;
      if (len<=minLen || len>=minLen*3) throw new Exception(errMsg);  // [4]

      byte[] encr=readMax(in, len);
      readCnt+=encr.length;

      if (encr.length!=len) throw new Exception(errMsg);  // [5]

      byte[] decr=blockDecrypt(key, encr, prevEncr);
      prevEncr=encr;

      out.write(decr);
  }

  return readCnt;
 }

 /**
  * Encrypts a block of plain text.
  *
  * @param key key to use
  * @param plain block of plain text to encrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @return encrypted block
  * @throws Exception in case of errors
  */
 public static byte[] blockEncrypt(byte[] key, byte[] plain, byte[] prevEncr)
   throws Exception
 {
  BigInteger b2=new BigInteger(1, key);  // [6]
  byte[] hash=computeHash(key.length, b2, plain, prevEncr);

  BigInteger aPr1=new BigInteger(1, appendHash(plain, hash));  // [7]

  boolean[] substOne=new boolean[1];
  BigInteger aPr2=basicEncrypt(b2, aPr1, substOne);
  byte[] encr=stripLeadingZeros(aPr2.toByteArray());  // [8]

  if (substOne[0] && blockDecryptImpl(key, encr, prevEncr, false)!=null) {
     throw new Exception("Cannot encrypt this data using this key: "+
       "Hash collision");  // [9]
  }

  return encr;
 }

 /**
  * Decrypts a block of encrypted text.
  *
  * @param key key to use
  * @param encr block of encrypted text to decrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @return decrypted block
  * @throws Exception in case of errors
  */
 public static byte[] blockDecrypt(byte[] key, byte[] encr, byte[] prevEncr)
   throws Exception
 {
  byte[] decr=blockDecryptImpl(key, encr, prevEncr, false);  // [10]
  if (decr!=null) return decr;

  decr=blockDecryptImpl(key, encr, prevEncr, true);  // [11]
  if (decr==null)
     throw new Exception("Incorrect key and/or data: Hash mismatch");  // [12] [13]

  return decr;
 }

 /**
  * Decrypts a block of encrypted text performing the substitution if requested.
  *
  * @param key key to use
  * @param encr block of encrypted text to decrypt
  * @param prevEncr previously encrypted block or <code>null</code>
  * @param substOne <code>true</code> if the most significant remainder of value
  *        1 must be substituted with 0
  * @return decrypted block or <code>null</code>
  */
 public static byte[] blockDecryptImpl(byte[] key, byte[] encr, byte[] prevEncr,
   boolean substOne)
 {
  BigInteger aPr2=new BigInteger(1, encr), b2=new BigInteger(1, key);

  BigInteger aPr1=basicDecrypt(b2, aPr2, substOne);
  if (aPr1==null) return null;  // [14]

  byte[] decr=stripLeadingZeros(aPr1.toByteArray());  // [15]

  byte[][] ph=extractHash(decr, key.length);
  byte[] plain=ph[0], hash=ph[1];

  byte[] hash2=computeHash(key.length, b2, plain, prevEncr);
  if (!Arrays.equals(hash, hash2)) return null;

  return plain;
 }

 /**
  * Basic encryption functionality.
  *
  * @param b2 key value to use
  * @param a1 number to encrypt
  * @param substOne output parameter, <code>true</code> if the most significant
  *        remainder of value 0 was substituted with 1
  * @return encrypted number
  */
 public static BigInteger basicEncrypt(BigInteger b2, BigInteger a1,
   boolean[] substOne)
 {
  BigInteger[] rems=computeRemainders(a1, b2);
  BigInteger[] rems2=permute(rems, b2, false);

  if (rems2[0].equals(BigInteger.ZERO)) {  // [16]
     rems2[0]=BigInteger.ONE;
     substOne[0]=true;
  }
  else substOne[0]=false;

  BigInteger a2=computeNumber(rems2, b2);
  return a2;
 }
 
 /**
  * Basic decryption functionality.
  *
  * @param b2 key value to use
  * @param a2 number to decrypt
  * @param substOne <code>true</code> if the most significant remainder of value
  *        1 must be substituted with 0 
  * @return decrypted number
  */
 public static BigInteger basicDecrypt(BigInteger b2, BigInteger a2,
   boolean substOne)
 {
  BigInteger[] rems=computeRemainders(a2, b2);

  if (substOne) {  // [17]
     if (rems[0].equals(BigInteger.ONE)) rems[0]=BigInteger.ZERO;
     else return null;
  }

  BigInteger[] rems2=permute(rems, b2, true);
  BigInteger a1=computeNumber(rems2, b2);
  return a1;
 }

 /**
  * Returns minimal data block length required for passed key length. [18]
  *
  * @param keyLength key length
  * @return minimal data block length
  */
 public static int minBlockLength(int keyLength)
 {
  if (keyLength<16) keyLength=16;       // 128->40
  else if (keyLength>64) keyLength=64;  // 512->100

  int n=40+((keyLength-16)*5+2)/4;
  return keyLength*n;
 }

 /**
  * Checks passed parameters.
  *
  * @param key key to check
  * @param length data length to check
  * @throws Exception in case of failed conditions
  */
 public static void check(byte[] key, long length) throws Exception
 {
  if (key[0]==0)
     throw new Exception("Suspectable key: Leading zeros are useless");  // [19]

  if ((key[key.length-1]&1)==0)
     throw new Exception("Suspectable key: Even values are not recommended");  // [20]

  int min=minBlockLength(key.length);
  if (length<min) {
     throw new Exception("Invalid data length: At least "+min+
       " bytes are required");  // [21]
  }
 }

 /**
  * Splits <code>a</code> into a sequence of remainders of division by
  * <code>b</code>.
  *
  * @param a number to split
  * @param b number to divide by
  * @return array of remainders
  */
 public static BigInteger[] computeRemainders(BigInteger a, BigInteger b)
 {
  LinkedList lst=new LinkedList();

  while (!a.equals(BigInteger.ZERO)) {  // [22]
        BigInteger[] qr=a.divideAndRemainder(b);
        a=qr[0];
        lst.addFirst(qr[1]);
  }

  return (BigInteger[])lst.toArray(new BigInteger[lst.size()]);
 }

 /**
  * Converts a sequence of remainders of division by <code>b</code> into a
  * number.
  *
  * @param rems array of remainders
  * @param b number to multiply by
  * @return computed number
  */
 public static BigInteger computeNumber(BigInteger[] rems, BigInteger b)
 {
  BigInteger a=rems[0];

  for (int i=1; i<rems.length; i++) {
      a=a.multiply(b);
      a=a.add(rems[i]);
  }

  return a;
 }
 
 /**
  * Computes hash of a data block. [23]
  *
  * @param len length of hash to compute
  * @param b2 key value to use
  * @param data data block to compute hash from
  * @param prevData previously processed block or <code>null</code>
  * @return computed hash
  */
 public static byte[] computeHash(int len, BigInteger b2, byte[] data,
   byte[] prevData)
 {
  byte[] bits;
  if (prevData!=null) bits=extractBits(prevData, len);
  else {
       bits=new byte[len];
       for (int i=0; i<len; i++) bits[i]=0x55;  // [24]
  }
  
  byte[] prevHash=permuteBits(bits, b2);

  BigInteger a1=new BigInteger(1, appendHash(data, prevHash));
  BigInteger a2=basicEncrypt(b2, a1, new boolean[1]);
  byte[] encr=stripLeadingZeros(a2.toByteArray());

  byte[] hash=permuteBits(extractBits(encr, len), b2);
  if (hash[0]==0) hash[0]=1;  // [25]

  return hash;
 }
 
 /**
  * Appends <code>hash</code> bytes to <code>data</code>. <code>hash</code>
  * array is split into two parts and <code>data</code> is inserted between
  * them.
  *
  * @param data data to append hash to
  * @param hash hash to append
  * @return computed array
  */
 public static byte[] appendHash(byte[] data, byte[] hash)
 {
  byte[] ret=new byte[data.length+hash.length];

  int len=hash.length, mid=len/2;
  System.arraycopy(hash, 0, ret, 0, len-mid);  // [26]
  System.arraycopy(data, 0, ret, len-mid, data.length);
  System.arraycopy(hash, len-mid, ret, ret.length-mid, mid);

  return ret;
 }

 /**
  * Splits passed array into the data and hash parts.
  *
  * @param bytes array to split
  * @param hashLen hash length
  * @return two-elements array with data and hash
  */
 public static byte[][] extractHash(byte[] bytes, int hashLen)
 {
  byte[] data=new byte[bytes.length-hashLen];
  byte[] hash=new byte[hashLen];

  int mid=hashLen/2;
  System.arraycopy(bytes, 0, hash, 0, hashLen-mid);
  System.arraycopy(bytes, hashLen-mid, data, 0, data.length);
  System.arraycopy(bytes, bytes.length-mid, hash, hashLen-mid, mid);

  return new byte[][]{data, hash};
 }

 /**
  * Strips leading zeros out of <code>bytes</code> array.
  *
  * @param bytes array to process
  * @return processed array
  */
 public static byte[] stripLeadingZeros(byte[] bytes)
 {
  if (bytes[0]!=0) return bytes;

  int i;
  for (i=1; i<bytes.length && bytes[i]==0; i++)
      ;

  return subArray(bytes, i, bytes.length-i);
 }

 /**
  * Extracts bits from passed <code>data</code>.
  *
  * @param data data to extract bits from
  * @param bitsLen length of array to return
  * @return computed array
  */
 public static byte[] extractBits(byte[] data, int bitsLen)
 {
  byte[] ret=new byte[bitsLen];

  for (int i=0, j=1; i<bitsLen; i++) {
      for (int mask=0x80; mask!=0; mask>>=1) {
          int n=(j++)*(data.length*8-1)/(bitsLen*8+1);  // [27]
          if ((data[n/8]&BIT_MASKS[n%8])!=0)
             ret[i]|=mask;
      }
  }

  return ret;
 }
 
 /**
  * Creates permutation of passed length. [28]
  *
  * @param len length of permutation
  * @param b number to create permutation from
  * @return array of positions
  */
 public static int[] createPermutation(int len, BigInteger b)
 {
  BigInteger b2=b;
  int[] ret=new int[len], val=new int[len];

  int med=len-len/2;
  for (int i=0; i<len; i++) {  // [29]
      ret[i]=-2;  // [30]

      int pos= (i<med) ? len-med+i : i-med;
      val[pos]=i;
  }

  int[] points={0, len-med, len};

  for (int p=0; p<points.length-1; p++) {  // [31]
      int pbeg=points[p], plen=points[p+1]-pbeg;

     loop:
      for (int i=0, sub=0; i<plen; i++) {
          if (i==plen-2 && sub==0) {  // don't left last element alone [32]
             for (int j=0; ; j++) {
                 if (ret[pbeg+j]==-2) {
                    if (ret[pbeg+j+1]==-2) {  // [33]
                       ret[pbeg+j]=val[pbeg+i+1];
                       ret[pbeg+j+1]=val[pbeg+i];
                       break loop;
                    }

                    break;
                 }
             }
          }

          BigInteger div=BigInteger.valueOf(plen-i-sub);
          if (b2.compareTo(div)<0) b2=b;  // restart from b [34]

          BigInteger[] qr=b2.divideAndRemainder(div);
          b2=qr[0];
          int rem=qr[1].intValue();

          for (int j=0, k=-1, v=val[pbeg+i]; ; j++) {
              if (ret[pbeg+j]==-2 && !(j>0 && v==ret[pbeg+j-1]+1) && ++k==rem) {
                 ret[pbeg+j]=v;
                 sub= (j+1<plen && ret[pbeg+j+1]==-2) ? 1 : 0;  // [35]

                 break;
              }
          }
      }
  }

  return ret;
 }

 /**
  * Permutes passed array of BigIntegers.
  *
  * @param rems array to permute
  * @param b number to create permutation from
  * @param inverse <code>true</code> if inverse permutation must be applied
  * @return permutted array
  */
 public static BigInteger[] permute(BigInteger[] rems, BigInteger b,
   boolean inverse)
 {
  int len=rems.length;
  BigInteger[] ret=new BigInteger[len];

  int perm[]=createPermutation(len, b);
  if (inverse) for (int i=0; i<len; i++) ret[i]=rems[perm[i]];
  else for (int i=0; i<len; i++) ret[perm[i]]=rems[i];

  return ret;
 }

 /**
  * Permutes bits of passed array.
  *
  * @param bits array to permute bits of
  * @param b number to create permutation from
  * @return permutted array
  */
 public static byte[] permuteBits(byte[] bits, BigInteger b)
 {
  byte[] ret=new byte[bits.length];

  int perm[]=createPermutation(bits.length*8, b);
  for (int i=0, j=0; i<bits.length; i++) {
      for (int mask=0x80; mask!=0; mask>>=1) {
          int n=perm[j++];
          if ((bits[i]&mask)!=0) ret[n/8]|=BIT_MASKS[n%8];
      }
  }

  return ret;
 }

 /**
  * Creates a subarray from passed array.
  *
  * @param array array to copy from
  * @param pos position to start from
  * @param len length of subarray
  * @return created subarray
  */
 public static byte[] subArray(byte[] array, int pos, int len)
 {
  byte[] ret=new byte[len];
  System.arraycopy(array, pos, ret, 0, len);

  return ret;
 }

 /**
  * Reads limited number of bytes. 
  *
  * @param in stream to read from
  * @param maxLen maximum number of bytes to read
  * @return read bytes
  * @throws Exception in case of errors
  */
 public static byte[] readMax(InputStream in, int maxLen) throws Exception
 {
  byte[] buf=new byte[maxLen];
  int cnt=in.read(buf);

  if (cnt==buf.length) return buf;
  if (cnt==-1) return new byte[0];
  return subArray(buf, 0, cnt);
 }

 /**
  * Writes 16 bit integer to stream using big-endian byte ordering.
  *
  * @param out stream to write to
  * @param val value to write
  * @throws Exception in case of errors
  */
 public static void writeInt16(OutputStream out, int val) throws Exception
 {
  out.write((val>>>8)&0xFF);
  out.write(val&0xFF);
 }

 /**
  * Reads 16 bit integer from stream using big-endian byte ordering.
  *
  * @param in stream to read from
  * @return read value or <code>-1</code> in case of EOF
  * @throws Exception in case of errors
  */
 public static int readInt16(InputStream in) throws Exception
 {
  int ch1=in.read();
  if (ch1==-1) return -1;

  int ch2=in.read();
  if (ch2==-1) throw new EOFException();

  return (ch1<<8)+ch2;
 }

 /** array of masks to extract successive bits of byte from left to right */
 public static final int[] BIT_MASKS={
   0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01
 };

 /**
  * The main function.
  * Checks passed parameters and performs requested operation.
  */
 public static void main(String[] args) throws Exception
 {
  if (args.length!=4) invalidArgs();

  String sCmd=args[0];
  String sKey=args[1];
  String sIn=args[2];
  String sOut=args[3];

  if ( !("e".equals(sCmd) || "d".equals(sCmd)) ) invalidArgs();

  byte[] key=readFile(sKey);
  check(key, (new File(sIn)).length());  // [36]

  FileInputStream fin=new FileInputStream(sIn);
  FileOutputStream fout=new FileOutputStream(sOut);

  long start=System.currentTimeMillis();

  long cnt= ("e".equals(sCmd)) ?
    streamEncrypt(key, fin, fout) : streamDecrypt(key, fin, fout);

  long dsec=(System.currentTimeMillis()-start+50)/100;
  if (dsec!=0) System.out.println((dsec/10)+" sec, "+(cnt*10/dsec)+" b/s");

  fout.close();
  fin.close();
 }

 /**
  * Prints the error message and exits.
  */
 public static void invalidArgs()
 {
  System.err.println("Invalid args. Must be:");
  System.err.println("e|d key_file input_file output_file");
  System.exit(1);
 }

 /**
  * Reads file with passed <code>name</code>.
  *
  * @param name file name
  * @return file content
  * @throws Exception in case of errors
  */
 public static byte[] readFile(String name) throws Exception
 {
  RandomAccessFile raf=new RandomAccessFile(name, "r");

  byte[] ret=new byte[(int)raf.length()];
  raf.readFully(ret);

  raf.close();
  return ret;
 }
}