# Latin Square Combining

## A Ciphers By Ritter Page

A conventional stream cipher combines some sort of keyed "running key" or confusion sequence with data by "addition," generally exclusive-OR.

We normally assume that an opponent will have some amount of known plaintext (the plaintext and related ciphertext, but not the keyed confusion sequence). The problem is that a simple additive combiner immediately exposes the confusion sequence under known-plaintext, which allows the confusion generator to be attacked.

To avoid this, we can use a Latin square combiner. The question then arises as to whether we can make a good Latin square in relatively small storage.

### Contents

• 2000-01-24 Alan Lawrence: "I'm having a go at writing some simple encryption software myself and wonder if anyone has any ideas...system works by combining the plaintext byte with other bytes, derived from the key, by some of the following methods:" "my problem is that I want a fourth method!"
• 2000-01-24 Terry Ritter: "Any such method will be particular cases of Latin square . . . ."
• 2000-01-25 Michael Wojcik: "Just off the top of my head:"
• 2000-01-25 Terry Ritter: "Can the given method be generalized to construct orthogonal Ls's?"
• 2000-01-25 Tim Tyler: "On subsequent colums, swap random row entries, with the constraint that you never swap a number into the same position as it is in, in any of the previous entries in that row."
• 2000-01-25 Terry Ritter: "We can improve efficiency by keeping lists of the symbols and positions used in rows and columns, and choosing the most-constrained element for a random fill."
• 2000-01-27 Alan Lawrence: "Is this decryptable (given the key)?"
• 2000-02- 3 Michael Wojcik: "Whether that square is "strong" (are all squares equally strong, or are some, say, easier to reconstruct from cyphertext?) is another question."
• 2000-02- 7 Michael Wojcik: "We can keep an order-256 square as two or three arrays of 256 bytes each . . . ." "For decoding, this only works if we can generate the inverse square in the same form." "Question: Is the inverse of a PRT-form square always itself a PRT- form square? More generally, are all Latin Squares in PRT-form?" "Call a square of this soft "PRT-form"."
• 2000-02- 8 Tim Tyler: "The information content is smaller than this perhaps might suggest . . . ."
• 2000-02- 7 r.e.s.: "But the table can't be totally random if it's to be a workable combiner."
• 2000-02- 8 Tim Tyler: "Indeed not. Only a tiny fraction of these would be valid Latin squares."
• 2000-02- 8 r.e.s.: "I was pointing out that it's not to a totally random table that one would want to make a comparison."
• 2000-02- 8 Tony T. Warnock: "A Latin square is the operation table of a quasi-group."
• 2000-02- 8 r.e.s.: "The Latin Square combiners appear to be a subset of all possible combiners . . . ."
• 2000-02- 9 zapzing: "You do *not* need a latin square . . . ."
• 2000-02- 9 r.e.s.: "We're in total agreement that a combiner need not be a Latin Square . . . ." ". . . . if a column is not a permutation of the entire output symbol alphabet, then some output symbols may tend to be more/less frequent than others . . . ."
• 2000-02-10 Tony T. Warnock: "With Latin squares, the probabilities get more uniform."
• 2000-02-10 wtshaw: "Consider Swagman, which specifies such a square for the key."
• 2000-02-10 zapzing: "If that sort of combining function were used, it would have to be used in conjunction with other techniques . . . ."
• 2000-02-10 Tim Tyler: "If you *don't* have a Latin square, you may be doing the equivalent of wasting some of your keys."
• 2000-02-11 zapzing: ". . . you might consider generating it in this way:"
• 2000-02-11 Michael Wojcik: "Well, I'm not convinced it's "much easier to do than making a latin square", since we're discussing a fast construction procedure for a subset of Latin Squares." ". . . I don't think anyone's made any very strong arguments for using Latin Squares as combiners yet (in this thread)."
• 2000-02-11 Terry Ritter: "The reason for having *Latin square* combiners is to prevent leakage through either input port."
• 2000-02-11 r.e.s.: ". . . the definition of "linear" is not really clear to me in this context."
• 2000-02-12 Terry Ritter: "In my experience, the distinction between "linear" and "nonlinear" is not as clear as one might like throughout cryptography."
• 2000-02-11 Michael Wojcik: ". . . a non-balanced combiner (as you or someone else pointed out in an earlier post, which unfortunately I've misplaced) lets you retrieve the message but not (completely) the key."
• 2000-02-11 Tony T. Warnock: "Latin squares are really only useful if the input alphabet and key alphabet are the same size."
• 2000-02-12 zapzing: "What if we generalize it to a latin *rectangle*?"
• 2000-02-12 Terry Ritter: "If we just drop in multiple occurrences of values at random, we are almost guaranteed to have some grouping which will highlight some locality of input values."
• 2000-02-13 zapzing: ". . . we would not be guaranteed that every column would contain 256 instances exactly of every byte, but the imbalance would be much less severe."
• 2000-02- 8 wtshaw: "Where you get 161820 for N=5 puzzles me."
• 2000-02- 8 r.e.s.: "(I didn't say that N!^N is the number of LSquares. It's the number of possible NxN "reversible combiners".)"
• 2000-02- 9 wtshaw: ". . . 6x2=12 is right for total possible squares for N=3."
• 2000-02- 8 Dan O.: "hat you are discribing is a permutation of a base Latin Square."
• 2000-02-11 Michael Wojcik: "It looks like we can generate both the encoding and decoding PRT arrays without having to actually generate the square in full at any point . . . ."
• 2000-02-11 Tony T. Warnock: "If the key symbol and the plaintext symbol are chosen independently, the sums of the squares of the probabilities of the output symbols is smaller . . . ."
• 2000-02- 7 r.e.s.: " . . . we can see that not all Lsquares are of your PRT form, by simply comparing with the known number of Latin Squares of given order."
• 2000-02-11 Michael Wojcik: "The relatively small number of order-256 squares that are PRT squares (the "PRT penalty", so to speak) may not be an issue in practice . . . ."
• 2000-02-12 Tim Tyler: "If there /are/ significant weaknesses, they are likely to be caused by "structure" in the table (resulting in spurious conserved quantities and the like) - rather than a lack of possible tables . . . ."
• 2000-02-12 r.e.s.: "Well, we know there are at least 256!255! ~ 10^1011 ~ 2^3359, which is also a healthy number ;-)"
• 2000-02-15 Michael Wojcik: ". . . in brief, some T permutations (reordering the rows after the columns are constructed by the PR method) produce squares that are also PR squares, and some T permutations do not . . . ."
• 2000-02-15 r.e.s.: "I meant to say just the reverse . . . ."
• 2000-02- 8 Terry Ritter: ". . . there really is a great deal more dangerous "structure" in Latin squares constructed from a few permutations than is likely to be present in schemes which must store an entire table."
```
Subject: Reversibly combining two bytes?
Date: Mon, 24 Jan 2000 17:09:32 +0000
From: Alan Lawrence <acl33@hermes.cam.ac.uk>
Message-ID: <Pine.SOL.4.10a.10001241632070.12226-100000@red.csi.cam.ac.uk>
Newsgroups: sci.crypt
Lines: 30

Hi -

I'm having a go at writing some simple encryption software myself and
wonder if anyone has any ideas...system works by combining the plaintext
byte with other bytes, derived from the key, by some of the following
methods:

*exclusive or
*multiply modulo 257 - a value of 256 (in modulo 257) is encoded as a
zero. Since 257 is prime, a value of 0 (modulo 257) is never created.
* ????

my problem is that I want a fourth method! It has to be reversible (so if
cipher = plaintext \$ xxx, then given cipher and xxx it must be possible to
get back the plaintext value), and it has to take two arguments 0..255 and
return a result also in range 0..255. I have tried division modulo 257,
but that's just the same as multiplying by the reciprocal. I tried
carry-less multiplication (i.e. rather than the conventional shift-add, I
did a shift-XOR) and this did indeed produce unique results in the range
0..65535, but I was unable to store these in 8 bits without producing
duplicates.

Any suggestions much appreciated!

Thanks very much
Alan Lawrence

Subject: Re: Reversibly combining two bytes?
Date: Mon, 24 Jan 2000 21:13:17 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <388cc041.2517272@news.io.com>
References: <Pine.SOL.4.10a.10001241632070.12226-100000@red.csi.cam.ac.uk>
Newsgroups: sci.crypt
Lines: 37

On Mon, 24 Jan 2000 17:09:32 +0000, in
<Pine.SOL.4.10a.10001241632070.12226-100000@red.csi.cam.ac.uk>, in
sci.crypt Alan Lawrence <acl33@hermes.cam.ac.uk> wrote:

>I'm having a go at writing some simple encryption software myself and
>wonder if anyone has any ideas...system works by combining the plaintext
>byte with other bytes, derived from the key, by some of the following
>methods:
>
>*exclusive or
>*multiply modulo 257 - a value of 256 (in modulo 257) is encoded as a
>zero. Since 257 is prime, a value of 0 (modulo 257) is never created.
>* ????
>
>my problem is that I want a fourth method!

Any such method will be particular cases of Latin square, and those
having simple math relationships are likely to be linear.  By using
explicit randomly-constructed Ls's which have no simple relationships,
the combining can be nonlinear, yet still reversible.

Given some Ls, one axis is selected by the confusion sequence, the
other by data, and the selected symbol is the ciphertext.  There is
always an inverse square that will take ciphertext to plaintext in a
similar way by using the same confusion sequence.  With a wide enough
confusion sequence, it is possible to select among many such squares,
or to use several selected squares in sequence.

You might want to take a look at my glossary under "combiner" and
"Latin square combiner."

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Originator: mww@lorelei-n

Subject: Re: Reversibly combining two bytes?
Date: 25 Jan 2000 17:04:53 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <86kl3l01kqs@news1.newsguy.com>
References: <Pine.SOL.4.10a.10001242129450.29719-100000@orange.csi.cam.ac.uk>
<388cc041.2517272@news.io.com>
Newsgroups: sci.crypt
Lines: 53

In article <Pine.SOL.4.10a.10001242129450.29719-100000@orange.csi.cam.ac.uk>, Alan Lawrence <acl33@hermes.cam.ac.uk> writes:

> Latin squares can, in effect, hold the details of how to encrypt and
> decrypt by _any_ reversible method, i.e. one could construct a Latin
> Square, the output of which is equal to the sum of the column number and
> row number. Obviously a Latin square with no simple relationships, and
> non-linear combining is far superior....however how do I generate such a
> square? If I find suitable seeds for a random number generator, I can
> permute the sequence 0..255 to generate a column of the table, and do this
> 256 times, but then how do I make sure each number appears exactly once in
> each row as well? Admittedly one could brute force this, repeatedly
> generating the table until it works, but being fussy I don't like doing it
> that way:-)

Just off the top of my head:

Generate one permutation 0..255.  Call it P.
Generate a second permuation 0..255.  Call it R.

For each column C[i=0..255], rotate P by R[i].  The rotation can be
trivially computed while populating C by using (index + R[i]) mod 256
to index P.

For example:

int P[256], R[256], C[256][256];

GeneratePermutation(P);
GeneratePermutation(R);

int col, row;

for (col=0; col < 256; col++)
for (row=0; row < 256; row++)
C[col][row] = P[ (row + R[col]) % 256 ];

Since all columns are different rotations of the same permutation,
no two columns will be the same, and no two columns will have the
same value x in a given row r, so no row will have a repeated
value.

I've only given this cursory thought; it may be broken or weak.

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

This is a "rubbering action game," a 2D platformer where you control a
girl equipped with an elastic rope with a fishing hook at the end.
-- review of _Umihara Kawase Shun_ for the Sony Playstation

Subject: Re: Reversibly combining two bytes?
Date: Tue, 25 Jan 2000 20:49:23 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <388e0c50.3129047@news.io.com>
References: <86kl3l01kqs@news1.newsguy.com>
Newsgroups: sci.crypt
Lines: 42

On 25 Jan 2000 17:04:53 GMT, in <86kl3l01kqs@news1.newsguy.com>, in
sci.crypt michael.wojcik@merant.com (Michael Wojcik) wrote:

>[...]
>Just off the top of my head:
>
>Generate one permutation 0..255.  Call it P.
>Generate a second permuation 0..255.  Call it R.
>
>For each column C[i=0..255], rotate P by R[i].  The rotation can be
>trivially computed while populating C by using (index + R[i]) mod 256
>to index P.

>[...]
>Since all columns are different rotations of the same permutation,
>no two columns will be the same, and no two columns will have the
>same value x in a given row r, so no row will have a repeated
>value.
>
>I've only given this cursory thought; it may be broken or weak.

Upon cursory reading :-), it looks like it ought to work, and I
haven't seen it before.  There is of course more of a relationship
than in a true random construction.  But it might be interesting to
investigate Boolean nonlinearity values in the squares produced by
this method, and compare the distribution to that which occurs in
random squares.

Naturally, for any fixed table, if the opponent can traverse and
identify a substantial portion of the table, or maybe just the part
most commonly used, not much strength can remain.  Ideally we will
select among a multiple keyed squares, used in several sequential
levels, for each character ciphered.

Question:  Can the given method be generalized to construct orthogonal
Ls's?

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Reversibly combining two bytes?
Date: Tue, 25 Jan 2000 17:05:40 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FowI5G.BtH@bath.ac.uk>
References: <Pine.SOL.4.10a.10001242129450.29719-100000@orange.csi.cam.ac.uk>
<388cc041.2517272@news.io.com>
Newsgroups: sci.crypt
Lines: 40

Alan Lawrence <acl33@hermes.cam.ac.uk> wrote:

[Terry Ritter suggested the use of a randomly-constructed Latin Square]

: Latin squares can, in effect, hold the details of how to encrypt and
: decrypt by _any_ reversible method, i.e. one could construct a Latin
: Square, the output of which is equal to the sum of the column number and
: row number. Obviously a Latin square with no simple relationships, and
: non-linear combining is far superior....however how do I generate such a
: square? If I find suitable seeds for a random number generator, I can
: permute the sequence 0..255 to generate a column of the table, and do this
: 256 times, but then how do I make sure each number appears exactly once in
: each row as well? Admittedly one could brute force this, repeatedly
: generating the table until it works, but being fussy I don't like doing it
: that way:-)

The problem is perhaps not /quite/ as bad as you make out.

Here's one (probably highly sub-optimal) way of doing it:

As you say, you can generate a single column of 256 bytes which is a
permutation - by repeatedly swapping individual entries at random a large
number of times.

Generate one column first - by swapping lots of random rows entries.

On subsequent colums, swap random row entries, with the constraint that
you never swap a number into the same position as it is in, in any of
the previous entries in that row.

Repeat until done.

This will produce a rather random Latin Square.  Of course, there is
*some* chance that this will be a linear table - but in a 256x256 table,
this chance is pretty remote.
--
__________
|im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

How do you tell when you've run out of invisible ink?

Subject: Re: Reversibly combining two bytes?
Date: Tue, 25 Jan 2000 20:16:09 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <388e0470.1112409@news.io.com>
References: <FowI5G.BtH@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 55

On Tue, 25 Jan 2000 17:05:40 GMT, in <FowI5G.BtH@bath.ac.uk>, in
sci.crypt Tim Tyler <tt@cryogen.com> wrote:

>Alan Lawrence <acl33@hermes.cam.ac.uk> wrote:
>
>[Terry Ritter suggested the use of a randomly-constructed Latin Square]
>
>: Latin squares can, in effect, hold the details of how to encrypt and
>: decrypt by _any_ reversible method, i.e. one could construct a Latin
>: Square, the output of which is equal to the sum of the column number and
>: row number. Obviously a Latin square with no simple relationships, and
>: non-linear combining is far superior....however how do I generate such a
>: square? If I find suitable seeds for a random number generator, I can
>: permute the sequence 0..255 to generate a column of the table, and do this
>: 256 times, but then how do I make sure each number appears exactly once in
>: each row as well? Admittedly one could brute force this, repeatedly
>: generating the table until it works, but being fussy I don't like doing it
>: that way:-)

One can compromise on using less data, but with more of a relationship
between the columns.  Of course there is always *some* relationship
between columns; if we know n-1 columns for any row, we know entry n.

>The problem is perhaps not /quite/ as bad as you make out.
>
>Here's one (probably highly sub-optimal) way of doing it:
>
>As you say, you can generate a single column of 256 bytes which is a
>permutation - by repeatedly swapping individual entries at random a large
>number of times.
>
>Generate one column first - by swapping lots of random rows entries.
>
>On subsequent colums, swap random row entries, with the constraint that
>you never swap a number into the same position as it is in, in any of
>the previous entries in that row.
>
>Repeat until done.
>
>This will produce a rather random Latin Square.  Of course, there is
>*some* chance that this will be a linear table - but in a 256x256 table,
>this chance is pretty remote.

We can improve efficiency by keeping lists of the symbols and
positions used in rows and columns, and choosing the most-constrained
element for a random fill.  Some backtracking is inevitable in a
random construction.  Years ago, on a 90 MHz Pentium, I could do a
random order-256 Ls in about a minute.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Reversibly combining two bytes?
Date: 27 Jan 2000 12:21:16 -0700
From: Alan Lawrence <acl33@hermes.cam.ac.uk>
Message-ID: <94900017012060@cs26.cs.auckland.ac.nz>
References: <pgpmoose.200001261914.18654@servo>
Newsgroups: sci.crypt,sci.crypt.research
Lines: 45

Hi -

Thanks for your suggestions - in particular the use of a balanced Latin
square, that is a 256*256 grid where each row and each column contains
each of the numbers 0..255 exactly once. This seems a good solution
provided a good method of generating such squares can be found.

A method suggested was to generate two byte arrays c[0..255] and
r[0..255], both containing all the numbers from 0.255 once, permuted
randomly (and hopefully differently).; then, the <x>th row of the latin
square contains the numbers in c rotated r[x] spaces to the right. How
numbers in c, all multiplied (modulo 257, a byte of value 0 meaning 256)
by r[x]. A third byte array b[0..255] could be used to rotate the rows as
well if this would increase security. (?)

Secondly, Terry Ritter's glossary <http://www.io.com/~ritter/GLOSSARY.HTM
states that a balanced Latin Square has "massive internal state". The
"state" is presumably the large table of numbers forming said square,
however this state does not change during operation. Would a dynamic
version not be better? After the cipher byte is selected by key and
plaintext bytes, the square could be altered similarly to a dynamic
substitution cipher: swapping the rows of the table indicated by key and
plaintext, and swapping the columns also.

Is this decryptable (given the key)? In the simplest case, yes, but
imagine the case where a plaintext byte is put through such a square twice
to produce a cipher. When decrypting, we have the cipher text - the output
of the second table - and the first table (i.e. before it was altered). To
produce the second table from the first, we need the plaintext or
intermediate bytes; but to produce either of these, we need the second
table....can anyone see a way round this? (the square may even be used >2
times).

Thanks very much for any ideas
Alan Lawrence

Subject: Re: Reversibly combining two bytes?
Date: 3 Feb 2000 11:35:11 -0800
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <pgpmoose.200002031135.8351@servo>
References: <86quud\$24d\$1@blowfish.isaac.cs.berkeley.edu>
<94900017012060@cs26.cs.auckland.ac.nz>
Newsgroups: sci.crypt,sci.crypt.research
Lines: 35

[Followups set to sci.crypt.]

In article <86quud\$24d\$1@blowfish.isaac.cs.berkeley.edu>, nmm1@cus.cam.ac.uk (Ni
ck Maclaren) writes:
> In article <94900017012060@cs26.cs.auckland.ac.nz>,
> Alan Lawrence  <acl33@hermes.cam.ac.uk> wrote:
> >[re generating latin squares]

> >Secondly, Terry Ritter's glossary <http://www.io.com/~ritter/GLOSSARY.HTM
> >states that a balanced Latin Square has "massive internal state".

> The converse of having "massive internal state" is that Latin squares
> have very few degrees of freedom.  Once you have settled only a few
> of their numbers, the rest can be arranged only one way (if at all.)
> Some care is needed to avoid getting into an impossible situation!

True - but the proposed method (generating a square as a random
permutation of the rotations of a random permutation, then randomly
swapping rows and/or columns) will always generate a valid square.
Whether that square is "strong" (are all squares equally strong, or
are some, say, easier to reconstruct from cyphertext?) is another
question.  And of course the quality of the shuffling algorithm and
the PRNG used to produce the permutations is a potential problem.

Actually, there's a keying issue there, I suppose.  I was assuming
key material (probably following some kind of expansion schedule)
would be used with plaintext to index entries in the square.  Would
the key also be used in producing the square itself (say by seeding
the PRNG)?  Might this leak information about the key, particularly
in chosen-plaintext attacks?

Subject: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 7 Feb 2000 21:31:44 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <87ndk0028ic@news2.newsguy.com>
References: <FpF0vL.Jt4@bath.ac.uk>
<pgpmoose.200002031135.8351@servo>
Newsgroups: sci.crypt
Lines: 170

[We're talking about ways to generate Latin Squares, and treating
them as combining functions as suggested by Terry Ritter.  Standard
disclaimer: I'm not a cryptographer, and am definitely not
recommending this method for anything more than experimentation.]

In article <FpF0vL.Jt4@bath.ac.uk>, Tim Tyler <tt@cryogen.com> writes:
> In sci.crypt Michael Wojcik <michael.wojcik@merant.com> wrote:

> : ... the proposed method (generating a square as a random
> : permutation of the rotations of a random permutation, then randomly
> : swapping rows and/or columns) will always generate a valid square.

> This method seems interesting - mainly due to its speed.

It also has advantages in storage requirements (see my earlier post
on the subject).  We can keep an order-256 square as two or three
arrays of 256 bytes each (depending on whether we swap rows again
after generating the columns) with only a small lookup penalty,
rather than using the 64K required to maintain the entire square in
memory.

At least for encoding, that is.  For decoding, this only works if we
can generate the inverse square in the same form.

More formally:

Generate a permutation P on {0..255} (the "primary permutation"), and
a second permutation R on {0..255} (the "rotation permutation").  Form
the columns of square S as follows: for each column c, 0<=c<=255, c
is rotate(P, R[c]).  For c s.t. R[c] is 0, the column will be simply
P; for other columns, the first entry in the column will be P[R[c]],
the second P[R[c]+1 (mod 256)], etc.

The columns of the square will be a permutation on the set of all
distinct rotations of P.

Call a square constructed this way "PR-form".  Call the set of all
squares constructed from the same P, but with different R, a "family"
of PR-form squares.

(If anyone prefers different notation, be my guest.  I'm just making
this up as I go along.  Also, note of course that we can swap "row"
and "column" throughout, since transposing a Latin Square yields a
valid square with similar properties.)

Having constructed a PR-form square, we can permute its rows and/or
columns and still have a valid square.  Permuting rows just yields
another member of the same family - probably not a very interesting
result for cryptographic purposes (if any of this is).  Permuting
rows, however, generally yields a square that is *not* in PR-form.

That third permutation we'll call T, for "third" or "transform"
(since it yields a square that is no longer in PR-form).  Again, we
can represent T as an ordering of the set {0..255}.

Call a square of this soft "PRT-form".

Assuming we're using the squares as generalized combiners, in the
manner suggested by Terry Ritter - as a kind of extended XOR.  For
each plaintext byte (since we're working with squares of order 256)
we mix plaintext and a byte of (expanded) key material, using one
to index the row and the other to index the column.  For convenience
I'll assume the key byte selects the column.

As I noted in an earlier post, given three arrays P, R, and T, that's
a simple and cheap operation.  We can even gain some cache locality
benefits by doing multiple passes over a block of plaintext rather
than indexing all three arrays for one byte of plaintext and then
moving on.  (Of course, on modern general-purpose CPUs, it may not be
terribly hard to keep all three arrays in cache anyway.)

That's convenient for encoding.  For decoding, though, we either have
to construct an inverse tree (such that indexing cyphertext and key
produces plaintext), or search the column indexed by the current key
byte for the cyphertext byte (then the position in the column is the
plaintext byte).

Searching is clearly suboptimal, since it adds an O(n) linear-
search time factor to the decoding process.  It can still be done
with arrays P, R, and T, assuming the encoding square is in PRT-form.
(Or with arrays P and R if the encoding square is just PR-form.)

What we'd really like is to be able to easily generate the inverse
square S^-1, though, in PRT-form.  (It won't be in PR-form in the
general case.  As trivial pen-and-paper experimentation shows, the
inverse of a PR-form square of even order 4 isn't guaranteed to be
in PR-form itself.  That is, its columns won't be rotations of one
another.)

Question: Is the inverse of a PRT-form square always itself a PRT-
form square?  More generally, are all Latin Squares in PRT-form?
Is there a simple, low-cost construction procedure to derive the
inverse of a PRT-form square in PRT notation?

Note that if the answer to the second question is yes (all Latin
Squares are in PRT-form), then we can reduce any Latin Square of
order N to three arrays of N entries, which means that the internal
state of a square of order N is bounded by 3N, not by N^2.  (Right?)
Ie., this result helps us specify how much information there really
is in a Latin Square, since it gives us a bijective compression
function for squares.  (That tends to make me suspect the answer is
no, but a few minutes of head-scratching wasn't enough for me to
prove it one way or another.)

> It may be that the results will be systematically weak in some way,
> though.  If I planned to use this, I'd generate some squares and test
> them with a stack of orthodox s-box criteria before doing much else.

Of course.  There's also Terry Ritter's Boolean non-linearity
test for Latin Squares, which is very interesting; I plan on giving
that a try one of these days.

PRT-form squares may well be stronger (by these criteria) than simple
PR-form squares, since they don't have the column-rotation attribute,
which looks potentially troublesome.

If some PRT-squares could be identified as weak by a fast procedure,
the square generator could be sensitive to that and reject weak
squares.  Assuming the permutations are generated by a PRNG seeded
with key material (the obvious protocol), we could in theory keep
generating new squares until we got a good one.  Since the decoder
would be applying the same tests, it would arrive at the same square.

> : Whether that square is "strong" (are all squares equally strong, or
> : are some, say, easier to reconstruct from cyphertext?) is another
> : question.

> Squares are not all equally strong.  Squares of the form...
>
> x(i,j) = (i+j) mod n, (i=1->n, j=1->n) would not do at all, for example.

Right.  Another idea would be to use multiple rounds and chaining
to offset the possible weakness of one particular square.  (Of
course, for an actual working cypher, I'd assume that square-
combining would be only one technique contributing to the encoding
process.)

encoding, as Terry Ritter suggested in another post.  Generating a
new square is relatively expensive, but perhaps not prohibitive with
this method.  If we're using square-combining in a block cypher, we
might advance to a new square on every block.  With a stream cypher,
we might generate a new square after every so many bytes (how many
is an interesting question), or we might do so dynamically based on,
say, the key or plaintext (with the decoder examining output plain-
text to decide when to regenerate).

Of course, if there's a way to identify with some decent probablility
where in the cyphertext the square changed (perhaps with a chosen-
plaintext attack), then dynamically deciding when to change squares
based on the key may not be a good idea.

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

Pseudoscientific Nonsense Quote o' the Day:
From the scientific standpoint, until these energies are directly
sensed by the evolving perceptions of the individual, via the right
brain, inner-conscious, intuitive faculties, scientists will never
grasp the true workings of the universe's ubiquitous computer system.
-- Noel Huntley

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 04:53:33 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FpLHL9.MpC@bath.ac.uk>
References: <87ndk0028ic@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 51

Michael Wojcik <michael.wojcik@merant.com> wrote [a disclaimer and then]:
: In article <FpF0vL.Jt4@bath.ac.uk>, Tim Tyler <tt@cryogen.com> writes:
:> In sci.crypt Michael Wojcik <michael.wojcik@merant.com> wrote:

:> : ... the proposed method (generating a square as a random
:> : permutation of the rotations of a random permutation, then randomly
:> : swapping rows and/or columns) will always generate a valid square.

:> This method seems interesting - mainly due to its speed.

: It also has advantages in storage requirements [...]

Yes.

[much snip]

: Question: [...] are all Latin Squares in PRT-form?

!!!? ;-)

: Note that if the answer to the second question is yes (all Latin
: Squares are in PRT-form), then we can reduce any Latin Square of
: order N to three arrays of N entries, which means that the internal
: state of a square of order N is bounded by 3N, not by N^2.  (Right?)

The information content is smaller than this perhaps might suggest - since
each array entry is itself constrained.

N! x N! x N! - for the Latin Square - compared to N^(N^2) for the totally
random table.

: Ie., this result helps us specify how much information there really
: is in a Latin Square, since it gives us a bijective compression
: function for squares.  (That tends to make me suspect the answer is
: no, but a few minutes of head-scratching wasn't enough for me to
: prove it one way or another.)

Ne neither.  It's half past four in the morning, here, though.

I /may/ try again "later", since the question appears to be of
some interest - if there's even the slightest chance that it's true.

To my eyes, it seems unlikely to be true, though.  If it's /not/ true
then there may remain some possibility that *all* Latin squares generated
in this manner may be cryptographically compromised in some (unspecified)
way.
--
__________
|im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Mon, 7 Feb 2000 23:51:55 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87ohuc\$ek0\$1@nntp2.atl.mindspring.net>
References: <FpLHL9.MpC@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 27

"Tim Tyler" <tt@cryogen.com> wrote ...
[...]
: : Note that if the answer to the second question is yes (all Latin
: : Squares are in PRT-form), then we can reduce any Latin Square of
: : order N to three arrays of N entries, which means that the internal
: : state of a square of order N is bounded by 3N, not by N^2.  (Right?)
:
: The information content is smaller than this perhaps might suggest - since
: each array entry is itself constrained.
:
: N! x N! x N! - for the Latin Square - compared to N^(N^2) for the totally
: random table.                                     ^^^^^^^

But the table can't be totally random if it's to be a workable
combiner.  So I think that that latter number should be N!^N
instead of N^(N^2).  (Suppose the column coordinate corresponds
to message symbol and row coordinate to the symbol it is to be
combined with.  Then each row must be a permutation of 1..N in
order to allow later recovery of the message symbol.)

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 16:59:41 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FpMF7H.1It@bath.ac.uk>
References: <87ohuc\$ek0\$1@nntp2.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 37

r.e.s. <rs.1@mindspring.com> wrote:
: "Tim Tyler" <tt@cryogen.com> wrote ...

: : : Note that if the answer to the second question is yes (all Latin
: : : Squares are in PRT-form), then we can reduce any Latin Square of
: : : order N to three arrays of N entries, which means that the internal
: : : state of a square of order N is bounded by 3N, not by N^2.  (Right?)
: :
: : The information content is smaller than this perhaps might suggest - since
: : each array entry is itself constrained.
: :
: : N! x N! x N! - for the Latin Square - compared to N^(N^2) for the totally
: : random table.                                     ^^^^^^^

: But the table can't be totally random if it's to be a workable
: combiner. [...]

Indeed not.  Only a tiny fraction of these would be valid Latin squares.

: So I think that that latter number should be N!^N instead of N^(N^2).

That is /an/ upper bound.  It may be possible to do much better, though.
N!^(N-1) is a smaller bound - since if N-1 columns are known, the last
column is uniquely determined.

I have a figure of 161820 possible 5x5 latin squares.  This doesn't
conform to the N!^N formula very well at all (though it's the right side
of it when taken as a bound).

The last I heard, the function yielding the number of Latin squares of
size NxN was one of the unsolved problems of mathematics - since no
simple expression of it has yet been discovered.
--
__________
|im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Breast is best.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 11:03:58 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87ppaj\$oo\$1@nntp9.atl.mindspring.net>
References: <FpMF7H.1It@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 53

"Tim Tyler" <tt@cryogen.com> wrote ...
: r.e.s. <rs.1@mindspring.com> wrote:
: : "Tim Tyler" <tt@cryogen.com> wrote ...
:
: : : : Note that if the answer to the second question is yes (all Latin
: : : : Squares are in PRT-form), then we can reduce any Latin Square of
: : : : order N to three arrays of N entries, which means that the internal
: : : : state of a square of order N is bounded by 3N, not by N^2.  (Right?)
: : :
: : : The information content is smaller than this perhaps might suggest -
since
: : : each array entry is itself constrained.
: : :
: : : N! x N! x N! - for the Latin Square - compared to N^(N^2) for the
totally
: : : random table.                                     ^^^^^^^
:
: : But the table can't be totally random if it's to be a workable
: : combiner. [...]
:
: Indeed not.  Only a tiny fraction of these would be valid Latin squares.

You missed my point.
Your number N^(N^2) was said to be for a "totally random table".
I was pointing out that it's not to a totally random table that
one would want to make a comparison.

: : So I think that that latter number should be N!^N instead of N^(N^2).
:
: That is /an/ upper bound.
: It may be possible to do much better, though.
: N!^(N-1) is a smaller bound - since if N-1 columns are known, the last
: column is uniquely determined.
:
: I have a figure of 161820 possible 5x5 latin squares.  This doesn't
: conform to the N!^N formula very well at all (though it's the right side
: of it when taken as a bound).

N!^N is not supposed to be the number of Lsquares.
It's the number of possible NxN combiners, against which
one might want to *compare* the number of Lsquare combiners.

: The last I heard, the function yielding the number of Latin squares of
: size NxN was one of the unsolved problems of mathematics - since no
: simple expression of it has yet been discovered.

Right. I cite a reference for this elsewhere in the thread.

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 08 Feb 2000 12:20:15 -0700
From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov>
Message-ID: <38A06C6E.28924D35@cic-mail.lanl.gov>
References: <FpMF7H.1It@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 4

All combiners will have to be Latin squares. Not all Latin squares are
simply generated. A Latin square is the operation table of a
quasi-group. I'm not sure there's much other structure.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 15:22:28 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87q8f5\$qdo\$1@nntp9.atl.mindspring.net>
References: <38A06C6E.28924D35@cic-mail.lanl.gov>
Newsgroups: sci.crypt
Lines: 35

"Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
: All combiners will have to be Latin squares.

The Latin Square combiners appear to be a subset of all
possible combiners, corresponding to "balanced" rows &
columns in the table; so a combiner that's an Lsquare
might be *better* than one that's not, in some context,
but not all combiners need be Lsquares, as far as I can
see in common usage of the term. (But it does seem that
to be a combiner it must allow for later recovery of the
message -- resulting in N!^N possible NxN combiners.)

To take the most extreme example:
If row corresponds to enciphering-symbol and column
corresponds to message-symbol, then for an alphabet of
4 symbols even the square

0123
0123
0123
0123

yields a combiner -- but not a good one, since a given message
symbol will result in an output independent of enciphering
symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
combiners are ever desirable -- that would seem to be another
question.

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Wed, 09 Feb 2000 20:45:31 GMT
From: zapzing <zapzing@my-deja.com>
Message-ID: <87sjl9\$uc2\$1@nnrp1.deja.com>
References: <87q8f5\$qdo\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 93

In article <87q8f5\$qdo\$1@nntp9.atl.mindspring.net>,
"r.e.s." <rs.1@mindspring.com> wrote:
> "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
> : All combiners will have to be Latin squares.
>
> The Latin Square combiners appear to be a subset of all
> possible combiners, corresponding to "balanced" rows &
> columns in the table; so a combiner that's an Lsquare
> might be *better* than one that's not, in some context,
> but not all combiners need be Lsquares, as far as I can
> see in common usage of the term. (But it does seem that
> to be a combiner it must allow for later recovery of the
> message -- resulting in N!^N possible NxN combiners.)
>
> To take the most extreme example:
> If row corresponds to enciphering-symbol and column
> corresponds to message-symbol, then for an alphabet of
> 4 symbols even the square
>
> 0123
> 0123
> 0123
> 0123
>
> yields a combiner -- but not a good one, since a given message
> symbol will result in an output independent of enciphering
> symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
> combiners are ever desirable -- that would seem to be another
> question.
>

I just did not make myself clear, or something,
so I will try again (assuming that the
moderators will be patient with my lack of
communication skills).
You do *not* need a latin square,
because what you refer to as the
encyphering symbol never needs to be
recovered. The only thing you ever really
need to do is recover the message symbol
from the combined symbol.
I will give an example which is hopefully
better explained. Suppose we have two bit bytes,
then coinsider the combining function given
by the table:

m=  0123
----
e=0   3102
e=1   2130
e=2   0231
e=3   1320

Now if you had the encyphering symbol
and the combined symbol then you could
recover the message symbol, but you
could not recover the encyphering symbol
from the combined symbol and the message
symbol, but that's OK, because you never
need to do that anyway.

This sort of combining function would
be much easier to do than making a
latin square, and there are more
possibilities also, so why would you
need a latin square? That was not
a rhetorical question , I really
do want to know why, if you would
be so kind as to clue me in.

Also, If you wanted a combining
function that was more function-like
than table-like, you could use something
like this:

c=(m+e+47)^e

Then you could recover the message symbol
like this:

m=(c^e)-e-47

this would also be reversible for
message symbol recovery but not for
encrypting symbol recovery.

--
Do as thou thinkest best.

Sent via Deja.com http://www.deja.com/

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Wed, 9 Feb 2000 16:31:17 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87t0sk\$std\$1@nntp9.atl.mindspring.net>
References: <87sjl9\$uc2\$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 99

"zapzing" <zapzing@my-deja.com> wrote ...
:   "r.e.s." <rs.1@mindspring.com> wrote:
: > "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
: > : All combiners will have to be Latin squares.
: >
: > The Latin Square combiners appear to be a subset of all
: > possible combiners, corresponding to "balanced" rows &
: > columns in the table; so a combiner that's an Lsquare
: > might be *better* than one that's not, in some context,
: > but not all combiners need be Lsquares, as far as I can
: > see in common usage of the term. (But it does seem that
: > to be a combiner it must allow for later recovery of the
: > message -- resulting in N!^N possible NxN combiners.)
: >
: > To take the most extreme example:
: > If row corresponds to enciphering-symbol and column
: > corresponds to message-symbol, then for an alphabet of
: > 4 symbols even the square
: >
: > 0123
: > 0123
: > 0123
: > 0123
: >
: > yields a combiner -- but not a good one, since a given message
: > symbol will result in an output independent of enciphering
: > symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
: > combiners are ever desirable -- that would seem to be another
: > question.
: >
:
: I just did not make myself clear, or something,
: so I will try again (assuming that the
: moderators will be patient with my lack of
: communication skills).

I missed your earlier posting.  We're in total agreement
that a combiner need not be a Latin Square -- that's the
point I was making, after all.  (I have the feeling that
replied in a similar vein.)

(btw, this ng is unmoderated)

: You do *not* need a latin square,
: because what you refer to as the
: encyphering symbol never needs to be
: recovered. The only thing you ever really
: need to do is recover the message symbol
: from the combined symbol.
: I will give an example which is hopefully
: better explained. Suppose we have two bit bytes,
: then coinsider the combining function given
: by the table:
:
:   m=  0123
:       ----
: e=0   3102
: e=1   2130
: e=2   0231
: e=3   1320
:
: Now if you had the encyphering symbol
: and the combined symbol then you could
: recover the message symbol, but you
: could not recover the encyphering symbol
: from the combined symbol and the message
: symbol, but that's OK, because you never
: need to do that anyway.
:
: This sort of combining function would
: be much easier to do than making a
: latin square, and there are more
: possibilities also, so why would you
: need a latin square? That was not
: a rhetorical question , I really
: do want to know why, if you would
: be so kind as to clue me in.

assume the "you" in the above sentence is generic,
since I didn't say that a Latin Square is needed--
I said that one is *not* needed, and that it's
a separate issue as to whether a non-LatinSquare
combiner would be "good" in a given context.

My 2-cents about the general situation, though, is
that if a column is not a permutation of the entire
output symbol alphabet, then some output symbols
may tend to be more/less frequent than others when
enciphering the same message symbol, and that might
well be a weakness wrt frequency anaysis.

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Thu, 10 Feb 2000 08:19:12 -0700
From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov>
Message-ID: <38A2D6F0.91FCC44A@cic-mail.lanl.gov>
References: <87t0sk\$std\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 101

"r.e.s." wrote:

> "zapzing" <zapzing@my-deja.com> wrote ...
> :   "r.e.s." <rs.1@mindspring.com> wrote:
> : > "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
> : > : All combiners will have to be Latin squares.
> : >
> : > The Latin Square combiners appear to be a subset of all
> : > possible combiners, corresponding to "balanced" rows &
> : > columns in the table; so a combiner that's an Lsquare
> : > might be *better* than one that's not, in some context,
> : > but not all combiners need be Lsquares, as far as I can
> : > see in common usage of the term. (But it does seem that
> : > to be a combiner it must allow for later recovery of the
> : > message -- resulting in N!^N possible NxN combiners.)
> : >
> : > To take the most extreme example:
> : > If row corresponds to enciphering-symbol and column
> : > corresponds to message-symbol, then for an alphabet of
> : > 4 symbols even the square
> : >
> : > 0123
> : > 0123
> : > 0123
> : > 0123
> : >
> : > yields a combiner -- but not a good one, since a given message
> : > symbol will result in an output independent of enciphering
> : > symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
> : > combiners are ever desirable -- that would seem to be another
> : > question.
> : >
> :
> : I just did not make myself clear, or something,
> : so I will try again (assuming that the
> : moderators will be patient with my lack of
> : communication skills).
>
> I missed your earlier posting.  We're in total agreement
> that a combiner need not be a Latin Square -- that's the
> point I was making, after all.  (I have the feeling that
> your remarks are really intended for Tony, to whom I had
> replied in a similar vein.)
>
> (btw, this ng is unmoderated)
>
> : You do *not* need a latin square,
> : because what you refer to as the
> : encyphering symbol never needs to be
> : recovered. The only thing you ever really
> : need to do is recover the message symbol
> : from the combined symbol.
> : I will give an example which is hopefully
> : better explained. Suppose we have two bit bytes,
> : then coinsider the combining function given
> : by the table:
> :
> :   m=  0123
> :       ----
> : e=0   3102
> : e=1   2130
> : e=2   0231
> : e=3   1320
> :
> : Now if you had the encyphering symbol
> : and the combined symbol then you could
> : recover the message symbol, but you
> : could not recover the encyphering symbol
> : from the combined symbol and the message
> : symbol, but that's OK, because you never
> : need to do that anyway.
> :
> : This sort of combining function would
> : be much easier to do than making a
> : latin square, and there are more
> : possibilities also, so why would you
> : need a latin square? That was not
> : a rhetorical question , I really
> : do want to know why, if you would
> : be so kind as to clue me in.
>
> assume the "you" in the above sentence is generic,
> since I didn't say that a Latin Square is needed--
> I said that one is *not* needed, and that it's
> a separate issue as to whether a non-LatinSquare
> combiner would be "good" in a given context.
>
> My 2-cents about the general situation, though, is
> that if a column is not a permutation of the entire
> output symbol alphabet, then some output symbols
> may tend to be more/less frequent than others when
> enciphering the same message symbol, and that might
> well be a weakness wrt frequency anaysis.

That's the point. With Latin squares, the probabilities get more
uniform.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Thu, 10 Feb 2000 11:23:23 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-1002001123230001@dial-243-002.itexas.net>
References: <38A2D6F0.91FCC44A@cic-mail.lanl.gov>
Newsgroups: sci.crypt
Lines: 15

In article <38A2D6F0.91FCC44A@cic-mail.lanl.gov>, ttw@lanl.gov wrote:

> That's the point. With Latin squares, the probabilities get more
> uniform.

Consider Swagman, which specifies such a square for the key.  I hear that
there is a Lazy Swagman, but figure it violates some rule.  Perhaps
someone will fill in the details.

Obviously a Swagman is limited by design to a fairly small key block, but
the idea of trying to obscure the key components is the same for any size.
--
If Al Gore wants to be inventor of the internet, complain that he
did a lousy job.  If he admits to not doing much, complain that he
is a slacker. Now, do we want him in charge of security?

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Thu, 10 Feb 2000 21:16:05 GMT
From: zapzing <zapzing@my-deja.com>
Message-ID: <87v9qf\$u1e\$1@nnrp1.deja.com>
References: <87t0sk\$std\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 120

In article <87t0sk\$std\$1@nntp9.atl.mindspring.net>,
"r.e.s." <rs.1@mindspring.com> wrote:
> "zapzing" <zapzing@my-deja.com> wrote ...
> :   "r.e.s." <rs.1@mindspring.com> wrote:
> : > "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
> : > : All combiners will have to be Latin squares.
> : >
> : > The Latin Square combiners appear to be a subset of all
> : > possible combiners, corresponding to "balanced" rows &
> : > columns in the table; so a combiner that's an Lsquare
> : > might be *better* than one that's not, in some context,
> : > but not all combiners need be Lsquares, as far as I can
> : > see in common usage of the term. (But it does seem that
> : > to be a combiner it must allow for later recovery of the
> : > message -- resulting in N!^N possible NxN combiners.)
> : >
> : > To take the most extreme example:
> : > If row corresponds to enciphering-symbol and column
> : > corresponds to message-symbol, then for an alphabet of
> : > 4 symbols even the square
> : >
> : > 0123
> : > 0123
> : > 0123
> : > 0123
> : >
> : > yields a combiner -- but not a good one, since a given message
> : > symbol will result in an output independent of enciphering
> : > symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
> : > combiners are ever desirable -- that would seem to be another
> : > question.
> : >
> :
> : I just did not make myself clear, or something,
> : so I will try again (assuming that the
> : moderators will be patient with my lack of
> : communication skills).
>
> I missed your earlier posting.  We're in total agreement
> that a combiner need not be a Latin Square -- that's the
> point I was making, after all.  (I have the feeling that
> your remarks are really intended for Tony, to whom I had
> replied in a similar vein.)
>
> (btw, this ng is unmoderated)

Newsgroups come and go so quickly around here.
This thread started in sci.crypt.reserach and then
hyperspace jumped over here, and I did not
bother to check, sorry.

>
> : You do *not* need a latin square,
> : because what you refer to as the
> : encyphering symbol never needs to be
> : recovered. The only thing you ever really
> : need to do is recover the message symbol
> : from the combined symbol.
> : I will give an example which is hopefully
> : better explained. Suppose we have two bit bytes,
> : then coinsider the combining function given
> : by the table:
> :
> :   m=  0123
> :       ----
> : e=0   3102
> : e=1   2130
> : e=2   0231
> : e=3   1320
> :
> : Now if you had the encyphering symbol
> : and the combined symbol then you could
> : recover the message symbol, but you
> : could not recover the encyphering symbol
> : from the combined symbol and the message
> : symbol, but that's OK, because you never
> : need to do that anyway.
> :
> : This sort of combining function would
> : be much easier to do than making a
> : latin square, and there are more
> : possibilities also, so why would you
> : need a latin square? That was not
> : a rhetorical question , I really
> : do want to know why, if you would
> : be so kind as to clue me in.
>
> assume the "you" in the above sentence is generic,
> since I didn't say that a Latin Square is needed--
> I said that one is *not* needed, and that it's
> a separate issue as to whether a non-LatinSquare
> combiner would be "good" in a given context.
>
> My 2-cents about the general situation, though, is
> that if a column is not a permutation of the entire
> output symbol alphabet, then some output symbols
> may tend to be more/less frequent than others when
> enciphering the same message symbol, and that might
> well be a weakness wrt frequency anaysis.
>

Yes, I see now. In the example I gave, if
the message was composed of all ones,
the output would be one fifty percent of
the time, assuming an evenly balanced
encrypting symbol. If that sort of combining
function were used, it would have to be used in
conjunction with other techniques, such as
pre or post block ciphering, with random noise

--
Do as thou thinkest best.

Sent via Deja.com http://www.deja.com/

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Thu, 10 Feb 2000 14:28:54 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FppxK6.6uv@bath.ac.uk>
References: <87sjl9\$uc2\$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 58

zapzing <zapzing@my-deja.com> wrote:

: You do *not* need a latin square,
: because what you refer to as the
: encyphering symbol never needs to be
: recovered. The only thing you ever really
: need to do is recover the message symbol
: from the combined symbol.
: I will give an example which is hopefully
: better explained. Suppose we have two bit bytes,
: then coinsider the combining function given
: by the table:

:   m=  0123
:       ----
: e=0   3102
: e=1   2130
: e=2   0231
: e=3   1320

: Now if you had the encyphering symbol
: and the combined symbol then you could
: recover the message symbol, but you
: could not recover the encyphering symbol
: from the combined symbol and the message
: symbol, but that's OK, because you never
: need to do that anyway.

: This sort of combining function would
: be much easier to do than making a
: latin square, and there are more
: possibilities also, so why would you
: need a latin square? That was not
: a rhetorical question , I really
: do want to know why, if you would
: be so kind as to clue me in.

To supplement r.e.s.'s post, perhaps you don't *need* a Latin square
- but a Latin square is *desirable*.

If you *don't* have a Latin square, you may be doing the equivalent
of wasting some of your keys.

If you were to waste *all* your keys, you may wind up with something like:

m=  0123
----
e=0   0312
e=1   0312
e=2   0312
e=3   0312 :-(

A Latin square avoids this sort of thing to the maximum possible degree.
--
__________
|im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

Legalise IT.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 04:38:17 GMT
From: zapzing <zapzing@my-deja.com>
Message-ID: <8803np\$gfm\$1@nnrp1.deja.com>
References: <FppxK6.6uv@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 91

In article <FppxK6.6uv@bath.ac.uk>,
tt@cryogen.com wrote:
> zapzing <zapzing@my-deja.com> wrote:
>
> : You do *not* need a latin square,
> : because what you refer to as the
> : encyphering symbol never needs to be
> : recovered. The only thing you ever really
> : need to do is recover the message symbol
> : from the combined symbol.
> : I will give an example which is hopefully
> : better explained. Suppose we have two bit bytes,
> : then coinsider the combining function given
> : by the table:
>
> :   m=  0123
> :       ----
> : e=0   3102
> : e=1   2130
> : e=2   0231
> : e=3   1320
>
> : Now if you had the encyphering symbol
> : and the combined symbol then you could
> : recover the message symbol, but you
> : could not recover the encyphering symbol
> : from the combined symbol and the message
> : symbol, but that's OK, because you never
> : need to do that anyway.
>
> : This sort of combining function would
> : be much easier to do than making a
> : latin square, and there are more
> : possibilities also, so why would you
> : need a latin square? That was not
> : a rhetorical question , I really
> : do want to know why, if you would
> : be so kind as to clue me in.
>
> To supplement r.e.s.'s post, perhaps you don't *need* a Latin square
> - but a Latin square is *desirable*.
>
> If you *don't* have a Latin square, you may be doing the equivalent
> of wasting some of your keys.
>
> If you were to waste *all* your keys, you may wind up with something like:
>
>   m=  0123
>       ----
> e=0   0312
> e=1   0312
> e=2   0312
> e=3   0312 :-(
>
> A Latin square avoids this sort of thing to the maximum possible degree.

I see what you mean, now. But your example was
a  bit extream, wasn't it? If we generated a
combining function by making the rows each
be a random permutation of 0..255 (for example)
then the degree of wastage wouldn't be _that_ great,
would it? Perhaps the wastage could be offset by the
greater entropy that kind of function.

But if you insist on using a Latin square,
and you don't mean Ricky Martin,
you might consider generating it in this way:

Say bytes are eight bits. first take the message
symbol and send ti through some sort of
reversible substitution, such as a reversible
8 bit to 8 bit s_box. then split both the
message symbol and the encrypting symbol
into 4-bit sections. Combine each 4 bit segment
with a latin square (4-bit to 4-bit) and then
send the result through another (different)
8 bit to 8 bit reversible s-box.

Each of the 4 bit Latin squares could be
selected from  a "stable" of standard
latin squares, according to the key,
and the s-boxes could also be selected
according to the key. This would give
you alot more entropy.

--
Do as thou thinkest best.

Sent via Deja.com http://www.deja.com/

Originator: mww@lorelei-n

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 11 Feb 2000 18:51:36 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <881lno020gn@news2.newsguy.com>
References: <87sjl9\$uc2\$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 61

In article <87sjl9\$uc2\$1@nnrp1.deja.com>, zapzing <zapzing@my-deja.com> writes:

> I just did not make myself clear, or something,
> so I will try again (assuming that the
> moderators will be patient with my lack of
> communication skills).

Sorry - I meant to respond to your post but lost it.  I tend to run
a bit behind on news reading.

(sci.crypt is an unmoderated group.  sci.crypt.research is
moderated.)

> You do *not* need a latin square,
> because what you refer to as the
> encyphering symbol never needs to be
> recovered. The only thing you ever really
> need to do is recover the message symbol
> from the combined symbol.

Yes, and this is an interesting idea - see my response to an
earlier post by r.e.s.

> This sort of combining function would
> be much easier to do than making a
> latin square, and there are more
> possibilities also, so why would you
> need a latin square? That was not
> a rhetorical question , I really
> do want to know why, if you would
> be so kind as to clue me in.

Well, I'm not convinced it's "much easier to do than making a latin
square", since we're discussing a fast construction procedure  for a
subset of Latin Squares.  I don't offhand see a significantly faster
way of producing nonbalanced combiners in this form (with the same
memory savings as the PRT method I proposed).

strong arguments for using Latin Squares as combiners yet (in this
but at the moment most of us are just playing with the idea.

Personally, I'm not persuaded we need new combiners at all, as far as
practical cryptography goes.  Existing methods certainly look good
enough for *my* purposes; those with more stringent threat models may
be looking elsewhere, but the state of public crypto is such that
inventing new encypherment methods doesn't appear to be a priority.
This is just a mental exercise, as far as I'm concerned.  Others may
feel different, of course.

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

If Mokona means for us to eat this, I, a gentle person, will become
angry!  -- Umi (CLAMP & unknown translator), _Magic Knight Rayearth_

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 21:45:57 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <38a482c0.3422814@news.io.com>
References: <881lno020gn@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 73

On 11 Feb 2000 18:51:36 GMT, in <881lno020gn@news2.newsguy.com>, in
sci.crypt michael.wojcik@merant.com (Michael Wojcik) wrote:

>[...]
>strong arguments for using Latin Squares as combiners yet (in this
>but at the moment most of us are just playing with the idea.

My main reason for using combiners is to complicate or eliminate
known-plaintext or defined-plaintext attacks.  Normally, in a stream
cipher using an additive combiner, known-plaintext (or just "guessed
plaintext") will immediately reveal the keystream or confusion stream.
Then the opponents start to work on the key generator.  A keyed
nonlinear combiner at least prevents easy access.

The reason for having *Latin square* combiners is to prevent leakage
through either input port.  We certainly don't want leakage from
plaintext.  But if we choose things at random I think it would be
common to find some amount of correlation between output and key under
known-plaintext conditions.  Then the opponents can at least start to
work on the key generator.

I recommend using keyed nonlinear combiners even for "one time pad"
systems.  The reason for this is that neither user nor designer can
test that there is no pattern in the confusion sequence.  The
randomness tests we have can be passed by PSEUDO random generators,
which can be attacked.  So if by some mischance the "really random"
generator is not as random as one hoped, the combiner prevents easy
cipher attack.

the confusion sequence, it has *strengthened* the cipher against that
attack.  This increase in strength can then be the basis for a
decrease in complexity of the confusion generator itself.

>Personally, I'm not persuaded we need new combiners at all, as far as
>practical cryptography goes.  Existing methods certainly look good
>enough for *my* purposes; those with more stringent threat models may
>be looking elsewhere, but the state of public crypto is such that
>inventing new encypherment methods doesn't appear to be a priority.
>This is just a mental exercise, as far as I'm concerned.  Others may
>feel different, of course.

I think the massive use of just a few well-known ciphers simply begs
attack.  These ciphers have been around for a while, and attacks on
them can use everything in the academic literature *plus* whatever
insights long and concentrated work can provide.  Those ciphers could
have been broken years ago, and if the opponents just kept quiet about
that, people would still use those ciphers.  Well, people *are* still
using them.  We do not and can not know whether or not the ciphers are
broken on a regular basis.

It is not only in theory but also in practice that we do not know if
our ciphers are secure.  But we *do* know that if our ciphers are
*not* secure, that situation is not going to change itself.  Indeed,
we know the situation will change only if *we* act to change our
ciphers.  I think that is a fine reason to continue the development of
a broad array of new cipher designs.

Note that the major investment involved in breaking a cipher could be
intellectual time and effort already past.  Success might well be
automated, and thus available at will simply by acquiring data and
starting the program.  Cipher breaking may be cheap and easy and thus
practical even for rather casual data.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 18:21:58 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <882g5q\$k0k\$1@nntp9.atl.mindspring.net>
References: <38a482c0.3422814@news.io.com>
Newsgroups: sci.crypt
Lines: 32

"Terry Ritter" <ritter@io.com> wrote ...
[...]
: My main reason for using combiners is to complicate or eliminate
: known-plaintext or defined-plaintext attacks.  Normally, in a stream
: cipher using an additive combiner, known-plaintext (or just "guessed
: plaintext") will immediately reveal the keystream or confusion stream.
: Then the opponents start to work on the key generator.  A keyed
: nonlinear combiner at least prevents easy access.
:
: The reason for having *Latin square* combiners is to prevent leakage
: through either input port.  We certainly don't want leakage from
: plaintext.  But if we choose things at random I think it would be
: common to find some amount of correlation between output and key under
: known-plaintext conditions.  Then the opponents can at least start to
: work on the key generator.
[...]

a subset of Latin Square combiners.  I've looked at your
on-line Glossary to see what you mean by "nonlinear combiner",
but the definition of "linear" is not really clear to me in
this context. The confusion is surely mine, but I have trouble
interpreting the above paragraphs because I'm not sure where
you draw the line between linear & nonlinear combiners. E.g.,
do you consider all Latin Square combiners to be linear?

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 07:50:26 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <38a51067.4922715@news.io.com>
References: <882g5q\$k0k\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 74

On Fri, 11 Feb 2000 18:21:58 -0800, in
<882g5q\$k0k\$1@nntp9.atl.mindspring.net>, in sci.crypt "r.e.s."
<rs.1@mindspring.com> wrote:

>"Terry Ritter" <ritter@io.com> wrote ...
>[...]
>: My main reason for using combiners is to complicate or eliminate
>: known-plaintext or defined-plaintext attacks.  Normally, in a stream
>: cipher using an additive combiner, known-plaintext (or just "guessed
>: plaintext") will immediately reveal the keystream or confusion stream.
>: Then the opponents start to work on the key generator.  A keyed
>: nonlinear combiner at least prevents easy access.
>:
>: The reason for having *Latin square* combiners is to prevent leakage
>: through either input port.  We certainly don't want leakage from
>: plaintext.  But if we choose things at random I think it would be
>: common to find some amount of correlation between output and key under
>: known-plaintext conditions.  Then the opponents can at least start to
>: work on the key generator.
>[...]
>
>a subset of Latin Square combiners.

Yes, and are clearly linear as mod 2 polys (XOR) or mod n (n probably
= 2**m for addition).  This is not just theoretical weakness.

>I've looked at your
>on-line Glossary to see what you mean by "nonlinear combiner",
>but the definition of "linear" is not really clear to me in
>this context. The confusion is surely mine, but I have trouble
>interpreting the above paragraphs because I'm not sure where
>you draw the line between linear & nonlinear combiners. E.g.,
>do you consider all Latin Square combiners to be linear?

I think that's a very reasonable question, if perhaps less easily
answered.  In my experience, the distinction between "linear" and
"nonlinear" is not as clear as one might like throughout cryptography.
Presumably any form of linearity counts, and there can be many such
forms.

We might consider permutation itself to be linear, but I think to do
so we must have access to the whole permutation.  If we know only part
of it, or none at all (e.g., one term of larger equation), we may not
be able to manipulate this "linearity" in a useful linear way.  The
S-boxes in DES are composed of permutations, yet they are always
called "nonlinear."

One way to think about linearity is the ease with which one can
extrapolate from a known transformation (from domain value to range
value) to expose an unknown transformation (given some other range or
domain value).  This is clearly trivial with XOR or (+), less trivial
with a random permutation of 256 values, and much less trivial when
multiple keyed transformations are involved in an equation.

I have also done some work comparing permutations in Latin squares
with respect to "Boolean function nonlinearity."  This is basically a
distance measure with respect to "affine Boolean functions" or "Walsh
functions," for any particular bit-position in such a table.  (An
"8-bit" permutation with 256 elements would have 8 Boolean function
nonlinearity values, of which we would typically take the smallest as
the indicator of the weakest bit in the permutation.)  Each result
tells us how well a bit-string can be modeled by the best linear
approximation to that sequence.  For the 256-bit sequences generated
by random "8-bit" permutations, typically something like 100 bits must
change to reach the linear Boolean function which is closest to any of
the 8 measured bit sequences.  I see this as one form of strength.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Originator: mww@lorelei-n

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 11 Feb 2000 18:41:39 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <881l5301uv9@news2.newsguy.com>
References: <87q8f5\$qdo\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 40

In article <87q8f5\$qdo\$1@nntp9.atl.mindspring.net>, "r.e.s." <rs.1@mindspring.com> writes:
> "Tony T. Warnock" <u091889@cic-mail.lanl.gov> wrote ...
> : All combiners will have to be Latin squares.

> The Latin Square combiners appear to be a subset of all
> possible combiners, corresponding to "balanced" rows &
> columns in the table; so a combiner that's an Lsquare
> might be *better* than one that's not, in some context,
> but not all combiners need be Lsquares, as far as I can
> see in common usage of the term. (But it does seem that
> to be a combiner it must allow for later recovery of the
> message -- resulting in N!^N possible NxN combiners.)

> [example snipped]
> yields a combiner -- but not a good one, since a given message
> symbol will result in an output independent of enciphering
> symbol.  Whether less-extreme non-balanced (i.e. non-Lsquare)
> combiners are ever desirable -- that would seem to be another
> question.

It's an interesting idea, since a non-balanced combiner (as you or
someone else pointed out in an earlier post, which unfortunately I've
misplaced) lets you retrieve the message but not (completely) the
key.  There are potential advantages to a scheme which prevented
retrieval of the key even with plaintext-cyphertext pairs - it would
keep that particular key secret even if some messages were exposed.
It would mean that more than one key could be used to decode a
message, but given a sufficiently large keyspace relative to the
amount of key equivalency, that might not be a problem.

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

This is a "rubbering action game," a 2D platformer where you control a
girl equipped with an elastic rope with a fishing hook at the end.
-- review of _Umihara Kawase Shun_ for the Sony Playstation

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 15:02:39 -0700
From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov>
Message-ID: <38A486FF.52B2BA15@cic-mail.lanl.gov>
References: <881l5301uv9@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 4

Latin squares are really only useful if the input alphabet and key
alphabet are the same size. The DES S-boxes don't have the same sizes
but seem to work OK.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 01:36:12 GMT
From: zapzing <zapzing@my-deja.com>
Message-ID: <882ded\$6q9\$1@nnrp1.deja.com>
References: <38A486FF.52B2BA15@cic-mail.lanl.gov>
Newsgroups: sci.crypt
Lines: 31

In article <38A486FF.52B2BA15@cic-mail.lanl.gov>,
ttw@lanl.gov wrote:
> Latin squares are really only useful if the input alphabet and key
> alphabet are the same size. The DES S-boxes don't have the same sizes
> but seem to work OK.
>
>

Well. actually that is true by definition,
since a latin *square* must be square.
But your post gives me an interesting idea.
What if we generalize it to a latin *rectangle*?

For example, the message symbol could be
one eight bit byte, and the encrypting
symbol could be *two* eight bit bytes.
The latin rectangle would be a
256 X 65536 array of bytes,
arrainged so that every column
has one instance of every byte, and
every row has 256 instances of every byte.

OK so maybe that is a bit large for memory,
but you get the idea.

--
Do as thou thinkest best.

Sent via Deja.com http://www.deja.com/

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 07:51:28 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <38a5109f.4978442@news.io.com>
References: <882ded\$6q9\$1@nnrp1.deja.com>
Newsgroups: sci.crypt
Lines: 28

On Sat, 12 Feb 2000 01:36:12 GMT, in <882ded\$6q9\$1@nnrp1.deja.com>, in
sci.crypt zapzing <zapzing@my-deja.com> wrote:

>In article <38A486FF.52B2BA15@cic-mail.lanl.gov>,
>  ttw@lanl.gov wrote:
>> Latin squares are really only useful if the input alphabet and key
>> alphabet are the same size. The DES S-boxes don't have the same sizes
>> but seem to work OK.
>>
>>
>
>Well. actually that is true by definition,
>since a latin *square* must be square.
>But your post gives me an interesting idea.
>What if we generalize it to a latin *rectangle*?

I suppose much would depend upon how it is used.  In many cases it
might be better to use multiple Latin squares:  If we just drop in
multiple occurrences of values at random, we are almost guaranteed to
have some grouping which will highlight some locality of input values.
minimized by the enforced spacing of different tables.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sun, 13 Feb 2000 01:59:23 GMT
From: zapzing <zapzing@my-deja.com>
References: <38a5109f.4978442@news.io.com>
Newsgroups: sci.crypt
Lines: 52

In article <38a5109f.4978442@news.io.com>,
ritter@io.com (Terry Ritter) wrote:
>
> On Sat, 12 Feb 2000 01:36:12 GMT, in <882ded\$6q9\$1@nnrp1.deja.com>, in
> sci.crypt zapzing <zapzing@my-deja.com> wrote:
>
> >In article <38A486FF.52B2BA15@cic-mail.lanl.gov>,
> >  ttw@lanl.gov wrote:
> >> Latin squares are really only useful if the input alphabet and key
> >> alphabet are the same size. The DES S-boxes don't have the same sizes
> >> but seem to work OK.
> >>
> >>
> >
> >Well. actually that is true by definition,
> >since a latin *square* must be square.
> >But your post gives me an interesting idea.
> >What if we generalize it to a latin *rectangle*?
>
> I suppose much would depend upon how it is used.  In many cases it
> might be better to use multiple Latin squares:  If we just drop in
> multiple occurrences of values at random, we are almost guaranteed to
> have some grouping which will highlight some locality of input values.
> This would leak more information than would happen if groupings were
> minimized by the enforced spacing of different tables.
>

I believe that is correct. If the column number
is the message and the row number is the
encrypting symbol, then if we made up
the "combining rectangle" by stacking up
rows that are permutations of the bytes from
0..255, then we would not be guaranteed that
every column would contain 256 instances
exactly of every byte, but the imbalance would
be much less severe.

And your idea of using multiple latin squares
could be used to, we could use a Latin
square, followed by a generalized combining
function, followed by a latin square. That
would make an encrypting symbol of an
effective size of three bytes. no highlited
input values, and more effective entropy
than a generalized combining function.

--
Do as thou thinkest best.

Sent via Deja.com http://www.deja.com/

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 08 Feb 2000 20:52:53 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0802002052530001@dial-243-031.itexas.net>
References: <FpMF7H.1It@bath.ac.uk>
Newsgroups: sci.crypt
Lines: 28

In article <FpMF7H.1It@bath.ac.uk>, tt@cryogen.com wrote:

> r.e.s. <rs.1@mindspring.com> wrote:
> : "Tim Tyler" <tt@cryogen.com> wrote ...
>
> : So I think that that latter number should be N!^N instead of N^(N^2).
>
> That is /an/ upper bound.  It may be possible to do much better, though.
> N!^(N-1) is a smaller bound - since if N-1 columns are known, the last
> column is uniquely determined.
>
> I have a figure of 161820 possible 5x5 latin squares.  This doesn't
> conform to the N!^N formula very well at all (though it's the right side
> of it when taken as a bound).
>
> The last I heard, the function yielding the number of Latin squares of
> size NxN was one of the unsolved problems of mathematics - since no
> simple expression of it has yet been discovered.
> --
I see that the number of different squares in which there are no two rows
alike and no two columns alike might be N!*N, at least it works out that
way for N=3.  Maybe I missed something, but for N=3, there are only 18
possibilities, N=4 is 48, and N=5 is 600, according to my calculations.
Where you get 161820 for N=5 puzzles me.
--
Life is full of upturns and downturns, with varying periods of
stabilty mixed in.  It is a fool's errand to assume that what is
happening any one day predicts the same as a constant future.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 21:14:59 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87qt47\$663\$1@nntp9.atl.mindspring.net>
References: <jgfunj-0802002052530001@dial-243-031.itexas.net>
Newsgroups: sci.crypt
Lines: 38

"wtshaw" <jgfunj@vgrknf.arg> wrote ...
: "Tim Tyler" tt@cryogen.com wrote:
: > r.e.s. <rs.1@mindspring.com> wrote:
: > : So I think that that latter number should be N!^N instead of N^(N^2).

(I didn't say that N!^N is the number of LSquares.
It's the number of possible NxN "reversible combiners".)

: > That is /an/ upper bound.  It may be possible to do much better, though.
: > N!^(N-1) is a smaller bound - since if N-1 columns are known, the last
: > column is uniquely determined.
: >
: > I have a figure of 161820 possible 5x5 latin squares.  This doesn't
: > conform to the N!^N formula very well at all (though it's the right side
^^^^^^^^^^^^^^^^^^^^^^^^^^^
(N!^N was not supposed to be the number of Lsquares!!!)

: > of it when taken as a bound).
: > The last I heard, the function yielding the number of Latin squares of
: > size NxN was one of the unsolved problems of mathematics - since no
: > simple expression of it has yet been discovered.
: > --
: I see that the number of different squares in which there are no two rows
: alike and no two columns alike might be N!*N, at least it works out that
: way for N=3.  Maybe I missed something, but for N=3, there are only 18
: possibilities, N=4 is 48, and N=5 is 600, according to my calculations.
: Where you get 161820 for N=5 puzzles me.

161280 for N=5 is correct according to my references.

The number of Latin Squares of order N, for N=1..10:
1,2,12,576,161280,812851200,61479419904000,108776032459082956800,
5524751496156892842531225600,9982437658213039871725064756920320000
Source:
http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Wed, 09 Feb 2000 09:22:05 -0600
From: jgfunj@vgrknf.arg (wtshaw)
Message-ID: <jgfunj-0902000922050001@dial-243-007.itexas.net>
References: <87qt47\$663\$1@nntp9.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 22

In article <87qt47\$663\$1@nntp9.atl.mindspring.net>, "r.e.s."
<rs.1@mindspring.com> wrote:
>
> 161280 for N=5 is correct according to my references.
>
> The number of Latin Squares of order N, for N=1..10:
> 1,2,12,576,161280,812851200,61479419904000,108776032459082956800,
> 5524751496156892842531225600,9982437658213039871725064756920320000
> Source:
> http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?An
> um=002860

Maybe some midnight math is involved on my part, that which does not need
to see the light of day, so starting from scratch with N=3, there are 6
possibilitites for the first row, abc, acb, bac, bca, cab, cba.  For the
second row, the selection of the first row limits the choices, so with abc
in the first row, you can have bca and cab. Then, 6x2=12 is right for
total possible squares for N=3.
--
Life is full of upturns and downturns, with varying periods of
stabilty mixed in.  It is a fool's errand to assume that what is
happening any one day predicts the same as a constant future.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 8 Feb 2000 07:27:00 GMT
From: oetting@ghtmail.cr.usgs.gov (Dan O.)
Message-ID: <oetting-0802000027020001@gldppp93.cr.usgs.gov>
References: <87ndk0028ic@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 76

In article <87ndk0028ic@news2.newsguy.com>, michael.wojcik@merant.com wrote:

> [We're talking about ways to generate Latin Squares, and treating
> them as combining functions as suggested by Terry Ritter.  Standard
> disclaimer: I'm not a cryptographer, and am definitely not
> recommending this method for anything more than experimentation.]
>
> In article <FpF0vL.Jt4@bath.ac.uk>, Tim Tyler <tt@cryogen.com> writes:
> > In sci.crypt Michael Wojcik <michael.wojcik@merant.com> wrote:
>
> > : ... the proposed method (generating a square as a random
> > : permutation of the rotations of a random permutation, then randomly
> > : swapping rows and/or columns) will always generate a valid square.
>
> > This method seems interesting - mainly due to its speed.
>
> It also has advantages in storage requirements (see my earlier post
> on the subject).  We can keep an order-256 square as two or three
> arrays of 256 bytes each (depending on whether we swap rows again
> after generating the columns) with only a small lookup penalty,
> rather than using the 64K required to maintain the entire square in
> memory.
>
> At least for encoding, that is.  For decoding, this only works if we
> can generate the inverse square in the same form.
>
> More formally:
>
> Generate a permutation P on {0..255} (the "primary permutation"), and
> a second permutation R on {0..255} (the "rotation permutation").  Form
> the columns of square S as follows: for each column c, 0<=c<=255, c
> is rotate(P, R[c]).  For c s.t. R[c] is 0, the column will be simply
> P; for other columns, the first entry in the column will be P[R[c]],
> the second P[R[c]+1 (mod 256)], etc.

What you are discribing is a permutation of a base Latin Square. Let L be
a base latin square {ie: L(r,c) = r+c mod 256}. Let P, R, T be
premutations on {0..255}. Then the latin square for encryption is t =
Le(r,c) = T(L(R(r),C(c))). And the inverse function for decryption in the
form r = Ld(t,c) = R'(L'(T'(t),C'(c)) where R', C', T' are the inverse
permutations of R, C, T respectivly and L' is the inverse of the base
latin square L [ie: L'(t,c) = t-c mod 256 = L(t,-c mod 256)].

> Question: Is the inverse of a PRT-form square always itself a PRT-
> form square?  More generally, are all Latin Squares in PRT-form?
> Is there a simple, low-cost construction procedure to derive the
> inverse of a PRT-form square in PRT notation?

Yes. No. Yes.

> Note that if the answer to the second question is yes (all Latin
> Squares are in PRT-form), then we can reduce any Latin Square of
> order N to three arrays of N entries, which means that the internal
> state of a square of order N is bounded by 3N, not by N^2.  (Right?)
> Ie., this result helps us specify how much information there really
> is in a Latin Square, since it gives us a bijective compression
> function for squares.  (That tends to make me suspect the answer is
> no, but a few minutes of head-scratching wasn't enough for me to
> prove it one way or another.)

For a 4x4 latin square there are exactly 2 unique base squares using PRT form:
sum(r,c) = 0 1 2 3
1 2 3 0
2 3 0 1
3 0 1 2

xor(r,c) = 0 1 2 3
1 0 3 2
2 3 0 1
3 2 1 0

The latin square xor() is also unique in the PR form whereas sum() has 3
variations in the PR form.

--
Dan Oetting <oetting@ghtmail.cr.usgs.gov>

Originator: mww@lorelei-n

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 11 Feb 2000 18:24:39 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <881k5701sgm@news2.newsguy.com>
References: <oetting-0802000027020001@gldppp93.cr.usgs.gov>
Newsgroups: sci.crypt
Lines: 42

In article <oetting-0802000027020001@gldppp93.cr.usgs.gov>, oetting@ghtmail.cr.usgs.gov (Dan O.) writes:
> In article <87ndk0028ic@news2.newsguy.com>, michael.wojcik@merant.com wrote:
>
> > Generate a permutation P on {0..255} (the "primary permutation"), and
> > a second permutation R on {0..255} (the "rotation permutation").  Form
> > the columns of square S as follows: for each column c, 0<=c<=255, c
> > is rotate(P, R[c]).  For c s.t. R[c] is 0, the column will be simply
> > P; for other columns, the first entry in the column will be P[R[c]],
> > the second P[R[c]+1 (mod 256)], etc.

> What you are discribing is a permutation of a base Latin Square. Let L be
> a base latin square {ie: L(r,c) = r+c mod 256}. Let P, R, T be
> premutations on {0..255}. Then the latin square for encryption is t =
> Le(r,c) = T(L(R(r),C(c))). And the inverse function for decryption in the
> form r = Ld(t,c) = R'(L'(T'(t),C'(c)) where R', C', T' are the inverse
> permutations of R, C, T respectivly and L' is the inverse of the base
> latin square L [ie: L'(t,c) = t-c mod 256 = L(t,-c mod 256)].

Thanks.  It looks like we can generate both the encoding and decoding
PRT arrays without having to actually generate the square in full at
any point, which preserves the memory-consumption advantage of this
method (which in turn makes using order-256 squares useful in memory-
constrained environments).

Further, the time to compute R', C', and T' is small (the decoder
can generate the inverses while populating the arrays - just another
indirection), and using the permutations to index (the virtual) L'
just requires an additional negation, so it looks like the decoder
won't be prohibitively slower than the encoder.

(Of course, whether this combiner is useful in cryptographic
applications is still an open question.)

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

I would never understand our engineer.  But is there anything in this world
that *isn't* made out of words?  -- Tawada Yoko (trans. Margaret Mitsutani)

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Fri, 11 Feb 2000 14:45:22 -0700
From: "Tony T. Warnock" <u091889@cic-mail.lanl.gov>
Message-ID: <38A482F2.E4260434@cic-mail.lanl.gov>
References: <881k5701sgm@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 16

Using a Latin square has the following property that may be of
advantage. If the key symbol and the plaintext symbol are chosen
independently, the sums of the squares of the probabilities of the
output symbols is smaller (or equal) to the sums of the squares of the
probabilities of the input symbols; equality obtains if one of the
inputs has only a single symbol. This makes the output distribution
closer to uniform than either of the two input distributions (equality
if only one symbol on one of the inputs.) I haven't tried to prove a
similar theorem for other types of combiners. If there were biases in
the keystream this might help a bit.

I devised this years ago for combining random number generators in
non-cryptographic applications. It turns out it doesn't matter
(distributionally speaking) what the combiner is, just that it is a
Latin square.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Mon, 7 Feb 2000 23:51:58 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <87ohue\$jt9\$1@nntp2.atl.mindspring.net>
References: <87ndk0028ic@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 51

"Michael Wojcik" <michael.wojcik@merant.com> wrote ...
:
: [We're talking about ways to generate Latin Squares, and treating
: them as combining functions as suggested by Terry Ritter.  Standard
: disclaimer: I'm not a cryptographer, and am definitely not
: recommending this method for anything more than experimentation.]
[...]

: Question: Is the inverse of a PRT-form square always itself a PRT-
: form square?  More generally, are all Latin Squares in PRT-form?

"No" to the 2nd question -- we can see that not all
Lsquares are of your PRT form, by simply comparing
with the known number of Latin Squares of given order.
Since each Lsquare created by your PRT method is the
product of three permutations of 1..N, that method
produces N!^3 distinct Lsquares.  E.g. for N=10,
that's ~10^20; but there are in fact ~10^25 order-10
Lsquares. The discrepancy grows rapidly -- there're
"only" ~10^36 PRT Lsquares of order 15, compared to
an estimated ~10^86 total.

Source:
McKay, B. D. and Rogoyski, E. ``Latin Squares of Order 10.''
Electronic J. Combinatorics 2, N3 1-4, 1995.
http://www.combinatorics.org/Volume_2/volume2.html#N3

: Is there a simple, low-cost construction procedure to derive the
: inverse of a PRT-form square in PRT notation?
:
: Note that if the answer to the second question is yes (all Latin
: Squares are in PRT-form), then we can reduce any Latin Square of
: order N to three arrays of N entries, which means that the internal
: state of a square of order N is bounded by 3N, not by N^2.  (Right?)

The numbers to compare are N!^3 vs. N!^N.
There are N!^3 PRT Lsquares, and N!^N squares that could serve
(in principle) as combiners.

: Ie., this result helps us specify how much information there really
: is in a Latin Square, since it gives us a bijective compression
: function for squares.  (That tends to make me suspect the answer is
: no, but a few minutes of head-scratching wasn't enough for me to
: prove it one way or another.)

--
r.e.s.
rs.1@mindspring.com

Originator: mww@lorelei-n

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 11 Feb 2000 18:35:35 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <881kpn01u5b@news2.newsguy.com>
References: <87ohue\$jt9\$1@nntp2.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 55

In article <87ohue\$jt9\$1@nntp2.atl.mindspring.net>, "r.e.s." <rs.1@mindspring.com> writes:
> "Michael Wojcik" <michael.wojcik@merant.com> wrote ...
> : [re generating Latin Squares with three permutations P (one
> :  column), R (an ordering of rotations of P), and T (a final
> :  permutation of rows)]

> : Question: Is the inverse of a PRT-form square always itself a PRT-
> : form square?  More generally, are all Latin Squares in PRT-form?

> "No" to the 2nd question -- we can see that not all
> Lsquares are of your PRT form, by simply comparing
> with the known number of Latin Squares of given order.
> Since each Lsquare created by your PRT method is the
> product of three permutations of 1..N, that method
> produces N!^3 distinct Lsquares.  E.g. for N=10,
> that's ~10^20; but there are in fact ~10^25 order-10
> Lsquares. The discrepancy grows rapidly -- there're
> "only" ~10^36 PRT Lsquares of order 15, compared to
> an estimated ~10^86 total.
>
> Source:
> McKay, B. D. and Rogoyski, E. ``Latin Squares of Order 10.''
> Electronic J. Combinatorics 2, N3 1-4, 1995.
> http://www.combinatorics.org/Volume_2/volume2.html#N3

Thanks - just what I was looking for.  Dan Oetting has already
supplied the construction principle for fast generation of the
inverse of a PRT square, but these questions remain interesting for
other reasons.

The relatively small number of order-256 squares that are PRT squares
(the "PRT penalty", so to speak) may not be an issue in practice,
since there are still around 10^1520 or 2^5051 PRT squares of order
256.  Other weaknesses may certainly exist, but at least that's a
large enough space to make searching prohibitive.  (Determining some
elements does narrow down the search, but quite a few would have to
be leaked to make the search space reasonable.  Even for a PR-form
square, if we determine an entire column we have 256! possibilities
to check; if we know which column it is, 255!.  That's around 10^507
or 2^1683.  The T permutation certainly looks like it should make
the search effort harder, and I don't see any way it would make it
easier.)

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

Against all odds, over a noisy telephone line, tapped by the tax authorities
and the secret police, Alice will happily attempt, with someone she doesn't
trust, whom she can't hear clearly, and who is probably someone else, to
fiddle her tax return and to organise a cout d'etat, while at the same time
minimising the cost of the phone call.   -- John Gordon

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 18:42:53 GMT
From: Tim Tyler <tt@cryogen.com>
Message-ID: <FptynH.8Gs@bath.ac.uk>
References: <881kpn01u5b@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 16

Michael Wojcik <michael.wojcik@merant.com> wrote:

: The relatively small number of order-256 squares that are PRT squares
: (the "PRT penalty", so to speak) may not be an issue in practice,
: since there are still around 10^1520 or 2^5051 PRT squares of order
: 256.  Other weaknesses may certainly exist, but at least that's a
: large enough space to make searching prohibitive. [...]

If there /are/ significant weaknesses, they are likely to be caused by
"structure" in the table (resulting in spurious conserved quantities and
the like) - rather than a lack of possible tables - IMO.
--
__________
|im |yler  The Mandala Centre  http://www.mandala.co.uk/  tt@cryogen.com

As scarce as the truth is, the supply has always been in excess of demand.

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Sat, 12 Feb 2000 15:04:22 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <884ot5\$kci\$1@nntp4.atl.mindspring.net>
References: <881kpn01u5b@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 81

"Michael Wojcik" <michael.wojcik@merant.com> wrote ...
: "r.e.s." <rs.1@mindspring.com> writes:
: > "Michael Wojcik" <michael.wojcik@merant.com> wrote ...
: > : [re generating Latin Squares with three permutations P (one
: > :  column), R (an ordering of rotations of P), and T (a final
: > :  permutation of rows)]
:
: > : Question: Is the inverse of a PRT-form square always itself a PRT-
: > : form square?  More generally, are all Latin Squares in PRT-form?
:
: > "No" to the 2nd question -- we can see that not all
: > Lsquares are of your PRT form, by simply comparing
: > with the known number of Latin Squares of given order.
: > Since each Lsquare created by your PRT method is the
: > product of three permutations of 1..N, that method
: > produces N!^3 distinct Lsquares.  E.g. for N=10,
: > that's ~10^20;

Sorry I didn't catch this earlier, but the number of PRT
squares is not N!^3, but N!(N-1)!f(N), where f(N)=1 for N<4,
and f(N)>1 for N>=4. (I haven't been able to deduce the
complete form of f(N).)  The first two steps, PR, result
in having filled the columns with the N rotations of a
selected permutation P.  Thus, col_0 could get filled in N!
ways, and for each of these there are N-1 ways that col_1
could get filled, then N-2 ways for col_2, etc, and hence
N!(N-1)! different PR squares.  "By inspection" we can see
that for N<4, further permutating the rows by T introduces
no square not already possible by PR alone, but that when
N>=4, new possibilities are indeed introduced.  (f(N) is
clearly not N! -- maybe someone else can see what it is?)

For example, look at all 2x2 latin squares:
01       10
10       01

P can be 01 or 10, and there are 2! ways to fill the first
column with a rotation of P.  But once that's done, there's
only one rotation left for the next column, giving a total
of 2!1! cases, not 2!2!. (Obviously in this case a further
permutation of rows would produce no new cases.)

Similarly, there are only 12 3x3 Lsquares, all (3!2!=12) of
which are PR squares.

For N>=4 the situation changes such that not all of the
Lsquares are PR squares, and *presumably* not all PRT
squares are Lsquares.  Since we don't know f(N), it's hard
to say much more, but I suspect N!(N-1)!f(N) will prove to
grow much less rapidly than L(n) -- but we don't even have
"computational evidence" for that, unless someone has
exhaustively computed all PRT squares for some N>3.

: > but there are in fact ~10^25 order-10
: > Lsquares. The discrepancy grows rapidly -- there're
: > "only" ~10^36 PRT Lsquares of order 15, compared to
: > an estimated ~10^86 total.

At this point, I think all we have is that N!(N-1)! is a
lower bound on the total number of PRT squares, e.g.:
N=10:  10!9!    ~ 10^12   ~ 2^40
N=15:  15!14!   ~ 10^23   ~ 2^77
N=256: 256!255! ~ 10^1011 ~ 2^3359

[...]
: The relatively small number of order-256 squares that are PRT squares
: (the "PRT penalty", so to speak) may not be an issue in practice,
: since there are still around 10^1520 or 2^5051 PRT squares of order
: 256.
[...]

Well, we know there are at least 256!255! ~ 10^1011 ~ 2^3359,
which is also a healthy number ;-)

--
r.e.s.
rs.1@mindspring.com

Originator: mww@lorelei-n

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: 15 Feb 2000 15:41:00 GMT
From: michael.wojcik@merant.com (Michael Wojcik)
Message-ID: <88bs2c0pod@news2.newsguy.com>
References: <884ot5\$kci\$1@nntp4.atl.mindspring.net>
Newsgroups: sci.crypt
Lines: 72

In article <884ot5\$kci\$1@nntp4.atl.mindspring.net>, "r.e.s." <rs.1@mindspring.com> writes:
> "Michael Wojcik" <michael.wojcik@merant.com> wrote ...
> : "r.e.s." <rs.1@mindspring.com> writes:
> : > "Michael Wojcik" <michael.wojcik@merant.com> wrote ...
> : > : [re generating Latin Squares with three permutations P (one
> : > :  column), R (an ordering of rotations of P), and T (a final
> : > :  permutation of rows)]

> Sorry I didn't catch this earlier, but the number of PRT
> squares is not N!^3, but N!(N-1)!f(N), where f(N)=1 for N<4,
> and f(N)>1 for N>=4. (I haven't been able to deduce the
> complete form of f(N).)  The first two steps, PR, result
> in having filled the columns with the N rotations of a
> selected permutation P.  Thus, col_0 could get filled in N!
> ways, and for each of these there are N-1 ways that col_1
> could get filled, then N-2 ways for col_2, etc, and hence
> N!(N-1)! different PR squares.  "By inspection" we can see
> that for N<4, further permutating the rows by T introduces
> no square not already possible by PR alone, but that when
> N>=4, new possibilities are indeed introduced.  (f(N) is
> clearly not N! -- maybe someone else can see what it is?)

Excellent point -- in brief, some T permutations (reordering the rows
after the columns are constructed by the PR method) produce squares
that are also PR squares, and some T permutations do not (for N >=
4).  f(N) = N! - {number of T permutations that produce other PR
squares, ie. squares where all columns are rotations of one another},
right?  We're interested in T permutations that produce non-PR
squares -- we want to avoid the structure of the PR form in our
combiner -- so let's call those permutations Td, the set of T
permutations that produce a PR square from a given input PR square.
(One obvious member of this set is T={0,1,2,...,N-1}, since it
doesn't reorder the input PR square at all.)

So f(N) = N! - #Td.  I suspect, though, that some elements of Td
depend on the input (at least for sufficiently large N), so that
should really be #Td(P,R).

> [snip example]

> For N>=4 the situation changes such that not all of the
> Lsquares are PR squares, and *presumably* not all PRT
> squares are Lsquares.

Maybe I'm missing something, but why wouldn't all PRT squares be
Latin Squares?

All PR squares are Latin Squares.  The "base column" (P) contains
each element from 0 to N-1 (or 1 to N, if you prefer that numbering)
once and only once.  All other columns are rotations of P, so each of
them contain each element once and only once.

Since each column's degree of rotation is a unique element in R, and
R contains each element once and only once, no columns contain the
same element in the same position; thus all rows contain each element
once and only once.

Since the PR square is a Latin Square, shuffling its rows produces a
Latin Square.  (Shuffling rows can't change how many times a value
appears in a column, and it can't change the composition of a row.)
That's what the T transformation does -- it selects a permutation of
the rows of the input PR square.

--
Michael Wojcik          	        michael.wojcik@merant.com
AAI Development, MERANT                 (block capitals are a company mandate)
Department of English, Miami University

Not the author (with K.Ravichandran and T.Rick Fletcher) of "Mode specific
chemistry of HS + N{_2}O(n,1,0) using stimulated Raman excitation".

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 15 Feb 2000 13:52:19 -0800
From: "r.e.s." <rs.1@mindspring.com>
Message-ID: <88ci3l\$6ih\$1@nntp9.atl.mindspring.net>
References: <88bs2c0pod@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 17

"Michael Wojcik" <michael.wojcik@merant.com> wrote ...
:"r.e.s." <rs.1@mindspring.com> writes:
[...]
: >> *presumably* not all PRT squares are Lsquares.
:
: Maybe I'm missing something, but why wouldn't all
: PRT squares be Latin Squares?
[...]

Sorry!  I meant to say just the reverse, viz.,
"*presumably* not all Lsquares are PRT squares."

--
r.e.s.
rs.1@mindspring.com

Subject: Re: Latin Squares (was Re: Reversibly combining two bytes?)
Date: Tue, 08 Feb 2000 22:40:49 GMT
From: ritter@io.com (Terry Ritter)
Message-ID: <38a09b6a.14542674@news.io.com>
References: <87ndk0028ic@news2.newsguy.com>
Newsgroups: sci.crypt
Lines: 35

On 7 Feb 2000 21:31:44 GMT, in <87ndk0028ic@news2.newsguy.com>, in
sci.crypt michael.wojcik@merant.com (Michael Wojcik) wrote:

>[...]
>encoding, as Terry Ritter suggested in another post.  Generating a
>new square is relatively expensive, but perhaps not prohibitive with
>this method.

A few simple 256-element random-like permutations (shuffling by a
keyed confusion-sequence) are surely fast enough in human terms, even
for message keying.  But there really is a great deal more dangerous
"structure" in Latin squares constructed from a few permutations than
is likely to be present in schemes which must store an entire table.

>If we're using square-combining in a block cypher, we
>might advance to a new square on every block.  With a stream cypher,
>we might generate a new square after every so many bytes (how many
>is an interesting question), or we might do so dynamically based on,
>say, the key or plaintext (with the decoder examining output plain-
>text to decide when to regenerate).

One might have at least two combining levels, plus a multiplicity of
squares (say, 16) in at least one level.  The confusion sequence then
selects among the 16 possible squares for that level on a
character-by-character basis.  Since the selection process is never
exposed, it should be hard for an opponent to identify which
characters are taken from which square.

---
Terry Ritter   ritter@io.com   http://www.io.com/~ritter/
Crypto Glossary   http://www.io.com/~ritter/GLOSSARY.HTM

```

Terry Ritter, his current address, and his top page.

Last updated: 2004-03-29 from 2001-06-24