Алгоритм шифрования данных ГОСТ 28147-89


Содержание

Отечественный стандарт шифрования данных ГОСТ 28147-89

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

  1. CALS-технологии — основная концепция разработки удаленных баз данных
  2. ERP-стандарты и соответствующие им методики управления и планирования
  3. II Качество и конкурентоспособность. Стандарты и системы качества
  4. L Довідники міжнародного стандарту
  5. L Стандартні повідомлення
  6. Абстрактные структуры данных
  7. Административные регламенты и стандарты
  8. Администрирование баз данных
  9. Активные базы данных
  10. Алгоритм шифрования RSA
  11. Анализ прибыли и рентабельности с использованием международных стандартов
  12. Анализ радиологических данных, с последующим сопоставлением с данными морфологических исследований должен стать привычкой.

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

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

Стандарт шифрования ГОСТ 28147-89 предусматривает шифрова­ние и расшифровку данных в следую­щих режимах работа:

О простая замена;

U гаммирование с обратной связью;

О выработка имитовставки.

Структурная схема алгоритма криптопреобразования, выполненного по ГОСТ 28147-89, изображена на рис. 4.16. Эта схема состоит из:

Q сумматоров по модулю 2 — СМ2 иСМ5;

Q сумматоров по модулю 232 — СМ1иСМЗ;

Q сумматора по модулю 232-1 — СМ4;

О накопителей с константами С1 и С2 — Н6 и Н5, соответственно;

Q основных 32-разрядных накопи­телей HI и Н2;

Q вспомогательных 32-разрядных накопителей НЗ и Н4;

Q ключевого запоминающего устройства КЗУ;

Q блока подстановки К;

СИ регистра циклического сдвига R.

Сумматоры по модулю 2 обеспечивают сложение по модулю 2 поступающих на их входы данных, представленных в двоичном виде.

Сумматоры по модулю 232 выполняют операцию суммирования по модулю 232 двух 32-разрядных чисел по правилу:

А[+]В = А + В, если А + В 232.

Сумматор по модулю 232-1 выполняет операцию суммирования по модулю 232-1 двух 32-разрядных чисел по правилу:

А[+]В = А + В, если А + В 232-1.

Накопители с константами Н6 и Н5 содержат 32-разрядные константы, соответ­ственно,

Основные 32-разрядные накопители служат для обеспечения всех режимов работы алгоритма.

Вспомогательные 32-разрядные накопители используются для обеспечения рабо­ты алгоритма в режиме гаммирования.

Ключевое запоминающее устройство предназначено для формирования ключевой последовательности W длиной 256 бит, представленной в виде восьми 32-разрядных чисел Xi (табл. 4.4) [i = 0( 1 )7]. Последовательность W = UXi = XO U X1 U. U X7, где U — знак объединения множеств.

Таблица 4.4. Числа, формирующие ключевую последовательность

Хо ».-
X, ..*
Х2 ».-
Х3 «••
Х4 • ••
Х5 • ••
Хб • • •
Х7 *••

Блок подстановки осуществляет дополнительное к ключевой последовательности шифрование передаваемых данных с помощью таблиц замен. Он состоит из восьми узлов замены К1, . , К8. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательных 4-разрядных векторов (слов), каждый из которых преобразуется в 4-разрядный вектор соответствующим узлом замены. Узел замены представляет собой таблицу из 16-и строк по 4 бита в каждой (рис. 4.17).

Входной вектор определяет адрес строки в таблице замены, а заполнение является выходным вектором. Затем выходные 4-разрядные векторы объединяются в один 32-разрядный вектор. Принцип работы блока подстановки рассмотрим на примере, пред­ставленном на рис. 4.18.

Пусть имеется блок данных с заполнением 0110. В десятичной системе счисления заполнение 0110 соответствует числу 6. По таблице замен находим строку с номером 6. Результатом является заполнение 0101, соответствующее узлу замены К1.

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

Регистр циклического сдвига R предназначен для осуществления операции цикли­ческого сдвига шифруемых данных на 11 разрядов в сторону старших разрядов в виде:

R(r32, r31. г2, г!) — (г21, г20. rl, г32. г22)

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

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

| следующая лекция ==>
Перспективный стандарт AES | Режим гаммирования

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

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

Алгоритм шифрования данных ГОСТ 28147-89

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля. Выделяют четыре режима работы ГОСТ 28147-89:

Режим простой замены

Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты — A, старшие биты — B [2] ). На i-ом цикле используется подключ Ki:

( = двоичное «исключающее или»)

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8.

Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим). Ключи K25…K32 являются ключами K8…K1.

После выполнения всех 32 раундов алгоритма, блоки A33 и B33 склеиваются (обратите внимание, что старшим битом становится A33, а младшим — B33) — результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей Ki.

Функция вычисляется следующим образом:

Ai и Ki складываются по модулю 2 32 .

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Режим простой замены имеет следующие недостатки:

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

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

Гаммирование

При работе ГОСТ 28147-89 в режиме гаммирования специальным образом формируется криптографическая гамма, которая затем складывается по модулю 2 с исходным открытым текстом для получения шифротекста. Шифрование в режиме гаммирования лишено недостатков, присущих режиму простой замены. Так, даже идентичные блоки исходного текста дают разный шифротекст, а для текстов с длиной, не кратной 64 бит, «лишние» биты гаммы отбрасываются.

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

  1. Синхропосылка шифруется с использованием описанного алгоритма простой замены, полученные значения записываются в N3 и N4 — младшие и старшие биты соответственно.
  2. К N3 и N4 прибавляются константы соответственно C2 = 101010116 и C1 = 101010416
  3. N3 и N4 переписываются соответственно в N1 и N2, которые затем шифруются и использованием алгоритма простой замены. Полученный результат является 64 битами гаммы.
  4. Шаги 2-4 повторяются в соответствии с длиной шифруемого текста.

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

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

Гаммирование с обратной связью

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

Алгоритм шифрования следующий:

  1. Синхропосылка заносится в регистры N1 и N2
  2. Содержимое регистров N1 и N2 шифруется в соответствии с алгоритмом простой замены. Полученный результат является 64-битным блоком гаммы.
  3. Блок гаммы складывается по модулю 2 с блоком открытого текста. Полученный шифротекст заносится в регистры N1 и N2
  4. Операции 2-3 выполняются для оставшихся блоков требующего шифрования текста.

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

Режим выработки имитовставки

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

Имитовставка вырабатывается для M ≥ 2 блоков открытого текста по 64 бит. Алгоритм следующий:

  1. Блок открытых данных записывается в регистры N1 и N2, после чего подвергается преобразованию, соответствующему первым 16 циклам шифрования в режиме простой замены
  2. К полученному результату по модулю 2 прибавляется следующий блок открытых данных. Последний блок при необходимости дополняется нулями. Сумма также шифруется в соответствии с пунктом 1.
  3. После добавления и шифрования последнего блока из результата выбирается имитовставка длиной L бит: с бита номер 32-L до 32(отсчет начинается с 1). Стандарт рекомендует выбирать L исходя из того, что вероятность навязывания ложных данных равна 2 -L . Имитовставка передается по каналу связи после зашифрованных блоков.

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

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

Узлы замены (S-блоки)

Все восемь S-блоков могут быть различными. Некоторые считают, что они могут являться дополнительным ключевым материалом, увеличивающим эффективную длину ключа; однако существуют применимые на практике атаки, позволяющие их определить. [3] Впрочем, и необходимости в увеличении длины ключа нет, 256 бит вполне достаточно в настоящее время. Как правило, таблицы замен являются долговременным параметром схемы, общим для определенной группы пользователей. В ГОСТ Р 34.11-94 для целей тестирования приведены следующие S-блоки:

Номер S-блока Значение
1 4 10 9 2 13 8 14 6 11 1 12 7 15 5 3
2 14 11 4 12 6 13 15 10 2 3 8 1 7 5 9
3 5 8 1 13 10 3 4 2 14 15 12 7 6 9 11
4 7 13 10 1 8 9 15 14 4 6 12 11 2 5 3
5 6 12 7 1 5 15 13 8 4 10 9 14 3 11 2
6 4 11 10 7 2 1 13 3 6 8 5 9 12 15 14
7 13 11 4 1 3 15 5 9 10 14 7 6 8 2 12
8 1 15 13 5 7 10 4 9 2 3 14 6 11 8 12

Данный набор S-блоков используется в криптографических приложениях ЦБ РФ. [4]

В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, то есть разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет узлы замены, см. RFC 4357.

Достоинства ГОСТа

  • бесперспективность силовой атаки (XSL-атаки в учёт не берутся, так как их эффективность на данный момент полностью не доказана);
  • эффективность реализации и соответственно высокое быстродействие на современных компьютерах.
  • наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

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

Считается (см. например Vitaly V. Shorin, Vadim V. Jelezniakov and Ernst M. Gabidulin: Linear and Differential Cryptanalysis of Russian GOST), что ГОСТ устойчив к таким широко применяемым методам, как линейный и дифференциальный криптоанализ. Обратный порядок использования ключей в последних восьми раундах обеспечивает защиту от атак скольжения(slide attack) и отражения(reflection attack).

В мае 2011 года известный криптоаналитик Николя Куртуа доказал существование атаки на данный шифр, имеющей сложность в 2 8 (256) раз меньше сложности прямого перебора ключей при условии наличия 2 64 пар открытый текст/закрытый текст. [5] [6] Данная атака не может быть осуществлена на практике ввиду слишком высокой вычислительной сложности. Более того, знание 2 64 пар открытый текст/закрытый текст, очевидно, позволяет читать зашифрованные тексты, даже не вычисляя ключа. В большинстве других работ также описываются атаки, применимые только при некоторых предположениях, таких как определенный вид ключей или таблиц замен, некоторая модификация исходного алгоритма, или же требующие все еще недостижимых объемов памяти или вычислений. Вопрос о наличии применимых на практике атак без использования слабости отдельных ключей или таблиц замены остается открытым.

Критика ГОСТа

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

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

В октябре 2010 года на заседании 1-го объединенного технического комитета Международной организации по стандартизации (ISO/IEC JTC 1/SC 27) ГОСТ был выдвинут на включение в международный стандарт блочного шифрования ISO/IEC 18033-3. В связи с этим в январе 2011 года были сформированы фиксированные наборы узлов замены и проанализированы их криптографические свойства. Однако ГОСТ не был принят в качестве стандарта, и соответствующие таблицы замен не были опубликованы [7]

Возможные применения

  • Использование в S/MIME (PKCS#7, Cryptographic Message Syntax). [8]
  • Использование для защиты соединений в TLS (SSL, HTTPS, WEB). [9]
  • Использование для защиты сообщений в XML Encryption. [10]

Примечания

  1. А. Винокуров. Алгоритм шифрования ГОСТ 28147-89, его использование и реализация для компьютеров платформы Intel x86
  2. В описании стандарта ГОСТ обозначены как N1 и N2 соответственно
  3. Панасенко С. П. Стандарт шифрования ГОСТ 28147-89
  4. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си, 2-е издание — М.: Триумф, 2002, 14.1
  5. Nicolas T. Courtois. Security Evaluation of GOST 28147-89 In View Of International Standardisation. Cryptology ePrint Archive: Report 2011/211
  6. SecurityLab: Взломан блочный шифр ГОСТ 28147-89
  7. Технический комитет по стандартизации (ТК 26) «Криптографическая защита информации» О деятельности по международной стандартизации алгоритма шифрования ГОСТ 28147-89
  8. Leontiev S., Chudov G.Using the GOST 28147-89, GOST R 34.11-94, GOST R 34.10-94, and GOST R 34.10-2001 Algorithms with Cryptographic Message Syntax (CMS) (англ.) (May 2006). — RFC 4490. Архивировано из первоисточника 24 августа 2011.Проверено 21 июня 2009.
  9. Leontiev, S., Ed. and G. Chudov, Ed.GOST 28147-89 Cipher Suites for Transport Layer Security (TLS) (англ.) (December 2008). — Internet-Drafts, work in progress. Архивировано из первоисточника 24 августа 2011.Проверено 21 июня 2009.
  10. S. Leontiev, P. Smirnov, A. Chelpanov Using GOST 28147-89, GOST R 34.10-2001, and GOST R 34.11-94 Algorithms for XML Security (англ.) (December 2008). — Internet-Drafts, work in progress. Архивировано из первоисточника 24 августа 2011.Проверено 21 июня 2009.

См. также

Ссылки

  • ГОСТ 28147—89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования»
  • Сергей ПанасенкоСтандарт шифрования ГОСТ 28147-89 (рус.) (15 августа 2007). Проверено 3 августа 2012.
  • Сайт об алгоритме шифрования ГОСТ 28147-89
  • ГОСТы для OpenSSL. — криптографический проект компании ООО «Криптоком» по добавлению российских криптографических алгоритмов в библиотеку OpenSSL. Архивировано из первоисточника 24 августа 2011.Проверено 16 ноября 2008.

Стандарт шифрования ГОСТ 28147-89

Алгоритм криптографического преобразования данных предназначен для аппаратной и программной реализации, удовлетворяет криптографическим требованиям и не накладывает ограничений на степень секретности защищаемой информации. Алгоритм шифрования данных, определяемый ГОСТ 28147-89, представляет собой 64-битный блочный алгоритм с 256-битным ключом. Данные, подлежащие зашифрованию, разбивают на 64-разрядные блоки. Эти блоки разбиваются на два субблока N1 и N2 по 32 бит (рис. 4.7).

Рис. 4.7. Схема алгоритма ГОСТ 28147-89

Субблок N1 обрабатывается определенным образом, после чего его значение складывается со значением субблока N2 (сложение выполняется по модулю 2, то есть применяется логическая операция XOR – исключающее ИЛИ), а затем субблоки меняются местами. Данное преобразование выполняется определенное число раз (раундов): 16 или 32 в зависимости от режима работы алгоритма.

В каждом раунде выполняются две операции:

¨ наложение ключа – содержимое субблока N1 складывается по модулю 2 32 с 32-битной частью ключа . Полный ключ шифрования представ­ляется в виде конкатенации 32-битных подключей: К0, К1, К2, КЗ, К4, К5, К6, К7. В процессе шифрования используется один из этих подключей – в зависимости от номера раунда и режима работы алгоритма.

¨ табличная замена – после наложения ключа субблок N1 разбивается на 8 частей по 4 бит, значение каждой из которых заменяется в соответствии с таблицей замены для данной части субблока. Затем выполняется побитный циклический сдвиг субблока влево на 11 бит.

Табличные замены. Блок подстановки S-box состоит из восьми узлов замены (S-блоков замены) S1, S2, . S8 с памятью 64 бит каждый. Поступающий на блок подстановки S 32-битный вектор разбивают на восемь последовательно идущих 4-битных векторов, каждый из которых преобразуется в 4-битный вектор соответствующим узлом замены. Каждый узел замены можно представить в виде таблицы-перестановки шестнадцати 4-битных двоичных чисел в диапазоне 0000÷1111. Входной вектор указывает адрес строки в таблице, а число в этой строке является выходным вектором. Затем 4-битные выходные векторы последовательно объединяют в 32-битный вектор. Узлы замены (таблицы-перестановки) представляют собой ключевые элементы, которые являются общими для сети ЭВМ и редко изменяются. Эти узлы замены должны сохраняться в секрете.

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

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

Расшифрование в данном режиме проводится точно так же, но с несколько другой последовательностью применения подключей:

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

В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 с блоком гаммы шифра размером 64 бит. Гамма шифра – это специальная последовательность, которая получается в результате определенных операций с регистрами N1 и N2 (рис. 4.8):

1. В регистры N1 и N2 записывается их начальное заполнение – 64-битная величина, называемая синхропосылкой.

2. Выполняется зашифрование содержимого регистров N1 и N2 (в данном случае синхропосылки) в режиме простой замены.

3. Содержимое регистра N1 складывается по модулю (2 32 — 1) с константой С1 = 2 24 + 2 16 + 2 8 + 2 4 , а результат сложения записывается в регистр N1.

4. Содержимое регистра N2 складывается по модулю 2 32 с константой С2 = 2 24 + 2 16 + 2 8 + 1, а результат сложения записывается в регистр N2.

5. Содержимое регистров N1 и N2 подается на выход в качестве 64-битного блока гаммы шифра (в данном случае N1 и N2 образуют первый блок гаммы).

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

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

Рис. 4.8. Выработка гаммы шифра в режиме гаммирования с обратной связью

Таблица 4.3. Пример зашифрования и расшифрования в режиме гаммирования

Операция Результат
Исходный текст
Гамма XOR
Шифртекст =
Гамма XOR
Исходный текст =

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

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

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

В режиме генерации имитоприставок генерируется имитоприставка. Имитоприставка – это криптографическая контрольная сумма, вычисляемая с использованием ключа шифрования и предназначенная для проверки целостности сообщений. При генерации имитоприставки выполняются следующие операции: первый 64-битный блок массива информации, для которого вычисляется имитоприставка, записывается в регистры N1 и N2 и зашифровыва­ется в сокращенном режиме простой замены (выполняются первые 16 раундов из 32). Полученный результат суммируется по модулю 2 со следующим блоком информации с сохранением результата в N1 и N2.

Цикл повторяется до последнего блока информации. Получившееся в результате этих преобразований 64-битное содержимое регистров N1 и N2 или его часть и называется имитоприставкой. Размер имитоприставки выбирается, исходя из требуемой достоверности сообщений: при длине имитоприставки r бит вероятность, что изменение сообщения останется незамеченным, равна 2 — r .

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

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

Алгоритм ГОСТ 28147-89 считается очень стойким – в настоящее время для его раскрытия не предложено более эффективных методов, чем упомянутый выше метод «грубой силы». Его высокая стойкость достигается в первую очередь за счет большой длины ключа – 256 бит. При использовании секретной синхропосылки эффективная длина ключа увеличивается до 320 бит, а засекречивание таблицы замен прибавляет дополнительные биты. Кроме того, криптостойкость зависит от количества раундов преобразований, которых по ГОСТ 28147-89 должно быть 32 (полный эффект рассеивания входных данных достигается уже после 8 раундов).

Стандарт шифрования AES

Криптоалгорит AES обладает следующими свойствами:

¨ алгоритм является симметричным;

¨ алгоритм является блочным шифром;

¨ алгоритм имеет длину блока 128 бит и поддерживать три длины ключа: 128, 192 и 256 бит.

¨ алгоритм использует операции, реализуемые как аппаратно (в микрочипах), так и программно (на персональных компьютерах и серверах);

¨ алгоритм ориентироваться на 32-разрядные процессоры;

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

В отличие от отечественного стандарта шифрования ГОСТ 28147-89, алгоритм AES представляет каждый блок обрабатываемых данных в виде двухмерного байтного массива размером 4´4, 4´6 или 4´8 в зависимости от установленной длины блока. Далее на соответствующих этапах производятся преобразования либо над независимыми столбцами, либо над независимыми строками, либо вообще над отдельными байтами.

Алгоритм AES состоит из определенного количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа) и выполняет четыре преобразования:

