Математические основы криптологии и криптографические методы и средс

Обычный протокол доказательства с нулевым разглашением конфиденциальной информации требует, чтобы Алиса и Боб после­ довательно повторили его шаги п раз. Можно попробовать выпол­ нять действия, предусмотренные этим протоколом, одновременно:

1.Алиса использует имеющуюся у нее информацию и п сгене­ рированных случайных чисел, чтобы свести труднорешаемую задачу

кп другим труднорешаемым задачам, изоморфным исходной задаче. Затем Алиса решает эти п новых задач.

2.Алиса задействует протокол предсказания бита для найден­ ных на шаге 1 п решений, чтобы впоследствии, если у Боба возник­ нет необходимость ознакомиться с этими решениями, Боб мог бы достоверно убедиться, что предъявленные Алисой решения действи­ тельно были получены им на шаге 1.

3.Алиса показывает п новых труднорешаемых задач Бобу.

4.Для каждой из п новых труднорешаемых задач Боб просит

Алису:

или а) - доказать, что она изоморфна исходной труднорешаемой задаче,

или б) - предоставить решение этой задачи, которое Алиса должна была найти на шаге 1, и доказать, что оно действительно яв­ ляется ее решением.

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

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

Постороннее лицо, не участвующее в выполнении шагов интерак­ тивного протокола доказательства с нулевым разглашением конфиден­ циальной информации, невозможно убедить в том, в чем в ходе реали­ зации протокола убеждается Боб, а именно - что Алиса действительно владеет конфиденциальной информацией. Чтобы преодолеть этот не­ достаток, потребуется применить неинтерактивный протокол, в котором вместо Боба используется однонаправленная функция:

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

2.Алиса задействует протокол предсказания бита для найден­ ных на шаге 1 п решений.

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

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

а) если этот бит равен 1, то Алиса доказывает, что исходная и /-я задачи изоморфны, или

б) если этот бит равен 0, то Алиса помещает в общедоступную базу данных решение i-й задачи, вычисленное на шаге 1.

5.Алиса передает в общедоступную базу данных все обязатель­ ства, которые были получены ею на шаге 2.

6.Боб, Владимир или любое другое заинтересованное лицо мо­ гут проверить правильность выполнения шагов 1-5 Алисой.

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

Роль Боба в этом протоколе исполняет однонаправленная функ­ ция. Если Алиса не знает решения труднорешаемой задачи, она все равно может выполнить действия, предусмотренные или пунктом а, или пунктом б шага 4 протокола, но отнюдь не обоими пунктами сразу. Поэтому, чтобы смошенничать, Алисе придется научиться предсказывать значения однонаправленной функции. Однако если функция действительно является однонаправленной, Алиса не смо­ жет ни догадаться, какими будут ее значения, ни повлиять на нее с тем, чтобы на ее выходе получилась нужная Алисе битовая после­ довательность.

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

Тогда Алиса может попытаться догадаться, на какой из этих пунктов падет выбор, и выполнить шаги 1-3 протокола. А если ее догадка неверна, она повторит все сначала. Именно поэтому в неинтерактивных протоколах необходим больший запас проч­ ности, чем в интерактивных. Рекомендуется выбирать п = 64 или даже п - 128.

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

В повседневной жизни людям регулярно приходится удостове­ рять свою личность. Обычно они делают это путем предъявления паспортов, водительских прав, студенческих билетов и других подобных документов. Такой документ обычно имеет некоторую ин­ дивидуальную отличительную особенность, которая позволяет одно­ значно связать его с определенным лицом. Чаще всего это фотогра­ фия, иногда - подпись, реже - отпечатки пальцев или рентгеновский снимок зубов. Можно ли делать то же самое с помощью криптогра­ фии?

Конечно. В этом случае для удостоверения личности Алисы ис­ пользуется ее тайный криптографический ключ. Применяя доказа­ тельство с нулевым разглашением конфиденциальной информации, Алиса может продемонстрировать любому, что знает свой тайный ключ, и тем самым однозначно идентифицировать себя. Идея цифро­ вой идентификации весьма заманчива и таит в себе массу разнооб­ разных возможностей, однако у нее есть ряд существенных недос­ татков.

Во-первых, злоумышленник Зиновий под фальшивым предло­ гом может попросить Алису предъявить свое цифровое удостовере­ ние личности. Одновременно с помощью современных средств связи Зиновий инициализирует процесс идентификации Алисы совсем в другом месте и будет переадресовывать все запросы из этого места Алисе, а данные им ответы - пересылать обратно. Например, Зино­ вий может связаться с ювелирным магазином и, выдав себя за Алису, оплатить из ее кармана весьма дорогую покупку.

Во-вторых, Зиновий может запросто обзавестись несколькими тайными ключами, а следовательно, и заиметь соответствующее Вис­ ло цифровых удостоверений личности. Одно из них он использует единственный раз для финансовой аферы и больше им пользоваться не будет. Свидетелем преступления станет лицо, которому Зиновий предъявит свое «одноразовое» удостоверение личности, однако Дока-

зать, что это был именно Зиновий, не удастся. Ведь предусмотри­ тельный Зиновий никогда не удостоверял таким образом свою лич­ ность прежде. Не станет он делать этого и впредь. А свидетель смо­ жет только показать, какое удостоверение личности было предъявле­ но преступником. Однозначно связать это удостоверение с лично­ стью Зиновия будет нельзя.

В-третьих, Алиса может попросить Зиновия одолжить на время его цифровое удостоверение личности. Мол, Алисе надо съездить в Соединенные Штаты, а поскольку она - бывший сотрудник совет­ ской разведки, работавший против США, американское правительст­ во наотрез отказывает ей во въездной визе. Зиновий с радостью со­ глашается: после отъезда Алисы он может пойти практически на лю­ бое преступление, поскольку обзавелся «железным» алиби. С другой стороны, ничто не мешает совершить преступление Алисе. Кто пове­ рит лепету Зиновия о том, что он одолжил свое цифровое удостове­ рение личности какому-то другому человеку?

Избавиться от перечисленных недостатков помогают дополни­ тельные меры предосторожности. В первом случае мошенничество стало возможным, поскольку Зиновий, проверяя цифровое удостове­ рение личности Алисы, мог одновременно общаться с внешним ми­ ром по телефону или радио. Если бы Зиновия поместили в экраниро­ ванную комнату без всяких средств связи, никакого мошенничества не было бы.

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

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

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

Протокол на основе задачи об изоморфизме графов

Пусть дана пара графов GX={U,ЕХ) и G2 =(U,E2) , здесь U -

множество вершин графа, а Ех и Е2 - множества ребер. Графы Gt

и G2 называют изоморфными, если существует перестановка <р вершин графа, которая переводит один граф в другой. Задача нахож­ дения такой перестановки и поиск ответа на вопрос о ее существова­ нии есть сложная математическая задача, не решаемая за полиноми­ альное время.

Итак, рассмотрим следующий протокол. Пусть ф - изоморфизм графов G, и G2, знанием которого обладает Алиса. Она доказывает это знание Бобу:

Алиса выбирает случайную перестановку я на множестве U

и передает граф я G\ Бобу.

Боб выбирает случайный бит а и пересылает его Алисе.

Если а = 1, то Боб пересылает Алисе перестановку я, иначе пе­ рестановку Я о ф .

При а = 0 Боб проверяет, является ли полученная перестановка изоморфизмом между G2H Н либо Gx и Н при а = 0 .

Данный протокол интересен только с теоретической точки зре­ ния. Применение его на практике невозможно по причине необходи­ мости передавать огромное количество данных.

Протокол Фейга - Фиата - Шамира (Feige - Fiat - Shamir)

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

В протоколе предполагается, что обе стороны заранее снабжены каким-то числом и = pq При этом разложение п на простые множи­

тели считается неизвестным для всех участников протокола. Доказы­

вающая сторона (Алиса) выбирает секретное число s, взаимно про­

стое с п, далее вычисляет значение o = ^2mod« и публикует значе­ ние о, объявляя его своим открытым ключом.

Как и все предыдущие, протокол Фейга - Фиата - Шамира со­ стоит в последовательном выполнении следующих итераций:

Алиса выбирает число z : 1< z < п - 1.

Алиса вычисляет и посылает проверяющей стороне (Бобу) чис­ ло x - z 2 mod/i.

Боб выбирает случайный бит а и пересылает его Алисе. Алиса пересылает Бобу число у:

Гz, если а = О

