Почему асимметричное шифрование слабее симметричного?

Question

[DVoropaev]

Вот видео на ютубе, где автор утверждает (11:30):

При одинаковой длине ключей, симметричных и асимметричных, криптостойкость алгоритмов разная. И криптостойкость симметричных выше. Асимметричных ниже. ...

Как это объяснить?

Comments

[sim3x]

Укажите тайминг

И укажите, кто такой автор

[Иван Шумов]

sim3x, подпишусь. Ибо или топикстартер не понял или это видео - трэш, но слушать час ради разбора....

[Дмитрий Шицков]

Утверждение чушь. Пруфлинк в студию

[Lynn «Кофеман»]

sim3x, Дмитрий Шицков, вообще-то утвержение правда https://en.wikipedia.org/wiki/Key_size

The effectiveness of public key cryptosystems depends on the intractability (computational and theoretical) of certain mathematical problems such as integer factorization. These problems are time consuming to solve, but usually faster than trying all possible keys by brute force. Thus, asymmetric algorithm keys must be longer for equivalent resistance to attack than symmetric algorithm keys.

Для AES сейчас считается достаточным 128 бит, а для RSA минимум 1024. Но вообще это странное сравнение, примерно как сравнивать самосвал и формулу-1

[Дмитрий Шицков]

Алексей Тен, черт, и правда. При равной длине ключа же... Сегодня день моих опрометчивых ошибок

[Lynn «Кофеман»]

Объяснение простое: разные алгоритмы, однако

[DVoropaev]

sim3x, Иван Шумов, Виноват, теперь указал

[Иван Шумов]

DVoropaev, забавно однако

Answer 1

[jcmvbkbc]

При одинаковой длине ключей, симметричных и асимметричных, криптостойкость алгоритмов разная. И криптостойкость симметричных выше. Асимметричных ниже. ...

Как это объяснить?

Это объясняется тем, что у симметричных и асимметричных алгоритмов разная природа.
Симметричные (например AES) используют ключ для генерации преобразования входного блока в выходной. Количество бит в ключе напрямую определяет размер пространства преобразований -- 128-битный ключ даёт 2¹²⁸ возможных значений выходного блока для каждого входного.
Асимметричные используют ключ по-разному, поэтому нужно рассматривать конкретный алгоритм. RSA использует биты ключа для хранения произведения двух простых чисел. 128-битный ключ даёт 64-битные простые числа. Факторизация 128-битного числа не требует перебора 2¹²⁸ вариантов и занимает на обычном современном железе порядка секунды.

Answer 2

[pestunov]

Это объясняется тем, что
(1) Для современных симметричных алгоритмов неизвестно атак, которые работают быстрее полного перебора ключей. Например, если длина ключа (скажем у AES) 128 бит, то взломать шифр можно только за 2^128 операций. Быстрее нельзя.

(2) Для большинства же асимметричных алгоритмов это утверждение неверно, поскольку для них существуют алгоритмы взлома, которые работают быстрее полного перебора. Для простоты расчетов я не буду приводить примеры самых быстрых алгоритмов взлома, но рассмотрю один алгоритм, демонстрирующий эту ситуацию.

Стойкость многих асимметричных систем основана на сложности решения задачи дискретного логарифмирования. И решить ее можно быстрее, чем полным перебором, например, методом Шенкса, который имеет сложность sqrt(длины ключа). Следовательно, ключ длиной 128 бит обеспечивает сложность взлома не 2^128, а всего лишь 2^64. Следовательно, для достижения сложности взлома 2^128 длина ключа должна быть 256 бит.

Вот и получается, что для достижения сложности взлома 2^128 симметричным схемам достаточно 128 бит, а асимметричным - 256. Но здесь оговорюсь еще раз, что существуют и более эффективные алгоритмы, чем метод Шэнкса, поэтому ключи асимметричных схем как правило еще длиннее.

Answer 3

[chupasaurus]

Эллиптическая криптография - ассиметричная и с теми же длинами ключей, что и у симметричных.

Answer 4

[Karpion]

Упорно не понимаю суть вопроса.

Есть стойкость шифрования к взлому. Она зависит от алгоритма и от длины ключа.
Достижение заданной стойкости - для разных алгоритмов требует разной длины ключа. Это, вроде, очевидно.

Асимметричные алгоритмы - это такие, что кроме криптостойкости, от них требуется ещё и асимметричность (ну, совсем уж очевидная фраза; правда, тут надо понимать, что же такое "асимметричность"). А ради дополнительного требования - практически всег...; в данном случае "падает стойкость при той же длине ключа" или "нужно нарастить ключ для той же стойкости".
(Если для улучшения не надо ничем жертвовать - то это улучшение делается, а элемент "A" на картинке по ссылке выбрасывается на помойку.)