RSA-ĉifrado. Priskribo kaj efektivigo de la RSA algoritmo

RSA-ĉifrado estas unu el la unuaj praktikaj publik-ŝlosilaj ĉifrosistemoj kiu vaste uzata por sekura transdono de datumoj. Lia ĉefa diferenco de simila servoj estas ke la ĉifroŝlosilo estas malfermita kaj malsama al la malĉifro ŝlosilo, kiu estas konservita sekreta. La RSA teknologio , ĉi tiu nesimetrio estas bazita sur la praktika malfacileco de faktoranta la reprodukto de du grandaj primoj (la problemo de faktoranta).

Historio de kreado

RSA La nomo konsistas el la komencaj literoj de la familiaj nomoj Rivest, Shamir kaj Adleman - la sciencistoj kiu unue publike priskribis tiujn ĉifrado algoritmoj en 1977. Klifford Koks, angla matematikisto, kiu laboris por la brita inteligenteco servoj, la unua evoluigi ekvivalentan sistemon en 1973, sed ĝi ne estis malsekretigita ĝis 1997

RSA uzanto kreas kaj publikigas la publika ŝlosilo en funkcio de du grandaj primoj kaj ankaŭ la helpa valoro. Primoj estas gardata sekreto. Iu ajn povas uzi la publikan ŝlosilon por ĉifri mesaĝon, sed se ĝi estas sufiĉe granda, do nur iu kun scio de primoj povas deĉifri la mesaĝon. RSA ĉifrado malkaŝo estas konata kiel la ĉefa problemo hodiaŭ estas malfermita diskuto pri kiel fidinda mekanismo.

RSA algoritmo estas relative malrapida, por kiu kialo ĝi ne estas tiel vaste uzata por rekte ĉifri la uzanto. Plejofte, ĉi metodo estas uzata por dissendo en la dividita ŝlosilo ĉifrita por simetria ĉifrado ŝlosilo, kiu siavice povas realigi operacioj dika ĉifrado kaj malĉifro je multe pli alta rapideco.

Kiam estis ĉifrosistemo en ĝia nuna formo?

La ideo de nesimetria ĉifrika ŝlosilo atribuita al Diffie kaj Hellman, kiu eldonis la koncepton en 1976, enkondukante ciferecaj signumoj, kaj provas apliki la teorion de nombroj. Ilia formulaĵo uzas dividita sekreto ŝlosilon generita de certa nombro de potencigo module primo. Tamen, ili lasis malfermi la demando pri realigo de tiu funkcio, kiam la principoj de faktoranta ne bone komprenita tiutempe.

Rivest, Adi Shamir, kaj Adleman ĉe MIT faris plurajn provojn tra la jaroj por krei unudirekta funkcio kiu estas malfacila por deĉifri. Rivest kaj SXamir (kiel komputilo sciencistoj) proponis multajn eblajn funkciojn, dum Adleman (kiel matematiko) por serĉi "malfortaj punktoj" de la algoritmo. Ili uzis multajn alproksimiĝojn kaj eventuale disvolvos fina sistemo, nun konata kiel RSA en aprilo 1977.

Elektronika subskribo kaj la publika ŝlosilo

Digital subskribon aŭ elektronika subskribo, estas integrita parto de la elektronika dokumento tipoj. Estas formita ĉe certa ĉifrikaj datumoj ŝanĝoj. Kun ĉi eco ebla por kontroli la integrecon de la dokumento, ĝia confidencialidad, kaj ankaŭ por determini kiu posedas ĝin. Fakte, alternativa al ordinara norma subskribo.

Ĉi ĉifrosistemo (RSA-ĉifrita) proponas la publika ŝlosilo, malkiel simetria. Lia komenco de funkciado estas, ke la du malsamaj ŝlosiloj estas uzataj - fermita (ĉifrita) kaj subĉiela. La unua estas uzata por generi la ciferecan subskribon kaj poste povos deĉifri la tekston. Due - pro la efektiva ĉifrado kaj elektronika subskribo.

Uzante subskribojn por pli bone kompreni la RSA ĉifrado, ekzemplo de kiu povas esti reduktita kiel normala sekreta "fermita de maldiskretaj okuloj," la dokumento.

Kio estas la algoritmo?

RSA algoritmo konsistas el kvar paŝojn: klavo generacio, dissendo, ĉifrado kaj malĉifro. Kiel dirite, RSA-ĉifrado inkludas publikan ŝlosilon kaj privata ŝlosilo. Subĉiela sciebla al ĉiuj kaj estas uzita por ĉifri mesaĝojn. Lia esenco estas en tio, ke la mesaĝoj koditaj kun la publika ŝlosilo nur povas esti deĉifrita en antaŭfiksita tempodaŭro uzante sekretan ŝlosilon.

Por sekureco, la entjeroj estas preferinda al la hazardo kaj esti identa en grandeco, sed malsamas en longo de kelkaj nombroj fari faktoranta pli malfacila. Sama sama nombro povas esti efike trovita de provo en sia simpleco, do la ĉifrado de informoj devas nepre kompliki.

La publika ŝlosilo konsistas la modulo kaj publika eksponento. Endoma unuo kaj konsistas privata figuro, kiu estas gardata sekreto.

RSA ĉifrado de dosieroj kaj malfortojn

