Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Курсы лекций
 Обсудить в форуме  Добавить новое сообщение
Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.6.2 Математические аспекты разработки схем электронной подписи Вверх: 4.6 Теоретические результаты Назад: 4.6 Теоретические результаты   Содержание   Предметный указатель


4.6.1 Основные понятия

Приведем необходимые определения. Согласно работам Гольдвассер, Микали, Ривеста [GMRiv] и Беллара, Микали [BeMi] протокол (схема) электронной подписи состоит из следующих компонентов:

1. Параметр безопасности (security parameter) $ k$. В качестве $ k$ может выступать длина подписи, длина подписываемых сообщений и т. п. Однако для каждой данной схемы род параметра безопасности должен быть фиксирован.

2. Пространство сообщений (message space) $ M$. Обычно предполагается, что $ M\subseteq\{0,1\}^l$, где $ l$ полиномиально от $ k$.

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

4. Алгоритм генерации ключей (key generation algorithm) -- полиномиальный (от $ k$) вероятностный алгоритм $ K$, генерирующий по данному параметру безопасности $ k$ пару $ (x,y)$, где $ x$ -- секретный ключ подписывающего, а $ y$ -- соответствующий открытый ключ. Если $ k$ -- это длина подписи или подписываемых сообщений, то на вход алгоритма $ K$ должна подаваться строка $ 1^k$.

5. Алгоритм генерации подписей (signature algorithm) -- полиномиальный (от $ k$) вероятностный алгоритм $ S$, генерирующий по данным сообщению $ m\in M$ и секретному ключу $ x$ (кроме этих, возможны и другие входные параметры) подпись $ s$ для сообщения $ m$.

6. Алгоритм проверки подписей (verification algorithm) -- полиномиальный вероятностный алгоритм $ V$, генерирующий по данным сообщению $ m\in M$, открытому ключу $ y$ и возможной подписи $ s'$ либо 1 (в этом случае говорят, что подпись $ s'$ для сообщения $ m$ принята) либо 0 (подпись отвергнута).


Все вышеуказанные параметры и алгоритмы, кроме секретного ключа, предполагаются общедоступными. Отметим, что алгоритм $ K$ обязан быть вероятностным, так как в противном случае противник может получить секретный ключ $ x$. Алгоритмы $ S$ и $ V$, напротив, могут быть детерминированными.

Говорят, что $ s'$ -- допустимая подпись для сообщения $ m$, если она принимается алгоритмом $ V$ с не пренебрежимо малой вероятностью, т. е. $ \Pr\{V(m,y,s')=1\}\geqslant k^{-c}$ для некоторой константы $ c>0$ и для всех достаточно больших $ k$. Разумеется, необходимо, чтобы подпись $ s=S(m,x)$ была допустимой для сообщения $ m$ или даже принималась с вероятностью $ 1$, но, вообще говоря, для этого сообщения могут существовать и другие допустимые подписи. Подделкой подписи для сообщения $ m$ называется нахождение противником, не имеющим секретного ключа подписывающего, допустимой подписи для этого сообщения.

Таким образом, в протоколе электронной подписи подписывающий участник, (отправитель, sender) сначала вычисляет $ (x,y)=K(k)$ и посылает $ y$ проверяющему, участнику (получателю, recipient'у), сохраняя $ x$ в секрете. Чтобы подписать сообщение $ m\in M$, подписывающий вычисляет $ s=S(m,x)$ и посылает $ s$ и $ m$ проверяющему, который после этого вычисляет $ V(m,y,s)$ и в зависимости от результата этого вычисления принимает или отвергает подпись $ s$ для сообщения $ m$. Отметим, что в большинстве протоколов электронной подписи информация пересылается только от подписывающего участника к проверяющему (протоколы не являются интерактивным).

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

Определение.  Схема подписи называется нестойкой против некоторой угрозы (за исключением универсальной подделки -- см. ниже) на основе некоторой атаки, если существует полиномиальный от $ k$ вероятностный алгоритм (противник), осуществляющий при возможности проведения данной атаки данную угрозу с вероятностью не менее $ k^{-c}$ (где $ c$ -- некоторая положительная константа) для бесконечного множества параметров $ k$. Вероятность берется по совместному распределению входных данных и случайных битов, используемых алгоритмом. Схема, не являющаяся нестойкой, называется стойкой.

В работе [GMRiv] описаны следующие типы угроз и атак (мы приводим их в порядке возрастания силы):


Типы угроз

1. Экзистенциальная подделка (existential forgery) -- подделка подписи для какого-нибудь (возможно, бессмысленного) сообщения, отличного от сообщений, которые противник получает или выбирает при осуществлении атак. При этом противник не контролирует выбор этого сообщения.

2. Селективная подделка (selective forgery) -- подделка подписи для сообщения, выбранного противником априори.

3. Универсальная подделка (universal forgery) -- нахождение эффективного алгоритма генерации подписи, функционально эквивалентного $ S(\cdot,x)$.

4. Полное раскрытие (a total break) -- вычисление некоторого секретного ключа, соответствующего открытому ключу $ y$ (что дает возможность генерировать подписи для любых сообщений). Отметим, что, вообще говоря, таких ключей может быть несколько.


Типы атак

1. Атака с открытым ключом (key-only attack). Противник получает только открытый ключ $ y$.

2. Атака с известными сообщениями (known-message attack). Противник получает полиномиальное от $ k$ количество пар вида $ (m,s)$, где $ m$ -- некоторое сообщение, а $ s$ -- допустимая подпись для $ m$. При этом противник никак не влияет на выбор сообщений $ m$ из этих пар.

3. Простая атака с выбором сообщений (generic chosen-message attack). Противник выбирает набор сообщений $ (m_1,\ldots,m_n)$, где $ n$ ограничено некоторым полиномом от $ k$, и получает набор $ (s_1,\ldots,s_n)$, где $ s_i$ -- допустимая подпись для $ m_i$. Предполагается, что сообщения $ m_i$ выбираются независимо от открытого ключа $ y$. Таким образом, эта атака не направлена против конкретного подписывающего.

4. Направленная атака с выбором сообщений (directed chosen-message attack). Противник получает открытый ключ $ y$, выбирает набор сообщений $ (m_1,\ldots,m_n)$, где $ n$ ограничено некоторым полиномом от $ k$, и получает набор $ (s_1,\ldots,s_n)$, где $ s_i$ -- допустимая подпись для $ m_i$. В отличие от предыдущей эта атака направлена против конкретного подписывающего (которому соответствует открытый ключ $ y$).

5. Адаптивная атака с выбором сообщений (adaptive chosen-message attack). Противник получает открытый ключ $ y$, выбирает сообщение $ m_1$ и получает допустимую подпись $ s_1$ для $ m_1$, затем выбирает сообщение $ m_2$ и получает допустимую подпись $ s_2$ для $ m_2$ и т. д.; возможно полиномиальное от $ k$ число циклов выбора сообщения и получения допустимой подписи для него. Другими словами, противник может обращаться к оракулу, дающему допустимые подписи для сообщений.

Вперед Вверх Назад Содержание Предметный указатель
Вперед: 4.6.2 Математические аспекты разработки схем электронной подписи Вверх: 4.6 Теоретические результаты Назад: 4.6 Теоретические результаты   Содержание   Предметный указатель

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100