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

Алгоритм шифрования ГОСТ 28147-89, его использование и программная реализация для компьютеров платформы Intel x86.

Андрей Винокуров

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

Термины и обозначения.

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

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

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

Если элемент данных состоит из нескольких элементов меньшего размера, то этот факт обозначается следующим образом: X =(X 0 ,X 1 ,…,X n –1)=X 0 ||X 1 ||…||X n –1 . Процедура объединения нескольких элементов данных в один называется конкатенацией данных и обозначается символом «||». Естественно, для размеров элементов данных должно выполняться следующее соотношение: |X |=|X 0 |+|X 1 |+…+|X n -1 |. При задании сложных элементов данных и операции конкатенации составляющие элементы данных перечисляются в порядке возрастания старшинства. Иными словами, если интерпретировать составной элемент и все входящие в него элементы данных как целые числа без знака, то можно записать следующее равенство:

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

X =(x 0 ,x 1 ,…,x n –1)=x 0 +2 1 ·x 1 +…+2 n –1 ·x n –1 .

Таким образом, если вы обратили внимание, для ГОСТа принята т.н. «little-endian» нумерация разрядов, т.е. внутри многоразрядных слов данных отдельные двоичные разряды и их группы с меньшими номерами являются менее значимыми. Об этом прямо говорится в пункте 1.3 стандарта: «При сложении и циклическом сдвиге двоичных векторов старшими разрядами считаются разряды накопителей с большими номерами». Далее, пункты стандарта 1.4, 2.1.1 и другие предписывают начинать заполнение данными регистров-накопителей виртуального шифрующего устройства с младших, т.е. менее значимых разрядов. Точно такой же порядок нумерации принят в микропроцессорной архитектуре Intel x86, именно поэтому при программной реализации шифра на данной архитектуре никаких дополнительных перестановок разрядов внутри слов данных не требуется.

Если над элементами данных выполняется некоторая операция, имеющая логический смысл, то предполагается, что данная операция выполняется над соответствующими битами элементов. Иными словами A B =(a 0 b 0 ,a 1 b 1 ,…,a n –1 b n –1), где n =|A |=|B |, а символом « » обозначается произвольная бинарная логическая операция; как правило, имеется в виду операция исключающего или , она же – операция суммирования по модулю 2:

Логика построения шифра и структура ключевой информации ГОСТа.

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

• цикл зашифрования (32-З);
• цикл расшифрования (32-Р);
• цикл выработки имитовставки (16-З).

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

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

• что такое основной шаг криптопреобразования;
• как из основных шагов складываются базовые циклы;
• как из трех базовых циклов складываются все практические алгоритмы ГОСТа.

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

Основной шаг криптопреобразования.

Основной шаг криптопреобразования по своей сути является оператором, определяющим преобразование 64-битового блока данных. Дополнительным параметром этого оператора является 32-битовый блок, в качестве которого используется какой-либо элемент ключа. Схема алгоритма основного шага приведена на рисунке 1.

Рисунок 1. Схема основного шага криптопреобразования алгоритма ГОСТ 28147-89.

Ниже даны пояснения к алгоритму основного шага:

Шаг 0

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

Шаг 1

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

Шаг 2

Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S= (S 0 , S 1 , S 2 , S 3 , S 4 , S 5 , S 6 , S 7), причем S 0 содержит 4 самых младших, а S 7 – 4 самых старших бита S .

