Kolumnowy Szyfr Przestawieniowy

Szyfr Kolumnowy jest szyfrem przestawieniowym. Jego działanie polega na przestawieniu pozycji liter oryginalnej wiadomości, bazując na tabeli wypełnionej literami w kolejności wskazanej przez sekretny klucz.

Zastosowanie

Kolumnowy Szyfr Przestawieniowy może być stosowany ręcznie, bez potrzeby używania dodatkowych urządzeń elektronicznych. Był znany od bardzo długiego czasu i używany w powszechnie w dwudziestym wieku przeróżnych sytuacjach przez dyplomatów, wojskowych i szpiegów.

Operacje szyfrowania i deszyfrowania za pomocą Kolumnowego Szyfru Przestawieniowego przeprowadza się zwykle na kartce papieru, na której rysuje się tabelę, zawierającą wszystkie litery przetwarzanej wiadomości.

Algorytm

Nazwa tego szyfru bierze się od operacji przeprowadzanych na tabeli podczas szyfrowania i deszyfrowania wiadomości. Liczba kolumn w tej tabeli jest określona przez sekretny klucz.

Kluczem sekretnym w Kolumnowym Szyfrze Przestawieniowym jest zwykle jedno słowo lub po prostu ciąg liter. Sekretne słowo należy przekonwertować na odpowiadający jemu ciąg liczb, o takiej samej długości. Wszystkie liczby określane są przez miejsca, jakie litery słowa zajmują w alfabecie. Literze sekretnego słowa, która zajmuje najniższe miejsce w alfabecie należy przypisać liczbę 1, druga z kolei litera alfabetu otrzyma numer 2, i tak dalej.

Jeżeli w słowie kluczowym znajduje się kilka identycznych liter, to każdemu kolejnemu pojawieniu się tej samej litery powinna zostać przypisana liczba o jeden większa niż liczba przypisana poprzedniemu pojawieniu się tej litery.

Przykładowo, jeśli za słowo kluczowe przyjmie się nazwę pewnego miasta w Anglii:
  SWINDON
to odpowiadająca mu sekwencja liczb będzie wynosić:
  6723154
Jak widać, litery N otrzymały odpowiednio liczby 3 (pierwsze wystąpienie) oraz 4 (drugie wystąpienie).

W celu zaszyfrowania wiadomości, wszystkie jej litery powinny zostać wpisane do tabeli, wierszami, od lewej do prawej. Wielkość tabeli zależy od długości wiadomości. Jedynym z góry określonym wymiarem jest szerokość tabeli, która jest zdefiniowana przez długość sekretnego słowa kluczowego (która równa jest długości ciągu liczb, utworzonego na jego podstawie). Sekretne słowo kluczowe jest oczywiście znane obu komunikującym się stronom.

Jeżeli po wpisaniu do tabeli całej wiadomości, niektóre pola w dolnym wierszu tabeli pozostały wolne, to jeden z dwóch możliwych sposobów traktowania ich może zostać wybrany:

  1. Komórki tabeli mogą pozostać puste i powinny być ignorowane podczas wszystkich późniejszych operacji szyfrowania.
  2. Nadawca może wpisać do nich jakieś rzadkie litery i podczas dalszego szyfrowania traktować je jako część tekstu jawnego. Po odszyfrowaniu, odbiorca powinien być w stanie określić, że te dodatkowe litery nie mają sensu i, że powinny zostać zignorowane.

Następnie, litery powinny zostać odczytane z tabeli w specyficzny sposób i dopisane do tworzonego szyfrogramu. Kolejność czytania liter jest określona przez ciąg numerów, zbudowany na podstawie słowa kluczowego. Należy ja odczytywać kolumnami, z góry do dołu, startując od kolumny, której pozycja odpowiada pozycji numeru 1 w ciągu numerów. Następna kolumna jest wskazana przez numer 2 w tym ciągu, i tak dalej, aż do odczytania liter za wszystkich kolumn tabeli. Aby ułatwić ten krok, zaleca się zapisanie numerów z ciągu nad odpowiadającymi im kolumnami.

Przykładowo, poniżej przedstawiono kroki, które należy wykonać, aby zaszyfrować tytuł jednej z komedii Szekspira A Midsummer Night's Dream. W tym celu wykorzystano sekretne słowo kluczowe przedstawione powyżej. Odpowiadający mu ciąg numerów wynosi 6723154, więc tabela, która będzie użyta podczas szyfrowania ma siedem kolumn.

Po usunięciu wszystkich znaków, które nie są literami, oraz zamienieniu wszystkich liter na wielkie litery, wiadomość powinna zostać wpisania do tabeli:

6723154
AMIDSUM
MERNIGH
TSDREAM

Nad wiadomością zapisano numery uzyskane ze słowa kluczowego. Określają one kolejność, w jakiej należy brać kolumny, z których następnie wszystkie litery powinny zostać odczytane (od góry do dołu) i dopisane do tworzonego szyfrogramu. W zaprezentowanym przykładzie jako pierwsza powinna zostać odczytana kolumna SIE, jako druga kolumna IRD, i tak dalej. Utworzony szyfrogram będzie wyglądał:
  SIE IRD DNR MHM UGA AMT MES

