На практике применяются в основном лишь два типа классических шифров: шифры замены и шифры перестановки. В шифре замены позиции символов (или битов) в шифротексте не изменяются, заменяются сами символы в соответствии с некоторым законом криптографического преобразования. В шифре перестановки все символы (в других случаях - биты) открытого текста не изменяются, а перемещаются с их исходной позиции. Комбинации этих двух типов образуют большинство практически реализованных классических (симметричных) шифров.
Сообщения, независимо от их структуры и сложности, всегда можно свести к последовательности знаков. Эти знаки берутся из заранее фиксированного множества, например, русского алфавита, таблицы ASCII или палитры цветов (красный, желтый, зеленый). Разные знаки встречаются в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаковыми системами, будет разным. В теории информации "бит" - это количество информации, уменьшающее неопределенность вдвое. Ответ на вопрос, есть ли спички в коробке, имеет два варианта: "да" или "нет", и уменьшает вдвое неопределенность. По Шеннону, количество информации определяется средним числом вопросов с ответами "ДА-НЕТ", необходимых для того, чтобы предсказать следующий символ сообщения. Если предположить, что символы в тексте сообщения следуют независимо друг от друга (статистически независимы), то среднее количество информации, приходящееся на один знак, равно:
H=PiLd(Pi), где 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 в чистом виде к полям базы данных во многом подобно "выстрелу из пушки по воробьям", не говоря о том, что снизит производительность системы на несколько порядков. Это во-первых. Во-вторых, существуют так называемые "критические миссии", когда необходимо сгенерить шифр за полчаса "на бумажке". В-третьих, "ручной" шифр, построенный по канонам математической науки, сопоставим по стойкости с машинными шифрами.
Резюмируя, приведу план построения криптосистемы:
- Подвергнуть открытый текст архивации для устранения избыточности сообщения.
- Провести преобразование перестановкой для устранения зависимости символов от места нахождения в тексте (марковости).
- Провести преобразование многозначной заменой для превращения текста в "информационный" шум.
Black Prince (WEREWOLF),
[email protected]
![Версия для печати Версия для печати](https://www.kv.by/sites/all/modules/print/icons/print_icon.png)
Горячие темы