авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

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


Pages:   || 2 |
-- [ Страница 1 ] --

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение высшего

профессионального образования

ДАЛЬНЕВОСТОЧНЫЙ ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ

ИНСТИТУТ ФИЗИКИ И ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

Кафедра информационной безопасности

Защищенная конференцсвязь.

Выработка ключа, с использованием протоколов на

идентификационных данных

Дипломная работа студента 167 группы Клочкова М. А.

Научный руководитель:

кандидат физико-математических наук, доцент ГОНЧАРОВ С.М.

Дата приема к защите:

Подпись зав. кафедрой:

Владивосток ОГЛАВЛЕНИЕ Перечень использованных терминов и сокращений...................................................... Введение............................................................................................................................. Глава 1. Эллиптические кривые.................................................................................... 1.1. Математические основы эллиптических кривых........................................ 1.1.1.Определение эллиптической кривой....................................................... 1.1.2.Законы сложения точек кривой Е и построение абелевой группы точек..................................................................................................... 1.1.3. Порядок группы точек Е и порядок точки........................................... 1.1.4. Проективные координаты...................................................................... 1.1.5. Дискриминант и j-инвариант эллиптической кривой......................... 1.1.6. Эллиптические кривые над простыми полями Галуа......................... 1.1.7. Методы экспоненцирования точки кривой.......................................... 1.2. Криптографические протоколы с использованием эллиптических кривых................................................................................................................... 1.2.1. Аналог обмена ключами по схеме Диффи-Хеллмана......................... 1.2.2. Протокол распределения ключей MQV................................................ 1.2.3. ГОСТ Р34.10-2001................................................................................... 1.2.4. ECDSA..................................................................................................... Глава 2. Криптосистемы на основе идентификационных данных............................. 2.1. Билинейные спаривания. Общие вопросы. Основные определения.......................................................................................................... 2.2. Примеры КСОИД на основе билинейных спариваний............................. 2.2.1. Шифрование. Базовая схема шифрования IBE (BasicIdent) Боне – Франклина......................................................................................................... 2.2.2. Схема выработки общего ключа. Протокол выработки общего ключа Yuan - Li............................................................................................................. 2.2.3. Схема цифровой подписи на основе идентификационных данных................................................................................................................ 2.2.4. Протокол спорной аутентификации на основе идентификационных данных................................................................................................................ 2.2.5. Схема подписи со строго определенной проверкой на основе идентификационных данных с использованием билинейных спариваний IBSDVS.............................................................................................................. 2.2.6. Трехсторонний однораундовый протокол выработки общего ключа Джоукса.............................................................................................................. 2.2.7. Расширенный протокол Джоукса, многосторонний протокол выработки ключа.............................................................................................. Глава 3 Реализация программного комплекса............................................................. 3.1. Разработка требований(технического задания)......................................... 3.2 Особенности реализации............................................................................. 3.2.1. Общая структура VoIP протокола H.323............................................ 3.2.2.Модификация протокола H.323, добавление выработки ключа................................................................................................................. Заключение...................................................................................................................... Список использованной литературы............................................................................. Приложение № 1. Требования к программному комплексу(техническое задание)............................................................................................................................. Приложение № 2. Модифицированные участки протокола H.323............................. Перечень использованных терминов и сокращений КСОИД - криптосистемы на основе идентификационных данных.

PKI (Public Key Infrastructure) - инфраструктура открытых ключей.

e (P,Q) - билинейное отображение точек P и Q.

E – эллиптическая кривая.

ЭЦП - электронная цифровая подпись.

PKG (Private Key Generator ) - центр генерации секретных ключей.

IBE (Identity-based encryption) - протоколы шифрования на основе идентификационных данных.

KGC (Key Generation Center) - центр генерации ключей.

TTP (Third trusted party) – третья доверенная сторона.

IBSDVS (Identity Based Strong Designated Verifier Signature) – схема подписи со строго определенной проверкой на основе идентификационных данных.

DV (Designated verifier) - определенный проверяющий.

Введение В большинстве современных продуктов и стандартов криптографии применяются методы с открытым ключом, основанные на проблеме факторизации больших чисел (RSA) и дискретного логарифмирования (Эль-Гамаль). Однако для их надежной защищенности число битов ключа в последние годы резко возросло, что обусловило рост нагрузки на вычислительные системы. Подход на основе эллиптических кривых E (которые являются источником конечных абелевых групп) обеспечивает эквивалентную защиту, в сравнении с ранее разработанными протоколами, при меньшем числе разрядов. Криптосистемы на основе E предложены в 1986 году В. Миллером и Н. Коблицем. Сложность атаки на ключ криптосистемы на основе E экспоненциально связана с длиной ключа. Стойкость же RSA и Эль-Гамаля субэкспоненциальная. При одинаковой стойкости криптосистема на основе E имеет размер модуля на порядок меньше. В результате успешных исследований безопасности и производительности криптосистем на основе E был утвержден ряд стандартов (например, FIPS 186-2-2000, ГОСТ Р34.10 2001).

Однако поддержка инфраструктуры открытых ключей PKI (Public Key Infrastructure) является очень сложной задачей. Сейчас надежность многих предлагаемых систем шифрования с открытым ключом во многом зависит от сертификата открытого ключа. Но использование сертификатов порождает ряд трудностей: проблема аннулирования сертификатов до окончания срока действия, передача большого количества информации, юридические сложности, большие денежные затраты. Проблему PKI могут решить криптосистемы на основе идентификационных данных (КСОИД).

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

Например, для этих целей можно использовать e-mail.

Первоначально схема шифрования на основе идентификационных данных была предложена в 1984 году Шамиром с целью упростить сертификационную систему. При использовании шифрования на основе идентификационных данных пользователям не нужно обмениваться своими открытыми ключами. Открытый ключ пользователя легко вычисляется из идентификационных данных пользователя. Только на установочном этапе требуются услуги центра генерации ключей (Private Key Generator - PKG) для того, чтобы сгенерировать системные параметры и секретный ключ пользователя. PKG, используя идентификационные данные, которые общеизвестны и представлены в стандартизованном виде, вычисляет секретный ключ и передает его пользователю. Хотя такая схема порождает некоторые сложности: PKG знает секретные ключи, что в некоторых приложениях может быть серьезной проблемой;

для получения секретного ключа пользователю необходимо аутентифицировать себя PKG;

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

С момента появления этой идеи в 1984 году до недавнего времени построение схемы шифрования на основе идентификационных данных оставалось открытой проблемой. Ситуация изменилась в 2001 году с появлением статьи Боне Франклина (Boneh, Franklin) [7]. Боне и Франклин представили схему шифрования на основе идентификационных данных, использующую свойства билинейных спариваний на эллиптических кривых, которая стала первой полностью функциональной схемой шифрования на основе идентификационных данных.

Ранее билинейные спаривания, а именно Вейль - спаривания и Тейт спаривания использовались в криптографии для MOV атак (используются Вейль – спаривания) и FR атак (используются Тейт – спаривания). Эти атаки основаны на сведении задачи дискретного логарифмирования на эллиптических кривых к задаче дискретного логарифмирования в конечном поле. Только после появления статьи Боне-Франклина билинейные спаривания стали использоваться в созидательных целях – построение новых криптографических протоколов.

Разработка КСОИД на основе билинейных спариваний является очень перспективной. С каждым годом растет количество таких протоколов, представляемых на международных конференциях. В частности действует рабочая группа IEEE P1363.3: Identity-Based Public Key Cryptography (возглавляемая William Whyte, Terence Spies), занимающаяся разработкой стандарта криптографии на основе идентификационных данных, использующего билинейные спаривания КСОИД на основе билинейных спариваний позволяют решать основные задачи криптографии: шифрование, выработка общего ключа, цифровая подпись.

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

Целью дипломной работы являлось создание программного комплекса для осуществления защищенной голосовой конференц-связи с использованием распределения ключей на КСОИД.

Были поставлены следующие задачи:

изучение применения эллиптических кривых, перспективных КСОИД в криптографии;

программная реализация протоколов;

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

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

выбор необходимых протоколов и реализация генерации ключей на них.

В первой главе диплома:

приводятся теоретические сведения по эллиптическим кривым;

описывается ряд криптографических протоколов на основе E;

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

приводятся теоретические сведения по билинейным спариваниям;

рассматриваются примеры КСОИД на основе билинейных спариваний;

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

Глава 1. Эллиптические кривые 1.1. Математические основы эллиптических кривых 1.1.1.Определение эллиптической кривой Определение. Эллиптической кривой E над полем К называется множество точек (x,y) КK, удовлетворяющих уравнению y2+a1xy+a3y=x3+a2x2+a4x+a6, ai K (1.1) вместе с точкой О – точка на бесконечности.

Вместо (1) используется и функция двух переменных F(x,y)= y2+a1xy+a3y-x3-a2x2-a4x-a6=0 (1.2) Введение операции сложения над парами точек E позволяет построить абелевую группу точек, если все точки E неособые (имеют однозначные производные). Такую кривую называют гладкой, или несингулярной.

Определение. Кривая Е называется сингулярной (особой), если существует хотя бы одна точка (х,у), в которой частные производные (1.2) одновременно обращаются в 0, т. е.

F/ х = F/ у = 0. (1.3) В противном случае кривая Е называется несингулярной (неособой). Такие кривые представляют интерес для криптографии.

Вместо общей записи уравнения (1.1) часто рассматривают уравнения трех типов кривых:

y2 = x3 + ах + b, р 2,3;

