Se il fattore principale per te e' l'autenticazione (Ovvero garantire agli altri che veramente tu ad inviare i messaggi) allora potresti criptare i msg con la chiave privata, inviarli e fare in modo che i destinatari li decriptino con la chiave pubblica. Ovviamente in questo caso viene a mancare la segretezza dei dati visto che la chiave per decriptare e' pubblica. Per avere una soluzione che offra sia segretezza che autenticazione servirebbe qualcosina di piu' "sofisticato"...
la soluzione è usare un firma digitale, con RSA potresti usare MD5, l'algorimto cosiste nel inserire la chiave privata e creare la firma, succesivamente con la chiave pubblica si verifica la firma.

L'algoritmo si chiama MD5withRSA.

EDIT:

Esempio:
Codifica
Messaggio originale----------------Impronta con MD5
------------------------------------------------------------|
------------------------------------------------------------|
Chiave privata-------------------Algorimo di firma----> Firma

Decodifica
Messaggio ricevuto-----------Algoritmo impronta----> Impronta
--------------------------------------------------------------------------------|
------------------------------------Chiave pubblica-------------------uguali?
---------------------------------------|-----------------------------------------|
Firma digitale--------------- Algoritmo firma--------------> Impronta