Angenommen, Sie haben sich zwei große Primzahlen, also natürliche Zahlen, die nur durch Eins und durch sich selbst teilbar sind, verschafft, die nur Sie selbst kennen. "Groß" bedeutet hier, dass sie einige hundert Stellen haben. Dann wird das Produkt der beiden Zahlen berechnet.
Seien die Primzahlen mit p und q bezeichnet, das Produkt p·q mit n. Bemerkenswerterweise sind dann p und q in der Zahl n auf praktisch unauffindbare Weise versteckt. Heute ist nämlich kein Verfahren bekannt, die Faktoren p und q in realistischer Zeit aus n zu rekonstruieren. Auch nicht, wenn die besten Computer der Welt mehrere Jahrtausende rechnen würden.
Diese Tatsache macht man sich für die Verschlüsselung von Daten zunutze. Sie verwendet einen Satz der Zahlentheorie, der schon vor mehreren hundert Jahren bekannt war: Man kann eine gegebene Zahl unter Verwendung von n so manipulieren, dass diese Veränderung nur dann rückgängig gemacht werden kann, wenn man p und q kennt. Wenn Ihnen also jemand eine vertrauliche Nachricht schicken soll, so müssen Sie dem Absender nur die Zahl n mitteilen und ein Verfahren vorschreiben, wie die Nachricht mit Hilfe von n zu verändern ist (dazu muss die Nachricht vorher in eine Zahl umgewandelt werden, was aber keine Schwierigkeit darstellt). Das Ergebnis soll Ihnen der Absender schicken. Niemand außer Ihnen kann dann mit der verschlüsselten Nachricht etwas anfangen; wegen der Kenntnis von p und q können nur Sie die Nachricht entschlüsseln.
Revolutionär an diesem Verfahren ist, dass es praktisch unter den Augen der Öffentlichkeit stattfinden kann, jeder darf sich das zum Verschlüsseln wichtige n und die verschlüsselte Nachricht ansehen; man spricht von einem "öffentlichen Schlüssel".
Es ist sehr erstaunlich, dass dieses Verfahren heute täglich millionenfach bei der Übermittlung vertraulicher Information u. a. im Internet eine entscheidende Rolle spielt.
Der Mathematiker Dr. Michael Laska erklärt für Laien gut verständlich die mathematischen Hintergründe dieses wichtigen Verfahrens.