Е: (1.4) ES: у2 + у = х3 + ах + b, р = 2;

(1.5) EN: у2+ ху = х3 + ах2 + b, b 0, р = 2, (1.6) первая из них описывает все кривые над полями характеристики, не равной 2 и 3, вторая и третья - кривые над полями характеристики 2.

Для кривых вида (1.4) над полями R и Q условие несингулярности оказывается равносильным условию отсутствия кратных корней у кубического трехчлена в правой части уравнения. Выразим кубический трехчлен в уравнении (1.4) через корни i f(x)= x3 + ах + b= (x- l)(x- 2)(x- 3).

Согласно (1.3) в сингулярной точке F/ у = 2у = 0, y=0, (x- l)(x- 2)(x- 3)= 0, F/ х = (х- 2)(х - 3) + (х - 1 )(х - 3) + (x - 1)(х - 2) = 0.

Отсюда следует, что условием существования сингулярной точки является совпадение хотя бы двух корней кубического трехчлена. Несингулярная кривая (1.4), таким образом, не имеет кратных корней кубического трехчлена f(х) (т. е.

кубическое уравнение имеет три различных вещественных корня, либо один вещественный и два комплексно-сопряженных корня).

Соотношение между параметрами а и b в сингулярной точке можно получить из (1.3) и (1.4) x3 + ах + b = 0, F/ у=2у = 0, = F/ х = Зх2 + а = 0.

Отсюда 2x3=b.

Умножив (1.4) на 2 получим 2ax+3b = 0, =8a3x3=27b3, = 4a3+27b2 =0 (при b 0).

Для несингулярной кривой (1.4), следовательно, должно выполняться условие = -(4a3+27b2 ) 0. (1.7) Величину называют дискриминантом кубического трехчлена.

Характерные графики несингулярных кривых показаны на рис. 1, а, б.

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

Рис. 1, а, б.

На рис. 2, а, б приведены сингулярные кривые у2 = х2 - 3х +2 = (х + 2) (х -1 ) и у2 = х3 с сингулярными точками (1,0) и (0,0) соответственно, что исключает возможность построения абелевой группы точек.

Рис. 2, а, б.

1.1.2.Законы сложения точек кривой Е и построение абелевой группы точек Важным свойством несингулярных кривых, является то, что любая прямая, проходящая через две различные точки кривой Е, пересекает эту кривую в единственной третьей точке (см. рис. 1). Кроме того, касательная в любой точке кривой (кроме точки перегиба) пересекает ее еще в одной точке. Симметрия кривой относительно оси х позволяет дать наглядное определение обратной к точке Р = (х1, у1) точки -P=(х1,- у1). (1.8) Эти свойства позволяют дать определение групповой операции, называемой сложением точек эллиптической кривой.

Определение. Суммой двух точек Р = (х1, у1) и Q = (х2, у2) называется точка R = Р + Q = (х3, y3), обратная третьей точке пересечения E прямой линией, проходящей через точки Р и Q.

Найдем координаты точки R = Р + Q = (х3, y3), выразив их через координаты точек Р и Q. При этом точки РиQ могут быть различными (рис. 3, а) или совпадающими (рис. 3, б).

Рис. 3, а, б.

В соответствии с этим имеют место два случая.

1. Р ±Q. Уравнение прямой линии, проходящей через точки Р u Q (рис 3, а), имеет вид y2 y ;

=y1 - x1.

у = х + ;

= (1.9) x2 x Уравнение (1.2) в канонической форме (1.4) можно переписать F(x,y)= у2-х3- ах-b = 0. (1.10) Точки пересечения кривой Е и прямой (1.9) имеют по оси х координаты x1, x2, x3 точек Р, Q и -R соответственно. Поскольку они являются общими для функций (1.9) и (1.10), последнее уравнение можно записать в виде ( х + )2 - х3 ах-b = 0, или -(х-x1)(x-х2)(х-х3) =0.

Приравнивая в этих кубических уравнениях коэффициенты при переменных x2, получим 2 = x1 + x2 + x3. (1.11) Параметр прямой (1.9) можно также выразить в виде y3 y =.

x3 x Из (1.11) и последнего соотношения окончательно имеем координаты точки R=Р+Q= (х3, y3) :

x3 = 2 x1 x2, (1.12) y2 y y3 = y1 ( x3 x1 ), = x x 2 2. Р = Q, R = 2Р. В этом случае x1 = x2 и параметр в (1.12) не определен.

Дифференциал функции (1.4) 2ydy = 3x2dх + adx, тогда при х =x1 производная равна параметру касательной у = х + к кривой в точке Р 3 x12 + a dy = x = x1 =.

dx 2 y Вместо (1.12) теперь можно записать координаты точки R = 2P =(х3, y3):

x3 = 2 2 x1, P = Q;

(1.13) 3x 2 + a y3 = y1 ( x3 x1 ), = 1.

2 y Формулы сложения (1.12) и удвоения (1.13) справедливы для кривых Е над всеми полями, в том числе и конечными, кроме полей характеристик 2 и 3. В последнем случае, как видно из (1.13), редукция по модулю 2 или 3 ведет к некорректности формул удвоения и следует использовать другие канонические уравнения кривых. Заметим, что координаты сложения и удвоения точек определяются с помощью всех операций в поле, т. е. сложения (вычитания), умножения и деления.

Для построения абелевой группы точек Е определим О группы как P+(-P) = О, P E.

Если провести прямую через точки Р и - Р, то третья точка пересечения прямой и E уходит в бесконечную точку вдоль оси у. Поэтому О группы точек E называют «точкой на бесконечности».

Смысл перехода к обратной к точке пересечения прямой и кривой Е при определении суммы R = Р + Q становится понятным, если выразить, например, точку Р как Р = R - Q. В этом случае прямая проходит через точки R, - Q и -Р, а обратной к этой третьей точке является точка Р. Для точек E выполняется ассоциативность сложения Р+(Q+S) = (Р+Q)+S, и коммутативность P+Q=Q+P.

Таким образом, множество точек Е замкнуто относительно операции сложения, удовлетворяет свойствам ассоциативности, коммутативности, имеет обратный элемент и О (нуль группы), т. е. удовлетворяет всем условиям аддитивной абелевой группы.

1.1.3. Порядок группы точек Е и порядок точки Аналогией с экспоненцированием в мультипликативной группе в аддитивной группе точек является k-кратное сложение элементов (в нашем случае точек Р), которое обозначается как:

Р + Р + Р +... + Р = kР.

Точку kР называют скалярным произведением, а процесс ее вычисления экспоненцированием точки Р (возведением в степень).

Определение. Порядком NE эллиптической кривой - называется число всех ее точек (х, у) вместе с точкой на бесконечности (точкой О).

Определение. Порядком точки Р эллиптической кривой называется наименьшее натуральное число m 0, для которого mР= О.

Порядки NE и m могут быть бесконечными и конечными. В группе бесконечного порядка (например, в группе точек Е над полями R или Q ) могут быть точки конечного порядка. В частности, в группе точек Е над R всегда есть точки 2-го и 3-го порядков. Координаты хi точек 2-го порядка - это корни кубического трехчлена правой части (1.4). Для кубического трехчлена с тремя действительными корнями 1, 2, 3 (Рис. 1, а) имеем три точки второго порядка ( 1,0), ( 2,0), ( 3, 0). В этих точках ( i,0) = -( i,0) = 2 ( i,0) =O.

Вместе с точкой О эти точки образуют подгруппу 4-го порядка группы точек Е бесконечного порядка. Кубический трехчлен с одним действительным корнем (Рис.1, б) порождает подгруппу 2-го порядка точек 2-го порядка.

Точки 3-го порядка в группе точек Е над R можно найти из соотношений 2Р = -Р = ЗР=О = x3=x1. Согласно (1.13) 3 x12 + a = x1 0.

2 x1 = x 2 y Отсюда с учетом (4) Зx14+6ax12+12bx1-a2 = 0, x1 0. (1.14) В частности, при а = x1 (x1 3 + 4b) = 0 = х1 = 0.

В общем случае x-координата точки третьего порядка совпадает с x-координатой точки перегиба эллиптической кривой Е.

Рис. Точки конечного порядка кривой образуют так называемые подгруппы кручения. На кривой у2= х3 +1 на рис. 4 имеются точки 2, 3 и 6-го порядков, образующие циклические подгруппы кручения тех же порядков.

Точка Q - точка 2-го порядка, являющаяся генератором подгруппы кручения G2 = {О, Q} 2-го порядка. Точка Р - точка 3-го порядка, генерирующая подгруппу G3= {О, Р, 2Р} того же порядка. Точка R - точка 6-го порядка, образующая под группу G6 = {О, R, 2R = 2P = -P, 3R = Q, 4R = Р, 5R = -R} порядка 6. Результат 2R = 2Р следует из удвоения суммы Р + Q= R. Очевидно также, что группа G6, может быть выражена через прямую сумму циклических подгрупп 2-го и 3-го порядков G6 = G2 G3 = {0, Q} {0,P,2P}.

Таким образом, любая точка группы G6 выражается через сумму точек из подгрупп G2 и G3.

Наряду с циклическими подгруппами в группах точек Е встречаются нециклические подгруппы кручения. Например, уравнение у2 =(x- l)(x- 2)(x- 3) над полем R с тремя вещественными корнями порождает 3 точки 2-го порядка и соответствующие нециклические подгруппы кручения (нециклическая подгруппа 4-го порядка, из 3 циклических подгрупп (точек 2-го порядка) кручения;

нет генерирующей точки для этой подгруппы).

