EducationBot: Новая страница: «{{Русская Википедия/Панель перехода}} '''Алгоритм Монтгомери'''(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой...»

2023-07-19T07:49:05Z

Новая страница: «{{Русская Википедия/Панель перехода}} '''Алгоритм Монтгомери'''(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой...»

Новая страница

{{Русская Википедия/Панель перехода}}
'''Алгоритм Монтгомери'''([[Английский язык|англ.]] Montgomery ladder) — это [[алгоритм]], позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей [[Эллиптическая кривая|эллиптической кривой]] за конечное время<ref name="автоссылка1">{{статья
|заглавие=Speeding the Pollard and elliptic curve methods of factorization
|doi=10.1090/s0025-5718-1987-0866113-7
|язык=en
|тип=journal
|автор=Montgomery, P.
|год=1987
}}
</ref>.

=== Недостатки предыдущих алгоритмов ===
Простейший [[алгоритм]] скалярного умножения точки <math>P</math>, лежащей на [[Эллиптическая кривая|эллиптической кривой]], на [[скаляр]] <math>k</math> выглядит следующим образом<ref>
{{статья
|заглавие=High-Performance Architecture of Elliptic Curve Scalar Multiplication
|издание={{Нп3|IEEE Transactions on Computers}}
|том=57
|страницы=1443—1453
|doi=10.1109/TC.2008.133
|язык=en
|тип=journal
|автор=Ansari, B.; Hasan, M.
|год=2008
}}</ref><ref>{{статья
|заглавие=A High Speed Coprocessor for Elliptic Curve Scalar Multiplications over 𝔽𝑝
|издание=International Workshop on Cryptographic Hardware and Embedded Systems.
|страницы=48—64
|doi=10.1007/978-3-642-15031-9_4
|язык=en
|тип=journal
|автор=Guillermin, N.
|год=2010
}}</ref>:

<syntaxhighlight>
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
</syntaxhighlight>

Описанный выше [[алгоритм]] скалярного умножения не рекомендуется использовать при проторении [[Криптосистема|криптосистем]] на [[Эллиптическая кривая|эллиптических кривых]], поскольку он подвержен [[Атака по энергопотреблению|атаке по энергопотреблению]]<ref>{{статья
|заглавие=Differential Power Analysis
|издание=Advances in Cryptology — CRYPTO’ 99
|том=1666
|страницы=388—397
|doi=10.1007/3-540-48405-1_25
|язык=und
|автор=Kocher, P.; Jaffe, J.; Jun, B.
|год=1999
}}</ref>. Шаги <code>3:</code> и <code>5:</code> позволяют злоумышленнику, перехватывающему значения <math>Q</math> на очередной итерации цикла, побитово восстановить значение [[Ключ (криптография)|секретного ключа]] <math>k</math><ref>
{{статья
|заглавие=New Fault Attack on Elliptic Curve Scalar Multiplication
|язык=en
|тип=journal
|издание=IACR Cryptology ePrint Archive 2009
|автор=Chilikov, A; Taraskin, O.
|год=2009
}}</ref>.

Аналогичным проблемам подвержены более сложные [[алгоритм]]ы скалярного умножения, использующие <math>y</math>-[[Система координат|координату]], поскольку к ним описан алгоритм [[Атака по сторонним каналам|атаки по ошибкам вычисления]], а именно атака смены знака<ref>{{статья
|заглавие=Sign change fault attacks on elliptic curve cryptosystems
|издание=International Workshop on Fault Diagnosis and Tolerance in Cryptography
|том=4236
|страницы=36—52
|doi=10.1007/11889700_4
|язык=en
|тип=journal
|автор=Blömer, J.; Otto, M.; Seifert, J.
|год=2006
}}
</ref>.

=== Описание алгоритма ===
В 1987 году американский математик [[Монтгомери, Питер|Питер Монтгомери]] предложил [[алгоритм]]<ref name="автоссылка1" />, в котором не требуется использование <math>y</math>-[[Система координат|координату]] для вычисления скалярного произведения точки на эллиптической кривой, что позволило значительно ускорить создание [[Криптосистема с открытым ключом|открытого ключа]], а также полностью [[Информационная безопасность|защититься]] от атак по энергопотреблению:
<syntaxhighlight>
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]
</syntaxhighlight>

Предлагается в самом начале помимо точки <math>Q_0 = P</math> рассчитывать также точку <math>Q_1 = 2P</math>. Основная идея заключается в том, что во время очередной [[Итерация|итерации]] [[Цикл (программирование)|цикла]] разница между точками <math>Q_0</math> и <math>Q_1</math> остаётся неизменно равной <math>P</math>. Это позволяет при помощи [[Эллиптическая криптография#Проективные координаты|проективных координат]]<ref>{{статья
|заглавие=Efficient Elliptic Curve Exponentiation Using Mixed Coordinates
|издание=Advances in Cryptology — ASIACRYPT’98
|том=1514
|страницы=51—65
|doi=10.1007/3-540-49649-1_6
|язык=en
|тип=journal
|автор=Cohen, H.; Miyaji, A.
|год=1998
}}</ref> быстро вычислять значение в точках <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>.

В дальнейшем оказалось, что главная особенность [[алгоритм]]а оказалась слабым местом, дающим возможность для [[Атака по ошибкам вычислений на эллиптические кривые, использующие алгоритм Монтгомери|атаки]] и расшифровки секретного ключа<ref>
{{статья
|заглавие=Fault attack on elliptic curve Montgomery ladder implementation
|издание=2008 5th Workshop on Fault Diagnosis and Tolerance in Cryptography
|страницы=92—98
|doi=10.1109/FDTC.2008.15
|язык=en
|тип=journal
|автор=Fouque, P.; Lercier, R.; Réal, D.; Valette, F.
|год=2008
}}</ref>.

=== Особенность реализации ===
Подсчёт <math>Q_0</math> и <math>Q_1</math> на очередном шаге [[алгоритм]]а заслуживает отдельного внимания. Поскольку [[Монтгомери, Питер|Монтгомери]] отказывается от использования <math>y</math>-координаты<ref>
{{статья
|заглавие=Speeding the Pollard and elliptic curve methods of factorization
|doi=10.1090/s0025-5718-1987-0866113-7
|язык=en
|тип=journal
|автор=Montgomery, P.
|год=1987
}}
</ref> необходимо иметь точный порядок действий для вычисления [[Эллиптическая криптография#Проективные координаты|проективных координат]] на очередной итерации.

В статье <ref>{{статья
|заглавие=Improved Elliptic Curve Multiplication Methods Resistant against Side Channel Attacks
|издание=Progress in Cryptology — INDOCRYPT 2002
|том=2551
|страницы=296—313
|doi=10.1007/3-540-36231-2_24
|язык=en
|тип=journal
|автор=Izu, T.; Möller, B.; Takagi, T.
|год=2002
}}</ref>
приводится полное подробное описание вычисления [[Эллиптическая криптография#Проективные координаты|проективных координат]], получающихся удвоением и суммированием соответствующих значений. Всего требуется 18 операций [[Умножение|умножения]], 13 [[Сумма (математика)|сложения]] и 4 [[Возведение в степень|возведения]] в квадрат для случая <math>A \ne -3</math>, и, соответственно, 23 [[Умножение|умножения]], 11 [[Сумма (математика)|сложения]] и 4 [[Возведение в степень|возведения]] в квадрат иначе.

=== Области применения ===
[[Алгоритм]] [[Монтгомери, Питер|Монтгомери]] применяется как в протоколе [[Протокол Диффи — Хеллмана|Диффи-Хэлмана]], так и в [[алгоритм]]ах [[Электронная подпись|электронной подписи]], в случае, когда оба строятся на [[Эллиптическая кривая|эллиптической кривой]] ([[Протокол Диффи — Хеллмана на эллиптических кривых|ECDH]] и [[ECDSA]] соответственно). В обоих случаях — это вычисление открытых ключей [[Алиса и Боб|агентов]], собирающихся обмениваться информацией по незащищённому [[Канал связи|каналу]]<ref>{{статья
|заглавие=Diffie-Hellman Key Distribution Extended to Group Communication
|страницы=31—37
|язык=en
|тип=journal
|автор=Steiner, M.; Tsudik, G.; Waidner, M.
|год=1996
}}</ref>.

Основным преимуществом криптосистемы, использующей [[Эллиптическая кривая|эллиптические кривые]], является относительно небольшая длина закрытого [[Ключ (криптография)|ключа]] (минимум 163 бита). Для [[Ключ (криптография)#Длина ключа|примера]] в [[алгоритм]]е [[RSA]] минимальная длина секретного [[Ключ (криптография)|ключа]] составляет 1024 бит<ref>
{{книга
|заглавие=The RSA security's official guide to cryptography
|год=2001
|isbn=0072194049
|ref=Burnett
|язык=en
|автор=Burnett, S.
}}
</ref>. Данная возможность появляется благодаря особенности вычисления открытого [[Ключ (криптография)|ключа]], задача [[Дискретное логарифмирование|дискретного логарифмирования]] для которого решается намного [[Вычислительная сложность|сложнее]], чем для [[алгоритм]]ов, построенных на [[Целое число|целых числах]]<ref>{{статья
|заглавие=Visual Cryptography
|издание=Advances in Cryptology — EUROCRYPT'94
|страницы=1—12
|doi=10.1007/BFb0053419
|язык=und
|автор=Naor, M.; Shamir, A.
|год=1994
}}</ref>.

==== RFID метки ====
На практике [[алгоритм]] [[Монтгомери, Питер|Монтгомери]] применяется в [[RFID|RFID метках]]<ref>{{статья
|заглавие=Public-key cryptography for RFID-tags
|издание=Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops (PerComW'07)
|страницы=217—222
|doi=10.1109/PERCOMW.2007.98
|язык=und
|автор=Batina, L.; Guajardo, J.; Kerins, T.
|год=2007
}}</ref>. Данные устройства применяются повсеместно для автоматической [[Идентификация (информационные системы)|идентификации]] объектов, но при этом оснащены сильно ограниченным количеством [[Компьютерная память|памяти]]<ref>{{статья
|заглавие=An introduction to RFID technology
|издание=IEEE pervasive computing
|язык=und
|автор=Want R.
|год=2006
}}</ref>. Также процесс считывания должен происходить быстро, например в момент оплаты или проверки автомобиля во время проезда через пропускной пункт<ref>{{статья
|заглавие=RFID technology and applications
|издание=IEEE pervasive computing
|язык=und
|автор=Nath B., Reynolds F., Want R.
|год=2006
}}</ref>. Здесь и помогает [[алгоритм]] [[Монтгомери, Питер|Монтгомери]], поскольку он [[Эффективность алгоритма|эффективнее]] других [[алгоритм]]ов с точки зрения аппаратной части (время, ресурсы), а также даёт защиту от большинства атак по сторонним каналам на [[Эллиптическая кривая|эллиптические кривые]]

==== Сенсорные сети ====
Другим интересным применением данного [[алгоритм]]а являются [[Беспроводная сенсорная сеть|беспроводные сенсорные сети]]<ref>{{статья
|заглавие=A survey on sensor networks
|издание=IEEE Communications magazine
|язык=und
|автор=Akyildiz I. F. et al.
|год=2002
}}</ref>. Как и в случае RFID меток, устройства сети оснащены компактными энергетически эффективными [[процессор]]ами, в которых спроектированы специальные Modular Arithmetic Logic Units(MALU) для проведения вычислений на [[Эллиптическая кривая|кривой]], в том числе скалярного умножения. Это помогает производить безопасные и экономные вычисления<ref>{{статья
|заглавие=Low-Cost Elliptic Curve Cryptography for Wireless Sensor Networks
|издание=Security and Privacy in Ad-Hoc and Sensor Networks. ESAS 2006
|том=4357
|страницы=6—17
|doi=10.1007/11964254_3
|язык=en
|тип=journal
|автор=Batina, L.; Mentens, N.; Sakiyama, K.
|год=2006
}}</ref>.

== Примечания ==
{{примечания}}

[[Категория:Эллиптические кривые]]

[[en:Montgomery ladder]]
{{Навигационная таблица/Портал/Русская Википедия}}
[[Категория:Русская Википедия]]
[[Категория:Википедия]]
[[Категория:Статья из Википедии]]
[[Категория:Статья из Русской Википедии]]

Русская Википедия:Алгоритм Монтгомери (эллиптические кривые) - История изменений