From: lwloen@rchland.vnet.ibm.com (Larry Loen)
Subject: Re: perfect secrecy
Date: Tue, 29 Dec 1992 15:22:17 GMT
Reply-To: lwloen@rchland.vnet.ibm.com
Disclaimer: This posting represents the poster's views, not necessarily those of IBM
Organization: IBM Rochester

In article <1992Dec29.121656.4726@nuscc.nus.sg>, isc40019@nusunix1.nus.sg (THAI LING) writes:
|> I think this is a neat folder to discuss topics on cyptography.
|> I am currently doing a course on it and there are some questions 
|> on my mind.Can anyone help?
|> 
|> Does anyone know how to prove the following :
|> 
|> Q1 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
|> Definition : M = the message space
|>              K = the key space
|>              C = the cytogram space 
|>  ! ! means the cardinality of
|> 
|> Given that !M! = !K! = !C! then perfect secrecy is achieved if
|> 
|> (1) all the keys are equiprobable
|> (2) there is exactly one transformation ( i.e one key ) from a given
|>     message to a given cyptogram
|> 

If this is meant for an arbitrary cryptosystem, it is easily _disproven_.

Suppose one has the well-broken cryptosystem that uses a "random" number
generator of the form  x(n+1) = (A * x(n)  + C)   mod M and that the
cipher text is formed by exclusive orring successive terms of x with
the plaintext.

Suppose further that the value of  x(0) (that is, the first term) is
chosen by flipping a perfectly balanced coin to establish each bit
in x's representation.

Now, if A, M, and C are correctly chosen (all relatively prime to each
other, if memory serves and this is usual for such a system), each value
from 0...M-1 will appear exactly once.  Now, since the plaintext is 
broken into groups of size M as well, it appears to me that the 
conditions described above have been achieved if one presumes a general
enough plaintext to admit all 0...M-1 values, which is also usual.

Yet, this system is well-studied and can be broken (for example) if
A, C, and M are known (usual crypto assumptions) and if two successive
values of the plaintext can be guessed using ordinary algebra.  There
are also breaks relating to the problem that there may be two messages
who share values of x.

At best, the conditions you cite are "necessary", but are certainly not
"sufficient".  They probably are not even "necessary".

|> Q2 ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
|> 
|> how can the key space be increased by using a combination of keys are
|> encryption instead of a single key replacement?
|> i.e instead of A   ......  B
|>                .          .
|>                .          .
|>                .          .
|>                .          .
|>                Z           K
|> 
|> to try        AB  .......   CD
|>                .          .
|>                .          .
|>                .          .
|>                .          .
|>               AZ   ......   WE  ...etc
|>  
|> Thanks in advance !!!!!
|> 
|> Linda

If I understand your question, the answer is very specific to the
system.  For instance, in DES, it can be shown that an "enhanced" 
DES using two keys done like so:

      E(k1,E(k2,x)) 

 can be defeated in only about double the number of
 operations rather that 2 to the 110 operations as might be guessed
 if one is granted the luxury of a table of size 2 to the 67th bytes.


If you don't mind my asking, what cryptography books do you have available
to you?  These questions should be able to be ferreted out of available
sources (such as H. F. Gaines' "Cryptanalysis").  On the other hand,
I have no idea what restrictions one labors under outside of the US.
(If you choose not to answer this question, I will understand; I really
_don't_ know what restrictions you labor under and it is sometimes a
mistake to even ask).
-- 
   Larry W. Loen        |  My Opinions are decidedly my own, so please
                        |  do not attribute them to my employer