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

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

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

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

Рис. 1 Ключ к шифру с заменой букв и обратно.

Теперь обратимся к таблице 2, где алфавиту присвоена нумерация.

Рис. 2 Таблица соответствия букв и цифр алфавитов.

Теперь зашифруем словоК О С Т Е Р :

1) 1. Переведем буквы в цифры:К = 12, О = 16, С =19, Т = 20, Ё = 7, Р = 18

2) 2. Переведем цифры в символы согласно таблицы 1.

КП КТ КД ПЩ Ь КЛ

3) 3. Готово.

Этот пример показывает примитивный шифр. Рассмотрим похожие по сложности шрифты.

1. 1. Самым простым шифром является ШИФР С ЗАМЕНОЙ БУКВ ЦИФРАМИ. Каждой букве соответствует число по алфавитному порядку. А-1, B-2, C-3 и т.д.
Например слово «TOWN » можно записать как «20 15 23 14», но особой секретности и сложности в дешифровке это не вызовет.

2. Также можно зашифровывать сообщения с помощью ЦИФРОВОЙ ТАБЛИЦЫ. Её параметры могут быть какими угодно, главное, чтобы получатель и отправитель были в курсе. Пример цифровой таблицы.

Рис. 3 Цифровая таблица. Первая цифра в шифре – столбец, вторая – строка или наоборот. Так слово «MIND» можно зашифровать как «33 24 34 14».

3. 3. КНИЖНЫЙ ШИФР
В таком шифре ключом является некая книга, имеющаяся и у отправителя и у получателя. В шифре обозначается страница книги и строка, первое слово которой и является разгадкой. Дешифровка невозможна, если книги у отправителя и корреспондента разных годов издания и выпуска. Книги обязательно должны быть идентичными.

4. 4. ШИФР ЦЕЗАРЯ (шифр сдвига, сдвиг Цезаря)
Известный шифр. Сутью данного шифра является замена одной буквы другой, находящейся на некоторое постоянное число позиций левее или правее от неё в алфавите. Гай Юлий Цезарь использовал этот способ шифрования при переписке со своими генералами для защиты военных сообщений. Этот шифр довольно легко взламывается, поэтому используется редко. Сдвиг на 4. A = E, B= F, C=G, D=H и т.д.
Пример шифра Цезаря: зашифруем слово « DEDUCTION » .
Получаем: GHGXFWLRQ . (сдвиг на 3)

Еще пример:

Шифрование с использованием ключа К=3 . Буква «С» «сдвигается» на три буквы вперёд и становится буквой «Ф». Твёрдый знак, перемещённый на три буквы вперёд, становится буквой «Э», и так далее:

Исходный алфавит:А Б В Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я

Шифрованный:Г Д Е Ё Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ъ Ы Ь Э Ю Я А Б В

Оригинальный текст:

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

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

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

5. ШИФР С КОДОВЫМ СЛОВОМ
Еще один простой способ как в шифровании, так и в расшифровке. Используется кодовое слово (любое слово без повторяющихся букв). Данное слово вставляется впереди алфавита и остальные буквы по порядку дописываются, исключая те, которые уже есть в кодовом слове. Пример: кодовое слово – NOTEPAD.
Исходный: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
Замена:N O T E P A D B C F G H I J K L M Q R S U V W X Y Z

6. 6. ШИФР АТБАШ
Один из наиболее простых способов шифрования. Первая буква алфавита заменяется на последнюю, вторая – на предпоследнюю и т.д.
Пример: « SCIENCE » = HXRVMXV

7. 7. ШИФР ФРЕНСИСА БЭКОНА
Один из наиболее простых методов шифрования. Для шифрования используется алфавит шифра Бэкона: каждая буква слова заменяется группой из пяти букв «А» или «B» (двоичный код).

a AAAAA g AABBA m ABABB s BAAAB y BABBA

b AAAAB h AABBB n ABBAA t BAABA z BABBB

c AAABA i ABAAA o ABBAB u BAABB

d AAABB j BBBAA p ABBBA v BBBAB

e AABAA k ABAAB q ABBBB w BABAA

f AABAB l ABABA r BAAAA x BABAB

Сложность дешифрования заключается в определении шифра. Как только он определен, сообщение легко раскладывается по алфавиту.
Существует несколько способов кодирования.
Также можно зашифровать предложение с помощью двоичного кода. Определяются параметры (например, «А» - от A до L, «В» - от L до Z). Таким образом, BAABAAAAABAAAABABABB означает TheScience of Deduction ! Этот способ более сложен и утомителен, но намного надежнее алфавитного варианта.

8. 8. ШИФР БЛЕЗА ВИЖЕНЕРА.
Этот шифр использовался конфедератами во время Гражданской войны. Шифр состоит из 26 шифров Цезаря с различными значениями сдвига (26 букв лат.алфавита). Для зашифровывания может использоваться tabula recta (квадрат Виженера). Изначально выбирается слово-ключ и исходный текст. Слово ключ записывается циклически, пока не заполнит всю длину исходного текста. Далее по таблице буквы ключа и исходного текста пересекаются в таблице и образуют зашифрованный текст.

Рис. 4 Шифр Блеза Виженера

9. 9. ШИФР ЛЕСТЕРА ХИЛЛА
Основан на линейной алгебре. Был изобретен в 1929 году.
В таком шифре каждой букве соответствует число (A = 0, B =1 и т.д.). Блок из n-букв рассматривается как n-мерный вектор и умножается на (n х n) матрицу по mod 26. Матрица и является ключом шифра. Для возможности расшифровки она должна быть обратима в Z26n.
Для того, чтобы расшифровать сообщение, необходимо обратить зашифрованный текст обратно в вектор и умножить на обратную матрицу ключа. Для подробной информации – Википедия в помощь.

10. 10. ШИФР ТРИТЕМИУСА
Усовершенствованный шифр Цезаря. При расшифровке легче всего пользоваться формулой:
L= (m+k) modN , L-номер зашифрованной буквы в алфавите, m-порядковый номер буквы шифруемого текста в алфавите, k-число сдвига, N-количество букв в алфавите.
Является частным случаем аффинного шифра.

11. 11. МАСОНСКИЙ ШИФР

12. 12. ШИФР ГРОНСФЕЛЬДА

По своему содержанию этот шифр включает в себя шифр Цезаря и шифр Виженера, однако в шифре Гронсфельда используется числовой ключ. Зашифруем слово “THALAMUS”, используя в качестве ключа число 4123. Вписываем цифры числового ключа по порядку под каждой буквой слова. Цифра под буквой будет указывать на количество позиций, на которые нужно сдвинуть буквы. К примеру вместо Т получится Х и т.д.

T H A L A M U S
4 1 2 3 4 1 2 3

T U V W X Y Z
0 1 2 3 4

В итоге: THALAMUS = XICOENWV

13. 13. ПОРОСЯЧЬЯ ЛАТЫНЬ
Чаще используется как детская забава, особой трудности в дешифровке не вызывает. Обязательно употребление английского языка, латынь здесь ни при чем.
В словах, начинающихся с согласных букв, эти согласные перемещаются назад и добавляется “суффикс” ay. Пример: question = estionquay. Если же слово начинается с гласной, то к концу просто добавляется ay, way, yay или hay (пример: a dog = aay ogday).
В русском языке такой метод тоже используется. Называют его по-разному: “синий язык”, “солёный язык”, “белый язык”, “фиолетовый язык”. Таким образом, в Синем языке после слога, содержащего гласную, добавляется слог с этой же гласной, но с добавлением согласной “с” (т.к. язык синий). Пример:Информация поступает в ядра таламуса = Инсифорсомасацисияся поссотусупасаетсе в ядсяраса тасаласамусусаса.
Довольно увлекательный вариант.

14. 14. КВАДРАТ ПОЛИБИЯ
Подобие цифровой таблицы. Существует несколько методов использования квадрата Полибия. Пример квадрата Полибия: составляем таблицу 5х5 (6х6 в зависимости от количества букв в алфавите).

1 МЕТОД. Вместо каждой буквы в слове используется соответствующая ей буква снизу (A = F, B = G и т.д.). Пример: CIPHER - HOUNIW.
2 МЕТОД. Указываются соответствующие каждой букве цифры из таблицы. Первой пишется цифра по горизонтали, второй - по вертикали. (A = 11, B = 21…). Пример: CIPHER = 31 42 53 32 51 24
3 МЕТОД. Основываясь на предыдущий метод, запишем полученный код слитно. 314253325124. Делаем сдвиг влево на одну позицию. 142533251243. Снова разделяем код попарно.14 25 33 25 12 43. В итоге получаем шифр. Пары цифр соответствуют букве в таблице: QWNWFO.

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

Методы вскрытия одноалфавитных систем (расшифровка)

При своей простоте в реализации одноалфавитные системы шифрования легко уязвимы.
Определим количество различных систем в аффинной системе. Каждый ключ полностью определен парой целых чисел a и b, задающих отображение ax+b. Для а существует j(n) возможных значений, где j(n) - функция Эйлера, возвращающая количество взаимно простых чисел с n, и n значений для b, которые могут быть использованы независимо от a, за исключением тождественного отображения (a=1 b=0), которое мы рассматривать не будем.
Таким образом получается j(n)*n-1 возможных значений, что не так уж и много: при n=33 в качестве a могут быть 20 значений(1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 29, 31, 32), тогда общее число ключей равно 20*33-1=659. Перебор такого количества ключей не составит труда при использовании компьютера.
Но существуют методы упрощающие этот поиск и которые могут быть использованы при анализе более сложных шифров.
Частотный анализ
Одним из таких методов является частотный анализ. Распределение букв в криптотексте сравнивается с распределением букв в алфавите исходного сообщения. Буквы с наибольшей частотой в криптотексте заменяются на букву с наибольшей частотой из алфавита. Вероятность успешного вскрытия повышается с увеличением длины криптотекста.
Существуют множество различных таблиц о распределении букв в том или ином языке, но ни одна из них не содержит окончательной информации - даже порядок букв может отличаться в различных таблицах. Распределение букв очень сильно зависит от типа теста: проза, разговорный язык, технический язык и т.п. В методических указаниях к лабораторной работе приведены частотные характеристики для различных языков, из которых ясно, что буквы буквы I, N, S, E, A (И, Н, С, Е, А) появляются в высокочастотном классе каждого языка.
Простейшая защита против атак, основанных на подсчете частот, обеспечивается в системе омофонов (HOMOPHONES) - однозвучных подстановочных шифров, в которых один символ открытого текста отображается на несколько символов шифротекста, их число пропорционально частоте появления буквы. Шифруя букву исходного сообщения, мы выбираем случайно одну из ее замен. Следовательно простой подсчет частот ничего не дает криптоаналитику. Однако доступна информация о распределении пар и троек букв в различных естественных языках.

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

Простейшим из шифров замены является одноалфавитная подстановка , называемая также шифром простой замены . Ключом такого шифра является взаимно однозначное отображение (подстановка ) F алфавита открытого текста (X ) в алфавит шифртекста (Y ): F : X ↔Y . Зафиксируем нумерацию символов в алфавитах X и Y : X = {x 1 , x 2 , … x n }, Y = {y 1 , y 2 , … y n }. Тогда отображение F фактически задается перестановкой p порядка n = |X | = |Y |: при шифровании символ x i открытого текста заменяется на символ y p ( i ) шифртекста. Эта перестановка может быть задана либо таблицей, либо с помощью формулы. При задании с помощью формулы значение p(i ) представляется в виде выражения, зависящего от i .

Типичным примером шифра замены является шифр Цезаря . Этот шифр реализует следующее преобразование текста, записанного с помощью латинского алфавита: каждая буква открытого текста заменяется буквой, стоящей на три позиции позже нее в алфавите (при этом алфавит считается записанным по кругу, то есть после буквы "z" идет буква "a"). Например, открытый текст "secret" будет преобразован в "vhfuhw". Ключ для шифра Цезаря можно задать в виде следующей таблицы (см. рис. 2.3). В первой строке записаны буквы открытого текста, во второй – соответствующие им буквы шифртекста.

Шифр Цезаря можно описать и в виде формулы. Для этого пронумеруем буквы латинского алфавита числами от 0 до 25: a = 0, b = 1, …, z = 25. Тогда правило замены можно описать следующим образом: буква с номером i i +3 (mod 26), где операция "mod 26" означает вычисление остатка от деления на 26.

Разумеется, возможен обобщенный вариант шифра Цезаря, при котором буква с номером i заменяется на букву с номером i +k (mod 26). В этом случае ключом шифра является число k .

Еще больше обобщив этот метод, мы придем к семейству аффинных шифров . Для алфавита из n символов {a 1 , a 2 , …, a n } аффинным шифром называется процедура, заменяющая входной символ a i на символ a j , где j = k ⋅i +l (mod n ). Для того чтобы имелась возможность расшифрования числа n и k должны быть взаимно простыми, то есть НОД(n , k ) = 1.

Шифры простой замены в настоящее время не используются, поскольку их стойкость невелика. Методы взлома таких шифров основаны на анализе частотности отдельных символов и их комбинаций. Дело в том, что в любом языке различные буквы и комбинации из двух, трех или большего количества букв имеют характерные частоты повторений в текстах. Например, в текстах на русском языке чаще всего встречается буква "О", затем, в порядке убывания частоты, идут буквы "Е" (считая, что "Е" и "Ё" – одна и та же буква), "А", "И", "Т" и т.д. Для английского языка аналогичная последовательность самых частых букв: "E", "T", "A", "I", "N". Самым частым символом в текстах является, однако, не буква, а символ пробела.

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

Для того чтобы увеличить стойкость шифров замены, применяют многоалфавитную подстановку, называемую также шифром сложной замены . Процедура шифрования для многоалфавитной замены включает набор подстановок {p 1 , p 2 ,…, p m } и функцию-распределительY (k ,i ), задающую последовательность применения подстановок p i . При шифровании i -го символа открытого текста применяется подстановка с номером Y (k ,i ), где k - ключ шифрования.

Частным случаем многоалфавитной замены является шифр Виженера. Формально этот шифр можно описать следующим образом. В качестве ключа шифрования выберем набор из m целых чисел: k = (k 1 , k 2 , …, k m ). Процедуру преобразования открытого текста t = (t 1 , t 2 , …) в шифртекст c = (c 1 , c 2 , …) построим на основе обобщенного шифра Цезаря: c 1 = t 1 + k 1 (mod 26),
c 2 = t 2 + k 2 (mod 26), и т.д. Когда будут использованы все m компонент ключа k , для шифрования (m +1)-й буквы снова возьмем k 1 , и т.д. Фактически, в качестве ключа шифрования используется гамма шифра – бесконечная последовательность, образованная периодическим повторением исходного набора: k 1 ,k 2 ,…,k m , k 1 ,k 2 ,…,k m , k 1 ,k 2 ,…

Взломать шифр многоалфавитной замены немного сложнее, чем шифры простой замены, но тоже достаточно легко. Такой шифр на самом деле представляет собой одновременное применение m шифров простой замены (обобщенный шифр Цезаря), причем часть исходного текста, состоящая из букв t i , t m+i , t 2 m+i , … шифруются с использованием "ключа" k i (i =1, …,m ).

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

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

Простейшим вариантом гомофонического шифра является следующий. Предположим, что нам известны частоты вхождений символов в открытый текст. Пусть f i - частота появления i –го символа в открытом текста (i - номер буквы в алфавите). Каждой букве t i исходного алфавита (т.е. алфавита, с помощью которого записывается открытое сообщение) сопоставим подмножество F i , содержащее f i символов выходного алфавита (т.е. алфавита, с помощью которого записывается шифртекст), причем никакие два подмножества F i и F j не пересекаются. При шифровании будем заменять каждое вхождение символа t i на случайный символ из множества F i . Ясно, что средняя частота появления в шифртексте любого из символов выходного алфавита одинакова, что существенно затрудняет криптоанализ.

Шифры гаммирования

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

Суть метода гаммирования заключается в следующем. С помощью секретного ключа k генерируется последовательность символов

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

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

Расшифрование осуществляется применением к символам шифртекста и гаммы обратной операции: , или (операция XOR является обратной к самой себе).

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

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

1) все символы гаммы полностью случайны и появляются в гамме с равными вероятностями;

2) длина гаммы равна длине открытого текста или превышает ее;

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

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

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

Линейный конгруэнтный генератор задается рекуррентной формулой: g i = a ×g i – 1 + b (mod m ), где g i – i -й член последовательности псевдослучайных чисел; a , b , m и g 0 – ключевые параметры. Данная последовательность состоит из целых чисел от 0 до m – 1, и если элементы g i и g j совпадут, то последующие участки последовательности также совпадут: g i +1 = g j +1 , g i +2 = g j +2 , и т.д. Поэтому последовательность {g i } является периодической, и ее период не превышает m . Для того чтобы период последовательности псевдослучайных чисел, сгенерированной по указанной рекуррентной формуле, был максимальным (равным m), параметры данной формулы должны удовлетворять следующим условиям:

· b и m -взаимно простые числа;

· a – 1 делится на любой простой делитель числа m ;

· a – 1 кратно 4, если m кратно 4.

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

, i = 0,1…,

где Å – операция вычисления суммы по модулю 2, – состояние j -го бита последовательности, – коэффициент обратной связи, , коэффициенты .

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

Последовательности такого вида легко реализуются программными или аппаратными средствами. Основу этой реализации составляет регистр сдвига с линейной обратной связью (РСЛОС).

РСЛОС представляет собой простое в реализации, недорогое устройство, способное формировать последовательности и обеспечить такие требования как:

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

· оптимальность корреляционных функций в ансамбле;

· сбалансированность структуры;

· максимальность периода для данной длины регистра сдвига.

Обобщенная схема РСЛОС приведена на рис. 2.4.

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

Обратная связь представляет собой просто операцию XOR над битами регистра, для которых значения коэффициентов обратной связи равно 1. Перечень этих битов называется отводной последовательностью .

Любой n -битовый РСЛОС может находиться в одном из 2 n –1 внутренних состояний. Это означает, что теоретически такой регистр может генерировать псевдослучайную последовательность с периодом 2 n –1 битов. (Число внутренних состояний и максимальный период равны 2 n –1, потому что заполнение РСЛОС нулями, приведет к тому, что сдвиговый регистр будет выдавать бесконечную последовательность нулей, что абсолютно бесполезно.) Только при определенных отводных последовательностях РСЛОС циклически пройдет через все 2 n –1 внутренних состояний, такие РСЛОС являются регистрами с максимальным периодом. Получившийся результат называется М – последовательностью .

Для того, чтобы конкретный n -битовый РСЛОС имел максимальный период 2 n –1, двоичный полином f (x ) = h n x n + h n – 1 x n – 1 + … + h 1 x + 1, образованный из отводной последовательности и константы 1, должен быть примитивным. Полином f (x ) степени n называется примитивным , если его нельзя представить в виде произведения двух полиномов с меньшими степенями (свойство неприводимости) и, если x является генератором всех ненулевых полиномов со степенями не выше n , умножение которых осуществляется по модулю f (x ).

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

Шифр замены

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

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

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

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

Шифр Атбаш

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

Алфавит замены: 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 .

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

Если множества состоят из одного элемента, то такой шифр называют шифром простой замены.

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

При шифровании каждой буквы исходного текста ее заменяют буквой, которая находится под ней во второй строке таблицы. Ключ такого шифра легко запомнить по первой букве второй строки. Процесс дешифрации выполняется в обратном порядке - каждую букву шифротекста находят во второй строке таблицы и заменяют на букву над ней (с первой строки). Число ключей такого шифра не превышает количество букв алфавита (для русскоязычных текстов Т = 33).

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

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

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

> Матрица букв

шифрограмм

Столбец ключа

Строка букв

открытого

Рис. 5.1. Таблица Вижинера

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

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

Задача 5.5

Пусть необходимо зашифровать следующий открытый текст : «ТО BE OR NOT ТО BE THAT IS THE QUESTION», используя секретный ключ «RELATIONS».

Решение.

Разобьем процесс шифрования на следующие этапы.

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

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

После шифрования получим криптограмму:

«КЗ МЕ НЕЕ ВВЬ КБ МЕ МРСЮ А1 ХЭЕ,Ю5ЕЕ78У».

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

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

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

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

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

одинаковых элементов. Множество называется множеством Шифр-обозначений для буквы а.

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

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

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

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

Часто состоит из одного элемента. Например, в романе Верна «Путешествие к центру Земли» в руки профессора Лиденброка попадает пергамент с рукописью из знаков рунического письма. Каждое множество состоит из одного элемента. Элемент каждого множества выбирается из набора символов вида

В рассказе А. Конан Дойла «Пляшущие человечки» каждый символ изображает пляшущего человечка в самых различных позах

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

Рассмотрим некоторые примеры шифров замены. Пусть каждое множество состоит из одной буквы. Например,

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

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

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

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

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

Другим примером шифра замены может служить лозунговый шифр. Здесь запоминание ключевой последовательности основано на лозунге - легко запоминаемом слове. Например, выберем слово-лозунг «учебник» и заполним вторую строку таблицы по следующему правилу: сначала выписываем слово-лозунг, а затем выписываем в алфавитном порядке буквы алфавита, не вошедшие в слово-лозунг. Вторая строка в (4) примет вид

В данном случае число вариантов ключа существенно больше числа букв алфавита.

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

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

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

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

Популярные у школьников криптограммы (типа рассмотренной в задаче 1.5) по сути дела являются шифром замены с ключом

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

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

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

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

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

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

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

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