Криптографические методы защиты информации

Лекции

6. ШИФРЫ ГАММИРОВАНИЯ

 

6.1. Основы шифрования.

6.2. Генерация случайных последовательностей.

6.2.1. Генерация истинно случайных последовательностей.

6.2.2. Генерация псевдослучайных последовательностей.

6.3. Отличие ключа от гаммы.

6.4. Стандарты и спецификации США.

Вопросы для самопроверки.

 

6.1. Основы шифрования

 

Шифры гаммирования (аддитивные шифры) являются самыми эффективными с точки зрения стойкости и скорости преобразований (процедур зашифрования и дешифрования). По стойкости данные шифры относятся к классу совершенных. Для зашифрования и дешифрования используются элементарные арифметические операции – открытое/зашифрованное сообщение и гамма, представленные в числовом виде, складываются друг с другом по модулю (mod). Напомним, что результатом сложения двух целых чисел по модулю является остаток от деления (например, 5+10 mod 4 = 15 mod 4 = 3).

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

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

Ci = (Pi + Ki) mod N,          (6.1)

Pi = (Ci + N - Ki) mod N,          (6.2)

где Pi, Ci - i-ый символ открытого и шифрованного сообщения;
N - количество символов в алфавите;
Кi - i-ый символ гаммы (ключа).

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

Таблица 6.1. Таблица кодирования символов

АБВГДЕЁЖЗИЙКЛМНОПРСТУФХЦЧШЩЪЫЬЭЮЯ
01234567891011121314151617181920212223242526272829303132

Например, для шифрования используется русский алфавит (N = 33), открытое сообщение – «АБРАМОВ», гамма – «ЖУРИХИН». При замене символов на числа буква А будет представлена как 0, Б – 1, …, Я – 32. Результат шифрования показан в следующей таблице.

Таблица 6.2. Пример аддитивного шифрования по модулю N = 33

С
и
м
в
о
л
открытого
сообщения, Pi
АБРАМОВ
0117013152
гаммы, KiЖУРИХИН
72017922914
шифрограммы, CiЖФБИВЧП
7211922416

Сложение по модулю 2 (шифр Вернама). Значительный успех в криптографии связан с именем американца Гильберто Вернама [15]. В 1917 г. он, будучи сотрудником телеграфной компании AT&T, совместно с Мейджором Джозефом Моборном предложил идею автоматического шифрования телеграфных сообщений. Речь шла о своеобразном наложении гаммы на знаки алфавита, представленные в соответствии с телетайпным кодом Бодо пятизначными «импульсными комбинациями». Например, буква A представлялась комбинацией («– – – + +»), а комбинация («+ + – + +») означала перехода от букв к цифрам. На бумажной ленте, используемой при работе телетайпа, знаку «+» соответствовало наличие отверстия, а знаку «–» - его отсутствие. При считывании с ленты металлические щупы проходили через отверстия, замыкали электрическую цепь и, тем самым, посылали в линию импульс тока.

Рис.6.1. Шифровальная машина Siemens M-190 [www.cryptomuseum.com]

Вернам предложил электромеханически покоординатно складывать «импульсы» знаков открытого текста с «импульсами» гаммы, предварительно нанесенными на ленту. Сложение проводилось «по модулю 2» (, для булевых величин аналог этой операции – XOR, «Исключающее ИЛИ»). Имеется в виду, что если «+» отождествить с 1, а «–» с 0, то сложение определяется двоичной арифметикой:

0 1
0 0 1
1 1 0

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

Ci = Pi Ki,          (6.3)

Pi = Ci Ki.          (6.4)

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

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

Шифры гаммирования стали использоваться немцами в своих дипломатических представительствах в начале 1920-х гг., англичанами и американцами – во время Второй мировой войны. Разведчики-нелегалы ряда государств использовали шифрблокноты1. Шифр Вернама применялся на правительственной «горячей линии» между Вашингтоном и Москвой, где ключевые материалы представляли собой перфорированные бумажные ленты, производившиеся в двух экземплярах [23].

Рис.6.2. Одноразовый шифровальный блокнот (СССР, ГДР, 1960-е гг.) [www.cryptomuseum.com]

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

Таблица 6.3. Коды символов Windows 1251 и их двоичное представление

