RSA, je li stvarno tako jednostavno? Odabir parametara RSA šifre i moguće posljedice Šifriranje korištenjem RSA algoritma

Ne znaju svi korisnici osobne računalne opreme što je RSA enkripcija i iznenade se kada čuju ovaj izraz. Ali u ovom konceptu nije skriveno ništa komplicirano. RSA enkripcija je samo kriptosustav koji vam omogućuje sigurno korištenje svih elektroničkih podataka stvorenih na računalnoj tehnologiji. Ovo nije dešifriranje podataka, gdje se datoteke ne mogu čitati bez poznavanja određenog koda. RSA enkripcija podrazumijeva da su ključevi otvoreni.

RSA enkripcija radi na principu faktoringa. Kao ovo? A ovo je faktoring
reprodukcija dva velika numerička podatka.

Tko je stvorio RSA enkripcijski sustav?

RSA enkripcijski algoritam nastao je davne 1977. godine, njegovi tvorci su znanstvenici Rivest, Shamir, Adleman, a skraćenica od početnih slova njihovih prezimena čini pojam RSA. Raniji algoritam razvio je Clifford Cox, matematičar iz Engleske koji je radio za tamošnju obavještajnu službu. Godine 1973. uspio je stvoriti ekvivalentni sustav, ali su ga koristili isključivo klasificirani pojedinci, a tehnika nije bila distribuirana na razini običnih korisnika opreme za osobno računalo.

Kako radi RSA enkripcija?

Korisnik sustava prvo kreira, a zatim objavi javni ključ koji se temelji na dva velika broja, samo s pomoćnom vrijednošću. Najjednostavniji brojevi se drže u tajnosti. Da biste, primjerice, pročitali e-poštu, samo trebate upotrijebiti javni ključ dokumenta, ali ako je ključ dugačak, tada postaje teško pristupiti informacijama.

Danas se RSA enkripcija karakterizira kao ne baš pouzdan način šifriranja podataka. Ovo je spor algoritam, pa nije tako uobičajen među običnim korisnicima računala. Pa zašto je onda stvoren ovaj sustav ako ga obični informatičari praktički ne koriste?

Stvar je u tome što je svoju primjenu našao u šifriranom prijenosu javnih ključeva za simetrični enkripcijski ključ, koji je dizajniran za skupno šifriranje i dešifriranje velikom brzinom.

Moderni kriptosustav asimetričnog ključa pojavio se zahvaljujući radu Diffieja i Hellmana. Koncept su razvili 1976. godine i predstavili ga javnosti kao digitalne snimke. Uspjeli su stvoriti javni ključ temeljen na načelu potenciranja određenog broja modulo prostog broja. No njihov je princip ostao lebdjeti u zraku, jer u to vrijeme sami principi faktoringa još nisu bili dobro proučeni.

Rivest, Adim Shamir, Adleman nisu se zaustavili na prethodno postignutom, te su temeljito razradili mehanizam jednosmjerne funkcije koju nije tako lako dekodirati. Rivest i Shamir radili su izravno na samim funkcijama, a Adleman je tražio slabosti u algoritmima koji su se stvarali. Na kraju su uspjeli stvoriti RSA sustav asimetričnih ključeva.

Digitalni potpis i komunikacija javnim ključem

Trenutno mnoge tvrtke koriste takav elektronički element kao digitalni potpis u svojim radnim aktivnostima. Izrađeni elektronički dokumenti koji sadrže tzv. digitalni potpis službeni su dokumenti priznati na zakonskoj razini. Elektronički digitalni potpis nastaje kada se podaci kriptografski mijenjaju.

Ova alternativa konvencionalnom potpisu omogućuje da se dokument učini povjerljivim, osigura njegov integritet i da uvijek imate informacije o njegovom kreatoru i vlasniku.

Elektronički potpis je usko povezan s predmetnom RSA enkripcijom. Ovaj sustav, kao što je gore spomenuto, pretpostavlja prisutnost javnog ključa. Danas se u praksi koriste dva ključa - javni - svima poznat i privatni - kriptirani kako bi se neovlaštenim osobama onemogućio pristup informacijama.

