Открытое распространение ключей

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

Точнее, хотелось бы иметь такой протокол, с помощью которого А и В обменивались бы сообщениями m1(от А к B), m2(от B к A), …, до тех пор пока А и В окончательно не условятся о некотором ключе k таким образом, чтобы определить k из знания только m1, m2,… было бы практически невозможно. Подчеркнем еще раз, что этого необходимо добиться даже несмотря на то что А и В заранее не обмениваются никакой информацией, которая не была бы известна подслушивателю.

Первый протокол, который достигает этой кажущейся невозможной цели, был предложен Диффи (W. Diffie) и Хеллманом (M.E. Hellman) в 1976 году. Он основывается на задаче дискретного логарифмирования, рассмотренной в разделе 1.1. Пусть n некоторое большое целое число, и пусть g другое целое, лежащее строго между 1 и n-1. В качестве первого шага протокола Диффи-Хеллмана A и B уславливаются об n и g посредством несекретного канала связи (альтернативно n и g могли бы быть стандартными параметрами, применяемыми всеми пользователями системы).

Затем А выбирает некоторое большое целое число x и вычисляет X = g^x mod(n). Соответственно, В выбирает y и вычисляет Y = g^y mod(n). После этого А и В обмениваются X и Y по тому же несекретному каналу связи, храня при этом в секрете x и y ( x знает только А, а y – только В). Наконец, А вычисляет Yx mod(n); соответственно, В вычисляет Xy mod(n). Оба эти значения равны между собой, так как каждое из них равно g(x*y) mod(n). Это и есть именно тот ключ k, который они хотели совместно выработать.

Нарушитель сталкивается с задачей вычисления k из информации, пересылаемой по несекретному каналу: g, n, X, Y. Очевидным подходом для нарушителя было бы вычислить x из g, n и X (или, по крайней мере, некоторое такое x’, что gx mod(n)=X, так как любое такое x’ дает Yx mod(n) = k). Однако, это в точности задача определения дискретного логарифма, которая считается практически невыполнимой. Еще никто не придумал способа вычислять k эффективно из g, n, X, Y, но и никто не смог доказать, что это невозможно, или хотя бы, что не существует лучшего способа сделать это, чем вычислить сначала дискретный логарифм. Поэтому, вообще говоря, правомерно предполагать, что вычисление k может быть осуществлено эффективно, даже если задача дискретного логарифмирования действительно оказалась бы практически невыполнимой.

Выбор g и n может оказывать существенное влияние на эффективность и надежность представленного выше проекта системы. Для того чтобы сократить размер возможных окончательных значений k, важно чтобы функция модульного возведения в степень f[g,n]: Zn -> Zn (как она определена в разделе 1.1.) была настолько почти взаимнооднозначной, насколько это возможно. В том случае, когда n является простым числом, всегда существует такое g, что g^x mod(n) принимает каждое из значений в промежутке от 1 до n-1, когда x пробегает значения из того же интервала. Такие g, известные как генераторы циклической группы Zn и были бы искомыми. В этом случае надежнее выбрать n таким образом, чтобы (n-1)/2 также было простым. Кроме того можно было бы все указанные операции проводить в полях Галуа GF(2k ). Они предоставляют возможность намного более эффективно осуществлять умножение (а следовательно и возведение в степень), так как позволяют избежать при вычислениях необходимости переносов и приведений по модулю. Размер ключа в этом случае будет, однако, существенно длинее.

Вы можете следить за любыми ответами на эту запись через RSS 2.0 ленту. Вы можете оставить ответ, или trackback с вашего собственного сайта.

Оставьте отзыв

XHTML: Вы можете использовать следующие теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

 
Rambler's Top100