БукваDec-кодBin-кодБукваDec-кодBin-кодБукваDec-кодBin-код
А1921100 0000Л2031100 1011Ц2141101 0110
Б1931100 0001М2041100 1100Ч2151101 0111
В1941100 0010Н2051100 1101Ш2161101 1000
Г1951100 0011О2061100 1110Щ2171101 1001
Д1961100 0100П2071100 1111Ъ2181101 1010
Е1971100 0101Р2081101 0000Ы2191101 1011
Ж1981100 0110С2091101 0001Ь2201101 1100
З1991100 0111Т2101101 0010Э2211101 1101
И2001100 1000У2111101 0011Ю2221101 1110
Й2011100 1001Ф2121101 0100Я2231101 1111
К2021100 1010Х2131101 0101

Примечание. Dec-код – десятичный код символа, Bin-код – двоичный код символа.

Пример шифрования сообщения «ВОВА» с помощью ключа «ЮЛЯ» показан в следующей таблице. Так как длина ключа меньше длины открытого сообщения, то для генерации гаммы он циклически повторяется.

Таблица 6.4. Пример аддитивного шифрования по модулю 2

Открытое
сообщение, Pi
БукваВОВА
Dec-код194206194192
Bin-код1100 00101100 11101100 00101100 0000
Гамма, KiБукваЮЛЯЮ
Dec-код222203223222
Bin-код1101 11101100 10111101 11111101 1110
Шифрограмма, CiDec-код2852930
Bin-код0001 11000000 01010001 11010001 1110

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

Таблица 6.5. Пример использования ложной гаммы

Шифрограмма, CiDec-код2852930
Bin-код0001 11000000 01010001 11010001 1110
Ложная гамма, K'iБукваЮЕМБ
Dec-код222197204193
Bin-код1101 11101100 01011100 11001100 0001
Ложное
открытое
сообщение, P'i
Dec-код194192209223
Bin-код1100 00101100 00001101 00011101 1111
БукваВАСЯ

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

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

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

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

- была случайной (должна отсутствовать закономерность в появлении символов гаммы);

- символы алфавита гаммы были распределены нормально (равновероятно);

- совпадала по размеру или была больше исходного открытого текста;

- применялась только один раз.

Первые два свойства (требования) проверяются с помощью различных тестов. Наиболее популярный и авторитетный из них «Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографических приложений» (англ. NIST SP 800-22 «A statistical test suite for random and pseudorandom number generators for cryptographic applications»), включающий в себя 15 тестов.


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

 

6.2. Генерация случайных последовательностей

 

Несмотря на все достоинства шифров гаммирования, одной из ключевых проблем их применения на практике является получение качественных гамм. Для процедур зашифрования/дешифрования можно использовать истинно случайные или псевдослучайные гаммы (последовательности). Псевдослучайная последовательность – последовательность чисел, которая была вычислена по определённой процедуре, но имеет все свойства случайной последовательности чисел в рамках решаемой задачи. Отличие истинно случайных последовательностей от псевдослучайных заключается в невозможности предсказания (расчета, определения) символов в ней. Таким образом, любой алгоритмически устроенный программно-аппаратный комплекс не может генерировать истинно случайные последовательности, т.к. он работает по строго определенным правилам, а значит результат (гамма) предсказуем. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений» [63].

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

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


2Рекуррентная формула - формула вида an = f(n, an-1, an-2, …, an-p), определяющая каждый член последовательности an, как функцию от p предыдущих членов и возможно номера члена последовательности n.

 

6.2.1. Генерация истинно случайных последовательностей

 

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

Среди физических процессов, которые рассматривались в качестве источника случайных последовательностей, можно выделить следующие [17, 64]:

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

- тепловой шум – равновесный шум, обусловленный тепловым движением носителей заряда в проводнике, в результате чего на концах проводника возникает флуктуирующая разность потенциалов. В микропроцессорах Intel с архитектурой Ivy Bridge для аппаратной генерации случайных последовательностей используется тепловой шум в кристаллах кремния [65]. Для усиления энтропии3 поток битов проходит дополнительную фильтрацию и шифрование AES в режимах CBC и CRT;

Рис.6.3. Микропроцессор Core i7-3770 с архитектурой Ivy Bridge и инструкцией генерации случайных чисел RdRand

- движение жидкостей в лавовых лампах. Компания CloudFlare, через сеть которой проходит до 10% траффика Интернета, в качестве одного из источников случайных последовательностей использует стену с сотней лавовых ламп;

Рис.6.4. «Стена энтропии» в компании CloudFlare

- движение ленточек в потоке воздуха вентилятора;

Рис.6.5. Хаотичное движение ленточек в потоке воздуха

- радиоактивный распад – спонтанное изменение состава или внутреннего строения нестабильных атомных ядер путём испускания элементарных частиц, гамма-квантов и/или ядерных фрагментов. Компания CloudFlare в качестве одного из источников случайных последовательностей использует радиоактивный элемент;

Рис.6.6. Счетчик Гейгера

- электромагнитное излучение – электромагнитные волны, возникающие при возмущении магнитного или электрического поля. Генераторы случайных последовательностей на базе квантовых явлений предлагает большое количество компаний (ID Quantique, QuintessenceLabs, ComScire и др.);

Рис.6.7. Квантовый генератор случайных чисел [www.idquantique.com/random-number-generation/overview]

- лавинный пробой в полупроводниках – электрический пробой p-n-перехода, вызванный лавинным размножением носителей заряда под действием сильного электрического поля;

     

Рис.6.8. Устройство ChaosKey [altusmetrum.org/ChaosKey]

- нестабильная частота свободно работающего осциллятора. Компания RAND использовала это явление для публикации в 1955 г. книги «Миллион случайных цифр со стандартным отклонением 100 000», а компания AT&T в 1986 г. представила коммерческую микросхему-генератор [66].

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

- время между нажатиями клавиш;

- движения компьютерной мыши;

- изменение скорости вращения жесткого диска, вызванного турбулентностью воздуха [8];

- время между принятыми пакетами в сети (например, пинг сайта Google).

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

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

- медленная скорость генерации числовых последовательностей;

- антропогенные процессы могут иметь скрытые зависимости – каждый пользователь обладает своим «подчерком» работы с компьютером.

В заключение обзора генераторов истинно случайных последовательностей рассматривается оригинальный метод, предложенный в 2013 г. учеными Корнельского университета [42]. Кратко принцип нового метода шифрования заключается в том, что отправитель и получатель (Алиса и Боб) во время встречи формируют общий ключ, облучая кусочки стекла изображением-паттерном с IDi (внешне он напоминает QR-код). В результате отражения и преломления, характер которого индивидуален для каждого куска стекла, у Алисы и Боба получаются собственные случайные изображения, которые затем оцифровываются (получаются ключи keyAi и keyBi). Из этих изображений и составляется общий ключ (keyABi = keyAi keyBi).

Схема генерации одного общего ключа показана на следующем рисунке.

Рис.6.9. Схема генерации одного общего ключа

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

Процедура обмена шифрограммами выглядит следующим образом.

Рис.6.10. Схема зашифрования и дешифрования сообщения

1) Алиса выбирает паттерн с IDi, облучает свой кусочек стекла и оцифровывает полученное изображение, получая ключ keyAi.

2) Исходное сообщение Pi Алиса складывает по модулю 2 с ключом keyAi (Ci = Pi keyAi) и отсылает шифрограмму Ci с идентификатором паттерна IDi Бобу.

3) Боб по полученному идентификатору IDi из общедоступного хранилища считывает общий ключ keyABi и, облучая паттерн с IDi и свой кусочек стекла, генерирует собственный ключ keyBi.

4) Складывая по модулю 2 ключи keyABi и keyBi, Боб получает ключ keyAi (keyAi = keyABi keyBi).

5) Для прочтения исходного сообщения Pi Боб складывает по модулю 2 шифрограмму Ci и ключ keyAi (Pi = Ci keyAi).

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

- потеря кусочка стекла;

- появление сколов и царапин на стекле;

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


3Информационная энтропия – мера неопределённости или непредсказуемости информации, неопределённость появления какого-либо символа первичного алфавита.

 

6.2.2. Генерация псевдослучайных последовательностей

 

Генераторы псевдослучайных последовательностей получили наибольшее распространение. По схеме использования они делятся на синхронные и самосинхронизирующиеся [8, 23].

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

Рис.6.11. Схема шифрования с использованием синхронных генераторов

При этом генератор гаммы, как правило, состоит из трех основных блоков.

Рис.6.12. Устройство генератора гаммы с внутренней обратной связью

Внутреннее состояние описывает текущее состояние генератора гаммы. Начальное внутреннее состояние, как правило, определяется ключом K. Два генератора, с одинаковым ключом и одинаковым внутренним состоянием, создают одинаковые гаммы. Функция переходов считывает текущее внутреннее состояние и генерирует новое внутреннее состояние. Выходная функция считывает внутреннее состояние и генерирует бит (биты) гаммы Ki.

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

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

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

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

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

