1ZI1703 - Algorytmy i bezpieczeństwo danych

Nazwa w drugim języku: 

Algorithms and Data Security

Przedmiot realizowany w planach wzorcowych:

Obieralny dla katalogów:

Znalazłem 0 pozycji. (Pokaż szczegóły)

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

• Efekty Kształcenia dla kierunku Informatyka stosowana:
• Wiedza

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  	Dodatkowe efekty kierownika przedmiotu	+++ (100%)	Wiedza z zakreu specjalnych algorytmów wykorzystywanych w kryptografii takich jak np. algorytm Montgomery'ego. Obszerna wiedza dotycząca metod kryptograficznych i ich podstaw matematycznych.	Egzamin
  E1_W01	ma podstawową wiedzę z zakresu matematyki, przydatną do formułowania i rozwiązywania zadań z zakresu studiów, dotyczącą: a) analizy matematycznej b) algebry c) probabilistyki d) metod numerycznych	++ (66%)	Wiedza z zakresu algebry i teorii liczb niezbędna do zrozumienia algorytmów kryptograficznych	Egzamin, zadania
  E1_W01b	ma podstawową wiedzę z zakresu matematyki, przydatną do formułowania i rozwiązywania zadań z zakresu studiów, dotyczącą algebry	+++ (100%)	Wiedza z zakresu algebry i teorii liczb niezbędna do zrozzumienia metod matematycznych stosowanych w kryptografii	Egzamin, zadania
  E1_W01c	ma podstawową wiedzę z zakresu matematyki, przydatną do formułowania i rozwiązywania zadań z zakresu studiów, dotyczącą probabilistyki	+ (33%)	Wiedza z zakresu teorii prawdopodobieństwa niezbędna w konstrukcji generatorów liczb losowych typu TRNG i PRNG oraz rozumienia zasad kryptoanalizy	Egzamin
  E1_W02	ma wiedzę przydatną do formułowania i rozwiązywania podstawowych zadań z zakresu studiów, dotyczącą: a) fizyki klasycznej b)podstaw fizyki relatywistycznej i kwantowej c) ma wiedzę na temat zasad przeprowadzania i opracowania wyników pomiarów fizycznych, rodzajów niepewności pomiarowych i sposobów ich wyznaczania	+ (33%)	Wiedza z zakresu kryptografii kwantowej	Egzamin
  I1_W04	Ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu informatyki, w szczególności: a) podstaw programowania, b) algorytmów i złożoności, c) architektury systemów komputerowych, d) systemów operacyjnych, e) technologii sieciowych, f) języków i paradygmatów programowania, g) grafiki i komunikacji człowiek-komputer, h) sztucznej inteligencji, i) baz danych, j) inżynierii oprogramowania, k) systemów wbudowanych, l) wybranych podstawowych zastosowań informatyki.	++ (66%)	Wiedza z zakresu bezpieczeństwa systemów komputerowych i algorytmiki	Egzamin, projekty
  I1_W04b	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu algorytmów i złożoności	+++ (100%)	Uporządkowana wiedza z zakresu algorytmów i złożoności obliczeniowej	Egzamin, zadania, testy
  I1_W04d	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu systemów operacyjnych	+ (33%)	Wiedza z zakresu bezpieczeństwa systemów operacyjnych	Egzamin
  I1_W04e	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu technologii sieciowych	++ (66%)	Wiedza z zakresu bezpieczeństwa technologii sieciowych	Egzamin
  I1_W08a	zna podstawowe, stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu informatyki metody	++ (66%)	Utrwalenie wiedzy z zakresu rozwiązywania zadań inżynierskich z zakresu informatyki	Zadania i projekty

