Es gibt einige mögliche Interpretationen, was es heißt, RSA zu "brechen". Den meisten Schaden richtet eine Aufdeckung des privaten Schlüssels an; dies erlaubt dem Angreifer alle Nachrichten zu lesen und Unterschriften zu fälschen. Es drängt sich der Versuch auf, das öffentlichen Modul n in seine Primfaktoren p und q zu faktorisieren. Aus p, q und e (dem öffentlichen Exponenten) kann der Angreifer leicht d (den privaten Exponenten) und damit den privaten Schlüssel errechnen. Der schwierige Teil davon ist die Faktorisierung von n, davon hängt die Sicherheit von RSA ab. Tatsächlich ist jeder andere Weg, den privaten Exponenten d zu ermitteln der Faktorisierung von n in genau zwei Primfaktoren äquivalent: Aus e, d und n kann p und q berechnet werden, wenn bekannt ist, daß n aus genau zwei Faktoren besteht. Siehe Frage 47 und Frage 48 für den aktuellen Stand der Faktorisierung. Es ist bemerkenswert, daß Hardwareverbesserungen allein RSA nicht aufweichen, solange angemessene Schlüssellängen verwendet werden. Tatsächlich erhöhen Hardwareverbesserungen die Sicherheit von RSA. (Siehe Frage 47)
Ein anderer Weg RSA zu brechen, besteht darin, einen Algorithmus zur Berechnung der e-ten modularen Wurzel zu finden. Da c = me mod n ist, ist die e-te modulare Wurzel aus c bzgl. n gleich der Nachricht m. Dieser Angriff gestattet es jemandem Nachrichten zu entschlüsseln und Unterschriften zu fäschen, ohne den privaten Schlüssel kennen zu müssen. Es ist nicht bekannt, ob dieser Ansatz äquivalent zur Faktorisierung ist oder nicht. Es sind keine generellen Algorithmen bekannt, die RSA in dieser Weise gefährlich werden können. Jedoch gibt es Spezialfälle, bspw. eine Nachricht mehrfach mit dem gleichen kleinen Exponent verschlüsselt wurde, in denen es möglich ist, die Nachricht auszudecken.
Die obenstehenden Angriffe sind die einzigen bekannten Wege RSA so zu brechen, daß der Angreifer alle Nachrichten lesen und Unterschriften eines bestimmten Schlüssels fälschen kann. Es gibt weitere Methoden, die eine einzelne Nachricht aufdecken können, jedoch keine weiteren Nachrichten des selben Schlüsselpaares. Einige Leute haben untersucht, welche Teile einer Nachricht aus einem Chiffrat abgeleitet werden können [ACG84].
Der einfachste Angriff auf Einzelnachrichten ist das Erraten eines Klartextes. Ein Angreifer errät zu einem Chiffrat den Klartext und verschlüsselt ihn mit dem öffentlichen Schlüssel des Empfängers. Hat er völlig richtig geraten, stimmt seine Verschlüsselung mit dem Chiffrat überein. Um sich gegen diesen Angriff zu schützen, kann man einige zufällige Bits im Klartext unterbringen. Ein anderer Angriff auf eine Einzelnachricht entsteht dann, wenn jemand einen Text m an einige Leute verschlüsselt, die alle den gleichen kleinen öffentlichen Exponenten haben. (Bspw. e=3 und die Nachricht geht an drei Leute.) Weiß der Angreifer das, so kann er die Nachricht m über den Chinesischen Restsatz zurückgewinnen. Näheres zu diesem Angriff und zu Schutzmenchnismen dagegen findet sich bei Hastad [Has88]. Glücklicherweise genügt es, die Nachricht in nur wenigen Füllbits an die verschiedenen Empfänger zu verändern. Es gibt auch einige gewählte Chiffretext Angriffe (oder gewählte Klartext Angriffe für Unterschriftsfälschungen), in denen der Angreifer etwas Chiffretext erzeugt und diesen nach dem Entschlüsseln sich besorgt. Das gelingt bspw. wenn eine gefälschte Nachricht durch den Schlüsselinhaber entschlüsselt wird und dieser sich dann mit Zitaten beschwert. Davida [Dav82] und Desmedt und Odlyzko [DO86] geben weitere Beispiele.
Einen Überblick über diese und andere Angriffe auf RSA ist [KR95c] empfehlenswert.
Natürlich gibt es auch Angriffe, die nicht auf RSA selbst sondern auf eine unsichere oder fehlerhafte Implementation von RSA zielen; jedoch zählt dies nicht als ein "Brechen" von RSA selbst, da es keinen Schwachpunkt des RSA Algorithmusses ausnutzt. Wenn bspw. den privaten Schlüssel unsicher abspeichert, kann ihn der Angreifer auffinden. Es kann nicht deutlich genug gesagt werden, daß eine sicheres RSA Kryptosystem eine sichere Implementierung voraussetzt. Mathematische Sicherheit ist wichtig, wie die Wahl der richtigen Schlüssellänge, aber nicht hinreichend. Die meisten praktischen erfolgreichen Angriffe zielen auf unsichere Implementationen und auf die Schlüsselverwaltung eines RSA Systems. In Abschnitt III befassen wir und mit den Fragen einer sicheren Schlüsselverwaltung in einer RSA Umgebung.