Matematické základy šifrování a kódování Permutace Pojem permutace patří mezi základní pojmy a nachází uplatnění v mnoha oblastech, např. kombinatorice, algebře apod. Definice Nechť je n-prvková množina. Permutací na množině A rozumíme libovolné uspořádání prvků množiny A, tj. libovolnou uspořádanou n-tici tvořenou právě všemi prvky množiny A. Běžně je k zápisu permutací využíván následující „dvouřádkový“ zápis , který interpretujeme následovně – první řádek určuje pozice v uspořádané n-tici a druhý řádek určuje prvky (z množiny A), které se na dané pozici vyskytují (tj. na 1. pozici je prvek , atd. až na n-té pozici je prvek ). S ohledem na tuto skutečnost je zřejmé, že např. zápisy a definují stejnou permutaci. Poznámky ∙
Permutace budeme obvykle značit malými řeckými písmeny z druhé poloviny řecké abecedy, např. apod.
∙
Alternativně lze permutaci definovat jako vzájemně jednoznačné zobrazení množiny A na sebe.
∙
Množinu všech permutací na n-prvkové množině budeme značit operaci násobení následovně:
(platí
) a definujeme na ní
(Pokud permutace chápeme jako vzájemně jednoznačné zobrazení množina A na sebe, potom součin odpovídá operaci skládání zobrazení.) ∙
Množina
spolu s výše definovanou operací násobení tvoří tzv. symetrickou grupu, zapisujeme
Permutace permutace
Zřejmě platí (ověřte): -
.
tvoří tzv. jednotkový prvek (označujeme idn, resp. 1) symetrické grupy a tvoří inverzní permutaci k
.
Příklad Nechť
, kde
.
Zřejmě platí:
;
Úvod do šifrování (kryptografie) Kryptografie je vědecká disciplína, která se zabývá metodami ochrany dat před neautorizovaným přístupem, resp. nakládáním s daty. Je přirozené, že snaha o ochranu dat před neautorizovaným přístupem vede k „protireakci“, tj. vyvolává snahu o prolomení kryptografické ochrany. Kryptoanalýza Vědecká disciplína, která se zabývá metodami prolomení kryptografické ochrany. Kryptoanalytické metody jsou v případě klasických substitučních šifrovacích metod založeny na tzv. frekvenční analýze, která odhaduje identitu znaků (resp. jejich kombinací) na základě porovnání frekvence jejich výskytu v daném jazyce a zašifrovaném textu. Kryptologie Disciplína, která zahrnuje jak kryptografii, tak i kryptoanalýzu. Vývoj obou disciplín je vzájemně provázán. Steganografie Ochránit data před neautorizovaným přístupem lze v zásadě dvěma způsoby – učinit data „nesrozumitelnými“ (→ kryptografická ochrana) nebo „utajit“ jejich samotnou existenci (→ steganograficke metody: technické a lingvistická).
Steganografie
Kryptologie
Kryptoanalýza
Kryptografie
Základní pojmy Otevřená abeceda Konečná množina znaků A, které používáme k zápisu nezašifrovaných zpráv. Jde např. o českou abecedu doplněnou o cifry a další speciální symboly. V těchto skriptech se pro jednoduchost omezíme na abecedu uvedenou v horním řádku následující tabulky (v celé řadě metod budeme znaky otevřené abecedy nahrazovat jejich pořadím, číslujeme od 0 - viz druhý řádek). a 0
b 1
c 2
d 3
e 4
f 5
g 6
h 7
i 8
j k l m n o p q r s t u v w x y z 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
Otevřený text Otevřeným textem rozumíme konečný řetězec znaků otevřené abecedy (n je délka). Otevřený text budeme psát obvykle malými písmeny a interpretujeme ho jako zprávu určenou k zašifrování. Prostor otevřených textů Množinu všech potenciálních otevřených textů budeme nazývat prostorem otevřených textů a značit . Šifrová abeceda Konečná množina znaků B, které používáme v zašifrovaných zprávách. V případě binárním šifrování. Zašifrovaný text (šifrový text) Konečný řetězec textu .
, mluvíme o
znaků šifrové abecedy, který vzniknul zašifrováním některého otevřeného
Prostor šifrových textů Množinu všech šifrových textů vzniklých zašifrováním otevřených textů z prostoru otevřených textů budeme nazývat prostorem otevřených textů a značit . Klíč, prostor klíčů Klíčem rozumíme uspořádanou dvojici , kde e nazýváme šifrovacím klíčem (parametr šifrovací metody), d dešifrovacím klíčem (parametr dešifrovací metody). Množina všech klíčů tvoří tzv. prostor klíčů, značíme . Jedním ze základních požadavků je, aby prostor klíčů byl dostatečně obsáhlý a prakticky znemožňoval „uhádnout“ klíč metodou hrubé síly, tj. prohledáním prostoru klíčů. Šifrování Proces transformace otevřeného textu do zašifrovaného textu. Zjednodušeně řečeno, lze šifrování chápat jako přesně definovaný proces převedení otevřeného textu do „nesrozumitelné“ podoby zašifrovaného textu. Šifrovací funkce/transformace Šifrovací funkcí rozumíme vzájemně jednoznačné zobrazení definované pro všechny (šifrovací) klíče z prostoru klíčů . Vzájemná jednoznačnost je základním předpokladem pro možnost zpětného dešifrování. Šifrovací systém Uspořádaná trojice je prostor klíčů,
, kde
je množina šifrovacích funkcí, je množina dešifrovacích funkcí, tvoří šifrovací systém, jestliže Interpretace - každý klíč příslušnou dešifrovací).
definuje jedinou dvojici transformací
a
(šifrovací transformaci a jí
Symetrické (klasické) šifrovací metody Šifrovací metody, kde dešifrovací klíč je výpočetně jednoduché odvodit ze šifrovacího klíče. Asymetrické šifrovací metody (s veřejným klíčem) Šifrovací metody, kde dešifrovací klíč nelze výpočetně jednoduše odvodit ze šifrovacího klíče. Transpoziční metody Šifrovací metody, ve kterých znaky otevřeného textu mění svou pozici, ale nemění svou identitu. Substituční metody Šifrovací metody, ve kterých znaky otevřeného textu mění svou identitu, ale nemění svou pozici. Monoalfabetické šifry Šifrovací metody (obvykle substituční), využívající pouze jednu šifrovou abecedu. Homofonní šifry Šifrovací metody, kde znaky šifrového textu mají teoreticky stejnou frekvenci výskytu. Polyalfabetické šifry Šifrovací metody (obvykle substituční) využívající více šifrovacích abeced, které systematicky (tj. dle definovaných pravidel) střídají.
Jednoduchá transpozice Šifrovací klíč: Šifrovací transformace: kde
,
kde ,
,
. (V tomto případě použijeme jako úplnou soustavu zbytků modulo n množinu Dešifrovací klíč: Dešifrovací transformace: kde
, kde
)
označuje inverzní permutaci k ,
,
. (V tomto případě použijeme také jako úplnou soustavu zbytků modulo n množinu
)
Poznámky ∙ Postup šifrování lze popsat následovně - nejprve text rozdělíme na po sobě jdoucí podřetězce délky d. Každý podřetězec pak zašifrujeme pomocí permutace na řetězec (tj. na pozici i umístíme znak z pozice ). Analogicky postupujeme i při dešifrování (pouze místo použijeme ). ∙ Pokud délka n textu není násobkem čísla d, doplníme ho libovolnými znaky na délku rovnou prvnímu násobku čísla d většímu než n. Příklad Uvažujte jednoduchou transpozici s klíčem a) Zašifrujte text „koloseum“.
.
otevřený text: zašifrovaný text:
k L
o K
l S
o O
s O
e M
u E
m Y
x U
y X
E n
M t
N u
U m
b) Dešifrujte text „DRMUITEMNU“(při šifrování byl použit klíč ). Dešifrovací klíč zašifrovaný text: otevřený text:
Afinní šifra Šifrovací klíč: Šifrovací funkce: kde
D r
,
R u
M d
U i
I m
T e
kde ,
, je číselná reprezentace i-tého znaku otevřeného textu.
Poznámka Nejprve převedeme textový řetězec na číselný řetězec např. tak, že každý znak nahradíme jeho pořadím v rámci uvažované abecedy (pozor - číslujeme od 0 nebo od 1) - viz tabulka č. 1. Dešifrovací klíč: Dešifrovací funkce:
,
kde
je inverzní prvek k ,
kde
.
Příklad Uvažujte afinní šifru s šifrovacím klíčem a) Zašifrujte text „vista“. Průběh šifrování lze zapsat následovně:
, kde
.
b) Dešifrujte text „BOWLC“. Průběh dešifrování lze zapsat následovně:
Jednoduchá substituce Šifrovací klíč: Šifrovací funkce: Dešifrovací klíč: Šifrovací funkce:
, kde
označuje inverzní permutaci k
Poznámka Alternativní způsob zadání šifrovacího klíče využívá šifrování označované jako substituce s klíčovým slovem. V tomto případě tvoří šifrovací klíč uspořádaná dvojice , kde . Číslo k definuje pozici, odkud začneme postupně umisťovat znaky textového řetězce, opakující se znaky vynecháváme. V další fázi doplníme chybějící znaky otevřené abecedy.
Příklad Otevřený text „aqua fontis“ zašifrujte pomocí jednoduché substituce. Jako šifrovací klíč použijte: a) Schematický zápis šifrování může vypadat následovně otevřený text: zašifrovaný text:
a D
q U
u C
a D
f T
o A
n R
t M
i B
s O
b) Nejprve na základě klíče vygenerujeme příslušnou permutaci definující substituční abecedu - od 7. znaku (tj. od písmene g) doplňujeme text „regnumBohemiae“ (opakující se znaky vynecháváme). V dlaší fázi doplníme chybějící znaky otevřené abecedy.
otevřený text: zašifrovaný text:
a T
q A
u J
a T
f Z
o H
n O
t F
i G
s D
Hillova šifra Šifrovací klíč: Šifrovací funkce: kde
Dešifrovací klíč: Dešifrovací funkce:
,
kde
je číselný vektor reprezentující šifrovaný podřetězec otevřeného textu, je číselný vektor reprezentující odpovídající šifrový text. , matice inverzní k H modulo 26
Poznámky ∙ Postup šifrování lze popsat následovně - nejprve otevřený text rozdělíme na po sobě jdoucí podřetězce délky d. Každý podřetězec pak převedeme na číselný vektor , který zašifrujeme pomocí šifrovací funkce na řetězec . ∙ Pokud délka n otevřeného textu není násobkem čísla d, doplníme ho libovolnými znaky na délku rovnou prvnímu násobku čísla d většímu než n. ∙ Existence inverzní matice je nezbytnou podmínkou pro jednoznačné dešifrování. Lze ukázat, že nutnou a postačující podmínkou je , kde označuje determinant matice H. Platí . ∙ Výpočet se provádí v soustavě Z26 a lze využít „standardní“ postupy, např. Gaussovu metodu, determinanty atd. Příklad Uvažujte Hillovu šifru s klíčem a) Zašifrujte text „tarsus“. Průběh šifrování lze zapsat následovně:
.
b) Dešifrujte text „QASNAL“. Průběh dešifrování lze zapsat následovně:
Vigenerova šifra Šifrovací klíč: Šifrovací funkce: kde
, (využíváme úplnou soustavu zbytků
Dešifrovací klíč: Dešifrovací funkce:
,
kde
)
označuje inverzní permutaci k
Poznámky ∙ Vigenerova šifra je polyalfabetická šifra, jejíž klíč tvoří d cyklicky se střídajících substitučních abeced. Tedy pro zašifrování: znaku použijeme abecedu , znaku použijeme abecedu ,
∙
znaku použijeme abecedu , Speciálním případem je šifrování pomocí tzv. Vigenerova čtverce, jehož první řádek tvoří otevřená abeceda a následující řádky reprezentují substituční abecedy vzniklé pouhým posunutím (viz tab. č. 2). Šifrovací klíč tvoří textový řetězec, který určuje řádky (první znak řádku), používané k zašifrování daného znaku otevřeného textu. a B C D E F G H I J K L M N
b C D E F G H I J K L M N O
c D E F G H I J K L M N O P
d E F G H I J K L M N O P Q
e F G H I J K L M N O P Q R
f G H I J K L M N O P Q R S
g H I J K L M N O P Q R S T
h I J K L M N O P Q R S T U
i J K L M N O P Q R S T U V
j K L M N O P Q R S T U V W
k L M N O P Q R S T U V W X
l M N O P Q R S T U V W X Y
m N O P Q R S T U V W X Y Z
n O P Q R S T U V W X Y Z A
o P Q R S T U V W X Y Z A B
p Q R S T U V W X Y Z A B C
q R S T U V W X Y Z A B C D
r S T U V W X Y Z A B C D E
s T U V W X Y Z A B C D E F
t U V W X Y Z A B C D E F G
u V W X Y Z A B C D E F G H
v W X Y Z A B C D E F G H I
w X Y Z A B C D E F G H I J
x Y Z A B C D E F G H I J K
y Z A B C D E F G H I J K L
z A B C D E F G H I J K L M
O P Q R S T U V W X Y Z A
P Q R S T U V W X Y Z A B
Q R S T U V W X Y Z A B C
R S T U V W X Y Z A B C D
S T U V W X Y Z A B C D E
T U V W X Y Z A B C D E F
U V W X Y Z A B C D E F G
V W X Y Z A B C D E F G H
W X Y Z A B C D E F G H I
X Y Z A B C D E F G H I J
Y Z A B C D E F G H I J K
Z A B C D E F G H I J K L
A B C D E F G H I J K L M
B C D E F G H I J K L M N
C D E F G H I J K L M N O
D E F G H I J K L M N O P
E F G H I J K L M N O P Q
F G H I J K L M N O P Q R
G H I J K L M N O P Q R S
H I J K L M N O P Q R S T
I J K L M N O P Q R S T U
J K L M N O P Q R S T U V
K L M N O P Q R S T U V W
L M N O P Q R S T U V W X
M N O P Q R S T U V W X Y
N O P Q R S T U V W X Y Z
Tabulka č. 2 - Vigenerův čtverec Příklad Uvažujte Vigenerovu šifru s klíčovým slovem „sera“. a) Zašifrujte text „circumicio“ s e r a s e r a s e klíč: c i r c u m i c i o otevřený text: M I C M Q Z C A S zašifrovaný text: U b) Dešifrujte text „SKXRWWJIG“ s e r a s e r a s klíč: S K X R W W J I G zašifrovaný text: a g g r e s s i o otevřený text:
Binární šifrování Ze zřejmých důvodů převládají v současné době šifrovací metody, které používají binární abecedu, tj. a tedy šifrují bitový (binární) řetězec reprezentující otevřený text opět na bitový (binární) řetězec tvořící šifrový text. Poznámky ∙ Standardní bitové (logické) operace:
∙
Bitové operace rozšíříme přirozeně na operace mezi bitovými řetězci stejné délky - provádíme bitové operace mezi sobě odpovídajícími bity obou bitových řetězců. Např. . ∙ Pro převod otevřeného textu na binární řetězec budeme využívat níže uvedenou ASCII tabulku. Znak 0 1 2 3 4 5 6 7 8 9 ASCII 00110000 00110001 00110010 00110011 00110100 00110101 00110110 00110111 00111000 00111001 Znak a b c d e f g h i j ASCII 01100001 01100010 01100011 01100100 01100101 01100110 01100111 01101000 01101001 01101010 Znak k l m n o p q r s t ASCII 01101011 01101100 01101101 01101110 01101111 01110000 01110001 01110010 01110011 01110100 Znak u v w x y z ASCII 01110101 01110110 01110111 01111000 01111001 01111010
Vernamova šifra Šifrovací klíč: Šifrovací funkce: kde
, kde je binární reprezentace otevřeného textu (resp. jeho části), je binární reprezentace zašifrovaného textu (resp. jeho části), je symbol pro operaci „vylučovací nebo“ (exclusive or, resp. xor).
Dešifrovací klíč: Dešifrovací funkce:
, kde
(tj. společný pro šifrování i dešifrování)
Poznámky ∙ Dešifrování probíhá korektně, neboť: ∙
∙
Postup šifrování lze popsat následovně - nejprve otevřený text převedeme na bitový řetězec, který následně rozdělíme na po sobě jdoucí bitové řetězce délky klíče (tj. d). Tyto řetězce pak zašifrujeme pomocí výše uvedené šifrovací funkce. Šifrovací klíč lze zadat pomocí klíčového slova, jehož binární reprezentace pak tvoří skutečný klíč k.
Příklad Uvažujte Vernamovu šifru s klíčovým slovem „ico“. a) Zašifrujte text „secus“ Bitová reprezentace klíče: e c otevřený text: s u s binární reprezentace: 01110011 01100101 01100011 01110101 01110011 klíč: 01101001 01100011 01101111 01101001 01100011 zašifrovaný text: 00011010 00000110 00001100 00011100 00010000 b) Dešifrujte text (00001111000011000001110100011010) zašifrovaný text: 00001111 00001100 00011101 00011010 klíč: 01101001 01100011 01101111 01101001 binární reprezentace: 01100110 01101111 01110010 01110011 o r otevřený text: f s
Feistelova šifra Šifrovací klíč: , kde Šifrovací proces probíhá následovně, v
na sebe navazujících krocích:
1. krok:
,
2. krok:
,
d. krok:
kde kde
,
kde
(d+1). krok: kde
je bitový řetězec délky
reprezentující otevřený text (resp. jeho část),
reprezentuje prvních n bitů, reprezentuje následujících n bitů (svislá čárka mezi a má pouze pomocný charakter), je bitový řetězec délky reprezentující zašifrovaný text příslušný . Dešifrovací klíč: , kde Dešifrovací proces probíhá následovně, v
odpovídá šifrovacímu klíči na sebe navazujících krocích:
1. krok: 2. krok:
d. krok:
, ,
kde kde
,
kde
(d+1). krok:
Poznámky ∙ Proces dešifrování probíhá stejně jako šifrování, pouze klíče používáme v obráceném pořadí, tj. v 1. kroku , 2. kroku , …, d. kroku . Na závěr zaměníme prvních a druhou polovinu bitů. ∙ DES, NDS, AES
Úvod do kódování Cílem následujících části skript je seznámit čtenáře se základy kódování. V úvodní části budou formulovány základní pojmy a poznatky z oblasti tzv. kódování bez šumu a následující část bude věnována úvodu do problematiky bezpečnostních (detekčních, opravných) kódů, zejména pak lineárních kódů. Úvod do kódování bez šumu Základní pojmy: Zdrojová abeceda Konečná množina , jejíž prvky budeme nazývat zdrojové znaky. Zdrojovou abecedu interpretujeme jako množinu znaků, které používáme k zápisu původní, tj. nezakódované zprávy (např. anglická/česká abeceda spolu s ciframi 0, 1,…, 9 a dalšími speciálními symboly). Kódová abeceda Konečná množina , jejíž prvky budeme nazývat kódové znaky. Kódovou abecedu interpretujeme jako množinu znaků, které používáme ke kódování (tj. k „zápisu“ zakódované zprávy). V případě, kdy , tj. kódová abeceda obsahuje dva znaky (nejčastěji 0, 1), mluvíme o binárním kódu/kódování. V případě mluvíme o ternárním kódování atd. Kódování Kódováním K rozumíme libovolné prosté zobrazení zdrojové abecedy A do množiny
všech
konečných slov nad abecedou B, tj. . Kódování lze interpretovat jako „předpis“, který každému zdrojovému znaku přiřadí slovo vytvořené ze znaků kódové abecedy. Slovo nazýváme kódové slovo příslušné zdrojovému znaku a. Vlastnost „K je prosté“ zajišťuje přirozený požadavek kladený na každé smysluplné kódování, totiž – různým znakům zdrojové abecedy odpovídají různá kódová slova. Kód Kódem rozumíme množinu všech kódových slov, tj. množinu . V další části nebudeme striktně rozlišovat mezi pojmy kódování (zobrazení) a kód (množina kódových slov) a budeme v obou případech používat označení K. Kódování zdrojových zpráv Je-li kódování, potom zobrazení abecedou A vztahem
definované pro libovolné slovo nad
nazveme kódováním zdrojových zpráv příslušným kódování K. Je zřejmé, že Jednoznačně dekódovatelné kódování Řekneme, že K je jednoznačně dekódovatelné kódování, jestliže kódování zdrojových zpráv K* je prosté zobrazení. Prefixový kód Prefixovým kódem (kódováním) rozumíme takový kód, kde žádné kódové slovo není prefixem jiného kódového slova.
Blokový kód Kód, jehož všechna kódová slova mají stejnou délku, nazýváme blokovým kódem délky. Počet znaků kódového slova pak nazýváme délkou blokového kódu. Platí: Každý prefixový kód je jednoznačně dekódovatelný a lze je „dekódovat znak po znaku“. Každý blokový kód je zřejmě prefixový a tedy i jednoznačně dekódovatelný.
