Strona główna » Algorytmy » Szyfry » Szyfr Gromark
 

Szyfr Gromark

Zasady szyfrowania

Krótki wstęp

Szyfr Gromark pozwala na zaszyfrowanie dowolnego tekstu złożonego z liter alfabetu łacińskiego i istnieje możliwość rozszerzenie go o dodatkowe znaki. W celu zaszyfrowania danych należy użyć słowa kluczowego oraz pewnej liczby szyfrującej. Następnie na podstawie słowa kluczowego tworzy się nowy alfabet z którego litery wybiera się przy pomocy utworzonego klucza na podstawie liczby szyfrującej. Poniżej został przedstawiony dokładny opis szyfrowania.

Przyjmijmy, że szyfrowany będzie tekst "INFORMACJA" słowem kluczowym GROMARK i liczbą 876532.

Alfabet szyfrujący

Na początek należy wymyśleć pewne słowo kluczowe, które posłuży do utworzenia alfabetu szyfrującego. Słowo może być dowolne, ale wszystkie znaki nie uwzględnione w alfabecie powinny zostać usunięte. Następnie należy utworzyć tabelkę o szerokości n = 9 i do kolejnych wierszy należy wpisywać unikalne litery z słowa kluczowego, a potem w kolejności alfabetycznej litery, które nie wystąpiły w słowu kluczowym. Kolejny krok polega na ustawieniu kolumn alfabetycznie poprzez porównanie pierwszych elementów w kolumnie od góry. Alfabet szyfrujący odczytuje się kolejnymi kolumnami od góry do dołu po posortowaniu.

Przykładowo weźmy słowo kluczowe "GROMARK". Litera 'R' występuje dwa razy, dlatego jej drugie wystąpienie zostanie zignorowane. Wtedy utworzona tabelka będzie miała postać:

GROMAKBCD
EFHIJLNPQ
STUVWXYZ

Następnie zamieniając kolumny tak, aby były posortowane otrzymamy:

ABCDGKMOR
JNPQELIHF
WYZ SXVUT

Odczytujący kolejne kolumny otrzymujemy alfabet szyfrujący: AJWBNYCPZDQGESKLXMIVOHURFT.

Autoklucz

Liczba szyfrująca musi być conajmniej dwu cyfrowa, a im dłuższa tym bardziej skutecznie będzie szyfrowanie. Początkowo autoklucz jest równy liczbie szyfrującej. Tworzenie autoklucza na jej podstawie należy utworzenie klucza tak długiego jak długi jest tekst jawny. Dopóki jest mniej cyfr niż szyfrowanych znaków to należy sumować kolejną parę cyfr z autoklucza i cyfrę jedności wyniku dopisać na koniec autoklucza.

Przykładowo niech liczba szyfrująca to 876532. Tekst jawny ma długość 10, a klucz 6. Należy zatem wyliczyć cztery dodatkowe cyfry.

AutokluczWybrana paraKolejna cyfra
87653287(8 + 7) ≡10 5
876532576(7 + 6) ≡10 3
8765325365(6 + 5) ≡10 1
87653253153(5 + 3) ≡10 8
8765325318--

Utworzony klucz szyfrujący liczbowy to: 8765325318.

Szyfrowanie

Zestawiając otrzymane otrzymujemy tabelkę szyfrującą z alfabetem początkowym i docelowym:

NormalnyABCDEFGHIJKLMNOPQRSTUVWXYZ
NowyAJWBNYCPZDQGESKLXMIVOHURFT

Każdemu znakowi z tekstu jawnego przyporządkowujemy cyfrę z klucza szyfrującego:

Klucz szyfrujący8765325318
Tekst jawnyINFORMACJA

Teraz w celu otrzymania podstawienia za dowolną literę tekstu jawnego należy znaleźć dany znak w alfabecie Normalnym i przejść o tyle pozycji ile wynosi przyporządkowana cyfra do litery z Klucza Szyfrującego. Następnie należy odczytać z tej samej kolumny literę z alfabetu Nowego i dopisać do szyfrogramu znaleziony znak. Przykładowo szyfrując znak I szukamy go w alfabecie Normalnym i stoi na pozycji 10 i przesuwamy go o 8 pozycji czyli przechodzimy do kolumny 18. W alfabecie Normalnym byłoby to 'Q', ale teraz przechodzimy na Nowy alfabet czyli szukany znak to 'X'.

Kontynuując szyfrowanie w ten sposób dochodzimy do szyfrogramu: "XOGVOKYYQZ".

Implementacja

Założenia wstępne

Poniżej znajduje się przykładowy program, który szyfruje zgodnie z szyfrem Gromark. Używanym alfabetem jest alfabet łaciński złożony z samych wielkich liter. Program zakłada poprawność danych wejściowych.

