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

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

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


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

УНИВЕРСИТЕТ

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

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

Слепые подписи, основанные на билинейном спаривании,

и их применение для генерации электронных монет.

Курсовая работа

студентки 147 группы

Сахно Е. А.

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

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

Срок сдачи работы:

Подпись научного руководителя:

Владивосток 2007 Оглавление.

Введение……………………………………………………………………………………..3 Глава 1. Криптография на эллиптических кривых и основные проблемы……………………….……………………………………………………………5 1.1 Эллиптические кривые………………………………………………………….. 1.2 Билинейные спаривания………………………………………………………. 1.3 Спаривание Вейля……………………………………………………………… 1.4 Основные проблемы в группе точек эллиптической кривой……………….. Глава 2. Частично слепая подпись……………………………………………………….. 2.1 Формальные определения……………………………………………………... 2.2 Схема основной подписи……………………………………………………… 2.3 Схема слепой GDH подписи…………………………………………………... 2.4 Схема частично слепой подписи……………………………………………… 2.5 Доказательства основных свойств……………………………………………. 2.6 Преимущества данной схемы…………………………………………………. Глава 3. Групповая слепая подпись, основанная на ИД………………………………... 3.1 Установка открытого ключа, основанного на ИД, с помощью билинейного спаривания………………………………………………. 3.2 Схема CZK групповой подписи, основанной на ИД………………………… 3.3 Схема групповой слепой подписи, основанной на ИД……………………… 3.4 Доказательства основных свойств……………………………………………. 3.5 Преимущества данной схемы…………………………………………………. Глава 4. Одношаговая слепая подпись основанная на ИД……………………………... 4.1 Структура слепой подписи, основанной на ИД……………………………… 4.2 Схема…………………………………………………………………………… 4.3 Доказательства основных свойств……………………………………………. 4.4 Преимущества данной схемы…………………………………………………. Заключение………………………………………………………………………………… Список использованной литературы…………………………………………………….. Введение.

Объект исследования данной работы – электронные монеты.

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

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

Для достижения данной цели были выделены следующие основные задачи:

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

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

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

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

Данная работа построена следующим образом: в Главе 1 приведены основные понятия из области эллиптических кривых и билинейных спариваний, на основе которых будут рассматриваться все схемы, а также проблемы, введенные в билинейных группах, на которые опираются доказательства безопасности данных схем. В Главах 2, 3, 4 рассмотрены три различные схемы слепых подписей, их отличительные черты и преимущества.

Обезличенностью денег, неотслеживаемостью платежей и введением частных валют осуществляется так называемая "денежная свобода" (monetary freedom).

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

К настоящему моменту в Internet представлены две технологии, реализующие эту идею.

Компания Mondex, возглавляемая Тимоти Джонсом (Timothy Jones), предлагает сетевую версию электронного кошелька, реализованную в виде аппаратно программного комплекса.

Компания же DigiCash под руководством Д.Чаума представила технологию сетевых электронных денег ecash в чисто программном варианте. Рассмотрим это решение.

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

Использование blinding factor и составляет суть приема "слепой подписи", предложенного Чаумом (Слепая подпись впервые была представлена Чаумом на конференции Crypto ’82) в дополнение к обычному методу криптозащиты с открытыми ключами. Благодаря использованию "слепой подписи" банк не в состоянии накапливать информацию о плательщиках, в то же время сохраняя возможность следить за однократным использованием каждой "монеты" данным клиентом и идентифицировать получателя каждого платежа. Чом называет такую логику взаимодействия сторон "односторонней безусловной непрослеживаемостью" платежей. Покупатель не может быть идентифицирован даже при сговоре продавца с банком. В то же время, покупатель при желании может идентифицировать себя сам, и доказать факт осуществления сделки, апеллируя к банку. Такая логика призвана воспрепятствовать криминальному использованию электронной наличности.

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

Глава 1.

Эллиптические кривые. Билинейное спаривание.

Группы точек эллиптических кривых были представлены задолго до того, как было обнаружена потенциальная возможность их использования для построения билинейных отображений. В 1985, Миллер первым упомянул использование групп эллиптических кривых в криптографии для реализации протокола распределения ключей Diffie-Hellman с целью получения большей надежности и эффективности.

Miller утверждал что, т.к. DLP атаки (атаки, основанные на дискретном логарифмировании) не были (и до сих пор не являются) эффективными против групп эллиптических кривых, реализация эллиптических кривых позволит улучшить надежность, в то время как каждый отдельный элемент группы будет занимать меньшее количество бит. Подобное утверждение было выдвинуто Koblitz. В году, схема цифровой подписи на эллиптических кривых, ECDSA, была утверждена стандартом США. В действительности, группы эллиптических кривых, до сих пор устояли перед многочисленными испытаниями против множества эффективных атак.

В 2000, Joux развил интерес к билинейным свойствам групп эллиптических кривых, используя их для реализации еще более оптимизированной версии протокола распределения ключей Diffie-Hellman, где теперь три человека могли договориться об общем ключе, вместо двух. Не смотря на это, начиная именно со статьи 2001 года Boneh и Franklin схемы шифрования с идентификационными данными, началось интенсивное изучение схем на билинейном спаривании в криптографии.

Наш пример применения билинейных групп в криптографии применяет эти группы для достижения 4 целей: (1) реализовать новые функциональности, для которых известные небилинейные конструкции являются не достаточно эффективными;

(2) достигнуть лучших временных и пространственных характеристик;

(3) отказаться от услуг доверительного центра;

и (4) избежать случайных оракулов.

Обозначение: будем писать G = g для обозначения того, что элемент g порождает группу G.

1.1 Эллиптические кривые E над полем Определение (Эллиптическая кривая). Эллиптической кривой K называется совокупность решений для уравнения ( x, y ) E : y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 + a6 вместе с дополнительной точкой на бесконечности P, где a1, a2, a3, a4, a6 K и 0, где является дискриминантом кривой E и определяется следующим образом:

= d 22 d8 8d 43 27 d 62 + 9d 2 d 4 d = a12 + 4a d2 = 2a4 + a1a d4 = a3 + 4a d6 = a1 a6 + 4a2 a6 a1a3a4 + a2 a3 a 2 d Если L некоторое расширение поля K, то совокупности L -рациональных точек на кривой E это: E ( L) = {( x, y ) L L : y 2 + a1 xy + a3 y x 3 a2 x 2 a4 x a6 = 0} { P } Замечания:

1. Уравнение E также называется Уравнением Вейерштрасса.

2. Говорят, что кривая E определена над полем K потому что коэффициенты a1, a2, a3, a4, a6 K. Иногда пишут E / K для того, чтобы подчеркнуть что E определена над полем K, и K называется основным полем. Заметим, что если E определена над полем K, то E определена над любым расширением L поля K.

3. Условие 0 означает что кривая E гладкая, т.е. в любой точке кривой нельзя провести более одной касательной. Доказательство приведено в [5].

4. Точка P единственная точка, принадлежащая прямой на бесконечности, удовлетворяющая уравнению Вейерштрасса.

5. L -рациональные точка кривой E это точки ( x, y ), удовлетворяющие уравнению кривой и координаты которых x, y L. Точка на бесконечности P также является L -рациональной точкой для всех расширений L поля K.

E : y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 + a Уравнение Вейерштрасса определенное над полем K может быть сведено к значительно более простой форме применением соответствующих замен переменных. Как правило, используют эти упрощенные уравнения. В зависимости от характеристики основного поля уравнение K представляется в виде:

1. Для характеристики char ( K ) 2,3 уравнение сводится к виду: y 2 = x3 + ax + b, где a, b K. Дискриминант такой кривой равняется = 16(4a 3 + 27b 2 ) 2. Для характеристики char ( K ) = 2 уравнение сводится к виду:

• для случая a1 0 : y 2 + xy = x 3 + ax 2 + b, где a, b K. Эта кривая является несуперсингулярной. Дискриминант кривой равняется = b • для случая a1 = 0 : y 2 + cy = x 3 + ax + b, где a, b K. Эта кривая является суперсингулярной. Дискриминант кривой равняется = c 3. Для характеристики char ( K ) = 3 уравнение сводится к виду:

• для случая a12 a2 : y 2 = x 3 + ax 2 + b, где a, b K. Эта кривая является несуперсингулярной. Дискриминант кривой равняется = a 3b • для случая a12 = a2 : y 2 = x 3 + ax + b, где a, b K. Эта кривая является суперсингулярной. Дискриминант кривой равняется = a Полные математические выкладки можно посмотреть в [1].

Групповой закон.

Пусть дана E эллиптическая кривая, определенная над полем K. Существует метод хорд-и-касательных для сложения точек кривой E ( K ) для получения третей точки этой же кривой E ( K ). Вместе с операцией сложения, совокупность точек кривой E ( K ) формируют абелеву группу с P, служащим единичным элементом.

Закон сложения для эллиптических кривых имеет геометрическую интерпретацию. Пусть P = ( x1, y1 ) и Q = ( x2, y2 ) две различные точки эллиптической кривой E.

Тогда сумма R точек P и Q, определяется следующим образом. Проведем линию через точки P и Q ;

эта линия обязательно пересечет эллиптическую кривую в третьей точке [2], и R будет отображением этой точки относительно оси x. Что проиллюстрировано на рисунке.

Удвоение R точки P определяется следующим образом. Проведем касательную к эллиптической кривой в точке P. Эта линия пересечет кривую в другой точке. Тогда R будет отображением этой точки относительно оси x. Что также проиллюстрировано на рисунке.

В [5] доказано, что введенный метод сложения 2-х точек является аддитивным.

В [4] доказано, что точка (х,у) - аддитивно обратная к точке (х, -у). Т.е. операция сложения, множество точек E(Fp) и точка О образуют аббелеву группу, в которой единичным элементом является О.

Алгебраические формулы группового закона могут быть выведены из геометрической интерпретации. Приведем пример группового закона для эллиптической кривой E / K : y 2 = x 3 + ax + b, char ( K ) 2,3 [1]:

1. Единичный элемент: P + = + P = P для любого P E ( K ).

2. Обратный элемент: Если P = ( x, y ) E ( K ), то ( x, y ) + ( x, y ) =. Точка ( x, y ), обозначаемая как P будет обратным элементом к точке P ;

заметим, что тока P так же лежит на кривой E ( K ). Так же, =.

3. Операция суммирования: Пусть P = ( x1, y1 ) E ( K ) и Q = ( x2, y2 ) E ( K ), где P ±Q. Тогда P + Q = ( x3, y3 ), где y y y y x3 = 2 1 x1 x2 и y3 = 2 1 ( x1 x3 ) y1.

x2 x x2 x 4. Операция удвоения точки: Пусть P = ( x1, y1 ) E ( K ), где P P. Тогда 2 P = ( x3, y3 ), где:

3 x12 + a 3x12 + a x3 = 2 x1 и y3 = ( x1 x3 ) y 2 y1 2 y Порядок группы.

Пусть дана эллиптическая кривая E над полем Fq. Количество точек кривой E (Fq ), обозначаемое как # E (Fq ) называется порядком кривой E над полем Fq. Из того, что уравнение Вейерштрасса имеет не более двух решений для любого x Fq, следует что # E (Fq ) [1, 2q + 1]. Теорема Хассе дает более точные границы # E (Fq ).

Теорема (Хассе). Пусть дана эллиптическая кривая E над полем Fq. Тогда q + 1 2 q # E (Fq ) q + 1 + 2 q.

Этот интервал носит название интервала Хассе. Другая запись этой же формулы имеет вид: # E (Fq ) = q + 1 t, где t 2 q ;

t называется следом кривой E над полем Fq. Т.к.

2 q относительно мало, имеем что # E ( Fq ) q.

Теорема (о допустимых порядках эллиптических кривых). Пусть q = p m, где p характеристика поля Fq. Существует эллиптическая кривая E над полем Fq порядка # E (Fq ) = q + 1 t тогда, и только тогда когда:

• t 0 (mod p ) и t 2 4q.

• m нечетное и либо (a) t = 0 ;

либо (b) t 2 = 2q и p = 2 ;

либо (c) t 2 = 3q и p = 3.

• m четное и либо (a) t 2 = 4q ;

либо (b) t 2 = q и p 1 (mod 3) ;

либо (c) t = 0 и p 1 (mod 4).

Следствие:: для любого простого p и целого t, удовлетворяющим t 2 p, существует эллиптическая кривая E над полем Fq порядка # E (Fq ) = q + 1 t.

Определение. Пусть p характеристика поля Fq. Эллиптическая кривая E над полем называется суперсингулярной, если p делит t, где t след кривой. Если p не делит t, то кривая E называется несуперсингулярной.

Если E эллиптическая кривая над полем Fq, то E так же определена над любым расширением Fq поля Fq. Группа E (Fq ) Fq -рациональных точек является n подгруппой группы E (Fq ) Fq -рациональных точек и, таким образом # E (Fq ) делит n n # E (Fq ).

n E Теорема. Пусть дана эллиптическая кривая над полем Fq, и пусть {Vn } # E (Fq ) = q n + 1 Vn n 2, # E (Fq ) = q + 1 t. Тогда для любого где n последовательность, определяемая рекурсивно V0 = 2, V1 = t и Vn = VVn 1 qVn 2 для любого n 2.

Структура группы эллиптической кривой.

Теорема (Структура группы эллиптической кривой). Пусть дана E эллиптическая кривая над полем Fq. Тогда E (Fq ) изоморфна Z n Z n, где n1 и n2 однозначно 1 определенные положительные целые числа такие, что n2 делит как n1 так и q 1.

Заметим, что # E (Fq ) = n1n2. Если n2 = 1, то E (Fq ) является циклической группой. Если n2 1, то говорят что E (Fq ) имеет ранг 2. Если n2 небольшое целое, то говорят что E (Fq ) почти циклическая группа.

Изоморфные классы.

Определение. Две эллиптические кривые E1 и E2 над полем K, заданные уравнениями Вейерштрасса:

E1 : y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 + a E2 : y 2 + a1 xy + a3 y = x 3 + a2 x 2 + a4 + a называются изоморфными над полем K, если существуют такие u, r, s, t K, u 0, что замена переменных ( x, y ) (u 2 x + r, u 3 y + u 2 sx + t ) приводит к тому, что уравнение для E1 переходит в уравнение E2.

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

1.2 Билинейные отображения (спаривания).

Определение (Билинейное спаривание). Пусть алгоритм Bilinear_Setup, для входного параметра безопасности 1k, выводит параметры (e, q, g1, g2, G 1, G 2, G T ) для билинейного спаривания, где:

