Przeczytaj

Problem 1

Napisz program szyfrujący dany komunikat za pomocą szyfru polialfabetycznego (wykorzystaj algorytm Vigenère'a).

Przetestuj działanie programu dla słowa jawnego ULEWA oraz klucza szyfrującego MODA.

Specyfikacja problemu:

Dane:

wiadomosc – słowo jawne; łańcuch znaków

slowo_klucz – klucz szyfrujący; łańcuch znaków

Wynik:

szyfrogram – słowo tajne; łańcuch znaków

RQO4kIda0ndPq

Polecenie 1

Porównaj swoje rozwiązanie z zaprezentowanym w filmie.

R1Ugz7WqX453r1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Przykład 1

Napisz w języku Java algorytm, który korzystając z szyfru Vigenère’a, zaszyfruje wiadomość.

Łańcuch znaków do zaszyfrowania: „PROGRAM”

Klucz: „KLUCZ”

W oparciu o tabelę, którą konstruowaliśmy w e‑materiale Szyfr polialfabetycznyPrHtFJ1fbSzyfr polialfabetyczny, spróbujmy zakodować słowo „PROGRAM” kluczem „KLUCZ”.

Weź poziomy rząd w tabeli, którego pierwszą literą jest „P” (pierwsza litera słowa do zaszyfrowania),
Weź pionowy rząd w tabeli, którego pierwszą litera jest „K” (pierwsza litera klucza).
Literą zaszyfrowana jest litera znajdująca się na przecięciu obu rzędów.
Weź kolejną literę słowa do zaszyfrowania oraz kolejną literę klucza i wróć do kroku nr 1 (w przypadku, gdy nie ma kolejnych liter klucza, należy wziąć pierwszą literę klucza).

Poniżej zostało przestawione graficzne rozwiązanie zadanego przykładu:

RBI1hiLSL4iu0

Animacja przedstawia szyfrowanie słowa: klucz. Przedstawia prostokątną tablicę o boku składającym się z dużych liter alfabetu. 1: Zaznaczono kolumnę pionową zaczynająca się na literę K oraz poziomą na literę A, przecięcie na literze K. 2: Zaznaczono kolumnę pionową zaczynająca się na literę L oraz poziomą na literę M, przecięcie na literze X. 3: Zaznaczono kolumnę pionową zaczynająca się na literę U oraz poziomą na literę O, przecięcie na literze I. 4: Zaznaczono kolumnę pionową zaczynająca się na literę C oraz poziomą na literę G, przecięcie na literze I. 5: Zaznaczono kolumnę pionową zaczynająca się na literę Z oraz poziomą na literę R, przecięcie na literze Q. — Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Implementacja w języku Java

Przejdźmy teraz do implementacji powyższego algorytmu, w postaci programu, w języku Java.

Do odwzorowania omówionej wcześniej tablicy użyjemy znanej już struktury danych – tablicy dwuwymiarowej.

static char[][] tabela = new char[26][26];

Zadeklarujemy również tablicę jednowymiarową alfabetLacinski o stałym rozmiarze 26, która będzie przechowywała kolejne litery alfabetu łacińskiego.

static char[] alfabetLacinski = new char[26];

Przejdźmy teraz do zadeklarowania funkcji odpowiedzialnej za utworzenie tablicy szyfrowania (dokładnie takiej, jak na powyższej grafice) oraz wyświetlenie jej na ekranie konsoli.

Funkcja przyjmie nazwę wypelnienieTablicy(), będzie typu void (nie zwracająca parametrów).

Funkcja nie będzie przyjmować żadnych parametrów.

static void wypelnienieTablicy() {
	
}

Następnym krokiem jest wypełnienie naszej tablicy jednowymiarowej alfabetLacinski kolejnymi literami alfabetu łacińskiego. Użyjemy do tego pętli oraz tablicy ASCII.

static void wypelnienieTablicy() {
    for (int i = 97, z = 0; i < 123; i++, z++) {
    	alfabetLacinski[z] = (char) i;
    }
}

Kolejnym krokiem jest wypełnienie tablicy dwuwymiarowej tabela tak, aby zgadzała się z tabelą przedstawioną na wcześniejszych grafikach. Będzie ona służyć do szyfrowania kolejnych liter.

static void wypelnienieTablicy() {
	for (int i = 97, z = 0; i < 123; i++, z++) {
		alfabetLacinski[z] = (char) i;
	}
	
	for (int j = 0; j < 26; j++) {

	}
}

W pierwszej pętli, której zmienną sterującązmienna sterującazmienną sterującą jest j, iterujemy po kolejnych wierszach tabeli, natomiast w drugiej pętli, której zmienną sterującą jest k, odbywa się iteracjach po wszystkich komórkach w danym wierszu – nadawane są kolejne wartości, zgodne z kolejnością w tabeli alfabet.

static void wypelnienieTablicy() {
	for (int i = 97, z = 0; i < 123; i++, z++) {
		alfabetLacinski[z] = (char) i;
	}
	
	for (int j = 0; j < 26; j++) {
		for (int k = 0; k < 26; k++) {
			tabela[j][k] = alfabetLacinski[k];
		}
	}	
}

W trzeciej pętli odbywa się zamiana kolejności liter w tabeli alfabet o jedną pozycję.

static void wypelnienieTablicy() {
	for (int i = 97, z = 0; i < 123; i++, z++) {
		alfabetLacinski[z] = (char) i;
	}
	
	for (int j = 0; j < 26; j++) {
		for (int k = 0; k < 26; k++) {
			tabela[j][k] = alfabetLacinski[k];
		}
		
		for (int l = 0; l < 26 - 1; l++) {
			char temp = alfabetLacinski[l];
			alfabetLacinski[l] = alfabetLacinski[l + 1];
			alfabetLacinski[l + 1] = temp;
		}
	}
}

Spróbujmy wypisać zawartość tabeli dwuwymiarowej, aby sprawdzić, czy jest ona zgodna z założeniami.

Linia 1. static void wypelnienieTablicy otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 2. for otwórz nawias okrągły int i znak równości 97 przecinek z znak równości 0 średnik i otwórz nawias ostrokątny 123 średnik i plus plus przecinek z plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 3. alfabetLacinski otwórz nawias kwadratowy z zamknij nawias kwadratowy znak równości otwórz nawias okrągły char zamknij nawias okrągły i średnik. Linia 4. zamknij nawias klamrowy. Linia 6. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny 26 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 7. for otwórz nawias okrągły int k znak równości 0 średnik k otwórz nawias ostrokątny 26 średnik k plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. tabela otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości alfabetLacinski otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 9. zamknij nawias klamrowy. Linia 11. for otwórz nawias okrągły int l znak równości 0 średnik l otwórz nawias ostrokątny 26 minus 1 średnik l plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. char temp znak równości alfabetLacinski otwórz nawias kwadratowy l zamknij nawias kwadratowy średnik. Linia 13. alfabetLacinski otwórz nawias kwadratowy l zamknij nawias kwadratowy znak równości alfabetLacinski otwórz nawias kwadratowy l plus 1 zamknij nawias kwadratowy średnik. Linia 14. alfabetLacinski otwórz nawias kwadratowy l plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy. Linia 18. for otwórz nawias okrągły int m znak równości 0 średnik m otwórz nawias ostrokątny 26 średnik m plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. for otwórz nawias okrągły int n znak równości 0 średnik n otwórz nawias ostrokątny 26 średnik n plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. System kropka out kropka print otwórz nawias okrągły tabela otwórz nawias kwadratowy m zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 23. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy.

static void wypelnienieTablicy() {
	for (int i = 97, z = 0; i < 123; i++, z++) {
		alfabetLacinski[z] = (char) i;
	}
	
	for (int j = 0; j < 26; j++) {
		for (int k = 0; k < 26; k++) {
			tabela[j][k] = alfabetLacinski[k];
		}
		
		for (int l = 0; l < 26 - 1; l++) {
			char temp = alfabetLacinski[l];
			alfabetLacinski[l] = alfabetLacinski[l + 1];
			alfabetLacinski[l + 1] = temp;
		}
	}
	
	for (int m = 0; m < 26; m++) {
		for (int n = 0; n < 26; n++) {
			System.out.print(tabela[m][n]);
		}
        
		System.out.println();
	}
}

Wynik konsoli:

abcdefghijklmnopqrstuvwxyz
bcdefghijklmnopqrstuvwxyza
cdefghijklmnopqrstuvwxyzab
defghijklmnopqrstuvwxyzabc
efghijklmnopqrstuvwxyzabcd
fghijklmnopqrstuvwxyzabcde
ghijklmnopqrstuvwxyzabcdef
hijklmnopqrstuvwxyzabcdefg
ijklmnopqrstuvwxyzabcdefgh
jklmnopqrstuvwxyzabcdefghi
klmnopqrstuvwxyzabcdefghij
lmnopqrstuvwxyzabcdefghijk
mnopqrstuvwxyzabcdefghijkl
nopqrstuvwxyzabcdefghijklm
opqrstuvwxyzabcdefghijklmn
pqrstuvwxyzabcdefghijklmno
qrstuvwxyzabcdefghijklmnop
rstuvwxyzabcdefghijklmnopq
stuvwxyzabcdefghijklmnopqr
tuvwxyzabcdefghijklmnopqrs
uvwxyzabcdefghijklmnopqrst
vwxyzabcdefghijklmnopqrstu
wxyzabcdefghijklmnopqrstuv
xyzabcdefghijklmnopqrstuvw
yzabcdefghijklmnopqrstuvwx
zabcdefghijklmnopqrstuvwxy

Jak widać (po wywołaniu funkcji wypelnienieTablicy w głównej funkcji programu main) powstała tabela jest zgodna z wcześniej omówioną tabelą, a więc możemy przejść do kolejnej części implementacji – szyfrowania za pomocą utworzonej tabeli.

W tym celu utwórzmy kolejną funkcję, nadajmy jej nazwę zaszyfruj() oraz nadajmy jej typ i przyjmowane parametry.

Funkcja powinna zwracać zaszyfrowany ciąg znaków, a więc powinna być łańcuchem znaków String. Przyjmowanymi parametrami będą dwa łańcuchy znaków String:

String doZaszyfrowania – podany ciąg znaków, który należy zaszyfrować,
String klucz – ciąg znaków określający klucz wedle jakiego będziemy szyfrować.

static String zaszyfruj(String doZaszyfrowania, String klucz) {
	String wynikSzyfrowania = "";
	
	for (int i = 0, j = 0; i < doZaszyfrowania.length(); i++) {
		wynikSzyfrowania += tabela[(int)(doZaszyfrowania.charAt(i) - 97)][(int)(klucz.charAt(j) - 97)];

		if (j == klucz.length() - 1) {
			j = 0;
		} else {
			j++;
		}
	}
	
	return wynikSzyfrowania;
}

Następnie należy wykonać iterację po słowie do zaszyfrowania i w każdej kolejnej iteracji nadpisywać zmienną wynikSzyfrowania o odpowiednia literę. Następujący fragment kodu:

[(int)(doZaszyfrowania.charAt(i) - 97)][(int)(klucz.charAt(j) - 97)]

określa komórkę w tabeli, która leży na przecięciu określonego rzędu i wiersza.

static String zaszyfruj(String doZaszyfrowania, String klucz) {
	String wynikSzyfrowania = "";
	
    for (int i = 0, j = 0; i < doZaszyfrowania.length(); i++) {
    		wynikSzyfrowania += tabela[(int)(doZaszyfrowania.charAt(i)-97)][(int)(klucz.charAt(j)-97)];
			
            j++;
    }
	
	return wynikSzyfrowania;
}

Może się zdarzyć, że klucz, wedle jakiego szyfrujemy, będzie krótszy niż słowo do zaszyfrowania. W takim przypadku tworzymy warunek – gdy do szyfrowania użyjemy ostatniego znaku klucza, zerujemy zmienną iterującą po kolejnych znakach klucza.

static String zaszyfruj(String doZaszyfrowania, String klucz) {
	String wynikSzyfrowania = "";
	
    for (int i = 0, j = 0; i < doZaszyfrowania.length(); i++) {
    		wynikSzyfrowania += tabela[(int)(doZaszyfrowania.charAt(i)-97)][(int)(klucz.charAt(j)-97)];

        if (j == klucz.length() - 1) {
            j = 0;
        } else {
            j++;
        }
    }
	
	return wynikSzyfrowania;
}

Wywołajmy teraz obie funkcje. Jako słowo do zaszyfrowania podajmy ciąg znaków „PROGRAM”, natomiast jako wartość klucza przyjmijmy „KLUCZ”.

public static void main(String[] args) {
	wypelnienieTablicy();
	System.out.println(zaszyfruj("program", "klucz"));
}

Wynik działania programu:

abcdefghijklmnopqrstuvwxyz
bcdefghijklmnopqrstuvwxyza
cdefghijklmnopqrstuvwxyzab
defghijklmnopqrstuvwxyzabc
efghijklmnopqrstuvwxyzabcd
fghijklmnopqrstuvwxyzabcde
ghijklmnopqrstuvwxyzabcdef
hijklmnopqrstuvwxyzabcdefg
ijklmnopqrstuvwxyzabcdefgh
jklmnopqrstuvwxyzabcdefghi
klmnopqrstuvwxyzabcdefghij
lmnopqrstuvwxyzabcdefghijk
mnopqrstuvwxyzabcdefghijkl
nopqrstuvwxyzabcdefghijklm
opqrstuvwxyzabcdefghijklmn
pqrstuvwxyzabcdefghijklmno
qrstuvwxyzabcdefghijklmnop
rstuvwxyzabcdefghijklmnopq
stuvwxyzabcdefghijklmnopqr
tuvwxyzabcdefghijklmnopqrs
uvwxyzabcdefghijklmnopqrst
vwxyzabcdefghijklmnopqrstu
wxyzabcdefghijklmnopqrstuv
xyzabcdefghijklmnopqrstuvw
yzabcdefghijklmnopqrstuvwx
zabcdefghijklmnopqrstuvwxy
zciiqkx

Po porównaniu z wcześniej omówionym przykładem teoretycznym, zauważamy, że program szyfruje w sposób prawidłowy.

Oto kod całego programu:

Linia 1. public class VigenereCipher otwórz nawias klamrowy. Linia 3. static char otwórz nawias kwadratowy zamknij nawias kwadratowy alfabetLacinski znak równości new char otwórz nawias kwadratowy 26 zamknij nawias kwadratowy średnik. Linia 4. static char otwórz nawias kwadratowy zamknij nawias kwadratowy otwórz nawias kwadratowy zamknij nawias kwadratowy tabela znak równości new char otwórz nawias kwadratowy 26 zamknij nawias kwadratowy otwórz nawias kwadratowy 26 zamknij nawias kwadratowy średnik. Linia 7. static void wypelnienieTablicy otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 8. for otwórz nawias okrągły int i znak równości 97 przecinek z znak równości 0 średnik i otwórz nawias ostrokątny 123 średnik i plus plus przecinek z plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 9. alfabetLacinski otwórz nawias kwadratowy z zamknij nawias kwadratowy znak równości otwórz nawias okrągły char zamknij nawias okrągły i średnik. Linia 10. zamknij nawias klamrowy. Linia 12. for otwórz nawias okrągły int j znak równości 0 średnik j otwórz nawias ostrokątny 26 średnik j plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. for otwórz nawias okrągły int k znak równości 0 średnik k otwórz nawias ostrokątny 26 średnik k plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. tabela otwórz nawias kwadratowy j zamknij nawias kwadratowy otwórz nawias kwadratowy k zamknij nawias kwadratowy znak równości alfabetLacinski otwórz nawias kwadratowy k zamknij nawias kwadratowy średnik. Linia 15. zamknij nawias klamrowy. Linia 17. for otwórz nawias okrągły int l znak równości 0 średnik l otwórz nawias ostrokątny 26 minus 1 średnik l plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 18. char temp znak równości alfabetLacinski otwórz nawias kwadratowy l zamknij nawias kwadratowy średnik. Linia 19. alfabetLacinski otwórz nawias kwadratowy l zamknij nawias kwadratowy znak równości alfabetLacinski otwórz nawias kwadratowy l plus 1 zamknij nawias kwadratowy średnik. Linia 20. alfabetLacinski otwórz nawias kwadratowy l plus 1 zamknij nawias kwadratowy znak równości temp średnik. Linia 21. zamknij nawias klamrowy. Linia 22. zamknij nawias klamrowy. Linia 24. for otwórz nawias okrągły int m znak równości 0 średnik m otwórz nawias ostrokątny 26 średnik m plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. for otwórz nawias okrągły int n znak równości 0 średnik n otwórz nawias ostrokątny 26 średnik n plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. System kropka out kropka print otwórz nawias okrągły tabela otwórz nawias kwadratowy m zamknij nawias kwadratowy otwórz nawias kwadratowy n zamknij nawias kwadratowy zamknij nawias okrągły średnik. Linia 27. zamknij nawias klamrowy. Linia 28. System kropka out kropka println otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 29. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 33. static String zaszyfruj otwórz nawias okrągły String doZaszyfrowania przecinek String klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. String wynikSzyfrowania znak równości cudzysłów cudzysłów średnik. Linia 36. for otwórz nawias okrągły int i znak równości 0 przecinek j znak równości 0 średnik i otwórz nawias ostrokątny doZaszyfrowania kropka length otwórz nawias okrągły zamknij nawias okrągły średnik i plus plus zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. wynikSzyfrowania plus znak równości tabela otwórz nawias kwadratowy otwórz nawias okrągły int zamknij nawias okrągły otwórz nawias okrągły doZaszyfrowania kropka charAt otwórz nawias okrągły i zamknij nawias okrągły minus 97 zamknij nawias okrągły zamknij nawias kwadratowy otwórz nawias kwadratowy otwórz nawias okrągły int zamknij nawias okrągły otwórz nawias okrągły klucz kropka charAt otwórz nawias okrągły j zamknij nawias okrągły minus 97 zamknij nawias okrągły zamknij nawias kwadratowy średnik. Linia 39. if otwórz nawias okrągły j znak równości znak równości klucz kropka length otwórz nawias okrągły zamknij nawias okrągły minus 1 zamknij nawias okrągły otwórz nawias klamrowy. Linia 40. j znak równości 0 średnik. Linia 41. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 42. j plus plus średnik. Linia 43. zamknij nawias klamrowy. Linia 44. zamknij nawias klamrowy. Linia 46. return wynikSzyfrowania średnik. Linia 47. zamknij nawias klamrowy. Linia 49. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 50. wypelnienieTablicy otwórz nawias okrągły zamknij nawias okrągły średnik. Linia 51. System kropka out kropka println otwórz nawias okrągły zaszyfruj otwórz nawias okrągły cudzysłów program cudzysłów przecinek cudzysłów klucz cudzysłów zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 52. zamknij nawias klamrowy. Linia 54. zamknij nawias klamrowy.

public class VigenereCipher {

	static char[] alfabetLacinski = new char[26];
	static char[][] tabela = new char[26][26];
	
	
    static void wypelnienieTablicy() {
        for(int i = 97, z = 0; i < 123; i++, z++) {
            alfabetLacinski[z] = (char) i;
        }

        for(int j = 0; j < 26; j++) {
            for(int k = 0; k < 26; k++) {
                tabela[j][k] = alfabetLacinski[k];
            }

            for(int l = 0; l < 26 - 1; l++) {
                char temp = alfabetLacinski[l];
                alfabetLacinski[l] = alfabetLacinski[l + 1];
                alfabetLacinski[l + 1] = temp;
            }
        }

        for(int m = 0; m < 26; m++) {
            for(int n = 0; n < 26; n++) {
                System.out.print(tabela[m][n]);
            }
            System.out.println();
        }

    }

    static String zaszyfruj(String doZaszyfrowania, String klucz) {
        String wynikSzyfrowania = "";

        for (int i = 0, j = 0; i < doZaszyfrowania.length(); i++) {
            wynikSzyfrowania += tabela[(int)(doZaszyfrowania.charAt(i)-97)][(int)(klucz.charAt(j)-97)];

            if (j == klucz.length() - 1) {
                j = 0;
            } else {
                j++;
            }
        }

        return wynikSzyfrowania;
    }
	
	public static void main(String[] args) {
		wypelnienieTablicy();
		System.out.println(zaszyfruj("program", "klucz"));
	}

}

Słownik

iteracja

słowo pochodzące od łacińskiego iteratio (powtarzanie); oznacza powtarzanie w pętli tych samych instrukcji, aż do spełnienia pewnego warunku

zmienna sterująca

zmienna przechowująca numer cyklu wykonywanego przez pętlę

Wprowadzenie

Animacja

Implementacja w języku Java

Słownik