RSA enkripcijski algoritam. Primjer algoritma rsa enkripcije Tehnologija implementacije rsa algoritma

Uvod 3

Glavni dio 5

1Povijest stvaranja 5

2Opis algoritma 5

2.1 Stvaranje ključeva 6

2.2 Šifriranje i dešifriranje 6

2.3 Upotrijebite primjer 7

Zaključak 9

Popis korištenih izvora 10

Uvod

Kriptografija je poseban sustav za mijenjanje običnog pisma, koji se koristi kako bi tekst bio razumljiv samo ograničenom broju ljudi koji poznaju ovaj sustav.

Kriptografija je znanost o zaštiti informacija pomoću matematičkih metoda.

Moderna kriptografija uključuje:

simetrični kriptosustavi;

asimetrični kriptosustavi;

Sustavi elektroničkog digitalnog potpisa (EDS);

hash funkcije;

upravljanje ključem;

dobivanje skrivenih informacija;

kvantna kriptografija.

Simetrična enkripcija - simetrični algoritmi su oni kod kojih se za enkripciju i dekripciju koristi isti tajni ključ (poznat samo pošiljatelju i primatelju).

Uobičajeni algoritmi simetrične enkripcije:

AES (Advanced Encryption Standard) - američki standard šifriranja;

GOST 28147-89 - domaći standard šifriranja podataka;

DES (Data Encryption Standard) - standard šifriranja podataka u SAD-u do AES;

3DES (trostruki DES, trostruki DES);

IDEA (International Data Encryption Algorithm);

SEED - korejski standard šifriranja podataka;

Camellia je šifra certificirana za upotrebu u Japanu;

XTEA je najlakši algoritam za implementaciju.

Asimetrični kriptoalgoritmi prvenstveno su dizajnirani da uklone glavni nedostatak simetričnih kriptosustava - složenost upravljanja i distribucije ključeva.

Osnova svih asimetričnih kriptografskih algoritama je visoka računalna složenost obnavljanja otvorenog teksta bez poznavanja privatnog ključa.

Primjeri asimetričnih kripto algoritama:

Diffie-Hellmann;

RSA - Rivest, Shamir, Adelman - temelji se na složenosti problema faktoriziranja velikih brojeva u kratkom vremenu;

DSA – Algoritam digitalnog potpisa, američki standard;

GOST R 34.10 – 94, 2001, standardi Ruske Federacije.

U ovom sažetku ćemo detaljno razmotriti algoritam asimetrične kriptografske enkripcije - RSA algoritam.

Glavni dio

RSA algoritam (akronim za Rivest, Shamir i Adleman) je kriptografski algoritam s javnim ključem koji iskorištava računsku složenost problema rastavljanja velikih cijelih brojeva na faktore. RSA kriptosustav bio je prvi sustav pogodan i za šifriranje i za digitalno potpisivanje.

Povijest stvaranja

Objavljen u studenom 1976., rad Whitfielda Diffieja i Martina Hellmana "Novi smjerovi u kriptografiji" revolucionirao je razumijevanje kriptografskih sustava postavljajući temelje za kriptografiju s javnim ključem. Naknadno razvijen Diffie-Hellmanov algoritam omogućio je dvjema stranama da dobiju zajednički tajni ključ koristeći nesiguran komunikacijski kanal. Međutim, ovaj algoritam nije riješio problem autentifikacije. Bez dodatnih alata korisnici ne bi mogli biti sigurni s kim su generirali tajni ključ.

Nakon proučavanja ovog članka, tri znanstvenika Ronald Linn Rivest, Adi Shamir i Leonard Adleman s Massachusetts Institute of Technology (MIT) započeli su potragu za matematičkom funkcijom koja bi omogućila implementaciju modela kriptografskog sustava s javnim ključem koji su formulirali Whitfield Diffie i Martin Hellman . Nakon što su proradili više od 40 mogućnosti, došli su do algoritma temeljenog na razlici u tome koliko je lako pronaći velike proste brojeve i koliko je teško faktorizirati umnožak dva velika prosta broja, što su kasnije nazvali RSA. Sustav je dobio ime po prvim slovima prezimena njegovih kreatora.

Opis algoritma

Prvi korak u bilo kojem asimetričnom algoritmu je stvaranje para ključeva - javnog i privatnog - i distribucija javnog ključa "po cijelom svijetu".

