WikiSort.ru - Не сортированное

В криптографии квадрат Полибия (англ. Polybius square), также известный как шахматная доска Полибия — оригинальный код простой замены, одна из древнейших систем кодирования, предложенная Полибием (греческий историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого алфавита^[1], но затем был распространен на другие языки.

Способ шифрования

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

   1    2   3    4   5

1  А    Б   В    Г   Д

2 Е/Э   Ж   З   И/Й  К

3  Л    М   Н    О   П

4 Р/С   Т   У   Ф/Х  Ц

5  Ч   Ш/Щ  Ы    Ю   Я

34  25  45  34  43  31  41  54                                                                                                                   (*)

3425453443314154	

4254534433141543

42 54 53 44 33 14 15 43

Добавление ключа^[4]

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

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

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

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

${\displaystyle N=25*24*23*...*2*1=25!\,(\approx 1,55\cdot 10^{25})}$

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

41 43 53 35 44 32 12 51

Историческая справка^[5]

Ещё в далекой древности у человека возникла необходимость передачи сигналов на расстояние. Для усиления голоса при подаче сигналов на охоте стали применять простейшие рупоры в виде рогов, раковин и др. Целями подачи служили тамтамы, барабаны и подобные им устройства, а чуть позже световые средства — факелы, костры. Даже эти примитивные предметы световой сигнализации позволили резко увеличить расстояние, на котором людям удавалось поддерживать связь.^[6]

С развитием общества возникла необходимость в передаче более разнообразных сигналов, в том числе сигналов, смысл которых не был обусловлен заранее. В книге Полибия описан способ^[7] применения водяных часов, так называемых клепсидр, в устройстве для дальней сигнализации. Клепсидры представляли собой сосуды с водой, на поверхности которой находились поплавки с вертикальными стойками на них. Вода из сосудов вытекала с постоянной скоростью, и длина видимой части стоек была обратно пропорциональна времени. Суть использования клепсидр для сигнализации состояла в том, что их вертикальные стойки имели однотипную разметку: вместо часовых делений на них были написаны в одинаковой последовательности различные слова, команды и т. п. По условному сигналу с передающего пункта обе клепсидры одновременно запускались, а по другому сигналу останавливались в тот момент, когда на стойках была видна надпись, которую нужно было передать. Так как клепсидры были довольно точными часами, то на передающем и на приемном пунктах они показывали один и тот же сигнал. В этом способе связи дальность определялась условиями видимости сигналов, которые могли подаваться любыми другими известными тогда сигнальными средствами.

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

Полибий описывает также и второй способ сигнализации, основанный на ином принципе, изобретение которого он связывает с именами Клеоксена и Демоклита из Александрии. По этому способу для сигнализации использовали факелы, которые выставляли на сигнальной стене. При этом существовал определенный код, составленный следующим образом. Греческий алфавит (24 буквы) разделяли на 5 групп таким образом, что каждая буква определялась номером группы и порядковым номером её в группе. Число факелов в левой части сигнальной стены означало номер группы, а число факелов в правой части стены — номер места в группе. Такой способ, хотя и требовал много времени на передачу каждого сигнала, однако давал возможность передавать буквенным текстом любое сообщение. Полибий, описывая этот способ, как раз приводил таблицу такого кода (таблица Полибия), которая рассматривается в статье, в дальнейшем нашедшую применение во многих системах сигнализации. Это, по-видимому, была одна из первых попыток использовать код (пятеричный двухразрядный) для передачи информации.

Интересно заметить, что в несколько измененном виде код Полибия дошёл до наших дней и получил интересное название «тюремный шифр». Для его применения необходимо знать лишь естественный порядок расположения букв в алфавите (как в указанных выше примерах для латинского и русского алфавитов). Число 3, например, передавалось путём трехкратного стука. При передаче буквы сперва отстукивалось число, соответствующее строке, в которой располагалась буква, а затем номер столбца. Например, буква «H» передавалась двукратным стуком (вторая строка) и затем трехкратным (третий столбец). Доподлинно известно, что декабристы, посаженные в тюрьму после неудачного восстания 1825 года, не могли установить связь с находившимся в одиночной камере Петропавловской крепости князем Одоевским. Оказалось, что он не помнил естественный порядок расположения букв в русском и французском алфавитах (другими языками он не владел). Декабристы для русского алфавита использовали прямоугольник размера 5x6 и сжатый до 30 букв алфавит. Поэтому «Тюремный шифр», строго говоря, не шифр, а способ модификации сообщения с целью его приведения к виду, удобному для передачи по каналу связи (через стенку).

Устойчивость к криптоанализу^[8]

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

Известнейшим примером неустойчивости шифра замены к частотной атаке является рассказ Артура Конан Дойля «Пляшущие человечки».

Примечания

Ссылки

• Флеш-приложение «Тюремная азбука».
• Шифры Древности.
• Появление шифров.
• Шифрование. Шифры замены.
• Легкие шифры, Квадрат Полибия, основные методики.

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