English          

Eliptičke krivulje u kriptografiji

Izborni kolegij na Diplomskom sveučilišnom studiju Teorijska matematika i Diplomskom sveučilišnom studiju Računarstvo i matematika                             0+0   3+0

Program sastavili: Andrej Dujella i Filip Najman

Predavanja (2020/2021): Andrej Dujella


Raspored: četvrtak 15-18 (online)
Nastava će početi u četvrtak 18.3.2021. u 15:15 (online).
Upute će biti objavljene nekoliko dana prije prvog predavanja.

Link za pristup nastavi:
https://zoom.us/j/95961917567?pwd=TWRrYUhOSHRMbHg4dVpiU3lEVGVCdz09
Passcode: 181408

U četvrtak 25.3.2021. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 1. zadaću.
Rješenja treba poslati do 8.4.2021. na duje@math.hr, po mogućnosti kao jedan pdf file.

U četvrtak 8.4.2021. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 2. zadaću.
Rješenja treba poslati do 13.5.2021. na duje@math.hr, po mogućnosti kao jedan pdf file.

U četvrtak 13.5.2021. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 3. zadaću.
Rješenja treba poslati do 27.5.2021. na duje@math.hr, po mogućnosti kao jedan pdf file.

U četvrtak 27.5.2021. studenti će na e-mail adresu navedenu u sustavu Merlin dobiti 4. zadaću.
Rješenja treba poslati do 10.6.2021. na duje@math.hr, po mogućnosti kao jedan pdf file.


Završni pismeni ispit će se održati u četvrtak 17.6.2021. u 15 sati (u terminu zadnjih predavanja). Ispit će se održati online. Studenti će se na početku ispita trebati spojiti preko zooma u 15:00 (link je isti kao za predavanja) zbog evidencije i uputa na početku pisanja ispita.

Studenti će svoje zadatke za završni pismeni ispit moći naći na poveznici
https://web.math.pmf.unizg.hr/~duje/elkript/zavrsni2021/
u 15 sati. Zadaci se nalaze u pdf fileu nazvanom po prezimenu studenta.

Ispit se piše 2 sata. Sastojat će se od 4 zadatka od koji svaki donosi 10 bodova. Zadaci će biti poput onih koji su došli na završnim ispitima 2017/2018 i 2018/2019.

Po završetku ispita, studenti trebaju poslati svoja rješenja e-mailom na duje@math.hr, konačna rješenja zadataka napišite u tekstu poruke, a postupak rješavanja pošaljite u prilogu poruke uslikan ili skeniran.

Studenti koji su iz zadaća i aktivnosti na nastavi sakupili dovoljan broj bodova za prolaznu ocjenu nisu obavezni izaći na završni ispit ako su zadovoljni ocjenom.

Studenti koji bi zbog opravdanih razloga bili spriječeni pristupiti ispitu u predviđenom terminu, mogu mi se javiti oko dogovora o dodatnom terminu, a ovisno o okolnostima i o modifikaciji završnog dijela polaganja ispita.


Rezultati zadaća i završnog ispita
Ako ima studenata koji ne žele prihvatiti ostvarenu ocjenu, molim da mi to jave do ponedjeljka 21.6.2021. u 12 sati.
Molim da mi se do istog roka jave i studenti koji žele izaći na popravni završni ispit.
Cilj ovog kolegija je upoznati studente s osnovnim pojmovima, činjenicama i algoritmima vezanim uz eliptičke krivulje nad poljem racionalnih brojeva i konačnim poljima, te njihovim primjenama u kriptografiji i algoritamskoj teoriji brojeva.

Kolegij nema formalnih kolegija prethodnika. Za uspješno praćenje kolegija, poželjno je da je položen kolegij Teorija brojeva s preddiplomskog studija matematike, te jedan od kolegija Algebarske krivulje (smjer teorijska matematika) ili Kriptografija i sigurnost mreža (smjer računarstvo i matematika).


Snimke predavanja

Sadržaj kolegija

Eliptičke krivulje nad poljem racionalnih brojeva. Zbrajanje točaka na eliptičkoj krivulji. Mordell-Weilova grupa eliptičke krivulje nad poljem racionalnih brojeva. Algoritmi za računanje torzijske grupe i ranga.

Eliptičke krivulje nad konačnim poljima. Efikasna implementacija osnovnih operacija na eliptičkih krivuljama. Eliptičke krivulje nad poljima karakteristike 2. Algoritmi za određivanje reda grupe točaka na eliptičkoj krivulji.