Далее значение каждого из восьми блоков заменяется новым, которое выбирается по таблице замен следующим образом: значение блока S i меняется на S i -тый по порядку элемент (нумерация с нуля) i -того узла замены (т.е. i -той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Отсюда становится понятным размер таблицы замен: число строк в ней равно числу 4-битовых элементов в 32-битовом блоке данных, то есть восьми, а число столбцов равно числу различных значений 4-битового блока данных, равному как известно 2 4 , шестнадцати.

Шаг 3

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

Шаг 4

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

Шаг 5

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

Шаг 6

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

Базовые циклы криптографических преобразований.

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

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

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

Цикл зашифрования 32-З:

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

Рисунок 2а. Схема цикла зашифрования 32-З

Цикл расшифрования 32-Р:

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

Рисунок 2б. Схема цикла расшифрования 32-Р

Цикл выработки имитовставки 16-З:

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

Рисунок 2в. Схема цикла выработки имитовставки 16-З.

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

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

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

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

Основные режимы шифрования.

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

• простая замена,
• гаммирование,
• гаммирование с обратной связью,

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

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

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

T о,T ш – массивы соответственно открытых и зашифрованных данных;

, – i - тые по порядку 64-битовые блоки соответственно открытых и зашифрованных данных:, , последний блок может быть неполным: ;

n – число 64-битовых блоков в массиве данных;

Ц X – функция преобразования 64-битового блока данных по алгоритму базового цикла «X».

Теперь опишем основные режимы шифрования:

Простая замена.

Зашифрование в данном режиме заключается в применении цикла 32-З к блокам открытых данных, расшифрование – цикла 32-Р к блокам зашифрованных данных. Это наиболее простой из режимов, 64-битовые блоки данных обрабатываются в нем независимо друг от друга. Схемы алгоритмов зашифрования и расшифрования в режиме простой замены приведены на рисунках 3а и б соответственно, они тривиальны и не нуждаются в комментариях.

Рисунок. 3а. Алгоритм зашифрования данных в режиме простой замены

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

Размер массива открытых или зашифрованных данных, подвергающийся соответственно зашифрованию или расшифрованию, должен быть кратен 64 битам: | T о |=| T ш |=64· n , после выполнения операции размер полученного массива данных не изменяется.

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

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

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

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

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

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битовые блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового исключающего или, алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны, их общая схема приведена на рисунке 4.

РГПЧ, используемый для выработки гаммы, является рекуррентной функцией: – элементы рекуррентной последовательности, f – функция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, то есть об элементе В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S , и называется в криптографии синхропосылкой , а в нашем ГОСТе – начальным заполнением одного из регистров шифрователя. По определенным соображениям разработчики ГОСТа решили использовать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 32-З: . Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, то есть элементы этой последовательности являются функцией своего номера и начального заполнения РГПЧ: где f i (X )=f (f i –1 (X )), f 0 (X )=X . С учетом преобразования по алгоритму простой замены добавляется еще и зависимость от ключа:

где Г i – i -тый элемент гаммы, K – ключ.

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

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

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

Исходя из перечисленных принципов, создатели ГОСТа спроектировали весьма удачный РГПЧ, имеющий следующие характеристики:

Где C 0 =1010101 16 ;

Где C 1 =1010104 16 ;

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

Второе выражение нуждается в комментариях, так как в тексте ГОСТа приведено нечто другое: , с тем же значением константы C 1 . Но далее в тексте стандарта дается комментарий, что, оказывается, под операцией взятия остатка по модулю 2 32 –1 там понимается не то же самое, что и в математике. Отличие заключается в том, что согласно ГОСТу (2 32 –1)mod (2 32 –1)=(2 32 –1), а не 0. На самом деле, это упрощает реализацию формулы, а математически корректное выражение для нее приведено выше.

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

Схема алгоритма шифрования в режиме гаммирования приведена на рисунке 4, ниже изложены пояснения к схеме:

Рисунок 4. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования.

Шаг 0

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

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

Шаг 1

Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение РГПЧ;

Шаг 2

Один шаг работы РГПЧ, реализующий его рекуррентный алгоритм. В ходе данного шага старшая (S 1) и младшая (S 0) части последовательности данных вырабатываются независимо друг от друга;

Шаг 3

Гаммирование. Очередной 64-битовый элемент, выработанный РГПЧ, подвергается процедуре зашифрования по циклу 32–З, результат используется как элемент гаммы для зашифрования (расшифрования) очередного блока открытых (зашифрованных) данных того же размера.

Шаг 4

Результат работы алгоритма – зашифрованный (расшифрованный) массив данных.

Ниже перечислены особенности гаммирования как режима шифрования:

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

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

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

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

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

где обозначает инвертированное по отношению к t значение бита ().

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

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

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

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

Рисунок 5. Алгоритм зашифрования (расшифрования) данных в режиме гаммирования с обратной связью.

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

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

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

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

Выработка имитовставки к массиву данных.

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

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

• вычисление имитовставки для заданного открытого массива информации;
• подбор открытых данных под заданную имитовставку;

Схема алгоритма выработки имитовставки приведена на рисунке 6.

Рисунок 6. Алгоритм выработки имитовставки для массива данных.

В качестве имитовставки берется часть блока, полученного на выходе, обычно – 32 его младших бита. При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2 –| I | на одну попытку подбора, если в распоряжении злоумышленника нет более эффективного метода подбора, чем простое угадывание. При использовании имитовставки размером 32 бита эта вероятность равна

Обсуждение криптографических алгоритмов ГОСТа.

Криптографическая стойкость ГОСТа.

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

• можно ли вообще раскрыть данный шифр;
• если да, то насколько это трудно сделать практически;

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

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

В ГОСТе используется 256-битовый ключ и объем ключевого пространства составляет 2 256 . Ни на одном из существующих в настоящее время или предполагаемых к реализации в недалеком будущем электронном устройстве нельзя подобрать ключ за время, меньшее многих сотен лет. Эта величина стала фактическим стандартом размера ключа для симметричных криптоалгоритмов в наши дни, – так, новый стандарт шифрования США также его поддерживает. Прежний же американский стандарт, DES с его реальным размером ключа в 56 бит и объемом ключевого пространства всего 2 56 уже не является достаточно стойким в свете возможностей современных вычислительных средств. Это было продемонстрировано в конце 90-х годов несколькими успешными попытками взлома DES переборным путем. Кроме того, DES оказался подвержен специальным способам криптоанализа, таким как дифференциальный и линейный. В этой связи DES может представлять скорее исследовательский или научный, чем практический интерес. В 1998 году его криптографическая слабость была признана официально, – национальный институт стандартов США рекомендовал использовать троекратное шифрование по DES. А в конце 2001 года был официально утвержден новый стандарт шифрования США, AES, построенный на иных принципах и свободный от недостатков своего предшественника .

Замечания по архитектуре ГОСТа.

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

Алгоритмы «основных шагов криптопреобразования» для шифров, подобных ГОСТу, построены идентичным образом, и эта архитектура называется сбалансированная сеть Файстеля (balanced Feistel network) по имени человека, впервые предложившего ее . Схема преобразования данных на одном цикле, или, как его принято называть, раунде , приведена на рисунке 7.

Рисунок 7. Содержание основного шага криптопреобразования для блочных шифров, подобных ГОСТу.

На вход основного шага подается блок четного размера, старшая и младшая половины которого обрабатываются отдельно друг от друга. В ходе преобразования младшая половина блока помещается на место старшей, а старшая, скомбинированная с помощью операции побитового « исключающего или » с результатом вычисления некоторой функции, на место младшей. Эта функция, принимающая в качестве аргумента младшую половину блока и элемент ключевой информации (X ), является содержательной частью шифра и называется его функцией шифрования . По разным соображениям оказалось выгодно разделить шифруемый блок на две одинаковые по размеру части: |N 1 |=|N 2 | – именно этот факт отражает слово «сбалансированная» в названии архитектуры. Впрочем, шифрующие несбалансированные сети также используются время от времени, хотя и не так часто, как сбалансированные. Кроме того, соображения стойкости шифра требуют, чтобы размер ключевого элемента не был меньше размера половины блока: в ГОСТе все три размера равны 32 битам.

Если применить сказанное к схеме основного шага алгоритма ГОСТ, станет очевидным, что блоки 1,2,3 алгоритма (см. рис. 1) определяют вычисление его функции шифрования, а блоки 4 и 5 задают формирование выходного блока основного шага исходя из содержимого входного блока и значения функции шифрования. Более подробно об архитектурах современных блочных шифров с секретным ключом можно прочитать в классических работах , или, в адаптированной форме, в моих работах .

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

Ни одна из рассмотренных автором реализаций DESа для платформы Intel x86 не достигает даже половины производительности предложенной вашему вниманию в настоящей статье реализации ГОСТа несмотря на вдвое более короткий цикл. Все сказанное выше свидетельствует о том, что разработчики ГОСТа учли как положительные, так и отрицательные стороны DESа, а также более реально оценили текущие и перспективные возможности криптоанализа. Впрочем, брать DES за основу при сравнении быстродействия реализаций шифров уже не актуально. У нового стандарта шифрования США дела с эффективностью обстоят гораздо лучше – при таком же как у ГОСТа размере ключа в 256 бит AES работает быстрее него примерно на 14% – это если сравнивать по числу «элементарных операций». Кроме того, ГОСТ практически не удается распараллелить, а у AES возможностей в этом плане намного больше. На некоторых архитектурах это преимущество AES может быть меньше, на других – больше. Так, на процессоре Intel Pentium оно достигает 28%. Подробности можно найти в .

Требования к качеству ключевой информации и источники ключей.

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

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

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

Ключ

Ключ должен являться массивом статистически независимых битов, принимающих с равной вероятностью значения 0 и 1. Нельзя полностью исключить при этом, что некоторые конкретные значения ключа могут оказаться «слабыми», то есть шифр может не обеспечивать заданный уровень стойкости в случае их использования. Однако, предположительно, доля таких значений в общей массе всех возможных ключей ничтожно мала. По крайней мере, интенсивные исследования шифра до сих пор не выявили ни одного такого ключа ни для одной из известных (т.е. предложенных ФАПСИ) таблиц замен. Поэтому ключи, выработанные с помощью некоторого датчика истинно случайных чисел, будут качественными с вероятностью, отличающейся от единицы на ничтожно малую величину. Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, – не меньшей, чем у самого ГОСТа. Иными словами, задача определения отсутствующих членов вырабатываемой генератором последовательности элементов не должна быть проще, чем задача вскрытия шифра. Кроме того, для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев, – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий Пирсона («хи квадрат»), а для проверки независимости битов ключа – критерий серий. Об упомянутых критериях можно прочитать в учебниках или справочниках по математической статистике.

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

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

Таблица замен

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

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

1. С помощью той или иной методики вырабатываете комплект из восьми узлов замен с гарантированными характеристиками нелинейности. Таких методик существует несколько, одна из них – использование так называемых бент-функций.
2. Проверяете выполнение простейших «критериев качества» – например, тех, что опубликованы для узлов замены DES. Вот еще несколько общих соображений на этот счет: Каждый узел замен может быть описан четверкой логических функций от четырех логических аргументов. Если эти функции, записанные в минимальной форме (т.е. с минимально возможной длиной выражения) окажутся недостаточно сложными, такой узел замены отвергается. Кроме того, отдельные функции в пределах всей таблицы замен должны отличаться друг от друга в достаточной степени. На этом этапе отсеиваются многие заведомо некачественные таблицы.
3. Для шифра с выбранными вами таблицами строите различные модели раунда, соответствующие разным видам криптоанализа, и измеряете соответствующие «профильные» характеристики. Так, для линейного криптоанализа строите линейный статистический аналог раунда шифрования и вычисляете «профильную» характеристику – показатель нелинейности. Если она оказывается недостаточной, таблица замен отвергается.
4. Наконец, используя результаты предыдущего пункта, подвергаете шифр с выбранной вами таблицей интенсивным исследованиям – попытке криптоанализа всеми известными методами. Именно этот этап является наиболее сложным и трудоемким. Но если он сделан качественно, то с высокой степенью вероятности можно констатировать, что шифр с выбранными вами таблицами не будет вскрыт простыми смертными, и, – не исключено, – окажется не по зубам спецслужбам.

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

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

Вариации на тему ГОСТа

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

Как поступить в этом и аналогичном ему случаях, чтобы увеличить быстродействие шифрования? Ответ лежит на поверхности – использовать модификацию шифра с меньшим количеством основных шагов (раундов) в базовых циклах. Во сколько раз мы уменьшаем число раундов шифрования, во столько же раз возрастает быстродействие. Указанного изменения можно достигнуть двумя путями, – уменьшением длины ключа и уменьшением числа «циклов просмотра» ключа. Вспомните, что число основных шагов в базовых циклах шифрования равно N =n·m , где n – число 32-битовых элементов в ключе, m – число циклов использования ключевых элементов, в стандарте n =8, m =4. Можно уменьшить любое из этих чисел, но простейший вариант – уменьшать длину ключа, не трогая схемы его использования.

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

Что касается устойчивости шифра к взлому «экстенсивными» методами, то есть к «переборной» атаке, тот тут все более или менее ясно: ключ размером 64 бита находится где-то на грани доступности этому виду атаки, шифр с ключом 96 бит и выше (помните, что ключ должен содержать целое число 32-битовых элементов) вполне устойчив против него. Действительно, несколько лет назад прежний стандарт шифрования США, DES, был неоднократно взломан переборным путем, – сначала его взломала вычислительная сеть, организованная на базе глобальной сети Интернет, а затем – специализированная, т.е. сконструированная специально для этого вычислительная машина. Примем, что стандартный вариант ГОСТа при программной реализации на современных процессорах работает вчетверо быстрее DES. Тогда 8-раундовый «редуцированный ГОСТ» будет работать в 16 раз быстрее DES. Примем также, что за прошедшее с момента взлома DES время производительность вычислительной техники согласно закону Мура возросла вчетверо. Получаем в итоге, что сейчас проверка одного 64-битового ключа для «редуцированного ГОСТа» с восемью циклами осуществляется в 64 раза быстрее, чем в свое время выполнялась проверка одного ключа DES. Таким образом, преимущество такого варианта ГОСТа перед DES по трудоемкости переборной атаки сокращается с 2 64–56 = 2 8 = 256 до 256/ 64 = 4 раз. Согласитесь, это весьма иллюзорное различие, почти что ничего.

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

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

С другой стороны, ГОСТ проектировался с большим запасом прочности и на сегодняшний день устойчив ко всем известным видам криптоанализа, включая дифференциальный и линейный. Применительно к ЛКА это означает, что для его успешного проведения требуется больше пар «открытый блок – зашифрованный блок», чем «существует в природе», то есть более 2 64 . С учетом сказанного выше это означает, что для успешного ЛКА 16-раундового ГОСТа потребуется не менее блоков или 2 35 байтов или 32 Гбайта данных, а для 8-раундового – не менее блоков или 2 19 байтов или 0.5 Мбайт.

Выводы из всего, сказанного выше, приведены в следующей таблице, обобщающей характеристики редуцированных вариантов ГОСТа.

Число раундов	Размер ключа, бит	Индекс быстро-действия	Вероятные характеристики шифра(очень грубая оценка)
24	192	1,33	Устойчив к большинству известных видов КА, или находиться на грани устойчивости. Практическая реализация КА невозможна из-за высоких требований к исходным данным и трудоемкости.
16	128	2	Теоретически неустойчив к некоторым видам криптоанализа, однако их практическая реализация в большинстве случаев затруднена из-за высоких требований к исходным данным и трудоемкости.
12	95	2,67	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков-сотен Кбайт) на короткий срок.
8	64	4	Неустойчив к некоторым известным видам криптоанализа, однако годится для обеспечения секретности небольших объемов данных (до десятков Кбайт) на короткий срок.

