On n-gram substitutions
in [Cryptography]
|
Prev: Server and Client Analogy – The NewCryptography Model
Next: Final Subj: A regular pattern found in the first 301 Million Prime Sums using the log of the golden ratio Lp! (0/1)
From: Mok-Kong Shen on 16 Mar 2010 11:03 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. 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. 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 it's 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 similar to those used in Playfair (the main rule being taking the opposite "diagonal" to e.g. transcribe ad to bc) can be employed to do the 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 (pseudo) 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+1) % m; else i' = j; if (j==i) j' = (i+1) % m; else j' = i; From this, it is evident 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) i' = (j+1) % m; else i' = j; if (j==k) j' = (k+1) % m; else j' = k; if (k==i) k' = (i+1) % m; else k' = i; The generalization of this for an n-gram substitution with n>3 should be obvious. 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 ------------------------------------------------------------------------ [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: Maaartin on 16 Mar 2010 12:39 > I am unaware of literatures on Playfair-like schemes for trigram > substitution. It would be easy generalize it to a 3x3x3 cube, I believe to have seen it somewhere. But it could be cumbersome to use. On Mar 16, 4:03 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > a c > b d > c a > d b > > then it can be easily seen that some rules of operation similar to > those used in Playfair (the main rule being taking the opposite > "diagonal" to e.g. transcribe ad to bc) can be employed to do the > 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 (pseudo) 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'). But this is no (real) digram substitution. Ignoring the (quite rare) case of i=j, you get U' as function of V only and V' as function of U only.
From: Mok-Kong Shen on 16 Mar 2010 14:25
Maaartin wrote: Mok-Kong.Shen wrote: [snip] My original presentation was not entirely right. I hope but doubt of soon finding good ways of amending it. Please ignore it anyway. Sincere apology. M. K. Shen |