Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Менезес, Окамото и Ванстоун [197] показали, что для специального класса эллиптических кривых, определенных на конечных полях ?д, существует эффективный алгоритм, отображающий пары, состоящие из точек кривой Е(?д), в невырожденный (т.е. не равный мультипликативной единице) элемент конечного поля ц G F^e. Эти особые кривые называются суперсингулярными (supersingular curves). Эти кривые удовлетворяют следующему условию: число t из уравнения (5.5.6) является кратным характеристике поля ?д (мы ограничимся рассмотрением характеристик поля, превышающих число 3).
В таком случае (когда число t из уравнения (5.5.6) является кратным характеристике поля ?д) для некоторого большого простого числа а | #Е(?д) кривая, определенная на расширении поля ?д, т.е. Е (F^e), содержит много точек порядка а, т.е. точек Р, удовлетворяющих условию [а]Р = О (см. раздел 5.5). Группа Е (?де) является нециклической, и, следовательно, многие из этих точек порядка а являются линейно-зависимыми. Точки Р uQ, имеющие простой порядок а, называются линейно независимыми, если Р ф [a]Q и Q ф [Ь]Р для любых целых чисел а и Ъ. (Иначе говоря, Р ? (Q) и Q ? (Р).) Для данного простого числа а расширение поля IFQe имеет единственную подгруппу порядка а (поскольку группа F*c является циклической (см. теорему 5.2)).
Менезес, Окамото и Ванстоун [197] показали, что подгруппа поля Е(?де) и подгруппа расширения поля F^e, имеющие одинаковый порядок а, являются изоморфными. Более того, расширение поля является небольшим: ? ^ 6! Этот факт очень важен! Мы вернемся к нему чуть позже.
Изоморфизм, использованный Менезесом, Окамото и Ванстоуном, называется спариванием Вейля (Weil pairing). В соответствие двум точкам подгруппы поля Е {?де) порядка а этот изоморфизм ставит элемент расширения поля F^e. Поскольку это отображение является изоморфизмом между двумя группами порядка а, одну из отображаемых точек, образующих пару, можно считать фиксированной константой, а вторую — переменной. Пусть X (Е Е (F9«) точка фиксированного порядка а (фиксированная константа). Спаривание Вейля обозначается как
ex(P,Q),
где либо Р е (X), либо Q G (X). Число ех{Р, Q) является корнем единицы с номером а, т.е. элементом порядка а поля ?д(, тогда и только тогда, когда числа
Глава 13. Аутентификация в криптографии с открытым ключом
495
Р и Q имеют простой порядок а и являются линейно независимыми (например, либо Р е (X), либо Q е (X)).
Обозначим через G\ подгруппу порядка а поля Е элементы которой
(кроме элемента О) являются линейно независимыми от "фиксированной константы X порядка а". (Такая подгруппа существует, если группа Е (?де) не является циклической и, следовательно, суперсингулярной.) Через G2 = (ех(Р,Х)) обозначим подгруппу порядка а поля Fg?, порожденную элементом ех(Р, X). Теперь нам известно, что #Gi = #G2 = Эти две подгруппы изоморфны относительно спаривания Вейля. Обратите внимание на то, что даже если группа G\ является аддитивной группой точек эллиптической кривой, а группа G2 — мультипликативной подгруппой конечного поля, с точки зрения изоморфизма между ними нет существенной разницы.
Спаривание Вейля обладает следующими свойствами.
Свойство 13.1 (Свойства спаривания Вейля). Пусть (G\, +) и (G2, •) —две изоморфные абелевы группы простого порядка относительно спаривания Вейля ех. Спаривание обладает следующими свойствами.
Тождественность. Для всех Р € G\
ех(Р,Р) = 1с2-
Билинейность. Для всех P,QeGi
ех(Р + Q,R) = ех(Р, R)ex(Q, Я), е*(Я Р + Q) = ex(R, P)ex(R, Q).
Невырожденность. Для всех Р € G\, таких что Р Ф О (поскольку точки Р и X являются линейно независимыми)
ех(Р,Х)ф1С2,ех(Х,Р)ф1с2.
Практическая эффективность. Для всех Р € G\ и Я € (X), числа ех(Р, Я) и ex{R, Р) допускают эффективное вычисление.
Из билинейности следует, что
ех([п]Р,Х) = ех(Р,Х)п = ех(Р, [п]Х).
Из свойства невырожденности и условия а\п следует, что результатом спаривания не может быть единица группы G2.
Благодаря свойствам спаривания Вейля задача дискретного логарифмирования на эллиптической кривой (задача ECDLP, описанная в разделе 5.5.3) значительно упрощается и сводится к задаче вычисления дискретного логарифма в конечном поле (MOV reduction). Для того чтобы свести задачу ECDLP к задаче вычисления
496
Часть IV. Аутентификация
дискретного логарифма в конечном поле, используя пару точек (Р, [п]Р), можно вычислить пары Вейля ? = ех{Р,Х) и т] = ех{[п]Р,Х) и учесть, что
V = ех([п]Р,Х) = ех(Р,Х)п = f. (13.3.3)'
Следовательно, пара точек (?, 77) из группы G2 образует задачу дискретного логарифмирования в мультипликативной группе G%, а значит, в конечном поле ?де. Для этой задачи существует субэкспоненциальный алгоритм решения, сложность которого задается выражением sub_exp(g*). Напомним, что ? < 6. Таким образом, достигается существенное уменьшение сложности: широко известная экспоненциальная задача О (\/с7) « О (^/q) сводится к субэкспоненциальной: sub_exp (</*), где ? < 6.
По мере развития компьютерной техники число q должно увеличиваться. Одновременно с ним должны увеличиваться параметры суперсингулярной кривой и размер конечного поля. Иначе говоря, преимущества эллиптических кривых в криптографии становятся все менее весомыми. После появления работы Мене-зеса, Окамото и Ванстоуна [197] стало общепризнанным, что суперсингулярные эллиптические кривые являются слабыми и не должны использоваться в криптографии.
