Što je RSA enkripcija i kako to radi?

RSA enkripcija je sustav koji rješava ono što je nekad bio jedan od najvećih problema u kriptografiji: Kako nekome možete poslati kodiranu poruku bez prilike da prethodno dijele kôd s njima?

Ovaj će vas članak naučiti svemu što trebate znati kako je razvijena RSA enkripcija, kako radi, matematiku iza toga, za što se koristi kao i neki od najveći sigurnosni problemi s kojima se suočava. Učenje o RSA pružit će vam neko temeljno znanje koje vam pomaže da shvatite koliko je dijelova našeg mrežnog života zaštićeno.

Što je RSA enkripcija?

Recimo da želite reći prijatelju tajnu. Ako ste odmah do njih, možete to samo šaputati. Ako se nalazite na suprotnim stranama zemlje, to očito neće uspjeti. Možete to zapisati i poslati im e-poštu ili koristiti telefon, ali svaki od tih kanala komunikacije je nesiguran i svatko s dovoljno jakom motivacijom mogao bi lako presresti poruku.

Ako je tajna bila dovoljno važna, ne biste je rizikovali normalno zapisati – špijuni ili je neki loš zaposlenik pošte mogao pregledavati vašu poštu. Isto tako, netko može prisluškivati ​​vaš telefon bez vašeg znanja i bilježiti svaki vaš poziv.

Jedno od rješenja za sprječavanje prisluškivanja pristupa sadržaju poruke jest šifrirajte ga. To u osnovi znači dodati kodu poruku koja ju pretvara u zbrku. Ako je vaš kôd dovoljno složen, jedini ljudi koji će moći pristupiti originalnoj poruci su oni koji imaju pristup kôdu.

Ako ste imali priliku ranije podijeliti kôd sa svojim prijateljem, onda bilo koji od vas može u bilo kojem trenutku poslati šifriranu poruku, znajući da ste vas dvojica jedini koji imaju mogućnost čitanja sadržaja poruke. Ali što ako niste imali priliku ranije podijeliti kôd?

Ovo je jedan od temeljnih problema kriptografije, koji je riješio sheme enkripcije javnih ključeva (poznate i kao asimetrična enkripcija) poput RSA.

Pod RSA enkripcijom poruke se šifriraju s kodom koji se zove a javni ključ, koji se mogu otvoreno dijeliti. Zbog nekih različitih matematičkih svojstava algoritma RSA, Nakon što je poruka šifrirana javnim ključem, može je dešifrirati samo drugi ključ, poznat kao privatni ključ. Svaki RSA korisnik ima par ključeva koji se sastoji od njihovih javnih i privatnih ključeva. Kao što ime sugerira, privatni ključ mora biti čuvan u tajnosti.

Sheme enkripcije javnih ključeva razlikuju se od enkripcija simetričnog ključa, gdje i šifriranje i dešifriranje koriste isti privatni ključ. Te razlike čine šifriranje javnih ključeva poput RSA korisnim za komunikaciju u situacijama kada prethodno nije bilo mogućnosti sigurne distribucije ključeva..

Algoritmi za simetrični ključ imaju vlastite aplikacije, poput šifriranja podataka za osobnu upotrebu ili kada postoje sigurni kanali preko kojih se privatni ključevi mogu dijeliti.

Vidi također: Kriptografija javnog ključa

Gdje se koristi RSA enkripcija?

RSA enkripcija se često koristi u sustavu kombinacija s drugim shemama šifriranja, ili za digitalni potpisi što može dokazati autentičnost i cjelovitost poruke. Obično se ne koristi za šifriranje cijelih poruka ili datoteka, jer je manje učinkovita i teška za resurse od šifriranja ključa sa simetričnim ključem..

Da bi stvar bila učinkovitija, datoteka će općenito biti šifrirana algoritmom simetričnog ključa, a potom će se simetrični ključ kriptirati RSA enkripcijom. U ovom će procesu samo entitet koji ima pristup privatnom ključu RSA moći dešifrirati simetrični ključ.

Bez mogućnosti pristupanja simetričnom ključu, originalna se datoteka ne može dešifrirati. Ova se metoda može koristiti za zaštitu poruka i datoteka, bez predugog trošenja i ne trošenja previše računskih resursa.

