Рейтинг:0

Реализация хаотической карты для получения (псевдо)-случайного числа

флаг in

Для моего проекта я использовал карту Henon для генерации (псевдо)-случайного числа. Я использовал следующий код для генерации матрицы (псевдо)-случайного числа.

def generate_by_henonmap (размер, ключ):
    х = ключ [0]
    у = ключ [1]
    # Общее количество произведенных битовых последовательностей
    sequenceSize = измерение * измерение * 8
    bitSequence = [] # Каждая bitSequence содержит 8 бит
    byteArray = [] # Каждый byteArray содержит m bitSequence
    Matrix = [] # Каждая матрица содержит m*n byteArray

    для i в диапазоне (sequenceSize):
        # Классическая карта Энона имеет значения a = 1,4 и b = 0,3.
        хН = у + 1 - 1,4 * х**2
        уН = 0,3 * х

        х = хН
        у = уН

        если xN <= 0,4:
            бит = 0
        еще:
            бит = 1

        пытаться:
            bitSequence.append(бит)
        кроме:
            битовая последовательность = [бит]

        если я % 8 == 7:
            десятичное = десятичное (последовательность битов)
            пытаться:
                byteArray.append(десятичный)
            кроме:
                массив байтов = [десятичный]
            битовая последовательность = []

        byteArraySize = измерение * 8

        если я % byteArraySize == byteArraySize-1:
            пытаться:
                Matrix.append(массив байтов)
            кроме:
                Матрица = [массив байтов]
            массив байтов = []

    матрица возврата

Прежде чем использовать этот код в своем производстве, я проверяю случайность с помощью набора тестов NIST из это но получил такой результат:

Допустимый тест из NIST-SP800-22r1a:
-монобит
-частота_в_блоке
-бежит
-самая длинная_выполнить_единицы_в_блоке
-dft
-non_overlapping_template_matching
-серийный
-приблизительная_энтропия
-нарастающие суммы
-random_excursion
-random_excursion_variant
Результаты теста:
- ПРОШЕЛ - оценка: 0,525 - Монобит - прошедшее время: 0 мс
- ПРОШЕЛ - оценка: 0,999 - Частота внутри блока - прошедшее время: 0 мс
- FAILED - оценка: 0.0 - Runs - прошедшее время: 1 мс
- FAILED - оценка: 0,002 - Самое длинное выполнение в блоке - прошедшее время: 0 мс
- FAILED - оценка: 0,004 - Дискретное преобразование Фурье - истекшее время: 2 мс
- ПРОШЕЛ - оценка: 0,899 - Сопоставление неперекрывающихся шаблонов - истекшее время: 8 мс
- FAILED - оценка: 0.0 - Serial - прошедшее время: 54 мс
- FAILED - оценка: 0.0 - Приблизительная энтропия - прошедшее время: 102 мс
- ПРОШЕЛ - оценка: 0,887 - Суммарные суммы - прошедшее время: 4 мс
- FAILED - оценка: 0,11 - Случайное отклонение - прошедшее время: 28 мс
- ПРОШЕЛ - оценка: 0,678 - Случайный вариант экскурсии - прошедшее время: 1 мс

Я думал, что хаотическая карта может генерировать достаточно рандома, но результат был таким разочаровывающим. Есть ли какая-либо логическая ошибка в коде, которая приводит к такому плохому результату? Я предполагаю, что то, как он генерирует битовую последовательность числа, создает проблему.

        если xN <= 0,4:
            бит = 0
        еще:
            бит = 1

Есть ли лучшая реализация хаотической карты для создания (псевдо)-случайного числа?

Paul Uszak avatar
флаг cn
Привет. Все это кажется неправильным. Тест прошел мс? Это должно занять много времени, особенно для Python. Насколько большим был файл примера? Почему `xN` такой предвзятый? Запустите ent на образце файла и посмотрите, что он говорит. На данном этапе это тест на случайность.
fgrieu avatar
флаг ng
Два замечания, не предназначенные для объяснения того, почему тест не проходит: 1) используется аппроксимация вещественных переменных с плавающей запятой. Это делает недействительными аргументы, основанные на допущении реальных переменных. В частности, рассуждения о том, что трансформация приводит к хаотическому поведению и длительному периоду, разваливаются в теории и в какой-то степени на практике. 2) Экспериментальные статистические тесты, такие как тест NIST, иногда могут показать, что генератор не подходит; не то, чтобы это было хорошо для криптографического использования. Очень легко создать генератор, который проходит тест NIST, но предсказуем по нескольким последовательным результатам.
Рейтинг:2
флаг my

Проблема с этим генератором случайных чисел заключается в том, что биты коррелированы; соседние выходные биты различаются в 70% случаев (конечно, для случайного потока мы ожидаем, что выходные данные будут отличаться в 50% случаев). Этого достаточно, чтобы любой тест, зависящий от битовой корреляции, провалился.

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

WhyMeasureTheory avatar
флаг in
Есть ли какое-то улучшение этого кольца или мне следует использовать другую хаотическую карту? @poncho Ваше предложение будет для меня большим подспорьем. И спасибо за ваш ответ.
poncho avatar
флаг my
Как его улучшить, будет зависеть от того, что вы пытаетесь сделать. Если вы пытаетесь придумать статистический ранг, очевидным подходом будет вычисление показателя Ляпунова и, исходя из этого, определение того, сколько «шагов» требуется, чтобы превратить неточности с плавающей запятой в дисперсии в битовом выходе. (и сгенерировать один вывод после такого количества шагов). Если вы пытаетесь разработать «криптографическую сеть», это сложнее (из-за проблем, на которые указал fgrieu).

Ответить или комментировать

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