[PDF] Cours de Cryptographie

View - Download Cours de Cryptographie

Previous PDF

Next PDF

Cryptography

Lecture Notes from CS276, Spring 2009

Luca Trevisan

Stanford University

Foreword

These are scribed notes from a graduate course on Cryptography oered at the University of California, Berkeley, in the Spring of 2009. The notes have been only minimally edited, and there may be several errors and imprecisions. We use a denition of security against a chosen cyphertext attack (CCA-security) that is weaker than the standard one, and that allows attacks that are forbidden by the standard denition. The weaker denition that we use here, however, is much easier to dene and reason about. I wish to thank the students who attended this course for their enthusiasm and hard work. Thanks to Anand Bhaskar, Siu-Man Chan, Siu-On Chan, Alexandra Constantin, James Cook, Anindya De, Milosh Drezgich, Matt Finifter, Ian Haken, Steve Hanna, Nick Jalbert, Manohar Jonnalagedda, Mark Landry, Anupam Prakash, Bharath Ramsundar, Jonah Sher- man, Cynthia Sturton, Madhur Tulsiani, Guoming Wang, and Joel Weinberger for scribing some of the notes. While oering this course and writing these notes, I was supported by the National Science Foundation, under grant CCF 0729137. Any opinions, ndings and conclusions or recom- mendations expressed in these notes are my own and do not necessarily re ect the views of the National Science Foundation.

San Francisco, May 19, 2011.

Luca Trevisanc

2011 by Luca Trevisan

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivs

3.0 Unported License. To view a copy of this license, visithttp://creativecommons.org/

licenses/by-nc-nd/3.0/or send a letter to Creative Commons, 171 Second Street, Suite

300, San Francisco, California, 94105, USA.

i ii

Contents

Forewordi

1 Introduction

1

1.1 Alice, Bob, Eve, and the others

2

1.2 The Pre-history of Encryption

2

1.3 Perfect Security and One-Time Pad

5

2 Notions of Security

7

2.1 Semantic Security

7

2.2 Security for Multiple Encryptions: Plain Version

12

2.3 Security against Chosen Plaintext Attack

13

3 Pseudorandom Generators

15

3.1 Pseudorandom Generators And One-Time Encryption

15

3.2 Description of RC4

18

4 Encryption Using Pseudorandom Functions

21

4.1 Pseudorandom Functions

21

4.2 Encryption Using Pseudorandom Functions

22

4.3 The Randomized Counter Mode

24

5 Encryption Using Pseudorandom Permutations

27

5.1 Pseudorandom Permutations

27

5.1.1 Some Motivation

27

5.1.2 Denition

27

5.2 The AES Pseudorandom Permutation

28

5.3 Encryption Using Pseudorandom Permutations

29
iii ivCONTENTS

5.3.1 ECB Mode

29

5.3.2 CBC Mode

29

6 Authentication

31

6.1 Message Authentication

31

6.2 Construction for Short Messages

32

6.3 Construction for Messages of Arbitrary Length

33

7 CCA-Secure Encryption

37

7.1 CBC-MAC

37

7.2 Combining MAC and Encryption

38

8 Collision-Resistant Hash Functions

43

8.1 Combining Encryption and Authentication

43

8.1.1 Encrypt-Then-Authenticate

43

8.1.2 Encrypt-And-Authenticate

44

8.1.3 Authenticate-Then-Encrypt

44

8.2 Cryptographic Hash Functions

45

8.2.1 Denition and Birthday Attack

45

8.2.2 The Merkle-Damgard Transform

47

8.3 Hash Functions and Authentication

49

9 One-Way Functions and Hardcore Predicates

51

9.1 One-way Functions and One-way Permutations

52

9.2 A Preview of What is Ahead

53

9.3 Hard-Core Predicate

54

9.4 The Goldreich-Levin Theorem

54

9.5 The Goldreich-Levin Algorithm

59

9.6 References

62

10 PRGs from One-Way Permutations

63

10.1 Pseudorandom Generators from One-Way Permutations

63

11 Pseudorandom Functions from PRGs

69

11.1 Pseudorandom generators evaluated on independent seeds

69

CONTENTSv

11.2 Construction of Pseudorandom Functions

70

11.2.1 Considering a tree of small depth

71

11.2.2 Proving the security of the GGM construction

72

12 Pseudorandom Permutations from PRFs

75

12.1 Pseudorandom Permutations

75

12.2 Feistel Permutations

76

12.3 The Luby-Racko Construction

77

12.4 Analysis of the Luby-Racko Construction

78

13 Public-key Encryption

85
quotesdbs_dbs2.pdfusesText_2

[PDF] applied cryptography

[PDF] decors chretiens de sainte sophie

[PDF] basilique sainte-sophie vikidia

[PDF] frise chronologique de sainte sophie

[PDF] chapelle du palais d'aix

[PDF] fonction dune basilique

[PDF] plan de la basilique sainte sophie

[PDF] sainte sophie plan

[PDF] conseiller d'animation sportive salaire

[PDF] fiches ressources eps lycée professionnel

[PDF] conseiller technique sportif salaire

[PDF] programme eps lycée professionnel 2016

[PDF] conseiller d'animation sportive fiche métier

[PDF] conseiller technique sportif fiche métier

[PDF] programme eps lycée 2010