RSA:n teoriaa

Heidän kehittämänsä RSA-menetelmä perustuu siihen, että sopivasti valituilla kokonaisluvuila , ja pätee kaavat

ja kun

Kaavoissa on siis salattava viesti, salattu viesti (ciphertext), ja avaimen salainen ja julkinen osa sekä n avaimen yhteinen osa, joka kuuluu siis sekä salaiseen että julkiseen avaimeen. Salainen avain on siis kaavan ja yhdessä, ja julkinen avain on kaavan ja yhdessä.

Yksinkertaisimmillaan , ja , jotka toteuttavat edellä olevat kaavat saadaan valitsemalla ja mielivaltaisiksi alkuluvuiksi ja niiden tuloksi. Voidaan myös olettaa, että näin valitut , ja toteuttavat riittävässä määrin myös asymmetriselle kryptausjärjestelmälle asetetut vaatimukset 2 ja 4. Ikävä kyllä tällä tavalla valitut , ja eivät kuitenkaan täytä asymmetrisille salausjärjestelmille asetettua ehtoa, jonka mukaan :n johtamisen :stä on oltava vähintään yhtä vaikeaa kuin salatun selväkielisen viestin johtaminen salatusta ilman avainta. On siis syytä esittää menetelmä sopivien :n, :n ja :n valitsemiseksi [SEDG83].

Aluksi valitaan kolme suurta mielivaltaista alkulukua, joista suurin olkoon . Muita kahta alkulukua kutsuttakoon :ksi ja :ksi. olkoon :n ja :n tulo. Tämän jälkeen valitaan siten, että yhtälö on tosi.

Kaavojen pätevyyden lukuteoreettinen todistus on varsin monimutkainen, eikä sen yksityiskohtaisempi tarkastelu tässä yhteydessä ole tarpeellista.