In this paper we investigate the security of the server aided RSA protocols RSA-S1 and RSA-S1M proposed by Matsumoto, Kato and Imai resp. Matsumoto, Imai, Laih and Yen. We prove lower bounds for the complexity of attacks on these protocols and show that the bounds are sharp by describing attacks ... more >>>