Kryptomatematiikka ja laskettavuusLaajuus (3 op)

Osaamistavoitteet

Opiskelija tuntee kryptomatematiikan perustana olevia algebrallisia teorioita niin paljon, että ymmärtää tavallisimpien salausalgoritmien toiminnan ja salauksen perustan. Opiskelija ymmärtää laskettavuuteen liittyvät perusasiat kuten polynomiaalisen ja ylipolynomiaalisen laskutyön eron sekä probabilististen algoritmien idean.

Sisältö

1) Algebra ja lukuteoria
2) Kryptografian käsitteitä
3) Laskenta-algoritmit ja laskennan vaativuus
4) RSA-salaus ja tekijöihinjako-ongelma
5) Diskreetin logaritmin ongelma ja sen soveltaminen kryptografiassa

Arviointikriteerit, tyydyttävä (1)

1) Opiskelija tuntee kokonaislukujen laskusäännöt, jaollisuuden, jakoyhtälön ja alkuluvut sekä alkutekijöihin jaon. Opiskelija tuntee modulaarialgebran laskusäännöt ja osaa laskea jakojäännöksillä. Opiskelija tuntee Fermat’n pienen lauseen ja Eulerin funktion.

2) Opiskelija tietää salauksen periaatteen, tuntee joitakin klassisia salausjärjestelmiä ja ymmärtää ilmeiset heikkoudet salauksissa. Opiskelija tuntee nimeltä moderneja salausjärjestelmiä. Opiskelija ymmärtää yksityisen avaimen ja julkisen avaimen salauksen eron.

3) Opiskelija osaa Eukleideen algoritmin ja laskea pienillä luvuilla käänteisalkion jäännösluokkarenkaassa. Opiskelija osaa pienillä luvuilla tehdä nopeasti potenssiin korotuksen jäännösluokkarenkaassa.

4) Opiskelija tietää RSA-salauksen periaatteen ja osaa selittää mihin sen oletettu turvallisuus perustuu. Opiskelija osaa pienillä luvuilla tehdä salauksen, laskea yksityisen avaimen julkisesta avaimesta sekä purkaa salauksen.

Arviointikriteerit, hyvä (3)

Tyydyttävien vaatimusten lisäksi

1) Opiskelija tuntee käsitteet ryhmä, rengas ja kunta sekä näiden perusominaisuuksia ja esimerkkejä näistä. Opiskelija tietää mitä tarkoittaa syklinen ryhmä ja virittäjä sekä osaa etsiä virittäjän alkulukukertalukua olevan kunnan multiplikatiiviselle ryhmälle. Opiskelija tuntee kiinalaisen jäännöslauseen ja osaa soveltaa sitä.

2) Opiskelija tuntee käsitteet kryptografinen sormenjälki, varmenne ja digitaalinen allekirjoitus. Opiskelija tietää eron yksityisen avaimen ja julkisen avaimen salauksen käyttökohteiden välillä.

3) Opiskelija osaa selittää polynomiaikaisen ja ylipolynomiaalisen ajan algoritmin ja niiden merkityksen kryptografiassa. Opiskelija osaa itse arvioida algoritmin vaatimaa laskenta-aikaa. Opiskelija tietää probabilistisen ja deterministisen algoritmin eron. Opiskelija tuntee Miller-Rabinin alkulukutestin ja Pollardin p-1-tekijöihinjakoalgoritmin.

4) Opiskelija tietää tärkeimmät turvallisuusvaatimukset RSA-salauksessa käytettäviltä alkuluvuilta. Opiskelija osaa selittää RSA-salausta käyttävän digitaalisen allekirjoituksen periaatteen.

5) Opiskelija osaa kuvata diskreetin logaritmin ongelman ja tietää vallitsevan käsityksen sen ratkaisemisen vaikeudesta. Opiskelija tuntee ElGamalin salauksen yleisen periaatteen. Opiskelija osaa pienillä kokonaisluvuilla tehdä salauksen, laskea yksityisen avaimen julkisesta avaimesta sekä purkaa salauksen.

Arviointikriteerit, kiitettävä (5)

Tyydyttävien ja hyvien vaatimusten lisäksi:

1) Opiskelija osaa laskea polynomeilla alkulukukertalukua olevan kunnan suhteen. Opiskelija tietää miten muodostetaan äärellinen kunta jaottoman polynomin avulla ja osaa tehdä konkreettisia laskutoimituksia näissä kunnissa kertaluvun ollessa riittävän pieni. Opiskelija tuntee elliptisen käyrän käsitteen, osaa selittää ryhmäoperaation käyrän pisteille sekä tuntee käyttömahdollisuuden kryptografiassa.

2) Opiskelija pystyy matemaattisen tietämyksensä pohjalta yksityiskohtaisesti selvittämään jonkin nykyaikaisen kryptografisen järjestelmän (esim. AES-salaus, SHA1-sormenjälki) toiminnan vaiheittain.

3) Opiskelija osaa Eukleideen algoritmin polynomeille ja osaa laskea käänteisalkion äärellisessä kunnassa. Opiskelija omaa valmiudet tehdä toimivia ja riittävän nopeita tietokoneohjelmia aiemmin esillä olleiden algoritmien toteuttamiseksi.