Budeme se zabývat úkolem, kdy na základě zadaného textového řetězce máme vytvořit jiný, ve kterém jsou některé znaky nahrazeny za jiné. Na úloze si procvičíme některé operace s řetězci a seznamy a ukážeme si některá použití.

Naším cílem je vytvořit funkci substituce, která obdrží tři parametry

1. text - textový řetězec, ve kterém budeme znaky nahrazovat,
2. co - znaky, které budeme nahrazovat, ve formě řetězce,
3. cim - znaky, kterými budeme nahrazovat, rovněž ve formě řetězce.

Pak znak původního řetězce nalezený v co je nahrazen znakem na odpovídající pozici v cim. Znaky, které v co obsaženy nejsou, jsou ponechány beze změny. Návratovou hodnotou funkce bude výsledný textový řetězec.

Je zřejmé, že pro rozumnou činnost této funkce by parametry co a cim měly mít stejnou délku a znaky v co by se neměly opakovat¹⁾.

Přímočará implementace funkce může vypadat například takto²⁾.

def substituce(text, co, cim):
    vysledek = "" # začneme s prázdným výsledkem
    for znak in text: # procházíme vstupní text
        index = co.find(znak) # test znaku v 'co'
        # do výsledku přidáme nahrazený/původní znak
        vysledek += cim[index] if index >= 0 else znak
    return vysledek

Na procvičení práce se seznamy vytvoříme ještě alternativní řešení - řetězec převedeme na seznam znaků, který budeme procházet a podle potřeby nahrazovat znaky. Nakonec znaky sloučíme zpět do řetězce.

def substituce(text, co, cim):
    vysledek = list(text) # budeme pracovat na seznamu
    for i in range(len(vysledek)):
        index = co.find(vysledek[i]) # je znak v 'co'?
        if index >= 0: # znak je třeba nahradit
            vysledek[i] = cim[index] # náhrada z 'cim'
    return "".join(vysledek) # vrátíme řetězec

Kód funkce je srovnatelně dlouhý a složitý, ale pro delší řetězce se ukazuje jako rychlejší. Důvodem je skutečnost, že opakované přidávání znaku na konec řetězce není příliš efektivní operace. Naproti tomu náhrada prvku v jednou vytvořeném seznamu příliš náročná není. V dalším budeme pokračovat s druhou variantou.

Jedním z reálných použití právě popsané funkce je odstranění diakritických znamének z českého textu. Důvodem může být nutnost použití nějakého staršího zařízení či komunikačního protokolu, kde jsou vyžadovány pouze ASCII znaky, přitom však požadujeme když už ne češtinu, tak alespoň „cestinu“.

Tuto práci pro nás udělá funkce hacky_carky. Jedná se vlastně jen o zavolání funkce substituce se správnými parametry - písmeny české abecedy s diakritikou a jejich ekvivalenty bez diakritiky³⁾. Podle potřeby lze doplnit znaky s přehláskami nebo přizpůsobit parametry jiným jazykům.

def hacky_carky(text):
    return substituce(text, \
                      "áÁčČďĎéÉěĚíÍňŇóÓřŘšŠťŤúÚůŮýÝžŽ", \
                      "aAcCdDeEeEiInNoOrRsStTuUuUyYzZ")

V souboru nahrada.py naleznete celý kód včetně odstavce českého textu pro vyzkoušení.

Možná už vás napadlo, že bychom pomocí funkce substituce mohli skrýt obsah nějakého textu před nepovolanými zraky tím, že bychom vhodně zaměnili všechna písmena za jiné symboly, které by běžný pozorovatel pokládal za pouhou nesmyslnou změť.

