Как работает шифр замены
Перейти к содержимому

Как работает шифр замены

  • автор:

Шифры замены

В предыдущей статье были рассмотрены простые шифры, использующие алфавиты естественных языков (ЕЯ). Автоматическая обработка сообщений в компьютерных и сетях связи предусматривает использование искусственных языков (ИЯ), что более эффективно во многих отношениях. Ранее описывалась классификация шифров и для некоторых из них было показано, как они применяются в области информационной безопасности для решения триединой задачи информационной безопасности: конфиденциальности, целостности и доступности. Здесь продолжим рассмотрение, но для более сложных современных шифров

Векторно-матричные преобразования

В некоторых шифрах замены используют в качестве преобразования сообщений квадратные матрицы прямую и обратную, например, L[3×3] размерности 3×3;

Процедура шифрования исходного оцифрованного текста состоит в последовательном умножении всех триад хi ИТ справа на шифрующую матрицу по mod 32

Получили шифртекст в триадах с переходом от числового представления к буквам
у1 = НЦЖ; у2 = ЕОВ; у3 = ФУТ; у4 = ЫЧИ; у5 =КФА; у6 = ФАЭ. Процедура расшифрования шифрованного текста состоит в последовательном умножении всех триад уi ИТ справа на матрицу обратную к шифрующей матрице по mod 32

В результате расшифрования получаем открытый текст. Отметим один существенный недостаток шифра. Такой шифр при любом ключе сохраняет неподвижным нулевой вектор, что, конечно, является уязвимостью. Этот недостаток устраним путем перехода от линейных преобразований к аффинным, которые описываются формулами с прямой y = L[3×3] (x ) и обратной матрицами х = L -1 [3×3] (y a ) преобразования. Устранение недостатка возможно введением вектора сдвига, что показано ниже.

Шифр аффинного преобразования

Пример 1. Шифрование с использованием аффинного преобразования сообщения.

Пусть в качестве открытого текста взято слово КРИПТОГРАФИЯ разбитое на триады. После зашифрования получается текст ПЮП РОЙ ИШЛ ЕЮШ.
Находим цифровое представление векторов открытого текста:
КРИ = х1 = (10, 16, 8), ПТО = х2 = (15, 18, 14), ГРА = x3 = (3,16, 0), ФИЯ = x4 = (20, 8, 31). Шифрованного текста:
ПЮП = y1 = (15,30,15), РОЙ = y2 = (16,14, 9), ИШЛ = y3 = (8, 24,11), ЕЮШ = y4 = (5,30,24).

Теперь перейдем к определению а вектора аффинного сдвига
Он находится как линейная комбинация входных векторов, представляющая нулевой вектор, т.е. решаем над кольцом Z/32Z систему линейных уравнений относительно переменных a, b, c, d: ax1+bx2+cx3 + dx4 = 0. Здесь 0 – нулевой вектор, а
x1, x2, x3, x4 – входные векторы триады- открытого текста. Получаем решение в виде
b = 8a, c = 10a, d = 24a, где а – произвольный ненулевой элемент кольца Z/32Z. Тогда уравнение шифрования для такой линейной комбинации входных текстов запишется в виде (а -вектор сдвига):

В кольце нет операции деления Z/32Z ее заменяют умножением на обратный к 11 элемент равный 3

Теперь находим матрицу L[3×3]. Для этого надо перейти к центрированным выходным векторам (ШТ), т.е. к шифрованным векторам, смещенным на вектор сдвига yi‘ = yiа:
y1‘ = (10, 20,0), y2‘ = (11, 4, 26), y3‘ = (3, 14, 28), y4‘= (0, 20, 9)
. Находим значения этих векторов (результатов центрирования):

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

Шифр RSA

Шифр RSA и ему подобные в своей основе имеет строгую математическую конструкцию – конечное числовое кольцо вычетов (КЧКВ) по модулю составного числа n = dмdб, где dм – меньший простой делитель, dб – больший делитель, оба очень большой разрядности до 300 десятичных цифр. Другим важным требованием к ключу шифра RSA является требование для разности делителей | dб – dм| = Δ, она должна иметь столь же высокую разрядность. Простой пример КЧКВ – это начальный фрагмент натурального ряда чисел с добавлением нулевого элемента. Кольцо образуют все числа подряд от 0 до n – 1. Более подробно о кольцах можно прочитать в учебниках по высшей алгебре.