¨ BS (ByteSub) – табличная замена каждого байта массива (рис. 4.9). Преобразование BS является нелинейной байтовой подстановкой которая воздействует независимо на каждый байт массива, используя таблицу замен (подстановок) S-box;

¨ SR (ShiftRow) – сдвиг строк массива (рис. 4.10). При этой операции первая строка остается без изменений, а остальные циклически побайтно сдвигаются влево на фиксированное число байтов, зависящее от размера массива. Например, для массива размером 4´4 строки 2, 3 и 4 сдвигаются соответственно на 1, 2 и 3 байта;

¨ МС (MixColumn) – операция над независимыми столбцами массива (рис. 4.11) – каждый столбец по определенному правилу умножается на фиксированную матрицу с(х);

¨ АК (AddRoundKey) – добавление ключа. Каждый бит массива складывается по модулю 2 с соответствующим битом ключа раунда, который, в свою очередь, определенным образом вычисляется из ключа шифрования (рис. 4.12).

Рис. 4.9. Преобразование BS (ByteSub) использует таблицу замен

(подстановок) для обработки каждого байта массива State

Рис. 4.10. Преобразование SR (ShiftRow) циклически сдвигает

три последних строки в массиве State

Рис. 4.11. Преобразование МС (MixColumn) поочередно обрабатывает

столбцы массива State

Рис. 4.12. Преобразование АК (AddRoundKey) производит сложение XOR


каждого столбца массива State со словом из ключевого набора

В каждом раунде над шифруемыми данными поочередно выполняются перечисленные преобразования (рис. 4.13). Исключения касаются первого и последнего раундов: перед первым раундом дополнительно выполняется операция АК, а в последнем раунде отсутствует МС.

Рис. 4.13. Раунд алгоритма AES

В результате последовательность операций при зашифровании выглядит так: АК, (повторяется R — 1 раз), BS, SR, АК.

Количество раундов шифрования R в алгоритме AES переменное (10, 12 или 14 раундов) и зависит от размеров блока и ключа шифрования (для ключа также предусмотрено несколько фиксированных размеров).

Расшифрование выполняется с помощью следующих обратных операций:

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

2. Обратной операцией к SR является циклический сдвиг строк вправо.

3. Обратная операция для МС – умножение по тем же правилам на другую матрицу d(x), удовлетворяющую условию с(х) * d(x) = 1.

4. Добавление ключа АК является обратным самому себе, поскольку в нем используется только операция XOR.

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

Алгоритм имеет ряду преимуществ перед другими алгоритмами:

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

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

Недостатком алгоритма AES – нетрадиционную плохо исследованную схему (в отличие от традиционных алгоритмов), поэтому он может содержать скрытые уязвимости, которые могут обнаружиться только по прошествии какого-то времени с момента начала его широкого распространения.

Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰).

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

Алгоритм шифрования данных ГОСТ 28147-89

В последние годы появляется большое количество статей, посвященных анализу российского алгоритма блокового («блочного») шифрования ГОСТ 28147-89 (см. [ГОСТ]). Одновременно с этим в российских СМИ и блогах российских пользователей растет число заметок о данном алгоритме: как освещающих различной степени достоверности результаты атак на российский стандарт, так и содержащих мнения о его эксплуатационных характеристиках. У авторов (а, следовательно, и читателей) данных заметок зачастую складывается впечатление, что отечественный алгоритм шифрования является морально устаревшим, медленным и обладающим уязвимостями, делающими его подверженным атакам в существенной мере больше, чем зарубежные алгоритмы шифрования с аналогичной длиной ключа. Данной серией заметок мы хотели бы в доступной форме рассказать о настоящем положении дел с российским стандартом. В первой части будут освещены все известные международной криптографической общественности атаки на ГОСТ 28147-89, текущие оценки его стойкости. В будущих публикациях мы также подробно рассмотрим свойства стандарта с точки зрения возможности построения эффективных реализаций.

Николя Куртуа – «великий и ужасный»

Начнем с рассказа о деятельности Николя Куртуа, который является автором целого цикла работ, посвященных российскому стандарту блокового шифрования ([Cour1-Cour5]).

В октябре 2010 года был начат процесс рассмотрения вопроса о включении алгоритма ГОСТ 28147-89 в международный стандарт ISO/IEC 18033-3. Уже в мае 2011 года на электронном архиве ePrint появилась статья известного криптографа Николя Куртуа [Cour1], отмеченного весьма неоднозначным отношением к нему мирового криптографического сообщества. Публикации Куртуа представляют собой печальный пример манипулирования понятиями, которое не открывает никаких новых свойств рассматриваемого объекта, но с претензией на сенсацию провоцирует распространение в некомпетентной среде ошибочных мнений о его действительных свойствах.

Эта, а также последующие ([Cour2-Cour6]) посвященные ГОСТ 28147-89 статьи Куртуа имеют крайне сходную структуру. В аннотации и введении содержится насыщенный эпитетами текст о том, насколько ужасающе слабым оказался российский стандарт блокового шифрования, как легко было построить на него атаку и как катастрофично было положение наивного комитета ISO, который, практически находясь на краю пропасти, чуть было не принял столь уязвимый российский стандарт в качестве международного. Далее присутствуют несколько оценок трудоемкости атак Куртуа, существенно меньших априорной (трудоемкости полного перебора ключей) 2 256 , несколько слов о недальновидности международного криптографического сообщества, в очередной раз отвергнувшего очередную его работу, а дальше… дальше идет основное содержание работы, в котором дошедший до него читатель (а не журналист, радостно закрывший статью, чтобы мгновенно поделиться с миром новостью о тотальных уязвимостях в российском стандарте), к своему удивлению, не находит ничего похожего на строгий научный текст с обоснованиями атак: вместо повествования, построенного по принципу «утверждение-доказательство», в работах присутствуют «факты» и комментарии к этим фактам. В качестве обоснования этих фактов приводятся, в лучшем случае, правдоподобные рассуждения, но никак не строгие доказательства. В заключениях работ содержится еще один яркий фрагмент текста о совершенной неожиданности обнаружения столь существенных слабостей в блоковом шифре, разработанном в недрах лабораторий могучего КГБ СССР.

«It appears that also that it is for the first time in history that a major standardized block cipher intended to provide a military-grade level of security and intended to protect also classified and secret documents, for the government, large banks and other organisations, is broken by a mathematical attack.» [Cour1]

Алгебраический метод

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

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

Алгебраический метод, эксплуатируемый Куртуа, коротко можно описать так. На первом этапе используются такие свойства ГОСТ 28147-89, как существование неподвижной точки для части шифрующего преобразования, а также так называемой точки отражения (reflection point). Благодаря этим свойствам из достаточно большого количества пар открытых-шифрованных текстов выбирается несколько пар, которые позволяют рассматривать преобразования не на 32, а лишь на 8 раундах. Второй этап состоит в том, что по полученным на первом этапе результатам 8-ми раундовых преобразований строится система нелинейных уравнений, неизвестными в которой являются биты ключа. Далее эта система решается (это звучит просто, но в действительности является самой трудоемкой частью метода, т.к. система состоит из нелинейных уравнений).

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

Дифференциальный метод

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

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

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

Куртуа использует несколько модифицированный вариант дифференциального метода. Сразу же отметим, что свой анализ Куртуа проводит для S-блоков, отличных от действующих и от предложенных в ISO. В работе приводятся дифференциальные характеристики (те самые номера, в которых должны отличаться блоки) для малого числа раундов. Обоснование продления характеристик на большее число раундов, как водится, основано на «фактах». Куртуа высказывает, опять же, ничем, кроме его авторитета, не подкрепленное предположение, что изменение S-блоков не повлияет на стойкость ГОСТ 28147-89 против его атаки (при этом по непонятным причинам S-блоки из 1-го рабочего проекта дополнения к стандарту ISO/IEC 18033-3 не рассматривались). Анализ, проведенный авторами статьи [Rud2], показывает, что даже если принять на веру необоснованные «факты» Куртуа и провести анализ ГОСТ 28147-89 с другими S-блоками, то атака опять же оказывается не лучше полного перебора.

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

Детальный анализ работ Куртуа с подробным обоснованием беспочвенности всех утверждений о снижении стойкости российского стандарта был проведен в работах [Rud2, Руд2].

При этом абсолютное отсутствие аккуратности выкладок признает даже сам Куртуа! Следующий слайд взят из презентации Куртуа на секции коротких объявлений FSE 2012.

Необходимо отметить, что работы Куртуа неоднократно критиковались также и зарубежными исследователями. Например, его работы по построению атак на алгоритм блокового шифрования AES с помощью XSL-метода содержали те же принципиальные недоработки, что и работы по анализу российского стандарта: большинство оценок трудоемкости появляется в тексте совершенно безосновательно и бездоказательно – подробную критику можно найти, например, в работе [Cid]. Кроме того, сам Куртуа признает повсеместные отказы в публикации его работ на крупных криптографических конференциях и в признанных рецензируемых журналах, оставлявшие ему зачастую лишь возможность выступить на секции коротких объявлений. Об этом, например, можно прочитать в разделе 3 работы [Cour4]. Вот некоторые цитаты, приводимые самим Куртуа и относящиеся к его работам:

  • «I think that the audiences of Asiacrypt will not feel it is interesting». Рецензент Asiacrypt 2011.
  • «… there is a big, big, big problem: this attack, which is the main contribution of the paper has already been published at FSE’11 (it was even the best paper), …». Рецензент Crypto 2011.

Таким образом, профессиональная часть международной криптографической общественности относится к качеству работ Куртуа с не меньшим сомнением, чем, скажем, к не подтвержденным никакими последовательными выкладками заявлениям некоторых российских специалистов об их умении взламывать AES за 2 100 или к очередным «доказательствам» на две страницы гипотезы о неравенстве сложностных классов P и NP.

Атаки Исобе и Динура-Данкельмана-Шамира

Общая идея атак Исобе ([Isobe]) и Динура-Данкельмана-Шамира (далее: атака ДДШ) ([DDS]) заключается в построении для определенного (зависящего от ключа) узкого множества открытых текстов эквивалентного на этом множестве преобразования, имеющего более простую, чем само шифрующее преобразование, структуру. В случае метода Исобе это множество таких 64-битных блоков x, что F8 -1 (Swap(F8(z))) = z, где z = F16(x), через F8(x) и F16(x) обозначены первые 8 и первые 16 раундов шифрования ГОСТ 28147-89 соответственно, через Swap – операция обмена местами половинок 64-байтового слова. При попадании открытого текста в это множество результат полного 32-раундового преобразования ГОСТ 28147-89 совпадает с результатом 16-раундового, что и эксплуатируется автором атаки. В случае метода ДДШ это множество таких x, что F8(x) = x (неподвижная точка преобразования F8). Для всякого открытого текста из этого множества преобразование ГОСТ 28147-89 работает в точности так же, как последние его 8 раундов, что и упрощает анализ.