Два последних варианта, с 12 и 8 раундами, способны обеспечить весьма и весьма ограниченную во времени защиту. Их использование оправдано лишь в задачах, где требуется лишь краткосрочная секретность закрываемых данных, порядка нескольких часов. Возможная область применения этих слабых вариантов шифра – закрытие UDP-трафика электронных биржевых торговых систем. В этом случае каждый пакет данных (datagram, средняя «D» из аббревиатуры UDP) шифруется на отдельном 64-битовом ключе, а сам ключ шифруется на сеансовом ключе (ключе, область действия которого – один сеанс связи между двумя компьютерами) и передается вместе с данными.

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

У рассматриваемого вопроса есть и обратная сторона. Что если скорость шифрования некритична, а требования к стойкости весьма жестки? Повысить стойкость ГОСТа можно двумя путями – условно назовем их «экстенсивный» и «интенсивный». Первый из них – это ни что иное, как простое увеличение числа раундов шифрования. Мне не совсем понятно, зачем это может реально понадобиться, ведь отечественный стандарт и без этого обеспечивает необходимую стойкость. Впрочем, если вы страдаете паранойей больше необходимого уровня (а все «защитники информации» просто обязаны ею страдать, это условие профпригодности такое, вопрос только в степени тяжеcти случая:), это поможет вам несколько успокоиться. Если вы не уверены в этом КГБ-шном шифре или используемой вами таблице замен, просто удвойте, учетверите, и т.д. число раундов – кратность выберите исходя из тяжести вашего случая. Указанный подход позволяет реально увеличить стойкость шифра, – если раньше криптоанализ был просто невозможным, то теперь он невозможен в квадрате!

