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

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

Алгоритм предусматривает четыре режима работы:

- шифрование данных в режиме простой замены;

- шифрование данных в режиме гаммирования;

- шифрование данных в режиме гаммирования с обратной связью;

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

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

В ГОСТе ключевая информация состоит из двух структур данных - собственно ключа, необходимого для всех шифров, и таблицы замен. Ключ является массивом из восьми 32-битных элементов кода (всего 256 бит). Обозначим его символом К: . Таблица замен является матрицей 8´16, содержащей 4-битовые элементы, которые можно представить в виде целых чисел от 0 до 15. Строки таблицы замен называются узлами замен, они должны содержать различные значения, то есть каждый узел замен должен содержать 16 различных чисел от 0 до 15 в произвольном порядке. Таблицу замен обозначим символом H: . Общий объем таблицы замен равен: 8 узлов ´ 16 элементов/узел ´ 4 бита/элемент = 512 бит или 64 байта.

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

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

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

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

- X – 32-битовый элемент ключа;

Шаг 1.Сложение с ключом. Младшая половина преобразуемого блока складывается по модулю 2³² с используемым на шаге элементом ключа.

Шаг 2.Поблочная замена. 32-битовое значение, полученное на предыдущем шаге, интерпретируется как массив из восьми 4-битовых блоков кода: S=(S₀,S₁,S₂,S₃,S₄,S₅,S₆,S₇). Далее значение каждого из восьми блоков заменяется на новое, которое выбирается по таблице замен следующим образом: значение блока S_i заменяется на S_i-ый по порядку элемент (нумерация с нуля) i-го узла замен (т.е. i-ой строки таблицы замен, нумерация также с нуля). Другими словами, в качестве замены для значения блока выбирается элемент из таблицы замен с номером строки, равным номеру заменяемого блока, и номером столбца, равным значению заменяемого блока как 4-битового целого неотрицательного числа.

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

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

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

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

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

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

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

Приведем этот порядок использования ключевых элементов для различных циклов.

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

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₇, K₆,K₅,K₄,K₃,K₂,K₁,K₀.

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

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₇,K₆,K₅,K₄,K₃,K₂,K₁,K₀,K₇,К₆,K₅,K₄,K₃,K₂,K₁,K₀,K₇, K₆,K₅,K₄,K₃,K₂,K₁,K₀.

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

K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇,K₀,K₁,K₂,K₃,K₄,K₅,K₆,K₇.

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

Ц_32-Р(Ц_32-З(T))=T,

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

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

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

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

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

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

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

Рассмотрим основные режимы шифрования ГОСТ 28147-89.

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

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

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

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

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

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

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

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

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

Гамма вычисляется следующим образом: с помощью заданного алгоритмического рекуррентного генератора последовательности чисел (РГПЧ) вырабатываются 64-битные блоки данных, которые далее подвергаются преобразованию по циклу 32-З, то есть зашифрованию в режиме простой замены, в результате получаются блоки гаммы. Благодаря тому, что наложение и снятие гаммы осуществляется при помощи одной и той же операции побитового «исключающего или», алгоритмы зашифрования и расшифрования в режиме гаммирования идентичны. РГПЧ, используемый для выработки гаммы, является рекуррентной функцией W_i+1=f(W_i), где W_i – элементы рекуррентной последовательности, f – функция преобразования. Неизбежно возникает вопрос об инициализации РГПЧ, то есть элементе W₀. Этот элемент данных является параметром алгоритма для режимов гаммирования, на схемах он обозначен как S, и называется в криптографии синхропосылкой, а в ГОСТ 28147-89 – начальным заполнением одного из регистров шифрователя. Разработчики ГОСТ 28147-89 используют для инициализации РГПЧ не саму синхропосылку, а результат ее преобразования по циклу 32-З: W₀=Ц_32-З(S). Последовательность элементов, вырабатываемых РГПЧ, целиком зависит от его начального заполнения, т.е. ее элементы являются функцией своего номера и начального заполнения РГПЧ. С учетом преобразования по алгоритму простой замены, добавляется еще и зависимость от ключа:

Г_i=Ц_32-З(W_i)=Ц_32-З(f_i(W₀))=Ц_32-З(f_i(Ц_32-З(S)))= W_i(S,K),

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

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

Схема алгоритма шифрования в режиме гаммирования приведена на рис. 6.8.

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

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

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

S – синхропосылка, 64-битный элемент данных, необходимый для инициализации генератора гаммы;

Шаг 1. Начальное преобразование синхропосылки, выполняемое для ее «рандомизации», то есть для устранения статистических закономерностей, присутствующих в ней, результат используется как начальное заполнение;

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

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

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

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

- период повторения последовательности чисел, вырабатываемой РГПЧ, не должен сильно отличаться от максимального при данном размере блока значения 2⁶⁴;

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

- РГПЧ должен быть достаточно просто реализуем как аппаратно, так и программно.

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

- в 64-битовом блоке старшая и младшая части обрабатываются независимо друг от друга: , фактически, существуют два независимых РГПЧ для старшей и младшей частей блока.

- рекуррентные соотношения для старшей и младшей частей следующие:

, где C₁=1010101₁₆;

, где C₂=1010104₁₆;

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

- период повторения последовательности для младшей части составляет 2³², для старшей части 2³²–1, для всей последовательности период составляет 2³² × (2³²–1).

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

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

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

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

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

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

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

При выборе размера имитовставки надо принимать во внимание, что вероятность успешного навязывания ложных данных равна величине 2^–P на одну попытку подбора. При использовании имитовставки размером 32 бита эта вероятность равна 2^–32»0.23·10^–9.

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

В заключении рассмотрим вопрос качества ключевой информации и источников ключей.

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

Если же ключи вырабатываются с помощью генератора псевдослучайных чисел, то используемый генератор должен обеспечивать указанные выше статистические характеристики, и, кроме того, обладать высокой криптостойкостью, не меньшей, чем у самого ГОСТ 28147-89. Для отбраковки ключей с плохими статистическими характеристиками могут быть использованы различные статистические критерии. На практике обычно хватает двух критериев – для проверки равновероятного распределения битов ключа между значениями 0 и 1 обычно используется критерий «хи квадрат», а для проверки независимости битов ключа – критерий серий.

В аппаратном устройстве криптографической защиты информации «КРИПТОН-4», являющемся аппаратной реализацией ГОСТ 28147-89, для генерирования ключевой информации используется аппаратно реализованный датчик случайных чисел, основанный на шумящем диоде. На рис. 6.10 представлен внешний вид устройства «КРИПТОН-4/PCI».

Рис. 6.10. Внешний вид устройства КРИПТОН-4

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