по разным путям геометрической фигуры.

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

Например, для d=6 в качестве ключа перестановки можно взять 436215 . Это означает, что в каждом блоке из 6 символов четвертый символ становится на первое место , третий – на второе, шестой – на третье и т.д. Пусть необходимо зашифровать такой текст:

Количество символов в исходном сообщении равно 24, следовательно, сообщение необходимо разбить на 4 блока. Результатом шифрования с помощью перестановки 436215 будет сообщение

ОЕТЭТ_ТЛСКДИШР_ЯФНАЯВОИ

Теоретически, если блок состоит из d символов, то число возможных перестановок d!=1*2*...*(d-1)*d . В последнем примере d=6 , следовательно, число перестановок равно 6!=1*2*3*4*5*6=720 . Таким образом, если противник перехватил зашифрованное сообщение из рассмотренного примера, ему понадобится не более 720 попыток для раскрытия исходного сообщения (при условии, что размер блока известен противнику).

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

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

Рассмотрим пример. Пусть в таблице кодирования будет 4 столбца и 3 строки (размер блока равен 3*4=12 символов). Зашифруем такой текст:

Количество символов в исходном сообщении равно 24, следовательно, сообщение необходимо разбить на 2 блока. Запишем каждый блок в свою таблицу по строчкам ( таблица 2.9).

Таблица 2.9. Шифрование методом перестановки по таблице

1 блок
Э	Т	О
Т	Е	К	С
Т		Д	Л
2 блок
Я		Ш	И
Ф	Р	О	В
А	Н	И	Я

Затем будем считывать из таблицы каждый блок последовательно по столбцам:

ЭТТТЕ ОКД СЛЯФА РНШОИИВЯ

Можно считывать столбцы не последовательно, а, например, так: третий, второй, первый, четвертый:

ОКДТЕ ЭТТ СЛШОИ РНЯФАИВЯ

В этом случае порядок считывания столбцов и будет ключом.

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

Посмотрим, как зашифровать и расшифровать сообщение, имеющее длину, не кратной размеру таблицы перестановки. Зашифруем слово

ПЕРЕМЕНКА

Количество символов в исходном сообщении равно 9. Запишем сообщение в таблицу по строкам ( таблица 2.10), а последние три ячейки оставим пустыми.

Затем будем считывать из таблицы последовательно по столбцам:

ПМАЕЕРНЕК

Для расшифрования вначале определяют число полных столбцов, то есть количество символов в последней строке. Для этого делят размер сообщения (в нашем примере – 9) на количество столбцов или размер ключа (в примере – 4). Остаток от деления будет числом полных столбцов: 9 mod 4 = 1 . Следовательно, в нашем примере был 1 полный столбец и три коротких. Теперь можно поставить буквы сообщения на свои места и расшифровать сообщение. Так как ключом при шифровании было число 1234 (столбцы считывались последовательно), то при расшифровании первые три символа (ПМА ) записываются в первый столбец таблицы перестановки, следующие два (ЕЕ ) – во второй столбец, следующие два (РН ) – в третий, и последние два (ЕК ) – в четвертый. После заполнения таблицы считываем строки и получаем исходное сообщение ПЕРЕМЕНКА .

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

Шифры подстановки (замены) основаны на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно-однозначное отображение конечного множества M на себя. Число N элементов множеств называется степенью подстановки. Количество n чисел действительно перемещаемых подстановкой называется длиной цикла подстановки.

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

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

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

1. Сделать шифр легко усложняемым (за счет увеличения количества раундов)
2. Сократить размера программного кода
3. Унифицировать алгоритмическую формулу шифрования

Сеть Фейсиля (Файсиля) – Feistel – это способ построения цикла шифрования в алгоритмах шифрования итеративных на основе регистра сдвига, с функцией обратной связи, зависящей от раундового ключа (оптимальное число раундов от 8 до 32)

DES – федеральный стандарт шифрования США (1997-2001).