Трудоемкость атаки Исобе составляет 2 224 операций зашифрования, атаки ДДШ – 2 192 . Однако все вопросы о том, следует ли, что атаки Исобе и ДДШ вносят новые ограничения на условия применения нашего алгоритма, снимает оценка требований к объему материала, необходимого для проведения каждой из атак: для метода Исобе требуется 2 32 пар открытых и шифрованных текстов, а для метода ДДШ – 2 64 . Обработка таких объемов материала без смены ключа априорно неприемлема для любого блокового шифра с длиной блока 64: на материале объемом 2 32 , с учетом задачи о днях рождения (см., например, [ISO]), близка к 1/2 вероятность появления повторяющихся блоков, что предоставит нарушителю возможность делать по шифрованным текстам некоторые заключения об открытых текстах без определения ключа. Наличие же 2 64 пар открытых и шифрованных текстов, полученных на одном ключе, фактически позволяет противнику осуществлять операции зашифрования и расшифрования вообще без знания этого ключа. Это обусловлено чисто комбинаторным свойством: противник в этом случае обладает всей таблицей шифрующего преобразования. Такая ситуация абсолютно недопустима ни при каких разумных эксплуатационных требованиях. Например, в КриптоПро CSP присутствует техническое ограничение на объём шифруемого (без преобразования ключа) материала в 4 Мб (см. [CPDN]). Таким образом, строгий запрет на использование ключа на материале такого объема присущ всякому блоковому шифру с длиной блока 64 бита, а следовательно, атаки Исобе и ДДШ никоим образом не сужают область использования алгоритма ГОСТ 28147-89 при сохранении максимально возможной стойкости 2 256 .

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

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

Отметим, что определенные небрежности в оценках средней трудоемкости присутствуют и в работе Динура, Данкельмана и Шамира. Так, при построении атаки не уделяется должного внимания следующему моменту: для существенной доли ключей множество открытых текстов x, таких, что F8(x) = x, является пустым: неподвижных точек у 8 раундов преобразования может просто не быть. Существование неподвижных точек зависит также и от выбора узлов замены. Таким образом, атака является применимой только при определенных узлах замены и ключах.

Стоит упомянуть также еще об одной работе с атакой на ГОСТ 28147-89. В феврале 2012 года на электронном архиве ePrint международной криптографической ассоциации появилась обновленная версия статьи [ZhuGong] (от ноября 2011 года), которая содержала новую атаку на ГОСТ 28147-89. Характеристики представленной атаки таковы: объем материала – 2 32 (как у Исобе), а трудоемкость – 2 192 (как у ДДШ). Таким образом, эта атака улучшала рекордную по времени атаку ДДШ по объему материала с 2 64 до 2 32 . Отметим отдельно, что авторы честно привели все выкладки с обоснованием трудоемкости и объема материала. Через 9 месяцев в приведенных выкладках была найдена принципиальная ошибка, и с ноября 2012 года обновленная версия статьи в электронном архиве уже не содержит каких-либо результатов касательно отечественного алгоритма.

Атаки в предположении, что нарушитель знает «кое-что» о ключах

Заметим напоследок, что в литературе также имеется некоторое количество работ (см., например, [R] и [П]), посвященных атакам на ГОСТ 28147-89 в так называемой модели со связанными ключами. Данная модель в своей основе содержит предположение о возможности нарушителя получать доступ для анализа не просто к парам открытых и шифрованных с помощью искомого ключа текстов, но также к парам открытых и шифрованных текстов, полученных с помощью (также неизвестных) ключей, отличающихся от искомого известным регулярным образом (например, в фиксированных битовых позициях). В данной модели действительно удается получить интересные результаты о ГОСТ 28147-89, однако в этой модели не менее сильные результаты удается получать и о, например, получившем наиболее широкое распространение в современных сетях общего пользования стандарте AES (см, например, [Khovr]). Заметим, что условия для проведения такого рода атак возникают при использовании шифра в некотором протоколе. Нельзя не отметить, что результаты такого рода, хоть и представляют несомненный академический интерес с точки зрения изучения свойств криптографических преобразований, но фактически не относятся к практике. Например, все сертифицированные ФСБ России средства криптографической защиты информации выполняют строжайшие требования по схемам выработки ключей шифрования (см., например, [ESP]). Как указано в результатах проведенного в [Rud1] анализа, при наличии 18 связанных ключей и 2 10 пар блоков открытого и шифрованного текста трудоемкость полного вскрытия закрытого ключа, при вероятности успеха 1-10 -4 , действительно составляет 2 26 . Однако при соблюдении упомянутых выше требований по выработке ключевого материала вероятность обнаружения таких ключей равна 2 -4352 , то есть в 2 4096 раз меньше, чем если просто попытаться угадать секретный ключ с первой попытки.

К работам, относящимся к модели со связанными ключами, относится также и работа [Fle], наделавшая в 2010 году много шума в российских электронных изданиях, не страдающих от привычки внимательно проверять материал в процессе гонки за сенсациями. Результаты, представленные в ней, не были подкреплены каким-либо сколь-нибудь строгим обоснованием, зато содержали громкие заявления о возможности взламывать государственный стандарт Российской Федерации на слабеньком ноутбуке за считанные секунды – в общем, статья была написана в лучших традициях Николя Куртуа. Но, несмотря на совершенно очевидную мало-мальски знакомому с основными принципами научности публикаций читателю безосновательность статьи, именно для успокоения российской общественности после работы [Fle] Рудским был написан подробный и обстоятельный текст [Rud1], содержащий всесторонний анализ данной недостатьи. В статье с говорящим названием «О нулевой практической значимости работы «Key recovery attack on full GOST block cipher with zero time and memory»» приводится обоснование того, что средняя трудоемкость приведенного в [ Fle ] метода не меньше, чем трудоемкость полного перебора.

Сухой остаток: какова стойкость на практике?

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

Атака Трудоемкость Память Требуемый материал
Исобе 2 224 2 64 2 32
Динур-Данкельман-Шамир, FP, 2DMitM 2 192 2 36 2 64
Динур-Данкельман-Шамир, FP, low-memory 2 204 2 19 2 64
Динур-Данкельман-Шамир, Reflection, 2DMitM 2 224 2 36 2 32
Динур-Данкельман-Шамир, Reflection, 2DMitM 2 236 2 19 2 32
Полный перебор 2 256 1 4
Количество наносекунд с возникновения Вселенной 2 89

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

В следующей части статьи в нашем блоге мы планируем обсуждение возможностей создания быстрых реализаций ГОСТ 28147-89.

Литература

[ГОСТ] Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. Ссылка.

[ТК26] О деятельности по международной стандартизации алгоритма шифрования ГОСТ 28147-89. Ссылка.

[ESP] Комбинированный алгоритм шифрования вложений IPsec (ESP) на основе ГОСТ 28147-89. Ссылка.

[CPDN] Интерфейс криптопровайдера «КриптоПро CSP 3.6». Описание функции CPEncrypt. Ссылка.

[ISO] ISO/IEC JTC 1/SC 27 Standing Document 12.

[Khovr] Related-key Cryptanalysis of the Full AES-192 and AES-256 . Alex Biryukov, Dmitry Khovratovich // Advances in Cryptology – ASIACRYPT 2009.

[Cid] C. Cid and G. Leurent. An Analysis of the XSL Algorithm. In B. Roy, editor, Proceedings of Asiacrypt 2005, LNCS, volume 3788, pages 333–352, Springer-Verlag,2005.

[Cour1] N. Courtois. Security Evaluation of GOST 28147-89 In View Of International Standardisation. Cryptology ePrint Archive 2011/211.

[Cour2] N. Courtois. M. Misztal, First Differential Attack On Full 32-Round GOST, in ICICS’11, pp. 216-227, Springer LNCS 7043, 2011.

[Cour3] N. Courtois. M. Misztal, Differential Cryptanalysis of GOST. Cryptology ePrint Archive 2011/312.

[Cour4] N. Courtois. Algebraic Complexity Reduction and Cryptanalysis of GOST. Cryptology ePrint Archive 2011/626.

[Cour5] N. Courtois. An Improved Differential Attack on Full GOST. Cryptology ePrint Archive 2012/138.

[Cour6] N. Courtois. Low-Complexity Key Recovery Attacks on GOST Block Cipher. Cryptologia Volume 37, Issue 1, 2013.

[DDS] I. Dinur, O. Dunkelman, A. Shamir. Improved Attacks on Full GOST. FSE 2012, LNCS 7549, pp. 9-28, 2012 (доступна также ранняя версия ).

[ Fle ] E. Fleischmann, M. Gorski, J.-H. Huhne, S. Lucks. Key Recovery Attack on full GOST Block Cipher with Zero Time and Memory, WEWoRC, 2009.

[Isobe] T. Isobe. A Single-Key Attack on the Full GOST Block Cipher. FSE 2011. LNCS, vol. 6733, Springer, 2011, pp. 290–305.

[R] Y. Ko, S. Hong, W. Lee, S. Lee, J.-S. Kang. Related Key Differential Attacks on 27 Rounds of XTEA and Full-Round GOST. In: Roy, B.K., Meier, W. (eds.) FSE 2004. LNCS, vol. 3017, pp. 299–316. Springer, Heidelberg (2004).

[Rud1] V. Rudskoy. On zero practical significance of “Key recovery attack on full GOST block cipher with zero time and memory. Cryptology ePrint Archive 2010/111.

[Rud2] V. Rudskoy, A. Dmukh. Algebraic and Differential Cryptanalysis of GOST: Fact or Fiction. Proceedings of CTCrypt 2012.

[ ZhuGong ] B. Zhu, G. Gong. Multidimensional Meet-in-the-Middle Attack and Its Applications to GOST, KTANTAN and Hummingbird-2. Cryptology ePrint Archive 2011/619.

[ДмухМаршалко] А. Дмух, Д. Дыгин, Г. Маршалко. О возможности модификации алгоритма шифрования ГОСТ 28147-89 с сохранением приемлемых эксплуатационных характеристик. Материалы конференции Рускрипто-2013.

[П] М. Пудовкина, Г. Хоруженко. Атака на шифрсистему ГОСТ 28147-89 с 12 связанными ключами. Матем. вопр. криптогр., 2013, 4, 2, 127—152.

[Руд1] В. Рудской. О некоторых подходах к оценке эффективности методов криптографического анализа, использующих связанные ключи. Материалы конференции Рускрипто-2011.

[Руд2] В. Рудской. Обзор последних публикаций по криптографическим исследованиям алгоритма шифрования ГОСТ 28147-89. Материалы конференции Рускрипто-2012.

Некоторые статьи и комментарии в сети:

Курсовая работа: Разработка программы, реализующей алгоритм шифрования ГОСТ 28147-89

Пояснительная записка к курсовой работе по информационной безопасности

Студент группы 1541 Р.В. Ткачук

Дальневосточная государственная социально-гуманитарная академия

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

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

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

Целью данной курсового проекта является разработка программы, реализующей шифрование ГОСТ 28147-89.

В курсовом проекте были поставлены следующие задачи:

Анализ литературы при разработке программы шифрования на основе ГОСТ 28147-89;

Анализ алгоритмов шифрования ГОСТ 28147-89;

Разработка программы реализующей алгоритм шифрования ГОСТ 28147-89;

Разработка руководства пользователя;

Разработка руководства программы.

Объектом в курсовом проекте является — методы шифрования ГОСТ 28147-89.

Предметом является – разработка программы для шифрования и дешифрования файлов алгоритмом ГОСТ 28147-89 методом гаммирования с обратной связью в среде программирования Delphi.

1 КРИПТОЛОГИЯ. ОСНОВНЫЕ ПОНЯТИЯ

Пpоблемой защиты инфоpмации путем ее пpеобpазования занимается кpиптология (kryptos — тайный, logos — наука).

К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ядоченный набоp из элементов алфавита.

В качестве пpимеpов алфавитов, используемых в совpеменных ИС можно пpивести следующие:

алфавит Z33 — 32 буквы pусского алфавита и пpобел;

алфавит Z256 — символы, входящие в стандаpтные коды ASCII и КОИ-8;

бинаpный алфавит — Z2 = <0,1>;

восьме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иптоанализа.

2 Требования к криптосистемам

П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авной длине исходного текста;

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

3.1 История создания. Правомерность использования

Как всякое уважающее себя государство, СССР имел свой стандарт шифрования. Этот стандарт закреплен ГОСТом №28147-89, принятом еще в 1989 году. Однако, без сомнения, история этого шифра гораздо более давняя. Стандарт родился предположительно в недрах восьмого главного управления КГБ СССР, преобразованного ныне в ФАПСИ. В те времена он имел гриф «Совершенно секретно», позже гриф был изменен на «Секретно», затем снят совсем. К сожалению, в отличие от самого стандарта, история его создания и критерии проектирования шифра до сих пор остаются тайной за семью печатями.

Возможное использование ГОСТа в собственных разработках ставит ряд вопросов. Вопрос первый – нет ли юридических препятствий для этого. Таких препятствий нет, и все могут свободно использовать ГОСТ, он не запатентован, следовательно, не у кого спрашивать разрешения. На указ Президента России №334 от 03.04.95 и соответствующие постановления правительства РФ, можем вообще смело закрыть глаза. Хотя данный документ формально и запрещают разработку систем, содержащих средства криптозащиты юридическими и физическими лицами, не имеющими лицензии на этот вид деятельности, реально указ распространяется лишь на случай государственных секретов, данных, составляющих банковскую тайну и т.п.

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

3.2 Описание метода

3.2.1 Базовые понятия и составляющие алгоритма

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

Элементы данных обозначим заглавными латинскими буквами с наклонным начертанием (например, X). Через |X| обозначается размер элемента данных X в битах. Таким образом, если интерпретировать элемент данных X как целое неотрицательное число, можно записать следующее неравенство: 0

e|d — e (encrypt) – зашифровать;

d (decrypt) – расшифровать;

— имя входного файла;

— имя выходного файла.

Если третий параметр опустить, то имя выходного файла будет формироваться из имени входного файла. При зашифровании это будет добавление расширения gst, при расшифровании удаление расширения gst.

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

В данной работе изучен алгоритм шифрования ГОСТ 28147-89. Так же на основании этого алгоритма была создана программа. В тексте работы приведено руководство к данной программе.

Герасименко В.А., Малюк А.А. Основы защиты информации. М.: МГИФИ, 1997. – 348 с.

Зима В.М.. Молдовян А.А., Молдовян Н.А. Компьютерные сети и защита передаваемой информации. СПб.: СПбГУ, 1998. – 312 с.

Мельников В.В. Защита информации в компьютерных системах. М.: Финансы и статистика, 1997. – 248 с.

Романец Ю.В.. Тимофеев П.А., Шаньгин В.Ф. Защита информации в компьютерных системах и сетях. М.: Радио и связь, 1999. – 349 с.

Харин Ю.С., Берник В.И., Матвеев Г.В. Математические основы криптологии. Мн.: БГУ, 1999. – 294 с.

TGOST_Block = array [0..1] of LongWord;

TGOST_Key = array [0..7] of LongWord;

TGOST_TZam256 = array [0..3, 0..255] of Byte;

GSeed: TGOST_Block = (0, 0);

ABlock: array [0..127] of TGOST_Block;

