17.2. Общие определения и теория

№task-number1task-section.task-number. Рассмотрим множество паролей, состоящих из 12 строчных и заглавных латинских букв, а также цифр.

• 1pt 0pt 0pt
• Каков размер этого множества?
• Сколько времени потребуется на взлом шифртекста, зашифрованного данным паролем, если предположить, что во взломе участвуют все компьютеры мира (7 млрд.), а средний компьютер перебирает 300 000 паролей в секунду?См. скорости перебора MD5-хешей на странице http://openwall.info0pt/wiki0pt/john0pt/benchmarks.
• Каковы затраты электроэнергии в денежном эквиваленте, если средний компьютер потребляет мощность 400 Вт, а стоимость 1 кВт$\times$час составляет 4,68 рубля?

Решение:

• 1pt 0pt 0pt
• общее количество символов: $26 + 26 + 10 = 62$;
• общее количество паролей: $62^{12} \approx 3{,}226\times 10^{21}$;
• время на перебор: $62^{12} / (3 \times 10^5) / (7 \times 10^9 ) \approx 1{,}54 \times 10^{6}$ сек.;
  • 1pt 0pt 0pt
  • в минутах: $\approx 25605$;
  • в часах: $\approx 427$;
  • в днях: $\approx 18$;
• стоимость: $427 \times (7 \times 10^9 ) \times 0{,}4 \times 4{,}68 \approx 5{,}59 \times 10^{12}$ руб.

Ответ: паролей $3{,}226 \times 10^{21}$; на перебор нужно $1{,}54 \times 10^6$ секунд ($\approx 18$ дней); затраты – 5,6 триллиона рублей.

№task-number1task-section.task-number. Источник открытого текста характеризуется случайной величиной $X$, принимающей два значения $x_1$ и $x_2$ с вероятностями $p \left( x = x_1 \right) = 1/5$ и $p \left( x = x_2 \right) = 4/5$ соответственно. Источник ключей характеризуется случайной величиной $Z$, независимой от величины $X$, принимающей два значения $z_1$ и $z_2$ с вероятностями $p \left( z = z_1 \right) = 1/6$ и $p \left( z = z_2 \right) = 5/6$ соответственно. Функция шифрования $E_{z} \left( x \right)$ задаётся следующими правилами: $\left( x_1, z_1 \right) \to y_1$, $\left( x_1, z_2 \right) \to y_2$, $\left( x_2, z_1 \right) \to y_2$, $\left( x_2, z_2 \right) \to y_1$.

1. 1pt 0pt 0pt
2. Найдите собственную информацию каждого из сообщений открытого текста в битах.
3. Найдите энтропию источника сообщений, источника ключей и шифртекста в битах.
4. Найдите взаимную информацию открытого текста и ключа в битах.
5. Найдите взаимную информацию открытого текста и шифртекста в битах.
6. Найдите взаимную информацию ключа и шифртекста в битах.
7. Найдите апостериорное распределение вероятностей открытого текста для обоих вариантов перехваченных злоумышленником шифртекстов $y_1$ и $y_2$. Используя вычисленные значения, определите, является ли данная шифросистема абсолютно надёжной. Если нет, то что в данной криптосистеме необходимо поменять? Покажите, что апостериорные вероятности после доработки будут удовлетворять необходимым требованиям абсолютно надёжной криптосистемы.

Ответ:

• 1pt 0pt 0pt
• $I \left( x_1 \right) = \log_2 5 = 2{,}322$ бит; $I \left( x_2 \right) = \log_2 5/4 = 0{,}322$ бит;
• $H \left( X \right) = 0{,}722$ бит; $H \left( Z \right) = 0{,}650$ бит; $H \left( Y \right) = 0{,}881$ бит;
• $I \left( X ; Z \right) = 0$ бит; $I \left( X; Y \right) = 0{,}231$ бит; $I \left( Y; Z \right) = 0{,}159$ бит;
• $p \left( x_1 | y_1 \right) = 1/21$; $p \left( x_2 | y_1 \right) = 20/21$; $p \left( x_1 | y_2 \right) = 5/9$; $p \left( x_2 | y_2 \right) = 4/9$; не является.