Бабаш А.В., Шанкин Г.П. Криптография (распознано не всё)
.pdf221 |
|
лНЬ |
|
|К| — =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 телеграмм или за один год одну телеграмму? Ответ на этот вопрос неоднозначен. Конечно, чем больше дешифрованной информации, тем лучше,