автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.19, диссертация на тему:Протоколы коллективной электронной цифровой подписи над эллиптическими кривыми

'/X /

Доронин Станислав Евгеньевич

ПРОТОКОЛЫ КОЛЛЕКТИВНОЙ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ НАД ЭЛЛИПТИЧЕСКИМИ КРИВЫМИ

Специальность: 05.13.19 -Методы и системы защиты информации, информационная безопасность

Автореферат диссертации на соискание ученой степени кандидата технических наук

1 О НОЯ 2011

Санкт-Петербург - 2011

4859378

Работа выполнена на кафедре автоматизированных систем обработки информации и управления Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" им. В.И.Ульянова (Ленина)

Научный руководитель: доктор технических наук, профессор

Молдовян Николай Андреевич

Официальные оппоненты: доктор технических наук, профессор

Оков Игорь Николаевич

доктор технических наук, профессор Котенко Игорь Витальевич

Ведущая организация: Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики

Защита диссертации состоится "25" ноября 2011 г. в 15 часов 30 минут на заседании совета по защите докторских и кандидатских диссертаций Д 002.199.01 Санкт-Петербургского института информатики и автоматизации РАН по адресу: 199178, Россия, Санкт-Петербург, 14 линия, дом 39. С диссертацией можно ознакомиться в библиотеке СПИИРАН Автореферат разослан "24" октября 2011 г.

Ученый секретарь

диссертационного совета Д 002.199.01

"/'СЬ'С-р1 ¿>

Нестеру к Ф. Г.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

подписи, а так же применения новых схем, основанных на конечных векторных пространствах.

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

С целью решения поставленной задачи в ходе выполнения диссертационных исследований решались следующие частные задачи:

1) анализ и разработка механизмов противодействия специфическим атакам на коллективную ЭЦП;

2) построение схем коллективной ЭЦП с использованием эллиптических кривых;

3) разработка схем для защиты бумажных носителей от подделки;

4) разработка подходов осуществления потенциальных атак на схемы коллективной ЭЦП и оценка стойкости разработанных схем коллективной ЭЦП;

5) реализация протоколов эллиптической криптографии с использованием полей, заданных в явной векторной форме;

Методы исследования. При выполнении диссертационного исследования использован аппарат и методы системного анализа, теории вероятностей, теории чисел, алгебры, криптографии, информатики и информационной безопасности.

Научная новизна. Новизна результатов диссертационного исследования заключается в предложенных механизмах и способах построения и модификации схем коллективной ЭЦП. Новыми результатами являются:

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

2) Механизмы снижения вычислительной сложности процедур проверки и формирования коллективной ЭЦП.

3) Протоколы, позволяющие сократить размер подписи при защите документов на бумажных носителях.

4) Сценарии потенциальных атака и оценка стойкости разработанных протоколов.

5) Способ ускорения алгоритмов и протоколов эллиптической криптографии, отличающийся заданием эллиптических кривых над конечными полями, представленными в явной векторной форме.

Основным результатом работы является созданием механизмов повышения эффективности существующих и новых схем коллективной ЭЦП для применения к бумажным и электронным документам.

Научные положения, выносимые на защиту:

1) Способ формирования коллективной ЭЦП, отличающийся обеспечением ее внутренней целостности.

2) Протокол коллективной ЭЦП, отличающийся сокращением вычислительной сложности процедур ее проверки и формирования.

3) Протокол композиционной ЭЦП, сокращающий ее размер для использования на бумажных носителях.

4) Алгоритм построения ЭЦП, отличающийся использованием эллиптических кривых, заданных над конечными полями в явной векторной форме.

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

Практическая реализация и внедрение результатов работы.

Результаты диссертационного исследования использованы при выполнении научно-исследовательских работ по гранту РФФИ (№ 08-07-00096-а), фанту Санкт-Петербурга для студентов, аспирантов молодых ученых и молодых кандидатов наук Правительства Санкт-Петербурга, 2010г. Результаты диссертационного исследования внедрены на кафедре автоматизированных систем обработки информации и управления (АСОИУ) Санкт-Петербургского государственного электротехнического университета в учебный процесс по специальности "Компьютерная безопасность" по дисциплинам "Криптографические методы защиты информации" и "Теоретические основы криптографии" при чтении курсов лекций, проведении практических работ и курсовом проектировании.

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

