Как компютрите генерират случайни числа

Компютрите генерират случайни числа за всичко - от криптография до видеоигри и хазарт. Има две категории случайни числа - „истински“ случайни числа и псевдослучайни числа - и разликата е важна за сигурността на системите за криптиране..

Компютрите могат да генерират наистина случайни числа, като наблюдават някои външни данни, като движения на мишката или шум от вентилатори, което не е предсказуемо и създава данни от него. Това е известно като ентропия. В други случаи те генерират „псевдослучайни“ числа, като използват алгоритъм, така че резултатите да са случайни, въпреки че не са.

Тази тема наскоро стана по-противоречива, като много хора поставиха под въпрос дали вграденият в Intel чип с генератор на случайни числа е надежден. За да разберете защо може да не е достоверно, трябва да разберете как най-напред се генерират случайни числа и за какво се използват.

За какво се използват случайни числа

Случайните числа се използват от много хиляди години. Независимо дали сменяте монета или хвърляте зарове, целта е да оставите крайния резултат до случаен случай. Генераторите на случайни числа в компютъра са подобни - те са опит да се постигне непредвидим, случаен резултат.

Генераторите на случайни числа са полезни за много различни цели. Освен очевидните приложения като генерирането на случайни числа за целите на хазарта или създаването на непредсказуеми резултати в компютърната игра, случайността е важна за криптографията.

Криптографията изисква номера, които нападателите не могат да познаят. Не можем просто да използваме еднакви числа отново и отново. Искаме да генерираме тези числа по много непредсказуем начин, така че нападателите да не ги познават. Тези случайни числа са от съществено значение за сигурно кодиране, независимо дали криптирате собствените си файлове или просто използвате HTTPS уебсайт в интернет..

Истински случайни числа

Може да се чудите как компютърът може да генерира случайно число. Откъде идва тази „случайност“. Ако това е просто част от компютърен код, не е ли възможно числата, генерирани от компютъра, да са предвидими?

Ние обикновено групираме произволните числа компютри, генерирани в два типа, в зависимост от това как те са генерирани: "True" случайни числа и псевдо-случайни числа.

За да генерира „истинско“ случайно число, компютърът измерва някакъв вид физическо явление, което се случва извън компютъра. Например, компютърът може да измери радиоактивния разпад на атома. Според квантовата теория няма начин да се знае със сигурност кога ще се случи радиоактивен разпад, така че това е по същество „чиста случайност“ от Вселената. Един нападател не би могъл да предвиди кога ще се случи радиоактивен разпад, за да не знаят произволната стойност.

За по-ежедневен пример, компютърът може да разчита на атмосферния шум или просто да използва точното време, когато натискате клавишите на клавиатурата като източник на непредсказуеми данни или ентропия. Например, компютърът ви може да забележи, че сте натиснали клавиш точно на 0.23423523 секунди след 14 ч. ... Хванете достатъчно време, свързано с тези натискания на клавиши и ще имате източник на ентропия, който можете да използвате, за да генерирате „истинска“ случайност номер. Вие не сте предсказуема машина, така че хакерът не може да отгатне точния момент, когато натискате тези клавиши. Устройството / dev / random на Linux, което генерира случайни числа, "блокове" и не връща резултат, докато не събере достатъчно ентропия, за да върне наистина случайно число.

Псевдослучайни числа

Псевдослучайните числа са алтернатива на "истинските" случайни числа. Компютърът може да използва семейна стойност и алгоритъм за генериране на числа, които изглеждат случайни, но всъщност са предвидими. Компютърът не събира никакви случайни данни от околната среда.

Това не е непременно нещо лошо във всяка ситуация. Например, ако играете видео игра, няма значение дали събитията, които се случват в тази игра, са обект на „истински“ случайни числа или псевдослучайни числа. От друга страна, ако използвате криптиране, не искате да използвате псевдослучайни числа, които хакер може да отгатне.

Например, да кажем, че един атакуващ знае алгоритъма и семенната стойност, която използва генераторът на псевдослучайни числа. Да кажем, че алгоритъмът за шифроване получава псевдослучайно число от този алгоритъм и го използва за генериране на ключ за криптиране, без да добавя допълнителна случайност. Ако хакерът знае достатъчно, те биха могли да работят назад и да определят псевдослучайния номер, който алгоритъмът за шифроване трябва да е избрал в този случай, като прекъсне шифроването.

NSA и генератора на хардуерни произволни числа на Intel

За да улеснят разработчиците и да помогнат за генерирането на сигурни случайни числа, чиповете на Intel включват хардуерен генератор на случайни числа, известен като RdRand. Този чип използва източник на ентропия на процесора и предоставя случайни числа на софтуера, когато софтуерът ги поиска.

Проблемът тук е, че генераторът на случайни числа е по същество черна кутия и ние не знаем какво става вътре в него. Ако RdR и съдържат задни врати на NSA, правителството ще може да прекъсне ключовете за криптиране, генерирани само с данни, предоставени от този генератор на случайни числа.

Това е сериозна загриженост. През декември 2013 г. разработчиците на FreeBSD премахнаха поддръжката за използване на RdRand директно като източник на случайност, заявявайки, че не могат да му се доверят. [Източник] Изходът на RdRand устройството ще бъде подаден в друг алгоритъм, който добавя допълнителна ентропия, като гарантира, че всички задни врати в генератора на случайни числа няма да имат значение. Linux вече е работил по този начин, като допълнително рандомизира произволните данни, идващи от RdRand, така че да не е предвидимо, дори и да има задната врата. [Източник] В неотдавнашното AMA (“Ask Me Anything”) на Reddit, главният изпълнителен директор на Intel Брайън Крзанич не отговори на въпроси относно тези опасения. [Източник]

Разбира се, това вероятно не е просто проблем с Intel чиповете. Разработчиците на FreeBSD извикаха и чиповете на Via по име. Този спор показва защо генерирането на случайни числа, които са наистина случайни и не са предвидими, е толкова важно.

За да генерират “истински” случайни числа, генераторите на случайни числа събират “ентропия” или привидно случайни данни от физическия свят около тях. За случайни числа, които не го правят наистина ли трябва да бъдат случайни, те могат просто да използват алгоритъм и стойност на семената.

Кредит на изображението: rekre89 на Flickr, Лиса Брюстър на Flickr, Райън Сома на Flickr, huangjiahui на Flickr