Stvaranje ključeva

Za RSA algoritam, faza stvaranja ključa sastoji se od sljedećih operacija:

Broj se naziva otvoreni eksponent

Šifriranje i dešifriranje

Recimo da pošiljatelj želi poslati poruku primatelju.

Poruke su cijeli brojevi u rasponu od 0 do , tj. . Slika 1 prikazuje dijagram RSA algoritma.

Slika 1 – Dijagram RSA algoritma

Algoritam pošiljatelja:

Algoritam primatelja:

Jednadžbe (1) i (2), na kojima se temelji RSA shema, određuju međusobno inverzne transformacije skupa.

Primjer upotrebe

Tablica 1 prikazuje primjer korištenja RSA algoritma. Pošiljatelj je poslao šifriranu poruku "111111", a primatelj ju je pomoću svog privatnog ključa dekriptirao.

Tablica 1 – Izvođenje RSA algoritma korak po korak

	Opis operacije	Rezultat operacije
Generiranje ključeva	Odaberite dva prosta broja
	Izračunajte modul
	Izračunajte Eulerovu funkciju
	Odaberite otvoreni eksponent
	Izračunaj tajni eksponent


Šifriranje	Odaberite tekst za šifriranje
Šifriranje	Izračunaj šifrirani tekst
Dekodiranje	Izračunaj izvornu poruku

Zaključak

U ovom sažetku se detaljno raspravlja o algoritmu asimetrične enkripcije RSA. Opisana je povijest njegovog nastanka, opisani su algoritmi za kreiranje ključeva, šifriranje i dešifriranje. Prikazan je i primjer praktične primjene RSA algoritma.

Popis korištenih izvora

Semenov Yu.A. Internetski protokoli // M.: Prospekt, 2011. – 114 str.

Belyaev A.V. Metode i sredstva informacijske sigurnosti // Black Branch of St. Petersburg State Technical University, 2010. – 142 str.

Venbo M. Moderna kriptografija. Teorija i praksa // M.: Williams, 2005. - 768 str.

Schneier B. Primijenjena kriptografija. Protokoli, algoritmi, izvorni tekstovi // M.: Triumph, 2002. - 816 str.

RSA algoritam // Internetski izvor: http://ru.wikipedia.org/wiki/Rsa

U drugom dijelu ćemo pogledati popularni RSA algoritam, gdje se za enkripciju koristi javni ključ. Ali prvo vas želim još jednom upozoriti. Kod predstavljen u ovom članku služi samo u obrazovne svrhe. Kriptografija je vrlo široko i složeno područje, a kako bih izbjegao bilo kakve probleme, ne preporučujem šifriranje podataka korištenjem mog hacka.

RSA algoritam

Šifriranje korištenjem javnog ključa

Enkripcija s javnim ključem koristi se posvuda. Ako ste barem jednom platili nešto online, već ste koristili ovu metodu (nadam se!). Odmah se postavlja pitanje kako ta zaštita funkcionira. Ako unesem broj svoje kreditne kartice da nešto kupim, zašto nitko osim primatelja ne može vidjeti te podatke? Dat ću vam metaforu. Za otvaranje sefa potreban vam je ključ (ili čekić, ali srećom sefovi i brave su otporni na takve aktere). U enkripciji s javnim ključem događa se uglavnom ista stvar. Pokazujete bravu da svi vide, ali samo nekolicina odabranih ima ključ za ovu bravu, a vrata je gotovo nemoguće otvoriti drugim metodama.

RSA je jedan od algoritama koji implementira gornju shemu. Osim toga, ovaj algoritam možemo koristiti za provjeru autentičnosti našeg identiteta. Ako nekome pošaljete šifriranu poruku koristeći privatni ključ, primatelj može dešifrirati vašu poruku pomoću javnog ključa. Ova tehnologija omogućuje potpisivanje poruka, čime se potvrđuje autentičnost pošiljatelja.

Demo program baziran na RSA algoritmu

Ovisno o strukturi korištenih ključeva, metode šifriranja dijele se na:

simetrično: autsajderi mogu znati algoritam šifriranja, ali mali dio tajnih informacija je nepoznat - ključ, koji je isti za pošiljatelja i primatelja poruke; Primjeri: DES, 3DES, AES, Blowfish, Twofish, GOST 28147-89
asimetrična enkripcija: autsajderi mogu znati algoritam šifriranja, a možda i javni ključ, ali ne i privatni ključ, poznat samo primatelju. Kriptografski sustavi s javnim ključem trenutno se naširoko koriste u raznim mrežnim protokolima, posebno u protokolima TLS i njegovom prethodniku SSL (temeljni HTTPS), kao i SSH, PGP, S/MIME itd. Ruski standard, koji koristi asimetričnu enkripciju - .

U ovom trenutku, asimetrična enkripcija s javnim ključem RSA (skraćenica za Rivest, Shamir i Aldeman - tvorci algoritma) koristi većina proizvoda na tržištu informacijske sigurnosti.

Njegova kriptografska snaga temelji se na težini faktoriziranja velikih brojeva, odnosno na iznimnoj težini zadatka određivanja tajnog ključa na temelju javnog ključa, jer bi to zahtijevalo rješavanje problema postojanja djelitelja cijelog broja. Najsigurniji sustavi koriste 1024-bitne i veće brojeve.

Pogledajmo RSA algoritam s praktične točke gledišta.

Prvo morate generirati javne i privatne ključeve:

Uzmimo dva velika prosta broja p i q.
Definirajmo n kao rezultat množenja p na q (n= p*q).
Izaberimo slučajni broj koji ćemo nazvati d. Ovaj broj mora biti relativno prost (nema nijedan zajednički djelitelj osim 1) s rezultatom množenja (p-1)*(q-1).
Definirajmo broj e za koji vrijedi sljedeća relacija (e*d) mod ((p-1)*(q-1))=1.
Nazovimo javni ključ brojevima e i n, a tajni ključ brojevima d i n.

Za šifriranje podataka pomoću javnog ključa (e,n) potrebno vam je sljedeće:

podijeliti šifrirani tekst u blokove, od kojih se svaki može predstaviti kao broj M(i)=0,1,2..., n-1 (tj. samo do n-1).
šifrirati tekst, promatran kao niz brojeva M(i) pomoću formule C(i)=(M(I)^e)mod n.

Za dešifriranje ovih podataka pomoću tajnog ključa (d,n), moraju se izvršiti sljedeći izračuni: M(i) = (C(i)^d) mod n. Kao rezultat, dobit će se skup brojeva M(i) koji predstavljaju izvorni tekst.

Sljedeći primjer jasno pokazuje RSA enkripcijski algoritam:

Kriptirajmo i dešifrirajmo "CAB" poruku pomoću RSA algoritma. Radi jednostavnosti, uzmimo male brojeve - to će skratiti naše izračune.

Izaberimo p=3 i q=11.
Definirajmo n= 3*11=33.
Nađimo (p-1)*(q-1)=20. Stoga će d biti jednako, na primjer, 3: (d=3).
Izaberimo broj e pomoću sljedeće formule: (e*3) mod 20=1. To znači da će e biti jednako, na primjer, 7: (e=7).
Zamislimo šifriranu poruku kao niz brojeva u rasponu od 0 do 32 (sjetimo se da završava na n-1). Slovo A =1, B=2, C=3.

Sada šifrirajmo poruku pomoću javnog ključa (7.33)

C1 = (3^7) mod 33 = 2187 mod 33 = 9;
C2 = (1^7) mod 33 = 1 mod 33 = 1;
C3 = (2^7) mod 33 = 128 mod 33 = 29;

Sada ćemo dešifrirati podatke korištenjem privatnog ključa (3.33).

M1=(9^3) mod 33 =729 mod 33 = 3(C);
M2=(1^3) mod 33 =1 mod 33 = 1(A);
M3=(29^3) mod 33 = 24389 mod 33 = 2(B);

Podaci dešifrirani!

Konačno je došlo vrijeme da počnemo opisivati RSA kriptosustav. Osim objašnjenja kako radi, moramo detaljno razgovarati o njegovoj sigurnosti; drugim riječima, zašto je tako teško razbiti poruku šifriranu RSA kriptosustavom?

§ 12.1. O početku i kraju

Da biste implementirali jednokorisnički RSA sustav šifriranja, morate odabrati dva različita prosta broja p i q i izračunati njihov umnožak. Prosti brojevi p i q ostaju tajni dok broj postaje dio javnog ključa. U § 12.5 detaljno raspravljamo o metodi za odabir ključnih primarnih brojeva i kako se ovaj izbor odnosi na pouzdanost sustava.

