Компьютерные сети. 6-е изд.

8.6. Алгоритмы с открытым ключом

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

В 1976 году два исследователя из Стэнфордского университета, Диффи (Diffie) и Хеллман (Hellman), предложили радикально новую криптосистему, в которой ключ дешифрования нельзя было получить из ключа шифрования — настолько они различались. Разработанные Диффи и Хеллманом алгоритмы шифрования E и дешифрования D (оба параметризованные ключом) должны были соответствовать следующим требованиям:

1. D(E(P)) = P.

2. Вывести D из E крайне сложно.

3. E нельзя взломать при помощи произвольного открытого текста.

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

Этот метод работает следующим образом. Допустим, Алиса, желая получать секретные сообщения, разрабатывает два алгоритма, удовлетворяющие перечисленным выше требованиям. Затем алгоритм шифрования и его ключ открыто публикуются; поэтому данный подход и называется шифрованием с открытым ключом (public-key cryptography). Алиса может разместить открытый ключ, к примеру, на своей домашней страничке. Алгоритм шифрования, параметризованный этим ключом, мы обозначим как EA. По аналогии алгоритм дешифрования (секретный), параметризованный персональным ключом Алисы, мы будем обозначать как DA. Боб делает то же самое: обнародует EB, но сохраняет в тайне DB.

Теперь мы попробуем решить проблему установки надежного канала между Алисой и Бобом, которые ранее никогда не встречались. Оба ключа шифрования, EA и EB, являются открытыми. Алиса берет свое первое сообщение P, вычисляет EB(P) и отправляет результат Бобу. Боб расшифровывает его с помощью своего секретного ключа DB, то есть вычисляет DB(EB(P)) = P. Никто другой не может прочитать зашифрованное сообщение EB(P), так как предполагается, что система шифрования надежна, а получить ключ DB на основании известного ключа EB очень трудно. Отсылая ответ R, Боб передает EA(R). Таким образом, Алиса и Боб получают надежный секретный канал связи.

Обратите внимание на используемую здесь терминологию. Шифрование с открытым ключом предполагает наличие у каждого пользователя двух ключей — открытого (все используют его для шифрования сообщений для этого пользователя) и закрытого (он нужен пользователю для дешифрования входящих сообщений). Мы будем и далее называть эти ключи открытым (public) и закрытым (private), чтобы отличать их от секретных (secret) ключей, которые применяются для шифрования и дешифрования в обычной криптографии с симметричным ключом.

8.6.1. Алгоритм RSA

Единственная загвоздка состоит в том, чтобы найти алгоритмы, отвечающие всем трем требованиям. Преимущества шифрования с открытым ключом очевидны, поэтому многие исследователи неустанно работали над созданием таких алгоритмов (некоторые из них уже опубликованы). Группой исследователей Массачусетского технологического института был разработан один надежный метод (Ривест и др.; Rivest et al., 1978). Он получил название RSA, по начальным буквам фамилий трех авторов: Рона Ривеста, Ади Шамира и Леонарда Адлемана (Ron Rivest, Adi Shamir, Leonard Adleman). Вот уже четверть века этот метод выдерживает попытки взлома и считается очень надежным. На его основе построены многие практические системы безопасности. По этой причине Ривест, Шамир и Адлеман в 2002 году получили награду ACM — Премию Тьюринга (Turing Award). Главный недостаток RSA в том, что для обеспечения достаточного уровня защиты нужен ключ длиной по крайней мере 2048 бит (против 256 бит в алгоритмах с симметричными ключами). Из-за этого алгоритм работает довольно медленно.

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

1. Выберем два больших простых числа p и q (скажем, длиной 1024 бита).

2. Вычислим n = p × q и z = (p – 1) × (q – 1).

3. Выберем число d, которое является взаимно простым с числом z.

4. Найдем такое число e, для которого справедливо равенство e × d = 1 mod z.

Заранее вычислив эти параметры, можно начинать шифрование. Сначала разобьем весь открытый текст (рассматриваемый в качестве битовой строки) на блоки так, чтобы каждое сообщение P попадало в интервал 0 ≤ P < n. Это несложно сделать, если разбить открытый текст на блоки по k бит, где k — максимальное целое число, для которого справедливо неравенство 2k < n.

Чтобы зашифровать сообщение P, вычислим C = P e (mod n). Чтобы дешифровать C, вычислим P = Cd (mod n). Можно доказать, что для всех значений P в указанном диапазоне функции шифрования и дешифрования являются взаимно обратными. Чтобы выполнить шифрование, нужны e и n. Для дешифрования требуются d и n. Таким образом, открытый ключ состоит из пары (e, n), а закрытый ключ — из пары (d, n).

Надежность метода обеспечивается сложностью факторизации больших чисел. Если бы криптоаналитик мог разложить на множители публично известное число n, он бы нашел значения p и q, а следовательно, и число z. После этого e и d можно найти с помощью алгоритма Евклида. К счастью, математики пытаются решить проблему факторизации больших чисел уже по меньшей мере 300 лет, и накопленный опыт говорит о том, что это очень трудная задача.