Tamen, estas kelkaj simplaj hacking RSA mekanismoj. Kiam kodi kun malaltaj kaj malgrandaj valoroj de kodo nombroj povas ilin malfermi, se la elekto radiko ĉifrita teksto super la entjeroj.

Ekde la RSA-ĉifrado estas determinisma algoritmo (tio estas, ne havas hazardaj komponanto), atacante povas sukcese lanĉi la elektitan tekston malfermita atako kontraŭ la ĉifrosistemo de kodi verŝajna fontajn tekstojn sub la publika ŝlosilo kaj ĉekojn ĉu ili estas egalaj ĉifrita teksto. Semantike sekura ĉifrosistemo estas nomita okaze ke atacante ne povas distingi inter ambaŭ ĉifrado unu de la alia, eĉ se li scias la gravaj tekstoj de la pligrandigita formo. Kiel priskribita supre, RSA aliaj servoj sen kompletigo ne estas semantike sekura.

Kromaj algoritmoj por ĉifrado kaj protekto

Por eviti la supre problemojn, en la praktika efektivigo de RSA estas kutime aldonitaj en iu formo de strukturita, hazardigitaj kompletigo antaux ĉifrado. Tio certigas, ke la enhavo ne falas ene de la gamo de nesekura fontajn tekstojn kaj ke tiu ĉi mesaĝo ne povas esti solvita per hazardaj elekto.

Sekureco RSA ĉifrosistemo kaj ĉifrado bazita sur du matematikaj problemoj: la problemo de faktoranta nombregoj kaj la reala RSA problemo. Plena malkaŝo de la ĉifrita teksto kaj subskribo en la RSA estas konsiderata neakceptebla sur la supozo ke ambaŭ problemoj ne povas esti solvitaj kolektive.

Tamen, kun la kapablo por rekuperi primaj faktoroj, atacante povas kalkuli la sekreta eksponento de la publika ŝlosilo kaj poste deĉifri tekston uzante la norma procedo. Malgraŭ tio, ke hodiaŭ jam ekzistantan metodon por faktoranta grandaj entjeroj en klasika komputilo ne povas esti trovita, ĝi ne estis provita, ke li ne ekzistas.

aŭtomatigo

La ilo, nomita Yafu, povas esti uzita por optimumigi la procezo. Aŭtomatigo en YAFU estas progresinta trajto kiu kombinas faktorigaj algoritmoj en intelekta kaj adapta metodiko kiu minimumigas la tempon por trovi la faktorojn de arbitra enigo nombroj. Plej implementaciones disfadeniga algoritmo permesante Yafu plenan uzon de multi- aŭ multaj procesoroj multi-kerno (inkluzive SNFS, SIQS kaj ECM). Unue, ĝi estas kontrolitaj de Komandlinia ilo. La tempo pasigita serĉi ĉifrado Yafu faktoro uzante konvencia komputilo, ĝi povas esti reduktita al sekundoj 103,1746. La ilo procesas la duumaj kapaciton de 320 bitoj aŭ pli. Tiu estas tre kompleksa programaro kiu postulas certan kvanton de teknikaj kapabloj por instali kaj agordi. Tiel, RSA-ĉifrado povas esti vundebla C.

Hacking provoj en la lastaj tempoj

En 2009, Bendzhamin Mudi-hundo uzante RSA-512 bita ŝlosilo laboris pri deĉifri kriptoteksta por 73 tagoj, uzante nur konata softvaro (GGNFS) kaj la meza labortablo (duobla kerno Athlon64 ĉe 1900 MHz). Kiel montrita per la sperto, postulata iomete malpli ol 5 GB de disko kaj ĉirkaŭ 2.5 gigabajtoj de memoro por la procezo de "cribado."

Aktuale en 2010, la plej granda nombro estis faktorita RSA 768 bitoj longa (232 decimaloj, aŭ RSA-768). Lia malkaŝo daŭris du jarojn sur kelkcent komputiloj tuj.

Praktike, la RSA klavoj estas longa - kutime de 1024 al 4096 pecoj. Iuj fakuloj kredas ke la 1024-bita klavoj povas iĝi nefidinda en proksima estonteco aŭ eĉ pli longe povas esti fendita tre bone financata atacantes. Tamen, kelkaj argumentus ke 4096 bitoj klavoj povas ankaŭ esti malkaŝitaj en la proksima estonteco.

perspektivojn

Tial, kiel regulo, ĝi supozas ke RSA estas sekura se la nombroj estas sufiĉe granda. Se la bazo da 300 bitoj aŭ malpli longa, kaj la ĉifrita teksto ciferecan subskribon povas esti malkomponita post kelkaj horoj sur personan komputilon uzante programaro disponebla jam en la publika domajno. Ŝlosilo longo 512 bitoj, kiel montrita, povas esti malfermita jam en 1999, kun la uzo de kelkaj cent komputiloj. Nuntempe eblas post kelkaj semajnoj uzante publike disponebla aparataro. Tiel, ĝi eblas kiu en buduschembudet facile malkaŝitaj RSA-ĉifrita sur la fingroj, kaj la sistemo estos senespere malmoderna.

Oficiale en 2003, estis nomita en demandon la sekureco de la 1024-bita ŝlosilojn. Nuntempe, ĝi rekomendas havi minimumon longo de 2048 bitoj.