64783 Str054 (2)

HM 3. Kryptogrifla

(por. ćwiczenie 10 do podrozdziału 1.2). Używając macierzowej postaci definicji, udowodnij, że liczba f_% jest parzysta wtedy i tylko wtedy, gdy liczba n jest podziclna przez 3. Ogólniej, udowodnij, że liczba f„ jest po-dzielna przez a wtedy i tylko wtedy, gdy liczba n jest podzielna przez b dla następujących a i b: (a) a = 2, b = 3; (b) a = 3, b = 4; (c) a = 5, b = 5; (d) a * 7, b = 8; (e) a = 8, b = 6; (0 a = 11, b = 10.

7.    Przechwyciłeś wiadomość „SONAFQCHMWPTVEVY”, o której wiesz, że powstała przez zastosowanie liniowego przekształcenia szyfrującego wc-ktorów-digramów, przy czym nadawca używał 26-literowego alfabetu A-Z z odpowiednikami liczbowymi 0-25. Analiza statystyczna przechwyconego wcześniej długiego kryptogramu wykazała, że najczęściej występującymi digramami kryptogramu są „KH" i „XW”, w tej kolejności. Odgadujesz, że te digramy odpowiadają digramom „TH” i „HE”, najczęściej występującym w większości długich tekstów otwartych na temat, którego spodziewasz się w przechwyconej wiadomości. Znajdź macierz rozszyfrowującą i odczytaj wiadomość.

8.    Przechwyciłeś wiadomość „ZRIXXYVBMNPO”, o której wiesz, że powstała przez zastosowanie liniowego przekształcenia szyfrującego wekto-rów-digramów 27-literowego alfabetu, w którym litery A-Z mają odpowiedniki liczbowe 0-25, a odstęp ma odpowiednik 26. Stwierdziłeś, że najczęściej występującymi digramami kryptogramu są „PK” i „RZ”. Przypuszczasz, że odpowiadają one najczęściej występującym digramom tekstów jawnych zapisanych za pomocą tego 27-literowego alfabetu, mianowicie „E ” (litera E, po której następuje odstęp) oraz „S ”. Znajdź macierz rozszyfrowującą i odczytaj wiadomość.

9.    Przechwyciłeś wiadomość „!IWGVIEX!ZRADRYD”, która powstała przez zaszyfrowanie za pomocą przekształcenia liniowego wektorów--digramów 29-literowego alfabetu, w którym litery A-Z mają odpowiedniki 0-25, odstęp = 26, ? = 27,! = 28. Wiesz, że ostatnie pięć liter kryptogramu to podpis nadawcy „MARIA”.

(a)    Znajdź macierz rozszyfrowującą i odczytaj wiadomość.

(b)    Znajdź macierz szyfrującą i podszywając się pod przyjaciela Marii, Jo, nadaj następującą wiadomość zaszyfrowaną w ten sam sposób: „DAMN FOG! JO”.

10.    W tym ćwiczeniu znów używamy alfabetu rosyjskiego (por. ćwiczenie 12 w poprzednim podrozdziale). Używamy alfabetu 34-literowego, w którym oprócz liter mamy jeszcze odstęp z odpowiednikiem liczbowym 33. Załóżmy, że nadal najczęściej występującymi digramami języka rosyjskiego będą „HO” oraz „ET”. Jednocześnie stwierdziliśmy, że digramami występującymi najczęściej w długim kryptogramic są „IOT” i „4M”. Wiemy, że szyfrowanie odbywa się za pomocą przekształceń liniowych wektorów digra-

mów tego 34-1 i terowego alfabetu. Odczytaj przechwyconą wiadomość

,,CXHC'hWOHir.(3^M.

11.    Udowodnij, że złożenie (por. ćwiczenie 14 w poprzednim podrozdzale) systemu kryptograficznego opartego na macierzy szyfrującej /f,eA/₂(Z/NZ)* i systemu kryptograficznego opartego na macierzy szyfrującej A_zeM_z(ZINZ)* jest też systemem kryptograficznym opartym na przekształceniu liniowym.

12.    Aby zwiększyć trudności związane ze złamaniem systemu kryptograficznego, postanawiasz szyfrować wektory-digramy 26-literowego alfabetu,

najpierw mnożąc je przez macierz

modulo 26, a następnie mnożąc

przez macierz

10 15 5 9

modulo 29. (Zauważ, że mnożenie przez dwie ma

cierze z tym samym modułem jest równoważne mnożeniu przez jedną macierz, jak już widzieliśmy to w ćwiczeniu 11; jednakże zmiana modułu w tym dwustopniowym szyfrowaniu znacznie komplikuje system kryptograficzny). Zatem Twoje teksty otwarte są napisane za pomocą alfabetu 26-literowego, kryptogramy zaś za pomocą alfabetu 29-literowego, którego używaliśmy w ćwiczeniu 9.

(a)    Zaszyfruj wiadomość „SEND” (wyślij).

(b)    Opisz, w jaki sposób należy rozszyfrowywać kryptogramy, mnożąc je kolejno przez dwie macierze, i rozszyfruj „ZMOY”.

13.    Udowodnij, że jeśli macierz nieodwracalna AeM₂(ZINl) została użyta do szyfrowania według wzoru C = AP, to każdy kryptogram może być rozszyfrowany na dwa różne sposoby, tak jakby pochodził od dwóch różnych tekstów otwartych.

14.    Przechwyciłeś wiadomość „S GNLIKD?KOZQLLIOMKUL.VY” (odstęp po literze S wchodzi w skład wiadomości). Załóż, że zostało użyte liniowe przekształcenie szyfrujące C = AP 30-literowego alfabetu, w którym litery A-Z mają liczbowe odpowiedniki 0-25, odstęp = 26, . = 27, , = 28, ? = 29. Wiesz także, że ostatnie sześć liter tekstu otwartego tworzy podpis KARLA, zakończony kropką. Znajdź macierz rozszyfrowującą A ”¹ i odczytaj wiadomość.

15.    Przechwyciłeś wiadomość „KVW? TA!KJB?FVR ”. (Odstępy po ? i po R wchodzą w skład wiadomości, ostatnia kropka nie). Wiesz, że użyto liniowego przekształcenia szyfrującego 30-literowego alfabetu, w którym litery A-Z mają liczbowe odpowiedniki 0-25, odstęp = 26, ? = 27,! = 28, . = 29. Wiesz także, że pierwsze sześć liter tekstu otwartego to „C.I.A.”. Znajdź macierz rozszyfrowującą A “¹ i odczytaj wiadomość.

16.    Przypuśćmy, że N = mn, gdzie NWD(m> n) = 1. Każda macierz A eA/₂(Z/jVZ) może być rozpatrywana w A/₂(Z/mZ) lub A/₂(Z/rcZ), gdy jej wyrazy zredukuje się modulo m lub n. Niech A i A oznaczają odpowiednie macierze w M₂(Z/mZ) i A/₂(Z/nZ).