1.4.3. Аутентификация, основанная на доказательствах с нулевым разглашением знания

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

1. Протоколы Файге - Фиата - Шамира. Это первый из пред-ложенных протоколов аутентификации, основанный на доказательствах с нулевым разглашением знания. Основой для него послужила схема аутентификации и цифровой подписи Фиата и Шамира (A. Fiat и A. Shamir, 1986).

Первоначально авторами был предложен протокол, показанный в табл. 1.20.

Таблица 1.20. Протокол аутентификации Фиата - Шамира Предварительный этап Р Центр доверия V s: (syn)=l,l¦>

у2 =x-ve (modn)

На предварительном этапе центр доверия выбирает два больших простых числа р, q (которые он держит в секрете) и публикует большое число п є Z : п - pq, п>5\2 бит (рекомендуется п ~ 1024 бита; для упрощения вычислений, но не для повышения безопасности рекомендуется выбирать п = (4p+?>)(4q+3) - число Блюма).

Рабочий этап протокола состоит в следующем. В цикле выпол-няются следующие действия (смысл цикла будет пояснен ниже; в табл. 1.20 показано содержание одного цикла):

Р выбирает случайное число г, г < п, вычисляет х = г2 mod п и отправляет его проверяющему V;

V вырабатывает случайный бит є є {0,1} и посылает его Р;

если е = 0, Р отправляет У число г, в противном случае (е - 1) он отправляет число у = ry(mod п)\

V проверяет, что у ф 0 (если у = 0, доказательство должно быть недействительно из-за того, что г = 0); если это условие вы-полнено, то проверяется равенство уг=х-ус (modи) и в случае его

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

Действия (1) - (4) повторяются в цикле t раз. Вероятность обма-на претендентом проверяющего (т. е. вероятность принятия прове-ряющим ошибочного решения) при однократном выполнении дей-ствий (1) - (4) равна 1/2, соответственно при выполнении цикла t раз вероятность равна 1/2'. Число t называют параметром безопасности протокола, его рекомендуется выбирать равным 20...40. Считается, что Р прошел аутентификацию, если проверка сравнения на шаге (4) во всех t циклах завершилась с положительным результатом.

Рассмотрим подробнее структуру этого протокола. Запрос е на шаге (2) требует, чтобы Р был способен ответить на два вопроса: один из них нужен для того, чтобы продемонстрировать знание s, другой - чтобы предотвратить обман честного претендента нечест-ным проверяющим. Соответственно запросу претендент отвечает на шаге (3) либо у = г, либо у - rs (mod п). Ни тот ни другой ответ не несет никакой информации об s: в первом случае он от s вообще не зависит, во втором - замаскирован случайной величиной г, которая известна только Р, так как на шаге (1) тоже была замаскирована при помощи однонаправленной функции.

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

е = О, так как это требует знания >/x(modn).

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

2

х =—(mod/і). Распределение вероятностей пар (х,у) не будет отли- v

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

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

Таблица L2L Протокол аутентификации Файге - Фиата - Шамира Предварительный этап Р Центр доверия V Sj. (Shn) = 1, 1 < 5 < п -1 , 2

