Источники случайных чисел

Непредсказуемость

Случайность

Требования к случайным числам

Большинство алгоритмов сетевой безопасности, основанных на криптографии, используют случайные числа. Например:

1. Схемы взаимной аутентификации. В большинстве сценариев аутентификации и распределения ключа используются nonсes для предотвращения атак повтора (replay-атак). Применение действительно случайных чисел в качестве nonces не дает противнику возможности вычислить или угадать nonce.

2. Ключ сессии, созданный KDC или кем-либо из участников.

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

Обычно при создании последовательности псевдослучайных чисел предполагается, что данная последовательность чисел должна быть случайной в некотором определенном статистическом смысле. Следующие два критерия используются для доказательства того, что последовательность чисел является случайной:

1. Однородное распределение: распределение чисел в последовательности должно быть однородным; это означает, что частота появления каждого числа должна быть приблизительно одинаковой.

2. Независимость: ни одно значение в последовательности не должно зависеть от других.

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

В приложениях, таких как взаимная аутентификация и генерация ключа сессии, нет жесткого требования, чтобы последовательность чисел была статистически случайной, но члены последовательности должны быть непредсказуемы. При "правильной" случайной последовательности каждое число статистически не зависит от остальных чисел и, следовательно, непредсказуемо. Однако правильные случайные числа на практике используются достаточно редко, чаще последовательность чисел, которая должна быть случайной, создается некоторым алгоритмом. В данном случае необходимо, чтобы противник не мог предугадать следующие элементы последовательности, основываясь на знании предыдущих элементов и используемого алгоритма.

Источники действительно случайных чисел найти трудно. Физические генераторы шумов, такие как детекторы событий ионизирующей радиации, газовые разрядные трубки и имеющий течь конденсатор могут быть такими источниками. Однако эти устройства в приложениях сетевой безопасности применяются ограниченно. Проблемы также вызывают грубые атаки на такие устройства. Альтернативным решением является создание набора из большого числа случайных чисел и опубликование его в некоторой книге. Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с тем количеством, которое требуется приложениям сетевой безопасности. Более того, хотя наборы из этих книг действительно обеспечивает статистическую случайность, они предсказуемы, так как противник может получить их копию.

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

Рассмотрим несколько алгоритмов генерации случайных чисел.

Дата добавления: 2014-12-23