---

Разделы На главную История денег и экономики История экономических знаний Формы безналичных денег Международные финансы Экономические концепции Экономические теории Экономика в реальной жизни Экономический анализ и интеграция Макроэкономика Экономика и социальное общество Социальная экономика Социология Кризисная экономика Инфляция в экономике Экономика зарубежных стран Иностранные деньги Государственное регулирование Бюджетная система Политическая экономия Политология Законы денег Налогообложение Аудит Банкротство Теория рынка Конкуренция Международная торговля Товарная биржа Нефть и газ на бирже Логистика Банки - услуги и операции Банки в России Банковский кредит Недвижимость Ипотека в банке Инвестирование Стратегии инвестирования Инвестиционные фонды Ценные бумаги Акции Вексель Облигации Опционы Фьючерсы Биржевая торговля Биржа Forex Фондовый рынок Фондовый рынок России Волны Эллиотта Теория фракталов Торговая теория Ганна Фибоначчи на бирже Графический анализ на бирже Паттерны Биржевой анализ "Крестики-нолики" Японские свечи Технический анализ Математика на бирже Фундаментальный анализ Биржевая торговля Стратегии торговли Механические торговые системы Программирование МТС Управление торговым капиталом Управление портфелем Управление риском Страхование Профессия трейдер Практический трейдинг Технологии инфосистем Информационный рынок Безопасность информации Криптология и криптография Реклама PR - Public Relations Маркетинг Финансовая система Начало бизнеса Предпринимательство Малый бизнес Микроэкономика Торговля Ценообразование Работа в Интернете Сайты, софт, дизайн Управление качеством Управление предприятием Производство продукции Стратегический менеджмент Учебники по менеджменту Системы и организации Теория систем Планирование Статистика финансов Управление персоналом Трудовые отношения Бухгалтерия «1С:Бухгалтерия» Управленческий учет Делопроизводство и офис Автоматизация делопроизводства Рынок труда Карьера Менеджер Лидерство и бизнес карьера Лидерство и карьера Общение и переговоры Общение в бизнесе Бизнес переговоры Инновации в моделировании Экономическое моделирование Нейронные сети Нейролингвистика Логика нейросетей Программирование Пакет Excel Технологии программирования Языки программирования Практическая психология Психологические тренинги Психология в медицине Возрастная психология Ваши скрытые резервы Здоровье и долголетие Работа с эмоциями Пикап Управление временем Гипнотерапия Подсознание Трансовые техники Магия Здоровье советы Спорт для здоровья Йога Религии Эзотерика Мистицизм

---

Схема подписи с верификацией по запросу

В работах Д. Шаума (см., например, [Ка5,Ка14]) впервые была предложена схема подписи с верификацией по запросу, в которой абонент V

не может осуществить верификацию подписи без участия абонента S. Такие схемы могут эффективно использоваться в том случае, когда фирма - изготовитель поставляет потребителю некоторый информационный продукт (например, программное обеспечение) с проставленной на нем подписью указанного вида [КУ10]. Однако проверить эту подпись, которая гарантирует подлинность программы или отсутствие ее модификаций, можно только уплатив за нее. После факта оплаты фирма - изготовитель дает разрешение на верификацию корректности полученных программ.

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

 

Схема ПВЗ

Пусть каждый пользователь S

имеет один открытый ключ P и два секретных ключа S1 и S2. Ключ S1 всегда остается в секрете, - он необходим для генерации подписи. Ключ S2

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

Вместе с обозначениями секретного и открытого ключей xÎRZq и yÎRZ*p (взятых из отечественного стандарта на электронную цифровую подпись) введем также обозначения S1=x и S2=u, uÎRZq, а также открытый ключ P=(g,y,w), где wºgu(mod p). Открытый ключ P публикуется в открытом сертифицированном справочнике.

Протокол ГП

Подпись кода m вычисляется следующим образом. Выбирается kÎRZq и вычисляется

. Затем вычисляется sº[xr+mku](mod q). Пара (r,s) является подписью для кода m. Подпись считается корректной тогда и только тогда, когда , где wºm-1(mod q).

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

