Введение в криптографию
Криптография — это искусство скрытия информации в последовательности битов от любого несанкционированного доступа. Для достижения этой цели используют шифрование: сообщение с помощью некоторого алгоритма комбинируется с дополнительной секретной информацией (ключом), в результате чего получается криптограмма. Долгое время способы разработки алгоритмов шифрования определялись исключительно хитростью и изобретательностью их авторов. И лишь в ХХ веке этой областью заинтересовались математики, а впоследствии — и физики.
Для любой системы передачи информации характерны следующие действующие лица: объекты А и Б, обменивающиеся информацией (будем называть их Алиса и Боб — Алиса передает информацию Бобу), и некто Е, пытающийся перехватить эту информацию (в дальнейшем — Ева). Задача заключается в том, чтобы исключить возможность расшифровки информации Евой. Однако на практике это жесткое требование заменяется более мягким: необходимо сделать расшифровку сообщения достаточно трудной для Евы.
Классический подход состоит в том, что ключ, использующийся как для шифровки, так и для расшифровки сообщения, должен быть известен только Алисе и Бобу. Такие системы называются криптосистемами с закрытым ключом. Надежность процедуры шифрования доказана только для метода «одноразовых блокнотов», предложенного в 1917 году Гильбертом Вернамом (Gilbert Vernam). Идея его состоит в том, что Алиса и Боб обмениваются набором общих секретных ключей, каждый из которых используется для шифрования только одного сообщения. Ключи генерируются случайно и никакой информации не несут. Процесс шифровки состоит в том, что каждый символ исходного сообщения «складывается» с соответствующим символом ключа (так что ключ должен быть достаточно длинным, а сообщение — достаточно коротким). В «докомпьютерное» время ключи хранили в блокнотах с отрывными листами (отсюда и название метода). Каждый лист блокнота уничтожался после использования.
В применении к системам телекоммуникаций возникает проблема обеспечения секретности во время обмена ключами («блокнотами»), поскольку ключ должен быть доставлен получателю сообщения заранее и с соблюдением строгой секретности. Иначе говоря, конфиденциально обменяться сообщениями позволяют ключи, но как обменяться самими ключами с обеспечением секретности? Сформулированную таким образом проблему называют проблемой распространения ключа.
Если используется постоянный закрытый ключ, то расшифровка сообщения зависит от вычислительной мощности системы и времени. В США, например, для шифрования используется стандарт DES (Data Encryption Standard), разработанный в 1977 году. Он основан на 56-битном ключе, при помощи которого можно закодировать 64 бит информации. На этом стандарте основывается защита банковских транзакций, паролей Unix-систем и других секретных данных. Поскольку длина ключа меньше, чем длина кодируемого сообщения, то механизм защиты не является абсолютно надежным. Если попытаться угадать ключ методом проб и ошибок, нужно перебрать 256 всевозможных значений. И хотя этот объем вычислений очень велик, в настоящее время уже имеются данные о возможности взлома подобных систем. Рекордное время составляет 22 часа 15 минут при распределенной обработке информации в компьютерной сети ().
Теория шифрования с использованием открытого ключа была создана Уэтфилдом Диффи (Whitfield Diffie) и Мартином Хеллманом (Martin Hellman) в 1976 г. В этой системе Боб имеет общедоступный код для шифрования и закрытый код для расшифровки сообщений. Криптосистемы с открытым ключом основываются на так называемых односторонних функциях:
по некоторому x легко вычислить функцию f(x), но зная f(x) трудно вычислить х.
Первый алгоритм, основанный на теории Диффи-Хеллмана, был предложен Роном Райвестом (Ron Rivest), Эди Шамиром (Adi Shamir) и Леонардом Эдлманом (Leonard Adleman) в 1977 г (RSA-алгоритм). Он основан на разложении простого числа на множители. Известно, что вычислить произведение двух простых чисел легко. В то же время, обратная задача – разложение числа на простые множители, достаточно трудоемка, поскольку время вычислений экспоненциально возрастает при увеличении количества битов в исходном числе. Хотя в настоящее время не опубликованы быстрые алгоритмы решения задачи разложения числа на простые множители, нельзя утверждать, что они не существуют вовсе. Кроме того, вычислительная мощность компьютерных систем постоянно возрастает, поэтому сложность задачи не означает ее неразрешимость. Так, компания RSA, основанная вышеперечисленными авторами алгоритма, предлагает всем желающим разложить на простые множители представленные ею числа. Один из последних отчетов компании посвящен разложению числа, состоящего из 155 цифр. Эта задача требует 35,7 процессорных года, что примерно эквивалентно 8000 MIPS-лет3; в реальном времени потребовалось 3,7 месяца благодаря распределенной обработке информации в компьютерной сети.
Таким образом, на настоящий момент единственно надежным методом шифрования является метод «одноразового блокнота», поскольку доказана его безусловная секретность, то есть секретность по отношению к шпиону, который обладает неограниченными временем и вычислительной мощностью. На пути к достижению такого уровня секретности, стоит проблема распространения ключа: Алиса и Боб должны обменяться ключом, сохранив его в полном секрете. Одним из ее решений является разработанный Чарльзом Беннетом (Charles Bennett) и Джилом Брассардом (Gilles Brassard) протокол квантового распространения ключа (quantum key distribution).
