Matikkaa tietokoneella

[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.

Sen voi todistaa Shannonin tai Min entropialla?
\(H(Z) \;\ge\; \max\bigl(H(X),\,H(Y)\bigr)\)

Näyttää tutulta, ja tuossa siis \(Z = X \oplus Y\), missä \(\oplus\) on XOR-operaatio. Todistus ei varmaankaan ole vaikea, mutta en nyt muista näitä juttuja ulkoa.

Tätä lausetta en tuossa edellä muistanut. Tuon perusteella kahden riippumattoman lähteen laatu voi parantua XOR-operaatiossa, mutta se ei ole koskaan huonompi kuin parhaan lähteen laatu.

Tuli mieleeni, että mikä olisi helppo esimerkki tästä tapauksesta \(H(X\oplus Y) > \max\bigl(H(X),\,H(Y)\bigr)\) eli siis vasemman puolen 'satunnaisuus on parempi' kuin X:n ja Y:n erikseen?

[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)\)

Näyttää tutulta, ja tuossa siis \(Z = X \oplus Y\), missä \(\oplus\) on XOR-operaatio. Todistus ei varmaankaan ole vaikea, mutta en nyt muista näitä juttuja ulkoa. Tuli mieleeni, että mikä olisi helppo esimerkki tapauksesta \(H(X\oplus Y) > \max\bigl(H(X),\,H(Y)\bigr)\) eli siis vasemman puolen 'satunnaisuus on parempi' kuin X:n ja Y:n erikseen?

Jaa olisiko vaikka se että ottaa kaksi toisistaan riippumatonta Bernoulli-lähdettä joissa molemmissa on pieni bias ja katsoo XOR-tuloksen entropiaa? Tarvinnee kirjoitella tätä auki jossain kohtaa. Muutamakin rivi harakanvarpaita tähän tarvitaan.

[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.

Sen voi todistaa Shannonin tai Min entropialla?
\(H(Z) \;\ge\; \max\bigl(H(X),\,H(Y)\bigr)\)

Näyttää tutulta, ja tuossa siis \(Z = X \oplus Y\), missä \(\oplus\) on XOR-operaatio. Todistus ei varmaankaan ole vaikea, mutta en nyt muista näitä juttuja ulkoa. Tuli mieleeni, että mikä olisi helppo esimerkki tapauksesta \(H(X\oplus Y) > \max\bigl(H(X),\,H(Y)\bigr)\) eli siis vasemman puolen 'satunnaisuus on parempi' kuin X:n ja Y:n erikseen?

Jaa olisiko vaikka se että ottaa kaksi toisistaan riippumatonta Bernoulli-lähdettä joissa molemmissa on pieni bias ja katsoo XOR-tuloksen entropiaa? Tarvinnee kirjoitella tätä auki jossain kohtaa. Muutamakin rivi harakanvarpaita tähän tarvitaan.

Joo. Kokeillaan 1-bittisillä satunnaisgeneraattoreilla X ja Y, jotka antavat satunnaisbitit 1 tai 0. Nuo X ja Y ovat hiukan vinksallaan siten, että X tuottaa bitit todennäköisyyksillä

\(P(X=1)=\dfrac{3}{5}\)

\(P(X=0)=\dfrac{2}{5}\)

ja Y on samalla tavalla epäkelpo

\(P(Y=1)=\dfrac{3}{5}\)

\(P(Y=0)=\dfrac{2}{5}\)

Shannonin entropiat ovat$$H(X)=H(Y)=-\sum_{i=0}^{1}P(x_i)\log_2P(x_i)=-\left(\frac{3}{5}\log_2(\frac{3}{5})+\frac{2}{5}\log_2(\frac{2}{5})\right) = 0.971$$XOR-operaattorin jälkeen todennäköisyydet \(P(0)\) ja \(P(1)\) ovat

\(P(X \oplus Y = 0) = P(X=0)\cdot P(Y=0) + P(X=1)\cdot P(Y=1) = \frac{2}{5} \cdot \frac{2}{5} + \frac{3}{5} \cdot \frac{3}{5}=\dfrac{13}{25}\)

\(P(X \oplus Y = 1) = \dfrac{12}{25}\)

Näistä saadaan edellistä kaavaa käyttämällä entropia

\(H(X \oplus Y) = 0.999\)

Tässä tapauksessa tosiaan \(H(X \oplus Y) > \max(H(X),H(Y))\), joten XOR parantaa satunnaisuutta.

[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)\)

