M A S A R Y K UNIVERSITY
FACULTY OF INFORMATICS
 %\--*/ &
Coding theory, cryptography and
cryptographic protocols - exercises
with solutions
(given in 2006)
BACHELOR THESIS
Zuzana Kuklová
Brno, Spring 2007
Declaration
Hereby I declare, that this paper is my original authorial work, which I have worked out by
my own. All sources, references and literature used or excerpted during elaboration of this
work are properly cited and listed in complete reference to the due source.
Advisor: prof. RNDr. Jozef Gruska, DrSc.
11
Acknowledgement
I would like to thank prof. RNDr. Jozef Gruska, DrSc. and Mgr. Lukáš Boháč for their inspiring
comments which have essentially contributed to fulfilling of the presented work.
I am obliged to my family for understanding and furtherance.
m
Abstract
The main goal of this work is to present detailed solutions of exercises that have been submitted
to students of the course Coding, cryptography and cryptographic protocols, given
by prof. RNDr. Jozef Gruska, DrSc. in 2006 as homeworks. This way a handbook of solved
exercises from coding theory and cryptography is created. Ahead of each set of new exercises
we include main concepts and results from the corresponding lecture that are needed
to solve exercises.
IV
Keywords
Coding theory, code, linear code, cyclic code, cryptography, cryptosystem, cryptoanalysis,
secret key cryptography, public key cryptography, digital signature, subliminal channel, elliptic
curve, factorization, prime recognition, identification, authentication, bit commitment,
zero knowledge proof
v
Contents
Introduction 3
1 Basics of Coding Theory 4
1.1 Definition of Code 4
1.2 Equivalence of Codes 4
1.3 Properties of Code 5
1.4 Entropy 5
1.5 Exercises 6
2 Linear Codes 12
2.1 Definition of Linear Code 12
2.2 Equivalence of Linear Codes 13
2.3 Dual Code 13
2.4 Encoding with Linear Codes 13
2.5 Decoding of Linear Codes 14
2.6 Hamming Code 14
2.7 Properties of Linear Code 15
2.8 Exercises 15
3 Cyclic Codes 22
3.1 Definition of Cyclic Code 22
3.2 Algebraic Characterization of Cyclic Codes 22
3.3 Generator Matrix, Parity Check Matrix and Dual Code 23
3.4 Encoding with Cyclic Codes 24
3.5 Hamming Code 24
3.6 Exercises 24
4 Secret Key Cryptography 30
4.1 Cryptosystem 30
4.2 Cryptoanalysis 30
4.3 Secret Key Cryptosystem 31
4.3.1 Caesar Cryptosystem 32
4.3.2 Polybious Cryptosystem 32
4.3.3 Hill Cryptosystem 32
4.3.4 Affine Cryptosystem 32
4.3.5 Playfair Cryptosystem 32
4.3.6 Vigenere and Autoclave Cryptosystems 33
4.3.7 One time pad Cryptosystem 33
4.4 Perfect Secret Cryptosystem 33
4.5 Exercises 33
5 Public Key Cryptography 39
5.1 Diffie-Hellman Key Exchange 39
5.2 Blom's Key Predistribution Protocol 39
1
5.3 Cryptography and Computational Complexity 40
5.4 RSA Cryptosystem 40
5.5 Rabin-Miller's Prime Recognition 40
5.6 Exercises 41
6 Other Public Key Cryptosystems 45
6.1 Rabin Cryptosystem 45
6.2 ElGamal Cryptosystem 45
6.3 Exercises 45
7 Digital Signature 49
7.1 Digital Signature Scheme 49
7.2 Attacks on Digital Signature 49
7.3 RSA Signatures 50
7.4 ElGamal Signatures 50
7.5 Digital Signature Algorithm 50
7.6 Ong-Schnorr-Shamir Subliminal Channel Scheme 51
7.7 Lamport Signature Scheme 51
7.8 Exercises 51
8 Elliptic Curve Cryptography and Factorization 56
8.1 Elliptic Curve 56
8.2 Addition of Points 56
8.3 Elliptic Curves over a Finite Field 57
8.4 Discrete Logarithm Problem for Elliptic Curves 57
8.5 Factorization 57
8.5.1 Factorization with Elliptic Curves 57
8.5.2 Pollarďs Rho Method 57
8.6 Exercises 58
9 User Identification, Message Authentication and Secret Sharing 64
9.1 User Identification 64
9.2 Message Authentication 65
9.3 Secret Sharing Scheme 65
9.3.1 Shamir's (n, i)-secret sharing scheme 65
9.4 Exercises 66
10 Bit Commitment Protocols and Zero Knowledge Proofs 70
10.1 Bit Commitment Protocols 70
10.2 Oblivious Transfer Problem 70
10.3 Zero Knowledge Proof Protocols 71
10.4 3-Colorability of Graphs 71
10.5 Exercises 72
Bibliography 76
2
Introduction
The main goal of this work is to present detailed solutions of exercises that have been submitted
to students of the course Coding, cryptography and cryptographic protocols, given
by prof. RNDr. Jozef Gruska, DrSc. in 2006 as homeworks. The authors of exercises are Mgr.
Lukáš Boháč, RNDr. Jan Bouda, Ph.D., Mgr. Ivan Fialik and Mgr. Josef Sprojcar.
This way we create a handbook of solved exercises from coding theory and cryptography
that could be useful to the future students of the above course. Ahead of each set of exercises
we include main concepts and results from the corresponding lecture that are needed to
solve exercises. The main source of solutions presented here are solutions submitted by the
students of the above course. The solutions were adopted and/or modified to achieve a
uniform presentation of the exercises and of their solutions.
For some of the exercises we present not only one, but several solutions in the case sufficiently
different approaches have been used in the submitted solutions. Some of the solutions
are newly created. The authors of solutions are cited. The solutions, where no author is
stated, were created or submitted by myself.
Ciphers and codes have been a part of human history since the time of Egyptian pharaohs.
They arose from the requirement to protect secrets and messages against aliens and enemies.
People were trying to protect their own secrets, as hard as they were trying to discover secrets
of others. Their competition led up to invent better and better ciphers and codes that
cannot be so easily broken through. And this is how the cryptography progresses till now:
code makers are inventing new more sophisticated and secure ciphers and codes and code
breakers try to crack them. The struggle between the code makers and the code breakers
stood in the background of various historical events - it decided battles, revolts and human
lives.
Today, encipherment, coding and authentication are an inseparable part of our daily life.
Therefore, it is very important to know the history of ciphers, how they work and where
are their weaknesses. The basics can be obtained in the course Coding, Cryptography and
Cryptographic Protocols, taught at the Faculty of Informatics every year by prof. RNDr. Jozef
Gruska, DrSc.
The bibliography I used as a source of information for my work and which can be useful
for everyone interested in more detailed information about studied problems is listed at the
end of the work. Simultaneously, there are listed some interesting web pages, where can be
found more about problems, as well as some useful tools for solving exercises.
3
Chapter 1
Basics of Coding Theory
Coding theory has developed methods of protecting information against noise. Without coding
theory and error correcting codes, there would be no deep space pictures, no satellite TV,
no CD, no DVD and many more...
1.1 Definition of Code
A code C over an alphabet S is a subset of X* (C C X*). A q-ary code is a code over alphabet
of q symbols. A binary code is a code over the alphabet {0,1}.
The Hamming distance h(x, y) of words x, y is the number of positions, where words x
and y differs. The properties of Hamming distance are following:
1. h(x,y) = 0 <^ x = y
2. h(x,y) = h(y,x)
3. h(x,z) <h(x,y) + h(y,z)
An important parameter of codes is their minimal distance h(C).
h{C) = mm{h(x,y)\x,y eC,x^ y},
h{C) is the smallest number of bits needed to change one codeword into another. Code C
can detect up to s errors if h(C) > s + 1. Code C can correct up to t errors if h(C) > 2t + 1.
An (n, M, d)-code C is a code such that n is the length of codewords, M is the number of
codewords and d is the minimum distance of C. A good (n, M, d) code has small n and large
M and d.
The main coding problem is to optimize one of the parameters n, M, d for given values
of the other two. Aq(n, d) is the largest M such that there is a q-ary (n, M, d)-code. It holds
that
1. Aq(n, 1) = qn
2. Aq{n,n) = q
1.2 Equivalence of Codes
Two q-ary codes are equivalent if one can be obtained from the other by a combination of
following operations:
1. permutation of the positions of the code;
4
1. BASICS OF CODING THEORY
2. permutation of symbols at the fixed positions.
Any q-ary (n, M, d)-code is equivalent to an (n, M, d)-code which contains the zero code-
word.
If d is odd then a binary (n, M, d)-code exists if and only if a binary (n + l,M,d + l)-code
exists. That means that if d is odd then ^ ( n , d) = Ä2{n + 1, d + 1) and if d is even then
A2(n,d) = A2(n- l,d- 1).
1.3 Properties of Code
and any integer r > 0 the sphere of radius r and center u is defined as
FTM is a set of all words of length n over alphabet {0,1,.. .q -- 1}. For any codeword u e Fr
q
are of radius r and center u is de
S(u,r) = {veFTM\d(u,v) <r}.
A sphere of radius r in FTM 0 < r < n contains
r
t o ˇ*
words.
The sphere packing bound: If C is a q-ary {n, M, 2i + l)-code, then
M-Y,(n
\q-Vý<qn
. (1.1)
i=o W
A code which achieves the sphere packing bound (a code that satisfies the equality) is called
a perfect code.
Singleton's bound: If C is a q-ary (n, M, d)-code, then
M < qn
~d+l
. (1.2)
Gilbert-Varshamov's bound (lower bound): For a given d < n, there exists a q-ary
(n, M, d)-code with
qv
M
> * i ,\ (1-3)
and therefore
1.4 Entropy
A(M)> ^_! 9
E^to1
(?)(?-i)
Let X be a random variable (source) which takes a value x with probability p(x). The entropy
of X is defined by
SpO = -J>(z)lgi>0*0 (1-4)
X
and it is considered to be the information content of X. Shannon's noiseless coding theorem
says that in order to transmit n values of X we need to use nS{X) bits. More exactly, we
cannot do better and we should reach the bound nS{X) as close as possible.
5
1. BASICS OF CODING THEORY
1.5 Exercises
Exercise 1.1
Determine Aq(n, d) and write or describe the corresponding code that achieves the upper
bound.
1. A2{S,d)iord = 1 and d = 2.
2. A2(n, 4) for n = 4, n = 5 and n = 6.
3. Aq(4,3)íorq = 2andq = 3.
Solution 1.1.1
1. A2(8,d)
(a) d = 1. A2(8,1) = 28
. Code C contains all binary words of the length eight.
(b) d = 2. A2(8,2) = A2(7,1) = 27
. Code C contains all binary words of the length
seven with the parity bit added.
2. A2{n,A)
(a) n = 4. A2(4,4) = 2. C = {0000,1111}.
(b) n = 5. A2(5, 4) = 2 because C contains the word 00000, then it can contain only
one word with four or five ones. C cannot contain any other word because of the
given minimum distance d = 4.
(c) n = 6. A2(6,4) = A2(5,3). We know from the first lesson, that A2(5,3) = 4 and
one of the corresponding codes is the code C3 = {00000,01101,10110,11011}.
(6,4, 4)-codes exist and come from the code C3. There is, for example, the code
C = {000000,011011,101101,110110} (it is the code C3 with a parity bit added).
3. ,4,(4,3)
(a) q = 2. ^2(4,3) = 2. Indeed, because 0000 G C, there is no word in C with less
then three ones and there can be only one word with three or four ones in C. One
of A2(4,3)-codes is code C = {0000, Olli}.
(b) q = 3. A3(4,3) < qTM-^1
= 32
according to Singleton's bound. And we can find
a ternary (4,9,3)-code C = {0000,0111,0222,1012,1120,1201,2021, 2102,2210}
that reaches the Singleton's bound (1.2).
Exercise 1.2
Let q > 1. What is the relation (<, > or =) between
1. Aq(2n, d) and Aq(n, d)
2. Aq(n,d) and Aq(n + 2,2d)
3. A2(n,2d-I) and A2(n +1,2d)
6
1. BASICS OF CODING THEORY
Solution 1.2.1
1. Aq(2n,d) > Ag(n,d)
Let Aq(2n, d) = M\ and Aq(n, d) = M2. We need to show that for each q, n and d it holds
Mi > M2. To do that, we need to determine which code contains more codewords. We
compute it using the Singleton bound (1.2), page :
Mi < q2n
~d
+\
M2 < qn
~d
+l
.
We can see that
2ra--d+l n n--d+l \ n--d+l
and therefore Aq(2n, d) contains qn
codewords more then Aq(n, d) and hence Aq(2n, d) >
Aq{n,d).
We can see that if we have two codes of different length with the same minimum distance,
the code with longer codewords contains more codewords then the other code.
2. Aq(n, d) and Aq(n + 2,2d) are incomparable as we can see in the following examples:
if q = 2, n = 2 and d = 1 then A2(2,1) = 22
< A2(4,2) = A2(3,1) = 23
,
if n = 2 and d = 2 then Aq{2, 2) = q = Aq(4, 4) = q,
ifq = 2,n = 4andd = 2 then A2(4,2) = A2(3,1) = 23
> A2(6, 4) = A2(5,3) = 4.
3. yl2(n, 2d - 1) = A2(n + 1,2d) Because
2d - 1 is odd, we have A2(n, 2d - 1) = A2{n + 1, (2d - 1) + 1) = A2{n + 1,2d).
Exercise 1.3
Consider the binary erasure channel which has two inputs (0 or 1) and three outputs (0, 1
or ?). The symbol is correctly received with probability 1 -- p and erased with probability p.
Erasure is indicated by receiving the symboľ?'.
1. Consider the nearest neighbour decoding strategy and the code
C = {011,101,110,000}.
Calculate the probability that the received word is decoded incorrectly and the probability
of error detection.
2. Consider a code C with the minimum distance h(C) = d. How many erasures can the
code C detect and correct?
3. Consider a binary channel that has both erasures and errors. Give the lower bound for
the minimum Hamming distance for a code capable of correcting all combinations of
e erasures and t errors.
7
1. BASICS OF CODING THEORY
Solution 1.3.1
1. The received word is decoded incorrectly only if it contains two or more question
marks. The probability of an erroneous decoding is:
3 ˇ P2
{1 - p) + P3
= 3j92
- 3j93
+ p3
= 3j92
- 2p3
We can detect every erasure because the question mark is not an element of the code
alphabet. And we can correct one erasure in the codeword. So the probability that the
received word is decoded correctly is:
(l-pf + 3-p-(l-p)2
= l-3j9 + 3j92
-J93
+ 3j9-6j92
+ 3j93
= l-3j92
+ 2j93
= l-(3j92
-2j93
)
2. Code C can detect every erasure - in this case we receive a symbol that cannot be sent.
Code C can correct up to d -- 1 erasures in a codeword. When receiving a word with
e < d -- 1 erased symbols, we delete positions where we received a question mark
in all codewords of C. This way we get a new code C. The length of the codewords
decreases from n to n -- e and the d(C) decreases to d -- e > 1. That means, that there
is still the Hamming distance h(x, y) > 1 of each two words x, y of the code C. So we
can decode the received word correctly.
3. The minimum distance for a code C capable of correcting all combinations of e erasures
and t errors is d(C) = 2t + e + 1. When there are some (less then or equal to e) erased
symbols, we transform the code C to code C the same way as it was described above
and d(C) > It + 1. According to the definition of Hamming distance, we can correct
up to t errors in the codeword.
Exercise 1.4
You are given two dices with 6 faces. Design a binary Huffman code for encoding the sum
of two dices. Compare efficiency of the proposed code with Shannon's entropy.
Solution 1.4.1
All the possible sums of two dices and their probabilities are written in the Table 1.1.
At the Figure 1.1 there you can see how to design a Huffman code for the given data. (For
short, there is written 1 there instead of 1/36 and so on.)
In the Table 1.2, there are written the possible values and their codes. We can see, that it
is a prefix code.
We calculate the Shannon's entropy (1.4) as follows:
S(X) = - J2P(X
) ˇ l
SP(x) ~ 3.2744
X
By Shannon's theorem, we need 3.2744 bits in average per message. Now, we calculate the
efficiency E of our code:
E =  p ( . , ) M e ( x ) | = 3 . 3 + 4 + 5
+ 6 + 5 + 4
+ 4 - ^|í + 5 - i  l ,, 3.3056
X
By using our code we need circa 0.03 bits per message (sum of two dices) more.
8
1. BASICS OF CODING THEORY
X p(x)
2 1/36
3 2/36
4 3/36
5 4/36
6 5/36
7 6/36
8 5/36
9 4/36
10 3/36
11 2/36
12 1/36
Table 1.1: Messages and their probabilities
6:
S:
5:
9:
4:
10:
3:
11:
2:
12:
6 6 6 6 7 8 10 11 15 21 36
5 5 5 5 i 6 i 7 . 8 \ 10 Í 11 \ 15 J
5 5 5 5 6 \ 7 \ 8 , 10
4 4 4 5 5 \ 6 \ 7
4 4 4 \ 4 5
\
, 5 5
3 3 4 ^L 4 , 4 * 5 ˇ
3 3 . 3 ; r^i 4
2 2 3
2 2 i 2 \
1 2
Figure 1.1: Design of the Huffman code
S code
2 00101
3 1000
4 000
5 011
6 110
7 111
8 101
9 010
10 1001
11 0011
12 00100
Table 1.2: Messages and their codes
1. BASICS OF CODING THEORY
Exercise 1.5
You have found the belt with an ornament displayed at the Figure 1.2. It seems that the
ornament is related to coding theory. Decode the hidden message.
O O OOO O OO OOOO 00
OOOOO OO O O OOOO OOOO o
OOO O 00 OOO O OOO OOO
O O OOO OOO OO OO OOO o
Figure 1.2: Ornament belt
Solution 1.5.1 by Lukáš Boháč
NRZI (Non Return to Zero, Inverted) signal encoding was used. A change of the level encodes
1, staying on the level encodes 0. The bit-string encodes the message CODE NRZI (8bit
ASCII code) as you can see at the Figure 1.3.
o o ooo o o o ooo o oo
OOOOO 0 0 0 0 0 0 0 0 0 0 0 0 o
01000011 01001111 01000100 01000101
C G D E
ooo o OO 00 O O 00 O 000
O O 00 O 000 00 00 000 o
01001110 01010010 01011010 01001001
N R Z I
Figure 1.3: Ornament belt - the hidden message
Exercise 1.6
A single character was encoded into the following long message. Decode.
012221102011200210110121222012001211122201
Solution 1.6.1
The message is 42 bits long and there should be hidden only one single character. Therefore
there is a strong probability that it is a graphic cipher. Our task is to form the message into
a table and look for the hidden letter. The character is formed by twos when we put the
message into a table with six rows and seven columns. And here we can see the letter G:
10
1. BASICS OF CODING THEORY
0 1 2 2 2 1 1
0 2 0 1 1 2 0
0 2 1 0 1 1 0
1 2 1 2 2 2 0
1 2 0 0 1 2 1
1 1 2 2 2 0 1
replacing the Is and 0s 1
2
2
2
2
2
2
2 2
2
2 2 2
2
2 2
Chapter 2
Linear Codes
Linear codes are important because they have very concise description, very nice properties,
very easy encoding and in principle quite easy decoding.
2.1 Definition of Linear Code
Linear codes are special sets of words of length n over an alphabet {0,... ,q -- 1} where q is
a power of prime.
A subset C C V (n, q) is called a linear code if
1. for all u, v G C: u + v G C;
2. for all u G C, a G GF (q): au G C,
where GF{q) is Galois field, the set {0,... ,q -- 1} with operations + and ˇ taken modulo g,
where g is a prime.
We can also say that a subset C C.V(n, q) is a linear code if one of the following conditions
are satisfied:
1. C is a subspace of V(n, q);
2. sum of any two codewords from C is in C (for the case q = 2).
If C is a fc-dimensional subspace of V(n, q) then C is called [n,fc]-codeand C consists of
qk
codewords.
If S is a set of vectors of a vector space then (S) is the set of all linear combinations of
vectors from S. For any subset S of a vector space the set (S) is a linear space that consists of
the following words:
* the zero word;
* all words from S;
* all sums of two or more words from S.
The weight of a codeword x denoted as w(x) is the number of nonzero entries of x. If
x,y G V(n, q) then the Hamming distance h(x,y) = w(x -- y). If C is a linear code then
the weight of code C, denoted as w(C), is the smallest weight of all the weights of nonzero
codewords from C and w(C) = h(C).
If C is a linear [n,fc]-codethen it has a basis of k codewords.
Ak xn matrix whose rows forms a basis of a linear [n,fc]-code(subspace) C is said to be
a generator matrix of C.
12
2. LINEAR CODES
2.2 Equivalence of Linear Codes
Two linear codes over GF (q) are equivalent if one can be obtained from the other by the
following operations:
1. permutation of the positions of the code;
2. multiplication of symbols appearing in a fixed position by a nonzero scalar.
Two nxk matrices generate equivalent linear [n,fc]-codeover GF{q) if one matrix can be
obtained from the other by a sequence of the following operations:
1. permutation of the rows;
2. multiplication of a row by a nonzero scalar;
3. addition of one row to another;
4. permutation of columns;
5. multiplication of a column by a nonzero scalar.
2.3 Dual Code
If C is a linear [n,fc]-codethen the dual code of C, denoted as C^, is defined by
C
= {ve V(n, q)\v ˇ u = 0 if u G C).
We can also say that if C is a linear [n, fc]-code with generator matrix G, then for all
v G V(n, q) holds
 e C 1
 vGT
= 0,
where GT
denotes the transpose of the matrix G.
If C is a linear [n, fc]-code over GF{q) then the dual code C1
- is a linear [n, n -- fc]-code.
A parity check matrix H of a linear [n,fc]-codeC is a generator matrix of code C^.
If H is a parity check matrix of C then
C = {xeV(n,q)\xHT
= 0}
and therefore any linear code is completely specified by its parity check matrix. The rows of
a parity check matrix are parity checks on codewords.
If G = [Ik\A] is the standard form of generator matrix of a linear [n,fc]-codeC, then the
parity check matrix for C is H = [--AT
\In_k\.
2.4 Encoding with Linear Codes
Encoding of a message u = (u\,..., Uk) with a linear code C with a generator matrix G is
vector - matrix multiplication:
k
u-G = y^ujTj,
Í - 1
where r\,..., rk are rows of the matrix G.
If a codeword x = x\,..., xn is sent and the word y = yi,..., yn is received then e =
y -- x = e\,..., en is said to be the error vector. To decode y, it is necessary to decide which x
was sent or which error e occurred.
13
2. LINEAR CODES
2.5 Decoding of Linear Codes
Suppose that C is a linear [n,fc]-codeover GF(q) and a e V(n, q). The set
a + C = {a + x\x G C}
is called a coset of C in l/(g, n).
If C is a linear [n,fc]-codeover GF(q), then every vector of V(n, q) is in some coset of C.
Every coset contains exactly qk
words and every two cosets are either disjoint or identical.
Each vector having the minimum weight in a coset is called a coset leader.
Nearest neighbour decoding strategy: A word y is decoded as a codeword of the first
row of the column in which y occurs.
Let C be a binary [n,fc]-code,and for i = 0,1,..., n let a be the number of coset leaders
of weight i. The probability Pcorr(C) that a received vector after decoding is the codeword
which was sent is given by
n
Pcorr{C) = Y,^p\l-p)n
-1
.
i=0
The decoder will fail to detect transmission errors if the received word y is a codeword
different from the sent codeword x. Let C be a binary [n,fc]-codeand Ai be the number of
codewords of C of weight i. The probability PUndetected{C) that a an incorrect codeword is
received is
n
Pundetected(C) = J ] AiP\l - p ) ^ .
i=0
If H is a parity check matrix of a linear [n,fc]-codeC, then S(y) is called the syndrom of
y, for each y G V (n, q). The syndrom can be calculated as follows:
S(y) = yHT
. (2.1)
Two words have the same syndrom if and only if they are in the same coset.
Syndrom decoding: When a word y is received, compute S(y), locate the coset leader I
with the same syndrom and decode y as y -- I.
2.6 Hamming Code
An important family of simple linear codes are Hamming codes. Let r be an integer and H be
a r x (2r
-- 1) matrix whose columns are nonzero distinct words from V(r, 2). The code having
H as its parity check matrix is called binary Hamming code and denoted as Ham(r, 2).
The Hamming code Ham(r, 2) is a linear [2r
-- 1, 2r
-- 1 -- r]-code, it has the minimum
distance 3 and it is a perfect code. Coset leaders are words of weight less then or equal to 1.
The syndrom of the word z with one at the ith position and zeroes otherwise is the transpose
of the ith column of matrix H.
Decoding the Hamming codes for the case that columns of H are arranged in the order
of increasing binary numbers the columns represent: when received word y compute S(y),
if S(y) = 0 then y is assumed to be the codeword sent, if S(y) / 0 then assuming a single
error, S(y) gives the binary position of the error.
14
2. LINEAR CODES
2.7 Properties of Linear Code
Singleton bound: If C is a linear (n, k, d)-code, then
n -- k > d -- 1.
If u is a codeword of a linear code C of weight w(u) = s, then there is a dependence relation
among s columns of any parity check matrix of C. Otherwise, any dependence relation
among s columns of a parity check matrix of C yields a codeword of weight s in C.
If C is a linear code then C has minimum weight d if d is the largest number such that
every d -- 1 columns of any parity check matrix of C are independent.
A linear (n, k, d)-code is called maximum distance separable (MDS code) iid = n -- k + 1.
MDS codes are codes with maximal possible minimum weight.
2.8 Exercises
Exercise 2.1
Decide which of the following codes is linear. Find a generator matrix in standard form for
linear codes.
1. 5-ary code Či = {21234, 42413,13142, 34321, 00000}
2. 6-ary code C2 = {201,202,231,402,403, 432,003, 004,033, 204, 205, 234,
405,400,435,000,001,030,404,005,200, 401,002, 203, 433, 034, 235, 430,
031,232,035,230,431,032, 233, 434}
3. Ternary code C3 = {000, 201, 111, 021, 012,120,102, 222, 210}
Solution 2.1.1
1. 5-ary code Či = {21234,42413,13142,34321, 00000} is linear code over GF(5) because
for each u,v <E C\ : u + v <E C\ and for each a G GF(5),u e C i : au G C\. The generator
matrix G is:
(2 1 2 3 4\
4 2 4 1 3
1 3 1 4 2
3 4 3 2 1
\0 0 0 0 0/
1 3 1 4 2 )=G
2. 6-ary code C2 is not a linear code because 6 is not a power of prime.
3. Ternary code C3 = {000,201, 111, 021,012,120,102,222,210} is linear code over GF(3)
because for each u, v G C3 : u + v G C3 and for each a G GF(3),u G C3 : au G C3. The
15
2. LINEAR CODES
generator matrix G is:
í° 0 o\
2 0 1
1 1 1
0 2 1
0 1 2
1 2 0
1 0 2
2 2
i
2
\2 1 0/
1 0
0 1
= G
Exercise 2.2
Let C be a binary code of length 6 such that for every rcia^s G {0, l } 3
: X\X2X?,X4X<ÓX§ G C if
and only if X4 = x\ + X2, X5 = X2 + 3 and a?6 = x\ + 2 + X3. Show that C is a linear code.
Find a generator matrix and a parity check matrix for C.
Solution 2.2.1 by Jiří Novosad
Consider binary code C of length 6 such that for every rcia^s G {0, l } 3
: x\X2X^x^x^x^ G
C -<==> X4 = x\ + X2, X5 = X2 + 3, a?6 = #1 + X2 + #3. In the next table are shown all the
codewords from the code C:
X\ 2 X3 ^1^2^3^4^5^6
0 0 0 000000
0 0 1 001011
0 1 0 010111
0 1 1 011100
1 0 0 100101
1 0 1 101110
1 1 0 110010
1 1 1 111001
Since C is a binary code we have to prove that \/x,y G C : x+y G C. Let x = X1X2X3X4X5XQ G
C and y = 2/12/22/32/42/52/6 G C. If
z = x + y = (xi+ y\){x2 + 2/2) ˇ ˇ ˇ (x6 + 2/6) = ^ 2 ^ 4 2 5 %
then we can see that
Zi = X4 + 2/4 = X\ + 2 + 2/1 + 2/2 = 21 + 22
Z5 = 5 + 2/5 = 2 + X3 + 2/2 + 2/3 = Z2 + <?3
Z6 = X6 + 2/6 = Xi + 2 + 3 + 2/1 + 2/2 + 2/3 = 21 + 22 + Z3
and that means that z G C and that the code C is linear.
16
2. LINEAR CODES
l 0 0 l 0 lN
~> i 0 l 0 l l l
.0 0 1 0 1 1.
= G.
Code C consists of 8 codewords thus its dimension must be 3. The generator matrix for
code C is:
/0 0 0 0 0 o\
0 0 1 0 1 1
0 1 0 1 1 1
0 1 1 1 0 0
1 0 0 1 0 1
1 0 1 1 1 0
1 1 0 0 1 0
\ 1 1 1 0 0 1/
The parity check matrix for code C is:
/ l 1 0 1 0 0>
# = [ 0 1 1 0 1 0
\1 1 1 0 0 1,
Solution 2.2.2 by Martin Vejnár
Let B = {100101,010111,001011}. Then C = (B) because
Va;i, #2, a;3.a;i (100101) +2 (010111) +3 (001011) = (x\, ^2,^3,^1 +^2,^2+^3,^1+^2 + X3).
The generator matrix for code C is
/ l 0 0 1 0 ť*
G = 0 1 0 1 1 1
\0 0 1 0 1 1,
And the parity check matrix for code C is
/ l 1 0 1 0 0>
# = [ 0 1 1 0 1 0
\1 1 1 0 0 1,
Exercise 2.3
Find examples of a linear self-dual code of length 3 and 4. If such code does not exist, prove
it.
Solution 2.3.1
There is no self-dual code C of length 3 because C must be a [3,fc]-codewhere k G {1,2,3}.
Code C1
- must be a [3,3 --fc]-code.But there is no k such that k = 3 -- k.
The code C = {0000,1010,0101,1111} is a self-dual code. The generator matrix for code
Cis:
'I 0 1 0N
G =
0 1 0 1
The parity check matrix H for code C is equal to matrix G. Because the generator matrix G1
for
the dual code C1
- is the parity check matrix for code C, we have G = H = G-1
. So we can
see that the code C is self-dual.
17
2. LINEAR CODES
Exercise 2.4
Find a generator matrix and a parity check matrix for ISBN code.
Solution 2.4.1
The ISBN code is not a linear code unless we allow all position of the code to have a value
from Zu - strictly, only the last digit can be X.
The ISBN code is a 11-ary code of length 10. We use it to encode massages of length 9, so
its dimension must be 9. Basically, encoding is a process of calculating the 10th position of
the given message so that the following equality is fulfilled:
10
y j i ˇ Xi = 0 (mod 11)
%=\
We can see, that the generator matrix for ISBN code is:
/ l 0 0 0 0 0 0 0 0 1\
G =
0 1 0 0 0 0 0 0 0 2
0 0 1 0 0 0 0 0 0 3
0 0 0 1 0 0 0 0 0 4
0 0 0 0 1 0 0 0 0 5
0 0 0 0 0 1 0 0 0 6
0 0 0 0 0 0 1 0 0 7
0 0 0 0 0 0 0 1 0 8
\0 0 0 0 0 0 0 0 1 9/
The parity check matrix is following:
H = -1 -6 -7 -8 - 9 1) = (10 9 8 7 6 5 4 3 2 1).
Exercise 2.5
Prove that a binary Hamming code 7ir is perfect.
Solution 2.5.1
According to the Corollary "If C is a linear code, then C has minimum weight d, if d is the
largest number such that every d -- 1 columns of any parity check matrix of C are independent."
we can see, that the minimum distance d of 7ťr is 3. Because the columns of the parity
check matrix for a 7ir consists of all non zero distinct words from V(r, 2), every two columns
are independent. When we have words 01...1,10...0,1...1 of length r, we can see that the sum
of the first and the second word is the third word. That means that not every 3 columns are
independent and therefore the largest d is 3.
The parity check matrix H for 7ir is a r x 2r
-- 1 matrix, hence the generator matrix for 7ir
is a 2r
-- 1 -- r x 2r
-- 1 -- r + r matrix. That means that Hr is a [2r
-- 1, 2r
-- 1 -- r]-code. Since
the dimension of the code Hr is 2r
-- 1 -- r, the number of codewords is 22r
~1
~r
. We can say
that Hr is a (2r
- 1,22r
-1
~r
, 3)-code.
18
2. LINEAR CODES
We know that a code is perfect if it achieves the sphere packing bound (1.1), page 5. That
means that the following equality must be satisfied:
2*--i- (  ('2
" , 1
] ( 2 - i r ] = 2
a = 0
2 r
- l
And we have:
-,2r
-l-r I I z L
+
1
(2 - 1) ) = 22 r
-1
"r
(1 + 2r
- 1) = 22 r
-1
"r
* 2r
= 22
"-1
o y v i
Now it is obvious, that Hr is a perfect code.
Exercise 2.6
Let C = {00000,10001,01010,11011, 00100,10101, OHIO, 11111} be a binary linear code. List
all the cosets of C. Compute a parity check matrix for C. Use syndrom decoding to decode
words 00111 and 01011.
Solution 2.6.1
Code C = {00000,10001, 01010,11011,00100,10101, OHIO, 11111} is a binary linear code because
the sums of any two or more words from C falls into C. The generator matrix G of
code C is
/0 0 0 0 o\
1 0 0 0 1
0 1 0 1 0
1 1 0 1 1
0 0 1 0 0
1 0 1 0 1
0 1 1 1 0
VI 1 1 1 1/
The dimension of the code is 3 and the parity check matrix H of code C is
'I 0 0 0 H
0 1 0 1 0 | =G.
, 0 0 1 0 0 ,
H =
0 1 0 1 0
. 1 0 0 0 1,
The cosets of code C are following:
* 00000 + C = {00000,10001, 01010,11011, 00100,10101, OHIO, 11111}
* 00001 + C = {00001,10000, 01011,11010, 00101,10100, 01111,11110}
* 00010 + C = {00010,10011, 01000,11001, 00110,10111, 01100,11101}
* 00011 + C = {00011,10010, 01001,11000, 00111,10110, 01101,11100}
There are no other cosets because there is only 25
binary words of length 5 and all of them
are listed above.
We determine the syndrom S(y) of word y as shown in (2.1), page 14. The syndromes of
coset leaders are following:
19
2. LINEAR CODES
coset leader I(z) syndrom z
00000 ÖÖ
00001 01
00010 10
00011 11
Now, we should decode words 00111 and 01011 using the syndrom decoding strategy:
* Lety = 00111 then z = S{y) = 11. The sent word was y -I (z) =00111-00011 = 00100.
* Lety = 01011 then z = S (y) = 01. The sent word was y-I(z) = 01011-00001 = 01010.
Exercise 2.7
Let C be a binary linear code. Show that either all the codewords of C have even weight or
exactly half of the codewords have even weight.
Solution 2.7.1
Let u and v be two binary words form V(r, 2). If w(u) and w(v) are both odd or both even,
the weight of their sum w(u + v) is even. If w(u) is even and w(v) is odd (or vice versa), the
weight of their sum w(u + v) is odd.
That means that if there is no word u G C with odd weight, all words from C must have
even weight.
In case that there is a word u G C with odd weight, the sum x + u must fall into C for
each x G C because C is a linear code. Now, we can define a relation a over the codewords
from C so that (x,y) G a if x + y = u. Since C is a binary code, a is symmetric relation, thus
(x, y) G a => (y, x) G a. Because w(u) is odd then one of w(x) and w(y) must be odd and the
other must be even. We can easily see that (x, y) G a only if x / y. In case that x = y then
x + y = x + x = 0 which is contradiction because w(0) is not odd.
Because a is defined over all words from C, and two words are in relation a only if one is
even and the other is odd, we can see that exactly one half of the codewords has odd weight
and the other has even weight.
Solution 2.7.2 by Jiří Novosad
Let x, y be codewords. Then x + y is a codeword with ones in exactly those positions, where
x and y differ. If w(x) and w(y) are both even, then w(x + y) is even too (two words with
even number of ones can't differ in an odd number of positions). By the same reasoning, we
get:
1. 2\w(x) A2\w(y) => 2\w(x + y)
2. 2 J(w(x) A2\w(y) ^ 2 )(w{x + y)
3. 2 J(w(x) A 2 )(w{y) ^2\w(x + y)
Now let us consider the three forms a generator matrix of a particular code can take (let k be
the dimension of the code):
* Firstly, all the vectors in the matrix can have even weight. From (1) we get that all the
generated vectors have even weight.
20
2. LINEAR CODES
* If exactly one of the vectors has odd weight, vector o, then the remaining k -- 1 vectors
generate a subspace E with 2fc_1
elements, whose weight is even, from (1). The coset
E + o has 2fc_1
elements with odd weight, from (2). The union of these two sets gives
us the whole subspace and exactly half the vectors has odd weight and the other half
has even weight.
* If there are more vectors of odd weight in the generator matrix, we can get the previous
case by choosing one odd vector and adding it to all the remaining odd vectors. From
(3) follows that there is only one vector with odd weight in the generator matrix.
Exercise 2.8
Let C be a binary linear code of length n. Let Cj denote the number of words of weight i in
C. Suppose that cn = 1. Show that Cj = cn-i for i G {0,1,..., n}.
Solution 2.8.1 by Martin Vejnár
Let C be a binary linear code of length n. Let Ci = {c G C\w(c) = i} be a set of codewords of
weight i. It holds that Cj = \Ci\. The only possible codeword x of weight w(x) = n is x = ln
.
Since cn = 1, Cn = {x}. Because C is a linear code, it is closed under addition and it holds
Vc G C. (c + x) G C. It can be easily observed, that w(c + x) = n -- w(c).
Now, we need to show that there is a bijective mapping for each 0 < i < n. Let fi : Ci -->ˇ
Cn-i be a mapping such that /j(c) = c + x. There is also a mapping kí : Cn-i -->ˇ Ci such that
ki{d) = d + x. We can see that fi and ki are bijective because f%oki = id = kiO fi.
21
Chapter 3
Cyclic Codes
Cyclic codes are of interest and importance because they posses rich algebraic structure that
can be utilized in a variety of ways. They have extremely concise specifications, they can be
efficiently implemented using shift registers. Many practically important codes are cyclic. In
order to specify a binary cyclic code with 2k
codewords of length n it is sufficient to write
down only one codeword of length n.
3.1 Definition of Cyclic Code
A code C is cyclic if
1. C is a linear code;
2. any cyclic shift of a codeword is also a codeword.
Comparing with linear codes, the cyclic codes are quite rare. For any field F and any
integer n > 3 there are always the following trivial cyclic codes of length n over F:
* Non information code (code consisting of just one zero codeword);
* Repetition code (code consisting of codewords an
for each a G F);
* Single-parity-check code (code consisting of all codewords with parity 0);
* Non parity code (code consisting of all codewords of length n).
For some cases, there are no other cyclic codes then the four trivial cyclic codes.
3.2 Algebraic Characterization of Cyclic Codes
A codeword of a cyclic code is usually denoted as
aodi... an-\
and to each such a codeword is associated the polynomial
do + a\x + Ü2X2
+ ˇ ˇ ˇ + an-\xa
~l
.
A code C is cyclic if C satisfies two conditions
1. a(x), b(x) e C ^ > a(x) + b(x) G C;
2. a(x) G C, r(x) G Rn => r(x)a(x) G C,
22
3. CYCLIC CODES
where Rn is a field such that Rn = Fq[x]/(xn
-- 1), where Fq[x] denotes the set of all polynomials
over GF(q).
For any f(x) G Rn the set
(f(x)) = {r(x)f(x)\r(x)<ERn}
is a cyclic code generated by the polynomial /.
Let C be a non zero cyclic code in Rn. Then there exists unique monic polynomial g(x) of
the smallest degree such that
* C = (g(x))
* g(x) is a factor of xn
-- 1.
If for a cyclic code C it holds
C = (g(x)),
then g (x) is called the generator polynomial for code C.
The task of finding all cyclic codes of given length n is equal to the task of finding all
factors of polynomial xn
-- 1.
3.3 Generator Matrix, Parity Check Matrix and Dual Code
Suppose C s a cyclic code of length n with the generator polynomial
g{x) = g0 + g\x H h grxr
.
Then dim(C) = n -- r and the generator matrix G for C is
f9o 9\ 92 ˇˇˇ 9r 0 0 0 ˇˇˇ 0 \
0 go gi 92 ˇˇˇ 9r 0 0 ˇ ˇ ˇ 0
0 0 go g\ 92 ˇˇˇ 9r 0 ˇˇˇ 0G =
\ 0 0 0 0 o go 9rJ
Let C be a cyclic [n, k] -code with the generator polynomial g (x) of order n -- k. Polynomial
g(x) is a factor of xn
-- 1. Hence
a;"--
1 = g{x)h{x)
for some polynomial /i(a;) of degree k. Polynomial h(x) is called the check polynomial of
code C.
Let C be a cyclic code over Rn with a generator polynomial g{x) and a check polynomial
h(x). Then any polynomial c{x) G i?TM is a codeword of C if c{x)h{x) = 0 (mod xn
-- 1).
Suppose C is a cyclic [n, fc]-code with the check polynomial h(x) = ho + ftio; H h hkXk
,
then
1. a parity check matrix for code C is
i i =
fhk hk-i
0 /ifc
Vo 0
ho 0
0
0 /ifc ˇˇˇ /io/
23
3. CYCLIC CODES
2. C1
- is the cyclic code generated by the reciprocal polynomial of h(x) :
h(x) = hk + hk-ix -\ h hoxk
3.4 Encoding with Cyclic Codes
Encoding using a cyclic code can be done by a multiplication of two polynomials - a message
polynomial and the generator polynomial of the cyclic code.
Let C be a cyclic [n,fc]-codeover any field F with the generator polynomial g{x) = go +
g\x + ˇ ˇ ˇ + grxr
of degree r = n -- k. If a message vector m is represented by a polynomial
m{x) of degree k and m is encoded as
c = niG,
then the following relation between m{x) and c{x) holds
c{x) = m{x)g{x).
3.5 Hamming Code
Let r be a positive integer and H be a r x (2r
-- 1) matrix whose columns are distinct nonzero
vectors from V(r, 2). Then the code having H as its parity check matrix is called binary
Hamming code and denoted as Ham(r, 2).
The binary Hamming code Ham(r, 2) is equivalent to a cyclic code.
If p{x) is an irreducible polynomial of degree r such that a; is a primitive element of the
field F[x]/p(x), ihenp(x) is called a primitive polynomial.
lip(x) is a primitive polynomial over GF{2) of degree r, then the cyclic code (p(x)) is the
Hamming code Ham(r, 2).
3.6 Exercises
Exercise 3.1
Let us consider the following definition of equivalence of two binary codes: Two binary
codes are equivalent if and only if they can be transformed to each other by permutation of
positions and addition of a constant vector.
Is this definition correct? Prove or disprove.
Solution 3.1.1 by Lukáš Mojžíš
The definition is correct. The standard definition of equivalence of two codes states that two
codes are equivalent if and only if one can be obtained from the other by permutation of
position and permutation of symbols appearing in a fixed position.
The first operation is the same in both definitions. The second operation, addition of
a constant vector, can be (for binary codes) transformed into permutation. If we want to
permute ith column, we add te every codeword vector v = (v\,V2, ˇ ˇ ˇ ,Vi,..., vn) where n is
the length of codeword and for i / j we have Vi = 1 and Vj = 0. Adding vector v to every
codeword we achieve the permutation of ith position.
24
3. CYCLIC CODES
Exercise 3.2
If it holds that C C C1
-, we say that C is weakly self-dual. If C is a weakly self-dual code,
show that every codeword has Hamming weight divisible by 3.
Solution 3.2.1 by Zdenek Kolář
This statement is not correct.
For example code C = {000,011} has a dual code C1
- = {000, 011, 111, 100}. We can see
that C C C1
- but the only non zero codeword has Hamming weight io(011) = 2.
Exercise 3.3
Use the Plotkin bound and properties of A(n, d) to prove that A2(2d, d) < 4d.
Plotkin bound: Let C be a binary code with minimum distance d and length n. If 2d > n
then
A(n, d) < 2 -- --v
' ;
- 2d-n
Solution 3.3.1
First we need to show that Aq(n, d) < qAq(n--1, d). Let Aq(n,d) = M\ and qAq(n--l,d) = M2.
From the Singleton's bound (1.2) (page 5) we have
Mi < qn
-d+
\
M2 < qqn-l-d+l = qn-d+l_
We can see that the values of Mi are lower then qn
-d
+l
. Now, we need to determine the
minimal values of Mj. To do that, we use the lower bound (1.3) (page 5):
n
Mi . q
d-1 fn\
n--l
T.U (?-i)'"
M2 . = "
E^UVX-1
)'"
It is obvious that Mimin < M2min. In total, we get that Mi < M2, what is equal to Aq(n, d) <
qAq{n- l,d).
Leťs assume that q = 2 and n = 2d. Then we have A2(2d, d) < 2A2(2d -- l,d). Because
2d > 2d -- 1 we can use the Plotkin bound and we get
A2(2d-l,d) <2
d
2d-{2d-I
When we put this two inequalities together we get
^2(2d, d) < 2A2(2d -l,d)< 4d.
= 2d.
25
3. CYCLIC CODES
Exercise 3.4
Determine whether the following codes are cyclic. Explain your reasoning.
1. The ternary code Ci = {0000,1212, 2121}
2. The ternary code C2 = {x\x G Z| A w(x) = 0 (mod 3)}
3. The ternary code C3 = {x\x G Z| A 1 + X2 + ˇ ˇ ˇ + 5 = 0 (mod 3)}
4. The 7-ary code C4 = {aľ|aľ G Zf A f=1 ia;, = 0 (mod 7)}
Solution 3.4.1
1. Ternary code C\ is cyclic code. Let c\ = 0000, C2 = 1212 and C3 = 2121, then:
Cl + C2 = C2, Cl + C3 = C3, C2 + C3 = Cl, C2 + C2 = C3, C3 + C3 = C2
Cl --ˇ Cl, C2 --ˇ C3 --ˇ C2
C\ = {1 - x + x2
- x3
)
2. Ternary code C'2 is not cyclic. For example, words 11100 and 00111 both fall into C'2,
because lo(lllOO) = lo(OOlll) = 0 (mod 3). Their sum must also fall into C2 in case it
is linear, but w(11100 + 00111) = w(11211) = 2 (mod 3). That is contradiction so code
C2 is not cyclic.
3. Ternary code C3 is a cyclic code. We know, that a code is cyclic, if it is a linear code and
if any cyclic shift of a codeword is also a codeword.
Firstly, let x = X1X2X3X4X5 and y = 2/12/22/32/42/5 be words from C3. Then x\ + X2 +
xs + X4 + X5 = 0 (mod 3) and 2/1 + 2/2+2/3+2/4 + 2/5 = 0 (mod 3), that means that
{x\ +^2+^3+^4+^5) + (2/1 +2/2+2/3+2/4+2/5) = 0 (mod 3) and because of commutativity
and associativity of addition we get (a;i+2/1)+ (^2+2/2)+ (^3+2/3)+ (^4+2/4)+ (^5+2/5) =
0 (mod 3). And so the word x + y = (x\ + y\){x2 + 2/2X^3 + 2/3)(4 + 2/4)(5 + 2/5) falls
into C3.
Leta; = ^1^23:3^4^5 be a word from code C3 and a be a scalar < 3. Wehavea;i+a;2+a;3 +
X4+X5 = 0 (mod 3) after multiplying this equality byawe get 0(^1+^2+^3+^4+^5) =
aO (mod 3) because of distributivity we get ax\ + ax2 + axs + ax^ + ax^ = 0 (mod 3)
hence the word ax = (axi)(ax2)(axs)(ax4)(ax5) G C3.
Secondly, let a; = ^1^23:3^4^5 be a word from code C3, then a?i + a?2 + X3 + 4 + X5 = 0
(mod 3). And because of commutativity of addition we get X5 + x\ + X2 + 3 + X4 = 0
(mod 3), that means that the word a^ia^iCsa^ falls into C3 too.
4. The 7-ary code C4 is not cyclic. We can easily see that the word 20001 is a codeword
from C4 because 2 + 0 + 0 + 0 + 5 = 0 (mod 7). If code C4 is cyclic, then any cyclic
shift of a codeword should be a codeword too. But the word 12000 is not a codeword
because 1 + 4 + 0 + 0 + 0 = 5 (mod 7). Hence the code C4 cannot be a cyclic code.
Exercise 3.5
Let Ci, C2 be </-ary cyclic codes of length n with generator polynomials f\{x), J2{x). Show
that the code C3 = C\ n C2 is also cyclic. Find its generator polynomial.
26
3. CYCLIC CODES
Solution 3.5.1
Let x and y be words from C3. That means that x,y G C\ and x,y G C2. Because both C\ and
C2 are cyclic, all cyclic shifts of x and y and their sums falls into C\ so as into C2. Hence they
fall into C3 too. And that means that C3 is a cyclic code too.
Let fi(x) and f2(x) be the generator polynomials of C\ and C2, then C\ = (fi(x)) and
C2 = (/2(a;))- We know that (f(x)) = {r(x)f(x)\r(x) G Rn} hence: (fi(x)) = {r(x)fi(x)\r(x) G
i?,,} and (f2(x)) = {s(x)f2(x)\s(x) G i?,,} (multiplication is taken modulo af1
-- 1) because
fi(x), f2(x) G Rn, there must be some r(x) = f2(x) and some s(x) = f\{x). That is the way
how we get the generator polynomial of C3, it is the polynomial lcm(/i(a:), f2(%)) (modulo
xn
- 1).
Exercise 3.6
1. Describe all binary cyclic codes of length 19.
2. How many different binary cyclic [65,36] codes are there?
3. Is it possible to find a binary cyclic [65,20] code?
Solution 3.6.1
With the help of website h t t p : //www. quickmath. com/ [6] and its factorizing tool we can
get the following results:
1. There are only four trivial binary cyclic codes of length 19. Firstly, it is written in the
materials, secondly, x19
-- 1 = (x + l)(x18
+ x17
+ x16
+ x15
+ xu
+ x13
+ x12
+ x11
+
xw
+ x9
+ x8
+ x7
+ x6
+ x5
+ xA
+ x3
+ x2
+ a; + 1) so the according cyclic codes are:
* (1) => nonparity code
* (x + 1) => single-parity-check code
* (a?18
+ a;17
+ ˇ ˇ ˇ + x + 1) => repetition code
* (a;19
-- 1) => non-information code
2. The factors of polynomial x65
-- 1 are (x +1) (a;4
+x3
+x2
+x +1) (a;12
+a;8
+a;7
+a;6
+a;5
+
a;4
+ l)(a;12
+a;10
+a;7
+a;6
+a;5
+a;2
+ l)(a;12
+a;10
+a;9
+a;8
+a;6
+a;4
+a;3
+a;2
+ l)(a;12
+a;11
+
a;9
+a;7
+a;6
+a;5
+a;3
+ a; + l)(a;12
+ a;11
+a;10
+ a;9
+ a;8
+ a;7
+a;6
+a;5
+a;4
+a;3
+a;2
+a; + l).
The binary cyclic [65,36]-code is generated by polynomial of degree 65 -- 36 = 29 that
are factors of x65
-- 1. Since 29 = 1 + 4 + 12 + 12 we have to choose two different
polynomials of degree 12, so there are (2) =10 possibilities how can we choose them.
That means that there are 10 different binary cyclic [65,36]-codes.
3. The factors of polynomial x65
-- 1 are written above and we can see that we get all the
trivial cyclic codes, one [65,61]-code, one [65,60]-code, five [65, 53]-codes, five [65, 52]codes,
five [65, 49]-codes, five [65,48]-codes, ten [65,41]-codes, ten [65, 40]-codes, ten
[65,37]-codes, ten [65,36]-codes, ten [65,29]-codes, ten [65,28]-codes, ten [65, 25]-codes,
ten [65,24]-codes, five [65,17]-codes, five [65,16]-codes, five [65,13]-codes, five [65,12]codes,
one [65, 5]-code and one [65,4]-code. But there is no [65,20]-code at all.
27
3. CYCLIC CODES
Exercise 3.7
Consider the polynomial g{x) = x3
+ x + l. Show that there is a cyclic code C of length 8 over
F3 such that g{x) is its generator polynomial. Find the generator polynomial of the code C^.
Solution 3.7.1
All cyclic codes of length 8 over field F3 are generated by the factors of the polynomial x8
-- 1.
If the polynomial g{x) = x3
+ x + 1 is a factor of x8
-- 1 then it generates a [8, 5]-cyclic code.
First, we need to factorize the polynomial x8
-- 1: x8
-- 1 = (x + 1) (x -- 1) (x2
+ x -- 1) (x4
--
x3
-- x -- 1). We can see that there are two different [8, 5]-codes, there are their generator
polynomials:
* (x + l)(x2
+ x -- 1) = x3
-- x2
-- 1
* (x -- l)(x2
+ x -- 1) = x3
+ x + 1 = g(x)
Now it is obvious that g{x) generates a cyclic code of length 8 over F3. Since x8
-- 1 =
g{x)h{x), the check polynomial h(x) = (x + l){xA
-- x3
-- x -- 1) = x5
--x3
-- x2
+ x -- 1. Hence
the code C-1
is generated by the reciprocal polynomial /i(a;) = --x5
+ xA
-- x3
-- x2
+ 1.
Exercise 3.8
Decide correctness of the following statement. Prove your decision. Let C be a code.
(C-1
)1
- = C
Solution 3.8.1 by Lukáš Mojžíš
The statement is not generally correct. For example for code C = {01}, C1
- = {00,10} and
then(C
)
= {00,01}/C.
If C is a linear code then the statement is correct. We will show that if C C Fn
is a kdimensional
code and if C1
- C Fn
is its dual code and if G is a generator matrix for C. Then
C = (C-1
)-1
.
Let g : Fn
-->ˇ Fk
is a linear map defined by the k x n generator matrix G of code C.
Observe that a vector x G Fn
obeys g{x) = 0 if and only if it is orthogonal to each of the
rows of G; but the rows of G form a basis for C. Therefore g{x) = 0 if and only if a; G C-1
.
Thus C1
- = ker(g). Since the k rows of G are linearly independent, the map g has rank
k. By the Rank Nullity Theorem, the kernel has dimension n -- k, thus C1
- is an (n -- k)dimensional
code. Clearly C C (C-1
)-1
- since a vector 3; e C i s orthogonal to every vector
which is orthogonal to x; but C and (C-1
)1
- both have dimension k, hence C = (C-1
)-1
-.
Solution 3.8.2
This statement is true for linear and cyclic code.
First, let C be a q-ary linear [n, fc]-code with the generator matrix G and parity check
matrix H. Then the dual code D = C1
- is a linear [n, n --fc]-codewith the generator matrix
H = G' and the parity check matrix H'. Let v G V (n, q),v e D o- vGT
= 0. The dual code
E = D1
- is a [n,fc]-codewith generator matrix H' = G". Word w G E 4^ wG'T
= 0 4^ wHT
=
0.
28
3. CYCLIC CODES
We can easily see that if wH = 0 then w G C. Because w is a word from code E then
C = E = D
= (C-1
)-1
-.
Second, if C is a cyclic [n,fc]-codewith the generator polynomial g (x) of degree n -- k then
the check polynomial h(x) = ho + h\x + ˇ ˇ ˇ + hkXk
and we know that g{x)h{x) = xn
-- 1. We
also know that the dual code D = C1
- is generated by the polynomial h(x) = hk + hk-ix +
* ˇ ˇ + h\xk
~l
+ hoxk
. According to the proof of polynomial representation of dual codes we
know that h(x) = xk
h{x~l
) and h{x)g{x) = 1 -- xn
. That means that g(x) = f(x) is the
check polynomial (of degree n -- k) of code D. The dual code E = D1
- is generated by the
polynomial f(x). Since polynomial f(x) = /o + fix -\ h fn-kXn
~k
then polynomial f(x) =
fn_k+fn-k-ix-\ \-fixn
~k
~l
+f0xn
~k
. Since polynomial g(x) = g0+g\x-\ \-gn-kxn
~k
and
polynomial g(x) = gn_k+9n-k-ix^ Vg\xn
-k
-l
+g0xn
-k
= f(x) = fo+fix-\ Vfn-kxn
~k
we get /o = gn-k, /i = gn-k-i, ˇˇˇJn-k = 9o- And now, we can easily see that f(x) =
fn-k + fn-k-ix + ˇˇˇ + fixn
~k
-1
+ f0xn
-k
=g0+gix + -- ˇ + gn_k-ixn
~k
~1
+gn-kxn
~k
= g{x)
and that means that C = (g(x)) = (f (x)) = E = D1
- = (C-1
)-1
. What we had to show
29
Chapter 4
Secret Key Cryptography
Secret key cryptosystems are very old. They were primarily used in pre-computer era - secret
key cryptosystems are too weak nowadays and too easy to break, especially with computers.
However, they can illustrate several ideas of cryptography and cryptoanalysis.
4.1 Cryptosystem
Every cryptosystem consists of a plaintext space P (set of plaintexts over an alphabet E), a
cryptotext space C (set of cryptotexts over an alphabet A) and a key space K (set of possible
keys).
Each key k determines an encryption algorithm ek and a decryption algorithm dk such,
that for any plaintext w, ek(w) is the corresponding cryptotext and it holds
w G dk(ek(w)) or w = dk(ek(w))
As encryption algorithms we can also use randomized algorithms.
The philosophy of modern cryptoanalysis is embodied in the Kerckhoff's principle formulated
in 1983: The security of a cryptosystem must not depend on keeping secret the
encryption algorithm. The security should depend only on keeping secret the key.
The requirements for good cryptosystem according to Sir F. R. Bacon are:
1. Given ek end a plaintext w, it should be easy to compute c = ek(w).
2. Given dk end a cryptotext c, it should be easy to compute w = dk (c).
3. A cryptotext ek(w) should not be much longer then the plaintext w.
4. It should be unfeasible to determine w from ek(w) without knowing dk.
5. The so called avalanche effect should hold: A small change in the plaintext, or in the
key, should lead to a big change in the cryptotext.
6. The cryptosystem should not be closed under composition.
7. The set of keys should be very large.
4.2 Cryptoanalysis
The aim of cryptoanalysis is to get as much information about the plaintext or the key as
possible.
Main types of cryptoanalytics attacks are: cryptotexts-only attack, known-plaintexts attack,
chosen-plaintexts attack, known-encryption-algorithm attack and chosen-cryptotext at-
tack.
30
4. SECRET KEY CRYPTOGRAPHY
Cryptotexts-only attack: The cryptoanalysts get cryptotexts c\ = ek(w\),..., cn = ek(wn)
and try to infer the key k or as many of the plaintexts w\,... ,wnas possible.
Known-plaintexts attack: The cryptoanalysts know some pair Wi, ek(wi), 1 < i < n, and try
to infer key k, or at least the plaintext wn+i for a new cryptotext ek(wn+i)Chosen-plaintexts
attack: The cryptoanalysts choose plaintexts w\,... ,wn to get cryptotexts
efc(ioi),..., ek(wn), and try to infer key k or at least wn+\ for a new cryptotext
cn+i = ek(wn+i).
Known-encryption-algorithm attack: The encryption algorithm e^ is given and the cryptoanalysts
try to get the decryption algorithm dkChosen-cryptotext
attack: The cryptoanalysts know some pairs Cj, dfc(cj), 1 < i < n, where
the cryptotexts Cj have been chosen by the cryptoanalysts. The aim is to determine the
key k.
The basic cryptoanalytic attack against monoalphabetic substitution cryptosystems begins
with frequency analysis. Each letter in the cryptotext is counted and put into a table,
so we get the frequency counts for each letter. The distribution of letters in the cryptotext is
likely to be substituted for the letter with highest frequency in the plaintext language, etc.
The likelihood grows with the length of cryptotext. The frequency tables can be found in the
Internet.
4.3 Secret Key Cryptosystem
A cryptosystem is called secret key cryptosystem if some secret piece of information (the
key) has to be agreed first between any two parties that want to communicate through the
cryptosystem.
There are some basic types of secret key cryptosystems:
* substitution based cryptosystems - they substitute the characters of plaintext for another
characters;
- monoalphabetic cryptosystems - they use a fixed substitution, one character is
always replaced with the same group of symbols;
- polyalphabetic cryptosystems - the substitution keeps changing during the en-
cryption;
* transposition based cryptosystems - they only transpose the characters of plaintext,
for example p e r m i s s i o n / i m p r e s s i o n .
The cryptosystems can be also divided into block cryptosystems (cryptosystems that are
used to encrypt simultaneously blocks of plaintext) and into stream cryptosystems (cryptosystems
that encrypt plaintext letter by letter, the encryption may vary during the encryption
process).
Stream cryptosystems are more appropriate in some applications (telecommunication),
usually are simpler to implement, faster and have no error propagation. In stream cryptosystems
is each block of plaintext encrypted using a different key.
In block cryptosystems, the same key is used to encrypt arbitrarily long plaintext block
by block.
31
4. SECRET KEY CRYPTOGRAPHY
4.3.1 Caesar Cryptosystem
Caesar cryptosystem can be used to encrypt words in any alphabet. In order to encrypt
words in English alphabet, we use the key space K = {0,1,...,25}.
An encryption algorithm e^ substitutes any letter by the one occurring k positions ahead
(cyclically) in the alphabet. A decryption algorithm dk substitutes any letter by the one occurring
k positions backwards (cyclically) in the alphabet.
4.3.2 Polybious Cryptosystem
Polybious cryptosystem is designed for encryption of words in the English alphabet without
the letter J. The key space is formed by checkerboards of size 5 x 5 with English letters and
with columns and rows labeled by symbols.
An encryption algorithm substitutes each character by the pair of symbols denoting the
row and the column of the checkerboard in which the symbol is placed. The decryption
algorithm substitutes every two symbols denoting the row and the column of checkerboard
by the symbol that is found at these coordinates.
4.3.3 Hill Cryptosystem
In spite of the fact that Hill cryptosystem was probably never used, it played an important
role in the history of modern cryptography.
The key space are matrices M of degree n with elements from the set {0,1,..., 25} such
that M~l
mod 26 exists. All the possible plaintexts and cryptotexts are words of length n.
Any word w is represented by a column vector cw of length n of the symbols ofw. Encryption
of column vector cw is computed as cc = Mcw mod 26. Decryption of column vector cc is
computed M~l
cc mod 26.
4.3.4 Affine Cryptosystem
The Affine cipher is one of monoalphabetic substitution ciphers. The cryptosystem for an
alphabet of size m is given by two integers a and b such that a and m are coprime and b is
positive.
The encryption algorithm for letter x is e(x) = (ax + b) mod m, the decryption of received
letter y is d(y) = a~x
(y -- b) mod m, where a- 1
is the inverse of a in the group Zm.
4.3.5 Playfair Cryptosystem
The playfair cipher was used in World War I by British Army. The key is a playfair square of
size 5 x 5, or a word, or text in which repeated letters are removed and the remaining letters
of alphabet (except J) are added and divided to form an array.
Encryption of a pair of letters x, y is done as follows:
* If a; and y are in the same row (column), then they are replaced by the pair of symbols
to the right (below) of them.
* If a; and y are neither in the same row nor in the same column, then the smallest rectangle
containing x and y is taken and symbols x and y are replaced by the pair of symbols
in the remaining corners of the rectangle.
32
4. SECRET KEY CRYPTOGRAPHY
4.3.6 Vigenere and Autoclave Cryptosystems
Both Vigenere and Autoclave cryptosystem are polyalphabetic modifications of the Caesar
cryptosystem. The key k of these cryptosystems is as long as the plaintext w. Using the
Vigenere cryptosystem, a short key p is chosen and the key k is calculated as k = prefix\w\p*
(the prefix of length \w\ from the word p*). It is a cyclic version of Caesar cryptosystem. Using
the Autoclave cryptosystem, we also choose a short key p. The key k is then calculated as
k = prefix\w\pw.
4.3.7 One time pad Cryptosystem
One time pad is cryptosystem for encoding binary data using a binary key of the same length
as the data. If w is binary plaintext, k binary key and c binary cryptotext, then the encryption
algorithm e^ is c = ek(w) = w  k and the decryption algorithm dk is w = (4(c) = c  k.
4.4 Perfect Secret Cryptosystem
By Shannon, a cryptosystem is perfect if the knowledge of the cryptotext provides no information
about the plaintext (with the exception of its length). It follows from Shannon's result
that perfect secrecy is possible if and only if the key space is as large as the plaintext space.
In addition, the key has to be as long as the plaintext and the same key should not be used
twice.
A cryptosystem in which |P| = \K\ = \C\ provides perfect secrecy if and only if every
key is used with the same probability and for every plaintext w G P and cryptotext c e C
there is a unique key k e K such that ek{w) = c.
4.5 Exercises
Exercise 4.1
Decode the following cryptotexts:
1. TEVSECMKOCKB
2. TSRLNCHHIAFCIEISIEEPR
3. D Q L F < i > D : v r > n ^ r i i D E L r ^ n D r
4. (Playfair cipher, password: PLAYFAIR)
BKLBPGQXKGFQTNQOKU
Solution 4.1.1
1. This is a Caesar cryptosystem and every letter of the message is shifted by 10 positions
ahead. To decode the message we need to shift every letter of the cryptotext 16
positions ahead or 10 positions backwards. Using this algorithm we get the message
"Julius Caesar".
2. To decode this cryptotext is a bit harder. When we put the message into a table, in the
columns we can see the hidden message. The message is "This is rail fence cipher" as
you can see in the Table 4.1.
33
4. SECRET KEY CRYPTOGRAPHY
T S R L N C H
H I A F C I E
I S I E E P R
Table 4.1: Message hidden using the Rail Fence cipher
3. To decode this cryptotext we need the tables shown at the Figure 4.1.
J_ K L
M- N ˇ0
P' Q "R
A B C
D E F
G H I
Figure 4.1: Tables for encoding and decoding messages using Pigpen cipher
And the hidden message is "Encrypted with Pigpen cipher".
4. Decode this cryptotext is very easy because we know that it is encoded with Playfair
cipher and we also know the key. We just need to design the playfair square (see Table
4.2). The hidden message is "Charles Wheatstone x".
P L A Y F
I R B C D
E G H K M
N O Q S T
U V w X Z
Table 4.2: Playfair square for the keyword PLAYFAIR
Exercise 4.2
Consider the following variation of the one time pad cryptosystem. Let P = K = {00,01,10}ž
.
Encryption and decryption work in the same way as in the one time pad. Decide whether
this cipher is perfectly secure. Explain your reasoning.
Solution 4.2.1
A cipher is perfectly secure, if |P| = \K\ = \C\. But we can see that C = {00,01,10,11} and
therefore |P| = \K\ ^ \C\. Now, it is obvious that this cipher is not perfectly secure.
Exercise 4.3
You have found an old cryptotext and you know that the plaintext is related to cryptography.
You suppose Vigenere cryptosystem was used so you looked for repeated strings in the
cryptotext. You found that the string TICRMQUIRTJR occurs twice in the cryptotext. The
first occurrence begins at position 10 and the second one at position 241. You guess this
cryptotext sequence is the encryption of the plaintext word CRYPTOGRAPHY. If you are right,
what would be the key?
34
4. SECRET KEY CRYPTOGRAPHY
Solution 4.3.1
The key would be the word "CORRECT".
First, we need to guess the length of the keyword. We can see that the distance between
this two occurrences is 241 -- 10 = 231. To guess the length of the keyword, we need to find
the factors of 231 and we can see that 231 = 11 ˇ 21 = 11 ˇ 7 ˇ 3.
Second, we get the letters of the keyword using the Vigenere encrypting table. And we
get results that are shown in the table:
Position in the cryptotext 10 11 12 13 14 15 16 17 18 19 20 21
Cryptotext
Message
T
C
I
R
C
Y
R
P
M
T
Q
o
U
G
I
R
R
A
T
P
J
H
R
Y
Keyword R R E C T c O R R E C T
Now, we can see, that the length of the keyword is not 3 because there are more then
three letters in the keyword. The length of the keyword is not 11 either because the 10th
and 21st position of the keyword are different. Hence the length of the codeword must be
7 and we can see that the 10th and 17th position are equal and so on. Now we must find
the beginning of the repeated keyword. Because its length is seven, it starts at 1st, 8th, 15th,
22nd ... position of the cryptotext - and here we get the keyword "Correct".
There is also another possibility - the length of the keyword is more then 11 symbols. In
this case we are unable to say anything about the keyword.
Exercise 4.4
Alice used Vigenere cryptosystem for encryption but she has become afraid that it can be easily
broken. She is now considering using double encryption, that means sender and receiver
agree on two keywords keyi and key2 and sender encrypts message m by first encrypting it
with Vigenere cipher using the key keyi and then encrypting the resulting cryptotext with
Vigenere cipher using the key key2. Show that the proposed encryption has actually the same
effect as a single Vigenere encryption using a keyword key% and describe how to find this
keyword. What can you say about security of the double encryption?
Solution 4.4.1
Let efc be the encryption algorithm and let dk be the decryption algorithm described in the
materials (lecture 4, site 6, 7). Let w be the plaintext and keyi and key2 be the two given
keywords. We take w[i] as the ith letter of the message w, keyi[i'] as the i'th character of
keyword keyi where i' = i (mod \keyi\).
The algorithm for encrypting the message w is following:
C[i\ = ekey2li'](e
keyi[i'](w[i]))
where i  {1,.. .,\w\}. According to the encryption algorithm we get
c[i] = ekey2(w[i] + keyi[i']) (mod 26)
= (w[i] + keyi[i'} + key2[i"]) (mod 26)
= (w[i\ + key3[i'"]) (mod 26)
35
4. SECRET KEY CRYPTOGRAPHY
where keys[i'"} = key\[i'} + key2[i"} (mod 26) and i = i' = i" = i"' (mod \keys\).
Hence we can see that double Vigenere encryption using keywords key\ and fcej/2 has
the same effect as a single Vigenere encryption using the keyword keys- The length n of
the keyword keys is lcm{|fcq/i|, \key2\}- And keys[i] = {key\[i} + key2[i}) (mod 26) where
i G {1,..., n}. Using double Vigenere encryption can be more secure than single Vigenere
encryption only because of the length of keys'- \keys\ > max{|fceyi|, \key2\}.
But encryption using keys, which is dependent on keys key\ andfcej/2is less secure than
encryption using a randomly chosen key keyr with the same length as keysExercise
4.5
Enigma was a family of portable electromechanical rotor machines used to encrypt and decrypt
secret message during WorldWar II. Consider the following Enigma machine whose
key consists of
* initial position of three different exchangeable rotors, each rotor has 26 different posi-
tions;
* plugboard setting allowing six swaps of two different characters from 26-letter alpha-
bet.
1. How many different keys does this Enigma machine have?
2. What is the key length (in bits)?
3. What is the average complexity of an exhaustive key search?
Solution 4.5.1 by Lukáš Mojžíš
1. The number of rotor keys is 3! ˇ 263
. There is 3! because there is 6 different orders of
rotors.
The number of possible plugboard combinations according to number of cables is written
in the Table 4.3. The sum of the right column of the table is our result.
Number of swaps Number of combinations
0
1
2
3
4
5
6
U\6
)(\4
)(2
t)
U\6
)(\4
)(\2
)(\°)
Ämra (?)(?)(?)
Table 4.3: The count of possible combinations of plugboard settings
Hence, the total number of keys is
(3! ˇ 263
) ˇ (sum of right column of Table 4.3)
= (3! ˇ 263
) ˇ 1.05578918576 ˇ 1011
= 1.1133930437350656ˇ 1016
36
4. SECRET KEY CRYPTOGRAPHY
2. Keylengthis flog2(l. 1133930437350656-1016
)] = 54, i.e. 54 bits are necessary to encode
key.
3. Using exhaustive key search we need to check w \ ˇ 1.1 ˇ 1016
keys on average. The
complexity is therefore big.
Exercise 4.6
Find the key and decode the following ciphertext produced by Vigenere cryptosystem.
AjcrvqtvixmrgvlslkraykefqrlzsD4Mragocaskhym"Wuhtgmteoo",i
patvnihjwebijwjkgzuclthhrkpxlzs26cmxletusfsgdipdpcrijjwsj sf.
Tjkwwpqcchwdvj ifwsunsjaugggfrfxijavqv,jwouqrytjgpsedj irv
wtkxafukpidevvijkrfer.LhgUgzj szjqsxycwhdotmhgnvqtgxhymlfiioe
esqyqrwapfaskqfvrwcvghlghympsmrrefwz;kwmfsvcpdlvvxvanvgv,lzs
ciqhcqxij sbuipdlkillticjwzafvstwfvusnef.Dikarvamlsj crvabvaw,
atkotjgjvlshetcxagbrtwwcwtmlq:hymwagpcpgxtzkijnqnsfysipevtq
uiwlvvxpsipvipl,oj blwptkrlwfdqkztj czwtsvvmfsvcpdwrzvxze
ectlswe'agsbkpsxsgljqsrkpi,kghyixlhgumyfocasxfkeijvwublw
tarmfyoelowyj crvdweofmtpgzwj urqrwdmpsodsuoigfuggj whimgwixgh
hdozvxwxvkrxgfdixaop.
Crglvvzeucguwgjmniwlhgtieghvteeprcrwd.Wwblwmcelafsniwwqwkthwr
nqxzapgbljogirwl,vj iogcumruaugsxlvvMragocaskkzlij apfggmzu
axgrgvlwwlkzehapgp.Lzsimasscneehdrvidvgtwagbkpelcqwpvts
twrfeevivstkmvoatfw,tmhkpelrgsyaj su,ryktcuaalvkpiKcj tiatarf,
xzencqhhoempsnfnmyzhscptsvqfwj sdwzwd.Vjijwafbihapgpesrvqx
houumtdswwvspgtwgfhfzisdvj ivwqigtlefvipl,kzblguvimnabxblw
orgvs1c i igueuuxgah.
Zvi944,xzeNwjloownianvtsvmqvlefezvvshzlofgatfwoahtp,gslnghlzs
Lpv(ulqeo) .Lzsimasscnmllzvj sp,cqpxsabzvkssykxuzkzbl40
houkxagbj.Qxjerneuwrkpivehcydldcckk.Ahvijuceviutkpklzsgtyys,cu
hwlsiumfefkrlzsuimdymgckzsvb,xzeqrij shfzggunfxmjbkpikwkvgzab
fvigfvj i4Ohggzbmgnu,geuzdfamiiqpvwkicbmfgkpevatwmvwnv
esetweixaopqj hdixemj ipi.Qgkhfnxzeugtdmutwrfeevmgfoim,yflkmi
lzsumjsunvtdmuj,vslpckv-oagv.
Solution 4.6.1
To decrypt the text we use the Kasiski method and frequency analysis. For example, the sequence
LZSIMASSCN starts at 719th and at 1005th position; the sequence MRAGOCASK starts
at 30th and at 679th position; the sequence TWRFEEV starts at 755th position and at 1250th
position. The distances between their first and second occurrences are 286, 649 and 495. Because
gcd(286,649, 495) = 11 the length of the keyword is most likely eleven. Now, it is easy
to find that the keyword is "ACCESSORIES". And here is the hidden message:
A handy feature that was used on the M4 Enigma was the "Schreibmax", a
l i t t l e p r i n t e r which could p r i n t the 26 l e t t e r s on a small paper ribbon.
This excluded the need for a second operator, reading the lamps and
writing the l e t t e r s down. The Schreibmax was placed on top of the Enigma
machine and was connected to the lamp panel; to i n s t a l l the p r i n t e r , the
lamp cover and a l l l i g h t bulbs had to be removed. Besides i t s handiness,
i t improved operational s e c u r i t y : the signal officer no longer had to
37
4. SECRET KEY CRYPTOGRAPHY
see the plaintext, as the printer might have been installed in the
captain's cabin of a submarine, so that the signals officer did the
typing and keyhandling but never gained knowledge of secret received
plaintext information.
Another accessory was the remote lamp panel. If the machine was equipped
with an extra panel, the wooden case of the Enigma was wider and could
store the extra panel. There was a lamp panel version that could be
connected afterwards, but that required, just as with the Schreibmax,
the lamp panel and light bulbs to be removed. The remote panel made it
possible for a person to read the decrypted text, without giving the
operator access to it.
In 1944, the Luftwaffe introduced an extra plugboard switch, called the
uhr (clock). There was a little box, containing a switch with 40
positions. It replaced the default plugs. After connecting the plugs, as
determined in the daily key sheet,the operator could turn the switch in
one of the 40 positions, each position resulting in a different
combination of plug wiring. Most of these plug connection are, unlike
the default plugs, not pair-wise.
38
Chapter 5
Public Key Cryptography
The main disadvantage of the classical cryptography is the need to send a long key through
a absolutely secure channel before sending the message itself. In secret key (symmetric key)
cryptography both sender and receiver share the same secret key. In public key cryptography
there are two different keys - a public (encryption) key and a secret (decryption) key. The
basic idea is that if it is infeasible from the knowledge of encryption algorithm e^ to construct
the decryption algorithm dk then e^ can be made public.
5.1 Diffie-Hellman Key Exchange
The main problem of secret key cryptography is secure distribution of the key before transmission.
The problem was solved in 1976 by Diffie and Hellman. They designed a protocol
for secure key establishment over public channels.
If two parties, Alice and Bob, want to create a common secret key, then they first agree
on a large prime p and a primitive root q (mod p) and then they perform, through a public
channel, the following activities:
* Alice chooses randomly a large integer 1 < x < p -- 1 and computes X = qx
mod p.
* Bob also chooses randomly a large integer 1 < y < p -- 1 and computes Y = qy
mod p.
* Alice and Bob exchange X and Y through a public channel and keep x and y secret.
* Alice computes Yx
mod p and Bob computes Xy
mod p. Then each of them has the key
K = YX
mod p = Xy
mod p = qxy
mod p.
In order to determine x from X, p and q or y from Y, p and q, an eavesdropper seems to
have the capability to compute the discrete logarithms, what is believed to be infeasible.
5.2 Blom's Key Predistribution Protocol
Blom's protocol allows trusted authority (Trent) to distribute secret keys to \n(n -- 1) pairs
of n users. Let a large prime p > n be publically known. The protocol goes as follows:
* Each user U in the network is assigned by Trent a unique public number ru < P*
Trent chooses three random numbers a, b and c, smaller then p.
* For each user U Trent calculates two numbers ajj = {a + brjj) mod p and bu = (b +
cru) mod p and sends them via his secure channel to U.
* Each user U creates the polynomial gu(x) = au + b\jx.
39
5. PUBLIC KEY CRYPTOGRAPHY
* If Alice (A) wants to send a message to Bob (B), then Alice computes her key K AB =
9A{TB) and Bob computes his key KB A = 9B{TA)*
It is easy to see that K AB = KB A and therefore Alice and Bob can now use their keys
to communicate using some secret key cryptosystem.
5.3 Cryptography and Computational Complexity
Modern cryptography uses such encryption methods that no enemy can have enough computational
power and time to do decryption. Modern cryptography is based on positive and
negative results of complexity theory - on the fact that for some algorithm problems no efficient
algorithm seem to exist, and for some small modifications of these problems there is a
simple, fast and good enough (randomized) algorithm.
Integer factorization Given n = pq, the task to find p, q is infeasible.
Prime recognition Is a given n prime? There is a fast randomized algorithm.
Discrete logarithm problem Given x, y, n, the task to compute a such that y = xa
(mod n)
is infeasible.
Discrete square root problem Given y, n, the task to compute x such that y = x2
(mod n)
is infeasible in general, but easy if n is a prime.
5.4 RSA Cryptosystem
The most important public key cryptosystem is the RSA cryptosystem. It was invented in
1978 by Rivest, Shamir and Adleman. The basic idea is that prime multiplication is very
easy but integer factorization seems to be infeasible. To design a RSA cryptosystem we need
to choose two large primes p and q and compute n = pq. Then choose a large d such that
gcd(d, <f(n)) = 1, where if is Euler's function, and compute e = d~l
(mod <p(ri)).
The public key is modulus n and encryption integer e. The private key is p, q and decryption
integer d. The plaintext is first encoded as a word over alphabet {0,1,..., 9}, then
divided into blocks of length i -- 1 where 10t_1
< n < 10\ Each block is then taken as an
integer and encrypted. The encryption of a plaintext w is the cryptotext c = we
mod n. The
decryption of a cryptotext c is the plaintext w = cd
mod n.
5.5 Rabin-Miller's Prime Recognition
One of the key problems for the development of RSA cryptosystem is the prime recognition.
Rabin-Miller's prime recognition algorithm is based on the following result of number
theory.
Let n G N, for 1 < x < n, C (x) denotes the following condition: "Either xn
~x
/ 1
(mod n) or there is an m = ,ß
=r- for some i, such that gcd(n, xm
-- 1) / 1". If C(x) holds for
some 1 < x < n, then n is not a prime. If n is not a prime, then C(x) holds for at least half of
x between 1 and n.
The algorithm goes as follows:
* Choose randomly integers x\,X2, ˇ ˇ ˇ, xm such that 1 < Xi < n
40
5. PUBLIC KEY CRYPTOGRAPHY
* For each Xi determine whether C(x) holds.
* If C(xi) holds for some Xi then n is not a prime for sure. Otherwise n is prime with the
probability of error 2~m
.
5.6 Exercises
Exercise 5.1
1. Compute 7120007
mod 143 by hand. (Use Chinese Remainder Theorem and Fermaťs
Little Theorem.)
2. Let n be any integer. Show that n5
-- n is divisible by 30.
Solution 5.1.1
1. First, using Fermaťs Little Theorem and modular exponentiation we get:
7120007 m o d n = 7 77 120000 m o d n = 7 7 ( 7 1 0 m o d n ) 12000 m o d n
= 77
l12000
mod 11 = 77
mod 11 = 6
7120007 m o d 1 3 = 7 77 120000 m o d ^ = 7 7 ( 7 1 2 m o d ^ 10000 m o d ^
= 77
l10000
mod 13 = 77
mod 13 = 6
Let a; be a number such that x = 7120007
(mod 143). Then we have two congruences:
x = 6 (mod 11)
x = 6 (mod 13)
From Chinese Reminder Theorem we know that if x = y (mod a) and x = y (mod b)
then x = y (mod ab). Hence we have 7120007
= 6 (mod 143).
2. We know, that n5
-- n is divisible by 30 only if n5
-- n is divisible by 2, 3 and 5 (its
factors). But we have: n5
--n = n(rr -- 1) = n(n2
-- l)(n2
+ 1) = n(n -- l)(n + l)(n2
+ l).
Now it is easy to see that
n5
-- n is divisible by 2: if n = 0 (mod 2) then n is divisible by 2, else if n = 1 (mod 2)
then n -- 1 is divisible by 2.
n5
-- n is divisible by 3: if n = 0 (mod 3) then n is divisible by 3, else if n = 1 (mod 3)
then n -- 1 is divisible by 3, else if n = 2 (mod 3) then n + 1 is divisible by 3.
n5
-- n is divisible by 5: if n = 0 (mod 5) then n is divisible by 5, else if n = 1 (mod 5)
then n -- 1 is divisible by 5, else if n = 4 (mod 5) then n + 1 is divisible by 5.
Now, we need to get factors of n5
-- n in Zsfn] and these are: n5
-- n = n(n -- l)(n +
1) (n -- 2) (n + 2). And here we can see that if n = 2 (mod 5) then n -- 2 is divisible
by 5 and if n = 3 (mod 5) then n + 2 is divisible by 5.
Hence n5
-- n is divisible by 30.
41
5. PUBLIC KEY CRYPTOGRAPHY
Exercise 5.2
Alice and Bob computed a secret key k using Diffe-Hellman protocol with p = 467, q = 4,
x = 400 and y = 134. Later they computed another secret key k! with the same p, q, y and
with x' = 167. They became very surprised after finding that k = k! . Determine the value of
both keys and explain why the keys are identical.
Solution 5.2.1
The secret key k is computed as k = qxy
mod p. For the values p = 467, q = 4, x = 400 and
y = 134 we have k = 161. When we get the same value of secret key after choosing another
x, say x' = 167, it means that qxy
mod p = k = k' = qxy
mod p.
Euler's Totient Theorem says that rď^ = 1 (mod m). Iťs corollary is that ^M+fc = n
k
(mod m). According to this theorem and corollary we have k = qxy
mod p = ql
f(m)+k m o c |
p = qk
mod p = qi(m)+km o c [ p = qx
y m o d p = k'. Because p is a prime Lp(p) = p -- 1 and we
can see that xy = x'y (mod p -- 1): xy = 400 ˇ 134 = 10 (mod 466) and x'y = 167 ˇ 134 = 10
(mod 466).
Now it is easy to see that k = 4^(467
)+10
mod 467 = 410
mod 467 = 161 = k'.
Exercise 5.3
To simplify the implementation of Diffe-Hellman protocol one replaces the multiplicative
group (Z*, ˇ) by the additive group (Zp, +). How is security affected?
Solution 5.3.1
The Diffie-Hellman protocol is secure because it is infeasible to compute discrete logarithm.
When we replace the multiplicative group (Z*, ˇ) by the additive group (Zp, +), we do not
need to compute the discrete logarithm, we just need to compute the inverse elements in
group (Zp, +) which is easy. That means that this simplified Diffie-Hellman protocol is not
secure.
In the Table 5.1 we can see the run of modified Diffie-Hellman protocol and also what
Alice, Bob and Eve knows. At the end of the key exchange protocol Eve doesn't know the
Alice Bob Eve
prime p, base q
X
qx mod p
qy mod p
k = qxy mod p
prime p, base q
y
qx mod p
qy mod p
k = qxy mod p
prime p, base q
doesn't know x nor y
qx mod p
qy mod p
doesn't know secret key k
Table 5.1: The design of the run of modified Diffie-Hellmann key exchange protocol
secret key, but it is easy for her to compute q~x
mod p such that q~x
q = 1 (mod p). She also
knows that qk = qxqy mod p. Here she gets k = q~x
qk = q~x
qxqy mod p = qxy mod p.
42
5. PUBLIC KEY CRYPTOGRAPHY
Exercise 5.4
Consider RSA cryptosystem. Is it possible to decrypt a ciphertext by repeated encryption of
the ciphertext?
Solution 5.4.1 by Martin Vejnár
The RSA cryptosystem is based on the fact that med
= m (mod n), where e, coprime of
<f(n), is a multiplicative inverse of d. Since e is a coprime of <p(ri), the Euler's theorem can be
applied to get
ď(<p(n)) = eď(<p(n))-l = x (m o d y^y
Using the Fermaťs little theorem we get
ip(ip(n))-l ip(ip(n))-l ,
m = c = m (mod n).
Now it is obvious that a cryptotext can be decoded by encrypting the cryptotext <p(<p(ri)) -- 1
times.
Exercise 5.5
Consider the following modification of RSA cryptosystem.
Public key is a pair (n = pq, e) which is defined in the same way as in the standard RSA.
Private key is a quintuple (p, q, dp, dq, qinv) where dv = e_ 1
mod p -- 1, dq = e_ 1
mod q -- 1
and qinv = q~l
mod p. Message m is encrypted by computing c = me
mod n. Decryption is
realized by computing numbers mp = cdp
mod p,mq = cdq
mod q and h = qínv{Tnp--mq) mod
p from which the original message m = mq + hq can be reconstructed. Show correctness of
the described cryptosystem.
Solution 5.5.1
In plain RSA it holds that m = cd
(mod n). We can see that dp = d mod p -- 1 and dq =
d mod q -- I. Since
w = cd
= cd mod p
-l
= cd
" (mod p) and
w = cd
= cd mod q
~l
= cd
" (mod q)
we can see that
m = med
= cd
= cdp
= mp (mod p) and
m = med
= cd
= cdq
= mq (mod q).
Now, we need to show that message m! = mq + hq is the original message. To do that we
need to verify whether m! = mp (mod p) and m! = mq (mod q). We can easily see that
m' = mq + hq = mq (mod q).
To show that m! = mp (mod p) we will start with mp -- mq = mp -- mq (mod p). Because
qqinv = 1 (mod p), we get
qinv(mp - mq) q = mp-mq (mod p)
v
v '
h
m' = mq + hq = mp (mod p).
43
5. PUBLIC KEY CRYPTOGRAPHY
Because \m\ < pq, m' = m (mod p) and m' = m (mod q) it must hold that m = m' and
hence the modified cryptosystem is correct.
Exercise 5.6
We want to set up RSA cryptosystem in a network of n users.
1. How many prime numbers do we have to generate?
2. Now consider we want to reduce this number by generating a smaller pool of prime
numbers and making combinations of two of these primes (for each user we pick up a
new pair). How is security of RSA cryptosystem affected?
Solution 5.6.1
1. We need two primes for each user, so we need to generate In prime numbers.
2. When there is only k prime numbers, we can calculate gcd(ni,rij) where rii, rij are
public keys of some users Ui and Uj of the network. When gcd(rii, rij) = x > 1, we can
compute such y and y' that xy = rii and xy' = rij. Because e and ej are known, we can
also compute di and dj .
Now, we know the private keys of users Ui and Uj of the network and we can read
messages addressed to them. This cryptosystem is not secure.
44
Chapter 6
Other Public Key Cryptosystems
6.1 Rabin Cryptosystem
Rabin cryptosystem is based on the discrete square root problem. To design Rabin cryptosystem,
we need to find two primes p and q of the form 4k + 3 (i.e. p = q = 3 (mod 4)). The
public key is number n = pq, primes p and q are kept secret. We can see that n is a Blum
integer what is important because of its nice properties.
The encryption of plaintext w < n is the cryptotext c = w2
mod n. The decryption of
cryptotext c is done when all square roots of c modulo n are found. Because n is a Blum
p+l p+l q+l q+1
integer, we can see that w e {c 4 mod n, p -- c 4 mod n, c 4 mod n, q -- c 4 mod n}. In
case the plaintext w is a meaningful text, it should be easy to determine the value of w.
However, if w is a random string, for example a secret key, it is impossible to determine the
value of w.
6.2 ElGamal Cryptosystem
To design ElGamal cryptosystem, we need to choose a large prime p, a primitive element
q of the group Z* and a random integer x such that 1 < x < p. Then we need to calculate
y = qx
mod p. The public key consists of numbers p, q and y. Number x is kept secret for
message decryption.
To encrypt a plaintext w G Z* we need to choose a random integer r and compute a =
qr
mod p and b = yr
w mod p. The cryptotext c = (a, b). To decrypt a cryptotext, we need
to calculate -^ mod p = ba~x
mod p = w. The security of ElGamal cryptosystem is based
on the discrete logarithm problem. As we can see, the cryptosystem is not secure under a
chosen cryptotext attack - for an encryption c = (a, b) of message m we can easy construct
an encryption d = (a, 26) of message 2m.
6.3 Exercises
Exercise 6.1
Show that with a chosen-ciphertext attack on RSA cryptosystem one can decrypt an arbitrary
ciphertext with only one query.
Solution 6.1.1 by Libor Caha
A chosen-ciphertext attack is an attack in cryptoanalysis in which the cryptoanalyst chooses
a ciphertext and let it decrypt. From some pairs of ciphertexts and decrypted ciphertexts the
cryptoanalyst wants to know some information about the key or about the messages sent.
45
6. OTHER PUBLIC KEY CRYPTOSYSTEMS
Our task is to decrypt an arbitrary ciphertext c using the chosen-ciphertext attack. Say the
ciphertext c was sent to Alice, whose public key is (n, e).
We need to choose a random integer r G Z*n and compute d = re
c mod n where e is
Alice's public key. We send d to Alice and she sends back d(d) = dd
mod n. Because dd
mod
n = red
cd
mod n = rw mod n we have the message we are looking for multiplied by r. To
get our message w, we need to calculate r~l
dd
mod n = r~l
rw mod n = w.
Exercise 6.2
What is the probability that two students of IV054 have the same birthday (74 students attend
IV054 course at this moment)?
Solution 6.2.1
Let p{n) be the probability that two out of n students of IV054 have the same birthday.
Let p{n) = 1 -- p{n) be the probability that no two students have the same birthday. Then
the probability p{n) is computed this as p{n) = 1 -- p{n). The probability p{n) is computed as
follows:
365(365 - 1 ) ˇˇˇ(365 - n + 1) 365!
V
^n
' ~ 365TM ~ 365ra
(365-n)!
365!
For n = 74 we have p(74) = 3 6 5 74( 3 6 5 _ 7 4 ) , ~ 0,00035 and p(74) = 1 - p(74)  1 0,00035
w 0,99965.
The probability that two students of IV054 have the same birthday is greater than 99,9%,
although it cannot be 100% unless there are at least 365 people attending the course.
Exercise 6.3
Prove or disprove the following implication. Let g, h be generators of the group (Z*, ˇ) where
p is an odd prime. Suppose g2u
= h2v
(mod p). Then gu
= hv
(mod p).
Solution 6.3.1
The condition is not true. We can choose the prime p = 7, then we can see that the group
(Zj, ˇ) has two generators g = 3 and h = 5. When choosing u = 1 and v = 2 we get:
g2u
= 32
= 2 (mod 7) h2v
= 54
= 2 (mod 7)
gu
= 31
= 3 (mod 7) hv
= 52
= 4 (mod 7)
We can see that g2u
= h2v
(mod 7) but gu
^ hv
(mod 7).
Exercise 6.4
Let p be a large prime, g a generator of the group (Z*, ˇ) and y = gx
mod p. Show that it is
possible to find the least significant bit of x by computing y 2 mod p.
46
6. OTHER PUBLIC KEY CRYPTOSYSTEMS
Solution 6.4.1 by Libor Caha
To find the least significant bit of x is equal to find the parity of x. Because g is a generator
P--i
of group (Z*, ˇ) then Z* = g%
for 1 < i < p -- 1. The expression y^r mod p can be rewrite as
g 2 mod p (using the Euler's Totient Theorem). Now, we need to discuss two cases:
p -- 1 xtp(p) 2kip(p)
x = 2k: If x is even then the least significant bit is 0. We can see that y^~ = g^^ = g 2
=
gk<p(p) = I (mOCl py
p--1 Xif(p)
x = 2k + 1: If a; is odd then the least significant bit is 1. We can see that y^~ = g 2 =
(2fc+l)y(p) , / s y(p)
g 2 = gľfWg 2 ^ 1 (mod p) because g is the generator of group Z*.
p--1
We can say that if y^~ = 1 (mod p) then x is even.
Exercise 6.5
Show that Rabin cryptosystem is vulnerable to a chosen-ciphertext attack.
Solution 6.5.1 by Lukáš Mojžíš
Suppose that V is any algorithm that computes one plaintext (of the four possible plaintexts)
corresponding to a valid cryptotext y. We choose a random i e Z * and compute y = x2
mod
n. Now we need to compute x1
= V(y) and we get x2
= x'2
(mod n). The probability that
x = x' (mod n) is0,5. In this case we have a;2
--a;'2
= (x--x')(x+x') = 0 (mod n)butneither
factor is equal to 0 modulo n. Therefore, gcd((a? -- x'),n) = p or q and the factorization of n is
obtained. After two attempts (on average) n is factored. Therefore any decryption algorithm
can be used to factor n efficiently.
After factoring n we can decipher any ciphertext using normal decoding strategy of Rabin
cryptosystem.
Exercise 6.6
Let p be a 1024-bit prime. Let g have order q in (Z*, ˇ), where q is a 160-bit prime. Consider
the following modification of ElGamal cryptosystem. Private key a; is a randomly chosen
element of {1,... ,q -- 1}. Public key is y = gx
mod p. Message m is encrypted by computing
pair
c = (gr
mod p, yr
gm
mod p),
where r is a randomly chosen integer.
1. Suppose you know factorization of p -- 1. Show a method of finding g G {0,..., p -- 1}
of order q.
2. How can the receiver compute gm
mod p from c?
3. Computing discrete logarithms is hard in (Z*, ˇ). In general, the receiver is not able
to recover m from gm
mod p. Assume the sender only sends messages from the set
{0,..., 100}. Show that the receiver can recover m.
47
6. OTHER PUBLIC KEY CRYPTOSYSTEMS
4. Suppose c\ = (gT1
mod p, yT1
gmi
mod p) is a cryptotext for some unknown message
mi and similarly c2 = (gT2
mod p, yT2
gm2
mod p) is a cryptotext for some unknown
message m2. Find a cryptotext c for a message m' = m\ + ÍÍÍ2 mod g using c\ and c2.
5. Suppose the receiver is conducting an auction in which two bidders encrypt their bids
using the scheme described above. Suppose also that both bidders can bid at most
$100. The bidder who goes second can eavesdrop messages between the receiver and
the first bidder. Show that he can almost always bid $1 more than the first bidder (even
without knowing the value of his bid).
Solution 6.6.1
1. Because q is a prime and it is order of some element of Z* then q must be a factor of
p -- 1 because every order of some group element divides the size of the group. To get
any element of order q we randomly choose a number x from 1 to p -- 1 and when it
holds xq
= 1 (mod p) then x might be g. There is more elements of order q, not only g.
Because q is a prime we don't need to check whether it has a smaller order - there are
no factors of q.
2. Let c = (a, b) where a = gr
mod p and b = yr
gm
mod p. Then
= gmy g g g
QTX QTX
Because a is an element of a group, there must be some inverse a l
in the group and
this element and multiplication is used instead of a and division.
3. Because the set M = {1,..., 100} is finite, we can calculate the values of ga
for each
a G M in a finite time. We save our results in a table as a couple (ga
, a). Then we can
easily search the table for a gm
and find the appropriate m.
4. Let d be the cryptotext for message m! = m\ + m2 mod q and let c be the cryptotext
for message m, then d = c\ ˇ c2:
d = {gs
mod p, ys
gm
^+m
* mod
9 mod p)
= (gri+r2
modp,yri+r2
gmi+m2
mod p) =
= (gT1
gT2
mod p, yri
gmi
yr2
gm2
modp) =
= (ai ˇ a2,6i ˇ b2) = {a\,h) ˇ (a2,b2) =
= ci ˇ c2.
This is correct because T\, r2 are random numbers so as s and gmi
+m2
= gm
i+m
2 mod q
(mod p) because m\ + m2 = kq + I and (mi + m2) mod q = I we get gk
i+l
= gk
igl
= gl
because q is the order of g.
5. The second bidder needs to calculate c\ for message m\ = 1. When he eavesdrops the
encrypted bid bi he just calculates c\ ˇ bi and sends it to the auctioneer. He bids $1 more
than the first bidder except for the case that the first bidder bids $100. In this case, the
second bid is not valid.
48
Chapter 7
Digital Signature
Digital signatures are one of the most important applications of modern cryptography Digital
signatures are such that each user is able to verify signatures of other users, but that gives
him no information about how to sign a message on behind of other users.
An important difference from handwritten signature is that digital signature of a message
is intimately connected with the message and for different messages is different, whereas the
handwritten signature is adjoint to the message and always looks the same.
Technically, a digital signature is performed by a signing algorithm and it is verified by
a verification algorithm. It can be used any public key cryptosystem in which the plaintext
space and cryptotext space are the same.
The signature of message w denoted as sig(w) is djj{w) so as everyone can verify that the
message was sent by user U. If the signature is important only for user V, then the signature
is computed as ev(du(w)). Now, only user V can verify, that the message was signed by user
U.
7.1 Digital Signature Scheme
Digital signature allows anyone to verify signature of sender S without providing any information
about generating signatures of S.
A digital signature scheme (M, S, KS,KV) is given by a set of messages to be signed (M),
a set of possible signatures (S), a set of private keys for signing (Ks) and a set of public keys
for verification (Kv).
It is required, that for each key k from Ks, there exists a single and easy to compute
signing mapping sigh : {0,1}* x M -->ˇ S, and for each key k from Kv, there exists a single
and easy to compute verifícation mapping verk : M x S -->ˇ {true, false} such that the
following conditions are satisfied:
Correctness: For a message m G M and public key k G Kv, it holds ver^m, s) = true if
there is an r G {0,1}* such that s = sigi(r, m) for a private key l G Ks corresponding
to the public key k.
Security: For any w G M and k G Kv, it is computationally infeasible, without the knowledge
of the private key corresponding to k, to find a signature s G S such that verk(w, s) =
true.
7.2 Attacks on Digital Signature
There are several types of attack on digital signature schemes:
Total break: The adversary manages to recover secret key from the public key.
49
7. DIGITAL SIGNATURE
Universal forgery: The adversary can derive from the public key an algorithm which allows
him to forge signature of any message.
Selective forgery: The adversary can derive from the public key a method to forge signatures
of selected messages (where the selection was made prior the knowledge of the
public key).
Existential forgery: The adversary is able to create from the public key a valid signature of
some message m (but has no control for which m).
7.3 RSA Signatures
Let us have an RSA cryptosystem with encryption and decryption exponents e and d. The
signature of message w is a couple s = (w,a) where a = wd
mod n. The signature s is valid
if <7e
= w mod n.
There are some known attacks on this scheme. The forger can use some public key e
to compute we
, the signature of this message is s = (we
,w). Everybody, who verifies the
signature, finds out that the signature is valid. The forger has no control over the content of
the message we
- it is an example of existential forgery.
Another attacker can produce some new valid signatures without the knowledge of secret
key - when he obtains signatures s\ = (w\,ai) and S2 = (W2,(T2), he can compute
valid signatures of messages w\W2 and toj-1
. The signatures are su = (101102,0TC2) and
s' = (wfVf1
).
7.4 ElGamal Signatures
The public key for ElGamal signature scheme is K = (p, q, y) where p is a prime, q is a
primitive element of Z* and y = qx
mod p. The integer 1 < x < p is secret key and is used
for signing messages.
To create the signature s of a message m we need to choose a random integer r e Z*_ 1.
The signature s = sig(m, r) = (a, b) where a = qr
mod p and b = (m -- ax)r~l
mod p -- 1.
The signature s = (a, b) of message m is valid if ya
ab
= qw
(mod p).
There are ways of producing (using ElGamal signature scheme) valid forged signatures,
but they do not allow the forger to create signature of message of his choice (see Exercise
7.1). There are also several ways of breaking the ElGamal signatures if these schemes are
used not carefully enough. If the random integer r of some signature is known, the forger
can compute the secret key x and then forge signatures at will. Another misuse of ElGamal
signature scheme is to use the same r to sign two messages. In such a case the secret key x
can be computed.
7.5 Digital Signature Algorithm
Digital Signature Algorithm (DSA) was accepted in 1994 as a standard.
The key for DSA is K = (p, q, r, x, y), where p is a large prime, q is a prime dividing p -- l,
p-i
r > 1 is a qth root of 1 in Zp (r = h t mod p where h is a primitive element in Zp), a; is a
random integer such that 0 < x < q and y = rx
mod p. The components of public key are p,
q and r; integers x and y are kept secret.
50
7. DIGITAL SIGNATURE
To sign a message w we need to choose a random integer k such that 0 < k < q and
gcd(k,q) = 1. The signature of message w is s = sig(w,k) = (a,b), where a = (rk
mod
p) mod q and b = k~1
{w + a;a) mod g, where kk~x
= 1 (mod <?). The signature s = (a, b) is
valid if (rUl
yU2
mod p) mod q = a, where u\ = wz mod g, 2 = az mod g and z = b~x
mod g.
7.6 Ong-Schnorr-Shamir Subliminal Channel Scheme
A subliminal channel is a covert communication channel among a set of users, such that
everybody can see their common messages, without any secret information. The top secret
message is hidden in the sent message and its signature.
To set up a subliminal channel, the users need to choose a large n and an integer k such
that gcd(fc, n) = 1. The public key is a couple (n, h), where h = k~2
mod n = (k~1
)2
mod n.
The secret key for all subliminal channel users is k.
When some user wants to send a secret message w, he needs to choose another harmless
message w'. The messages have to be such that gcd(w, n) = 1 and gcd(/, n) = 1. The
signature of those messages is s = (Si, S2), where
1
íw
' \
61 = \-w) mod n and
2\w J
Q k fw' \
62 = -- w ) mod n.
2\w J
The signature s is for everybody just a signature of message /, for the subliminal channel
users are the message w' and its signature s only numbers needed to get the hidden message
w.
The signature of message w' is valid if Sf -- hS^ mod n = w'. The hidden message w can
be obtained by computing w'(Si + fc-1
^)-1
mod n.
7.7 Lamport Signature Scheme
Lamport signature scheme shows how to construct a signature scheme for only one use from
any one way function. This signature cannot be forged because we are unable to invert the
one way function. On the other hand, Lamport signature scheme can be used to sign only
one message.
Let k be a positive integer and let P = {0, l}k
be the set of messages. Let / : Y --> Z be a
one way function where F is a set of partial signatures. Y = {ijijli < i < k,j = 0,1}, where
yij is chosen randomly and Z = {ZÍJ\ZÍJ = f(yij)}- The key K consists of /, Y and Z - Y is
the secret key; / and Z are public.
The signature of message x G P is s = sig(xi... xk) = (yixi, ˇ ˇ ˇ > Vkxk)- The signature
s is denoted as (ai,..., ak). The signature s of message x is valid if f(a,i) = ZiXi for each
ie {l,...,k}.
7.8 Exercises
Exercise 7.1
Consider the DSA signature scheme. Show that is possible to recover the secret key in the
following situations.
51
7. DIGITAL SIGNATURE
1. A signer has precomputed one pair k, a with a = (rk
mod q) mod p and always uses
this pair to sign his messages.
2. A signer creates a signature (a, 0) for some message w.
Solution 7.1.1
1. When we eavesdrop two messages w\ and 102 and their signatures (a, 61) and (a, 62)
sent by the signer, we can calculate the value of k - one of the secret keys. Suppose that
b\ > 62 and kk~l
= 1 (mod q), then we have:
b\ = k~l
(w\ + xa) mod q
62 = k~l
(w2 + xa) mod q
b\ -- 62 = k~l
(w\ + xa) -- k~l
(ui2 + xa) mod g
fc(6i -- 62) = wi + ^a -- W2 -- xa = w\ -- W2 mod q
k = {w\ -- W2){b\ -- &2)_1
mod q
where (61 -- 62) (&i -- fo)-1
= 1 (mod q). Because q is a prime and 0 < b\ -- 62 < b\ < q
we know that gcd(6i --62, q) = 1- Hence we can calculate (61 -- fe)-1
using the Extended
Euclidean algorithm and the Bezouťs identity.
With the knowledge of the value of k we can recover x:
b\ = k~l
(w\ + xa) mod q
kb1 = w\ + xa mod q
kb1 --w\=xa mod q
x = {kb\ -- w\)a~l
mod q
where aar1
= 1 (mod q). The value of a- 1
can be calculated the same way as described
above. Now, we know the value of the secret key x and we can send messages
pretending to be someone else.
2. When we sent a message w with signature (a, 0), anybody can compute the value of
our secret key x:
0 = b = k~l
(w + xa) mod q
k0 = 0 = w + xa mod q
xa = --w mod q
x = --wa~l
mod q
where aar1
= 1 (mod q). Whoever did this calculation, can now send messages with
our signature.
Exercise 7.2
Consider the ElGamal digital signature scheme. A valid signature pair (a, b) for a random
message w can be constructed as follows:
a = qt
y3
mod p,
b = --aj~ľ
mod (p -- 1),
w = --aij~l
mod (p -- 1),
52
7. DIGITAL SIGNATURE
for 0 < i, j < p -- 2 and gcd(j,p -- 1) = 1.
1. Let p = 1367, q = 5 be the generator of Z* and y = 307 be the public key. Using
the construction described above find a signature and the corresponding message for
parameters i, j of your choice. Show derivation steps for equations for a, b and w.
Verify this signature.
2. How can we prevent this attack on ElGamal signature scheme?
Solution 7.2.1
1. We can choose for example i = 10 and j = 3. First we need to calculate j _ 1
such that
jj~l
= 1 (mod p -- 1). From Extended Euclidean algorithm we have 1366 = 3 ˇ 455 + 1,
that means that 1 = 1366 -- 3 ˇ 455. Here we get 1 = 3- (--455) (mod 1366), hence
j ' 1
= -455 = 911 (mod 1366).
Now, we can calculate a, b and w.
a = qi
yj
mod p = 510
3073
mod 1367 = 12
b = --aj~l
mod (p -- 1) = --12 ˇ 911 mod 1366
= -4(3 ˇ 911) mod 1366 = - 4 mod 1366 = 1362
w = --aij~l
mod (p -- 1) = bi mod (p -- 1) = 1362 ˇ 10 mod 1366
= - 4 ˇ 10 mod 1366 = -40 mod 1366 = 1326
The signature (a, b) of message w is valid if ya
ab
= qw
(mod p). And we can see that
va
ab
= va
a~a:
'1 mod
(p_1
) = ya
q~ai:
>~1 mod
(p-l
)y-a
J3^1 mod
(P_1
)
= ya
~a
n~ai:
> 1 m o d
( P _ 1
) = QW
And we really get
ya
ab
mod p = 30712
* 121362
mod 1367 = 1097
qw
mod p = 51326
mod 1367 = 1097
2. This forgery attack can be prevented by signing only the hash of the message. The
forger can determine the signature only for a random messages - he can never sign
any message of his choice, provided the security wasn't broken.
Exercise 7.3
Consider the RSA signature scheme with the public key (n = 9797, e = 131). Decide whether
the following signatures are valid.
1. w = 123, sig{w) = 6292
2. w = 4337, sig(w) = 4768
3. w = 4333, sig(w) = 1424
53
7. DIGITAL SIGNATURE
Solution 7.3.1
The signature of message w using RSA signature scheme is sig(w) = wd
mod n. We can verify
the signature by calculating sig(w)e
mod n. The signature is valid if sig(w)e
= w (mod n).
The couple (n, e) is the public key.
1. Let w = 123 be the message and sigiw) = 6292 its signature.
Because 6292131
mod 9797 = 123 the signature is valid.
2. Let w = 4337 be the message and sig(w) = 4768 its signature.
Because 4768131
mod 9797 = 9644 the signature is not valid.
3. Let w = 4333 be the message and sig(w) = 1424 its signature.
Because 1424131
mod 9797 = 4333 the signature is valid.
Exercise 7.4
Consider the following signature scheme. Alice chooses two large secret primes p, q and
computes their product n. She also chooses an element g e {0,..., n -- 1} such that g generates
a subgroup of order r in (Z, ˇ), where r is a large prime.
Alice's public key is a pair (n, g), her private key is a number r.
To sign a message m, Alice finds x such that xm = 1 (mod r). Then she computes the
signature s = gx
(mod n). Suppose Bob has received a pair (m, s) from Alice.
1. How is Bob able to verify her signature?
2. Show that r is a factor of at least one of numbers p -- 1, q -- 1.
3. Show that if r is a factor of exactly one of these numbers then one can factor n using
only a public key.
Solution 7.4.1
1. When Bob receives couple (m, s) from Alice, he calculates
sm = gxm = gkr+l = gkrg = g ( m o d ^
This is correct since gr
= 1 (mod n). Therefore, Alice's signature is valid if sm
= g.
2. The size of group (Z*, ˇ) is |Z* | = ip(ri) = (p -- l)(q -- 1). Let a be an element from Z*,
let k be the order of a then k divides |Z| thus k divides (p -- l)(q -- l).In our case k = r
and r is a prime. That means that r divides (p -- 1) or r divides (q -- 1). In other words
r is factor of at least one of numbers (j> -- 1), (q -- 1).
3. Suppose, r divides q -- 1 and does not divide p -- 1. Because gr
mod n = 1 it must also
hold that gr
mod p = 1. Since r is a prime, we can see that the order of g in Z* is r or 1.
Because r does not divide p -- 1 (the size of group Z*), the order of g must be 1. Here
we get g mod p = 1 and # -- 1 mod p = 0. Now it is obvious that g -- 1 and n have a
common divisor. Hence, to factor n we merely have to compute the greatest common
divisor of numbers g -- 1 and n and we get gcd(g -- l,n) = p.
54
7. DIGITAL SIGNATURE
Exercise 7.5
Prove that the Ong-Schnorr-Shamir subliminal channel scheme is correct.
Solution 7.5.1
Qng-Schnorr-Shamir subliminal channel scheme is correct. Because w and w' are coprimes
to n, we have gcd(n, w) = gcd(n,/) = 1. Therefore we can easily calculate w~l
mod n and
w'~l
mod n using the Extended Euclidean algorithm and the Bezouťs identity.
We can see that the verification is correct:
w' = Sf -- hS% mod n
= 7 --ô" + 2w
+ w
- k
~\r
4 \  J 2
/ 4
(4
= - (w'2
w~2
+ 2/ + to2
- w/2
t(;"
4 v -2
+ ;
Aw1
= ---- mod n = w' mod n = w'
4
2w' + w J mod n
+ 2w' -- w2
) mod n
The decryption of subliminal message is also correct:
_ľk fw'
S\ + k 1
S*2 mod n = - ( hw +
2\w )
-- w ) mod n
w
And now, we can see that
w
1 fw w \
\-w-\ w ) mod n
2 \w w J
2(w'w~1
) 1 -1 A
mod n = w w mod n
= w'(Si + k~1
S2)~1
mod n
= w'(w'w~l
)~l
mod n
= w'w'~1
(w~1
)~1
mod n
= w mod n = w.
Exercise 7.6
Assume that in the Lamport signature schemes two fc-tuples, x and x', were signed by Bob.
Let / = d(x, x1
) be the Hamming distance of x and x'. How many new messages is an
adversary able to sign in such a case?
Solution 7.6.1 by Lukáš Mojžíš
If d(x, x1
) = f then messages x and x' differs in exactly / positions Pi1,Pi2, ˇ ˇ ˇ, Pif ˇ At every
position piq, where 1 < q < f, we can choose from values 0 and 1 because we know both ijiqo
and yiq\. We are able to sign every message chosen this way. Therefore we can sign (2-f -- 2)
new messages for / > 1. If / = 0 then x = x' and the security was not broken - we are
unable to sign any other message.
55
Chapter 8
Elliptic Curve Cryptography and Factorization
Cryptography based on manipulating with points of so called elliptic curves is getting monument
and it has tendency to replace public key cryptography based on infeasibility of factorizing
integers or of computing discrete logarithm.
The main advantage of elliptic curves cryptography is that to achieve a certain level of
security shorter keys are required then in case of classical cryptography. Using shorter keys
can result in savings in hardware implementations. The second advantage of elliptic curves
cryptography is that many attacks available for cryptography based on factorization and
discrete logarithm do not work for elliptic curves cryptography.
8.1 Elliptic Curve
An elliptic curve E is the graph of the equation
E : y2
= x3
+ ax + b,
where a, b are (for our purposes) either rational number or integers (mod n), we extend all
the points of the graph by a point oíinfínity, denoted as Ö, that can be regarded as sitting at
the top and the bottom of y-axis at the same time. We consider only those elliptic curves that
have no multiple roots (i.e. 4a3
+ 27b2
/ 0).
8.2 Addition of Points
On elliptic curve, addition of points can be defined in such a way that they form an Abelian
group. If the line through two different points P\ and P2 of an elliptic curve E intersects
E in a point Q = (x, y), then we define Pi + P2 = P3 = (x, --y). If the line through two
different points P\ and P2 is parallel with y-axis, then we define P\ + P2 = O. If P\ = P2
and the tangent to E in P\ intersects E in a point Q = {x, y), then we define P\ + P\ = P3 =
(x, --y). Now, it is easy to verify that the addition of points forms Abelian group with Ö as
the identity element.
Addition of points P\ = (x\, y\) and P2 = (#2,2/2) of an elliptic curve E : y2
= x3
+ ax + b
can be computed using the formula Pi + P2 = P3 = (#3, J/3), where xs = A2
-- x\ -- X2 and
j/3 = \(x\ -- X3) -- y\ and A can be calculated as follows:
X=hv2-Vl)(x2-X1)-1
if Px+ P2
\(3x2
+ a){2yi)-1
i f P i = P 2
If A is not finite, then P3 = O
56
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
8.3 Elliptic Curves over a Finite Field
The points on an elliptic curve E : y2
= x3
+ ax + b (mod n) are such pairs (x, y) mod n
that satisfy the above equation, along with the point of infinity Ö. The addition of points on
an elliptic curve over a finite field is done the same way as described above. The number of
points on an elliptic curve over a finite field is limited by the Hasse's theorem.
Hasse's theorem: If an elliptic curve E (mod n) has N points, then | N -- n -- 1| < 2^l/ň.
8.4 Discrete Logarithm Problem for Elliptic Curves
Let E be an elliptic curve and A, B its points such that B = kA for some k. The task to find
k is called the discrete logarithm problem for the elliptic curve E. No efficient algorithm to
compute discrete logarithm problem for elliptic curves is known and also no good general
attacks. Elliptic curves cryptography is based on these facts.
Every cryptosystem (protocol) based on discrete logarithm problem can be converted
into a cryptosystem (protocol) based on elliptic curves. The conversion goes as follows:
* Assign to the message (plaintext) a point on an elliptic curve.
* Change in the cryptosystem modular multiplication to addition of points on an elliptic
curve.
* Change in the cryptosystem exponentiation to multiplying a point on an elliptic curve
by an integer.
* To the point of an elliptic curve that results from the modified cryptosystem assign a
message (cryptotext).
8.5 Factorization
Factorization is a process, in which a composite number is decomposed into a product of
factors that are prime numbers. For each number there is an unique decomposition and the
product of factors is equal to the original integer.
When the number is very large, there is no efficient factorization algorithm known. The
hardest problem is to find factors of n = pq, where p and q are distinct primes of the same
size but with a great distance \p -- q\.
8.5.1 Factorization with Elliptic Curves
To factorize an integer n we choose an elliptic curve E, a point P on E (mod n) and compute
either points iP for i = 2,3,4,... or points 2j
P for j = 1,2,3, In doing that we need to
compute gcd(a;a -- Xb,n) for various points A, B (while computing A). If one of these values
is between 1 and n, we have a factor of n.
8.5.2 Pollarďs Rho Method
This method is based on the Birthday paradox - when we keep choosing pseudorandom
integers, there must be a pair a, b such that a = b (mod p), where p is a prime factor of
n, the number we want to factor. First, we need to choose some pseudorandom function
57
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
/ : Zra --> Zra and an integer XQ G Zn. Then we keep computing a;j+i = /(i) for i = 0,1,2,...
and gcd(|:Cj -- Xk\, n), for each k < j.li gcd(|a;./ -- Xk\,n) > r > 1 then we have found a factor
r of n such that xj = xk (mod r).
There is several modification of this method. They differ in the frequency of calculating
gcd(\xj -- Xk\, n). In the second Pollarďs rho method, we calculate gcd{\xj -- Xk\, n) only for
one k < j . li j is an (h + 1) bit integer (2h
< j < 2h+l
), then compute gcd(\xj -- x2h-i\,n).
8.6 Exercises
Exercise 8.1
Factorize the following numbers (Do not use just brute force; describe computation steps.)
1. 232
- 1
2. 264
- 1
3. 332
- 1
Solution 8.1.1 by Tomáš Laurinčík
Using the quadratic sieve method and properties of Fermaťs numbers, we get:
1. (232
- 1) = (216
+ 1)(216
- 1) = (216
+ 1)(28
+ 1)(24
+ 1)(22
+ 1)(2 + 1)(2 - 1) =
1 ˇ 3 ˇ 5 ˇ 17 ˇ 257 ˇ 65 537 = 3 ˇ F1 ˇ F2 ˇ F3 ˇ F4, where Fi is ith Fermaťs number. Because
the first four Fermaťs number are primes, the prime factors of (232
-- 1) are 3,5,17,257
and 65 537.
2. (264
- 1) = (232
+ 1) (232
- 1) = 3 ˇ Fi ˇ F2 ˇ F3 ˇ F4 ˇ F5, where Fi is ith Fermaťs number.
The factors of F5 are 641 and 6 700 417, hence the prime factors of (264
-- 1) are 3, 5,17,
257, 641, 65 537 and 6 700 417.
3. (332
- 1) = (316
+ 1)(316
- 1) = (316
+ 1)(38
+ 1)(34
+ 1)(32
+ 1)(3 + 1)(3 - 1) =
2 ˇ 4 ˇ 10 ˇ 82 ˇ 6 562 ˇ 43 046 722, where the prime factors are 4 = 22
,10 = 2 ˇ 5, 82 = 2 ˇ 41,
6 562 = 2 ˇ 17 ˇ 193 and 43 046 722 = 2 ˇ 21 523 361. It can be shown, that all of the listed
factors are primes using the Fermaťs test and the Lucas's test or any factorization tool.
The prime factors of (332
- 1) are 27
, 5,17,41,193 and 21523 361.
Exercise 8.2
Show that 216
+ 1 is prime number.
Solution 8.2.1 by Dušan Katona
We can see that 216
+ 1 = 224
+ 1 is fourth
is prime, we can use the Pepin's test:
ˇFn -1
Fn is a prime if and only if 3 2 =
F4-l 2 1 6
+ 1 - 1 ,,15
For F4 we have 3 2 = 3 2 = 3Z
=
Fermat number. To test whether a Fermat number
--1 (mod Fn)
--1 (mod 216
+ 1) and therefore 216
+ 1 is a prime.
58
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
Solution 8.2.2 by Martin Mec
To show that 216
+ 1 is prime we can use Lucas test:
Let n > 1. If for every prime factor q of n -- 1 there is an integer a such that
n - l
an
~ = 1 (mod n) and a  ^ 1 (mod n), then n is a prime.
In the first step of Lucas test we find out whether a and n are coprimes, in the second step
we test the order of a. If its order is equal to n -- 1 then the size of the set Z* is n -- 1 and
therefore n is a prime.
The number 216
has only one prime factor - 2. And we can see that 32
= 1 (mod 216
+1)
and 3^~ = 32
= --1 (mod 216
+ 1). The number 216
+ 1 passes the test and therefore it is a
prime.
Exercise 8.3
Assume that n = pq, where p and q are distinct primes.
1. Compute A = n + 1 -- <p(ri).
2. Compute roots of the equation x2
-- Ax + n and give explicit expressions for computing
p and q.
3. Find the factorization for n = 15 049 and <p(n) = 14 800.
Solution 8.3.1
1. A = n + 1 -- <p(ri) = pq + 1 -- (p -- l)(q -- 1) = pq + 1 -- (pq -- p -- q + 1) = p + q
2. The roots of equation x2
-- Ax + n are p and q:
x2
-- Ax + n = 0
2
-- (p + q)x +pq = 0
(a; -- p) (a; -- q) = 0
The roots can be calculated using the quadratic formula:
A + \/A2
- 4n A - \/A2
- 4n
P =
2 ' q =
2
3. When we know the values of n and <p(ri), we can find the factors of n. For n = 15 049
and ip(ri) = 14 800 we get:
A =n + l - <p(ri) = 15049 + 1 - 14800 = 250
p =
A + VA2
-
2
-An 250 + V2304
2
250 - ^2304
= 149
Q =
A-VA2
- -An
250 + V2304
2
250 - ^2304
= 101
59
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
Exercise 8.4
Consider the finite field K = GF (7) = Z7. An elliptic curve Ea>b over K is defined by
K,b = {>} U {{x,y) eK2
\y2
= x3
+ ax + b}.
1. Find all points of 72,1.
2. Verify Hasse's Theorem.
3. For each point P e 72,1, compute -- P and check that it lies on the curve as well.
4. To which group is ^,1 isomorphic to?
Solution 8.4.1
1. To find all point of the curve 72,1 : y2
= x3
+ 2x + 1 we need to find the squares of all
elements of Z7:
e 0 1 2 3 4 5 6
e2
mod 7 0 1 4 2 2 4 1
For each S6Z7 we should find y2
, if it is a square in Z7, we have found new points of
the curve 72,1:
X 0 1 2 3 4 5 6
y2
mod 7 1 4 6 6 3 3 5
For a; = 0 we get points P\ = (0,1) and P2 = (0, 6), for x = 1 we get another two
points P3 = (1,2) and P4 = (1, 5). And there is another one point of 72,i - the point
Po = O: 72,i = {O, (0,1), (0,6), (1,2), (1, 5)}. Because the curve has no multiple roots
(4a3
+ 2762
= 4 ˇ 23
+ 27 = 3 > 0), its points forms a group.
2. We should verify the Hasse's Theorem - and we can see that it holds:
\N-p-l\ < 2^/p
| 5 - 7 - l | = 3 < 2 - 2 <2v/
7
3. For each point P = (x, y) G 72,1 we can find the point --P = (x,--y mod 7):
P -P
Po = 0 -Po = 0 = Po
Pi = (0,1) -Pi- = (0, -1 mod 7) = (0,6) == P2
^ = (0,6) -P2-- = (0, -6 mod 7) = (o,i) == Pl
^3 = (1,2) -P3-- = (1,-2 mod 7) = (1,5) == P4
PA = (1,5) -P4-- = (1,-5 mod 7) = (1,2) == P3
And we can see that all of this points lies on the curve 72,1.
60
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
The group (E2yi, +) is isomorphic to the group (Z5, +). Let / : E2ii --> Z5 be a function
such that
f(0)  0
/ ( ( 0 , 1 ) ) ^ 1
/ ( ( 1 , 5 ) ) ^ 2
/ ( ( 1 , 2 ) ) ^ 3
/ ( ( 0 , 6 ) ) ^ 4
We can see that / is a homomorphous mapping (/(a +E2 1 b) = f (a) +zB /(&)) and we
can easily find the inverse homomorphous mapping g:
9(0) ^O
5  .-+(0,1)
5(2) .-+(1,5)
5(3) -+(1,2)
5(4) .-+(0,6)
Exercise 8.5
Use the rho method with f(x) = x2
-- 1 and XQ = 5 to find a factor of n = 7 031.
Solution 8.5.1
Using the Pollarďs rho method with function f(x) = x2
-- 1, XQ = 5 and Xi+\ = f(xi) we get
the following factors of n = 7031:
x\ = x\ - 1 = 24
gcd(a;i -- xo,n) = gcd(19, 7031) = 1
%2 = x\ -- 1 = 575
gcd(a;2 -- xo,ri) = gcd(570, 7031) = 1, gcd(:c2 -- x\,n) = gcd(551, 7031) = 1
X3 = x\ -- 1 = 167
gcd(:c3 -- xo,n) = gcd(162, 7031) = 1, gcd(:c3 -- xi,n) = gcd(143, 7031) = 1,
gcd(a;3 -- X2,ri) = gcd(6623, 7031) = 1
X4 = x\ -- 1 = 6795
gcd(:c4 -- xo,n) = gcd(6790, 7031) = 1, gcd(:c4 -- x\, n) = gcd(6771, 7031) = 1,
gcd(a;4 - x2,n) = gcd(6220, 7031) = 1, gcd(a;4 - x3,n) = gcd(6628, 7031) = 1
x5 = x\ - 1 = 6478
gcd(:c5 -- xo,n) = gcd(6473, 7031) = 1, gcd{x$ -- x\, n) = gcd(6454, 7031) = 1,
gcd(a;5 -- X2,ri) = gcd(5903, 7031) = 1, gcd(:c5 -- xs,n) = gcd(6311, 7031) = 1,
gcd(a;5 -- X4,n) = gcd(6714, 7031) = 1
61
8. ELLIPTIC C U R V E C R Y P T O G R A P H Y A N D FACTORIZATION
Xß = x\ -- 1 = 3475
gcd(:c6 -- xo,ri) = gcd(3470, 7031) = 1,
gcd(a;6 - x2,n) = gcd(2900, 7031) = 1,
gcd(a;6 -- X4,n) = gcd(3711, 7031) = 1,
1 = 3397
gcd(:c7 -- xo,n) = gcd(3392, 7031) = 1,
gcd(a;7 - x2,n) = gcd(2822, 7031) = 1,
gcd(:c7 -- X4,n) = gcd(3633, 7031) = 1,
gcd(a;7 -- xe,ri) = gcd(6953, 7031) = 1
Xj X
6
gcd(:c6 -- x\,n)
gcd(a;6 -x3,ri)
gcd(a;6 -x5,n)
gcd(:c7 -- xi,n)
gcd(a;7 -x3,n)
gcd(a;7 -x5,n)
gcd(3450, 7031) = 1,
gcd(3308,7031) = 1,
gcd(4028,7031) = 1
gcd(3373,7031) = 1,
gcd(3230,7031) = 1,
gcd(3950,7031) = 79,
And we can see that 79 is one factor of 7031: 7031/79 = 89.
Solution 8.5.2 by Lukáš Mojžíš
To factor n = 7031 we can also use the second Pollarďs rho method.
x\ = XQ - 1 = 24
%2 = x\ -- 1 = 575
x3 = x\ -- 1 = 167
X4 = x\ -- 1 = 6795
x5 = x\ - 1 = 6478
%6 = x\ -- 1 = 3475
xj = x\ -- 1 = 3397
^8 = %7 -- 1 = 1737
XQ = x\ -- 1 = 869
gcd(a;i -- xo,n)
gcd(a;2 --xi,n)
gcd(a;3 -xi,n)
gcd(:c4 -- x3,ri)
gcd(a;5 -X3,n)
gcd(a;6 -x3,ri)
gcd(a;7 -x3,n)
gcd(:c8 -- xj,n)
gcd(a;g -- xj,n)
= gcd(19,7031) = 1
= gcd(551,7031) = 1
= gcd(143,7031) = 1
= gcd(6628, 7031) = 1
= gcd(6311,7031) = 1
= gcd(3308, 7031) = 1
= gcd(3230, 7031) = 1
= gcd(5371,7031) = 1
= gcd(4503, 7031) = 79
79 is prime and it is a prime factor of 7031, the other prime factor is 7031/79 = 89.
Exercise 8.6
Let n be an odd integer.
1. Describe a method based on Fermaťs theorem for testing whether n is composite.
2. Prove that for each odd composite number n there are always at least two numbers
a G Z* such that da
~l
= 1 (mod n).
3. Are there any numbers n for which the test (from (1)) fails for any a G Z^? Prove that
such numbers do not exist or give an example of such number.
Solution 8.6.1 by Martin Mec
1. The method is called Fermaťs primality test. It is based on the Fermaťs little theorem:
Let p be a prime, a any positive integer such that gcd(a, n) = 1, then ara_1
= 1
(mod n).
62
8. ELLIPTIC CURVE CRYPTOGRAPHY AND FACTORIZATION
It says that an odd positive integer n is composite if there exists a positive integer a
such that gcd(a, n) = 1 and ara_1
^ 1 (mod n).
2. If a = 1 or a = n -- 1, then da
~l
= 1 (mod n). If a = 1, then for any positive integer
k it holds that lk
= 1. If a = n -- 1, then a is even (because n is odd) and we have
(n - l)n
~l
= (-l)TM"1
= ( ( - l ) 2
) 2
^ = 1 ^ = 1 (mod n).
3. The test fails for Carmichael numbers. Carmichael numbers are not primes, but they
satisfy ara_1
= 1 (mod n) for all values of a such that gcd(a, n) = 1. The smallest
Carmichael number is 561.
Exercise 8.7
In 2002 three Indian scientists published the first deterministic polynomial algorithm deciding
the primality problem. The method uses the following theorem.
Let n > 1, a be integers such that gcd(a, n) = 1. Then n is a prime if and only if
(x + a)n
= xn
+ a in Zn[x\.
Prove this theorem.
Solution 8.7.1 by Tomáš Laurinčík
Firstly, we will show that if n is a prime then (x + a)n
= xn
+ a in Zn[x]. We have
(x + a)n
= J2(l)%k
an
-k
= an
+ xn
+ J2
fc=0 ^ ' fc=l
Since n is a prime,
n\ n\ (n -- 1)!
1
-- = n,
,xk
an k
k,
Jz) k\{n-k)\ k\{n-k)\
Because n is a prime, for all 0 < I < n it holds gcd(Z, n) = 1. Therefore gcd(fc!(n -- k)l, n) = 1
and n divides (^) for 0 < k < n. Hence (x + a)n
= xn
+ an
in Zn[x]. Using the Fermaťs little
theorem we get an
= a (mod n) and therefore (x + a)n
= xn
+ a in Zn[x\.
Secondly, we will show that if n is a composite number, then (x + a)n
/ xn
+ a in Zn[x\.
Because n is composite we can write n = pe
m, where p is a prime such that pe+1
does not
divide n. We have
'n\ n\ (pe
m)\
kJ k\(n -- k)\ k\{pe
m -- k)V
for k = p we get
n\ {pe
m)\ pe
~1
m(pe
m -- 1)!
Kp) p\(pe
m -- k)\ (p -- l)\(pe
m -- k)V
It is obvious that pe
does not divide (TM). Since gcd(a, n) = 1, it holds that gcd(a,pe
) = 1 and
also gcd(an
~p
,pe
) = 1. There we get ("))xp
an
~p
= cxp
, where c / 0 in Zn. Hence (x + a)n
/
xn
+ a in Zn\x\.
63
Chapter 9
User Identification, Message Authentication and Secret Sharing
Most applications of cryptography ask for authentic data rather then secret data. A practically
very important problem is how to protect data and communication against an active
attacker.
9.1 User Identification
User identifícation is a process at which one party (called a prover) convinces another party
(called verifier) of prover's identity and that the prover has actually participated in the identification
process. The purpose of any identification process is to preclude impersonation
(pretending to be another person).
User identification has to satisfy following conditions:
* The verifier has to accept prover's identity if both parties are honest.
* The verifier cannot later, after succesful identification, pose as a prover and identify
himself to another verifier (as the prover).
* A dishonest party that claims to be the other party has only negligible chance to identify
himself successfully.
Every user identification protocol has to satisfy two security conditions:
* If one party (verifier) gets a message from the other party (prover), then the verifier is
able to verify that the sender is indeed the prover.
* There is no way to pretend for a party when communicating with Bob, that he is Alice,
without Bob having a large chance to find out that.
Identification system can be based on any public key cryptosystem. The identification
goes as follows: Alice chooses a random r and sends e#(r) to Bob (e# is the encryption
algorithm for Bob). Alice identifies a communicating person as Bob, if he can send her back
r. Bob identifies a communicating person as Alice, if she can send him r.
Identification scheme can be also based on any one way function / and key k. Both Alice
and Bob share a key k and a one way function /. The identification goes as follows: Bob
sends Alice a random number or string r. Alice sends Bob P = f (k, r). If Bob gets P, then
he verifies whether P = f (k, r). If yes, he starts to believe that the communicating person is
Alice. The process can be repeated to increase the probability of correct identification.
64
9. USER IDENTIFICATION, MESSAGE AUTHENTICATION AND SECRET SHARING
9.2 Message Authentication
The goal of the data authentication protocols is to handle the case that data are sent through
insecure channels. By creating so-called Message Authentication Code (MAC) and sending
this MAC together with the message through an insecure channel, the receiver can verify
whether data were not changed in the channel. The price to pay is that the communicating
parties need to share a secret random key that needs to be transmitted through a very secure
channel.
The basic difference between MACs and digital signatures is that MACs are symmetric.
Anyone who is able to verify MAC of a message is also able to generate the same MAC
and vice versa. A scheme (M, T, K) for data authentication is given by a set of possible
messages (M), a set of possible MACs (T) and a set of possible keys (K). It is required
that to each key k from K there is a single and easy to compute authentication mapping
authk : { 0 , l } ' x M - > r and a single easy to compute verification mapping verk : M x T -->ˇ
{true, false}. An authentication scheme should also satisfy the condition of correctness: For
each m from M and k from K it holds verk(m, c) = true if there exists an r from {0,1}*
such that c = author, m); and the condition of security: For any m from M and k from
K it is computationally unfeasible (without the knowledge of k) to find c from T such that
verk(m,c) = true.
9.3 Secret Sharing Scheme
Secret sharing schemes distribute a secret among several users in such a way that only predefined
sets of users can recover the secret.
Let t < n be positive integers. A (n, i)-threshold scheme is a method of sharing a secret
S among a set P of n participants, P = {Pi | 1 < i < n}, in such a way that any t, or
more, participants can compute the value S, but no group of t -- 1, or less, participants can
compute S. Secret S is chosen by a dealer D fi P. It is assumed that the dealer distributes the
secret to participants secretly and in such a way that no participant knows shares of other
participants.
9.3.1 Shamir's (n, í)-secret sharing scheme
Initiation phase: Dealer D chooses a prime p > n,n distinct Xi, 1 < i < n and D gives the
value Xi to the user Pi. The values public.
Share distribution phase: Suppose D wants to share secret S G Zp among the users. D
randomly chooses t -- 1 elements from Zp, a\,... at-\. For 1 < i < n D computes the
shares tji = f(xi), where f(x) = S + Y?j=i a
ix
^ m
°d V- D gives the computed share tji
to the participant Pi.
Secret cumulation phase: Let participants P^,..., Pit want to determine secret S. Since f(x)
has degree t -- 1, f (x) has the form f(x) = ÜQ + a\x -\ \- at-ix1-1
, and coefficients am
can be determined from t equations f(xi-) =y%-, where all arithmetics is done modulo
p. It can be shown that equations obtained this way are linearly independent and the
system has only one solution. In such a case we get S = ÜQ.
65
9. USER IDENTIFICATION, MESSAGE AUTHENTICATION AND SECRET SHARING
9.4 Exercises
Exercise 9.1
Consider the following identification scheme (based on RDSA signatures).
Let n be a large integer of size s, 7 an element of Z^ and q a prime of size t (e.g. s = 1024
and t = 160 bits). Values n, 7 and q are public parameters.
Let a <E {2,... ,q -- 1} be a private key and a = 7" mod n be the corresponding public
key.
Identification goes as follows:
1. Prover chooses randomly k e {0,... ,q -- 1}, computes ß = 7fc
mod n and sends ß to
Verifier.
2. Verifier chooses challenge e e {0,... ,q -- 1} and sends it to Prover.
3. Prover checks whether e G {0,... ,q -- 1} and computes x = k -- ae. Prover computes
r, / such that x = Iq + r. Prover computes A = 7' mod n and sends A, r to Verifier.
4. Verifier checks whether r e {0,. ˇ ˇ ,q -- 1} and /x = 7r
o;e
A9
mod n.
Answer the following questions:
1. Show that the verification is correct if both Prover and Verifier follow the instructions.
2. What happens if Verifier chooses e = 0? Compute I, r and A for this case. Does Verifier
learns something about Prover's private key?
3. Show that Verifier, who sends e = 1 as his challenge, can learn (with high probability)
one bit of Prover's private key after a few runs of the protocol. Compute I, r and A for
this case.
Solution 9.1.1
1. Let ßp = 7fc
mod n is ß computed by Prover.
Verifier calculates ßy = 7r
o;e
A9
mod n = Y{la
)e
{ll
)q
mod n = Y+ae+lq
mod n =
^x+ae m o c | n _ ^(k-ae)+ae m Q C | n _ ^k m Q C | n_
If both Prover and Verifier follow the protocol then ßp = ßy.
2. If Verifier chooses e = 0 then x = k. Because 0 < k < q we have x = Oq + r and
we can see that r = k, I = 0 and A = 70
mod n = 1. Verifier then calculates ß =
Yoř\q
mod n = Y ˇ 1 ˇ 1 mod n = Y mod n.
If ß = a we can see that 7r
= 7" (mod n). Let 0 be the order of 7 in Z^ then r = a
(mod o).lío> q then r = a. Because we don't know anything about the order of 7 nor
about the factorization of n, we cannot be sure that r = a, there is only the possibility
that it holds.
3. If Verifier chooses e = 1 then x = k -- a.
* If k > a then 0 < x < q and hence x = Oq + (k -- a), so I = 0, r = k -- a and A = 1.
66
9. USER IDENTIFICATION, MESSAGE AUTHENTICATION AND SECRET SHARING
* If k < a then --q < x < 0, hence x = --q + (k -- a + q), so I = -- 1, r = k -- a + q and
A = 7_1
modn. If 7 / 1 then A / 1. If 7 = 1 then this protocol makes no sense.
With each run of the protocol we calculate dist and put the value into the the set Dist.
if A = 1 (k - a > 0),
-q if A / 1 (k - a < 0).
We can see that each d G Dist satisfies d > --a (the least d = r -- q = k -- a + q -- q =
k -- a = --a for k = 0) and d < q -- 1 -- a (the biggest d = r = k -- a = q -- 1 -- a for
k = q -- 1). So we have --a < d < q -- a -- 1 what is equal to --d < a < q -- 1 -- d.
Because this unequality is satisfied for each d G Dist it must hold also for dmin =
min{d G Dist} and dmax = max{d G Dist}. We can see that --dmax < --dmin and
q-l-dmax < Q-1 -dmin- Now we have -dmax < -dmin <a< q-l-dmax < q-l-dmin
and therefore --dmin < a < q -- 1 -- dmax.
Now, we know the interval where a lies. That means that we can learn several most
significant bits of a.
Exercise 9.2
Consider Shamir's (10,3)-secret sharing scheme over Zp where p is a large prime. There is
one cheating share holder. His goal is to give a bad share in the secret cumulation phase. The
point is that nobody knows which share holder is the cheater.
1. Describe a method to reconstruct the secret given all 10 shares and explain why it
works.
2. Determine the smallest number x of shares that are sufficient to reconstruct s. Explain.
3. Let us take any collection of fewer than x share holders. Can they obtain any information
about the secret? Explain.
Solution 9.2.1 by Mária Svoreňová
1. We can compute secrets s\, S2, S3 for three disjoint sets of shares. We obtain at least two
same secrets sÍ = sj = s, because the cheater's bad share can be in only one set. If we
have three disjoint sets of three shares and s\ = S2 = S3, we know that the cheater is
the one, not being in any set.
2. We know, that x must be greater then 3, otherwise we cannot reconstruct the secret.
If x = 4, then we obtain up to (3) = 4 different secrets. If all four reconstructed secrets
are the same, then there is no cheater in the group and we get the secret s. If the reconstructed
secrets are all different or do not exist, there is the cheater in the group and
only one of these secrets is our secret s - and we cannot find out which one it is.
If x = 5, then we obtain (3) = 10 possible secrets. If there is the bad share, then the secret
s appears (3) = 4 times. The other 6 secrets are different or do not exist. Therefore,
the smallest number x of shares sufficient to reconstruct the secret s is 5.
67
9. USER IDENTIFICATION, MESSAGE AUTHENTICATION AND SECRET SHARING
If there are less then three share holders, they cannot obtain any information about the
secret.
Any three share holders can compute some secret, but they cannot be sure whether
they have recover the secret s. The probability, that they have found it is
70 %, what is not bad.
(ľ) 10
A group of four share holders can compute up to four possible secrets. If they are
all equal, they reconstructed the secret s. Otherwise, if one of the share holders is the
cheater, they know, that only one of the computed secrets is the secret s.
Exercise 9.3
Sender S broadcasts messages to n receivers R\,..., Rn. Privacy is not important but message
authenticity is. Each of the receivers wants to be assured that the messages he has received
were sent by S. The subjects decide to use a MAC.
1. Suppose all subjects share a secret key k. Sender S adds the MAC to every message he
sends using k and each receiver verifies it. Explain why this scheme is insecure.
2. Suppose sender S has a set A = {fa,..., km} of m secret keys. Each receiver Ri has
some subset Ai C A of the keys. Before sending a message, S computes MAC Cj of the
message for each key fa. Then S sends all MACs c\,... ,cm with the message. When
receiver Ri receives a message, he accepts it as authentic if and only if all MACs corresponding
to keys in Ai are valid. Which property should sets Ai,... ,An satisfy to be
resistant to the attack from (1). Assume that the receivers cannot collude.
3. Suppose that n = 6. Show that it is sufficient for the sender to append 4 MACs to every
message to satisfy the condition derived in (2). Describe sets A\,..., AQ C {fa,..., fa}.
Solution 9.3.1
1. When all receivers R\,..., Rn share the same key k for verifying that the received message
was sent by S, each of them can calculate the MAC using the key k for any message
m of his choice. When this cheater broadcasts this message m and its MAC calculated
using the key k of S, all receivers verify that the message was sent by S.
2. Let l<i,j<n,i^j then Ai ^ Aj. If the keyset Ai of receiver Ri is a subset of keyset
Aj of receiver Rj then the receiver Rj can send a message m with MACs c\,..., cm
where Q is computed using the key fa e Aj, cx such that fa  Aj is chosen randomly.
Now the receiver Ri accepts the message (and thinks that the sender was S) because
for each kw G Ai is the MAC cw valid.
If there are no such key sets Ai C Aj then the scheme is secure.
3. This scheme is secure because we can make 6 different sets Ai such that \Ai\ = 2 and
Ai c {ki, fa, ks, Li}. When we have elements fa, fa, fa and fa we can get six different
pairs of them because
'4\ _ 4! _ 4 ˇ 3 _
~ 2!2! ~ ~2~ ~ 6
'
68
9. USER IDENTIFICATION, MESSAGE AUTHENTICATION AND SECRET SHARING
Now, there is no receiver Ri who can make another receiver think that the sender was
someone else.
Exercise 9.4
Alice wishes to prove to Bob that she really does know the private key d corresponding to
her RSA public key (n, e). They decide to use the following protocol:
* Bob chooses a random r and sends its encryption s = re
(mod n) to Alice.
* Alice decrypts s by computing sd
(mod n) and returns the result to Bob.
* Bob accepts if and only if the returned message is r.
1. Prove that the protocol is zero knowledge under the assumption that Bob is honest.
2. What kind of information can dishonest Bob learn?
Solution 9.4.1 by Tomáš Laurinčík
1. Assume that Bob is honest. Bob chooses a random number r and encrypts it with Alice's
public key. Since the number r is random, it gives no information about Alice's
private key. Alice uses her private key to decrypt the number r and sends it back to
Bob. Bob cannot get any information about Alice's private key, because everything he
gets is the random number r, that he already knows. If the parameters for RSA are
properly chosen, then this protocol is zero knowledge.
2. A dishonest Bob can use this protocol to decrypt messages sent to Alice by someone
else. He only sends the message he wants to decrypt (with some salt, so that Alice does
not recognize, that it is message sent to her) to Alice, Alice decrypts it and sends it back
to Bob.
Bob can also misuse this protocol. He can send a message m to Alice (not encrypted
with her public key), Alice sends him back me
mod n, what is Alice's signature of message
m. Then, Bob can send any message m pretending that the sender is Alice.
69
Chapter 10
Bit Commitment Protocols and Zero Knowledge Proofs
A protocol is an algorithm two (or more) parties have to follow to perform a communication.
A cryptographical protocol is a protocol to achieve secure communication during some goal
oriented cooperation.
10.1 Bit Commitment Protocols
In a bit commitment protocol Alice chooses a bit b and gets committed to b, in the sense, that
Bob has no way of knowing which commitment Alice had made, and Alice has no way of
changing her commitment once she has made it (after Bob announces his guess as to what
Alice has chosen).
The basis of bit commitment protocols are bit commitment schemes. A bit commitment
scheme is a mapping / : { 0 , l } x l - > ľ , where X and Y are finite sets. A commitment to
bit b G {0,1} is any value f(b, x) for x G X. Each bit commitment protocol has two phases the
commitment phase and the opening phase. In the commitment phase, the sender sends
a bit b he wants to commit to (in an encrypted form) to the receiver. In the opening phase,
the sender sends to the receiver information that enables the receiver to get the bit b.
Each bit commitment scheme should have three properties:
Hiding(privacy): For no b G {0,1} and x G X, it is feasible for Bob to determine b from
B = f(b,x).
Binding: Alice can open her commitment B by revealing x and b such that B = f (b, x), but
she should not be able to open a commitment B with both 0,1.
Correctness: If both, the sender and the receiver, follow the protocol, then the receiver will
always learn the commitment b.
10.2 Oblivious Transfer Problem
The oblivious transfer problem: Design a protocol for sending messages from Alice to Bob in
such a way that Bob receives the message with probability \ and garbage otherwise. Moreover,
Bob knows whether he got the message or garbage, but Alice has no idea which one he
got.
The l-out-of-2 oblivious transfer problem: Alice sends two messages to Bob in such a
way that Bob can choose which of the messages he receives (but he cannot choose both of
them), but Alice cannot learn Bob's decision.
70
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
10.3 Zero Knowledge Proof Protocols
One of the most important, and at the same time very counterintuitive, primitives for cryptographic
protocols are so called zero knowledge proof protocols. We can say that zero knowledge
proof protocol allows one party, usually called prover, to convince another party, called
verifier, that prover knows some facts without revealing to the verifier any information about
his knowledge. Zero knowledge proof protocols are a special type of so called interactive
proof systems.
An interactive proof system has the property of being zero knowledge if verifier, who
interacts with the honest prover, learns nothing from the interaction beyond the validity of
the statement being proved. There are several variants of zero knowledge, that differs in the
way how "learning nothing" is specified.
In an interactive proof system, there are two parties: a prover, often called Peggy (a randomized
algorithm using a private random number generator), and a verifier, often called
Vic (a polynomial time randomized algorithm using a private random number generator).
Prover knows some secret, or knowledge, or a fact about a specific object, and wishes to
convince the verifier, through a communication with him, that he has this knowledge.
The interactive proof system consists of several rounds. In each round prover and verifier
alternatively do the following: receive a message from the other party, perform a private
computation and send a message to the other party. The communication starts usually by a
challenge of verifier and a response of prover. At the end, verifier either accepts or rejects
prover's attempts to convince him.
A zero knowledge proof of a theorem T is an interactive two party protocol, in which
prover is able to convince verifier who follows the same protocol, by the overwhelming
statistical evidence, that T is true, if T is really true, but no prover is able to convince verifier,
that T is true, if T is not true. In addition, during the interaction, the prover does not reveal
to verifier any other information, except whether T is true or not. Therefore, after verifier
gets convinced, he can only believe that T is true.
10.4 3-Colorability of Graphs
With the following protocol Peggy can convince Vic that a particular graph G, known to both
of them, is 3-colorable and that Peggy knows such a coloring, without revealing to Vic any
information how such coloring looks.
Peggy colors the graph G = (V,E) with three colors and then she perform with Vic \E\2
times the following interaction, where v\,... ,vn are vertices of V.
1. Peggy chooses a random permutation of colors, recolors G and encrypts, for i = 1,..., n,
the color a of vertex vi by an encryption procedure e (different for each i).
Peggy then removes colors from vertices, labels the ith vertex of G with cryptotext
Vi = ei(ci) and designs for her a table containing the color and cryptotext of each
vertex. Then Peggy shows Vic the graph with vertices labeled by cryptotexts.
2. Vic chooses an edge and ask Peggy to show him coloring of the adjacent vertices.
3. Peggy shows Vic the colors and encryption procedures corresponding to the selected
vertices.
71
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
4. Vic performs encryption to verify that vertices really have colors as shown.
10.5 Exercises
Exercise 10.1
There is a cryptographic conference in Monaco. The best student of a cryptographic course
will be allowed to participate. Keiko and Hiroki are students with the maximum number of
points from exercises. Unfortunately, only one of them is allowed to participate so they have
to decide which one. Hiroki is now abroad, therefore Keiko suggest the following protocol
that allows them to remotely flip a coin.
* Keiko chooses either x = "HEAD" or x = "TAIL" and picks a random number k. She
encrypts x with DES cipher using the key k. She obtains y = DESfc(a;).
* Keiko sends y to Hiroki.
* Hiroki flips a coin and tells Keiko which face is up.
* Keiko reveals k.
* Hiroki decrypts y with DES using the key k and obtains the guess of Keiko. If Keiko's
guess is correct, she travels to Monte Carlo.
Is Keiko able to cheat?
Solution 10.1.1
Keiko would be able to cheat only if she knew such keys k\, &2 that DESkl (HEAD) =
y = DESk2(TAIL). To find such keys, she can built two lists DESkl(HEAD),ki) and
(DESk2 (TAIL), fc2). Both lists are sorted according to the first field of each entry. Keiko then
looks for collisions between the two lists and obtains keys k\, fo, such that DESkl (HEAD) =
DESk2(TAIL).
Then when she sends y to Hiroki she learns what face of coin is up. Then she can send
back to Hiroki such kí that DESki (x) = y where x is the face.
Because of the computational complexity, it is not easy to find such k\ and fo; by the
Birthday paradox, we need to perform about 232
DES evaluations for getting one collision.
Therefore, we can say that Keiko is not able to cheat.
Exercise 10.2
Let p be a large prime. Let g be a generator of the group (Z*, ˇ). Discuss the security of the
following commitment scheme.
* To commit to m e {0,1,... ,p -- 1}, Alice randomly picks r e {0,1,... ,p -- 1} and sends
c = gr
m (mod p) to Bob.
* To open her commitment, Alice sends r and m to Bob.
1. Is this protocol hiding?
2. Is this protocol binding?
72
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
Solution 10.2.1 by Lukáš Mojžíš
1. The protocol is hiding if m > 0 because when Bob gets c, he knows that c = gk
mod p.
But he doesn't know the two elements h and I2 such that h + h = k. So he is not able
to learn anything about m.
There is only one exception: if m = 0 then c = 0 irrespective of r that Alice chooses (g
is a generator of group Z*, ˇ and there is no s such that gs
= 0 because 0 ^ Z*). And
because m = 0 is allowed, the protocol is not hiding.
2. The protocol is not binding because Alice can choose two distinct r\,T2 G {0,..., p -- 1}
and commit to m = gr2
. Then she sends to Bob c = gri
m = gri
gr2
= m'gr2
and that
means that Alice can open her commitment with m and T\ or with m! and r2 and it is
up to her which of the two pairs she sends to Bob.
Exercise 10.3
Consider the following implementation of l-out-of-2 oblivious transfer which uses standard
oblivious transfer as the underlying primitive:
* Let m = 3n where n is a security parameter. Alice randomly chooses a bit string r =
T\r2 ˇ ˇ ˇ rm. Using standard oblivious transfer m times, she transfers it to Bob, one bit at
a time. Bob learns approximately one half of the bits of r. Let I C. {1,..., m} be a set of
indices for which Bob learns r.
* Bob wants to learn Alice's bit bs. He randomly chooses subset Is C / of size n and
h-s Q {1, ˇ ˇ ˇ, rn} \ I also of size n. He sends Io, I\ in this order to Alice.
* Alice checks that IQ and I\ are of the correct form. She computes Cj = bi  0 - , ^ fj r
where í G {0,1} and sends co, c\ (in this order) to Bob.
* Bob computes bs = cs  0 j  / s TJ.
Answer the following questions:
1. This protocol can fail sometimes. Explain why.
2. Explain how can Bob learn the desired value bs.
3. Can cheating Bob obtain any information about b\-sl
4. Explain why Alice learns nothing about s.
5. Can cheating Bob learn both 60 and 61?
6. Why does Alice need to check correctness of Io and I\ in the third step?
7. Could the number m be defined to be In instead of 3n? Could it be defined to be 5n?
Explain.
73
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
Solution 10.3.1
1. The protocol fails if Bob learns less then n bits of R because then he cannot construct
the set Is. If Bob learns more then 2n bits of R then the protocol also fails because Bob
is not able to construct the correct set /i_s .
2. Bob knows Is and he learns cs from Alice. Then he computes:
cs  (J3 fj = bs (4-) rj (4-) rj = bs
j&is jeis j&is
because the operation  is commutative and it holds that x = x (B a (B a for each a.
3. Cheating Bob can learn both values bs and b\-s only if he knows more then or equal to
In bits of R. When he knows less then In bits of R then he cannot learn anything about
bis4.
She cannot learn anything about s because the only information she gets from Bob is
the two distinct sets IQ and I\. The information about the set / is hidden to her and so
she doesn't know which set Is is the subset of I.
5. When Bob knows more then or equal to 2n bits of R. Then he construct such sets IQ and
h that Io,h Q I and IQC\I\ = 0. Because he knows all the values ri where i G IoL)I\ C I,
he can compute both values bo and b\.
6. Alice need to check the correctness of IQ and I\ because if |/s| < n then the probability
that /o U I\ C / increases so as insecurity. If /o n I\ = A / 0 then the probability that
i o U / i C J also increases.
7. If m = In than the security of the protocol increases but the probability that Bob learns
at least n bits of R decreases. However, if Bob is lucky and learns more then n of R,
he cannot follow the protocol correctly, because he is unable to construct correct sets IQ
and 11.
If m = 5n than Bob learns approximately y = 2, 5n bits of R and so he can learn both
bo and b\ with higher probability and hence the protocol is less secure.
Exercise 10.4
Consider the zero knowledge proof protocol for 3-colorability of graphs that was described
in the section 10.4.
1. Suppose Peggy does not know 3-coloring of a 3-colorable graph G = (V,E), where
| V\ = n and \E\ = m. What is the maximal probability that Peggy makes Vic accept her
proof in single iteration of the protocol? Explain.
2. Suppose Peggy is honest but her random number generator is faulty. The identity permutation
is chosen with probability \ and each of the other permutations is chosen
with probability j ^ . Explain how cheating Vic can discover 3-coloring of G with high
probability after sufficiently many iterations of the protocol.
74
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
Solution 10.4.1 by Martin Vejnár
1. Peggy does not know the 3-coloring of graph G, but according to the protocol, she must
commit to a permutation of her coloring to Vic. Once committed, Peggy cannot change
the coloring. Vic then chooses a random edge and asks Peggy to reveal the coloring
of its adjacent vertices. Peggy cannot lie and Vic can check, whether the vertices have
different color.
Since Peggy does not know the coloring, she must color the graph randomly. The probability,
that both vertices have the same color, for any given pair of vertices, is |.
Hence, after one iteration of the protocol, the probability of Vic accepting the proof is
|. After k iteration of the protocol, the probability would be (|)fc
.
2. With the broken generator, Vic will be able to determine the coloring of an arbitrary
pair of adjacent vertices. In every iteration of the protocol, he just has to choose the
same edge (the one connecting the aforementioned vertices), until a sufficient number
of colorings is retrieved. Then, statistically, about half of the colorings will be the same.
Such a dominant coloring is the Peggy's original coloring. Thus, Vic retrieves a coloring
for the two vertices.
Now, Vic merely has to use this procedure repeatedly, until the coloring of all vertices
is revealed.
75
Bibliography
[1] Baigněres, Thomas, et al.: A classical introduction to cryptography exercise book. New
York : Springer, 2006. ISBN 0387279342.
[2] Kahn, David A.: The codebreakers : the comprehensive history of secret communication
from ancient times to the Internet: the story of secret writing. New York: Scribner,
1996. ISBN 0684831309.
[3] Rothe, Jörg : Complexity theory and cryptology: an introduction to cryptocomplexity.
New York : Springer, 2005. ISBN 3540221476.
[4] Stinson, Dougles R.: Cryptography: theory and practice. Boca Raton: CRC Press, 2002.
ISBN 1584882069.
[5] Introduction to ECC [Online]. Certicom Inc., 2007 [cited 2007 May 12]. Available from
< h t t p : / / w w w . c e r t i c o m . c o m / i n d e x . p h p ? a c t i o n = e c c , a b o u t _ e c c > .
[6] QuickMath: Automatic math solutions [Online]. 1999-2007 [cited 2007 May 12]. Available
from < h t t p : //www.quickmath. com/>.
[7] Cryptography A-Z : Cryptography De-Mystified [Online]. SSH Communications Security,
2007 [cited 2007 May 12]. Available from < h t t p : //www. ssh. com/support/
cryptography/>.
[8] Wikipedia contributors: Linear code [Online]. Wikipedia, The Free Encyclopedia; last
revision 19 April 2007 19:39 UTC [cited 2007 May 12]. Available from < h t t p : / / e n .
wikipedia.org/w/index.php?title=Linear_code&oldid=124164759>.
[9] Wikipedia contributors: Hamming code [Online]. Wikipedia, The Free Encyclopedia;
last revision 12 May 2007 16:46 UTC [cited 2007 May 12]. Available from
< h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = H a m m i n g _ c o d e & o l d i d =
130352788>.
[10] Wikipedia contributors: Public-key cryptography [Online]. Wikipedia, The Free
Encyclopedia; last revision 8 May 2007 21:13 UTC [cited 2007 May 12]. Available
from < h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = P u b l i c - k e y _
cryptography&oldid=12 935 0176>.
[11] Wikipedia contributors: Digital signature [Online]. Wikipedia, The Free Encyclopedia;
last revision 9 May 2007 01:12 UTC [cited 2007 May 12]. Available
from < h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = D i g i t a l _
signature&oldid=12 94 0067 0>.
76
10. BIT COMMITMENT PROTOCOLS AND ZERO KNOWLEDGE PROOFS
[12] Wikipedia contributors: Secret sharing [Online]. Wikipedia, The Free Encyclopedia;
last revision 3 May 2007 08:20 UTC [cited 2007 May 12]. Available
from < h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = S e c r e t _
sharing&oldid=127 905516>.
[13] Wikipedia contributors: Zero-knowledge proof [Online]. Wikipedia, The Free Encyclopedia;
last revision 27 April 2007 19:25 UTC [cited 2007 May 12]. Available
from < h t t p : / / e n . w i k i p e d i a . o r g / w / i n d e x . p h p ? t i t l e = Z e r o - k n o w l e d g e _
proof&oldid=1264 57594>.
77