Шифр фейстеля: Почему сеть Фейстеля работает? Объяснение «на пальцах» / Хабр

НОУ ИНТУИТ | Лекция | Алгоритмы симметричного шифрования. Часть 1

< Лекция 12 || Лекция 2: 1234

Аннотация: Рассматриваются основные понятия, относящиеся к алгоритмам симметричного шифрования, ключ шифрования, plaintext, ciphertext. Дается определение стойкости алгоритма. Рассматриваются типы операций, используемые в алгоритмах симметричного шифрования. Рассматривается сеть Фейстеля, которая лежит в основе многих современных алгоритмов симметричного шифрования. Даются основные понятия криптоанализа, рассмотрены линейный и дифференциальный криптоанализ. Представлено описание алгоритмов DES и тройного DES.

Ключевые слова: криптография, определенность алгоритма, plaintext, выход алгоритма, ciphertext, дешифрование, ключ шифрования, алгоритмы шифрования, диффузия, конфузия, стойкость алгоритма, криптографический ключ, алгоритм симметричного шифрования, длина блока, симметричное шифрование, S-box, XOR, раунд, подключ, шифрование данных, хэш-функция, микроконтроллер, смарт-карта, возможный ключ, алгоритм, подстановка, сеть Фейстеля, функция, операции, whitening, криптоанализ, атака, ключ, длина ключа, бит, статистические методы, представление, файл, дифференциальный криптоанализ, линейный криптоанализ, DES, линейное уравнение, микропроцессор, исключающее ИЛИ, условный переход, пространство, data encryption standard, NIST, technological, качество стандартов, FIPS, операции сдвига, инверсия, обратная функция, подстановка результатов, вход алгоритма, permute, choice, расшифрование, функция выходов, тройной DES, IDEA, Rijndael, длина

Криптография

Основные понятия

intuit.ru/2010/edi»>Рассмотрим общую схему симметричной, или традиционной, криптографии.

Рис. 2.1.

Общая схема симметричного шифрования

В процессе шифрования используется определенный алгоритм шифрования, на вход которому подаются исходное незашифрованное сообщение, называемое также plaintext, и ключ. Выходом алгоритма является зашифрованное сообщение, называемое также ciphertext . Ключ является значением, не зависящим от шифруемого сообщения. Изменение ключа должно приводить к изменению зашифрованного сообщения.

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

intuit.ru/2010/edi»>Незашифрованное сообщение будем обозначать P или M, от слов plaintext и message. Зашифрованное сообщение будем обозначать С, от слова ciphertext.

Безопасность, обеспечиваемая традиционной криптографией, зависит от нескольких факторов.

Во-первых, криптографический алгоритм должен быть достаточно сильным, чтобы передаваемое зашифрованное сообщение невозможно было расшифровать без ключа, используя только различные статистические закономерности зашифрованного сообщения или какие-либо другие способы его анализа.

Во-вторых, безопасность передаваемого сообщения должна зависеть от секретности ключа, но не от секретности алгоритма. Алгоритм должен быть проанализирован специалистами, чтобы исключить наличие слабых мест, при наличии которых плохо скрыта взаимосвязь между незашифрованным и зашифрованным сообщениями. К тому же при выполнении этого условия производители могут создавать дешевые аппаратные чипы и свободно распространяемые программы, реализующие данный алгоритм шифрования.

В-третьих, алгоритм должен быть таким, чтобы нельзя было узнать ключ, даже зная достаточно много пар (зашифрованное сообщение, незашифрованное сообщение), полученных при шифровании с использованием данного ключа.

Клод Шеннон ввел понятия диффузии и конфузии для описания стойкости алгоритма шифрования.

Диффузия — это рассеяние статистических особенностей незашифрованного текста в широком диапазоне статистических особенностей зашифрованного текста. Это достигается тем, что значение каждого элемента незашифрованного текста влияет на значения многих элементов зашифрованного текста или, что то же самое, любой элемент зашифрованного текста зависит от многих элементов незашифрованного текста.

Конфузия — это уничтожение статистической взаимосвязи между зашифрованным текстом и ключом.

intuit.ru/2010/edi»>Если Х — это исходное сообщение и K — криптографический ключ, то зашифрованный передаваемый текст можно записать в виде

Y = EK[X].

Получатель, используя тот же ключ, расшифровывает сообщение

X = DK[Y]

Противник, не имея доступа к K и Х, должен попытаться узнать Х, K или и то, и другое.

Алгоритмы симметричного шифрования различаются способом, которым обрабатывается исходный текст. Возможно шифрование блоками или шифрование потоком.

Блок текста рассматривается как неотрицательное целое число, либо как несколько независимых неотрицательных целых чисел. Длина блока всегда выбирается равной степени двойки. В большинстве блочных алгоритмов симметричного шифрования используются следующие типы операций:

• ru/2010/edi»> Табличная подстановка, при которой группа бит отображается в другую группу бит. Это так называемые S-box .
• Перемещение, с помощью которого биты сообщения переупорядочиваются.
• Операция сложения по модулю 2, обозначаемая XOR или
• Операция сложения по модулю 2³² или по модулю 2¹⁶.
• Циклический сдвиг на некоторое число бит.

Эти операции циклически повторяются в алгоритме, образуя так называемые раунды. Входом каждого раунда является выход предыдущего раунда и ключ, который получен по определенному алгоритму из ключа шифрования K. Ключ раунда называется подключом . Каждый алгоритм шифрования может быть представлен следующим образом:

Рис. 2. 2. Структура алгоритма симметричного шифрования

Области применения

Стандартный алгоритм шифрования должен быть применим во многих приложениях:

• Шифрование данных. Алгоритм должен быть эффективен при шифровании файлов данных или большого потока данных.
• Создание случайных чисел. Алгоритм должен быть эффективен при создании определенного количества случайных бит.
• Хэширование. Алгоритм должен эффективно преобразовываться в одностороннюю хэш-функцию.

Платформы

Стандартный алгоритм шифрования должен быть реализован на различных платформах, которые, соответственно, предъявляют различные требования.

• Алгоритм должен эффективно реализовываться на специализированной аппаратуре, предназначенной для выполнения шифрования/дешифрования.
• Большие процессоры. Хотя для наиболее быстрых приложений всегда используется специальная аппаратура, программные реализации применяются чаще. Алгоритм должен допускать эффективную программную реализацию на 32-битных процессорах.
• Процессоры среднего размера. Алгоритм должен работать на микроконтроллерах и других процессорах среднего размера.
• Малые процессоры. Должна существовать возможность реализации алгоритма на смарт-картах, пусть даже с учетом жестких ограничений на используемую память.

Дополнительные требования

Алгоритм шифрования должен, по возможности, удовлетворять некоторым дополнительным требованиям.

• Алгоритм должен быть простым для написания кода, чтобы минимизировать вероятность программных ошибок.
• intuit.ru/2010/edi»>Алгоритм должен иметь плоское пространство ключей и допускать любую случайную строку бит нужной длины в качестве возможного ключа. Наличие слабых ключей нежелательно.
• Алгоритм должен легко модифицироваться для различных уровней безопасности и удовлетворять как минимальным, так и максимальным требованиям.
• Все операции с данными должны осуществляться над блоками, кратными байту или 32-битному слову.

Дальше >>

< Лекция 12 || Лекция 2: 1234

Сеть (конструкция) Фейстеля кратко Шифры в криптографии

Привет, Вы узнаете про сеть фейстеля, Разберем основные ее виды и особенности использования. Еще будет много подробных примеров и описаний. Для того чтобы лучше понимать что такое сеть фейстеля, конструкция фейстеля , настоятельно рекомендую прочитать все из категории Шифры в криптографии.

сеть фейстеля ( конструкция фейстеля ) — разновидность блочного шифра с определенной итеративной структурой. Многие современные алгоритмов используют сеть Фейстеля как основу.

В 1973 году Хорст Фейстель ( англ. Horst Feistel ) в журнале Scientific American опубликовал статью «Криптография и компьютерная безопасность» ( «Cryptography and Computer Privacy»), в которой раскрыл некоторые важные аспекты шифрования, а также ввел конструкцию, названную позже сетью Фейстеля. Эта схема была использована в проекте Lucifer фирмы IBM , над которым работал Фейстель и Дон Коперсмит (Don Coppersmith). Этот проект был скорее экспериментальным, но стал базисом для DES . Итеративная структура алгоритма позволяла упростить его реализацию в аппаратном среде.

Конструкция

шифрование

расшифровка

• блок открытого текста делится на 2 равные части (
• в каждом раунде рассчитывается ( — номер раунда)

,

где — некоторая функция, а — ключ -го раунда . Об этом говорит сайт https://intellect.icu . результатом выполнения раундов является . Но обычно вм раунде перестановка и не выполняются, что позволяет использовать ту же процедуру и для расшифровки, просто инвертувавшы порядок использования раундовой ключевой информации:

,

Небольшие изменения позволяют достичь полной идентичности процедур шифрования и расшифровки. Одной из преимуществ такой модели является применимость алгоритма независимо от функции , И она может быть любой сложности.

Шифрование

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

Алгоритм шифрования.

• Информация разбивается на блоки одинаковой (фиксированной) длины. Полученные блоки называются входными, так как поступают на вход алгоритма. В случае, если длина входного блока меньше, чем размер, который выбранный алгоритм шифрования способен зашифровать единовременно (размер блока), то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например, составляет 64 бита или 128 бит.

Расшифрование

Расшифровка информации происходит так же, как и шифрование, с тем лишь исключением, что ключи следуют в обратном порядке, то есть не от первого к N-му, а от N-го к первому.

Пример реализации на языке Си

Модификации сети Фейстеля

При большом размере блоков шифрования (128 бит и более) реализация такой сети Фейстеля на 32-разрядных архитектурах может вызвать сложности, поэтому используются модифицированные варианты этой конструкции. В обычных ситуациях используются сети с 4 ветвями. На рисунке показано наиболее распространенные модификации. Также существуют схемы, в которых длины половинок и не совпадают. Они называются несбалансированными .

Модификации сети Фейстеля

тип 1

тип 2

тип 3

Особенности сети Фейстеля

• в каждом проходе — по одному слою (преобразования однотипны)
• на какую-либо часть шифруемого блока обратимая (необратимая) операция накладывает значение, вычисленное от другой части
• Сеть является обратимой (для дешифрации не нужно вычислять обратную функцию)
• Для дешифрации используется тот же алгоритм, на вход подается тот же текст, ключи используются в обратном порядке
• Входной блок делится на несколько одинаковых подблоков — ветвей

Шифры на основе сети (конструкции) Фейстеля

Такие шифры используют классическую или модифицированную сеть Фейстеля в своей основе:

• Blowfish
• Camellia
• CAST
• DES
• FEAL
• ГОСТ 28147-89
• KASUMI
• LOKI97
• Lucifer
• MacGuffin
• MARS
• MAGENTA
• MISTY1
• RC2
• RC5
• RC6
• Skipjack
• TEA
• Triple DES
• Twofish
• XTEA

См.

также

• Криптография
• Потоковый шифр
• Сеть подстановки- перестановки
• Схема подъема для дискретного вейвлет -преобразования имеет примерно такую ​​же структуру
• Шифрование с сохранением формата
• Схема Лая – Мэсси

В общем, мой друг ты одолел чтение этой статьи об сеть фейстеля. Работы в переди у тебя будет много. Смело пишикоментарии, развивайся и счастье окажется в ваших руках. Надеюсь, что теперь ты понял что такое сеть фейстеля, конструкция фейстеля и для чего все это нужно, а если не понял, или есть замечания, то нестесняся пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Шифры в криптографии

Из статьи мы узнали кратко, но емко про сеть фейстеля

Feistel Cipher — GeeksforGeeks

Улучшить статью

Сохранить статью

• Уровень сложности: Средний
• Последнее обновление: 24 фев, 2022

Читать

Обсудить

Улучшить статью

Сохранить статью

Модель шифра Фейстеля — это структура или схема, используемая для разработки многих блочных шифров, таких как DES. Шифр Фейстеля может иметь в своей конструкции обратимые, необратимые и самообратимые компоненты. Используется тот же алгоритм шифрования, что и алгоритм дешифрования. Для каждого раунда используется отдельный ключ. Однако для шифрования и дешифрования используются одни и те же раундовые ключи.
 

Алгоритм шифрования Фейстеля

• Создайте список всех символов обычного текста.
   
• Преобразование обычного текста в формат ASCII, а затем в 8-битный двоичный формат.
   
• Разделить двоичную строку обычного текста на две половины: левую половину (L1) и правую половину (R1)
   
• Генерировать случайные двоичные ключи (K1 и K2) длиной, равной половине длины обычного текста для два раунда.
   

Первый этап шифрования 

• а. Сгенерируйте функцию f1, используя R1 и K1 следующим образом:

 f1= xor(R1, K1) 

• b. Теперь новые левая половина (L2) и правая половина (R2) после раунда 1 выглядят следующим образом:

 R2= xor(f1, L1)
L2=R1 

Второй раунд шифрования

• а. Сгенерируйте функцию f2, используя R2 и K2, следующим образом:
  

 f2= xor(R2, K2) 

• b. Теперь новые левая половина (L3) и правая половина (R3) после раунда 2 выглядят следующим образом:

 R3= xor(f2, L2)
L3=R2 

• Конкатенация R3 и L3 является зашифрованным текстом
• Тот же алгоритм используется для дешифрования для извлечения обычного текста из зашифрованного текста.

Примеры:  

 Обычный текст: Hello
Шифрованный текст: E1!w(
Полученный обычный текст: b'Hello'
Обычный текст: Компьютерщики
Шифрованный текст: O;Q
Полученный обычный текст: b'Geeks' 

 

Python3

import binascii   def rand_key(p):             import random      key1 = "" P = Int (P) для I В для I . 0102 range (p):                     temp = random.randint( 0 , 1 )          temp = STR (TEMP) KEY1 = KEY1 + TEMP 03      return (key1)     def exor(a,b):             temp = "" для I в . 0102 (a[i] = = b[i]):              temp + = "0"                         else : Temp + = "1" 1101 9 9 0102   def BinaryToDecimal(binary):                         string = int (binary, 2 ) возврат Строка PT = Hello » PT = Hello» . 0102 print ( "Plain Text is:" , PT)   PT_Ascii = [ ord (x) for x in PT]   PT_Bin = [ format (y, '08b' ) for y in PT_Ascii] PT_BIN = ". ) L1 = PT_Bin[ 0 :n] R1 = PT_Bin[n::] m = len (R1)     K1 = rand_key(m)     K2 = rand_key(m)     f1 = exor(R1,K1) R2 = exor(f1,L1) L2 = R1     f2 = exor(R2,K2) R3 = exor(f2,L2) L3 = R2     bin_data = L3 + R3 str_data = ' '   for i in range ( 0 , len (bin_data), 7 ):                         temp_data = bin_data[i:i + 7 ] DECIMAL_DATA DECIMAL_DATA DECIMAL_DATA DECIMAL_DATA . 0101 = BinaryToDecimal(temp_data)                                         str_data = str_data + chr (decimal_data)        print ( "Зашифрованный текст:" , str_data)   L4 = L3 R4 = R3     f3 = exor(L4,K2) L5 = exor(R4,f3) R5 = L4     f4 = exor(L5,K1) L6 = exor(R5,f4) R6 = L5 PT1 = L6 + R6     PT1 = INT (PT1, 2 ) RPT = 11010101 RPT = 1. Хуль 110100.0102 Печать ( «Получено простое текст:« , RPT)

Выход:

. Простой текст: Hell: Hellp: Hellp: Hell: Hellp: Hellp: Hell: Hell: Hell: Hell: Hell: Hell: Hell: Hell: Hello.
Шифрованный текст: E1!w(
Полученный обычный текст: b'Hello' 

Статьи по теме

Что нового

Мы используем файлы cookie, чтобы обеспечить вам максимальное удобство при просмотре нашего веб-сайта. Используя наш сайт, вы подтверждаете, что вы прочитали и поняли наши Политика в отношении файлов cookie & Политика конфиденциальности

Что такое шифр Фейстеля?

Быстрые ответы: 

• Шифр ​​Фейстеля — это проектная модель, предназначенная для создания различных блочных шифров, таких как DES.
• Модель попеременно использует подстановку и перестановку.
• Эта структура шифра основана на модели Шеннона, предложенной в 1945 году.   

Что такое шифр Фейстеля?

Шифр ​​Фейстеля — это проектная модель или структура, используемая для создания различных симметричных блочных шифров, таких как DES. Эта проектная модель может иметь обратимые, необратимые и самообратимые компоненты. Кроме того, блочный шифр Фейстеля использует те же алгоритмы шифрования и дешифрования.

Структура Фейстеля основана на структуре Шеннона, предложенной в 1945 году и демонстрирующей процессы реализации путаницы и диффузии. Путаница создает сложную связь между зашифрованным текстом и ключом шифрования, что достигается с помощью алгоритма подстановки. С другой стороны, распространение создает сложную связь между обычным текстом и зашифрованным текстом с использованием алгоритма перестановки.

Шифр ​​Фейстеля предложил структуру, которая попеременно реализует замену и перестановку. Подстановка заменяет элементы обычного текста зашифрованным текстом. Перестановка изменяет порядок элементов обычного текста, а не заменяет их другим элементом, как это делается при подстановке.

Пример шифрования с помощью шифра Фейстеля 

Процесс шифрования с помощью шифра Фейстеля включает многочисленные этапы обработки обычного текста. Каждый раунд включает в себя этап замены, а затем этап перестановки. Ознакомьтесь со следующим примером, описывающим структуру шифрования, используемую для этой модели проектирования.

• Шаг 1 – На первом этапе обычный текст делится на блоки фиксированного размера, при этом одновременно обрабатывается только один блок. Вход алгоритма шифрования состоит из простого текстового блока и ключа K. 
• Шаг 2 – Блок обычного текста делится на две половины. Левая половина блока обычного текста будет представлена ​​как LE0, а правая половина блока будет RE0. Обе половины блока открытого текста (LE0 и RE0) будут проходить многочисленные этапы обработки открытого текста для создания блока зашифрованного текста.

Для каждого раунда функция шифрования применяется к правой половине REi блока открытого текста плюс ключ Ki. Затем результаты функции подвергаются операции XOR с левой половиной LEj. XOR — это логический оператор, используемый в криптографии, который сравнивает два входных бита и выдает один выходной бит. Результаты функции XOR становятся новой правой половиной для следующего раунда RE i+1. Предыдущая правая половина REi становится новой левой половиной LEi+1 для следующего раунда.

Каждый раунд будет выполнять одну и ту же функцию, в которой функция подстановки реализована с использованием функции раунда в правой половине блока открытого текста. Результат этой функции подвергается операции XOR с использованием левой половины блока. Затем используется функция перестановки путем переключения двух половин. Результаты перестановки предоставляются для следующего раунда. Действительно, именно так модель шифра Фейстеля поочередно реализует этапы замены и перестановки, подобно упомянутой выше структуре Шеннона.

 

Особенности конструкции шифра Фейстеля, учитываемые при использовании блочного шифра:

 

• Размер блока — Блочные шифры считаются более надежными, когда размер блока больше. Однако большие размеры блоков снижают скорость выполнения процесса шифрования и дешифрования. Обычно блочные шифры имеют размер блока 64 бита, но современные блоки, такие как AES (Advanced Encryption Standard), имеют размер блока 128 бит.
• Легкий анализ – Блочные шифры должны легко поддаваться анализу, что может помочь выявить и устранить любые криптоаналитические недостатки для создания более надежных алгоритмов.
• Размер ключа — Как и размер блока, ключ большего размера считается более безопасным за счет потенциального замедления времени, необходимого для завершения процесса шифрования и дешифрования. Современные шифры используют 128-битный ключ, который заменил более раннюю 64-битную версию.
• Количество раундов — Количество раундов также может влиять на безопасность блочного шифра. Хотя большее количество раундов повышает безопасность, шифр сложнее расшифровать. Таким образом, количество раундов зависит от желаемого бизнесом уровня защиты данных.
• Функция округления — Сложная функция округления помогает повысить безопасность блочного шифра.
• Функция генерации подключа — Чем сложнее функция генерации подключа, тем труднее для опытных криптоаналитиков расшифровать шифр.
• Быстрое программное шифрование и дешифрование — Полезно использовать программное приложение, которое может повысить скорость выполнения блочных шифров.

Пример расшифровки шифра Фейстеля

Может показаться удивительным, что модель шифра Фейстеля использует один и тот же алгоритм для шифрования и дешифрования. В процессе расшифровки необходимо учитывать несколько ключевых правил:  

Как показано на рисунке выше, блок зашифрованного текста состоит из двух половин: левой (LD0) и правой (RD0).

Как и алгоритм шифрования, функция раунда выполняется на правой половине блока шифра с ключом K16. Результат функции подвергается операции XOR с левой половиной блока зашифрованного текста. Выход функции XOR становится новой правой половиной (RD1), а RD0 переключается с LD0 для следующего раунда. Действительно, каждый раунд использует одну и ту же функцию, и после выполнения фиксированного количества раундов получается блок простого текста.

Заключительные пункты 

Шифр ​​Фейстеля — это хорошо известная модель криптографии, которую организации могут использовать для защиты своих конфиденциальных данных. Даже если хакер знает алгоритм шифрования, надежный шифр должен помешать преступнику расшифровать открытый текст шифра, не имея ключа или наборов ключей. В дополнение к этой модели шифрования компаниям следует принять многоуровневую стратегию кибербезопасности, чтобы предотвратить кражу или раскрытие конфиденциальной информации злоумышленниками. Токенизация — это эффективное решение, заменяющее исходные данные уникальными, случайно сгенерированными числами, называемыми токенами. Токенизированные данные можно хранить и управлять ими через безопасную облачную платформу.