Tako javni ključ omogućuje pristup dokumentu s elektroničkim pečatom, a privatni ključ dekriptiranje potpisa i njegovu provjeru. Drugim riječima, RSA enkripcija omogućuje vam skrivanje dokumenata od znatiželjnih očiju, čuvanje tajnosti, ali uz mogućnost pristupa njima u pravom trenutku.

Hajde da shvatimo što je suština izumljenog algoritma?

RSA enkripcija radi u četiri faze:
generiranje ključeva;
distribucija ključeva;
šifriranje ključem;
dešifriranje ključeva.

Načelo RSA enkripcije kombinira stvaranje javnih i privatnih ključeva. Zaustavimo se opet na ovome. Otvoreno – poznato svima, može se koristiti za šifriranje poruka. Ovi elektronički podaci mogu se dešifrirati pomoću privatnog ključa. Kod kreiranja javnih ključeva brojevi se biraju nasumično i iste su veličine, ali različiti u trajanju zapisa, pa je faktoring teži.

Identični brojevi se pronalaze testiranjem njihove jednostavnosti. Tako je šifriranje postupno postalo složenije. Od čega se sastoji javni ključ? A sastoji se od redovnog modula i takozvanog javnog eksponenta. Ali zatvoreni uključuje modul i privatni indikator, koji se ne daje nikome osim kreatoru.

Slabosti tehnike RSA enkripcije

Unatoč dobro osmišljenom principu šifriranja, može se lako razbiti. To se može učiniti ako su za izradu ključeva korišteni mali brojevi; ključ se može otkriti jednostavnim odabirom jednostavnih cijelih brojeva.

Sama RSA enkripcija algoritam je koji eliminira nasumične komponente, što prevarantima računalne mreže olakšava razbijanje determinističkog mehanizma uspoređujući ga s otvorenim tekstom Dos napada, koji provjeravaju jesu li pokrenuti tekstovi trajno jednaki u duljini generiranim ključevima.

A to, prije svega, objašnjava da RSA enkripcija nije isti kriptosustav koji je u svakom pogledu siguran za očuvanje elektroničkih podataka od napada neželjenih osoba. Osim ako se doda naprednijim poslužiteljima, ne dobije takva svojstva.

Dodatne komponente koje osiguravaju sigurnost korištenja RSA enkripcije

Kako bi spriječili mogućnost hakiranja enkripcije RSA formata, programeri u nju ugrađuju oblik strukturiranog, takozvanog nasumičnog punjenja, što se radi prije stvarne enkripcije elektroničkih informacija. Ova točka jamči da sadržaj elektroničkih dokumenata neće biti prikazan svima i da se povjerljivi podaci ne mogu vidjeti kada se na dokumente primijeni mehanizam za slučajni odabir ključeva.

RSA enkripcija rastavlja matematičke brojeve na faktore, ali mehanizam nikada nije usavršen. Stoga napadači u ovom trenutku još uvijek imaju priliku i mnogo rupa u zakonu za odabir metoda za razbijanje enkripcije podataka. A to im polazi za rukom upravo kroz mehanizam obnavljanja prafaktora.

Prevaranti izračunavaju tajni indikator sadržan u javnom ključu i dekriptiraju dokumentaciju koristeći standardnu ​​metodu. Dakle, polje djelovanja za one koji stvarno žele naštetiti tvrtki je značajno veliko. Recimo samo da je problem sigurnosti RSA enkripcije i dalje aktualan i otvoren, iako malo ljudi o tome javno govori.

Automatizirani proces elektroničke enkripcije podataka

Unatoč niskoj sigurnosnoj ocjeni, dotična RSA enkripcija primjenjiva je u mnogim industrijama. Posebno je dobrodošao kada postoji velika cirkulacija elektroničke dokumentacije. Recimo samo da se RSA enkripcija koristi za zaštitu dokumenata na prosječnoj razini odgovornosti.