• Umiejętności

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  	Dodatkowe efekty kierownika przedmiotu	+++ (100%)	Umiejętność wykorzystania istniejących metod i narzędzi do tworzenia bezpiecznych systemów informatycznych i komputerowych.	Egzamin, zadania projekty.
  E1_U05	Potrafi planować własne uczenie się, ma umiejętności samokształcenia.	+++ (100%)	Umiejętność samodzielnego docierania do informacji z zakresu algorytmiki i bezpieczeństwa danych. Umiejętność aktualizacji wiedzy.	Projekt zespołowy stanowiący potencjalną możliwośc kontynuacji przedmiotu.
  E1_U12	potrafi dokonać wstępnej analizy ekonomicznej podejmowanych działań inżynierskich	+++ (100%)	Umiejętność jednoczesnej oceny kosztów i bezpieczeństwa projektowanego systemu.	Projekty.
  I1_U01	Potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł w wersji drukowanej i elektronicznej, w tym w Internecie, także w języku angielskim albo francuskim lub niemieckim w zakresie informatyki, potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski, formułować i uzasadniać opinie.	+++ (100%)	Wyuczenie współczesnego standardu pozyskiwania i syntezy informacji pochodzącej z różnych żródeł. Umiejętność tworzenia struktury.	Wspólna dyskusja nad zadaniem-projektem.
  I1_U02	Potrafi porozumiewać się przy użyciu różnych technik w środowisku zawodowym związanym z informatyką oraz w innych środowiskach.	+++ (100%)	Umiejętność operowania pojęciami z zakresu algorytmiki i bezpieczenstwa informacji.	Egzamin. Rozumienie i rozwiązywanie zadań o charakterze obliczeniowym.
  I1_U03	Potrafi przygotować i przedstawić w języku polskim i języku angielskim albo francuskim lub niemieckim dobrze udokumentowane opracowanie problemów z zakresu informatyki.	+++ (100%)	Umiejętność tworzenia precyzyjnego opisu projektu z zakresu bezpieczenstwa informacji.	Ocena wykonanego projektu lub wykonanie projektu zespołowego jako kontynuacja przedmiotu.
  I1_U04	Potrafi przygotować i przedstawić w języku polskim i języku angielskim albo francuskim lub niemieckim prezentację ustną, dotyczącą szczegółowych zagadnień z zakresu informatyki.	+++ (100%)	Umiejętność precyzyjnego formułowania myśli i problemów w zakresie algorytmiki i bezpieczenstwa informacji	Egzamin i TESTY
  I1_U06	Ma umiejętności językowe w zakresie ogólnie pojętej informatyki, pozwalające na porozumiewanie się i korzystanie z materiałów w języku obcym; poziom znajomości języka powinien odpowiadać wymaganiom określonym dla poziomu B2 Europejskiego Systemu Opisu Kształcenia Językowego.	+++ (100%)	Umiejętności językowe (słownictwo) w zakresie algorytmiki i bezpieczeńwa informacji	Sprawdzanie pośrednie w ramach wykonania projektu zespołowego z przedmiotu.
  I1_U07	Potrafi posługiwać się technikami informacyjno-komunikacyjnymi w tym grafiką inżynierską, właściwymi do realizacji zadań typowych dla działalności inżynierskiej.	+++ (100%)	Umiejętność wykorzystania narzędzi CAD w tym bibliotek kryptograficznych.	Ocena projektu. Egzamin.
  I1_U08b	potrafi planować i przeprowadzać eksperymenty, w tym symulacje komputerowe	+++ (100%)	Umiejętność weryfikacji projektu metodą symulacji komputerowej.	Ocena wykonywanych zadań-projektów
  I1_U08c	potrafi planować i przeprowadzać eksperymenty, w tym interpretować uzyskane wyniki i wyciągać wnioski	+++ (100%)	Umiejętność planowania doświadczeń i przeprowadzania eksperymentów w zakresie algorytmiki i bezpieczeństwa informacji	Ocena wykonywanych zadań-projektów
  I1_U09	Potrafi wykorzystać do formułowania i rozwiązywania zadań inżynierskich metody: analityczne, symulacyjne, eksperymentalne.	+++ (100%)	Umiejętność wykorzystania metod analitycznych, symulacyjnych i eksperymentalnych w zakresie algorytmiki i bezpieczenstwa informacji.	Ocena projektów. Egzamin
  I1_U14	Potrafi dokonać identyfikacji i sformułować specyfikację prostych zadań inżynierskich o charakterze praktycznym, charakterystycznych dla informatyki.	+++ (100%)	Umiejętność wyodrębnienia i rozwiązania prostych zadań inżynierskich o charakterze praktycznym w zakresie algorytmiki i bezpieczenstwa danych.	Ocena zadań-projektów.
  I1_U15	Potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla informatyki oraz wybrać i zastosować właściwą metodę i narzędzia.	+++ (100%)	Umiejętność wykorzystania standartowych rozwiązań i metod w zakresie algorytmiki i bezpieczeństwa informacji	Egzamin, zadania, projekty.
  I1_U16	Potrafi, zgodnie z zadaną specyfikacją, zaprojektować oraz zrealizować proste urządzenie, obiekt, system lub proces, typowe dla informatyki, używając właściwych metod, technik i narzędzi.	+++ (100%)	Umiejętność zaprojektowania bezpiecznego systemu komputerowego lub informatycznego.	Egzamin, zadania, projekty.

