Cryptography-Digest Digest #582, Volume #14 Sun, 10 Jun 01 19:13:01 EDT
Contents:
Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY ("John A.
Malley")
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Best, Strongest Algorithm (gone from any reasonable topic) - VERY
Date: Sun, 10 Jun 2001 16:01:26 -0700
Mok-Kong Shen wrote:
>
>
> 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 thought I did with the quote on infinite symbol streams out of a
Markov source. Shannon divides his exposition on perfect secrecy into
two parts - one part dealing with a finite set of messages and the other
part dealing with a message source with an infinite number of messages.
See Part II Theoretical Secrecy, Sections 9, 10 of Shannon's paper for
more.
The paper is on-line, in pages scanned and posted as PDF files, at
http://www3.edgenet.net/dcowley/docs.html
(Thank you, Mad Cow.)
>
> > >
> > > 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.
Just a comment - the messages in a finite set do NOT need to be of the
same length for the cipher to achieve perfect secrecy. Shannon
considered the uncertainty of the set of messages regardless of their
lengths but each message is finite. However, he was clear that the
messages in the set were not infinite in length. They are all finite.
[...]
> >
> > 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.)
The length of the messages matters only in the sense of comparing
perfect secrecy for a finite set of messages verses perfect secrecy for
an infinite number of messages from a message source modeled as a
suitable Markov process.
The remainder of this post describes
1) perfect secrecy for a finite set of messages and considers their bit
lengths,
2) perfect secrecy for an infinite number of messages from a source
modeled as a suitable Markov process and considers their bit lengths,
3) why it's possible to implement a cipher with perfect secrecy that
XORs a binary key string with a binary message string, BUT, XORing a
binary string uniformly at random with a binary message string of the
same length does *NOT* always result in a cipher with perfect secrecy!!!
Very interesting explanation, too. Builds on 1) and 2).
1) PERFECT SECRECY FOR A FINITE SET OF MESSAGES
Let a finite set {m1, m2, m3, m4} = M, the set of messages. P(m_i) is
the probability of occurrence of the ith message. The sum of P(m_i) over
i = 1 to |M| is 1. For example, let P(m1) = 1/2, P(m2) = 1/4, P(m3) =
1/8 and P(m4) = 1/8. The uncertainty of the message source M is given by
- [ P(m1)*log(P(m1)) + P(m2)*log(P(m2)) + P(m3)*log(P(m3)) +
P(m4)*log(P(m4))] =
- [ 1/2 * -1 + 1/4 * -2 + 1/8 * -3 + 1/8 * -3 ] = 1.75 bits.
A cipher with perfect secrecy for the finite set M requires as many
cryptograms as messages. Let the finite set {c1, c2, c3, c4} = E, the
set of cryptograms.
A cipher with perfect secrecy for the finite set M requires a finite set
of keys K with uncertainty equal to or greater than the uncertainty of M
and with the keys equiprobable. The uncertainty of K must equal or
exceed 1.75 bits. Let the uncertainty of K = 2 bits. Then let {k1, k2,
k3, k4} = K with each key value equally probable, so P(k1) = P(k2) =
P(k3) = P(k4) = 1/4.
For perfect secrecy, each key selects a map taking each m_i to a
distinct c_j for each k_l value. So in this example:
k1 selects this mapping:
m1 <-> c1
m2 <-> c2
m3 <-> c3
m4 <-> c4
k2 selects this mapping:
m1 <-> c2
m2 <-> c3
m3 <-> c4
m4 <-> c1
k3 selects this mapping:
m1 <-> c3
m2 <-> c4
m3 <-> c1
m4 <-> c2
k4 selects this mapping:
m1 <-> c4
m2 <-> c1
m3 <-> c2
m4 <-> c3
Alice and Bob agree on the set of keys K, the P(k_l), the set of
messages M, the P(m_i), the set of cryptograms E, the P(c_j) and the 4
mappings relating m_i to c_j. This is their shared cipher system. Alice
and Bob agree to use a particular key k_i selected uniformly at random
out of K and keep that key value secret.
Eve also knows the set of keys K, the P(k_l), the set of messages M, the
P(m_i), the set of cryptograms E, the P(c_j) and the 4 mappings relating
m_i to c_j. Eve doesn't know the secret key k_i shared by Alice and
Bob.
This cipher for this finite set of messages M has perfect secrecy iff
the cryptogram intercepted by Eve tells her nothing more about which
message m_i was sent than what she already knew - the a priori
probabilities of any m_i being sent (the P(m_i)). Perfect secrecy
requires
P( m_i | c_j ) = [ P(m_i) * P( c_j | m_i )] / P(c_j) = P(m_i).
The cipher above for M does have perfect secret. Here's an example:
P( m1 | c2 ) = [ P(m1) * P( c2 | m1 )] / P(c2);
P(m1) = 1/2.
P(c2 | m1 ) is the probability of mapping m1 to c2. That's the same as
choosing the mapping given by k2. So P(c2 | m1) = P(k2) = 1/4.
P(c2) is the probability of seeing c2 for any cause/reason. So if the
key is k1, m2 yields c2. For k2, m1 yields c2. For k3, m4 yields c2 and
for k4, m3 yields c2.
P(c2) = P(k1)*P(m2) + P(k2)*P(m1) + P(k3)*P(m4) + P(k4)*P(m3)
P(c2) = 1/4 * 1/4 + 1/4 * 1/2 + 1/4 * 1/8 + 1/4 * 1/8
P(c2) = 1/4 * ( 1/4 + 1/2 + 1/8 + 1/8)
P(c2) = 1/4 * (1)
P(c2) = 1/4.
So,
P( m1 | c2 ) = [ 1/2 * 1/4 ] / 1/4 = 1/2 = P(m1).
There is perfect secrecy [try any other m_i, c_j and see it works for
that pair as well :-) ]
Now here's an important point: at no time did I stipulate the string
lengths of the elements of M, K or E.
Any strings of any length can play the role of the elements of M, K or E
AS LONG AS those strings have the required uncertainty stipulated for
the example.
So as long as the P(m1) = 1/2, P(m2) = 1/4, P(m3) = 1/8 and P(m4) = 1/8
then any mix of finite length strings works.
As long as the P(k1) = P(k2) = P(k3) = P(k4) = 1/4 then any mix of
finite length strings for the keys works.
Any four unique strings for E works.
It can be a waste of bandwidth to use very long strings for E but one
can do so. What counts in perfect secrecy for a finite set of messages
is the uncertainty of M, K, not the exact lengths of the strings m_i
and k_l.
For example, let the sets M and K and E be
m1 = 0 P(m1) = 1/2
m2 = 10 P(m2) = 1/4
m3 = 110 P(m3) = 1/8
m4 = 111 P(m4) = 1/8
k1 = 00 P(k1) = 1/4
k2 = 01 P(k2) = 1/4
k3 = 10 P(k3) = 1/4
k4 = 11 P(k4) = 1/4
c1 = 0
c2 = 10
c3 = 110
c4 = 111
The cipher will have perfect secrecy. In fact, when Eve intercepts c_j
she can't say what the length of the actually message m_i was, all she
knows is that the
P( m_i is 3 bits long) = 1/4,
P( m_i is 2 bits long) = 1/4,
P( m_i is 1 bit long ) = 1/2,
and she already knew this a priori.
Another example, let the sets M and K and E be
m1 = 0 P(m1) = 1/2
m2 = 10 P(m2) = 1/4
m3 = 110 P(m3) = 1/8
m4 = 111 P(m4) = 1/8
k1 = 00 P(k1) = 1/4
k2 = 01 P(k2) = 1/4
k3 = 10 P(k3) = 1/4
k4 = 11 P(k4) = 1/4
c1 = 00
c2 = 01
c3 = 10
c4 = 11
Again, the cipher will have perfect secrecy. When Eve intercepts c_j she
can't say what the length of the actually message m_i was, all she knows
is that the
P( m_i is 3 bits long) = 1/4,
P( m_i is 2 bits long) = 1/4,
P( m_i is 1 bit long ) = 1/2,
and she already knew this a priori.
Another example, let the sets M and K and E be
m1 = 0 P(m1) = 1/2
m2 = 101 P(m2) = 1/4
m3 = 110101 P(m3) = 1/8
m4 = 111100001 P(m4) = 1/8
k1 = 00 P(k1) = 1/4
k2 = 01 P(k2) = 1/4
k3 = 10 P(k3) = 1/4
k4 = 11 P(k4) = 1/4
c1 = 00
c2 = 01
c3 = 10
c4 = 11
Again, the cipher will have perfect secrecy. When Eve intercepts c_j she
can't say what the length of the actually message m_i was, all she knows
is that the
P( m_i is 9 bits long) = 1/8,
P( m_i is 6 bits long) = 1/8,
P( m_i is 3 bits long) = 1/4,
P( m_i is 1 bit long ) = 1/2,
and she already knew this a priori.
2) PERFECT SECRECY FOR AN INFINITE NUMBER OF MESSAGES FROM A SOURCE
MODELED AS A SUITABLE MARKOV PROCESS
Assume a stream of message is generated by a suitable Markov process. No
finite key will give perfect secrecy. Suppose
the key source generates key in the same manner, that is, as an infinite
sequence of symbols. Alice and Bob exchange a length L_m of message at
a time. That is, the next L_m = a symbols out of the Markov process
form a message Alice sends to Bob. And then the next L_m = b symbols
out of the Markov process form a message from Alice to Bob. And then
the next L_m = c symbols out of the Markov process form a message from
Alice to Bob. And so on.
A length of key L_k is needed to encipher and decipher the length of
message L_m, and Alice and Bob need to share the length of key L_k. So
when Alice sends the next L_m = a symbols out of the Markov process she
needs to encipher it with the next L_k = d symbols out of the key source
and get this key string to Bob. When Alice sends the next L_m = b
symbols out of the Markov process to Bob she needs to encipher it with
the next L_k = e symbols out of the key source and get this key string
to Bob. And so on.
Alice and Bob need to exchange a length of key L_k which was used to
encrypt the length of message L_m. Alice must get the length of key L_k
to Bob secretly, so Bob and decrypt the length of message L_m with it.
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], perfect secrecy for this message
source requires
R_m * L_m <= R_k * L_k.
When L_k = L_m so the key string is as long as the message string in
units of symbols. Perfect secrecy then requires the log of the number of
key alphabet symbols equal or exceed the log of the number of message
alphabet symbols.
Let M be a message source generating two messages m1 and m2 as the
outputs of a Markov process, where the P(m1) = 1/2, P(m2) = 1/2, and
there is no dependency of the current message output on any past or
future message output from M. The values M(i) can take on are Mvalues =
{m1, m2}.
Alice generates a n message long sequence of outputs from M, M(i) for i
= 1 to n. She enciphers and sends this sequence to Bob. And then Alice
generates another j message long sequence of outputs from M, M(i) for i
= 1 to j, and enciphers sends this string to Bob. And so on.
The probability of any particular n message long sequence, where the
sequence is a mixture of occurrences of m1 and m2, is
P( particular message sequence ) = (1/2)^n
Let L_m = L_k. Perfect secrecy requires the log of the number of
elements in the key alphabet, or the number of distinct keys, must be
equal to or greater than the log of the number of possible values M(i)
can take on. M(i) can take on only two values, m1 and m2, so the number
of possible values the key could take on must be at a minimum of two, k1
and k2.
Let K be a key source generating two key values k1 and k2 as the outputs
of a Markov process, where the P(k1) = 1/2, P(k2) = 1/2, and there is no
dependency of the current key value output on any past or future key
value output from K. The values K(i) can take on are Kvalues = {k1,
k2}.
When Alice generates a n message long sequence of outputs from M, M(i)
for i = 1 to n, she also generates a sequence of n key values from K,
K(i) for i = 1 to n. She and Bob must secretly share this key sequence n
values long. Alice uses the key sequence to encrypt the message sequence
from M into a ciphertext sequence and Bob uses the key sequence to
decrypt the resulting ciphertext sequence back to the message sequence
from M.
The probability of any particular n key value long sequence, where the
sequence is a mixture of occurrences of k1 and k2, is
P( particular key value sequence ) = (1/2)^n
A cipher with perfect secrecy for a finite set of messages requires as
many cryptograms as messages. Similarly, let E be the set of cryptograms
to which the set of outputs from M(i) map to when enciphered. Let the
number of distinct cryptograms equal the number of distinct values M(i)
can take on. So E = { c1, c2 }.
For an n message sequence, i = 1 to n, Alice enciphers M(i) using the
key K(i) with these two mappings:
if K(i) = k1
M(i) = m1 <-> c1
M(i) = m2 <-> c2
if K(i) = k2
M(i) = m1 <-> c2
M(i) = m2 <-> c1
Alice and Bob both know the source M, the set of Mvalues = {m1, m2}, the
P(m_i), the source K, the set of Kvalues = { k1, k2}, the P(k_i), the
set of cryptograms E. This is their shared cipher system. Alice and Bob
agree to use a particular sequence of n key values out of K and keep
that key value sequence secret.
Eve also knows the source M, the set of Mvalues = {m1, m2}, the P(m_i),
the source K, the set of Kvalues = { k1, k2}, the P(k_i), the set of
cryptograms E. Eve does not know the particular sequence of n key
values out of K.
Eve intercepts a sequence of cryptograms E(1) through E(n) corresponding
to a message sequence M(1) through M(n).
This cipher has perfect secrecy iff the E(j) value, j = 1 to n, tells
her nothing more about which message m_i corresponds to M(j) than what
she already knew - the a priori probabilities of any m_i being M(j) (the
P(m_i)). Perfect secrecy requires
P( M(j) = m_i | E(j) = c_l ) = [ P( M(j) = m_i) * P( E(j) = c_l | M(j)
= m_i )] / P( M(j) = c_l) = P( M(j) = m_i).
The cipher above for the output of M does have perfect secrecy. Here's
an example:
P( M(j) = m1 | E(j) = c_2 ) = [ P( M(j) = m1) * P( E(j) = c2 | M(j) =
m1 )] / P(E(j) = c2);
P(M(j) = m1) = 1/2.
P(E(j) = c2 | M(j) = m1 ) is the probability of mapping m1 to c2. That's
the same as choosing the mapping given by k2. So P( E(j) = c2 | M(j) =
m1) = P(K(j) = k2) = 1/2.
P(E(j) = c2) is the probability of seeing c2 for any cause/reason. So
if the key is k1, m2 yields c2. For k2, m1 yields c2.
P(E(j) = c2) = P(K(j) = k1)*P(M(j) = m2) + P(K(j) = k2)*P(M(j) = m1)
P(E(j) = c2) = 1/2 * 1/2 + 1/2 * 1/2
P(E(j) = c2) = 1/2 * ( 1/2 + 1/2 )
P(E(j) = c2) = 1/2 * (1)
P(E(j) = c2) = 1/2.
So,
P( M(j) = m1 | E(j) = c_2 ) = [ 1/2 * 1/2 ] / 1/2 = 1/2 = P(M(j) =
m1).
There is perfect secrecy [try any other m_i, c_l and see it works for
that pair as well, and this works across all j. :-) ]
Now here's an important point: at no time did I stipulate the string
lengths of the elements of Mvalue, Kvalue or E.
Any strings of any length can play the role of the elements of Mvalue,
Kvalue or E AS LONG AS those strings have the required probabilities
stipulated for the example.
So as long as the P( M(j) = m1) = 1/2, P(M(j) = m1) = 1/2 then any pair
of finite length strings works.
As long as the P(K(j) = k1) = P(K(j) = k2) = 1/2 then any pair of finite
length strings for the keys works.
Any two unique strings for E works.
Now here are three examples of message sequences out of M enciphered
with perfect secrecy.
================================================
First example, the sets Mvalue and Kvalue and E
m1 = 0 P(M(j) = m1) = 1/2
m2 = 1 P(M(j) = m2) = 1/2
k1 = 0 P(K(j) = k1) = 1/2
k2 = 1 P(K(j) = k2) = 1/2
c1 = 0
c2 = 1
work in the above mappings and provide perfect secrecy. Here's a sample
message sequence, a keys sequence, and resulting ciphertext using the
tables for k1 and k2 above in this post:
message sequence 0 0 1 1 0
key sequence 1 1 0 1 0
ciphertext sequence 1 1 1 0 0
=====================================
Second example, these values for Mvalue, Kvalue and E
m1 = 0 P(M(j) = m1) = 1/2
m2 = 01 P(M(j) = m2) = 1/2
k1 = 0 P(K(j) = k1) = 1/2
k2 = 1 P(K(j) = k2) = 1/2
c1 = 0
c2 = 01
work in the above mappings and provide perfect secrecy. Here's a sample
message sequence, a keys sequence, and resulting ciphertext using the
tables for k1 and k2 above in this post:
message sequence 0 01 01 0 01 0
key sequence 0 1 0 1 1 0
ciphertext sequence 0 0 01 01 0 0
=====================================
Third example, these values for Mvalue, Kvalue and E
m1 = 0 P(M(j) = m1) = 1/2
m2 = 01 P(M(j) = m2) = 1/2
k1 = 010 P(K(j) = k1) = 1/2
k2 = 011 P(K(j) = k2) = 1/2
c1 = 1
c2 = 0
work in the above mappings and provide perfect secrecy. Here's a sample
message sequence, a keys sequence, and resulting ciphertext using the
tables for k1 and k2 above in this post:
message sequence 0 01 01 0 01 0
key sequence 010 010 011 011 010 011
ciphertext sequence 1 0 1 0 0 0
================================================
All three examples fit the definition of a cipher system with perfect
secrecy for infinite messages produced by a suitable Markov process per
Shannon's paper. In all three examples Alice and Bob must share the
secret key sequence shown; Alice sends a ciphertext string to Bob and
Bob can decipher it using the key sequence and the two tables for k1, k2
which constitute the cipher.
In fact, all three examples still attain perfect secrecy when the
message sequence is just a single M(i) output long. (I leave this as an
exercise for the interested reader.)
VERY IMPORTANT POINT: Any cipher providing perfect secrecy when
encrypting a sequence of output from a Markov message source M *must*
also provide perfect secrecy when encrypting a single output from the
Markov message source M.
The cipher consisting of the mappings taking {m_i} to {c_j} where the
particular mapping to use is selected by a key value k_l provides
perfect secrecy for a single m_i.
Alice and Bob can use a mathematical function T_k() instead of a table
of relations between {m_i} and {c_j} selected by k_l IFF the table of
relations can be produced by an algorithm T_k() that takes an element of
{m_i} and a specific key {k_l} and produces a cryptogram out of the set
{c_j}. Any mathematical encryption function c_j = T_k( m_i, k_l) can
be represented by a table of relations between c_j and m_i selected by
the value k_l.
Only *one* of these three examples can actually be implemented using the
XOR operation! It's first of the three, where E(i) = M(i) XOR K(i). This
function implements the cipher tables for k1 and k2 given the binary
string values of {k_l}, {m_i} and {c_j}, or in other words, T_k( M(i),
K(i)) = M(i) XOR K(i).
The other two cipher systems cannot be implemented using the XOR
operation but nonetheless do provide for perfect secrecy.
Which brings us now to section 3) of this post.
3) WHY ENCIPHERING A FINITE SET OF MESSAGES BY XORING RANDOM BINARY
STRINGS AS LONG AS THE MESSAGES DOES *NOT* GUARANTEE PERFECT SECRECY
Let a finite set {m1, m2} = M, the set of messages. P(m_i) is the
probability of occurrence of the ith message. The sum of P(m_i) over i =
1 to |M| is 1. For example, let P(m1) = 1/2, P(m2) = 1/2. The
uncertainty of the message source M is given by
- [ P(m1)*log(P(m1)) + P(m2)*log(P(m2))] =
- [ 1/2 * -1 + 1/2 * -1 ] = 1 bit.
A cipher with perfect secrecy for the finite set M requires as many
cryptograms as messages. Let the finite set {c1, c2} = E, the set of
cryptograms.
A cipher with perfect secrecy for the finite set M requires a finite set
of keys K with uncertainty equal to or greater than the uncertainty of M
and with the keys equiprobable. The uncertainty of K must equal or
exceed 1 bit in this example. Let the uncertainty of K = 1 bit . Then
let {k1, k2 } = K with each key value equally probable, so P(k1) = P(k2)
= 1/2.
For perfect secrecy, each key selects a map taking each m_i to a
distinct c_j for each k_l value. So in this example:
k1 selects this mapping:
m1 <-> c1
m2 <-> c2
k2 selects this mapping:
m1 <-> c2
m2 <-> c1
The cipher above for M does have perfect secrecy (and it can be shown
using the same approach taken in section 1 of this post).
At no time did I stipulate the string lengths of the elements of M, K or
E. Any strings of any length can play the role of the elements of M, K
or E AS LONG AS those strings have the required uncertainty stipulated
for the example.
So as long as P(m1) = 1/2, P(m2) = 1/2 then any distinct pair of finite
length strings works.
As long as P(k1) = P(k2) = 1/2 then any any distinct pair of finite
length strings for the keys works.
Any unique pair of strings for E works.
These sets M, K and E of binary strings
m1 = 0 P( m1) = 1/2
m2 = 1 P( m2) = 1/2
k1 = 0 P( k1) = 1/2
k2 = 1 P( k2) = 1/2
c1 = 0
c2 = 1
work in the above mappings and provide perfect secrecy. Here's a sample
message, a key and resulting ciphertext using the tables for k1 and k2
above:
message 0
key 1
ciphertext 1
message 1
key 0
ciphertext 1
message 0
key 0
ciphertext 0
The application of the tables per the value of k can be done with a
mathematical function c = m XOR k. Just XOR the message binary string
with the key binary string to get the ciphertext binary string.
These sets M, K and E of binary strings
m1 = 00 P( m1) = 1/2
m2 = 11 P( m2) = 1/2
k1 = 00 P( k1) = 1/2
k2 = 11 P( k2) = 1/2
c1 = 00
c2 = 11
work in the above mappings and provide perfect secrecy. Here's a sample
message, a key and resulting ciphertext using the tables for k1 and k2
above:
message 00
key 11
ciphertext 11
message 11
key 00
ciphertext 11
message 00
key 00
ciphertext 00
The application of the tables per the value of k can be done with a
mathematical function c = m XOR k. Just XOR the message binary string
with the key binary string to get the ciphertext binary string.
Now suppose Alice and Bob think they can implement a cipher with perfect
secrecy by always picking uniformly at random a binary string the same
length as the binary string representing m1 or m2 and XORing them
together. But does this actually work? Does it even make sense?
Let the set M be
m1 = 0 P( m1) = 1/2
m2 = 01 P( m2) = 1/2
m1 gets enciphered with 1 or 0, and m2 gets enciphered with 00, 01, 10,
00. The resulting cryptograms are 0, 1, 00, 01, 10 and 11.
And there are 6 values in E = { 0, 1, 00, 01, 10, 11 ).
There are 6 key values in K = { 0, 1, 00, 01, 10, 11 } and each key
should be equiprobable for a cipher with perfect secrecy, so the P(k_i)
= 1/6. When each key is equiprobable the uncertainty of the keys K is
- [ 6 * (1/6 * log(1/6)) ] = - log(1/6). 2 bits < The uncertainty
of K < 3 bits. And this is greater than the uncertainty of the messages
M which is 1 bit.
So far, so good, since perfect secrecy requires the uncertainty of K >=
uncertainty of M.
But actually each key is not equiprobable. The two bit keys are selected
only when the message is two bit long and the 1 bit keys are selected
only when then message is 1 bit long. What about the mappings from M to
E as selected by the different key values? What do they look like?
k = 0 selects this mapping:
m1 = 0 <-> 0
m2 = 01 <-> undefined! There is no mapping from m2 into E when k = 0.
k = 1 selects this mapping:
m1 = 0 <-> 1
m2 = 01 <-> undefined! There is no mapping from m2 into E when k = 1.
k = 00 selects this mapping:
m1 = 0 <-> undefined! There is no mapping from m1 into E when k = 00.
m2 = 01 <-> 01
k = 01 selects this mapping:
m1 = 0 <-> undefined! There is no mapping from m1 into E when k = 01.
m2 = 01 <-> 00
k = 10 selects this mapping:
m1 = 0 <-> undefined! There is no mapping from m1 into E when k = 10.
m2 = 01 <-> 11
k = 11 selects this mapping:
m1 = 0 <-> undefined! There is no mapping from m1 into E when k = 11.
m2 = 01 <-> 10
Wow! There are NO complete mappings taking every element of M to every
element of E for any k value in K. BUT, every key should select a
mapping that takes every element from M into E - this is required for a
cipher on M that gives perfect secrecy.
Because of these mappings Eve would always know that any 2 bit length
cryptogram could only represent m2 and any 1 bit length cryptogram could
only represent m1.
This cipher, picking uniformly at random a binary string the same length
as the binary string representing m1 or m2 and XORing them together,
does NOT have perfect secrecy.
Can we define a cipher for m1 = 0 and m2 = 01 that has perfect secrecy?
Sure, two examples:
These sets M, K and E of binary strings
m1 = 0 P( m1) = 1/2
m2 = 01 P( m2) = 1/2
k1 = 0 P( k1) = 1/2
k2 = 1 P( k2) = 1/2
c1 = 0
c2 = 1
work in the above mappings and provide perfect secrecy. Here's a sample
message, a key and resulting ciphertext using the tables for k1 and k2
above:
message 0
key 1
ciphertext 1
message 01
key 0
ciphertext 1
message 01
key 1
ciphertext 0
but this cipher cannot be implemented with the algorithm ciphertext = m
XOR k.
These sets M, K and E of binary strings
m1 = 0 P( m1) = 1/2
m2 = 01 P( m2) = 1/2
k1 = 0 P( k1) = 1/2
k2 = 1 P( k2) = 1/2
c1 = 0
c2 = 01
work in the above mappings and provide perfect secrecy. Here's a sample
message, a key and resulting ciphertext using the tables for k1 and k2
above:
message 0
key 1
ciphertext 01
message 01
key 0
ciphertext 01
message 01
key 1
ciphertext 0
and this cipher cannot be implemented with the algorithm ciphertext = m
XOR k.
So these examples show it's possible to implement a cipher with perfect
secrecy that XORs a binary key string with a binary message string, BUT,
XORing a binary string uniformly at random with a binary message string
of the same length does *NOT* always result in a cipher with perfect
secrecy.
I took a couple of days to write this up, I hope this helps.
All the results in this posted analysis come either directly from or are
derived from the information in Shannon's paper.
John A. Malley
[EMAIL PROTECTED]
------------------------------
** 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
******************************
