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


Содержание

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

Читайте также:

  1. Блоковые шифры
  2. Блочные и поточные шифры. Стандарт шифрования DES
  3. Блочные матрицы
  4. Блочные систематические коды.
  5. Блочные шифры
  6. Крупноблочные стены
  7. Недетерминированные шифры
  8. Перестановочные шифры.
  9. Потоковые шифры
  10. Потоковые шифры
  11. Поточные шифры

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

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

Характерной особенностью блочных криптоалгоритмов является тот факт, что в ходе своей работы они производят преобразование блока входной информации фиксированной длины и получают результирующий блок того же объема, но недоступный для прочтения сторонним лицам, не владеющим ключом. Таким образом, схему работы блочного шифра вы имеете возможность описать функциями Z=EnCrypt(X,Key)и X=DeCrypt(Z,Key).

Ключ Key является параметром блочного криптоалгоритма и представляет собой некоторый блок двоичной информации фиксированного размера. Исходный (X) и зашифрованный (Z) блоки данных также имеют фиксированную разрядность, равную между собой, но необязательно равную длине ключа.

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

Криптоалгоритм именуется идеально стойким, если прочесть зашифрованный блок данных, вы имеете возможность только перебрав все возможные ключи, до тех пор, пока сообщение не окажется осмысленным. Так как по теории вероятности искомый ключ будет найден с вероятностью 1/2 после перебора половины всех ключей, то на взлом идеально стойкого криптоалгоритма с ключом длины N потребуется в среднем 2 N-1 проверок. Таким образом, в обшем случае стойкость блочного шифра зависит только от длины ключа и возрастает экспоненциально с ее ростом. Даже предположив, что перебор ключей производится на специально созданной многопроцессорной системе, в которой благодаря диагональному параллелизму на проверку 1 ключа уходит только 1 такт, то на взлом 128 битного ключа современной технике потребуется не менее 10 21 лет.

Кроме этого условия к идеально стойким криптоалгоритмам применяется еше одно очень важное требование, которому они должны обязательно соответствовать. При известных исходном и зашифрованном значениях блока ключ, которым произведено это преобразование, вы имеете возможность узнать также только полным перебором. Ситуации, в которых постороннему наблюдателю известна часть исходного текста встречаются повсеместно. Это могут быть стандартные надписи в электронных бланках, фиксированные заголовки форматов файлов, довольно часто встречающиеся в тексте длинные слова или последовательности байт. Таким образом, на функцию стойкого блочного шифра Z=EnCrypt(X,Key)накладываются следующие условия:

— функция EnCryptдолжна быть обратимой;

— не должно существовать иных методов прочтения сообщения X по известному блоку Z, кроме как полным перебором ключей Key;

— не должно существовать иных методов определения каким ключом Keyбыло произведено преобразование известного сообщения X в сообщение Z, кроме как полным перебором ключей.

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

Это позволяет при выполнении условия обратимости функции относительно величины X сделать функцию необратимой относительно ключа Key.

Дата добавления: 2014-01-11 ; Просмотров: 367 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Глава 3 БЛОЧНЫЕ ШИФРЫ

3.1 Классификация блочных шифров

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

  • — шифры перестановки (Р-блоки);
  • — шифры замены (Б-блоки).

Шифры перестановки переставляют элементы открытых данных в некотором новом порядке. Существует несколько видов такой перестановки:

  • — горизонтальные;
  • — вертикальные;
  • — двойные;
  • — решетки;
  • — лабиринты.

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

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

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

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

Блочный шифр всегда состоит из двух взаимосвязанных алгоритмов, алгоритмов шифрования и расшифровывания. Входными данными служит блок размером п бит и ключ, размером к бит. На выходе мы получим п-битный зашифрованный блок. Обозначим алгоритм шифрования за ? , а алгоритм расшифровывания за ?’*, тогда для любого фиксированного ключа функция расшифровывания будет являться обратной к функции шифрования Ей?*Сйг(Ю) = М . Очевидно, что шифр будет работать тогда и только тогда, когда каждому ключу К, ?» будет являться однозначным отображением. Проще говоря, множеству битов ключа будет взаимно-однозначно соответствовать множество битов зашифрованного текст побитно.

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

  • — вероятность ошибки;
  • — простота доступа;
  • — уязвимость.

Существуют характерные размеры ключей, которые увеличиваются в соответствии с растущими вычислительными способностями современных суперкомпьютеров. Типичные размеры ключа:

По состоянию на 2010 год 128-битный ключ способен был выстоять перед атакой полного перебора. При использовании блочного перед исполнителем зачастую встает проблема дополнения. Дело в том, что размер шифруемого блока не всегда кратен размеру блока. Допустим, что мы имеем дело с алгоритмом, разбивающим данные по 16 байт, а в последнем используемом блоке мы получаем остаток из 5 байт. Отбросить данные мы не можем, поэтому данные 5 бит нам придется тащить за собой. Можно передать оставшиеся 5 бит в незашифрованном виде вместе с основной частью, но тогда мы получим возможность, хоть и малую, для атаки на наш шифр. В основном с оставшимися байтами поступают следующим образом:

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

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

  • 1) Что такое блочный шифр?
  • 2) Для чего используются блоки?
  • 3) Назовите характерный размер блоков.
  • 4) Назовите виды блочных шифров.
  • 5) Назовите типичные размеры ключа.
  • 6) Назовите основные характеристики алгоритмов блочного шифрования.
  • 7) Какой последовательности действий подвергаются байты открытого текста, которые не способны образовать целый блок?
  • 8) Опишите основной принцип работы блочных шифров.

9) Что такое принцип рассеивания и принцип перемешивания в блочных шифрах?

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

Представляют собой последовательность (с возможным повторением и чередованием) основных методов преобразования, применяемую к блоку (части) шифруемого текста. Блочные шифры на практике встречаются чаще, чем «чистые» преобразования того или иного класса в силу их более высокой кpиптостойкости. Российский и Американский стандарты шифрования основаны именно на этом классе шифров.

Шифрование с использованием открытых ключей

Как бы ни были сложны и надежны кpиптогpафические системы — их слабое мест пpи пpактической pеализации — пpоблема pаспpеделения ключей. Для того, чтобы был возможен обмен конфиденциальной информацией между двумя субъектами ИС, ключ должен быть сгенерирован одним из них, а затем каким-то обpазом опять же в конфиденциальном порядке передан другому. Т.е. в общем случае для пеpедачи ключа опять же тpебуется использование какой-то кpиптосистемы.

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

Суть их состоит в том, что каждым адpесатом ИС генеpиpуются два ключа, связанные между собой по опpеделенному пpавилу. Один ключ объявляется откpытым, а дpугой закpытым. Откpытый ключ публикуется и доступен любому, кто желает послать сообщение адpесату. Секpетный ключ сохpаняется в тайне.

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

Кpиптогpафические системы с откpытым ключом используют так называемые необpатимые или одностоpонние функции, котоpые обладают следующим свойством: пpи заданном значении x относительно пpосто вычислить значение f(x), однако если y=f(x), то нет пpостого пути для вычисления значения x.

Множество классов необpатимых функций и поpождает все pазнообpазие систем с откpытым ключом. Однако не всякая необpатимая функция годится для использования в pеальных ИС.

В самом опpеделении необpатимости пpисутствует неопpеделенность. Под необpатимостью понимается не теоpетическая необpатимость, а пpактическая невозможность вычислить обpатное значение используя совpеменные вычислительные сpедства за обозpимый интеpвал вpемени.

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

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

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


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

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

Система в которой реализуется все необходимое для использования технологии с открытыми ключами называется инфраструктура с открытыми ключами (ИОК).

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

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

Не нашли то, что искали? Воспользуйтесь поиском:

Режимы работы блочных шифров

Общие сведения о режимах шифрования. В 1980 г. в США был принят стандарт (FIPS PUB 81), определяющий режимы работы алгоритма DES (табл. 2.15). Аналогичный стандарт для алгоритма AES принят американским NIST в 2001 г. (NIST SP 800-38А 1 ). Эти режимы не привязаны к кон-

Режимы работы блочных шифров

Типичные области применения

Электронная кодовая книга (ЕСВ)

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

Передача отдельных значений (коротких текстов, ключевой информации)

