Добрый вечер! Ищу генератор перестановок из N элементов, который бы,

Question

RU.CRYPTOGRAPHY — Криптография, алгоритмы, шифрование.

Добрый вечер! Ищу генератор перестановок из N элементов, который бы,

во-1, за N! генераций выдал бы N! уникальный перестановок и при этом, во-2, любые соседние перестановки были бы максимально непохожими друг на друга. Алгоритм Нарайяны соответствует первому критерию, но не соответствует второму. Алгоритм получения новой перестановки шифра RC4 (уже в режиме генерирования нового байта гаммы, а не создания начальной перестановки по ключу) соответствует второму критерию, но не соответствует первому. Я слегка изменил RC4, чтобы он выдавал больше уникальных перестановок, но 100%-ого результата всё равно не достиг. Кто-нибудь из здесь присутствующих знает что-то, что могло бы соответствовать сразу обоим предъявленным критериям? Спасибо.

#cryptocurrency #cryptography #programming #russian

0

15.08.2021

18 ответов

42 просмотра

Fido Retano Автор вопроса

То есть, один начинает с "1234", а второй с "4321"?

0

15.08.2021

Vladimir Cherepanov

Да, но я не уверен, что они всегда будут получаться "максимально непохожими"

0

15.08.2021

Fido Retano Автор вопроса

если каждая копия алгоритма Нарайяны пройдёт только половину своего пути и их выводы чередовать в один общий поток, то любые две соседние перестановки скорее всего таки будут сильно непохожими. Однако я теперь понял, что нужно вводить третий критерий: непредугадываемость следующей перестановки до момента её фактического появления. То есть, нужно ещё что-то по типу псевдослучайности их появления. Ваше предложение соответствует предъявленным двум критериям, но от него придётся всё же отказаться.

0

15.08.2021

Vladimir Cherepanov

Тогда вам нужен какой-то алгоритм перемешивания, например, алгоритм Фишера-Йетса

0

15.08.2021

Fido Retano Автор вопроса

Не слышал о таком. Сейчас буду читать.

0

15.08.2021

Vlad Roskov

а какая конечная цель? почему соседние перестановки должны быть непохожими может можно чёто придумать отталкиваясь от задачи

0

15.08.2021

Fido Retano Автор вопроса

Увы, но именно этот алгоритм не подходит, так как уникальность получаемых перестановок зависит только от псевдослучайности числовых последовательностей и никак не зависит от предыдущей перестановки. Нужно что-то самодостаточное, как RC4.

0

15.08.2021

Fido Retano Автор вопроса

Вот представьте себе алгоритм Диффи-Хелмана, который при правильно подобранных параметрах сгенерит все числа, не превышающие простой модуль, ни разу их не повторив. Вот нужно тоже самое, но генерящее перестановки.

0

15.08.2021

Fido Retano Автор вопроса

Сейчас напишу.

0

15.08.2021

Vladimir Cherepanov

Вы про формулу g^x (mod p), которая сгенерит все числа от 1 до p?

0

15.08.2021

Vladimir Cherepanov

Я не очень понимаю, что это значит. Как без псевдослучайности выполнить этот критерий: "непредугадываемость следующей перестановки до момента её фактического появления"? Если мы знаем перестановку и алгоритм, при этом алгоритм детерминированный, мы можем посчитать следующую

0

15.08.2021

Fido Retano Автор вопроса

Да.

0

15.08.2021

Fido Retano Автор вопроса

Да, можем посчитать, как, например, значение хеш-функции. Но не должно быть возможности сказать, хотя бы в какой части диапазона N! она будет до её подсчёта.

0

15.08.2021

Fido Retano Автор вопроса

Эээээ... Не знаю. Может быть. :-))) Бент-функции я как-то раз пытался осилить, но так и не осилил.

0

15.08.2021

Vlad Roskov

ну типа, достаточно же сделать маппинг номер→перестановка

0

15.08.2021

Pablo K

А нельзя ли взять (kx + b) mod n! и алгоритм получения перестановки по номеру?

0

28.08.2021

Fido Retano Автор вопроса

Вы имеете в виду получение перестановки по номеру в лексико-графическом порядке? (http://neerc.ifmo.ru/wiki/index.php?title=%D0%9F%D0%BE%D0%BB%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D0%B0_%D0%BE%D0%B1_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D1%83_%D0%B8_%D0%BE%D0%B1%D1%8A%D0%B5%D0%BA%D1%82%D0%B0_%D0%BF%D0%BE_%D0%BD%D0%BE%D0%BC%D0%B5%D1%80%D1%83)

0

30.08.2021

Vladimir Cherepanov · Accepted Answer

Vladimir Cherepanov

Можно запустить два алгоритма Нарайяны навстречу друг другу, на i-ой генерации брать вывод первого или второго, в зависимости от четности i

0

15.08.2021

377 похожих чатов

Добрый вечер! Ищу генератор перестановок из N элементов, который бы,

18 ответов

Похожие вопросы