RSA enkripcija može se koristiti u više različitih sustava. Može se implementirati u OpenSSL, wolfCrypt, kriptlib i niz drugih kriptografskih knjižnica.

Kao jedna od prvih široko korištenih shema šifriranja javnih ključeva, RSA je postavila temelje mnogih naših sigurnih komunikacija. Bilo je koji se tradicionalno koristi u TLS a bio je i izvorni algoritam koji se koristio u šifriranju PGP-a. RSA se i dalje može vidjeti u različitim web preglednicima, e-pošti, VPN-ovima, chatu i drugim komunikacijskim kanalima.

RSA se također često koristi za povezivanje između VPN klijenata i VPN poslužitelja. Pod protokolima kao što je OpenVPN, TLS rukovanje može koristiti RSA algoritam za razmjenu ključeva i uspostavljanje sigurnog kanala.

Pozadina RSA enkripcije

Kao što smo spomenuli na početku ovog članka, prije šifriranja javnim ključem bio je izazov sigurno komunicirati ako prije nije postojala prilika da sigurno razmijenimo ključeve. Ako nije bilo mogućnosti dijeljenja koda prije vremena ili sigurnog kanala preko kojeg bi se mogli distribuirati ključevi, ne bi bilo načina da komuniciraju bez prijetnje da će neprijatelji moći presresti i pristupiti sadržaju poruke.

Tek su se sedamdesete stvari počele mijenjati. Prvi veliki razvoj prema kriptografiji s javnim ključem objavio je početkom desetljeća James H. Ellis. Ellis nije mogao pronaći način da sprovede svoj posao, ali njegov kolega Clifford Cocks proširio ga je i postao ono što sada znamo kao RSA enkripcija.

Konačni dio slagalice je ono što sada zovemo Razmjena ključeva Diffie-Hellman. Malcolm J. Williamson, drugi suradnik, smislio je shemu koja je omogućila dvjema stranama da dijele ključ za šifriranje, čak i ako kanal nadziru protivnici.

Sav taj posao poduzeo je u britanskoj obavještajnoj agenciji, Vladinom sjedištu za komunikacije (GCHQ), koje je držao otkriće klasificiranim. Djelomično zbog tehnoloških ograničenja, GCHQ tada nije mogao vidjeti korištenje kriptografije s javnim ključem, tako da je razvoj nepomično sjedio na polici i skupljao prašinu. Tek je 1997. delo deklasificirano i priznati izvorni izumitelji RSA.

Nekoliko godina kasnije slični pojmovi počeli su se razvijati u javnoj sferi. Ralph Merkle stvorio je rani oblik kriptografija s javnim ključem, što je utjecalo na Whitfield Diffieja i Martina Hellmana u dizajnu razmjene ključeva Diffie-Hellman.

Diffie-jevim i Hellmanovim idejama nedostajao je jedan važan aspekt koji bi njihov rad učinio temeljem kriptografije javnog ključa. Ovo je bio a jednosmjerna funkcija koju bi bilo teško invertirati. 1977. godine, Ron Rivest, Adi Shamir i Leonard Adleman, čija su prezimena akronim RSA, pronašlo je rješenje nakon godinu dana truda oko problema.

Akademici sa sjedišta na MIT-u napravili su svoj proboj nakon pashalne zabave 1977. Rivest je, nakon jedne noći pijenja, otišao kući, ali umjesto da spava, grozničavo je proveo večer pišući rad koji je formalizirao njegovu ideju za potrebnu jednosmjernu funkciju.

Ideju je patentirao 1983. godine MIT, ali tek je ranih dana na internetu algoritam RSA počeo široko prihvaćati kao važan sigurnosni alat.

Kako radi RSA enkripcija?

Sljedeće će predstavljati malo pojednostavljenje, jer je previše čitatelja vjerojatno preplašio njihov učitelj matematike u srednjoj školi. Kako bismo spriječili da nam se matematika previše ne nadmaši pojednostavljivanje nekih koncepata i upotreba mnogo manjih brojeva. U stvarnosti, RSA enkripcija koristi jednostavne brojeve koji su mnogo veći i postoji nekoliko drugih složenosti.

