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 Pizzini  wrote:
>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