1. Прості числа
Просте число більше за 1 і має рівно два додатні дільники. 1 не є простим.
35 = 5 × 7, а 37 — просте.
Оберіть число.
Розділ 2 · Частина 3 · Місія 2.10
Математика двох ключів
Як відкрити ключ для всіх, а секрет залишити лише собі? Дослідимо прості числа, НСД, алгоритм Евкліда й обернені числа за модулем.
Справа Буча: два ключі, одна задача
Буч хоче отримувати секретні повідомлення без попередньої домовленості про спільний таємний ключ. Спочатку треба опанувати математичні інструменти. Сьогодні ми ще не шифруємо справжнім RSA.
2. НСД і Евклід
НСД(a,b) = НСД(b, a mod b). Повторюємо до нульової остачі.
3. Обернене за модулем
Шукаємо x, для якого a · x ≡ 1 (mod m). Воно існує лише за НСД(a,m)=1.
Навіщо це двом ключам?
RSA використовує прості множники, арифметику за модулем та обернені показники. Діффі—Геллман використовує степені за модулем, щоб узгодити спільний секрет. Це різні завдання. Малі числа з уроку не забезпечують реальної безпеки.
Чотири інтерактивні практики
1. Мисливець за простими
Розкладіть числа в групи. Перетягування або дотик на смартфоні.
2. Лабіринт Евкліда
Відновіть кроки ділення та дослідіть НСД.
3. Знайди обернений ключ
Досліджуйте коло остач і знаходьте обернені числа.
4. Майстерня двох ключів
Зберіть математичну схему RSA та відрізніть її від Діффі—Геллмана.
Короткий Python
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(252, 105)) # 21Компетентнісне завдання
Команда А бере випадкові малі числа без перевірок. Команда Б перевіряє простоту, НСД та існування оберненого. Який підхід математично обґрунтованіший? Чому цього ще недостатньо для реальної безпеки?
Пройти математичний сейф Буча