Poruka (koja se može smatrati cijelim brojem) je šifrirana podizanjem na neki modulo stepen. Stoga, prvo moramo pronaći način da predstavimo tekst poruke kao popis modulo klasa proces enkripcije, već samo priprema poruke da bi se mogla šifrirati.

Radi jednostavnosti, pretpostavimo da tekst poruke sadrži samo riječi napisane velikim slovima. Dakle, poruka je u konačnici niz slova i razmaka. Prvi korak je zamijeniti svako slovo poruke brojem koji je odabran iz sljedeće tablice:

(vidi sken)

Razmak između riječi zamjenjuje se brojem 99. Nakon ove procedure dobit ćemo broj, moguće vrlo velik ako je poruka duga. Međutim, ovo nije konačan broj kojem težimo, već samo skup modulo klasa. A sada moramo razbiti numeričku reprezentaciju poruke na dijelove, od kojih je svaki prirodan broj koji ne prelazi ovi dijelovi se obično nazivaju. blokovi poruka.

Na primjer, numerički prikaz mota “UPOZNAJ SEBE” izgleda ovako:

Odabirom jednostavnih dobivamo umnožak. Dakle, numerički prikaz poruke koja je napisana iznad mora se podijeliti na blokove manje od 23.393.

Naravno, izbor blokova nije jednoznačan, ali nije ni posve proizvoljan. Na primjer, kako bi se izbjegle dvosmislenosti u fazi

dešifriranje ne bi trebalo istaknuti blokove koji počinju s nulom.

Prilikom dešifriranja poruke šifrirane sustavom RSA enkripcije dobiva se niz blokova. Zatim se spajaju kako bi proizveli numerički prikaz poruke. I tek nakon zamjene brojeva slovima u skladu s gornjom tablicom bit će moguće pročitati izvornu poruku.

Imajte na umu da je svako slovo u tablici kodirano dvoznamenkastim brojem. Ovo se radi kako bi se spriječila zabuna. Pretpostavimo da smo slova numerirali redom, počevši od 1, tj. A odgovara 1, B 2, i tako dalje. U ovom slučaju nećemo moći sa sigurnošću reći predstavlja li blok 12 par slova ili samo jedno slovo, dvanaesto slovo abecede. Naravno, za numerički prikaz poruke možete koristiti bilo koju korespondenciju jedan-na-jedan između slova i brojeva, na primjer, -kodiranje, u kojem se prijevod poruke u digitalni oblik automatski izvodi pomoću računala.

§ 12.2. Šifriranje i dešifriranje

Poruka pripremljena za enkripciju korištenjem metode iz § 12.1 sastoji se od niza blokova, od kojih je svaki broj manji od Sada raspravimo kako je svaki blok šifriran. Da bismo to učinili, potreban nam je broj jednak umnošku prostih brojeva i prirodnog broja, modulo invertibilan, tj. broj koji zadovoljava uvjet

Prisjetimo se da se iz poznatih p i q broj može lako izračunati. Stvarno,

Par se naziva javni ili ključ za kodiranje RSA kriptosustava koji opisujemo. Neka blok poruke, odnosno cijeli broj koji zadovoljava nejednakost Koristit ćemo simbol za označavanje bloka šifrirane poruke koji odgovara Izračunava se prema sljedećem pravilu:

Imajte na umu da je svaki blok poruke zasebno šifriran. Stoga se šifrirana poruka zapravo sastoji od zasebnih šifriranih blokova. Štoviše, te blokove ne možemo kombinirati u jedan veliki broj, budući da će to onemogućiti dešifriranje poruke. Uskoro ćemo vidjeti razlog za to.

Vratimo se na primjer koji smo počeli razmatrati u prvom odlomku. Popravili smo tako da Sada trebamo odabrati broj Podsjetimo se da mora biti istoprost s Najmanji prosti broj koji ne dijeli 23088 je jednak 5. Postavimo Za kodiranje prvog bloka poruke iz § 12.1, imamo da odredimo oduzimanje broja 25245 po modulu 23393. Korištenjem programa za simbolički izračun (ili kalkulatora, ako imate strpljenja) dobivamo da je traženi odbitak 22 752. Dakle, šifrirana poruka je predstavljena sljedećim nizom blokova :

