Mybrary.info
mybrary.info » Книги » Научно-образовательная » Математика » Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗

Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗

Тут можно читать бесплатно Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан (бесплатные книги онлайн без регистрации TXT) 📗. Жанр: Математика. Так же Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте mybrary.info (MYBRARY) или прочесть краткое содержание, предисловие (аннотацию), описание и ознакомиться с отзывами (комментариями) о произведении.
Перейти на страницу:

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

С(a,Ь)(x) =х + b) (mod n),

где а и b — два целых числа, меньших, чем число (n) букв в алфавите. Наибольший общий делитель (НОД) чисел а и n должен быть равен 1 [НОД (а, n) = 1], потому что иначе, как мы увидим позже, получится несколько возможностей для шифрования одной и той же буквы. Ключ шифра определяется парой (а, Ь). Шифр Цезаря с ключом 3 является, следовательно, аффинным шифром со значениями

а = 1 и b = 3.

Обобщенный аффинный шифр имеет более высокий уровень безопасности, чем обычный шифр Цезаря. Почему? Как мы видели, ключом аффинного шифра является пара чисел (а, b). Если сообщение написано с использованием алфавита из 26 букв и зашифровано с помощью аффинного шифра, то и а, и b могут принимать любые значения от 0 до 25. Таким образом, в этой системе шифрования с алфавитом из 26 букв возможное количество ключей составит 25 х 25 = 625. Заметим, что количество ключей для алфавита из n букв в n раз больше, чем в шифре Цезаря.

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

* * *

НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ (НОД)

Наибольший общий делитель двух чисел может быть найден с помощью алгоритма Евклида. Этот алгоритм заключается в делении одного числа на другое, а затем проведении последовательных делений предыдущего делителя на новый остаток. Процесс заканчивается, когда остаток равен 0. Делитель последней операции деления и будет наибольшим общим делителем данных чисел.

Например, найдем НОД (48,30).

Разделим 48 на 30, получим остаток 18 и частное 1.

Разделим 30 на 18, получим остаток 12 и частное 1.

Разделим 18 на 12, получим остаток 6 и частное 1.

Разделим 12 на 6, получим остаток 0 и частное 2.

Мы закончили алгоритм.

НОД (48,30) = 6.

Если НОД (а, n) = 1, мы говорим, что а и n взаимно просты.

Соотношение Везу, имеющее большое значение в криптографии, устанавливает следующий факт: для двух целых чисел а и n, больших нуля, существуют целые числа k и q, такие что НОД (а, n) =+ nq.

Игра в шпионов

При каких условиях сообщение, зашифрованное аффинным шифром, может расшифровать предполагаемый получатель или шпион? Мы ответим на этот вопрос, используя простой пример шифра для алфавита из шести букв:

Математики, шпионы и хакеры. Кодирование и криптография - _19.jpg

Текст будет зашифрован с помощью аффинного шифра C(x) = 2x + 1 (mod 6).

Буква А зашифрована по формуле С(0) = 2 х 0 + 1 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_27
1 (mod 6), что соответствует букве В.

Буква В зашифрована по формуле C(1) = 2 x 1 + 1 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_28
3 (mod 6), что соответствует букве D.

Буква С зашифрована по формуле С(2) = 2 х 2 + 1 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_29
5 (mod 6), что соответствует букве F.

Буква D зашифрована по формуле С(3) = 2 х З + 1 = 7 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_30
1 (mod 6), что соответствует букве В.

Буква Е зашифрована по формуле С(4) = 2 х 4 + 1 = 9 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_31
3 (mod 6), что соответствует букве D.

Буква F зашифрована по формуле С(5) = 2 х 5 + 1 = 11 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_32
5 (mod 6), что соответствует букве F.

Предлагаемый аффинный шифр преобразует сообщения АВС и DEF в одно и то же BDF, поэтому исходное сообщение теряется. Что же случилось?

Если мы работаем с шифром, выраженным формулой С(а, b)(х) =х + b) (mod n), мы можем расшифровать сообщение однозначно, только когда НОД (а, n) = 1. В нашем примере НОД (2, 6) = 2 и, следовательно, не удовлетворяет этому условию.