Апробация результатов работы. Основные результаты диссертационной работы докладывались на следующих конференциях:

1) V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2007)», г. Санкт-Петербург, 23-25 октября 2007г.

2) Всеармейская научно-практическая конференция «Инновационная деятельность в Вооруженных силах Российской Федерации», г. Санкт-Петербург, 22-23 ноября 2007г.

3) XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008), г. Санкт-Петербург, 22-24 октября 2008г.

4) VI Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2009)», г. Санкт-Петербург, 28-30 октября 2009г.

5) XV Санкт-Петербургская Ассамблея молодых учёных и специалистов и Международная научно-практическая конференция XXXIX НЕДЕЛЯ НАУКИ СПбГПУ, г. Санкт-Петербург, 7 декабря 2010 г.

Публикации. По теме диссертации опубликованы 10 научных работ, из них 6 статей, 3 из которых опубликованы в журналах из списка ВАК, и 4 работы в сборниках трудов международных и российских научно-технических конференций. По результатам исследований подана 1 патентная заявка.

Структура и объем работы. Диссертация состоит из введения, 4 глав, приложения, заключения и списка литературы. Диссертационная работа изложена на 130 страницах, работа содержит 20 рисунков, 5 таблиц и список литературы из 60 наименований.

Содержание работы

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

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

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

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

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

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

В качестве базовой схемы на основе которой производится демонстрация описанных свойств, выбирается схема построения коллективной ЭЦП на базе ЭК, полно описанная в литературе, представленная на рис. 1

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

Рис.1 - базовая схема КЭЦГ1

В предлагаемой схеме коллективной ЭЦП, процедуры формирования и проверки подлинности модифицируются следующим образом: генерируют ЭК в виде совокупности точек, каждая из которых определяется парой чисел, являющихся соответственно абсциссой и ординатой данной точки ЭК в декартовой системе координат, генерируют точку в ЭК, имеющую порядок <7, формируют совокупность из и > 2 секретных ключей в виде значений к\, А"2, ..., кт по секретным ключам формируют п открытых ключей в виде точек Р), Р;,.... Р„ ЭК, получаемых по формуле Р, = кгО, где /=1,2,...,«, принимают ЭД, представленный значением 11, формируют коллективный открытый ключ в виде точки Р ЭК, генерируемой в зависимости от точек ЭК ^а, > , •••, » гДе аь «2> ••-. а„, - натуральные числа; 2 < т <п; щ<п и /=1,2,...,/?/, в зависимости от принятого ЭД и от значения секретных ключей Ц , ка2, ■■■, к<гт , формируют ЭЦП в виде двух чисел, формируют

первое А и второе В проверочные значения, сравнивают их и при совпадении их параметров делают вывод о подлинности ЭЦП, причем, по крайней мере, одно из проверочных значений формируют в зависимости от коллективного открытого ключа Р, новым является то, что ЭЦП формируют в зависимости от коллективного открытого ключа, а в качестве ЭК используют ЭК,

заданную над простым полем GF(p), где р - простое число вида р = 2* ±ns2i! ±\iu2h± 1, где к>99; 0<g<k; 0<A<g; nf е{0,1};цА е{0,1}.

