Сеть Файстеля. Значение для криптографии. Вариации. Свойства.

Билет №1

Сеть Файстеля. Значение для криптографии. Вариации. Свойства.

Сеть Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.

Простое описание

Шифрование

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

• Вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например: 64 бита, 128 бит. Далее будем рассматривать операции происходящие только с одним блоком, так как с другими в процессе шифрования выполняются те же самые операции.
• Выбранный блок делится на два равных подблока — «левый» () и «правый» ().
• «Левый подблок» видоизменяется функцией в зависимости от раундового ключа , после чего он складывается по модулю 2 с «правым подблоком» .
• Результат сложения присваивается новому левому подблоку , который будет половиной входных данных для следующего раунда, а «левый подблок» присваивается без изменений новому правому подблоку (см. схему), который будет другой половиной.
• После чего операция повторяется N-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи ( на и т. д.) по какому-либо математическому правилу, где N — количество раундов в заданном алгоритме.

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

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

Алгоритмическое описание

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

,

где — некоторая функция, а — ключ -го раунда.

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

,

Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.

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

Математическое описание

Инволюция^[4] — взаимно-однозначное преобразование, которое является обратным самому себе. Рассмотрим на примере: Пусть X — входной блок, а A — некоторое инволютивное преобразование, Y — результат. При однократном применении преобразования к входному блоку получится: , при применении преобразования к результату предыдущего преобразования получится: .

Пусть входной блок X=(L, R) состоит из двух подблоков (L и R) равной длины. Определим два преобразования (шифрование ключом K) и (перестановка подблоков). Введём обозначения:

Докажем их инволютивность:

1. Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным. Поэтому далее будем рассматривать только подблок L. После того как преобразование G будет дважды применено к L получим: . Таким образом , следовательно G — инволюция.
2. .

Рассмотрим сам процесс шифрования. Определим X как входное значение. Пусть — преобразование с ключом , а — выходное значение после i-го раунда. Тогда преобразование на i+1-м раунде можно записать в виде , кроме первого, где . Следовательно, выходное значение после m раундов шифрования будет . Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.

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

. Достоинства и недостатки

Достоинства:

• Простота аппаратной реализации на современной электронной базе
• Простота программной реализации в силу того, что значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, сложение по модулю 2, сложение по модулю , умножение по модулю , и т. д.)
• Хорошая изученность алгоритмов на основе сетей Фейстеля^[5]

Недостатки:

• За один раунд шифруется только половина входного блока^[6]

Описание алгоритма

Предположим, существует два абонента: Алиса и Боб. Обоим абонентам известны некоторые два числа g и p, которые не являются секретными и могут быть известны также другим заинтересованным лицам. Для того, чтобы создать неизвестный более никому секретный ключ, оба абонента генерируют большие случайные числа: Алиса — число a, Боб— число b. Затем Алиса вычисляет значение^[5] (1):

(1)

и пересылает его Бобу, а Боб вычисляет (2):

(2)

Пример

Ева — криптоаналитик. Она читает пересылку Боба и Алисы, но не изменяет содержимого их сообщений^[7].

• s = секретный ключ. s = 2
• g = открытое простое число. g = 5
• p = открытое простое число. p = 23
• a = секретный ключ Алисы. a = 6
• A = открытый ключ Алисы. A = g^a mod p = 8
• b = секретный ключ Боба. b = 15
• B = открытый ключ Боба. B = g^b mod p = 19

Алгоритм Диффи-Хеллмана так же может быть использован при шифровании с открытым ключом. В этом случае общая схема остаётся аналогичной приведённой выше, но с небольшими отличиями. Алиса не передаёт значения p, g и A Бобу напрямую, а публикует их заранее в качестве своего открытого ключа. Боб выполняет свою часть вычислений, после чего шифрует сообщение симметричным алгоритмом, используя K в качестве ключа, и передает шифротекст Алисе вместе со значением B.

