Koristim simboliku iz svoje prve poruke gde sam objasnio RSA.
Citat:
Nedeljko: RSA:
1. Generisati dva ogromna prosta broja p i q i izračunati n=pq i fi(n)=(p-1)(q-1).
2. Generisati broj u uzajamno prost sa fi(n) i naći broj v takav da je uv-1 deljivo sa fi(n).
Jedan ključ je (u,n), a drugi (v,n) (ta dva ključa su par). Poruka je ceo nenegativan broj a<n. Šifrira se tako što se izračuna čemu je kongruentno au po modulu n (u sistemu ostataka 0,...,n-1). Dešifrovanje se vrši na sličan način, samo što se umesto u koristi v. Dešifrovana poruka je identična originalu ako je a uzajamno prosto sa n.
Promenio sam to što je sada poruka co nenegativan broj a<n, a ne prirodan broj a<n (dozvoljeno je da bude a=0).
U odnosu na uobi;ajenu primenu RSA algoritma ovde postoje neke razlike.
Brojevi p i q su javni, tj. znaju ih svi igrači na početku. Oni mogu biti čak jednom dogovoreni i da se koriste za neograničen broj partija. Samim tim su svima poznati i brojevi n i fi(n). Znači, njih ima na internetu i svi igrači ih koriste, to jest dele iste p, q, n, fi(n).
Igrač P(i) na početku generiše slučajan prirodan broj u(i)<fi(n) uzajamno prost sa fi(n). Zatim izračunava prirodan broj v(i)<n takav da je u(i)v(i)-1 deljivo sa fi(n). Postoji tačno jedan broj koji ispunjava te uslove i on je uzajamno prost sa fi(n). Brojevi u(i) i v(i) su tajna igrača P(i).
Igrač P(i) stavlja svoj katanac na poruku a tako što izračuna ostatak c(a,i) pri delenju broja a
u(i) sa n, a skida svoj katanac sa poruke a tako što izračuna ostatak d(a,i) pri delenju broja a
u(i) sa n. Ojlerova teorema garantuje da ako je a uzajamno prosto sa n, onda važi d(c(a,i),i)=c(d(a,i),i)=a, to jest, kada nešto zaključam, pa otključam, dobiću ono što sam imao na početku. To je tačno još i u slučaju kada je a=0. No, kada je a različito od 0, ali je deljivo sa jednim o brojeva p,q, onda kada a zaključaš, pa otključaš, nećeš dobiti a, nego neko đubre. To je jednostavno falinka RSA algoritma. Verovatnoća da a bude takvo je 1/p + 1/q - 2/n, odnosno jako je mala ako su p i q jako veliki.
Zahvaljujući tome što svi igrači koriste iste n i fi(n), redosled stavljanja i skudanja katanaca neće biti bitan.
Ovaj postupak se razlikuje od uobičajene upotrebe RSA algoritma po tome što su ovde p,q,n i fi(n) javni, a u i v tajni, a kod uobičajne upotrebe su u i n javni, a v,p,q, i fi(n) tajni. Štaviše, nakon izračunavanja v više nisu ni bitni p,q i fi(n) (uništavaju se, štaviše p i q se iništavaju nakon izračunavanja fi(n)).
Ovde pretpostavljam da se zna matematička pozadina RSA algoritma.
Dobro je da se to ne desi, ali je jako mala verovatnoća da će se to desiti. Uostalom, sam RSA ima sličnu falinku koju sam opisao.
Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.