Снижение временной сложности операции умножения по модулю р определяется следующими математическими выкладками. Пусть требуется умножить по модулю р два ¿-разрядных двоичных числа а и Ь. Выполним операцию арифметического умножения, получим число c = ab, которое представим в виде конкатенации четырех чисел а,,и2,и3,и4: с = к, ||и2 ||и. ||и4, где lt2 ~ (к - £)-разрядное значение, и3 -(g - //(-разрядное значение и "4 - А-разрядное значение, а разрядность значения не превышает значение к + 1. Тогда число с можно представить в виде следующей суммы

с = и, || и21| щ || и4 = г/, • 2к + и2 ■ 2s + щ ■ 21' + и4 =

= н, •2* ±н, -2* ±г/, •2h±u{ +«, ■2s+u,-2h + ul + + u2 +иъ '2h + «4 =

= щ (2к ± 28 ± 2'1 ± l) + (гл + г/,) • 2s + (w3 +//,)• 2h + u4 + и,. Из последнего выражения видно, что первое слагаемое сравнимо с нулем по модулю р- 2* ± 2* ± 2fc ± I, поэтому после выполнения пяти операций сложения и двух операций арифметического сдвига (на g и h двоичных разрядов) получим (g + к+ 1)-разрядное число с' = ч[ || и\ || щ || и'4 = с mod р, где и'2 - (к - £)-разрядное значение, и'3 -(g - А)-разрядное МДЧ и и\ - Л-разрядное значение, а разрядность значения и[ не превышает значение g+ 1. Представим число с' в виде следующей суммы

с-' = II u\ II щ II и4 = и\ ■ 2к + u[ ■ 2s + u\ • 2h + u\ = = u\-2k ±u\-2* ±u\-2h ±u\ + u\-2* T«;-2* + + + г/i ■ 2я + г/j • 2'1 + г/4 =

=ц;(2' ± 2* ± 2Л ± i)+(«;+и;) • г* + («;+«;) • 24+и\+

Из последнего выражения видно, что первое слагаемое сравнимо с нулем по модулю р = 2* + ¡л±ц,,2'' ± ], поэтому после выполнения пяти операций сложения и двух операций арифметического сдвига получим (2g + 1)-разрядное число с*. При выборе значения g <к!2 разрядность числа с * будет меньше значения к, т. е. с* = ab mod р. Таким образом, для выбранной структуры простого модуля операция модульного умножения выполняется за одно арифметическое умножение, четыре операции арифметического сдвига и десять арифметических сложений (вычитаний),

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

В третьей главе производится анализ безопасности протоколов ЭЦП и возможные атаки на базовые протоколы, и протоколы коллективной ЭЦП, основанные на них. Рассматривается атака на схему коллективной ЭЦП базирующейся на сложности задачи дискретного логарифмирования в группе точек ЭК на базе стандарта ГОСТ Р 34.10-2001.

Пусть ш-1 пользователей хотят сформировать коллективную подпись,

»-I

проверяемую но коллективному открытому ключу Q = Q'+Qm, где Q' = Yjй -

¿-I

то есть ш-1 пользователей объединили свои усилия для того, чтобы сформировать пару чисел (R.S), такую что R = .г,- modi?, где точка С вычисляется из выражения С = ((Se~!) mod q)G + ((q~ К)е~' mod q)(Q'+Qm). Это означает, что они могут подделать подпись «под» открытый ключ Q' = Q' + Qm, то есть вычислить значения R и S, которые удовлетворяют уравнению R = лгс mod?, где С = (№ ')mod</)G + ((q-R)elmodi?)£>'.

Ясно, что последнее выражение обозначает возможность подделать цифровую подпись в базовой схеме ЭЦП, так как открытый ключ Q' имеет случайное значение, так же как и открытый ключ, принадлежащий какому-то отдельному пользователю. Формально докажем этот факт.

Используя предполагаемую возможность нарушители формируют коллективную подпись (Л",5"), соответствующую коллективному открытому ключу Q = Q'+Ql„ где в качестве 0'„ взято значение Qm - Qm - Q'.

Коллективная подпись удовлетворяет соотношению

С = ((S'e') mod q)G + ((</ - R') оГ1 mod = =((SV')m od 9)G + ((? - Л V mod q){ff + &„)=> => С = ((SV' )modq)G + ((q-R')e~' mod q)Qa.

Последнее выражение показывает, что (Я\S") является подлинной индивидуальной ЭЦП т-го пользователя.

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

Пусть нарушитель желает получить возможность подделывать подписи от коллектива подписывающих, в который входят z пользователей, владеющих правильными ключами уь j';, ..., уг. Каждый из этих ключей сформирован по формуле у,- = ах> moil р. Для этого нарушитель вычисляет некорректный открытый ключ, равный

где X— секретное значение, которым нарушитель может воспользоваться для подделки коллективной подписи от имени коллектива, в который входит он сам и 2 выбранных им пользователей-жертв. Коллективная ЭЦП этого коллектива проверяется по коллективному открытому ключу, равному произведению открытых ключей всех членов коллектива, т.е. по открытому ключу

который соответствует секретному ключу X как правильно сформированный индивидуальный открытый ключ пользователя владеющего секретным ключом X. Поскольку подлинность коллективной ЭЦП проверяется но тому же проверочному уравнению, что и индивидуальная ЭЦП, то владелец секретного ключа X может сформировать коллективную ЭЦП от имени указанного коллектива как индивидуальную ЭЦП, соответствующую секретному ключу X. Однако, легко видеть, что нарушитель не сможег сформировать индивидуальную ЭЦП, соответствующую открытому ключу У. Он также не сможет сформировать коллеетивную ЭЦП никакого подмножества пользователей, входящих в рассматриваемый коллектив (за

У = ах П v, 'mod/? ,

исключением случая, когда ему удастся решить задачу дискретного логарифмирования, но тогда он полностью взломает всю криптосистему).

Таким образом, применение коллективной ЭЦП связано с явным заданием требования выполнения процедуры проверки корректности открытых ключей. Наиболее удобным вариантом выполнения такой процедуры является задание требования подписать представляемую заявку на регистрацию открытого ключа в удостоверяющем центре.

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

Конечное множество /«-мерных векторов задается следующим образом:

я-е + ЬЛ + ... + с'},

где еД ... ] ~ базисные вектора, которые будем представлять также и в виде набора координат (а,Ь,...,с), являющихся элементами конечного поля СР\р) где р - простое число. В дальнейшем нас будут интересовать условия, при которых рассматриваемое множество векторов будет обладать свойствами расширенного поля, поэтому определим на этом множестве две операции -сложение векторов и умножение векторов. Операцию сложения векторов определим по следующему естественному правилу:

(а,Ь,.. „с) + (х,у,.. = (я + х,Ь + у,.. ,,с + г).

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

(ас + Ьл+ ... + с^Хх-е + >'•» + . ■ • + г-\) = ахее + ау-с\ + ...

+ агц + + ¿>х-ш + йу-Ц + ... + Ьг-Ц + ... + сх^е + су-ДО + ... + сг-Ц,

где каждое из произведений ее, е1, е], 1е, н, ...Ц,.,.]е, ...до следует заменить на значение е\', где V - вектор, принадлежащий множеству базисных векторов, задаваемое таблицей умножения базисных векторов.

С целью реализации вычислительно эффективных алгоритмов ЭЦП, непосредственно базирующихся на полях в предлагаемой форме, требуется получить циклическую подгруппу векторов большого простого порядка г/, размер которого удовлетворяет условиям |<7|>160бит и »(т - 1 )|р|. Последнее условие возможно только для простых значений т. Действительно порядок мультипликативной группы конечного расширенного поля С17(р"') равен

П=рт-\ = (р- 1 )(р""1+р'л~* +...+Р+ 1).

Легко показать, что если размерность m не является простым числом, то вторая скобка разлагается на нетривиальные множители для любого простого числа р. При условии m \р - 1 (которое имеет место в случае формирования векторных полей) сумма рт~' +рт~' +...+ р+ 1 делится иа т, поэтому простым может быть только порядок циклической подгруппы мультипликативной группы поля GFip"'), равный

q = in~<(pm~l +р'"~~1 +...+р+ 1). Эксперимент показывает, что легко найти такие значения простого р, для которых такое значение q также является простым. В этом случае имеем циклическую подгруппу векторов, размер порядка которой равен

Для построения алгоритмов ЭЦП требуется использовать подгруппы простого порядка размером |П'| > 160 бит. Для этой цели следует формировать поля m-мерных векторов, заданных над простым полем с размером характеристики |р|, удовлетворяющим условию

, . 160-1m | 160 ч

\р\>-!—U-- (бит).

ш-1 т~ 1

Таким образом, важное требование наличия в мультипликативной группе поля подгруппы простого порядка достаточно большого размера реализуется при сравнительно малом размере |р|. Практическое значение для разработки алгоритмов ЭЦП, основанных на сложности задачи дискретного логарифмирования в новых полях, имеют случаи m е {3,5,7,11,13,17,19,23}.

Рассматривается возможный вариант обобщенной схемы ЭЦП, основанной на сложности дискретного логарифмирования в конечных расширенных полях, предполагая в нем использование циклической группы векторов Г (рис. 2).

Подписывающий формирует свой открытый ключ У в виде вектора У~ G", где G - вектор, являющийся генератором группы Г, имеющей достаточно большой порядок q (|g| > 160 бит).

Формирование подписи к сообщению M выполняется следующим образом: I ) выбрать случайное число к < q и вычислить вектор R = Ск;

2) используя некоторую криптографически стойкую хэш-функцию /•}„ вычислить хэш-код h от сообщения M с присоединенным к нему вектором R: h = Fi,(M,R). Значение А будет первым элементом ЭЦП;

3) вычислить второй элемент ЭЦП: s = xh +1 mod q. Проверка подлинности подписи (A,s) состоит в следующем.

1) вычисляется вектор R' = Y4~hGs;

2) вычисляется значение h'~ F/,(M,R');

3) сравниваются значения h'и А; если h'= А, то ЭЦП признается подлинной.

Рис.2 - Обобщенная схема ЭЦП на базе циклической группы векторов.

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

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

2) Предложены механизмы формирования схем коллективной ЭЦП, используя модуль особого вида, позволяющий снизить временную сложность процедур проверки и формирования подписи.

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

