Hlavní navigace

Šifra Delastelle - BIFID

Pavel Vondruška

Celá staletí bylo utajování textů založeno buď na jejich skrytí (steganografie) nebo na využití transpozičních a substitučních šifer. Tyto šifry pracovaly s celým znakem (výjimečně bigramem) otevřeného textu. Dnes, v době počítačů, je naopak zcela přirozené, že šifrování probíhá na úrovní bitové reprezentace písmen.

Poznámka pro čtenáře tohoto serveru – pokud se vám následující text bude zdát poněkud jednoduchý a „polopatický“, pak je to v pořádku, má takový být. Jde o rozšíření textu o šifře BIFID z knihy P.Vondruška: Kryptologie, šifrování a tajná písma, edice OKO, Albatros, Praha 2006. V knize je celý tento text zúžen na stručný výklad šifry BIFID, a to ještě pouze na použití vodorovného sdružování ([1], str.111–114). Neúprosná smlouva s nakladatelstvím na pouhých 185 NS (342 stran velikosti OKO) neumožnila v knize otisknout všechny připravené texty a bylo třeba krátit, což postihlo i tento systém. Snad předvánoční nálada, kdy se snažíme alespoň na chvíli se oprostit od aktuálních profesních problémů a najít si chvilku na odreagování, je vhodná k tomu, že se můžeme na chvíli zastavit a přečíst si text určený pro mládež a ne IT profesionály.

Celá staletí bylo utajování textů založeno buď na jejich skrytí (steganografie) nebo na využití transpozičních a substitučních šifer. Tyto šifry pracovaly s celým znakem (výjimečně bigramem) otevřeného textu. Tedy s jednotlivými znaky otevřeného textu, které byly různě přehazovány a nahrazovány podle různě složitých pravidel za znaky jiné. Tento přístup odpovídal tehdejší schopnosti reprezentovat jednotlivé znaky otevřeného a šifrového textu. Dnes, v době počítačů, je naopak zcela přirozené, že šifrování probíhá na úrovní bitové reprezentace písmen a „promíchávají“ se nikoliv celá písmena, ale jejich bitová reprezentace a substituce také již neprobíhá po celých písmenech, ale nahrazují se jednotlivé bity v reprezentaci příslušného znaku. Je samozřejmé, že tato nová kvalita vnesla další prvek složitosti a zvýšila tak odolnost jednotlivých šifer. Z hlediska bezpečnosti samozřejmě není využití jiné reprezentace automaticky zvýšením kryptografické bezpečnosti – obdoba Caesarovy šifry aplikovaná na bitovou reprezentaci písmen např. v podobě šifry rot13 samozřejmě není o nic bezpečnější než původní šifra římského císaře. Jenže bitová reprezentace umožňuje nejen využití počítačů, ale také použití nových druhů transformací a tím rychlejší „odstranění“ zbytkové informace ze šifrového textu. Mohli se touto cestou šifrování vydat kryptologové již dříve, resp. byla tato možnost v minulých staletích skutečně využita?

Když mi bylo dvanáct let, byly vyhlášeny dlouhé uhelné vánoční prázdniny. Abych se nenudil, začali jsme si dopisovat s jedním kamarádem pomocí šifer. Jedinou, kterou jsme znali, byla jednoduchá záměna, kde se převod otevřeného textu na šifrový prováděl pomocí tabulky. Jenže k Vánocům jsme oba dva dostali trojbarevnou propisku. To nám umožnilo použít novou reprezentaci písmen – využití barev. Nejprve tak, že např. C bylo modré A, K bylo zelené A a J červené A. Brzy jsme však zjistili, že se kvalita šifry nijak výrazně nezměnila. Po chvíli „bádání“ jsme se dohodli na „revoluční myšlence“. Každé písmeno jsme symetricky rozdělili na dvě poloviny (horní a dolní). Každou polovinu jsme šifrovali podle jiné převodové tabulky. S překvapením jsme však zjistili, že jsme dosáhli jen toho, že vytvořit výsledný šifrový text a jeho následnou dešifraci je sice těžší, ale šifra nic nového nepřinesla. Všimli jsme si totiž, že lze šifrovat a dešifrovat podle jediné tabulky, kde šifrová abeceda je tvořena „zpotvořenými“ písmenky, která vzniknou námi definovanou záměnou. Napadlo nás proto šifru doplnit o další prvek. Nejprve se písmenka „rozstříhala“ a u dvou sousedních se zaměnil hořejšek a spodek ponechal. Pak jsme použili naše dvě původní převodové tabulky pro „hořejšky“ a pro „spodky“. Nová šifra byla na světě. Zdála se nám naprosto dokonalá (až na tu pracnost), nikdo ji neznal a navíc odolala všem snahám spolužáků, kteří se ji snažili vyluštit.

Vánoční stromek malý

Adventní kalendář

Už jste dnes viděli, jak vypadá další odkryté okénko v našem adventním kalendáři? Každý předvánoční den se na jeho stránce jedna část odkryje. Nenechejte si uniknout pointu a diskutujte o ní v naší diskusi.