Математическая операция расшифровки эквивалентна нахождению неизвестного х при данном значении у по модулю n.

С(а, b)(х) = (ах + b) y (mod n)

(ах + b) = у (mod n)

ах у b (mod n)

Другими словами, нам нужно найти значение а-1 (обратное значению а), удовлетворяющее равенству а-1а = 1, так что

а-1ах = а-1х(у b)(mod n)

х = а-1 b)(mod n).

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

В случае аффинного шифра С(а, b)(х) = (ах + b) (mod n) обратное значение числа а будет существовать тогда и только тогда, когда НОД (а, n) = 1.

В случае аффинного шифра в нашем примере, С(х) =+ 1 (mod 6), мы хотим узнать, существует ли обратное значение для числа а, в нашем случае для числа 2.

То есть существует ли целое число n, которое меньше 6 и удовлетворяет выражению 2∙n = 1 (mod 6). Для ответа на этот вопрос мы подставим в данное выражение все возможные значения (0, 1, 2, 3, 4, 5):

2-0 = 0, 2–1 = 2, 2–2 = 4, 2–3 = 6 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_35
0, 2–4 = 8 
Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_34
2, 2–5 = 10 
Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_33
4.

Нет такого значения, следовательно, можно заключить, что 2 не имеет обратного числа. На самом деле мы это уже знали, так как НОД (2,6) 

Математики, шпионы и хакеры. Кодирование и криптография - n.jpg
1.

Предположим теперь, что мы перехватили зашифрованное сообщение: YSFMG. Мы знаем, что оно было зашифровано аффинным шифром вида С(х) = 2х + 3 и изначально было написано на испанском языке с алфавитом из 27 букв (включая букву N, идущую после обычной N).

Как получить исходное сообщение?

Сначала мы посчитаем НОД (2,27), который равен 1. Значит, сообщение можно расшифровать! Для этого для функции С(х) = 2х + 3 мы должны найти обратную функцию по модулю 27:

у = + 3

= у 3.

Чтобы найти x, мы должны умножить обе части уравнения на число, обратное 2.

Число, обратное числу 2 по модулю 27, — это целое число n такое, что 2n 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg
1 (mod 27), а именно 14. И действительно:

14∙2 = 28 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_0
1.

Итак, мы имеем

x = 14∙(у 3).

Теперь мы можем расшифровать сообщение YSFMG.

Буква Y стоит на позиции 25, ей соответствует расшифрованная буква, стоящая на позиции

14∙(25—3) = 308 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_1
11 (mod 27).

Буква, стоящая в алфавите на позиции 11, — это L.

Для буквы S имеем 14∙(19—3) = 224 

Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_2
8 (mod 27), эта позиция соответствует букве I.

Перейти на страницу:

Гомес Жуан читать все книги автора по порядку

Гомес Жуан - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки mybrary.info.


Математики, шпионы и хакеры. Кодирование и криптография отзывы

Отзывы читателей о книге Математики, шпионы и хакеры. Кодирование и криптография, автор: Гомес Жуан. Читайте комментарии и мнения людей о произведении.


Уважаемые читатели и просто посетители нашей библиотеки! Просим Вас придерживаться определенных правил при комментировании литературных произведений.

  • 1. Просьба отказаться от дискриминационных высказываний. Мы защищаем право наших читателей свободно выражать свою точку зрения. Вместе с тем мы не терпим агрессии. На сайте запрещено оставлять комментарий, который содержит унизительные высказывания или призывы к насилию по отношению к отдельным лицам или группам людей на основании их расы, этнического происхождения, вероисповедания, недееспособности, пола, возраста, статуса ветерана, касты или сексуальной ориентации.
  • 2. Просьба отказаться от оскорблений, угроз и запугиваний.
  • 3. Просьба отказаться от нецензурной лексики.
  • 4. Просьба вести себя максимально корректно как по отношению к авторам, так и по отношению к другим читателям и их комментариям.

Надеемся на Ваше понимание и благоразумие. С уважением, администратор mybrary.info.


Прокомментировать
Подтвердите что вы не робот:*