В свое время Ривест вместе с коллегами пришел к заключению, что разложение на множители числа из 500 цифр займет 1025 лет, если действовать методом простого перебора. Предполагалось использование наиболее известного алгоритма и компьютера, выполняющего одну инструкцию за 1 мкс. Если миллион чипов будет работать одновременно и выполнять одну инструкцию за 1 нс, все равно потребуется 1016 лет. Даже при экспоненциальном росте скоростей компьютеров потребуются многие годы, чтобы факторизовать числа из 500 цифр, а к тому времени наши потомки могут просто выбрать еще большие p и q. При этом, вероятно, никого не удивит, что атаки тоже совершенствуются — на сегодняшний день их скорость значительно возросла.

На илл. 8.19 приведен тривиальный учебный пример работы алгоритма RSA. Здесь p = 3 и q = 11, что дает значения n = 33 и z = 20 (так как (3 – 1) ×× (11 – 1) = 20). Число d можно выбрать равным 7, так как числа 20 и 7 не имеют общих делителей. Значение e можно найти, решив уравнение 7e = 1 (mod 20), откуда следует, что e = 3. Зашифрованный текст C получается из открытого сообщения P по формуле C = P3 (mod 33). Получатель расшифровывает сообщение по формуле P = C7 (mod 33). В качестве примера на рисунке показано шифрование слова «SUZANNE».

Илл. 8.19. Пример работы алгоритма RSA

Поскольку выбранные для этого примера простые числа настолько малы, P должно быть меньше 33, поэтому каждый блок открытого текста может содержать лишь одну букву. В результате получается моноалфавитный подстановочный шифр, что не слишком впечатляет. Если бы вместо этого мы выбрали числа p и q ≈ 2512, мы бы получили n ≈ 21024. Тогда каждый блок мог бы содержать до 1024 бит или 128 восьмиразрядных символов против 8 символов в случае метода DES или 16 символов для AES.

Отметим, что такое использование RSA аналогично применению симметричного алгоритма в режиме ECB, в котором одни и те же блоки на входе преобразуются в одинаковые блоки на выходе. Таким образом, для шифрования данных требуется сцепление блоков в том или ином виде. Но на практике RSA с открытым ключом используется только для передачи одноразовых 128- или 256-битных сеансовых ключей, после чего задействуется алгоритм с симметричным ключом наподобие AES. Система RSA слишком медленная, чтобы шифровать большие объемы данных, однако она широко применяется для распространения ключей.

8.6.2. Другие алгоритмы с открытым ключом

Хотя RSA по-прежнему популярен, это далеко не единственный известный алгоритм с открытым ключом. Первым таким алгоритмом стал алгоритм на основе задачи о рюкзаке (knapsack algorithm) Меркла и Хеллмана (Merkle and Hellman, 1978). Его принцип заключается в следующем. Допустим, имеется очень большое количество объектов разного веса. Их владелец кодирует сообщение, выбирая подмножество вещей и помещая их в рюкзак. Известен общий вес объектов в рюкзаке, а также список всех возможных объектов и их вес по отдельности. Список вещей в рюкзаке хранится в секрете. Считалось, что при некоторых дополнительных ограничениях определить возможный список объектов по известному общему весу невозможно путем вычислений. Поэтому эта задача легла в основу алгоритма с открытым ключом.

Разработчик алгоритма Ральф Меркл (Ralph Merkle) был настолько уверен в его надежности, что предложил $100 любому, кто сумеет его взломать. Ади Шамир («S» в группе RSA) мгновенно взломал его и получил награду. Это не смутило Меркла. Он усилил алгоритм и предложил за его взлом уже $1000. Рон Ривест («R» в группе RSA) тут же взломал улучшенную версию и получил награду. Леонард Адлеман («A» в группе RSA) остался без награды, поскольку Меркл уже не рискнул предложить $10 000 за взлом следующей версии. Несмотря на то что алгоритм рюкзака был в очередной раз исправлен, он не считается надежным и не используется на практике.

Остальные алгоритмы с открытым ключом основаны на сложности вычисления дискретных логарифмов или значений эллиптических кривых (Менезес и Ванстоун; Menezes and Vanstone, 1993). Первые были разработаны Эль Гамалем (El Gamal, 1985) и Шнорром (Schnorr, 1991). Вторые используют раздел математики, известный в очень узких кругах, — теорию эллиптических кривых.

Существует и ряд других схем, однако алгоритмы, использующие сложность факторизации больших чисел, вычисления дискретных логарифмов, разделенных по модулю на большое простое число, и значений эллиптических кривых, безусловно, являются самыми важными. Эти задачи считаются по-настоящему сложными, так как математики пытаются их решить уже много лет без особого успеха. Эллиптические кривые здесь представляют особый интерес, поскольку задачи дискретного логарифмирования на такой кривой еще сложнее, чем задачи разложения на множители. Голландский математик Арьен Ленстра (Arjen Lenstra) предложил сравнивать криптографические алгоритмы по количеству энергии, которая тратится на их взлом. По его расчетам, чтобы взломать 228-битный RSA-ключ, требуется примерно столько же энергии, сколько нужно для того, чтобы вскипятить одну чайную ложку воды. Однако в случае ключа той же длины на базе эллиптической кривой на взлом уйдет столько же энергии, сколько нужно для того, чтобы вскипятить всю воду на планете. Перефразируя Ленстра, можно сказать, что даже испарив всю воду (включая воду в их телах), взломщики вряд ли добьются успеха.