Yafu softver vam omogućuje automatsko šifriranje elektroničkih podataka. Ovaj vam program omogućuje brzo pronalaženje podataka za stvaranje asimetričnih ključeva, poštujući pravila faktoring pouzdanosti. Kompatibilan je s procesorima kao što su SIQS, ECM, SNFS. Pokreće se putem naredbenog retka. Unos ove naredbe u redak omogućuje nekoliko puta smanjenje vremena potrebnog za traženje podataka za izradu ključeva.

Prosječan korisnik opreme za osobno računalo ne može se nositi s ovim softverom. Njegova instalacija i konfiguracija zahtijeva određeno znanje i to često rade IT programeri i stručnjaci.

RSA enkripcija je ozbiljno ranjiva, i to unatoč činjenici da se za kreiranje javnih i privatnih ključeva koriste veliki brojevi, koji iznose nekoliko tisuća bitova na diskovima.

Benjamin Moody je 2009. godine dokazao da je proces krekiranja javnih i privatnih ključeva moguć. Iako to može potrajati dvije ili više godina, ostaje činjenica da mnogi svjetski računalni sustavi mogu biti u opasnosti od hakiranja.

Na primjer, ovom stručnjaku nije bilo potrebno ništa posebno da pregleda ključne skripte - računalo običnog korisnika i GGNFS softver. Čak ni praksa ključeva enkripcije od nekoliko tisućitih bitova ne štiti informacije od napuštanja povjerljivih polja i nedostupnosti drugim korisnicima.

Naravno, razbijanje RSA enkripcije zahtijeva vrijeme. Mnogi hakeri potroše godine kako bi postigli pozitivan rezultat. To su često visokoplaćeni izgledi koji potiču interes za nastavkom potrage za pravim ključem. U većini slučajeva hakiranje dugih ključeva napušta se u potrazi za jednostavnijim izgledima. Ali to ne znači da nitko ne pokušava stvoriti jednostavniji mehanizam za probijanje ključeva.

Glavna zaštita od intruzivnih napada prevaranata je stvaranje velikih i dugih ključeva od više od dvije tisuće bitova. Već su poznati slučajevi hakiranja ključeva duljine od sto do petsto bitova. Stoga morate držati uši oštrim. Ako postoji mehanizam za razbijanje kratkih ključeva, vjerojatno se negdje na strani zlonamjernika radi punom parom na razbijanju najdužih kombinacija elektroničke enkripcije podataka.

Zaključak

Na temelju navedenog, RSA enkripcija je sigurna metoda očuvanja povjerljivosti elektroničkih podataka, pod uvjetom da su kreirani dugi i informacijama bogati ključevi.

Teško ih je odabrati ručno, pa se koristi automatizirani programski proizvod Yafu. Instaliraju ga i konfiguriraju IT stručnjaci. Ako to učinite sami, to može oštetiti operativni sustav vašeg računala.
Ovaj softver dizajniran je za rad u tandemu s višejezgrenim računalnim procesorima moderne generacije.

Glavne mete prijevarnih napada su velike industrijske i financijske tvrtke, pa bez RSA enkripcije njihovo elektroničko upravljanje dokumentima ne funkcionira. Elektronički potpis dokumenata također je podložan enkripciji i za njega vrijede isti sigurnosni standardi kao i za ostale informacijske podatke. Načelo - što je veći ključ, to je teže hakirati dokument - trebalo bi vrijediti za apsolutno sve podatke koji nisu namijenjeni javnoj upotrebi.

RSA enkripcija jedan je od prvih praktičnih kriptosustava s javnim ključem i naširoko se koristi za siguran prijenos podataka. Glavna razlika od sličnih servisa je u tome što je ključ za šifriranje javan i razlikuje se od ključa za dešifriranje koji se drži u tajnosti. RSA tehnologija temelji se na praktičnim poteškoćama rastavljanja dva velika prosta broja (problem faktoringa).

Povijest stvaranja