Pogledajmo kako se dekodiraju blokovi šifrirane poruke. Da bismo započeli dešifriranje, moramo znati inverzni element na modulo. Posljednji od njih je prirodni broj, koji ćemo označiti s Par se naziva tajni ili ključ za dekodiranje RSA enkripcijskog sustava. Ako je a blok šifrirane poruke, tada je odgovarajuća dešifracija

Rezultat operacije je:

Prije nego se vratimo na primjer, potrebni su neki komentari. Prvo, vrlo je lako izračunati ako znate. Uistinu, tajni ključ se određuje pomoću proširenog Euklidovog algoritma. Drugo, ako je blok izvorna poruka, onda imamo pravo očekivati jednakost. Drugim riječima, pri dekodiranju bloka šifrirane poruke, nadamo se da ćemo pronaći odgovarajući blok izvorne poruke. Činjenica da će to biti slučaj ne proizlazi izravno iz gore opisanog algoritma, ali ćemo sve detaljno raspraviti u sljedećem paragrafu.

Konačno, kao što smo tvrdili u uvodu i kroz cijelu knjigu, da biste razbili RSA kriptosustav, morate ga faktorizirati jer morate znati kako dešifrirati poruku. Međutim, nakon što se detaljno opiše rad sustava, jasno je da potonja izjava nije posve točna. Za čitanje enkripcije, osim samog elementa, trebate znati samo inverzni modul elementa. Stoga, da biste hakirali sustav, dovoljno je izračunati s poznatim Ispada da je ovaj izračun ekvivalentan faktoriziranju broja. , kao što ćemo vidjeti u § 12.4.

U primjeru o kojem se raspravlja, primjenjujemo prošireni euklidski algoritam na brojeve i 5 za određivanje.

(vidi sken)

Prema tome, inverz od 5 modulo bi bio -9235 i

Najmanji prirodni broj usporediv s -9235 po modulu Dakle, da bismo dekodirali blok šifrirane poruke, moramo ga podići na potenciju 13 853 po modulu 23 393. U našem primjeru, prvi kodirani blok je 22 752. Izračunavanje oduzimanja broja 22 75213853 modulo 23,393 , dobivamo Napomena da čak i s tako malim brojevima, zahtjevi za rad RSA kriptosustava premašuju mogućnosti većine džepnih kalkulatora.

§ 12.3. Zašto djeluje?

Kao što smo ranije napomenuli, gore opisani koraci dovode do radnog kriptosustava samo ako se, kao rezultat dekodiranja svakog bloka šifrirane poruke, vrati odgovarajući blok izvornog. Pretpostavimo da imamo posla s RSA sustavom koji ima javni ključ i privatni ključ. Koristeći zapis iz § 12.2, trebamo pokazati da za svaki cijeli broj koji zadovoljava nejednakost vrijedi identitet.

Zapravo, dovoljno je to dokazati

Doista, i 6 i nenegativni cijeli brojevi su manji, stoga su usporedivi u apsolutnoj vrijednosti ako i samo ako su jednaki. Ovo, posebno, objašnjava zašto numerički prikaz poruke razbijamo na manje blokove. Osim toga, iz ovoga se vidi da blokovi

Kodirana poruka mora biti odvojeno zapisana: inače naše zaključivanje neće funkcionirati.

Iz recepata za šifriranje i dešifriranje slijedi da

Budući da su elementi međusobno inverzni po modulu, postoji prirodni k takav da Štoviše, prema uvjetu, brojevi su veći. Stoga, zamjenom umjesto umnoška u jednadžbi (3.1), dobivamo

Upotrijebimo sada Eulerov teorem, koji kaže da Dakle, tj.

i potpuno bismo dobili dokaz da se u njega nije uvukla mala greška.

Ako ponovno pažljivo pregledate naše razmišljanje, primijetit ćete da nismo uzeli u obzir uvjete Eulerovog teorema. Naime, prije primjene teorema potrebno je uvjeriti se da su brojevi međusobno prosti. To, čini se, treba pratiti prilikom pripreme poruke za šifriranje, tj. Kada dijelite numeričku reprezentaciju poruke u blokove, morate osigurati da su svi rezultirajući blokovi međusobno prosti. Srećom, to nije potrebno, jer se zapravo usporedba vrši za bilo koji blok. A greška nije u rezultatu koji želimo dokazati, već samo u samom dokazu. Ispravan pristup temelji se na obrazloženju korištenom u dokazu Corceltova teorema u 7. poglavlju.

Podsjetimo se gdje su različiti prosti brojevi. Definirajmo ostatke broja modulo Budući da

izračuni za oba prosta broja su slični, samo ćemo detaljno razraditi slučaj, dakle, to smo već vidjeli

za neki cijeli broj, dakle,

Sada bismo željeli primijeniti Fermatov teorem, ali imamo pravo to učiniti samo ako ne dijeli. Neka ovaj zahtjev bude zadovoljen. Onda to shvaćamo

Zamjenom Fermatovog teorema Eulerovim teoremom nismo riješili problem koji se pojavio: usporedba vrijedi samo za neke, ali ne i za sve blokove. Međutim, sada se blokovi za koje obrazloženje ne radi moraju podijeliti s Dalje, ako dijeli onda su oba 6 i usporedivi su s 0 u modulu i stoga međusobno usporedivi. Dakle, usporedba koja se dokazuje vrijedi iu ovom slučaju. Stoga je usporedba istinita za bilo koji cijeli broj. mogao upotrijebiti slično razmišljanje kada je primijenio Eulerov teorem na Doista, nejednakost ne znači usporedbu jer je broj složen.

Dakle, dokazali smo da je usporedba dokazana na sličan način. Drugim riječima, i dijele s i But su različiti prosti brojevi, tako da nam lema iz § 3.6 jamči da dijelimo A budući da imamo za bilo koji cijeli broj. Drugim riječima, As. primijetili smo na početku odlomka, to je dovoljno da se dokaže jednakost budući da su oba njezina dijela nenegativni cijeli brojevi manji od Da rezimiramo, možemo reći da

algoritam iz prethodnog paragrafa vodi do praktičnog kriptosustava. Sada morate provjeriti je li pouzdan.

§ 12.4. Zašto je sustav pouzdan?

Podsjetimo se da je RSA sustav šifriranja s javnim ključem koji se sastoji od umnoška različitih prostih brojeva i modulo invertibilnog prirodnog broja. Pogledajmo pažljivo što se može učiniti za probijanje RSA ako je sve što je poznato par

Za dekodiranje bloka šifriranog RSA-om, moramo znati inverziju modula k. Problem je u tome što je praktički jedini poznati način da to učinimo temeljen na primjeni proširenog Euklidovog algoritma na. Međutim, za izračunavanje pomoću formule iz § 9.4 moramo znati što potvrđuje izvornu izjavu: Razbijanje RSA zahtijeva faktorizaciju. A budući da su poteškoće s dekompozicijom fundamentalne, RSA sustav je siguran.

Može se, naravno, pretpostaviti da će jednog dana netko otkriti algoritam koji izračunava bez informacija o faktorima broja. Što će se, na primjer, dogoditi ako netko smisli učinkovit način za izravno određivanje. Zapravo, to je samo prikrivena metoda ekspanzije Točnije, ako

poznati, onda možemo lako izračunati Doista,

pa je poznat zbroj traženih prostih djelitelja. Unaprijediti,

stoga je i razlika poznata. Sada, rješavanjem jednostavnog sustava linearnih jednadžbi, možemo lako pronaći faktorizaciju.

To znači da algoritam koji izračunava zapravo rastavlja broj na faktore, tako da je to nevjerovatna stvar. Ali prerano je za smirenje. Možete ići dalje u svojim fantazijama i pretpostaviti da je netko izmislio algoritam koji određuje izravno prema Ali Dakle, ako znamo, onda znamo broj koji je višekratnik toga. Ispada da je i takva informacija dovoljna za dekompoziciju. Vjerojatni algoritam koji vodi takvoj dekompoziciji može se pronaći V . Vježba 7 prikazuje sličan (ali jednostavniji) algoritam dekompozicije pod pretpostavkom da se Rabinov kriptosustav može razbiti. To će vam dati ideju o vjerojatnosnom algoritmu iz .

