Pull to refresh
  • by relevance
  • by date
  • by rating

Новый алгоритм ГСЧ на замену /dev/random

Cryptography
Как известно, генерация случайных чисел является ключевым элементом для приложений криптографии, экономики, информационной безопасности, имитационного моделирования (прогнозы погоды) и многих других. Все существующие алгоритмы ГСЧ используют внешний источник энтропии, например, счётчик тактов процессора, шум звуковой карты, движение мыши пользователя и т.д.

Немецкие исследователи Бернард Фечнер (университет Хагена) и Андре Остерлох (BTC AG) заявили о прорыве в методах генерации случайных чисел. Они разработали алгоритм, который обеспечивает дискретное равномерное распределение до 20 раз лучше существующих методов. К работе прилагаются результаты тестов по сравнению качества случайных чисел, генерируемых разными методами.
Читать дальше →
Total votes 57: ↑52 and ↓5 +47
Views3.9K
Comments 64

Правда о ГСЧ покер румов

Покерофф corporate blog

Введение


В этой статье вы узнаете об одной из важнейших составляющих онлайн покера — генераторе случайных чисел (ГСЧ). «Честность» ГСЧ различных покер-румов регулярно подвергается сомнению и обязательно обсуждается на любом ресурсе посвященном покеру. Пользователи постоянно жалуются на «подкрученный» генератор, который позволяет комнате сдерживать более сильных игроков для того чтобы большинство представляющее категорию «более слабых игроков» осталось лояльным комнате. Давайте разберемся действительно ли все так плохо со случайностью на покерных сайтах.
Читать дальше →
Total votes 76: ↑40 and ↓36 +4
Views64.5K
Comments 35

Как работает новый генератор случайных чисел Intel

Cryptography
Translation


Представьте, что сейчас 1995 год и вы собираетесь совершить первую покупку в онлайне. Вы открываете браузер Netscape и прихлёбываете из чашечки кофе, пока главная страница медленно загружается. Ваш путь лежит на Amazon.com — новый онлайн-магазинчик, о которой рассказал вам друг. Когда наступает этап оформить покупку и ввести персональные данные, адрес в браузере меняется с «http» на «https». Это сигнализирует о том, что компьютер установил зашифрованное соединение с сервером Amazon. Теперь можно передавать серверу данные кредитной карты, не опасаясь мошенников, которые хотят перехватить информацию.

К сожалению, ваша первая покупка в интернете была скомпрометирована с самого начала: вскоре обнаружится, что якобы безопасный протокол, по которому браузер установил соединение, на самом деле не очень защищён.
Читать дальше →
Total votes 179: ↑170 and ↓9 +161
Views52.1K
Comments 112

Шустрый 128-битный LFSR (MMX required)

CryptographyAssemblerAlgorithms
Sandbox
Случайные числа — темная лошадка обеспечения механизмов безопасности в цифровой среде. Незаслуженно оставаясь в тени криптографических примитивов, они в то же время являются ключевым элементом для генерации сессионных ключей, применяются в численных методах Монте-Карло, в имитационном моделировании и даже для проверки теорий формирования циклонов!

При этом от качества реализации самого генератора псевдослучайных чисел зависит и качество результирующей последовательности. Как говорится: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».



Вариантов реализации генератора псевдослучайных чисел достаточно много: Yarrow, использующий традиционные криптопримитивы, такие как AES-256, SHA-1, MD5; интерфейс CryptoAPI от Microsoft; экзотичные Chaos и PRAND и другие.

Но цель этой заметки иная. Здесь я хочу рассмотреть особенность практической реализации одного весьма популярного генератора псевдослучайных чисел, широко используемого к примеру в Unix среде в псевдоустройстве /dev/random, а также в электронике и при создании потоковых шифров. Речь пойдёт об LFSR (Linear Feedback Shift Register).

Дело в том, что есть мнение, будто в случае использования плотных многочленов, состояния регистра LFSR очень медленно просчитываются. Но как мне видится, зачастую проблема не в самом алгоритме (хотя и он конечно не идеал), а в его реализации.
Читать дальше →
Total votes 39: ↑39 and ↓0 +39
Views15.5K
Comments 40

