Рейтинг:0

PRNG на основе GF?

флаг tf
Tom

Есть ли генератор псевдослучайных чисел на основе полей Галуа? Источник случайности AES лежит в GF, поэтому GF должен быть способен генерировать случайные биты.

Почему нет таких генераторов?

poncho avatar
флаг my
Ну, вентили И выполняют умножение в $GF(2)$, а вентили XOR выполняют сложение. Все схемы могут быть построены из этих примитивов, следовательно, любая логика, выражаемая как схема (включая PRNG), может рассматриваться как основанная на этом конечном поле...
Рейтинг:1
флаг sa

Я не понимаю, что вы имеете в виду под Источник случайности AES лежит в G(alois) F(field).

Поле — это алгебраическая структура, в нем нет случайности. Вы можете представить классическую теоретико-информационную случайность, которая является свойством вероятностного источника. Источник используется для создания начального числа, а начальное число может быть принято как элемент поля с отображением обновления, основанным на алгебраической структуре поля.

Даже если вы захотите мыслить в терминах колмогоровской сложности как меры «случайности» и возьмете бинарное расширение поля Галуа и представите его отдельные элементы как битовые строки, некоторые из этих элементов будут иметь краткие описания, некоторые — нет, но поле Просто пассивная структура.

В дополнение к хорошим примерам в другом ответе генераторов, использующих конечные поля, следующие также используют конечные поля:

  1. Последовательности максимальной длины ($м-$последовательности) используют LFSR с полиномом соединения примитивным полиномом $ф(х)$ степени $n$ над $GF(2)$ а тактирование состояния соответствует умножению на примитивный элемент в поле расширения $$GF(2^n)=GF(2)/(f(x))$$
  2. Вы можете взять $м-$последовательность, которая уязвима для атаки Берлекэмпа Мэсси, и применяет нелинейную логическую функцию к некоторым битам состояния. Необходимые свойства (нелинейность, устойчивость, алгебраическая невосприимчивость и т. д.) для того, чтобы такая функция фильтрации приводила к более надежной выходной последовательности, доказываются с помощью полей Галуа. См., например, ответ на этот вопрос для некоторых из этих свойств: https://crypto.stackexchange.com/questions/34946/how-are-boolean-functions-used-in-cryptography/
  3. Вы также можете взять несколько LFSR и применить к их выходу нелинейную функцию. Аналогичные комментарии, что и в пункте 2 выше, применимы.
Рейтинг:1
флаг si

Есть несколько генераторов, использующих конечные поля. Блюм Блюм Шуб использует один напрямую, но очень медленно. AES-CTR-DRBG представляет собой CSPRNG, использующий AES-128 в режиме CTR, тем самым косвенно используя конечное поле. Это достаточно быстро для практического использования, особенно с аппаратно ускоренными инструкциями AES, которые есть во многих современных процессорах.

poncho avatar
флаг my
Технически число Блюма-Блюма-Шуба основано на кольце с нетривиальными идеалами, следовательно, это не конечное поле...

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

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