Содержание к диссертации
Введение
1 Анализ систем электронного документооборота 13
1.1 Обзор современных систем электронного документооборота 14
1.2 Методы организации защищенного документооборота 29
1.3 Анализ инфраструктуры открытых ключей 37
1.4 Особенности организации электронного документооборота на предприятии 48
1.5 Формирование проблемной ситуации. Постановка задач исследований 50
Выводы по 1 разделу 53
2 Организация защищенного электронного документооборота на основе разработки метода электронной цифровой подписи с открытым коллективным ключом 55
2.1 Анализ задач криптографии и основных принципов построения современных криптографических систем 55
2.2 Сравнительный анализ и обоснование методов организации систем защищенного электронного документооборота 63
2.3 Сравнительный анализ схем электронной цифровой подписи 74
2.4 Обоснование выбора математического аппарата эллиптических кривых 79
2.5 Разработка модифицированной схемы электронной цифровой подписи 84
2.6 Метод формирования и проверки электронной цифровой подписи на основе коллективного открытого ключа 90
Выводы по 2 разделу 93
3 Разработка алгоритмов моделирования криптографических систем на эллиптической кривой и оценки её стойкости 95
3.1 Сравнительный анализ группового закона сложения точек для эллиптических кривых в аффинной и проективной плоскостях 95
3.2 Анализ особенностей стандарта электронной цифровой подписи ГОСТ Р 34.10.2001 101
3.3 Разработка алгоритма выбора параметров электронной цифровой подписи на основе открытого коллективного ключа 104
3.4 Исследование алгоритмов оценки стойкости систем электронной цифровой подписи на эллиптических кривых 111
3.5 Пример нахождения личного ключа подписи на эллиптической кривой над полем GF(p) 119
Выводы по 3 разделу 121
4 Разработка методики организации защищенного электронного документооборота предприятия и рекомендации по программно-аппаратной реализации электронной цифровой подписи на основе открытого коллективного ключа 122
4.1 Методика организации защищенного электронного документооборота предприятия и особенности её внедрения 122
4.2 Определение способов повышения скорости генерации параметров эллиптической кривой 124
4.3 Определение способов повышения скорости выполнения операций в группе точек эллиптической кривой 127
4.4 Предложения по программно-аппаратной реализации электронной цифровой подписи на основе открытого коллективного ключа 136
Выводы по 4 разделу 140
Заключение 142
Список использованных источников 144
- Методы организации защищенного документооборота
- Сравнительный анализ и обоснование методов организации систем защищенного электронного документооборота
- Анализ особенностей стандарта электронной цифровой подписи ГОСТ Р 34.10.2001
- Определение способов повышения скорости генерации параметров эллиптической кривой
Введение к работе
В современных условиях увеличение количества информации, обрабатываемой, передаваемой и хранимой в автоматизированных системах управления (АСУ) предприятий и организаций привело к повышению актуальности задач [2, 16, 31]:
обеспечения конфиденциальности, целостности, неотрицания авторства электронного документа;
создания защищенного электронного документооборота;
обеспечения высокой скорости обработки и подписания электронного документа.
В настоящее время основу обеспечения безопасности электронного документооборота (ЭД) составляют системы электронной цифровой подписи (ЭЦП) [2, 20, 31, 44]. Наиболее широко применяемым видом ЭЦП является индивидуальная подпись. Однако вариант "один документ - одна подпись" является не единственным, требуемым на практике. В частности, вопросы передачи документов от имени некоторого коллегиального органа или от имени совокупности субъектов делают актуальным вопрос разработки таких систем ЭЦП как: групповая, кратная ЭЦП и ЭЦП на основе открытого коллективного ключа.
Современные системы электронного документооборота позволяют обрабатывать и подписывать документ одновременно только одним пользователем, что увеличивает время обработки и подписания документа, если его должны подписать несколько пользователей. Следовательно, размер ЭЦП увеличивается пропорционально числу пользователей, подписывающих электронный документ, в несколько раз. Кроме того, процедура проверки подлинности подписи подразумевает проверку подписей всех подписавших.
В области теории и практики разработки ЭЦП, как в нашей стране, так и за рубежом, издано большое количество трудов. Из их числа следует отметить работы Эль-Гамаля Т., ШнорраК., РабинаМ., КоблицаН., Ростовцева А.Г., Черемушкина А.В., Молдовяна Н.А., Еремеева М.А., Маховенко Е.Б. и др. [27, 28, 40, 44, 45, 54, 63, 68, 69, 78].
Создание метода формирования и проверки электронной цифровой подписи на основе открытого коллективного ключа (ЭЦП ОКК) даёт возможность обработки и подписания документа одновременно несколькими пользователями. При этом размер ЭЦП не увеличивается, что позволяет сократить объем избыточной информации, необходимой для аутентификации электронных документов и упростить протокол поддержки такой ЭЦП. Время на подписание документа остается прежним, как и при стандартной процедуре подписи, а время проверки подлинности ЭЦП уменьшается.
Таким образом, выявлена проблемная ситуация, определяемая как противоречие между необходимостью обеспечения подлинности и сохранения целостности информации в автоматизированной системе предприятия при коллективной обработке электронных документов и несоответствием существующих методов, алгоритмов и средств организации защищенного электронного документооборота современным требованиям защищенности, функциональности и оперативности.
Разрешение данной проблемной ситуации требует создания метода формирования и проверки электронной цифровой подписи на основе открытого коллективного ключа.
Объектом исследования является система защищенного электронного документооборота (СЗЭД) в автоматизированной системе управления предприятия, а предметом — методы создания и проверки электронной цифровой подписи при организации электронного документооборота.
Целью исследования является повышение оперативности обработки информации в защищенном электронном документообороте предприятия. Для достижения поставленной цели решалась научная задача построения схем электронной цифровой подписи на основе открытого коллективного ключа и криптографических конструкций на эллиптических кривых (ЭК). Достижение поставленной цели и решение научной задачи потребовало решения следующих частных задач исследований:
1. Проведения анализа современных методов и средств защиты систем электронного документооборота.
2. Осуществления выбора системы ЭЦП как основного механизма обеспечения оперативного защищенного электронного документооборота.
3. Разработки метода формирования и проверки ЭЦП ОКК.
4. Разработки алгоритма выбора параметров ЭЦП ОКК.
5. Разработки методики организации защищенного документооборота предприятия.
6. Разработки программного комплекса по реализации ЭЦП ОКК и рекомендации по её внедрению в систему защищенного электронного документооборота.
Основные положения, выносимые на защиту:
1. Метод формирования и проверки электронной цифровой подписи на основе открытого коллективного ключа, использующий эллиптическую криптографию.
2. Алгоритм выбора параметров ЭЦП ОКК, позволяющий повысить оперативность обработки информации.
3. Методика организации защищенного документооборота в АСУ предприятия и рекомендации по программно-аппаратной реализации ЭЦП ОКК.
Методы выполнения исследований. Для решения задач диссертационного исследования в работе применялись методы системного анализа, теории множеств, теории чисел и алгебраической геометрии. В ходе разработки предлагаемого метода и проверки его работоспособности проводились вычислительные эксперименты.
Достоверность полученных результатов диссертационной работы определяется корректным использованием математического аппарата теории чисел, совпадением теоретических результатов по использованию
вычислительных задач высокой сложности с результатами вычислительных экспериментов, апробированием результатов на научных конференциях.
Научная новизна работы состоит в обосновании и разработке метода формирования и проверки электронной цифровой подписи на основе открытого коллективного ключа и криптографических конструкций с использованием эллиптических кривых, позволяющего повысить оперативность совместной обработки электронных документов при сохранении требуемого уровня защищённости.
Практическая значимость работы состоит в разработке программного комплекса ЭЦП ОКК и возможности его реализации в существующих и перспективных СЗЭД, что позволит повысить оперативность обработки электронных документов.
Результаты проведённых исследований изложены в четырех главах.
В первой главе отмечается значимость внедрения защищенного электронного документооборота в структуру автоматизированных систем управления предприятием. Показано, что внедрение защищенного электронного документооборота (ЭД) позволяет обеспечить: подлинность информации, автоматизацию работы с документами, систематизацию хранения информации, уменьшение количества бумажных документов, облегчение работы пользователей.
Проводится анализ современных систем ЭД и выявляются их недостатки с позиций обеспечения информационной безопасности.
В общем виде сформулированы подходы к устранению указанных недостатков: внедрение юридически значимой ЭЦП по схемам ГОСТ и альтернативным схемам; расширение функциональности схем ЭЦП; обеспечение разграничения прав доступа; полная поддержка жизненного цикла электронного документа; внедрение возможностей совместной работы с документами и управление потоками работ; повышение удобства работы пользователя.
Определены цель проведения диссертационного исследования и частные задачи исследования.
Во второй главе на основе применения теоретико-множественного подхода выполнена постановка научной задачи исследования.
При разработке метода формирования и проверки ЭЦП ОКК предложено использовать групповой закон сложения точек эллиптической кривой.
Разработан обобщенный метод формирования и проверки ЭЦП ОКК, который состоит из трёх этапов: формирования ЭЦП ОКК на основе генерации индивидуальных параметров подписи и применения функции, отображающих их в коллективный параметр подписи; собственно создание ЭЦП ОКК и отправка её вместе с электронным документом соответствующим пользователям АСУ предприятия; проверка ЭЦП ОКК с использованием открытого коллективного ключа.
Произведено сравнение характеристик обычной и ЭЦП ОКК для т пользователей, которое показало, что сложность генерации подписи является одинаковой, а сложность проверки ЭЦП ОКК в т раз меньше.
Исследована реализуемость ЭЦП ОКК на основе известных алгоритмов ЭЦП и показана возможность разработки ЭЦП ОКК с использованием отечественных стандартов цифровой подписи и схемы Шнорра.
На основе стандарта ЭЦП РФ ГОСТ Р 34.10-2001 разработана схема формирования и проверки ЭЦП ОКК, которая соответствует обобщенному методу ЭЦП ОКК.
Третья глава диссертационной работы посвящена разработке алгоритма выбора параметров ЭЦП ОКК.
Показано, что параметрами, от которых зависит безопасность систем ЭЦП в целом и ЭЦП ОКК в частности, с применением ЭК, являются: - вид конечного поля;
- характеристика поля и (или) его расширения;
- уравнение ЭК;
- порядок циклической подгруппы точек ЭК;
- генератор подгруппы точек ЭК.
Выявлен ряд свойств кривых, при которых существенно уменьшается стойкость. Поскольку основным параметром, определяющим стойкость, является величина порядка группы на кривой, был разработан алгоритм выбора параметров ЭЦП ОКК, основанный на выборе параметров ЭК с требуемым порядком группы. Результатом выбора параметров ЭЦП ОКК является уравнение ЭК с порядком группы, удовлетворяющим требуемой стойкости и скорости преобразования.
Применение данного алгоритма позволяет осуществлять поиск уравнения ЭК для создания ЭЦП ОКК с требуемым уровнем стойкости за конечное число шагов с невысокой временной сложностью.
Четвертая глава посвящена разработке методики организации защищенного документооборота в АСУ предприятия и обоснованию практических рекомендаций по программно-аппаратной реализации ЭЦП ОКК.
Методика организации защищенного электронного документооборота опирается на обследование АСУ предприятия, анализ организационной структуры и информационных потоков. Кроме того, в методику включены вопросы: создания удостоверяющего центра в структуре АСУ предприятия для придания легитимности и юридической значимости защищенного электронного документооборота; разработки требований и организация процессов ЭД в АСУ предприятия (формирование, отправка, доставка, проверка подлинности, подтверждение получения, отзыв, учёт, хранение электронных документов); определения правил использования ЭЦП и ЭЦП ОКК в ЭД; разработки требований и определения порядка создания криптографических ключей, выдачи электронных цифровых сертификатов, действий при компрометации ключей.
Составной частью предложенной методики является разработанный программный комплекс, в котором реализован метод формирования и проверки ЭЦП ОКК и алгоритм выбора параметров ЭЦП ОКК. Его возможности включают формирование ЭЦП и ЭЦП ОКК, проверку ЭЦП и ЭЦП ОКК, генерацию ключей подписи и проверки, генерацию эллиптической кривой, параметры которой удовлетворяют всем требованиям стандарта на ЭЦП. Назначение программного комплекса - обеспечение целостности и авторства хранимой и обрабатываемой информации в системе защищенного электронного документооборота предприятия на основе применения систем ЭЦП ОКК.
Проведено исследование безопасности ЭЦП ОКК в сравнении с системами ЭЦП подобного и других видов. Показано, что выигрыш в показателе безопасности при использовании аддитивной группы точек эллиптических кривых в сравнении с использованием мультипликативной группы кольца целых чисел зависит от длины ключа и может достигать нескольких порядков при равной длине ключа. Преимущество использования ЭК при создании ЭЦП ОКК подтверждается также результатами исследования скорости криптографического преобразования в зависимости от длины ключа.
В заключении сформулированы основные результаты работы, кратко охарактеризована их новизна и практическая ценность. Сделан вывод о степени выполнения поставленных задач и достижении цели исследований.
Реализация и внедрение результатов исследований.
Основные результаты диссертации реализованы в Санкт-Петербургском филиале ФГУП «ЗащитаИнфоТранс» и в учебном процессе ФГОУ ВПО «Петербургский государственный университет путей сообщения» при изучении дисциплины «Криптографические методы защиты информации». Апробаі{ия. Основные результаты работы прошли апробацию в процессе докладов на II Международной научно-практической конференции «Актуальные проблемы развития железнодорожного транспорта» (Самара, 2005), 62-й научно-технической конференции «Неделя науки - 2002» (Санкт-Петербург, ПГУПС, 2002), 11-й, 12-й и 14-й международных научно-практических конференциях «Инфотранс-2006», «Инфотранс-2007» и «Инфотранс-2009», на плановых научных семинарах кафедры информатики и информационной безопасности ПГУПС.
Публикации. Материалы диссертации опубликованы в 13 работах, в том числе: 11 статьях и докладах на научно-технических и научно-практических конференциях, из них одна в издании, рекомендованном ВАК Минобрнауки России, 2 отчетах НИР.
Диссертационная работа состоит из введения, четырех глав основного содержания с выводами по каждой главе, заключения, списка литературы, включающего 80 наименований. Материалы диссертации изложены на 153 страницах, включающих 20 иллюстраций и 16 таблиц.
Методы организации защищенного документооборота
Документы в системе электронного документооборота являются информацией и, стало быть, обладают следующими важными с точки информационной безопасности свойствами: конфиденциальностью, целостностью, доступностью, наличием подтвержденного (безусловного) автора [2, 16, 18, 19,34].
Конфиденциальность информации - это субъективно определяемая характеристика (свойство) информации, составляющая коммерческую или личную тайну.
Целостность информации — свойство информации, заключающееся в её существовании в неискаженном виде (неизменном по отношению к некоторому фиксированному её состоянию).
Доступность информации — свойство информации, обеспечивающее беспрепятственный доступ к ней для проведения санкционированных операций по ознакомлению, документированию, модификации и уничтожению при её обработке техническими и/или алгоритмическими средствами.
Неотрицание (подтверждение) авторства означает, что отправитель сообщения (автор документа) впоследствии не должен иметь возможности ложно отрицать отсылку сообщения (авторство документа).
Таким образом, комплекс технических (программных) и организационно-правовых решений по защите системы электронного документооборота (разработке системы защищенного документооборота) должен гарантировать: 1. Конфиденциальность хранимых, обрабатываемых и передаваемых электронных документов. 2. Целостность электронных документов. 3. Наличие и безусловность признания авторства электронного документа. 4. Надёжность и отказоустойчивость системы электронного документооборота. Если надёжность и отказоустойчивость развернутой в организации (вузе) системы электронного документооборота обеспечивается за счёт применения соответствующего оборудования от заслуживающих доверия поставщиков и выработки детальных технических требований к программному обеспечению, то выполнение первых трёх требований, относящихся непосредственно к обрабатываемой в системе электронного документооборота информации, обеспечивается средствами криптографической защиты информации. Криптографическая защита — защита данных с помощью криптографического преобразования, подразумевающая преобразование данных шифрованием и выработкой имитовставки.
Алгоритм криптографического преобразования — набор математических правил, определяющих содержание и последовательность операций, зависящих от ключа шифрования, по преобразованию исходного открытого текста к зашифрованному и, наоборот, расшифрованию информации.
Ключ — конкретное секретное состояние некоторых параметров алгоритма криптографического преобразования информации, обеспечивающее выбор одного преобразования из совокупности всевозможных для данного алгоритма преобразования.
Обеспечение конфиденциальности электронных документов обеспечивается при помощи средств шифрования (преобразования открытых данных в зашифрованные с помощью шифра), целостности и неотрицания авторства — при помощи электронной цифровой подписи.
Система подписи цифровой - система криптографическая, выполняющая аутентификацию источника данных или аутентификацию сообщения [48]. Математическая модель системы подписи цифровой включает схему подписи цифровой и систему ключевую, в качестве которой обычно выступает инфраструктура открытых ключей.
Электронная цифровая подпись (ЭЦП) — это присоединяемое к тексту (электронному документу, сообщению) его криптографическое преобразование, которое позволяет при получении текста другим пользователем проверить авторство и подлинность [16].
Стойкость зашифрованных данных обеспечивается путем обеспечения конфиденциальности криптографического ключа. Однако на практике любой шифр, используемый в той или другой криптосистеме, поддаётся раскрытию с определённой трудоемкостью. Таким образом, одним из критериев при выборе того или иного криптографического алгоритма для использования в системе защищенного документооборота является криптостойкость применяемых шифров в алгоритме криптопреобразования, то есть возможность раскрыть шифр без знания ключа.
В современных информационных системах с большим количеством пользователей типовыми являются следующие проблемы
Сравнительный анализ и обоснование методов организации систем защищенного электронного документооборота
При передаче информации по общедоступным каналам связи возникает необходимость решения задач обеспечения информационной безопасности. При этом первостепенную важность приобретает решение следующих трёх основных задач: - обеспечение конфиденциальности передаваемой информации; - обеспечение целостности информации; - обеспечение авторства электронных документов. Эти требования реализуются применением системы защищенного электронного документооборота (СЗЭД), основанной на ИОК (инфраструктура открытых ключей) и предназначенной для обеспечения достоверности, целостности и аутентификации передаваемой информации. Задачами, решаемыми внедрением защищенной СЗЭД, являются [3-6, 16,36,52]: - конфиденциальность — информация должна быть защищена от несанкционированного прочтения, как при хранении, так и при передаче. В системах криптографической защиты конфиденциальность обеспечивается шифрованием. - контроль доступа — информация должна быть доступна только для того, для кого она предназначена. В системах криптографической защиты контроль доступа обеспечивается шифрованием. - аутентификация — возможность однозначно идентифицировать отправителя. В системах криптографической защиты аутентификация обеспечивается ЭЦП и сертификатом. -целостность - информация должна быть защищена от несанкционированной модификации, как при хранении, так и при передаче.
В системах криптографической защиты целостность обеспечивается электронной цифровой подписью и имитозащитой. - неотрекаемость — отправитель не может отказаться от совершённого действия. В системах криптографической защиты неотрекаемость обеспечивается электронной цифровой подписью и сертификатом. В контексте функционирования СЗЭД, технология ИОК может использоваться в следующих областях [29, 35]: - организация внутреннего ведомственного защищенного документооборота, а также защищенного обмена информацией со сторонними организациями, при этом они могут иметь собственную ИОК -инфраструктуру; - организация защищенного доступа к Web-приложениям, СУБД, обеспечение защиты управляющего трафика телекоммуникационной сети; - организация единой системы аутентификации и централизованного управления аутентификационной информацией (интеграция с ОС, СУБД, межсетевыми экранами, системами разграничения доступа и т.д.), реализация принципа единой подписи (один пользователь - один ключ); - использование открытых сетей в качестве среды передачи юридически значимой информации (организация защищенной электронной почты, ЭЦП данных); - организация сервиса «неотрекаемости» (по терминологии Х.800) -невозможности «отказа от обязательств», т. е. отправитель не может отказаться от совершённого действия; - реализация централизованной политики информационной безопасности (идентификационная информация владельца, содержащаяся в сертификате, может быть использована службой контроля доступа). Таким образом, при проектировании СЗЭД ИОК должна рассматриваться как часть комплексной системы обеспечения безопасности функционирования АС обмена информацией. ИОК - это комплексная система, обеспечивающая все необходимые сервисы для использования технологии с открытыми ключами.
Цель ИОК состоит в управлении ключами и сертификатами, посредством которого поддерживается надежная сетевая среда. ИОК позволяет использовать сервисы шифрования и выработки цифровой подписи согласованно с широким кругом приложений, функционирующих в среде с открытыми ключами. Ключевым элементом организационной структуры СЗЭД, включенным в состав ИОК является Удостоверяющий центр (УЦ). Основные функции УЦ как организации регламентируются Федеральным законом «Об электронной цифровой подписи». Схема работы УЦ АС предприятия с различными типами пользователей представлена на рисунке 2.4. Структура Щ должна включать следующие функциональные элементы [28,48]: -Центр сертификации (ЦС), обеспечивающий формирование сертификата пользователя по запросам Центра регистрации с обеспечением уникальности информации в данных сертификатах, ведение базы данных сертификатов и её изменение по запросам от Центра регистрации, взаимодействие с Центром регистрации и протоколирование своей работы.
Анализ особенностей стандарта электронной цифровой подписи ГОСТ Р 34.10.2001
Параметрами цифровой подписи являются [21]: - простое число р- модуль эллиптической кривой, - эллиптическая кривая Е; целое число т - порядок группы точек ЭК Е; - простое число q - порядок циклической подгруппы группы точек ЭК Е, для которого выполнено следующее условие: - точка G O ЭК Е, удовлетворяющая равенству qxG = 0; - хэш-функция / (), отображающая сообщения, представленные в виде двоичных векторов произвольной конечной длины, в двоичные вектора заданной длины. Каждый пользователь схемы цифровой подписи должен обладать личными ключами: - ключом подписи - целым числом d, удовлетворяющим неравенству О d q; - ключом проверки - точкой Q ЭК Е, удовлетворяющей равенству d х G = Q. Для получения цифровой подписи под сообщением МєГш необходимо выполнить следующие действия (шаги). Шаг 1 - вычислить хэш-код сообщения М :h= Н(м). Шаг 2 - вычислить целое число а, двоичным представлением которого является вектор И и определить Если е = 0, то определить е = 1. Шаг 3 - сгенерировать случайное (псевдослучайное) целое число к, удовлетворяющее неравенству Шаг 4 - вычислить точку эллиптической кривой C = kxG и определить где хс - х-координата точки С. Если г = 0, то вернуться к шагу 3. Шаг 5 - вычислить значение s = 0, то вернуться к шагу 3. Шаг 6 - вычислить двоичные векторы г и s, соответствующие г и s, и определить цифровую подпись С = v II ) как конкатенацию двух двоичных векторов.
Исходными данными этого процесса являются ключ подписи d и подписываемое сообщение М, а результатом - цифровая подпись . Для проверки цифровой подписи под полученным сообщением М необходимо выполнить следующие действия. Шаг 1 - по полученной подписи вычислить целые числа г и s . Если выполнены равенства 0 r q, 0 s д,то перейти к следующему шагу. В противном случае подпись не верна. Шаг 2 - вычислить хэш-код полученного сообщения М :h = h(M). Шаг 3 - вычислить целое число а, двоичным представлением которого является вектор h , и определить Если е = 0, то определить е — \. Шаг 4 - вычислить значение v s= e-1(modg). Шаг 5 - вычислить значения Шаг 6 - вычислить точку эллиптической кривой C = z1x.G+z2xQ и определить где хс - х-координата точки С. Шаг 7 - если выполнено равенство R = г, то подпись принимается, в противном случае подпись не верна. Исходными данными этого процесса являются подписанное сообщение М, цифровая подпись Q , ключ проверки Q, а выходным результатом -свидетельство о достоверности или ошибочности данной подписи.
Основной задачей при создании криптосистемы на эллиптической кривой, в том числе электронной цифровой подписи на основе коллективного открытого ключа (ЭЦП ОКК), является расчёт числа точек [27, 28, 45]. При этом, для того чтобы выполнялись криптографические требования, нужно проверить в среднем O(\ogq) эллиптических кривых. В стандарте на подпись не определяется процесс генерации параметров схемы цифровой подписи. Конкретный алгоритм (способ) реализации данного процесса определяется субъектами схемы цифровой подписи исходя из требований к аппаратно-программным средствам, реализующим электронный документооборот. С одной стороны это является недостатком, т. к. заставляет разработчиков криптографических систем искать методы расчёта точек эллиптической кривой, методы генерации кривых, удовлетворяющих заданным требованиям надёжности и скорости вычислений. Но с другой стороны этот факт позволяет повысить криптографическую стойкость стандарта и обеспечивает гибкость при разработке криптографических систем, использующих данную схему цифровой подписи, предоставляя авторам криптосистем определённую свободу при выборе методов генерации кривых. Обнаружение уязвимостеи кривых, процесс генерации которых был бы описан в стандарте, привело бы в конечном итоге к отказу от использования данного стандарта и к необходимости его изменения и доработки. В качестве показателя стойкости к криптоанализу ЭЦП ОКК на основе применения группового закона сложения на ЭК предлагается использовать асимптотическую -оценку сложности алгоритма вскрытия в терминах О — символики [38, 49]. На основе исследования алгоритмов криптоанализа показано, что стойкость ЭЦП ОКК существенно зависит от порядка группы, определяется как сложность наилучшего алгоритма по определению индекса и оценивается значением o( j, где р — наибольший простой множитель порядка группы точек кривой.
Определение способов повышения скорости генерации параметров эллиптической кривой
При выборе параметров эллиптической кривой приходится выполнять перебор возможных значений характеристики поля. Наиболее трудоёмкой операцией при переборе является проверка на простоту значений характеристик поля и порядка группы точек эллиптической кривой. При проверке одного значения характеристики поля необходимо проверить два значения порядка группы точек. Для того чтобы выполнялись криптографические требования в среднем необходимо опробовать кривых. Для ускорения процесса генерации параметров кривой необходимо определить наиболее эффективный алгоритм проверки чисел на простоту и ограничить число классов проверяемых характеристик поля, исключив те значения характеристик, которые не позволяют построить группу точек.
Для проверки целого рационального числа на простоту обычно используются вероятностные алгоритмы. Это обусловлено тем, что детерминированные тесты значительно менее «прозрачны» и более сложны, а разницы между понятием доказуемо простого числа и числа, предположительно являющегося простым с вероятностью ошибки 10 10 , практически нет. Рассмотрим наиболее известные алгоритмы проверки чисел на простоту [52]: 1. Тест Миллера-Рабина. Вероятность ошибки для к циклов теста составляет 2 2к. Данные оценки являются весьма пессимистичными, так как с ростом длины проверяемого числа вероятность ошибки быстро снижается. Так для чисел длины 100 десятичных знаков вероятность ошибки для одного цикла не превышает 10"7. Существуют и более точные оценки: вероятность (к/Уг ошибки в одном тесте для и 100 бит составляет менее 4w2V2 . Для 256-битового числа вероятность ошибки в 6 тестах менее 2 51. Сложность алгоритма составляет o((log/?)3). 2. Тест Соловея-Штрассена. Сложность алгоритма составляет o((log/?)3). Вероятность ошибки теста в к циклах равна 2 к. Данный тест требует вычисления символа Якоби. 3. Тест Леманна. Довольно простой тест, вероятность ошибки в к циклах равна 2 к, сложность алгоритма O log/?)3). 4. Тест на основе проверки соответствия числа точек эллиптической кривой над кольцом вычетов по модулю р расчётному значению. Тест не эффективен для чисел длиной больше 500 бит. Наиболее эффективным тестом является тест Миллера-Рабина. В этом тесте вероятность прохождения проверки составным числом убывает быстрее, чем в других тестах. На практике этот тест применяется совместно с проверкой делимости проверяемого числа на простые числа менее 256 (отсеивается 80% нечётных чисел). Наиболее эффективной является проверка на делимость для всех простых чисел, меньше 2000. В общем случае, доля нечётных кандидатов, которые не делятся ни на одно простое число, меньшее п, равно 1.12/lnw. Рассмотрим описание теста Миллера-Рабина.
Необходимо проверить число р на простоту. Вычислим числа b и т, такие что р = 1 + 2Ь т. Далее дано описание одного цикла теста. 1. Выберите случайное число я, меньшее/?. 2. Установите j = 0 и z = ат{то&р). 3. Если z = l или z = р -1, то число р — вероятно простое. 4. Если j 0 и z = 1, то число р - составное. 5. 7 = ./ + 1 6. Если j Ь и гФ р-1,то z = z2(mod/?) и вернуться на шаг4. 7. Если j = b и z /?-1, то число/? — составное. 8. Если z = /? — 1, то число/? — вероятно простое. В разработанном программном комплексе используется тест Миллера-Рабина с 5 циклами, что обеспечивает достаточно низкую вероятность ошибки, и проверка на делимость для простых чисел, меньших 2000. В таблице 4.1 приведена зависимость времени проверки простоты числа от его длины с помощью указанного метода с проверкой на делимость для малых простых чисел и без неё. Как было показано в п. 3.1, основной криптографической операцией в алгоритмах на эллиптических кривых, является умножение точки на число Р = пхО.
В операции сложения двух точек при рассмотрении кривой в аффинной плоскости присутствует операция инверсии элемента группы, а в случае умножения точки на достаточно большое число (порядка 250 двоичных разрядов), операция инверсии повторяется многократно, что делает операцию умножения длительной. В соответствии с поставленной в работе задачей оценки стойкости необходимо максимально сократить время, затрачиваемое на выполнение каждого шага при криптоанализе. В связи с этим определим подходы к повышению скорости вычислений при выполнении групповых операций. Частными подходами к повышению скорости вычислений при выполнении групповых операций является минимизация количества операций сложения, умножения, модульного деления (обращения) в поле. Использование проективных координат устраняет самую трудоёмкую операцию модульного деления. Кроме того, имеется возможность сокращения числа операций при операции умножения точки ЭК на число.
