RSA-amgryptio. Disgrifiad a gweithrediad y algorithm RSA

RSA-amgryptio yn un o'r cryptosystems cyhoeddus-allweddol ymarferol cyntaf sy'n cael ei defnyddio'n eang ar gyfer trosglwyddo data yn ddiogel. Mae ei brif wahaniaeth o wasanaethau tebyg yw mai'r allwedd amgryptio yn agored ac yn wahanol i'r allwedd dadgriptio, sy'n cael ei chadw'n gyfrinachol. Mae'r dechnoleg RSA , anghymesuredd hwn yn seiliedig ar yr anhawster ymarferol ffactoreiddio y chwarae dau rif cysefin mawr (y broblem o ffactoreiddio).

Hanes greu

RSA Enw'r cynnwys y llythrennau cychwynnol y cyfenwau Rivest, Samir a Adleman - y gwyddonwyr sydd gyntaf a ddisgrifir yn gyhoeddus rhain algorithmau amgryptio yn 1977. Klifford Koks, mathemategydd Saesneg, a oedd yn gweithio ar gyfer gwasanaethau cudd-wybodaeth Prydain, y cyntaf i ddatblygu system gyfatebol yn 1973, ond ni chafodd ei declassified tan 1997

defnyddiwr RSA yn creu ac yna'n cyhoeddi'r allwedd gyhoeddus yn seiliedig ar ddau rifau cysefin fawr ynghyd â gwerth ategol. rhifau cysefin Dylid cadw cyfrinach. Gall unrhyw un ddefnyddio'r allwedd gyhoeddus i amgryptio neges, ond os yw'n ddigon mawr, yna gall dim ond rhywun sydd â gwybodaeth o rifau cysefin decode y neges. datgeliad amgryptio RSA yn cael ei adnabod fel y brif broblem heddiw yw trafodaeth agored ynglŷn â sut mecanwaith dibynadwy.

RSA algorithm yn gymharol araf, am y rheswm nad yw'n cael ei ddefnyddio mor eang â uniongyrchol encrypt y defnyddiwr. Yn y rhan fwyaf o achosion, y dull hwn yn cael ei ddefnyddio ar gyfer trosglwyddo yn yr allwedd rennir hamgryptio er allwedd amgryptio cymesur, a all yn ei dro yn perfformio gweithrediadau amgryptio swmp a dadgriptio ar gyflymder llawer uwch.

Pan roedd cryptosystem yn ei ffurf bresennol?

Mae'r syniad o allwedd cryptograffig anghymesur a briodolir i Diffie a Hellman, a gyhoeddodd y cysyniad yn 1976, gan gyflwyno llofnodion digidol, ac yn ceisio rhoi'r theori rhifau. Mae eu llunio yn defnyddio allwedd gyfrinach a rennir a gynhyrchwyd o nifer penodol o exponentiation modwlo rhif cysefin. Fodd bynnag, maent yn gadael yn agor y mater o wireddu swyddogaeth hon, gan nad yw'r egwyddorion ffactoreiddio yn deall yn dda ar y pryd.

Rivest, Adi Samir, ac Adleman yn MIT wedi gwneud sawl ymgais dros y blynyddoedd i greu swyddogaeth un-ffordd sy'n anodd ei ddadgodio. Rivest a Samir (fel gwyddonwyr cyfrifiadurol) wedi cynnig llawer o swyddogaethau posibl, tra Adleman (fel mathemateg) i chwilio am "pwyntiau gwan" y algorithm. Maent yn defnyddio llawer o ddulliau ac yn y diwedd yn datblygu system terfynol, a elwir bellach yn RSA ym mis Ebrill 1977.

llofnod electronig a'r allwedd gyhoeddus

llofnod digidol neu lofnod electronig, yn rhan annatod o'r mathau dogfennau electronig. Mae'n cael ei ffurfio mewn rhai newidiadau data cryptographic. Gyda'r nodwedd hon yn bosibl i wirio cywirdeb y ddogfen, ei cyfrinachedd, yn ogystal ag i bennu pwy sy'n berchen arno. Yn wir, dewis arall yn lle llofnod safonol arferol.

