трънки и блогинки

Забавления с ent

Написано на: 07.12.2004 · 7 коментара

Без добър генератор на случайност в живота сме преебани. Тази, толкова близка до логиката и толкова далеч от практическото осъществяване, теза смятам да докажа.

За тези, които ги влече литературата, бих припомнил немският офицер от „Триумфалната арка“ на Ремарк, който обясняваше на разпитваният от него, че каквото и да казва или да прави той не може да се отклони от шаблона, който той болезнено познава. Дали героят на книгата, щеше да избере пътя на съпротивата или на колаборацията бе без значение, защото всички пътища и изходите от тях бяха известни.

За тези, които са запазили детето в себе си, бих припомнил как едно време, може би, са играли на „познай в коя ръка е камъчето“ и е трябвало да изненадат противника си с разнообразните си тактики и липсата на повтаряемост и шаблон в действията им. Друга подобна игра беше и „нож, листо и камък“, на която определени „печени“ батковци бяха много добри.

Обаче, за тези, които са свикнали с командния ред, мисля, ще е най-забавно и интересно.

Програмката се нарича ent и е предназначена за проверка на качеството на генератори на псевдослучайни числа. Тя смята няколко показателя, които са описани на нейната страница и ако искате да разберете какви са те и какви са нормалните им стойности вижте горната страница.

Първоначално целта ми беше да проверя какво е качеството на генераторите на случайност в различни операционни системи. Благодарение на Vortex и Дончо се сдобих с проби от Solaris, OpenBSD, FreeBSD, Windows и разбира се Linux.

Целях да имам нещо еквивалентно на това под Linux:

dd if=/dev/urandom count=10K bs=1 conv=ascii of=linux.rnd

В последствие реших да добавя и разни други файлове, за да добия представа как може различни типове файлове да се ползват за източници на случайност. Така добавих и песен в mp3, jpeg картинка, html страница, ядрото, с което съм в момента, малко изход от /dev/zero и дори се опитах да създам малко случайност и сам като цъкам неориентирано по клавиатурата. Всички тези файлове ги сложих с разширение .rnd, за да мога да изпълня долното:

for rndfile in `ls *.rnd`; do echo $rndfile >> results.txt ; ent -t $rndfile >> results.txt; echo „“ >> results.txt; done
sed -ri -e ‘s/^(1|0),//’ results.txt

Както, може би разбирате, аз подадох събраните от мен файлове за анализ на ent и събрах резултатите в results.txt файла. Ето го и него:

devzero.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10240,0.000000,2611200.000000,0.000000,4.000000,-100000.000000

freebsd.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10240,7.980525,278.600000,127.904199,3.146542,0.011914

img.jpg.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
45419,7.933575,4368.206235,119.567384,3.360550,0.021741

linux.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10240,7.981352,260.300000,127.650391,3.080891,0.016841

mе.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
94,0.998693,11959.787234,49.478723,4.000000,-0.193651

openbsd.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10240,7.982329,248.800000,127.149707,3.155920,-0.001354

solaris.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10240,7.983549,235.450000,127.219141,3.155920,0.006017

song.mp3.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
5030138,7.966659,325372.579764,125.314870,3.153515,0.102014

vmlinuz.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
1385038,7.996012,9910.271109,127.390263,3.133439,0.003880

webpage.html.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
27635,4.836179,355352.051493,88.669369,4.000000,0.096925

windows.rnd
File-bytes,Entropy,Chi-square,Mean,Monte-Carlo-Pi,Serial-Correlation
10000,7.982685,239.795200,128.395000,3.126050,0.013917

Детайлния анализ на резултатите оставям на вас (те са в csv, така че може да се забавлявате), защото може да има много аргументи и заключения, но само искам да изтъкна, че предвидимостта на човека надвишава само /dev/zero , което устройство бълва само и единствено и завинаги нули и въобще не си помисля за друго.