Teprve po mnoha letech jsem zjistil, že jsme nebyli první, kdo (ovšem mnohem důmyslněji…) šifru založenou na podobné myšlence vymyslel a popsal. Kupodivu ani on nebyl kryptolog profesionál, ale amatér, který systém objevil až po svém odchodu do důchodu a popsal v knize, kterou napsal rok před svou smrtí. Kniha se jmenuje Le Traité élémentaire de cryptographie a vyšla v nakladatelství Gauthier-Villars v Paříži roku 1902. Tento muž, Francouz, se jmenoval Félix-Marie Delastelle (1840–1902). Hlavním jeho cílem bylo popsat v knize jednotlivé šifrové systémy, roztřídit je a ukázat na vztahy mezi nimi. Za svoji systematičnost byl nečekaně odměněn. Když studoval bigrafické šifrové systémy ([1], str.34) a snažil se vyhnout nepraktickému používání velkých šifrovacích tabulek 26 × 26, objevil zcela nový šifrový systém. Tento systém se po něm nejprve nazýval Delastelle, ale dnes je znám spíše pod jménem BIFID, resp. jeho upravená varianta jako TRIFID ([1], str.114). Systém patří mezi zlomkové šifrové systémy, ale je odlišný od podobných zlomkových systémů Pliny Earla Chasea ([1], str. 107). Spočívá na převodu otevřených znaků na dvouciferná (v případě TRIFID trojciferná) čísla a jejich rozpis do řádků. Následně se číslice v řádcích sdruží a vytvoří podle převodové tabulky šifrový text.

Šifra Delastelle – BIFID

Systém vysvětlíme na příkladu zašifrování otevřeného textu: NOVY TYP SIFRY.

1) Převod otevřeného textu na dvojice čísel

Nejprve se vytvoří tabulka pro převod otevřených znaků na dvojici čísel.

Tabulka

Tento převod musí splňovat podmínku, že pokud se objeví nějaká hodnota řádkové souřadnice, pak musí být tato hodnota použita i jako sloupcová souřadnice a naopak. Lze proto pro realizaci s výhodou použít Polybiův čtverec ([1], str.35, 42, 201), kde řádky a sloupce mají stejné souřadnice a znaky otevřené abecedy (písmena) jsou ve čtverci rozházeny nebo zapsány podle nějakého hesla (zde ALBATROS).

Hodnoty se (po převodu pomocí tabulky) zapisují do dvou řádků. Do prvního řádku budeme zapisovat řádkovou souřadnici určující pozici písmene v tabulce (např. pro N to bude 4) a do druhého řádku sloupcovou souřadnici (pro N to je 3).

Podle tohoto pravidla dostaneme pro námi zvolený otevřený text následující vyjádření:

Otevřený text:            NOVY TYP SIFRY
Přepis podle tabulky:      (N=43, O = 21, V=51 …)
1. řádek          4255 154 23315
2. řádek          3114 444 24154 

2) Rozdělení na skupiny

Kdybychom nyní použili Delastellovu koncepci zašifrování souřadnic (viz část 3), získal by eventuální luštitel řadu informací o otevřeném textu a systém by měl závažné bezpečnostní vady. Např. by luštitel znal délku jednotlivých slov otevřeného textu, v případě samostatně stojícího písmene by nedošlo k jeho přešifrování a stejná slova by se zašifrovala vždy stejně. Z těchto důvodů se proto nyní otevřený text dělí do skupin. Často používaná dělba byla po pěti písmenech ve skupině, ale jsou možné i dělby na jiný počet písmen (např. po osmi znacích). Je také možné u krátkých textů vypustit všechny mezery v otevřeném textu a dále text již nedělit a zacházet s ním při přešifrování jako s celkem.

Příprava textu – dělba na pět znaků:

Otevřený text:            NOVY TYP SIFRY
Po úpravě:            NOVYT YPSIF RY
Přepis podle tabulky:      (N=43, O = 21, V=51 …)
1. řádek          42551 54233 15
2. řádek          31144 44241 54 

3) Delastellova koncepce sdružování

Šifra BIFID je založena na následující Delastellově koncepci sdružování souřadnic a jejich zpětném převodu na šifrový text. Delastelle navrhl domluveným způsobem sdružovat jednotlivé souřadnice textu na dvojice čísel a tyto skupiny převést podle převodové tabulky zpět na písmena, která vytvoří výsledný šifrový text.

Sdružovat souřadnice lze různým způsobem, v případě šifry BIFID jsou nejčastěji používány tři postupy: „vodorovně“, „šikmo nahoru“ a „šikmo dolů“.

3 a) sdružování „vodorovně“

Seskupování se provádí v rámci jednoho číselného vyjádření skupiny, jestliže vyčerpáme v tomto vyjádření v prvním řádku všechny číslice, pokračujeme v sestavování dvojic v řádku druhém a to opět od začátku skupiny.

Delastellovo přešifrování (vodorovné sdružování):

