Файстелов шифър (Feistel) — симетрична мрежа за блокови шифри

Файстелов шифър — ясно обяснение на симетричната мрежа за блокови шифри: принципи, предимства, S/P-кутийки и приложения (DES и съвременни алгоритми).

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

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

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

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

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

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

Основна конструкция и математическо описание

Класическият Файстел-раунд работи като разделя входния блок на две половини: лява (L) и дясна (R). За индекс i (кръг i) се прилага функцията на кръга F с подклуч Ki. Типичното повторение е:

• L_i = R_{i-1}
• R_i = L_{i-1} XOR F(R_{i-1}, K_i)

След n кръга финалният шифротекст често се записва като комбинация от L_n и R_n. Поради присъствието на XOR и разместването на половините, операцията е обратима без необходимост F да бъде обратима сама по себе си — това е едно от ключовите предимства на Файстеловия дизайн.

Декриптиране и графика на ключовете

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

Вариации и практическа употреба

Има няколко вариации на Файстел-мрежата:

• Балансирана — лявата и дясната половина имат еднакъв размер (най-често срещано).
• Небалансирана — половините са с различен размер, използва се в някои специализирани конструкции.
• Частично обратими/обогатени схемы — добавяне на допълнителни операции преди или след стандартния Файстел-раунд (например допълнителни сумиране или S-кутии).

Примери за реални шифри, изградени върху Файстелови мрежи, са Data Encryption Standard, Blowfish, CAST, GOST и други. Някои модерни алгоритми комбинират идеи от Файстел и от други блокови шифри (например Substitution–Permutation Network), за да постигнат по-добри свойства по отношение на сигурността и производителността.

Теоретни резултати и сигурност

Съществуват важни теоретични резултати за Файстеловите мрежи. По-специално, теоремата на Luby–Rackoff показва, че ако кръговите функции са независими случайни функции, то след достатъчен брой кръгове се получава пермутация, която е трудноразличима от случаен пермутационен бутон (псевдослучайна пермутация). Конкретно:

• 3 кръга могат да дадат псевдослучайна пермутация (PRP) при подходящи условия;
• 4 кръга дават още по-силно свойство (силна PRP), устойчиво срещу по-широк клас атаки.

В практиката броят на кръговете и дизайнът на F (напр. използване на S-кутии, нелинейни трансформации и добра графика на ключовете) са критични за устойчивост срещу атаки като differential и linear cryptanalysis. Лошо проектираните S-кутии или предсказуем график на ключовете водят до слабости, независимо от самата Файстелова структура.

Имплементация и производителност

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

Практически съвети за дизайн

• Осигурете достатъчен брой кръгове — практиката и анализите диктуват повече кръгове за по-голяма сигурност.
• Проектирайте силни нелинейни компоненти (S-кутии) и добър механизъм за дифузия (P-кутии).
• Използвайте солидна графика на ключовете — слаба или линейна графика улеснява атаките.
• Проверете устойчивостта към известни типове криптоанализа (диференциален, линеен и др.) чрез анализ и публичен преглед.

Кратко обобщение

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

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

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

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

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

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

L i + 1 = R i {\displaystyle 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 n + 1 , L n + 1 ) {\displaystyle (R_{n+1},L_{n+1})} . (Обикновено двете части R n {\displaystyle R_{n}} и L n {\displaystyle L_{n}} не се разменят след последния рунд).

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

R i = L i + 1 {\displaystyle 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 1 , R 1 ) {\displaystyle (L_{1},R_{1})} отново е откритият текст.

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

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

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

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

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

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

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

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

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

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

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

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

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

Търсене по буква