Skip to content

Latest commit

 

History

History
55 lines (34 loc) · 2.82 KB

arxseq.md

File metadata and controls

55 lines (34 loc) · 2.82 KB
Raw

Let me introduce a PRNG based on an ARX structure, that can be upgraded to a CSPRNG.

Inside a buffer of 8 words, 64-bit in this case, a step transformation operates on four consecutive of these words, wrapping as necessary at the end of the buffer to the beginning.

The basic step is (p is the first position to mix, r1 and r2 are rotation distances):

    step(p,r1,r2) 
        p+2 := p+2 xor p+0
        p+3 := p+3 xor p+1
        p+2 := p+2  +  p+1
        p+3 := p+3  +  p+0
        rotate_left(p+2, r1)
        rotate_left(p+3, r2)

and the whole mixing for 3 rounds is:

    process_input(output[8], input[8])
        copy input into output
        for 3 rounds
            step(output+0, 22,41) // 16+6 40+1
            step(output+2, 20,43) // 16+4 40+3
            step(output+4, 18,45) // 16+2 40+5
            step(output+6, 16,47) // 16+0 40+7 // output+8=output+0, output+9=output+1
        end for

As all the steps and rounds can be reversed without ambiguity it's a permutation, so each input state gives rise to a different output state, the input state filled with zeros outputs all zeros and must be avoided. This ensures that the period length of this generator is 2^512-1 blocks of 64 bytes, if we use the input state as a counter starting from 1.

The input state can be configured as desired. In my own tests first 64-bit word is an incremental counter, and second 64-bit word a sequence selector. The rest is filled with zeros.

Furthermore, if we take contiguous values sized as powers of two, from 0 to 9, i.e. 1 to 512 bits, over the entire period each value is equidistributed. This is proved by the fact that the mixing is a permutation.

In a x64 processor able to execute two machine instructions each cycle if ordered properly, the cost of step() is 3 cycles, for 3 rounds and 4 calls, leads to 36 cycles to generate 64 bytes, resulting in 0.56 cycles/byte. This can be confirmed experimentally with little differences.

This generator passes TestU01's BigCrush battery of test, and PractRand up to 2^40 bytes.

A fast version is provided, with autofeedback of all but the first 64-bit word, in order to achieve a maximum throughput, but without proved equidistribution.

In order to go crypto more rounds are needed, and to define a more complex state. That of Salsa20 can be used, and the number of rounds discussed, taking into account that this arx mixer passes tests with 3 rounds and is 64-bit oriented, while others aren't.

Files are at https://github.com/danielnager/arxseq64.

An implementation can be found at: https://github.com/danielnager/arxseq64/raw/main/arxseq64_512_out.c this implementation outputs a pseudo random stream.

And a benchmarking tool at: https://github.com/danielnager/arxseq64/raw/main/arxseq64_512_bm.c

Daniel Nager daniel.nager@gmail.com