4) Рассмотрены виды атак на предложенные схемы коллективной ЭЦП, и алгоритмы модификации криптографических процедур для противодействия данным атакам, а так же была формально доказана криптографическая стойкость применяемых схем ЭЦП, сводимая к стойкости базовых методов положенных в их основу.

5) Обоснована перспективность использования конечных векторных полей для построения схем ЭЦП на эллиптических кривых, для ускорения механизмов проверки и формирования подписи за счет распараллеливания ресурсоемких операций.

Список опубликованных работ по теме диссертации

1. Доронин С.Е., Молдовяну П.А., Синев В.Е. Векторные конечные поля: задание умножения векторов большой четной размерности // Вопросы защиты информации. 2008. № 4(83). С. 2-7.

2. Доронин С.Е., Молдовян H.A., Синев В.Е. Конечные расширенные поля для алгоритмов электронной цифровой подписи // Информационно-управляющие системы. 2009. № 1. С. 33-40.

3. Молдовян H.A., Морозова Е.В., Костин A.A., Доронин С.Е. Системы композиционной электронной цифровой подписи II Программные продукты и системы. 2008. № 4. С. 161-164.

4. Галанов А.И., Доронин С.Е., Костин A.A., Молдовян У.А. Протокол слепой коллективной подписи на основе сложности задачи дискретного логарифмирования // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конференции, г. Санкт-Петербург, 10-11 декабря 2009г. - СПб.: ВАС, 2009. -С. 163-168.