b1, b2: TGOST_Block;

procedure GOST_SetSeed(const GS: TGOST_Block);

procedure GOST_EncryptBlock(var GBlock: TGOST_Block); assembler;

Алгоритм ГОСТ 28147-89 и шифр «Магма» (ГОСТ Р 34.12-2015)

Общая схема алгоритма. Алгоритм, описанный ГОСТ 28147—89 «Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования», является отечественным стандартом симметричного шифрования (до 1 января 2020 г.) и обязателен для реализации в сертифицированных средствах криптографической защиты информации, применяемых в государственных информационных системах и, в некоторых случаях, в коммерческих системах. Сертификация средств криптографической защиты информации требуется для защиты сведений, составляющих государственную тайну РФ, и сведений, конфиденциальность которых требуется обеспечить согласно действующему законодательству. Также в Российской Федерации применение алгоритма ГОСТ 28147—89 рекомендовано для защиты банковских информационных систем.

Алгоритм ГОСТ 28147—89 (рис. 2.21) базируется на схеме Фейстеля и шифрует информацию блоками по 64 бит, которые разбиваются на два подблока по 32 бита (I, и R). Подблок R, обрабатывается функцией раундового преобразования, после чего его значение складывается со значением подблока Lj, затем подблоки меняются местами. Алгоритм имеет 16 или 32 раунда в зависимости от режима шифрования (вычисление имитовставки или другие режимы шифрования).

Рис. 2.21. Схема раунда алгоритма ГОСТ 28147—89

В каждом раунде алгоритма выполняются следующие преобразования.

1. Наложение ключа. Содержание подблока Ri складывается по модулю 2 32 с ключом раунда К. Kj — это 32-битовая часть исходного ключа, используемая в качестве раундового. Алгоритм ГОСТ 28147—89 нс использует процедуру расширения ключа, исходный 256-битный ключ шифрования представляется в виде конкатенации (сцепления) восьми 32-битовых подключей (рис. 2.22): К, К<, Кт К,, КА, К5, К6, К7.

В процессе шифрования используется один из этих подключей К•

• с 1-го по 24-й раунд — в прямой последовательности:

• с 25-го но 32-й раунд — в обратной последовательности:

Рис. 2.22. Строение ключа шифрования алгоритма ГОСТ 28147—89

2. Табличная замена. После наложения ключа подблок Ri разбивается на восемь частей но 4 бита, значение каждой из которых по отдельности заменяется в соответствии со своей таблицей замены (S-блоком). Всего используется восемь S-блоков — S, S,, S2, S3, S4, S5, S6, S7. Каждый S-блок алгоритма ГОСТ 28147—89 представляет собой вектор (одномерный массив) с ^элементами, пронумерованными от 0 до 15. Значениями S-блока являются 4-битовые числа, т.е. целые числа от 0 до 15.

Из таблицы S-блока берется элемент, порядковый номер которого совпадает со значением, пришедшим на вход подстановки.

Пусть имеется S-блок следующего вида:

Пусть на вход этого S-блока подано значение 01002 = 4. Выходом S-блока будет 4-й элемент таблицы замен, т.е. 15 = 11112 (нумерация элементов начинается с нуля). [1]

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

К сожалению, алгоритм ГОСТ 28147—89 имеет «слабые» таблицы замен, при использовании которых алгоритм может быть достаточно легко раскрыт криптоаналитическими методами. К числу «слабых» относится, например, тривиальная таблица замен, в которой вход равен выходу (табл. 2.16).

Пример слабого S-блока

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

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

  • • устанавливается нулевой ключ и выполняется поиск «нулевого вектора», т.е. значения z = F(0), где F — функция раундового преобразования алгоритма. Это требует порядка 2 32 тестовых операций шифрования;
  • • с помощью нулевого вектора вычисляются значения таблиц замен, что занимает не более 2 11 операций.


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

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

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

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

Для проектирования S-блоков был выдвинут целый ряд критериев. Таблица замен должна удовлетворять:

  • • строгому лавинному критерию;
  • • критерию независимости битов;
  • • требованию нелинейности от входных значений.

Для выполнения последнего требования было предложено задавать линейную комбинацию i битов (i = 1, . т) значений таблицы замен бентфункциями (англ, bent — отклоняющийся, в данном случае — от линейных функций). Бент-функции образуют специальный класс булевых функций, характеризующихся высшим классом нелинейности и соответствием строгому лавинному критерию.

В некоторых работах для S-блоков предлагается проверка выполнения гарантированного лавинного эффекта порядка у — при изменении одного входного бита меняется, по крайней мере, у выходных бит S-блока. Свойство гарантированного лавинного эффекта порядка у от 2 до 5 обеспечивает достаточно хорошие диффузионные характеристики S-блоков для любого алгоритма шифрования.

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

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

Можно предложить следующий порядок [2] проектирования отдельных S- блоков алгоритма ГОСТ 28147—89:

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

Описаны и другие алгоритмы [3] построения S-блоков для шифра ГОСТ 28147—89. На практике обычно достаточно получить узлы замен как независимые случайные перестановки чисел от 0 до 15.

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

Попытки проектирования S-блоков как функции от ключа шифрования показали, что использование зависящих от ключа S-блоков обычно ослабляет шифр (как для DES, так и для ГОСТ 28147—89).

Режимы работы алгоритма ГОСТ 28147—89. Алгоритм ГОСТ 28147—89 имеет четыре режима работы, которые отличаются от общепринятых:

  • • простой замены;
  • • гаммирования;
  • • гаммирования с обратной связью;
  • • выработки имитовставки.

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

Режим гаммирования. В режиме гаммирования каждый блок открытого текста побитно складывается по модулю 2 (XOR) с 64-битным блоком гаммы шифра (рис. 2.23). Гамма шифра — псевдослучайная последовательность, которая вырабатывается следующим образом:

  • • в 32-битовые регистры N< и N2 записываются их начальные значения — половины 64-битной величины, называемой синхропосылкой. Синхропосылка является аналогом вектора инициализации в режимах СВС, CFB, OFB;
  • • выполняется шифрование содержимого N< и N0 в режиме простой замены, результаты записываются в регистры JV, и N2;
  • • содержимое N< складывается по модулю (2 32 -1) со значением константы Ах = 2 24 + 2 16 + 2 8 + 4. Если получено значение, равное нулю, оно заменяется на 2 32 — 1. Результат сложения записывается в регистр Nv С учетом сделанного замечания корректная с математической точки зрения формула для вычисления нового значения А, может быть записана как Nu = = (Nu_< + А, — l)mod(2 32 — 1) + 1;
  • • содержимое N2 складывается по модулю 2 32 со значением константы А2 = 2 24 + 2 lfi + 2 s + 1, результат сложения записывается в регистр N2: N2i = = (N2i_< + A2)mod2 32 ;
  • • содержимое регистров N< и JV2 подается на выход алгоритма выработки гаммы, г.е. представляет блок гаммы, которая затем складывается с блоком открытого текста;
  • • при необходимости продолжения повторяются все шаги, кроме первого.

Рис. 2.23. Режим гаммирования

Период повторения генерируемой гаммы М составляет 2 32 (2 32 — 1), т.е.

Режим гаммирования с обратной связью. Этот режим аналогичен предыдущему, но в качестве заполнения регистров N< и N2, начиная со второго блока, используется результат шифрования предыдущего блока открытого текста (рис. 2.24).

Рис. 2.24. Режим гаммирования с обратной связью

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

  • • первый блок информации, для которого вычисляется имитовставка, шифруется алгоритмом ГОСТ в сокращенном режиме, в котором выполняются только 16 раундов из 32;
  • • результат шифрования суммируется (с помощью операции побитового XOR) со следующим блоком информации;
  • • результат суммирования снова шифруется в сокращенном режиме;
  • • при необходимости все шаги, кроме первого, повторяются.

Рис. 2.25. Режим выработки имитовставки

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

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

Для защиты от преднамеренной модификации данных применяют другие криптографические методы — в первую очередь электронную цифровую подпись (ЭЦП).

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

  • 1) вычисление имитовставки для заданной незашифрованной информации;
  • 2) подбор открытых данных иод заданную имитовставку.

Имитовставка используется следующим образом:

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

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

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

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

Криптостойкость алгоритма ГОСТ 28147—89. В 1994 г. описание алгоритма ГОСТ 28147—89 было переведено на английский язык и опубликовано. Именно после этого стали появляться результаты его анализа, выполненные зарубежными специалистами.

В течение значительного времени не было найдено каких-либо практически осуществимых атак [4] . В открытой публикации довольно мало работ, посвященных криптоанализу ГОСТ, по их результатам можно сделать вывод о весьма высокой криптостойкости отечественного стандарта шифрования. Высокая стойкость достигается за счет:

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

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

Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифротекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа [6] . Этими авторами был найден большой класс слабых ключей алгоритма ГОСТ 28147—89, которые позволяют вскрыть алгоритм с помощью всего четырех выбранных открытых текстов и соответствующих им шифротекстов с достаточно низкой сложностью. Классы слабых ключей ГОСТ 28147—89 описаны и в других работах [7] .

В 2011 г. предложена новая атака «рефлексивная встреча посередине», незначительно снижающая стойкость ГОСТ 28147—89 (с 2256 до 2225) [8] . Лучший результата криптоанализа алгоритма по состоянию на 2012 г. позволяет снизить его стойкость до 2 192 , требуя относительно большого размера шифротекста и объема предварительно сформированных данных [9] . Несмотря на предложенные атаки, на современном уровне развития вычислительной техники ГОСТ 28147—89 сохраняет практическую стойкость.

Шифр «Магма» (ГОСТ Р 34.12—2015). Стандарт ГОСТ 28147—89 действовал в России более 25 лет. За это время он показал достаточную стойкость и хорошую эффективность программных и аппаратных реализаций, в том числе и на низкоресурсных устройствах. Хотя и были предложены криптоаналитические атаки, снижающие оценки его стойкости (лучшая — до 2 192 ), они далеки от возможности практической реализации. Поэтому было принято решение о включении алгоритма ГОСТ 28147—89 во вновь разрабатываемый стандарт симметричного шифрования.

В шопе 2015 г. приняты два новых национальных криптографических стандарта: ГОСТ Р 34.12—2015 «Информационная технология. Криптографическая защита информации. Блочные шифры» и ГОСТ Р 34.13—2015 «Информационная технология. Криптографическая защита информации. Режимы работы блочных шифров», которые вступают в действие с 1 января 2020 г.

Стандарт ГОСТ Р 34.12—2015 содержит описание двух блочных шифров с длиной блока 128 и 64 бит. Шифр ГОСТ 28147—89 с зафиксированными блоками нелинейной подстановки включен в новый ГОСТ Р 34.12—2015 в качестве 64-битового шифра под названием «Магма» («Magma»).

Ниже приведены закрепленные в стандарте блоки замен:

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

По мнению технического комитета по стандартизации «Криптографическая защита информации» (ТК 26), фиксация блоков нелинейной подстановки сделает алгоритм ГОСТ 28147—89 более унифицированным и поможет исключить использование «слабых» блоков нелинейной подстановки. Кроме того, фиксация в стандарте всех долговременных параметров шифра отвечает принятой международной практике. Новый стандарт ГОСТ Р 34.12—2015 терминологически и концептуально связан с международными стандартами ИСО/МЭК 10116 «Информационные технологии. Методы обеспечения безопасности. Режимы работы для «-битовых блочных шифров» (ISO/IEC 10116:2006 Information technology — Security techniques — Modes of operation for an n-bit block cipher) и серии ИСО/МЭК 18033 «Информационные технологии. Методы и средства обеспечения безопасности. Алгоритмы шифрования»: ИСО/МЭК 18033-1:2005 «Часть 1. Общие положения» (ISO/IEC 18033-1:2005 Information technology — Security techniques — Encryption algorithms — Part 1: General) и ИСО/МЭК 18033-3:2010 «Часть 3. Блочные шифры» (ISO/IEC 18033-3:2010 (Information technology — Security techniques — Encryption algorithms — Part 3: Block ciphers)).

В стандарт ГОСТ P 34.12—2015 включен также новый блочный шифр («Кузнечик») с размером блока 128 бит. Ожидается, что этот шифр будет устойчив ко всем известным на сегодняшний день атакам на блочные шифры.

Режимы работы блочных шифров (простой замены, гаммирования, гам- мирования с обратной связью по выходу, гаммирования с обратной связью по шифротексту, простой замены с зацеплением и выработки имитовстав- ки) выведены в отдельный стандарт ГОСТ Р 34.13—2015, что соответствует принятой международной практике. Эти режимы применимы как к шифру «Магма», так и к новому шифру «Кузнечик».

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

ГОСТ 28147-89

Содержание

Краткое описание

  • Создатель — КГБ, 8-е управление
  • Создан — 1989 г.
  • Опубликован — 1990 г.
  • Размер ключа — 256 бит
  • Размер блока — 64 бит
  • Число раундов — 32\16
  • Тип — Сеть Фейстеля

Так же стоит обратить внимание на:

История блочного шифра ГОСТ

ГОСТ 28147-89 — советский и российский стандарт Симметричное шифрование симметричного шифрования, введённый в 1990 году, также является стандартом СНГ. Полное название— «ГОСТ 28147-89 Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования». Блочный шифроалгоритм. При использовании метода шифрования с гаммированием, может выполнять функции поточного шифроалгоритма.

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

С момента опубликования ГОСТа на нём стоял ограничительный гриф «Для служебного пользования», и формально шифр был объявлен «полностью открытым» только в мае 1994 года. К сожалению, история создания шифра и критерии разработчиков до сих пор не опубликованы.

Описание

ГОСТ 28147-89 — блочный шифр с 256-битным ключом и 32 циклами преобразования, оперирующий 64-битными блоками. Основа алгоритма шифра — Сеть Фейстеля.

