Генерация случайных чисел в Java


Генерация случайных чисел в Java

Существует несколько способов генерации случайного (псевдослучайного) числа:

  1. Использование метода random() из класса математических функций Math , находящемся в пакете java.lang.
  1. Использование метода random() из класса Random , находящемся в пакете java.util.Random.
  1. Использование генератора случайных чисел класса SecureRandom , предназначенного для целей криптографии и, находящегося в пакете java.security. SecureRandom (здесь не рассматривается).

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

Класс Math. Метод random()

Метод random() класса Math возвращает псевдослучайное число типа double в диапазоне 0 ≤ Math.random()

Пример 1. Несколько случайных чисел

Случайное число № 1: 0.9161994380531232
Случайное число № 2: 0.24340742865928744
Случайное число № 3: 0.9783627451986034

Пример 2. Случайное число x в диапазоне a ≤ x ≤ b

Для генерации целого случайного числа x в заданном диапазоне a ≤ x ≤ b, обычно используется следующая зависимость:

x = a + (int)(Math.random()*((b — a) + 1)).

Получим случайное число x в диапазоне: 10 ≤ x ≤ 20 (a=10, b=20).

Результат.
Случайное число x: 19

Класс Random. Метод random()

Это наиболее часто используемый класс для генерации псевдослучайный чисел с равномерной функцией распределения. Имеется метод nextGaussian() , который моделирует функцию нормального распределения.

Основными методами этого класса являются:

  • int nextInt( ) — возвращает следующее случайное значение ix типа int в диапазоне -2147483648 ≤ ix
  • int nextInt(int n) — возвращает следующее случайное значение ix типа int в диапазоне 0 ≤ ix
  • float nextFloat() — возвращает следующее случайное значение fx типа float в диапазоне 0.0 ≤ fx
  • double nextDouble() — возвращает следующее случайное значение dx типа double в диапазоне 0.0 ≤ dx
  • boolean nextBoolean() — возвращает следующее случайное значение типа boolean
Для получения случайных чисел необходимо:
  1. Подключить библиотеку случайных чисел. Пишем до определения класса.
    import java.util.Random;
  2. В классе создать объект rand случайных чисел
    Random rand = new Random();
  3. Далее использовать необходимые методы объекта rand.

Пример 1. Несколько случайных чисел разных типов.


Случайное число ix: 1438841988 Случайное число dx: 0.6120986135409442 Случайное число fx: 0.103119016 Случайное число bx: true

Пример 2. Случайное число x в диапазоне a ≤ x ≤ b.

Для генерации целого случайного числа x в заданном диапазоне a ≤ x ≤ b, обычно используется следующая зависимость:

тип int int x = a + rand.nextInt(b — a + 1).

тип double double y = a + rand.nextInt(b — a).

Случайное число x: 12 Случайное число dx: 17.505847041626733

Для типа double будет выведено случайное число в виде:

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

Форматный вывод

Пакет java.io содержит класс PrintStream , который содержит методы printf и forma t, позволяющие выводить числа с заданной точностью. Рассмотрим метод format(). Синтаксис метода

System.out.format(String format, Object. args),

format — это строка — шаблон, согласно которому будет происходить форматирование, args — это список переменных, для вывода по заданному шаблону.

Строка — шаблон содержит обычный текст и специальные форматирующие символы. Эти символы начинаются со знака процента (%) и заканчиваются конвертором — символом, который определяет тип переменной для форматирования. Вот некоторые конверторы:

Блог только про Java

Учимся программировать на Java с нуля

Генерация случайных чисел Java

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

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

— nextBoolean()
— nextInt()
— nextLong()
— nextFloat()
— nextDouble()

Стоит отметить, что вещественные числа генерируются только в промежутке с 0 до 1, а целочисленные по всему спектру значений. Кроме того, целые числа можно генерировать в диапазоне с 0 до max — 1: nextInt(max).
Заполним массив байт случайными значениями:

Создать рандом в диапазоне от 5 до 50

01.10.2015, 11:18

Рандом в диапазоне
Всем привет. Ниже приведен рабочий код, который генерирует 3 колонки по 7 ячеек рандомных чисел в.

Задать рандом в диапазоне с шагом
У меня есть диапазон и шаг и шаг de(Я их считаю в программе). Помогите задать рандом. Я пробовал.

Как сделать Рандом в диапазоне?
Нужно сделать так, чтобы вопросы выводились в случайном порядке, заранее спасибо. Код: .

Как задать рандом в диапазоне?
Сделал переменную rnd = 7 + rand() % 10 По идее должны генерироваться числа от 7 до 10, но.

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

Генерация уникальных случайных чисел в Java

Я пытаюсь получить случайные числа от 0 до 100. Но я хочу, чтобы они были уникальными, а не повторялись в последовательности. Например, если я получил 5 номеров, они должны быть 82,12,53,64,32, а не 82,12,53,12,32 Я использовал это, но он генерирует те же числа в последовательности.

16 ответов


  • Добавьте каждое число в диапазоне последовательно в списке .
  • Shuffle it.
  • Возьмите первый ‘n’.

Вот простая реализация. Это напечатает 3 уникальных случайных числа из диапазона 1-10.

Первая часть исправления с оригинальным подходом, как отметил Марк Байерс в удаленном ответе, состоит в использовании только одного Random экземпляр.

Вот что делает цифры одинаковыми. Экземпляр Random заполняется текущим временем в миллисекундах. Для определенного значения начального числа экземпляр ‘random’ вернет точно такую ​​же последовательность псевдослучайных чисел.

В Java 8+ вы можете использовать ints метод Random для получения IntStream случайных значений, а затем distinct и limit , чтобы уменьшить поток до числа уникальных случайных значений.

Random также имеет методы, которые создают LongStream s и DoubleStream s, если они вам нужны.

Если вы хотите, чтобы все (или большое количество) чисел в диапазоне находились в случайном порядке, может быть более эффективно добавить все числа в список, перемешать его и взять первые n, поскольку приведенный выше пример в настоящее время реализуется путем генерации случайных чисел в запрошенном диапазоне и передачи их через набор (аналогично ответу Роба Килти ), который может потребоваться генерировать намного больше, чем сумма, передаваемая для ограничения, потому что вероятность генерирования нового уникального числа уменьшается с каждым найденным. Вот пример другого способа:

  1. Создайте массив из 100 чисел, затем рандомизируйте их порядок.
  2. Разработайте генератор псевдослучайных чисел с диапазоном 100.
  3. Создайте логический массив из 100 элементов, а затем установите значение true при выборе этого числа. Когда вы выбираете следующее число, проверьте массив и повторите попытку, если установлен элемент массива. (Вы можете создать простой в очистке логический массив с массивом long , в котором вы перемещаетесь и маскируете для доступа к отдельным битам.)

Используйте Collections.shuffle() на все 100 номеров и выберите первые пять, как показано здесь .

Я чувствую, что этот метод стоит упомянуть.

Я пересмотрел ответ Ананда, чтобы использовать не только уникальные свойства набора, но и использовать логическое ложное значение, возвращаемое set.add() когда не удается добавить в набор.

Я сделал это так.

Я пришел сюда из другого вопроса, который дублировал этот вопрос ( Генерация уникального случайного числа в Java )

Храните от 1 до 100 номеров в массиве.

Генерирует случайное число от 1 до 100 в качестве позиции и возвращает массив [position-1], чтобы получить значение

Как только вы используете число в массиве, пометьте значение как -1 (нет необходимости поддерживать другой массив, чтобы проверить, используется ли этот номер уже)

Если значение в массиве равно -1, снова получите случайное число, чтобы получить новое местоположение в массиве.

Один умный способ сделать это — использовать показатели примитивного элемента в модуле.

Например, 2 является примитивным корневым модом 101, что означает, что полномочия 2 мода 101 дают неповторяющуюся последовательность, которая видит каждое число от 1 до 100 включительно:

В коде Java вы должны написать:

Найти примитивный корень для определенного модуля может быть непросто, но функция «primroot» в Maple сделает это за вас.

All my circuits

Реклама

воскресенье, 22 сентября 2013 г.


Генерация случайного числа в заданном диапазоне в Java

Для генерации целого случайного числа в заданном диапазоне от Min до Max, обычно используется следующий паттерн:

Min + (int)(Math.random() * ((Max — Min) + 1))

В Java метод Math.random() генерирует число типа double в диапазоне [0,1). Обратите внимание, что 1 не входит в этот диапазон!
Чтобы получить определенный диапазон значений, сначала нужно умножить на разницу между максимумом и минимумом

Math.random() * ( Max — Min )

Это вернет нам значение в диапазоне [0,Max-Min).
К примеру, если мы хотим получить целые значения [5,10], нам нужно покрыть диапазон в 5 целых(int) значений. То есть:

Данный пример будет генерировать значения в диапазоне [0,5).
Теперь нам нужно сдвинуть этот диапазон, чтобы минимальное значение соответствовало желаемому. Для этого мы просто добавляем значение минимума

Min + (Math.random() * (Max — Min))

Теперь мы получим значение в диапазоне [Min,Max). Продолжая наш пример, это будет [5,10):

5 + (Math.random() * (10 — 5))

Но этот вариант все равно не включает значение Max, и вообще, мы получаем значение типа double. Для того чтобы значение Max тоже входило в допустимый диапазон, нужно прибавить 1 к нашему параметру диапазона (Max — Min) и затем избавиться от дробной части приведением значения к int. Вот так:

Мастер Йода рекомендует:  25 самых используемых регулярных выражений в Java

Min + (int)(Math.random() * ((Max — Min) + 1))

Теперь то что надо! Случайное целое значение в диапазоне [Min,Max], или как в нашем случае [5,10]:

int rnd = 5 + (int)(Math.random() * ((10 — 5) + 1))

Обратите внимание! Как уже не раз (а два) отмечалось в комментариях, при приведении double к int происходит не математическое округление, а просто отсекается дробная часть:

double a = 2.3;
double b = 2.8;
int i_a = (int) a; // i_a=2
int i_b = (int) b; // i_b=2

Это первая статья из серии «Азы программирования на Java». Следующие статьи:

Шифрование и генерация случайных чисел в Android приложениях. Тестовые примеры

Шифрование данных

Шифрование имеет важное значение, поскольку позволяет скрыть от посторонних глаз то, что им не следует видеть. Мобильные устройства хранят все больше и больше значимой информации, и защитить ее – прямая обязанность каждого разработчика.
Существует два варианта шифрования данных под Android: с использованием Java Crypto API и OpenSSL API (нативный код). Мы рассмотрим оба.

Java Crypto API

Использовать Java Crypto API под Android очень просто. Сначала вам необходимо сгенерировать ключ шифрования. За это отвечает класс KeyGenerator в пэкедже javax.crypto.

Теперь вы можете использовать сгенерированный ключ для шифрования файлов с данными. Для этого зашифруем блоки байтов по алгоритму AES с помощью javax.crypto.

OpenSSL API

Шифрование данных через OpenSSL под Android требует написания нативного кода С, который доступен в Java через вызовы JNI. Это отнимает больше времени, зато быстродействие в результате будет выше.
Для начала сгенерируем ключ и iv.

Теперь мы можем использовать сгенерированный ключ (cKeyBuffer) для шифрования файла. Инициализируем EVP с помощью вашего ключа и iv. Теперь подаем блоки байтов на вход функции EVP_EncryptUpdate. Последняя порция байтов из вашего файла должна быть скормлена функции EVP_EncryptFinal_ex.

Генерация случайных чисел

Генератор случайных чисел (RNG) – это программа или устройство для производства случайной последовательности чисел на определенном промежутке. RNG является жизненно важным для безопасности приложения. В реальности криптографический протокол может быть очень надежным, но при этом подверженным разнообразным атакам из-за того, что в своей основе использует слабые методы генерации ключа. Для усиления ключа и повышения надежности всей системы в целом может использоваться аппаратная поддержка RNG.

Существует целых 4 способа сгенерировать случайные числа в Android:

  • java.util.random
  • java.security.SecureRandom
  • /dev/urandom
  • OpenSSL API

Однако, если вы используете RNG для генерации ключа, защищающего ваши данные, использовать обычный класс Random не рекомендуется, так его легче всего взломать. Остальные 3 метода обеспечивают более надежную защиту.

java.util.random

Использовать Java Random Number API очень просто. Вызов Random.nextInt() возвратит 4-байтное случайное значение (общее количество возможных значений – 2 32 ). Это API вполне годится для случаев, когда не требуется полагаться на действительно случайные числа.

java.security.SecureRandom


SecureRandom похож на java.util.Random в том смысле, что также возвращает 4-байтовое значение. SecureRandom криптографически более надежен, однако разработчики должны ознакомиться с недавней рекомендацией генерировать затравочную величину с помощью /dev/urandom для SecureRandom перед генерацией случайных чисел. В примере ниже /dev/urandom не используется.

/dev/urandom

Во всех операционных системах семейства Linux, включая Android, имеется специальный файл, созданный ядром, с помощью которого можно предоставить случайные числа приложениям. Среди всех 4 способов этот самый медленный, он генерирует криптографически безопасные значения с высокой энтропией путем объединения шумовых величин из различных частей операционной системы (например, драйверов устройств) для RNG. Мы можем получить случайное число непосредственно из ядра, прочитав файл /dev/urandom. /dev/urandom имеет доступ к аппаратному RNG, если таковой имеется.

OpenSSL API

Мы также можем использовать OpenSSL API для получения случайных чисел в нативном коде С. В OpenSSL возможно использование затравочных байт из /dev/urandom для генерации криптографически безопасных случайных чисел. OpenSSL API обратится к аппаратному RNG, если таковой имеется.

Взлом генератора случайных чисел Java

Содержание статьи

Java предоставляет два основных генератора псевдослучайных последовательностей (PRNG): java.util.Random — криптографически нестойкий, но выдающий равномерно распределенную последовательность, и java.security.SecureRandom — криптографически стойкий, поэтому может использоваться в реализации стойкой криптографии, например для генерации ключей. Поскольку Java широко используется, эти генераторы часто встречаются в реальных приложениях.

Рис. 1. Общая конструкция PRNG

Xakep #246. Учиться, учиться, учиться!

Внутреннее состояние PRNG изменяется функцией перехода (Ft) при вычислении каждого элемента выходной последовательности, а функция выхода (Fo) преобразует внутреннее состояние в выходные элементы S, S1, . Sn . Из общей схемы работы PRNG можно отметить следующие потенциальные уязвимости:

  1. Если внутреннее состояние относительно небольшое, можно просто перебрать все возможные комбинации, а зная внутреннее состояние и конструкцию PRNG (здесь и далее предполагается, что конструкция PRNG известна), можно воспроизвести его выходную последовательность.
  2. Если на основании выходной последовательности можно сделать предположения о внутреннем состоянии, то это сокращает перебор.
  3. Если для инициализации PRNG использовался слабый инициализатор ( seed ), то, имея выходную последовательность, можно подобрать seed (если seed короче внутреннего состояния, проще перебирать его).

Теория java.util.Random

Random — линейный конгруэнтный генератор, имеющий линейную функцию перехода Ft. Внутреннее состояние изменяется так: Statei + 1 = A * Statei + C mod M , где A = 0x5deece66d (A = 25 214 903 917) , C = 11 и M = 248 . Длина внутреннего состояния — 48 бит. Начальное внутреннее состояние (State) получается из seed следующим образом: A ⊕ seed mod M , где ⊕ — битовый XOR. Механизм инициализации Random будет рассмотрен далее.

Выходная последовательность генератора представляет собой либо модуль внутреннего состояния (иногда такой подход называют «модулярным» или «взятие снизу»), либо битово сдвинутое вправо произведение («мультипликативный», или «взятие сверху»). В зависимости от используемого метода и их параметров Random использует оба подхода.

Рис. 2. Работа генератора

Далее будут рассмотрены атаки на внутреннее состояние, когда имеется выходная последовательность.

Метод nextInt(). Как видно из листинга, старшие 32 бита внутреннего состояния идут без изменения в выход, поэтому для восстановления внутреннего состояния необходимо перебрать только 16 младших бит. На ноутбуке с четырехъядерным Intel i5 (все дальнейшие оценки — на этом же ноутбуке) это занимает менее секунды.

Метод nextLong(). В данном случае внутреннее состояние изменяется дважды для генерации одного выходного элемента. Сценарий атаки здесь полностью повторяет nextInt() . Как и прежде, атака занимает менее секунды.

Метод nextInt(limit), где limit четное (но не степень 2). Атака на этот сценарий была известна ранее (goo.gl/uNl2sG, goo.gl/rLzE2g) и основана на использовании генератора с сокращенным внутренним состоянием для восстановления сначала младших 17 бит внутреннего состояния основного генератора, а остальное — перебором.

Рис. 5. nextInt(2k)

Четный limit может быть представлен как n * 2 p , где n — нечетное и p ≥ 1 . Генератор с сокращенным состоянием длины p + 17 (субгенератор) будет выдавать последовательность, где каждый элемент (Si′) однозначно связан с известной выходной последовательностью основного генератора: S′ = S mod 2 p , S1′ = S1 mod 2 p , …, Sn′ = Sn mod 2 p . Если принять во внимание этот факт, корректные 17 бит внутреннего состояния могут быть восстановлены. На следующем шаге 31 старший бит внутреннего состояния подбирается в виде H31bits = (S + J * limit) mod 2 31 , то есть с шагом limit . Описанные два шага взлома занимают не больше двух секунд.

Метод nextInt(limit) где limit — степень 2. В данном случае используется «мультипликативный» подход к формированию выхода.

Если внутреннее состояние пробовать взломать полным перебором, подбирая его в виде X = (S * 2 48 – p + t) mod 2 48 , необходимо перебрать все возможные t[0; 2 48 – p – 1] . Но при анализе зависимости выхода Si от разных t было обнаружено, что Si изменяется на 1 mod limit только когда t увеличится на некоторое число c такое, что 2 13 – p 14 – p , c

2 13,44644 – p . Такое поведение объясняется алгоритмом изменения внутреннего состояния и получения из него выхода: предыдущее внутреннее состояние умножается на большое целое A = 0x5deece66dL (

234,55) , что эквивалентно сдвигу влево на

34 бита, поэтому внутреннее состояние должно быть изменено более чем с раз, прежде чем это отразится в выходе.


Рис. 6. Зависимость выходной последовательности от t

Знание зависимости выходной последовательности от t позволяет при переборе пропускать значения t, которые будут давать на выходе известные Si, что в общем случае при переборе позволяет пропускать (limit – 1) * c значений t и сокращает сложность перебора с O(248 – p) до O(248 – 2p) . Например, если limit = 64 , сложность перебора составит

Метод nextInt(limit), где limit нечетное. В данном случае используется «модульный» подход к формированию выхода.

Искать внутреннее состояние будем в виде X = (2 17 H31bits + L17bits) mod 2 48 , где H31bits — старшие 31 и L17bits — младшие 17 бит. С учетом алгоритма работы генератора H31bits можно искать в следующем виде: H31bits = (S + J * limit) mod 2 31 , где S — первый элемент имеющейся выходной последовательности, то есть перебором через limit, а L17bits «в лоб» пришлось бы подбирать с шагом 1.

Однако при анализе зависимости выхода Si от L17bits при увеличении на 1 была обнаружена зависимость, показанная на рис. 7.

Рис. 7. Зависимость выхода от младших 17 бит внутреннего состояния

Элементы выходной последовательности генератора могут быть записаны в виде матрицы, имеющей d столбцов и 2 17 /d строк, где d = min i:(A*i) >> 17 = (limit – 1) mod limit , а A = 0x5deece66d — то же A, что используется при смене внутреннего состояния генератора. В каждом столбце матрицы значения изменяются определенным образом: следующий элемент остается неизменным, либо уменьшается на 1 mod limit , либо изменяется на p mod limit , либо на (p + 1) mod limit , где p = 2 31 mod limit .

Рис. 8. Возможные изменения значений в столбцах

Изменение на p и p + 1 происходит периодически, и период может быть рассчитан: period = 2 31 / (A d >> 17) , где, как и прежде, A = 0x5deece66d .

С учетом этой зависимости на первом шаге атаки необходимо предварительно рассчитать значения L17bit, где выход изменяется на p или p + 1 — таких значений будет 2 17 / (d * period) . На следующем шаге будем перебирать значение L17bit, пропуская значения L17bit, заведомо не приводящие к выходу следующего элемента известной последовательности S1 (то есть не выдающие взламываемую последовательность). В каждом столбце необходимо выполнить проверку 2 17 / (d * limit) значений L17bit, вместо 2 17 /d . Сложность взлома с помощью указанного алгоритма составляет O(248/period) вместо O(248/limit) в случае полного перебора, что может быть значительно эффективнее, если period > limit .

Мастер Йода рекомендует:  Как сменить IP адрес компьютера и зачем это нужно

Инициализация Random. В JDK для инициализации используется время с момента старта системы в наносекундах ( System.nanoTime() ). В GNU Classpath конструктор по умолчанию использует время в миллисекундах с начала эпохи ( System.currentTimeMillis() ). Знания об инициализации PRNG позволяют эффективнее проводить взлом.

Основываясь на идеях, описанных выше, мы разработали утилиту командной строки JavaCG для эффективного взлома генераторов Random по имеющейся выходной последовательности. Утилита написана на С++11 и работает под Windows и Linux, доступна на GitHub.

Практическая эксплуатация java.util.Random

От теории к практике! Мы поискали Java-приложения, доступные на sourceforge.net и использующие Random для целей безопасности, и обнаружили множество парольных менеджеров с функциональностью генерации паролей. Например:

Если злоумышленнику известен один пароль, сгенерированный перечисленными инструментами, он может восстановить внутреннее состояние генератора — экземпляра Random , что позволит предсказать последующие и предыдущие пароли, сгенерированные этим же генератором.

Далее мы поискали доступные в cети приложения, использующие Random для сервисов безопасности. В результате был найден контейнер сервлетов Winstone. Jenkins (сервер непрерывной интеграции с открытым кодом, поддерживаемый на коммерческой основе CloudBees) и Hudson (также сервер непрерывной интеграции, поддерживаемый Eclipse Foundation) используют по умолчанию Winstone, который достаточно популярен, как можно видеть из рис. 9.

Рис. 9. Результаты поиска Winstone

В Winstone Random используется для генерации идентификатора сессии, алгоритм реализован в методе makeNewSession() класса winstone.WinstoneRequest . Логика генерации ID сессии следующая: фиксированная строка «Winstone» конкатенируется с IP-адресом клиента, портом сервера, временем генерации в миллисекундах и выходом nextLong() экземпляра Random , от полученной строки вычисляется MD5. PRNG инициализируется временем в миллисекундах с начала эпохи во время старта сервера.

Рис. 10. Формирование ID сессии в Jenkins

Время в миллисекундах дает 10 бит энтропии, поскольку атакующий может получить время в секундах из заголовка Date HTTP-ответа. Единственное, что неизвестно — количество миллисекунд.

Следующее, что нужно угадать атакующему — значение выхода nextLong() . Для воспроизведения выходной последовательности необходимо знать seed , которым был инициализирован генератор, — энтропия 14 бит, и количество сгенерированных случайных чисел с момента старта генератора (это то же, что и количество сессий с сервером с момента старта Winstone — энтропия log2(количество сгенерированных сессий) ). Логично предположить, что Winstone стартует вместе с запуском сервера, поэтому инициализирующее генератор значение времени будет близко к времени его работы. Можно найти разные способы определения времени работы сервера, например в Linux можно использовать значение TCP timestamp , рекомендованное RFC1323. TCP timestamp — это 32-битное значение (timestamp clock) в опциях TCP, используемое для корректировки интервала RTO (retransmission timeout) и в механизме PAWS (Protection Against Wrapping Sequence). Timestamp clock инициализируется известным значением во время старта сервера и инкрементируется с фиксированной частотой. Эта функция включена по умолчанию на большинстве дистрибутивов Linux. Например, в Ubuntu 12.04 LTS timestamp clock инициализируется значением –300 и частота инкрементирования составляет 1000 Гц. Итак, можно оценить время работы сервера, имея значение timestamp clock , а само TCP timestamp можно узнать Nmap’ом с ключом –O .

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

Итого, общая энтропия ID сессии 24 + log2(количество сгенерированных сессий) . Если даже на момент атаки был сформирован миллион сессий, общая энтропия не составит 44 бита, что сравнительно немного и может быть перебрано «в лоб» на практике. Атака реализуется следующим образом:

  1. Атакующий получает новый ID сессии; из заголовка HTTP Date извлекает время в секундах и использует его для оценки времени генерации ID сессии в миллисекундах.
  2. Атакующий оценивает время работы сервера, например с помощью описанной выше техники TCP timestamp.
  3. Атакующий в офлайне подбирает внутреннее состояние PRNG.
  4. Атакующий начинает периодически обращаться на сервер, получая новые ID сессии, определяя по ним, на сколько изменилось внутреннее состояние PRNG: если обнаружено изменение на более чем одно состояние, значит, между нашими периодическими подключениями кто-то еще подключился и для него был сгенерирован ID сессии; атакующий сохраняет значение внутреннего состояния PRNG и период, в течение которого была произведена генерация сессии.
  5. Узнав каким-либо образом IP-адрес подключившегося, атакующий подбирает его ID сессии.

Сценарий атаки представлен на рис. 11, скрипты для взлома приведены в GitHub.

Рис. 11. Сценарий атаки на Jenkins

Видео с демонстрацией атаки доступно здесь. В настоящий момент уязвимость CVE-2014-2060 исправлена.

Теория java.security.SecureRandom

SecureRandom наследован от Random , использует детерминированный алгоритм для формирования псевдослучайной последовательности из истинно случайного seed . В SecureRandom реализована неочевидная логика работы, зависящая от операционной системы, параметров -Djava.security.egd , securerandom.source и механизма инициализации. Чтобы использовать SecureRandom безопасно, нужно хорошо разбираться во всех этих особенностях.

Провайдер JCE по умолчанию, sun.security.provider.Sun , имеет две реализации SecureRandom : NativePRNG и SHA1PRNG . Реализация NativePRNG используется по умолчанию в Linux и Solaris, его выход представляет собой значение SHA1PRNG , сложенное (XOR) с байтами из /dev/random или /dev/urandom , поэтому создание экземпляра SecureRandom с фиксированным seed вполне безопасно и не приводит к проблемам с производительностью. NativePRNG используется, когда securerandom.source=file:/dev/urandom (по умолчанию) или file:/dev/random .


Следующей реализацией SecureRandom является SHA1PRNG — детерминированный генератор, использующий SHA1 для формирования выхода из его внутреннего состояния. По умолчанию применяется в Windows.

Рис. 12. Логика работы SHA1PRNG

Инициализация SHA1PRNG может быть явной и неявной. По умолчанию поддерживаются три варианта неявной инициализации (получения seed ): NativeSeedGenerator , URLSeedGenerator , ThreadedSeedGenerator . Какой из них будет использоваться — зависит от операционной системы и параметра securerandom.source. Байты seed , полученные одним из трех способов, конкатенируются с байтами из функции getSystemEntropy и затем результат перемешивается с помощью SHA1: State= SHA1(getSystemEntropy() || seed) , где || означает конкатенацию.

Реализация NativeSeedGenerator работает в случае, если securerandom.source=file:/dev/urandom или file:/dev/random . В Linux и Solaris эта реализация читает байты из /dev/random , а в Windows используется Microsoft CryptoAPI .

URLSeedGenerator работает, когда securerandom.source!=file:/dev/urandom или file:/dev/random . Он просто читает байты из указанного источника. Реализация ThreadedSeedGenerator работает, если параметр securerandom.source не указан и использует несколько потоков исполнения ( threads ).

Явная инициализация SHA1PRNG происходит при вызове либо конструктора SecureRandom(byte[] seed) (при этом State будет присвоено SHA1(seed) ), либо методов setSeed(long seed) или setSeed(byte[] seed) — здесь Statei будет присвоено значение Statei ⊕ seed .

Важно отметить, что в Linux и Solaris рекомендуется изменять значение по умолчанию securerandom.source ввиду проблем с производительностью: по умолчанию при неявной инициализации NativeSeedGenerator читает байты из /dev/random , а он блокируется при нехватке энтропии, что приводит к зависанию приложения.

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

Вариант 1. SecureRandom инициализируется через конструктор значением seed с малой энтропией (обычно временем):

Вариант 2. SecureRandom инициализируется методом setSeed значением seed с малой энтропией перед вызовом nextBytes :

Практическая эксплуатация небезопасного использования SecureRandom

Первым примером приложения, использующего SecureRandom небезопасно, будет Tiny Java Web Server — небольшой быстрый контейнер сервлетов, способный работать на Android и Blackberry, написанный Дмитрием Рогаткиным. SecureRandom здесь используется для генерации ID сессии и инициализируется временем в секундах. В году всего

225 с, поэтому энтропия такой инициализации очень мала. Эта уязвимость может применяться для перехвата пользовательской сессии (session hijacking). С помощью Shodan можно обнаружить сервисы дистанционного банковского обслуживания, использующие RestEasy и TJWS, а так же была обнаружена MetricStream — GRC-система, использующая TJWS.

Следующим примером будет Oracle WebLogic — сервер приложений Java EE, у которого есть коннектор WTC — WebLogic Tuxedo connector к серверу приложений Tuxedo, используемому для приложений на C, C++, Cobol. WTC реализует протокол LLE — Link-Level encryption для защиты соединения WebLogic с Tuxedo. Связка WebLogic — Tuxedo используется, например, при развертывании Oracle PeopleSoft.

Фрагменты кода класса weblogic.wtc.jatmi.tplle , выполняющие инициализацию LLE:

LLC использует алгоритм Диффи — Хеллмана (DH) для создания пары ключей RC4. Приватный ключ DH для WebLogic генерируется SecureRandom , инициализируемым методом setSeed . Случайность инициализации берется из времени в миллисекундах (10 бит энтропии) и количества свободного памяти в куче (10 бит энтропии). Интервал между вызовами currentTimeMillis() в этой реализации не превышает одной миллисекунды, поэтому следующий вызов добавит лишь один бит энтропии. Оставшиеся параметры могут быть определены, если взять систему аналогичной конфигурации. Данная уязвимость позволяет атакующему, перехватившему публичный DH-ключ Tuxedo, расшифровать защищаемый трафик. Данная уязвимость была исправлена в Oracle Critical Patch Update за октябрь 2014 года.

Третьим интересным примером плохой инициализации SecureRandom является JacORB — реализация ORB (Object Request Broker) в Java. CORBA используется для построения распределенных приложений, работающих на разных платформах. Серверы приложений JBoss и JOnAS содержат библиотеки JacORB, а протокол IIOP (Internet Inter-Orb Protocol) используется для взаимодействия. IIOP может защищаться с использованием SSL (SSLIOP). Вот как SSLIOP реализован в JacORB — фрагмент класса org.jacorb.security.ssl.sun_jsse.JSRandomImpl :

Фрагмент класса org.jacorb.security.ssl.sun_jsse.SSLSocketFactory :

В классе JSRandomImpl создается экземпляр SecureRandom , инициализируется значением 4711 методом setSeed и передается в экземпляр класса SSLContext во время инициализации SSL с помощью метода init . Чтобы понять, как SecureRandom используется в SSLContext , необходимо внимательно ознакомиться, как случайные числа используются в SSL в случае применения RSA OAEP.

Если SecureRadnom плохо инициализирован на клиенте, атакующий, перехватывающий SSL-трафик, может расшифровать его. Эта атака демонстрируется здесь: с помощью ARP-спуфинга атакующий перехватывает трафик SSLIOP, извлекает элементы SSL handshake и передает их в скрипт compute-master.py, который вычисляет ключ. Затем ключ передается в Wireshark, который расшифровывает SSL.

Мастер Йода рекомендует:  Задача на поиск «волшебного» индекса в массиве

GNU Classpath

GNU Classpath — свободная альтернативная реализация стандартной библиотеки классов Java 5. GNU Classpath используется свободными JVM (Java Virtual Machine), такими, например, как JamVM, SableVM, Kaffe, CACAO. Любопытно, что в SableVM SecureRandom неявно инициализируется с помощью вызова new Random(0), — это серьезная уязвимость всех приложений, работающих на SableVM. Широко известный дистрибутив Linux для анонимного интернет-серфинга Liberté Linux используется GNU Classpath и JamVM.

SecureRandom в GNU Classpath реализован проще, чем в JDK. При неявной инициализации используется 32-байтное значение seed , логика формирования которого реализована в классе SecureRandomAdapter . Выходная последовательность представляет собой SHA512 от внутреннего состояния.

Рис. 13. Выходная последовательность в GNU Classpath

При инициализации GNU Classpath пытается извлечь случайность из следующих источников:

  • из файла, заданного параметром securerandom.source в /usr/local/classpath/lib/security/classpath.security ;
  • из файла, заданного параметром командной строки java.security.egd ;
  • при помощи метода generateSeed из класса java.security.VMSecureRandom .

Метод generateSeed получает seed , используя механизм генерации с помощью потоков выполнения ( threads ): создаются восемь потоков (рабочие), которые инкрементируют свои внутренние счетчики, а другой поток (основной) запускает цикл из 32 итераций и на каждой из них вычисляет один байт seed путем сложения (XOR) значений счетчиков рабочих потоков. Затем основной поток вызывает Thread.yield() , который информирует планировщик потоков, что вызывающий поток желает уступить свое процессорное время:

Проблема в том, что планировщик может игнорировать это «желание» потока и продолжить его исполнение.

Рис. 14 показывает, что происходит при вызове generateSeed на системе с одним процессом с одним ядром, — все сгенерированные 32 байта одинаковы! На самом деле первый байт может отличаться, но остальные всегда одинаковы.

Рис. 14. generateSeed на одноядерном процессоре


Для исследования такого поведения класс VMSecureRandom был модифицирован для вывода значений счетчиков всех рабочих потоков (spinner) на каждой итерации. Рис. 15 показывает 10 из 32 итераций: видно, что счетчики рабочих потоков отличаются только на первой итерации, а все остальные остаются неизменными. Причина такого поведения в стремлении планировщика «честно» распределить процессорное время после первой итерации, и все последующие итерации он игнорирует просьбу основного потока отдать его процессорное время рабочим, поэтому цикл прокручивается 31 раз без изменения счетчиков рабочих процессов.

Рис. 15. Вывод модифицированного VMSecureRandom на машине с одним процессором

Если метод generateSeed вызывается на системе с двумя процессорами, тогда все байты seed кажутся различными.

Рис. 16. generateSeed на машине с двумя процессорами

Но, вызвав generateSeed модифицированного VMSecureRandom , можно видеть, что счетчик только одного рабочего потока изменяется на всех итерациях, а счетчики остальных не меняются после первой итерации.

Рис. 17. Выход модифицированного VMSecureRandom на машине с двумя процессорами

Если запустить параллельно какую-нибудь задачу, потребляющую процессорное время, то сформированный seed вновь содержит одинаковые байты.

Рис. 18. generateSeed на двух процессорах одновременно с задачей, потребляющей процессорное время

Если запустить модифицированный VMSecureRandom параллельно с задачей, потребляющей процессор, видно, что счетчики рабочих потоков изменяются только на первой итерации. В общем случае сформированный seed будет иметь 32 одинаковых байта.

Рис. 19. Выход модифицированного VMSecureRandom, работающего параллельно с задачей, потребляющей процессорное время, на двухпроцессорной машине

Для демонстрации описанной выше уязвимости использован контейнер сервлетов Jetty, работающий на JamVM и GNU Classpath. В прошлом Jetty имел уязвимость перехвата сессии (CVE-2007-5614), поэтому сейчас там используется SecureRandom для реализации SSL и генерации ID сессии.

Логика генерации ID сессии расположена в классе org.eclipse.jetty.server.session.AbstractSessionIdManager : инициализация — в методе public void initRandom() , непосредственно генерация — в методе public String newSessionId(HttpServletRequest request, long created) . Пример ID сессии — JSESSION >.

Рассмотрим внимательнее процесс инициации.

_random.nextLong() в реализации SecureRandom в GNU Classpath дает 16 бит энтропии (здесь инициализация происходит через механизм потоков исполнения), для взлома атакующий может перебрать все возможные комбинации. System.currentTimeMillis() — время в миллисекундах с начала эпохи дает 13 бит энтропии — атакующий может оценить это время, используя описанную ранее технику TCP timestamp . Runtime.getRuntime().freeMemory() — количество свободной памяти в байтах — дает 10 бит энтропии, которые атакующий может оценить, взяв систему аналогичной конфигурации. hashCode() — адрес объекта в куче JVM, что дает 12 бит энтропии и может быть оценено на основании известного значения hashcode другого объекта, создаваемого во время старта сервера Jetty.

Для целей демонстрации класс AbstractSessionIdManager был незначительно модифицирован: оставлена только часть _random.nextLong() .

Демонстрация атаки приведена в YouTube, а используемый скрипт доступен на GitHub.

Данную уязвимость можно исправить, заменив вызов Thread.yeild() на Thread.sleep(1) в коде метода generateSeed .

Заключение

Как же можно бороться с описанными уязвимостями?

Во-первых, Random никогда не должен использоваться для целей, связанных с безопасностью, вместо него должен использоваться SecureRandom . Во-вторых, никогда не следует заниматься изобретением своего криптографически стойкого PRNG: значительно безопаснее использовать какой-либо из готовых. В-третьих, при использовании SecureRandom необходимо быть уверенным, что он правильно инициализирован, то есть что энтропия достаточно велика. И последнее: добавление новой свежей энтропии в SecureRandom методом setSeed значительно повысит безопасность.

Генерация случайных чисел

Ключевой момент: вы можете использовать Math.random() для получения величины double между 0.0 and 1.0, исключая 1.0.

Предположим вы хотите создать программу для первоклашек, чтобы они могли практиковаться в вычитании. Программа генерирует два случайных числа в одну цифру, number1 и number2, с условием number1 >= number2 и отображает школьнику вопрос вроде такого: «Сколько будет 9 — 2?». После ввода школьником ответа, программа отображает сообщение о том, является ли он правильным.

Генерация случайных чисел в java

Я хочу создать 30 таблиц, которые состоят из следующих полей. Например,

Как вы можете сделать вывод из приведенных выше таблиц, я получаю значения обратной связи. Я создал эти значения consumer_feedback , Service_ID , Service_Type , используя понятие случайных чисел. Я использовал функцию:

Мне нужно, чтобы Service_Types распределялся равномерно во всех 30 таблицах. Точно так же мне нужно получить значение обратной связи 1 для генерации много раз, кроме 0 и -1.

Если у вас есть 30 номеров, и вам нужны эти 30 номеров, которые будут найдены вашим методом, тогда случайный генератор не будет вам полезен. В этом случае я думаю, что было бы более целесообразно добавить эти 30 номеров в список и вызвать метод [Collections.shuffle] [1], чтобы перетасовать содержимое списка, а затем просто пересечь его с помощью блока for . each , Если вам нужны действительно случайные числа, тогда вы должны использовать класс Random, как объяснил Стивен.

Просто помните, что вы НЕ должны создавать новый экземпляр класса Random каждый раз, когда вам нужно случайное число:

Хорошей практикой является использование Random.nextInt(int n) , обеспечивающее максимальное целочисленное значение, поскольку обычная практика Random.nextInt() % n не генерирует равномерно распределенные числа.

Если вам нужно число от 50 до 100, это просто:

Под капотом Math.random() используется экземпляр java.util.Random для генерации чисел. Вы можете избежать беспорядочности отображения из двойников в целые числа, используя Random API напрямую:

Сделайте что-то вроде этого:

Конечно, число, созданное Random, не очень случайное, но они, безусловно, достаточно хороши для вашего случая использования. Тем не менее, я задаюсь вопросом, не лучше ли вам использовать стратегию «round robin» для распределения нагрузки между устройствами.

Изменить: Этот ответ основан на неправильном понимании вопроса, где я принимал «много раз, кроме 0 и -1», чтобы означать «много раз больше, чем 0 и -1». Я оставляю этот ответ на случай, если он полезен кому-то другому, но я сомневаюсь, что он будет полезен для оригинального плаката.

Чтобы создать неравномерные случайные числа, вам нужно будет указать, какие должны быть веса. Например, возможно, вы хотите, чтобы в три раза больше 1, чем 0 или -1.

Вот метод, который принимает массив из трех значений double , где первым значением является вес для -1, второе значение — вес для 0, а третье значение — вес для 1. Это будет генерировать -1, 0 или 1 с различной вероятностью в зависимости от веса, который вы даете.

Я протестировал этот метод, вызвав его с весовым массивом < 1.0, 1.0, 3.0 >(т.е. в три раза больше 1 как 0 или -1) сто тысяч раз, и получил следующие результаты:

Как вы можете видеть, я получил примерно в три раза больше результатов «1», так как получил результаты «0» или «-1».

Генератор случайных чисел — java.util.Random

Как говорится: случайность — частный случай закономерности. Поэтому наверняка вы используете случайные числа в некоторых своих разработках.

В Java есть класс для работы со случайными (точнее псевдослучайными) числами — java.util.Random. Тем не менее, некоторые люди пользуются им не совсем так, как надо.

Казалось бы, что тут такого плохого?

Давайте рассмотрим следующий метод (можете поместить его в класс TestRandom):

По идее, в нижнюю половину диапазона должно попасть около 500000 чисел. Но мы видим, что туда попадает около 666666. Это число приближается к 500000 по мере увеличения делителя в первой строке метода. Но все равно, непорядок.

Есть еще одна проблема. Метод Math.abs(k) возвращает Integer.MIN_VALUE, если k = Integer.MIN_VALUE, так как не может взять модуль этого числа. То есть в случае, когда nextInt() вернет Integer.MIN_VALUE, не исключено, что generateRandom() вернет отрицательное число. Это не получится только в том случае, когда n — степень числа 2.

Следующий метод демонстрирует нам потенциальный крах программы:

А выход есть — используйте Random.nextInt(int), не зря же его дядьки умные придумали.

Updated (28.01.2008): В литературе мне встречалась информация, что если n — степень двойки, то последовательность псевдослучайных чисел будет повторятся через довольно короткий период. Как я и обещал ранее, привожу небольшой тест, который подтверждет это утверждение:

Программа для POWER_OF_TWO = 2 дает следующий результат:

То есть с периодом 131072 последовательность чисел повторяется. Для POWER_OF_TWO = 4 мощности моего компьютера не хватает. Попробую как-нибудь на машине посерьезнее.

Надеюсь, статья была вам интересна. До скорой встречи.

Добавить комментарий