// $Id: $//// $Log: $// Revision 1.2  1998/05/2  Serpent authors// + further performance improvement by new gate circuits// + and other changes//// Revision 1.1.3  1998/04/14  raif// + further performance improvement by reducing multi-dim array references.// + performance improvement by inlining function calls.// + added code to generate Intermediate Values KAT.// + cosmetics.//// Revision 1.1  1998/04/07  Serpent authors// + revised slightly (endianness, and key schedule for variable lengths)//// Revision 1.0  1998/04/06  raif// + start of history.//// $Endlog$/* * Copyright (c) 1997, 1998 Systemics Ltd on behalf of * the Cryptix Development Team. All rights reserved. */package Serpent;import java.io.PrintWriter;import java.security.InvalidKeyException;//.........................................................................../** * A bit-slice implementation in Java of the Serpent cipher.<p> * * Serpent is a 128-bit 32-round block cipher with variable key lengths, * including 128-, 192- and 256-bit * keys conjectured to be at least as secure as three-key triple-DES.<p> * * Serpent was designed by Ross Anderson, Eli Biham and Lars Knudsen as a * candidate algorithm for the NIST AES Quest.<p> * * References:<ol> *  <li>Serpent: A New Block Cipher Proposal. This paper was published in the *  proceedings of the "Fast Software Encryption Workshop No. 5" held in *  Paris in March 1998. LNCS, Springer Verlag.<p> *  <li>Reference implementation of the standard Serpent cipher written in C *  by <a href="http://www.cl.cam.ac.uk/~fms/"> Frank Stajano</a>.</ol><p> * * <b>Copyright</b> &copy; 1997, 1998 * <a href="http://www.systemics.com/">Systemics Ltd</a> on behalf of the * <a href="http://www.systemics.com/docs/cryptix/">Cryptix Development Team</a>. * <br>All rights reserved.<p> * * <b>$Revision: $</b> * @author  Raif S. Naffah * @author  Serpent authors (Ross Anderson, Eli Biham and Lars Knudsen) */public final class Serpent_BitSlice // implicit no-argument constructor{// Debugging methods and variables//...........................................................................    static final String NAME = "Serpent_BitSlice";    static final boolean IN = true, OUT = false;    static final boolean DEBUG = Serpent_Properties.GLOBAL_DEBUG;    static final int debuglevel =        DEBUG ? Serpent_Properties.getLevel("Serpent_Algorithm") : 0;    static final PrintWriter err =        DEBUG ? Serpent_Properties.getOutput() : null;    static final boolean TRACE =        Serpent_Properties.isTraceable("Serpent_Algorithm");    static void debug (String s) { err.println(">>> "+NAME+": "+s); }    static void trace (boolean in, String s) {        if (TRACE) err.println((in?"==> ":"<== ")+NAME+"."+s);    }    static void trace (String s) { if (TRACE) err.println("<=> "+NAME+"."+s); }// Constants and variables//...........................................................................    static final int BLOCK_SIZE =  16; // bytes in a data-block    static final int ROUNDS = 32;              // nbr of rounds    static final int PHI = 0x9E3779B9; // (sqrt(5) - 1) * 2**31    /**     * An array of 32 (number of rounds) S boxes.<p>     *     * An S box is an array of 16 distinct quantities, each in the range 0-15.     * A value v at position p for a given S box, implies that if this S box     * is given on input a value p, it will return the value v.     */    static final byte[][] Sbox = new byte[][] {	{ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 },/* S0: */	{15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 },/* S1: */	{ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 },/* S2: */	{ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 },/* S3: */	{ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 },/* S4: */	{15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 },/* S5: */	{ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 },/* S6: */	{ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 },/* S7: */	{ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 },/* S0: */	{15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 },/* S1: */	{ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 },/* S2: */	{ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 },/* S3: */	{ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 },/* S4: */	{15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 },/* S5: */	{ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 },/* S6: */	{ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 },/* S7: */	{ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 },/* S0: */	{15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 },/* S1: */	{ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 },/* S2: */	{ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 },/* S3: */	{ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 },/* S4: */	{15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 },/* S5: */	{ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 },/* S6: */	{ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 },/* S7: */	{ 3, 8,15, 1,10, 6, 5,11,14,13, 4, 2, 7, 0, 9,12 },/* S0: */	{15,12, 2, 7, 9, 0, 5,10, 1,11,14, 8, 6,13, 3, 4 },/* S1: */	{ 8, 6, 7, 9, 3,12,10,15,13, 1,14, 4, 0,11, 5, 2 },/* S2: */	{ 0,15,11, 8,12, 9, 6, 3,13, 1, 2, 4,10, 7, 5,14 },/* S3: */	{ 1,15, 8, 3,12, 0,11, 6, 2, 5, 4,10, 9,14, 7,13 },/* S4: */	{15, 5, 2,11, 4,10, 9,12, 0, 3,14, 8,13, 6, 7, 1 },/* S5: */	{ 7, 2,12, 5, 8, 4, 6,11,14, 9, 1,15,13, 3,10, 0 },/* S6: */	{ 1,13,15, 0,14, 8, 2,11, 7, 4,12,10, 9, 3, 5, 6 } /* S7: */    };    static final byte[][] SboxInverse = new byte[][] {	{13, 3,11, 0,10, 6, 5,12, 1,14, 4, 7,15, 9, 8, 2 },/* InvS0: */	{ 5, 8, 2,14,15, 6,12, 3,11, 4, 7, 9, 1,13,10, 0 },/* InvS1: */	{12, 9,15, 4,11,14, 1, 2, 0, 3, 6,13, 5, 8,10, 7 },/* InvS2: */	{ 0, 9,10, 7,11,14, 6,13, 3, 5,12, 2, 4, 8,15, 1 },/* InvS3: */	{ 5, 0, 8, 3,10, 9, 7,14, 2,12,11, 6, 4,15,13, 1 },/* InvS4: */	{ 8,15, 2, 9, 4, 1,13,14,11, 6, 5, 3, 7,12,10, 0 },/* InvS5: */	{15,10, 1,13, 5, 3, 6, 0, 4, 9,14, 7, 2,12, 8,11 },/* InvS6: */	{ 3, 0, 6,13, 9,14,15, 8, 5,12,11, 7,10, 1, 4, 2 },/* InvS7: */	{13, 3,11, 0,10, 6, 5,12, 1,14, 4, 7,15, 9, 8, 2 },/* InvS0: */	{ 5, 8, 2,14,15, 6,12, 3,11, 4, 7, 9, 1,13,10, 0 },/* InvS1: */	{12, 9,15, 4,11,14, 1, 2, 0, 3, 6,13, 5, 8,10, 7 },/* InvS2: */	{ 0, 9,10, 7,11,14, 6,13, 3, 5,12, 2, 4, 8,15, 1 },/* InvS3: */	{ 5, 0, 8, 3,10, 9, 7,14, 2,12,11, 6, 4,15,13, 1 },/* InvS4: */	{ 8,15, 2, 9, 4, 1,13,14,11, 6, 5, 3, 7,12,10, 0 },/* InvS5: */	{15,10, 1,13, 5, 3, 6, 0, 4, 9,14, 7, 2,12, 8,11 },/* InvS6: */	{ 3, 0, 6,13, 9,14,15, 8, 5,12,11, 7,10, 1, 4, 2 },/* InvS7: */	{13, 3,11, 0,10, 6, 5,12, 1,14, 4, 7,15, 9, 8, 2 },/* InvS0: */	{ 5, 8, 2,14,15, 6,12, 3,11, 4, 7, 9, 1,13,10, 0 },/* InvS1: */	{12, 9,15, 4,11,14, 1, 2, 0, 3, 6,13, 5, 8,10, 7 },/* InvS2: */	{ 0, 9,10, 7,11,14, 6,13, 3, 5,12, 2, 4, 8,15, 1 },/* InvS3: */	{ 5, 0, 8, 3,10, 9, 7,14, 2,12,11, 6, 4,15,13, 1 },/* InvS4: */	{ 8,15, 2, 9, 4, 1,13,14,11, 6, 5, 3, 7,12,10, 0 },/* InvS5: */	{15,10, 1,13, 5, 3, 6, 0, 4, 9,14, 7, 2,12, 8,11 },/* InvS6: */	{ 3, 0, 6,13, 9,14,15, 8, 5,12,11, 7,10, 1, 4, 2 },/* InvS7: */	{13, 3,11, 0,10, 6, 5,12, 1,14, 4, 7,15, 9, 8, 2 },/* InvS0: */	{ 5, 8, 2,14,15, 6,12, 3,11, 4, 7, 9, 1,13,10, 0 },/* InvS1: */	{12, 9,15, 4,11,14, 1, 2, 0, 3, 6,13, 5, 8,10, 7 },/* InvS2: */	{ 0, 9,10, 7,11,14, 6,13, 3, 5,12, 2, 4, 8,15, 1 },/* InvS3: */	{ 5, 0, 8, 3,10, 9, 7,14, 2,12,11, 6, 4,15,13, 1 },/* InvS4: */	{ 8,15, 2, 9, 4, 1,13,14,11, 6, 5, 3, 7,12,10, 0 },/* InvS5: */	{15,10, 1,13, 5, 3, 6, 0, 4, 9,14, 7, 2,12, 8,11 },/* InvS6: */	{ 3, 0, 6,13, 9,14,15, 8, 5,12,11, 7,10, 1, 4, 2 } /* InvS7: */    };    private static final char[] HEX_DIGITS = {        '0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'    };// Basic API methods//...........................................................................    /**     * Expand a user-supplied key material into a session key.     *     * @param key  The user-key bytes (multiples of 4) to use.     * @exception  InvalidKeyException  If the key is invalid.     */    public static synchronized Object makeKey (byte[] key)    throws InvalidKeyException {if (DEBUG) trace(IN, "makeKey("+key+")");if (DEBUG && debuglevel > 7) {System.out.println("Intermediate Bit-slice Session Key Values");System.out.println();System.out.println("Raw="+toString(key));}        // compute prekeys w[]:        // (a) from user key material        int[] w = new int[4 * (ROUNDS + 1)];        int limit = key.length / 4;        int i, j, t, offset = 0;        for (i = 0; i < limit; i++)            w[i] = (key[offset++] & 0xFF) |                   (key[offset++] & 0xFF) <<  8 |                   (key[offset++] & 0xFF) << 16 |                   (key[offset++] & 0xFF) << 24;        if (i < 8)            w[i++] = 1;//        for (; i < 8; i++)//            w[i] = 0;        // (b) and expanding them to full 132 x 32-bit material        // this is a literal implementation of the Serpent paper        // (section 4 The Key Schedule, p.226)        //        // start by computing the first 8 values using the second        // lot of 8 values as an intermediary buffer        for (i = 8, j = 0; i < 16; i++) {            t = w[j] ^ w[i-5] ^ w[i-3] ^ w[i-1] ^ PHI ^ j++;            w[i] = t << 11 | t >>> 21;        }        // translate the buffer by -8        for (i = 0, j = 8; i < 8; ) w[i++] = w[j++];        limit = 4 * (ROUNDS + 1); // 132 for a 32-round Serpent        // finish computing the remaining intermediary subkeys        for ( ; i < limit; i++) {            t = w[i-8] ^ w[i-5] ^ w[i-3] ^ w[i-1] ^ PHI ^ i;            w[i] = t << 11 | t >>> 21;        }        // compute intermediary key. use the same array as prekeys        int x0, x1, x2, x3, y0, y1, y2, y3, z;        byte[] sb;        for (i = 0; i < ROUNDS + 1; i++) {            x0 = w[4*i    ];            x1 = w[4*i + 1];            x2 = w[4*i + 2];            x3 = w[4*i + 3];            y0 = y1 = y2 = y3 = 0;            sb = Sbox[(ROUNDS + 3 - i) % ROUNDS];            for (j = 0; j < 32; j++) {                z = sb[((x0 >>> j) & 0x01)      |                       ((x1 >>> j) & 0x01) << 1 |                       ((x2 >>> j) & 0x01) << 2 |                       ((x3 >>> j) & 0x01) << 3];                y0 |= ( z        & 0x01) << j;                y1 |= ((z >>> 1) & 0x01) << j;                y2 |= ((z >>> 2) & 0x01) << j;                y3 |= ((z >>> 3) & 0x01) << j;            }            w[4*i    ] = y0;            w[4*i + 1] = y1;            w[4*i + 2] = y2;            w[4*i + 3] = y3;        }        // instead of a 2-dim array use a 1-dim array for better preformanceif (DEBUG && debuglevel > 7) {System.out.println("K[]:"); for(i=0;i<ROUNDS+1;i++){for(j=0;j<4;j++) System.out.print("0x"+intToString(w[i*4+j])+", "); System.out.println();}System.out.println();}if (DEBUG) trace(OUT, "makeKey()");        return w;    }    /**     * Encrypt exactly one block of plaintext.     *     * @param  in         The plaintext.     * @param  inOffset   Index of in from which to start considering data.     * @param  sessionKey The session key to use for encryption.     * @return The ciphertext generated from a plaintext using the session key.     */    public static byte[]    blockEncrypt (byte[] in, int inOffset, Object sessionKey) {if (DEBUG) trace(IN, "blockEncrypt("+in+", "+inOffset+", "+sessionKey+")");        int[] K = (int[]) sessionKey;        int x0 = (in[inOffset++] & 0xFF)       |                 (in[inOffset++] & 0xFF) <<  8 |                 (in[inOffset++] & 0xFF) << 16 |                 (in[inOffset++] & 0xFF) << 24;        int x1 = (in[inOffset++] & 0xFF)       |                 (in[inOffset++] & 0xFF) <<  8 |                 (in[inOffset++] & 0xFF) << 16 |                 (in[inOffset++] & 0xFF) << 24;        int x2 = (in[inOffset++] & 0xFF)       |                 (in[inOffset++] & 0xFF) <<  8 |                 (in[inOffset++] & 0xFF) << 16 |                 (in[inOffset++] & 0xFF) << 24;        int x3 = (in[inOffset++] & 0xFF)       |                 (in[inOffset++] & 0xFF) <<  8 |                 (in[inOffset++] & 0xFF) << 16 |                 (in[inOffset++] & 0xFF) << 24;        int y0, y1, y2, y3, z;	int t00, t01, t02, t03, t04, t05, t06, t07, t08, t09, t10;	int t11, t12, t13, t14, t15, t16, t17, t18, t19;	x0 ^=  K[ 0*4+0];	x1 ^=  K[ 0*4+1];	x2 ^=  K[ 0*4+2];	x3 ^=  K[ 0*4+3] ;/* S0:   3  8 15  1 10  6  5 11 14 13  4  2  7  0  9 12 *//* depth = 5,7,4,2, Total gates=18 */	t01 = x1  ^ x2 ;	t02 = x0  | x3 ;	t03 = x0  ^ x1 ;	y3  = t02 ^ t01;	t05 = x2  | y3 ;	t06 = x0  ^ x3 ;	t07 = x1  | x2 ;	t08 = x3  & t05;	t09 = t03 & t07;	y2  = t09 ^ t08;	t11 = t09 & y2 ;	t12 = x2  ^ x3 ;	t13 = t07 ^ t11;	t14 = x1  & t06;	t15 = t06 ^ t13;	y0  =     ~ t15;	t17 = y0  ^ t14;	y1  = t12 ^ t17;	x0  = ((((y0))<<(13))| (((y0))>>>(32-(13)))) ;	x2  = ((((y2))<<(3))| (((y2))>>>(32-(3)))) ;	x1  =   y1  ^   x0  ^   x2 ;	x3  =   y3  ^   x2  ^ (x0)<<3;	x1  = ((((x1))<<(1))| (((x1))>>>(32-(1)))) ;	x3  = ((((x3))<<(7))| (((x3))>>>(32-(7)))) ;	x0  =   x0  ^   x1  ^   x3 ;	x2  =   x2  ^   x3  ^ (x1 <<7);	x0  = ((((x0))<<(5))| (((x0))>>>(32-(5)))) ;	x2  = ((((x2))<<(22))| (((x2))>>>(32-(22))))  ;	x0 ^=  K[ 1*4+0];	x1 ^=  K[ 1*4+1];	x2 ^=  K[ 1*4+2];	x3 ^=  K[ 1*4+3] ;/* S1:  15 12  2  7  9  0  5 10  1 11 14  8  6 13  3  4 *//* depth = 10,7,3,5, Total gates=18 */	t01 = x0  | x3 ;	t02 = x2  ^ x3 ;	t03 =     ~ x1 ;	t04 = x0  ^ x2 ;	t05 = x0  | t03;	t06 = x3  & t04;	t07 = t01 & t02;	t08 = x1  | t06;	y2  = t02 ^ t05;	t10 = t07 ^ t08;	t11 = t01 ^ t10;	t12 = y2  ^ t11;	t13 = x1  & x3 ;	y3  =     ~ t10;	y1  = t13 ^ t12;	t16 = t10 | y1 ;	t17 = t05 & t16;	y0  = x2  ^ t17;	x0  = ((((y0))<<(13))| (((y0))>>>(32-(13)))) ;	x2  = ((((y2))<<(3))| (((y2))>>>(32-(3)))) ;	x1  =   y1  ^   x0  ^   x2 ;	x3  =   y3  ^   x2  ^ (x0)<<3;	x1  = ((((x1))<<(1))| (((x1))>>>(32-(1)))) ;	x3  = ((((x3))<<(7))| (((x3))>>>(32-(7)))) ;	x0  =   x0  ^   x1  ^   x3 ;	x2  =   x2  ^   x3  ^ (x1 <<7);	x0  = ((((x0))<<(5))| (((x0))>>>(32-(5)))) ;	x2  = ((((x2))<<(22))| (((x2))>>>(32-(22))))  ;	x0 ^=  K[ 2*4+0];	x1 ^=  K[ 2*4+1];	x2 ^=  K[ 2*4+2];	x3 ^=  K[ 2*4+3] ;/* S2:   8  6  7  9  3 12 10 15 13  1 14  4  0 11  5  2 *//* depth = 3,8,11,7, Total gates=16 */	t01 = x0  | x2 ;	t02 = x0  ^ x1 ;	t03 = x3  ^ t01;	y0  = t02 ^ t03;	t05 = x2  ^ y0 ;	t06 = x1  ^ t05;	t07 = x1  | t05;	t08 = t01 & t06;	t09 = t03 ^ t07;	t10 = t02 | t09;	y1  = t10 ^ t08;	t12 = x0  | x3 ;	t13 = t09 ^ y1 ;	t14 = x1  ^ t13;	y3  =     ~ t09;	y2  = t12 ^ t14;	x0  = ((((y0))<<(13))| (((y0))>>>(32-(13)))) ;	x2  = ((((y2))<<(3))| (((y2))>>>(32-(3)))) ;	x1  =   y1  ^   x0  ^   x2 ;	x3  =   y3  ^   x2  ^ (x0)<<3;	x1  = ((((x1))<<(1))| (((x1))>>>(32-(1)))) ;	x3  = ((((x3))<<(7))| (((x3))>>>(32-(7)))) ;	x0  =   x0  ^   x1  ^   x3 ;	x2  =   x2  ^   x3  ^ (x1 <<7);	x0  = ((((x0))<<(5))| (((x0))>>>(32-(5)))) ;	x2  = ((((x2))<<(22))| (((x2))>>>(32-(22))))  ;	x0 ^=  K[ 3*4+0];	x1 ^=  K[ 3*4+1];	x2 ^=  K[ 3*4+2];	x3 ^=  K[ 3*4+3] ;/* S3:   0 15 11  8 12  9  6  3 13  1  2  4 10  7  5 14 *//* depth = 8,3,5,5, Total gates=18 */	t01 = x0  ^ x2 ;	t02 = x0  | x3 ;	t03 = x0  & x3 ;	t04 = t01 & t02;	t05 = x1  | t03;	t06 = x0  & x1 ;	t07 = x3  ^ t04;	t08 = x2  | t06;	t09 = x1  ^ t07;	t10 = x3  & t05;	t11 = t02 ^ t10;	y3  = t08 ^ t09;	t13 = x3  | y3 ;	t14 = x0  | t07;	t15 = x1  & t13;	y2  = t08 ^ t11;