Полная версия

Главная arrow Информатика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

РАССТОЯНИЯ ЕДИНСТВЕННОСТИ ШИФРА

Расстояния единственности для открытого текста и ключа

В данном разделе будут рассматриваться лишь поточные шифры (M,K,E,f) с заданными вероятностными распределениями на М и К. Напомним, что поточный шифр определен опорным шифром и соответствием между ключами и ключевыми последовательностями[1]. Будем предполагать, что М—F, где I - алфавит открытого текста, а /: МхК—>Е - сюръективное отображение, EczO1, где О - алфавит шифрованного текста. Наряду с текстом т еМ длины N и шифрованным текстом е еЕ длины N мы будем рассматривать их начальные отрезки mL и eL длины L ≤ N. Будем считать, что вероятностное распределение на множестве М индуцирует вероятностное распределения на начальных отрезках mL eMl сообщений т из М. Последнее распределение и вероятностное распределение на ключах К индуцируют вероятностные распределения на начальных отрезках eLEEL криптограмм е из Е и другие совместные и условные распределения. При изучении свойств рассматриваемого шифра будем считать, что N всегда больше рассматриваемых нами значений L. В связи со сказанным выше корректно введение и соответствующих энтропий:

Эти энтропии также трактуются как ненадежности части сообщения и ключа. Отметим, что в поточном шифре множество ключей не зависит от длины L сообщения.

Теорема Шеннона

1. Ненадежность ключа H(K/EL) есть невозрастающая функция от L, т.е. при любом L '>Ь

2. Ненадежность первых к букв сообщения является невозрастающей функцией от Z, т.е. при L '>L

3. При любом L

Справедливость утверждений теоремы вытекает из свойств условных энтропий.

На качественном уровне, под расстоянием единственности шифра по открытому тексту понимают минимальное натуральное число L, при котором по известному шифртексту eL длины L однозначно восстанавливается соответствующее ему открытое сообщение mL. Аналогично, под расстоянием единственности шифра по ключу понимают минимальное L, при котором по известному шифртексту длины L однозначно восстанавливается использованный ключ. Такие качественные понятия не вполне точны. Действительно, видимо минимальное L, о котором идет речь (если оно существует), зависит от конкретного шифртекста е и тогда минимальное L=L(e). Следовательно, видимо речь должна идти о среднем значении таких минимальных L(e). С другой стороны, для каждого eL можно определить все множество сообщений mL, которые могут быть зашифрованы шифром в криптограмму eL. Расстояние единственности шифра по открытому тексту можно определить теперь как минимальное L, при котором среднее значение мощностей этих множеств равно единице.

Первое определение Шеннона расстояний единственности шифра. Ранее было показано, что энтропия характеризует некоторый источник информации, в частности, вероятностные модели получения открытых (т.е. содержательных) текстов. Число открытых текстов и их вероятности оцениваются по фундаментальным теоремам теории информации, теоремам Шеннона, Хинчина, Макмиллана.

Аналогичную роль играет и условная энтропия H(Mi/Ei) - ненадежность части сообщения в вероятностной модели шифра. Она характеризует среднее число текстов длины L, которые могут соответствовать известному отрезку eL шифрованного текста. Именно, Шеннон полагал, что среднее число текстов mL, которые могут быть зашифрованы в заданный шифртекст, равно

где 2 - основание логарифма в выражении энтропии.

Аналогично 2H(K/El) - среднее число ключей (по всем eL), при которых получается отрезок шифрованного текста (при подходящих выборах mL из М).

Согласно, пункту 1 теоремы Шеннона второе из этих значений с ростом L не возрастает и, в случае существования минимального L, при котором это значение становится равным единице, такое L называют расстоянием единственности шифра по ключу. Аналогично определяют расстояние единственности шифра по открытому тексту, именно, как минимальный корень уравнения R(L) = 2H(Ml/El) = 1.

Таким образом, расстояния единственности шифра это минимальные корни уравнений

относительно L (если такие корни существуют).

