serpent-reference.c

Diamond加密算法

BIT getBit(WORD x[], int p) {
  /* Return the value of the bit at position 'p' in little-endian word
     array 'x'. */

  return (BIT) ((x[p/BITS_PER_WORD] 
                 & ((WORD) 0x1 << p%BITS_PER_WORD)) >> p%BITS_PER_WORD);
}

/* They should all be just getBit, but no overloading in C... */
BIT getBitFromWord(WORD x, int p) {
  return (BIT) ((x & ((WORD) 0x1 << p)) >> p);
}
BIT getBitFromNibble(NIBBLE x, int p) {
  return (BIT) ((x & (0x1 << p)) >> p);
}

NIBBLE getNibble(WORD x, int p) {
  /* Return the nibble at position 'p' (in 0..7) in 'x'. */

  return (NIBBLE) (0xf & (x >> (p*BITS_PER_NIBBLE)));
}

NIBBLE makeNibble(BIT b0, BIT b1, BIT b2, BIT b3) {
  /* Return a nibble made of the given bits (b0 being the least significant). */

  return (NIBBLE) (b0 | (b1 << 1) | (b2 << 2) | (b3 << 3));
}

void xorBlock(BLOCK in1, BLOCK in2, BLOCK out) {
  /* Xor 'in1' and 'in2', yielding 'out'. */
  int i;
  for (i = 0; i < WORDS_PER_BLOCK; i++) {
    out[i] = in1[i] ^ in2[i];
  }
}

void applyPermutation(permutationTable t, BLOCK input, BLOCK output) {
  /* Apply the permutation defined by 't' to 'input' and return the result
     in 'output'. */

  int p;
  for (p=0; p<WORDS_PER_BLOCK; p++) {
    output[p] = 0;
  }
  for (p=0; p<BITS_PER_BLOCK; p++) {
    setBit(output, p, getBit(input, t[p]));
  }
}

void applyXorTable(xorTable t, BLOCK input, BLOCK output) {
  /* Apply the linear transformation defined by 't' to 'input', yielding
     'output'. Each bit in 'output' is the xor of the bits from 'input'
     given in the corresponding row of 't'. */

  int i, j;
  BIT b;
  for (i = 0; i < BITS_PER_BLOCK; i++) {
    b = 0;
    j = 0;
    while (t[i][j] != MARKER) {
      b ^= getBit(input, t[i][j]);
      j++;
    }
    setBit(output, i, b);
  }
}

NIBBLE S(int box, NIBBLE input) {
  /* Apply S-box number 'box' (0..31) to 'input', returning its output. */

  return SBox[box][input];
}

NIBBLE SInverse(int box, NIBBLE output) {
  /* Apply S-box number 'box' (0..31) in reverse to 'output', returning its
     input. */

  return SBoxInverse[box][output];
}

WORD rotateLeft(WORD x, int p) {
  /* Return word 'x' rotated left by 'p' places. The leftmost (i.e. most
     significant) 'p' bits fall off the edge and come back in from the
     other side. */
  return ((x << p) | (x >> (BITS_PER_WORD-p))) & 0xffffffff;
}

void shiftBlockLeft(BLOCK b, BIT in) {
  /* Return block 'b' shifted left by one place. The leftmost (i.e. most
     significant) bit falls off the edge and is lost, while bit 'in' is
     inserted at the rightmost (least significant) position to make up for
     it. */
  int i;
  for (i=WORDS_PER_BLOCK-1; i>0; i--) {
    b[i] <<= 1;
    setBit(&b[i], 0, getBit(&b[i-1], BITS_PER_WORD-1));
  }
  b[0] <<= 1;
  setBit(&b[0], 0, in);
}

/* -------------------------------------------------- */
/* Short key support */

void shortToLongKey(KEY key, int bitsInShortKey) {
  /* Take a short key (stored in key) and transform it (in place) into its
     long form (and write it to longKey). The number of significant bits in
     the supplied short key is given by bitsInShortKey. The caller is
     responsible for ensuring that all the remaining (most significant)
     bits in key from position bitsInShortKey upwards are 0 (as they should
     be anyway since key is declared to be WORDS_PER_KEY words long). */

  key[bitsInShortKey/BITS_PER_WORD] |= 
    ((WORD) 1) << (bitsInShortKey%BITS_PER_WORD);
}

