Pseudorandom number generators for mobile devices: an examination and attempt to improve randomness

Abstract

This thesis examines the quality of pseudorandom number generation for cryptographic purposes in general and the generation of such numbers in a mobile device (Android phone), in particular, since we expected to find non-random properties in these. Initially, the need for random numbers for encryption purposes is discussed from a perspective of Information Warfare. Thereafter, ways of testing a bit string for random properties as well as some pseudorandom number generating algorithms are presented. This also includes the shrinking and the self-shrinking generator normally used to improve the random properties of the output m-sequence of linear feedback shift registers. A couple of possible attacks on pseudorandom number generators are also briefly presented. Finally, we generate and analyze some pseudorandom bit strings in three different ways using the NIST test suite, both before and after the self-shrinking generator has been applied to them. The strings generated by the Android phone passed the NIST test suite, and it is difficult to claim any improvement in random properties by applying the self-shrinking generator. On a bit string with poor random properties, however, the self-shrinking generator improves randomness from the perspective of linear dependency and complexity, but not from the perspective of bit frequency.