|
Читайте также: |
P(Ml\CJ) = P(Mi) (14.2)
Таким образом, для системы с совершенной секретностью характерно следующее: если криптоаналитик перехватил сообщение С,-, то дальнейшей информации, которая бы облегчила ему дешифровку сообщения, он не получит. Необходимое и достаточное условие совершенной секретности: для любого М, и С,
P(Cj\M:) = P(Cj) (14.3)
На рис. 14.4 изображен пример схемы совершенной секретности. В этом примере Ш}=М0, М„ М2, М3; {С} = С0, Си С2, Су, {К} = К* Кх, К2, Къ-, N=U = 4, Р(М,) = Р{С}) = {. Преобразование сообщения в шифрованный текст выполняется следующим образом:
Cs=TKj(Mj),
(14.4)
рованных сообщений равны между собой, то система имеет совершенную секретность тогда и только тогда, когда выполняются следующие два условия.
1. Существует только один ключ, преобразующий каждое сообщение в каждый шифрованный текст.
2. Все ключи равновероятны.
Если эти условия не выполняются, то будет существовать некоторое сообщение Mh при котором для данного Cj не существует ключа, который мог бы дешифровать С, в Mh Отсюда следует, что для некоторых i и j P(M\Cj) = 0. В этом случае криптоаналитик может исключить из рассмотрения определенные нешифрованные сообщения, упростив, таким образом, задачу. Вообще, совершенная секретность является очень желательным свойством, поскольку это означает, что система шифрования безусловно защищена. Должно быть очевидно, что в системах, передающих большое количество сообщений, для достижения совершенной секретности требуется распределить большое количество ключей, а это, в свою очередь, может привести к значительным практическим затруднениям, что делает такие системы нереализуемыми. В системе с совершенной секретностью число возможных ключей так же велико, как и число возможных сообщений, поэтому, если мы разрешим передавать сообщения неограниченной длины, совершенная секретность потребует бесконечного количества ключей.
Пример 14.1. Взлом системы шифрования, если область ключей меньше области сообщений
Рассмотрим шифрованный текст, состоящий из 29 символов.
GROBOKBODROROBYOCYPIOCDOBIOKB Данный текст был получен с помощью шифра Цезаря (см. раздел 14.1.4); каждая буква получена сдвигом на К символов, где 1 < К < 25. Покажите, как криптоаналитик может взломать этот код.
Решение
Поскольку количество возможных ключей (их 25) меньше количества возможных осмысленных сообщений из 29 символов (их огромное множество), совершенная секретность не может быть достигнута. В исходном полиалфавитном шифре, показанном на рис. 14.3, символ открытого текста заменяется буквой некоторой строки, причем номер строки постоянно возрастает. Следовательно, в процессе анализа шифрованного текста мы обращаем процесс: теперь буквы шифрованного текста заменяются буквами строк, причем номер строки постоянно уменьшается. Путем перебора всех ключей от 1 до 25 (рис. 14.5) можно легко рассмотреть все возможности. В результате, этот процесс приводит к единственному ключу (К = 10), дающему осмысленное сообщение (пробелы были добавлены вручную): WHERE ARE THE HEROES OF YESTERYEAR.
Пример 14.2. Совершенная секретность
Для создания шифра, имеющего совершенную секретность, можно несколько модифицировать область ключей, описанную в примере 14.1. В этой новой системе шифрования каждый символ сообщения шифруется с использованием случайно выбранного ключевого значения. Теперь ключ К задается последовательностью к\, кг,..., кгч, где каждое к; — это случайно выбранное целое число из интервала (1, 25), определяющее сдвиг, используемый для /-го символа. Таким образом, всего существует (25)29 различных ключевых последовательностей. Значит, шифрованный текст из 29 символов, приведенный в примере 14.1, может соответствовать любому осмысленному сообщению из 29 символов. Например, шифрованный текст мог соответствовать следующему открытому тексту (пробелы были добавлены вручную).
ENGLISH AND FRENCH ARE SPOKEN HERE
Данный текст получен с помощью ключа 2, 4, 8, 16, 6, 18, 20,.... Стоит отметить, что большинство возможных наборов из 29 символов можно исключить, поскольку они не являются осмысленными сообщениями. Совершенная секретность данного кода — результат того, что перехват шифрованного текста не дает никакой дополнительной информации об открытом сообщении.
Ключ Текст
|
Рис. 14.5. Пример взлома системы шифрования, если область ключей меньше области сообщений
14.2.2. Энтропия и неопределенность
Как обсуждалось в главе 9, объем информации в сообщении связан с вероятностью появления сообщения. Сообщения вероятности 0 либо 1 не содержат информации, поскольку можно с известной долей определенности предсказать их появление. Чем больше неопределенности существует в предсказании появления сообщения, тем больше оно содержит информации. Следовательно, если все сообщения множества равновероятны, мы не можем быть уверенными в возможности предсказания появления конкретного сообщения, и неопределенность информационного содержания сообщения является максимальной.
Энтропия Н(К) определяется как средний объем информации на сообщение. Она может рассматриваться как мера того, насколько в выбор сообщения X вовлечен случай. Она записывается как следующее суммирование по всем возможным сообщениям.
Н(Х) = -У Р(Х)1оё2 Р(Х) = Ур(Х)1о82-^— (14.5)
х х Р(*>
Если, как выше, логарифм берется по основанию 2, Н(Х) представляет собой математическое ожидание числа битов в оптимально закодированном сообщении X. Это все еще не та мера, которую хотел бы иметь криптоаналитик. Им будут перехвачены некоторые шифрованные тексты, и он захочет узнать, насколько достоверно он может предсказать сообщение (или ключ) при условии, что был отправлен именно этот конкретный шифрованный текст. Неопределенность, определенная как условная энтропия X при данном Y, является для криптоаналитика более полезной мерой при попытке взлома шифра. Она задается с помощью следующей формулы:
Н(Х | Y) = - J]p(X,y)log2 P(X,Y)
(14.6)
Неопределенность может рассматриваться как неуверенность в том, что отправлено было сообщение X, при условии получения Y. Желательным для криптоаналитика является приближение H(X\Y) к нулю при увеличении объема перехваченного шифрованного текста У..
Пример 14.3. Энтропия и неопределенность
Рассмотрим выборочное множество сообщений, состоящее из восьми равновероятных сообщений {X} = Xt, Хг,..., Х8.
а) Найдите энтропию, связанную с сообщением из множества {X}.
б) Дано другое множество равновероятных сообщений {У} = Yi, Y2. Пусть появление каждого сообщения Y сужает возможный выбор X следующим образом.
При наличии Y{ возможны только Х1; Х2, Хг или Х4 При наличии У2 возможны только Х5, Х6, Х7 или Х8
Найдите неопределенность сообщения X, обусловленную сообщением Y. Решение
а) Р(Х)=±
//(X) = 8 [jlog2 8] = 3 бит/сообщение
б) P(Y) = -j. Для каждого Y, Р(Х|К) = j для четырех сообщений из множества {X} и Р(Х|У) = 0 для оставшихся четырех. Используя уравнение (14.6), получим следующее.
H(X\Y) = 2^^4(-^log2 4jj = 2 бит/сообщение
Видно, что знание Y сводит неопределенность X с 3 бит/сообщение до 2 бит/сообщение.
14.2.3. Интенсивность и избыточность языка
Истинная интенсивность языка определяется как среднее число информационных битов, содержащихся в каждом символе, и для сообщения длиной N выражается следующим образом:
Здесь Н(Х) — энтропия сообщения, или число битов в оптимально закодированном сообщении. Для письменного английского языка при больших N оценки г дают значения между 1,0 и 1,5 бит/символ [4]. Абсолютная интенсивность или максимальная энтропия языка определяется как максимальное число информационных битов, содержащихся в каждом символе, в предположении, что все возможные последовательности символов одинаково вероятны. Абсолютная интенсивность задается следующим образом:
r'=\o%iL- (14.8)
Здесь L — число знаков в языке. Для английского алфавита / = log2 26 = 4,7 бит/символ. Истинная интенсивность английского языка, конечно, гораздо меньше его абсолютной интенсивности, поскольку, как и большинство языков, английский очень избыточен и структурирован.
Избыточность языка определяется через его истинную и абсолютную интенсивности.
D = r'-r (14.9)
Для английского языка, где г'= 4,7 бит/символ и г= 1,5 бит/символ, D = 3,2, а отношение D/r'= 0,68 — это мера избыточности языка.
14.2.4. Расстояние единственности и идеальная секретность
Ранее утверждалось, что если допускаются сообщения неограниченной длины, то совершенная секретность требует бесконечного количества ключей. При конечном размере ключа его неопределенность Н(К\С) обычно приближается к нулю, откуда следует, что ключ может бьггь определен единственным образом, а система шифрования может быть взломана. Расстояние единственности (unicity distance) определяется как наименьшая длина шифрованного текста N, при которой неопределенность ключа Н(К\С) близка к нулю. Следовательно, расстояние единственности — это количество шифрованного текста, необходимое для того, чтобы однозначно определить ключ и таким образом взломать систему шифрования. Шеннон (Shennon) [5] описал систему с идеальной секретностью как систему, в которой Н(К\С) не стремится к нулю, если количество шифрованного текста стремится к бесконечности. Иными словами, ключ не может быть определен, независимо от того, сколько шифрованного текста перехвачено. Термин “идеальная секретность” описывает систему, которая не достигает совершенной секретности, но, тем не менее, не поддается взлому (безусловно защищенная система), поскольку она не дает достаточно информации для определения ключа.
Большинство систем шифрования слишком сложны для определения вероятностей, необходимых для вычисления расстояния единственности. В то же время расстояние единственности иногда можно аппроксимировать, что было показано Шенноном [5] и Хэллма- ном (Heilman) [6]. Следуя Хэллману, предположим, что каждый открытый текст и шифрованное сообщение получены с помощью конечного алфавита из L символов. Таким образом, всего существует 2ЛУ возможных сообщений длиной N, где / — абсолютная интенсивность языка. Всю область сообщений можно разделить на два класса — осмысленные сообщения М, и бессмысленные сообщения М2. Тогда имеем
число осмысленных сообщений 2rN (14.10)
число бессмысленных сообщений 2r'N — 2rN, (14.11)
где г — истинная интенсивность языка, а априорные вероятности классов сообщений описываются следующими выражениями.
Р(М2) = О М2 — бессмысленное (14.13)
Предположим, что существует 2тК) возможных ключа (размер алфавита ключей), где Н(К) — энтропия ключа (количество бит в ключе). Предположим, что все ключи равновероятны.
р(к)=-^щ-=2~ЩК) (14Л4>
Определение расстояния единственности основано на модели случайного шифра, которая утверждает, что для каждого ключа К и шифрованного текста С операция дешифрования D^Q дает независимую случайную переменную, распределенную по всем возможным 2/N сообщениям (как осмысленным, так и бессмысленным). Следовательно, для данных Ки С операция D^C) может с равной вероятностью давать любое из открытых сообщений.
При данном шифровании, описываемом как C,=EK(Mt), неверное решение F
возникает всегда, когда шифрование с помощью другого ключа Kt может давать С, из того же сообщения М, или из некоторого другого сообщения Мг
С, =Ek{M1) = EKj(M') = EKj(Mj) (14.15)
Криптоаналитик, перехвативший С„ не сможет выбрать верный ключ и, следовательно, не сможет взломать систему шифрования. Мы не рассматриваем операции дешифрования, которые дают бессмысленные сообщения, так как они могут легко отбрасываться.
Для каждого верного решения конкретного шифрованного текста существует 2И(АЭ_1 неверных ключа, каждый из которых имеет ту же вероятность P(F) получения неверного решения. Так как все осмысленные открытые сообщения предполагаются равновероятными, вероятность неверного решения равна вероятности получения осмысленного сообщения.
syrN
P(F) = ^-— = 2{r~r')N=2~DN (14.16)
Здесь D = / - г — избыточность языка. Тогда ожидаемое число неверных решений F равно следующему:
F = [2H(K) -1]P(F) = [2"W -\]2~dn (14.17)
Поскольку F быстро убывает с увеличением N, то
log2F = H(K)-DN=0 (14.18)
является точкой, где число неверных решений достаточно мало; так что шифр может быть взломан. Следовательно, получаемое расстояние единственности описывается следующим выражением:
Из уравнения (14.17) следует, что если Н(К) значительно больше DN, то будет множество осмысленных расшифровок, и, следовательно, существует малая вероятность выделения криптоаналитиком верного сообщения из возможных осмысленных. Приблизительно, DN — это число уравнений для ключа, а Н(К) — число неизвестных. Если число уравнений меньше числа неизвестных битов ключа, единственное решение невозможно; говорят, что система на поддается взлому. Если число уравнений больше числа неизвестных, возможно единственное решение, и система не может больше считаться не поддающейся взлому (хотя она все еще может относиться к защищенным по вычислениям).
Стоит отметить, что доминирование бессмысленных дешифровок позволяет взламывать криптограммы. Уравнение (14.19) показывает значение использования методов сжатия данных до шифрования. Сжатие данных устраняет избыточность языка, таким образом увеличивая расстояние единственности. Совершенное сжатие данных даст D -0 и /V = оо для любого размера ключа.
Пример 14.4. Расстояние единственности
Вычислите расстояние единственности для системы шифрования, использующей письменный английский язык, ключ которой задается последовательностью к\, к2,..., £», где каждое к, — случайное целое из интервала (1, 25), которое определяет номер сдвига (рис. 14.3) для /-го символа. Предположим, что все возможные ключевые последовательности равновероятны.
Решение
Существует (25)29 возможных равновероятных ключевых последовательностей. Следовательно, используя равенства (14.5), (14.8) и (14.19), получаем следующее:
энтропия ключа: Н(К) = log2 (25)29 = 135 бит,
абсолютная интенсивность английского языка: / = log2 26 = 4,7 бит/символ,
предполагаемая истинная интенсивность английского языка: г = 1,5 бит/символ,
избыточность: D = /-г — 3,2 бит/символ,
„ Н(К) 135 N =--- = = 43 символа.
D 3,2
В примере 14.2 совершенная секретность сообщения из 29 символов иллюстрировалась с использованием того же типа ключевой последовательности, что и в данном примере, где показано, что если имеющийся шифрованный текст состоит из 43 символов (откуда следует, что некоторая часть ключевой последовательности должна использоваться дважды), то возможно единственное решение. В то же время не определена вычислительная сложность отыскания решения. Даже если оценить теоретическое количество шифрованного текста, необходимое для взлома шифра, практически это может оказаться невозможным.
14.3. Практическая защищенность
Для последовательностей шифрованного текста, размер которых больше расстояния единственности, любая система уравнений (определяющая ключ) может быть решена путем простого перебора всех возможных ключей, пока не будет получено единственное решение. Однако это совершенно непрактично, за исключением применения очень короткого ключа. Например, для ключа, полученного путем перестановки английского алфавита, существует 26! = 4 х 1026 возможных пере-
становок (в криптографическом смысле это считается малым). Будем считать, что в результате изнурительных поисков мы нашли правильный ключ, перебрав приблизительно половину возможных комбинаций. Если допустить, что каждая проверка потребует для вычисления 1 мкс, то полное время поиска превысит 1012 лет. Следовательно, если криптоаналитик хочет иметь некоторую надежду на успех, то о “лобовых” методах перебора следует забыть и применять какую-ту иную технологию (например, статистический анализ).
14.3.1. Смешение и диффузия
При расшифровке многих систем шифрования может применяться статистический анализ, использующий частоту появления отдельных символов и их комбинаций. Шеннон [5] предложил две концепции шифрования, усложняющие задачу криптоаналитика. Он назвал эти преобразования “смешение” (confusion) и “диффузия” (diffusion). Смешение — это подстановки, которые делают взаимосвязь между ключом и шифрованным текстом как можно более сложной. Это усложняет применение статистического анализа, сужающего поиск практического подмножества области ключей. В результате смешения дешифрование даже очень короткой последовательности шифрованного текста требует большого числа ключей. Диффузия — это преобразования, сглаживающие статистические различия между символами и их комбинациями. Примером диффузии 26-буквенного алфавита является преобразование последовательности сообщений М = М0, Л/ь... в новую последовательность сообщений Y = Y0, Yu... с помощью следующего соотношения:
5-1
Yn = ^ Мп +, по модулю 26. (14.20)
1 = 0
Здесь каждый символ в последовательности рассматривается как число по модулю 26, s — некоторое выбранное целое число и п = 1, 2,.... Новое сообщение Y будет иметь ту же избыточность, что и исходное сообщение М, но частота появления всех букв в Y будет более равномерной, чем в М. В результате, чтобы статистический анализ принес криптоаналитику какую-либо пользу, ему необходимо перехватить большую последовательность шифрованного текста.
Дата добавления: 2015-10-28; просмотров: 69 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Основы теории принятая статистических решений 1051 77 страница | | | Основы теории принятая статистических решений 1051 79 страница |