Аффинный шифр

Аффинный шифр — это тип одноалфавитного шифра замены , в котором каждая буква алфавита сопоставляется со своим числовым эквивалентом, шифруется с помощью простой математической функции и преобразуется обратно в букву. Используемая формула означает, что каждая буква зашифровывается в одну другую букву и обратно, что означает, что шифр, по сути, представляет собой стандартный шифр замены с правилом, определяющим, какая буква к какой переходит. По существу, он имеет недостатки всех шифров замены. Каждая буква шифруется функцией $(ax + b) mod 26$ , где $b$ — величина сдвига.

Описание

Здесь буквы алфавита размера $m$ сначала сопоставляются с целыми числами в диапазоне $0 ... m - 1$ . Затем он использует модульную арифметику для преобразования целого числа, которому соответствует каждая буква открытого текста, в другое целое число, соответствующее букве зашифрованного текста. Функция шифрования для одной буквы

E(x)=(ax+b){\bmod {m}}

где модуль $m$ — размер алфавита, $а a$ и $b$ — ключи шифра. Значение $a$ должно быть выбрано таким, чтобы $a$ и $m$ были взаимно простыми . Функция дешифрования

D(x)=a^{-1}(x-b){\bmod {m}}

где $ -1$ является мультипликативным модулем $обратным$ m $.$ модульным Т.е. оно удовлетворяет уравнению

1=a^{-1}{\bmod {m}}

Мультипликативный обратный $a$ существует только в том случае, если $a$ и $m$ взаимно просты. Следовательно, без ограничения на $расшифровка$ может быть невозможна. Можно показать следующим образом, что функция дешифрования является обратной функцией шифрования:

{\begin{aligned}D(E(x))&=a^{-1}(E(x)-b){\bmod {m}}\\&=a^{-1}(((ax+b){\bmod {m}})-b){\bmod {m}}\\&=a^{-1}(ax+b-b){\bmod {m}}\\&=a^{-1}ax{\bmod {m}}\\&=x{\bmod {m}}\end{aligned}}

Слабые стороны

Поскольку аффинный шифр по-прежнему является одноалфавитным шифром замены, он наследует недостатки этого класса шифров. Шифр Цезаря является аффинным шифром с $a = 1$ , поскольку функция шифрования просто сводится к линейному сдвигу. Шифр Атбаша использует $a = -1$ .

Учитывая конкретный случай шифрования сообщений на английском языке (т.е. $m = 26$ ), всего существует 286 нетривиальных аффинных шифров, не считая 26 тривиальных шифров Цезаря. Это число связано с тем, что существует 12 чисел, взаимно простых с 26, меньшими 26 (это возможные значения $a$ ). Каждое значение $a$ может иметь 26 различных дополнительных сдвигов ( $значение b$ ); следовательно, возможных ключей 12 × 26 или 312. Отсутствие разнообразия делает систему крайне небезопасной, если рассматривать ее в свете принципа Керкхоффса .

Основная слабость шифра связана с тем, что если криптоаналитик может обнаружить (посредством частотного анализа , грубой силы , угадывания или иным образом) открытый текст двух символов зашифрованного текста, то ключ можно получить путем решения одновременного уравнения . Поскольку мы знаем, $что a$ и $m$ относительно простые, это можно использовать для быстрого исключения многих «ложных» ключей в автоматизированной системе.

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

Пример

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

А	Б	С	Д	И	Ф	Г	ЧАС	я	Дж	К	л	М	Н	ТО	П	вопрос	Р	С	Т	В	V	В	Х	И	С
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25

Шифрование

В этом примере шифрования ^[1] открытый текст, который нужно зашифровать, - это «АФФИННЫЙ ШИФР», используя упомянутую выше таблицу числовых значений каждой буквы, принимая $a$ за 5, $b$ за 8 и $m$ за 26, поскольку в используемом алфавите 26 символов. Только значение $a$ имеет ограничение, поскольку оно должно быть взаимно простым с 26. Возможные значения $a$ : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25. Значение $b$ может быть произвольным, пока $a$ не равно 1, поскольку это сдвиг шифра. Таким образом, функция шифрования для этого примера будет $y = E (x) = (5 x + 8) mod 26$ . Первым шагом в шифровании сообщения является запись числовых значений каждой буквы.

открытый текст	А	Ф	Ф	я	Н	И	С	я	П	ЧАС	И	Р
$х$	0	5	5	8	13	4	2	8	15	7	4	17

Теперь возьмите каждое значение $x$ и решите первую часть уравнения $(5 x + 8)$ . Найдя значение $(5 x + 8)$ для каждого символа, возьмите остаток от деления результата $(5 x + 8)$ на 26. В следующей таблице показаны первые четыре шага процесса шифрования.

открытый текст	А	Ф	Ф	я	Н	И	С	я	П	ЧАС	И	Р
$х$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 х + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 х + 8) мод 26$	8	7	7	22	21	2	18	22	5	17	2	15

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

открытый текст	А	Ф	Ф	я	Н	И	С	я	П	ЧАС	И	Р
$х$	0	5	5	8	13	4	2	8	15	7	4	17
$(5 х + 8)$	8	33	33	48	73	28	18	48	83	43	28	93
$(5 х + 8) мод 26$	8	7	7	22	21	2	18	22	5	17	2	15
зашифрованный текст	я	ЧАС	ЧАС	В	V	С	С	В	Ф	Р	С	П

Расшифровка

В этом примере расшифровки зашифрованный текст, который будет расшифрован, представляет собой зашифрованный текст из примера шифрования. Соответствующая функция дешифрования равна $D (y) = 21(y - b) mod 26$ , где $a -1$ рассчитывается как 21, а $b$ равно 8. Для начала запишите числовые эквиваленты каждой буквы зашифрованного текста, как показано в таблице ниже.

зашифрованный текст	я	ЧАС	ЧАС	В	V	С	С	В	Ф	Р	С	П
$и$	8	7	7	22	21	2	18	22	5	17	2	15

Теперь следующий шаг — вычислить $21(y - 8)$ и затем взять остаток от деления этого результата на 26. В следующей таблице показаны результаты обоих вычислений.

зашифрованный текст	я	ЧАС	ЧАС	В	V	С	С	В	Ф	Р	С	П
$и$	8	7	7	22	21	2	18	22	5	17	2	15
$21(у - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(у - 8) по модулю 26$	0	5	5	8	13	4	2	8	15	7	4	17

Последний шаг в расшифровке зашифрованного текста — использование таблицы для преобразования числовых значений обратно в буквы. Открытый текст в этой расшифровке — AFFINECIPHER. Ниже приведена таблица с завершенным последним шагом.

зашифрованный текст	я	ЧАС	ЧАС	В	V	С	С	В	Ф	Р	С	П
$и$	8	7	7	22	21	2	18	22	5	17	2	15
$21(у - 8)$	0	−21	−21	294	273	−126	210	294	−63	189	−126	147
$21(у - 8) по модулю 26$	0	5	5	8	13	4	2	8	15	7	4	17
открытый текст	А	Ф	Ф	я	Н	И	С	я	П	ЧАС	И	Р

Весь алфавит закодирован

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

письмо открытым текстом	А	Б	С	Д	И	Ф	Г	ЧАС	я	Дж	К	л	М	Н	ТО	П	вопрос	Р	С	Т	В	V	В	Х	И	С
номер в открытом тексте	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25
$(5 х + 8) мод 26$	8	13	18	23	2	7	12	17	22	1	6	11	16	21	0	5	10	15	20	25	4	9	14	19	24	3
зашифрованное письмо	я	Н	С	Х	С	ЧАС	М	Р	В	Б	Г	л	вопрос	V	А	Ф	К	П	В	С	И	Дж	ТО	Т	И	Д

Примеры программирования

Следующий код Python можно использовать для шифрования текста с помощью аффинного шифра:

# Prints a transposition table for an affine cipher.
def affine(a: int, b: int, s: str):
    import string

    D = dict(enumerate(string.ascii_lowercase, start=0))
    E = {v: k for k,v in D.items()}
    size = len(string.ascii_lowercase)
    ret = ""
    print(size)
    for c in s:
        N = E[c]
        val = a * N + b
        val = val % size
        print(f"{c}({N}) -> {D[val]}({val})")
        ret += D[val]
    return ret

affine(7, 3, 'foobar')

См. также

Ссылки

^ Коздрон, Михаил. «Аффинные шифры» (PDF) . Проверено 22 апреля 2014 г.

[1] Коздрон, Михаил. «Аффинные шифры» (PDF) . Проверено 22 апреля 2014 г.

[1]