От школьной параболы к криптографии: как геометрия помогает защищать данные
Школьная парабола (y=x^2) умеет неожиданную вещь: с ее помощью можно перемножать числа. Для вычисления достаточно выбрать на графике две точки и провести через них прямую. Место, где прямая пересечет вертикальную ось, даст результат умножения. Геометрический прием легко проверить на бумаге, а лежащая в его основе идея приводит к более сложной математике, которую используют в криптографии на эллиптических кривых.
Начать проще всего с конкретного примера. Пусть нужно вычислить (3 \times 4). На параболе (y=x^2) выбираем две точки: ((-3,9)) и ((4,16)). Координата (y) в первой точке равна 9, потому что ((-3)^2=9), во второй равна 16, потому что (4^2=16). Если соединить точки прямой, линия пересечет ось (y) на отметке 12. Получаем привычный результат:
3 \times 4 = 12
Для наглядного опыта параболу можно нарисовать на картоне, поставить небольшие штырьки в точках с целыми координатами и натянуть между нужными точками веревку с грузиками на концах. Практической необходимости в такой конструкции нет: тот же результат дает обычный чертеж на бумаге или интерактивная модель на экране.
Порядок множителей ничего не меняет. Вместо точек ((-3,9)) и ((4,16)) можно взять ((-4,16)) и ((3,9)). Соединяющая их прямая тоже пересечет вертикальную ось при (y=12).
Правило работает не только для 3 и 4. Возьмем произвольные числа (a) и (b). На графике (y=x^2) отметим точки
(-a,a^2)
и
(b,b^2)
Через любые две разные точки проходит прямая. Ее уравнение можно записать в виде
y=mx+c
где (m) задает наклон линии, а (c) равен координате точки пересечения с осью (y). Нужно доказать, что в выбранной конструкции (c=ab).
Подставим координаты первой точки в уравнение прямой:
a^2=-ma+c
Для второй точки получаем:
b^2=mb+c
Двух уравнений достаточно, чтобы определить неизвестные (m) и (c). Из второго уравнения выражаем (m):
m=\frac{b^2-c}{b}
Теперь подставляем полученное выражение в первое:
a^2=\frac{a(c-b^2)}{b}+c
Умножим обе части на (b):
a^2b=ac-ab^2+bc
Перенесем слагаемые и сгруппируем выражение с (c):
a^2b+ab^2=c(a+b)
Левую часть можно вынести за общий множитель:
ab(a+b)=c(a+b)
При (a+b\neq0) сокращение дает
c=ab
Случай (a+b=0) требует отдельной оговорки: тогда выбранные точки ((-a,a^2)) и ((b,b^2)) совпадают, поэтому единственную прямую через них провести нельзя. Для всех остальных пар чисел координата пересечения с осью (y) действительно равна произведению (a) и (b).
Такой геометрический калькулятор работает и с нецелыми числами. Например, можно выбрать дробные координаты, провести прямую и приблизительно определить результат по сетке. Точность быстро упирается в точность самого рисунка: чем сложнее координаты, тем труднее без вычислений поставить точки и считать место пересечения. Поэтому парабола интересна прежде всего как наглядное доказательство связи между геометрией и арифметикой, а не как замена обычному калькулятору.
Похожий принцип, где операции над числами связывают с точками на кривой, встречается в современной криптографии. Криптографам особенно полезны задачи с заметной разницей между прямым и обратным вычислением. Определенную операцию можно выполнить сравнительно быстро, но восстановить исходные данные по полученному результату при достаточно больших параметрах чрезвычайно трудно.
Классический пример дает RSA. Криптосистема опирается на свойства арифметики больших целых чисел и, в частности, на вычислительную сложность факторизации произведения больших простых чисел. Перемножить известные простые числа легко. Найти исходные множители по одному очень большому произведению намного труднее.
Криптография на эллиптических кривых использует другую математическую задачу. Несмотря на название, эллиптическая кривая не имеет формы эллипса. В простейшей записи над вещественными числами семейство таких кривых можно задавать уравнением вида
y^2=x^3+ax+b
при дополнительных условиях, которые исключают особые точки и вырожденные случаи.
С точками на эллиптической кривой можно выполнять строго определенную операцию сложения. Геометрическое объяснение удобно начать с двух точек (P) и (Q). Через них проводят прямую. Обычно прямая пересекает кубическую кривую еще в одной точке. Полученную точку отражают относительно оси (x), после чего получают сумму (P+Q).
Если нужно сложить точку саму с собой, через (P) проводят не прямую через две разные точки, а касательную к кривой. Дальнейший порядок остается тем же: находят еще одно пересечение и отражают его относительно горизонтальной оси. Операцию называют удвоением точки.
Многократное сложение одной точки с самой собой записывают как
Q=kP
где (k) - целое число. Зная (P) и (k), вычислить (Q) можно достаточно эффективно. Обратная задача требует по известным (P) и (Q) определить (k). В криптографии ее называют задачей дискретного логарифмирования на эллиптической кривой.
Реальные криптографические системы выполняют вычисления не на непрерывной плоскости с обычными вещественными координатами. Обычно используют конечные поля, где координаты и арифметические операции подчиняются модульным правилам. Геометрический рисунок помогает понять принцип сложения точек, но практические алгоритмы работают с конечным набором допустимых значений.
При правильно выбранной кривой, размере поля и других параметрах задача дискретного логарифмирования требует огромного объема вычислений. Благодаря этому криптография на эллиптических кривых позволяет использовать ключи меньшего размера, чем RSA при сопоставимом классическом уровне безопасности. Меньший ключ означает меньше данных для хранения и передачи и часто снижает вычислительные затраты.
Связь со школьной параболой здесь не означает, что криптографические алгоритмы напрямую умножают числа с помощью графика (y=x^2). Общий математический принцип другой: точки на кривых можно снабдить правилами, которые превращают геометрию в арифметику. Для параболы прямая между двумя выбранными точками неожиданно выдает произведение на оси (y). Для эллиптических кривых операции над точками дают математическую структуру, на которой строят криптографические алгоритмы.