9.4. Длины ключей

В таблице [tab:recommended-key-lengths] приведены битовые длины ключей для криптосистем.

 1.5cmБлочные шифры, $K$Схема ЭП
 1.5cmRSA, $n$2.4cmЭллипт. кривые, порядок точки3.5cmЭль-Гамаль $\operatorname{mod} p$: модуль / порядок (под)группы
Взломано
Биты56768109503
КонкурсDesChalRSA-768ECC2K-108
Год199720092000
Стандарт России
Биты256255
ГОСТ28147--89—34.10-2001—
Год19892001
Стандарт США
Биты128-2561024-3072151-4801024-3072/160-256
FIPS №197draft 186-3draft 186-3draft 186-3
Год2001200620062006
Таблица 9.3 — Минимальные длины ключей в битах по стандартам России и США
Скорость вычисления ЭП

Сравним производительность схем ЭП, чтобы продемонстрировать преимущества ЭП вида Эль-Гамаля перед RSA для больших ключей. В приложении показано, что в модульной арифметике по модулю числа $n$ с битовой длиной $k \simeq \log_2 n$ операции имеют битовую сложность:

$$ \begin{array}{lcl} a^b \mod n & - & O(k^3), \\ ab \mod n, ~ a^{-1} \mod n & - & O(k^2), \\ a+b \mod n & - & O(k). \\ \end{array} $$

Так как все описанные схемы ЭП используют возведение в степень по модулю, то битовая сложность – $O(k^3)$. Оценки количества целочисленных $t$-разрядных умножений при вычислении ЭП имеют вид:

  1. RSA:
    $$ (2 \log_2 n) \cdot \left( \frac{\log_2 n}{t} \right)^2; $$
  2. DSA (англ. Digital Signature Algorithm, стандарт США [55]) – электронная подпись, вычисляемая по принципу Эль-Гамаля по модулю $p$ и с порядком циклической подгруппы $q$:
    $$ (2 \log_2 q) \cdot \left( \frac{\log_2 p}{t} \right)^2; $$
  3. ГОСТ Р 34.10-2001 (стандарт России [126]) и ECDSA (англ. Elliptic Curve Digital Signature Algorithm, стандарт США [55]), вычисляемые по принципу Эль-Гамаля в группе точек эллиптической кривой по модулю $p$:
    $$ (2 \log_2 p) \cdot 4 \cdot \left( \frac{\log_2 p}{t} \right)^2. $$

В таблице [tab:signature-rate] приведены оценки скорости вычисления ЭП (оценки числа умножений 64-битовых слов).

ЭПОценочное число 64-битовых умножений
RSA 1024$(2 \cdot 1024) \cdot \left( \frac{1024}{64} \right)^2 \approx$ 500 000
RSA 20484 000 000
RSA 307214 000 000
RSA 409634 000 000
DSA 1024/160$(2 \cdot 160) \cdot \left( \frac{1024}{64} \right)^2 \approx$ 82 000
DSA 3072/2561 200 000
ECDSA 160$(2 \cdot 160) \cdot 4 \cdot \left( \frac{160}{64} \right)^2 \approx$ 8 000
ECDSA 512260 000
ГОСТ Р 34.10-2001$(2 \cdot 256) \cdot 4 \cdot \left( \frac{256}{64} \right)^2 \approx$ 33 000
Таблица 9.4 — Оценочное число 64-битовых умножений для вычисления ЭП