Nekoliko ćete različitih koncepata morati zaobići kako bismo mogli objasniti kako se sve to uklapa. Oni uključuju zamkačke funkcije, generiranje prašuma, Carmichaelova totientska funkcija i odvojene procese koji su uključeni u to računanje javnih i privatnih ključeva koristi se u postupcima šifriranja i dešifriranja.

Funkcije klopnih vrata

RSA enkripcija radi pod pretpostavkom da je algoritam lako je izračunati u jednom smjeru, ali gotovo nemoguće obrnuto. Na primjer, ako bi vam rekli da je 701,111 proizvod dvaju pravih brojeva, biste li mogli shvatiti koji su to dva broja?

Čak i s kalkulatorom ili računalom, većina nas ne bi imala pojma odakle započeti, a kamoli biti u stanju shvatiti odgovor. Ali ako stvari preokrenemo, postaje mnogo lakše. Što je rezultat:

907 x 773

Ako bi vam bilo dovoljno dosadno, mogli biste izvaditi telefon ili ga možda izračunati u glavi da otkrijete da je odgovor prethodno spomenuti 701,111. Ovi 907 i 773 su primarni brojevi koji daju odgovor na naše prvo pitanje, što nam pokazuje da određene jednadžbe možemo lako shvatiti na jedan način, ali obrnuto naizgled nemoguće.

Još jedan zanimljiv aspekt ove jednadžbe je da je lako utvrditi jedan od glavnih brojeva ako već imate drugi, kao i proizvod. Ako vam je rečeno da je 701,111 rezultat 907 pomnožen s drugim jednostavnim brojem, možete to shvatiti sa drugim jednadžbom sljedećom jednadžbom:

701,111 ÷ 907 = 773

Kako je odnos između tih brojeva jednostavno izračunati u jednom smjeru, ali obrnuto je težak, jednadžba je poznata kao funkcija zamka vrata. Imajte na umu da, iako je gornji primjer teško shvatiti, računala mogu obavljati operaciju u trivijalnom vremenskom roku.

Zbog toga RSA koristi mnogo veće brojeve. Veličina prajdova u stvarnoj RSA implementaciji varira, ali u 2048-bitnom RSA-u oni bi se sastavili kako bi napravili ključeve duge 617 znamenki. Da biste vam olakšali vizualizaciju, ključan bi bio broj ove veličine:

99999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

Stvaranje prašuma

Spomenute funkcije zamka vrata čine osnovu za funkcioniranje shema šifriranja javnih i privatnih ključeva. Njihova svojstva omogućuju dijeljenje javnih ključeva bez ugrožavanja poruke ili otkrivanja privatnog ključa. Također omogućuju šifriranje podataka jednim ključem na način koji drugi dešifrirani ključ može dešifrirati iz para.

Prvi korak šifriranja poruke s RSA-om je generiraju ključeve. Da bismo to učinili, trebamo dva glavna broja (p i q) koji su odabrani testom primalnosti. Test primalnosti je algoritam koji efikasno pronalazi jednostavne brojeve, kao što je test primarnosti Rabin-Miller.

Primarni brojevi u RSA moraju biti jako veliki, a također i relativno udaljeni. Brojevi koji su mali ili bliže jedan drugom mnogo je lakše probiti se. Unatoč tome, naš će primjer upotrijebiti manje brojeve kako bi se stvari lakše pratile i računale.

Recimo da nam test primalnosti daje primarne brojeve koje smo koristili gore, 907 i 773. Sljedeći je korak otkrivanje modula (n), koristeći sljedeću formulu:

n = p x q

Gdje p = 907 i q = 773

Stoga:

n = 907 x 773

n = 701,111

Carmichaelova totientska funkcija

Jednom jesmo n, koristimo Carmichaelova totička funkcija:

    λ(n) = LCM (p – 1, q – 1)

Ako je prošlo dosta vremena otkako ste pogodili udžbenike matematike, gore navedeno može izgledati pomalo zastrašujuće. Možete preskočiti ovaj dio i samo vjerovati da matematika funkcionira, a u protivnom se pridržavajte još nekoliko izračuna. Sve će vam biti objašnjeno u što većem broju detalja kako bi vam pomoglo da se oko glave temeljite.

