Elektroda.pl
Elektroda.pl
X
SterControl
Proszę, dodaj wyjątek www.elektroda.pl do Adblock.
Dzięki temu, że oglądasz reklamy, wspierasz portal i użytkowników.

Generator liczb losowych oparty o pamięć RAM

ghost666 30 Cze 2015 14:27 9423 31
  • Generator liczb losowych oparty o pamięć RAMJak wygenerować losowy ciąg bitów? Niektórzy ludzie powiedzą, że to niełatwe, inni, że to bardzo trudne, a jeszcze inni zastanawiać się będą, czy to w ogóle możliwe. Oczywiście, nie problemem jest tworzenie ciągów pseudolosowych bitów korzystając z oprogramowania, ale niestety nawet najlepszy programowy generator liczb pseudolosowych potrzebuje dobrego losowego ziarna do inicjalizacji generatora, nie chcemy w końcu, aby przy każdym uruchomieniu generator dawał taką samą sekwencję bitów, nie? Dlatego też konieczne są implementacje rzeczywistych generatorów liczb losowych, które wymagają dedykowanych układów i implementacji sprzętowej.

    Niektóre wysokiej klasy mikroprocesory wbudowane mają rzeczywiste generatory liczb losowych, jednakże większość niedrogich mikrokontrolerów pozbawiona jest takich modułów. Inżynierowie mają w rękawie kilka asów - sztuczek - pozwalających na quasi-losową inicjalizację programowego generatora. Zazwyczaj jest on inicjalizowany ziarnem generowanym przez licznik, zatrzymany zdarzeniem zewnętrznym (np. naciśnięciem przycisku). Oczywiście takie coś funkcjonuje całkiem nieźle, ale nie jest pozbawione wad. Po pierwsze, istnieje szansa, że licznik zsynchronizuje się z częstotliwością pracy skanera portów wejściowych układu. Po drugie, czas pomiędzy uruchomieniem licznika a naciśnięciem przycisku jest zazwyczaj krótki, co powoduje, że ziarno jest bliskie początkowej wartości licznika, a przez to dosyć przewidywalne. Po trzecie, w niektórych aplikacjach nie da się zaimplementować wejścia zewnętrznego, więc trzeba znaleźć inny sposób inicjalizacji generatora.

    Niezależnie od tego, co się mówi, większość mikrokontrolerów ma wbudowane źródło całkiem niezłych liczb losowych. Jakkolwiek nie jest on doskonały i może nie nadawać się do aplikacji typowo kryptograficznych, to generuje on dostatecznie dużo entropii, aby nadawać się do wykorzystania w grach, symulacjach, gadżetach itp.

    Niezainicjalizowana pamięć RAM

    Hakerzy i zaawansowani inżynierzy często wykorzystują hardware w sposób nieprzewidziany przez producenta, w tym przypadku ulotną pamięć RAM, nie jako pamięć, a jako źródło entropii. Gdy do mikrokontrolera dołączy się zasilanie, wewnętrzna pamięć RAM (ulotna) ma nieznaną i losową zawartość. Każdy przerzutnik w jej strukturze będzie wstępnie ustawiony jako 0 lub 1 - jest to konsekwencja odchyłek od idealnej struktury układu, zapadów pamięci zasilania oraz termalnego (i kwantowego) szumu. Z tego względu zawartość pamięci RAM jest inna przy każdym uruchomieniu układu.

    Generator liczb losowych oparty o pamięć RAM


    Kilka lat temu firma Intel opracowała nowatorski sposób generacji losowych bitów, oparty o specjalnie skonstruowany przerzutnik. Został on ustawiony w stanie metastabilny, a następnie zwolniony do stabilnego 0 lub 1. Całość powtarza się z częstotliwością 3 MHz. Firma Intel planuje zaimplementować taki układ w nowej generacji swoich procesorów.

    Póki co w mikrokontrolerach nie ma takich przerzutników, ale generalnie to jest ich sporo, a część z nich da się stroić. To, ile przerzutników ulotnej pamięci RAM potrzebne jest do stworzenia generatora liczb losowych, zależne jest od parametrów samej pamięci, więc aby dobrać ich ilość trzeba przeprowadzić szereg eksperymentów. Pozwoli to sprawdzić, ile bitów pamięci RAM zachowuje się nieprzewidzianie po załączeniu układu. Niestabilność, o którą nam chodzi, objawia się w wysoce symetrycznych przerzutnikach z dobrze zbalansowanymi tranzystorami. Potrzebujemy tych nieprzewidywalnych bitów do zbierania entropii, więc zebrać trzeba możliwie dużo danych, najlepiej sczytać całą pamięć RAM przed jej inicjalizacją.

    Eksperymenty

    Przyjrzyjmy się zawartości pamięci RAM typowego mikrokontrolera przed inicjalizacją. Poniższy obrazek zawiera początkowy stan 2048 bitów pamięci układu PIC18F2525. W każdym rzędzie jest 256 bitów (32 bajty). Jedynki są czerwone, a zera żółte.

    Generator liczb losowych oparty o pamięć RAM


    Oczywiście jest o wiele mniej jedynek niż zer w pamięci, ale to nie ma znaczenia. Co innego jest interesujące. Czy jeżeli wzięlibyśmy inny układ, nawet z tej samej rodziny lub tej samej linii produkcyjnej, to ile bitów różniłoby się, względem zaprezentowanego obrazka?

    Najpewniej łatwo się tego domyślić - każdy układ ma charakterystyczny dla siebie rozkład. Drugim, istotniejszym pytaniem jest to, ile bitów pamięci RAM będzie generowało losowe stany po włączeniu. Poniżej zaprezentowany wyniki kolejnego, prostego eksperymentu. Uruchomiono mikrokontroler (PIC18F2525) dwukrotnie, za każdym razem odczytując niezainicjalizowaną pamięć. Kolor biały to odczytane dwa zera, kolor szary dwie jedynki. Kolorem czerwonym oznaczono odczytanie najpierw zera, potem jedynki, a niebieskim sytuację odwrotną.

    Generator liczb losowych oparty o pamięć RAM


    Po przeprowadzeniu pewnych eksperymentów widać, że na ogół te same bity pamięci RAM wykazują nieprzewidywalne zachowanie - o takie nam chodzi i one będą naszym źródłem entropii. Przetestowano mikrokontrolery z rodziny PIC18 i PIC24 (rezultaty znajdują się poniżej), ale każdy układ powinien zachowywać się w podobny sposób. Wyniki zaprezentowane tutaj uzyskano dla szybkiego narastania napięcia zasilającego, ale podobne zachowanie da się zaobserwować dla wolnego narastania napięcia zasilającego. Taka sytuacja powoduje generację pewnych wzorów w pamięci, ale przyczynia się to do zwiększenia niestabilnych bitów w pamięci.

    Oprogramowanie

    Zatem jeżeli potrzebujesz kilku losowych bitów (np. do inicjalizacji generatora programowego), pamięć RAM jest dobrym ich źródłem. Trzeba napisać procedurę, która będzie XORować (lub wykonywać ADD MOD 256) z bitami w blokach niezainicjalizowanej pamięci. Jeśli potrzebujemy np. 32-bitowego losowego ziarna, to 4K pamięci RAM PIC18F2525 dzielimy w cztery 1024-bitowe bloki i wykorzystujemy do wygenerowania czterech bajtów ziarna. Nawet jeśli część pamięci zostanie już zainicjalizowana, to nie powinno to mieć wpływu na całkowitą entropię otrzymanego ziarna.

    Ograniczeniem opisywanej metody jest sytuacja, w której pamięć podtrzymywana jest napięciem z baterii lub gdy urządzenie jest usypiane, a nie wyłączane. Tym niemniej w większości mniej czułych na słabą entropię aplikacji, wystarczy moment wymiany baterii, aby wygenerować losowe ziarno starczające na bardzo długi czas działania programowego generatora liczb losowych.

    Podczas tworzenia aplikacji wykorzystujących ten sposób generowania liczb losowych, pamiętać trzeba, że pamięć odczytywać trzeba przed jej inicjalizacją, od razu po włączeniu układu. Dodatkowo warto zwrócić uwagę, aby układ, w którym to realizujemy, nie miał zbyt wielkiej pojemności filtrującej zasilanie, gdyż CMOS RAM potrzebuje naprawdę niewiele prądu do podtrzymania zapisu. W takiej sytuacji, kiedy wyłączamy układ tylko na chwilę i następuje zasadniczo jedynie zapad napięcia z uwagi na ładunek zgromadzony w kondensatorze filtrujący mikrokontroler zresetuje się, ale pamięć RAM pozostanie w dużej mierze nietknięta.

    Istnieje kilka możliwych podejść do realizacji takiego układu, pozwalających na poprawienie jakości liczb losowych generowanych przez układ. Nie należy nigdy inicjalizować całej pamięci RAM, jedynie potrzebny jej fragment. Nie można także używać zbyt dużych pojemności filtrujących, zasilanie najlepiej odłączać zamiast usypiać układ.

    Jednostka eksperymentalna

    Pierwsze rezultaty eksperymentalne okazały się być bardzo obiecujące, więc autor zdecydował się na konstrukcję trzech prototypów generujących strumień losowych bitów.

    Generator liczb losowych oparty o pamięć RAM


    1. Dwa układy PIC18F2525s komunikującej się poprzez 8-bitową szynę równoległą. Podległy mikrokonstroler generuje 16 losowych bitów, każdy z nich oparty o 248 bitów pamięci RAM. Master (po środku na schemacie) odbiera te bity i wysyła do komputera PC poprzez interfejs RS232. Po odebraniu 16 bitów, układ sterujący odłącza podległe mu mikrokontrolery na 200 ms, co powinno zresetować układ i zapełnić RAM losową zawartością. Dalej całość się powtarza - realizowane jest 625 tysięcy cykli, aby zebrać 10 MB danych, potrzebnych do testów losowości. Całość trwa około 50h.

    2. W tym prototypie master jest ten sam, ale podległe ma dwa układy 24EP512GP202. W tym przypadku strumień ma 192 bity w pakiecie, więc 10 Mb danych generuje się przez 5,5 h.

    3. W ostatnim przykładzie wykorzystany jest tylko mikrokontroler 24EP256GP710A z 4 megabitami zewnętrznej pamięci SRAM CY62177EV30. Pamięć SRAM jest odłączana od zasilania i odczytywana w podobny sposób jak wewnętrzna pamięć układów w poprzednich przypadkach. Jedyną zaletą tego podejścia jest duża pojemność pamięci RAM, co oznacza, że generacja generacja 10 Mb danych jest szybka - zajmuje jednie 19 minut.

    Generator liczb losowych oparty o pamięć RAM


    Test losowości

    Dwa zestawy testów zrealizowane zostały dla prezentowanych prototypów - Diehard i ENT. Pierwszy prototyp przeszedł wszystkie testy, a dwa pozostałe oblały część testów ENT - najczulsze z testów losowości. Wyniki testów losowości zawarte są w poniższej tabeli:







    Żródło entropii 1. (8 bitowy mikrokontroler)2. (16 bitowy mikrokontroler z programowym generatorem liczb losowych)3. (zewnętrzna pamięć RAM z programowym generatorem liczb losowych)
    Entropia (bits/byte)7.9999827.9999827.999982
    Kompresja zredukowała wymiar o 0%0%0%
    Wartość chi² dla rozkładu losowego przekroczona przy:47.47%34.29%42.24%
    Średnia arytmetyczna (127.5 = wartość w pełni losowa)127.4936127.5478127.4937
    Błąd wartości liczby π wyznaczonej metodą Monte Carlo0.030.050.00
    Szeregowy współczynnik korelacji (0.0 = wartości nieskorelowane)0.0002060.0004340.000104


    Testy typu Diehard wymagają o wiele obszerniejszego opisu. Ich wynik umieszczono na stronie www.voja.rs/rndtests.htm wraz z plikami binarnymi wygenerowanymi w eksperymencie.

    Podsumowanie

    Podsumowując, po drobnych modyfikacjach, wszystkie przedstawione prototypy przechodzą poprawnie testy losowości, którym czasami nie mogą sprostać nawet komercyjne (i drogie!) rzeczywiste generatory liczb losowych. Te układy DIY można złożyć za mniej niż 10 dolarów.

    Pamiętać trzeba oczywiście, że działanie powyższych urządzeń oparte jest o nieudokumentowane działanie mikrokontrolerów. W ten sposób także nie da się osiągnąć poziomu losowości i bezpieczeństwa potrzebnego w poważnych aplikacjach kryptograficznych, jednakże niezainicjalizowany RAM jest doskonałym źródłem losowych liczb do mniej wymagających aplikacji, a przede wszystkim - przedstawiona metoda jest prosta, jej implementacja jest darmowa i zasadniczo nie powoduje zwiększenia powierzchni PCB ani poboru dodatkowego prądu przez układ.

    Źródło:

    http://hackaday.com/2015/06/29/true-random-number-generator-for-a-true-hacker/


    Fajne!
  • SterControl
  • #2 30 Cze 2015 22:27
    Petros
    Poziom 20  

    Ciekawy artykuł.
    Metoda ta nie znajdzie zastosowania w aplikacjach z większymi kondensatorami.
    Nikt nie będzie dobierał elektrolitów do generatora liczb losowych...

    Innym o wiele prostszym sposobem jest wykorzystanie RTC - licznik milisekund inkrementowany nawet jeśli układ jest wyłączony.
    Jeśli mikrokontroler nie posiada RTC może być to zwykły timer z zapisem wartości do eepromu
    Trzeba tylko pamiętać aby wartość timera pomnożyć przez wartość innego niezsynchronizowanego timera lub zmienną

  • SterControl
  • #3 30 Cze 2015 22:42
    ghost666
    Tłumacz Redaktor

    Oczywiście że nie będzie, jednakże jeśli liczby losowe są istotne dla jakiejś aplikacji, to można o tym pomyśleć. Może w ogóle jakieś dedykowane np. ATTiny stosować?

    Innym ciekawym pomysłem, jest wykorzystanie szumów cieplnych tranzystora.

  • #4 01 Lip 2015 10:06
    Urgon
    Poziom 36  

    AVE...

    W okolicach 1998-1999 roku opracowano generator liczb losowych, który używał kilka sztuk lampy LavaLamp Lite i kamerki internetowej z celowo rozregulowaną optyką. Uzyskany obraz był jeszcze potem dodatkowo przetwarzany by zwiększyć chaos.

    Można wziąć matrycę CCD, zamknąć ją w izolowanym pudełku i rejestrować szum. Dodanie niewielkiego źródła promieniowania, na przykład izotopu ameryku z detektora dymu zwiększy jeszcze ilość szumu i losowość.

  • #6 01 Lip 2015 10:26
    freebsd
    Poziom 34  

    Te rozwiązanie jest znane i stosowane od lat. Odkryli koło ponownie. Do tego jako prawdziwy generator liczb losowych działa to strasznie powoli.

  • #7 01 Lip 2015 23:35
    maciej_333
    Poziom 34  

    Freddy napisał:
    Mam pewne wątpliwości, czy jest to naprawdę generator liczb losowych, a nie pseudolosowych.

    Niewątpliwie jest to generator liczb losowych. Generator liczb pseudolosowych to właściwie rejestr z pewnymi sprzężeniami zależnymi od stosowanego wielomianu. Taki generator jest całkowicie deterministyczny, jeżeli znamy ten wielomian i początkową wartość rejestru. Zatem taki szum będzie miał maksima co jakiś czas w funkcji autokorelacji. Jest to spowodowane "powtarzalnością" co pewien okres. Ma to zastosowanie np. w różnych technikach rozpraszania widma. Tam jednak trzeba synchronizować dwa takie generatory (nadajnik i odbiornik).

    Tak, jak napisał kolega ghost666 można próbować zastosować element półprzewodnikowy. Może to być np. dioda. Wiele mikrokontrolerów ma przetworniki A/C z wejściami różnicowymi i PGA. Proponowałbym podać np. na wejście nieodwracające spadek napięcia z diody spolaryzowanej w kierunku przewodzenia. Na wejście odwracające ten sam sygnał podany jednak przez prosty filtr dolnoprzepustowy RC. Usuniemy w ten sposób składową stałą i zapewnimy jej kompensację termiczną. PGA wzmocni szumy diody. Jednak poziom szumu będzie zależny od temperatury.

  • #8 02 Lip 2015 00:52
    freebsd
    Poziom 34  

    Ja też mam wątpliwości takie jak @Freddy Wynik testów mierzących jakość generatorów uważanych za generatory bitów losowych są probabilistyczne. By określić, czy RAM w tych testowanych układach nadaje się do tego w poważnych zastosowaniach brakuje mi jeszcze kilku testów. Testowanie hipotez, częstości, podwójnych bitów, serii, korelacji, postulaty Golomba. Pozytywnie wyszedł test Maurera - co uważam za duży plus, ale czy próbka była wystarczająco duża? Do tego testy przy różnych poziomach zasilania, temperaturach - każdy generator do poważniejszych zastosowań musi być okresowo kontrolowany, czyli dochodzą jeszcze testy w czasie. Nawet po ich pozytywnym przejściu można tylko określić, że dany generator wytwarza ciągi mające własności ciągów losowych - pozytywne wyniki dają dowód probabilistyczny, nie deterministyczny.

    Jak już odbiegamy od tematu to istnieje wiele metod generowania ciągów pseudolosowych. Liniowe generatory kongruencyjne o maksymalnym okresie i spełniające testy Knutha dla wymiarów 2,3,4,5 i 6 od dawna są skompromitowane (Reeds, Boyar). Z kolei rejestry przesuwające z liniowym sprzężeniem zwrotnym, często stosowane i dobrze udokumentowane, mają kolejne bity ciągu powiązane liniowo... (co wykorzystał Berlekamp i Massey). Do tego programowa realizacja LSFR jest mało wydajna (dla gęstych wielomianów). Mimo wad często w komercyjnych rozwiązaniach stosuje sie tą metodę.

  • #9 02 Lip 2015 06:17
    dondu
    Moderator Mikrokontrolery Projektowanie

    Petros napisał:
    Innym o wiele prostszym sposobem jest wykorzystanie RTC - licznik milisekund inkrementowany nawet jeśli układ jest wyłączony.
    Jeśli mikrokontroler nie posiada RTC może być to zwykły timer z zapisem wartości do eepromu
    Trzeba tylko pamiętać aby wartość timera pomnożyć przez wartość innego niezsynchronizowanego timera lub zmienną


    ghost666 napisał:
    Oczywiście że nie będzie, jednakże jeśli liczby losowe są istotne dla jakiejś aplikacji, to można o tym pomyśleć. Może w ogóle jakieś dedykowane np. ATTiny stosować?

    Innym ciekawym pomysłem, jest wykorzystanie szumów cieplnych tranzystora.


    Można tak:

    Generator liczb losowych oparty o pamięć RAM

    http://mikrokontrolery.blogspot.com/2011/03/epp-generator-losowy-program.html

    albo za pomocą przetwornika ADC:
    http://mikrokontrolery.blogspot.com/2011/04/generator-liczb-losowych.html

  • #10 02 Lip 2015 09:48
    __Grzegorz__
    Poziom 27  

    @dondu:

    Cytat:
    Liniowe generatory kongruencyjne ... od dawna są skompromitowane


    i to do tego stopnia, że jak mi podasz kilka kolejnych wartości ze swojego generatora, jestem w stanie przewidzieć WSZYSTKIE następne wartości jakie wylosujesz :) , gdyż w banalny sposób można odtworzyć wartości zmiennych a,c i m z wzoru podanego w linku.
    np.:
    http://sandeepmore.com/blog/2012/03/23/breaking-linear-congruential-generator/

  • #11 02 Lip 2015 10:45
    andrzejlisek
    Poziom 28  

    A ja mam pomysł na generator losowy (nie pseudolosowy), prosty, tani, ale skuteczny. Jednak nie wykonałem ani jednego eksperymentu potwierdzającego lub obalającego słuszność pomysłu.

    Opiera się na założeniu, że każdy tranzystor, szczególnie te słabej jakości, generuje szum własny, co jest irytujące we wszelkich wzmacniaczach analogowych. Jednak tym razem zamiast walczyć z szumem, można go wykorzystać. Z takich tranzystorów można zbudować wzmacniacz o dużym wzmocnieniu, ale wejście zewrzeć do masy. Na wyjściu będzie wzmocniony szum własny tranzystorów, amplituda szumu kilka woltów.

    Biorąc pod uwagę, że taki szum nie będzie idealnym szumem białym, a także temperatura otoczenia może mieć wpływ na ten szum, nie można wykorzystywać napięcia chwilowego na wyjściu, jednak można wykonać kilka przekształceń po stronie programu.

    Taki szum można podać na wejście przetwornika A/C uzyskując jakąś wartość. Jeden odczyt służyłby do wygenerowania jednego bitu losowego. Wartość bitu zależy od tego, czy odczytana wartość jest wyższa, czy niższa od wartości progowej. Po uruchomieniu układu programu trzeba tylko przeprowadzić kilkadziesiąt losowań bez wykorzystania wartości. W programie byłby bufor pamiętający kilkadziesiąt ostatnich wartości z przetwornika, przy każdym losowaniu wartość progowa byłaby określana na podstawie wartości z bufora tak, żeby prawdopodobieństwo otrzymania wartości powyżej i poniżej było jednakowe, tak więc prawdopodobieństo uzyskania bitu 0 lub 1 byłoby jednakowe.

    Idę o zakład, że już przede mną były takie pomysły.

    Ciekawe, że żaden producent procesora nie wyposaży go w taki układ i nie udostępni rozkazu pobierającego wartość z przetwornika analogowo-cyfrowego, do którego jest podłączony generator szumu zbliżonego do szumu białego (nie musi to być dokładnie szum biały i niewielka zmiana właściwości pod wpływem czynników zewnętrznych byłaby dopuszczalne). Całą resztę, czyli wartość progowa, buforowanie i ostateczne wyznaczanie wylosowanej wartości można oprogramować.

    Jak widać, prosty układ, prosty pomysł i przestają być potrzebne niezwykle skomplikowanie generatory ciągów, które nie są prawdziwie losowe.

    Poprzez analogię do kostki do gry.

    Załóżmy, że kosta nie jest prawidłowo zrobiona i 16 ostatnich rzutów byłoby takich: 5 1 1 6 2 5 2 4 1 4 4 2 1 6 3 1
    Poszczególne liczby wypadły w ilościach odpowiednio 5, 3, 1, 3, 2, 2
    Na podsawie powyższego mozna wyznaczyć wartość progową na poziomie 2.5, bo było razem 8 rzutów poniżej 2.5 i 8 rzutów powyżej 2.5.
    Z tego można wywnioskować, że przy następnym rzucie, prawdopodobieństwo, że wyjdzie poniżej 2.5 jest 50%, podobnie, jak prawdopodobieństwo, że wyjdzie powyżej 2.5.

  • #12 02 Lip 2015 10:59
    Urgon
    Poziom 36  

    AVE...

    W linku o sprzętowym RNG od Dondu jest link do opisu dokładnie takiego generatora liczb losowych używającego złącze PN tranzystora. Generatory tego typu nie zawsze są losowe, bo wiele zależy od projektu płytki i zakłóceń w okolicy. Zarówno taki generator, jak i gołe ADC mogą łapać przykładowo przydźwięk sieciowy, który losowy nie jest.

  • #13 02 Lip 2015 13:11
    dondu
    Moderator Mikrokontrolery Projektowanie

    __Grzegorz__ napisał:
    @dondu:
    Cytat:
    Liniowe generatory kongruencyjne ... od dawna są skompromitowane


    i to do tego stopnia, że jak mi podasz kilka kolejnych wartości ze swojego generatora, jestem w stanie przewidzieć WSZYSTKIE następne wartości jakie wylosujesz :) , gdyż w banalny sposób można odtworzyć wartości zmiennych a,c i m z wzoru podanego w linku.
    np.:
    http://sandeepmore.com/blog/2012/03/23/breaking-linear-congruential-generator/

    Odnosisz się do pierwszego linku? Jeśli tak, to jest to artykuł o pseudolosowym algorytmie na AVR. Jest więc oczywiście podatny na taki problem, choć jak pokazuje wykres dla większości przypadków jest wystarczający dla aplikacji opartych ta malutkie AVR.


    andrzejlisek napisał:
    Taki szum można podać na wejście przetwornika A/C uzyskując jakąś wartość. Jeden odczyt służyłby do wygenerowania jednego bitu losowego. Wartość bitu zależy od tego, czy odczytana wartość jest wyższa, czy niższa od wartości progowej.
    ...
    Idę o zakład, że już przede mną były takie pomysły.

    Zakład wygrasz, bo dokładnie tak zrobiłem w artykule z drugiego linku. :)

    Urgon napisał:
    W linku o sprzętowym RNG od Dondu jest link do opisu dokładnie takiego generatora liczb losowych używającego złącze PN tranzystora. Generatory tego typu nie zawsze są losowe, bo wiele zależy od projektu płytki i zakłóceń w okolicy. Zarówno taki generator, jak i gołe ADC mogą łapać przykładowo przydźwięk sieciowy, który losowy nie jest.

    Mówisz o tym?:

    Generator liczb losowych oparty o pamięć RAM
    Jeśli tak, to pokazałem go tylko jako dodatek do ADC.

    Na poziomie najmłodszego bitu ADC, z którego składany jest bajt losowy, nawet przy takim problemie jak opisujesz nadal można uznać za losowy bowiem mówimy o przetworniku co najmniej 10-bitowym, czyli dla napięcia odniesienia np. 2,56V 1 bit to zaledwie 2,5mV :)

  • #15 02 Lip 2015 13:54
    andrzejlisek
    Poziom 28  

    Urgon napisał:
    AVE...

    W linku o sprzętowym RNG od Dondu jest link do opisu dokładnie takiego generatora liczb losowych używającego złącze PN tranzystora. Generatory tego typu nie zawsze są losowe, bo wiele zależy od projektu płytki i zakłóceń w okolicy. Zarówno taki generator, jak i gołe ADC mogą łapać przykładowo przydźwięk sieciowy, który losowy nie jest.


    O zakłóceniach i przydźwięku zapomniałem. Ale z drugiej strony, jak będą dwa takie same układy obok siebie, to zakłócenia będą tak samo zmieniać wyjście obu układów.
    Wtedy by się rejestrowało nie sam sygnał, tylko różnicę sygnałów, co teoretycznie powinno skompensować wpływ zakłóceń i pozostawić szum własny. Skoro tego nie stosuje się na szeroką skalę, to widocznie nie jest to sprawa tak prosta, jakby się mogło wydawać.

  • #16 02 Lip 2015 15:02
    Urgon
    Poziom 36  

    AVE...

    Sprzętowe generatory liczb losowych są stosowane w kryptografii, choćby w systemach bankowych do generowania unikalnych kluczy sesji bankowej. Muszą być więc absolutnie odporne na wpływ czynników zewnętrznych. Do zastosowań amatorskich każdy generator sprzętowy z ADC albo nawet generatory programowe liczb pseudolosowych w zupełności wystarczą. Ale dla wojska czy bankowości to stanowczo za mało. Dlatego dobre generatory liczb losowych są testowane i sprawdzane czasem przez długie miesiące i w różnych warunkach pracy. Nie tylko na "losowość", ale bardziej pod kątem odporności na wpływ zewnętrzny.

    Taki scenariusz weź pod uwagę:
    Duży bank raz na miesiąc generuje zestaw kluczy kryptograficznych do komunikacji ze swoimi oddziałami. Klucze na płytach przekazywane są do oddziałów pilnie strzeżonym kanałem. Sprytny haker jednak wie, że generator używa tranzystora do generowania losowego szumu, oraz wie, gdzie generator się znajduje. Buduje więc nadajnik z bardzo kierunkową anteną, celuje w stronę generatora i "zagłusza" szum swoim sygnałem nasycając tranzystor, co sprawia, że generator generuje same jedynki. Nikt poprawności kluczy nie sprawdza, bo ten system działał od lat bez problemów. Ale haker wie, z czego wygenerowano klucze i teraz może przechwycić, rozszyfrować, zmienić, zaszyfrować i przesłać dalej każde zlecenie transferu środków. Bank dość szybko się zorientuje, ale nim to się stanie, straty mogą być ogromne.

  • #17 02 Lip 2015 15:20
    dondu
    Moderator Mikrokontrolery Projektowanie

    Urgon napisał:
    Taki scenariusz weź pod uwagę:
    Duży bank raz na miesiąc generuje zestaw kluczy kryptograficznych do komunikacji ze swoimi oddziałami. Klucze na płytach przekazywane są do oddziałów pilnie strzeżonym kanałem. Sprytny haker jednak wie, że generator używa tranzystora do generowania losowego szumu, oraz wie, gdzie generator się znajduje. Buduje więc nadajnik z bardzo kierunkową anteną, celuje w stronę generatora i "zagłusza" szum swoim sygnałem nasycając tranzystor, co sprawia, że generator generuje same jedynki.

    To scenariusz dla filmu z Hollywood, a nie do faktycznego zastosowania. :)

  • #18 04 Lip 2015 11:06
    323493
    Użytkownik usunął konto  
  • #19 09 Lip 2015 01:01
    sundayman
    Poziom 24  

    Generator szumu na starym germanowym tranzystorze. A co tam - dodajmy jeszcze dwa takie same i zmieszajmy :)
    Wpuszczamy ten szum na dowolny ADC, całość zamykamy w obudowie z blachy stalowej 1mm.

    Całość to jakieś 200 zł. Razem z kolorowym napisem "military random noise generator".
    Ciekaw jestem, jak wszystkie połączone siły NATO wpłyną na działanie tego generatora liczb losowych ? Chyba z pomocą oddziału telepatów :)

  • #20 09 Lip 2015 10:43
    freebsd
    Poziom 34  

    Gdy potrzeba generatora z prawdziwego zdarzenia można po prostu kupić mikrokontroler posiadający moduł kryptograficzny.

  • #21 09 Lip 2015 12:35
    andrzejlisek
    Poziom 28  

    freebsd napisał:
    Gdy potrzeba generatora z prawdziwego zdarzenia można po prostu kupić mikrokontroler posiadający moduł kryptograficzny.

    Żebyś mógł kupić taki mikrokontroler, to trzeba go wyprodukować i do tego celu jest potrzebny generator losowy lub szumu. Domyślam się, że specjalizowane mikrokontrolery są lepsze niż amatorskie układy takie jak szum tranzystora lub przetwornik z wiszącymi wejściami, ale cały czas dyskusyjna jest podatność na czynniki zewnętrzne wpływające na pracę.

  • #22 09 Lip 2015 13:28
    freebsd
    Poziom 34  

    andrzejlisek napisał:
    Żebyś mógł kupić taki mikrokontroler, to trzeba go wyprodukować i do tego celu jest potrzebny generator losowy lub szumu. Domyślam się, że specjalizowane mikrokontrolery
    Sam Atmel ma w swojej wyszukiwarce 47 procesorów obsługujących TRNG.

  • #23 09 Lip 2015 18:08
    sundayman
    Poziom 24  

    Cytat:
    Domyślam się, że specjalizowane mikrokontrolery są lepsze niż amatorskie układy takie jak szum tranzystora


    A co masz do zarzucenia szumowi tranzystora ?
    Imo nie ma w przyrodzie nic bardziej przypadkowego niż fizyczny szum złącza.
    Sugerujesz, że w naturalnym szumie termicznym jest jakakolwiek prawidłowość ?

  • #24 09 Lip 2015 20:05
    maciej_333
    Poziom 34  

    sundayman napisał:
    Sugerujesz, że w naturalnym szumie termicznym jest jakakolwiek prawidłowość ?

    Każdy tranzystor, czy dioda szumią inaczej - tzn. z innym rozkładem. Inna sprawa, że szum ten zależny jest od temperatury.

  • #25 09 Lip 2015 20:19
    sundayman
    Poziom 24  

    Cytat:
    Każdy tranzystor, czy dioda szumią inaczej - tzn. z innym rozkładem


    a jakie ma znaczenie rozkład szumu ? Dowolny szum, czy tam biały, czy różowy jest tak samo przypadkowy - idealnie przypadkowy.

  • #26 09 Lip 2015 20:24
    Urgon
    Poziom 36  

    AVE...

    Na zależność od temperatury pomoże albo zapakowanie układu generacji w ogrzewany pojemnik, jak z TXCO, albo kompensacja termiczna w sofcie. Tak czy siak generalnie każdy półprzewodnik szumi, kwestią jest izolowanie go od wpływu warunków zewnętrznych. Amerykańscy idioci wydają setki i tysiące dolców na "magiczne" radioodbiorniki kryształkowe z diodą germanową wystawioną na światło, by uzyskać maksymalnie losowy szum zależny również od warunków oświetleniowych. Z kolei szukający duchów używają radia, które jest szybko przestrajane przez cały swój zakres wte i nazad, by wyłapywać pojedyncze słowa i sylaby z komercyjnych pasm, co ma udawać próbę kontaktu ducha. Oczywiście łowcy duchów nie wiedzą, że to tak działa, więc dają się pięknie naciągnąć. Połączenie odbiornika FM z TRNG dałoby ciekawy efekt, jeśli chodzi o generowanie chaosu.

  • #27 09 Lip 2015 20:33
    andrzejlisek
    Poziom 28  

    sundayman napisał:
    Cytat:
    Domyślam się, że specjalizowane mikrokontrolery są lepsze niż amatorskie układy takie jak szum tranzystora


    A co masz do zarzucenia szumowi tranzystora ?
    Imo nie ma w przyrodzie nic bardziej przypadkowego niż fizyczny szum złącza.
    Sugerujesz, że w naturalnym szumie termicznym jest jakakolwiek prawidłowość ?


    Samemu szumowi tranzystora nie mam nic do zarzucenia, nawet kilka postów wyżej sam zasugerowałem, że tranzystor z wysokim poziomem szumów będzie dobry, ale już kilka postów wyżej pojawił się komentarz sugerujący, że taki tranzystor jest podatny na przydźwięk sieci elektrycznej i zakłócenia elektromagnetyczne, co ogranicza przypadkowość.

  • #28 09 Lip 2015 20:42
    freebsd
    Poziom 34  

    W 1992 r. M. Richter opublikował swoja pracę doktorską: Ein Rauschgenerator zur Gewinnung von quasi-ideal Zufallszahlen für die stochastische simulation. Opisał tam generator liczb wykorzystujący szum termiczny diody półprzewodnikowej. Ta metoda nie jest uważana za bezpieczną, ponieważ może być manipulowana z zewnątrz (np. oddziałując fala elektromagnetyczną). Nie wiem czy można temu zapobiegać, np. poprzez ekranowanie. Na tej stronie https://www.random.org/randomness/ odrobinę poruszono temat wykorzystania fizyki kwantowej. Tu z kolei jest więcej o szumach... http://elektronikab2b.pl/technika/25143-szumy-wlasne-ukladow-elektronicznych#.VZ6-LXU8YWM ,a temat nie jest banalny (patrz załącznik).

    W firmowych rozwiązaniach wykorzystuje się np. niestabilności oscylatorów.

  • #29 09 Lip 2015 21:33
    sundayman
    Poziom 24  

    Cytat:
    tranzystor jest podatny na przydźwięk sieci elektrycznej i zakłócenia elektromagnetyczne,


    Dlatego napisałem o puszce z blachy stalowej.
    Do tego dowolny stabilizator napięcia za 10 zł, i sprawa załatwiona.

    Chyba, że ktoś będzie chciał toto zakłócać falami skalarnymi, albo grawitacyjnymi, no to faktycznie ;)

  • #30 09 Lip 2015 21:44
    andrzejlisek
    Poziom 28  

    Czy zamiast puszki/ekranu (ewentualnie oprócz ekranowania) sprawdziłby się sposób, w którym są dwa takie same generatory obok siebie i wykorzystywany sygnał jest różnicą potencjałów wyjść tych generatorów? Wtedy każde zakłócenie odkształci oba sygnały jednakowo, więc różnica to wyeliminuje, na tym samym założeniu jest oparte każde łącze z sygnałem symetrycznym.