jedna matematicka...

[Zuffa Jan]

Uff, to si sa rozpisal
Zaujimave citanie. K tomu len jedna drobnost,
korelacia nie je konvolucia aspon teda exaktne matematicky
hoci to navovok vypada rovnako :)

j.

-----Original Message-----
From: Hw-list [mailto:hw-list-bounces na list.hw.cz] On Behalf Of Jan Waclawek
Sent: Tuesday, April 09, 2019 11:40 AM
To: HW-news
Subject: Re: jedna matematicka...

Tych kriterii a testov na to, ci je PRNG "dobry", je vela, vid napr.
https://en.wikipedia.org/wiki/Diehard_tests a tam spomenute starsie a novsie verzie/sady testov. No ale ako vznikli? Z praxe, samozrejme. Tie testy sa negeneruju z nejakych "akademickych" dovodov, ale jednoducho kvoli tomu, ze nejake chyby PRNG sa prejavuju v nejakych aplikaciach. A tiez nemusia, PRNG moze pokojne "neprezit" niektory z testov a v aplikacii byt adekvatny - prikladom je prave to LFSR, ktore tvrdosijne drzi ako "zakladny" PRNG (lebo sa dobre implementuje v hardware), pritom je napriklad z pohladu kryptografie uplne ubohy - t.j. sa da z pohladu na stream uhadnut, ze sa jedna o LFSR, pretoze sa v nom v dostatocne velkej sekvencii M vyskytuje vzdy presne Ni sekvencii naslednych nul (alebo jedniciek), co sedi s pravdepodobnostou vyskytu sekvencii naslednych nul v skutocne nahodnom streame, ale tuna to sedi *presne*, pricom skutocne nahodny stream ma samozrejme odchylky (tu vznikne potom nutkanie to LFSR vylepsovat, z toho je to slovicko "nelinearita", no ale to je len slovicko, za tym sa schovava spusta diablikov aj diablov). No ale to pre spustu aplikacii vobec, ale vobec nevadi, vid prax.

Korelacia (t.j. konvolucia dvoch signalov) je jedno z moznych kriterii, ako som povedal, vysetruje, ci nie je jeden signal posunutou a deformovanou verziou druheho. Predstav si fourierku v jednom frekvencnom bode, to je (nie je, ale pre ilustraciu je to dobre) konvolucia sinusu danej frekvencie s vysetrovanym signalom - ak sa v signale "nachadza" ta sinusovka, vyjde vyssie cislo, ak nenachadza, vyjde nizsie (presne cislo a jeho interpretacia zavisi od vselicoho typu okno - lebo sinusovka je nekonecna - normalizacia vstupnych bodov, vydelenie vystupu poctom bodov
apod.) Takze toto kriterium je relevantne pre Tvoj pripad, len ak budes robit konvoluciu tych signalov, alebo nejaku podobnu operaciu, t.j. posuv v case a integraciu (co je len hrozive slovo pre sucet cez cely casovy rozsah). No lenze Ty nebudes; budes ich scitavat v jednom bode bez casoveho posuvu (prip. s konstantnym casovym posuvom). Ja si dokonca dovolim tvrdit, ze pre tento pripad dokonale postaci, ak ten isty vstupny nahodny stream pouzijes 4x, navzajom poposuvany v case. Korelacia bude 100%, takze podla kriteria korelacie je to uplne najhorsie, ale ja tvrdim, ze pre Tvoj pripad puheho scitania to vobec nebude vadit, pretoze v jednom casovom bode budu tie streamy (a ich blizke okolie) navzajom dokonale nahodne.

Ale ako riesenie to nedoporucim, jednoducho preto, lebo to znie prilis nebezpecne, a lebo to Tvoje "scitanie" nemusi byt v skutocnosti puhe scitanie (najma v spojitosti s operaciami pred a po) a moze pokojne v sebe schovavat privela diablikov na to aby niektory z nich v skutocnosti bol casovym posuvom, aj ked si to na prvy pohlad neuvedomis.

No a to scitanie je dovod, preco si myslim, ze ten puhy xor je zle riesenie. Predstav si, ze generujes sumy A, B, C a ten stvrty ako A^B^C; a predstav si, ze namiesto scitania vyslednych signalov pouzijes xor, to by vysledny sumovy signal bol A ^ B ^ C ^ A^B^C = 0, co zrejme nie je dobre pre vysledok, lebo si tam chcel mat sucet styroch sumovych signalov a nie nulu. No ale ja nepouzivam xor ale scitanie, vravis. No, hej, lenze scitanie je "blizky pribuzny" xoru, v skutocnosti scitanie je xor s prenosom medzi radmi - ten prenos to sice trocha "rozmaze", ale zakladny problem tam zostava, ta metoda generacie stvrteho signalu vnasa zavislost, ktoru dovolim si tvrdit na vysledku moze byt vidiet. Pritom sa zase ukazuje, ze korelacia je na vysetrenie takehoto problemu absolutne nevhodna, pretoze ten xorovany signal je vdaka vzajomnemu "rozmazavaniu" s inymi signalmi v akomkolvek pare dokonale nekorelovany - korelacia totiz vysetruje len pary, nie rovno celu stvoricu, a ten problem s xorom sa prejavi len v celej stvorici. (Ten pripad xoru len dvoch signalov, nie vsetkych troch, to cele prilis nevylepsi).

Ake je riesenie? Nuz ja neviem. To je to, ze da sa pomerne lahko povedat, co je zle, ale v principe sa neda povedat, co je dobre, da sa len povedat, ze u tohoto riesenia sme zatial nic zle nepostrehli... myslim si, ze to, co som navrhol, t.j. vysledny signal "shiftovat a akumulovat" (pamatat si predchadzajuci stav a v kazdom kroku ho shiftnut a prixorovat ostatne, mozno tiez vzajomne shiftnute) by mohlo stacit, kedze to "rozmazava" ten xor predchadzajucim stavom, ktory je zase "rozmazavany" po ostatnych bitoch tym shiftom - ale ako som povedal, nie som expert so skusenostami, co pozrie a vidi problem. 

Dalsia vec je, co sa da s takym PRNG streamom urobit. To je prave zakerne v kryptografii, ze nestaci mat nieco, co je podla vsetkych uz ustanovenych kriterii (ako bolo povedane, tych, co vychadzaju z nejakych uz riesenych problemov); nielenze nejake nove kriterium moze ukazat nejaku slabinu, ale co je horsie, ak sa ten stream pouzije "nespravne", tak sa jeho "uz otestovana dobrost" pokazi. Trivialny ucebnicovy priklad je skalovanie, napr. mas fakt dobry nahodny generator od 0 do 255 a potrebujes cisla od 0 do 254, nuz urobis rng mod 255, nie? No nie, lebo nula bude mat dvakrat vyssiu pravdepodobnost vyskytu ako vsetky ostatne cisla. No fajn, tak to budem robit tak, ze ak sa mi vyskytne 255, tak ho vynecham a zoberiem dalsiu hodnotu, co sa tym moze pokazit? No to je to, ze moze, a to ze to moze odhalit nejaky skryty problem povodneho RNG, ktory sa pri "nevynechavani" neprejavi - ja priklad neviem, kedze je to ucebnicovy priklad, verim tomu, ze experti v kryptografii vedia na pockanie vytriast taky z rukava.

Zakernost celej veci spociva v tom, ze *vsetky* operacie maju potencial
*nejako* ten vysledny stream pokazit, a mozno najvacsi borci v kryptografii vedia zo skusenosti odhadnut, ktore operacie su horuci kandidati na pokazenie, ale ja ako bezny uzivatel v podstate musim na nich urobit znova to vysetrenie, ci ten vysledok vyhovuje vsetkym znamym kriteriam, alebo/a ci vyhovuje aplikacii.

Tymto mierim na to, ci to rozbitie jedneho streamu na tri je koser. Z Tvojho vyjadrenia som len odhadol, ze sa jedna o LFSR so stavom 74 bitov; to, ze generuje 14-bitove slova, neviem co presne znamena. No a bohuzial, nie som ten expert, co vie povedat, ci prave takou operaciou rozbitia streamu z LCRNG na tri "postupnym vyberanim" sa moze prejavit nejaky problem, trebars aj konkretnej konstelacie toho LFSR (neznasam to slovo polynom, lebo to sa tyka nenormalnej aritmetiky a normaleho uzivatela to zbytocne matie), ktory sa pri "nevyberani" neprejavi; alebo trebars aj prejavi, len ho nikto na kriterium "budem scitavat niekolko za sebou nasledujucich podsekcii" netestoval... A ano, korelacia je este stale nepatricny test pre Tvoju aplikaciu. Moj dokonale nekvalifikovany odhad tu je, ze sanca na problem je povedzme do 5%, uz je na Tebe, ci Ti to staci.
Alebo pouzit to, co tu spominali uz viaceri, viac generatorov (a pouzijem od nich odkukane fancy slovicko, "ortogonalnych"), tym by sa snad nic nemalo pokazit (teda okrem toho ze ten program v FPGA napuchne).

wek







----- Original Message ---------------


vzorka pol miliona bodov je radovo 10ms z 24 hodinovej sekvencie.
Scitavaju sa data naraz zo 4 senzorov, prave koli znizeniu sumu.



On 08/04/2019 23:19, Jan Waclawek wrote:
>> To ze ti to ukazovalo ty hodnoty jake to ukazovalo souvisi s oknem 
>> kterym pres sebe ty useky prekryvas. Nech si vygenerovat mocnasobek 
>> te PRBS, (treba
> 
> Tohoto, t.j. prveho kroku, cize rozsekania toho povodneho streamu na 3 
> casti, by som sa vobec nebal. Ty si pouzil pomerne extremny kratky 
> priklad a ta korelacia - ako sam pises - sa prejavuje pri opakovani; 
> perioda Danovho PRNG je 24 hodin a predpokladam ze skusanych polmega 
> vzoriek je z toho par minut. To, ze je relativny kratky usek zo 
> sekvencie PRNG s velmi dlhou periodou "dost dobre nahodny" je prave 
> jednou z prvych veci co sa na tych PRNG skuma, takza ako vravim, tohoto by som sa nebal.
> 
> 
>> podla tabulky je miera nahodnosti medzi vsetkymi styrmi priblizne 
>> rovnaka,
> 
> Ma vobec nepocuvas. Ta tabulka nema ziadnu vypovednu hodnotu pre Tvoj 
> pripad.
> 
> wek
> 

_______________________________________________
HW-list mailing list  -  sponsored by www.HW.cz Hw-list na list.hw.cz http://list.hw.cz/mailman/listinfo/hw-list