Блочные шифры

Блочный шифр — разновидность симметричного шифра. Особенностью блочного шифра является обработка блока нескольких байт за одну итерацию (как правило 8 или 16). Блочные криптосистемы разбивают текст сообщения на отдельные блоки и затем осуществляют преобразование этих блоков с использованием ключа.

Преобразование должно использовать следующие принципы:

• Рассеивание (diffusion) — то есть изменение любого знака открытого текста или ключа влияет на большое число знаков шифротекста, что скрывает статистические свойства открытого текста;
• Перемешивание (confusion) — использование преобразований, затрудняющих получение статистических зависимостей между шифротектстом и открытым текстом.

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

Основная идея

Блочный шифр состоит из двух взаимосвязанных алгоритмов: алгоритм шифрования E и алгоритм расшифрования E^-1. Входными данными служат блок размером n бит и k-битный ключ. На выходе получается n-битный зашифрованный блок. Для любого фиксированного ключа функция расшифрования является обратной к функции шифрования для любого блока M и ключа K.

Для любого ключа K, E_K является биективной функцией (перестановкой) на множестве n-битных блоков.

Размер блока n — это фиксированный параметр блочного шифра, обычно равный 64 или 128 битам, хотя некоторые шифры допускают несколько различных значений. Длина 64 бита была приемлема до середины 90-х годов, затем использовалась длина 128 бит, что примерно соответствует размеру машинного слова и позволяет эффективную реализацию на большинстве распространнённых вычислительных платформах. Различные схемы шифрования позволяют зашифровывать открытый текст произвольной длины. Каждая имеет определенные характеристики: вероятность ошибки, простота доступа, уязвимость к атакам. Типичными размера ключа являются 40, 56, 64, 80, 128, 192 и 256 бит. В 2006 г. 80-битный ключ способен был предотвратить атаку грубой силой.

Режимы работы (шифрования) блочного шифра

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

1. Electronic Codebook (ECB)

   Сообщение делится на блоки. Каждый блок шифруется отдельно (независимо от других и на одном ключе). Этот режим называется режимом электронной кодовой книги, так как существует возможность создать книгу, в которой каждому блоку открытого текста будет сопоставлен блок зашифрованного текста. Однако создать книгу — нетривиальная задача. Если размер блока равен x бит, то в книге будет содержаться 2^x записей, и каждая книга будет соответствовать одному ключу.

   Данный метод в ГОСТ 28147—89 называется "режим простой замены".

   Зашифрование может быть описано следующим образом:

   C_i = F(P_i) для любых i от 1 до N.

   Здесь C_i и P_i - блоки зашифрованного и открытого текстов соответственно, а F — функция блочного шифрования. Расшифровка по той же схеме. То есть P_i = F^-1(C_i).

   Шифрование в режиме ECB

   Расшифрование в режиме ECB

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   Недостатки:

   • Идентичные блоки открытого текста шифруются в идентичные блоки зашифрованного текста при одном и том же ключе; таким образом, этот метод плохо скрывает структуру данных.
   • Блоки могут пропадать или появляться. Злоумышленник может перехватить блок и продублировать его, и со стороны приёмника он будет воспринят как «правильный». Таким образом, не рекомендуется к использованию в криптографических протоколах.
2. Cipher Block Chaining (CBC)

   Для сцепления используется механизм обратной связи, поскольку результат шифрации предыдущих блоков используется для шифрации текущего блока. Этот метод называется "режим сцепления блоков шифртекста". Таким образом любой блок шифра зависит не только от исходного текста, но и от всех предыдущих блоков текста. В Cipher Block Chaining (CBC) текст XOR’ится с предыдущим зашифрованным блоком перед шифрацией. Дешифрация проводится аналогично. Математическая запись:

   
   
   

   C₀ = IV

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

   Шифрование в режиме CBC

   Расшифрование в режиме CBC

   Большинство сообщений не делятся нацело на 64-битные блоки, обычно остается короткий блок в конце. Можно по-разному бороться с этим. Простейший метод — padding (дополнение до полного блока). Если надо потом убирать мусор, то достаточно просто последним байтом обозначить количество лишних байтов. Можно также обозначать последний байт текста символом конца файла. Это не всегда можно сделать (напр., если надо расшифровать блок и поставить его куда-нибудь в память). Тогда применяется следующая схема шифрования: предположим, в последнем блоке j бит. После зашифровки последнего целого блока, зашифруем шифрованный блок еще раз, выберем j начальных битов полученного текста и по XOR’им с исходным текстом. Это и есть шифр для неполного блока.

3. Cipher Feedback (CFB)

   Режим (CFB) обратной связи шифра, близкий родственник CBC, превращает блочный шифр в самосинхронизирующийся шифр потока. Этот метод называется также «режим обратной связи по шифртексту». Операция очень похожа на предыдущую; в частности расшифровка CFB почти идентична расшифровке CBC, выполненной наоборот:

   
   
   

   C₀ = IV, где IV — вектор инициализации

   Шифрование в режиме CFB

   Расшифрование в режиме CFB

   Как режим CBC, изменения в открытом тексте распространяется повсюду в зашифрованном тексте, и в кодировании нельзя найти что-либо подобное. Также как и в CBC, в расшифровке можно найти что-либо подобное. Расшифровывая, однобитовое изменение в зашифрованном тексте затрагивает два блока открытого текста: однобитовое изменение в соответствующем блоке открытого текста, и полном искажении следующего блока открытого текста. Более поздние блоки открытого текста будут расшифрованы как обычно.

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

   CFB совместно использует два преимущества перед режимом CBC с режимами OFB шифра потока и CTR: блочный шифр только когда-либо используется в направлении шифровки, и сообщение не должно быть дополнено к кратному числу размера блока шифра.

   Данный метод в ГОСТ 28147—89 называется «режим гаммирования с обратной связью».

4. Output Feedback (OFB)

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

   Из-за симметрии операции сложения, шифрование и расшифрование похожи:

   
   
   

   O_i = E_k(O_i - 1)

   O₀ = IV

   Шифрование в режиме OFB

   Расшифрование в режиме OFB

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

   Данный метод называется также "режим обратной связи по выходу".

5. Counter Mode (CTR)

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

   Шифрование в режиме CTR

   ВВОД:

   ВЫВОД:
   
   

   Расшифровка в режиме CTR

   ВВОД:

   ВЫВОД:
   
   

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

   При отсутствии обратной связи алгоритмы шифрования и расшифровки в режиме CTR могут выполняться параллельно. Это обеспечивает режиму CTR преимущество перед режимами Cipher Feedback (CFB) и Output Feedback (OFB).