A modification of the RSA public-key encryption procedure (Corresp.)

The Rivest, Shamir, and Adleman (RSA) public-key encryption algorithm can be broken if the integer <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> used as the modulus can be factored. It my however be possible to break this system without factoring <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> . A modification of the RSA scheme is described. For this modified version it is shown that, if the encryption procedure can be broken in a certain number of operations, then <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">R</tex> can be factored in only a few more operations. Furthermore, this technique can also be used to produce digital signatures, in much the same manner as the RSA scheme.