Distributed programming paradigms with cryptography applications

In 1976, Diffie and Hellman introduced the idea of a public-key cryptosystem. Subsequently, Rivest, Shamir and Adleman proposed the first example of a public-key cryptosystem, now known as the RSA cryptosystem. Despite the advantages of a public-key cryptosystem, RSA has been slow to gain acceptance for practical use. This is primarily due to the large computational requirements of RSA enciphering and deciphering. Since speed is the main barrier to the use of RSA in practical systems, numerous simplifications and optimizations have been proposed in order improve the speed of RSA enciphering and deciphering. We show how to speed up several applications related to the RSA cryptosystem by the use of parallelism. We address the problems of prime generation for RSA key selection, RSA modulus factorization, and RSA enciphering and deciphering. To make parallel RSA enciphering possible, we propose a new mode of operation that preserves many of the important properties of the conventional RSA mode of operation, but does not serialize the enciphering process. We also propose a new algorithm to generate deterministically certified primes. The execution time of the algorithm is comparable to that of the conventional probabilistic prime certification algorithm, and the algorithm is amenable to a parallel implementation. To develop our distributed implementations, we use a methodology developed by Per Brinch Hansen, based on distributed programming paradigms. A generic program implements the control structures of a programming paradigm, but does not implement specific computations for any particular application. Subsequently, the generic program can be used to implement any algorithm that fits the control structure of the paradigm. Implementation of a particular algorithm is done by simple substitution of algorithm-specific data types and procedures. We introduce two programming paradigms relevant to public-key cryptography applications, and use generic programs for the paradigms to implement efficient distributed programs for those applications. Our work demonstrates that the methodology can be successfully used to simplify the development of distributed implementations of scientific problems. As an interesting result of our work, we find that prime generation is an application for which non-deterministic communication substantially improves parallel efficiency