«Человеческая» энтропия для генератора случайных чисел

Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

Чем больше люди постигали тайны Вселенной, тем ближе они приближались к той точке незнания, в которой их предки все приписывали богам. Теперь это называется – случайность. И хотя Эйнштейн не верил в случайность – он говорил «Бог не играет в кости», – он в числе первых из списка: Эйнштейн, Шредингер, Лаплас…

В наш век цифровых технологий и огромной роли информации в развитии человечества защита информации – актуальнейшая задача. Технологическое решение этой задачи предполагает привлечение «случайности», а именно – генерацию случайных чисел. При этом от качества используемых генераторов напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из ORNL: «генерация случайных чисел слишком важна, чтобы оставлять её на волю случая».

Источники настоящих случайных чисел, например, физические шумы – детекторы событий ионизирующей радиации, дробовой шум в резисторе, космическое излучение и т.п. – применяются в приложениях безопасности редко. Альтернативным решением является создание некоторого набора из большого количества случайных чисел и опубликование его в некотором словаре. Тем не менее, и такие наборы обеспечивают очень ограниченный источник чисел по сравнению с требуемым: данные наборы действительно обеспечивают статистическую случайность, но они не достаточно случайны.

Криптографические приложения используют для генерации случайных чисел особенные алгоритмы. Эти алгоритмы заранее определены и, следовательно, генерируют последовательность чисел, которая теоретически не может быть статистически случайной. В то же время, если выбрать хороший алгоритм, полученная численная последовательность будет проходить большинство тестов на случайность. Такие числа называют псевдослучайными числами.

Никакой детерминированный алгоритм не может генерировать полностью случайные числа, он может только аппроксимировать некоторые их свойства. Как сказал Джон фон Нейман, «всякий, кто питает слабость к арифметическим методам получения случайных чисел, грешен вне всяких сомнений».

Большинство простых арифметических генераторов хотя и обладают большой скоростью, но страдают от многих серьёзных недостатков:

— Слишком короткий период/периоды.
— Последовательные значения не являются независимыми.
— Некоторые биты «менее случайны», чем другие.
— Неравномерное одномерное распределение.
— Обратимость.

Как же сделать такой ГСЧ, результаты которого будут непредсказуемы в той мере, насколько это вообще возможно? Что является одним из самых непредсказуемых явлений в природе и практически не поддается формализации, а следовательно, моделированию? Поведение человека: индивидуума, а не массы (толпы, группы, организации, клуба и т.п.).

Предлагается конструирование ГСЧ на идее непредсказуемости поведения отдельного человека. Для реализации проекта выбрана интегрированная среда разработки Microsoft Visual Studio 2010, и язык Visual Basic.NET.

На форме проекта размещены рядом друг с другом 56 кнопок-квадратиков. К каждой кнопке привязано системное событие MouseEnter.

image

В обработчике событий каждой кнопки находится код, который получает системное время в миллисекундах. При наведении курсора на кнопку в памяти сохраняется некоторое число в пределах 0 ÷ 999. При повторном проведении курсором над той же кнопкой сохраняется уже новое число. Таким образом, пользователь произвольно проводит курсором над полем кнопок, формируя серию чисел. Рекомендуется «поработать» (провести курсором над кнопками) минимум над 1/2 поля, чтобы получить «лучшую» последовательность (при меньшем количестве программа не позволит получить серию цифр).

Вне зависимости от того, над сколькими квадратиками был проведен курсор, в результате всегда будем получать 56 цифр. «Недостающие» цифры появляются следующим образом:

— Создается 2 массива b и c размерностью в 56 элементов каждый. Поочередно рандомно (встроенной функцией) заполняются массивы b и c; каждый раз, до заполнения очередного элемента, инициируется сброс счетчика рандомизации, иначе каждое следующее значение зависело бы от предыдущего.
— Фрагмент программного кода (представлен ниже) иллюстрирует алгоритм заполнения массива:

 Randomize()
 
                        znak = Rnd() * 5
                        If znak = 0 Then
                            a(ii) = b(ii) + c(ii)
                            If a(ii) > 999 Then
                                While a(ii) > 999
                                    a(ii) = (a(ii) / 3.14) + Rnd() * 42
                                End While
                            End If
                        ElseIf znak = 1 Then
                            a(ii) = b(ii) - c(ii)
                            If a(ii) < 0 Then
                                a(ii) = a(ii) * (-1)
                            End If

                        ElseIf znak = 2 Then
                            a(ii) = b(ii) * c(ii)
                            If a(ii) > 999 Then
                                While a(ii) > 999
                                    a(ii) = (a(ii) / 3.14) + Rnd() * 42
                                  End While
                            End If
                        ElseIf znak = 3 Then
                            a(ii) = b(ii) / (c(ii) + Rnd() * 9)
                            If c(ii) = 0 Then
                                c(ii) = Rnd() * 99 + 1
                            End If
                            If a(ii) > 999 Then
                                While a(ii) > 999
                                    a(ii) = (a(ii) / 3.14) + Rnd() * 42
                                End While
                            End If

                        ElseIf  znak = 4 Then
                            a(ii) = Now.Millisecond
                        End If


Каждый раз, при очередном «резервном» заполнении массива, вызывается функция Randomize(), которая в качестве исходной точки берет значение системного таймера, а не предыдущее значение Rnd. То есть каждый раз, генерируя очередную последовательность, пользователь инициирует заполнение массивов b и c заново, разными значениями, не зависящими друг от друга.
После того, как пользователь достаточно «поелозил» по полю, он нажимает на соответствующую кнопку и получает результат.
Программа позволит пользователю увидеть результат работы только в том случае, если он «задействовал», как минимум, половину кнопок поля, в противном случае он получит сообщение о необходимости «задействовать» большее число «реагирующих» кнопок. Реализованная программа позволяет скопировать полученные данные в буфер обмена. Также пользователь может получить статистические данные по сгенерированной последовательности, такие как число запусков генерации, распределение чисел по интервалам, сумму данной серии чисел, нажав соответствующую кнопку.

Кнопки-квадратики расположены в абсолютно хаотическом порядке, то есть первая кнопка (если ее задействовать курсором) необязательно определяет первое число последовательности, и т.д., что дополнительно улучшает «случайность», поэтому даже если построчно проводить по полю, с допустимо большой скоростью, нельзя будет определить системность полученной последовательности. Невозможно предсказать, как поведет себя пользователь, в какой последовательности он будет водить курсором над квадратиками, какие задействует, какие нет. Следует заметить, что при повторе одного и того же алгоритма движений курсора, будем получать разные цифры: невозможно попасть в тот же временной промежуток, в котором «рисовалась» предыдущая траектория курсора, так как человеческая реакция просто не способна на такое. Таким образом, качество предлагаемого генератора обусловлено, в том числе, внешним источником энтропии:

— произвольностью расположения кнопок на форме;
— произвольностью их выбора пользователем;
— непредсказуемостью временного интервала этого выбора.
Данный генератор тестировался на качество работы:
— случайность;
— равномерную распределенность;
— статистическую независимость.

Тестирование проведено неоднократно, разными людьми, в разное время. Применялись тесты: критерий пиков, тестирование равномерного распределения: математическое ожидание, дисперсия, среднеквадратическое отклонение, частотный тест, проверка по критерию «Хи-квадрат», проверка на статистическую независимость, отсутствие автокорреляции. Большинство тестов показали надежность данного генератора (не менее 90%), Хи-квадрат тест показал 99% надежности, тестирование отдельных статистик всегда показывало результаты, близкие к эталонным для равномерного распределения.

UPD:
Если интересна программная реализация, то загрузил сюда. Писал больше года назад, смею надеяться что с тех пор скилл программирования улучшился: )

Similar posts

AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 28

    +7
    Что является одним из самых непредсказуемых явлений в природе и практически не поддается формализации, а следовательно, моделированию? Поведение человека: индивидуума
    Спорное утверждение, по-моему.

    p.s. читая вашу реализацию, мне сразу вспоминается генерация ключей для WebMoney)
      0
      Когда-то в университете нас учили: чтобы предсказать будущее, нужно не так уж и много — знать начальное положение и направление движения всех атомов во вселенной.
        +2
        Не иронизируйте. Я к тому, что пример странноват.

        Как по мне, те же квантовые флуктуации намного более непредсказуемые)
          0
          да… а создатель — это огромный вселенский компьютер, который может высчитывать положения этих атомов в нужной точке времени :)
            0
            Сразу вспоминается «Автостопом по галактике».
            –1
            Если вы демон Лапласа это не проблема: )
              0
              … пока за дело не берется квантовая механика.
              0
              В очень старых версиях Opera Mini тоже такая штука была
                0
                Согласен, спорное, но в данном контексте речь идет о непредсказуемости того как человек будет двигаться по полю кнопок. Да возможны шаблоны (рисование спирали, квадрата, X, и т.д.), но попадание в один и тот же временной промежуток, рисуя одно и тоже — на мой взгляд событие весьма сомнительное (речь идет о миллисекундах, размах (0 — 999)), а разница в одну миллисекунду в начале — повлечет полное изменение всей последовательности.
                  0
                  Ну не знаю, если спросят о «непредсказуемости», то у меня сразу возникают ассоциации с какими-нибудь явлениями вроде Броуновского движения, а не с человеком)
                    0
                    У некоторых людей мысли, как броуновское движение, так что — никакого противоречия.
                  +2
                  Айзек Азимов явно поддержал бы Ваши сомнения :) Как раз его герой Гэри Селдон разработал "психоисторию", в рамках которой статистически просчитал будущее человечества в галактических масштабах и через много-много лет после себя с помощью достигнутых результатов оказывал влияние на ход процессов в обществе.
                  0
                  Если такая задача возникает на десктопе — что мешает просто взять шум из звуковой карты? (тот же дробовой шум по сути)
                    0
                    Закон распределения не так близок к равномерному как хотелось бы, вот люди и извращаются, как например это
                    Lavarand
                    0
                    А где кстати пример посмотреть?
                      0
                      Если интересна программная реализация, то загрузил сюда. Писал больше года назад, смею надеяться что с тех пор скилл программирования улучшился: )
                        0
                        кстати если проводить по кнопкам по очереди например змейкой, то получается мягко говоря не равномерное распределение :)
                          0
                          Ну не знаю, только что сделал как вы сказали змейкой, получилось:

                          0-250: 36
                          251-500: 43
                          501-750: 41
                          751-999: 48

                          Распределение может и не совсем равномерное, но и нельзя сказать что «мягко говоря не равномерное распределение»
                            0
                            "
                              0
                              я змейкой по горизонтали водил: )
                              Да, действительно, распределение не равномерное, но один запуск это слишком мало, при дальнейших запусках есть большая вероятность «выравнивания» серии, и не стоит каждый раз водит в одинаковой последовательности, весь смысл как раз в том чтобы в новом запуске рандомно по полю пробежаться
                                0
                                Ну естественно, просто показал что и такое бывает
                                  0
                                  От 0 до 250 почему-то так выскакивает вперед… i.imgur.com/9IJ7Kxf.png
                        0
                        При создании электронного-ключа для usb-токена в интернет-банке Абсолютбанка предусмотрен точно такой же принцип.
                          0
                          Используется ПО компании BIFIT
                          +5
                          А многочисленные «поводите мышкой и понажимайте кнопки некоторое время над этим полем, мы собираем энтропию» (или без поля), используемые в различном софте — это не оно же? Примеры: KeePass, TrueCrypt, Cryptool, Mega.co.nz, /dev/urandom (выше уже называли вебмани) и т.д.
                            0
                            Есть ведь /dev/urandom, на подобном принципе построен.
                              +6
                              image
                                0
                                Был проведен эксперимент, людей просили назвать серию абсолютно произвольных цифр, и все что они называли не проходило по тестам как случайная последовательность. Хотя здесь во многом зависит от теста проверки, многие алгоритмы проверки говорят что «1234567890123456...» — абсолютно случайная независимая серия.

                              Only users with full accounts can post comments. Log in, please.