Архитектура – классическая, сбалансированная сеть Фейсиля с начальными и конечными битовыми перестановками общего вида. Размер ключа – 56 бит. На его основе – международный стандарт ISO 8372-87. Алгоритм предназначен для шифрования данных 64-битовыми блоками.

DES представляет собой комбинацию двух основных методов:

1. Подстановка
2. Перестановка.

К тексту применяется единичная комбинация этих двух методов.

DES включает 16 раундов, то есть одна и та же комбинация методов применяется к открытому тексту 16 раз.

Наложение ключа-раунда производится операцией XOR

Исходный текст=>Начальная перестановка=>Шифрование * 16(<=Ключ) =>Конечная перестановка=>шифротекст

Цель начальной перестановки – равномерно распределить по блокам рядом стоящие биты.

Для зашифрования и расшифрования можно использовать одну и ту же функцию, но ключи используются в обратном порядке.

DES предусматривает 4 типа работы:

1. ECB-электронный шифр-блокнот. Открытый текст обрабатывается блоками по 64 бит, шифруемых одним ключом
2. CBC - цепочка блоков. Устраняет недостаток первого режима. Входное значение алгоритма зашифрования задается равным XOR-разности текущего блока открытого текста и полученного на предыдущем шаге блока шифрованного текста. Таким образом, все блоки исходного текста оказывается связанными (текст=>зашифрованный текст=>XOR=>текст=>зашифрованный текст)
3. CFB – обратная связь по шифро-тексту. Алгоритм преобразуется в поточный шифр, то есть каждый символ можно зашифровать и сразу передавать получателю
4. OFB – обратная связь по выходу. В регистр сдвига подается порция зашифрованного текста. Для каждого сеанса шифрования используется новое начальное состояние регистра.

Считается, что четырех режимов достаточно, чтобы использовать DES в практически любой области, для которой этот алгоритм подходит

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

AES-федеральный стандарт шифрования США, используемый в настоящее время.

AES – улучшенный стандарт шифрования.

Требования:

1. Шифр должен быть блочным
2. Шифр должен иметь длину блока, равную 128 битам
3. Шифр должен поддерживать ключи длиной 128, 192, 256 бит

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

Алгоритм представляет каждый блок кодируемых данных в виде двумерного массива байтов размером 4х4, 4х6 или 4х8 в зависимости от установленной длины блока.

Алгоритм состоит из определенного количества раундов (от 10 до 14 – это зависит от размера блока и длины ключа).

ГОСТ 28147089 – стандарт РФ на шифрование и имитозащиту данных.

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

Алгоритм реализует шифрование 64-битовых блоков данных с помощью 256-битового ключа, состоящего из восьми 32-битовых подключей.

На каждом i-м раунде используется K­ i -й подключ.

Алгоритмы шифрования ГОСТ 28147-89 обладают достоинствами других алгоритмов для симметричных систем и превосходят их своими возможностями.

На каждом i-м раунде алгоритма ГОСТ выполняется следующие операции:

L i =R i -1 , R i =L i -1 (плюсвкружочке)f(R i -1 , K i)

После выполнения этих 32 операций реализация алгоритма шифрования будет завершена.

Достоинством ГОСТ является наличие защиты от навязывания ложных данных (режим имитовставки), а также одинаковый цикл шифрования во всех 4 режимах (алгоритмах) ГОСТ.

Высокая криптостойкость обеспечивается за счет большой длины ключа (256 бит) и 32 раундов преобразования.

Стандарт включает режимы (алгоритмы):

1. Режим простой замены
2. Режим гаммирования
3. Режим гаммирования с обратной связью
4. Режим выработки имитовставки

Асимметричные алгоритмы шифрования.

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

Эти ключи различны и не могут быть получены один из другого.

Схема обмена информацией:

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

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

Применение таких шифров стало возможным благодаря К. Шеннону, предложившему строить шифр таким способом, чтобы его раскрытие было эквивалентно решению математической задачи, требующей выполнения объемов вычислений, превосходящих возможности современных ЭВМ (например, операции с большими простыми числами и их произведениями; нахождение значения произведения P=x*y)