Naziv RSA sastoji se od početnih slova prezimena Rivesta, Shamira i Adlemana, znanstvenika koji su ih prvi javno opisali 1977. godine. Clifford Cox, engleski matematičar koji je radio za britanske obavještajne službe, prvi je razvio ekvivalentni sustav 1973. godine, ali s njega je skinuta oznaka tajnosti sve do 1997. godine.

RSA korisnik stvara i zatim objavljuje javni ključ temeljen na dva velika prosta broja zajedno s pomoćnom vrijednošću. mora biti tajna. Svatko može koristiti javni ključ za šifriranje poruke, ali ako je dovoljno velik, tada samo netko tko poznaje primarne brojeve može dekodirati poruku. Poznato je da je razbijanje RSA enkripcije veliki problem: danas postoji otvorena rasprava o tome koliko je mehanizam siguran.

RSA je relativno spor algoritam, zbog čega ga izravni korisnici ne koriste široko. Najčešća uporaba ove metode je prijenos šifriranih zajedničkih ključeva za simetrični ključ šifriranja, koji zauzvrat može izvesti skupne operacije šifriranja i dešifriranja mnogo većim brzinama.

Kada se pojavio kriptosustav u svom modernom obliku?

Ideja o kriptosustavu asimetričnog ključa pripisuje se Diffieju i Hellmanu, koji su objavili koncept 1976., uvodeći digitalne potpise i pokušavajući primijeniti teoriju brojeva. Njihova formulacija koristi zajednički tajni ključ stvoren od eksponenta nekog broja modulo prim broja. Međutim, ostavili su otvorenim problem implementacije ove funkcije, budući da načela faktoringa u to vrijeme nisu bila dobro shvaćena.

Rivest, Adi Shamir i Adleman s MIT-a nekoliko su puta pokušali tijekom godine dana stvoriti jednosmjernu funkciju koju je teško dekodirati. Rivest i Shamir (kao računalni znanstvenici) predložili su mnoge potencijalne funkcije, dok je Adleman (kao matematičar) tragao za slabostima algoritma. Poduzeli su mnoge pristupe i na kraju razvili konačni sustav u travnju 1977., danas poznat kao RSA.

Digitalni potpis i javni ključ

Elektronički digitalni potpis ili EDS sastavni je dio elektroničkih dokumenata. Nastaje određenom kriptografskom promjenom podataka. Pomoću ovog atributa moguće je provjeriti cjelovitost dokumenta, njegovu povjerljivost, kao i utvrditi tko je njegov vlasnik. U biti, ovo je alternativa uobičajenom standardnom potpisu.

Ovaj kriptosustav (RSA enkripcija) nudi javni ključ, po čemu se razlikuje od simetričnih. Princip njegovog rada je da se koriste dva različita ključa - privatni (kriptirani) i javni. Prvi se koristi za generiranje elektroničkog potpisa i mogućnost dešifriranja teksta. Drugi je za stvarnu enkripciju i provjeru digitalnog potpisa.

Korištenje potpisa omogućuje nam bolje razumijevanje RSA enkripcije, čiji se primjer može dati kao obični klasificirani dokument "zatvoren od znatiželjnih očiju".

Što je suština algoritma?

RSA algoritam se sastoji od četiri faze: generiranje ključa, distribucija ključa, enkripcija i dešifriranje. Kao što je već rečeno, RSA enkripcija uključuje javni ključ i privatni ključ. Open može biti poznat svima i koristi se za šifriranje poruka. Njegova bit je da se poruke kriptirane javnim ključem mogu dešifrirati samo unutar određenog vremenskog razdoblja korištenjem privatnog ključa.

Radi sigurnosti, cijeli brojevi trebaju biti nasumično odabrani i iste veličine, ali se razlikuju po duljini za nekoliko znamenki kako bi faktoring bio teži. Identični brojevi mogu se učinkovito pronaći korištenjem testa njihove primalnosti, tako da šifriranje informacija nužno mora postati kompliciranije.

Javni ključ se sastoji od modula i javnog eksponenta. Privatno se sastoji od modula i privatnog indikatora koji se moraju čuvati u tajnosti.

