На сегодняшний день случайность повсеместно используется в нашей жизни. Она есть в научных работах и исследовательских моделях, защитных алгоритмах и криптосистемах, в лотереях и азартных играх, системах автоматизации и математике. Сейчас я немного расскажу про ГСЧ и какие плюсы и минусы можно от них получить в той или иной сфере.
В подавляющем большинстве моих постов о генерации случайных чисел рассматривались в основном свойства различных схем генерации. Это может оказаться неожиданным, но производительность алгоритма рандомизации может зависеть не от выбранной схемы генерации, а от других факторов. В этом посте (на который меня вдохновила превосходная статья Дэниела Лемира) мы исследует основные причины снижения производительности генерации случайных чисел, которые часто перевешивают производительность движка ГПСЧ.
Представьте такую ситуацию:
В качестве домашнего задания Хуан и Саша реализуют одинаковый рандомизированный алгоритм на C++, который будет выполняться на одном университетском компьютере и с одним набором данных. Их код почти идентичен и отличается только в генерации случайных чисел. Хуан торопится на свои занятия по музыке, поэтому просто выбрал вихрь Мерсенна. Саша, с другой стороны, потратил несколько лишних часов на исследования. Саша провёл бенчмарки нескольких самых быстрых ГПСЧ, о которых недавно узнал из соцсетей, и выбрал наиболее быстрый. При встрече Саше не терпелось похвастаться, и он спросил Хуана: «Какой ГПСЧ ты использовал?»
«Лично я просто взял вихрь Мерсенна — он встроен в язык и вроде неплохо работает».
«Ха!», — ответил Саша. «Я использовал jsf32. Он намного быстрее, чем старый и медленный вихрь Мерсенна! Моя программа выполняется за 3 минуты 15 секунд!».
«Хм, неплохо, а моя справляется меньше, чем за минуту», — говорит Хуан и пожимает плечами. «Ну ладно, мне пора на концерт. Пойдёшь со мной?»
«Нет», — отвечает Саша. «Мне… эээ… нужно снова взглянуть на свой код».
Эта неловкая вымышленная ситуация не особо и вымышлена; она основана на реальных результатах. Если ваш рандомизированный алгоритм выполняется не так быстро, как хотелось бы, и узким местом похоже является генерация случайных чисел, то, как это ни странно, проблема может быть и не в генераторе случайных чисел!
Читать полностью »
Программа воссоединения семей (Family Reunification Program или Family sponsorship) — одна из трёх основных канадских программ помощи мигрантам. Она позволяет как недавно прибывшим иммигрантам, так и давно устоявшимся канадцам воссоединиться с членами своих семей. В соответствии с положениями об иммиграции и защите беженцев (Immigration and Refugee Protection Regulations), проживающие за рубежом семьи получают финансовую помощь, также как проживающие в Канаде родственники мигранта. На финансовую помощь могут рассчитывать супруги, дети, родители, внуки, усыновлённые дети и т. д.
Проблема в том, что Канада не может сразу предоставить гражданство всем родственникам всех мигрантов. Раньше их ставили в очередь, а рассмотрения заявки приходилось ожидать годами. Чтобы ускорить процесс, либералы предложили проводить лотерею. Так что с 2017 года в Канаде разыгрывается лотерея по типу американской Green Card. Среди примерно 100 000 заявок случайным образом выбирают 10 000. Благодаря официальному ответу на запрос по Закону доступа к информации канадскому изданию The Globe an Mail стали известны некоторые технические детали, как проводится лотерея.
Читать полностью »
Совсем недавно, помогая коллеге в решении вопроса о неповторяемости работы ряда тестов, я в очередной раз натолкнулся на задачу симуляции устройства, генерирующего последовательности случайных чисел. В этой статье я расскажу о том, какие сложности были обнаружены, какой подход к их разрешению был выбран, и как я проверял, что новое решение лучше предыдущего. Сразу отмечу, что вопрос создания и верификации случайных последовательностей очень тонкий, и почти никакое решение не может считаться в нём окончательным. Буду признателен за комментарии и исправления.
Вначале я кратко расскажу о предметной области аппаратных и псевдослучайных генераторов, об их характеристиках и требованиях к ним. Затем перейду к своему частному случаю — области программной симуляции вычислительных систем, и к конкретной задаче, которую нужно было решить.
Иногда самый надёжный способ получить случайное число — взять его из справочника. Источник изображения: www.flickr.com/photos/nothingpersonal/337684768/
Читать полностью »
Компания Apple недавно допустила крупную ошибку, забыв удалить лишнюю строчку с оператором безусловного перехода goto посередине функции SSLVerifySignedServerKeyExchange для проверки серверной подписи при установке SSL-соединения. В результате, функция успешно завершала работу, независимо от результата проверки подписи.
Однако, это не первый случай в истории, когда критическая ошибка объясняется единственной строчкой кода. Вот ещё несколько таких примеров.
В 2006 году было обнаружено, что X Server проверяет рутовые права у пользователя, но при этом разработчики в реальности забыли вызвать соответствующую функцию.
--- hw/xfree86/common/xf86Init.c
+++ hw/xfree86/common/xf86Init.c
@@ -1677,7 +1677,7 @@
}
if (!strcmp(argv[i], "-configure"))
{
- if (getuid() != 0 && geteuid == 0) {
+ if (getuid() != 0 && geteuid() == 0) {
ErrorF("The '-configure' option can only be used by root.n");
exit(1);
} 
Все знают, что лучший генератор случайных чисел — это устройство, оцифровывающее выход с очень чувствительного микрофона, стоящего на солнечном берегу моря где-нибудь в районе диких пляжей Бали.
Если у вас такого устройства нет, то прошу под кат.
Читать полностью »
На Хабре и в сети часто начали появляться статьи, посвященные уязвимостям генераторов случайных чисел. Данная тема крайне обширна и является одной из основных в криптографии. Под катом находится описание случайных чисел от A до Z. Статья является результатом свободного перевода цикла статей из одного западного блога и личных дополнений автора. Основная цель — получить feedback и поделиться знаниями.
Читать полностью »