Презентация на тему: Математические основы шифрования

Математические основы шифрования
Разделы
Арифметика остатков
Арифметика остатков
Равный остаток
Модуль как оператор
Множество Z/NZ
Пример
Пример
Сравнимость по модулю
Операции на Z/NZ
Группы
Кольца
Замкнутость сложения
Ассоциативность сложения
Нуль является единичным элементом (или единицей) по сложению
Всегда существует обратный элемент по сложению
Коммутативность сложения
Замкнутость умножения
Ассоциативность умножения
Число 1 является единичным элементом (единицей) по умножению:
Умножение и сложение связанны законом дистрибутивности
Коммутативность умножения
Группы
Кольцо
Пример
Аддитивность
Мультипликативность
Цикличность
Дискретный логарифм
Кольцо
Пример
Поле
Центральная задача арифметики остатков
Пример
Наибольший общий делитель
Функция Эйлера
Функция Эйлера
Функция Эйлера
Малая теорема Ферма
Знать
1/41
Средняя оценка: 4.4/5 (всего оценок: 31)
Код скопирован в буфер обмена
Скачать (378 Кб)
1

Первый слайд презентации: Математические основы шифрования

Изображение слайда
2

Слайд 2: Разделы

Арифметика остатков Операции по модулю Группы и кольца Функция Эйлера Наибольший общий делитель Взаимная простота Алгоритм Евклида Китайская теорема об остатках

Изображение слайда
3

Слайд 3: Арифметика остатков

6 /12=6 18/12=6 3/12=3 15/12=3 Остатки

Изображение слайда
4

Слайд 4: Арифметика остатков

Фиксируется положительное натуральное число N, которое называется модулем Если разность двух целых чисел Ь — а делится на N нацело, то пишут а = b (mod N) В этом случае числа а и b имеют один и тот же остаток от деления на N, говорят, что в таком случае a и b сравнимы по модулю

Изображение слайда
5

Слайд 5: Равный остаток

b =7+7+7+3=24 a= 7+3=10 В алгебраической записи a =x•N+c b = y • N + c где х и у произвольные целые числа Очевидно, что разность делится на N без остатка. Для модуля N=7 - a-b=(x-y)•N+(c-c)=(x-y)•N

Изображение слайда
6

Слайд 6: Модуль как оператор

Будем использовать (mod N) как обозначение оператора модуля на множестве целых чисел, который вычисляет наименьшее натуральное число, сравнимое с данным по модулю N. 18 (mod 7) = 4, -18 (mod 7) = 3. 18-4=14 -18-3=21 Делятся на 7 без остатка

Изображение слайда
7

Слайд 7: Множество Z/NZ

Все возможные остатки от деления чисел на N образуют множество Z/NZ= {О,..., N-1} Z/NZ — множество значений оператора модуля (mod N).

Изображение слайда
8

Слайд 8: Пример

Например, множество всех возможных остатков от деления чисел на 7 это { 0,1,2,3,4,5,6 } Так 7 mod 7 =0 8 mod 7 =1 9 mod 7=2 10 mod 7 =3 … 13 mod 7 = 6 И снова 14 mod 7 =0 15 mod 7 = 1

Изображение слайда
9

Слайд 9: Пример

Эту идею так же можно пояснить через использование примера с представлением чисел, как k •N+ x, как только « x » становится равным N, т.е. наступает ситуация x=N можно переписать наше уравнение как ( k +1)• N + x - N и т.д.

Изображение слайда
10

Слайд 10: Сравнимость по модулю

В се сравнимые между собой по модулю N целые числа имеют один и тот же остаток, мы можем считать, что элемент Изображает целый класс чисел вида Таким образом, оперируя с целыми числами по модулю N, мы будем считать все сравнимые между собой числа равными друг другу

Изображение слайда
11

Слайд 11: Операции на Z/NZ

На множестве Z/NZ есть две основных операции — сложение и умножение. Они определяются обычным путем, например, (11 + 13) (mod 16) = 24 (mod 16) = 8, так как 24 = 1 • 16 + 8, (11 • 13) (mod 16) = 143 (mod 16) = 15, Поскольку 143 = 8•16 + 15.

Изображение слайда
12

Слайд 12: Группы

