Шифърът на Файстел

В криптографията шифърът на Файстел е симетрична структура, използвана при конструирането на блокови шифри, наречена на името на немския криптограф на IBM Хорст Файстел; тя е известна и като мрежа на Файстел. Голям набор от блокови шифри използват тази схема, включително Data Encryption Standard

Предимството на структурата на Файстел е, че операциите по криптиране и декриптиране са много сходни, дори идентични в някои случаи, като се изисква само обръщане на графика на ключовете. Поради това размерът на кода или схемата, необходима за реализиране на такъв шифър, се намалява почти наполовина.

Конструкцията на Файстел е итеративна по своята същност, което улеснява внедряването на криптосистемата в хардуера.

Мрежите на Файстел и други подобни конструкции са продуктови шифри и съчетават множество кръгове от повтарящи се операции, като например:

Разбъркване на битове (често наричани кутии за пермутация или P-кутии)
Прости нелинейни функции (често наричани кутии за заместване или S-кутии)
Линейно смесване (в смисъла на модулната алгебра) с помощта на XOR за създаване на функция с големи количества от това, което Клод Шанън описва като "объркване и дифузия".

Разбъркването на битове създава ефекта на дифузия, а заместването се използва за объркване.

Теоретична работа

Много съвременни симетрични блокови шифри използват мрежи на Файстел, а структурата и свойствата на шифрите на Файстел са широко изследвани от криптографите. По-конкретно, Майкъл Луби и Чарлз Ракоф анализират конструкцията на блоковия шифър на Фейстел и доказват, че ако функцията на кръга е криптографски сигурна псевдослучайна функция, като за семето се използва К, _iто 3 кръга са достатъчни, за да се превърне блоковият шифър в псевдослучайна пермутация, а 4 кръга са достатъчни, за да се превърне в "силна" псевдослучайна пермутация (което означава, че остава псевдослучайна дори за противник, който получава достъп до обратната пермутация). Заради този много важен резултат на Люби и Ракоф шифрите на Фейстел понякога се наричат блокови шифри на Люби-Ракоф. По-нататъшни теоретични изследвания обобщават конструкцията и определят по-точни граници на сигурността.

Строителство

Нека F {\displaystyle {\rm {F}}} ${\rm F}$ е функцията на рунда и нека K 1 , K 2 , ... , K n {\displaystyle K_{1},K_{2},\ldots ,K_{n}} $K_1,K_2,\ldots,K_{n}$ са подключовете $1,2,\ldots,n$ съответно за рундовете 1 , 2 , ... , n {\displaystyle 1,2,\ldots ,n}.

Тогава основната операция е следната:

Разделяне на блока с открит текст на две равни части: ( L 1 {\displaystyle L_{1}} L_1 , R 1 {\displaystyle R_{1}} R_1 )

За всеки кръг i = 1 , 2 , ... , n {\displaystyle i=1,2,\dots ,n} $i =1,2,\dots,n$ , изчисляване (calculate)

L i + 1 = R i {\displaystyle L_{i+1}=R_{i}\,} $L_{i+1} = R_i\,$

R i + 1 = L i ⊕ F ( R i , K i ) {\displaystyle R_{i+1}=L_{i}\oplus {\rm {F}}(R_{i},K_{i})} $R_{i+1}= L_i \oplus {\rm F}(R_i, K_i)$ .

Тогава шифърният текст е ( R n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} $(R_{n+1}, L_{n+1})$ . (Обикновено двете части R n {\displaystyle R_{n}} R_n и L n {\displaystyle L_{n}} L_n не се разменят след последния рунд).

Декриптирането на шифротекст ( R n , L n ) {\displaystyle (R_{n},L_{n})} (R_n, L_n) се извършва чрез изчисляване за i = n , n - 1 , ... , 1 {\displaystyle i=n,n-1,\ldots ,1} $i=n,n-1,\ldots,1$

R i = L i + 1 {\displaystyle R_{i}=L_{i+1}\,} $R_{i} = L_{i+1}\,$

