AU kursuskatalog arkiv

Matematiske aspekter af kryptologi ( forår 2009 - 10 ECTS )

Rammer for udbud

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

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 der 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

Kursushjemmesiden kan ses på instituttets hjemmeside
http://www.imf.au.dk
kort før kursets start.

Eksamensterminer

Eksamen: 4. kvarter

Reeksamen: efter aftale med faglæreren.

Udbyder

Institut for Matematiske Fag (IMF)

Tilmelding til undervisning

Tilmelding i Informationen på Institut for Matematiske Fag fra d. 1. - 15. december 2008.

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.

Bedømmelse

Kurset evalueres efter 7-trinsskalaen med intern censur.

Den første delprøve kan være et studenterseminar med noter udarbejdet af den studerende, eller en skriftlig opgave.

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.