Алгоритм Монтгомери (эллиптические кривые)

Алгоритм Монтгомери(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой за конечное время.

Недостатки предыдущих алгоритмов

Простейший алгоритм скалярного умножения точки $P$, лежащей на эллиптической кривой, на скаляр $k$ выглядит следующим образом:

Input: k, P
Output: kP

1: Q = P
2: for i = n-2 down to 0:
3:     Q = 2Q
4:     if k[i] == 1:
5:         Q = Q + P
6: return Q

Описанный выше алгоритм скалярного умножения не рекомендуется использовать при построении криптосистем на эллиптических кривых, поскольку он подвержен атаке по энергопотреблению. Шаги 3: и 5: позволяют злоумышленнику, перехватывающему значения $Q$ на очередной итерации цикла, побитово восстановить значение секретного ключа $k$.

Аналогичным проблемам подвержены более сложные алгоритмы скалярного умножения, использующие $y$-координату, поскольку к ним описан алгоритм атаки по ошибкам вычисления, а именно атака смены знака.

Описание алгоритма

В 1987 году американский математик Питер Монтгомери предложил алгоритм, в котором не требуется использование $y$-координаты для вычисления скалярного произведения точки на эллиптической кривой, что позволило значительно ускорить создание открытого ключа, а также полностью защититься от атак по энергопотреблению:

Input: k, P
Output: kP

1: Q[0] = P, Q[1] = 2P
2: for i = k-2 down to 0:
3:     Q[1 - k[i]] = Q[0] + Q[1]
4:     Q[k[i]] = 2Q[k[i]]
5: return Q[0]

Предлагается в самом начале помимо точки $Q_0=P$ рассчитывать также точку $Q_1=2P$. Основная идея заключается в том, что во время очередной итерации цикла разница между точками $Q_0$ и $Q_1$ остаётся неизменно равной $P$. Это позволяет при помощи проективных координат быстро вычислять значение в точках $(X_{Q_0+Q_1}:.:Z_{Q_0+Q_1})$ и $(X_{2Q_0}:.:Z_{2Q_0})$, с помощью которых обновляются значения $Q_0$ и $Q_1$. В самом же конце используя $(X_{kP}:.:Z_{kP})$ вычисляется значение открытого ключа $kP$.

В дальнейшем оказалось, что главная особенность алгоритма оказалась слабым местом, дающим возможность для атаки и расшифровки секретного ключа.

Особенность реализации

Подсчёт $Q_0$ и $Q_1$ на очередном шаге алгоритма заслуживает отдельного внимания. Поскольку Монтгомери отказывается от использования $y$-координаты необходимо иметь точный порядок действий для вычисления проективных координат на очередной итерации.

В статье приводится полное подробное описание вычисления проективных координат, получающихся удвоением и суммированием соответствующих значений. Всего требуется 18 операций умножения, 13 сложения и 4 возведения в квадрат для случая $A\ne -3$, и, соответственно, 23 умножения, 11 сложения и 4 возведения в квадрат иначе.

Области применения

Алгоритм Монтгомери применяется как в протоколе Диффи-Хэлмана, так и в алгоритмах электронной подписи, в случае, когда оба строятся на эллиптической кривой (ECDH и ECDSA соответственно). В обоих случаях — это вычисление открытых ключей агентов, собирающихся обмениваться информацией по незащищённому каналу.

Основным преимуществом криптосистемы, использующей эллиптические кривые, является относительно небольшая длина закрытого ключа (минимум 163 бита). Для примера в алгоритме RSA минимальная длина секретного ключа составляет 1024 бит. Данная возможность появляется благодаря особенности вычисления открытого ключа, задача дискретного логарифмирования для которого решается намного сложнее, чем для алгоритмов, построенных на целых числах.

RFID метки

На практике алгоритм Монтгомери применяется в RFID метках. Данные устройства применяются повсеместно для автоматической идентификации объектов, но при этом оснащены сильно ограниченным количеством памяти. Также процесс считывания должен происходить быстро, например в момент оплаты или проверки автомобиля во время проезда через пропускной пункт. Здесь и помогает алгоритм Монтгомери, поскольку он эффективнее других алгоритмов с точки зрения аппаратной части (время, ресурсы), а также даёт защиту от большинства атак по сторонним каналам на эллиптические кривые

Сенсорные сети

Другим интересным применением данного алгоритма являются беспроводные сенсорные сети. Как и в случае RFID меток, устройства сети оснащены компактными энергетически эффективными процессорами, в которых спроектированы специальные Modular Arithmetic Logic Units(MALU) для проведения вычислений на кривой, в том числе скалярного умножения. Это помогает производить безопасные и экономные вычисления.