Сцепление блоков шифра (СВС)

Входной блок данных алгоритма шифрования вычисляется как побитовый XOR текущего полного блока открытого текста и предшествующего полного блока шифротекста

Поблочная передача данных общего назначения. Аутентификация

Обратная связь по

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

Потоковая передача данных общего назначения. Аутентификация

1 NIST SP 800-38А 2001 Edition. Recommendation for Block Cipher Modes of Operation. Methods and Techniques // NIST Dec. 2001. URL: http://csrc.nist.gov/publications/nistpubs/ 800-38a/sp800-38a.pdf

Типичные области применения

Обратная связь по выходу (OFB)

Подобна СFВ, но в качестве входных данных алгоритма шифрования используется ранее полученный блок псевдослучайной последовательности

Потоковая передача данных по каналам с помехами

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

  • • электронная кодовая книга ЕСВ (Electronic Code Book);
  • • сцепление блоков шифра СВС (Cipher Block Chaning);
  • • обратная связь но шифротексту СЕВ (Cipher Feed Back);
  • • обратная связь но выходу OFB (Output Feed Back).

Можно сказать, что режимы работы уточняют особенности реализации блочных шифров для различных применений. FIPS PUB 81 определяет четыре режима работы: ЕСВ, СВС, СЕВ и OFB. Банковские стандарты ANSI определяют для шифрования ЕСВ и СВС, а для проверки подлинности — СВС и /-битовый СЕВ. Кроме того, режимы СЕВ и OFB (CTR) блочных симметричных шифров могут быть использованы в качестве криптографически стойких генераторов псевдослучайных последовательностей.

Электронная кодовая книга. Режим электронной кодовой книги ЕСВ является наиболее простым. При использовании режима ЕСВ защищаемое сообщение разбивают на 64-битные блоки Xt. Каждый такой блок шифруют независимо от других, с использованием одного и того же ключа шифрования (рис. 2.14). При расшифровывании криптограммы У, также преобразуются независимо друг от друга:

где Ek функция шифрования на ключе k; Xi и Yi блоки открытого текста и соответствующие им блоки зашифрованного текста.

Рис. 2.14. Режим электронной кодовой книги ЕСВ

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

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

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

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

Схема преобразования представлена на рис. 2.15. В этом режиме исходное сообщение, как и в предыдущем случае, разбивается на блоки Xt по 64 бита (для DES).

Перед шифрованием каждого блока i шифруемых данных предварительно выполняется его сложение по модулю 2 (XOR) с результатом шифрования предыдущего блока г — 1:

Рис. 2.15. Режим сцепления блоков СВС

Первый блок складывается побитно по модулю 2 с 64-битным блоком, называемым инициализирующим вектором (вектором инициализации, Initialization Vector) — IV, который известен обеим сторонам взаимодействия, периодически ими меняется и держится в секрете от других:

Затем блок исходного сообщения Х2 модифицируется с использованием блока криптограммы У, и т.д. Аналогичные действия производят при расшифровывании.

Варьируя значение вектора инициализации, можно получать различные шифротексты для одинаковых открытых текстов. При расшифровывании вектор инициализации должен быть известен. То же справедливо и для остальных режимов работы блочных шифров (СРВ и OFB).

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

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

Как легко заметить, последний блок криптограммы зависит от инициализирующего вектора, каждого бита открытого текста и значения секретного ключа: Уу = f(Xv Х,. XN, IV, к). Поэтому последний блок УЛГ можно использовать для контроля целостности и аутентификации сообщений (MAC — Message Authentication Code). Аутентификация отправителя зашифрованного сообщения производится но знанию им общего с получателем секретного ключа к.

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

Обратная связь но шифротексту. Режим обратной связи по шифротексту СРВ (рис. 2.16) более сложен в реализации, чем два предыдущих.

Рис. 2.1 в. Режим обратной связи по шифротексту CFB

Режим CFB используется в тех случаях, когда длина преобразуемого блока отличается от размера полного блока шифра (например, 64 бит для DES). Пусть необходимо зашифровать сообщение, считываемое последовательно блоками по гбит, где 1 1 NIST SP 800-38А 2001 Edition. Recommendation for Block Cipher Modes of Operation. Methods and Techniques.

Погружение в крипту. Часть 3: отечественные шифры

Содержание статьи

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

Roadmap

Это третий урок из цикла «Погружение в крипту». Все уроки цикла в хронологическом порядке:


  • Урок 1. Исторические шифры. Основы и исторические шифраторы. Как работают (и анализируются) шифры сдвига, замены, Рихарда Зорге, шифр Вернама и шифровальные машины
  • Урок 2. Распределение ключей. Что это такое, как выполняется распределение ключей и как выбрать криптостойкий ключ
  • Урок 3. Современные отечественные шифры. Что такое сеть Фейстеля и какими бывают отечественные блочные шифры, используемые в современных протоколах, — ГОСТ 28147—89, «Кузнечик» (ты здесь)
  • Урок 4. Современные зарубежные шифры. В чем разница между 3DES, AES, Blowfish, IDEA, Threefish от Брюса Шнайера и как они работают
  • Урок 5. Электронная подпись. Виды электронных подписей, как они работают и как их использовать
  • Урок 6. Квантовая криптография. Что это такое, где используется и как помогает в распределении секретных ключей, генерации случайных чисел и электронной подписи
Илон Маск рекомендует:  Шаблон сайта желтая звезда HTML, CSS, JavaScripts, 5 страниц

Блочное и поточное шифрование

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

Чтобы отличие между блочными и поточными шифрами стало понятнее, приведем пример на простом шифре замены.

Поточное шифрование

Зашифруем поточным шифром замены слово CIPHER:

a b c d e f g h i j k l m n o p q r s t u v w x y z
b e x g w i q v l o u m p j r s t n k h f y z a d c
С I P H E R
X L S V W N

Зашифровали каждый символ и получили шифротекст. Проще простого.

Блочное шифрование

Зашифруем слово AVADAKEDAVRA. Поскольку шифр блочный, открытый текст разобьем на блоки по четыре символа: AVAD | AKED | AVRA. На практике блоки текста состоят из 64‒256 бит. Для каждого блока придумаем свою таблицу замены:

a b c d e f g h i j k l m n o p q r s t u v w x y z
b e x g w i q v l o u m p j r s t n k h f y z a d c
a b c d e f g h i j k l m n o p q r s t u v w x y z
p g x e n v c i l h u j b m r s w t k o f d z a y q
a b c d e f g h i j k l m n o p q r s t u v w x y z
x w b g s q i v l c u m p o r j t m k n f y h a z d

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

A V A D
B Y B G
A K E D
P U N E
A V R A
X Y M X

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

Сеть Фейстеля

Теперь мы готовы перейти к очень важной теме, которая открывает дверь в бескрайний мир современных систем шифрования. Сеть Фейстеля — это метод блочного шифрования, разработанный Хорстом Фейстелем в лаборатории IBM в 1971 году. Сегодня сеть Фейстеля лежит в основе большого количества криптографических протоколов. Попробуем разобрать «на пальцах», что же она собой представляет.

Сеть Фейстеля оперирует блоками открытого текста, поэтому мы рассмотрим механизм ее работы на одном из блоков. С остальными блоками действия будут аналогичны.

  • Блок разбивается на две равные части — левую (L) и правую (R).
  • После разбиения левый подблок изменяется функцией f с использованием ключа K: x = f(L, K) . В качестве функции можно представить себе какое угодно преобразование — например, старый добрый шифр сдвига с ключом K.
  • Полученный подблок складывается по модулю 2 с правым подблоком R, который до этого был не у дел: x = x⊕R .
  • Далее полученные части меняются местами и склеиваются.

Как видишь, все достаточно просто. Для того чтобы понять, как это работает, посмотри на схему:

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

Теперь посмотрим работу сети Фейстеля на примере. Возьмем слово AVADAKEDAVRA и разобьем его на два блока по шесть символов — AVADAK | EDAVRA. За функцию возьмем шифр сдвига на число позиций, определенных раундовым ключом. Пусть секретный ключ K = [1, 2] . В качестве раундовых ключей возьмем K[0] = 1, K[1] = 2 . Для сложения по модулю 2 переведем текст в двоичный код согласно телеграфному алфавитику, которым вряд ли кто-то еще пользуется вообще.

