Universiteit Leiden Mathematisch Instituut
Getaltheorie en Cryptografie Derde en hogerejaars Wiskunde -  Wordt niet gegeven in 2003-2004

Docent:	Dr. J.-H. Evertse Kamer 228,  tel. 071-5277128 email:    evertse@math.leidenuniv.nl
Werkvorm:	Hoorcollege
Voorkennis:	Het college is geschikt voor beginnende derdejaarsstudenten wiskunde. In het bijzonder wordt de inhoud van de Leidse colleges Algebra 1, Algebra 2 (elementaire theorie van groepen en ringen) bekend verondersteld. Op het college wordt gebruik gemaakt van eindige lichamen. Wanneer dit nodig is worden de benodigde feiten over eindige lichamen kort herhaald. Kennis van het college Getaltheorie (wordt gegeven in voorjaar 2004 door J.-H. Evertse) is nuttig maar niet noodzakelijk.
Aantal studiepunten:	10 (ECTS-systeem);  7 (oud systeem)
Opmerkingen:	Dit college wordt niet gegeven in het cursusjaar 2003/04. Studenten die daarvoor belangstelling hebben kunnen eventueel zelfstandig de stof bestuderen en huiswerkopgaven inleveren. Bij de docent J.-H. Evertse is een dictaat verkrijgbaar. De huiswerkopgaven kunnen van deze webpagina worden gedownload. De hierondergenoemde tentamenregeling blijft daarbij van kracht. Het college Getaltheorie en Cryptografie is goed te combineren met het college Getaltheorie van Prof. R. Tijdeman dat wel wordt gegeven in 2003-04. Het college wordt aanbevolen voor een afstudeerproject getaltheorie.
Tentamen- regeling:	Het tentamen bestaat voor de helft uit het vier keer (ongeveer om de drie weken) inleveren van opgaven en voor de helft uit een mondeling tentamen waarin op de theorie wordt ingegaan. Zowel het resultaat van de opgaven als van het mondeling tentamen moet voldoende zijn. Het eindcijfer is het gemiddelde van het cijfer voor de opgaven en het cijfer voor het mondeling tentamen. Het mondeling tentamen duurt ongeveer 1 uur. Voor het mondeling tentamen moet uiterlijk een week van te voren een afspraak worden gemaakt met de docent. Op het mondeling tentamen zal de nadruk liggen op theorie (definities, stellingen en bewijzen). Over de volgende hoofdstukken zal worden getentamineerd: 1,3 (alleen definities+Vernam one-time pad; over Rijndael wordt niet gevraagd), 4 (alleen de definities en stellingen), 5,6,7,8,9,11,12. De resultaten van hoofdstuk 2 (eindige lichamen) worden niet expliciet gevraagd maar zullen wel in toepassingen in de andere hoofdstukken bekend worden verondersteld.
Huiswerk- opgaven: (kunnen nog worden ingeleverd)	Deel 1:   postscript-file      pdf-file Deel 2:   postscript-file      pdf-file Deel 3:   postscript-file      pdf-file Deel 4:   postscript-file      pdf-file NORMERING VAN DE HUISWERKOPGAVEN: Deel 1: 1a) 5, 1b) 5; 2a) 5, 2b1) 5, 2b2) 5, 2b3) 5; 3a) 5, 3b 5), 3c 10); 4a) 3, 4b) 5 4c) 2; 5a) 5, 5b) 5, 5c) 10, 5d) 10 Totaal: 90; Cijfer=(aantal punten)/9 Deel 2: 6a) 3, 6b) 7; 7a) 5, 7b) 5; 8a) 5, 8b) 5; 9a) 5, 9b) 5; 10a) 5, 10b) 5; 11) 5; 12a) 5, 12b) 5, 12c) 5 Totaal: 70; Cijfer=(aantal punten)/7 Deel 3: 13a) 2, 13b) 4, 13c) 4; 14a) 5, 14b) 5 14c) 5; 15a) 6, 15b) 4; 16a) 3, 16b) 3, 16c) 4, 16d) 5; 17a) 5, 17b) 5, 17c) 5; 18a) 5, 18b) 5, 18c) 5 Totaal: 90; Cijfer=(aantal punten)/9 Deel 4: 19a) 5, 19b) 5, 19c) 10; 20a) 5, 20b) 5, 20c) 5; 21a) 5, 21b) 5, 21c) 10; 22) 15; 23a) 10; 23b) 10 Totaal: 90; Cijfer=(aantal punten)/9
Literatuur:	Op het college wordt een dictaat uitgedeeld. Verder wordt aanbevolen: N. Koblitz, A course in number theory and cryptography, Springer Verlag 1987 (elementaire inleiding tot getaltheorie en toepassingen daarvan in de cryptografie, met veel aandacht voor elliptische krommen) H.C.A. van Tilborg, An introduction to cryptology, Kluwer 1988 (elementaire inleiding tot cryptografie, met veel aandacht voor conventionele cryptosystemen) H. Cohen, A Course in Computational Algebraic Number Theory, Springer Verlag 1993 (een geavanceerder boek met allerlei getaltheoretische algoritmen waaronder priemtesten en factorisatiemethoden). A.J. Menezes, P.C. van Oorschot, S.A. Vanstone, Handbook of applied cryptography, CRC Press, 1996 (een dik boek van ruim 800 pagina's waarin erg uitgebreid wordt ingegaan op alle praktische aspecten van cryptografie en waarin de meeste van de in omloop zijnde cryptografische systemen worden beschreven; verder worden de definities van alle in de cryptografie in omloop zijnde begrippen gegeven; wiskundige bewijzen worden niet gegeven; erg uitgebreide bibliografie; op de webpagina van het boek staan instructies hoe het boek gratis kan worden gedownload) De volgende artikelen hebben betrekking op de inhoud van het college: [1]  W. Diffie, M.E. Hellman, New directions in cryptography, IEEE Transactions in Information Theory, vol.IT-22, 1976, 644-654. [2]  R.L. Rivest, A. Shamir, L. Adleman, A method for obtaining digital signatures and public key cryptosystems, Communications of the ACM, vol. 21, 1978, 120-126. [3]  The Advanced Encrytion Standard (Rijndael)
Gerelateerde webpagina's	2000 Mathematics Subject Classification (Classificatie van alle wiskunde-gebieden; cryptografie valt onder 94A en getaltheorie onder 11) MathSciNet (hierop kunnen samenvattingen van in de literatuur verschenen artikelen worden geraadpleegd; alleen toegankelijk vanuit het netwerk van het Mathematisch Instituut) Overview of cryptography (Gary C. Kessler) The prime pages (informatie over priemgetallen en priemtesten) Factorization records (informatie over de grootste tot dusver gefactoriseerde getallen) EIDMA Cryptography working group Dictaten over getaltheorie en cryptografie kunnen worden gedownload van de websites van Ed Schaefer (in het Engels) en van Wolfgang Ruppert (in het Duits).
Inhoud:	Op het college worden (onder voorbehoud, afhankelijk van de beschikbare tijd) de volgende onderwerpen behandeld: conventionele cryptosystemen (o.m. Vernam one-time pad en Rijndael), eenvoudige algoritmen met afschatting van rekentijd, oplossen van kwadratische congruenties, het RSA-systeem, priemtesten, cryptosystemen gebaseerd op discrete logaritmen (o.m. het sleuteldistributiesysteem van Diffie en Hellman, het public key cryptosysteem en het digitale handtekeningensysteem van El-Gamal) en, afhankelijk van de tijd, factorisatiemethoden en cryptografische protocollen of cryptosystemen gebaseerd op elliptische krommen. In de cryptografie worden wiskundige methoden bedacht die de veiligheid van elektronisch gegevensverkeer moeten vergroten (bijvoorbeeld veilige cryptosystemen waarmee gegevens kunnen worden vercijferd en digitale handtekeningensystemen waarmee elektronische boodschappen van een onvervalsbare digitale handtekening kunnen worden voorzien). Tot in het midden van de jaren 1970 bestonden er alleen zogenaamde conventionele cryptosystemen waarin twee partijen A en B samen een geheime sleutel moeten uitwisselen om de boodschappen die ze naar elkaar willen sturen te kunnen vercijferen. In 1976 suggereerden Diffie en Hellman (zie hun beroemde artikel [1]) het concept van een zogenaamd public key cryptosysteem, waarin iedere gebruiker een eigen vercijfersleutel heeft die hij openbaar maakt in een publiek bestand en een eigen ontcijfersleutel die hij geheim houdt. Wanneer A een boodschap naar B wil sturen zoekt hij B's vercijfersleutel op in het publieke bestand, vercijfert daarmee de boodschap, en stuurt die naar B. B kan dan met zijn alleen aan hemzelf bekende ontcijfersleutel de door A verstuurde boodschap terugvinden. Diffie en Hellman bedachten wel het concept van een public key cryptosysteem, maar wisten geen goede methode om een dergelijk systeem te maken. in 1978 publiceerden Rivest, Shamir en Adleman [2] een public key systeem dat nu als het RSA-systeem bekend staat. Dit systeem kan ook worden gebruikt om boodschappen van een digitale handtekening te voorzien. In het RSA-systeem kiest elke gebruiker twee grote priemgetallen p en q van ongeveer 150 cijfers die hij geheim houdt en maakt hun product n=pq openbaar. Het RSA-systeem dankt zijn bruikbaarheid en veiligheid aan het feit dat het enerzijds betrekkelijk weinig rekentijd kost om priemgetallen van 150 cijfers te vinden, terwijl het anderzijds (met de huidige stand van zaken) ondoenlijk is om getallen van 300 cijfers in factoren te ontbinden. In het college wordt daarom ook aandacht besteed aan priemtesten en (afhankelijk van de tijd) factorisatiemethoden. Na het RSA-systeem zijn nog allerlei andere public key cryptosystemen en digitale handtekeningensystemen bedacht die gebaseerd zijn op getaltheorie. Op het college komen ook cryptosystemen ter sprake die gebaseerd zijn op het discrete logaritme-probleem voor eindige lichamen. We zullen verder enkele eenvoudige cryptografische protocollen behandelen. Tenslotte behandelen we nog enkele conventionele cryptosystemen, onder meer het door de Belgen Daemen en Rijmen ontwikkelde systeem Rijndael [3] (ook bekend als AES, Advanced Encryption Standard). Op het college wordt de benodigde getaltheorie behandeld; voor de bewijzen van enkele resultaten wordt verwezen naar het college getaltheorie van Prof. Tijdeman.
English abstract:	Cryptography is concerned with the invention of mathematical methods to enhance the security of electronic data transmission (for instance cryptosystems for securely encrypting data and digital signature systems which attach unforgeable signatures to electronic data). Until the mid-1970's only so-called conventional cryptosystems existed, in which two parties A and B have to exchange a secret key for enciphering the messages they want to send to each other. In 1976, Diffie and Hellman (see their famous paper [1] mentioned above) proposed the notion of a public key cryptosystem, in which each user has his own encryption key which he publishes in some public directory, and his own decryption key which he keeps secret. When A wants to send a message to B, he looks up B's encryption key in the public directory, encrypts the message, and sends this to B. Then B can decrypt the message with his decryption key known only to himself. Diffie and Hellman could not give a concrete example of a public key cryptosystem but in 1978, Rivest, Shamir and Adleman published a system, nowadays known as the RSA-system [2], based on number theory. This system can also be used for attaching digital signatures to messages. In the RSA-system, each user chooses two large prime numbers p and q of about 150 digits, keeps p and q secret, and makes their product n=pq public. The RSA-system owes its usefulness and security to the fact that on the one hand it takes relatively little computation time to find prime numbers of 150 digits, whereas (with the present state of affairs) it is infeasible to factor numbers of 300 digits. Therefore, we will also pay attention to prime tests and (depending on the time) factorization methods. After the RSA-system, several other cryptosystems and digital signature systems based on number theory have been developed. In this course we discuss systems based on the discrete logarithm problem in finite fields. Depending on the time we will pay attention to either cryptosystems based on the discrete logarithm problem for elliptic curves, or on cryptographic protocols. Apart from the systems mentioned above we will also pay attention to some conventional cryptosystems, in particular the Rijndael system (also known as AES, Advanced Encryption Standard) developed by the Belgians Daemen en Rijmen [3].