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

Одно из главных ограничений использования обычных криптографических систем связано с трудностью распространения ключей. Диффи и Хеллман, а также, независимо от них, Меркль, показали, что можно исключить защищенный канал передачи ключей и при этом обеспечить защиту при передаче сообщений по незащищенному каналу без осуществления каких-либо предварительных мероприятий. Как видно из рис. 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—личным ключом.

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