Вот что получилось:

A V A D A K E D A V R A
00011 11110 00011 01001 00011 01111 00001 01001 00011 11110 01010 00011

Теперь прогоним через сеть Фейстеля из двух раундов первый блок:

Прогон первого блока

Второй блок попробуй зашифровать сам, у меня получилось MOSSTR.

Расшифрование осуществляется точно так же: шифротекст разбивается на блоки и затем подблоки, левый подблок поступает в функцию, складывается по модулю 2 с правым, и затем подблоки меняются местами. Отличие заключается в том, что раундовые ключи подаются в обратном порядке, то есть в нашем случае в первом раунде применим ключ K = 2, а затем во втором раунде K = 1.

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

ГОСТ 28147—89 (Магма)

В арсенале уже есть почти все необходимые понятия, поэтому мы готовы перейти к первой важной теме отечественной криптографии — ГОСТ 28147—89. Стоит сказать, что про этот стандарт не написал еще только ленивый, поэтому я попробую в миллион первый раз кратко и без тучи формул изложить суть режимов шифрования великой и ужасной Магмы. Если решишь почитать сам стандарт, то стоит запастись временем, силами, терпением и едой, потому что стандарты на человеческом языке, как известно, писать строго запрещено.

Основные характеристики: ключ 256 бит, блок 64 бита.

Перед разбором Магмы необходимо усвоить новое понятие — таблицы замены, или S-боксы. Это таблица того же вида, что и таблица в шифре замены. Предназначена для замены символов подблока на символы, зафиксированные в таблице. Не стоит думать, что S-бокс — это случайные цифры, сгенерированные функцией rand() . S-боксы представляют собой результат продуманных сгенерированных последовательностей, ведь на них держится криптостойкость всего шифра.

Продолжение доступно только участникам

Вариант 1. Присоединись к сообществу «Xakep.ru», чтобы читать все материалы на сайте

Членство в сообществе в течение указанного срока откроет тебе доступ ко ВСЕМ материалам «Хакера», увеличит личную накопительную скидку и позволит накапливать профессиональный рейтинг Xakep Score! Подробнее

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

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

  • шифры перестановки (transposition, permutation, P-блоки);
  • шифры замены (подстановки, substitution, S-блоки).

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

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

  • моноалфавитные (код Цезаря) ;
  • полиалфавитные (шифр Видженера, цилиндр Джефферсона, диск Уэтстоуна, Enigma).

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

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

В современных криптографических системах, как правило, используют оба способа шифрования (замены и перестановки). Такой шифратор называют составным (product cipher). Oн более стойкий, чем шифратор, использующий только замены или перестановки.

Блочное шифрование можно осуществлять двояко [4, c.129-130]:

1. Без обратной связи (ОС). Несколько битов (блок) исходного текста шифруются одновременно, и каждый бит исходного текста влияет на каждый бит шифртекста. Однако взаимного влияния блоков нет, то есть два одинаковых блока исходного текста будут представлены одинаковым шифртекстом. Поэтому подобные алгоритмы можно использовать только для шифрования случайной последовательности битов (например, ключей). Примерами являются DES в режиме ECB и ГОСТ 28147-89 в режиме простой замены.


2. С обратной связью. Обычно ОС организуется так: предыдущий шифрованный блок складывается по модулю 2 с текущим блоком. В качестве первого блока в цепи ОС используется инициализирующее значение. Ошибка в одном бите влияет на два блока — ошибочный и следующий за ним. Пример — DES в режиме CBC.

Генератор ПСЧ может применяться и при блочном шифровании [4, c. 128]:

1. Поблочное шифрование потока данных. Шифрование последовательных блоков (подстановки и перестановки) зависит от генератора ПСЧ, управляемого ключом.

2. Поблочное шифрование потока данных с ОС. Генератор ПСЧ управляется шифрованным или исходным текстом или обоими вместе.

Весьма распространен федеральный стандарт США DES (Data Encryption Standard) [1, 5], на котором основан международный стандарт ISO 8372-87. DES был поддержан Американским национальным институтом стандартов (American National Standards Institute, ANSI) и рекомендован для применения Американской ассоциацией банков (American Bankers Association, ABA). DES предусматривает 4 режима работы:

  • ECB (Electronic Codebook) электронный шифрблокнот;
  • CBC (Cipher Block Chaining) цепочка блоков;
  • CFB (Cipher Feedback) обратная связь по шифртексту;
  • OFB (Output Feedback) обратная связь по выходу.

ГОСТ 28147-89 — отечественный стандарт на шифрование данных [8]. Стандарт включает три алгоритма зашифровывания (расшифровывания) данных: режим простой замены, режим гаммирования, режим гаммирования с обратной связью — и режим выработки имитовставки.

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

Алгоритмы шифрования ГОСТ 28147-89 обладают достоинствами других алгоритмов для симметричных систем и превосходят их своими возможностями. Так, ГОСТ 28147-89 (256-битовый ключ, 32 цикла шифрования) по сравнению с такими алгоритмами, как DES (56-битовый ключ, 16 циклов шифрования) и FEAL-1 (64-битовый ключ, 4 цикла шифрования) обладает более высокой криптостойкостью за счет более длинного ключа и большего числа циклов шифрования.

Следует отметить, что в отличие от DES, у ГОСТ 28147-89 блок подстановки можно произвольно изменять, то есть он является дополнительным 512-битовым ключом.

Алгоритмы гаммирования ГОСТ 28147-89 (256-битовый ключ, 512-битовый блок подстановок, 64-битовый вектор инициализации) превосходят по криптостойкости и алгоритм B-Crypt (56-битовый ключ, 64-битовый вектор инициализации).

Достоинствами ГОСТ 28147-89 являются также наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

Блочные алгоритмы могут использоваться и для выработки гаммы. В этом случае гамма вырабатывается блоками и поблочно складывается по модулю 2 с исходным текстом. В качестве примера можно назвать B-Crypt, DES в режимах CFB и OFB, ГОСТ 28147-89 в режимах гаммирования и гаммирования c обратной связью.

Блочный шифр — Block cipher

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

Современный дизайн блочных шифров основан на концепции итерированного шифра продукта . В своей основополагающей 1949 публикации, Теория связи в секретных системах , Клод Шеннон проанализировали шифры продуктов и предложили им в качестве средства эффективного повышения безопасности пути объединения простых операций , таких как замены и перестановки . Итерированные шифры продукта осуществляют шифрование в нескольких раундах, каждый из которых использует другой раздел , полученный из исходного ключа. Одно широкое внедрение таких шифров, назвала сеть Feistel после Файстеля , в частности , реализуются в DES шифре. Многие другие реализации блочных шифров, таких как AES , классифицируются как заместительная-подстановок сетей .

Публикация шифра DES Национальным бюро стандартов Соединенных Штатов (впоследствии США Национальным институтом стандартов и технологий , NIST) в 1977 году был основным в общественном понимании современного дизайна блочных шифров. Это также повлияло на академическое развитие криптоаналитических атак . Оба дифференциальных и линейный криптоанализ возник из исследований по проектированию DES. По состоянию на 2020 год существует палитра методов атаки , против которой блочный шифр должен быть безопасным, в дополнение к тому , устойчив к грубой силы нападения .

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

содержание

Определение

Блочный шифр состоит из двух парных алгоритмов , один для шифрования, Е , а другой для расшифровки, D . Оба алгоритма принимает два входа: входной блок размера п бит и ключ от размера K бит; и оба получение п выходного -битный блока. Алгоритм дешифрования D определен , чтобы быть обратной функцией шифрования, т.е. D = E -1 . Более формально, блочный шифр задается с помощью функции шифрования

который принимает в качестве входных данных ключа K бита длиной к , называется размером ключа и битовой строка P длиной п , называется размером блока , и возвращает строку C из п бит. P называется открытым текстом , и C , называется шифротекста . Для каждого K , функция Е К ( Р ) требуется , чтобы быть обратимым отображением на <0,1>п . Обратным для Е определяется как функция

принимая ключ K и шифротекст C , чтобы возвращать значение открытого текста Р , таким образом, что

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

