Das Hauptproblem bei symmetrischen Verschlüsselungen ist nicht die Sicherheit der eingesetzten Verfahren, sondern der Austausch der Schlüssel. Wenn zwei Kommunikationspartner einmal die Schlüssel ausgetauscht haben, kann der betreffende Schlüssel für sicheren Datenaustausch benutzt werden. Die Frage ist nur, auf welchem sicheren Wege der Schlüsselaustausch stattgefunden hat. Wahrscheinlich wäre es für einen Angreifer viel leichter, den Schlüssel abzufangen, als alle möglichen Schlüssel im key space auszuprobieren (eine Erfahrung, die die Deutschen mit ihrer Enigma auch machen mußten). Ein weiteres Problem ist die Anzahl der insgesamt benutzten Schlüssel. Wenn die Zahl der Leute, die miteinander kommunizieren wollen, n beträgt, so werden insgesamt n(n-1)/2 Schlüssel (also beispielsweise 45 Schlüssel bei 10 Leuten) benötigt. Dies mag für eine geringe Personenzahl noch angehen, läßt sich aber bei großen Personengruppen nicht mehr handhaben.
Der Sinn von Verschlüsselungsverfahren mit öffentlichem Schlüssel besteht darin, daß das Sicherheitsrisiko beim gegenseitigen Schlüsselaustausch gänzlich vermieden wird. Jeder hat ein Schlüsselpaar mit einem öffentlichen und einem geheimen Schlüssel. Zum Verschlüsseln einer Nachricht benutzt man den öffentlichen Schlüssel des Empfängers, und nur dieser kann sie mit seinem geheimen Schlüssel wieder entschlüsseln.
Dadurch löst man das Problem des Schlüsselaustausches bei symmetrischer Verschlüsselung. Sender und Empfänger brauchen sich nicht auf einen Schlüssel zu einigen. Erforderlich ist nur, daß der Absender eine Kopie des öffentlichen Schlüssels des Empfängers besitzt. Dieser eine öffentliche Schlüssel kann von jedem benutzt werden, der mit dem Empfänger kommunizieren will. Somit sind dann insgesamt nur n Schlüsselpaare notwendig, wenn n Leute verschlüsselt miteinander kommunizieren wollen.
Die Verschlüsselung mit öffentlichem Schlüssel beruht auf sogenannten Falltür-Algorithmen bzw. Einweg-Hashes. Das sind Funktionen, die leicht zu berechnen sind, doch umgekehrt ist es praktisch unmöglich, aus dem Ergebnis dieser Hash-Funktionen wieder den Ausgangswert zu berechnen. So ist es z.B. leicht, zwei Primzahlen miteinander zu multiplizieren, um eine Nichtprimzahl zu erhalten, es ist aber schwer, eine Nichtprimzahl in ihre Primfaktoren zu zerlegen. Falltür-Algorithmen sind ähnlich, haben aber eine ``Falltür''. Das heißt: Wenn ein Stück Information bekannt ist, kann man leicht die Umkehrfunktion berechnen. Wenn Sie z.B. eine aus zwei Primfaktoren bestehende Zahl haben, so macht die Kenntnis eines der Faktoren es leicht, den zweiten zu berechnen.
Angenommen, ein Verfahren beruhe auf der Bildung einer Zahl aus Primfaktoren, dann enthält der öffentliche Schlüssel eine aus zwei großen Primfaktoren zusammengesetzte Zahl, und das Verschlüsselungsverfahren benutzt dann diese Nichtprimzahl zum Verschlüsseln der Nachricht. Das Verfahren zum Wiederherstellen dieser Nachricht erfordert dann die Kenntnis der Primfaktoren. So ist die Entschlüsselung möglich, wenn Sie den privaten Schlüssel haben, der einen der Faktoren enthält, ist aber praktisch unmöglich, wenn Sie ihn nicht haben.
Wie bei guten symmetrischen Verschlüsselungsverfahren beruht die Sicherheit auch bei Public-Key-Verfahren ausschließlich auf dem Schlüssel. Aus diesem Grund kann man die Schlüsselgröße als ein Maß für die Sicherheit des Systems nehmen. Allerdings kann man die Größe eines symmetrischen Schlüssels nicht mit der von Public-Key-Verfahren vergleichen, um Rückschlüsse auf deren relative Sicherheit ziehen zu können. Bei einem Brute-Force-Angriff auf eine symmetrische Verschlüsselung mit einer Schlüsselgröße von 80 Bit muß der Angreifer bis zu 280-1 Schlüssel ausprobieren, um den richtigen Schlüssel zu finden. Bei einem Brute-Force-Angriff auf eine Public-Key-Verschlüsselung muß der Angreifer bei einer Schlüsselgröße von 512 Bit eine in 512 Bit codierte (bis zu 155 Dezimalstellen umfassende) Nichtprimzahl in ihre Primfaktoren zerlegen. Der Rechenaufwand für den Angriff weist je nach der Verschlüsselung gewaltige Unterschiede auf. Während 128 Bit für symmetrische Schlüssel ausreichen, werden angesichts der heutigen Verfahren zur Faktorisierung grosser Zahlen für die meisten Zwecke öffentliche Schlüssel mit 1024 Bits empfohlen.