Specialized permutations used for ciphering.
Subject: Coderpunks Query on Teledyne Crypto Date: Thu, 30 Mar 2000 08:11:29 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <38e30407.3351702@news.ecn.ab.ca> Newsgroups: sci.crypt Lines: 76 There was a question on the Coderpunks mailing list, which I saw in the newsgroup where its contents are echoed, about the encryption products discussed at the web site http://www.infsec.com/EncrypTech.html While the term "Dynamic Substitution" was used, this wasn't a reference to Terry Ritter's cipher of that name (although one of his patents was cited as prior art) but I did find the Teledyne patent referred to: U. S. Patent 6035042 and it appears to describe the following process of generating S-boxes: Start with two S-boxes of a given size (as an example, I will take the two S-boxes from LUCIFER): Input: S-box 1 S-box 2 0000 1100 0111 0001 1111 0010 0010 0111 1110 0011 1010 1001 0100 1110 0011 0101 1101 1011 0110 1011 0000 0111 0000 0100 1000 0010 1100 1001 0110 1101 1010 0011 0001 1011 0001 1010 1100 1001 0110 1101 0100 1111 1110 0101 1000 1111 1000 0101 An S-box of twice the size is produced by choosing a bit position in which to insert both 0 or 1 for the two occurrences of a value on both sides of the table: Input: Output: Input: Output: 00000 10100 00100 01111 00101 11111 00001 01010 00110 00111 00010 10110 00011 10010 00111 10001 01100 11110 01000 00011 01001 10101 01101 11011 01110 10011 01010 00000 01011 01000 01111 00100 10100 00010 10000 11100 10001 01110 10101 11101 10010 01011 10110 01001 10111 00001 10011 11010 11000 11001 11100 00110 11101 01100 11001 10111 11010 00101 11110 10000 11011 11000 11111 01101 ^ ^ ^ ^ This guarantees that changing the one bit used for expansion on the input side will put you in a completely different permutation; hence, if instead of starting with S-boxes produced by other means, if I used this method from the ground up, all the bits would have this property, which would make the permutation _orthomorphic_. (The patent notes that for 8-bit S-boxes, there are 510 that are orthomorphic.) Since such a permutation provides perfect diffusion, it is claimed to be good for cryptographic purposes. Otherwise, the cipher is illustrated as a classical Shannon S-P network, like that which appeared in the Scientific American article on Lucifer (not the Feistel round structure which Lucifer actually used), using S-boxes constructed this way as its components. John Savard (teneerf <-) http://www.ecn.ab.ca/~jsavard/index.html
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Thu, 30 Mar 2000 11:25:33 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <38e33940.566930@news.ecn.ab.ca> References: <38E33877.7657A8F7@t-online.de> <38e30407.3351702@news.ecn.ab.ca> Newsgroups: sci.crypt Lines: 21 On Thu, 30 Mar 2000 13:20:23 +0200, Mok-Kong Shen <mok-kong.shen@t-online.de> wrote, in part: >In the last line of the table > >> 11011 11000 >> ^ ^ > >on one side a 0 is inserted, while on the other side a 1. Is this >a printing error? No, the bits are essentially random, except that in one copy of 11x11, a 0 must be inserted, and in the other copy, a 1 must be inserted, and in one copy of 1x000 a 0 must be inserted, and in the other copy, a 0 must be inserted. As to what an orthomorphic permutation is, I did not see a clear explanation of that in the patent. John Savard (teneerf <-) http://www.ecn.ab.ca/~jsavard/index.html
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Thu, 30 Mar 2000 18:33:15 GMT From: "Douglas A. Gwyn" <gwyn@arl.mil> Message-ID: <38E39DEB.AB22A117@arl.mil> References: <38e33940.566930@news.ecn.ab.ca> Newsgroups: sci.crypt Lines: 7 John Savard wrote: > As to what an orthomorphic permutation is, I did not see a clear > explanation of that in the patent. Just from analyzing the word, perhaps it means a transformation of a set to an orthogonal (anticorrelated) set. Maybe this refers to the one-bit-changes-everything aspect.
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Thu, 30 Mar 2000 22:39:20 GMT From: reeds@research.att.com (Jim Reeds) Message-ID: <Fs9AxK.EBv@research.att.com> References: <38E39DEB.AB22A117@arl.mil> Newsgroups: sci.crypt Lines: 27 In article <38E39DEB.AB22A117@arl.mil>, "Douglas A. Gwyn" <gwyn@arl.mil> writes: |> John Savard wrote: |> > As to what an orthomorphic permutation is, I did not see a clear |> > explanation of that in the patent. |> |> Just from analyzing the word, perhaps it means a transformation |> of a set to an orthogonal (anticorrelated) set. Maybe this |> refers to the one-bit-changes-everything aspect. From personal communication with Teledyne people, & from reading some Teledyne papers, I know what "orthomorphism" means. A permutation f of the elements of a group is an orthomorphism if the function g(x):=f(x)+x (for additive groups, or g(x):=f(x)*x for multiplicative ones) is also a permutation. In the case at hand, the group is bitwise mod 2 addition of bytes. There is some precedent in the math. literature for use of this term, but it doesn't come up often. -- Jim Reeds, AT&T Labs - Research Shannon Laboratory, Room C229, Building 103 180 Park Avenue, Florham Park, NJ 07932-0971, USA reeds@research.att.com, phone: +1 973 360 8414, fax: +1 973 360 8178
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Fri, 31 Mar 2000 21:04:03 GMT From: Jim Reeds <reeds@research.att.com> Message-ID: <38E512C3.3A02108D@research.att.com> References: <38E508B1.70F1E91A@t-online.de> <Fs9AxK.EBv@research.att.com> Newsgroups: sci.crypt Lines: 42 Mok-Kong Shen wrote: > > Jim Reeds wrote: > > > > > From personal communication with Teledyne people, & from > > reading some Teledyne papers, I know what "orthomorphism" > > means. A permutation f of the elements of a group > > is an orthomorphism if the function g(x):=f(x)+x ... > > Do I understand correctly that x is a character of the input > alphabet and f(x) is the corresponding character of the > output alphabet? [...] could you please tell what are the essential > advantages of the orthomorphism? ... I've not looked at the patent, I don't know what the Teledyne product is. A couple of years ago a Teledyne mathematician told me he was working on orthomorphisms, and gave me copies of some papers he had written. The algebraic definition stuck in my mind. I don't know what the advantages of using orthomorphisms are, neither in the Teledyne context nor otherwise. I'm not denying that there might be advantages, I just don't know what they are. Note that there is nothing stoping a linear function from being an orthomorphism: if k is an element of GF(256), for instance, with k not equal to 0 or 1, then f(x) := k*x is an orthomorphism. Note that some groups don't have orthomorphisms. (Integers mod 10, for instance.) I think the underlying formula for computation of check digits on serial numbers on German paper currency is based on an orthomorphism of the dihedral group D_5. But I don't think the standard expositions of the checksum formula use the term "orthomorphism." -- Jim Reeds, AT&T Labs - Research Shannon Laboratory, Room C229, Building 103 180 Park Avenue, Florham Park, NJ 07932-0971, USA reeds@research.att.com, phone: +1 973 360 8414, fax: +1 973 360 8178
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Sat, 01 Apr 2000 15:52:49 GMT From: jsavard@tenMAPSONeerf.edmonton.ab.ca (John Savard) Message-ID: <38e615d4.150876@news.ecn.ab.ca> References: <Fs9AxK.EBv@research.att.com> Newsgroups: sci.crypt Lines: 89 On Thu, 30 Mar 2000 22:39:20 GMT, reeds@research.att.com (Jim Reeds) wrote, in part: >A permutation f of the elements of a group >is an orthomorphism if the function g(x):=f(x)+x (for >additive groups, or g(x):=f(x)*x for multiplicative ones) >is also a permutation. In the case at hand, the group >is bitwise mod 2 addition of bytes. Given that definition of an orthomorphism, there are seven orthomorphisms of GF(2^2): 00 | 00 01 01 10 10 11 11 01 | 10 10 11 00 01 00 01 10 | 11 00 10 01 11 10 00 11 | 01 11 11 11 00 01 10 which I obtained by pencil and paper by starting with the possible values of substitutes for 00, and going onwards in a tree fashion (rather than checking all 24 possibilities). Now then, does the method outlined in the Teledyne patent, when given two orthomorphisms as input, produce an orthomorphism as output, and if so, under what conditions? For one thing, my illustration is wrong. It is necessary to introduce the additional bit in the same position in both mappings. That way, the XOR of x and f(x), which was an orthomorphism, will at least contribute to the resulting mapping's being an orthomorphism, since now the same bits as were XORed previously will still be XORed again. Thus, take two orthomorphisms from the list 00 - 10 00 - 11 01 - 00 01 - 00 10 - 01 10 - 10 11 - 11 11 - 01 and expand them by the method outlined 0w0 - 1a0 0W0 - 1D1 0x1 - 0b0 0X1 - 0B0 1y0 - 0c1 1Y0 - 1A0 1z1 - 1d1 1Z1 - 0C1 where A is the complement of a, and so on. This complementation property is the only property required to ensure the resulting mapping is a permutation. What is required to ensure that it is also an orthomorphism? If we expand the table to show x XOR f(x) in addition to x and f(x), we get 0w0 - 1a0 (1 wa 0) 0W0 - 1D1 (1 wd 1) 0x1 - 0b0 (0 xb 1) 0X1 - 0B0 (0 xb 1) 1y0 - 0c1 (1 yc 1) 1Y0 - 1A0 (0 ya 0) 1z1 - 1d1 (0 zd 0) 1Z1 - 0C1 (1 zc 0) In this particular case, wa must be not zc, xb must be not xb (so no orthomorphism is obtainable from the two parent orthomorphisms chosen), yc must be not wd, and zd must be not ya. We've discovered one condition: the two parent orthomorphisms, f(x) and g(x), must be chosen so that f(x)=g(x) is false for all x. Let's try again: 00 - 10 00 - 11 01 - 00 01 - 01 10 - 01 10 - 00 11 - 11 11 - 10 These two meet that condition. Proceeding directly to the expanded table: 0w0 - 1a0 (1 wa 0) 0W0 - 1D1 (1 wd 1) 0x1 - 0b0 (0 xb 1) 0X1 - 0C1 (0 xc 1) 1y0 - 0c1 (1 yc 1) 1Y0 - 0B0 (0 yb 0) 1z1 - 1d1 (0 zd 0) 1Z1 - 1A0 (1 za 0) we get the conditions wa = ~za, xb = ~xc, yc = ~wd, and zd = ~yb. Hence, in this particular case, w=~z, b=~c, hence the last two conditions can be changed to yb = wd and wd = yb, which are at least consistent. But I don't see a simple mechanical condition for guaranteeing an orthomorphism immediately. Perhaps there is one somewhere in that patent. John Savard (teneerf <-) http://www.ecn.ab.ca/~jsavard/index.html
Subject: Re: Coderpunks Query on Teledyne Crypto Date: Fri, 31 Mar 2000 09:52:26 GMT From: socrates314@my-deja.com Message-ID: <8c1sgn$83d$1@nnrp1.deja.com> References: <38E39DEB.AB22A117@arl.mil> Newsgroups: sci.crypt Lines: 57 In article <38E39DEB.AB22A117@arl.mil>, "Douglas A. Gwyn" <gwyn@arl.mil> wrote: > John Savard wrote: > > As to what an orthomorphic permutation is, I did not see a clear > > explanation of that in the patent. > > Just from analyzing the word, perhaps it means a transformation > of a set to an orthogonal (anticorrelated) set. Maybe this > refers to the one-bit-changes-everything aspect. > I also think so, orthomorphic might be used as a term somewhat opposed to isomorphic. But in defining it, you have to talk about this property respective to some relation between two (or more sets). An isomorphy between two sets N and M regarding to some relation R can be defined the following (didn't look it up though, sorry if it isn't 100% correct): (1) There is a bijective function f: N --> M such that each element of N is mapped to an element of M, and the inverse of f maps each element of M to the respective element of N, i.e. each element of N is associated with an element of M and vice versa, and no two different elements of N are associated with the same element in M and vice versa (2) If for two elements <a,b> of N relation R holds R(a,b), then relation R also holds for the respective elements in M, i.e. R(f(a), f(b)) (3) If (1) and (2) are fullfilled the two sets are isomorphic regarding to relation R For example, if N={1,2,3} and M = {2,4,6} and relation R is > "greater than", N and M are isomorphic because f(n) = 2n is a bijective relation over N and M, and if e.g. 2>1 (in N), also 4>2 holds, etc. Now, orthomorphic perhaps is about some similar property, except that N and M are guaranteed *not* to fullfill (2). For example, if you take R to be an ordering relation (like e.g. > also is), function f would guarantee that for each pair <a,b> in N, if R(a,b) then NOT(R(f(a), f(b))) holds. In this example, f would ensure that the ordering of M (as defined by R) is always different than the ordering of N. As an example,for N = {1,2,3} regarding to relation > "greater than", f(n) = n*-1 would ensure that N and M are orthomorphic regarding greater than, because if e.g. 2>1 the respective relation in M (2*-1) > (1*-1) is wrong, and so for each other argument of f as well. Just an assumption, maybe they mean something completely different by "orthomorphic". And sorry if my definitions weren't correct... Greetings, Erich Steinmann Sent via Deja.com http://www.deja.com/ Before you buy.
Terry Ritter, his current address, and his top page.
Last updated: 2001-06-24