14.2.4. Расстояние единственности и идеальная секретность

Лекции по Теоретическим основам цифровой связи   

14. Шифрование и дешифрование

14.2.4. Расстояние единственности и идеальная секретность

Ранее утверждалось, что если допускаются сообщения неограниченной длины, то совершенная секретность требует бесконечного количества ключей. При конечном размере ключа его неопределенность Н(К|С) обычно приближается к нулю, откуда следует, что ключ может быть определен единственным образом, а система шифрования может быть взломана. Расстояние единственности (unicity distance) определяется как наименьшая длина шифрованного текста N, при которой неопределенность ключа Н(К|С) близка к нулю. Следовательно, расстояние единственности — это количество шифрованного текста, необходимое для того, чтобы однозначно определить ключ и таким образом взломать систему шифрования. Шеннон (Shennon) [5] описал систему с идеальной секретностью как систему, в которой Н(К|С) не стремится к нулю, если количество шифрованного текста стремится к бесконечности. Иными словами, ключ не может быть определен, независимо от того, сколько шифрованного текста перехвачено. Термин «идеальная секретность» описывает систему, которая не достигает совершенной секретности, но, тем не менее, не поддается взлому (безусловно защищенная система), поскольку она не дает достаточно информации для определения ключа.

Большинство систем шифрования слишком сложны для определения вероятностей, необходимых для вычисления расстояния единственности. В то же время расстояние единственности иногда можно аппроксимировать, что было показано Шенноном [5] и Хэллманом (Hellman) [6]. Следуя Хэллману, предположим, что каждый открытый текст и шифрованное сообщение получены с помощью конечного алфавита из L символов. Таким образом, всего существует 2rN возможных сообщений длиной N, где r — абсолютная интенсивность языка. Всю область сообщений можно разделить на два класса - осмысленные сообщения M1 и бессмысленные сообщения М2. Тогда имеем

                   число осмысленных сообщений 2rN                                   (14.10)

             число бессмысленных сообщений 2rN - 2rN,                             (14.11)

где r — истинная интенсивность языка, а априорные вероятности классов сообщений описываются следующими выражениями.

                    M1осмысленное                               (14.12)

             Р(М2) = 0                        М2 – бессмысленное                            (14.13)

Предположим, что существует 2H(K) возможных ключа (размер алфавита ключей), где H(К) — энтропия ключа (бит в ключе). Предположим, что все ключи равновероятны.

                                         Р(К) == 2-Н(К)                                         (14.14)

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

При данном шифровании, описываемом как  Сi=EKi(Mi), неверное решение F возникает всегда, когда шифрование с помощью другого ключа Kj может давать Сi  из того же сообщения Mi  или из некоторого другого сообщения Мj.

                                    Ci=EKi(Mi) = EKj(Mi) = EKj(Mj)                             (14.15)

Криптоаналитик, перехвативший Сi, не сможет выбрать верный ключ и, следовательно, не сможет взломать систему шифрования. Мы не рассматриваем операции дешифрования, которые дают бессмысленные сообщения, так как они могут легко отбрасываться.

Для каждого верного решения конкретного шифрованного текста существует 2H(K)-1  неверных ключа, каждый из которых имеет ту же вероятность P(F) получения неверного решения. Так как все осмысленные открытые сообщения предполагаются равновероятными, вероятность неверного решения равна вероятности получения осмысленного сообщения.

                                        P(F)== 2(r-r’) = 2 -DN                                  (14.16)

Здесь D =r’-rизбыточность языка. Тогда ожидаемое число неверных решений F равно следующему.

                                                        (14.17)

Поскольку F быстро убывает с увеличением N, то

                                          log2 = H(K)-DN= 0                                      (14.18)

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

                                                          N=                                         (14.19)

Из уравнения (14.17) следует, что если Н(К) значительно больше DN, то будет множество осмысленных расшифровок, и, следовательно, существует малая вероятность выделения криптоаналитиком верного сообщения из возможных осмысленных. Приблизительно, DNэто число уравнений для ключа, а Н(К) — число неизвестных. Если число уравнений меньше числа неизвестных битов ключа, единственное решение невозможно; говорят, что система не поддается взлому. Если число уравнений больше числа неизвестных, возможно единственное решение, и система не может больше считаться не поддающейся взлому (хотя она все еще может относиться к защищенным по вычислениям).

Стоит отметить, что доминирование бессмысленных дешифровок позволяет взламывать криптограммы. Уравнение (14.19) показывает значение использования сжатия данных до шифрования. Сжатие данных устраняет избыточность языка, таким образом, увеличивая расстояние единственности. Совершенное сжатие данных даст D = 0 и N =для любого размера ключа.

Пример 14.4. Расстояние единственности

Вычислите расстояние единственности для системы шифрования, использующей письменный английский язык, ключ которой задается последовательностью k1, k2,..., k29, где каждое kiслучайное целое из интервала (1, 25), которое определяет номер сдвига (рис. 14.3) для i-го символа. Предположим, что все возможные ключевые последовательности равновероятны.

Решение

Существует (25)29 возможных равновероятных ключевых последовательностей. Следовательно, используя равенства (14.5), (14.8) и (14.19), получаем следующее.

Энтропия ключа: Н(К) = log2 (25)29 =135 бит

Абсолютная интенсивность английского языка: r’=log226= 4,7 бит/символ

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

r=1,5 бит/символ

Избыточность: D = r’-r = 3,2 бит/символ

N = символа

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







© Банк лекций Siblec.ru
Формальные, технические, естественные, общественные, гуманитарные, и другие науки.