Более хитрым и интересным является вопрос, а можно ли увеличить стойкость шифра, не меняя количества и структуры основных шагов шифрования. Как ни удивительно, ответ на этот него положительный, хотя мы опять ступаем на зыбкую почву спекуляций. Дело в том, что в ГОСТе на основном шаге преобразования предполагается выполнение замены 4 на 4 бит, а на практике (речь об этом еще впереди) все программные реализации выполняют замену побайтно, т.е. 8 на 8 бит – так делается по соображениям эффективности. Если сразу спроектировать такую замену как 8-битовую, то мы существенно улучшим характеристики одного раунда. Во-первых, увеличится «диффузионная» характеристика или показатель «лавинности» – один бит исходных данных и/или ключа будет влиять на большее число бит результата. Во вторых, для больших по размеру узлов замены можно получить более низкие дифференциальную и линейную характеристики, уменьшив тем самым подверженность шифра одноименным видам криптоанализа. Особенно актуально это для редуцированных циклов ГОСТа, а для 8 и 12-раундовых вариантов такой шаг просто необходим. Это несколько скомпенсирует потерю стойкости в них от уменьшения числа раундов. Что затрудняет использование этого приема – так это то, что конструировать подобные «увеличенные» узлы замены вам придется самостоятельно. А также то, что более крупные узлы вообще конструировать заметно труднее, чем меньшие по размеру.

Нестандартное использование стандарта.

Безусловно, основное назначение криптоалгоритмов ГОСТ – это шифрование и имитозащита данных. Однако им можно найти и другие применения, связанные, естественно, с защитой информации. Коротко расскажем о них:

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

• Как уже отмечалось выше, гамму можно использовать как «сырье» для выработки ключей. Для этого нужно лишь получить отрезок гаммы нужной длины – 32 байта. Таким способом ключи можно изготавливать по мере необходимости и их не надо будет хранить, – если такой ключ понадобится повторно, будет достаточно легко его выработать снова. Надо только будет вспомнить, на каком ключе он был выработан исходно, какая использовалась синхропосылка и с какого байта выработанной гаммы начинался ключ. Вся информация, кроме использованного ключа, несекретна. Данный подход позволит легко контролировать достаточно сложную и разветвленную систему ключей, используя всего лишь один «мастер-ключ».
• Аналогично предыдущему, гамму можно использовать в качестве исходного «сырья» для выработки паролей. Тут может возникнуть вопрос, зачем вообще нужно их генерировать, не проще ли по мере надобности их просто выдумывать. Несостоятельность такого подхода была наглядно продемонстрирована серией инцидентов в компьютерных сетях, самым крупным из которых был суточный паралич интернета в ноябре 1988 года, вызванный «червем Морриса». Одним из способов проникновения злоумышленной программы на компьютер был подбор паролей: программа пыталась войти в систему, последовательно перебирая пароли из своего внутреннего списка в несколько сотен, причем в значительной доле случаев ей это удавалось сделать. Фантазия человека по выдумыванию паролей оказалась весьма бедной. Именно поэтому в тех организациях, где безопасности уделяется должное внимание, пароли генерирует и раздает пользователям системный администратор по безопасности. Выработка паролей чуть сложнее, чем выработка ключей, так как при этом «сырую» двоичную гамму необходимо преобразовать к символьному виду, а не просто «нарезать» на куски. Кроме того, отдельные значения, возможно, придется отбросить, чтобы обеспечить равную вероятность появления всех символов алфавита в пароле.
• Еще один способ использования криптографической гаммы – гарантированное затирание данных на магнитных носителях. Дело в том, что даже при перезаписи информации на магнитном носителе остаются следы предыдущих данных, которые может восстановить соответствующая экспертиза. Для уничтожения этих следов такую перезапись надо выполнить многократно. Оказалось, что потребуется перезаписывать информацию на носитель меньшее количество раз, если при такой процедуре использовать случайные или псевдослучайные данные, которые останутся неизвестными экспертам, пытающимся восстановить затертую информацию. Гамма шифра здесь будет как нельзя кстати.

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

• Мы знаем, что один из таких вариантов использования ГОСТа – выработка имитовставки для массивов данных. Однако на базе любого блочного шифра, и ГОСТа в том числе, достаточно легко построить схему вычисления односторонней хэш-функции, называемой также в литературе MDC, что в разных источниках расшифровывается как код обнаружения изменений / манипуляций (M odification/M anipulation D etection C ode) или дайджест сообщения (M essage D igest C ode). Первая расшифровка появилась в литературе гораздо раньше, вторую, более короткую, я думаю, придумали те, кому оказалось не под силу запомнить первую:), – это была шутка. MDC может непосредственно использоваться в системах имитозащиты в качестве аналога имитовставки, не зависящего, однако, от секретного ключа. Кроме того, MDC широко используется в схемах электронно-цифровой подписи (ЭЦП), ведь большинство таких схем сконструированы таким способом, что подписывать удобно блок данных фиксированного размера. Как известно, на базе обсуждаемого стандарта ГОСТ 28147-89 построен стандарт Российской Федерации на вычисление односторонней хэш-функции ГОСТ Р34.11-94 .
• Менее известно, что на базе любого блочного шифра, и ГОСТа в том числе, может быть построена вполне функциональная схема ЭЦП, с секретным ключом подписи и открытой проверочной комбинацией. По ряду причин эта схема не получила широкого практического распространения, однако в отдельных случаях до сих пор может рассматриваться как весьма привлекательная альтернатива доминирующим ныне в мире «математическим» схемам ЭЦП.

Литература

Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования ГОСТ 28147-89. Гос. Ком. СССР по стандартам, М., 1989. ftp://ftp.wtc-ural.ru/pub/ru.crypt/GOST-28147
Шеннон Клод. Математическая теория секретных систем. В сборнике «Работы по теории информации и кибернетике», М., ИЛ, 1963, с. 333-369. http://www.enlight.ru/crypto/articles/shannon/shann__i.htm
Announcing Approval of Federal Information Processing Standard (FIPS) 197, Advanced Encryption Standard (AES), Federal Register Vol. 66, No. 235 / Thursday, December 6, 2001 / Notices, pp 63369–63371. http://csrc.nist.gov/encryption/aes/
Файстель Хорст. Криптография и компьютерная безопасность. Перевод А.Винокурова по изданию Horst Feistel. Cryptography and Computer Privacy, Scientific American, May 1973, Vol. 228, No. 5, pp. 15-23. http://www.enlight.ru/crypto/articles/feistel/feist_i.htm
Шнайер Брюс. Прикладная криптография. 2-е изд. Протоколы, алгоритмы и исходные тексты на языке Си., М., «Триумф», 2002 http://www.ssl.stu.neva.ru/psw/crypto/appl_rus/appl_cryp.htm
Menezes Alfred, van Oorschot Paul, Vanstone Scott. Handbook of applied cryptography. ttp://www.cacr.math.uwaterloo.ca/hac/
Винокуров Андрей. Как устроен блочный шифр? Рукопись. http://www.enlight.ru/crypto/articles/vinokurov/blcyph_i.htm
Винокуров Андрей. Выпуски по криптографии для электронного журнала iNFUSED BYTES online. http://www.enlight.ru/crypto/articles/ib/ib.htm
Винокуров Андрей, Применко Эдуард. Текст доклада «О программной реализация стандартов шифрования РФ и США», конференция по информатизации, Москва, МИФИ, 28-29 января 2001г. Опубликован в материалах конференции.
Информационная технология. Криптографическая защита информации. Функция хэширования ГОСТ Р34.11-94, Госстандарт РФ, М., 1994.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

• «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.

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

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

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

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

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

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

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

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

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

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

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

В заключение приведем таблицу, содержащую данные обо всех известных международному криптографическому сообществу результатах строго описанных и обоснованных атак на ГОСТ 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
	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 не позволяет определять ключ с трудоемкостью меньшей полного перебора.

«Пока ты жив, не умирай, на этот мир взгляни.
У многих здесь душа мертва – они мертвы внутри.
Но ходят и смеются, не зная, что их нет,
Не торопи свой смертный час» – она сказала мне.

Ария, «Там высоко»

1. Введение

1. Предварительные сведения о блочных шифрах

2.1 Сети Файстеля.
2.2 Блочный шифр ГОСТ 28147-89

1. Теоретический минимум

3.1 Ключевая информация
3.2 Основной шаг криптопреобразования

3.3 Базовые циклы: “ 32-З ” , “ 32-Р ” .

1. Практика

4.1 Реализация основного шага криптопреобразования
4.2 Увеличение быстродействия алгоритма
5.
6. Список использованной литературы
7. Благодарности.

Введение.

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

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

Предварительные сведения о блочных шифрах.

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

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

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

2.1 Сети Файстеля

Предложенная Файстелем архитектура нового метода шифрования в классической литературе получила название «Архитектура Файстеля», но на данный момент в русской и зарубежной литературе используется более устоявшийся термин – «сеть Файстеля» или Feistel`s NetWork. В последствии по данной архитектуре был построен шифр «Люцифер» — который позднее был опубликован и вызвал новую волну интереса к криптографии в целом.

Идея архитектуры «сети Файстеля» заключается в следующем: входной поток информации разбивается на блоки размером в n битов, где n четное число. Каждый блок делится на две части – L и R, далее эти части подаются в итеративный блочный шифр, в котором результат j-го этапа определяется результатом предыдущего этапа j-1! Сказанное можно проиллюстрировать на примере:

Рис. 1

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

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

Для того чтобы идея сетей Файстеля была окончательна ясна, рассмотрим простейший случай изображенный на рис. 1 , где в функции А – выступит операции “mod 2” (“xor”), но это простейший случай, в более серьезной ситуации, например сокрытие информации государственной важности функция А может быть более сложной (сколько я видел функция А действительно бывает очень сложной):

Исходные данные:

L = 1110b, R = 0101, K = 1111b

Получить шифрограмму

1. (R + K) mod 2 4 = Smod, Smod = 0100b
2. (Smod + L) mod 2 = Sxor, Sxor = 1010b
3. L = R, R = Sxor

L = 0101b, R = 1010b

Поясним наши действия:

1. Эта операция сложение по mod 2 4 . На практике такая операция сводится к простому сложению, где мы должны сложить два числа и проигнорировать перенос в 5й разряд. Так как, если проставить над разрядами двоичного представления числа проставить показатели степени, над пятым разрядом как раз будет показатель четыре, взглянем на рисунок ниже, где изображены действия нашей операции:

Рис. 2

Здесь я стрелкой указал на показатели степени, как видно, результат должен был получиться 10100, но так как при операции mod 2 4 игнорируется перенос, мы получаем 0100.

1. Эта операция в литературе называется mod 2, на языке ассемблера реализуется командой XOR . Но ее более правильное название mod 2 1 . Без этой уникальной операции вряд ли можно построить быстрый, легко реализуемый алгоритм шифрования и при этом, чтобы он был еще довольно криптостойким. Уникальность этой операции заключается в том, что она сама себе обратная! К примеру, если число А поXORить с числом Б, в результате получим В, в дальнейшем достаточно переXORить числа Б и В между собой, чтобы получить прежнее значение А!

В этой операции мы получили 1010 имея числа 1110 и 0100, чтобы получить обратно 1110, достаточно переXORрить между собой числа 0100 и 1010! Более подробно об этой операции можно почитать в статье, которая вложена на сайте www.wasm.ru , «Элементарное руководство по CRC_алгоритмам обнаружения ошибок » автор, которой Ross N. Williams . В этом труде есть пункт — «5. Двоичная арифметика без учета переносов ». Вот именно в этой статье и описана операция xor! Я восклицаю потому что в этой статье эта операция так расписана, что читатель не просто понимает как работает эта операция, он даже начинает ее видеть, слышать и чувствовать!

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

2.2 Блочный шифр ГОСТ 28147-89

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

Для работы данного метода алгоритма необходимо разбить информацию на блоки размером в 64 бита. Сгенерировать или ввести в систему шифрования, следующую ключевую информацию: ключ и таблицу замен. К выбору ключа и таблицы замен при шифровании следует отнестись очень серьезно, т.к. именно это фундамент безопасности вашей информации. О том, какие требования налагаются на ключ, и таблицу замен смотри пункт «Требования к ключевой информации».

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

Теоретический минимум.

3.1 Ключевая информация

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

3.1.1. Ключ – это последовательность восьми элементов размером в 32 бита каждый. Далее будем обозначать символом К, а элементы из которых он состоит – k1,k2,k3,k4,k5,k6,k7,k8.

3.1.2 Таблица замен – матрица из восьми строк и шестнадцати столбцов, в дальнейшем – Hij. Каждый элемент на пересечении строки i и столбца j занимает 4 бита.

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

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

1. Сложение часть блока R суммируется с элементом ключа K по mod 2 32 . О подобной операции я описал выше, здесь тоже самое только показатель степени не «4», а «32» — результат этой операции в дальнейшем буду обозначать Smod.
2. Полученный ранее результат Smod делим на четырех битные элементы s7,s6,s5,s4,s3,s2,s1,s0 и подаем в функцию замены. Замена происходит следующим образом: выбирается элемент Smod — s i , с начала начинаем с младшего элемента, и заменяем значением из таблицы замен по i — той строке и столбцу, на который указывает значение элемента s i . Переходим к s i +1 элементу и поступаем аналогичным образом и продолжаем так, пока не заменим значение последнего элемента Smod – результат этой операции будем обозначать как, Ssimple.
3. В этой операции значение Ssimple сдвигаем циклически влево на 11 бит и получаем Srol.
4. Выбираем вторую часть блока L и складываем по mod 2 с Srol, в итоге имеем Sxor.
5. На этой стадии часть блока L становится равным значению части R, а часть R в свою очередь инициализируется результатом Sxor и на этом функция основного шага завершена!

3.3 Базовые циклы: “32-З”, “32-Р”.

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

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

K = k1,k2,k3,k4,k5,k6,k7,k8

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

Базовые циклы имеют, как бы это сказать, маркировку: n – m. Где n – количество основных шагов криптопреобразования в базовом цикле, а m – это «тип» базового цикла, т.е. о чем идет речь, о «З» ашифровывании или «Р» асшифровывании данных.

Базовый цикл шифрования 32–З состоит из 32-х основных шагов криптопреобразования. В функцию реализующую действия шага подают блок N и элемент ключа К причем, первый шаг происходит с к1, второй над полученным результатом с элементом к2 и т.д. по следующей схеме:

k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8,k1,k2,k3,k4,k5,k6,k7,k8k8,k7,k6,k5,k4,k3,k2,k1

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

k1,k2,k3,k4,k5,k6,k7,k8,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1,k8,k7,k6,k5,k4,k3,k2,k1

Практика.

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

Исходные данные:

Возьмем блок информации N = 0102030405060708h, здесь части L и R равны:

L = 01020304h, R =05060708h, возьмем ключ:

K = ‘as28 zw37q839 7342ui23 8e2twqm2 ewp1’ (это ASCII – коды, для того, чтобы посмотреть шестнадцатеричное представление, можно открыть этот файл в режим просмотра в Total Commander нажав на клавишу «F3 » и далее клавишу «3 »). В этом ключе значения элементов будут:

k1 = ‘as28’, k2 = ‘zw37’, k3 = ‘q839’, k4 = ‘7342’

k5 = ‘ui23’, k6 = ‘8e2t’, k7 = ‘wqm2’, k8 = ‘ewp1’

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

Рис. 3

Здесь строки нумеруются от 0 до 7, столбцы от 0 до F.

Предупреждение: Вся информация, в том числе и ключ с таблицей замен взята в качестве примера для рассмотрения алгоритма!

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

1. Выбираем часть R = 05060708h и элемент ключа k1 = ‘as28’, в шестнадцатеричном виде элемент ключа будет выглядеть так: 61733238h. Теперь же делаем операцию суммирования по mod 2 32:

Рис. 4

Как видно на рисунке у нас не произошло переноса в 33 бит помеченный красным цветом и с показателем степени «32 ». А если бы у нас были бы другие значения R и элемента ключа – это вполне могло бы произойти, и тогда бы мы его проигнорировали, и в дальнейшем использовали только биты, помеченные желтым цветом.

Такую операцию я выполняю командой ассемблера add :

; eax = R, ebx = ‘as28’

Результат этой операции Smod = 66793940h

1. Теперь самая заковыристая операция, но если присмотреться по внимательней, то она уже не такая страшная, как кажется в первое время. Представим Smod в следующем виде:

РИСУНОК НЕ СОХРАНЕН

Рис. 5

Я постарался наглядно представить элементы Smod на рисунке, но все равно поясню:

s0 = 0, s1 = 4, s2 = 9 и т.д.

Теперь начиная с младшего элемента s0, производим замену. Вспоминая пункт «3.2 Основной шаг криптопреобразования » i ­– строка, s i – столбец, ищем в нулевой строке и нулевом столбце значение:

Рис.6

Таким образом, текущее значение Smod, не 66793940 h, а 66793945 h.

Приступаем заменять s1, т.е. четверку. Используя первую строку и четвертый столбец (s1= 4!). Глядим на рисунок:

Рис. 7

Теперь уже значение Smod, не 6679394 5h, 6679392 5h. Я предполагаю, что теперь алгоритм замены читателю понятен, и я могу сказать, что после конечный результат Ssimple будет иметь следующее значение – 11e10325h.

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

1. Полученное значение Ssimple мы должны сдвинуть на 11 бит влево.

Рис. 8

Как видно это действие довольно простое, и реализуется одной командой языка ассемблера – rol и результат этой операции Srol равен 0819288Fh.

1. Теперь же остается часть L нашего блока информации поXORить со значением Srol. Я беру калькулятор от w2k sp4 и получаю Sxor = 091b2b8bh.
2. Это действие итоговое и мы просто присваиваем, чисти R значение части L, а часть L инициализируем значением Sxor.

Конечный результат:

L = 091b2b8bh, R = 01020304h

4.2 Увеличения быстродействия алгоритма

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

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

1. Выбрал часть блока L в регистр eax, а R в edx.
2. В регистр esi инициализировал адресом расширенного ключа, об этом ниже.
3. В регистр ebx присваивал значение адреса расширенной таблицы замен, об этом тоже ниже
4. Передавал информацию пунктов 1,2, 3 в функцию базового цикла 32 – З или 32 – Р, в зависимости от ситуации.

Если посмотреть на схему подачи элементов ключа в пункте «Базовые циклы: “32-З”, “32-Р” », то наш ключ для базового цикла 32 – З можно представить в следующем:

К 32-З =

‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,

‘as28’,‘zw37’,‘q839’,‘7342’,‘ui23’,‘8e2t’,‘wqm2’,‘ewp1’,

‘ewp1’,‘wqm2’,‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’

Т.е. с начала идут k1,k2,k3,k4,k5,k6,k7,k8 — ‘ as28’, ‘ zw37’, ‘ q839’, ‘7342’, ‘ ui23’, ‘8 e2 t’, ‘ wqm2’, ‘ ewp1’ три раза эта последовательность повторяется. Затем элементы идут в обратном порядке, т.е.: k8,k7,k6,k5,k4,k3,k2,k1 — ‘ewp1’, ‘wqm2’, ‘8e2t’,‘ui23’,‘7342’,‘q839’,‘zw37’,‘as28’ .

Я заранее расположил в массиве элементы в том порядке, как они должны подаваться в 32 – З. Тем самым я увеличил память, требуемую под ключ, но избавил себя от некоторых процессов мышления, которые мне были не нужны, и увеличил скорость работы алгоритма, за счет уменьшения времени обращения к памяти! Здесь я описал только ключ для 32 – З, для цикла 32 – Р я поступил аналогично, но используя другую схему подачи элементов, которую я тоже описывал в пункте «Базовые циклы: “32-З”, “32-Р ».

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

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

К примеру, нам потребовалось заменить, число 66793940h. Представлю его в следующем виде:

РИСУНОК НЕ СОХРАНЕН

Рис. 9

Теперь если взять элементы s1,s0, т.е. младший байт, то результат функции замены будет равен 25h! Почитав статью Андрея Винокурова, которую я привел в пункте «Список используемой литературу », вы действительно обнаружите, что если взять две строки можно получить массив, позволяющий быстро находить элементы замены с помощью команды ассемблера xlat. Говорят можно и другим способом более быстрым, но Андрей Винокуров потратил на исследование быстрых алгоритмов для реализации ГОСТа около четырех лет! Думаю, не стоит изобретать велосипед, когда он уже есть.

Итак, о массиве:

Возьмем две первые строки нулевую и первую, создадим массив на 256 байт. Теперь наблюдаем одну особенность, что если надо преобразовать 00h, то результат будет 75h (опираемся на рис.3) – кладем это значение в массив на смещение 00h. Берем значение 01h, результат функции замен 79h, кладем его в массив на смещение 01 и так далее до 0FFh, которое нам даст 0FCh, которое мы положим в массив по смещение 0FFh. Вот мы и получили расширенную таблицу замен для первой группы строк: первой и нулевой. Но еще есть три группы: вторая стр.2, стр.3, третья стр.4, стр. 5, четвертая стр.6, стр.7. С этим тремя группами поступаем тем же способом, что и с первой. Результат – расширенная таблица замен!

Теперь можно реализовать алгоритм, который будет производить замену. Для этого берем исходные коды, которые выложил Андрей Винокуров на своей страничке, смотри «Список используемой литературы ».

lea ebx,extented_table_simple

mov eax,[положить число которое нужно заменить]

add ebx,100h ;переход к двум следующим узлам

sub ebx,300h ; чтобы в дальнейшем ebx показывал на таблицу

Теперь еще одна особенность, предыдущими действиями мы не только заменили, но и сдвинули число на 8 бит влево! Нам остается только сдвинуть число еще на 3 бита влево:

и мы получаем результат операции rol eax,11!

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

Требования к ключевой информации.

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

— критерий равновероятного распределения битов между значениями 1 и 0. Обычно в качестве критерия равновероятного распределения битов – выступает критерий Пирсона («хи-квадрат»).

Это значит ключом, в принципе может любое число. То есть при формировании очередного бита ключа вероятность его инициализации единицей или нулем 50/50!

Прошу заметить, что ключ из восьми элементов, каждый по 32 бита, таким образом всего в ключе 32*8 = 256 битов и количество возможных ключей 2 256 ! Тебя это не поражает? 🙂

— критерий серий.

Если мы посмотрим на наш ключ, который я привел в пункте «4.1 Реализация основного шага криптопреобразования », то вы заметите, что справедлива следующая запись:

Рис. 10

Одной фразой значение k 1 не должно повториться не в k 2 , не в каком либо другом элементе ключа.

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

Теперь про выбор таблицы замен:

Теперь же поговорим о том, как правильно выбрать таблицу замен. Основное требование к выбору таблиц замен – это явление «неповторяемости» элементов, каждый из которых размером в 4 бита. Как вы уже видели выше, каждая строка таблицы замен состоит из значений 0h, 1h, 2h, 3h, …, 0fh. Так вот основное требование гласит о том, что в каждой строке есть значения 0h, 1h, 2h, … , 0fh и каждое такое значение в одном экземпляре. К примеру, последовательность:

1 2 3 4 5 6 7 8 9 A B C D E F

Вполне соответствует этому требованию, но все же! Такую последовательность в качестве строки выбирать не рекомендуется. Так как если вы подадите значение на вход функции, которая опирается на такую строку, то на выходе вы получите такое же значение! Не верите? Тогда возьмите число 332DA43Fh и восемь таких строк, в качестве таблицы замен. Проведите операцию замены, и уверяю вас, на выходе вы получите число 332DA43Fh! То есть такое же, что вы подали на вход операции! А это не является признаком хорошего тона при шифровании, да и являлось ли? 🙂

Это было одно требование, следующий критерий говорит о том, что – каждый бит выходного блока должен быть статистически независим от каждого бита входного блока!

Как это выглядит проще? А вот как, к примеру, мы выбрали из приведенного выше числа элемент s0 = 0Fh, 01111b. Вероятность того, что мы сейчас заменим первый бит единицей или нулем равна 0,5! Вероятность замены второго, третьего и четвертого бита, каждый бит, рассматриваем по отдельности, единицами или нулями тоже равна 0, 5. При выборе s1 = 0Eh, вероятность того, что мы нулевой бит, а это «0», заменим нулем или единицей тоже равна – 0,5! Таким образом, согласно этому критерию между заменой нулевых битов элементов s0, s1 нет никакой закономерности! Да, вы могли заменить единицами, но вы также могли поставить и нули. 🙂

Для оценки таблицы по этому критерию можно построить таблицу коэффициентов корреляции, рассчитанные по формуле:

— если p = 1, то значение бита j на выходе равно значению бита i на входе при любых комбинациях бит на входе;

— если p = -1, то значение бита j на выходе всегда является инверсией входного бита i;

— если p = 0, то выходной бит j с равной вероятностью принимает значения 0 и 1 при любом фиксированном значении входного бита i.

Возьмем пример одной строки:

D	B	4	1	3	F	5	9	0	A	E	7	6	8	2	C

Разложим на «составляющие»:

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

— берем 0-й бит 0-ого числа (0) на входе и 0-й бит 0-ого числа на выходе (1) проводим операцию 0 XOR 1 = 1.

— берем 0-й бит 1-ого числа (1) на входе и 0-й бит 1-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.

— берем 0-й бит 2-ого числа (0) на входе и 0-й бит 2-ого числа на выходе (0) проводим операцию 0 XOR 0 = 0.

— берем 0-й бит 3-ого числа (1) на входе и 0-й бит 3-ого числа на выходе (1) проводим операцию 1 XOR 1 = 0.

Проведя последовательно операции XOR в такой последовательности, подсчитываем количество всех ненулевых значений, получаем значение 6. Отсюда P 00 = 1-(6/2 4-1) = 0,25. Итак, выяснилось, что значение бита 0 на выходе равно значению бита 0 на входе в 4-х случаях из 16-ти;

Итоговая таблица коэффициентов:

Таблица коэффициентов будет следующая (кому не лениво может пересчитать)

	Вход
Выход		0	1	2	3
	0	-0,25	0,00	0,00	0,00
	1	0,00	1,00	0,00	0,00
	2	0,00	0,00	1,00	0,00
	3	0,00	0,00	0,00	-0,50

Ну, в этой таблице дела обстоят еще хуже – биты 1 и 2 группы остаются неизменными! Криптоаналитику есть, где развернуться 🙂 С учетом всех этих требований простым перебором («в лоб») были найдены таблицы перестановки соответствующие указанной теории (на сегодняшний день – 1276 сочетаний) Вот некоторые из них:

09 0D 03 0E-06 02 05 08-0A 07 00 04-0C 01 0F 0B

00 05 0A 07-03 08 0F 0C-0E 0B 04 09-0D 06 01 02

06 0B 0F 00-0C 01 02 0D-08 07 09 04-05 0A 03 0E

04 0E 00 09-0B 01 0F 06-03 0D 07 0A-0C 02 08 05

04 02 08 0E-05 0F 03 09-0B 01 0D 07-0A 0C 06 00

07 03 09 0C-08 00 06 0F-0E 04 01 0A-0D 0B 02 05

06 0F 03 08-0D 04 0A 01-09 02 05 0C-00 0B 0E 07

0C 06 08 01-03 09 07 0E-0B 05 0F 02-04 0A 00 0D

04 0B 09 06-0E 01 00 0F-0A 05 03 0C-0D 02 07 08

00 0E 0F 01-07 08 09 06-04 0B 0A 05-03 0D 0C 02

0F 09 01 07-04 0A 08 06-0E 00 02 0C-05 03 0B 0D

0A 03 04 01-05 0C 0B 0E-08 06 0F 0D-07 09 00 02

0B 06 0F 01-04 0A 08 05-00 0D 0C 02-07 09 03 0E

0C 03 02 08-0D 06 0B 05-07 09 04 0F-0A 00 01 0E

02 0B 0F 04-09 00 06 0D-05 0E 01 08-0C 07 0A 03

Список использованной литературы.

1. Статья Андрея Винокурова:

Алгоритм шифрования ГОСТ 28147-89, его использование и реализация

для компьютеров платформы Intel x86.

(можно найти по адресу: http://www.enlight.ru/crypto/frame.htm).

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

1. Статья Хорста Файстеля:

Криптография и Компьютерная безопасность.

(можно найти по тому же адресу что и предыдущую статью)

1. Ross N. Williams:

Элементарное руководство по CRC алгоритмам обнаружения ошибок

Выложена на сайте www. wasm. ru .

Благодарности.

Хотелось бы высказать благодарность всем посетителям форума www.wasm.ru. Но особо бы хотелось бы поблагодарить ChS, который в настоящий момент известен, как SteelRat, он помог мне понять такие вещи, чего я бы, наверное, никогда бы не понял, а так же помощь при написании пункта: «Требования к ключевой информации », основной часть данного пункта была написана им. Также глубоко признателен сотруднику КГТУ им. А.Н. Туполева Аникину Игорю Вячеславовичу и грех было бы не отметить Криса Касперски, за то, что он есть и Volodya / wasm.ru за его наставления. Ох, и достается мне от него:). Так же хочу отметить Sega-Zero / Callipso зато, что донес до моего разума некоторые математические дебри.

Это, пожалуй, все, что я хотел бы сказать вам.

Буду, признателен за критику или вопросы, связанные с этой статьей или просто советы. Мои контактные данные: [email protected], ICQ – 337310594.

С уважением Evil`s Interrupt.