1.1.4. Проективные координаты При рассмотрении E полезным оказывается переход от аффинных координат (х,у) к проективным (X, У, Z), связывающий точки кривой Е в этих координатах отношением эквивалентности. Привлечение новой переменной Z позволяет задать координаты нуля группы Е (точки на бесконечности). В операциях над конечными полями проективные координаты позволяют избежать трудоёмких вычислений обратного элемента поля при сложении точек.

Определение Проективной плоскостью над полем K называется множество классов эквивалентности троек (X,Y,Z), в которых хотя бы один элемент ненулевой.

Эквивалентными считаются тройки, если элементы одной из них получаются из другой умножением на скаляр:(X,Y, Z ) ~ (X,Y, Z), если для некоторого элемента K : (X, Y, Z ) = (X,Y, Z). Такие классы эквивалентности называются проективными точками. Например, две точки (7, 1, 1) и (8, 3, 3) эквивалентны в проективной плоскости над F13 ( =3). Проективные точки с ненулевым элементом Z принадлежат классу эквивалентности, содержащему единственную точку, вида (x,y,1): она просто вычисляется x=X/Z,y=Y/Z.

В аффинных координатах уравнение кривой (1.4) запишем как F(x,y)=y2-x3-ax-b, a,bK.

Формально введем новые переменные подстановкой х=X/Z, у=Y/Z, z=Z/Z=1.

Тогда при Z О 2 Y X X F(x,y)= - -a -b=0.

Z Z Z Умножая это уравнение на Z3, имеем F(X,Y, Z)=Z3F(x,y)=Y2Z-X3- aXZ2- bZ3 =0. (1.18) Исключая из рассмотрения начало координат (0, 0, 0), для любой тройки (X, Y, Z) класс эквивалентности задается проективной точкой ( X, Y, Z), где скаляр, X, Y, Z - фиксированы. В трехмерном пространстве этот класс представляет собой прямую линию, проходящую через начало координат. При Z 0 любая такая прямая пересекает плоскость Z = 1, в которой, как видно из (1.18), мы возвращаемся к записи кривой в аффинных координатах. Таким образом, проективная плоскость может быть определена, как множество всех точек (x,y) обычной (аффинной) плоскости с дополнением точек, для которых Z=0.

Кроме точек с Z 0 уравнению (1.18) удовлетворяет еще одна точка.

Подставим Z=0 в уравнение, получим X 3 = 0, это означает, что X=0. Но имеется только один класс эквивалентности, где оба элемента X и Z нулевые – класс, содержащий (0,1,0). В проективной плоскости она задает координаты бесконечно удаленной точки или нулевого элемента группы точек Е. Точка О является третьей точкой пересечения точек Р и -Р на бесконечности.

1.1.5. Дискриминант и j-инвариант эллиптической кривой При изучении многих свойств и преобразований эллиптических кривых часто полезными оказываются дискриминант и j-инвариант кривой. В частности, условие 0 является необходимым и достаточным условием несингулярности кривой над любым полем.

Для кривой (1.4) дискриминант кубического уравнения x3 + ах + b = (х- е1)(х - е2)(х - е3) = определен формулой (1.7).

Найдем корни кубического трехчлена. Будем искать решение в форме x= 3 r + 3 s, при этом x3=r+s+3 3 rs ( 3 r + 3 s )=r+s+3 3 rs x.

Сравнивая это уравнение с исходным, получаем 3 3 rs = -а, r+s= -b и, следовательно, a3 a rs = ;

r+s = -b r + br = 0.

27 Решение этого квадратного уравнения дает пару значений b 1 3 ;

= -(4а +27b ).

r, s = ± (1.19) Таким образом, дискриминант кубического трехчлена совпадает с дискриминантом квадратного уравнения, определяющего значения r, s. Корни кубического уравнения теперь можно найти из a e=x= 3 r + 3 s = 3 r - (1.20).

3r В общем случае дискриминант полинома n-й степени f(x)=xn+an-1xn-1+…+a1x+a0=(х- е1)(х - е2)(х - е3)…(x-en) определяется как произведение квадратов разностей всех корней = i f k (ei-ek)2. (1.21) Для кривой (1) общего вида определим вспомогательные коэффициенты c2i, d4, дискриминант и j-инвариант равенствами:

c2 = а12 + 4а2;

c4=2a4+ a1a3;

c6=a32+4a6;

c8=a12a6+4a2a6-a1a3a4+a2a32-a42;

d4=c22-24c4;

= -c22 c8-8c43-27c62+9c2c4c6;

d, 0.

j= В частности, для кривой (4) получим 43123 a 3 123 4a =-16 • (4a3+27b2);

0.

j(E)= =3 (1.22), 4a + 27b Отсюда видно, что кривые с коэффициентом а = 0 - кривые с нулевым j-инвариантом, а кривые с коэффициентом b = 0 - кривые с j-инвариантом, равным 123= 1728.

Для кривых (1.5), (1.6) характеристики 2 соответственно имеем =1, ES: j = 0;

(1.23) j= 1/ = b-1.

= b, E N: (1.24) Изоморфные кривые и так называемые кривые кручения имеют один и тот же j-инвариант. Кривые с нулевым j-инвариантом над некоторыми полями не рекомендуются для криптографических применений.

Можно заметить, что всегда можно найти кривую с заданным j(E)=j0.

j k Пусть a=3k(mod p), b=2k(mod p), тогда j0=1728 mod p и k= modp.

k +1 1728 - j 1.1.6. Эллиптические кривые над простыми полями Галуа Рекомендуемыми в появившихся за последние годы стандартах являются два типа полей - простые поля Галуа FP, и расширенные поля F2m характеристики 2.

Рассмотрим свойства кривых Е над простыми полями FP, p 3. В ряде случаев операции над простым полем оказываются менее сложными (и более быстрыми), чем над расширенным полем. В частности, ГОСТ Российской Федерации Р34.10 2001 рекомендует именно такое поле.

Пусть кривая (1.4) с целыми коэффициентами а и b определена над полем рациональных чисел и p 3 - простое число. Тогда сравнение у2=х3 + ах + b (mod p) (1.25) называется редукцией кривой по модулю р. При этом и коэффициенты кривой, и координаты (х, у) точек являются целыми сравнимыми по модулю р числами.

Редукция называется хорошей, если р не делит дискриминант или = - (4а3 + 27b2) mod p 0. (1.26) В этом случае все корни кубического уравнения различны и кривая является несингулярной (без особых точек). Будем рассматривать только такие кривые.

Редукция (1.25) равнозначна переходу от поля Q к конечному полю, в частности, простому полю Галуа, т. е.

y2 = х3 + ах + b;

a, b FP. (1.27) Абелеву группу точек (х, у), удовлетворяющих уравнению (1.27), вместе с точкой на бесконечности О обозначим ЕP. В отличие от коэффициентов а, b кривой координаты (x, у) точек могут рассматриваться как элементы любого расширения Fpm (m = 1, 2, 3,... ) поля Fр вплоть до алгебраического замыкания F p. Законы сложения точек (1.12), (1.13) справедливы для группы Ep (р 2, 3) после введения редукции по модулю р, а операция деления равнозначна умножению на обратный элемент поля Fp. Из конечности числа элементов поля, очевидно, следует и конечность числа точек кривой, т. е. ее порядка.

Так как кривая всегда содержит точку на бесконечности О, а для каждого решения x уравнения (1.27) имеются по два значения у, для числа NE точек кривой можно получить грубую оценку 1 NE2p + 1, или |р+ 1-NE| p.

Более точную оценку порядка NE эллиптической кривой Е над конечным полем Fq получил в 1934 г. немецкий математик Г. Хассе.

Теорема (Хассе): Для эллиптической кривой E над конечным полем Fq, справедлива следующая оценка порядка кривой N E q = pm, m = 1, 2, 3,....

q+1-2 q NE q+1+2 q, (1.28) В частности, для простого поля она может быть записана как |p+1-NE| 2 p. (1.29) Пусть (z) - квадратичный характер элемента z поля Fq, определяемый как 1, z = a 2, a Fq, ( z ) = 1, z a 2, (1.30) 0, z = 0, Иными словами, если z имеет корень квадратный в поле Fq, (z) = 1, в противном случае (z) = - 1. В первом случае говорят, что z является квадратичным вычетом, во втором - квадратичным невычетом. Тогда с учетом (1.27) порядок кривой можно рассчитать перебором всех элементов поля Fq как сумму { ( x + ax + b) + 1} = q + 1 + ( x 3 + ax + b) = q + 1 t, (1.31) xFq xFq где t = ( x3 + ax + b).

xFq Первая единица в выражении (1.31) учитывает точку на бесконечности О, а под знаком суммы каждое решение х уравнения (1.27) даст по две точки Е.

Исключением являются точки второго порядка с координатой у=0, которые в соответствии с (1.30), (1.31) учитываются по одному разу. Значение t в (1.31), не превышающее по абсолютной величине 2 q, может быть положительным или отрицательным в зависимости от преобладания квадратичных вычетов или невычетов f(x) = х3 + ах + b.

1.1.7. Методы экспоненцирования точки кривой Наиболее распространенной операцией во всех криптографических алгоритмах является k-кратное сложение точки Р, обозначаемое как kР. Эту операцию обычно называют скалярным умножением, или, в терминологии мультипликативной группы, экспопенцированием точки кривой.

Дадим краткое описание методов повышения производительности при вычислении точки kР [1]. Подход к расчету точки kР может отличаться в зависимости от того, является ли точка Р фиксированной (заранее известной) или произвольной точкой. В первом случае всегда можно пользоваться предвычислениями точек, например, 2iР, которые хранятся в памяти. Двоичное представление числа k позволяет селектировать те из них, которые в результате суммирования образуют точку kР. Во втором, более общем случае, все вычисления приходится проводить в реальном времени.

Пусть порядок Ord Р = r, [log2 r] = L и число k представлено в двоичной L системе k= k i 2 i i = Алгоритм удвоения-сложения Самый простой метод, при котором вычисления осуществляются по формуле L 1 L kP= k i 2 i P = k i Pi, Pi=2iP.

i =0 i = Вычисления осуществляются с помощью следующего алгоритма.

Bxoд: k = (kL-1,kL-2,...,k0), P Е. Выход: kР.

1. R 0.

2. for i = 0 to L-1 do 2.1. if k i= 1 then R R + P.

2.2. P 2P.

3. return R.

Реализация метода требует (L - 1) операций D удвоения точки и W(k) - сложений А, где W(k) - вес Хэмминга двоичного вектора k (число единиц этого вектора). Так как в среднем число единиц случайного вектора k равно 1/2, общее число групповых операций оценивается величиной 0.5LA + LD.

Алгоритм удвоения-сложения-вычитания Предыдущий алгоритм можно усовершенствовать, если ввести дополнительную операцию - вычитания точки. Например, число k = 31 в двоичной системе имеет вес W(k) = 5, но его можно представить как 25 - 1 с весом 2.

Снижение веса Хэмминга (и, соответственно, числа групповых операций) реализуется переходом от двоичного представления числа k к троичному NAF(k) с коэффициентами ki {0,1,-1} (NAF - non-adjacent form). Одно из свойств представления NAF(k) — отсутствие в нем смежных пар ненулевых элементов, благодаря чему возрастает удельный вес нулевых элементов ki. Для расчета NAF(k) используется следующий алгоритм.

Вход: положительное целое число k. Выход: NAF(k).

1. i0.

2. while k 1 do 2.1. if k is odd then: ki 2 - (k mod 4), k k – ki;

//odd -нечетное 2.2. else ki 0;

2.3. k k/2, i i+1.

3. return (k0,k1,…,kL-1 ).

После расчета NAF(k) вычисляется точка kР методом слева-направо с помощью следующего алгоритма.

Вход: NAF(k), PE. Выход: kР.

1. R 0.

2. for i = 0 to L-1 do 2.1. if k i= 1 then R R + P.

2.2. if k i= -1 then R R - P.

2.3. P 2P.

3. return R.

NAF-представпение числа k может оказаться на один бит длиннее двоичного. В то же время для случайного k вероятность ненулевых элементов 1 и -1 снижается от 1/2 до 1/3, т. е. в среднем для L-разрядного числа их количество оценивается величиной L/3. Тогда общее среднее число групповых операций сложения А и удвоения D можно оценить как сумму (L/3)А + LD.

Метод окон с алгоритмом удвоения-сложения-вычитания Если в криптосистеме есть резервы памяти, их можно задействовать для дальнейшего увеличения скорости вычислений. Вместо точки Р можно экспоненцировать и в дальнейшем складывать смежные блоки или окна шириной w в NAF-представлении точки kР.

L k 2 i Назовем w-окном числа NAFw(k) = нечетный коэффициент ki, i i = | ki | 2w-1, содержащий хотя бы один ненулевой элемент. Заметим, что NAF2(k) = NAF(k). Например [6], при w = 4 имеем 8 различных значений ki:

-710= (-1,0, 0, 1), 110 = (0, 0, 0, 1), -510 = (0,-1, 0,-1), 310 = (0, 1, 0,-1), -310 = (0,-1, 0, 1), 510 = (0, 1, 0, 1), -110 = (0, 0, 0,-1), 710 = (1, 0, 0,-1).

Этих окон достаточно для формирования числа произвольной длины L.

Четные коэффициенты в NAF-представлении числа k избыточны, так как они образуются удвоением нечетных. На первом этапе предвычислений рассчитываются и записываются в память 8 точек: ±Р, ±3Р, ±5Р и ±7Р.

В общем случае в памяти хранится 2w-1 точек. Число NAFw(k) может быть определено с помощью модифицированного алгоритма вычисления NAF(k).

Модификация состоит в следующем: на шаге 2.1 вместо “ki 2-(k mod 4)” следует записать “ki k mod 2w”, где k mod 2w означает целое число u k mod 2w, определенное в интервале -2w-1 и 2w-1. Далее вычисляется точка kР по следующему алгоритму.

L k 2, P Е.

i Вход: w, NAFw(k) = Выход: kР.

i i = 1. Pi = iP, i = 1, 3,5.....2w-1 - 1.

2. R 0.

3. for i = 0 to L-1 do 3.1. if ki 0 then:

if ki 0 then R R + Pki else R R- Pki 3.2. Р 2P.

4. return R.

Например, w = 4, k =249, при этом NAF (k) = (1,0,0,0,0,-1,0,0,1) и NAF4(k) = (1, 0, 0, 0, 0, 0, 0, 0, 0, -710). Использование троичного NAF(k) требует, очевидно, двух сложений точек, тогда как во втором случае за счет предварительного расчета точки -7P достаточно одного сложения. Число удвоений одинаково в обоих случаях. Ясно также, что выигрыш за счет окна появляется лишь при сравнительно больших длинах L числа k.Рост ширины w окна ведет к увеличению сложности вычислений на первом шаге (и объема памяти) и снижению временной сложности на третьем шаге.

1.2. Криптографические протоколы с использованием эллиптических кривых 1.2.1. Аналог обмена ключами по схеме Диффи-Хеллмана По аналогии между экспоненцированием элементов в мультипликативной группе поля и k-кратным сложением точки эллиптической кривой можно построить протокол Диффи-Хеллмана.

Обмен ключами с использованием эллиптических кривых выполняется по следующей схеме [3]. Сначала выбирается простое число p 2 180 и параметры a и b для эллиптической кривой в уравнении y2 = x3 + ах + b (mod p). Это задает группу точек на эллиптической кривой. Затем в этой группе выбирается генерирующия точка G = (x1,y1 ). При выборе G важно, чтобы наименьшее значение n при котором nG=O, оказалось очень большим простым числом.

Параметры p,a,b и G криптосистемы являются параметрами, известными всем участникам.

Обмен ключами между пользователями А и В проводится по следующей схеме:

1. Сторона А выбирает целое число nA, меньшее n. Это число будет личным ключом участника А. Затем участник А генерирует открытый ключ PA = nA G.

Открытый ключ представляет собой некоторую точку из группы точек на эллиптической кривой.

2. Точно так же участник В выбирает личный ключ nB, и вычисляет открытый ключ РB.

3. Участник А генерирует секретный ключ K = nA РB, а участник В генерирует секретный ключ K = nB PA.

Два последних выражения дают один и тот же результат, поскольку nA РB= nA (nB G )= nB (nA G )=nB PA.

Чтобы взломать эту схему, противник должен будет вычислить k по данным G и kG, что предполагается трудной задачей.

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

Протокол Диффи-Хеллмана, однако, не защищен от противника С, который имеет доступ к каналу связи и может подменять пересылаемые точки PA и PB своими точками Pc = ncG. Он, таким образом, может либо выступать от имени одного из пользователей, установив секретную связь с другим, либо, контролируя канал, быть транслятором их переписки, свободно расшифровывая и читая все сообщения. Такого активного криптоаналитика С называют «man in the middle».

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

1.2.2. Протокол распределения ключей MQV Протокол распределения ключей на эллиптической кривой (ЕСКЕР-Elliptic Curve Key Establishment Protocol), предложенный Менезисом, Кью и Ванстоуном (A.

Menezes, M. Qu, S. Vanstone) и называемый MQV-протоколом, предполагает использование как долговременных ключей dA и dB, так и разовых ключей kA, kB пользователей [1]. Для формирования общего секретного ключа КАВ пользователи выполняют следующие действия:

1. Пользователь A:

а) генерирует случайное целое число 0 kA п;

б) вычисляет точку RA = kAG=(xA, yA);

в) вычисляет точку YA = kAQB= (x1,y1);

г) вычисляет целое число sA = (kА + dAxAx1) mod n;

д) отправляет точку RA пользователю В.

2. Пользователь В:

а) генерирует случайное целое число 0 kB п;

б) вычисляет точку RB = kBG=(xB, yB);

в) вычисляет точку YB = kBQA = (х2,,y2);

г) вычисляет целое число sB = (kB + dB xB x2) mod n;

д) отправляет точку RB пользователю А.

3. Пользователь A:

а) вычисляет точку YB = dARB =(x2,y2 );

б) вычисляет точку К = sA (RB + xB x2QB).

4. Пользователь В:

а) вычисляет точку YA = dBRA = (x1,y1 );

б) вычисляет точку К = sB (RA + xA x1QA).

В результате вычислений пользователи получают одну и ту же точку K.

Действительно, для пользователя A с учетом равенства QB = dBG и согласно соотношений 2 (б), (г) и 3 (б) имеем K = sA (RB + xB x2QB)= sA (kB + dB xB x2)G.

Аналогично вычисления пользователя B согласно 4 (б) дают K = sB (RA + xAx1QA)= sB(kA + dA xA x1)G.

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

Протокол MQV можно модифицировать без расчета параметров sA, sB согласно 1 (г) и 2 (г), а вычисляя точку К тождественными операциями с точками кривой Е. Для этого в пункте 3 пользователь A вычисляет точку V = (RB + xB x2 QB), а затем точки kAV и dAxAx1V. Сумма двух последних точек дает точку К. Так же действует и пользователь В. Этот алгоритм, более трудоемок, так как операции с точками сложней операций в поле Fq.

При выполнении этого протокола у активного криптоаналитика С («man in the middle») возникают проблемы. Если бы пользователи просто складывали свои секретные ключи, т. е. sA,B = (kA,B + dA,B) mod n, то, ситуация для С будет такой же благоприятной, как и в протоколе Диффи-Хеллмана. Идея защиты от навязывания противником С своего разового ключа kC состоит в том, что соотношение sA = (kA + dA xA x1) mod n согласно пункту 1(в) нелинейно связывает ключи kA, dA и dB, так как х1 =f (kA, dB). Тем самым противник С лишается возможности свободной подтасовки ключа kC..

Чтобы рассчитать свое значение sA, в котором ему известно лишь хА, противнику С придется определить долговременные ключи dA и dB т. е. дважды вычислить дискретный логарифм в группе E.

1.2.3. ГОСТ Р34.10- ГОСТ Р34.10-2001 принят в Российской Федерации в октябре 2001 года. Он регламентирует процедуры формирования и проверки электронной цифровой подписи (ЭЦП) на основе арифметики эллиптических кривых, определенных над простым полем Галуа (предыдущий ГОСТ Р34.10-1994, принятый в 1994 году, основан на проблеме дискретного логарифмирования в конечном поле – схема Эль Гамаля).

Общесистемные параметры в стандарте определены с ограничительными условиями:

Fp- простое поле Галуа порядка p 2255;

Е - эллиптическая кривая у2 = х3 + ах + b над полем Fp с числом точек m=nq и дискриминантом (4a3 + 27b2) 0;

эллиптическая кривая задается через величину 4a 3 J(E) J(E)=1728 3 mod p (затем рассчитывается k= mod p, a=3k(mod p), 4a + 27b 1728 - J(E) b=2k(mod p));

P - генератор криптосистемы простого порядка q, 2254 q 2256;

h(M) - хэш-функция, отображающая двоичные сообщения М произвольной длины в двоичный вектор длины 256 бит. Хэш-функция определена в ГОСТ Р34.11-1994.

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

1. MOV-атака. Порядок q криптосистемы не должен делить порядок (рk - 1) мультипликативной группы расширенного поля Галуа с расширением k = 2, 3,.... В, В 31.

Тест на аномальность кривой. Должно выполняться условие m p. В 2.

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

3. Тест на инвариант (и суперсингулярность), j-инвариант кривой J(E) 0 mod 1728. Это, в частности, требует выполнения условий a 0и b 0 для уравнения кривой.

Параметры пользователя Пользователь А:

• генерирует и хранит в секрете долговременный секретный ключ как целое число 0 dA q;

• вычисляет открытый ключ как точку кривой QA = dAP. Открытый ключ доступен для всех пользователей системы.

Формирование ЭЦП Пользователь А:

1. Вычисляет хэш значение сообщения М: е=h(M) mod q. Если е = 0, то принять е = 1.

2. Генерирует случайное целое число 0 kА q.

3. Вычисляет точку C = kAP = (xc,yc).

4. Вычисляет параметр r = xc mod q. При r=0 возврат в пункт 2.

5. Вычисляет параметр s = (kА е + dA r) mod q. При s = 0 возврат в пункт 2.

6. Определяет цифровую подпись =(r || s) - в виде конкатенации двух двоичных векторов r и s.

Проверка ЭЦП Пользователь В проверяет цифровую подпись пользователя А с помощью его открытого ключа QA, общесистемных параметров, алгоритма хэширования h(M) и подписанного сообщения (М, ). Проверка заключается в вычислении на основе известных данных параметра r' и сравнении его с принятым значением r.

Умножив равенство в пункте 5 на инверсию е-1, и учитывая, что QA = dAP, для точек криптосистемы получим равенство kAP = е-1sP - е-1rdAP = uP+ vQA ;

и = е-1s mod q;

v = - е-1r mod q.

Протокол проверки ЭЦП включает следующие вычисления.

Пользователь В:

1. По полученной подписи вычисляет целые числа r и s. Если 0 r q, 0 s q, то перейти к следующему шагу. В противном случае подпись неверна.

2. Вычисляет хэш значение полученного сообщения h = h(M) как целое число.

3. Вычисляет е = h mod q. Если е = 0, то принять е = 1.

4. Вычисляет обратный элемент е-1 mod q мультипликативной группы поля Fq.

5. Вычисляет параметры и = е-1s mod q, v = - е-1r mod q.

6. Вычисляет точку C’= uP + vQA = = (xc’, yc’).

7. Вычисляет параметр r’ =хc’ mod q.

8. Сравнивает вычисленное r’ и принятое r значения. При равенстве r=r’ цифровая подпись принимается, в противном случае она неверна.

При проверке требуется вычисление одной инверсии е-1 в поле.

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

1.2.4. ECDSA Алгоритм ECDSA был впервые предложен С. Ванстоуном в 1992 году, после чего он прошел длительный этап исследований на стойкость и различного рода усовершенствований и доработок. Лишь в конце XX века он был утвержден в ряде стандартов цифровой подписи: международном стандарте ISO/IEC CD 15946-2 в 1999 году, американском стандарте для финансовых служб X9.62 ANSI (American National Standard Institute) в 1999 года, американском национальном стандарте FIPS 186-2 [5] NIST в 2000 года, P1363 IEEE (Institute of Electrical and Electronics Engineers) в 2000 году и других. Национальный стандарт DSS правительства США принятый NIST в 2000 году сменил предыдущий стандарт FIPS 186-1, действующий с 1994 года, и рекомендует ECDSA взамен DSA, построенного на арифметике простого поля Галуа. Вообще по новому стандарту ЭЦП может вырабатываться по одному из трех алгоритмов: DSA – на основе проблемы дискретного логарифмирования в конечном поле, RSA DSA – вариант схемы RSA и ECDSA. Сам алгоритм ECDSA в стандарте не приведен со ссылкой на описание алгоритма в стандарте X9.62 ANSI.

Описание ECDSA [1].

Параметры пользователя Пользователь А:

- генерирует и хранит в секрете долговременный секретный ключ как целое число 0 dA п;

- вычисляет открытый ключ как точку кривой QA = dAG. Открытый ключ доступен для всех пользователей системы.

Формирование ЭЦП Пользователь A:

1. Вычисляет хэш значение сообщения М как целое число е = h(M), e п.

2. Генерирует случайное целое число 0 kА п.

3. Вычисляет точку R = kAG = (x1, у1).

4. Вычисляет параметр r = (R) mod п. При r = 0 возврат в пункт 2.

5. Вычисляет обратный элемент kА - 1 простого поля Fn.

6. Вычисляет параметр s = kА - 1 (e + dAr) mod п. При s=0 возврат в пункт 2.

7. Направляет пользователю В подписанное сообщение (М, r, s), в котором DS = (r, s) - цифровая подпись.

В пункте 4 преобразование точки R в целое число предполагает, что ее х-координата как элемент x1 поля Fn переводится в целое число x1 с последующей редукцией по модулю n ( r = (R) mod n = x1 mod n).

Проверка ЭЦП Пользователь B проверяет ЭЦП пользователя А, имея в распоряжении следующую информацию: открытый ключ пользователя A QA, общесистемные параметры, алгоритм хэширования h(M) и подписанное сообщение (M, r, s). Суть проверки состоит в вычислении на основе известных данных параметра r' и сравнении его с принятым значением r.

Умножив равенство в пункте 6 на инверсию s -1 второго параметра подписи и учитывая, что QA = dAG для точек криптосистемы в результате экспоненцирования (скалярного произведения) получим равенство kAG = s -1 eG + s-1r dA G = uG + vQA;

и = s -1e mod n, v= s-1r mod n.

Согласно пунктам 3 и 4 протокола формирования левая часть этого ра венства определяет точку R = (x1, у1) и, соответственно, параметр r = x1 mod п.

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

Протокол проверки ЭЦП включает следующие вычисления.

Пользователь В:

1. Вычисляет хэш значение полученного сообщения М: е = h(M), e п.

2. Вычисляет обратный элемент s -1 mod n поля Fn.

3. Вычисляет параметры u = s -1 e mod n, v= s -1 r mod n.

4. Вычисляет точку R'= uG + vQA = (x1, у1).

5. Вычисляет параметр r' = (R') = x1 ' mod п.

6. Сравнивает вычисленное r ' и принятое значения r. При равенстве r' = r цифровая подпись верна, в противном случае она отвергается.

В результате проверки пользователь В удостоверяется в подлинности отправителя А и целостности сообщения М.

В ряде проектов и стандартов определение параметра r подписи не регламентируется, а задается функцией r= ( x1, y1) mod п. Это, в частности, позволяет избежать неоднозначности определения r = x1 mod n в связи с наличием обратной точки (n - kA)G = - kAG, имеющей ту же х-координату, что и точка kAG (и, следовательно, совпадающий параметр r).

FIPS 186-2-2000 рекомендует к использованию 10 полей и 15 эллиптических кривых, 5 из которых определены над простыми полями Fp и 10 - над расширенными полями F2т. Значения модулей простых полей:

P192=2192 - 264 -1, P224=2224 - 296 +1, P256=2256 - 2244 +2192 + 296 -1, P384=2384 - 2128 +296 + 232 -1, P521=2521 -1.

Расширения двоичного поля равны т = 163, 233,283,409 и 571.

Из кривых над простыми полями Fp NIST рекомендует кривую у2 =x3 - 3х + b mod p.

|Значения коэффициента b для пяти рекомендуемых кривых, координаты одного из возможных генераторов - точки G = (Gx, G y) порядка n приведены в стандарте.

Из 10 кривых над расширенными полями F2т 5 несуперсингулярных кривых у2 +ху=х3 +ах2 + b с коэффициентами а = 1 и b F2m, b 0, 1.

Еще 5 несуперсингулярных кривых вида у2 +ху=х3 +ах2 + 1 над полем F2m с коэффициентами а =1 или 0. Эти кривые называют кривыми Коблица, в стандарте они обозначены как К-т. В стандарте FIPS 186-2-2000, кроме порядков кривых, даны возможные значения координат точек G порядка п.

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

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

В целом [1], при одинаковых алгоритмах и программной реализации арифметика эллиптических кривых над простым полем Fp выполняется в 2 - 3 раза быстрее, чем в поле F2m.

Глава 2. Криптосистемы на основе идентификационных данных 2.1. Билинейные спаривания. Общие вопросы. Основные определения.

G1, G2 – группы простого порядка q. G1 – аддитивная группа, G2 – мультипликативная группа. P G1 ( aP – означает P a-кратное сложение точки Р).

Предполагается, что задача дискретного логарифмирования сложна и в G1, и в G2.

e : G12 G Отображение называется билинейным, если оно удовлетворяет следующим свойствам:

1. Билинейность: e(aP, bQ) = e(P,Q)ab, для любых P,Q G1 и любых a,b Zq.

Или иначе: для P,Q, R G1, e(P+Q,R)=e(P, R) e(Q,R) и e(P,Q+R)= e(P,Q) e(P, R).

2. Невырожденность: Существует точка P G1, такая что e(P, P) 1.

3. Вычислимость: Существует полиномиальный алгоритм вычисления e(P,Q) для любых P, Q G1.

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

Большинство протоколов основано на ряде проблем.

Проблема дискретного логарифмирования (DLP - Discrete Logarithm Problem): Даны два элемента R, S G1, нужно найти целое a Zq *, такое, что S=aR.

Вычислительная проблема Диффи-Хеллмана (CDHP-Computational Diffie Hellman): Для a, b Zq * даны P, aP, bP, нужно вычислить abP.

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

Проблема решения Диффи-Хеллмана (DDHP-Decision Diffie-Hellman problem): Для a, b, c Zq * даны P, aP, bP, cP, нужно решить c ab mod q, т.е.

проблема заключается в различении двух наборов P, aP, bP, abP и P, aP, bP, cP.

Если существует спаривание на (G1, G2 ), то DDHP – проста в (G1,+ ).

Теорема.

Доказательство: ab c e(aP, bP) = e( P, cP).

Билинейная проблема Диффи-Хеллмана (BDHP – Bilinear Diffie-Hellman P, aP, bP, cP problem) заключается в следующем: дан набор для некоторых случайных a, b, c Zq * нужно вычислить W = e( P, P) G abc Чтобы BDHP была сложной, (G1,+ ) и (G2,) должны быть выбраны так, чтобы не было известного алгоритма для эффективного решения задачи Диффи Хеллмана ни в (G1,+ ), ни в (G2,).

Промежуточная проблема Диффи-Хэллмана (GDHP - Gap Diffie-Hellman Problem): Класс проблем, в котором DDHP может быть решена за полиномиальное время, но нет вероятностного алгоритма, решающего за полиномиальное время CDHP.

Билинейный генератор параметров Диффи-Хеллмана (BDH):

Случайный алгоритм IG – это генератор параметров BDHP, если IG принимает параметр безопасности k0, выполняется за время полиномиальное от k, и возвращает описание двух групп G1 и G2 одного простого порядка q и описание возможного спаривания e : G1 G1 G2.

Теорема. Пусть существует билинейное спаривание на (G1, G2 ), тогда если CDHP проста в (G1,+ ) или (G2,), тогда BDHP также проста.

Доказательство: Если CDHP проста в (G1,+ ), можно вычислить abP с помощью e( P, P) ab = e(abP, P).

aP и bP, тогда Если CDHP проста в (G2,), тогда можно вычислить элементы g = e( P, P), gab = e(aP, bP) и gс = e( P, cP), затем еще раз решить CDHP в (G2,) и получить gabс.

Обобщенная билинейная проблема Диффи-Хеллмана (GBDHP-General Bilinear Diffie-Hellman problem): Для данного случайно выбранного P G, а также aP и bP (для случайно выбранных a, b, c Z / qZ ) получить пару Q, (Q, P) abc Гипотеза BDHP: Если IG – генератор параметров BDHP, преимущество AdvIG (B), которое алгоритм B имеет в решении задачи BDHP, определяется e( P, P) abc, вероятностью, что алгоритм B вернет если на входе будут G1, G2, e, P, aP, bP, cP, где (G1, G 2, e) – результат IG для достаточно большого параметра безопасности k, P – случайный генератор G1, а a, b, c – случайные элементы из Z/qZ. Гипотеза BDHP заключается в том, что AdvIG (B) незначительно для всех эффективных алгоритмов B.

Промежуточная группа Диффи-Хелмана (Gap Diffie-Hellman (GDH) group). Группа G1 простого порядка называется GDH группой, если существует эффективный полиномиальный алгоритм, который решает проблему DDHP в G1, и не существует вероятностного алгоритма, который решает проблему CDHP с не незначительной вероятностью успеха. В области билинейных спариваний существуют GDH группы. MOV-сведение обеспечивает метод решения DDHP в G1, тогда как неизвестно эффективного алгоритма для CDHP в G1.

Билинейная проблема решения Диффи-Хеллмана (Decisional Bilinear abc Diffie-Hellman (DBDH) problem). Заключается в проверке равенства r = e( P, P), если дан P, aP, bP, cP, r, где a, b, c Zq *, rG2 выбираются случайно.

Билинейная хэш проблема решения Диффи-Хеллмана (Decisional Hash Bilinear Diffie-Hellman (DHBDH) problem). Заключается в проверке равенства r = H (e( P, P ) abc ), если дан P, aP, bP, cP, r, где a, b, c Zq *, rG2, хэш-функция H: G2 Zq *.

2.2. Примеры КСОИД на основе билинейных спариваний 2.2.1. Шифрование. Базовая схема шифрования IBE (BasicIdent) Боне Франклина.

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

Когда пользователь A хочет отправить письмо пользователю B, то просто шифрует письмо, используя открытый ключ B, который получает из идентификационной информации B. B, после получения зашифрованного письма, получает свой секретный ключ от третьей стороны Центра Генерации Секретных Ключей (PKG - Private Key Generator) после аутентификации у PKG. После этого он может расшифровать письмо. Секретный ключ, который PKG генерирует по запросу B, является функцией мастер-ключа и идентификационных данных.

Первый IBE протокол был предложен Боне и Франклином [4] в 2001году, этот протокол использует билинейные спаривания. Преимущества IBE протоколов очевидны: такие протоколы делают ненужным инфраструктуру открытых ключей.

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

Однако IBE системы обладают рядом недостатков:

1. PKG знает секретный ключ B, что в некоторых приложениях может быть серьезной проблемой.

2. Пользователю B необходимо аутентифицировать себя PKG (как и в системах с Центрами сертификации) 3. Для передачи секретного ключа от PKG пользователю B необходим защищенный канал.

4. B публикует свои PKG открытые параметры и пользователю A необходимо получить эти параметры, перед тем как отправлять B шифрованное письмо.

Базовая схема шифрования IBE (BasicIdent) Боне - Франклина.

Описание протокола (состоит из 4-х алгоритмов Setup, Extract, Encrypt, Decrypt):

- Setup: Генератор IG случайных параметров BDH выбирает случайное и устанавливает Ppub= sP, где генератор P G1. Выбирает s Zq * криптографические хэш-функции H1: {0, 1}* G1 и Н2: G2 {0,1}, n - битовая * n длина сообщения. Master-ключ – s, глобальный открытый ключ - Ppub.

- Extract: По данному открытому идентификатору ID {0,1}* алгоритм вычисляет открытый ключ QID= H1(ID) G1* и секретный ключ dID= sQID.

Вычисление QID=H1(ID) отображает случайную строку в точку группы G1.

- Encrypt: Алгоритм выбирает случайное r Z q, вычисляет шифрованный * текст С открытого сообщения М:

C = rP, M H 2 ( g ID ), r где gID = e(QID, Ppub) -Decrypt: Дано С = U,V, вычисляет V H 2 (e(dID,U)) Предположение: проблема BDHP сложна.

Безопасность: Защищенность против атаки с использованием подободранных шифртекстов в модели со случайным оракулом была доказана Fujisaki-Okamoto.

Эффективность:

- Setup: 1 скалярное умножение в G1.

- Extract: 1 отображение в точку кривой;

1 скалярное умножение в G1.

- Encrypt: 1 отображение в точку кривой;

1 скалярное умножение в G1;

вычисление хэш-функции (H2);

1 операция XOR;

1 вычисление спаривания;

возведение в степень в G2.

-Decrypt: Вычисление хэш-функции (H2);

1 операция XOR;

1 вычисление спаривания.

2.2.2. Схема выработки общего ключа. Протокол выработки общего ключа Yuan - Li.

