Solo la crittografia end-to-end, come suggerisce pepe, può offrire qualcosa di significativo, e comunque non ti salverà in casi come messaggi vocali, ecc.
Inoltre, il "rooting / jailbreaking" del telefono potrebbe non essere una domanda importante se preoccupati delle installazioni illegali del software lato client. Il rooting del telefono può portare ad aprirlo allo sfruttamento, se non è attento (a volte lascia aperto il demone ssh con la password predefinita), ma in tal caso potresti essere in grado di installare il software di sicurezza solo dopo averlo effettuato il rooting. Il recente exploit per iPhone / iPad lo dimostra: si avvale di un errore in un font che analizza il routing nel software dell'iPhone mentre apre un'accurata costruzione File PDF e utilizza questo errore per ottenere l'accesso root. Il fatto è che dopo lo sfruttamento, puoi applicare una patch per l'errore in modo che nessuno possa sfruttare il tuo dispositivo a tua insaputa se ti capita di aprire un PDF dannoso. Senza il jailbreak del dispositivo non è possibile installare la patch (non è ancora ufficiale).
Gli operatori telefonici (o le agenzie segrete) hanno l'autorità e i mezzi per spingere e installare software sul dispositivo a tua insaputa. Ma non sono solo loro, guarda qui e here per esempio. È possibile inviare aggiornamenti software e firmware a qualsiasi telefono: non è necessario che sia "semplice" o "non smartphone".
Un altro interessante factoid: i log delle chat tra Bradley Manning e Adrian Lamo che Wired recentemente rilasciato contenere più riferimenti a intercettazioni telefoniche da parte di agenzie segrete, ad esempio che ci sono volute 50 persone NSA e 6 mesi per capire come toccare l'iPhone. La parte più interessante è che le intercettazioni telefoniche sono qualcosa comunemente fatto e non devono ottenere un mandato o pensare ai diritti alla privacy mentre lo fanno perché non presentano i dati sulle intercettazioni come prove in tribunale per essere contestati - usano solo i dati per ottenere conduce ad altre prove.