/* -------------------------------------------------- */
/* Functions used in the formal description of the cipher */

void IP(BLOCK input, BLOCK output) {
  /* Apply the Initial Permutation to 'input', yielding 'output'. */
  applyPermutation(IPTable, input, output);
}

void FP(BLOCK input, BLOCK output) {
  /* Apply the Final Permutation to 'input', yielding 'output'. */
  applyPermutation(FPTable, input, output);
}

void IPInverse(BLOCK output, BLOCK input) {
  /* Apply the Initial Permutation in reverse to 'output', yielding 'input'. */
  applyPermutation(FPTable, output, input);
}

void FPInverse(BLOCK output, BLOCK input) {
  /* Apply the Final Permutation in reverse to 'output', yielding 'input'. */
  applyPermutation(IPTable, output, input);
}

void SHat(int box, BLOCK input, BLOCK output) {
  /* Apply a parallel array of 32 copies of S-box number 'box' to 'input',
     yielding 'output'. */
  int iWord, iNibble;
  for (iWord = 0; iWord < WORDS_PER_BLOCK; iWord++) {
    output[iWord] = 0;
    for (iNibble = 0; iNibble < NIBBLES_PER_WORD; iNibble++) {
      output[iWord] |= ((WORD) S(box, getNibble(input[iWord], iNibble)))
                        << (iNibble*BITS_PER_NIBBLE);
    }
  }
}

void SHatInverse(int box, BLOCK output, BLOCK input) {
  /* Apply, in reverse, a parallel array of 32 copies of S-box number 'box'
     to 'output', yielding 'input'. */
  int iWord, iNibble;
  for (iWord = 0; iWord < WORDS_PER_BLOCK; iWord++) {
    input[iWord] = 0;
    for (iNibble = 0; iNibble < NIBBLES_PER_WORD; iNibble++) {
      input[iWord] |= ((WORD) SInverse(box, getNibble(output[iWord], iNibble)))
                        << (iNibble*BITS_PER_NIBBLE);
    }
  }
}

void LT(BLOCK input, BLOCK output) {
  /* Apply the table-based version of the linear transformation to 'input',
     yielding 'output'. */

  applyXorTable(LTTable, input, output);
}

void LTInverse(BLOCK output, BLOCK input) {
  /* Apply, in reverse, the table-based version of the linear
     transformation to 'output', yielding 'input'. */

  applyXorTable(LTTableInverse, output, input);
}

void R(int i, BLOCK BHati, keySchedule KHat, BLOCK BHatiPlus1) {
  /* Apply round 'i' to 'BHati', yielding 'BHatiPlus1'. Do this using the
    appropriately numbered subkey(s) from 'KHat'. NB: it is allowed for
    BHatiPlus1 to point to the same memory as BHati. */

  BLOCK xored, SHati;

  xorBlock(BHati, KHat[i], xored);
  SHat(i, xored, SHati);
  if ( (0 <= i) && (i <= r-2) ) {
    LT(SHati, BHatiPlus1);
  } else if (i == r-1) {
    xorBlock(SHati, KHat[r], BHatiPlus1);
  } else {
    printf("ERROR: round %d is out of 0..%d range", i, r-1);
    exit(1);
    /* Printf and exit is disgusting--if we were programming in a sensible
       language, we'd have exceptions. Shall I make the code less readable
       with ugly return codes that no caller ever checks anyway?
       Naaah... */
  }

#ifdef SHOW_INTERNALS
  printf("R[%d]", i);
  render("=", BHatiPlus1, WORDS_PER_BLOCK);
#endif
}

void RInverse(int i, BLOCK BHatiPlus1, keySchedule KHat, BLOCK BHati) {
  /* Apply round 'i' in reverse to 'BHatiPlus1', yielding 'BHati'. Do this
    using the appropriately numbered subkey(s) from 'KHat'. NB: it is
    allowed for BHati to point to the same memory as BHatiPlus1. */

  BLOCK xored, SHati;

  if ( (0 <= i) && (i <= r-2) ) {
    LTInverse(BHatiPlus1, SHati);
  } else if (i == r-1) {
    xorBlock(BHatiPlus1, KHat[r], SHati);
  } else {
    printf("ERROR: round %d is out of 0..%d range", i, r-1);
    exit(1);
  }
  SHatInverse(i, SHati, xored);
  xorBlock(xored, KHat[i], BHati);

#ifdef SHOW_INTERNALS
  printf("Rinv[%d]", i);
  render("=", BHati, WORDS_PER_BLOCK);
#endif
}



