Jak inicjalizować generator pseudolosowy losową wartością? Jedną z
możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
określić - ile?). W Linuksie zdaje się, jest 512 bitowy pojemnik losowy
utrzymywany przez system. Jak to zrobić w Windows? Problemem jest że
bardzo powoli przybywa bitów. Zaledwie kilka na przerwanie, 160-bitowa
liczba będzie wymagała wielu przerwań, a co jeśli chcemy wygenerować
wiele takich liczb?

do góry

W dniu 23.06.2011 01:04, Tubylerczyk pisze:
> Jak inicjalizować generator pseudolosowy losową wartością?
Byłoby łatwiej jakbyś określił do czego Ci to potrzebne.

> Jedną z
> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
> określić - ile?).
Liczysz md5 z tej wartości i się nie przejmujesz tym ile.

> 160-bitowa
> liczba będzie wymagała wielu przerwań, a co jeśli chcemy wygenerować
> wiele takich liczb?
Od tego jest generator PSEUDOlosowy - on ma już pamięć i generuje
kolejne wartości w oparciu o poprzednie - seed ustawia się raz.

--
Pozdrawiam
Michoo

do góry

W dniu 2011-06-23 01:46, Michoo pisze:
> W dniu 23.06.2011 01:04, Tubylerczyk pisze:
>> Jak inicjalizować generator pseudolosowy losową wartością?
> Byłoby łatwiej jakbyś określił do czego Ci to potrzebne.

(W jakiś sposób guid w systemie liczony jest tak, że mamy 128-bitową
wartość losową, nie wiem na ile jest losowy)
Na przykład: generuję losowe hasło dla użytkownika.

>
>> Jedną z
>> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
>> określić - ile?).
> Liczysz md5 z tej wartości i się nie przejmujesz tym ile.

Ale losowa pozostaje tylko część tej liczby. Mówiąc obrazowo: mam 128
bitową liczbę, ale tylko mały podzbiór jej wartości jest osiągalny.
w skrajnym wypadku byłby jeden bit, policzenie md5 dałoby dwie duże
liczby z których albo jedna albo druga by występowała.

> Od tego jest generator PSEUDOlosowy - on ma już pamięć i generuje
> kolejne wartości w oparciu o poprzednie - seed ustawia się raz.

Przydałby się prawdziwie losowy generator wbudowany w procesor oparty o
kwanty. Pojedyncza instrukcja dawałaby 64 bity szumu. Są jakieś
zewnętrzne generatory które dołącza się przez USB ale nie są standardem,
jest tez strona Random.org.

do góry

On Jun 23, 7:04 am, Tubylerczyk <t...@d...pl> wrote:

> Przydałby się prawdziwie losowy generator wbudowany w procesor oparty o
> kwanty. Pojedyncza instrukcja dawałaby 64 bity szumu. Są jakieś
> zewnętrzne generatory które dołącza się przez USB ale nie są standardem,
> jest tez strona Random.org.
No ale do czego to potrzebujesz? Naprawde bardzo duzo mozna osiagnac
bez kwantowego generatora liczb losowych. Ba, bardzo duzo mozna
osiagnac na prostej funkcji rand C++ ktora (bez losowej inicjacji) za
kazdym
razem daje identyczny ciag liczb losowych. Wszystko zalezy od tego do
czego
to potrzebujesz.
Pozdrawiam

do góry

W dniu 23.06.2011 07:04, Tubylerczyk pisze:
> W dniu 2011-06-23 01:46, Michoo pisze:
>> W dniu 23.06.2011 01:04, Tubylerczyk pisze:
>>> Jak inicjalizować generator pseudolosowy losową wartością?
>> Byłoby łatwiej jakbyś określił do czego Ci to potrzebne.
>
> (W jakiś sposób guid w systemie liczony jest tak, że mamy 128-bitową
> wartość losową, nie wiem na ile jest losowy)
On ma być unikalny a nie losowy. Oidp jakaś implementacja używała
fragmentu MAC i czasu jako części składowych.

> Na przykład: generuję losowe hasło dla użytkownika.
Oidp sam wynik MD5 jest dość dobrym ciągiem losowym.

Jeżeli dokładny czas jest nieznany "na zewnątrz". (Np użycie licznika
cykli z performance counters) to dla potrzeb wygenerowania hasła
wystarczy (każda sekunda to 10^9 możliwości).

Zapewnia to po pierwsze losowy rozkład wyjścia a po drugie praktyczną
niemożliwość prognozowania hasła na podstawie nawet wielu znanych. A to
chyba główne 2 zadania do których losowość jest tu potrzebna.

>
>>
>>> Jedną z
>>> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
>>> określić - ile?).
>> Liczysz md5 z tej wartości i się nie przejmujesz tym ile.
>
> Ale losowa pozostaje tylko część tej liczby. Mówiąc obrazowo: mam 128
> bitową liczbę, ale tylko mały podzbiór jej wartości jest osiągalny.
> w skrajnym wypadku byłby jeden bit, policzenie md5 dałoby dwie duże
> liczby z których albo jedna albo druga by występowała.
Tylko czas ma taką niewiarygodną własność, że jest monotoniczny a nie 2
wartościowy.

