Шифр «Четыре квадрата»: описание и криптоанализ

Введение

Шифр симметричного шифрования. Шифр «Четыре квадрата» — это ручная техника симметричного шифрования. Он был изобретён французским криптографом Феликсом Деластелем. Эта техника шифрует пары букв (диграфы) и, таким образом, относится к категории шифров, известных как полиграфические шифры подстановки. Это значительно повышает стойкость шифрования по сравнению с монографическими шифрами подстановки, которые оперируют с отдельными символами. Использование диграфов делает метод «Четыре квадрата» менее уязвимым к атакам частотного анализа, поскольку анализ необходимо проводить на 676 возможных диграфов, а не только на 26 при монографической подстановке. Частотный анализ диграфов возможен, но значительно сложнее и, как правило, требует гораздо большего объёма зашифрованного текста, чтобы быть эффективным.

Криптоанализ четырех квадратов

Как и большинство шифров досовременной эпохи, четырехквадратный шифр можно относительно легко взломать при наличии достаточного объема текста. Получение ключа достаточно прямолинейно, если известны и открытый текст, и шифротекст. Когда известен только шифротекст, криптоанализ методом полного перебора включает поиск в ключевом пространстве соответствий между частотой встречаемости диграмм (пар букв) и известной частотой встречаемости диграмм в предполагаемом языке исходного сообщения. Криптоанализ четырехквадратного шифра обычно включает поиск закономерностей в повторяющихся монограммах. Это справедливо только при известных двух матрицах открытого текста. При шифровании четырехквадратным шифром обычно используются стандартные алфавиты в этих матрицах, хотя это и не является обязательным условием. Если это так, то определенные слова всегда будут приводить к повторениям одинаковых букв в шифротексте. Например, слово MI LI TA RY всегда будет генерировать одну и ту же букву шифротекста в первой и третьей позициях, независимо от используемых ключевых слов. Такие закономерности можно каталогизировать и сопоставлять с повторяющимися буквами в шифротексте. Затем можно подставлять предполагаемый открытый текст, чтобы попытаться раскрыть матрицы шифрования. В отличие от шифра Плейфера, четырехквадратный шифр не будет показывать обратные диграфы шифротекста для обратных диграфов открытого текста (например, диграфы AB BA в шифре Плейфера будут зашифрованы в шаблон XY YX, но не в четырехквадратном шифре). Это, конечно, верно только в том случае, если два ключевых слова различны. Еще одно отличие между четырехквадратным шифром и шифром Плейфера, которое делает четырехквадратный шифр более надежным, заключается в том, что в шифротексте четырехквадратного шифра могут встречаться диграфы из повторяющихся букв. По всем параметрам четырехквадратный шифр является более надежной системой шифрования информации, чем шифр Плейфера. Однако он более громоздкий из-за использования двух ключей, а подготовка листа шифрования/дешифрования может занять много времени. Учитывая, что повышение стойкости шифрования, обеспечиваемое четырехквадратным шифром по сравнению с шифром Плейфера, незначительно, и что обе схемы легко взламываются при наличии достаточного количества шифротекста, шифр Плейфера стал гораздо более распространенным. Хорошее руководство по восстановлению ключа для четырехквадратного шифра можно найти в главе 7 "Решение полиграфических систем подстановки" Полевого руководства 34-40-2, изданного армией Соединенных Штатов.

Like most pre modern era ciphers, the four square cipher can be easily cracked if there is enough text. Obtaining the key is relatively straightforward if both plaintext and ciphertext are known. When only the ciphertext is known, brute force cryptanalysis of the cipher involves searching through the key space for matches between the frequency of occurrence of digrams (pairs of letters) and the known frequency of occurrence of digrams in the assumed language of the original message. Cryptanalysis of four square generally involves pattern matching on repeated monographs. This is only the case when the two plaintext matrices are known. A four square encipherment usually uses standard alphabets in these matrices but it is not a requirement. If this is the case, then certain words will always produce single letter ciphertext repeats. For instance, the word MI LI TA RY will always produce the same ciphertext letter in the first and third positions regardless of the keywords used. Patterns like these can be cataloged and matched against single letter repeats in the ciphertext. Candidate plaintext can then be inserted in an attempt to uncover the ciphertext matrices. Unlike the Playfair cipher, a four square cipher will not show reversed ciphertext digraphs for reversed plaintext digraphs (e. g. the digraphs AB BA would encrypt to some pattern XY YX in Playfair, but not in four square). This, of course, is only true if the two keywords are different. Another difference between four square and Playfair which makes four square a stronger encryption is the fact that double letter digraphs will occur in four square ciphertext. By all measures, four square is a stronger system for encrypting information than Playfair. However, it is more cumbersome because of its use of two keys, and, preparing the encryption/decryption sheet can be time consuming. Given that the increase in encryption strength afforded by four square over Playfair is marginal and that both schemes are easily defeated if sufficient ciphertext is available, Playfair has become much more common. A good tutorial on reconstructing the key for a four square cipher can be found in chapter 7, "Solution to Polygraphic Substitution Systems," of Field Manual 34 40 2, produced by the United States Army.