Параллельная схема идентификации с нулевой передачей знаний
Параллельная схема идентификации позволяет увеличить число аккредитаций, выполняемых за один цикл, и тем самым уменьшить длительность процесса идентификации. Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и секретный ключи для стороны А, сначала выбирают К различных чисел V1, V2,..., VK, где каждое Vi, является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение V, таким, что сравнение х2 º Vi (mod n) имеет решение и существует Vi-1 (mod n). Полученная строка V1, V2,..., VK является открытым ключом. Затем вычисляют такие наименьшие значения Si, что Si = sqrt (Vi-1) (mod n). Эта строка S1, S2,..., SK является секретным ключом стороны А. Протокол процесса идентификации имеет следующий вид: 1. Сторона А выбирает некоторое случайное число r, r<n. Затем она вычисляет х = r2 mod n и посылает х стороне В. 2. Сторона В отправляет стороне А некоторую случайную двоичную строку из К бит: b1, b2,..., bK. 3. Сторона А вычисляет у = r * (S1b1 * S2b2 *... * SKbK) mod n. Перемножаются только те значения Si, для которых bi=1. Например, если b1=1, то сомножитель S1 входит в произведение, если же b1=0, то S1 не входит в произведение, и т.д. Вычисленное значение у отправляется стороне В. 4. Сторона В проверяет, что х = у2 * (V1b1 * V2b2 *... * VKbK) mod n. Фактически сторона В перемножает только те значения Vi, для которых bi=1. Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает S1, S2,..., SK. Вероятность того, что А может обмануть В, равна (1/2)Kt. Авторы рекомендуют в качестве контрольного значения брать вероятность обмана В равной (1/2)20 при К=5 и t=4. Пример. Рассмотрим работу этого протокола для небольших числовых значений. Если n = 35 (n - произведение двух простых чисел 5 и 7), то возможные квадратичные вычеты будут следующими:
Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35, потому что они не являются взаимно простыми с 35. Составим таблицу квадратичных вычетов по модулю 35, обратных к ним значений по модулю 35 и их квадратных корней.
Итак, сторона А получает открытый ключ, состоящий из К = 4 значений V: [4, 11, 16, 29]. Соответствующий секретный ключ, состоящий из К = 4 значений S: [3, 4, 9, 8]. Рассмотрим один цикл протокола. 1. Сторона А выбирает некоторое случайное число r = 16, вычисляет х = 162 mod 35 = 11 и посылает это значение х стороне В. 2. Сторона В отправляет стороне А некоторую случайную двоичную строку [1, 1, 0, 1]. 3. Сторона А вычисляет значение у = r * (S1b1 * S2b2 *...* SKbK) mod n = 16 * (31 * 41 * 90 * 81) mod 35 = 31 и отправляет это значение у стороне В. 4. Сторона В проверяет, что х = y2 * (V1b1 * V2b2 *... * VKbK) mod n = 312 * (41 * 111 * 160 * 291) mod 35 = 11. Стороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом r, пока сторона В не будет удовлетворена. При малых значениях величин, как в данном примере, не достигается настоящей безопасности. Но если n представляет собой число длиной 512 бит и более, сторона В не сможет узнать ничего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ. В этот протокол можно включить идентификационную информацию. Пусть I - некоторая двоичная строка, представляющая идентификационную информацию о владельце карты (имя, адрес, персональный идентификационный номер, физическое описание) и о карте (дата окончания действия и т.п.). Эту информацию I формируют в Центре выдачи интеллектуальных карт по заявке пользователя А. Далее используют одностороннюю функцию f(·) для вычисления f(I, j), где j - некоторое двоичное число, сцепляемое со строкой I. Вычисляют значения Vj = f(I, j) для небольших значений j, отбирают К разных значений j, для которых Vj являются квадратичными вычетами по модулю n. Затем для отобранных квадратичных вычетов Vj вычисляют наименьшие квадратные корни из Vj-1 (mod n). Совокупность из К значений Vj образует открытый ключ, а совокупность из К значений Sj - секретный ключ пользователя А.
|