void makeSubkeysBitslice(KEY userKey, keySchedule K) {
  /* Given 'userKey' (shown as K in the paper, but we can't use that name
     because of a collision with K[i] used later for something else),
     produce the array 'K' of 33 128-bit subkeys. */

  int i, j, l, whichS;
  NIBBLE input, output;
  WORD k[132], raw_w[140];
  /* The w array, in the notation of the paper, is supposed to span the
     range -8..131. But we can't have negative array indices in C. NOTE
     that this is a typical place where one can make trivial mistakes in
     the implementation when setting j = i+8 and so on (I know -- I did
     too).  So what do I do here? My little hack (all for the sake of
     readability) is to define a raw_w array in the range 0..139 and to
     make a "proper" w alias on top of that by starting from the 8th
     element, so that w[i] is redirected to raw_w[i+8], which works for i
     in -8..131. */
  WORD* w = &raw_w[8];

  /* "We write the key as 8 32-bit words w-8 ... w-1" */
  for (i = -8; i < 0; i++) {
    w[i] = userKey[i+8];
  }

  /* "We expand these to a prekey w0 ... w131 with the affine recurrence" */
  for (i = 0; i < 132; i++) {
    w[i] = rotateLeft(w[i-8] ^ w[i-5] ^ w[i-3] ^ w[i-1] ^ phi ^ i, 11);
  }

  /* The round keys are now calculated from the prekeys using the S-boxes
     in bitslice mode. */
  for (i = 0; i < r+1; i++) {
    whichS = (r + 3 - i) % r;
    k[0+4*i] = k[1+4*i] = k[2+4*i] = k[3+4*i] = 0;
    for (j = 0; j < 32; j++) {
      input = makeNibble(getBitFromWord(w[0+4*i], j),
                         getBitFromWord(w[1+4*i], j),
                         getBitFromWord(w[2+4*i], j),
                         getBitFromWord(w[3+4*i], j));
      output = S(whichS, input);
      for (l = 0; l < 4; l++) {
        k[l+4*i] |= ((WORD) getBitFromNibble(output, l)) << j;
      }
    }
  }

  /* We then renumber the 32 bit values k_j as 128 bit subkeys K_i. */
  for (i = 0; i < 33; i++) {
    for (j = 0; j < 4; j++) {
      K[i][j] = k[4*i+j];
    }
#ifdef SHOW_INTERNALS
    printf("SK[%d]", i);
    render("=", K[i], WORDS_PER_BLOCK);
#endif
  }
}


void makeSubkeys(KEY userKey, keySchedule KHat) {
  /* Given 'userKey' (shown as K in the paper, but we can't use that name
     because of a collision with K[i] used later for something else),
     produce the array 'KHat' of 33 128-bit subkeys. */

  int i;
  keySchedule K;

#ifdef SHOW_INTERNALS
  render("LONG_KEY=", userKey, WORDS_PER_KEY);
#endif

  makeSubkeysBitslice(userKey, K);

  /* We now apply IP to the round key in order to place the key bits in the
     correct column. */
  for (i = 0; i < 33; i++) {
    IP(K[i], KHat[i]);

#ifdef SHOW_INTERNALS
    printf("SK^[%d]", i);
    render("=", KHat[i], WORDS_PER_BLOCK);
#endif
  }

}


void encryptGivenKHat(BLOCK plainText, keySchedule KHat, BLOCK cipherText) {
  /* Encrypt 'plainText' with 'KHat', using the normal (non-bitslice)
     algorithm, yielding 'cipherText'. */

  BLOCK BHat;
  int i;

  IP(plainText, BHat);
  for (i = 0; i < r; i++) {
    R(i, BHat, KHat, BHat);
  }
  FP(BHat, cipherText);
}

void decryptGivenKHat(BLOCK cipherText, keySchedule KHat, BLOCK plainText) {
  /* Decrypt 'cipherText' with 'KHat', using the normal (non-bitslice)
     algorithm, yielding 'plainText'. */

  BLOCK BHat;
  int i;

  FPInverse(cipherText, BHat);
  for (i = r-1; i >=0; i--) {
    RInverse(i, BHat, KHat, BHat);
  }
  IPInverse(BHat, plainText);
}