1ZI1703 - Algorytmy i bezpieczeństwo danych

Nazwa w drugim języku: 

Algorithms and Data Security

Cel przedmiotu: 

Celem przedmiotu jest zapoznanie słuchacza wykładu z dwiema bardzo istotnymi,
osiowymi dla szeroko pojętej elektroniki i informatyki dziedzinami:

1. teorią algorytmów (a ściślej rzecz biorąc z pewnymi bardziej zaawansowanymi fragmentami tej
teorii związanymi z implementacją algorytmów kryptograficznych)

2.podstawami teoretycznymi kryptografii i bezpieczeństwa informacji

W rozdziałach poświęconych teorii algorytmów omawiane są te fragmenty teorii, które są
wykorzystywane w kryptografii i bezpieczeństwie informacji, takie jak złożonosć obliczeniowa, algorytmy probabilistyczne
 i algorytmy teorioliczbowe (np. algorytmy testowania pierwszości).

W rozdziałach poświęconych kryptografii omawiane są podstawowe algorytmy kryptograficzne, protokoły i metody stosowane w systemach komputerowych i sieciach komputerowych do ochrony informacji.

Treści kształcenia: 

___________________________________________________________________________
Treść przedmiotu
___________________________________________________________________________
Część 1 – Algorytmy komputerowe i struktury danych
1. Wprowadzenie
a. Algorytm, analiza i projektowanie algorytmów
b. Złożoność obliczeniowa algorytmu – podstawowe pojęcia
c. Sposoby opisu algorytmów – język publikacyjny
d. Zapisy asymptotyczne
e. Elementarne struktury danych
f. Rekurencja i metody projektowania algorytmów
g. Równania rekurencyjne
h. Algorytmy probabilistyczne

2. Złożoność obliczeniowa i NP zupełność
a. Teoria złożoności obliczeniowej
b. Problemy (problemy obliczeniowe) i problemy decyzyjne
c. Algorytmy z czasem wielomianowym
d. Redukowalność i problemy NP –zupełne oraz przykłady problemów NP-zupełnych
e. Klasy złożoności algorytmów probabilistycznych

3. Algorytmy sortowania
a. Problem sortowania
b. Sortowanie bąbelkowe (bubblesort)
c. Zmodyfikowane sortowanie bąbelkowe (modified bubblesort)
d. Insertionsort – sortowanie przez wstawianie
e. Sortowanie przez selekcję (selectionsort)
f. Algorytm sortowania „mergesort” (algorytm sortowania przez scalanie)
g. Algorytmy sortowania w czasie liniowym
h. Sortowanie przez zliczanie – countsort
i. Sortowanie pozycyjne – algorytm radixsort
j. Sortowanie kubełkowe - algorytm bucketsort
k. Sortowanie przez kopcowanie (ang. heapsort)
l. Sortowanie szybkie – quicksort
m. Szybkie algorytmy wyznaczania k-tego elementu co do wartości w ciągu.
n. Sortowanie zewnętrzne
o. Sieci sortujące

4. Algorytmy tekstowe
a. Problem wyszukiwania wzorca
b. Algorytm naiwny wyszukiwania wzorca
c. Algorytm automatowy
d. Algorytm Rabina-Karpa
e. Algorytm KMP

5. Algorytmy teorioliczbowe
a. Rozszerzony binarny algorytm Euklidesa
b. Szybkie algorytmy podnoszenia do potęgi modulo n
c. Algorytmy obliczania pierwiastka kwadratowego mod n
d.Algorytm Montgomery’ego
e.Algorytm Barretta
f. Algorytmy testowania pierwszości

Część 2 – Algorytmy i bezpieczeństwo danych
1. Kryptografia - pojęcia podstawowe
a. Cele i środki kryptografii
b. System kryptograficzny
c. Rodzaje szyfrów (szyfry z kluczem publicznym i z kluczem prywatnym, szyfry blokowe)
d. Szyfry klasyczne (szyfry podstawieniowe, szyfry monoalfabetowe i polialfabetowe, szyfry przedstawieniowe, szyfry idealne)