Базовым режимом шифрования по ГОСТ 28147-89 является режим простой замены (определены также более сложные режимы гаммирование, гаммирование с обратной связью и режим имитовставки). Для зашифрования в этом режиме открытый текст сначала разбивается на две половины (младшие биты — A, старшие биты — B. На i-ом цикле используется подключ Ki:

A i + 1 = B i ⊕ f ( A i , K i ) <\displaystyle

Для генерации подключей исходный 256-битный ключ разбивается на восемь 32-битных блоков: K1…K8.

Ключи K9…K24 являются циклическим повторением ключей K1…K8 (нумеруются от младших битов к старшим). Ключи K25…K32 являются ключами K1…K8, идущими в обратном порядке.

После выполнения всех 32 раундов алгоритма, блоки A33 и B33 склеиваются (обратите внимание, что старшим битом становится A33, а младшим — B33) — результат есть результат работы алгоритма.

Расшифрование выполняется так же, как и зашифрование, но инвертируется порядок подключей Ki.

Ai и Ki складываются по модулю 2 32 .

Результат разбивается на восемь 4-битовых подпоследовательностей, каждая из которых поступает на вход своего узла таблицы замен (в порядке возрастания старшинства битов), называемого ниже S-блоком. Общее количество S-блоков ГОСТа — восемь, то есть столько же, сколько и подпоследовательностей. Каждый S-блок представляет собой перестановку чисел от 0 до 15. Первая 4-битная подпоследовательность попадает на вход первого S-блока, вторая — на вход второго и т. д.

Если S-блок выглядит так:

1, 15, 13, 0, 5, 7, 10, 4, 9, 2, 3, 14, 6, 11, 8, 12

и на входе S-блока 0, то на выходе будет 1, если 4, то на выходе будет 5, если на входе 12, то на выходе 6 и т. д.

Выходы всех восьми S-блоков объединяются в 32-битное слово, затем всё слово циклически сдвигается влево (к старшим разрядам) на 11 битов.

Все восемь S-блоков могут быть различными. Фактически, они могут являться дополнительным ключевым материалом, но чаще являются параметром схемы, общим для определенной группы пользователей. В ГОСТ Р 34.11-94 для целей тестирования приведены следующие S-блоки:

Название: Разработка программы, реализующей алгоритм шифрования ГОСТ 28147-89
Раздел: Рефераты по информатике, программированию
Тип: курсовая работа Добавлен 13:38:02 04 мая 2008 Похожие работы
Просмотров: 4715 Комментариев: 20 Оценило: 9 человек Средний балл: 3.3 Оценка: 3 Скачать
Номер S-блока Значение
1 4 10 9 2 13 8 14 6 11 1 12 7 15 5 3
2 14 11 4 12 6 13 15 10 2 3 8 1 7 5 9
3 5 8 1 13 10 3 4 2 14 15 12 7 6 9 11
4 7 13 10 1 8 9 15 14 4 6 12 11 2 5 3
5 6 12 7 1 5 15 13 8 4 10 9 14 3 11 2
6 4 11 10 7 2 1 13 3 6 8 5 9 12 15 14
7 13 11 4 1 3 15 5 9 10 14 7 6 8 2 12
8 1 15 13 5 7 10 4 9 2 3 14 6 11 8 12

В тексте стандарта указывается, что поставка заполнения узлов замены (S-блоков) производится в установленном порядке, то есть разработчиком алгоритма. Сообщество российских разработчиков СКЗИ согласовало используемые в Интернет узлы замены, см. RFC 4357.

Достоинства ГОСТа

  • бесперспективность силовой атаки (XSL-атаки в учёт не берутся, так как их эффективность на данный момент полностью не доказана);
  • эффективность реализации и соответственно высокое быстродействие на современных компьютерах.
  • наличие защиты от навязывания ложных данных (выработка имитовставки) и одинаковый цикл шифрования во всех четырех алгоритмах ГОСТа.

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

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

Отечественные ученые А. Г. Ростовцев и Е. Б. Маховенко в 2001 г. предложили принципиально новый метод криптоанализа (по мнению авторов, существенно более эффективный, чем линейный и дифференциальный криптоанализ) путем формирования целевой функции от известного открытого текста, соответствующего ему шифртекста и искомого значения ключа и нахождения ее экстремума, соответствующего истинному значению ключа. Они же нашли большой класс слабых ключей алгоритма ГОСТ 28147-89, которые позволяют вскрыть алгоритм с помощью всего 4-х выбранных открытых текстов и соответствующих им шифротекстов с достаточно низкой сложностью.

В 2004 г. группа специалистов из Кореи предложила атаку, с помощью которой, используя дифференциальный криптоанализ на связанных ключах, можно получить с вероятностью 91,7 % 12 бит секретного ключа. Для атаки требуется 2 35 выбранных открытых текстов и 2 36 операций шифрования. Как видно, данная атака практически бесполезна для реального вскрытия алгоритма. Ссылка на материал криптоанализа.

Критика ГОСТа

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

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

ГОСТ 28147-89 vs DES

ГОСТ DES
Внутренняя разработка КГБ, что делает его закрытым для общественности. Является корпоративной разработкой, открыт для общественного пользования.
Удобен в реализации в варианте soft и hardware Легок в реализации в hardware варианте, сложно реализовать в варианте soft продукта.
Учел все предыдущие разработки и ошибки, более прогрессивный, используется в настоящий момент. Не рекомендован к использованию.
Не очень популярен из-за закрытости алгоритма, конкретно S-блоков, которые выдаются в ФСБ по запросу. Обладал высокой популярностью.
Обладает хорошей стойкостью ключа. На данный момент не известны случаи взлома. Был взломан перебором.
Сравнение стойкости ключевого пространства: Block:64, Key 256 — большей запас ключевого пространства. Сравнение стойкости ключевого пространства: Block:64, Key 56 — можно перебрать на современных ЭВМ, за небольшой период времени.

Режимы шифрования в ГОСТ

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

ГОСТ 28147-89 является отечественным блочным шифром. То есть открытый текст разбивается на блоки (в данном случае 64 бита), и каждый блок преобразовывается отдельно. В основу алгоритма положена сеть Фейстеля, представленная на рисунке ниже.

  • Каждый блок разбивается на два «подблока» (левый и правый, соотвественно).
  • Исходное заполнение правого блока записывается в левый блок на выходе.
  • Над правым блоком производится криптографическое преобразование с применением ключевых данных.
  • Левый (исходный) и правый (преобразованный) блоки складываются по модулю 2 в сумматоре по модулю 2.
  • Так повторяется несколько раз.

Структурная схема алгоритма

Данная схема содержит

  • Четыре накопителя по 32 бита: N1, N2, N3, N4.
  • Два 32-разрядных накопителя: N5 и N6, — с записанными в них постоянными заполнениями C2 и C1 соответственно.
  • Ключевое запоминающее устройство (КЗУ) на 256 бит. КЗУ состоит из восьми накопителей по 32 разряда каждый: X, X1, X2, X3, X4, X5, X6, X7.
  • 32-разрядный сумматор по модулю 2: СМ2.
  • Еще один сумматор по модулю 2, который не имеет ограничения на разрядность (но используется 64 бита): СМ5.
  • Два сумматора по модулю 232 разрядности 32 бита: СМ1, СМ3.
  • Сумматор по модулю (232-1): СМ4.
  • Блок подстановки К: восемь узлов замены K1, K2, K3, K4, K5, K6, K7, K8, каждый с памятью на 64 бита.
    • Регистр циклического сдвига влево на 11 бит R.

Ключи

КЗУ отведено 256 бит, в ГОСТ 28147-89 используется ключ длиной 256 бит. Ключ разбивается на восемь блоков по 32 бита, и каждый бит каждого блока последовательно вводится в накопитель X соответствующего порядка.

То есть, 1-й бит ключа вводится в 1-й разряд накопителя X, 2-й — во 2-й разряд накопителя X, 33-й — в 1-й разряд накопителя X1, 65-й — в 1-й разряд накопителя X2, и так далее, 224-й бит ключа вводится в 1-й разряд накопителя X7, 256-й бит ключа вводится в 32-й разряд накопителя X7.

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

В блоке подстановки K

Блок подстановки содержит в себе таблицу замены размерностью 16×8, которая является долговременным ключом.

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

Ключи как в КЗУ, так и в блоке К, являются секретными, и требуются меры по недопущению их компрометации.

Параметры алгоритма ГОСТ 28147-89

Алгоритм ГОСТ 28147-89 является одним из блочных алгоритмов, основанных на сети Файстеля. В данной лаб. работе необходимо реализовать один из раундов сети Файстеля, определенных в этом алгоритме. Графическое описание одного раунда имеет вид (номер шага отмечен на соответствующем блоке схемы):

Шаг 0. Определяет исходные данные для основного шага криптопреобразования:

N – преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая (N1) и старшая (N2) части обрабатываются как отдельные 32-битовые целые числа. Таким образом, можно записать N=(N1,N2).

X – 32-битовый элемент ключа; в данной лаб. работе в качестве X можно использовать любое произвольно выбранное 32-битное число.

Т. обр., на вход алгоритма нужно подать три числа типа longint – X, N1, N2.

Шаг 1. Сложение с ключом. Число N1 складывается по модулю 2 32 с используемым на шаге элементом ключа X, результат передается на следующий шаг. Под сложением по модулю 2 32 можно понимать обычное сложение двух чисел типа longint с приведением результата к типу longint.

Шаг 2. Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S = (S, S1, S2, S3, S4, S5, S6, S7). Далее значение каждого из восьми блоков заменяется новым, которое выбирается по соответствующей таблице замен. Рекомендуется использовать следующие S-блоки (зададим их в виде одномерного списка, как договаривались ранее):

S-блок Значение
S
S1
S2
S3
S4
S5
S6
S7

Шаг 3. Циклический сдвиг на 11 бит влево. Результат предыдущего шага сдвигается циклически на 11 в сторону старших разрядов (т.е. влево, shl) и передается на следующий шаг.

Шаг 4. Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 с N2. Напомним, что побитное сложение по модулю 2 – это операция xor (исключающее или).

Шаг 5. Переприсвоение: N2 := N1; а в N1 записывается результат выполнения предыдущего шага.

Т.к. сеть Файстеля в общем случае строится на основе необратимых преобразований, то при построении обратного отображения не имеет смысл вычислять обратные S-блоки и выполнять указанные преобразования в обратном порядке. Обратное преобразование в этом случае будет иметь вид:

Шаг 0. Определяет исходные данные для основного шага обратного криптопреобразования:

N – преобразуемый 64-битовый блок данных, в ходе выполнения шага его младшая (N1) и старшая (N2) части обрабатываются как отдельные 32-битовые целые числа. Таким образом, можно записать N=(N1,N2).

X – 32-битовый элемент ключа; в данной лаб. работе в качестве X можно использовать любое произвольно выбранное 32-битное число.

Т. обр., на вход алгоритма нужно по-прежнему подать три числа типа longint – X, N1, N2.

Шаг 1. Сложение с ключом. Число N2 складывается по модулю 2 32 с используемым на шаге элементом ключа X, результат передается на следующий шаг.

Шаг 2. Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S = (S, S1, S2, S3, S4, S5, S6, S7). Далее значение каждого из восьми блоков заменяется новым, которое выбирается по соответствующей таблице замен (ПО ТОЙ ЖЕ ТАБЛИЦЕ ЗАМЕН, ЧТО И В ПРЕДЫДУЩЕМ АЛГОРИТМЕ).

Шаг 3. Циклический сдвиг на 11 бит влево. Результат предыдущего шага сдвигается циклически на 11 в сторону старших разрядов (т.е. влево, shl) и передается на следующий шаг.

Шаг 4. Побитовое сложение: значение, полученное на шаге 3, побитно складывается по модулю 2 с N1.

Шаг 5. Переприсвоение: N1 := N2; а в N2 записывается результат выполнения предыдущего шага.

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

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

1. Реализовать 8 S-блоков, описанных в шаге 2 раунда шифрования ГОСТ (см. таблицу). Решение этой задачи – это процедура или функция, которой на вход подается 32-битное число. Данная подпрограмма должна разбить это число на 8 4-битных блоков и осуществить замену каждого i-го блока (i=0,1,…,7) в соответствии с i-й таблицей.

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

3. Реализовать функцию, выполняющую 1 раунд шифрования по ГОСТ 28147-89. Реализовать также обратную к ней функцию.

Отчет по работе должен включать:

1. 2-минутное сообщение

Лабораторная работа № 6

Программная реализация алгоритма шифрования ГОСТ 28147-89.

Задание: Программно реализовать алгоритм блочного шифрования ГОСТ 28147-89, один раунд которого был получен на предыдущем лабораторном занятии.

Время выполнения: 1 пара.

Алгоритм ГОСТ 28147-89 – блочный алгоритм шифрования данных, имеющий следующие основные параметры:

· Размер блока – 64 бит

· Длина ключа – 256 бит

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

· При работе алгоритма 256-битный ключ шифрования K разбивается на 8 32-битных подключей, использующихся на итерациях сети Файстеля: K = K | K1 | K2 | K3 | K4 | K5 | K6 | K7. На итерациях Файстеля при шифровании данных используются следующие подключи:

Номер итерации
Номер подключа
Номер итерации
Номер подключа

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

Номер итерации
Номер подключа
Номер итерации
Номер подключа

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

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

1. Реализовать алгоритм, выполняющий зашифрование одного 64-битного блока данных, представленного одним числом int64 или двумя числами longint, с помощью алгоритма ГОСТ 28147-89.

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

Отчет по работе должен включать:

1. 2-минутное сообщение


Лабораторная работа № 7

Режимы использования блочных шифров.

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

· режим простой замены (ECB)

· режим шифрования с обратной связью (CBC, режим сцепления блоков)

· режим гаммирования с обратной связью (CFB, режим обратной связи по шифротексту)

· режим OFB (обратная связь по выходу).

Время выполнения: 1 пара.

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

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

· M=i> – исходный текст M, разделенный на блоки m1, m2, …, mN

· C=i> – шифрованный текст С, разделенный на блоки с1, с2, …, сN

· E – функция зашифрования на ключе K

· D – функция расшифрования на ключе K.

Тогда режим простой замены можно описать в виде формулы:

Графическое описание Формула
Зашифрование: ci = E(mi) Расшифрование: mi = D(ci)

В режиме шифрования с обратной связью (СВС, режим сцепления блоков) каждый блок сi, i³1, шифртекста перед очередным зашифрованием складывается по модулю 2 со следующим блоком открытого текста mi+1. При этом вектор c полагается равным начальному вектору IV (Initial Vector, вектор инициализации). Начальный вектор хранится в секрете. Рекомендуется его постоянно менять. Вектор инициализации также используется в двух нижеописанных режимах использования шифра.

Режим сцепления блоков можно описать в следующем виде:

Графическое описание Формула
Зашифрование: ci = E(ci-1 Å mi), c=IV Расшифрование: mi = D(ci) Å ci-1

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

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

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

Графическое описание Формула
Зашифрование: ci = mi Å E(ci-1), c=IV Расшифрование: mi = E(ci-1) Å mi

Режим обратной связи по выходу (OFB) подобен режиму CFB, но величины, складываемые поразрядно по модулю 2 с блоками исходного текста (с помощью операции XOR), не зависят от исходного текста.

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

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

Графическое описание Формула
Зашифрование: si = E(si-1), ci = mi Å si, s = IV Расшифрование: si = E(si-1), mi = ci Å si

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

1. Реализовать процедуры, выполняющие шифрование и расшифрование текста алгоритмом ГОСТ 28147-89 с помощью режима простой замены. Алгоритм шифрования одного блока исходного текста получен в предыдущей лаб. работе.

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

Отчет по работе должен включать:

1. 2-минутное сообщение

Лабораторная работа № 8

Алгоритм асимметричного шифрования Эль-Гамаля (El-Gamal).

Задание: Реализовать алгоритмы шифрования данных и генерации ключей Эль-Гамаля.

Время выполнения: 1 пара.

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

Алгоритм Эль-Гамаля – один из самых известных алгоритмов асимметричного шифрования данных, основанных на проблеме вычисления дискретного логарифма чисел в конечном поле. Данный алгоритм также допускает построение протокола цифровой подписи документов (на нем основаны стандарты ЭЦП DSA (амер. стандарт) и российский стандарт, ныне устаревший, ГОСТ 34.10-94).

Пусть даны два пользователя – А (Алиса) и Б (Боб). Пусть пользователь A желает инициировать криптосистему (т.е. сгенерировать все ключи и др. необходимые параметры) и начать обмен конфиденциальной информацией с Б. Тогда он должен выполнить следующее:

1. Сгенерировать простое число p (рекомендуется, чтобы оно было как минимум 512-битным). Сгенерировать также случайное целое число g, 1 a mod p.

3. Составить открытый ключ Ko = и передать его пользователю Б.

4. Составить секретный ключ Ks = и оставить его в секрете.

Допустим, что пользователь Б желает передать пользователю А некую конфиденциальную информацию, представленную в виде целого числа M, M k mod p.

3. Найти y2 = M Å (y k mod p), где M – исходное сообщение.

Пользователь А, получив шифровку (y1, y2) от пользователя Б, выполняет ее расшифрование:

1. Расшифрование: M = (y1 a mod p) Å y2

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

Вход: a, b: longint

Выход: c: longint // с = НОД(a,b).

1. Если a>b, то поменять местами а и b;

2. Присвоить с := a mod b. Если c=0, то вернуть b.

3. Присвоить a := b; b := c; Перейти к шагу 2.

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

1. Реализовать алгоритм Евклида, выполняющий поиск НОД двух чисел.

2. Реализовать криптосистему Эль-Гамаля. При этом рекомендуется выбрать следующие параметры этой криптосистемы:

· Исходное сообщение должно быть не более чем 16-битным числом (или массивом таких чисел).

· В качестве числа p возьмите простое число, большее 2 16 , например, 87649.

· Для хранения промежуточных операций, во избежание переполнения, используйте тип int64.

Отчет по работе должен включать:

  1. 2-минутное сообщение
  2. программу-тест

Лабораторная работа № 9

Бесключевые функции хеширования. Алгоритм SHA-1.

Задание: Реализовать алгоритм хеширования данных SHA-1.

Время выполнения: 1 пара.

Алгоритм SHA-1 – это алгоритм бесключевого хеширования данных, вырабатывающий 160-битную свертку сообщения.

Обработка исходного сообщения выполняется по одному 512-битному блоку. Поэтому исходное сообщение необходимо дополнить так, чтобы его длина стала кратной 32 битам. Оно дополняется до этой длины даже если его длина уже кратна указанной.

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

1. Дополнить сообщение до длины, кратной 512 битам, как описано выше.

2. Завести переменные

Для хранения этих переменных используйте тип 32-битное целое число (для С++-программистов рекоменжуется использовать тип без знака).

3. Завести переменные a,b,c,d,e и скопировать в них значения переменных A,B,C,D и E соответственно (программистам Дельфи придется придумать для них другие имена).

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

1. Определить операцию \ \IMG. ВНИМАНИЕ! ПЕРЕД СКАЧИВАНИЕМ ПРОЧИТАЙТЕ ЗАМЕЧАНИЯ НИЖЕ.

ЗАМЕЧАНИЕ: При добавлении вашего виртуального диска к менеджеру виртуальных дисков может появиться ошибка, которая говорит, что такой виртуальный диск уже зарегистрирован в системе:

Это говорит о том, что до вас работал другой студент, и его образ виртуальной машины остался зарегистрированным в программе. Диски регистрируются в VirtualBox по их уникальному UUID, поэтому вам необходимо скачать любой другой диск. Для предотвращения путаницы, номер используемого вами диска отобразите в названии ВМ, переименовав ее (см. далее, как переименовать машину). Сами также скачивайте диск с номером, не отображенным в именах уже созданных ВМ.

Замечание 2. Т.к. вам придется одновременно качать образы дисков, желательно использовать ftp-клиента с поддержкой докачки, в связи с возможными обрывами соединения. Для этого лучше всего использовать клиент FileZilla. Запустите его, и в основном окне укажите адрес ftp-сервера. Доступ к нему анонимный, поэтому ничего больше указывать не нужно. Далее нажмите кнопку «Быстрое соединение»:

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

После загрузки и распаковки виртуального диска, в программе VirtualBox выберите опцию «Существующий» и нажмите кнопку менеджера жестких дисков:

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

Далее укажите путь к распакованному вами файлу. После этого описание диска появится в списке. Выберите его и нажмите «Выбрать»:

После этого нажмите «Далее» и «Готово». Виртуальная машина создана.

  1. Научиться выполнять базовую настройку виртуальной машины.
    1. Щелкните мышью на имени виртуальной машины в основном окне программы Virtual Box и нажмите кнопку «Свойства»:

После этого откроется окно, позволяющее персонализировать настройки вашей ВМ. Переименуйте в нем вашу виртуальную машину, с указанием номера используемого диска:

    1. Ассоциировать ВМ с сетевым интерфейсом. Для этого выберите вкладку «Сеть» и в правой части окна, под вкладкой «Адаптер 1» в опции «Тип подключения» выберите «Сетевой мост». Это значит, что виртуальный интерфейс виртуальной машины будет объединен в мост с сетевой картой вашего компьютера и будет ее использовать для передачи данных по сети. Далее выберите в списке вашу сетевую карту (если их несколько):

После этого нажмите кнопку «ОК».

    1. Запустить ВМ. В главном окне программы VirtualBox щелкните мышью на имени машины и затем нажмите кнопку «Старт»:

Дождитесь загрузки ОС. На все появляющиеся диалоговые окна реагируйте следующим образом:

Перед загрузкой ОС будет произведена ее настройка, затем будет выполнена перезагрузка. После перезагрузки необходимо ввести имя пользователя и имя машины (процесс является первой настройкой только что установленной Windows 7):

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

Другими словами, чтобы начать работать мышью внутри ВМ, нужно просто щелкнуть по окну ВМ, а чтобы продолжить работать с основной ОС, нужно нажать хост-клавишу (по умолчанию – правый Ctrl).

В диалоговом окне нажмите «Захватить» и продолжите работу с ВМ.

Далее введите пароль (можно оставить его пустым). Если захотите ввести пароль, обязательно также указать подсказку для него:

Далее укажите, какие параметры безопасности ОС следует настроить:

Для вашей ВМ выбор опции в этом окне значения не имеет.

Настройте остальные требуемые параметры и перезагрузите ВМ. После ее загрузки установите Дополнения гостевой ОС в вашу ВМ.

Для этого в меню окна с вашей ВМ выберите «Устройства –> установить дополнения гостевой ОС»:

Замечание: Дополнения гостевой ОС позволят вам работать с сетью, звуком и некоторыми другими устройствами вашей ВМ. Кроме того, они позволят мыши автоматически захватываться окном ВМ и автоматически освобождаться, без нажатия хост-клавиши.

Внутри ВМ должно отобразиться меню автозапуска CD-ROM. Запустите предлагаемый exe-файл и установите программу. В процессе установки разрешите установку драйверов sun:

После завершения установки выберите опцию «Перезагрузить компьютер»:

Замечание: отключение UAC – шаг, предлагаемый для повышения удобства и совместимости программ. Т.к. UAC может серьезно повысить защищенность ОС, не рекомендуется этого делать на основных ОС.

Чтобы отключить UAC, в панели управления выберите User Accounts:

В открывшемся окне выберите «Change user account control settings»:

И в открывшемся окне переместите ползунок в крайнее нижнее положение:

    1. Проверить статус лицензии ВМ. Т.к. данный образ ВМ был подготовлен с помощью общедоступной версии Windows 7, то он имеет ограниченный срок действия. Для более подробной информации просмотрите «описание ВМ» на ftp-сервере преподавателя.

В меню «пуск выполните команду» slmgr.vbs –dlv. В открывшемся окне отобразится информация об используемом лицензионном ключе и об окончании срока лицензии:

Если время подойдет к 0 минут, можно выполнить команду slmgr -rearm и сбросить счетчик. Количество возможных выполнений этой команды отображено в окне выше в секции «remaining windows rearm count».

    1. Настройте сеть в ВМ. Внутри гостевой машины в панели управления выберите Network and sharing center:

Откроется окно, отображающее информацию о работе вашей сети. Чтобы изменить параметры сетевого подключения, выберите «Change adapter settings»:

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

Нажмите по нему правой кнопкой мыши и выберите в контекстном меню «Properties». В открывшемся окне выберите «IP v4» и нажмите «Properties»:

Далее пропишите ip-адрес, связный с подсетью 10.113.0.0/255.0.0.0. ВНИМАНИЕ: IP-адреса виртуальных машин ОБЯЗАТЕЛЬНО должны быть разными и не совпадать с IP-адресами хостовых систем:

    1. С помощью команды ping проверить связность с хостовой машиной. Если связности нет, попробуйте перезагрузит ВМ.
  1. Научиться создавать открытую сетевую папку на виртуальной машине, с анонимным доступом к этой папке. Она понадобится, если потребуется копировать даны в и из виртуальной машины. Для простоты настроим доступ для пользователя «гость» (guest).

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

Сначала нужно включить учетную запись «гость» (по умолчанию она отключена). Для этого в панели управления выберите «Computer management»:

В открывшейся оснастке выберите вкладку «Local users and groups». Далее щелкните правой кнопкой мыши по записи «Guest» и нажмите «properties »:

В открывшемся окне снимите галочку с опции «account is disabled»:

  1. Создайте папку, которую нужно сделать доступной по сети. Далее щелкните по ней правой кнопкой мыши и выберите «properties». В открывшемся окне щелкните на вкладку «Sharing», а в ней нажмите на кнопку «Advanced Sharing»:

В открывшемся окне сначала выберите опцию «Share this folder»:

Отредактируйте поле «Share name». Далее нажмите кнопку «Permissions» и установите права для сетевого доступа к этой папке:

Выберите пользователей и группы (по умолчанию выбрана группа «Все») и отредактируйте права доступа к этой папке. Установите галочку «Full control» для полного доступа к папке.

В окне «properties» щелкните на гиперссылку «Network and Sharing center».

В открывшемся окне установите разрешение на доступ к файлам и принтерам по сети:

Нажмите «Save changes». Далее в окне «properties» щелкните на вкладку «Security» установите локальные права доступа для гостя (которые будут действовать при его олицетворении):

Нажмите «Edit» и кнопку «Add», чтобы добавить разрешения для пользователя «guest». В открывшемся окне нажмите «Advanced»:

В раскрывшемся окне нажмите «Find now», чтобы компьютер выполнил поиск всех учетных записей и групп на локальном компьютере:

После этого выберите учетную запись гостя и нажмите ОК:

Далее добавьте гостю полный доступ к этой папке:

Далее отредактируйте права локальной политики компьютера для разрешения доступа гостя по сети (по умолчанию доступ по сети с учетной записью guest запрещен).

Для этого выполните команду gpedit.msc. Откроется оснастка-редактор локального объекта групповой политики:

В левой части открывшегося окна раскройте «Computer configuration -> windows settings -> security settings -> local policies -> user rights assignments». В списке опций справа выберите опцию «Deny access to this computer from the network»:

Дважды щелкните по этому пункту, чтобы отредактировать параметр:

Выберите запись «guest» и нажмите кнопку «remove».

a. Попробуйте обратиться к созданной вами общей папке из основной машины. Для этого используйте UNC-пути к этой папке (т.е. пути вида \\имя_компьютера\имя_ресурса) в окне проводника:

Отчет по работе должен включать:

1. Устный отчет на 2 мин. с демонстрацией полученных умений.

Лабораторная работа № 11

Программа True Crypt. Защита конфиденциальной информации. Программа PGP Desktop и стандарт защиты конфиденциальных данных PGP.

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

Время выполнения: 1 пара.

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

Файлы могут копироваться с, и на подключенный том TrueCrypt также, как они копирутся с/на любой нормальный диск (к примеру, с помощью технологии перетаскивания — drag-n-drop). Файлы автоматически дешифруются «на лету» (в память) во время чтения или копирования с зашифрованного тома TrueCrypt. Верно и обратное — файлы, записываемые или копируемые на том TrueCrypt, «на лету» шифруются в памяти прямо перед записью на диск. Однако это не значит, что весь файл, предназначенный для шифрования/расшифрования, должен целиком попасть в память перед шифрованием/расшифрованием. Для TrueCrypt не требуется дополнительная память.

TrueCrypt никогда не сохраняет никакие данные в незашифрованном виде на диск — он их временно хранит в памяти. Даже когда том подключен, данные на нём хранятся в зашифрованном виде. Когда вы перезапускаете Windows или выключаете компьютер, том отключается, и файлы, хранимые на нём, становятся недоступными, оставаясь зашифрованными. То же самое происходит в случае непредвиденного отключения электроэнергии (без правильного завершения работы системы). Чтобы получить к ним доступ снова, вы должны подключить том, используя правильные пароль и/или ключевой файл.

PGP (Pretty Good Privacy) — компьютерная программа, позволяющая выполнять операции шифрования (кодирования) и цифровой подписи сообщений, файлов и другой информации, представленной в электронном виде. Первоначально разработана Филиппом Циммерманном в 1991 году.

PGP имеет множество реализаций, совместимых между собой и рядом других программ (GnuPG, FileCrypt и др.) благодаря стандарту OpenPGP (RFC 4880), но имеющих разный набор функциональных возможностей. Существуют реализации PGP для всех наиболее распространённых операционных систем.

Пользователь PGP создаёт ключевую пару: открытый и закрытый ключ. При генерации ключей задаются их владелец (Имя и адрес электронной почты), тип ключа, длина ключа и срок его действия.

PGP поддерживает два типа ключей — RSA и Diffie-Hellman/DSS (Elgamal в терминологии GnuPG). Длина ключа может составлять от 1024 до 4096 бит. Ключи могут содержать один главный ключ и дополнительные ключи для шифрования. При этом ключ электронной подписи в ключах Diffie-Hellman/DSS всегда имеет размер 1024. Срок действия для каждого из типов ключей может быть определён как неограниченный или до конкретной даты. Для защиты ключевого контейнера используется секретная фраза.

Электронная цифровая подпись формируется путём подписи дайджеста(хэш значения, свертки) сообщения (файла) закрытым ключом отправителя (автора). Для формирования дайджеста могут использоваться алгоритмы MD5, SHA-1, RIPEMD-160, SHA-256, SHA-384, SHA-512. В новых версиях PGP поддержка MD5 осуществляется для сохранения совместимости с ранними версиями. Для подписи используются алгоритмы RSA или DSA (в зависимости от типа ключа).

Шифрование производится с использованием одного из пяти симметричных алгоритмов (AES, CAST5, TripleDES, IDEA, Twofish) на сеансовом ключе. Сеансовый ключ генерируется с использованием криптографически стойкого генератора псевдослучайных чисел. Сеансовый ключ зашифровывается открытым ключом получателя с использованием алгоритмов RSA или Elgamal (в зависимости от типа ключа получателя).

В целях уменьшения объёма сообщений и файлов и, возможно, для затруднения криптоанализа PGP производит сжатие данных перед шифрованием. Сжатие производится по одному из алгоритмов ZIP, ZLIB, BZIP2. Для сжатых, коротких и слабосжимаемых файлов сжатие не выполняется.

GNU Privacy Guard, GnuPG, GPG — свободная альтернатива набору криптографического ПО PGP, выпущенная под лицензией General Public License. Является частью проекта GNU, получила гранты от Германского правительства. GnuPG полностью совместим со стандартом IETF OpenPGP. Текущие версии GnuPG могут взаимодействовать с PGP и другими OpenPGP-совместимыми системами в режиме совместимости. GnuPG позволяет шифровать и подписывать данные в целях безопасного хранения и передачи информации.

GnuPG изначально создан Вернером Кохом (Werner Koch). Его свойства:

  • Полная альтернатива PGP.
  • Не использует патентованные алгоритмы.
  • Распространяется под GNU General Public License.
  • Полная реализация OpenPGP (RFC2440).
  • Дешифрование и аутентификация сообщений, созданных с помощью PGP 5, 6 и 7.
  • Поддержка электронной подписи с помощью алгоритмов ElGamal, DSA, RSA и хеш-функций MD5, SHA-1, RIPE-MD-160 и TIGER.
  • Работа с ассиметричным шифрованием ElGamal и RSA (длина ключа от 1024 до 4096 бит)
  • Поддержка блочных алгоритмов симметричного шифрования AES, 3DES, Blowfish, Twofish, CAST5, а также IDEA с помощью плагина.
  • Лёгкая реализация новых алгоритмов с помощью дополнительных модулей.
  • Поддержка просроченных ключей и подписей.
  • Интегрированная поддержка серверов ключей.

GnuPG — ПО, часто включаемое в свободные ОС, такие как GNU/Linux, FreeBSD, OpenBSD и NetBSD. В 2005 году выпущен Gpg4win — прогрaммный набор, который включает в себя GnuPG для Windows, WinPT, Gnu Privacy Assistant, и плагины GnuPG для Проводника Windows и Outlook.

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

GnuPG не использует запатентованное или иначе ограниченное ПО и/или алгоритмы, включая алгоритм IDEA. GnuPG использует другие непатентованные алгоритмы CAST5, 3DES, AES, Blowfish и Twofish. Тем не менее, возможно использование в GnuPG и алгоритма IDEA с помощью дополнительного модуля.

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

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

  1. Провести бенчмарку компьютера. Этот тест выполняет проверку скорости выполнения алгоритмов шифрования на машине. Например алгоритм AES будет шифровать/расшифровывать со скоростью 99/94,5 МБ/с.
    1. Нажмите Tools -> Benchmark…


    1. Нажмите [Close]
  1. Для создания нового файлового контейнера в основном окне программы нажмите Create Volume:

Далее нажмите [Create a file container], нажмите [Next>]

Выбрать [Standard TrueCrypt volume], нажмите [Next>]

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

Следует указывать путь следующего вида: D:\stud\ \ . Затем нажмите [Next>].

Выберите алгоритм шифрования:

Следует выбирать установки предложенные по умолчанию (Encryption Algorithm – AES, Hash Algorithm – RIPEMD-160)

Установите размер контейнера (например 1ГБ) и нажмите [Next>]

Введите пароль и подтверждение пароля:

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

Процесс генерации ключа:

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

После создания контейнера предлагается создать другой контейнер [Next>] или закрыть мастера создания контейнеров [Exit]:

  1. Монтировать контейнер и скопировать на него несколько файлов

Нажмите кнопку [Select File…] в основном окне программы, выберите созданный контейнер, который собираетесь смонтировать, нажмите [Mount]

Введите пароль к контейнеру

После чего в списке появится установленный контейнер, а в проводнике он будет отображаться в виде нового логического диска:

Теперь можно пользоваться контейнером как обычным диском.

  1. Зашифровать физический раздел жесткого диска. Для этого сначала создайте этот раздел (пустое место на диске под ваш раздел уже было выделено на вашей ВМ). Для этого зайдем в апплет «Администрирование» Панели управления и откроем ярлык «Управление компьютером». На левой панели выберите вкладку «Управление дисками»:

Нажмите правой кнопкой на области, которая не распределена и выберите в контекстном меню пункт «Создать раздел». После этого откроется мастер создания разделов. Нажмите «Далее».

В следующем окне выберите «Основной раздел» и нажмите «Далее»:

В следующем окне согласитесь с предложенными данными и нажмите «Далее»:

В следующем окне назначьте любую из предложенных букв вашему новому дисковому разделу:

После этого нажмите «Далее»:

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

Нажмите кнопку «Готово».

Далее повторите шаг 2 данной работы, но укажите «Create a volume within non-system partition/device».

  1. Создать спрятанный контейнер внутри существующего контейнера. Для этого требуются действия, аналогичные п. 2 предыдущей лаб., но потребуется указать, что контейнер имеет тип Hidden (спрятанный):

В окне VolumeCreation Mode выбрать Direct mode. Нажмите [Next>]

Открыть контейнер созданный в предыдущей лаб. работе (если он утерян, вернитесь к предыдущему шагу и вместо опции Direct mode укажите Normal mode; при этом сначала будет предложено создать обычный контейнер), нажмите [Next>]

Введите пароль к этому контейнеру

Создание скрытого контейнера:

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

Завершение работы мастера

  1. Монтируйте спрятанный контейнер и скопируйте в него несколько файлов (при монтировании укажите файл с обычным контейнером, но вводите пароль от спрятанного контейнера). Затем монтируйте обычный контейнер и убедитесь, что файлы спрятанного контейнера на нем не видны.
  2. Начало работы с программой OpenPGP.

1. Установка и настройка PGP Desktop.

Сначала выберите язык установки:

Затем согласитесь с EULA и пройдите несколько шагов:

Далее ответьте утвердительно (Yes) на предложение перезагрузки:

После перезагрузки системы запустится мастер установки PGP. Укажите «yes» и нажмите «Далее»:

Далее укажите свои данные. Эти данные потом можно будет использовать для создания вашей пры ключей в PGP:

Далее в окне выбора типа лицензирования программы укажите «использовать без лицензии и отключить большинство функций»:

Далее выберите опцию «Я уже использовал программу PGP»:

После этого нажмите насколько раз «Далее», затем нажмите «Skip». Завершите установку программы.

После этого в системном трее появится иконка программы PGP:

2. Генерация ключевых пар и ключей.

Щелкнув по ней левой или правой кнопкой мыши, вы откроете меню PGP:

Выберите «Open PGP Desktop», чтобы открыть программу «PGP Desktop»:

Чтобы сгенерировать новую пару ключей, выберите в меню keys -> New keyring:

После этого появится новя запись в секции «Ключи» основного окна. Щелкните по ней правой кнопкой мыши и переименуйте

так, как вам удобно:

Чтобы сгенерировать ключи в выбранном keyring, нажмите File->New PGP Key. Откроется мастер создания ключей:

Нажмите «Далее» и укажите пользователя, для которого требуется создать ключевую пару:

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

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

Нажмите «Advanced» и укажите дополнительные параметры ключа и используемых с ним алгоритмов шифрования данных:

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

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

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

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

После этого программа выполнит генерацию ключей:

Далее мастер завершит работу.

3. Дополнительные параметры ключей. Обмен ключами.

Чтобы просмотреть параметры вашего ключа, щелкните по нему правой кнопкой мыши и выберите «Properties»:

Окно с опциями имеет следующий вид:

Чтобы просмотреть Фингерпринт вашего ключа (значение хеш-функции от него), нажмите на раскрывающуюся вкладку Fingerprint, а в ней выберите закладку «Hexadecimal»:

далее настройте еще одну виртуальную машину (Wondows Vista или Windows Server) и установите программу PGP Desktop на ней. Также сгенерируйте на ней пару ключей для пользователя с именем, отличным от имени пользователя с созданной на первой машине парой ключей.

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

Чтобы экспортировать ключ, выберите его, а затем в меню выберите File->Export->key:

Дата добавления: 2015-11-23 ; просмотров: 1069 | Нарушение авторских прав

Достигаем феноменальной скорости на примере шифрования ГОСТ 28147—89

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

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

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

В чем измеряется производительность кода? Поскольку я первый об этом заговорил, то по праву первооткрывателя буду его измерять в RTT-шках ;).

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

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

