Note: This document is in Croatian only. To obtain some information in English, just type PGP on Yahoo! or any other search engine. This should keep you busy for a few days. Also, take a look at PGP, RSA and International PGP home pages.
    Nešto o kriptografiji. PGP. RSA.

    Svi su valjda čuli za nekakav PGP public key iliti PGP javni ključ. Ja bih sad ovdje htio reći nešto općenito o kriptografiji, o tome što je PGP i kako radi RSA algoritam na kojem se temelji PGP-ova programska podrška, koja je danas najrasprostranjenije i najučinkovitije oruđe za kriptiranje datoteka ili, uostalom, bilo čega.


    Osnovni kriptografski problem...

    Dvoje ljudi može se dogovoriti za bilo kakvu funkciju, koja mora biti bijekcija, da služi za šifriranje međusobnih poruka. Pošiljatelj će tada primijeniti dogovorenu funkciju na skup podataka i dobiti kriptirani tekst kojeg će onda primatelj dekriptirati primjenjujući na njega inverz dogovorene funkcije. Kako bijekcija ima pun kufer, naši junaci ne moraju strahovati da će ih netko prokljuviti.
    Stvar naravno štima, ako ta dvojica imaju tiho i skrovito mjesto na kojem se u miru mogu dogovarati o svojoj funkciji za kriptiranje. Ali, što ako takvog mjesta nemaju, ili se čak uopće ne mogu sresti da bi dogovorili način kriptiranja? Mali Ivica bi možda prvo poslao svom sugovorniku formulu, a nakon toga i kriptirani tekst. No, jasno je da onda kriptiranje nema smisla, jer ono želi spriječiti treću osobu da čita ono što joj nije namijenjeno, a ako takav subverzivni element može doći do kriptiranog teksta kojeg Ivica šalje, tada je prethodno mogao uzeti i funkciju-kuharicu za dešifriranje.


    ...i njegovo rješenje "na prste"

    Ideja je, dakle, u postojanju dva ključa od kojih prvi služi za kriptiranje (zaključavanje) a drugi za dekriptiranje (otključavanje) podataka. Javni ključ, za zaključavanje, može biti dostupan svima, dok tajni ključ, za otključavanje, ima samo onaj kome je poruka upućena. To znači da ako Ivica želi uputiti Marici poruku lascivnog sadržaja, a da ih učiteljica ne skuži, on će pročitati Maričin javni ključ na njenoj WWW stranici, upotrijebiti ga da bi kriptirao sadržaj poruke i poslat će ju Marici. Ona će tada upotrijebiti svoj tajni ključić (kojeg ima samo ona) da bi dekriptirala Ivičinu poruku, na primjer pomoću programa PGP koji radi na opisanom načelu dva ključa. To bi tako trebalo ići.
    No, svatko prosječno inteligentan uočit će odmah jednu upitnu stvar: ako zahtijevamo bijektivnost kriptiranja/dekriptiranja (a moramo, inače gubimo podatke koji se prenose), tada je pomoću javnog ključa (bijekcija!) na jedinstven način određen tajni ključ (njegov inverz) koji može otključati što je ovaj zaključao. I, time smo na početku.


    Tri pametne glave (RSA)

    "Hej, sjetili smo se!" - povikala su uglas davne 1977. godine trojica profesora na već legendarnom MIT, Ronald L. Rivest, Adi Shamir i Leonard M. Adleman, i smislili algoritam, kojeg su bez lažne skromnosti nazvali početnim slovima svojih prezimena. Spomenuta trojka pokušala je smisliti određenu klasu funkcija kojima je teško odrediti inverz, što im je u pravom smislu riječi uspjelo, i time su razriješili navedeni kriptografski problem. Kriptirajuća funkcija i dalje, kao bijekcija, određuje svoj inverz, ali ga je jaaako teško naći. Kako? Profesori su se sjetili da je jedna od teoretski najlakših, ali praktički najtežih stvari u matematici - faktorizacija. Na faktorizaciji, i to brojeva, počiva RSA algoritam, kojeg ću, da ne duljim, navesti:
    1. Uzmite dva velika (npr. 1024-bitna) prosta broja p i q.
    2. Odaberite broj e takav da su e i ( p - 1)· ( q - 1) relativno prosti (nemaju zajedničkih prostih faktora). Broj e ne mora biti prost, ali mora biti neparan, jer je ( p - 1)· ( q - 1) paran.
    3. Odaberite d takav da je ( d· e - 1) djeljiv s ( p - 1)· ( q - 1) .
    4. Kriptirajuća funkcija f je f( t ) = ( t e ) mod ( p· q ) , za t prirodan broj.
    5. Dekriptirajuća funkcija f -1 je f -1( c ) = ( c d ) mod ( p· q ) , za c prirodan broj.

      Vaš javni ključ je par ( p· q , e). Vaš tajni ključ je broj d.

    Čak je i površnim uvidom jasno da je za dani par ( p· q , e) vrlo teško izračunati neki broj d. To je zato jer je prvo potrebno naći brojeve p i q, dakle, faktorizirati p· q. Ukoliko su p i q 1024 - bitni, laganim računom slijedi da bi najmoćnije računalo današnjice tražilo faktorizaciju 2048 - bitnog broja p· q dulje od životnog vijeka Zemaljske kugle, a teorija još uvijek ne nudi ništa više od Eratostenovog sita. Time je invertiranje kriptirajuće funkcije praktički onemogućeno.


    Ma nemoj...

    E, sad dolazi do izražaja Tvoja kritičnost, dragi čitatelju ove stranice. Jesi li se zapitao, ne vučem li te možda za nos? Ukoliko nisi, zapitat ću se ja: pa, kako je moguće odabrati slučajni 1024 - bitni prim broj, kad nemam formulu n - tog prim broja, ili bar kriterij? Mogu odabrati veliki slučajni broj, a kako li ću ispitati je li prost? Možda mogu zaroštiljat računalo? Hej, pa onda sam na istom! Problem nalaženja 1024 - bitnog prostog broja nije ništa lakši nego spomenuta faktorizacija. Dapače, ti problemi su ekvivalentni. Nije li naša MIT profesorska trojka samo pretočila iz šupljeg u prazno tj. svela problem na ekvivalentno praktički nerješiv? Tko je tu lud?


    Fermat & Rivest : Ma moj!

    Pierre Fermat, francuski pravnik kojemu je struka dosadila pa se bavio matematikom, formulirao je 1640. godine tvrdnju, kasnije poznatu kao

      Mali Fermatov teorem:
      Neka je p prost broj i a prirodan broj koji nije djeljiv s p.
      Tada je broj a p - 1 - 1 djeljiv s p.

      Dokaz.

    Ovu činjenicu iskoristio je već spomenuti Ron Rivest da bi proveo istraživanje, čiji rezultati su objavljeni u 'Advancess in Cryptology: Proceedings of Crypto '91' , pod naslovom koji govori bolje od ičega o njegovom uspjehu. Naslov glasi: Finding Four Million Large Random Primes. Da ne duljim, ispitavši više od 700,000,000 256-bitnih brojeva, empirijski je zaključio da je vjerojatnost da 256-bitni broj p zadovoljava tvrdnju Malog Fermatovog teorema uz a = 2 , a da ujedno nije prost, manja od 10 -6 . Dakle, u praktične svrhe nalaženja velikih prostih brojeva (zapravo pseudoprostih, tj. takvih koji su vrlo vjerojatno prosti), dovoljan je Mali Fermatov teorem (kako male stvari čine život ljepšim), čije vrijeme izvođenja je tako kratko, da ne stignete kako spada izgovoriti 'Fermat' .


    Prilično dobra privatnost

    Programski paket PGP (Pretty Good Privacy) najbolji je, najpoznatiji i najrasprostranjeniji soft za kriptiranje/dekriptiranje danas. Tvorac PGP-a je Philip Zimmermann, čovjek koji je zbog svog životnog djela imao sijaset problema. PGP za generiranje ključeva koristi RSA algoritam, odnosno njegovu preinaku, koja je relativno brža, no, u osnovi, to je to. Zadnja inačica PGP-a nudi nekoliko stupnjeva zaštite: niski, visoki i 'vojni'. Prvi koristi 512-bitni ključ, drugi 768-bitni, a tzv. vojni stupanj, praktički neuništiv 1024-bitni ključ. Osim generiranja para kripto-ključeva i njihove uporabe, u PGP paketu naići ćete na još 800 raznih stvari. Kao prvo, velik broj hackera nadograđuje i distribuira svoje inačice PGP-a, kao da 'službenih' već nema dvadesetak. Nadalje, sam paket sastoji se od gomile datoteka i još veće gomile uputa i objašnjenja, tako da Vam neće biti dosadno. Za generiranje velikih slučajnih brojeva ne koristi nikakav poznati generator (tko je to vidio; ionako niti jedan nije uniforman!), nego od Vas traži da lupate po tastaturi, mjereći vremena između udaraca. Na kraju, paranoično će 'spaliti' kompletan sadržaj korištenog stacka i RAM-a, da netko ne bi, kad se vi maknete s računala, pročitao Vaš tajni ključ.
    PGP nudi još jednu vrlo korisnu stvar: potpisivanje poslanih dokumenata poznatu kao     PGP signature. Pretpostavimo da Marica očekuje od Ivice poruku. No, kad poruka stigne, kako ona može biti sigurna da ju je poslao baš Ivica, a ne npr. Štef, koji zna fake-ati mail? E pa zato će Ivica potpisati svoj dokument, i to na sljedeći način: svoje ime i prezime on će kriptirati pomoću svog tajnog ključa. Kada Marica primi poruku, upotrijebit će Ivičin javni ključ, kojeg hvalabogu zna, za dekriptiranje potpisa. Ako se pojavi Ivičino benigno ime, sve je OK, a ako dobije smeće na ekranu, znači da joj je netko, tko ne zna Ivičin tajni ključ (dakle, nije Ivica), pokušao uvaliti.
    Kako je, zbog slanja elektronskom poštom, kriptirane datoteke potrebno prevesti u ASCII, PGP može poslužiti i umjesto uuencode programa ili ekvivalenata.


    Tražeći Sveti Gral: Idemo svi!

    Očigledna je, dakle, važnost nalaženja prostih brojeva, ne samo u teoretske svrhe nego, kako smo vidjeli, i za budućnost kriptografije. Tijekom povijesti, određene klase brojeva bile su za neke ljude pravi fetiši; sjetimo se samo Pitagorejske škole koja je odavanje tajne o postojanju korijena iz 2 kažnjavala smrću, ili slobodnih zidara različitih stupnjeva, koji su napredovali upravo proučavajući omjere brojeva na čelu sa Zlatnim rezom.
    Među prostima, očigledno je najzanimljivija klasa Mersenneovih brojeva. To su prosti brojevi oblika     2 n -1 , a naziv su dobili po francuskom redovniku imena Marin Mersenne, koji je 1644. naveo (pogrešno) prvih 11 brojeva rečenog oblika. Danas je, ne biste vjerovali, organiziran pravi pokret za traženje i nalaženje Mersenneovih brojeva, koji je 13. studenog 1996. svijetu svečano objavio da je rekord u potrazi ponovo srušen: dokazano je (najobičnijim dijeljenjem, naravno) da je 2 1398269 -1 najveći dosad poznati Mersenneov, a i prim broj uopće. Ako vas, dakle, zanimaju prosti brojevi, posjetite The Prime Page, a a