Введение в криптографию

       

Программные разложения фунции на множетели


Криптографический алгоритм 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 лет.



Содержание раздела