Случайные числа. Take Two

Positive Technologies corporate blogInformation Security
Недавно вышла замечательнейшая работа про атаки на генератор случайных чисел в PHP, однако в ней никаких практических примеров представлено не было. Мы провели собственное исследование данной темы, которое вылилось в создание набора инструментов для реализации подобного рода атак.
Читать дальше →
Total votes 64: ↑60 and ↓4 +56
Views29.3K
Comments 40

Случайный генератор буквоцифр и его варианты

Abnormal programmingJavaScriptAlgorithms
Обратиться к теме написания случайных генераторов букв навела мысль о том, что в JS существует нетипичная нативная функция преобразования строки в n-ичное число, где n = 2..36. 36 в стандарте языка придумано не случайно — это сумма количества цифр и малых английских букв, из которых предлагается писать такие числа. Это значит, что парой нативных функций уже можно построить полезный генератор небольших строк из буквоцифр.

Math.random().toString(36) //даст числа вида 0.816cwugw2ky, 0.opgqwav8w1m, 0.f0w4ejtq8wk, ...

Это значит, что для некоторых задач можно не писать относительно честные генераторы на основе унылых строк вида «abcdefghijklmno...».
Сделаем несколько полезных функций
Total votes 28: ↑21 and ↓7 +14
Views89.7K
Comments 19

Разработчики FreeBSD ограничат использование аппаратных генераторов случайных чисел из-за подозрений на наличие бэкдоров

Information SecurityCryptography
image

В следующей, 10-й версии FreeBSD, разработчики откажутся от непосредственного использования аппаратных генераторов случайных чисел, встроенных в чипы Intel и VIA, из-за сомнений в их безопасности. Один из главных источников таких сомнений — публикации секретных документов АНБ Эдвардом Сноуденом, которые свидетельствуют о том, что спецслужбы активно работают над внедрением бэкдоров в базовые криптографические технологии, как на программном, так и на аппаратном уровне.
Читать дальше →
Total votes 77: ↑72 and ↓5 +67
Views26.4K
Comments 14

Генерация случайных чисел большой разрядности

ProgrammingAlgorithms
Sandbox

imageОднажды я столкнулся с задачей генерации 128-битных случайных чисел для реализации генетического алгоритма. Из-за большой размерности задачи алгоритм гонялся долго, поэтому были повышенные требования к скорости работы. Я решил написать свой генератор специально для поставленной задачи.

В этом посте речь пойдет о применении линейного конгруэнтного метода для получения псевдослучайных чисел разрядности 64 и 128 бит с пояснением принципа работы и подбора параметров.

Если вам в тягость пользоваться ГСЧ из стандартной библиотеки, у вас к нему нестандартные требования или просто охота держать под контролем весь процесс генерации случайных чисел в своем приложении, добро пожаловать под кат.

Читать дальше →
Total votes 42: ↑34 and ↓8 +26
Views39.2K
Comments 29

Преобразование равномерно распределенной случайной величины в нормально распределенную

ProgrammingAlgorithmsMathematics
Этот вопрос уже давно подробно изучен, и наиболее широкое распространение получил метод полярных координат, предложенный Джорджем Боксом, Мервином Мюллером и Джорджем Марсальей в 1958 году. Данный метод позволяет получить пару независимых нормально распределенных случайных величин с математическим ожиданием 0 и дисперсией 1 следующим образом:
алгоритм марсалья marsaglia
где Z0 и Z1 — искомые значения, s = u2 + v2, а u и v — равномерно распределенные на отрезке (-1, 1) случайные величины, подобранные таким образом, чтобы выполнялось условие 0 < s < 1.
Многие используют эти формулы, даже не задумываясь, а многие даже и не подозревают об их существовании, так как пользуются готовыми реализациями. Но есть люди, у которых возникают вопросы: «Откуда взялась эта формула? И почему получается сразу пара величин?». Далее я постараюсь дать наглядный ответ на эти вопросы.

Читать дальше →
Total votes 78: ↑73 and ↓5 +68
Views101.9K
Comments 33

