Lavinový efekt
Lavinový efekt ("efekt laviny") je vlastnost blokových šifer a algoritmů kryptografických hašovacích funkcí. V kryptografii je často žádoucí. Efekt říká, že se musí změnit velká část výstupu, i když se vstup změní jen málo. V dobrých blokových šifrách to znamená: Malá změna klíče nebo otevřeného textu by měla způsobit silnou změnu šifrového textu.
To znamená, že malé změny se mohou rychle šířit, pokud algoritmus používá iterace. Každý bit výstupu tedy závisí na každém bitu vstupu.
Termín lavinový efekt poprvé použil Horst Feistel (Feistel 1973). Později byl tento pojem ztotožněn se Shannonovou vlastností zmatení.
Pokud bloková šifra nebo kryptografická hašovací funkce nesplňuje lavinový efekt ve značné míře, pak má špatnou randomizaci. Kryptoanalytik tedy může provádět předpovědi o vstupu, pokud mu je dán pouze výstup. To může stačit k částečnému nebo úplnému prolomení (cracknutí) algoritmu.
Je to jeden z hlavních cílů návrhu při vytváření silné šifry nebo kryptografické hašovací funkce. Snaží se v ní vytvořit dobrý lavinový efekt. Matematicky se k tomu využívá motýlí efekt. Proto je většina blokových šifer součinovými šiframi. Je to také důvod, proč mají hašovací funkce velké datové bloky.
Hašovací funkce SHA1 má dobrý lavinový efekt. Při změně jediného bitu se součet hašů zcela změní.
Název
Původ názvu jsou sesuvy půdy. Malý kámen se může zřítit dolů, spolu se sněhem a vytvořit ničivý sesuv. Skála byla malá, ale mohla způsobit mnoho zkázy. To je stejné, jako to, co dělá tento efekt. Malá změna na vstupu (skála) by měla změnit výstup (krajinu).
Přísné lavinové kritérium
Přísné lavinové kritérium (SAC; "kritérium silného sesuvu") je vlastnost logických funkcí. Má význam pro kryptografii. Je splněno, pokud se při změně jediného vstupního bitu změní všechny výstupní bity s pravděpodobností 50 procent.
SAC byl postaven na konceptu evoluční úplnosti a lavinovitosti. Zavedli ji Webster a Tavares v roce 1985. V současné době je požadavkem každého moderního kryptografického systému. Splňovali ji např. všichni finalisté soutěže AES.
Kritérium bitové nezávislosti
Kritérium nezávislosti bitu (BIC; kritérium nezávislé na bitu) je kritérium. Platí: Při změně (inverzi) jednoho vstupního bitu by se měly nezávisle na sobě změnit dva výstupní bity. To platí pro všechny bity.
Nebylo by např. splněno, kdyby se změnil pouze jeden výstupní bit, když se změní i druhý výstupní bit. Mohly by se změnit jen proto, že se změnil vstupní bit. V opačném případě by výstupní bity na sobě závisely.
Související stránky
- Zmatek a rozptyl
Otázky a odpovědi
Otázka: Co je to lavinový efekt?
Odpověď: Lavinový efekt (známý také jako "efekt laviny") je vlastnost blokových šifer a algoritmů kryptografických hašovacích funkcí, která říká, že malá změna klíče nebo otevřeného textu by měla způsobit silnou změnu šifrového textu.
Otázka: Kdo jako první použil termín "lavinový efekt"?
Odpověď: Termín lavinový efekt poprvé použil Horst Feistel v roce 1973.
Otázka: Jak souvisí se Shannonovou vlastností zmatení?
Odpověď: Pojem lavinový efekt byl ztotožněn se Shannonovou vlastností zmatenosti, která říká, že pokud bloková šifra nebo kryptografická hašovací funkce nesplňuje tento stupeň ve významné míře, pak má špatnou náhodnost a může být částečně nebo úplně prolomena (prolomena).
Otázka: Jaké jsou některé cíle návrhu při vytváření silných šifer?
Odpověď: Když lidé vytvářejí silné šifry, snaží se do nich zabudovat dobrý lavinový efekt s využitím matematických principů, jako je například motýlí efekt. Proto je většina blokových šifer součinovými šiframi a proto mají hašovací funkce velké datové bloky.
Otázka: Co se stane, když algoritmus nesplňuje lavinový efekt?
Odpověď: Pokud algoritmus nesplňuje lavinový efekt ve významné míře, pak má špatnou randomizaci a může být částečně nebo úplně prolomen (prolomen) kryptoanalytiky, kteří mohou provádět předpovědi o vstupu pouze na základě daného výstupu.
Otázka: Proč většina blokových šifer používá součinové šifry?
Odpověď: Většina blokových šifer používá součinové šifry, protože do nich pomáhají zabudovat dobré avalanční efekty pomocí matematických principů, jako je například motýlí efekt.
Otázka: Proč mají hašovací funkce velké datové bloky?
Odpověď: Hašovací funkce mají velké datové bloky, protože pomáhají vytvářet dobré avalanční efekty pomocí matematických principů, jako je například motýlí efekt.
