Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)

221
лНЬ
|К| — =1
относительно Ь, получаем решение
1о8, |К |	1°8 2 |К |
’ 1об2 111-Н	О1082 Ц Г

ности с ростом I; лишь в случае, когда число ключей |К| растет вместе с Ь, на­ пример, для случайного шифра гаммирования (К=11').

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

равна — . Следовательно, величина

I1-

2 НЬ

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

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

тексту и по ключу совпадают, то величину Ь0= 1о8 г |К |	1оВ, | К |
1°82 111- Н	О 1о§2 111
зываютрасстоянием единственности шифра.

Отметим определенную некорректность во введении понятия рас­ стояния единственности во втором определении Шеннона. Число содержа­ тельных открытых текстов приблизительно равно 2НЬ, это число получено в

предположении, что рассматривается достаточно больше число Ь. В связи с этим предыдущие равенства следует-рассматривать как приближенные. Не-

222

коректность же заключается в том, что одновременно при нахождении рас­ стояния единственности (корня уравнения) ищется по существу минимальное Ь (оно, возможно, будет и небольшим), и тогда нельзя пользоваться прибли­ женной формулой 2НЬ для числа открытых текстов.

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

,НЬ г-О.) =1+1К -И ^ Г

Следовательно, г'(Ь) при

2НЬ

|К-1|— г =0. | 1 |

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

равны.

