Как задать паролем перемешивание 32 элементов?

Question

[Сергей Соколов]

N элементов (до 32) надо перемешать между собой. Например:

было:  0,1,2,3,4,5,6,7
стало: 0,4,2,6,1,5,3,7

Как однозначно из строки (пароля) любой длины получать этот порядок перемешивания?

Т.е., например, из строки и длины получать порядок:

f( 'суперпароль', 8) -> [0,4,2,6,1,5,3,7]
f( 'asdf123', 8)     -> [1,3,2,7,5,0,4,6]

N.B. Из комбинаторики известно, что 32 элемента можно перемешать 32! числом способов: довольно большое число порядка 2.63*10³⁵.

Comments

[Алексей]

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

[Сергей Соколов]

Алексей, это вы предложили Fisher–Yates shuffle.

В моей задаче порядок должен определяться из «пароля».

[vaut]

Пароль -> хеш от пароля (можно посолить но это не обязательно) -> длинное псевдослучайное число -> любым удобным способом превращаем его в перестановки.

[Сергей Соколов]

vaut, под вечер пятницы я затупил с моментом «любым удобным способом превращаем его в перестановки»

[Денис Загаевский]

Зачем?

[Сергей Соколов]

Денис Загаевский, «нет времени объяснять» : )

[vaut]

Сергей Соколов, что нибудь вроде:
рубим число на N одинаковых частей, хвост просто выкинем. (N количество элементов в массиве)
Берем остаток от деления первой части на N это у нас будет первый элемент.
Второй остаток от деления второй части на N-1 и т.д.

Внимание, я не уверен что у нас будет нормальное распределение....

Answer 1

[Mercury13]

Если не нужна криптостойкость, то…
1. Преобразовать (однозначно) в очень длинное число.
2. Получаем такие части этого числа.
• Остаток от деления на 32
• Неполное частное на 32, затем остаток на 31
• Неполное частное на 32·31, затем остаток на 30
• Неполное частное на 32·31·30, затем остаток на 29…
На словах страшно, алгоритм простейший.
3. Из 31 числа — первое от 0 до 31, второе от 0 до 30, последнее 0 или 1 — легко получить перестановку.

Если криптостойкость всё же нужна — придётся пароль «посолить» до достаточной длины и зашифровать чем-то.

Comments

[Сергей Соколов]

Спасибо! Идея с последовательным отбором из 32, из 31, ... – то, что надо!

Answer 2

[Ivan Bogachev]

N элементов (до 32)....однозначно из строки (пароля) любой длины

Думаю можно сделать это с использованием sha-256 (для 32 элементов в самый раз):

let permutation = [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31];

sha256.array('суперпароль').forEach((n, i) => {
    let j = n % (permutation.length - i) + i;
    
    [permutation[i], permutation[j]] = [permutation[j], permutation[i]];
});

console.log(permutation); // [19, 30, 25, 16, 23, 8, 11, 27, 13, 6, 4, 26, 21, 28, 24, 14, 2, 5, 15, 18, 10, 0, 7, 22, 31, 9, 17, 29, 20, 3, 12, 1]

codepen