Рассмотренные в предыдущих главах криптографические методы часто используются в качестве инструментов для решения других практически важны задач. Современная криптография позволяет решать проблемы, которые ранее считались в принципе неразрешимыми. Причем в настоящее время многие такие возможности криптографии используются в реальных компьютерных системах. Это и заключение коммерческих сделок в режиме удаленного взаимодействия участников, и осуществление денежных расчетов по сети, и проведение выборов по компьютерным сетям, и многое другое. Методы решения подобных задач обычно описываются в форме так называемых криптографических протоколов. Некоторые из них будут представлены в этой главе.
Обратим внимание читателя на то, что криптографические алгоритмы не просто предоставляют новые возможности пользователю (например, не нужно ходить в банк, можно произвести все необходимые операции со своего домашнего компьютера). Важно то, что они способны обеспечивать надежность значительно более высокую, чем традиционные механизмы. Например, если бумажную банкноту можно подделать, и случаи подделок весьма многочисленны, то электронную банкноту, созданную при помощи криптографических методов, подделать практически невозможно.
Рассмотрим следующую задачу, возникающую в некоторых криптографических приложениях. Снова участвуют Алиса и Боб. Алиса знает решение некоторой сложной задачи, она хочет убедить Боба в этом, однако так, чтобы Боб не узнал самого решения задачи. Т.е. в результате Боб должен убедиться в том, что Алиса знает решение, но не должен узнать что-нибудь о самом решении. На первый взгляд сама задача кажется абсурдной, а возможность ее решения фантастической! Для того чтобы лучше понять ситуацию, рассмотрим случай из жизни пиратов. Пусть, например, Алиса знает карту острова, где спрятан клад, а Боб капитан корабля, который может доставить ее на остров. Алиса хочет доказать, что карта у нее есть, не показывая ее Бобу (иначе Боб обойдется без Алисы, и весь клад достанется ему).
Такая же задача актуальна для компьютерных сетей в тех случаях, когда Боб (сервер или контроллер домена) должен принять решение о допуске Алисы к информации, хранящейся в сети, но при этом Алиса не хочет, чтобы кто-либо, прослушивающий канал передачи данных и сам сервер, получил какие-либо знания о ее пароле. Т.е. Боб получает «нулевое знание» о пароле (или карте) Алисы, но уверен, что у Алисы такой пароль (или карта) есть.
Итак, наша задача построить протокол «доказательства с нулевым знанием». При этом мы считаем, что каждый из участников может вести «нечестную» игру и пытаться обмануть другого.
В качестве сложной задачи, решение которой известно Алисе, мы рассмотрим задачу нахождения гамильтонова цикла в графе. Отметим, что эта задача NР-полная. Мы не приводим формального определения NР-полноты, которое может быть найдено, например, в [1]. Для читателя, не знакомого с этим определением, отметим только, что NР-полнота задачи неформально означает, что время решения задачи растет экспоненциально с ростом размера задачи (объема исходных данных).
Задача о нахождении гамильтонова цикла в графе
Рассматриваемая в данном разделе задача не просто предоставляет нам возможность описать одну схему построения протокола доказательства с нулевым знанием, но и имеет важное теоретическое значение. Блюм (Manuel Blum) показал, что, выражаясь неформально, любое математическое утверждение может быть представлено в виде графа, причем доказательство этого утверждения соответствует гамильтонову циклу в этом графе (см., например, [2б]). Поэтому наличие протокола доказательства с нулевым знанием для гамильтонова цикла означает, что доказательство любого математического утверждения может быть представлено в форме доказательства с нулевым знанием.
Определение 6.1. Гамильтоновым циклом в графе называется непрерывный путь, проходящий через все вершины графа ровно по одному разу.
П р и м е р б.1. Рассмотрим граф, изображенный на рис. б.1.
Путь, проходящий последовательно через вершины 8, 2, 4, б, 3, 5, 7, 1, представляет собой гамильтонов цикл. Действительно, в этом пути содержатся все вершины графа, и каждая вершина посещается только один раз.
Рис. 6.1. Граф с гамильтоновым циклом (8, 2, 4, 6, 3, 5, 7, 1)
Ясно, что если в графе G с n вершинами гамильтонов цикл существует, то при некоторой нумерации вершин он пройдет точно через вершины с последовательными номерами 1, 2, 3, ... , n. Поэтому путем перебора всех возможных нумераций вершин мы обязательно найдем гамильтонов цикл. Но количество возможных нумераций равно n!, и поэтому уже при умеренно больших n, например, при n 100, такой подход становится практически нереализуемым. Доказано, что задача нахождения гамильтонова цикла в графе является NР-полной. Мы уже говорили кратко о понятии NР-полноты. Неформально, NР-полнота рассматриваемой задачи означает, что для ее решения не существуют (точнее, неизвестны) алгоритмы существенно более быстрые, чем указанный метод перебора.
Нашей задачей будет построение криптографического протокола, с помощью которого Алиса будет доказывать Бобу, что она знает гамильтонов цикл в некотором графе G так, чтобы Боб не получил никаких знаний о самом этом цикле. Иными словами, Алиса будет предоставлять Бобу доказательство с нулевым знанием. Еще раз напомним читателю, что «нулевое знание» означает, что независимо от числа реализаций протокола доказательства Боб будет располагать точно такими же сведениями о гамильтоновом цикле, какие он мог бы получить, просто изучая представленный ему граф G.
Итак, допустим, что Алиса знает гамильтонов цикл в графе G. Теперь она может это доказывать Бобу и всем, кто имеет граф G, с помощью описываемого ниже протокола. Алиса может использовать это доказательство, например, для идентификации своей личности. Но прежде чем мы перейдем к описанию протокола, договоримся о некоторых обозначениях.
Мы будем обозначать графы буквами G, Н, F, понимая под этим одновременно соответствующие матрицы смежности. Элемент матрицы Нij = 1, если в графе Н есть ребро, соединяющее вершины i и j; Нij = 0 в противном случае. Символом || будем обозначать конкатенацию (сцепление) двух чисел, точнее, двоичных слов, им соответствующих. Нам понадобится шифр с открытым ключом. Вообще говоря, это может быть любой шифр, но для определенности будем использовать шифр RSA (разд. 2.б). Будем считать, что Алиса сформировала систему RSA с открытыми параметрами N и d. Важно, что зашифрованные в этой системе сообщения может расшифровать только Алиса и больше никто.
Протокол доказательства состоит из следующих четырех шагов (пояснения будут даны ниже).
Шаг 1. Алиса строит граф Н, являющийся копией исходного графа G, где у всех вершин новые, случайно выбранные номера. На языке теории графов говорят, что Н изоморфен G. Иными словами, Н получается путем некоторой перестановки вершин в графе G (с сохранением связей между вершинами). Алиса кодирует матрицу Н, приписывая к первоначально содержащимся в ней нулям и единицам случайные числа r по схеме . Затем она шифрует элементы матрицы Н, получая зашифрованную матрицу F,
. Матрицу F Алиса передает Бобу.
Шаг 2. Боб, получив зашифрованный граф F, задает Алисе один из двух вопросов.
1. Каков гамильтонов цикл для графа Н?
2. Действительно ли граф Н изоморфен G?
Шаг З. Алиса отвечает на соответствующий вопрос Боба.
1. Она расшифровывает в F ребра, образующие гамильтонов цикл.
2. Она расшифровывает F полностью (фактически передает Бобу граф ) и предъявляет перестановки, с помощью которых граф Н был получен из графа G.
Шаг 4. Получив ответ, Боб проверяет правильность расшифровки путем повторного шифрования и сравнения с F и убеждается либо в том, что показанные ребра действительно образуют гамильтонов цикл, либо в том, что предъявленные перестановки действительно переводят граф G в граф Н.
Весь протокол повторяется t раз.
Обсудим вначале кратко несколько вопросов по построению протокола.
1. Зачем Алиса строит изоморфный граф? Если бы она этого не делала, то Боб, получив ответ на свой вопрос номер один, узнал бы гамильтонов цикл в графе G.
2. Зачем Алиса кодирует матрицу Н? С этим приемом мы уже встречались при шифровании цветов вершин графа. Дело в том, что невозможно зашифровать непосредственно нули и единицы (с помощью шифра RSA они вообще не шифруются). Даже если заменить их на какие-то произвольные числа а и b, то мы получим всего два различны шифротекста, и Бобу не со-ставит труда понять, какой из них какому числу соответствует. Т.е. структура графа не будет скрыта. Здесь мы сталкиваемся
с типичной ситуацией, когда требуется использовать так называемый рандомизированный шифр. И такой шифр строится путем добавления случайны чисел в матрицу Н перед шифрованием. Закодированная матрица точно также задает граф (нечетность числа означает наличие ребра, четность его отсутствие), но после шифрования
структура графа полностью скрывается (мы используем известное свойство шифра RSA он полностью скрывает четность числа [22]).
3. Зачем Боб задает два вопроса? Если бы он задавал только вопрос номер один, который по смыслу протокола является основным, то Алиса, не зная в действительности гамильтонова цикла в графе G, могла бы предъявить Бобу совсем другой граф с таким же количеством вершин и искуственно заложенным в него гамильтоновым циклом. Поэтому Боб иногда просит Алису доказать изоморфизм графов Н и G. Важно, что Алиса не знает заранее, какой из двух вопросов задаст Боб.
4. Почему Боб не может задать сразу двух вопросов? В этом случае он узнал бы гамильтонов цикл в G, так как ему был бы показан гамильтонов цикл в Н и правило перехода от Н к G.
5. Зачем Боб проверяет правильность расшифровки? Если бы он этого не делал, то Алиса на четвертом шаге могла бы предоставить ему «выгодную» для себя информацию, а не ту, которую она посылала ему на втором шаге.
Более точно основные детали протокола обосновываются в ходе доказательства двух основных утверждений.
Утверждение б.1. Вероятность обмана при t реализациях протокола не превосходит 2-t.
Д о к а з а т е л ь с т в о. Вначале покажем, что вероятность обмана в одной реализации протокола равна 1/2. Заметим, что если Алиса действительно знает гамильтонов цикл в графе G, то она может правильно ответить на любой вопрос Боба. Если же она не знает гамильтонов цикл, то самое большее, что она может сделать, это подготовиться к ответу на первый либо на второй вопрос. В ожидании первого вопроса, она создает новый граф с искусственно заложенным в него гамильтоновым циклом. Но в этом случае она не сможет доказать его изоморфизм графу G . В ожидании второго вопроса, она строит граф, изоморфный графу G . Но в этом случае она не сможет показать в нем гамильтонов цикл. Таким образом, вероятность успешности обмана равна вероятности угадывания номера вопроса. В предположении, что Боб задает оба вопроса с одинаковыми вероятностями, мы получаем, что вероятность обмана равна 1/2.
Так как Боб прекращает игру при первом же неправильном ответе, вероятность обмана при t реализациях протокола не превосходит (1/2)t.
Утверждение б.2. Представленный протокол реализует доказательство с нулевым знанием.
Д о к а з а т е л ь с т в о. Чтобы доказать, что Боб не получает никаких знаний в ходе реализации протокола, достаточно показать, что все, что он получает от Алисы, он мог бы получить сам, не вступая с ней ни в какое общение.
Рассмотрим вначале второй вопрос Боба. В ответ на этот вопрос он получает граф, изоморфный графу G. Но он сам мог строить сколько угодно изоморфны графов, и то, что присылает ему Алиса, это просто один из них.
Случай с первым вопросом не столь очевиден. В ответ на первый вопрос Боб получает гамильтонов цикл в графе, изоморфном графу G. На первый взгляд может показаться, что это дает Бобу какую-то информацию. Однако это не так. Заметим, что если в G есть гамильтонов цикл, то при некоторой нумерации вершин существует изоморфный граф, который задается матрицей смежности вида
(6.1)
где * означает неопределенность в наличии или отсутствии ребра. Т.е. при такой нумерации гамильтонов цикл проходит через вершины в порядке возрастания номеров. Изменяя нумерацию вершин, Боб может получать из (б.1) всевозможные изоморфные матрицы. Когда Алиса, отвечая на его первый вопрос, открывает гамильтонов цикл, Боб видит как раз одну из таких матриц.
Таким образом, Боб не получает от Алисы никакой информации, которую он не мог бы получить сам.
Рассмотрим пример, иллюстрирующий все основные этапы описанного протокола.
П р и м е р б.2. Возьмем в качестве основного граф G, изображенный на рис. б.1. Его матрица смежности имеет вид
В матрице с помощью показан гамильтонов цикл. Алиса выбирает некоторую случайную нумерацию вершин, скажем, 7, 4, 5, 3, 1, 2, 8, б, и получает изоморфный граф
Для шифрования матрицы будем использовать систему RSA с параметрами N = 55, d = 3. Вначале закодируем матрицу Н. В рамках данного примера просто припишем слева к каждому элементу матрицы выбираемую случайно с равными вероятностями цифру из множества {1, 2, 3, 4, 5}:
Теперь мы шифруем матрицу , возводя каждый ее элемент в куб по модулю 55:
(При внимательном просмотре матрицы F может показаться, что использованный нами шифр плохо скрывает исходную матрицу Н. Это объясняется тем, что, во-первых, модуль 55 слишком мал и, во-вторых, в матрице много чисел, не взаимно просты с модулем. Для реальных систем RSA, где N большое число, такая ситуация практически исключена.)
Боб получает матрицу F и задает один из двух вопросов. Если он просит доказать изоморфизм графов, то Алиса просто посылает ему кодированную матрицу и использованную нумерацию 7, 4, 5, 3, 1, 2, 8, б. Боб проверяет соответствие матрицы
матрице F, т.е.выполнение равенств 503 mod 55 = 40, 203 mod 55 = 25 и т.д. Из матрицы
Боб получает граф Н (просто отбросив старшую десятичную цифру). Затем он переставляет вершины графа G в соответствии с полученной нумерацией, как это делала Алиса, и убеждается в том, что Н и G один и тот же граф.
Если Боб просит показать ему гамильтонов цикл, то Алиса посылает ему соответствующий список (закодированных) ребер графа Н: (1, 5, 21), (5, 7, 41), (7, б, 21), ... , (3, 1, 41). Каждый элемент содержит номера вершин и код ребра. Боб проверяет соответствие указанных в списке ребер матрице F, например, 213 mod 55 = 21 = F1,5, 413 mod 55 = 06 = F5,7 и т.д. Затем он убеждается, что указанный в списке путь проходит через все вершины графа по одному разу.
Во многих странах люди оплачивают покупки при помощи электронных карточек, заказывают авиабилеты через Интернет, покупают самые разнообразные товары в Интернет-магазинах. Сведения о покупках накапливаются в магазинах и банках. Поэтому появилась новая проблема, иногда называемая «проблема Большого Брата».
Суть проблемы состоит в том, что исчезает анонимность процесса покупки, т.е. информация о покупках любого человека может стать известной третьим лицам и использоваться против него. Например, сведения о покупке билета на поезд или самолет могут представлять интерес для преступников, информация о закупках алкогольных напитков политическим деятелем может быть использована против него его противниками и т.д., и т.п.
Поэтому возникла идея разработать такие схемы электронных платежей, которые сохраняли бы анонимность покупателя в той же степени, что и при расчете наличными деньгами. Такие протоколы называются электронными или цифровыми деньгами (digital cache), что подчеркивает их основное свойство они обеспечивают ту же степень анонимности, что и обычные деньги. Некоторые схемы уже используются в реальной жизни. Описываемая ниже схема была предложена Д. Чаумом (David Chaum), см. [2, 22].
Мы рассмотрим две «плохие» схемы, а затем «хорошую», чтобы было легче понять суть метода.
Вначале дадим более точную постановку задачи. Имеются три участника: банк, покупатель и магазин. Покупатель и магазин имеют соответствующие счета в банке, и покупатель хочет купить некоторый товар в магазине. Покупка осуществляется в виде трехступенчатого процесса:
1) покупатель снимает нужную сумму со своего счета в банке;
2) покупатель «пересылает» деньги в магазин;
3) магазин сообщает об этом в банк, соответствующая сумма денег зачисляется на счет магазина, а покупатель забирает товар(или последний ему доставляется).
Наша цель разработать такую схему, чтобы
• она была надежна;
• чтобы банк не знал, кто купил товар, т.е. была сохранена ано-нимность обычных денег.
Опишем первую «плохую» схему (она базируется на RSA). Банк имеет следующую информацию: секретные числа Р, Q, с и открытые
(6.2)
Допустим, покупатель решил израсходовать некоторую заранее оговоренную с банком сумму (например, 100$). (Мы сначала рассмотрим случай, когда может использоваться «банкнота» только одного номинала (скажем, 100$).) Покупатель высылает в банк число n, которое будет номером банкноты (обычно требуется, чтобы генерировалось случайное число в промежутке [2, N — 1]) .
Банк вычисляет число
(6.3)
и формирует банкноту , которую возвращает покупателю, предварительно уменьшив его счет на 100$. Параметр s в банкноте это подпись банка. Никто не может подделать подпись, так как число с секретно.
Покупатель предъявляет банкноту в магазине, чтобы купить товар. Магазин отправляет эту банкноту в банк для проверки. Прежде всего, банк проверяет правильность подписи (эту проверку мог бы сделать и магазин, используя открытые ключи банка). Но кроме этого банк хранит все номера возвратившихся к нему банкнот и проверяет, нет ли числа n в этом списке. Если n есть в списке, то платеж не принимается (кто-то пытается использовать банкноту повторно), и банк сообщает об этом магазину. Если же все проверки прошли успешно, то банк добавляет 100$ на счет магазина, а магазин отпускает товар покупателю.
Недостаток этой схемы отсутствует анонимность. Банк, а также все, кто имеет доступ к открытым линиям связи, могут запомнить, какому покупателю соответствует число n, и тем самым выяснить, кто купил товар.
Рассмотрим вторую «плохую» схему, которая уже обеспечивает анонимность. Эта схема базируется на так называемой «слепой подписи».
Снова покупатель хочет купить товар. Он генерирует число n, которое теперь не будет посылаться в банк. Затем он генерирует случайное число r, взаимно простое с N, и вычисляет число
(6.4)
Число покупатель отправляет в банк.
Банк вычисляет число
(6.5)
и отправляет обратно покупателю (не забыв при этом снять 100$ с его счета).
Покупатель находит число r-1 mod N и вычисляет
(6.6)
Заметим, что с учетом соотношений (б.5), (б.4) и (б.2) имеем
т.е. мы получили подпись банка к n (см. (б.3)), но самого числа n ни банк, ни кто либо другой не видел. Вычисление (б.5) называется «слепой подписью», так как реальное сообщение (n) подписывающий не видит и узнать не может.
Таким образом, покупатель имеет число n, которое никому не известно и никогда не передавалось по каналам связи, и подпись банка s, совпадающую с вычисленной по (б.3). Покупатель формирует банкноту и действует так же, как в первой «плохой» схеме. Но теперь никто не знает, кому соответствует эта банкнота, т.е. она стала анонимной, как обычная бумажная банкнота.
Действия магазина и банка после предъявления покупателем банкноты ничем не отличаются от действий, описанных в первой схеме.
Почему же данная схема плохая? Она имеет следующий недостаток: можно сфабриковать фальшивую банкноту, если известны хотя бы две настоящие. Делается это так. Путь злоумышленник (будь то покупатель или магазин) имеет две настоящие банкноты и
. Тогда он легко сможет изготовить фальшивую банкноту
, вычислив числа
Действительно,
(6.7)
т.е. s3 является правильной подписью для n3, и у банка нет никаких оснований, чтобы не принять эту фальшивую банкноту (он просто не сможет отличить ее от подлинной). Это так называемое «мультипликативное свойство» системы RSA.
Опишем, наконец, «хорошую» схему, в которой устранены все недостатки первых двух. В одном варианте такой схемы используется некоторая односторонняя функция
(f вычисляется легко, а обратная к ней функция f-1 очень трудно). Функция f не секретна и известна всем (покупателю, банку и магазину).
Банкнота теперь определяется как пара чисел , где
т.е. подписывается не n, а значение f (n).
Покупатель генерирует n (никому его не показывая), вычисляет f (n), подписывает в банке при помощи «слепой подписи» число f (n) и формирует банкноту . Эта банкнота обладает всеми хорошими свойствами, как и во второй схеме, в то же время подделать такую банкноту невозможно, так как невозможно вычислить f -1. Для проверки подписи (т.е. подлинности банкноты) нужно вычислить f (n) и убедиться, что
Заметим, что при выборе односторонней функции нужно проявлять осторожность. Например, функция , которая действительно является односторонней, не годится для рассматриваемого протокола. Читатель может проверить, что банкноты, созданные с использованием такой функции, будут по-прежнему обладать мультипликативным свойством (б.7). На практике в качестве f (n) обычно используются криптографичесие хеш-функции, описываемые в главе 4.
Все остальные действия магазина и банка остаются такими же, как и в ранее описанных схемах.
Есть еще один, более простой, способ борьбы с мультипликативным свойством системы RSA - внесение избыточности в сообщение. Допустим, что длина модуля N - 1024 бита. Такой же может быть и длина числа n. Будем записывать (случайно выбираемый) номер банкноты только в младшие 512 бит n, а в старшие 512 бит n запишем некоторое фиксированное число. Это фиксированное число может нести полезную информацию, такую, как номинал банкноты и наименование банка (с помощью 512 бит можно представить строку из б4 символов ASCII). Теперь банк при предъявлении ему банкноты будет обязательно проверять наличие фиксированного заголовка в параметре n и отвергать банкноту в случае его отсутствия. Вероятность того, что при перемножении двух чисел по модулю N результат совпадет с ними в 512 битах пренебрежимо мала. Поэтому получить фальшивую банкноту по формуле (б.7) не удастся.
П р и м е р б.3. Пусть в качестве секретных параметров банка выбраны числа Р = 17, Q = 7, с = 77. Соответствующие им открытые параметры будут N = 119, d = 5. Для исключения возможности подделки банкнот их допустимыми номерами считаются только числа, состоящие из двух одинаковых десятичны цифр, например, 11, 77, 99.
Когда покупатель хочет получить банкноту, он вначале случайным образом выбирает ее номер (из числа допустимы). Предположим, он выбрал n = 33. Затем он находит случайное число r, взаимнопростое со 119. Допустим, r = 67, (67, 119) = 1. Далее, покупатель вычисляет
Именно число 52 он посылает в банк.
Банк списывает со счета покупателя 100$ и отправляет ему число
Покупатель вычисляет r-1 = 67-1 mod 119 = 16 и s = 103 • 16 mod 119 = 101 и получает платежеспособную банкноту
Эту банкноту он приносит (или посылает) в магазин, чтобы купить товар.
Магазин предъявляет банкноту в банк. Банк делает следующие проверки:
1) номер банкноты (n = 33) состоит из двух одинаковых десятичных цифр (т.е. содержит требуемую избыточность);
2) ранее банкнота с таким номером не предъявлялась;
3) подпись банка верна, т.е. 335 mod 119 = 101.
Так как все проверки прошли успешно, банк зачисляет 100$ (это фиксированный номинал банкноты) на счет магазина, о чем ему и сообщает. Магазин отпускает товар покупателю.
В завершение разберем еще две проблемы, возникающие в связи с рассмотренной схемой электронных денег.
В представленной схеме независимо действующие покупатели или даже один покупатель, который не помнит номеров ранее использованных им банкнот, могут случайно сгенерировать две или более банкноты с одинаковыми номерами. По условиям протокола банк примет к оплате только одну из таких банкнот (ту, которая будет предъявлена первой). Однако примем во внимание размеры чисел, используемых в протоколе. Если номер банкноты число длиной 512 бит и покупатели генерируют его действительно случайным образом, то вероятность получения когда либо двух одинаковых номеров пренебрежимо мала.
Вторая проблема состоит в том, что в рассмотренной схеме используются только банкноты одного фиксированного номинала, что, конечно, неудобно для покупателя. Решение проблемы использования банкнот разного номинала возможно следующим образом. Банк заводит несколько пар (сi, di), обладающих свойством (б.2), и объявляет, что d1 соответствует, например, 1000 руб., d2 - 500 руб. и т.д. Когда покупатель запрашивает слепую подпись в банке, он дополнительно сообщает, какого номинала банкноту он хочет получить. Банк снимает с его счета сумму, равную указанному номиналу, и формирует подпись, используя соответствующее секретное число сi. Когда впоследствии банк получает подписанную банкноту, он использует для проверки подписи по очереди числа d1, d2 и т.д. Если подпись оказалась верна для какого-то di, то принимается банкнота i-го номинала. В случае, когда параметр n банкноты содержит фиксированный заголовок с указанием ее номинала, задача проверки подписи облегчается банк сразу использует нужный ключ di.
В данном разделе мы рассмотрим криптографически стойкий протокол, в результате реализации которого два абонента сети А и В взаимно идентифицируют друг друга (т.е. А убеждается в том, что взаимодействует с В, а В в том, что он взаимодействует с А) и формируют общий секретный ключ, который может использоваться в дальнейшем для шифрования передаваемых ими сообщений. В реальной жизни в качестве А и В могут выступать пользователь и компьютерная система или две различные компьютерные системы суть описываемого ниже протокола от этого не меняется.
В процессе описания мы рассматриваем различные, все более изощренные типы атак и средства защиты от них. Так мы уже рассматривали ранее (см. разд. 2.1 и 2.2) подходы к решению задачи идентификации и установления ключа. Однако мы исходили из того, что противник может только прослушивать информацию, передаваемую по открытому каналу. Но в современных сетях передачи данных, например в Интернете, информация от одного пользователя передается другому через множество промежуточных узлов (маршрутизаторы, шлюзы, почтовые серверы и т.д.), не контролируемых этими пользователями. В результате противник, обосновавшийся на одном таком промежуточном узле, может не только прослушивать информацию, т.е. играть чисто пассивную роль, но и осуществлять активные воздействия, например, изменять, добавлять или удалять сообщения.
Разберем, например, типичную атаку на систему Диффи-Хеллмана в сети связи с активным противником. Алиса выбирает свое секретное число ХА и посылает Бобу . Боб выбирает свое секретное число ХB и посылает Алисе
. Однако Ева перехватывает эти числа и посылает вместо них и Алисе, и Бобу
, где ХЕ ее число. Все эти числа выглядят как совершенно случайные, так что ни Алиса, ни Боб ничего не подозревают. В результате Алиса формирует ключ
а Боб ключ
. Оба этих ключа могут быть легко вычислены и Евой. Теперь, когда Алиса посылает Бобу сообщение, зашифрованное с ключом КА, Ева расшифровывает его, снова шифрует с ключом КВ и отправляет Бобу. Аналогично Ева действует и при передаче сообщений в обратном направлении. Боб и Алиса взаимодействуют, как им кажется, в защищенном режиме, но на самом деле Ева читает все их сообщения.
Такая атака становится невозможной, если Алиса и Боб не передают открытые ключи (в системе Диффи-Хеллмана это и
) по каналу связи, а выбирают их из некоторой таблицы или справочника, который был получен ими ранее из «надежного» источника (как это предполагалось в разд. 2.2).
Вообще, большинство криптосистем с открытыми ключами требуют наличия некоторой организационной структуры, занимающейся сертификацией открыты ключей. Такая структура может, например, выглядеть следующим образом. В сети, которой принадлежат Алиса и Боб, имеется «честный» пользователь Трент (абонент Т), который заинтересован только в том, чтобы сеть работала надежно (скорее всего это не человек, а хорошо охраняемый компьютер, работающий по жестко заложенной программе). Трент располагает какой-либо надежной криптосистемой (например, RSA с длиной модуля порядка 10000 бит) с соответствующими открытыми ключами и выполняет всего две функции:
1) он добавляет в свою базу данных информацию об открытом ключе пользователя, присылаемую в виде сообщения, зашифрованного с использованием открытого ключа Трента;
2) он сообщает информацию о чьем-либо открытом ключе, снабженную своей подписью.
Открытые ключи Трента доводятся до сведения всех пользователей каким-либо способом, исключающим вмешательство Евы. Например, они публикуются в виде рекламного сообщения в газете. Теперь Алиса, вычислив свой открытый ключ, формирует сообщение из своего имени и этого ключа, шифрует его с использованием открытого ключа Трента и посылает Тренту (никто кроме Трента не может расшифровать это сообщение). Боб, когда ему нужен открытый ключ Алисы, посылает запрос Тренту, и Трент присылает ему подписанный ключ Алисы (никто не может подделать подпись Трента). Боб проверяет подпись Трента, используя его открытый ключ, и принимает ключ Алисы как достоверный. Таким образом, каждый пользователь сети получает достоверную информацию об открыты ключах других пользователей, и Ева никак не может вмешаться в этот процесс.
Итак, если Алиса и Боб пользуются достоверными открытыми ключами, то схема диффи-Хеллмана решает задачу установления секретного ключа. Однако она непосредственно не обеспечивает идентификацию пользователей. Действительно, если вместо Алисы выступала Ева, которая не знает секретного ключа Алисы, то у них с Бобом будут сформированы различные секретные ключи, но это может выясниться только позднее, на стадии обмена данными, когда Боб, например, не сможет расшифровать переданное ему сообщение или обнаружит, что «Алиса» не понимает того, что он посылает ей. Часто требуется обеспечить явную идентификацию, чтобы по завершении протокола стороны точно знали, кто есть кто.
У схемы диффи-Хеллмана есть и другой недостаток: секретный ключ, который формируют Алиса и Боб, будет всегда один и тот же, пока они не поменяют открытые ключи. Но смена открытых ключей это относительно долгий процесс (например, обычно требуется оповестить всех пользователей сети об изменении какого-то открытого ключа, чтобы они могли скорректировать информацию в своих справочниках). Хотелось бы иметь протокол, обеспечивающий оперативное создание каждый раз различных, случайно выбираемых секретных ключей.
Решение состоит в использовании какого-либо шифра с открытым ключом для передачи секретных ключей. Обозначим шифр сообщения х, построенный с использованием открытого ключа пользователя А, через РА(х). (Например, РА(х) может быть шифром RSA или шифром Эль-Гамаля. В случае RSA , где пара чисел dА и NА представляет собой открытый ключ пользователя А.) Все, кто знает открытый ключ А, могут вычислить РА(х) для сообщения х. В то же время только А, знающий соответствующий секретный ключ, может получить х из у = РА(х). Аналогично (РВ(х)) будем обозначать шифр, построенный с помощью открытого ключа пользователя В. Символом ||, как и ранее, будем обозначать конкатенацию чисел. Мы опишем протокол поэтапно, чтобы не «утопить» читателя в деталях.
Напомним, что мы решаем следующую задачу: Алиса и Боб хотят взаимно идентифицировать друг-друга и установить общий секретный ключ. Рассмотрим вначале следующий (плохой) протокол, состоящий из трех шагов, чтобы обсудить несколько важных вопросов.
Шаг 1. Алиса придумывает секретный ключ k1, шифрует его, используя открытый ключ Боба, и посылает Бобу:
(6.8)
Шаг 2. Боб расшифровывает k1, снова шифрует его, используя открытый ключ Алисы, и посылает Алисе:
(6.9)
Шаг З. Алиса расшифровывает k1 и сравнивает его с тем, который она придумала на шаге 1.
Что мы имеем в результате реализации этого протокола? Во-первых, Алиса и Боб получили общий секретный ключ k1, неизвестный Еве (Ева не может расшифровать ни РВ (k1), ни РA (k1)). Во-вторых, Алиса получила криптографически стойкую идентификацию Боба, так как никто кроме него не смог бы расшифровать k1. Очевидно, что в данном протоколе Боб не получает никакой идентификации Алисы (сообщение (б.8) мог послать кто угодно). Он мог бы провести симметричный протокол со своей стороны:
(6.10)
(6.11)
и получить такую идентификацию. Проблема, однако, здесь состоит в логической независимости двух протоколов, в результате чего нет гарантии, что оба протокола проводятся одними и теми же участниками.
Но есть и более тонкая проблема. Алиса может использовать описанный протокол для вскрытия криптосистемы Боба! Делается это так. Допустим, Алиса перехватила какое-то сообщение у, предназначенное для Боба, т. е. у = Рв (х). Она притворяется, что хочет войти в систему Боба, и запускает протокол (б.8), (б.9). Однако вместо РВ (k1) она передает Бобу сообщение у. Так как k1 произвольно выбранное число, то Боб не может ничего заподозрить. Он честно выполняет свой шаг в протоколе и расшифровывает для Алисы х !
Урок, который следует отсюда извлечь, следующий: никогда ни для кого не следует расшифровывать случайные числа. Это может повредить вашей безопасности. Средство борьбы с такой «опасной» случайностью внесение избыточности в сообщения, например, введение какого-либо элемента, известного получателю и ожидаемого им. В частности, в (б.8) Алиса могла бы послать свое имя. Она могла бы построить сообщение, отведя 512 бит под случайное число k1 и 512 бит под свое имя, адрес, фрагмент открытого ключа и другую легко проверяемую информацию (будем обозначать все это вместе через ), и послать Бобу
. В этом случае Боб не стал бы посылать Алисе сообщение х, так как его соответствующие 512 бит наверняка не содержали бы
.
Все вышеизложенное приводит нас к следующему протоколу Нид-хама—Шредера (Needham, Schroeder, см., например, [23]), который полностью решает поставленную в начале раздела задачу.
Шаг 1. Алиса выбирает случайное число k1, объединяет его со своей открытой информацией и посылает Бобу
(6.12)
Шаг 2. Боб расшифровывает (6.12) и убеждается в том, что полученное сообщение содержит открытую информацию Алисы . Затем он выбирает случайное число k2, объединяет его с k1 и посылает Алисе
(6.13)
Шаг З. Алиса расшифровывает (6.13) и убеждается в том, что полученное сообщение содержит k1. Это является для нее надежным признаком идентификации Боба, так как никто другой не мог бы извлечь k1 из (6.12). Алиса посылает Бобу
(6.14)
Шаг 4. Боб расшифровывает (6.14) и убеждается в том, что он получил k2. Это является для него надежным признаком идентификации Алисы, так как никто другой не мог бы извлечь k2 из (6.13).
Теперь Алиса и Боб могут сформировать из k1, k2 общий ключ, например, k = k1 k2, где
побитовая сумма по модулю 2, или использовать k1 и k2 по-отдельности для шифрования входящих и исходящих сообщений.
П р и м е р б.4. Пусть в некоторой сети используется шифр Эль-Гамаля с открытыми параметрами р = 107, g = 2. Пользователи А И В имеют открытые ключи dA = 58, dB = 28, Которым соответствуют секретные СА = 33, СВ = 45. Рассмотрим реализацию протокола Нидхама-Шредера для взаимной идентификации пользователей А и В и установления общего секретного ключа. Учитывая небольшую величину модуля р в нашем примере, будем использовать в качестве идентификаторов пользователей одну цифру в десятичной записи, пусть = 1,
= 2, и секретный ключ будем получать также в виде одной десятичной цифры.
На первом шаге протокола А выбирает секретный ключ, пусть k1 = 3, и формирует сообщение . Это сообщение шифруется шифром Эль-Гамаля на открытом ключе пользователя В:
Пара чисел (26, 47) и есть тот шифротекст, который необходимо послать В. В использованных при описании протокола обозначениях = (26,47) и
На втором шаге протокола В расшифровывает (26, 47), используя свой секретный ключ:
В убеждается, что младшая цифра содержит идентификационный номер пользователя А и извлекает k1 = 3. Затем он выбирает свое секретное число, пусть k2 = 7, формирует сообщение m == 37 и шифрует его на открытом ключе А:
Пара чисел (63, 18) - это то, что нужно послать А. Т.е. = (63, 18) и
На третьем шаге А расшифровывает (63, 18) :
А убеждается в том, что старшая цифра содержит k1 = 3 и извлекает k2 = 7. Теперь А шифрует k2 для В :
и посылает В
На четвертом шаге В расшифровывает (82, 49) :
В убеждается в том, что он получил свое число k2 = 7.
Теперь А и В могут сформировать общий ключ по заранее оговоренной схеме, например,
6.1. В системе электронных денег выбраны секретные параметры банка Р = 17, Q = 7, с = 77, а соответствующие им открытые параметры N = 119, d = 5. Сформировать электронные банкноты со следующими номерами:
1.1. а. k = 17. б. k = 27.
1.2. а. ПРИВЕТ (k = 5). б. ВЕСНА (k = 20).
2.1. а. 5 = 5, 16 = 6, 27 = 7, −4 = 6, −13 = −3 = 7, 3 + 8 = 1, 3 − 8 = 5, 3 · 8 = 4, 3 · 8 · 5 = 4 · 5 = 0 (mod 10).
b. 5 = 5, 16 = 5, 27 = 5, −4 = 7, −13 = −2 = 9, 3 + 8 = 0, 3 − 8 = 6, 3 · 8 = 2, 3 · 8 · 5 = 2 · 5 = 10 (mod 11).
2.2. 28 mod 10 = 6, 37 mod 10 = 7, 719 mod 100 = 43, 757 mod 100 = 7.
2.3. 108 = 2 · 2 · 3 · 3 · 3, 77 = 7 · 11, 65 = 5 · 13, 30 = 3 · 3 · 5, 159 = 3 · 53.
2.4. пары (25,12) и (40, 27) взаимно просты, другие нет (числа (25, 15) делятся на 5, (13, 39) делятся на 13).
2.5. (14) = 6,
(20) = 8.
2.6. (53) = 52,
(21) =
(7) ·
(3) = 6 · 2 = 12,
(159) = 2 · 52 = 104.
2.7. 313 mod 13 = 3 · 312 mod 13 = 3, 522 mod 11 = 52 · 510 · 510 mod 11 = 25 mod 11 = 3, 317 mod 5 = 3.
2.8. 39 mod 20 = 3·38 mod 20 = 3, 214 mod 21 = 22 ·212 mod 21 = 4, 2107 mod 159 = 23 · 2104 mod 159 = 8.
2.9. (21, 12) = 3,
(30, 12) = 6,
(24, 40) =
(40, 24) = 8,
(33, 16) = 1.
2.10. а. x = −1, y = 2. б. x = 1, y = −2. в. x = 2, y = −1. г. x = 1, y = −2.
2.11. 3−1 mod 7 = 5, 5−1 mod 8 = 5, 3−1 mod 53 = 18, 10−1 mod 53 = 16.
2.12. Простые числа, меньшие 100: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, б1, б7, 73, 79, 83, 89, 97. Из них числа 5, 7, 11, 23, 47, 59 и 83 соответствуют виду р = 2q + 1.
2.13. При р = 11 в качестве параметра g могут быть выбраны числа 2, 6, 7 и 8.
2.14. а. YA = 20, YB = 17, ZAB = 21.
б. YA = 13, YB = 14, ZAB = 10.
в. YA = 21, YB = 9, ZAB = 16.
г. YA = 8, YB = 5, ZAB = 9.
д. YA = 6, YB = 17, ZAB = 16.
2.15. а. dA = 11, dB = 13, x1 = 17, x2 = 5, x3 = 6, x4 = 4.
б. dA = 3, dB = 19, x1 = 8, x2 = 12, x3 = 3, x4 = 6.
в. dA = 5,
dB = 11, x1 = 14, x2 = 10, x3 = 3, x4 = 10.
г. dA = 5, dB = 15, x1 = 7, x2 = 21, x3 = 14, x4 = 17.
д. dA = 11, dB = 5, x1 = 15, x2 = 2, x3 = 8, x4 = 9.
2.16. а. dB = 13, r = 14, e = 12, m' = 5.
б. dB = 16, r = 9,
e = 15, m' = 10.
в. dB = 15, r = 16, e = 14, m' = 10.
г. dB = 21,
r = 14, e = 12, m' = 5.
д. dB = 8, r = 5, e = 5, m' = 10.
2.17. а. NA = 55, (NA) = 40, cA = 27, e = 23, m' = 12.
б. NA = 65, (NA) = 48, cA = 29, e = 50, m' = 20.
в. NA = 77, (NA) = 60, cA = 43, e = 52, m' = 17.
г. NA = 91, (NA) = 72,
cA = 29, e = 88, m' = 30.
д. NA = 33, (NA) = 20, cA = 7, e = 9, m' = 15.
2.18. m = 111.
3.1. а. = 1111001110. б.
= 1111110101. в.
= 0001000110. г.
= 0101011011. д.
= 0001010001.
3.2. а. P1 0.002, P2
0.006, P3
0.623, P4
0.051, P5
0.311,
P6
0.007.
б. P1 0.000, P2
0.009, P3
0.000, P4
0.000,
P5
0.892, P6
0.099.
в. P1 0.000, P2
0.697, P3
0.000,
P4
0.004, P5
0.299, P6
0.000.
г. P1 0.003, P2
0.000,
P3
0.036, P4
0.000, P5
0.801, P6
0.160.
д. P1 0.196, P2
0.000, P3
0.001, P4
0.000, P5
0.018, P6
0.785.
3.3. а. H 1.16, n
6.04. б. H
0.52, n
2.42. в. H
0.9,
n
3.76. г. H
1.08, n
5.08. д. H
1.16, n
6.04.
3.4. а. P1 0.7 (
= bcacbcacc), P2 = 0, P3
0.3 (
= acbcacbcc),
P4 = 0, P5 = 0, P6 = 0.
б. P1 = 0, P2 = 0, P3 = 0, P4 0.21 (
=
bcccaccac), P5
0.20 (
= abbbcbbcb), P6
0.59 (
= acccbccbc).
в. P1 = 0, P2 = 0, P3 = 0, P4 = 1 ( = ccbcabccb), P5 = 0,
P6 = 0.
г. P1 = 0, P2 = 0, P3 0.000 (
= acbbbbcbb), P4
1.000
(
= abccccbcc), P5 = 0, P6 = 0.
д. P1 = 0, P2 = 0, P3 0.009
(
= bbbcbbbcb), P4
0.970 (
= cccbcccbc), P5 = 0, P6
0.021
(
= cccacccac).
5.1. а. s = 28. б. s = 30. в. s = 26. г. s = 71. д. s = 18.
5.2. а. 7, 28
подлинно,
22, 15
нет,
16, 36
подлинно.
б. 6, 42
нет,
10,30
да,
6,41
да.
в. 13,41
да,
11, 28
нет,
5, 26
да.
г. 15,71
да,
11,46
нет,
16,74
да.
д. 10,14
нет,
24,18
да,
17,8
да.
5.3. а. y = 14, r = 3, s = 8. б. y = 24, r = 3, s = 5. в. y = 40, r = 9, s = 2. г. y = 22, r = 9, s = 5. д. y = 64, r = 7, s = 10.
5.4. а. 10; 4, 5
нет (h−1 = 10, u1 = 6, u2 = 4, au1 = 62, yu2 = 25,v = 9
4),
10; 7, 5
да (h−1 = 10, u1 = 6, u2 = 7, au1 = 62,
yu2 = 59, v = 7),
10; 3, 8
да (h−1 = 10, u1 = 3, u2 = 3, au1 = 14,
yu2 = 64, v = 3).
б. 1; 3, 5
да (h−1 = 1, u1 = 5, u2 = 8, au1 = 40,
yu2 = 64, v = 3),
1; 4, 3
да (h−1 = 1, u1 = 3, u2 = 7, au1 = 14,
yu2 = 25, v = 4),
1; 4, 5
нет (h−1 = 1, u1 = 5, u2 = 7, au1 = 40,
yu2 = 25, v = 7
4).
в. 7; 7, 4
да (h−1 = 8, u1 = 10, u2 = 10,
au1 = 59, yu2 = 62, v = 7),
7; 9, 2
нет (h−1 = 8, u1 = 5, u2 = 5, au1 = 40, yu2 = 14, v = 2
9),
5; 9, 2
да (h−1 = 9, u1 = 7, u2 = 7,
au1 = 9, yu2 = 22, v = 9).
г. 6; 9, 5
да (h−1 = 2, u1 = 10, u2 = 4,
au1 = 59, yu2 = 24, v = 9),
8; 8, 3
нет (h−1 = 7, u1 = 10, u2 = 10, au1 = 59, yu2 = 64, v = 2
8),
7; 4, 1
да (h−1 = 8, u1 = 8, u2 = 1,
au1 = 24, yu2 = 22, v = 4).
д. 10; 7, 3
да (h−1 = 10, u1 = 8,
u2 = 7, au1 = 24, yu2 = 24, v = 7),
7; 7, 10
да (h−1 = 8, u1 = 3, u2 = 10, au1 = 14, yu2 = 22, v = 7),
8; 7, 5
нет (h−1 = 7, u1 = 2, u2 = 6, au1 = 22, yu2 = 59, v = 3
7).
б.1. а. = 103,
= 52, r-1 = 24, банкнота
11,58
.
б. = 13,
= 13, r-1 = 20, банкнота
99,22
.
в. = 58,
= 74, r-1 = 12, банкнота
55,55
.
г. = 37,
= 46, r-1 = 8, банкнота
44,11
.
д. = 49,
= 70, r-1 = 4, банкнота
77,42
.