>From: Jack Lloyd <[EMAIL PROTECTED]> >Sent: Mar 22, 2006 11:30 PM >To: cryptography@metzdowd.com >Subject: Re: Entropy Definition (was Re: passphrases with more than 160 bits >of entropy)
... As an aside, this whole discussion is confused by the fact that there are a bunch of different domains in which entropy is defined. The algorithmic information theory sense of entropy (how long is the shortest program that produces this sequence?) is miles away from the information theory sense of entropy, and even that has a bunch of different flavors. For the information theory meanings of entropy, what you're really talking about is a property of a probability distribution. You can do that in terms of Shannon entropy if you want to know about bounds on average bandwidth requirements for transmitting symbols from that distribution. You can look at guessing entropy if you want to know the -lg(expected work to guess the next symbol). You can look at min-entropy if you want a hard bound on how many symbols you need to sample to derive a 128-bit key that won't ever expose you to weaknesses based on how you selected it. And so on. Shannon entropy is the one most people know, but it's all wrong for deciding how many samples you need to derive a key. The kind of classic illustration of this is the probability distirbution: 0 occurs with probability 1/2 each other number from 1 to 2^{160}+1 happens with probability 2^{-161}. The Shannon entropy on this distribution is 81.5 bits. But if you tried to sample it once to generate an 80-bit Skipjack key, half the time, I'd guess your key on my first try. ... >Yes. Let's say the contents of tommorrow's NY Times has n bits of entropy (we >probably can't actually calculate n, but we know it is a finite and fixed >value). And the LA Times from the same day will also have some amount of >entropy (call it n'). However, the entropy of the two papers combined would >(probably) not be n+n', but some number x st min(n,n') <= x <= n+n', because >the two papers will report on many of the same issues, carry some of the same >AP stories, and so forth. This redundant information doesn't increase the >entropy (reading the same AP story in a second newspaper wouldn't give you any >new information). Right. If the probabilities are independent, you can add the entropies. That's why they're defined in log terms. --John --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]