Што е генератор на случајни броеви?
Генератор на случајни броеви (RNG) е систем што произведува случајни или псевдослучајни броеви. Дали следниот број може навистина да се предвиди зависи од видот на генераторот. Некои генератори се потпираат на физички процес, некои ги пресметуваат своите броеви со алгоритам, а некои алгоритми се изградени така што дури и некој што го видел нивниот претходен резултат не може да предвиди што следува. Да се изгледа случајно и да се биде непредвидлив се различни својства, и најголемиот дел од овој текст е посветен токму на таа разлика.
Хардверски генератори на случајни броеви
Хардверски генератор на случајни броеви (HRNG), исто така наречен вистински генератор на случајни броеви (TRNG), ги изведува своите броеви од физички процес. Најстарите работат пред нашите очи: фрлена монета, фрлена коцка, рулет. Механиката целосно го опишува секој од нив, но сепак добро изработено тркало во пракса е непредвидливо, бидејќи ситните разлики во тоа како започнува секое вртење прераснуваат во сосема различни исходи.
Современите хардверски генератори наместо тоа мерат микроскопски феномени: сачмен (shot) и термички шум во електронски кола, атмосферски шум, квантни ефекти. Ова се добри извори на ентропија — мерлива непредвидливост — но физичкиот извор по својата природа не е совршен: може да биде пристрасен, неговите параметри можат да се поместат со текот на времето, а може и да откаже. Затоа неговиот квалитет мора да се оценува и следи, а неговиот резултат дополнително да се обработува каде што е потребно, како што опишуваат стандардите како NIST SP 800-90B. Хардверските извори се користат таму каде што гаранцијата е најважна — пред сѐ во криптографијата, каде што обезбедуваат непредвидлив почетен материјал за клучевите зад протоколите како што е безбедноста на транспортниот слој (TLS).
Псевдослучајни генератори на броеви
Алтернативата за физички уред е алгоритам. Псевдослучаен генератор на броеви (PRNG) произведува низа што изгледа случајно, но е целосно одредена од почетна вредност наречена семе (seed). Внесете ја истата почетна вредност во истиот алгоритам и секој пат ќе ја добиете истата низа. Тоа е слабост секаде каде што резултатот мора да биде непредвидлив, а почетната вредност или внатрешната состојба може да се погоди или реконструира, и предност секаде каде што резултатот мора да биде повторлив — симулација или тест може повторно да се изврши точно на ист начин. PRNG се исто така брзи, евтини и лесни за имплементација, поради што повеќето софтвери се потпираат на нив. Добро познати алгоритми се линеарниот конгруентен генератор (LCG), генераторите xorshift и Mersenne Twister.
Mersenne Twister
Mersenne Twister, објавен во 1997 година од Макото Мацумото и Такуџи Нишимура, е еден од најшироко користените генератори на псевдослучајни броеви и стандарден избор во многу програмски јазици. Неговото име потекнува од неговиот период — должината на низата пред да почне да се повторува — кој во стандардната варијанта MT19937 е Мерсеновиот прост број 219937 − 1. Тој поминува повеќето статистички тестови за случајност и добро одговара за симулации. Сепак, тој не е дизајниран за чување тајни: од 624 последователни 32-битни излезни вредности секој може да ја реконструира неговата внатрешна состојба и да ја предвиди секоја вредност што следува, па затоа не смее да се користи за клучеви, лозинки или било што друго што мора да остане непредвидливо.
Криптографски безбедни генератори и ентропија
На многу апликации им се потребни двете работи одеднаш: брзината на алгоритамот и непредвидливоста на физичкиот извор. Одговорот е криптографски безбеден генератор на псевдослучајни броеви (CSPRNG). Тоа е сè уште PRNG, но изграден така што гледањето дел од неговиот излез не дава практичен начин да се предвиди остатокот, и се иницијализира и редовно освежува од извор на вистинска ентропија. Почетната вредност од физички извор не прави обичен PRNG безбеден; самиот алгоритам мора да биде дизајниран за тоа. Физички извор како термички шум или времето на хардверски настани обезбедува мала количина вистинска случајност, а CSPRNG од неа многу побрзо добива долга низа вредности. Оваа комбинација е она што оперативниот систем им го нуди на програмите што работат на него, и тоа е она што „генератор на случајни броеви“ обично значи во практиката денес. Тој создава клучеви за шифрирање, сесиски токени и лозинки.
Случајни броеви во прелистувачот
JavaScript му дава на веб-страницата два вградени начини за добивање случајни вредности, и тие припаѓаат на различни категории. Math.random() е обичен PRNG: јазичниот стандард го остава алгоритмот на секој прелистувач и не гарантира ништо за безбедноста — погоден за анимација, но несоодветен за извлекување што некој би можел да го оспори. Другиот е Web Crypto API. Неговиот метод crypto.getRandomValues() враќа криптографски силни случајни вредности, произведени од CSPRNG кој е иницијализиран со ентропијата на оперативниот систем.
Нашиот онлајн генератор на случајни броеви користи Web Crypto API за секое извлекување, а броевите се создаваат во вашиот прелистувач наместо на сервер. Истиот извор ги придвижува и другите генератори на оваа страница, без разлика дали фрлате коцки, фрлате монета или генерирате лозинка.
Од случајни битови до број во вашиот опсег
Криптографски безбеден генератор е само половина од фер извлекување. Тој испорачува сурови битови, а програмата сè уште мора да ги претвори во број во вашиот опсег — и тука може да се појави пристрасност. Да претпоставиме дека изворот ги дава вредностите од 0 до 9 со еднакви шанси, а вам ви треба број од 0 до 5. Земањето на остатокот по делењето со 6 изгледа природно, но 0, 1, 2 и 3 тогаш можат да се појават на два начини, а 4 и 5 само на еден начин. Така, секој од броевите од 0 до 3 има 20% шанса, а 4 и 5 само по 10%. Еден начин да се отстрани оваа пристрасност (modulo bias) е да се отфрлат вредностите што не одговараат и да се извлекува повторно; материјалите за генераторот на случајни броеви навлегуваат во ова детално.
Уште две работи ги изненадуваат луѓето. Повторувањата се нормални: кога цел број од 1 до 10 се извлекува независно и секој број е подеднакво веројатен, тукушто извлечениот број има иста шанса 1 од 10 да се појави повторно како и секој друг. Извлекување без повторувања е различен вид извлекување, а не повеќе случајно. И самиот фер генератор не ја прави целата постапка фер: списокот на учесници и бројот на обиди се исто толку важни, како што објаснува нашиот водич за тоа како да изберете случаен победник на наградна игра.