Математические основы криптографии

Роль ПреподавательГде АзТУ, Баку

Наглядные объяснения к курсу. Всё работает прямо в браузере: меняйте входные данные, проходите алгоритм или атаку по шагам и смотрите, где именно всё получается или ломается.

Теория чисел

Расширенный алгоритм Евклида и обратные по модулю

Остатки уменьшаются, а каждая строка сохраняет r = x·a + y·n. Когда остаток равен 1, x и есть обратный элемент. Игрушечный RSA даёт d.

gcd · Bézout · a⁻¹ mod nОткрыть →

Китайская теорема об остатках

Два циферблата вращаются вместе, один по модулю m, другой по модулю n, пока оба не покажут нужные остатки. Тогда загорается вся сетка.

x ≡ a (mod m) · x ≡ b (mod n)Открыть →

Степени по модулю p: Ферма, Эйлер и порядки

Следите, как a, a², a³, … идут по кругу, пока цикл не замкнётся.

aᵖ⁻¹ ≡ 1 · ord(a) | p − 1Скоро

RSA: от генерации ключей до расшифрования

Выберите два простых числа и проследите каждое число в схеме.

n = pq · ed ≡ 1 (mod φ)Скоро

Эллиптические кривые

Сложение точек на эллиптической кривой

Правило хорды и касательной над вещественными числами, затем те же формулы над 𝔽ₚ, где прямая заворачивается по сетке.

y² = x³ + ax + b · P + Q · kGОткрыть →

Решётки и постквантовая криптография

Хороший и плохой базис одной решётки

Одна и та же сетка точек, два базиса. С коротким базисом округление находит ближайшую точку; с длинным и скошенным — нет.

L(B) · CVP · Babai · LWEОткрыть →

Подписи

ECDSA: повторил nonce — потерял ключ

У двух подписей с одним k одинаковое r. Четыре строки алгебры — и закрытый ключ раскрыт.

s = k⁻¹(z + r·d) mod nОткрыть →

Приложения

Подсчёт зашифрованных бюллетеней

Зашифровать каждый бюллетень, объединить шифртексты, расшифровать только итог. Paillier опирается на факторизацию, схема LWE — на шум.

Enc(a) · Enc(b) = Enc(a + b)Открыть →

Другие темы

Группы и образующие

Таблицы Кэли для ℤₙ* и то, как образующий обходит все элементы.

⟨g⟩ · LagrangeСкоро

Арифметика в GF(2⁸)

Байты как многочлены, умножение с приведением и S-блок AES.

x⁸ + x⁴ + x³ + x + 1Скоро

Хеш-функции: лавинный эффект и дни рождения

Измените один бит входа — изменится половина выхода; найдите коллизию короткого хеша.

2ⁿ/² · SHA-256Скоро