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

Сообщения, независимо от их структуры и сложности, всегда можно свести к последовательности знаков. Эти знаки берутся из заранее фиксированного множества, например, русского алфавита, таблицы ASCII или палитры цветов (красный, желтый, зеленый). Разные знаки встречаются в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаковыми системами, будет разным. В теории информации "бит" - это количество информации, уменьшающее неопределенность вдвое. Ответ на вопрос, есть ли спички в коробке, имеет два варианта: "да" или "нет", и уменьшает вдвое неопределенность. По Шеннону, количество информации определяется средним числом вопросов с ответами "ДА-НЕТ", необходимых для того, чтобы предсказать следующий символ сообщения. Если предположить, что символы в тексте сообщения следуют независимо друг от друга (статистически независимы), то среднее количество информации, приходящееся на один знак, равно:

H=P_iLd(P_i), где Ld - двоичный логарифм.

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

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

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

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

Отсюда следующий вывод: для построения шифросистемы текст нужно преобразовать алгоритмом перестановки для того, чтобы "убить" марковость. Алгоритмы DES, Lucifer, IDEA основаны в первую очередь на алгоритмах перестановки, другими словами, на взбивании. Их еще называют "шифры-взбивалки".

Простейший вариант реализации шифров перестановки - это использование двумерных таблиц. Возьмем, к примеру, открытый текст, используемый в Windows 95, как текст бегущей строки по умолчанию: "Философия - отыскивание сомнительных причин в обоснование того, во что веришь инстинктивно." Здесь 91 символ - сделаем запись в квадратную таблицу 10х10. Для удобства все буквы запишем прописным равноширинным шрифтом. Транспонируем матрицу и выпишем полученный шифротекст:

"Ф-АИПБЕОИНИ НТРО ШКЛОИЕЧСТЧЬТОТЕЛИНОТ ИСЫ ЬНОГОИВОССН ВО ННФКОЫВА,ВСОИИМХ Н ЕТ.ЯВН ОИВРИ ". Шифровка готова.

ФИЛОСОФИЯ    Ф-АИПБЕОИН

- ОТЫСКИВА   И НТРО ШК

НИЕ СОМНИТ   ЛОИЕЧСТЧЬТ

ЕЛЬНЫХ ПРИ   ОТЕЛИНОТ И

ЧИН В ОБОС   СЫ ЬНОГОИВ

НОВАНИЕ ТО   ОССН ВО НН

ГО, ВО ЧТО   ФКОЫВА,ВСО

 ВЕРИШЬ ИН   ИИМХ Н ЕТ.

СТИНКТИВНО   ЯВН ОИВРИ 

Открытый текст  Шифротекст

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

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

Для реализации простейших шифров многозначной замены чаще всего используют операцию "сложение по модулю". Частный случай этой операции, сложение по модулю 2 - это операция XOR. Для шифрования берутся блок исходного текста и какая-либо последовательность символов, играющая роль ключа, и налагаются посимвольно друг на друга с помощью XOR. Дешифрование происходит так же: на шифротекст накладывается ключ с помощью XOR. Похожего результата можно достичь с помощью посимвольных ротационных сдвигов ROR и ROL для обратного преобразования. Всего возможных значений у байта 256, поэтому количество возможных знаков или комбинаций при преобразовании тоже 256. Для применения криптозакрытия полей в базах данных этот метод в чистом виде не годится, так нужно обеспечить фильтрацию служебных символов с номерами 0-31.

Другой способ замены - это наложение псевдослучайной последовательности на открытый текст. Вся проблема в том, чтобы подобрать псевдослучайную последовательность с большим периодом и не имеющую скрытых периодичностей. Функция RND из паскаля или бейсика не годится: период ее всего около 20000 и она лишь отдаленно напоминает равномерное распределение, то есть легко предсказуема и, соответственно, вскрываема.

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

Можно полемизировать по поводу применения "ручных" шифров и столпов криптографии, таких, как DES, IDEA или RSA. Применение DES в чистом виде к полям базы данных во многом подобно "выстрелу из пушки по воробьям", не говоря о том, что снизит производительность системы на несколько порядков. Это во-первых. Во-вторых, существуют так называемые "критические миссии", когда необходимо сгенерить шифр за полчаса "на бумажке". В-третьих, "ручной" шифр, построенный по канонам математической науки, сопоставим по стойкости с машинными шифрами.

Резюмируя, приведу план построения криптосистемы:

1. Подвергнуть открытый текст архивации для устранения избыточности сообщения.
2. Провести преобразование перестановкой для устранения зависимости символов от места нахождения в тексте (марковости).
3. Провести преобразование многозначной заменой для превращения текста в "информационный" шум.

Black Prince (WEREWOLF),
[email protected]