From: jpr@jpradley.jpr.com (Jean-Pierre Radley)
Subject: Re: encryption program?
Date: Wed, 23 Dec 1992 04:45:09 GMT
Organization: Unix in NYC

In article <1992Dec16.104806.23577@nuscc.nus.sg> elekokws@nuscc.nus.sg (Netweaver) writes:
>I have some data file ( binary and text ) that I would like to
>encrypt, using something better than the Unix's crypt().
>can anyone tell me where I can ftp one?
>



:
# hill.c : an encryption program superior to Xenix 'crypt'
# 
# Author: John Cowan.  Copyright (c) 1987 by John Cowan.  Permission
# for unrestricted noncommercial republication granted provided this
# copyright notice is retained on all republished copies.  Permission
# to post this file on Compuserve specifically granted by John Cowan.
#
# The Unix/Xenix 'crypt' program is not, as many erroneously believe,
# an implementation of the National Bureau of Standard's "Data Encryption
# Standard" (DES) for data encryption.  It is, instead, an implementation
# of an unrelated algorithm, much simpler, much faster-running, and much
# more vulnerable to determined code-breaking, mostly because it preserves
# the structure of the original (plaintext) data and is therefore open to
# statistically-based pattern-recognition methods of code-breaking.
# 
# This program provides an encryption/decryption scheme that's
# stronger than Unix/Xenix 'crypt', but is still weaker than the
# DES standard.  No utility is supplied with any current
# microcomputer version of Unix or Xenix that truly implements the
# DES standard, although such utilities can be constructed (more
# or less) with the function libraries that usually come with Unix
# (Xenix with the "Development System(s)") and a bit of twiddling
# around.  The Unix/Xenix password-encryption scheme does use the
# DES standard (in a stronger way than does the DES standard
# itself), but it's something else again.
# 
# This archive contains the files hill.doc, hill.c, table.i, and
# kappa.c.  To extract these files, type "sh filename" where
# 'filename' is the name you've saved this file under.
# 
echo splitting out files
sed -n '/#START/,$p' <$0 | \
sed -e '/file: hill\.doc/,/EOF: hill\.doc/w hill.doc' \
    -e '/file: hill\.c/,/EOF: hill\.c/w hill.c' \
    -e '/file: table\.i/,/EOF: table\.i/w table\.i' \
    -e '/file: kappa\.c/,$w kappa.c' >/dev/null
echo compiling hill
cc -o hill hill.c
echo compiling kappa
cc -o kappa kappa.c
echo Done.
exit
#START
/* file: hill.doc */
Hill encryption (decryption) program

Hill operates as a filter, reading plain (encrypted) text from the standard
input and writing encrypted (plain) text to the standard output.  It is
necessary to specify either -e for encryption or -d for decryption.  The
key may be specified on the command line or, if omitted, will be prompted
for.  The minimum keysize is 9 characters; the maximum is 256.  Longer keys
make for greater security and slower operation.

The options -c, -C, -p, and -s are mutually exclusive, and specify pre-encoding
(post-decoding) of the plaintext.  -c specifies dynamic Huffman encoding using
'compact' ('uncompact'); -C specifies Lempel-Ziv encoding using 'compress'
('uncompress'); -p specifies fixed Huffman encoding using 'pack' ('unpack');
-s specifies CP/M compatible fixed Huffman encoding using 'sq' ('usq').
The specified programs for each option must exist on the system for the option
to be effective.  The options -c and -C actually improve cryptographic security,
and should be used whenever time is not critical; the options -p and -s decrease
security, and should be used only when space is critical.

Timing considerations:  On an 8MHz IBM PC-AT running Microport Unix, 'hill'
operates at about 3K/sec for a 16-byte key.  Using a 100-byte key, speed is
about half that.

Space considerations:  Encrypted files are about 1% longer than their plaintext
equivalents.

Kappa:  Kappa is a utility program which prints the byte frequencies of the
standard input.  The output is in the form of an array of 256 frequencies,
read row-wise.  Each frequency is multiplied by 1000 on output.
/* EOF: hill.doc */
/* file: hill.c */
# include <stdio.h>
# include "table.i"
FILE *popen();

# define Over(x) for (x = 0; x < order; x++)
# define Times(a,b) ((long)(a) * (long)(b) % 257)

int mode;
int reduction;

char key[256];
int matkey[16][16];
int invec[16];
int outvec[16];
int order;

FILE *input;
FILE *output;

