Cryptography: An Introduction (3rd Edition)

1 Cryptography: An Introduction (3rd Edition) Nigel SmartPreface To Third EditionThe third edition contains a number of new chapters, and various material has been movedaround. The chapter on Stream Ciphers has been split into two. One chapter now deals withthe general background and historical matters, the second chapter deals with modernconstructions based on LFSR s. The reason for this is to accomodate a major new sectionon the Lorenz cipher and how it was broken. This compliments the earlier section on thebreaking of the Enigma machine. I have also added a brief discussion of the A5/1 cipher,and added some more diagrams to the discussion on modern stream ciphers.

2 Because CTR mode is becoming more used, both by itself and as part of more complexmodes which perform full authenticated encryption. Thus it is important that studentsare exposed to this mode. Ihavereorderedvariouschaptersandintroduc edanewpartonprotocols,inwhichwecover secret sharing, oblvious transfer and multi-party computation. This compliments thetopics from the previous edition of commitment schemes and zero-knowledge protocols,which are retained a moved around a bit. Thus the second edition s Part 3 has now beensplit into two parts, the material on zero-knowledge proofs has now been moved to Part 5and this has been extended to include other topics, such as oblivious transfer and securemulti-party computation.

3 The new chapter on secret sharing contains a complete description of how to recombineshares in the Shamir secret-sharing method in the presence of malicious adversaries. Toour knowledge this is not presented in any other elementary textbook, although it doesoccur in some lecture notes available on the internet. We also present an overview ofShoup s method for obtaining threshold RSA signatures. Asmallsectiondetailingthelinkagebetweenz ero-knowledgeandthecomplexityclassNPhas been reason for including extra sections etc, is that we use this text in our courses at Bristol, and sowhen we update our lecture notes I also update these notes.

4 In addition at various points studentsdo projects with us, a number of recent projects have been on multi-party computation and hencethese students have found a set of notes useful in starting their projects. We have also thanks for aspects of the third edition go to Dan Bernstein and Ivan Damg ard, whowere patient in explaining a number of issues to me for inclusion in the new sections. Also thanksto Endre Bangerter, Jiun-Ming Chen, Ed Geraghty, Thomas Johansson, Georgios Kafanas, ParimalKumar, David Rankin, Berry Schoenmakers, S. Venkataraman, and Steve Williams for providingcomments, spotting typos and feedback on earlier drafts and preface to the second edition follows:3 Preface To Second EditionThe first edition of this book was published by McGraw-Hill.

5 they did not sell enough towarrant a second edition , mainly because they did not think it worth while to allow people inNorth America to buy it. Hence, the copyright has returned to me and so I am making it availablefor free via the this second edition I have taken the opportunity to correct the errors in the first edition , anumber of which were introduced by the typesetters. I have also used a more pleasing font to theeye (so for example ayin a displayed equation no longer looks somewhat like a Greek letter ). Ihave also removed parts which I was not really happy with, hence out have gone all exercises andJava examples Themajorchangesaredetailed below: The section on the Enigma machine has been extended to a full chapter.

6 The material on hash functions and message authentication codes has now been placed inaseperatechapterandextendedsomewhat. The material on stream ciphers has also been extracted into a seperate chapter and beenslightly extended, mainly with more examples. The sections on zero-knowledge proofs have been expanded and more examples have beenadded. The previous treatment was slightly uneven and so now a set of examples ofincreasing difficulty are introduced until one gets to the protocol needed in the votingscheme which follows. A new chapter on the KEM/DEM method of constructing hybrid ciphers.

7 The chapterdiscusses RSA-KEM and the discussion on DHIES has been moved here and now uses theGap-Diffie Hellman assumption rather than the weird assumption used in the original. Minor notational updates are as follows: Permutations are now composed left to right, operate on elements from the right . This makes certain things in the sections onthe Enigma machine easier on the may ask why does one need yet another book on cryptography? There are already plentyof books which either give a rapid Introduction to all areas, like that of Schneier, or one whichgives an encyclopedic overview, like theHandbook of Applied Cryptography(hereafter calledHAC).

8 However, neither of these books is suitable for an undergraduate course. In addition, the approachto engineering public key algorithms has changed remarkably over the last few years, with the adventof provable security . No longer does a cryptographer informally argue why his new algorithm issecure, there is now a framework within which one can demonstrate the security relative to otherwell-studied courses are now taught at all major universities, sometimes these are taught inthe context of a Mathematics degree, sometimes in the context of a Computer Science degree andsometimes in the context of an Electrical Engineering degree.

9 Indeed, a single course often needsto meet the requirements of all three types of students, plus maybe some from other subjects whoare taking the course as an open unit . The backgrounds and needs of these students are different,some will require a quick overview of the current algorithms in use, whilst others will want anintroduction to the current research directions. Hence, there seems to be a need for a textbook56 PREFACETOSECONDEDITION which starts from a low level and builds confidence in students until they are able to read, forexampleHACwithout any background I assume is what one could expect of a third or fourth year undergraduate incomputer science.

10 One can assume that such students have met the basics of discrete mathematics(modular arithmetic) and a little probability before. In addition, they would have at some pointdone (but probably forgotten) elementary calculus. Not that one needs calculus for cryptography,but the ability to happily deal with equations and symbols is certainly helpful. Apart from that Iintroduce everything needed from scratch. For those students who wish to dig into the mathematicsa little more, or who need some further reading, I have provided an appendix (Appendix A) whichcovers most of the basic algebra and notation needed to cope with modern public key is quite common for computer science courses not to include much of complexity theory orformal methods.