Воскресенье, 11.04.2021, 06:54
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 2
Гостей: 2
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » КОДИРОВАНИЕ И КРИПТОГРАФИЯ

16 = 4. Модульная арифметика и математика шифра Цезаря
29.05.2015, 16:51

16 = 4? 2 = 14? Это не ошибка и не какая-то странная система счисления. Работа шифра Цезаря может быть проиллюстрирована теорией, которая привычна для математики и в еще большей степени для криптографии — модульной арифметикой, иногда называемой часовой арифметикой. Эта теория появилась еще в работах греческого математика Евклида (325–265 гг. до н. э.) и является одной из основ современной информационной безопасности. В этом параграфе мы расскажем о базовых математических понятиях, связанных с этим особым типом арифметики.

Возьмите в качестве примера обычные часы со стрелками и сравните их с цифровыми часами. На часах со стрелками циферблат разделен на 12 частей, которые мы обозначим числами 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, И. В следующей таблице можно видеть, как время на аналоговом циферблате соответствует времени после полудня на экране цифровых часов.

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

Когда мы говорим, например, что сейчас 14:00, мы можем также сказать, что сейчас два часа дня. Тот же принцип применяется и в случае измерения углов. Угол в 370 градусов равен углу в 10 градусов, потому что от первого значения мы должны вычесть полный оборот в 360 градусов. Заметим, что 370 = (1 х 360) + 10, то есть 10 является остатком от деления 370 на 360. Какой угол эквивалентен углу в 750 градусов? Вычитая соответствующее количество полных оборотов, мы получим, что угол в 750 градусов равен углу в 30 градусов. Мы видим, что 750 = (2 х 360) + 30, то есть 30 является остатком от деления 750 на 360. В математике это обозначается так:

750

Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография - t.jpg_14
 30 (mod 360)

Мы говорим: «750 сравнимо с 30 по модулю 360». В случае с часами мы бы написали

14

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

Мы также можем представить себе часы с отрицательными числами. В этом случае который будет час, когда стрелка показывает на —7? Или, другими словами, с каким числом сравнимо число —7 по модулю 12? Давайте посчитаем, учитывая, что на наших часах с циферблатом, разделенным на 12 частей, значение 0 соответствует 12.

— 7 = —7 + 0 = —7 + 12 = 5.

* * *

ОТЕЦ АНАЛИТИЧЕСКОЙ КРИПТОГРАФИИ

Основная работа Евклида Александрийского, «Начала», состоит из 13 томов, в которых излагаются основные факты планиметрии, теории пропорций, свойства чисел, сведения об иррациональных числах и стереометрии. Чаще всего ассоциируемые с этой последней теорией, работы греческого математика, связанные с арифметическими операциями на конечных числовых множествах, или операциями по модулю, являются одним из столпов современной теории криптографии. Известные и почитаемые еще арабскими учеными, работы Евклида впервые были изданы в Венеции в 1482 г. Вовсе не случайно, что и арабы, и венецианцы были великими мастерами криптографии.

* * *

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

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

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

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

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

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

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

* * *

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

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

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

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

а — b  0 (mod m)

а b кратно m

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

19 

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

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

19 

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

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

127 

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

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

(1) 3 + 3 

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

(2) 3 + 14 

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

(3) 3 х 3 = 9 

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

(4) 5 x 4 = 20 

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

(5) 7 

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

(6) 35 

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

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

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

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

Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография - _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 

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

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

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

* * *

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

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

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

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

* * *

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мир математики. т.2. Математики, шпионы и хакеры. Кодирование и криптография - _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 

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

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

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

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

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

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

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

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

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

С(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.

Категория: КОДИРОВАНИЕ И КРИПТОГРАФИЯ | Добавил: admin | Теги: шифры, криптография и математика, кодирование информации, модульная арифметика, занимательная математика, дидактический материал по математик
Просмотров: 4032 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ

ИНФОРМАТИКА В ШКОЛЕ

ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"

ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ИГРОВЫЕ ЗАДАНИЯ ПО ИНФОРМАТИКЕ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2021
    Яндекс.Метрика Рейтинг@Mail.ru