Схема выработки общего ключа, которая позволяет двум участникам установить общий секретный ключ посредством обмена по незащищенному каналу, была впервые предложена Диффи и Хэлманом. Однако этот протокол незащищен от атаки человек в середине. Для защиты от этой атаки позже было предложено большое число аутентифицированных протоколов. Но большинство из них использует инфраструктуру открытых ключей (PKI), поддержание которой является весьма трудоемкой задачей. Чтобы упростить эту систему Шамир предложил новую идею – системы на базе идентификационных данных. Первый протокол на базе идентификационных данных аутентифицированной выработки общего ключа на основе спариваний был предложен Смартом. Его протокол базировался на идеи Боне - Франклина и идеи трехстороннего протокола Joux.

Однако в дальнейшем была показана его уязвимость. В дальнейшем было предложено большое число подобных протоколов, но большинство из них обладает тем или иными слабостями. Рассмотрим протокол Yuan - Li 2005 года [10], в котором на данный момент не было найдено каких-либо уязвимостей.

Протокол выработки общего ключа Yuan - Li.

Описание протокола:

KGC (Key Generation Center) - Центр Генерации Ключей.

- Setup: KGС выбирает G1, G2, e: G1 G1 G2, P, H1:{0, 1}* G1, s Z p и H * – функция для получения ключа. KGС вычисляет Ppub = sP, публикует G1, G2, e, P, Ppub, H1, H и сохраняет s в качестве мастер ключа.

- Extract: Для пользователя с идентификатором ID открытый ключ вычисляется так: QID = H1 (ID). KGС генерирует связанный секретный ключ:

S ID = sQID.

1. А случайно выбирает a Z p, вычисляет TA = aP * A B: TA 2. B случайно выбирает b Z p, вычисляет TB = bP * B A: TB 3. A вычисляет h = aTB = abP и общий секретный ключ K AB = e( aPpub + S A, TB + QB ) 4. B вычисляет h = bTA = abP и общий секретный ключ K BA = e(TA + QA, bPpub + S B,) Сеансовый ключ H(A, B, h, KAB).

Корректность: KBA = KAB = e (P, P)abs e(P, QB)as e(QA, P)bs e(QA, QB)s.

Предположение: проблема CDHP трудна.

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

2.2.3. Схема цифровой подписи на основе идентификационных данных Схема цифровой подписи на основе идентификационных данных требует участия третьей доверенной стороны (TTP -Third trusted party) и состоит из четырех алгоритмов:

Setup: TTP вычисляет открытые системные параметры и главный секретный ключ – мастер-ключ.

Extract: По идентификационным данным TTP вычисляет секретный ключ пользователя с помощью мастер-ключа.

Signing: Используя системные параметры и свой секретный ключ, пользователь создает свою подпись Verify: Проверяющий вычисляет открытый ключ для конкретных идентификационных данных, используя системные параметры, и проверяет подпись.

Полная схема подписи [8]:

Setup: TTP выбирает G1, G2, P. Мастер-ключ – случайное s Z q *.

Системными параметрами являются G1, G2, P, Ppub = sP, e, H 1, H 2, H 3, где Hi – криптографические хэш-функции H 1 : {0,1} G1, H 2 : {0,1} Z q *, H 3 : G1 Z q *.

* * Extract: Секретный ключ пользователя D ID = sH 1 ( ID) Sign: Чтобы подписать сообщение M {0,1}, пользователь сначала выбирает * случайное k Z q и вычисляет подпись сообщения М как пару U, V = * S = H 2 ( M ) P + H 3 (kP) DID.

kP, k 1 S G1 G1, где Verify: Чтобы проверить подпись U, V сообщения М получатель должен Q ID = H 1 ( ID). Затем он сначала вычислить открытый ключ для данного ID:

e( Ppub, QID ) H 3 (U ).

H 2 (M ) вычисляет e(U,V ) и сравнивает результат со значением e( P, P) Если U, V - корректная подпись, то она всегда будет успешно проходить проверку, что следует из теории билинейных спариваний:

e(U,V ) = e(kP,k-1(H2(M)P+H3(U)DID)) = e(P,H2(M)P+H3(U)DID) e( Ppub, QID ) H 3 (U ).

H 2 (M ) = e( P, P ) Утверждается, что данная схема в модели случайного оракула является надежной против атак на основе выбранного шифртекста.

2.2.4. Протокол спорной аутентификации на основе идентификационных данных (2006 год) Протокол спорной аутентификации обладает следующим свойством:

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

В 1998 году Dwork и ряд соавторов, а также Aumann и Rabin предложили концепцию протокола спорной аутентификации, основанном на доказательстве с нулевым разглашением, но такое доказательство делало аутентификацию затратной по части времени, а также имело еще некоторые недостатки. В 2001 году Deng и ряд соавторов предложили два протокола (основываясь на протоколе Aumann и Rabin): один на основе проблемы факторизации, другой на основе дискретного логарифмирования. В 2006 году Zhu и соавторы показали, что протокол Aumann и Rabin подвержен атаке “человек посередине”. В 2002 году Fan и соавторы предложили протокол спорной аутентификации на основе алгоритма Диффи-Хэллмана. Однако в 2005 году Yoon и соавторы показали, что этот протокол подвержен атаке маскарадом и предложили свой протокол. После анализа Jue-Sam Chou, Yalin Chen, Jin-Cheng Huang нашли в протоколе Yoon и соавторов уязвимость. Наконец, в 2005 году Cao и соавторы предложили протокол спорной аутентификации на основе идентификационных данных. Но Jue-Sam Chou, Yalin Chen, Jin-Cheng Huang показали его подверженность KCI атаке и предложили свой протокол [7].

Описание протокола (Jue-Sam Chou, Yalin Chen, Jin-Cheng Huang).

Два пользователя A и B, каждый имеет свою пару открытый/секретный ключ SA / QA и SB / QB.

Setup: PKG выбирает мастер-ключ s Zq* и задает Ppub=sP, H1:{0,1} G1* Extract: Для пользователя с идентификатором ID={0,1}* PKG вычисляет открытый ключ QID=H1(ID) и его секретный ключ SID=sQID.

Шаг 1. А выбирает большое случайное число r1 Zq *, вычисляет u = r1QA, затем передает IDA, u пользователю B.

Шаг 2. После получения IDA, u B выбирает большое случайное число r Zq h B =H(e(u,SB)). Затем он также вычисляет U = h B r, * и вычисляет X =H( x ) и Y =H( y ), где x =e(rSB, P) и y =e(rQA, Ppub). Затем передает IDB,U пользователю A.

Шаг 3. После получения IDB,U A вычисляет hB =H(e(r1SA,QB )) и U hB, чтобы получить r. Затем A вычисляет X=H(x) и Y=H(y), где x= e(rQB,Ppub) и XY y=(rSA, P), вычисляет сеансовый ключ K =e(SA,QB ). После этого A вычисляет h= H(IDB, m, x, y, K) и передает h, m пользователю B, где m –это сообщение которое A хочет отправить B со спорным свойством.

Шаг 4. После получения h,m B вычисляет сеансовый ключ K'=e( QA,SB)X 'Y ' и h =H(IDB, m, x, y, K') и сравнивает h с h. Если h = h B принимает его.

Иначе он считает его непригодным.

Анализ безопасности Лемма 1. Предложенный протокол является протоколом спорной аутентификации.

Доказательство. Т.к. A и B разделяют общий сеансовый ключ K, B не может доказать другим сторонам, что получил h,m в действительности от A. Если B заявит, что A отсылал ему h,m, то A может оспорить это заявление, поскольку B может вычислить значение h.

Лемма 2. Предложенный протокол может аутентифицировать источник сообщения m (корректность).

