Una semplice domanda sull'entropia e sui dati casuali

0

Diciamo che rotolo un dado a 6 facce 100 volte e registra i risultati in una stringa di 100 caratteri, ad esempio:

//this is obviously an example (and very unlikely) outcome
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"

Sono abbastanza sicuro che questa stringa da 100 byte abbia più di 256 bit di entropia, rendendo quasi impossibile per chiunque trovare la stessa stringa. (Arrivo a quel numero di entropia perché 6 ^ 99 < 2 ^ 256 < 6 ^ 100.)

È corretto?

Se è così, ho ulteriori domande:

Da ciò segue che se ripeto la sequenza che ho generato sopra 10 volte,

"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"
"1234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234561234"

che ora ho generato 1000 byte di dati casuali con entropia a 256 bit?

Andiamo oltre. Posso prendere la mia stringa iniziale e ripeterla 10.000.000.000 di volte e dire che ho generato 1 terabyte di dati casuali con entropia a 256 bit?

In sostanza mi sto chiedendo se perderò qualsiasi entropia ripetendo gli stessi dati "seme" iniziali.

    
posta cryptonamus 09.08.2015 - 19:34
fonte

1 risposta

1

Sicuramente non impossibile, e non perderete entropia ripetendo i dati seme, ma non ne otterrete neanche uno.

Per "loro", mi riferisco solo a una persona fittizia che sta cercando di capire come viene generata l'entropia.

Se sanno che stai tirando un dado, sanno che ogni cifra sarà 1-6. Se sanno quante volte tiri i dadi, conoscono la lunghezza della corda. Se sanno che il numero viene ripetuto altre 9 volte, hanno bisogno solo di 100/1000 cifre per calcolare l'intera stringa.

Un hacker potrebbe aver già dedotto un numero di possibilità avendo questa conoscenza.

Tecnicamente, non è nemmeno completamente casuale.

Codice di esempio Python:

# Generating dice rolls

import random

finalResult = ''

for i in range(0, 99):
    finalResult += str(random.randint(1, 6))

finalResult = finalResult * 10

print finalResult

La nostra stringa di risultati è

"445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263445656152532321321544533156515514562441512263431326526522641111345452422363416326462451246641163263"

La stringa produce 2.5806473 bit entropici.

Se dovessimo ripetere questa stringa 100 volte, i bit di entropia producono 2.5806473, quindi non otterrete più entropia ripetendo la stessa stringa. Ha esattamente la stessa quantità di bit entropici.

Potresti utilizzare un metodo molto migliore per calcolare quei tipi di stringhe.

Ad esempio, usiamo il seguente set di caratteri:

  • (abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789 ~ '@ # $% ^ & * () -_ = + [{]} \ |;:!'.?, < > / ")

Potremmo far corrispondere ciascun carattere a un numero casuale (0-9).

Genereremo una stringa casuale di 100 caratteri per 10 volte, ogni risultato sarà aggiunto alla fine dell'altro.

Codice di esempio Python:

import random

finalResult = ''

for i in range(0, 9):
    charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789~'!@#$%^&*()-_=+[{]}\|;:',<.>?/"

    charDict = {}

    for char in charSet:
        charDict[char] = random.randint(0, 9)

    resultNum = ''

    for c in range(0, 99):
        resultNum += str(charDict[random.choice(charSet)])

    finalResult += resultNum

print finalResult

Il nostro risultato finale è

"989399239097499389189022059092089492027501842251063182295989039209500981690709174339560500718099187606453339255549850346696565025042504925549332139224650652008702541994436538038618150315533023690953265748197684554400738548471882056153703865878585568168785067956510245109630478032252017568653870833894188388554461614037175856595140494136416835954432291428646093513565418053453659690464509631548126684471012603870043241726762620992001266264567652958725540078190802887737716846137398760778230100671898578274611212550507493363271408738936020202251709524912326332192065460961427192491397953337291818408796519672933031867956012894824302218099239929701290857804033886980677310953734098050027009200344729070097168472819000050821260058120486772283080610287066869211061373297557455864016702744529267151023698266001761202821747262141933039130063624472814012939225414242779000144228077687272549297604021".

La stringa produce 3.3067561 bit entropici.

Anche se dovessi ripetere 100 volte questa stringa, i bit di entropia sarebbero comunque 3.3067561.

Per generare 1 TB di entropia casuale, questo porterebbe a termine il lavoro, tuttavia non suggerisco di eseguire il codice, poiché potrebbe causare il crash del tuo computer.

import random

finalResult = ''

for i in range(0, 999999999999):
    charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789~'!@#$%^&*()-_=+[{]}\|;:',<.>?/"

    charDict = {}

    for char in charSet:
        charDict[char] = random.randint(0, 9)

    resultNum = ''

    for c in range(0, 99):
        resultNum += str(charDict[random.choice(charSet)])

    finalResult += resultNum

print finalResult
    
risposta data 09.08.2015 - 20:23
fonte

Leggi altre domande sui tag