:::::: № 1 январь-февраль 2005 г. :::::: - Журнал «Защита информации. Инсайд»

		№1 январь-февраль 2005 г. Тема номера: ЭКОНОМИЧЕСКИ ОПРАВДАННАЯ БЕЗОПАСНОСТЬ
		МЕТОД ГЕНЕРАЦИИ СЕКРЕТНОГО КЛЮЧА ПО ОТКРЫТОМУ КАНАЛУ СВЯЗИ М. Я. Фитерман, ст. научный сотрудник ОАО «ВАМИ-РУСАЛ» fiterman@vami.rusal.ru

1. Идея метода

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

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

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

При генерации общего ключа каждый абонент пытается угадать ключ партнера в результате двухстороннего обмена сообщениями. Для этого каждая версия ключа передается по каналу связи в замаскированном виде так, что его невозможно однозначно определить из переданных текстов. С ростом числа таких сообщений вероятность правильного угадывания абонентом ключа, выбранного партнером, возрастает. Когда эта вероятность достигает достаточно большой величины (скажем 99,99 %), процедуру генерации общего ключа можно считать успешно законченной, и затем абоненты могут пользоваться этим ключом для шифрования своих информационных сообщений. Сказанное в равной мере относится и к криптоаналитику, располагающему всеми переданными текстами. Поэтому, исходя из закона сохранения количества информации, вероятность угадывания ключа криптоаналитиком должна оказаться такой же, что и для абонентов. Ниже это доказано строго математически. Таким образом, у абонентов пока нет никакого выигрыша в секретной информации по сравнению с криптоаналитиком. Но ситуация меняется, если абоненты в своих сообщениях используют квантовый эффект случайного события – угадывания ключа. Оказывается, что обратная связь между абонентами (двухсторонний обмен сообщениями) позволяет им обратить квантовый эффект себе на пользу, а криптоаналитик лишен этой возможности. В результате нарастание вероятности угадывания ключа абонентами прогрессивно опережает таковую для криптоаналитика и можно добиться расхождения вероятностей абонентов и криптоаналитика в любое число раз, например в 1000. Степень расхождения этих вероятностей зависит от объема переданной информации, то есть от длительности процедуры генерации общего секретного ключа. Так как эта процедура носит служебный характер, а главная цель абонентов – передача полезной секретной информации (на основе выработанного ключа), то, очевидно, следует ограничиться каким-то разумным расхождением вероятностей абонентов и криптоаналитика.

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

Во-первых, абоненты должны передавать друг другу свои версии общего ключа в замаскированном виде. Для этого они могут использовать обычные способы шифрования информации, то есть преобразования открытого текста X в шифр-текст Y с помощью функции (или алгоритма) шифрования E: Y = E(X, K), где K – ключ шифра. В данном случае открытый текст X является эталонным и общеизвестным, например, фиксированным числом. Поэтому передаваемый шифртекст Y несет в себе информацию только о ключе K, и его можно назвать носителем ключа. Функция шифрования должна быть не обратимой относительно ключа (точнее не однозначно обратимой). Это означает, что могут существовать другие значения ключа K’, дающие тот же результат шифрования (и дешифрования): E(X, K’)=E(X, K) для K’№K. Такие ключи K’ будем называть ложными ключами. Можно сказать, что в этом случае шифртекст является нечетким носителем ключа, и это есть первое необходимое условие протокола генерации общего секретного ключа. Однако одного этого свойства протокола недостаточно для достижения вероятностного выигрыша абонентов по отношению к криптоаналитику.

Во-вторых, протокол должен использовать квантовый эффект случайных событий, в данном случае события угадывания абонентом ключа партнера. Это можно обеспечить путем передачи ключа не в одном сообщении, а в серии сообщений. Назовем абонентов A и B и будем обозначать их ключи и шифртексты одноименными верхними индексами. Абонент A, получив от абонента B шифртекст Y^B =E(X, K^B), проверяет, удовлетворяет ли его ключ KA данному уравнению шифрования. Если E(X, K^A)=Y^B (удовлетворяет), то он сохраняет этот ключ и использует его в своем следующем сообщении. В противном случае он выбирает новый ключ, например, случайным выбором из заданного множества ключей. Таковы же действия абонента B. Далее, если у абонента один ключ сохраняется заданное число раз подряд, он полагает, что это и есть угаданный им ключ партнера и отбирает его в качестве элемента общего секретного ключа. Серия сообщений с обменом ключами считается успешной, если обоим абонентам удалось отобрать заданное число ключей. В противном случае (если один из абонентов не успел отобрать все ключи) серия считается неудачной и повторяется вновь.

1.1. Качественный анализ метода

Как же здесь работает квантовый эффект? Дело в том, что факт сохранения ключа абонентом является единичным исходом (квантом) события «произвольный ключ удовлетворяет уравнению шифрования» и происходит в случайный момент времени (в случайном сообщении из серии). Сохранение ключа может произойти в двух случаях. В первом случае ключ абонента случайно совпадает с ключом партнера. Ясно, что, начиная с этого момента (с этого номера сообщения), оба абонента обязательно сохранят свои ключи заданное число раз. Следовательно, в этом случае совпадение отобранных ими ключей гарантировано. Второй возможный случай – ключ абонента не совпадает с ключом партнера, но удовлетворяет уравнению шифрования. Такой ключ по определению ложный. Если он случайно удовлетворит и уравнениям шифрования следующих сообщений партнера заданное число раз, то в соответствии с протоколом этот ложный ключ будет также отобран абонентом. Далее, если на интервале сохранения ключа первым абонентом ключ второго абонента случайно совпадет с сохраняемым ложным ключом первого абонента (как в первом случае), то с этого момента ключ первого абонента перестает быть ложным и переходит в разряд истинного ключа. В результате оба абонента снова отберут гарантированно совпадающие ключи, но на не совпадающих номерах сообщений, то есть не синхронно. Ясно, что если интервалы сохранения ключей у абонентов вообще не перекрываются, то сохраняемые ими ключи все же случайно могут совпасть. Вероятность такого их совпадения, то есть вероятность угадывания абонентов в этом случае равна априорной вероятности угадывания без обмена сообщениями.

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

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

< ... >

Полную версию статьи смотрите на страницах журнала «Защита информации. Инсайд»

Обращайтесь!!!
e-mail: magazine@inside-zi.ru
тел.: +7 (921) 958-25-50, +7 (911) 921-68-24

Предыдущая статья СОДЕРЖАНИЕ НОМЕРА Следующая статья