Шифрование с открытым ключом
Одно из главных ограничений использования обычных криптографических систем связано с трудностью распространения ключей. Диффи и Хеллман, а также, независимо от них, Меркль, показали, что можно исключить защищенный канал передачи ключей и при этом обеспечить защиту при передаче сообщений по незащищенному каналу без осуществления каких-либо предварительных мероприятий. Как видно из рис. 18.6, между отправителем и получателем допускается двухсторонний обмен, но перехватчик здесь пассивный и только слушает. В отличие от обычных систем, в которых ключ должен сохранятся в секрете, системы, допускающие такую работу, называются системами с открытым ключом.
Рис. 18.6.
Поток информации в криптографической системе с открытым ключом
Для решения этой проблемы предлагаются два подхода. При открытом распространении ключей отправитель и получатель могут договориться о ключе, используемом в обычной криптографической системе. Несмотря на то, что противник слушает все переговоры, он не в состоянии вычислить ключ и не может понять последующего обмена сообщениями. Второй подход реализует криптографические системы с открытыми ключами, в которых для шифрования используются разные ключи.
Причина, по которой ключи в обычных криптографических системах должны столь тщательно защищаться, состоит в том, что функции шифрования и дешифрования в ней неразделимы. Любое лицо, получившее ключ для шифрования сообщений, может также дешифровать сообщения. Если средства шифрования разделены, то секретность можно обеспечить без засекречивания ключа шифрования, так как его нельзя использовать для расшифровывания.
Взаимодействуя по открытым каналам связи, абоненты А и В решают следующие задачи:
- вначале у А и В нет никакой общей секретной информации, но в конце процедуры такая общая секретная информация (общий ключ) у А и В появляется, т.е. вырабатывается;
- противник, который перехватывает все передачи и знает, что хочет получить А и В, тем не менее не может восстановить выработанный общий ключ А и В.
Предложено решать эти задачи с помощью функции F(x) = ?x (mod p), где р — большое простое число, x — произвольное натуральное число, ? — некоторый примитивный элемент поля G F(p).
Примитивным называется такой элемент ? из G F(p), что каждый элемент поля, может быть представлен в виде степени ?. Доказывается, что примитивный элемент всегда существует.
Общепризнанно, что инвертирование функции ?x (mod p), т.е. дискретное логарифмирование, является трудной математической задачей.
Саму же процедуру или, как принято говорить, протокол выработки общего ключа, можно описать следующим образом.
Числа р и ? считаются общедоступными.
Абоненты А и В независимо друг от друга случайно выбирают по одному натуральному числу — скажем xA и xB и. Эти элементы они держат в секрете. Далее каждый из них вычисляет новый элемент:
уA = ?x (mod p), уB = ?x (mod p)
Потом они обмениваются этими элементами по каналу связи. Теперь абонент А, получив уB и зная свой секретный элемент xA, вычисляет новый элемент:
= (?x) (mod p)
Аналогично поступает абонент В:
= (?x) (mod p)
Из свойств поля следует, что тем самым у А и В появится общий элемент, который и является общим ключом А и В.
Из описания протокола видно, что противник знает p, ?, ?x, ?x, не знает xA, xB
и хочет узнать ?x. В настоящее время нет алгоритмов действий противника, более эффективных, чем дискретное логарифмирование, а это — труднейшая математическая задача.
Эти системы должны разрабатываться таким образом, чтобы облегчить генерацию случайных пар инверсных ключей Е для шифрования и Д для дешифрования и работу с этими ключами, но чтобы вычисления Д по Е было вычислительно нереализуемым.
Криптографическая система с открытым ключом представляет собой пару семейств алгоритмов {EK}KÎ{K} и {ДK}KÎ{K}, определяющих обратимые преобразования
,
на конечном пространстве сообщений {M} со следующими свойствами.
1. Для каждого KÎ{K} ДK
обратно к EK , т.е. при любых К и М справедливо ДКЕК(М) = М.
2. Для каждого KÎ{K} и MÎ{M} нетрудно вычислить величины ЕК(М) и ДК(М).
3. Для почти каждого KÎ{K} невозможно в вычислительном отношении вывести из ЕК
какой-либо легко выполнимый алгоритм, эквивалентный ДК.
4. По каждому заданному KÎ{K} можно получить инверсную пару ЕК и ДК.
Свойство 3 позволяет не засекречивать ключи шифрования пользователя ЕК
и при этом не компроментировать секретность ключа дешифрования ДК. Следовательно, криптогафические системы распадаются на две части (семейство преобразований шифрования и семейство преобразований дешифрования) таким образом, что по данному члену одного семейства невозможно определить соответствующий член другого.
Свойство 4 гарантирует наличие реализуемого пути вычисления соответствующих пар обратных преобразований, когда не наложено никаких ограничений на то, каким должно быть преобразование шифрования или дешифрования. На практике криптографическое оборудование должно содержать генератор истинных случайных чисел для генерации К, а также генерирующий пару EК и ДК по заданному K.
Система такого рода упрощает проблему распределения ключей. Каждый пользователь генерирует пару взаимно обратных преобразований Е и Д. Он держит преобразование дешифрования Д в секрете, а преобразование шифрования публикует в открытом справочнике наподобие технического справочника. Теперь любой желающий может шифровать сообщения и посылать их пользователю, но никто, кроме него, не может дешифровать предназначенные для него сообщения.
Если вместо приведенных условий 1–4 множество преобразований обеспечивает, что для каждого KÎ{K} EK
является обратным ДK, т.е. при любых К и М справедливо утверждение ЕКДК(М) = М, то возможно, а часто и желательно осуществлять шифрование с помощью ключа Д, а дешифрование — с помощью ключа Е. По этой причине часто называют EK открытым ключом, а ДK
— личным ключом.
За время, истекшее после того, как была предложены эта система, разработано несколько путей ее реализации.