L i = R i + 1 ⊕ F ( L i + 1 , K i ) {\displaystyle L_{i}=R_{i+1}\oplus {\rm {F}}(L_{i+1},K_{i})} $L_{i} = R_{i+1} \oplus {\rm F}(L_{i+1}, K_{i})$ .

Тогава ( L 1 , R 1 ) {\displaystyle (L_{1},R_{1})} отново (L_1,R_1) е откритият текст.

Едно от предимствата на този модел е, че кръглата функция F {\displaystyle {\rm {F}}} ${\rm F}$ не е задължително да бъде инвертируема и може да бъде много сложна.

Диаграмата илюстрира процеса на криптиране. Декриптирането изисква само обръщане на реда на подключовете K n , K n - 1 , ... , K 1 {\displaystyle K_{n},K_{n-1},\ldots ,K_{1}} $K_{n},K_{n-1},\ldots,K_1$ , като се използва същият процес; това е единствената разлика между криптирането и декриптирането:

Небалансираните шифри на Фейстел използват модифицирана структура, при която L 1 {\displaystyle L_{1}} L_1 и R 1 {\displaystyle R_{1}} R_1 не са с еднаква дължина. Шифърът MacGuffin е експериментален пример за такъв шифър.

Конструкцията на Фейстел се използва и в криптографски алгоритми, различни от блоковите шифри. Например схемата Optimal Asymmetric Encryption Padding (OAEP) използва проста мрежа на Файстел за рандомизиране на шифровите текстове в някои схеми за криптиране с асиметричен ключ.

Мрежова операция на Фейстел върху блоков шифър, където P е откритият текст, а C е шифърът

Списък на шифрите на Файстел

Feistel или модифициран Feistel: Blowfish, Camellia, CAST-128, DES, FEAL, ICE, KASUMI, LOKI97, Lucifer, MARS, MAGENTA, MISTY1, RC5, TEA, Triple DES, Twofish, XTEA, GOST 28147-89

Обобщен Feistel: CAST-256, MacGuffin, RC2, RC6, Skipjack

Въпроси и отговори

В: Какво представлява шифърът на Файстел?

О: Шифърът на Файстел е симетрична структура, използвана при изграждането на блокови шифри, наречена на името на немския криптограф на IBM Хорст Файстел. Шифърът е известен и като мрежа на Файстел.

В: Какви са някои предимства на използването на структурата на Файстел?

О: Основното предимство на използването на структурата на Файстел е, че операциите по криптиране и декриптиране са много сходни, дори идентични в някои случаи, като се изисква само обръщане на графика на ключовете. Това намалява почти наполовина размера на кода или схемата, необходима за реализирането на такъв шифър. Освен това итеративният му характер улеснява прилагането на криптосистемата в хардуер.

Въпрос: Как Клод Шанън описва "объркването и разпространението"?

О: Клод Шанън описва "объркването и дифузията" като наличие на голямо количество от двата елемента, за да се затрудни дешифрирането на криптирано съобщение от нападателя.

В: Какви техники се използват за създаване на объркване и разсейване?

О: Объркването и дифузията се създават чрез разбъркване на битове (често наричани кутии за пермутация или P-кутии) и прости нелинейни функции (често наричани кутии за заместване или S-кутии), както и чрез линейно смесване (в смисъла на модулната алгебра) с помощта на XOR. Разбъркването на битове създава ефекта на дифузия, докато заместването се използва за объркване.

Въпрос: Какъв тип шифър е мрежата на Файстел?

О: Мрежата на Файстел е вид продуктов шифър, който комбинира няколко кръга от повтарящи се операции с цел сигурно криптиране на данни.

В: Кой е разработил този вид криптография?

О: Структурата на Файстел е разработена от немския криптограф на IBM Хорст Файстел.

В: Стандартът за криптиране на данни основава ли се на този тип криптография?

О: Да, Data Encryption Standard използва този тип криптография, която използва същите принципи, описани по-горе, за създаване на объркване и разсейване в криптираното съобщение.