| На практике применяются в основном лишь два типа классических шифров: шифры замены и шифры перестановки. В шифре замены позиции символов (битов) в шифртексте не изменяются, но заменяются символы по какому-либо закону криптографического преобразования. В шифре перестановки все символы (в других случаях биты) открытого текста не изменяются, но перемещаются с их исходной позиции. Комбинации этих двух типов образуют большинство практически реализованных классических (симметричных) шифров. |
| Сообщения, независимо от их структуры и сложности, всегда можно свести к последовательности знаков. Эти знаки берутся из заранее фиксированного множества, например, русского алфавита, таблицы ASCII или палитры цветов (красный, желтый, зеленый). Разные знаки встречаются в сообщениях с разной частотой. Поэтому количество информации, передаваемой разными знаковыми системами, будет разным. Бит, в теории информации, это количество информации уменьшающее неопределенность вдвое. Ответ на вопрос, есть ли спички в коробке, имеет два варианта: "Да или нет", и уменьшает вдвое неопределенность. В определении информации по Шеннону, количество информации определяется средним числом вопросов с ответами, ДА или НЕТ необходимых для того, чтобы предсказать следующий символ сообщения. Если предположить, что символы в тексте сообщения следуют независимо друг от друга (статистически независимы), то среднее количество информации приходящееся на один знак, равно: |
| , где Ld - двоичный логарифм. |
| Cообщения человеческого языка занимают места больше, чем это реально необходимо для передачи сообщения. Это называют избыточностью языка, которое можно легко наблюдать, сравнивая размеры текстового файла до и после архивации. Буквы в тексте сообщения появляются с разной частотой (или другими словами вероятностью). Причем в разных языках эти частоты разные. Можно построить алгоритм распознавания языка сообщения по частотам символов, встречающимся в сообщении. На этом же принципе основана простейшая криптоатака: вычисляются вероятности появления символов и по ним пытаются угадать их первоначальное значение. |
| Отсюда вывод: для построения шифрсистемы перед шифрованием открытый текст сначала необходимо подвергнуть архивации. Алгоритмы архивации выходят за рамки данной статьи. |
| Однако определение количества информации по Шеннону неверно при ближайшем рассмотрении – символы в сообщении не являются независимыми друг от друга. Можно привести пример хрестоматийной фразы: "Казнить, нельзя помиловать", смысл которой изменяется на противоположный в зависимости от положения единственной запятой. |
| Для уточнения количества информации в сообщении исследуют зависимость символа от предыстории, вычисляя вероятности появления в тексте биграмм, триграмм и т.д. В теории вероятностей это называется построением Марковских цепей. Подобный анализ является также более сильным инструментом для криптоатаки. В самом деле, сообщения часто начинаются с обращения, заканчиваются подписью с реквизитами адресата, официальные документы начинаются со стандартных заголовков. Это дает предсказуемые участки открытого текста для криптоанализа. Другая особенность "живых" языков – это согласование окончаний в падежах, родах, числах. Эта особенность хорошо прослеживается на примере русского и немецкого языков, что порой однозначно определяет следующий символ в тексте сообщения. Более точный семантический анализ сложнее, чем простое построение Марковских цепей, он предполагает разбор грамматических, орфографических конструкций, работу с идиомами и лексикой. |
| Отсюда следующий вывод: для построения шифр системы текст нужно преобразовать алгоритмом перестановки, для того чтобы "убить" марковость. Алгоритмы 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) |
