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

аффинный шифр цезаря, аффинный шифр виженера
Аффинный шифр — это частный случай более общего моноалфавитного шифра подстановки К шифрам подстановки относятся также шифр Цезаря, ROT13 и Атбаш Поскольку аффинный шифр легко дешифровать, он обладает слабыми криптографическими свойствами[1]

Содержание

  • 1 Описание
  • 2 Примеры шифрования и расшифрования
    • 21 Шифрование
    • 22 Расшифрование
    • 23 Шифрование всего алфавита
  • 3 Криптоанализ
  • 4 Примечания

Описание

В аффинном шифре каждой букве алфавита размера m ставится в соответствие число из диапазона 0 m − 1 Затем при помощи модульной арифметики для каждого числа, соответствующего букве исходного алфавита, вычисляется новое число, которое заменит старое в шифротексте Функция шифрования[2] для каждой буквы

E x = a x + b mod m , }x=ax+b\mod ,}

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

D x = a − 1 x − b mod m , }x=a^x-b\mod ,}

где a − 1 } — обратное к a число по модулю m То есть оно удовлетворяет уравнению[2]

1 = a a − 1 mod m \mod }

Обратное к a число существует только в том случае, когда a и m — взаимно простые Значит, при отсутствии ограничений на выбор числа a расшифрование может оказаться невозможным Покажем, что функция расшифрования является обратной к функции шифрования

D E x = a − 1 E x − b mod m = a − 1 a x + b mod m − b mod m = a − 1 a x + b − b mod m = a − 1 a x mod m = x mod m }}x&=&a^}x-b\mod \\&=&a^ax+b\mod -b\mod \\&=&a^ax+b-b\mod \\&=&a^ax\mod \\&=&x\mod \end}}

Количество возможных ключей для аффинного шифра можно записать через функцию Эйлера как φ m m [1]

Примеры шифрования и расшифрования

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

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
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

Шифрование

В этом примере необходимо зашифровать сообщение "ATTACK AT DAWN", используя упомянутое выше соответствие между буквами и числами, и значения a = 3 , b = 4 и m = 26 , так как в используемом алфавите 26 букв Только на число a наложены ограничения, так как оно должно быть взаимно простым с 26 Возможные значения a : 1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23 и 25[3] Значение b может быть любым, только если a не равно единице, так как это сдвиг шифра Итак, для нашего примера функция шифрования y = E x = 3 x + 4 mod 26 }} Первый шаг шифрования — запись чисел, соответствующих каждой букве сообщения

сообщение A T T А C K A T D A W N
x 0 19 19 0 2 10 0 19 3 0 22 13

Теперь, для каждого значения x найдем значение 3 x + 4 После нахождения значения 3 x + 4 для каждого символа возьмем остаток от деления 3 x + 4 на 26 Следующая таблица показывает первые четыре шага процесса шифрования

сообщение A T T А C K A T D A W N
x 0 19 19 0 2 10 0 19 3 0 22 13
3 x + 4 4 61 61 4 10 34 4 61 13 4 70 43
3 x + 4 mod 26 }} 4 9 9 4 10 8 4 9 13 4 18 17

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

сообщение A T T А C K A T D A W N
x 0 19 19 0 2 10 0 19 3 0 22 13
3 x + 4 4 61 61 4 10 34 4 61 13 4 70 43
3 x + 4 mod 26 }} 4 9 9 4 10 8 4 9 13 4 18 17
шифротекст E J J E K I E J N E S R

Расшифрование

Для расшифрования возьмем шифротекст из примера с шифрованием Функция расшифрования будет D y = a − 1 y + m − b  mod  m }y=a^y+m-b}m} , где a − 1 = 9 =9} , b = 4 и m = 26

Замечание: если каждая y ⩾ b , то функция расшифрования принимает вид D y = a − 1 y − b  mod  m }y=a^y-b}m} Точно так же, как и в обозреваемом примере, но разберём общий вариант

Для начала запишем численные значения для каждой буквы шифротекста, как показано в таблице ниже

шифротекст E J J E K I E J N E S R
y 4 9 9 4 10 8 4 9 13 4 18 17

Теперь для каждого y необходимо рассчитать 9 y + m − 4 и взять остаток от деления этого числа на 26 Следующая таблица показывает результат этих вычислений