2. Podstawy matematyczne kryptografii
a. Grupy i logarytmy dyskretne
b. Pierścienie i ciała
c. Podzielność, kongruencje i chińskie twierdzenie o resztach, twierdzenie Eulera
d. Liczby pierwsze i testowanie pierwszości

3. Systemy kryptograficzne z kluczem publicznym
a. Wprowadzenie
b. System kryptograficzny RSA
c. System kryptograficzny Rabina
d. System kryptograficzny ElGamala
e. Szyfry plecakowe
f. System kryptograficzny Massey’a–Omury

4. Systemy kryptograficzne z kluczem prywatnym
a.Szyfry Feistala
b. DES (Data Encryption Standard) i rozszerzenia, modyfikacje DES’a (DESX, 3DES)
c. Szyfr AES (Advanced Encryption Standard)
d. Szyfry IDEA, Serpent, Camelia

5. Funkcje skrótu
a. Podstawowe definicje (funkcja jednokierunkowa, funcje słabo i silnie bezkonfliktowe)
b. Funkcja hashująca Chaum’a –van Heijst’a –Pfitzmanna
c. Funkcja haszująca MD 5, Whirlpool, SHA-256
d. Schematy ogólne tworzenia funkcji skrótu
e. Paradoks dnia urodzin i ataki na funkcje skrótu

6. Tryby wykorzystania szyfrów blokowych i szyfry strumieniowe
a. Tryb szyfrowania ECB, CBC i OFB
b. Szyfry strumieniowe

7. Uwierzytelnianie dokumentu - podpisy cyfrowe
a. Podpisy cyfrowe – uwagi wstępne, typy podpisów cyfrowych
b. Algorytm podpisów cyfrowych RSA
c. Algorytm podpisów cyfrowych ElGamala
d. Algorytm podpisów cyfrowych DSS
e. Algorytm podpisów Rueppela-Nyberga
e. Algorytm podpisów ślepych

8. Uwierzytelnianie strony
a. Metoda haseł, metoda haseł z soleniem
b. Metoda pytanie odpowiedź (metoda challenge-response)
c. Protokoły z wiedzą zerową (protokoły Fiata-Shamira i Feige-Fiata Shamira)

9. Dystrybucja kluczy, protokoły wymiany klucza
a. Protokół Diffiego-Hellmana
b. Protokoły szerokogębnej żaby i Needhama-Schroedera

Bibliografia: 

Bibliografia:
[1] T.Adamski, J.Ogrodzki; Algorytmy komputerowe i struktury danych; Oficyna wydawnicza P.W., Warszawa 2005.
[2] L.Banachowski, K.Diks, W.Rytter; Algorytmy i struktury danych; WNT, Warszawa 1996.
[3] T.Cormen, C.Leiserson,R.Rivest, C.Stein; Wprowadzenie do algorytmów; WNT, Warszawa 2004.
[4] A.Menezes, P.Oorschot, S.Vanstone; Kryptografia stosowana; WNT, Warszawa, 2005.
[5] J.Buchmann; Wprowadzenie do kryptografii; PWN, Warszawa, 2006.

Metody oceny: 

Przedmiot zaliczany jest w formie egzamin pisemnego (60p).
 
Za rozwiązanie zadań i małych projektów do samodzielnego rozwiązania
nazywanych TESTami można dodatkowo zdobyć 40p (to dużo).
Rozwiązywanie TESTów nie jest obowiąkowe ale bardzo zalecane.

W sumie są 4 serie TESTów po 10p.

Ostatecznie można zdobyć 100p. Próg zaliczenia to 50p.

Przeliczenie punty ocena jest liniowe:
50p - próg zaliczenia
50-59 ocena 3
60-69 ocena 31/2
70-79 ocena 4
80-89 ocena 41/2
90-100 ocena 5

Uwagi: 

-

Przedmioty na których bazuje dany przedmiot (prerekwizyty):

• [DE1102] Matematyka 1