Za one koji nisu svjesni, λ (n) predstavlja Carmichael za koji se lijepi n, dok LCM znači najniži zajednički višestruki, što je najmanji broj koji su oboje p i q mogu se podijeliti u. Postoji nekoliko različitih načina kako to shvatiti, ali najlakši je povjerenje internetskom kalkulatoru koji će jednadžbu napraviti za vas. Pa, stavimo naše brojeve u jednadžbu:

    λ(701111) = LCM (907 – 1, 773 – 1)

    λ(701111) = LCM (906, 772)

   Pomoću gore navedenog kalkulatora dobijemo:

    λ(701111) = 349.716

Stvaranje javnog ključa

Sad kad imamo Carmichael-ov najčešći broj, to je stvar, vrijeme je da shvatimo naš javni ključ. Pod RSA, javni ključevi sastoje se od pravog broja e, kao i n. Broj e može biti između 1 i vrijednosti za λ(n), što u našem primjeru iznosi 349.716.

Budući da se javni ključ otvoreno dijeli, to nije toliko važno e da bude slučajni broj. U praksi, e općenito je postavljeno na 65.537, jer kad se puno veći broj odabere nasumično, to šifriranje čini mnogo manje učinkovitim. Za današnji će primjer biti zadržani mali brojevi kako bi proračuni bili učinkoviti. Recimo:

e = 11

Naši konačni šifrirani podaci nazivaju se šifrirani tekst (c). To izvedemo iz naše otvorene poruke (m), primjenom javnog ključa sa sljedećom formulom:

c = me mod n

Već smo smislili e i znamo n također. Jedino što moramo objasniti je modni. To je malo izvan dubine ovog članka, ali odnosi se na modulski rad, što u suštini znači ostatak koji vam ostaje kad podijelite jednu stranu na drugu. Na primjer:

10 modni 3 = 1

To je zato što 3 ulazi u 10 tri puta, a ostatak 1.

Natrag do naše jednadžbe. Da stvari budu jednostavne, recimo to poruka (m) koje želimo šifrirati i čuvati u tajnosti samo je jedan broj, 4. Uključimo sve u:

c = me modni n

c = 411 modni 701111

c = 4,194,304 modni 701111

Opet, da napravimo modulski rad lako, koristit ćemo internetski kalkulator, ali vi to možete shvatiti sami. Unosom 4.194.304 u mrežni kalkulator daje nam:

c = 688.749

Zbog toga kada koristimo RSA za šifriranje naše poruke, 4, s našim javnim ključem, daje nam šifrirani tekst 688.749. Prethodni koraci možda su izgledali previše teški matematički, ali važno je ponoviti što se zapravo dogodilo.

Imali smo poruka od 4, koju smo željeli zadržati u tajnosti. Na njega smo primijenili javni ključ, koji nam je dao šifrirani rezultat od 688,749. Sad kad je šifriran, broj 688,749 možemo sigurno poslati vlasniku para ključeva. Oni su jedina osoba koja će to moći dešifrirati svojim privatnim ključem. Kad ga dešifriraju, vidjet će poruku koju smo stvarno poslali, 4.

Generiranje privatnog ključa

U RSA enkripciji, nakon što se podaci ili poruka pretvore u šifrični tekst javnim ključem, on se može dešifrirati samo privatnim ključem iz istog para ključeva. Privatni se ključevi sastoje od d i n. Već znamo n, a za pronalaženje se koristi sljedeća jednadžba d:

d = 1 /e mod λ(n)

U Stvaranje javnog ključa odjeljak iznad, to smo već odlučili u našem primjeru, e bilo bi jednako 11. Slično tome, znamo to λ(n) jednak je 349,716 iz našeg ranijeg rada pod Carmichaelova totientska funkcija. Stvari se malo slože kada naiđemo na ovaj odjeljak formule:

1 /e modni

Ova jednadžba može izgledati kao da traži da podijelite 1 na 11, ali to nije slučaj. Umjesto toga, to samo simbolizira da moramo izračunati modularni inverzni od e (što je u ovom slučaju 11) i λ(n) (što u ovom slučaju iznosi 349.716).