Стойкость шифра RSA к раскрытию ключа оценивается как очень высокая и все усилия криптоаналитиков по взлому шифра (точнее его математического алгоритма) с момента его публикации (1978) успеха до сих пор не имели. Можно назвать ряд причин такого положения.

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

В интернете имеется список RSA-чисел. Конкурс, объявленный в 1991 году, с предложением их факторизовать пока далек от завершения. Анализ результатов мультипликативного разложения чисел из списка доступен, как и сами числа, открыт для всех. Из анализа следует, чем больше цифр в описании числа, тем большее время требовалось для его разложения. Напрашивается вывод о том, что для разложения модуля n используются алгоритмы весьма чувствительные к разрядности чисел, т.е. алгоритмы используют свойства чисел, сильно зависящие от их разрядности. С моей стороны предлагается использовать в алгоритмах атак свойства подобные «признакам делимости» чисел. Они практически от разрядности факторизуемого числа не зависят.

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

Авторы публикаций и владельцы алгоритмов шифрования не отрицают других новых подходов, и не исключают возможности создания новых алгоритмов на новых идеях, перед которыми задача факторизации больших чисел (ЗФБЧ) не устоит и ее решение будет успешным. Меня как автора настоящей публикации привлекают как раз новые оригинальные разработки в области решения ЗФБЧ. Большинство моих публикаций посвящены как раз новым подходам, начиная с синтеза моделей натурального ряда чисел (НРЧ), изучения их свойств и использования таких свойств при разработке новых оригинальных алгоритмов решения ЗФБЧ.*********

Об этом шифре написано достаточно много и вполне заслуженно. Это асимметричный блочный шифр замены известный с 1978 года, а преобразования, используемые в его алгоритме очень просты. В шифре используются модуль шифра n = pq (p и q простые числа одинаковой очень большой разрядности), n публикуется открыто, доступен всем, два ключа открытый е — открыто публикуется и доступен всем и d — закрытый ключ, он известен только получателю сообщений и сохраняемый в тайне. Устанавливает шифр, параметры шифра получатель сообщения и хранит в тайне значения p,q, d,φ(n). Здесь φ(n) — функция Эйлера, используемая для отыскания значения закрытого ключа d как результата решения сравнения ed = 1(modφ(n)). Решение сравнения находится путем применения расширенного алгоритма Евклида наибольшего общего делителя (НОД). Текстовое сообщение перед зашифрованием разбивается на блоки и оцифровывается. Значение блока mi не превышает модуля n > mi шифра. Как видим, шифр устроен просто и доступен для понимания за короткое время. Надо еще сказать, что шифр реализуется над алгебраической структурой — конечным числовым кольцом вычетов по составному модулю Zn. Это означает, что все блоки исходного, шифрованного текстов, ключи е и d, простые числа p и q, значения функции Эйлера — это элементы означенного кольца. Все законы и кольцевые операции справедливы для элементов шифра

Зашифрование сообщения М = m1,m2, . mk> из k блоков выполняется последовательно блок за блоком по формуле yi =mi e (modn), где yi — блок шифртекста, mi — числовой блок исходного (открытого) текста, е — открытый ключ шифра, n — модуль шифра;

Расшифрование шифрсообщения Y= y1,y2, . yk> из шифрованных блоков выполняется последовательно блок за блоком по формуле mi =yi d (modn), где yi — блок шифртекста, mi — числовой блок исходного (открытого) текста, d— закрытый ключ шифра, n- модуль шифра;

Из известных шифров RSA можно считать долгожителем. В качестве однонаправленной функции fz(x) шифрования с потайным ходом (с лазейкой) в системе RSA используется дискретное возведение числового представления блока сообщения в степень ключа (открытого) шифрования Y =M e (modn).

