Современная криптология - Брассар Ж.
Скачать (прямая ссылка):
Для более основополагающих сведений по вычислительной теории чисел для криптографии мы отсылаем читателя к замечательной книге Евангелоса Кранакиса [244].
§ 2. Открытое распределение ключей
Одна из основных трудностей, которую всегда необходимо учитывать в больших многопользовательских криптографических системах заключается в том, что каждая пара ее пользователей, предполагающих обмениваться друг с другом конфиденциальной информацией, должна заранее выработать свой обоюдный секретный ключ. Как же, например, должны поступить два конкретных пользователя, которые неожиданно захотели установить между собой секретную связь, но еще не сообщали друг другу никакой секретной информации? Традиционное решение для них — где-нибудь встретиться и выработать совместный секретный ключ, или использовать для его передачи доверительного курьера. Оба этих решения являются очень неоперативными и дорогостоящими. К тому же они не могут быть абсолютно надежными.
Предназначение криптосистемы с открытым распределением ключей как раз и заключается в том, чтобы позволить двум пользователям Алисе и Бобу выработать в результате переговоров друг с другом по несекретному каналу связи такой совместный секретный ключ, который «нарушитель» не мог бы разгадать даже после прослушивания всех этих переговоров.
Открытое распределение ключей
Точнее говоря, хотелось бы иметь такой протокол, с помощью которого Алиса и Боб могли обмениваться сообщениями mi (от Алисы к Бобу), m2 (от Боба к Алисе), ..., до тех пор пока они оба окончательно не договорятся между собой о некотором совместном ключе к, причем они должны сделать это так, чтобы определить к из знания только mi, m2, ... было практически невозможно. Подчеркнем еще раз, что этого необходимо добиться даже в том случае, если Алиса и Боб не обменивались заранее никакой информацией, которая не была бы известна нарушителю.
Первый кажущийся абсолютно невозможным протокол, который тем не менее достигает этой цели, был предложен Диффи и Хеллманом [157] в 1976 году. Он основывается на задаче дискретного логарифмирования, рассмотренной в § 1. Пусть п — некоторое большое целое число, и пусть д — другое целое, лежащее строго между 1 и п — 1. В качестве первого шага протокола Диффи-Хеллмана Алис а и Боб уславливаются об п и д посредством несекретного канала связи (в качестве альтернативы пи) могли бы быть стандартными параметрами, применяемыми всеми пользователями системы). Затем Алиса, выбирает некоторое большое целое число х и вычисляет X = gx mod п. Соответственно, Боб выбирает число у и вычисляет Y = ду mod ft. После этого Алиса, и Боб обмениваются числами X и Y по тому же несекретному каналу связи, сохраняя в секрете х и у (Алиса при этом знает только х, а Боб — только у). Наконец, Алиса вычисляет Yx mod п, а Боб, соответственно, вычисляет Ху mod п. Оба эти значения, очевидно, равны между собой, так как каждое из них равно д(х у^ mod п. Это как раз и есть тот самый ключ к, который Алиса и Боб хотели совместно выработать.
Нарушитель при таком протоколе сталкивается с задачей вычисления к из пересылаемых по несекретному каналу чисел д, тг, X и Y. Очевидным подходом для нарушителя было бы вычислить х из д, п и X (или по крайней мере некоторое х, такое, что дх mod п = X, так как для любого подобного х всегда Yx mod п = к). Однако это в точности задача нахождения дискретного логарифма, которая считается практически невыполнимой. Кроме того, никто пока не придумал способа вычислять к эффективно из д, п, X и Y, как никто и не смог доказать, что это невозможно, или хотя бы продемонстрировать, что не
50 Системы с открытым ключом
Глава 4
существует лучшего способа сделать это, по сути дела не находя в процессе вычисления дискретного логарифма. Вот почему, вообще говоря, правомерно предполагать, что вычисление к может быть осуществлено эффективно, даже если окажется, что решение задачи дискретного логарифмирования действительно практически невыполнимо.
Выбор д и п может оказывать существенное влияние на эффективность и надежность представленного только что проекта криптосхемы. Для того чтобы сократить размер возможных окончательных значений к, важно чтобы функция модульного возведения в степень /дп:Жп -^Жп (как она определена в § 1) была настолько почти взаимнооднозначной, насколько это возможно. В том случае, когда п является простым числом, всегда существует такое д, что дх mod п принимает каждое из значений в промежутке от 1 до гг — 1, когда х пробегает значения из того же интервала. Подобные д, которые называются образующими элементами, или генераторами, циклической группы Жп, и были бы искомыми. При этом надежнее выбрать п таким обра-
л — ^
зом, чтобы —-— также было простым [288]. Кроме того, можно было бы все указанные операции проводить в полях Галуа GF(2fc), описание методов вычисления в которых, к сожалению, выходит далеко за рамки этой книги [41]. Они предоставляют возможность намного более эффективно осуществлять умножение (а следовательно, и возведение в степень), так как позволяют избежать при вычислениях необходимости переносов и приведений по модулю [5, 4]. Однако в этом случае размер ключа будет намного длиннее. С другой стороны, длины всех чисел, участвующих в арифметических операциях можно существенно сократить, если использовать вычисления над эллиптическими кривыми [6].
