/**
 * Title:        DualKeys
 * Description:  Explore the "dual" keys for DES
 * Copyright:    Copyright (c) 2000, Burton Rosenberg.
 * Company:      Univ of Miami
 * @author       Burton Rosenberg
 * @version 1.0
 */

/*  Keys K1 and K2 are dual if DES Encrypting with key K1 equals
 *  DES Decrypting with key K2. Notation: D(K1) = K2.
 *
 *  Conjecture: such keys arise exactly when the key schedule for
 *  K1 is the revers of the key schedule for K2, i.e. K1_i = K2_{17-i}
 *  for the i-th subkey of K1 and the (17-i)-th subkey of K2.
 *
 *  In which case, it is easy to see that if D(K1)=J1 and D(K2)=J2
 *  then D(K1 OR K2) = D(K1) OR D(K2) = J1 OR J2. Likewise for
 *  operations AND and XOR. It is also easy to see that the all zero's
 *  and all one's keys are self-dual. A corollary is that if D(K1)=K2
 *  then D(NOT K1)=NOT K2.
 *
 *  Furthermore, there are minimal primal-dual pairs whose AND is 0,
 *  and all primal-dual pairs are unions or extensions of these atoms
 *  and their complements.
 *
 *  The atoms are arrived at in this program by defining a more general
 *  form of D, first dualKeys() and then dualize(), and iterating
 *  dualize over a key with a single one until the result stabilizes; that
 *  is, dualize(K1)=K2; dualize(K2)=K1; ... .
 *
 *  Considering the space of keys as subsets of [1,64], the subset of
 *  integers i for which the i-th bit of the key is one, and making a poset
 *  of this space by subset inclusion, D is the closure of the dualize
 *  operation, and the primal/dual pair are closed elements.
 *
 *  dualize(K) = min { J | J_(17-i) contains K_i, i=1,...,16 }
 *
 *  The results are
 *  D({1}) = { 1,2,3,17,18,19,33,34,35,36,49,50,51,52 }
 *           { 9,10,11,25,26,27,41,42,43,44,57,58,59,60 }
 *         = D({2}) = D({3}) = ... etc.
 *
 *  D({4}) = { 4,5,6,7,20,21,22,23,37,38,39,53,54,55 }
 *           { 12,13,14,15,28,29,30,31,45,46,47,61,62,63 }
 *         = D({4}) = D({5}) = ... etc.
 */

package dualkeys;

public class DualKeys {

