DES Revisited and the Shaft
DATELINE NOVEMBER, 2012: After 22 years of shuffling from court to court, venue to venue, jurisdiction to jurisdiction, the case of FoobarSoft vs. Stevens has finally been settled by the United States Supreme Court. It seems that in the year 1990, the time of the landmark decision where a columnist's opinion was no longer protected from claims of libel, Stevens was a victim of the common columnist's malady known as "pub lag." Unaware of the impending abridgement of the rights of columnists, and working with the columnist's usual four-month lead time, Stevens dutifully reported to his devoted readership that FoobarSoft's new Foobar C++ compiler had a small bug where the Foobar C++ Programmer's Chaise Lounge failed to allow the programmer to assign preferred ratios to the ingredients of the vodka_martini class. As a result, programmers were forced to overload, encapsulate, and polymorphize under the influence of two-parts vodka to one-part vermouth. Stevens went on to say that he was unable to maintain mental track of class hierarchies and networks with more than 3500 derived classes while under the influence of instantiated objects of the vodka_martini class. He expressed his strong opinion that programmers should be allowed to define drier martinis to taste, and he concluded that FoobarSoft C++ had a deficiency.
After the column was "in the can," as we say, but before the issue was in the hands of readers, the Supreme Court made their ruling. If the opinion of a columnist causes harm to someone and the opinion is not clearly factual, that person has been libeled and is entitled to redress.
Billy Ghoats, FoobarSoft's president, heard from a programmer in Bangor, Maine who said that because of Stevens's remarks, the programmer would delay his paradigm shift until all the compilers got all their ingredients right. Ghoats consulted his legal staff who advised him to sue Stevens for $195.53, the profits that FoobarSoft realize on each sale of the $200 C++ package. Wanting satisfaction as well as compensation, Ghoats also petitioned the court to allow him to scratch "C++" across Stevens's chest as punitive damages.
Now, after 22 years, the case has finally been settled. The many delays were a result of the court's heavy calendar which included the 7,532 lawsuits that were filed against Andy Rooney by food, soap, and cosmetic manufacturers immediately after the 1990 landmark ruling. The decision in the Stevens case was rendered by almost the same Supreme Court that made the original ruling. Chief Justice Wapner, who was appointed by President Quayle in 1998, read the opinion. The court unanimously ruled that Stevens's report of the FoobarSoft C++ behavior did not constitute libel because it was factual. However, calling the behavior a bug and a deficiency was, in the court's opinion, nonfactual and damaging to FoobarSoft, and so the plaintiff received an award in the amount originally requested. The punitive damages were waived because Stevens, now 72 and retired, wears only T-shirts collected over the years from software conferences and vendor-supplied reviewer's packages, and Ghoats was afraid Stevens would insist on wearing the rare and now-collectible "Foobar 'til your pointer drops!" edition given out at the 1995 FoobarSoft-Woodstock Grog and Granola Festival and subsequently banned in Berkeley.
The indulgence to which I just subjected you is not as far-fetched as it seems. The Supreme Court ruling really happened. We columnists and product reviewers better watch our step. How far can this new attitude reach? If I discuss a compiler, editor, or debugger in this column and do not like it, my opinion becomes lawyer fodder. If the program lacks features, is my opinion that the lack constitutes a deficiency factual or is it libel? Who will be the first to test it?
How far do the implications of this decision reach? Is this opinionated tirade of mine libelous to the Supreme Court itself? Wow! How'd you like to be sued by a bunch of Supreme Court justices?
In September I published a C implementation of the Data Encryption Standard (DES) algorithm. I built it from the National Bureau of Standards FIPS PUB 46 document which describes the algorithm. I lamented the lack of a validation suite of data that would allow me to determine if the algorithm would comply with the specification. Without one I plodded ahead anyway. The programs seemed to work. They did a dandy job of mangling a file beyond recognition and putting it back in a usable format again.
Richard Feezel, a reader, sent me a message on CompuServe saying that he had compared the output from my programs with that of a hardware board that implemented DES, and the results were different. He spent a good bit of time looking at the code and pointed out some likely problems. Richard did not have the DES document, so he couldn't tell where the code was going astray or if the board and my programs were just different implementations. Later he told me that he found public domain DES code and validation data on CompuServe. The DES hardware he was using passed the tests provided by the validation data.
That was good news. I really needed a validation data file. The DES code in the download was a bonus that turned out to be a life saver. You will remember that the DES algorithm involves a lot of loops of permutations of bit patterns. An implementor needs a sequence of data blocks that represent the interim steps that the algorithm takes. The input and output examples were helpful but only to tell if the program was working or failing. Nothing really points you to the particular place in the procedure where the first failure occurs. The DES algorithm goes into a loop where halves of a 64-bit data block are permuted, swapped, and mangled with a value derived from the key. The first error, no matter how small, is going to spread like a mushroom.
The big help came from the program that the validation data file accompanied. It is a public domain C program first implemented by James Gillogly and later modified by Phil Karn. You can find it on CompuServe as file DES.ARC in Data Library 3 of the IBMPRO forum. It is no doubt available on other BBSs and online services. The program, which was written some time ago, does not use ANSI C conventions but the authors have included a version that compiles with Turbo C, warnings and all.
By following the progress of the Gillogly/Karn program and comparing its results to those of my program, I was able to correct the problems. Because of the data permutations in DES, I was sure that my implementation of the structure of the algorithm was sound. It was encrypting and decrypting large files without losing any data. The problems had to do with the internal representations of data blocks causing the programs to permute differently than they should. And so they were, most of them. I cleared up most problems by using a swapbyte function that changes the byte order of a long integer from aabbccdd to ddccbbaa. The Gillogly/Karn program uses such a function but only in the Turbo C version. Apparently the byte/word architecture of the original machine does not order the bytes in the backward view of 8- and 16-bit machines that has plagued me ever since I first saw a PDP-11.
There were a few other problems. I was not rotating the key schedule output correctly. That was a bug that did not prevent the programs from encrypting and decrypting, but the encrypted data blocks were not compatible with the DES specification and probably not as secure.
David Dunthorn of Oak Ridge, Tennessee wrote that my observation about the 8-bit value being preserved in the encrypted file means that my DES code was not working correctly. How true. The behavior I saw was a byproduct of the other problems and led me to a false conclusion. Mr. Dunthorn provided data examples which can serve to test a DES implementation. Example 1 provides three of the examples he sent. The code in this month's column correctly processes these examples as well as that in the downloaded validation data and the other examples from Mr. Dunthorn.
Mr. Dunthorn continues:
The algorithm for DES is so interconnected that if a program does even a few examples correctly, it has a very high probability of being correct. A one bit change anywhere will yield an entirely different result, not something that is just a little bit off. . . . It is something of a challenge to get DES operating correctly even when working from the specification.
I'll say.
The DES specification says that the least significant bit of each byte of the key may be for a parity bit or whatever you want it to be, and so the algorithm ignores the least significant bit of the key. When my program's output did not match the output from the Gillogly/Karn program, I found that they were using the most significant bit for parity and I was not. The DES specification is not concerned with the implementation problems associated with such things as files and key parity. The specification addresses how you encrypt and decrypt 8-byte blocks of data with an 8-byte key. The parity code in the Gillogly/Karn program is in an outer shell that manages the files and key and calls the inner encryption and decryption code. The inner algorithms comply with the DES specification. From this I realized that different complying DES programs that encrypt and decrypt data files will not always be compatible. I added the odd parity logic to my program so that I could encrypt and decrypt files interchangeably between my program and the downloaded one to test the algorithm.
The documentation that came with the Gillogly/Karn program identified the DES Cipher Block Chaining (CBC) mode, something that is not addressed in the NBS 1977 FIPS PUB DES specification, although the program uses the CBC mode as a default. That had me going for a while. In the CBC mode, the previous ciphered block of 8 bytes is exclusive-orred with the current unencrypted block before the program encrypts the current block. The other mode, which bypasses the extra encryption, is the Electronic Code Book mode. That is the mode supported by my programs. The Gillogly/Karn program implements the CBC mode outside of the DES code, so that is another area where implementations will differ.
I mentioned in September that the DES algorithm has a shortcoming. Because it encrypts blocks of 8 bytes by mangling and scattering the bits all over the block, an encrypted file must necessarily have a length that is a multiple of 8 bytes. The DES algorithm has no way to know the actual length of that last block. In some applications the precise end-of-file location is critical to the use of the file. The Gillogly/Karn program records the length of the last block in the last byte of the file. If the file is an even multiple of 8 bytes, the algorithm adds a block with that information in it. This approach solves the problem, but it is not a part of the DES specification. As with the other external extensions, this solution produces a file format that would not be compatible with other implementations.
Probably the most significant difference between the two implementations is in their execution speed. The Gillogly/Karn program is faster. They do not implement all the permutations by using tables the way I did. Rather, to improve performance, they use certain characteristics of the table values to code some of the permutations with shifts and masks. The cost for those performance improvements is that the code is difficult to understand in places. Often I could not compare their interim results with mine because our approaches were different enough that there were no corresponding data patterns to compare.
The "C Programming" column is as much about C code as it is about algorithms, so I did not attempt to incorporate any of the Gillogly/Karn performance improvements. If I were using DES in a small file environment, such as an electronic mail application, I would probably use my programs because they would be easier for me to understand and maintain. For applications involving large files I would adapt the Gillogly/Karn algorithm to gain its performance benefits. Or I would search out some of the assembly language implementations that are even faster.
I changed the structure of the programs to isolate the DES algorithms from the code that manages the key and the files. You will find the corrected and modified DES programs here in Listing One, des.h (page 164), Listing Two, main.c (page 164), Listing Three, des.c (page 164), and Listing Four, tables.c (page 165). Compile and link everything into an executable program named "des.exe." Instead of separate encrypt and decrypt programs, such as we had in September, the des program handles both functions. You specify -e or -d as the first command line parameter to tell the program which operation to perform. The second parameter is the 8-byte key and the third and fourth parameters are the input and output filenames.
You can incorporate the DES functions into your own programs by including des.h and linking to des.c and tables.c. Call the initkey function with the address of your 8-byte key as an argument. Then call either the encrypt or decrypt function once for each 8-byte block in the data you want to encrypt or decrypt. Both functions accept a pointer to the 8-byte block where the input to and output from the algorithm will go.
A reader named Dave called to say that crypto.c, my first example of a simple encryption/decryption algorithm was not very good. It seems that he encrypted a file that had long strings of zero bytes. The crypto program encrypts and decrypts by simply exclusive-orring the 8-byte key with each successive 8-byte block of the data file. When the file has strings of zero bytes, the encrypted value is the key itself.
I designed crypto.c to encrypt ASCII electronic mail message text, which never has strings of zero-value bytes. I should have warned you about that particular behavior, however.
Another reader, Roberto Quijalvo of Plantation, Florida wrote to point out that if your ASCII text file has strings of spaces and the key is also ASCII text, the exclusive-or inserts the key into the text with a case change. That one never bit me because my ASCII files go through a run-length encoder, which truncates trailing white space from lines and compresses other runs of characters into escape sequences prior to encryption. That process was not for encryption, though, but for compression minimize transmission time.
Mr. Quijalvo contributed some code +to internally mangle the key. He says
A slight alteration in [the] code would make it more difficult to discover the key:
By checking the key for a character greater than 0x40 ('@') and changing any alpha character to a non-alpha character before using it, the key can be saved from experiencing such embarrassingly blatant exposure.
Francis Rocks of Berwyn, Pennsylvania reported the same problem and offered a different solution. Francis says,
A solution would be to eliminate hex 20 (blank) encoding with the following code replacing your second "while" construct:
All three readers thought that crypto.c was less secure than it ought to be, which it is if you use it outside of a controlled data environment such as the one I built the algorithm for.
These modifications are, of course, merely moves to beef up a simple algorithm whose original intent was only to momentarily divert the merely curious, which is the cause for encryption for most of us. In more hostile surroundings if the invader knows that the text is encrypted, he or she must discover the algorithm as well as the key. Because the exclusive-or algorithm is a common one, the appearance of any repeated pattern, even the mangled key, would tend to alert the spy to the possibility of exclusive-orring the entire message with different permutations of that pattern to see what would happen. Rocks's solution works only for the strings of spaces. But if a file has repeated strings of other values, fixed permutations of the key are going to be in there, and a codebreaker will exploit the patterns.
The crypto program was like a bicycle lock. It would deter the casual interloper, but the serious thief has the tools and skills to get past it. If you need to be that secure, you need something other than crypto.
Listing Five, page 166, and Listing Six, page 166, are encrypto.c and decrypto.c, two programs that eliminate the exposed key problems that crypto.c has with text files. I combined the run-length encoding algorithm of my text compresser and the encryption of the crypto.c program into these two programs. Besides encrypting and decrypting, they compress runs of duplicate characters into a simple escape se uence. The programs work only with ASCII text files.
The encrypto.c program translates any run of two or more duplicated characters into 2 bytes. The first byte is the count of the run with the most significant bit set on. The second byte is the duplicated character. Because the algorithm uses the most significant bit to identify a run-length counter, it works only with 7-bit ASCII files and will terminate if it finds a most significant bit set in the input file. After encrypto.c compresses the text, it encrypts it in blocks with lengths equal to that of the key's length. The compression and encryption are done in one pass of the file.
The decrypto.c program reverses the compression/encryption process. It decrypts the characters and then decompresses them.
The crypto.c program in September used a fixed-length key of 8 bytes. encrypto.c and decrypto.c take the key length that is entered and encrypt/decrypt blocks of that length.
I considered writing an identifying signature at the front of the encrypted file so that the decrypto.c program could verify that it was being asked to decrypt a properly encrypted file. I rejected this idea because an outsider who intercepted the file might then know which program encrypted it. I then considered encrypting the signature. I rejected that idea as well. A codebreaker who already knew the algorithm would then have a known data value from which to reverse-engineer the key.
While not immune to the attacks of a persistent codebreaker, the algorithms in encrypto.c and decrypto.c are more secure than those of the simpler crypto.c program from September and far less complex than those of DES.
_C PROGRAMMING COLUMN_
by Al Stevens
[LISTING ONE]DES Revisited
Example 1: Data examples for DES testing
Key: 0123456789ABCDEF 0123456789ABCDEF 0123456789ABCDEF
Text: 4E6F772069732074 68652074696D6520 666F7220616C6C20
Encr: 3FA40E8A984D4815 6A271787AB8883F9 893D51EC4B563B53
The CRYPTO Program
/* original code segment */
while (*cp1 && cp1 < argv [1]+8)
*cp2++ ^= *cp1++;
/* altered code segment */
while (*cp1 && cp1 < argv [1]+8)
*cp2++ ^=
(*cp1<0x41 ? *cp1++:
*cp1++ - 0x40);
while (*cp1 && cp1 < argv[1]+8) {
if (*cp2 != 0x20) {
*cp2++ ^=*cp1++;
}
else {
*cp2++;
*cp1++;
}
}
<a name="024b_0008">
/* -------------- des.h ---------------- */
/* Header file for Data Encryption Standard algorithms */
/* -------------- prototypes ------------------- */
void initkey(char *key);
void encrypt(char *blk);
void decrypt(char *blk);
/* ----------- tables ------------ */
extern unsigned char Pmask[];
extern unsigned char IPtbl[];
extern unsigned char Etbl[];
extern unsigned char Ptbl[];
extern unsigned char stbl[8][4][16];
extern unsigned char PC1tbl[];
extern unsigned char PC2tbl[];
extern unsigned char ex6[8][2][4];
<a name="024b_0009"><a name="024b_0009">
<a name="024b_000a">
[LISTING TWO]<a name="024b_000a">
/* Data Encryption Standard front end
* Usage: des [-e -d] keyvalue infile outfile
*/
#include <stdio.h>
#include <string.h>
#include "des.h"
static void setparity(char *key);
void main(int argc, char *argv[])
{
FILE *fi, *fo;
char key[9];
char blk[8];
if (argc > 4) {
strncpy(key, argv[2], 8);
key[8] = '\0';
setparity(key);
initkey(key);
if ((fi = fopen(argv[3], "rb")) != NULL) {
if ((fo = fopen(argv[4], "wb")) != NULL) {
while (!feof(fi)) {
memset(blk, 0, 8);
if (fread(blk, 1, 8, fi) != 0) {
if (stricmp(argv[1], "-e") == 0)
encrypt(blk);
else
decrypt(blk);
fwrite(blk, 1, 8, fo);
}
}
fclose(fo);
}
fclose(fi);
}
}
else
printf("\nUsage: des [-e -d] keyvalue infile outfile");
}
/* -------- make a character odd parity ---------- */
static unsigned char oddparity(unsigned char s)
{
unsigned char c = s | 0x80;
while (s) {
if (s & 1)
c ^= 0x80;
s = (s >> 1) & 0x7f;
}
return c;
}
/* ------ make a key odd parity ------- */
void setparity(char *key)
{
int i;
for (i = 0; i < 8; i++)
*(key+i) = oddparity(*(key+i));
}
<a name="024b_000b"><a name="024b_000b">
<a name="024b_000c">[LISTING THREE]<a name="024b_000c">
/* ---------------------- des.c --------------------------- */
/* Functions and tables for DES encryption and decryption
*/
#include <stdio.h>
#include <string.h>
#include "des.h"
/* -------- 48-bit key permutation ------- */
struct ks {
char ki[6];
};
/* ------- two halves of a 64-bit data block ------- */
struct LR {
long L;
long R;
};
static struct ks keys[16];
static void rotate(unsigned char *c, int n);
static int fourbits(struct ks, int s);
static int sixbits(struct ks, int s);
static void inverse_permute(long *op,long *ip,long *tbl,int n);
static void permute(long *op, long *ip, long *tbl, int n);
static long f(long blk, struct ks ky);
static struct ks KS(int n, char *key);
static void swapbyte(long *l);
/* ----------- initialize the key -------------- */
void initkey(char *key)
{
int i;
for (i = 0; i < 16; i++)
keys[i] = KS(i, key);
}
/* ----------- encrypt an 8-byte block ------------ */
void encrypt(char *blk)
{
struct LR ip, op;
long temp;
int n;
memcpy(&ip, blk, sizeof(struct LR));
/* -------- initial permuation -------- */
permute(&op.L, &ip.L, (long *)IPtbl, 64);
swapbyte(&op.L);
swapbyte(&op.R);
/* ------ swap and key iterations ----- */
for (n = 0; n < 16; n++) {
temp = op.R;
op.R = op.L ^ f(op.R, keys[n]);
op.L = temp;
}
ip.R = op.L;
ip.L = op.R;
swapbyte(&ip.L);
swapbyte(&ip.R);
/* ----- inverse initial permutation ---- */
inverse_permute(&op.L, &ip.L,
(long *)IPtbl, 64);
memcpy(blk, &op, sizeof(struct LR));
}
/* ----------- decrypt an 8-byte block ------------ */
void decrypt(char *blk)
{
struct LR ip, op;
long temp;
int n;
memcpy(&ip, blk, sizeof(struct LR));
/* -------- initial permuation -------- */
permute(&op.L, &ip.L, (long *)IPtbl, 64);
swapbyte(&op.L);
swapbyte(&op.R);
ip.R = op.L;
ip.L = op.R;
/* ------ swap and key iterations ----- */
for (n = 15; n >= 0; --n) {
temp = ip.L;
ip.L = ip.R ^ f(ip.L, keys[n]);
ip.R = temp;
}
swapbyte(&ip.L);
swapbyte(&ip.R);
/* ----- inverse initial permuation ---- */
inverse_permute(&op.L, &ip.L,
(long *)IPtbl, 64);
memcpy(blk, &op, sizeof(struct LR));
}
/* ------- inverse permute a 64-bit string ------- */
static void inverse_permute(long *op,long *ip,long *tbl,int n)
{
int i;
long *pt = (long *)Pmask;
*op = *(op+1) = 0;
for (i = 0; i < n; i++) {
if ((*ip & *pt) || (*(ip+1) & *(pt+1))) {
*op |= *tbl;
*(op+1) |= *(tbl+1);
}
tbl += 2;
pt += 2;
}
}
/* ------- permute a 64-bit string ------- */
static void permute(long *op, long *ip, long *tbl, int n)
{
int i;
long *pt = (long *)Pmask;
*op = *(op+1) = 0;
for (i = 0; i < n; i++) {
if ((*ip & *tbl) || (*(ip+1) & *(tbl+1))) {
*op |= *pt;
*(op+1) |= *(pt+1);
}
tbl += 2;
pt += 2;
}
}
/* ----- Key dependent computation function f(R,K) ----- */
static long f(long blk, struct ks key)
{
struct LR ir;
struct LR or;
int i;
union {
struct LR f;
struct ks kn;
} tr = {0,0}, kr = {0,0};
ir.L = blk;
ir.R = 0;
kr.kn = key;
swapbyte(&ir.L);
swapbyte(&ir.R);
permute(&tr.f.L, &ir.L, (long *)Etbl, 48);
tr.f.L ^= kr.f.L;
tr.f.R ^= kr.f.R;
/* the DES S function: ir.L = S(tr.kn); */
ir.L = 0;
for (i = 0; i < 8; i++) {
long four = fourbits(tr.kn, i);
ir.L |= four << ((7-i) * 4);
}
swapbyte(&ir.L);
ir.R = or.R = 0;
permute(&or.L, &ir.L, (long *)Ptbl, 32);
swapbyte(&or.L);
swapbyte(&or.R);
return or.L;
}
/* ------- extract a 4-bit stream from the block/key ------- */
static int fourbits(struct ks k, int s)
{
int i = sixbits(k, s);
int row, col;
row = ((i >> 4) & 2) | (i & 1);
col = (i >> 1) & 0xf;
return stbl[s][row][col];
}
/* ---- extract 6-bit stream fr pos s of the block/key ---- */
static int sixbits(struct ks k, int s)
{
int op = 0;
int n = (s);
int i;
for (i = 0; i < 2; i++) {
int off = ex6[n][i][0];
unsigned char c = k.ki[off];
c >>= ex6[n][i][1];
c <<= ex6[n][i][2];
c &= ex6[n][i][3];
op |= c;
}
return op;
}
/* ---------- DES Key Schedule (KS) function ----------- */
static struct ks KS(int n, char *key)
{
static unsigned char cd[8];
static int its[] = {1,1,2,2,2,2,2,2,1,2,2,2,2,2,2,1};
union {
struct ks kn;
struct LR filler;
} result;
if (n == 0)
permute((long *)cd, (long *) key, (long *)PC1tbl, 64);
rotate(cd, its[n]);
rotate(cd+4, its[n]);
permute(&result.filler.L, (long *)cd, (long *)PC2tbl, 48);
return result.kn;
}
/* rotate a 4-byte string n (1 or 2) positions to the left */
static void rotate(unsigned char *c, int n)
{
int i;
unsigned j, k;
k = ((*c) & 255) >> (8 - n);
for (i = 3; i >= 0; --i) {
j = ((*(c+i) << n) + k);
k = (j >> 8) & 255;
*(c+i) = j & 255;
}
if (n == 2)
*(c+3) = (*(c+3) & 0xc0) | ((*(c+3) << 4) & 0x30);
else
*(c+3) = (*(c+3) & 0xe0) | ((*(c+3) << 4) & 0x10);
}
/* -------- swap bytes in a long integer ---------- */
static void swapbyte(long *l)
{
char *cp = (char *) l;
char t = *(cp+3);
*(cp+3) = *cp;
*cp = t;
t = *(cp+2);
*(cp+2) = *(cp+1);
*(cp+1) = t;
}
<a name="024b_000d"><a name="024b_000d">
<a name="024b_000e">[LISTING FOUR]<a name="024b_000e">
/* --------------- tables.c --------------- */
/* tables for the DES algorithm
*/
/* --------- macros to define a permutation table ---------- */
#define ps(n) ((unsigned char)(0x80 >> (n-1)))
#define b(n,r) ((n>r||n<r-7)?0:ps(n-(r-8)))
#define p(n) b(n, 8),b(n,16),b(n,24),b(n,32),\
b(n,40),b(n,48),b(n,56),b(n,64)
#define q(n) p((n)+4)
/* --------- permutation masks ----------- */
unsigned char Pmask[] = {
p( 1),p( 2),p( 3),p( 4),p( 5),p( 6),p( 7),p( 8),
p( 9),p(10),p(11),p(12),p(13),p(14),p(15),p(16),
p(17),p(18),p(19),p(20),p(21),p(22),p(23),p(24),
p(25),p(26),p(27),p(28),p(29),p(30),p(31),p(32),
p(33),p(34),p(35),p(36),p(37),p(38),p(39),p(40),
p(41),p(42),p(43),p(44),p(45),p(46),p(47),p(48),
p(49),p(50),p(51),p(52),p(53),p(54),p(55),p(56),
p(57),p(58),p(59),p(60),p(61),p(62),p(63),p(64)
};
/* ----- initial and inverse-initial permutation table ----- */
unsigned char IPtbl[] = {
p(58),p(50),p(42),p(34),p(26),p(18),p(10),p( 2),
p(60),p(52),p(44),p(36),p(28),p(20),p(12),p( 4),
p(62),p(54),p(46),p(38),p(30),p(22),p(14),p( 6),
p(64),p(56),p(48),p(40),p(32),p(24),p(16),p( 8),
p(57),p(49),p(41),p(33),p(25),p(17),p( 9),p( 1),
p(59),p(51),p(43),p(35),p(27),p(19),p(11),p( 3),
p(61),p(53),p(45),p(37),p(29),p(21),p(13),p( 5),
p(63),p(55),p(47),p(39),p(31),p(23),p(15),p( 7)
};
/* ---------- permutation table E for f function --------- */
unsigned char Etbl[] = {
p(32),p( 1),p( 2),p( 3),p( 4),p( 5),
p( 4),p( 5),p( 6),p( 7),p( 8),p( 9),
p( 8),p( 9),p(10),p(11),p(12),p(13),
p(12),p(13),p(14),p(15),p(16),p(17),
p(16),p(17),p(18),p(19),p(20),p(21),
p(20),p(21),p(22),p(23),p(24),p(25),
p(24),p(25),p(26),p(27),p(28),p(29),
p(28),p(29),p(30),p(31),p(32),p( 1)
};
/* ---------- permutation table P for f function --------- */
unsigned char Ptbl[] = {
p(16),p( 7),p(20),p(21),p(29),p(12),p(28),p(17),
p( 1),p(15),p(23),p(26),p( 5),p(18),p(31),p(10),
p( 2),p( 8),p(24),p(14),p(32),p(27),p( 3),p( 9),
p(19),p(13),p(30),p( 6),p(22),p(11),p( 4),p(25)
};
/* --- table for converting six-bit to four-bit stream --- */
unsigned char stbl[8][4][16] = {
/* ------------- s1 --------------- */
14,4,13,1,2,15,11,8,3,10,6,12,5,9,0,7,
0,15,7,4,14,2,13,1,10,6,12,11,9,5,3,8,
4,1,14,8,13,6,2,11,15,12,9,7,3,10,5,0,
15,12,8,2,4,9,1,7,5,11,3,14,10,0,6,13,
/* ------------- s2 --------------- */
15,1,8,14,6,11,3,4,9,7,2,13,12,0,5,10,
3,13,4,7,15,2,8,14,12,0,1,10,6,9,11,5,
0,14,7,11,10,4,13,1,5,8,12,6,9,3,2,15,
13,8,10,1,3,15,4,2,11,6,7,12,0,5,14,9,
/* ------------- s3 --------------- */
10,0,9,14,6,3,15,5,1,13,12,7,11,4,2,8,
13,7,0,9,3,4,6,10,2,8,5,14,12,11,15,1,
13,6,4,9,8,15,3,0,11,1,2,12,5,10,14,7,
1,10,13,0,6,9,8,7,4,15,14,3,11,5,2,12,
/* ------------- s4 --------------- */
7,13,14,3,0,6,9,10,1,2,8,5,11,12,4,15,
13,8,11,5,6,15,0,3,4,7,2,12,1,10,14,9,
10,6,9,0,12,11,7,13,15,1,3,14,5,2,8,4,
3,15,0,6,10,1,13,8,9,4,5,11,12,7,2,14,
/* ------------- s5 --------------- */
2,12,4,1,7,10,11,6,8,5,3,15,13,0,14,9,
14,11,2,12,4,7,13,1,5,0,15,10,3,9,8,6,
4,2,1,11,10,13,7,8,15,9,12,5,6,3,0,14,
11,8,12,7,1,14,2,13,6,15,0,9,10,4,5,3,
/* ------------- s6 --------------- */
12,1,10,15,9,2,6,8,0,13,3,4,14,7,5,11,
10,15,4,2,7,12,9,5,6,1,13,14,0,11,3,8,
9,14,15,5,2,8,12,3,7,0,4,10,1,13,11,6,
4,3,2,12,9,5,15,10,11,14,1,7,6,0,8,13,
/* ------------- s7 --------------- */
4,11,2,14,15,0,8,13,3,12,9,7,5,10,6,1,
13,0,11,7,4,9,1,10,14,3,5,12,2,15,8,6,
1,4,11,13,12,3,7,14,10,15,6,8,0,5,9,2,
6,11,13,8,1,4,10,7,9,5,0,15,14,2,3,12,
/* ------------- s8 --------------- */
13,2,8,4,6,15,11,1,10,9,3,14,5,0,12,7,
1,15,13,8,10,3,7,4,12,5,6,11,0,14,9,2,
7,11,4,1,9,12,14,2,0,6,10,13,15,3,5,8,
2,1,14,7,4,10,8,13,15,12,9,0,3,5,6,11
};
/* ---- Permuted Choice 1 for Key Schedule calculation ---- */
unsigned char PC1tbl[] = {
p(57),p(49),p(41),p(33),p(25),p(17),p( 9),
p( 1),p(58),p(50),p(42),p(34),p(26),p(18),
p(10),p( 2),p(59),p(51),p(43),p(35),p(27),
p(19),p(11),p( 3),p(60),p(52),p(44),p(36),
p(0),p(0),p(0),p(0),
p(63),p(55),p(47),p(39),p(31),p(23),p(15),
p( 7),p(62),p(54),p(46),p(38),p(30),p(22),
p(14),p( 6),p(61),p(53),p(45),p(37),p(29),
p(21),p(13),p( 5),p(28),p(20),p(12),p( 4),
p(0),p(0),p(0),p(0)
};
/* ---- Permuted Choice 2 for Key Schedule calculation ---- */
unsigned char PC2tbl[] = {
p(14),p(17),p(11),p(24),p( 1),p( 5),p( 3),p(28),
p(15),p( 6),p(21),p(10),p(23),p(19),p(12),p( 4),
p(26),p( 8),p(16),p( 7),p(27),p(20),p(13),p( 2),
q(41),q(52),q(31),q(37),q(47),q(55),q(30),q(40),
q(51),q(45),q(33),q(48),q(44),q(49),q(39),q(56),
q(34),q(53),q(46),q(42),q(50),q(36),q(29),q(32)
};
/* ---- For extracting 6-bit strings from 64-bit string ---- */
unsigned char ex6[8][2][4] = {
/* byte, >>, <<, & */
/* ---- s = 8 ---- */
0,2,0,0x3f,
0,2,0,0x3f,
/* ---- s = 7 ---- */
0,0,4,0x30,
1,4,0,0x0f,
/* ---- s = 6 ---- */
1,0,2,0x3c,
2,6,0,0x03,
/* ---- s = 5 ---- */
2,0,0,0x3f,
2,0,0,0x3f,
/* ---- s = 4 ---- */
3,2,0,0x3f,
3,2,0,0x3f,
/* ---- s = 3 ---- */
3,0,4,0x30,
4,4,0,0x0f,
/* ---- s = 2 ---- */
4,0,2,0x3c,
5,6,0,0x03,
/* ---- s = 1 ---- */
5,0,0,0x3f,
5,0,0,0x3f
};
<a name="024b_000f"><a name="024b_000f">
<a name="024b_0010">[LISTING FIVE]<a name="024b_0010">
/* ---------------------- encrypto.c ----------------------- */
/* Single key text file encryption
* Usage: encrypto keyvalue infile outfile
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define FALSE 0
#define TRUE !FALSE
static void charout(FILE *fo, char prev, int runct, int last);
static void encrypt(FILE *fo, char ch, int last);
static char *key = NULL;
static int keylen;
static char *cipher = NULL;
static int clen = 0;
void main(int argc, char *argv[])
{
FILE *fi, *fo;
char ch, prev = 0;
int runct = 0;
if (argc > 3) {
/* --- alloc memory for the key and cipher blocks --- */
keylen = strlen(argv[1]);
cipher = malloc(keylen+1);
key = malloc(keylen+1);
strcpy(key, argv[1]);
if (cipher != NULL && key != NULL &&
(fi = fopen(argv[2], "rb")) != NULL) {
if ((fo = fopen(argv[3], "wb")) != NULL) {
while ((ch = fgetc(fi)) != EOF) {
/* ---- validate ASCII input ---- */
if (ch & 128) {
fprintf(stderr, "%s is not ASCII",
argv[2]);
fclose(fi);
fclose(fo);
remove(argv[3]);
free(cipher);
free(key);
exit(1);
}
/* --- test for duplicate bytes --- */
if (ch == prev && runct < 127)
runct++;
else {
charout(fo, prev, runct, FALSE);
prev = ch;
runct = 0;
}
}
charout(fo, prev, runct, TRUE);
fclose(fo);
}
fclose(fi);
}
if (cipher)
free(cipher);
if (key)
free(key);
}
}
/* ------- send an encrypted byte to the output file ------ */
static void charout(FILE *fo, char prev, int runct, int last)
{
if (runct)
encrypt(fo, (runct+1) | 0x80, last);
if (prev)
encrypt(fo, prev, last);
}
/* ---------- encrypt a byte and write it ---------- */
static void encrypt(FILE *fo, char ch, int last)
{
*(cipher+clen) = ch ^ *(key+clen);
clen++;
if (last || clen == keylen) {
/* ----- cipher buffer full or last buffer ----- */
int i;
for (i = 0; i < clen; i++)
fputc(*(cipher+i), fo);
clen = 0;
}
}
<a name="024b_0011"><a name="024b_0011">
<a name="024b_0012">[LISTING SIX]<a name="024b_0012">
/* ---------------------- decrypto.c ----------------------- */
/* Single key text file decryption
* Usage: decrypto keyvalue infile outfile
*/
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <process.h>
static char decrypt(FILE *);
static char *key = NULL;
static int keylen;
static char *cipher = NULL;
static int clen = 0, coff = 0;
void main(int argc, char *argv[])
{
FILE *fi, *fo;
char ch;
int runct = 0;
if (argc > 3) {
/* --- alloc memory for the key and cipher blocks --- */
keylen = strlen(argv[1]);
cipher = malloc(keylen+1);
key = malloc(keylen+1);
strcpy(key, argv[1]);
if (cipher != NULL && key != NULL &&
(fi = fopen(argv[2], "rb")) != NULL) {
if ((fo = fopen(argv[3], "wb")) != NULL) {
while ((ch = decrypt(fi)) != EOF) {
/* --- test for run length counter --- */
if (ch & 0x80)
runct = ch & 0x7f;
else {
if (runct)
/* --- run count: dup the byte -- */
while (--runct)
fputc(ch, fo);
fputc(ch, fo);
}
}
fclose(fo);
}
fclose(fi);
}
if (cipher)
free(cipher);
if (key)
free(key);
}
}
/* ------ decryption function: returns decrypted byte ----- */
static char decrypt(FILE *fi)
{
char ch = EOF;
if (clen == 0) {
/* ---- read a block of encrypted bytes ----- */
clen = fread(cipher, 1, keylen, fi);
coff = 0;
}
if (clen > 0) {
/* --- decrypt the next byte in the input block --- */
ch = *(cipher+coff) ^ *(key+coff);
coff++;
--clen;
}
return ch;
}