Решение задач по определению стойкости шифров

Задача 1.

На основе моделей открытых текстов на русском языке вычислить их энтропии Н ₀, Н ₁.

Определение.

Энтропия языка – мера средней информации, приходящейся на одну букву открытого текста языка. Находится в соответствии с выражением:

Решение.

а) Для нахождения H ₀ выбираем n =32 (с пробелом, но без ъ и ё); p_i =1/32.

б) Для нахождения H ₁ принимаем n =32 (с пробелом, но без ъ и ё); p_i берем из [1] (страница 438).

 

Задача 2.

С учетом оценки энтропии языка величиной Н ₁, вычисленной для позначной модели открытого текста, определить расстояние единственности для шифра простой замены на русском языке.

Определение.

Расстояние единственности для шифра определяется в соответствии с выражением:

где: - расстояние единственности для шифра;

- количество возможных ключей;

n - количество букв в алфавите;

- избыточность языка, определяется в соответствии с выражением:

H_L - энтропия языка. В конкретной данной задаче выбираем полученное значение для H ₁ из задачи 1.

Решение.

Количество возможных ключей находим из комбинаторики. Здесь мы имеем размещения без повторений 32 из 32

В нашем случае (К=32!). H в примере берем 4, 339 (при решении задачи необходимовыбирать значение, полученное в задаче 1, а именно 4.357).

 

Выводы:

1. Избыточность языка означает, что при оптимальном кодировании текста его можно сжать на (R*100)%.

2. Расстояние единственности – средняя длина шифртекста, необходимая для однозначного восстановления истинного ключа (без каких-либо ограничений на время его нахождения). С ростом длины шифротекста число ложных ключей уменьшается.

3. Расстоянием единственности шифра называют такую длину шифртекста, начиная с которой число ложных ключей становится равным нулю. Другими словами, это средний объем шифротекста, необходимый для однозначного вскрытия ключа атакующим, имеющим неограниченные вычислительные ресурсы. Для абсолютно стойких криптосистем L= ∞.

 

Объяснить отличие полученных результатов от вычислений для асимптотических значений энтропии языка.

 

Задача 3.

Рассчитать оценку расстояния единственности для шифра, если известно, что деловое сообщение на русском языке, закодированное байтовым кодом, зашифровано криптоалгоритмом ГОСТ 28147-89 в режиме простой замены (длина блока, используемого для кодирования открытого сообщения составляет 64 бит, длина ключа – 256 бит). Чем объясняется малое расстояние единственности для данного случая? Какими методами можно его увеличить?

Решение.

Расстояние единственности для шифра определяется в соответствии с выражением:

где:

=2²⁵⁶ (256 бит ключа – из комбинаторики);

=2⁶⁴ – шифрование в режиме простой замены;

H_L =83, 4 (деловой текст на русском языке –таблица 1 для данной лабораторной работы). В нашем случае 64 бита открытого текста воспринимаются как один символ. Для его обозначения введем понятие макросимвол. Энтропия, приходящаяся на этот макросимвол равна H *8 бит. n =2⁶⁴ – количество возможных макросимволов.

Расстояние единственности определяется для макросимвола.

От макросимволовнеобходимо перейти к битам.

Т.е. расстояние единственности дляГОСТ 28147-89 в режиме простой замены составляет 285, 635 бита.

 

Повысить L можно уменьшив избыточность сообщения: архивированием, использованием оптимального кодирования (кода Хаффмена, кода Фано). Например, при получении избыточности 0, 1% имеем расстояние единственности:

=2, 56

 

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

 

Задача 4.

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

Подсказка.

Данная задача из области комбинаторики. Основные выражения, необходимые для решения задачи:

а) Число перестановок порядка n равно n!

(оно же количество размещений без повторений из n по n). Это число указывает на количество вариантов заполнения одной строки латинского (русского квадрата) алфавитом, состоящим из n символов.

б) Количество размещений с повторениями из n по k равно n^k.

Это число указывает на количество различных гамм длины n, которые могут быть составлены из алфавита, состоящего из k символов.

Решение.

В качестве избыточности языка примем избыточность языка в целом 72, 6 [1].

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

а) Для текста длиной n =33 символа получим:

Количество ключей вычисляется как количество способов заполнения латинского квадрата плюс количество различных гамм, использующих этот квадрат. При вычислении избыточности принимаем энтропию языка, умноженную на количество символов в макросимволе. Таким образом, получаем энтропию макросимвола. nⁿ - это количество возможныхмакросимволов. Далее вычисляем L. Получаем расстояние единственности.

 

s w: val=" 28" /> < w: vertAlign w: val=" superscript" /> < w: lang w: val=" EN-US" /> < /w: rPr> < m: t> R=0, 728< /m: t> < /m: r> < /m: e> < /m: mr> < /m: m> < /m: oMath> < /m: oMathPara> < /w: p> < w: sectPr wsp: rsidR=" 00000000" > < w: pgSz w: w=" 12240" w: h=" 15840" /> < w: pgMar w: top=" 1134" w: right=" 850" w: bottom=" 1134" w: left=" 1701" w: header=" 720" w: footer=" 720" w: gutter=" 0" /> < w: cols w: space=" 720" /> < /w: sectPr> < /w: body> < /w: wordDocument> ">

 

L=1.373 означает, что расстояние единственности для шифра табличного (модульного) гаммирования, заданного латинским (русским) квадратом равно 1.373 макросимвола, или 45.304 буквы.

б) Для текста длиной 2 n =66 символов аналогично имеем:

Макросимвол будет включать в себя 66 букв.

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

 

Задача 5.

Рассчитать расстояние единственности для шифра, если известно, что деловое сообщение на французском языке, закодированное байтовым кодом, зашифровано криптоалгоритмомDES в режиме электронной кодовой книги (длина блока, используемого для кодирования открытого сообщения составляет 64 бит, длина ключа – 56 бит).

Подсказка.

Режим электронной кодовой книги (ECB – ElectronicCodeBook) отвечает обычному использованию DES как блочного шифра, осуществляющего некоторую простую замену блоков открытого текста.

Решение.

См. задачу 3, данная задача решается аналогично.

 

3. Контрольные вопросы

1. Понятие криптографической стойкости

2. Понятиеатаки на криптосистему

3. Что такое Практическая и Теоретическая стойкость шифра?

4. Что такое Хеш-функции? Ключевые и бесключевые хэш-функции.

5. Понятие энтропии. Формула нахождения. Физический смысл. Понятие энтропии языка.

6. Понятие избыточность языка. Формула нахождения. Физический смысл.

7. Понятие расстояния единственности для шифра. Формула нахождения. Физический смысл.

8. Понятие имитостойкостишифра.