Дидактические цели
Как можно отправить кому-то секретное сообщение с помощью ключа, который знают все? Этот парадокс и есть RSA — алгоритм, который до сих пор защищает интернет-соединения. Лаборатория для старшей школы и университета проходит путь целиком: от простого шифра Цезаря до генерации открытых и закрытых ключей, через модульную арифметику и теорию чисел, делающие всю эту магию возможной.
Чему учимся
Ученик строит RSA кирпичик за кирпичиком, не пропуская ни одного шага: сначала взламывает Цезаря, чтобы понять, зачем нужно что-то лучше, затем открывает модульную арифметику и функцию φ Эйлера, и наконец с помощью малой теоремы Ферма видит, почему возведение в степень e шифрует, а в степень d — расшифровывает.
По дороге прорабатывается понятие обратной функции (декодирование versus кодирование).
- Исследуется шифр Цезаря с интерактивным диском: шифровать, расшифровывать и считать 25 возможных ключей.
- Прорабатываются сложение и умножение по модулю m, включая мультипликативный обратный (5·x ≡ 1 mod 11).
- Вычисляется φ(n) в трёх вариантах: φ(15) на сетке 3×5, φ(77) = 6×10, φ(125) = 5³ − 5².
- Выводится формула φ(pq) = (p−1)(q−1) на основе предыдущих примеров.
- Открывается теорема Ферма: a^10 ≡ 1 mod 11 для любого a, не кратного 11; и что кратные (20, 30, 40) тоже работают.
- Пошагово генерируются ключи RSA: выбрать
e, взаимно простое с φ(n), вычислитьdкак обратный кeпо модулю φ(n), и различить открытый ключ (e, n) от закрытого ключа d. - Шифруется и расшифровывается конкретное сообщение (m = 2, n = 55) с помощью быстрого возведения в степень последовательным возведением в квадрат.
- Исследуются допустимые комбинации пар (e, d) и обосновывается, почему получить d из n невозможно без знания p и q.
- Финальный зал вводит блочное кодирование из k−1 бит для настоящих сообщений.
Ключевые математические идеи
- Обратные функции: некоторые операции можно отменить.
- Модульная арифметика: сложение и произведение цикличны; мультипликативные обратные существуют, когда множители взаимно просты.
- Функция φ Эйлера: φ(pq) = (p−1)(q−1) подсчитывает целые числа, меньшие n и взаимно простые с n.
- Малая теорема Ферма / теорема Эйлера: a^φ(n) ≡ 1 mod n; позволяет обратить возведение в степень, взяв остаток от показателя.
- Пара ключей RSA: e·d ≡ 1 mod φ(n) гарантирует, что (mᵉ)ᵈ ≡ m (mod n).
- Безопасность через факторизацию: зная только n и e, невозможно вычислить φ(n) — а значит и d — без разложения n на множители, что неразрешимо для чисел из сотен цифр.
- Быстрое возведение в степень: последовательное возведение в квадрат сокращает O(n) умножений до O(log n).
Содержание по залам
Зал 1 · Криптография: секретные сообщения
Введение в лабораторию: что такое криптография, почему атака перебором может взломать слабые ключи и как модульная арифметика делает RSA возможным.
Задания для ученика
- Прочитать введение и понять задачу, которую ставит перебор.
- Перейти дальше, чтобы начать путешествие по залам.
Зал 2 · Шифр Цезаря
Интерактивный диск с двумя концентрическими кольцами (буквами). При нажатии кнопок + и − внутреннее кольцо поворачивается, задавая сдвиг; ученик вводит сообщение и наблюдает, как оно шифруется побуквенно.
Задания для ученика
- Повернуть диск на нужный сдвиг.
- Написать сообщение и посмотреть на получившийся шифртекст.
Зал 3 · Сколько ключей у Цезаря?
Ученик получает шифртекст «MJQQT RZSIT» и должен повернуть диск, чтобы найти исходное сообщение. Затем отвечает, сколько различных ключей у шифра Цезаря.
Задания для ученика
- Повернуть диск и расшифровать «MJQQT RZSIT».
- Ответить, сколько различных ключей у Цезаря (25).
Зал 4 · Обратный сдвиг
HOLA, зашифрованная со сдвигом 15, даёт WDAP. Ученик должен найти обратный сдвиг, который возвращает WDAP в HOLA, вводя идею обратной операции в модульной арифметике.
Задания для ученика
- Вычислить сдвиг, расшифровывающий WDAP → HOLA (ответ: 11).
Зал 5 · Сложение по модулю m
Интерактивный исследователь с ползунками для двух слагаемых и выбором модуля. Модуль 12 визуализирует сложение как на аналоговых часах.
Задания для ученика
- Двигать ползунки и менять модуль для исследования различных сумм.
- Ответить, чему равно 8 + 6 mod 11 (ответ: 3).
Зал 6 · Умножение по модулю m
Исследователь модульного умножения. Вводится понятие мультипликативного обратного: число x такое, что a·x ≡ 1 (mod m).
Задания для ученика
- Изучить произведения по разным основаниям и модулям.
- Найти мультипликативный обратный к 5 по модулю 11 (ответ: 9, так как 5·9 = 45 ≡ 1 mod 11).
Зал 7 · Функция Эйлера φ
φ(n) считает целые числа от 1 до n, взаимно простые с n. Визуализация — сетка 3×5 для n = 15 = 3×5, в которой выделены кратные 3 и 5.
Задания для ученика
- Посмотреть, какие клетки остались не выделенными в сетке 3×5.
- Вычислить φ(15), пересчитав взаимно простые числа (ответ: 8).
Зал 8 · Вычисли φ(77)
Прямое применение формулы φ(p·q) = (p−1)(q−1) для n = 77 = 7×11.
Задания для ученика
- Вычислить φ(77) по простым множителям 7 и 11 (ответ: 60).
Зал 9 · Вычисли φ(125)
Случай степени простого числа: 125 = 5³. Только кратные 5 имеют общий множитель с 125, поэтому φ(125) = 125 − 25 = 100.
Задания для ученика
- Подсчитать кратные 5 в промежутке от 1 до 125.
- Вычислить φ(125) (ответ: 100).
Зал 10 · Общая формула φ(pq)
Повторение на примере p=3, q=5: методом включений-исключений выводится pq − q − p + 1 = (p−1)(q−1). Ученик выбирает правильную формулу из четырёх вариантов.
Задания для ученика
- Повторить рассуждение на примере методом включений-исключений.
- Выбрать правильную формулу для φ(p·q): (p−1)(q−1).
Зал 11 · Открытие Ферма
Интерактивный исследователь степеней по модулю 11: ученик меняет основание и показатель и обнаруживает, что существует показатель, всегда дающий 1 (Малая теорема Ферма).
Задания для ученика
- Перебрать разные основания с показателем 10 mod 11.
- Определить «магический показатель», всегда дающий 1 (ответ: 10).
Зал 12 · Кратные порядку
Уже известно, что показатель 10 всегда даёт 1 mod 11. Ученик должен отметить из списка показателей те, которые тоже работают (кратные 10).
Задания для ученика
- Выбрать из списка показатели, при которых a^exp ≡ 1 mod 11 для любого основания.
- Найти закономерность: это числа 20, 30 и 40 (кратные 10).
Зал 13 · Шифрование и расшифрование с помощью теоремы Ферма
Так как 7×3 = 21 ≡ 1 mod 10, возведение в степень 7 шифрует, а в степень 3 расшифровывает по модулю 11. Ученик проверяет это с помощью интерактивного ползунка и убеждается, что шифрование с последующим расшифрованием возвращает исходное сообщение.
Задания для ученика
- Использовать исследователь для шифрования числа с показателем 7 mod 11.
- Применить показатель 3 к результату и убедиться, что исходное число восстановлено.
Зал 14 · От Ферма к RSA
Пояснительный зал, обобщающий теорему Ферма на составные числа с помощью теоремы Эйлера: a^φ(n) ≡ 1 (mod n). На примере n = 91 = 7×13, φ = 72, e = 5, d = 29 показывается, что e·d ≡ 1 mod φ(n) гарантирует пару шифрование/расшифрование.
Задания для ученика
- Прочитать обобщение Ферма на случай RSA с p=7, q=13.
- Проверить, что 5·29 = 145 ≡ 1 mod 72.
Зал 15 · Открытый ключ e
При φ(n) = 40 = 2³×5 ученик должен выбрать e, взаимно простое с 40, из кандидатов {2, 3, 5, 8, 10, 40}. Применяется условие НОД(e, 40) = 1.
Задания для ученика
- Исключить чётные числа и кратные 5.
- Выбрать единственное допустимое значение открытого ключа e (ответ: 3).
Зал 16 · Закрытый ключ d
Дано e = 3 и φ(n) = 40. Ученик находит d такое, что 3·d ≡ 1 mod 40, последовательно перебирая значения (3×27 = 81 = 2×40 + 1).
Задания для ученика
- Перебирать значения d до тех пор, пока 3·d mod 40 = 1.
- Ввести результат (ответ: 27).
Зал 17 · Ключи RSA
Визуальное резюме полученной пары ключей при p=5, q=11: открытый ключ (e=3, n=55), которым делятся со всеми, и закрытый ключ (d=27, n=55), известный только владельцу.
Задания для ученика
- Понять различие между открытым и закрытым ключами.
- Перейти дальше с уже созданной парой ключей для блока шифрования.
Зал 18 · Шифрование RSA
Применение формулы шифрования c = m^e mod n при m=2, e=3, n=55. Первое численное знакомство с этапом шифрования RSA.
Задания для ученика
- Вычислить c = 2³ mod 55 (ответ: 8).
Зал 19 · Быстрое возведение в степень
Для вычисления 8^27 mod 55 используется метод последовательного возведения в квадрат: 8² = 64 ≡ 9, 8⁴ = 9² = 81 ≡ 26 … Ученик вычисляет промежуточный шаг 8⁴ mod 55.
Задания для ученика
- Следовать методу последовательного возведения в квадрат.
- Вычислить 8⁴ mod 55 (ответ: 26).
Зал 20 · Расшифрование RSA
Так как 27 = 16+8+2+1, разложим 8^27 в произведение известных степеней (8¹, 8², 8⁸, 8¹⁶ mod 55). Ученик выбирает правильную операцию (умножить, а не сложить) и вычисляет результат.
Задания для ученика
- Выбрать между «сложить» и «умножить» степени (верно: умножить).
- Вычислить 8²⁷ mod 55 (ответ: 2, исходное сообщение).
Зал 21 · Полный цикл!
Анимация полного цикла RSA с m=2, e=3, d=27, n=55: зашифровать → c=8, расшифровать → m=2. Демонстрирует, почему работает тождество m^(e·d) ≡ m (mod n) по теореме Эйлера.
Задания для ученика
- Посмотреть анимацию полного цикла шифрования-расшифрования.
- Убедиться, что расшифрованное сообщение совпадает с исходным.
Зал 22 · Почему RSA безопасен?
Объяснение основы безопасности: чтобы получить d, нужно вычислить φ(n), а для этого требуется разложить n на множители. Для n примерно из 617 цифр классические алгоритмы потратят больше времени, чем возраст Вселенной.
Задания для ученика
- Прочитать аргумент безопасности и сравнение n=55 (легко) с числом из 617 цифр (невозможно).
Зал 23 · Исследователь ключей RSA
Свободный инструмент: ученик выбирает p и q из нескольких вариантов (11/13/17 и 17/19/23) и видит все допустимые пары (e, d) для этих простых чисел с таблицей k·φ(n)+1 = e×d.
Задания для ученика
- Выбирать разные комбинации p и q.
- Наблюдать, сколько допустимых пар ключей генерирует каждая комбинация.
Зал 24 · Допустимые комбинации ключей
При p=3, q=11, n=33, φ=20 ученик отмечает из списка все пары (e, d), образующие допустимые ключи RSA (условие: НОД(e, 20)=1 и e·d ≡ 1 mod 20).
Задания для ученика
- Проверить НОД для каждого кандидата e.
- Вычислить e·d mod 20 и отметить пары, дающие 1: (3,7), (9,9), (13,17), (19,19).
Зал 25 · Итоговое задание: найди закрытый ключ
Полноценное задание с p=7, q=29, n=203, φ=168, e=5, m=2. Ученик должен найти d такое, что 5·d ≡ 1 mod 168, зашифровать m и проверить, что расшифрование возвращает исходное сообщение.
Задания для ученика
- Вычислить d как обратное к 5 по модулю 168 (ответ: 101).
- Проверить цикл шифрования-расшифрования с полученными значениями.
Зал 26 · Почему сложно найти d?
Злоумышленник знает n и e, но не знает φ(n). Вопрос с выбором ответа: почему он не может напрямую применить расширенный алгоритм Евклида для вычисления d?
Задания для ученика
- Прочитать задачу злоумышленника.
- Выбрать правильную причину: φ(n) трудно вычислить, не зная p и q.
Зал 27 · Блочное кодирование
На практике сообщение не шифруется побуквенно: весь текст переводится в биты и делится на равные блоки, каждый из которых меньше n (демонстрация на слове «HOLA»). Задаётся вопрос: какого размера должен быть блок, если n имеет k бит.
Задания для ученика
- Посмотреть демонстрацию блоков на слове «HOLA».
- Выбрать правильный размер блока: k−1 бит, чтобы блок был гарантированно меньше n.
Залы для показа
Самые наглядные для показа и обсуждения в классе.