Математические основы криптологии и криптографические методы и средс

Шаг 4. Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S = (*У0, S\9S2, S3, SA, S5, 5б, S7). Далее значе­ ние каждого из восьми блоков заменяется на новое, которое выбира­ ется по таблице замен следующим образом: значение блока Si заме­ няется на Sriл по порядку элемент (нумерация с нуля) i-ro узла замен (т.е. 1-й строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа. Теперь становится по­ нятным размер таблицы замен: число строк в ней равно числу 4-битных элементов в 32-битном блоке данных, т.е. восьми, а число столбцов равно числу различных значений 4-битного блока данных, равному, как известно, 24, шестнадцати.

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

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

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

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

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

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

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

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

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

1. Цикл шифрования 3 2 -3 :

Д)Д . Д 2Д зД . ,К5,КвД 7Д 0Д Д гД зД Д зД б Д зД о Д Д 2Д 3Д 4,Д ,

ДД 7Д 7Д 6Д 5Д 4Д зД 2Д ,Д 0.

2.Цикл дешифрования 32 - Р:

ДД Д г Д з Д Д з Д ^ Д Д б Д Д Д з Д г Д Д о Д Д б Д з Д Д з Д г ,

ДД оД 7ДбДзД , Д зД 2Д , До.

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

А0Д1Д2Д3ДД5Д6Д7Д0Д1Д2Д3Д4Д5Д6Д7

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

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

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

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

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

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

Теперь опишем основные режимы шифрования. 4. Простая замена

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

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

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

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

5. Гаммирование Как же можно избавиться от недостатков режима простой заме­

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

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

Теперь перейдем непосредственно к описанию режима гаммирования. Гамма для этого режима получается следующим образом: с помощью некоторого алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битные блоки данных, которые далее подвергаются преобразованию по циклу 32-3, т.е. шифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуще­ ствляется при помощи одной и той же операции побитового ИСКЛЮЧАЮЩЕГО ИЛИ, алгоритмы шифрования и дешифрования в режиме гаммирования идентичны, их общая схема приведена на рис. 40,41.

РГПЧ, используемый для выработки гаммы, является рекур­ рентной функцией: Q ,+ 1 =_Д О ,), где Q , - элементы рекуррентной последовательности, /-ф ункция преобразования. Следовательно, неизбежно возникает вопрос о его инициализации, т.е. об элементе О о- В действительности, этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S, и называется в криптографии синхропосыпкой, а в нашем ГОСТе- начальным заполнением одного из регистров шифрователя. По оп­ ределенным соображениям разработчики ГОСТа решили использо­ вать для инициализации РГПЧ не непосредственно синхропосылку, а результат ее преобразования по циклу 3 2 -3 : О о = Цзг-зО^)- По­ следовательность элементов, вырабатываемых РГПЧ, целиком зави­ сит от его начального заполнения, т.е. элементы этой последователь­ ности являются функцией своего номера и начального заполнения РГПЧ: Q ,• =/{ Q о), где f{X) i(2Q), fo(X) =X. С учетом преобра­ зования по алгоритму простой замены добавляется еще и зависи­ мость от ключа:

Г,■- Ц32 - з( ^ «) - Ц32 - з(/К ^ о)) - Ц32 - з(/ХЦз2 - з(*^))) = <?,{SJK), где Г,-- i-й элемент гаммы, К - ключ.

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

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

♦период повторения последовательности чисел, вырабатывае­ мой РГПЧ, не должен сильно (в процентном отношении) от­ личаться от максимально возможного при заданном размере блока значения 264-

♦соседние значения, вырабатываемые РГПЧ, должны отли­ чаться друг от друга в каждом байте, иначе задача криптоа­ налитика будет упрощена;

♦РГПЧ должен быть достаточно просто реализуем как аппа­ ратно, так и программно на наиболее распространенных ти­ пах процессоров, большинство из которых, как известно, имеют разрядность 32 бита.

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

- в 64-битовом блоке старшая и младшая части обрабатываются независимо друг от друга: Clt = (Q?,fiJ),|Q° |=|Q} |=32, Q°+I =

= /(^?)»^}+i = 7 ( 0 j) , фактически существуют два независимых РГПЧ для старшей и младшей частей блока, рекуррентные соотно­ шения для старшей и младшей частей следующие:

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

Второе выражение нуждается в комментариях, так как в тексте ГОСТа приведено нечто другое: Q}+, =(Д{+C2)mod(232 -1 ), с тем

же значением константы С2. Но далее в тексте стандарта дается ком­ ментарий, что, оказывается, под операцией взятия остатка по модулю 232-1 там понимается не то же самое, что и в математике. Отличие заключается в том, что согласно ГОСТу (232 - l)mod(232- l) = (232—1), а не 0. На самом деле это упрощает реализацию формулы, а матема­ тически корректное выражение для нее приведено выше.

♦Период повторения последовательности для младшей части составляет 232, для старшей части 232—1, для всей последова­ тельности период составляет 232-(232-1). Первая формула из двух реализуется за одну команду, вторая, несмотря на ее

кажущуюся громоздкость, за две команды на всех современ­ ных 32-разрядных процессорах.

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