Реферат: Введение в криптографию

При хранении и передаче данных нередко возникает требование защитить их от нежелательного прочтения и/или модификации. Если задача защиты от нежелательной модификации решается обсуждавшимися в предыдущем разделе избыточными кодами, то с прочтением все существенно сложнее.

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

История криптографии насчитывает тысячи лет, и многие основополагаю­щие принципы современной криптографии известны, возможно, с доисто­рических времен, однако, существенный прогресс в теории шифрования был достигнут лишь относительно недавно, в связи с разработкой совре­менной теории информации.

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

Подстановки и перестановки производятся по определенным правилам. При этом надежда возлагается на то, что эти правила и/или используемые в них параметры известны только автору и получателю шифрованного сообщения и неизвестны посторонним лицам. В докомпьютерную эру старались засек­ретить обе составляющие процесса шифрования. Сейчас для шифрования, как правило, используют стандартные алгоритмы, секретность же сообще­ния достигается путем засекречивания используемого алгоритмом парамет­ра, ключа (key).

Прочтение секретного сообщения посторонним лицом, теоретически, может быть осуществлено двумя способами: похищением ключевого значения либо его угадыванием путем анализа перехваченной шифровки. Если первое ме­роприятие может быть предотвращено только физической и организацион­ной защитой, то возможность второго определяется используемым алгорит­мом. Ниже мы будем называть процесс анализа шифровки взломом шифра, а человека, осуществляющего этот процесс, — взломщиком. По-научному эта деятельность называется более нейтрально — криптоанализ. К примеру, сообщение на естественном языке, зашифрованное подстанов­кой отдельных букв, уязвимо для частотного анализа: основываясь на том факте, что различные буквы встречаются в текстах с разной часто­той, взломщик легко — и с весьма высокой достоверностью — может восстановить таблицу подстановки. Существуют и другие примеры неудач­ных алгоритмов, которые сохраняют в неприкосновенности те или иные присутствовавшие в сообщении автокорреляции — каждый такой параметр можно использовать как основу для восстановления текста сообщения или обнаружения ключа.

Устойчивость шифра к поиску автокорреляций в сообщении называется криптостойкостью алгоритма. Даже при использовании удачных в этом смысле алгоритмов, если взломщик знает, что исходные (нешифрованные) данные удовлетворяют тому или иному требованию, например, содержат определенное слово или снабжены избыточным кодом, он может произве­сти полный перебор пространства ключей: перебирать все значения ключа, допускаемые алгоритмом, пока не будет получено удовлетворяющее требо­ванию сообщение. При использовании ключей достаточно большой разряд­ности такая атака оказывается чрезмерно дорогой, однако прогресс вычис­лительной техники постоянно сдвигает границу «достаточности» все дальше и дальше. Так, сеть распределенных вычислений Bovine в 1998 году взлома­ла сообщение, зашифрованное алгоритмом DES с 56-разрядным ключом за 56 часов работы [www.distributed.net]!

Простым и эффективным способом борьбы с такой атакой является расши­рение пространства ключей. Увеличение ключа на один бит приводит к уве­личению пространства вдвое — таким образом, линейный рост размера ключа обеспечивает экспоненциальный рост стоимости перебора. Некото­рые алгоритмы шифрования не зависят от разрядности используемого клю­ча—в этом случае расширение достигается очевидным способом. Если же в алгоритме присутствует зависимость от разрядности, расширить пространст­во можно, всего лишь применив к сообщению несколько разных преобразо­ваний, в том числе и одним алгоритмом, но с разными ключами. Еще один способ существенно усложнить работу взломщику — это упаковка сообще­ния перед шифрованием и/или дополнение его случайными битами.

Важно подчеркнуть, впрочем, что количество двоичных разрядов ключа яв­ляется лишь оценкой объема пространства ключей сверху, и во многих си­туациях эта оценка завышена. Некоторые алгоритмы в силу своей природы могут использовать только ключи, удовлетворяющие определенному усло­вию — например, RSA использует простые числа. Это резко сужает объем работы по перебору, поэтому для обеспечения сопоставимой криптостойко-сти разрядность ключа RSA должна быть намного больше, чем у алгорит­мов, допускающих произвольные ключи.

Низкая криптостойкость может быть обусловлена не только алгоритмом шифрования, но и процедурой выбора ключа: если ключ может принимать любые двоичные значения заданной разрядности, но реально для его выбора используется страдающий неоднородностью генератор псевдослучайных чи­сел, мы можем значительно сократить объем пространства, которое реально должен будет перебрать взломщик наших сообщений (вопросы генерации равномерно распределенных псевдослучайных чисел обсуждаются во втором томе классической книги [Кнут 2000]). Еще хуже ситуация, когда в качестве ключа используются «легко запоминаемые» слова естественного языка: в этом случае реальный объем пространства ключей даже довольно большой разрядности может измеряться всего лишь несколькими тысячами различ­ных значений.

Современные алгоритмы шифрования делятся на два основных класса: с секретным и с публичным ключом (кажущееся противоречие между тер­мином «публичный ключ» и приведенными выше рассуждениями будет разъяснено далее).

Алгоритмы с секретным ключом, в свою очередь, делятся на потоковые (stream) и блочные (block). Потоковые алгоритмы обычно используют под­становку символов без их перестановки. Повышение криптостойкости при этом достигается за счет того, что правила подстановки зависят не только от самого заменяемого символа, но и от его позиции в потоке.