Для каждого ключа К , Е К является перестановка (а взаимно однозначное отображение) по множеству входных блоков. Каждая клавиша выбирает одну перестановку из множества возможных перестановок. ( 2 N ) ! <\ Displaystyle (2 ^ <п>)!>

дизайн

Итерированные блочные шифры

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

Как правило, круглый функция R принимает разные круглые ключи К я в качестве второго входа, которые получены из исходного ключа:

где есть открытый текст и шифротекст, причем г является числом раундов. M 0 <\ Displaystyle M_ <0>> M р <\ Displaystyle M_ <г>>

Часто ключ отбеливание зубов используется в дополнение к этому. В начале и в конце концов, данные изменены с ключевым материалом (часто с XOR , но также используются простые арифметические операции , такие как сложение и вычитание):

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

Замещение-подстановки сеть

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

Окно подстановки (S-бокс) заменяет небольшой блок входных бит с другим блоком выходных бит. Эта замена должна быть одна-к-одному , чтобы обеспечить обратимости (отсюда и дешифрование). Безопасная S-коробка будет иметь свойство , что изменение одного входного бита будет изменяться примерно половиной выходных бит в среднем, демонстрируя то , что известно как эффект лавинного -ie он обладает свойством , что каждый выходной бит будет зависеть от каждого входного бита.

Окно перестановки (P-бокс) является перестановкой всех бит: он принимает выходные сигналы всех S-блоки одного раунда, переставляют биты, и подают их в S-боксы следующего раунда. Хороший Р-коробка имеет свойство , что выходные биты любого S-блок распределены как много входов S-коробки , как это возможно.

На каждом раунде, круглый ключ (полученный от ключа с некоторыми простыми операциями, например, с использованием S-блоков и P-боксы) в сочетании с использованием некоторой операции группы, как правило , XOR .

Дешифрование производится путем простого обратного процесса ( с использованием обратны S-блоков и P-коробки и применяя круглые клавиши в обратном порядке).

Фейстеля шифры

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

Тогда основная операция заключается в следующем:

Разделить блок открытого текста на две равные части, ( , ) L 0 <\ Displaystyle L_ <0>> р 0 <\ Displaystyle R_ <0>>

Для каждого раунда , вычислите я знак равно 0 , 1 , . , N

Затем зашифрованный текст . ( р N + 1 , L N + 1 ) <\ Displaystyle (R_ <п + 1>, )>

Дешифрования шифротекста выполняется путем вычисления для ( р N + 1 , L N + 1 ) <\ Displaystyle (R_ <п + 1>, )> я знак равно N , N — 1 , . , 0

Тогда это открытый текст снова. ( L 0 , р 0 ) <\ Displaystyle (L_ <0>, R_ <0>)>

Одним из преимуществ модели криптографической по сравнению с сетью замещения-перестановки в том , что круглая функция не должна быть обратимой. F <\ Displaystyle <\ гт >>

Lai-Massey шифры

Схема Lai-Massey предлагает свойство безопасности , аналогичное тем , в структуре Фейстеля . Он также разделяет свое преимущество , что круглая функция не должна быть обратимы. Еще одно сходство, которое также разбивает входной блок на две равные части. Тем не менее, круглая функция применяется к разнице между ними, и результат затем добавляется к обоим блокам половиной. F <\ Displaystyle \ mathrm >

Тогда основная операция заключается в следующем:

Разделить блок открытого текста на две равные части, ( , ) L 0 <\ Displaystyle L_ <0>> р 0 <\ Displaystyle R_ <0>>

Для каждого раунда , вычислите я знак равно 0 , 1 , . , N

Затем зашифрованный текст . ( L N + 1 , р N + 1 ) знак равно ( L N + 1 ‘ , р N + 1 ‘ ) <\ Displaystyle (L_ <п + 1>, ) = (L_ <п + 1>‘R_ <п + 1>‘)>


Дешифрования шифротекста выполняется путем вычисления для ( L N + 1 , р N + 1 ) <\ Displaystyle (L_ <п + 1>, )> я знак равно N , N — 1 , . , 0

Тогда это открытый текст снова. ( L 0 , р 0 ) знак равно ( L 0 ‘ , р 0 ‘ ) <\ Displaystyle (L_ <0>, R_ <0>) = (L_ <0>‘R_ <0>‘)>

операции

ARX ​​(надстройка вращать-XOR)

Многие современные блочные шифры и хэш ARX алгоритмы-их круглая функция включает в себя только три операции: сложение, модульное вращение с фиксированной суммой вращения и XOR (ARX). Примеры включают ChaCha20 , Спек , XXTEA и Blake . Многие авторы делают сеть ARX, вид диаграммы потока данных , чтобы проиллюстрировать такую круглую функцию.

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

Другие операции

Другие операции , часто используемые в блочных шифрах включают в себя вращение данных в зависимости от , как и в RC5 и RC6 , в заместительной коробке , выполненной в виде справочной таблицы , как в Data Encryption Standard и Advanced Encryption Standard , в окне перестановки и умножении , как и в IDEA .

Режимы работы

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

Чтобы преодолеть это ограничение, несколько так называемых режимы блочного шифра работы были разработаны и определены в национальных рекомендациях , такие как NIST 800-38A и BSI TR-02102 и международные стандарты , такие как ISO / IEC 10116 . Общая концепция заключается в использовании рандомизации из данных открытого текста на основе дополнительного входного значения, часто называемый вектор инициализации , чтобы создать то , что называется вероятностное шифрование . В популярным шифре цепочке блоков режим (ПГС), для шифрования , чтобы быть обеспечить вектор инициализации передается вместе с открытым текстом сообщения должно быть случайным или псевдослучайным значение, которое добавляет в исключающем или таким образом , чтобы первый блок открытого текста перед тем он шифруется. Полученный блок шифртекста затем используются в качестве нового вектора инициализации для следующего блока открытого текста. В шифре обратного режима (ЦКС), который эмулирует самосинхронизирующийся потоковый шифр , вектор инициализации сначала шифруются и затем добавляют к блоку открытого текста. Выход обратной связи Режим (OFB) повторно шифрует вектор инициализации , чтобы создать поток ключей для эмуляции синхронного поточного шифра . Новый счетчик режим (CTR) , аналогично создает ключевой поток, но имеет преимущество только нуждающийся уникальные и не (псевдо-) случайные значения в качестве векторов инициализации; необходимая случайность происходят внутри , с использованием вектора инициализации в качестве блока счетчика и шифрования этого счетчика для каждого блока.

Илон Маск рекомендует:  Что такое код ssi

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

набивка

Некоторые режимы , такие как режим CBC работать только на полных блоков открытого текста. Просто расширение последнего блока сообщения с нулевой бит является недостаточным , поскольку он не позволяет приемник легко различать сообщения , которые отличаются только в количестве бит заполнения. Что еще более важно, такой простое решение приводит к очень эффективным атакам обивки оракула . Подходящая схема заполнения Поэтому необходимо , чтобы расширить последний блок открытого текста по размеру блока шифра. Хотя многие популярные схемы , описанные в стандартах и в литературе , как были показаны , чтобы быть уязвимы для заполнения оракула атак, решение , которое добавляет одну немного , а затем проходит последний блок с нулевыми битами, стандартизированный «метод заполнения 2» в ISO / IEC 9797-1 , было доказано в безопасности от этих атак.

криптоанализа

Грубая сила атака

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

Дифференциальный криптоанализ

Линейный криптоанализ

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

Открытие приписывается Мицуру Matsui , который первым применил технику к FEAL шифра (Matsui и Ямагиши, 1992).

Интегральный криптоанализ

Интегральный криптоанализ является криптоаналитической атакой,частностиприменимы к блоку шифровоснове заместительных-перестановки сетей. В отличии от дифференциального криптоанализа,котором используется пар выбранных открытых текстов с разностью фиксированной XOR, интегральный криптоанализ использует наборы или даже мультинаборы из выбранных открытых текстов из которых часть удерживается постояннойа другая часть изменяется через все возможности. Например, атака может использовать 256 выбранных открытых текстовкоторые имеют всекроме 8 бит их же, но все отличаются в этих 8 битов. Такой набор обязательно имеет XOR сумму 0, а XOR сумма соответствующих наборов шифртекстов предоставляет информацию о работе шифра. Этот контраст между перепадами пара текстов и суммами больших наборов текстов вдохновил название «Интеграл криптоанализа», заимствуя терминологию исчисления.

