Czy potrafisz wyjaśnić wartość szacunkową entropii używaną losowo?

/dev/randomużywa taktowania przerwań jądra, aby dodać do puli entropii. Ilość entropii w puli jest śledzona w zmiennej o nazwie entropy_count.

Oto odpowiedni fragment kodu z random.c. Reprezentuje czas (jak sądzę w jiffies) między dwoma ostatnimi interuptami w zmiennej deltai różnicami w deltach jako delta2.

delta = time - state->last_time;
state->last_time = time;

delta2 = delta - state->last_delta;
state->last_delta = delta;

if (delta < 0) delta = -delta;
if (delta2 < 0) delta2 = -delta2;
delta = MIN(delta, delta2) >> 1;
for (nbits = 0; delta; nbits++)
  delta >>= 1;

r->entropy_count += nbits;

/* Prevent overflow */
if (r->entropy_count > POOLBITS)
  r->entropy_count = POOLBITS;

Wygląda na to, że oszacowanie dodanej entropii to w zasadzie podłoga (nie sufit z powodu początkowej przesunięcia bitów przed pętlą) logarytmu podstawy 2 delty. Ma to pewien intuicyjny sens, choć nie jestem pewien, jakie założenia byłyby potrzebne, aby formalnie było to poprawne.

Moje pierwsze pytanie brzmi: „jakie jest uzasadnienie tego oszacowania?”

Moje drugie pytanie dotyczy delta = MIN(delta, delta2) .... Co to robi? Po co brać minimum tej delty i ostatniej? Nie wiem, co to ma osiągnąć - być może dzięki temu oszacowanie jest lepsze, a może bardziej konserwatywne.

Edycja: Znalazłem artykuł, który określa oszacowanie , ale tak naprawdę nie podaje uzasadnionego argumentu (chociaż zawiera pewne nieformalne warunki, które estymator powinien spełnić).

Inne zasoby, które pojawiły się w komentarzach:

• Wikipedia na /dev/randomi/dev/urandom
• Artykuł, który próbuje to wyjaśnić (jestem sceptyczny, zobacz komentarze)
• Wpis na blogu/dev/random zawierający komentarze faceta, który napisał powyższy kod.
• Odpowiedź secutity.SE na temat /dev/randompuli entropii.

delta2nie jest poprzednią delta, ale różnicą między dwiema kolejnymi wartościami delta. Jest to rodzaj pochodnej: jeśli deltamierzy prędkość, delta2jest przyspieszeniem.

Intuicyjna idea tego oszacowania polega na tym, że przerwania występują w mniej lub bardziej losowych odstępach czasu, podyktowane nieprzewidywalnymi zdarzeniami ze świata fizycznego (np. Naciśnięcia klawiszy lub przybycie pakietów sieciowych). Im dłuższe opóźnienie, tym bardziej nieprzewidywalne zdarzenia. Istnieją jednak systemy fizyczne, które przerywają ogień z ustaloną szybkością; delta2środkiem jest mechanizm ochronny, który wykrywa takich zdarzeń (jeśli występują przerwania w stałych odstępach czasu, a więc zdecydowanie przewidywalne, wszystko deltabędzie miało taką samą wartość, stąd delta2będzie zero).

Powiedziałem „intuicyjnie” i nie ma nic więcej do powiedzenia. W rzeczywistości w modelu „losowych zdarzeń fizycznych” liczenie bitów jest nieprawidłowe; jeśli zdarzenie sprzętowe wystąpi z prawdopodobieństwem p dla każdej jednostki czasu, a otrzymasz opóźnienie wyrażone przez n bitów, wówczas wkład entropii powinien być rozliczony jako n / 2 bity, a nie n bitów. Ale wiemy, że w rzeczywistości zdarzenia fizyczne nie występują dokładnie w przypadkowych momentach; delta2mechanizm przyznaje tyle.

W praktyce więc „oszacowanie entropii” jest dokładnie tym: oszacowaniem . Jego wartość bezpieczeństwa nie pochodzi z dobrze uzasadnionego, matematycznie dokładnego uzasadnienia, ale ze zwykłego źródła bezpieczeństwa: wydaje się, że nikt nie znalazł sposobu na nadużycie (jeszcze).

Ta strona została napisana przez kogoś, kto ma już dość mitów /dev/randomi estymatora entropii, i myślę, że dobrze to wyjaśnia, z wystarczającą ilością szczegółów. Ważne jest, aby uzyskać kilka podstawowych pomysłów w kontaktach z RNG.