Патенты. Владельцем патентов на ряд особенностей слепых подписей является Чаум (Chaum) (см. ).
Табл. -. Патенты Чаума на слепые подписи
№
патента США
|
Дата
|
Название
|
Упрощенная схема идентификации с нулевой передачей знаний
Схему идентификации с нулевой передачей знаний предложили в 1986 г. У. Фейге, А. Фиат и А. Шамир. Она является наиболее известным доказательством идентичности с нулевой передачей конфиденциальной информации.
Рассмотрим сначала упрощенный вариант схемы идентификации с нулевой передачей знаний для более четкого выявления ее основной концепции. Прежде всего выбирают случайное значение модуля n, который является произведением двух больших простых чисел. Модуль nдолжен иметь длину 512... 1024 бит. Это значение n может быть представлено группе пользователей, которым придется доказывать свою подлинность. В процессе идентификации участвуют две стороны:
• сторона А, доказывающая свою подлинность,
• сторона В, проверяющая представляемое стороной А доказательство.
Для того чтобы сгенерировать открытый и секретный ключи для стороны А, доверенный арбитр (Центр) выбирает некоторое число V, которое является квадратичным, вычетом по модулю n. Иначе говоря, выбирается такое число V, что сравнение
x2 V(mod n)
имеет решение и существует целое число
V-1mod n
Выбранное значение V является открытым ключом для А. Затем вычисляют наименьшее значение S, для которого
S sqrt (V-1)(mod n).
Это значение S является секретным ключом для А.
Теперь можно приступить к выполнению протокола идентификации.
1. Сторона А выбирает некоторое случайное число r, r < n. Затем она вычисляет
x = r2 mod n
и отправляет х стороне В.
2. Сторона В посылает А случайный бит b.
3. Если b = 0, тогда А отправляет г стороне В. Если b = 1, то А отправляет стороне В
y = r * S mod n
4. Если b = 0, сторона В проверяет, что
x = r2 mod n
чтобы убедиться, что А знает sqrt(x). Если b = 1, сторона В проверяет, что
x = y2 * V mod n,
чтобы быть уверенной, что А знает sqrt(V-1).
Эти шаги образуют один цикл протокола, называемый аккредитацией. Стороны А и В повторяют этот цикл t раз при разных случайных значениях г и b до тех пор, пока В не убедится, что А знает значение S.
Если сторона А не знает значения S, она может выбрать такое значение г, которое позволит ей обмануть сторону В, если В отправит ей b= 0, либо А может выбрать такое г, которое позволит
обмануть В, если В отправит ей b = 1. Но этого невозможно сделать в обоих случаях. Вероятность того, что А обманет В в одном цикле, составляет 1/2. Вероятность обмануть В в t циклах равна (1/2)t,
Для того чтобы этот протокол работал, сторона А никогда не должна повторно использовать значение г. Если А поступила бы таким образом, а сторона В отправила бы стороне А на шаге 2
другой случайный бит b, то В имела бы оба ответа А. После этого В может вычислить значение S, и для А все закончено.
Параллельная схема идентификации с нулевой передачей знаний
Параллельная схема идентификации позволяет увеличить число аккредитаций, выполняемых за один цикл, и тем самым уменьшить длительность процесса идентификации.
Как и в предыдущем случае, сначала генерируется число n как произведение двух больших чисел. Для того, чтобы сгенерировать открытый и секретный ключи для стороны А, сначала выбирают К
различных чисел V1, V2, ...,VK, где каждое Vi является квадратичным вычетом по модулю n. Иначе говоря, выбирают значение Vi таким, что сравнение
x2 Vi mod n
имеет решение и существует Vi-1 mod п. Полученная строка 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. Сторона А вычисляет
Перемножаются только те значения Si для которых b1 = 1. Например, если b1 = 1, то сомножитель S, входит в произведение, если же b1 = 0, то S1 не входит в произведение, и т.д. Вычисленное значение у отправляется стороне В.
4. Сторона В проверяет. Что
Фактически сторона В перемножает только те значения Vi для которых bi = 1. Стороны А и В повторяют этот протокол t раз, пока В не убедится, что А знает Sl, S2,..., SK
Вероятность того, что А может обмануть В, равна {1/2)Kt. Авроры рекомендуют в качестве контрольного значения брать вероятность обмана В равной (1/2)20 при К = 5 и t=4.
Пример. Рассмотрим работу этого протокола для небольших числовых значений [102]. Если n = 35 (n - произведение двух простых чисел 5 и 7), то возможные квадратичные вычеты будут следующими:
1: х2 1 (mod 35) имеет решения: х = 1, 6. 29, 34;
4: х2 4 (mod 35) имеет решения: х = 2, 12, 23, 33;
9: х2 9 (mod 35) имеет решения: х= 3, 17, 18, 32;
11: х2 11 {mod 35) имеет решения: х = 9, 16, 19. 26;
14: х2 14 (mod 35) имеет решения: х = 7, 28;
15: x215(mod35) имеет решения: х = 15, 20;
16: х2 16 (mod 35) имеет решения: х = 4, 11, 24, 31;
21: х2 21 (mod 35) имеет решения: х = 14, 21;
25: x225(mod35) имеет решения: х = 5, 30;
29: х2 29 (mod 35) имеет решения: х = 8, 13. 22, 27;
30: х2 30 (mod 35) имеет решения: х = 10, 25.
Заметим, что 14, 15, 21, 25 и 30 не имеют обратных значений по модулю 35, потому что они не являются взаимно простыми с 35. Следует также отметить, что число квадратичных вычетов по модулю 35, взаимно простых с n = p*q = 5*7=35 (для которых НОД (х, 35) =1), равно
(p-1)(q-1)/4 = (5-1)(7-1)/4 = 6
Составим таблицу квадратичных вачетов по модулю 35, обратных к ним значений по модулю 35 и их квадратных корней.
V
|
V-1
|
S = sqrt (V-1)
|
1
|
1
|
1
|
4
|
9
|
3
|
9
|
4
|
2
|
11
|
16
|
4
|
16
|
11
|
9
|
29
|
29
|
8
|
Итак, сторона А получает открытый ключ, состоящий из К=4 значений V:
[4,11,16,29].
Соответствующий секретный ключ, состоящий из К= 4 значений S:
[3 4 9 8].
Рассмотрим один цикл протокола.
1. Сторона А выбирает некоторое случайное число r = 16, вычисляет x=162mod35=11и посылает это значение х стороне В.
2. Сторона В отправляет стороне А некоторую случайную двоичную строку
[1,1,0,1].
3. Сторона А вычисляет значение
и отправляет это значение у стороне В.
4. Сторона В проверяет, что
Cтороны А и В повторяют этот протокол t раз, каждый раз с разным случайным числом г, пока сторона В не будет удовлетворена. ;
При малых значениях величин, как в данном примере, не достигается настоящей безопасности. Но если n представляет собой число длиной 512 бит и более, сторона В не сможет узнать ничего о секретном ключе стороны А, кроме того факта, что сторона А знает этот ключ.
В этот протокол можно включить идентификационную информацию [123].
Пусть I-некоторая двоичная строка, представляющая идентификационную, информацию о владельце карты (имя, адрес, персональный идентификационный номер, физическое описание) и о карте (дата окончания действия и т.п.). Эту информацию формируют в Центре выдачи интеллектуальных карт по заявке пользователя А.
Далее используют одностороннюю функцию f() для вычисления f(l,j), где j-некоторое двоичное число, сцепляемое со строкой I. Вычисляют значения
Vj = f(l, j)
для небольших значений j, отбирают К разных значений j, для которых Vj являются квадратичными вычетами по модулю n. Затем для отобранных квадратичных вычетов Vj вычисляют наименьшие
квадратные корни из Vj-1(mod n). Совокупность из К значений Vj образует открытый ключ, а совокупность из К значений Sj- секретный ключ пользователя А.
Проблема гроссмейстера
Вот как Алиса, даже не зная правил шахмат, может обыграть гроссмейстера. (Иногда это называется проблемой гроссмейстера.) Она посылает вызов Гарри Каспарову и Анатолию Карпову, предлагая играть в одно время, в одном и том же мести, но в раздельных комнатах. Она играет белыми против Каспарова и черными против Карпова. Ни один гроссмейстер не знает о другом.
Карпов, играя белыми, делает свой ход первым. Алиса записывает ход и идет в комнату к Каспарову. Играя белыми, она делает тот же ход на доске Каспарова. Каспаров делает свой первый ход черными. Алиса записывает ход, идет в комнату к Карпову и делает тот же ход. Это продолжается, пока она не выигрывает одну из партий, проигрывая другую, или обе партии кончаются вничью.
На самом деле Каспаров играет с Карповым, а Алиса просто посредник, повторяющий ходы одного гроссмейстера на доске другого. Однако, если Карпов и Каспаров не знают о присутствии друг друга, каждый из них будет поражен игрой Алисы.
Этот способ мошенничества может быть использовать против доказательства личности с нулевым знанием. Когда Алиса доказывает свою личность Мэллори, Мэллори может одновременно доказать Бобу, что он-то и есть Алиса.
Обман, выполненный мафией
Обсуждая свой протокол идентификации с нулевым знанием, Ади Шамир сказал: "Я могу ходить в принадлежащий мафии магазин хоть миллион раз подряд, а они все еще не смогут выдать себя за меня."
Вот как мафия сможет это сделать. Алиса ест в ресторанчике Боба, принадлежащем мафии. Кэрол делает покупки в дорогом ювелирном магазине Дэйва. Боб и Кэрол - мафиози, переговаривающиеся по потайному радиоканалу. Алиса и Дэйв не подозревают о мошенничестве.
Когда Алиса поела и собралась платить и доказывать свою личность Бобу, Боб подает сигнал Кэрол, что пора начинать. Кэрол выбирает бриллианты подороже и собирается доказывать свою личность Дэйву. Теперь, пока Алиса доказывает свою личность Бобу, тот подает сигнал Кэрол, и та выполняет тот же протокол с Дэйвом. Когда Дэйв задает вопрос по протоколу, Кэрол сообщает этот вопрос Бобу, а Боб задает его Алисе. Когда Алиса отвечает, Боб передает правильный ответ Кэрол. По сути, Алиса просто доказывает свою личность Дэйву, а Боб и Кэрол просто, находясь внутри протокола, передают сообщения туда-сюда. Когда протокол завершается, Алиса доказала свою личность Дэйву и заплатила за дорогие бриллианты (с которыми Кэрол теперь и исчезнет).
Обман, выполненный террористами
Если Алиса хочет объединиться с Кэрол, то они также могут провести Дэйва. В этом протоколе Кэрол - известная террористка. Алиса помогает ей въехать в страну. Дэйв - офицер-пограничник, Алиса и Кэрол общаются по тайному радиоканалу.
Когда Дэйв задает Кэрол вопросы в соответствии по протоколу с нулевым знанием, Кэрол передает их Алисе, которая и отвечает на вопросы. Кэрол повторяет эти ответы Дэйву. Carol recites these answers to Dave. По сути, Свою личность Дэйву доказывает Алиса, а Кэрол выступает в роли линии связи. Когда протокол завершается, Дэйв считает, что Кэрол - это Алиса, и разрешает ей въехать в страну. Спустя три дня Кэрол всплывает у правительственного здания вместе с микроавтобусом, набитом взрывчаткой.
Предлагаемые решения
Оба описанных мошенничества возможны, так как заговорщики используют тайный радиоканал. Одним из способов предотвратить мошенничество является проведение процедуры идентификации в клетке Фарадея, блокирующей электромагнитное излучение. В примере с террористом это гарантирует, что Кэрол не получит ответов от Алисы. В примере с мафией Боб может построить фальшивую клетку Фарадея в своем ресторане, но у ювелира-то клетка будет работать , и Боб и Кэрол не смогут обмениваться сообщениями. Для решения проблемы гроссмейстера Алиса должна сидеть на своем стуле до конца игры.
Тотас Бот (Thomas Both) и Иво Десмедт предложили другое решение, использующее точные часы. Если каждый этап протокола должен происходить в заданное время, у мошенников не останется времени для обмена информацией. В случае с проблемой гроссмейстера это соответствует предложению ограничить время обдумывания хода одной минутой - у Алисы не останется времени бегать из комнаты в комнату. В истории с мафией у Боб и Кэрол не хватит времени передавать друг другу ответы и вопросы.
Обман с несколькими личностями
Существуют и другие способы злоупотребить доказательствами идентичности с нулевым знанием. В ряде реализаций проверка при регистрации человеком своего ключа не производится. Следовательно, у Алисы может быть несколько закрытых ключей и, таким образом, несколько личностей. Это может здорово помочь ей, если она захочет мошенничать с налогами. Алиса также может совершить преступление и скрыться. В первых, она создает несколько личностей, одна из которых не используется. Затем, она использует эту личность для совершения преступления так, чтобы свидетель идентифицировал ее как эту личность. Затем, она немедленно прекращает пользоваться этой личностью. Свидетель знает личность преступника, но Алиса никогда больше не будет использовать эту личность - ее невозможно проследить.
Прокат паспортов
Алиса хочет поехать в Заир, но правительство этой страны не дает ей визы. Кэрол предлагает сдать свою личность Алисе "напрокат". Кэрол продает Алисе свой закрытый ключ и Алиса едет в Заир, выдавая себя за Кэрол.
Кэрол получает не только плату за свою личность, но и идеальное алиби. Она совершает преступление, пока Алиса находится в Заире. "Кэрол" доказала свою личность в Заире, как она могла совершить преступление дома?
Конечно, развязаны руки и у Алисы. Она может совершить преступление либо перед отъездом, либо сразу же после возвращения, около дома Кэрол. Сначала она покажет, что она - Кэрол (имея закрытый ключ Кэрол, ей не составит труда сделать это), затем она совершит преступление и убежит. Полиция будет искать Кэрол. Кэрол будет утверждать, что сдала свою личность напрокат Алисе, но кто поверит в такую невероятную историю?
Проблема в том, что Алиса доказывает не свою личность, а то, что ей известна некоторая секретная информация. Именно связь между этой информацией и личностью и служит предметом злоупотребления. Решение защищенных от воровства детей защитило бы от такого мошенничества, как и создание полицейского государства, в котором все граждане должны очень часто доказывать свою личность (в конце дня, на каждом углу и т.д.). Помочь решить эту проблему могут биометрические методы - отпечатки пальцев, снимки сетчатки глаза, запись голоса и т.п.
|