Другие методы

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

Стойкость

Когда блок шифр используются в данном режиме работы , полученный алгоритм должен быть идеально примерно так же безопасен , как сами блочным шифр. ЕЦБ (обсуждалось выше) категорически не хватает этого свойства: независимо от того, насколько безопасный базовый блок шифр, ЕСВ режим легко могут быть атакованы. С другой стороны, режим CBC может быть доказан в безопасности в предположении , что основной блок шифр является также безопасным. Замечу, однако, что делать заявление , как это требует формальных математических определений для того, что это означает , что для алгоритма шифрования или блочного шифра , чтобы «быть безопасными». В этом разделе описываются два общих понятия для того, что свойства блочного шифра должен иметь. Каждый соответствует математической модели , которая может быть использована , чтобы доказать свойство алгоритмов более высокого уровня, такие как CBC.

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

стандартное исполнение

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

Для того, чтобы быть немного более точным, пусть Е быть п -битных блочный шифр. Мы представляем себе следующую игру:

  1. Человек работает игра подбрасывает монету.
    • Если монета приземляется на голове, он выбирает случайный ключ K и определяет функцию F = E K .
    • Если монета приземляется на хвост, он выбирает случайную перестановку тг на множестве п битовых строк, и определяет функцию F = П .
  2. Атакующий выбирает п -разрядной строки X , а человек запустить игру говорит ему значение F (X) .
  3. Шаг 2 повторяется в общей сложности д раз. (Каждый из этих д взаимодействий является запрос .)
  4. Атакующий догадывается, как монета приземлился. Он выигрывает, если его догадка верна.

Злоумышленник, который мы можем моделировать как алгоритм, называется противником . Функции F (который противник был в состоянии запроса) называется Oracle .

Обратите внимание , что противник может тривиально обеспечить 50% шансы на победу , просто угадывая в случайном порядке (или даже, например, всегда угадывают «головы»). Поэтому, пусть P E (A) обозначает вероятность того, что противник выигрывает эту игру против E , и определить преимущества от А , как 2 ( Р Е (А) — 1/2). Отсюда следует , что если догадывается случайным образом , его преимущество будет 0; С другой стороны, если всегда выигрывает, то его преимущество состоит в том 1. блочного шифра Е представляет собой псевдослучайные перестановки (ПРП) , если противник не имеет преимущества значительно больше , чем 0, учитывая указание ограничения на ц и время работы на противнике , Если на шаге 2 выше противников имеют возможность обучения п -1 (X) вместо F (X) (но все еще имеют лишь небольшие преимущества) , то Е является сильным ПРП (СПРП). Противник неадаптивная , если он выбирает все Q значения X до начала игры (то есть, она не использует какую — либо информацию , почерпнутые из предыдущих запросов , чтобы выбрать каждый X , как она идет).

Эти определения оказались полезными для анализа различных режимов работы. Например, можно определить подобную игру для измерения безопасности алгоритма шифрования шифра на основе блока, а затем попытаться показать (через аргумент редукции ) , что вероятность противника победы в эту новую игру не намного больше , чем P E (А) для некоторого А . (Уменьшение обычно обеспечивает пределы на д и времени работы .) Эквивалентно, если Р Е (А) мал для всех соответствующих А , то ни один злоумышленник не имеет значительную вероятность выигрыша новую игру. Это формализует идею о том , что алгоритм более высокого уровня безопасности наследуется блочного шифра.

Идеальная модель шифра

Практическая оценка

Блочные шифры могут быть оценены в соответствии с множеством критериев на практике. Общие факторы включают в себя:

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

Заметные блочные шифры

Люцифер / DES

Lucifer , как правило , считается первый гражданский блочный шифр, разработанный в IBM в 1970 — х годах на основе работы , проделанной Файстель . Пересмотренный вариант алгоритма был принят в качестве правительства США Federal Information Processing Standard : FIPS PUB 46 Data Encryption Standard (DES). Он был выбран американским Национальным бюро стандартов (НБС) после публичного приглашения для представления и некоторых внутренних изменений по НБС (и, потенциально, тем NSA ). DES был публично выпущен в 1976 году и широко используется.

DES был разработан , чтобы, среди прочего, противостоять определенной криптографические атаки , известный АНБ и переоткрыт IBM, хотя неизвестно публично , пока вновь снова и опубликованы Бихам и Ади Шамир в конце 1980 — х годов. Метод называется дифференциальным криптоанализом и остается одним из немногих общих атак против блочных шифров; линейный криптоанализ другой, но , возможно, были неизвестны даже АНБ, до его публикации Мицуру Мацуи . DES предложено большое количество других работ и публикаций в области криптографии и криптоанализа в открытом обществе , и это вдохновило много новых шифров конструкций.

DES имеет размер блока 64 бита и размер ключа 56 бита. 64-разрядные блоки стали обычным делом в блоке шифра конструкций после DES. Длина ключа зависит от нескольких факторов, в том числе и государственного регулирования. Многие наблюдатели в 1970 — х годах заметили , что длина ключа 56-бита используется для DES была слишком короткой. Время шло, его неадекватность стала очевидной, особенно после того, как машина специального назначения предназначен сломать DES был продемонстрирован в 1998 году Electronic Frontier Foundation , . Расширение DES, тройной DES , тройной шифрует каждый блок либо с двумя независимыми ключами (112-битный ключ и 80-битный безопасности) или трех независимых ключей (168-битовый ключ и 112-битный безопасности). Он был широко принят в качестве замены. По состоянию на 2011 год , три ключа версии по — прежнему считается безопасным, хотя Национальный институт стандартов и технологий (NIST) стандарты не позволяют использовать два ключа версии новых приложений из — за его уровня безопасности 80-битным.

International Data Encryption Algorithm ( IDEA ) представляет собой блочный шифр разработанный Джеймсом Мэсси из ETH Zurich и Xuejia Lai ; он был впервые описан в 1991 году, в качестве предназначенного для замены DES.

IDEA работает на 64-битных блоков , используя 128-битный ключ, и состоит из серии из восьми идентичных преобразований (а круглые ) и выходного преобразования ( полукруглой ). Процессы шифрования и дешифрования похожи. IDEA получает большую часть своей безопасности чередованием операций из различных групп — модульное сложение и умножение, и побитовое исключающее ИЛИ (XOR) — алгебраически «несовместимы» в каком — то смысле.

Разработчики проанализировали IDEA , чтобы измерить его силу против дифференциального криптоанализа и пришли к выводу , что иммунитет при определенных предположениях. Нет успешных линейных или алгебраические недостатки не поступало. По состоянию на 2012 год , лучшая атака , которая распространяется на все лады может сломаться полным 8,5-круглый IDEA с помощью узкополосной bicliques атаки примерно в четыре раза быстрее , чем грубая сила.

RC5 представляет собой блочный шифр разработанный Ривест в 1994 году , который, в отличие от многих других шифров, имеет переменный размер блока (32, 64 или 128 бит), размер ключа ( от 0 до 2040 бит) , и количество раундов ( от 0 до 255). Оригинальный предложил выбор параметров был размером блока 64 бита, 128-битного ключа и 12 раундов.

Ключевая особенность RC5 является использованием вращений данных зависят от способа ; одна из целей RC5 был подсказывать изучение и оценку таких операций , как криптографический примитив. RC5 также состоит из ряда модульных дополнений и операции XOR. Общая структура алгоритма является Фейстеля сеть -подобного. Шифрование и дешифрование функция может быть определена в нескольких строках кода. Основной график, однако, является более сложным, расширяя ключ , используя по существу односторонний функции с бинарным разложением как е и золотым сечением в качестве источников « ничего не мои номеров рукава ». Дразнящая простота алгоритма вместе с новизной вращений данных в зависимости от сделала RC5 привлекательный объект исследования для криптоаналитиков.

12 круглый RC5 (с 64-битовыми блоками) чувствителен к дифференциальной атаке с помощью 2 44 выбранных открытых текстов. 18-20 раундов, предлагаются в качестве достаточной защиты.

Rijndael / AES