Рис.6.13. Схема шифрования с использованием самосинхронизирующихся генераторов гаммы

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

Недостатки самосинхронизирующегося генератора.

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

2. При потере бита Ci необходимо заново передать часть сообщения, но в отличие от синхронных генераторов, синхронизация намного проще.

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

В качестве иллюстрации ниже приведены некоторые из них.

А) Рекуррентные формулы:

- линейный конгруэнтный генератор;

- инверсный конгруэнтный генератор;

- аддитивный генератор;

- регистр сдвига с линейной обратной связью.

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

Xi+1 = (a Xi + b) mod m,          (6.5)

где a, b и m – некоторые коэффициенты.

Агоритм RANDU - один из вариантов линейного конгруэнтного генератора псевдослучайных чисел, десятилетиями использовавшийся на мейнфреймах. Он определяется рекуррентным соотношением:

Xi+1 = (65539 Xi) mod 231,          (6.6)

где X0 - нечётное.

Пример псевдослучайной последовательности, порождаемой алгоритмом RANDU при начальном значении X0 = 1:

1
65 539
393 225
1 769 499
7 077 969
26 542 323
...
388 843 697
238 606 867
79 531 577
477 211 307
1
   (повтор для элемента № 536 870 913)

.

К сожалению, линейные конгруэнтные генераторы нельзя использовать в криптографии, т.к. они предсказуемы. Впервые линейные конгруэнтные генераторы были взломаны Джимом Ридсом, а затем Джоан Бояр [8]. Ей удалось также вскрыть квадратичные генераторы

Xi+1 = (a Xi2 + b Xi + с) mod m          (6.7)

и кубические генераторы

Xi+1 = (a Xi3 + b Xi2 + c Xi + d) mod m.          (6.8)

А.2) Инверсный конгруэнтный генератор (генератор Эйхенауэра – Лена) – генератор псевдослучайных чисел, в котором новый член последовательности рассчитывается как обратное число к предыдущему по модулю. Общая формула генератора выглядит следующим образом:

Xi+1 = (a Xi-1 + b) mod m,          (6.9)

где a, b и m – некоторые коэффициенты, 0 ≤ a < m, 0 ≤ b < m.

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

А.3) Аддитивный генератор (запаздывающий генератор Фибоначчи) – генератор псевдослучайных чисел, в котором новый член последовательности зависит более чем от одного из предшествующих. Одна из ранних реализаций генератора последовательности Фибонначи с запаздыванием была предложена 1958 г. Дж. Ж. Митчелом и Д. Ф. Муром:

Xi+1 = (Xi-a + Xi-b) mod m,          (6.10)

где a = 24, b = 55 – запаздывание, b > a ≥ 1;
X0 .. X54 – произвольные целые числа;
m – чётное число.

Более сложные реализации аддитивных генераторов применяются в алгоритмах Fish, Pike, Mush и др.

A.4) Регистр сдвига с линейной обратной связью (РСЛОС) – упорядоченный набор битов, у которого значение входного (вдвигаемого слева, старшего) бита равно линейной булевой функции от значений остальных битов регистра до сдвига. Теорию последовательности регистров сдвига разработал в 1965 г. главный криптограф норвежского правительства Эрнст Селмер [8].

Длиной регистра называется количества битов в нем. В качестве булевой функции для РСЛОС чаще всего используют сложение по модулю 2. Такие РСЛОС обычно записывают в виде многочлена (полинома) или упорядоченной последовательности. Запись x8 + x4 + x3 + x2 + 1 или (8, 4, 3, 2, 0) означает, что длина регистра 8 битов, а входной бит рассчитывается по формуле b7 = b4 b3 b2 b0 (для битов нумерация начинается справа и с нулевой позиции). Выходной (выдвигаемый справа, младший) бит будет являться частью генерируемой гаммы. Расчет требуемой гаммы осуществляется в цикле, на каждой итерации которого выполняются следующие операции.

1. Добавление выходного бита b0 к гамме.

2. Расчет входного бита bn-1 по формуле.

3. Сдвиг битов регистра вправо на одну позицию.

4. Занесение рассчитанного входного бита bn-1 в позицию n-1.

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

Таблица 6.6. Пример генерации гаммы для РСЛОС x8 + x4 + x3 + x2 + 1

№ п/пИсходное состояние регистраБит гаммы,
b0
Входной бит,
b7 = b4 b3 b2 b0
Сдвиг регистра вправо на одну позициюЗанесение входного бита b7 в регистр
0
10001100
0 0 1 1 0 = 0
 1000110
01000110
1
01000110
0 0 0 1 0 = 1
 0100011
10100011
2
10100011
1 0 0 0 1 = 1
 1010001
11010001
3
11010001
1 1 0 0 1 = 0
 1101000
01101000
4
01101000
0 0 1 0 0 = 1
 0110100
10110100
..................
Гамма00110... 

Для регистра длиной n максимальное количество состояний (период гаммы) составляет 2n–1 (Это число равно 2n–1, а не 2n, поскольку заполнение РСЛОС нулями влечет вывод регистром бесконечной последовательности нулей, что совершенно бесполезно). Для получения такого максимального периода многочлен должен быть примитивным по модулю 2. Примитивный многочлен степени n – неприводимый многочлен, который является делителем , но не является делителем xd+1 для всех d, являющихся делителями 2n–1. Чем больше битов регистра используются для расчета входного бита, тем лучше (повышается стойкость). Многочлены с большим количеством членов называют плотными, с малым – разреженными.

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

Б) Алгоритмы:

- алгоритм Блюм - Блюм - Шуба;

- RC4;

- Trivium;

- генератор на базе иррациональных чисел.

Б.1) Алгоритм Блюм - Блюм - Шуба (англ. Algorithm Blum - Blum - Shub, BBS) предложен в 1986 г. Ленор Блюм, Мануэлем Блюмом и Майклом Шубом.

Рекуррентная формула BBS выглядит следующим образом:

Xi+1 = Xi2 mod m,          (6.11)

где m = p * q – является произведением двух больших простых p и q, сравнимых с 3 по модулю 4.

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

Пример с использованием двух малых простых чисел.

p = 7 (7 mod 4 = 3) и q = 19 (19 mod 4 = 3).
m = 7 * 19 = 133.
X0 = 53.

Таблица 6.7. Пример генерации гаммы по алгоритму BBS

№ п/пXЧетный
паритетный
бит
Младший
бит
2 младших
бита
Dec-кодBin-код
0531101010101
116100001000
212311110110111
310011001001000
425110011101
Гамма01011…10101…0100110001…

Как было отмечено выше, X0 должно быть взаимно простым с m. Если для генерации последовательности с параметрами p = 7, q = 19 и m = 133 выбрать X0 = 57 = 3 * 19, то она будет состоять из одних Xi = 57 (572 mod 133 = 57). Таким образом период последовательности будет равным 1, что не лучшим образом сказывается на качестве гаммы. Слишком малый период может возникать и в случае, когда X0 и m взаимно просты. Например, если при тех же параметрах выбрать X0 = 130, то последовательность будет выглядеть: 130, 9, 81, 44, 74, 23, 130, ...

Особенностью этого алгоритма является то, что для получения Xn необязательно вычислять все n - 1 предыдущих чисел, если известно начальное состояние генератора X0 и числа p и q, то n-ное значение может быть вычислено по формуле:

.          (6.12)

Б.2) RC4 (от англ. Rivest cipher или Ron’s code) был создан сотрудником компании «RSA Security» Рональдом Ривестом в 1987 г. В течение семи лет шифр являлся коммерческой тайной, и точное описание алгоритма предоставлялось только после подписания соглашения о неразглашении, но в сентябре 1994 г. его описание было анонимно отправлено в список рассылки «Cypherpunks» [17].

Этап 1. Инициализация S-блока.

Перед генерацией гаммы выполняется инициализация S-блока длиной Ls. Обычно Ls выбирается кратно 8 битов (28 = 256, 216 = 65536 и т.п.). Для инициализации используется ключ K длиной LK от 40 до 2048 битов по следующему алгоритму.

1. Цикл A. Для i := 0 до Ls - 1

1.1. S[i] := i

2. j := 0

3. Цикл B. Для i := 0 до Ls - 1

3.1. j := (j + S[i] + K[i mod LK]) mod Ls

3.2. Поменять местами S[i] и S[j]

Этап 2. Генерация гаммы.

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

1. i := 0

2. j := 0

3. L := 0

4. Цикл. Пока L < Lg

4.1. i := (i + 1) mod Ls

4.2. j := (j + S[i]) mod Ls

