ключа равна произведению вероятностей биграмм, состоящих из
символа по этому варианту расшифровки и следующего за ним, уже
известного символа. Если Li - буква текста, стоящая на месте i,
то вероятность одного из 10 вариантов:
р (L1L2) p(L4L5) р(L7L8) p(L10L11) p(L13L14) p(L16L17)
Для вычисления вероятности биграмм воспользуемся таблицей из
приложения. Поскольку в ней даны логарифмы вероятностей биграмм,
то их достаточно суммировать. В результате для вариантов от 0 до
3 имеем такие численные значения вероятностей:
р(0)=р(ФО)р(ИР)р(ИН)р(С)р(ИК)р(ИТ)=43
р(1)=р(УО)р(ЗР)р(ЗН)р(Р)р(ЗК)р(ЗТ)=23
р(2)=р(ТО)р(ЖР)р(ЖН)р(П)р(ЖК)р(ЖТ)=27
р(3)=р(СО)р(ЕР)р(ЕН)р(О)р(ЕК)р(ЕТ)=50
В результате для первой цифры ключа получается наиболее
вероятным 3 вариант расшифровки. Это дает следующую таблицу:
ключ 31?31?31?31?31?31?3
вариант 0 Ж Ь С Х Ф С
вариант 1 ОЕ РЫ HP Ф КУ ТР
вариант 2 Д Ъ П У Т П
вариант 3 С ГЕ ЩЕ ОО ТЕ С ОО
вариант 4 в т н с р н
вариант 5 Б Ч М Р П М
вариант 6 А Ц Л П О Л
вариант 7 Х К О Н К
вариант 8 Я Ф Й Н М Й
вариант 9 Ю У И М Л И
сообщение СО?ЕР?ЕН?0?ЕК?РТ?0
Теперь сообщение читается совсем просто. Достаточно выбрать
одну из 10 строк с вариантом для 3 цифры ключа. В результате
получим ключ и текст сообщения:
сообщение: СОВЕРШЕННО СЕКРЕТНО
ключ: 3143143143143143143
В принципе есть возможность чтения шифра Гронсфельда
напрямую, анализом таблицы возможных замен, даже если ключ
длинный. При достаточно большой длине текста в таблице будут
несложно прочитываемые участки. Использование ЭВМ для подключения
к криптографической атаке на этот шифр априорных знаний о
чередовании русских букв в тексте обычно позволяет без труда
читать подобные шифровки.
При многоалфавитной замене с длинным ключом использованный
для взлома шифра Гронсфельда прием уже не подходит. Однако
известно, что шифры русских революционеров цифирная палата легко
читала. Как же это удавалось сделать - черная магия? Все гораздо
проще. Приведем короткий пример: перехвачена шифровка, вероятным
автором которой является Троцкий. Известно также, что аналогичные
шифровки делались методом сложной замены и в качестве ключа
использовались тексты революционных песен, а иногда стихотворения
Пушкина, Лермонтова и Некрасова. Так как отправитель Троцкий, то
естественно предположить, что сообщение оканчивается подписью
ТРОЦКИЙ с предыдущим пробелом. Подставив ее в шифровку вместо
ключа, получим кусок настоящего ключа.
Шифровка ДДЯ Л ЫСЫ ШНМРКЮЮЩДБЬИЬМЫМТАНЭХЦК
Сообщение????????????????????????? ТРОЦКИЙ
Ключ?????????????????????????НАС ЗЛОБ
Не напоминает ли фрагмент НАС ЗЛОБ какойто известный текст?
Не правда ли, очень похоже на слова, переведенной Кржижановским
песни польского восстания 1863 года, называемой "Варшавянкой"?
Теперь, подставив разгаданный ключ в виде текста песни: ВИХРИ
ВРАЖДЕБНЫЕ ВЕЮТ НАД НАМИ ТЕМНЫЕ СИЛЫ НАС ЗЛОБ, можно вскpыть само
сообщение:
ОБЫВАТЕЛИ СПАЛИ НЕ ЗНАЯ ЧТО МЕНЯЕТСЯ
ВЛАСТЬ ТРОЦКИЙ
Такая расшифровка вряд ли заняла бы вместе с составлением
сопроводительной записки более часа времени. Ну, а предположим,
что отправитель неизвестен? И это не беда, хотя потребует больше
времени. Несложно перебрать несколько возможных имен, а в случае
неудачи придется подставлять в разные места часто употребляемые
слова текста и ключа - ТОВАРИЩ, ВЛАСТЬ, ВОССТАНИЕ. Отгадав одно
из двух - текст или ключ, сразу получим второе.
Вот как немцы описали вскрытие ручных шифров советской группы
шпионов "Красная Капелла", полностью уничтожить которую Мюллер,
Канарис и Шелленберг не смогли, несмотря на многие аресты ее
участников с начала и до конца войны: "Тем временем
математический отдел разведки и служба расшифровки Главного
командования вермахта лихорадочно работала над найденным в
особняке наполовину обуглившимся обрывком зашифрованного текста
радиопередачи. Они пришли к выводу, что ключ к шифру находится в
тексте какой-то французской книги (Язык сообщения и тип шифра
стали известны после того, как арестованная бельгийская
консьержка на допросах сообщила о пристрастии агентов "Красной
Капеллы" к чтению французских романов, часть названий которых она
вспомнила.). Из крошечного обрывка сожженного листка бумаги
специалисты после кропотливых исследований сумели
реконструировать слово ПРОКТОР. Теперь, следовало выяснить, в
каких книгах встречается это ключевое слово. Через три месяца мы
разыскали эту книгу. Тогда специалисты отдела расшифровки
Главного командования вермахта принялись за работу, чтобы
раскусить шифр. Они смогли расшифровать обнаруженные в Брюсселе и
перехваченные заново радиопередачи."
Еще один короткий пример вскрытия многоалфавитного шифра
замены приведем из-за его занимательной истории. Писатель Эдгар
По считал себя непревзойденным криптоаналитиком. Ему принадлежит
дерзкое высказывание: "...можно смело утверждать, что
человеческий гений не в силах составить шифр, раскрыть который
оказалось бы не под силу человеческому гению". Поэтому в 1839
году он бросил вызов читателям Журнала "Alexander's Weekly
Messenger", утверждая, что расколет любой их шифр замены. Некто
Калп в 1840 году прислал ему такой текст шифровки:
GE JEASGDXV, ZIJ GL MW, LAAM, XZY...
Эдгар По, предполагавший, что будет предложен шифр простой
замены, счел пример Калпа "мешаниной случайных букв". Однако в
1975 году слушатели лекций по криптологии Винкель и Листер
расшифровали его, предположив многоалфавитную замену вместо
простой. Скорее всего они начали с первых двух слов, увидев в них
искаженное имя получателя ALEXANDER как ALXANDER:
Шифpовка GE JEASGDXV
Сообщение MR ALXANDER
Ключ UN JTDSTATE
Полученная частная расшифровка была очень похожа на фразу
UNITED STATES и, повторяя ее циклически, они вскрыли весь текст
шифровки. Стало ясно, что даже если бы дилетант По и знал о
многоалфавитных шифрах, то взламывание текста-шифровки Калпа
представляло собой серьезную задачу: одна буква в шифровке была
пропущена, а 15 искажены скорее всего по вине наборщика. Этот
пример показывает, что ошибки в шифровании способны озадачить не
только криптоаналитика, но и легального получателя сообщения,
обладающего ключом. Ведь из-за пропущенной пятой буквы текста
шифровки весь ее остаток был нечитаемым!
Вскрытие машинного шифра
Машинные шифры в принципе много сложнее ручных и их
раскалывание скорее напоминает не подбор отмычки к сейфу, а
высверливание его механизма. Тем не менее, если силу прикладывать
неразумно, то вряд ли можно будет добиться успеха. Рассмотрим
лишь простенький древний машинный шифр.
Одна из первых систем шифрования опробовалась в начале XX
века на телеграфе. Она основывалась на том, что каждый символ
кодировался 5 импульсами тока, а это вполне соответствует пяти
битам представления этого кода в ЭВМ. Смысл шифра состоял в
перестановке этих импульсов или, соответственно, бит по сложному
закону с большим периодом. В частности от двоичного счетчика с n
разрядами поступало n сигналов на релейные схемы, меняющие
местами 2 бита. Так как n было велико, то такие перестановки пар
бит, называемые математиками транспозициями, могли в принципе
дать любую перестановку бит внутри кода символа. Однако если все
биты равны нулю или единице, то, как их не переставляй, их
совокупность не изменится. Если не все биты равны между собой, то
может произойти замена символа. Число вариантов замены зависит от
числа нулевых бит в коде символа:
число нулевых бит 0 1 2 3 4 5
число единичных бит 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
...дальше нет вариантов...
СИНИ ВЫЛИ СТАВИЕ СО СТАВОЛОЙ прочтение
Несмотря на немного смешной вид полученного текста, он
довольно-таки близок к оригиналу: отгадано 19 букв из 28!
Некоторое улучшение отгадывания может быть достигнуто переходом к
оценке вероятностей не по биграммам, а по триграммам -
трехбуквенным сочетаниям и даже полному словарю слов. Применение
в программе полного словаря дало вариант расшифровки: ЖИЛИ БЫЛИ
СТАРИК СО СТАРУХОЙ. Однако вряд ли кто лучше человека сможет
выбрать окончательный вариант прочтения. Из этого примера следует
важный вывод, что избыточность языка позволяет читать сообщение
даже при большой неоднозначности прочтения каждой отдельно взятой
буквы. В приведенном примере на одну букву в среднем приходится 7
вариантов ее прочтения. Практически, если число вариантов
прочтения каждой буквы не больше 7, то текст обычно прочесть
удается.
Попробуем теперь сделать выводы из рассмотренных примеров:
что помогает и что мешает раскалыванию шифров. Помогает
криптографической атаке на шифр в основном то обстоятельство, что
буквы и слова в тексте взаимосвязаны. Так, например, было
несложно отгадать слово АККУ?А?НО и даже по фрагменту НАС ЗЛОБ
определить песню, откуда он взят. Такая внутренняя зависимость
участков текста друг от друга - свойство естественного языка и от
него никуда не денешься. Хотя были и есть языки с гораздо меньшей
зависимостью, чем у русского языка, но не заставишь же их
использовать для того, чтобы решить проблемы шифрования. Другой
помощник криптоаналитика - малое число вариантов соответствия
текста шифровке при незнании ключа. Так в шифре Гронсфельда букве
шифровки могут соответствовать лишь 10 букв из текста, а в шифре
перестановки бит и того меньше, в среднем 7. Способствует
вскрытию шифра и малая длина ключа - вряд ли так легко мы
разделались бы с шифром Гронсфельда, если длина ключа превышала
длину сообщения. И, в конце концов, почему же так просто был
вскрыт многоалфавитный шифр замены? Ведь у него и число вариантов
для отгадывания было велико, и ключ длинный. Причина успеха его
взлома заключается в сильной зависимости ключа, текста и шифровки
меж собой. Шифровка известна всегда. Поэтому сначала, мы угадали
кусок текста и сразу же за это в награду получили кусок ключа. По
этому куску ключа удалось восстановить весь ключ целиком.
Итак, во-первых, если кусок-ключа можно было получить,
отгадав лишь очень большую часть текста или перебрав множество
вариантов, то этот номер не прошел бы. Во-вторых, это не дело,
когда по малому участку ключа удается угадать весь ключ. Будь
ключ представлен не осмысленным текстом, а случайным, то этого не
удалось бы. Во всех современных системах шифрования открытый
текст обязательно сжимается перед шифрованием. Сжимать
шифрованный текст слишком поздно, так как шифровки почти
несжимаемы. Кроме экономии места под хранение и времени передачи,
сжатие еще и повышает стойкость шифра. Многие атаки на шифр
осуществляются поиском фрагмента открытого текста в шифровке.
Если отрытый текст перед шифрованием был сжат, то эти атаки
затруднены и потери времени на сжатие окупаются.
Теперь давайте пофантазируем, как составить нераскрываемый
шифр. Если мы возьмем за основу многоалфавитный шифр замены, то
это будет неплохой выбор, он многовариантен и к нему так просто
не подступишься. Однако ключ для шифровки должен быть очень
хорош: бесконечной длины и, конечно же, несмысловой. Можно
схитрить и составить ключ из текста, беря из него лишь каждую
третью букву, ведь по фрагменту ДНВТДМИН никогда не скажешь, что
он взят из той же "Варшавянки". Еще лучше, если сообщение
зашифровано дважды разными ключами и шифрами разных типов. Далее,
скверно, когда символы всегда находятся в том же месте в
шифровке, что и в сообщении - на подпись, заголовок или другой
известный фрагмент текста может начаться атака. Поэтому вместе с
заменой применим простой шифр двойной перестановки - пусть
взломщики поищут, где теперь находится подпись. Таким способом,
комбинируя шифр перестановки с многоалфавигным шифром замены при
хорошем ключе, можно получить вполне приемлемый ручной шифр,
вскрыть который будет очень непросто или вообще невозможно.
Но сменим галоп нашего рассуждения на шаг, чтобы предостеречь
читателя от одной широко распространенной ошибки. Насколько
осложнится вскрытие сообщения, если его зашифровать несколько раз
одним ключом? Ответ естественный, хотя для многих и неожиданный,
взломка сложнее вряд ли станет. Во времена Второй мировой войны
английским криптографам не давал покоя простой, но заковыристый
немецкий полицейский шифр. Из-за краткости сообщений его чтение
удавалось далеко не всегда и, как правило, с большими
трудностями. Немецкие криптографы об этом не знали, решив
улучшить шифр, как бы удвоив примененный ключ. Так вот, после
такого "усложнения" вскрытие шифровок стало легким и приятным. В
известном автору аналогичном случае, имевшем место некогда в
известной фирме, текст был зашифрован дважды. Шифровка
криптоаналитиком была восстановлена из свободных кластеров на
рабочей дискете, а в директории остались следы от двойного
шифрования и длины двух файлов типа ВАК того же сообщения. Из
этих следов и сопоставления длин шифровки с длинами файлов стало
ясно, что текст зашифрован дважды. По заголовку файла была
определена программа шифрования. Так как во второй раз был
зашифрован и текст сообщения, и заголовок файла шифровки,
содержание которого отчасти известно, то найти второй ключ
удалось просто подбором, потому что он был всего из 5 букв по
имени владельца. Первый ключ был угадан после этого сразу же, так
как стало ясно пристрастие автора файла к собственному имени.
Вследствие этого, примите за правило никогда не шифровать одно
сообщение дважды одним и тем же ключом, чтобы не усложнять себе
жизнь лишней работой. Применение нескольких разных ключей порой
оправдано, если не из-за увеличения стойкости шифра, то хотя бы
как свидетельство о согласии нескольких отправителей шифровки или
одновременном присутствии нужных получателей сообщения.
Лучшие известные криптографические системы, преимущественно
принадлежащие правительствам, практически невозможно вскрыть.
Однако все государства теми или иными путями пытаются сдержать и
даже запретить свободное использование криптографии, как
вызывающее головную боль у их секретных служб. В то время, как
ЦРУ в США призывает фирмы шире использовать шифрование, то АНБ
пытается ограничить длину ключа 40 битами. В последнем случае
возможен даже прямой перебор ключей, если использовать достаточно
мощную ЭВМ. По оценкам специалистов, раскалывание шифра алгоритма
RC-4 с ключом из 40 бит, широко используемого в сети Internet,
потребует около 100 MIPS (MIPS - million instructions per second
- миллион операций в секунду.) лет. Раньше считалось, что меньше,
чем за 6 месяцев работы суперкомпьютера, такой шифр вскрыт не
будет. Эта оценка была проверена практически и оказалось, что 120
рабочих станций с двумя суперкомпьютерами параллельного действия
взломали ключ за, 8 дней. Цена такого раскалывания достаточно
высока и превышает $10000, что впрочем сильно зависит от
эффективности алгоритма атаки. Поэтому проблемы криптоанализа еще
долгое время будут весьма актуальны.
ОСНОВЫ КЛАССИЧЕСКОЙ КРИПТОГРАФИИ
В этой главе будут изложены теоретические основы классической
криптографии, приведены описания основных компонентов современных
систем шифрования заменой, перестановкой и блочным взбиванием, а
также дан анализ устойчивости этих классов шифров к попыткам их
взлома. Следует отметить, что криптографические системы,
изобретенные любителями и непрофессионалами, всегда крайне
непрактичны в применении и нестойки от вскрытия. В частности
многие из самоучек видят основу стойкости шифра в секретности
системы шифрования. Профессионалы же, напротив, считают систему
шифрования общеизвестной и выводят стойкость шифра через
стойкость к, взлому секретного ключа.
Шифры замены
Теперь посмотрим, как обычно практически выполняется
шифрование заменой с помощью ЭВМ. Самый простой и эффективный
способ сделать текст нечитаемым - спрятать его, смешав с
последовательностью случайных чисел, заданной ключом, с помощью
операции XOR(Операция XOR выполняет следующие действия: (О XOR
0)-0, (О XOR 1)=1, (1 XOR 0)=1, (1 XOR 1)=0.). При этом
информация сообщения прячется в шуме - самом информативном, по
определению Шеннона, сигнале. Все правильно, песчинку лучше
прятать на пляже, рыбу в море, а информацию в шуме.
Есть и другие обоснования выбора случайных чисел для
шифрования заменой. Можно исходить из того, что криптоаналитик
попытается снизить неопределенность чтения шифровки, зная
статистические свойства нашей последовательности. А как только
человеку становится известным чье-то намерение, то его поведение
соответственно меняется. Поэтому если криптоаналитик знает наше
намерение использовать последовательность, где 1 встречается с
вероятностью р, а 0 с вероятностью 1-р, то, зная теорию игр, он
тоже с вероятностью р будет предполагать наличие 1. Вероятность
его успехов будет равна:
Р(Р)=Р-Р+(1-Р)-(1-Р)
Эта функция достигает минимума при р=0.5, что выпадает при
случайном выборе из 0 и 1 с равновероятными исходами. Далее, если
биты в случайной последовательности с одинаковой вероятностью
принимают значения 0 и 1, то биты в шифровке будут обладать тем
же свойством. Докажем это. Пусть вероятность нулевого бита в
тексте равна р, а единичного соответственно 1-р. Нулевой бит в
шифровке появляется, когда соответствующие биты
последовательности и текста оба равны либо О, либо 1. Значит,
вероятность появления нулевого бита в шифре равна:
Р=0.5-р+0.5-(1-р)=0.5
Более того, если биты в используемой для шифрования случайной
последовательности статистически независимы друг от друга, то и в
шифровке они становятся такими же. Текст превращается во что
угодно, то есть в шум. Из-за специфики операции XOR процедура
шифрования совпадает с процедурой расшифрования. Например,
обозначив через t вектор бит сообщения, у вектор случайной
последовательности и s шифровки, получаем t=s XOR у и s=t XOR у.
Приведем пример программной реализации этого шифра на языке
QuickBasic, называемого далее просто шифром замены. Такие шифры
образуют подмножество многоалфавитных шифров замены, которые мы
рассматривали выше.
'пример шифрования заменой
DECLARE SUB CodeAndPrint (Password!, Map%())
DEFINT I-N: CLS
DIM Map (40): CONST Password = -231.157
' сообщение
FOR i = 1 TO 40
Map(i) = ASC ("A")
NEXT
FOR i = 1 TO 40
PRINT CHR$ (Map (i));
NEXT
'шифровка
CALL CodeAndPrint (Password, Map())
' расшифровка
CALL CodeAndPrint (Password, Map ())
END
SUB CodeAndPrint (Password, Map())
x = RND (Password)
FOR i = 1 TO 40
Map(i) = INT(32 * RND) XOR Map(i)
NEXT
FOR i = 1 TO 40
PRINT CHR$ (Map (i));
NEXT
END SUB
В результате работы программы появляются три строки,
представляющие собой: верхняя - исходный текст, средняя -
шифрованный, а нижняя - расшифровку:
АААААААААААААААААААААААААААААААААААААААА
ЦСТЙЙШАШЬЦБНЫЩЛЮЫБЮЛРШБТОЙУФИИЪЪТЯЭЗЦЯЗС
АААААААААААААААААААААААААААААААААААААААА
У машинного многоалфавитного шифра замены с помощью операции
XOR есть ряд очень слабых мест, которые нужно знать и учитывать
использовании этого шифра. Серьезную неприятность может доставить
обратимость этого шифра, так как для расшифровки применяется то
же самое преобразование, что и для зашифровки. В том случае, если
одно и то же сообщение должно быть послано нескольким адресатам и
шифруется одним и тем же шифром может произойти так, что длина
сообщения изменится из-за сбоя или ошибки. В этом случае будет
получено 2 сообщения разной длины. Так, если имеем две шифровки
s' и s", которые отличаются тем, что исходный текст сообщения
оказался сдвинутым на один символ:
S'(i)=T(i)+Y(i);S"(i+1)=T(i+1)+Y(i)
где t - текст, а у - ключ, то, находя их сумму, получим сумму
текста со сдвигом:
S(i)=S'(i)+S"(i+1)=T(i)+T(i+1).
Исходный текст можно получить, подобрав S0, которое
неизвестно, в выражении:
T(n)=S0+S1+S2+...+Sn
Следующий пример демонстрирует эту технику. Пусть по двум
шифровкам, полученным из текста, сдвинутого на один символ,
образована следующая их сумма:
ЗВГЮШВЪСЮШТБПРЩВЦТЮТТБПРГВТЬ S(i)
Подбором S0 получаем текст исходного сообщения:
ГЕИЕЭЯШИЕЭОПЮНЕЗЭОЛЭОПЮНРТЛХ S0=29
ДЖИЖЮ ЩЙЖЮПРЯОХИЮПМЮПРЯОСУМЭ S0=30
ЕЭКЭЯАЪКЗЯРС ПЗЙЯРНЯРС ПТФНИ S0=31
ЖИЛИ БЫЛИ СТАРИК СО СТАРУХОЙ S0=32
Подобные коллизии нередко возникали лет тридцать назад, так
как основным носителем информации была перфолента, а при ее
заправке в считывающее устройство запросто можно было ошибиться
при рассылке циркулярной телеграммы адресованной в несколько
мест, но шифруемой одним ключом. Сейчас такие "подарки" для крип-
тоаналитиков почти исключены, так как криптографы стали держаться
правила ни при каком случае не использовать ключ дважды. При
такой ошибке шифровальщика шифр замены на основе XOR легко
вскрыть, даже не прибегая к отгадыванию и анализу. Число
вариантов прочтения шифровки не превышает число символов в
алфавите - это не подбор ключей.
Другая неприятность с машинным многоалфавитным шифром замены
может возникнуть, если в сообщении встречаются большие участки
пробелов или нулевых символов. Допустим, например, что линия
связи недозагружена, но в то время, когда нет сообщений,
аппаратура шифрования не выключается. Поэтому когда сообщений нет
и t=0, шифровка будет представлять собой "чистую"
последовательность ключа. Если в это время с помощью специальной
аппаратуры перехватить шифровку, представляющую собой ключ s=y,
то можно наложить на нее текст своего сообщения s'=s+t=t+y и
передать искаженную шифровку по каналу связи. Получатель,
расшифровав ее:
s'+y=s+t+y=t+y+y=t
получит переданный ему перехватчиком текст сообщения. А так как
этот текст поступит в шифрованном виде, то его содержимому могут
поверить, а это уже никак не допустимо. Так как перехватчик не
знает, свободна ли линия, то будет накладывать свой текст на
непрерывный шифрованный сигнал наугад несколько раз. Даже если в
это время по линии шла передача - не беда, скорее всего возникшие
искажения будут интерпретированы как помехи в канале связи.
Шифры перестановки
Из-за отмеченных особенностей шифр замены в чистом его виде
никогда не применяется, а всегда употребляется вместе с
перестановкой, например, бит внутри байта. Если после замены
символы сообщения превращались во что угодно, но сохраняли в
шифровке свое исходное местоположение, то после перестановки они
там и расположены еще и где угодно, что надежно защищает шифровку
от атак криптологов. Потому что перестановку можно рассматривать
как умножение вектора сообщения на матрицу перестановки бит Р с
элементами 0 и 1 и размером в длину сообщения в битах. Рассмотрим
два случая.
1. Перестановка может делаться до наложения на
сообщение случайной последовательности, то
есть s'=Pt+y. В случае, если текст в сообщении
отсутствует t=0 и идут нули или пробелы, то
s'=y, а в канал связи попадает чистый ключ.
2. Перестановка может делаться и после наложе-
ния на сообщение случайной последовательно-
сти, то есть s"=P(t+y). В случае, если текст в со-
общении отсутствует t=0 и идут нули или пробе-
лы, как s"=Py, а в канал связи попадает ключ,
шифрованный перестановкой.
Поэтому обычно предпочтение отдается второй схеме, когда в
отсутствие текста шифровка представляет собой не чистый ключ, а
осложненный перестановкой. Хотя и в том, и в другом случае
наложение на шифровку своего текста для введения получателя в
заблуждение ничего не дает. Однако перестановки необходимы и для
того, чтобы атака на ключ стала неэффективной. Если передача идет
побайтно, то достаточно лишь переставлять биты внутри байта,
чтобы с вероятностью 0.97 исказить его и сделать перехват ключа
описанным способом невозможным.
Перестановка может выполняться отдельными битами или группами
бит как байты, что программно куда удобнее, хотя и не
перемешивает биты полностью. Перестановку можно было бы
произвести и побитно, но это был бы очень дорогой процесс.
Временная сложность перестановки связана с квадратом числа
переставляемых элементов, поэтому перестановка бит была бы в 64
раза дороже перестановки байт. Вычислительных способов
перестановок существует множество, на любой вкус. Например, в
программах широко применяется перестановка по номерам N от 0 до
L-1 на основе рекуррентного выражения:
N(i+1)=(K-Ni+M) MOD L
при выполнении следующих 4 условий:
1) К и М берутся из интервала [1, L-1],
2) М взаимно просто с L,
3) К-1 делится на любой простой делитель L,
4) К-1 делится на 4, если L делится на 4.
Для хорошего запутывания в этом случае приходится делать
перестановку несколько раз, меняя случайным образом К и М. Часть
Дата добавления: 2015-08-28; просмотров: 25 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |