Содержание к диссертации
Введение
Глава 1. Теория, применение и оценка качества генераторов псевдослучайных последовательностей (ПСП) 13
1.1. Задачи, решаемые с использованием генераторов ПСП 13
1.2. Обзор функций генераторов ПСП в защищенных программных системах 14
1.3. Требования к генераторам ПСП. 17
1.4. Оценка качества генераторов ПСП 18
1.5. Формулировка целей работы и постановка задач исследования 19
1.6. Выводы 20
Глава 2. Исследование эллиптических алгоритмов обеспечения безопасности информации (ОБИ) 21
2.1. Основы теории эллиптических алгоритмов 21
2.1.1. Введение 21
2.1.2. Группа 21
2.1.3. Конечное поле 22
2.1.4. Группа точек эллиптической кривой 26
2.1.5. Математические основы преобразований на эллиптических кривых 27
2.2. Анализ атак на ECDLP 41
2.2.1. Полный перебор (Exhaustive Search) 42
2.2.2. Атака Полига-Хеллмана (Pohlig-Hellman Attack) 42
2.2.3. Алгоритм маленьких и больших шагов Шэнкса
(Baby-step Giant-step) 45
2.2.4. р-алгоритм Полларда (Pollard's р method) 46
2.2.5. Ылетод Полларда (Pollard's X method) 49
2.3. Выводы 49
Глава 3. Исследование и разработка эллиптических алгоритмов формирования ПСП 51
3.1. Эллиптические алгоритмы формирования ПСП 51
3.1.1. Эллиптические генераторы ПСП на основе функции след 51
3.1.2. Эллиптические генераторы ПСП на основе регистров сдвига с линейными обратными связями 55
3.1.3. Эллиптические алгоритмы формирования ПСП на основе линейных конгруэнтных генераторов 60
3.1.4. Эллиптические алгоритмы формирования ПСП на основе инверсивного конгруэнтного генератора 62
3.1.5. Генераторы ПСП на основе статической и динамической экспоненты 63
3.1.6. Эллиптические генераторы ПСП на основе умножения матриц 67
3.1.7. Эллиптические генераторы ПСП на основе нелинейного фильтра 68
3.1.8. Эллиптические генераторы ПСП на основе NR функции 70
3.2. Исследование быстродействия и статистической безопасности эллиптических алгоритмов генерации ПСП 72
3.3. Выводы 73
Глава 4. Разработка и исследование быстродействующих алгоритмов генерации ПСП 74
4.1. Разработка и исследование программных средств генерации ПСП на основе стохастических сумматоров 74
4.1.1. Стохастическое преобразование информации. R-блоки ... 74
4.1.2. Регистры сдвига со стохастическими обратными связями 76
4.1.3. Хеширование с использованием R-блоков 77
4.1.4. Модификация существующих алгоритмов 77
4.1.5. Разработка нелинейных стохастических генераторов ПСП длиной 2 78
4.1.6. Разработка блоков стохастического преобразования над конечными полями GF(p) 79
4.1.7. Исследование и разработка генераторов ПСП RpFSR 80
4.1.8. Аддитивные генераторы по модулю р 83
4.2. Исследование и программная реализация дихотомических генераторов ПСП 87
4.2.1. Простейший дихотомический (нелинейный) счетчик 87
4.2.2. Простейший одномерный дихотомический генератор 88
4.2.3. Простейший двухмерный (дуальный) дихотомический генератор 89
4.3. Выводы 90
Глава 5. Разработка программного комплекса «Стохастические эллиптические алгоритмы обеспечения безопасности информации»... 92
5.1. Структура комплекса 92
5.2. Реализация стохастических эллиптических алгоритмов 95
5.2.1. Схема симметричного преобразования на эллиптических кривых (Symmetric ECES) 95
5.2.2. Схема асимметричного преобразования на эллиптических кривых (Asymmetric ECES) 96
5.2.3. Схема электронной цифровой подписи на эллиптических кривых (ECSS) 98
5.2.4. Схема электронной цифровой подписи на эллиптических кривых (ECDSA) 101
5.2.5. Протокол выработки общего секретного ключа (ЕСКЕР) 102
5.2.6. Протокол аутентификации на эллиптических кривых (ЕСКАР) 105
5.2.7. Схема преобразования с использованием сеансового ключа (ECES-SK) 107
5.2.8. Схема формирования ЭЦП и преобразования на эллиптических кривых (ECSCS) 109
5.2.9. Схема формирования слепой ЭЦП 113
5.2.10. Реализации стенографического скрытия информации с использованием протокола ECES 117
5.2.11. Протокол доказательства с нулевым разглашением знаний (Elliptic Curve-Zero-Knowledge Proof) 119
5.3. Выводы 120
Заключение 121
Список источников информации
- Обзор функций генераторов ПСП в защищенных программных системах
- Математические основы преобразований на эллиптических кривых
- Эллиптические генераторы ПСП на основе регистров сдвига с линейными обратными связями
- Стохастическое преобразование информации. R-блоки
Введение к работе
Актуальность темы. Важным элементом любой защищенной компьютерной системы (КС), независимо от ее сложности и назначения, являются программные и программно-аппаратные средства генерации псевдослучайных последовательностей (ПСП). Можно выделить следующие задачи защиты программных систем, для решения которых используются генераторы ПСП:
Обеспечения секретности или конфиденциальности информации;
Обеспечения аутентичности (целостности, подлинности) объектов (массивов данных, сообщений) информационного взаимодействия;
Обеспечения аутентичности (подлинности) субъектов информационного взаимодействия (удаленных абонентов);
Обеспечения неотслеживаемости информационных потоков в системе;
Обеспечения правильности функционирования компонентов системы в любой момент времени, в том числе отсутствия недокументированных возможностей;
Обеспечения своевременного доступа пользователей к необходимой им информации или компонентам системы (защиты от случайных и умышленных деструктивных воздействий, в том числе от вредоносных программ);
Защиты авторских прав, прав собственников информации, обеспечения возможности разрешения конфликтов;
Разграничения ответственности за нарушение правил информационных взаимоотношений;
Непрерывного анализа защищенности процессов управления, обработки и передачи информации и опережающего совершенствования методов и средств обеспечения безопасности информации (ОБИ).
Можно выделить следующие функции генераторов ПСП:
Формирование ключевой информации в симметричных и асимметри чных криптосистемах, а также паролей пользователей в системах разграничения доступа;
Формирование случайных запросов в протоколах аутентификации удаленных абонентов при реализации механизма «запрос-ответ» (пример - протокол симметричной аутентификации Нидхэма-Шредера);
Формирование затемняющих множителей в протоколах слепой электронной цифровой подписи (ЭЦП), применяемой в частности для обеспечения анонимности и неотслеживаемости платежей в электронных платежных системах (ЭПС) на основе цифровых денег;
Формирование прекурсора, хеш-образ которого используется в качестве серийного номера цифровой купюры (ЦК) и обеспечивающего защиту прав владельца ЦК в ЭПС на основе цифровой наличности;
Внесение неопределенности в работу средств и объектов защиты для повышения их устойчивости к воздействию различного рода разрушающих программных воздействий (РПВ) (пример - технология ОАЕР);
Формирование гаммы при использовании поточных шифров для обеспечения секретности информации;
Формирование случайных чисел в протоколе выработки общего секретного ключа, который используется в качестве строительного блока в большинстве прикладных протоколах ОБИ (пример - протокол TLS);
Формирование долей секрета в протоколах разделения секрета. Именно от свойств генераторов ПСП, особенно в тех случаях, когда
необходимо обеспечить устойчивую работу программных систем при наличии случайных и умышленных деструктивных воздействий, в значительной степени зависит надежность процессов сбора, обработки,
9 хранения и передачи информации. К программным средствам генерации ПСП предъявляются жесткие требования, в первую очередь по таким параметрам, как непредсказуемость, безопасность реализации, статистические и периодические свойства.
Анализ показывает, что можно выделить следующие наиболее перспективные семейства алгоритмов генерации ПСП.
Эллиптические алгоритмы генерации ПСП. Они относятся к наиболее математически обоснованным генераторам ПСП, а именно генераторам, нелинейное преобразование которых строится с использованием односторонних функций [ 20,41,44,46,53, 70 ].
Дихотомические алгоритмы генерации И.А. Кулакова как наименее ресурсоемкие и наиболее быстродействующие. При этом существует возможность построения на их основе всех симметричных криптографических примитивов [13,20].
Генераторы псевдослучайных последовательностей на регистрах сдвига с нелинейными обратными связями на основе так называемых стохастических сумматоров или R-блоков (Random), обобщающие многолетние исследования вопросов теории и применения генераторов на линейных и нелинейных регистрах сдвига [19].
Таким образом, актуальной научной задачей является развитие теории генераторов ПСП, в том числе создание новых алгоритмов генерации ПСП, сочетающих в себе непредсказуемость, высокое быстродействие и эффективную программную реализацию на различных платформах. Одним из направлений решения данной задачи является совершенствование стохастических алгоритмов формирования цифровых последовательностей, основанных на использовании стохастических сумматоров, т. е. сумматоров с непредсказуемым результатом работы.
10 Целями диссертационной работы являются:
исследование наиболее перспективных семейств алгоритмов генерации ПСП;
разработка алгоритмов генерации ПСП, сочетающих в себе высокое быстродействие при программной реализации и качество формируемых последовательностей, приемлемое для большинства приложений.
Для достижения поставленных целей необходимо решение следующих задач:
Исследование стохастических методов защиты компьютерных систем, основанных на свойствах эллиптических кривых, в том числе вопросов их безопасной программной реализации;
Разработка структуры, состава и интерфейса пользователя программного комплекса, предназначенного для изучения принципов использования эллиптических алгоритмов защиты программных систем;
Исследование статистической безопасности эллиптических алгоритмов генерации ПСП;
Исследование вопросов программной реализации дихотомических алгоритмов генерации ПСП;
Разработка и исследование генераторов ПСП, основанных на использовании стохастических сумматоров в цепи обратной связи, в том числе нелинейных генераторов ПСП длиной 2, где Q - число элементов памяти генератора, универсальных генераторов, обеспечивающих произвольное значение периода и предпериода (длины нестационарного участка) формируемых последовательностей. Методы исследований. При проведении исследований и
разработок в диссертационной работе были использованы теория конечных полей, теория линейных последовательностных машин, математическая статистика.
11 Научная новизна работы состоит в том, что:
разработан и исследован новый стохастический алгоритм генерации ПСП длиной 2, где Q - число элементов памяти генератора;
разработан и исследован новый стохастический алгоритм генерации ПСП с произвольными значениями периода и предпериода (длины нестационарного участка) формируемых последовательностей;
разработана структура и определен состав компонентов программного комплекса, предназначенного для исследования принципов использования эллиптических алгоритмов защиты программных систем;
предложены новые стохастические эллиптические алгоритмы и протоколы, в том числе алгоритмы формирования ПСП. Практическая ценность работы заключается в следующем:
создан программный комплекс, предназначенный для изучения принципов использования эллиптических алгоритмов защиты программных систем;
рассмотрены вопросы программной реализации дихотомических генераторов ПСП;
проведено исследование качества эллиптических алгоритмов генерации ПСП.
Реализация результатов. Результаты диссертационной работы внедрены в учебный процесс кафедры «Компьютерные системы и технологии» МИФИ. Практическое использование результатов диссертации подтверждено актом о внедрении.
Апробация работы. Основные результаты работы докладывались и обсуждались на научных сессиях МИФИ (Москва, 2005 г., 2006 г. и 2007 г.), на научной сессии, посвященной дню Радио (Москва, май 2007); демонстрировались на выставке «Телекоммуникации и новые информационные технологии в образовании» (Москва, 2006 г.).
Публикации. По теме диссертационной работы опубликовано 7 печатных работ, в том числе 4 тезиса докладов на научных сессиях МИФИ, материалы в каталоге экспонатов выставки «Телекоммуникации и новые информационные технологии в образовании», статья в журнале «Инженерная физика» и доклад в сборнике научных трудов Российского НТО радиотехники, электроники и связи им. А.С.Попова.
Структура работы. Диссертация состоит из введения, пяти глав, заключения и приложений. Основной материал изложен на 130 страницах и содержит 49 рисунков. Список литературы включает 79 наименований. В приложения включены результаты исследований, руководства пользователя по созданным программным продуктам. В приложения включены результаты исследования, примеры генераторов ПСП, описание интерфейса пользователья разработанного программного комплекса.
На защиту выносятся:
разработанный алгоритм генерации нелинейных ПСП длиной 2Q, где Q - число элементов памяти генератора;
разработанный алгоритм генерации ПСП с произвольными значениями периода и предпериода (длины нестационарного участка) формируемых последовательностей;
структура и состав компонентов программного комплекса, предназначенного для исследования принципов использования стохастических эллиптических алгоритмов защиты программных систем;
стохастические эллиптические алгоритмы и протоколы, в том числе эллиптические алгоритмы формирования ПСП.
результаты исследования качества эллиптических алгоритмов генерации ПСП.
Обзор функций генераторов ПСП в защищенных программных системах
Можно выделить следующие функции генераторов ПСП: Формирование ключевой информации в симметричных и асимме тричных криптосистемах, а также паролей пользователей в системах разграничения доступа; Формирование случайных запросов в протоколах аутентификации удаленных абонентов при реализации механизма «запрос-ответ» (пример - протокол симметричной аутентификации Нидхэма-Шредера); Формирование затемняющих множителей в протоколах слепой электронной цифровой подписи (ЭЦП), применяемой в частности для обеспечения анонимности и неотслеживаем ости платежей в электронных платежных системах (ЭПС) на основе цифровых денег; Формирование прекурсора, хеш-образ которого используется в качестве серийного номера цифровой купюры (ЦК) и обеспечи вающего защиту прав владельца ЦК в ЭПС на основе цифровой наличности; Внесение неопределенности в работу средств и объектов защиты для повышения их устойчивости к воздействию различного рода вредоносных программ (пример-технология ОАЕР); Формирование гаммы при использовании поточных шифров для обеспечения секретности информации; Формирование случайных чисел в протоколе выработки общего секретного ключа, который используется в качестве строительного блока в большинстве прикладных протоколах ОБИ (пример - протокол TLS); Формирование долей секрета в протоколах разделения секрета. Рассмотрим функции генераторов ПСП на примере механизмов обеспечения безопасности электронных платежных систем (ЭПС) на основе цифровых денег [7].
При обеспечении безопасности ЭПС помимо традиционных задач защиты информации, таких как аутентификация участников информацион ного взаимодействия; обеспечение конфиденциальности и целостности электронных документов при их передаче по каналам связи; обеспечение невозможности отказа от факта получения какого-либо сообщения; обеспечение юридической значимости пересылаемых электронных документов, приходится решать и такие новую задачу как обеспечение анонимности (anonymity) и неотслеживаем ости (untracebility) электронных платежей. Именно это свойство, присущее обычным бумажным денежным купюрам, необходимо обеспечить при попытке создания их цифрового аналога.
Анонимность платежа предполагает отсутствие взаимосвязи между платежом и личностью инициирующего его потребителя. Неотслеживаемость платежей означает, что два платежа, совершенные одним и тем же потребителем, не могут быть соотнесены друг с другом ни при каких условиях.
Решение указанных задач невозможно без применения стохастических методов.
ЭПС - аналог традиционной платежной системы, обеспечивающий денежные расчеты между поставщиками и потребителями в электронном виде. Участники ЭПС: банки, объединенные договорными обязательствами; предприятия торговли и сервиса, образующие сеть точек обслуживания клиентов; процессииговые центры; держатели платежных средств.
Цифровые деньги (цифровая наличность) - это защищенное от подделки электронное платежное средство. Более того, это единственное платежное средство, обеспечивающее анонимность и неотслеживаемость платежей. Ни одно из множества других электронных платежных средств (платежные карты, электронные чеки и пр.) такими свойствами не обладает.
Формат цифровой купюры (ЦК): номинал ЦК; серийный номер ЦК; электронная цифровая подпись (ЭЦП) банка-эмитента цифровой наличности. Проблемы информационной безопасности, которые необходимо решить: Как защититься от кражи ЦК, иначе говоря, как защитить права владельца ЦК; Как защититься от повторного использования купюры, учитывая, что электронный документ и ЭЦП можно копировать сколь угодно много раз; Как защититься от подделки номинала ЦК, учитывая что ЭЦП банка-эмитента ставится только на номере ЦК; Как обеспечить анонимность и неотслеживаем ость платежей, иначе говоря, как получить полный цифровой аналог традиционных денег, обладающих такими свойствами. В таблице 1.1 приведены методы решения, из которой видно, что три из четырех задач решаются стохастическими методами.
Математические основы преобразований на эллиптических кривых
Наиболее общее определение эллиптической кривой дает уравнение Вейерштрасса. Для конечного поля Галуа GF(p), где р 3 и является простым числом, уравнение Вейерштрасса имеет вид y2=x3+ax + b(modp), (1.1) где а и Ь есть целые числа над полем GF(p), такие, что справедливо выражение 4a3+27b2 0(modp). Для расширенного поля GF{2 ), уравнение Вейерштрасса имеет вид у2 + а1ху + а3у = х3 +а2х2 +а4х + э6. Обычно рассматривают две версии уравнения (1.2) у2 + ху = х3 +ах2 +Ь (1.2) (1.3) у2 +су = х3 +ах + Ь (1.4) где a1t 32, аз, э4р ав, з, b и с - элементы поля GF(2m), т.е. полиномы степени m - 1 над полем GF(2). Все вычисления в (1.3) и (1.4) производятся по двойному модулю (f(x), 2), где f(x) - примитивный полином степени т. Причем в уравнении (1.3) b 0, а в уравнении (1.4) с 0.
Уравнение (1.4) описывает суперсингулярную кривую. Для нее проблема дискретного логарифма легко и быстро решается. Поэтому суперсингулярные кривые неприменимы для целей ОБИ. Уравнение (1.3) описывает несуперсингулярную кривую.
Эллиптичная кривая Е над конечным полем GF(p) определяется множеством точек на плоскости Р = (хр, ур), где хр и ур являются элементами поля GF(p). Элементы поля а є GF(p) и b є GF(p) называются коэффициентами эллиптической кривой Е. Составляющие точки Р называются хр- и ур-координатами точки Р.
Следующий результат определяет возможные значения для #E(GF(p)) наЕ.
Теорема (возможные значения порядка эллиптической кривой). Пусть р = qm, где q - характеристика GF(p). Эллиптическая кривая Е, определенная над GF(p), с #E(GF(p)) = р + 1 -1 существует тогда и только тогда, когда выполняется одно из следующих условий: t#0(modp)H t 27p; m - нечетное и или a) t = 0; или b) t = д/2р и q = 2; или с) t = - /Зр и q = 3. m - четное и или a) t = 2 /р; или b) t = Л/р и q 1 (mod 3); или с) t = 0 и q Ф 1(mod 4). Порядок п точки Р суть наименьшее положительное целое число такое, что nP = О.
Циклическая подгруппа, произведенная Р, имеет вид {Р} = {0,Р,2Р,ЗР,...,(п-1)Р}. Если j и к - целые числа, то jP = кР тогда и только тогда, когда j = k (mod п). Чтобы проверить порядок случайной точки, нужно умножить эту точку на ее порядок плюс 1 и проверить, получится ли вновь стартовая точка: Р = (п + 1)Р, где п - порядок точки Р, находящейся на кривой. Пример. Пустьр = 5, а = b = 1, 4а3 + 27Ь2 =4 + 4 = 8 0. Рассмотрим эллиптическую кривую Е:у2=х3+х + 1 (рис. 2.6). E(GF(5)) СОСТОИТ ИЗ следующих точек (рис. 2.7): Р = (0,1),2Р=(4,2)1ЗР = (211),4Р = (314)15Р = (311)1 6Р = (2,4), 7Р = (4,3), 8Р = (0,4), 9Р = О, при этом ЮР = Р. Шаг ребенка, шаг великана (Baby step, Giant step). Это известный алгоритм для подсчета числа точек на эллиптической кривой.
Пусть PeE(GF(p)). Требуется найти порядок точки Р. Сначала необходимо найти целое число к такое, что к х Р = О. Пусть #E(GF(p))=N. По теореме Лагранжа NP = О. Известно, что р + 1-2 р Nip + 1 + 2 /p. Можно перебирать все значения, лежащие на этом интервале, и искать то, которое удовлетворяет условию N х Р = О. На это потребуется около 4д/р шагов. Имеется возможность ускорить поиск и довести число шагов до 4р1/4 , применяя следующий алгоритм.
Алгоритм (Baby step, Giant step): 1. Вычисляем Q = (p + 1)P. 2. Выбираем целое число m такое, что m p1M. Вычисляем и сохраняем точки jx Рдляі-0,1,2,..., m. 3. Вычисляем точки: С1 + к(2тР)дляк = -т,-(т-1), ...,т, пока не получим совпадения Q + k(2mP) = ±jP с ТОЧКОЙ {ИЛИ ее инверсным значением) в хранимом списке. 4. ВычисляемМ = (р +1 + 2mk±j)такое,что(р + 1 +2mk±j)P = 0. 5. Вычисляем множители М. Пусть Рі,...,рг - различные простые множители М. 6. Вычисляем (М/рі)хР для і =1,...,г. Если (M/pj)P = О для некоторого І, заменяем М на (M/pi) и возвращаемся к шагу 5. Если (М/рі) Р Ф О для всех і, М является порядком точки Р. 7. Если ищем #E(GF(p)), то повторяем шаги 1 - 6 со случайно выбранными точками на E(GF(p)), пока наибольшее общее кратное порядка не поделит только одно целое число N, р + 1-2д/р N p + 1 + 2 p. Тогда N = #E(GF(p)). По теореме Хассе #E(GF{p)) находится в интервале длины 4 /р. Поэтому, если можно найти точку с порядком, большим чем Л р, с учетом того, что может быть только одно кратное этого порядка в указанном выше интервале и оно равно #E(GF(p)).
Эллиптические генераторы ПСП на основе регистров сдвига с линейными обратными связями
В 2001 г. G.Gong и C.C.Y.Lam предложили LFSR-последовательность (Linear Feedback Shift Register) над группой точек эллиптической кривой и предложили конструкцию двоичных последовательностей, полученных из этих LFSR-последовательностей и названных LFSR-EC последователь ностями. Суть предложения - комбинация эллиптических кривых и LFSR для генерации ПСП.
Рассмотрим линейную рекуррентную последовательность, формируе мую регистром сдвига с линейной обратной связью. Пусть г -положительное целое число и 2Г - кольцо классов вычетов по модулю г.
Пусть f(x) = хп - 2Госіх » Cj є Zr - многочлен, нормированный над 2Г, и b = { bj}, bZr. b называется линейной рекуррентной последовательностью, сформированной регистром сдвига с линейной обратной связью, соответствующим f(x), если для данного п-кортежа (b0,b1,...,bn_1)Z!? bk+n = Ecibk+h = 0,1 1=0 При этом f(x) называется характеристическим многочленом LFSR и последовательности b, a (b0lb1l...,bn_1) - начальным состоянием LFSR.
Характеристический многочлен b, имеющий наименьшую степень, называется минимальным многочленом Ь, а степень минимального многочлена b называется линейной сложностью Ь. Период f(x) определен как наименьшее целое число t такое, что f(x) х1 -1. Пусть G f) - набор последовательностей, соответствующих характеристическому многочлену f(x). Легко видеть, что для любого Ь, период b - делитель периода f(x). Пусть V(Zr)-{(h0Jh1,...)hi eZr}. Тогда V(Zr) - линейное пространство над Zr и GZf(f) - подпространство V(Zr). GZr(f) -линейное пространство над Zr. Пусть f(x) - неприводимый многочлен над GF(q) степени п и у - корень f(x). Тогда для любой последовательности b = {1} є G2 (f) существует некоторое р є GF(q"J такое, что b TrJ py ) 1 = 0,1 где Trq (х) = х + xq + — + xq - функция следа от GF(qn) к GF(q). Рассмотрим принципы формирования и основные свойства LFSR-последовательностей над Е. Пусть Е - эллиптическая кривая над GF(q) порядка г, т-(х) = хп-спИх"-1 c x-c0eZr[x] - многочлен, нормированный над Zr и Р = {Рц}, где Рк = (хк, уїс) є Е.
Для фиксированного с_іє Zr и данного (n + 1) кортежа (Q, Ро,.... Рп-і) є Еп + \ если последовательность удовлетворяет следующему линейному рекуррентному соотношению п-1 Pn+k = Ecipi+k+c_iQf k = 0-1 1=0 то Р называется линейной рекуррентной последовательностью над Е, соответствующей f(x) степени п, или, более традиционно, последова тельностью n-разрядного регистра сдвига с линейной обратной связью, соответствующего f(x), над эллиптической кривой Е или просто, LFSR-EC-последовательностью. f(x) называется характеристическим многочленом Р, а (О, Р0, Pi,..., Pn-i) называется начальным состоянием Р.
Пусть GE(f) - набор, состоящий из ЕС-последовательностей над Е с характеристическим многочленом f(x). Для любой Р = { Рк } є GE(f) с исходным состоянием (О, Ро, Pi, .... Рп - і), элементы Р могут быть представлены следующим образом Р = 1ЬкЛ к = 0,1,..., 1=0 где длякаждогоі (0 i n-1)bi = {bk,i} є Gz (f) с начальными состояниями Ьм=5уДЛяО к п-1. Если исходное состояние Р = {PR}, Рк є GE(f), задается как (O,s0P,SiP...Ts№iP)IsiZr, то Pk = ZbK,i(s,P)= Е(ьк(8,)Р = акР, к = 0,1,..., 3.2) i=0 i=0 где п 1 «к s Xbk,i i. к = 0,1,.... [=0
Пусть а = {Эк}. Эта последовательность формируется следующим образом a = 2TOSI=I "I aK как є zrW из соотношения (3.2) следует, что GZr(f) - линейное пространство, a = Sbj eGz (f). Из соотношения (3.2) также следует, что значение Рк может быть вычислено путем умножения Р на ак (mod t), где t - порядок Р. Pk = akP(modt),k = 0,1,... Для этого специального исходного состояния, определяем аР = {аР}, і 0, и GP(f)= РI а Е GZr(f)j. ЕС-последовательность аР называется ЕС-последо вательность одиночной точкой. Если f(x) - неприводимый многочлен над GF(q) степени 2, можно вычислить ЕС-последовательность следующим образом. 1. Порядок Е над GF(q) равен г. Для любого Рє GE(f), элементы Р могут быть представлены следующим образом Pk=Tr/(aTk)p1+Trf(pyk)p0 где у - корень f(x) и а, р є Zr. 2. Если Рє Е и ее порядок - г и Pi = tP и Р0 = sP, t, s є Zrjo Pk=Trqq2((ta + sp)yk)p, к = 0Д.... Если f(x) - неприводимый многочлен над GF(q) степени п, можно вычислить ЕС-последовательность следующим образом.
Стохастическое преобразование информации. R-блоки
Эффективным средством защиты информации от случайных и умышленных деструктивных воздействий является стохастическое преобразование информации [14]. Схема одного из возможных вариантов построения {впервые предложенного для решения задачи помехоустойчивого кодирования САОсмоловским в работе [14]) блока R стохастического преобразования и его условное графическое обозначение показаны соответственно на рис. 4.1 и 4.2.
Ключевая информация R-блока - заполнение таблицы Н = {Н(т)}, размерности n х 2П, содержащей элементы GF(2n), перемешанные случайным образом, т.е. Н(т) є GF(2n). Результат RH(A, В) преобразования входного п-разрядного двоичного набора А зависит от заполнения таблицы Н и параметра преобразования В, задающего смещение в таблице относительно ячейки, содержащей значение А, следующим образом
RH(A1B) = H{(mA+B)mod2n)1 где mA - адрес ячейки таблицы Н, содержащей код А, т.е. H(mA) = А. Другими словами результат работы R-блока суть считывание содержимого ячейки таблицы Н, циклически смещенной на В позиций в сторону старших адресов относительно ячейки, содержащей код А. Для ускорения преобразования в состав R-блока вводится вспомогательный адресный массив Addr = {Addr(j)} размерности n х 2", причем Vj = 0,(2" -1J Addr(j) = mj. Иными словами ячейка с адресом j в массиве Addr хранит адрес ячейки массива Н, содержащей код] . Заслуживают внимания следующие факты: в частном случае при Addr = {0, 1, 2, ... , (2П - 1)} и В - 0 получаем классический S-блок (блок замены) с таблицей замен Н; при записи в каждую ячейку массивов Н и Addr ее собственного адреса получаем классический сумматор по модулю 2П, а значит, с полным на то основанием R-блок может быть назван стохастическим сумматором.
Для построения нелинейного стохастического генератора ПСП, получившего название RFSR (Random Feedback Shift Register), в схеме аддитивного генератора, в [2] предлагается вместо блоков сложения по модулю 2N использовать R-блоки (рис. 4.3). В состав RFSR входят N регистров q1( q2, ..., \н разрядностью п каждый, п-разрядный блок стохастического преобразования R. Уравнения работы RFSR имеют вид q1(t+1) = R(qi(t)lqN(t)),
fc(t + 1) = qi-i(t), J = 2,Nt
где (jj(t) и qj(t + 1)- состояние j-го регистра соответственно в моменты времени t и t + 1. Выходная последовательность снимается с выхода одного из регистров. В качестве вектора инициализации (синхропосыпки) может использоваться начальное состояние регистров Ці(0), ь(0),...,ян(0). При соответствующем заполнении таблицы Н RFSR формирует нелинейную последовательность 2Q - 1, где Q - число элементов памяти RFSR. В приложении 1 приведен пример RFSR, формирующего ПСП длиной 2Q - 1. В работе [2] определены таблицы Н, при использовании которых формируемая ПСП является нелинейной (стохастической) М-последователь ностью. Основное достоинство RFSR - эффективная программная реализация. Все теоретические и практические результаты, полученные для LFSR при решении задач защиты информации от случайных воздействий, легко обобщаются и позволяют столь же эффективно решать задачи защиты информации от умышленных деструктивных воздействий.
Схемы с использованием LFSR наиболее эффективны при использовании образующего многочлена вида xN + Xі + 1, где і = 8,16,32,64, 128 и т. д. Пример реализации подобного 8-входового хеш-генератора на основе параллельного генератора Фибоначчи (Fibonacci) показан на рис. 4.4, где qot qit ,.,, qs2o - разряды LFSR, Принципы построения и Криптостойкость существующих поточных шифров, использующих в своей работе блоки сложения по модулю 256 или линейные генераторы ПСП, можно легко значительно увеличить простой их заменой соответственно на стохастические сумматоры (R-блоки) и RFSR- На рис. 4.5 показан модифицированный генератор ПСП PIKE, на рис. 4.6 -модифицированный генератор ПСП RC4 [2]
