Квадрат Полибия: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
[отпатрулированная версия][непроверенная версия]
Содержимое удалено Содержимое добавлено
м орфо, replaced: путем → путём (2)
м автоматическая отмена правки участника Федор Георгиевич Коновалов - R:5B ORES: 0.4512
Метка: откат
 
(не показано 56 промежуточных версий 41 участника)
Строка 1: Строка 1:
В [[криптография|криптографии]] '''квадрат Полибия''' ({{lang-en|Polybius square}}), также известный как шахматная доска Полибия — оригинальный [[код]] простой замены, одна из древнейших систем кодирования, предложенная [[Полибий|Полибием]] ([[греки|греческий]] историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого [[алфавит]]а<ref>УДК 511 Коробейников А. Г, Ю. А. Гатчин. Математические основы криптологии.
В [[криптография|криптографии]] '''квадрат Полибия''' ({{lang-en|Polybius square}}), также известный как [[шахматная доска]] Полибия — оригинальный [[код]] простой замены, одна из древнейших систем кодирования, предложенная [[Полибий|Полибием]] ([[греки|греческий]] историк, полководец, государственный деятель, III век до н. э.). Данный вид кодирования изначально применялся для греческого [[алфавит]]а<ref>УДК 511 Коробейников А. Г, Ю. А. Гатчин. Математические основы криптологии
Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с, илл.
Учебное пособие. СПб: СПб ГУ ИТМО, 2004. – 106 с, илл.
Лицензия ИД № 00408 от 05.11.99</ref>, но затем был распространен на другие языки.
Лицензия ИД № 00408 от 05.11.99</ref>, но затем был распространен на другие языки.


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


=== Шаг 1: Формирование таблицы шифрования<ref>Kahn D. The Codebreakers; The Comprehensive History of Secret Communication from Ancient Times to the Internet, N- Y: Macmillan Publ. Co. 1996.</ref> ===
=== Шаг 1: Формирование таблицы шифрования<ref>Kahn D. The Codebreakers; The Comprehensive History of Secret Communication from Ancient Times to the Internet, N- Y: Macmillan Publ. Co. 1996.</ref> ===
К каждому языку отдельно составляется таблица шифрования с одинаковым (не обязательно) количеством пронумерованных строк и столбцов, параметры которой зависят от его мощности (количества букв в алфавите). Берутся два целых числа, произведение которых ближе всего к количеству букв в языке — получаем нужное число строк и столбцов. Затем вписываем в таблицу все буквы алфавита подряд — по одной в каждую клетку. При нехватке клеток можно вписать в одну две буквы (редко употребляющиеся или схожие по употреблению).

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


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


{| class="wikitable" align="center"
{| class="wikitable" align="center"
Строка 28: Строка 27:
|}
|}


==== Русский алфавит<ref>Антонов А. К., Артюшенко В. М. Защита информации. Методы защиты информации. Ч.1.: Курс лекций / М. : ГОУВПО МГУС, 2005—191 с.</ref> ====
==== Русский алфавит<ref>Антонов А. К., Артюшенко В. М. Защита информации. Методы защиты информации. Ч.1.: Курс лекций / М. : ГОУВПО МГУС, 2005—191 с.</ref> ====
Идею формирования таблицы шифрования проиллюстрируем для [[русский язык|русского языка]]. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33):
Идею формирования таблицы шифрования проиллюстрируем для [[русский язык|русского языка]]. Число букв в русском алфавите отличается от числа букв в греческом алфавите, поэтому размер таблицы выбран другой (квадрат 6*6=36, поскольку 36 наиболее близкое число к 33):


Строка 48: Строка 47:
|}
|}


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


{| class="wikitable" align="center"
{| class="wikitable" align="center"
! || 1 || 2 || 3 || 4 || 5 || 6
! || 1 || 2 || 3 || 4 || 5 || 6
|-
|-
| 1 || А || Б || В || Г || Д || Е/Ё
|'''1'''|| А || Б || В || Г || Д || Е/Ё
|-
|-
| 2 || Ж || З || И/Й || К || Л || М
|'''2'''|| Ж || З || И/Й || К || Л || М
|-
|-
| 3 || Н || О || П || Р || С || Т
|'''3'''|| Н || О || П || Р || С || Т
|-
|-
| 4 || У || Ф || Х || Ц || Ч || Ш
|'''4'''|| У || Ф || Х || Ц || Ч || Ш
|-
|-
| 5 || Щ || Ы || Ь/Ъ || Э || Ю || Я
|'''5'''|| Щ || Ы || Ь/Ъ || Э || Ю || Я
|-
|-
|}
|}


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


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


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


