Основы криптографии Учебное пособие - Алферов А.П.
ISBN 5-85438-025-0
Скачать (прямая ссылка):
которая легко приводится к виду
/cL = '?dP(y)-\K(y)\-l- (*)
yeY
Теорема .Для любого рассматриваемого шифра YjB с равновероятными ключами при достаточно больших значениях L имеет место неравенство
\к\
где Rli — избыточность данного языка.
Доказательство. Согласно формулам (3) и (4), а также условию X с: Al , при достаточно большом L получаем:
H(X) = H1 *L-HA=L-(\-RK)-\og2n. (10)
Так как Y с A1, то
H(Y) < log2\Y\ < Iog1 \aL\ = Iog2 nL = L- Iog2 n.
Отсюда, а также из формулы (7) для неопределенности шифра по ключу и формулы (10), получаем:
H(KlY) = H(X) + H(K) - H(Y) *
* H(K) + L ¦ (I - Ra) • Iog2 п - H(Y) >
> H(K)+ L-(I-Ra)-log2n-L-Xog2 п =
= H(K)-L-Ra-Iog2 п. (11)
165
fлава 7
Найдем соотношение между неопределенностью шифра по ключу и числом ложных ключей. Из определения условной энтропии и равенства (8) получаем:
H(KlY) = ^р(у) ¦ H(KIy) < JjPiy) • Iog21*(>0| <
yeY уеУ
Г \
^lOg;
= Iog2Ort+!).
Мы воспользовались известным неравенством Иенсена [Бил69] применительно к функции действительного переменного f(x) = Iog2 X .
Так называют следующее утверждение. Если f(t) — заданная на отрезке (а,в) вогнутая (то есть выпуклая вверх) функция действительного переменного, то при любых значе-
fff
ti, ..., tm є (а,в) и любых Pu ...,рт >0, YjP1 ~ 1'
;=1
т Ґ т
полняется неравенство Yp' Yp1’1
ниях t/, tm є (а,в) и любых Pu ..., Pm ? U, 2_,P1 ~ *' ВЬ|‘
;=1
( т \
• Для
/=1 ^ i=l J
выпуклых (вниз) функций знак неравенства — противоположный.
Таким образом, получаем неравенство
H(K/Y)<\og2(fcL+l), (12)
которое имеет место при достаточно большом L. Из (И) и
(12)следует, что
Iog2O^ +1) > H(K) -L Rk- Iog2 п.
Условие равновероятности ключей шифра максимизирует энтропию H(K) . Это дает нам неравенство
166
НаОежность шифров
Iog2Oci +1) > Iog2 |А"| -L-Ra -Iog2 п,
потенцируя которое получаем искомое неравенство (9).
Назовем расстоянием единственности для шифра натуральное число (обозначим его L0 ), для которого ожидаемое
число ложных ключей кА равно нулю. По сути, расстояние единственности есть средняя длина шифртекста, необходимая для однозначного восстановления истинного ключа (без каких-либо ограничений на время его нахождения).
Для получения оценки расстояния единственности для поточного шифра с равновероятными ключами воспользуемся неравенством (9). Непосредственно из этого неравенства следует, что
Минимально возможное значение L в этом неравенстве и принимается за L0. Таким образом
Несмотря на некоторую некорректность вывода формулы (13), эта формула тем не менее хорошо согласуется с практикой, и поэтому ею пользуются. Например, для шифра простой
замены с параметрами п = 26, |АГ| = 26!, Ra = 0,5 формула
(13) дает оценку
K1 +1
откуда при K1 = 0 получаем (АТ) <nL Ra и, следовательно,
L>
Ra - log 2п
167
І лава 7
L, =
88,4
0,5-4,7
= 38.
Это значит, что для английского языка в среднем по криптограмме длиной около 40 можно однозначно определить открытый текст, что приблизительно соответствует практическому опыту.
Замечания
1. Следует иметь в виду, что при попытке вскрыть, например, шифр простой замены с использованием только частот букв целесообразно оценивать расстояние единственности с учетом оценки энтропии Ha величиной H1, вычисленной для позначной модели открытого текста. При этом оценка для расстояния единственности может существенно вырасти. При использовании частот биграмм целесообразно Ha приблизить величиной H2 и так далее.
2. В наших выводах о числе ложных ключей и расстоянии единственности для поточного шифра предполагалось,
что число ключей \к\ рассматриваемого шифра является
постоянным. Тем самым из рассмотрения выпадают, например, шифры гаммирования со случайной гаммой. Для них число ключей растет вместе с ростом длины открытого текста и тем самым может потенциально вырасти до бесконечности. Подобные шифры обычно называют случайными в отличие от программных шифров, для которых число ключей фиксировано и не зависит от длины открытого текста. Таким образом, наши выводы справедливы лишь для программных шифров. Для случайных шифров расстояние единственности потенциально может быть равно + оо . Такие шифры имеют название идеальных.
3. Формулу расстояния единственности можно применять и для блочных шифров. В этом случае шифр можно рас-
168
Надежность шифров
сматривать как поточный, но в большом алфавите. Естественно, что при этом следует использовать избыточность языка, подсчитанную для «-грамм, где п — длина блока
Ra
(грубым приближением для нее служит отношение------).
п
§ 7.3. Стойкость шифров
Надежность или стойкость шифров определяется объемом работы криптоаналитика, необходимой для их вскрытия. Шифрсистема может служить объектом нападения противника, располагающего разного уровня интеллектуальным и вычислительным потенциалом. Нападающий может быть оди-ночкой-хакером, имеющим персональный компьютер. Задача криптоанализа может интересовать некую фирму, обладающую солидным персоналом и оборудованием. Наконец, речь может идти о работе по добыванию информации мощной государственной организацией типа АНБ США. Возможности потенциального противника определяют требования, предъявляемые к надежности шифрования.
