Prev: Patented HOTP One-Time Password Algorithm?
Next: Complexity Theoretic Cryptography
From: Mok-Kong Shen on 17 Mar 2010 17:23
[The original version of this post was erroneous. This is a revision.]

For digram substitutions in classical crypto, a scheme that has the
merit of being highly compact is the well-known Playfair, where for an
alphabet of size 25 (commonly i=j) one needs only a 5*5 matrix (with
single letters as elements), while for a general substitution scheme
a 25*25 matrix (with randomly ordered digrams as elements) would be
required.

Certainly, for the compactness of Playfair there is a corresponding
price to be paid, namely its digram mapping is less general. For
example, with the following Playfair matrix (taken from H. F. Gaines,
ch.21, Polygram Substitution -- The Playfair Cipher):

c u l p e
r a b d f
g h i k m
n o q s t
v w x y z

if the first element of a plaintext pair is c and the second element
is not in (u, l, p, e), i.e. is not an element of the row where c is,
then the first element of the ciphertext pair is always in
(c, r, g, n, v), i.e. is an element of the column where c is. This
is clearly a severe limitation in comparison to a general digram
substitution.

Consider however n-gram (n>2) substitutions. In this case a general
substitution scheme for an alphabet of size 25 would require an
n-dimentional array of size 25 in each dimension and with randomly
ordered n-grams as elements, which would apparently be unfavourable
in respect of storage for larger values of n.

I am unaware of literatures on Playfair-like schemes for trigram
substitution. (One person who had previously coded a 3*3*3 Playfair
informed me that his code is unfortunately no longer available.) In the
following we shall first show an alternative compact scheme for diagram
substitution that, though requiring some more storage space than
Playfair (more exactly two times as much), is still much less in
storage requirement than that of a general substitution scheme. (Note
that its mapping is on the other hand also somewhat more general than
Playfair.) From that we shall derive an analogous (similarly compact)
trigram substitution scheme, which has the merit of being easily and
systematically generalizable to n-gram substitutions for arbitrarily
large values of n.

To simplify explanations, let's consider an alphabet (a, b, c, d) of
size m = 4 . An example of a Playfair matrix is:

a c
b d

If we have, for example, the following two vectors (vertical columns):

a c
b d
c a
d b

then it can be easily seen that some rules of operation of Playfair
(the main rule being taking the opposite "diagonal" to e.g. transcribe
ad to bc) can be taken over to do a digram substitution. In fact,
denoting the two vectors by u[*] and v[*] and letting the plaintext
pair (U,V) be represented by (u[i],v[j]), we can use the following code:

if (i==j) i' = j' = (i+1) % m;
else { i' = j; j' = i; }

to obtain the pair (u[i'],v[j']) as the ciphertext pair (U',V'). Note
that the purpose of the if-part of the above statement is to take care
of the degenerate case where the two "diagonals" coalesce into one
"horizontal", with the undesirable consequence of having (U',V') equal
to (U,V) if the else-part were executed instead.

It is difficult to see how the above code could be generalized to the
case of trigrams. Now let's rewrite it to the following (slightly less
efficient) equivalent form:

if (!(i==j)) { i' = j; j' = i; }
else { i' = (i+1) % m; j' = (j+1) % m; }