На практике, алгоритм Диффи-Хеллмана не используется таким образом. В данной области доминирующим алгоритм с открытым ключом является RSA. Это больше обусловлено в силу коммерческих выгод, так как именно RSA был создан центр сертификации. К тому же алгоритм Диффи-Хеллмана не может быть использован при подписании сертификатов^[6].

Билет №1

Сеть Файстеля. Значение для криптографии. Вариации. Свойства.

Сеть Фе́йстеля (конструкция Фейстеля) — один из методов построения блочных шифров. Сеть представляет собой определённую многократно повторяющуюся (итерированную) структуру, называющуюся ячейкой Фейстеля. При переходе от одной ячейки к другой меняется ключ, причём выбор ключа зависит от конкретного алгоритма. Операции шифрования и расшифрования на каждом этапе очень просты, и при определённой доработке совпадают, требуя только обратного порядка используемых ключей. Шифрование при помощи данной конструкции легко реализуется как на программном уровне, так и на аппаратном, что обеспечивает широкие возможности применения. Большинство современных блочных шифров используют сеть Фейстеля в качестве основы. Альтернативой сети Фейстеля является подстановочно-перестановочная сеть.

Простое описание

Шифрование

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

• Вся информация разбивается на блоки фиксированной длины. В случае, если длина входного блока меньше, чем размер, который шифруется заданным алгоритмом, то блок удлиняется каким-либо способом. Как правило длина блока является степенью двойки, например: 64 бита, 128 бит. Далее будем рассматривать операции происходящие только с одним блоком, так как с другими в процессе шифрования выполняются те же самые операции.
• Выбранный блок делится на два равных подблока — «левый» () и «правый» ().
• «Левый подблок» видоизменяется функцией в зависимости от раундового ключа , после чего он складывается по модулю 2 с «правым подблоком» .
• Результат сложения присваивается новому левому подблоку , который будет половиной входных данных для следующего раунда, а «левый подблок» присваивается без изменений новому правому подблоку (см. схему), который будет другой половиной.
• После чего операция повторяется N-1 раз, при этом при переходе от одного этапа к другому меняются раундовые ключи ( на и т. д.) по какому-либо математическому правилу, где N — количество раундов в заданном алгоритме.

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

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

Алгоритмическое описание

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

,

где — некоторая функция, а — ключ -го раунда.

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

,

Небольшим изменением можно добиться и полной идентичности процедур шифрования и расшифрования.

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

Математическое описание

Инволюция^[4] — взаимно-однозначное преобразование, которое является обратным самому себе. Рассмотрим на примере: Пусть X — входной блок, а A — некоторое инволютивное преобразование, Y — результат. При однократном применении преобразования к входному блоку получится: , при применении преобразования к результату предыдущего преобразования получится: .

Пусть входной блок X=(L, R) состоит из двух подблоков (L и R) равной длины. Определим два преобразования (шифрование ключом K) и (перестановка подблоков). Введём обозначения:

Докажем их инволютивность:

1. Несложно заметить, что преобразование G меняет только левый подблок L, оставляя правый R неизменным. Поэтому далее будем рассматривать только подблок L. После того как преобразование G будет дважды применено к L получим: . Таким образом , следовательно G — инволюция.
2. .

Рассмотрим сам процесс шифрования. Определим X как входное значение. Пусть — преобразование с ключом , а — выходное значение после i-го раунда. Тогда преобразование на i+1-м раунде можно записать в виде , кроме первого, где . Следовательно, выходное значение после m раундов шифрования будет . Можно заметить, что на последнем этапе не обязательно выполнять перестановку T.

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

. Достоинства и недостатки

Достоинства:

• Простота аппаратной реализации на современной электронной базе
• Простота программной реализации в силу того, что значительная часть функций поддерживается на аппаратном уровне в современных компьютерах (например, сложение по модулю 2, сложение по модулю , умножение по модулю , и т. д.)
• Хорошая изученность алгоритмов на основе сетей Фейстеля^[5]

Недостатки:

• За один раунд шифруется только половина входного блока^[6]