Приведем пример. Пусть |К|=2100, (1|=32, Н=1 бит. Тогда г(Ь)=1 при Ь0=25. Если |К|=2104, то г(Ь)=1 при Ь0=26. Откуда следует, что для 2 100<(К|<21<)4 величина Ь0будет находится в пределах 25<Ь0<26. В частности, в этих грани­ цах будет находится и Ь0для |К|=2100+1. Рассчитаем теперь для этого |К| вели­

чину Ь'о(1), при которой г'(Ь)=-^-, то есть решим уравнение

2

2 И Ь	1
|К-1| 11 |ь	2х

Имеем

2юо 2^ = —

2 х ’

100 + 1

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

223

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

Третий подход к формализации понятий расстояний единственно­ сти шифра.

Рассмотрим уравнение шифрования поточного шифра (М,К,Е,Г), МсХ, Е={(МхК)

Г(ть,х)=еь.
Пусть I- алфавит открытого текста, О - алфавит шифрованного текста,	еь

-начальные отрезки Шифруемого текста т и шифрованного текста е, соответ­ ственно. Множество всех возможных отрезков шь обозначим через Мь, а множество всех возможных отрезков еь обозначим через Е[_. В случае

всегда найдется еь, при котором число решений уравнения шиф­ рования относительно неизвестной пары (тьх) больше единицы. За расстоя­ ние единственности шифра примем минимальное Ь, если оно существует, при котором |Оь|=|Мь||К| (имеется в виду приближенное равенство).

Рассмотрим пример. Пусть М - множество содержательных откры­ тых текстов, |К|=2100, |1|=|0|=32, Н=1, тогда |Мь|=2нь и решение уравнения Р1|=|МЬ||К| относительно Ь дает: 25Ь=2Ь2 100, 5Ь=Ь+100, то есть Ь=25. Сравните

с приведенным выше примером.

Одна трактовка второго определения Шеннона расстояний един­ ственности шифра.

Попытаемся уточнить использованное Шенноном предположение о случайностирасшифрования криптограммы. Предположим, что шифр (М,К,Е,!), Е=Г(МхК), ЕсУ выбирается случайно и равновероятно из множест­ ва всехшифров такого вида. То есть при фиксированных множествах М - сообщений, У - шифробозначений, из множества всех биекций М в У случай­ но и равновероятно выбираются (с возвращением) |К| инъекций {Гх :М—>У, ХеК}. Тем самым случайно выбран шифр А=(М,К,Е,Г).

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

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

| К | | М |

| У|

224

ДОКАЗАТЕЛЬСТВО. Докажем сначала очевидное на интуитивном уровне вспомогательное утверждение: при случайном и равновероятном вы­ боре инъективного отображения РХ:М—»У вероятность того, что элемент у бу­

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

Действительно, число возможных различных образов (Об) инъектив­

ного отображения: М-»У равно С|у^, каждый из таких образов равновероя­

тен. Число образов Об(у), содержащих элементу, равно

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

Р(уеГх(М ))=Х Р(У е ГХ(М )/ГХ(М ) = Об)Р(Гх(М = Об) =

Об

- 7 Р г Е р(у 6 г,(М )/г1 (м ) = о б ) - - Ь гс!«!г1’ ,

|У| Об С,У|

так как вероятность Р(уеГх(М)/ Гх(М)=Об) равна либо единице либо нулю. Раскроем последнее выражение

_ 1 _ С |МН	| М | ! ( | У | - | М | ) !	(IУ 1-1)1___________ |М |
С]“ 1 |УИ	I У |!	(IМ |—1)!(| V |- 1 - 1М |+1)!		|У|'
Среднее значение случайной величины |Р(А,у)| определяется числом
испытаний |К| и вероятностью «успеха» Р(уеГх(М))=			. Среднее значение
|Е(А,у)| равно
	| К Ц М |

|У |

Беря в качестве М - множество содержательных открытых текстов и полагая |М|=2Н1'., а в качестве У беря Оь, получаем, что среднее значение слу­ чайной величины |Р(А,у)| - числа прообразов шифртекстау равно

9НЬ

1К1— г -

|0|ь

Из уравнения

1К 1

г

о

225

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

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

2 НЬ

Четвертый подход к оценке расстояний единственности шифра/

Вернемся к началу раздела, посвященному расстояниям единственно­ сти шифра по открытому тексту и ключу. Там отмечалось, что расстояния единственности шифра - это, соответственно, целочисленные минимальные корни уравнений

2Н(МЛ>=1,

2Н(К\ Ч ,

то есть корни уравнений Н(М[/Е|)=0 и Н(К/Е^)=0, если они существуют. В разделе «Второе определение Шеннона ...» говорилось о том , что прямой

подсчет расстояний единственности шифра, как правило, затруднителен, в связи с чем выше были рассмотрены и другие формализации понятий рас­ стояний единственности по открытому тексту и ключу.

Ниже, на основе результатов Ю.С. Харина (Ю.С. Харин, В.И. Берник, Г.В. Матвеев «Математические основы криптологии», Минск, БГУ, 1999) даются верхние приближенные оценки указанных корней.

Пусть Ь0- минимальное натуральное число, при котором Н(Мь/Еь)=0.

Имеем

Н(ЕьМьК)=Н(ЕО+Н( Мь/ ЕО+Н(К/Мь,ЕО, Н(Еь,К,М!.)=Н(ЕО+Н(К/ЕО+Н(Мь/К,ЕО.

Так как при известном шифрованном тексте и известном ключе от­ крытый текст восстанавливается расшифрованием однозначно, то Н(Мь/К,Еь)=0. С учетом этого из данных уравнений находим

Н( Мь/ЕО=Н(К/ЕО-Н(К/Мь ЕО

и заключаем, что

Н(Мь/Еь)<Н(К/Еь).

Следовательно, любая верхняя оценка минимального корня уравнения Н(К/Еь)=0 (расстояния единственности по ключу) будет верхней оценкой и

226

для Ь0- расстояния единственности по открытому тексту. Для получения та­

кой оценки используем формулу для ненадежности ключа: Н(К/ЕЬ)=Н(МЬ)+Н(К)-Н(Е[.).

Найдем одно из натуральных чисел Ь, при котором Н(К/Еь)=Н(М1_)+Н(К)-Н(ЕО=0.

Имеем Н(Мь)<1о§2|Мь| (энтропию измеряем в битах) и Н(К)=1о§2|К|

при равновероятном распределении на множестве ключей К. При рассматри­ ваемых условиях справедливо неравенство

Н(МО+Н(К)-Н(ЕО< Ь^МьИоёгМ-ЩЕО.

Искомую верхнюю оценку величины Ь0теперь можно получить, если решить

уравнение

адм ^ + адк н -н сЕ ьН )

относительно Ь.

Введем дополнительные предположения относительно рассматри­

ваемого шифра. Предположим, что

1) Значение Ь достаточно велико, именно - оно таково, что мощность
\	нг	и они
. |М[ | множества открытых текстов приблизительно равна 2

все равновероятны (см. теоремы Шеннона, Н - энтропия на букву). 2) Вероятностные распределения на Мь и К индуцируют равномер­

ное распределение на множестве	(О - алфавит шифрован­
ных текстов.
Из предположения 1) вытекает, что
1о&|Мь|гЬН,
а из 2) получаем

Уравнение

1оё2|М[.|+1о82|К|-Н(Еь)=0

теперь можно переписать в виде ЕН+1оё2|К|-1оё2|Еь|=0.

Представим |Еь| в виде |Еь|=У1', где V зависит от Ь, У=У(Ь). Тогда уравнение принимает вид

Ь Н +1о§ 2|К |-Ы о§ 2У = 0 .

Откуда получаем искомую верхнюю приблизительную оценку расстояний единственности шифра

ь, 1о§2 IКI У=У(Ь). 1о§2 V ” Н

В случае Н(Мь)=ЬН, Н(К)=1о§2|К|, Н(ЕО=Ь 1о&|У| имеем Ь0=1Л

227

При отказе от предположения 2) для вычисления Ь' используют в ряде публикаций неравенство

Ш+1о§2|К|-Н(Еь)>Ш+1о82|К|-Ш §2У

с последующим определением V как корня уравнения ЬН+1о§2|К|-Ыо§2У=0,

который, вообще говоря, не обязан быть в случае строгого неравенства оцен­ кой искомого корня Ь0уравнения ЬН+1о§2|К|-Н(Еь)=0.

В заключение отметим, что мы рассматриваем поточные шифры, для которых существуют расстояния единственности. Очевидно, например, для шифров с эквивалентными ключами расстояние единственности по ключу отсутствует.

Теоретическая стойкость шифров.

Понятие теоретической стойкости шифров обычно ассоциируется с понятием совершенного шифра по К. Шеннону.

Определение. Шифр (Х,К,У,0, У=Г(ХхК) с заданными вероятностны­

ми распределениями Р(х), х€Х на X и Р(х), уеК называют теоретически стойким, если он совершенный по Шеннону, то есть при любом у€У

Р(х/у)=Р(х)

при любом хеХ.

Таким образом, теоретическая стойкость шифра (его совершенность) состоит в том, что знание шифрованного текста, не влечет перераспределения вероятностей на множестве шифруемых текстов X.

При изучении энтропий открытых и шифрованных текстов ранее было показано, что условие совершенства шифра (Х,К,У,Г) равносильно условию: Н(Х/У)=Н(Х).

Вряде случаев понятие теоретической стойкости шифра трактуют

иподругому.

Теоретически стойкими шифрами относительно криптографических методов определения открытых текстов считаются те шифры, для которых эти методы приводят к неоднозначному определению открытых (содержатель­ ных) текстов. Например, теоретически стойкими шифрами относительно ме­ тодов, приводящих к чтению текстов в колонках, считаются шифры, для ко­ торых доказана неоднозначность такого чтения.

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

228

ГЛАВА 5. ПРАКТИЧЕСКАЯ СТОЙКОСТЬ ШИФРОВ

«Надежна ли шифрсистема, если криптоаналитик располагает ограниченным временем и ограни­ ченными вычислительными воз­ можностями для анализа перехва­ ченных криптограмм?»

К. Шеннон

Параграф 5.1 Понятие практической стойкости шифров

(/П р о /,/Ф о м /)

Правила криптоаналйза были сформулированы еще в конце XIX века преподавателем немецкого языка в Париже голландцем Керкхофом в книге «Ьа СгурЮ§гарЫе пгпШаге». Согласно одному из этих правил разработчик шифра должен оценивать криптографические свойства шифра в предположении, что не только шифртекст известен противнику (криптоаналитику противника), но известен и алгоритм шифрования, а секретным для него является лишь ключ.

Основными количественными мерами стойкости шифра служат так на­ зываемые «трудоемкость метода криптографического анализа» и «надежность его». Обозначим через А - класс применимых к шифру алгоритмов дешифро­ вания и через Т(ф) - трудоемкость реализации алгоритма <р на некотором вы­ числительном"устройстве.

Трудоемкость дешифрования. Данная трудоемкость обычно измеряется усредненным по ключам шифра и открытым текстам количеством времени или условных вычислительных операций, необходимых для реализации алгоритма. За трудоемкость дешифрования принимают величину

т т Е Т ( ф ) .

среА

Последняя величина (по определению) совпадает со средней трудоемкостью ЕТ(ф) лучшего из известных и применимых к шифру алгоритмов. При попытке практического использования этой формулы выявляются некоторые проблемы.

229

Поясним более подробно введенное понятие. Алгоритмы дешифрова­ ния применяются обычно к входным данным. В нашем случае это шифрован­ ныйтекст «у» и шифр. Следовательно, результатом применения алгоритма до­ лжен быть открытый текст. Наша же цель состоит в определении трудоемкости - времени Т(ф), требуемого на реализацию алгоритма. Возможно, что Т(ф) бу­ дет зависеть от ряда дополнительных параметров, например, от шифртекста «у» и от порядка опробования ключей в алгоритме. Криптоанализ проводится, как правило, без наличия конкретного шифртекста и без прямой реализации алгоритма. Сам алгоритм в ряде случаев становится вероятностным алгорит­ мом, в его фрагментах используются вероятностные правила принятия реше­ ния о выполнении последующих действий, например, опробование ключей. Таким образом, умозрительное построение процесса нахождения открытого текста шифра скорее всего следует назвать методом (криптографическим ме­ тодом) решения задачи. В предположении о вероятностных распределениях случайных действий алгоритма и неизвестных нам входных данных алгоритма, атакже вероятностных характеристик выбора ключа в шифре при зашифрова­ нии случайного открытого текста подсчитывается среднее число операций (действий) алгоритма, которое и называется трудоемкостью метода криптоа­ нализа. При фиксации в предположениях вычислительных способностей про­ тивника (производительность ЭВМ, объем возможных памятей и т. д.) это сре­ днее число операций адекватно переводится в среднее время, необходимое для дешифрования шифра.

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

Конечно, используют и другие характеристики эффективности методов криптоанализа, например, вероятность дешифрования за время, не превосхо­ дящее Т. -

Под количественной мерой криптографической стойкости шифра понима­ ется наилучшая пара (Т(ф),я(ф)) из всех возможных методов криптографичес­ кого анализа шифра. Смысл выбора наилучшей пары состоит в том, чтобы вы­ брать метод с минимизацией трудоемкости и одновременно максимизацией его надежности.

230

Предположения о возможностях противника.

Криптограф, оценивая стойкость шифра, как правило, имитирует атаку на шифр со стороны криптоаналитика противника. Для этого он строит модель действий и возможностей противника, в которой максимально учитываются интеллектуальные, вычислительные, технические, агентурные и другие возмо­ жности противника. Примером такого подхода может служить случай в США в конце 70-х годов, Криптографы не нашли практически приемлемого алгоритма дешифрования «ОЕ8-алгоритма». Но небольшой размер ключа БЕЗ-алгоритма

не позволил прогнозировать его практическую стойкость как достаточную на длительный срок, что привело к решению отказаться от использования БЕ8-

алгоритма в государственных учреждениях для защиты информации.

Учет интеллектуальных возможностей противника нередко прояв­

ляется в постановках задач криптоанализа шифра. В шифрах гаммирования не­ редко оценивают трудоемкости и надежности методов определения открытого текста по параметрам эффективности методов определения ключа по известной гамме наложения (или, что то же самое, по известным открытому и шифрован­ ному текстам). Аналогично иногда поступают и с другими поточными шифра­ ми, например, при анализе шифров поточной замены переходят к решению за­ дачи определения ключа по известной управляющей последовательности шиф­ рующего блока. В задачах чтения открытого текста по шифрованному тексту иногда «добавляют» и другой известной информации, облегчающей нахожде­ ние решения задачи. Таким образом, учет интеллектуальных возможностей противника проводится путем постановки и решения «облегченных» задач криптоанализа. При этом полагают, что криптографическая стойкость шифра, вычисленная по таким «облегченным» задачам, не превышает стойкости шиф­ ра, анализируемого в реальных условиях эсплуатации. Нередко в качестве та­ ких задач выделяют задачи, возникающие на промежуточных этапах анализи­ руемого метода криптоанализа. Примерами таких задач являются разнообраз­ ные математические задачи, к которым сводится метод криптоанализа, напри­ мер, задача решения систем нелинейных уравнений в разнообразных алгебраи­ ческих структурах, определение начального состояния автомата По его выход­ ной и входной последовательностям, определение входной последовательнос­ ти автомата по его начальному состоянию и выходной последовательности и др. Нахождение эффективных алгоритмов решения какой-либо из этих матема­ тических задач может значительно понизить криптографическую стойкость многих шифров.

Учет старения дешифруемой информации. Что лучше? Дешифровать

за 5 лет 5 телеграмм или за один год одну телеграмму? Ответ на этот вопрос неоднозначен. Конечно, чем больше дешифрованной информации, тем лучше,