<<

. 25
( 36 .)



>>

Let the source generate potentially unbounded messages m1m2 . . . mt,
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 ˜ ,

<<

. 25
( 36 .)



>>