Длина ключа и его полный перебор

1. Введение

1.1. Что такое бит?

Бит является фундаментальной единицей информации. Он может принимать значения 0

или 1. В течение сорока последних лет компьютеры работают сбинарными данными, то

есть с наборами битов (а не с цифрами от 0 до 9, как это принято у людей; можно

сказать, что компьютеры имеют только два пальца). Битыпозволяют кодировать целые

числа, символы, и т.д.. Вся информация, проходящая через компьютер, превращается

в биты.

8 бит образуют байт; это дает 256 комбинаций и позволяет кодировать числа от 0

до 255 или символы (включая разницу между прописными и строчными буквами,символы

с надстрочными знаками и другие).

1024 байта образуют один килобайт (кБ). 1024 используется вместо 1000 так как

1024 является степенью числа 2, то есть "круглым" числом, еслиработать по

основанию 2. 1024 килобайта образуют мегабайт (МБ), или 1048576 байт. 1024

мегабайта образуют гигабайт (ГБ), или 1073741824 байта. 1024 ГБобразуют терабайт

(ТБ). Дальнейшее умножение малоупотребительно, т.к. дорогостояще со всех точек

зрения. Типичная емкость жестких дисков широко распространенных внастоящее время

компьютеров составляет десять гигабайт. Развитая сеть может пропускать десять

мегабайт в секунду между двумя машинами.

1.2. Что такое криптографический ключ?

Криптографические операции, такие как шифрование и подписание данных электронной

цифровой подписью, могут быть осуществлены только определеннымилицами,

располагающими некоторыми секретами. В прошлые века этим секретом был сам способ

преобразования данных. Однако более рационально и более

эффективноконцентрировать этот секрет в виде набора битов, а сам алгоритм делать

общедоступным.

Действительно, сохранять в тайне алгоритм проблематично, и, кроме того,

необходима численная оценка его безопасности. Сам факт публикации

алгоритмапозволяет "бесплатно" получить признание его надежности

криптографическим сообществом.

Ключ, таким образом, является концентрацией секрета, этот набор битов является

"эссенцией" конфиденциальности.

1.3. Что такое полный перебор?

Взломать криптосистему, значит суметь осуществить некоторые операции, требующие

(в теории) знания секрета (ключа), не имея информации о последнем.Наиболее

полным взломом является взлом, в результате которого становится известен ключ,

что дает взломщику те же полномочия, что и законному владельцуключа.

Полный перебор является наиболее простым методом этой точки зрения: он состоит в

том, чтобы пробовать все ключи один за другим до тех пор, пока ненайдется

правильный. Этот метод является наиболее общим, и может быть распараллелен

(вычисления могут быть распределены на много машин). Кроме того,он наиболее

реалистичен: если рассматривать случай симметричной системы шифрования (которая

ставит в соответствие блоку, состоящему из несколькихбайтов, другой блок той же

длины, но преобразованный к "нечитаемому" виду при помощи ключа), достаточно

перехватить пару открытыйтекст/зашифрованный текст, то есть блок из несколько

байтов и соответствующих им зашифрованных. Например, если передается картинка в

формате JPG, то началосообщения представляет собой стандартный заголовок JPG,

формат которого всем хорошо известен.

С точки зрения статистики, надо перебрать примерно половину возможных ключей,

прежде чем найдется правильный. Если длина ключа составляет 56 битов,это

означает, что в среднем необходимо провести 2^55 итераций, что составит

36028797018963968.

1.4. Является ли полный перебор единственновозможным методом криптоанализа?

Нет. Но другие методы сильно зависят от конкретного алгоритма. Некоторые,

такиекак линейный или дифференциальный криптоанализ, требуют огромного числа пар

открытый/зашифрованный текст, представляя, таким образом, чисто

теоретическийинтерес.

Кроме того, существуют криптосистемы (в частности, системы асимметричные,

называемые еще "системами с открытым ключом"), для которых всесочетания битов не

образуют правильного ключа. Типичный пример - RSA, где ключ представлен большим

числом, полученным из двух больших простых чисел.Совокупность наборов из 1024

бит, которые являются двоичной записью этих чисел, гораздо меньше 2^1024. Полный

перебор абсурден в этом случае.

1.5. 128-битный ключ в два раза устойчивее квзлому, чем 64-битный?

НЕТ! Это распространенная ошибка. Каждый дополнительный бит удваивает количество

возможных ключей и затраты на полный перебор. Ключ длиной 128 битявляется в

18446744073709551616 раз более сложным для подбора, по сравнению с ключом длиной

64 бита (который уже не назовешь совсем легким).

1.6. PGP должно быть очень устойчив, так какиспользует ключи 1024 бита.

Стоп! Давайте разберемся! "1024 бит" в PGP - это ключ RSA или DSS, то есть ключ

асимметричного алгоритма. Атака методом полного перебора не самыйлучший вариант

в этом случае.

Кроме того, асимметричные алгоритмы относительно медленны, и "внутри" PGP

использует симметричный алгоритм (исторически IDEA,затем CAST) размер ключа

которого составляет 128 бит.