MD5 (czy SHA - do wyboru) daje wyjście spełniające dość dobrze kryteria
ciągu losowego.

W efekcie mamy funkcję przyporządkowującą dla danego T n-bitową wartość
losową[*]. To, że ciąg z którego bierzemy T nie jest losowy nie ma
praktycznego znaczenia, bo używana funkcja nie posiada funkcji odwrotnej.

[*] ściśle mówiąc pseudolosową - przeciwdziedzina funkcji skrótu jest
zawsze ograniczona, czas również (do słowa 64/128b), ale są to wartości
dostatecznie duże

>
>> Od tego jest generator PSEUDOlosowy - on ma już pamięć i generuje
>> kolejne wartości w oparciu o poprzednie - seed ustawia się raz.
>
> Przydałby się prawdziwie losowy generator wbudowany w procesor oparty o
> kwanty.
Są generatory oparte o szumy termiczne. Stosuje się je tam gdzie to jest
konieczne. W komputerach domowych raczej nie jest. No i łatwiej się
poprawia ewentualne błędy w programach niż w krzemie.

--
Pozdrawiam
Michoo

do góry

W dniu 2011-06-23 01:04, Tubylerczyk pisze:
> Jak inicjalizować generator pseudolosowy losową wartością? Jedną z
> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
> określić - ile?). W Linuksie zdaje się, jest 512 bitowy pojemnik losowy

Wszystkie. Przecież nie korzystasz z wartości [czas], tylko
(w uproszczeniu) z r_1 = F(czas) [a dalej r_n = F (r_{n-1})]
Jeśli czasy różnią się choć jednym bitem, to pierwsza liczba
pseudolosowa r_1 bdyie w obu przypadkach zupełnie różna.

Pamiętaj, że w programie raz się inicjalizuje tą zmienną,
najczęściej nie trzeba więc wysokiej rozdzielczośći czau,
chyba , że programy są często odpalane i krótkie
(to czemu tego nie wrzucić w jeden program w pętle;)

BTW, ostatnio ktoś tu, albo na p.c.l.c pisał o tym, że
korzysta z zegara i numeru wątku/procesu, aby wielowątkowo
puszczony program nie szedł tą samą ścieżką.

> utrzymywany przez system. Jak to zrobić w Windows? Problemem jest że
> bardzo powoli przybywa bitów. Zaledwie kilka na przerwanie, 160-bitowa
> liczba będzie wymagała wielu przerwań, a co jeśli chcemy wygenerować
> wiele takich liczb?

Użyj tych prawdziwych liczb losowych do inicjalizowania
generatora pseudolosowych. Jeśli nie szyfrujesz kanału
Klewki-Baza CIA będzie dobrze. A inicjalozowanie jest
bardzo rzadkie (raz na program).

pozdrawiam
bartekltg

do góry

W dniu 2011-06-23 15:20, bartekltg pisze:
> W dniu 2011-06-23 01:04, Tubylerczyk pisze:
>> Jak inicjalizować generator pseudolosowy losową wartością? Jedną z
>> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
>> określić - ile?). W Linuksie zdaje się, jest 512 bitowy pojemnik losowy
>
> Wszystkie. Przecież nie korzystasz z wartości [czas], tylko
> (w uproszczeniu) z r_1 = F(czas) [a dalej r_n = F (r_{n-1})]
> Jeśli czasy różnią się choć jednym bitem, to pierwsza liczba
> pseudolosowa r_1 bdyie w obu przypadkach zupełnie różna.

Owszem, jeśli chodzi o inicjalizację zmiennej a potem używa wartości
pseudolosowych. Wtedy wystarczy jeden bit różnicy, podczas gdy skrót MD5
czy SHA będą różniły się całkowicie.
Ale weźmy czas w formacie Unixa zmieniający się co sekundę. Można
powiedzieć że źle będzie tylko wówczas gdy wykonamy program dwa razy w
ciągu tej samej sekundy, a gdy o jedną sekundę później to już dobrze.
Jednak co co się stanie, gdy ktoś zna funkcję haszującą i wartość
pierwszej chwili czasowej? Będziemy mieli 32 bity czasu, >130 lat ale
tylko najmłodsze bity będą się różniły. Nawet te najmłodsze nie będą
losowe, bo wiadomo że przy drugim odpaleniu będą miały wartość większą a
nie mniejszą.
Losowość rozumiem w ten sposób, że wciskam klawisz i za sekundę wciskam,
sterownik oblicza między nimi ilość taktów procesora, to czy ta ilość
jest parzysta czy nie jest czysto losową zmienną, również starsze bity,
tak aż do pół sekundy, ten półsekundowy bit nie będzie tak już w pełni
losowy, a starsze będą zerowe więc wcale nie losowe.

do góry

On Jun 23, 5:02 pm, Tubylerczyk <t...@d...pl> wrote:
> Ale weźmy czas w formacie Unixa zmieniający się co sekundę. Można
> powiedzieć że źle będzie tylko wówczas gdy wykonamy program dwa razy w
> ciągu tej samej sekundy, a gdy o jedną sekundę później to już dobrze.
> Jednak co co się stanie, gdy ktoś zna funkcję haszującą i wartość

srand( wszystko_co_ci_przyjdzie_do_glowy );
time_t s = time(NULL) + 2;
while( s > time(NULL) )
rand();
return rand();

Mocno obciaza procesor, ale teraz by musial znac duzo dokladniej
czas uruchomienia (no i to co przyszlo Ci do glowy )
Pozdrawiam

do góry

On 23.06.2011 17:02, Tubylerczyk wrote:
> W dniu 2011-06-23 15:20, bartekltg pisze:
>> W dniu 2011-06-23 01:04, Tubylerczyk pisze:
>>> Jak inicjalizować generator pseudolosowy losową wartością? Jedną z
>>> możliwości jest odczyt zegara, ale tylko najmłodsze bity są losowe (jak
>>> określić - ile?). W Linuksie zdaje się, jest 512 bitowy pojemnik losowy
>>
>> Wszystkie. Przecież nie korzystasz z wartości [czas], tylko
>> (w uproszczeniu) z r_1 = F(czas) [a dalej r_n = F (r_{n-1})]
>> Jeśli czasy różnią się choć jednym bitem, to pierwsza liczba
>> pseudolosowa r_1 bdyie w obu przypadkach zupełnie różna.
>
> Owszem, jeśli chodzi o inicjalizację zmiennej a potem używa wartości
> pseudolosowych. Wtedy wystarczy jeden bit różnicy, podczas gdy skrót MD5
> czy SHA będą różniły się całkowicie.
> Ale weźmy czas w formacie Unixa zmieniający się co sekundę. Można
> powiedzieć że źle będzie tylko wówczas gdy wykonamy program dwa razy w
> ciągu tej samej sekundy, a gdy o jedną sekundę później to już dobrze.
> Jednak co co się stanie, gdy ktoś zna funkcję haszującą i wartość
> pierwszej chwili czasowej? Będziemy mieli 32 bity czasu, >130 lat ale
> tylko najmłodsze bity będą się różniły. Nawet te najmłodsze nie będą
> losowe, bo wiadomo że przy drugim odpaleniu będą miały wartość większą a
> nie mniejszą.
> Losowość rozumiem w ten sposób, że wciskam klawisz i za sekundę wciskam,
> sterownik oblicza między nimi ilość taktów procesora, to czy ta ilość
> jest parzysta czy nie jest czysto losową zmienną, również starsze bity,
> tak aż do pół sekundy, ten półsekundowy bit nie będzie tak już w pełni
> losowy, a starsze będą zerowe więc wcale nie losowe.

Weź kartę radiową, nastaw na nieużywany kanał, nie na stację. Masz
losowy szum na wejściu.

Możesz skorzystać też np z licznika bajtów na interfejsie sieciowym,
stanów rejestrów, pobrać jakiś stan z dysku, można próbować pogadać z
kartą graficzną. Możliwości jest naprawdę dużo.

--
wer <",,)~~
http://szumofob.eu

do góry

W dniu 2011-06-24 09:09, Mariusz Marszałkowski pisze:
> srand( wszystko_co_ci_przyjdzie_do_glowy );
> time_t s = time(NULL) + 2;
> while( s> time(NULL) )
> rand();
> return rand();

Ja to rozwiązałem w ten sposób:
Podczepić hooka pod zdarzenia przycisku klawiatury. W przypadku
uderzenia klawisza odczytujemy czas - ilość taktów zegara CPU za pomocą
rdtsc. Wyliczamy odstępy między kolejnymi uderzeniami - liczba dodatnia
(aby nie było problemów, program musi działać tylko na jednym rdzeniu
SetProcessAffinityMask(GetCurrentProcess(), 1) bo inaczej raz odczyta z
jednego licznika a raz z drugiego).
Sam odstęp jeszcze nie mówi ile bitów losowych da się z niego uzyskać,
autorepeat klawisza daje niemal identyczne czasy i mało w nim bitów
losowych. Potrzebna jest różnica, o ile zmienił się odstęp - im większa,
tym więcej bitów losowych. Wyliczyć ile bitów - z wartości bezwzględnej
policzyć indeks najstarszego zapalonego bitu + 1.
Bitami losowymi będą najmłodsze bity ostatniego czasu. Nie da się
wykorzystać znaku różnicy odstępów ponieważ ma rozkład nie losowy.
Typowe bębnienie po klawiaturze dawało strumień rzędu 800 bitów/s.

do góry