To u suštini to znači umjesto da izvodimo standardnu ​​operaciju modula, koristit ćemo obrnuto. To se obično nalazi s proširenim euklidskim algoritmom, ali to je malo izvan okvira ovog članka, pa ćemo umjesto toga samo prevariti i koristiti internetski kalkulator. Sada kada razumijemo sve što se događa, uključimo naše podatke u formulu:

d = 1 /11 modni 349716

Za izvođenje ove operacije jednostavno unesite 11 (ili bilo koju vrijednost koju možda imate e ako to pokušavate vlastitim primjerom) gdje piše Integer i 349.716 (ili bilo koju vrijednost koju možda imate λ(n) ako to pokušavate vlastitim primjerom) gdje piše modulo u mrežnom kalkulatoru koji je gore naveden. Ako ste to ispravno učinili, trebali biste dobiti rezultat gdje:

d = 254, 339

Sada kada imamo vrijednost za d, možemo dešifrirati poruke koje su šifrirane našim javnim ključem pomoću sljedeće formule:

m = cd mod n

Sada se možemo vratiti na šifrirani tekst koji smo šifrirali ispod Generiranje privatnog ključa odjeljak. Kad smo poruku šifrirali javnim ključem, ona nam je dala vrijednost c od 688.749. Odozgo to znamo d jednako 254.339. To također znamo n jednako 701,111. To nam daje:

m = 688.749254339 modni 701111.

Kao što ste možda primijetili, pokušaj da se broj prebaci na 254.339. moć mogao bi biti većinom za većinu normalnih kalkulatora. Umjesto toga, koristit ćemo internetski kalkulator dešifriranja RSA. Ako biste željeli koristiti drugu metodu, primijenili biste ovlasti kao i obično i izveli operaciju modula na isti način kao što smo učinili u Stvaranje javnog ključa odjeljak.

U gornji kalkulator unesite tamo 701.111 gdje piše Modul opskrbe: N, 254.399 gdje piše Ključ za dešifriranje: D, i 688.749 gdje piše Šifrična poruka u numeričkom obliku, kao što je prikazano niže:

Nakon što unesete podatke, pritisnite Dekodiranje, koji će brojeve stavljati kroz gornju formulu dešifriranja. Tako ćete dobiti originalnu poruku u donjem okviru. Ako ste sve učinili pravilno, trebali biste dobiti odgovor 4, koja je bila originalna poruka koju smo šifrirali svojim javnim ključem.

Kako RSA enkripcija funkcionira u praksi

Gornji odjeljci trebali bi vam razumjeti kako funkcionira matematika koja stoji iza šifriranja javnih ključeva. To može biti malo zbunjujuće, ali čak i oni koji nisu razumjeli sitnice jednadžbi mogu vam nadamo oduzeti neke važne podatke o procesu.

U gore navedenim koracima pokazali smo kako dva subjekta mogu sigurno komunicirati, a da prethodno nisu podijelili kôd. Prvo, svi trebaju uspostaviti vlastite parove ključeva i dijeliti javni ključ jedni s drugima. Dva entiteta moraju čuvati svoje privatne ključeve u tajnosti kako bi komunikacija ostala sigurna.

Jednom kada pošiljatelj ima javni ključ svog primatelja, on ih može upotrijebiti za šifriranje podataka za koje želi da ostane siguran.. Jednom kada je šifriran javnim ključem, on se može dešifrirati samo privatnim ključem iz istog para ključeva. Čak se isti javni ključ ne može upotrijebiti za dešifriranje podataka. To je zbog svojstava funkcije zamki vrata koje smo gore spomenuli.

Kad primatelj primi šifriranu poruku, oni koriste svoj privatni ključ za pristup podacima. Ako primatelj želi vratiti komunikaciju na siguran način, oni tada mogu šifrirati svoju poruku javnim ključem stranke s kojom komuniciraju. Ponovno, nakon što je šifriran javnim ključem, jedini način da se pristupi informacijama je kroz odgovarajući privatni ključ.