Криптосистема шифрования данных RSA.

В настоящее время наиболее развитым методом криптографической защиты информации с известным ключом является RSA, названный так по начальным буквам фамилий её изобретателей (Rivest, Shamir, Adleman)

Чтобы использовать алгоритмы RSA, надо сначала сгенерировать открытый и секретный ключи, выполнив следующие шаги:

1. Выбрать два очень больших простых числа p и q и определить n как результат умножения p на q (n=p*q)
2. Выбрать большое случайное число d. Это число должно быть взаимно простым с m результатом умножения (p-1)(q-1)
3. Определить такое число e, для которого является истинным следующее соотношения (e*d)mod(m)=1 или e=(1mod(m))/d
4. Открытым ключом будут числа e,n, а секретным ключом – числа d,n

Красным выделено создание ключа.

Асимметрические криптосистемы на базе эллиптических кривых.

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

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

Для перечисленных выше реализаций используются эллиптические кривые над полями Галуа GF(p) конечным числом p элементов двух видов:

1. Эллиптическая кривая над конечным полем типа E(GF(p)), где р – некоторое простое число
2. Эллиптическая кривая над конечным полем типа E(GF(2m)), где p=2m

Пример: Алгоритм асимметричного шифрования на базе эллиптических кривых ECES (Elliptic Curve Encryption Scheme)

Алгоритм Эль-Гамаля.

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

Множество параметров системы включает простое число p и целое g, степени которого по модулю p порождают большое число элементов Z p

Методы замены.

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

4 типа замены (подстановки):

1. Моноалфавитная. Формула = Y i =k 1 X i +k 2 (modN), где Y i – i-символ алфавита, k 1 , k 2 – константы, Х i – i-символ открытого текста, N - длина используемого алфавита.

Пример. Замена – открытый текст, Ключ – Ключ

1. Гомофоническая замена – замена одному символу открытого текста ставит в соответствие несколько символов шифртекста. Этот метод применяется для искажения статистических свойств шифротектста. Используется подстановка таблицей. Значения используются поочередно из столбца.

1. Полиалфавитная замена – использование нескольких алфавитов. Смена алфавита идет на каждом шаге шифрования. Используется ступеньчатая замена букв по таблице.
2. Полиграммная замена – формируется из одного алфавита с помощью специальных правил. Шифр располагается в матрице, а открытый текст разбивается на пары символов XiXi+1

Шифры перестановки.

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

Пример. Текст «Грузите апельсины бочками Братья Карамазовы»

Шифротекст «Птр_аезгуионл_бысеьит_крабмчаизрямаакь_а__в____оы»

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

где i 1 – номер места шифртекста, на которое попадает первая буква открытого текста при выбранном преобразовании, i 2 - номер места для второй буквы и т. д. В верхней строке таблицы выписаны по порядку числа от 1 до n , а в нижней те же числа, но в произвольном порядке. Такая таблица называется перестановкой степени n .

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

Число различных преобразований шифра перестановки, предназначенного для шифрования сообщений длины n , меньше либо равно n ! (n факториал). Заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах.

С увеличением числа n значение n ! растет очень быстро. Для использования на практике такой шифр не удобен, так как при больших значениях n приходится работать с длинными таблицами. Поэтому широкое распространение получили шифры, использующие не саму таблицу перестановки, а некоторое правило, порождающее эту таблицу. Рассмотрим несколько примеров таких шифров.

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

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

Рис. 1.2. Шифр "Скитала"

Такой же результат можно получить, если буквы сообщения писать по кольцу не подряд, а через определенное число позиций до тех пор, пока не будет исчерпан весь текст. Сообщение "НАСТУПАЙТЕ " при размещении его по окружности стержня по три буквы дает шифртекст: "НУТАПЕСА_ТЙ ".

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

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

В качестве ключа в шифрующих таблицах используются:

размер таблицы;

слово или фраза, задающие перестановку;

особенности структуры таблицы.

Одним из самых примитивных табличных шифров перестановки является простая перестановка, для которой ключом служит размер таблицы. Этот метод шифрования сходен с шифром скитала. Например, сообщение "ТЕРМИНАТОР ПРИБЫВАЕТ СЕДЬМОГО В ПОЛНОЧЬ "записывается в таблицу поочередно по столбцам. Результат заполнения таблицы из 5 строк и 7 столбцов показан на рис. 1.3.

После заполнения таблицы текстом сообщения по столбцам для формирования шифртекста считывают содержимое таблицы по строкам. Если шифртекст записывать группами по пять букв, получается такое шифрованное сообщение: "ТНПВЕ ГЛЕАР АДОНР ТИЕЬВ ОМОБТ МПЧИР ЫСООЬ ".

Рис. 1.3. Заполнение шифрующей таблицы из 5 строк и 7 столбцов

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

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

Применим в качестве ключа, например, слово "ПЕЛИКАН ", а текст сообщения возьмем из предыдущего примера. На рис. 1.4 показаны две таблицы, заполненные текстом сообщения и ключевым словом, при этом левая таблица соответствует заполнению до перестановки, а правая таблица – заполнению после перестановки.

Рис. 1.4. Шифрующие таблицы, заполненные ключевым словом и текстом сообщения

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

При считывании содержимого правой таблицы по строкам и записи шифртекста группами по пять букв получим шифрованное сообщение: "ГНВЕП ЛТООА ДРНЕВ ТЕЬИО РПОТМ БЧМОР СОЫЬИ ".

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

Пример выполнения шифрования методом двойной перестановки показан на рис. 1.5. Если считывать шифртекст из правой таблицы построчно блоками по четыре буквы, то получится следующее: "ТЮАЕ ООГМ РЛИП ОЬСВ ".

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

Ключом к шифру двойной перестановки служит последовательность номеров столбцов и номеров строк исходной таблицы (в нашем примере последовательности 4132 и 3142 соответственно).

Число вариантов двойной перестановки быстро возрастает при увеличении размера таблицы:

для таблицы 3x3 36 вариантов;

для таблицы 4x4 576 вариантов;

для таблицы 5x5 14400 вариантов.

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

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

Пример магического квадрата и его заполнения сообщением "ПРИЛЕТАЮ ВОСЬМОГО " показан на рис. 1.6.

Рис. 1.6. Пример магического квадрата 4х4 и его заполнение сообщением

Шифртекст, получаемый при считывании содержимого правой таблицы по строкам, имеет вполне загадочный вид: "ОИРМ ЕОСЮ ВТАЪ ЛГОП ".

Число магических квадратов быстро возрастает с увеличением размера квадрата. Существует только один магический квадрат размером 3x3 (если не учитывать его повороты). Количество магических квадратов 4x4 составляет уже 880, а количество магических квадратов 5x5 – около 250000.

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

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

ОТКРЫТЫЙ ТЕКСТ: пример маршрутной перестановки

КЛЮЧ: (3, 1, 4, 2, 5)

КРИПТОГРАММА: рмупткмрнрнпррйсвиатеаиешоео

Заполнять последнюю строку таблицы «нерабочими» буквами нецелесообразно, так как криптоаналитик, получивший данную криптограмму, получает сведения о длине числового ключа .

Шифр вертикальной перестановки. Является разновидностью предыдущего шифра. К особенностям шифра можно отнести следующие:

Количество столбцов в таблице фиксируется и определяется длиной ключа;

Маршрут вписывания - строго слева-направо сверху-вниз;

Шифрограмма выписывается по столбцам в соответствии с их нумерацией (ключом).

Рис.5.5. Пример использования шифра вертикальной перестановки

