Kryptografia

Question 1

Kryptografia

Podaj różnice między kryptografią klasyczną (symetryczna) a kryptografią klucza publicznego.

Answer 1

Kryptografia symetryczna, znana również jako kryptografia klasyczna, wykorzystuje ten sam klucz do szyfrowania i deszyfrowania danych. Obie strony muszą dzielić się kluczem w bezpieczny sposób, co może być wyzwaniem, szczególnie w dużych sieciach.

Kryptografia klucza publicznego, znana także jako asymetryczna, używa pary kluczy:
* klucz publiczny jest udostępniany wszystkim
* klucz prywatny jest trzymany w tajemnicy przez właściciela.

Klucze są matematycznie powiązane: coś zaszyfrowane kluczem publicznym można odszyfrować tylko odpowiadającym mu kluczem prywatnym i odwrotnie.

Question 2

Kryptografia

Podaj nazwy dwóch głównych, przeciwstawnych sobie, gałęzi kryptologii. Scharakteryzuj krótko co jest przedmiotem ich badań.

Answer 2

Kryptografia jest gałęzią kryptologii zajmującą się projektowaniem algorytmów i systemów do zabezpieczania informacji przed nieautoryzowanym dostępem. Przedmiotem jej badań są różne metody szyfrowania, uwierzytelniania i zapewniania integralności danych.

Kryptoanaliza to druga gałąź kryptologii, która skupia się na badaniu metod łamania szyfrów i atakach na systemy kryptograficzne. Kryptoanalitycy próbują znaleźć słabe punkty w algorytmach i wykorzystywać je do odszyfrowania informacji bez znajomości klucza.

Question 3

Kryptografia

Bartek ma dwie kłódki zamykane kodami. Alicja twierdzi, że zna kod otwierający jedną z nich. Zaproponuj dowód o wiedzy zerowej przekonujący Bartka, że Alicja rzeczywiście zna kod otwierający jedną z kłódek. Bartek nie powinien poznać kodu ani uzyskać wiedzy, którą kłódkę potrafi otworzyć Alicja.

Answer 3

Alicja może użyć interaktywnego protokołu o wiedzy zerowej, by udowodnić Bartkowi, że zna kod, nie ujawniając go ani nie wskazując, którą kłódkę potrafi otworzyć. Przykładowo:

1. Bartek wychodzi z pokoju, a Alicja otwiera jedną z kłódek (wybraną przez siebie) i wkłada tam kartkę z napisem “Alicja zna kod”.
2. Alicja zamyka kłódkę i czeka na powrót Bartka.
3. Bartek wchodzi do pokoju i wskazuje jedną z kłódek do otwarcia.
4. Alicja albo otwiera wskazaną kłódkę (jeśli to ta, którą wcześniej otworzyła), albo prosi Bartka ponownie o wyjście, aby zamienić kartkę do drugiej kłódki, zamykając ją z powrotem. Proces może być powtórzony kilka razy.

Jeśli Alicja może zawsze odpowiedzieć na wybór Bartka, dowodzi to, że zna kod do jednej z kłódek, bez ujawniania, która to kłódka lub jaki to kod.

Question 4

Kryptografia

W oparciu o jaki trudny obliczeniowo problem matematyczny działa kryptosystem RSA?

Answer 4

Kryptosystem RSA opiera się na trudnym obliczeniowo problemie matematycznym znanym jako rozkład liczby całkowitej na czynniki pierwsze.

Problem ten polega na znalezieniu dwóch różnych liczb pierwszych, których iloczyn daje dużą liczbę całkowitą. Znalezienie tych liczb pierwszych jest stosunkowo łatwe, nawet dla bardzo dużych liczb. Natomiast odwrotny problem, czyli rozłożenie dużej liczby na czynniki pierwsze, jest bardzo trudny obliczeniowo.

Question 5

Kryptografia

Kryptografia klucza publicznego rozwinęła się w połowie lat 70 XX wieku równolegle z rozwojem teorii złożoności obliczeniowej. Objaśnij co bada złożoność obliczeniowa.

Answer 5

Złożoność obliczeniowa to dziedzina informatyki teoretycznej i matematyki, która bada efektywność algorytmów w kontekście zasobów potrzebnych do wykonania danego zadania. Zasobami tymi mogą być czas obliczeniowy (złożoność czasowa) lub ilość zużywanej pamięci (złożoność pamięciowa).

Złożoność obliczeniowa klasyfikuje algorytmy na podstawie ich efektywności i skuteczności, a także pomaga zrozumieć granice możliwości obliczeniowych – czyli jakie problemy można wydajnie rozwiązać za pomocą komputerów, a jakie są zbyt trudne i prawdopodobnie nierozwiązywalne przy obecnym stanie wiedzy.