Квадрат Полибия

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

[править | править код]

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

Шаг 1: Формирование таблицы шифрования[2]

[править | править код]

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

Латинский алфавит

[править | править код]

В современном латинском алфавите 26 букв, следовательно, таблица должна состоять из 5 строк и 5 столбцов, так как 25=5*5 — наиболее близкое к 26 число. При этом буквы I, J не различаются (J отождествляется с буквой I), так как не хватает 1 ячейки:

1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Русский алфавит[3]

[править | править код]

Идею формирования таблицы шифрования проиллюстрируем для русского языка. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33):

1 2 3 4 5 6
1 А Б В Г Д Е
2 Ё Ж З И Й К
3 Л М Н О П Р
4 С Т У Ф Х Ц
5 Ч Ш Щ Ъ Ы Ь
6 Э Ю Я - - -

Возможен также другой вариант составления, предусматривающий объединение букв Е и Ё, И и Й, Ъ и Ь. В данном случае получаем следующий результат:

1 2 3 4 5 6
1 А Б В Г Д Е/Ё
2 Ж З И/Й К Л М
3 Н О П Р С Т
4 У Ф Х Ц Ч Ш
5 Щ Ы Ь/Ъ Э Ю Я

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

Или есть такой вариант: Шифр «Квадрат Полибия».

«Квадрат Полибия» представляет собой квадрат 5x5, столбцы и строки которого нумеруются цифрами от 1 до 5. В каждую клетку этого квадрата записывается одна буква (в русском [каком?] алфавите 31 буква, Ъ и Ё исключены, кроме того в одну клетку поместите буквы е-э, и-й, ж-з, р-с, ф-х, ш-щ). Буквы расположены в алфавитном порядке. В результате каждой букве соответствует пара чисел, и шифрованное сообщение превращается в последовательность пар чисел. Расшифровывается путём нахождения буквы, стоящей на пересечении строки и столбца.

1 2 3 4 5
1 А Б В Г Д
2 Е/Э Ж/З И/Й К Л
3 М Н О П Р/С
4 Т У Ф/Х Ц Ч
5 Ш/Щ Ы Ь Ю Я

Шаг 2: Принцип шифрования

[править | править код]

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

1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Зашифруем слово «sometext»:

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

Таблица координат
Буква текста: S O M E T E X T
Буква шифротекста : X T R K Y K C Y

Таким образом после шифрования получаем:

Результат
До шифрования: SOMETEXT
После шифрования: XTRKYKCY
1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

Сообщение преобразуется в координаты по квадрату Полибия, координаты записываются вертикально:

Таблица координат
Буква: S O M E T E X T
Координата вертикальная: 3 4 2 5 4 5 3 4
Координата горизонтальная: 4 3 3 1 4 1 5 4

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

34  25  45  34  43  31  41  54                                                                                                                   (*)

Далее координаты преобразуются в буквы по этому же квадрату:

Таблица координат
Координата вертикальная: 3 2 4 3 4 3 4 5
Координата горизонтальная: 4 5 5 4 3 1 1 4
Буква: S W Y S O C D U

Таким образом после шифрования получаем:

Результат
До шифрования: SOMETEXT
После шифрования: SWYSOCDU
1 2 3 4 5
1 A B C D E
2 F G H I/J K
3 L M N O P
4 Q R S T U
5 V W X Y Z

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

3425453443314154	

Полученная последовательность цифр сдвигается циклически влево на один шаг (нечётное количество шагов, т.е. цифра 3 перемещается в конец):

4254534433141543

Эта последовательность вновь разбивается в группы по два:

42 54 53 44 33 14 15 43

и по таблице заменяется на окончательный шифротекст:

Таблица координат
Координата вертикальная: 4 5 5 4 3 1 1 4
Координата горизонтальная: 2 4 3 4 3 4 5 3
Буква: I U P T N Q V O

Таким образом после шифрования получаем:

Результат
До шифрования: SOMETEXT
После шифрования: IUPTNQVO

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

[править | править код]

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

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

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

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

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

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

1 2 3 4 5
1 D R A F T
2 B C E G H
3 I K L M N
4 O P Q S U
5 V W X Y Z

Преобразуем сообщение в координаты по квадрату Полибия:

Таблица координат
Буква: S O M E T E X T
Координата вертикальная: 4 1 4 3 5 3 3 5
Координата горизонтальная: 4 4 3 2 1 2 5 1

Считаем координаты по строкам:

41 43 53 35 44 32 12 51

Преобразуем координаты в буквы по этому же квадрату:

Таблица координат
Координата вертикальная: 4 4 5 3 4 3 1 5
Координата горизонтальная: 1 3 3 5 4 2 2 1
Буква: F M N X S E B T

Таким образом после шифрования получаем:

Результат
До шифрования: SOMETEXT
После шифрования: FMNXSEBT

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

[править | править код]

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

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

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

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

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

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

[править | править код]

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

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

Примечания

[править | править код]
  1. УДК 511 Коробейников А. Г, Ю. А. Гатчин. Математические основы криптологии Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с, илл. Лицензия ИД № 00408 от 05.11.99
  2. Kahn D. The Codebreakers; The Comprehensive History of Secret Communication from Ancient Times to the Internet, N- Y: Macmillan Publ. Co. 1996.
  3. Антонов А. К., Артюшенко В. М. Защита информации. Методы защиты информации. Ч.1.: Курс лекций / М. : ГОУВПО МГУС, 2005—191 с.
  4. Баричев С. Г. Основы современной криптографии. М.: Горячая Линия — Телеком, 2001. 152 стр.
  5. Астрахан В. И., Гусев В. В., Павлов В. В., Чернявский Б. Г. Становление и развитие правительственной связи в России, Орел: ВИПС, 1996.
  6. Дильс Г. Античная техника. Под ред. С. И. Ковалева. М. — Л., Гостехиздат, 1934
  7. Полибий. Всеобщая история в сорока книгах. Пер. с греч. Ф. Г. Мищенко. Т . 2, М ., 1895, с . 282—284.
  8. Варфоломеев А. А., Жуков А. Е., Пудовкина М. А. Поточные крипто- системы. Основные свойства и методы анализа стойкости. М.: «ПАИМС». 2000.