Gjenerues i numrave pseudo të rastësishëm. Gjeneruesit e numrave pseudo të rastësishëm

PRNG-të përcaktuese

PRNG-të (PRNG) janë gjenerues të numrave pseudo të rastësishëm. I njëjti term përdoret shpesh për të përshkruar PRBG - gjeneratorë pseudo të rastësishëm bit, si dhe shifra të ndryshme të rrjedhës. PRNG-të, si shifrat e transmetimit, përbëhen nga një gjendje e brendshme (nga 16 bit në disa megabajt në madhësi), një funksion për të inicializuar gjendjen e brendshme me një çelës ose fara, një funksion përditësimi të brendshëm të gjendjes dhe një funksion dalës. PRNG-të ndahen në aritmetikë të thjeshtë, kriptografikë të thyer dhe të fortë kriptografikë. Qëllimi i tyre i përgjithshëm është të gjenerojnë sekuenca numrash që nuk mund të dallohen nga ato të rastit.

Asnjë algoritëm përcaktues nuk mund të gjenerojë numra krejtësisht të rastësishëm, por vetëm të përafrojë disa veti të numrave të rastit. Siç u tha, "Kushdo që ka dobësi për metodat aritmetike për marrjen e numrave të rastësishëm është mëkatar pa dyshim".

Çdo PRNG me burime të kufizuara ngec herët a vonë. Gjatësia e cikleve PRNG varet nga vetë gjeneratori dhe është mesatarisht rreth 2 (n/2) ku n është madhësia e gjendjes së brendshme në bit, megjithëse gjeneratorët linear-kongruentë dhe gjeneratorët LFSR kanë cikle maksimale të rendit 2 n. Nëse një PRNG mund të konvergojë në cikle që janë shumë të shkurtër, ai PRNG bëhet i parashikueshëm dhe i papërdorshëm.

Shumica e gjeneratorëve të thjeshtë aritmetikë, megjithëse të shpejtë, vuajnë nga shumë mangësi serioze:

• Periudha/periudha shumë të shkurtra
• Vlerat e njëpasnjëshme nuk janë të pavarura
• Disa pjesë janë "më pak të rastësishme" se të tjerët
• Shpërndarja e njëanshme e njëanshme
• kthyeshmëria

Në veçanti, algoritmi RANDU, i përdorur për dekada në kompjuter, doli të ishte shumë i dobët. Si rezultat, shumë studime janë më pak të besueshme se sa mund të jenë.

PRNG me burim entropie ose RNG

Së bashku me nevojën ekzistuese për të gjeneruar sekuenca lehtësisht të riprodhueshme të numrave të rastit, ekziston gjithashtu nevoja për të gjeneruar numra krejtësisht të paparashikueshëm ose thjesht krejtësisht të rastësishëm. Gjeneratorë të tillë quhen "gjeneruesit e numrave të rastësishëm" (gjenerator i numrave të rastësishëm) ose shkurt RNG. Meqenëse gjeneratorë të tillë përdoren më shpesh për të gjeneruar çelësa unikë simetrikë dhe asimetrikë për enkriptim, ata më së shpeshti ndërtohen nga një kombinim i një PRNG të fortë kriptografikisht dhe një burimi të jashtëm. Kështu, me RNG tani është zakon të nënkuptojmë PRNG-të kripto-rezistente me një burim të jashtëm entropie.

Pothuajse të gjithë prodhuesit kryesorë të mikroçipave furnizojnë RNG-të e harduerit me burime të ndryshme entropie, duke përdorur metoda të ndryshme për t'i pastruar ato nga parashikueshmëria e pashmangshme. Megjithatë, në ky moment shpejtësia e mbledhjes së numrave të rastësishëm nga të gjithë mikroçipet ekzistuese (disa mijëra bit në sekondë) nuk përputhet me shpejtësinë e procesorëve modernë.

Në kompjuterët personalë, autorët e softuerit RNG përdorin burime shumë më të shpejta të entropisë, të tilla si zhurma e kartës së zërit ose vlerat e numëruesit të orës së procesorit që lexohen lehtësisht, për shembull, duke përdorur një udhëzim në procesorët Intel. Para shfaqjes në procesorë të aftësisë për të lexuar vlerën e numëruesit të ciklit të procesorit që është më i ndjeshëm ndaj ndryshimeve më të vogla në mjedis, mbledhja e entropisë ishte pika më e cenueshme e RNG. Ky problem ende nuk është zgjidhur plotësisht në shumë pajisje (p.sh. kartat inteligjente), të cilat kështu mbeten të pambrojtura. Shumë RNG ende përdorin metoda tradicionale (të vjetruara) të mbledhjes së entropisë, siç janë veprimet e përdoruesit (lëvizjet e miut, etj.), si p.sh. Yarrow, ose ndërveprim ndërmjet temave, si p.sh. në Java të sigurta të rastësishme.

Këtu janë disa shembuj të RNG-ve me burimet dhe gjeneratorët e tyre të entropisë:

• /dev/ rastit në / - burimi i entropisë: , megjithatë, mblidhet vetëm gjatë ndërprerjeve të harduerit; PRNG: LFSR, me dalje të hashuar nëpërmjet ; avantazhet: disponohen në të gjitha Unix-et, një burim i besueshëm i entropisë; disavantazhet: "nxehet" për një kohë shumë të gjatë, mund të "ngecë" për një kohë të gjatë, ose funksionon si një PRNG ( /dev/urandom);
• Yarrow nga - burimi i entropisë: metodat tradicionale (të vjetruara); PRNG: AES-256 dhe gjendja e brendshme e vogël; avantazhet: dizajn fleksibël kripto-rezistent; disavantazhet - "nxehet" për një kohë të gjatë, një gjendje shumë e vogël e brendshme, varet shumë nga forca kriptografike e algoritmeve të zgjedhura, është e ngadaltë, është e zbatueshme vetëm për gjenerimin e çelësave;
• gjenerator nga Leonid Yuriev (Leo Yuriev) - burimi i entropisë: zhurma e kartës së zërit; PRNG: ende nuk dihet; avantazhet: ka shumë të ngjarë një burim i mirë dhe i shpejtë i entropisë; disavantazhet - nuk ka asnjë PRNG të pavarur, padyshim kripto-rezistent, ai është i disponueshëm vetëm si një DLL për Windows;
• Microsoft CryptoAPI - burimi i entropisë: koha aktuale, madhësia e diskut, madhësia e memories së lirë, ID e procesit dhe emri i kompjuterit NETBIOS; PRNG: hash i gjendjes së brendshme 128-bit (hash i disponueshëm vetëm në versionet 128-bit të Windows); avantazhet - i integruar në Windows, nuk "ngec"; disavantazhet - një gjendje e vogël e brendshme, lehtësisht e parashikueshme;
• Java SecureRandom - burimi i entropisë: ndërveprimi ndërmjet thread-eve (threads); PRNG: hash i gjendjes së brendshme (1024 bit); avantazhet - në Java nuk ka ende zgjidhje tjetër, një gjendje e madhe e brendshme; disavantazhet: mbledhja e ngadaltë e entropisë, megjithëse në Java nuk ka ende zgjidhje tjetër;
• Kaos nga Ruptor - burimi i entropisë: , mblidhet vazhdimisht; PRNG: hashimi i gjendjes së brendshme 4096-bit bazuar në versionin jolinear të gjeneratorit Marsaglia; avantazhet: ndërsa më e shpejta nga të gjitha, gjendja e brendshme e madhe, nuk "ngec".

Hardware PRNG

Përveç gjeneratorëve të vjetëruar të njohur LFSR që u përdorën gjerësisht si PRNG harduerike në shekullin e kaluar, për fat të keq dihet shumë pak për PRNG-të moderne të harduerit (shifrat e rrjedhës), pasi shumica e tyre janë zhvilluar për qëllime ushtarake dhe mbahen sekret. Pothuajse të gjitha PRNG-të ekzistuese të pajisjeve komerciale janë të patentuara dhe gjithashtu mbahen sekret. PRNG-të e harduerit kufizohen nga kërkesat strikte për konsumin e memories (më shpesh, përdorimi i memories është i ndaluar), shpejtësia (1-2 cikle) dhe zona (disa qindra qeliza FPGA ose ASIC). Për shkak të kërkesave të tilla strikte për harduerin PRNG, është shumë e vështirë të krijohet një gjenerator kriptorezistent, prandaj, deri më tani, të gjitha PRNG-të e njohura të harduerit janë prishur. Shembuj të gjeneratorëve të tillë janë Toyocrypt dhe LILI-128, të cilët janë të dy gjeneratorë LFSR dhe të dy janë prishur duke përdorur sulme algjebrike.

Për shkak të mungesës së PRNG-ve të mira harduerike, prodhuesit janë të detyruar të përdorin kode blloku shumë më të ngadaltë por të njohur gjerësisht si AES dhe funksionet hash si p.sh.

Teknologjia e parë e përdorur gjerësisht për gjenerimin e një numri të rastësishëm ishte algoritmi i propozuar nga Lehmer, i cili njihet si metoda lineare kongruente. Ky algoritëm është i parametrizuar nga katër numra si më poshtë:

Sekuenca e numrave të rastit (X n ) merret duke përdorur barazinë përsëritëse të mëposhtme:

X n +1 = (a X n + c) mod m

Nëse m, a dhe c janë numra të plotë, atëherë krijohet një sekuencë numrash të plotë në rangun 0 X n< m.

Zgjedhja e vlerave për a, c dhe m është kritike për zhvillimin e një gjeneruesi të mirë të numrave të rastësishëm.

Natyrisht, m ​​duhet të jetë shumë i madh që të jetë në gjendje të gjenerojë shumë numra të rastit. Besohet se m duhet të jetë afërsisht e barabartë me numrin e plotë pozitiv maksimal për këtë kompjuter. Kështu, zakonisht m është afër ose e barabartë me 2 31 .

Ekzistojnë tre kritere të përdorura kur zgjidhni një gjenerues të numrave të rastësishëm:

1. Funksioni duhet të krijojë një periudhë të plotë, d.m.th. të gjithë numrat ndërmjet 0 dhe m përpara se numrat e gjeneruar të fillojnë të përsëriten.

2. Sekuenca e krijuar duhet të shfaqet rastësisht. Sekuenca nuk është e rastësishme pasi gjenerohet në mënyrë deterministe, por teste të ndryshme statistikore që mund të aplikohen duhet të tregojnë se sekuenca është e rastësishme.

3. Funksioni duhet të zbatohet në mënyrë efektive në procesorët 32-bit.

Vlerat e a, c dhe m duhet të zgjidhen në atë mënyrë që të plotësohen këto tre kritere. Në përputhje me kriterin e parë, mund të tregohet se nëse m është i thjeshtë dhe c = 0, atëherë për një vlerë të caktuar të a, periudha e krijuar nga funksioni do të jetë e barabartë me m-1. Për aritmetikën 32-bitësh, vlera e thjeshtë përkatëse është m = 2 31 - 1. Kështu, funksioni për gjenerimin e numrave pseudo të rastësishëm është:

X n +1 = (a X n) mod (2 31 - 1)

Vetëm një numër i vogël i vlerave të një i plotëson të tre kriteret. Një vlerë e tillë është a = 7 5 = 16807, e cila është përdorur në familjen e kompjuterëve IBM 360. Ky gjenerator përdoret gjerësisht dhe ka kaluar më shumë se një mijë teste, më shumë se të gjithë gjeneruesit e tjerë të numrave pseudo rastësor.

Fuqia e algoritmit linear kongruent është se nëse faktori dhe moduli (baza) janë zgjedhur siç duhet, atëherë sekuenca rezultuese e numrave do të jetë statistikisht e padallueshme nga një sekuencë që është e rastësishme nga grupi 1, 2, ..., m- 1. Por nuk mund të ketë rastësi në sekuencën e marrë duke përdorur algoritmin, pavarësisht nga zgjedhja e vlerës fillestare X 0. Nëse zgjidhet një vlerë, atëherë numrat e mbetur në sekuencë do të paracaktohen. Kjo gjithmonë merret parasysh në kriptanalizë.

Nëse kundërshtari e di se përdoret algoritmi linear kongruent dhe nëse parametrat e tij janë të njohur (a = 7 5 , c = 0, m = 2 31 - 1), atëherë nëse zbulohet një numër, e gjithë sekuenca e numrave bëhet e njohur . Edhe nëse kundërshtari e di vetëm se përdoret algoritmi linear kongruent, njohja e një pjese të vogël të sekuencës është e mjaftueshme për të përcaktuar parametrat e algoritmit dhe të gjithë numrat pasues. Supozoni se armiku mund të përcaktojë vlerat e X 0 , X 1 , X 2 , X 3 . Pastaj:

X 1 \u003d (a X 0 + c) mod mX 2 \u003d (a X 1 + c) mod mX 3 \u003d (a X 2 + c) mod m

Këto barazi na lejojnë të gjejmë a, c dhe m.

Kështu, megjithëse algoritmi është një gjenerues i mirë i një sekuence pseudo të rastësishme numrash, është e dëshirueshme që sekuenca e përdorur në të vërtetë të jetë e paparashikueshme, pasi në këtë rast, njohja e një pjese të sekuencës nuk do të lejojë që dikush të përcaktojë elementët e saj të ardhshëm. . Ky qëllim mund të arrihet në disa mënyra. Për shembull, duke përdorur orën e brendshme të sistemit për të modifikuar rrjedhën e numrave të rastësishëm. Një mënyrë për të përdorur orën është të rinisni sekuencën pas N numrave, duke përdorur vlerën aktuale të orës modulo m si vlerë të re fillestare. Një mënyrë tjetër është thjesht të shtoni vlerën aktuale të kohës në çdo modul m të numrave të rastësishëm.

algoritmi për gjenerimin e numrave pseudo të rastësishëm, i quajtur Algoritmi BBS(nga emrat e autorëve - L. Blum, M. Blum, M. Shub) ose gjenerator kuadratik i mbetjes. Për qëllime të kriptografisë, kjo metodë u propozua në 1986.

Është si më poshtë. Së pari, dy numrat kryesorë të mëdhenj 1 Një numër i plotë pozitiv më i madh se një quhet thjeshtë, nëse nuk pjesëtohet me asnjë numër tjetër përveç vetes dhe një. Për më shumë informacion mbi numrat e thjeshtë, shihni "Bazat e teorisë së numrave të përdorura në kriptografinë e çelësit publik". numrat p dhe q. Numrat p dhe q duhet të jenë të dy të krahasueshme me 3 modul 4, pra kur pjesëtohen p dhe q me 4, duhet të fitohet e njëjta mbetje 3. Më pas, llogaritet numri M = p * q, i quajtur numri i plotë i Bloom. Pastaj zgjidhet një tjetër numër i plotë i rastësishëm x, koprim (d.m.th., duke mos pasur pjesëtues të përbashkët përveç njërit) me M. Llogaritni x0= x 2 mod M . x 0 quhet numri fillestar i gjeneratorit.

Në çdo hap të n-të të gjeneratorit, llogaritet x n+1 = x n 2 mod M. Rezultati i hapit të n-të është një bit (zakonisht më pak i rëndësishëm) i x n+1. Ndonjëherë bitet e barazisë merren si rezultat, domethënë numri i njësheve në paraqitjen binar të elementit. Nëse numri i njësive në hyrjen e numrit është çift - biti i barazisë merret i barabartë me 0, tek - biti i barazisë merret si 1.

Për shembull, le të p = 11, q = 19 (sigurohemi që 11 mod 4 = 3, 19 mod 4 = 3 ). Atëherë M = p* q = 11*19=209 . Ne zgjedhim x coprime në M: le të x = 3. Llogaritni numrin fillestar të gjeneratorit x 0:

x 0 = x 2 mod M = 3 2 mod 209 = 9 mod 209 = 9.

Llogaritni dhjetë numrat e parë x i duke përdorur algoritmin BBS. Ne do të marrim bitin më pak të rëndësishëm në paraqitjen binar të numrit x i si bit të rastësishëm:

x 1 = 9 2 mod 209 = 81 mod 209 = 81	bit i ulët:	1
x 2 \u003d 81 2 mod 209 \u003d 6561 mod 209 \u003d 82	bit i ulët:	0
x 3 = 82 2 mod 209 = 6724 mod 209 = 36	bit i ulët:	0
x 4 = 36 2 mod 209 = 1296 mod 209 = 42	bit i ulët:	0
x 5 = 42 2 mod 209 = 1764 mod 209 = 92	bit i ulët:	0
x 6 = 92 2 mod 209 = 8464 mod 209 = 104	bit i ulët:	0
x 7 \u003d 104 2 mod 209 \u003d 10816 mod 209 \u003d 157	bit i ulët:	1
x 8 \u003d 157 2 mod 209 \u003d 24649 mod 209 \u003d 196	bit i ulët:	0
x 9 \u003d 196 2 mod 209 \u003d 38416 mod 209 \u003d 169	bit i ulët:	1
x 10 \u003d 169 2 mod 209 \u003d 28561 mod 209 \u003d 137	bit i ulët:	1

Vetia më interesante e kësaj metode për qëllime praktike është se për të marrë numrin e n-të të sekuencës, nuk është e nevojshme të llogariten të gjithë n numrat e mëparshëm x i. Rezulton se x n mund të merret menjëherë nga formula

Për shembull, le të llogarisim x 10 menjëherë nga x 0:

Si rezultat, ne vërtet morëm të njëjtën vlerë si në llogaritjen vijuese, - 137 . Llogaritjet duken mjaft të komplikuara, por në fakt ato janë të lehta për t'u mbyllur në një procedurë ose program të vogël dhe për t'u përdorur kur është e nevojshme.

Aftësia për të marrë xn "direkt" bën të mundur përdorimin e algoritmit BBS për kriptimin e transmetimit, për shembull, për skedarë me akses të rastësishëm ose fragmente skedarësh me regjistrime të bazës së të dhënave.

Siguria e algoritmit BBS bazohet në vështirësinë e faktorizimit të një numri të madh M. Argumentohet se nëse M është mjaft e madhe, mund të mos mbahet e fshehtë; derisa M nuk është faktorizuar, askush nuk mund të parashikojë daljen e gjeneratorit PRNG. Kjo për faktin se problemi i faktorizimit të numrave të formës n = pq (p dhe q janë numra të thjeshtë) në faktorë është llogaritur shumë i vështirë nëse dimë vetëm n, dhe p dhe q janë numra të mëdhenj që përbëhen nga disa dhjetëra ose qindra bit (kjo e ashtuquajtur problemi i faktorizimit).

Për më tepër, mund të vërtetohet se një sulmues, duke ditur një sekuencë të krijuar nga gjeneratori BBS, nuk do të jetë në gjendje të përcaktojë as bitet e mëparshme para tij dhe as ato të ardhshme. Gjenerator BBS e paparashikueshme në drejtimin e majtë Dhe në drejtimin e duhur. Kjo veti është shumë e dobishme për qëllime të kriptografisë dhe lidhet gjithashtu me veçoritë e faktorizimit të numrit M.

Pengesa më e rëndësishme e algoritmit është se ai nuk është mjaft i shpejtë, gjë që nuk e lejon atë të përdoret në shumë fusha, për shembull, në llogaritjet në kohë reale dhe, për fat të keq, në enkriptimi i transmetimit.

Por ky algoritëm prodhon një sekuencë vërtet të mirë numrash pseudo të rastësishëm me një periudhë të madhe (me një zgjedhje të përshtatshme të parametrave fillestarë), gjë që lejon që ai të përdoret për qëllime kriptografike kur gjeneron çelësat e enkriptimit.

Termat kyç

shifra e rrjedhës- shifra e transmetimit.

Algoritmi BBSështë një nga metodat për gjenerimin e numrave pseudo të rastësishëm. Emri i algoritmit vjen nga emrat e autorëve - L. Blum, M. Blum, M. Shub. Algoritmi mund të përdoret në kriptografi. Për të llogaritur numrin tjetër x n+1 sipas algoritmit BBS, përdoret formula x n+1 \u003d x n 2 mod M, ku M \u003d pq është produkti i dy numrave të thjeshtë p dhe q.

Gjeneruesi i numrave pseudorandom (PRNG)- disa algoritëm ose pajisje që krijon një sekuencë bitësh që duken si të rastësishme.

Gjenerator linear kongruent Numrat pseudo të rastësishëm është një nga PRNG-të më të thjeshtë, i cili përdor formulën ki =(a*k i-1 +b) mod c për të llogaritur numrin tjetër ki , ku a, b, c janë disa konstante, ak i-1 është i mëparshmi numër pseudo rastësor.

Metoda Fibonacci me vonesaështë një nga metodat për gjenerimin e numrave pseudo të rastësishëm. Mund të përdoret në kriptografi.

Shifra e transmetimitështë një shifër që kodon mesazhin hyrës një bit (ose bajt) për operacion. Algoritmi inline i enkriptimit eliminon nevojën për të ndarë mesazhin në një numër të plotë blloqesh. Shifrat e transmetimit përdoren për të enkriptuar të dhënat në kohë reale.

Përmbledhje e shkurtër

Një shifër e transmetimit është një shifër që kodon mesazhin hyrës një bit (ose bajt) për çdo operacion. Algoritmi inline i enkriptimit eliminon nevojën për të ndarë mesazhin në një numër të plotë blloqesh. Kështu, nëse një rrjedhë karakteresh transmetohet, çdo karakter mund të kodohet dhe transmetohet menjëherë. Shifrat e transmetimit përdoren për të enkriptuar të dhënat në kohë reale.

Në programet kompjuterike, shpesh është e nevojshme të imitohet rastësia. Për shembull, kur zhvilloni lojëra. Nëse programi ka një gjenerator të caktuar, d.m.th., një prodhues, të një numri të rastësishëm, atëherë, duke përdorur numrin e marrë në këtë mënyrë, mund të zgjidhni një ose një degë tjetër të ekzekutimit të programit, ose një objekt arbitrar nga koleksioni. Me fjalë të tjera, gjëja kryesore është të gjeneroni një numër. Mbi të bazohet emulimi i rastësisë së një lloji tjetër.

Sigurisht që nuk e dimë nëse ka ndonjë aksident në natyrë, apo na duket vetëm për shkak të njohurive të kufizuara të njohurive tona. Ne e dimë vetëm se nuk ka rastësi të vërtetë në programim. Askund për të marrë një numër arbitrar, nuk mund të programoni pamjen e tij nga askund. Mund të krijoni vetëm një program që, si rezultat i aplikimit të një formule komplekse në "farë", do të prodhojë një numër dhe do të na duket se ky numër është i rastësishëm.

"Grain" është të dhënat fillestare për formulën. Mund të jetë, për shembull, koha e sistemit në milisekonda, e cila ndryshon vazhdimisht. Prandaj, "kokrra" do të jetë vazhdimisht e ndryshme. Ose programuesi mund ta vendosë vetë.

Një program i tillë (në fakt një modul ose funksion) quhet gjenerues i numrave pseudo të rastësishëm. Biblioteka standarde Python përfshin modulin e rastësishëm. Ai përmban shumë funksione që lidhen me emulimin e rastësisë (për shembull, "përzierja" e elementeve të një sekuence), dhe jo vetëm funksione për gjenerimin e numrave pseudo të rastësishëm.

Ky tutorial do të mbulojë funksionet random(), randrange() dhe randint() nga moduli i rastësishëm. Vini re se moduli i rastësishëm përmban funksionin random() me të njëjtin emër. Ndodh.

Për të hyrë në funksione, duhet të importoni modulin e rastësishëm:

>>> importoni rastësisht

Ose importoni funksione individuale prej tij:

>>> nga importi i rastësishëm, i rastësishëm, i rëndomtë, i rastësishëm

Funksionet për marrjen e numrave të plotë "të rastësishëm" - randint() dhe ranrange()

Funksionet randint() dhe randrange() gjenerojnë numra të plotë pseudo të rastësishëm. E para prej tyre është më e thjeshta dhe merr gjithmonë vetëm dy argumente - kufijtë e gamës së numrit të plotë nga i cili zgjidhet çdo numër:

>>> rastësor .randint (0 , 10 ) 6

ose (nëse janë importuar funksione të veçanta):

>>> randint (100 , 200 ) 110

Në rastin e randint(), të dy kufijtë përfshihen në diapazonin, d.m.th., në gjuhën e matematikës, segmenti përshkruhet si.

Numrat mund të jenë negativ:

>>> rastësor .randint (-100 , 10 ) -83 >>> rastësor .randint (-100 , -10 ) -38

Por numri i parë duhet të jetë gjithmonë më i vogël ose të paktën i barabartë me të dytin. Ajo eshte nje<= b.

Funksioni randrange() është më i komplikuar. Mund të marrë një argument, dy apo edhe tre. Nëse specifikohet vetëm një, atëherë ai kthen një numër të rastësishëm midis 0 dhe argumentit të specifikuar. Për më tepër, vetë argumenti nuk përfshihet në interval. Në gjuhën e matematikës, kjo është