Архив задач олимпиады по математике и криптографии
Фраза на латыни
Зашифрование фразы на латинском языке осуществлено в два этапа. На первом этапе каждая буква текста заменяется на следующую в алфавитном порядке (последняя Z заменяется на первую A). На втором этапе применяется шифр простой замены с неизвестным ключом. Его применение заключается в замене каждой буквы шифруемого текста буквой того же алфавита, при этом разные буквы заменяются разными буквами. Ключом такого шифра является таблица, в которой указано, какой буквой надо заменить каждую букву алфавита.
По данному шифртексту
OSZJX FXRE YOQJSZ RAYFJ
восстановите открытое сообщение, если известно, что для использованного (неизвестного) ключа результат шифрования не зависит от порядка выполнения указанных этапов для любого открытого сообщения. Пробелы в тексте разделяют слова.
Занумеруем буквы латинского алфавита последовательно числами от 1 до 24. Пусть x - некоторое число от 1 до 24, а f(x) - число, в которое переходит x на втором этапе. Тогда перестановочность этапов можно записать в следующем виде:
f(x+1) = f(x) + 1, т. е. f(x+1) - f(x) = 1.
Это означает, что соседние числа x и x+1 на втором этапе переходят в соседние же числа f(x) и f(x+1), т. е. второй этап - тоже сдвиг. Последовательное применение двух сдвигов - очевидно тоже сдвиг и остается рассмотреть 24 варианта различных сдвигов. Читаемый текст определяется однозначно. Осложнения, связанные с переходом Z в A, устраняются либо переходом к остаткам при делении на 24, либо выписыванием после буквы Z второй раз алфавита AB... Z.