Протокол верификации ПВ

Абонент V вычисляет  и просит абонента S доказать, что пара (r,s) есть его подпись под кодом m. Эта задача эквивалентна доказательству того, что дискретный логарифм g по основанию r равен (по модулю p) дискретному логарифму w по основанию g, то есть, что logg(p)wºlogr(p)g. Для этого:

                    Абонент V

выбирает a,bÎRZq, вычисляет  и посылает d абоненту S.

    Абонент S выбирает tÎRZq, вычисляет ,  и посылает h1 и h2 абоненту V.

    Абонент V высылает параметры a и b.

    Если , то абонент S

посылает V параметр t; в противном случае - останавливается.

    Абонент V проверяет выполнение равенств  и .

Если проверка завершена успешно, то подпись принимается как корректная.

Протокол ОП

 В отвергающем протоколе S доказывает, что logg(p)w¹logr(p)g. Следующие шаги выполняются в цикле l раз.

                    Абонент V

выбирает d,eÎRZq, d¹1, bÎR{0,1}. Вычисляет , , если b=0 и , , если b=1. Посылает S значения a, b, d.

                    Абонент S

проверяет соотношение . Если оно выполняется, то a=0, в противном случае a=1. Выбирает RÎRZq, вычисляет  и посылает V

значение c.

                    Абонент V

посылает абоненту S значение e.

                    Абонент S проверяет, что выполняются соотношения из следующих двух их пар: ,  и , . Если да, то посылает V значение R. Иначе останавливается.

                    Абонент V

проверяет, что .

Если во всех l циклах проверка в п.5 выполнена успешно, то абонент V принимает доказательства.

Таблица 13.1. Протокол верификации является интерактивным протоколом доказательств с абсолютно нулевым разглашением.



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

Требуется доказать, что вышеприведенный протокол удовлетворяет трем свойствам: полноты, корректности и нулевого разглашения [Ка5, Ка14].

