Шифр четырёх квадратов
Шифр четырёх квадратов — метод ручного симметрического шифрования, который представляет собой модифицированный вариант шифра Плейфера. Этот метод обеспечивает более высокий уровень безопасности защищённых данных. Шифр был изобретён известным французским криптографом Феликсом Деластелем[англ.] в 1902 году[1].
Данный метод шифрует пары букв и, тем самым, попадает в категорию шифров, известных как полиграфические подстановочные шифры[англ.]. Это добавляет значительную прочность шифрованию по сравнению с шифрами простой замены, которые действуют на отдельные символы[2]. Использование биграмм делает шифр четырёх квадратов менее восприимчивым к частотному криптоанализу, так как он должен быть применен к 676 возможным парам букв (в английском алфавите), а не только к 26 символам для монографического замещения[3]. Частотный анализ для биграмм возможен, но он гораздо сложнее, и для того, чтобы этот анализ был полезен, требуется, как правило, намного больше шифротекста.
Описание[править | править код]
Шифр четырёх квадратов использует 4 квадратных матрицы, размером зависящих от количества букв в алфавите, например, 5х5 в английском языке, 6х6 в русском.
| 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 |
| А | Б | В | Г | Д | Е |
| Ё | Ж | З | И | Й | К |
| Л | М | Н | О | П | Р |
| С | Т | У | Ф | Х | Ц |
| Ч | Ш | Щ | Ъ | Ы | Ь |
| Э | Ю | Я | - | - | - |
Две из них заполняются алфавитом в стандартном порядке (обычно буква «Q» опускаются, чтобы уменьшить алфавит, либо «I» и «J» объединяются в одной клетке). В две оставшиеся таблицы помещаются ключевые слова в верхней строке слева направо. Потом в оставшиеся ячейки матрицы записываются по порядку символы алфавита, не встречающиеся в ключевом слове. Ключевые слова, дополненные алфавитом, составляют матрицы 5х5 и являются ключом шифра.[источник не указан 2221 день]
| A | B | C | D | E | C | R | I/J | P | T | |
| F | G | H | I/J | K | O | G | A | F | B | |
| L | M | N | O | P | D | E | H | K | L | |
| Q | R | S | T | U | M | N | Q | S | U | |
| V | W | X | Y | Z | V | W | X | Y | Z | |
| S | E | G | U | R | A | B | C | D | E | |
| T | A | B | C | D | F | G | H | I/J | K | |
| F | H | I/J | K | L | L | M | N | O | P | |
| M | N | O | P | Q | Q | R | S | T | U | |
| V | W | X | Y | Z | V | W | X | Y | Z |
Алгоритм[править | править код]
Для шифрования необходимо выполнить следующие пункты:
- Разделить сообщение на биграммы.
ATTACK AT DAWN = AT TA CK AT DA WN
- По очереди найти их в левом верхнем и правом нижнем квадрате. Например, AT.
| A | B | C | D | E | C | R | I/J | P | T | |
| F | G | H | I/J | K | O | G | A | F | B | |
| L | M | N | O | P | D | E | H | K | L | |
| Q | R | S | T | U | M | N | Q | S | U | |
| V | W | X | Y | Z | V | W | X | Y | Z | |
| S | E | G | U | R | A | B | C | D | E | |
| T | A | B | C | D | F | G | H | I/J | K | |
| F | H | I/J | K | L | L | M | N | O | P | |
| M | N | O | P | Q | Q | R | S | T | U | |
| V | W | X | Y | Z | V | W | X | Y | Z |
- Комплементарно найденным буквам выбрать другие 2 буквы из правого верхнего и левого нижнего квадратов — PM. При этом все четыре буквы будут находиться в вершинах полученного прямоугольника. Полученную пару букв помещают в шифр слева направо.
| A | B | C | D | E | C | R | I/J | P | T | |
| F | G | H | I/J | K | O | G | A | F | B | |
| L | M | N | O | P | D | E | H | K | L | |
| Q | R | S | T | U | M | N | Q | S | U | |
| V | W | X | Y | Z | V | W | X | Y | Z | |
| S | E | G | U | R | A | B | C | D | E | |
| T | A | B | C | D | F | G | H | I/J | K | |
| F | H | I/J | K | L | L | M | N | O | P | |
| M | N | O | P | Q | Q | R | S | T | U | |
| V | W | X | Y | Z | V | W | X | Y | Z |
- Повторить для всех пар букв, содержащихся в сообщении.
- В итоге получается зашифрованное сообщение:
PM MU TB PM CU XH = PMMUTBPMCUXH
Для расшифровки сообщения нужно проделать те же действия, выбирая буквы на квадратах с кодовыми словами.
Реализация[править | править код]
Ниже показан пример функции на JavaScript, которая выполняет шифрование сообщения и возвращает результат[4].
function encrypt(messageInput, keyword, alphabet) {
var messageOutput = "";
var pos = 0;
while (pos < messageInput.length) {
var m1 = messageInput[pos];
var m2 = '';
if (pos + 1 < messageInput.length) {
m2 = messageInput[pos + 1];
pos += 2;
} else {
m2 = 'Q'
pos += 1;
}
var idx1 = alphabet.indexOf(m1);
var idx2 = alphabet.indexOf(m2);
var c1 = keyword[0][(5 * Math.floor(idx1 / 5)) + idx2 % 5];
var c2 = keyword[1][(5 * Math.floor(idx2 / 5)) + idx1 % 5];
messageOutput = messageOutput.concat(c1);
messageOutput = messageOutput.concat(c2);
}
return messageOutput;
}
В истории[править | править код]
Во время Второй мировой войны шифр четырёх квадратов использовался немецкими вооруженными силами. Тогда текст немного изменялся, прежде чем быть зашифрованным: например, сообщение MORE TROOPS NEEDED HERE разбивалось таким образом:
MORET NEEDE ROOPS DHERE
и биграммы, которые подвергались шифровке, были:
MR OO RO EP TS ND EH EE DR EE
Согласно книге Codebreakers[5], сборнику воспоминаний тех, кто работал в Блетчли-парке во время войны, немецкая армия использовала шифр, в котором биграммы шифровались с помощью шифра четырёх квадратов.
Джим Джиллогли[англ.] отметил, что рассекреченные документы NSA относятся также к шифру этого типа, в котором биграммы были зашифрованы дважды посредством шифра с четырьмя квадратами. Так как каждая буква была зашифрована в первый раз, а затем помещалась в квадрат с другой стороны для второй шифровки, отношение между открытым текстом и шифром было намного сложнее, чем в шифре Плейфера[6].
Безопасность[править | править код]
Шифр четырёх квадратов может быть легко взломан. Довольно просто определить ключ, если известны и открытый текст, и шифротекст, и по этой причине угадывание части открытого текста является очень эффективным способом взлома этого шифра. Если часть открытого текста известна или легко угадываема, это должно быть использовано в первую очередь, чтобы определить как можно большую часть ключа, а затем могут быть применены и другие методы[7].
По сравнению с шифром Плейфера, шифр четырёх квадратов является более надёжным в случае симметричных биграмм (например, AB BA будет зашифровано как XY YX в шифре Плейфера, но не в шифре четырёх квадратов). Это верно только в том случае, если два ключевых слова разные[7].
Шифр четырёх квадратов является более сильным, чем шифр Плейфера, но более громоздким из-за использования двух ключей, и процессы шифрования и дешифрования сообщения могут занять много времени. Принимая во внимание, что увеличение прочности шифрования, обеспечиваемое шифром четырёх квадратов, является незначительным, и что оба метода легко взломать, если достаточное количество шифротекста известно, шифр Плейфера был гораздо более распространён[8].
Примечания[править | править код]
- ↑ Félix Delastelle. Traité élémentaire de cryptographie. — Gauthier-Villars, 1902-01-01.
- ↑ Administrator. CrypTool-Online / Ciphers / Four-Square. www.cryptool-online.org. Дата обращения: 2 декабря 2016. Архивировано 2 декабря 2016 года.
- ↑ Four-Square Cipher. Crypto Corner. Дата обращения: 2 декабря 2016. Архивировано 20 ноября 2016 года.
- ↑ Four-Square Cipher | Polygraphic Substitution | Crypto-IT. www.crypto-it.net. Дата обращения: 28 ноября 2016. Архивировано 29 ноября 2016 года.
- ↑ Kahn D. The Codebreakers: The Comprehensive History of Secret Communication from Ancient Times to the Internet (Abridged Version). — 1967.
- ↑ A Cryptographic Compendium. www.quadibloc.com. Дата обращения: 2 декабря 2016. Архивировано 9 ноября 2020 года.
- ↑ 1 2 Practical Cryptography. practicalcryptography.com. Дата обращения: 2 декабря 2016. Архивировано 21 ноября 2016 года.
- ↑ four square cipher. Дата обращения: 28 ноября 2016. Архивировано 21 ноября 2016 года.
Литература[править | править код]
- F. Delastelle. Traité élémentaire de cryptographie.
- Analysis of Four-Square and Two-Square Ciphers // Basic Cryptanalysis. — Fort Devens[англ.]: U.S. Army Intelligence School, Department of the Army, 1990. — Vol. 34-40-2. — P. 7-0—7-12. — (Field Manual[англ.]).