Ostaje posljednja mogućnost za hakiranje: pokušaj vraćanja bloka izravno po modulu ostatka. Ako je dovoljno velik, tada je sustavno pretraživanje svih mogućih kandidata za pretraživanje jedini izlaz. Nitko još nije smislio ništa bolje. Naveli smo glavne argumente koji objašnjavaju zašto se razbijanje RSA kriptosustava smatra jednakim faktorizaciji, iako još nema rigoroznih dokaza za ovu tvrdnju.

§ 12.5. Odabir jednostavnih

Iz prethodne rasprave proizlazi da je za sigurnost RSA kriptosustava važno odabrati prave proste brojeve. Naravno, ako su mali, sustav se lako hakira. Međutim, nije dovoljno izabrati velike, čak i ako su p i q ogromni, ali je razlika mala, njihov se umnožak može lako faktorizirati korištenjem Fermatovog algoritma (vidi § 3.4).

Ovo nije prazna priča. Godine 1995. dva su studenta na američkom sveučilištu provalila javnu verziju RSA. To je postalo moguće zbog lošeg izbora prostih faktora sustava.

S druge strane, RSA se koristi već duže vrijeme i, ako se glavni faktori pažljivo biraju, sustav se zapravo pokazuje prilično pouzdanim. Stoga svaki programer RSA enkripcije treba učinkovitu metodu za uspješan odabir prostih brojeva.

Pretpostavimo da želimo stvoriti RSA kriptosustav s javnim ključem u kojem cijeli broj ima oko znamenki. Prvo, odaberimo prosti broj čiji se broj znakova nalazi između, uzmimo ga blizu. Trenutno je preporučena veličina ključa za osobnu upotrebu 768 bita, tj. treba imati približno 231 znamenku. Da bismo konstruirali takav broj, potrebna su nam dva jednostavna, recimo od 104 i 127 znamenki. Imajte na umu da su ovako odabrani prosti brojevi prilično udaljeni jedan od drugog, tj. Korištenje Fermatovog algoritma za dekompoziciju u ovoj situaciji je nepraktično. Osim toga, moramo biti sigurni da u rastavljanje brojeva na proste faktore nisu uključeni samo mali faktori, već i veliki. Doista, inače, broj postaje lak plijen za neke dobro poznate algoritme dekompozicije (vidi). Razmotrimo sada metodu kojom se pronalaze prosti brojevi koji zadovoljavaju navedene uvjete.

Prvo trebamo jedan jednostavan rezultat o distribuciji prostih brojeva. Prisjetimo se što označava broj prostih brojeva koji ne prelaze x. S obzirom na teorem o prostom broju, vidimo da je za veliki x broj približno jednak gdje je prirodni logaritam

na temelju (vidi § 4.5). Neka to bude vrlo velik, neki pozitivan broj. Želimo procijeniti broj prostih brojeva koji se nalaze između i procijeniti razliku. Zahvaljujući teoremu o prostim brojevima i svojstvima logaritma, razlika je približno jednaka

Pod pretpostavkom da je vrlo mala, možemo pretpostaviti da je vrijednost jednaka 0 i dobiti razumnu procjenu razlike, dakle, broj prostih brojeva između njih je približno jednak, što je x veći Za detaljniji uvod u takvu procjenu, vidi ([D. 10]).

Pretpostavimo da trebamo odabrati prosti broj u blizini cijelog broja x. Radi određenosti, pretpostavit ćemo da je x reda , a tražimo prosti broj u intervalu od x do Bilo bi korisno znati unaprijed koliko prostih brojeva ima u tom intervalu. Za procjenu broja prostih brojeva, možete koristiti upravo dobiveni rezultat. U našem primjeru, vrijednost je vrlo malog reda veličine: Stoga, korištenjem gore napisane formule, zaključujemo da interval između leži približno

primarni brojevi. Na kraju drugog paragrafa 11. poglavlja formulirali smo strategiju za dokazivanje jednostavnosti zadanog neparnog broja. Sastoji se od tri koraka.

Shema Rivest-Shamir-Adleman (RSA) trenutno je jedina široko prihvaćena i praktično korištena shema šifriranja s javnim ključem.

RSA shema je blok šifra u kojoj su i otvoreni tekst i šifrirani tekst predstavljeni cijelim brojevima u rasponu od 0 do P- 1 za neke P.

