Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
Почему в заглавии раздела термин "слабые" взят в кавычки? Недавно было открыто новое полезное свойство суперсингулярных эллиптических кривых, шокировавшее научное сообщество. Однако для начала опишем задачу принятия решений Диффи-Хеллмана.
13.3.4.2 Задача принятия решений Диффи-Хеллмана
В определении 8.1 (раздел 8.4) была сформулирована вычислительная задача Диффи-Хеллмана (CDH problem — computational Diffie-Hellman problem). Ее вариант, касающийся принятия решений, описывается следующим определением.
Определение 13.1 (Задача принятия решений Диффи-Хеллмана (задача DDH)).
ВВОД desc(G): описание абелевой группы G;
(9i9a,9b,9c) ? G4, где д — порождающий элемент группы G. ВЫВОД ДА, если oh = c(mod #G).
Задача принятия решений Диффи-Хеллмана не может быть сложнее, чем ее вычислительный аналог. Если существует алгоритм решения вычислительной задачи Диффи-Хеллмана (т.е. некий оракул, решающий эту задачу), то, получив четверку (д, да, <Д дс), он по первым трем элементам может найти число раЬ и ответ к задаче CDH, проверив, равен ли результат вычисления числу дс.
Однако в общем случае никакие другие зависимости между этими двумя задачами не известны. Более того, до сих пор нет ни одного алгоритма решения задачи
Глава 13. Аутентификация в криптографии с открытым ключом
497
DDH. Трудность решения задачи DDH общепризнанна, а сама задача стала образцом неразрешимой проблемы и лежит в основе многих криптографических систем [20, 58, 84, 209, 283].
Для специального случая суперсингулярных эллиптических кривых недавно был открыт следующий факт: задача DDH является легко разрешимой. Это доказали Жё и Нгуен [155]. Чтобы объяснить этот факт, необходимо сначала представить задачи DDH, CDH и DL в аддитивном виде, поскольку группы точек эллиптической кривой являются аддитивными.
Задача дискретного логарифмирования (DL) в группе (g, +)
ВВОД Два элемента P,QeG, где Р — порождающий элемент группы.
ВЫВОД Целое число а, удовлетворяющее условию Q = аР.
Вычислительная задача Диффи-Хеллмана (CDH) в группе (g, +)
ВВОД Три элемента Р, аР, ЬР € g, где Р — порождающий элемент группы.
ВЫВОД Элемент {qb)P € g.
Задача принятия решения Диффи-Хеллмана (DDH) в группе (g, +)
ВВОД Четыре элемента Р, аР, ЬР, сР € g, где Р — порождающий элемент группы.
ВЫВОД ДА, тогда и только тогда, когда с = ab(mod #g).
13.3.4.3 "Слабые" кривые, допускающие простое решение задачи принятия решений Диффи-Хеллмана
Свойство тождественности спаривания Вейля (свойство 13.1) является довольно неудобным. Оно означает, что для точек P,Q eg\ (а также точки Q = [а]Р, где а — некоторое целое число) спаривание приводит к следующему результа-ТУ: ex(P,Q) = &х{Р,Р) = la = 1- Для того чтобы отображение не приводило к вырожденному результату, необходимо найти другую точку X порядка а, линейно независимую от элементов группы g\. Это сильное ограничение, не позволяющее непосредственно применять спаривание Вейля в криптографических приложениях.
Ферхойль (Verheul) [296] разработал метод, который он назвал "деформирующим отображением" координат точек, лежащих на кривой. Отображение выполняется в поле ?д и обозначается через F(P). Если точка Р лежит в поле Е(?де), точка ?(Р) остается в поле Е(?де) того же порядка (кручения), поскольку порядок точки Р превышает число 3. Еще более важно то, что точки Р и ?(Р) являются линейно независимыми. При деформирующем отображении спаривание Вейля приобретает следующий вид.
е(Р,Р) = ех(Р,?(Р)).
498
Часть IV. Аутентификации
Очевидно, что е(Р, Р) ф 1, поскольку точки Р и F(P) линейно независимы^ Более того, для точек P,QgG\ спаривание Вейля обладает следующим свойством симметрии.
Рассмотрим теперь задачу DDH в группе G\. Для того чтобы определить, яв-« ляется ли четверка (Р, [а]Р, [Ь]Р, [с]Р) четверкой задачи DDH, вычислим функций) спаривания: ? = е(Р, [с]Р) ит/ = е([а]Р, [Ь]Р). Учитывая, что
и е(Р, Р) ф 1, получаем, что указанная четверка описывает задачу DH тогдя и только тогда, когда ? = -ц, т.е. если и только если ab = c(mod#Gi). Поскольку! функция спаривания Вейля допускает эффективное вычисление, задача принятия решений становится легкоразрешимой.
Это важное наблюдение, сделанное Жё и Нгуеном [155], расширило возмож-1 ности применения суперсингулярных эллиптических кривых в криптографии. Од! ним из таких приложений стала личностная криптография. Она основана на свой-1 ствах суперсингулярных кривых и предположении о неразрешимости вычисли! тельной задачи Диффи-Хеллмана и задачи о вычислении дискретного логарифма!
Факт (задача DDH является легкоразрешимой)
Задачу DDH в группах точек суперсингулярных кривых можно эффективна решить с помощью алгоритма спаривания Вейля.
Предположение (задачи CDH и DL остаются трудноразрешимыми)
При правильном выборе размера эллиптической кривой задача CDH (а зна-J чит, и задача DL) в группах точек суперсингулярной кривой является трудно! разрешимой. Для кривой Е (?Qe) сложность задается выражением sub_exp (</*), где ? ^ 6.
Предположение о том, что "задачи CDH и DL остаются трудноразрешимы-] ми" содержит оценку сложности решения задачи для кривой Е {?де). Эта оценк! следует из возможности упрощения задачи дискретного логарифмирования и су-1 ществования субэкспоненциального алгоритма решения задачи о вычислении дис-1 кретного логарифма в конечных полях. Таким образом, по сравнению с обычными эллиптическими кривыми при работе с суперсингулярными кривыми необходи-J мо выбирать большой параметр безопасности (размер кривой). Этот параметр] должен быть настолько большим, чтобы величина sub_exp(<7f) была практически недостижимой. Итак, для того, чтобы получить возможность применять недав-] но открытое свойство суперсингулярных эллиптических кривых в криптографии (см. разделы 13.3.5-13.3.7), необходимо пожертвовать эффективностью, которая присуща эллиптическим кривым, определенным в конечных полях.
