Matematiske aspekter af kryptologi ( forår 2008 - 10 ECTS )
Rammer for udbud
-
Uddannelsessprog:
(se under Undervisnings- og arbejdsform)
-
Niveau:
Overbygningskursus
-
Semester/kvarter:
3. + 4. kvarter (Forår 2008)
-
Timer per uge:
4
-
Deltagerbegrænsning:
-
Undervisningssted:
Århus
-
Hovedområde:
Det Naturvidenskabelige Fakultet
-
Udbud ID:
7064
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.
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.
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. 3. - 14. december 2007.
Bedømmelse
Kurset evalueres efter 7-trinsskalaen med intern censur.
Evalueringen foregår ved to delprøver.
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 minutter forberedelse
og alle sædvanlige hjælpemidler.
Ved karaktergivning vægter den første delprøve 1/3
og den mundtlige eksamen 2/3.
