Mir scheint, du hast das Prinzip der asymmetrischen Verschlüsselung noch nicht ganz verstanden. Ich meine, irgendwo mal ein Video gesehen zu haben, wo das echt super erklärt war, finde es aber nicht mehr, sorry. Wikipedia gibt, soweit ich das beim Überfliegen beurteilen konnte, nicht viel her. Daher ein schneller Überblick von mir.
Der richtige Einsatz für ein Schlüsselpaar (also z.B. ein RSA-Key mit GnuPG erzeugt oder ein X.509-Zertifikat von einer CA) ist, dass du den Private-Key nur auf deinem Rechner hast und niemandem gibst, den Public-Key aber jedem geben kannst.
Man kann mit dem Public-Key Nachrichten verschlüsseln und die Signatur eines Dokumentes überprüfen.
Mit dem Private-Key kann man Nachrichten entschlüsseln und Dokumente signieren.
Anders ausgedrückt: Jeder kann dir mit deinem Schlüssel verschlüsselte Nachrichten schicken und nur du kannst sie lesen. Nur du kannst Nachrichten signieren und somit dem Empfänger zeigen, dass sie von dir kommt und nicht von einer Drittperson. Der Empfänger kann das prüfen.
Es ist also nicht so, dass du für dich und alle deine Kommunikationspartner Zertifikate erstellen musst, sondern, dass sich jeder ein Zertifikat erstellt. Du hast ja schon eins, deine Kollegen brauchen dann noch jeweils eines. Dann tauscht ihr eure Public-Keys aus. Bei GnuPG z.B. kann man diesen als Datei exportieren, verschicken und importieren. Wenn die richtige E-Mailadresse beim erstellen des Keys angegeben wurde, müsste gleich der richtige Key genutzt werden, wenn man eine Mail verschickt. Außerdem besteht die Möglichkeit, einen Schlüssel auf einen Keyserver hochzuladen, dann entfällt das manuelle tauschen. Wie das bei S/MIME mit X.509-Zertifikaten aussieht, weiß ich nicht, ich vermute aber, dass das ähnlich aussieht. Twingoteele in A#5 hat da was zu gesagt.
Daraus ergibt sich, dass sowohl Sender als auch Empfänger ein E-Mailprogramm mit Verschlüsselungsfunktion brauchen (oder ein Stanaloneprogramm wie in A#5 genannt), der Empfänger einer Nachricht ein Schlüsselpaar besitzt und dem Sender den Öffentlichen Schlüssel mitgeteilt hat.
Wie du gemerkt hast, ist es (zumindest mit GnuPG oder S/MIME) nicht möglich, einfach eine Nachricht mit einem generierten Schlüssel zu verschlüsseln und dem Empfänger zu ermöglichen, sie 'ohne großen Aufwand', sprich: ohne vorher die Public-Keys auszutauschen, zu entschlüsseln.
Ele