Rivest-Shamir-Adleman public key cryptosystems do not always conceal messages
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.