Tworzenie alfabetu

Do utworzenia alfabetu szyfrującego służy funkcja utworzAlfabet(), która jako jedyny argument przyjmuje slowoKluczowe wczytane od użytkownika. Pierwszy etap polega na przygotowaniu tablicy liter w takiej kolejności w jakiej znalazłyby się w tabeli o pewnej szerokości n. Funkcja przewiduje, że szerokość tabeli może być różna.

  1. char* utworzAlfabet(char* slowoKluczowe) {
  2.   int n = 9;
  3.   int dlAlfabet = 'Z' - 'A' + 1;
  4.   int mn = ceil((double)(dlAlfabet) / (double)(n));
  5.   char* temp = new char[n*mn];
  6.   for (int i = 0; i < n*mn; i++)
  7.     temp[i] = '#';
  8.   int zapis = 0;
  9.   for (int i = 0; i < strlen(slowoKluczowe); i++) {
  10.     if (wyszukaj(temp, zapis, slowoKluczowe[i]) == -1)
  11.       temp[zapis++] = slowoKluczowe[i];
  12.   }
  13.   for (int i = 'A'; i <= 'Z'; i++) {
  14.     if (wyszukaj(temp, zapis, i) == -1)
  15.       temp[zapis++] = i;
  16.   }

Początkowo (2.) ustalana jest szerokość tabeli, (3.) długość alfabetu oraz (4.) ile wierszy miałaby tabela (tj. po ile będą grupowane liczby). (5. - 7.) Następnie tworzona jest tymczasowa tablica znaków i wypełniania znakiem '#', który pełni tu rolę domyślnego znaku w tabeli. (8.) Ze względu na to, że niekoniecznie i-ty znak słowa kluczowego będzie i-tym znakiem alfabetu, więc deklarowana jest dodatkowa zmienna zapis, która będzie kontrolować, gdzie jest ostatnia zapisana wartość alfabetu tymczasowego. Najpierw przepisywane (9. - 12.) są unikalne litery ze słowa kluczowego, a potem (13. - 16.) pozostałe litery z alfabetu w kolejności alfabetycznej.

Tak przygotowana tablica temp odpowiada tabeli czytanej wierszami po kolei od lewej do prawej. Kolejny etap polega teraz na zamianie "kolumn" tabeli można to zrobić poprzez podzielenie tablicy na n grup po mn elementów. Grupy będą zamieniane miejscami tylko, gdy pierwszy element grupy wymaga zamiany.

  1.   for (int i = 0; i < n; i++)
  2.     for (int j = 0; j < n; j++)
  3.       if (temp[i] < temp[j])
  4.         for (int k = 0; k < mn; k++)
  5.           swap(temp[i + n* k], temp[j + n* k]);
  6.   char* nowyAlfabet = new char[dlAlfabet + 1];
  7.   for (int i = 0, zapis = 0; i < n; i++) {
  8.     for (int k = 0; k < mn; k++) {
  9.       if (temp[i + n* k] != '#')
  10.         nowyAlfabet[zapis++] = temp[i + n* k];
  11.     }
  12.   }
  13.   nowyAlfabet[dlAlfabet] = '\0';
  14.   return nowyAlfabet;
  15. }

Zastosowany został tutaj (17. - 18.) algorytm sortowania bąbelkowego: (19.) porównywane są pierwsze elementy z każdej grupy. Jeśli zaistnieje potrzeba zamiany to (20. - 21.) zamieniane są całe grupy. Po posortowaniu pozostaje tylko utworzyć (22.) nowy alfabet. Długość należy zwiększyć o 1, aby na koniec (29.) dopisać znak końca danych. Algorytm (23. - 28.) wybiera kolejne grupy i przepisuje do nowej tablicy. (29.) Utworzony alfabet zostaje zwrócony.

Tworzenie autoklucza

W celu utworzenia klucz należy przekazać dwie informacje: liczba - zapisany w postaci ciągu znaków liczba szyfrująca oraz n - długość tekstu szyfrowanego.

  1. int* utworzKlucz(char* liczba, int n) {
  2.   int* autoklucz = new int[n];
  3.   int dl_liczba = strlen(liczba);
  4.   int i = 0;
  5.   for (; i < dl_liczba; i++)
  6.     autoklucz[i] = liczba[i] - '0';
  7.   for (; i < n; i++) {
  8.     int c = autoklucz[i + 1 - dl_liczba] + autoklucz[i - dl_liczba];
  9.     autoklucz[i] = c % 10;
  10.   }
  11.   return autoklucz;
  12. }

Testowanie funkcji

W celu sprawdzenia działania napisanych funkcji można skorzystać z poniższej funkcji main(), która