Rivest-Shamir-Adleman public key cryptosystems do not always conceal messages
Academic Article

Overview

Identity

Additional Document Info

Other

View All

Overview

abstract

To every pair p, q of distinct primes there correspond 9 positive integers x no larger than pq such that c mod (pq) for every odd positive integer c. Therefore these 9 messages x are unconcealable in any Rivest-Shamir-Adleman public key cryptosystem which has the product pq for its encoding modulus. There are, in fact, such cryptosystems which do not conceal any messages, and others which conceal less than 50% of all messages possible within them. These examples point up the need for effective criteria for evaluating the concealing power of any such cryptosystem. This paper treats these questions for a general square free encoding modulus m. It contains easy to use necessary and sufficient conditions that the function f(x) = xc be: 1. a permutation of the residue classes module m; 2. a derangement (i.e. a permutation without fixed points) of the collection of all the residue classes modulo m other than the unavoidably unconcealable ones. It also provides a construction of all such "deranging" exponents. 1979.