jedna matematicka...

[Jan Waclawek]

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
>