RSA-dulkóðun. Lýsing og framkvæmd RSA reiknirit

RSA-dulkóðun er einn af þeim fyrstu hagnýtum public-lykill cryptosystems sem er víða notað fyrir örugg gagnaflutning. Helsti munurinn hennar frá svipuðum þjónustu er að lykilorð er opið og frábrugðin dulráðunarlykil, sem er haldið leyndum. RSA tækni , þetta asymmetry er byggt á hagnýta erfitt að þátta spilun tveimur stórum prímtölur (að þátta).

Saga um sköpun

RSA Nafnið samanstendur af fyrstu stafina Eftirnöfn Rivest, Shamir og Adleman - vísindamenn sem fyrst opinberlega lýst þessum dulritunaralgrími árið 1977. Klifford Koks, enskur stærðfræðingur, sem starfaði fyrir bresku leyniþjónustunnar, fyrst að þróa samsvarandi kerfi í 1973, en það var ekki declassified til 1997

RSA notanda skapar og þá gefur út dreifilykil byggist á tveimur stórum prímtölur ásamt tengd gildi. Frumtölur skal haldið leyndum. Hver sem er getur notað opinber lykill til að dulkóða skilaboð, en ef það er nógu stór, þá bara einhver með þekkingu á frumtölum geta lesa skilaboðin. RSA dulkóðun birting er þekktur sem helstu vandamál í dag er opið umræða um hvernig traustur vélbúnaður.

RSA reiknirit er tiltölulega hægur, sem ástæða það er ekki eins og víða notað til að beint dulkóða notanda. Í flestum tilfellum, þessi aðferð er notuð til flutnings á sameiginlegum lykli dulkóðuð fyrir samhverft dulkóðun lykill, sem aftur getur framkvæmt aðgerðir magn dulkóðun og decryption á miklu meiri hraða.

Þegar það var cryptosystem í núverandi mynd?

Hugmyndin um ósamhverfum dulrituðu lykill rekja til Diffie og Hellman, sem birt hugmyndina árið 1976, kynna stafrænar undirskriftir, og reyna að beita kenningu um tölum. mótun þeirra notar samnýtt leynilykil mynda frá ákveðinn fjölda Veldi modulo frumtala. Hins vegar eftir að þeir opna útgáfu framkvæmd þessa aðgerð, þar sem meginreglur þátta var ekki vel skilið á þeim tíma.

Rivest, Adi Shamir og Adleman við MIT hafa gert nokkrar tilraunir gegnum árin til að búa til einhliða aðgerð sem erfitt er að lesa. Rivest og Shamir (eins vísindamönnum tölva) hafa lagt mörgum mögulegum aðgerðum, en Adleman (eins stærðfræði) til að leita að "veikburða stig" af reiknirit. Þeir nota mikið af aðferðum og að lokum að þróa endanlega kerfi, nú þekkt sem RSA í apríl 1977.

Rafræn undirskrift og dreifilykill

Stafræn undirskrift eða rafræn undirskrift, er óaðskiljanlegur hluti af rafrænum gerðir skjal. Það myndast á tilteknum dulritunar gögn breytingar. Með þessa eiginleika hægt að athuga heilleika skjalinu, trúnað hans, sem og til að ákvarða hver á það. Í raun, í stað venjulegrar venjulegu undirskrift.

Þetta cryptosystem (RSA-dulkóðuð) býður upp á dreifilykil ólíkt samhverf. Meginreglan hennar starfsemi er að tveir mismunandi lyklar eru notaðir - lokað (dulkóðuð) og úti. Í fyrsta lagi er notuð til að búa til stafræna undirskrift og þá geta hallmæla texta. Í öðru lagi - til the raunverulegur dulkóðun og rafræn undirskrift.

Using undirskrift til að skilja betur RSA dulkóðun, en dæmi um slíkt er hægt að minnka eins og venjulegt leyndarmál "lokuð frá hnýsinn augum," skjalið.

Hvað er reiknirit?

RSA reiknirit samanstendur af fjórum skrefum: lykill kynslóð, dreifingu, dulkóðun og decryption. Eins og áður hefur komið fram, RSA-dulkóðun inniheldur lykil opinbera og sér lykil. Úti geta verið þekkt til allra og er notað til að dulrita skeyti. kjarni hennar liggur í þeirri staðreynd að skilaboð dulkóðuð með dreifilykli er aðeins hægt að decrypted á tilteknu tímabili með því að nota leyndarmál takkann.

Af öryggisástæðum, Heiltölurnar að vera valin af handahófi og vera eins í stærð, en mismunandi að lengd eftir nokkrum tölum til að gera þátta erfiðara. Sama Sama númer er hægt að finna í raun með próf í einfaldleika sínum, þannig að dulkóðun upplýsinga verður endilega að vera flókið.

The opinber lykill samanstendur af stuðull og opinber veldisvísi. Innanhúss eining og samanstendur af a persónulegur mynd, sem ætti að vera haldið leyndum.

RSA dulkóðun skráa og veikleika

Hins vegar eru a tala af einföldum reiðhestur RSA kerfi. Aðdulrita með lágu og litlum gildum kóðanúmerum geta hæglega opnað, ef velja rót ciphertext yfir heiltölur.

Þar sem RSA-dulkóðun er deterministic reiknirit (þ.e. hefur engin handahófi hluti), sem árásarmaður geta tekist ræst Texta opinn ráðast gegn cryptosystem með því að dulkóða líklegt plaintexts undir dreifilyklinum og eftirlit á því hvort þeir eru jafnir ciphertext. Merkingu örugg cryptosystem er kallað ef að árásarmaður geta ekki greint á milli tveggja dulkóðun frá hvor öðrum, jafnvel þótt hann veit viðkomandi texta í stækkuðu formi. Eins og lýst er hér að framan, RSA önnur þjónusta án bólstrunar er ekki merkingu örugg.

Önnur reiknirit fyrir dulkóðun og verndun

Til að koma í veg fyrir ofangreind vandamál, í verklega framkvæmd RSA eru yfirleitt sett í einhvers konar skipulögð, slembiraðaðri fyllingu áður dulkóðun. Þetta tryggir að efnið falli ekki innan þeirra marka sem óörugg plaintexts, og að þessi skilaboð ekki hægt að leysa með því að handahófi val.

Öryggi RSA cryptosystem og dulkóðun byggist á tveimur stærðfræðilegum vandamálum: að þátta stórar tölur og í raun RSA vandamál. Full upplýsingagjöf um ciphertext og undirskrift hjá RSA er talið ótækt á þeirri forsendu að bæði þessi vandamál geta ekki leyst í sameiningu.

Hins vegar, með getu til að endurheimta helsta þætti, sem árásarmaður geta reikna út leyndarmál veldisvísir af dreifilyklinum og þá hallmæla texta með staðlaða aðferð. Þrátt fyrir þá staðreynd að í dag eigi núverandi aðferð til að þátta stórar heiltölur á klassískum tölvu er ekki hægt að finna, það hefur ekki verið sannað að hann er ekki til.

sjálfvirkni

The tól kallast Yafu, er hægt að nota til að hagræða því ferli. Sjálfvirkni í YAFU er háþróaður lögun sem sameinar þáttun reiknirit í vitsmunalegum og aðlögunar aðferðafræði sem lágmarkar tíma til að finna þá þætti handahófskenndra inntak númer. Flestar útfærslur multitreaded reiknirit sem leyfir Yafu fulla notkun multi- eða margra örgjörva multi-algerlega (þar með talið SNFS, SIQS og ECM). Fyrst af öllu, það er stjórnað af stjórn-lína tól. Tíminn sem fer í að leita að dulkóðun Yafu þáttur með hefðbundnum tölva, getur það að minnka sekúndum 103.1746. The tól afgreiðir tvöfaldur getu 320 bitum eða fleiri. Þetta er mjög flókið hugbúnaður sem þarf tiltekið magn af tæknilegum færni til að setja upp og stilla. Svona, RSA-dulkóðun kann að vera viðkvæmt C.

Dýrka tilraunir í seinni tíð

Árið 2009, Bendzhamin Mudi með RSA-512 bita lykil var að vinna á deciphering kriptoteksta í 73 daga, með því að nota aðeins vel þekkt hugbúnaður (GGNFS) og meðaltal skrifborð (tvískiptur-algerlega Athlon64 á 1900 MHz). Eins og sést af reynslu, þarf aðeins minna en 5 GB diskur og um 2,5 gígabæta minni ferli "sigta".

Frá og með 2010, mesti fjöldi var reiknað RSA 768 bitar (232 tölustafi eða RSA-768). birting hans stóð í tvö ár á nokkur hundruð tölvum í einu.

Í reynd eru RSA lykla lengi - venjulega frá 1024 til 4096 bita. Sumir sérfræðingar telja að 1024 bita lyklar geta verið óáreiðanleg í náinni framtíð eða jafnvel lengur getur verið klikkaður mjög vel fjármögnuð árásarmönnum. Hins vegar fáir myndu halda því fram að 4096 bita lykla má einnig birta í náinni framtíð.

horfur

Því, sem að jafnaði er gert ráð fyrir að RSA er öruggt ef þau eru nógu stór. Ef stöð fjöldi 300 bita eða styttri, og ciphertext stafrænni undirskrift er hægt að niðurbrot innan nokkurra klukkustunda á einkatölvu með hugbúnaður laus þegar í almenningi. A lykill lengd 512 bitar, eins og sýnt er, er hægt að opna eins snemma og 1999, með því að nota nokkur hundruð tölvur. Nú það er hægt í nokkrar vikur með öllum aðgengileg vélbúnaði. Þannig er hugsanlegt að í buduschembudet auðveldlega birta RSA-dulkóðuð á fingrum, og kerfið verður hopelessly gamaldags.

Opinberlega árið 2003, var kallað í efa öryggi á 1024-bita lykla. Eins og er, er mælt með því að hafa lágmarksfjölda 2048 bita.