Сохраняют ли аффинные шифры частоту

/ / Опубликовано в Информационная безопасность, Основы классической криптографии EITC/IS/CCF, История криптографии, Модульные арифметические и исторические шифры

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

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

    \[ E(x) = (ax + b) \mod m \]

где:
– Бывший) это функция шифрования.
– x является числовым эквивалентом буквы открытого текста.
– a и b являются ключами шифра, причем a являющийся мультипликативным ключом и b являющийся аддитивным ключом.
– m размер алфавита (для английского алфавита м = 26).

Функция дешифрования, наоборот, определяется выражением:

    \[ D(y) = a^{-1}(y - b) \mod m \]

в котором y является числовым эквивалентом буквы зашифрованного текста и а^{-1} является модульным мультипликативным обратным числом a форма m.

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

Например, если буква «Е» является наиболее часто встречающейся буквой в данном открытом тексте (как это обычно бывает в английском тексте) и она зашифрована до буквы «К» с использованием аффинного шифра, то «К» будет буквой «К». Самая частая буква в зашифрованном тексте. Таким образом, частотное распределение букв сохраняется, поскольку отображение является взаимно однозначным и последовательным по всему тексту.

Чтобы проиллюстрировать это на конкретном примере, рассмотрим аффинный шифр с a = 5 и б = 8 для английского алфавита. Функция шифрования будет:

    \[ E(x) = (5x + 8) \mod 26 \]

Шифрование открытого текстового сообщения «HELLO» (с Н = 7, Е = 4, Л = 11, О = 14):

– H \rightarrow (5 \cdot 7 + 8) \mod 26 = (35 + 8) \mod 26 = 43 \mod 26 = 17 \rightarrow R
– E \rightarrow (5 \cdot 4 + 8) \mod 26 = (20 + 8) \mod 26 = 28 \mod 26 = 2 \rightarrow C
– L \rightarrow (5 \cdot 11 + 8) \mod 26 = (55 + 8) \mod 26 = 63 \mod 26 = 11 \rightarrow L
– L \rightarrow (5 \cdot 11 + 8) \mod 26 = (55 + 8) \mod 26 = 63 \mod 26 = 11 \rightarrow L
– O \rightarrow (5 \cdot 14 + 8) \mod 26 = (70 + 8) \mod 26 = 78 \mod 26 = 0 \rightarrow A

Таким образом, «HELLO» зашифровывается в «RCLLA». Если «L» является наиболее часто встречающейся буквой в открытом тексте, она остается наиболее часто встречающейся буквой в зашифрованном тексте.

Однако, хотя аффинные шифры сохраняют частоту отдельных букв, они не сохраняют частоту орграфов (пар букв) или более крупных n-грамм. Это ограничение делает их уязвимыми для атак частотного анализа — распространенного метода, используемого в криптоанализе. Частотный анализ использует тот факт, что определенные буквы и комбинации букв появляются в данном языке с предсказуемой частотой. Например, в английском языке чаще всего встречается буква «Е», за ней следуют «Т», «А», «О», «Я», «Н» и т. д.

Чтобы взломать аффинный шифр с помощью частотного анализа, криптоаналитик должен проанализировать распределение частот зашифрованного текста и сравнить его с известным распределением частот языка открытого текста. Определив наиболее распространенные буквы в зашифрованном тексте и выдвинув гипотезу об их эквивалентах в открытом тексте, криптоаналитик может получить ключи. a и b.

Например, если «R» — наиболее часто встречающаяся буква в зашифрованном тексте, а «E» — наиболее часто встречающаяся буква в типичном английском тексте, криптоаналитик может предположить, что «R» соответствует «E». Используя эту гипотезу, криптоаналитик может создать систему линейных сравнений для решения a и b:

    \[ 5x + 8 \equiv y \mod 26 \]

в котором x и y являются числовыми эквивалентами «E» и «R» соответственно. Решение этой системы позволит раскрыть ключи и позволит расшифровать все сообщение.

Хотя аффинные шифры сохраняют частоту отдельных букв, что делает их уязвимыми для атак частотного анализа, они не сохраняют частоту пар букв или более крупных n-грамм. Это свойство ограничивает их безопасность и эффективность, особенно в контексте современных криптографических стандартов. Тем не менее, понимание принципов аффинных шифров дает ценную информацию об эволюции криптографических методов и важности надежных методов шифрования.

Другие недавние вопросы и ответы, касающиеся Основы классической криптографии EITC/IS/CCF:

Дополнительные вопросы и ответы см. в разделе Основы классической криптографии EITC/IS/CCF.

Еще вопросы и ответы:

Теги: , , , , ,