Осмысление различных протоколов и методов их построения привело в 1985–1986 гг. к появлению двух плодотворных математических моделей — интерактивной системы доказательства и доказательства с нулевым разглашением.
Математические исследования этих новых объектов позволили доказать несколько утверждений, весьма полезных при разработке криптографических протоколов.
Под интерактивной системой доказательства (P, V, S) понимают протокол взаимодействия двух абонентов: P (доказывающий) и V (проверяющий). Абонент P хочет доказать V, что утверждение S истинно. При этом абонент V самостоятельно, без помощи P, не может доказать утверждение S (поэтому V и называется проверяющим). Абонент P может быть и противником, который хочет доказать V, что утверждение S истинно, хотя оно ложно. Протокол может состоять из многих раундов обмена сообщениями между P и V и должен удовлетворять двум условиям:
1) полнота — если S действительно истинно, то абонент P почти наверняка убедит абонента V признать это;
2) корректность — если S ложно, то абонент P вряд ли убедит абонента V, что S истинно.
Здесь словами «почти наверняка» и «вряд ли» мы заменили точные математические формулировки, использующие понятие вероятности.
Подчеркнем, что в определении системы (P, V, S) не допускалось, что V может быть противником. А если V оказался противником, который хочет «выведать» у P какую-нибудь новую полезную для себя информацию об утверждении S? В этом случае P, естественно, может не хотеть, чтобы это случилось в результате работы протокола (P, V, S). Протокол (P, V, S), решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1 и 2, еще и следующему условию:
3) нулевое разглашение (или стойкость) — в результате работы протокола (P, V, S) абонент V не увеличит свои знания об утверждении S или, другими словами, не сможет извлечь никакой информации о том, почему S истинно.
Самое удивительное, что в 1991 году для широкого класса математических проблем (включающего так называемые NP-полные задачи) удалось доказать существование доказательств с нулевым разглашением. Впрочем, это доказано только в предположении, что существует односторонняя функция.
Приведем одно практическое применение теории доказательств с нулевым разглашением — «интеллектуальные карточки» (неподделываемые удостоверения личности, кредитные карточки и т.п.). В них вмонтирован микропроцессор, реализующий действия абонента P в протоколе, претендующем быть протоколом доказательства с нулевым разглашением (P, V, S). Здесь абонент P — владелец карточки, а абонент V — например, компьютер в банке или в проходной секретного учреждения. Подумайте, почему в таком случае можно обеспечить неподделываемость удостоверений личности и кредитных карточек.
Заключение
Вы прочли первую книгу по криптографии.
Если вам хочется подробней узнать историю криптографии, события и легенды, связанные с ней, то рекомендуем попытаться найти и прочесть упомянутые в этюде 1.4 книги Д. Кана и Т.А. Соболевой, а также любые номера журнала «Cryptology».
Если вы увлекаетесь программированием и вам захотелось самому реализовать какие-нибудь криптографические алгоритмы, то прежде всего полезно овладеть упомянутой в этюде 2.8 книгой Д. Кнута. Затем можно обратиться к одной из многочисленных книг для программистов по вопросам защиты информации в ЭВМ.
Если вас интересуют математические вопросы криптографии, то в первую очередь необходимо углубиться в те разделы математики, которые упомянуты в этюдах 2.1, 2.2, 2.3, 3.3, 3.4 и 3.8. Систематическое образование в этой области можно получить в любом из вузов, указанных во введении.
Что еще можно почитать о криптографии1. Т.А. Соболева. Тайнопись в истории России. (История криптографической службы России XVIII — начала XX в.). М., 1994.