Содержание к диссертации
Введение
1 Анализ устойчивости алгоритма кодирования информации мак - элис к действию комплекса помех . 11
1.1 Вводные замечания 11
1.2 Описание алгоритма мак-элис 13
1.3 Мешающие влияния в каналах передачи информации.. 15
1.4 Исследование помехоустойчивости алгоритма кодирования информации мак - элис
4.1 Характеристики комплекса помех 20
4.2 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении
кодов Хэмминга 21
1.4.3 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Боуза - Чоудхури - Хоквингема 31
1.4.4 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Рида - Соломона 36
1.4.5 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Гоппы 41
1.4.6 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении метода порогового и многопорогового декодирования 45
1.4.7 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении произведения кодов 55
1.4.8 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении
турбо кодов 64
1.5 Выводы 68
2 Модификации алгоритма мак - элис для повышения информационной скрытности и кодовой скорости 72
2.1 Вводные замечания 72
2.1.1 Особенности алгоритмов шифрования 72
2.1.2 Алгоритмы защиты информации с открытым ключом 74
2.1.3 Шифросистемы алгоритма с открытым ключом 75
2.2 Варианты повышения эффективности алгоритма мак - элис 83
2.2.1 Алгоритм на основе изменения входной информации кодера 83
2.2.2 Алгоритм повышения кодовой скорости
2.2.3 Алгоритм основанный на совмещении требований повышения кодовой скорости и информационной скрытности 91
2.2.4 Алгоритм основанный на применении параллельных кодов...95
2.2.5 Алгоритм на основе использования произведения кодов 99
2.2.6 Алгоритм Мак-Элис при использовании сжатия информации... 103
2.2.7 Сравнение эффективности вариантов модификаций алгоритма Мак - Элис 108
2.3 ВЫВОДЫ 108
3 Практические аспекты реализации алгоритма мак - элис 111
3.1 Вводные замечания 111
3.2 Применение алгоритма мак-элис для электронной цифровой подписи
3.2.1 Понятие электронной цифровой подписи 113
3.2.2 Анализ применения алгоритма Мак-Элис для электронной цифровой подписи 116
3.3 Анализ факторов влияющих на практическую реализацию алгоритма мак-элис 118
3.3.1 Факторы обеспечения заданной скорости передачи информации 118
3.3.2 Факторы обеспечения заданной помехоустойчивости и скрытности передачи информации 121
3.3.3 Анализ вычислительных затрат на реализацию алгоритма Мак-Элис і 127
3.4 Анализ реализации алгоритма мак - элис на программируемых логических интегральных схемах 131
3.4.1 Обоснование реализации алгоритма Мак-Элис на программируемых логических интегральных системах 131
3.4.2 Особенности структуры программируемых логических интегральных схем 134
3.4.3 Анализ реализации алгоритма Мак-Элис на программируемых логических интегральных схемах 136
3.5 Выводы 142
Заключение 143
Список литературы
- Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Боуза - Чоудхури - Хоквингема
- Алгоритмы защиты информации с открытым ключом
- Алгоритм основанный на совмещении требований повышения кодовой скорости и информационной скрытности
- Понятие электронной цифровой подписи
Введение к работе
Актуальность темы. Одной из важнейших задач при построении современных систем передачи информации является проблема повышения надежности, помехоустойчивости, скрытности и скорости передаваемой информации.
Кроме того, эти системы должны выполнять поставленные задачи в условиях действия различного вида помех.
Одним из решений данной задачи является использование помехоустойчивого кодирования в системах передачи информации. Целесообразность кодирования информации впервые была показана в работе Шеннона К., где было доказано, что если скорость создания сообщений источником не превосходит некоторой величины, называемой пропускной способностью канала, то при правильно выбранных методах кодирования и декодирования можно вести передачу по каналу с шумом со сколь угодно малой вероятностью ошибки. Основные задачи помехоустойчивого кодирования связаны с построением кодов с высокой корректирующей способностью и разработке высокоэффективных, практически реализуемых алгоритмов их декодирования.
Значительный вклад в области повышения помехоустойчивости передаваемой информации внесли такие учёные как Котельников В. А., Злотник Б. М, Кларк Д. Ж., Кейн Д. Ж., Питерсон У., Уэлдон Э., Месси Б. Дж., Кассами Т., Токура Н., Морелос-Сарагоса Р., Золотарёв В. В., Самсонов Б., Плохов Е. М, и.др.
Другим важным требованием к системам передачи информации является
обеспечение скрытности, которая характеризуется способностью системы
противостоять мерам, направленным на раскрытие содержания информации.
Обеспечение скрытности передаваемой информации включает комплекс мер
затрудняющих: обнаружение сигнала, определение структуры обнаруженного
сигнала (на основе определения ряда его параметров) и раскрытие смысла
содержащегося в передаваемой информации. Одним из методов, часто
использующимся для повышения скрытности информации, является
применение кодирования. Повышением скрытности передаваемой
информации занимались Шеннон К., Тузов Г. И., Сивов В. А., Брюс Щнайер, Саломаа А., Алферов А. П., Зубов А. Ю., Нечаев В.И, Молдовян Н. А, Молдовян А. А, Венбо Мао и.др.
В настоящее время широко используются такие системы кодирования, как RSA, Эль-Гамаля, "проблемы рюкзака ", и. др. Однако, для реализации данных алгоритмов требуются значительные вычисленные затраты, большое количество операций, что приводит к увеличению времени шифрования и дешифрования. Высокая сложность устройств кодирования и декодирования в этих системах затрудняет реализацию алгоритмов в реальном масштабе
времени и существенно ограничивает скорость передачи информации. Кроме того, эти алгоритмы имеют низкую помехоустойчивость.
В отличие от этих систем алгоритм Мак-Элис, основанный на использовании линейных кодов, позволяет одновременно обеспечивать заданную помехоустойчивость и скрытность передаваемой информации. Однако, данный алгоритм обладает такими недостатками, как низкая кодовая скорость, большая длина кодового слова, значительный размер закрытого и открытого ключа. Для широкого использования данного алгоритма, необходимо устранить вышеперечисленные недостатки.
Таким образом, актуальной задачей является исследование и разработка
модификаций алгоритма Мак-Элис, позволяющих повысить
помехозащищенность высокоскоростных систем передачи информации.
Цель работы. Основной целью работы является разработка и обоснование модификаций алгоритма Мак-Элис в интересах повышения эффективности по скорости, скрытности и помехоустойчивости передачи информации.
Поставленная в работе цель включает решение следующих задач:
- анализ устойчивости алгоритма Мак-Элис в случае действия комплекса
помех, при использовании различных линейных кодов (например, коды
Хэмминга, Боуза - Чоудхури - Хоквингема, Рида-Соломона, Гоппы,
самоортогональных кодов (СОК), произведение кодов, турбо кодов);
модификации алгоритма Мак-Элис в интересах повышения скрытности, скорости и помехоустойчивости передачи информации;
исследования применения комбинированных кодов в качестве линейных кодов алгоритма Мак-Элис, позволяющих значительно увеличить помехоустойчивость и скрытность передаваемой информации данного алгоритма;
- исследования применения модификаций алгоритма Мак-Элис для
электронной цифровой подписи (ЭЦП) в радиосистемах передачи
информации;
- анализ реализации модификаций алгоритма Мак-Элис при
использовании программированных логических интегральных систем
(ПЛИС) в высокоскоростных системах передачи информации.
Методы проведения исследований. В работе использовались методы статистической радиотехники, математической статистки, численные методы вычислительной математики. Данные теоретические методы сочетались с экспериментальными исследованиями на основе имитационного моделирования.
Научная новизна. В рамках данной работы были получены следующие новые научные результаты:
1.Оценена устойчивость алгоритма Мак-Элис при действии комплекса широкополосной, узкополосной, структурной и импульсной помех в
случае использования кодов Хэмминга, Боуза - Чоудхури -Хоквингема, Рида-Соломона, Гоппы, произведение кодов, СОК, турбо кодов с различными кодовыми скоростями и определена самая опасная помеха. 2.Обоснована модификация алгоритма Мак-Элис на основе изменения исходной последовательности и добавления информации в вектор ошибки, позволяющая повысить скрытность передачи информации и кодовую скорость. 3.Предложены модификации блок-схемы алгоритма Мак-Элис при использовании комбинированных кодов (параллельных и произведения кодов), позволяющие повысить помехоустойчивость и скрытности передачи информации. 4. Предложена модификация алгоритма Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющая получить выигрыш в информационной скрытности, а также значительно повысить кодовую скорость. 5.По казана возможность применения алгоритма Мак-Элис для ЭЦП, а
также в радиосистемах передачи информации. Практическая ценность.
Представленные в работе модифицированные алгоритмы Мак-Элис, имеют высокую помехоустойчивость, скрытность передачи информации и кодовую скорость, что позволяет их использовать для ЭЦП и в различных радиосистемах передачи информации. Модифицированные алгоритмы Мак-Элис, использующие комбинированные коды и обладающие высокой способностью исправлять ошибки, могут применяться в системах передачи данных, требующих высокую помехоустойчивость. Результаты диссертационной работы нашли применения в сетях передачи данных в ОАО «Телекоммуникационной компании Ринфотелс», а также в ГОУ ВПО «Рязанский государственный радиотехнический университет». Основные положения, выносимые на защиту:
1 .Модифицированный алгоритм Мак-Элис, основанный на добавлении информации в вектор ошибки и изменении исходной информации путем использования матрицы хеширования, обеспечивающей информационную скрытность до 1,37.1016 при использовании кода Гоппы (1024, 524). 2.Модифицированный алгоритм Мак-Элис основанный на добавлении информации в вектор ошибок, позволяющий повысить кодовую скорость на -60%. 3 .Модифицированный алгоритм Мак-Элис основанный на использовании параллельных кодов, позволяющий повысить информационную скрытность в 1014раз (при длине кодового слова п=1) по сравнению с исходным алгоритмом.
Модифицированный алгоритм Мак-Элис, основанный на применении произведения кодов, обеспечивающий информационную скрытность более 1,37.1016 и число исправляемых ошибок до 91 бит при использовании произведения кода Х(15,11)БЧХ(1024,728).
Модифицированный алгоритм Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющий получить информационную скрытность АТ~1,37.1016 в случае использования кода Гоппы (1024,524), а также повысить кодовую скорость до 0,95.
Апробация работы. Результаты работы докладывались на следующих научно-технических конференциях:
1.52-я Студенческая Научно-Техническая Конференция. 2005, Рязань. 2. Всероссийская научно-практическая конференция студентов, молодых
учёных и специалистов "Новые информационные технологии в
научных исследования и в образовании". 2005, Рязань. 3.Всероссийская научно-практическая конференция "Сети и системы
связи", 2005. Рязань.
Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникации». 2005, Рязань.
Международная молодежная научная конференция, посвященная 1000 летию города Казани "Туполевские чтения". 2005, Казань.
Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании". 2006, Рязань.
Всероссийская научно-практическая конференция "Сети и системы связи", 2006. Рязань.
Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании". 2007, Рязань.
Всероссийская научно-практическая конференция "Сети и системы связи", 2007. Рязань.
Публикации. По теме диссертации опубликовано 13 работ. Из них 3 статьи в журналах, рекомендованных ВАК РФ для кандидатских диссертаций, 1 статья в межвузовских сборниках, 9 тезисов докладов.
Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключение, списка литературы из 119 наименований и 3 Приложений. Диссертация содержит 168 стр., в том числе 132 стр. основного текста, 12 таблиц и 92 рисунка.
Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Боуза - Чоудхури - Хоквингема
Ретранслированная помеха создается в результате усиления и переизлучения переданного сигнала одной - двумя соседними станциями. Переизлученный и задержанный сигнал, попадая в приемник истинной станции, создает специфическую помеху, воздействующую тем сильнее, чем хуже корреляционные свойства передаваемых сигналов.
Имитационная помеха (ИМП) близка по форме переданному сигналу; степень близости определяется числом передаваемых сигналов и их корреляционными свойствами. Часто ИМП называют также структурной или прицельной помехой [3, 13]. Название «прицельная помеха» становится оправданным при совпадении в приемнике фазы или средней частоты ИМП с фазой переданного сигнала или со средней частотой одного или нескольких частотных подканалов. В последнем случае помеху иногда называют сосредоточенной.
В наземных радиолиниях причинами замираний, составляющих основную часть мешающих влияний естественного происхождения, служат многолучевость, метеоусловия, время года. Многолучевость вызывает быстрые замирания, метеоусловия и время года - медленные. Частотную селективность замираний определяют по снижению коэффициента частотной корреляции р до значения 0.5 ... 0.6. Интервал частот, лежащий в пределах р=\...0.5, называют полосой (интервалом) когерентности канала связи.
Искажения сигнала могут вызываться как характеристиками тракта передачи, так и помехами. Однако понятие искажения обычно связывают только с влиянием на сигнал линейных и нелинейных характеристик тракта. Воздействие линейных характеристик, и в частности неравномерности амплитудно-частотной характеристики (АЧХ), приводит к появлению межсимвольных искажений (МСИ); ограничение амплитуды сигнала вызывает появление нежелательные частот в спектре, создающих помехи нелинейных переходов.
Ошибки фиксируются на выходе дискретного канала: именно они определяют верность информации. Деление ошибок на независимые и пакетные вызвано главным образом спецификой помехоустойчивого кода, его способностью исправлять или обнаруживать ошибки [1, 4... 10].
Для априорной оценки эффективности кода проводят имитационное моделирование, требующее знания статистического распределения мешающих влияний. Обычно шум предполагают нормально распределенным (белым гауссовым шумом — БГШ). При большом разнообразии ИП нет единой универсальной модели, описывающей, эти помехи. Как правило [3, 13], уровни и длительности ИП принимают распределенными, по экспоненциальному закону, а вероятность появления т импульсов на интервале времени Тим (в соответствии с распределением Пуассона) Tu.n{m) = iK,T M-K,V (1.6) где Л — среднее число импульсов на интервале Тип. Наиболее сложно моделировать преднамеренные помехи, «качество» которых тем выше, чем менее определена их статистика. Однако каждая помеха характеризуется несколькими параметрами, которые при моделировании могут быть заданы в априорно выбранном диапазоне значений в виде, например, случайных чисел.
Искажения рассматривают как дополнительный флуктуационный шум [13]. В силу многообразия причин и конкретных условий невозможно описать статистическое распределение ошибок одной моделью. Наиболее простой является модель независимых ошибок, описываемая биномиальным распределением; вероятность появления m ошибок в п символах [3] P{m,n) = Cnmpm{\-pTm, (1.7) где р - вероятность одной ошибки; вероятность m и более ошибок P( m,n) = qpi(\-py-i. (1.8) i=m Биномиальное распределение хорошо описывает ошибки в дискретном канале, причиной которых служит флуктуационный сигнала принимают при моделировании нормально распределенными и шум.
Для каналов с памятью существует несколько моделей пакетированных ошибок. Широко используют модель ключевого канала, имеющего два состояния - хорошее (G) и плохое (В) - и соответственно две вероятности ошибок PG, Рв, четыре вероятности переходов состояний Pg& Pgb, Рьь Pbg, три вероятности т ошибок в п символах: усредненная по всем состояниям канала Р(т,п), в хорошем состоянии G{m,n), в плохом состоянии В(т п) [3]. В различных каналах передачи информации мешающие влияния даже одного вида имеют различные параметры распределения. Эту особенность необходимо учитывать при выборе помехоустойчивого кода.
Как показано выше, особенностью алгоритма Мак - Элис является использование линейного кода. Поэтому исследование, оценка помехоустойчивости алгоритма Мак - Элис при использовании различных линейных кодов и действии комплекса помех играют важную роль. В качестве широкополосной помехи использовался белый в полосе сигнала гауссовский шум. Узкополосная помеха с полосой Afy=Afc/8, в виде сигналов других станций, воздействовала в полосе Д/с передаваемого сигнала, искажая его спектр и ухудшая как спектральные, так и корреляционные свойства. Структурная помеха представляла собой случайную последовательность фазоманипулированных сигналов с несущей частотой, аналогичной передаваемому сигналу [13]. В общем виде импульсную помеху можно представить как последовательность радиоимпульсов с несущей частотой сигнала, амплитуды и длительность которых, а также интервалы между соседними импульсами изменяются случайным образом. В настоящее время отсутствуют аналитические выражения сравнения вероятности ошибки на бит для разных систем кодирования дискретной информации. В связи с этим исследование устойчивости алгоритма Мак-Элис при различных системах кодирования возможно провести на основе имитационного моделирования. Характеристики используемых при имитационном моделировании помех приведены в Приложении 2.
Алгоритмы защиты информации с открытым ключом
Зависимости средней вероятности ошибки на бит от отношения сигнал-широкополосная помеха при действии импульсной помехи с отношением сигнал-помеха дм,=15 дБ, qu,=25 дБ и qu,=35 дБ и с использованием в качестве линейного кода PC (15, 7) При действии широкополосной помехи помехоустойчивость системы передачи информации на основе алгоритма Мак - Элис с применением кода PC (15, 7) выше примерно на 1 дБ, чем у системы с использованием кода БЧХ (15, 7) и на 1,5 дБ с использованием кода Хэмминга (7,4). Кроме того, в этом случае при действии узкополосной помехи для достижения вероятности Ре = 10" , необходимо qy =7 дБ, а в случае использования кодов Хэмминга qy-\7 дБ и БЧХ qy =14 дБ при отношении сигнал - широкополосный шум qm=l дБ. При том же отношении сигнал - широкополосный шум, под действием структурной помехи, для достижения вероятности Pe=W, необходимо qc= 13 дБ, а если применяется код Хэмминга (7,4), то qc=22 дБ и БЧХ (15,7) - qc=\4 дБ. Аналогично, при действии импульсной помехи с отношением сигнал - импульсная помеха qu- 15 дБ и при отношении сигнал -шум дш= 7дБ, вероятность Ре=\0 3, а в случае использования кода БЧХ (15,7) Ре=2,2.10"3, а для кода Х(7,4) (или БЧХ (7,4)) Ре=5,2.10"3. Кроме того, анализ результатов на рисунках 1. 22 - 1. 24 показывает, что узкополосная и структурная помеха менее опасны, чем импульсная, например, при широкополосной помехе из канала дш = 6 дБ, и под действием узкополосной, структурной и импульсной помех с отношениями сигнал-помеха qy=qc=qu=\5j}$, получаются вероятности Реу=\,5Л0 , Рес=ЗЛ0 и Реи=5Л0 соответственно.
Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Гоппы Известно [5, 6], что благодаря методу кодирования и удобства вычисления порождающей матрицы, коды Гоппы рекомендуются для алгоритма Мак-Элис. Данные коды - это один из важнейших классов линейных кодов, не являющихся вообще говоря, циклическими. При рассмотрении кодов Гоппы будем следовать работе [6]. Пусть 0 п 2т и L = {ava2,---,an}- множество элементов GF(2m). Обозначим через V„, п мерное векторное пространство над GF(2). Вектор v = (yvv2"-vn)eVn сопоставим рациональную функцию переменного z (z будет принимать значения в GF(2m)): RJz) = ± -. (1.26) м z-cc, Отображение v- J?„(z)- гомоморфизм S в аддитивную группу рациональных функций над GF(2m). Выберем некоторый многочлен g(z) с коэффициентами из GF(2" ), не имеющий корней в L. Определим линейный код как множество векторов X, для которых i?v(z) = 0modg(z). Задавая различным образом многочлен g(z), можно получать коды с различными свойствами. Вместе с каждым вектором v, имеющим единицы на местах i{,i2,---,ik, будем рассматривать многочлен f{z) = (z-an)(z-any-(z-aik). Очевидно, Rr(z) = f\z)/f(z),me f\z) формальная производная многочлена/ ).
Корректирующая способность кодов: Так как для кодовых многочленов fiz) = 0 mod g(z) и f\z) = 0 mod g(z) где g(z) - многочлен минимальной степени, являющийся полным квадратом и такой, что g(z) g(z) то deg/(z) degg(z) +1 так что для веса кода получается оценка
Зависимости средней вероятности ошибки на бит от отношения сигнал - широкополосный шум для различных кодов БЧХ и Гоппы в ДСК для кодовых скоростей 1/2 На рисунках 1. 26 - 1. 28 представлены зависимости, средней вероятности ошибки на бит для алгоритма Мак-Элис при действии узкополосной, структурной и импульсной помехи с заданним ОСШ цш в канале [52].
Зависимости средней вероятности ошибки на бит от отношения сигнал-широкополосная помеха при действии импульсной помехи с отношением сигнал-помеха qu=\5 дБ, qu=2S дБ и qu=35 дБ и с использованием в качестве линейного кода Гоппы (16,8) Полученные результаты показали, что помехоустойчивость алгоритма Мак - Элис на основе кода Гоппы по сравнению с алгоритмом на основе кода БЧХ (15,7), имеющим сходные характеристики (t = 2 - количество исправляемых ошибок, г 1/2 - кодовая скорость) близки, а код РС(15,7) обладает преимуществом в помехоустойчивости по сравнению с данным кодом. Например, при действии узкополосной помехи с =15 дБ и при присутствии широкополосного шума из канала с qM=l дБ, для кода Гоппы (16,8) вероятность ошибки на бит /?е=8,5.10"4, а для кода PC (15,7) -Ре=2.\0 4. В случае действия структурной помехи с qc= 15 дБ и при том же qul, для кода Гоппы вероятность Ре=2.10 3, а для кода PC (15,7) Ре=3.10"4, аналогично, под действием импульсной помехи при тех же отношений сигнал-шум qUi и сигнал-помеха qu, для кода Гоппы (16,8) вероятность Ре = 3,5.10"3, а для кода РС-Ре=10 3.
Алгоритм основанный на совмещении требований повышения кодовой скорости и информационной скрытности
Анализ шифросистемы показал, что данная шифросистема имеет высокую информационную скрытность, но шифрование и дешифрование сложно выполняются, что требует большое время для кодирования и декодирования. В настоящее время использование высоких технологий позволяет решить эту проблему. Кроме того, шифросистема RSA обладает слабой устойчивостью к действию помех [15,16].
Шифросистема Эль-Гамаля была предложена в 1985 г [15... 17, 19, 20] и является фактически одним из вариантов метода определения открытых ключей Диффи-Хеллмана. Информационная скрытность данной системы основана на сложности проблемы логарифмирования в мультипликативной группе конечного простого поля. Шифрсистема Эль-Гамаля (X,K,Y,E,D) определяется следующим образом [15... 17] X=Z p, Y = Z p.Z p,K={(p,a,/3,a)a"=j3(modp)}, (2Л0) где р — достаточно большое простое число, а — порождающий элемент группы Z р,а — целое число из интервала 1 а р — 2 . Ключ к = (р, а, р, а) представляется в виде открытого ключа к0 = (р,а,р)и секретного ключа к3 = (а). Правило шифрования на ключе к определяется формулой Е (М) = (Сі, Сі), где Ci = a (mod;?),C2 =A/-/T(modp),a г - случайно выбираемое число (рандомизатор) из интервала 0 г р-2. Правило расшифрования на ключе к имеет вид А=(С„С2) = С2(С1Т1 (mod р). (2.П) Несложно проверить, что такое определение корректно, то есть что выполняется равенство Dk(Ek(M)) = Миря любых к е К и М є X. (2.12) Использование рандомизатора г делает шифр Эль-Гамаля шифром многозначной замены. В связи со случайным характером выбора параметра г подобную схему шифрования называют еще схемой вероятностного шифрования. Для нее открытый текст и ключ не определяют шифртекст однозначно. Для определения открытого и секретного ключей каждый из абонентов системы осуществляет следующие операции [17]: 1)выбирает большое простое число р и некоторый порождающий элемент а группы Z%; 2)случайно выбирает целое число а, где 1 а р-2, и вычисляет Р = аа(то&р); 3) публикует открытый ключ (р, а,р), оставляя в секрете число а. Следует отметить, что в приведенной системе необходимо использовать различные значения рандомизатора г для шифрования различных открытых текстов М и М . В самом деле, в противном случае соответствующие шифртексты (Сі.Сг) и (Сі ,С2 ) оказываются связанными соотношением С2{С2 )Л =М(М) ] и М может быть легко вычислен, если известен М.
Как уже отмечалось, стойкость системы Эль-Гамаля определяется сложностью решения задачи дискретного логарифмирования в Z p. В настоящее время эта задача практически нереализуема для значений р , содержащих не менее 150 десятичных знаков. Рекомендуется также, чтобы число (р - 1) содержало бы большой простой делитель.
Система Эль-Гамаля может быть обобщена для применения в любой конечной циклической группе G Информационная скрытность такой обобщенной схемы определяется сложностью задачи логарифмирования в группе G При этом групповая операция в G должна быть легко реализуемой. В качестве G чаще всего выбираются следующие три группы: 1 Мультипликативная группа Z p целых чисел по модулю простого числа р; 2)мультипликативная группа GF(2m) конечного поля GF{2m) характеристики 2; 3) группа точек эллиптической кривой над конечным полем. Вероятностный характер шифрования можно отнести к достоинствам системы Эль-Гамаля, так как схемы вероятностного шифрования обладают, как правило, большей стойкостью по сравнению со схемами с детерминированным процессом шифрования. Недостатком системы является удвоение длины открытого текста при шифровании а также, как и в случае системы RSA низкая устойчивость к действию помех [15...20].
"Проблема рюкзака" (или "ранца") может быть сформулирована следующим образом. Пусть задано множество натуральных чисел А = {ai,a2,.,.,an} и натуральное число S [15...20]. Требуется установить, имеется ли такое подмножество множества А, сумма элементов которого была бы равна S. Эквивалентной является следующая формулировка: существует ли такой набор чисел х є {0,1}, / п, для которого s = а,хг
Понятие электронной цифровой подписи
Шифрование, состоящее из симметричных шифросистем и шифросистем с открытым ключом [15... 17], история которой охватывает несколько тысячелетий, зародилась из потребности передачи секретной информации. Длительное время она была связана только с разработкой специальных методов преобразования информации с целью её представления в форме, недоступной для потенциального злоумышленника. С началом применения электронных способов передачи и обработки информации задачи шифрования начали расширяться. В настоящее время, когда компьютерные информационные технологии нашли массовое применение, проблематика шифрования включает многие задачи, которые не связаны непосредственно с засекречиванием информации (например, контроль целостности информации, электронная цифровая полнись, создание электронного казино и т. п.) [19, 20].
Примитивные с позиций сегодняшнего дня методы шифрования известны с древнейших времен и длительное время рассматривались скорее как некоторые ухищрения, чем как строгая научная дисциплина. Классической задачей шифрования является обеспечение обратимости преобразования некоторого исходного текста (открытого текста) в кажущуюся случайной последовательность знаков, называемую шифртекстом (закрытым текстом) [16, 17,19,20, 76...78].
Теперь, значение шифрования выходит далеко за рамки обеспечения секретности данных. По мере все большей автоматизации процессов передачи и обработки информации и интенсификации информационных потоков методы шифрования приобретают уникальное значение. Новые информационные технологии в своей основе имеют двухключевое шифрование, которая позволяет реализовать протоколы, предполагающие, что секретный ключ известен только одному пользователю, т.е. протоколы, ориентированные на взаимное недоверие взаимодействующих сторон. Отметим основные приложения современного шифрования [19,20].
На практике, распространенными применениями шифросистемы с открытым ключом являются цифровые подписи и обмен секретными ключами через открытые каналы связи [29]. Известно [15, 17, 21...24], что одной из шифросистем с открытым ключом является алгоритм Мак-Элис, применяющий линейный код. Анализ алгоритма Мак-Элис показал, что использование данного алгоритма позволяет повысить скрытность, а также помехоустойчивость передаваемой информации. Кроме того, основными требованиями к практической реализации системы передачи информации являются высокая вычисленная скорость, обеспечение высокой надежности и низкая цена устройства. В настоящее время развитие цифровых технологий позволит реализовать данные требования.
Исходя из представленных проблем, в третий главе решаются следующие задачи: 1. Исследование и анализ применения алгоритма Мак-Элис для цифровой подписи и характеристик данного применения. 2. Анализ факторов влияющих на практическую реализацию и эффективное использование алгоритма Мак-Элис, кроме того, определение вычислительных затрат при применении данного алгоритма для обеспечения заданной скорости передачи информации. 3. Исследование реализации алгоритма Мак-Элис на практике при использовании современных цифровых устройств, а также вычисление затрат при применении данного алгоритма для обеспечения заданной скрытности и помехоустойчивости передаваемой информации.
Основываясь на идее использования односторонней функции с потайным ходом, Диффи В., Хеллман М. Е. предложили структуру шифросистемы с открытыми ключами для сети с многими абонентами [15... 17, 19, 20, 79]. Каждый абонент, например /-и, случайным образом выбирает некоторое значение параметра zh и держит его в секрете. Далее он формирует алгоритме и предоставляет его для опубликования в открытом справочнике, а также формирует алгоритм Д и держит его о секрете. Любой другой абонент, например j-vi, может послать /-му абоненту секретное сообщение М. Для этого он использует открытый алгоритм шифрования Е, и вычисляет кодовое слово 19,20] C = fz{M), (3.1) которое посылает /-му абоненту. Используя секретный алгоритм Д абонент / вычисляет исходный открытый текст [19,20]:
Эта обобщенная схема открытого шифрования может быть применена для получения цифровых подписей. В общем случае цифровая подпись представляет собой некоторое число со специфической структурой, которое допускает проверку с помощью открытого ключа того факта, что оно было выработано для некоторого сообщения с использованием секретного ключа. Для реализации цифровой подписи необходимо выбрать такую одностороннюю функцию с потайным ходом (с секретом) , для которой при всех значенях параметра z область определения функции f2, совпадает с областью её значений. При этом условии для любого сообщения, которое может быть представлено в виде числа из области определения функции Дх), абонент / может сформировать с помощью секретного алгоритма число Л = / ] (М). Если сообщение слишком велико, то его можно разбить на части необходимой меры и каждую из них подписать независимо.
