Генераторы псевдослучайных чисел
Первой широко используемой технологией создания случайного числа был алгоритм, предложенный Лехмером, который известен как метод линейного конгруента. Последовательность случайных чисел {Xn} получается с помощью следующего итерационного равенства:
Xn+1 = (a Xn + c) mod m
Если m, а и с являются целыми, то создается последовательность целых чисел в диапазоне 0 Xn < m.
Выбор значений для а, с и m является критичным для разработки хорошего генератора случайных чисел.
Очевидно, что m должно быть очень большим, чтобы была возможность создать много случайных чисел. Считается, что m должно быть приблизительно равно максимальному положительному целому числу для данного компьютера. Таким образом, обычно m близко или равно 231.
Существует три критерия, используемые при выборе генератора случайных чисел:
Функция должна создавать полный период, т.е. все числа между 0 и m до того, как создаваемые числа начнут повторяться.
Создаваемая последовательность должна появляться случайно. Последовательность не является случайной, так как она создается детерминированно, но различные статистические тесты, которые могут применяться, должны показывать, что последовательность случайна.
Функция должна эффективно реализовываться на 32-битных процессорах.
Значения а, с и m должны быть выбраны таким образом, чтобы эти три критерия выполнялись. В соответствии с первым критерием можно показать, что если m является простым и с = 0, то при определенном значении а период, создаваемый функцией, будет равен m-1. Для 32-битной арифметики соответствующее простое значение m = 231 - 1. Таким образом, функция создания псевдослучайных чисел имеет вид:
Xn+1 = (a Xn) mod (231 - 1)
Только небольшое число значений а удовлетворяет всем трем критериям. Одно из таких значений есть а = 75 = 16807, которое использовалось в семействе компьютеров IBM 360. Этот генератор широко применяется и прошел более тысячи тестов, больше, чем все другие генераторы псевдослучайных чисел.
Сила алгоритма линейного конгруента в том, что если сомножитель и модуль (основание) соответствующим образом подобраны, то результирующая последовательность чисел будет статистически неотличима от последовательности, являющейся случайной из набора 1, 2, ..., m-1. Но не может быть случайности в последовательности, полученной с использованием алгоритма, независимо от выбора начального значения Х0. Если значение выбрано, то оставшиеся числа в последовательности будут предопределены. Это всегда учитывается при криптоанализе.
Если противник знает, что используется алгоритм линейного конгруента, и если известны его параметры (а = 75, с = 0, m = 231 - 1), то, если раскрыто одно число, вся последовательность чисел становится известна. Даже если противник знает только, что используется алгоритм линейного конгруента, знания небольшой части последовательности достаточно для определения параметров алгоритма и всех последующих чисел. Предположим, что противник может определить значения Х0, Х1, Х2, Х3. Тогда :
Х1 = (а Х0 + с ) mod m
Х2 = (а Х1 + с ) mod m
Х3 = (а Х2 + с ) mod m
Эти равенства позволяют найти а, с и m.
Таким образом, хотя алгоритм и является хорошим генератором псевдослучайной последовательности чисел, желательно, чтобы реально используемая последовательность была непредсказуемой, поскольку в этом случае знание части последовательности не позволит определить будущие ее элементы. Эта цель может быть достигнута несколькими способами. Например, использование внутренних системных часов для модификации потока случайных чисел. Один из способов применения часов состоит в перезапуске последовательности после N чисел, используя текущее значение часов по модулю m в качестве нового начального значения. Другой способ состоит в простом добавлении значения текущего времени к каждому случайному числу по модулю m.
- 1. Понятие информационной безопасности
- 2. Важность и сложность проблемы информационной безопасности
- 3. Основные составляющие информационной безопасности
- 4. Категории информационной безопасности
- 5. Требования к политике безопасности в рамках iso
- 6. Общие сведения о стандартах серии iso 27000
- Разработчики международных стандартов
- Русские переводы международных стандартов
- 7. Iso 15408 - Общие критерии оценки безопасности информационных технологий
- 8. Iso 18028 - Международные стандарты сетевой безопасности серии
- Iso/iec 18028-1:2006 Информационные технологии. Методы обеспечения безопасности. Сетевая ит безопасность. Управление сетевой безопасностью.
- Iso/iec 18028-5:2006 Информационные технологии. Методы обеспечения безопасности. Защита сетевых взаимодействий при помощи Виртуальных Частных Сетей
- 9. Российские стандарты гост
- 10. Модель сетевого взаимодействия
- 11. Модель безопасности информационной системы
- 12. Классификация криптоалгоритмов
- 13. Алгоритмы симметричного шифрования
- 14. Криптоанализ
- Дифференциальный и линейный криптоанализ
- 15. Используемые критерии при разработке алгоритмов
- 16. Сеть Фейштеля
- 17. Алгоритм des Принципы разработки
- Проблемы des
- 18. Алгоритм idea
- Принципы разработки
- Криптографическая стойкость
- 21. Создание случайных чисел
- 22. Требования к случайным числам
- Случайность
- Непредсказуемость
- Источники случайных чисел
- Генераторы псевдослучайных чисел
- Криптографически созданные случайные числа
- Циклическое шифрование
- Режим Output Feedback des
- Генератор псевдослучайных чисел ansi x9.17
- 23. Разработка Advanced Encryption Standard (aes) Обзор процесса разработки aes
- Обзор финалистов
- Критерий оценки
- Запасной алгоритм
- Общая безопасность
- 25. Основные способы использования алгоритмов с открытым ключом
- Алгоритм rsa
- 27. Алгоритм обмена ключа Диффи-Хеллмана
- 28. Транспортное кодирование
- 29. Архивация
- Требования к хэш-функциям
- 31. Цифровая подпись Требования к цифровой подписи
- Прямая и арбитражная цифровые подписи
- 32. Симметричное шифрование, арбитр видит сообщение:
- 33. Симметричное шифрование, арбитр не видит сообщение:
- 34. Шифрование открытым ключом, арбитр не видит сообщение:
- 35. Стандарт цифровой подписи dss
- Подход dss
- 36. Отечественный стандарт цифровой подписи гост 3410
- 37. Алгоритмы распределения ключей с использованием третьей доверенной стороны Понятие мастер-ключа
- 38. Протоколы аутентификации
- Взаимная аутентификация
- 39. Элементы проектирования защиты сетевого периметра.
- 40. Брандмауэр и маршрутизатор.
- 41. Брандмауэр и виртуальная частная сеть.
- 42. Многоуровневые брандмауэры.
- 43. Прокси-брандмауэры.
- 44.Типы прокси.
- 46.Недостатки прокси-брандмауэров.
- 48. Виртуальные локальные сети.
- 49. Границы виртуальных локальных сетей.
- 50. Частные виртуальные локальные сети.
- 51. Виртуальные частные сети.
- 52. Основы построения виртуальной частной сети.
- 53. Основы методологии виртуальных частных сетей.
- 54. Туннелирование.
- 55. Защита хоста.
- 56. Компьютерные вирусы
- Структура и классификация компьютерных вирусов
- 2.3.3. Механизмы вирусной атаки
- 58. Протокол ррр рар
- 59. Протокол ррр chap
- 60. Протокол ррр еар
- 68. Виртуального удаленного доступа
- 69. Сервис Директории и Служб Имен
- 70. По и информационная безопасность
- 71. Комплексная система безопасности. Классификация информационных объектов