Алгоритмические основы эллиптической криптографии

ссылки мёртвые, если есть у кого перезалейте плз. Было бы интересно почитать.

 

kyprizel насколько я помню дело все вот в чем(простите за много букафф, как и просили на пальцах и с примером)
Как известно задача дискретного логарифма в группе целых числе имеет т.н. субэкспоненциальный алгоритм решения. По сути означает это следующее зависимость сложности решения задачи о дискретном логарифме зависит нелинейно от роста размера поля. И рост сложности решения гораздо медленее роста размера поля. Именно этим объясняются такие большие размеры простых чисел в асимметричных криптосистемах.

Но это качается только групп целых чисел. Что же касается эллиптических кривых то для них субэкспоненциального алгоритма решения дискретного логарифма в группе точек не известно. Т.е. рост сложности такой же как и рост размера поля. Поэтому то в эллиптической криптографии можно обойтись гораздо меньшими размерами. Но дело все в том что для суперсингулярных эллиптических кривых существует метод, который называется спариванием Вейла, позволяющий преобразовывать (грубо говоря) точки эллиптической кривой в элементы поля целых чисел. При этом размер полученного поля имеет схожие размеры с исходным полем точек эллиптической кривой. Получается что размер поля относительно невелик, а субэкспоненциальные алгоритмы применить на нем можно. И все это приводит к тому что возникает возможность атаки грубой силой на эллиптическую криптосистему использующую суперсингулярные кривые.

Теперь пример. Допустим вы используете обычную схему DSA над полем целых чисел с размером ключа 1024 бита. Чтобы взломать эту систему субэкспоненциальным методом требуется примерно 2^86 операций.
Теперь представьте что используете ECDSA с ключом размером 160 бит. Для взлома ключа потребуется 2^80(с учетом атаки дней рождений) что примерно сопоставимо с 2^86 из первого случая.
Но в случае если используется суперсингулярная кривая с тем же размером 160 бит, то с помощью спаривания Вейля можно преобразовать ее в поле целых числе размером не более 960 бит(но вероятнее всего меньше). Для поля такого размера субэкспоненциальный алгоритм даст 2^62(в самом неблагоприятном для нападающего случае) операций для взлома грубой силой(вместо обещанных 2^80).

И кстати это глупость что суперсингулярные кривые не подходят для криптографических целей. Очень даже подходят правда для очень специфических целей Они используются в неинтерактивных криптосистемах для обмена ключами. Об этом в частности можно почитать в книге Венбо Мао-современная криптография.

CreatorCray в свое время отсюда качал http://www.infanata.org/science/exact/1146098296-jelementarnoe-vvedenie-v-jellipticheskuju.html. Правда зарегиться нужно.

 

Sharkey
Пасиб, но меня Elliptic Curves: Number Theory and Cryptography, 2nd Edition и Handbook of Elliptic and Hyperelliptic Curve Cryptography интересуют.

 

CreatorCray вот чего нет того нет. Но тоже бы с удовольствием почитал. Присоединяюсь к просьбе, если у кого есть залейте пожалуйста.

 

вы про это?
Elliptic Curves: Number Theory and Cryptography
Автор: Lawrence C. Washington
Год издания: 2008
Издат.: Chapman & Hall/CRC

 

http://ifolder.ru/20177593

 

korbian класс, большое человеческое спасибо.)

 

всеже сингулярная кривая != суперсингулярная
но принцип примерно понятен, спасибо за разъяснение.

 

Sharkey
Hyperelliptic нашёл: http://rapidshare.com/files/429763368/HB_HECC.rar

 

kyprizel да уж опозорился. Но слово уж больно красивое "суперсингулярность", не мог сдержаться
CreatorCray спасибо за ссылку.

 

Может у кого-нибудь есть данная книженция?
Бессалов А.В., Телиженко А.Б. Криптосистемы на эллиптических кривых : Учеб. Пособие. – К.: ІВЦ „Видавництво „Політехніка””, 2004. – 224с.
А то покупать не хочется)