1.řádek       42551 54233 15
2.řádek       31144 44241 54 

Výsledek:

sdružení v prvé skupině: 42, 55, 13, 11, 44 , ve druhé: 54, 23, 34, 42, 41 třetí: 15, 54

Převod pomocí tabulky :

M Z B   Y C I    R
  A P      M K   Y 

3 b) sdružování „šikmo nahoru“

Mimo vodorovného sdružování se používá i sdružování směrem šikmo nahoru. První horní znak v prvé skupině je využit až pro poslední sdružení v této skupině.

Delastellovo přešifrování (sdružování šikmo nahoru):

1.řádek       42551 54233 15
2.řádek       31144 44241 54 

Výsledek:

sdružení v prvé skupině: 32 , 15, 15, 41, 44 , ve druhé: 44, 42, 23, 43, 15, třetí: 55, 41

Výsledný šifrový text : MZBAP YCIMK RY

Převod pomocí tabulky : GRRKP PMCNR ZK

Výsledný šifrový text : GRRKP PMCNR ZK

3 c) sdružování „šikmo dolů“:

Dalším možným typem sdružování je sdružování směrem šikmo dolů. První dolní znak v prvé skupině je použit až pro poslední sdružení v této skupině.

Delastellovo přešifrování (sdružování šikmo dolů):

1.řádek       42551 54233 15
2.řádek       31144 44241 54 

Výsledek:

sdružení v prvé skupině: 41, 21, 54, 54, 13 , ve druhé: 54, 42, 24, 31, 34, ve třetí: 14, 55

Zpětný převod pomocí tabulky : KOYYB YMDFI TZ

Výsledný šifrový text : KOYYB YMDFI TZ

Poznámka (rozdílné převodové tabulky):

Zpětná převodová tabulka v části 3 může být pro větší bezpečnost odlišná od prvé převodové tabulky v části 1!

4) Dešifrování

Příjemce musí znát použitou převodovou tabulku v části 1 a v části 3 (pokud byla odlišná). Dále musí být s odesílatelem domluven na délce použité dělby otevřeného textu (např. podle slov – nedoporučuje se, délka 5, délka 8, celý text) a způsobu sdružování souřadnic (vodorovně, šikmo dolů, šikmo nahoru). Příjemce (dešifrant) přijaté znaky šifrového textu nahradí číslicemi podle druhé převodové tabulky, provede správné uspořádání číslic do dvou řádků a převede s využitím známého sdružování souřadnic dvoumístné skupiny čísel zpět pomocí prvé tabulky na otevřené znaky.

[1] P.Vondruška: Kryptologie, šifrování a tajná písma, edice OKO, Albatros, Praha 2006

Našli jste v článku chybu?

14. 4. 2009 12:56

bubo (neregistrovaný)
NO a sranda, ze my sme dostali na skole spravit program, ktory desifruje text hrubou silou .. a ten program musi zistit, ci ten text ma zmysel alebo nie .. nepozname kluc, nepozname nic iba dlzu textu ;-) tak si to niekto skuste spravit

13. 12. 2006 7:37

Pavel Vondruška (neregistrovaný)
Tu složitost si jeste "malinko" muzete zvetsit. Nevite totiz typ sdruzovani, ale co hure, nevite take delbu na skupiny (to je docela zajimavy dalsi parametr) ....
Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

DigiZone.cz: Velká cena v Abú Dhabí: 131 ti­síc diváků

Velká cena v Abú Dhabí: 131 ti­síc diváků

Měšec.cz: Kdy vám stát dá na stěhování 50 000 Kč?

Kdy vám stát dá na stěhování 50 000 Kč?

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

120na80.cz: 5 nejčastějších mýtů o kondomech

5 nejčastějších mýtů o kondomech

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Podnikatel.cz: Chaos u EET pokračuje. Jsou tu další návrhy

Chaos u EET pokračuje. Jsou tu další návrhy

120na80.cz: Co všechno ovlivňuje ženskou plodnost?

Co všechno ovlivňuje ženskou plodnost?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Měšec.cz: Jak vymáhat výživné zadarmo?

Jak vymáhat výživné zadarmo?

Podnikatel.cz: K EET. Štamgast už peníze na stole nenechá

K EET. Štamgast už peníze na stole nenechá

DigiZone.cz: Flix TV: dva set-top boxy za korunu

Flix TV: dva set-top boxy za korunu

120na80.cz: Pánové, pečujte o svoje přirození a prostatu

Pánové, pečujte o svoje přirození a prostatu

120na80.cz: Horní cesty dýchací. Zkuste fytofarmaka

Horní cesty dýchací. Zkuste fytofarmaka

DigiZone.cz: ČRo rozšiřuje DAB do Berouna

ČRo rozšiřuje DAB do Berouna

Vitalia.cz: Potvrzeno: Pobyt v lese je skvělý na imunitu

Potvrzeno: Pobyt v lese je skvělý na imunitu

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

DigiZone.cz: Recenze Westworld: zavraždit a...

Recenze Westworld: zavraždit a...

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum