MATHEMATICAL CRYPTOLOGY - TUT

1 MATHEMATICAL CRYPTOLOGYK eijo Ruohonen(Translation by Jussi Kangas and Paul Coughlan)2014 Contents1I INTRODUCTION3II NUMBER THEORY: PART , Factors, of Integers in Different Common Divisor and Least Common Calculus or Modular Class Rings and Prime Arithmetic Operations for Large Integers14 Addition and subtraction14 Multiplication16 Division18 Powers19 Integral root21 Generating a random integer23 III SOME CLASSICAL CRYPTOSYSTEMS PERMUTATION. AFFINE-HILL. VIGEN ALGEBRA: RINGS AND and Fields34V Bytes (SubBytes) Rows (ShiftRows) Columns (MixColumns) Round Keys (AddRoundKey) the Variant of s Modes of AESiii42VI PUBLIC-KEY Theory of and Fall of Knapsack Suitable for Public-Key Encryption48 VII NUMBER THEORY: PART s Function and Euler s and Discrete Remainder and Generating of Square Random LLL Algorithm65 VIII and and Partial Information about by LLL Algorithm74IX ALGEBRA: Curves85X ELGAMAL.

2 DIFFIE s Hellman Based on Elliptic and up the Using LLL Algorithm94 XII HASH FUNCTIONS AND van Heijst Pfitzmann Hashiii100 XIII s Attack Against Signature103 XIV TRANSFERRING SECRET and Random Data Proofs111XV QUANTUM Registers and Quantum s s Search Key-Exchange122 Appendix: Cryptanalysis127 References130 IndexForewordThese lecture notes were translated from the Finnish lecture notes for the TUT course Mate-maattinen kryptologia . The laborious bulk translation was taken care of by the students JussiKangas (visiting from the University of Tampere) and Paul Coughlan (visiting from the Univer-sity of Dublin, Trinity College).

3 I want to thank the translation team for their notes form the base text for the course MAT-52606 MATHEMATICAL CRYPTOLOGY . Theycontain the central MATHEMATICAL background needed for understanding modern data encryptionmethods, and introduce applications in cryptography and various the union of mathematics and CRYPTOLOGY is old, it really came to the fore in con-nection with the powerful encrypting methods used during the Second World War and theirsubsequent breaking. Being generally interesting, the story is told in several (partly) fictivebooks meant for the general area got a whole new speed in the 1970 s when the completely open, fast and strongcomputerized cryptosystem DES went live, and the revolutionary public-key paradigm this, development of CRYPTOLOGY and also the mathematics needed by it1An example is Neal Stephenson s Levy s bookCrypto.

4 Secrecy and Privacy in the New Code Wargives a bit romanticized description ofthe birth of public-key mostly certain fields of number theory and algebra has beenremarkably fast. It is no exag-geration to say that the recent popularity of number theory and algebra is expressly because ofcryptology. The theory of computational complexity, whichbelongs to the field of theoreticalcomputer science, is often mentioned in this context, but inall fairness it must be said that itreally has no such big importance in CRYPTOLOGY . Indeed, suitable MATHEMATICAL problems foruse in cryptography are those that have been studied by top mathematicians for so long that onlyresults that are extremely hard to prove still remain open.

5 Breaking the encryption then requiressome huge theoretical breakthrough. Such problems can be found in abundance especially innumber theory and discrete of number theory and algebra, and the related algorithms, are presented in their ownchapters, suitably divided into parts. Classifying problems of number theory and algebra intocomputationally easy and hard is essential here. The former are needed in encrypting anddecrypting and also in setting up cryptosystems, the latterguarantee strength of encryption. Thefledgling quantum cryptography is briefly introduced together with its a few classical cryptosystems in which also DES and thenewer AES must be in-cluded according to their description are introduced, much more information about these canbe found in the references BAUER, MOLLINand SALOMAA.

6 The main concern here is inmodern public-key methods. This really is not an indicationof the old-type systems not beinguseful. Although the relevance of old classical methods vanished quite rapidly3, newer methodsof classical type are widely used and have a very important role in fast mass-encryption. Alsostream encrypting, so important in many applications, is not treated here. The time available fora single course is limited. A whole different chapter would be correct implementation and useof cryptosystems, which in a mathematics course such as thiscannot really be touched very powerful cryptosystem can be made inefficient withbad implementation and Ruohonen3As an example of this it may be mentioned that the US Army field manual FM 34-40-2:Basic Cryptanalysisispublicly available in the web.

7 The book BAUER also contains material quite recently (and possibly still!) classifiedas great book on this topic is Bruce Schneier sSecrets and Lies. Digital Security in a Networked 1 Introduction Cryptography involves one genius trying towork out what another genius has done. (MAIJIA:Decoded)Encryptionof a message means the information in it is hidden so that anyone who s reading(or listening to) the message, can t understand any of it unless he/she canbreakthe original plain message is calledplaintextand an encrypted encryptingyou need to have a so-calledkey, a usually quite complicated parameter that you can use tochange the encryption.

8 If the encrypting procedure remainsunchanged for a long time, theprobability of breaking the encryption will in practise increase substantially. Naturally differentusers need to have their own keys, receiver of the messagedecryptsit, for which he/she needs to have his/her own the encrypting key and decrypting key are very valuablefor an eavesdropper, using theencrypting key he/she can send encrypted fake messages and using the decrypting key he/shecan decrypt messages not meant to him/her. In symmetric cryptosystems both the encryptingkey and the decrypting key are usually the encrypting procedure can encrypt a continuous stream of symbols (stream encryption)or divide it into blocks (block encryption).

9 Sometimes in block encryption the sizes of blockscan vary, but a certain maximum size of block must not be exceeded. However, usually blocksare of the same size. In what follows we shall only examine block encryption, in which case it ssufficient to consider encrypting and decrypting of an arbitrary message block, and one arbitrarymessage block may be considered as the plaintext and its encrypted version as the encryption procedure issymmetric,if the encrypting and decrypting keys are the sameor it s easy to derive one from the other. Innonsymmetricencryption the decrypting key can tbe derived from the encrypting key with any small amount of work.

10 In that case the encryptingkey can be public while the decrypting key stays classified. This kind of encryption procedureis known aspublic-key cryptography,correspondingly symmetric encrypting is calledsecret-key problem with symmetric encrypting is the secret key distribution to allparties, as keys must also be updated every now and encryption can be characterized as a so calledcryptosystemwhich is an orderedquintet(P, C, K, E, D), where Pis the finitemessage space(plaintexts). Cis the finitecryptotext space(cryptotexts). Kis the finitekey space. for every keyk Kthere is anencrypting functionek Eand adecrypting functiondk called theencrypting function spacewhich includes every possible encryptingfunction andDis called thedecrypting function spacewhich includes every possibledecrypting 1.