  static int keySchedule[][] =
    {
     /* round 1 */
       { 10, 51, 34, 60, 49, 17,   33, 57,  2,  9, 19, 42,
          3, 35, 26, 25, 44, 58,   59,  1, 36, 27, 18, 41,
         22, 28, 39, 54, 37,  4,   47, 30,  5, 53, 23, 29,
         61, 21, 38, 63, 15, 20,   45, 14, 13, 62, 55, 31 },
     /* round 2 */
       {  2, 43, 26, 52, 41,  9,   25, 49, 59,  1, 11, 34,
         60, 27, 18, 17, 36, 50,   51, 58, 57, 19, 10, 33,
         14, 20, 31, 46, 29, 63,   39, 22, 28, 45, 15, 21,
         53, 13, 30, 55,  7, 12,   37,  6,  5, 54, 47, 23 },
     /* round 3 */
       { 51, 27, 10, 36, 25, 58,    9, 33, 43, 50, 60, 18,
         44, 11,  2,  1, 49, 34,   35, 42, 41,  3, 59, 17,
         61,  4, 15, 30, 13, 47,   23,  6, 12, 29, 62,  5,
         37, 28, 14, 39, 54, 63,   21, 53, 20, 38, 31,  7 },
     /* round 4 */
       { 35, 11, 59, 49,  9, 42,   58, 17, 27, 34, 44,  2,
         57, 60, 51, 50, 33, 18,   19, 26, 25, 52, 43,  1,
         45, 55, 62, 14, 28, 31,    7, 53, 63, 13, 46, 20,
         21, 12, 61, 23, 38, 47,    5, 37,  4, 22, 15, 54 },
     /* round 5 */
       { 19, 60, 43, 33, 58, 26,   42,  1, 11, 18, 57, 51,
         41, 44, 35, 34, 17,  2,    3, 10,  9, 36, 27, 50,
         29, 39, 46, 61, 12, 15,   54, 37, 47, 28, 30,  4,
          5, 63, 45,  7, 22, 31,   20, 21, 55,  6, 62, 38 },
     /* round 6 */
       {  3, 44, 27, 17, 42, 10,   26, 50, 60,  2, 41, 35,
         25, 57, 19, 18,  1, 51,   52, 59, 58, 49, 11, 34,
         13, 23, 30, 45, 63, 62,   38, 21, 31, 12, 14, 55,
         20, 47, 29, 54,  6, 15,    4,  5, 39, 53, 46, 22 },
     /* round 7 */
       { 52, 57, 11,  1, 26, 59,   10, 34, 44, 51, 25, 19,
          9, 41,  3,  2, 50, 35,   36, 43, 42, 33, 60, 18,
         28,  7, 14, 29, 47, 46,   22,  5, 15, 63, 61, 39,
          4, 31, 13, 38, 53, 62,   55, 20, 23, 37, 30,  6 },
     /* round 8 */
       { 36, 41, 60, 50, 10, 43,   59, 18, 57, 35,  9,  3,
         58, 25, 52, 51, 34, 19,   49, 27, 26, 17, 44,  2,
         12, 54, 61, 13, 31, 30,    6, 20, 62, 47, 45, 23,
         55, 15, 28, 22, 37, 46,   39,  4,  7, 21, 14, 53 },
     /* round 9 */
       { 57, 33, 52, 42,  2, 35,   51, 10, 49, 27,  1, 60,
         50, 17, 44, 43, 26, 11,   41, 19, 18,  9, 36, 59,
          4, 46, 53,  5, 23, 22,   61, 12, 54, 39, 37, 15,
         47,  7, 20, 14, 29, 38,   31, 63, 62, 13,  6, 45 },
     /* round 10 */
       { 41, 17, 36, 26, 51, 19,   35, 59, 33, 11, 50, 44,
         34,  1, 57, 27, 10, 60,   25,  3,  2, 58, 49, 43,
         55, 30, 37, 20,  7,  6,   45, 63, 38, 23, 21, 62,
         31, 54,  4, 61, 13, 22,   15, 47, 46, 28, 53, 29 },
     /* round 11 */
       { 25,  1, 49, 10, 35,  3,   19, 43, 17, 60, 34, 57,
         18, 50, 41, 11, 59, 44,    9, 52, 51, 42, 33, 27,
         39, 14, 21,  4, 54, 53,   29, 47, 22,  7,  5, 46,
         15, 38, 55, 45, 28,  6,   62, 31, 30, 12, 37, 13 },
     /* round 12 */
       {  9, 50, 33, 59, 19, 52,    3, 27,  1, 44, 18, 41,
          2, 34, 25, 60, 43, 57,   58, 36, 35, 26, 17, 11,
         23, 61,  5, 55, 38, 37,   13, 31,  6, 54, 20, 30,
         62, 22, 39, 29, 12, 53,   46, 15, 14, 63, 21, 28 },
     /* round 13 */
       { 58, 34, 17, 43,  3, 36,   52, 11, 50, 57,  2, 25,
         51, 18,  9, 44, 27, 41,   42, 49, 19, 10,  1, 60,
          7, 45, 20, 39, 22, 21,   28, 15, 53, 38,  4, 14,
         46,  6, 23, 13, 63, 37,   30, 62, 61, 47,  5, 12 },
     /* round 14 */
       { 42, 18,  1, 27, 52, 49,   36, 60, 34, 41, 51,  9,
         35,  2, 58, 57, 11, 25,   26, 33,  3, 59, 50, 44,
         54, 29,  4, 23,  6,  5,   12, 62, 37, 22, 55, 61,
         30, 53,  7, 28, 47, 21,   14, 46, 45, 31, 20, 63 },
     /* round 15 */
       { 26,  2, 50, 11, 36, 33,   49, 44, 18, 25, 35, 58,
         19, 51, 42, 41, 60,  9,   10, 17, 52, 43, 34, 57,
         38, 13, 55,  7, 53, 20,   63, 46, 21,  6, 39, 45,
         14, 37, 54, 12, 31,  5,   61, 30, 29, 15,  4, 47 },
     /* round 16 */
       { 18, 59, 42,  3, 57, 25,   41, 36, 10, 17, 27, 50,
         11, 43, 34, 33, 52,  1,    2,  9, 44, 35, 26, 49,
         30,  5, 47, 62, 45, 12,   55, 38, 13, 61, 31, 37,
          6, 29, 46,  4, 23, 28,   53, 22, 21,  7, 63, 39 }
    } ;