Wreszcie, po usunięciu spacji, które zostały dodane w celu zaznaczenia oddzielnych kolumn, otrzymuje się zaszyfrowaną wiadomość:
  SIEIRDDNRMHMUGAAMTMES

Aby odszyfrować otrzymany szyfrogram, odbiorca powinien wykonać następujące kroki:

  1. Znając sekretne słowo kluczowe oraz długość wiadomości, tabela o takiej samej długości, jaką miała tabela użyta do szyfrowania, powinna zostać utworzona.
  2. Szyfrogram powinien zostać wpisany do kolumn tabeli, poczynając od najbardziej lewej kolumny do najbardziej prawej, od góry do dołu.
  3. Kolumny powinny zostać poprzestawiane i umieszczone w pozycjach, w których powinny się znajdować według słowa kluczowego.
  4. Odszyfrowana wiadomość może zostać odczytana wierszami, startując od górnego wiersza, od lewej do prawej.

Siła Kolumnowego Szyfru Przestawieniowego

Kolumnowy Szyfr Przestawieniowy był wykorzystywane do poważnych celów na całym świecie, aż do początku drugiej połowy dwudziestego wieku.

Aby złamać ten szyfr, atakujący powinien zbudować szereg tabeli o różnych wielkościach, powpisywać do nich litery szyfrogramu (kolumnami), a następnie szukać w nich pojawiających się w wierszach anagramów rzeczywistych słów.

Implementacja

Szyfrowanie

Poniżej przedstawiono funkcje napisane w Pythonie, które umożliwiają szyfrowanie za pomocą Kolumnowego Szyfru Przestawieniowego. Parametrami wejściowymi są wiadomość i sekretne słowo kluczowe. Główna funkcja, szyfruj, wykorzystuje dwie funkcje pomocnicze w celu utworzenia tabeli i sekwencji liczb słowa kluczowego.

def szyfruj(wiadomosc, klucz):
  tabela = utworzTabeleSzyfrujaca(len(klucz), wiadomosc)
  kluczSequence = sekwencjaKlucza(klucz)

  szyfrogram = "";
  for num in range(len(kluczSequence)):
    pos = kluczSequence.index(num+1)
    for row in range(len(tabela)):
      if len(tabela[row]) > pos:
        szyfrogram += tabela[row][pos]
  return szyfrogram


def utworzTabeleSzyfrujaca(szerokosc, wiadomosc):
  r = 0
  c = 0
  tabela = [[]]
  for pos, ch in enumerate(wiadomosc):
    tabela[r].append(ch)
    c += 1
    if c >= szerokosc:
      c = 0
      r += 1
      tabela.append([])

  return tabela


def sekwencjaKlucza(klucz):
  sekwencja = []
  for pos, ch in enumerate(klucz):
    poprzednieLitery = klucz[:pos]
    nowyNumer = 1
    for prevPos, prevCh in enumerate(poprzednieLitery):
      if prevCh > ch:
        sekwencja[prevPos] += 1
      else:
        nowyNumer += 1
    sekwencja.append(nowyNumer)
  return sekwencja

Deszyfrowanie

Poniższe funkcję napisane w Pythonie umożliwiają deszyfrowanie szyfrogramów Kolumnowego Szyfru Przestawieniowego. Parametrami wejściowymi są wiadomość i sekretne słowo kluczowe. Główna funkcja, deszyfruj, wykorzystuje funkcje pomocnicze w celu utworzenia tabeli i sekwencji liczb słowa kluczowego.

def decrypt(wiadomosc, klucz):
  tabela = utworzTabeleDeszyfrujaca(sekwencjaKlucza(klucz), wiadomosc)

  tekstJawny = "";
  for r in range(len(tabela)):
    for c in range (len(tabela[r])):
      tekstJawny += tabela[r][c]
  return tekstJawny


def utworzTabeleDeszyfrujaca(kluczSequence, wiadomosc):
  szerokosc = len(kluczSequence)
  wysokosc = len(wiadomosc) / szerokosc
  if wysokosc * szerokosc < len(wiadomosc):
    wysokosc += 1

  tabela = utworzPustaTabele(szerokosc, wysokosc, len(wiadomosc))

  pos = 0
  for num in range(len(kluczSequence)):
    column = kluczSequence.index(num+1)

    r = 0
    while (r < len(tabela)) and (len(tabela[r]) > column):
      tabela[r][column] = wiadomosc[pos]
      r += 1
      pos += 1

  return tabela


def utworzPustaTabele(szerokosc, wysokosc, dlugosc):
  tabela = []
  iloscDodanych = 0
  for r in range(wysokosc):
    tabela.append([])
    for c in range(szerokosc):
      if iloscDodanych >= dlugosc:
        return tabela
      tabela[r].append('')
      iloscDodanych += 1
  return tabela


def sekwencjaKlucza(klucz):
  sekwencja = []
  for pos, ch in enumerate(klucz):
    poprzednieLitery = klucz[:pos]
    nowyNumer = 1
    for prevPos, prevCh in enumerate(poprzednieLitery):
      if prevCh > ch:
        sekwencja[prevPos] += 1
      else:
        nowyNumer += 1
    sekwencja.append(nowyNumer)
  return sekwencja