second order homophonic substitution

[peter honeyman <honey@citi.umich.edu>]

a faq on this list (and other places) is whether it is possible to
encipher a message in such a way that the resulting ciphertext can be
deciphered into a different (harmless?) message.  i mentioned on
sci.crypt that a second-order homphonic substitution does just this,
but it seems to have been missed by the cpunx readership.  so, just to
prove that i can read denning and still type, here is a brief
explanation.  (not brief enuf, sorry.)

a homophonic substitution maps letters from the plaintext alphabet into
sets of letters from the ciphertext alphabet.  to encipher, you pick an
arbitrary letter from the image of each plaintext letter.  usually the
intent is to disguise single letter frequency statistics.  it's still
not very strong, since it doesn't disguise digram or trigram
statistics.  (also, it seems to me that it would be vulnerable to the
same sort of attack used on running key ciphers.)

need an example?  see denning, p. 70.

to build a second order homophonic substitution cipher, you construct
an n by n table, where n is the size of the plaintext alphabet.  (say n
= 26).  initialize each entry in the table by a unique element from the
ciphertext alphabet.  (say, the integers from 0 to 26 * 26, permuted
arbitrarily.)  this table constitutes the key.

to encipher a message, select a "dummy" message (say the itar regs).
to encipher the i-th plaintext letter, say p sub i, grab the i-th
dummy letter, say d sub i, and output table[d sub i, p sub i].

to decipher, find the ciphertext letter (or number, in this case) in
the table at row i and column j.  to recover the actual message, output
the j-th plaintext alphabet letter.  to recover the dummy message,
output the i-th plaintext alphabet letter.  i.e., the rows give the
dummy message, while the columns give the actual message.

simple stuff.  here's an example.

table:

	
	D	E	G	I	N	O	S	T	U
D	01	02	03	04	05	06	07	08	09

E	10	11	12	13	14	15	16	17	18

G	19	20	21	22	23	24	25	26	27

I	28	29	30	31	32	33	34	35	36

N	37	38	39	40	41	42	43	44	45

O	46	47	48	49	50	51	52	53	54

S	55	56	57	58	58	60	61	62	63

T	64	65	66	67	68	69	70	71	72

U	73	74	75	76	77	78	79	80	81

here is some ciphertext: 64 11 05 32 49 77 57.

it's clear how to extend this to n-th order.

	peter