Analysis of efficient random permutations generation for security applications

In this paper, random permutation generation algorithms namely, Fisher-Yates algorithm, its variant Sattolo algorithm and Josephus algorithm are discussed. Both chaos and non-chaos based approaches have been analyzed and compared. Their efficiency has been tested against three criteria: no ideally fixed points, no un-separated pairs and shift factor greater than one third the degree of permutation. A random permutation algorithm should successfully satisfy the above criteria. Incorporating chaotic behavior increases the randomness of the generated permutation. Chaotic maps are used for the generation of key-dependent and deterministic random behavior. The ones chaos based are attracting more attention as they produce less predictive permutations. A slight change in input parameters prompt a significant change in the resulting outcome thereby making it suitable for security applications. The performance test has been done on samples consisting of 10000, 50000 and 100000 permutations. In each sample, every individual permutation has (I) 50000 elements (II) 100,000 elements. The experimental results demonstrate that the chaos-based approach outperforms other approaches and generates more efficient random permutations.