    private int invertKeySchedule( int bit, int round )
    {
       int i ;
       for ( i=0; i<keySchedule[round].length; i++ )
       {
          if ( keySchedule[round][i] == bit ) return i ;
       }
       return -1 ;
    }

    private int dualKey( int bit, int round )
    {
       int place = invertKeySchedule( bit, round ) ;
       if ( place < 0 ) return place ;
       return keySchedule[ keySchedule.length-round-1 ][place] ;
    }

    private int [] dualKeys( int bit, int [] a )
    {
        if ( a == null ) a = new int [ keySchedule.length ] ;
        for ( int round=0; round<keySchedule.length; round++ )
        {
            a[round] = dualKey( bit, round ) ;
        }
        return a ;
    }

    private void compact( int [] a )
    {
        /*  starting from the top of array a, remove duplicates
         *  by shifting array elements up. Fill bottom elements with -1
         */
        int i, j ;
        j = a.length-1 ;
        i = j-1 ;
        /* LI j points to last compacted element, i points to
           element to consider
         */
        while ( i>=0 )
        {
            if ( a[i] != a[j] ) a[--j] = a[i] ;
            i-- ;
        }
        while ( (--j) >= 0 ) a[j] = -1 ;
    }

    private void dualize( int [] bitsIn, int [] bitsOut )
    {
        int [] mergeBuffer = new int [ keySchedule.length * 2 ] ;
        int i ;
        /* Assert: mergeBuffer[i] == 0 */
        for ( i=0; i<bitsIn.length; i++ )
            if ( bitsIn[i]%8 != 0 )  // skip parity bits
            {
               dualKeys( bitsIn[i], mergeBuffer ) ;
               java.util.Arrays.sort( mergeBuffer );
               compact( mergeBuffer ) ;
            }
        int j = 0 ;
        for ( i=0; i< mergeBuffer.length; i++ )
        {
            if ( mergeBuffer[i]>0 ) bitsOut[j++] = mergeBuffer[i] ;
        }
        for ( j=j ; j < bitsOut.length; j++ )
            bitsOut[j] = 0 ;
    }

    public DualKeys()
    {
    }

    private void myPrint( String title, int [] a )
    {
       System.out.println(title) ;
       for ( int i=0; i<a.length; i++ )
         if ( a[i]>0 ) System.out.println( "  " + a[i] ) ;
      System.out.println() ;
    }

    public static void main(String[] args)
    {
      DualKeys dk = new DualKeys();
      int [] thePrimal = new int [64] ;
      int [] theDual = new int [64] ;

      thePrimal[0] = 1 ;
      dk.myPrint( "Primal 0", thePrimal ) ;
      dk.dualize( thePrimal, theDual );
      dk.myPrint( "Dual 0", theDual ) ;
      dk.dualize( theDual, thePrimal );
      dk.myPrint( "Primal 1", thePrimal ) ;
      dk.dualize( thePrimal, theDual );
      dk.myPrint( "Dual 1", theDual ) ;
      dk.dualize( theDual, thePrimal );
      dk.myPrint( "Primal 2", thePrimal ) ;

      for ( int i=0; i<thePrimal.length; i++ ) thePrimal[i] = 0 ;
      thePrimal[0] = 4 ;
      dk.myPrint( "Primal 0", thePrimal ) ;
      dk.dualize( thePrimal, theDual );
      dk.myPrint( "Dual 0", theDual ) ;
      dk.dualize( theDual, thePrimal );
      dk.myPrint( "Primal 1", thePrimal ) ;
      dk.dualize( thePrimal, theDual );
      dk.myPrint( "Dual 1", theDual ) ;
      dk.dualize( theDual, thePrimal );
      dk.myPrint( "Primal 2", thePrimal ) ;

    }
}