Доказательство. Получив h,m, B может аутентифицировать источник сообщения m проверкой h = h: h = H(IDB,m, x, y,K), h =H(IDB,m, x, y, K'), где K'=e (SA, QB ) X 'Y '= K=e( QA,SB) XY сеансовый ключ, x=e(rSB, P) = x = e(rQB, Ppub) и y=e(rQA, Ppub)= y =(rSA,P). Поэтому B может аутентифицировать источник сообщения m, сравнив h и h.

Лемма 3. Предложенный протокол устойчив к KCI-атаке (атаке маскарадом).

Доказательство. Если атакующий C знает секретный ключ SA пользователя A, он не может выступить в роли B и взаимодействовать с A, потому что C не может вычислить h B без SB, т.к. h B =H(e(u,SB )). Если С знает секретный ключ SA пользователя A, он не может вычислить hB =H(e(r1SA,QB ))(которое должно быть равно h B ), т.к. не знает r1. Следовательно, KCI – атака потерпит крах.

2.2.5. Схема подписи со строго определенной проверкой на основе идентификационных данных с использованием билинейных спариваний IBSDVS (2006 год) Подпись с определенной проверкой (Designated verifier signature - DVS). DVS впервые представил Jakobsson и соавторы на Eurocrypt’96, как специальный тип ЭЦП, который обеспечивает аутентификацию сообщения с возможностью отказа от авторства. Такие подписи могут применяться при электронном голосовании, нужны для платежных средств и лицензирования программного обеспечения.

Допустим, пользователь A оправил DVS пользователю B. В отличие от обычной ЭЦП, B не может доказать третьей стороне, что A создала ЭЦП. Это достигается благодаря возможности пользователя B создавать ЭЦП, которая неотличима от ЭЦП пользователя A. Таким образом, третьей стороне нет причин верить в то, что ЭЦП была создана пользователем A. Таким образом, DVS дает подписывающей стороне возможность внести неопределенность относительности авторства подписи. Однако третья сторона может поверить в то, что подпись сделал A, если B может доказать третьей стороне, что он еще не получал ЭЦП. Тогда третья сторона с большой вероятностью согласится с тем, что A создал ЭЦП. Strong Designated Verifier Signature (SDVS) - подпись со строго определенной проверкой, решает эту проблему, заставляя определенного проверяющего (Designated verifier - DV) использовать его секретный ключ во время проверки. Таким образом, ни кто другой за исключением DV не может проверить SDVS. Lipmaa и соавторы показали атаку “возможность делегирования” на DVS и SDVS схемы. А может делегировать третьей стороне С возможность подписывать, это касается и определенного проверяющего, без раскрытия секретов. Однако C затем может присвоить авторство материала, созданного пользователем A. Хотя это не очень существенная атака, но она все же нежелательно во многих приложениях.

Identity Based Strong Designated Verifier Signature (IBSDVS) – схема подписи со строго определенной проверкой на основе идентификационных данных с использованием билинейных спариваний. IBSDVS применима для электронного голосования, аукционов и в электронной коммерции, где определенный проверяющий только может проверить и убедиться для себя в подлинности подписи. Рассмотрим схему IBSDVS предложенную K. Phani Kumar, G. Shailaja, Ashutosh Saxena [9]. Безопасность схемы основана на проблеме BDHP. Проблема делегирования в этой схеме решена.

Модель IBSDVS Key Generation Center (KGC) – центр генерации ключей, подписывающее лицо – S (signer), определенный проверяющий DV. Модель IBSDVS должна удовлетворять следующим свойствам:

1. Корректность: Правильно сформированная подпись IBSDVS должна проходить алгоритм проверки.

2. Невозможность подделки: Вычислительно невозможно построить верную подпись IBSDVS без знания секретного ключа подписывающей стороны или определенного проверяющего.

3. Сокрытие источника: Для данного сообщения M и подписи IBSDVS невозможно установить, кто сделал подпись - подписывающая сторона или определенный проверяющий, даже зная их секретные ключи.

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

Этапы схемы:

IBSDVS схема состоит из 5 этапов - алгоритмов Setup, KeyGen, DeSign, DeVerify, Simulation.

Setup: Задается параметр безопасности k, алгоритм генерирует открытые параметры.

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

DeSign: На основе сообщения m, секретного ключа подписывающей стороны и открытому ключу DV, алгоритм вычисляет определенную подпись сообщения m.

DeVerify: На основе пары сообщение-подпись (m, ) и секретного ключа DV алгоритм проверяет правильна ли подпись.

Simulation: На основе секретного ключа DV и открытого ключа подписывающей стороны алгоритм воспроизводит подпись, определяемую для DV и удовлетворяющую алгоритму проверки.

Два первых этапа происходят в KGC.

Пусть G1 это GDH группа порядка большого простого числа q и G2 это мультипликативная группа того же порядка.

1. Setup: KGC выбирает генератор P G1, случайное число s Zq* и вычисляет PPub = sP. KGC также выбирает две криптографические хэш функции H : {0, 1}* G1 и H2 : {0, 1}* G2 G1 и билинейное отображение e : G1 G1 G2.

Системные параметры G1, G2, P, Ppub, H1, H2, e открыты, мастер-ключом является s и держится в секрете.

2. KeyGen: На основе идентификатора пользователя ID вырабатывается SID=sH1(ID) и отсылается пользователю с идентификатором ID. QID = H1(ID) является открытым ключом пользователя с идентификатором ID.

3. DeSign: Задаются секретный ключ SA подписывающей стороны A, открытые ключи QA подписывающей стороны A и QB определенного проверяющего B, сообщение M. Вычисление подписи :

Выбирая случайные числа r1, r2, r3 Zq* вычисляется U1 = r1QB U2 = r2QA U3 = r1r3QB V = r3H + r1 1SA где H = H2(M, e(r2QB, SA)).

Подписывающая сторона отсылает M, определенному проверяющему, где =U1, U2, U3, V.

4. DeVerify: Получив M,, определенный проверяющий вычисляет H=H2(M, e(U2, SB)) и считает подпись верной, если верно выражение:

e(U1,V)=e(U3,H)e(SB,QA).

5. Simulation: Определенный проверяющий B не может доказать третьей стороне, что подпись была сделана стороной A, т.к. B может создать неотличимую подпись для того же сообщения M. B может создать подпись следующим образом:

B выбирает случайные числа r1, r2, r3 Zq*, вычисляет U1 = r1 QA U 2 = r2 QB U 3 = r1 r3 QA H = H2(M, e( r2 QA, SB)) V = r3 H + r1 SB.

Ясно, что = U1, U 2, U 3, V пройдет проверку.

Анализ безопасности Корректность Следующее доказывает корректность проверки:

e(U1, V ) = e(r1QB, r3H + r1 1SA) = e(r1QB, r3H)e(r1QB, r1 1 SA) = e(r3r1QB, H)e(QB, sQA);

= e(U3, H)e(sQB, QA) = e(U3,H)e(SB,QA) Строгость определенной проверки Определенный проверяющий использует секретный ключ SB во время проверки при вычислении хэш H. Поэтому, никто за исключением определенного проверяющего не может выполнить проверку. Поэтому приведенная схема со строго определенной проверкой.

Невозможность подделки Невозможно вычислить H и V без знания секретного ключа подписывающей стороны SA или секретного ключа проверяющего SB. Поэтому подпись невозможно подделать.

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

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

Невозможность делегирования Для вычисления V необходим секретный ключ подписывающей стороны SA.

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

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

2.2.6. Трехсторонний однораундовый протокол выработки общего ключа Джоукса.

Рассмотрим 3-х сторонний неаутентифицированный протокол Джоукса [20] (2000) выработки общего ключа.

Пусть три стороны A, B, C имеют секретные ключи a, b, c Z q соответственно.

* Абоненты отправляют друг другу посылки:

A B, C : aP B A, C : bP C A, B : cP A вычисляет K A = e(bP, cP).

a B вычисляет K b = e(aP, cP).

b C вычисляет K c = e(aP, bP)c.

Общий ключ для A, B, C K ABC = K A = K B = K C = e( P, P).

abc Протокол использует предположение о трудности проблемы BDH и защищен от пассивного противника.

Эффективность:

Связь. Требуется 1 раунд связи, по сети отправляются 3 элемента группы G1.

Вычисления. 3 скалярных умножения в G1, 3 вычисления спариваний, 3 возведения в степень в G2.

2.2.7. Расширенный протокол Джоукса, многосторонний протокол выработки общего ключа.

Рассмотрим неаутентифицированный многосторонний протокол выработки общего ключа, использующий билинейные спаривания. По сути, этот протокол является комбинацией 2-х стороннего и 3-х стороннего протоколов выработки общего ключа и наследует все их полезные свойства. Таким образом, безопасность многостороннего протокола базируется на безопасности 2-х и 3-х стороннего протоколов. В данной схеме используется трехсторонний неаутентифицированный протокол Джоукса, но он может быть заменен на любой другой. В 2003 г. Баруа, Дутта и Саркар предложили другую версию протокола с аутентификацией [30].

Рассмотрим этот протокол.

Пусть H : G2 Z q - хеш-функция. Рассмотрим множество из n пользователей * n U = {1, 2,..., n}. Пусть p = и r = n mod 3. Множество U разбивается на три множества U1,U 2, U 3 с числом элементов p, p, p соответственно, если r = 0, или с числом элементов p, p, p + 1 соответственно, если r = 1, или с числом элементов p, p + 1, p + 1 соответственно, если r = 2.

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

Рассмотрим эти процедуры.

CombineThree (трехгрупповой протокол Диффи-Хеллмана).

Пусть три множества U1,U 2, U 3 имеют соответствующие секретные ключи s1, s2, s3 Z q. Пусть Rep (U i ) - представитель множества U i.

* Rep (U1 ) U 2, U 3 : s1 P.

Rep (U 2 ) U1,U 3 : s2 P.

Rep (U 3 ) U1,U 2 : s3 P.

s Каждый член U1 вычисляет H (e( s2 P, s3 P) ). s Каждый член U 2 вычисляет H (e( s1 P, s3 P) ). s Каждый член U 3 вычисляет H (e( s1 P, s2 P) ). Общий ключ членов множеств U1,U 2, U 3 H (e( P, P) ).

ss s CombineTwo (двухгрупповой протокол Диффи-Хеллмана).

Пусть два множества U1, U 2 имеют соответствующие секретные ключи s1, s2 Z q. Пусть Rep (U i ) - представитель множества U i.

* s Zq * (U1 ) Rep случайно генерирует и отправляет оставшимся sP пользователям. Общий ключ членов множеств U1, U 2 H (e( P, P) ).

ss s Протокол является защищенным от пассивного противника при предположении, что DHBDH проблема сложна.

Эффективность:

1 Связь. Требуется log 3 n раундов связи, по сети отправляется n log 3 n элементов группы G1.

2 Вычисления. 5 / 2(n 1) скалярных умножения в G1, n log 3 n вычислений спариваний, n log 3 n возведений в степень в G2, n log 3 n вычислений хеш функции H.

Данный протокол был программно реализован на базе библиотеки MIRACL для осуществления голосовой конференц-связи.

Глава 3. Реализация программного комплекса.

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

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



Pages:   || 2 |
 














 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.