5. Доронин С.Е., Еремеев М.А., Молдовян A.A. реализация коллективной подписи на основе задач дискретного логарифмирования в мультипликативной группе и на эллиптической кривой И Материалы V Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР-2007)»: Труды конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: СПОИСУ, 2007. - С. 177-180.

6. Доронин С.Е„ Молдовян H.A., Молдовяну П.А.. Схемы коллективной подписи на основе задач дискретного логарифмирования // Инновационная деятельность в Вооруженных силах Российской Федерации: Труды всеармейской научно-практической конф., г. Санкт-Петербург, 22-23 ноября 2007г. - СПб.: ВАС, 2007. - С. 242-246.

7. Ананьев М.Ю., Доронин С.Е., Мирин А.Ю., Морозова Е.В. Вариант криптографической защиты бумажных документов от подделки // Материалы VI Санкт-Петербургской межрегиональной конференции «Информационная безопасность регионов России (ИБРР-2009)»., г. Санкт-Петербург, 28-30 октября 2009г. - СПб.: СПОИСУ, 2009. - С. 84-85.

8. Хо Нгок Зуй, Доронин С.Е., Молдовяну П.А., Избаш В.И. Конечные группы и поля векторов над конечными полями многочленов // XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008). Материалы конф., г. Санкт-Петербург, 22-24 октября 2008г. - СПб, 2008. - С. 59.