Так вот, программный код, который загружает все исполнительные устройства процессора одновременно на протяжении всего времени исполнения кода, будет иметь производительность 12 RTT-шек. Максимум! Честно признаюсь, такого кода я раньше не писал, но в этой статье попытаюсь сделать над собой усилие.

Программный код, который использует в процессорном ядре одно исполнительное устройство, естественно, будет иметь производительность в 1 RTT-шку. Такой производительностью кода могут «похвастаться» программы, генерируемые компиляторами языков высокого уровня, и интерпретаторы виртуальных машин. Не нужно считать, что показатель загрузки процессора, который можно увидеть в диспетчере задач ОС, может служить объективным критерием эффективности кода. Загрузка ядра процессора может быть 100%, но при этом программный код будет использовать одно исполнительное устройство в нем (производительность 1 RTT). В этом случае при 100%-й загрузке процессорное ядро будет работать в 1/12 своей максимальной производительности. Другими словами, когда в диспетчере задач ОС Windows показывается максимальная загрузка процессора, его реальная производительность может варьироваться от 1 до 12 RTT. Увидев в окне производительности 100%-ю загрузку на каком-либо процессорном ядре, неправильно считать, что в этом ядре работают все исполнительные устройства, отнюдь!

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

Традиционная реализация ГОСТ 28147—89

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

