Das mit dem Public Key ist schon mal ein guter Ansatz. In der Regel benutzt man Public Key Verfahren aber nur um einen sogenannten Session Key auszutauschen, welcher dann für das verschlüsseln der eigentlichen Daten benutzt wird.
Es kommen also zwei Verfahren zum Einsatz, einmal asymetrische Verschlüsselung (z.B. RSA) und einmal symetrische Verschlüsselung ( z.B. DES, AES). Die asymetrische Verschlüsselung ist recht zeitaufwändig und wird desshalb nur zum Schlüsselaustausch benutzt. (siehe z.B. SSL)
Für allgemeine Infos rund um Verschlüsselung und deren Knacken gibt es bei dem
CrypTool von der Deutschen Bank.
MfG