Примером простейшего — и в то же время абсолютно не поддающегося взлому — потокового алгоритма является система Вернама или одноразовый блокнот. Система Вернама основана на ключе, размер которого равен размеру сообщения или превосходит его. При передаче двоичных данных подстановка осуществляется сложением по модулю 2 (операцией исключающего или) соответствующих битов ключа и сообщения.

Если ключ порожден надежным генератором случайных чисел (например, правильно настроенным оцифровщиком теплового шума), никакая инфор­мация об автокорреляциях в исходном тексте сообщения взломщику не по­может: перебирая полное пространство ключей, взломщик вынужден будет проверить все сообщения, совпадающие по количеству символов с исходным, в том числе и все сообщения, удовлетворяющие предполагаемому автокор­реляционному соотношению.

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

Более практичным оказалось применение в качестве ключа псевдослучай­ных последовательностей, порождаемых детерминированными алгоритмами, В промежутке между первой и второй мировыми войнами широкое распро­странение получили шифровальные машины, основанные на механических генераторах таких последовательностей. Чаще всего использовались сочетания, получаемые при вращении колес с взаимно простыми количествами зубцов.

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

В системах цифровой связи широкое применение получили блочные алго­ритмы, выполняющие над блоками данных фиксированной длины последо­вательности — иногда довольно сложные — перестановок, подстановок и других операций, чаще всего двоичных сложений данных с ключом по ка­кому-либо модулю. В операциях используются компоненты ключевого слова относительно небольшой разрядности.

Например, широко применяемый блочный алгоритм DES шифрует 64-битные блоки данных 56-битным ключом. Полное описание алгоритма при­водится в документе [NBS FIPS PUB 46, 1977]. Русский перевод этого документа может быть найден в приложениях к книге [Дейтел 1987]. Для современной вычислительной техники полный перебор 56-битного про­странства — «семечки», поэтому сейчас все большее распространение полу­чают алгоритмы с большей разрядностью ключа — Blowfish, IDEAL и др. [Анин 2000].

Шифры с открытым ключом называются также двухключевыми. Если в ал­горитмах со скрытым ключом для кодирования и декодирования сообщений используется один и тот же ключ, то здесь используются два ключа: пуб­личный и приватный. Для прочтения сообщения, закодированного публич­ным ключом, необходим приватный, и наоборот.

Помимо обычных соображений криптостойкости, к таким алгоритмам предъявляется дополнительное требование: невозможность восстановле­ния приватного ключа по публичному иначе как полным перебором пространства ключей.

Двухключевые схемы шифрования намного сложнее в разработке, чем схе­мы с секретным ключом: требуется найти преобразование, не поддающееся обращению при помощи применявшегося в нем публичного ключа, *но та­кое, чтобы с применением приватного ключа его все-таки можно было об­ратить. Известные криптоустойчивые схемы основаны на произведениях простых чисел большой разрядности, дискретных логарифмах и эллиптиче­ских кривых. Наиболее широкое применение получил разработанный в 1977 г. алгоритм RSA [www.rsa.com FAQ].

Известные двухключевые алгоритмы требуют соответствия ключей весьма специфическим требованиям, поэтому для достижения криптостойкости, сопоставимой с блочными алгоритмами, необходимо использовать ключи намного большей разрядности. Так, снятые в 2000 году ограничения Мини­стерства торговли США устанавливали ограничения разрядности ключа, ко­торый мог использоваться в экспортируемом за пределы США профаммном обеспечении: для схем с секретным ключом устанавливался предел, равный 48 битам, а для схем с открытым — 480.

Использование ключей большой разрядности требует значительных вычис­лительных затрат, поэтому двухключевые схемы чаще всего применяются в сочетании с обычными: обладатель публичного ключа генерирует случайную последовательность битов, кодирует ее и отправляет обладателю приватного ключа. Затем эта последовательность используется в качестве секретного ключа для шифрования данных. При установлении двустороннего соедине­ния стороны могут сначала обменяться своими публичными ключами, а за­тем использовать их для установления двух разных секретных ключей, ис­пользуемых для шифрования данных, передаваемых в разных направлениях.

Такая схема делает практичной частую смену секретных ключей: так, в про­токоле SSH ключ генерируется на каждую сессию [www.cs.hut.fi SSH]; в про­токоле виртуальных приватных сетей IPSEC время жизни ключа ограничено восемью часами [redbooks.ibm.com sg245234.pdf].

Еще более широкое применение двухключевые схемы нашли в области ау­тентификации и электронной подписи. Электронная подпись представляет собой контрольную сумму сообщения, зашифрованную приватным ключом отправителя. Каждый обладатель соответствующего публичного ключа мо­жет проверить аутентичность подписи и целостность сообщения. Это может использоваться для проверки аутентичности как сообщения, так и самого отправителя. Использование в качестве контрольной суммы обычного CRC невозможно, потому что генерация сообщения с заданным CRC не представляет вычислительной сложности. Для применения в электронной подписи были разработаны специальные алгоритмы вычисле­ния контрольных сумм, затрудняющие подбор сообщения с требуемой сум­мой [RFC 1320, RFC 1321].