Chapter1 Introduction 1.1.1 WhatisCryptography?
The study of principles and techniques by which information can be concealed in ciphers and later revealed by legitimate users employing a secret key (i.e., a piece of information known only to them), but in which it is either impossible or computationally infeasible for an unauthorized person to do so. (Encyclopedia Britannica)
The word comes from Greek kryptos hidden, and graphein to write.
A more inclusive term is cryptology, from Greek kryptos and logos word.
The science of secure (generally secret) communications. (Encyclopedia Britannica)
Apart from Cryptography, the term Cryptology includes Cryptanalysis: From Greek
kryptos and anal ein to loosen, to untie.
The science (and art) of recovering information from ciphers without knowledge of the key. (Encyclopedia Britannica)
1.1.2 Thedi erencebetweenciphersandcodes
Cipher: From French chi re and Arabic sifr (nothing also related to zero).
1. Any system of secret writing that uses a prearranged scheme or key. 2. A message
in cipher, also, its key. (Funk & Wagnalls Standard Desk Dictionary).
Code: From Latin codex writing tablet.
A set of signals, characters, or symbols used in communication. (Funk & Wagnalls)
The main topic of this course will be ciphers rather than codes. Some examples of codes: Morse code
ASCII (American Standard Code for Information Interchange) The pigpen cipher (really a code)
Sherlock Holmes Dancing Men
1.1.3 Aboutthiscourse
The main purpose of this course:
To give the mathematical foundations of modern cryptography and of the most important
cryptosystems.
To give means to judge the security of a cryptosystem.
1.1 Generalities
1.2 More Terminology, Classification
What this course does not cover (or only in passing):
Implementations, protocols, etc.
Related to this: Network security, e-commerce, etc.
Political and social issues (escrow systems, the CLIPPER chip, etc.)
Ethical and human-rights issues
Steganography (covert secret writing; from Greek steganos covered)
1.2 MoreTerminology,Classification 1.2.1 Terminology
Cryptosystem (or cryptographic system: A more technical term for cipher.
Plaintext: An English (French, German, . . . ) text, numerical data, other information; may
already have been encoded (for instance, in ASCII).
Encryption: Performed by the sender; intended to render the message unintelligible to any
eavesdropper.
Ciphertext: The result of an encryption; usually a string of symbols, digits, bits, . . .
Decryption: Performed by the intended receiver; the recovering of plaintext from cipher-
text.
1.2.2 Kerckho sprinciple
It is assumed that the cryptosystem in use, and the workings of this system, are public knowledge, or at least known to the potential eavesdropper.
(Auguste Kerckho s, 1883)
Reasons:
It is unreasonable to depend on the secrecy of the cryptosystem.
Adherence to this principle makes standardization of algorithms and large-scale commu-
nication easier.
Thus, the only secret is the key. Therefore, key distribution and key management are fundamental issues in cryptography.
1.2.3 Classification
Cryptosystems can be (roughly) classified according to three di erent criteria:
1. The types of operations used for encryption:
Substitution: Each element in the plaintext (bit, letter, group of bits or letters) is mapped
to another element.
Transposition: Elements in the plaintext are rearranged.
2
1.3 Basic Concepts of Cryptanalysis
Most cryptosystems employ multiple stages of substitutions and transpositions (product sys- tems).
2. The number of keys used:
Symmetric (or single-key, secret-key, conventional) encryption:
Both sender and receiver use the same key.
Asymmetric (or two-key, or public key) encryption:
Sender and receiver each uses a di erent key.
3. The way in which the plaintext is processed:
Block cipher: Input is processed one block of elements at a time, producing an output
block for each input block.
Stream cipher: Input elements are processed continuously, producing an output of one
element at a time, as it goes along.
1.2.4 Modelofconventionalcryptosystems
The basic communications scenario can be depicted as follows:
There are two parties, usually called Alice and Bob (for A and B) who wish to communicate securely over an insecure channel. We assume that a third party has access to the insecure channel and thus to the ciphertext and, in certain scenarios, will also have access to the corre- sponding plaintext and might even be able to alter the ciphertext and/or impersonate Alice or Bob. In accordance with Kerckho s principle, we also assume that this party will know which cryptosystem is used and will know its inner workings. This party is often called Oscar (for opponent or observer), or Eve (for eavesdropper).
3
1.3 BasicConceptsofCryptanalysis
Cryptanalysis is as much an art as it is a science. Although some ciphers may be compu- tationally intractable, human ingenuity and intuition may help to crack them. (There are many examples of this throughout history).
1.3.1 Meansofcryptographicattacks
1. Mathematical:
Statistics (frequency distributions, etc.). Number theory.
Group theory.
Combinatorics and graph theory, etc.
2. Side information:
Linguistic (human language is full of redundancy). Formatting (such as Dear Dr. Dilcher).
Subject.
Known words or phrases (such as military ranks).
3. Cloak & Dagger methods:
Theft, bribery, blackmail, sex, violence.
1.3.2 Typesofcryptographicattacks
1. Ciphertext only:
The cryptanalyst has only the ciphertext to work with. Easiest type to defend against.
Example of this type of attack: exhaustive search.
2. Known plaintext:
Often the cryptanalyst has one or more plaintext messages along with corresponding
encryptions.
Closely related: Probable word attack.
3. Chosen ciphertext:
The cryptanalyst can cause a ciphertext of his choice to be decoded.
Both ciphertext and corresponding plaintext segments are then known. Similar: Chosen plaintext attack.
4
1.3 Basic Concepts of Cryptanalysis
1.4 SomeHistory
This is a selective list of some key dates (pun intended) and events in the history of cryptography.
Ancient Egyptians, Hebrews, Babylonians, Assyrians used protocryptographic systems.
ca. 400 BC: Spartans used the scytale for communications between military commanders.
First transposition cipher.
4th century BC: Chapter on cryptography in a book by Aeneas. Earliest treatise on the
subject.
Same time: Polybios encoded letters into pairs of symbols. First biliteral substitution.
ca. 50 BC: Caesar cipher: simple shift cipher.
Arab culture: First clear understanding of the principles of cryptology. 1412: Treatment
of several cryptosystems in an encyclopedia by al-Kalkashandi. First use of frequency
analysis.
1379: First European manual on cryptography, by Gabriele de Lavinde of Parma.
1470: First cipher disk, by Leon Battista Alberti.
1586: Blaise de Vigenere The Vigenere table.
17th 19th centuries: Rapid development of techniques.
1920s: Electromechanical devices used by most powers.
Both world wars: Cryptanalytical successes of greatest importance to (mostly) the Allied
forces.
1950s on: Use of electronic computers.
1976: Public key cryptography described by Di e and Hellman.
1977: Data Encryption Standard (DES) adopted.
1978: RSA (Rivest, Shamir, Adleman).
1980s: Elliptic curve cryptosystems.
2000/2001: Replacement of DES by the Rijndael algorithm as new Advanced Encryption
Standard (AES).
5
1.4 Some History
Chapter2 ClassicalCryptography
In this chapter we are going to study some basic principles of cryptography, along with several historical and insecure cryptosystems as examples. We will also consider modern block ciphers and stream ciphers, and two sections contain mathematical background that will be required in this chapter and throughout the course.
2.1 Cryptosystems 2.1.1 Basics
Definition 2.1.
A cryptosystem is a 5-tuple (P, C, K, E, D) with the following properties:
1. P is a set, called the plaintext space. Its elements are called plaintexts.
2. C is a set, called the ciphertext space. Its elements are called ciphertexts.
3. K is a set, called the key space. Its elements are called keys.
4. E = {Ek : k 2 K } is a family of functions Ek : P ! C. Its elements are called
encryption functions.
5. D = {Dk : k 2 K } is a family of functions Dk : C ! P. Its elements are called
decryption functions.
6. Foreache2K thereisad2K suchthat Dd(Ee(p))=p forallp2P.
|
Example 1. Shift ciphers.
LetP=C=K ={A,B,C,,Z}.Weidentifythissetwith={0,1,2,,25}according
to the table
Notation: Zm is the set {0,1,2,,m 1} along with the two operations + and which are carried out as in N, except that we reduce modulo 26. (More about this in the next section).
For e 2 Z26 we define the encryption function Ee by
Ee :!, x7!(x+e) (mod26).
For d 2 Z26 the decryption function Dd is defined by
Dd :!, x7!(x d) (mod26).
The decryption key belonging to the encryption key e is d = e.
Example: Apply the shift cipher with key e = 5 to the word cryptography. We get
HWDUYTLWFUMD.
A
B
C
Z
0
1
2
25
2.2 Mathematical Background I
Remarks:
1. When the key is e = 3, this is called the Caesar cipher.
2. The key space has only 26 elements. To cryptanalyze, we need only try all keys on a
segment of the ciphertext, until it makes sense.
3. Shift ciphers can be modified as follows: Let P and C be the set of all sequences
w = (w1,w2,,wn), with wi 2 , 1 i n. Again K = Z26. Now the function Ee replaces each wi with wi + e (mod 26), 1 i n.
4. The symbol is the capital Greek letter Sigma, and is pronounced this way.
5. Obviously, all this can be done with Zm, for any m 2.
6. Recall that d = e. We can use this as an alternative definition of a symmetric, resp. an
asymmetric cryptosystem: A cryptosystem is called
symmetric if d = e,
asymmetric if d , e, and the computation of d from e is not feasible.
2.1.2 Requirementsforagoodcryptosystem
A. Classical requirements (Claude Shannon, 1940): A good cryptosystem should
1. be highly secure against its designer, that is, the designer of the system should not have
any advantage in decryption;
2. use short, easily-changed key;
3. require only simple encryption/decryption;
4. not introduce error propagation;
5. not entail message expansion.
Remark: Requirements 2 5 reflect the fact that encryption/decryption used to be done manually by error-prone cipher clerks. They are less important with the use of computers.
B. Modern requirements:
1. As before.
2. As before keys must be small (but small is a relative term; keys can be many digits
long).
3. As before operations must be relatively simple (what computers do best), but we can do
many of them.
4. Some error propagation may even be desirable.
5. Moderate message expansion is now acceptable.
7
2.2 MathematicalBackgroundI 2.2.1 Congruences
Modular arithmetic and the basics of (abstract) algebra are of fundamental importance for cryptographic algorithms.
Definition 2.2.
Givena,b2Z,wesaythataiscongruenttobmodulom(writtenab (modm))ifm divides b a (written m | b a).
Examples: 2 19 (mod 21), 10 0 (mod 2).
2.2 Mathematical Background I
Remark: Congruence modulo m is an equivalence relation, that is, it satisfies the following relations:
1. a a (mod m) (reflexivity),
2. a b (mod m) implies b a (mod m) (symmetry);
3. a b (mod m) and b c (mod m) implies a c (mod m)
The following characterization is also useful.
Lemma 2.1.
The following statements are equivalent:
1. a b (mod m).
2. Thereisak2Zwitha=b+km.
3. When divided by m, both a and b leave the same remainder.
(transitivity).
|
We are now ready to define a basic concept in modular arithmetic:
Definition 2.3.
~
|
The equivalence class of a 2 Z is the set of all integers obtained from a by adding integer multiples of m, that is,
{b2Z|ba (modm)}=a+mZ. This is called the residue class of a (mod m).
Examples:1.Theresidueclassof1 (mod4)is{1,14,124,}={1, 3,5, 7,9,}. 2. The residue class of 0 (mod 2) is the set of all even integers; the residue class of 1
(mod 2) is the set of all odd integers.
3.Theresidueclasses (mod4)are0+4Z,1+4Z,2+4Z,3+4Z.
Notation: The set of residue classes (mod m) is denoted by Z/mZ. It has m elements since 0, 1, 2, . . . , m 1 are all the possible remainders upon division by m.
A set of representatives is a set of integers that contains exactly one element of each residue class (mod m).
8
2.2 Mathematical Background I
Examples: 1. {0, 1, 2}, {3, 2, 5}, and {9, 16, 14} are di erent sets of representatives of Z/3Z.
2. Foranym2N,theset{0,1,2,,m 1}isasetofrepresentatives (modm),called
the least nonnegative residues (mod m), denoted by Zm.
3. {1, 2, . . . , m} is a set of representatives, the least positive residues
Proposition 2.1.
Supposethatab (modm)andcd (modm).Then (a) a b (mod m),
(b) a+cb+d (modm),
(c) ac bd (mod m).
(mod m).
Proof (a) Since m divides a b, it also divides a + b, and therefore a b (mod m).
(b), (c): exercise.
Example: The integer F = 22n + 1 is called a Fermat number. Pierre de Fermat (16011665) n
observed that F0 = 3, F1 = 5, F2 = 17, F3 = 257, and F4 = 65 537 are all prime. He conjectured that all Fn are prime.
However, Leonhard Euler (17071786) showed that 641 | F5.
Proof Itisclearthat641=640+1=527+1,so527 1(mod641).ByProposition2.1(c)
we get by multiplying both sides of this congruence with itself 4-times over,
54 228 1 (mod 641). (2.1)
Ontheotherhand,641=625+16=54 +24,so
54 24 (mod 641).
Substituting this into (2.1), we get
24 228 1 (mod 641),
or 232 1 (mod641),i.e.,225 +10 (mod641). 2.2.2 Someabstractalgebra
Definition 2.4.
If X is a set, a map : X X ! X which sends a pair (x1, x2) of elements from X to the element x1 x2 is called an operation on X.
|
|
Example: Addition and multiplication are operations on X = R. Definition 2.5.
Given the residue classes a + mZ and b + mZ,
(i) their sum is (a + mZ) + (b + mZ) = (a + b) + mZ; (ii) their product is (a + mZ) (b + mZ) = (a b) + mZ.
9
2.2 Mathematical Background I
Remark: This definition uses representatives; however, by Proposition 2.1 sum and product are independent of representatives, that is, they are well defined.
Example: Let m = 5. Then
(3 + 5Z) + (2 + 5Z) = 5 + 5Z = 5Z;
(3 + 5Z) (2 + 5Z) = 6 + 5Z = 1 + 5Z.
Or: 3+20 (mod5); 321 (mod5). Definition 2.6.
A pair (H, ) consisting of a set H and an operation that satisfies (a b) c=a (b c) forall a,b,c2H
(i.e., the operation is associative,) is called a semigroup. If, in addition,
a b=b a forall a,b2H,
the semigroup is called commutative or abelian.
A neutral element of the semigroup (H, ) is an element e 2 H which satisfies e a = a e = a for all a 2 H. A semigroup with a neutral element is called a monoid.
|
Example: (Z, +), (Z, ), (Z/mZ, +), and (Z/mZ, ) are commutative semigroups. In fact, they are monoids.
Some properties: Let (H, ) be a semigroup, and set a1 = a and an+1 = a an for a 2 H and
n 2 N. Then
an am = an+m, (an)m = anm
for a 2 H and n, m 2 N. If a, b 2 H and a b = b a, then (a b)n = an bn. (This is true in general if the semigroup is commutative).
Definition 2.7.
Let (H, ) be a semigroup and e its neutral element. Given an a 2 H, an element b 2 H is called an inverse of a if a b = e = b a. An element a is called invertible in H if it has an inverse.
Remarks:
(a) A semigroup has at most one neutral element.
(b) In a monoid each element has at most one inverse.
Examples:
(Z, +): Neutral element is 0. Inverse of a is a.
(Z, ): Neutral element is 1. The only invertible elements are 1 and 1.
(Z/mZ, +): Neutral element is the residue class mZ. Inverse of a + mZ is a + mZ.
|
10
(Z/mZ, ): Neutral element is the residue class 1 + mZ. For the invertible elements, see the next subsection.
Definition 2.8.
A group is a monoid in which every element is invertible. A group is called commutative or abelian if the monoid is commutative.
2.2 Mathematical Background I
|
Examples: (Z, +) and (Z/mZ, +) are abelian groups. (Z, ) is not a group because not every element is invertible.
Some properties: Let (G, ) be a group. Denote by a 1 the inverse of a 2 G, and set a n = (a 1)n
for all n 2 N. Then
holds for all a 2 G and n,m 2 Z. If the group is abelian, then
an am = an+m, (an)m = anm (a b)n = an bn
holds for all n 2 Z.
An important property of a group is that we can cancel:
Proposition 2.2.
Let (G, ) be a group and a, b, c 2 G. Then ca = cb implies a = b, and
ac = bc implies a = b.
Definition 2.9.
The order of a group is the number of its elements.
Examples:
(a) The additive group Z has infinite order. (b) The additive group Z/mZ has order m.
Definition 2.10.
A ring is a triplet (R, +, ) such that (a) (R, +) is an abelian group,
(b) (R, ) is a semigroup,
(c) For all x, y, z 2 R we have
x (y + z) = (x y) + (x z),
|
(x + y) z = (x z) + (y z).
The ring is called commutative if the semigroup (R, ) is commutative. An identity (or unit element) of the ring is a neutral element of the semigroup (R, ). The property in (c) is called distributivity.
|
Examples:
11
2.2 Mathematical Background I
(1) (Z, +, ) is a commutative ring with identity 1. This implies: (2) (Z/mZ, +, ) is a commutative ring with identity 1 + mZ;
it is called the residue class ring modulo m.
Remark: If it is clear which operations are meant, we often write simply R for (R,+,); for
instance, we write Z/mZ for the residue class ring (mod m). Definition 2.11.
Let R be a ring with identity. An element a 2 R is called invertible, or a unit, if it is invertible in the multiplicative semigroup of R. An element a 2 R is called a zero divisor if a , 0 and there is a b , 0, b 2 R, with ab = 0 or ba = 0.
|
Remark: The units of a commutative ring form a group, the group of units of R, denoted by R.
Examples: (1) Z = { 1, 1}.
(2) Z has no zero divisors.
(3) Claim: The zero divisors of the residue class ring Z/mZ are the residue classes a + mZ
with 1 < gcd (a, m) < m.Proof (i)Ifa+mZisazerodivisorofZ/mZ,thenthereisab2Zwithab0 (modm),but a . 0 (mod m) and b . 0 (mod m). Hence m | ab, but m – a and m – b. So gcd (a, m) must lie strictly between 1 and m.(ii) Suppose that 1 < gcd(a,m) < m, and set b := m/gcd(a,m). Then a . 0 (mod m), ab=(a/gcd(a,m))m0 (modm),andb.0 (modm).Hencea+mZisazerodivisorof Z/mZ. Examples:Whenm=6,then230 (mod6);hence2+6Zisazerodivisor. Consequence: If m is a prime, then Z/mZ has no zero divisors. Definition 2.12.A field is a commutative ring in which every nonzero element is invertible. Examples: Q, R, C are fields. Z is not a field.2.2.3 DivisionintheresidueclassringDivisibility in rings is defined as in Z: Definition 2.13.|Let R be a ring and a, n 2 R. We say that a divides n if there is an element b 2 R such thatn=ab. Inthiscaseaiscalledadivisorofn,andnamultipleofa,andwewrite a | n (otherwise, a – n).|We will now restrict our attention to R = Z/mZ. Which elements in Z/mZ are invertible? Recall: The class a + mZ is invertible if and only if the congruenceax 1 (mod m) (2.2) 12is solvable. When is this the case?Proposition 2.3.The residue class a + mZ is invertible in Z/mZ (i.e., the congruence (2.2) is solvable) if and only if gcd(a, m) = 1. If gcd(a, m) = 1, then the inverse of a + mZ is uniquely determined (i.e., the solution of (2.2) is is uniquely determined modulo m.)Proof Later.Remarks: (a) A residue class a + mZ with gcd(a, m) = 1 is called an invertible residue class modulo m. By Proposition 2.3, a residue class a + mZ, 1 a < m, is either a zero divisor or an invertible residue class (i.e., a unit in the residue class ring Z/mZ).(b) The solution of (2.2), and thus the inverse of a + mZ (when gcd(a, m) = 1), can be computed e ciently with the Euclidean algorithm (see later).Example: Let m = 10. The class a + 10Z is invertible if and only if gcd(a, 10) = 1, i.e., when a = 1, 3, 7, 9. To obtain the inverses, note that371 (mod10), 731 (mod10), 991 (mod10). Proposition 2.4.Z/mZ is a field if and only if m is a prime number.Proof By Proposition 2.3, Z/mZ is a field if and only if gcd(k,m) = 1 for all k, 1 k < m.But this is the case if and only if m is a prime. Corollary 2.1.The set of all invertible residue classes modulo m is a finite abelian group with respect to multiplication.~Remark: This group is called the multiplicative group of residues modulo m, denoted by (Z/mZ).Definition 2.14.The Euler ‘-function ‘ : N ! N is defined as follows: If m 2 N, then ‘(m) is the order of (Z/mZ). In other words: ‘(m) is the number of integers a 2 {1, 2, . . . , m} with gcd(a, m) = 1.|Remarks: (a) In place of ‘-function you will sometimes see phi-function; in either case, it is pronounced like fee-function. The name Euler is pronounced like oiler.(b) The first few values of the ‘-function areIn particular: If p is prime, then ‘(p) = p 1. 132.2 Mathematical Background I m1 2 345 6 7 8 9 10 11 … ‘(m)1 1 224 2 6 4 6 4 10 …2.3 The A ne CipherThe Euler ‘-function will be studied in greater detail later. For now, here are two formulas for calculating ‘(n); they will have been derived in most !Discrete Mathematics courses: ‘(n)=nY 1 1 ,(2.3) p where the product is taken over all primes dividing n.p|n Ifn=pe1 …pek,(thecanonicalform),then1k'(n)=(pe1 pe1 1)…(pek pek 1). 11 kk(2.4) Examples: (a) Let n = 2000. The only prime divisors of n are 2 and 5. so by (2.3) we haveFor both formulas it is essential that n be completely factored. ‘(2000)=2000 1 1! 1 1!=200014=800.2525(b) Let n = 4116. The factorization is 4116 = 22 3 73. This time we use (2.4) to obtain'(4116) = (22 2)(3 1)(73 72) = 1176.We close this section with one last result on division in modular arithmetic. We have seen that addition, subtraction and multiplication modulo m are no problem. Also, when m is prime, we can cancel modulo m. But what happens when m is not prime?Example: Starting with the congruence 3 8 3 4 (mod 12), we see that 8 4 (mod 12) is certainly wrong. However, we do have 8 4 (mod 4). This is explained by the following result.Proposition 2.5.xaxb (modm)ifandonlyifab (mod m ). gcd(x,m) Proof Two directions need to be shown:(a) ): The first congruence can be rewritten as m | (xa xb), and then m | x(a b).Now denote d := gcd(x, m) and divide the last relation by d. Then m | x (a b), and since ddgcd( m, x ) = 1, we have m | (a b), which is equivalent to the second congruence. ddd(b) (: The second congruence is equivalent to m | (a b), which implies m | d(a b) dand also m | x(a b) since x is a multiple of d. This last relation is the same as m | (xa xb), and this is equivalent to the first congruence. 2.3 TheA neCipherIn this section we present a cipher that is easily broken using the methods from the previous sections. It is also the basis of some historical ciphers which we will consider later, in Section 2.8.14congruence for x. First,ax+by (modm) axy b (modm).Now, since gcd(a,m) = 1, there is a multiplicative inverse a 1 2 Zm such that a 1a 1 (mod m). Soora 1ax a 1(y b) (mod m), xa 1(y b) (modm).Therefore, given the encryption key k = (a, b), the decryption function is Dk(y)=a 1(y b) (modm).Example: Let m = 26. Alice wants to encipher the word bald with the key k = (a, b) = (7, 3). Note that gcd(7, 26) = 1. We use the translation table from Section 2.1; the steps are summarized in the following table:2.3 The A ne Cipher 2.3.1 DescriptionofthecipherIn Section 2.1 we considered the shift cipher as a special example of a substitution cipher. Its encryption function wasEk (x) = x + b (mod m), x 2 Zm,with key k = b 2 Zm.We now define the more general a ne cipher by the encryption functionEk (x) = ax + b (mod m), x 2 Zm, with key k = (a, b) 2 Z2m, and gcd(a, m) = 1.Why do we have this last condition?Suppose that gcd(a, m) = d > 1. We have seen (see Example (3) after Definition 11) that a + mZ is a zero divisor in Z/mZ, so the congruence ax 0 (mod m) has at least two solutions, namely x = 0 and x = m/d. Hence we would have
Ek (0) = b = Ek (m/d),
so the encryption function is not injective, which is not allowed.
Suppose now that we do have gcd(a, m) = 1. What is the decryption function? Solve the
plaintext
b
a
l
d
x
1
0
11
3
y7x+3 (mod26)
10
3
2
24
ciphertext
K
D
C
Y
15
2.4 Block Ciphers
To decipher, Bob has to find a 1. By inspection: 15 7 = 105 1 (mod 26) (later we will meetanalgorithmfordoingthis).Soa 1 =15,andthedecryptionfunctionisDk(y)=15(y 3) (mod 26). The steps are now:
2.3.2 Cryptanalysisofthea necipher
1. Ciphertext only:
Consider an a ne cipher with m = 26. Given a key k = (a, b), b can take on any value
b 2 Z26, while for a we require gcd(a, 26) = 1, so there are (26) = 12 possibilities. In total: the key space has only 12 26 = 312 elements; an exhaustive search is easily possible.
A di erent kind of ciphertext only attack can be found in the assignments.
2. Known plaintext or known ciphertext:
Example: Suppose that the eavesdropper Oscar knows that the a ne cipher (with m = 26)
with key k = (a, b) maps e to R and s to H. Then he obtains the following congruences 4a+b 17 (mod26) (frome7!R),
18a+b 7 (mod26) (froms7!H). Subtract the first congruence from the second one:
14a 10 16 (mod 26), or, upon dividing by 2 (using Proposition 2.5),
7a 8 (mod 13).
If we now multiply by 2 and note that 14 1 (mod 13), we get
a163 (mod13).
This means that either a 3 (mod 26), or a 16 (mod 26). The second case is not possible since gcd(16, 26) = 2, while the first case is allowable and leads to b 17 4a = 5 (mod 26). So, finally, the encryption key was k = (3, 5), and Oscar has broken the cipher.
2.4 BlockCiphers
Recall from the introduction: One criterion for classifying cryptosystems was block ci- phers versus stream ciphers. Here we are going to discuss block ciphers in general. First we need some more background material.
ciphertext
K
D
C
Y
y
10
3
2
24
x=15(y 3) (mod26)
1
0
11
3
plaintext
b
a
l
d
16
2.4.1 Alphabetsandwords
Definition 2.15.
An alphabet is a finite nonempty set . The length of is the number of elements in . The elements of are called symbols or letters.
|
2.4 Block Ciphers
Examples:
(1) = { A, B, . . . , Z }; length 26. (2) = {0, 1}; length 2.
(3) The ASCII symbols; length 128.
Ifanalphabethaslengthm,wecan(andoftenwill)identifyitwithZm ={0,1,,m 1}. Definition 2.16.
A finite sequence is a finite ordered set (a1, a2, . . . , an ); its elements (some of which may be identical) are called components. Sometimes we also write a1a2 . . . an. The empty sequence () has no components.
Example: (2, 3, 1, 2, 3), or 23123. Definition 2.17.
|
|
Example: Let X = {0, 1, . . . , 5}. An element in the first row of the following matrix is mapped to the number below:
*.0 1 2 3 4 5+/ ,1 2 4 3 5 0-
Example: Let = { A, B, . . . , Z }, v = DAL, w = HOUSIE. Then v w = DALHOUSIE. 2.4.2 Permutations
Definition 2.18.
Let X be a set. A permutation of X is a bijective map f : X ! X. The set of all permutations of X is denoted by S(X).
|
Let be an alphabet.
(1) A word or string over is a finite sequence of symbols from including the empty sequence, which is denoted by and called the empty string.
(2) The length of a word w over is the number of its components, and is denoted by |w|. Also, || = 0.
(3) The set of all words over including the empty string is denoted by .
(4) If v, w 2 , then vw = v w is the string that is obtained by concatenating v and w; it is called the concatenation of v and w. In particular, v = v = v.
(5) For n 2 N, n denotes the set of all words of length n over .
17
2.4 Block Ciphers
Permutations can always be represented like this.
Remark: The set S(X), together with composition, forms a group (in general non-commutative).
Proof By induction on n. (Usually covered in Abstract Algebra and Discrete Mathematics courses.)
Example: Let X = {0, 1}n, the set of all bitstrings of length n. A bit permutation is a permutation on X in which just the positions of the bits are permuted. Choose a permutation 2 Sn. Then put
f : {0,1}n ! {0,1}n, b1b2 bn 7! b(1)b(2) b(n).
Every bit permutation can be uniquely written in this way. Hence there are n! bit permutations
of bitstrings of length n.
Example: Circular leftshift of i positions: The bitstring (b0, b1 . . . bn 1) is mapped to
(bi (mod n), bi+1 (mod n), . . . , bi+n 1 (mod n) ). Circular rightshifts are defined analogously. 2.4.3 Blockciphers
Definition 2.19.
A cryptosystem is called a block cipher if its plaintext space and ciphertext space are n (n 2 N), the words of a fixed length n over an alphabet . The integer n is called the block length.
|
Example: A shift cipher is a block cipher of length 1. In general, block ciphers of length 1 are called substitution ciphers.
Ifn2N,Sn denotesthegroupofpermutationsoftheset{1,2,,n}. Example: S2 consists of the two elements 1 2 , 1 2 .
12 21 ThegroupSn hasordern!=12n.
Proposition 2.6.
Proposition 2.7.
The encryption functions of a block cipher are permutations.
Proof We know that encryption functions are injective (Assignment 1). But an injective map from a finite set A ! A (here A = n) must be bijective, i.e., a permutation.
The most general block cipher can be described as follows:
Fix block length n and alphabet .
UseP=C=n.
Key space is K = S(n).
Encryption function for a key 2 S(n): E :n !n, v7!(v).
18
Decryption function:
D :n !n, v7! 1(v).
The key space is very large; it contains (||n)! elements. The problem with this is that it is very ine cient to use; it is not clear how to represent and evaluate a permutation 2 S(n) e ciently. In practice, therefore, only a subset of all possible permutations of n is used; it is chosen
such that the permutations are easy to represent and to evaluate.
Example: The permutation cipher. We use only permutations that permute positions of the
symbols. For 2 Sn, set
E : n ! n, (v1,,vn) 7! (v(1),,v(n));
so the key space is the group of permutations Sn. Decryption function:
D :n !n, (x1,,xn)7!(x 1(1),,x 1(n)). Remarks: (a) If = {0, 1}, these are the bit permutations.
(b) The key space has n! elements.
2.5 ModesofBlockCipherOperation
2.5.1 ECBmode
We use a block cipher with alphabet and block length n. Let K be the key space and Ek, Dk the encryption and decryption functions for k 2 K .
The electronic codebook mode (ECB mode) is used as follows:
An arbitrarily long plaintext is decomposed into blocks of length n; if necessary, supple-
ment plaintext (for instance, by randomly chosen symbols) such that its length is divisible by n.
2.5 Modes of Block Cipher Operation
19
2.5 Modes of Block Cipher Operation
Each block of length n is encrypted using the encryption function Ee.
The ciphertext is decrypted by applying the decryption function Dd to the blocks of length
n, where the decryption key d corresponds to the encryption key e.
In short, this mode amounts to each block being looked up in a codebook.
ECB mode is illustrated in the diagram above
Example: Take = {0, 1}, block length n = 4, and the permutation cipher. So K = S4, and for
2 S4,
E : {0,1}4 ! {0,1}4, b1b2b3b4 7! b(1)b(2)b(3)b(4).
Suppose we have the plaintext
m = 101100010100101.
Decompose it into blocks of length 4. The last block has length 3, so we add a random bit, say
0. So we have the blocks
m1 = 1011, m2 = 0001, m3 = 0100,m4 = 1010.
We use the key = 1 2 3 4 , so b1b2b3b4 7! b2b3b4b1. The blocks are encrypted separately, 2341
and we get the ciphertext blocks
c1 = E(m1) = 0111, c2 = E(m2) = 0010,
c3 = E(m3) = 1000, c4 = E(m4) = 0101. So the ciphertext is c = 0111001010000101.
The main weaknesses of ECB mode are as follows:
The same plaintext blocks give rise to the same ciphertext blocks. Di erences in frequen-
cies may therefore be apparent, and be exploited by the eavesdropper Oscar.
Oscar can also change the ciphertext and not be detected.
2.5.2 CBCmode
The cipherblock chaining (CBC) mode avoids the weaknesses of ECB mode. Here: en- cryption of a block depends not only on the key, but also on the previous block. In other words: Encryption is context dependent, in the sense that equal texts in di erent contexts are enciphered di erently. The ciphertext can therefore not be manipulated; manipulations will be detected.
We need the following fundamental operation:
Definition 2.20.
(a) The map : {0,1}2 ! {0,1}, (b,c) 7! b c, called the exclusive or of two bits, or XOR, is defined by the following table:
20
2.5 Modes of Block Cipher Operation
bcb c 000 101 011 110
(b) If k 2 N, b = (b1,b2,,bk), c = (c1,c2,ck) 2 {0,1}k, then we set b c = (b1 c1,b2 c2,,bk ck).
Remark: If {0, 1} is a system of representatives of Z/2Z, then is the same as addition in Z/2Z.
Example: Ifb=0100andc=1101;thenb c=1001.
CBC mode works as follows:
As before, use a block cipher with alphabet = {0, 1}, block length n, key space K , and
encryption and decryption functions Ek and Dk for k 2 K .
Use a fixed initialization vector IV 2 n which need not be kept secret.
Theplaintextisdecomposedintoblocksoflengthn(asinECBmode),saym1,m2,,mt.
Alice obtains the ciphertext by setting
c0=IV, and cj=Ee(cj 1 mj) for 1jt;
the ciphertext is then c = c1c2 . . . ct .
To decipher, Bob uses the decryption key d that satisfies Dd (Ee (w)) = w for all plaintext
blocks w. Then he computes
c0=IV, and mj=cj 1 Dd(cj) for 1jt. (2.5)
CBC mode can be illustrated as follows:
|
21
2.5 Modes of Block Cipher Operation
Remark: Why does this work? For 1 j t, set
cj 1 Dd(cj) = cj 1 Dd(Ee(cj 1 mj))
= cj 1 (cj 1 mj)=(cj 1 cj 1) mj = 0 mj=mj.
Example: Use the same block cipher, same plaintext, and same key as in the previous example, namely plaintext blocks m1 = 1011, m2 = 0001, m3 = 0100, m4 = 1010, and key = 1 2 3 4 .
We choose the initialization vector IV = 1010. Then
c1= E(c0 m1)=E(0001)=0010,
c2= E(c1 m2)=E(0011)=0110,
c3= E(c2 m3)=E(0010)=0100,
c4= E(c3 m4)=E(1110)=1101.
So the ciphertext is c = 0010011001001101.
The decryption works as follows (note that here we have D = E 1, the inverse in the group
of permutations):
d
m = c E 1(c)=1010 0001=1011, 101
m = c E 1(c)=0010 0011=0001, 212
m = c E 1(c)=0110 0010=0100, 323
m = c E 1(c)=0100 1110=1010, 434
and we (i.e., Bob) have recovered the plaintext.
Remark: What are the e ects of transmission errors? Consider the decryption process (2.5). If the ciphertext block cj is transmitted incorrectly, then mj and mj+1 may be incorrect, but everything after that will not be influenced.
2.5.3 CFBmode
A disadvantage of the CBC mode is that encryption and decryption of blocks are done sequentially. Encryption and decryption functions may be expensive to compute, which may lead to time lags. For some applications, however, (for instance, secure telephone communications), real-time encryption and decryption are necessary. This time-lag problem is reduced in cipher feedback mode (or CFB mode). The main di erence to CBC mode is that the encryption function is
not used directly for encrypting plaintext blocks, but used for generating a sequence of key blocks.
CFB mode works as follows:
As before, we use a block cipher with alphabet = {0, 1}, block length n, key space K ,
and encryption function Ek for k 2 K .
22
2341
2.5 Modes of Block Cipher Operation
Use a fixed initialization vector IV 2 n.
Choose an integer r, 1 r n, and decompose the plaintext into blocks of length r.
To encrypt the sequence m1, m2, . . . , mu of plaintext blocks, Alice sets
I1 = IV, and for 1 j u:
(1) Oj =Ek(Ij),
(2) tj is the string consisting of the first r bits of Oj,
(3) cj =mj tj,
(4) Ij+1 = 2r Ij + cj (mod 2n), i.e., Ij+1 is obtained by deleting the first r bits in Ij and
appending cj .
Theciphertextisthesequencec1,c2,,cn.
To decrypt, Bob sets I1 = IV, and for 1 j u:
(1) Oj =Ek(Ij),
(2) tj is the string consisting of the first r bits of Oj, (3) mj =cj tj,
(4) Ij+1 = 2r Ij + cj (mod 2n) (as before).
CFB mode can be illustrated as follows:
Remarks:
(1) Why does this work? We have
cj tj =(mj tj) tj =mj (tj tj)=mj.
(2) Both Alice and Bob compute the string tj+1 as soon as they know the ciphertext block cj.
(3) Only the XORs are computed sequentially; this is fast.
(4) CFBmodecannotbeusedwithpublic-keycryptographysincebothAliceandBobusethe
same key.
(5) Transmission errors: Decryption is spoiled as long as parts of the wrong ciphertext block
are in the vector Ij.
23
2.6 Stream Ciphers
2.5.4 OFBmode
The output feedback mode (OFB mode) is very similar to the CFB mode. Everything is the same up to
For 1 j u:
(1) Oj =Ek(Ij),
(2) tj is the string consisting of the first r bits of Oj, (3) cj =mj tj,
(4) Ij+1 =Oj.
Decryption works analogously again, with Step (3) replaced by mj = cj tj. OFB mode can be illustrated as follows:
Remarks:
(1) The key block tj depends only on IV and the key k; it can be computed simultaneously by Alice and Bob. (This is even more e cient than in CFB mode).
(2) Weakness: While encryption of a plaintext block does depend on its position, it does not depend on the previous plaintext blocks. This makes ciphertext manipulation easier than in CFB mode.
(3) Ifabitofciphertextisincorrectlytransmitted,onlythisonebitofplaintextwillbea ected.
2.6
StreamCiphers
A general theory of stream ciphers is described in the textbook (1) by Stinson. Here I will present only a particular example.
With the alphabet = {0, 1}, let the plaintext and ciphertext spaces be P = C = . The key space is K = n for some n 2 N. Words in are encrypted bit by bit as follows:
24
2.7 Mathematical Background II: Linear Algebra
(1) Letk=(k1,k2,,kn)2K.
(2) Letw= 1 1 m beawordoflengthmin.
(3) Alicegeneratesakeystreamz1,z2,,zm bysettingz1 =k1,z2 =k2,,zn =kn,and
for m > n,
where c0, c1, . . . , cn 1 are fixed coe cients.
(4) Then the encryption function Ek is defined by
Ek(w) = 1 z1, 2 z2,, m zm.
(5) The decryption function is the same, namely
Dk(w) = 1 z1, 2 z2,, m zm.
(It is easy to see that this is a cryptosystem).
Example: Letn=4,andchoosec0 =c1 =1,c2 =c3 =0,so
zi+4 = zi zi+1. Let the key be k = (1,0,0,0); the key stream is then
1,0,0,0,1,0,0,1,1,0,1,0,1,1,1,1,0,0,0, | {z }
k
This is periodic with period length 15.
Remarks:
(2.7)
n 1 X
(2.6)
zi+n = cjzi+j (mod2) j=0
n
Xn
det A = ( 1)i+jai,j det Ai,j.
j=1 Remarks: (1) The matrices Ai, j are called minors.
|
(2)ThevalueofdetAisindependentofthechoiceofi. Also,forall j 2 {1,2,,n}we
have
This is called a column expansion of the determinant, while the formula in the definition is a row
Xn
det A = ( 1)i+jai,j det Ai,j.
i=1
expansion.
Example:IfA=a1,1 a1,2,thenA =(a ),A =(a ),A =(a ),andA =(a ).
a2,1 a2,2 1,1 2,2 1,2 2,1 2,1 1,2 2,2 1,1 det A = a1,1a2,2 a2,1a1,2.
Hence
We will make repeated use of this formula.
Definition 2.24.
(a) A matrix A 2 R(n,n) which has a multiplicative inverse is called invertible. (b) The adjoint of A is the n n matrix defined by
adj A = ( 1)i+j det Aj,i . Example: If A= a1,1 a1,2 ,thenadjA= a2,2 a1,2 .
Proposition 2.8.
(a) A matrix A 2 R(n,n) is invertible if and only if det A is a unit in R. (b) If A is invertible then
|
a2,1 a2,2 a2,1 a1,1
A 1 = (det A) 1adj A.
The most important special case for our purposes arises when R = Z/mZ. To deal with this
case, we first introduce some
Notation: Let A = (ai,j), B = (bi,j) 2 Z(n,n) and m 2 N. We write
AB (modm) ifai,j bi,j (modm)forall1i,jn.
27
2.7 Mathematical Background II: Linear Algebra
The following is an immediate consequence of Proposition 2.8:
Proposition 2.9.
Given an A 2 Z(n,n), the congruence
AA0 In (mod m) (2.8)
is solvable if and only if gcd(det A, m) = 1. In this case, if a is an inverse of det A (mod m), then
A0aadjA (modm) is a solution of the congruence (2.8),
Example: Let A = 1 2 . Does the congruence 34
AA0 I2
(mod 11)
have a solution? If so, find it.
Solution. We find det A = 1 4 3 2 = 2, which is coprime to 11 (i.e., gcd( 2, 11) = 1),
so the congruence is solvable. Note that ( 2)( 6) 1 (mod 11), so (det A) 1 6 5 (mod11).NowadjA=4 2,andso
31
A0=5 4 2 = 20 10 91 (mod11).
3 1 15 5 7 5 2.7.3 A nelinearfunctions
Recall that the a ne cipher was, in fact, a block cipher of block length 1. In the next section we generalize a ne ciphers to arbitrary block lengths. But first we need some more concepts and results from linear algebra.
Definition 2.25.
A function f : Rn ! Rl is called a ne linear if there is a matrix A 2 R(l,n) and a vector
b 2 Rl such that
for all v 2 Rn. If b = 0, then the function is called linear.
f (v) = Av + b (2.9)
|
Once again we consider the important special case R = Z/mZ. Recall that Zm = {0, 1, . . . , m 1}, the set of least nonnegative residues mod m.
Definition 2.26.
A function f : Znm ! Zlm is called a ne linear if there is a matrix A 2 Z(l,n) and a vector
b 2 Zl such that
for all v 2 Znm. If b 0 (mod m), then the function is called linear.
f(v)=Av+b (modm) (2.10)
|
28
Proposition 2.10.
The a ne linear map (2.9) is bijective if and only if l = n and det A is a unit in R.
Example: Consider the map f : {0, 1}2 ! {0, 1}2 defined by
f(0,0) = (0,0), f(1,0) = (1,1),
f(0,1) = (1,0), f(1,1) = (0,1).
This can be written as Hence f is linear.
Proposition 2.11.
f(v)=11v forall v2{0,1}2. 10
2.8 A ne Linear Block Cipher
We recall that a corollary is a commonly used mathematical term which means conse- quence of a previous theorem or proposition. And indeed, the following is an easy consequence of Proposition 2.10.
Corollary 2.2.
The a ne linear map (2.10) is bijective if and only if l = n and gcd(det A, m) = 1.
~
(1)Afunction f : Rn ! Rn islinearifandonlyif
f (av + bw) = a f (v) + b f (w)
for all v, w 2 Rn and all a, b 2 R.
(2) The function is a ne linear if and only if the function Rn ! Rn defined by v 7!
f (v) f (0) is linear.
2.8 A neLinearBlockCipher
Several famous historical cryptosystems turn out to be a ne linear block ciphers, and can be easily broken.
2.8.1 Thecipheringeneral
Let n 2 N be the block length, and m 2 N, m > 2. Definition 2.27.
A block cipher with block length n and P = C = Zm is called a ne linear (resp. linear) if its encryption functions are a ne linear (resp. linear).
|
By definition, the encryption functions must be of the form E:Znm!Znm, v7!Av+b (modm),
where A 2 Z(n,n), b 2 Zn. For this to be a cryptosystem, E must be injective, hence bijective. By 29
2.8 A ne Linear Block Cipher
the Corollary to Proposition 2.10, gcd(det A, m) = 1. Hence the encryption function is uniquely determined by the key
(A,b)2Z(n,n)Zn, where gcd(detA,m)=1. The corresponding decryption function is then
D:Znm!Znm, v7!A0(v b) (modm), where A0 = a0 adj A (mod m), with a0 an inverse of det A (mod m).
Remark: The size of the key space depends on the number of invertible matrices modulo m. There is a formula, but it is too involved to give here. Note that the number of all matrices over Zm ismn2.
2.8.2 Vigenere,Hill,andpermutationciphers
1. The Vigenere cipher (Blaise de Vigenere, 15231596). The key space is K = Znm. For
a k 2 Znm we have and
Ek:Znm!Znm, v7!v+k (modm), Dk:Znm!Znm, v7!v k (modm).
It is clear that Ek and Dk are a ne linear (A = In, so det A = 1). The number of elements in K is mn.
2. The Hill cipher (Lester S. Hill, 18911961). The key space is K ={A2Z(n,n) |gcd(detA,m)=1}.
For A 2 K we have and
EA:Znm!Znm, v7!Av (modm), Dk:Znm!Znm, v7!A0v (modm),
with A0 the inverse matrix modulo m, as in the previous subsection. In other words, the Hill cipher is the most general linear block cipher.
3. The permutation cipher (see Section 2.4). Let 2 Sn, and let ei, 1 i n, be the unit vectors, namely the row vectors of the identity matrix In. Now let E be the n n matrix whose ith row vector is e(i), 1 i n, i.e., the rows of In are permuted according to the permutation . Now, for any vector v = (v1, v2, . . . , vn ) 2 Znm we have
(v(1),v(2),,v(n)) = Ev.
Hence the permutation cipher is a linear cipher (note that det E = 1), and thus a special case of the Hill cipher.
30
2.8.3 Cryptanalysisofa nelinearblockciphers
For a possible ciphertext-only attack, see the assignments. Here I will describe a known plaintext attack. Suppose Alice and Bob use an a ne linear cipher with key
the encryption function is
k = (A, b) 2 Z(n,n) Zn; Ek:Znm!Znm, v7!Av+b (modm).
Suppose that Oscar has n + 1 plaintext blocks wi, 0 i n, and the corresponding ciphertext blocks
ciAwi+b (modm), 0in.
By subtracting the congruence for i = 0 from the other n congruences, he gets ci c0=A(wi w0) (modm), 1in.
Now let W be the matrix
W=(w1 w0,w2 w0,,wn w0) (modm),
(2.11) (2.12)
where the columns are the vectors wi w0 (mod m), 1 i n, and similarly, let C be the matrix C=(c1 c0,c2 c0,,cn c0) (modm).
Then by the rules of matrix multiplication Oscar can rewrite (2.12) as AWC (modm).
If gcd(det A, m) = 1, then he can solve this matrix congruence by multiplying by W 0 from the right; hence, by Proposition 2.9,
ACW0C(w0adjW) (modm), where w0 is the inverse of det W modulo m. Also, from (2.11) he gets
b c0 Aw0 (mod m).
Thus, Oscar has obtained the key ( A, b) from n + 1 pairs of plaintext and ciphertext blocks. If the cipher is linear, then Oscar has w0 = c0 = b = 0. If he knows about linearity beforehand, then n pairs would su ce.
Remark: This shows that any linear or a ne linear cipher is insecure.
Example: We want to break a Hill cipher with block length n = 2 and m = 26. Suppose we know that hand is encrypted as FOOT. Hence we have the two plaintext-ciphertext pairs (see the table in Section 2.1)
w1 =ha= (7,0) 7! c1 =FO= (5,14),
w2 =nd= (13,3) 7! c2 =OT= (14,19).
SoW=713andC=5 14.NowdetW=21,sogcd(detW,26)=1,andalso21 15 0 3 14 19
31
2.8 A ne Linear Block Cipher
W053 131513 (mod26) 07 09
ACW05141513239 (mod26), 141909 215
32
2.8 A ne Linear Block Cipher
(mod 26). So
and
and thus the cipher is broken.
Chapter3 ProbabilityandPerfectSecrecy
We have seen several historical cryptosystems which, as a ne linear ciphers, are insecure. Are there secure cryptosystems? How can we define perfect secrecy? To discuss these questions, we need some basic concepts and results from probability theory.
3.1 BasicsofProbabilityTheory 3.1.1 Probability
Definition 3.1.
Suppose we have an experiment with a finite number of outcomes. Then the sample space S is the set of these outcomes. Its elements are called elementary events.
|
Examples:
(a) Ifweflipacoin,thenwegeteitherheads(H)ortails(T).SothesamplespaceisS = {H,T}. (b) If we throw a die, then the sample space is S = {1,2,3,4,5,6}.
Definition 3.2.
Given the sample space S,
(a) an event (for S) is a subset of S;
(b) the certain event is the set S itself;
(c) the null event is the empty set ;;
(c) two events A and B are mutually exclusive if their intersection is empty (i.e., A B = ;). |
Example: If we throw a die, then obtaining an even number is an event. According to the definition, this is the subset {2, 4, 6} of the sample space S = {1, 2, . . . , 6}. It excludes the event {1, 3, 5} of throwing an odd number.
Definition 3.3.
Let P(S) be the power set of S, i.e., the set of all events for S. A probability distribution on S is a map
p : P(S) ! R
with the properties
(1) p(A) 0 forallevents AS;
(2) p(S) = 1;
(3) p(A [ B) = p(A) + p(B) if the two events A, B are mutually exclusive.
If A is an event, p(A) is called the probability of A. For an elementary event a 2 S, we define p(a) = p({a}).
|
Properties:
(1) p(;) = 0.
(2) IfAB,thenp(A)p(B).
(3) 0p(A)1forallA2P(S).
(4) p(SA)=1 p(A).
(5) If A1, A2, . . . , An are pairwise mutually exclusive events, then
Remarks:
(1) These properties follow almost directly from the definition. For proofs of (1) and (2), see Assignment 5.
(2) SinceSisafiniteset,itsu cestodefinetheprobabilitydistributiononelementaryevents, by Property (5).
(3) For the same reason, we have for any event AX S,
p(A) = p(a). a2A
(4) A random variable is some function on the sample space. For instance, if two dice are thrown, the sum of the dots would be a random variable on the set of all pairs S = {1, 2, . . . , 6}2. We will not use this term in this course.
*[n + Xn
p Ai = p(Ai).
,i=1 i=1
Examples: (a) The probability distribution of throwing a fair die is the function p : {1, . . . , 6} ! Rgivenbyp(a)=1 foralla2S={1,,6}.
6
(b) The probability of the event even result is
3.1 Basics of Probability Theory
p({2, 4, 6}) = p(2) + p(4) + p(6) = 1 + 1 + 1 = 1 . 6662
Remark: The probability distribution that maps each elementary event a 2 S to the probability p(a) = 1 is called the uniform distribution.
|S|
3.1.2 Conditionalprobability
Example: You throw a fair die, so the sample space is S = {1, 2, . . . , 6}, and the probability distribution is p(a) = 1 for all a 2 S. Now suppose you have thrown one of the numbers {4, 5, 6},
6
i.e., the event B = {4, 5, 6} has happened. Given this assumption, what is the probability that you
have thrown an even number?
Each elementary event in B is equally likely, and so has probability 1 . Since two numbers
in B are even, the probability that you have thrown an even number is 2 . 3
How can we express this symbolically?
Let A = {2, 4, 6} and, as before, B = {4, 5, 6}. Then the elementary events in question are
the members of the set A B = {4, 6}. However, the event B = {4, 5, 6}, which has probability 34
3
3.1 Basics of Probability Theory
1 , occurred with certainty, so we must divide by 1 . Thus, the probability of A, given that B 22
occurs, is
This suggests the following definition.
p(AB)= p({4,6}) =1/3=2. p(B) p({4, 5, 6}) 1/2 3
Definition 3.4.
Let S be a sample space, A and B events for S, and p a probability distribution on S. If p(B) > 0, the conditional probability of A given that B occurs is defined to be
p(A | B) = p(A B). p(B)
Another term is closely related to this:
Definition 3.5.
With S and p as before, two events A and B are called independent if p(A B) = p(A)p(B).
(3.1)
|
(3.2) Remark: It is clear form (3.1) and (3.2) that independence of two events A and B is equivalent
If the events are not independent, they are called dependent. to p(A | B) = p(A).
Examples: (a) We flip two coins. The event first coin comes up tails (probability 1) is 2
independent from the event second coin comes up tails (probability 1 ). The probability that
2
(b) If the coins are welded together so that either two heads or two tails come up, then the
|
both events occur is therefore 1 1 = 1 . 224
probability of two tails is 1 , 1 1 . So the two events of (a) are dependent. 222
Proposition 3.1.
(Theorem of Bayes) Let S and p be as before, and A,B be events with p(A) > 0 and p(B) > 0. Then
p(B)p(A | B) = p(A)p(B | A).
Proof By (3.1) we have p(B)p(A | B) = p(A B) and p(A)p(B | A) = p(A B). The result
now follows by equating the two. 3.1.3 An example: the birthday paradox
Problem: Suppose there are k people in a room. What is the probability that two them have the same birthday?
Related to this is the question: How many people do you need to have in the room so that with probability 1/2 two of them have the same birthday?
The answer is surprisingly low (and is therefore referred to as the birthday paradox): With as few as 23 people the probability is already slightly higher than 1/2.
35
3.1 Basics of Probability Theory
To be able to use the solution of this problem for cryptographic purposes (and not just as a neat example of probability theory), we consider a more general situation:
Suppose there are n possible birthdays, and k people are in the room. Then the formal setting is as follows:
ThesamplespaceisS={1,2,,n}k.
An elementary event is the k-tuple (b1,b2,,bk) 2 S, meaning that the ith person has
birthday bi, 1 i k.
Hence there are nk elementary events.
We assume that the elementary events are equally probable, so p(a) = 1/nk for all a 2 S.
Now let p be the probability that two people have the same birthday. Then the probability that any two people have di erent birthdays is q = 1 p. To determine this probability, we consider the event
E={(b1,b2,,bk)2S|bi,bj for 1i
the probability distribution on K is the uniform distribution, and if
foranyw2Pandanyc2Cthereisexactlyonek2KwithEk(w)=c.
Proof ): Suppose the cryptosystem has perfect secrecy. Let w 2 P.
(i) If there is a c 2 C for which there is no k 2 K with Ek (w) = c, then
0 = p(w | c) , p(w) > 0, 39
3.2 Perfect Secrecy
and this contradicts perfect secrecy. Hence for any c 2 C there is at least one k 2 K with Ek (w) = c. But there cannot be more than one key since |K | = |C|. This proves the second assertion.
(ii) Fix a c 2 C, and let k(w) be the key with Ek(w)(w) = c. By the theorem of Bayes we
have
p(w|c)= p(c|w)p(w) = p(k(w))p(w) (3.9) p(c) p(c)
for each w 2 P. Since the system has perfect secrecy, we have p(w | c) = p(w), so (3.9) implies
p(k(w)) = p(c),
thatis,p(k(w))isthesameforeachw2P. Butanykeyk2Kisequaltok(w)forsome w 2 P. Hence the probability for all keys is the same, so the probability distribution on K is uniform.
(: Assume the two statements hold, and let k (w, c) be the unique key k with Ek (w) = c. Then by the theorem of Bayes,
p(w) p(c | w) p(w) p(k(w,c)))
p(w | c) = p(c) = Px2P p(x)p(k(x,c)). (3.10)
Now, by assumption we have p(k(w, c)) = 1/|K |, and so
X p(x)p(k(x, c)) = 1 X p(x) = 1 = p(k(w, c)).
x2P |K| x2P |K|
Hence by (3.10) we have p(w | c) = p(w), and perfect secrecy follows.
Example: If the 26 keys of the shift cipher are used with equal probability 1 , then the shift 26
cipher has perfect secrecy.
Indeed,wehaveP=C=K =Z26,andtheencryptionfunctionisEk(w)=w+kfor
w2Pandk2K. So,givenw2Pandc2CwithEk(w)=c,thereisexactlyonekey k c w (mod 26). Therefore, by Shannons theorem, the shift cipher has perfect secrecy.
Remark: It is important to note that a new random key must be used to encrypt for every plaintext character.
3.2.2 TheVernamone-timepad
Gilbert S. Vernam (1890 1960) invented and patented in 1917 the famous Vernam one-time pad: Let
P=C=K ={0,1}n.
For k 2 K , the encryption function is
Ek:{0,1}n!{0,1}n, w7!w k. The decryption function is the same.
In practice, to encrypt a plaintext w 2 {0,1}n, Alice chooses a key randomly with uniform distribution from the set {0, 1}n, and then computes the ciphertext c = w k.
40
3.3 Random and Pseudo-random Numbers
This cryptosystem has perfect secrecy by Shannons theorem: (i) Uniform distribution is used on the key space, and (ii) given a plaintext w and a ciphertext c, there is exactly one key k with c = w k. Indeed, XOR w to both sides of this last relation, to obtain
w c = w (w k) = (w w) k = k. (3.11)
The main drawback of this system is that the one-time pad is not very e cient: To com- municate a plaintext of length n, a key of length n must be randomly generated and exchanged. It cannot be reused: If Oscar knows the plaintext w and the corresponding ciphertext c, then he can obtain the key k by way of (3.11).
Still, the Vernam one-time pad is useful in situations where perfect secrecy is of the utmost importance.
3.3 RandomandPseudo-randomNumbers
We have seen that it is of great importance to have a source of random numbers (or random bits). Systems to create them, also known as random number generators, can be hardware-based or software-based.
1. Hardware-based systems use, for instance,
the randomness of radioactive decay;
the thermal noise from a semiconductor resistor; the time between two keyboard strokes.
Most of these systems are slow and/or expensive to implement.
2. Software-based systems are typically pseudo-random number (or bit) generators. These are algorithms that, given a short sequence of random bits, produce a long sequence of bits that look random.
There are many pseudo-random number generators of various quality. We will not deal with this topic in this course; for more details, see the book (1) by Stinson.
41
Chapter4 ModernClassicalCryptosystems
In Chapter 2 we defined cryptosystems and studied some historical examples. Most turned out to be a ne linear, and can therefore be easily broken. In Chapter 3, on the other hand, we saw that the Vernam one-time pad is a cryptosystem with perfect secrecy, but it is ine cient to use.
In this chapter we will study two modern cryptosystems that use a key of limited size to encrypt a relatively long string of plaintext (i.e., use the same key for many messages), while ensuring at least computational security, that is, they make breaking the cipher with any cryptanalytic attack a computationally di cult problem.
4.1 TheDataEncryptionStandard(DES)
In 1973 the U.S. National Bureau of Standards (now called the National Institute of Standards and Technology NIST) issued a call for a cryptosystem that was to become a national standard. In 1975, the DES was first published, and in 1977 it became the o cial standard. It has now been largely superseded by the Advanced Encryption Standard (AES, which we will study in Section 4.3), but its design principles are still of interest.
4.1.1 Feistelciphers
The DES belongs to a class of more general cryptosystems called Feistel ciphers, named after Horst Feistel of IBM. A Feistel cipher works as follows.
1. We have a block cipher, which we call the underlying or the internal block cipher with alphabet{0,1};
block length t;
encryption function fK for the key K in this block ciphers key space Kint.
2. The Feistel cipher constructed with this internal block cipher is itself a block cipher as follows:
The alphabet is again {0, 1};
block length is 2t;
there is an integer r 1 counting the number of rounds;
the key space is K;
given a key k 2 K, there is a method that generates a sequence K1,K2,,Kr of round
keys that belong to the key space Kint of the internal block cipher.
3. The encryption function Ek for a key k 2 K is then defined as follows: Let w be a plaintext of length 2t.
Figure 4.1: Feistel encryption and decryption
Split it into 2 halves of length t, and set w = (L0, R0), where L0 is the left half and R0 is the right half.
For 1 i r construct the sequence
(Li, Ri) = (Ri 1, Li 1 fKi (Ri 1)). (4.1)
Finally, set
Ek (w) = (Rr, Lr ).
4. To decrypt, we have to reverse the process, trying to go backwards. First, from (4.1) we have that Ri 1 = Li. Then the second components in (4.1) give, if we XOR fKi (Ri 1) to both sides,
Li 1 = (Li 1 fKi (Ri 1)) fKi (Ri 1) = Ri fKi (Ri 1) = Ri fKi (Li). Together, we have for 1 i r,
(Ri 1, Li 1) = (Li, Ri fKi (Li)).
Using this in r rounds with the reverse key sequence (Kr, Kr 1, . . ., K1), we obtain the plaintext
pair (R0, L0) from the ciphertext pair (Rr, Lr ). 43
4.1 The Data Encryption Standard (DES)
Remarks:
(1) We see that for the Feistel cipher, encryption and decryption are the same, except that the key sequence is reversed.
(2) The security of the Feistel cipher depends on the security of the underlying internal block cipher.
4.1.2 TheDESAlgorithm
The DES is a slightly modified Feistel cipher with block length 2t = 64 and r = 16 rounds.
1. Plaintext, ciphertext, and key spaces:
P=C={0,1}64.
Keys are elements of {0, 1}64.
Ifakeyisdividedinto8bytes,thenthebitsumofeachbyteisodd(i.e.,7bitsofeachbyte
determine the eighth bit).
This means that the key space is
K = {(b1,,b64) 2 {0,1}64 |
Therefore |K | = 256 7.2 1016.
2. The initial permutation: Given a plaintext w 2 {0, 1}64,
X8 i=1
b8k+i 1
(mod 2),0 k 7}.
Apply the initial permutation IP, to obtain IP(w) 2 {0, 1}64.
Then apply the Feistel cipher to IP(w), with output (R16, L16).
Finally, use the inverse permutation IP 1:
c = IP 1(R16L16).
The initial permutation is defined in Table 4.1; it is to be read as follows: If w = w1w2w3 . . . w64, then IP(w) = w58w50w42 . . . w7. For the inverse initial permutation, see Table 4.2.
4.1 The Data Encryption Standard (DES)
58 50 42 34 26 18 60 52 44 36 28 20 62 54 46 38 30 22 64 56 48 40 32 24 574941332517 59 51 43 35 27 19 61 53 45 37 29 21 63 55 47 39 31 23
10 2 12 4 14 6 16 8
91 11 3 13 5 15 7
Table 4.1: The initial permutation IP
44
Figure 4.2: The encryption function of DES
4.1 The Data Encryption Standard (DES)
40 8 48 39 7 47 38 6 46 37 5 45 36 4 44 35 3 43 34 2 42 33141
16 56 24 64 32 15 55 23 63 31 14 54 22 62 30 13 53 21 61 29 12 52 20 60 28 11 51 19 59 27 10 50 18 58 26
9 49 17 57 25
Table 4.2: The inverse permutation IP 1
3. The internal block cipher (see Figure 4.3): Block length is t = 32.
KeyspaceisKint ={0,1}48.
The encryption function fK : {0, 1}32 ! {0, 1}32, for a key K 2 {0, 1}48, is defined as follows:
Let R 2 {0, 1}32 be the string to be encrypted.
Apply the expansion function E : {0, 1}32 ! {0, 1}48 to R; see Table 4.3 (i.e., if R =
45
R1 R2 . . . R32, then
E(R) = R32R1R2R3R4R5R4R5R6R7R8R9R8R9 . . . R32R1.)
Compute E(R) K.
Divide the result into 8 blocks of length 6:
E(R) K = B1B2B3B4B5B6B7B8, whereBi 2{0,1}6,1i8.
Foreach1i8,applyanS-box
Si : {0,1}6 ! {0,1}4
(see below); we obtain the string
C = C1C2 . . . C8,
whereCi =Si(Bi),1i8.ThenC2{0,1}32.
Apply the fixed permutation P to C (see Table 4.3).
The result of the block cipher is then fK (R) = P(C).
4.1 The Data Encryption Standard (DES)
Figure 4.3: The internal block cipher of DES
E
P
32 1 2 3 4 5 456789 8 9101112 13
12 13 14 15 16 17 16 17 18 19 20 21 20 21 22 23 24 25 24 25 26 27 28 29 28 29303132 1
16 7 29 12 1 15 5 18 2 8 32 27 19 13 22 11
20 21 28 17 23 26 31 10 24 14
3 9 30 6 4 25
Table 4.3: The functions E and P
46
4.1 The Data Encryption Standard (DES)
4. The S-boxes:
Each S-box Si, 1 i 8, is represented by a table with 4 rows and 16 columns. Given a string B = b1b2 . . . b6, Si (B) is computed as follows:
The integer with binary expansion b1b6 is used as row index.
The integer with binary expansion b2b3b4b5 is used as column index.
The entry of the S-box in this row and column is written in binary expansion.
The result is padded with leading 0s to give it length 4.
This 4-bit string is then Si (B).
For the S-box Si, see Table 4.4. The other S-boxes are similar; see, e.g., the book (1) by
Stinson.
Table 4.4: The S-box S1
Example: Find S1 (001011). The outer bits are 01, so the row index is 1 (i.e., the second row). The inner bits are 0101, so the column index is 5. The corresponding entry in S1 is 2, or 10 in binary. Hence S1(001011) = 0010.
5. The round keys (see Figure 4.4):
Let k 2 K = {0,1}64 be a DES key. First we define:
For1i16,thevalues 8><>:1 fori2{1,2,9,16}, vi = 2 otherwise;
the function
PC1:{0,1}64!{0,1}28{0,1}28, k=k1k2k647!(C,D)
according to Table 4.5, namely
C = k57k49 k36, D = k63k55 k4;
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
0 1 2 3
14 4 13 1 2 15 11 8 3 10 6 12 5 9 0 7 0 15 7 4 14 2 13 1 10 6 12 11 9 5 3 8 4 1 14 8 13 6 2 11 15 12 9 7 3 10 5 0
15 12 8 2 4 9 1 7 5 11 3 14 10 0 6 13
the function
PC2 : {0, 1}28 {0, 1}28 ! {0, 1}48
according to Table 4.5, namely if (C, D) = b1b2 . . . b56, then PC2(b1b2 b56) = b14b17 b32.
The round keys Ki 2 Kint = {0, 1}48, 1 i 16, are now generated as follows: 47
4.1 The Data Encryption Standard (DES)
Figure 4.4: Generation of the DES round keys
PC1
PC2
57 49 41 33 25 17 9 1 58 50 42 34 26 18 10 2 59 51 43 35 27 19 11 3 60 52 44 36
14 17 11 3 28 15 23 19 12 16 727 41 52 31 30 40 51 44 49 39 46 42 50
24 1 5 6 21 10 4 26 8
20 13 2 37 47 55 45 33 48 56 34 53 36 29 32
63 55 47 39 31 23 15 7 62 54 46 38 30 22 14 6 61 53 45 37 29 21 13 5 28 20 12 4
Table 4.5: The functions PC1 and PC2
Let (C0, D0) = PC1(k).
For1i16,dothefollowing:
(a) Let Ci be the string that is obtained from Ci 1 by a circular left shift of vi positions.
(b) Let Di be the string that is obtained from Di 1 by a circular left shift of vi positions.
Then Ki = PC2(Ci, Di ).
48
4.1 The Data Encryption Standard (DES)
6. Decryption:
As we saw in Section 4.1.1, in order to decrypt a ciphertext, DES is applied with the reverse key sequence. In the process, the permutations IP and IP 1 will cancel each other out.
Example: We apply the first round of DES with hexadecimal plaintext and key w = 0123456789ABCDEF, k = 133457799BBCDFF1,
respectively. The left-hand table below is w in binary expansion, and the right-hand table is IP(w):
00000001 00100011 01000101 01100111 10001001 10101011 11001101 11101111
11001100 00000000 11001100 11111111 11110000 10101010 11110000 10101010
Then we obtain
L0 = 11001100000000001100110011111111,
R0 = 11110000101010101111000010101010. The binary expansion of the DES key k is
00010011 00110100 01010111 01111001 10011011 10111100 11011111 11110001
To compute the first round key, we find
C0 = 1111000011001100101010101111,
D0 = 0101010101100110011110001111, C1 = 1110000110011001010101011111, D1 = 1010101011001100111100011110,
and therefore
K1 = 000110110000001011101111111111000111000001110010.
49
4.2 Mathematical Background III: Finite Fields
Using this key, we obtain
E(R0) K1 = 011000010001011110111010100001100110010100100111,
then
and finally
fK1 (R0) = 00100011010010101010100110111011, R1 = 11101111010010100110010101000100.
The other rounds are computed analogously.
4.1.3 SecurityofDES
1. Several techniques have been developed to attack DES, such as di erential cryptanalysis
linear cryptanalysis
exhaustive search of the key space.
The last method has proved to be the most successful. With special hardware or large networks of workstations, DES ciphertexts can now be decrypted in a few hours.
2. Double DES.
If we use two di erent keys k1, k2 and encrypt a plaintext w by Ek2 (Ek1 (w)), does this increase security?
We saw: In the case of the a ne cipher, doing this is equivalent to an encryption with a third key, say Ek3 (w); in this case we say that the cipher is a group.
Is DES a group? The answer is no, as can be proven. One might therefore think that Double DES would have the security level of a 2 56 = 112-bit key.
However, Double DES is vulnerable to a meet-in-the-middle attack, which reduces the security level to that of a 57-bit key.
3. Triple DES.
To avoid the weakness of Double DES, one can use Triple DES. To encrypt the plaintext w, choose two DES keys k1, k2 and perform
Ek1 (Dk2 (Ek1 (w))).
This is resistant to meet-in-the-middle attacks. Other kinds of attacks have been proposed, but
they are impractical.
4.2 MathematicalBackgroundIII:FiniteFields
The Rijndael algorithm of the next section requires a certain type of multiplication that is based on finite fields. This concept is also used in other cryptographic applications.
50
4.2.1 Polynomials
Polynomials have many important applications in cryptography. In particular, they are needed to introduce the concept of a finite field.
Definition 4.1.
Let R be a commutative ring with identity 1 , 0. A polynomial (in one variable) over R in x is an expression
f (x) = an xn + an 1 xn 1 + . . . + a1 x + a0,
withthecoe cientsaj 2R,j=0,1,,n,andthevariablex.Thesetofallpolynomials over R in x is denoted by R[x]. If an , 0, then n is called the degree of f , n = deg f . The coe cients an and a0 are called the leading, resp. the constant coe cient of f .
|
Example: The polynomials 23 + x + 1, x, and 1 are elements of Z[x] of degrees 3, 1, and 0, respectively.
(a)Thevalueof2x3 +x+12Z[x]at 1is 2.
(b) Denote the elements of Z/2Z by 0 and 1. Then x2 + 1 2 (Z/2Z)[x]; it has the zero 1.
Let g 2 R[x] be another polynomial,
g(x) = bm xm + . . . + b1 x + b0,
and assume that n m. If the missing coe cients in g are set to 0, we can write g ( x ) = bn x n + . . . + b1 x + b0 .
Definition 4.3.
With f, g 2 R[x] as above, we define the sum and the product of f and g by ( f + g)(x) = (an + bn)xn + . . . + (a1 + b1)x + (a0 + b0)
4.2 Mathematical Background III: Finite Fields
Definition 4.2.
Let f 2 R[x]. If r 2 R, then
f (r) = anrn + an 1rn 1 + . . . + a1r + a0
is called the value of f at r. If f (r) = 0, then r is called a zero of f .
Examples:
|
and with
( f g)(x) = cn+m xn+m + . . . + c1 x + c0,
ck =
where any undefined coe cients ai, bi are set to 0.
|
Xk j=0
ajbk j, 0kn+m,
51
4.2 Mathematical Background III: Finite Fields
Examples: Let f (x) = x3 + 22 + x + 2 2 Z[x], g(x) = x2 + x + 1 2 Z[x]. Then ( f + g)(x) = x3 + 32 + 2x + 3
and
(fg)(x) = x5 +(2+1)x4 +(1+2+1)x3 +(2+1+2)x2 +(2+1)x+2
= x5 +34 +43 +52 +3x+2.
Remark: With this sum and product, (R[x], +, ) is a commutative ring with identity 1.
In what follows, let F be a field. Then the ring F[x] has no zero divisors. In fact, it is easy to see that
deg ( f g) = deg f + deg g
for all f , g 2 F[x] with f , g , 0. Most of the following results will be stated without proof.
Theorem 4.1.
Let f , g 2 F[x], g , 0. Then there are uniquely determined polynomials q, r 2 F[x] with f=qg+r, where r=0 or degr
Proof
We have
Remarks:
gcd(r0, r1)
= gcd(r0 q1r1, r1) = gcd(r1, r2) | {z }
r2
= gcd(r1 q2r2,r2)=gcd(r2,r3)
| {z }
r3 .
= gcd(rm 1, rm) = gcd(qmrm, rm) = rm.
(1) Starting with positive integers is no serious restriction since gcd(|a|, |b|) = gcd(a, b) for all a, b 2 Z.
(2) The Euclidean algorithm necessarily terminates after at most n steps since the (integer) remainders get successively smaller.
65
5.2 Mathematical Background IV: Some Number Theory
(3) In fact, the algorithm requires considerably fewer steps. Suppose we apply the algorithm to a = r0 and b = r1 with a > b > 0. Then the following can be shown:
Let = (1 + p5)/2 (the golden mean). Then the number of iterations in the Euclidean
algorithm is at most
ln b + 1. ln
Roughly speaking, the extended Euclidean algorithm consists of going backwards after the Euclidean algorithm has been completed.
Example: In the previous example, we start with the second-last row and move upwards: 2 = 50 316
= 50 3(216 450)=1350 3216
= 13(482 2216) 3216=13482 29216 = 13482 29(1180 2482)
= 71482 291180.
So (x, y) = (71, 29) is a solution of the equation in Corollary 5.2.
This idea can be formalized to give a more convenient algorithm. Given the sequence q1, q2, . . . , qm as in the Euclidean algorithm (note that rk = brk 1/rk c), we define the two sequences
x0 = 1, x1=0, xk+1=qkxk+xk 1 (1kn), (5.2)
y0 = 0, y1=1, yk+1=qkyk+yk 1 (1kn). (5.3) Theorem 5.4.
The extended Euclidean algorithm
For 0 k n + 1 we have
rk =( 1)kxka+( 1)k+1ykb.
In particular,
gcd(a,b)=rn =( 1)nxna+( 1)n+1ynb.
Proof We prove this by induction on k. First note that
r0 = a = 1 a 0 b = x0a y0b,
~
r1 =b= 0a+1b= x1a+y1b;
this is the induction beginning. Now let k 2 and suppose the assertion is true for subscripts
less than k. Then by (5.1), (5.2), and (5.3) we have
rk = rk 2 qk 1rk 1
= ( 1)k 2xk 2a + ( 1)k 1yk 2b
qk+1 ( 1)k 1xk 1a+( 1)kyk 1b 66
5.2 Mathematical Background IV: Some Number Theory
= ( 1)ka(xk 2 + qk 1xk 1) + ( 1)k+1b(yk 2 + qk 1yk 1)
= ( 1 ) k x k a + ( 1 ) k + 1 y k b,
which proves the result. Example: Let a = 100, b = 35. We construct the following table:
Son=3,andgcd(100,35)=r3 =5= 1100+335. 5.2.3 Moreongroups
Groups play a fundamental role in modern cryptography. We have seen the following examples:
The multiplicative groups of Q, R, C;
the group of units in the residue class ring Z/mZ; the multiplicative group of the finite field GF(pn).
Of these the finite groups are more relevant to cryptography than the infinite ones. Another important group is
The group of points on an elliptic curve.
In this subsection, G denotes a group that is multiplicatively written, with neutral element 1.
Definition 5.2.
Letg2G. Ifthereisane2Nwithge =1,thenthesmallestsuchintegeriscalledthe orderofginG,denotedbyordGg.OtherwisewesaythattheorderofginGisinfinite. |
The next theorem shows that only a limited number of exponents can possible be an order of given element g 2 G.
k
0
1
2
3
4
rk qk xk yk
100
1 0
35 2 0 1
30 1 1 2
5 6 1 3
0
7 20
Theorem 5.5.
Letg2Gande2Z.Thenge =1ifandonlyifeisamultipleofordGg. Proof Letn:=ordGg.(:Ife=kn,thenge =gkn =(gn)k =1k =1.
):Letge =1ande=qn+rwith0r
(me)dm1l=m (modn).
congruence is also true (see the assignments).
This theorem shows that to decrypt, Bob only needs to do the following: He obtains the ciphertext c, as computed in (5.5) by Alice.
He uses his secret key d to compute
cd (mod n). By Theorem 5.17, this gives the plaintext m.
Remark: This shows that RSA is indeed a cryptosystem since for each encryption function there is a decryption function.
Example: We continue the previous example, where we had n = 253, e = 3, and d = 147. The ciphertext was c = 110. Then we get 110147 (mod 253) = 165, which is the original plaintext.
5.3.3 Securityande ciency
A great deal could be said about these two issues; see, e.g., the book (1) by Stinson. Here we consider only a few important remarks.
Security of RSA
1. Computing the secret RSA key from the public RSA key is equivalent to factoring the RSA modulus n.
73
5.3 The RSA Cryptosystem
obtain c = 110.
2. RSA decryption is based on the following result.
Theorem 5.12.
Let (n, e) be the public RSA key and d the corresponding private key. Then for any m 2 Z
with 0 m < n we haveProof Since ed 1 (mod ‘(n)), there is an l 2 Z with5.3 The RSA CryptosystemOne direction of this is clear: If Oscar knows the prime factors p and q of n, then he knows ‘(n) = (p 1)(q 1), and can use the extended Euclidean algorithm to find d from e via ed 1 (mod ‘(n)).2. On the other hand, it is conceivable that Oscar is able to determine the plaintext that corresponds to a given ciphertext, using some other method.It is not known whether being able to decrypt RSA ciphertexts implies the ability to factor n e ciently. In other words, it is not known whether breaking RSA is as di cult as factoring integers.3. It is essential that the prime factors p and q of the RSA modulus n be chosen appropriately, to make the factorization of n infeasible. (For prime number generation see Section 5.4).Given the strength of currently known factoring algorithms, p and q should be random primes of a given bit length. However, there are factoring algorithms that work better if the numbers n, p, or q have a special form. But the probability of this to occur is negligible, and it seems that it is not necessary to test for those special properties.4. The public encryption exponent e is chosen to be as small as possible to make encryption e cient. Some further remarks: The choice e = 2 is impossible since ‘(n) is even and we must have gcd(e, ‘(n)) = 1. The least possible encryption exponent is e = 3; then the encryption would require onesquaring and one multiplication modulo n. However, a small e may make it possible for Oscar to stage a low-exponent attack. Thiscan be used if the same message m is encrypted e times with encryption exponent e and epairwise coprime RSA moduli. Therefore a larger encryption exponent is often used; a common choice is e = 216 + 1 (itrequires 16 squarings and multiplications modulo n for encryption). Anotherdefenceagainstalow-exponentattackistochooseafewbitsintheplaintextblockat random.E ciency of RSAWe cannot go into the details of a complexity analysis of RSA encryption and decryption. Once again, just a few important points: RSA encryption requires one exponentiation modulo n. Encryption e ciency (with fast exponentiation) depends on the size of the exponentwhich, however, should not be too small (see above). RSA decryption also requires one exponentiation modulo n. The decryption exponent must be as large as n; small d can be e ciently computed fromthe corresponding public key (n, e). If n is a k-bit number then, typically, d is also a k-bit number and roughly k/2 of thebits will be 1. Then, with fast exponentiation, decryption requires k squarings and k/2 74 5.4This would make RSA decryption almost four times faster than it would otherwise be.PrimeNumberGeneration5.4 Prime Number Generationmultiplications modulo n. If the RSA modulus has 1024 bits, then 1023 squarings and 512 multiplications modulo nare required. Compared to DES decryption, this is very slow. According to Stinsons book (1), it isabout 1500 times slower than DES. A speed-up of RSA decryption is possible if the Chinese remainder theorem is used. In RSA, as well as in many other public-key cryptosystems, large random prime numbers are used. They are produced by generating random numbers of the desired size; testing whether these random numbers are prime.Of the many existing primality tests, we will discuss only a few important ones.5.4.1 TrialdivisionThis first algorithm is not e cient for large integers, but it is still useful. It is based on the following simple theorem.Theorem 5.13. p Ifn2Niscomposite,thenithasaprimedivisorp n. ~Proof Sinceniscomposite,wecanwriten=ab,witha>1andb>1. Nowapnor b pn since otherwise ab > pnpn = n, a contradiction. Suppose that a pn. Then a has a prime divisor p which also divides n, and p a pn.
This result suggests the following algorithm, called trial division:
Check for all prime numbers p pn whether they divide n.
If a prime divisor of n is found, then n is composite.
Otherwise n is prime.
The primes p pn can either be generated by the sieve of Eratosthenes, or obtained from a precomputed table.
Example: Is n = 15413 prime? We have bpnc = 124. Hence we must test whether one of the 29 odd primes 3, 5, 7, . . . , 109, 113 divides n. None of them does, and therefore n is prime.
Remarks:
(1) Trial division can also be used to find the prime factorization of n.
(2) In factoring algorithms, trial division is typically used to find all prime factors < 106.755.4 Prime Number Generation(3) For large n, trial division becomes very ine cient: If (x) denotes the number of primes x, then the famous prime number theorem (first proved in 1896 by J. Hadamard and independently by C. de la Vallee Poussin) states that (x) is approximately x/ ln x; to be exact,lim (x) =1. x!1 x/lnxNow, for RSA we need primes > 1075. To prove primality of such a number, about 1075/2 36
ln(1075/2) > 0.36 10 divisions would be necessary, which is impossible.
5.4.2 TheFermattestandCarmichaelnumbers
It is computationally expensive to prove that a given integer is prime. However, there are e cient algorithms that show that a number is prime with a high probability; such algorithms are called (probabilistic) primality tests.
1. The Fermat test
Recall Fermats little theorem: If n is a prime, then an 1 1 (mod n) for all a 2 Z with gcd(a, n) = 1. This can be used to test a given n 2 N for being composite:
Chooseana2{1,2,,n 1}.
Use fast exponentiation to compute y = an 1 (mod n). If y , 1, then n is composite by Fermats little theorem. If y = 1 then the test is inconclusive.
Example: Let n = 341. Choose a = 2. We have
2340 1 (mod 341),
so the test is inconclusive. In fact, 341 = 11 31. On the other hand, with a = 3 we have
3340 56 (mod 341), and this proves that 341 is composite.
Remark: Even if the Fermat test proves that n is composite, it does not find a divisor of n.
2. Carmichael numbers
Recall that
the Fermat test can prove that a positive integer is composite, but it cannot prove primality.
If the Fermat test gives remainder 1 for many bases a, then it would seem likely that n is prime. However, we have the following unfortunate situation:
Example: Letn=561=31117. Itturnsoutthat
an 1 1
76
(mod n)
5.4 Prime Number Generation
for all a with gcd(a, n) = 1. Hence the Fermat test for compositeness fails for every base, but still n is not prime.
Definition 5.5.
(a) If n 2 N is odd and composite, and if a 2 Z is such that an 1 1 (mod n),
then n is called a pseudoprime to base a.
(b) If n is a pseudoprime to all bases a with gcd(a, n) = 1, then n is called a Carmichael number.
Remark: Carmichael numbers are rare, but is was shown in 1994 that there are infinitely many of them. The smallest one is 561 = 3 11 17; the next ones are 1105, 2465, 2821, 6601, and 8911. These are all the ones below 10000. There are only 2163 Carmichael numbers < 109.5.4.3 TheMiller-RabintestBecause of the existence of Carmichael numbers, the Fermat test is not optimal for practical use. The Miller-Rabin test can prove the compositeness of any composite positive integer, i.e., there is no analogue of Carmichael numbers for the Miller-Rabin test. We begin with the following set-up: Letn2Nbeodd. Let s := max{r 2 N | 2r |n 1}, i.e., 2s is the largest power of 2 that divides n 1. Letd:=(n 1)/2s (sodisodd).The following result, presented here without proof, is the basis for the Miller-Rabin test:Theorem 5.14.If n is prime and a 2 Z with gcd(a, n) = 1, then with the previous notation we have either |ad 1 (mod n), or there exists an r 2 {0, 1, . . . , s 1} witha2r d 1 (mod n).This theorem implies: If we can find an a 2 Z with gcd(a, n) = 1 that satisfies neither (5.6) nor (5.7) for r 2 {0, 1, . . . , s 1},then n is proven composite.(5.6) (5.7) ~Remarks: (a) This test is called the Miller-Rabin test.(b) An integer a, gcd(a, n) = 1, for which (5.6) and (5.7) (for all r) does not hold, is calleda witness for the compositeness of n.Example: Let n = 561. Then 560 = 24 35, so s = 4. Try a = 2; then235 263 (mod 561), 775.5 The Di e-Hellman Key Exchangeand2235 166 (mod 561), 2435 67 (mod 561), 2835 1 (mod 561).So (5.7) is not satisfied for any r 2 {0, 1, 2, 3}, and thus Theorem 5.14 proves that 561 is composite. 2 is a witness for the compositeness of 561.For the e ciency of the Miller-Rabin test it is important that there are su ciently many witnesses. This is guaranteed by the following result, again stated without proof.Theorem 5.15.Ifn 3isanoddcompositeinteger,thentheset{1,2,…,n 1}containsatmost(n 1)/4 numbers relatively prime to n and not witnesses for the compositeness of n.~The Miller-Rabin test can be used as follows: Given:anoddn2Ntobetested. Choosearandoma2{2,3,…,n 1}. If gcd(a, n) > 1 then n is composite.
Otherwise,computead,a2d,,a2s 1d.
If none of them satisfies identity (5.6), resp. (5.7), then a is a witness and n is composite. Otherwise repeat with a new random a.
By the previous theorem, the probability that n is composite and a is not a witness is at most 1/4. So, if the test is repeated t times then the probability of not finding a witness is at most (1/4)t . (For t = 10, for instance, this is 1/220 10 6).
5.4.4 Generatingrandomprimes
To generate a random prime of bit length k, we do the following:
Set the first and last bit of a k-bit number n to 1.
Choose the remaining k 2 bits randomly with uniform distribution.
Check whether n is divisible by a prime number below a predefined bound B (typically
B = 106).
If no prime divisor of n is found, apply the Miller-Rabin test t times.
It can be shown that the choice t = 3 su ces to make the error probability less than 2 80
if k 1000.
If this test finds no witness for the compositeness of n, then n is considered prime. (Note:
5.5
it is not proven prime, but it is prime with a very high probability). TheDi e-HellmanKeyExchange
The protocol described here is not a public-key cryptosystem, although it is the basis for the ElGamal system described in Section 5.6.
78
5.5 The Di e-Hellman Key Exchange
The situation is as follows:
Alice and Bob wish to use a symmetric encryption system.
They must exchange a secret key for this system.
They want (or have) to use an insecure channel for this purpose.
This can be done with the Di e-Hellman key exchange, which is not based on the factoring problem for integers, but on the discrete logarithm problem.
5.5.1 Discretelogarithms
Recall from Section 5.2.3: The group (Z/pZ) is cyclic of order p 1. A generator of a residue class group (Z/mZ), when it is cyclic, is called a primitive root modulo m. When g is a primitive root modulo p, we have seen that ga, a = 0, 1, . . ., p 2, gives all p 1 elements of the group (Z/pZ).
Definition 5.6.
Let g be a primitive root modulo p. Given A 2 {1,2,,p 1}, the exponent a 2
{0, 1, . . . , p 2} with
is called the discrete logarithm of A to the base g, and is denoted by a = dlogg A.
|
Remarks: (1) The computation of discrete logarithms is considered to be di cult. While there are algorithms for solving this problem, no e cient algorithms are known.
(2) On the other hand, there is no proof that this problem is in fact di cult.
(3) Discrete logarithms can be defined in arbitrary cyclic groups, and whenever the discrete logarithm problem is di cult in such a group, it will be of interest in cryptography. An important example is the group of points on an elliptic curve; see Section 5.7, where we will go into greater detail.
Example 1: Let p = 13. We saw in Section 5.2.3 that ordG (2+13Z) = 12, where G = (Z/13Z); this means that g = 2 is a primitive root. The corresponding discrete logarithms are:
Example 2: Consider the additive group Z/nZ for n 2 N. A generator of this group is the residue class 1 + nZ. Let A 2 {0, 1, . . . , n 1}. Then the discrete logarithm a of A + nZ to the base 1 + nZ satisfies the congruence
Aa (modn);
hence a = A. The other generators of Z/nZ are the residue classes g + nZ with gcd(g, n) = 1.
Then the discrete logarithm a of A + nZ to the base g + nZ satisfies A ga (mod n).
A ga (mod p)
A
1 2 3 4 5 6 7 8 9 10 11 12
dlog2 A
0 1 4 2 9 5 11 3 8 10 7 6
79
5.5 The Di e-Hellman Key Exchange
This can be e ciently solved for a by the extended Euclidean algorithm. So the additive cyclic group Z/nZ cannot be used to implement any cryptographic application based on the discrete logarithm problem.
5.5.2 FindingPrimitiveRoots
Primitive roots belonging to a given prime p are basic to the Di e-Hellman key exchange, the main topic of this section, and the related ElGamal cryptosystem in the next section. It is therefore important to know how to find primitive roots.
Unfortunately, there is no general formula for computing primitive roots, and no fast deter- ministic algorithm is known. However, as is often the case, probabilistic algorithms work quite well in practice, as we will now see.
First recall that by Theorem 5.7, a cyclic group of order n has exactly ((n)) generators. This means that there are (p 1) primitive roots mod p.
Example1. Iftheprimepisoftheformp=2q+1,whereqisalsoaprime,then'(p 1)= (2q) = (q) = q 1, so almost half of all integers between 2 and p 1 are primitive roots.
In general, the number (or proportion) of primitive roots depends on the size of (n) compared with n. How small can (n)/n get? It has been shown that for any positive integer
n 5 we have
(n) 1
n 6loglogn
.
This means that even for n = p 1 of cryptographic size there are still plenty of primitive roots. For instance, if n has about 100 decimal digits, then log log n 5.4, so the probability of an integer between 2 and p 2 being a primitive root modulo a prime of this size is at worst 0.03, and is usually much better.
Based on this, we can use the following procedure:
Given a prime p,
(1) factor p 1;
(2)choosearandomintegerg 2 {2,3,,p 2};
(3) use Theorem 5.8, together with the factorization of (1),
to find the order of g mod p;
(4) if the order found in (3) is p 1, then g is a primitive root;
(5) if the order found in (3) is < p 1, discard g and return to step (2).Remarks:(1) This procedure is likely to succeed after a relatively small number of attempts.(2) It works only if we can factor p 1; this, however, is quite likely to succeed for primes in the 100-digit range, using various known factorization methods, including the elliptic curve methods discussed at the end of Section 5.7.805.5 The Di e-Hellman Key Exchange(3) The important Theorem 5.5 says that only factors of p 1 are candidates for the order of d. So we only need to compute, with fast exponentiation, gd (mod p) for d < p 1 with d | p 1. Ifallthesepowersare1 (mod p),thengmustbeaprimitiverootmodulop.Example 2. Let p = 23. Then p 1 = 22 = 2 11. We choose a random g 2 {2, 3, . . . , 21}, say g = 3. Then we find32 9 (mod23), 311 1 (mod23). So ord23 =11.g = 3 is therefore not a primitive root. We try again with another random g, say g = 7. In thiscase we find72 3 (mod23), 711 1 (mod23). So ord23 =22.Therefore g = 7 is a primitive root mod p. 5.5.3 ThekeyexchangeThe Di e-Hellman key exchange works as follows: Alice and Bob agree on a large prime p and a primitive root g modulo p, with 2 g p 2.(These numbers p and g can be publicly known, so an insecure channel can be used forthis agreement.) Alicechoosesana2{0,1,…,p 2}atrandomandcomputesA = ga (mod p). She sends the result A to Bob, but keeps the exponent a secret. Bobchoosesab2{0,1,…,p 2}atrandomandcomputes B = gb (mod p). He sends the result B to Alice, but keeps the exponent b secret. To obtain the common secret key, Alice computes Similarly, Bob computes The the common key isBa = gbaAb = gabK = gab(mod p). (mod p).(mod p).Example: Alice and Bob agree on p = 17 and g = 3. Alice chooses a = 7, computes ga 11 (mod p); she sends the result A = 11 to Bob. Bob chooses b = 4, computes gb 13 (mod p); he sends the result B = 13 to Alice. Alice computes Ba 4 (mod p);81 Bob computes Ab 4 (mod p). The common key is therefore K = 4.5.5.4 SecurityoftheDi e-Hellmankeyexchange1. Suppose that Oscar knows the integers p, g, A, and B, but not the discrete logarithms a and b. He wants to determine the secret key K = gab (mod p) from what he knows. This is called the Di e-Hellman problem.It is clear that if Oscar can compute discrete logarithms modulo p, then he can also solve the Di e-Hellman problem: He determines the discrete logarithm b of B to base g; then he computes the key K = Ab (mod p).Some remarks: This is the only known method for breaking the Di e-Hellman protocol. Nobody has been able to prove that if Oscar can break the Di e-Hellman problem, thenhe can also e ciently compute discrete logarithms modulo p. AslongastheDi e-Hellmanproblemisdi culttosolve,noeavesdroppercandeterminethe secret key from the publicly known information. To prevent the application of known discrete logarithm algorithms, the prime p must be atleast of length 768 bits. It appears best to choose p randomly, as in Section 5.4.4, from all primes of a certain length.2. Another possible attack is the intruder-in-the-middle attack. It works as follows: Oscar exploits the fact that Alice cannot verify that the messages she receives really comefrom Bob, and the same is true for Bob. Oscar intercepts all messages between Alice and Bob. He impersonates Bob and exchanges a key with Alice. He also impersonates Alice and exchanges a key with Bob. When Bob sends an encrypted message to Alice, he uses the key he has previouslyunknowingly exchanged with Oscar. Oscar intercepts and decrypts Bobs message. Oscarthenchangesthemessage,encryptsitwiththekeyhehaspreviouslyexchangedwithAlice, and sends it to Alice.As a defence against this attack, digital signatures can be used.5.6 TheElGamalCryptosystemThe following system was first published by T. ElGamal in 1985. As in the previous section, the security of this cryptosystem is based on the di culty of solving the Di e-Hellman problem in the group (Z/pZ).825.6 The ElGamal Cryptosystem A = ga Alices public key is then the triple (p, g, A). Her private key is the exponent a. 2. Encryption is done as follows:(mod p). Plaintextspaceistheset{0,1,…,p 1}. Bob obtains Alices public key (p, g, A). Hechoosesarandomb2{0,1,…,p 2}andcomputesB = gb (mod p). Given a plaintext m, he determinesc=Abm (modp),i.e., Bob encrypts the message m by multiplying it modulo p by the Di e-Hellman key. The ElGamal ciphertext is the pair (B, c)3. Decryption works as follows: Alice obtains the ciphertext (B, c); she knows her secret key a. She divides c by the Di e-Hellman key Ba (mod p); this is achieved by calculatingm=Bxc(modp),wherex=p 1 a. (Note:since1ap 2,wehave1 x p 2). This gives the original plaintext back sinceBxc gb(p 1 a) Abm (gp 1)b(ga) b Abm A bAbmm (modp).Example: Alice chooses p = 23, g = 7, and a = 6. ShecomputesA=ga (modp)=4. Her public key is then (p = 23, g = 7, A = 4). Her secret key is a = 6. Suppose Bob wants to encrypt m = 7. He obtains (p, g, A), and chooses b = 3 at random. HecomputesB=gb (modp)=21. He encrypts m by computing c = Abm (mod p) = 11. The ciphertext is (B, c) = (21, 11); he sends it to Alice. Alice decrypts by computing Bp 1 6c (mod p) = 7 = m.835.6 The ElGamal Cryptosystem 5.6.1 ThecryptosystemWe assume that Bob wants to send a message to Alice.1. Key generation works as follows: Alice chooses a large prime p and a primitive root g modulo p. Thenshechoosesarandoma2{0,…,p 2}andcomputes5.7 Elliptic Curve CryptographyRemark: As was the case with the Di e-Hellman key exchange, the ElGamal cryptosystem can be implemented in any cyclic group in which the discrete logarithm problem is di cult.5.6.2 E ciencyandSecurity1. E ciency ElGamal encryption requires 2 modular exponentiations: Ab (mod p) and B = gb (mod p). (Compare: RSA requires only one). However,theseexponentiationsareindependentoftheplaintexttobeencrypted.Therefore, the exponentiations can be carried out as precomputations. The precomputed values must be kept secret and must be securely stored. Thentheactualencryptionrequiresonlyonemodularmultiplicationandisthereforemuch more e cient than RSA encryption. ElGamal decryption requires one modular exponentiation, as in RSA; also, the moduli must be of similar size in both systems. IncontrasttoRSA,theChineseremaindertheoremdoesnotspeedupElGamaldecryption. IntheElGamalsystem,theciphertextistwiceaslongastheplaintext;thisisadisadvantageof the system (but it is beneficial for security see below). The same prime number could be used in all public keys. However, if computing discretelogarithms modulo this p turns out to be easy, then the whole system is insecure. 2. Security IfOscarcancomputediscretelogarithmsmodulop,thenhecanbreaktheElGamalsystem. However, it is not known whether being able to break the ElGamal system implies theability to e ciently compute discrete logarithms modulo p. ButitiseasytoshowthattheElGamalcryptosystemandtheDi e-Hellmankeyexchangeprotocol are equally di cult. As a consequence, the ElGamal prime modulus p should have at least the same length asthe prime modulus for the Di e-Hellman key exchange, namely at least 768 bits. An advantage of the ElGamal system over RSA is that it is randomized in the sense that theciphertexts(B,c)arerandompairsin{0,1,…,p 1}2 (aslongasAisaprimitive root modulo p.) This makes cryptanalysis, in particular statistical methods, much moredi cult.EllipticCurveCryptography 5.7Recall the discrete logarithm problem (Section 5.5.1). There we mainly considered elements of (Z/pZ) for a fixed prime p. Given an integer A 2 {1, 2, . . . , p 1} and a primitive root g modulo p, i.e., a generator of the cyclic group (Z/pZ), find a k 2 N such thatgk B (mod p). 845.7 Elliptic Curve CryptographyThe same question can be asked in any group G: Given g 2 G and B 2 G, find a k 2 N such thatgk = B.Now, it may happen that no such k exists. But if we insist that B is in the subgroup generated by g (i.e., the group of all powers of g), which is the case when G is cyclic and g is a generator, then the problem does have a solution, just as before.5.7.1 EllipticCurvesApart from the group (Z/pZ), another group of particular importance in cryptography is related to elliptic curves.Definition 5.7.An elliptic curve is the set of solutions of a cubic or quartic polynomial equation in two variables, plus one additional point.For our purposes we will insist that the equation be cubic and of the form| y2 = x3 + ax + b,a,b2Z and 4a3+27b2.0 (modp)whereand we will look for solutions in Z/pZ for a fixed prime p.Example:Letp=7,a= 1,b=0,sothaty2 x3 x (mod7).xx3 xy 0 1 2 3 4 5 60 0 6 3 4 1 000 2, 2 1, 1 0Thus the points are(0,0), (1,0), (4,2), (4,-2), (5,1), (5,-1), (6,0).We also include a point which we denote by 1, and call the point at infinity. (An explanation for this later).Remark: In this case the curve has 7 points. In general, the number of points on such a curve (over Z/pZ) will be betweenp+1 2pp and p+1+2pp.This fact is known as Hasses Theorem, a proof of which would be beyond the scope of this course.85ThenP=(x,y)and Pj =(xj,yj),P + 1 = P, P = (x, y),j=1,2,3.P + ( P) = 1. Furthermore, P1 + P2 = P3, whereandx3 = m2 x1 x2,y3 = m(x1 x3) y1,8><> y2 y1
>
> x2 x1 if x1 , x2,
m = >32 + a
>1 ifx=x.
5.7 Elliptic Curve Cryptography
Figure 5.1: Adding points on an elliptic curve 5.7.2 TheGroupStructure
What makes elliptic curves so important is the fact that their points have a group structure. (See Figure 5.1). We can translate this geometric definition into arithmetical rules: Let
: 2y1 Theorem 5.16.
12
Elliptic curves have the following important property, which will be stated without proof.
The set of points on an elliptic curve, with this operation + defined above, forms a commutative group.
~
86
In particular, this means that
P + Q = Q + P, P + (Q + R) = (P + Q) + R.
While the other three properties of a group are easy to prove, to verify associativity requires
considerably more e ort. Example:Lety2 =x3 x,p=7,andlet
Then
and
P1 = (1,0), P2 = (4,2). m=2 0=225=103 (mod7)
4 1 3
x3 = m2 x1 x2 = 33 1 4 = 4,
y3 =m(x1 x3) y1 =3(1 4) 0= 95 (1, 0) + (4, 2) = (4, 5).
(mod7).
5.7 Elliptic Curve Cryptography
So we have found
Similarly, we could build a complete addition table.
5.7.3 TheEllipticCurveDiscreteLogProblem
Let us consider the group of points
E = {(x, y) 2 (Z/pZ)2 | y2 = x3 + ax + b} [ {1}
with the operation + defined in the previous subsection. Then the discrete logarithm problem for this group becomes:
Given G 2 E and B 2 E, find a k 2 N such that k G = B,
where k G means that the point G is added k-times to itself.
(Note that this group is written additively, so what was an exponentiation earlier is now a repeated addition.)
The integer k is then the elliptic curve discrete logarithm of B. For large p this integer k is extremely di cult, or impossible, to determine from B and G. Based on this, we can design an analogue of the Di e-Hellman key exchange protocol:
AliceandBobagreeonp,E,andG2E.
Alice chooses a 2 N at random, computes A = a G, and sends it to Bob. Bob chooses b 2 N at random, computes B = b G, and sends it to Alice. AlicethencomputesaB=(ab)G.
BobcomputesbA=(ba)G.
K=(ab)G=(ba)Gisthenthecommonkey.
87
5.7 Elliptic Curve Cryptography
The security of this key exchange protocol relies on the di culty of solving the elliptic curve discrete logarithm problem.
5.7.4 FurtherRemarks
1. General remarks:
Just as the usual Di e-Hellman key exchange leads to the ElGamal cryptosystem, there
is an elliptic curve ElGamal cryptosystem.
No good general attack on the elliptic curve discrete logarithm problem is known.
However, this is currently an area of intense research.
Instead of elliptic curves over (Z/pZ), many applications use elliptic curves over the finite
field GF(2n).
In this case the equations for elliptic curves need to be modified, mainly because we have
characteristic 2, i.e., 2 = 0 in GF(2n). The equations will be of the form y2 + a1xy + a3y = x3 + a2x2 + a4x + a6.
2. Representing Plaintext
In an elliptic curve cryptosystem, how do we represent plaintext? This is not as straightfor-
ward as in cryptosystems over (Z/pZ).
The general set-up:
An elliptic curve E will be fixed.
The ciphertext has to be mapped onto a point of E.
The cryptosystem uses elliptic curve operations to yield a new point. This point will serve as ciphertext.
The main problem here is: There is no known polynomial-time deterministic algorithm for writing down points on an arbitrary elliptic curve E (mod p). However, there are fast probabilistic methods for finding points. These methods can be used for encoding plaintext. One such method works as follows:
LetE: y2x3+ax+b(modp)bethegivencurve.
The message m will be embedded in the x-coordinate of a point.
Problem: Probability that m2 + bm + c is a square modulo p is only 1/2.
Solution: Adjoin a few bits at the end of m and adjust them until we get a number x such
thatx3 +ax+bisasquare (mod p).
If we adjoin K bits, then the probability of failure is only 2 K .
To recover the message m from the point P = (x, y) in the end, simply remove the last K
bits.
Howcanwetellifx3 +ax+bisasquaremodulop?
88
5.7 Elliptic Curve Cryptography
There are fast methods using quadratic reciprocity and Legendre symbols or Jacobi symbols. (These terms are taught in any course on elementary number theory, for instance MATH 3070 at Dalhousie).
The actual square root modulo p is easy to find when p 3 (mod 4) (see one of the assignments), and not so easy, but feasible, when p 1 (mod 4).
5.7.5 FactoringwithEllipticCurves
Elliptic curves can be used to factor large numbers. The basic idea is (roughly) as follows:
Given: a composite number n to be factored.
We choose a point P and a curve E on which P lies.
We consider E to be an elliptic curve over (Z/nZ) (as if n were a prime!)
We successively add P to itself.
In each such step we have to evaluate a modular inverse, say d 1 (mod n).
For this to succeed, we need gcd(d, n) = 1.
Ifthisfails,theneitherd=n0 (modn),or1
|
Thus, hash functions map arbitrarily long strings to strings of fixed length, while compres- sion functions map strings of fixed length to strings of shorter (fixed) length. Both types of functions are never injective (or one-to-one).
Example 1. The map that sends the word b1b2 . . . bm 2 {0, 1}m to b1 b2 bm 2 {0, 1}
is a compression function if m > 1 is fixed. It can also be seen as a hash function if m is considered to be an arbitrary positive integer.
In cryptography, hash functions and compression functions must satisfy the following Basic requirements: Let h : D ! n be a hash or compression function, where D = ,
respectively D = m. Then
(a) h(x) must be easy to compute for all x 2 D, and
(b) h must be secure, in the sense described below. Definition 6.2.
(Informal definition) The function h, as defined above, is a one-way function if it is infeasible to invert h; that is, to find computationally an x 2 D such that h(x) = s for a given image s 2 n.
|
6.1 Cryptographic Hash Functions
What does infeasible mean? Intuitively: If any algorithm that, on input of an s 2 n, almost always fails to compute the corresponding x 2 D because it uses too much time or space.
Example 2. Let p be a randomly chosen 1024-bit prime and g a primitive root mod p. Then the function
f :{0,1,2,,p 1}!{1,2,,p 1}, x7!gx (modp)
is easy to compute (see Section 5.2.5), but an e cient inversion function is not known because of the di culty of computing discrete logarithms (see Section 5.5). This function f can therefore be used as a one-way function.
A good hash function should be resistant to collisions, which are defined as follows.
Definition 6.3.
Let h : D ! n be a hash or compression function. A collision of h is a pair (x, x0) 2 D2 for which x , x0 and h(x) = h(x0).
|
All hash functions and compression functions have collisions because they are not injective. The objective, however, is to make these functions resistant to collisions.
Example 3. Consider the hash function in Example 1. A collision in this case is provided by any pair of strings whose numbers of 1s have the same parity. For instance, h(1011) = 1 = h(010).
Definition 6.4.
(a) The function h : D ! n is called weak collision resistant if for a given x 2 D it is infeasible to compute a collision (x, x0).
(b) The function h is called (strong) collision resistant if it is infeasible to compute any collision (x, x0) of h.
|
Example 4. Alice wants to protect a sensitive file on her o ce computer from unauthorized changes. She uses a hash function h : ! n to compute y = h(x) of her file x and stores the hash value y on a storage device; this will be safe to take home with her. The next morning she checks whether her file has been changed by computing the hash value again and comparing it with the value on her device.
This test is only secure if the hash function h is weak collision resistant. If not, Eve can compute another inverse image x0 of the hash value h(x) and change the file x to x0 without Alice noticing.
The Birthday Attack
This term refers to an attack on the strong collision resistance of a hash function h. We will see that for a hash function
h: !n 91
6.1 Cryptographic Hash Functions
to be secure, the string length n of the hash value cannot be too small. We can see this by using the birthday paradox (see Section 3.1.3). We proceed as follows:
Compute as many hash values as time and space permit.
Store the values along with their inverse images and sort them. Then look for a collision.
What is the probability of a collision? Or, looking at it slightly di erently, how many hash values do we have to compute to get a collision with probability greater than 1 ? We have the following
2 Number of possible hash values $ number of birthdays.
analogies:
Number of hash values computed $ number of people in the room.
We also assume that the strings from can be chosen such that the corresponding hash values have uniform distribution. If = {0,1}, then the number of possible hash values in n is obviously 2n.
We saw in Section 3.1.3: If k strings in are chosen, then k f(n):=11+p1+(8ln2)2n
2
is su cient for the probability of a collision to exceed 1/2. The following table show log2 ( f (n)),
that is, the minimal bit length, for typical sizes of n:
n
50
100
150
200
log2(f(n))
25.24
50.24
75.24
100.24
Hence, if we compute just over 2n/2 hash values, then the birthday attack finds a collision with probability > 1 . To foil the birthday attack, n has to be chosen such that the computation of
2
2n/2 hash values is infeasible. Today, n 128 or sometimes n 160 is required.
How to Construct Hash Functions
It is not known whether collision resistant hash functions even exist. Similarly, as mentioned before, it is not known whether secure and e cient encryption schemes exist.
1. However, if we assume that an encryption scheme is secure, we can construct compression functions that appear to be collision resistant. This can be done as follows.
Suppose we have a cryptosystem with P = C = K = {0, 1}n. The encryption functions are ek : {0,1}n ! {0,1}n, k 2 {0,1}n.
Then the compression function
h : {0,1}n {0,1}n ! {0,1}n
92
can be defined in either one of the following ways:
h(k, x) = ek (x) x,
h(k, x) = ek (x) x k, h(k, x) = ek (x k) x, h(k, x) = ek (x k) x k.
The values of the function h always have length n. To prevent the birthday attack, we must choose n 128; DES can therefore not be used.
As long as the underlying cryptosystem is secure, the compression functions appear to be collision resistant. However, no proof for this statement is known.
2. Given a collision resistant compression function, we can use it to construct a collision resistant hash function. The idea is as follows. Let
g : {0,1}m ! {0,1}n be a compression function, and let
r := m n.
Since g is a compression function, we have r > 0. Here we also assume that r > 1. (A typical
choice would be m = 640 and n = 128, so that r = 512.) We want to construct a hash function h : {0,1} ! {0,1}n.
We compute h(x) as follows:
Let x 2 {0, 1}.
Append 0s to the left so that the new string length is divisible by r .
Then append r 0s to the right.
Determine the binary representation of the original string length of x. Append 0s to the right so that the length is divisible by r 1.
Append a1to the left of each block of r 1 of this string.
The resulting representation string is appended to the right of the
previously normalized string.
The complete string is then written as a sequence
x1x2xt, xi 2{0,1}r, 1it. This is an intermediate step. Before continuing, we look at an example:
Example 5. Let r = 4. We follow the bullet points as above: Suppose that x = 111011.
Appending two 0s on the left: 0011 1011.
Appending four 0s on the right: 0011 1011 0000.
Binary expansion of the string length 6 of x: 110. Appending a 1 to the left: 1110.
93
6.1 Cryptographic Hash Functions
6.1 Cryptographic Hash Functions
Appending this to the right of the previous string: 0011 1011 0000 1110. Result of this intermediate step:
x1 =0011, x2 =1011, x3 =0000, x4 =1110.
Returning to the procedure: The hash value h(x) is now computed iteratively:
SetH0 :=0n =000.
ThendetermineHj :=g(Hj 1 xj),1jt.
(Recall that Hj 2 {0,1}n, xj 2 {0,1}r, g : {0,1}n+r ! {0,1}n.) Finally, we set h(x) = Ht.
Remark. It can be proven that the hash function h(x) is collision resistant as long as the compression function g(x) is collision resistant.
3. As mentioned before, there are no provably collision resistant compression functions. However, we can construct a compression function that can be proven collision resistant if computing discrete logarithms in (Z/pZ) is infeasible.
It works as follows: Let p be a prime;
q = p 1 also a prime; 2
a a primitive root mod p;
b randomly chosen in {1, 2, . . . , p 1}. Consider the function
{0,1,,q 1}2 !{1,2,,p 1},
(x1,x2)7!ax1bx2
(modp).
This becomes a compression function if we translate bitstrings of an appropriate length to nonnegative integers, and back.
Since q = p 1 , this function maps bitstrings (x1, x2) whose binary length is approximately 2
twice the binary length of p, to bitstrings whose length is at most that of p.
Example 6. Let p = 23 and q = 11. We choose the primitive root a = 5 mod p, and choose b at
randomin{1,2,,22},sayb=4. Then,forexample, h(5,10)=554102065 (mod23).
We now re-state and prove what we claimed above.
Theorem 6.1.
If computing discrete logarithms in (Z/pZ) is infeasible, then the above compression function is collision resistant.
~
Proof We prove this by showing that being able to find a collision of h implies the ability of computing the discrete logarithm of b for base a mod p.
94
6.1 Cryptographic Hash Functions
Let(x,x0)beacollisionofh,wherex=(x1,x2)andx0 =(x3,x4),withxi 2{0,1,,q
1}, 1 i 4. Then
which can be rewritten as
ax1bx2 ax3bx4 (modp),
ax1 x3 bx4 x2 (mod p). ax1 x3 ay(x4 x2) (mod p).
Since a is a primitive root mod p, this implies the congruence
x1 x3y(x4 x2) (modp 1), or x1 x3y(x4 x2) (mod2q).
Does this congruence have a solution y? If so, then we have found the discrete logarithm of b for base a mod p.
The answer is yes, if
d:=gcd(x4 x2,p 1) divides x1 x3.
Because of the choice of x2 and x4, we have |x4 x2| < q, and since p 1 = 2q, this implies d 2 {1,2}. If d = 1, then there is a unique solution mod p 1, which is the discrete log. Ifd=2,thentherearetwodi erentsolutionsmodp 1,andthediscretelogcanbefound by trying both. Remarks. (1) This shows that collision resistance of this compression function has been reduced to a well-studied problem in number theory.(2) However, this compression function is not very e cient since it requires modular exponentiation. It is therefore mainly of theoretical interest, in addition to serving as a review of some earlier concepts.Message Authentication CodesWe saw in Example 4 how a hash function can be used to check whether a file has been changed. If not only the integrity of a document, but also the authenticity is to be guaranteed, then we can use the following:Definition 6.5.A parametrized hash function is a family {hk : k 2 K } of hash functions. Here, K is a set, called the key space of h. A parametrized hash function is also called a message authentication code, or MAC.Example 7. For a fixed n, consider a hash functiong : {0,1} ! {0,1}n.Denote by y the discrete logarithm of b for base a mod p, i.e., b ay (mod p). Then95|It can be transformed into the MAChk : {0,1} ! {0,1}n, x 7! g(x) k,With key space {0, 1}n.The next example shows how a MAC can be used.Example 8. Professor Alice sends the final grades of her cryptography class (with Eve and Oscar among the students) via e-mail to Bob, the Registrars secretary. Bob needs to be convinced that this e-mail is authentic.For proof of authenticity, a MAC {hk : k 2 K } is used. Alice and Bob exchange a secret key. Together with her list x, Alice also sends the hash value y = hk (x) to Bob.Bob then computes the hash value y0 = hk (x0) of the message x0 he received. If y = y0, he accepts the list as authentic.The procedure in this last example proves the authenticity only if without knowledge of the key k it is infeasible to compute a pair (x0, hk (x0)) from the pair (x, hk (x)) with x , x0.6.2 DigitalSignaturesDigital signatures are used to sign” electronic documents. Such signatures have properties similar to handwritten signatures. We first discuss this analogy, and then describe some of the known signature schemes.What is the purpose of a handwritten signature, and how does it work? To quote Wikipedia: The traditional function of a signature is evidential: It is to give evidence of:1. The provenance of the document (identity)2. The intention (will) of an individual with regard to that document”.Typically, a signature is attached to the (paper) document in question, and it has a number of important properties:1. It is fast to execute by the signer, independent of the length of the document;2. It is di cult (but not impossible) to forge;3. It is easy to establish the authenticity by the recipient of the document or by the signer.A digital signature of an electronic document should, in principle, have the same properties. So, why dont we just digitize our handwritten signature and append it to the digital document?The problem here is that, while copying and/or cutting and then pasting is easily detected on a paper document, such electronic forgery is quite easy to do but di cult to detect. Therefore we require that a digital signature cannot be separated from a message and attached to another one. In other words, a digital signature has the following properties: It is not only tied to the signer, but is also tied to the document that is signed.966.2 Digital Signatures Butfor some integer k, and thereforede1 (mod ‘(n)), thatis, de=1+k'(n) zye m1+k'(n) =mm'(n)k m1k =m (modn),as required.5. Why is this thought to be secure? Suppose Eve wants to attach Alices signature y to another message m1. She cannot simply use the pair (m1, y) since ye . m1 (mod n).976.2 Digital Signatures Furthermore, it needs to be easy to verify by other parties.Digital signature schemes therefore consist of two distinct steps: The signing process, and the verification process.Another consideration is the fact that signed documents are often public, which should also be possible for digitally signed documents. Therefore we are not trying to encrypt the document in question.6.2.1 TheRSASignatureSchemeSuppose that Bob has a document m that Alice agrees to sign. (As usual, we assume that m is a large integer that has been translated from the bitstring representing the document.) They do the following.1. In preparation for the signing process, Alice does the following: She generates two large primes p, q and computes n = pq. She chooses e such that 1 < e < ‘(n) and gcd(e, ‘(n)) = 1. She calculates d such that ed 1 (mod ‘(n)). Her public key is (e, n), while d, p, q must be kept private.2. This is how Alice signs the document: Alices signature on the document m is y md (mod n). The pair (m, y) is then made public.3. This is how Bob verifies that Alice really signed the document: He obtains Alices public (e, n). He calculates z ye (mod n). If z = m, then Bob accepts the signature as valid; otherwise he rejects it.4. Why does this work? Just like with RSA, we havezye (md)e =mde (modn).6.2 Digital Signatures Therefore she needs y1 with y1e m1 (mod n). But this is the same problem as decrypting an RSA ciphertext” m1to obtain the plaintext” y1. This signature scheme is therefore as secure as RSA.Important remark. Some attacks on the RSA signature scheme are known, which have to be guarded against through careful implementations and the right protocols. This is part of applied or practical cryptography, which goes beyond the scope of this course.6.2.2 TheElGamalSignatureSchemeJust as the RSA cryptosystem was modified to give a signature scheme, we can also use the ElGamal cryptosystem for this purpose. One feature that is di erent from RSA is that there are many di erent signatures that are valid for a given message.1. In preparation for the signing process, Alice does the following: She chooses a large prime p and a primitive root g. Then she chooses an integer a, 1 a p 2 and calculates A ga (mod p). The values (p, g, A) are made public; a must remain private. 2. This is how Alice signs a document or message m: She selects a random k such that gcd(k, p 1) = 1. Then she computes Finally, she computesr gk (mod p).sk 1(m ar) (modp 1). The signed message is the triple (m, r, s).3. This is how Bob verifies the signature: He obtains Alices public key (p, g, A). He computesv1 Arrs (mod p) and v2 Argm (mod p). The signature is considered valid if and only if v1 v2 (mod p). 4. Why does this work? Assume the signature is valid. Sincewe havesk 1(m ar) (modp 1),skm ar (modp 1), so msk+ar (modp 1).986.2 Digital SignaturesTherefore, using the same Fermat argument” as in Step 4 of the RSA signature scheme, that is, a congruence mod p 1 in the exponent yields an overall congruence mod p, we getv2 gm gsk+ar ga r gks Arrs v1 (mod p). 5. Why is this thought to be secure? (a) Suppose that Eve wants to fake Alices signature on a di erent document m0. However, she cannot compute the corresponding s since she doesnt know Alices secretkey a. Obtaining a would be equivalent to solving the discrete logarithm problem. (b) Suppose Eve tries to bypass this step by finding an s0 that satisfies the verificationcondition. This means that s0 needs to satisfyArrs0 gm0 (mod p), or rs0 A rgm0 (mod p). But this is once again the discrete logarithm problem. (c) Suppose Eve doesnt give up and first chooses an s0 and then tries to find the corre-sponding r. However, solving for r is similar to a discrete log problem, only more complicated.Important: If Alice wants to sign a second document, she must choose a random value of k. This is for the following reason: Suppose she uses the same k for messages m1 and m2. Then the same value of r is used in both signatures. Eve will therefore see that k has been usedtwice, and can exploit this fact as follows:the s values are di erent, say s1 and s2. Eve knows that Therefores1k m1 ar s2k m2 (mod p 1). (s1 s2)k m1 m2 (mod k 1).Let d := gcd(s1 s2, p 1). Then there are d solutions to this congruence, which can be found with the Euclidean algorithm. Usually d is small, so Eve can compute gk (mod p), until she gets the value r. Now she knows k, and she solvesar m1 ks1 (mod p 1)for a. There are gcd(r, p 1) possibilities, again usually a small number. Then Eve computes ga mod p for each one of these, until she gets A.Eve has now found Alices secret key a, and all is lost. For instance, she can reproduce Alices signatures at will.Some further considerations: Often it is not the document, but a hash value of the document that will be signed. Therefore, the hash function used must be secure, especially against a birthday attack”.996.2 Digital Signatures The Digital Signature Algorithm” (DSA), adopted as standard in 1994, is based on the ElGamal signature scheme. It uses a hash function with 160-bit output, and has some other built-in safety features. 100
Reviews
There are no reviews yet.