Prezentacja multimedialna

Zadanie 2. Podpis elektroniczny

Bajtek otrzymał od przyjaciela 500 jawnych wiadomości. Do każdej z nich przyjaciel dołączył podpis elektroniczny, będący zaszyfrowanym skrótem wiadomości. Skróty utworzył, przekształcając wiadomość w 8-znakowy napis. Następnie zaszyfrował ten skrót za pomocą algorytmu A o tylko sobie znanym kluczu prywatnym (e,n).

Bajtek chciałby odszyfrować wszystkie otrzymane skróty z użyciem algorytmu A, za pomocą ogólnie znanego klucza publicznego (d,n) o wartościach (3,200).

W pliku podpisy.txt znajduje się 500 wierszy, z których każdy zawiera 8 liczb całkowitych z przedziału [22, 162], stanowiących elementy podpisu elektronicznego jednej wiadomości. Liczby w wierszu oddzielone są pojedynczymi znakami odstępu. Kolejność wierszy podpisów jest zgodna z kolejnością wierszy wiadomości (pierwszy wiersz podpisów odpowiada pierwszej wiadomości, drugi — drugiej i tak dalej).

Algorytm A deszyfrowania kluczem publicznym (d,n)

Deszyfrowanie polega na wykonaniu operacji:

x=y·d mod n

gdzie za y należy przyjąć kolejne liczby tworzące podpis elektroniczny. Tekst wynikowy można otrzymać, składając w jeden napis reprezentacje graficzne kolejnych liczb x zgodnie ze standardem ASCII.

Algorytm A szyfrowania kluczem prywatnym (e,n)

Zaszyfrowanie za pomocą algorytmu A polega na wykonywaniu operacji:

y=x·e mod n

Za x należy podstawić kody ASCII kolejnych znaków tekstu źródłowego. Uzyskany w ten sposób ciąg liczb jest podpisem elektronicznym wiadomości. Gdyby ktoś chciał złamać szyfr A, czyli wyznaczyć nieznany element e klucza prywatnego, musiałby znaleźć taką wartość e, względnie pierwszą z d, że:

e⋅d mod n=1

Uzasadnienia szukaj w prawach arytmetyki modularnej.

Polecenie 1

Napisz program, który odszyfruje skróty wiadomości ze wszystkich podpisów elektronicznych umieszczonych w pliku podpisy.txt, stosując algorytm A z kluczem publicznym (d,n) = (3,200). Wyniki zapisz do pliku wynik2.txt, w takim samym formacie jak w pliku wejściowym (każdy znak oddzielony pojedynczym znakiem odstępu), zachowując oryginalne linijki.

R5cytRuQpO72C

Przycisk do pobrania pliku TXT z treścią zadania.

Plik TXT o rozmiarze 13.35 KB w języku polskim

Do oceny oddajesz:

  • plik wynik2.txt zawierający odpowiedź do zadania (odszyfrowane skróty wiadomości ze wszystkich podpisów elektronicznych),

  • plik(i) z komputerową realizacją zadania (kodem programu).

Polecenie 2

Przedstaw rozwiązanie w wybranym języku programowania: C++, Java lub Python. Odpowiedź dla danych z pliku znajdziesz pod prezentacją omawiającą kolejne kroki rozwiązania.

RQAXMcqrqewTM
x

Zadanie zostało opracowane na podstawie zadania nr 78, które pojawiło się w zbiorze zadań z informatyki przygotowanego przez Centralną Komisję Egzaminacyjną.

Rozwiązanie

Rozwiązanie zadania przedstawimy w postaci pseudokodu.

R9R8p9cdAx44t1
Źródło: Contentplus.pl sp. z o.o., licencja: CC BY-SA 3.0.
Ważne!

W pseudokodzie wykorzystaliśmy operator mod oraz funkcję znak():

  • mod – operator modulo, służy do obliczania reszty z dzielenia,

  • znak(a) – wypisuje znak odpowiadający liczbie a w kodzie ASCII.

Odpowiedź do zadania

Poprawna odpowiedź dla danych z pliku podpisy.txt zapisana jest w pliku wynik2.txt.

R1IrQPnNu2Aqp

Przycisk do pobrania pliku TXT z wynikiem zadania.

Plik TXT o rozmiarze 8.30 KB w języku polskim
Polecenie 3

Dodaj do napisanego przez siebie programu komentarze, aby nawet osoba, która nie potrafi programować, mogła go zrozumieć.

Przeczytaj
Sprawdź się