RSA šifriranje datoteka i slabosti

Međutim, postoji niz mehanizama za razbijanje jednostavnog RSA. Kod šifriranja s niskim brzinama i malim brojevima, šifra se može lako razbiti ako pronađete korijen šifriranog teksta preko cijelih brojeva.

Budući da je RSA enkripcija deterministički algoritam (tj. nema nasumične komponente), napadač može uspješno pokrenuti napad odabranim otvorenim tekstom na kriptosustav šifriranjem prihvatljivih otvorenih tekstova pod javnim ključem i provjerom jesu li jednaki šifriranom tekstu. Za kriptosustav se kaže da je semantički siguran ako napadač ne može razlikovati dvije enkripcije jednu od druge, čak i ako poznaje odgovarajuće tekstove u brisanom obliku. Kao što je gore opisano, RSA, bez nadopune s drugim uslugama, nije semantički siguran.

Dodatna enkripcija i sigurnosni algoritmi

Kako bi se izbjegli gore navedeni problemi, praktične implementacije RSA obično ugrađuju neki oblik strukturiranog, nasumičnog punjenja prije enkripcije. To osigurava da sadržaj ne spada u raspon nesigurnog otvorenog teksta i da poruka ne može biti slučajno ugrožena.

Sigurnost RSA kriptosustava i enkripcije informacija temelje se na dva matematička problema: problemu faktoriziranja velikih brojeva i samom RSA problemu. Potpuno otkrivanje šifriranog teksta i digitalnog potpisa u RSA smatra se neprihvatljivim pod pretpostavkom da se oba ova problema ne mogu riješiti zajedno.

Međutim, zahvaljujući mogućnosti oporavka prostih faktora, napadač može izračunati tajni eksponent iz javnog ključa i zatim dešifrirati tekst koristeći standardnu ​​proceduru. Iako danas nije pronađena postojeća metoda za faktoriziranje velikih brojeva na klasičnom računalu, nije dokazano da ona ne postoji.

Automatizacija

Alat nazvan Yafu može se koristiti za pojednostavljenje ovog procesa. Automatizacija u YAFU je vrhunska značajka koja kombinira algoritme faktorizacije u inteligentnoj i prilagodljivoj metodologiji koja minimizira vrijeme za pronalaženje faktora proizvoljnih ulaznih brojeva. Većina implementacija algoritma je multi-threaded, što Yafu omogućuje da u potpunosti iskoristi više ili više (uključujući SNFS, SIQS i ECM). Prije svega, to je upravljani alat naredbenog retka. Vrijeme potrošeno na traženje faktora šifriranja pomoću Yafua na običnom računalu može se smanjiti na 103,1746 sekundi. Alat proizvodi kapacitet obrade od 320 bita ili više. Ovo je vrlo složen softver koji zahtijeva određenu količinu tehničkih vještina za instalaciju i konfiguraciju. Stoga RSA C enkripcija može biti ranjiva.

Pokušaji hakiranja u moderno doba

Godine 2009. Benjamin Moody, koristeći RSA-512 bitni ključ, radio je na dešifriranju kriptoteksta 73 dana koristeći samo uobičajeni softver (GGNFS) i prosječno stolno računalo (dual-core Athlon64 na 1900 MHz). Kao što je ovo iskustvo pokazalo, za proces "prosijavanja" bilo je potrebno nešto manje od 5 gigabajta diska i oko 2,5 gigabajta RAM-a.

Od 2010. najveći faktorirani RSA broj bio je dug 768 bita (232 decimalne znamenke ili RSA-768). Njegovo otkrivanje trajalo je dvije godine na nekoliko stotina računala istovremeno.

U praksi su RSA ključevi duži – obično od 1024 do 4096 bita. Neki stručnjaci vjeruju da bi 1024-bitni ključevi mogli postati nesigurni u bliskoj budućnosti ili da bi ih već mogao probiti napadač koji je dobro financiran. Međutim, malo tko bi tvrdio da se 4096-bitni ključevi također mogu otkriti u doglednoj budućnosti.

