RSA-kryptering. Beskrivning och genomförande av RSA-algoritmen

RSA-kryptering är en av de första praktiska offentliga nyckelkrypto som ofta används för säker dataöverföring. Dess huvudsakliga skillnaden från liknande tjänster är att krypteringsnyckeln är öppen och skiljer sig från krypteringsnyckeln, som hålls hemlig. RSA-teknik , denna asymmetri är baserad på den praktiska svårigheten att facto uppspelningen av två stora primtal (problemet med factoring).

Historien om skapelsen

RSA Namnet består av de första bokstäverna i efternamnen Rivest, Shamir och Adleman - forskarna som först offentligt beskrivs dessa krypteringsalgoritmer 1977. Klifford Koks, en engelsk matematiker, som arbetade för brittiska underrättelsetjänster, det första att utveckla ett likvärdigt system 1973, men det var inte hävas förrän 1997

RSA användare skapar och publicerar sedan den publika nyckeln baserat på två stora primtal tillsammans med hjälpvärdet. Primtal ska hållas hemlig. Vem som helst kan använda den publika nyckeln för att kryptera ett meddelande, men om det är tillräckligt stor, då endast någon med kunskap om primtal kan avkoda meddelandet. RSA-kryptering avslöjande är känt som det största problemet i dag är en öppen diskussion om hur en pålitlig mekanism.

RSA-algoritmen är relativt långsam, varför det inte så stor utsträckning används för att direkt kryptera användaren. I de flesta fall är denna metod som används för sändning i den delade nyckeln krypteras för en symmetrisk krypteringsnyckel, som i sin tur kan utföra operationer bulk kryptering och dekryptering med en mycket högre hastighet.

När det var en krypto i sin nuvarande form?

Idén om asymmetriska kryptonyckel tillskrivs Diffie och Hellman, som publicerade konceptet 1976, att införa digitala signaturer, och försöker att tillämpa teorin om siffror. Deras formulering använder en delad hemlig nyckel som genereras från ett visst antal exponentiering modulo ett primtal. Men de lämnade öppna frågan om förverkligandet av denna funktion, eftersom principerna för factoring inte var väl förstått vid den tidpunkten.

Rivest, Adi Shamir och Adleman vid MIT har gjort flera försök genom åren att skapa en enkelriktad funktion som är svår att avkoda. Rivest och Shamir (som datavetare) har föreslagit många potentiella funktioner, medan Adleman (som matematik) för att söka efter "svaga punkter" av algoritmen. De använde en hel del metoder och så småningom utveckla en slutliga systemet, numera känd som RSA i April 1977.

Elektronisk signatur och den publika nyckeln

Digital signatur eller elektronisk signatur, är en integrerad del av den elektroniska dokumenttyper. Den bildas vid en viss kryptografiska data ändras. Med detta attribut möjligt att kontrollera integriteten av dokumentet, dess sekretess, samt avgöra vem som äger den. I själva verket, ett alternativ till vanlig standard signatur.

Denna krypto (RSA-krypterade) erbjuder den publika nyckeln, till skillnad från symmetrisk. Dess funktionsprincip är att de två olika nycklar används - stängt (krypterat) och utomhus. Den första används för att generera den digitala signaturen och sedan kunna dekryptera texten. Andra - för själva kryptering och elektronisk signatur.

Använda signaturer för att bättre förstå RSA-kryptering, ett exempel på vilken kan reduceras som en normal hemliga "stängd från nyfikna ögon" dokumentet.

Vad är algoritmen?

RSA-algoritmen består av fyra steg: nyckelgenerering, distribution, kryptering och dekryptering. Som redan nämnts, inkluderar RSA-kryptering en publik nyckel och en privat nyckel. Utomhus kan vara känd för alla och används för att kryptera meddelanden. Dess väsen ligger i det faktum att meddelanden krypterade med den publika nyckeln endast kan dekrypteras i en given tidsperiod med hjälp av en hemlig nyckel.

Av säkerhetsskäl till heltal väljas slumpmässigt och vara identiska i storlek, men skiljer sig i längd med några siffror för att göra facto svårare. Samma samma nummer kan effektivt hittas genom ett test i sin enkelhet, så kryptering av information måste med nödvändighet vara komplicerat.

Den offentliga nyckeln består av modulen och allmänheten exponent. Inomhusenhet och består av en privat siffra som bör hållas hemliga.