1. G 1, G T две (мультипликативные) циклические группы простого порядка q = (2k ) ;

2. каждый элемент G 1, G 2 и G T имеет единственное двоичное представление;

3. параметры включают порождающие для групп G 1 = g1 и G 2 = g2.

G1 G 2 G T, 4. e эффективно вычисляемое отображение (спаривание) обладающее следующими свойствами:

• (Билинейность) для любых g1 G 1, g2 G 2 и для любых a, b Z q2, e(g1a, g2 ) = e(g1, g2 ) ab ;

b • (Невырожденность) если порождающий группы G1 и g1 g порождающий группы G 2, то e(g1, g2 ) порождает G T.

Билинейные отображения так же называют спариваниями, т.к. методы Weil и Tate спариваний обычно используются для их реализации.

Дивизоры.

Рациональную функцию F ( x) одной переменной из поля K ( x) можно с точностью до константы задать списком нулей и полюсов с учетом их кратностей.

Поскольку числитель и знаменатель функции F ( x) являются полиномами из K [ x], они раскладываются на конечное число линейных множителей. Точно так же рациональную функцию на алгебраической кривой E ( K ) можно с точностью до константы задать конечным списком ее нулей и полюсов с учетом их кратностей.

Дивизором на алгебраической кривой E ( K ) назовем формальную (без указания и выполнения конкретной арифметики над точками) сумму точек кривой с кратностями (целыми коэффициентами) nP : D = nP ( P ), nP Z в которой все nP, PE ( K ) за исключением конечного числа раны нулю. Сумма берется по конечному числу точек, поскольку мы рассматриваем рациональные функции на кривой, а числа nP связаны с нормированием кривой в точке P.

Множество дивизоров образует абелеву группу с законом сложения, которая называется группой дивизоров алгебраической кривой и обозначается E(K ) Div( E ( K )). Конечное множество точек P в дивизоре, для которых nP 0 называется носителем дивизора. Степенью дивизора D называется целочисленная сумма его коэффициентов: deg( D) = n p. Дивизор D называется положительным D 0, PE ( K ) если все его коэффициенты неотрицательны.

Ненулевая рациональная функция f, заданная на алгебраической кривой E ( K ), может иметь лишь конечное число нулей и полюсов. Можно определить дивизор функции: div( f ) = vP ( f )( P) Div( E ( K )), где vP порядок нуля (или PE ( K ) полюса) функции в точке P. Тогда произведению функций на кривой будет соответствовать сумма их дивизоров, т.е. существует гомоморфизм абелевых групп:

K ( E )* Div( E ( K )).

Дивизор на кривой, равный дивизору некоторой рациональной функции, называется главным дивизором.

Теорема (о дивизоре для функции на эллиптической кривой). Дивизор D= nP ( P ) является дивизором некоторой функции эллиптической кривой E PE ( K ) тогда и только тогда, когда одновременно выполняются равенства:

n • = 0 (сумма целых чисел) P n • P = P (сумма точек эллиптической кривой) P Пусть f - функция на кривой E и D - дивизор на этой же кривой, причем носители дивизоров div( f ) и D не пересекаются. Определим значение функции f на дивизоре D как: f ( D) = f ( P)v. P Теорема (закон взаимности Вейля). Пусть E ( K ) - неособая кривая и f, g K ( E ) рациональные функции такие, что носители их дивизоров не пересекаются. Тогда f (div( g )) = g ( div( f )).

1.3 Спаривание Вейля (Weil pairing).

Пусть K - конечное поле характеристики char ( K ) = p и E / K - эллиптическая кривая. Предположим, что на кривой E / K существует точка простого порядка m и ( p, m) = 1.

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

Таким образом, существуют точки кривой E ( K ) имеющие порядок m. Эти точки образуют подгруппу E[m] группы кручения. Число точек кручения порядка m кривой E ( K ) равно m 2. Все точки порядка m лежат в некотором конечном расширении L поля K.

Пусть T - точка кривой E ( L), имеющая порядок m, т.е. точка кручения порядка m. Тогда по теореме «о дивизоре для функции на эллиптической кривой»

существует функция fT L( E ) на кривой E ( L) с дивизором div( fT ) = m(T ) m( P ).

Пусть T1 - точка кривой E ( L) такая, что mT1 = T (при необходимости можно перейти к расширению поля L ). Пусть отображение [m] кривой E ( L) на себя задается умножением точки P E ( L) на число m : [m]( P) mP. Тогда можно составить композицию функции fT и отображения [m] :

( fT [m])( P) = fT ([m]( P)) = fT (mP ) Эта функция имеет нули кратности m в тех точках, которые после умножения на m дадут T. Такие точки имеют вид T1 + R, где R - любая из m 2 точек порядка m.

Функция fT [m] имеет полюсы кратности m в точках R, которые после умножения на m дадут P. Поэтому:

div( fT [m]) = m (T1 + R) m ( R) RE [ m ] RE [ m ] Определим функцию gT L( E ) с дивизором div( gT ) = ((T1 + R ) ( R)) RE [ m ] Функция gT существует, т.к. ее дивизор имеет степень 0 и соответствующая (T1 + R R ) = m 2T1 = P. Функции fT [m] и gT m имеют сумма точек кривой равна RE [ m ] один и тот же дивизор, поэтому с точностью до константы из L имеем fT [m] = gT m.

Пусть S E[m] - еще одна точка кручения кривой E ( L) (допускается случай S = T ). Тогда для любой точки T E ( L) имеет место равенство:

gT ( X + S ) m = fT ([m] X + [m]S ) = fT ([m] X ) = gT ( X ) m m g (X + S) = 1.

Следовательно: T gT ( X ) Определим спаривание Вейля e m : E[m] E[m] {µ m }, где µ m - корень степени gT ( X + S ) m из 1 в поле L, полагая: e m ( S, T ) =.

gT ( X ) Здесь X - любая точка кривой E ( L) такая, что оба обозначения g ( X + S ) и g ( X ) определены и ненулевые. Подчеркнем, что хотя g определена с точностью до ненулевой константы из L (известен лишь ее дивизор), спаривание Вейля не зависит от этой константы, т.к. она сокращается при делении.

Теорема (свойства спаривания Вейля). Спаривание Вейля e m : G 1 G 2 G T обладает следующими свойствами:

1. Билинейность:

• e m ( S1 + S 2, T ) = e m ( S1, T )e m ( S 2, T ) • e m ( S, T1 + T2 ) = e m ( S, T1 )e m ( S, T2 ) 2. Знакопеременность: e m ( S, T ) = e m (T, S ) 3. Невырожденность: Если e m ( S, T ) = 1 для любого T E[n], то S = P. Т.е.

Существуют точки S, T такие, что e m ( S, T ) - примитивный корень степени m из 1.

4. Сочетаемость: Если S E[nm] и T E[n], то e nm ( S, T ) = en ([m]S, T ) Лемма. Пусть e : G 1 G 2 G T билинейное спаривание, как определено выше. Пусть S G 1 и T G 2, тогда:

e( S,0) = e(0, T ) = • • e( S,0) = e( S, T ) 1 = e( S, T ) e([ j ] S, T ) = e( S, T ) j = e( S,[ j ]T ) для любого j Z.