Швейцарские физики превратили Nokia N9 в квантовый генератор случайных чисел

Microsoft Lumia corporate blogCryptography
В сфере компьютерной безопасности использование генератора случайных чисел (ГСЧ) является основой для создания любой криптографической системы. К примеру, ГСЧ используются для защиты личных данных при обработке транзакций с кредитных карт, совершенных через Интернет. Хотя, не вам нам объяснять.



Интересная новость из области разработки генераторов случайных чисел пришла недавно из Швейцарии: физики из Женевского университета нашли способ получать случайные числа, используя принцип квантовой неопределённости при обработке сигнала с сенсора цифровой камеры Nokia N9.
Давайте попробуем разобраться, что же в этом такого.
Читать дальше →
Total votes 44: ↑28 and ↓16 +12
Views33.1K
Comments 18

Лёгкий блочный шифр Speck, или пылинка от агенства, которого нет

CryptographyC++Algorithms
Устройство на КДПВ шифрует не по алгоритму Speck, но могло бы

В июне 2013 года АНБ опубликовало описание двух лёгких блочных шифров — Simon и Speck [1].

Произошло это в самый разгар скандала со Сноуденом, поэтому новость была встречена с понятным скептицизмом. Особенно потому, что в статье не было результатов криптоанализа, а только описание алгоритма и данные о производительности.

Прошло два года, практических атак ни на Simon, ни на Speck не появилось [2], а преимущества (простота и гибкость) — остались.

В отличие от своего младшего брата Simon, который оптимизирован для железа, Speck создан для программной имплементации, в том числе на устройствах с ограниченными возможностями вроде микроконтроллеров. Поскольку программистов среди читателей скорее всего больше, чем аппаратчиков, остаток статьи будет про Speck.

Что там внутри и зачем он нужен, когда есть AES
Total votes 37: ↑35 and ↓2 +33
Views27K
Comments 9

Создаём аппаратный генератор случайных чисел

Development for Linux
Я хочу представить вашему вниманию программно-аппаратный вариант получения случайных чисел. Забегая вперёд, скажу, что данный вариант не единственный, и этот пост открывает мою небольшую серию статей о получении, генерации и изучении случайных чисел, или точнее сказать просто случайностей.



Читать дальше →
Total votes 162: ↑159 and ↓3 +156
Views51.3K
Comments 104

Генерируем псевдослучайные ID а-ля Youtube

Virgil Security, Inc. corporate blogCryptographyAlgorithmsMathematics
Привет, %username%! Бывает необходимо генерировать ID не подряд, причем чтобы они гарантированно не повторялись. На youtube это используется для того, чтобы вы не могли брутфорсом получить все новые и старые видосики, так же это не редкость на разных файлообменниках и вообще везде где нужно предотвратить или хотя бы затруднить возможность прямого перебора значений.


К примеру, в системе moodle, которая использовалась у нас в универе для тестирования студентов, ID ответов были инкрементными и сквозными на всю базу. Логично предположить, что правильным ответом был тот, что с наименьшим ID в пределах вопроса. В общем, проблем с тестами у нас не было. Потом они перешли на GUID, но я к тому моменту уже выпустился, хехе.

Давайте рассмотрим несколько способов генерации таких ограниченных по длине последовательностей от самых простых до криптографически стойких.
Читать дальше →
Total votes 69: ↑63 and ↓6 +57
Views21.5K
Comments 41

Случайное распределение урона в RPG

Game development
Translation
image

Для вычисления урона от атаки в таких настольных ролевых играх, как Dungeons & Dragons, используются броски урона. Это логично для игры, чей процесс основан на бросках кубиков. Во многих компьютерных RPG урон и другие атрибуты (сила, очки магии, ловкость и т.д.) вычисляются по похожей системе.

Обычно сначала пишется код вызова random(), а затем результаты корректируются и подстраиваются под нужное игре поведение. В этой статье будут рассмотрены три темы:

  1. Простые корректировки — среднее значение и дисперсия
  2. Добавление асимметрии — отбрасывание результатов или добавление критических попаданий
  3. Полная свобода в настройке случайных чисел, неограниченная возможностями кубиков
Читать дальше →
Total votes 28: ↑28 and ↓0 +28
Views25.6K
Comments 11

Избавляем игрока от раздражения: правильное использование случайных чисел

Game development
Translation
image

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

Но есть способ и получше. Используя случайных чисел и их генерирование иным образом, мы можем создавать захватывающий игровой процесс, создающий «идеальный» уровень сложности, не выбешивая при этом игроков. Но прежде чем мы перейдём к этому, давайте рассмотрим основы генераторов случайных чисел (или RNG).
Читать дальше →
Total votes 30: ↑27 and ↓3 +24
Views17K
Comments 18

Фотонный генератор случайных чисел: самое надежное шифрование?

ua-hosting.company corporate blogInformation SecurityCryptographyPopular sciencePhysics


Информация это один из самых ценных ресурсов нашего времени. Полезна ли информация? Вопрос риторический. Конечно, да. Но попав не в те руки, она может навредить. Именно потому и используются различные методы, техники и алгоритмы шифрования данных. Ведь, покупая что-то в сети, вы не хотите чтобы ваши платежные данные попали какому-то проходимцу. Однако не все алгоритмы одинаково хороши. Защита данных и хакеры (будем для простоты называть всех похитителей данных именно так) всегда работают на опережение друг друга. С появлением нового способа шифрования появляются и новые методы его обойти. Но что если будет такой алгоритм, который невозможно взломать? В этом помогают квантовые генераторы случайных чисел. Исследователи из университета Бристоля (Великобритания) разработали новое устройство шифрования — чип размером 1 мм2, использующее для генерации чисел фотоны. Еще одной отличительной чертой новинки является ее скорость — более 1 Гбит/с. Какие сложности пришлось преодолеть, какие преимущества именно у этого устройства в сравнении с другими, и насколько защищенными с его помощью станут наши данные? На эти и другие вопросы будем искать ответы в отчете исследователей. Поехали.
Читать дальше →
Total votes 17: ↑12 and ↓5 +7
Views6.1K
Comments 10

Random.org — история длиной в 20 лет

RUVDS.com corporate blogHistory of IT
Уже совсем скоро в рамках проекта «Сервер в облаках» у нас полетит воздушный шар, чьи координаты места приземления — настоящий генератор истинно случайных чисел, у которого источником энтропии является движение воздушных масс. На момент написания этого поста более 100 хабражителей принимают участие в этой интеллектуальной гонке – угадать/рассчитать место приземления сервера и выиграть сертификат на участие в регате. Присоединяйся!



А пока идет гонка и подготовка к полету, мы вспомнили, что у Random.org, одного из самых популярных онлайн-генераторов, предоставляющего истинно случайные числа, источником энтропии тоже является атмосфера, точнее, атмосферные шумы. К тому же сайт скоро будет справлять 20-летие. И история развития Random.org оказалась настолько феерична, и в духе нашего проекта, что в честь «энтропийного совпадения» и скорого юбилея мы решили перевести её для вас.
Читать дальше →
Total votes 29: ↑27 and ↓2 +25
Views8.8K
Comments 3

Заблуждения игроков при оценке рисков. Контроль генератора случайных чисел в разработке

Game developmentGame designGames and game consoles
Человеческий мозг по своей природе очень плохо умеет оценивать вероятность срабатывания случайных событий, на основании выданной числовой оценки. И довольно хорошо на основании качественных оценок. А все потому, что человек мысленно делает конвертацию числовых вероятностей в качественные оценки, и делает это очень субъективно:

  • 80% попадания выстрела в игре — ну это почти гарантированное попадание;
  • 80% того, что ваш товарищ хоть когда-нибудь отдаст долг — не-не-не, так не пойдёт, это слишком большой риск;
  • 5% получения критического урона он NPC врага — маловероятно, риск можно игнорировать;
  • 1% риск падения сосульки, если пройти под крышей с капающими метровыми сосульками — ещё чего, лучше обойти с другой стороны тротуара;
  • 51% вероятность выигрыша в мини-игре в большой РПГ — можно рассчитывать на то, что после 20 ставок я чуть-чуть выиграю или, как минимум, останусь при своих… через 20 ставок… как такое могло случиться, что я проиграл половину всего своего золота? Тут явно сломан генератор случайных чисел!


В статье будут рассмотрены следующие вопросы:

  • ошибочные допущения в оценке вероятностей;
  • конкретные примеры заблуждений игроков и фактические вероятности «редких» событий;
  • генератор случайных чисел (вообще-то псевдослучайных);
  • ранние простые генераторы псевдослучайных чисел на примере Final Fantasy I;
  • подходы к реализации случайных событий с воспроизводимостью и без;
  • примеры удачно внедренных разных подходов и манипуляции в Fire Emblem.
Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Views18.6K
Comments 37

CPU-функции RDRAND и RDSEED стали доступнее

CryptographyAssemblerDelphi
Всем привет!

Сам я криптографией не занимаюсь, но кому то вполне может пригодится мое небольшое исследование. Решил разобраться со встроенными в процессор функциями RDRAND и RDSEED. Компилятор Delphi сказал Undeclared identifier. Хмм. Уже давно существует BMI, BMI2, AVX, AVX2 и даже AVX-512, а дельфийцы остановились на SSE4.2. Не беда. Скомпилируем код сами.

Сначала сделал проверку на поддержку данных функций процессором. Конечно же CPUID. Использовать CPUID можно начиная с первых Pentium процессоров. Надеюсь никто не додумается запустить CPUID на 486 машине, ибо ее там еще не было. Кстати RDRAND и RDSEED до процессоров IvyBridge также не существует.

function CPU_support_RDRAND: Boolean;
asm
  mov rax, $01
  cpuid
  test ecx, 40000000h //тестируем 30-й бит
  setne al
end;

function CPU_support_RDSEED: Boolean;
asm
  mov rcx, 0
  mov rax, $07 //страница №7
  cpuid
  test ebx, 40000h //тестируем 18-й бит
  setne al
end;

Оказалось, что мой Core i7 G6950X Extreme поддерживает данные функции. Поэтому дальше решил скомпилировать байт-код вручную. Для опытных приведу код REX и REX.W префиксов. Возможно вы захотите записать результат в другой регистр:

const
  REX_RDRAND32: Byte = $F0; //(11b:REG, 110b:OPCODE, 000b:EAX) 
  REX_RDSEED32: Byte = $F8; //(11b:REG, 111b:OPCODE, 000b:EAX)
  REX_W_RDRAND64: Byte = $48; //(11b:REG, 110b:OPCODE, 000b:RAX)
  REX_W_RDSEED64: Byte = $48; //(11b:REG, 111b:OPCODE, 000b:RAX)
Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Views5K
Comments 15

Случайные перестановки и случайные разбиения

Mathematics
Sandbox
Я много лет читаю курсы по комбинаторике и графам для студентов-математиков и computer scientists (как это по-русски, компьютерных научников?), раньше в Академическом университете, а теперь в СПбГУ. Программа у нас построена так, что эти темы проходят как часть «теоретической информатики» (другие темы в ней — алгоритмы, сложность, языки и грамматики). Не могу сказать, насколько это оправдано метафизически или исторически: всё же комбинаторные объекты (графы, системы множеств, перестановки, клетчатые фигуры и др.) начали изучали задолго до появления компьютеров, и сейчас последние хотя и важная, но далеко не единственная причина интереса к ним. Но так посмотреть на самых спецов по комбинаторике и по theoretical computer science — это удивительно часто одни и те же люди: Ловас, Алон, Семереди, Разборов и далее. Наверно, есть на то свои причины. На моих уроках часто очень нетривиальные решения сложных задач предлагают чемпионы олимпиадного программирования (их перечислять не буду, кому любопытно посмотрите топ codeforces.) В общем, думаю, что некоторые вещи из комбинаторики могут быть интересны сообществу. Говорите, если что так или не так.
Читать дальше →
Total votes 12: ↑11 and ↓1 +10
Views3.6K
Comments 3
1