An Introduction to Cryptography - uni-kl.de

1 An Introduction to CryptographyMohamed Barakat, Christian Eder, Timo HankeSeptember 20, 2018 PrefaceSecond EditionLecture notes of a class given during the summer term 2017 at the University of Kaiserslautern. Thenotes are based on lecture notes byMohamed BarakatandTimo Hanke[BH12](see also below).Other good sources and books are, for example,[Buc04,Sch95,MVO96].Many thanks to Raul Epure for proofreading and suggestions to improve the lecture EditionThese lecture notes are based on the course Kryptographie given byTimo Hankeat RWTH AachenUniversity in the summer semester of 2010. They were amended and extended by several topics,as well as translated into English, byMohamed Barakatfor his course Cryptography at TU Kaiser-slautern in the winter semester of 2010/11.

2 Besides the literature given in the bibliography section,our sources include lectures notes of courses held byMichael Cuntz,Florian He ,Gerhard Hi andJ rgen M ller. We would like to thank them Barakat would also like to thank the audience of the course for their helpful remarksand questions. Special thanks toHenning Koppfor his numerous improvements suggestions. Alsothanks toJochen Kallwho helped locating further errors and Bergerhelped me withsubtle formatting issues. Many Edition.. iFirst Edition.. iContentsii1 Introduction12 Basic Quick & Dirty Introduction to Complexity Theory.. Underlying Structures.

3 Investigating Security Models.. 113 Modes of Block Ciphers.. Modes of Block Ciphers.. Stream Ciphers.. A Short Review of Historical Ciphers.. 254 Information A Short Introduction to Probability Theory.. Perfect Secrecy.. Entropy.. 355 Pseudorandom Introduction .. Linear recurrence equations and pseudorandom bit generators.. Finite fields.. Statistical tests.. Cryptographically secure pseudorandom bit generators.. 666 Modern Symmetric Block Feistel cipher.. Data Encryption Standard (DES).. Advanced Encryption Standard (AES).. 747 Candidates of One-Way Complexity classes.

4 Squaring modulon.. Quadratic residues.. Square roots.. One-way functions.. Trapdoors.. TheBlum-Goldwasserconstruction.. 858 Public Key .. TheRabincryptosystem.. Security models.. 939 Primality Probabilistic primality tests.. Deterministic primality tests.. 10010 Integer sp 1 method.. s method.. s method.. s method.. The quadratic sieve.. 10711 Elliptic The projective space.. The group structure(E,+).. Elliptic curves over finite fields.. s factorization method.. Elliptic curves Cryptography (ECC).. 12612 Attacks on the discrete logarithm Specific attacks.

5 General attacks.. 13013 Digital Basic Definitions & Notations.. Signatures usingOWFwith trapdoors.. Hash functions.. Signatures usingOWFwithout trapdoors.. 135A Some Real functions.. 137 Bibliography138 Chapter 1 IntroductionCryptology consists of two branches:Cryptographyis the area of constructing cryptographic the area of breaking cryptographic is a field of computer science and mathematics that focusses on techniques for securecommunication between two parties (Alice & Bob) while a third-party (Eve1or Mallory2) is present(see ). This is based on methods like encryption, decryption, signing, generating ofpseudo random numbers, (p,k)=cplaintextpBobDecryptionD(c,k )=pplaintextpinsecure channelattackseavesdropssecurechannelsec urechannelFigure :A basic idea for secure communication1 Usually Eve stands for Mallory stands for a man-in-the-middle 1.

6 INTRODUCTIONThe four ground principles of Cryptography areConfidentialityDefines a set of rules that limits access or adds restriction on certain IntegrityTakes care of the consistency and accuracy of data during its entire the truth of an attribute of a datum that is claimed to be true by the inability of an author of a statement resp. a piece of information todeny there are in general two different schemes: On the one hand, there aresymmetricschemes, where both, Alice and Bob, need to have the same key in order to encrypt their com-munication. For this, they have to securely exchange the key initially. On the other hand, sinceDiffie and Hellman s key exchange idea from 1976 (see also (3) and Chapter8) therealso exists the concept ofasymmetric schemeswhere Alice and Bob both have a private and a publickey.

7 The public key can be shared with anyone, so Bob can use it to encrypt a message for only Alice, with the corresponding private key, can decrypt the encrypted message from this lecture we will discover several well-known cryptographic structures likeRSA(Rivest-Shamir-Adleman cryptosystem),DES(Data Encryption Standard),AES(Advanced EncryptionStandard),ECC(Elliptic Curve Cryptography ), and many more. All these structures have twomain is the security of the structure itself, based on mathematics. There is a standardiza-tion process for cryptosystems based on theoretical research in mathematics and complexitytheory. Here our focus will lay in this we have the implementation of the structures in devices, ,TLSin your webbrowser orGPGfor signed resp.

8 Encrypted emails. These implementations should not di-verge from the theoretical standards, but must still be very fast and convenient for the is often this mismatch between these requirements that leads to practical attacks of theoreticallysecure systems, [Wik16b,Wik16c,Wik16e].Before we start defining the basic notation let us motivate the following with some historicallyknown cryptosystems:Example of the most famous cryptosystems goes back to Julius Ceasar:Caesar s cipherdoes thefollowing: Take the latin alphabet and apply a mappingA7!0,B7!1,..,Z7!25. Now weapply a shifting mapx7!(x+k)mod 26for some secretk2Z. For example,ATTACK maps toCVVCEM fork=2.

9 This describes theencryption process. The decryption is applied via the mapy7!(y k)mod 26with the samek. Clearly, both parties need to knowkin advance. Problems with this cipher:Same letters are mapped to the same shifted letters, each language has its typical distribu-tion of letters, used much more frequently in the English language thanK. Besidesinvestigating only single letters one can also check for letter combinations of length 2-3, generalization of Caesar s cipher isVigen re s cipher: It was invented several times, nowa-days the reference goes back to the French cryptographer Blaise de Vigen re. The maindifference is that instead of using only onek2Z, we now usek2 Znfor somen2N.

10 Forexample, let the secret be represented by the wordSECRET. We again map the letters fromthe alphabet to corresponding numbers modulo26:k=(18,4,2,17,4,19)2(Z=26Z) we apply for each letter the Caesar cipher to our textATTACK:A7!ST7!XT7!VA7!RC7!GK7!CThis system is a bit harder to attack, try to find redundancies in the text like the letterEappearing on several positions. With this one can crack the length of the secret keyn. Af-terwards one can splice the text in chunks ofnletters and rather easily test all possibilitiesvia some assumptions like the text contains English words from the dictionary etc. Still notethatkhas to be known to Alice and Bob at the same 1976 Whitfield Diffie and Martin Hellman (and also Ralph Merkle) proposed an idea for se-curely exchanging keys over an insecure communication channel, nowadays known asDiffie-Hellman Key gab AbmodpFigure :Diffie-Hellman Key Exchangea)Alice and Bob agree publicly on a cyclic group, ,G=F 1.