V,- = St (mod /і), v = (v[, V2,..., s = (Sh s2 Jt) p,q - большие про-стые числа, n=pq n, vt, V2,..., V* Рабочий этап 1 P 1 1 v for a = 1,2,... ,t) 1 rі - случайное число, г,-<п, xі = rі mod п 2 (єц, е,ъ ..., eit) Є {0,1 f- случайное число 3 у, = rt(rftsef...s?)(modn) 4

Запечников С. В. Криптографические протоколы и их применение

Число п выбирается, как и в предыдущем случае. Далее Р выби- рает свой секретный ключ в виде набора k различных чисел ,

где каждое Sf'. (shn) = 1, 1 < s < п -1. Строка {v,-}*, где V/ = sf (mod n),

принимается в качестве открытого ключа Р.

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

Р выбирает случайное число г, г<п, вычисляет х = r(mod п) и отправляет его проверяющему V;

V вырабатывает случайную двоичную строку {е,}^, е. є {0,1}, и посылает ее Р\

к

Р вычисляет У ~ Г S-', перемножая только те sh которые со-

1=1

ответствуют единичным битам вектора е, и посылает у проверяющему;

к

V проверяет, что х= у2 - vf' .

1=1

В данном протоколе вероятность ошибки проверяющего в t проходах цикла равна 1/2*'. Авторы протокола рекомендовали выбирать к = 5, t - 4.

Стойкость протокола Фиата - Шамира основана на сложности извлечения квадратного корня по модулю л, когда неизвестно раз-ложение п на множители.

2.

Таблица 1.22. Протокол аутентификации Guillou - Quisquater Предварительный этап Р Центр доверия V Ip , в, J p,q - простые числа, п = pq, IP, J = Н(1Р), JBV s l(mod/i) п, J Рабочий этап Р V 1 г ~ случайное число, г є (1;/7 - 1), Т = rvmod п 2 Перед началом протокола V считывает у клиента Р строку J. Ра-бочий этап протокола состоит из следующих шагов:

Р выбирает случайное число г, \V выбирает случайное число deZ,d<0Р вычисляет D = rBd mod п и посылает его V;

V вычисляет Т - DvJd mod п. Аутентификация считается за-вершившейся успешно, если Т= Т (mod л), так как

Г = DV' = (rBd)yf = rvBdV = r\JB")d = /=Т (mod п).

Знание двух ответов Dj и D2 на два различных запроса d\ и d2 при одинаковом Т эквивалентно знанию в\ где k = НОД (v,d2- dx).

Корректность протокола доказывается следующим образом. Пусть d\, d2- два запроса к Р, посылаемые V на шаге (2) протокола, такие что 0 = Dv2J^ = Т (mod п). Тогда: / v

j'-^ = l(mod н).

Как известно, для любой пары положительных целых чисел уравнение ax-by = ±НОД(;с,у) всегда имеет решение, 0<а<у,

ОВозводя полученное ранее уравнение в степень а, получаем:

/ D Vv

2

А ,

V 1 У

/

D,

j±\+bv = l(mod 7г),

А ,

v 1 у

D 4

А

v 1

= l(mod п).

Но, поскольку В по условиям протокола является решением

Jb (mod п).

уравнения JBv = l(modn) ,то B±l =

, А у \ 1

Отсюда видно, что противник может легко вычислить секретный ключ В абонента Р.

3. Протокол Шпорра и основанные на нем протоколы. Схема, предложенная Шнорром (С. Schnorr, 1989), основана на сложности задачи дискретного логарифмирования (табл. 1.23).

Таблица 23. Протокол аутентификации Шнорра Предварительный этап Р Центр доверия V SER {1,...,<7-1}, v = a mod р p,q — простые числа, q\p~l, a GZp:aq = l(modр) Р, q, a, v Рабочий этап Р V 1 г є {1,...,х = ar mod р 2 е Є {0,...,2'_1}-случайное число 3 у — r+se mod q 4 <1

x=ayve mod р

Центр доверия выбирает и открыто публикует два простых числа р и с]\ q\p-l - и число а ї 1: aq = l(modp). Далее выбирается случайное число sПротокол аутентификации состоит в следующем:

Р выбирает случайное число rV вырабатывает случайное число е: 0 < е < 2' -1 и посылает его Р\

Р вычисляет у = r+se (mod q) и посылает его V;

V проверяет, выполнено ли равенство Jt = aV mod p.

Как видно, проверка аутентичности Р основана на том, что в вычислениях Р на шаге (3) участвует его секретный ключ s, который V получить не может вследствие вычислительной сложности задачи дискретного логарифмирования. Р считается прошедшим аутенти-фикацию, если проверка сравнения на шаге (4) прошла с положи-тельным результатом.

Безопасность протокола основана на величине параметра t. Авторы указывают, что сложность вскрытия протокола составляет порядка 2' операций, и рекомендуют выбирать р~512 бит, д~140 бит, t = 72 битам. Свойство нулевого разглашения для схемы Шнорра строго не доказано.

Брикелл и Мак-Карли (Brickell Е., McCurley К., 1990-1991) предложили модификацию протокола Шнорра (табл. 1.24).

Таблица 1.24. Протокол аутентификации Брикелла - Мак-Карли

Предварительный этап

Р

V

Центр доверия

s

v.* v = a's (mod р)

p,q,w - простые числа,

k

qw\p-l\q2\p-l\q,w>2 a\aq = l(mod р)

р, а, у

Окончание табл.

х = a' mod р - случайное число 2 е Є |0,...,2'}-случайное число 3 у = (r+se) mod (р-1) 4 х=ау ve mod р

Для этого протокола центр доверия выбирает простые числа p,q,w : qw\p - 1 \q2\p - 1 \q,w> 2k, где k - параметр безопасности. Числа q и w являются секретными, остальные - открытыми. Далее, как и в предыдущем случае, Р выбирает случайный секретный ключ s

Рабочий этап протокола аутентификации выполняется следую-щим образом:

Р выбирает случайное число г<р, вычисляет х - a mod р и посылает его проверяющему V (вычисления могут быть выполнены предварительно);

V вырабатывает случайное число е: 0<е<2'-1,и пересылает его Р;

Р вычисляет у = (r+se) mod (р-1) и пересылает его Р;

V проверяет выполнение равенства х = aV mod p.

Описанный протокол не имеет принципиальных отличий от ис-ходного протокола Шнорра, поэтому дополнительных пояснений по нему, на наш взгляд, не требуется. Заметим только, что протокол дополнительно усложняет задачу противника: он должен уметь уже не только решать задачу дискретного логарифмирования, но и задачу факторизации числа (р-1).

Авторы протокола рекомендуют выбирать к-140, р~512 бит.

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

функцией. Сообщение не хешируется перед подписанием - вместо этого хеш-функция включается в сам алгоритм цифровой подписи.

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

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

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

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