Izgledi

Stoga se općenito pretpostavlja da je RSA siguran ako su brojevi dovoljno veliki. Ako je osnovni broj 300 bita ili kraći, šifrirani tekst i digitalni potpis mogu se dekomponirati unutar nekoliko sati na osobnom računalu pomoću softvera koji je već besplatno dostupan. 512-bitne ključeve dokazano je moguće provaliti još 1999. pomoću nekoliko stotina računala. Danas je to moguće u roku od nekoliko tjedana korištenjem javno dostupnog hardvera. Stoga je sasvim moguće da će se u budućnosti RSA enkripcija lako razbiti na prstima, a sustav će postati beznadno zastario.

Službeno je 2003. godine dovedena u pitanje sigurnost 1024-bitnih ključeva. Trenutačno se preporučuje da bude dugačak najmanje 2048 bita.

Ispod presjeka su primjeri odabira "loših" parametara RSA šifre.

“Treba naglasiti da se mora voditi računa o odabiru RSA modula (broj n) za svakog od mrežnih dopisnika. S tim u vezi može se reći sljedeće. Čitatelj to može samostalno provjeriti poznavajući jednu od tri veličine str, q ili φ(n), možete jednostavno pronaći RSA privatni ključ...".

Nadodajmo ovaj tekst. Ako je odabir modula RSA šifre neuspješan, kao što je učinjeno u primjeru priručnika danom u nastavku, možete dešifrirati tekst bez prisustva tajnog ključa, tj. a da ne poznaje niti jednu od tri navedene veličine.

Da biste to učinili, dovoljno je imati šifrirani tekst određen modulom šifre n, javni ključ ešifrirati i izvesti samo tri koraka napada čitanja bez ključa. Nakon četvrtog koraka napada, utvrđuje se da je izvorni tekst dobiven u prethodnom koraku i da se može čitati. Pokažimo kako je to lako učiniti.

Najprije navedimo sam primjer sa str. 313-315 navedenog priručnika.

Primjer

Šifriranje kratka početna tekstualna poruka: RSA.
Primatelj postavlja šifru s karakteristikama n=pq=527, Gdje p=17, q=31 I φ(n)=(r –1)(q – 1)=480. Kao javni ključ e odabrani broj koji je koprost s φ(n), e=7. Cijeli brojevi za ovaj broj se pronalaze pomoću proširenog Euklidovog algoritma u I v, zadovoljavajući odnos e∙u+φ(n)∙v=1:

480=7∙68+4,
7=4∙1+3,
4=3∙1+1,
1=4–3∙1=4–(7–4∙1)∙1=4∙2–7∙1=(480–7∙68)∙2–7∙1=480∙2–7∙137,
v=2, u=–137.

Jer –137≡343(mod480), To d=343.

Ispitivanje: 7∙343=2401≡1(mod480).

Tekstualna poruka je predstavljena kao niz brojeva sadržanih u intervalu . Pisma za ovo R, S I A su kodirani kao pet-bitni binarni brojevi. Serijski brojevi ovih slova u engleskoj abecedi koriste se u njihovom binarnom prikazu:

R=18 10 =(10010) 2, S=19 10 =(10011) 2,
A=1 10 =(00001) 2.

Zatim RSA=(100101001100001) 2. Razbijanje teksta u blokove ograničene duljine proizvodi prezentaciju od dva bloka: RSA=(100101001), (100001)=(M 1 =297, M 2 =33).

Blokovi izvornog teksta šifriraju se sekvencijalno Ml =297, M2 =33:
y 1 =E k (M 1)=M 1 e ≡297 7 (mod527)=474.

Ovdje smo koristili činjenicu da:

297 7 =((297 2) 3)297≡(mod527)=(200 3 (mod527)297)(mod527)=474,
y 2 =E k (M 2)=M 2 e ≡33 7 (mod527)=407.

Šifrirani tekst, kao i izvorni, dobiva se u obliku dva bloka: y 1 =474; y 2 =407.

