t -+ 00, and there be a fked-length key k = k l k 2 . . . k,, s 2 1. (As we

mentioned above the per-letter source entropy is assumed to be non-zero

since, otherwise, there is no necessity to transmit anything.) We shall split

the message into blocks of n letters where n > 1 is a parameter of the

method. Denote one of such blocks by m. Describe the transformations

carried out on each n-letter block.

First determine the number of individual letters a1 and a2 in m. Let

there be, say, n1 letters a1 and 712 = n - n1 letters a2. Define u(*) as a

+

word of length [log(n 1)1 bits which encodes n l .

Now consider the set S of all sequences consisted of n1 letters a1 and

n letters a2. There are

2

n!

J

;

(

IS' - nl)!

= = n1!(n

elements in this set. Despite the fact that the probabilities of the sequences

from S are unknown, one thing may be stated - they are equal to each

other (by independence of individual letters). Set a lexicographic order on

S (assuming that a1 < a2) and compute the ordinal number of f i within

Basics of Contemporary Cryptography f o r IT Practitioners

132

S (the efficient algorithm [Ryabko (1998)] can be used for this computa-

tion, but its description goes beyond the scope of the book). Denote the

computed ordinal by w ( m ) .

Split the set S into non-overlapping subsets So, S 1 , . . . , S, with the

numbers of elements equal to the powers of 2 (e.g. if IS1 = 21 then three

subsets may result with cardinalities 16, 4, and 1). Using w ( a ) , determine

to what subset m belongs (denote the ordinal number of such subset by

w(%)) and find the ordinal of f i within this subset (denote this ordinal by

w(fi))*

Look attentively at the ordinal of the message within the subset w ( f i ) .

What is remarkable, the w(m) is a completely random sequence of zeroes

and ones (i.e. all bits are equiprobable and independent). Indeed, w(a)

is the ordinal of one of equiprobable sequences of letters in a set of 2'

elements (for some b). The ordinals of all such sequences are all possible

combinations of b binary digits. But if all combinations of b binary digits are

equiprobable, then the individual bits are equiprobable and independent.

So, by processing consecutive blocks of the message in the described

way we represent the message in the form

Now describe the procedure of encrypting the transformed message.

It may seem strange at first sight, but the words u(-) w(.) are not

and

encrypted at all! Only the words w(.) encrypted under the secret

are

key f . As one of the possibilities, we may use as the cipher the bitwise

sum modulo 2 with periodically continued key. To describe such a cipher

enumerate sequentially the symbols of all words w(.) denote these by

and

˜ 1 ˜ 2 ˜ . 3 . . the encryption is performed according t o the formula

. Then

As a result, we have encrypted the source message by the following way:

By the algorithm's construction, it is clear that the message can be

recovered from the right side of (7.26) if we know the secret key f . First

we need to decrypt the symbols of the words w(.) the formula

by

(7.27)

wi = z @ ki mod s

i

Theoretical Security of Cryptosystems 133

and then from the words u(.)v(.)w(.) the consecutive blocks of the message

can be recovered.

Example 7.6 Let it be required to encrypt the message

under the 3-bit key = 011. Split the message into two blocks of 5 symbols,

n = 5.

Perform the transformation for the first block 6 1 = a2a2a˜a2a2.For

this block, n1 = 1 and u(iii1) = (001)˜. Consider now the ordered set of all

messages consisted of 1 letter a1 and 4 letters a2 (see Table 7.1). There are

3 = 5 such messages, so we have two subsets So and S with the number

l

of elements 4 and 1, respectively.

Table 7.1 The set of equiprobable messages;

n1 = 1, n2 = 4.

S,

Ordinal in S

Message w

We can see that f i 1 enters in So under the ordinal 2 = ( 1 0 ) ˜ .So we

obtain the following two words: v(ml) 0, w(iizl) = (10)˜.

=

Now perform the transformation for the second block of the message.

f i z = a2a1a2a2a1. For this block, n1 = 2 and u(fi2) = (010)˜. Consider

the ordered set of all messages consisted of 2 letters a1 and 3 letters a2 (see

Table 7.2). There are $& = 10 such messages, so we have two subsets SO

and S with the number of elements 8 and 2, respectively.

1

We can see that f i 2 enters in So under the ordinal 6 = (110)2. So we

obtain v(iiz2) = 0, w(jj22) = (110)2.

To that point, we have obtained the following binary code of the trans-

formed message:

001 0 10 010 0 110

(blank spaces here are only for ease of perception; they are not needed for

unique decoding).

Basics of Contemporary Cryptography for IT Practitioners

134

Table 7.2 The set of equiprobable messages;

n1 = 2, n2 = 3.

Ordinal in S S,

Message w

0000 000

a1 a1 azaza2

001

a1 a2a1 a2a2 0001

010

a1 a2azai a2 0010

s

o 011

aia2a2a2ai 0011

100

0100

a2aiaia2a2

0101 101

a2ai a2ai a2

110

a˜aia˜a˜ai 0110

111

a2a2alalaZ 0111

s1

a2a2aia2ai 1000 0

a2a2aZalal 1

1001

Now encrypt the transformed message. The periodically continued key

looks like k = 011011.. . . Bitwise summation modulo 2 of the words w(.)

with that key gives

10110

@01101

11011

The ciphertext looks like this:

e = 001 0 11 010 0 011.

Discuss now the main properties of the described method.

Proposition 7 4 The cipher constructed is strongly ideal.

.

Proof. Without much rigour, the idea of the proof is the following. As

we have already noted in the method description, the word w(m) each for

block consists of equiprobable and independent symbols 0 and 1 (is com-

pletely random, for short). Since the blocks of the message are independent,

the sequence w ( m , ) w ( i i z 2 ) . . . = ˜ 1 2 ˜ 2 ˜. in .the transformed message is

3 .

also completely random. But any sequence W I W ˜ W .˜. corresponds to some

.

message and all such messages are equiprobable. Therefore, under substitu-

tion of any key in deciphering equation (7.27), we obtain some solution, all

the solutions being equiprobable. As a result, having only the ciphertext,

we cannot say anything about the key used, i.e.

Theoretical Security of Cryptosystems 135

Further, each individual message mlm2 . . . mt converts to one and only

one sequence ˜ 1 ˜ 2 ˜. and, . under a sufficiently large t , namely, such

3.

that the length of the sequence 2 ˜ 1 ˜ 2 . . is no less than the key length,

˜3.

each different key, being used in (7.271, will produce different equiprobable

messages. Therefore

H ( r n 1 m 2 . . . mtle) = H ( 2 ) .

Non-zero source entropy guarantees that the required sufficiently large t

always exists.

0

So, we can see that (7.25) holds.

The peculiarity of the described method is that not all transformed

message is encrypted but only a part of it. In the example provided, it may

even seem that too much information remains “open”. What portion of

information is concealed by the cipher? The following proposition answers

this question.

Proposition 7.5 Let the message be generated by a memoryless source

with the entropy h per letter. T h e n for every block rii of n symbols, the

expected length of the encrypted word w(m)satisfies the inequality

+ 1)

E ( l w ( f i ) l )> nh - 2log(n (7.28)

(here E(.) denotes expectation and I . I the length).

Proof. The code component u(m) can take on any value from 0 t o n,

therefore its maximal entropy is log(n + 1).

The word v ( f i ) can take on any value from 0 to v which is related

with splitting the set S into the subsets SO,S1, . . . , S It is obvious that

.

,

Y 5 [log ISl]. From the well-known inequality IS1 = (,”,) < 2n we obtain

log (SI < n and, hence, v 5 log 1 < n. Therefore the maximal entropy of

st

the word w(m) is less than log(n + 1).

The entropy of the block H ( f i ) = nh (since the letters are generated

by a memoryless source). The transformation of the block does not change

the entropy. Therefore for the entropy of the word w ( m ) we have

H ( w ( m ) )> nh - 2 log(n -t1)

(we subtract from the block entropy the upper bounds for the entropies

of u(m) and ˜(6)).s the word w ( 6 ) consists of equiprobable and

But a

independent symbols 0 and 1, its average length equals the entropy which

0

completes the proof.

Basics of Contemporary Cryptography for IT Practitioners

136

Informally, Proposition 7.5 says that “almost all” information of the

message is contained in the encrypted codeword w if the blocklength n is

sufficiently large. In other words, the presented cipher conceals “almost

all” information and even the exhaustive search through the whole set of

keys does not allow to break the cipher.

Problems and Exercises

k:

7.1 Encrypt the message m by the Vernam cipher under the key

k

(a) m = 1001101011, = 011O1OO1O1,

k = 1100011100,

(b) 7tL = 0011101001,

m = 1000011100, L = 1001011010,

(c)

m = 0011100010, k = 0110111001,

(d)

k

(e) f i = 1001101011, = 1000111010.

7.2 Let a memoryless source generate letters over the alphabet A =

{ a , b, c } with probabilities P ( a ) , P(b), P(c). The encrypter substi-

tutes the letters using one of the six possible permutations, as in

Example 7.3. Determine the a posteriori probabilities of keys given

the ciphertext 8:

P ( a ) = 0.1, P(b) = 0.7, P ( c ) = 0.2, E = abaacac,

(a)

P ( u ) = 0.9, P(b) = 0.09, P(c)= 0.01, e = C ˜ U C C C ˜ ,