P.S.: Этой статьей я не старался кого-то перещеголять. Она была написана с умыслом, облегчить изучение ГОСТа и если у вас получились трудности, то это не значит, что я повинен в этом. Будь разумны, и наберитесь терпения, всего вам доброго!

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

В отличие от американского DES в отечественном стандарте применяется более длинный ключ – 256 бит . Кроме того, российский стандарт предлагает использовать 32 раунда шифрования, тогда как DES – только 16.

Таким образом, основные параметры алгоритма криптографического преобразования данных ГОСТ 28147-89 следующие: размер блока составляет 64 бита, размер ключа – 256 бит , количество раундов – 32.

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

В алгоритме шифрования используются следующие операции :

• сложение слов по модулю 2 32 ;
• циклический сдвиг слова влево на указанное число бит;
• побитовое сложение по модулю 2;
• замена по таблице.

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

Структура раунда ГОСТ 28147-89

Структура одного раунда ГОСТ 28147-89 приведена на рис. 5.1 .

Шифруемый блок данных разбивается на две части, которые затем обрабатываются как отдельные 32-битовые целые числа без знака. Сначала правая половина блока и подключ раунда складываются по модулю 2 32 . Затем производится поблочная подстановка . 32-битовое значение , полученное на предыдущем шаге (обозначим его S ), интерпретируется как массив из восьми 4-битовых блоков кода: S=(S 0 ,S 1 ,S 2 ,S 3 ,S 4 ,S 5 ,S 6 ,S 7) . Далее значение каждого из восьми блоков заменяется на новое, которое выбирается по таблице замен следующим образом: значение блока S i заменяется на S i -тый по порядку элемент ( нумерация с нуля) i-го узла замен (т.е. i-той строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент c номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. В каждой строке таблицы замен записаны числа от 0 до 15 в произвольном порядке без повторений. Значения элементов таблицы замен взяты от 0 до 15 , так как в четырех битах, которые подвергаются подстановке, может быть записано целое число без знака в диапазоне от 0 до 15 . Например, первая строка S-блока может содержать такие значения: 5, 8, 1, 13, 10, 3, 4, 2, 14, 15, 12, 7, 6, 0, 9, 11 . В этом случае значение блока S 0 (четыре младших бита 32-разрядного числа S) заменится на число, стоящее на позиции, номер которой равен значению заменяемого блока. Если S 0 = 0 , то оно заменится на 5 , если S 0 = 1 , то оно заменится на 8 и т.д.

Рис. 5.1.

После выполнения подстановки все 4-битовые блоки снова объединяются в единое 32-битное слово , которое затем циклически сдвигается на 11 битов влево. Наконец, с помощью побитовой операции "сумма по модулю 2" результат объединяется с левой половиной, вследствие чего получается новая правая половина R i . Новая левая часть L i берется равной младшей части преобразуемого блока: L i = R i-1 .

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

Процедуры шифрования и расшифрования

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

Рассмотрим процесс создания подключей раундов. В ГОСТ эта процедура очень проста, особенно по сравнению с DES . 256-битный ключ K разбивается на восемь 32-битных подключей, обозначаемых K 0 , K 1 , K 2 ,K 3 , K 4 , K 5 , K 6 , K 7 . Алгоритм включает 32 раунда, поэтому каждый подключ при шифровании используется в четырех раундах в последовательности, представленной на таблица 5.1 .

Таблица 5.1. Последовательность использования подключей при шифровании

Раунд	1	2	3	4	5	6	7	8
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	9	10	11	12	13	14	15	16
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	17	18	19	20	21	22	23	24
Подключ	K 0	K 1	K 2	K 3	K 4	K 5	K 6	K 7
Раунд	25	26	27	28	29	30	31	32
Подключ	K 7	K 6	K 5	K 4	K 3	K 2	K 1	K 0

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

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

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

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

Рис. 2.21.

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

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

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

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

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

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

2. Табличная замена. После наложения ключа подблок R i разбивается на восемь частей но 4 бита, значение каждой из которых по отдельности заменяется в соответствии со своей таблицей замены (S-блоком). Всего используется восемь S-блоков - S 0 , S, S 2 , S 3 , S 4 , S 5 , S 6 , S 7 . Каждый S-блок алгоритма ГОСТ 28147-89 представляет собой вектор (одномерный массив) с ^элементами, пронумерованными от 0 до 15. Значениями S-блока являются 4-битовые числа, т.е. целые числа от 0 до 15.

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

Пример 2.6.

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

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

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

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

Таблица 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).

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

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

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

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

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