RSA-kryptering av filer och svagheter

Det finns dock ett antal enkla hacking RSA mekanismer. När kryptering med låga och små värden på kodnummer lätt kan öppnas, om pick rot chiffertexten över heltalen.

Eftersom RSA-kryptering är en deterministisk algoritm (dvs har ingen slumpmässig komponent), en angripare kan lyckas starta den markerade texten öppet angrepp mot kryptosystemet genom att kryptera troliga plaintexts enligt den publika nyckeln och kontrollerar på om de är lika chiffertexten. Semantiskt säker krypto kallas i händelse av att en angripare inte kan skilja mellan de två kryptering från varandra, även om han vet relevanta texter i utökad form. Som beskrivits ovan, är RSA andra tjänster utan stoppning inte semantiskt säker.

Ytterligare algoritmer för kryptering och skydd

För att undvika de ovan nämnda problemen, i det praktiska genomförandet av RSA är vanligen införda i någon form av strukturerade, randomiserad fyllning före kryptering. Detta säkerställer att innehållet inte faller inom området för osäkra plaintexts och att detta budskap inte kan lösas genom slumpmässigt urval.

Security RSA krypto och kryptering bygger på två matematiska problem: problemet med factoring stort antal och den faktiska RSA problem. Full utlämnande av chiffer och underskrift i RSA anses avvisas på antagandet att båda dessa problem inte kan lösas kollektivt.

Men med förmågan att återhämta sig primtalsfaktorer, kan en angripare beräkna den hemliga exponent för den publika nyckeln och sedan dekryptera text med standardförfarandet. Trots att det idag ingen existerande metod för facto stora heltal på en klassisk dator inte kan hittas, har det inte bevisats att han inte existerar.

automation

Verktyget, kallat Yafu kan användas för att optimera processen. Automation i YAFU är en avancerad funktion som kombinerar faktorisering algoritmer intellektuella och adaptiv metod som minimerar tiden för att hitta de faktorer som godtyckliga mata in siffror. De flesta implementationer flertrådade algoritm tillåter Yafu fullt utnyttjande av multi- eller flera multi-core processorer (inklusive SNFS, SIQS och ECM). Först och främst är det styrs av kommandoradsverktyg. Tiden söker kryptering Yafu faktor med hjälp av en konventionell dator, kan det sänkas till sekunder 103.1746. Verktyget bearbetar binära kapacitet på 320 bitar eller mer. Detta är en mycket komplex programvara som kräver ett visst mått av tekniska färdigheter för att installera och konfigurera. Således kan RSA-kryptering vara sårbara C.

Intrångsförsök på senare tid

Under 2009 var Bendzhamin Mudi använder RSA-512 bitars nyckel arbetar dechiffrera kriptoteksta för 73 dagar, med enbart välkända programvara (GGNFS) och den genomsnittliga skrivbordet (dual-core Athlon64 vid 1900 MHz). Som framgår av erfarenhet, krävs något mindre än 5 GB disk och cirka 2,5 gigabyte minne för processen att "siktning".

Från och med 2010 har det största antalet vägas RSA 768 bitar lång (232 decimaler, eller RSA-768). Hans avslöjande varade i två år på flera hundra datorer på en gång.

I praktiken RSA-nycklar är långa - oftast från 1024 till 4096 bitar. Vissa experter tror att 1024-bitars nycklar kan bli otillförlitlig inom en snar framtid eller ännu längre kan knäckas mycket välfinansierade angripare. Dock skulle få hävda att 4096-bitars nycklar kan också avslöjas inom en snar framtid.

utsikter

Därför, som regel, antas det att RSA är säker om siffrorna är tillräckligt stor. Om bastalet 300 bitar eller kortare, och chiffer digital signatur kan brytas ned inom ett par timmar på en dator med hjälp av programvara som redan finns i det offentliga rummet. En nyckellängd 512 bitar, såsom visas, kan öppnas så tidigt som 1999, med användning av ett par hundra datorer. Numera är det möjligt i ett par veckor med hjälp av en allmänt tillgänglig hårdvara. Sålunda är det möjligt att i buduschembudet lätt avslöjas RSA-krypterade på fingrarna, och systemet kommer att bli hopplöst föråldrade.

Officiellt 2003 ifrågasattes säkerheten för de 1024-bitars nycklar. För närvarande är det rekommenderas att ha en minimilängd 2048 bitar.