Асимметричные криптоалгоритмы

За последние годы криптография и криптографические методы все шире входят в нашу жизнь и даже быт. Вот несколько примеров.

1 Отправляя Email, мы в некоторых случаях отвечаем на вопрос меню: ``Нужен ли режим зашифрования?''

2 Владелец интеллектуальной банковской карточки, обращаясь через терминал к банку, вначале выполняет криптографический протокол аутентификации карточки.

3 Пользователи сети Интернет наверняка знакомы с дискуссиями вокруг возможного принятия стандарта цифровой подписи для тех страниц, которые содержат ``критическую'' информацию (юридическую, прайс-листы и др.). С недавних пор пользователи сетей стали указывать после своей фамилии наряду с уже привычным ``Email...'' и менее привычное - ``Отпечаток открытого ключа...''.

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

В 1976 году была опубликована работа молодых американских математиков У.Диффи и М.Э.Хеллмана ``Новые направления в криптографии''), которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием ``новой криптографии'' является понятие односторонней функции.

Односторонняя функция должна обладать такими двумя свойствами:

а) существует полиномиальный(эффективный) алгоритм вычисления значений

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

Еще одним новым понятием является понятие функции с секретом. Иногда еще употребляется термин функция с ловушкой. Функцией с секретом называется функция , зависящая от параметра и обладающая тремя свойствами:

а) существует полиномиальный (эффективный) алгоритм вычисления значения для любых и ;

б) не существует полиномиального алгоритма инвертирования при неизвестном ;

в) существует полиномиальный(эффективный) алгоритм инвертирования при известном .

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

Наиболее известной и популярной из них является теоретико-числовая функция, на которой построен шифр RSA.

Применение функций с секретом в криптографии позволяет:

1) организовать обмен шифрованными сообщениями с использованием только открытых каналов связи, т.е. отказаться от секретных каналов связи для предварительного обмена ключами;

2) включить в задачу вскрытия шифра трудную математическую задачу и тем самым повысить обоснованность стойкости шифра;

3) решать новые криптографические задачи, отличные от шифрования (электронная подпись, защита электронной информации от модификации и др.).

Опишем, например, как можно реализовать п. 1).

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

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

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

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

Сообщение, подписанное цифровой подписью, можно представить себе как пару ,

где - сообщение,

- решение уравнения ,

- функция с секретом, известная всем взаимодействующим абонентам. Из определения функции очевидны следующие полезные свойства цифровой подписи:

1) подписать сообщение , т.е. решить уравнение , может только абонент - обладатель данного секрета ; другими словами, подделать подпись невозможно;

2) проверить подлинность подписи может любой абонент, знающий открытый ключ, т.е. саму функцию ;

3) при возникновении споров отказаться от подписи невозможно в силу ее неподделываемости;

4) подписанные сообщения можно, не опасаясь ущерба, пересылать по любым каналам связи.

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

1) вначале у и нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у и появляется, т.е. вырабатывается;

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

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

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

Приведем несколько примеров задач, решаемых удаленными абонентами.

1. Взаимодействуют два не доверяющих друг другу абонента. Они хотят подписать контракт. Это надо сделать так, чтобы не допустить следующую ситуацию: один из абонентов получил подпись другого, а сам не подписался.

Протокол решения этой задачи принято называть протоколом подписания контракта.

2. Взаимодействуют два не доверяющих друг другу абонента. Они хотят бросить жребий с помощью монеты. Это надо сделать так, чтобы абонент, подбрасывающий монету, не мог изменить результат подбрасывания после получения догадки от абонента, угадывающего этот результат.

Протокол решения этой задачи принято называть протоколом подбрасывания монеты.

3. Взаимодействуют два абонента и (типичный пример: - клиент банка, - банк). Абонент хочет доказать абоненту , что он именно , а не противник.

Протокол решения этой задачи принято называть протокол идентификации абонента.

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

Эту задачу принято называть задачей о византийских генералах, а протокол ее решения - протоколом византийского соглашения.

Осмысление различных протоколов и методов их построения привело в 1985-1986 г.г. к появлению двух плодотворных математических моделей – интерактивной системы доказательства и доказательства с нулевым разглашением. Математические исследования этих новых объектов позволили доказать много утверждений, весьма полезных при разработке криптографических протоколов.

Под интерактивной системой доказательства понимают протокол взаимодействия двух абонентов: (доказывающий) и (проверяющий).

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

1) полнота - если действительно истинно, то абонент убедит абонента признать это;

2) корректность - если ложно, то абонент вряд ли убедит абонента , что истинно (за словами ``вряд ли'' для простоты заменена точная математическая формулировка).

В определении системы не допускалось, что может быть противником. А если оказался противником, который хочет ``выведать'' у какую-нибудь новую полезную для себя информацию об утверждении ? В этом случае , естественно, может не хотеть, чтобы это случилось в результате работы протокола .

Протокол , решающий такую задачу, называется доказательством с нулевым разглашением и должен удовлетворять, кроме условий 1) и 2), еще и следующему условию:

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

Поиск по сайту: