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

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

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

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

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

До 10 ооо

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

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

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

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

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

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

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

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 текст

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

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 текст

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

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

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

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

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

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

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

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

Алфавит 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 Ф.И. инициалы текст

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Задача