3.3.2. Разложения на множетели

Начиная с 1985, на ECDLP обратили значительное внимание ведущие математики во всем мире. Алгоритм из-за Pohlig и Hellman приводит определениеl к определениюl модуля каждый из главных множителей n. Следовательно, чтобы достичь возможно максимального уровня защиты, n должен быть главным. Лучший алгоритм, известный до настоящего времени для ECDLP - Pollard метод ро, где шаг имеется эллиптическое сложение кривой. В 1993 Р. Oorschot и Майкл Винер показали, как Pollard метод ро может быть параллелизован так, чтобы, если r процессоры использовались, то ожидаемое число с каждым процессором перед одиночным дискретным логарифмом получено - ( ) /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 ,чтобы взломать данный шифр.

Таблица 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. 4. MOV алгоритм приведения выдает алгоритм для ECDLP, когда эллиптическая кривая суперсингулярна. В большенстве случаев эллиптические кривые являются не-суперсингулярными. Кроме того, можно легко проверить действительно ли MOV алгоритм приведения выполним для данной эллиптической кривой – следовательно, этого разъедания легко избегают на практике. Также, можно легко обнаружить является ли данная кривая аномальной. Разъедания на аномальной кривой легко избегают. При выборе не-суперсингулярной эллиптической кривой, можно выбирать кривую наугад, или можно выбирать кривую специальными свойствами, которые могут привести быстрее к эллиптической арифметике кривой. Пример специальной категории кривых, который был предложен - кривые Koblitz . ECDLP одинаково труден для образцов, которые используют беспорядочно сгенерированные кривые, и для тех, которые используют кривые Koblitz. Не имелось никаких математических открытий до настоящего времени, которые показывают, что ECDLP для беспорядочно сгенерированных эллиптических кривых - проще или тяжелее чем ECDLP для кривых Koblitz.