Die beste Größe eines RSA Moduls hängt von den eigenen Sicherheitsanforderungen ab. Je größer der Modul, desto sicherer und langsamer ist das Verfahren. Die Länge des Moduls sollte zuerst von der Überlegung abhängen, wieviel die eigenen zu schützenden Daten wirklich Wert sind und dann von der Überlegung, wie mächtig die potentiellen Feinde sind.
Ein guter Überblick über die Sicherheit, die von einer bestimmten Modullänge gewonnen werden kann, findet sich bei Rivest [Riv92a]. Diese Stelle behandelt zwar diskrete Logarithmen, betrifft jedoch RSA genauso. Eine tiefergehende Studie der RSA Schlüssellängen steht in einer Arbeit von Odlyzko [Odl95]. Diese Arbeit bestimmt die Sicherheit von RSA Schlüssellängen anhand der 1995 verfügbaren Faktorisierungstechniken und der Möglichkeit, Rechenleistung aus großen Computernetzen zusammenzuschalten. Eine spezielle Untersuchung [Rob95d] der Sicherheit eines 512 bit Schlüssels zeigt, daß dieser mit weniger als 1Mio. US$ Aufwand in 8 Monaten 1997 zu faktorisieren ist. Es wird angenommen, daß 512 bit Schlüssel nicht länger hinreichende Sicherheit im Zeitalter der neuen Faktorisierungsmethoden und der verteilten Rechentechnik leisten können. Solche Schlüssel sollte nicht nach 1997 or 1998 eingesetzt werden. Die RSA Laboratorien empfehlen 768 bit für den privaten Gebrauch, 1024 bit für den geschäftlichen Gebrauch und 2048 bit für wirklich wichtige Schlüssel wie die einer Zertifikationsinstanz (siehe Frage 123) Ein 768-bit Schlüssel sollte bis ins Jahr 2004 benutzbar sein.
Der Schlüssel eines einzelnen Nutzers kann nach einer gewissen Zeit verfallen, bspw. nach 2 Jahren (siehe Frage 118). Das gestattet es, Schlüssel regelmäßig zu wechseln und einen bestimmten Sicherheitslevel zu halten. Vor dem Verfall sollte der Nutzer einen neuen Schlüssel generieren, der etwas größer ist, als der Alte, um den gewachenen Rechengeschwindigkeit der letzten 2 Jahre etwas entgegenzusetzen. Die RSA Laboratorien veröffentlichen regelmäßig neue Empfehlungen über die Schlüssellänge.
Jeder Nutzer sollte ich klarmachen, daß die angegeben Zeiten zum Brechen von RSA durchschnittliche Zeiten sind. Mit großem Aufwand ist es möglich, viele tausend RSA Module gleichzeitig anzugreifen, um einen in akzeptabler Zeit zu brechen. Obwohl die Sicherheit jedes Einzelschlüssels hoch ist, kann es einem Angreifer immer gelingen, mit viel Glück einen Schlüssel schnell zu brechen.
Die Verdopplung der Schlüssellänge (siehe Frage 9) vervierfacht die Zeit der Operationen mit dem öffentlichen Schlüssel (Verschlüsselung und Unterschriftenprüfung) und verachtfacht die Zeit der Operationen mit dem privaten Schlüssel (Entschlüsselung und Unterschreiben) unter der Annahme der typischen RSA Implementierung. Der Grund für die schnellerer Abarbeitung der Operationen mit dem öffentlichen Schlüssel liegt darin, daß der öffentliche Exponent fest bleibt, während der Modul sich vergrößert, während jedoch der private Exponent linear mitwächst. Die Zeit zur Schlüsselerzeugung versechszehntfacht sich bei Verdoppelung der Schlüssellänge, jedoch wird diese Operation i.d.R. selten ausgeführt. Für andere Vergrößerungen der Schlüssellängen gelten gleichartige Berechnungen.