www.pudn.com > serpent.rar > serpent-reference.c
/*
$Id: serpent-reference.c,v 1.42 1998/06/10 13:50:31 fms Exp $
This is a reference implementation of the Serpent cipher invented by Ross
Anderson, Eli Biham, Lars Knudsen. It is written for the human reader
more than for the machine and, as such, it is optimised for clarity
rather than speed. ("Premature optimisation is the root of all evil.")
# This file is part of the C reference implementation of Serpent.
#
# Written by Frank Stajano,
# Olivetti Oracle Research Laboratory direction) {
case DIR_ENCRYPT:
switch (cipher->mode) {
case MODE_ECB:
encryptGivenKHat(input, key->KHat, output);
break;
case MODE_CBC:
for (i=0; i < WORDS_PER_BLOCK; i++) {
temp[i] = input[i] ^ ((WORD*) cipher->IV)[i];
}
encryptGivenKHat(temp, key->KHat, output);
for (i=0; i < WORDS_PER_BLOCK; i++) {
((WORD*) (cipher->IV))[i] = output[i];
}
break;
case MODE_CFB1:
/* We use cipher->IV as the shift register. New data comes in at
the LSB end and old data is dropped out of the MSB end. This
is what is traditionally called a "left shift", though in our
case we are actually shifting towards the right (MSB end)
since we store multiword quantities in little-endian
format.
The first bit of the plaintext to be encrypted is bit 0
(LSB). This is stored in bit 0 of the output ciphertext
block. Similarly, every bit of the plaintext is stored, after
encryption, in the corresponding bit of the output block.
Note that, due to the way it's called, this routine will
always encrypt an entire block, though in theory MODE_CFB1
could also encrypt a non-round number of bits. */
for (i=0; iIV), key->KHat, temp);
plainTextBit = getBit(input, i);
cipherTextBit = getBit(temp, BITS_PER_BLOCK-1) ^ plainTextBit;
setBit(output, i, cipherTextBit);
shiftBlockLeft((WORD*)(cipher->IV), cipherTextBit);
}
break;
default:
return BAD_CIPHER_MODE;
}
break;
case DIR_DECRYPT:
switch (cipher->mode) {
case MODE_ECB:
decryptGivenKHat(input, key->KHat, output);
break;
case MODE_CBC:
decryptGivenKHat(input, key->KHat, temp);
for (i=0; i < WORDS_PER_BLOCK; i++) {
output[i] = temp[i] ^ ((WORD*) cipher->IV)[i];
}
for (i=0; i < WORDS_PER_BLOCK; i++) {
((WORD*) cipher->IV)[i] = input[i];
}
break;
case MODE_CFB1:
/* The comments on the encryption side apply. See above. */
for (i=0; iIV), key->KHat, temp);
/* NB: yes, in CFB the cipher is used in encryption mode even
when decrypting. */
cipherTextBit = getBit(input, i);
plainTextBit = getBit(temp, BITS_PER_BLOCK-1) ^ cipherTextBit;
setBit(output, i, plainTextBit);
shiftBlockLeft((WORD*)(cipher->IV), cipherTextBit);
}
break;
default:
return BAD_CIPHER_MODE;
}
break;
default:
return BAD_KEY_DIR;
}
return TRUE;
}
/* -------------------------------------------------- */
/* Auxiliary bit-twiddling stuff */
void setBit(WORD x[], int p, BIT v) {
/* Set the bit at position 'p' of little-endian word array 'x' to 'v'. */
if (v) {
x[p/BITS_PER_WORD] |= ((WORD) 0x1 << p%BITS_PER_WORD);
} else {
x[p/BITS_PER_WORD] &= ~((WORD) 0x1 << p%BITS_PER_WORD);
}
}
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> (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);
}