Rijndael шифр , разработанный бельгийскими криптографы, Джоан Daemen и Винсент Рэймен был один из конкурирующих проектов для замены DES. Он выиграл открытый конкурс 5-летний , чтобы стать AES, (Advanced Encryption Standard).

Принято NIST в 2001 году, AES имеет фиксированный размер блока 128 бит и размер ключа 128, 192 или 256 бит, в то время как Rijndael может быть указан с блоком и ключевыми размерами в любом кратном 32 бит, с минимумом 128 биты. Размер_блока имеет максимум 256 бит, но размер ключа не имеет теоретического максимума. AES работает на 4 × 4 столбцам порядка матрицы байтов, называется состояние (варианты Rijndael с большим размером блока имеют дополнительные столбцы в состоянии).

Blowfish

Blowfish представляет собой блочный шифр, разработанный в 1993 году Брюс Шнайер и включены в большом количестве шифров и продуктов шифрования. Иглобрюхий имеет 64-битный размер блока и переменную длину ключа от 1 бит до 448 бит. Это 16-раундовый Feistel шифр и использует большой ключзависимости от S-блоки . Особенности конструкции являются ключевыми зависящими от S-блоки и весьма сложного ключом графика .

Он был разработан как алгоритм общего назначения, предназначенный в качестве альтернативы старения DES и без проблем и ограничений , связанных с другими алгоритмами. В то время Blowfish был выпущен, многие другие проекты были собственностью, обременены патентами или были коммерческими / государственными секретами. Шнайер заявил , что, «Blowfish является незапатентованный, и будет оставаться таковым во всех странах. Алгоритм тем самым помещен в общественное достояние и могут свободно использоваться кем угодно.» То же самое относится к Twofish , алгоритм преемника из Шнайер.

Обобщения

Оттиск и блочные шифры

М. Лиск, Р. Ривест и Д. Вагнер описали обобщенный вариант блочных шифров под названием «» настраиваемые блочные шифры. Настраиваемых блочный шифр принимает второй вход называется подстройкой вместе с обычным открытым текстом или входом шифртекста. Твик, вместе с ключом, выбирает перестановку , вычисленную шифр. При изменении настроек достаточно легкий ( по сравнению с обычно довольно дорогой ключевой операцией установки), то некоторые интересные новые режимы работы становятся возможными. Теория шифрования диска статья описывает некоторые из этих режимов.

Формат сохраняющих шифрования

Блочные шифры традиционно работают над двоичным алфавитом . То есть, как вход и выход являются двоичными строками, состоящим из п нулей и единиц. В некоторых ситуациях, однако, один , возможно , пожелают иметь блочный шифр , который работает над каким — либо другим алфавитом; например, шифрование номера кредитных карт 16-значных таким образом , что шифротекста также 16-значное число может облегчить добавление слоя шифрования для унаследованного программного обеспечения. Это пример шифрования формата сохраняющих . В целом, шифрование формата сохраняющего требует шпоночной перестановки на некотором конечном языке . Это делает FORMAT сохраняющих схемы шифрования естественное обобщение (настраиваемых) блочных шифров. В отличие от традиционных схем шифрования, такие как CBC, не являются перестановками , так как тот же открытый текст может зашифровать к нескольким различным шифртекстам, даже при использовании фиксированного ключа.

Отношение к другим криптографических примитивов

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

  • Шифры Потоковые могут быть построены с использованием блочных шифров. OFB-режим и режим CTR являются режимами блоков , которые превращают блочный шифр в потоковый шифр.
  • Криптографические хэш — функции могут быть построены с использованием блочных шифров. См односторонний функции сжатия для описания нескольких таких методов. Методы похожи на режимах блочного шифра работы , обычно используемые для шифрования.
  • Криптографические защита генераторы псевдослучайных чисел (CSPRNGs) могут быть построены с использованием блочных шифров.
  • Безопасные псевдослучайные перестановки из произвольного размера конечных множеств могут быть построены с блочными шифрами; см Формат сохраняющих шифрования .
  • Коды аутентификации сообщений (ПДК) часто строятся из блочных шифров. CBC-MAC , OMAC и РМАС такие МЫ.
  • Заверенные шифровании также построены из блочных шифров. Это означает , что для шифрования и MAC одновременно. То есть , как обеспечить конфиденциальность и аутентификацию . CCM , EAX , GCM и ОСВ такие режимы шифрования с проверкой подлинности.

Подобно тому , как блочные шифры могут быть использованы для построения хэш — функций, хэш — функции могут быть использованы для построения блочных шифров. Примеры таких блочных шифров являются SHACAL , медведь и ЛЬВЕВ .

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

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

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

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

Режим электронной шифровальной книги. Режим электронной шифровальной книги (electronic codebook, ECB) — это наиболее очевидный способ использовать блочный шифр: блок открытого текста заменяется блоком шифротекста. Так как один и тот же блок открытого текста заменяется одним и тем же блоком шифротекста, то теоретически возможно создать шифровальную книгу блоков открытого текста и соответствующих шифротекстов. Однако, если размер блока — 64 бита, то кодовая книга будет состоять из 264 записей — слишком много для предварительного вычисления и хранения. И не забывайте, для каждого ключа понадобится отдельная шифровальная книга.

Это самый легкий режим работы. Все блоки открытого текста шифруются независимо. Нет необходимости в последовательном шифровании файла, можно зашифровать сначала 10 блоков из середины текста, затем последние блоки, и наконец, первые. Это важно для шифрованных файлов с произвольным доступом, например, для баз данных. Если база данных зашифрована в режиме ЕСВ, то любая запись может быть добавлена, удалена, зашифрована или расшифрована независимо от любой другой записи (при условии, что каждая запись состоит из целого числа блоков шифрования). Кроме того, обработка может быть распараллелена, если используются несколько шифровальных процессоров, они могут независимо друг от друга шифровать или дешифрировать различные блоки.

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

Если криптоаналитик знает, что блок открытого текста «5е081Ьс5» при шифровании превращается в блок шифротекста «7еа593а4,» то он может мгновенно расшифровать этот блок шифротекста, в каком-бы другом с сообщении он не появился. Если в шифрованном сообщении много повторов, которые имеют тенденцию занимать одинаковое место в различных сообщениях, криптоаналитик может получить много информации. Он может попытаться статистически вскрыть используемый открытый текст, независимо от силы блочного шифра.

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

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

Набивка. Большинство сообщений точно не делятся на 64-битные (или любого другого размера) блоки шифрования, в конце обычно оказывается укороченный блок. ЕСВ требует использовать 64-битные блоки. Способом решения этой проблемы является набивка.

Последний блок дополняется (набивается) некоторым регулярным шаблоном — нулями, единицами, чередующимися нулями и единицами — для получения полного блока. При необходимости удалить набивку после дешифрирования запишите количество байтов набивки в последний байт последнего блока. Например, пусть размер блока — 64 бита, и последний блок состоит из 3 байтов (24 бит). Для дополнения блока до 64 бит требуется пять байтов, добавьте четыре байта нулей и последний байт с числом 5. После дешифрирования удалите последние 5 байтов последнего расшифрованного блока. Чтобы этот метод работал правильно, каждое сообщение должно быть дополнено. Даже если открытый текст содержит целое число блоков, вам придется добавить один полный блок. С другой стороны, можно использовать символ конца файла для обозначения последнего байта открытого текста и дополнить этот символ ег.

Илон Маск рекомендует:  Что такое код asp cpuenablelogging

Р «_] — последний полный блок открытого текста, а Р» — последний, короткий блок открытого текста. С «_; — последний полный блок шифротекста, и С» — последний, короткий блок шифротекста. С’ — это промежуточный результат, не являющийся ч а-стью переданного шифротекста.

Блочные шифры и их криптоанализ Текст научной статьи по специальности « Общие и комплексные проблемы технических и прикладных наук и отраслей народного хозяйства»

Аннотация научной статьи по общим и комплексным проблемам технических и прикладных наук и отраслей народного хозяйства, автор научной работы — Пестунов А. И.

Nowadays block ciphers became the most important way for data protection, therefore there are a number of projects devoted to their investigation Specialists from all over the world are involved in their design and analysis. This paper provides a survey of design principles and methods of checking the security of contemporary block ciphers.

Похожие темы научных работ по общим и комплексным проблемам технических и прикладных наук и отраслей народного хозяйства , автор научной работы — Пестунов А. И.,