Otvoreni tekst šifriran je u blokovima, od kojih svaki sadrži binarnu vrijednost manju od određenog broja P. To znači da duljina bloka ne smije biti veća od log2(“). U praksi se odabire duljina bloka 2 k bitovi gdje 2 do Shema koju su razvili Rivest, Shamir i Adleman temelji se na izrazima s ovlastima. Šifriranje i dešifriranje za blok otvorenog teksta M i blok šifriranog teksta C može se predstaviti sljedećim formulama:

I pošiljatelj i primatelj moraju znati značenje P. Pošiljatelj zna značenje e, a samo primatelj zna vrijednost d. Dakle, ova shema je algoritam šifriranja s javnim ključem KU= (e, p), i privatni ključ KR = (d, p).

Da bi se ovaj algoritam koristio za enkripciju s javnim ključem, moraju biti ispunjeni sljedeći zahtjevi:

Moraju postojati takve vrijednosti e, d I P,Što M ed = M (mod P) za sve M str.

IVT i trebao bi biti relativno jednostavan za izračunavanje C c1 za sve vrijednosti M p.

Mora biti gotovo nemoguće odrediti d prema raspoloživom njezin str.

Prvo analizirajmo prvi zahtjev, a kasnije pogledajmo ostale. Potrebno je pronaći odnos forme

Ovdje je najprikladniji korolar iz Eulerovog teorema: za bilo koja dva takva prosta broja R I q i bilo koja dva takva cijela broja Pete,Što n=pqn0 i proizvoljan cijeli broj Do vrijede sljedeće relacije:

gdje je φ(i) Eulerova funkcija čija je vrijednost jednaka broju pozitivnih cijelih brojeva manjim od P i međusobno prime sa P.

U slučaju jednostavnog R I q imamo f (pq) - (str - 1 )(q - 1). Stoga se traženi omjer dobiva pod uvjetom

Ovo je ekvivalentno sljedećim odnosima:

oni. njezin d međusobno su inverzni po modulu φ(i). Imajte na umu da se, prema pravilima aritmetike u klasama ostataka, to može dogoditi samo kada d(i stoga e) je relativno prost s φ(u). U ekvivalentnoj notaciji (f(/7), d)=.

Sada imamo sve za uvođenje RSA sklopa. Komponente kruga su:

R I q- dva prosta broja (tajni, odabrani);

p - pq(otvoreno, izračunato);

takav e, što (f(i), e)= 1,1 e

d = e l(mod f(/?)) (tajno, izračunato).

Privatni ključ se sastoji od (d,n), i otvoriti - od (e, p). Pretpostavimo da je korisnik A objavio svoj javni ključ i sada će mu korisnik B proslijediti poruku M.

Zatim korisnik B izračunava šifriranu poruku

Nakon što primi taj šifrirani tekst, korisnik A ga dešifrira računanjem

Ima smisla dati obrazloženje za ovaj algoritam ovdje. Bili odabrani njezin d takav da

Tako da izgleda kao sranje kts>(p)+. Ali posljedicom Eulerovog teorema, za bilo koja dva takva prosta broja R I qu cijeli brojevi p = pqn M, tajO odnosi su zadovoljni

Zato

Sada imamo

Tablica 10.1 sažima RSA algoritam, a sl. Na slici 10.1 prikazan je primjer njegove primjene. U ovom primjeru, ključevi se izračunavaju na sljedeći način:

1. Izabrana su dva prosta broja: p- 7 wq- 17.
2. Izračunato p = pq= 7 x 17 = 119.
3. Izračunajte f (p) - (p -) (q - 1) = 96.
4. Odabrano e, koprim s f (P)= 96 i manji od f(i); u ovom slučaju = 5.
5. Ovo je određeno d,Što de= 1 (mod 96) i d 96. Odgovarajuća bi vrijednost bila d= 77, budući da je 77 x 5 = 385 = 4 x 96 + 1.
6. Rezultat je javni ključ KU = (5, 119) i privatni ključ KR = (77, 119).

Ovaj primjer pokazuje upotrebu ovih ključeva s unosom otvorenog teksta M = 19. Prilikom šifriranja, 19 se podiže na petu potenciju, što rezultira u 2,476,099, što daje ostatak od 66. Prema tome, 19 5 = 66 (mod 119). , pa će stoga šifrirani tekst biti 66. Nakon dešifriranja ispada da

Riža. 10.1.

Tablica 10.1