Введение в криптографию
Список замеченных опечаток:
В шифровке на стр. 325,
напечатано: 212850А
Следует читать: 212850Б
При хранении и передаче данных нередко возникает требование защитить их от нежелательного прочтения и/или модификации. Если задача защиты от нежелательной модификации решается обсуждавшимися в предыдущем разделе избыточными кодами, то с прочтением все существенно сложнее.
Проще всего обеспечить защиту данных, лишив потенциальных злоумышленников доступа к физическому носителю данных или физическому каналу, по которому происходит их передача. К сожалению, иногда это невыполнимо (например, если обмен данными происходит по радиоканалу), а зачастую просто слишком дорого. В этом случае на помощь приходят методики, собирательное название которых – криптография (тайнопись). В отличие от большинства терминов компьютерной лексики это слово не английского, а греческого происхождения.
История криптографии насчитывает тысячи лет, и многие основополагающие принципы современной криптографии известны, возможно, с доисторических времен, однако, существенный прогресс в теории шифрования был достигнут лишь относительно недавно, в связи с разработкой современной теории информации.
Практически все методы криптографии сводятся к преобразованию данных в набор из конечного количества символов и осуществлению над этими символами двух основных операций: подстановки и перестановки. Подстановка состоит в замене одних символов на другие. Перестановка состоит в изменении порядка символов. В качестве символов при этом могут выступать различные элементы сообщения – так, при шифровании сообщений на естественных языках подстановке и перестановке могут подвергаться как отдельные буквы, так и слова или даже целые предложения (как, например, в аллегорических изложениях магических и священных текстов). В современных алгоритмах этим операциям чаще всего подвергаются блоки последовательных битов. Некоторые методики можно описать как осуществление операции подстановки над полным сообщением.
Подстановки и перестановки производятся по определенным правилам. При этом надежда возлагается "на то, что эти правила и/или используемые в них параметры известны только автору и получателю шифрованного сообщения и неизвестны посторонним лицам. В докомпьютерную эру старались засекретить обе составляющие процесса шифрования. Сейчас для шифрования, как правило, используют стандартные алгоритмы, секретность же сообщения достигается путем засекречивания используемого алгоритмом параметра, ключа (key).
Прочтение секретного сообщения посторонним лицом, теоретически, может быть осуществлено двумя способами: похищением ключевого значения либо его угадыванием путем анализа перехваченной шифровки. Если первое мероприятие может быть предотвращено только физической и организационной защитой, то возможность второго определяется используемым алгоритмом. Ниже мы будем называть процесс анализа шифровки взломом шифра, а человека, осуществляющего этот процесс, – взломщиком. По-научному эта деятельность называется более нейтрально – криптоанализ.
К примеру, сообщение на естественном языке, зашифрованное подстановкой отдельных букв, уязвимо для частотного анализа: основываясь на том факте, что различные буквы встречаются в текстах с разной частотой, взломщик легко – и с весьма высокой достоверностью – может восстановить таблицу подстановки. Существуют и другие примеры неудачных алгоритмов, которые сохраняют в неприкосновенности те или иные присутствовавшие в сообщении автокорреляции – каждый такой параметр можно использовать как основу для восстановления текста сообщения или обнаружения ключа.
Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостыо алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произвести полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требованию сообщение. При использовании ключей достаточно большой разрядности такая атака оказывается чрезмерно дорогой, однако прогресс вычислительной техники постоянно сдвигает границу "достаточности" все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взломала сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы [www.distributed.net]!
Простым и эффективным способом борьбы с такой атакой является расширение пространства ключей. Увеличение ключа на один бит приводит к увеличению пространства вдвое – таким образом, линейный рост размера ключа обеспечивает экспоненциальный рост стоимости перебора. Некоторые алгоритмы шифрования не зависят от разрядности используемого ключа – в этом случае расширение достигается очевидным способом. Если же в алгоритме присутствует зависимость от разрядности, расширить пространство можно, всего лишь применив к сообщению несколько разных преобразований, в том числе и одним алгоритмом, но с разными ключами. Еще один способ существенно усложнить работу взломщику – это упаковка сообщения перед шифрованием и/или дополнение его случайными битами.
Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа является лишь оценкой объема пространства ключей сверху, и во многих ситуациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному условию – например, RSA использует простые Числа. Это резко сужает объем работы по перебору, поэтому для обеспечения сопоставимой криптостойкости разрядность ключа RSA должна быть намного больше, чем у алгоритмов, допускающих произвольные ключи.