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

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.

author list (cited authors)

  • Blakley, G. R., & Borosh, I.

citation count

  • 35

publication date

  • January 1979