Криптографическое преобразование по ГОСТ 28147—89 используется для поточного шифрования информации в каналах связи и на дисковых накопителях.

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

Рис. 1. Цитата из ГОСТа

Хакер #163. Лучшие гаджеты для хакера

По п. 1.2 ГОСТа этот блок реализует тетрадные (по четыре бита) перестановки в 32-битном слове, но архитектура процессора х86/64 и его система команд не способна эффективно манипулировать тетрадами.

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

В более продвинутых реализациях эти таблицы имеют размер 1024 байта (256 слов по четыре байта). Это сделано для того, чтобы реализовать в таблицах дополнительно циклический сдвиг на 11 позиций полученного в результате подстановки 32-битного слова (следующая операция алгоритма преобразования по ГОСТу). Пример реализации ГОСТа по данному методу показан в приложении 1 (на диске).

Информация блока подстановок является секретным компонентом криптофункции (как это сформулировано в ГОСТе, см. на рис. 2).

Рис. 2. Еще одна цитата из ГОСТа

Размещение этих таблиц с ключами блока подстановок в ОП противоречит требованиям ГОСТа (п. 1.7), поскольку секретная информация становится доступной для сторонних программ, работающих на вычислительной установке. ФСБ, сертифицирующая в том числе и программные реализации шифрования по ГОСТу, на данное нарушение смотрит, мягко говоря, снисходительно. Если для размещения ключей в ОП ФСБ еще требует наличия «фигового листочка» — маскирования ключей операцией XOR, то для блоков замен в ОП ничего не требуется, они хранятся в открытом виде.

Короче говоря, ФСБ пропускает такие программные реализации криптопроцедуры, несмотря на явное снижение стойкости такого решения и прямое нарушение собственных требований по ГОСТу (п. 1.7). И это несмотря на общеизвестные методы взлома шифров через съем дампа памяти…

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

Но хватит лирики, важно в рамках рассматриваемой темы то, что этот программный код имеет производительность в 1 RTT-шку. Теперь напишем код с производительностью 2 RTT-шки.

Многопоточная реализация ГОСТ 28147—89

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

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

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

Современные процессоры имеют в своем составе как минимум два, а то и три-шесть арифметико-логических устройств. Эти АЛУ (FPU, блоки адресной арифметики и так далее) могут работать независимо друг от друга, единственным условием их параллельной работы является непересекающиеся программные объекты, которыми они оперируют. Другими словами, в командах, которые одновременно выполняют АЛУ, адреса памяти и номера регистров должны быть разными. Либо в общие регистры и адреса памяти, к которым обращаются различные исполнительные устройства процессора, не должно выполняться операций записи.

Загрузкой работой всех АЛУ управляет специальный аппаратный блок внутри процессорного ядра — планировщик, который просматривает исполняемый код форвардно, на глубину до 32–64 байт. Если планировщик обнаруживает команды, которые можно запускать на АЛУ без конфликтов, то он их запускает одновременно на разных исполнительных устройствах. При этом счетчик выполненных команд указывает на ту исполняемую команду (их в такой схеме несколько), после которой все команды уже выполнены.

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

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

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

Но можно поступить и иначе: чередовать команды, относящиеся к обработке разных блоков данных. Графически эти варианты представлены на рис. 3.

Рис. 3. Чередование команд

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

Далее показан пример с чередованием команд из разных потоков обработки. В этом случае команды, относящиеся к разным блокам данных, чередуются. Планировщик выбирает независимые друг от друга команды и передает их на выполнение в АЛУ1 и АЛУ2. Группировка команд первого и второго потока на этих АЛУ осуществляется автоматически, поскольку в алгоритм работы планировщика заложена группировка команд с зацеплением по общим данным на одном и том же исполнительном устройстве.

Чтобы такой программный код работал без простоев АЛУ, необходимо, чтобы каждый программный поток работал со своим набором регистров. Кеш в этой схеме становится узким местом (у него только два порта выдачи данных), поэтому ключи храним в MMX-регистрах. Поскольку в данном случае узлы замены (и сдвига) в памяти только читаются, то они могут быть общими для обоих программных потоков.

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

Метод параллельного шифрования эффективно реализуется только для 64-битного режима работы процессора, поскольку в этом режиме имеется достаточное количество РОН (целых 16 штук!). Пример реализации ГОСТа по данному методу показан в приложении 2 (на диске).

Ясно, что данная реализация ГОСТа имеет производительность кода 2 RTT-шки. А теперь посмотрим, как это сказывается на времени выполнения.

Цикл шифрования для одного потока (приложение 1) составляет 352 такта, и за это время обсчитывается 8 байт данных, для двухпоточной реализации ГОСТа (приложение 2) требуется 416 тактов процессора, но при этом обсчитывается 16 байт. Таким образом, результирующая скорость преобразования повышается с 80 до 144 мегабайт для процессора частотой 3,6 ГГц.

Интересная получается картина: код содержит ровно в два раза больше команд, а выполняется всего на 15% дольше, но, думаю, читатели уже поняли причину этого феномена…

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

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

Использование SSE-регистров и AVX-команд современных процессоров для реализации ГОСТ 28147—89

Современные процессоры архитектуры х86/64 имеют в своем составе набор регистров SSE размером 16 байт и специализированные FPU (как минимум два) для выполнения различных операций над этими регистрами. Возможна реализация ГОСТа на этом оборудовании, причем в этом случае узлы замены можно размещать не в виде таблиц в оперативной памяти, а непосредственно на выделенных SSE-регистрах.

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

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

Схема одного из возможных размещений узлов замены на SSE-регистрах показана на рис. 4.

