MADRYGA

MADRYGA (na počest autora WE Madryga) je blokový šifrovací algoritmus vytvořený V. E. Madrigou v roce 1984.

Vlastnosti

Tento algoritmus je navržen tak, aby usnadnil a zefektivnil implementaci šifrování v rámci softwaru. Algoritmus provádí všechny operace s byty.

Při návrhu algoritmu autor vyřešil následující problémy:

  1. Otevřený text nelze získat ze šifrovaného textu bez pomoci klíče (algoritmus je bezpečný);
  2. Počet operací potřebných k určení klíče z dostupného šifrového textu a otevřeného textu by se měl statisticky rovnat součinu počtu šifrovacích operací počtem možných klíčů;
  3. Nápadnost algoritmu neovlivňuje sílu šifry;
  4. Změna jednoho bitu klíče musí způsobit u stejného otevřeného textu radikální změnu šifrového textu a změna jednoho bitu otevřeného textu musí způsobit u stejného klíče radikální změnu šifrového textu;
  5. Algoritmus musí obsahovat nekomutativní kombinaci substitucí a permutací;
  6. Substituce a permutace použité v algoritmu musí být určeny jak vstupem, tak klíčem;
  7. Nadbytečné bitové skupiny otevřeného textu musí být v šifrovém textu zcela maskovány;
  8. Délka šifrovaného textu se musí rovnat délce otevřeného textu;
  9. Mezi možnými klíči a vlastnostmi šifrového textu by neměly existovat jednoduché vztahy;
  10. Všechny možné klíče musí poskytovat silnou šifru (nesmí existovat žádné slabé klíče);
  11. Délku klíče a textu lze upravit tak, aby splňovaly různé bezpečnostní požadavky;
  12. Algoritmus musí umožňovat efektivní implementaci softwaru na velkých sálových počítačích , minipočítačích , mikropočítačích a s diskrétní logikou.

Algoritmus DES splnil prvních devět požadavků, ale poslední tři se staly novými. Dávají tomuto algoritmu možnost softwarových implementací.

Popis algoritmu

Madryga se skládá ze dvou vnořených smyček. Vnější smyčka se opakuje osmkrát (ale toto číslo lze zvýšit pro zlepšení zabezpečení) a obsahuje aplikaci vnitřní smyčky na prostý text. Vnitřní smyčka změní otevřený text na šifrovaný text, který se opakuje pro každý 8bitový blok (bajt) otevřeného textu. Proto je celý otevřený text algoritmem zpracován osmkrát za sebou.

Iterace vnitřní smyčky funguje na 3bajtovém okně dat nazývaném pracovní rámec. Toto okno je posunuto o jeden bajt na iteraci. První dva bajty pracovního rámce jsou otočeny o proměnný počet pozic a poslední bajt je XORed s některými klíčovými bity. Jak pracovní rámec postupuje, všechny bajty jsou postupně "rotovány" a XORed s částmi klíče. Postupné rotace kombinují výsledky předchozích XOR a rotací a výsledek XOR ovlivní rotaci. Díky tomu je proces reverzibilní.

Vzhledem k tomu, že každý bajt dat ovlivňuje ano bajty nalevo a jeden bajt napravo, po osmi průchodech závisí každý bajt šifrovaného textu na 16 bajtech nalevo a osmi bytech napravo.

Při šifrování každá operace vnitřní smyčky nastaví operační rámec na předposlední textový bajt a převede jej na bajt prostého textu třetí vlevo od posledního. Celý klíč je nejprve XORed s náhodnou konstantou a poté otočen doleva o 3 bity. Spodní tři bity dolního bajtu pracovního rámce jsou zachovány a určují rotaci zbývajících dvou bajtů. Dolní bajt pracovního rámce je pak XORed s dolním bytem klíče. Dále se spojení dvou vysokých bajtů cyklicky posouvá doleva o proměnný počet bitů (od 0 do 7). Nakonec se pracovní rámec posune o jeden bajt doprava a celý proces se opakuje.

Význam náhodné konstanty je změnit klíč na pseudonáhodnou sekvenci. Délka konstanty se musí rovnat délce klíče. Při výměně dat musí účastníci používat konstanty stejné délky. Pro 64bitový klíč Madriga doporučuje konstantu 0x0f1e2d3c4b5a6978.

Při dešifrování je proces invertován. Při každé iteraci vnitřní smyčky je pracovní rámec nastaven na bajt třetí zleva od posledního bajtu šifrovaného textu a vrací se zpět k bajtu, který je dva bajty vlevo od posledního bajtu šifrovaného textu. Jak klíč, tak dva bajty šifrového textu se během procesu otočí doprava a před otočením se provede XOR.

Kryptoanalýza MADRYGA

Vědci z Queensland University of Technology zkoumali Madrygu spolu s některými dalšími blokovými šiframi. Zjistili, že v tomto algoritmu pro převod prostého textu na šifrovaný nebyl žádný zaplavovací efekt . Také v mnoha šifrových textech bylo procento jedniček vyšší než procento nul.

Po povrchním seznámení s algoritmem došel Eli Biham k následujícím závěrům:

  1. Algoritmus sestává pouze z lineárních operací (cyklický posun a XOR), mírně upravených v závislosti na datech
  2. To není nic jako síla DES S-boxů .
  3. Parita všech bitů šifrového textu a otevřeného textu se nemění a závisí pouze na klíči. Proto lze vzhledem k otevřenému textu a odpovídajícímu šifrovanému textu předpovědět paritu šifrového textu pro jakýkoli otevřený text.

Poznámky

Literatura

Odkazy