Това за мен доказва, че не само ще бъдем преебани, ако нямаме добър генератор на случайност. Ние ще бъдем оттегчителни.

Категория: за шанса · проекти

7 коментара ↓

  • Хубаво ми е, когато хората коментират. Чета внимателно всеки коментар и отговарям, когато имам какво да кажа.

  • дафчо на 08.12.2004г. в 11:46ч.

    А на някои дънни платки може да има Intel random generator. Това, не пречи ли на резултатите?
    А добър генератор на случайност е обикновеното гама лъчение. В поколенията на живите същества, се създава завидна причудливост.

  • Никола Славчев на 08.12.2004г. в 12:22ч.

    Ако се интересуваш от тестове за RNG този документ ще ти е от полза:
    http://csrc.nist.gov/publications/nistpubs/800-22/sp-800-22-051501.pdf
    Някъде на сайта на NIST имаше и сорсове на описаните методи. И все пак тестовете само предполагат, а не доказват липсата на зависимости. И Енигма генерира висока ентропия, но шифъра ѝ се разбива елементарно.

    Поздрави! :)

  • пейо на 09.12.2004г. в 20:30ч.

    @ Дафчо
    Ми не знам за платките. Аз питам устройството, а то кой пита е вече отвъд познанията ми.

    А какво е това гама лъчение и има ли infrared интерфейс? Мисля това беше един от основните проблеми – да се цифровизират резултатите от такива източници, макар че сега чета че има и процес на „дестилация“ на тези резултати, с цел да се преодолеят някои слабости.

    @ Никола
    Аз не се интересувах толкова, до преди да се опитам да се запозная с документа и прложените сорсове. Мноого интересно ми стана, за което ти благодаря най-искренно!

    Този pdf наистина събуди много нови въпроси в мен, въпреки че се губя по частите с повечко математика.

    Ще ти бъда много благодарен, ако ми отделиш малко време да ме насочиш по някои от въпросите, които се формулират в мен.

  • дафчо на 10.12.2004г. в 07:01ч.

    Ами стандартното действие на йонизиращата радиация върху живи неща.

  • Никола Славчев на 10.12.2004г. в 08:12ч.

    Заповядай! Стига да съм достатъчно компетентен по тях. И на мен на места ми куца математиката. Занимавам с приложна криптография и генераторите повече ги ползвам отколкото да ги разучавам. Теорията съм я учил защото сертифицирахме разни алгоритми по FIPS140-2 стандарта, където гореописаните тестове са задължителни ако алгоритъма не е в списъка на вече одобрените. Моето лично мнение е, че случайноста е недуказуема със стандартни тестове.
    Дафчо е прав за йонизацията, но резултатите са гаусова крива при висока активност (голям брой регистрирани частици) и поасонова при ниска, а за криптографски цели се иска изключително равномерно разпределение, така че и там трябва да се мине през псевдо RNG алгоритъм за да не е предвидим резултата.

  • пейо на 10.12.2004г. в 11:09ч.

    @ Дафчо
    Това само ми напомня колко много процеси на разложение протичат във всеки един от нас постоянно…. Приземяваща мисъл такава :))

    @ Никола
    Благодаря за желанието, ще се възползвам с няколко въпроса и ще се постарая да не те занимвам с глупости. Днес вече ме наругаха, че шляпам с джапанки в храма на науката и питам къде е кинкалерията, така че имай предвид, че няма да е много умно това което ми се мъти в главата.

  • Христо Илиев на 10.12.2004г. в 19:41ч.

    И на мен едно време ми се беше наложило да търся свестен случаен генератор за Монте Карло симулация, при което /dev/urandom отпадна още при първия тест.
    Иначе естественият гама фон не е лош източник на случайност, но ще има да чакаш с векове за да натрупаш повечко чисълца. IR интерфейс има, ако сложиш такъв на броячната апаратура :) Което ми напомня, че съм обещал на Велин да му правя генератор на бял шум със сериен изход…