A tétel alapján, ha p és q különböző prímszámok, és a-nak egyik sem osztója, akkor mind p, mind pedig q osztója a(p-1)(q-1)-1-nek, ami képlettel leírva:
Ez nem más, mint a Fermat tétel, csak a tételbeli képletben a helyére egyszer ap-1, egyszer pedig aq-1 kerül rendre a q-val, illetve p-vel való oszthatóságot felírva. Mivel p és q különböző prímek, ezért a szorzatukkal is osztható a(p-1)(q-1)-1. Legyen n=qp. Ekkor a(p-1)(q-1)+1 pont a maradékot ad n-nel osztva, ha a kisebb, mint n.
Legyen ef=(p-1)(q-1)+1 szorzat alakban feírva. Ekkor az
egyenlethez jutottunk, ahol a mod a maradékképzést jelenti. Legyen a nyilvános kulcs az e,n számpáros, a titkos kulcs pedig az f szám.
A kódolás során az üzenetet először számokká alakítjuk olyan módon, hogy a számok mindegyike kisebb legyen mint n. Ezután az egyes m számokat az
képlettel kódoljuk előállítva a rejtjelezett M üzenetet, és ezt az üzenetet az
képlet alapján lehet dekódolni.
A felhasznált számoknak olyan nagyoknak kell lenniük, hogy az n számot ne lehessen prímtényezőkre bontani. Ha ugyanis az n számot fel tudjuk bontani n=qp alakra, akkor e alapján egy osztással meg lehet határozni f-et.
A prímtényezős felbontásra pillanatnyilag nem áll rendelkezésre hatékony algoritmus, bár az sem bizonyított, hogy ilyen algoritmus nem létezik. Mivel az alapvető arithmetikai műveletek, mint szorzás, összeadás, hatványozás hatékonyan elvégezhetőek, ezért lehetséges olyan nagy p és q használata, amely esetén n nem bontható fel szorzattá.
A tipikus méret általában bithosszban van megadva, és többnyire kettőhatvány. Ha n 1024 bit hosszú, azt általában katonai célokra is megfelelőnek tartják.
toc