Рис. 4. Схема одного из возможных размещений узлов замены на SSE-регистрах

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

  • Ядро процессора переведено в режим хоста гипервизора, и в нем принудительно отключен блок прерываний (APIC). В этом случае ядро процессора полностью изолировано от ОС и приложений, функционирующих на вычислительной установке.
  • Загрузка SSE-регистров и изоляция вычислительного ядра производится до начала старта ОС, оптимальным является выполнение этих процедур с модуля доверенной загрузки (МДЗ).
  • Программы криптопроцедур по ГОСТу размещаются в немодифицируемой области памяти вычислительной установки (либо БИОС, либо в флеш-памяти МДЗ).

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

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

Имея узлы хранения подстановок на SSE-регистрах и многовходовый коммутатор в блоках FPU, можно организовать следующее преобразование в блоке подстановок (рис. 5).

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

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

Работой коммутаторов управляет специальная трехадресная команда AVX VPSHUFB. Ее первый операнд является приемником информации из коммутаторов, второй — источником, к которому подключены входы коммутаторов. Третий операнд является управляющим регистром для коммутаторов, каждый байт которого ассоциирован с соответствующим коммутатором; значение в нем задает номер направления, с которого коммутатор считывает информацию. Описание этой команды из официальной документации Intel см. на рис. 5. На рис. 6 приведена схема работы этой команды — изображена только половина SSE-регистров, для второй половины все аналогично.

Рис. 5. Преобразование в блоке подстановок

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

Рис. 6. Цитата из официальной документации Intel

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

Как говорится, «Наш финиш — горизонт», поэтому выжимать так выжимать. будем прессовать и складывать в пакеты!

Это не игра слов, а суровая FPUшная реальность — регистры SSE можно разбивать на равные части и выполнять над этими частями одинаковые преобразования одной командой. Для того чтобы процессор это понял, имеется магическая буковка «Р» — пакет, которая ставится перед мнемоникой команды, и не менее магические буковки «Q», «D», «W», «B», которые ставятся в конце и объявляют, на какие части разбиты в этой команде регистры SSE.

Рис. 7. Схема команды

Нас интересует пакетный режим с разбивкой SSE-регистра на четыре 32-битных блока; соответственно, все команды будут иметь префикс «P», а в конце — символ «D». Это дает возможность одной процессорной командой параллельно обрабатывать сразу четыре блока по 32 бита, то есть в параллель рассчитывать четыре блока данных.

Программа, реализующая этот метод, имеется в приложении 3, там же — все пояснения.

Впрочем, прессовать так прессовать! В современных процессорах имеется как минимум два блока FPU, и для их полной загрузки можно использовать два потока независимых команд. Если грамотно чередовать команды из независимых потоков, то можно загрузить работой оба блока FPU полностью и получить сразу восемь параллельно обрабатываемых потоков данных. Такая программка была написана, и ее можно посмотреть в приложении 4, только смотреть нужно осторожно — можно слететь с катушек. Это, что называется, «код не для всех. ».

Цена вопроса

Использование SSE-регистров для хранения узлов замены понятно — оно дает некую гарантию изоляции секретной информации, а вот смысл расчета самой криптофункции на FPU неочевиден. Поэтому были проведены замеры времени выполнения стандартных процедур по методу прямой замены в соответствии с ГОСТом для четырех и для восьми потоков.

Для четырех потоков была получена скорость выполнения 472 процессорных такта. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 59 мегабайт в секунду, а четыре потока соответственно со скоростью 236 мегабайт в секунду.

Для восьми потоков была получена скорость выполнения 580 процессорных тактов. Таким образом, для процессора с частотой 3,6 ГГц один поток считается со скоростью 49 мегабайт в секунду, а восемь потоков со скоростью 392 мегабайта в секунду.

Как может заметить читатель, код в примере № 3 имеет производительность 4 RTT, а код в примере № 4 имеет производительность 8 RTT. В этих примерах на SSE-регистрах закономерности те же, что и при использовании РОН, только планировщик снизил свою эффективность. Сейчас он обеспечивает 20%-е увеличение длительности при двукратном увеличении длины кода.

Причем эти результаты были получены с использованием универсальных AVX-команд, имеющихся как в процессорах Intel, так и в процессорах AMD. Если выполнить оптимизацию под процессор AMD, результат будет значительно лучше. Звучит поперек тренда, но тем не менее это правда, и вот почему: процессоры AMD имеют дополнительный набор команд, так называемое XOP-расширение, и в этом дополнительном наборе команд есть такие, которые значительно упрощают реализацию алгоритма ГОСТа.

Имеются в виду команды логического пакетного сдвига байтов и пакетного циклического сдвига двойных слов. В примерах, приведенных в приложениях 3 и 4, используются последовательности универсальных команд, реализующих необходимое преобразование: в первом случае одна «лишняя» команда, а в другом случае сразу четыре лишних команды. Так что резервы оптимизации есть, и немалые.

Если речь зашла о дальнейшей оптимизации, нелишне помнить о наличии 256-битных регистров (YMM-регистры), используя которые можно теоретически еще удвоить скорость вычислений. Но пока это только перспектива, на данный момент процессоры очень сильно замедляются, когда выполняют 256-битные инструкции (FPU имеют ширину тракта 128 бит). Эксперименты показали, что на современных процессорах счет в 16 потоков на YMM-регистрах выигрыша не дает. Но это только пока, на новых моделях процессоров, несомненно, будет увеличено быстродействие 256-битных команд, и тогда использование 16 параллельных потоков станет целесообразно и приведет к еще большему увеличению скорости работы криптопроцедуры.

Теоретически можно рассчитывать на скорость 600–700 мегабайт в секунду при наличии в процессоре двух FPU с шириной рабочего тракта 256 бит каждый. В этом случае можно говорить о написании кода с эффективностью 16 RTT, и это не фантастика, а ближайшая перспектива.

Смешанный режим

Будем прессовать дальше. Наша цель — получить 12 RTT-шек, это можно сделать, выполняя команды одновременно на всех имеющихся в ядре процессора FPU. Их у Intel три штуки, мы же пока задействовали только два, так что вперед!

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

Рассчитывать на прибавку в 50% здесь не приходится, узким местом становится кеш-память, где хранятся технологические маски, но прибавку в 100 дополнительных мегабайт все же получить можно. Этот вариант не приведен в приложениях (макросы аналогичны используемым в коде на 8 RTT), но он имеется в программных файлах. Так что если кто не верит в возможность шифрования со скоростью 500 мегабайт в секунду на одном процессорном ядре, пусть запустит тестовые файлы. Там же есть и тексты с комментариями, чтобы никто не подумал, что я лукавлю.

Такой фокус возможен только на процессорах Intel, у AMD только два блока FPU на два процессорных модуля (аналог режима гипертрейдинг). Но зато имеется еще четыре АЛУ, которые грех не использовать.

Можно загнать процессорные модули «Бульдозера» в режим, аналогичный режиму гипертрейдинга, но запускать на разных модулях в одном потоке преобразование на РОН, а в другом потоке на SSE-регистрах и получить те же 12 RTT. Этот вариант я не проверял, но, думаю, на AMD код в 12 RTT будет работать более эффективно. Желающие могут попробовать, тестовые программы можно подкорректировать для работы на «Бульдозерах» достаточно легко.

Кому это нужно?

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

Причем, как это ни странно, встроенное в процессоры шифрование по AES-алгоритму оказывается значительно медленнее, тесты показывают скорость на уровне 100–150 мегабайт в секунду, и это при аппаратной реализации алгоритма! Проблема заключается в однопоточном счете и блоке замен, который оперирует байтами (таблица из 256 строк). Так что ГОСТ оказывается эффективнее в реализации на архитектуре х86/64, кто бы мог подумать…

Это если говорить о достигнутом уровне скорости шифрования. А если иметь в виду теоретические изыски в области повышения эффективности кода, то скорее всего это никому не нужно. Специалистов уровня 3–6 RTT практически нет, компиляторы вообще генерят код на уровне 1–2,5 RTT, а основная масса программистов не знает ассемблера, а если и знает его правописание, то не понимает устройства современного процессора. А без этих знаний что ассемблер, что какой-нибудь там СИ-шарп — без разницы.

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

Отечественный стандарт шифрования данных

В нашей стране установлен единый алгоритм криптографического представления данных для систем обработки информации в сетях ЭВМ, отдельных вычислительных комплексов и ЭВМ, который определяется ГОСТ 28147-89.

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

При описании алгоритма используются следующие обозначения:

L и R — последовательности битов;
LR — конкатенация последовательностей L и R, в которой биты последовательности R следуют за битами последовательности L;
(+) — поразрядное сложение по модулю 2 (операция «исключающее ИЛИ»);
[+] — сложение 32-разрядных чисел по модулю 2 32 ;
<+>— сложение 32-разрядных чисел по модулю 2 32 -1.

Числа суммируются по следующему правилу:

A [+] B = A + B, если A + B 32 ,
A [+] B = A + B — 2 32 , если A + B >= 2 32 . A <+>B = A + B , если A + B A <+>B = A + B — (2^32 — 1), если A + B >= 2^32 — 1.

В любом случае для шифрования данных используется 256-битовый ключ K, который представляется в виде восьми 32-битовых подключей K i :

K = K 7 K 6 K 5 K 4 K 3 K 2 K 1 K 0 .

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

Режим простой замены

Первый и самый простой режим — замена. Данные, подлежащие шифрованию, разбивают на 64-битовые блоки. Процедура шифрования блока открытых данных T 0 включает 32 цикла (j=1. 32).

Блок T 0 разделяется на две последовательности по 32 бита: В(0)A(0), где В(0) — левые или старшие биты, A(0) — правые или младшие биты.

Эти последовательности вводят в накопители N 1 и N 2 перед началом первого цикла шифрования.

Первый цикл (j=1) процедуры шифрования 64-битового блока данных описывается следующими формулами:

< A(1) = f ( A(0) [+] K 0 ) (+) B(0),
B(1)=A(0).

Здесь A(1) — заполнение накопителя N 1 после 1-го цикла шифрования

< A(i) = f ( A(i-1) [+] X(j) ) (+) B(i-1),
B(i) = A(i-1), если i=25, 26. 31; j=32-i
< A(32) = A(31),
B(32) = f ( A(31) [+] X(0) ) (+) B(31),

Здесь i обозначает номер итерации (i = 1, 2. 32).

Функция f называется функцией шифрования. Ее аргументом является сумма по модулю 2 32 числа A(i), полученного на предыдущем шаге итерации, и числа X(j) ключа (размерность каждого из этих чисел равна 32 знакам).

Функция шифрования включает две операции над полученной 32-разрядной суммой. Первая операция называется подстановкой К. Блок подстановки К состоит из 8 узлов замены К(1) . К(8) с памятью 64 бит каждый. Поступающий на блок подстановки 32-разрядный вектор разбивается на 8 последовательно идущих 4-х разрядных векторов, каждый из которых преобразуется в 4-х разрядный вектор соответствующим узлом замены, представляющим собой таблицу из 16 целых чисел в диапазоне 0. 15.

Входной вектор определяет адрес строки в таблице, число из которой является выходным вектором. Затем 4-х разрядные выходные векторы последовательно объединяются в 32-разрядный вектор. Таблицы блока подстановки К содержит ключевые элементы, общие для сети ЭВМ и редко изменяемые.

Вторая операция — циклический сдвиг влево 32-разрядного вектора, полученного в результате подстановки К. 64-разрядный блок зашифрованных данных Т ш представляется в виде Т ш =A(32)B(32).

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

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

Режим гаммирования

Открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2. m, где m определяется обьемом шифруемых данных), зашифровываются в режиме гаммирования путем поразрядного сложения по модулю 2 с гаммой шифра Г ш , которая вырабатывается блоками по 64 бит, то есть Г ш = (Г(1),Г(2). Г(i). Г(m)).

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

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

Ш(i) = A (Y(i-1) [+] C2, Z(i-1) <+>C1) (+) T(i) = Г(i) (+) T(i) .
Здесь Ш(i) — 64-разрядный блок зашифрованного текста,
A — функция шифрования в режиме простой замены (аргументами этой функции являются два 32-разрядных числа),
С1 и С2 — константы, заданные в ГОСТ 28147-89,
Y(i) и Z(i) — величины, которые определяются итерационно по мере формирования гаммы следующим образом:
(Y(0), Z(0)) = A(S), где S — 64-разрядная двоичная последовательность (синхропосылка);
(Y(i), Z(i)) = (Y(i-1) [+] C2, Z(i-1) <+>C1) для i = 1, 2. m.

Расшифрование данных возможно только при наличии синхропосылки, которая не является секретным элементом шифра и может храниться в памяти ЭВМ или передаваться по каналам связи вместе с зашированными данными.

Режим гаммирования с обратной связью

Режим гаммирования с обратной связью очень похож на режим гаммирования. Как в и режиме гаммирования открытые данные, разбитые на 64-разрядные блоки Т(i) (i=1, 2. m , где m определяется обьемом шифруемых данных), зашифровываются путем поразрядного сложения по модулю 2 с гаммой шифра Г ш , которая вырабатывается блоками по 64 бит:

Число двоичных разрядов в блоке Т(m) может быть меньше 64, при этом неиспользованная для шифрования часть гаммы шифра из блока Г(m) отбрасывается.

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

Ш(1) = A(S) (+) T(1) = Г(1) (+) Т(1),
Ш(i) = A(Ш(i-1)) (+) T(i) = Г(i) (+) Т(i), для i = 2,3. m.

Здесь Ш(i) — 64-разрядный блок зашифрованного текста,
A — функция шифрования в режиме простой замены. Аргументом функции на первом шаге итеративного алгоритма является 64-разрядная синхропосылка, а на всех последующих — предыдущий блок зашифрованных данных Ш(i-1).

Bыработки имитовставки

Процесс выработки имитовстаки единообразен для любого из режимов шифрования данных.

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

Для получения имитовставки открытые данные представляются в виде 64-разрядных блоков Т(i) (i = 1, 2. m , где m определяется объемом шифруемых данных). Первый блок открытых данных Т(1) подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Причем в качестве ключа для выработки имитовставки используется ключ, по которому шифруются данные.

Полученное после 16 циклов работы 64-разрядное число суммируется по модулю 2 со вторым блоком открытых данных Т(2). Результат суммирования снова подвергается преобразованию, соответствующему первым 16 циклам алгоритма зашифрования в режиме простой замены. Полученное 64-разрядное число суммируется по модулю 2 с третьим блоком открытых данных Т(3) и т.д. Последний блок Т(m) при необходимости дополненный до полного 64-разрядного блока нулями, суммируется по модулю 2 с результатом работы на шаге m-1, после чего зашифровывается в режиме простой замены по первым 16 циклам работы алгоритма. Из полученного 64-разрядного числа выбирается отрезок Ир длиной р бит.

Имитовставка Ир передается по каналу связи или в память ЭВМ после зашифрованных данных. Поступившие зашифрованные данные расшифровываются, и из полученных блоков открытых данных T(i) вырабатывается имитовставка Ир’, которая затем сравнивается с имитовставкой Ир, полученной из канала связи или из памяти ЭВМ. В случае несовпадения имитовставок все расшифрованные данные считают ложными.

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