Dekodiranječini se da je slijed radnji D k (y i)=(y i) d =(y i) 343 (mod 527), i=1,2.

Izračuni stepenovanja d prikladnije je izvesti tako da se prvo eksponent predstavi kao zbroj potencija broja 2 , naime: 343=256+64+16+4+2+1 .

Koristeći ovaj prikaz eksponenta d=343, dobivamo:

474 2 ≡174(mod527),
474 4 ≡237(mod527),
474 8 ≡307(mod527),
474 16 ≡443(mod527),
474 32 ≡205(mod527),
474 64 ≡392(mod527),
474 128 ≡307(mod527),
474 256 ≡443(mod527),
i konačno 474 343 (mod527)=(443∙392∙443∙237∙174∙474) (mod527)=297.

Vrijednost se izračunava na sličan način 407 343 (mod527) = 33.

Prebacivanje na doslovno predstavljanje dešifrirane poruke daje: RSA.

Nakon pogleda na primjer, priručnik govori o robusnosti RSA sustava. Ističe se potreba opreza pri odabiru modula RSA šifre (brojeva). n) za svakog od mrežnih dopisnika. Ukazuje se da je nedopustivo ignorirati zahtjeve za odabranim karakteristikama sustava šifriranja. Među tim zahtjevima, nažalost, nije naznačeno čije kršenje ilustrira navedeni primjer.

Napad na RSA šifru

Pogledajmo primjer napada na RSA šifru. Poslužimo se podacima iz primjera danog na stranicama 313-315 u udžbeniku “Osnove kriptografije” A.P. Alferov, A.Yu. Zubov, A.S. Kuzmin, A.V. Čeremuškin, Moskva. "Helios ARV", 2001.

Neispravnost (neprihvatljivost) odabranih parametara sustava u ovom primjeru lako se pokazuje izračunima koji provode napad na čitanje izvornog teksta bez ključa. Suština takvog napada je sljedeća. Naveden je javni ključ RSA šifre ( e=7, n=527) i šifrirani tekst. U primjeru je šifrirani tekst predstavljen u dva bloka
y=(y 1 =474, y 2 =407).

Svaki šifrirani blok se napada zasebno, prvo mi napadamo y 1 =474, nakon što ga dekriptiramo, napadamo drugi blok y 2 =407.

Zatim se niz numeričkih vrijednosti formira ponovljenim šifriranjem, pohranjivanjem rezultata dva uzastopna koraka algoritma napada i korištenjem javnog ključa. y i, y 1 =y dostupni šifrirani tekst.

U algoritmu napada šifriranim tekstom određuje se sljedeći broj koraka: j, za koji y i e j (mod n)=(y i e j–1 (mod n)) e (mod n)=y i, i>1. Iz zadnje relacije vidimo da kada se podigne na potenciju e vrijednosti (y i e j–1 (mod n)) dobiva se početni šifrat y i = y 1.

Ali to znači da je otvoreni tekst bio šifriran u ovom koraku. Izravnim izračunima (ima ih vrlo malo) pomoću kalkulatora na ekranu nalazimo tu vrijednost j, pri čemu ciklus šifriranja završava s vrijednošću y 1, od koje je ciklus započeo.

Napad na prvi blok y 1 =474šifrirani tekst.
Korak 1:  474 7 (mod527)=382;
Korak 2:  382 7 (mod527)=423;
3. korak:  423 7 (mod527)=297;
Korak 4:   u ovom koraku već pronađeni izvorni tekst je šifriran, ali to mora biti učinjeno jer napadač ne zna izvorni tekst. Znak završetka napada je slučajnost početne vrijednosti šifriranog teksta ( 474 ) i rezultat 4. koraka šifriranja. Upravo se takva slučajnost i događa.

297 7 (mod527) = 474 primio početni (prvi) blok šifrovanog teksta. Napad na prvi blok uspješno je završen y 1 =474. Prethodni rezultat koraka 3 jednak je otvorenom tekstu Ml =297.

n=527 r=297 modulo n=527. Napisano je ovako y i =u 1 =297. Stvaranje energetskih ostataka
(((297 7 (mod527)) 7 (mod527)) 7 (mod527)) 7 =297.

Napad na drugi blok y 2 =407šifrirani tekst.
Korak 1:  407 7 (mod527)=16;
Korak 2:  16 7 (mod527)=101;
3. korak:  101 7 (mod527)=33;
Korak 4:  33 7 (mod527)=407.

Opet, u trećem koraku, dobiven je blok izvornog teksta ( M2 =33), ali napadač to ne zna, te izvodi sljedeći (četvrti korak) čiji je rezultat ( 407 ) odgovara početnom šifriranom tekstu y 2 =407.

U biti u prstenu modulo ostataka n=527 implementiran je kratki ciklus obrade odbitka r=33 modulo n=527. Napisano je ovako y i =y 2 =33.
Stvaranje energetskih ostataka ((33 7 (mod527)) 7 (mod527)) 7 (mod527)=33.

Rezultat napada (izvorni tekst Ml =297, M2 =33) dobiva se šifriranjem zadanog šifriranog teksta tri puta. Teško je zamisliti veći uspjeh napadača na šifrirani tekst.

Nastavljajući raspravu o izboru modula i ostalih parametara šifre, možemo dodati da modul šifre ( n=527) neki izvorni tekstovi se uopće ne mogu šifrirati. U ovom slučaju izbor vrijednosti javnog ključa ne igra veliku ulogu. Postoje vrijednosti izvornog teksta koje je općenito nemoguće šifrirati odabranom šifrom s modulom n=527.

Niti jedan od navedenih ne može šifrirati izvorne tekstove predstavljene brojevima
187 , 341 , 154 I 373 .

Primjer (nemogućnost šifriranja vrijednosti nekih izvornih tekstova)

Neka izvorni tekstovi budu predstavljeni s četiri bloka y=(y 1 =154, y 2 =187, y 3 =341, y 4 =373). Izlagač e javni ključ šifre može biti bilo koji koprost broj s Eulerovom funkcijom φ(n)=φ(527)=480. Međutim, za slučaj koji razmatramo, javni ključ e može se postaviti proizvoljno. Doista, neka e=2, 4, 7, 9, 17, 111 Zatim:

154 2 (mod527)=1;
154 4 (mod527)=1;
154 7 (mod527)=154;
154 9 (mod527)=154;
154 17 (mod527)=154;
154 111 (mod527)=154;
187 2 (mod527)=187;
187 4 (mod527)=187;
187 7 (mod527)=187;
187 9 (mod527)=187;
187 17 (mod527)=187;
187 111 (mod527)=187;
341 2 (mod527)=341;
341 4 (mod527)=1;
341 7 (mod527)=341;
341 9 (mod527)=341;
341 17 (mod527)=341;
341 111 (mod527)=341;
373 2 (mod527)=1;
373 4 (mod527)=373;
373 7 (mod527)=373;
373 9 (mod527)=373;
373 17 (mod527)=373;
373 111 (mod527)=373.

Iz razmatranog primjera proizlazi jednostavan zaključak. Doista, izboru parametara za proces šifriranja mora se pristupiti vrlo pažljivo i mora se provesti temeljita preliminarna analiza takvih parametara. Kako to učiniti je zasebno pitanje i ne razmatra se u okviru ovog rada.

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 sa sigurnošću reći je 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 pomoću 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 što 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 tvrdnja 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 vode do radnog kriptosustava samo ako će dekodiranje svakog bloka šifrirane poruke vratiti odgovarajući blok izvorne poruke. 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 razmišljanje 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 provjeriti jesu li brojevi međusobno prosti, što je, čini se, potrebno 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 za dokazivanje 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 dokažemo jednakost budući da su oba njegova dijela nenegativni cijeli brojevi, da rezimiramo

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 odlomka 11. poglavlja formulirali smo strategiju za dokazivanje primarnosti zadanog neparnog broja. Sastoji se od tri koraka.