В качестве ключа можно использовать слово или фразу. Тогда порядок выписывания столбцов соответствует алфавитному порядку букв в ключе. Например, если ключевым словом будет «ДЯДИНА», то присутствующая в нем буква А получает номер 1, Д – 2 и т.д. Если какая-то буква входит в слово несколько раз, то ее появления нумеруются последовательно слева направо. В примере первая буква Д получает номер 2, вторая Д – 3.

При шифровании сообщения «АБРАМОВ ИЛЬЯ СЕРГЕЕВИЧ» результат будет «ОЯЕ_АВ_ЕРИЕИАЛРЧМЬГ_Б_СВ».

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

Рассмотрим преобразование из ШП, предназначенное для зашифрования сообщения длиной символов. Его можно представить с помощью таблицы

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

Зная подстановку, задающую преобразование, можно осуществить как зашифрование, так и расшифрование текста. Например, если для преобразования используется подстановка

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

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

примерах шифров перестановки. Ответы помещены в конце раздела.

Читатель, знакомый с методом математической индукции, может легко убедиться в том, что существует (обозначается читается факториал») вариантов заполнения нижней строки таблицы (6). Таким образом, число различных преобразований шифра перестановки, предназначенного для зашифрования сообщений длины меньше либо равно (заметим, что в это число входит и вариант преобразования, оставляющий все символы на своих местах!).

С увеличением числа значение растет очень быстро. Приведем таблицу значений для первых 10 натуральных чисел:

(см. скан)

При больших для приближенного вычисления можно пользоваться известной формулой Стирлинга

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

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

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

Зашифруем, например, указанным способом фразу:

используя прямоугольник размера

(см. скан)

Зашифрованная фраза выглядит так:

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

Ниже приводятся описания трех разновидностей шифров перестановки, встречавшихся в задачах олимпиад.

Шифр «Сцитала». Одним из самых первых шифровальных приспособлений был жезл («Сцитала»), применявшийся еще во времена войны Спарты против Афин в V веке до н. э. Это был цилиндр, на который виток к витку наматывалась узкая папирусная лента (без просветов и нахлестов), а затем на этой ленте вдоль его оси записывался необходимый для передачи текст. Лента сматывалась с цилиндра и отправлялась адресату, который, имея цилиндр точно такого же диаметра, наматывал ленту на него и прочитывал сообщение. Ясно, что такой способ шифрования осуществляет перестановку местами букв сообщения.

Шифр «Сцитала», как видно из решения задачи 2.1, реализует не более перестановок по прежнему, - длина сообщения). Действительно, этот шифр, как нетрудно видеть, эквивалентен следующему шифру маршрутной перестановки: в таблицу, состоящую из столбцов, построчно записывают сообщение, после чего выписывают буквы по столбцам. Число задействованных столбцов таблицы не может превосходить длины сообщения.

Имеются еще и чисто физические ограничения, накладываемые реализацией шифра «Сцитала». Естественно предположить, что диаметр жезла не должен превосходить 10 сантиметров. При высоте строки в 1 сантиметр на одном витке такого жезла уместится не более 32 букв Таким образом, число перестановок, реализуемых «Сцита-лой», вряд ли превосходит 32.

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

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

Поясним процесс шифрования на примере. Пусть в качестве ключа используется решетка приведенная на рис. 1.

Зашифруем с ее помощью текст

Наложив решетку на лист бумаги, вписываем первые 15 (по числу

вырезов) букв сообщения: Сняв решетку, мы увидим текст, представленный на рис. 2. Поворачиваем решетку на 180°. В окошечках появятся новые, еще не заполненные клетки. Вписываем в них следующие 15 букв. Получится запись, приведенная на рис. 3. Затем переворачиваем решетку на другую сторону и зашифровываем остаток текста аналогичным образом (рис. 4, 5).

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

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

больше числа Однако, уже при размере трафарета число возможных решеток превосходит 4 миллиарда.

Широко распространена разновидность шифра маршрутной перестановки, называемая «шифром вертикальной перестановки» (ШВП). В нем снова используется прямоугольник, в который сообщение вписывается обычным способом (по строкам слева направо). Выписываются буквы по вертикали, а столбцы при этом берутся в порядке, определяемом ключом. Пусть, например, этот ключ таков: (5,4,1,7,2,6,3), и с его помощью надо зашифровать сообщение:

Впишем сообщение в прямоугольник, столбцы которого пронумерованы в соответствии с ключом:

(см. скан)

Теперь, выбирая столбцы в порядке, заданном ключом, и выписывая последовательно буквы каждого из них сверху вниз, получаем такую криптограмму:

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

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

В случае, когда ключ ШВП не рекомендуется записывать, его можно извлекать из какого-то легко запоминающегося слова или предложения. Для этого существует много способов. Наиболее распространенный состоит в том, чтобы приписывать буквам числа в соответствии с обычным алфавитным порядком букв. Например, пусть ключевым словом будет Присутствующая в нем буква А получает номер 1. Если какая-то буква входит несколько раз, то ее появления нумеруются последовательно слева направо. Поэтому второе вхождение буквы А получает номер 2. Поскольку буквы в этом слове нет, то буква В получает номер 3 и так далее. Процесс продолжается до тех

пор, пока все буквы не получат номера. Таким образом, мы получаем следующий ключ:

Перейдем к вопросу о методах вскрытия шифров перестановки. Проблема, возникающая при восстановлении сообщения, зашифрованного ШП, состоит не только в том, что число возможных ключей велико даже при небольших длинах текста. Если и удастся перебрать все допустимые варианты перестановок, не всегда ясно, какой из этих вариантов истинный. Например, пусть требуется восстановить исходный текст по криптограмме и нам ничего не известно, кроме того, что применялся шифр перестановки. Какой вариант «осмысленного» исходного текста признать истинным: или А может быть Приведем пример еще более запутанной ситуации. Пусть требуется восстановить сообщение по криптограмме

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

Эти варианты имеют прямо противоположный смысл и в имеющихся условиях у нас нет возможности определить, какой из вариантов истинный.

Иногда, за счет особенностей реализации шифра, удается получить информацию об использованном преобразовании (перестановке). Рассмотрим шифр «Сцитала» из задачи 2.1. Выше уже рассматривался вопрос о количестве перестановок, реализуемых «Сциталой». Их оказалось не более 32. Это число невелико, поэтому можно осуществить перебор всех вариантов. При достаточной длине сообщения, мы, скорее всего, получим единственный читаемый вариант текста. Однако, используя информацию о расположении линий, оставленных шифровальщиком, удается определить диаметр стержня, а значит, и возникающую перестановку букв (см. задачу 2.1).

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

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

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

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

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

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

В заключение рассказа о шифрах перестановки приведем историю с зашифрованным автографом А. С. Пушкина, описанную в романе В. Каверина «Исполнение желаний».

Главный герой романа - студент-историк Трубачевский, - занимавшийся работой в архиве своего учителя - академика Бауэра С. И., - нашел в одном из секретных ящиков пушкинского бюро фрагмент недописанной X главы «Евгения Онегина». Это был перегнутый вдвое полулист плотной голубоватой бумаги с водяным знаком 1829 года. На листе было написано следующее.

(см. скан)

(см. скан)

Без особых усилий Трубачевский прочитал рукопись, и ничего не понял. Он переписал ее, получилась бессвязная чепуха, в которой одна строка, едва начавшая мысль, перебивается другой, а та - третьей, еще более бессмысленной и бессвязной. Он попробовал разбить рукопись на строфы, - опять не получилось. Стал искать рифмы, - как будто и рифм не было, хотя на белый стих все это мало похоже. Просчитал строку - четырехстопный ямб, размер, которым написан «Евгений Онегин».

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

Прошло время. Однажды, когда он смотрел на светлые пятна окон подходящего к перрону поезда, каким-то внутренним зрением он

увидел перед собой всю рукопись - и с такой необыкновенной отчетливостью, как это бывает только во сне.