setup(argc, argv)
int argc; char **argv;
    {
    extern int optind;
    extern int opterr;
    int eflag = 0;
    int dflag = 0;
    int cflag = 0;
    int Cflag = 0;
    int pflag = 0;
    int sflag = 0;
    int qflag = 0;
    int c;
    long tloc;

    time(&tloc);
    srand((int) tloc);
    opterr = 0;
    mode = 0;
    reduction = 0;
    while ((c = getopt(argc, argv, "edcCps")) != EOF)
	switch(c) {
	case 'e': eflag++; break;
	case 'd': dflag++; break;
	case 'c': cflag++; break;
	case 'C': Cflag++; break;
	case 'p': pflag++; break;
	case 's': sflag++; break;
	case '?': qflag++; break;
	    }
    if (qflag || (!eflag && !dflag) || (eflag && dflag) ||
		(cflag + Cflag + pflag + sflag > 1)) {
	fprintf(stderr,
"usage: %s { -e | -d } [{ -c | -C | -p | -s }] [key]\n", argv[0]);
	exit(1);
	}
    if (eflag) mode = 'e';
    if (dflag) mode = 'd';
    if (cflag) reduction = 'c';
    if (Cflag) reduction = 'C';
    if (pflag) reduction = 'p';
    if (sflag) reduction = 's';
    strcpy(key, argv[optind]);
    argv[optind] = 0;
    }

makemat()
    {
    int i, j, k;
    int n = 0;
    FILE *tty;

    if (strlen(key) == 0) {
	tty = fopen("/dev/tty", "r+");
	setbuf(tty, NULL);
	fprintf(tty, "Key? ");
	fgets(key, sizeof(key), tty);
	key[strlen(key) - 1] = 0;
	fclose(tty);
	}
    setorder();
    Over(i) Over(j)
	matkey[i][j] = key[n++];
    for (i = 0; i < strlen(key); i++)
	key[i] = 0;
    square();
    while ((k = invert()) != EOF)
	matkey[k][k] = (matkey[k][k] + 1) % 257;
    }

setorder()
    {
    int n = strlen(key);

    for (order = 0; order < 17; order++)
	if (order*order > n) break;
    order--;
    if (order < 3) {
	fprintf(stderr, "key size < 9\n");
	exit(1);
	}
    }

square()
    {
    int result[16][16];
    int i, j, k;

    Over(i) Over(j)
	result[i][j] = 0;
    Over(i) Over(j) Over(k)
	result[i][j] += Times(matkey[i][k], matkey[k][j]);
    Over(i) Over(j)
	matkey[i][j] = result[i][j] % 257;
    }

int invert()
    {
    int matrix[16][16];
    int inverse[16][16];
    int i, j, k;
    int t;
    int pivot;

    Over(i) Over(j) {
	matrix[i][j] = matkey[i][j];
	inverse[i][j] = 0;
	}
    Over(k)
	inverse[k][k] = 1;

    Over(k) {
	if (matrix[k][k] == 0) {
	    for (i = k + 1; i < order; i++)
		if (matrix[i][k]) {
		    Over(j) {
		        t = matrix[i][j];
		        matrix[i][j] = matrix[k][j];
		        matrix[k][j] = t;
		        t = inverse[i][j];
		        inverse[i][j] = inverse[k][j];
		        inverse[k][j] = t;
		        }
		    break;
		    }
	    if (i == order) return(k);
	    }

	pivot = inverses[matrix[k][k]];
	Over(j) {
	    matrix[k][j] = Times(matrix[k][j], pivot);
	    inverse[k][j] = Times(inverse[k][j], pivot);
	    }
	Over(i) if (i != k) {
	    pivot = matrix[i][k];
	    Over(j) {
		matrix[i][j] -= Times(pivot, matrix[k][j]);
		if (matrix[i][j] < 0) matrix[i][j] += 257;
		inverse[i][j] -= Times(pivot, inverse[k][j]);
		if (inverse[i][j] < 0) inverse[i][j] += 257;
		}
	    }
	}

    if (mode == 'd') Over(i) Over(j)
	matkey[i][j] = inverse[i][j];
    return(EOF);
    }

streams()
    {
    input = stdin;
    output = stdout;
    if (mode == 'e') {
	if (reduction == 'c')
	    input = popen("compact", "r");
	else if (reduction == 'C')
	    input = popen("compress", "r");
	else if (reduction == 'p')
	    input = popen("cat >/tmp/hl$$;\
pack /tmp/hl$$ >/dev/null; cat </tmp/hl$$.z; rm /tmp/hl$$.z", "r");
	else if (reduction == 's')
	    input = popen("cat >/tmp/hl$$;\
sq /tmp/hl$$ >/dev/null; cat </tmp/hl$$.SQ;\
rm /tmp/hl$$ /tmp/hl$$.SQ", "r");
	}
    else {
	if (reduction == 'c')
	    output = popen("uncompact", "w");
	else if (reduction == 'C')
	    output = popen("uncompress", "w");
	else if (reduction == 'p')
	    output = popen("cat >/tmp/hl$$.z;\
unpack /tmp/hl$$ >/dev/null; cat </tmp/hl$$; rm /tmp/hl$$", "w");
	else if (reduction == 's')
	    output = popen("cat >/tmp/hl$$.SQ;\
usq /tmp/hl$$.SQ >/dev/null; cat </tmp/hl$$;\
rm /tmp/hl$$ /tmp/hl$$.SQ", "w");
	}
    }

int getvec()
    {
    int i;
    int padf = 0;

    Over(i)
	if ((invec[i] = getc(input)) == EOF) {
	    if (i == 0) return(0);
	    else if (padf) invec[i] = rand() % 257;
	    else { invec[i] = 256; padf++; }
	    }
	else if (invec[i] == 255 && mode == 'd')
	    invec[i] += getc(input);
    return(i);
    }

putvec()
    {
    int j;

    Over(j)
	switch(outvec[j]) {
	case 256:
	    if (mode == 'd') return;
	    else putc(255, output) , putc(1, output);
	    break;
	case 255:
	    putc(255, output);
	    if (mode == 'e') putc(0, output);
	    break;
	default:
	    putc(outvec[j], output);
	    }
    }

matmul()
    {
    int i, j, k;

    Over(i) {
	outvec[i] = 0;
	Over(j)
	    outvec[i] += Times(invec[j], matkey[i][j]);
	outvec[i] %= 257;
	}
    }

main(argc, argv)
int argc; char **argv;
    {
    setup(argc, argv);
    streams();
    makemat();
    while(getvec()) {
	matmul();
	putvec();
	}
    if (mode == 'e' && reduction) pclose(input);
    if (mode == 'd' && reduction) pclose(output);
    }
/* EOF: hill.c */
/* file: table.i */
int inverses[257] = { 0, 1, 129, 86, 193, 103, 43, 147, 225, 200, 180, 187, 
150, 178, 202, 120, 241, 121, 100, 230, 90, 49, 222, 190, 75, 72, 89, 238, 101, 
195, 60, 199, 249, 148, 189, 235, 50, 132, 115, 145, 45, 163, 153, 6, 111, 40, 
95, 175, 166, 21, 36, 126, 173, 97, 119, 243, 179, 248, 226, 61, 30, 59, 228, 
102, 253, 87, 74, 234, 223, 149, 246, 181, 25, 169, 66, 24, 186, 247, 201, 244, 
151, 165, 210, 96, 205, 127, 3, 65, 184, 26, 20, 209, 176, 152, 216, 46, 83, 
53, 139, 135, 18, 28, 63, 5, 215, 164, 177, 245, 188, 224, 250, 44, 218, 116, 
124, 38, 113, 134, 159, 54, 15, 17, 158, 140, 114, 220, 51, 85, 255, 2, 172, 
206, 37, 143, 117, 99, 240, 242, 203, 98, 123, 144, 219, 133, 141, 39, 213, 7, 
33, 69, 12, 80, 93, 42, 252, 194, 229, 239, 122, 118, 204, 174, 211, 41, 105, 
81, 48, 237, 231, 73, 192, 254, 130, 52, 161, 47, 92, 106, 13, 56, 10, 71, 233, 
191, 88, 232, 76, 11, 108, 34, 23, 183, 170, 4, 155, 29, 198, 227, 196, 31, 9, 
78, 14, 138, 160, 84, 131, 221, 236, 91, 82, 162, 217, 146, 251, 104, 94, 212, 
112, 142, 125, 207, 22, 68, 109, 8, 58, 197, 62, 156, 19, 168, 185, 182, 67, 
35, 208, 167, 27, 157, 136, 16, 137, 55, 79, 107, 70, 77, 57, 32, 110, 214, 
154, 64, 171, 128, 256};
/* EOF: table.i */
/* file: kappa.c */
# include <stdio.h>

long table[256];
long total;

main()
    {
    int ch;
    int i;
    int lcmpr();

    while ((ch = getchar()) != EOF) {
	table[ch]++;
	total++;
	}
    printf("Total: %ld\n\n", total);
    for (i = 0; i < 256; i++) {
	table[i] *= 1000;
	table[i] /= total;
	}
    for (i = 0; i < 256; i++) {
	printf("%3.3ld ", table[i]);
	if ((i + 1) % 16 == 0) putchar('\n');
	if ((i + 1) % 128 == 0) putchar('\n');
	}
    }
-- 
Jean-Pierre Radley   Unix in NYC   jpr@jpr.com   jpradley!jpr   CIS: 72160.1341
Xref: sparky alt.security:5213 sci.crypt:6079 talk.politics.misc:65164 alt.security.pgp:378