Шифр вертикальной перестановки. Шифрование методом перестановки. Виды и способы шифров

Шифры подстановки (замены) основаны на алгебраической операции, называемой подстановкой. Подстановкой называется взаимно-однозначное отображение конечного множества 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

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

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

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

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

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

Простейшим примером перестановки является перестановка с фиксированным периодом 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-разрядного сообщения. Так, если принять размер блока равным восьми битам, можно, к примеру, использовать такой блок перестановки, как на

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

Самая простая перестановка - написать исходный текст задом наперед и одновременно разбить шифрограмму на пятерки букв. Например, из фразы:

ПУСТЬ БУДЕТ ТАК, КАК МЫ ХОТЕЛИ,

получится такой шифртекст:

ИЛЕТО ХЫМКА ККАТТ ЕДУБЬ ТСУП

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

ПУСТЬ-БУДЕТ-ТАККА-КМЫХО-ТЕЛИО.

Тогда шифрограмма, несмотря на столь незначительное изменение, будет выглядеть по-другому:

ОИЛЕТ ОХЫМК АККАТ ТЕДУБ ЬТСУП

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

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

После этого вертикальные столбцы по порядку писали в строку с разбивкой на пятерки букв:

ПКУМС ЫТХЬО БТУЕД ЛЕИТК ТЛАМК НКОАП

Вариант этого шифра: сначала исходную фразу записать в столбики:

Потом разбить строки на пятерки букв:

ПСЬУЕ ТКАМХ ТЛАВД УТБДТ АККЫО ЕИБГЕ

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

Для примера возьмем решетку 6х6 (причем количество строк может увеличиваться или уменьшаться в зависимости от длины исходного сообщения) и заполним ее по строкам:

Если шифровать по стрелкам (диагоналям) сверху вниз с левого верхнего угла, то в итоге получится такая шифрограмма:

П УУ СДК ТЕКХ ЬТАОА БТКТБМ АМЕВЛ ЫЛГК ИДИ ЕЗ Ж

Для окончательного оформления шифртекст может быть разбит на группы по 6 символов:

ПУУСДК ТЕКХЬТ АОАБТК ТБМАМЕ ВЛЫЛГК ИДИЕЗЖ

Очень часто используют перестановки с ключом. Тогда правила заполнения решетки и шифрования из нее упрощаются, становятся стандартными. Единственное, что надо помнить и знать - это ключ, которым может быть любое слово, например, РАДИАТОР. В соответствии с расположением букв в алфавите, буква А получает номер 1, вторая буква А - 2, следующая по алфавиту буква Д - 3, потом И - 4, О – 5; первая буква Р - 6, вторая Р - 7 и буква Т - 8. Заполняем решетку:

Записываем столбики в соответствии с номерами букв ключа:

УТЫ ЬКТ СТХ ТАО УАЛ ПЕМО ДКИ БКЕ

Затем последовательность опять разбивается на пятерки:

УТЫЬК ТСТХТ АОУАЛ ПЕМОД КИБКЕ

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

Развитием этого шифра является шифр перестановки колонок с пропусками, которые располагаются в решетке тоже в соответствии с ключом (в нашем случае через 6-1-3-4-2-8-5-7 ... символов):

Шифрограмма будет такой:

УДК Ь СЕХЛ ТТОМ АЕП ПКИ УКЛР БТТО

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

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

Простая перестановка

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

Шифрование проводится в следующем порядке:

Шифруемый текст записывается последовательными строками под числами ключевой последовательности, образуя блок шифрования размером n*m.

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

Заполняется новый блок и т.д.

Например, зашифруем текст

ГРУЗИТЕ_АПЕЛЬСИНЫ_БОЧКАХ

блоком размером 8*3 и ключом 5-8-1-3-7-4-6-2.

Таблица простой перестановки будет иметь вид:

Г Р У З И Т Е _ А П Е Л Ь С И Н Ы _ Б О Ч К А Х

Зашифрованное сообщение:

УЕБ_НХЗЛОЕСЛГАЫЕИАИЬЧРП_

Расшифрование выполняется в следующем порядке:

Из зашифрованного текста выделяется блок символов размером n*m.

Этот блок разбивается на n групп по m символов.

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

Выделяется новый блок символов и т.д.

Перестановка, усложненная по таблице

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

При шифровании текста в неиспользуемые элементы не заносятся символы текста и в зашифрованный текст из них не записываются никакие символы - они просто пропускаются. При расшифровке символы зашифрованного текста также не заносятся в неиспользуемые элементы.

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

Перестановка, усложненная по маршрутам

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

Струкрура трехмерного гиперкуба представлена на рисунке 6.

Рисунок 6. Трехмерный гиперкуб

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

Рисунок 7. Маршруты Гамильтона

Последовательность перестановок символов в шифруемом блоке для первой схемы 5-6-2-1-3-4-8-7, а для второй 5-1-3-4-2-6-8-7. Аналогично можно получить последовательность перестановок для других маршрутов: 5-7-3-1-2-6-8-4, 5-6-8-7-3-1-2-4, 5-1-2-4-3-7-8-6 и т.д.

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

Стойкость простой перестановки однозначно определяется размерами используемой матрицы перестановки. Например, при использовании матрицы 16*16 число возможных перестановок достигает 1.4E26. Такое число вариантов невозможно перебрать даже с использованием ЭВМ. Стойкость усложненных перестановок еще выше. Однако следует иметь в виду, что при шифровании перестановкой полностью сохраняются вероятностные характеристики исходного текста, что облегчает криптоанализ.

Шифрование по методу магических квадратов.

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

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

Зашифруем фразу «МАГИЧЕСКАЯ СИЛА» с помощью магического квадрата размером 4х4. Для этого выберем один из 880 вариантов магических квадратов заданного размера (рисунок 8а). Затем вписываем каждую букву сообщения в отдельную ячейку таблицы с номером, соответствующим порядковому номеру буквы в исходной фразе (рисунок 8б). При считывании заполненной таблицы по строкам получаем шифротекст: «_ГАИАЕССЧЯ_КИАЛМ».

Рисунок 8. Пример шифрования с помощью магических квадратов

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

Рис. 1.6.

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

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

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

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

Запишем фразу «Терминатор прибывает седьмого в полночь» в таблицу размером 5x7 (рис. 1.7) но столбцам. Выписав текст из таблицы построчно, получим шифр: «тннвеглеарадонртиеьвомобтмнчирысооь».

Рис. 1.7.

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

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

Решетка Кардано. Решетка Кардано (поворотная решетка) - это прямоугольная или квадратная карточка с четным числом строк и столбцов 2k X 2т. В ней проделаны отверстия таким образом, что при последовательном отражении или поворачивании и заполнении открытых клеток карточки постепенно будут заполнены все клетки листа.

Карточку сначала отражают относительно вертикальной оси симметрии, затем - относительно горизонтальной оси, и снова - относительно вертикальной (рис. 1.8).

Если решетка Кардано - квадратная, то возможен и другой вариант ее преобразований - поворот на 90° (рис. 1.9).

Рис. 1.8.

Рис. 1.9.

При записи обычным способом (слева направо и сверху вниз) словосочетания «шифрование текста» (без пробелов) в свободные клетки поворотной решетки, изображенной на рис. 1.9, получим текст в виде таблицы (рис. 1.10), или, записав текст в одну строку, - «кшииоесвтафатрен».

Рис. 1.10.

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

Например, для решеток размером 4X4 существует 256 возможных вариантов трафарета (с учетом начальной ориентации) или всего 64 различных трафаретов.

Несмотря на то, что число трафаретов для больших решеток достаточно велико (порядка 4 млн (4- 10 е)), оно все же существенно меньше, чем случайных перестановок элементов таблицы, число которых равно (2т? 2k).

Например, для таблицы размером 4x4 число случайных перестановок составляет порядка 2 ? 10 13 , а для таблиц размером 8x8 - около 10 89 .

Решетки Кардано, так же как и шифрующие таблицы, являются частными случаями шифра маршрутной перестановки.