IMG964 (4)

Takie szyfry są niepraktyczne

Wyjątki: korespondencja dyplomatyczna i wojskowa Szyfry stosowane w praktycejnp. t=10000000 i a =0,0000001)

Powszechnie używane są szyfry: RSA, DES, AES.

Hipoteza P= NP -> algorytm dla pewnej klasy problemów. Hipoteza dotycz szybkich algorytmów działających w czasie wielomianowym.

Algorytm RSA

•    jednym z 1. i najpopularniejszych asymetrycznych algorytmów kryptograficznych

•    kryptografia klucza publicznego to rodzaj kryptografii który używa się zestawu dwu lub więcej powiązanych kluczy umożliwiających wykonanie wielu czynności kryptograficznych. Jeden może być udostępniony publicznie bez utraty bezpieczeństwa

•    pierwszy który można było używać do szyfrowania i podpisów szyfrowych

•    bezpieczeństwo szyfrów opiera się na trudności faktoryzacji

Generowanie kluczy:

Wybieramy dwie liczby pierwsze p i q Obliczamy n=pq

Obliczamy wartość Eulera <p(n)= (p-l)(q-l) wybieramy liczbę e(l<e<rp(n)) pierwszą z <p(n)

Znajdujemy liczbę d odwrotną do e mod <p(n) d=e-lmod tp(n)

Klucz publiczny jest definiowany jako para liczb (n,e) natomiast kluczem prywatnym jest para (n,d)

Problem korni wojażera

Podróż z miasta do miasta sprzedając swoje produkty. Wyrusza z rodzinnego miasta po czym jego trasa przebiega dokładnie jeden raz przez każde miasto.

Miasta to wierzchołki grafów a trasy to krawędzie z wagami

Waga krawędzi odpowiada odległości pomiędzy miastami

Problem jest oparty o cykl Hammiłtona.

Przykład:

Ile różnych cykli Hammiłtona zawiera taki graf:

• jedną krawędź cyklu można wybrać na 9 sposobów