4.3. Поменять местами S[i] и S[j]

4.4. t := (S[i] + S[j]) mod Ls

4.5. Блок гаммы := S[t]

4.6. L := L + Ls

RC4 получил широкое распространение в криптосистемах и протоколах, в частности [17]:

- WEP (англ. Wired Equivalent Privacy) — алгоритм для обеспечения безопасности сетей Wi-Fi;

- WPA (англ. Wi-Fi Protected Access) — обновленный алгоритм сертификации устройств сетей Wi-Fi;

- BitTorrent protocol encryption — протоколы пиринговых файлообменных сетей;

- SSL (англ. Secure Sockets Layer) — криптографический протокол передачи данных в сети;

- Kerberos — сервер аутентификации Kerberos;

- PDF (англ. Portable Document Format) — межплатформенный формат электронных документов, разработанный фирмой Adobe Systems;

- Skype — программное обеспечение IP-телефонии;

- и др.

Обнаруженные уязвимости в стандартной реализации RC4 привели к отказу от его использования в некоторых криптосистемах и протоколах, а также появлению различных его модификаций: RC4A, RC4+, VMPC, Spritz.

Б.3) Trivium был представлен в 2008 г. как часть европейского проекта eSTREAM по профилю 2 (аппаратно ориентированные шифры) и в настоящий момент имеет статус международного стандарта «ISO/IEC 29192-3:2012. Информационные технологии - Методы безопасности - Легкая криптография - Часть 3: Поточные шифры» (англ. «ISO/IEC 29192-3:2012. Information technology - Security techniques - Lightweight cryptography - Part 3: Stream ciphers»). Авторами генератора (шифра) являются Кристоф Де Канньер и Барт Пренел [17].

По аналогии с RC4 процедура выработки гаммы состоит из двух этапов: инициализации S-блока и непосредственно генерации гаммы.

Этап 1. Инициализация S-блока.

Длина S-блока составляет 288 битов. При этом он условно делится на 3 части длинами 93, 84 и 111 битов. В первую часть S1 заносится 80-битовый ключ К с добавлением 13 нулевых битов, во вторую часть S2 заносится 80-битовый вектор инициализации IV с добавлением 4 нулевых битов и в последнюю часть S3 заносятся нулевые биты за исключением трех последних единичных битов. После первоначальной инициализации в цикле осуществляется связывание битов из разных частей со сдвигами битов вправо в каждой из них. Весь алгоритм инициализации выглядит следующим образом.

1. S1 = (s1, s2, ..., s93) := (K1, K2, ..., K80, 0, ..., 0)

2. S2 = (s94, s95, ..., s177) := (IV1, IV2, ..., IV80, 0, ..., 0)

3. S3 = (s178, s179, ..., s288) := (0, ..., 0, 1, 1, 1)

4. Цикл. Для i := 1 до 288

4.1. t1 := s66 (s91 s92) s93 s171

4.2. t2 := s162 (s175 s176) s177 s264

4.3. t3 := s243 (s286 s287) s288 s69

4.4. Сдвиг первой части на один бит вправо S1 := (_, s1, s2, ..., s92)

4.5. Занесение t3 в первую позицию первой части S1 := (t3, s1, s2, ..., s92)

4.6. Сдвиг второй части на один бит вправо S2 := (_, s94, s95, ..., s176)

4.7. Занесение t1 в первую позицию второй части S2 := (t1, s94, s95, ..., s176)

4.8. Сдвиг третьей части на один бит вправо S3 := (_, s178, s179, ..., s287)

4.9. Занесение t2 в первую позицию третьей части S3 := (t2, s178, s179, ..., s287)

Этап 2. Генерация гаммы.

Для генерации гаммы длиной Lg в каждой итерации цикла на основе 15 битов S-блока вычисляется один бит гаммы и выполняются операции, идентичные рассмотренным в инициализации S-блока. Алгоритм генерации следующий.

1. L := 0

2. Цикл. Пока L < Lg

2.1. Бит гаммы := s66 s93 s162 s177 s243 s288

2.2. t1 := s66 (s91 s92) s93 s171

2.3. t2 := s162 (s175 s176) s177 s264

2.4. t3 := s243 (s286 s287) s288 s69

2.5. Сдвиг первой части на один бит вправо S1 := (_, s1, s2, ..., s92)

2.6. Занесение t3 в первую позицию первой части S1 := (t3, s1, s2, ..., s92)

