Ovde sam izložio teorijske osnove RSA.
Najpre se generišu veliki različiti prosti brojevi p i q i izračunaju n=pq i (p-1)(q-1). Potom se izabere neki broj e, koji će pripadati javnom ključu (najčešće 65537) i izračuna broj d takav da je ed-1 deljivo sa (p-1)(q-1). Javni ključ čine brojevi n i e, a privatni brojevi n i d (odnosno d, pošto se n zna iz javnog ključa), dok se brojevi p, q i (p-1)(q-1) moraju bezbedno uništiti. Obzirom da je tipično e=65537, možemo reći da se javni deo praktično sastoji iz broja n, a tajni iz broja d.
Poruka se deli na blokove od kojih se svaki može kodirati sa k bita tako da je 2
k+2<(p-1)(q-1). Naravno, k je poznat, a p, q i (p-1)(q-1) su uništeni. Ako neki nekriptovani blok odgovara binarnom zapisu broja m, onda je kriptovan oblik bloka binarni zapis broja c u opsegu od 0 do 2
k-1 takav da je (m+2)
e-c-2 deljivo sa n. Što se dekriptovanja tiče, sasvim je slično, jer je (c+2)
d-e-2 deljivo sa n sa verovatnoćom većom od oko 1-1/p-1/q. Rizik da poruka bude pogrešno dekriptovana se prihvata. Napominjem da je pronalaženje bar jedne takve poruke dovoljno da se razbije takav ključ, ali se taj rizik prihvata jer je 1/p+1/q blisko nuli.
Obzirom da n i d imaju otprilike onoliko bitova koliko i zbir bitova za p i q, jasno je zašto se dobijaju blokovi oko 4 puta manje dužine od dužine para ključeva (javni je (n,e), a privatni (n,d)).
Brojevi p i q su generisani nasumično (uz uslov da imaju odgovarajući broj bita, pri čemu bi odnos broja bitova od p i q trebao da bude od 40:60 do 45:55 i da prosti brojevi p i q uvećani/umanjeni za 1 nemaju samo male proste faktore, već i bar neki veliki). Stoga je neophodno koristiti generator (pseudo)slučajnih brojeva, a on zahteva početnu vrednost semena. Ako oni nisu kriptografski sigurni, može se napad izvršiti na njih.
Primera radi
Mersen-Tvister algoritam za generisanje pseudoslučajnih brojeva nije podesan za kriptografske svrhe, bar ne u svom osnovnom obliku, iako ima odlične statističke osobine (vrlo je podesan za simulacije), jer ako znaš bilo kojih 624 uzastopnih generisanih binarnih reči dužine 32 bita, možeš predvideti sve prethodne i sve sledeće. Recimo, ako si e generisao slučajno (nisi se držao standardne preporuke o ozboru e=3 ili e=65537), onda on predstavlja niz uzastopnih generisanih bajtova, pa se na osnovu toga može rekonstruisati ostatak procesa generisanja ključeva i unapred i unazad i eto privatnog ključa.
Ako se nije vodilo računa o generisanju semena, opet sve pada u vodu, jer je ceo postupak generisanja ključeva jednoznačno određen semenom i algoritmom (koji je poznat), pa se postupak generisanja ključeva može ponoviti i opet doći do privatnog ključa. O jednom takvom slučaju se već raspravljalo
ovde. Dakle, jedini izvor slučajnosti je bio PID (process ID), koji na Linuksu ima 16 bita, tako da program za generisanje ključeva nije mogao da generiše više od 65536 različitih parova ključeva (koji se svi generišu vrlo brzo) i sve ostalo pade u vodu. Treba voditi računa da izvor entropije bude dovoljno bogat, a onda dodatno primeniti neku dobru heš funkciju, koja dovodi seme na potrebnu širinu za seme korišćenog generatora pseudoslučajnih brojeva i vrši difuziju, tako da ako neko ima deo informacija o izvorima entropije, ne može praktično ništa da zaključi o semenu.
Jednostavno, kriptografija je lanac koji je jak koliko i najslabija karika. Stoga se mora voditi računa bukvalno o svemu. Ako se ključevi generišu korišćenjem generatora slučajnih, a ne pseudoslučajnih brojeva, onda nema zime. Na primer, mogu se koristiti posebni
kvantni uređaji u tu svrhu. Problem je samo što imaju neku cenu zbog koje nisu standardna oprema svakog računara.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.