Криптография
учено -
( ) /r. Наиболее существенно, алгоритмы " типа показателя степени " не
являются известными из-за ECDLP ,что касается процессора передачи данных.
По этой причине, ECDLP является намного тяжелее или чем IFP или процессор
передачи данных .
В 1991 Menezes, Okamoto и Vanstone (MOV) показал, как ECDLP может быть
сокращен к процессу перпдачи данных в полях Fq, где могут применяться
методы конкремента индекса. Однако, этот MOV алгоритм приведения эффективен
только для очень специальной категории кривых ,известных как
суперсингулярные кривые. Имеется простое испытание, чтобы гарантировать,
что эллиптическая кривая не уязвима к этому разложению. Суперсингулярные
кривые специально запрещены во всех стандартах эллиптических систем кривой
типа ИИЭРА P1363, ANSI X9.62, и ANSI X9.63.
Другой жидкий класс эллиптических кривых - так называемые аномальные
кривые - кривые E определенные по Fq, которые имеют точно q точки.
Разложение на этих кривых было обнаружено Semaev, Smart, и Satoh и Araki ,
и обобщено Rьck. Имеется простое испытание над суперсингулярными кривыми
для того чтобы гарантировать, что эллиптическая кривая не уязвима; через
это испытание, эти кривые специально запрещены во всех стандартах
эллиптических систем кривой.
3.3.3. Программные разложения фунции на множетели
Криптографический алгоритм RSA использует только один тип
вычислений – возведение в степень . Показатель степени определяет
длительность выполнения процедуры вычеслений. Чтобы обеспечить требуемый
уровень надежности , показатель степени, являющийся секретным ключом ,
должен быть достаточно большим , поэтому для вычислений требуется много
времени.
Производительность вычислительных устройств с недавнего
времени принято оценивать в MIPS ( Million Instruction Per Second):
1MIPS=10^6 опер./с.
MIPS года – такая сложность алгоритма, которая требует годовой
работы компьютера чтобы его вскрыть.
По отношению к эллиптическим кривым производительность 1 MIPS
соответствует примерно 4*10^4 операций сложения кривой в секунду,
поскольку длина ключа существенно превышает длину еденицы данных. У
стойчивость алгоритмов криптографии принято оценивать в MIPS годах . Иначе
говоря , устойчивость – это число лет непрерывной работы , необходимое
вычислителю с производительностью 1 MIPS ,чтобы взломать данный шифр.
|Время на взлом |Размер ключа |Размер ключа |Отношение длин |
|MIPS лет |RSA/DSA |ЕСС |ключей RSA/DSA |
|10^4 |512 |106 |5:1 |
|10^8 |768 |132 |6:1 |
|10^11 |1.024 |160 |7:1 |
|10^20 |2.048 |210 |10:1 |
|10^78 |21 |600 |35:1 |
Таблица 3.1. Сравнение размеров ключей , необходимых для обеспечения
эквивалентных уровней безопасности.
Программные выполнение на SPARC IPC исполняют 2,000 эллиптических
сложений кривой в секунду. Тогда число эллиптических сложений кривой,
которые могут быть выполнены 1 механизмом MIPS в одном году:
(4 x 104) • (60 x 60 x 24 x 365) " 240.
Например, если 10,000 компьютеров каждый в 1,000 MIPS году доступн, то
эллиптическая кривая дискретного логарифма может быть вычислена через
96,000 лет.
3.3.4 Выбор основного поля Fq и эллиптической кривой E
При установке режимов эллиптической системы шифрования кривой, имеются
три основных пункта, которые должны быть сделаны:
1. Выбор основного конечного поля Fq.
2. Выбор представления для элементов Fq.
3. Выбор эллиптической кривой E по Fq.
1. Два наиболее общего выбора в практических приложениях для
основного конечного поля - F2m и Fp (где p - вспомогательный штрих). ECDLP
одинаково труден для образцов, которые используют F2m и для образцов ,
которые используют Fp, и где размеры 2m и p полей приблизительно равны. Не
имелось никаких математических открытий до настоящего времени, которые
показывают, что ECDLP для эллиптических кривых по F2m может быть проще или
тяжелее чем ECDLP для эллиптических кривых по Fp.
2. Если поле F2m выбрано как основное конечное поле, то имеются
много путей, в которых элементы F2m могут быть представлены. Два наиболее
эффективных пути : оптимальное , нормальное представление основания и
полиномиальное представление основания. Так как элементы в одном
представлении могут быть эффективно преобразованы к элементам в другом
представлении, используя соответствующую матрицу изменения основания, на
ECDLP не воздействует выбор представления.
4. MOV алгоритм приведения выдает алгоритм для ECDLP, когда элли
| |  скачать работу |
Криптография | 
