Two mathematical security aspects of the RSA cryptosystem : signature padding schemes and key generation with a backdoor
Geneviève Arboit · 2008
This work presents mathematical properties of the RSA cryptosystem. The topics of backdoors and padding algorithm are developped. For padding schemes, we give a practical instantiation with a security reduction. It is based on the compression function of SHA-1 without any chaining function. Our solution has the advantage over the previous one of removing the relation of the output length of the compression function to the length of the RSA modulus. For backdoors, improvements on definitions, existing algorithms as well as extensions of existing theorems are shown. The definitions pertaining to backdoored key generators are improved as to make their analysis uniform and comparable. New algorithms are presented and compared to existing ones as to show improvements mainly on their running time, the indistinguishability of the keys produced, and that some of these new algorithms are, for all practical purposes, the best that may be called asymmetric. Our theorem on the correctness (or completeness) of one of our better backdoored key generators is a generalization of a theorem of Boneh, Durfee and Frankel's on partial information on the decryption exponent.