Introduction to Cryptography.pdf-资料库

weixin_43960172-10921067-4744302543441840308.pdf-第1页.png

第1页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第2页.png

第2页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第3页.png

第3页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第4页.png

第4页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第5页.png

第5页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第6页.png

第6页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第7页.png

第7页 / 共258页

weixin_43960172-10921067-4744302543441840308.pdf-第8页.png

第8页 / 共258页

Introduction to Cryptography Sahadeo Padhye Associate Professor Department of Mathematics Motilal Nehru National Institute of Technology Allahabad, India Rajeev A. Sahu Post-Doctoral Researcher Departement d’Informatique Université Libre de Bruxelles (ULB) Brussels, Belgium Vishal Saraswat Visiting Scientist R.C. Bose Centre for Cryptology and Security Indian Statistical Institute Kolkata, India

CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 © 2018 by Taylor & Francis Group, LLC CRC Press is an imprint of Taylor & Francis Group, an Informa business Version Date: 20180524 International Standard Book Number-13: 978- 1-138-07153-7 (Hardback) Visit the Taylor & Francis Web site at http://www.taylorandfrancis.com and the CRC Press Web site at http://www.crcpress.com

Foreword Cryptography is an amazing science. It has been around for thousands of years, but took off phenomenal strides less than fifty years ago. At the crossroads of mathematics, computing, telecommunications networks and quantum physics, cryptography is nowadays a field of abundant researches and applications. Essential for the smooth running of the digital world in which we live, the learning of cryptography is therefore today a necessity for any IT specialist. It is in this context that Sahadeo Padhye, Rajeev Anand Sahu and Vishal Saraswat offer us a new textbook on cryptography of very high quality. This book is an ideal companion for any student in computer science, in mathematics or in engineering who wishes to approach cryptography in a formal, scientific and rigorous manner. The authors have succeeded in proposing a textbook that presents cryptography in depth with a great deal of clarity. This comprehensive and self-contained book introduces very clearly and iteratively all the mathematical elements necessary to understand the cryptographic tools presented afterwards. Indeed, the first five chapters will give readers the elements of algebra, number theory, probability and complexity of algorithms that will allow them to easily approach the next five chapters dedicated to the most fundamental tools of cryptography such as encryption, hash functions and digital signatures. For every discussed cryptographic aspect, the reader will find informal explanations, formal definitions of all the underlying mathematical aspects, a clear description of the cryptographic scheme itself, numerical examples and corresponding exercises. The reader will be taken on a journey from the oldest cryptographic algorithms to the most modern cryptographic schemes. From the scytale to elliptic curves cryptography. Very complete, this book also presents really clear descriptions of most of the essential algorithms needed to implement cryptographic schemes, such as the computation of inverses, of square roots, primality tests, exponentiations, factorization, discrete logarithm, etc.

Few books deal with so many different aspects of general cryptography in such a didactic and comprehensive manner. All of this makes this introductory book on cryptography by Sahadeo Padhye, Rajeev Anand Sahu and Vishal Saraswat a teaching and pedagogical tool of quality, both for students or neophytes who are discovering this exciting science and for teachers who need to set up a new course on this subject. Olivier Markowitch Brussels, December 2017

Preface In the past three decades, study and research in cryptography has been growing. ‘Cryptography’ is no longer an unknown term. In many universities students are studying cryptography in undergraduate and/or postgraduate courses, researchers are involved in exploring various useful primitives of cryptography and many people are using cryptography in their daily life, knowingly or unknowingly. Cryptography has been practiced since long, but it has attracted the attention of researchers and academicians in the last 30 years, since the elementary foundations proposed by IBM (the Data Encryption Standard) in mid 1970s, Diffie and Hellman (the key exchange protocol over the public network) in 1976 and by Rivest, Shamir and Adleman (the RSA public key cryptosystem) in 1978. The idea of cryptography is not independent of mathematics, in fact, major mathematical theories are at the core of cryptography. This book presents an introduction to the notion of cryptography and to the mathematical theories underlying the notion. This book aims at readers who have some elementary background in mathematics and are interested to learn cryptography. We have introduced basic techniques of cryptography addressing the mathematical results used to establish those techniques. In this way we achieve one of our goals, i.e. to provide mathematical structures of basic cryptographic primitives and a list of ready reference to the students of undergraduate and postgraduate with a possibility to cover major sections of their syllabus of cryptography. We have arranged the topics such that the mathematical theories have been described before being mentioned in design and/or analysis of cryptographic schemes. The book starts with an overview of cryptography which includes the goals of cryptography and cryptanalysis. In the second chapter, we have provided definitions from algebra that are essential in the formalization of various designs in later chapters. Number theory captures important results of mathematics used in cryptography. We have discussed many of these results with brief description in third chapter. Probability and random numbers are other important notions used in design and analysis of cryptographic algorithms. These theories have been covered in the fourth chapter. The fifth chapter introduces the theory of complexity, which plays important

