Die Geschwindigkeit und die Schlüssel-, Chiffrat- bzw. Signaturlängen von Public-Key-Verfahren stellen sich praktisch als besondere Herausforderung heraus. In diesem Kapitel werden die Aufwände für die RSA-Verfahren (Verschlüsselung und Signatur) genauer untersucht. Weiterhin werden Möglichkeiten zur Optimierung, die praktisch eingesetzt werden, vorgestellt und genauer analysiert. Die effiziente Erzeugung von Schlüsselpaaren sowie Anforderungen an Schlüsselpaare, um die gewünschten Sicherheitseigenschaften gewährleisten zu können, werden hier beleuchtet. Zentral ist hierbei die Aufgabe, effizient sehr große Primzahlen zu finden. Insbesondere wird dabei auf das Faktorisierungsproblem im Kontext der RSA-Verfahren und deren Schlüsselerzeugung eingegangen. Beispielhaft werden bekannte Angriffe bei nicht sorgfältig erzeugtem Schlüsselmaterial gezeigt.