9. Доронин С.Е., Молдовян H.A. Избаш В.И. Примитивы алгоритмов цифровой подписи: эллиптические кривые над векторными конечными полями // XI Санкт-Петербургская международная конференция Региональная информатика-2008 (РИ-2008). Материалы конф., г. Санкт-Петербург, 22-24 октября 2008г. - СПб, 2008. - С. 99.

10. Доронин С.Е., Еремеев М.А., Молдовян A.A. реализация коллективной подписи на основе задач дискретного логарифмирования в мультипликативной группе и на эллиптической кривой // V Санкт-Петербургская межрегиональная конференция «Информационная безопасность регионов России (ИБРР-2007)». Материалы конф., г. Санкт-Петербург, 23-25 октября 2007г. - СПб.: СПОИСУ, 2007. - С. 81-82.

Подписано в печать 18 октября 2011 года. Формат 60x84 1/16.

Усл. Печ. Л. 1,0. Тираж 100 экз. Заказ К" 1750. Отпечатано в цифровом копировальном центре «СредниИ-28» 199004, Санкт-Петербург, В.О., Средний пр., 28. Тел.: (812) 323-40-44

61 12-5/352

Санкт-Петербургский государственный электротехнический

университет «ЛЭТИ»

На правах рукописи

Доронин Станислав Евгеньевич

Протоколы коллективной электронной цифровой подписи над

эллиптическими кривыми

05.13.19 - методы и системы защиты информации, информационная

безопасность

Диссертация на соискание ученой степени кандидата технических

наук

Научный руководитель доктор технических наук профессор Молдовян Н.А.

Санкт-Петербург 2011

Оглавление

Введение.......................................................................................................................4

1. Задачи и механизмы обеспечения информационной безопасности в автоматизированных информационных системах...................................................8

1.1 Обеспечение конфиденциальности и аутентичности информации..............8

1.2 Схемы электронной цифровой подписи с открытым ключом.....................11

1.3 Эллиптическая криптография.........................................................................19

1.4 Схемы мультиподписи и их приложения......................................................27

Выводы к первой главе................................... .......................................................33

2. Схемы коллективной ЭЦП над эллиптическими кривыми...............................34

2.1 Общая схема построения протоколов коллективной подписи....................34

2.2 Протоколы коллективной подписи.................................................................38

2.3 Протоколы коллективной подписи на основе стандартов ЭЦП России и Украины...................................................................................................................46

2.4 Протоколы композиционной электронной цифровой подписи...................57

Выводы ко второй главе........................................................................................67

3. Анализ безопасности протоколов коллективной ЭЦП......................................68

3.1 Подделка коллективной ЭЦП..........................................................................68

3.2 Целостность коллективной ЭЦП....................................................................73

3.3 Модифицированные схемы коллективной ЭЦП...........................................77

Выводы к третьей главе.........................................................................................88

4. Реализация протоколов эллиптической криптографии с использованием полей, заданных в явной векторной форме.............................................................90

4.1. Задание конечных расширенных полей в явной векторной форме...........90

4.2. Оценка сложности операции умножения......................................................91

4.3. Ускорение алгоритмов эллиптической криптографии................................95

4.4. Выбор параметров конечного поля для задания эллиптических кривых 102 Выводы к четвертой главе...................................................................................106

Заключение...............................................................................................................107

Литература................................................................................................................112

Приложение 1...........................................................................................................118

Программное приложение «Калькулятор ЭК»..................................................118

