Новые направления
В 1983 году в книге ``Коды и математика'' М.Н.Аршинова и Л.Е.Садовского (библиотечка ``Квант'') было написано: ``Приемов тайнописи - великое множество, и, скорее всего, это та область, где уже нет нужды придумывать что-нибудь существенно новое.'' Однако это было очередное большое заблуждение относительно криптографии. Еще в 1976 году была опубликована работа молодых американских математиков У.Диффи и М.Э.Хеллмана ``Новые направления в криптографии''1), которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием ``новой криптографии'' является понятие односторонней функции (подробнее об этом см. главу ).
, обладающая двумя свойствами:
а) существует полиномиальный алгоритм вычисления значений ;
б) не существует полиномиального алгоритма инвертирования функции (т.е. решения уравнения относительно , точное определение см. на стр. ).
Отметим, что односторонняя функция существенно отличается от функций, привычных со школьной скамьи, из-за ограничений на сложность ее вычисления и инвертирования. Вопрос о существовании односторонних функций пока открыт.
Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с секретом называется функция
, зависящая от параметра и обладающая тремя свойствами:
а) существует полиномиальный алгоритм вычисления значения для любых и ;
б) не существует полиномиального алгоритма инвертирования при неизвестном ;
в) существует полиномиальный алгоритм инвертирования при известном .
Про существование функций с секретом можно сказать то же самое, что сказано про односторонние функции. Для практических целей криптографии было построено несколько функций, которые могут оказаться функциями с секретом. Для них свойство б) пока строго не доказано, но считается, что задача инвертирования эквивалентна некоторой давно изучаемой трудной математической задаче. Наиболее известной и популярной из них является теоретико-числовая функция, на которой построен (подробнее об этом см. главу ).
Применение функций с секретом в криптографии позволяет:
1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;
2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;
3) решать новые криптографические задачи, отличные от шифрования ( и др.).
Опишем, например, как можно реализовать п. 1). Пользователь , который хочет получать шифрованные сообщения, должен выбрать какую-нибудь функцию с секретом . Он сообщает всем заинтересованным (например, публикует) описание функции в качестве своего алгоритма шифрования. Но при этом значение секрета он никому не сообщает и держит в секрете. Если теперь пользователь хочет послать пользователю защищаемую информацию , то он вычисляет и посылает по открытому каналу пользователю . Поскольку для своего секрета умеет инвертировать , то он вычисляет по полученному . Никто другой не знает и поэтому в силу свойства б) функции с секретом не сможет за полиномиальное время по известному шифрованному сообщению вычислить защищаемую информацию .
Описанную систему называют криптосистемой с открытым ключом, поскольку алгоритм шифрования является общедоступным или открытым. В последнее время такие криптосистемы еще называют асимметричными, поскольку в них есть асимметрия в алгоритмах: алгоритмы шифрования и дешифрования различны. В отличие от таких систем традиционные шифры называют симметричными: в них ключ для шифрования и дешифрования один и тот же. Для асимметричных систем алгоритм шифрования общеизвестен, но восстановить по нему алгоритм дешифрования за полиномиальное время невозможно.
Описанную выше идею Диффи и Хеллман предложили использовать также для электронной цифровой подписи сообщений, которую невозможно подделать за полиномиальное время. Пусть пользователю необходимо подписать сообщение . Он, зная секрет , находит такое , что , и вместе с сообщением
посылает
пользователю в качестве своей цифровой подписи. Пользователь хранит в качестве доказательства того, что подписал сообщение .
Сообщение, подписанное цифровой подписью, можно представлять себе как пару , где - сообщение, - решение уравнения
,
- функция с секретом, известная всем взаимодействующим абонентам. Из определения функции очевидны следующие полезные свойства цифровой подписи:
1) подписать сообщение , т.е. решить уравнение , может только абонент - обладатель данного секрета ; другими словами, подделать подпись невозможно;
2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию ;
3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;
4) подписанные сообщения можно, не опасаясь ущерба, пересылать по любым каналам связи.
Кроме принципа построения криптосистемы с открытым ключом, Диффи и Хеллман в той же работе предложили еще одну новую идею - открытое распределение ключей. Они задались вопросом: можно ли организовать такую процедуру взаимодействия абонентов и по открытым каналам связи, чтобы решить следующие задачи:
1) вначале у и нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у и
появляется, т.е. вырабатывается;
2) пассивный противник, который перехватывает все передачи информации и знает, что хотят получить и , тем не менее не может восстановить выработанный общий ключ и .
Диффи и Хеллман предложили решать эти задачи с помощью функции
где - большое простое число, - произвольное натуральное число, - некоторый примитивный элемент поля . Общепризнанно, что инвертирование функции , т.е. дискретное логарифмирование, является трудной математической задачей. (Подробнее см. главу .)
Сама процедура или, как принято говорить, протокол выработки общего ключа описывается следующим образом.
Абоненты и независимо друг от друга случайно выбирают по одному натуральному числу - скажем и . Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:
(Числа и считаются общедоступными.) Потом они обмениваются этими элементами по каналу связи. Теперь абонент , получив и зная свой секретный элемент , вычисляет новый элемент:
Аналогично поступает абонент :
Тем самым у и появился общий элемент поля, равный . Этот элемент и объявляется общим ключом и .
Из описания протокола видно, что противник знает
, не знает и и хочет узнать . В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это - трудная математическая задача.
Успехи, достигнутые в разработке схем цифровой подписи и открытого распределения ключей, позволили применить эти идеи также и к другим задачам взаимодействия удаленных абонентов. Так возникло большое новое направление теоретической криптографии - (подробнее см. главу ).
Объектом изучения теории криптографических протоколов являются удаленные абоненты, взаимодействующие, как правило, по открытым каналам связи. Целью взаимодействия абонентов является решение какой-то задачи. Имеется также противник, который преследует собственные цели. При этом противник в разных задачах может иметь разные возможности: например, может взаимодействовать с абонентами от имени других абонентов или вмешиваться в обмены информацией между абонентами и т.д. Противником может даже оказаться один из абонентов или несколько абонентов, вступивших в сговор.
Приведем еще несколько примеров задач, решаемых удаленными абонентами. (Читателю рекомендуем по своему вкусу самостоятельно придумать еще какие-нибудь примеры.)
1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.
Протокол решения этой задачи принято называть протоколом подписания контракта.
2. Взаимодействуют два не доверяющих друг другу абонента. Они хотят бросить жребий с помощью монеты. Это надо сделать так, чтобы абонент, подбрасывающий монету, не мог изменить результат подбрасывания после получения догадки от абонента, угадывающего этот результат.
Протокол решения этой задачи принято называть .
Опишем один из простейших протоколов подбрасывания монеты по телефону (так называемая схема Блюма-Микали). Для его реализации у абонентов и должна быть односторонняя функция , удовлетворяющая следующим условиям:
1) - множество целых чисел, которое содержит одинаковое количество четных и нечетных чисел;
2) любые числа , имеющие один образ , имеют одну четность;
3) по заданному образу ``трудно'' вычислить четность неизвестного аргумента .
Роль подбрасывания монеты играет случайный и равновероятный выбор элемента , а роль орла и решки - четность и нечетность соответственно. Пусть - абонент, подбрасывающий монету, а - абонент, угадывающий результат. Протокол состоит из следующих шагов:
1) выбирает (``подбрасывает монету''), зашифровывает , т. e. вычисляет , и посылает абоненту ;
2) получает , пытается угадать четность и посылает свою догадку абоненту ;
3) получает догадку от и сообщает , угадал ли он, посылая ему выбранное число ;
4) проверяет, не обманывает ли , вычисляя значение и сравнивая его с полученным на втором шаге значением .
3. Взаимодействуют два абонента и (типичный пример: - клиент банка, - банк). Абонент хочет доказать абоненту , что он именно , а не противник.
Протокол решения этой задачи принято называть .
4. Взаимодействуют несколько удаленных абонентов, получивших приказы из одного центра. Часть абонентов, включая центр, могут быть противниками. Необходимо выработать единую стратегию действий, выигрышную для абонентов.
Эту задачу принято называть задачей о византийских генералах, а протокол ее решения - протоколом византийского соглашения.
Осмысление различных протоколов и методов их построения привело в 1985-1986 г.г. к появлению двух плодотворных математических моделей - и . Математические исследования этих новых объектов позволили доказать много утверждений, весьма полезных при разработке криптографических протоколов (подробнее об этом см. главу ).
Под интерактивной системой доказательства понимают протокол взаимодействия двух абонентов: (доказывающий) и
(проверяющий). Абонент хочет доказать , что утверждение истинно. При этом абонент самостоятельно, без помощи , не может проверить утверждение (поэтому и называется проверяющим). Абонент может быть и противником, который хочет доказать , что утверждение
истинно, хотя оно ложно. Протокол может состоять из многих раундов
обмена сообщениями между и и должен удовлетворять двум условиям:
1) полнота - если действительно истинно, то абонент
убедит абонента признать это;
2) корректность - если ложно, то абонент вряд ли убедит абонента , что истинно.
Здесь словами ``вряд ли'' мы для простоты заменили точную математическую формулировку.
Подчеркнем, что в определении системы не допускалось, что
может быть противником. А если оказался противником, который хочет ``выведать'' у какую-нибудь новую полезную для себя информацию об утверждении ? В этом случае , естественно, может не хотеть, чтобы это случилось в результате работы протокола . Протокол , решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1) и 2), еще и следующему условию:
3) - в результате работы протокола абонент не увеличит свои знания об утверждении
или, другими словами, не сможет извлечь никакой информации о том, почему истинно.
Next: 1.5. Заключение
Up: 1. Основные понятия криптографии
Previous: 1.3. Математические основы
Contents:
