Sistem kriptografi RSA bekerja sebagai berikut. Misalkan kita memilih dua bilangan prima acak berukuran 150 digit, \(p\) dan \(q\text{.}\) Selanjutnya, kita hitung hasil kali \(n= pq\) dan juga \(\phi(n) = m = (p - 1)(q-1)\text{,}\) dengan \(\phi\) sebagai fungsi \(\phi\) Euler. Kemudian kita memilih bilangan bulat acak \(E\) sampai menemukan satu yang relatif prima terhadap \(m\text{;}\) yaitu, kita pilih \(E\) sedemikian sehingga \(\gcd(E, m) = 1\text{.}\) Dengan algoritma Euklides, kita dapat menemukan bilangan \(D\) sedemikian sehingga \(DE \equiv 1 \pmod{m}\text{.}\) Bilangan \(n\) dan \(E\) kemudian diumumkan kepada publik.