Moderní šifrování. Kurzy kryptografie. Moderní blokové šifry. Režim snadné výměny

Ve starověkém světě vznikla potřeba šifrovat korespondenci a objevily se jednoduché náhradní šifry. Šifrované zprávy určovaly osud mnoha bitev a ovlivnily běh dějin. Postupem času lidé vynalézali stále pokročilejší metody šifrování.

Kód a šifra jsou mimochodem různé pojmy. První znamená nahrazení každého slova ve zprávě kódové slovo. Druhým je šifrování každého symbolu informace pomocí specifického algoritmu.

Poté, co matematika začala kódovat informace a byla vyvinuta teorie kryptografie, vědci mnohé objevili užitečné vlastnosti tato aplikovaná věda. Vyřešit pomohly například dekódovací algoritmy mrtvé jazyky, jako je starověká egyptština nebo latina.

Steganografie

Steganografie je starší než kódování a šifrování. Toto umění se objevilo již dávno. Doslova to znamená " skrytý dopis"nebo "tajné psaní". Přestože steganografie přesně neodpovídá definici kódu nebo šifry, má skrýt informace před zvědavýma očima.

Steganografie je nejjednodušší šifra. Typickým příkladem jsou spolknuté poznámky pokryté voskem nebo vzkaz na oholené hlavě, která se skrývá pod porostem vlasů. Nejjasnějším příkladem steganografie je metoda popsaná v mnoha anglických (nejen) detektivních knihách, kdy se zprávy přenášejí prostřednictvím novin, kde jsou písmena diskrétně označena.

Hlavní nevýhodou steganografie je, že si jí může všimnout pozorný outsider. Proto, aby se zabránilo snadnému čtení tajné zprávy, používají se ve spojení se steganografií metody šifrování a kódování.

ROT1 a Caesarova šifra

Název této šifry je ROTate 1 letter forward a zná ji mnoho školáků. Je to jednoduchá substituční šifra. Jeho podstatou je, že každé písmeno je zašifrováno posunutím abecedy o 1 písmeno dopředu. A -> B, B -> B, ..., I -> A. Zašifrujme například frázi „naše Nasťa hlasitě pláče“ a dostaneme „obshb Obtua dspnlp rmbsheu“.

Šifru ROT1 lze zobecnit na libovolný počet offsetů, pak se nazývá ROTN, kde N je číslo, o které má být šifrování písmen posunuto. V této podobě je šifra známá od starověku a nazývá se „Caesarova šifra“.

Caesarova šifra je velmi jednoduchá a rychlá, ale jedná se o jednoduchou šifru s jednou permutací, a proto je snadné ji prolomit. S podobnou nevýhodou je vhodný pouze pro dětské žerty.

Transpoziční nebo permutační šifry

Tyto typy jednoduchých permutačních šifer jsou vážnější a aktivně se používaly ještě nedávno. Během americké občanské války a první světové války byl používán k přenosu zpráv. Jeho algoritmus spočívá v přeskupování písmen - napište zprávu v opačném pořadí nebo přeskupte písmena ve dvojicích. Zašifrujme například frázi „Morseova abeceda je také šifra“ -> „Akubza ezrom - ezhot rfish“.

Díky dobrému algoritmu, který určoval libovolné permutace pro každý znak nebo jejich skupinu, se šifra stala odolnou vůči jednoduché hackování. Ale! Pouze včas. Protože je šifra snadno prolomitelná jednoduché vyhledávání nebo slovníková shoda, dnes už její dekódování zvládne každý smartphone. S příchodem počítačů se proto tato šifra stala i dětským kódem.

Morseova abeceda

Abeceda je prostředkem výměny informací a jejím hlavním úkolem je zjednodušit a srozumitelnější zprávy pro přenos. I když je to v rozporu s tím, k čemu je šifrování určeno. Přesto funguje jako ty nejjednodušší šifry. V systému Morse má každé písmeno, číslo a interpunkční znaménko svůj vlastní kód, složený ze skupiny pomlček a teček. Při přenosu zprávy pomocí telegrafu označují pomlčky a tečky dlouhé a krátké signály.

Jako první si v roce 1840 „svůj“ vynález patentoval telegraf a abeceda, ačkoli podobná zařízení byla vynalezena před ním jak v Rusku, tak v Anglii. Ale koho to teď zajímá... Telegraf a Morseova abeceda mají velmi velký vliv světu, což umožňuje téměř okamžitý přenos zpráv na kontinentální vzdálenosti.

Monoalfabetická substituce

ROTN a Morseova abeceda popsané výše jsou zástupci monoalfabetických náhradních písem. Předpona „mono“ znamená, že během šifrování je každé písmeno původní zprávy nahrazeno jiným písmenem nebo kódem z jediné šifrovací abecedy.

Dešifrování jednoduchých substitučních šifer není obtížné a toto je jejich hlavní nevýhoda. Lze je vyřešit jednoduchým hledáním nebo Například je známo, že nejpoužívanějšími písmeny v ruštině jsou „o“, „a“, „i“. Můžeme tedy předpokládat, že písmena, která se v šifrovém textu vyskytují nejčastěji, znamenají buď „o“, „a“ nebo „i“. Na základě těchto úvah lze zprávu dešifrovat i bez vyhledávání na počítači.

Marie I., královna Skotů v letech 1561 až 1567, je známá tím, že používala velmi složitou monoalfabetickou substituční šifru s více kombinacemi. Přesto její nepřátelé dokázali zprávy rozluštit a informace stačily k odsouzení královny k smrti.

Gronsfeldova šifra nebo polyalfabetická substituce

Jednoduché šifry jsou kryptografií považovány za zbytečné. Proto bylo mnoho z nich upraveno. Gronsfeldova šifra je modifikací Caesarovy šifry. Tato metoda je mnohem odolnější vůči hackingu a spočívá v tom, že každý znak zakódované informace je zašifrován pomocí jednoho z různé abecedy, které se cyklicky opakují. Dá se říci, že se jedná o vícerozměrnou aplikaci nejjednodušší substituční šifry. Ve skutečnosti je Gronsfeldova šifra velmi podobná té, o které se pojednává níže.

ADFGX šifrovací algoritmus

Toto je nejznámější šifra z první světové války, kterou používali Němci. Šifra dostala své jméno, protože redukovala všechny šifry na střídání těchto písmen. Výběr samotných písmen byl určen jejich pohodlností při přenosu po telegrafních linkách. Každé písmeno v šifře je reprezentováno dvěma. Zvažme více zajímavá verzečtverec ADFGX, který obsahuje čísla a nazývá se ADFGVX.

Algoritmus pro sestavení čtverce ADFGX je následující:

1. Vezmeme náhodných n písmen k označení sloupců a řádků.
2. Sestavíme matici N x N.
3. Do matice zadáme abecedu, čísla, znaménka, náhodně rozeseté po buňkách.

Udělejme podobný čtverec pro ruský jazyk. Vytvořme například čtverec ABCD:

Tato matice vypadá zvláštně, protože řada buněk obsahuje dvě písmena. To je přijatelné; význam zprávy není ztracen. Dá se snadno obnovit. Zašifrujme frázi „Kompaktní šifra“ pomocí této tabulky:

Konečná zašifrovaná zpráva tedy vypadá takto: „bvgvgbgdagbvdbabdgvdvaadbbga“. Němci samozřejmě provedli podobnou linii prostřednictvím několika dalších šifer. Výsledkem byla šifrovaná zpráva velmi odolná proti hackerům.

Vigenèrova šifra

Tato šifra je řádově odolnější proti prolomení než monoalfabetické, ačkoliv jde o jednoduchou šifru nahrazující text. Nicméně díky robustnímu algoritmu na dlouhou dobu bylo považováno za nemožné hacknout. Jeho první zmínky pocházejí z 16. století. Vigenère (francouzský diplomat) je mylně považován za jeho vynálezce. Abychom lépe pochopili co mluvíme o tom, zvažte Vigenèrovu tabulku (Vigenèrův čtverec, tabula recta) pro ruský jazyk.