Na taj način, nepoznate strane mogu RSA enkripciju koristiti za sigurno slanje podataka među sobom. Značajni dijelovi komunikacijskih kanala koje koristimo u našim mrežnim životima izgrađeni su od ove temelje.

Kako su složenije poruke šifrirane s RSA-om?

U našem primjeru stvari smo mnogo pojednostavili kako bismo ih lakše razumjeli, zbog čega smo samo šifrirali poruku “4”. Mogućnost šifriranja broja 4 ne čini se posebno korisnom, pa biste se možda pitali kako možete šifrirati složeniji skup podataka, poput simetričnog ključa (koji se najčešće koristi RSA) ili čak poruke.

Neki se mogu zbuniti kako ključ poput “n38cb29fkbjh138g7fqijnf3kaj84f8b9f …” ili poruka poput “kupi mi sendvič” može se kriptirati algoritmom poput RSA, koji se bavi brojevima, a ne slovima. Realnost je da su sve informacije koje naša računala obrađuju pohranjene u binarnim (1 i 0) i koristimo standarde kodiranja poput ASCII ili Unicode da ih predstavljaju na načine koje ljudi mogu razumjeti (slova).

Ovo znači to ključevi poput “n38cb29fkbjh138g7fqijnf3kaj84f8b9f …”, a poruke poput “kupi mi sendvič” već postoje kao brojevi, koje se lako mogu izračunati u algoritmu RSA. Brojevi kojima su oni predstavljeni mnogo su veći i teže nam je upravljati, zato se radije bavimo alfanumeričkim znakovima, a ne žurnom binarnom snagom.

Ako želite kodirati ključ duže sesije ili složeniju poruku s RSA-om, to bi jednostavno uključivalo puno veći broj.

punjenje

Kad se implementira RSA, koristi se nešto što se zove padding kako bi se spriječio veći broj napada. Da bismo objasnili kako to funkcionira, počet ćemo s primjerom. Recimo da prijatelju šaljete kodiranu poruku:

Draga Karen,

    Nadam se da si dobro. Hoćemo li sutra večerati?

    S poštovanjem,

    James

Recimo da ste poruku kodirali na jednostavan način mijenjajući svako slovo na ono koje ga slijedi u abecedi. To bi promijenilo poruku u:

Efbs Lbsfo,

    J ipqf zpv bsf xfmm. Bsf xf tujmm ibwjoh ejoofs upnpsspx?

    Zpvst tjodfsfmz,

    Kbnft

Ako su vaši neprijatelji presreli ovo pismo, postoji trik koji bi oni mogli upotrijebiti za isprobavanje koda. Mogli su pogledajte format svog pisma i pokušajte pogoditi o čemu bi se moglo govoriti. Oni znaju da ljudi obično započinju svoja slova sa “Bok”, “Zdravo”, “Poštovani” ili nizom drugih konvencija.

Kada bi pokušali primijeniti “Bok” ili “Zdravo” kao prvu riječ, vidjeli bi da to ne bi odgovaralo broju znakova. Tada bi mogli isprobati “Dragi”. Odgovara, ali to ne mora nužno ništa značiti. Napadači bi to samo pokušali i vidjeli gdje ih je vodio. Tako bi promijenili slova “e”, “f”, “b”, i “s” s “d”, “e”, “a”, odnosno “r”. To bi im omogućilo:

Dragi Laseo,

    J ipqe zpv su xemm. Jesu li xe tujmm iawjoh djooes upnpsspx?

    Zpvrt tjoderemz,

    Kanet

I dalje izgleda prilično zbunjujuće, pa bi napadači mogli pokušati pogledati neke druge konvencije, kako zaključujemo svoja pisma. Ljudi često na kraju dodaju “From” ili “Srdačan pozdrav”, ali nijedan od njih ne odgovara formatu. Umjesto toga, napadači bi mogli isprobati “S poštovanjem” i zamijeniti druga slova da bi vidjeli gdje ih vodi. Promjenom “z”, “p”, “v”, “t”, “j” “o”, “d” i “m” s “y”, “o”, “u”, “s”, ” i “,” n “,” c “i” l “, dobili bi:

Dragi Lasen,

    Pretpostavljam da ste kreten. Jesu li xe tuill iawinh dinnes uonossox?

    S poštovanjem,

    Kanet

