RSA-enkripsie. Beskrywing en implementering van die RSA-algoritme

RSA-enkripsie is een van die eerste praktiese openbare-sleutel crypto wat algemeen gebruik word vir 'n veilige data-oordrag. Die belangrikste verskil van soortgelyke dienste is dat die enkripsie sleutel is oop en anders as die dekripsie sleutel, wat geheim gehou. Die RSA-tegnologie , hierdie asimmetrie is gebaseer op die praktiese probleme van factoring die speel van twee groot priemgetalle (die probleem van factoring).

Geskiedenis van die skepping

RSA Die naam bestaan uit die eerste letters van die vanne Rivest, Shamir en Adleman - die wetenskaplikes wat die eerste keer in die openbaar hierdie beskryf enkripsie-algoritmes in 1977. Klifford KOKS, 'n Engelse wiskundige, wat vir die Britse intelligensie dienste het, die eerste om 'n soortgelyke stelsel te ontwikkel in 1973, maar dit is nie gederubriceerd tot 1997

RSA gebruiker skep en dan publiseer die publieke sleutel gebaseer op twee groot priemgetalle saam met die hulp waarde. Priemgetalle moet geheim gehou word. Enigeen kan die publieke sleutel gebruik om 'n boodskap te enkripteer, maar as dit is groot genoeg is, dan net iemand met kennis van priemgetalle kan die boodskap te ontsyfer. RSA enkripsie bekendmaking staan bekend as die grootste probleem vandag is 'n oop gesprek oor hoe 'n betroubare meganisme.

RSA-algoritme is relatief stadig, waarvoor rede dit is nie so wyd gebruik word om direk te enkripteer die gebruiker. In die meeste gevalle, is hierdie metode wat gebruik word vir die oordrag in die gedeelde sleutel geïnkripteer vir 'n simmetriese enkripsie sleutel, wat op sy beurt kan bedrywighede grootmaat enkripsie en dekripsie op 'n veel hoër spoed uit te voer.

Wanneer daar 'n crypto in sy huidige vorm?

Die idee van asimmetriese kriptografiese sleutel toegeskryf word aan Diffie en Hellman, wat die konsep in 1976 gepubliseer, die bekendstelling van digitale handtekeninge, en probeer om die teorie van getalle toe te pas. Hul formulering gebruik 'n gedeelde geheime sleutel gegenereer uit 'n sekere aantal van magsverheffing modulo n priemgetal. Hulle het egter oopgelaat die kwessie van die verwesenliking van hierdie funksie, aangesien die beginsels van factoring is nie goed verstaan op die oomblik.

Rivest, Adi Samir en Adleman by MIT het verskeie pogings oor die jare om 'n one-way funksie wat is moeilik om te ontsyfer skep gemaak. Rivest en Shamir (soos rekenaar wetenskaplikes) het baie potensiaal funksies voorgestel, terwyl Adleman (soos wiskunde) om te soek na "swak punte" van die algoritme. Hulle gebruik 'n baie benaderings en uiteindelik 'n finale stelsel, nou bekend as RSA in April 1977 te ontwikkel.

Elektroniese handtekening en die publieke sleutel

Digitale handtekening of elektroniese handtekening, is 'n integrale deel van die elektroniese dokument tik. Dit is gevorm op 'n sekere kriptografiese data veranderinge. Met hierdie kenmerk moontlik om die integriteit van die dokument kyk, sy vertroulikheid, asook om vas te stel wat dit besit. Trouens, 'n alternatief vir gewone standaard handtekening.

Dit crypto (RSA-geïnkripteer) bied die openbare sleutel, in teenstelling met simmetriese. Die beginsel van werking is dat die twee verskillende sleutels gebruik - gesluit (geïnkripteer) en buite. Die eerste gebruik word om die digitale handtekening te genereer en dan in staat wees om die teks dekripteer. Tweede - vir die werklike kodering en elektroniese handtekening.

Die gebruik van handtekeninge om beter te verstaan die RSA enkripsie, 'n voorbeeld van wat kan verminder word as 'n normale geheim "gesluit van die gierige oë," die dokument.

Wat is die algoritme?

RSA algoritme bestaan uit vier stappe: sleutel generasie, verspreiding, enkripsie en dekripsie. Soos reeds genoem, RSA-enkripsie sluit 'n publieke sleutel en 'n private sleutel. Buite kan bekend geword aan al en word gebruik om boodskappe te enkripteer. Die essensie lê in die feit dat boodskappe geïnkripteer met die openbare sleutel kan slegs Ontcijferde in 'n gegewe tydperk met behulp van 'n geheime sleutel.

Om veiligheidsredes, die heelgetalle te kies na willekeur en wees identies in grootte, maar verskil in lengte deur 'n paar nommers te maak factoring moeiliker. Dieselfde ewe veel kan effektief gevind word deur 'n toets in hul eenvoud, so die kodering van inligting moet noodwendig ingewikkeld.

Die publieke sleutel bestaan uit die modulus en openbare eksponent. Binnenshuise eenheid en bestaan uit 'n private figuur, wat geheim moet bly.

