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 <http://www3.edgenet.net/dcowley/docs.html> (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$ gives a one-to-one correspondence between all the $M$'s and some of
the $E$'s. For perfect secrecy $P_M(E) = P(E) \neq 0$ for any of these
$E$'s and any $M$. Hence there is at least one key transforming any $M$
into any of these $E$'s. But all the keys from a fixed $M$ to different
$E$'s must be different, and therefore {\em the number of different keys
is at least as great as the number of $M$'s}. It is possible to obtain
perfect secrecy with only this number of keys, as one shows by the
following example: Let the $M_i$ be numbered 1 to $n$ and the $E_i$ the
same, and using $n$ keys let
\[
T_i M_j = E_s
\]
where $s = i + j\ (\Mod n)$. In this case we see that
$P_E(M) = \frac{1}{n} = P(E)$ and we have perfect secrecy. An example is
shown in Fig. 5 with $s = i + j - 1\ (\Mod 5)$.
% Fig. 5 -- Perfect system.
%
% Figure shows a fully-connected mesh between M_1 to M_5 on the left, and
% E_1 to E_5 on the right. The line from M_j to E_s is labelled i, with
% s = i + j - 1 (mod 5).
Perfect systems in which the number of cryptograms, the number of
messages, and the number of keys are all equal are characterized by the
properties that (1) each $M$ is connected to each $E$ by exactly one line,
(2) all keys are equally likely. Thus the matrix representation of the
system is a ``Latin square."
In MTC it was shown that information may be conveniently measured by
means of entropy. If we have a set of possibilities with probabilities
$p_1, p_2, \cdots, p_n$, the entropy $H$ is given by:
\[
H = -\sum{p_i \log p_i}.
\]
In a secrecy system there are two statistical choices involved, that of
the message and of the key. We may measure the amount of information
produced when a message is chosen by $H(M)$:
\[
H(M) = -\sum{P(M) \log P(M)},
\]
the summation being over all possible messages. Similarly, there is an
uncertainty associated with the choice of key given by:
\[
H(K) = -\sum{P(K) \log P(K)}.
\]
In perfect systems of the type described above, the amount of
information in the message is at most log $n$ (occurring when all
messages are equiprobable). This information can be concealed
completely only if the key uncertainty is at least log $n$. This is
the first example of a general principle which will appear frequently:
that there is a limit to what we can obtain with a given uncertainty
in key---the amount of uncertainty we can introduce into the solution
cannot be greater than the key uncertainty.
The situation is somewhat more complicated if the number of messages
is infinite. Suppose, for example, that they are generated as infinite
sequences of letters by a suitable Markoff process. It is clear that
no finite key will give perfect secrecy. We suppose, then, that the
key source generates key in the same manner, that is, as an infinite
sequence of symbols. Suppose further that only a certain length of
key $L_K$ is needed to encipher and decipher a length $L_M$ of message.
Let the logarithm of the number of letters in the message alphabet be
$R_M$ and that for the key alphabet be $R_K$. Then, from the finite
case, it is evident that perfect secrecy requires
\[
R_M L_M \leq R_K L_K.
\]
This type of perfect secrecy is realized by the Vernam system.
These results have been deduced on the basis of unknown or arbitrary
{\em a priori} probabilities of the messages. The key required for
perfect secrecy depends then on the total number of possible messages.
One would expect that, if the message space has fixed known statistics,
so that it has a definite mean rate $R$ of generating information, in
the sense of MTC, then the amount of key needed could be reduced on the
average in just this ratio $\frac{R}{R_M}$, and this is indeed true. In
fact the message can be passed through a transducer which eliminates
the redundancy and reduces the expected length in just this ratio, and
then a Vernam system may be applied to the result. Evidently the amount
of key used per letter of message is statistically reduced by a factor
$\frac{R}{R_M}$ and in this case the key source and information source
are just matched---a bit of key completely conceals a bit of message
information. It is easily shown also, by the methods used in MTC, that
this is the best that can be done.
Perfect secrecy systems have a place in the practical picture---they
may be used either where the greatest importance is attached to complete
secrecy---e.g., correspondence between the highest levels of command, or
in cases where the number of possible messages is small. Thus, to take
an extreme example, if only two messages ``yes" or ``no" were anticipated,
a perfect system would be in order, with perhaps the transformation table:
\begin{center}\begin{tabular}{c@{\s}|@{\s}c@{\s}c}
$M \K$ & $A$ & $B$ \\
\h% -------------------
yes & 0 & 1 \\
no & 1 & 0 \\
\end{tabular}\end{center}
The disadvantage of perfect systems for large correspondence systems is,
of course, the equivalent amount of key that must be sent. In succeeding
sections we consider what can be achieved with smaller key size, in
particular with finite keys.
\end{document}
Several things are clear from this:
- Perfect secrecy is defined for an arbitrary message space, as Tim
says.
- Nowhere does the paper say that the key length and message length of
a perfect system are the same (for one case it gives an inequality
relating them, but that's all).
- 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, regardless of what the length
of a blank message is considered to be.
- The paper explicitly mentions the possibility of using "a transducer
which eliminates redundancy", i.e. what we now call a compression
algorithm, before encryption with a perfect system.
> ...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. Arguably that definition is not as strict as the definition for
finite messages, since the rate at which the ciphertext is sent gives away
information about the rate at which the plaintext is generated.
> I'm curious to learn the historical roots of the (clearly mistaken) idea
> that conventional OTPs are perfect in this way. Is Shannon responsible?
> ...or those who came after him?
The idea that perfect secrecy is only defined for fixed message lengths is
certainly not supported by the paper.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOyF0yTkCAxeYt5gVAQGzbgf/evTAgidG2SHyLeILozNr3dEUT7+X0dVw
el2omJ3MO34TTizPj4VNNjUVjRI5nT2XkbJoPuNAJZAwoaWBhl4VbeG1C0zXh+tq
LR5/OmKPWyQ8X43ryBv1N9bdbXvauDoFpTT968QK6fwvYxFNJFIwv+0dxVsnU92B
BfkeGZRx6uvteDYTZpeqKtOX8todOkqqvau2/3NE0uWinP3LQwMY1apzXWx0mCjr
bu/Qhcdc12pvYZTmQ8vEZJegs34yb6r3viL2qD5K1pamf2vtb24L6s3dwxeKB3bI
UulBSGn8MnV5Ts/dcfhmPbBcyKoV9OyxhUNIAvsRzFuR7vXgidhJvA==
=KNUx
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Shannon's definition of perfect secrecy
Date: 9 Jun 2001 04:08:39 GMT
[EMAIL PROTECTED] (David Hopwood) wrote in
<[EMAIL PROTECTED]>:
>Perfect systems in which the number of cryptograms, the number of
>messages, and the number of keys are all equal are characterized by the
>properties that (1) each $M$ is connected to each $E$ by exactly one line,
>(2) all keys are equally likely. Thus the matrix representation of the
>system is a ``Latin square."
>
Actually you only quoted part of the paper. But the above portion
is also directly related to the long long thread. Notice each $M$ is
connect to each $E$. The reason for this is that an encrypted message
could have come from any possible input message of the set.Yes ths
does not say that you have to use an OTP for all the same length. Though
doing so would allow a "perfect security" system to be built.
But what it clear shows. Is that if you have a set of messages
of different lengths. If you only encrypted them to the input message
length. Then your have created several residue classes for the set.
And an encrypted message of one length will not map "be connected"
to input messages of other lengths thus meaning you do not have
"perfect security".
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: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Fri, 8 Jun 2001 21:18:56 -0700
Al <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Interesting...
> Your replies seem to suggest that you think there is some merit in
> what newbie says...
I made no comment on newbie. It had to do with lurkers
who only come out to engage crippled targets.
My reply doesn't suggest what I think, it clearly spells it out.
Small investment, negligible contribution.
> 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,
Could be? not very likely.
>thats the point of this OTP thread.
> Do you guys get out much?
Not really but thanks for the interest.
Paul
------------------------------
From: "Neil Couture" <[EMAIL PROTECTED]>
Subject: Re: Alice and Bob Speak MooJoo
Date: Sat, 9 Jun 2001 00:22:58 -0700
Reply-To: "Neil Couture" <[EMAIL PROTECTED]>
"Robert J. Kolker" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> [EMAIL PROTECTED] wrote:
>
> >
> > > If there were no Rosetta Stone Egyptian hieroglyphs would
> > > be opaque to us.
> >
> > Perhaps--but if we were able to observe living Egyptians in action, we
> > would eventually get the idea.
>
> At the time the French got a hold of the Rossetta Stone there
> were no living speakers or writers of ancient egyptian. The
> closest thing to it, was the liturgy of the coptic church and
> the written language had been lost by then.
>
> >
> >
> > Of course, whether that's practical in wartime or not is a separate
> > question. There are other weaknesses to this idea, which I mentioned
> > before: (1) if there are no native speakers, then the cost of teaching
> > the "language" is high. (2) If there are dictionaries, then a stolen
> > dictionary == a stolen codebook. (3) If a unit loses its Orawanee
> > Eskimo radioman, it must communicate in the clear.
>
> Or go back to using crypto.
>
> The best form of cryptography is clear communiction in
> a mostly unknown language.
>
> Bob Kolker
>
>
that's it!
------------------------------
From: Wander <[EMAIL PROTECTED]>
Crossposted-To:
alt.drugs.pot,sci.electronics.design,sci.electronics.repair,sci.environment
Subject: Re: Bow before your new master
Date: Sat, 09 Jun 2001 05:50:42 GMT
How many of us have had these thoughts, these feelings, and have been unable
to express them is such a poignant, hartfelt way?
Thank you for sharing and teaching.
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> That's right you stupid, inbred, homosexual, redneck, motherfucking,
> brain dead, useless cocksuckers! I'm taking over all of Usenet! There
> isn't a fucking thing you can do about it either! You're all a bunch
> of worthless scum bags, and now you will all answer to me! If you
> don't like this fact TOO FUCKING BAD! You think you've had trouble
> with kooks before? You aint seen nothing yet! I will go down in the
> annals of history as the man who brought you to your knees! Now get
> down on your knees and pay proper tribute to my glorious self! While
> you're down there SUCK MY COCK! I know you want to!
>
> I AM BRENT K KOHLER LORD AND HIGH MASTER OF USENET!
>
> My first royal order to all of you peons is that from this time
> foward you will add the following signature to all of your posts!
>
>
> ***** This was posted with the express permission of *****
> **********************************************************
> ** HIS HIGHNESS BRENT KOHLER LORD AND MASTER OF USENET **
> **********************************************************
> *********** We are simple servants of his will ***********
>
>
> This will be appended to the bottom of all your posts with absolutely
> no exceptions! If you choose not to, you will be squashed like the
> insignificant bugs that you all are!
>
> I am running Usenet now! You may only post messages because I for
> the time being am allowing it! Do you faggots understand me!
>
> THIS IS THE DAWNING OF THE AGE OF BRENT!
>
> ALL HAIL BRENT K KOHLER LORD AND HIGH MASTER OF USENET!
>
>
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 09 Jun 2001 07:11:04 GMT
Subject: Re: National Security Nightmare?
John Myre [EMAIL PROTECTED] writes:
>JPeschel wrote:
><snip>
>> No, Phil, the English of Americans and the British is one language.
><snip>
>
>Barely.
>
Barely? How so?
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Sat, 09 Jun 2001 10:12:08 +0200
"Douglas A. Gwyn" wrote:
>
> Mok-Kong Shen wrote:
> > ... Whitehead and Russell's famous book 'Principia
> > Mathematica' ... is a work well respected by
> > mathematicians, as far as I am aware.
>
> Well, not exactly. PM is famous because it was an ambitious
> attempt to implement a model of mathematics which we now know
> to be wrong. PM is also known for introducing the "ramified
> theory of types", which has not generally been deemed to
> properly solve the kind of problem that motivated it.
> PM has no practical value for working mathematicians.
While my knowlegde is too far from being able to understand
the matter, I do like very very much to know of the name of
a good reference where it is claimed/established that the
theory which Whitehead and Russell developed (or further
developed) is wrong. Could you please supply such a
reference? Thanks in advance.
> > I am sure that
> > there are very good reasons (though I am ignorant of these)
> > why a foundation of a couple of hundred pages is needed
> > in order to rigorously prove 1+1=2.
>
> The goal wasn't simply to rigorously prove 1+1=2; it doesn't
> take hundreds of pages to do that, even along the lines of PM.
I didn't say that a couple of hundred pages were exclusively
devoted to the proof of that. The work certainly deals
with lots and lots of other stuffs. But that seems to be
an appropriate foundation for that as considered by the
authors. If simply twenty pages (or less) would have been
sufficient for that apparently very trivial ('apparent'
for an ignorant like me) issue, I stronly believe that they
would have put that proposition at the beginning part of
their book or perhaps even dispensed with giving a proof
at all (perhaps at most with a one line mention only).
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Rip Van Winkle
Date: Sat, 09 Jun 2001 10:46:12 +0200
Tom St Denis wrote:
>
> I thought the RVW cipher was the only "perfectly secure" method? I.e you
> send X streams at Y bits per second constantly and the key is when and over
> what channels the message is really being sent. (Of course you xor the RNG
> output with the message).
>
> This way you don't know when the message is being sent or over what
> channels.
That cipher is shortly sketched in AC. I understand too
little of it but I guess that its main characteristic
lies in the 'delay'. Mixing different stuffs and sending
over different channels (in some unpredictable manner)
is commonly considered a rather general aspect that is
not exclusively a characteristic of that scheme, if
I don't err.
BTW, in another thread you mentioned about a Dover math
book that has only 13 words (proper content, if I
understood right) in it. I have told that news to a
couple of friends. They are very eager to get that book
'as soon as possible' like me. Could you please post
the title and author name right now? I hope that this
is certainly o.k. for you. Thanks a lot in advance.
M. K. Shen
===============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Sat, 9 Jun 2001 08:46:08 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
:>I'm well aware of the shortcomings of the method - and believe BICOM
:>should probably have an option for prepending a random IV - despite
:>the fact that this would destroy BICOM's bijectivity.
: Actually I like the purity of Matts work. [...]
Don't get me wrong - so do I. I'm not talking about having this on by
default.
: But since one has access to the soucrce code there is no reason someone
: could modify it on there own. Such that a different inital IV could
: be assumed. Sort of like a secondary password if you wish.
If this was done, the IV should probably be prepended (in the clear) to
the encrypted message - rather than treated as additional key material.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