Nakon te modifikacije, izgleda da napadači počinju negdje stići. Pronašli su riječi “ja”, “ti” i “jesu”, uz riječi koje su tvorile njihova početna nagađanja.

Gledajući kako su riječi u pravilnom gramatičkom poretku, napadači mogu biti prilično sigurni da idu u pravom smjeru. Do sada su vjerojatno shvatili i da kod uključuje promjene svakog slova u ono koje slijedi na abecedi. Jednom kada to shvate, olakšava se prevođenje ostatka i čitanje izvorne poruke.

Gornji primjer bio je samo jednostavan kod, ali kao što vidite, struktura poruke može dati napadačima tragove o njenom sadržaju. Naravno, bilo je teško shvatiti poruku samo iz njezine strukture i trebalo je nekih obrazovanih nagađanja, ali morate imati na umu da su računala mnogo bolja u tome nego mi. To znači da se pomoću njih mogu utvrditi daleko složeniji kodovi u mnogo kraćem vremenu, zasnovan na tragovima koji potječu od strukture i drugih elemenata.

Ako struktura može dovesti do pucanja koda i otkrivanja sadržaja poruke, onda nam treba neki način da sakrijemo strukturu da bismo poruku sačuvali u sigurnosti. To nas dovodi do punjenje.

Kad je poruka podstavljena, dodaju se nasumični podaci kako bi se sakrili izvorni tragovi oblikovanja koji bi mogli dovesti do kršenja šifrirane poruke. S RSA-om stvari su malo složenije, jer šifrirani ključ nema očigledno oblikovanje pisma koje bi nam pomoglo da nam da tragove u našem gornjem primjeru..

Unatoč tome, protivnici mogu upotrijebiti brojne napade kako bi iskoristili matematička svojstva koda i razbili šifrirane podatke. Zbog ove prijetnje, implementacije RSA koriste sheme padding-a kao što je OAEP za umetanje dodatnih podataka u poruku. Dodavanje ove obloge prije šifriranja poruke čini RSA mnogo sigurnijim.

Potpisivanje poruka

RSA se može koristiti za šifriranje podataka. Njegova svojstva čine ga korisnim i za potvrđujući da je poruku poslao subjekt koji tvrdi da ju je poslao, kao i da dokazuje da poruka nije izmijenjena ili neovlaštena.

Kad netko želi dokazati autentičnost svoje poruke, može izračunati a paprikaš (funkcija koja uzima podatke proizvoljne veličine i pretvara ih u vrijednost fiksne duljine) u otvorenom tekstu, a zatim ih potpisuje svojim privatnim ključem. Oni potpišite hash primjenom iste formule koja se koristi kod dešifriranja (m = cd mod n). Kad se poruka potpiše, oni će digitalni potpis poslati primatelju zajedno s porukom.

Ako primatelj primi poruku s digitalnim potpisom, može ih koristiti potpis da provjeri je li poruka autentično potpisana privatnim ključem osobe koja tvrdi da ju je poslala. Oni također mogu vidjeti jesu li napadači promijenili poruku nakon što je poslana.

Da bi provjerio digitalni potpis, primatelj prvo koristi istu funkciju raspršivanja kako bi pronašao hash vrijednost poruke koju je primio. Primatelj tada primjenjuje javni ključ pošiljatelja na digitalni potpis, pomoću formule šifriranja (c = me mod n), da im daju hash digitalnog potpisa.

Po uspoređujući hash poruke koja je primljena uporedo sa hash-om iz šifriranog digitalnog potpisa, primatelj može reći je li poruka vjerodostojna. Ako su dvije vrijednosti iste, poruka nije promijenjena otkako je potpisana od originalnog pošiljatelja. Da je poruku promijenio čak i jedan znak, vrijednost hash-a bila bi potpuno drugačija.

Sigurnost RSA & napadi

Kao i većina kriptosistema, sigurnost RSA ovisi o tome kako se provodi i koristi. Važan čimbenik je veličina ključa. što je veći broj bita u ključu (u osnovi koliko je ključ dug), to je teže probiti se napadima kao što su brutalno forsiranje i faktoring.

