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

Понятие криптографии. Подстановка. Перестановка.

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

Проще всего обеспечить защиту данных, лишив потенциальных злоумышленников доступа к физическому носителю данных или физическому каналу, по которому происходит их передача. К сожалению, иногда это невыполнимо. В этом случае на помощь приходят методики, собирательное название которых — криптография (κρyπτoγαψιoσ — тайнопись). В отличие от большинства терминов компьютерной лексики это слово не английского, а греческого происхождения.

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

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

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

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