Per firmare solo, una chiave RSA a 512 bit dovrebbe resistere almeno a qualche giorno, probabilmente a poche settimane, anche contro determinati aggressori. Questo è ancora "ragionevole" finché si verifica la firma "presto". Puoi immaginare che dal momento in cui la chiave pubblica è stata resa pubblica, hai pochi minuti, al massimo delle ore di sicurezza, dopo di che devi considerare la chiave come scaduta e rifiutare di fidarti delle firme calcolate con quella chiave.
Però trovo il tuo caso d'uso un po 'dubbioso. Generare le chiavi RSA sarà piuttosto costoso per quanto riguarda il calcolo di una firma. Se ti preoccupi della dimensione della firma, dovresti esaminare DSA o le sue varianti di curve ellittiche. ECDSA con una curva a 160 bit utilizzerà firme a 320 bit (molto più piccole delle firme a 512 bit per RSA-512) pur essendo sostanzialmente più strong (ECDSA con una curva a 160 bit è ancora oltre la tecnologicamente fattibile) e sarà ancora competitivo per quanto riguarda l'utilizzo della CPU.
Inoltre, la parte più difficile della crittografia asimmetrica è la distribuzione delle chiavi (questo è ciò che è PKI ); se generi più chiavi, rendi questa parte solo più difficile.