Введение в криптографию 2 Семейство алгоритмов над конечными полями (RSA) - презентация

1 Введение в криптографию 2 Семейство алгоритмов над конечными полями (RSA)

2 Задачи Закодировать Отчество шифром цезаря Гаммировать Имя (+Отчество) Фамилией Гаммировать Фамилию Сл. Последовательностью (генерировать на калькуляторе (или в экселе)). *Провести частотный анализ текста в Экселе

3 До Взять (по таблице простых чисел) число простое число р b+a+d (фио) Обратить по данному модулю число а+b+c+d Q/P Q/P

4 Ч числа КАРМАЙКЛА 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, … k i Кармайкловы ччисла имеют по меньшей мере три простых положительных множителя. Первые кармайкловы ччисла с четырьмя простыми множителями: псевдопростое число кармайкла Первые ччисла Кармайкла из 4 х чисел Первые ччисла Кармайкла

5 Тест Миллера Разность квадратов Т.к. n-простое или

6 До 10 ооо

7 Протокол Kerberos / Цербер Долгосрочный ключ Разделённый секрет Долгосрочный ключ Разделённый секрет А желает иметь общение сВ - Метка Сообщения

8 Конечные поля Не группа По умножению Делители нуля Функция Эйлера

9 F* 7 -группа * поля F 7 обратные корень 1 Задача построить поле (с+d) : вар.- ФИО Выписать обратные Найти корни

10 ф.Эйлера Разложение на простые множители Все разные:частный случай одно простое число Закодировать первые буквы Ф.И. Возвести в 1 ю большую abc степень k, взаимно простую с φ(n) использовав обратный в кольце φ(n) вычислить И Декодировать сообщение.

11 Вычислить 17-1mod125 Восстановление обр элемента отсюда Алгоритм Евклида Проход по остаткам

12 Вычислить 965-1mod 996 Восстановление обр элемента отсюда Алгоритм Евклида Проход по остаткам

13 Вычислить 965-1mod 996 Восстановление обр элемента отсюда Алгоритм Евклида Проход по остаткам

14 Mod 997 текст Т А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 ы 26 э 27 ю 28 я 29 текст

15 Разложение остаток

16 Mod 997 текст Т А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 ы 26 э 27 ю 28 я 29 текст

17 Технология ЭЛЕКТРОННЫХ платежей (Master card) секретно открыт секретно Односторонняя функция «затемняющий» МНОЖИТЕЛЬ

18 Mod остатки модуль Кратные 2 Кратные 5

19 Масси-Омуры p (открытое) Простое

20 Mod остатки модуль Кратные 5 Кратные

21 Пусть p=7,q=11 возьмём тогда

22 2 й RSA: Шифр c подписью

23 Потеря секретных данных секретно открыто Пусть тогда Что вместе с известно Квадратное уравнение Над R Корнями являются Теорема ВИЕТА

24 ПРОтокол ФИАТА-Шамира секретно открыто разложение Доверяют Все Юзеры Юзер А выбирает S секретно открыто как открытые данные идентификация * A выбирает с. r Передаёт его В * B случайным обр. выбирает Передаёт его A или * A вычисляет и передаёт его В проверка если * B проверяет если Отвергает без проверки repeat until

25 Алфавит a 0 b 1 c2 d3 e4 f5 g6 h7 I8 j9 k10 l11 m12 n13 o14 p15 q16 r17 s18 t19 u20 v21 w22 x23 y24 z25 а 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 ъ 26 ы 27 ь 28 э 29 ю 30 я 31 А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 ы 26 э 27 ю 28 я 29 А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 щ 26 ъ 27 ы 28 ь 29 э 30 ю 31 я ричная 32-ричная 30-ричная Ф.И.О. инициалы А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 ш 26 щ 27 ъ 28 ы 29 ь 30 э 31 ю 32 я 33 Ф.И. инициалы текст

26 Число атомов в планете Земля гугол Число атомов во вселенной Расстояние до Владивостока

27 Вычислить 7-1mod19 Восстановление обр элемента отсюда посчитаем Проход по остаткам

28 Криптосистема RSA работа Шифрованный текст Расшифровка

29 Зашифровать алгоритмом Масси-Омуры

30 Диффи-Хелмана Открытое общее знание шифровка или Де шифровка (обратно) Алгоритм секретно открыто секретно

31 Зашифровать алгоритмом Диффи-Хелмана

32 Эллиптические кривые строим требуется 0 p-1 =1 Теорема: существует неприводимый многочлен любой степени n 0 p-1 Многочленов степени n В точности неразложимпроверка откуда

33 Алгоритм ЕВКЛИДА в строим откуда Проверка неразложимости ЗАДАЧА: Обратить элемент а+b+d (оцифровка α 1 х+α0) в

34 Плином непрриводим Оцифровать f(x)(а+b+c+d) и Обратить по mod g

35

36 Простые ччисла Ччисла ферма Ччисла Мерсена

37 Задачи Найти все произведения Найти все обратимые Вычислить Ответ сравнить Найти порождающий(-щие) элементы Указать порядок каждого элемента группы

38 Задачи Оцифровать первые (2) или 3 буквы фамилии Взяв в качестве простого ччисла Зашифровать

39 Конечные поля

40 3 – порождающий элемент p-1 (обратимых) элементов

41 Задача