Path: illuminati.io.com!uunet!sparky!paganini.sydney.sterling.com!paganini. + sydney.sterling.com!not-for-mail From: ggr@sydney.sterling.com (Greg ROSE) Newsgroups: sci.crypt Subject: Re: Algorithms Date: 21 Nov 1994 11:35:03 +1100 Organization: Sterling Software (Aust) Pty. Ltd. Lines: 85 Message-ID: <3aopvn$sai@paganini.sydney.sterling.com> References: <199411152009.OAA09390@pentagon.io.com> <3adpb0$q9@news.halcyon. + com> NNTP-Posting-Host: paganini.sydney.sterling.com In article <3adpb0$q9@news.halcyon.com>, Ken Pizziniwrote: >In article <199411152009.OAA09390@pentagon.io.com>, >Terry Ritter wrote: >> Now, suppose we confine each of the newspaper ciphers to a subset >> of their 26! possible permutations: Does this prevent us from >> solving the overall permutation of several sequential ciphers? >> No, it does not (unless we insist on solving for each key). The >> fact that the overall permutation may not be producible from a >> single key is beside the point if we just want to find the hidden >> information. > >... >Now, if a new attack on DES is discovered that is both more efficient >than a keyspace attack and doesn't care about the key used, then >yes, I agree that the groupness of DES is irrelevant. But since >the best attacks known are attacks on the keyspace it is relevant >whether the keyspace is enlarged by composition. And the proof >that DES is not a group tells us that the keyspace of DES does >get enlarged by composition. I'm sorry, but the last statement is not strictly true, in general, and while it is likely to be true of DES, I don't actually know that either. (Perhaps Ken does know this; it depends on the form of the proof that DES is not a group, see below.) It is true that "If DES is a group, the keyspace of repeated DES does not get enlarged". The contrapositive statement "If the keyspace of repeated DES is larger than that of DES, then DES cannot be a group" must also be true, and for all I know may be how DES was proven not to be a group. However, the inverse and converse statements (I'm not going to write them out, and anyway I can never remember which is which) are NOT NECESSARILY true. I can construct a theoretical cipher which is easily proven not to be a group, but in which the repeated application of the cipher has the identical keyspace. I believe that with thought I could construct one that has a smaller keyspace when composed. (The example cipher? Working only on English alphabetic characters, (a=>1, b=>2, etc) choose a permutation such that odd numbered characters become even numbered, and even become odd. This has a keyspace of (13!)**2. Hovever, take two different such ciphers, and compose them. The new cipher maps an even numbered character (via an odd numbered one) to another even numbered one, and hence is not one of the original possible ciphers (therefore the original ciphers do not form a group). However, it is representable as a single application of a similar even=>even, odd=>odd cipher with exactly the same sized keyspace!) Anyway, I agree with Terry's statement that people often misuse terms like "groupiness" to handwave arguments that are incorrect (although I can't point at Ken for that). In case anyone has never heard of the classification of implications, here is a simplified version. Using A and B to be statements like "I am on Mars" or "the sky is pink", and '=>' to mean 'implies' or 'therefore', and '~' to mean "not": A => B is the original statement, assume it is true. ~B => ~A is called the contrapositive, and is true if the original statement is true. B => A is the converse, and is not necessarily true (there may be other pink-skied worlds) ~A => ~B is the inverse, and also might not be true. -- Greg Rose INTERNET: greg_rose@sydney.sterling.com Sterling Software VOICE: +61-2-975 4777 FAX: +61-2-975 2921 28 Rodborough Rd., French's Forest. NSW 2086 Australia. 04 6A E7 37 BF 64 3D B0 F1 A5 B3 CA 64 1D 48 67 co-mod sci.crypt.research