Als Antwort auf dieses Dilemma präsentierten drei Wissenschaftler vom MIT in Boston im Jahre 1978 eine verblüffende Lösung [1]. Das nach den Autoren Rivest, Shamir und Adleman benannte RSA-Verfahren verwendet das Konzept des öffentlichen Schlüssels und zählt daher zu den Public Key Systems. Im folgenden sei der Einfachheit halber angenommen, der zu übertragende Klartext bestehe aus einer einzigen ganzen Zahl x (bei realen Anwendungen muß der Klartext zuvor als eine Folge von Zahlen dargestellt werden).
Abbildung 2 zeigt, wie die Kommunikationspartner Alice, welche die zu übertragende Nachricht x verfaßt hat und ihr Kommunikationspartner Bob, für den die Nachricht bestimmt ist, dabei vorgehen. Bob konstruiert auf Grundlage eines mathematischen Verfahrens drei Zahlen e, d und n mit der Eigenschaft (xemodn)d mod n = x. Auf deutsch: Wenn man x e-mal mit sich selbst malnimmt und dann das Ergebnis d-mal mit sich selbst malnimmt, kommt wieder x heraus. Alle Rechnungen erfolgen mit den Resten, die bei Division durch n entstehen, genannt modulo. Nun können die Zahlen n und e von Bob veröffentlicht werden für jeden potentiellen Sender der an ihn eine Nachricht schicken möchte. Verschlüsselt wird dann mit der für den Adressaten Bob konstruierten öffentlichenFunktiony : = encB(x) = xemodn, entschlüsselt wird vom Adressaten mit der nur ihm bekannten, aber sonst geheimenFunktionx : = decB(y) = ydmodn.
Als Beispiel seien n = 143, e = 47 und d = 23 genannt. Dann wird x verschlüsselt durch Bilden von y : = x47 mod 143, auf der Gegenseite wird y entschlüsselt durch Bilden von x : = y23 mod 143. In der Praxis werden die Zahlen n, e und d unter Verwendung 300-stelliger Primzahlen konstruiert und sind so gewählt, daß aus der Kenntnis von n, e und der verschlüsselten Nachricht y die Rekonstruktion von d und damit die Rekonstruktion von x in akzeptabler Rechenzeit nicht möglich ist. Ein abhörender Spion könnte daher die beobachtete Nachricht y erst in Jahrzehnten entschlüsseln.