id: Гость   вход   регистрация
текущее время 15:46 19/09/2020
Автор темы: Гость, тема открыта 27/09/2014 18:00 Печать
Категории: криптография, случайные числа
http://www.pgpru.com/Форум/Криптография/ГенерацияТринарныхСлучайныхЧисел
создать
просмотр
ссылки

генерация троичных случайных чисел

Где-то (не помню где) упоминалось, что в Китае военная и государственная криптография работает в троичной системе исчисления.
В принципе – интересное направление, например, хотя бы потому, что гаммирование работает в системе исчисления с любым основанием, являющимся степенью простого числа. Однако, возник вопрос: как генерировать случайные числа (пригодные для использования в криптографии) для системы исчисления с основанием, не являющимся степенью 2.
Пытался найти что-либо о генерации true random numbers в троичной системе исчисления – совершенно ничего (не говоря уже про остальные – 5,7,11,...).
По идее, при решении этой задачи можно рассматривать два направления:
1 – аппаратные генераторы;
2 – преобразование двоичных случайных чисел в троичные.
Если первое направление – это уровень физико-математического НИИ (и даже в этом случае есть вопросы), то со вторым направлением можно, наверное, что-то предпринять: весьма привлекательна идея генерации случайных чисел с помощью /dev/random и несмещенного преобразования их в систему исчисления с другим основанием.
Интересно, существуют ли какие-либо работы в этом направлении, или это китайская военная тайна?


 
Комментарии
— unknown (27/09/2014 22:49, исправлен 27/09/2014 23:30)   профиль/связь   <#>
комментариев: 9796   документов: 488   редакций: 5664

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


Например, нужно генерировать десятичные числа. Тогда, ближе всего к десятичным будет 210 = 1024. Просто берём 10-битную последовательность и если результат больше или равен 1000, то отбрасываем и генерируем рэндом заново. А если меньше, то берём результат по модулю 10. Ещё лучше — по модулю 1000 получать трёхразрядные десятичных числа за один раз. Удобнее конечно работать с байтами. Тогда всё, что от нуля до 249 — берём по mod 10, всё, что не попадает в интервал — отбрасываем и перегенерируем из /dev/{u}random заново. Из одного байта можно генерировать и два десятичных числа за один проход, отбрасывая результат, начиная с 200 и беря модуль по 100.


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


методом отбрасывания и округления можно моделировать любое (даже предопределённое неплоское и неравномерное) распределение с заданной точностью (<2512, например). А для равномерного — вообще никаких проблем. Отбрасывай хвосты, да и всё. Цикл с одной проверкой.


Сложнее реализовывать в двоичной системе недвоичные перестановки (не генерировать перестановки по методу тасовки карт — это также тривиально для небольших чисел, а например, эффективно реализовать блочные шифры с размером блока, некратным 2n). Есть или переработка обычных алгоритмов (AES), но запакованных в некрасивые и неоптимальные конструкции, или совершенно альтернативные и очень маргинальные алгоритмы, созданные для этой цели с нуля.


Аппаратные рализации троичного железа делали ещё очень давно в СССР (Сетунь). За рубежом исследовательские прототипы на более современной аппаратной базе делают до сих пор. Но особого распространения это не получило. И даже непонятно — зачем это нужно теперь? Это в середине XX века было актуально выжать из аппаратной части больше производительности, но сейчас такое усложнение основ мало оправдано. Даже если его внедрить, производительность будет выше даже не на десятичный порядок. С т.з. криптографии — это в пределах погрешности, с т.з. экономики даже при замедляющемся законе Мура — тоже. Скорее перейдут если не на кванты, то на какие-то другие физические принципы (какая-нибудь неквантовая оптоэлектроника), но не будут просто так подбирать крохи на этих тритах и трайтах.


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

— Достовер (28/09/2014 00:35)   <#>
Действительно просто, эффективно (высокий процент используемых случайных чисел) и несмещённо.
У меня хуже (сложнее и менее эффективно) получилось – при преобразовании 9 бит выходил 1 трит, хотя тоже несмещенно (3 9-битных числа преобразуются в троичную систему исчисления, оставляются только 3 младших разряда, остальные отбрасываются, одно из чисел циклически сдвигается влево, другое – вправо а потом все 3 числа складываются по модулю 3).
Спасибо за подсказку!
С таким преобразователем и аппаратного ничего мудрить не нужно для иных систем исчисления – достаточно бинарных устройств и существующих алгоритмов.
Хотя на циклических счетчиках со случайным периодом стопа, в теории, можно реализовать аппаратный генератор для любой n-ричной системы исчисления, что по-сути и есть аппаратный RND mod n. – Первоначально в качестве генератора я пытался представить физическую систему, в которой некоторый элемент может находиться с равной вероятностью в 3 или более состояниях.
Ваша оценка документа [показать результаты]
-3-2-1 0+1+2+3