Budući da se algoritmi asimetričnih ključeva poput RSA mogu slomiti cjelobrojnom faktorizacijom, dok algoritmi simetričnih ključeva poput AES ne mogu, RSA ključevi trebaju biti puno duži da bi postigli istu razinu sigurnosti.

Trenutno je najveća veličina ključa koja se bilježi je dugačka 768 bita. To je učinio tim akademika u razdoblju od dvije godine, koristeći stotine strojeva.

Budući da je faktoring završen krajem 2009. godine i računska snaga je značajno porasla od tog vremena, može se pretpostaviti da je pokušaj sličnog intenziteta sada bi mogao uzeti u obzir mnogo veći RSA ključ.

Unatoč tome, vrijeme i resursi potrebni za ovakav napad stavljaju ga van dosega većine hakera i u područje nacionalnih država. Najbolja duljina ključa za korištenje ovisit će o vašem pojedinačnom modelu prijetnji. Nacionalni institut za standarde i tehnologiju preporučuje minimalnu veličinu ključa od 2048-bitni, ali koriste se i 4096-bitni ključevi u nekim situacijama kada je razina prijetnje veća.

Faktoring je samo jedan od načina na koji RSA može biti probijen. Brojni drugi napadi mogu razbiti šifriranje s manjom količinom resursa, ali oni ovise o implementaciji i drugim faktorima, a ne nužno i samom RSA-u. Neki od njih uključuju:

Jesu li primi stvarno slučajni?

Neke implementacije RSA koriste slabe generatore slučajnih brojeva kako bi osmislili prim. Ako ovi brojevi nisu dovoljno slučajni, napadači znatno olakšavaju faktoritiranje i probijanje šifriranja. Ovaj problem može se izbjeći korištenjem kriptografski sigurnog generatora pseudo slučajnih brojeva.

Loša generacija ključeva

RSA ključevi trebaju potpasti unutar određenih parametara da bi bili sigurni. Ako primes p i q su preblizu zajedno, ključ se lako može otkriti. Isto tako, broj d koji čini dio privatnog ključa ne može biti premalen. Mala vrijednost olakšava rješavanje. Važno je da ti brojevi budu odgovarajuće duljine kako bi vaš ključ bio siguran.

Napadi bočnih kanala

To su vrsta napada koji ne razbijaju RSA izravno, već umjesto toga koriste informacije iz njegove implementacije kako bi napadačima dali naputke o procesu šifriranja. Ti napadi mogu uključivati ​​i stvari poput analizirajući količinu snage koja se koristi, ili analiza predviđanja grana, koji koristi mjerenje vremena izvršenja za otkrivanje privatnog ključa.

Druga vrsta napada bočnih kanala poznata je kao vremenski napad. Ako napadač može izmjeriti vrijeme dešifriranja na ciljnom računalu za brojne različite šifrirane poruke, ove informacije napadaču mogu omogućiti utvrđivanje ciljanog privatnog ključa.

Većina implementacija RSA izbjegava ovaj napad dodavanjem jednokratne vrijednosti tijekom postupka šifriranja, što uklanja ovu korelaciju. Taj se proces zove kriptografsko zasljepljivanje.

Je li RSA enkripcija sigurna za budućnost?

Dobra vijest je da se RSA smatra sigurnom za uporabu, unatoč tim mogućim napadima. Upozorenje je to treba ga pravilno implementirati i upotrijebiti ključ koji spada u točne parametre. Kao što smo već raspravljali, implementacije koje ne upotrebljavaju padding, koriste neprimjerene primjere ili imaju druge ranjivosti ne mogu se smatrati sigurnim.

Ako želite koristiti RSA enkripciju, pazite da koristite tipku od najmanje 1024 bita. Oni s modelima veće prijetnje trebaju se držati ključeva od 2048 ili 4096 bita ako žele s pouzdanjem koristiti RSA. Sve dok ste svjesni slabosti koje RSA ima i pravilno ih koristite, trebali biste se osjećati sigurno koristiti RSA za dijeljenje ključeva i druge slične zadatke koji zahtijevaju šifriranje javnih ključeva.

Vidi također: Objašnjene su uobičajene vrste šifriranja