2.7. Сдвиг второй части на один бит вправо S2 := (_, s94, s95, ..., s176)

2.8. Занесение t1 в первую позицию второй части S2 := (t1, s94, s95, ..., s176)

2.9. Сдвиг третьей части на один бит вправо S3 := (_, s178, s179, ..., s287)

2.10. Занесение t2 в первую позицию третьей части S3 := (t2, s178, s179, ..., s287)

2.11. L := L + 1

Существуют упрощенные модификации генератора гаммы Univium, Bivium, Trivium-toy и Bivium-toy.

Б.4) Иррациональное число – вещественное число, которое не является рациональным, т.е. не может быть представлено в виде обыкновенной дроби , где m, n – натуральные числа. К наиболее известным иррациональным числам относятся , , , ln2, e и π [17].

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

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

- отсутствие доказательства нормальности чисел;

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

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

В качестве примера рассмотрим число π.

Равновероятность появления цифр в записи (≈ нормальность) числа π не доказана, хотя анализ первых 200 млрд. десятичных цифр говорит в пользу этого.

Таблица 6.8. Количество появлений десятичных цифр в первых 200 млрд. знаках числа π

ЦифраКоличество появлений
020 000 030 841
119 999 914 711
220 000 136 978
320 000 069 393
419 999 921 691
519 999 917 053
619 999 881 515
719 999 967 594
820 000 291 044
919 999 869 180

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

Важным достижением в области расчетов числа π стала формула Бэйли – Боруэйна – Плаффа, открытая в 1997 г. Саймоном Плаффом и названная в честь авторов статьи, в которой она впервые была опубликована [67].

.          (6.13)

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


4Взаимно простые числа – числа, не имеющие общих делителей, кроме 1, т.е. наибольший общий делитель которых равен 1.

 

6.3. Отличие ключа от гаммы

 

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

Для иллюстрации отличий приведена следующая таблица.

Таблица 6.9. Отличия ключа от гаммы

Метод генерации гаммыКлючГамма
На базе случайных физических или антропогенных процессовКлюч соответствует гамме
На базе слова или фразы
(см. табл. 6.2 и 6.4)
Слово или фразаЦиклически повторяющееся слово или фраза
Линейный или инверсный конгруэнтный генераторНачальное число и коэффициенты формулГенерируемая числовая последовательность
Регистр сдвига с линейной обратной связьюВид полинома и исходное состояние регистраГенерируемая числовая последовательность
RC4Ключ КЧисловая последовательность из частей S-блока
На базе числа πНомер начальной позиции в дробной части, с которой выбираются цифры числа πПоследовательность цифр числа π, начиная с заданной позиции

 

6.4. Стандарты и спецификации США

 

Развитая система стандартов и спецификаций по генерации и тестированию псевдослучайных последовательностей существует в США. ANSI (Американский национальный институт стандартов – англ. American national standards institute) и NIST (Американский национальный институт стандартизации – англ. National Institute of Standards and Technology) разработали следующие документы:

- стандарты ANSI серии X9.82:

- ANSI X9.82 «Random Number Generation. Part 1: Overview and Basic Principles» (рус. «Генерация случайных чисел. Часть 1: Обзор и основные принципы»);

- ANSI X9.82 «Financial Services - Random Number Generation. Part 2: Entropy Sources» (рус. «Финансовые услуги – Генерация случайных чисел. Часть 2: Источники энтропии»);

- ANSI X9.82 «Random Number Generation. Part 3: Deterministic Random Bit Generators» (рус. «Генерация случайных чисел. Часть 3: Детерминированные генераторы случайных битов»);

- ANSI X9.82 «Random Number Generation. Part 4: Random Bit Generator Constructions» (рус. «Генерация случайных чисел. Часть 4: Конструкции генератора случайных битов»);

- специальные публикации NIST серии 800:

- NIST SP 800-22 Rev.1a «A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications» (рус. «Набор статистических тестов для генераторов случайных и псевдослучайных чисел для криптографического приложений»);

- NIST SP 800-90A «Recommendation for Random Number Generation Using Deterministic Random Bit Generators» (рус. «Рекомендации для генерации случайных чисел с использованием детерминированных генераторов случайных битов»).

 

Вопросы для самопроверки

 

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

2. Назовите основные характеристики гаммы.

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

4. Опишите схемы шифрования с использованием синхронных и самосинхронизирующихся потоковых шифров.