Feistelova šifra

Byla vytvořena německým kryptografem Horstem Feistelem v rámci laboratoří IBM v roce 1973. První kryptosystém, který ji využíval se nazýval Lucifer.

Jedná se o základní blokovou symetrickou šifru. Řada pozdějších kryptosystémů (jako DES, AES a jiné) je postavena právě na principu této šifry. Její základní princip spočívá v rozdělení otevřeného textu (vstupu šifrování) na dvě poloviny (z toho již vyplývá i požadavek, aby vstup měl sudý počet bitů). Zbytek šifry probíhá v tzv. rundách, runda představuje jeden krok šifry.

Šifrování a dešifrování

Feistelova šifra při svém šifrování pracuje tak, jak je demonstrováno na následujícím schématu:

Nejdříve se vstup rozdělí na dvě poloviny. Následně se z první poloviny vypočítá XOR výstupu ze šifrovací funkce f, která má jako vstup druhou polovinu otevřeného textu a klíč příslušný dané rundě. Jednotlivé rundy mohou mít odlišný klíč. Zbytek algoritmu je zřejmý, dochází k periodickému opakování levé a pravé strany až do konce. Na funkci f není kladen žádný speciální požadavek (především NEMUSÍ být invertovatelná, tj. mít inverzní funkci). Na konci se poloviny výstupu opět spojí a vzniká zašifrovaný blok.

Dešifrování

Probíhá přesně stejně jako šifrování s tím rozdílem, že se začíná odspodu.

Kryptoanalýza

Její úspěch závisí pouze na velikosti vstupu (při nízkých hodnotách možno použít frekvenční analýzu) a vlastnostech funkce f, případně použitém klíči.

Úlohy k programování

Mějme otevřený text jako 64 bitový integer, a dále klíč taktéž 64 bitový integer. Napište šifru Feistel šifrující tak, že bude mít 16 rund, jako klíč každé rundy bude výchozí klíč odrotovaný doleva o počet bitů rovný trojnásobku pořadí aktuální rundy.