Это множества, обладающие определёнными свойствами из следующего списка: 1. Операция ассоциативна 2. Существует единичный элемент (или единица или нейтральный элемент) 3. Любой ненулевой элемент обратим Группа считается абелевой если умножение коммутативно 4. Коммутативность умножения Операцией может быть как сложение, так и умножение ( G,+ ) и (G,●) соответственно

Изображение слайда
13

Слайд 13: Кольца

Это множества, обладающие определёнными свойствами из следующего списка: 1. Замкнутость сложения 2. Ассоциативность сложения 3. Ноль является единичным элементом (или единицей) по сложению 4. Всегда существует обратный элемент по сложению 5. Коммутативность сложения 6. Замкнутость умножения 7. Ассоциативность умножения 8. Число 1 является единичным элементом (единицей) по умножению 9. Умножение и сложение связаны законом дистрибутивности 10. Коммутативность умножения

Изображение слайда
14

Слайд 14: Замкнутость сложения

Число полученное в результате операции сложения(двух целых чисел) тоже является целым. Это не так, например, в случае с делением. При делении 5 на 2 результат не находится в множестве целых чисел. Для любых a и b принадлежащих к множеству выполняется следующее

Изображение слайда
15

Слайд 15: Ассоциативность сложения

Свойство показывает, что порядок применения операции сложения к нескольким числам не влияет на результат

Изображение слайда
16

Слайд 16: Нуль является единичным элементом (или единицей) по сложению

При сложении любого числа из указанного множества с нулём получается то же самое число

Изображение слайда
17

Слайд 17: Всегда существует обратный элемент по сложению

Для любого элемента из указанного множества существует такой элемент, что при сложении его(по модулю) с некоторым другим числом из этого множества, которое называют обратным получится единица( в смысле единичного элемента по сложению, который в данном случае равен нулю). В случае когда мы говорим о операциях не по модулю, т.е. изучающемуся в школе, всё просто. Обратный элемент это число с противоположным знаком, т.е. для 9, обратный элемент -9, т.к. 9+(-9)=9-9=0 Когда мы рассматриваем операции по модулю, ситуация сложнее, например, обратный элемент к 6 при сложении по модулю 7 будет 1, т.к. ( 6+1 ) ( mod 7 ) =7(mod7)=0

Изображение слайда
18

Слайд 18: Коммутативность сложения

От перемены мест слагаемых, сумма не меняется 

Изображение слайда
19

Слайд 19: Замкнутость умножения

То же что и при сложении, результат применения операции к числам Из указанного множества не выходит за его пределы.

Изображение слайда
20

Слайд 20: Ассоциативность умножения

То же, что для сложения, при наличии трёх и более аргументов, результат одинаков в не зависимости от порядка применения операции.

Изображение слайда
21

Слайд 21: Число 1 является единичным элементом (единицей) по умножению:

При умножении любого числа из множества на 1, результатом будет само это число

Изображение слайда
22

Слайд 22: Умножение и сложение связанны законом дистрибутивности

Изображение слайда
23

Слайд 23: Коммутативность умножения

Изображение слайда
24

Слайд 24: Группы

Это множество с операцией, которая : замкнута обладает единицей ассоциативна относительно нее каждый элемент обладает обратным Группу с коммутативной операцией называют коммутативной или абелевой. Т.е. множество обладающее св-вами 1-4 называется группой, а при выполнении 5 условия абелевой группой

Изображение слайда
25

Слайд 25: Кольцо

Абелева группа в которой сложение и умножение связаны законом дистрибутивности

Изображение слайда
26

Слайд 26: Пример

Целые, вещественные или комплексные числа по сложению. Единицей здесь является обычный О, а обратным к х служит - x, т.к. x +(-х) = 0. Ненулевые рациональные, вещественные или комплексные числа по умножению. Единица в них — это 1, и обратным к х будет, поскольку x • =1.

Изображение слайда
27

Слайд 27: Аддитивность

Группу называют аддитивной если ее операция записывается как сложение: Аддитивные группы обозначаются (G, +).

Изображение слайда
28

Слайд 28: Мультипликативность

Группа называется мультипликативной если мы записываем ее операцию как умножение, т. е. точкой: Такая группа обозначается как (G, •)

