OSEC

Neohapsis is currently accepting applications for employment. For more information, please visit our website www.neohapsis.com or email hr@neohapsis.com
Crypto Archives: Notes on Substitutions

Notes on Substitutions

Mok-Kong Shen (mok-kong.shent-online.de)
Mon, 01 Nov 1999 12:24:46 +0100

The now classsical polyalphabetical substitution uses a key to choose
from a set of (in the general case independent, i.e. not merely
rotated or Vigenere type) monoalphabetic substitutions. Implemented
on a computer, the substitution table provides a set of bijective
mappings of [0, 2^n-1] to itself (with e.g. n=8) with the mappings
being used in a fixed cyclical order determined by the key.

Partly stimulated by some recent discussions on compression in
sci.crypt, I like to point out the following possibilities of
generalization of encipherment with polyalphabetical substitutions.

1. The key, customarily fairly short, may be extended (in the sense
of avoiding short periodicity of processing), if one uses it as a
seed of a PRNG and let the output of the PRNG to choose from a set
of mappings (which themselves can be conveniently generated with the
PRNG). Thus the PRNG 'drives' the polyalphabetical substitution,
analogously to my recent suggestion to use a PRNG to drive modern
block ciphers for the purpose of defeating differential analysis of
these. (I employed this technique in my humble algorithm WEAK3-EX.)
Through the 'indirectness' (i.e. the PRNG output is not 'directly
involved' with the ciphertext like in cases where XORing of PRNG
output with the plaintext is employed) the inference of the PRNG is
difficult to perform.

2. One need not confine oneself to using bijective mappings of
[2, 2^n-1] to itself, where the input and output symbols are all of
constant size, i.e. all of n bits. One can use Huffman codes instead.
This immediately enables one to obtain a plethora of essentially
different mappings. (Note that a short code symbol can be mapped to
a long one and vice versa. This huge 'variability' can serve to
greatly confound the analyst.) Firstly, for m terminal nodes there is
a large number of possible binary trees (of different shapes), giving
rise to a large number of sets of Huffman code symbols. Secondly,
given two such Huffman trees, their terminal nodes can be mapped in
m factorial different ways, i.e. leading to m! different mappings.
Note again that in both these aspects a PRNG can be utilized to
advantage. Of course, these mappings can be dynamically chosen as
described in item 1 above and even created (possibly also in
plaintext dependent ways) as the encryption processing goes on.
Further, encryptions of such nature employing different mappings can
be advantageously concantenated (superencipherment).

To avoid eventual misunderstandings, it is to be remarked that this
article does not touch on the topic of compression, even though
Huffman encoding is generally associated with the field of
compression. In fact, encryption using suggestions given in item 2
above may even often lead to outputs that are longer than the inputs.
I like also to acknowlege that an essential part of the ideas in
item 2 stems from Serge Hallyn.

M. K. Shen
---------------------------
http://home.t-online.de/home/mok-kong.shen

This archive was generated by hypermail 2.0b3 on Mon Nov 01 1999 - 08:04:53 CST