{| class="wikitable" align="center"
<br />
1 2 3 4 5<br />
! || 1 || 2 || 3 || 4 || 5
|-
1 А Б В Г Д<br />
|'''1'''|| А || Б || В || Г || Д
2 Е/Э Ж З И/Й К<br />
|-
3 Л М Н О П<br />
|'''2'''|| Е/Э || Ж/З || И/Й || К || Л
4 Р/С Т У Ф/Х Ц<br />
|-
5 Ч Ш/Щ Ы Ю Я
|'''3'''|| М || Н || О || П || Р/С
|-
|'''4'''|| Т || У || Ф/Х || Ц || Ч
|-
|'''5'''|| Ш/Щ || Ы || Ь || Ю || Я
|}


=== Шаг 2: Принцип шифрования ===
=== Шаг 2: Принцип шифрования ===
Строка 84: Строка 89:


==== Метод 1 ====
==== Метод 1 ====
{| class="wikitable" align="center"
Зашифруем слово «SOMETEXT»:
! || 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»:


Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от неё в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.
Для шифрования на квадрате находили букву текста и вставляли в шифровку нижнюю от неё в том же столбце. Если буква была в нижней строке, то брали верхнюю из того же столбца.
Строка 101: Строка 120:
|+ Результат
|+ Результат
|- class="bright"
|- class="bright"
! colspan = «4» | До шифрования: || SOMETEXT
! colspan = «4» | До шифрования: ||SOMETEXT
|- class="bright"
|- class="bright"
! colspan = «4» | После шифрования: || XTRKYKCY
! colspan = «4» | После шифрования: || XTRKYKCY
Строка 107: Строка 126:


==== Метод 2 ====
==== Метод 2 ====
{| class="wikitable" align="center"
! || 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
|-
|}
Сообщение преобразуется в координаты по квадрату Полибия, координаты записываются вертикально:
Сообщение преобразуется в координаты по квадрату Полибия, координаты записываются вертикально:


Строка 114: Строка 147:
! colspan = «4» | Буква: || S || O || M || E || T || E || X || T
! colspan = «4» | Буква: || S || O || M || E || T || E || X || T
|- class="bright"
|- class="bright"
! colspan = «4» | Координата горизонтальная: || 3 || 4 || 2 || 5 || 4 || 5 || 3 || 4
! colspan = «4» | Координата вертикальная: || 3 || 4 || 2 || 5 || 4 || 5 || 3 || 4
|- class="bright"
|- class="bright"
! colspan = «4» | Координата вертикальная: || 4 || 3 || 3 || 1 || 4 || 1 || 5 || 4
! colspan = «4» | Координата горизонтальная: || 4 || 3 || 3 || 1 || 4 || 1 || 5 || 4
|}
|}


Строка 127: Строка 160:
|+ Таблица координат
|+ Таблица координат
|- class="bright"
|- class="bright"
! colspan = «4» | Координата горизонтальная: || 3 || 2 || 4 || 3 || 4 || 3 || 4 || 5
! colspan = «4» | Координата вертикальная: || 3 || 2 || 4 || 3 || 4 || 3 || 4 || 5
|- class="bright"
|- class="bright"
! colspan = «4» | Координата вертикальная: || 4 || 5 || 5 || 4 || 3 || 1 || 1 || 4
! colspan = «4» | Координата горизонтальная: || 4 || 5 || 5 || 4 || 3 || 1 || 1 || 4
|- class="highlight"
|- class="highlight"
! colspan = «4» | Буква: || S || W || Y || S || O || C || D || U
! colspan = «4» | Буква: || S || W || Y || S || O || C || D || U
Строка 145: Строка 178:


==== Метод 3 ====
==== Метод 3 ====
{| class="wikitable" align="center"
Усложненный вариант, который заключается в следующем: полученный первичный шифротекст (*) шифруется вторично. При этом он выписывается без [[разбиение|разбиения]] на пары:
! || 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
3425453443314154
Полученная последовательность цифр сдвигается [[цикл]]ически влево на один шаг(нечетное количество шагов):
Полученная последовательность цифр [[Циклический сдвиг|сдвигается циклически]] влево на один шаг (нечётное количество шагов, т.е. цифра 3 перемещается в конец):
4254534433141543
4254534433141543
Эта последовательность вновь разбивается в [[группа|группы]] по два:
Эта последовательность вновь разбивается в группы по два:
42 54 53 44 33 14 15 43
42 54 53 44 33 14 15 43


Строка 157: Строка 204:
|+ Таблица координат
|+ Таблица координат
|- class="bright"
|- class="bright"
! colspan = «4» | Координата горизонтальная: || 4 || 5 || 5 || 4 || 3 || 1 || 1 || 4
! colspan = «4» | Координата вертикальная: || 4 || 5 || 5 || 4 || 3 || 1 || 1 || 4
|- class="bright"
|- class="bright"
! colspan = «4» | Координата вертикальная: || 2 || 4 || 3 || 4 || 3 || 4 || 5 || 3
! colspan = «4» | Координата горизонтальная: || 2 || 4 || 3 || 4 || 3 || 4 || 5 || 3
|- class="highlight"
|- class="highlight"
! colspan = «4» | Буква: || I || U || P || T || N || Q || V || O
! colspan = «4» | Буква: || I || U || P || T || N || Q || V || O
Строка 175: Строка 222:


== Добавление ключа<ref>Баричев С. Г. Основы современной криптографии. М.: Горячая Линия — Телеком, 2001. 152 стр.</ref> ==
== Добавление ключа<ref>Баричев С. Г. Основы современной криптографии. М.: Горячая Линия — Телеком, 2001. 152 стр.</ref> ==
На первый взгляд шифр кажется очень [[устойчивость|нестойким]], но для его реальной оценки следует учитывать два [[фактор]]а:
На первый взгляд шифр кажется очень [[Криптостойкость|нестойким]], но для его реальной оценки следует учитывать два [[фактор]]а:


# ''возможность заполнить квадрат Полибия буквами произвольно, а не только строго по алфавиту;''
# ''возможность заполнить квадрат Полибия буквами произвольно, а не только строго по алфавиту;''

# ''возможность периодически заменять квадраты.''
# ''возможность периодически заменять квадраты.''


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


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


: <math>N = 25*24*23*...*2*1 = 25!</math>
: <math>N = 25*24*23*...*2*1 = 25! \,(\approx 1,55\cdot 10^{25})</math>


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


=== Пример ===
=== Пример ===
Строка 215: Строка 261:
! colspan = «4» | Буква: || S || O || M || E || T || E || X || T
! colspan = «4» | Буква: || S || O || M || E || T || E || X || T
|- class="bright"
|- class="bright"
! colspan = «4» | Координата горизонтальная: || 4 || 1 || 4 || 3 || 5 || 3 || 3 || 5
! colspan = «4» | Координата вертикальная: || 4 || 1 || 4 || 3 || 5 || 3 || 3 || 5
|- class="bright"
|- class="bright"
! colspan = «4» | Координата вертикальная: || 4 || 4 || 3 || 2 || 1 || 2 || 5 || 1
! colspan = «4» | Координата горизонтальная: || 4 || 4 || 3 || 2 || 1 || 2 || 5 || 1
|}
|}


Строка 228: Строка 274:
|+ Таблица координат
|+ Таблица координат
|- class="bright"
|- class="bright"
! colspan = «4» | Координата горизонтальная: || 4 || 4 || 5 || 3 || 4 || 3 || 1 || 5
! colspan = «4» | Координата вертикальная: || 4 || 4 || 5 || 3 || 4 || 3 || 1 || 5
|- class="bright"
|- class="bright"
! colspan = «4» | Координата вертикальная: || 1 || 3 || 3 || 5 || 4 || 2 || 2 || 1
! colspan = «4» | Координата горизонтальная: || 1 || 3 || 3 || 5 || 4 || 2 || 2 || 1
|- class="highlight"
|- class="highlight"
! colspan = «4» | Буква: || F || M || N || X || S || E || B || T
! colspan = «4» | Буква: || F || M || N || X || S || E || B || T
Строка 247: Строка 293:
== Историческая справка<ref>Астрахан В. И., Гусев В. В., Павлов В. В., Чернявский Б. Г. Становление и развитие правительственной связи в России, Орел: ВИПС, 1996.</ref> ==
== Историческая справка<ref>Астрахан В. И., Гусев В. В., Павлов В. В., Чернявский Б. Г. Становление и развитие правительственной связи в России, Орел: ВИПС, 1996.</ref> ==


Ещё в далекой древности у человека возникла необходимость передачи [[сигнал]]ов на расстояние. Для усиления голоса при подаче сигналов на охоте стали применять простейшие [[рупор]]ы в виде рогов, раковин и др. Целями подачи служили тамтамы, барабаны и подобные им устройства, а чуть позже световые средства — [[факел]]ы, костры. Даже эти примитивные предметы световой сигнализации позволили резко увеличить расстояние, на котором людям удавалось поддерживать [[связь]].<ref>Дильс Г. Античная техника. Под ред. С. И. Ковалева. М. — Л., Гостехиздат, 1934</ref>
Ещё в далекой древности у человека возникла необходимость передачи [[сигнал]]ов на расстояние. Для усиления голоса при подаче сигналов на охоте стали применять простейшие [[рупор]]ы в виде рогов, раковин и др. Целями подачи служили тамтамы, барабаны и подобные им устройства, а чуть позже световые средства — [[факел]]ы, костры. Даже эти примитивные предметы световой сигнализации позволили резко увеличить расстояние, на котором людям удавалось поддерживать [[Передача информации|связь]].<ref>Дильс Г. Античная техника. Под ред. С. И. Ковалева. М. — Л., Гостехиздат, 1934</ref>