role in measure of strength of a cryptosystem. Thus, the first five chapters provide a mathematical foundation. Hereafter, we start explaining the concepts of cryptographic constructions. The explanation begins with description of the classical cryptosystems in chapter six. The description of modern cryptographic designs starts with details of symmetric key cryptography in chapter seven where we discuss various block ciphers. The asymmetric cryptosystems (public key cryptosystems) are explained in chapter nine. We have included description of digital signature, an important primitive of public key cryptography, in an independent chapter, chapter ten. Hash function is an integral ingredient of public key cryptography, it has been covered in chapters eight to ten. Chapter 11 discusses emerging topics in cryptography. The authors thank everyone due to whom this book could have come in its current form. In particular, we are thankful to Vijay Primlani of Science Publishers CRC Press, for giving us the opportunity to publish this work. We express our special thanks to Prof. Olivier Markowitch who happily agreed to present his views about this book in the foreword. We are also grateful to Gaurav Sharma and Veronika Kuchta, postdoctoral researchers at ULB, Brussels, Belgium, for their useful suggestions during discussions. Sonika Singh and Swati Rawal, Ph.D. students of Sahadeo Padhye at MNNIT Allahabad, have extended their efforts in proofreading, we thank both of them. Last, but not least, we thank our respective wives and children for their patient and support during the writing of this book. Sahadeo Padhye Rajeev Anand Sahu Vishal Saraswat

Contents Foreword Preface 1 Overview of Cryptography 1.1 Introduction 1.2 Goals of Cryptography 1.3 Classification of Cryptosystem 1.4 Practically Useful Cryptosystem 1.4.1 Confusion and Diffusion 1.5 Cryptanalysis 1.5.1 Types of Attackers 1.5.2 Types of Attacks 1.5.3 Security Notions 2 Basic Algebra 2.1 Group 2.2 Ring 2.3 Field 2.4 Exercises 2.3.1 Finite Field 2.3.2 Field Construction 2.3.3 Field Construction using Irreducible Polynomial 2.3.4 Galois Field GF(2n) 2.3.4.1 Integer Representation of Finite Field Elements 2.3.5 Field Construction using Generator v vii 1 2 3 4 5 6 7 7 8 9 11 12 15 16 17 18 19 19 20 22 23

3 Number Theory 3.1 Prime Numbers 3.2 Cardinality of Primes 3.3 Extended Euclidean Algorithm 3.4 Congruences 3.4.1 Solving Linear Congruence in Zn 3.4.2 Chinese Remainder Theorem (CRT) 3.5 Integer Factorization Problem 3.5.1 Trial Division Method 3.5.2 Fermat’s Method 3.5.3 Pollard’s p – 1 Method 3.5.4 Pollard’s Rho Method 3.5.5 Quadratic Sieve 3.5.6 Number Field Sieve 3.6 Primality Testing 3.6.1 Sieve of Eratosthenes 3.6.2 Divisibility Algorithm 3.6.3 AKS Algorithm 3.6.4 Fermat Test 3.6.5 Miller-Rabin Algorithm 3.7 Quadratic Congruence 3.7.1 Quadratic Residue or Non-Residue 3.7.2 Legendre Symbol and Jacobi Symbol 3.8 Exponentiation and Logarithm 3.8.1 Square and Multiply Method 3.9 Discrete Logarithm Problem 3.9.1 Shank’s Baby-Step Giant-Step Algorithm 3.9.2 Pollard’s Rho Algorithm 3.9.3 Pohlig-Hellman Algorithm Index Calculus Algorithm 3.9.4 3.10 Exercises 4 Probability and Perfect Secrecy 4.1 Basic Concept of Probability 4.2 Birthday Paradox 4.3 Perfect Secrecy 4.4 Vernam One-Time Pad 4.5 Random Number Generation 4.6 Pseudo-random Number Generator 4.7 Exercises 25 26 27 29 32 33 34 35 35 36 37 39 40 41 41 41 42 42 43 43 45 45 46 50 50 51 52 53 56 58 59 61 62 64 66 68 69 69 70

资料库

Introduction to Cryptography.pdf

相关推荐

课程资源

热门标签

最新资料