шифротекст E J J E K I E J N E S R
y 4 9 9 4 10 8 4 9 13 4 18 17
9 y + 26 − 4 234 279 279 234 288 270 234 279 315 234 360 351
9 y + 26 − 4 mod 26 }} 0 19 19 0 2 10 0 19 3 0 22 13

Последний шаг операции расшифрования для шифротекста — поставить в соответствие числам буквы Сообщение после расшифрования будет "ATTACKATDAWN" Таблица ниже показывает выполнение последнего шага

шифротекст E J J E K I E J N E S R
y 4 9 9 4 10 8 4 9 13 4 18 17
9 y + 26 − 4 234 279 279 234 288 270 234 279 315 234 360 351
9 y + 26 − 4 mod 26 }} 0 19 19 0 2 10 0 19 3 0 22 13
сообщение A T T A C K A T D A W N

Шифрование всего алфавита

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

буква сообщения 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
x 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
3 x + 4 mod 26 }} 4 7 10 13 16 19 22 25 2 5 8 11 14 17 20 23 0 3 6 9 12 15 18 21 24 1
буква шифротекста E H K N Q T W Z C F I L O R U X A D G J M P S V Y B

Криптоанализ

Так как аффинный шифр является по сути моноалфавитным шифром замены, то он обладает всеми уязвимостями этого класса шифров Шифр Цезаря — это аффинный шифр с a = 1 , что сводит функцию шифрования к простому линейному сдвигу[1]

В случае шифрования сообщений на русском языке те m = 33 существует 297 нетривиальных аффинных шифров, не учитывая 33 тривиальных шифра Цезаря Это число легко посчитать, зная, что существует всего 20 чисел взаимно простых с 33 и меньших 33 а это и есть возможные значения a Каждому значению a могут соответствовать 33 разных дополнительных сдвига значение b ; то есть всего существует 2033 или 660 возможных ключей Аналогично, для сообщений на английском языке те m = 26 всего существует 1226 или 312 возможных ключей[3] Такое ограниченное количество ключей приводит к тому, что система крайне не криптостойка с точки зрения принципа Керкгоффса

Основная уязвимость шифра заключается в том, что криптоаналитик может выяснить путём частотного анализа[4], полного перебора[1], угадывания или каким-либо другим способом соответствие между двумя любыми буквами исходного текста и шифротекста Тогда ключ может быть найдет путём решения системы уравнений[4] Кроме того, так мы знаем, что a и m — взаимно простые, это позволяет уменьшить количество проверяемых ключей для полного перебора

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

Примечания

  1. 1 2 3 4 S R Nagpaul, Surender Kumar Jain Topics in applied abstract algebra — AMS — P 137-138
  2. 1 2 3 Johannes Buchmann Introduction to cryptography — Springer — P 95
  3. 1 2 David Salomon Coding for data and computer communications — Springer — P 204
  4. 1 2 Josef Pieprzyk, Thomas Hardjono, Jennifer Seberry Fundamentals of computer security — Springer, 2003 — P 72-74 — 677 p
  5. Алгоритмы: введение в разработку и анализ — Издательский дом Вильямс — С 130-131

аффинный шифр виженера, аффинный шифр мкх-10, аффинный шифр цезаря, аффинный шифрин


Аффинный шифр Информацию О

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


  • user icon

    Аффинный шифр beatiful post thanks!

    29.10.2014


Аффинный шифр
Аффинный шифр
Аффинный шифр Вы просматриваете субъект
Аффинный шифр что, Аффинный шифр кто, Аффинный шифр описание

There are excerpts from wikipedia on this article and video

Случайные Статьи

Громов, Евгений Иванович

Громов, Евгений Иванович

Евгений Иванович Громов (10 февраля 1909(19090210) — 21 ноября 1981, Москва) — советский п...
J

J

J: J — буква латиницы Ј — буква кириллицы j — обозначение палатального сонорного сог...
Пайдейя

Пайдейя

Пайдейя (др.-греч. παιδεία — воспитание детей; от παιδος — мальчик, подросток) — категория...
Каделл ап Грифид

Каделл ап Грифид

Ка́делл ап Гри́фид (валл. Cadell ap Gruffydd) (умер в 1175 году) — правитель королевства Дехейб...