Все о геологии :: на главную страницу! Геовикипедия 
wiki.web.ru 
Поиск  
   Rambler's Top100 Service
 Главная страница  Конференции: Календарь / Материалы  Каталог ссылок    Словарь       Форумы        В помощь студенту     Последние поступления
   Геология | Книги
 Обсудить в форуме  Добавить новое сообщение
Next: Где взять истинно случайную Up: 6.3. Как зашифровать файл? Previous: А можно ли обойтись Contents: Содержание

Где взять ключи?

Каким должен быть ключ шифрования? Случайным и равновероятным. А как получить случайную и равновероятную последовательность символов? Правильно, с помощью генератора случайных чисел. Написать свой генератор ``случайных'' чисел очень просто. Хорошие по статистическим свойствам последовательности получаются по формуле линейного конгруэнтного метода:

\begin{displaymath} r_{n+1} = (ar_n + b) \mod{m}, \end{displaymath}

где $ r_i$ - $ i$-й член псевдослучайной последовательности; $ a$, $ b$, $ m$ - некоторые целые числа.

Качество псевдослучайной последовательности зависит от выбора чисел $ a$, $ b$ и $ m$. Эти числа обязательно должны быть взаимно просты. Есть и другие правила выбора этих коэффициентов, о них можно прочитать в [1]. В Diskreet, например, используется следующий генератор псевдослучайной последовательности:

\begin{displaymath} r_{n+1}= (214013r_n + 2531011) \mod{2^{32}}. \end{displaymath}

Как видите, формула для получения очередного ``случайного'' числа рекурсивна - каждый член последовательности зависит от предыдущего. Возникает вопрос: откуда берется первый член? Обычно в качестве $ r_1$ берут текущее время с точностью до тика таймера (0,054945 сек.). Если для генерации ключа используется линейный конгруэнтный метод, ключом является последовательность чисел $ (r_1, r_2,\dots,r_N)$, где

\begin{displaymath} N= \frac{\text{(длина ключа)}}{\text{(длина $r_i$ в байтах)}}. \end{displaymath}

Предположим, что с помощью линейного конгруэнтного метода сгенерирована последовательность $ (r_1, r_2, \dots, r_{128})$, где каждое $ r_i$ есть короткое целое число (16 бит). Созданный ключ представляет собой случайную равновероятную последовательность длиной 256 байт. Оценим, сколько различных вариантов ключа можно получить по данной схеме.

Зафиксируем значение $ r_1$. Какие значения может принимать $ r_2$? Только одно значение. Если $ r_1$ фиксировано, то значение $ r_2$ определено однозначно:

\begin{displaymath} r_2 = (ar_1 + b) \mod{m}. \end{displaymath}

Значение $ r_3$ тоже определено однозначно. Оно равно

\begin{displaymath} r_3 = (ar_2 + b) \mod{m}= (a ((ar_1 + b) \mod{m}) + b) \mod{m}. \end{displaymath}

Таким образом, значение $ r_1$ однозначно определяет значения всех следующих членов последовательности. Получается, что различных последовательностей $ (r_1, r_2,\dots,r_{128})$ в точности столько же, сколько различных значений $ r_1$. В нашем примере $ r_1$ - короткое целое число, принимающее значения от 0 до $ 2^{16}-1=65535$. Оказывается, что стойкость ключевой системы (число различных вариантов ключа) равна не $ 2^{256}$, а всего лишь $ 2^{16}$, что в $ 1{,}77 \cdot10^{72}$ раз меньше!

Получается, что псевдослучайные последовательности в качестве ключей использовать нельзя. А что можно?

В чем слабость псевдослучайных последовательностей? В том, что они псевдослучайны. Первый член последовательности однозначно определяет остальные. Чтобы ключ был по-настоящему случайным и равновероятным, последовательность должна быть не псевдослучайной, а истинно случайной.

Next: Где взять истинно случайную Up: 6.3. Как зашифровать файл? Previous: А можно ли обойтись Contents: Содержание

Проект осуществляется при поддержке:
 Геологического факультета МГУ,
РФФИ
    
TopList Rambler's Top100