Наследие Ферма в каждом платеже
Честно скажем сразу: сама Великая теорема ничего не шифрует. Зато математика, выросшая вокруг неё, - модульная арифметика, малая теорема Ферма и эллиптические кривые из доказательства Уайлса - это фундамент современной криптографии. Ниже - три живых примера.
Малая теорема Ферма
У Ферма есть «младшая сестра» великой теоремы, и вот она работает безотказно: если p - простое число, а «a» на него не делится, то ap-1 mod p = 1. Остатки от деления степеней ходят по кругу и к шагу p - 1 всегда возвращаются к единице.
| k | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 3k mod 7 | 3 | 2 | 6 | 4 | 5 | 1 |
36 mod 7 = 1
RSA: шифр на остатках
Алгоритм RSA защищает банковские операции и сайты с замочком в адресной строке. Его корректность доказывается через малую теорему Ферма. Вот игрушечный RSA с маленькими простыми - настоящий использует числа в сотни цифр.
- сообщение 42
- 4217 mod 3 233 = 2 557
- шифр 2 557 летит по сети
- 2 5572 753 mod 3 233 = 42
Эллиптические кривые: из доказательства - в смартфон
Герои доказательства Уайлса живут и в твоём телефоне. «Сложение точек» на кривой (смотри картинку) легко выполнять, но крайне трудно обращать: зная точку P и результат тысяч сложений, найти число слагаемых практически невозможно.
На этой односторонности построена криптография ECC: подписи ECDSA в Bitcoin, обмен ключами в TLS и мессенджерах с шифрованием. Ключ ECC в 256 бит защищает не хуже ключа RSA в 3072 бита.