Шифрование с открытым ключом

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

Рис. 18.6. Поток информации в криптографической системе с открытым ключом

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

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

Взаимодействуя по открытым каналам связи, абоненты А и В решают следующие задачи:

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

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

Предложено решать эти задачи с помощью функции F(x) = α^x (mod p), где р — большое простое число, x — произвольное натуральное число, α — некоторый примитивный элемент поля G F(p).

Примитивным называется такой элемент α из G F(p), что каждый элемент поля, может быть представлен в виде степени α. Доказывается, что примитивный элемент всегда существует.

Общепризнанно, что инвертирование функции α^x (mod p), т.е. дискретное логарифмирование, является трудной математической задачей.

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

Числа р и α считаются общедоступными.

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

у_A = α^x (mod p), у_B = α^x (mod p)

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

= (α^x) (mod p)

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

= (α^x) (mod p)

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

Из описания протокола видно, что противник знает p, α, α^x, α^x, не знает x_A, x_B и хочет узнать α^x. В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это — труднейшая математическая задача.

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

Криптографическая система с открытым ключом представляет собой пару семейств алгоритмов {E_K}_KÎ{K} и {Д_K}_KÎ{K}, определяющих обратимые преобразования

,

на конечном пространстве сообщений {M} со следующими свойствами.

1. Для каждого KÎ{K} Д_K обратно к E_K, т.е. при любых К и М справедливо Д_КЕ_К(М) = М.

2. Для каждого KÎ{K} и MÎ{M} нетрудно вычислить величины Е_К(М) и Д_К(М).

3. Для почти каждого KÎ{K} невозможно в вычислительном отношении вывести из Е_К какой-либо легко выполнимый алгоритм, эквивалентный Д_К.

4. По каждому заданному KÎ{K} можно получить инверсную пару Е_К и Д_К.

Свойство 3 позволяет не засекречивать ключи шифрования пользователя Е_К и при этом не компроментировать секретность ключа дешифрования Д_К. Следовательно, криптогафические системы распадаются на две части (семейство преобразований шифрования и семейство преобразований дешифрования) таким образом, что по данному члену одного семейства невозможно определить соответствующий член другого.

Свойство 4 гарантирует наличие реализуемого пути вычисления соответствующих пар обратных преобразований, когда не наложено никаких ограничений на то, каким должно быть преобразование шифрования или дешифрования. На практике криптографическое оборудование должно содержать генератор истинных случайных чисел для генерации К, а также генерирующий пару E_К и Д_К по заданному K.

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

Если вместо приведенных условий 1–4 множество преобразований обеспечивает, что для каждого KÎ{K} E_K является обратным Д_K, т.е. при любых К и М справедливо утверждение Е_КД_К(М) = М, то возможно, а часто и желательно осуществлять шифрование с помощью ключа Д, а дешифрование — с помощью ключа Е. По этой причине часто называют E_K открытым ключом, а Д_K — личным ключом.

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

Цифровая подпись

Идея цифровой подписи (ее еще называют электронной подписью) была предложена Диффи и Хеллманом. Суть ее заключается в использовании односторонней функции с секретом F_К. В настоящее время эта идея реализована в большом количестве систем передачи данных. Сообщение, подписанное цифровой подписью, можно представить в виде пары (x,y), где x — сообщение, F_К: x ® y —односторонняя функция, известная всем взаимодействующим абонентам, y — решение уравнения F_К(y) = x. Из определения функции F_К очевидны следующие достоинства цифровой подписи.

1. Подписать сообщение x, т.е. решить уравнение F_K(y) = x, может только абонент, являющийся обладателем данного секрета К; другими словами, подделать подпись невозможно.

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

4. При возникновении споров отказаться от подписи невозможно в силу ее неподделываемости.

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

Именно перечисленные достоинства и обусловили широкой применение и распространение систем цифровой подписи.

Как практически выглядит использование цифровой подписи? Рассмотрим, как осуществляется работа банка с платежными поручениями своих клиентов. Все абоненты этой сети знают одностороннюю функцию F_K, и каждый клиент имеет собственный, никому неизвестный секрет К. Клиент подписывает платежное поручение x с помощью функции F_K со своим секретом К и посылает подписанное платежное поручение в банк. Банк, получив сообщение от клиента и зная открытый ключ, проверяет подлинность подписи клиента и только после этого выполняет его платежное поручение. В силу отмеченных достоинств цифровой подписи и банк, и клиент уверены, что их интересы не пострадают.

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