Введение в современную криптографию
Сдвиговый шифр и принцип достаточного пространства ключей
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Сдвиговый шифр и принцип достаточного пространства ключей. Сдви-
говый шифр можно рассматривать, как вариант шифра Цезаря² только с клю- чом. В частности, в сдвиговом шифре ключ k является номером между 0 и 25. Чтобы зашифровать, буквы сдвигаются как в шифре Цезаря, но количество знаков определяется ключом k . Переводя это на синтаксис шифрования, опи- санный выше, получаем, что пространство сообщений состоит из цепочек букв латинского алфавита произвольной длины без использования знаков пункту- ации, пробелов и числительных, а также нечувствительных к регистру. Алго- ритм генерации Gen выдает унифицированный ключ k ∈ {0, . . . , 25}; алгоритм Enc принимает ключ k и открытый текст, сдвигает каждую букву открытого текста вправо на k мест (циклический переход в конце алфавита); а алгоритм расшифровки Dec принимает ключ k и шифртекст и сдвгает каждую букву со- общения влево на k мест. Получается строго математическое описание , если приравнять английский алфавит с множеством {0, . . . , 25} (так,a = 0, b = 1, и т.д .). __________________________________________________________ ²В некоторых книгах, “шифр Цезаря” и “сдвиговый шифр” используются взаимозаме- няемо. 15 Тогда пространство сообщений M - любая конечная последовательность це- лых чисел из этого множества. Шифрование сообщения m = m1 • • • mA (где mi ∈ {0, . . . , 25}) с помощью ключа k задается выражением Enck (m1 • • • mA ) = c1 • • • cA, где ci = [(mi + k) mod 26]. (Запись [a mod N ] обозначает остаток от деления на N , при 0 ≤ [a mod N ] < N . Мы называем процесс отображения a в [a mod N ] как деление по модулю N; мы поговорим об этом подробнее в начале Г лавы 8.) Расшифровка шифртекста c = c1 • • • cA с помощью ключа k задана выражением Deck (c1 • • • cA ) = m1 • • • mA, где mi = [(ci − k) mod 26]. Хорошо ли защищен сдвиговый шифр? Перед тем как продолжить чтение, попытайтесь расшифровать следующий текст, зашифрованный с помощью сдвигового шифра и секретного ключа k: OVDTHUFWVZZPISLRLFZHYLAOLYL. Можно ли восстановить сообщение не зная k? На самом деле все просто! При- чина в том, что всего существует только 26 возможных ключей. Поэтому можно попытаться расшифровать шифрограмму с помощью перебора всех возмож- ных ключей и тем самым получить 26 образцов открытого текста. Несомнен- но среди них будет и верный образец; более того, если шифртекст «достаточно большой», тогда правильный текст будет по всей вероятности единственным образцом среди всех, который «обладает смыслом». (Последнее утверждение необязательно должно быть верным, но оно справедливо в большинстве слу- чаев. Даже когда это не так, атака сужает множество потенциальных текстов максимум до 26.) Просмотрев весь перечень из 26 образцов, легко обнаружить первоначальный открытый текст. Атака, которая заключается в переборе всех возможных ключей, называется ата- кой методом грубой силы или перебором всех возможных вариантов. Очевидно, что стойкая криптосистема не должна быть уязвима атакам такого рода.³ Данное замечание известно, как принцип достаточности пространства ключей: В любой стойкой криптосистеме пространство ключей должно быть достаточно большим, чтобы свести на нет любые попыт- ки атак методом перебора. Можно дискутировать на тему того, сколько попыток должно быть, чтобы считать взлом «неосуществимым», а точное определение осуществимости за- висит, как от ресурсов потенциальной нападающей стороны, так и от длитель- ности времени, в течение которого отправляющая и принимающая стороны хотят обеспечивать секретность обмена данными. Сегодня злоумышленники могут использовать суперкомпьютеры, тысячи персональных компьютеров или 16 графических процессоров для ускорения атак методом грубой силы. Для защиты от таких атак необходимо, чтобы пространство ключей было очень большим - ска- жем, размером как минимум 270 и даже больше, если имеется заинтересованность в длительной защите от нападающих противников с хорошим финансированием. Принцип достаточности пространства ключей предоставляет необходимое условие для безопасности, но НЕ достаточное. Это проиллюстрировано в сле- дующем примере. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|