Паранойя с открытым ключом

Zero Gravity (dik@taifun.ru)

Спецвыпуск Xakep, номер #015, стр. 015-104-2

Открытый ключ

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

RSA - влезаем глубже

Поговорим об алгоритме RSA. Это криптосистема, разработанная Ривестом, Шамиром и Эдлеманом (Rivest, Shamir, Adleman). Ее идея состоит в искусном использовании того факта, что легко перемножить два больших простых числа, однако крайне трудно разложить на множители их произведение. Вот это произведение и есть тот самый открытый ключ. Немного формул :). Берем два больших простых числа p и q, перемножаем их и получаем n (n = p*q). Потом выберем большое число d > 1, к которому надо подобрать число 1 < e < (p-1)*(q-1) , - такое, что (e*d) mod (p-1)(q-1) = 1 . Напомню, что mod дает остаток от целочисленного деления. Открытым ключом являются числа n и e, а закрытым - число d. Естественно, что для шифрования данных используются числовые значения кодов шифруемых символов. Если ASCII-код буквы A - 65, то буква A шифруется так: (65^e) mod n = X , где X - зашифрованный символ. Расшифровать это можно так: (X^d) mod n = 65. Но, если ты заметил, здесь присутствует возведение в степень. Возводя большие числа в степень, ты почти наверняка выйдешь за приделы разрядности процессора. Вот так мы наступаем на пятки прогрессу :). Кричишь ему, мол: "Прогресс, шагай с нами в ногу! Левой, левой!", а он не слышит почему-то ;). О чем это говорит? О том, что данный алгоритм сложно реализовать своими силами, то есть самому написать процедуры шифрации и дешифрации. Но если такая необходимость есть, то можно воспользоваться другими, не менее криптостойкими алгоритмами. Например, шифрование при помощи сверхрастущего вектора.

PGP

В 1990 году Фил Циммерман использовал систему RSA в своей программе Pretty Good Privacy. В США есть законы, в соответствии с которыми программа PGP классифицирована как "военное снаряжение" (то есть нечто вроде танков и напалма :)), поэтому ее экспорт из страны запрещен. Но однажды система PGP была нелегально экспортирована из Соединенных Штатов. Почти наверняка это произошло без ведома Циммермана. Тем не менее против Фила было выдвинуто обвинение, которое сейчас рассматривается Большим Жюри. Ну да черт с ней, с буржуйской бюрократией! Давай лучше посмотрим, что собой представляет сам предмет спора. PGP работает следующим образом - у каждого пользователя имеется два ключа: закрытый секретный и открытый. Секретный ключ он оставляет в тайне, а открытый сообщает всем своим приятелям. Для того чтобы организовать безопасную переписку между двумя пользователями, необходимо, чтобы они поменялись своими открытыми ключами. Первый пользователь шифрует сообщение открытым ключом второго пользователя и отправляет его (сообщение). Оно может быть расшифровано только вторым пользователем, так как соответствующий закрытый ключ есть только у него. Он получает сообщение, расшифровывает его, пишет ответ и шифрует его открытым ключом второго пользователя. Так и переписываются :).