Lecture Notes

APPLIED CRYPTOGRAPHY AND DATA

SECURITY
Dr. Christof Paar

Cryptography and Information Security (CRIS) Group

Department of Electrical & Computer Engineering
Worcester Polytechnic Institute
Worcester, MA 01609

[Link]
Preface
These lecture notes are not meant as a replacement of a more comprehensive textbook.
Rather, the notes at hand present the essentials of modern applied cryptography in compact
form and should accompany the lecture in conjunction with one of the books mentioned
below. The notes grew out of an introductory graduate course in cryptography which I have
taught twelve times by now at Worcester Polytechnic Institute and in industry. Remarks,
questions, and classroom discussions by our graduate students as well as by the sta of GTE
Governments Systems, MA, and Philips Research, NY, greatly helped to improve the lecture
notes.
I tried to present modern cryptography in a way that is accessible for engineers without
any background in abstract mathematics. There is a focus on private-key and public-key
algorithms, an understanding of which appears to be extremely helpful for the development
of real-world applications. However, protocol-related issues such as security services, key
distributions, and identi cation are also treated.
The lecture notes work well together with an actual book. I've used Doug Stinson's
excellent textbook, [Sti95], as well as Bruce Schneier's comprehensive compilation, [Sch93].
The treatment of topics in these lecture notes loosely follow the presentation in Stinson's
book. For those interested in an in-depth understanding of the eld, including many the-
oretical topics, the handbook by Alfred Menezes, Paul van Oorschot, and Scott Vanstone,
[AM97], can be strongly recommended for additional reading. Another good book which is
more introductory is William Stalling's recent text book [Sta99].
I would like to express my deep gratitude to my graduate students Jorge Guajardo and
Martin Rosner, who were in charge of typing the notes and of drawing all gures and tables.
Their many suggestions and proof reading greatly improved the notes.

Christof Paar
May 2000
Table of Contents
1 Introduction to Cryptography and Data Security 1
1.1 Literature Recommendations . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Private-Key Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4 Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.4.1 Attacks against Cryptoalgorithms . . . . . . . . . . . . . . . . . . . . 4
1.5 Some Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.6 Simple Blockciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.6.1 Shift Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.6.2 Ane Cipher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

2 Stream Ciphers 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 One-Time Pad and Pseudo-Random Generators . . . . . . . . . . . . . . . . 15
2.3 Synchronous Stream Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.1 Linear Feedback Shift Registers (LFSR) . . . . . . . . . . . . . . . . 18
2.3.2 Clock Controlled Shift Registers . . . . . . . . . . . . . . . . . . . . . 20
2.4 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.4.1 Known Plaintext Attack Against LFSRs . . . . . . . . . . . . . . . . 23

ii
3 Some Results From Information Theory 25
3.1 Levels of Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 Computational Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Cryptography and Coding . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.4 Confusion and Di usion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Data Encryption Standard (DES) 28

4.1 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.1.2 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.3 Core Iteration / f-Function . . . . . . . . . . . . . . . . . . . . . . . . 31
4.1.4 Key Schedule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
4.2 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
4.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.1 Hardware . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.3.2 Software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4.4.1 Exhaustive Key Search . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.4.2 Di erential Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . 40
4.4.3 Linear Cryptanalysis . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
4.5 DES Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

5 Rijndael { The Advanced Encryption Standard 43

5.1 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.1 Basic Facts about AES . . . . . . . . . . . . . . . . . . . . . . . . . . 43
5.1.2 Chronology of the AES Process . . . . . . . . . . . . . . . . . . . . . 44
5.2 Rijndael Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
5.3 Some Mathematics: A Very Brief Introduction to Galois Fields . . . . . . . . 47

iii
 5.4 Internal Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4.1 Byte Substitution Layer . . . . . . . . . . . . . . . . . . . . . . . . . 52
5.4.2 Di usion Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5.4.3 Key Addition Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5.5 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

6 More about Block Ciphers 56

6.1 Modes of Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
6.1.1 Electronic Codebook Mode (ECB) . . . . . . . . . . . . . . . . . . . 56
6.1.2 Cipher Block Chaining Mode (CBC) . . . . . . . . . . . . . . . . . . 57
6.1.3 Cipher Feedback Mode (CFB) . . . . . . . . . . . . . . . . . . . . . . 58
6.1.4 Counter Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6.2 Key Whitening . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
6.3 Multiple Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3.1 Double Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3.2 Triple Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

7 Introduction to Public-Key Cryptography 66

7.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
7.2 One-Way Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
7.3 Overview of Public-Key Algorithms . . . . . . . . . . . . . . . . . . . . . . . 68
7.4 Important Public-Key Standards . . . . . . . . . . . . . . . . . . . . . . . . 69
7.5 More Number Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.5.1 Euclid's Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
7.5.2 Euler's Phi Function . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

8 RSA 77
8.1 Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
8.2 Computational Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

iv
 8.2.1 Choosing p and q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
8.2.2 Choosing a and b . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.2.3 Encryption/Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . 81
8.3 Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.3.1 Brute Force . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.3.2 Finding (n) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.3.3 Finding a directly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
8.3.4 Factorization of n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
8.4 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

9 The Discrete Logarithm (DL) Problem 87

9.1 Some Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
9.1.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
9.1.2 Finite Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
9.2 The General DL Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
9.3 Attacks for the DL Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
9.4 Die-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.4.1 Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
9.4.2 Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

10 Elliptic Curve Cryptosystem 97

10.1 Elliptic Curves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
10.2 Cryptosystems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102
10.2.1 Die-Hellman Key Exchange . . . . . . . . . . . . . . . . . . . . . . 102
10.2.2 Menezes-Vanstone Encryption . . . . . . . . . . . . . . . . . . . . . . 103
10.3 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

11 ElGamal Encryption Scheme 105

11.1 Cryptosystem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105

v
 11.2 Computational Aspects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.2.1 Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.2.2 Decryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
11.3 Security of ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109

12 Digital Signatures 110

12.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
12.2 RSA Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
12.3 ElGamal Signature Scheme . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

13 Hash Functions 115

13.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
13.2 Security Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
13.3 Hash Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

14 Message Authentication Codes (MACs) 122

14.1 Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122
14.2 MACs from Block Ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
14.3 HMAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124

15 Security Services 126

15.1 Attacks Against Information Systems . . . . . . . . . . . . . . . . . . . . . . 126
15.2 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
15.3 Privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
15.4 Integrity and Sender Authentication . . . . . . . . . . . . . . . . . . . . . . . 129
15.4.1 Digital Signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
15.4.2 MACs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
15.4.3 Integrity and Encryption . . . . . . . . . . . . . . . . . . . . . . . . . 130

vi
16 Key Establishment 131
16.1 Introduction . . . . . . . . . . . . . . . . . .... . . . . . . . . . . . . . . . 131
16.2 Private-Key Approaches . . . . . . . . . . .... . . . . . . . . . . . . . . . 132
16.2.1 The n2 Key Distribution Problem . .... . . . . . . . . . . . . . . . 132
16.2.2 Key Distribution Center (KDC) . . .... . . . . . . . . . . . . . . . 133
16.3 Public-Key Approaches . . . . . . . . . . . .... . . . . . . . . . . . . . . . 134
16.3.1 Man-In-The-Middle Attack . . . . . .... . . . . . . . . . . . . . . . 134
16.3.2 Certi cates . . . . . . . . . . . . . .... . . . . . . . . . . . . . . . 135
16.3.3 Die-Hellman Exchange with Certi cates . . . . . . . . . . . . . . . 137
16.3.4 Authenticated Key Agreement . . . .... . . . . . . . . . . . . . . . 137

17 Case Study: The Secure Socket Layer (SSL) Protocol 139

17.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
17.2 SSL Record Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
17.2.1 Overview of the SSL Record Protocol . . . . . . . . . . . . . . . . . . 141
17.3 SSL Handshake Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
17.3.1 Core Cryptographic Components of SSL . . . . . . . . . . . . . . . . 143

18 Introduction to Identi cation Schemes 145

18.1 Private-key Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

vii
Chapter 1

Introduction to Cryptography and

Data Security

1.1 Literature Recommendations

Course Textbooks: [Sti95] or [Sch93].
Further Reading - the following books are excellent supplements to the course textbook:
1. [AM97] - great compilation of theoretical and practical aspects of many crypto schemes.
Unique since it includes many theoretical topics that are hard to nd otherwise. Highly
recommended.
2. [Sta95] - Very readable treatment of algorithms and standards relevant to cryptography
in networks.

1.2 Overview
Brief History of Cryptography
 Private-Key: all encryption and decryption schemes dating from BC to 1976.
1
 CRYPTOLOGY

Cryptography Cryptanalysis

Private-Key Public-Key Protocols

Block cipher Stream cipher

Figure 1.1: Overview on the eld of cryptology

 Public-Key: in 1976 the rst public-key scheme was introduced by Die-Hellman key
exchange protocol.
 Hybrid Approach: in today's protocol, very often hybrid schemes are applied which
use private and public-key algorithms.

1.3 Private-Key Cryptosystems

Sometimes these schemes are also referred to as symmetric, single-key, and secret-key ap-
proaches.
Problem Statement: Alice and Bob want to communication over an un-secure channel
(e.g., computer network, satellite link). They want to prevent Oscar (the bad guy) from
listening.
Solution: Use of private-key cryptosystems (these have been around since BC) such that
if Oscar reads the encrypted version of the message over the un-secure channel, he will
y x

not be able to understand its content because x is what really was sent.

2
 Oscar
(bad)

x y x
Alice Encryption Decryption Bob
(good) e() d() (good)

k k
Secure Channel

Key
Generator

Figure 1.2: Private-key cryptosystem

Some important de nitions:

1a) x is called the \plaintext"
1b) P= f x1 ; x2 ; : : : ; xp g is the ( nite) \plaintext space"
2a) y is called the \ciphertext"
2b) C= f y1 ; y2 ; : : : ; yc g is the ( nite) \ciphertext space"
3a) k is called the \key"
3b) K= f k1 ; k2 ; : : : ; kl g is the nite \key space"
4a) There are l encryption functions eki : P!C (or: ( ) = y)
eki x

4b) There are l decryption functions dki : C!P (or: ( ) = x)

d ki y

4c) ek1 and dk2 are inverse functions if k1 = k2 : dki (y) = dki (eki (x)) = x for all ki 2K
Example: Data Encryption Standard (DES)
 P = C = f0 1 2 ; ; ;:::; 264 , 1g (each xi has 64 bits: xi = 010 ::: 0110)
 K= f0 1 2 ; ; ;:::; 256 , 1g (each ki has 56 bits)
 encryption ( k ) and decryption ( k ) will be described in Chapter 4
e d

3
1.4 Cryptanalysis
De nition: The science of recovering the plaintext x from the ciphertext y without the
knowledge of the key (Oscar's job).

Rules of the game:

The cryptanalysis rules are known as Kerckho 's Principle:
1. Oscar knows the cryptosystem (encryption and decryption algo-
rithms).
2. Oscar does not know the key.

1.4.1 Attacks against Cryptoalgorithms

1. Ciphertext-only attack
Oscar's knowledge: some y1 = k ( 1 ), 2 = k ( 2 ),
e x y e x :::

Oscar's goal : obtain 1 or the key .

x ; x2 ; : : : k

2. Known plaintext attack

Oscar's knowledge: some pairs ( x1 ; y1 = k ( 1 )) (
e x ; x2 ; y2 = k ( 2 ))
e x :::

Oscar's goal : obtain the key . k

3. Chosen plaintext attack

Oscar's knowledge: some pairs ( x1 ; y1 = k ( 1 )) (
e x ; x2 ; y2 = k ( 2 ))
e x ::: of which he can choose
x1 ; x2 ; : : :

Oscar's goal : obtain the key . k

4. Chosen ciphertext attack

Oscar's knowledge: some pairs ( x1 ; y1 = k ( 1 )) (
e x ; x2 ; y2 = k ( 2 ))
e x ::: of which he can choose

4
y1; y2; : : :
Oscar's goal : obtain the key k.

1.5 Some Number Theory

Modulo operation:
Question: What is 12 mod 9?
Answer: 12 mod 9  3
or 12  3 mod 9.

De nition 1.5.1 Modulo Operation

Let a; r; m 2 Z (where Z is a set of all integers) and m > 0. We write
a  r mod m if m divides r , a.
\m" is called the modulus.
\r" is called the remainder.

Some remarks on the modulo operation:

 How is the remainder computed?
It is always possible to write a 2 Z , such that
a = q
m + r; 0  r < m
Now since a , r = q
m (m divides a , r) and a  r mod m.
Note that r 2 f0; 1; 2; : : : ; m , 1g.
Example:
a = 42; m = 9
42 = 4
9 + 6 therefore 42  6 mod 9.

5
  C programming command : \%" (C can return a negative value)
r = 42 % 9 returns r = 6
but r = -42 % 9 returns r = -6 ! if remainder is negative, add modulus m:
,6 + 9 = 3  ,42 mod 9

Ring:
De nition 1.5.2 The \ring Zm" consists of:
1. The set Zm = f0; 1; 2; : : : ; m , 1g
2. Two operations \+" and \" for all a; b 2 Zm such that:
 a + b  c mod m (c 2 Zm)
 a  b  d mod m (d 2 Zm)
Example: m = 9
Z9 = f0; 1; 2; 3; 4; 5; 6; 7; 8g
6 + 8 = 14  5 mod 9
6  8 = 48  3 mod 9

6
De nition 1.5.3 Some important properties of the ring Zm = f0; 1; 2; : : :; m , 1g
1. The additive identity is the element zero \0": a + 0 = a mod m, for any
a 2 Zm.
2. The additive inverse \,a" of \a" is such that a+(,a)  0 mod m: ,a = m,a,
for any a 2 Zm.
3. Addition is closed: i.e., for any a; b 2 Zm, a + b 2 Zm .
4. Addition is commutative: i.e., for any a; b 2 Zm, a + b = b + a.
5. Addition is associative: i.e., for any a; b 2 Zm , (a + b) + c = a + (b + c).
6. The multiplicative identity is the element one \1": a  1  a mod m, for any
a 2 Zm.
7. The multiplicative inverse \a,1 " of \a" is such that a  a,1 = 1 mod m: An
element a has a multiplicative inverse \a,1" if and only if gcd(a; m) = 1.
8. Multiplication is closed: i.e., for any a; b 2 Zm , ab 2 Zm .
9. Multiplication is commutative: i.e., for any a; b 2 Zm , ab = ba.
10. Multiplication is associative: i.e., for any a; b 2 Zm , (ab)c = a(bc).

7
Some remarks on the ring Zm:
 Roughly speaking, a ring is a structure in which we can add, subtract, multiply, and
sometimes divide.
 De nition 1.5.4 If gcd(a; m) = 1, then a and m are \relatively prime" and the
multiplicative inverse of a exists.
Example:
i) Question: does multiplicative inverse exist with 15 mod 26?
Answer: yes | gcd(15; 26) = 1
ii) Question: does multiplicative inverse exist with 14 mod 26?
Answer: no | gcd(14; 26) =6 1
 The modulo operation can be applied whenever we want:
(a + b) mod m = [(a mod m) + (b mod m)] mod m.
(a  b) mod m = [(a mod m)  (b mod m)] mod m.
Example: 38 mod 7 = ?
i) 38 = 34
34 = (81 mod 7)
(81 mod 7)  4
4 = 16  2 mod 7.
ii) 38 = 6561  2 mod 7, since 6561 = 937
7 + 2.
As we see, it is almost always of computational advantage to apply the modulo reduc-
tion as soon as we can.
 The ring Zm, and thus the integer arithmetic with the modulo operation, is of central
importance to modern public-key cryptography. In practice, the integers are repre-
sented with 150{2048 bits.

8
1.6 Simple Blockciphers
Recall:
Private-key Systems

Block ciphers Stream ciphers

Figure 1.3: Classi cation of private-key systems

Idea: The message string is divided into blocks (or cells) of equal length that are then
encrypted and decrypted.
Input: message string X ! X = x1 ; x2 ; x3; : : : ; xn, where each xi is one block.
Cipher: Y = y1; y2; y3; : : : ; yn; with yi = ek (xi) where the key k is xed.

9
1.6.1 Shift Cipher
One of the most simple ciphers where the letters of the alphabet are assigned a number as
depicted in Table 1.1.
A B C D E F G H I J K L M
0 1 2 3 4 5 6 7 8 9 10 11 12
N O P Q R S T U V W X Y Z
13 14 15 16 17 18 19 20 21 22 23 24 25

Table 1.1: Shift cipher table

De nition 1.6.1 Shift Cipher

Let P = C = K = Z26. x 2 P , y 2 C , k 2 K.
Encryption: ek (x) = x + k mod 26.
Decryption: dk (y ) = y , k mod 26.

Remark:
If k = 3 the the shift cipher is given a special name | \Caesar Cipher".

Example:
k = 17,
plaintext:
X = x1 ; x2 ; : : : ; x6 = ATTACK .
X = x1 ; x2 ; : : : ; x6 = 0; 19; 19; 0; 2; 10.

encryption:
y1 = x1 + k mod 26 = 0 + 17 = 17 mod 26 = R

10
 y2 = y3 = 19 + 17 = 36  10 mod 26 = K
y4 = 17 = R
y5 = 2 + 17 = 19 mod 26 = T
y6 = 10 + 17 = 27  1 mod 26 = B

ciphertext: Y = y1; y2; : : : ; y6 = R K K R T B.

Attacks on Shift Cipher

1. Ciphertext-only: Try all possible keys (jkj = 26). This is known as \brute force attack"
or \exhaustive search".
Secure cryptosystems require a suciently large key space. Minimum requirement
today is jK j > 280 , however for long-term security, jK j  2100 is recommended.
2. Same cleartext maps to same ciphertext ) can also easily be attacked with letter-
frequency analysis.

11
1.6.2 Ane Cipher
This cipher is an extension of the Shift Cipher (yi = xi + k mod m).

De nition 1.6.2 Ane Cipher Let P = C = Z26.

encryption: ek (x) = a
x + b mod x.
key: k = (a; b) where a; b 2 Z26.
decryption: a
x + b = y mod 26.
a
x = (y , b) mod 26.
x = a,1
(y , b) mod 26.
restriction: gcd(a; 26) = 1 in order for the ane cipher to work since
a,1 does not always exist.

Question: How is a,1 obtained?

Answer: a,1  a11 mod 26 (the proof for this is in Chapter 6)
or by trial-and-error for the time being.

12
Chapter 2
Stream Ciphers
Further Reading: [Sim92, Chapter 2]

2.1 Introduction
Remember classi cation:
Private-key Systems

Block ciphers Stream ciphers

Figure 2.1: Private-key cipher classi cation

Block Cipher: Y = y1; y2; : : : ; yn = ek (x1); ek (x2 ); : : : ; ek (xn),

e.g. the key does not change with every block
Stream Cipher: Y = y1; y2; : : : ; yn = ez1 (x1 ); ez2 (x2 ); : : : ; ez (xn )
n

with the \keystream" = z1 ; z2; : : : ; zn

13
 Zi Zi
Xi Yi Xi

Figure 2.2: Most Popular Encryption/Decryption Function

Most popular en/decryption function: modulo 2 addition

Assume: xi ; yi; zi 2 f0; 1g

yi = ez (xi ) = xi + zi mod 2 ! encryption

i

xi = ez (yi) = yi + zi mod 2 ! decryption

i

Remarks:
1. Developed by Vernam in 1917 for Baudot Code on teletypewriters.
2. The modulo 2 operation is equivalent to a 2-input XOR operation.
Why are encryption and decryption identical operations? Truth table of modulo 2
addition:
a b c = a + b mod 2
0 0 0 + 0 = 0 mod 2
0 1 0 + 1 = 1 mod 2
1 0 1 + 0 = 1 mod 2
1 1 1 + 1 = 0 mod 2
.

) modulo 2 addition yields the same truth table as the XOR operation.
3. Encryption and decryption are the same operation, namely modulo 2 addition (or
XOR).
Why? We show that decryption of ciphertext bit yi yields the corresponding plaintext
14
 bit.
+ zi}) + zi = xi + (zi + zi )  xi mod 2.
Decryption: yi + zi = (|xi {z
encryption
Note that zi + zi  0 mod 2 for zi = 0 and for zi = 1.
Example: Encryption of the letter `A' by Alice.
`A' is given in ASCII code as 6510 = 10000012.
Let's assume that the rst key stream bits are ! z1 ; : : : ; z7 = 0101101

Encryption by Alice: plaintext xi : 1000001 = `A' (ASCII symbol)

key stream zi : 0101101
ciphertext yi : 1101100 = `l' (ASCII symbol)
Decryption by Bob: ciphertext yi : 1101100 = `l' (ASCII symbol)
key stream zi : 0101101
plaintext xi : 1000001 = `A' (ASCII symbol)

2.2 One-Time Pad and Pseudo-Random Generators

De nition 2.2.1 Unconditional Security
A cryptosystem is unconditionally secure if it cannot be broken even
with in nite computational resources.

De nition 2.2.2 One-time Pad (OTP)

A cryptosystem developed by Mauborgne based on Vernam's stream ci-
pher consisting of:
jPj = jCj = jKj,
with xi ; yi; ki 2 f0; 1g.
encrypt ! ek (xi) = xi + ki mod 2.
i

decrypt ! dk (yi) = yi + ki mod 2.

i

15
 Theorem 2.2.1 The OTP is unconditionally secure if keys are only
used once.
Remarks:
1. OTP is the only provable secure system:

y0 = x0 + K0 mod 2
y1 = x1 + K1 mod 2
...

each equality is a linear equation with 2 unknowns.

) for every yi, xi = 0 and xi = 1 are equally likely.
) holds only if K0; K1 ; : : : are not related to each other, i.e., Ki must be generated
trully randomly.
2. OTP are impractical for most applications.
Question: Can we \emulate" a OTP by using a short key?

initial key (short)

k k

Oscar
key-stream key-stream
Alice generator generator Bob

zi zi

xn ... x1 x0 yn ... y1 y0 xn ... x1 x0

Figure 2.3: Stream cipher model

