Вскрытие машинного шифра
Машинные шифры в принципе много сложнее ручных и их раскалывание скорее напоминает не подбор отмычки к сейфу, а высверливание его механизма. Тем не менее, если силу прикладывать неразумно, то вряд ли можно будет добиться успеха. Рассмотрим лишь простенький древний машинный шифр.
Одна из первых систем шифрования опробовалась в начале XX века на телеграфе. Она основывалась на том, что каждый символ кодировался 5 импульсами тока, а это вполне соответствует пяти битам представления этого кода в ЭВМ. Смысл шифра состоял в перестановке этих импульсов или, соответственно, бит по сложному закону с большим периодом. В частности от двоичного счетчика с n разрядами поступало n сигналов на релейные схемы, меняющие местами 2 бита. Так как n было велико, то такие перестановки пар бит, называемые математиками транспозициями, могли в принципе дать любую перестановку бит внутри кода символа. Однако если все биты равны нулю или единице, то, как их не переставляй, их совокупность не изменится. Если не все биты равны между собой, то может произойти замена символа. Число вариантов замены зависит от числа нулевых бит в коде символа:
число нулевых бит 0 1 2  3 4 5
число единичных битp; 5 4 3 2 1 0
число вариантов 1 5 10 10 5 1
Предположим, что буква А кодируется 00000, Б как 00001 и так далее до Я - 11111. В этом случае букве А при любых перестановках бит будет соответствовать только она сама. Букве Б могут соответствовать уже 5 вариантов: Б(00001), В(00010), Д(00100), И(01000), Р(10000). Поэтому, написав под каждой буквой шифровки все буквы сообщения, которые возможно ей соответствуют, получим таблицу, содержащую все варианты прочтения шифровки. Для того, чтобы облегчить чтение, варианты расшифровки каждой буквы в таблице расположены сверху вниз в порядке убывания их вероятности, что выполнено на ЭВМ с учетом априорной информации о чередовании букв в тексте на естественном языке. В верхней строке таблицы дан исходный текст сообщения, а во второй - шифровка, полученная случайной перестановкой бит у каждой буквы. Далее приведены альтернативные варианты прочтения букв. Причем, чем ниже приведен вариант, тем менее он правдоподобен, а варианты с вероятностью прочтения ниже 0.05 отброшены. Программа на ЭВМ попыталась найти и наиболее вероятное прочтение шифровки используя для этого данные о вероятностях биграмм текста на русском языке. Предложенный ей вариант прочтения букв выделен жирными символами:
| ЖИЛИ | БЫЛИ | СТАРИК | СО | СТАРУХОЙ | текст |
| МДЩВ | БЮХД | ЕСАВРЖ | ЕЛ | ЕКАДЦНЬТ | шифр |
| СИНИ | ВыхИ | СТАВИЕ | Сл | СТАВОЛьг | 1 |
| Мров | бчЛв | мк брм | мО | мк блзОИ | 2 |
| СИНИ | ВЫЛИ | СТАВИЕ | СО | СТАВОЛОЙ | прочтение |
Попробуем теперь сделать выводы из рассмотренных примеров: что помогает и что мешает раскалыванию шифров. Помогает криптографической атаке на шифр в основном то обстоятельство, что буквы и слова в тексте взаимосвязаны. Так, например, было несложно отгадать слово АККУ?А?НО и даже по фрагменту НАС ЗЛОБ определить песню, откуда он взят. Такая внутренняя зависимость участков текста друг от друга - свойство естественного языка и от него никуда не денешься. Хотя были и есть языки с гораздо меньшей зависимостью, чем у русского языка, но не заставишь же их использовать для того, чтобы решить проблемы шифрования. Другой помощник криптоаналитика - малое число вариантов соответствия текста шифровке при незнании ключа. Так в шифре Гронсфельда букве шифровки могут соответствовать лишь 10 букв из текста, а в шифре перестановки бит и того меньше, в среднем 7. Способствует вскрытию шифра и малая длина ключа - вряд ли так легко мы разделались бы с шифром Гронсфельда, если длина ключа превышала длину сообщения. И, в конце концов, почему же так просто был вскрыт многоалфавитный шифр замены? Ведь у него и число вариантов для отгадывания было велико, и ключ длинный. Причина успеха его взлома заключается в сильной зависимости ключа, текста и шифровки меж собой. Шифровка известна всегда. Поэтому сначала, мы угадали кусок текста и сразу же за это в награду получили кусок ключа. По этому куску ключа удалось восстановить весь ключ целиком.
Итак, во-первых, если кусок- ключа можно было получить, отгадав лишь очень большую часть текста или перебрав множество вариантов, то этот номер не прошел бы. Во-вторых, это не дело, когда по малому участку ключа удается угадать весь ключ. Будь ключ представлен не осмысленным текстом, а случайным, то этого не удалось бы. Во всех современных системах шифрования открытый текст обязательно сжимается перед шифрованием. Сжимать шифрованный текст слишком поздно, так как шифровки почти несжимаемы. Кроме экономии места под хранение и времени передачи, сжатие еще и повышает стойкость шифра. Многие атаки на шифр осуществляются поиском фрагмента открытого текста в шифровке. Если отрытый текст перед шифрованием был сжат, то эти атаки затруднены и потери времени на сжатие окупаются.
Теперь давайте пофантазируем, как составить нераскрываемый шифр. Если мы возьмем за основу многоалфавитный шифр замены, то это будет неплохой выбор, он многовариантен и к нему так просто не подступишься. Однако ключ для шифровки должен быть очень хорош: бесконечной длины и, конечно же, несмысловой. Можно схитрить и составить ключ из текста, беря из него лишь каждую третью букву, ведь по фрагменту ДНВТДМИН никогда не скажешь, что он взят из той же "Варшавянки". Еще лучше, если сообщение зашифровано дважды разными ключами и шифрами разных типов. Далее, скверно, когда символы всегда находятся в том же месте в шифровке, что и в сообщении - на подпись, заголовок или другой известный фрагмент текста может начаться атака. Поэтому вместе с заменой применим простой шифр двойной перестановки - пусть взломщики поищут, где теперь находится подпись. Таким способом, комбинируя шифр перестановки с многоалфавигным шифром замены при хорошем ключе, можно получить вполне приемлемый ручной шифр, вскрыть который будет очень непросто или вообще невозможно.
Но сменим галоп нашего рассуждения на шаг, чтобы предостеречь читателя от одной широко распространенной ошибки. Насколько осложнится вскрытие сообщения, если его зашифровать несколько раз одним ключом? Ответ естественный, хотя для многих и неожиданный, взломка сложнее вряд ли станет. Во времена Второй мировой войны английским криптографам не давал покоя простой, но заковыристый немецкий полицейский шифр. Из-за краткости сообщений его чтение удавалось далеко не всегда и, как правило, с большими трудностями. Немецкие криптографы об этом не знали, решив улучшить шифр, как бы удвоив примененный ключ. Так вот, после такого "усложнения" вскрытие шифровок стало легким и приятным. В известном автору аналогичном случае, имевшем место некогда в известной фирме, текст был зашифрован дважды. Шифровка криптоаналитиком была восстановлена из свободных кластеров на рабочей дискете, а в директории остались следы от двойного шифрования и длины двух файлов типа ВАК того же сообщения. Из этих следов и сопоставления длин шифровки с длинами файлов стало ясно, что текст зашифрован дважды. По заголовку файла была определена программа шифрования. Так как во второй раз был зашифрован и текст сообщения, и заголовок файла шифровки, содержание которого отчасти известно, то найти второй ключ удалось просто подбором, потому что он был всего из 5 букв по имени владельца. Первый ключ был угадан после этого сразу же, так как стало ясно пристрастие автора файла к собственному имени. Вследствие этого, примите за правило никогда не шифровать одно сообщение дважды одним и тем же ключом, чтобы не усложнять себе жизнь лишней работой. Применение нескольких разных ключей порой оправдано, если не из-за увеличения стойкости шифра, то хотя бы как свидетельство о согласии нескольких отправителей шифровки или одновременном присутствии нужных получателей сообщения.
Лучшие известные криптографические системы, преимущественно принадлежащие правительствам, практически невозможно вскрыть. Однако все государства теми или иными путями пытаются сдержать и даже запретить свободное использование криптографии, как вызывающее головную боль у их секретных служб. В то время, как ЦРУ в США призывает фирмы шире использовать шифрование, то АНБ пытается ограничить длину ключа 40 битами. В последнем случае возможен даже прямой перебор ключей, если использовать достаточно мощную ЭВМ. По оценкам специалистов, раскалывание шифра алгоритма RC-4 с ключом из 40 бит, широко используемого в сети Internet, потребует около 100 MIPS (MIPS - million instructions per second - миллион операций в секунду.) лет. Раньше считалось, что меньше, чем за 6 месяцев работы суперкомпьютера, такой шифр вскрыт не будет. Эта оценка была проверена практически и оказалось, что 120 рабочих станций с двумя суперкомпьютерами параллельного действия взломали ключ за, 8 дней. Цена такого раскалывания достаточно высока и превышает $10000, что впрочем сильно зависит от эффективности алгоритма атаки. Поэтому проблемы криптоанализа еще долгое время будут весьма актуальны.