Mae'r cryptosystem (RSA-amgryptio) yn cynnig yr allwedd gyhoeddus, yn wahanol i cymesur. Mae ei egwyddor o weithredu yw bod y ddau allweddi gwahanol yn cael eu defnyddio - ar gau (amgryptio) ac awyr agored. Mae'r cyntaf yn cael ei ddefnyddio i greu llofnod digidol ac wedyn yn gallu dadgryptio testun. Ail - ar gyfer y amgryptio gwirioneddol a llofnod electronig.

Gan ddefnyddio llofnodion i ddeall y amgryptio RSA yn well, yn enghraifft gellir o'r rhain yn cael ei leihau fel yn gyfrinach normal "cau rhag llygaid busneslyd," y ddogfen.

Beth yw'r algorithm?

RSA algorithm yn cynnwys pedwar cam: genhedlaeth allweddol, dosbarthu, amgryptio a dadgriptio. Fel y soniwyd eisoes, RSA-amgryptio yn cynnwys allwedd gyhoeddus ac allwedd breifat. Gellir Awyr Agored yn hysbys i bawb ac yn cael ei ddefnyddio i amgryptio negeseuon. Ei hanfod yn gorwedd yn y ffaith y gall negeseuon amgryptio gyda'r allwedd gyhoeddus ond yn cael ei decrypted mewn cyfnod penodol o amser gan ddefnyddio allwedd gyfrinach.

Am resymau diogelwch, mae'r cyfanrifau i gael eu dewis ar hap a bod yn union yr un fath o ran maint, ond yn wahanol o hyd gan ychydig o rifau i wneud ffactoreiddio yn fwy anodd. Gall un rhif un fath i'w gael yn effeithiol trwy brawf yn eu symlrwydd, felly mae'n rhaid i'r amgryptio gwybodaeth fod yn gymhleth o reidrwydd.

Yr allwedd gyhoeddus yn cynnwys fodwlws ac ddehonglwr cyhoeddus. uned dan do ac yn cynnwys ffigwr preifat, a ddylai gael ei gadw'n gyfrinachol.

RSA amgryptio ffeiliau a gwendidau

Fodd bynnag, mae nifer o fecanweithiau RSA hacio syml. Pryd y gall amgryptio â gwerthoedd isel a bach o rifau cod yn cael ei agor yn hawdd, os yw'r ciphertext gwraidd dewis dros y cyfanrif.

Ers y RSA-amgryptio yn algorithm penderfynedig (hy, nid oes elfen ar hap), gall ymosodwr lansio'r ymosodiad agored yn destun a ddewiswyd yn erbyn y cryptosystem llwyddiannus trwy amgryptio plaintexts tebygol o dan yr allwedd gyhoeddus a gwiriadau ar p'un a ydynt yn ciphertext gyfartal. Semantig alw'n cryptosystem diogel yn os na all ymosodwr gwahaniaethu rhwng y ddau amgryptio oddi wrth ei gilydd, hyd yn oed os yw'n gwybod y testunau perthnasol yn y ffurf estynedig. Fel y disgrifiwyd uchod, nid yw RSA gwasanaethau eraill heb padin yn semantig ddiogel.

algorithmau ychwanegol ar gyfer amgryptio a diogelu

Er mwyn osgoi'r problemau uchod, yn y gweithrediad ymarferol y RSA fel arfer yn cael eu mewnosod i ryw fath o strwythuredig, llenwi ar hap cyn amgryptio. Mae hyn yn sicrhau nad yw'r cynnwys yn dod o fewn yr ystod o plaintexts ansicr, ac na all y neges hon yn cael ei datrys drwy ddewis ar hap.

Diogelwch RSA cryptosystem ac amgryptio yn seiliedig ar ddau problemau mathemategol: y broblem o ffactoreiddio rhifau mawr ac mae'r broblem RSA gwirioneddol. Ystyrir datgeliad llawn y ciphertext a llofnod yn y RSA yn annerbyniadwy ar y dybiaeth na all y ddau o'r problemau hyn yn cael eu datrys ar y cyd.

Fodd bynnag, gyda'r gallu i adfer ffactor gysefin, gall ymosodwr gyfrifo ddehonglwr cyfrinach yr allwedd gyhoeddus ac yna dadgryptio testun gan ddefnyddio'r weithdrefn safonol. Er gwaethaf y ffaith na all heddiw oes dull presennol ar gyfer ffactoreiddio gyfanrifau mawr ar gyfrifiadur clasurol i'w cael, nid yw wedi cael ei brofi nad yw'n bodoli.

awtomeiddio

Gall yr offeryn, a elwir Yafu, gael ei ddefnyddio i wneud y gorau y broses. Automation yn YAFU yn nodwedd ddatblygedig sy'n cyfuno algorithmau ffactoriad mewn methodoleg deallusol ac addasol sy'n lleihau'r amser i ddod o hyd i'r ffactorau o rifau mewnbwn mympwyol. Mae'r rhan fwyaf gweithrediadau multithreaded algorithm caniatáu Yafu defnydd llawn o aml- neu lawer o broseswyr aml-graidd (gan gynnwys SNFS, SIQS a ECM). Yn gyntaf oll, mae'n cael ei reoli gan offeryn gorchymyn-lein. Mae'r amser a dreulir yn chwilio am ffactor Yafu encryption ddefnyddio cyfrifiadur confensiynol, gellir ei leihau i eiliadau 103.1746. Mae'r offeryn yn prosesu'r deuaidd gallu 320 ddarnau neu fwy. Mae hwn yn feddalwedd gymhleth iawn sy'n gofyn am rywfaint o sgiliau technegol i osod a ffurfweddu. Felly, efallai y RSA-amgryptio fod yn agored i niwed C.

Hacio ymdrechion yn ddiweddar

Yn 2009, Bendzhamin Mudi ddefnyddio RSA-512 bit allweddol yn gweithio ar ddehongli kriptoteksta am 73 diwrnod, gan ddefnyddio meddalwedd yn unig adnabyddus (GGNFS) a'r y bwrdd gwaith ar gyfartaledd (Athlon64 deuol yn rhai craidd am 1900 MHz). Fel y dangosir gan y profiad, sy'n ofynnol ychydig yn llai na 5 GB o ddisg a thua 2.5 gigabeit o gof ar gyfer y broses o "hidlo."

Fel yn 2010, y nifer fwyaf yn ffactor RSA 768 darnau hir (232 digidau degol, neu RSA-768). Mae ei datgelu para dwy flynedd ar gannoedd o gyfrifiaduron ar yr un pryd.

Yn ymarferol, yr allweddi RSA yn hir - fel arfer 1024-4096 ddarnau. Mae rhai arbenigwyr yn credu y gall y allweddi 1024-bit dod yn annibynadwy yn y dyfodol agos neu hyd yn oed mwy o amser y gellir cracio ymosodwyr a ariennir gan dda iawn. Fodd bynnag, byddai rhai yn dadlau y gallai allweddi 4096-bit hefyd yn cael eu datgelu yn y dyfodol agos.

rhagolygon

Felly, fel rheol, tybir y RSA yn ddiogel os yw'r niferoedd yn ddigon mawr. Os gall y nifer sylfaenol o 300 ddarnau neu fyrrach, ac mae'r llofnod digidol ciphertext cael ei pydredig o fewn ychydig oriau ar gyfrifiadur personol gan ddefnyddio meddalwedd sydd ar gael eisoes yn y parth cyhoeddus. Mae allwedd hyd 512 darnau, fel y dangosir, yn gallu cael ei agor mor gynnar â 1999, gyda'r defnydd o ychydig gannoedd o gyfrifiaduron. Y dyddiau hyn mae'n bosibl mewn ychydig wythnosau gan ddefnyddio caledwedd ar gael i'r cyhoedd. Felly, mae'n bosibl y yn buduschembudet hawdd datgelu RSA-amgryptio ar y bysedd, a bydd y system yn dod yn anobeithiol wedi dyddio.

Yn swyddogol yn 2003, oedd amheuaeth diogelwch y allweddi 1024-bit. Ar hyn o bryd, argymhellir i gael isafswm hyd 2048 ddarnau.