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.
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: *add modulo 256 *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: > >*add modulo 256 >*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 about this alternative method: instead make the <x>th row contained the 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.) We should also return to the question of changing squares during 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 Mary had a little RAM - about a MEG or so.
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. > OK, I posted about this before but apparently 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/ Before you buy.
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. : > : : OK, I posted about this before but apparently : 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. Again, although your reply is to my posting, I'll 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. > : > > : > : OK, I posted about this before but apparently > : 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. > > Again, although your reply is to my posting, I'll > 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. > : > > : > : OK, I posted about this before but apparently > : 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. > > Again, although your reply is to my posting, I'll > 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 added in the blocks.. -- Do as thou thinkest best. Sent via Deja.com http://www.deja.com/ Before you buy.
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/ Before you buy. 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: > OK, I posted about this before but apparently > 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). But to answer your question: I don't think anyone's made any very strong arguments for using Latin Squares as combiners yet (in this thread). Terry Ritter has made some suggestions in that direction, 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: >[...] >But to answer your question: I don't think anyone's made any very >strong arguments for using Latin Squares as combiners yet (in this >thread). Terry Ritter has made some suggestions in that direction, >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 access to the confusion sequence and so complicates a normal stream cipher attack. To the extent that a keyed nonlinear combiner complicates access to 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. [...] Additive combiners (XOR or modular addition) are, of course, 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. >[...] > >Additive combiners (XOR or modular addition) are, of course, >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/ Before you buy.
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. This would leak more information than would happen if groupings were 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> Message-ID: <88535q$uad$1@nnrp1.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/ Before you buy.
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: >[...] >We should also return to the question of changing squares during >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