STUDY OF NEXT BIT/SYMBOL PREDICTOR ALGORITHMS FOR CRYPTOLOGICAL APPLICATIONS

Abstract

The security of many cryptographic systems depends upon the generation of unpredictable quantities. Examples include the secret key in the DES encryption algorithm the primes p, q in the RSA encryption and digital signature schemes, the private key an in the DSA, and the challenges used in challenge-response identification systems[1]. In all these cases, the quantities generated must be of sufficient size and be "random" in the sense that the probability of any particular value being selected must be sufficiently small to preclude an adversary from gaining advantage through optimizing a search strategy based on such probability. For example, the key space for DES has size 2'G. If a secret key k were selected using a true random generator, an adversary would on average have to try 255 possible keys before guessing the correct key k. If, on the other hand, a key k were selected by first choosing a16-bit random secret s, and then expanding it into a 56-bit key k using a complicated but publicly known function f, the adversary would on average only need to try 2' possible keys (obtained by running every possible value for s through the function). Prediction is important in communication, control, forecasting, investment, molecular biology, security, and other areas. We understand how to do optimal prediction when the data model is known, but there is a need for designing universal prediction algorithms that will perform well no matter what the underlying probabilistic model is. Universal prediction was subject of extensive research over the last 50 years; it dates back to Shannon