Описание................................................................................................................118

Техническая реализация......................................................................................119

Руководство Пользователя..................................................................................122

Приложение 2...........................................................................................................131

Копии актов внедрения результатов диссертационной работы......................131

Введение

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

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

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

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

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

Объектом исследования являются защищенные автоматизированные информационные системы и бумажные носители.

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

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

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

С целью решения поставленной задачи в ходе выполнения диссертационных исследований решались следующие частные задачи:

1) анализ и разработка механизмов противодействия специфическим атакам на коллективную ЭЦП;

2) построение схем коллективной ЭЦП с использованием эллиптических кривых;

3) разработка схем для защиты бумажных носителей от подделки;

4) разработка подходов осуществления потенциальных атак на схемы коллективной ЭЦП и оценка стойкости разработанных схем коллективной ЭЦП;

5) реализация протоколов эллиптической криптографии с использованием полей, заданных в явной векторной форме;

Новизна результатов диссертационного исследования заключается в предложенных механизмах и способах построения и модификации схем коллективной ЭЦП. Новыми результатами являются:

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

2) Механизмы снижения вычислительной сложности процедур проверки и формирования коллективной ЭЦП.

3) Протоколы, позволяющие сократить размер подписи при защите документов на бумажных носителях.

4) Сценарии потенциальных атака и оценка стойкости разработанных протоколов.

5) Способ ускорения алгоритмов и протоколов эллиптической криптографии, отличающийся заданием эллиптических кривых над конечными полями, представленными в явной векторной форме.

Основным результатом работы является созданием механизмов повышения эффективности существующих и новых схем коллективной ЭЦП для применения к бумажным и электронным документам.

6

Научные положения:

1) Способ формирования коллективной ЭЦП, отличающийся обеспечением ее внутренней целостности.

2) Протокол коллективной ЭЦП, отличающийся сокращением вычислительной сложности процедур ее проверки и формирования.

3) Протокол композиционной ЭЦП, сокращающий ее размер для использования на бумажных носителях.

4) Алгоритм построения ЭЦП, отличающийся использованием эллиптических кривых, заданных над конечными полями в явной векторной форме.

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

Глава 1.

Задачи и механизмы обеспечения информационной безопасности

в автоматизированных информационных системах

1.1 Обеспечение конфиденциальности и аутентичности информации

Стремительное развитие и рост автоматизированных информационных и телекоммуникационных систем расширяет круг существующих, а так же поднимает ряд новых проблем связанных с обеспечением конфиденциальности, целостности и аутентичности информации. Развитие средств и механизмов доступа к информации, глобализация информационных систем, открывающая многоуровневый доступ к огромным объемам информации различному кругу лиц, накладывает все более жесткие требования на такие характеристики как конфиденциальность и аутентичность информации. Социальные и демократические институты, политическая и экономическая сфера общественной деятельности предъявляют все новые требования и провоцируют эволюционные, а порой и революционные изменения в методах и механизмах информатизации общества. Все это и ряд других факторов приводят к ужесточению требований, предъявляемых к автоматизированным информационным и телекоммуникационным системам, в составе которых огромные массивы информации хранятся, передаются и обрабатываются [8-10]. Основными требованиями, предъявляемыми к подобным системам можно считать обеспечение конфиденциальности, целостности и аутентичности информации.

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

8

ограничения на круг лиц, имеющих доступ к данной информации. Механизмы подобного рода можно отнести к двум категориям: защитным и верификационным. Ключевым отличием данных категорий являются методы организации конфиденциальности информации в различных информационных средах по отношению к группам - потребителям данной информации. Защитные механизмы решают данную задачу путем искажения объекта таким образом, что субъекту требуется совершить ряд действий, направленных на раскрытие истинной составляющей объекта, содержащего искомые данные. Верификационные же механизмы в свою очередь реализуют различные системы разграничения доступа, для ограждения объекта информационного обмена от субъектов, которым данный объект не принадлежит. К защитным механизмам можно отнести алгоритмы симметричного и ассиметричного шифрования. К верификационным механизмам можно отнести алгоритмы аутентификации и идентификации [11-14].

