Pull to refresh

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

Reading time 5 min
Views 17K
Лишь вследствие нашей слабости, вследствие нашего невежества случайность для нас существует

А. Пуанкаре

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

В наш век цифровых технологий и огромной роли информации в развитии человечества защита информации – актуальнейшая задача. Технологическое решение этой задачи предполагает привлечение «случайности», а именно – генерацию случайных чисел. При этом от качества используемых генераторов напрямую зависит качество получаемых результатов. Это обстоятельство подчёркивает известный афоризм Роберта Р. Кавью из 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:
Если интересна программная реализация, то загрузил сюда. Писал больше года назад, смею надеяться что с тех пор скилл программирования улучшился: )
Tags:
Hubs:
+1
Comments 28
Comments Comments 28

Articles