From this, it can be seen how we could in the case of n=3 use three
vectors u[*], v[*], w[*] to transcribe the plantext triple (U,V,W),
represented by (u[i],v[j],w[k]), to obtain the triple
(u[i'],v[j'],w[k']) as the ciphertext triple (U',V',W'), namely:

if (!(i==j || j==k || k==i)) { i' = j; j' = k; k' = i; }
else { i' = (i+1) % m; j' = (j+1) % m; k' = (k+1) % m; }

For a general n, we have the following pseudo-code (where we have
also used an arbitrary constant c (1 <= c <= 25) instead of 1 as the
increment):

If (the indices are all distinct) cyclically permute the indices;
else increment all indices by c;

Of course, the elements in the above need not be letters of the English
alphabet but can be e.g. bytes. It may be remarked that, if there are
N (N>n) vectors available, we could (employing the idea of the common
polyalphabetic substitution) use a keystream to determine n vectors out
of the total N vectors to process any single n-gram of the given
plaintext stream (i.e. in a sense "polyalphabetic" n-gram substitution).

Thanks.

M. K. Shen
------------------------------------------------------------------------

P.S. Maaartin questioned in a follow-up to the original version of this
post whether our scheme (with n=2) could be considered as (real) digram
substitution. Answer: Our scheme could be considered as a digram
substitution in the same sense that Playfair could. (For our scheme
works in ways analogous to Playfair. See also the limitation of Playfair
described above.)

------------------------------------------------------------------------

[OT, personal note:] I am unfortunately forced by recurrent personal
insults to use kill-file. That is, I would not read, not to say answer,
posts of some who have the mean habit of frequently abuse this
sci-group that way. Anyone who doesn't like my posts for whatever
reasons is strongly advised to put me in his kill-file as well.
From: Mok-Kong Shen on 18 Mar 2010 05:39
Mok-Kong Shen wrote:

> For a general n, we have the following pseudo-code (where we have
> also used an arbitrary constant c (1 <= c <= 25) instead of 1 as the
> increment):
>
> If (the indices are all distinct) cyclically permute the indices;
> else increment all indices by c;

[Addendum:] We have very closely followed Playfair in developing our
scheme, adopting some rules of Playfair directly. However, because of
the difference to Playfair (we use n alphabets, while Playfair uses
one), we could simplify the above to the following:

Cyclically permute the indices;
Increment all indices by c (mod m);

Note that one could also dynamically vary c, if one likes.

M. K. Shen
From: Maaartin on 18 Mar 2010 12:23
> P.S.  Maaartin questioned in a follow-up to the original version of this
> post whether our scheme (with n=2) could be considered as (real) digram
> substitution. Answer: Our scheme could be considered as a digram
> substitution in the same sense that Playfair could. (For our scheme
> works in ways analogous to Playfair. See also the limitation of Playfair
> described above.)

You missed my point. Sure, Playfair is not a general digram
substitution cipher, but - unlike yours - it produces pairs of
ciphertext letters where both members depends on both members of the
plaintext letter pair.

Most of the time (i.e., except in case of i=j) your (digram) cipher
does two monoalphabetic substitutions followed by a swap of the
letters inside each pair.

What you do most of the time is just:
- Locate the second letter in the second column and output the
corresponding letter from the first column.
- Locate the first letter in the first column and output the
corresponding letter from the second column.
So there's one monoalphabetic substitutions for letters in the odd
positions and it's inverse for the rest.
From: Noob on 18 Mar 2010 12:37
Maaartin wrote: [snip]

Hello Maaartin,

Because I don't have the original message, and because your post
does not include an attribution line, I cannot tell who you are
replying to.

Could you include such an attribution line in your future posts?

Regards.
From: Maaartin on 18 Mar 2010 13:24
On Mar 18, 5:37 pm, Noob <r...(a)127.0.0.1> wrote:
> Maaartin wrote: [snip]
>
> Hello Maaartin,
>
> Because I don't have the original message, and because your post
> does not include an attribution line, I cannot tell who you are
> replying to.
>
> Could you include such an attribution line in your future posts?
>
> Regards.

Sure, I will. I do it usually but sometimes forget. You can see the
whole thread here:
http://groups.google.com/group/sci.crypt/browse_thread/thread/ca6cb9ab2eae1a57/7cb9c13467b9d360?hl=en#7cb9c13467b9d360
 |  Next  |  Last
Pages: 1 2
Prev: Patented HOTP One-Time Password Algorithm?
Next: Complexity Theoretic Cryptography