Cryptography-Digest Digest #550, Volume #14 Thu, 7 Jun 01 13:13:01 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: Best, Strongest Algorithm (gone from any reasonable topic) ("John A. Malley")
Re: Def'n of bijection ("Paul Pires")
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
Re: OTP WAS BROKEN!!! (Tim Tyler)
Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and (Phil
Carmody)
Re: OTP WAS BROKEN!!! ("Robert J. Kolker")
Re: practical birthday paradox issues (Phil Carmody)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Mok-Kong Shen)
Re: Best, Strongest Algorithm (gone from any reasonable topic)
([EMAIL PROTECTED])
Re: Best, Strongest Algorithm (gone from any reasonable topic) (Tim Tyler)
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 15:09:19 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:> [EMAIL PROTECTED] wrote:
:>: Tim Tyler <[EMAIL PROTECTED]> writes:
:>:> Tom St Denis <[EMAIL PROTECTED]> wrote:
:>:>: Or if you just pad the bloody thing to a multiple of say 64 bytes. [...]
:>:>
:>:> Still not enough for perfect secrecy :-(
:>:
:>: Right--no matter what ``a multiple'' means.
:>
:> That's correct - so long as no restraints are placed on the set of
:> possible plaintexts.
: Exactly. So why do you keep switching premises? Specifically:
: 1. When somebody says, ``OTP on padded messages gives (Tim Tyler's
: definition of) perfect secrecy,'' you reply, ``No, because no
: amount of padding is enough.'' In other words, you assume that the
: space of plaintexts is infinite.
: 2. When somebody replies, ``Okay: if the space of messages is infinite,
: then (your definition of) perfect secrecy is impossible to achieve.''
: You reply, ``No, because the space of messages is actually finite.''
: (Or alternately, ``...has cardinality 2 in my universe.'')
You dare to misquote me in the course of misrepresenting my postion.
You misquote yourself as well to distort things still further - but I
guess that's your privelidge.
We can talk again when you have learned to put quotation marks around
stuff people have actually said.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 08:18:08 -0700
Tim Tyler wrote:
>
>
> : You probably question whether such usage leads to
> : Shannon's perfect security which, as you said, is claimed
> : to be a property of OTP. However, I don't see where in the
> : literature about OTP (in connection with perfect security)
> : the length enters into the argumentation, i.e. plays a role
> : in the proof.
Shannon's paper "Communications Theory of Secrecy Systems" addresses
this. Perfect secrecy is a property of the OTP (i.e. the Vernam cipher
specifically cited in that paper) AND message length DOES enter into the
argument. However, using an OTP is NOT required for perfect secrecy when
the set of messages is finite. :-)
>
> I also think that it's not mentioned. I beleive it is common to
> consider the domain where all plaintexts are the same length -
> perhaps in order to get the "perfect secrecy" result.
>
> : My memory of Shannon's paper is no good, but I don't think that he
> : considered the length of the messages.
>
> I don't think it was mentioned either - all the messages were the same
> length in the system in question.
> --
Shannon's important paper on cipher systems carefully considers the
length of the messages. Shannon shows the OTP is NOT required for a
finite set of messages to give perfect secrecy. (I've posted on this
before, given examples of such ciphers, just search google or drop me a
note by email for more specific examples. :-) )
The OTP is required for message sources with an infinite number of
messages. From page 682 of "Communications Theory of Secrecy Systems",
C. E. Shannon, Bell System Technical Journal, pp. 656-715, 1949:
"The situation [perfect secrecy] 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 Markov 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 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 [for perfect secrecy], it is evident that perfect secrecy
requires
R_m * L_m <= R_k * L_k.
This type of perfect secrecy is realized by the Vernam system."
We can model many message sources as "infinite sequences of symbols
generated by a suitable Markov process." Consider this post. Here I sit
early in the morning composing a message on-the-fly as if I'm such a
Markov process. (Oops, gotta get ready for my day job!) Say I want to
send it to you with perfect secrecy. There's no bag of messages fixed in
number and string lengths shared betwixt you, me, regular readers and
the silent majority of lurkers out there. So we can't all agree on a set
of mappings chosen by a set of keys that constitutes a cipher with
perfect secrecy for this finite set of messages. I can't say ahead of
time what exactly I will write to you, nor can you do the same for me.
So we use a Vernam system to encipher our messages to one another. We
prepare a shared OTP before we send messages to one another. And we need
to exchange/share as much OTP as messages stream we send. So our
communications fits this model of Shannon's - perfect secrecy for a
Markov process source generating an infinite sequence of symbols.
The length of any finite sequence passing between us tell nothing to Eve
that she doesn't already know. Eve knows the Markov process. She knows
the Markov process will generate an infinite sequence of symbols. She
knows the statistics of substrings that might appear.
Interception of any portion of the infinite sequence of symbols
generated by the Markov process and enciphered with perfect secrecy
using an OTP tells Eve nothing more than what she already knew about the
Markov process.
Hope this helps,
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Def'n of bijection
Date: Thu, 7 Jun 2001 08:33:24 -0700
John Myre <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> [EMAIL PROTECTED] wrote:
> <snip>
> > If every compressed file shrunk by at least one bit, then the
> > result could be compressed again, and again, until you've shrunk it
> > down to one bit.
> <snip>
>
> And then compress once more...
LOL
>
> JM
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 15:26:30 GMT
[EMAIL PROTECTED] wrote:
: Tim Tyler <[EMAIL PROTECTED]> writes:
:> [EMAIL PROTECTED] wrote:
:>: Tim Tyler <[EMAIL PROTECTED]> writes:
:>:> ``...a finitely odd stream...is an infinitely long sequence of
:>:> bits, but with the last 1 bit at a position finitely far from
:>:> the beginning...''
:>:
:>: Complete red herring; in the material you posted, that ``infinite
:>: sequence of 0s'' is not used for anything.
:>
:> Who are you to call it a "red herring"?
: A mathematician who can read English. (Don't forget where the burden
: of proof lies, BTW.)
I see. You think you know better how to explain how Matt Timmermans
compressor operates than Matt Timmermans himself. On your current
showing I beg to differ - but I guess such things are a matter of taste.
:> So, what was it about "all bits are significant to the output" that you
:> missed?
: Nothing. [...]
OK - so can you identify one bit in that stream which is *not* significant?
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 15:30:44 GMT
Al <[EMAIL PROTECTED]> wrote:
: Hey newbie...
: 23490123489234934789945892348234234765784567234623784623784682346238462378468723
: Which I'm sure you'll understand LOL
I hope you're not pretending you made that using an OTP.
Just look at all those "23"s and "234"s...
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: Help with Comparison Of Complexity of Discrete Logs, Knapsack, and
Date: Thu, 07 Jun 2001 15:57:44 GMT
Tom St Denis wrote:
> > You need a certain minimal background and mathematical maturity before
> > tackling hard problems. You need experience in knowing what works and
> > what doesn't work. The idea that some naiive "kid" will pop out of nowhere
> > and solve a hard problem "BECAUSE HE HAS NOT LEARNED THE WRONG APPROACH"
> > is ludicrous.
>
> I don't see a big argument for this. Most "great" mathmetiticans were teens
> when they invented stuff. The prime number theorem was written by a 15 yr
> old.
It was _conjectured_, not proved, from numerical evidence.
http://primepages.org/primes/howmany.shtml
> Thus I disproved your notion.
Nah, not really. In what way was Gauss 'naive'?
He was known to be able to do things better than the supervisors that
taught him for 7 years before he first conjectured the PNT.
Note also that the field (prime number density) was pretty bare in the
late C18, and so Gauss had no less expereience in the field than the
other great mathematicians of the time.
Phil
------------------------------
From: "Robert J. Kolker" <[EMAIL PROTECTED]>
Subject: Re: OTP WAS BROKEN!!!
Date: Thu, 07 Jun 2001 12:03:38 -0400
Gordon Burditt wrote:
>
> If the key is used MORE THAN ONCE, you can take the possible keys,
> slide them along other messages, and compute possible plaintexts
> from this. IF you get a sensible-looking plaintext, you now have
> a much-better-than-random-guess probability that this is the correct
> key, being re-used.
Isn't the entire point of the OTP to use each key only once? Why
else call it a One Time Pad? If two plaintexts are sent with the
same key, the second crypt can readily be decrypted.
What makes OTP difficult to use is key distribution and management.
The keys must be conveyed to the recievers (the Bobs of the world)
securely and the application of a key to an encrypted message must
be pre-arranged.
Bob Kolker
------------------------------
From: Phil Carmody <[EMAIL PROTECTED]>
Subject: Re: practical birthday paradox issues
Date: Thu, 07 Jun 2001 16:02:26 GMT
Dirk Bruere wrote:
>
> "Richard D. Latham" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > "Dirk Bruere" <[EMAIL PROTECTED]> writes:
> >
> > >
> > > One might make a guess at h/w capability given that the old WW2 custom
> > > electromech system was roughly as powerful as a Pentium 100MHz.
>
> > Surely you jest ?
>
> No. Based on recently declassified Brit stuff being used at Bletchley Park
> in WW2, namely things called 'bombes'.
> http://www.bcs.org.uk/publicat/ebull/mar99/news.htm
>
> From the British Computer Society (above):
> "The Bombe was an electro-mechanical device but so tuned to its one task
> that a simulation on a modern PC takes 15 hours to do what a Bombe did in 15
> minutes."
The Bombes were _massively_ parallel.
Why do I have an image of GIMPS running on HP calculators in my head!
Go see Bletchley Park. I've stood >| |< this far
from a running Colossus, and it was a moving experience. A small bit
of history very much come to life.
Phil
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 18:13:17 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> : An encrypted message Y, on arrival in the hand of the opponent,
> : has a 'concrete' form. It has a bit pattern and also a length,
> : which in the case of OTP processing with xor is equal to
> : the length of the plaintext X that the sender has input
> : into his software. Trivailly, (note) X has ALSO a concrete
> : form. We consider our X to be the original, i.e. the
> : ASCII text that the sender has actually written down
> : manually. Shannon's argument guarantees in this case that
> : the opponent's knowledge about X is not enhanced by his
> : having 'in addition' a corresponding Y. Now consider
> : carefully what this actually claims. Note that the
> : term 'his knowldege about X' is dependent on the very
> : 'existence' of X. Before X comes into being, 'his
> : knowledge about X' is not well-defined (excepting
> : perhaps the 'idea' of its non-existence). After X comes
> : into being, the opponent's a-priori knowledge of X
> : (now that we can talk about X) 'can' include the size of X.
>
> That's possible.
>
> If the attacker knows in advance that all messages that could be
> sent have the same size (which is what you are saying here) then
> the resulting system has perfect secrecy.
I am assuming that the message can be of different sizes
but the size of the ciphertext is equal to or is a known
function of the size of the plaintext (unless 'disguised'
as I suggested with 'randomizing').
>
> I think this is the system which Shannon's proof relates to.
>
> However, note that this systems is not the OTP as generally
> described. The OTP is not normally considered to be constrained
> in such a way that all messages are known on a-priori grounds to
> be the same size.
I am currently not yet very sure whether Shannon's paper
explicitly throw the length into his argumentation. (I
am asking John Malley for that.)
> : One can however reduce that a-priori
> : knowledge through varying the size of X, i.e. through
> : somehow transforming X to X_1 (reversibly, in effect
> : doing a superencipherment step) such that the size of
> : X_1 is now random (within a range that is feasible, of
> : course) and send with OTP processing the corresponding
> : Y_1. Shannon's argument again applies, now concerning
> : the pair X_1 and Y_1. But the 'a-priori knowldege of
> : the opponent' (and with it his a-posteriori knowldege,
> : of course) gets changed. For now, in lieu of the length
> : of the original ASCII text, he has a random value which
> : is no information for him.
>
> You seem to be talking about varying the size of
> the plaintext in the case where the attacker knows
> it is of fixed size.
>
> Scott and I are have previously discussed almost the
> exact opposite - taking plaintext of varying lengths
> and padding them until they are all indistinguishable
> from one another when encrypted.
>
> If your process that translates from X to X_1 is
> key dependent then you won't lose anything significant - but
> you won't gain in security either, if the attacker couldn't
> distingish the plaintexts in the first place because they
> all had the same length.
>
> Your procedure may well have value if the length of X
> is *not* known in advance, though.
Whether there are fixed or varying length of the naturally
created plaintext messages, one can always try to vary
the length (within certain extent), thus the result
would be always of varying length and these lengths
are random (pseudo-random).
>
> : [...] there could be cases that the size plays a role.
> : To illustrate, let's consider a hypothetical case where among the
> : messages communicated between a company A and a company B there is a
> : particular class of messages that always has a fixed length,
> : because it is a routine purchasing order that the manager
> : of A makes through filling a form (nowadays commonly in
> : a window on his computer) and sends. Let's say that
> : the other messages between A and B are all of varying
> : lengths, e.g. diverse business letters etc. etc. Now the
> : opponent can simply count the number of messages of the
> : said fixed length and know how many orders A has placed
> : with B [...]
>
> Yes.
>
> : One might say that this belongs to traffic analysis and not
> : encryption proper [...]
>
> Pah! Cryptanalysis usually involves analysing traffic. ;-)
If you don't object, so much the better.
>
> : [...] but anyway information is still information. Through randomizing
> : the size of the messages we make it difficult for the opponent to
> : gain that information.
>
> Key dependent padding would certainly help obscure length information -
> though it's not very likely to produce perfect secrecy,
> since for any message you'll still have an upper bound on the
> size of the plaintext if given the cyphertext.
There are other ways, e.g. sort of using homophones. There
are certainly upper bounds of what is do-able in practice.
If one assumes however infinite resources of the opponent,
then yes, one cannot prevent the length information from
being exploitable (at least to a tiny amount) by the
opponent. The consequence of that would be that OTP cannot
provide perfect security. Or am I missing something?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 18:13:32 +0200
Tim Tyler wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> :> : Tim Tyler wrote:
>
> :> :> Consider BICOM for example. It can map a 8 bit cyphertext to
> :> :> one of some 2^128 plaintexts - considerably more than your figure of 2^8.
> :>
> :> : There are in total 2^8 possible ciphertexts.
> :>
> :> You were talking about a *particular* 8 bit cyphertext, of which there was
> :> one, not 2^8
> :>
> :> There are *many* more than 2^8 possible cyphertexts altogether.
>
> : Sorry, I still don't understand. How could there be more
> : than 2^8 possible ciphertexts of length 8 bits?
>
> I never said that there were more than 2^8 possible ciphertexts of
> length 8 bits. I said there were more than 2^8 possible cyphertexts
> *altogether*.
>
> There are probably going to be at least as many cyphertexts as there are
> possible plaintexts.
Do we have a context about the key size and ciphertext
sizes at all, or are we discussing all possible keys
and ciphertexts? If the former, what are the 'sizes' that
applies to your sentences above? See however also below.
>
> :> : What is the cardinality of the set of plaintexts that correspond to them?
> :>
> :> Well you don't /really/ want to know that, but...
> :>
> :> The size of the set of plaintexts that could correspond to
> :> 2^8 cyphertexts them in some cyphersystems can be calculated by:
> :>
> :> How many possible plaintexts are there in your whole system?
> :>
> :> How many can be represented by your key? Multiply that by 2^8
> :> (for the number of different cyphertexts you asked me to consider).
> :>
> :> Take the smaller of these two figures, and you have my reply.
>
> : What if my key is 8 bits? I am confused.
>
> If your key is 8 bits each possible 8 bit cyphertext could map to one of
> 256 plaintexts. The maximum total number of plaintexts would thus be
> 256x256 = 65536.
>
> To see how a particular 8 bit cyphertext could map to more than 256
> different plaintexts, just get an 8 bit cyphertext, decrypt it with
> BICOM under a number of keys.
>
> You will see *many* different plaintexts come out - not just 256.
I was referring to the following that you wrote previously:
Yes it is. Consider BICOM for example. It can map a
8 bit cyphertext to one of some 2^128 plaintexts -
considerably more than your figure of 2^8.
Does the 2^128 come from using a 128 bit key for the
AES in it and there are 2^128 possible keys for AES?
If yes, I think I capture that, otherwise not yet.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Date: Thu, 07 Jun 2001 18:13:27 +0200
"John A. Malley" wrote:
>
> Tim Tyler wrote:
> >
> > : You probably question whether such usage leads to
> > : Shannon's perfect security which, as you said, is claimed
> > : to be a property of OTP. However, I don't see where in the
> > : literature about OTP (in connection with perfect security)
> > : the length enters into the argumentation, i.e. plays a role
> > : in the proof.
>
> Shannon's paper "Communications Theory of Secrecy Systems" addresses
> this. Perfect secrecy is a property of the OTP (i.e. the Vernam cipher
> specifically cited in that paper) AND message length DOES enter into the
> argument. However, using an OTP is NOT required for perfect secrecy when
> the set of messages is finite. :-)
I unfortunately don't have the paper easily available.
Could you kindly quote just one sentence in it showing
that the message length does enter into Shannon's argument
in a significant way?
> >
> > I also think that it's not mentioned. I beleive it is common to
> > consider the domain where all plaintexts are the same length -
> > perhaps in order to get the "perfect secrecy" result.
> >
> > : My memory of Shannon's paper is no good, but I don't think that he
> > : considered the length of the messages.
> >
> > I don't think it was mentioned either - all the messages were the same
> > length in the system in question.
> > --
>
> Shannon's important paper on cipher systems carefully considers the
> length of the messages. Shannon shows the OTP is NOT required for a
> finite set of messages to give perfect secrecy. (I've posted on this
> before, given examples of such ciphers, just search google or drop me a
> note by email for more specific examples. :-) )
>
> The OTP is required for message sources with an infinite number of
> messages. From page 682 of "Communications Theory of Secrecy Systems",
> C. E. Shannon, Bell System Technical Journal, pp. 656-715, 1949:
>
> "The situation [perfect secrecy] 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 Markov 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 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 [for perfect secrecy], it is evident that perfect secrecy
> requires
>
> R_m * L_m <= R_k * L_k.
>
> This type of perfect secrecy is realized by the Vernam system."
>
> We can model many message sources as "infinite sequences of symbols
> generated by a suitable Markov process." Consider this post. Here I sit
> early in the morning composing a message on-the-fly as if I'm such a
> Markov process. (Oops, gotta get ready for my day job!) Say I want to
> send it to you with perfect secrecy. There's no bag of messages fixed in
> number and string lengths shared betwixt you, me, regular readers and
> the silent majority of lurkers out there. So we can't all agree on a set
> of mappings chosen by a set of keys that constitutes a cipher with
> perfect secrecy for this finite set of messages. I can't say ahead of
> time what exactly I will write to you, nor can you do the same for me.
> So we use a Vernam system to encipher our messages to one another. We
> prepare a shared OTP before we send messages to one another. And we need
> to exchange/share as much OTP as messages stream we send. So our
> communications fits this model of Shannon's - perfect secrecy for a
> Markov process source generating an infinite sequence of symbols.
>
> The length of any finite sequence passing between us tell nothing to Eve
> that she doesn't already know. Eve knows the Markov process. She knows
> the Markov process will generate an infinite sequence of symbols. She
> knows the statistics of substrings that might appear.
> Interception of any portion of the infinite sequence of symbols
> generated by the Markov process and enciphered with perfect secrecy
> using an OTP tells Eve nothing more than what she already knew about the
> Markov process.
I don't fully understand the sentence 'The length ......
she doesn't already know.' Does the length of the message
belong to what she already knows (before getting the
message)? Further, does the length play a role in
the security? (My interpretation of your sentence
would be 'no', but this would seem to contradict what
you wrote at the beginning of this post where you said
that the length enters into the argument of Shannon.)
Thanks.
M. K. Shen
------------------------------
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
From: [EMAIL PROTECTED]
Date: 07 Jun 2001 12:17:01 -0400
Tim Tyler <[EMAIL PROTECTED]> writes:
>
> You dare to misquote me in the course of misrepresenting my postion.
Reread your posts with great care. You consistently make the space of
messages infinite (if people suggest that padding solves your problem),
but then make it finite (when people reply that your preceding remark
implies that perfect secrecy is impossible). The exact words with which
you perform the switch are completely irrelevant to this issue.
> We can talk again when you have learned to put quotation marks around
> stuff people have actually said.
Actually, it would be better if you attended some math courses before
discussing the subject again. It's fairly clear that you have little
or no mathematical background whatsoever. Suffice it to say, you will
never convince anyone of your claims for BICOM, if you don't even know
what a proof is, or how to go about constructing one.
Anyway, you did a neat job of ignoring the points I made, which
address the heart of your problems. To wit:
1. Number of plausible messages in the space of all messages of size 2510
bytes or less. This can be estimated reasonably (and conservatively) at
2^5 000. Since the space of all binary files up to 2510 bytes has size
around 2^20 000, the probability of a random file up to 2510 bytes being a
plausibly mistaken for an English message is something like 1 in 2^15 000,
or effectively zero.
2. Density of binary files up to 2510 bytes whose preimage under BICOM
is ``plausible'': I have no idea. I'm willing to bet, however, that
the odds of a BICOM preimage being ``plausible'' is essentially
zero. Can you prove that the probability of a random 2510-byte-or-less
file having a plausible decompression is larger than 1 in 2^20 000?
(If you can even prove, for random files of size 1024 bytes or less, that
plausible BICOM preimages are likelier than 1 in 2^1 000, then I'll keep
you in beer for the next six months.)
3. If you want at least one false positive to be found for at least 1%
of ciphertexts being brute-forced, assuming 128-bit keys, then the
probability of plausible BICOM preimages of files up to 1024 bytes
long, must be in the ballpark of 1 in 2^13. Can you prove anything
remotely resembling that?
You see, it's ``obvious'' to you that BICOM improves secrecy, because
there are ``lots'' of keys to try, and ``lots'' of plausible files
that shrink under BICOM--even though there are ``lots'' of files in
total.
Your problem boils down to this: you haven't the faintest idea what
``lots'' means--and in the three uses above, ``lots'' varies by
thousands of orders of magnitude.
(Note: many classic blunders by young mathematicians result from
confusing completely incompatible ideas of ``smallness''. For example,
did you know that the Real numbers can be expressed as the union of a
nowhere dense set and a set with Lebesgue measure 0? I've been collecting
such instances in my spare time for an expository paper.)
Len.
--
Profile. Don't speculate.
-- Dan Bernstein
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic)
Reply-To: [EMAIL PROTECTED]
Date: Thu, 7 Jun 2001 16:04:27 GMT
John A. Malley <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
: The OTP is required for message sources with an infinite number of
: messages.
With an infinite number of possible finite messages, perfect secrecy
is not a practical possibility.
: From page 682 of "Communications Theory of Secrecy Systems",
: C. E. Shannon, Bell System Technical Journal, pp. 656-715, 1949:
: "The situation [perfect secrecy] 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 Markov 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 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 [for perfect secrecy], it is evident that perfect secrecy
: requires
: R_m * L_m <= R_k * L_k.
: This type of perfect secrecy is realized by the Vernam system."
Thanks very much for the quotation.
Shannon is *only* considering messages that are infinite streams.
His argument doesn't apply to the transmission of finite files using an OTP.
Any subsequent attempt to cite this result as though it applied
without qualification to systems used for sending finite messages
is in danger of going severely off the rails.
--
__________
|im |yler http://rockz.co.uk/ http://alife.co.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
