Русская Википедия:Алгоритм Монтгомери (эллиптические кривые)
Алгоритм Монтгомери(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой за конечное время[1].
Недостатки предыдущих алгоритмов
Простейший алгоритм скалярного умножения точки <math>P</math>, лежащей на эллиптической кривой, на скаляр <math>k</math> выглядит следующим образом[2][3]:
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Описанный выше алгоритм скалярного умножения не рекомендуется использовать при проторении криптосистем на эллиптических кривых, поскольку он подвержен атаке по энергопотреблению[4]. Шаги 3: и 5: позволяют злоумышленнику, перехватывающему значения <math>Q</math> на очередной итерации цикла, побитово восстановить значение секретного ключа <math>k</math>[5].
Аналогичным проблемам подвержены более сложные алгоритмы скалярного умножения, использующие <math>y</math>-координату, поскольку к ним описан алгоритм атаки по ошибкам вычисления, а именно атака смены знака[6].
Описание алгоритма
В 1987 году американский математик Питер Монтгомери предложил алгоритм[1], в котором не требуется использование <math>y</math>-координату для вычисления скалярного произведения точки на эллиптической кривой, что позволило значительно ускорить создание открытого ключа, а также полностью защититься от атак по энергопотреблению:
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]Предлагается в самом начале помимо точки <math>Q_0 = P</math> рассчитывать также точку <math>Q_1 = 2P</math>. Основная идея заключается в том, что во время очередной итерации цикла разница между точками <math>Q_0</math> и <math>Q_1</math> остаётся неизменно равной <math>P</math>. Это позволяет при помощи проективных координат[7] быстро вычислять значение в точках <math>(X_{Q_0 + Q_1} : \;.\; : Z_{Q_0 + Q_1})</math> и <math>(X_{2Q_0} : \;.\; : Z_{2Q_0})</math>, с помощью которых обновляются значения <math>Q_0</math> и <math>Q_1</math>. В самом же конце используя <math>(X_{kP} : \;.\; : Z_{kP})</math> вычисляется значение открытого ключа <math>kP</math>.
В дальнейшем оказалось, что главная особенность алгоритма оказалась слабым местом, дающим возможность для атаки и расшифровки секретного ключа[8].
Особенность реализации
Подсчёт <math>Q_0</math> и <math>Q_1</math> на очередном шаге алгоритма заслуживает отдельного внимания. Поскольку Монтгомери отказывается от использования <math>y</math>-координаты[9] необходимо иметь точный порядок действий для вычисления проективных координат на очередной итерации.
В статье [10] приводится полное подробное описание вычисления проективных координат, получающихся удвоением и суммированием соответствующих значений. Всего требуется 18 операций умножения, 13 сложения и 4 возведения в квадрат для случая <math>A \ne -3</math>, и, соответственно, 23 умножения, 11 сложения и 4 возведения в квадрат иначе.
Области применения
Алгоритм Монтгомери применяется как в протоколе Диффи-Хэлмана, так и в алгоритмах электронной подписи, в случае, когда оба строятся на эллиптической кривой (ECDH и ECDSA соответственно). В обоих случаях — это вычисление открытых ключей агентов, собирающихся обмениваться информацией по незащищённому каналу[11].
Основным преимуществом криптосистемы, использующей эллиптические кривые, является относительно небольшая длина закрытого ключа (минимум 163 бита). Для примера в алгоритме RSA минимальная длина секретного ключа составляет 1024 бит[12]. Данная возможность появляется благодаря особенности вычисления открытого ключа, задача дискретного логарифмирования для которого решается намного сложнее, чем для алгоритмов, построенных на целых числах[13].
RFID метки
На практике алгоритм Монтгомери применяется в RFID метках[14]. Данные устройства применяются повсеместно для автоматической идентификации объектов, но при этом оснащены сильно ограниченным количеством памяти[15]. Также процесс считывания должен происходить быстро, например в момент оплаты или проверки автомобиля во время проезда через пропускной пункт[16]. Здесь и помогает алгоритм Монтгомери, поскольку он эффективнее других алгоритмов с точки зрения аппаратной части (время, ресурсы), а также даёт защиту от большинства атак по сторонним каналам на эллиптические кривые
Сенсорные сети
Другим интересным применением данного алгоритма являются беспроводные сенсорные сети[17]. Как и в случае RFID меток, устройства сети оснащены компактными энергетически эффективными процессорами, в которых спроектированы специальные Modular Arithmetic Logic Units(MALU) для проведения вычислений на кривой, в том числе скалярного умножения. Это помогает производить безопасные и экономные вычисления[18].
Примечания