• Из 1 свойства спаривания Вейля следует, что это отображение при фиксированной точке T является изоморфизмом группы кручения E[m] на подгруппу порядка m мультипликативной группы L*. Кроме того, точки кривой E ( K ), имеющие порядок m, являются точками кручения порядка m кривой E ( L). Тогда, если на эллиптической кривой E ( K ) выполняется равенство P = nQ, то в группе L* выполняется e m ( P, T ) = e m (Q, T ) n. Точку T нужно выбрать так, чтобы значения L* спаривания Вейля пробегали в всю подгруппу порядка m. Имеем последовательность гомоморфизмов: E ( K ) E[m]( L) L*.

Первое отображение означает переход от кривой E ( K ) к кривой E ( L) над расширенным полем, где число # L 1 делится на m. Второе отображение есть спаривание Вейля.

1.4 Основные проблемы в группе точек эллиптической кривой.

1. Проблема дискретного логарифмирования (DLP): дано 2 элемента P, Q, надо найти целое n Zq* такое, что Q = nP.

2. Вычислительная проблема Диффи - Хэллмана (CDHP): дано P, aP, bP, a, b Zq* необходимо найти abP.

3. Проблема решения Диффи – Хэллмана (DDHP): дано P, aP, bP, cP, a, b, c Zq* необходимо определить, что c = ab mod q.

4. Проблема (k+1)-ой экспоненты (k+1 Exponent Problem): дано k + 1 значение {P, yP, y 2 P,..., y k P}, необходимо вычислить y k +1 P.

G1 называется Gap Diffie – Hellman Group (GDH группа), если DDHP может быть решена за полиномиальное время, но не существует такого полиномиального алгоритма, который бы решил CDHP или DLP.

5. Bilinear Diffie-Hellman (BDH) Problem:

Даны случайные P, aP, bP, cP G1 на выходе e( P, P) abc, где a, b, c R Z q.

6. Generalized Tate Inversion (GTI) Problem:

Дано h G2 надо найти пару ( S, T ) G1 такую, что e( S, T ) = h, где e : G1 G1 G Тейт спаривание.

7. Modified Generalized Bilinear Inversion (MGBI):

Дано h G2 и порождающий элемент P G1, необходимо найти точку S G такую, что e( P, S ) = h, где e определено как билинейное спаривание.

Основываясь на вышеперечисленных проблемах, определим новую:

Определение (Bilinear Diffie-Hellman Inversion (BDHI) Problem).

Даны три случайных элемента aP, bP, cP G1, нужно вычислить два элемента S, T G такие, что e( S, T ) = e( P, P) abc. Таким образом, BDHI предположение заключается в том, что не существует PPT алгоритма, который может решить BDHI проблему с не незначительной вероятностью.

Очевидно, что BDH проблема может быть решена, если BDHI проблема разрешима.

Также очевидно, что BDHI проблему можно разрешить, если CDH проблема может быть решена. И так, BDHI предположение находится где-то между CDH предположением и BDH. Поэтому BDHI предположение слабее BDH, но сильнее CDH.

Более того, предложим новое вычислительное предположение, названое one-more bilinear Diffie-Hellman Inversion (1m-BDHI) предположение.

Определение 3 (1m-BDHI предположение).

Пусть e : G1 G1 G2 - билинейное спаривание, где G1 и G 2 группы простого порядка q и P - порождающий элемент группы G1. Пусть x, y случайные элементы из Z q и пусть X = xP, Y = yP. Злоумышленнику A известно (e, G1, G 2, q, P, X, Y ) и он имеет доступ к двум оракулам.

(1) Первый из них – target oracle TO, каждый раз он не требует входных параметров и возвращает случайную точку из G1.

(2) Второй – helper oracle HO, который принимает Z G1 и возвращает S, T G1 такие, что e( S, T ) = e(Y, Z ) x. Также этот оракул HO возвращает вспомогательную информационную часть R, которая может быть использована для проверки равенства e( S, T ) = e(Y, Z ) x. Пример ( R, S, T ) используемый в данной работе дан со следующими замечаниями:

Говорим, что A выиграл, если на выходе у него имеется последовательность точек S1, T1,..., S n, Tn G1 удовлетворяющих следующим равенствам e( S1, T1 ) = e(Y, Z 1 ) x,..., e( S n, Tn ) = e(Y, Z n ) x, где все различные Z 1,..., Z n получены от TO злоумышленника A и число запросов злоумышленника к его ораклу HO строго меньше n. 1m-BDHI выгода злоумышленника A, обозначим ее Adv1m BDHI (k ), это вероятность того, что A A выиграет, taken over the coins используемых в генерации (e, G1, G2, q, P, X, Y ), монеты злоумышленника A и монеты, используемые ораклом TO across its invocations. Будем говорить, что 1m-BDHI проблема сложна если функция Adv1m BDHI (k ) незначительна для всех полиномиальновременных A злоумышленников A.

Замечание 1.

В данной работе действительный ответ ( R, S, T ) оракула HO должен удовлетворять:

e( R, S ) = e( xP, yP), e( R, Z ) = e( P, T ).

Действительно, предположим что R = rP. Тогда из выше приведенных равенств следуют равенства:

S = r 1 xyP, T = rZ.

В итоге имеем e( S, T ) = e( yP, Z ) x.

И в заключении опишем ROS-проблему.

Определение 4 (ROS-Problem).

Дана предсказывающая случайная функция F : Z q Z q, нужно найти коэффициенты l a k,i Z q и разрешимую систему l + 1 различных уравнений (1) относительно неизвестных с1, с 2,..., сl над Z q :

a k,1c1 +... + a k,l cl = F (a k,1,..., a k,l ), для k = 1,2,..., t. (1) Таким образом, ROS предположение заключается в том, что не существует PPT алгоритма для решения ROS проблемы с не незначительной вероятностью.

Глава 2.

Частично слепая подпись.

Существует два недостатка слепых подписей:

1). Банк должен вести базу данных потраченных монет, чтобы предотвратить их повторное использование, база данных должна постоянно обновляться и она может разрастаться до неограниченного размера.

2). Банк не может определить то, что пользователь ему предоставляет для подписания, пользователь может подменить номинал. Возможны несколько решений этой проблемы: банк использует разные открытые ключи для монет разного наминала, тогда пользователи должны позаботиться о том, чтобы у них был полный список этих ключей. Второе решение основано на использовании алгоритма cut-and-choose, но это очень не эффективно.

Частично слепая подпись представлена впервые Abe и Fujisaki [12], она позволяет явно включить некоторую информацию в слепую подпись. И она предотвращает разрастание базы данных использованных монет т.к. в каждую монету встраивается информация о ее сроке действия, следовательно, все просроченные монеты можно удалить из базы. Также в слепую подпись можно встроить и номинал монеты.

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

2.1 Формальные определения.

В [13] Abe and Okamoto представили формальное определение схемы частично слепой подписи:

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

• (Выработка ключа) G - это вероятностный полиномиальный алгоритм, который на входе принимает параметр секретности k, а на выходе выдает пару открытый и секретный ключ (pk;

sk).

• (Подписание) S (соответствует подписывающему) и U (соответствует пользователю) – это пара вероятностных интерактивных машин Тьюринга, каждая из которых имеет:

открытую входную ленту (чтение) закрытую входную ленту (чтение) закрытую случайную ленту (чтение) закрытую рабочую ленту (чтение и запись) закрытую выходную ленту (запись) открытую выходную ленту (запись) входную коммуникационную ленту (чтение) выходную коммуникуционную ленту (запись) Открытая входная лента U содержит pk и info.

Открытая входная лента S содержит info.

Закрытая входная лента S содержит sk.

Закрытая входная лента U – сообщение m.

S и U вступают в протокол и останавливаются через время, которое полиномиально зависит от n. Когда они остановились, открытая выходная лента S содержит или «завершено» или «не завершено», а закрытая выходная лента U имеет или «неудача» или (info, m, ).

U S открытая входная pk, info r info закрытая входная m r sk закрытая случайная r закрытая рабочая r/w неудача / (info, m, ) закрытая выходная w открытая выходная w завершено/незавершено входная коммуникационная r выходная коммуникуционная w • (Проверка) V - это вероятностный полиномиальный алгоритм, который на вход принимает (pk, info, m, ), а на выходе выдает вера подпись или нет.

Безопасность частично слепой подписи основана на трех требованиях: завершенность, частичная слепость и невозможность подделать данную подпись.

Определение (Завершенность):

Если S и U выполняют протокол подписания частично слепой подписью и на открытой входой ленте U содержится (pk, info), а на открытой входной ленте S – info, тогда с вероятностью как минимум 1 для большого n и некоторой константы c, nc на выходе S будет «завершено» и выход U будет содержать (info, m, ), которая удовлетворяет следующему равенству V(pk, info, m, ) = accept.

Частичная слепость:

Определим свойство слепости, представив сначала игру между злоумышленником S (подписывающий) и двумя честными пользователями U 0 и U1.

1. Злоумышленник S (1n, info) на выходе получает pk и ( m0, m1 ) 2. Установим входные ленты U 0 и U1 следующим образом:

Случайно выбираем b {0,1} и устанавливаем mb и mb на закрытых входных лентах U 0 и U1 соответственно. ( b = 1 - b) - Устанавливаем (info, pk) на открытой входной ленте U 0 и U - Случайно выбираем содержание закрытых случайных лент 3. S вступает в исполнение протокола с U 0 и U 4. Если U 0 и U1 сгенерируют верные подписи (info, mb, b ) и (info, mb, b ), соответственно, тогда это даст ( 0, 1 ) злоумышленнику S, в противном случае будет «неудача».

5. S на выходе имеет b {0,1} AdvPBS = 2 Pr[b = b] 1, где вероятность берется как вероятность blind Обозначим подбрасывания монеты злоумышленником S и пользователями U 0 и U1.

Определение (Частичная слепость):

Злоумышленник S - (t, )-взламывающий свойство слепости схемы частично слепой blind подписи, если S выполняет игру за время не большее t и AdvPBS как минимум равно.

Схема частично слепой подписи называется (t, )-слепой если не существует злоумышленника S(t, )-взламывающего свойство слепости данной схемы.

Замечание (Совершенная частичная слепость):

Схема является совершенно слепой если она является (, 0)-слепой.

Неподделываемость:

Определим свойство не подделываемости рассмотрев следующую игру между злоумышленником U и честным подписывающим S.

1. (pk, sk) получено с помощью G(1), pk устанавливаем на открытую входную ленту U и S, и sk устанавливаем на закрытую входную ленту S.

2. При каждом выполнении протокола подписи с S, злоумышленник U на выходе имеет информацию info, которая устанавливается на открытую входную ленту S. Тогда U вступает в протокол с S согласованным и прослоенным (interleaving) способом.

3. Для каждой информации info, положим linfo – число выполнений протокола подписи, где S на выходе выдает «завершено», с информацией info на его входной ленте. (для информации info, которая никогда не появляется на входной ленте S, полагаем linfo = 0).

4. U выигрывает игру, если U сгенерировал l верных подписей (info, m1, 1 ),..., (info, ml, l ) для некоторой информации info такой, что a). mi m j для любых пар (i, j) таких, что i j (i, j {1,..., l }).

b). l linfo unforge Определим AdvPBS как вероятность того, что U выиграет игру, определяется как подбрасывание монеты злоумышленником U, G и S.

Определение (неподделываемость):

Злоумышленник U - (t, qs, ) -подделывающий схему частично слепой подписи, если U выполняет игру за время меньшее t, U выполняет менее qs раз протокол подписания и AdvPBS не меньше. Схема частично слепой подписи - (t, qs, ) -неподделываемая unforge если не существует злоумышленника U (t, qs, ) -подделывающего схему.

Для дальнейшего рассмотрения введем обозначения:

P - порождающий элемент группы G1, порядком которой является простое число q.

Билинейное спаривание: e : G1 G1 G2.

H 0 :{0,1}* G1*, H :{0,1}* {0,1} - хэш - функции.

2.2 Схема “основной” подписи (The Basic Signature Scheme).

1). Генерируем параметры системы (Generate): params.

2). Генерация ключа (KeyGenparam):

Выбираем случайное число x Z*, вычисляем Ppub = xP.

q Ppub - открытый ключ, x - секретный.

3). Подписание (Sign):

Дан секретный ключ x и сообщение m, которое необходимо подписать, вычисляем S= P.

H ( m) + x 4). Проверка (Verify):

Дано: открытый ключ Ppub, сообщение m и подпись S, подпись действительна, если выполняется равенство e( H (m) P + Ppub, S ) = e( P, P).

Безопасность данной схемы основана на предположении, что “k+1 Exponent Problem”, “CDHP” сложны в G1.

2.3 Схема слепой GDH подписи.

1). Генерируем параметры системы (Generate): params.

2). Генерация ключа (KeyGenparam):

Выбираем случайное число x Z*, вычисляем Ppub = xP.

q Ppub - открытый ключ, x - секретный.

3). Подписание (Blind signature issuing):

Пользователь хочет подписать сообщение m {0,1}*.

• Затемнение (Blind).

Пользователь выбирает случайное число r Z*, вычисляет M = H 0 (m) + rP и q отправляет M подписывающему.

• Подписание вслепую (BSign).

Подписывающий возвращает пользователю = x M.

• Избавление от слепого множителя (Unblind).

Пользователь вычисляет подпись = rPpub и в результате получает (m, ).

4). Проверка (Verify):

Дано: открытый ключ Ppub, сообщение m и подпись, подпись действительна если выполняется равенство e( Ppub, H 0 (m)) = e( P, ).

Безопасность данной схемы основана на предположении, что “CDHP” сложна в G1.

2.4 Схема частично слепой подписи, основанной на GDH слепой подписи и на “основной” подписи.

Параметры системы - params = {G1, G2, e, q,, P, H, H 0 }.

1). Генерация ключа (Key generation):

Выбираем случайное число x Z*, вычисляем Ppub = xP, Ppub - открытый ключ, x q закрытый.

2). Протокол генерации частично слепой подписи (Partially blind signature issuing protocol):

Обозначим подписываемое сообщение как m, а открытую согласованную информацию как c.

• Генерация открытой информации (Generation of the public information).

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

• Затемнение (Blinding).

r Z*, Пользователь выбирает случайное число вычисляет q U = H 0 (m || c) + r ( H (c) P + Ppub ) и отправляет U подписывающему.

• Подписание (Signing).

Подписывающий возвращает обратно пользователю V, где V = U.

H (c ) + x • Избавление от слепого множителя (Unblinding).

Пользователь вычисляет S = V rP.

( S, m, c) - частично слепая подпись сообщения m с открытой информацией c.

3). Проверка (Verification):

Подпись действительна тогда и только тогда, когда верно равенство e( H (c) P + Ppub, S ) = e( P, H 0 (m || c)).

2.5 Доказательства основных свойств.

Доказательство свойства завершенности данной схемы.

Завершенность следует из следующих равенств:

e( H (c) P + Ppub, S ) = e(( H (c) + x) P,V rP ) = e(( H (c) + x) P,( H (c) + x) 1U rP) = e(( H (c) + x) P,( H (c) + x) 1U )e(( H (c) + x) P, rP) = e( P, H 0 (m || c) + r ( H (c) P + Ppub )e( H (c) P + Ppub, rP ) = e( P, H 0 (m || c))e( P, r ( H (c) P + Ppub ))e( H (c) P + Ppub, rP) = e( P, H 0 (m || c)).

Доказательство свойства частичной слепоты данной схемы.

На шаге Затемнение (Blinding) r выбирается случайно из Z*, таким образом q H 0 (m || c) + r ( H (c) P + Ppub ) - случайный элемент группы G1. Подписывающий получает случайную информацию и открытую заранее согласованную информацию, которую он уже знает, т.е. он не получает никакой дополнительной информации о подписываемом сообщении.

Подписывающий уверен, что его подпись содержит открытую информацию, согласованную между ним и пользователем и эта информация не может быть удалена из подписи. Это действительно так, т.к. если пользователь генерирует c и заменяет им c в подписи ( S, m, c), для получения ( S, m, c), тогда имеем e( H (c) P + Ppub, S ) = e( P, H 0 (m || c)), что означает e(( H (c) H (c)) P, S ) = e( P, H 0 (m || c) H 0 ( m || c)), т.е. c и c должны удовлетворять равенству ( H (c) H (c)) S = H 0 (m || c) H 0 (m || c). А это маловероятно, т.к. H и H 0 - криптографические хэш функции.

Дана действительная подпись ( S, m, c) и пара (U,V ), всегда существует уникальный затемняющий множитель r такой, что V S = rP. И так, благодаря случайности затемняющего множителя, выбранного на шаге Затемнение (Blinding), и тому факту, что открытая информация не зависит от подписываемого сообщения даже если одинаковая информация используется для двух различных сообщений, подписывающий не сможет связать подпись и отдельный протокол подписания.

От сюда следует, что частично слепая подпись удовлетворяет свойству частичной слепости.

Доказательство свойства неподделываемости данной схемы приведено в [11].

2.6 Преимущества данной схемы:

1. Короткая подпись. В представленной схеме подпись состоит только из элемента G1. На практике, размер элемента из G1 может быть представлен степенью двойки используя технику сжатия. Следовательно данная схема может обеспечить короткую подпись, длина подписи равна половине длины подписи DSA для такого же уровня безопасности. Это свойство имеет большое значение в системах электронной коммерции. Электронные монеты сохраняются в электронных кошельках пользователей, которые часто расположены на смарт картах, обладающих ограниченным объемом памяти. Небольшой размер подписи делает систему более практичной.

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

3. Одновременная проверка. (Для одинаковой информации с). Эффективность системы имеет большое значение, когда число проверок очень велико (на пример когда банк выпускает много электронных монет и пользователь желает проверить действительность монет). Представленная частично слепая подпись очень эффективна когда пользователь сразу проверяет песколько подписей с одинаковой открытой информацией с. Предположим что S1, S 2,..., S n – частично слепые подписи для сообщений m1, m2,..., mn с одинаковой информацией с.

Одновременная проверка заключается в проверке следующего равенства:

e( H (c) P + Ppub, Si ) = e( P, H 0 (mi || c)).

Глава 3.

Групповая слепая подпись, основанная на идентификационных данных (ID-based групповая слепая подпись).

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

Слепая групповая подпись сочетает в себе свойства и групповой и слепой подписи. Она была впервые представлена by Lysyanskaya and Ramzan. Учитывая свойства групповой слепой подписи Lysyanskaya и Ramzan создали новый тип системы Электронных Платежей, Распределенный Электронный Банк. Отличие от прежних систем в том, что электронные наличные могут выпускаться несколькими банками. И это большое преимущество новой системы делает приложение электронных платежей более обширным чем ранее.

ID-based групповая подпись впервые была представлена by Park, Kim and Won.

Схема неэффективна: длина открытого ключа группы и подписи пропорциональны размеру группы;

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

анонимность схемы не гарантируется. В настоящее время, лучшая ID-based групповая подпись представлена в работе [16] by Chen, Zhang and Kim (CZK подпись). Длина открытого ключа группы и подписи постоянна, не зависит от размера группы.

The CZK is provable secure. Безопасность схемы основана на системах ID-based шифровании с открытым ключом, которые построены на билинейном спаривании. В данной главе расмотрим схему ID-based групповой слепой подписи.

3.1 Установка открытого ключа, основанного на ИД, с помощью билинейного спаривания.

ID-based система открытых ключей была представлена Шамиром, она позволяет некоторой открытой информации, такой как имя, адрес или e-mail (лучше чем просто случайная строка) выступать в качестве открытого ключа. Секретный ключ пользователя вычисляется Закрытым Генератором Ключей (Private Key Generator PKG) и посылается пользователю по секретному каналу. ID-based установка открытого ключа с помощью билинейного спаривания может быть осуществлена следующим способом:

Пусть G1 - циклическая аддитивная группа порожденная P, ее порядок – e : G1 G1 G2.

q.

простое число Билинейное спаривание Определим две криптографические хэш-функции H1 :{0,1}* Z q и H 2 :{0,1}* G1.

1. Установка: PKG выбирает случайное число s Z* и вычисляет Ppub = sP. Центр q params = {G1, G2, e, q, P, Ppub, H1, H 2 }, публикует параметры системы а s оставляет в секрете, это главный ключ (master-key).

2. Выработка ключа: Пользователь отправляет его идентификационную информацию – ID в PKG. PKG вычисляет открытый ключ пользователя QID = H 2 ( ID) и возвращает S ID = sH 2 ( ID) пользователю как его секретный ключ.

Представим сначала схему CZK ID-based групповой подписи, на основе которой далее рассмотрим схему CZK ID-based слепой групповой подписи.

3.2 Схема CZK групповой подписи, основанной на ИД.

Пусть G1 - GDH группа, с порождающим элементом P, и пусть ее порядок простое число q, G2 – циклическая мультипликативная группа того же порядка q.

Билинейное спаривание e : G1 G1 G2. Определим две идеальные хэш-функции H1 :{0,1}* G1 Z q, H 2 :{0,1}* G1 G1.

Менеджер группы (GM) выбирает случайное число s Z* и вычисляет Ppub = sP.

q GM сохраняет s как главный ключ (master-key) и публикует открытый ключ группы Y = {G1, G2, e, q, P, Ppub, H1, H 2 }. Пользователь выбирает случайное число r Z* в q качестве своего долгосрочного закрытого ключа и посылает rP менеджеру группы GM. GM вычисляет S ID = sH 2 ( ID || T, rP ), где T – время действия закрытого ключа r и посылает S ID пользователю. Закрытый ключ пользователя это пара r, S ID, открытый ключ – ID.

Схема CZK ID-based групповой подписи может быть описана следующим протоколом:

1. Присоединение:

i = 1, 2,..., k.

xi Z*, - пользователь случайно выбирает Посылает q rxi P, xi P, rP, ID, S ID менеджеру GM.

если S ID = sH 2 ( ID || T, rP ), e(rxi P, P) = e(rP, xi P ), GM посылает пользователю Si = sH 2 (T, rxi P ), i = 1, 2,..., k.

- сертификаты члена группы – ( Si, rxi P ), а соответствующие закрытые ключи rxi, где i = 1, 2,..., k.

- GM добавляет rxi P, xi P, rP, ID в список членов группы.

2. Подписание:

a Z* - подписывающий выбирает случайное число и вычисляет q U = aH 2 (T, rxi P ).

вычисляет V = rxi H 2 (m,U ), вычисляет h = H1 (m,U + V ), вычисляет W = (a + h) Si.

(U,V,W, T, rxi P ) – подпись сообщения m.

3. Проверка:

Если T – действительно, то проверяющий вычисляет H 2 (T, rxi P ), H 2 (m,U ), h = H1 (m,U + V ) и проверяет e(W, P ) = e(U + hH 2 (T, rxi P), Ppub ), если равенство выполняется, то подпись действительна.

4. Раскрытие:

Пусть имеется действительная групповая подпись, GM может легко определить подписавшего из следующих двух равенств:

e(rxi P, P) = e( xi P, rP) e( S ID, P) = e( H 2 ( ID || T, rP ), Ppub ) 3.3 Схема групповой слепой подписи, основанной на ИД.

В данной схеме впервые не интерактивная часть «подписание», выше представленной схемы CZK ID-based групповой подписи, преобразована в интерактивное «подписание», а затем в схему слепой подписи:

Шаг 1 (пользователь):

Пользователь хочет подписать сообщение и посылает запрос m подписывающему.

Шаг 2 (подписывающий):

затем вычисляет U = aH 2 (T, rxi P) и Выбирает случайное число a Z*, q посылает пользователю.

Шаг 3 (пользователь):

Пользователь выбирает случайное число b Z*, потом он вычисляет и q посылает U = U + bP и H 2 (m,U ) подписывающему.

Шаг 4 (подписывающий):

Подписывающий вычисляет V = rxi H 2 (m,U ) и посылает полученное значение пользователю.

Шаг 5 (пользователь):

Пользователь вычисляет V = V + bP и h = H1 (m,U + V ), затем посылает h подписывающему.

Шаг 6 (подписывающий):

Вычисляет W = (a + h) Si и посылает полученное значение пользователю.

Шаг 7 (пользователь):

Вычисляет W = W + bPpub.

(U,V,W, T, rxi P ) - ID-based групповая слепая подпись сообщения m. Далее покажем с помощью теорем 1 и 2, что свойства корректности и слепости для данной схемы выполняются.

3.4 Доказательства основных свойств.

Теорема 1:

ID-based групповая слепая подпись рассмотренная выше – корректна.

Доказательство:

Дана подпись (U,V,W, T, rxi P ), проверяющий сначала вычисляет h = H1 (m,U + V ) и H 2 (T, rxi P). А затем он проверяет, выполняется ли равенство e(W, P) = e(U + hH 2 (T, rxi P), Ppub ).

Подробно проверка выглядит следующим образом:

e(W, P) = e(W + bPpub, P) = e(W, P )e(bP, Ppub ) = e((a + h) Si, P)e(bP, Ppub ) = e(asH 2 (T, rxi P ) + hsH 2 (T, rxi P ), P )e(bP, Ppub ) = e(U + hH 2 (T, rxi P ) + bP, Ppub ) = e(U + hH 2 (T, rxi P ), Ppub ) Теорема 2:

Схема CZK ID-based групповой слепой подписи – корректно слепая.

Доказательство:

На шаге 3, пользователь выбирает случайное число b для затемнения U, полученного от подписывающего, и получает U. В тоже время, пользователь затемняет сообщение m с помощью хэш-функции H 2. Таким образом, на шаге 4 подписывающий ставит подпись на сообщении m и на U не зная их. На шаге 5 случайное число b маскирует V и заменяет его на V. И так на шаге 6 подписывающий использует свой сертификат Si для проставления подписи без знания самого подписываемого сообщения. На шаге 7 пользователь использует случайное число b для затемнения W полученного от подписывающего.

3.5 Преимущества данной схемы.

Длина открытого ключа группы зависит и групповой слепой подписи зависит от числа членов группы. Алгоритмы и протоколы групповой слепой подписи эффективны. В данной схеме слепая групповая подпись получается из CZK схемы только добавлением модульного сложения;

в то время как, в LR98 вводится вычисление дискретного логарифма, корня логарифма и случайной перестановки для затемнения групповой подписи CS97. Т.к. вычислительная сложность важна, схема, рассмотренная в данной работе, более эффективна, чем LR98.

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

Глава 4.

Одношаговая слепая подпись, основанная на ИД.

4.1 Структура слепой подписи, основанной на ИД Определение 5.

Схема ID-based слепой подписи (IDBS) может быть представлена как совокупность четырех алгоритмов (или протоколов):

1). Установка (Setup).

Этот алгоритм выполняется PKG (доверительный центр), на входе получает секретный параметр и генерирует открытые параметры системы params и master key.

PKG раскрывает params, а ключ для себя master key держит в секрете.

2). Получение секретного ключа (Extract).

Дан идентификатор ID, master key и params, на выходе алгоритм выдает закрытый ключ DID идентификатора ID.

3). Подписание (Issue).

В этом протоколе подписывающий ставит слепую подпись по запросу пользователя.

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

а). Затемнение (Blind).

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

б). Подписание вслепую (Blind Sign).

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

в). Избавление от слепого множителя (Unblind).

На входе – подпись и используемая ранее случайная строка r, на выходе – подпись без слепого множителя (unblinded signature).

4). Проверка (Verify).

На вход алгоритма подается подпись, сообщение m, идентификатор ID и параметры системы params, на выходе – 1, если подпись для сообщеия m и идентификатора ID - действительна или 0, в противном случае.

Безопасность схемы ID-based слепой подписи состоит из двух требований:

свойство слепости (слепоты) и невозможность подделать дополнительную подпись.

Будем говорить схема слепой подписи безопасна, если она удовлетворяет этим двум требованиям.

4.2 Схема 1). Установка (Setup).

PKG (доверительный центр) генерирует параметры системы params и master key следующим образом:

• генерирует группы G1 и G2 простого порядка q с билинейным спариванием e : G1 G1 G2 ;

• выбирает произвольный порождающий элемент P G1 ;

• выбирает случайное число s Z q и устанавливает Ppub = sP ;

• выбирает криптографические хэш функции H1, H 2 :{0,1}* G1. Открытые параметры PKG - params = (G1, G2, e, q, P, Ppub, H1, H 2 ) ;

его master key - s Z q.

2). Получение секретного ключа (Extract).

Подписывающий с идентификатором ID получает свой закрытый ключ DID = sQID от PKG, где QID = H1 ( ID) G1.

3). Подписание (Issue).

• Затемнение (Blind).

Пользователь выбирает случайно число r1 Z q в качестве слепого множителя, вычисляет Pm = r1 H 2 (m) и посылает Pm подписывающему.

• Подписание вслепую (Blind Sign).

Подписывающий отправляет обратно ( A, B, C ), где A = xID Pm, B = xID DID, C = xID P, xID Z q.

R • Избавление от слепого множителя (Unblind).

Сначала пользователь убеждается в действительности слепой подписи ( A, B, C ), для этого он проверяет выполняются ли следующие равенства e( A, P ) = e( Pm, C ), e(QID, Ppub ) = e( B, C ).

Затем пользователь выбирает случайное число r2 Z q и вычисляет подпись ( A, B, C ), где A = r2 r11 A, B = r21 B, C = r2C.

4). Проверка (Verify).

Пусть ( A, B, C ) - подпись на сообщении m и Pm = H 2 (m). Для удостоверения подлиности необходимо проверить:

e( A, P) = e( Pm, C ), e(QID, Ppub ) = e( B, C ).

4.3 Доказательства основных свойств Корректность.

Если некто с идентификатором ID поставил подпись = ( A, B, C ) на сообщении m по рассмотренному протоколу, то легко проверить, что будет удовлетворять проверке:

e( A, P) = e(r2 r11 A, P) = e(r2 r11 xID Pm, P ) = e(r2 r11 xID r1Pm, P ) = e(r2 xID Pm, P) = e( Pm, r2 xID P) = e( Pm, r2C ) = e( Pm, C ), e( B, C ) = e(r21 B, r2C ) = e( B, C ) = e( xID DID, xID P) = e( DID, P ) = e(QID, sP) = e(QID, Ppub ).

Подобным образом можно показать, что слепая подпись сгенерирована честным подписывающим на шаге Подписание вслепую (Blind Sign) удовлетворяет равенствам, проверяемым пользователем на шаге Избавление от слепого множителя (Unblind).

e( A, P) = e( xID Pm, P) = e( Pm, C ), e(QID, Ppub ) = e( DID, P) = e( xID xID DID, P) = e( B, C ).

Теорема Представленная схема ID-based слепой подписи действительно является слепой.

Доказательство:

Свойство слепоты может быть доказано на основе определения 6. Предположим, что для сообщений mb ( m1b ) сгенерированы подписи b = ( Ab, Bb, Cb ), (соответственно 1b = ( A1b, B1b, C1b ) ), пользователь U 0 (соотв. U1 ) посылает Pm (соотв. Pm ) 1b b злоумышленнику A, который затем возврвщает слепую подпись b = ( Ab, Bb, Cb ) (соотв. 1b = ( A1b, B1b, C1b ) ).

Для b, если мы сможем доказать, что существуют два целых числа r1, r2 Z q такие, что Pm = r1H 2 (mb ), Ab = r2r11 A1b, Bb = r21 B1b, Cb = r2C1b, 1b тогда можно утверждать, что для злоумышленника A, b может быть связана с сообщениями ( Pm, A1b, B1b, C1b ) или с пользователем U1. Другими словами, 1b злоумышленник A не сможет определить, который из двух пользователей сгенерировал подпись b.

Предположим, что ( Ab, Bb, Cb ) и ( A1b, B1b, C1b ) действительны, тогда e( Ab, P ) = e( Pm, Cb ), e(QID, Ppub ) = e( Bb, Cb ) ;

b e( A1b, P) = e( Pm, C1b ), e(QID, Ppub ) = e( B1b, C1b ).

1b Пусть cb, c1b Z q целые числа удовлетворяющие Cb = cb P, C1b = c1b P соответственно. Из свойства билинейности спаривания имеем:

Ab = r2 r11 Ab = r2 r11 xID Pm = r2 xID Pm Ab = cb Pm b b Cb = r2Cb = r2 xID P b Bb = r21 Bb = ( r2 xID ) 1 DID = (r2 xID ) 1 sQID Bb = cb1sQID Аналогично получаем:

A1b = c1b Pm, 1b B1b = c1b sQID.

Пусть r1, r2 целые числа, удовлетворяющие Cb = r2C1b (т.е. r2 = cb c1b mod q ) и Pm = r1Pm (= r1H 2 (mb )) 1b b соответственно, тогда они удовлетворяют и Ab = r2r11 A1b и Bb = r21 B1b.

4.4 Преимущества данной схемы:

Даная схема не основывается ни на каких других, ранее рассмотренных ID-based схемах подписи, и не предполагает сложности вычисления никаких ранее введенных вычислительных проблем. Во-первых, вычислительная сложность оптимальна. А именно, каждая отдельная генерация подписи - это запрос от пользователя и ответ подписывающего – готовая подпись. А во-вторых, представленная схема – вероятностно безопасна по отношению к обшей параллельной атаке и не использует ROS-предположение. Безопасность схемы основана на новом предположении – 1m BDHI-предположении. И так как это ID-based схема, то не существует трудностей в распределении ключей.

Заключение.

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

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

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

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

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

Список использованной литературы.

[1]- Guide to Elliptic Curve Cryptography Darrel Hankerson, Alfred MenezesScott, Vanstone. Springer [2]- Алгоритмические основы эллиптической криптографии, А.А. Болотов, С.Б.

Гашков, А.Б. Фролов, А.А. Часовских, Москва: Мэи, 2000.

[3]- Н.Смарт Криптография Москва: Техносфера, 2006. -528 с.

[4]- Коблиц Н., Введение в эллиптические кривые и модулярные формы: Пер. с англ. М.: Мир, 1988.- 320 с.

[5]- Ростовцев А.Г., Маховенко Е.Б., Теоретическая криптография, [6]- Silverman J.H. The arithmetic of elliptic curves. Springer-Verlag, 1986.

[7]- Security of blind digital signatures. Ari Juels, Michael Luby, Rafail Ostrovsky.

[8]- W.Diffi and M.Hellman. “New directions in cryptography”. IEEE Trans. On inf.

Theory, IT-22, pp. 644-654, 1976.

[9]- Blind Digital Signatures and Their Application. Otto-Carl Marte, 1999.

[10]- A.Juels, M.Luby, R.Ostrovsky: Security of Blind Signatures, Proceedings of Crypto ’97, LNCS 1294, Springer Verlag, pp. 150-164.

[11]- Fangguo Zhang, Reihaneh Safavi-Naini and Willy Susilo. Efficient Verifiably Encrypted Signature and Partially Blind Signature from Bilinear Pairings. School of Information Technology and Computer Science University of Wollongong, NSW Australia, 2004.

[12]- M. Abe and E. Fujisaki, How to date blind signatures, Advances in Cryptology – Asiacrypt. 1996. LNCS 1163, pp. 244-251, Springer-Verlag, 2002.

[13]- M. Abe and T. Okamoto, Provably secure partially blind signatures, Advances in Cryptology - CRYPTO 2000. LNCS 1880, pp. 271-286, Springer-Verlag, 2000.

[14]- T. Okamoto. Efficient blind and partially blind signatures without random oracles.

[15]- Jun Zhong Dake He, A New Type of Group Blind Signature Scheme Based on Bilinear Pairings, School of Information Science and Technology, Southwest Jiaotong University, Chengdu 610031, China, http://eprint.iacr.org/2006/439, [16]- X. Chen, F. Zhang and K. Kim. A new ID-based group signature scheme from bilinear pairings, http://eprint.iacr.org/2003/116, 2003.

[17]- Wei Gao, Xueli Wang, Guilin Wang and Fei Li. One-Round ID-Based Blind Signature Scheme without ROS Assumption, http://eprint.iacr.org/2007/007, 2007.



 














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

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