Näyttää tutulta, ja tuossa siis \(Z = X \oplus Y\), missä \(\oplus\) on XOR-operaatio. Todistus ei varmaankaan ole vaikea, mutta en nyt muista näitä juttuja ulkoa. Tuli mieleeni, että mikä olisi helppo esimerkki tapauksesta \(H(X\oplus Y) > \max\bigl(H(X),\,H(Y)\bigr)\) eli siis vasemman puolen 'satunnaisuus on parempi' kuin X:n ja Y:n erikseen?

Jaa olisiko vaikka se että ottaa kaksi toisistaan riippumatonta Bernoulli-lähdettä joissa molemmissa on pieni bias ja katsoo XOR-tuloksen entropiaa? Tarvinnee kirjoitella tätä auki jossain kohtaa. Muutamakin rivi harakanvarpaita tähän tarvitaan.

Joo. Kokeillaan 1-bittisillä satunnaisgeneraattoreilla X ja Y, jotka antavat satunnaisbitit 1 tai 0. Nuo X ja Y ovat hiukan vinksallaan siten, että X tuottaa bitit todennäköisyyksillä

\(P(X=1)=\dfrac{3}{5}\)

\(P(X=0)=\dfrac{2}{5}\)

ja Y on samalla tavalla epäkelpo

\(P(Y=1)=\dfrac{3}{5}\)

\(P(Y=0)=\dfrac{2}{5}\)

Shannonin entropiat ovat$$H(X)=H(Y)=-\sum_{i=0}^{1}P(x_i)\log_2P(x_i)=-\left(\frac{3}{5}\log_2(\frac{3}{5})+\frac{2}{5}\log_2(\frac{2}{5})\right) = 0.971$$XOR-operaattorin jälkeen todennäköisyydet \(P(0)\) ja \(P(1)\) ovat

\(P(X \oplus Y = 0) = P(X=0)\cdot P(Y=0) + P(X=1)\cdot P(Y=1) = \frac{2}{5} \cdot \frac{2}{5} + \frac{3}{5} \cdot \frac{3}{5}=\dfrac{13}{25}\)

\(P(X \oplus Y = 1) = \dfrac{12}{25}\)

Näistä saadaan edellistä kaavaa käyttämällä entropia

\(H(X \oplus Y) = 0.999\)

Tässä tapauksessa tosiaan \(H(X \oplus Y) > \max(H(X),H(Y))\), joten XOR parantaa satunnaisuutta.

Joo tässä tapauksessa voi sanoa että XOR kannatti, mutta se on kuitenkin lineaarinen operaatio. Toisaalta helppo, nopea ja tässäkin tarkoituksessa usein käytetty. Minä olen kuitenkin päätymässä kolmeen entropialähteeseen RDSEED, TPM ja Infinite Noise TRNG usb-tikkuun. En käytä XOR:ää, vaan SHA3-512 algoritmia. Sen sisällä tehdään XOR operaatioita, mutta siellä tapahtuu paljon muutakin. Toi tikku on Suomessa lentokentällä tulossa. Ajan sille testejä kunhan saan koodin valmiiksi ja kerron täällä millaisia tuloksia saan.

[Abezethibou]

Koodi: Valitse kaikki

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <x86intrin.h>
#include <unistd.h>
#include <fcntl.h>
#include <openssl/evp.h>

#define BUFFER_SIZE 1024
#define SALT_SIZE 32
#define MAX_RETRIES 5

static uint8_t tpm_salt[SALT_SIZE];

// Lue suola TPM:stä (esim. /dev/tpm0)
static int read_tpm_salt() {
    int fd = open("/dev/tpm0", O_RDONLY);
    if (fd == -1) {
        perror("TPM-virhe");
        return 0;
    }
    
    ssize_t bytes_read = read(fd, tpm_salt, SALT_SIZE);
    close(fd);
    
    if (bytes_read != SALT_SIZE) {
        fprintf(stderr, "Varoitus: TPM-stä luettiin vain %zd tavua\n", bytes_read);
        return 0;
    }
    return 1;
}

// Valkaise RDSEED-arvo HKDF:llä käyttäen TPM-suolaa
static int hkdf_whitening(uint64_t *val) {
    uint8_t ikm[8];  // RDSEED-avainmateriaali
    memcpy(ikm, val, sizeof(*val));
    
    uint8_t okm[8];  // Valkaistu tulos
    
    EVP_PKEY_CTX *ctx = EVP_PKEY_CTX_new_id(EVP_PKEY_HKDF, NULL);
    if (!ctx) return 0;

    if (EVP_PKEY_derive_init(ctx) <= 0 ||
        EVP_PKEY_CTX_set_hkdf_md(ctx, EVP_sha3_256()) <= 0 ||
        EVP_PKEY_CTX_set1_hkdf_salt(ctx, tpm_salt, SALT_SIZE) <= 0 ||
        EVP_PKEY_CTX_set1_hkdf_key(ctx, ikm, sizeof(ikm)) <= 0 ||
        EVP_PKEY_derive(ctx, okm, &(size_t){sizeof(okm)}) <= 0) {
        EVP_PKEY_CTX_free(ctx);
        return 0;
    }
    
    memcpy(val, okm, sizeof(*val));
    EVP_PKEY_CTX_free(ctx);
    return 1;
}

// Lue RDSEED laitteistolta (vain 64-bittinen versio)
static int hardware_rand(uint64_t *val) {
    for (int i = 0; i < MAX_RETRIES; ++i) {
        if (_rdseed64_step(val)) return 1;
        usleep(100 * (i + 1));
    }
    return 0;
}

int main(int argc, char *argv[]) {
    // Alusta TPM-suola
    if (!read_tpm_salt()) {
        fprintf(stderr, "Kriittinen virhe: Suolan lukeminen epäonnistui\n");
        return EXIT_FAILURE;
    }

    // Pääsilmukka
    uint64_t buffer[BUFFER_SIZE];
    size_t buf_pos = 0;
    
    while (1) {
        uint64_t val;
        if (!hardware_rand(&val) || !hkdf_whitening(&val)) {
            fprintf(stderr, "Arvon generointi epäonnistui\n");
            return EXIT_FAILURE;
        }
        
        buffer[buf_pos++] = val;
        
        if (buf_pos == BUFFER_SIZE) {
            fwrite(buffer, sizeof(uint64_t), BUFFER_SIZE, stdout);
            buf_pos = 0;
        }
    }
    
    return EXIT_SUCCESS;
}

En ole vielä testannut että kääntyykö tuo edes. Mutta ideana on hakea ensin TPM sirulta suola. Se on turkasen hidasta ja siksi se haetaan vain kerran ja käytetään samaa suolaa. Sitten käytetään SHA3-256:ta HKDF:ssä. Myöhemmin voi sitten miettiä lisää kun saan kolmannen entropian lähteen. Olen tässä miettinyt neljättäkin. Jos liitän mikrofoniliittimeen VLF vastaanottimen ja generoin satunnaislukuja radion kohinasta.

[QS]

Olen tässä miettinyt neljättäkin. Jos liitän mikrofoniliittimeen VLF vastaanottimen ja generoin satunnaislukuja radion kohinasta.

Vain insinööriaivot keksivät näitä, ja mulla ei tuota kykyä ole

[Disputator]

Luin joskus vuosia sitten jonkun vempaimen käyttöohjeita. Olen sen jälkeenkin toki lukenut käyttöohjeita, mutta se kerta jäi mieleeni syvällisellä tavalla. Siinä ohjeessa käyttöohjeiden laatijoilla oli tapana käyttää erilaisia lyhenteitä niin paljon, että itse tekstistä ei saannut mitään selvää.

Yleensäkin vempaimien käyttöohjeet pitäisi testauttaa ennen julkaisua jollain sopivalla testijengillä, esimerkiksi vanhainkodin asukkailla, lastentarhan lapsilla, paatuneet linnakunditkin käy, jotta nähdään se, että ymmärtääkö keskivertotavis mitään niistä.

Alussa mainitsemani keissi oli tosiaankin malliesimerkki siitä, että insinöörejä ei saa koskaan päästää laatimaan käyttöohjeita, silloin kun luin sitä juttua, haaveilin siitä sitten että minusta tulisi diktaattori ja määräisin tuollaisille käyttöohjeiden "laatijoille" kuolemantuomion ampumalla tai giljotiinilla... 

 

[Abezethibou]

Olen tässä miettinyt neljättäkin. Jos liitän mikrofoniliittimeen VLF vastaanottimen ja generoin satunnaislukuja radion kohinasta.

Vain insinööriaivot keksivät näitä, ja mulla ei tuota kykyä ole

Kävin eilen paikallisella kirpputorilla ja oli ihan pienestä kiinni että en ostanut vanhaa melkein taskuun mahtuvaa kuvaputkitelevisiota. Ehkä vielä ostankin jos tulee vähän halvempi vastaan. Laitan webbikameran kuvaamaan "lumisadetta" kuvaputkella ja generoin webbikameran signaalista satunnaislukuja. Noin 1% vanhan television lumisateesta on alkuperältään kosmista mikroaaltotaustasäteilyä. Loput läheisistä sähkömagneettisista häiriölähteistä, vastaanottimen analogisen elektroniikan termisestä kohinasta ja erilaisista ilmakehän häiriöistä. Varsin hyvä entropian lähde sanoisin.

[Eusa]

Olen tässä miettinyt neljättäkin. Jos liitän mikrofoniliittimeen VLF vastaanottimen ja generoin satunnaislukuja radion kohinasta.

Vain insinööriaivot keksivät näitä, ja mulla ei tuota kykyä ole

Kävin eilen paikallisella kirpputorilla ja oli ihan pienestä kiinni että en ostanut vanhaa melkein taskuun mahtuvaa kuvaputkitelevisiota. Ehkä vielä ostankin jos tulee vähän halvempi vastaan. Laitan webbikameran kuvaamaan "lumisadetta" kuvaputkella ja generoin webbikameran signaalista satunnaislukuja. Noin 1% vanhan television lumisateesta on alkuperältään kosmista mikroaaltotaustasäteilyä. Loput läheisistä sähkömagneettisista häiriölähteistä, vastaanottimen analogisen elektroniikan termisestä kohinasta ja erilaisista ilmakehän häiriöistä. Varsin hyvä entropian lähde sanoisin.

Ehkei sentään entropian lähde mutta informaation lähde kuitenkin.

Muistelen esitetyn, että kun informaatiota saadaan selville, entropia vähenee. Jos kaikki informaatio saadaan selville, häviääkö entropia tyystin?

Tässä on mielenkiintoinen kysymys informaatioteorian ja termodynamiikan rajapinnasta.

 

Informaatioteoriassa entropia mittaa epävarmuutta tai tiedon puutetta. Kun saamme uutta informaatiota, epävarmuus vähenee ja samalla informaatioteoreettinen entropia pienenee. Jos tietäisimme täydellisesti kaiken mahdollisen systeemin tilan, informaatioteoreettinen entropia olisi periaatteen mukaisesti nolla.

 

Termodynamiikassa (lue: todellisuudessa) tilanne on kuitenkin monimutkaisempi. Fysikaalisissa järjestelmissä entropia liittyy systeemin mikrotilojen lukumäärään ja satunnaisuuteen. Vaikka tietäisimme kaiken järjestelmästä makroskooppisella tasolla, kvanttimekaniikan epävarmuusperiaate estää meitä tietämästä kaikkea täydellisesti mikroskooppisella tasolla.

 

Lisäksi on syytä huomata, että informaation hankkiminen itsessään vaatii energiaa ja tyypillisesti tuottaa entropiaa ympäristöön (Landauerin periaate). Informaation käsittely ja tallentaminen aiheuttavat aina vähintään teoreettisen minimimäärän entropian kasvua.

 

Joten vaikka teoreettisesti voisimme tietää "kaiken", termodynaamisessa mielessä entropia ei suinkaan häviäisi kaikkeudesta.