80820 Str050 (2)

%    3. Kryptogrnfifl

Przypadek (iii). JcAli r i d nic są jednocześnie po dzielne przez m, u

przyjmujemy

i postępujemy tak jak w przypadku (ii). Te trzy

przypadki wyczerpują wszystkie możliwości. Zatem z zaprzeczenia (a) wynjfc. zaprzeczenie (c). To kończy dowód twierdzenia 3.2.1.

Przykład 2. Rozwiążmy następujące układy kongruencji:

(a)    2jc + 3y s I (mod 26),

7x + 8y a 2 (mod 26);

(b)    x + 3y s 1 (mod 26), lx *f 9j> s 2 (mod 26);

(c)    x + 3y s 1 (mod 26),

7x + 9y s 1 (mod 26).

Rozwiązanie. Układ (a) ma postać macierzową AX = B (mod 26), gdzie A jest

macierzą z przykładu 1, X =

|. Układ ten ma jedno rozwiązanie

X==A~ⁱB =

(mod 26).

Macierz układów (b) i (c) nie ma macierzy odwrotnej, gdyż jej wyznacznik, równy 14, ma wspólny czynnik 2 z modułem 26. Jednakże możemy rozważać kongrucncje modulo 13 i zobaczyć, czy rozwiązanie modulo 13 daje rozwiązanie modulo 26. Rozwiązanie modulo 13 otrzymujemy ze wzoru

żliwości modulo 26, stwierdzamy, że układ (b) nie ma rozwiązań, a układ (c) ma dwa rozwiązania: x = 6, y = 7 i x = 19, y — 20.

w przypadku (c)). To daje

(mod 13). Sprawdzając te mo-

Innym sposobem rozwiązywania układów kongruencji (szczególnie wtedy, gdy macierz układu nie jest odwracalna) jest eliminowanie jednej niewiadomej (np. w układach (b) i (c) można odjąć pierwszą kongruencję pomnożoną przez 7 od drugiej).

Powracając do kryptografii, widzimy z twierdzenia 3.2.1, że możemy uzyskać przekształcenie szyfrujące naszych wektorów-digramów, używając

do tego macierzy /le Af₂(Z/N&), której wyznacznik nie ma wspólnych dzielników z AT:

Mianowicie każda jednostka tekstu P = zgodnie ze wzorem

jest zaszyfrowana jako C =

C = AP, czyli

Aby odszyfrować wiadomość, po prostu korzystamy z macierzy odwrotnej:

Przykład 3. Używając alfabetu 26-literowego, zaszyfrujmy wiadomość „NO” za pomocą macierzy A z przykładu 1.

Rozwiązanie. Mamy

a więc wektor C = AP odpowiada digramowi „QV”.

Uwaga. Aby zaszyfrować tekst otwarty składający się z k digramów P = P_lP₂p2— P*, możemy zapisać te k wektorów jako kolumny macierzy o wymiarach 2 x k, którą także oznaczymy przez P, a następnie mnożymy macierz A przez macierz P, otrzymując macierz C = /4P, o wymiarach 2 x k, której kolumnami są zaszyfrowane wektory-digramy.

Przykład 4. Kontynuując przykład 3, zaszyfrujmy wiadomość „NOANS-WER” (bez odpowiedzi).

Rozwiązanie. Odpowiednikiem liczbowym wiadomości „NOANSWER” jest

ciąg wektorów

|. Mamy więc

/2 3    13 0 18 4 \ /68 39 102 59\ /16 13 24 7\

- .4P - ^7 g    _{14 13} 22 17/ \203 104 302 164/ \2I 0 16 8/ czyli wiadomość zaszyfrowana ma postać „QVNAYQHr\