• Kompetencje społeczne

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  	Dodatkowe efekty kierownika przedmiotu	+++ (100%)	Kultura myślenia.Wprowadzenie zasady: nic bez precyzyjnego uzasadnienia (dowodu)	Egzamin, rozwiązywanie zadań
  E1_K01	Jest przygotowany do przeprowadzenie krytycznej analizy posiadanej wiedzy, ma świadomość posiadanych kompetencji i umie pozyskać informacje potrzebne do realizacji postawionych przed nim zadań.	+++ (100%)	Przyzwyczajenie studenta do stałej syntezy i poszerzania wiedzy	Rozwiązywanie zadań i testów mających charakter projektu
  E1_K02	Jest przygotowany do współpracy z mentorem dla osiągnięcia postawionych celów.	+++ (100%)	Umiejętność doboru stsosowanych rozwiązań do potrzeb społecznych	Ocena zadań projektowych
  E1_K05	Prawidłowo identyfikuje i rozstrzyga dylematy związane z wykonywaniem zawodu.	++ (66%)
  E1_K07	Ma świadomość roli społecznej absolwenta uczelni technicznej, a zwłaszcza rozumie potrzebę formułowania i przekazywania społeczeństwu, w szczególności poprzez środki masowego przekazu, informacji i opinii dotyczących osiągnięć techniki i innych aspektów działalności inżynierskiej; podejmuje starania, aby przekazać takie informacje i opinie w sposób powszechnie zrozumiały z zachowaniem zasad etyki zawodowej.	+++ (100%)	Jasność formułowania myśli a wszczególności istoty problemu technicznego. Przyzwyczajenie studenta do dowodzenia w sposób jasny stawianych tez.	Ocena zadań. Egzamin z przedmiotu.

• • Punkty ECTS za zajęcia kontaktowe z nauczycielem: 3 
  • Punkty ECTS za zajęcia praktyczne łącznie; kontaktowe i bez kontaktu z nauczycielem: 6 
• • Uzasadnienie punktów ECTS:

  • Zajęcia kontaktowe z nauczycielem: 

    3 punkty ECTS,
    
    Zajęcia kontaktowe są bardzo istotne ale w koncepcji wykładu główny nacisk położony jest na pracę samodzielną studenta uzupełnioną kontaktami z nauczycielem przez Internet.

  • Zajęcia bez kontaktu z nauczycielem: 

    3 punkty ECTS
    
    Praca samodzielna studenta (praca w domu i w bibliotece uzupełniona kontaktami przez Internet) jest głównym sposobem opanowywania materiału przez słuchacza wykładu. Bardzo istotnym elementem wykładu jest duża ilość zadań i miniprojektów do samodzielnego rozwiązania. Miniprojekty mogą zostać rozszerzone do tzw. Projektu Zespołowego a ten z kolei do pracy dyplomowej.

  • • Sumaryczna liczba godzin pracy studenta: 60 
  • Łączna liczba punktów ECTS wynika z sumarycznej liczby godzin pracy studenta.