67642 Str047 (2)

90 3 Kryptografia

brane module A'. Jeśli na przykład używamy alfabetu 26-1 i terowego A-Z z od.

powiednikami liczbowymi 0-25, to digramowi NO odpowiada wektor Przyjrzyjmy się poniższemu wykresowi.

ND

NO

Każdy digram P jest przedstawiony w postaci punktu w tablicy kwadratowej o wymiarach NxN. Inaczej mówiąc mamy tu do czynienia z układem współrzędnych kartczjańskich, z tą tylko różnicą, że osie nie są osiami rzeczywistymi, ale są kopiami Z/NZ. Tak samo, jak płaszczyzna z kartezjańskim układem współrzędnych jest oznaczana symbolem R², ta tablica o wymiarach NxN będzie oznaczana symbolem (Z/NZ)².

Z chwilą gdy przedstawiliśmy digramy w postaci wektorów (punktów na płaszczyźnie), będziemy interpretować przekształcenia szyfrujące jako przekształcenia tej tablicy w siebie. Dokładniej, przekształcenie szyfrujące jest funkcją różnowartościową ze zbioru (Z/NZ)² w ten sam zbiór.

Uwaga. Przez wiele stuleci jednym z najbardziej popularnych systemów kryptograficznych był tzw. „szyfr Vigenere’a”. Można go opisać w następujący sposób. Dla ustalonego k bloki k-literowe traktujemy jako wektory w przestrzeni (Z[NZ)^k, Wybieramy pewien ustalony wektor be(Z/NZ)^k (zazwyczaj b jest wektorem odpowiadającym jakiemuś łatwemu do zapamiętania „słowu kluczowemu”) i szyfrujemy za pomocą przesunięcia o wektor b: C = P + b (gdzie jednostka kryptogramu C i jednostka tekstu otwartego P są ciągami k liczb modulo N). Ten system kryptograficzny jest jednakże prawie tak samo łatwy do złamania jak system oparty na przesunięciu pojedynczych liter (por. ćwiczenie 1 z poprzedniego podrozdziału). Mianowicie, jeśli znane są N i k (lub odgadniemy je), to po prostu rozbijamy kryptogram na bloki po k liter i za pomocą analizy częstości liter wśród pierwszych liter wszystkich bloków ustalamy pierwszą literę b, potem tak samo ustalamy drugą literę b itd.

12. M tóatt nyfmjice    91

Przegląd metod algebry liniowej. Przypomnimy teraz, w jaki sposób posługujemy się wektorami na płaszczyźnie i macierzami 2/2 o wyrazach rzeczy-

na

wjstych. Dla danej macierzy 2/2 liczb rzeczywistych

plaszczyźnie (wektory zapisujemy w postaci kolumn) możemy rozważać iloczyn macierzy przez wektor. Jest on wektorem określonym następująco:

\c d)\y)tirf\cjc + dy)

Dla ustalonej macierzy tę funkcję, przeprowadzającą jeden wektor na drugi, nazywamy przekształceniem liniowym, co oznacza, że zachowuje ona sumy wektorów i iloczyny przez liczby. Zgodnie z tymi oznaczeniami, każdy układ równań postaci ax + by - e, cx + dy = /jest równoważny jednemu równaniu zapisanemu w postaci macierzowej AX = B, gdzie A oznacza macierz

X oznacza wektor niewiadomych ( La B oznacza wektor wyrazów wolnych

miany jako żądanie znalezienia wektora, który po pomnożeniu przez pewną znaną macierz da w wyniku pewien znany wektor. Zatem mamy tu analogię do prostych równań ax = b, które rozwiązujemy, mnożąc obie strony przez a^-1 (przy założeniu, że a ź 0). Podobnie, jedna z metod rozwiązywania równań macierzowych AX == B polega na znalezieniu macierzy odwrotnej do A i pomnożeniu obu stron przez A'¹. W ten sposób otrzymujemy jedyne rozwiązanie, którym jest wektor X= A~¹B.

Macierz odwrotna do macierzy A to macierz, która po pomnożeniu przez A daje macierz jednostkową

(czyli macierz taką, że jej iloczyn z dowolnym wektorem nie zmienia tego wektora). Ale nie wszystkie macierze mają macierze odwrotne. Nietrudno dowieść, że macierz

ma macierz odwrotną wtedy i tylko wtedy, gdy jej wyznacznik D = ad- bejest różny od zera oraz że ta macierz odwrotna jest wtedy równa