12.5 Cryptography Fundamentals
209
The conditional probabilities p yx for the channel from Alice to Bob, compared with
(12.8), are consistent with ε = 0, which implies that the mutual information I [x; y]
is unity. Since we have α = 1/2 this implies that the channel capacity C, shown on
the right-hand side in Fig. 12.3, is also unity. On the other hand, the probabilities p zx
for the channel from Alice to Eve, are consistent with ε = 1/2, which indicates that
the channel capacity C is zero and Eve cannot extract information from the stream of
bits that travels on the public channel. We point out that this result depends to some
extent on the chosen key k. We picked one with four bits set and four bits unset. If
we pick a key k with three bits set and five bits unset, ε differs from 1/2.
In the example, we only used an eight-bit key, but we can of course make the key
k much longer, say 256 bits and encode blocks of the same length, one at a time.
Cryptographic systems that work on such fixed-length blocks of data are referred to
as block ciphers, on which many encryption systems, discussed below, are based.
We note that simple cryptographic algorithms have two significant problems.
First, both the sender and the recipient have to know the key k, which makes it
mandatory to send the key over a potentially insecure communication channel. We
might consider to encrypt the transfer, but this requires an earlier transmission of
another key to encode it. We will later address how the key-distribution, which is
how this hen-and-egg problem is commonly called, can be solved. The second
problem of the simple xor-cipher is that we can easily uncover the presumably secret
key by passing a special messages to the encoding function. The trivial example is
that xor(b
0, k) = k, where m = b
0 is a messages comprising of only zeros.
This second problem was initially solved by the Data Encryption Standard (DES),
first introduced in the 1970s. It works on blocks with a length of 64 bits and uses a
key k 0 with an effective length of 56 bits, comprising of eight 7-bit sections. From
this secret key sixteen sub-keys k 0 , . . . , k 15 are derived. The encoding proceeds in
sixteen steps, called rounds, labelled by the index i, in which the message m i at step
i is split in a left and a right part m i = (L i , R i ), each with a length of 32 bits. The
transformation from one round to the next is given by
m i+1 = (L i+1 , R i+1 ) = (R i , xor(L i , F(R i , k i ))) ,
(12.27)
where F(R i , k i ) is a so-called Feistel function. It scrambles the 32 bits in R i with the
sub-key k i using an algorithm that is specific to DES. Finally R i+1 is calculated as
the xor with L i . Note that in each round one half of m i remains unchanged, while the
other half is xor’ed with a key derived from the other half and a sub-key. After sixteen
rounds the original message m 0 has mogrified to the cipher text c = m 16 . It turns out
that the same algorithm can be used to decipher an encrypted cipher text c. All we
have to do is to reverse the order of the sub-keys and pass the cipher text through the
sixteen rounds, where the last round uses sub-key k 0 , to recover the original message
m 0 . Since both encoding and decoding use the same algorithm, DES is considered
efficient. Over the years, however, it was shown that the DES encryption can be
broken within a reasonably short time and its use is no longer recommended. It is
superseeded by other encryption algorithms, for example by Triple-DES, which uses
three 56-bit long keys. It first encrypts using one key, then decrypts with the second
209
The conditional probabilities p yx for the channel from Alice to Bob, compared with
(12.8), are consistent with ε = 0, which implies that the mutual information I [x; y]
is unity. Since we have α = 1/2 this implies that the channel capacity C, shown on
the right-hand side in Fig. 12.3, is also unity. On the other hand, the probabilities p zx
for the channel from Alice to Eve, are consistent with ε = 1/2, which indicates that
the channel capacity C is zero and Eve cannot extract information from the stream of
bits that travels on the public channel. We point out that this result depends to some
extent on the chosen key k. We picked one with four bits set and four bits unset. If
we pick a key k with three bits set and five bits unset, ε differs from 1/2.
In the example, we only used an eight-bit key, but we can of course make the key
k much longer, say 256 bits and encode blocks of the same length, one at a time.
Cryptographic systems that work on such fixed-length blocks of data are referred to
as block ciphers, on which many encryption systems, discussed below, are based.
We note that simple cryptographic algorithms have two significant problems.
First, both the sender and the recipient have to know the key k, which makes it
mandatory to send the key over a potentially insecure communication channel. We
might consider to encrypt the transfer, but this requires an earlier transmission of
another key to encode it. We will later address how the key-distribution, which is
how this hen-and-egg problem is commonly called, can be solved. The second
problem of the simple xor-cipher is that we can easily uncover the presumably secret
key by passing a special messages to the encoding function. The trivial example is
that xor(b
0, k) = k, where m = b
0 is a messages comprising of only zeros.
This second problem was initially solved by the Data Encryption Standard (DES),
first introduced in the 1970s. It works on blocks with a length of 64 bits and uses a
key k 0 with an effective length of 56 bits, comprising of eight 7-bit sections. From
this secret key sixteen sub-keys k 0 , . . . , k 15 are derived. The encoding proceeds in
sixteen steps, called rounds, labelled by the index i, in which the message m i at step
i is split in a left and a right part m i = (L i , R i ), each with a length of 32 bits. The
transformation from one round to the next is given by
m i+1 = (L i+1 , R i+1 ) = (R i , xor(L i , F(R i , k i ))) ,
(12.27)
where F(R i , k i ) is a so-called Feistel function. It scrambles the 32 bits in R i with the
sub-key k i using an algorithm that is specific to DES. Finally R i+1 is calculated as
the xor with L i . Note that in each round one half of m i remains unchanged, while the
other half is xor’ed with a key derived from the other half and a sub-key. After sixteen
rounds the original message m 0 has mogrified to the cipher text c = m 16 . It turns out
that the same algorithm can be used to decipher an encrypted cipher text c. All we
have to do is to reverse the order of the sub-keys and pass the cipher text through the
sixteen rounds, where the last round uses sub-key k 0 , to recover the original message
m 0 . Since both encoding and decoding use the same algorithm, DES is considered
efficient. Over the years, however, it was shown that the DES encryption can be
broken within a reasonably short time and its use is no longer recommended. It is
superseeded by other encryption algorithms, for example by Triple-DES, which uses
three 56-bit long keys. It first encrypts using one key, then decrypts with the second