Тест. Шифрование и хэширование

Основы криптографии – тест 5

Что является особенностью использования режима простой замены блочного шифра, определяемого ГОСТ 28147-89?

Что является особенностью использования режима простой замены блочного шифра, определяемого ГОСТ 28147-89?

Цифровая подпись на основе алгоритмов с открытым ключом

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

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

1. подпись воспроизводится только одним лицом, а подлинность ее может быть удостоверена многими;
2. подпись неразрывно связывается с данным сообщением и не может быть перенесена на другой документ;
3. после того, как документ подписан, его невозможно изменить;
4. от поставленной подписи невозможно отказаться, то есть лицо, подписавшее документ, не сможет потом утверждать, что не ставило подпись.

Асимметричные алгоритмы шифрования могут быть использованы для формирования цифровой (электронной) подписи (digital signature) – уникального числового дополнения к передаваемой информации, позволяющего проверить ее авторство. Электронная (цифровая) подпись (ЭЦП) представляет собой последовательность бит фиксированной длины, которая вычисляется определенным образом с помощью содержимого подписываемой информации и секретного ключа.

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

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

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

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

1. Пользователь А посылает пользователю Б свой открытый ключ U по любому каналу связи, например, по электронной почте.
2. Пользователь А шифрует сообщение М своим закрытым ключом R и получает зашифрованное сообщение С.
3. Зашифрованное сообщение пересылается пользователю Б.
4. Пользователь Б расшифровывает полученное сообщение С, используя открытый ключ пользователя А. Если сообщение расшифровалось, значит, оно подписано пользователем А.

Этот протокол можно изобразить в виде схемы, как на
рис.
9.2.

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

Физическое представление пары ключей зависит от конкретной системы, поддерживающей использование ЭЦП. Чаще всего ключ записывается в файл, который, в дополнение к самому ключу, может содержать, например, информацию о пользователе – владельце ключа, о сроке действия ключа, а также некий набор данных, необходимых для работы конкретной системы (подробнее об этом см.
“Электронная цифровая подпись”
).

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

На
рис.
9.2представлена схема формирования так называемой цифровой подписи с восстановлением документа. Цифровые подписи с восстановлением документа как бы содержат в себе подписываемый документ: в процессе проверки подписи автоматически вычисляется и тело документа.

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

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

К тому же практически все применяемые алгоритмы вычисления ЭЦП используют для расчета сообщения заранее заданной стандартной длины. Например, в российском алгоритме формирования цифровой подписи ГОСТ Р34.10-94 этот размер определен равным 32 байтам.

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

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

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

1. Пользователь А посылает пользователю Б свой открытый ключ U по любому каналу связи, например, по электронной почте.
2. Пользователь А с помощью некоторой надежной хеш-функции Н вычисляет хеш-код своего сообщения h = H(M).
3. Затем пользователь А шифрует хеш-код сообщения h своим закрытым ключом R и получает цифровую подпись С.
4. Исходное сообщение М вместе с цифровой подписью С пересылаются пользователю Б.
5. Пользователь Б вычисляет хеш-код h полученного сообщения М, а затем проверяет цифровую подпись С, используя открытый ключ пользователя А.

Этот протокол можно изобразить в виде схемы, как на
рис.
9.3.

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

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

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

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

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

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

Misty1

Блочный алгоритм шифрования, созданный на основе «вложенных» сетей Фейстеля 1995 году криптологом Мицуру Мацуи (Mitsuru Matsui) совместно с группой специалистов для компании Mitsubishi Electric. MISTY — это аббревиатура Mitsubishi Improved Security Technology, а также инициалы создателей алгоритма: в разработке алгоритма также приняли участие Тэцуя Итикава (Tetsuya Ichikawa)

MISTY1 — это сеть Фейстеля с изменчивым числом раундов (рекомендовано 8, но оно может быть любым, кратным 4). Алгоритм работает с 64-битными блоками и использует 128-битный ключ. Шифр стал победителем среди алгоритмов, шифрующих 64-битные блоки, на Европейском конкурсе NESSIE.

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

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

MISTY1 запатентованный алгоритм. Однако исконный владелец патента, Mitsubishi Electric, объявил, что будет выдавать лицензию на использование бесплатно.MISTY1 был разработан на основе теории «подтверждённой безопасности» против дифференциального и линейного криптоанализа. Этот алгоритм был спроектирован, чтобы противостоять различным криптоатакам, известным на момент создания.

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

Дифференциальный криптоанализ высокого порядка эффективно применяется к блочным шифрам с малой степенью. Мисти содержит 2 look-up таблицы S7 и S9, обе с малой ad, 3 и 2 соответственно. Поэтому достаточно много статей посвящены дифференциальному криптоанализу мисти.

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

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

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