Стандарт ГОСТ Р 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, что соответствует принятой международной практике. Эти режимы применимы как к шифру «Магма», так и к новому шифру «Кузнечик».

• Осуществляется побитовый циклический сдвиг влево на 11 битов. Расшифрование осуществляется по этой же схеме, но с другим расписаниемиспользования ключей: с 1-го по 8-й раунд расшифровки - в прямом порядке: с 9-го по 32-й раунд расшифровки - в обратном порядке: По сравнению с шифром DES у ГОСТ 28147-89 есть следующие достоинства: существенно более длинный ключ (256 бит против 56 у шифра DES),атака на который путем полного перебора ключевого множества на данныймомент представляется невыполнимой; простое расписание использования ключа, что упрощает реализациюалгоритма и повышает скорость вычислений. Проектирование S-блоков ГОСТ 28147-89. Очевидно, что схема алгоритма ГОСТ 28147-89 весьма проста. Это означает, что наибольшая нагрузка по шифрованию ложится именно на таблицы замен. Значения таб-
• Панасепко С. П. Алгоритмы шифрования: специальный справочник. СПб.: БХВ-Петер-бург, 2009.
• Kara О. Reflection Attacks on Product Ciphers. URL: http://eprint.iacr.org/2007/043.pdf
• Российский стандарт шифрования: стойкость снижена. URL: http://cryptofaq.ru/index.php/2010-12-23-18-20-21/2010-12-23-18-22-09/90-2011-02-01-07-47-27
• Ачексеев Е. К., Смышляев С. В. ГОСТ 28147-89: «Не спеши его хоронить».