16
Classi cation by key-stream generator:
a) \synchronous stream cipher"
zi = f (k) ! pseudo-random generator (PRG).
b) \asynchronous stream cipher"
zi = f (k; yi,1; yi,2; : : : ; yi,N ) ! feedback of cipher.
c) The key issue is that Bob has to `match' the exact zi to get the correct message.
In order to do this, both key-stream generators have to be synchronized.

Encr.
xi xi zi = yi yi

zi
feedback path only
f( ) in asynchronous stream ciphers

Figure 2.4: Asynchronous stream cipher

It is important to note that key stream generators must not only possess good statistical
properties, which is true for other pseudo-random generatores as well, but they must also be
cryptographically secure:

De nition 2.2.3 Cryptographically secure pseudo-random generators

A pseudo random generator (key stream generator) is cryptographically
secure if it is unpredictable. That is, given the rst n output bits of the
generator, it is computatinally infeasible to compute the bits n + 1; n +
2; : : :

17
2.3 Synchronous Stream Ciphers
The keystream z1 ; z2 ; : : : is a pseudo-random sequence which depends only on the key.

2.3.1 Linear Feedback Shift Registers (LFSR)

An LFSR consists of m storage elements ( ip- ops) and a feedback network. The feedback
network computes the input for the \last" ip- op as XOR-sum of certain ip- ops in the
shift register.
Example: We consider an LFSR of degree m = 3 with ip- ops K2 , K1, K0 , and a feedback
path as shown below.
mod 2 addition / XOR

K2 K1 K0

Z2 Z1 Z0 Z0 Z 1 ........ Z 6

CLK

Figure 2.5: Linear feedback shift register

K2 K1 K0
1 0 0
0 1 0
1 0 1
1 1 0
1 1 1
0 1 1
0 0 1
1 0 0

18
Mathematical description for keystream bits zi with z0 ; z1; z2 as initial settings:
z3 = z1 + z0 mod 2
z4 = z2 + z1 mod 2
z5 = z3 + z2 mod 2
...
general case: zi+3 = zi+1 + zi mod 2; i = 0; 1; 2; : : :

Expression for the LFSR:

........

C m-1 C1 C0
K m-1 K1 K0

........ OUTPUT

CLK

Figure 2.6: LFSR with feedback coecients

C0 ; C1; : : : ; Cm,1 are the feedback coecients. Ci = 0 denotes an open switch (no con-
nection), Ci = 1 denotes a closed switch (connection).

,1
mX
zi+m = Cj
zi+j mod 2; Cj 2 f0; 1g; i = 0; 1; 2; : : :
j =0

The entire key consists of:

k = f(C0; C1; : : : ; Cm,1 ); (z0; z1; : : : ; zm,1 ); mg

Example:
k = f(C0 = 1; C1 = 1; C2 = 0); (z0 = 0; z1 = 0; z2 = 1); 3g
19
 Theorem 2.3.1 The maximum sequence length generated by the LFSR
is 2m , 1.
Proof:
There are only 2m di erent states (k0; : : : ; km) possible. Since only the current
state is known to the LFSR, after 2m clock cycles a repetition must occur. The
all-zero state must be excluded since it repeats itself immediately.
Remarks:
1.) Only certain con gurations (C0; : : : ; Cm,1) yield maximum length LFSRs.
For example:
if m = 4 then (C0 = 1; C1 = 1; C2 = 0; C3 = 0) has length of 2m , 1 = 15
but (C0 = 1; C1 = 1; C2 = 1; C3 = 1) has length of 5
2.) LFSRs are sometimes speci ed by polynomials.
such that the P (x) = xm + Cm,1 xm,1 + : : : + C1x + C0.
Maximum length LFSRs have \primitive polynomials".
These polynomials can be easily obtained from literature (Table 16.2 in [Sch93]).
For example:
(C0 = 1; C1 = 1; C2 = 0; C3 = 0) () P (x) = 1 + x + x4

2.3.2 Clock Controlled Shift Registers

Example: Alternating stop-and-go generator.

20
 LFSR1 Out1

LFSR2 Out2

Out4 = Zi (key stream)

CLK

LFSR3 Out3

Figure 2.7: Stop-and-go generator example

21
Basic operation:
When Out1 = 1 then LFSR2 is clocked otherwise LFSR3 is clocked.
Out4 serves as the keystream and is a bitwise XOR of the results from LFSR2 and LFSR3.

Security of the generator:

 All three LFSRs should have maximum length con guration.
 If the sequence lengths of all LFSRs are relatively prime to each other, then the
sequence length of the generator is the product of all three sequence lengths, i.e.,
L = L1
L2
L3 .
 A secure generator should have LFSRs of roughly equal lengths and the length should
be at least 128: m1  m2  m3  128.

22
2.4 Attacks
2.4.1 Known Plaintext Attack Against LFSRs
Assumption:
For a known plaintext attack, we have to assume that m is known.
Idea:
This attack is based on the knowledge of some plaintext and its corresponding ciphertext.
i) Known plaintext ! x0 ; x1; : : : ; x2m,1 .
ii) Observed ciphertext ! y0; y1; : : : ; y2m,1.
iii) Construct keystream bits ! zi = xi + yi mod 2; i = 0; 1; : : : ; 2m , 1.
Goal:
To nd the feedback coecients Ci.

Using the LFSR equation to nd the Ci coecients:

,1
mX
zi+m = Cj
zi+j mod 2; Cj 2 f0; 1g
j =0
We can rewrite this in a matrix form as follows:
i=0 zm = C0z0 + C1z1 + : : : + Cm,1zm,1 mod 2:
i=1 zm+1 = C0z1 + C1z2 + : : : + Cm,1zm mod 2:
... ... ... ... ... (2.1)

i=m,1 z2m,1 = C0zm,1 + C1 zm + : : : + Cm,1 z2m,2 mod 2:

Note:
We now have m linear equations in m unknowns C0; C1; : : : ; Cm,1. The Ci co-
ecients are constant making it possible to solve for them when we have 2m
plaintext-ciphertext pairs.

23
Rewriting Equation (2.1) in matrix form, we get:
2 3 2 3 2 3
66 z0 ::: zm,1 77 66 c0 7
7 6
6
zm 77
66 ... ... 77
66 ... 7
7 = 6
6
... 77 mod 2 (2.2)
64 7
5 6 4 7
5 6 4 7
5
zm,1 : : : z2m,2 cm,1 z2m,1
Solving the matrix in (2.2) for the Ci coecients we get:
2 3 2 3,1 2 3
66 c0 77 66 z0 ::: zm,1 77 66 zm 7
7
66 ... 77 = 66 ... ... 77
66 ... 7
7 mod 2 (2.3)
64 75 64 7
5 6
4 7
5
cm,1 zm,1 ::: z2m,2 z2m,1
Summary:
By observing 2m output bits of an LFSR of degree m and matching them to the
known plaintext bits, the Ci coecients can exactly be constructed by solving a
system of linear equations of degree m.

) LFSRs by themselves are extremely un-secure! However, combinations of them

such as the Alternating stop-and-go generator can be secure.

24
Chapter 3
Some Results From Information
Theory
3.1 Levels of Security
De nition 3.1.1 Unconditional Security
A cryptosystem is unconditionally secure if it cannot be broken even
with in nite computational resources.

Theorem 3.1.1 The OTP is unconditionally secure if keys are only

used once.

3.2 Computational Security

For all known practical cryptosystems we have:

De nition 3.2.1 Computational Security

A system is \computational secure" if the best possible algorithm
for breaking it requires N operations, where N is very large and known.

25
Unfortunately, all known practical systems are only computational secure for known algo-
rithms.
De nition 3.2.2 Relative Security
A system is \relative secure" if its security relies on a well studied, very
hard problem.
Example:
A system S is secure as long as factoring of large integers is hard (this is believed
for RSA).

3.3 Cryptography and Coding

There are three basic forms of coding in modern communication systems: source coding,
channel coding, and encryption. From an information theoretical and practical point of
view, the three forms of coding should be applied as follows:
removes adds
redundancy redundancy

Data Source Channel

Source Encryption
Coding Coding

introduces
errors and Channel
eavesdropping

Data Source Channel

Decoding Decryption Decoding
Sink

Figure 3.1: Communication coding system model

26
3.4 Confusion and Di usion
According to Shannon, there are two basic approaches to encryption.
1. Confusion | encryption operation where the relationship between cleartext and ci-
phertext is obscured. Some examples are:
(a) Shift cipher | main operation is substitution.
(b) German Enigma (broken by Turing) | main operation is smart substitution.
2. Di usion | encryption by spreading out the in uence of one cleartext letter over
many ciphertext letters. An example is:
(a) permutations | changing the positioning of the cleartext.
Remarks:
1. Today ! changing of one bit of cleartext should result on average in the change of
half the output bits.
x1 = 001010 ! encr. ! y1 = 101110.
x2 = 000010 ! encr. ! y2 = 001011.
2. Combining confusion with di usion is a common practice for obtaining a secure scheme.
Data Encryption Standard (DES) is a good example of that.

x y’ ............... Diff-N y_out

Diff-1 Conf-1 Diff-2 Conf-2 Conf-N

product
cipher

Figure 3.2: Example of combining confusion with di usion

27
Chapter 4
Data Encryption Standard (DES)
General Notes:
 DES is by far the most popular private-key algorithm.
 It was published in 1975 and standardized in 1977.
 Expired in 1998.

4.1 Encryption
System Parameters:
! block cipher.
! 64 input/output bits.
! 56 bits of key.
Principle: 16 rounds of encryption.

28
X Initial Encryption Encryption Final Y
Permutation 1 16 Permutation

K1 K16

Figure 4.1: General Model of DES

29
4.1.1 Overview

Message X Key K

64

Initial Permutation
IP(X)
56

64

L0 R0

32
32 48

f Transform 1
32 K1
56
round 1
32

32

L1 R1

L 15 R 15

32
48
32
f Transform 16
32 K 16
round 16
32

32

L 16 R 16

Final Permutation
-1
IP (R16 , L16 )

Cipher Y = DESK (X)

Figure 4.2: The Feistel Network

30
4.1.2 Permutations
a) Initial Permutation IP.
IP
58 50 42 34 26 18 10 2
60 52 44 36 28 20 12 4
62 54 46 38 30 22 14 6
64 56 48 40 32 24 16 8
57 49 41 33 25 17 9 1
59 51 43 35 27 19 11 3
61 53 45 37 29 21 13 5
63 55 47 39 31 23 15 7

1 50 58 64

IP(X)
1 2 40

Figure 4.3: Initial permutation

b) Inverse Initial Permutation IP ,1 ( nal permutation).

Note:
IP ,1 (IP (X )) = X .

4.1.3 Core Iteration / f-Function

General Description:
Li = Ri,1 .

31
 40

-1
IP (Z)
1

Figure 4.4: Final permutation

Ri = Li,1  f (Ri,1 ; ki).

The core iteration is the f-function that takes the right half
of the output of the previous round and the key as input.

E bit table
32 1 2 3 4 5
4 5 6 7 8 9
8 9 10 11 12 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 29 30 31 32 1

S-boxes:
Contain look-up tables (LUTs) with 64 numbers ranging from 0 : : : 15.
Input: Six bit code selecting one number.
Output: Four bit binary representation of one number out of 64.

32
 R i-1

32 Diffusion: Spreading influence

of single bits

Expansion
E(Ri-1 )

48

48

Ki

48

confusion: obscures
ciphertext/cleartext
6 6 relationship

f-function
S1 S8

4 4

L i-1 8 * 4 = 32
page 75 in Stinson

Permutation P

32

32
32

Ri

Figure 4.5: Core function of DES

33
Example:
S1
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
S-Box 1

Input: Six bit vector with MSB and LSB selecting the row and four inner bits
selecting column.
b = (100101).
! row = (11)2 = 3 (forth row).
! column = (0010)2 = 2 (third column).
S1 (37 = 1001012 ) = 8 = 10002.

Remark:
S-boxes are the most crucial elements of DES because they introduce a non-
linear function to the algorithm, i.e., S (a) XOR S (b) 6= S (a XOR b).

4.1.4 Key Schedule

Note: 64

7 1 7 1

P P

P = parity bits

Figure 4.6: 64 bit DES block

34
 In practice the DES key is arti cially enlarged with odd parity bits. These bits
are \stripped" in PC-1.

K
64

PC - 1
56

C0 D0

28 28

LS 1 LS 1

28 28

K1 PC - 2 C1 D1
48 56
28 28

LS 2 LS 2

LS 16 LS 16

K 16 PC - 2 C 16 D 16
48 56

Figure 4.7: DES key scheduler

The cyclic Left-Shift (LS) blocks have two modes of operation:

a) for LSi where i = 1; 2; 9; 16, the block is shifted once.
b) for LSi where i 6= 1; 2; 9; 16, the block is shifted twice.

35
Remark:
The total number of cyclic Left-Shifts is 4
1 + 12
2 = 28. As a results of this
C0 = C16 and D0 = D16 .

4.2 Decryption
One advantage of DES is that decryption is essentially the same as encryption. Only the
key schedule is reversed. This is due to the fact that DES is based on a Feistel network.

Question: Why does decryption work essentially the same as encryption?

a) Find what happens in the initial stage of decryption!
(Ld0 ; R0d) = IP (Y ) = IP (IP ,1(R16 ; L16 )) = (R16 ; L16 ).
(Ld0 ; R0d) = IP (Y ) = (R16 ; L16).
Ld0 = R16 .
R0d = L16 = R15 .
b) Find what happens in the iterations!
What are (Ld1 ; R1d) ?
Ld1 = R0d = L16 = R15 .
substitute into the above equation to get:
R1d = Ld0  f (R0d ; k16 ) = R16  f (L16 ; k16 ).
R1d = [L15  f (R15 ; k16 )]  f (R15 ; k16 ).
R1d = L15  [f (R15 ; k16 )  f (R15 ; k16 )] = L15 .
in general: Ldi = R16,i and Rid = L16,i ;
such that: Ld16 = R16,16 = R0 and R16 d
= R0 .
c) Find what happens in the nal stage!
IP ,1(R16 d
; Ld16 ) = IP ,1 (L0 ; R0 ) =: IP ,1 (IP (X )) = X q.e.d.

36
 Cipher Y = DES(X) Key K

64 64

Initial Permutation
IP PC-1
64
56
d d
L0 R0

32
32 48
f Transform 16
32 K 16

32

32

d d 56
L1 R1

d d
L 15 R 15

32
48
32
f Transform 1
32 K1

32

32

d d
L 16 R 16

Final Permutation
IP -1

-1 -1
X = DES (Y) = DES (DES(X))

Figure 4.8: Decryption of DES

37
Reversed Key Schedule:
Question: Given K , how can we easily generate k16?
k16 = P C 2(C16; D16 ) = P C 2(C0; D0 ) = P C 2(P C 1(k)).
k15 = P C 2(C15; D15 ) = P C 2(RS1(C16 ); RS1 (D16 )) = P C 2(RS1(C0 ); RS1 (D0 )).

4.3 Implementation
Note:
One design criteria for DES was fast hardware implementation.

4.3.1 Hardware
Since permutations and simple table look-ups are fast in hardware, DES can be implemented
very eciently [AM97, page 362].
Fastest Implementation:
) 9 Gbit/s as 0:6 m technology ASIC [WPR+ 99] with 16 stage pipeline.

4.3.2 Software
Record: 130 Mbits/s by Biham [Bih97].
Typically: a few 10 Mbit/s.

4.4 Attacks
There have been two major points of criticism about DES from the beginning:
i) key size is too small,
ii) the S-boxes contained secret design criteria.

38
 K
56

PC - 1
56

K 16 PC - 2 C0 = C 16 D0 = D 16
48 56
28 28

RS 1 RS 1

28 28

K 15 PC - 2 C 15 D 15
48 56
28 28

RS 2 RS 2

RS 15 RS 15

K1 PC - 2 C1 D1
48 56

Figure 4.9: Reversed key scheduler for decryption of DES

4.4.1 Exhaustive Key Search

Known Plaintext Attack:
known: X and Y .
unknown: K , such that Y = DESk (X ).

39
 idea: test all 256 possible keys ! DESk (X ) =? Y ; i = 0; 1; : : : ; 256 , 1.
i

4.4.2 Di erential Cryptanalysis

Proposed by Biham/Shamir in 1990.
Principle:
To consider di erences in plain and ciphertext pairs and deduce the likelihood
of certain keys.
16-round DES requirements:
With chosen plaintext, 247 (X,Y) pairs are needed.
With known plaintext, 255 (X,Y) pairs are needed.
237 arithmetic operations are needed.
Since each (X,Y) pair is 128 bits long, large storage is needed which makes this attack
highly impractical!

Remark: The DES S-boxes are optimized against di erential cryptanalysis.

4.4.3 Linear Cryptanalysis

Proposed by Matsui in 1993 and presented at CRYPTO'94.
Principal:
To consider di erences in plain and ciphertext pairs and deduce the likelihood
of certain key bits.
The actual attack was implemented:
! with 243 known plaintexts, the key was recovered in 50 days.
! using 12 HP RISC workstations running at 99MHz.

Remark: The S-box design of DES is not optimized for this attack.

40
 Date Proposed/implemented attack
1977 Die & Hellman, estimate cost of key search machine (underestimate)
1990 Biham & Shamir propose di erential cryptoanalysis (247 chosen ciphertexts)
1993 Mike Wiener proposes detailed hardware design for key search machine:
average search time of 36 h @ $100,000
1993 Matsui proposes linear cryptoanalysis (243 chosen ciphertexts)
Jun. 1997 DES Challenge I broken, distributed e ort took 4.5 months
Feb. 1998 DES Challenge II{1 broken, distributed e ort took 39 days
Jul. 1998 DES Challenge II{2 broken, key-search machine built by the
Electronic Frontier Foundation (EFF), 1800 ASICs, each with 24
search units, $250K, 15 days average (actual time 56 hours)
Jan. 1999 DES Challenge III broken, distributed e ort combined with EFF's
key-search machine, it took 22 hours and 15 minutes.
Table 4.1: History of full-round DES attacks

4.5 DES Alternatives

There exists a wealth of other block ciphers. A small collection of as of yet unbroken ciphers
is:
Algorithm Year Inventor X/Y bits Key Core Operation
AES 2000+ ? 128 128/192/256 ?
Triple DES 64 112 S-box
IDEA 90/92 Lai/Massey 64 128 modulo arithmetic
Cast 93 Adams/Tavares 64 64 variable S-boxes
Safer 94 Massey 64 64/128 modulo arithmetic

41
For further reading, consult Chapters 13 and 14 in [Sch93].

42
Chapter 5
Rijndael { The Advanced Encryption
Standard
5.1 History

5.1.1 Basic Facts about AES

 Successor to DES.
 The AES selection process was administered by NIST.
 Unlike DES, the AES selection was an open (i.e., public) process.
 Likely to be the dominant secret-key algorithm in the next decade.
 Main AES requirements by NIST:
{ Block cipher with 128 I/O bits
{ Three key lengths must be supported: 128=192=256 bits
{ Security relative to other submitted algorithms
{ Ecient software and hardware implementations
43
  See [Link] for further information on AES

5.1.2 Chronology of the AES Process

 Development announced on January 2, 1997 by the National Institute of Standards
and Technology (NIST).
 15 candidate algorithms accepted on August 20th, 1998.
 5 nalists announced on August 9th, 1999
{ Mars, IBM Corporation.
{ RC6, RSA Laboratories.
{ Rijndael, J. Daemen & V. Rijmen.
{ Serpent, Eli Biham et al.
{ Two sh, B. Schneier et al.
 Monday October 2nd, 2000, NIST chooses Rijndael as the AES.

A lot of work went into software and hardware performance analysis of the AES candidate
algorithms. Here are representative numbers:

44
 Algorithm Pentium-Pro @ 200 MHz FPGA Hardware
(Mbit/sec) [WWGP00] (Gbit/sec) [EYCP00]
MARS 69 {
RC6 105 2.4
Rijndael 71 1.9
Serpent 27 4.9
Two sh 95 1.6

Table 5.1: Speeds of the AES Finalists in Hardware and Software

45
5.2 Rijndael Overview

128 128
x y
Rijndael

k
128/192/256

Figure 5.1: AES Block and Key Sizes

 Both blocksize and keylength of Rijndael are variable. Sizes shown in Figure 5.2 are
the ones required by the AES Standard. The number of rounds (or iterations) is a
function of the key length:
Key lengths (bits) nr = # rounds
128 10
192 12
256 14

Table 5.2: Key lenghts and number of rounds for Rijndael

 However, Rijndael also allows blocksizes of 192 and 256 bits. For those blocksizes the
number of rounds must be increased.

Important: Rijndael does not have a Feistel structure. Feistel networks do not encrypt
an entire block per iteration (e.g., in DES, 64=2 = 32 bits are encrypted in one iteration).
Rijndael encrypts all 128 bits in one iteration. As a consequence, Rijndael has a comparably
small number of rounds.
46
Rijndael uses three di erent types of layers. Each layer operates on all 128 bits of a block:
1. Key Addition Layer: XORing of subkey.
2. Byte Substitution Layer: 8-by-8 SBox substitution.
3. Di usion Layer: provides difussion over all 128 (or 192 or 256) block bits. It is split
in two sub-layers:
(a) ShiftRow Layer.
(b) MixColumn Layer.
Remark: The ByteSubstitution Layer introduces confusion with a non-linear operation.
The ShiftRow and MixColumn stages form a linear Di usion Layer.

5.3 Some Mathematics: A Very Brief Introduction to

Galois Fields
\Galois elds" are used to perform substitution and di usion in Rijndael.

Question: What are Galois elds?

Galois elds are elds with a nite number of elements. Roughly speaking, a eld is a
structure in which we ca add, subtract, multiply, and compute inverses. More exactly a eld
is a ring in which all elements except 0 are invertible.

Fact 5.3.1 Let p be a prime. GF (p) is a \prime eld," i.e., a Galois eld with a
prime number of elements. All arithmetic in GF (p) is done modulo p.

Example: GF (3) = f0; 1; 2g

47
 x

Key Addition Layer

ByteSubstitution Layer

ShiftRow SubLayer
rounds 1 ... n r - 1 Diffusion Layer
MixColumn Sublayer

Key Addition Layer

ByteSubstitution Layer

ShiftRow SubLayer round n r

Key Addition Layer

Figure 5.2: Rijndael encryption block diagram

addition additive inverse
+ 0 1 2
0 0 1 2 ,0 = 0
1 1 2 0 ,1 = 2
2 2 0 1 ,2 = 1

48
 multiplication multiplicative inverse
 0 1 2
0 0 0 0 0,1 does not exist
1 0 1 2 1,1 = 1
2 0 2 1 2,1 = 2, since 2
2  1 mod 3

Theorem 5.3.1 For every power pm, p a prime and m a positive integer, there exists
a nite eld with pm elements, denoted by GF (pm ).

Examples:
- GF (5) is a nite eld.
- GF (256) = GF (28) is a nite eld.
- GF (12) = GF (3
22) is NOT a nite eld (in fact, the notation is already incorrect
and you should pretend you never saw it).
Question: How to build \extension elds" GF (pm), m > 1 ?

Note: See also [Sti95, Section 5.2.1]

1. Represent elements as polynomials with m coecients. Each coecient is an element
of GF (p).
Example: A 2 GF (28)
A ! A(x) = a7x7 +


+ a1x + a0 ; ai 2 GF (2) = f0; 1g
2. Addition and subtraction in GF (pm )
C (x) = A(x) + B (x) = Pii==0m,1 ci xi; ci = ai + bi mod p
Example: A; B 2 GF (28)
49
 A(x) = x7+ x6 + x4 + 1
B (x) = x4 + x2 + 1
C (x) = x7+ x6 + x2
3. Multiplication in GF (pm ): multiply the two polynomials using polynomial multipli-
cation rule, with coecient arithmetic done in GF (p). The resulting polynomial will
have degree 2m , 2.
A(x)
B (x) = (am,1 xm,1 +


+ a0 )
(bm,1 xm,1 +


+ b0 )
C 0 (x) = c02m,2 x2m,2 +


+ c00
where:
c00 = a0b0 mod p
c01 = a0b1 + a1 b0 mod p
...
c02m,2 = am,1 bm,1 mod p
Question: How to reduce C 0 (x) to a polynomial of maximum degree m , 1?
Answer: Use modular reduction, similar to multiplication in GF (p). For arithmetic
in GF (pm) we need an irreducible polynomial of degree m with coecients from GF (p).
Irreducible polynomials do not factor (except trivial factor involving 1) into smaller
polynomials from GF (p).
Example 1: P (x) = x4 + x +1 is irreducible over GF (2) and can be used to construct
GF (24).
C = A
B ) C (x) = A(x)
B (x) mod P (x)
A(x) = x3 + x2 + 1
B (x) = x2 + x
C 0 (x) = A(x)
B (x) = (x5 + x4 + x2 ) + (x4 + x3 + x) = x5 + x3 + x2 + 1
50
 x4 = 1
P (x) + (x + 1)
x4  x + 1 mod P (x)
x5  x2 + x mod P (x)
C (x)  C 0 (x) mod P (x)
C (x)  (x2 + x) + (x3 + x2 + 1) = x3
A(x)
B (x)  x3
Note: in a typical computer representation, the multiplication would assign the follow-
ing unusually looking operations:

A
B = C
(1 1 0 1)
(0 1 1 0) = (1 0 0 0)
Example 2: x4 + x3 + x + 1 is reducible since x4 + x3 + x + 1 = (x2 + x + 1)(x2 + 1).
4. Inversion in GF (pm ): the inverse A,1 of A 2 GF (pm) is de ned as:
A,1(x)
A(x) = 1 mod P (x)
) perform the Extended Euclidean Algorithm with A(x) and P (x) as inputs
s(x)P (x) + t(x)A(x) = gcd(P (x); A(x)) = 1
) t(x)A(x) = 1 mod P (x)
) t(x) = A,1 (x)
Example: Inverse of x2 2 GF (23), with P (x) = x3 + x + 1
t0 = 0, t1 = 1
x3 + x + 1 = [x]x2 + [x + 1] t2 = t0 , q1t1 = ,q1 = ,x = x
x + 1 = [1]x + 1 t3 = t1 , q2t2 = 1 , q2x = 1 , x = x + 1
x = [x]1 + 0
) (x2 ),1 = t(x) = t3 = x + 1
51
 Check: (x + 1)x2 = x3 + x = (x + 1) + x  1 mod P (x) since x3  x + 1 mod P (x).
Remark: In every iteration of the Euclidean algorithm, you should use long division (not
shown above) to uniquely determine qi and ri.

5.4 Internal Structure

In the following, we assume a block length of 128 bits. The ShiftRow Sublayer works slightly
di erently for other block sizes.

5.4.1 Byte Substitution Layer

 Splits the incoming 128 bits in 128=8 = 16 bytes.
 Each byte A is considered an element of GF (28) and undergoes the following substi-
tution individually
1. B = A,1 2 GF (28) where P (x) = x8 + x4 + x3 + x + 1
2. Apply ane transformation de ned by:
0 1 0 10 1 0 1
BB c0 CC BB 1 1 1 1 1 0 0 0 C B b0 C B 0 C
CC BB CC BB CC
BB c CC BB 0 0C
BB 1 CC BB 1 1 1 1 1 0 CC BBB b1 CCC BBB 1 CCC
BB c2 CC BB 0 0 1 1 1 1 1 0C CC BBB b2 CCC BBB 1 CCC
BB CC BB C BB b CC BB 0 CC
BB c3 CC BB 0 0 0 1 1 1 1 1C CC BB 3 CC + BB CC
BB CC = BB
BB c4 CC BB 1 0 0 0 1 1 1 1C CC BBB b4 CCC BBB 0 CCC
BB CC BB C BB CC BB CC
BB c5 CC BB 1 1 0 0 0 1 1 1C CC BB b5 CC BB 0 CC
BB c CC BB 1 1 1 0 0 0 1 1C CC BBB b6 CCC BBB 1 CCC
B@ 6 CA B@ A@ A @ A
c7 1 1 1 1 0 0 0 1 b7 1
where (b7


b0 ) is the vector representation of B (x) = A,1 (x).

52
  The vector C = (c7


c0) (representing the eld element c7 x7 +


+ c1 x + c0) is the
result of the substitution:
C = ByteSub(A)
The entire substitution can be realized as a look-up in a 2568-bit table with xed
entries.

Remark: Unlike DES, Rijndael applies the same S-Box to each byte.

5.4.2 Di usion Layer

 Unlike the non-linear substitution layer, the di usion layer performs a linear operation
on input words A; B . That means:

DIFF(A)  DIFF(B ) = DIFF(A + B )

 The di usion layer consists of two sublayers.

ShiftRow SubLayer
1. Write an input word A as 128=8 = 16 bytes and order them in a square array:
Input A = (a0 ; a1;


; a15 )

a0 a4 a8 a12
a1 a5 a9 a13
a2 a6 a10 a14
a3 a7 a11 a15

53
 2. Shift cyclically row-wise as follows:
a0 a4 a8 a12 0 positions
a5 a9 a13 a1 , , , ,! 3 positions right shift
a10 a14 a2 a6 ,, ,! 2 positions right shift
a15 a3 a7 a11 , ,! 1 position right shift
MixColumn SubLayer
Principle: each column of 4 bytes is individually transformed into another column.

Question: How?
Each 4-byte column is considered as a vector and multiplied by a 4  4 matrix. The matirx
contains constant entries. Multiplication and addition of the coecients is done in GF (28).
0 1 0 10 1
BB c0 CC BB 02 03 01 01 C B b0 C
C BB CC
BB c1 CC BB 01 02 03 01 C
CC BB b1 CC
BB CC = BB C BB CC
BB c2 CC BB 01 01 02 03 CCA B@ b2 CA
@ A @
c3 03 01 01 02 b3
Remarks:
1. Each ci ; bi is an 8-bit value representing an element from GF (28).
2. The small values f01; 02; 03g allow for a very ecient implementation of the coecient
multiplication in the matrix. In software implementations, multiplication by 02 and
03 can be done through table look-up in a 256-by-8 table.
3. Additions in the vector-matrix multiplication are XORs.

5.4.3 Key Addition Layer

Simple bitwise XOR with a 128-bit subkey.
54
5.5 Decryption
Unlike DES and other Feistel ciphers, all of Rijndael layers must actually be inverted.
y

Key Addition Layer

Inv ShiftRow SubLayer inverse of round n r

Inv ByteSubstitution Layer

Key Addition Layer

Inv MixColumn Sublayer inverse of rounds n r -1, ..., 1

Inv ShiftRow SubLayer

Inv ByteSubstitution Layer

Key Addition Layer

Figure 5.3: Rijndael decryption block diagram

55
Chapter 6

More about Block Ciphers

Further Reading:
Section 8.1 in [Sch93].
Note:
The following modes are applicable to all block ciphers e (X ).
k

6.1 Modes of Operation

6.1.1 Electronic Codebook Mode (ECB)

X0 X1 X2 e Y0 Y1 Y2 e-1 X0 X1 X2

K K

Figure 6.1: ECB model

General Description:
e
,1 (Y ) = e,1 (e (X )) = X ; where the encryption can, for instance, be DES.
k i k k i i

56
Problem:
This mode is susceptible to substitution attack because same X are mapped to same Y . i i

Example: Bank transfer.

Block # 1 2 3 4 5
Sending Sending Receiving Receiving Amount
Bank A Account # Bank B Account # $

Figure 6.2: ECB example

1. Tap encrypted line to bank B.

2. Send $1 00 transfer to own account at bank B repeatedly ! block 4 can be identi ed
:

and recorded.
3. Replace in all messages to bank B block 4.
4. Withdraw money and y to Paraguay.

Note: This attack is possible only for single-block transmission.

6.1.2 Cipher Block Chaining Mode (CBC)

Beginning: Y0 = ( ek X0  ). IV

X0 = IV  ek
,1 (Y )= IV  ,1 (e
ek (
X0  )) = .
IV X0
0 k

Encryption: = (  , ).Yi ek Xi Yi 1

Decryption: = , ( )  , .
Xi ek
1
Yi Yi 1

Question: How does it work?

Xi= , ( (  , )) 
ek
1
ek Xi Yi 1 Yi ,1 .
Xi=(  , ) , .
Xi Yi 1 Yi 1

57
 i=0 i=0
IV IV

Y i-1 Y i-1

Y i-1 Y i-1

Xi e e-1 Xi
Yi

k k

Figure 6.3: CBC model

Xi = Xi . q.e.d.

Remark: The Initial Vector (IV) can be transmitted initially in cleartext.

6.1.3 Cipher Feedback Mode (CFB)

Assumption: block cipher with bits block width and message with block width , 1 
b l

l .b

SR l SR l
b b

~
zi ~
zi
l l
e e

b b

k b:l Y i-1 Y i-1 b:l k

zi zi l
l l l l
Xi Xi
Yi

Figure 6.4: CFB model

58
Procedure:
1. Load shift register with initial value IV.
2. Encrypt ( ) = ~ .
ek I V z0

3. Take leftmost bits: ~ ! .

l z0 z0

4. Encrypt data: Y0 = X0  .
z0

5. Shift the shift register and load Y0 into the rightmost SR position.
6. Go back to (2) substituting ( ) with ( e IV e SR ).

6.1.4 Counter Mode

Notes:
 Another mode which uses a block cipher as a pseudo-random generator.
 Counter Mode does not rely on previous ciphertext for encrypting the next block.
) well suited for parallel (hardware) implementation, with several encryption blocks
working in parallel.
 Counter Mode stems from the Security Group of the ATM Forum, where high data
rates required parallelization of the encryption process.
Description of Counter Mode:
1. An -bit initial vector (IV) is loaded into a (maximum length) LFSR. The IV can be
n

publically known, although a secret IV (i.e., the IV is considered part of the private
key) turns the counter mode systems into a non-deterministic cipher which makes
cryptoanalysis harder.
2. Encrypt block cipher input.
59
 LFSR

k e

n n
X Y

Figure 6.5: Counter Mode model

3. The block cipher output is considered a pseudorandom mask which is XORed with the
plaintext.
4. The LFSR is clocked once (note: all input bits of the block cipher are shifted by one
position).
5. Goto to Step 2.
Note that the period of a counter mode is
2 which is very large for modern block
n
n

ciphers, e.g., 128
2 = 2 for AES algorithms.

128 135

6.2 Key Whitening

Xi e Yi

k2 k1 k3

Figure 6.6: Whitening example

60
Encryption: = Y ( ) = 1(  )  .
ek1 ;k2 ;k3 X ek X k2 k3

Decryption: = X
, (  ) .
ek
1
1
Y k3 k2

popular example: DESX

6.3 Multiple Encryption

6.3.1 Double Encryption

Note: The keyspace of this encryption is j j = 2
2 = 2 . k

k k 2k

However, using the meet-in-the-middle attack, the key search is reduced signi cantly.

-1
e (X) = z (1)
i e (Y) = z (2)
j
ki kj

X e e Y
n z
k

ki kj

Figure 6.7: Double encryption and meet-in-the-middle attack

Meet in the middle attack:

Input ! some pairs ( 0 0), ( 00 00), .
x ;y x ;y :::

Idea ! compute = ( 0 ) and = , ( 0).

(1)
zi eki x
(2)
zj ek
1
j
y

Problem ! to nd a matching pair such that = (1)

zi
(2)
zj .

Procedure:
1. Compute a look-up table for all ( ), = 1 2 2 and store it in memory.
(1)
zi ; ki i ; ;:::;
k

Number of entries in the table is 2 with each entry being bits wide.
k
n

61
2. Find matching (2)
zj .
(a) compute , ( 0) = ek
1
j
y
(2)
zj

(b) if is in the look-up table, i.e., if

(2)
zj
(1)
zi = (2)
zj , check a few other pairs ( 00 00) ( 000 000)
x ;y ; x ;y ;:::

for the current keys and ki kj

(c) if and give matching encryptions stop; otherwise go back to (a) and try
ki kj

di erent key . kj

Question: How many additional pairs ( 00 00); (x000 ; y 000); : : : should we

x ;y test?

General system: subsequent encryptions and pairs ( 0 0) ( 00 00)

l t x ;y ; x ;y .
;:::

1. In the rst step there are 2 possible key combinations for the mapping ( 0) =
lk
E x

e (


( ( ( 0 ))


) = 0 but only 2 possible values for 0 and 0. Hence, there are

e e x y
n
x y

2 lk

2 n

mappings ( 0 ) = 0. Note that only one mapping is done by the correct key!
E x y

2n

X’ Y’

2lk mappings E(x’) = y’

2n

Figure 6.8: Number of mappings 0 to 0 under -fold encryption

x y l

62
 2. We use now a candidate key from step 1 and check whether ( 00) = 00. There are 2 E x y
n

possible outcomes for the mapping ( 00 ). If a random key is used, the likelyhood
y E x

that ( 00 ) = 00 is
E x y

1
2 n

If we check additionally a third pair ( 000 000) under the same \random" key from step
x ;y

1, the likelyhood that ( 00 ) = 00 and ( 000 ) = 000 is

E x y E x y

1
2 2n

If we check , 1 additional pairs ( 00 00) ( 000 000) (

t x ;y ) the likelyhood that a
; x ;y ;::: x
(t)
;y
(t)

random key ful lls ( 00 ) = 00, ( 000 ) = 000 is

E x y E x y ;:::

1
2 , (t 1)n

2n

X’’ Y’’

2n mappings E(x’’) = y

Figure 6.9: Number of mappings 00 to x y

3. Since there are candidate keys in step 1, the likelyhood that at least one of the
2lk
2n

candidate keys ful lls all ( 00 ) = 00, ( 000 ) = 000 is

E x y E x y ;:::

1 2 =2 , lk
lk tn

2, 2 (t 1)n n

Example: Double encryption with DES. We use two pairs ( 0 0) ( 00 00). The likelyhood x ;y ; x ;y

that an incorrect key pair is picked is

ki ; kj

2 , =2 ,
lk tn 112 128
= 2, 16

63
 If we use three pairs ( 0 0) ( 00 00) ( 000 000), the likelyhood that an incorrect key pair
x ;y ; x ;y ; x ;y

ki ; kj is picked is
2 , = 2112,192 = 2,80
lk tn

Computational complexity:
Brute force attack: 22 .
k

Meet in the middle attack: 2 encryptions + 2 decryptions = 2 +1 computations

k k k

and 2 memory locations.

k

64
6.3.2 Triple Encryption

Option 1:
Y = ( ,12 ( 1 ( ))); if 1 = 2 ! =
ek1 ek ek X k k Y ek1 X( ).
Option 2:
Y = ( ( ( ))); where j j  22
ek3 ek2 ek1 X k
k

Option 2 should be preferred.

X e e e Y
z
1

k1 k2 k3

Figure 6.10: Triple encryption example

Note:
Meet in the middle attack can be used in a similar way by storing results in
zi

memory. The computational complexity of this approach is 2
2 = 22 .

k k k

65
Chapter 7

Introduction to Public-Key

Cryptography

7.1 Principle
Quick review of private-key cryptography

e Y dk
X k X

k k

Figure 7.1: Private-key model

Two properties of private-key schemes:

1. The algorithm requires same secret key for encryption and decryption.
2. Encryption and decryption are essentially identical (symmetric algorithms).

66
Analogy for private key algorithms
Private key schemes are analogous to a safe box with a strong lock. Everyone
with the key can deposit messages in it and retrieve messages.
Main problems with private key schemes are:
1. Requires secure transmission of secret key.
2. In a network environment, each pair of users has to have a di erent key resulting in
too many keys (
( , 1)  2 key pairs).
n n

New Idea:
Make a slot in the safe box so that everyone can deposit a message, but only the
receiver can open the safe and look at the content of it. This idea was proposed
in [WD76] in 1976 by Die/Hellman.
Idea: Split key.
K

public part private part

(encryption) (decryption)

Figure 7.2: Split key idea

Protocol:
1. Alice and Bob agree on a public-key cryptosystem.
2. Bob sends Alice his public key.
3. Alice encrypts her message with Bob's public key and sends the ciphertext.
4. Bob decrypts ciphertext using his private key.

67
 Alice Oscar Bob

K pub
X ( K pub , K pr ) = K
2.)

Y
3.) Y = eK (X) Y
pub

X = dK (Y)
4.) pr

Figure 7.3: Public-key encryption protocol

7.2 One-Way Functions

All public-key algorithms are based on one-way functions.

De nition 7.2.1 A function f is a \one-way function"

if:
(a) y = f (x) ! is easy to compute,
(b) x = f ,1 (y) ! is very hard to compute.

Example: Discrete Logarithm (DL) one-way Function

2 mod 127  31
x

x =?

De nition 7.2.2 A trapdoor one function is a one-way

function whose inverse is easy to compute given a side
information such as the private key.

7.3 Overview of Public-Key Algorithms

There are three families of Public-Key (PK) algorithms of practical relevance:
1. Integer factorization algorithms (RSA, ...)
68
 2. Discrete logarithms (D{H, DSA, ...)
3. Elliptic curves (EC)

) Generally speaking, public-key algorithms are much slower than private-key algorithms.
) Public-Key algorithms are mainly used for key establishment and digital signatures and
not for bulk data encryption.

Algorithm Family Bit length of the operands

Integer Factorization (RSA) 1024
Discrete Logarithm (D{H, DSA) 1024
Elliptic curves 160
Block cipher 80
Table 7.1: Bit lengths for security level of approximately 280 computations for successful
attack.

7.4 Important Public-Key Standards

a) IEEE P1363. Comprehensive standard of public-key algorithms. Collection of IF, DL,
and EC algorithm families, including in particular:
{ Key establishment algorithms
{ Key transport algorithms
{ Signature algorithms
Note: IEEE P1363 does not recommend any bit lengths or security levels.

69
b) ANSI Banking Security standards.
ANSI# Subject
X9.30{1 digital signature algorithm (DSA)
X9.30{2 hashing algorithm for RSA
X9.31{1 RSA signature algorithm
X9.32{2 hashing algorithms for RSA
X9.42 key management using Di e-Hellman
X9.62 (draft) elliptic curve digital signature algorithm (ECDSA)
X9.63 (draft) elliptic curve key agreement and transport protocols

c) U.S. Government standards (FIPS)

FIPS# Subject
FIPS 180-1 secure hash standard (SHA-1)
FIPS 186 digital signature standard (DSA)
FIPS JJJ (draft) entity authentication (asymetric)

70
7.5 More Number Theory
7.5.1 Euclid's Algorithm
Basic Form
Given r0 and r1 with one larger than the other, compute the gcd(r0; r1).
Example 1:
r0 = 22; r1 = 6.
gcd(r0; r1) =?

11111
00000
r0 6 6 6 00000
11111
4
11111
00000
gcd(22,6) = gcd(6,4)
11111
00000
11
00
00
11
2 gcd(6,4) = gcd(4,2)
4
r1 00
11
00
11
00
11
00
11
2 00
11
2 gcd(4,2) = 2
r2 00
11
00
11
r3 2

gcd(22, 6) = gcd(6, 4) = gcd(4, 2) = gcd(2, 0) = 2

Figure 7.4: Euclid's algorithm example

Example 2:
r0 = 973; r1 = 301.
973 = 3
301 + 70.
301 = 4
70 + 21.
70 = 3
21 + 7.
21 = 3
7 + 0.
gcd(973; 301) = gcd(301; 70) = gcd(70; 21) = gcd(21; 7) = 7.

71
Algorithm:
input: r0 , r1
r0 = q1
r1 + r2 gcd(r0 ; r1) = gcd(r1 ; r2)
r1 = q2
r2 + r3 gcd(r1 ; r2) = gcd(r2 ; r3)
... ...
rm,2 = qm,1
rm,1 + rm gcd(rm,2 ; rm,1) = gcd(rm,1 ; rm)
rm,1 = qm
rm + 0 y gcd(r0 ; r1) = gcd(rm,1 ; rm) = rm
y - termination criteria

72
Extended Euclidean Algorithm
Theorem 7.5.1 Given two integers r0 and r1, there exist two other integers s and t
such that s
r0 + t
r1 = gcd(r0 ; r1).

Question: How to nd s and t?

Use Euclid's algorithm and express the current remainder ri in every iteration in the form
ri = sir0 + tir1 . Note that in the last iteration rm = gcd(r0; r1) =! sm r0 + tm r1 = sr0 + tr1 .
index Euclid's Algorithm rj = sj
r0 + tj
r1
2 r0 = q1
r1 + r2 r2 = r0 , q1
r1 = s2
r0 + t2
r1
3 r1 = q2
r2 + r3 r3 = r1 , q2
r2 = r1 , q2 (r0 , q1
r1)
= [,q2 ]r0 + [1 + q1
q2 ]r1 = s3
r0 + t3
r1
.. .. ..
. . .
i ri,2 = qi,1
ri,1 + ri ri = si
r0 + ti
r1
i + 1 ri,1 = qi
ri + ri+1 ri+1 = si+1
r0 + ti+1
r1
i + 2 ri = qi+1
ri+1 + ri+2 ri+2 = ri , qi+1
ri+1
= (si
r0 + t1
r1 ) , qi+1 (si+1
r0 + ti+1
r1 )
= [si , qi+1 ]
si+1 ]r0 + [t1 , qi+1
ti+1 ]r1
= si+2
r0 + ti+2
r1
.. .. ..
. . .
m rm,2 = qm,1
rm,1 + rm rm = gcd(r0 ; r1 ) = sm
r0 + tm
r1

Now: s = sm , t = tm
Recursive formulae:

s0 = 1, t0 = 0
s1 = 0, t1 = 1
si = si,2 , qi,1
si,1, ti = ti,2 , qi,1
ti,1 ; i = 2; 3; 4 : : :

73
Remark:
a) Extended Euclidean algorithm is commonly used to compute the inverse element in
Zm. If gcd(r0 ; r1) = 1, then t = r1,1 mod r0.
b) For fast software implementation, the \binary extended Euclidean algorithm" is more
ecient [AM97] because it avoids the division required in each iteration of the extended
Euclidean algorithm shown above.

7.5.2 Euler's Phi Function

De nition 7.5.1 The number of integers in Zm rela-
tively prime to m is denoted by (m).

Example 1:
m = 6; Z6 = f0; 1; 2; 3; 4; 5g
gcd(0; 6) = 6
gcd(1; 6) = 1
gcd(2; 6) = 2
gcd(3; 6) = 3
gcd(4; 6) = 2
gcd(5; 6) = 1
(6) = 2

74
Example 2:
m = 5; Z5 = f0; 1; 2; 3; 4g
gcd(0; 5) = 5
gcd(1; 5) = 1
gcd(2; 5) = 1
gcd(3; 5) = 1
gcd(4; 5) = 1
(5) = 4

Theorem 7.5.2 If m = pe1
pe2
: : :
pen , where pi are

1 2 n

prime numbers and ei are integers, then:

Y
n
(m) = (pei , pei , )
i i 1

i=1
.
Example:
m = 40 = 8
5 = 23
5 = pe11
pe22
(m) = (23 , 22)(51 , 50) = (8 , 4)(5 , 1) = 4
4 = 16

Theorem 7.5.3 Euler's Theorem

If gcd(a; m) = 1, then:

a(m)  1 mod m
.
Example:
m = 6; a = 5
(6) = (3
2) = (3 , 1)(2 , 1) = 2
5(6) = 52 = 25  1 mod 6

75
76
Chapter 8
RSA
1. Most popular public-key cryptosystem.
2. Invented by Rivest/Shamir/Adleman in 1977 at MIT.
3. Patented until 2000.

77
8.1 Cryptosystem
Set-up Stage
1. Choose two large primes and . p q

2. Compute =
. n p q

3. Compute ( ) = ( , 1)( , 1).

n p q

4. Choose random ; 0 ( ), with gcd( ( )) = 1.

b < b < n b; n

Note that has inverse in ( ) .

b Z n

5. Compute inverse = ,1 mod ( ): a b n

b
 1 mod ( )
a n :

6. Public key: kpub =( n; b ).

Private key: kpr =( p; q; a ).

Encryption: done using public key, kpub .

y = ( ) = mod .
ekpub x x
b
n

x 2 Zn = f0 1
; , 1g.
;:::;n

Decryption: done using private key, kpr .

x = ( )=
dkpr y y
a
mod . n

Example:
Alice sends encrypted message ( = 4) to Bob after Bob x

sends her the public key.

78
Alice Bob
(1) choose = 3; = 11p q

(2) =
= 33
n p q

(3) ( ) = (3 , 1)(11 , 1) = 2
10 = 20
n

(4) choose = 3; gcd(20 3) = 1

b ;

(3 33)
x =4 kpub
, ;
(5) = ,1 = 7 mod 20
a b

=31
y = mod
x
b
n = 43 = 64  31 mod 33 ,!
y
x = = 317  4 mod 33
y
a

Why does RSA work?

We have to show that: pr ( ) = pr ( pub ( )) = . dk y dk ek x x

pr = = = mod . a ba ab
dk y x x n

a
 1 mod ( ) ()
 1 +
( ); is an integer.
b n a b t n t

dk pr = =
( )
1 = ( ( ) )
mod .
x
ab
x
t n
x x
n t
x n

if ( )  1 mod then pr = ( ( ) )
= 1
= 1
= mod .

x
n
n dk x
n t
x
t
x x x n

1. Case: gcd( ) = gcd(
) = 1 x; n x; p q

Euler's Theorem: ( )  1 mod , q.e.d. x

n
n

2. Case: gcd( ) = gcd(
) 6= 1 x; n x; p q

either =
or =
; are integers such that;

x r p x , . s q r; s r < q s < p

assume =
) gcd( ) = 1 x r p x; q

( ) = ( ,1)( ,1) = ( )( ,1) = ( ( ) ) ,1 = 1 mod

x
n
x
q p
x
q p
x
q p
q

( ) = 1 +
; where is an integer
x
n
c q c

( ) = +

= +


= +


= +


x x
n
x x c q x r p c q x r c p q x r c n

( )  mod
x x
n
x n

79
 x
( )n
 1 mod , q.e.d.
n

8.2 Computational Aspects

8.2.1 Choosing p and q

Problem: Finding two large primes , (each p q > 250 bits).

Principle:
Pick a large integer and apply primality test. In practice, a \Monte Carlo" test
developed by Miller-Rabbin (pg. 136 in [Sti95]) is used. Note that a primality
test does NOT require factorization.
Miller-Rabin Algorithm:
Input: or and arbitrary number
p q . r < p; q

Output 1: Statement \ is composite" ! always true.

p; q

Output 2: Statement \ is prime" ! true with probability 0 75.

p; q > :

In practice, the above algorithm is run 3 times (for a 1000 bit prime) and upto 12 times (for
a 150 bit prime) [AM97, Table 4.4 page 148] with di erent parameters . If the answer is r

always \ is prime", then is with very high probability a prime.

p p

P ( is composite )  0 25 where = number of tries.

p :
t
t

Question: What is the likelihood that a randomly picked integer or is prime? p q

Answer: P ( is prime )  1( ) .
p
ln p

Example:  2250 ! (250 bits).

p

P ( is prime ) = ln(21 )  1731 .

p 250

80
8.2.2 Choosing a and b

kpub= ; condition: gcd( ( )) = 1; where ( ) = ( , 1)
( , 1).

b b; n n p q

kpr= ; where = ,1 mod ( ).

a a b n

Pick arbitrary (large!) and compute:

b

1. Euclidean Algorithm:
( ) +
= gcd( ( )) s n t b b; n

2. Test if gcd( ( )) = 1 b; n

3. Calculate : a

Question: What is
mod ( )? t b n

= (, )( ) + 1
t b s n

)
 1 mod ( )
t b n

) = ,1 = mod ( )
t b a n

Remark:
It is not necessary to nd for the computation of . s a

8.2.3 Encryption/Decryption

encryption: ekpub x ( ) = mod = . x

b
n y

decryption: dk pr ( ) =
y mod = . y
a
n x

Question: How many multiplications are required for computing 8 ? x

Answer: |
{z= 2}; | 2
{z2 = 4}; | 4
{z4 = 8}.

x x x x x x x x x

1 2 3
if 0 ( ) then O(( ))  O( ).
< b < n n n

Question: How many multiplications are required for computing 13 ? x

Answer: |
{z= 2}; | 2
{z= 3}; | 3
{z3 = 6}; | 6
6{z= 12}; | 12
{z= 13}.
x x x x x x x x x x x x x x x

SQ MUL SQ SQ MUL

81
Square-and-multiply algorithm
First: binary representation of the exponent ! ;  15 x
B
B

B = 3
23 + 2
22 + 1
21 + 0
b b b b

B = ( 3
2 + 2 )22 + 1
2 + 0 = (( 3
2 + 2 )2 + 1 )2 +
b b b b b b b b0
x = (( 3
2+ 2)2+ 1 )2+ 0
B
x
b b b b

Step x
B

#1 x
b3
2
#2 (x
b3
2
x 2 )b

#3 (x 3
b
2
x 2 )2
b

#4 (x 3
b
2
x 2 )2
x 1
b b

#5 (( x
b3
2
x 2 )2
x 1 )2
b b

#6 (( x
b3
2
x 2 )2
x 1 )2
x 0
b b b

Example: x
13 = x
11012 = x
(3
b ;b2 ;b1 ;b0 )2

#1 3
2 = 2
x
b
x SQ
#2 2
3 = 2
= 3
x x
b
x x x MUL
#3 ( 3 )2 = 6
x x SQ
#4 6
0 6
1 = 6
x x x x

#5 ( 6 )2 = 12
x x SQ
#6 12
0 = 12
= 13
x x
b
x x x MUL
Complexity: [log2 ]
SQ + [ 12 log2 ]
MUL.
n n

Comparison: = 21000B

Straight forward exponentiation: 21000  10300 multiplications

! computationally impossible.
Square-and-multiply: 1 5
log2 (21000 ) = 1500 multiplications and squarings
:

! relatively easy.

82
Remark: Remember to apply modulo reduction after every multiplication and squaring
operation.
Algorithm [Sti95]: computes , where = P ,=01 2 B
x B
l
i
bi
i

1. =z x

2. for = , 1 downto 0 do:

i l

(a) = z z
2 mod n

(b) if ( = 1) then =
mod

bi z z x n

8.3 Attacks
8.3.1 Brute Force

Given = mod , try all possible keys ; 0 

y x
b
n a a < ( ) to obtain =
n x y
a
mod . In
n

practice jKj = ( )  2500 ) impossible.

n n >

8.3.2 Finding (n)

Given = mod , nd ( ) and compute = ,1 mod ( ).
n; b; y x
b
n n a b n

) computing ( ) is believed to be as dicult as factoring .

n n

8.3.3 Finding a directly

Given = mod , nd directly and compute = mod .

n; b; y x
b
n a x y
a
n

) computing directly is believed to be as dicult as factoring .

a n

83
8.3.4 Factorization of n

Given = mod , nd
= and compute:

n; b; y
b
x n p q n

( ) = ( , 1)( , 1)
n p q

b= ,1 mod ( )
a n

x = mod y
a
n

! This approach is the only attack believed to be practical.

Factoring Algorithms:
1. Quadratic Sieve (QS): speed depends on the size of ; record: in 1994 factoring of
n

=RSA129, log10 = 129 digits, log2 = 426 bits.

n n n

2. Elliptic Curve: similar to QS; speed depends on the size of the smallest prime factor
of , i.e., on and .
n p q

3. Number Field Sieve: asymptotically better than QS; record: in 1996 factoring of
=RSA140; log10 = 140 digits; log2 = 466 bits.
n n n

Algorithm Complexity
pln( ) ln(ln( ))
Quadratic Sieve O(e (1+ (1))
p
o n
) n

Elliptic Curve O(e(1+ (1)) 2 ln( ) ln(ln( )) )

o p p

Number Field Sieve O(e(1 92+ (1))(ln( ))1=3 (ln(ln(

: o n n)))2=3 )

84
number month MIPS-years algorithm
RSA-100 April 1991 7 quadratic sieve
RSA-110 April 1992 75 quadratic sieve
RSA-120 June 1993 830 quadratic sieve
RSA-129 April 1994 5000 quadratic sieve
RSA-130 April 1996 500 generalized number eld sieve
RSA-140 February 1999 1500 generalized number eld sieve
RSA-155 August 1999 8000 generalized number eld sieve

85
8.4 Implementation
 Hardware: 1024 bit decryption in less that 5 ms.
 Software: 1024 bit decryption in 43 ms; 1024 bit encryption in 0.65 ms
 hybrid systems, consisting of public-key and private-key algorithms: most commonly
used in practice
1. key exchange and authentication with (slow) public-key algorithm
2. bulk data encryption with (fast) block ciphers

86
Chapter 9
The Discrete Logarithm (DL)
Problem
 DL is the underlying one-way function for:
1. Die-Hellman key exchange.
2. DSA (digital signature algorithm).
3. ElGamal encryption/digital signature scheme.
4. Elliptic curve cryptosystems.
5. : : : : : :
 DL is based on nite groups.

9.1 Some Algebra

Further Reading: [Big85].

87
9.1.1 Groups

De nition 9.1.1 A group is a set G of elements together with a binary operation

\o" such that:
1. If a; b 2 G then a  b = c 2 G ! (closure).
2. If (a  b)  c = a  (b  c) ! (associativity).
3. There exists an identity element e 2 G :
e  a = a  e = a ! (identity).
4. There exists an inverse element a~, for all a 2 G :
a  a~ = e ! (inverse).

Examples:
1. G = Z = f: : : ; ,2; ,1; 0; 1; 2; : : :g
 = addition
(Z; +) is a group with e = 0 and a~ = ,a
2. G = Z
 = multiplication
(Z; ) is NOT a group since inverses a~ do not exist except for a = 1
3. G =C (complex numbers u + iv)
 = multiplication
(C ; ) is a group with e = 1 and
a~ = a,1 = uu2 ,+ ivv2

De nition 9.1.2 \Zn " denotes the set of numbers i, 0  i < n, which are relatively
prime to n.

88
Examples:
1. Z9 = f1; 2; 4; 5; 7; 8g
2. Z7 = f1; 2; 3; 4; 5; 6g

Multiplication Table

 mod 9 1 2 4 5 7 8
1 1 2 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1

Theorem 9.1.1 Zn forms a group under modulo n multiplication. The identity ele-
ment is e = 1.
Remark:
The inverse of a 2 Zn can be found through the extended Euclidean algorithm.

9.1.2 Finite Groups

De nition 9.1.3 A group (G , ) is nite if it has a nite number of g elements.

We denote the cardinality of G by jGj.

Examples:
1. (Zm; +): a + b = c mod m
Question: What is the cardinality ! jZmj = m
Zm = f0; 1; 2; : : : ; m , 1g

89
 2. (Zp; ): a  b = c mod p; p is prime
Question: What is the cardinality ! jZp j = p , 1
Zp = f1; 2; : : : ; p , 1g
De nition 9.1.4 The order of an element a 2 (G ; ) is the smallest positive integer
o such that a  a  : : :  a = ao = 1.
Example: (Z11 ; ), a = 3
Question: What is the order of a = 3?
a1 = 3
a2 = 32 = 9
a3 = 33 = 27  5 mod 11
a4 = 34 = 33
3 = 5
3 = 15  4 mod 11
a5 = a4
a = 4
3 = 12  1 mod 11
) ord(3) = 5

90
 De nition 9.1.5 A group G which contains elements with maximum order
ord( ) = jGj is said to be cyclic. Elements with maximum order are called gen-
erators or primitive elements.
Example: 2 is a primitive element in Z11
jZ11 j = jf1; 2; 3; 4; 5; 6; 7; 8; 9; 10gj = 10
a=2
a2 = 4
a3 = 8
a4 = 16  5
a5 = 10;
a6 = 20  9
a7 = 18  7
a8 = 14  3;
a9 = 6
a10 = 12  1
a11 = 2 = a.
) ord(a = 2) = 10 = jZ11 j
) (1) jZ11 j is cyclic
) (2) a = 2 is a primitive element

Observation (important): 2i; i = 1; 2; : : : ; 10 generates all elements of Z11

i 1 2 3 4 5 6 7 8 9 10
2i 2 4 8 5 10 9 7 3 6 1

91
Some properties of cyclic groups:
1. The number of primitive elements is (jGj).
2. For every a 2 G : ajGj = 1.
3. For every a 2 G : ord(a) divides jGj.
Proof only for (2): a = i
ajGj= ( i)jGj = ( jGj)i =: 1i = 1.

Example: Z11 ; jZ11 j = 10

1. (10) = (2 , 1)(5 , 1) = 1
4 = 4
2. a = 3 ! 310 = (35)2 = 12 = 1
3. homework : : :

92
9.2 The General DL Problem
Given a cyclic subgroup (G ; ) and a primitive element . Let

= |  {z: : : } = i
i times
be an arbitrary element in G .

General DL Problem:
Given G , ; = i, nd i.

i = log ( )

Examples:
1. (Z ; +); = 2; = 2| + 2 +{z: : : + 2} = i
2
11

i times
i 1 2 3 4 5 6 7 8 9 10 11
2i 2 4 6 8 10 1 3 5 7 9 0

Let i = 7: = 7
2  3 mod 11
Question: given = 2, = 3 = i
2, nd i
Answer: i = 2,
3 mod 11
1

Euclid's algorithm can be used to compute i thus this example is NOT a one-way
function.
2. (Z  ; ); = 2; = |2
2
{z: : :
2} = 2i
11
i times
= 3 = 2i mod 11
Question: i = log (3) = log (2i) = ?
2 2

Very hard computational problem!

93
9.3 Attacks for the DL Problem
1. Brute force:
check:
1 ?
=
2 ?
=
...
?i=

Complexity: O(jGj) steps.

Example: DL in Zp  p, tests2
1

minimum security requirement ) p , 1 = jGj  2 80

2. Shank's algorithm (Baby-step giant-step) and Pollard's- method:

Further reading: p. 165 in [Sti95].
q
Complexity: O( jGj) steps (for both algorithms).
Example: DL in Zp  pp steps
minimum security requirement ) p , 1 = jGj  2 160

3. Pohlig-Hellman algorithm:
Let jGj = p
p


|{z}
1 2 pl
Complexity: O(ppl ) steps.
largest prime

Example: DL in Zp : pl of (p , 1) must be  2 160

minimum security requirement ) pl  2 160

4. Index-Calculus method:
Further reading: [AM97].
Applies only to Zp and Galois elds GF(2k)
p p p
Complexity: O (e (1+O (1))
) steps.
ln( ) ln(ln( ))

Example: DL in Zp : minimum security requirement ) p  2 1024

94
 Remark: Index-Calculus is more powerful against DL in Galois Fields GF(2k ) than
against DL in Zp .

9.4 Die-Hellman Key Exchange

Remarks:
 Proposed in 1976 in Die-Hellman paper.
 Used in many practical protocols.
 Can be based on any DL problem.

9.4.1 Protocol

Set-up:

1. Find a large prime p.

2. Find a primitive element of Zp or
of a subgroup of Zp.
Protocol:
Alice Bob
pick kprA = aA 2 f2; 3; : : : ; p , 1g pick kprB = aB 2 f2; 3; : : : ; p , 1g
compute kpubA = bA = aA mod p compute kpubB = bB = aB mod p
bA
,!
bB
,
kAB = baBA = ( aB )aA kAB = baAB = ( aA )aB

Session key kses = kAB = aB
aA = aA
aB mod p.

95
9.4.2 Security

Question: Which information does Oscar have?

Answer: ; p; bA; bB .

Die-Hellman Problem:

Given bA = aA mod p; bB = aB mod p, and nd aA
aB mod p.

One solution to the D-H problem:

1. Solve DL problem: aA = log (bA) mod p.
2. Compute: baBA = ( aB )aA = aA
aB mod p.
Choose p  2 . 1024

Note:
There is no proof that the DL problem is the only solution to the D-H problem!
However, it is conjectured.

96
Chapter 10
Elliptic Curve Cryptosystem
Further Reading:
Chapter 6 in [Kob94].
Book by Alfred Menezes [Men93].

Remarks:
 Relatively new cryptosystem, suggested independently:
! 1987 by Koblitz at the University of Washington,
! 1986 by Miller at IBM.
 It is believed to be more secure than RSA/DL in Zp, but uses arithmetic with much
shorter numbers ( 160 { 256 bits vs. 1024 { 2048 bits).
 It can be used instead of D-H and other DL-based algorithms.
Drawbacks:
 Not as well studied as RSA and DL-base public-key schemes.
 It is conceptually more dicult.
 Finding secure curves in the set-up phase is computationally expensive.
97
10.1 Elliptic Curves
Goal: To nd another instance for the DL problem in cyclic groups.
Question: What is the equation x2 + y2 = r2 over reals?
Answer: It is a circle.
y

r2

Figure 10.1: x2 + y2 = r2 over reals

Question: What is the equation a
x2 + b
y2 = c over reals?

Answer: It is an ellipsis.
y

Figure 10.2: a
x2 + b
y2 = c over reals

Note:
There are only certain points (x,y) which ful ll the equation. For example the
point (x = r; y = 1) ful lls the equation of a circle.

98
 De nition 10.1.1 The elliptic curve over Zp, p > 3, is a set of all pairs (x, y) 2 Zp
which ful ll:
y 2  x3 + a
x + b mod p
where
a; b; 2 Zp
and
4
a3 + 27
b2 6= 0 mod p
Question: How does y2 = x3 + a
x + b look over reals?
y

Q+Q=2Q

Q
P
x

P+Q

Figure 10.3: y2 = x3 + a
x + b over the reals

Goal: Finding a (cyclic) group (G , ) so that we can use the DL problem as a one-way
function.
We have a set (points on the curve). We \only" need a group operation on the points.

99
Group G : Points on the curve given by (x, y).
Operation : P + Q = (x1; y1) + (x2 ; y2) = R = (x3 ; y3).

Question: How do we nd R?
Answer: First geometrically.
a) P 6= Q ! line through P and Q and mirror point of third interception along the x-axis.
b) P = Q ) P + Q = 2Q ! tangent line through Q and mirror point of second intersec-
tion along the x-axis.
Point Addition (group operation):

x3 = 2 , x1 , x2 mod p
y3 = (x1 , x3 ) , y1 mod p

where 8>
< y2 ,y1
x2 ,x1 6 Q
mod p ; if P =
=>
: 3x21 +a
2y1 mod p ; if P = Q
Remarks:
 If x1  x2 mod p and y1  ,y2 mod p, then P + Q = O which is an abstract point
at in nity.
 O is the neutral element of the group: P +O= P ; for all P .
 Additive inverse of any point (x; y) = P is P +(,P ) = O such that (x; y)+(x; ,y) = O.

Theorem 10.1.1 The points on an elliptic curve together with O have

cyclic subgroups.
100
Remark: Under certain conditions all points on an elliptic curve form a cyclic group as
the following example shows.
Example: Finding all points on the curve E: y2  x3 + x + 6 mod 11.
#E = 13.
primitive element ! = (2; 7) ) generates all points.
2 = + = (2; 7) + (2; 7) = (x3 ; y3)
 = 3x21y+1 a = (2
7),1 (3
4 + 1) = 3,1
13  4
13  4
2 = 8 mod 11
2

x3 = 2 , x1 , x2 = 82 , 2 , 2 = 60  5 mod 11
y3 = (x1 , x3 ) , y1 = 8(2 , 5) , 7 = ,24 , 7 = ,31  2 mod 11
2 = (2; 7) + (2; 7) = (5; 2)
3 = 2 + = :::
...
12 = 11 + = (2; 4)
13 = 12 + = (2; 4) + (2; 7) = (2; 4) + (2; ,4) = O
14 = 13 + =O+ =
...

All 12 non-zero elements together with O form a cyclic group.

= (2; 7) 2 = (5; 2) 3 = (8; 3)
4 = (10; 2) 5 = (3; 6) 6 = (7; 9)
7 = (7; 2) 8 = (3; 5) 9 = (10; 9)
10 = (8; 8) 11 = (5; 9) 12 = (2; 4)
Table 10.1: Non-zero elements of the group over y2  x3 + x + 6 mod 11

Remark: In general, nding of the group order #E is computationally very complex.

101
10.2 Cryptosystems
10.2.1 Die-Hellman Key Exchange
The cryptosystem is completely analogous to D-H in Zp .
Set-up:
1. Choose E: y2  x3 + a
x + b mod p.
2. Choose primitive element = (x ; y ).
Protocol:
Alice Bob
choose kprA = aA 2 f2; 3; : : : ; #E , 1g choose kprB = aB 2 f2; 3; : : : ; #E , 1g
compute kpubA = bA = aA
= (xA; yA) compute kpubB = bB = aB
= (xB ; yB )
bA
,!
bB
,
compute aA
bB = aA
aB
= (xk ; yk ) compute aB
bA = aB
aA
= (xk ; yk )
kAB = xk 2 Zp kAB = xk 2 Zp

Security:
8
>< E; p; ; bA = aA
; bB = aB

Die-Hellman problem for elliptic curves >
Oscar knows:

: Oscar wants to know: kAB = aA
aB

One possible solution to the D-H problem for elliptic curves:
1. Compute discrete logarithm:
Given and | + +{z: : : + } = bA , nd aA.
aA times
2. Compute aA
bB = aA
aB
.

102
Attacks:
 Only possible attacks against elliptic curves are the Pohlig-Hellman scheme together
with Shank's algorithm or Pollard's-Rho method.
) #E must have one large prime factor pl
) 2160  pl  2250.
 So-called \Koblitz curves" (curves with a; b 2 f0; 1g)
 For supersingular elliptic curves over GF(2n), DL in elliptic curves can be solved by
solving DL in GF(2k
n); k  6.
) stay away from supersingular curves despite of possible faster implementations.
 Powerful index-calculus method attacks are not applicable (as of yet).

10.2.2 Menezes-Vanstone Encryption

Set-up:
1. Choose E: y2  x3 + a
x + b mod p.
2. Choose primitive element = (x ; y ).
3. Pick random integer a 2 f2; 3; : : : ; #E , 1g.
4. Compute a
= = (x ; y ).
5. Public Key: kpub = (E; p; ; ).
6. Private Key: kpr = (a).

103
Encryption:
1. Pick random k 2 f2; 3; : : : ; #E , 1g. Compute k
= (c1; c2).
2. Encrypt ekpub (x; k) = (Y0; Y1; Y2).
Y0 = k
! point on the elliptic curve.
Y1 = c1
x1 mod p ! integer.
Y2 = c2
x2 mod p ! integer.
Decryption:
1. Compute a
Y0 = (c1; c2 ).
a
Y0 = a
k
= k
= (c1 ; c2 ).

2. Decrypt: dkpr (Y0; Y1; Y2) = (Y1
c,1 1 mod p; Y2
c,2 1 mod p) =
(x1 ; x2).
Remark: The disadvantage of this scheme is the message expansion factor:
# bits y = 4dlog2 pe = 2
# bits x 2dlog2 pe

10.3 Implementation
1. Hardware:
 Approximatly 0.2 msec for an elliptic curve point multiplication with 167 bits on
an FPGA [OP00].
2. Software:
 One elliptic curve point multiplication a
P in less than 10 msec over GF(2155).
 Implementation on 8-bit smart card processor without coprocessor available

104
Chapter 11
ElGamal Encryption Scheme
11.1 Cryptosystem
Remarks:
 Published in 1985.
 Based on the DL problem in Zp or GF(2k ).
 Extension of the D-H key exchange for encryption.
Protocol:
Alice Bob
choose private key kprA = aA choose private key kprB = aB
compute kpubA = aA mod p = bA compute kpubB = aB mod p = bB
bA
,!
bB
,
kAB = baBA = aA aB mod p kAB = baAB = aB aA mod p
y
y = x
kAB mod p ,!
x = y
kAB
,1 mod p

105
ElGamal:
Set-up:
1. Choose large prime p.
2. Choose primitive element 2 Zp .
3. Choose secret key a 2 f2; 3; : : : ; p , 2g.
4. Compute = a mod p.
5. Public Key: Kpub = (p; ; ).
6. Private Key: Kpr = (a).
Encryption:
1. Choose k 2 f2; 3; : : : ; p , 2g.
2. Y1 = k mod p.
3. Y2 = x
k mod p.
4. Encryption: = ekpub (x; k) = (Y1; Y2).
Decryption:

x = dkpr (Y1 ; Y2 ) = Y2 (Y1a ),1 mod p:

106
Question: How does the ElGamal scheme work?
dkpr (Y1 ; Y2 ) = Y2 (Y1a ),1
= x
k (( k )a ),1 ! but = a
= x( a )k (( k )a),1
= x
ak
,ak
=x

107
Remarks:
 ElGamal is essentially an extension of the D-H key exchange protocol.
9
Y =x
> k =
 2 1 k >; if x1 is known, k can be found from Y2.
Y3 = x2

Thus for every message block xi choose a new k!
 Message expansion factor
# of y bits = 2dlog 2py e = 2
# of x bits dlog 2pxe
.

11.2 Computational Aspects

11.2.1 Encryption
9
Y1 = k mod p >=
Y2 = x
k mod p >; apply the square-and-multiply for exponentiation

11.2.2 Decryption

x = dkpr (Y1 ; Y2 ) = Y2 (Y1a ),1 mod p.

Question: How can (Y1a ),1 be computed eciently?

Derivation: b 2 Zp:
be = bq(p,1)+r = (bp,1 )q
br
= 1q
br mod p
= br mod p
) e = r mod (p , 1)

108
 Thus, be  be mod (p,1) mod p, where b 2 Zp and e 2 Z

The above derivation can be used for decryption:

(Y1a),1 = Y1,a = Y1,a mod (p,1) mod p

= Y1p,1,a mod p

Note: Y1p,1,a mod p can be computed using the square-and-multiply algorithm.

11.3 Security of ElGamal

Oscar knows: p; ; = a; Y1 = k ; Y2 = x
k .
Oscar wants to know: x
 He attempts to nd the secret key a:
1. a = log mod p hard, DL problem.
2. x = Y2(Y1a ),1 mod p easy.
 He attempts to nd the random exponent k:
1. k = log Y1 mod p hard, DL problem.
2. Y2
,k = x easy.
 In both cases Oscar has to compute the DL problem in nite elds (Zp or GF(2k )).
He can use index-calculus method which forces us to implement schemes with at least
1024 bits.

109
Chapter 12
Digital Signatures
Protocols use:
 Private-key algorithms.
 Public-key algorithms.
 Digital Signatures.
 Hash functions.
 Message Authentication Codes.
as building blocks. In practice, protocols are often the most vulnerable part of a cryp-
tosystem. The next two chapters deal with digital signature, message authentication codes
(MACs), and hash functions.

110
12.1 Principle
The idea is similar to a conventional signature where a given message x gets a unique digital
signature which is a function of the message and is attached to the message.

message x

signature f(message) = f(x)

Figure 12.1: Digital signature and message block

message space

signature space

sig (x) = y
Kpr

y
x

true if y = sig(x)
ver (x, y)=
Kpub false if y == sig(x)

Figure 12.2: Digital signature and message domain

111
Basic protocol:
1. Bob signs his message x with his private key kpr :
) y = sigk (x).
pr

2. Bob sends (y; x) to Alice.

3. Alice runs the veri cation function verk (x; y) with Bob's public key.
pub

Properties of digital signatures:

 Only Bob can sign his document (with kpr ).
 Everyone can verify the signature (with kpub).
 Authentication: Alice is sure that Bob signed the message.
 Integrity: Message x cannot be altered since that would be detected through veri ca-
tion.
 Non-repudiation

12.2 RSA Signature Scheme

Set-up: kpr = (p; q; a); kpub = (n; b).
General Protocol:
1. Bob computes: y = sigk (x) = ek (x) = xa mod n.
pr pr

2. Bob sends (x; y) to Alice.

3. Alice veri es:
8
>
< =x ) true
verkpub (x; y ) = dkpub (y ) = y >
b
: 6= x ) false

112
Question: Why does it work?
dkpub (y ) = dkpub (ekpr (x)) = x:

Remark:
 The role of public/private key are exchanged if compared with RSA public-key encryp-
tion.
 This algorithm was standardized in ISO/IEC 9796.
Drawback:
Oscar can generate a valid signature for a random message x:
1. Choose signature y 2 Zn.
2. Encrypt: x = ek (y) = yb mod n ! outcome x cannot be controlled.
pub

3. Send (x; y) to Alice.

4. Alice veri es: verk (x; y): yb  x mod n ) true.
pub

12.3 ElGamal Signature Scheme

Remarks:
 ElGamal signature scheme is di erent from ElGamal encryption.
 Digital Signature Algorithm (DSA) is a modi cation of ElGamal signature scheme.
 This scheme was published in 1985.

113
Set-up:
1. Choose a prime p.
2. Choose primitive element 2 Zp .
3. Choose random a 2 f2; 3; : : : ; p , 2g.
4. Compute = a mod p.
Public key: kpub = (p; ; ).
Private key: kpr = (a).
Signing:
1. Choose random k 2 f0; 1; 2; : : : ; p,2g; such that gcd(k; p,1) = 1.
2. Compute signature:

sigkpr (x; k) = ( ;  ); where

= k
mod p
 = (x , a
)k,1 mod p , 1
Public veri cation:

8
>
<= x
mod p valid signature
verkpub (x; ( ;  )) =

>
: 6= x
mod p invalid signature
Question: Why does this scheme work?


= ( a) ( k )(x,a
)k, 1 mod (p,1) mod p
k
k,1 (x,a

= a


) mod p
a
,a
+x =
= x

114
Chapter 13

Hash Functions

13.1 Introduction
The problem with digital signatures is that long messages require very long signatures. We
would like for performance as well as for security reasons to have one signature for a message
of arbitrary length. The solution to this problem are Hash functions.
x

x x is of arbitrary length

zi = h ( xi ||zi-1 )

z z is of fixed length

sig (z)
kpr

y = sig (z) y is of fixed length

kpr

Figure 13.1: Hash functions and digital signatures

115
Remarks:
 z, x don't have the same length.
 h(x) has no key.
 h(x) is public.
Basic Protocol:
Alice Bob
1) z = h(x)
2) y = sigk (z)
pr

3) (x;y)
,
4) z = h(x)
5) verk (z; y)
pub

Potential hash function properties

a) One-way: for (almost) all given output z, it is impossible to nd any input x such that
h(x) = z .

b) Weak collision resistant: given x, and thus h(x), it is impossible to nd any x0 such
that h(x) = h(x0 ).
c) Strong collision resistant: it is impossible to nd any two pairs x; x0 such that
h(x) = h(x0 ).

116
Requirements for a hash function (Adopted from [Sta95])
1. h(x) can be applied to x of any size.
2. h(x) produces a xed length output.
3. h(x) is relatively easy to compute in software and hardware.
4. h(x) is one-way.
5. h(x) is weak collision resistant.
6. h(x) is strong collision resistant.
Discussion:
 (1) | (3) are practical requirements
 (4) if h(x) is not one-way, Oscar can compute x from h(x) in cases where x is encrypted.
 (5) if h(x) is not weak collission free, Oscar can replace x with x0 .
Alice Oscar Bob
z = h(x)
(x;y)
, y = sigK (z )
pr
(y;x0 )
,
z = h(x0 ) = h(x)
verKpub (z; y ) = true

 (6) if h(x) is not strong collission free, Oscar runs the following attack:
a) Choose legitimate message x1 and fraudulent message x2

117
 b) Alter x1 and x2 at \non-visible" location, i.e. replace tabs through spaces, append
returns, etc., until h(x01 ) = h(x02 ) (Note: e.g. 64 alteration locations allow 264
versions of a message with 264 di erent hash values).
c) Let Bob sign x01 ! (x01 ; sigK (h(x01 ))
pr

d) Replace x01 ! x02 and (x02 ; sigK (h(x02))

pr

13.2 Security Considerations

Question: How many people are needed at a party so that there is a 50% chance that at
least two people have the same birthday?

In general, given a large set with n di erent values:

  ! k ,1 
1 2 k,1 Y i
P (no collission among k random elements) = 1 , 1,


1, = 1,
| {z n } n n i=1 n
|k = 2 elt.{z }
| k = 3 elt. {z }
k elt.
Often n is large (n = 365 in birthday paradox, n = 2160 in hash functions).
Recall:
x2 x3
e,x = 1 , x + , +



2! 3!
if x << 1
e,x  1 , x
Thus,
k ,1
Y ,i k,
P (no collision)  e n = e, n e, n e, n


e, n
1 2 3 1

i=1
k ,1
Y ,i


+k,1
e n = e,
1+2+3+
n

i=1

118
Rewriting the exponent with the help of the following identity:

1 + 2 + 3 +


+ k , 1 = k(k , 1)=2

We obtain,
,
P (no collission)  e,
k(k 1)
2n

De ne  as
,
P (at least one collission) =   1 , e,
DEF k(k 1)
2n

,
1 ,   e,
k(k 1)
2n

ln (1 , )  , k(k , 1)
2n  1 
k(k + 1)  ,2n ln (1 , ) = 2n ln
1,
If k >> 1, then
 1 
k2  k(k , 1)  2n ln
1,
s  1 
k  2n ln 1 , 

Example: s   p
k( = 0:5)  2n ln
1 = 2 ln 2
pn = 1:18pn
1 , 0:5

) A collission in a set of n values is found after about pn trials with a probability of 0.5.
p
In other words, hash funtion with 40 bit output ) collission after  240 = 220 trials.

) In order to provide collision resistance in practice, the output space of the hash function
should contain at least 2160 elements, that is, the hash function should have at least 160
p
output bits. Finding a collision takes then roughly 2160 = 280 steps.

119
13.3 Hash Algorithms
Overview:
Hash Algorithms

customized modular arithmetic based

e.g. MD4 family (rare, often unsecure)
block cipher based

Figure 13.2: Family of Hash Algorithms

a) MD4{family
1. SHA-1

Output: 160 bits ) input size for DSS.

Input: 512 bit chunks of message x.
Operations: bitwise AND, OR, XOR, complement and cyclic shift.

2. RIPE-MD 160

Output: 160 bits.

Input: 512 bit chunks of message x.
Operations: same as SHA but runs two algorithms in parallel whose
outputs are combined after each round.

120
b) Hash functions from block ciphers

xi

H i-1 m
g e
K Hi = e g(H )
( xi ) xi
i-1

Hi

Figure 13.3: Hash Functions from Block Ciphers

where g is a simple n-to-m bit mapping function (if n = m, g can be the identity
mapping)
Last output Hl is the hash of the whole message x ,x ,: : :,xl
1 2

Also secure are:

{ Hi = Hi,  ex (Hi, )
1 i 1

{ Hi = Hi,  xi  eg H , (xi)
1 ( i 1)

Remark:
For block ciphers with less than 128 bit block length, di erent techniques
must be used (Sec. 9.4.1 (ii) in [AM97])

121
Chapter 14
Message Authentication Codes
(MACs)
Other names: \cryptographic checksum" or \keyed hash function".
Private-key based.

14.1 Principle message space

"signing"
signature space

MACK (x)

y
x

?
MACK (x) = y ; verification

Figure 14.1: MAC and message domain

122
Protocol:
Alice Bob
1) y = MACK (x)
2) x;y,
( )

3) y0 = MACK (x)
y0 = y?

Properties:
1. Generate signature for a given message.
2. Private-key based: signing and verifying party must share a secret
key.
3. Accepts messages of arbitrary length and generates xed size sig-
nature.

Properties 2 and 3 are di erent from digital signatures.

Idea: To use block-cipher's one of the chaining modes to generate signature.

14.2 MACs from Block Ciphers

CBC mode:
y = ek (x  IV ) = ek (x  0000 : : :)
0 0 0

yi = ek (xi  yi, )
1

X = x ; x ; : : : ; xm,
0 1 1

MACk (x) = ym, 1

123
 i=1 IV i=1 IV

Y i-1 Y i-1

Y i-1 Y i-1
i=n
X n , ... , X2 , X 1 Y n X n , ... , X2 , X 1 Yi
e e
Y’n
?
k k
Yn

X n , ... , X2 , X 1

Figure 14.2: MAC in a CBC mode

Veri cation: Run the same process on the receiving end.

Remark: CBC with DES is standardized (ANSI X9.17).

14.3 HMAC
 Popular in modern protocols such as SSL.
 Attractive property: HMAC can be proven to be secure under certain assumptions
about the hash function. \Secure" means here that the hash function has to be broken
in order to break the HMAC.
 Basic idea: Hash a secret key K together with the message M and consider the hash
output the authentication tag for the message: H (K jjM ).
 Details:
HMACK (M ) = H [(K  opad)jjH [(K  ipad)jjM ]]
+ +

where
K = K padded with zeros on the left so that the result is b bits in length (where b
+

is the number of bits in a block).

124
ipad = 00110110 repeated b=8 times.
opad = 01011010 repeated b=8 times.

125
Chapter 15
Security Services
15.1 Attacks Against Information Systems

Information Information
source destination

(a) Normal flow (b) Interruption

(c) Interception (d) Modification

(e) Fabrication

126
 Remarks:
 Passive attacks: (c) ! interception.
 Active attacks: (b) ! interruption, (d) ! modi cation, (e) ! fabrication.

15.2 Introduction
Security Services are goals which information security systems try to achieve. Note that
cryptography is only one module in information security systems.

The main security services are:

 Con dentiality/Privacy. Information is kept secret from all but authorized parties.
 (Message/Sender) Authentication. Ensures that the sender of a message is who she/he
claims to be.
 Integrity. Ensures that a message has not been modi ed in transit.
 Non-repudiation. Ensures that the sender of a message can not deny the creation of
the message.
 Identi cation/Entity Authentication. Establishing of the identity of an entity (e.g. a
person, computer, credit card).
 Access Control. Restricting access to the resources to privileged entitites.
Remark: Message Authentication implies data integrity; the opposite is not true.

15.3 Privacy
Tool: Encryption algorithm.

127
a) Private-Key

e Y dk
X k X

k k

Provides:
,privacy 9
,message authentication and thus >>>= only if Bob can distinguish
,integrity >> between valid and invalid X

,no non-repudiation >; and if there are only two parties.

Remark:
In practice, authentication and integrity are often achieved with MACs
(Chapter 14)
b) Public-Key

e Y dkpr_B
X kpub_B X
ekpub_B (x)

kpub_B kpr_B

Provides:
- privacy
- integrity (if invalid can e detected)
x

- no message authentication
128
15.4 Integrity and Sender Authentication
Recall: Sender authentication implies integrity.

15.4.1 Digital Signatures

(x, y) (x, y)
x x

y
y = sig (h(x)) x
Kpr_A
x h(x) sig h(x) ver true / false

Kpr_A Kpub_A

Provides:
- integrity
- sender authentication
- non-repudiation (only Alice can construct valid signature)

15.4.2 MACs
(x, y) (x, y)
x x

x MAC y x MAC true / false

K K

Provides:

129
 - integrity
- authentication
- no non-repudiation

15.4.3 Integrity and Encryption

(x, y)
x e d
eK (x, y)
y
y x compare
x K
h(x) K h(x)
y’

Provides:
- privacy
- integrity
- authentication
- no non-repudiation
Remark:
 Instead of hash functions, MACs are also possible. In this case: =
c e K1 (x; MACK2 (y )).

 This scheme adds strong authentication and integrity to an encryption-protocol with

very little computational overhead.

130
Chapter 16
Key Establishment
16.1 Introduction
Secret key establishment

key distribution key agreement

One party generates Both parties generate
secret key and distributes secret key jointly
it

Figure 16.1: Key establishment schemes

Remark:
Some schemes make use of trusted authority (TA) which is trusted by and can
communicate with all users.

131
16.2 Private-Key Approaches
16.2.1 The n2 Key Distribution Problem
TA generates a key for every pair of users:

Example: = 4 users.
n

KAB KAC KAD KAB KBC KBD

A B

TA secure channels

D C
KAD KBD KCD KAC KBC KCD

Figure 16.2: The role of the Trusted Authority

Drawbacks:
 secure channels are needed
n

 each user must store , 1 keys

n

 TA must transmit ( , 1) keys

n n

 TA must generate n n,  n keys

(
2
1) 2
2

 every new network user makes updates at all other user as of necessary ) scales badly

132
16.2.2 Key Distribution Center (KDC)
TA is a KDC: TA shares secret key with each user and generates session keys.

a) Basic protocol:
- ks = session key between Alice and Bob
- kA;KDC = secret key between Alice and KDC (Key encryption key, KEK)
- kB;KDC = secret key between Bob and KDC (Key encryption key, KEK)

Alice KDC Bob

ekA;KDC (ks )=yA ekB;KDC (ks )=yB
, ,!
k s = dkA;KDC (yA ) ks = dkB;KDC (yB )
y
y = e ks (x) ,! x = dks (y )

Remarks:
{ TA stores only keys n

{ each user stores only one key

U

b) Modi ed (advanced) protocol:

Alice KDC Bob
1a) A = kA ( s)
y e k

1b) B = kB ( s)
y e k

2) yA ;yB )
(
,
3) k s = dkA (yA)
5)y;yB
4) = y e ks (x) ,! ( )
7) s = kB ( B )
k d y

6) = ks ( )
x d y

Remark: This approach is the basis for Kerberos.

133
16.3 Public-Key Approaches
16.3.1 Man-In-The-Middle Attack
D-H key exchange revised
Set-up:
- nd large prime p
- nd primitive element 2 Zp
Protocol:
Alice Bob
pick kprA = aA 2 f2; 3; : : : ; p , 2g pick kprB = aB 2 f2; 3; : : : ; p , 2g
compute kpubA = bA = aA mod p compute kpubB = bB = aB mod p
bA
,!
bB
,
kAB = baBA = aA aB mod p kAB = baAB = aA aB mod p
Security:
1. passive attacks
) security relies on Die-Hellman problem thus p > 2 1000
.
2. active attack
) Man-in-the-middle attack:
Alice Oscar Bob
a o
,! ,!
,o ,b
kAO = ( o)a = ao kAO = ( a )o kBO = ( o)b = bo

kBO = ( b)o
y
y = ekAO (x) ,! x = dkAO (y )
0
0 0

y
y = ekBO (x) ,! x = dkBO (y )
00
00 00

134
 Remarks:
 Oscar can read and alter x without detection.
 Underlying Problem: public keys are not authenticated.
 Man-in-the-middle attack applies to all Public-key schemes.

16.3.2 Certi cates

Certi cates bind ID information (e.g., name, social security number) to a public key through
digital signatures.

General structure of certi cates:

1. Each user U :
 ID(U) = ID information such as user name, e-mail address, SS#, etc.
 private key: KprU
 public key: KpubU
2. Certifying Authority (CA):
 secret signature algorithm sigTA
 public veri cation algorithm verTA
 certi cates for each user U:
C (U ) = (ID(U ); KprU ; sigTA(ID(U ); KprU ))
General requirement: all users have the correct veri cation algorithm verTA with TA's public
key.

135
 0000000
1111111
1111111
0000000
1111111
0000000 ID(U)
0000000
1111111
0000000
1111111
0000000
1111111 KprU
1111111
0000000
0000000
1111111 sig TA(ID(U), K prU )
0000000
1111111
Figure 16.3: General structure of the certi cate C(U)

Version

Serial Number

Algorithm Identifier:
- Algorithm
- Parameters

Issuer

Period of Validity:
- Not Before Date
- Not After Date

Subject

Subject’s Public Key:

- Algorithm
- Parameters
- Public Key

Signature

Figure 16.4: Detailed structure of an X.509 certi cate

136
Remarks:
 Certi cate structures are speci ed in X.509, authentication services for the X.500 di-
rectory recommendation (CCITT).

16.3.3 Die-Hellman Exchange with Certi cates

Idea: As standard D-H, but each users's public key is authenticated by a certi cate.

Alice Bob
KpubA = bA KpubB = bB
KprA = aA KprB = aB
C (B)=(ID(B);bB ;sigCA (ID(B);bB ))
,
C (A)=(ID A ;bA ;sigCA ID A ;bA
( )
,! ( ( ) ))

1.) verCA(ID(B ); bB ) 1.) verCA(ID(A); bA)

2.) kAB = baBA = aB aA = aA aB 2.) kAB = baAB = aAaB
Remaining major problems with CAs:
1. The CA's public key must initially be distributed in an authenticated manner!
2. Identity of user must be established by CA.
3. Certi cate Revocation Lists (CRLs) must be distributed.

16.3.4 Authenticated Key Agreement

Idea: Alice and Bob sign their own public keys. Signatures can be correctly veri ed through
certi cates.

137
Set-up:
 public veri cation key for verTA
 public prime p
 public primitive element 2 Zp
Protocol:
Alice TA Bob
C (A)=(ID(A);verA ;sigTA(ID(A);verA ))
,
C (B)=(ID(B);verB ;sigTA (ID(B);verB ))
,!
1.) kprA = aA
bA
2.) kpubA = bA = aA mod p ,!
3.) kprB = aB
4.) kpubB = bB = aB mod p
5.) kAB = baAB = aAaB mod p
C (B);bB ;yB )
(
, 6.) yB = sigB (bB ; bA)
7.) verTA(C (B )): true/false
8.) verB (yB ): true/false
9.) kAB = baBA = aAaB mod p
C (A);yA )
10.) yA = sigA(bA ; bB ) (
,!
11.) verTA(C (A)): true/false
12.) verA(yA): true/false
Remark:
This scheme is also known as station-to-station protocol and is the basis for
ISO 9798-3.

138
Chapter 17
Case Study: The Secure Socket Layer
(SSL) Protocol
Note:
This chapter describes the most important security mechanisms of the SSL Pro-
tocol. For more details references [Sta99] and Netscape's SSL web page are
recommended.

17.1 Introduction

 SSL was developed by Netscape.

 TLS (Transport Layer Security) is the IETF standard version of SSL. TLS is very close
to SSL.
 SSL provides security services for end-to-end applications.
 Most applications must be SSL enabled, i.e., SSL is not transparent.
 SSL is algorithm independent: for both public-key and symmetric-key operations, sev-
eral algorithms are possible. Algorithms are negotiated on a per-session basis.
139
 HTTP FTP SMTP
SSL or TLS
TCP
IP

Figure 17.1: Location of SSL in the TCP/IP protocol stack.

 SSL consists of two main phases:

Handshake Protocol : provides shared secret key using public-key techniques and
mutual entity authentication.
Record Protocol : provides con dentiality and message integrity for application
data, using the shared secret established during the Handshake Protocol.

140
17.2 SSL Record Protocol

The SSL Record Protocol provides two main services:

1. Con dentiality: SSL payloads are encrypted with a symmetric cipher. The keys are for
the symmetric cipher and they must be established during the preceding handshake
protocol.
2. Message Integrity: the integrity of the message is provided through HMAC, a message
authentication code.

17.2.1 Overview of the SSL Record Protocol

Application data

Fragment

11
00
1111111
0000000
0000000
1111111
00
11
Add MAC
0000000
1111111
0000000
1111111

000000000
111111111
000000000
111111111
Encrypt

111111111
000000000
000000000
111111111
Append SSL
record header

Figure 17.2: Simpli ed operations of the SSL Record Protocol

Description:
 Fragmentation: the message is devided into blocks of 214 bytes.
 MAC: a derivative of the popular HMAC message authentication code. HMACs are
based on hash functions.

MAC = H(secret-key jj pad2 jj

141
 H(secret-key jj pad1 jj seq-num jj fragment-length jj fragment))
where:
H = hash algorithm; either MD5 or SHA-1.
secret-key = shared secret session key.
pad1 = the byte 0x36 (0011 0110) repeated 48 times (384 bits) for MD5 and 40
times (320 bits) for SHA-1.
pad2 = the byte 0x5C (0101 1100) repeated 48 times for MD5 and 40 times for
SHA-1.
seq-num = the sequence number of the message.
fragment-length = length of the fragment (plaintext).
fragment = the plaintext block for which the MAC is computed.

 Encrypt: the following algorithms are allowed:

1. Block ciphers:
{ IDEA (128-bit key)
{ RC-2 (40-bit key)
{ DES-40 (40-bit key)
{ DES (56-bit key)
{ 3DES (168-bit key)
{ Fortezza (80-bit key)
2. Stream ciphers:
{ RC4-40 (40-bit key)
{ RC4-128 (128-bit key)

142
17.3 SSL Handshake Protocol

Remark: Most complex part of SSL, requires costly public-key operations

17.3.1 Core Cryptographic Components of SSL

CLIENT SERVER

random, cipher suite

PHASE 1
random, cipher suite

certificate
PHASE 2

key exchange parameters

certificate
PHASE 3

key exchange parameters

Figure 17.3: Simpli ed SSL Handshake Protocol

Explanation:
 Phase 1: establish security capabilities.
random : 32-bit timestamp concatenated with 28-byte random value. Used
as nonces and to prevent replay attacks during the key exchange.
cipher suite : several elds, in particular:

143
 1. Key exchange method.
(a) RSA: the secret key is encrypted with the receiver's public RSA-
key. Certi cates are required.
(b) Authenticated Die-Hellman: Die-Hellman with certi cate.
(c) Anonymous Die-Hellman: Die-Hellman without authentica-
tion.
(d) Fortezza
2. Secret-key algorithm (see Section 17.2).
3. MAC algorithm (MD5 or SHA-1).
 Phase 2: server authentication and key exchange.
Certi cate : authenticated public key for any key exchange method except
anonymous Die-Hellman.
Key exchange parameters : signed public-key parameters, depending on
the key exchange method.
 Phase 3: see Phase 2.

144
Chapter 18
Introduction to Identi cation Schemes
Examples for electronic identi cation situation:
1. Money withdrawal from ATM machine (PIN).
2. Credit card purchase over telephone (card number).
3. Remote computer login (user name and password).

Distinction between identi cation (or entity authentication) and message authentication:
 Identi cation schemes are performed online.
 Identi cation schemes do not require a meaningful message.

Basis for identi cation techniques:

9
1. Something known (password, PIN) >
=
cryptography based
2. Something possessed (chipcard) >;
3. Something inherent to a human individual ( ngerprint, retina pattern)

145
 Overview:
ID techniques

weak identification strong identification

(passwords, PINs)

private-key public-key zero-knowledge

use challenge-response (CR) protocols

Figure 18.1: Identi cation Techniques

) passwords and PINs are weak since they violate requirement 1 below.

Goals (informal de nition):

1. Alice wants to prove her identity to Bob without revealing her

identifying information to a listening Oscar. (\strong identi ca-
tion")
2. Also, Bob should not be able to impersonate Alice.
To achieve these goals, Alice has to perform a proof of knowledge which in general involves
a challenge-and-response protocol.

146
18.1 Private-key Approach
Challenge-and-response (CR) protocol:
Assumption: Alice and Bob share a secret key kAB and a keyed one-way function f (x).
Alice Bob
1) generate challengex
x
,
y
2) y = fkAB (x) ,!
3) y = fkAB (x)
0

4) veri cation: y =? y 0

Example:
a) fk (x) = DESk (x).
b) fk (x) = H (kjjx).
c) fk (x) = xk mod p.

Remarks:
 CR protocols are standardized in ISO/IEC 9798.
 There are many variations to the above protocol, e.g., including time stamps or serial
numbers in the response.
 Instead of block ciphers, public-key algorithms and keyed hash functions can be used.

Variant with time stamp (TS)

147
Alice Bob
1) y = ekAB (T S; I D(Bob))
y
,!
2) (T S ; I D (Bob) = e,1
0 0
kAB (y )
? ?
T S  time  T S + 

148
Bibliography
[AM97] S.A. Vanstone A.J. Menezes, P.C. Oorschot. Handbook of Applied Cryptography.
CRC Press, 1997.
[Big85] N.L. Biggs. Discrete Mathematics. Oxford University Press, New York, 1985.
[Bih97] E. Biham. A Fast New DES Implementation in Software. In Fourth Inter-
national Workshop on Fast Software Encryption , volume LNCS 1267, pages
260{272, Berlin, Germany, 1997. Springer-Verlag.
[EYCP00] A. J. Elbirt, W. Yip, B. Chetwynd, and C. Paar. An FPGA Implementation
and Performance Evaluation of the AES Block Cipher Candidate Algorithm
Finalists. In Third Advanced Encryption Standard (AES3) Conference, pages
13{27, New York, USA, March 13{14, 2000. National Institute of Standards
and Technology (NIST).
[Kob94] N. Koblitz. A Course in Number Theory and Cryptography. Springer-Verlag,
New York, second edition, 1994.
[Men93] A.J. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic
Publishers, 1993.
[OP00] Gerardo Orlando and Christof Paar. A High-Performance recon gurable Elliptic
Curve Processor for GF (2m). In Cetin K. Koc and Christof Paar, editors, Cryp-

149
 tographic Hardware and Embedded Systems (CHES'2000), pages 41{56, Berlin,
2000. Springer-Verlag. Lecture Notes in Computer Science Volume.
[Sch93] B. Schneier. Applied Cryptography. Wiley & Sons, 1993.
[Sim92] G.J. Simmons. Contemporary Cryptology. IEEE Press, 1992.
[Sta95] W. Stallings. Network and Internetwork Security. Prentice Hall, 1995.
[Sta99] W. Stallings. Cryptography and Network Security { Principles and Practice.
Prentice Hall, 2nd edition, 1999.
[Sti95] D.R. Stinson. Cryptography, Theory and Practice. CRC Press, 1995.
[WD76] M.E. Hellman W. Die. New directions in cryptography. In IEEE Transactions
on Information Theory, volume IT-22, pages 644{654, 1976.
[WPR+99] D. Craig Wilcox, Lyndon G. Pierson, Perry J. Robertson, Edward L. Witzke,
and Karl Gass. A DES ASIC Suitable for Network Encryption at 10 Gbps and
Beyond. In Cetin K. Koc and Christof Paar, editors, Cryptographic Hardware
and Embedded Systems (CHES'99), pages 37{48, Berlin, 1999. Springer-Verlag.
Lecture Notes in Computer Science Volume 1717.
[WWGP00] T. Wollinger, M. Wang, J. Guajardo, and C. Paar. How Well Are High-End
DSPs Suited for the AES Algorithms? AES Algorithms on the TMS320C6x
DSP. In Third Advanced Encryption Standard (AES3) Conference, pages 94{
105, New York, USA, March 13{14, 2000. National Institute of Standards and
Technology (NIST).

150