Asimetricna kriptografija - Kriptografija sa javnim kljucem


Asimetricna kriptografija se odnosi na krpitografiju koja koristi razlicite kljuceve za sifrovanje i desifrovanje poruka.

Glavna upotreba ove vrste kriptografije je bezbedna komunikacija izmedju korisnika koji prethodno nisu bili u bezbednom kontaktu.

Asimetricna kriptografija, kao i simetricna, moze da se sprovede na vise nacina. Prvi i najpoznatiji je RSA kriptosistem.


RSA kriptosistem koristi Ojlerovu teoremu i kongruetna svojsva operacije modularnosti.

Takodje koristi pretpostavku da je faktorisanje velikih brojeva sa samo dva faktora,

racunski znatno zahtevan proces, cime omogucava bezbednost ovog sistema.


Ojlerova teorema

Ojlerova teorema tvrdi da ako su dva broja a i n uzajamno prosta i k broj uzajamno prostih celih brojeva manjih od n.

Onda je k-ti stepen broja a kongruentan broju jedan po modulu n.


Tacnost ove teoreme se dokazuje preko Lagranzove teoreme koja tvrdi da red podgrupe neke konacne grupe uvek deli red te grupe.

Uzajamno prosti brojevi manji od nekog n cine grupu sa operacijom mnozenja po modulu,

odnosno svaki ima inverz u tom skupu, gde je 1 neutral grupe i sam skup je zatvoren i asocijativan.

Posto red elementa (stepen nad kojim postaje neutral) deli red grupe, jer i sami stepeni elementa cine grupu (Ciklicna grupa),

u kome je ocigledno red svakog elementa ujedno i red te Ciklicne grupe, onda je i k-ti stepen svakog elementa uzajammno prostog sa n

i sam neutral grupe koju uzajamno prosti brojevi manji od n cine, jer je k red te grupe.


Ako je p neki prost broj, onda je broj uzajamno prostih brojeva manjih od p jednak p-1. Ako je i q neki prost broj,

br. uzajamno prostih brojeva manjih od pq je pq-p-q+1, jer ce svi osim brojeva p,2p,...,(q-1)p i q,2q,...,(p-1)q i 1

biti uzajamno prosti sa pq. Posto p-ova ima q-1 i q-ova ima p-1 ukupno ih ima pq-(p-1)-(q-1)-1 sto je jednako pq-p-q+1.


Za dva velika prosta broja ovaj broj ce idalje biti lak da se izracuna znajuci brojeve p i q, ali tesko znajuci samo njihov prozivod.

Uz pomoc ovog broja moze se lako izracunati produzenim euklidovim algoritmom dva inverzna broja po modulu pq-p-q+1

birajuci jedan broj njemu uzajamno prost.


Stepenovanjem bilo kog broja uzajamno prostim sa pq sa jednim od ova dva broja dobijamo broj koji se dodatim stepenovanjem

drugim brojem vraca u pocetnu vrednost.

Posto se nijednom poznatom metodom ne moze naci pocetna vrednost broja, znajuci samo pq i jedan od ova dva inverzna broja,

stepenovanje svakog broja jednim od ova dva dobijamo broj od kog mozemo vratiti pocetnu vrednost samo znajuci drugi od ova dva broja.

Ovom metodom korisik moze da javno objavi broj pq i jedan od dva inverzna broja, kojim drugi korisnici mogu da sifruju poruke citljive samo tom korisniku.

Sifrovanjem sa drugim tajnim brojem pocetni korisnik moze da sifruje poruke citljive svima, dokazujuci da je ista osoba koja ih je generisala na prvom mestu.


Kombinacija poluprostog broja pq i jednog od dva inverzna broja koji se objavljuje javno se naziva javni kljuc,

dok se kombinacija pq i drugog tajnog broja zove privatni kljuc.