Программные разложения фунции на множетели
Криптографический алгоритм 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 лет.
