собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ.
генерацию случайных чисел нельзя отдавать на волю случая... однако.
Все мысли, которые могут прийти в голову при чтении комментария являются объектом авторского права и их незаконное обдумывание запрещается.
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1.
Может и выпасть. При равномерном распределении — с вероятностью (P=1/N^1000), где N — ширина диапазона. А вопрос-то в чём?
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ.
Генераторы бывают разные. С разными законами распределения.
Генератор с равномерным распределением может выдать одно и то же значение 1000 раз подряд. Одно другому не мешает.
EG>генерацию случайных чисел нельзя отдавать на волю случая... однако.
существуют тесты AES, NIST и т.д. В эллиптической криптографии генератор случайных чисел должен выдать числа случайным образом, но при этом равномерно распределённые по заданной зоне.
Я к тому, что если числа распологаются равномерно, то их расположение уже зависимо и его можно предсказать.
Все мысли, которые могут прийти в голову при чтении комментария являются объектом авторского права и их незаконное обдумывание запрещается.
Здравствуйте, EmmGold, Вы писали:
EG>применительно к криптографии.
EG>существуют тесты AES, NIST и т.д. В эллиптической криптографии генератор случайных чисел должен выдать числа случайным образом, но при этом равномерно распределённые по заданной зоне.
EG>Я к тому, что если числа распологаются равномерно, то их расположение уже зависимо и его можно предсказать.
Я не понимаю, в каком смысле здесь используются термины "зависимо" и "предсказать". ГСЧ, генерирующий равномерно распределенную последовательность, в идеале должен выдавать любую конкретную допустимую последовательность с одной и той же (крайне малой) вероятностью. Последовательность в 100 единиц ничем не отличается от других; если генератор будет выдавать некоторую последовательность длины 100 (например ту, которая у нас получилась вчера), чаще, чем 100 единиц подряд, то это плохой генератор — у него не все моменты будут совпадать с моментами равномерного распределения. Возможность "предсказания" (в смысле: о! уже выпало четыре единицы, значит следующая точно не единица) в общем-то и есть криптографическая слабость.
Представьте себе монетку (она хорошо моделирует ГСЧ с равномерным распределением по диапазону из двух значений). Ваш вопрос тогда превращается в вопрос о том, как монетка избегает серии из 100 решек подряд. Ответ: никак, ей пофиг.
А вот что действительно можно "предсказать" (и что, кстати, и должны проверять тесты), так это моменты — матожидание, дисперсию, эксцесс и т.д. Они должны сходиться (по вероятности) к соответствующим параметрам равномерного распределения. Если отклонение от этих параметров статистически значимо, то ГСЧ плохой.
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел.
Наверняка имелось ввиду то, что из различных типов ГСЧ нужен именно "ГСЧ с равномерным распределением", а не, к примеру, "ГСЧ с нормальным распределением".
Например, если в роли ГСЧ взять оцифрованные шумы от звуковой карточки без какой-либо обработки (вопрос качества такого "генератора" надо обсуждать отдельно), то полученное распределение будет близко к нормальному, а не к равномерному.
EG>Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ.
Если речь про двоичную случайную последовательность (значения 0 и 1) — то да, безусловно.
Лично видел, как в рулетке "чёрное" выпало 15 раз подряд
EG>генерацию случайных чисел нельзя отдавать на волю случая... однако.
Это точно! Особенно, если речь идёт о криптографии.
В серьёзных приложениях при начальном формировании ключей пользователя заставляют двигать мышкой или набирать текст на клавиатуре.
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ.
Может выпать. Но вероятность такого варианта стремится к нулю очень стремительно... EG>генерацию случайных чисел нельзя отдавать на волю случая... однако.
Поздравляю!
Вы в точности повторили мысль Дональда Кнута — см. том 2 Получисленные алгоритмы... :_
Хочешь быть счастливым — будь им!
Без булдырабыз!!!
Здравствуйте, andy1618, Вы писали:
A>Это точно! Особенно, если речь идёт о криптографии. A>В серьёзных приложениях при начальном формировании ключей пользователя заставляют двигать мышкой или набирать текст на клавиатуре. Слово серьёзных я бы тут убрал.
А ты знаешь зачем это делается и для чего используются эти данные?
Здравствуйте, CreatorCray, Вы писали:
A>>Это точно! Особенно, если речь идёт о криптографии. A>>В серьёзных приложениях при начальном формировании ключей пользователя заставляют двигать мышкой или набирать текст на клавиатуре.
CC> Слово серьёзных я бы тут убрал.
Ваше право
CC>А ты знаешь зачем это делается и для чего используются эти данные?
В моём случае это использовалось как источник энтропии для начальной инициализации ГПСЧ
в сертифицированном модуле СКЗИ для биржевого софта. Делать это надо было только один раз
после инсталляции модуля. Конечная цель — генерация асимметричных ключей для формирования запросов
на сертификаты и генерация сессионных симметричных ключей для защиты канала.
Кстати, написать реализацию вычисления случайных чисел по времени задержки нажатия на клавиши — задачка не такая простая как кажется.
Главная засада там — что стандартный опрос клавиш идёт по системному таймеру с фиксированным(!) интервалом.
Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными.
Соответственно, совсем нелишним будет протестировать реализацию на прохождение тестов типа DieHаrd.
Здравствуйте, andy1618, Вы писали:
A>>>Это точно! Особенно, если речь идёт о криптографии. A>>>В серьёзных приложениях при начальном формировании ключей пользователя заставляют двигать мышкой или набирать текст на клавиатуре.
CC>>А ты знаешь зачем это делается и для чего используются эти данные? A>В моём случае это использовалось как источник энтропии для начальной инициализации ГПСЧ
Как единственный источник или всё же как один из многих?
A>Кстати, написать реализацию вычисления случайных чисел по времени задержки нажатия на клавиши — задачка не такая простая как кажется. A>Главная засада там — что стандартный опрос клавиш идёт по системному таймеру с фиксированным(!) интервалом. A>Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными.
Потому в серьёзном софте подобные источники энтропии как правило вообще не используются. В крайнем случае "для массовки" как один из многих источников.
Здравствуйте, CreatorCray, Вы писали:
A>>Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными. CC>Потому в серьёзном софте подобные источники энтропии как правило вообще не используются. В крайнем случае "для массовки" как один из многих источников.
А какие есть альтернативы (с учётом того, что модуль может запускаться на разных архитектурах, включая какие-нибудь военные покоцанные линуксы а-ля МСВС)?
Здравствуйте, andy1618, Вы писали:
A>>>Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными. CC>>Потому в серьёзном софте подобные источники энтропии как правило вообще не используются. В крайнем случае "для массовки" как один из многих источников. A>А какие есть альтернативы (с учётом того, что модуль может запускаться на разных архитектурах, включая какие-нибудь военные покоцанные линуксы а-ля МСВС)?
Альтернативы все как правило или ни разу ни crossplatform или вообще hardware.
Самое универсальное что я видел это USB Dongle c хардварным генератором внутри. Соответственно в системе нужен драйвер для доступа к Dongle.
А так всё придумано до нас: собираем как можно больше энтропии в системе и кормим ей генератор(ы).
Либо юзают CryptoAPI предоставляемое системой.
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ. EG>генерацию случайных чисел нельзя отдавать на волю случая... однако.
случайных чисел "просто так" не бывает. я не знаю такой задачи, где были бы нужны просто "некие случайные числа". бывают только случайные числа принадлежащие некоторому распределению. если есть задача, где нужны случ числа, то оговаривается распределение всегда.
если распределение неравномерно, то оно другое. Например, из распространенных есть еще нормальное распределение — это характеризует попадания пуль в мишень или ошибки измерений, экспоненциальное распределение — время ожидания покупателя в магазине.
Просто равеномерное достаточно просто сгенерировать и из него можно получить любое нужное нам.
Здравствуйте, andy1618, Вы писали: A>>>Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными. CC>>Потому в серьёзном софте подобные источники энтропии как правило вообще не используются. В крайнем случае "для массовки" как один из многих источников. A>А какие есть альтернативы (с учётом того, что модуль может запускаться на разных архитектурах, включая какие-нибудь военные покоцанные линуксы а-ля МСВС)?
простейший здравый генератор случайных чисел — шипящий транзистор, генерирующий белый шум. каждый транзистор шипит, остается только оцифровать шум, немного обработать и использовать.
Здравствуйте, __kot2, Вы писали:
A>>А какие есть альтернативы (с учётом того, что модуль может запускаться на разных архитектурах, включая какие-нибудь A>>военные покоцанные линуксы а-ля МСВС)?
__>простейший здравый генератор случайных чисел — шипящий транзистор, генерирующий белый шум. каждый транзистор шипит, остается только оцифровать шум, немного обработать и использовать.
Там речь шла о клиентском софте, который устанавливался у конечных пользователей, причём на самом разнообразном железе.
А так, конечно, аппаратный генератор СЧ — вещь шикарная!
Сам когда-то паял генератор шума на стабилитроне — он легко проходил все самые хитроумные статистические тесты, на которых многие программные генераторы сыпались
Здравствуйте, andy1618, Вы писали:
A>Например, если в роли ГСЧ взять оцифрованные шумы от звуковой карточки без какой-либо обработки (вопрос качества такого "генератора" надо обсуждать отдельно), то полученное распределение будет близко к нормальному, а не к равномерному.
Да, это более-менее доступный источник. Распределение не так важно, важна именно энтропийность. Проблема в том, что на микрофонном входе присутствует не только шум, но и довольно сильный хам, который ни фига не случайный. Его можно конечно отфильтровать, но проблематично — даже после самой мощной фильтрации остается некая периодичность. Решение — затыкать вход короткозамкнутой заглушкой, но кто же их будет делать?
Меня вообще удивляет — чего может быть проще встроить в проц один-единственный стабилитрон и снимать с него шум?! А ведь задача очень востребована на самом деле. И никто, ну вообще никто об этом даже не подумал! А теперь уже поздно, ибо "совместимость". Так в нашем мире проявляется костный корпоративный идиотизм.
McSeem
Я жертва цепи несчастных случайностей. Как и все мы.
Здравствуйте, EmmGold, Вы писали:
EG>собственно, почему требуется равномерное распределение значений в заданной зоне для генератора случайных чисел. Числа ведь случайные и вполне может выпасть 1000 раз значение 1. или я неправ.
EG>генерацию случайных чисел нельзя отдавать на волю случая... однако.
Здравствуйте, McSeem2, Вы писали:
MS>Да, это более-менее доступный источник. Распределение не так важно, важна именно энтропийность. Проблема в том, что на микрофонном входе присутствует не только шум, но и довольно сильный хам, который ни фига не случайный.
Я, конечно, понимаю термины spam/ham, но по-русски это звучит не то странной формой самокритики, не то каким-то очень подозрительным общим выводом о тех, кто хотя бы находится близко к микрофону. Впрочем, если речь о "телевизионных деятелях искусств", то я на 99% согласен с такой оценкой любого из них.
MS>Меня вообще удивляет — чего может быть проще встроить в проц один-единственный стабилитрон и снимать с него шум?! А ведь задача очень востребована на самом деле. И никто, ну вообще никто об этом даже не подумал! А теперь уже поздно, ибо "совместимость". Так в нашем мире проявляется костный корпоративный идиотизм.
Не знаю насчёт процессора, но в интеловских чипсетах такое давно есть.
Хотя по современным меркам действительно лучше пытаться держать такое в процессоре. Если, конечно, оно не будет слишком сильно греться.
Здравствуйте, andy1618, Вы писали:
A>Кстати, написать реализацию вычисления случайных чисел по времени задержки нажатия на клавиши — задачка не такая простая как кажется. A>Главная засада там — что стандартный опрос клавиш идёт по системному таймеру с фиксированным(!) интервалом.
Ну вообще-то, если речь о клавиатуре типичного современного PC, там нет никакого "опроса клавиш по таймеру" (это Вы в лучшем случае начитались Jourdain'а). Контроллер клавиатурного выхода генерирует именно прерывание. С другой стороны, здесь могут участвовать такие факторы, как
— цикл опроса в самой клавиатуре (там обычно небольшой процессор, в классике был 8042, сейчас — не знаю)
— разнообразные системные задержки (от кэша до загруженности PCI)
— посторонние участники вроде SMM
A>Поэтому числа (задержки клавиш), которые на вид кажутся случайными, при детальном анализе могут оказаться сильно коррелированными. A>Соответственно, совсем нелишним будет протестировать реализацию на прохождение тестов типа DieHаrd.
Вот поэтому мне кажется наиболее правильным (при отсутствии аппаратного ГСЧ) подход Yarrow. В нём нет проблемы, какую детализацию каждой порции "энтропии" применять: кормится её существенная часть, а перед выходом к клиенту данные подвергаются хэшированию, которое устраняет все неслучайности. Кстати, кроме DieHard давно есть ещё как минимум DieHarder.
