Matikkaa tietokoneella

[Disputator]

Iltapäivää

Keskeinen raja-arvolause todennäköisyyslaskennassa

Tätä kuuluisaa lausetta testasin reaalimaailman datalla. Aivojeni valintapolkuja en osaa selittää, mutta päädyin siihen, että perusjoukko on 5 km alueella Zürichistä mitatut maanpinnan korkeudet (keskimääräisestä merenpinnasta). Pisteitä on 101 781.

Kuvassa korkeuksien luokkaväli on 20 m, ja pystyakseli on todennäköisyys sille, että satunnaisesti poimittu korkeus \(x\) osuu kyseiselle välille, esimerkiksi \(P(400\le x<420)=0.19\). Keskimääräiseksi korkeudeksi sain \(\bar x = 492.778\)


Zurich korkeudet merenpinnasta.png


Tein pienehkön satunnaisotannan palauttamatta, otoksen koko vain 500. Toistin kuitenkin tämän 5000 kertaa. Yksittäisen otoksen korkeuksien keskiarvo on \(\bar x\), ja kaikkien otoksien kesiarvot ovat joukko \(\{\bar x_1,\bar x_2,\bar x_3,...,\bar x_{5000}\}\).

Näiden 5000 keskiarvon joukosta sain keskiarvon \(\mu=492.736\) ja keskihajonnan \(\sigma=3.997\). Normaalijakauman tiheysfunktio on

$$f(x)=\frac{1}{\sqrt{2 \pi \sigma^2} }e^{-\frac{(x-\mu )^2}{2 \sigma ^2}}$$

Plottasin nuo 5000 keskiarvoa (luokkaväli 1 m), ja niitä vastaavat todennäköisyystiheydet pystyakselille. Lisäsin samaan kuvaan sinisellä normaalijakauman tiheysfunktion \(f(x)\).


keskeinen raja-arvolause.png


Keskeinen raja-arvolause pätee tässä varsin hyvin, joskin 5000 kertaa toisto hiukan liioittelua. Mutta matematiikka on kaunista!

 

Olipas mielenkiintoinen havainnollistus, oikeasti, ei kettuilua..

Tuo keskeinen raja-arvolause (CLT) on kyllä jotenkin mystinen juttu, vaikka sen "perusversion" todistaminen tai ainakin uskottavaksi tekeminen ei ole mitenkään supervaikeaa.

[QS]

Kaikkea ne matematiikkasoftat osaa. En ymmärrä kemiasta mitään, mutta plottasin molekyylin

mysteerio.png (49.25 KiB) Katsottu 16441 kertaa

[Abezethibou]

stellarium-001.jpg (386.07 KiB) Katsottu 95 kertaa

Asun Tampereella Kalevan kirkon kupeessa, niin tein Googlen katunäkymän kuvista 360 asteen kuvan omilta kotinurkilta. Nyt on kiva Stellariumista katsoa tähtitaivasta juuri niin kuin se näkyy omilla nurkilla ja tietysti mistä ilmansuunnasta tahansa. Kuvassa näkyy myös Kalevan kirkon siluetti. Vielä pitää maiseman ilmansuunnat säätää oikein tähtitaivaan kanssa ja vähän siivota pilvistä taivasta muutamista kohdista. Se on sitä meikäläisen tuuria, että Google oli ottanut kuvansa juuri silloin kun taivas oli kokonaan tummien pilvien peitossa. Niiden siivoaminen pois oli melkoinen savotta. Matikkaa on aika paljon tämänkin taustalla ja tähtiluetteloita.

[Abezethibou]

stellarium-002.jpg (333.93 KiB) Katsottu 78 kertaa

Sehän oli 90 astetta pielessä. Nyt ehkä oikein.

[Abezethibou]

Neuvokaapa viisaammat minua. Jos tuotan kaksi satunnaislukua. Toisen RDSEED komennolla joka käyttää prosessorin entropialähdettä ja toisen TPM sirusta, niin miten teen diffuusion noiden kahden välillä? Onko pelkkä XOR riittävä vai pitäisikö vääntää jotain muuta? Tavoitteena saada kaksi erilaista entropian lähdettä yhdistämällä parempia satunnaislukuja.

[QS]

Neuvokaapa viisaammat minua. Jos tuotan kaksi satunnaislukua. Toisen RDSEED komennolla joka käyttää prosessorin entropialähdettä ja toisen TPM sirusta, niin miten teen diffuusion noiden kahden välillä? Onko pelkkä XOR riittävä vai pitäisikö vääntää jotain muuta? Tavoitteena saada kaksi erilaista entropian lähdettä yhdistämällä parempia satunnaislukuja.

En ole viisaampi, mutta yleisellä aiheen tuntemuksella sanoisin, että tässä tapauksessa XOR tuottaa satunnaisluvun, joka on korkeintaan yhtä hyvä kuin näiden (riippumattomien) lähteiden parempi satunnaisluku. Asiasta on olemassa teoriakin, jonka yksityiskohtia en muista.

Voisi miettiä käyttötarkoitusta. Jos kyseessä salaus, niin esim TPM-siruun tunkeutuja voi purkaa XOR:in, jos sattuu arvaamaan, että käytät XOR:ia, ja siten selvittää prosessorin antaman satunnaisluvun. Tässä tapauksessa XOR:n sijasta/lisäksi voisi käyttää jotain algoritmia, joka "salaa" tuon XOR:n antaman satunnaisluvun.

Mutta ehkä joku viisas osaa sanoa täsmällisen vastauksen.

[Abezethibou]

Neuvokaapa viisaammat minua. Jos tuotan kaksi satunnaislukua. Toisen RDSEED komennolla joka käyttää prosessorin entropialähdettä ja toisen TPM sirusta, niin miten teen diffuusion noiden kahden välillä? Onko pelkkä XOR riittävä vai pitäisikö vääntää jotain muuta? Tavoitteena saada kaksi erilaista entropian lähdettä yhdistämällä parempia satunnaislukuja.

En ole viisaampi, mutta yleisellä aiheen tuntemuksella sanoisin, että tässä tapauksessa XOR tuottaa satunnaisluvun, joka on korkeintaan yhtä hyvä kuin näiden (riippumattomien) lähteiden parempi satunnaisluku. Asiasta on olemassa teoriakin, jonka yksityiskohtia en muista.

Voisi miettiä käyttötarkoitusta. Jos kyseessä salaus, niin esim TPM-siruun tunkeutuja voi purkaa XOR:in, jos sattuu arvaamaan, että käytät XOR:ia, ja siten selvittää prosessorin antaman satunnaisluvun. Tässä tapauksessa XOR:n sijasta/lisäksi voisi käyttää jotain algoritmia, joka "salaa" tuon XOR:n antaman satunnaisluvun.

Mutta ehkä joku viisas osaa sanoa täsmällisen vastauksen.

Joo näin se tietysti on. Nyt tosin ei ole pelkoa tunkeutujista tai mistä sitä koskaan tietää jos vaikka vieraita valtoja kiinnostaisi meikäläisen hörhötykset. Kokeilin RDSEED:in kanssa tämmöistä "valkaisufunktiota":

Koodi: Valitse kaikki

static inline void whitening(unsigned long long *val) {
/* Vaihe 1: AES-NI pohjainen diffuusio */
__m128i data = _mm_set_epi64x(0, *val);
__m128i key = _mm_aeskeygenassist_si128(data, 0x1);

for(int i = 0; i < AES_ROUNDS; i++) {
key = _mm_aeskeygenassist_si128(key, i);
data = _mm_aesenc_si128(data, key);
}

/* Vaihe 2: Bittitason permutaatio GCC-intrinsics */
uint64_t mixed = _mm_extract_epi64(data, 0) ^ _mm_extract_epi64(data, 1);
mixed = __rorq(mixed, (mixed % 24)) ^ __rolq(mixed, (mixed % 40));
mixed = _mm_crc32_u64(0xFFFFFFFF, mixed);

/* Vaihe 3: Epälineaarinen transformaatio */
for(int i = 0; i < MIXER_ROUNDS; i++) {
mixed = (mixed * 0x5BD1E9955BD1E995) + 0x9E3779B97F4A7C15;
mixed ^= (mixed >> 32) | (mixed << 32);
mixed = __rorq(mixed, 17) ^ __rolq(mixed, 29); // Korjattu rotaatiot
}

/* Vaihe 4: Adaptiivinen sekoitus */
static __uint128_t entropy_buffer = 0;
entropy_buffer = _mm_crc32_u64(entropy_buffer, mixed);
*val = mixed ^ (entropy_buffer >> 64) ^ entropy_buffer;
}

Mitään iloa siitä ei ollut ainakaan FIPS 140-2 testissä. Kokeilin 300000 satunnaisluvun sarjalla, niin 0.0787% ei mennyt testistä läpi. Vaan jos tuota kehittelisi pidemmälle ja ottaisi sen TPM sirun tarjooman satunnaisluvun soppaan mukaan. Ihan hyvää tavaraa tuo RDSEED tekee sellaisenaankin. Ainoa että jos prosessori lämpiää kovin kuumaksi, niin laatu väitetysti heikkenee. Tässä pelkkää RDSEED:iä.

dieharder.jpg (521.01 KiB) Katsottu 35 kertaa

[Abezethibou]

Se taitaa olla niin, että XOR-operaatio kahden (tai useamman) lähteen välillä ei voi parantaa laatua yli sen parhaan yksittäisen lähteen mutta se ei myöskään huononna tulosta jos lähteet ovat toisistaan riippumattomia. Jos siis prosessori kuumenee mikä saattaa huonontaa RDSEED:in laatua tulee TPM parantamaan tilannetta. Jotain tuollaista ajattelin, mutta ei olisi ensimmäinen aivopieru tämäkään. En tosin oikeasti luota kumpaankaan ja niiden tilalle tulee Infinite Noise TRNG.

[QS]

Se taitaa olla niin, että XOR-operaatio kahden (tai useamman) lähteen välillä ei voi parantaa laatua yli sen parhaan yksittäisen lähteen mutta se ei myöskään huononna tulosta jos lähteet ovat toisistaan riippumattomia.

Ainakin päättelemällä näin on. Esimerkiksi jos huono lähde tuottaisi koko ajan vain lukua 0, niin XOR toisen hyvän satunnaisluvun kanssa ei huononna tätä hyvää lähdettä. Päättely ei toki todistan mitään, vaan vain toteaa erään erikoistapauksen.

[Abezethibou]

Se taitaa olla niin, että XOR-operaatio kahden (tai useamman) lähteen välillä ei voi parantaa laatua yli sen parhaan yksittäisen lähteen mutta se ei myöskään huononna tulosta jos lähteet ovat toisistaan riippumattomia.

Ainakin päättelemällä näin on. Esimerkiksi jos huono lähde tuottaisi koko ajan vain lukua 0, niin XOR toisen hyvän satunnaisluvun kanssa ei huononna tätä hyvää lähdettä. Päättely ei toki todistan mitään, vaan vain toteaa erään erikoistapauksen.

Sen voi todistaa Shannonin tai Min entropialla?
\(H(Z) \;\ge\; \max\bigl(H(X),\,H(Y)\bigr)\)
\(H_{\infty}(Z) \;=\; \min\bigl(H_{\infty}(X),\,H_{\infty}(Y)\bigr)\)