Шифрование с помощью простых чисел

1. Шифрование RSA с помощью простых чисел

МОУ «Средняя школа № 3» г. Николаевска
Шифрование RSA с помощью
простых чисел
Автор:
Руководитель:

2.

Тема данного проекта актуальна, т.к
защита данных с помощью
шифрования становится всё больше
востребованна с каждым годом.
Задача проекта – объяснение
работы шифрования RSA
Цель – научить защищать данные
технологией RSA

3. Что будет использовано для шифрования?

1) Решето Эратосфена
2) Модульная арифметика
3) Функция Эйлера
3) Числа Ферма
4) Алгоритм Евклида
5) Расширенный алгоритм Евклида

4.

1) Для шифрования данных простыми числами,
нужны сами простые числа. Для нахождения
простых чисел можно использовать решето
Эратосфена.
Решето Эратосфена –
это алгоритм
нахождения всех
простых чисел до
некоторого целого
числа n.

5.

Для отсеивания простых чисел надо знать,
что такое простое число.
Просто число – это число, которое делится
только само на себя и 1 (сама единица не в
счёт)
Все остальные числа – это либо составные,
либо единица
Пример: 2,3,5,7,11,13…

6.

Алгоритм нахождение простых чисел с
помощью решета Эратосфена прост, нужно
взять любое число n и все числа, стоящие до
n, надо делить на 2, 3, 4, 5…, n, оставляя
только те числа, которые делятся сами на себя
и 1, так отсеются все составные числа.
Пример: все простые числа до 100

7. Есть ещё другие способы нахождения простых чисел в ходе отсеивания составных, например:

1) Решето Аткина
2) Числа Мерсенна и тест Люка-Лемера
3) Теорема Ферма и тест Миллера-Рабина
Но для наглядного примера Решето
Эратосфена будет самым оптимальным!

8. 2) Добавляем модульную арифметику

Это раздел математики, изучающий сравнение
двух целых чисел по модулю натурального
числа, то есть - это операция, позволяющая
ответить на вопрос “дают ли 2 целых числа при
делении на одно и тоже натуральное число
одинаковые остатки?”
Примеры:
11 ≡ 5 mod 6 (11 эквивалентно 5 по модулю 6)
23 ≡ 1 mod 2 (23 эквивалентно 1 по модулю 2)

9. 3) функция Эйлера φ(n)

Функция Эйлера вычисляет количество взаимно
простых чисел с данным числом, то есть числа, у
которых НОД с данным числом равен 1

10. 4) Числа Ферма

2