AU kursuskatalog arkiv

Matematiske aspekter af kryptologi (Q3+Q4) ( forår 2010 - 10 ECTS )

Rammer for udbud

• Uddannelsessprog: engelsk (eller dansk)
• Niveau: Kandidatkursus
• Semester/kvarter: 3. + 4. kvarter (Forår 2010)
• Timer per uge: 4
• Deltagerbegrænsning: Ingen
• Undervisningssted: Århus
• Hovedområde: Det Naturvidenskabelige Fakultet
• Udbud ID: 15296

Formål

Kurset dækker matematiske aspekter der er nødvendige for design og evaluering af sikre public key kryptosystemer.

Indhold

Public key kryptosystemer som RSA og DSA bygger på algebraiske strukturer, specielt grupper, og primtal spiller en fundamental rolle. De underliggende problemer som muliggør systemerne er faktorisering af hele tal og det diskrete logaritmeproblem.

I kurset gennemgås den primtalsteori der er nødvendig for konstruktionen af praktiske systemer, bl.a. primtalstest og algoritmer til effektiv beregning med meget store heltal. Faktoriseringsalgoritmer fra testdivision over Pollard's probabilistiske metoder, n-1 algoritmen og Lenstra's metode, til de stærkeste algoritmer der på forskellig ikke-triviel vis reducerer problemet til et lineær algebra problem. En forståelse af disse algoritmer er essentiel for konstruktionen af sikre systemer.

Metoder til løsning af det diskrete logaritme problem gennemgås, bl. a Shanks baby step giant step metode, Pollard's rho algoritme, Pohlig-Hellman og index calculus. Ikke alle algoritmer er generiske, nogle afhænger af strukturen af gruppeordenen (såkaldt fladhed) andre af den konkrete repræsentation af gruppen. Det sidste har stor betydning i forbindelse med elliptiske kurver. Her fungerer den stærske algoritme ikke. Dette oversætter direkte til at samme sikkerhed kan opnås for meget mindre gruppeordner sammenlignet med endelige legemer, et forhold af stor betydning i praksis. Igen er et kendskab til disse angreb en forudsætning for at konstruere sikre systemer.

Elliptiske kurver behandles i det omfang det er nødvendigt for at forstå hvordan systemer kan implementeres der.

Faglige forudsætninger

Algebra.

Underviser

Jørgen Brandt

Undervisnings- og arbejdsform

4 timers undervisning pr. uge.

Litteratur

Crandall & Pomerance, Prime Numbers, 2.nd ed. , Springer, 2005

Kursushjemmeside

Eksamensterminer

Eksamen: 4. kvarter

Reeksamen: efter aftale med faglæreren.

Udbyder

Institut for Matematiske Fag (IMF)

Tilmelding til undervisning

Eftertilmeldinger: Kontakt Maiken Kirdorf Nielsen, maiken@imf.au.dk

Læringsmål

Ved kursets afslutning forventes den studerende inden for kursets emneområde at kunne:

• beskrive de matematiske principper bag moderne public key kryptografi
• evaluere sikkerheden i konkrete systemer
• sammenholde centrale resultater
• anvende kursets grundlæggende teknikker, resultater og begreber på konkrete eksempler og opgaver
• sætte sig ind i et foreskrevet delemne på selvstændig vis og præsentere udvalgte dele af dette delemne for sine medstuderende mundtligt med tilhørende skriftlige noter
• kombinere begreber fra algebra og talteori.

Studieordning og bedømmelse

Tilvalgsfag: Matematik og statistik

• Mundtlig, bedømt efter 7-skala med intern censur

Kurset evalueres efter 7-trinsskalaen med intern censur.

Den første delprøve er et studenterseminar med noter udarbejdet af den studerende.

Den anden delprøve er en mundtlig eksamen, som varer ca. 20 minutter, med 25 minutters forberedelse og alle sædvanlige hjælpemidler.

Ved karaktergivning vægter den første delprøve 1/3 og den mundtlige eksamen 2/3.