Другой важной характеристикой информации в защищенной информационной или телекоммуникационной системе является ее аутентичность. Под аутентичностью понимают механизмы однозначного определения источника информации. Для решения этой задачи, а так же для обеспечения и контроля целостности данных используется электронная цифровая подпись (ЭЦП) [9,11,12,15]. Электронная цифровая подпись - это некая последовательность символов, полученная в результате криптографического преобразования электронных данных.

Схема ЭЦП обычно включает в себя:

• Алгоритм генерации ключевых пар пользователя

• Функцию вычисления подписи

• Функцию проверки подписи

Практически все современные алгоритмы ЭЦП относятся к классу асимметричных [16], а функции вычисления подписи являются вероятностными.

Все ЭЦП можно разделить на два больших класса:

• Обычная цифровая подпись

• Цифровая подпись с восстановлением документа

Основным отличием цифровой подписи с восстановлением документа служит то, что подпись содержит в себе тело самого документа и восстанавливает его при осуществлении проверки.

ЭЦП призвана обеспечить неизменность документа, подписанного данной подписью, а так же неотрекаемость от авторства подписи.

Целостность документа, как правило, вычисляется исходя из значения хэш-функции, получаемого от документа. Это позволяет надежно отслеживать изменения, произошедшие в исходном документе, имея при этом гораздо меньший объем данных, которые будет необходимо подписать. Как правило хэш-функции не участвуют в схемах ЭЦП, поэтому используются наиболее подходящие из доступных (примером может служить схема ЭЦП ГОСТ 34.1094, использующая хэш-функцию ГОСТ 34.11-94).

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

Надежность такого механизма держится на ряде условий:

• Секретный ключ должен быть известен только одному пользователю

• Не должно быть возможности вычислить секретный ключ, используя открытый ключ, за разумное время (вычислительно сложная задача)

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

К таким атакам можно отнести:

• Подделка подписи для документа

• Подделка документа, для существующей подписи

1.2 Схемы электронной цифровой подписи с открытым ключом

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

Задача дискретного логарифмирования является одной из основных задач, на которых базировались изначальные криптографические алгоритмы, в том числе, алгоритмы генерации ЭЦП. По своей сути - это задача обращения функции gx в некоторой конечной мультипликативной группе в.

Данная задача имеет довольно высокую вычислительную сложность, к

примеру, для алгоритма Эль-Гамаля [36], который будет рассмотрен чуть ниже,

1/2

сложность составляет (Э(ехр(с(^(р)к^к^(р)) )).

Подпись Эль-Гамаля

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

Механизм взаимодействия состоит из 3-х последовательных шагов. Генерация ключей

1) Необходимо выбрать случайный порождающий элемент g, который удовлетворяет условию g(p_1) = 1 mod р

2) Выбирается секретный элемент х, такой, что 1 < х < р.

3) Вычисляется элемент у = gx mod р

В качестве открытого ключа будут фигурировать 3 параметра: р, g, у

Вычисление подписи

1) Необходимо сгенерировать секретный элемент к, являющийся взаимнопростым с р-1 (НОД(к, р-1) = 1) и удовлетворяющий условию

О < к < р-1

2) Вычисляется R = gkmod р

3) Вычисляется S = (М- xR)/kmod (р-1)

В качестве подписи к сообщению М будет фигурировать пара чисел (R, S).

После вычисления подписи, секретный ключ х и элемент к должны быть уничтожены.

Проверка подписи

Подпись считается верной, если выполняется равенство:

12

yRRs = gM mod p. Справедливость данной схемы несложно проверить уравнением gM = yRRs = (gx)R(gk)(M"xR)/k = gxRgMgxR = gM mod p

(1.2.1) (1.2.2)

Подпись Шнорра

Данная схема [37] содержит в своей основе приведенную ранее схему Эль - Гамаля [36], однако обладает одной очень важной особенностью, секретный элемент к в ней выбирается из меньшего множества чисел (длина элемента порядка 160 бит), что повышает эффективность вычисления д