С развитием общества возникла необходимость в передаче более разнообразных сигналов, в том числе сигналов, смысл которых не был обусловлен заранее. В [[Всеобщая история (Полибий)|книге Полибия]] описан способ<ref>Полибий. [[Всеобщая история в сорока книгах]]. Пер. с греч. Ф. Г. Мищенко. Т . 2, М ., 1895, с . 282—284.</ref> применения водяных часов, так называемых клепсидр, в устройстве для дальней сигнализации. Клепсидры представляли собой [[Сосуд (ёмкость)|сосуды]] с водой, на поверхности которой находились поплавки с вертикальными стойками на них. Вода из сосудов вытекала с постоянной [[скорость]]ю, и длина видимой части стоек была обратно пропорциональна времени. Суть использования клепсидр для сигнализации состояла в том, что их вертикальные стойки имели однотипную разметку: вместо часовых делений на них были написаны в одинаковой последовательности различные слова, команды и т. п. По условному сигналу с передающего [[пункт]]а обе клепсидры одновременно запускались, а по другому сигналу останавливались в тот момент, когда на стойках была видна надпись, которую нужно было передать. Так как клепсидры были довольно точными часами, то на передающем и на приемном пунктах они показывали один и тот же [[сигнал]]. В этом способе связи дальность определялась условиями видимости сигналов, которые могли подаваться любыми другими известными тогда сигнальными средствами.
С развитием общества возникла необходимость в передаче более разнообразных сигналов, в том числе сигналов, смысл которых не был обусловлен заранее. В [[Всеобщая история (Полибий)|книге Полибия]] описан способ<ref>Полибий. [[Всеобщая история в сорока книгах]]. Пер. с греч. Ф. Г. Мищенко. Т . 2, М ., 1895, с . 282—284.</ref> применения водяных часов, так называемых клепсидр, в устройстве для дальней сигнализации. Клепсидры представляли собой сосуды с водой, на поверхности которой находились поплавки с вертикальными стойками на них. Вода из сосудов вытекала с постоянной [[скорость]]ю, и длина видимой части стоек была обратно пропорциональна времени. Суть использования клепсидр для сигнализации состояла в том, что их вертикальные стойки имели однотипную разметку: вместо часовых делений на них были написаны в одинаковой последовательности различные слова, команды и т. п. По условному сигналу с передающего [[пункт]]а обе клепсидры одновременно запускались, а по другому сигналу останавливались в тот момент, когда на стойках была видна надпись, которую нужно было передать. Так как клепсидры были довольно точными часами, то на передающем и на приемном пунктах они показывали один и тот же [[сигнал]]. В этом способе связи дальность определялась условиями видимости сигналов, которые могли подаваться любыми другими известными тогда сигнальными средствами.


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


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


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


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


== Примечания ==
== Примечания ==
Строка 271: Строка 317:
== Ссылки ==
== Ссылки ==
* [http://fundux.ru/project/download/1538_fundux_ru.swf Флеш-приложение «Тюремная азбука»].
* [http://fundux.ru/project/download/1538_fundux_ru.swf Флеш-приложение «Тюремная азбука»].
* [http://www.hrono.ru/libris/lib_s/shifr01.html Шифры Древности].
* [http://www.hrono.ru/libris/lib_s/shifr01.html Шифры Древности] {{Wayback|url=http://www.hrono.ru/libris/lib_s/shifr01.html |date=20121013172610 }}.
* [http://hacktheplanet.ru/item/16 Появление шифров].
* [http://hacktheplanet.ru/item/16 Появление шифров] {{Wayback|url=http://hacktheplanet.ru/item/16 |date=20120728041317 }}.
* [http://files.school-collection.edu.ru/dlrstore/ce78903f-c622-4239-a5e6-97da5a0854ff/tema2.pdf Шифрование. Шифры замены].
* [http://files.school-collection.edu.ru/dlrstore/ce78903f-c622-4239-a5e6-97da5a0854ff/tema2.pdf Шифрование. Шифры замены] {{Wayback|url=http://files.school-collection.edu.ru/dlrstore/ce78903f-c622-4239-a5e6-97da5a0854ff/tema2.pdf |date=20160508112946 }}.
* [http://easyciphers.com Легкие шифры, Квадрат Полибия, основные методики].
* [http://easyciphers.com Легкие шифры, Квадрат Полибия, основные методики] {{Wayback|url=http://easyciphers.com/ |date=20190416230636 }}.


{{Письменности}}
{{rq|sources|image}}
{{Нет иллюстрации}}
{{нет ссылок|дата=20 июня 2018}}


[[Категория:Шифры]]
[[Категория:Шифры]]

Текущая версия от 13:11, 7 августа 2024

В криптографии квадрат Полибия (англ. 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.