^[zyinodn, если а = 1

Боб проверяет что у Ф0 и у 2 = jcva(mod п) .

Рассмотрим последнюю проверку. Если a = 0, то у = z , у 2 - z2, xua = х, и проверка означает проверку на эквивалентность z2 и х по модулю п, что должно следовать из первого пункта протокола. Если a = 1, то у = zsmo&n, у 2 = z2s2 modп , xva = xv = xs2(mod«). И про­ верка означает проверку на эквивалентность по модулю п чисел г2^2 и xs2, что опять же должно вытекать из первого пункта.

Протоколы с нулевым разглашением на практике

Как было отмечено выше, многие другие криптографические протоколы идентификации не являются в точном математическом смысле протоколами с абсолютно нулевым разглашением. Однако совсем не этот фактор имеет в данном случае решающее значение.

Многие протоколы, в том числе протоколы на основе систем с открытым ключом, требуют огромного количества вычислений с обеих сторон. В то же время они обладают тем существенным пре­ имуществом, что для полной проверки доказываемого знания Доста­ точно одной итерации. В случае же с протоколами с нулевым раз­ глашением, вычисления, как правило, более просты. Но в тоже Лремя

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

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

2.4.8. Протокол обмена ключами. Схема Диффи - Хеллмана

В 1976 году американцы Уитфилд Диффи и Мартин Хеллман (W. Diffi, М. Heilman) в статье «Новые направления в криптографии» предложили новый принцип построения криптосистем, не требую­ щий не только передачи ключа принимающему сообщение, но даже сохранения в тайне метода шифрования. Этот метод получил назва­ ние «метод экспоненциального ключевого обмена» и является пер­ вой криптосистемой с открытым ключом. Метод запатентован, но срок действия патента истек 29 апреля 1997 года. Рассмотрим его основные положения.

Пусть абоненты А и В условились организовать секретную пе­ реписку между собой, используя секретный ключ, сгенерированный при помощи алгоритма Диффи--Хеллмана. Для этого они вместе выбирают два достаточно больших простых числа п и q так, чтобы q было примитивным элементом в GF(n). Эти два числа необязательно хранить в секрете. Абоненты А и В могут передать эти числа по от­ крытому каналу связи. Затем абоненты реализуют следующий алго­ ритм.

1. А выбирает случайное большое целое число а, вычисляет * = ^“mod п и посылает В число х.

2. В выбирает случайное большое целое число р, вычисляет

у= <7Pmod п и посылает А число .у.

3.А вычисляет ki= у “mod п.

4.В вычисляет кг - х pmod п.

Витоге А и В получили такие числа, что к\ = кг = 9 °pmod и. Ни­ кто из злоумышленников, имеющих доступ к этому открытому кана­ лу, не может определить эти значения, так как им известны n ,q ,x и у, но неизвестны а и р. Для получения а и р необходимо вычислить дискретный логарифм, что является трудной в вычислительном пла­ не задачей. Таким образом, величина к = к\ = кг может являться сек­ ретным ключом, который А и В вычислили независимо. В данном алгоритме выбор п и q существенно влияет на криптостойкость.

Пример 56. Пусть абоненты А и В условились организовать секретную переписку между собой, используя секретный ключ, сге­ нерированный при помощи алгоритма Диффи - Хеллмана. Тогда они вместе выбирают числа п = 67 и q = 11. Затем

1.А выбирает случайное целое число а =47, вычисляет jc=^“mod п =

=1 l47mod 67 = 2 и посылает В число 2.

2. В выбирает случайное целое число Р= 51, вычисляет у =* (/mod

и= 1151mod 67 = 3 и посылает Л число 3.

3.А вычисляет к\ =у “mod п = 347mod 67 = 27.

4.В вычисляет кг =х pmod п = 251mod 67 = 27.

В итоге А и В получили секретный ключ к = к\ = к2= 27.

Без дополнительных мер безопасности (введения сертификатов открытых ключей) рассмотренный метод ключевого обмена Уязвим с точки зрения атаки, известной под названием «человек посередине»

(main in the midlle attact).

Предположим, что злоумышленник С может не только подслу­ шивать сообщения между А и В, но также изменять, удалять И созда­ вать новые ложные сообщения. Тогда С может выдавать себя за А, что сообщающего В, и за В, что сообщающего А. Атака состоит

вследующем:

1.А посылает В свой открытый ключ. С перехватывает его и по­ сылает В свой собственный открытый ключ.