Текст научной работы на тему «Блочные шифры и их криптоанализ»

Том 12, Специальный выпуск 4, 2007

БЛОЧНЫЕ ШИФРЫ И ИХ КРИПТОАНАЛИЗ

Институт вычислительных технологий СО РАН, Новосибирск, Россия

e-mail: an24@ngs. ru

Nowadays block ciphers became the most important way for data protection, therefore there are a number of projects devoted to their investigation Specialists from all over the world are involved in their design and analysis. This paper provides a survey of design principles and methods of checking the security of contemporary block ciphers.

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

Для того чтобы злоумышленник не смог извлечь пользу из перехвата информации или получатель смог определить, что сообщение фальсифицировано, как правило, используются схемы с секретным (закрытым) ключом. По большому счету, они уже применялись в древности, но формализованы были в 1949 г. Клодом Шенноном (Claude Shannon), именно со времени его публикации [1] криптография, которая ранее называлась тайнописью, считается оформившейся как наука.

Схема с секретным ключом (рис. 1) подразумевает наличие двух каналов связи: «дешевого» (Интернет, телефон) и «дорогого» (личная встреча, курьерская почта). Дешевизна первого из них может заключаться в его материальной стоимости, доступности в любой момент или высокой скорости передачи сообщений. Дорогой канал не предоставляет таких удобств, но он, в отличие от дешевого, защищен от доступа к нему посторонних. Для безопасного общения отправитель и получатель информации разово обмениваются секретным ключом с помощью защищенного канала, а затем передают сообщения, зашифрованные некоторым алгоритмом с полученным ключом, по незащищенному каналу.

В 1976 г. Уидфилд Диффи (Whitfield Diffie) и Мартин Хеллман (Martin Hellman) [2] предложили схему с открытым ключом, которая позволяет обмениваться данными без

© Институт вычислительных технологий Сибирского отделения Российской академии наук, 2007.

Рис. 1. Схема с секретным ключом

наличия дорогого защищенного канала. Скорость работы подобного рода схем мала, и они обычно применяются в комбинации со схемами с секретным ключом, выступая в роли дорогого канала: абоненты формируют секретный ключ с помощью схемы Диф-фи — Хелмана (или аналогичной ей) и осуществляют обмен сообщениями с помощью схемы Шеннона.

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

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

1. Общие сведения о блочных шифрах

Типичный блочный шифр преобразует открытый текст, представленный в виде последовательности битов (нулей и единиц), по блокам фиксированной длины, чаще всего 64 или 128 бит. Секретный ключ также представляет собой битовую последовательность обычно длиной 128 или 256, из которой с помощью определенного для каждого шифра алгоритма получается набор из Я подключен. Процедура шифрования заключается в Я-кратном выполнении некоторой относительно простой функции, которая зависит от своего подключа и называется раундом шифрования. Чаще шифр состоит из одинаковых раундов, но иногда они различаются. Чем больше раундов выполнено, тем надежней, но медленней становится шифр, поэтому создатель определяет такое количество раундов, которое обеспечит как безопасность, так и быстродействие алгоритма. Для удобства реализации, особенно на физическом уровне, блочные шифры проектируются так, чтобы процедуры шифрования и дешифрирования были похожи. Наиболее удачными в этом отношении выглядят те шифры, в которых эти две процедуры разли-

чаются только порядком подачи подключей, т. е. для расшифровки требуется обратный порядок подключей с R-то по 1-й.

Главные свойства шифра — это пропускная способность (скорость шифрования) и надежность. Скорость измеряется числом тактов на шифрование одного блока или просто физическим временем, если измерения проводятся на аналогичных процессорах. Существенно сложнее обстоит дело с безопасностью. Надежным шифром интуитивно можно считать тот, который невозможно взломать, или вскрыть. Но это понятие требует уточнения. Для того чтобы внести определенность, еще в 1883 г. Август Керхгоффс (Augustо Kerckhoffs) предложил считать, что злоумышленник знает о криптосистеме все, кроме секретного ключа, и главной его целью является разработка метода, позволяющего отыскать ключ, используя какие-то эксперименты с шифром1. Алгоритм такого сорта называется атакой.

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

Любой шифр может быть вскрыт с помощью полного перебора ключей. Злоумышленник перехватывает одну пару (или несколько пар) блоков — «текст» и «шифртекст», а затем, шифруя «текст» всеми возможными ключами, ищет тот из них, который приведет к шифрованию «текста» в «шифртекст». Очевидным достоинством данного метода является то, что таким образом вскрывается любой шифр. Главный недостаток — необходимость перебирать все возможные ключи. Так, например, если длина ключа составляет 128 бит, то такой метод требует в среднем 2127 операций шифрования. Отсюда следует, что длина ключа должна быть достаточной, чтобы исключить подобного рода угрозы, причем и в обозримом будущем, поскольку мощности ЭВМ растут.


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

Первым блочным шифром стоит признать алгоритм Люцифер (Lucifer), опубликованный в 1973 г. [3], который разработан Хорстом Фейстелем, а через четыре года Национальным бюро стандартов США был опубликован усовершенствованный вариант алгоритма Люцифера — шифр DES — Data Encryption Standard (стандарт шифрования данных), который играл ключевую роль в защите информации на протяжении последней четверти XX в. [4]. DES принимал 56-битный ключ, но с развитием вычислительной техники перебор размера 256 становился все более и более реальным, компанией RSA был даже запущен Интернет-проект, в рамках которого люди по всему миру осуществляли подобный перебор, и примерно за два года ключ был найден.

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

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

опасность этого алгоритма не вызывает сомнений, но скорость шифрования и относительная сложность реализации были неприемлемы для ряда приложений и устройств. Очевидная необходимость обновления стандарта шифрования произвела своего рода бум, в результате которого появились новые алгоритмы, претендовавшие на потенциально вакантное место, а в 1997-2000 гг. Национальный институт стандартов и технологий США провел конкурс шифров, победитель которого получил название AES (Advanced Encryption Standard) [5] и был принят в качестве стандарта.

2. Дизайн блочного шифра

