Introduction to Modern Cryptography

[Pages:283]Introduction to Modern Cryptography

Mihir Bellare1

Phillip Rogaway2

May 11, 2005

1 Department of Computer Science and Engineering, University of California at San Diego, La Jolla, CA 92093, USA. mihir@cs.ucsd.edu,

2 Department of Computer Science, Kemper Hall of Engineering, University of California at Davis, Davis, CA 95616, USA; and Department of Computer Science, Faculty of Science, Chiang Mai University, Chiang Mai, 50200 Thailand. rogaway@cs.ucdavis.edu,

2

Preface

This is a set of class notes that we have been developing jointly for some years. We use them for cryptography courses that we teach at our respective institutions. Each time one of us teaches the class, he takes the token and updates the notes a bit. The process has resulted in an evolving document that has lots of gaps, as well as plenty of "unharmonized" parts. One day it will, with luck, be complete and cogent.

The viewpoint taken throughout these notes is to emphasize the theory of cryptography as it can be applied to practice. This is an approach that the two of us have pursued in our research, and it seems to be a pedagogically desirable approach as well.

We would like to thank the following students of past versions of our courses who have pointed out errors and made suggestions for changes: Andre Barroso, Keith Bell, Kostas Bimpikis, Alexandra Boldyreva, Dustin Boswell, Brian Buesker, Michael Burton, Chris Calabro, Sashka Davis, Alex Gantman, Bradley Huffaker, Hyun Min Kang, Vivek Manpuria, Chanathip Namprempre, Adriana Palacio, Wenjing Rao, Fritz Schneider, Juliana Wong. We welcome further corrections, comments and suggestions.

Mihir Bellare Phillip Rogaway

San Diego, California USA Davis, California USA

c Mihir Bellare and Phillip Rogaway, 1997?2005.

Contents

1 Introduction

7

1.1 Goals and settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.2 Other goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 What cryptography is about . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.4 Approaches to the study of cryptography . . . . . . . . . . . . . . . . . . . . . . . . 18 1.5 What background do I need? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2 Classical Encryption

29

2.1 Substitution ciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.2 One-time-pad encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.3 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Blockciphers

39

3.1 What is a blockcipher? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 3.2 Data Encryption Standard (DES) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.3 Key recovery attacks on blockciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.4 Iterated-DES and DESX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.5 Advanced Encryption Standard (AES) . . . . . . . . . . . . . . . . . . . . . . . . . . 50 3.6 Limitations of key-recovery based security . . . . . . . . . . . . . . . . . . . . . . . . 54 3.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55

4 Pseudorandom Functions

59

4.1 Function families . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.2 Random functions and permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 4.3 Pseudorandom functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 4.4 Pseudorandom permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.5 Modeling blockciphers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 4.6 Example attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 4.7 Security against key recovery . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.8 The birthday attack . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.9 The PRP/PRF switching lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.10 Unix one-way function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.11 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

3

4

CONTENTS

5 Symmetric Encryption

93

5.1 Symmetric encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 5.2 Some symmetric encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 5.3 Issues in privacy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 5.4 Indistinguishability under chosen-plaintext attack . . . . . . . . . . . . . . . . . . . . 102 5.5 Example chosen-plaintext attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 5.6 Semantic security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 5.7 Security of CTR modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 5.8 Security of CBC with a random IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.9 Indistinguishability under chosen-ciphertext attack . . . . . . . . . . . . . . . . . . . 127 5.10 Example chosen-ciphertext attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 5.11 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 5.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

6 Hash Functions

139

6.1 The hash function SHA1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 6.2 Collision-resistant hash functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 6.3 Collision-finding attacks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 6.4 One-wayness of collision-resistant hash functions . . . . . . . . . . . . . . . . . . . . 147 6.5 The MD transform . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

7 Message Authentication

155

7.1 The setting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 7.2 Privacy does not imply authenticity . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 7.3 Syntax for message authentication . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 7.4 Definitions of security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 7.5 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 7.6 The PRF-as-a-MAC paradigm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 7.7 The CBC MAC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 7.8 The universal-hashing approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 7.9 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

8 Authenticated Encryption

177

9 Computational Number Theory

179

9.1 The basic groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179 9.2 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 9.3 Cyclic groups and generators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 186 9.4 Squares and non-squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190 9.5 Groups of prime order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195 9.6 Historical Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196 9.7 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

CONTENTS

5

10 Number-Theoretic Primitives

197

10.1 Discrete logarithm related problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 197 10.2 The choice of group . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201 10.3 The RSA system . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204 10.4 Historical notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

10.5 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

11 Asymmetric Encryption

211

11.1 Asymmetric encryption schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 11.2 Notions of security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 11.3 One encryption query or many? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 11.4 Hybrid encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 11.5 El Gamal scheme and its variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

12 Digital signatures

237

12.1 Digital signature schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 12.2 A notion of security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 238 12.3 RSA based signatures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

13 Authenticated Key Exchange

257

14 The Asymptotic Approach

259

15 Interactive Proofs and Zero Knowledge

261

15.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 15.2 Interactive functions and the accepting probability . . . . . . . . . . . . . . . . . . . 265 15.3 Proofs of language-membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 15.4 NP proof-systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 271 15.5 Exercises and Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

A The Birthday Problem

273

B Information-Theoretic Security

275

6

CONTENTS

Chapter 1

Introduction

Historically, cryptography arose as a means to enable parties to maintain privacy of the information they send to each other, even in the presence of an adversary with access to the communication channel. While providing privacy remains a central goal, the field has expandeded to encompass many others, including not just other goals of communication security, such as guaranteeing integrity and authenticity of communications, but many more sophisticated and fascinating goals.

Once largely the domain of the military, cryptography is now in widespread use, and you are likely to have used it even if you don't know it. When you shop on the Internet, for example to buy a book at , cryptography is used to ensure privacy of your credit card number as it travels from you to the shop's server. Or, in electronic banking, cryptography is used to ensure that your checks cannot be forged.

Cryptography has been used almost since writing was invented. For the larger part of its history, cryptography remained an art, a game of ad hoc designs and attacks. Although the field retains some of this flavor, the last twenty-five years have brought in something new. The art of cryptography has now been supplemented with a legitimate science. In this course we shall focus on that science, which is modern cryptography.

Modern cryptography is a remarkable discipline. It is a cornerstone of computer and communications security, with end products that are imminently practical. Yet its study touches on branches of mathematics that may have been considered esoteric, and it brings together fields like number theory, computational-complexity theory, and probabiltity theory. This course is your invitation to this fascinating field.

1.1 Goals and settings

Modern cryptography addresses a wide range of problems. But the most basic problem remains the classical one of ensuring security of communication across an insecure medium. To describe it, let's introduce the first two members of our cast of characters: our sender, S, and our receiver, R. (Sometimes people call these characters Alice, A, and Bob, B. Alice and Bob figure in many works on cryptography. But we're going to want the letter A for someone else, anyway.) The sender and receiver want to communicate with each other.

7

8

INTRODUCTION

xx

S

xx

A

xx

R

Figure 1.1: Several cryptographic goals aim to imitate some aspect of an ideal channel connecting a sender S to a receiver R.

The ideal channel. Imagine our two parties are provided with a dedicated, untappable, impenetrable pipe or tube into which the sender can whisper a message and the receiver will hear it. Nobody else can look inside the pipe or change what's there. This pipe provides the perfect medium, available only to the sender and receiver, as though they were alone in the world. It is an "ideal" communication channel from the security point of view. See Fig. 1.1.

Unfortunately, in real life, there are no ideal channels connecting the pairs of parties that might like to communicate with each other. Usually such parties are communicating over some public network like the Internet.

The most basic goal of cryptography is to provide such parties with a means to imbue their communications with security properties akin to those provided by the ideal channel.

At this point we should introduce the third member of our cast. This is our adversary, denoted A. An adversary models the source of all possible threats. We imagine the adversary as having access to the network and wanting to compromise the security of the parties communications in some way.

Not all aspects of an ideal channel can be emulated. Instead, cryptographers distill a few central security goals and try to achieve them. The first such goal is privacy. Providing privacy means hiding the content of a transmission from the adversary. The second goal is authenticity or integrity. We want the receiver, upon receiving a communication pertaining to be from the sender, to have a way of assuring itself that it really did originate with the sender, and was not sent by the adversary, or modified en route from the sender to the receiver.

Protocols. In order to achieve security goals such as privacy or authenticity, cryptography supplies the sender and receiver with a protocol. A protocol is just a collection of programs (equivalently, algorithms, software), one for each party involved. In our case, there would be some program for the sender to run, and another for the receiver to run. The sender's program tells her how to package, or encapsulate, her data for transmission. The receiver's program tells him how to decapsulate the received package to recover the data together possibly with associated information telling her whether or not to regard it as authentic. Both programs are a function of some cryptographic keys as we discuss next.

Trust models. It is not hard to convince yourself that in order to communicate securely, there must be something that a party knows, or can do, that the adversary does not know, or cannot do. There has to be some "asymmetry" between the situation in which the parties finds themselves and situation in which the adversary finds itself.

The trust model specifies who, initially, has what keys. There are two central trust models: the symmetric (or shared-key) trust model and the asymmetric (or public-key) trust model. We look

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download