Takový přístup má v dějinách kryptografie své důležité místo, obyčejně o něm hovoříme jako o monoalfabetické substituční šifře, tzn. nahrazujeme písmena (nikoliv např. slabiky, slova) a zachováváme jejich pořadí. Aby takový postup fungoval, musíme nejprve kromě běžné abecedy (skládá se ze všech znaků, které jsou používány ve zprávách pro šifrování) mít ještě substituční abecedu se znaky zašifrovaných zpráv. Obě abecedy musí být stejně dlouhé a v žádné se nesmějí opakovat znaky⁴⁾. Vůbec není vyloučeno (naopak je to častý případ), že obě abecedy se skládají z týchž znaků, ale v různém pořadí!

Při splnění těchto podmínek probíhá šifrování tak, že znaky zprávy převádíme z běžné abecedy do substituční, dešifrování je proces zcela shodný, pouze se vymění role obou abeced. Ten, kdo nezná substituční abecedu, nemůže snadno zašifrovanou zprávu rozluštit.

Pro zprávy zapsané pomocí malých písmen anglické abecedy (má 26 znaků) je počet možných substitučních abeced již tak ohromný (číslo 26! jako počet permutací 26 prvků bychom uměli snadno spočítat), že ani současným superpočítačům by se v představitelném čase nepodařilo vyzkoušet všechny možnosti. V praxi se obyčejně využívaly shodné symboly i v substituční abecedě (samozřejmě v jiném pořadí). Předávat si celou substituční abecedu mezi odesílatelem a příjemcem se v reálném životě ukazovalo nešikovné⁵⁾ a hledalo se řešení, jak ji zkonstruovat na základě nějakého snadno zapamatovatelného klíče⁶⁾. Pokud obě strany znaly stejný tajný klíč, mohli si předem daným postupem vytvořit shodnou substituční abecedu a poté šifrovaně komunikovat.

V jazyce Python bychom tak mohli pro zašifrování zprávy a její rozšifrování mít dvě funkce

# šifrování
# znaky normální abecedy měníme za prvky substituční abecedy
def zasifruj(text, klic):
    return substituce(text, abeceda, subst_abc(klic))
 
# dešifrování
# znaky substutuční abecedy měníme za prvky normální abecedy
def rozsifruj(text, klic):
    return substituce(text, subst_abc(klic), abeceda)

používající běžnou abecedu danou obsahem proměnné abeceda a zatím neurčenou funkci subst_abc, která na základě tajného klíče vytvoří substituční abecedu. Její konkrétní tvar nás pak zavede k jednotlivým variantám této šifry, my si ukážeme dvě z nich.

Mezi římskými legiemi a římským ústředím putovaly šifrované zprávy, jedním z používaných postupů byla i tzv. Caesarova šifra. V dalším budeme předpokládat, že zprávy se skládají z malých písmen anglické abecedy (což samozřejmě neodpovídá dobovým reáliím). Substituční abeceda se vytvoří jednoduchým posunutím o určený počet písmen (pro písmena na konci se pak pokračovalo znovu od začátku abecedy) a skládá se tedy ze stejných symbolů. Klíčem je číslo udávající posunutí. Například

klíč:                3
abeceda:             abcdefghijklmnopqrstuvwxyz
substituční abeceda: defghijklmnopqrstuvwxyzabc

tj. znak a nahradíme d atd. Při dešifrování se role obou abeced prohodí (z d se stane zpátky a), výsledkem bude původní zpráva. Máme pouze 26 různých možných klíčů, přičemž pouze 25 z nich vede ke skutečnému šifrování. Pravděpodobně to však svému účelu přesto dobře posloužilo.

Funkci pro vytvoření substituční abecedy naprogramujeme snadno.

abeceda = "abcdefghijklmnopqrstuvwxyz"
 
# vytvoření substituční abecedy
#  - cyklický posun o pocet pismen určený číselným klíčem
def subst_abc(klic):
    klic %= len(abeceda) # zajištění správného rozsahu
    return abeceda[klic:] + abeceda[:klic]

Za zmínku stojí skutečnost, že používáme globální proměnnou abeceda uvnitř funkcí, ačkoliv jsme takový přístup nedoporučovali. V tomto případě se jedná o proměnnou, která jednou na začátku získá hodnotu a nadále se nemění. Používá se v několika funkcích a má svou jasně danou úlohu. I vzhledem ke srozumitelnosti je použití globální proměnné v tomto případě ospravedlnitelné.