Полнота означает, что если оба участника (V

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

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

доказать, что logg(p)wºlogr(p)g, когда на самом деле эти логарифмы не равны.

Предположим, что logg(p)w¹logr(p)g. Ясно, что для каждого a существует единственное значение b, то которое дает данный запрос d. Поэтому d не содержит в себе никакой информации об a. Если S смог бы найти h1, h2, t1

и t2 такие, что



и

,

где a1¹a2, то тогда выполнялось бы соотношение

logg(p)rº[(a1-a2)-1((b2-b1)+(t2-t1))](mod q)ºlogw(p)g.

Отсюда, очевидно, следует, что logg(p)wºlogr(p)g. В самом деле, пусть logw(p)gºlogg(p)r ºl. Тогда

,

что противоречит предположению. Следовательно, какие бы h1, h2, t1 и t2

не выбрал S, проверка, которую проводит V, может быть выполнена только для одного значения a. Отсюда вероятность обмана не превосходит 1/q. Отметим, что протокол верификации является безусловно стойким для абонента V, то есть доказательство корректности не зависит ни от каких предположений о вычислительной мощности доказывающего (S).

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


Для доказательства нулевого разглашения необходимо для любого возможного проверяющего V* построить моделирующую машину , которая является вероятностной машиной Тьюринга, работает за полиномиальное в среднем время и создает на выходе (без участия S) такое же распределение случайных величин, которое возникает у V* в результате выполнения протокола. В нашем случае, случайные величины, которые «видит» V*, - это h1, h2, и t. Необходимо доказать, что протокол верификации является доказательством с абсолютно нулевым разглашением, то есть моделирующая машина создает распределение случайных величин (h1,h2,t), которое в точности совпадает с их распределением, возникающим при выполнении протокола. Моделирующая машина  использует в своей работе V* в качестве «черного ящика».

Моделирующая машина

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

значение d

и после этого снова запоминает состояние машины V*.

    Выбирает hÎRZq и вычисляет  и .

    Получает от V* значения a и b. Если , то  останавливается.

    Машина  «отматывает» V*

на состояние, которое было запомнено в конце шага 1. Выбирает tÎRZq

и вычисляет  и .

    Машина  передает V*

h1, h2 и получает ответ (a¢,b¢). Возможны два варианта:

    5.1.    a=a¢, b=b¢. В этом случае моделирование закончено и  записывает на выходную ленту тройку (h1,h2,t) и останавливается.

    5.2.    a¹a¢ или b¹b¢. Отсюда следует, что . Предположим, что b¹b¢. Из этого следует, что a¹a¢. Следовательно,  может вычислить . Отсюда (b¢-b)/(a-a¢)=l - дискретный логарифм r по основанию g.

6. Машина  «отматывает» V*

на состояние, которое было заполнено в начале шага 1. Получает от V* значение d.

7. Выбирает hÎRZq вычисляет  и  и передает их V*.

8. Получает от V* значения a и b. Если , то  останавливается.


В противном случае вычисляет

t=[h-al-b](mod q), выдает (h1,h2,t) на выходную ленту и останавливается.

К пп. 7 и 8 необходимо сделать следующее пояснение. Поскольку logg(p)wºlogr(p)g, из этого следует, что logw(p)gºlogg(p)r. Отсюда

.

Из описания моделирующей машины  очевидно, что она работает за полиномиальное время. Величины (h1,h2,t) на шаге 5.1 выбираются в точности как в протоколе и поэтому имеют такое же распределение вероятностей. Кроме того, значения (h1,h2), выбираемые на шаге 7, имеют такое же распределение, как и в протоколе. Чтобы показать что и t имеет одинаковое распределение, достаточно заметить, что машина V*

не может по h1 и h2 определить, с кем она имеет дело - с S или . Поэтому, даже если бы V* могла каким-либо «хитрым» образом строить a и b с учетом (h1,h2), распределение вероятностей величин a

и b в обоих случаях одинаковы. Но значение t определяется однозначно четверкой величин a, b, h1, h2, при условии выполнения проверки на шаге 5 протокола.     n

Таблица 13.2. Отвергающий протокол является протоколом доказательства с абсолютно нулевым разглашением.

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

Полнота протокола очевидна. Если абоненты S

и V следуют протоколу, тогда абонент V всегда примет доказательства абонента S.

Для доказательства корректности прежде всего заметим, что если logg(p)wºlogr(p)g, то a и b, выбираемые абонентом V

на шаге 1, не несут в себе никакой информации о значении b. Поэтому, если S может “открыть” c, сгенерированное им на шаге 2, лишь единственным образом (то есть выдать на шаге 4 единственное значение R, соответствующее данному a), то проверка на шаге 5 будет выполнена с вероятностью 1/2 в одном цикле и с вероятностью 1/2l во всех l циклах.

Если же S может сгенерировать c таким образом, что с вероятностью, которая не является пренебрежимо малой, он может на шаге 4 “открыть” оба значения a, то есть найти R1 и R2 такие, что  и , то алгоритм, который использует S для этой цели, можно использовать для вычисления дискретных логарифмов: loggd=R2-R1.


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

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

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

Моделирующая машина

Следующие шаги выполняются в цикле l раз.

    Машина  запоминает состояние машины V*.

Получает от V*

значения a, b и d.

Выбирает aÎR{0,1}, RÎRZq и вычисляет . Посылает V* значение c.

Получает от V*

значение e.

Проверяет, было ли «угадано» на шаге 2 значение a (это значение было «угадано», если ,  и a=0, либо ,  и a=1). Если да, то записывает на входную ленту значение (c,R). В противном случае «отматывает» V* на то состояние, которое было запомнено на шаге 1, и переходит на шаг 2.

Легко видеть, что распределения случайных величин (c,R), возникающее в процессе выполнения протокола и создаваемые моделирующей машиной , одинаковы, поскольку R в обоих случаях - чисто случайная величина, а величина c

записывается на выходную ленту машины  только тогда, когда a совпало с b.

Поскольку значение a выбирается машиной  на шаге 3 случайным образом, а c не дает V*

никакой информации о значении a, на каждой итерации a

будет угадано с вероятностью 1/2. Отсюда следует, что машина  работает за полиномиальное в среднем время. n

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

---

---