Блочные шифры конструируются двумя наиболее распространенными способами: в виде сети Фейстеля и подстановочно-перестановочной сети. Сеть Фейстеля получила свое название по имени Хорста Фейстеля — создателя первого блочного шифра Люцифер. Раунды этого типа шифруют блок текста следующим образом: блок вначале разбивается на две равные части, затем правая из них преобразуется функцией F, зависящей от подключа, и Х(Жируется с левой частью, после этого части меняются местами. Сеть Фейстеля очень хороша тем, что шифрование отличается от дешифрирования только порядком подачи подключей, а раундовая функция может быть практически любой. Главный недостаток такого рода шифров заключается в том, что за один раунд изменяется только одна половина блока. Позднее появились различные модификации сети Фейстеля (рис. 2), что связано в основном с тем, что классическая сеть Фейстеля ориентирована на 64-битные блоки, а если преобразовывать текст по 128-битным блокам, то возникают проблемы, как как платформы на большинстве современных ЭВМ 32-битные. Вследствие этого блок необходимо разбивать не на две, а на четыре части. Одна из модификаций сети Фейстеля приведена на рис. 2.

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

ется небольшая подстановочно-перестановочная сеть. Победитель конкурса AES шифр

Модифицированная сеть Фейстеля Подстановочно-перестановочная сеть

Рис. 2. Типы раундов блочного шифра

Rijndael [6] полностью является подстановочно-перестановочной сетью с двумя типами перестановок. Модифицированными сетями Фейстеля являются финалисты конкурса AES: Mars, ЕС6 и Twofish.

3. Криптоанализ блочного шифра

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

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

3.1. Дифференциальный и линейный криптоанализ

Дифференциальный криптоанализ [7], предложенный Эли Бихамом (Eli Biham) и Ади Шамиром (Adi Shamir) в 1992 г., стал первым методом, который позволил разработать алгоритм поиска всех подключей для DES быстрее полного перебора ключей. В том же году ,\ii щуру Мацу и ( Mi! sum Matsui) предложил линейный криптоанализ [8], что позволило находить подключи еще быстрее.

Основной объект, который исследуется в дифференциальном криптоанализе, — это пары блоков текста йВс определенной разностью (difference), как правило, эта разность определяется как исключающее или (хог), т.е. A ф B. Если мы не располагаем информацией о том, как связаны входная (между блоками открытого текста) и выходная (между блоками шифртекста) разности, то все выходные разности равновероятны, но если нам удалось установить, что некоторая входная разность Ainp вызывает некоторую выходную разность Aout с вероятностью, большей, чем остальные, то это может быть использовано для поиска подключей шифра. Пара (Ainp и Aout) называется дифференциалом, а совокупность всех дифференциалов на различных раундах называется характеристикой.

Алгоритм поиска подключей поясним на примере. Рассмотрим шифр, имеющий 64-битный блок, 128-битный секретный ключ, состоящий из R =16 раундов и на всех

Ainp. Если шифр совершенный, то вероятность того, что разность пары блоков шифр-

текста равна Aout, составляет 2-64, т. е. все выходные разности равновероятны. Предположим, нами установлено, что если такую пару зашифровать с помощью R — 1 раундов, то выходная разность равна Aout с вероятноетью 2-20. Такой недостаток шифра может

Атака реализуется в несколько шагов. Возьмем 220 пар блоков с разностью Ainp,

расшифровываем на один раунд сохраненные в памяти пары шифртекста и проверяем равенство их разности Aout. Если ни одна из пар не приводит к такой разности, то отбрасываем этот подключ и переходим к следующему. Если такая разность появилась хотя бы раз, то подключ — верный.

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

этому вероятность появляения любой разности (в том числе и Aout) равна 2-64. Вероятность появления такой разности среди 220 пар равна 2-44. Вероятность, что хотя бы один из 232 — 1 неправильных подключей приведет к такой разности, равняется 2-12, и все неправильные подключи будут отброшены с вероятностью 1 — 2-12.

Если пара расшифрована с помощью правильного подключа, то выходная разность

равна Aout с вероятное тью 2-20, а, используя распределение Пуассона, можно заклю-220

образом, вероятность успеха нашей атаки равна примерно 0.63, она может быть увеличена, если увеличить число блоков текста.

блоков открытого текста, 224 байт памяти, чтобы их хранить, и 253 операций однораун-дового дешифрирования (эквивалентно 249 полнораундовых шифрований), чтобы для

После описания исходного варианта дифференциального криптоанализа стали появляться различные его модификации: усеченные (truncated) дифференциалы [9], атака бумерангом (boomerang attack) [10], нереальные (impossible) дифференциалы [11]. На данный момент дифференциальный криптоанализ вместе со всеми своими модификациями является бесспорным лидером по числу успешных попыток вскрытия блочных шифров.

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

3.2. Интегральный криптоанализ и другие виды атак

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

чивыми к этим атакам, в частности шифр «Квадрат» (Square) [12]. Но в процессе его разработки авторы придумали новую атаку и, чтобы обезопасить шифр от нее, вынуждены были увеличить рекомендуемое число раундов. Позднее под разными названиями аналогичные идеи появились в нескольких статьях, а обобщены были под названием интегральный криптоанализ [13].

При использовании интегрального криптоанализа исследуется то, как меняются свойства специальных мультимножеств при прохождении через раунды. Например, если мы установили, что множество, где каждый элемент встречается четное число раз, шифруется во множество с суммой, равной нулю после R — 1 раундов, то по аналогичной схеме из предыдущего раздела можно найти подключ последнего раунда.

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

Помимо трех наиболее распространенных типов криптоанализа: линейного, дифференциального и интегрального — существуют другие подходы к вскрытию шифров, но они пока не дали таких серьезных результатов, как описанные методы, поэтому приведем лишь их основные идеи. Все алгебраические атаки имеют общую цель — представить шифровальный алгоритм в виде системы уравнений, где подключи являются неизвестными, и разрешить. Достаточно многообещающим в последние годы становится подход, основанный на том, что при физической реализации различные операции, участвующие в шифровании, потребляют разную мощность или выполняются разное время. Устройства для подобных измерений уже производятся и имеют вполне приемлемую цену — от нескольких сотен до нескольких тысяч долларов. Эти измерения часто в комбинации с вышеупомянутыми теоретическими атаками позволяют эффективно отыскивать подключи. Еще один вид атак называется интерполяционным криптоанализом [14], где на основе уменьшенного количества раундов шифра с помощью интерполяционных многочленов (например, Лагранжа) строится приближение на большее число раундов или на весь шифр.

4. Конкурсы блочных шифров

Из-за востребованности шифрования информации и достаточно большого числа предложенных шифров были организованы несколько крупных конкурсов, направленных на стандартизацию или исследование с дальнейшей рекомендацией к применению блочных шифров. Наиболее значительным оказался проект A ES [5], ориентированный на поиск преемника DES как стандарта шифрования в США, а по сути и по всему миру. Требования к кандидатам были достаточно простыми: 128-битный блок, 128-, 192- и 256-битный секретный ключ, шифр должен по надежности не уступать 3-DES, но быть существенно быстрее него. На конкурс было подано порядка 20 заявок, из которых 15 шифров полностью соответствовали требованиям конкурса. После первого этапа были отобраны пять шифров, которые показали эффективную работу на различных платформах и хорошую надежность. Они исследовались еще более тщательно, но каких бы то ни было серьезных криптоаналитических результатов достигнуто не было и все шифры признались как «не имеющие недостатков». Однако по условиям конкурса выбрать нужно было только один шифр, и в результате голосования, в котором участвовали сие-

циалисты, исследовавшие шифры, победил бельгийский Rijdael [6] во многом благодаря прозрачностии и элегантности дизайна.

После этого конкурса было проведено еще два — NESSIE [15] (в Европе) и CRYPTREC [16] (в Японии), где исследовались не только блочные шифры, но и другие алгоритмы.

[1] Shannon С. Communication Theory of secrecy systems // Bell System Technical J. 1949. Vol. 28. P. 656-715.

[2] dlffle W., Hellman M. New directions in cryptography // IEEE Trans, on Information Theory. 1976. Vol. 22 (6). P. 644-654.

[3] Feistel H. Cryptography and computer privacy // Sei. American. 1973. Vol. 228, N 5. P. 15-23.

[4] National Bureau of Standards. Data encryption standard // Federal Information Proc. Standard (FIPS). 1977. Vol. 81.

блочное шифрование

Характерной чертой блочных шифров это обработка исходных данных по несколько бит, десятки сотки поблочно. Эти шифры есть логичным продолжением идеи алфавитных замен. В современных системах передачи, обработки и передачи данных двоичное представление данных разрешало достичь непостижимой абстракции формы от содержание. Любую информацию, будто графическую или музыкальную можно представить в виде последовательности битов. Любой блочный шифр в общем осмотре являет собой отображение многих входных блоков начального текста на много блоков зашифрованного текста. Это показано на рис.1. Блочный шифр — это шифр замены над очень большим алфавитом. Что бы показать только одно отображение над 64-битным блоком, нужно 64 × 2 64 = 2 70 бит запоминающего устройства. Количество бит в используемом блоке называют разрядностью блока, а количество бит в ключе — размер ключа алгоритма. Общий вид процесса шифрования: Z = EnCrypt(X, key); где Х — блок исходного текста, Key — ключ шифрования, Z — зашифрованный блок. Дешифрование происходит обратным образом. Основная идея всех блочных шифров есть то, что последовательность бит любой длины Q можно показать в виде натурального числа из диапазона [Q … 2 Q — 1].

Обратимые операции в блочном шифровании

Ясно, что для однозначного дешифрование данных на приемной стороне все преобразование должны быть обратными. И при этом ни на каком этапе процесса не должно быть потери данных. На рис.2 показано самые часто применяемые операции с их обозначениями в блочном шифровании.

С помощью табличных подстановок реализуют самые общие законы модификации данных, которые описываются не алгоритмически не аналитически. Такая подстановка имеет преимущество перед нелинейными операциями в плане быстродействия. Все приведенные операции на рис.1 кроме табличных подстановок и 2 N + 1 имеют линейную зависимость между выходными и входными значениями.

Необратимые операции в блочном шифровании

Когда от преобразования не нужно обратимости по входным характеристикам, такие операции показаны на рис.3.

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

Ниже описаны варианты элементов ИС использование блоковых шифров:

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL