Шифр Полибия

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

История

Изобретение шифра приписывается древнегреческому историку и полководцу Полибию (ок. 200 — ок. 120 гг. до н. э.), который описал его в своём труде «Всеобщая история» (книга X, глава 45). Полибий предложил использовать систему для передачи тактических сообщений на поле боя с помощью факелов: по два факела в каждой руке сигнальщика обозначали номер строки и столбца таблицы. Таким образом можно было быстро передать любую букву греческого алфавита на расстояние до нескольких километров.

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

Устройство и принцип работы

Таблица Полибия

Основой шифра является квадратная таблица размером \( n \times n \), где \( n \) — количество строк и столбцов. Для алфавита, содержащего \( m \) букв, выбирается такое \( n \), чтобы \( n^2 \ge m \). Обычно используется таблица размером 5×5 для 25 букв (например, для латинского алфавита без J или для русского алфавита с объединением букв Ё и Е, или с исключением редких букв). Для русского алфавита из 33 букв применяется таблица 6×6 (36 ячеек), в которую помещаются все буквы, а оставшиеся ячейки могут заполняться знаками препинания или цифрами.

Строки и столбцы таблицы нумеруются числами от 1 до \( n \) (или буквами, например, для латинского алфавита — A, B, C, D, E). Каждая буква алфавита записывается в одну из ячеек. Порядок заполнения может быть:

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

Шифрование и дешифрование

Шифрование: Для каждой буквы открытого текста определяется её положение в таблице (номер строки и номер столбца). Эти два числа записываются последовательно (например, «строка-столбец»). Таким образом, каждая буква заменяется парой цифр.

Пример для латинского алфавита (5×5, без J, прямой порядок):

Открытый текст: HELLO

• H → строка 2, столбец 3 → 23
• E → строка 1, столбец 5 → 15
• L → строка 3, столбец 1 → 31
• L → 31
• O → строка 3, столбец 4 → 34

Шифротекст: 23 15 31 31 34 (или без пробелов: 2315313134).

Дешифрование: Шифротекст разбивается на пары цифр. Каждая пара указывает на строку и столбец, по которым из таблицы извлекается исходная буква.

Варианты

• Цифровой вариант: вместо букв для нумерации строк и столбцов могут использоваться цифры от 0 до 9 (для таблицы 10×10). Это позволяет шифровать не только буквы, но и цифры и знаки.
• Буквенный вариант: строки и столбцы обозначаются буквами (например, A–E для таблицы 5×5). Тогда шифротекст состоит из двух букв на каждую букву открытого текста (например, AD вместо 14). Такой вариант использовался в шифре ADFGVX.
• С перестановкой: координаты могут записываться не в порядке «строка-столбец», а «столбец-строка» или в обратном порядке.
• С ключевым словом: таблица заполняется не по алфавиту, а начиная с ключевого слова, что усложняет криптоанализ.

Криптостойкость

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

Основные недостатки:

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

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

Применение

Историческое

• Древняя Греция: передача сообщений с помощью факелов на расстояние до 5 км. Сигнальщик поднимал левую руку с факелами для обозначения номера строки, правую — для номера столбца.
• Римская империя: использовался для шифрования военных донесений, передаваемых гонцами.
• Средневековье: применялся в дипломатической переписке, часто в сочетании с другими шифрами.
• Первая мировая война: германский шифр ADFGVX (модификация квадрата Полибия с перестановкой столбцов) использовался для шифрования радиограмм на Западном фронте. Был взломан французским криптоаналитиком Жоржем Пенвеном в 1918 году.

Современное

• Образование: шифр Полибия часто используется на уроках информатики и криптографии для демонстрации принципов шифрования замены и частотного анализа.
• Криптография в играх: применяется в настольных и компьютерных играх (например, в серии игр Assassin’s Creed), а также в головоломках и квестах.
• Стеганография: координаты могут быть закодированы не числами, а другими символами (например, цветами, жестами, звуками), что позволяет скрыть сам факт передачи сообщения.
• Системы сигнализации: принцип квадрата Полибия используется в некоторых системах световой и звуковой сигнализации (например, в азбуке Морзе с двухзначным кодом).

Интересные факты

• Шифр Полибия является предшественником современных бинарных кодов, где каждая буква кодируется фиксированным числом бит (например, ASCII). В квадрате Полибия каждой букве соответствует два символа (координаты), что аналогично двухмерному кодированию.
• В некоторых вариантах шифра для русского алфавита буквы Ё и Е считаются одной буквой, а буква Ъ может быть опущена или заменена на Ь.
• Шифр Полибия иногда называют «квадратом Полибия» или «полибианским квадратом».
• В 2014 году шифр Полибия был использован в качестве одной из загадок в популярной телепередаче «Форт Боярд».

Критика

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

Источники

• Полибий. «Всеобщая история». Книга X, глава 45.
• Кан, Дэвид. «Взломщики кодов: История тайного письма». — М.: Центрполиграф, 2000.
• Сингх, Саймон. «Книга шифров: Тайная история шифров и их расшифровки». — М.: АСТ, 2007.
• Шнайер, Брюс. «Прикладная криптография». — М.: Триумф, 2002.
• «Криптография: от древности до наших дней». — М.: Наука, 2010.