Hacks, Spooks, and Data Encryption
The lexicon keeps mutating. In days gone by "hackers" were honored souls who rummaged in the innards of computer systems finding clever and tricky ways to do things within the bounds of official sanction. A good algorithm was called a "good hack." A generation of computer invaders and the media have likewise pilfered the word so that now a hacker is someone who steals computer time and information. This column is about how the hackers of yore can protect their users from the new generation of punk hackers. We'll discuss the basics of data encryption and implement two encryption algorithms in C.
I just finished reading The Cuckoo's Egg by Clifford Stoll (1989, Doubleday). It's not about C (although C is mentioned and Unix is a major player), but all programmers will enjoy and relate to the true story about a mysterious computer break-in artist and the programmer who relentlessly sniffed out the devious interloper's location and identity. It's a compelling book. Plan enough time to read it in one sitting because you'll need it. Stoll is the programmer, and he writes about how a seemingly mundane assignment to find a 75 cent discrepancy in his employer's computer accounting system turned into a one year trek through the holes in Unix and VMS, the careless neglect and ignorance that most system managers have about system security, and the mindless, motionless bureaucracies of federal law enforcement and intelligence agencies.
You will learn from this book about computer pirates and how they routinely gain unauthorized access to computer systems by finding the unlocked back doors and unplugged holes. You'll also learn how the computers of government, universities, and research centers are linked together in complex networks by Tymnet and other communications services. And, if you've never worked inside your government, you'll gain from Stoll's novitiate insight into the bewildering and confounding nature of Potomac fever and lethargy. Character development is weak, and some of the dialogue is obviously contrived to explain things, but the book is loaded with suspense, and you will not want to put it down.
Reading The Cuckoo's Egg brings us to the subject of data encryption. Data encryption means that you take some entity of data that has meaning in its original form and mangle it beyond recognition so that unauthorized peeping persons can neither understand nor use it. Later, you or someone who has authorized access to the information can unscramble it and use it. The idea, of course, is to scramble it in a way known only to those of the inner sanctum. The stuff of spies.
Computer-aided encryption involves at the very least an algorithm and often much more. The complexity of your encryption scheme will depend on the measure of protection you require or your level of paranoia, whichever is greater. For a well-developed treatment of the various techniques of encryption, see "Cloak and Data" by Rick Grehan in Byte Magazine, June 1990.
The other side of encryption is decryption. Usually, but not always, you need to decrypt something in order to use it. When would you not? The sign-on password is an example. When you select a password for access to a system, the computer will often encrypt it before it records it, forgetting the original. The encryption algorithm is designed so that no one can derive the original password from its encrypted form. If someone gets hold of the password file, they cannot use its contents to sign onto someone else's account. When you sign on, the system encrypts the password you enter and compares it to what is stored. This approach prevents the system from making a permanent record of passwords.
Stoll compared such password encryption schemes to sausage grinders. You can't run the ground meat backwards through the grinder and get a sausage. And so he wondered why his ersatz user kept downloading the useless password files. Later he learned that the Unix-encryption algorithm is common knowledge, and his anonymous burglar had used the algorithm to encrypt all the words in an English spelling dictionary. He would compare the downloaded encrypted passwords with the ones from his dictionary and thus learn the passwords of those users who innocently selected English words.
There are some very practical uses for data encryption in the world of shared computers. Every complex system must have a superuser, a system manager, a supervisor account, or whatever, so that the systems programmers can maintain the operating system. Some other users -- users of applications -- are responsible for information so sensitive that it must not be seen by others, not even the system supervisor. Payroll records, cost proposals, hostile takeover bids, employee health records, and such are all compartmentalized information to be viewed only by those who have the need to know.
Many successful unauthorized system penetrations involve the perpetrator's ability to gain superuser status through knowledge of a bug in the system. With that status, all the files and programs are wide open to the spook. Encryption adds one more level of protection against inquiring minds.
Electronic mail is a hot new item among local and wide area networks. With all that text roaming around all those systems with so many varied degrees of protection and privilege, there is always a potential for that confidential memo, love letter, or football pool to be seen by the wrong eyes. Trouble usually follows.
As an example, the Novell network provides a measure of protection by allowing the system supervisor to grant read and write privileges to users at the network subdirectory level. If the system is properly configured, I can write to your mail subdirectory but I cannot read it. I can read the subdirectory where the software is stored but I cannot write it. I can read and write to my own mail subdirectory. When mail leaves my local area network to go to someone somewhere else, I must depend on the integrity of that remote site to similarly protect my precious data from prying eyes. Let's make the absurd assumption that all systems are secure and that all system supervisors are trustworthy. Is there a back door into this scheme of protection, one that would admit an intruder? Of course there is.
Novell network applications exchange messages between networks by using a delivery agent program called the Message Handling Service (MHS). MHS has become a standard, and because of its acceptance, other platforms such as MCI Mail and CompuServe have or are developing gateway processes that exchange messages between themselves and MHS installations. Big stuff. Now suppose that you and I are common, unprivileged users on a network that uses MHS and I want to intercept your incoming mail. Our network has a hub name and password that the MHS administrator assigns. The hubs call one another and use those data elements to identify and verify one another. All I need to do to get your mail is set up another system, assign it our hub name and password and have it connect to the guys who send stuff to you. How do I learn the hub's password? Simple. MHS records it in the public directory file that everyone can read. Dumb. But typical. And reason enough to consider adding encryption to our message exchanging systems.
Usually you encrypt a file by specifying a key value to the encrypting algorithm. The intended receiver of the file must know the key value in order to decrypt and use the data. This often presents a dilemma. If you want to remember only one key -- mind, you mustn't write it down or keep it in a file -- but have a lot of people to send mail to, then every one of them must know your key. The more of them there are, the greater potential there is for compromise and the less substantial the protection. If you exchange mail with a lot of people who do not know your key, then you need to remember all their keys. Although propriety prevents you from making any kind of permanent record, no one can remember so many keys, and the stuff gets written down somewhere.
A better scheme for encryption in electronic mail systems involves two keys, a public one and a private one. Your public key is known to everyone and only you know the private one. On the other hand you know the public keys of the other users. The public key is a function of the private key, and like the password discussed above, one cannot usually reverse-engineer the private key from the public one. Everyone sends things to you that are encrypted with the public key. But only the private key can decrypt the messages. You need to remember only one key for yourself, and you can record the public keys of your correspondents wherever you like, even in your electronic mail address book. Grehan's article in Byte explains several algorithms for developing a two-key encryption system.
In one-on-one exchanges, a single key system seems to work better. You and your pen pal know the key, and no one else does. You freely exchange encrypted messages. When it is necessary, the two of you agree to change the key.
Listing One, page 147, is crypto.c, an implementation of a small encryption algorithm. It's all the encryption most of us would ever need. Unless you are in a really hostile environment where highly sensitive records are kept, encryption usually serves only to keep the curious honest. In Stoll's book, although the intruder tried for a year to get at something classified, he never did. The lax security he consistently found allowed him to purloin only from unclassified systems.
CRYPTO reads a key word and two filenames from the command line. If you run the program against an encrypted file, CRYPTO decrypts it. The algorithm is simple. The program reads the input file in 64-bit blocks, does an exclusive OR of the block and the keyword, and writes the block to the output file. To decrypt the encrypted file, you run it against the same CRYPTO program by using the same password.
To the uninitiated, the encrypted file seems to contain random byte values. Even if a snooper has the CRYPTO program, without the keyword the file is useless. This algorithm is much better than a simple character substitution encryption scheme because each character's modification is a function of its position in the 8-byte block and the corresponding character in the keyword. This technique is not immune to code-breaking techniques, but it will keep your code-breaker busy for a while. Encryption sometimes serves its purpose if it merely delays when the information goes public. If your message says, "We attack at high noon," who cares if the code-breakers figure it out by 1 P.M.?
The government has sanctioned a standard algorithm for single-key encryption called the Data Encryption Standard (DES). You can get a copy of the standard from most government libraries by requesting the Federal Information Processing Standards Publication (FIPS PUB) 46. The algorithm is complex, and FIPS PUB 46 is not the clearest documentation you'll ever read. I'll try to explain it better and at the same time demonstrate it with C programs that implement the algorithm.
DES encrypts data 64 bits at a time. It mangles the 64 bits by way of a several-step algorithm that includes a 64-bit key value supplied by the user. The standard specifies a key of eight 8-bit bytes and does not use the most significant bit of each byte in the key, reserving that as a parity bit if needed.
DES works with bit strings and refers to bit 1, bit 2, and so on. You have to read the standard carefully all the way through to determine that bit 1 is the most significant bit of an 8-bit byte or of a 64-bit block and that bit numbers read from left to right. They are unspecific about the integer and long integer configuration of the architecture, so you must be careful about the last-byte-first view of data in most 16- and 32-bit machines.
The encryption algorithm works on the data file in 64-bit blocks. It begins by rearranging the bits in the block according to an initial permutation table. Then it separates the block into two 32-bit halves, a left half and a right half. There are 16 iterations of a mangling process designed to mutate the data beyond recognition with the key playing a major part. The result of these iterations is a final pair of 32-bit halves. The algorithm permutes this 64-bit block by using a permutation table that is the inverse of the initial permutation table. The output from this permutation is the encrypted 64-bit block. An interesting property of this inverse permutation is that if your input file does not use the most significant eighth bit, neither will the encrypted file. This means that if you transmit ASCII text data files over serial lines with 7-bit data byte communications protocols, your encrypted files will transmit correctly.
That seems simple enough. Now things begin to get complicated. The 16 iteration data-mangling process goes like this:
For each iteration, the left half of the block is exclusive ORed with the 32-bit output of a function called f. Then, except for the sixteenth iteration, the halves are exchanged. That's not so bad. Now let's consider the f function, which is appropriately named.
The f function takes the 32-bit right half of the block and the 48-bit output of the KS (key schedule) function as its arguments. The right half is called "R." The function permutes the 32 bits of R into 48 bits. This permutation is called "E," and it is exclusive ORed with the 48-bit output from the KS function. The 48-bit result is then segmented into eight 6-bit values. The S function compresses each of these a 4-bit value. The eight 4-bit values combine into one 32-bit value, which is then permuted through a permutation table called "P." That permuted value is the output from the f function. Whew.
The S function consists of eight different subfunctions (S1, S2, S3 ...) depending on whether it is compressing the first, second, third, etc. 6-bit block. There are eight tables, one for each subfunction. The tables are arrays of two dimensions with 4 columns and 16 rows. Each entry in the array contains a value between 0 and 15 representing the 4-bit compressed representation of the 6-bit input. The 6-bit value to be compressed provides the array subscripts in this bizarre manner: Bits 1 and 6 combine to be the row subscript 0 - 3. Bits 2 - 5 are the column subscript 0 - 15. The S function returns the 4-bit value taken from the proper array as the result of these subscripts. We're not done yet.
The KS function returns a 48-bit value based on the 64-bit key. Its arguments are the iteration number of the 16 iterations discussed earlier and the key value for the encryption. For the first iteration, the function permutes the key value by using the Permuted Choice 1 table. The key divides into two halves and these halves are each shifted one or two bits to the left depending on which iteration is running. A table controls the shift values. Each iteration after the first uses the shifted value of the previous iteration as its input, does its own shift, and then permutes the value once more by using the Permuted Choice 2 table.
Decryption reverses the encryption procedure. Because the initial and inverse-initials permutations are reciprocal, the decryption steps are the same except that the decryption reverses the half exchanges during the iterations and uses the permuted key values returned by the KS function in the reverse order of that used by encryption.
Listing Two, page 147, is des.h, the header file that defines the global formats, function prototypes, and external data names. The file also defines the preprocessor macros that the program uses to build permutation tables. See the discussion on permutations later for an explanation of these macros.
Listing Three, page 147, is encrypt.c, the program that scrambles a data file. You run it by entering the keyword, which should be eight characters, the name of the input file and the name of the encrypted output file. The program reads the file 64 bits at a time and encrypts those 64 bits with the DES algorithm. It permutes the input with the initial permutation table and does the 16 iterations of right- and left-half exchanges and key-dependent block modifications. Then it uses the inverse initial permutation table to permute the output.
Note that the program computes the 16-key schedules into an array at the beginning of the program. These values are constant for the entire process and do not need to be recomputed for every iteration that uses them.
The output file will always be an even multiple of 8 bytes. This is necessary because the encryption process scrambles in 64-bit chunks.
Listing Four, page 148, is decrypt.c, which is similar to encrypt.c except that it reverses the order of right-left exchanges and fetches from the key schedule array. The decrypted file is the length of the encrypted file, an even multiple of 8 bytes with the excess bytes padded with zeros. This padding could be a problem, particularly with files of fixed format where an application appends records. If this is the case, you could modify the encryption program to write a control value as part of the encrypted file. The value would specify the length of the original data file. You can modify the decryption program to use this value to truncate the excess bytes in the decrypted file. You could decide to bypass encrypting the last block if it is less than 8 bytes. Beware, though. If the user's message to his boss's secretary ends with "Love, Ed", there might be some explaining due.
Listing Five, page 148, is des.c, which contains the DES functions. I explained most of them in the discussion on the algorithms. The terse function names f, S, and KS come from the DES specification. The discussion on permutations that follows explains the permute and inverse_permute functions. The sixbits function might need some explanation. Its purpose is to extract and return a 6-bit value from within a 48-bit block. None of this is readily supported by the typical 8- and 16-bit architectures most of us use, so the sixbits function uses a brute force method. A table named "ex6" contains an entry for each of the eight 6-bit values. Each entry identifies the 2 bytes that contain the spread of 6 bits. One element specifies the number of bits to shift the byte left and another specifies the number to shift right. Those two elements are mutually exclusive. Another element specifies the mask for ANDing off the excess bits.
Listing Six, page 149, is tables.c. I put the tables into a separate source file because they compile so slowly. The next discussion explains why.
I have mentioned the various permutations that DES performs. A permutation of a data block consists of rearranging the bits into a specified order. The DES specification provides tables that identify what the permuted order of the bits will be for each permutation. There are several ways that you could implement such permutations in C. I built an array of bit masks for each of the 64 bits in a permutation. Each array entry contains a 64-bit value with one bit set on. Its position in the table associates it with the bit that it will change. So, if the third table entry has its fifth bit set, then the permuted output will have its fifth bit set only if the input has its third bit set. For testing the 64 input bit positions, I built a general-purpose table with the bits set in ascending order -- the first bit is set in the first entry, the second in the second, and so on. Some of this could be done more efficiently in assembly language with shifts and carry tests. The C language as implemented on the PC, however, does not have a convenient 64-bit shift operator. Consequently I chose the bit test mask and bit set mask approach described here.
To make building the bit masks easier and reduce the potential for transcription errors, I developed the preprocessor macros in DES.H. By coding the p(n) macro with a number between 1 and 64 as its argument, you tell the preprocessor to define a comma-separated set of eight integral values with seven of them of value 0 and one of them having a value with a single bit (1, 2, 4, 8, 0x10, 0x20, 0x40, or 0x80) set. The value 1 sets the left-most bit of the left-most byte. Subsequent ascending values set the next sequential bit to the right. The p(n) expressions can then be coded into the initializers for a character array.
By using this technique, I was able to lift the permutation table values directly out of the DES standard document and code them into the p(n) expressions. Observe the macros. When you code a p(n) expression, it expands to eight calls to the b(n,r) macro, one for each byte in the 64-bit mask. The r argument identifies which of the 8 bytes the b(n,r) macro expands. The macro uses that value to test the range of the n argument to see if its corresponding bit falls within the byte. If not, the expression expands to a zero value for the byte. If so, the macro calls the ps(n) macro passing an argument in the range 1 - 8 that is computed from the n and r arguments to the b(n,r) macro. The ps(n) macro expands the byte to a value with a single bit shifted into the correct position.
This exercise illustrates the power of the C preprocessor. By coding these macros I am able to express the permutation tables with more readable language and less margin for error. But there is a cost. There are several of those tables in the program, and all that preprocessor activity slows a 20-MHz 386 to a crawl when the tables.c file compiles. The first time it happened, I thought that Turbo C had hung up.
The DES algorithm is complex and slow. The ENCRYPT program published here takes one minute, ten seconds to encrypt the text of this column, about 25K bytes, and the DECRYPT program uses the same time to decrypt it. I made these measures on a 20-MHz 386 with Turbo C 2.0 for the compiler. By comparison, the simpler CRYPTO program takes about 3.5 seconds to perform the same task. The poor showing of the DES programs could reflect a bad implementation (who, me?) or a non-optimum compile. I haven't tried it on a 4.77-MHz PC. Pack a lunch and bring a toothbrush.
The algorithms in DES.C assume a 32-bit long integer and an 8-bit byte. I used the PC's long integer to implement the halves of the 64-bit key and data block because it was convenient and offered the best chance for efficiency. A more portable program would adapt itself to the correct integral data type for the compiler and might not work as well. Perhaps the permutation functions could be optimized. A profiler will show that those functions occupy most of the algorithm's time. Optimization would, though, be compiler-dependent. You can look at the 64 iterations of the permute function and decide to use subscripts instead of pointers, or use 64 discrete in-line bit tests and ORs to avoid the loop overhead. Code it one way or another, and the program's performance could improve or degrade depending on the C compiler you use.
Because DES is defined by the National Bureau of Standards, a truly conforming device or program must be validated, and these programs have not been tested and blessed. My copy of the standard does not identify the validation procedures. Perhaps a good test would be to see if a candidate implementation can successfully exchange encrypted files with an approved device. The specification implies, however, that an implementer has some leeway in the design of the various permutation tables. If this is so, then the encrypted files would not be compatible between different implementations.
Farewell to Howard Benner, the author of TAPCIS. I never met Howard, but I use his work every day. So do many others. Howard was a programmer in a relatively new craft, one that is only about 40 years old. When I began programming 32 years ago, the programmers were all young, too, and there were not very many of us. I still think of us all as young people. It does not seem right somehow that programmers should die.
_C PROGRAMMING COLUMN_
by Al Stevens
[LISTING ONE]Data Encryption
One- and Two-Key Encryption
CRYPTO
Data Encryption Standard
Encryption with DES
Decryption with DES
ENCRYPT and DECRYPT
DES Permutations
DES Performance
Epilogue
<a name="01e8_000f">
/* ---------------------- crypto.c ----------------------------- */
/*
* Simple, single key file encryption/decryption filter
* Usage: crypto keyvalue infile outfile
*/
#include <stdio.h>
#include <string.h>
void main(int argc, char *argv[])
{
FILE *fi, *fo;
int ct;
char ip[8];
char *cp1, *cp2;
if (argc > 3) {
if ((fi = fopen(argv[2], "rb")) != NULL) {
if ((fo = fopen(argv[3], "wb")) != NULL) {
while ((ct = fread(ip, 1, 8, fi)) != 0) {
cp1 = argv[1];
cp2 = ip;
while (*cp1 && cp1 < argv[1]+8)
*cp2++ ^= *cp1++;
fwrite(ip, 1, ct, fo);
}
fclose(fo);
}
fclose(fi);
}
}
}
<a name="01e8_0010"><a name="01e8_0010">
<a name="01e8_0011">[LISTING TWO]<a name="01e8_0011">
/* -------------- des.h ---------------- */
/*
* Header file for Data Encryption Standard algorithms
*/
/* ------- two halves of a 64-bit data block ------- */
struct LR {
long L;
long R;
};
/* -------- 48-bit key permutation ------- */
struct ks {
char ki[6];
};
/* --------- 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)
/* -------------- prototypes ------------------- */
void inverse_permute(long *op, long *ip, long *tbl, int n);
void permute(long *op, long *ip, long *tbl, int n);
long f(long blk, struct ks ky);
struct ks KS(int n, char *key);
/* ----------- 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="01e8_0012"><a name="01e8_0012">
<a name="01e8_0013">[LISTING THREE]<a name="01e8_0013">
/* ------------- encrypt.c ------------- */
/*
* Data Encryption Standard encryption filter
* Usage: encrypt keyvalue infile outfile
*/
#include <stdio.h>
#include "des.h"
void main(int argc, char *argv[])
{
int i;
struct LR op, ip;
FILE *fi, *fo;
struct ks keys[16];
for (i = 0; i < 16; i++)
keys[i] = KS(i, argv[1]);
if (argc > 3) {
if ((fi = fopen(argv[2], "rb")) != NULL) {
if ((fo = fopen(argv[3], "wb")) != NULL) {
while (fread(&ip, 1,
sizeof(struct LR), fi) != 0) {
int n;
/* -------- initial permuation -------- */
permute(&op.L, &ip.L, (long *)IPtbl, 64);
/* ------ swap and key iterations ----- */
for (n = 0; n < 16; n++) {
ip.L = op.R;
ip.R = op.L ^ f(op.R, keys[n]);
op.R = ip.R;
op.L = ip.L;
}
/* ----- inverse initial permuation ---- */
inverse_permute(&op.L, &ip.L,
(long *)IPtbl, 64);
fwrite(&op, 1, sizeof(struct LR), fo);
/* ------- to pad the last block ------- */
ip.L = ip.R = 0;
}
fclose(fo);
}
fclose(fi);
}
}
}
<a name="01e8_0014"><a name="01e8_0014">
<a name="01e8_0015">[LISTING FOUR]<a name="01e8_0015">
/* ------------- decrypt.c ------------- */
/*
* Data Encryption Standard encryption filter
* Usage: decrypt keyvalue infile outfile
*/
#include <stdio.h>
#include "des.h"
void main(int argc, char *argv[])
{
int i;
struct LR op, ip;
FILE *fi, *fo;
struct ks keys[16];
for (i = 0; i < 16; i++)
keys[i] = KS(i, argv[1]);
if (argc > 3) {
if ((fi = fopen(argv[2], "rb")) != NULL) {
if ((fo = fopen(argv[3], "wb")) != NULL) {
while (fread(&ip, 1,
sizeof(struct LR), fi) != 0) {
int n;
/* -------- initial permuation -------- */
permute(&op.L, &ip.L, (long *)IPtbl, 64);
/* ------ swap and key iterations ----- */
for (n = 15; n >= 0; --n) {
ip.R = op.L;
ip.L = op.R ^ f(op.L, keys[n]);
op.R = ip.R;
op.L = ip.L;
}
/* ----- inverse initial permuation ---- */
inverse_permute(&op.L, &ip.L,
(long *)IPtbl, 64);
fwrite(&op, 1, sizeof(struct LR), fo);
/* ------- to pad the last block ------- */
ip.L = ip.R = 0;
}
fclose(fo);
}
fclose(fi);
}
}
}
<a name="01e8_0016"><a name="01e8_0016">
<a name="01e8_0017">[LISTING FIVE]<a name="01e8_0017">
/* ---------------------- des.c --------------------------- */
/*
* Functions and tables for DES encryption and decryption
*/
#include <stdio.h>
#include "des.h"
static void rotate(unsigned char *c, int n);
static long S(struct ks ip);
static int fourbits(struct ks, int s);
static int sixbits(struct ks, int s);
/* ------- inverse permute a 64-bit string ------- */
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 ------- */
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) ----- */
long f(long blk, struct ks key)
{
struct LR ir = {0,0};
struct LR or;
union {
struct LR f;
struct ks kn;
} tr = {0,0}, kr = {0,0};
ir.L = blk;
kr.kn = key;
permute(&tr.f.L, &ir.L, (long *)Etbl, 48);
tr.f.L ^= kr.f.L;
tr.f.R ^= kr.f.R;
ir.L = S(tr.kn);
permute(&or.L, &ir.L, (long *)Ptbl, 32);
return or.L;
}
/* ---- convert 48-bit block/key permutation to 32 bits ---- */
static long S(struct ks ip)
{
int i;
long op = 0;
for (i = 8; i > 0; --i) {
long four = fourbits(ip, i);
op |= four << ((i-1) * 4);
}
return op;
}
/* ------- 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[8-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 = (8-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 ----------- */
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 positions to the left ---- */
static void rotate(unsigned char *c, int n)
{
int i;
unsigned j, k;
k = *c >> (8 - n);
for (i = 3; i >= 0; --i) {
j = (*(c+i) << n) + k;
k = j >> 8;
*(c+i) = j;
}
}
<a name="01e8_0018"><a name="01e8_0018">
<a name="01e8_0019">[LISTING SIX]<a name="01e8_0019">
/* --------------- tables.c --------------- */
/*
* tables for the DES algorithm
*/
#include "des.h"
/* --------- 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( 0),
p( 1),p(58),p(50),p(42),p(34),p(26),p(18),p( 0),
p(10),p( 2),p(59),p(51),p(43),p(35),p(27),p( 0),
p(19),p(11),p( 3),p(60),p(52),p(44),p(36),p( 0),
p(63),p(55),p(47),p(39),p(31),p(23),p(15),p( 0),
p( 7),p(62),p(54),p(46),p(38),p(30),p(22),p( 0),
p(14),p( 6),p(61),p(53),p(45),p(37),p(29),p( 0),
p(21),p(13),p( 5),p(28),p(20),p(12),p( 4),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),
p(41),p(52),p(31),p(37),p(47),p(55),p(30),p(40),
p(51),p(45),p(33),p(48),p(44),p(49),p(39),p(56),
p(34),p(53),p(46),p(42),p(50),p(36),p(29),p(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
};