Теория информационных систем. Страница 14.

Параллельная четность

Широко известный и применяемый код Хэмминга (Hamming code) находится в близком родстве с параллельной четностью. Его теоретическое обоснование несколько менее очевидно, чем у предыдущего алгоритма, но в реализации он, пожалуй, даже проще [Берлекэмп 1971]. Идея алгоритма состоит в том, чтобы снабдить блок данных несколькими битами четности, подсчитанными по различным совокупностям битов данных. При выполнении неравенства Хэмминга (1.1) сформированный таким образом код обеспечивает обнаружение и исправление одиночных ошибок либо гарантированное обнаружение (но не исправление!) двойных ошибок. Важно подчеркнуть гарантию обнаружения, в отличие от всего лишь высокой вероятности обнаружения при использовании CRC.

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

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

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

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

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

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