Некоторые шифры устроены так, что их количество ключей растет с ростом длины L сообщений, например, шифр гаммирования. В этом случае возможна ситуация, когда R(L)—>oc с ростом L. Такие шифры называют асимптотически стойкими. Для таких шифров при достаточно большом L величина R(L) становится большой и среди R(L) возможных текстов выбрать текст, который был действительно зашифрован в заданную криптограмму, становится невозможным.

Второе определение Шеннона расстояний единственности шифра (модель случайного шифра).

Прямой подсчет расстояний единственности шифра (по открытому тексту и ключу), как правило, затруднителен. В связи с чем, для их подсчета используют модель «случайного шифра». Пусть (E,K,X,F) - шифр расшифрования для шифра зашифрования, МаХ, где М - все множество содержательных открытых текстов длины N в алфавите I (1>2).

Предполагается (в этом и заключается случайность модели шифра), что при случайном и равновероятном выборе ключа %еК и расшифровании на нем криптограммы eL (L≤N) вероятность получить содержательный текст равна

где Н - энтропия на букву содержательного текста в алфавите I, 2 - основание логарифма в выражении энтропии.

Это число «почти» совпадает с вероятностью выбора содержательного открытого текста длины L при случайном и равновероятном выборе последовательности длины L букв алфавита (2НЬ - приближенное значение количества содержательных открытых текстов). Тогда при расшифровании шиф- ртекста длины L на всех ключах из К мы получим в среднем

открытых текстов. Так как H2I, то отсюда следует, что r(L)—>0 с ростом L.

Решая теперь уравнение

относительно L, получаем решение

где D=1---избыточность открытого текста.

l°g2111

2^1

Замечание. Величина |7^f| yyp =r(L) может стремится к бесконечности с

ростом L лишь в случае, когда число ключей К растет вместе с L, например, для случайного шифра гаммирования (К=1Ь).

Расстояние единственности для ключа. Аналогично вычисляется расстояние единственности для ключа. Множество ключей, при которых может быть получен шифртекст eL, при условии, что мы шифровали лишь открытые сообщения (М - множество открытых текстов), совпадает с множеством ключей, расшифровывающих eL в открытый текст, вероятность такого расшифрования и, следовательно, вероятность получения нужного

2»l

ключа при опробовании, как было замечено ранее, равна уур-. Следовательно, величина

одновременно является и средним числом ключей, соответствующих криптограмме длины L. Решение этого уравнения с правой частью r(L)=l относительно L называется расстоянием единственности шифра по ключу.

Так как введенные расстояния единственности шифра по открытому

Т log21К | log21К |

тексту и по ключу совпадают, то величину L0=-——— = ———L назы-

log2|J|-H Dlog2|I|

вают расстоянием единственности шифра.

Отметим определенную некорректность во введении понятия расстояния единственности во втором определении Шеннона. Число содержательных открытых текстов приблизительно равно 2Hl, это число получено в предположении, что рассматривается достаточно больше число L. В связи с этим предыдущие равенства следует рассматривать как приближенные. Некорректность же заключается в том, что одновременно при нахождении расстояния единственности (корня уравнения) ищется по существу минимальное L (оно, возможно, будет и небольшим), и тогда нельзя пользоваться приближенной формулой 2HL для числа открытых текстов.

Второе сомнение в корректности такой формализации понятия расстояния единственности шифра может возникнуть из следующих соображений. По логике рассматриваемого подхода «случайного шифра» расшифрованию подлежит криптограмма, полученная при некотором открытом тексте и некотором истинном ключе х<>- Следовательно, предположение о случайном расшифровании можно относить к ключам из множества К{х0}, и тогда, имея в виду, что уже имеется один истинный ключ, заведомо дающий открытый текст, для среднего значения числа открытых текстов получаем выражение

Следовательно, r'(L) =1 при

Если К>2, то это приближенное равенство справедливо лишь для достаточно больших L (чем лучше приближение, тем больше Ь0). Тем не менее, расчеты показывают, что значения корней уравнений r(L)=l, r'(L) =1 приблизительно равны.

Приведем пример. Пусть |А*|= 2100, |/| =32, Н=1 бит. Тогда r(L)=l при L0=25. Если К=2104, то r(L)=l при L0=26. Откуда следует, что для 2100<К<2104 величина Ь0 будет находится в пределах 250<26. В частности, в этих границах будет находится и L0 для К=2100+1. Рассчитаем теперь

для этого К величину L (t), при которой r'(L)= — , т.е. решим уравнение

Имеем

откуда t=4L-100. Окончательно получаем L'0(t)= 1. При t=4 получаем

L'0(4)=26. Следовательно, для К=2100+1 имеем L'0(4)<26. При t=20 получаем L'o(20)=30. Уже есть повод задуматься и предложить другие подходы к подсчету расстояний единственности шифра.

Третий подход к формализации понятий расстояний единственности шифра. Рассмотрим уравнение шифрования поточного шифра (M,K,E,j), МаХ, E=f(MxK)

Пусть / - алфавит открытого текста, О - алфавит шифрованного текста, mL, eL - начальные отрезки шифруемого текста т и шифрованного текста е, соответственно. Множество всех возможных отрезков mL обозначим через ML, а множество всех возможных отрезков eL обозначим через Еь. В случае |0L|<|Mi||A’| всегда найдется eL, при котором число решений уравнения шифрования относительно неизвестной пары (mL,%) больше единицы. За расстояние единственности шифра примем минимальное L, если оно существует, при котором |Oz'|^M^||A‘| (имеется в виду приближенное равенство).

Пример. Пусть М - множество содержательных открытых текстов,

|К=2100, 1==32, Н=1, тогда ML=2HL и решение уравнения ^=МьК относительно L дает: 25L=2L2100, 5LM.+100, т.е. Ь^25. Сравните с приведенным выше примером.

Одна трактовка второго определения Шеннона расстояний единственности шифра. Попытаемся уточнить использованное Шенноном предположение о случайности расшифрования криптограммы. Предположим, что шифр (M,K,E,f), E=f(MxK), EczY выбирается случайно и равновероятно из множества всех шифров такого вида. т.е. при фиксированных множествах М— сообщений, У - шифробозначений, из множества всех биекций М в У случайно и равновероятно выбираются (с возвращением) К инъекций {fx :М—>У, %еК}. Тем самым случайно выбран шифр A=(M,K,E,f).

Для произвольного шифробозначения уеУ и шифра А обозначим через F(A,y) множество всех сообщений т еМ, для которых существует %, при котором, f(m,x)=y- При фиксированном уеУ заданное вероятностное распределение на шифрах индуцирует вероятностную меру на множестве мощностей F(A,y).

Утверждение. Среднее значение случайное величины F(A,y) | равно

Доказательство. Докажем сначала очевидное на интуитивном уровне вспомогательное утверждение: при случайном и равновероятном выборе инъективного отображения /Х:М—УУ вероятность того, что элемент у будет

принадлежать образу отображения fx, равна у^у-.

Действительно, число возможных различных образов (Об) инъективного отображения: М—>У равно С^1, каждый из таких образов равновероятен. Число образов Об(у), содержащих элементу, равно

Следовательно,

так как вероятность Р(у efz(M)/fz(M)=06) равна либо единице либо нулю. Раскроем последнее выражение

Среднее значение случайной величины F(A,y) определяется числом испытаний |А*| и вероятностью «успеха» P(yefx(M))= Среднее значение F(A,y) равно

Беря в качестве М - множество содержательных открытых текстов и полагая М =2HL , а в качестве У беря ОL, получаем, что среднее значение случайной величины F(A,y) - числа прообразов шифртекстау равно

Из уравнения

находим «новое» расстояние единственности шифра по открытому тексту.

Напомним, что по второму определению Шеннона расстояния единственности шифра по открытому тексту для числа открытых текстов мы имели выражение

  • [1] Бабаш А.В. Криптографические и теоретико-автоматные аспекты современнойзащиты информации. Том 2. М.: Евразийский открытый институт: МЭСИ, 2010.
 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>