Пример 2. Владелец «умного» устройства, подвергнувшегося атаке со стороны нарушителя, поставлен перед фактом – устройство перестало работать, его функционирование заблокировано. Если это замки на входных дверях, то ни войти, ни выйти из «умного» дома. На светящемся экране дисплея системы при проверке владелец видит последовательность чисел Y1 = 474 иY2 =407. Можно предположить, что это шифрованное сообщение нарушителя владельцу устройства.

Телефонным звонком по мобильному телефону нарушитель объявляет свои условия снятия блокировки. Это может быть банальное вымогательство денежной суммы. Нарушитель не лишен чувства юмора и дополнительно сообщает, что параметрами трех-буквенного шифра являются номер дома и возраст сына владельца. Что дает возможность владельцу самостоятельно разблокировать систему.

Если исходный текст будет восстановлен из шифртекста, то введение его в систему снимет ее блокировку. После проб и ошибок с 3-х буквенными шифрами владелец приходит к выводу о шифре RSA с модулем n = 527, равным номеру дома и открытым ключом е = 7 (число полных лет сына). Но даже в этих условия задача не из простых. Необходимо восстановить личный (закрытый) ключ нарушителя.

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

Владельцу раньше доводилось слышать о бесключевой атаке на шифр RSA. Для ее проведения достаточно знать открытый ключ е =7 и модуль n = 527 шифра. После звонка приятелю, компетентному в криптографии, принимается решение о самостоятельной разблокировке.

Формируется путем повторного многократного шифрования каждого блока на открытом ключе е последовательность числовых значений Yj, определяется такой j ≥ 1, для которого

Из последнего соотношения видим, что на некотором шаге при возведении в степень е значения блока шифрованного текста

из шифрованных текстов Y1 = 474; Y2 = 407 получается всего за 3 возведения каждого шифрованного блока в степень открытого ключа е = 7 открытые тексты.

В примере 2 для Mj = M1 = 297 сформированы (((297) 7 (mod527)) 7 (mod527)) 7 (mod527) = 297 вычеты по модулю 527 за 3 шага.