Существует модификация данного алгоритма — MISTY2. Однако она не получила широкой известности вследствие низкого уровня криптостойкости.

Так же получила распространение модификация MISTY1 — алгоритм KASUMI — в 2000 году стал стандартом шифрования мобильной связи W-CDMA.

KASUMI (от японск.霞 (hiragana かすみ, romaji kasumi) — туман, mist) — блочный шифр, использующийся в сетях сотовой связи 3GPP. Также обозначается A5/3 при использовании в GSM и GEA3 в GPRS.

KASUMI разработан группой SAGE (Security Algorithms Group of Experts), которая является частью Европейского Института по Стандартизации в области Телекоммуникаций (ETSI). За основу был взят существующий алгоритм MISTY1 и оптимизирован для использования в сотовой связи.

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

Rabin

Этот алгоритм был опубликован в январе 1979 года Майклом О. Рабином. Криптосистема Рабина была первой асимметричной криптосистемой, в которой восстановление всего открытого текста из зашифрованного текста можно было доказать так же сильно, как факторинг.

Генерация ключа:

Выберем два больших разных числа p и q. Можно выбратьдля упрощения вычисления квадратных корней по модулю p и q (см. ниже). Но схема работает с любыми штрихами.Позволять , Тогда n является открытым ключом. Простые числа и являются закрытым ключом.Для шифрования сообщения необходим только открытый ключ . Чтобы расшифровать зашифрованный текст, необходимы факторы и , .

Генерация ключа

1. выбираются два случайных числа p и q с учётом следующих требований:
2. числа должны быть большими (см. разрядность);
3. числа должны быть простыми;
4. должно выполняться условие:.

Выполнение этих требований сильно ускоряет процедуру извлечения корней по модулю р и q;

вычисляется число

1. число n — открытый ключ;
2. числа p и q — закрытый.

ШифрованиеИсходное сообщение m (текст) шифруется с помощью открытого ключа — числа n по следующей формуле:
Благодаря использованию умножения по модулю скорость шифрования системы Рабина больше, чем скорость шифрования по методу RSA, даже если в последнем случае выбрать небольшое значение экспоненты.

Расшифровка Для расшифровки сообщения необходим закрытый ключ — числа p и q. Процесс расшифровки выглядит следующим образом:

1. Сначала, используя алгоритм Евклида, из уравнения находят числа и ;
2. далее, используя китайскую теорему об остатках, вычисляют четыре числа:

   

Одно из этих чисел является истинным открытым текстом m.

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

P.P.S. Была идея также сделать Сравнительную таблицу, но для начала хотелось бы узнать, по каким именно параметрам Вы хотели бы увидеть сравнение.

P.P.P.S Для статейного конкурса «Нетологии», Ссылка на сайт, Ссылка на блог.

Safer

Семейство симметричных блочных криптоалгоритмов на основе подстановочно-перестановочной сети. Основной вклад в разработку алгоритмов внёс Джеймс Мэсси. Первый вариант шифра был создан и опубликован в 1993 году.

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

Первая разновидность алгоритма — SAFER K-64 была разработана Джэймсом Мэсси для калифорнийской корпорации «Cylinc» в 1993 году. Опубликованный в том же году, алгоритм имел блок и ключ шифрования длиной в 64 бита. Для него рекомендовалось использовать 6 раундов шифрования.

Однако, из-за необходимости увеличить длину ключа до 128 бит (так как была обнаружена слабость в первоначальном варианте алгоритма), Мэсси разработал новый вариант шифра SAFER K-128, который был опубликован на следующий год после SAFER K-64. Новый алгоритм включал в себя расписание ключей, разработанное министерством внутренних дел Сингапура, и в дальнейшем использовался им для различных целей. Также для этого алгоритма рекомендовалось использовать 10 (максимум 12) раундов шифрования.

Спустя некоторое время в первых вариантах алгоритма выявились некоторые слабости, обнаруженные Ларсом Кнудсеном и Шоном Мёрфи. Это повлекло за собой создание новых версий алгоритма, названных SAFER SK-64 и SAFER SK-128, в которых расписание ключей было изменено в соответствии со схемой, предложенной Кнудсеном.

Также был разработан вариант с длиной ключа, уменьшенной до 40 бит — SAFER SK-40. Сокращение «SK» в названии алгоритмов расшифровывается как «Strengthened Key schedule» (Усиленное расписание ключей). Для новых вариантов шифра предлагалось использовать не 6, а по крайней мере 8 (максимум 10) раундов шифрования.

Алгоритм SAFER был разработан в 1998 году калифорнийской корпорацией Cylinc совместно с Армянской академией наук для участия в конкурсе AES, на котором прошёл лишь первый отборочный тур. Данный шифр имеет входной блок длиной 128 бит и размер ключа 128, 192 или 256 бит.

Последней из созданных разновидностей алгоритма SAFER является SAFER , разработанный Мэсси в 2000 году и ставший дальнейшим развитием алгоритма SAFER . Алгоритм принял участие в европейском конкурсе алгоритмов NESSIE, где был представлен в двух вариантах:

шифр с 64-битным блоком и 128-битным блоком. Он прошёл во вторую фазу конкурса, но не был выбран в набор рекомендуемых NESSIE криптографических примитивов. Эксперты сочли, что шифр слишком медленный на всех машинах, кроме 8-битных (таких как смарт-карты), а запас безопасности шифра слишком мал.

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

Skipjack

Блочный шифр, разработанный Агентством национальной безопасности США в рамках проекта Capstone[en]. После разработки сведения о шифре были засекречены. Изначально он предназначался для использования в чипе Clipper для защиты аудио информации, передаваемой по сетям правительственной телефонной связи, а также по сетям мобильной и беспроводной связи. Позже алгоритм был рассекречен.

Skipjack являлся одной из инициатив, предложенных в рамках проекта Capstone. Руководили проектом Агентство национальной безопасности (АНБ) и Национальный институт стандартов и технологий (НИСТ), финансируемые правительством США. Официальная дата начала инициативы — 1993 год.

Алгоритм шифрования был разработан в 1980 году, а первая его реализация была получена в 1987 году. Шифр был предназначен для использования в чипе Clipper, встраиваемом в защищаемое оборудование. При этом Skipjack использовался только для шифрования сообщений, а депонирование ключа для возможности последующего использования уполномоченными органами — наиболее обсуждаемый аспект использования шифра — достигалось за счёт отдельного механизма, называемого Law Enforcement Access Field.

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

1. Принимая во внимание, что стоимость вычислительных мощностей уменьшается вдвое каждые 18 месяцев, лишь через 36 лет стоимость взлома Skipjack полным перебором сравняется со стоимостью взлома DES сегодня.
2. Риск взлома шифра с помощью более быстрых способов, включая дифференциальный криптоанализ, незначителен. Алгоритм не имеет слабых ключей и свойства комплементарности.
3. Устойчивость Skipjack к криптоанализу не зависит от секретности самого алгоритма.

Шифр был опубликован в открытый доступ 24 июня 1998 года. В августе 2021 года НИСТ принял новые принципы использования криптографических стандартов, в которых отозвал сертификацию алгоритма Skipjack для правительственных целей.

Skipjack использует 80-битный ключ для шифрования/дешифрования 64-битных блоков данных. Это несбалансированная сеть Фейстеля с 32 раундами.

Twofish

Симметричный алгоритм блочного шифрования с размером блока 128 бит и длиной ключа до 256 бит. Число раундов 16. Разработан группой специалистов во главе с Брюсом Шнайером. Являлся одним из пяти финалистов второго этапа конкурса AES. Алгоритм разработан на основе алгоритмов Blowfish, SAFER и Square.

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

Twofish разрабатывался специально с учетом требований и рекомендаций NIST для AES:

1. 128-битный блочный симметричный шифр
2. Длина ключей 128, 192 и 256 бит
3. Отсутствие слабых ключей
4. Эффективная программная (в первую очередь на 32-битных процессорах) и аппаратная реализация
5. Гибкость (возможность использования дополнительных длин ключа, использование в поточном шифровании, хэш-функциях и т. д.).
6. Простота алгоритма — для возможности его эффективного анализа.

Алгоритм Twofish возник в результате попытки модифицировать алгоритм Blowfish для 128-битового входного блока. Новый алгоритм должен был быть легко реализуемым аппаратно (в том числе использовать таблицы меньшего размера), иметь более совершенную систему расширения ключа (key schedule) и иметь однозначную функцию F.

В результате, алгоритм был реализован в виде смешанной сети Фейстеля с четырьмя ветвями, которые модифицируют друг друга с использованием криптопреобразования Адамара (Pseudo-Hadamar Transform, PHT).

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

Например, в функции F при вычислении PHT и сложении с частью ключа K намеренно используется сложение, вместо традиционного xor. Это дает возможность использовать команду LEA семейства процессоров Pentium, которая за один такт позволяет вычислить преобразование Адамара (Правда в таком случае код приходится компилировать под конкретное значение ключа).
Алгоритм Twofish не запатентован и может быть использован кем угодно без какой-либо платы или отчислений. Он используется во многих программах шифрования, хотя и получил меньшее распространение, чем Blowfish.