25 ms·
You can draw the cards in a random order by using the output of an accumulator fed to a block cipher as an index. The fixed output size of a block cipher does e
by ZephyrP 7y ago
You can draw the cards in a random order by using the output of an accumulator fed to a block cipher as an index. The fixed output size of a block cipher does entail extra work in filtering numbers outside the range you'd like, just as you would with an LFSR. (as a direct power of 2, you could directly use an LFSR or some ECB-mode block ciphers as if it were format-preserving, but that is "coincidence").
You can produce an exact random permutation with a Feistel network for any number, in this case selecting every number between 0 and 2^64 exactly once, with no appreciable space requirements.
procedure feistel(input) {
result = input;
h = 2<<32;
for (let i = 0; i < 8; i++) {
l = (input / h)|0;
r = input % h;
temp = r;
fn = (r + i) % h;
r = (l + fn) % h;
l = temp;
result = h * l + r;
}
return result;
}
- tripzilch 7y agoIs that code correct? Why do you overwrite `result` every step of the loop if you only use it at the end?
- ZephyrP 7y agoGood eye, `input` should be replaced with `result` when building the subkeys within the loop. Here's a working implementation: function feistel(ctr, lr, ll) { let result = ctr; for (var i = 0; i < 8; i++) { let l = (result / ll)|0; let r = result % ll; let temp = r; // alter round fn's multiplier & increment accordingly. let fn = (r * 16807 + i) % lr; r = (l + fn) % lr; l = temp; result = lr * l + r; } return result; } let rsize = 8; let outputs = new Set(); for(let i = 0; i < rsize * rsize; i++) outputs.add(feistel(i, rsize, rsize)) for(let i = 0; i < rsize * rsize; i++) if (!outputs.has(i)) console.log('failure: ', i);
- deleted 7y ago[deleted]