RSA:n murtaminen eroaa symmetristen kryptausmenetelmien murtamisesti oleellisesti sinä, että RSA:ta vastaan suunnatut hyökkäykset suunnataan avaimeen eikä kryptattuun viestiin.
Teoriassa avaimen murtaminen tapahtuu hyvin yksinkertaisesti.
Julkiseen avaimeen kuuluva avaimen yhteinen osa jaetaan tekijöihin,
jonka tuloksena saadaan siis avainparin generoinnissa luodut alkuluvut
ja
. Kun avaimen julkinen osa on tiedossa voidaan julkinen osa
laskea erittäin helposti.
RSA:n turvallisuus perustuu siis siihen, että kokonaislukujen tekijöihinjako on aikavaativuudeltaan erittäin vaikea tehtävä. Tekijöidenjaon vaatima aika kasvaa eksponentiaalisesti suhteessa tekijöihinjaettavan luvun kokoon. Kuitenkaan ei voida todistaa, etteikö algoritmia, joka jakaa luvun tekijöihinsä plynomaalisessa ajassa olisi olemassa. Ranskalainen François Morain on väitöskirjassaan [MORA90] tutkinut suurten kokonaislukujen faktorointimenetelmiä, ja onkin saavuttanut merkittäviä tuloksiä. Hän on pystynyt nopeuttamaan tekijöihinjakoa huomattavasti, mutta samalla tullut tulokseen, jonka mukaan polynomaalisen faktorointialgoritmin löytyminen ei tunnu todennäköiseltä. Morainin alkulukututkimukset perustuvat elliptisten funktioiden ominaisuuksien tutkimiseen. Menetelmät ovat erittäin monimutkaisia, eikä niihin paneutuminen tässä yhteydessä ole tarkoituksenmukaista. Riittänee, kun todetaan, että vastaavilla analyysimenetelmillä on aiemmin tutkittu mm. yleistä muotoa olevan viidennen asteen polynomin nollakohtien etsimistä.
Nykytiedon mukaan RSA on siis turvallinen algoritmi, mikäli käytetty salausavain on riittävän pitkä. Nykyisillä tietokoneilla noin 400-bittinen avain on aivan riittävä, mutta hieman pidempikään ei tietenkään ole pahasta. Ylettömän pitkän RSA-avaimen käyttö ei ole tarkoituksenmukaista sikäli, että tiedon kryptaus ja tällaisella avaimella salatun tiedon avaus hidastuu entisestään suoraan verrainnollisesti avaimen koon kasvattamiseen. Myöskin RSA-avaimen generointi on sitä hitaampaa, mitä pidempiä avaimia generoidaan.
Tietokoneiden laskentakapasiteetin lisääntyessä on avainten pituutta luonnollisesti kasvatettava vastaavasti, mutta lähivuosikymmeninä tuskin kehitetään tietokonetta, joka pystyisi brute force menetelmällä murtamaan esim. 1024-bittisen RSA-avaimen. Luonnollisesti on mahdollisuuksien rajoissa, että kokonaislukujen tekijöihinjakoon keksitään nopea algoritmi, mutta sekään mahdollisuus ei tunnu kovin todennäköiseltä. Tietenkin voidaan esittää salaliittoteorioita, joiden mukaan jollain tiedusteluorganisaatiolla on hallussaan tällainen nopea faktorointialgoritmi, jolla se pystyy murtamaan kaikki haluamansa RSA-avaimet (vrt. Enigma), mutta sekin mahdollisuus tuntuu hieman kaukaa haetulta, koska keksintö olisi varmaankin peräisin jostain yliopistosta, josta se lähes vuorenvarmasti olisi vuotanut julkisuuteen.