Изображение слайда
29

Слайд 29: Цикличность

Абелева группа называется циклической если в ней есть образующая Любой другой элемент группы получается многократным применением к ней(образующей) групповой операции. Например, число 1 — образующая группы целых чисел по сложению. 7 = 1 + 1 + 1 + 1 + 1 + 1 + 1, - 2 = (-1) + (-1).

Изображение слайда
30

Слайд 30: Дискретный логарифм

Если g — образующая циклической группы G, мы пишем G = < g >, В мультипликативном случае каждый элемент h группы G можно записать в виде а в аддитивном где x в обоих случаях — некоторое целое число, называемое дискретным логарифмом элемента h по основанию g.

Изображение слайда
31

Слайд 31: Кольцо

Кольцо — это множество R с двумя операциями, сложением и умножением, традиционно обозначаемыми «+» и «•», которые обладают свойствами 1-9. Кольцо вместе с его операциями можно записать тройкой ( R, •, +). Если окажется, что умножение в данном кольце коммутативно, то кольцо называют коммутативным.

Изображение слайда
32

Слайд 32: Пример

Вы знакомы с бесконечными коммутативными кольцами целых, вещественных и комплексных чисел Множество остатков Z/NZ с операциями сложения и умножения тоже является коммутативным кольцом, которое часто называют кольцом вычетов по модулю N Кольцо вычетов — один из центральных объектов криптографии, на свойствах которого основаны многие методы шифрования

Изображение слайда
33

Слайд 33: Поле

Полем называется множество (F, •,+) с двумя операциями, обладающее дополнительными свойствами: - (F, +) — абелева группа с единичным элементом О, - {F \ {0}, •) — абелева группа с единичным элементом 1, - (F, •, +) удовлетворяет закону дистрибутивности. Следовательно, поле — это коммутативное кольцо, в котором каждый ненулевой элемент обратим.

Изображение слайда
34

Слайд 34: Центральная задача арифметики остатков

Одна из центральных задач арифметики остатков — это решение уравнения а • x = b (mod N ) Т.е. на что надо умножить x, чтобы при делении на N остаток был равен b. Линейное уравнение ах = b с вещественными коэффициентами при а≠0 всегда разрешимо. Если же рассматривать его над кольцом целых чисел, то ответ найдется не всегда. Например, не существует целого числа x, обращающего уравнение 2 x = 5 в верное равенство. Случай кольца вычетов еще более сложный.

Изображение слайда
35

Слайд 35: Пример

существует ровно одно решение уравнения 7•x = 3 (mod 143), уравнение 11• x = 3 (mod 143) решений не имеет множество решений уравнения 11 •x = 22 (mod 143) насчитывает 11 элементов.

Изображение слайда
36

Слайд 36: Наибольший общий делитель

Количество решений вышеописанной задачи определяется наибольшим общим делителем НОД( a,N ) Когда НОД( a,N )=1 говорят, что числа a и N взаимнопросты.

Изображение слайда
37

Слайд 37: Функция Эйлера

Число элементов кольца Z/ N Z, взаимно простых с N, дается функцией Эйлера Всякое составное число может быть единственным образом представлено в виде произведения простых множителей. Например, 48 = 2 · 2 · 2 · 2 · 3 225 = 3 · 3 · 5 · 5 1050 = 2 · 3 · 5 · 5 · 7

Изображение слайда
38

Слайд 38: Функция Эйлера

Если То

Изображение слайда
39

Слайд 39: Функция Эйлера

Особый интерес представляют следующие частные случаи: Если р простое, то Если р и q — простые числа и p≠q то

Изображение слайда
40

Слайд 40: Малая теорема Ферма

Для Z/NZ при простом модуле N выполняется равенство

Изображение слайда
41

Последний слайд презентации: Математические основы шифрования: Знать

Что такое арифметика остатков Что означает формулировка числа a и b сравнимы по модулю N Множество значений оператора mod N (т.е. понимать что это за множество) Какие свойства определяют группы и кольца Что такое образующая группы Что такое циклическая группа Что такое поле Что такое ф-я Эйлера и как вычислить её значение Формулировку Малой теоремы Ферма

Изображение слайда