Celý kód včetně příkladů zašifrování a rozšifrování si můžete stáhnout caesar.py. Z dnešního hlediska musíme tuto šifru považovat za velmi slabou a následující zpráva zašifrovaná Ceasarovou šifrou je prakticky zcela veřejná⁷⁾.

xgefuf fmwahq lbdmhk zqzu hgnqo anfulzq mzu nql baoufmoq

Nyní ukážeme metodu, jak vytvořit substituční abecedu na základě textového klíče (skládajícího se z jednoho či více slov). Na jedné straně si takový klíč relativně snadno zapamatujeme (ostatně při použití počítače potřebujeme takových hesel celou řadu), na straně druhé počet možných substitučních abeced s délkou klíče strmě roste, což činí zkoušení všech možností obtížné.

Budeme postupovat tak, že nejprve do substituční abecedy zapíšeme znaky klíče (mezery a opakující se písmena přeskočíme). Výsledek doplníme zbývajícími znaky v abecedním pořadí s tím, že začneme s procházením za dosud posledním znakem klíče a případně pokračujeme znovu od začátku.

jaro leto podzim zima       ; klíč

jaroletpdzim                ; začínáme písmeny klíče (bez opakování)
            nqsuvwxy        ; poté procházíme zbytek abecedy od 'n'
                    bcfghk  ; dokončíme procházením od začátku abecedy
jaroletpdzimnqsuvwxybcfghk  ; kompletní substituční abeceda

Vytvoření substituční abecedy programem znamená provést právě popsané kroky.

def subst_abc(klic):
    vysledek = []
    # unikátní písmena z klíče
    for pismeno in klic:
        if pismeno in abeceda and pismeno not in vysledek:
            vysledek.append(pismeno)
    # pořadí následujícího písmena
    index = abeceda.find(vysledek[-1]) + 1
    # doplnění zbylých písmen v abecedním pořadí (s přetečením)
    delka_abc = len(abeceda)
    for i in range(delka_abc):
        pismeno = abeceda[(index + i) % delka_abc]
        if pismeno not in vysledek:
            vysledek.append(pismeno)
    return "".join(vysledek) # vrátíme řetězec

Připomínáme, že klíč je nyní textový řetězec (pro správnou činnost nesmí být prázdný). Činnost je opět možné si vyzkoušet na kompletním kódu sifra.py.

Z dnešního hlediska ani tato šifra (či jakákoliv jiná varianta monoalfabetické substituční šifry) nepřináší potřebnou míru zabezpečení. Pokud máme k dispozici dostatečný objem zašifrovaného textu, lze poměrně efektivně provést frekvenční analýzu, tj. odhadnout alespoň některá písmena na základě jejich četnosti v běžném jazyce, a následně pokračovat doplňováním častějších slabik, slov atp.

Ukázali jsme si, že nahrazení některých znaků za jiné nalezne použití v různých situacích. Bylo by až skoro s podivem, kdyby jazyk Python pro takovou činnost neměl přímou podporu.

Skutečně jí má - jedná se o řetězcovou metodu str.translate. Metodu jsme nepředstavili hned v úvodu ze dvou důvodů: procvičování operací na řetězcích a seznamech a skutečnost, že parametrem metody translate je objekt datového typu slovník, který neznáme. Pro zjednodušení existuje pro řetězce statická metoda str.maketrans (opět nevíme přesně, o co se jedná), která tuto substituční tabulku připraví.

S pomocí těchto nových metod bychom místo naší funkce substituce

vysledek = substituce(text, co, cim)

mohli použít metodu translate s vhodně vytvořenou substituční tabulku

vysledek = text.translate(str.maketrans(co, cim))

se stejným výsledkem, ale (asi nepříliš překvapivě) efektivněji a rychleji. Možností metody translate jdou ještě dále, což je však už za hranicí našeho výkladu.