Выбери любимый жанр

Математики, шпионы и хакеры. Кодирование и криптография - Гомес Жуан - Страница 6


Перейти на страницу:
Изменить размер шрифта:

6

ОПЕРАЦИИ ПО МОДУЛЮ

Как посчитать 231 по модулю 17 на калькуляторе?

Сначала мы разделим 231 на 17 и получим 13,58823529.

Затем найдем произведение 13 x 17 = 221. Таким образом мы избавимся от дробной части.

Наконец, найдем разность 231–221 = 10, получив остаток отделения.

Итак, 231 по модулю 17 равно 10. Этот результат записывается как 231 

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

* * *

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

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_6
b (mod m), если остаток от деления а на m равен b, при условии что а, b и m — целые числа. Число b сравнимо с остатком от деления а на m. Следующие утверждения эквивалентны:

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_7
b (mod m)

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_8
a (mod m)

а — b  0 (mod m)

а b кратно m

Вопрос «Которому часу на часах со стрелками соответствует время 19 часов?» эквивалентен в математических терминах следующему вопросу: «С каким числом сравнимо число 19 по модулю 12?» Чтобы ответить на этот вопрос, мы должны решить уравнение

19 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_13
х (mod 12).

Разделив 19 на 12, мы получим частное 1 и остаток 7, поэтому

19 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_14
7 (mod 12).

А в случае 127 часов? Разделив 127 на 12, мы получим частное 10 и остаток 7, поэтому

127 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_15
7 (mod 12).

Чтобы повторить изученное до сих пор, давайте рассмотрим следующие операции по модулю 7:

(1) 3 + 3 

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

(2) 3 + 14 

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

(3) 3 х 3 = 9 

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

(4) 5 x 4 = 20 

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

(5) 7 

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

(6) 35 

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

(7) -44 = -44 + 0 = -44 + 7 х 7 

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

(8) -33 = -33 + 0 = -33 + 5 x 7 

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

(1) 6 меньше, чем модуль, поэтому не меняется

(2) 3 + 14 = 17; 17: 7 = 2 и в остатке 3.

(3) 3 X 3 = 9; 9: 7 = 1 и в остатке 2.

(4) 5 х 4 = 20; 20: 7 = 2 и в остатке 6.

(5) 7 = 7; 7: 7 = 1 и в остатке 0.

(6) 35 = 35; 35: 7 = 5 и в остатке 0.

(7) -44 = -44 + 0; 44 + 7 х 7 

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

(8) -33 = -33 + 0; -33 + 5 x 7 

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

* * *

ТАБЛИЦА УМНОЖЕНИЯ ПО МОДУЛЮ 5 В EXCEL

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

Построить такую и подобные таблицы очень легко даже с базовыми знаниями офисной программы Excel. В нашем случае синтаксис функций для ячеек Excel (для столбцов и строк на нашем компьютере) показан ниже. Действие «остаток отделения числа на 5» переводится на язык Excel как «=ОСТАТ(число;5)». Конкретная операция по нахождению произведения 4 на 3 по модулю 5 записывается как «=ОСТАТ (4∙3;5)» и дает результат 2. Подобные таблицы очень помогают в расчетах по модульной арифметике.

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

* * *

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

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

Мы видим, что зашифрованное значение буквы под номером х (в стандартном алфавите) является буквой, стоящей на позиции х + 3 (также в стандартном алфавите). Поэтому необходимо найти преобразование, которое каждому числу ставит в соответствие число, сдвинутое на три единицы, и взять результат по модулю 26.

Заметим, что 3 является ключом нашего шифра. Таким образом, наша функция записывается как

C(х) = + 3) (mod 26),

где х — изначальное значение, а С(х) — зашифрованное значение. Теперь достаточно подставить вместо буквы ее числовое значение и применить трансформацию.

Возьмем в качестве примера слово PLAY и зашифруем его.

Буква Р стоит на позиции 15, С(15) = 15 + 3

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_19
 18 (mod 26), а число 18 соответствует букве S.

Буква L стоит на позиции 11, С(11) = 11 + 3 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_20
14 (mod 26), а число 14 соответствует букве О.

Буква А стоит на позиции 0, С(0) = 0 + 3 

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

Буква Y стоит на позиции 24, С (24) = 24 + 3 = 27 

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

Таким образом, слово PLAY, зашифрованное с ключом 3, превратится в слово SODB.

В общем случае, если х означает позицию буквы, которую мы хотим зашифровать (0 для А, 1 для В, и т. д.), позиция зашифрованной буквы [обозначаемая С(х)] выражается формулой

С(х) = + k) (mod n),

где n — длина алфавита (26 в английском алфавите), a k — ключ, используемый в данном шифре.

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

С-1(х) =k) (mod n).

В случае сообщения SODB, зашифрованного шифром Цезаря с ключом 3 с применением английского алфавита, то есть k = 3 и n = 26, мы получим:

С-1(х) = 3) (mod 26).

Применим эту формулу следующим образом:

Для S: х = 18, С-1(18) = 18 — 3 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_23
15 (mod 26), что соответствует букве Р.

Для О: х = 14, С-1(14) = 14 — 3 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_24
 11 (mod 26), что соответствует букве L.

Для D: х = 3, С-1(3) = 3–3 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_25
0 (mod 26), что соответствует букве А.

Для В: x = 1, С-1(1) = 1–3 = —2 + 26 

Математики, шпионы и хакеры. Кодирование и криптография - _15.jpg_26
24 (mod 26), что соответствует букве Y.

Сообщение SODB, зашифрованное шифром Цезаря с ключом 3, соответствует, как мы уже знаем, оригинальному тексту PLAY.

6
Мир литературы

Жанры

Фантастика и фэнтези

Детективы и триллеры

Проза

Любовные романы

Приключения

Детские

Поэзия и драматургия

Старинная литература

Научно-образовательная

Компьютеры и интернет

Справочная литература

Документальная литература

Религия и духовность

Юмор

Дом и семья

Деловая литература

Жанр не определен

Техника

Прочее

Драматургия

Фольклор

Военное дело