Cryptography-Digest Digest #576
Cryptography-Digest Digest #576, Volume #14 Sat, 9 Jun 01 21:13:01 EDT
Contents:
Re: Differential cryptanalysis ("Adam O'Brien")
Re: National Security Nightmare? (Jim D)
Re: National Security Nightmare? (Jim D)
Re: OTP WAS BROKEN!!! (Jim D)
Re: Differential cryptanalysis ("Tom St Denis")
Re: Brute-forcing RC4 (Ichinin)
Re: Any Informed Opinions? ("Jeffrey Walton")
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Encryption based password validation system? (phallen)
Re: Encryption based password validation system? ("Tom St Denis")
Re: Encryption based password validation system? ([EMAIL PROTECTED])
Re: Shannon's definition of perfect secrecy (Mok-Kong Shen)
Re: cubing modulo 2^w - 1 as a design primitive? (Mok-Kong Shen)
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
From: "Adam O'Brien" <[EMAIL PROTECTED]>
Subject: Re: Differential cryptanalysis
Date: Sat, 09 Jun 2001 18:55:39 GMT
Sorry Tom I don't understand still. What do A,B and x refer to and how do
they relate to Sio and Sii in Table 5.
Adam
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:RAoU6.68230$[EMAIL PROTECTED]...
>
> "Adam O'Brien" <[EMAIL PROTECTED]> wrote in message
> news:0voU6.24565$[EMAIL PROTECTED]...
> > I'm reading Biham and Shamir's paper, Differential Cryptanalysis of
> DES-like
> > cryptosystems.
> > I can understand how to derive Table 5.
> > Can anyone help?
>
> Simple.
>
> You could how many times
>
> A = sbox[x] xor sbox[x xor B]
>
> For all A,B,x in the domain of the sbox i.e
>
> s = 0
> for x = 0 to N-1 do
>if A = sbox[x] xor sbox[x xor B]
>s = s + 1
>
> If you can support the memory you can write the code as
>
> for A = 0 to N-1 do
> for B = 0 to N-1 do
> for x = 0 to N-1 do
>dt[B][sbox[x] xor sbox[x xor A]] += 1
>
> (where "a += 1" means "a = a + 1")
>
> Tom
>
>
--
From: [EMAIL PROTECTED] (Jim D)
Subject: Re: National Security Nightmare?
Date: Sat, 09 Jun 2001 18:58:18 GMT
Reply-To: Jim D
On Sat, 09 Jun 2001 00:41:19 GMT, "Tom St Denis" <[EMAIL PROTECTED]>
wrote:
>
>"Jim D" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> On Fri, 08 Jun 2001 17:01:09 GMT, "Tom St Denis" <[EMAIL PROTECTED]>
>> wrote:
>>
>> >"A bunch of people is wrong". Doesn't sound right since it is more than
>one
>> >person who is wrong.
>>
>> There's only one bunch.
>
>Yeah I agree the original is grammatically correct, it just doesn't sound
>right.
Quite so. 'the police have...', '...the government have...' is what you
usually hear. Gramatically wrong, but acceptably so.
--
__
Posted by Jim D.
Propino tibi salutem !
jim @sideband.fsnet.co.uk
dynastic @cwcom.net
___
--
From: [EMAIL PROTECTED] (Jim D)
Subject: Re: National Security Nightmare?
Date: Sat, 09 Jun 2001 18:58:19 GMT
Reply-To: Jim D
On Sat, 9 Jun 2001 13:05:09 GMT, Tim Tyler <[EMAIL PROTECTED]> wrote:
>David Wagner <[EMAIL PROTECTED]> wrote:
>
>: In particular, I couldn't find any prohibition against the "GCHQ
>: backdoor", i.e., a gentleman's agreement between the NSA and GCHQ to
>: spy on each other's citizens and swap intercepts. If it is the
>: policy of the NSA that such conduct is forbidden, how can I tell?
>
>I believe GCHQ does not need to go to any such lengths if it wants to
>spy on UK citizens.
GCHQ does not do so. Believe me. They have other things to waste
our money on.
Spying on UK citizens is done by the lying, blackmailing, murdering
outfit known as the Security Services (ex MI5).
--
__
Posted by Jim D.
Propino tibi salutem !
jim @sideband.fsnet.co.uk
dynastic @cwcom.net
___
--
From: [EMAIL PROTECTED] (Jim D)
Subject: Re: OTP WAS BROKEN!!!
Date: Sat, 09 Jun 2001 18:58:20 GMT
Reply-To: Jim D
On Sat, 09 Jun 2001 14:51:51 GMT, Charles Lyttle <[EMAIL PROTECTED]>
wrote:
>Al wrote:
>>
>> Interesting...
>> Your replies seem to suggest that you think there is some merit in
>> what newbie says...
>> OTP is indistinguishable from completely randomly generated numbers,
>> even seemingly random typing of the upper row of numbers. This could
>> be any message shifted out mod 26, thats the point of this OTP thread.
>> Do you guys get out much?
>
>But your message wasn't completely randomly generated numbers, as Paul
>demonstrated. The second biggest problem with OTP is that it is very
>difficult to get a large quantity of true random numbers.
Doesn't have to be. Need only be random enough so the cryptanalyst
can't/is unlikely to be able to predict the next key byte.
--
__
Posted by Jim D.
Propino tibi salutem !
jim @side
Cryptography-Digest Digest #575
Cryptography-Digest Digest #575, Volume #14 Sat, 9 Jun 01 14:13:01 EDT
Contents:
where can I find information about DES? ("doublemc")
Re: Shannon's definition of perfect secrecy (Mok-Kong Shen)
Re: where can I find information about DES? (Mok-Kong Shen)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: cubing modulo 2^w - 1 as a design primitive? (Mok-Kong Shen)
Re: Uniciyt distance and compression for AES ("Tom St Denis")
Re: cubing modulo 2^w - 1 as a design primitive? (Mark Wooding)
Re: Shannon's definition of perfect secrecy (SCOTT19U.ZIP_GUY)
Re: where can I find information about DES? ("Robert J. Kolker")
Re: where can I find information about DES? ("Robert J. Kolker")
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: Hex notation (Paul Schlyter)
Re: Shannon's definition of perfect secrecy (John Savard)
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: Simple C crypto ("Sam Simpson")
Re: Simple C crypto ("Sam Simpson")
Re: Shannon's definition of perfect secrecy (SCOTT19U.ZIP_GUY)
Re: Simple C crypto ("Tom St Denis")
RC5 test vector ("Cristiano")
Re: RC5 test vector ("Tom St Denis")
From: "doublemc" <[EMAIL PROTECTED]>
Subject: where can I find information about DES?
Date: Sat, 09 Jun 2001 16:20:37 GMT
Hi everybody!.
I´m searching information about DES.
Can you help me to find it?
Thank you.
--
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Shannon's definition of perfect secrecy
Date: Sat, 09 Jun 2001 18:27:33 +0200
Tim Tyler wrote:
>
[snip]
> Yes - he doesn't deal with the conventional OTP on finite files in the
> passage you quote.
After having followed part of this thread, I am still not
very clear about the current status of the debate over the
conventional OTP (which is the case of more practical
significance than the case of infinite stream in my humble
view). Is it correct to say that Shannon's paper doesn't
deal with the conventional OTP and hence he has not proved
the perfect security of the conventional OTP (and hence
some of the literatures seem to be a bit problematic
on the issue)? If yes, is the conventional OTP perfectly
secure or not and how to rigorously prove that in the
positive case? Thanks.
M. K. Shen
--
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: where can I find information about DES?
Date: Sat, 09 Jun 2001 18:31:27 +0200
doublemc wrote:
>
> I´m searching information about DES.
If you are not unconditionally needing the original
standard document, look it up in the commonly recommended
textbooks (Stinson, Schneier, Menezes et al., etc.) or do
a search over the internet.
M. K. Shen
--
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Uniciyt distance and compression for AES
Date: 9 Jun 2001 16:36:08 GMT
[EMAIL PROTECTED] (Tom St Denis) wrote in
:
>Also to drag the dead around (like he does to David Wagner) he once said
>he found a short cut attack on RC5 that would reduce the keyspace to
>nothing. I wonder what came of that? He hasn't won the RC5 64 challenge
>yet so I guess he's a BS'ing liar (as he would put it).
>
AS you can tell Tom is full of shit. When did I say something
about short cut attack on RC5 that would reduce the keyspace
to nothing. Or are you just blowing smoke out your ass as usual.
I guess I could can aruging with Tom as usual. But its really
a waste of time. You can belive his distorted lies of you wish.
I for one think the only sane thing is to put him back in my kill
file for another month. Since arguing with him is totally
unproductive.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
--
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: cubing modulo 2^w - 1 as a design primitive?
Date: Sat, 09 Jun 2001 18:40:00 +0200
Tom St Denis wrote:
>
> "Mark Wooding" <[EMAIL PROTECTED]> wrote:
> > Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> > > It is a bijection since 3 does not divide the order for w=32 or w=64.
> >
> > It's a bijection in Z/(2^w - 1)Z. Unfortunately, we're probably
> > actually working in Z/(2^w)Z. As a result, the mapping is biased,
> > noninjective and nonsurjective. I can't see an attack against sixteen
> > rounds, but that doesn't
Cryptography-Digest Digest #574
Cryptography-Digest Digest #574, Volume #14 Sat, 9 Jun 01 12:13:01 EDT
Contents:
Re: National Security Nightmare? (Tim Tyler)
Re: National Security Nightmare? (Tim Tyler)
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: cubing modulo 2^w - 1 as a design primitive? ("Peter L. Montgomery")
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: Brute-forcing RC4 (Charles Lyttle)
Re: OTP WAS BROKEN!!! (Charles Lyttle)
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Uniciyt distance and compression for AES ("Tom St Denis")
Re: cubing modulo 2^w - 1 as a design primitive? (Mika R S Kojo)
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 9 Jun 2001 13:05:09 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
: In particular, I couldn't find any prohibition against the "GCHQ
: backdoor", i.e., a gentleman's agreement between the NSA and GCHQ to
: spy on each other's citizens and swap intercepts. If it is the
: policy of the NSA that such conduct is forbidden, how can I tell?
I believe GCHQ does not need to go to any such lengths if it wants to
spy on UK citizens.
The NSA gets other things (besides info on US citizens) from the UK -
things like the MenWith Hill Station - from which they can conveniently
spy on the rest of Europe.
No doubt the UK gets something out of it all. It seems likely that the
NSA has various desirable bargaining chips to play with.
--
__
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
--
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: National Security Nightmare?
Reply-To: [EMAIL PROTECTED]
Date: Sat, 9 Jun 2001 13:16:02 GMT
JPeschel <[EMAIL PROTECTED]> wrote:
: John Myre [EMAIL PROTECTED] writes:
:>JPeschel wrote:
:>> No, Phil, the English of Americans and the British is one language.
:>Barely.
: Barely? How so?
There are at least a few irritating differences. These irk me whenever I
use programming languages written by Americans - because they don't seem
to know how to spell things like "colour" properly ;-)
--
__
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
--
Subject: Re: Uniciyt distance and compression for AES
From: [EMAIL PROTECTED]
Date: 09 Jun 2001 09:49:17 -0400
[EMAIL PROTECTED] (SCOTT19U.ZIP_GUY) writes:
>
> Actaully your quite wrong there is not needed to reject meaningless
> messages by compression. What compression does is to make a large
> set of files smaller.
Actually, it makes a *tiny* set of files smaller--so tiny as to be
practically nonexistent. It makes a similarly tiny set of files *much*
larger. The vast majority of files are barely changed in size--they may
stay the same, get slightly larger, or get slightly smaller.
> Yes if it redues redunacy in messages yes many meaningless ones will
> be resduced to. So what. But the very fact of reducing it in your
> target set increase the density of those messages.
>From practically zero to practically zero. It may ``increase'' the
density, but not enough to make a difference. (Unless extremely careful
effort is devoted to exactly that outcome.)
Len.
--
Frugal Tip #58:
Make people give you money at gunpoint. But do it in a nice way so they
won't feel bad about the experience overall.
--
Subject: Re: Uniciyt distance and compression for AES
From: [EMAIL PROTECTED]
Date: 09 Jun 2001 09:55:23 -0400
"Tom St Denis" <[EMAIL PROTECTED]> writes:
>
> Typically random ASCII messages will not compress much if any at all.
One would expect them to compress by about 12.5% at least, since every
eighth bit is known to be zero. Which isn't ``hardly any'', but is still
quite a bit less than English text.
> What I don't get is why do you think brute force is [impossible] or [very
> hard]? I can still guess the key, I can still try to decompress and I can
> still check for proper ASCII and english digrams.
Bingo! For messages of realistic (and still very small) size, the
likelihood of a false positive is essentially zero--unless some
specific property of the codec ensures otherwise. Which requires
proof.
> For example if I see "PQ" or "MZ" etc in the plaintext I can be sure I've
> most likely guessed the key wrong.
Note that random padding can help defeat such statistical analysis--but
all th
Cryptography-Digest Digest #573
Cryptography-Digest Digest #573, Volume #14 Sat, 9 Jun 01 09:13:01 EDT
Contents:
Re: Shannon's definition of perfect secrecy (Tim Tyler)
Re: Anyone Heard of "Churning" (Tim Tyler)
Re: Algorithms ("Vance Gloster")
Re: Uniciyt distance and compression for AES ([EMAIL PROTECTED])
Re: Alice and Bob Speak MooJoo ([EMAIL PROTECTED])
Hex notation ("Adam O'Brien")
Re: Alice and Bob Speak MooJoo (Quisquater)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: Uniciyt distance and compression for AES (Andreas Gunnarsson)
Re: Hex notation (Nicol So)
Differential cryptanalysis ("Adam O'Brien")
Re: Uniciyt distance and compression for AES ("Tom St Denis")
Re: Differential cryptanalysis ("Tom St Denis")
Re: Uniciyt distance and compression for AES ("Tom St Denis")
Re: cubing modulo 2^w - 1 as a design primitive? (Mark Wooding)
Re: Hex notation (Mathew Hendry)
Re: Uniciyt distance and compression for AES (SCOTT19U.ZIP_GUY)
Re: practical birthday paradox issues (Johnny Bravo)
Mantin-Shamir's RC4 distinguisher paper and RC4 *student* paper ("Michael Lee")
Re: cubing modulo 2^w - 1 as a design primitive? ("Tom St Denis")
Re: Mantin-Shamir's RC4 distinguisher paper and RC4 *student* paper ("Scott Fluhrer")
Re: Hex notation (Tim Tyler)
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Shannon's definition of perfect secrecy
Reply-To: [EMAIL PROTECTED]
Date: Sat, 9 Jun 2001 09:00:04 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> My main concern is with the definition and usage of the term
:> "perfect secrecy" - I'd like to see what Shannon wrote,
:> whether his proof relates to what he wrote, and whether others
:> have followed his usage properly.
: This is from the scanned copy of "Communication Theory of Secrecy Systems"
: at
Thanks for that URL - and for the text. I didn't know this was available
online.
: Several things are clear from this: [...]
: - Nowhere does the paper say that the key length and message length of
:a perfect system are the same [...]
They don't need to be.
: - The footnote about traffic analysis suggests sending "blank" messages,
:which obviously requires the ciphertext distribution for blank messages
:to be the same as for normal messages [...]
Yes - if perfect secrecy is to be maintained ;-)
:> ...but [Shannon] is also supposed to have proved that the (conventional?)
:> OTP has [perfect secrecy], which it does not. I'll resolve the apparent
:> friction between these ideas by reading his actual words and proof.
: He only mentions the Vernam cipher (i.e. OTP) for the case of potentially
: infinite length streams, and for a definition of perfect secrecy adapted
: to that case. [...]
Yes - he doesn't deal with the conventional OTP on finite files in the
passage you quote.
--
__
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
--
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Anyone Heard of "Churning"
Reply-To: [EMAIL PROTECTED]
Date: Sat, 9 Jun 2001 09:34:55 GMT
Stephen Thomas <[EMAIL PROTECTED]> wrote:
: [This didn't get a response in sci.crypt.research, so I thought I'd try here.]
: Apparently, ATM Passive Optical Networks (APONs) have standardized on
: an "encryption" algorithm refered to as "churning." Does anyone know
: anything about this? Especially details on the algorithm. (FWIW, PONs
: are shared media networks like cable modems.)
: The only references I can find are:
: APON uses a 24-bit key churning mechanism
: Churning is a memoryless transformation of one byte to a
: different byte
A superficial search suggests that the "churning" of keys is somtimes used
as a generic term for the passing of a key through a one-way hash
function, or similar.
That doesn't square with "Churning is a memoryless transformation of one
byte to a different byte" - but that apparently comes from a marketing
document.
--
__
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
--
From: "Vance Gloster" <[EMAIL PROTECTED]>
Subject: Re: Algorithms
Date: Sat, 9 Jun 2001 03:17:22 -0700
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Well if you want the algorithms for Digital Signatures, there are 3 of
them
> in FIPS 186-2, those are a good beginning, you can them compare these to
NSS
> (from NTRU www.ntru.com), various PKCS1 versions, ACE Sign, ESIGN, FLASH,
> QUARTZ, SFLASH (all 5 available from
If you are researching digital signatures, you need to take a look at the
X.509 standard.
Vance Gloster One should never listen. To listen is a sign of
[EMAIL PROTECTED] indifference to one's hearers. -Oscar Wilde
http://www.vancesoft.com/vmghome
--
From: [EMAIL PROTECTED]
Subject: Re: Uniciyt distance and compressio
Cryptography-Digest Digest #572
Cryptography-Digest Digest #572, Volume #14 Sat, 9 Jun 01 05:13:01 EDT
Contents:
Shannon's definition of perfect secrecy (David Hopwood)
Re: Shannon's definition of perfect secrecy (SCOTT19U.ZIP_GUY)
Re: OTP WAS BROKEN!!! ("Paul Pires")
Re: Alice and Bob Speak MooJoo ("Neil Couture")
Re: Bow before your new master (Wander)
Re: National Security Nightmare? (JPeschel)
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and (Mok-Kong
Shen)
Re: Rip Van Winkle (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Date: Sat, 09 Jun 2001 02:04:39 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Subject: Shannon's definition of perfect secrecy
=BEGIN PGP SIGNED MESSAGE=
Tim Tyler wrote:
> My main concern is with the definition and usage of the term
> "perfect secrecy" - I'd like to see what Shannon wrote,
> whether his proof relates to what he wrote, and whether others
> have followed his usage properly.
This is from the scanned copy of "Communication Theory of Secrecy Systems"
at (the pages numbered 679 to
683). It's compilable LaTeX.
\documentclass[a4paper,11pt]{llncs} \def\Mod{{\rm Mod\ }}
\def\log{\:{\rm log}\:} \def\K{\hspace{2em}\raisebox{1ex}{$K$}}
\def\h{\hline\vspace{-2ex}\\} \def\s{\hspace{1em}}
\begin{document} \setcounter{section}{9} \setcounter{theorem}{5}
Excerpt from ``Communication Theory of Secrecy Systems" by Claude Shannon,
in the Bell System Technical Journal, Vol 28, October 1949, pages 656--715.
% Section 10
\section{Perfect Secrecy}
Let us suppose the possible messages are finite in number $M_1, \cdots, M_n$
and have {\em a priori} probabilities $P(M_1), \cdots, P(M_n)$, and that
these are enciphered into the possible cryptograms $E_1, \cdots, E_m$ by
\[
E = T_i M.
\]
The cryptanalyst intercepts a particular $E$ and can then calculate, in
principle at least, the {\em a posteriori} probabilities for the various
messages, $P_E(M)$. It is natural to define {\em perfect secrecy} by the
condition that, for all $E$ the {\em a posteriori} probabilities are equal
to the {\em a priori} probabilities independently of the values of these.
In this case, intercepting the message has given the cryptanalyst no
information.\footnote[9]
{
A purist might object that the enemy has obtained some information in
that he knows a message was sent. This may be answered by having among
the messages a ``blank" corresponding to ``no message." If no message
is originated the blank is enciphered and sent as a cryptogram.
Then even this modicum of remaining information is eliminated.
}
Any action of his which depends on the information contained in the
cryptogram cannot be altered, for all of his probabilities as to what the
cryptogram contains remain unchanged. On the other hand, if the condition
is {\em not} satisfied there will exist situations in which the enemy has
certain {\em a priori} probabilities, and certain key and message choices
may occur for which the enemy's probabilities do change. This in turn may
affect his actions and thus perfect secrecy has not been obtained. Hence
the definition given is necessarily required by our intuitive ideas of
what perfect secrecy should mean.
A necessary and sufficient condition for perfect secrecy can be found as
follows: We have by Bayes' theorem
\[
P_E(M) = \frac{P(M) P_M(E)}
% ---
{P(E)}
\]
in which:
\begin{tabular}{rcp{0.75\textwidth}}
$ P(M)$ &=& {\em a priori} probability of message $M$. \\
$P_M(E)$ &=& conditional probability of cryptogram $E$ if message
$M$ is chosen i.e. the sum of the probabilities of all
keys which produce cryptogram $E$ from message $M$.\\
$ P(E)$ &=& probability of obtaining cryptogram $E$ from any cause.\\
$P_E(M)$ &=& {\em a posteriori} probability of message $M$ if
cryptogram $E$ is intercepted.
\end{tabular}
For perfect secrecy $P_E(M)$ must equal $P(M)$ for all $E$ and all $M$.
Hence either $P(M) = 0$, a solution that must be excluded since we demand
the equality independent of the values of $P(M)$, or
\[
P_E(M) = P(M)
\]
and we have perfect secrecy. Thus we have the result:
% Theorem 6
\begin{theorem}
A necessary and sufficient condition for perfect secrecy is that
\[
P_M(E) = P(E)
\]
for all $M$ and $E$. That is, $P_M(E)$ must be independent of $M$.
\end{theorem}
Stated another way, the total probability of all keys that transform $M_i$
into a given cryptogram $E$ is equal to that of all keys transforming $M_j$
into the same $E$, for all $M_i, M_j$ and $E$.
Now there must be as many $E$'s as there are $M$'s since, for a fixed $i$,
$T_i$ give