Začněme šifrovat frázi „Kasperovich se směje“. Ale aby bylo šifrování úspěšné, potřebujete klíčové slovo – ať je to „heslo“. Nyní začněme šifrovat. Za tímto účelem zapíšeme klíč tolikrát, aby počet písmen z něj odpovídal počtu písmen v zašifrované frázi, a to opakováním klíče nebo jeho odříznutím:

Nyní pomocí souřadnicové roviny hledáme buňku, která je průsečíkem dvojic písmen, a dostaneme: K + P = b, A + A = B, C + P = B atd.

Dostáváme, že „Kasperovič se směje“ = „abvyusnyugshch eykhzhgal“.

Prolomit Vigenèrovu šifru je tak obtížné, protože frekvenční analýza vyžaduje znát délku klíčové slovo. Proto hackování zahrnuje náhodné vhození délky klíčového slova a pokus o prolomení tajné zprávy.

Je třeba také zmínit, že kromě absolutně náhodný klíč lze použít zcela jiný stůl Vigenère. V v tomto případě Vigenère čtverec se skládá z ruské abecedy psané řádek po řádku s posunem o jedna. Což nás přivádí k šifře ROT1. A stejně jako v Caesarově šifře může být offset cokoliv. Pořadí písmen navíc nemusí být abecední. V tomto případě může být klíčem samotná tabulka, aniž bychom věděli, který z nich nebude možné zprávu přečíst, a to ani při znalosti klíče.

Kódy

Skutečné kódy se skládají ze shod pro každé slovo samostatný kód. Pro práci s nimi potřebujete tzv. kódové knihy. Ve skutečnosti se jedná o stejný slovník, který obsahuje pouze překlady slov do kódů. Typickým a zjednodušeným příkladem kódů je ASCII tabulka- mezinárodní šifra jednoduchých znaků.

Hlavní výhodou kódů je, že se velmi obtížně dešifrují. Při jejich hackování téměř nefunguje frekvenční analýza. Slabinou kódů jsou ve skutečnosti samotné knihy. Za prvé, jejich příprava je složitý a nákladný proces. Za druhé, pro nepřátele se promění v žádaný objekt a zachycení i části knihy je donutí úplně změnit všechny kódy.

Ve 20. století mnoho států používalo kódy k přenosu tajných dat, čímž se kódová kniha v průběhu času měnila. určitá doba. A aktivně sháněli knihy svých sousedů i odpůrců.

"Hádanka"

Každý ví, že Enigma je hlavní šifrovací stroj Nacisté během druhé světové války. Struktura Enigmy zahrnuje kombinaci elektrických a mechanických obvodů. Jak šifra dopadne, závisí na počáteční konfiguraci Enigmy. Enigma přitom během provozu automaticky mění svou konfiguraci a jednu zprávu zašifruje několika způsoby po celé její délce.

Na rozdíl od většiny jednoduché šifry Enigma dala biliony možné kombinace, díky čemuž bylo prolomení zašifrovaných informací téměř nemožné. Nacisté se zase připravili na každý den určitá kombinace, které v konkrétní den použili k přenosu zpráv. Proto, i když se Enigma dostala do rukou nepřítele, nijak nepřispěla k dešifrování zpráv bez zavedení požadovaná konfigurace každý den.

Aktivně se snažili rozbít Enigmu po celou dobu Hitlerovy vojenské kampaně. V Anglii v roce 1936 bylo za tímto účelem postaveno jedno z prvních výpočetních zařízení (Turingův stroj), které se stalo prototypem počítačů budoucnosti. Jeho úkolem bylo simulovat provoz několika desítek Enigm současně a nechat jimi procházet zachycené nacistické zprávy. Ale i Turingův stroj byl jen občas schopen rozlousknout zprávu.

Šifrování veřejným klíčem

Nejoblíbenější šifrovací algoritmus, který se používá všude v technologii a počítačové systémy. Jeho podstata spočívá zpravidla v přítomnosti dvou klíčů, z nichž jeden je předáván veřejně a druhý je tajný (soukromý). Veřejný klíč se používá k zašifrování zprávy a tajný se používá k dešifrování zprávy.

Roli veřejného klíče nejčastěji hraje velmi velké číslo, který má pouze dva dělitele, nepočítaje jednoho a samotného čísla. Společně tyto dva dělitele tvoří tajný klíč.

Podívejme se na jednoduchý příklad. Nechť veřejný klíč je 905. Jeho děliteli jsou čísla 1, 5, 181 a 905. tajný klíč bude tam např. číslo 5*181. Řekli byste, že je to příliš jednoduché? Co když je veřejné číslo číslo s 60 číslicemi? Je matematicky obtížné vypočítat dělitele velkého čísla.

Pro realističtější příklad si představte, že vybíráte peníze z bankomatu. Při čtení karty jsou osobní údaje zašifrovány určitým veřejným klíčem a na straně banky jsou informace dešifrovány tajným klíčem. A tento veřejný klíč lze pro každou operaci změnit. Ale neexistují žádné způsoby, jak rychle najít klíčové oddělovače při jeho zachycení.

Trvanlivost písma

Šifrovací síla šifrovacího algoritmu spočívá v jeho schopnosti odolat hackerům. Tento parametr je nejdůležitější pro jakékoli šifrování. Je zřejmé, že jednoduchá substituční šifra, kterou může rozluštit každý elektronické zařízení, je jedním z nejvíce nestabilních.

Dnes neexistuje společné standardy, podle kterého by se dala posoudit síla šifry. Je to náročné na práci a dlouhý proces. Existuje však řada komisí, které v této oblasti vytvořily standardy. Například, minimální požadavky k algoritmu Pokročilé šifrování Encryption Standard nebo AES, vyvinutý NIST USA.

Pro informaci: Vernamova šifra je považována za nejodolnější šifru proti prolomení. Jeho výhodou je zároveň to, že jde podle algoritmu o nejjednodušší šifru.

Sergej Panasenko,
vedoucí vývojového oddělení software společnost "Ankad"
[e-mail chráněný]

Základní pojmy

Proces převodu otevřených dat na šifrovaná data a naopak se obvykle nazývá šifrování a dvě složky tohoto procesu se nazývají šifrování a dešifrování. Matematicky je tato transformace reprezentována následujícími závislostmi, které popisují akce s původními informacemi:

C = Ek1(M)

M" = Dk2(C),

kde M (zpráva) - otevřené informace(v literatuře o bezpečnosti informací často označované jako „zdrojový text“);
C (cipher text) - šifrovaný text (nebo kryptogram) získaný jako výsledek šifrování;
E (šifrování) - šifrovací funkce, která provádí šifrovací transformace na zdrojovém textu;
k1 (klíč) - parametr funkce E, nazývaný šifrovací klíč;
M" - informace získané v důsledku dešifrování;
D (decryption) - dešifrovací funkce, která provádí inverzní kryptografické transformace na šifrovaném textu;
k2 je klíč používaný k dešifrování informací.

Pojem „klíč“ v normě GOST 28147-89 (algoritmus symetrické šifrování) je definován takto: „specifický tajný stav některých parametrů algoritmu kryptografické transformace, zajišťující výběr jedné transformace z množiny možných pro tohoto algoritmu transformace." Jinými slovy, klíč je jedinečný prvek, pomocí kterého můžete změnit výsledky šifrovacího algoritmu: stejný zdrojový text bude při použití různých klíčů zašifrován odlišně.

