2.2.7. Новые направления

В 1976 году была опубликована работа молодых американских математиков У. Диффи и М. Э. Хеллмана «Новые направления в криптографии»,  которая не только существенно изменила криптографию, но и привела к появлению и бурному развитию новых направлений в математике. Центральным понятием «новой криптографии» является понятие одно­сторонней функции [12, 14].

Односторонней называется функция F: X→ У, обладающая двумя свойствами:

а) существует полиномиальный алгоритм вычисления значений F(х);

б) не существует полиномиального алгоритма инвертирования фун­кции F (т. е. решения уравнения    относительно х).

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

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

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

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

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

Про существование функций с секретом можно сказать то же са­мое, что сказано про односторонние функции. Для практических це­лей криптографии было построено несколько функций, которые могут оказаться функциями с секретом. Для них свойство б) пока строго не доказано, но считается, что задача инвертирования эквивалентна не­которой давно изучаемой трудной математической задаче. Наиболее известной и популярной из них является теоретико-числовая функция, на которой построен шифр RSA (Райвест, Шамир, Адлеман), основанный на операциях с большими (более 100 знаков) простыми числами и их произведениями [4].

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

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

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

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

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

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

Рис. 2.7. Схема асимметричного метода шифрования

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

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

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

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

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

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

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

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

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

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

Диффи  и  Хеллман предложили решать эти задачи с помощью функ­ции

,

где р – большое простое число, х – произвольное натуральное число,  – некоторый примитивный элемент поля Галуа  [4, 5]. Общепризнанно, что инвертирование функции , т. е. дискретное логарифмиро­вание, является трудной математической задачей.

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

Абоненты А и В независимо друг от друга случайно выбирают по одному натуральному числу – скажем  и . Эти  элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:

,    .

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

.

Аналогично поступает абонент В:

.

Тем самым у А и В появился общий элемент поля, равный . Этот элемент и объявляется общим ключом   А  и  В.

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

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

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

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

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

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

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

За последние годы криптография и криптографические методы все шире входят в нашу жизнь.  От­правляя электронную почту, мы в некоторых случаях отвечаем на вопрос меню: «Нужен ли режим зашифрования?» Владелец интеллектуальной банков­ской карточки, обращаясь через терминал к банку, вначале выполняет криптографический   протокол   аутентификации  карточки.  Пользовате­ли  сети  Internet наверняка знакомы с дискуссиями вокруг возмож­ного принятия стандарта цифровой подписи для тех страниц, которые содержат «критическую» информацию (юридическую, прайс-листы и др.). С недавних пор пользователи сетей стали указывать после своей фамилии наряду с уже привычным «Email ...» и менее привычное – «Отпечаток открытого ключа ...».

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