RSA enkripsie van lêers en swakhede

Daar is egter 'n aantal eenvoudige inbraak RSA meganismes. Wanneer versleutelen met 'n lae en klein waardes van kodenommers maklik oopgemaak kan word, indien die pick wortel kriptoteks oor die heelgetalle.

Sedert die RSA-enkripsie is 'n deterministiese algoritme (dit wil sê, het geen ewekansige komponent), 'n aanvaller kan die geselekteerde teks oop aanval teen die crypto suksesvol van stapel te stuur deur versleutelen waarskynlik plaintexts onder die publieke sleutel en tjeks op die vraag of hulle gelyk kriptoteks. Semanties veilige crypto genoem in die geval dat 'n aanvaller nie kan onderskei tussen die twee enkripsie van mekaar, selfs as hy weet die betrokke tekste in die uitgebreide vorm. Soos hierbo beskryf, RSA ander dienste sonder padding is nie semanties veilige.

Bykomende algoritmes vir kodering en beskerming

Om die bogenoemde probleme te vermy, in die praktiese implementering van RSA word gewoonlik plaas in een of ander vorm van gestruktureerde, ewekansige vul voor enkripsie. Dit verseker dat die inhoud nie binne die omvang van onseker plaintexts val, en dat hierdie boodskap nie opgelos kan word deur ewekansige seleksie.

Sekuriteit RSA crypto en enkripsie gebaseer op twee wiskundige probleme: die probleem van factoring groot getalle en die werklike RSA probleem. Volle bekendmaking van die kriptoteks en handtekening in die RSA beskou ontoelaatbaar op die aanname dat beide van hierdie probleme nie gesamentlik opgelos kan word.

Maar met die vermoë om priemfaktore te herstel, 'n aanvaller kan die geheim eksponent van die publieke sleutel te bereken en dan decrypt teks met behulp van die standaard prosedure. Ten spyte van die feit dat ons vandag geen bestaande metode vir factoring groot heelgetalle op 'n klassieke rekenaar nie gevind kan word, het dit nie bewys dat hy nie bestaan nie.

outomatisering

Die instrument, genaamd Yafu, kan gebruik word om die proses te optimaliseer. Outomatisering in YAFU is 'n gevorderde funksie wat faktorisering algoritmes kombineer in intellektuele en aangepaste metode wat die tyd om die faktore van arbitrêre inset getalle vind verminder. Die meeste implementering multi algoritme toe te laat Yafu ten volle gebruik van multi- of baie multi-core processors (insluitend SNFS, SIQS en ECM). In die eerste plek, is dit beheer word deur command-line hulpmiddel. Die tyd spandeer op soek na encryption Yafu faktor met behulp van 'n konvensionele rekenaar, kan dit verminder word tot sekondes 103,1746. Die instrument verwerk die binêre kapasiteit van 320 stukkies of meer. Dit is 'n baie komplekse sagteware wat 'n sekere bedrag van tegniese vaardighede om te installeer en instel vereis. Dus, kan RSA-enkripsie wees kwesbaar C.

Inbraak pogings in die afgelope tyd

In 2009, Bendzhamin Mudi met behulp van RSA-512 bis sleutel is besig om op te ontsyfer kriptoteksta vir 73 dae, met behulp van slegs bekende sagteware (GGNFS) en die gemiddelde lessenaar (dual-core Athlon64 by 1900 MHz). Soos blyk uit die ervaring, wat nodig is effens minder as 5 GB hardeskyf en sowat 2,5 GB geheue vir die proses van "sif."

Soos van 2010, is die grootste getal ingereken RSA 768 stukkies lang (232 desimale syfers, of RSA-768). Sy bekendmaking geduur twee jaar 'n hele paar honderd rekenaars in 'n keer.

In die praktyk, die RSA sleutels is lank - tipies 1024-4096 stukkies. Sommige kenners glo dat die 1024-bit sleutels onbetroubaar kan wees in die nabye toekoms of selfs langer kan gekraak baie goed befonds aanvallers. Maar min mense sou argumenteer dat 4096-bit sleutels ook kan openbaar gemaak word in die nabye toekoms.

vooruitsigte

Daarom, as 'n reël, is dit aanvaar dat RSA is veilig as die getalle is groot genoeg. As die basis aantal 300 stukkies of korter, en die kriptoteks digitale handtekening kan ontbind word binne 'n paar uur op 'n persoonlike rekenaar met behulp van sagteware wat reeds beskikbaar is in die openbare domein. 'N Belangrike lengte 512 stukkies, soos aangedui, kan so vroeg as 1999 geopen, met die gebruik van 'n paar honderd rekenaars. Deesdae is dit moontlik in 'n paar weke met behulp van 'n publiek sigbaar hardeware. Dus, is dit moontlik dat in buduschembudet maklik openbaar RSA-geïnkripteer op die vingers, en die stelsel sal hopeloos verouderd geraak.

Amptelik in 2003, is in twyfel getrek die veiligheid van die 1024-bit sleutels. Op die oomblik word dit aanbeveel om 'n minimum lengte van 2048 bisse het.