Aby se výsledek dešifrování shodoval s původní zpráva(tj. pro M" = M) musí být současně splněny dvě podmínky. Za prvé, dešifrovací funkce D musí odpovídat šifrovací funkci E. Za druhé, dešifrovací klíč k2 musí odpovídat šifrovacímu klíči kl.

Pokud byl pro šifrování použit kryptograficky silný šifrovací algoritmus, pak při absenci správného klíče k2 není možné získat M" = M. Kryptografická síla je hlavní charakteristikou šifrovacích algoritmů a především udává stupeň složitosti získání originálu text ze zašifrovaného textu bez klíče k2.

Šifrovací algoritmy lze rozdělit do dvou kategorií: symetrické a asymetrické šifrování. V prvním případě je poměr šifrovacích a dešifrovacích klíčů definován jako k1 = k2 = k (tj. funkce E a D používají stejný šifrovací klíč). Při asymetrickém šifrování se šifrovací klíč k1 vypočítá z klíče k2 tak, že inverzní konverze nemožné např. pomocí vzorce k1 = ak2 mod p (a a p jsou parametry použitého algoritmu).

Symetrické šifrování

Symetrické šifrovací algoritmy se datují do starověku: právě tento způsob skrývání informací používal římský císař Gaius Julius Caesar v 1. století před naším letopočtem. e. a algoritmus, který vynalezl, je známý jako „Caesarův kryptosystém“.

V současnosti je nejznámějším algoritmem symetrický DES šifrování(Data Encryption Standard), vyvinutý v roce 1977. Donedávna to byl „americký standard“, protože vláda této země doporučila jeho použití k implementaci různé systémyšifrování dat. Navzdory skutečnosti, že se původně plánovalo použití DES ne déle než 10-15 let, pokusy o jeho nahrazení začaly až v roce 1997.

DES se nebudeme podrobně zabývat (téměř všechny knihy na seznamu doplňkové materiály sníst to Detailní popis) a pojďme k modernějším šifrovacím algoritmům. Za zmínku stojí pouze to, že hlavním důvodem pro změnu šifrovacího standardu je jeho relativně slabá kryptografická síla, důvodem je, že délka klíče DES je pouze 56 významné bity. Je známo, že každý silný šifrovací algoritmus lze prolomit vyzkoušením všech možných šifrovacích klíčů (tzv. hrubou silou - hrubou silou Záchvat). Je snadné spočítat, že shluk 1 milionu procesorů, z nichž každý počítá 1 milion klíčů za sekundu, zkontroluje 256 variant klíčů DES za téměř 20 hodin, a protože podle dnešních standardů takový výpočetní výkon jsou zcela reálné, je jasné, že 56bitový klíč je příliš krátký a Algoritmus DES nutno vyměnit za silnější.

Dnes se stále častěji používají dva moderní silné šifrovací algoritmy: domácí standard GOST 28147-89 a nový americký kryptografický standard - AES (Advanced Encryption Standard).

Norma GOST 28147-89

Algoritmus definovaný GOST 28147-89 (obr. 1) má délku šifrovacího klíče 256 bitů. Šifruje informace v blocích po 64 bitech (takové algoritmy se nazývají blokové algoritmy), které jsou pak rozděleny do dvou podbloků po 32 bitech (N1 a N2). Podblok N1 je zpracován určitým způsobem, načež se jeho hodnota přičte k hodnotě podbloku N2 (sčítání se provádí modulo 2, tzn. logická operace XOR - "exclusive or"), a pak jsou dílčí bloky prohozeny. Tato transformace provedeno určitý početčasy („koly“): 16 nebo 32 v závislosti na provozním režimu algoritmu. V každém kole se provádějí dvě operace.

První je klíčování. Obsah podbloku N1 je doplněn modulo 2 s 32bitovou částí klíče Kx. Úplný klíčšifrování je reprezentováno jako zřetězení 32bitových podklíčů: K0, K1, K2, K3, K4, K5, K6, K7. Během procesu šifrování je použit jeden z těchto podklíčů v závislosti na čísle kola a provozním režimu algoritmu.

Druhou operací je výměna stolu. Po zaklíčování se podblok N1 rozdělí na 8 částí po 4 bitech, z nichž hodnota každého je nahrazena v souladu s tabulkou náhrad pro tuto část podbloku. Dílčí blok je poté bitově otočen doleva o 11 bitů.

Záměny tabulek(Substitution box - S-box) se často používají v moderních šifrovacích algoritmech, takže stojí za to vysvětlit, jak je taková operace organizována. Výstupní hodnoty bloků jsou zaznamenány v tabulce. Datový blok určitého rozměru (v našem případě - 4bitový) má svůj vlastní číselné znázornění, který udává číslo výstupní hodnoty. Pokud například S-box vypadá jako 4, 11, 2, 14, 15, 0, 8, 13, 3, 12, 9, 7, 5, 10, 6, 1 a 4bitový blok „0100“ přišel na vstup (hodnota 4), pak podle tabulky výstupní hodnota se bude rovnat 15, tj. "1111" (0 a 4, 1 a 11, 2 a 2 ...).

Algoritmus definovaný GOST 28147-89 poskytuje čtyři provozní režimy: jednoduchá výměna, hraní, hraní s zpětná vazba a generování imitačních předpon. Používají stejnou transformaci šifrování popsanou výše, ale protože účel režimů je jiný, tato transformace se v každém z nich provádí jinak.

V režimu snadná výměna Pro zašifrování každého 64bitového bloku informací se provede 32 výše popsaných kol. V tomto případě se 32bitové podklíče používají v následujícím pořadí:

K0, K1, K2, K3, K4, K5, K6, K7, K0, K1 atd. - v kolech 1 až 24;

K7, K6, K5, K4, K3, K2, K1, K0 - v kolech 25 až 32.

Dekódování v tento režim se provádí přesně stejným způsobem, ale s mírně odlišnou sekvencí použití podklíčů:

K0, K1, K2, K3, K4, K5, K6, K7 - v kolech 1 až 8;

K7, K6, K5, K4, K3, K2, K1, K0, K7, K6 atd. - v 9. až 32. kole.

Všechny bloky jsou šifrovány nezávisle na sobě, to znamená, že výsledek šifrování každého bloku závisí pouze na jeho obsahu (odpovídající bloku původního textu). Pokud existuje několik identických bloků původního (prostého) textu, odpovídající bloky šifrovaného textu budou také identické, což poskytuje další užitečné informace pro kryptoanalytika, který se snaží prolomit šifru. Tento režim se tedy používá především pro šifrování samotných šifrovacích klíčů (velmi často jsou implementována víceklíčová schémata, ve kterých jsou z řady důvodů klíče šifrovány na sobě). Pro šifrování samotné informace jsou určeny další dva provozní režimy – gama a gama se zpětnou vazbou.

V gama režim každý blok prostý text bitově přidaný modulo 2 s 64bitovým šifrovacím gama blokem. Gama šifra je speciální sekvence, která je získána jako výsledek určitých operací s registry N1 a N2 (viz obr. 1).

1. Jejich počáteční naplnění se zapíše do registrů N1 a N2 - 64bitová hodnota nazývaná synchronizační zpráva.

2. Obsah registrů N1 a N2 (v tomto případě synchronizační zprávy) je zašifrován v režimu jednoduché výměny.

3. K obsahu registru N1 se přičte modulo (232 - 1) s konstantou C1 = 224 + 216 + 28 + 24 a výsledek sčítání se zapíše do registru N1.

4. Obsah registru N2 se sečte modulo 232 s konstantou C2 = 224 + 216 + 28 + 1 a výsledek sčítání se zapíše do registru N2.

5. Obsah registrů N1 a N2 je vydán jako 64bitový gama blok šifry (v tomto případě N1 a N2 tvoří první gama blok).

Pokud je potřeba další gama blok (tj. šifrování nebo dešifrování musí pokračovat), vrátí se ke kroku 2.

Pro dešifrování se gama generuje podobným způsobem a poté se šifrovaný text a bity gama znovu XORují. Jelikož je tato operace vratná, v případě správně rozvinutého měřítka se získá původní text (tabulka).

Šifrování a dešifrování v gama režimu

K vyvinutí šifry potřebné k dešifrování gama musí mít uživatel dešifrující kryptogram stejný klíč a stejnou hodnotu synchronizační zprávy, jaké byly použity při šifrování informací. V opačném případě nebude možné ze zašifrovaného získat původní text.

Ve většině implementací algoritmu GOST 28147-89 není synchronizační zpráva tajná, nicméně existují systémy, kde je synchronizační zpráva stejným tajným prvkem jako šifrovací klíč. U takových systémů je efektivní délka klíče algoritmu (256 bitů) zvýšena o dalších 64 bitů tajné synchronizační zprávy, kterou lze rovněž považovat za klíčový prvek.

V režimu zpětné vazby gama se k naplnění registrů N1 a N2, počínaje 2. blokem, nepoužívá předchozí gama blok, ale výsledek zašifrování předchozího bloku otevřeného textu (obr. 2). První blok v tomto režimu je generován zcela podobně jako předchozí.

Rýže. 2. Vývoj šifry gama v režimu gama se zpětnou vazbou.

S ohledem na režim generace imitačních předpon, měl by být definován pojem předmětu generování. Imitační předpona je kryptografická kontrolní součet, vypočítaný pomocí šifrovacího klíče a určený k ověření integrity zpráv. Při generování prefixu imitace se provádějí následující operace: první 64bitový blok informačního pole, pro který je vypočítán prefix imitace, je zapsán do registrů N1 a N2 a zašifrován v režimu redukovaného jednoduchého nahrazení (tzv. provede se prvních 16 kol z 32). Získaný výsledek se sečte modulo 2 s další blok informace s uložením výsledku do N1 a N2.

Cyklus se opakuje až do posledního bloku informací. Výsledný 64bitový obsah registrů N1 a N2 nebo jejich části v důsledku těchto transformací se nazývá prefix imitace. Velikost předpony imitace se vybírá na základě požadované spolehlivosti zpráv: s délkou předpony imitace r bitů je pravděpodobnost, že změna ve zprávě zůstane nepovšimnuta, rovna 2-r Použita je 32bitová imitace prefixu, tedy polovina obsahu registrů. To stačí, protože jako každý kontrolní součet je imitace přílohy určena především k ochraně před náhodným zkreslením informací. Na ochranu před úmyslnou úpravou dat, jiné kryptografických metod- především elektronický digitální podpis.

Při výměně informací slouží předpona imitace jako druh dodatečné prostředkyřízení. Vypočítává se pro prostý text, když je jakákoli informace zašifrována a je odeslána spolu se šifrovaným textem. Po dešifrování se vypočítá nová hodnota předpony imitace a porovná se s odeslanou. Pokud se hodnoty neshodují, znamená to, že šifrovaný text byl poškozen během přenosu nebo byly během dešifrování použity nesprávné klíče. Imitační předpona je užitečná zejména pro kontrolu správného dešifrování klíčových informací při použití víceklíčových schémat.

Algoritmus GOST 28147-89 je považován za velmi silný algoritmus - v současné době nebyl navržen žádný další pro jeho zveřejnění efektivní metody než výše zmíněná metoda „hrubé síly“. Jeho vysoké odolnosti je dosaženo především díky dlouhá délka klíč - 256 bitů. Při použití tajné synchronizační zprávy se efektivní délka klíče zvýší na 320 bitů a šifrování náhradní tabulky přidává další bity. Kryptografická síla navíc závisí na počtu transformačních kol, který by podle GOST 28147-89 měl být 32 (plného efektu rozptylu vstupních dat je dosaženo po 8 kolech).

standard AES

Na rozdíl od algoritmu GOST 28147-89, který zůstal dlouho tajný, americký standard AES šifrování, který má nahradit DES, byl vybrán prostřednictvím otevřené soutěže, kde všechny zainteresované organizace a jednotlivci mohli studovat a komentovat kandidátské algoritmy.

Soutěž na nahrazení DES byla vyhlášena v roce 1997. Národní ústav Americké standardy a technologie (NIST - National Institute of Standards and Technology). Do soutěže bylo předloženo 15 kandidátských algoritmů vyvinutých jak známými organizacemi v oblasti kryptografie (RSA Security, Counterpane atd.), tak jednotlivci. Výsledky soutěže byly vyhlášeny v říjnu 2000: vítězem se stal Rijndaelův algoritmus, který vyvinuli dva kryptografové z Belgie, Vincent Rijmen a Joan Daemen.

Rijndaelův algoritmus není jako většina známé algoritmy symetrické šifrování, jehož struktura se nazývá „síť Feistel“ a je podobná ruskému GOST 28147-89. Zvláštností Feistelovy sítě je, že vstupní hodnota je rozdělena do dvou nebo více podbloků, z nichž část je v každém kole zpracována podle určitého zákona, načež je superponována na nezpracované podbloky (viz obr. 1).

Na rozdíl od domácího šifrovacího standardu představuje algoritmus Rijndael datový blok ve formě dvourozměrného bajtového pole o velikosti 4X4, 4X6 nebo 4X8 (je povoleno použití několika pevné velikosti zašifrovaný blok informací). Všechny operace se provádějí na jednotlivých bytech pole, stejně jako na nezávislé sloupce a linky.

Algoritmus Rijndael provádí čtyři transformace: BS (ByteSub) - tabulkové nahrazení každého bytu pole (obr. 3); SR (ShiftRow) - posun řádků pole (obr. 4). Při této operaci zůstane první řádek nezměněn a zbytek se cyklicky posouvá bajt po bajtu doleva o pevný počet bajtů v závislosti na velikosti pole. Například pro pole 4X4 jsou řádky 2, 3 a 4 posunuty o 1, 2 a 3 bajty. Následuje MC (MixColumn) - operace na nezávislých sloupcích pole (obr. 5), kdy je každý sloupec vynásoben pevnou maticí c(x) podle určitého pravidla. A nakonec AK (AddRoundKey) - přidání klíče. Ke každému bitu pole je přidán modulo 2 s odpovídajícím bitem kulatého klíče, který se zase vypočítává určitým způsobem z šifrovacího klíče (obr. 6).

Rýže. 3. Provoz BS.

Rýže. 4. Operace SR.

Rýže. 5. Provoz MC.

Počet šifrovacích kol (R) v algoritmu Rijndael je variabilní (10, 12 nebo 14 kol) a závisí na velikosti bloku a šifrovacím klíči (existuje také několik pevných velikostí klíče).

Dešifrování se provádí pomocí následujících zpětných operací. Na inverzní tabulce se provede inverze tabulky a nahrazení tabulky (ve vztahu k tabulce použité při šifrování). Inverzní operace k SR je otočení řádků doprava spíše než doleva. Inverzní operace pro MC je násobení pomocí stejných pravidel jinou maticí d(x) splňující podmínku: c(x) * d(x) = 1. Přidání klíče AK je inverzní samo o sobě, protože používá pouze XOR úkon. Tyto zpětné operace jsou aplikovány během dešifrování v opačném pořadí, než jaké se používá během šifrování.

Rijndael se stal novým standardem pro šifrování dat díky řadě výhod oproti jiným algoritmům. V první řadě poskytuje vysoká rychlostšifrování na všech platformách: v softwarové i hardwarové implementaci. Rozlišuje se nesrovnatelně nejlepší příležitosti paralelizace výpočtů ve srovnání s jinými algoritmy přihlášenými do soutěže. Navíc nároky na zdroje pro jeho provoz jsou minimální, což je důležité při použití v zařízeních s omezenými výpočetními možnostmi.

Za jedinou nevýhodu algoritmu lze považovat jeho vlastní nekonvenční schéma. Faktem je, že vlastnosti algoritmů založených na Feistelově síti byly dobře prostudovány a Rijndael na rozdíl od nich může obsahovat skryté zranitelnosti, který lze objevit až po uplynutí určité doby od začátku jeho široké distribuce.

Asymetrické šifrování

Asymetrické šifrovací algoritmy, jak již bylo uvedeno, používají dva klíče: k1 - šifrovací klíč, neboli veřejný, a k2 - dešifrovací klíč, neboli tajný. Veřejný klíč se vypočítá z tajenky: k1 = f(k2).

Asymetrické šifrovací algoritmy jsou založeny na použití jednosměrných funkcí. Podle definice je funkce y = f(x) jednosměrná, pokud: je snadné ji vypočítat pro všechny možné možnosti x a pro většinu možné hodnoty y je poměrně obtížné vypočítat hodnotu x, pro kterou y = f(x).

Příkladem jednosměrné funkce je násobení dvou velkých čísel: N = P*Q. Toto násobení samo o sobě je jednoduchá obsluha. Inverzní funkce (rozklad N na dva velké faktory), nazývaná podle moderních odhadů faktorizace, je však poměrně složitá matematický problém. Například faktorizace N s rozměrem 664 bitů při P ? Q bude vyžadovat přibližně 1023 operací a pro inverzní výpočet x pro modulární exponent y = ax mod p se známými a, p a y (se stejnými rozměry aap) je třeba provést přibližně 1026 operací. Poslední uvedený příklad se nazývá Problém diskrétního logaritmu (DLP) a tento druh funkce se často používá v algoritmech asymetrického šifrování a také v algoritmech používaných k vytváření elektronického digitálního podpisu.

Další důležitou třídou funkcí používaných v asymetrickém šifrování jsou jednosměrné funkce zadních vrátek. Jejich definice říká, že funkce je jednosměrná se zadními vrátky, pokud je jednosměrná a lze ji efektivně vypočítat inverzní funkce x = f-1(y), tj. pokud je znám „tajný průchod“ (určité tajné číslo, v aplikaci na algoritmy asymetrického šifrování - hodnota tajného klíče).

Jednosměrné funkce zadních vrátek se používají v široce používaném asymetrickém šifrovacím algoritmu RSA.

Algoritmus RSA

Vyvinuli jej v roce 1978 tři autoři (Rivest, Shamir, Adleman), svůj název dostal podle prvních písmen příjmení vývojářů. Spolehlivost algoritmu je založena na obtížnosti faktorizace velkých čísel a výpočtu diskrétních logaritmů. Hlavní parametr Algoritmus RSA- modul systému N, podle kterého se provádějí všechny výpočty v systému a N = P*Q (P a Q jsou tajné náhodné jednoduché velká čísla, obvykle stejné velikosti).

Tajný klíč k2 je vybrán náhodně a musí splňovat následující podmínky:

1

kde GCD je největší společný dělitel, tj. k1 musí být prvočíslo k hodnotě Eulerovy funkce F(N), přičemž tato funkce se rovná počtu kladných celých čísel v rozsahu od 1 do N s prvočíslem až N, a vypočítá se jako F(N) = (P - 1)* (Q - 1).

Veřejný klíč k1 se vypočítá ze vztahu (k2*k1) = 1 mod F(N) a pro tento účel je použit zobecněný euklidovský algoritmus (algoritmus pro výpočet největšího společného dělitele). Šifrování datového bloku M pomocí algoritmu RSA se provádí následovně: C=M [k síle k1] mod N. Všimněte si, že protože ve skutečném kryptosystému využívajícím RSA je číslo k1 velmi velké (v současné době může jeho rozměr dosahovat až 2048 bitů), přímý výpočet M [k síle k1] neskutečný. K jeho získání se používá kombinace opakovaného kvadrátu M a násobení výsledků.

Inverze této funkce pro velké rozměry není proveditelná; jinými slovy, je nemožné najít M vzhledem ke známým C, N a k1. S tajným klíčem k2 je však možné pomocí jednoduchých transformací vypočítat M = Ck2 mod N. Je zřejmé, že kromě samotného tajného klíče je nutné zajistit utajení parametrů P a Q. Pokud útočník získá jejich hodnoty , bude schopen vypočítat tajný klíč k2.

Které šifrování je lepší?

Hlavní nevýhodou symetrického šifrování je nutnost přenášet klíče „z ruky do ruky“. Tato nevýhoda je velmi závažná, protože znemožňuje použití symetrického šifrování v systémech s neomezeným počtem účastníků. Nicméně jinak má symetrické šifrování některé výhody, které jsou jasně viditelné na pozadí vážných nevýhod asymetrického šifrování.

Prvním z nich je nízká rychlost šifrovacích a dešifrovacích operací kvůli přítomnosti operací náročných na zdroje. Další „teoretickou“ nevýhodou je, že kryptografická síla asymetrických šifrovacích algoritmů nebyla matematicky prokázána. Je to dáno především problémem diskrétního logaritmu - dosud nebylo prokázáno, že jeho řešení v přijatelném čase je nemožné. Zbytečné potíže vytváří i nutnost chránit veřejné klíče před záměnou – nahrazením veřejného klíče legálního uživatele bude moci útočník zašifrovat důležitou zprávu svým veřejným klíčem a následně ji snadno dešifrovat svým soukromým klíčem.

Tyto nedostatky však nebrání širokému používání asymetrických šifrovacích algoritmů. Dnes existují kryptosystémy, které podporují certifikaci veřejných klíčů a také kombinují symetrické a asymetrické šifrovací algoritmy. Ale to je téma na samostatný článek.

Šifrování dat je nesmírně důležité pro ochranu soukromí. V tomto článku se budu zabývat různými typy a metodami šifrování, které se dnes používají k ochraně dat.

Věděl jsi?
V římských dobách šifrování používal Julius Caesar k tomu, aby dopisy a zprávy byly pro nepřítele nečitelné. Hrálo důležitou roli jako vojenská taktika, zejména během válek.

Jak možnosti internetu neustále rostou, stále více našich obchodů je provozováno online. Mezi nejvýznamnější patří internetové bankovnictví, online platby, e-maily, výměna soukromých a úředních zpráv atd., které zahrnují výměnu důvěrných dat a informací. Pokud se tato data dostanou do nesprávných rukou, může to poškodit nejen jednotlivého uživatele, ale i celý online obchodní systém.

Aby se tomu zabránilo, bylo přijato několik opatření pro zabezpečení sítě na ochranu přenosu osobních údajů. Hlavní z nich jsou procesy šifrování a dešifrování dat, které jsou známé jako kryptografie. Ve většině dnešních systémů se používají tři hlavní způsoby šifrování: hašování, symetrické a asymetrické šifrování. V následujících řádcích budu o každém z těchto typů šifrování hovořit podrobněji.

Typy šifrování

Symetrické šifrování

Při symetrickém šifrování jsou normální čitelná data, známá jako prostý text, zašifrována tak, že se stanou nečitelná. Toto kódování dat se provádí pomocí klíče. Jakmile jsou data zašifrována, mohou být bezpečně odeslána do přijímače. U příjemce jsou šifrovaná data dekódována pomocí stejného klíče, který byl použit pro kódování.

Je tedy zřejmé, že klíč je nejdůležitější součástí symetrického šifrování. Musí být skryta před cizinci, protože kdokoli, kdo k ní má přístup, bude moci dešifrovat soukromá data. To je důvod, proč je tento typ šifrování také známý jako "tajný klíč".

V moderních systémech je klíčem obvykle řetězec dat, který je odvozen ze silného hesla nebo ze zcela náhodného zdroje. Je vložen do symetrického šifrovacího softwaru, který jej používá k utajení vstupních dat. Šifrování dat je dosaženo pomocí symetrického šifrovacího algoritmu, jako je Data Encryption Standard (DES), Advanced Encryption Standard (AES) nebo International Data Encryption Algorithm (IDEA).

Omezení

Nejslabším článkem tohoto typu šifrování je zabezpečení klíče, a to jak z hlediska uložení, tak přenosu k ověřenému uživateli. Pokud je hacker schopen získat tento klíč, může snadno dešifrovat zašifrovaná data, čímž zmaří celý účel šifrování.

Další nevýhodou je, že software, který data zpracovává, neumí pracovat se zašifrovanými daty. Proto, aby bylo možné tento software používat, musí být data nejprve dekódována. Pokud je kompromitován samotný software, může útočník snadno získat data.

Asymetrické šifrování

Šifrování asymetrickým klíčem funguje podobně jako symetrický klíč v tom, že používá klíč k šifrování přenášených zpráv. K dešifrování této zprávy však místo toho, aby použil stejný klíč, použije úplně jiný.

Klíč použitý pro kódování je dostupný všem uživatelům sítě. Jako takový je znám jako „veřejný“ klíč. Na druhou stranu klíč použitý k dešifrování je uchováván v tajnosti a je určen pro soukromé použití samotným uživatelem. Proto je znám jako „soukromý“ klíč. Asymetrické šifrování je také známé jako šifrování veřejným klíčem.

Vzhledem k tomu, že u této metody nemusí být tajný klíč potřebný k dešifrování zprávy přenášen pokaždé a je obvykle znám pouze uživateli (příjemci), je pravděpodobnost, že se hackerovi podaří zprávu dešifrovat, vysoká. dolní.

Diffie-Hellman a RSA jsou příklady algoritmů, které používají šifrování veřejným klíčem.

Omezení

Mnoho hackerů používá man-in-the-middle jako formu útoku k obejití tohoto typu šifrování. V asymetrickém šifrování dostanete veřejný klíč, který se používá k bezpečné výměně dat s jinou osobou nebo službou. Hackeři však používají síťový podvod, aby vás přiměli ke komunikaci s nimi, zatímco vy jste vedeni k přesvědčení, že jste na zabezpečené lince.

Chcete-li lépe porozumět tomuto typu hackování, zvažte dvě interagující strany, Sashu a Natashu, a hackera Sergeje, kteří mají v úmyslu zachytit jejich rozhovor. Nejprve Sasha odešle zprávu přes síť určenou pro Natashu a požádá o její veřejný klíč. Sergej zachytí tuto zprávu a získá veřejný klíč, který je s ní spojen, a použije jej k zašifrování a odeslání falešné zprávy Nataše, která obsahuje jeho veřejný klíč namísto Sašina.

Natasha, která si myslí, že tato zpráva přišla od Sashy, ji nyní zašifruje Sergeiovým veřejným klíčem a odešle ji zpět. Tato zpráva byla znovu zachycena Sergejem, dešifrována, upravena (v případě potřeby), znovu zašifrována pomocí veřejného klíče, který Sasha původně poslal, a odeslána zpět Sashe.

Když tedy Sasha obdrží tuto zprávu, byl veden k tomu, aby věřil, že přišla od Nataši, a není si vědom špatné hry.

Hašování

Hašovací technika používá algoritmus známý jako hashovací funkce ke generování speciálního řetězce z daných dat, známého jako hash. Tento hash má následující vlastnosti:

• stejná data vždy vytvářejí stejný hash.
• Ze samotného hashe není možné generovat nezpracovaná data.
• Není praktické zkoušet různé kombinace vstupů ve snaze vygenerovat stejný hash.

Hlavním rozdílem mezi hašováním a dalšími dvěma formami šifrování dat je tedy to, že jakmile jsou data zašifrována (hashována), nelze je získat zpět v původní podobě (dešifrovat). Tato skutečnost zajišťuje, že i když se hackerovi dostane do rukou hash, nebude mu k ničemu, protože nebude schopen dešifrovat obsah zprávy.

Message Digest 5 (MD5) a Secure Hash Algorithm (SHA) jsou dva široce používané hashovací algoritmy.

Omezení

Jak již bylo zmíněno dříve, je téměř nemožné dešifrovat data z daného hashe. To však platí pouze v případě, že je implementováno silné hashování. V případě slabé implementace hašovací techniky, s využitím dostatku zdrojů a útoků hrubou silou, dokáže vytrvalý hacker najít data, která odpovídají hash.

Kombinace šifrovacích metod

Jak bylo diskutováno výše, každá z těchto tří metod šifrování trpí některými nevýhodami. Při použití kombinace těchto metod však tvoří bezpečný a vysoce účinný šifrovací systém.

Nejčastěji se techniky soukromého a veřejného klíče kombinují a používají společně. Metoda soukromého klíče umožňuje rychlé dešifrování, zatímco metoda veřejného klíče nabízí bezpečnější a pohodlnější způsob přenosu tajného klíče. Tato kombinace metod je známá jako „digitální obálka“. Software pro šifrování e-mailů PGP je založen na technice „digitální obálky“.

Hašování se používá jako prostředek kontroly síly hesla. Pokud systém uloží hash hesla místo hesla samotného, ​​bude to bezpečnější, protože i když se hackerovi dostane do rukou tento hash, nebude mu rozumět (přečíst). Během ověřování systém zkontroluje hash příchozího hesla a zjistí, zda se výsledek shoduje s uloženým. Tímto způsobem bude skutečné heslo viditelné pouze v krátkých okamžicích, kdy je třeba je změnit nebo ověřit, čímž se výrazně sníží pravděpodobnost, že se dostane do nesprávných rukou.

Hašování se také používá k autentizaci dat pomocí tajného klíče. Pomocí dat a tohoto klíče se vygeneruje hash. Viditelná jsou tedy pouze data a hash a samotný klíč se nepřenáší. Tímto způsobem, pokud jsou provedeny změny v datech nebo hash, budou snadno detekovány.

Závěrem lze říci, že tyto techniky lze použít k efektivnímu kódování dat do nečitelného formátu, který může zajistit, že zůstanou bezpečná. Většina moderních systémů obvykle používá kombinaci těchto metod šifrování spolu se silnými implementacemi algoritmů ke zlepšení zabezpečení. Kromě zabezpečení poskytují tyto systémy také mnoho dalších výhod, jako je ověření identity uživatele a zajištění toho, že přijatá data nemohou být zmanipulována.

09.07.2003

Co je šifrování?

Šifrování lidstvo používá od okamžiku, kdy se objevily první tajné informace, tedy takové informace, ke kterým by měl být omezen přístup. To bylo velmi dávno – například jedna z nejznámějších šifrovacích metod je pojmenována po Caesarovi, který, pokud ji sám nevynalezl, tak ji aktivně používal (viz postranní panel).

Kryptografie zajišťuje, že význam zprávy je skrytý a odhalený dešifrováním pomocí speciálních algoritmů a klíčů. Klíč chápeme jako specifický tajný stav parametrů šifrovacích a dešifrovacích algoritmů. Znalost klíče umožňuje přečíst tajnou zprávu. Jak však uvidíte níže, neznalost klíče nemusí vždy zaručit, že zprávu nebude moci přečíst cizí osoba.

Proces prolomení šifry bez znalosti klíče se nazývá kryptanalýza. Doba potřebná k prolomení šifry je určena její kryptografickou silou. Čím větší je, tím „silnější“ je šifrovací algoritmus. Ještě lepší je, když je zpočátku nemožné vůbec zjistit, zda je výsledek hacku dosažitelný.

Základní moderní šifrovací metody

Mezi různými metodami šifrování lze rozlišit následující hlavní metody:

• Algoritmy náhrady nebo náhrady - znaky zdrojového textu jsou nahrazeny znaky jiné (nebo stejné) abecedy podle předem určeného schématu, které bude klíčem této šifry. Samostatně se tato metoda prakticky nepoužívá v moderních kryptosystémech kvůli její extrémně nízké kryptografické síle.
• Algoritmy přeuspořádání - znaky původního textu jsou prohozeny podle určitého principu, kterým je tajný klíč. Samotný permutační algoritmus má nízkou kryptografickou sílu, ale je součástí mnoha moderních kryptosystémů.
• Gama algoritmy - znaky zdrojového textu jsou přidány ke znakům určité náhodné sekvence. Nejčastějším příkladem je šifrování souborů „username.pwl“, ve kterém operační systém Microsoft Windows 95 ukládá hesla k síťovým zdrojům daného uživatele (hesla pro přihlášení k NT serverům, hesla pro DialUp přístup k internetu atd.) .

Když uživatel zadá své heslo při přihlašování do Windows 95, vygeneruje se z něj gama (vždy stejná) pomocí šifrovacího algoritmu RC4, který se používá k šifrování síťových hesel. Jednoduchost výběru hesla je v tomto případě způsobena tím, že Windows preferuje vždy stejné barevné schéma.

• Algoritmy založené na složitých matematických transformacích výchozího textu podle určitého vzorce. Mnoho z nich používá nevyřešené matematické úlohy. Například šifrovací algoritmus RSA široce používaný na internetu je založen na vlastnostech prvočísel.

Symetrické a asymetrické kryptosystémy

Než přejdeme k jednotlivým algoritmům, pojďme se krátce zamyslet nad konceptem symetrických a asymetrických kryptosystémů. Vygenerovat tajný klíč a zašifrovat s ním zprávu je jen polovina úspěchu. Jak ale může být takový klíč zaslán někomu, kdo jej musí použít k dešifrování původní zprávy? Přenos šifrovacího klíče je považován za jeden z hlavních problémů kryptografie.

I když zůstáváme v rámci symetrického systému (takto pojmenovaný, protože pro šifrování a dešifrování se používá stejný klíč), je nutné mít spolehlivý komunikační kanál pro přenos tajného klíče. Takový kanál však není vždy dostupný, a proto američtí matematici Diffie, Hellman a Merkle vyvinuli v roce 1976 koncept veřejného klíče a asymetrického šifrování. V takových kryptosystémech je veřejně dostupný pouze klíč pro proces šifrování a postup dešifrování zná pouze vlastník tajného klíče.

Když například chci, aby mi byla zaslána zpráva, vygeneruji veřejný a soukromý klíč. Pošlu vám to, vy zašifrujete zprávu a pošlete mi ji. Zprávu mohu dešifrovat pouze já, protože jsem tajný klíč nikomu nedal. Oba klíče jsou samozřejmě propojeny zvláštním způsobem (v každém kryptosystému různými způsoby) a distribuce veřejného klíče nezničí kryptografickou sílu systému.

V asymetrických systémech musí být splněn následující požadavek: neexistuje (nebo ještě není znám) žádný algoritmus, který by odvozoval původní text z kryptotextu a veřejného klíče. Příkladem takového systému je známý kryptosystém RSA.

Algoritmus RSA

Algoritmus RSA (po prvních písmenech příjmení jeho tvůrců Rivest-Shamir-Adleman) je založen na vlastnostech prvočísel (a velmi velkých). Prvočísla jsou ta čísla, která nemají žádného dělitele kromě sebe a jedničky. A koprimá čísla jsou ta čísla, která nemají žádného společného dělitele kromě 1.

Nejprve zvolíme dvě velmi velká prvočísla (velká prvočísla jsou potřebná ke konstrukci velkých silných klíčů. Například unixový program ssh-keygen generuje klíče ve výchozím nastavení dlouhé 1024 bitů).

Pojďme definovat parametr n v důsledku množení p A q. Zvolme velké náhodné číslo a zavolejme ho d a musí být coprime s výsledkem násobení (p -1)* (q -1).

Najděte číslo e, pro které platí vztah

(e*d) mod ((p-1)*(q-1)) = 1

(mod- zbytek po dělení, tj. jestliže e násobeno d je děleno ((p -1)*(q -1)), pak zbytek je 1).

Veřejný klíč je dvojice čísel e a n a zavřeno - d a n.

Při šifrování se se zdrojovým textem zachází jako s číselnou řadou a s každým číslem provedeme operaci

C(i)= (M(i) e) mod n.

Výsledkem je sekvence C(i), který bude tvořit kryptotext. Dekódování informací probíhá podle vzorce

M(i) = (C(i) d) mod n.

Jak vidíte, dešifrování vyžaduje znalost tajného klíče.

Zkusme to na malých číslech.

Pojďme nainstalovat p=3, q=7. Pak n=p*q=21. Vybrat d jako 5. Ze vzorce (e*5) mod 12=1 vypočítat e=17. Veřejný klíč 17, 21 , tajný - 5, 21 .

Pojďme zašifrovat sekvenci "12345":

C(1)= 117 mod 21= 1

C(2)= 217 mod21=11

C(3)= 3 17 mod 21= 12

C(4)= 417 mod 21= 16

C(5)= 517 mod 21= 17

Kryptotext – 1 11 12 16 17.

Zkontrolujeme dešifrování:

M(1)= 15 mod 21= 1

M(2)= 115 mod 21= 2

M(3)= 125 mod 21= 3

M(4)= 165 mod 21= 4

M(5)= 175 mod 21= 5

Jak vidíte, výsledek se shodoval.

Na internetu je široce používán kryptosystém RSA. Když se připojíte k zabezpečenému serveru přes SSL, nainstalujete si do počítače certifikát WebMoney nebo se připojíte ke vzdálenému serveru pomocí Open SSH nebo SecureShell, všechny tyto programy používají šifrování veřejným klíčem pomocí nápadů z algoritmu RSA. Je tento systém opravdu tak spolehlivý?

RSA hackerské soutěže

Od svého vzniku bylo RSA neustále vystaveno útokům hrubou silou. V roce 1978 autoři algoritmu publikovali článek, kde představili řetězec zašifrovaný metodou, kterou právě vynalezli. První člověk, který zprávu rozluštil, dostal odměnu 100 dolarů, ale to vyžadovalo rozdělení 129místného čísla na dva faktory. Toto byla první soutěž, která rozlouskla RSA. Problém byl vyřešen až 17 let po zveřejnění článku.

Šifrovací síla RSA je založena na předpokladu, že je extrémně obtížné, ne-li nemožné, určit soukromý klíč z veřejného klíče. K tomu bylo nutné vyřešit problém existence dělitelů obrovského celého čísla. Doposud to nikdo nevyřešil analytickými metodami a algoritmus RSA lze prolomit pouze hrubou silou. Přísně vzato, tvrzení, že problém faktorizace je obtížný a že prolomení systému RSA je obtížné, také není prokázáno.

Číslo získané jako výsledek zpracování textu zprávy hashovací funkcí je zašifrováno pomocí algoritmu RSA na soukromém klíči uživatele a odesláno příjemci spolu s dopisem a kopií veřejného klíče. Příjemce pomocí veřejného klíče odesílatele provede stejnou hashovací funkci u příchozí zprávy. Pokud jsou obě čísla stejná, znamená to, že zpráva je pravá, ale pokud byl změněn alespoň jeden znak, čísla se nebudou shodovat.

Jeden z nejběžnějších e-mailových klientů v Rusku, program The Bat!, má vestavěné funkce pro přidávání digitálních podpisů do dopisů (při úpravě dopisu věnujte pozornost položce Soukromí). Přečtěte si více o této technice v článku (viz „PC World“, č. 3/02).

Rýže. 3

Kryptografie

Kryptografie je věda o principech, prostředcích a metodách transformace informací, aby byly chráněny před neoprávněným přístupem a zkreslením. V poslední době se vyvíjí velmi, velmi rychle. Je to nekonečný, vzrušující závod, který vyžaduje spoustu času a úsilí: kryptoanalytici prolomí algoritmy, které byly donedávna standardní a široce používané. Mimochodem, nedávno matematici Dan Goldston (USA) a Kem Ildirim (Turecko) prokázali první pravidelnost v rozdělení prvočísel (takové pravidelnosti nebyly dosud zaznamenány). Prvočísla jsou umístěna na číselné ose v určitých shlucích, což usnadňuje jejich nalezení.

Matematický výzkum prováděný po celém světě neustále vede k novým objevům. Kdo ví, možná jsme na pokraji prolomení algoritmu RSA nebo jiných kryptosystémů založených na nevyřešených matematických problémech.

Oleg Bunin- specialista na vývoj softwaru pro velké internetové projekty, zaměstnanec firmy Rambler, http://www..htm).

Caesarův šifrovací systém

Příkladem náhradního algoritmu je šifrovací systém Caesar. Tato metoda je založena na nahrazení každého písmena zprávy jiným posunutím od originálu o pevný počet znaků. Pokuste se rozluštit čtyřverší Omara Khayyama (doba dokončení - 10 minut).

RLZ YOMEIZ AVBZHU IYZAVLU, BZHSCHLU ZHSCHEZZHZ ZHUOSCHZ, EYSH YSHCHAZhFO ISHCHYVESH BSHCHIZHV EESH ZHSCHRSCHG: LF EMRSYU ЪZEZESCHG, RYYO RLZ IIZZISHCHEZ YUKYZHLU, KDUYZESHY MRSY CHEZ.

Udělal jsi to? Zde je odpověď:

Chcete-li žít svůj život moudře, musíte toho hodně vědět,

Pro začátek si zapamatujte dvě důležitá pravidla:

Radši budeš hladovět, než něco jíst

A je lepší být sám, než jen s kýmkoli.

Dešifrovací klíč: posun o sedm znaků (vezměte sedmý) doleva podle abecedy. Abeceda je zacyklená. Velikost písmen není citlivá.

Windows a hesla

Jak Windows šifruje hesla?

Systém vezme heslo, převede ho na velká písmena, zkrátí ho na 14 znaků, poté je rozdělí na dvě poloviny po 7, zašifruje každou zvlášť a uloží je tak, což trochu usnadňuje hackování. Mimochodem, až budete vymýšlet heslo, mějte na paměti, že kombinace delší než 14 znaků má malý význam.

Soutěž AES (Advanced Encryption Standard).

V 80. letech v USA přijali symetrický šifrovací standard pro vnitřní použití - DES ((Data Encryption Standard, podobný standard existuje v Rusku). Ale v roce 1997, kdy se ukázalo, že 56bitový klíč DES nestačí pro spolehlivý cryptosystem, American Standards Institute vyhlásil soutěž o nový standardní algoritmus Z 15 možností byla vybrána ta nejlepší: belgický algoritmus Rijndael (jeho jméno je tvořeno jmény autorů – Rijmen a Daemen, čteno jako „Rijndael“. Tento algoritmus je již zabudován do různých kryptografických nástrojů dodávaných na trh jinými finalisty). .

Kryptografické hašovací funkce

Kryptografické hašovací funkce převádějí vstupní data libovolné velikosti na řetězec pevné velikosti. Je velmi obtížné pro ně najít:

• dvě různé datové sady se stejným výsledkem transformace (odolnost proti kolizi); například počet aritmetických operací potřebných k nalezení datového bloku, který má také krátkou zprávu pro hashovací funkci MD5, je přibližně 2 64;
• vstupní hodnota založená na známém výsledku hašování (nevratnost); pro MD5 je odhadovaný počet operací potřebných k výpočtu původní zprávy 2 128.

Anotace: Tato přednáška má několik cílů. Ukažte rozdíl mezi tradičními a moderními šiframi symetrických klíčů. Přineste moderní blokové šifry a diskutovat o jejich vlastnostech. Vysvětlete, proč musí být moderní blokové šifry navrženy jako substituční. Představte součásti blokových šifer, jako jsou P-boxy a S-boxy. Diskutujte a ukažte rozdíl mezi dvěma třídami šifer: Feistelovými šiframi a nefeistelovými šiframi. Diskutujte o dvou typech útoků speciálně zaměřených na prolomení moderních blokových šifer: diferenciální a lineární kryptoanalýza. Představte pojem „proudové šifry“ a ukažte rozdíl mezi synchronními a nesynchronními šiframi. Diskutujte o lineární a nelineární zpětné vazbě posuvného registru pro implementaci proudových šifer.

Tradiční šifry s symetrický klíč, které jsme dosud studovali, jsou charakterově orientované. S příchodem počítače se bitově orientované šifry staly nutností. Protože informace, které je třeba zašifrovat, nejsou vždy jen text; může sestávat také z čísel, grafiky, audio a video dat. Je vhodné převést tyto typy dat na proud bitů, zašifrovat tento proud a poté zašifrovaný proud přenést. Navíc, když je text zpracováván na úrovni bitů, je každý znak nahrazen 8 (nebo 16) bity, což znamená, že počet znaků se 8 (nebo 16) krát zvětší. Smíchání více znaků zvyšuje bezpečnost.

Tato kapitola poskytuje nezbytný základ pro studium moderních blokových a proudových šifer, kterým se věnují následující tři kapitoly. Většina této kapitoly je věnována diskuzi o obecných myšlenkách moderních blokových šifer a jen malá část je věnována principům moderních proudových šifer.

7.1. Moderní blokové šifry

Moderní bloková šifra se symetrickým klíčem zašifruje n-bitový blok prostého textu nebo dešifruje n-bitový blok šifrovaného textu. Šifrovací nebo dešifrovací algoritmus používá k-bitový klíč. Dešifrovací algoritmus musí být inverzní k šifrovacímu algoritmu a oba fungují pomocí stejného tajného klíče, aby mohl Bob rekonstruovat zprávu odeslanou Alicí. Obrázek 7.1 ukazuje obecnou myšlenku šifrování a dešifrování v moderní blokové šifře.

Rýže. 7.1.

Pokud je velikost zprávy menší než n bitů, je nutné přidat výplň, aby se vytvořil tento nbitový blok; má-li zpráva více než n bitů, musí být rozdělena na n-bitové bloky a do posledního bloku musí být v případě potřeby přidána vhodná výplň. Běžné hodnoty pro n jsou obvykle 64, 128, 256 nebo 512 bitů.

Příklad 7.1

Kolik bitů navíc musí být přidáno do 100znakové zprávy, pokud je kódování 8bitové ASCII a bloková šifra přijímá 64bitové bloky?

Řešení

Zakódujte 100 znaků pomocí 8bitového ASCII. Tato zpráva obsahuje 800 bitů. Zdrojový text musí být dělitelný 64. Pokud | M | a | Podložka |- délka zprávy a délka odsazení

| M | + | Podložka | == 0 mod 64 -> | Podložka | = -800 mod 64->32 mod 64

To znamená, že ke zprávě musí být přidáno 32 bitů výplně (například nul). Text se pak bude skládat z 832 bitů nebo třinácti 64bitových bloků. Všimněte si pouze toho poslední blok obsahuje polstrování. Šifrovač použije šifrovací algoritmus třináctkrát k vytvoření třinácti bloků šifrovaného textu.

Substituce nebo transpozice

Moderní bloková šifra může být navržena tak, aby fungovala buď jako substituční šifra, nebo jako transpoziční šifra. Jedná se o stejnou myšlenku, která se používá v tradičních šifrách, kromě toho, že znaky, které budou nahrazeny nebo přesunuty, obsahují místo znaků bity.

Pokud je šifra navržena jako substituční šifra, bitové hodnoty 1 nebo 0 palců zdrojový text lze nahradit buď 0 nebo 1. To znamená, že původní text a šifrovaný text mohou mít jiné číslo Jednotky. 64bitový blok otevřeného textu, který obsahuje 12 nul a 52 jedniček, může být v šifrovém textu reprezentován 34 nulami a 30 jedničkami. Pokud je šifra navržena jako permutační šifra (transpozice), bity pouze mění své pořadí (přesun), přičemž zachovávají stejný počet znaků v originálu a šifrovém textu. V obou případech je počet možných n-bitových holých textů nebo šifrových textů 2n, protože každý z n bitů použitých v bloku může mít jednu ze dvou hodnot – 0 nebo 1,2 64 bloků po 64 bitech pro nalezení jednoho , což znamená smysl. Pokud by Eva mohla vyzkoušet 1 miliardu bloků za sekundu, trvalo by stovky let, než by tato práce mohla uspět.

b. Ve druhém případě (transpozice) Eva ví, že v původním textu je přesně 10 jedniček, protože transpozice nemění počet jedniček (nebo nul) v šifrovém textu. Eva může spustit vyčerpávající vyhledávací útok pouze s těmi 64bitovými bloky, které mají přesně 10 bloků. Existuje pouze (64!) / [(10!) (54!)] = 151 473 214 816 ze 2 64 slov o 64 bitech, která mají přesně 10 jednotek. Eva je dokáže všechny otestovat za méně než 3 minuty, pokud zvládne 1 miliardu testů za sekundu.

Moderní bloková šifra, odolná vůči vyčerpávajícímu vyhledávacímu útoku, musí být navržena jako substituční šifra.