Cryptography-Digest Digest #520, Volume #11 Sun, 9 Apr 00 19:13:01 EDT
Contents:
Re: Skipjack algorithm. (CLSV)
Re: Turing machine ("John A. Malley")
Re: Blowfish constants (lordcow77)
Re: GSM A5/1 Encryption (David A. Wagner)
Re: GSM A5/1 Encryption (David A. Wagner)
Security model for blinded-key recipient-hiding encryption (David Hopwood)
Re: Q: Entropy (Xcott Craver)
----------------------------------------------------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: Skipjack algorithm.
Date: Sun, 09 Apr 2000 23:13:54 +0200
[EMAIL PROTECTED] wrote:
>
> I've implemented the Skipjack algorithm in assembler, and the win32 dll +
>source are at
> http://ingrato.penguinpowered.com/~fastwalker - thanks if you would check it out,
>and give me comments.
> It is claimed Skipjack provides insufficient security due to its short (80 bit) key,
>my question is
> has anyone examined the security of Skipjack used with larger than 80 bit (1024 bits
>is possible) keys?
> Instinct tells me a 1024 bit key varient of Skipjack would be exponetionally more
>secure, however I seem
> to remember reading that an implementation of DES using independent subkeys for a
>total 768 bit key did
> little for it's security, this is perplexing and warrents explanation.
> Another Question, would a longer key varient of Skipjack (considering the
>ease with which this is accomplished
> and the fact that the algorithm is not changed) be a possible AES candidate? I'd
>much rather use a strengthened version
> of what the government uses then any AES candidate to date. Thanks.
One of the official remarks on the algorithm is
that the length of its keys can not be extended.
I don't know where I read it but if you look for
it you probably can find it. This is possibly the
optimal length for this cipher. It might as well
be one of the (secret) design criteria.
Regards,
CLSV
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Turing machine
Date: Sun, 09 Apr 2000 14:18:34 -0700
The B-Machine sounds like Alan Turing's "B-type unorganized machine" of
1948. It's described in a paper titled "Intelligent Machinery" written
while Turing worked at the National Physical Laboratory in London,
England. Sir Charles Darwin ( grandson of the "evolutionary" Darwin ),
the lab's director, dismissed it as a "schoolboy essay." This paper
was not published until 1968 - years after Turing's death.
Turing described Connectionism (a.k.a. neural networks) in that paper
some 10 years before Rosenblatt's paper in 1958. In Turing's B-type
unorganized machine, every neuron connected to every neuron, unlike the
3-layer back-propogation neural nets or the Kohonen topological neural
net sheets so prominent in today's NN research/development.
See the excellent article in the April, 1999 Scientific American, "The
Lost Brainstorms of Alan Turing."
John A. Malley
[EMAIL PROTECTED]
[EMAIL PROTECTED] wrote:
>
> In article <SZCH4.23924$[EMAIL PROTECTED]>,
> "Stou Sandalski" <tangui [EMAIL PROTECTED]> wrote:
>
> > Oh and I read a long time ago somewhere about this machine I think it
> was
> > called a B-Machine (or something similar) designed (theoreticaly) by a
> > mathematician from early this century (I think) and it looked to me
> like a
> > neuro-network (the b-machine had states like organized or trained and
> > unorganized). I remember there was some kind of device attached to it
> that
> > theoreticaly could be used to solve any problem (you know the...
> assume a
> > device such that can solve any problem in the universe, deal) Does
> anyone
> > have any clue what this is? I would realy realy like to learn more
> about it
> > but I can't find where i read it orignaly.
> >
>
> You might be thinking of Bayesian networks or something related to them.
> I have heard of things like the Helmholtz Machine but I don't know
> anything about this "machine".
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
Subject: Re: Blowfish constants
From: lordcow77 <[EMAIL PROTECTED]>
Date: Sun, 09 Apr 2000 14:52:49 -0700
In article <[EMAIL PROTECTED]>, Tom St Denis
<[EMAIL PROTECTED]> wrote:
>Do the constants in blowfish [for the sbox/pbox] have to be
pi? Can
>they just be sum(0, 1024, C) where 'C' is some odd constant?
That would
>space some space in the library...
>
Why do you insist on inventing your own notation for some very
simple concepts? "sum(0, 1024, C)" has absolutely no standard
meaning at all. It's possible to guess from context that you
mean incrementing each successive S-box entry by some constant,
but why can't you just say that? Similarly, why do you always
refer to the construction of the PRNG described in Knuth's TAOCP
as Alg. M? "Alg. M" means nothing except in context, and if you
provide the context, why can't you just use a more descriptive
name? Taking the "dot product" of two numbers, as you suggested
in a previous posting, also has no well-defined, standard
mathematical meaning; taking the dot product of two numbers
interpreted as bit vectors makes more sense, but again, why
don't you just say what you mean instead of saying what you
think other people say when they mean what you mean?
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 9 Apr 2000 14:25:45 -0700
In article <8cqqbl$[EMAIL PROTECTED]>,
Guy Macon <[EMAIL PROTECTED]> wrote:
> What I suggested was to add a random number of random characters at the
> beginning and end of the plaintext before encrypting it.
In the context of GSM, this requires you to add to the frame length, no?
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: GSM A5/1 Encryption
Date: 9 Apr 2000 14:28:50 -0700
In article <8cqqbl$[EMAIL PROTECTED]>,
Guy Macon <[EMAIL PROTECTED]> wrote:
> If using a strong cipher is cheap and easy, why is there an entire
> newsgroup dedicated to discussing which one to use and tricks and traps
> involved in doing so? Encryption seems easy when you use someone else's
> work (which is the only sane thing to do if your goal is to protect
> your information), but try rolling your own without an education in the
> subject (as I am doing to meet my quite different goal of educating myself
> about the subject) and then tell me how easy it is.
You answered your own question.
The solution is to use someone else's work!
In research, you try to advance the state of the art, and that's not easy.
However, in a production system, you avoid the bleeding edge, and stick with
the "tried and true" strong ciphers. That part _can_ legitimately be easy.
In the world of crypto, there are plenty of "tried and true" strong ciphers
(strong enough for the context of GSM that there was no need to go with an
"on the edge" cipher like 64- or 54-bit A5/1).
------------------------------
Date: Sun, 09 Apr 2000 22:23:10 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Security model for blinded-key recipient-hiding encryption
=====BEGIN PGP SIGNED MESSAGE=====
Here's an attempt at a formal security model for blinded-key
recipient-hiding encryption schemes (borrowing heavily from the models
used in Bellare and Rogaway's papers, e.g. [DHAES] and [CONCRETE]).
PK is the set of public keys (blinded or not).
SK is the set of private keys.
PT is the set of possible plaintexts.
CT is the set of possible ciphertexts.
Coins is the set of possible random inputs, used to model
non-deterministic functions. Coins arguments are omitted when
that does not cause ambiguity.
A blinded-key asymmetric encryption scheme ASYM is modelled by a tuple
(ASYM.encrypt, ASYM.decrypt, ASYM.keygen, ASYM.blind, ASYM.TIMES):
ASYM.encrypt : PK x PT x Coins -> CT
ASYM.decrypt : SK x CT -> PT union {INVALID}
ASYM.keygen : Coins -> SK x PK
ASYM.blind : PK x Coins -> PK
ASYM.TIMES : a set (normally a range) of non-negative integers
Iff n is in ASYM.TIMES, then it is valid for a public key generated
by ASYM.keygen to be blinded (using ASYM.blind) n times, and the
resulting public key used for encryption.
[For example, if a scheme EXAMPLE allows keys to be blinded any number
of times, but an initial public key generated by EXAMPLE.keygen cannot
be used for encryption, then EXAMPLE.TIMES will be the set of all
integers >= 1.]
Correctness.
ASYM is correct if it can accurately decrypt any ciphertext that could
be produced by encryption using a public key that has been blinded a
number of times n, for all n in ASYM.TIMES:
forall (sk, pk_0) <- ASYM.keygen,
forall n <- ASYM.TIMES,
forall { pk_i <- ASYM.blind(pk_{i-1}): i = 1..n }
forall P <- PT,
(ASYM.decrypt(sk, ASYM.encrypt(pk_n, P)) = P)
(This is also implicitly quantified over all the possible random choices
for the Coins arguments.)
Message Privacy under Chosen-Plaintext Attack.
The advantage of an adversary A in attacking ASYM under chosen plaintext
attack is defined as
Adv_CPA(A, ASYM) = max {2.Pr[(sk, pk_0) <- ASYM.keygen;
pk_i <- ASYM.blind(pk_{i-1}), for i = 1..n;
(P_0, P_1, state) <- A.find(pk_<0..n>);
b <- {0, 1};
C <- ASYM.encrypt(pk_n, P_b);
A.guess(pk_<0..n>, state, C) = b] - 1
: n <- ASYM.TIMES}
Explanation
This definition is based on definition 6 from [DHAES] (but with slightly
different notation).
The advantage of the attacker A is calculated based on the following
experiment:
- generate a key pair (sk, pk_0).
- blind the public key pk_0 n times, to create a chain of n+1 keys,
pk_<0..n>.
- call the attacker's function "A.find(pk_<0..n>)", which chooses
two plaintexts (P_0 and P_1) that it will try to distinguish between.
The find function also returns a state for later use by the attacker.
- choose one of the plaintexts, P_b, according to a fair coin toss
(i.e. b = 0 or 1).
- encrypt P_b using pk_n to give C.
- call the attacker's function "A.guess(pk_<0..n>, state, y)", which
tries to guess which plaintext was encrypted.
The "advantage" of the attacker is dependent on the probability of it
succeeding in its guess (taken over the random choices in key generation,
blinding, and encryption). Since the attacker can achieve a success
probability of 1/2 by random guessing, the probability is scaled by
multiplying by 2 and subtracting 1, to give an advantage ranging from 0
(maximum security) to 1 (maximum insecurity). Adv_CPA(A, ASYM) is defined
as the maximum advantage of A against ASYM in a chosen plaintext attack,
over all possibilities for n (the number of blinded keys in the chain),
i.e. all values of n from the set ASYM.TIMES.
Note that it is important for the attacker to be given the whole chain
of blinded public keys, rather than just the one that is being used for
encryption. As a somewhat artificial, but concrete example to motivate
this, consider modifying a proven-secure blinded-key encryption scheme
as follows:
- add to the public key of a generated key pair, a random DHAES public
key (g, y) (for which the private key is not known).
- add to ciphertexts produced by the scheme, the encryption of the
plaintext using DHAES with public key (g, y).
- when a key is blinded, set y := g^y.
This is insecure if the attacker is given the "previous" public key in
the chain (and therefore insecure in practice), but can be "proven
secure" in a model where the attacker is only given the public key
used for encryption - so such a model would obviously be inadequate.
As in [DHAES], the security of ASYM against chosen plaintext attack is
defined by the function
InSec_CPA(ASYM, t, m) = max_A {Adv_CPA(A, ASYM)}
where the maximum is taken over all adversaries A running in time +
code size at most t, and whose outputs P_0 and P_1 have length at most
m bits.
Message Privacy under Non-Adaptive Chosen-Ciphertext Attack.
The advantage of an adversary A in attacking ASYM under non-adaptive
chosen ciphertext attack is defined as
Adv_CCA1(A, ASYM) = max {2.Pr[(sk, pk_0) <- ASYM.keygen;
pk_i <- ASYM.blind(pk_{i-1}), for i = 1..n;
(P_0, P_1, state) <-
A.find(ASYM.decrypt_sk, pk_<0..n>);
b <- {0, 1};
C <- ASYM.encrypt(pk_n, P_b);
A.guess(pk_<0..n>, state, C) = b] - 1
: n <- ASYM.TIMES}
The security of ASYM against non-adaptive chosen ciphertext attack is
defined as
InSec_CCA1(ASYM, t, q, mu, m) = max_A {Adv_CCA1(A, ASYM)}
where the maximum is taken over all adversaries A running in time + code
size at most t, making at most q queries to its decryption oracle, these
queries totaling at most mu bits, and whose outputs x_0 and x_1 have length
at most m bits.
The only difference from the chosen-plaintext-only case is that the attacker
is given a decryption oracle (ASYM.decrypt_sk) in the find stage. This is
based on definition 7 from [DHAES], adapted for blinded keys.
Message Privacy under Adaptive Chosen-Ciphertext Attack.
The advantage of an adversary A in attacking ASYM under adaptive chosen
ciphertext attack is defined as
Adv_CCA2(A, ASYM) = max {2.Pr[(sk, pk_0) <- ASYM.keygen;
pk_i <- ASYM.blind(pk_{i-1}), for i = 1..n;
(P_0, P_1, state) <- A.find(pk_<0..n>);
b <- {0, 1};
C <- ASYM.encrypt(pk_n, P_b);
A.guess(pk_<0..n>, state, C) = b] - 1
: n <- ASYM.TIMES}
The security of ASYM against adaptive chosen ciphertext attack is
InSec_CCA2(ASYM, t, q, mu, m) = max_A {Adv_CCA2(A, ASYM)}
where the maximum is taken over all adversaries A running in time + code
size at most t, making at most q queries to its decryption oracle, these
queries totaling at most mu bits, and whose outputs P_0 and P_1 have length
at most m bits.
Again, this is a straightforward adaption from definition 8 of [DHAES].
Now we define new security properties for blinded-key encryption and
recipient hiding (based on the same approach to modelling security):
Security of public key blinding.
Informally, an attacker is able to break the security of the blinding
function if it can determine with non-negligable probability whether
two given keys are blinded versions of the same public key (or
equivalently, that they correspond to the same private key).
Note that giving the hypothetical attacker the blinded public keys
directly results in a stronger security property than giving the attacker
only ciphertexts, because given the public keys, the attacks can generate
its own ciphertexts corresponding to arbitrary chosen plaintexts.
However, we must be careful to account for all possibilities in the
relationship between the public keys involved. In the diagram below,
X and Y are the public keys of two newly generated key pairs, A and B
are keys obtained by blinding X and Y some number of times, and Z is
a blinded version of *either* A or B. Loosely speaking, the attacker's
advantage is based on the probability of it being able to guess which
key Z was blinded from.
A
X o --->o --->o -------->-
\
?-->o Z
B /
Y o --->o --->o --->o -->-
Only one possible case is shown in the diagram; it is also possible
for Z to be one of the original keys X or Y, if keys generated by
ASYM.keygen can be used directly for encryption (i.e. when 0 is an
element of ASYM.TIMES). In general, all valid combinations for the
number of steps between X and Z, and between Y and Z must be
considered; the overall advantage of the attacker is the maximum
advantage for any of these combinations.
More precisely, for each combination, the attacker's advantage is
calculated based on the following experiment:
- generate two key pairs (skX, pkX_0) and (skY, pkY_0).
- blind pkX_0 and pkY_0, nX and nY times respectively, to give two
chains of keys pkx_<0..nX> and pky_<0..nY>.
- let pkZ be either pkX_nX or pkY_nY, according to a fair coin
toss.
- call the attacker's function
"A.guess(pkX_<0..nX-1>, pkY_<0..nY-1>, pkZ)", which tries to
guess which chain of keys pkZ belongs to.
(Note that nX or nY can be zero; in that case pkX_<0..-1> and
pkY_<0..-1> are of zero length.)
Note that unlike the definitions for message privacy, there is no
"find" stage. The reason why a "find" stage is needed for those
definitions is that there could be a subset of messages for which
a scheme is insecure, but which are a negligable proportion of all
possible messages. This should count as a security weakness, and
therefore it's necessary to allow the attacker to choose the messages
that it will try to distinguish. In constrast, key pair generation
and blinding do not require any non-random input, so there is no
input that could be influenced by an attacker (assuming that the
RNG is secure). "Weak keys" may be possible, but they are only a
security weakness if they occur with non-negligable probability,
and so it's sufficient to randomly choose the chains of keys that
are to be distinguished in the experiment.
[In all of these security definitions, random number generators are
not modelled explicitly, and are assumed to produce output that is
indistinguishable by an attacker from a uniformly random independent
distribution. Modelling them explicitly probably wouldn't help
much: we already know that the RNG has to be secure, and it would
complicate the definitions considerably.]
For this security property the attacker is not given a decryption oracle
(i.e. cannot perform chosen ciphertext attacks). If a decryption oracle
were allowed, then it would not be possible to prove the security of
public key blinding for any scheme, because that would enable asking the
owner of one of the private keys whether a message can be validly
decrypted - which would immediately give away whether the public key used
for encryption corresponds to that private key. I.e. this type of attack
must be prevented at the protocol level, rather than by the encryption
scheme. This should not be too much of a problem for protocols that
are specifically designed to support anonymity.
[It is still useful for chosen ciphertext attacks to be considered for
message privacy, since that protects the confidentiality of messages
even when the anonymity of a recipient has been broken, or the mechanism
for preventing chosen ciphertext attacks at the protocol level fails
(i.e. it provides defense in depth).]
The advantage of an adversary A in attacking the public key blinding
of ASYM is therefore defined as
Adv_Blind(A, ASYM) = max {2.Pr[(skX, pkX_0) <- ASYM.keygen;
(skY, pkY_0) <- ASYM.keygen;
pkX_i <- ASYM.blind(pkX_{i-1}),
for i = 1..nX;
pkY_i <- ASYM.blind(pkY_{i-1}),
for i = 1..nY;
b <- {0, 1};
pkZ <- { pkX_nX, if b = 0
{ pkY_nY, if b = 1
A.guess(pkX_<0..nX-1>, pkY_<0..nY-1>, pkZ)
= b] - 1
: nX <- ASYM.TIMES, nY <- ASYM.TIMES}
The security of ASYM for public key blinding is
InSec_Blind(ASYM, t) = max_A {Adv_Blind(A, ASYM)}
where the maximum is taken over all adversaries A running in time + code
size at most t.
Recipient hiding under Chosen Plaintext and Adaptive Chosen
Ciphertext Attack.
A blinded-key encryption scheme is recipient-hiding, if given two
blinded key chains, at the ends of which are two keys pkX and pkY,
and oracles that encrypt chosen plaintexts or decrypt chosen ciphertexts
with either pkX or pkY (always the same one), it is not possible to
guess which key is being used for encryption, with probability
significantly higher than 1/2.
The security definition for this property has two differences from that
for key blinding:
- the attacker is given oracles that encrypt and decrypt with the
randomly selected key, rather than the key itself.
- the blinded key chains include both of the end keys (pkX and pkY).
We use the following experiment:
- generate two key pairs (skX, pkX_0) and (skY, pkY_0).
- blind pkX_0 and pkY_0, nX and nY times respectively, to give two
chains of keys pkx_<0..nX> and pky_<0..nY>.
- let (skZ, pkZ) be either (skX, pkX_nX) or (skY, pkY_nY), according to a
fair coin toss.
- call the attacker's function
"A.guess(pkX_<0..nX>, pkY_<0..nY>, ASYM.encrypt_pkZ,
ASYM.decrypt_skZ)", which tries to guess which chain of keys
pkZ belongs to (by use of the oracles, rather than by knowing
pkZ directly).
The advantage of an adversary A in attacking the recipient-hiding
property of ASYM is defined as
Adv_Hide(A, ASYM) = max {2.Pr[(skX, pkX_0) <- ASYM.keygen;
(skY, pkY_0) <- ASYM.keygen;
pkX_i <- ASYM.blind(pkX_{i-1}), for i = 1..nX;
pkY_i <- ASYM.blind(pkY_{i-1}), for i = 1..nY;
b <- {0, 1};
(skZ, pkZ) <- { (skX, pkX_nX), if b = 0
{ (skY, pkY_nY), if b = 1
A.guess(pkX_<0..nX>, pkY_<0..nY>,
ASYM.encrypt_pkZ, ASYM.decrypt_skZ)
= b] - 1
: nX <- ASYM.TIMES, nY <- ASYM.TIMES}
The insecurity level of ASYM for recipient hiding is
InSec_Hide(ASYM, t, q, mu) = max_A {Adv_Hide(A, ASYM)}
where the maximum is taken over all adversaries A running in time + code
size at most t, making at most q queries in total to its encryption and
decryption oracles, these queries totaling at most mu bits.
An encryption scheme need not be blind to be recipient hiding, and
the recipient hiding property can be useful on its own. Here are
the corresponding definitions for a non-blind encryption scheme,
modelled as a tuple (ASYM.keygen, ASYM.encrypt, ASYM.decrypt) in
the obvious way:
Adv_Hide'(A, ASYM) = 2.Pr[(skX, pkX_0) <- ASYM.keygen;
(skY, pkY_0) <- ASYM.keygen;
b <- {0, 1};
(skZ, pkZ) <- { (skX, pkX_nX), if b = 0
{ (skY, pkY_nY), if b = 1
A.guess(pkX, pkY, ASYM.encrypt_pkZ,
ASYM.decrypt_skZ) = b] - 1
InSec_Hide'(ASYM, t, q, mu) = max_A {Adv_Hide'(A, ASYM)}
Blinded-key indistinguishability under Chosen-Plaintext Attack.
Two blinded keys corresponding to the same private key are
indistinguishable, if even the private key holder cannot tell which
key was used to produce a collection of ciphertexts.
The advantage of an adversary A in attacking the blinded-key
indistinguishability of ASYM, under adaptive chosen plaintext attack is
Adv_Indist(A, ASYM) = max {2.Pr[(skZ, pkX_0) <- ASYM.keygen;
pkX_i <- ASYM.blind(pkX_{i-1}),
for i = 1..nX;
pkY_i <- { pkX_i, for i = 0..n;
{ ASYM.blind(pkY_{i-1}),
for i = n+1..nY;
b <- {0, 1};
pkZ <- { pkX_nX, if b = 0
{ pkY_nY, if b = 1
A.guess(pkX_<0..nX>, pkY_<0..nY>,
ASYM.encrypt_pkZ, skZ) = b] - 1
: nX <- ASYM.TIMES, nY <- ASYM.TIMES, n <- {0..nX}}
The insecurity level of ASYM for blinded-key indistinguishability under
adaptive chosen plaintext attack is
InSec_Indist(ASYM, t, q, mu) = max_A {Adv_Indist(A, ASYM)}
where the maximum is taken over all adversaries A running in time + code
size at most t, making at most q queries to its encryption oracle, these
queries totaling at most mu bits.
References:
[DHAES] Michel Abdalla, Mihir Bellare, Phillip Rogaway,
"DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem,"
Contribution to IEEE P1363a.
http://grouper.ieee.org/groups/1363/contributions/dhaes.pdf
(temporary URL), or
Theory of Cryptography Library.
http://philby.ucsd.edu/cryptolib/1999/99-07.html
[CONCRETE] M. Bellare, A. Desai, E. Jokipii and P. Rogaway,
"A concrete security treatment of symmetric encryption: Analysis
of the DES modes of operation."
Preliminary version in Proceedings of the 38th Symposium on
Foundations of Computer Science, IEEE, 1997.
Current version at
http://www-cse.ucsd.edu/users/mihir/papers/sym-enc.html
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOPD0pTkCAxeYt5gVAQFLWwf/budX9tcCBR9MF9oNBgenK125ESzX2wAg
Z0ylmfP4z4sMOlioI/nv7GdxdEXnBxyly6EdH1GZ95py+lDJYCddIo5geTpkArvV
4YvZx35290rB3ik3Cn1LI1sUDCshBcjKMRZp5JzfTWufb16VrS7jNrEBruGvxv3f
luT7t4DgW55r57tlv7AbHX8T3Xj4VtY4qKrI+C5H4j+XeCmVNSv2P9pPyXenotP8
O44F1KyKgzXfZLhlsOLsUoPGDQV6hJw520T3KkgRNzu0FMEhEIECrQCb46fQPfZ5
+OJugh76N0yETsEp3D40ed0Ura+/ZJyBgYjko3VRsRVHW+loUkclow==
=aTyy
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Xcott Craver)
Subject: Re: Q: Entropy
Date: 9 Apr 2000 22:21:59 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>I don't understand. There are only two possible answers. I just
>look at the 'answering device' as a black box and want to know
>how many bits come out of it.
Hi,
Think of it this way: suppose I have a black box that
outputs a 1 or a 0. Two possible answers. But, the
internals of the box are broken, so that it always outputs 0.
How many bits of information does this box output? Each
time, physically, electrically, it outputs a physical bit,
but you get zero information. It doesn't actually output
two possible values, because one value is impossible, and
you can always predict the output with 100% accuracy.
And, if you can always predict it, then it isn't providing
any information!
One other justification: if the bits coming out of the
box are not equally probable, then there exists a lossless
compression algorithm which can squeeze that string of bits into
a smaller string of bits. The "information content" turns
out to be the number of bits you can compress the output down to,
an intuitive answer: if you can squeeze 100MB down to 10MB,
losslessly, then it really was only 10MB of "information"
redundantly masquerading as 100MB of "data."
So, the entropy of a source is dependent upon its distribution,
because it's dependent upon the predictability of it's output.
For Shannon entropy, we have H(X) representing a sort of average
unpredictability. Imagine a "shock value" function Shock(x),
which represents the degree to which we're surprised when x
occurs---a newsworthiness function of an event x. This is,
naturally, a function of its probability.
There are a number of reasonable ways you can define Shock(x);
one way that works really well is this: Shock(x) = log( 1/prob(x) ).
I.e., the number of digits needed to write down the odds of x
occuring. Wasted ink! The Shannon Entropy of a random variable is
the expected value of Shock(x): H(X) = [sum] prob(x) log(1/prob(x)).
If X is a coin flip, and x can be HEADS or TAILS each with
probability 1/2, and you do your logs base 2, H(X) = 1 bit. Makes
sense. If X is the output of an 8-sided die, each face equally
probable, H(X) = 3 bits. Makes sense. If the coin toss is biased,
H(X) comes out less than 1 bit.
I suggest you pick up a book like Cover and Thomas's _Elements
of Information Theory._ It's a very accessible book, and
provides a wide-sweeping view of the subject.
>M. K. Shen
-Scott
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