Kriptografija javnog ključa. Ideja javnog ključa. Kriptosustavi zasnovani na problemu faktorizacije i problemu diskretnog logaritma u konačnoj grupi. Digitalni potpis.

Kriptosustavi koji koriste eliptičke krivulje. Analogoni El-Gamalovog i DSA kriptosustava. Usporedba s ostalim kriptosustavima javnog ključa. Problem diskretnog logaritma za eliptičke krivulje. Izbor parametara kriptosustava.

Ostale primjene eliptičkih krivulja. Lenstrina metoda faktorizacije. Dokazivanje prostosti pomoću eliptičkih krivulja.


Osnovna literatura

  1. A. Dujella: Teorija brojeva, Školska knjiga, Zagreb, 2019.

  2. A. Dujella: Number Theory, Školska knjiga, Zagreb, 2021.

  3. A. Dujella, M. Maretić: Kriptografija, Element, Zagreb, 2007.

  4. N. Koblitz: A Course in Number Theory and Cryptography, Springer-Verlag, New York, 1994.

Dodatna literatura

  1. I. Blake, G. Seroussi, N. Smart: Elliptic Curves in Cryptography, Cambridge University Press, Cambridge, 1999.

  2. A. Enge: Elliptic Curves and Their Applications to Cryptography. An Intoduction, Kluwer, Boston, 1999.

  3. D. Hankerson, A. Menezes, S. Vanstone: Guide to Elliptic Curve Cryptography, Springer-Verlag, New York, 2004.

  4. J. H. Silverman, J. Tate: Rational Points on Elliptic Curves, Springer-Verlag, Berlin, 1992.

  5. L. C. Washington: Elliptic Curves: Number Theory and Cryptography, CRC Press, Boca Raton, 2008.


Eliptičke krivulje u kriptografiji, skripta
(u pdf formatu)


Način polaganja ispita:

Domaće zadaće: Bit će četiri domaće zadaće (koje će se bodovati). Rok za predaju zadaće će biti u pravilu dva tjedna. Maksimalan broj bodova na svakoj zadaći je 15.
Aktivnost na nastavi: Na nastavi će se zadavati zadaci za samostalno rješavanje. Studenti koji budu najuspješniji u rješavanju tih zadataka, dobit će u pravilu za svaki zadatak po 5 bodova. Maksimalan broj bodova koji će se moći sakupiti u ovoj komponenti je 20.
Kolokviji i završna provjera znanja: Neće biti kolokvija. Završna provjera znanja je pismena. Zadaci će biti iz onih poglavlja koja nisu bila obuhvaćena domaćim zadaćama. Nema uvjeta za pristup završnoj provjeri. Završna provjera znanja će se održati u redovitom terminu nastave iz ovog kolegija (vjerojatno zadnji tjedan nastave). Maksimalan broj bodova koji je moguće dobiti na završnom ispitu je 40.
Bit će jedan termin za popravak završnog ispita u dogovoru za zainteresiranim studentima. Nema uvjeta za izlazak na popravak.
Zaključivanje ocjene: Zbrojit će se bodovi iz domaćih zadaća (max. 60), aktivnosti na nastavi (max. 20) i završnog ispita (max. 40).
Ocjene:   ≥ 85 bodova - ocjena 5;   ≥ 70 bodova - ocjena 4;   ≥ 55 bodova - ocjena 3;   ≥ 40 bodova - ocjena 2;   < 40 bodova - ocjena 1.


Obavijesti na web forumu kolegija "Kriptografija"

Kriptografija i sigurnost mreža - kolegij na diplomskom studiju računarstva

Teorija brojeva - kolegij na preddiplomskom studiju

Elementarna teorija brojeva - kolegij na preddiplomskom studiju

Algoritmi za eliptičke krivulje - poslijediplomski kolegij (2008/2009)

Teorija brojeva u kriptografiji - poslijediplomski kolegij (2003/2004)

Studentski seminar - Eliptičke krivulje i njihova primjena u kriptografiji (2002/2003)

Popis dostupne literature iz teorije brojeva

PARI/GP home page

PARI/GP in browser

Number Theory and PARI/GP

SageMathCell

MAGMA Calculator

LMFDB database


Domaće zadaće i završni ispiti:

2012/2013: zad1, zad2, zad3, zad4, završni,

2013/2014: zad1, zad2, zad3, završni

2014/2015: zad1, zad2, zad3, zad4, završni

2015/2016: završni

2017/2018: završni

2018/2019: završni


Andrej Dujella home page