Обрабатывается первый блок шифртекста Y1 = 474:
1-й шаг ((474) 7 (mod 527)= 537865465949405824 (mod 527) = 382;
2-й шаг ((382) 7 (mod 527)= 1186980379913527168 (mod 527) = 423;
3-й шаг ((423) 7 (mod 527)= 2423162679857794647 (mod 527) = 297;
4-й шаг, ШТ = ((297) 7 (mod 527)= 203842691587258713 (mod 527) = 474.
На этом шаге получили значение 474, с которого начали атаку.

Следовательно, на предыдущем шаге вычислений было получено значение открытого текста М1 = 297.

Теперь обрабатываем второй блок шифртекста Y2 =407:
1-й шаг ((407) 7 (mod 527)= 1849953723041760743 (mod 527) = 16;
2-й шаг (( 16) 7 (mod 527)= 268435456 (mod 527) = 101;
3-й шаг ((101) 7 (mod 527)= 107213535210701 (mod 527) = 33;
4-й шаг, ШТ = ((33) 7 (mod 527)= 42618442977 (mod 527) = 407.

Получили значение 407, с которого начали возведение в степень открытого ключа, следовательно, на предыдущем шаге было получено значение открытого текста М2 = 33. Теперь обрабатываем оба блока открытого текста с целью возможности их прочтения. Переход к буквенному представлению не дает разгадки (смысла). Пробуем представить блоки в двоичном виде:
297 = 100101001 и 33 = 100001.

Запишем числа без пробелов 100101001100001, здесь 15 символов. Многие шифры имеют названия на английском языке используются латинские буквы. В английском языке 26 букв 5 символов на букву. Пробуем переход к десятичному представлению 100102 = 1810, 100112 = 1910, 000012 = 110 .

Для английского алфавита используют две разные его оцифровки в зависимости от удобства для автора

В нашем случае воспользуемся средней строкой чисел. получаем три буквы RSA — это название трехбуквенного шифра 100102 = R =1810, 100112 = S = 1910, 000012 = A = 110 . Можно полагать, что исходный текст расшифрован верно. Загрузка чисел в память устройства снимает его блокировку. В этот раз обошлось без выкупа, нарушитель дал шанс владельцу, которым тот успешно воспользовался.

Заключение

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

Замечание. Шифр RSA противостоит атакам более 40 лет. Но и он имеет слабые места. Так, например, текст из 6-и блоков: 001; 341;187;154; 373; 526 этим шифром с составным модулем n = 527 не может быть зашифрован ни на каком ключе.

Для каждого конкретного модуля существуют такие нешифруемые сообщения.

1.Алферов А.П. и др. Основы криптографии.- М.:Гелиос АРВ, 2001.- 480 с.
2. Маховенко Е.Б. Теоретико-числовые методы в криптографии. -М.: Гелиос АРВ, 2006. — 320 с.
3. Ростовцев А.Г. Алгебраические основы криптографии.- СПб.: Мир и семья, 2000. — 354 с.
4. Ростовцев А.Г., Маховенко Е.Б. Введение в криптографию с открытым ключом. -СПб.: Мир и семья, 2001. — 336 с.
5. Ростовцев А.Г., Маховенко Е.Б. Введение в теорию итерированных шифров.- СПб.:Мир и семья,2003. — 302 с.
6. Жельников В. Криптография от папируса до компьютера.- М.: АBF, 1996.-
7 . Уэзерелл Ч. Этюды для программистов. — М.: Мир, 1982. — 288 с.
8. Молдовян А.А. и др. Криптография: скоростные шифры. -СПб.: БХВ, 2002. — 496 с.

Шифр замены

Шифр подстано́вки каждый символ открытого текста заменяет на некоторый другой. В классической криптографии различают четыре типа шифра подстановки:

  • Одноалфавитный шифр подстановки (шифр простой замены) — шифр, при котором каждый символ открытого текста заменяется на некоторый, фиксированный при данном ключе символ того же алфавита.
  • Однозвучный шифр подстановки похож на одноалфавитный за исключением того, что символ открытого текста может быть заменен одним из нескольких возможных символов.
  • Полиграммный шифр подстановки заменяет не один символ, а целую группу. Примеры: шифр Плейфера, шифр Хилла.
  • Многоалфавитный шифр подстановки состоит из нескольких шифров простой замены. Примеры: шифр Виженера, шифр Бофора, одноразовый блокнот.

Шифры простой замены

В шифрах простой замены замена производится только над одним единственным символом. Для наглядной демонстрации шифра простой замены достаточно выписать под заданным алфавитом тот же алфавит но в другом порядке или например со смещением. Записанный таким образом алфавит называют алфавитом замены.

Примеры шифров простой замены

Шифр Атбаш

Шифр простой замены, использованный для еврейского алфавита и получивший оттуда свое название. Шифрование происходит заменой первой буквы алфавита на последнюю, второй на предпоследнюю (алеф (первая буква) заменяется на тав (последнюю), бет (вторая) заменяется на шин (предпоследняя); из этих сочетаний шифр и получил свое название). Шифр Атбаш для английского алфавита:

Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Алфавит замены: Z Y X W V U T S R Q P O N M L K J I H G F E D C B A

Шифр с использованием кодового слова

Шифр с использованием кодового слова является одним из самых простых как в реализации так и в расшифровывании. Идея заключается в том что выбирается кодовое слово, которое пишется впереди, затем выписываются остальные буквы алфавита в своем порядке. Шифр с использованием кодового слова WORD.

Исходный алфавит: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Алфавит замены: W O R D A B C E F G H I J K L M N P Q S T U V X Y Z

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

К шифрам замены тоже можно отнести всем известные шифры, используемые авторами многих известных книг. Таких как «Пляшущие человечки» А. Конан Дойла, или «Золотой Жук» Э. По, так же шифр из романа Ж. Верна «Путешествие к центру земли».

Безопасность шифров простой замены

Главный недостаток этого метода шифрования это то, что последние буквы алфавита (которые имеют низкие коэффициенты при частотном анализе) имеют тенденцию оставаться в конце. Более защищенный способ построить алфавит замены состоит в том, чтобы выполнить колоночное перемещение (перемещение столбцов) в алфавите, используя ключевое слово, но это не часто делается. Несмотря на то, что число возможных ключей является очень большим (26! = 2^88.4), этот вид шифра может быть легко взломанным. Согласно расстоянию уникальности английского языка, 27.6 букв от зашифрованного текста должно быть достаточно чтобы взломать шифр простой замены. На практике, обычно достаточно около 50 символов для взлома, хотя некоторые шифротексты могут быть взломаны и с меньшим количеством символов, если найдены какие-либо нестандартные структуры. Но при равномерном распределении символов в тексте может потребоваться куда более длинные шифротексты для взлома.

  • расстояние уникальности — термин, используемый в криптографии, обращающейся к длине оригинального шифротекста, которого должно быть достаточно для взлома шифра.

Омофоническая замена

Ранние попытки увеличивать трудность дешифровки частотным анализом шифров замены состояла в том, чтобы замаскировать реальные частоты появления символов обычного текста с помощью омофонии. В этих шифрах, буквы исходного алфавита соответствуют больше чем одному символу из алфавита замены. Обычно, символам исходного текста наивысшей частотой дают большее количество эквивалентов чем более редким символам. Таким образом, распределение частоты становится более равномерным, сильно затрудняя частотный анализ. С тех пор как для алфавита замены стало требоваться больше чем 26 символов появилась необходимость в расширенных алфавитах. Одним из самых простых решений является это замена алфавита на цифры. Другой метод состоит из простых изменений существующего алфавите: прописные буквы, строчные буквы, перевернутые символы и т. д. Более художественными, хотя не обязательно более надежными, будут омофонические шифры, которые используют полностью изобретенные (вымышленные) алфавиты. (например «Пляшущие человечки» А. Конан Дойла, или «Золотой Жук» Э. По. или «Рукопись Войнича»).

Примеры омофонических шифров

Номенклатор

Шифр, изданный средневековым чиновником, представляющий собой маленькую книгу с большими омофоническими таблицами замены. Первоначально шифр был ограничен названиям важных людей того времени, отсюда и последовало название шифра; в более поздних изданиях это шифр дополнился большим количеством распространенных слов и географических названий. На основе этого «номенклатора» был составлен Великий Шифр Россиньеля, используемый королем Франции Луи XIV. И действительно после того как этот шифр перестал использоваться французские архивы были закрытыми ещё в течение нескольких сотен лет. «Номенклаторы» были стандартом для дипломатической корреспонденции, шпионских сообщений, и являлись основыним средством антиполитической конспирации с начала пятнадцатого столетия до конца восемнадцатого столетия. Хотя правительственные криптоаналитики систематически взламывали «номенклаторы» к середине шестнадцатого столетия. Обычный выходом из этой ситуации было увеличение объемов таблиц. Но к концу восемнадцатого столетия, когда система начинала вымирать, некоторые «номенклаторы» имели до 50 000 символов. Однако, не все «номенклаторы» были сломаны.

Великий Шифр Россиньеля

Антони Россиньель и его сын Бонавентур Россиньель изобрели шифр, который использовал 587 различных числа. Шифр был настолько силен, что в течение многих столетий никто не мог взломать его, пока это не сделал Командир Птинье Базарье в 1893 году, который понял, что каждое число замещало французский слог, а не одну букву, как до этого считали. Он предположил, что специфическая последовательность повторных чисел, 124-22-125-46-345, кодирует слово «les ennemis» (враги) и отталкиваясь от этой информации он смог распутать весь шифр.

Книжный шифр

Книжный шифр — шифр, в котором ключом является книга или небольшая часть текста. Основным требованием будет, чтобы оба корреспондента не только имели одну и ту же самую книгу, но и тот же самое издание и выпуск. Традиционно книжные шифры работают заменяя слова в исходном тексте на местоположение этих же слов в книге. Это будет работать до тех пор пока не встретится слово, которого не будет в книге, тогда сообщение не может быть закодировано. Альтернативный подход, который обходит эту проблему, состоит в том, чтобы заменять отдельные символы, а не слова. Однако, такой способ имеет побочный эффект: зашифрованный текст становится очень большого размера. (обычно используется от 4 до 6 цифр для шифрования каждого символа или слога).

Именно это способ показан в начале фильма Семнадцать мгновений весны.

Криптоанализ

Шифр простой замены легко вскрывается с помощью частотного анализа, так как не меняет частоты использования символов в сообщении.

Однозвучные шифры сложнее для вскрытия, хотя они и не скрывают всех статистических свойств текста.

Многоалфавитные шифры шифруют каждый символ с помощью некоторого одноалфавитного шифра. Стойкость такого шифра сильно зависит от количества используемых шифров простой замены. Но при использовании компьютера криптоаналитик не испытает трудностей при вскрытии.

См. также

Литература

  • Bruce Schneier «Applied Cryptography, Second Edition», ISBN 0-471-12845-7
  • «Введение в криптографию» под ред. В. В. Ященко — М.: МЦНМО-ЧеРо, 2000, ISBN 5-900916-40-5

Wikimedia Foundation . 2010 .

Подстановочные шифры (шифры замены)

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

В шифре простой замены происходит замена буквы на букву, т.е. устанавливается попарное соответствие символов исходного алфавита с символами шифроалфавита.

Например, в рассказе Эдгара По «Золотой жук» пиратский капитан Кидд в своей шифровке вместо букв a, b, c, d, e, f, g, h, i писал соответственно 5, 2, -, +, 8, 1, 3, 4, 6, 0, 9 . В «Пляшущих человечках» Артура Конан-Дойла бандит Слени использовал шифр, где буквы заменялись схематическими человеческими фигурками в разных позах.

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

а б в г д е ж з и й к л м н о п
щ ъ ы ь э ю п о л я р н и к а б
р с т у ф х ц ч ш щ ъ ы ь э ю я
в г д е ж з й м с т у ф х ц ч ш

При шифровании каждая буква открытого текста заменяется на стоящую под ней букву. В рассматриваемом примере указание никогда не рассекречивай открытый текст в его истинной формулировке можно представить в виде криптограммы КЛРАЬ ЭЩКЮВ ЩГГЮР ВЮМЛЫ ЩЯАДР ВФДФЯ ДЮРГД ЫЮЬАЛ ГДЛКК АЯЖАВ ИЕНЛВ АЫРЮУ . Здесь, как это часто делается, текст разбит на пятибуквенные блоки, в конце, для завершенности, добавлена незначащая буква.

Криптоанализ шифров простой замены осуществляется с помощью частотных характеристик языка открытых текстов.

Известно, что в русском тексте длиной 10 000 знаков буква О встречается в среднем 1047 раз, Е – 836, А – 808, Н – 723, И – 700, Т – 625, Р – 584, В – 569, С – 466.

Поэтому, если в достаточно длинной криптограмме какая-то буква оказывается безусловным лидером по числу вхождений, есть основание предполагать, что она заменяет О. Блестящим примером частотного криптоанализа являются рассуждения Леграна, героя рассказа «Золотой жук», прочитавшего шифрованное указание о месте сокрытия пиратского клада, и выводы (в подлиннике) Шерлока Холмса в Деле Пляшущих Человечков. Заметим, что в английских текстах самыми частыми являются (в порядке убывания) буквы е, t, a, o, i, n, s, r.

Для увеличения стойкости подстановочных шифров используют различные методы, скрывающие частотные соотношения языка. Рассмотрим несколько известных приемов. Шифры названы историческими именами использовавших их агентов.

Шифр «Дора»

123456789
4, 5, 6, 7, 8, 9 a s i n t o e r
2, 3 b c d f g h j k l
1 mpquvwxyz

Во второй строке таблицы записаны самые частые английские буквы (65% всех букв в текстах) в виде мнемонической (для запоминания) фразы a sin to er(r) – «грех ошибаться». Далее оставшиеся буквы перечисляются в алфавитном порядке с пропуском букв из второй строки. Заметим, что, за счет только изменения порядка букв во второй строке, можно получить 40320 различных таблиц. Шифрование производится заменой каждой буквы на двузначное число, составленное из номера строки и номера столбца, где находится эта буква. При этом буква может выступать в криптограмме в нескольких вариантах. Например, 41, 51, 61, 71, 81, 91 – образы одной и той же буквы a . Понятно, что, глядя на криптограмму, невозможно установить, как же в ней «спрятана» та или иная из самых частых букв.

Шифр «Марк»

1 2 3 4 5 6 7 8 9 0
с е н о в а л
8 б г д ж з и й к м
9 р т у ф х ц ч ш щ
0 ы ь э ю я /

Буквы, стоящие во второй строке таблицы (они дают 45% букв в русских текстах), при шифровании заменяются стоящими над ними цифрами, остальные буквы – двузначными числами «строка-столбец». Косая черта – знак начала и окончания числового массива в открытом тексте (цифры при шифровании сохраняются).

Шифр «Жанна»

Английский алфавит записан в таблицу 5×5 с паролем в данном примере eighty four – «84» (буква j в открытых текстах всюду заменялась на i ). Открытый текст разбивается на блоки длины 4.

e i g h t
y f o u r
a b c d k
l n n p q
s v w x z

Первая буква каждого блока заменяется на своего верхнего соседа в таблице («север»), вторая – на правого («восток»), третья – на нижнего («юг»), четвертая – на левого («запад»).

Простейшие методы шифрования с закрытым ключом

Методы шифрования заменой (подстановкой) основаны на том, что символы исходного текста, обычно разделенные на блоки и записанные в одном алфавите, заменяются одним или несколькими символами другого алфавита в соответствии с принятым правилом преобразования.

Одноалфавитная замена

Одним из важных подклассов методов замены являются одноалфавитные (или моноалфавитные) подстановки, в которых устанавливается однозначное соответствие между каждым знаком ai исходного алфавита сообщений A и соответствующим знаком ei зашифрованного текста E . Одноалфавитная подстановка иногда называется также простой заменой, так как является самым простым шифром замены.

Примером одноалфавитной замены является шифр Цезаря, рассмотренный ранее. В рассмотренном в «Основные понятия криптографии» примере первая строка является исходным алфавитом, вторая (с циклическим сдвигом на k влево) – вектором замен.

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

Подстановка может быть задана с помощью таблицы, например, как показано на рис. 2.3.

 Пример таблицы замен для двух шифров

Рис. 2.3. Пример таблицы замен для двух шифров

В таблице на рис. 2.3 на самом деле объединены сразу две таблицы. Одна (шифр 1) определяет замену русских букв исходного текста на другие русские буквы, а вторая (шифр 2) – замену букв на специальные символы. Исходным алфавитом для обоих шифров будут заглавные русские буквы (за исключением букв » Ё » и » Й «), пробел и точка.

Зашифрованное сообщение с использованием любого шифра моноалфавитной подстановки получается следующим образом. Берется очередной знак из исходного сообщения. Определяется его позиция в столбце «Откр. текст» таблицы замен. В зашифрованное сообщение вставляется шифрованный символ из этой же строки таблицы замен.

Попробуем зашифровать сообщение «ВЫШЛИТЕ ПОДКРЕПЛЕНИЕ» c использованием этих двух шифров ( рис. 2.4). Для этого берем первую букву исходного сообщения «В» . В таблице на рис. 2.3 в столбце «Шифр 1» находим для буквы «В» заменяемый символ. Это будет буква «О» . Записываем букву «О» под буквой «В» . Затем рассматриваем второй символ исходного сообщения – букву «Ы» . Находим эту букву в столбце «Откр. текст» и из столбца «Шифр 1» берем букву, стоящую на той же строке, что и буква «Ы» . Таким образом получаем второй символ зашифрованного сообщения – букву «Н» . Продолжая действовать аналогично, зашифровываем все исходное сообщение ( рис. 2.4).

 Пример шифрования методом прямой замены

Рис. 2.4. Пример шифрования методом прямой замены

Полученный таким образом текст имеет сравнительно низкий уровень защиты, так как исходный и зашифрованный тексты имеют одинаковые статистические закономерности. При этом не имеет значения, какие символы использованы для замены – перемешанные символы исходного алфавита или таинственно выглядящие знаки.

Зашифрованное сообщение может быть вскрыто путем так называемого частотного криптоанализа. Для этого могут быть использованы некоторые статистические данные языка, на котором написано сообщение.

Известно, что в текстах на русском языке наиболее часто встречаются символы О, И . Немного реже встречаются буквы Е, А . Из согласных самые частые символы Т, Н, Р, С . В распоряжении криптоаналитиков имеются специальные таблицы частот встречаемости символов для текстов разных типов – научных, художественных и т.д.

Криптоаналитик внимательно изучает полученную криптограмму, подсчитывая при этом, какие символы сколько раз встретились. Вначале наиболее часто встречаемые знаки зашифрованного сообщения заменяются, например, буквами О . Далее производится попытка определить места для букв И, Е, А . Затем подставляются наиболее часто встречаемые согласные. На каждом этапе оценивается возможность «сочетания» тех или иных букв. Например, в русских словах трудно найти четыре подряд гласные буквы, слова в русском языке не начинаются с буквы Ы и т.д. На самом деле для каждого естественного языка (русского, английского и т.д.) существует множество закономерностей, которые помогают раскрыть специалисту зашифрованные противником сообщения.

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

ТНФЖ.ИПЩЪРЪ

Это сообщение состоит из 11 символов. Пусть известно, что эти символы составляют целое сообщение, а не фрагмент более крупного текста. В этом случае наше зашифрованное сообщение состоит из одного или нескольких целых слов. В зашифрованном сообщении символ Ъ встречается 2 раза. Предположим, что в открытом тексте на месте зашифрованного знака Ъ стоит гласная О, А, И или Е . Подставим на место Ъ эти буквы и оценим возможность дальнейшего криптоанализа таблица 2.1

Таблица 2.1. Варианты первого этапа криптоанализа

Зашифрованное сообщение
Т Н Ф Ж . И П Щ Ъ Р Ъ
После замены Ъ на О
О О
После замены Ъ на А
А А
После замены Ъ на И
И И
После замены Ъ на Е
Е Е

Все приведенные варианты замены могут встретиться на практике. Попробуем подобрать какие-нибудь варианты сообщений, учитывая, что в криптограмме остальные символы встречаются по одному разу ( таблица 2.2).

Таблица 2.2. Варианты второго этапа криптоанализа

Зашифрованное сообщение
Т Н Ф Ж . И П Щ Ъ Р Ъ
Варианты подобранных дешифрованных сообщений
Ж Д И С У М Р А К А
Д Ж О Н А У Б И Л И
В С Е Х П О Б И Л И
М Ы П О Б Е Д И Л И

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

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

В «Алгоритм криптографического преобразования данных ГОСТ 28147-89» будут более подробно рассмотрены вопросы теоретической стойкости криптосистем, а также принципы построения идеальных криптосистем.

Интересно, что если попытаться замаскировать статистические характеристики открытого текста, то задача вскрытия шифра простой замены значительно усложнится. Например, с этой целью можно перед шифрованием «сжимать» открытый текст с использованием компьютерных программ-архиваторов.

С усложнением правил замены увеличивается надежность шифрования. Можно заменять не отдельные символы, а, например, двухбуквенные сочетания – биграммы. Таблица замен для такого шифра может выглядеть, как на таблица 2.3.

Таблица 2.3. Пример таблицы замен для двухбуквенных сочетаний

Откр. текст Зашифр. текст Откр. текст Зашифр. текст
аа кх бб пш
аб пу бв вь
ав жа . .
. . яэ сы
ая ис яю ек
ба цу яя рт

Оценим размер такой таблицы замен. Если исходный алфавит содержит N символов, то вектор замен для биграммного шифра должен содержать N 2 пар «откр. текст – зашифр. текст» . Таблицу замен для такого шифра можно также записать и в другом виде: заголовки столбцов соответствуют первой букве биграммы, а заголовки строк – второй, причем ячейки таблицы заполнены заменяющими символами. В такой таблице будет N строк и N столбцов ( таблица 2.4).

Таблица 2.4. Другой вариант задания таблицы замен для биграммного шифра

а б . я
а кх цу . .
б пу пш . .
в жа вь . .
. . . . .
ю . . . ек
я ис . . рт

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *